My solution there was also quite verbose. Golfing an implementation might be a worthwhile exercise.
Thanks, -- Raul On Wed, Feb 2, 2022 at 6:15 AM 'Michael Day' via Programming <programm...@jsoftware.com> wrote: > > More chat on this old thread. > > Finished at last! 50 stars for something or other... > It took quite a lot of tweaking to build in the restrictions to the > "amphipods' " movements that I'd > mentioned in my msg of 23Jan, below. I'd overlooked the paragraph > (originally without J's NB. as > Raul pointed out. The NB.s arise from the way I process the results of > text-capture from a browser > in order to embed them in a J script.) > > The problem remained difficult for me probably because I didn't find a > decent data structure. > FWIW, each "state" consisted of one item of cost with 7 hall cells + 8 > room cells for part 1, or > with 7 + 16 room cells for part 2. It might well be better to have 7 > hall cells + 4 room objects, > or even, possibly, 7 + 4 donors rooms + 4 sink rooms, but I haven't > explored these ideas. > > The original approach considered single cell moves only, ie those > between adjacent pairs of > room cells, between any outermost room cell and its two neighbouring > hall cells, and between > pairs of hall cells; distances traversed were either one or two units, > the latter where the > transient hall cell immediately outside a room was crossed. > > After my epiphany, I dispensed with hall-hall movements altogether. > However, it was still > tricky to limit hall-room and room-room movements according to the > current occupancy of > the rooms. > > The code is far too verbose and loopy to be worth posting! > > I'll now have a look at Raul Miller's solution, way below in this > post, and see what I missed. > > And then back to Project Euler to see if any current problems are > approachable! > > Thanks for your patience, > > Mike > > On 23/01/2022 19:02, 'Michael Day' via Programming wrote: > > Chat really - sorry! > > > > An update on my progress on this so-far elusive problem for me, part2 > > at least. > > > > I _nearly_ got the right answer - tweaking the code resulted in being > > able to reach > > a termination of the tree-search - too high! - another tweak - too > > low! further > > tweaks - explosion of search space. > > > > Then I noticed: > NB. I MISSED THIS POINT!!!!! > NB. Once an amphipod stops moving in the hallway, it will stay in > that spot until it can move into a room. (That > > NB. is, once any amphipod starts moving, any other amphipods currently > > in the hallway are locked in place and > > NB. will not move again until they can move fully into a room.) > > > > I'd completely overlooked this restriction - my amphipods could all > > move in the hallway ... > > > > Back to the J-board. > > > > I'm avoiding looking at Raul's solution, still hoping to find one for > > myself! > > > > > > READ THE PAPER BEFORE TACKLING THE QUESTIONS! > > > > > > > > Cheers, > > > > > > Mike > > > > > > > > On 13/01/2022 01:19, Raul Miller wrote: > >> 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, > >> > > > > > > > -- > This email has been checked for viruses by Avast antivirus software. > https://www.avast.com/antivirus > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
