[Community Puzzle] Bender - Episode 4

Puzzles
26

Hi,

This was a tough one. I first started to think about it a year ago and finally managed to finish it. Thanks @eulerscheZahl, yet another great puzzle from you! I really liked how there were multiple problems packed together. It gave a bit the same feeling as the leagues in multiplayer: solve introduction cases (Wood 1), avoid magnetic fields (Bronze), find a good compression algorithm (Silver), solve big maps (Gold), make good use of the Garbage balls (Legend).

Here below are the detailed steps it took me to solve the problem (spoiler alert).

Click to expand

Data structure

First an important thing for every problem is to define properly the data stracture, notably what is static and what is part of a game state. One has to find the good balance with a minimalist game state (which will perform faster with search algorithms that make many copies) and readability/easiness to use. The following was what worked best for me.

Global static data
  • Map layout: for each cell, it gives the information of whether it’s a wall or not (Can be stored in a 2D array CELLS[x][y] or 1D array CELLS[position] where position = x + y * width)
  • Neighbours: for each cells, precompute the neighbours (many structures are possible, I tend to go for a 1D array NEIGHBOURS[position*NB_DIRECTIONS + direction] where NB_DIRECTIONS=4 and direction is a char between 0 and 3 mapped to UP, DOWN, LEFT, RIGHT)
  • Fry’s position
  • Fields: for each field, store its position and associated switch
  • Switches: for each switch, store its position and associated field
Game state data:
  • Bender’s position
  • state of the fields (on/off)
  • position of the balls
  • path: list of directions that Bender took to get to the state (Alternatively, we could just store the last move and the pointer to the parent and deduce the path from backtracking. But I didn’t want to manage pointers and the performances were already good enough)

Step 1 - Basic maze resolution

I started to work on the problem as if it was a standard maze puzzle, ignoring all fields and considering balls as walls. I just used a simple BFS disallowing Bender to go back to an already visited cell. This was easy to test thanks to the introduction levels.

See code here 
State initialState;
list<State> queue;
queue.push(initialState);
array<bool, NB_CELLS> visitedCells;
visitedCells.fill(false);
visitedCells[initialState.position] = true;
while (queue.size() > 0) {
  State& currentState = queue.front();
  for (char direction = 0; direction < NB_DIRECTIONS; direction++) {
    int nextPosition = NEIGHBOURS[position * NB_DIRECTIONS + direction];
    // if the next position was already visited we skip it
    if (visitedCells[nextPosition]) continue;
    // playDirection returns whether the move was successful
    bool hasMoved = currentState.playDirection(direction);
    if (hasMoved) {
      if (currentState.position == targetPosition) {
        // if Bender is on Fry's position, we found our solution
        return currentState;
      }
      // Mark the cell as visited so we don't process it again
      visitedCells[currentState.position] = true;
      queue.push_back(tempState);
      // reset currentState for the next moves
      currentState.revertLastMove();
    }
  }
  queue.pop_front();
}

Step 2 - Solve the maze with magnetic fields

As expected, when we start to test the previous code on maps containing fields, Bender will rush to Fry and get nuked by the first field he encounters.
So, in a second step, in State::playDirection we need to take fields into account:

  • When Bender walks on a switch, toggle the associated field
  • When Bender tries to go on an active field, consider it as an invalid move

With this, we pass all the introduction levels, and the basic setup is done. But we quickly notice that for complex maps, the BFS fails to find a solution. Indeed, sometimes when a Bender reaches a switch, he needs to go back on his steps to go to his next target, but he can’t because of the visited cells logic.

I tried a few approaches that didn’t work that well:

  • Remove visited cells logic: it’s the issue, so why not just removing it? Well allowing Bender to go back on his steps without any conditions makes the search space explode with duplicated non relevant states:
    • depth 0: (0,0)
    • depth 1: (0,1), (1,0)
    • depth 2: (0, 0), (0,2), (1,1), (0,0), (1,1), (2,0) => at depth 2 only, we already have a duplicated (1,1) position and even a (0,0) duplicated position that is equivalent to depth 0
  • Reset visited cells when walking on a switch: This one is better and actually on some maps where the switch is not far from its associated field AND Fry, it would pass the validators. But the search space still explodes when Bender has to walk on multiple switches:
    • depth X: (posSwitch0), etc
    • depth Y: (posSwitch1), etc (=> walking on posSwitch1 reset the visited cells so Bender can go back to posSwitch0)
    • depth Z: (posSwitch0), etc (=> a few turns later, Bender is again on posSwitch0, which reset the visited cells and he can go back to posSwitch1 in a few turns, etc…)

What we notice is that with poor reset conditions, the search space is unbounded (due to the infinite loops between states) and the bfs will never terminate in time.

After thinking about the problem, I realized that a BFS can be bounded by the number of different possible states of a problem. The basic maze problem mislead me because Bender’s position/cell was actually equivalent to the state. But actually, all we need to do is to prevent Bender from going back to a visited state rather than a visited cell.

Our game state structure consists of the position, the state of the fields, the position of the balls and the path. The position of the balls can be ignored for now and the path is there merely to easily print the result of the search. So in the end, our state is Bender’s position and the state of the magnetic fields (if you are good at visualizing, the problem is similar to a 3D maze where switches are portals that link 2D maps), with a search space limited to:

NB_STATES = WIDTH * HEIGHT * pow(2, NB_SWITCHES) = 21 * 21 * pow(2, 11) = 903168

Wow it’s almost a million! But it’s still good news:

  • A boundary of 1 million is better than an unbounded problem
  • States can be defined by a 32-bits int
  • Our NB_STATES is very pessimistic. There is sometimes less than 11 switches per map, not all state combinations will be explored before finding a solution. And we are lucky enough to be in a maze, so a lot of the cells are walls.

After replacing the visitedCells by the visitedStates logic in the BFS, all tests were now passing in under 10ms (in C++)!

Step 3 - Allow moves on Garbage Balls

We now need to include garbage balls handling in State::playDirection:

  • Bender can walk on a ball if the next cell behind it is not a wall or another ball
  • Update the position of the ball

My first approach was to run a BFS once with balls as walls and once considering that balls can be moved for the rest of the time. It actually gives pretty decent results with a score around 3800. But because the BFS is still relying on states that aren’t considering the balls, it behaves a bit randomly depending on the map.

I tried to include the balls in the state “hash” but it was making the search space too big. In the end my best score without compression was 3744.

Step 4 - Compression

Nothing fancy here, I check all the substrings of the result and find the one that will reduce the most the size of the result. I repeat the process until I reach 9 functions or I can’t improve the size of the result. (Pro tip: ignore substrings containing the “;” function separator)

Misc

Pruning

In a maze, most dead ends are useless. Replacing them by walls can reduce the search space by a lot. But removing all of them can have bad consequences as well so choose carefully :wink:

Direction order

If like me, you use a search with fixed direction order, changing the order might affect the result of your searches. While it won’t change the size of the path, it can change the path itself and as such how good it is for compression. Tweaking the direction order made me gain a few more points.

4 Likes