From J Wiki
Jump to navigation Jump to search

The Problem << >>

Another maze follower, but this time with the maze changing each move. Cute.

The elves can stay in their starting position indefinitely, which means that new solution opportunities will be presented every clock cycle. Nevertheless, I think I will be better off tracking the elves' positions using an array of (y,x) rather than points on the playing area, because my puzzle input seems to have very few empty spaces: I think the frontier of solution will be pruned heavily each clock cycle.

I am not asked for the best path, so I won't track it. I'll keep only the active solutions.

I see no reason to update all the blizzard positions each step. They are predictable, and I will convert each position I care about back to the original board position at step 0. That will be a winner because there will be many more blizzards than active solutions.

After many clock cycles, I will find that most of the solutions are old. I could implement something like A* where I focus on the most promising solutions and then use distance to cut off the rest after I find the first to reach the goal. I'm not going to do that right off.

I read the input.

   ]board =: ] onaoclines

I start a script.

NB. Blizzards
bdirs =: _2 ]\_1 0  0 1  1 0  0 _1  NB. move amounts for the different blizzard types
dirs =: bdirs , 0 0 NB. possible move directions, for elves, allowing staying put
bchar =: '^>v<'  NB. characters indicating presence of blizzard in this direction
maze =: {{  NB. y is board as read in, result is #moves to reach the goal
pos =. ,:00 1  NB. list of (y,x) positions held by elves
tick =. 0   NB. the clock
goal =. _1 _2 + $x  NB. the goal
while. do.  NB. till we find the cheese...
  tick =. >: tick  NB. advance tick and convert to 1-origin
  if. goal e. pos =. ,/ pos +"1/ dirs do. break. end.  NB. get places to move to, exit if goal is one of them 5nx2
        NB. We know the goal is reachable, and it may appear to be on a blizzard if we check its coordinate
  NB. back up time to match original map; handle wrap within blizzard area;  fetch from board; set 1 if any type shows blizzard there
  inblizz =. +./"1 bchar ="1 x (<"1@[ { ])~ (_2+$x)&|"1&.:<: pos -"1/ tick * bdirs
        NB. pos is 5nx2; then 5nx4x2; 5nx4; 5nx4; 5n
  NB. Also check the out-of-bounds board, which doesn't move and mustn't be rotated.  Keep surviving positions
  pos =. ~. 00 1 ,~ pos #~ -. inblizz +. '#' = pos (<"1@[ { ]) x  NB. Keep only pos not in blizzard
        NB. 00 1 may appear to be blocked when it is forced onto the board, so include it always

After fixing a couple of blunders (directions not matching the arrows, and goa, specified in the wrong place, both repaired in the version above), it works.

   board maze ''

In Part 2 I must go through the back, go back to the start, and then to the end again. I'll loop over the goals.

NB. Blizzards
pos =. ,: initpos =. 00 1  NB. list of (y,x) positions held by elves
tick =. 0   NB. the clock
for_goal. (_1 _2 + $x) , 0 1 ,: (_1 _2 + $x) do.
... loop to go to goal
  pos =. ,: initpos =. goal  NB. reset to start at the previous goal

I had to fix one more bug: when the elves got to the first goal, the next move took them out of the board array. I extended the board with one final row of '#' to prevent the index error.