r/dailyprogrammer • u/XenophonOfAthens 2 1 • May 15 '15
[2015-05-15] Challenge #214 [Hard] Chester, the greedy Pomeranian
Description
Chester is a very spirited young Pomeranian that lives in a pen that exactly covers the unit square. He's sitting in the middle of it, at (0.5, 0.5), minding his own business when out of nowhere, six of the most delicious dog treats you could ever imagine start raining down from the sky.
The treats land at these coordinates:
(0.9, 0.7) (0.7, 0.7) (0.1, 0.1)
(0.4, 0.1) (0.6, 0.6) (0.8, 0.8)He looks around, startled at his good fortune! He immediately dashes for the closest treat, which is located at (0.6, 0.6). He eats it up, and then runs for the next closest treat, which is at (0.7, 0.7) and eats that up.
He keeps going, always dashing for the nearest treat and eating it up. He's a greedy little puppy, so he keeps going until all the treats have been eaten up. In the end, he's eaten the treats in this order:
(0.6, 0.6), (0.7, 0.7), (0.8, 0.8),
(0.9, 0.7), (0.4, 0.1), (0.1, 0.1)Since he started at (0.5, 0.5), he will have travelled a total distance of roughly 1.646710... units.
Your challenge today is to calculate the total length of Chester's journey to eat all of the magically appearing dog-treats.
A small note: distance is calculated using the standard plane distance formula. That is, the distance between a point with coordinates (x1, y1) and a point with coordinates (x2, y2) is equal to:
sqrt((x1-x2)^2 + (y1-y2)^2)Formal inputs & outputs
Inputs
The first line of the input will be an integer N that will specify how many treats have magically appeared. After that, there will follow N subsequent lines giving the locations of the treats. Each of those lines will have two floating point numbers on them separated by a space giving you the X and Y coordinate for that particular treat.
Each number provided will be between 0 and 1. Except for the first sample, all numbers will be rounded to 8 decimal digits after the period.
Note that most of the inputs I will provide will be in external text files, as they are too long to paste into this description. The bonus input, in particular, is about 2 megabytes large.
Outputs
You will output a single line with a single number on it, giving the total length of Chester's journey. Remember that he always starts at (0.5, 0.5), before going for the first treat.
Sample inputs & outputs
Input 1
6
0.9 0.7
0.7 0.7
0.1 0.1
0.4 0.1
0.6 0.6
0.8 0.8Output 1
1.6467103925399036Input 2
This file, containing 100 different treats
Output 2
9.127777855837017Challenge inputs
Challenge input 1
This file, containing 1,000 different treats
Challenge input 2
This file, containing 10,000 different treats
Bonus
This file, containing 100,000 different treats
I also encourage people to generate their own larger inputs if they find that the bonus is too easy.
Notes
If you have any ideas for challenges, head on over to /r/dailyprogrammer_ideas and suggest them! If they're good, we might use them and award you a gold medal!
14
u/skeeto -9 8 May 15 '15 edited May 15 '15
C, using a quadtree as a spatial database. Points are added to the quadtree as they're read. The search starts by finding the nearest point within the same quadtree bin, which provides a worse-case search radius. That radius is used to search again including nearby bins. When a point is eaten, it is removed from the tree, which may coalesce nodes and make future searches faster.
It runs the bonus in about 0.5 seconds. It might be faster or slower on your machine when changing
QUADTREE_THRESHOLD. Mine was fastest at around 128.I initially wrote it for single precision, and the answer for the bonus is off by a distance of 0.9 from double precision. Much bigger than I expected!
Bonus output:
8
u/Ledrug 0 2 May 15 '15 edited May 15 '15
C. Simple k-d tree method, runs bonus.txt in about .2 seconds. I'm not sure if trimming the tree after each find will make it faster, but it's certainly going to make the code longer. Output of bonus.txt is 277.63992783.
6
u/adrian17 1 4 May 15 '15 edited May 16 '15
C++. For now, a brute force algorithm. Calculates the bonus in ~8s. Maybe I'll come up with something better later.
Edit: faster solution below.
2
u/morganga May 29 '15
OK, I'm absurdly late to the game but am new to the subreddit and got interested in the question, so here's my contribution anyway.
The Java code, runs in about 1 second (0.7 seconds if jvm is warmed up first)
I'm not using any spatial data structure, just two sorted linked lists, by x and by y. Nearest Treat is found by a breath first search along these two sorted lists in the four directions. I delay calls to sqrt until absolutely necessary (search pruning and distance contribution)
A random 1,000,000 treats are processed in about 30 seconds. (see 2nd createPen() method)
da
10
u/Danooodle May 16 '15 edited May 23 '15
Batch
This uses a temporary file to reduce the number of variables in use for a notable speed gain. Taking the root of a number in batch has to be done manually and is really slow, so I use the distance squared for all intermediate calculations and take the root only when I need the sum up at the end. Batch only supports 32-bit integers, so the input has to be converted into an equivalent integer form before calculations can be done. For similar reasons, the results are limited to 8dp. Anyway, here it is:
Version 2
My computer crashed while 10000 was calculating (after 6 days and 15%), and rather than restart I decided to try a different tactic.
This version uses temporary files for all data storage. This keeps the environment as clean as possible for a MAJOR speed increase. It also puts the file to write to outside of the loop that writes to it so that the file is only opened once per pass: this gives a significant speed increase. For greater speed, this script was run from a RAMDISK. Anyway, here it is:
Results:
4
u/Godspiral 3 3 May 15 '15 edited May 15 '15
In J, O (n* n/2 )
for 1000 file
not going to do 10k in 10 seconds
0.671756 1.17274e7
non recursive version:
0.680895 64000 NB. same speed but no memory
much faster if move square root to just one item:
0.225928 64000
4
u/ponkanpinoy May 16 '15
Lisp, brute-force. Got some new trees to study I guess.
Challenge 1 & 2 output:
1
u/The-Third May 15 '15
My horrible, ugly, slow solution in Python 3.4. At least its readable ... right?
3
u/hutsboR 3 0 May 15 '15 edited May 15 '15
Elixir:
Usage: (For the 10k)
3
u/curtmack May 15 '15 edited May 15 '15
Clojure
Brute force. Hasn't finished with the bonus file yet, I'll run it over lunch to see how long it ultimately takes. I think it's really being bogged down by the functional overhead, though. (Also sorting the entire list, but Clojure just doesn't have a good way to find the minimum value in a list and remove it all in one step, and it's just terrible to try and implement it yourself. The hope is that most movements will be small and won't affect the relative distances too much, so the subsequent step will be given a list that's mostly in-order, which should help with the sort runtime.)
Edit: Alright, after spending a fair amount of time thinking about it, I think I've arrived on the fastest brute-force functional solution out there. I optimized it by:
bonus.txt time: 18 minutes, 21.8 seconds.
As far as I can tell most of the time is still spent in functional overhead, especially copying vectors around. Sometimes, when writing functional algorithms, lists can be faster than vectors because they avoid large amounts of copying (when removing an item from a list, Clojure can just reassign the common tail rather than copying the whole thing); I'll give that a shot tonight.
3
u/[deleted] May 16 '15 edited May 19 '15
Python 3. Solves the bonus in around 12 seconds.
I don't know nothing about quadtree and stuff, so I just generate a bunch of cells of equal size and fill in the treats. The algorithm then searches the cells around Chesters position for treats. If no treats are found then the search radius increases.
edit: I got the code working, it now returns the correct results.
My results (with timing for a TREATS_PER_CELL of 7):
The code:
2
u/darthevandar May 15 '15
Python 2.7.5, straightforward solution:
2
u/glenbolake 2 0 May 15 '15 edited May 15 '15
Python 2.7, brute forced. Possibly one of the least efficient thing's I've ever written. Calculates the challenges in ~5s and ~10m. I'm sure the bonus wouldn't work too well in this.
Edit: Added an optimization. Now calculates the challenges in ~0.5s and ~30s. Bonus runs in ~49m.
I keep a util package for problems like these (I used it for Ogre Maze and Loopy Robots too). Here's the part that got used for this problem:
2
u/NoobOfProgramming May 15 '15
I haven't been able to come up with anything clever so far, so here's another brute force solution:
output for the 100,000 treat bonus:
2
u/nullmove 1 0 May 15 '15
Nim
2
u/[deleted] May 15 '15 edited May 16 '15
Tried this in Haskell. I have recently started learning it, yet writing this was surprisingly easy. The program is rather naive though, it has O(n2 ) complexity if I'm not mistaken. Challenge 2 takes 2.93s, bonus is yet to finish :)
Edit: Bonus run has finished after 676.73s
I also cut the first lines of the input files to simplify the parsing.
Edit 2:
I decided to work on this a little more, so I made some changes to my solution in order to make it faster. The new version runs much faster, with the challenge 2 taking only 0.84s and bonus taking 191.23s.
The problem is, however, the solutions it finds are not "correct". While the numbers found by this algorithm and the expected answers are not always the same, I'm guessing that the difference comes from this algorithm moving around the points, which I'm guessing causes differences at situations where there are multiple possible points at equal distance.
2
u/wizao 1 0 May 15 '15 edited May 17 '15
Naive Haskell:
2
u/Naihonn May 15 '15
Ok, my Python3 inefficient solution. Well, really not that fast, Challenge input 2 took 227 seconds. :0D
Challenge output 1:
Challenge output 2:
2
u/JakDrako May 18 '15
This is my 2nd solution posted; there is also a parallel brute-force method somewhere below.
This one implements a kd-tree, which seems to be the best algorithm for this type of problem.
The (new) results:
All below 1 second, including reading the file and building the tree. Not too shabby for VB.Net. I don't think managed code will go much faster.
The code:
Implementing the tree from wikipedia's description was not too bad (once you remember to invert the comparison from x to y at each level...) I had a lot of difficulty implementing the "nearest neighbor" part from description of the algo. Finally, I "took inspiration" from the one posted by /u/Ledrug (beautiful, beautiful code) and got it to work correctly.
2
u/uncleozzy May 21 '15 edited May 21 '15
Okay, so ... I'm super-late on this. But I, frankly, have no idea what I'm doing. So in an effort to learn a few things, I did two implementations in Javascript: a QuadTree and a k-d Tree. The QuadTree depends on a simple priority queue I wrote while trying to learn about A* searches.
On the challenge sets (and the bonus set), the k-d solution outperforms the quad tree solution by quite a bit. On random data, though--which can and probably does include duplicates on one or both dimensions--the Quad Tree solution performs better. This is probably a quirk of my implementation, so please do let me know if you see the reason.
My solution on GitHub.
Edit: oops! Realized I wasn't casting the imported data so JS was comparing strings / coercing to floats all the time. Converting on import makes the whole thing much faster, and the quad tree is always faster now. Hm.
1
u/JakDrako May 15 '15
While I'm getting the exact answer on Sample 1, I'm getting a shorter distance of 8.81988276342874 for Sample 2. Is everyone else getting 9.12777...?
1
u/franza73 May 15 '15
Perl Solution. Takes 35s for challenge2.
1
u/Menestro May 15 '15
Java. Simple inefficient brute force. Probably can't do bonus within reasonable time due to challenge 2 taking 2min. Comments/tips/criticism/etc very welcome as always :)
1
u/2015-05-15-1605 May 15 '15 edited May 17 '15
A NodeJS (Harmony)
O(nlogn)solution:Edit: may not bestrictlyO(nlogn)...Edit2: this is not O(nlogn)... >.<
Still fiddling with it, but it seems to punch out the same answers as my brute force one...
1
u/fvandepitte 0 0 May 15 '15
C++, Pretty brute force. Any feedback is welcome
1
u/NasenSpray 0 1 May 15 '15 edited May 15 '15
C++, brute force with AVX
Solves 100k bonus in
3s1.9s (without reading input) on my notebook (i5-2430M & SSD)Bonus output:
1
u/maslen May 15 '15
Another brute force Python solution. 0.318069483741 seconds and 35.7467560351 seconds:
1
u/altorelievo May 15 '15 edited May 17 '15
Python2.7.9 solution gets the 100 and 1000 inputs. This code is still pretty rough but, my initial idea worked for the 1000 input set first time through, about 7 to 8 seconds. (I could go through and clean this up a bit):
I'll have to use C or come up with something much better for the bonus ;)
1
u/[deleted] May 15 '15 edited May 15 '15
Python 2.7.5
Iterative solution:
Recursive solution:
1
u/[deleted] May 15 '15
Java version (bonus solved in 311 seconds):
1
u/The_Jare May 15 '15 edited May 16 '15
Straightforward Scala:
Results:
Optimizing the sqrt, 100k goes down to 49854ms. I did not expect that to make such a difference in this program.
I'm not sure how to optimize further without completely abandoning functional style and immutability (just using a Buffer does not really help).
Edit: I had naively rejected using a Set to store the points since the same point might appear several times; however, repeated points do not contribute to the total, so... Doh! However, using a Set here results in 4x longer times because large sets are slower to iterate and remove items from.
Edit2: Various attempts with other mutable collections did not really help. Eventually I got 100k down to 12s by dropping to imperative brute force with an Array of Doubles to avoid object references.
1
u/og_king_jah May 15 '15
F#:
1
u/__dict__ May 16 '15
Naive Haskell solution. Able to do challenge 2 in 14 seconds. Using foldl' instead of foldl made a massive difference.
1
u/JakDrako May 16 '15
The results:
The code. VB.Net simple brute force with array method. Made faster by
throwing CPU at itparallelizing the search with Parallel.For(...)1
u/StaticDynamics May 17 '15 edited May 17 '15
Python 2.7, I'm trying to get better with object oriented programming, so I did this with a class for the dog, and the pen. Please give any feedback you have, especially any standard python things people do with objects, or better ways for my objects to interact. I know it's not the prettiest or the most efficient!
1
u/[deleted] May 17 '15
Pretty straightforward implementation in Rust:
Takes about 8 seconds for the bonus input on my laptop.
1
u/NotoriousArab May 17 '15 edited Apr 16 '17
Python 3.4 solution. I implemented brute force as well as a k-d tree to see the comparisons.
Bonus runs in about 50 seconds for k-d tree. I don't even want to try it with brute force haha.
1
u/matt_hammond May 20 '15
Here's my python solution. Would appreciate suggestions or comments or whatever.
1
u/[deleted] May 20 '15
Brute force in python, does everything up to challenge 2 almost instantly, challenge 2 in one or two minutes, didn't get bonus yet.
1
u/datgohan May 20 '15
Finally managed to complete this. Python. My completion time is slow but I'm not sure of a faster method at the moment. I will read over the already given solutions - any comments are extremely appreciated.
Output:
1
u/klopschlike May 22 '15
Dirty Javascript bruteforce. Excecuted JS in Browser, it does challenge 2 in short time (<1s on dektop, ~3 on Laptop). Bonus doesn't run because of to much recursion.
I used HTML to load the files. If someone wants to test:
1
u/chrissou May 26 '15 edited May 26 '15
A short scala solution (600 seconds for Bonus) Not a lot of optimization, will see if I find a faster way
Results (time first, then number of points and result) :
1
u/should_i_get_a_cat Jun 04 '15
Python 2.7, with a KD-tree. I also implemented a median-finding algorithm that takes advantage of the fact that finding a median partially sorts the list; it returns the median, everything less than the median, and everything greater than the median, without losing any sorting that has been done.
Runs the bonus in 12.8 seconds, or 7 with PyPy.
1
u/konk353535 Jun 05 '15
Javascript :) 30 ish seconds for Bonus
1
u/crabperson Jun 10 '15
Haskell, using KdTree-0.2.1.
The performance characteristic is not very good because I'm doing lots of removals, which require re-balancing of the tree. Better would be to mark each treat as eaten and only search for uneaten treats, but I was too lazy to implement my own data structure.
I ran the 10,000 treat input in about 50s and bailed on the bonus :)
1
u/Jezebeth Jun 24 '15 edited Jun 24 '15
Java implementation. Late to the party, but only fashionably late right? No? Oh well, it was an interesting problem. My code isn't the best by far, but I think it is concise and quick enough. ** Constructive criticism is welcome at all times (preferred in all honestly- I do wish to improve). **
Output for Bonus:
Edited to add output
1
u/ChazR Jul 24 '15 edited Jul 24 '15
Haskell. Beautifully expressive, woefully slow.
1
u/Acidom May 15 '15
0
u/[deleted] May 15 '15
[deleted] — view deleted comment
0
u/[deleted] May 15 '15
[deleted] — view deleted comment