3 ms·
"Your solution is very good, but I do not believe it to be optimal. I am working on a better one." Very well sirrah, I shall consider myself slapped in the fac
by Stormbringer 16y ago
"Your solution is very good, but I do not believe it to be optimal. I am working on a better one."
Very well sirrah, I shall consider myself slapped in the face with the object with five extrusions that is topologically identical to a plane. Your challenge is accepted. :D Duelling algorithms at dawn it is. I keenly await your opening salvo.
- patio11 16y agoCoded both our algorithms. I win by a nose (more visible at larger building sizes -- 1k floors, etc.) Code quality is an abomination, please excuse exploratory programming: http://dl.dropbox.com/u/751473/hn.rb http://dl.dropbox.com/u/751473/hn.rb Gist of my approach: dynamically recalculate number of steps to go with each jump we take, using the same approach that you do (find smallest k such that k(k + 1) / 2 > n), rather than assuming it decreases monotonically. This has superior performance around some boundary conditions. Instructions for running script: ruby hn.rb patio11 debug 100 ruby hn.rb stormy debug 100 Debug on or off as desired, 100 is size of building. Then, leave off debug flags, and diff the outputs.
- lurker19 16y agoDo you mean "incrementally by 1 each iteration" where you wrote "monotontically", in your reference to Stormbringer's algorithm? Mathematically, I do not see how any solution could beat Stormbringer's, by considering the cases where tolerance = k+0.5 and tolerance = ((kk +k)/2+0.5, which shows that the set of tolerances for a building of height > (kk+k)/2 requires >= k+1 drops to validate. But I have not been quite formal in my analysis. (Argh, asterisks!)
- deleted 16y ago[deleted]