January 29th 2011
UWCS Progcomp Chain 6, Results
As a continuation of bucko’s progcomp chain, I set Progcomp 6.
The objective was to walk your way through a “maze” with huge constraints to make the problem simpler.
I believed the simplest solution to the problem was graph search with backtracking. My inefficient implementation (with debugging) of this is unbelievably fast; it can solve a 300×5000 map (>100 times the size of the original problem) in around 2 seconds. The map generator ensures there are no problems set with trivial solutions (i.e. going in a straight line all the way down the map). I thought that the effort of solving it by hand within the (6-second) time constraint would require far too much UI work, so keeping the problem size small enough to fit on the screen was fine.
I was wrong. So wrong.
bucko’s Perl solution was first, after 15 minutes, with a tree search implementation. While easier to implement, this is much slower.
I’d carefully designed the page, submission process and timeout so that people who found curl / wget too much effort could submit the solution by copy-pasting; I could copy the result from the page (without the IE-only JS’ assistance) into my solver, solve it, and copy the result back in ~5 seconds; hence the 6-second timeout. bucko’s solution sometimes doesn’t finish in time, even on these tiny maps. It’ll never finish on the huge map.
fice was second, after 21 minutes. Algorithm / code unknown, although I’m guessing there was auto-submission as no User-Agent was set.
Queex (outsider!) was third, after about 50 minutes, with his Java solution. He decided the problem wasn’t complicated enough to write a “proper” solution for, and went for just trying to jiggle away from the edges. Obviously it works fine, and I have no idea how to harden the map generator against it, except perhaps forcing you to go from the left edge to the right edge at least once. It can only solve some of the maps, but this isn’t important as it was a “solve once” problem.
Next up was Afal’s js solution. He (correctly) guessed that the map generator only generates large walls every 10 spaces, worked out which side it was, and jiggled away from it a bit. Apparently works most of the time. Again he uses an in-browser implementation to avoid having to do any page parsing or post rubbish.
Afal then decided to submit 62,000 other solutions, which has made my log huge and writing this a pain. Such a penis. Such a penis.
At this point an hour had passed and I turned the debugger on; when you die it tells you where and shows you what you submitted, etc.
james was next, with some more jiggling Java, and a shell-script wrapper.
MrWilson then submitted a travesty. It generates random solutions and assumes loads of things about the map. It works in nearly no cases. I don’t know how he can show his face in public after this.
Connorhd duplicated bucko’s solution in php.
sadiq, tom, Softly, Trencha and Steve Brandwood also had a correct answer.
Meta: I wrote my own solutions website instead of using bucko’s. I got the logging all wrong. I got the map size all wrong (not realising how lazy everyone is).
It took me about 90 minutes to do the map generator and my solution with debugger, and verifier. Another 90 minutes was spent on the website. That is, a ~3 hour time investment for causing hours of suffering and an entire night of entertainment. Totally worth it.
Next up is bucko’s progcomp chain, link 7, but tom still owes us a progcomp.
