Join GitHub today
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
This is the ICFP 2012 entry for Invisible Imp, a.k.a. T. Alexander Popiel. I am working as a team of only one person, both to reduce communication overhead and because I cannot find anybody local with the same dedication to the contest that I have. This is the first year that I'm doing the contest in what is arguably a functional languange; this year, I'm using Scala. Huzzah! My work for previous years has been in Java, C, and Perl. Random notes: * I'm using maven, just because I'm using it at work, and it's a convenient way to make sure that all the dependent jars I feel like pulling in actually end up in my submission image. To compile from source and run unit tests, 'mvn scala:run'. * All map coordinates are one-dimensional for me. This is a trick I learned long, long ago; by just maying out the map in row-major order in a single array, symmetry between the different directions is exposed. Add in an extra border wall (which was implied in the spec anyway), and you also eliminate all need for boundary checking. * I ended up revisiting my storage layer something like 4 times. If you want to see the history, I can make my git repository public. * The very first significant decision I made was to do map updates in place, to save on memory consumption and memory copies. This does mean that for backtracking, I'm going to have to replay move sequences... but I suspect that will be less expensive in the long run than tons of memory copies. Of course, I later ended up partially recanting on this, and now have a map structure involving the original map and then patches layered on top of that. With this incremental approach, backtracking is instantaneous, but I do run out of stack space on the long paths. I was contemplating yet another rewrite of this, so that I did actually change the original map, but kept a better-formed log of update tuples (position, from, to) for rapid reconstruction... but no energy for that. * The second significant decision was to express map update in terms of the destination cells instead of the source cells. In the process, I introduced a new cell state for "a rock _was_ here just a moment ago", but eliminated the need for a prior image of the map. I have a second pass during update to clean up the dust of moving rocks. Again, this was revisited and the extra state was removed, when I could easily look at multiple versions of the map without a hefty memory cost. * My main algorithm is A* search from point to point, with a floodfill gradient ignoring rocks and other movable objects to act as my cost underestimate. I had intended to later play games with reordering the goals in an optimization phase (and have a fair amount of experience with that from long ago... the ideal mutator seems to be picking a random subsequence and either repositioning it or reversing it), but the spec updates were too numerous for me to ever get to it. Fri Jul 13 06:30:00 PDT 2012 This is about when I started. Fri Jul 13 14:00:00 PDT 2012 This is about when I paused for lunch and a bit of TV. Fri Jul 13 15:30:00 PDT 2012 About when I resumed to start the major refactor of State construction Fri Jul 13 17:39:45 PDT 2012 Pausing to lie down for a bit. Refactor complete, works as a scoring machine Fri Jul 13 18:58:05 PDT 2012 Back. Going to write some unit tests, of all things. Fri Jul 13 19:14:10 PDT 2012 Just had a 5 second or so power outage. Thundering outside. This may be a problem. Thank goodness for UPSes. Fri Jul 13 20:44:37 PDT 2012 From chat: (8:02:21 PM) ems_: mietek: my reading is that if the robot leaves the water, but the rising water covers the robot again in the map update, then this does not reset the waterproofing. However, I haven't tested against the validator. (8:03:00 PM) Patcdr: I have tested it, and the counter is reset I'm going to have to fix that... my code currently works like mietak expected. Fri Jul 13 20:45:29 PDT 2012 My ramp-making code seems to be in place, will help with path-finding. Fri Jul 13 20:58:42 PDT 2012 Going to feed the cats and take another break. Sat Jul 14 06:22:00 PDT 2012 Eating breakfast, reading icfp mail. Have ideas about undo and memory usage. Sat Jul 14 06:53:35 PDT 2012 Done putting Melissa to bed. Resuming coding. Sat Jul 14 09:07:20 PDT 2012 Woohoo! Undo works. Sat Jul 14 10:45:32 PDT 2012 Pathing is getting there, but throwing stack overflows in findPath Sat Jul 14 11:02:05 PDT 2012 Pathing is still throwing stack overflow, but I just got a vision on how to rework state management to get rid of the side effects, and without consuming millions of megabytes for large maps. Need to think about how to best handle this. Is the rewrite worth it? Sat Jul 14 12:51:43 PDT 2012 Rewrite mostly done. Pausing to feed cats and eat lunch. Sat Jul 14 13:21:55 PDT 2012 Resuming work on rewrite. Sat Jul 14 14:33:32 PDT 2012 Immutable state seems to work. Sat Jul 14 15:25:28 PDT 2012 (3:16:30 PM) invisibleimp: When you step onto a razor, _how many_ additional applications become available? (3:16:41 PM) slindley: just one (3:16:57 PM) pyjar: is there a maximum number you can carry? (3:17:03 PM) slindley: no Sat Jul 14 16:33:07 PDT 2012 Fixed a bunch of stupid glitches in the simulation. Sat Jul 14 16:48:57 PDT 2012 Prepping for first submission. Sat Jul 14 17:13:19 PDT 2012 Submission complete. That was painful. Hint: don't include the lib dir, and use Chrome. Sat Jul 14 19:37:01 PDT 2012 Refactor of priority queue almost complete. Dinner time. Sat Jul 14 22:18:24 PDT 2012 Back from dinner. Time to see if I can get the queue refactor working. Sat Jul 14 22:44:45 PDT 2012 Queue refactor seems to be working. Sat Jul 14 23:02:16 PDT 2012 More tweaks to priority, goals. Sun Jul 15 08:33:32 PDT 2012 It's morning. have read email, see that the final amendment has been announced. I'll be fetching it in a moment. Priorities for today: 1. Fix approach to lift, so we properly solve map 1. 2. Fix mine representation (again), to eliminate stack overflows with long paths. 3. Update rules to support trampolines, beards, and whatever the final mess is. Sun Jul 15 09:21:25 PDT 2012 Fixed ramp, still not getting to lift. Sun Jul 15 09:49:14 PDT 2012 submission: MD5(../icfp-95267072.tgz)= 9ed28ed4033f5979c3110f01a429c2c7 Sun Jul 15 10:00:54 PDT 2012 Added the rest of the sample maps Sun Jul 15 11:17:31 PDT 2012 Can read all maps, at least. Sun Jul 15 12:26:25 PDT 2012 Fixed water counting; had an off-by-one on the water level. Sun Jul 15 12:32:26 PDT 2012 submission: MD5(../icfp-95267072.tgz)= 0a2bef64fa7d82521ee71ad4570ef9e0 Sun Jul 15 13:01:37 PDT 2012 Taking a break before implementing more additions. Sun Jul 15 13:43:11 PDT 2012 Returning to the underwater beard-shaving competition. Sun Jul 15 18:16:24 PDT 2012 submission: MD5(../icfp-95267072.tgz)= 123df9b81949d6f6a3a4a35785b73840 Sun Jul 15 18:26:55 PDT 2012 Just about ready to give up. Too tired to do much more. Sun Jul 15 20:42:20 PDT 2012 OK, have written up a bit more notes at the top of the file. In the process, got a bit more energy to continue, and managed to improve my horocks solution (now it'll pick up horocks that it happens to break open by accident) Sun Jul 15 20:48:12 PDT 2012 submission: MD5(../icfp-95267072.tgz)= afbce0f2a005426b02490950f01af41a Sun Jul 15 21:03:15 PDT 2012 Just realized how to avoid the stack overflow on long paths, and I feel dumb. Just use the immutable maps as they were meant to be used, instead of stringing quite so many together with defaulting. Only about a 5 line change. Sun Jul 15 21:09:44 PDT 2012 submission: MD5(../icfp-95267072.tgz)= 98e4a846ddcc4684c3e1089e6d7ad2fb