Santa maria! egba mi o! 10k!!

dhtml118:
Santa maria! egba mi o! 10k!!

Una i go chop dat boy money.

seunthomas:

When i finish eating your money. I will still go back to insulting you until you confirm you lied....

I don compile the interpreter now now....

Which one be compiling of interpreter again?
Lol, abeg o, grant me parole on that case o.

No diss jarey, all these is just to catch fun...

DanielTheGeek:


Which one be compiling of interpreter again?
Lol, abeg o, grant me parole on that case o.

No dies jarey, all these is just to catch fun...

Na beg you dey beg?? But you were so confident about this your 10K bet ohhh. If this boy waste my time, na annihilate i go annihilate am ohhhh.

seunthomas:

Una i go chop dat boy money.

Maybe 4Kings may eat it before you even though you have a big mouth...

DanielTheGeek:


Maybe 4Kings may eat it before you even though you have a big mouth...

See this man. I don dey learn the syntax already....

seunthomas:

Na beg you dey beg?? But you were so confident about this your 10K bet ohhh. If this boy waste my time, na annihilate i go annihilate am ohhhh.

Lol ...

Hot thread. Hmm.

You guys will need to pay the tithe of the 10k to me - as the master troll of this thread.

dhtml118:
You guys will need to pay the tithe of the 10k to me - as the master troll of this thread.

I dont mind. Do you have a *nix system that has GCC on it so you can build the interpreter?? We go need umpire because i no trust that boy..
You can find the glass interpreter here
http://codu.org/eso/glass/
I am using this one..
http://codu.org/eso/glass/glass-0.12.tar.bz2

Challenge ends 6am on Tuesday.

DanielTheGeek:
Challenge ends 6am on Tuesday.

Oga we need 1 week for this. The language is not the average language

Though am getting a hang of it. I need 7 days.
Have to finish stranger things before am in work mode....

seunthomas:

I dont mind. Do you have a *nix system that has GCC on it so you can build the interpreter?? We go need umpire because i no trust that boy..
You can find the glass interpreter here
http://codu.org/eso/glass/
I am using this one..
http://codu.org/eso/glass/glass-0.12.tar.bz2

May mac failed to compile it, i for on my kali linux, but no, i don tire, need to sleep - i had to use cutlass clear plenty grass today (lazy boy like me), na sleep i dey go sleep, will watch out for the winner.

I don mixup everything, tiredness don catch me.

dhtml118:

May mac failed to compile it, i for on my kali linux, but no, i don tire, need to sleep - i had to use cutlass clear plenty grass today (lazy boy like me), na sleep i dey go sleep, will watch out for the winner.

Your mac no dey developer compliant. Na one time my own cook am....
just run make
only...

The MAC no gree o, the thing taya me - na okrika mac im be. As e see the code like this, im shout - WAYO ALLAH - and refused to compile.

dhtml118:
The MAC no gree o, the thing taya me - na okrika mac im be. As e see the code like this, im shout - WAYO ALLAH - and refused to compile.

dont run make with any arguments.

seunthomas:

dont run make with any arguments.

When i tried that, i got this:

