<trollin>

DanielTheGeek:


Minus GCD of what and what? I appreciate your effort but please don't just google and implement straight away..

Although I really commend your effort and at this stage you have gotten to I'd really like to know you more.... (That's for another day though, let's not derail) because you're getting a tad bit close to the actual efficient solution..but your answer is just not correct as it lacks mathematical logic..

let v = gcd of x and y
let n = number of cells

n = (x + y) - v

I just realized if x = y, gcd of x and y = x = y

I only googled the meaning of gcd (and found out it meant hcf, americans with their naming wahala ) and used "v" hint you provided

Can you or seunthomas help we children with an answer?... We're kinda trying to figure things out..

dhtml118:
<trollin>

orimion:
gcd of x and y

I only googled the meaning of gcd (and found out it meant hcf, americans with their naming wahala ) and used "v" hint you provided

Nice try...but overall, you're still wrong or rather looking wrong in my opinion till I can be disproved... Let me just tender my solution: Note: I never saw the correct answer for the question so I guess the only way to prove is to test in a language and benchmark if possible... Then 4kings will test his.

Since we already know and accept that v = gcd of x and y then let a=x/v and b=y/v. It's obvious that gcd(a,b)=1. As i mentioned earlier, starting from the cell (0,0) - (1,1) to the cell (a-1,b-1)-(a,b), the line moves either to the right or above the cell. If it moves to the right (above), the x(y) coordinate gets incremented. The line passes through a+b-1 cells. So therefore, we can come up with a formula;

(a+b-1)*gcd(x,y) to get the total count of cells in any condition...

DanielTheGeek:
But before then, I have a simple question.. I don't need to see code; just logical reasoning..
(Taken from an interview of a company I worked for)

In a co-ordinate plane, a line segment is drawn from the origin to a point A(x,y). With great efficiency, find the number of cells the line passes through Assuming X and Y are ints...

Google may not be of too much help, this is largely theoretical.

Mod: let's have more of this kind of questions as the ones involving code can easily be Googled or outsourced.. This tests the fundamental knowledge of computer science.. Programming is more of thinking than coding

I may ve wrong but this can be solved by finding the distance between the two points. On the Euclidean plane , i think density equals distance.

DanielTheGeek:
But before then, I have a simple question.. I don't need to see code; just logical reasoning..
(Taken from an interview of a company I worked for)

In a co-ordinate plane, a line segment is drawn from the origin to a point A(x,y). With great efficiency, find the number of cells the line passes through Assuming X and Y are ints...

Google may not be of too much help, this is largely theoretical.

Mod: let's have more of this kind of questions as the ones involving code can easily be Googled or outsourced.. This tests the fundamental knowledge of computer science.. Programming is more of thinking than coding

Not a programmer but I strolled in here. . .I found this 'correlation'.

The number of cells it passes through = (a/b) × b

Where a is the larger number of the two coordinates and b is the smaller number.

Another condition is that if "a/b" gives a decimal number, no matter how small, it should be rounded up to the next whole number.

For example, the one in the picture, we have

(10/4) × 4

= 3 × 4 = 12 cells.


(Provided both a and b DO NOT equal 0)

Before test results come in, let's play around with actual coding so other guys can join in;

Find if a set of given positive integers can be divided into two parts (subsets) with equal sum.

Example:
Where S represents sets and Sn represents subsets;

S = { 5, 2, 2, 3, 3, 4, 1 }

Partitioning will give us;
S1 = { 5, 2, 3 }
S2 = { 2, 3, 4, 1 }

Summation of S1 and S2 will give a total of the sum of values in the original set.

It's not compulsory for integers in subsets to be arranged in any order.. As far as the summation gives the required results, you're good to go...

I love this thread.

If x and y were to always be the same value then this could workout although with further hacks.. But X can be anything and Y could be anything so it's possible for the line to even be curved at some point but the distance will remain constant hence.. This won't be accurate at all.

bolkay47:
I may ve wrong but this can be solved by finding the distance between the two points. On the Euclidean plane , i think density equals distance.

DanielTheGeek:

(a+b-1)*gcd(x,y) to get the total count of cells in any condition...

