Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / NewStats: 3,195,076 members, 7,957,009 topics. Date: Tuesday, 24 September 2024 at 03:52 AM |
Nairaland Forum / Science/Technology / Programming / Challenge Me (16683 Views)
(1) (2) (3) ... (5) (6) (7) (8) (9) (10) (Reply) (Go Down)
Re: Challenge Me by Nobody: 8:46pm On Oct 28, 2017 |
Santa maria! egba mi o! 10k!! |
Re: Challenge Me by seunthomas: 8:47pm On Oct 28, 2017 |
dhtml118:Una i go chop dat boy money. |
Re: Challenge Me by Nobody: 8:49pm On Oct 28, 2017 |
seunthomas: 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... |
Re: Challenge Me by seunthomas: 8:51pm On Oct 28, 2017 |
DanielTheGeek: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. |
Re: Challenge Me by Nobody: 8:52pm On Oct 28, 2017 |
seunthomas: Maybe 4Kings may eat it before you even though you have a big mouth... |
Re: Challenge Me by seunthomas: 8:54pm On Oct 28, 2017 |
DanielTheGeek:See this man. I don dey learn the syntax already.... |
Re: Challenge Me by Nobody: 8:59pm On Oct 28, 2017 |
seunthomas: Lol ... |
Re: Challenge Me by bolkay47(m): 8:59pm On Oct 28, 2017 |
Hot thread. Hmm. |
Re: Challenge Me by Nobody: 9:00pm On Oct 28, 2017 |
You guys will need to pay the tithe of the 10k to me - as the master troll of this thread. |
Re: Challenge Me by seunthomas: 9:08pm On Oct 28, 2017 |
dhtml118: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 |
Re: Challenge Me by Nobody: 9:13pm On Oct 28, 2017 |
Challenge ends 6am on Tuesday. |
Re: Challenge Me by seunthomas: 9:15pm On Oct 28, 2017 |
DanielTheGeek: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.... |
Re: Challenge Me by Nobody: 9:15pm On Oct 28, 2017 |
seunthomas: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. |
Re: Challenge Me by seunthomas: 9:17pm On Oct 28, 2017 |
dhtml118:Your mac no dey developer compliant. Na one time my own cook am.... just run make only... |
Re: Challenge Me by Nobody: 9:19pm On Oct 28, 2017 |
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. 1 Like |
Re: Challenge Me by seunthomas: 9:19pm On Oct 28, 2017 |
dhtml118:dont run make with any arguments. |
Re: Challenge Me by Nobody: 9:21pm On Oct 28, 2017 |
seunthomas: When i tried that, i got this: dhtml:glass tony$ make make: Nothing to be done for `all'. dhtml:glass tony$ |
Re: Challenge Me by Nobody: 9:22pm On Oct 28, 2017 |
seunthomas: 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... |
Re: Challenge Me by seunthomas: 9:25pm On Oct 28, 2017 |
DanielTheGeek:Mr man, i thought the challenge was for only me |
Re: Challenge Me by Nobody: 9:26pm On Oct 28, 2017 |
*watching* |
Re: Challenge Me by Nobody: 9:29pm On Oct 28, 2017 |
seunthomas: Will you also set the terms and conditions? |
Re: Challenge Me by Nobody: 9:30pm On Oct 28, 2017 |
You may as well request it open for one year nah... 7 days is too much nah, who else agrees? |
Re: Challenge Me by Nobody: 9:45pm On Oct 28, 2017 |
Let me reinstall gcc and try again:
Someone is owing me 248MB of data o. Let me continue. |
Re: Challenge Me by Nobody: 9:49pm On Oct 28, 2017 |
Omo, na same thing o, i taya. |
Re: Challenge Me by seunthomas: 9:57pm On Oct 28, 2017 |
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 |
Re: Challenge Me by 4kings: 10:01pm On Oct 28, 2017 |
Oga Dhtml is participating. Now this is dope. |
Re: Challenge Me by WhiZTiM(m): 10:02pm On Oct 28, 2017 |
@DanielTheGeek, I am not into this hullabaloo contest you guys are doing here, but I loved the question below... Cc: Cc: 4kings DanielTheGeek: 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: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
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
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...
4. We calculate the slope... Secondary School stuff.
5. Steps 5, code first..
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:
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... 3 Likes
|
Re: Challenge Me by WhiZTiM(m): 10:05pm On Oct 28, 2017 |
DanielTheGeek: 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...? 1 Like |
Re: Challenge Me by okwyee(m): 10:05pm On Oct 28, 2017 |
can i enter this contest too? |
Re: Challenge Me by Nobody: 10:15pm On Oct 28, 2017 |
4kings:I am not participating o, i am only an umpire here. |
Re: Challenge Me by seunthomas: 10:19pm On Oct 28, 2017 |
okwyee:Its not a contest but a challenge. Its for me alone. |
Re: Challenge Me by Nobody: 10:20pm On Oct 28, 2017 |
My eyes don dey gum, i don sleep be that. |
(1) (2) (3) ... (5) (6) (7) (8) (9) (10) (Reply)
How Can I Make Payment For Any Udemy Course With My Credit Card? / The Importance Of Software Testing And Not Just Software Programming / Learn How To Build A Desktop Software Using PYTHON – Tutorial On Nairaland
(Go Up)
Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health religion celebs tv-movies music-radio literature webmasters programming techmarket Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 56 |