-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME
198 lines (145 loc) · 7.59 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
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