popiel / icfp-2012 Goto Github PK

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