dhtml:glass tony$ make
make: Nothing to be done for `all'.
dhtml:glass tony$

seunthomas:

Oga we need 1 week for this. The language is not the average language

Though am getting a hang of it. I need 7 days.
Have to finish stranger things before am in work mode....

I'm sorry the challenge is fixed at three days, best I can do is to extend it to 8pm by Tuesday. I think it's feasible because if I were to take part I could attempt it within the time frame. The other brah has accepted the challenge and is prolly working already...

DanielTheGeek:


I'm sorry the challenge is fixed at three days, best I can do is to extend it to 8pm by Tuesday. I think it's feasible because if I were to take part I could attempt it within the time frame. The other brah has accepted the challenge and is prolly working already...

Mr man, i thought the challenge was for only me

*watching*

seunthomas:

Mr man, i thought the challenge was for only me

Will you also set the terms and conditions?

You may as well request it open for one year nah... 7 days is too much nah, who else agrees?

Let me reinstall gcc and try again:

dhtml:glass tony$ brew install gcc
==> Installing dependencies for gcc: gmp, mpfr, libmpc, isl
==> Installing gcc dependency: gmp
==> Downloading https://homebrew.bintray.com/bottles/gmp-6.1.2_1.sierra.bottle.tar.gz
==> Downloading from https://akamai.bintray.com/90/90715336080bd2deb92bd74361f50d91fe288d18e4c18a70a8253add6aa13200?__gda
######################################################################## 100.0%
==> Pouring gmp-6.1.2_1.sierra.bottle.tar.gz
� /usr/local/Cellar/gmp/6.1.2_1: 18 files, 3.1MB
==> Installing gcc dependency: mpfr
==> Downloading https://homebrew.bintray.com/bottles/mpfr-3.1.6.sierra.bottle.tar.gz
==> Downloading from https://akamai.bintray.com/a8/a8f99b5754688942fdb644a6c00f37d3c4311bcd4477f58b6dc356b0f32ee29d?__gda
######################################################################## 100.0%
==> Pouring mpfr-3.1.6.sierra.bottle.tar.gz
� /usr/local/Cellar/mpfr/3.1.6: 26 files, 3.6MB
==> Installing gcc dependency: libmpc
==> Downloading https://homebrew.bintray.com/bottles/libmpc-1.0.3_1.sierra.bottle.tar.gz
######################################################################## 100.0%
==> Pouring libmpc-1.0.3_1.sierra.bottle.tar.gz
� /usr/local/Cellar/libmpc/1.0.3_1: 12 files, 345.0KB
==> Installing gcc dependency: isl
==> Downloading https://homebrew.bintray.com/bottles/isl-0.18.sierra.bottle.tar.gz
==> Downloading from https://akamai.bintray.com/1c/1c2765a5766f8bc022dc49d77d7d32a9c3e92e82452bc63ab534f3c1f18a913c?__gda
######################################################################## 100.0%
==> Pouring isl-0.18.sierra.bottle.tar.gz
� /usr/local/Cellar/isl/0.18: 80 files, 3.8MB
==> Installing gcc
==> Downloading https://homebrew.bintray.com/bottles/gcc-7.2.0.sierra.bottle.tar.gz
==> Downloading from https://akamai.bintray.com/bc/bc96bddd0e9f7c074eab7c4036973bc60d5d5ef4489e65db64018363d63d248d?__gda
######################################################################## 100.0%
==> Pouring gcc-7.2.0.sierra.bottle.tar.gz
� /usr/local/Cellar/gcc/7.2.0: 1,487 files, 284MB

Someone is owing me 248MB of data o. Let me continue.

Omo, na same thing o, i taya.

g++ -O2 -g -c builtins.cc -o builtins.o
g++ -O2 -g -c func.cc -o func.o
g++ -O2 -g -c glass.cc -o glass.o
glass.cc:117:48: warning: comparison of unsigned expression < 0 is always false [-Wtautological-compare]
if (fread(input, 1, sbuf.st_size, fin) < 0) continue;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~
1 warning generated.
g++ -O2 -g -c klass.cc -o klass.o
g++ -O2 -g -c klassi.cc -o klassi.o
g++ -O2 -g -c parseq.cc -o parseq.o
g++ -O2 -g -c variable.cc -o variable.o
g++ -O2 -g builtins.o func.o glass.o klass.o klassi.o parseq.o variable.o -o glass

Oga Dhtml is participating.
Now this is dope.

@DanielTheGeek, I am not into this hullabaloo contest you guys are doing here, but I loved the question below... Cc: Cc: 4kings

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 probably don't have the requisite knowledge (or not smart enough, whichever one) to bring up mathematical tricks to quicken this up... But I used the basic maths skills to work out the problem.. And I wanted to try an online algorithm that spits out the cells as it walks through its process...

--------

Olyboy16:

**checked my post again to make sure i didnt type nonsense sir**

Nahh... You didn't type nonsense, I realized my thoughts were wrong about the question... I didn't mean to come off that way. Sorry about that.

---

Ok, so I took some time out today to look at this question because I found it interesting...

While tinkering on a possible solution, I realized one edge case we (perharps only myself) haven't clarified...
The edge case: what if the points lie on the same coordinate axis... for example...
Between two points A(x=0, y=0) and B(x=0, y=2).... Clearly when you draw this line, it doesn't technically cross any cell. In such cases, what should we do?

In my own solution, I assumed such doesn't cross any cell hence I return 0.
So, the story today goes- (remember, I expanded the problem to make my code identify the cells being crossed)...

At first I was tinkering along a possible solution that involves line intersections, wrt that line AB and the cell grids. While I was confident that was going to work, I quickly saw how much coding effort would be involved, so I ditched the idea. I mean, this problem looks simpler than this...

Secondly, I was thinking of the previous solution but with a Breadth First Search approach... I quickly saw that it was going to be an O(N^2) complexity, which just doesn't seem right for this problem... However, I noticed the complexity could be improved if we add a heuristic... Effectively making it a variant of an A* algorithm... That would involve too much work, so I ditched it again.... Do I even recall how to code A*?

Thirdly, I used drawing softwares to draw grids. then started making lines from one arbitrary point to another; while observing the behavior of the box occurence, I realized, I would have to sweep the plane... And I started...

Anyways... heres a solution in Python...

1. Check for corner cases such as the one raised above, if we are have a corner case, return early

def cellCount(A, B) :
	if A.x == B.x or A.y == B.y :
		return 0
        ....

2. We want to walk the grid from left to right, in order to do that, we must ensure that, based on the horizontal x-axis, A comes before B

        ...
	if A.x > B.x:
		A, B = B, A
        ...

3. Next, we must confirm that A.x is a positive number, if it's not, we rebase it to zero. and adjust B.x appropriately. If we don't do this, our left-to-right walking algorithm may at some point switch from a negative number to zero, then to a positive number; handling these scenarios is more work; rather add more code, its better we rebase our coordinates to ensure our left-to-right sweeping of the coordinate remains positive...

        ...
	if A.x < 0:
		B.x += -A.x
		A.x = 0
        ...

4. We calculate the slope... Secondary School stuff.

        ...
	slope = (A.y - B.y) / (A.x - B.x)
        ...

5. Steps 5, code first..

        ...
	count = 0
	x, y = A.x + 1, A.y
	while(x <= B.x):
		py = x * slope + A.y
		count += countBoundariesCrossed(y - py)
		y = int(py)
		x += 1
	return count

5 (a). The logic here is to follow the line AB with referenced on the x-axis, sweeping from left to right... in this case from 0, 1, 2, all up to the x-value of the second point.
5 (b). We then use the equation for straight lines to determine `y`, whenever we move x to the next cell using our good old, y = mx +c ... py = slope * x + Origin
5 (c). py will be the new position, of y when when x has been upped one step forward.... We need to know the lateral distance covered by the difference between y and py, and use this to count how many gridlines crossed by this delta....
5 (d). That job is done by countBoundariesCrossed.
5 (e). The gridlines crossed tells us how many cells we've passed; we increment our counter with this info
6. We are done...

Complexity: Armotized O(n). where n is the maximum distance between the two points on x-axis or y-axis. Armotized here because, the answer may be larger than N, but definitely in the realm of O(kN), where k is a number greater than zero, but significantly less than N

The full code is here below:

class Point:
	def __init__(self, x, y) :
		self.x = x
		self.y = y
	def __str__(self):
		return "Point(x={0}, y={1}) ".format(self.x, self.y)
	def __repr__(self) :
		return self.__str__()
		
def countBoundariesCrossed(n) :
	n = float(abs(n))
	count = 0
	while n > 0.0 :
		n -= 1
		count += 1
	return count
	
#A and B are Point objects
def cellCount(A, B) :
	if A.x == B.x or A.y == B.y:
		return 0
	if A.x > B.x :
		A, B = B, A
	if A.x < 0:
		B.x += -A.x
		A.x = 0
	slope = (A.y - B.y) / (A.x - B.x)
	count = 0
	x, y = A.x + 1, A.y
	while(x <= B.x) :
		py = x * slope + A.y
		count += countBoundariesCrossed(y - py)
		y = int(py)
		x += 1
	return count
	
print(cellCount(Point(4,3), Point(342,-2352)))

---

NOTES:
- I really enjoyed this problem... after solving it... I decided to search the internet for its application, and I came across [url=https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm]Bresenham's line algorithm[/url] used to approximate straight lines in Bitmap images....

- A quick glance at Bresenham's line algorithm shows it achieves its work in O(N) time, which I find really cool! Mine does same!
- There may be a bug lurking somewhere, while I doubt it, I am opened to learning from failure cases of my algorithm.
- before posting this, I decided to go through the whole nonsense on this thread and I am only just realizing there is an amortized O(1) algorithm for counting the cells... And hell no, there was no way I was close to thinking that GCD direction... So, I am definitely not the smartest here.
- Once again, I enjoyed the problem, thanks for posting.

Another thing that makes me feel good is that, with only two changes to the code, the above solution can work for rectangular grids...

DanielTheGeek:


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, a layman shoul be able to deduce from the little things we know that we can come up with a formula;

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

Good to know about the GCD thing! ... However your explanation just doesn't cut it for me... especially where you wrote

So therefore, a layman shoul be able to deduce from the little things we know that we can come up with a formula

I am not (yet) a PhD holder in a Mathematics heavy field, however, I am not a layman in basic mathematics, yet I didn't deduce it... I think you should rethink your assertions, or one down a bit on it. However, I found this to be more helpful. Nonetheless, thanks for posting, I first knew about this armotized solution from your post, quoted above... Thanks...

-------

Ummm, quick question...
While I know the question assumes square grids, does the GCD solution work for rectangular grids? Or what tweak can we do to make it work for rectangular grids...?

can i enter this contest too?

4kings:
Oga Dhtml is participating.
Now this is dope.

I am not participating o, i am only an umpire here.

okwyee:
can i enter this contest too?

Its not a contest but a challenge. Its for me alone.

My eyes don dey gum, i don sleep be that.