Introduction

Today’s puzzle was about grid traversal and simulating process. Let me setup the scenario.

We are there at the printing department. And we need the forklift for the commute process, but the forklifts are used by the elves for moving heavy rolls of wrapping paper. We need to optimize their workflow, so that the forklifts become free ASAP.

Now comes the important part, the paper rolls are arranged in a grid, and in the given representation, a paper roll is represented by @. For example,

In this grid a forklift can access/lift a paper roll if there are fewer than four in the eight adjacent positions. In the above example, the rolls that can be accessed are marked x.

Puzzle 1

First puzzle was quite simple simple, we simply had to count the number of liftable rolls. In the given example, it is $13$.

Let me tell you a little bit about the adjacent positions. In a grid, for a position (i, j), the adjacent positions are the following. Its the positions at units distance from that position in vertical or horizontal or diagonal direction. In the figure below for blue position, the green position are called adjancent.

Solution and Implementation

We will simply check at each of the eight positions, that if they exist(they don’t for border elements) and if they are paper roll and count them, if that count < 4, count it in ans.

for (int i = 0; i < grid.size(); ++i) {
    for (int j = 0; j < grid[0].size(); ++j) {
      if (grid[i][j] != '@')
        continue;
      int count =
          // N
          (i >= 1 && grid[i - 1][j] == '@') +
          // NW
          (i >= 1 && j >= 1 && grid[i - 1][j - 1] == '@') +
          // W
          (j >= 1 && grid[i][j - 1] == '@') +
          // SW
          (j >= 1 && i < grid.size() - 1 && grid[i + 1][j - 1] == '@') +
          // S
          (i < grid.size() - 1 && grid[i + 1][j] == '@') +
          // SE
          (j < grid[0].size() - 1 && i < grid.size() - 1 &&
           grid[i + 1][j + 1] == '@') +
          // E
          (j < grid[0].size() - 1 && grid[i][j + 1] == '@') +
          // NE  ← missing one
          (i >= 1 && j < grid[0].size() - 1 && grid[i - 1][j + 1] == '@');
      if (count < 4)
        ans++; // count as liftable
    }
  }

Puzzle 2

Now the Elves just need help accessing as much of the paper as they can.

Once a roll of paper can be accessed by a forklift, it can be removed. Once a roll of paper is removed, the forklifts might be able to access more rolls of paper, which they might also be able to remove. How many total rolls of paper could the Elves remove if they keep repeating this process?

In simple words, we remove the removable ones, then remove more(if possible) until we are left with such situation, that we can’t remove anymore. In the above example, the simulation/solution is present here.

Solution

We can’t remove the removable paper rolls on the first pass(where we are checking if they are removable or not) as that might hinder the verification of other rolls, instead we just mark them, and then after this pass, we remove them(just mark them .). And repeat this process, until nothing is marked in first pass

Implementation

In my implementation, I used a list of positions that are supposed to be marked. When I have to mark them, I just push them in this list. If nothing is in the list after this pass we just stop the whole process, else we remove(marking them . in the grid) all the positions while also adding the list’s original size to the final solution.

  int final_ans = 0;
  list<pair<int, int>> positions;
  do {
    positions.clear();
    for (int i = 0; i < grid.size(); ++i) {
      for (int j = 0; j < grid[0].size(); ++j) {
        if (grid[i][j] != '@')
          continue;
        int cnt =
            // N
            (i >= 1 && grid[i - 1][j] == '@') +
            // NW
            (i >= 1 && j >= 1 && grid[i - 1][j - 1] == '@') +
            // W
            (j >= 1 && grid[i][j - 1] == '@') +
            // SW
            (j >= 1 && i < grid.size() - 1 && grid[i + 1][j - 1] == '@') +
            // S
            (i < grid.size() - 1 && grid[i + 1][j] == '@') +
            // SE
            (j < grid[0].size() - 1 && i < grid.size() - 1 &&
             grid[i + 1][j + 1] == '@') +
            // E
            (j < grid[0].size() - 1 && grid[i][j + 1] == '@') +
            // NE  ← missing one
            (i >= 1 && j < grid[0].size() - 1 && grid[i - 1][j + 1] == '@');
        if (cnt < 4) {
          final_ans++;
          positions.push_back({i, j});
        }
      }
    }
    for (const auto [i, j] : positions)
      grid[i][j] = '.';
  } while (positions.size() != 0);

Conclusion

These might not have been the most efficient solutions, but they are surely simple, and that also counts in software engineering. Most of the times, simplicity of the solutions matters mote than the premature optimizations/optimizations possible.

Signing off