https://adventofcode.com/2021/day/23
For day 23, we needed to solve a lazy shrimp problem.
We had a room and hallway setup (view in monospace font):
sample=:];._2 {{)n
#############
#...........#
###B#C#B#D###
#A#D#C#A#
#########
}}
Ignore spaces and '#' (wall) characters. The important locations are
marked with . or letters ABCD.
Actually, also we partially ignore the '.' characters which align
vertically here with a letter -- those locations are significant but
must always be left open.
The horizontal section of dots was the 'hallway' and the sections
initially containing letters were 'rooms'.
The task involved moving each of the letters (the shrimp) into the
rooms so that the shrimp would be arranged in alphabetical order, left
to right with these constraints (stated slightly differently in the
puzzle):
(1) Each shrimp could only move twice
(2) each move must change the shrimp's horizontal position
(3) no shrimp could pass through another shrimp
(4) shrimp cannot break through the walls
also each move cost of distance * 10^'ABCD' i. shrimpId (we use
manhattan distance here, because of rule 4).
So the task was to to do all this while minimizing the total energy
cost expended by the shrimp.
For part B, the task description was the same except that the rooms
were extended with this for the middle of each room (with these
additional shrimp):
#D#C#B#A#
#D#B#A#C#
My initial approach here was to solve the puzzle by hand and write
some code to tally the costs. That got me part A, but part B was too
complicated for me to see the solution. It was not until a few days
ago that I managed to solve part B (but I did use my initial solution
to help debug my part B implementation (running the solver against the
part A data set)).
To actually solve this, I wound up using an A* algorithm. For part B
this still took about half an hour (and part A took significantly
longer, ironically).
A* is a highly serial approach, but has the advantage of eliminating
significant parts of some search spaces. Instead of doing a breadth
first or depth first search (which could be parallelized), A* uses a
queue of partial results which are sorted in lowest cost order.
I also maintained a "lowest cost" array for each visited state, and
when revisiting such a state I only proceed if my new cost is lower
than my old cost.
Also,
(a) I precalculated for each shrimp, a characterization of its two
moves (a coordinate pair, with a 0 marking the undetermined part of
each move), and
(b) I assigned the total cost of a shrimp's moves to the move into the
hallway (this meant that the second move was always cheaper than any
first move, which reflects the issue that blocking the hallway would
tend to drive up the costs of other moves).
Other than that, my code is nothing special -- actually, it's rather
verbose. But because a complete test of the code is time consuming and
I did not have any further use for it, I've left it in its crude "just
got it working" state. I apologize for the lack of readability and
lack of relevant abstraction here, but I'm feeling lazy.
(That said, the code echos every intermediate state as it's being
processed, and would probably run faster if I removed that.)
The first part -- a23 -- sets up a batch of globals to be used by
the solver:
a23=: {{
bounds=: $y
roomsN=: _4]\I.,y e.'ABCD'
hallN =: I.,(y='.')>"1 +./y e.'ABCD'
doorsN=: ({.roomsN) - {:$y NB. room positions in hallN
boardC=: ((#hallN)#'.'),(,y) ([-.-.)'ABCD'
locationsN=: ($y)#:hallN,,roomsN
assert. locationsN -:&# boardC
mask=: (-.y e.'# ')*(1~:i.#y)+./'#'=2{y
show=: (+./"1 mask)#($mask)$(,mask)#inv ([
assert@('literal'-:datatype))@]
move =: +./\.'ABCD'~:"1 roomsN {,y
roomsM=: ($roomsN)$(-#,roomsN){.i.#boardC
agenda=: move <@(,.&0,0,.|.)@#"1&|: roomsM
done=: ((#hallN)#'.'),,($roomsN)$'ABCD'
seen=: ,:done [ costs=: ,999999999
boardC 0 allpaths agenda
}}
The solver is... not pretty. Conceptually, various parts of this could
have been abstracted, resulting in tighter code.
allpaths=: {{
mqueue=: 0#,m
xqueue=: 0#,:x
yqueue=: 0#,:y
pqueue=: i.0
whilst.#mqueue do.
if. x e. seen do.
ndx=.seen i. x
if. m < ndx{costs do.
costs=: m ndx} costs
if.0=ndx do.
B=: b=. mqueue < {.costs
mqueue=: b#mqueue
xqueue=: b#xqueue
yqueue=: b#yqueue
pqueue=: b#pqueue
end.
else.
M=: m=. {.mqueue
X=: x=. {.xqueue
Y=: y=. {.yqueue
if.0=ndx do.
B=: b=. }.mqueue < {.costs
else.
B=: b=. 1
end.
mqueue=: b#}.mqueue
xqueue=: b#}.xqueue
yqueue=: b#}.yqueue
pqueue=: b#}.pqueue
echo x
continue.
end.
else.
seen=:seen,x
costs=:costs,m
end.
echo (":(show x);' ';":,.m,{.costs)-."1' '-.~,":2#<' '
displaced=. (#hallN){.x
free=. '.'=displaced
pending=.i.0 0
phase=.i.0
plan=.i.0 0
paths=. i.0
for_room.'ABCD' do.
t=. room_index {:: y
if.0=#t do.continue. end.
for_next. (1 (0}) </\ 0={."1 t) #t do.
todo=. (<t -. next) room_index} y
sign=. *hallN-room_index{doorsN
if. 0={:next do. NB. move into hallN
open=. (*/\.(_1=sign)#free),*/\(1=sign)#free
piece=. ({. next){x
assert. piece e. 'ABCD'
moves=.(#~ openmask */ .<: open"_) next+"1]0,.I.open
index=. 'ABCD'i.piece
cost=. 10^index
prices=. cost*+/"1|-/"2 moves{locationsN
door=. index{doorsN
seq=. +/piece=(#hallN){.x
row=. 1+(+/0={."1 index{::y)-+/piece=(#hallN){.x
dist=. +/"1|(({:"1 moves){locationsN)-"1 row,}.bounds#:door
values=. dist*cost
plan=.plan,(prices+values),.moves
elseif.'.'=({:next){x do. NB. move from hallN
'L R'=. sign </. displaced
opts=.((room={:L-.'.')#L i:room),(#L)+(room={.R-.'.')#R
i.room
if.#opts do.
'breakpoint here'
end.
moves=. (#~ openmask */ .<: (displaced e.'.',room)"_)
next+"1]opts,.0
plan=.plan,0,.moves
else.
continue.
end.
phase=. phase,(#moves)#*{. next
pending=.pending,(#moves)#,:todo
end.
end.
energy=. m+{."1 plan
nexts=. (_2{."1 plan) |.@:{`[`]}"1 x
B=: b=. energy < {.costs
mqueue=: mqueue,~ b#energy
xqueue=: xqueue,~ b#nexts
yqueue=: yqueue,~ b#pending
pqueue=: pqueue,~ b#{."1 plan
if.-.0={.pqueue do.
order=. /: pqueue
mqueue=: order{mqueue
xqueue=: order{xqueue
yqueue=: order{yqueue
pqueue=: order{pqueue
end.
M=:m=. {.mqueue
X=:x=. {.xqueue
Y=:y=. {.yqueue
mqueue=: }.mqueue
xqueue=: }.xqueue
yqueue=: }.yqueue
pqueue=: }.pqueue
end.
}}
The one bit of abstraction that I used here was:
thru=: [ ~.@, <. + i.@(+*)@-~
openmask=:{{
(({:bounds)|hallN)&e.@thru/"1 y { {:"1 locationsN
}}
This is used in determining whether moves are possible.
Anyways, when this runs, it displays the board (what I think the
puzzle called the shell) positions while it's running, and for
plausible layouts displays the current and final cost to along with
each board position. Discarded states are instead displayed in a
compressed format.
When it finishes, this implementation displays the board in its final
state along with the minimal cost. But that's also available in
{.costs if you wanted to remove the echo from the code.
For part B, I used the same code, with the required extra content added:
b23=: {{
a23 (3{.y),extension,3}.y
}}
extension=: ];._2 {{)n
###D#C#B#A###
###D#B#A#C###
}}
If I could find a production use for this kind of thing, I would
probably not implement it in J, except maybe this kind of prototype.
These kinds of highly serial algorithms favor compiled code, and we
currently do not have a J compiler.
FYI,