here I tested your answer with mine for every possible pair combination of the arrays [356, 357,... 800] and [119, 120,...715. Both gave the same answer. The language is haskell. Please try to do in your preferred language

Wow (*leaves work and focuses on the thread*)

Super duper awesome, which planet are you from? Thanks for testing if both gives the same result then there could be bottlenecks in either of the solutions... Can you run a benchmark test against both in Haskell?

Remember the question placed focus on efficiency... Thus any solution could still be considered a failure if it's not efficient enough.

orimion:

here I tested your answer with mine for every possible pair combination of the arrays [356, 357,... 800] and [119, 120,...715. Both gave the same answer. The language is haskell. Please try to do in your preferred language

But this Haskell syntax na wa o... I honestly just managed to read the code in the test, can anyone familiar with Haskell take a look at the code to confirm if it's free of logical errors?

Asalimpo is right and no matter what...whether you get the desired result.. a -0.1ms difference in performance should mean a lot to you. Remember, good companies won't look only for the program that gets the job done but the one that gets it done faster... Good job though.

bolkay47:
Good evening.
You may be right. The solution gets the job done and it took '00:00:00.1405923' which in my opinion is still good....
if you have any other method, you can put it forward.I will be glad to see it.
Can you help me locate the OP?

DanielTheGeek:
Can you run a benchmark test against both in Haskell?

I'm not sure I can, maybe someone in anothe language?

I just dey see different languages for this thread. I use to think people here only run their mouth o.
Hmn, where is that pesky moderator that is always ban ban, hope you are seeing all this now? Tobaya, you will start banning people upandan.

I remember once posting on this section that i know close to 20 programming languages and some unfortunate fellow felt i was lying or blowing a big trumpet. But alas people with knowledge of haskell have found their way into this thread.
But for those of us rushing into functional programming beware...
OOP is the best approach and won't die anything time soon.
Be functional but Objects will always triumph....

DanielTheGeek:
Asalimpo is right and no matter what...whether you get the desired result.. a -0.1ms difference in performance should mean a lot to you. Remember, good companies won't look only for the program that gets the job done but the one that gets it done faster... Good job though.

I disagree with you completely. Although performance is important, it is only one of the very many important metrics...

na wa oh...I'm a 400L student of computer science (soon to graduate) and I don't know jack of what's been said in this thread...I fear for life after school oh..GOD help me...how do I learn coding/hackingall I can beat my chest after school is my maths skills.. chai.. a 4pointer. for that matter.. and I currently don't have the money all these coding/programming schools are requesting.. how do I learn all thesesome one should please help out...God bless!!

*Watching Seunthomas* Like Seun is watching me *

seunthomas:

I disagree with you completely. Although performance is important, it is only one of the very many important metrics...

Then you're disagreeing with yourself because You said completely and went on to mention performance as one of the very many...

You should disagree partially, however performance is still quite very important too which is why pantheon will probably kick out it's CMS hosting competitors in few years..

When you have two apps performing the same task, every other thing looks good, it's hard to differentiate which app to go for as a tech company then it's down to performance.. To an average Joe, he'd probably go for the app that makes more business sense at the cost of performance when the performant application could easily be upgraded.

The secret about learning ANY language is in every developer, getting is just the tricky part..

There's a difference between understanding a language and knowing a language. TF! I can keep a list of languages I know coming in till tomorrow.. But the languages I understand in-out aren't more than 5 or 6.. However I think Seunthomas has gotten to the stage where he doesnt need an eBook or video to learn a new language..even i have gotten to that stage and it's not pride, we all learn everyday, every ambitious/serious programmer will get to that stage....all you do is apply your previous knowledge of other languages to work with the new one... As far as you have good knowledge of at least one functional and one object oriented language then picking another language will be a matter of adapting to the syntax and learning the conventions. I will not forget ShedrachOkonofua...one of the finest devs I met on NL, this guy is a real polyglot developer and I respect him much as I respect others in here.

But what I have come to discover in my little years of gaining peanut knowledge is that polyglot developers are the least efficient in the room as devs with a focus on a single language tend to do more, but this is only my opinion/theory...

seunthomas:
I remember once posting on this section that i know close to 20 programming languages and some unfortunate fellow felt i was lying or blowing a big trumpet. But alas people with knowledge of haskell have found their way into this thread.
But for those of us rushing into functional programming beware...
OOP is the best approach and won't die anything time soon.
Be functional but Objects will always triumph....

Does Daniel know the BrainFuck language , Yeah....can he write a simple hello world program in it? Hell no..

Yeah, knowing multiple languages is one thing, but practicing multiple languages on production level is a very inefficient thing for a developer, and it is not something to be desired truly.

DanielTheGeek:
The secret about learning ANY language is in every developer, getting is just the tricky part..

There's a difference between understanding a language and knowing a language. TF! I can keep a list of languages I know coming in till tomorrow.. But the languages I understand in-out aren't more than 5 or 6.. However I think Seunthomas has gotten to the stage where he doesnt need an eBook or video to learn a new language..even i have gotten to that stage and it's not pride, we all learn everyday, every ambitious/serious programmer will get to that stage....all you do is apply your previous knowledge of other languages to work with the new one... As far as you have good knowledge of at least one functional and one object oriented language then picking another language will be a matter of adapting to the syntax and learning the conventions. I will not forget ShedrachOkonofua...one of the finest devs I met on NL, this guy is a real polyglot developer and I respect him much as I respect others in here.

But what I have come to discover in my little years of gaining peanut knowledge is that polyglot developers are the least efficient in the room as devs with a focus on a single language tend to do more, but this is only my opinion/theory...



Does Daniel know the BrainFuck language , Yeah....can he write a simple hello world program in it? Hell no..

Mr man, stop making nonsense noise and lets go head to head. Infact i will allow you pick the language you want me to write the solution in. Lets see if your silly theory on polygot holds water. For someone like me every language is one and the same. Programming is first like an art, you have to know how to paint and then you can use the brush and paint to create a work of art. I am waiting for you to challenge me else dont be making generalized statements like someone who said Naija coders are copy pasters. You don interview every polygot programmer before

seunthomas:

Mr man, stop making nonsense noise and lets go head to head. Infact i will allow you pick the language you want me to write the y pasters. You don interview every polygot programmer before

Are you an expert [at programming] ?

This thread is fast deviating to chest-thumping.

dhtml118:
This thread is fast deviating to chest-thumping.

Some people just like to weigh everyone based on their own mental capacity.

Because you can do 2X2 table only does not mean there are people who can't do 10X10 or 20X20.

Anyway as the CEO of this thread, i caution everyone to be on track.

The whole idea is to create an environment where we can freely exchange ideas (in a competitive environment).

I am still looking for that rocket man that has been deleting my threads...

Hmn, I agree, what will you do to the said "rocket man"? Allow him to go scot-free?

hMM, haskel that's cool.

@danielthegeek et al...
here's the code:
apologies for my variable naming.

def func(lenY, m, b):
    lenY, m, b = lenY, m, b
    x_points, fac = [], 0
    
    for y in range(1,lenY+1):
        x = (y - b)/m
        
        if x.is_integer() is not True:
            x_points.extend(list(range(fac, int(x)+1)))
            x_points.append(x_points[-1])
            fac = int(x) + 1
        else:
            x_points.extend(list(range(fac, int(x)+1)))
            fac = int(x) + 1
    
    dif = int(len(x_points[:-1])/lenY)
    y_points = [i for i in range(1,lenY+1) for j in range(dif)]
    
    cells = len(x_points[:-1])
    cells_coordinates = list(zip(y_points, x_points[:-1]))
    
    return(cells, cells_coordinates)

the function takes in height or lenght of Y, m and b.
m is gradient of line; using any two point in y will give 0.4
b is point of intersection which is 0.
so if two list of values for x and y is given, the common number is the intersection and m is determined by picking any two values from y with respect to x. change in y/change in x

then the function calculates the number of cells and also give the coordinates or location of each cell from the top.

number, locations = func(4, 0.4, 0)

Benchmark:
import timeit
timer = timeit.Timer('func(3,0.4,0)', 'from __main__ import func')
benchmark = timer.timeit(number=1000)
print(benchmark)

It took average of 0.026 seconds with 1000 number of executions.

When i increased Y to 1000. That is func(1000, 0.4,0); Python messed me up, it took average of 5.3 seconds.

So there's the code, returning number of cells and their locations.

---

I didn't loop through every value of x like i said before that is 0.1,0.2 to 10.
I just calculated x at different values of y(intervals), and any number that exceeded an integer indicates a repeated cell.
For example if x values are 2.5, 5, 7.5, 10. 2.5 is counted twice because it extends to cell 3.

Just incase anyone is still confused on how to get m and b (gradient and intersection).
here's an example:
From the diagram:
x = [0, 2.5, 5, 7.5, 10]
y = [0, 1, 2, 3, 4]

0 is b the intersection. ==> filter(lambda x:x in x,y)

gradient(m) is 2-1/5-2.5 or 4-3/10-7.5 or any two values of y and x.

then put the variables in the function parameters.
func(lenY, m, b)
lenY is obviously lenght of Y which is 4. len(Y)

DONADAMS:
na wa oh...I'm a 400L student of computer science (soon to graduate) and I don't know jack of what's been said in this thread...I fear for life after school oh..GOD help me...how do I learn coding/hackingall I can beat my chest after school is my maths skills.. chai.. a 4pointer. for that matter.. and I currently don't have the money all these coding/programming schools are requesting.. how do I learn all thesesome one should please help out...God bless!!

Lmao-ing at that first line. I'm positive there are programmers in your department. Yo can move closer to them and see where it leads you.

seunthomas:

Mr man, stop making nonsense noise and lets go head to head. Infact i will allow you pick the language you want me to write the solution in. Lets see if your silly theory on polygot holds water. For someone like me every language is one and the same. Programming is first like an art, you have to know how to paint and then you can use the brush and paint to create a work of art. I am waiting for you to challenge me else dont be making generalized statements like someone who said Naija coders are copy pasters. You don interview every polygot programmer before

Hmm, can you write a code that rearranges pixels in an image based on hue value(or any other image parameter you want) in assembly?

seunthomas:

Mr man, stop making nonsense noise and lets go head to head. Infact i will allow you pick the language you want me to write the solution in. Lets see if your silly theory on polygot holds water. For someone like me every language is one and the same. Programming is first like an art, you have to know how to paint and then you can use the brush and paint to create a work of art. I am waiting for you to challenge me else dont be making generalized statements like someone who said Naija coders are copy pasters. You don interview every polygot programmer before

You should be able to read in between the lines... No beef man, I stated clearly that it's a personal opinion/theory, it's okay not believe it and once again as i said earlier, programming is not all about writing code..