@mazon Logistics
I think this day was the first that gave me a proper headache for the first time this year, all because of a stupid bug in part 2... but let's proceed in order.
We're in a warehouse with a number of boxes scattered all over. Our robot @ is moving around and causing any boxes O in the way to shift as well, until they point they reach a wall (# in the example):
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########
In that starting position, if the robot was to move one step towards the left, the box next to it would move as well:
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#.O@...O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########
The same applies to any cases where there's multiple boxes in a row, of course. Say we are in this situation:
########
#...@OO#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########
The robot stepping towards South would result in this layout, leading to all four boxes ahead of it to shift downwards:
########
#....OO#
##..@..#
#...O..#
#.#.O..#
#...O..#
#...O..#
########
If a movement was not possible, such as moving downwards again in the previuos grid, the robot would just skip to the next step.
The movement instructions are determined by a list of arrows like <vv>^<v^>v>^vv^v>v<>v^v, where intuitively < indicates a step towards West, v towards South, and so on.
The key challenge for this task is to figure out the boxes' movements, since for example a row/column of boxes can be pushed freely (there's no limit to the number of boxes the robot is able to shift) for as long as there is a space . at the end.
A strategy I thought would be useful is a recursive function that essentially address the question: can the current box move? The answer is yes if the next coordinate in the same direction (given by the robot's current movement) is an empty space. If instead there is a wall, the answer's no. If the next cell is another box, we can call the function again on such box.
function shiftBox(grid: Grid, box: Coord, dir: Cardinal) {
const candidatePos = move(box, dir);
if (grid.get(candidatePos) === '#') {
// The box can't move because of a wall
return box; // Return its coordinates
}
if (grid.get(candidatePos) === '.') {
// The box can move because there is a free space ahead
grid.set(candidatePos, 'O'); // Shift the box ahead by one step
grid.set(box, '.');
return candidatePos; // Return the box' new position
}
if (grid.get(candidatePos) === 'O') {
// The cell ahead is occupied by another box
const res: Coord = shiftBox(grid, candidatePos, dir)!; // Call the recursive function with the neighbor box as subject
if (res !== candidatePos) {
// The box can move thanks to an empty space
if (grid.get(box) === 'O') {
grid.set(candidatePos, 'O');
grid.set(box, '.');
}
return candidatePos;
} else {
// The box cannot move
return box;
}
}
}
At this point we can loop through all the input directions and find the final position of all boxes, which is used to calculate the answer for part 1:
let sourcePos = new Coord(initialPos.x, initialPos.y);
for (const dir of directions) {
const newPos = move(sourcePos, dir);
if (grid.get(newPos) === '.') {
// If new position is empty, just move the robot
sourcePos = new Coord(newPos.x, newPos.y);
} else if (grid.get(newPos.serialize()) === 'O') {
// Otherwise, figure out if the boxes ahead can be moved
const res = shiftBox(grid, sourcePos, dir)!;
if (res === newPos) {
sourcePos = new Coord(newPos.x, newPos.y);
}
}
}
As for part 2, the additional difficulty is due to the fact that we're essentially doubling the width of the warehouse - including the boxes, which go from O to []. This translates the original example
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########
into something like this:
####################
##....[]....[]..[]##
##............[]..##
##..[][]....[]..[]##
##....[]@.....[]..##
##[]##....[]......##
##[]....[]....[]..##
##..[][]..[]..[][]##
##........[]......##
####################
Not much changes if the robot moves horizontally: we simply need to take into account that a box is composed of two parts, so any movement will have to shift both halves.
##############
##......##..##
##..........##
##....[][]@.##
##....[]....##
##..........##
##############
Move <:
##############
##......##..##
##..........##
##...[][]@..##
##....[]....##
##..........##
##############
Moving vertically, on the other hand, comes with a bit of a twist, because the boxes can now be staggered: the robot only sees one directly ahead of it, but beyond such box there could be two boxes, which in turn could be connected to three more, and so on. Essentially for every robot's step that would cause a box to shift, we need to trace the "chain" of boxes that would move together if pushed.
##############
##..........##
##....[]....##
##.[][]..#..##
##..[].[]...##
##...[][]...##
##....[]....##
##.....@....##
##############
Above, for example, if the robot was to move upwards, eight boxes would have to shift upwards as well.
First things first, I wrote a function to identify a box's two coordinates:
function findBoxCoords(pos: Coord, grid: Grid) {
if (grid.get(pos) === '[') {
return { l: pos, r: new Coord(pos.x + 1, pos.y) };
} else {
return { l: new Coord(pos.x - 1, pos.y), r: pos };
}
}
This function is to address the case involving an "horizontal chain": we basically keep adding the boxes' coordinates until we find a space, or a wall.
function findHorizontalChain(
pos: Coord,
grid: Grid,
dir: Cardinal.EAST | Cardinal.WEST
): { canMove: boolean; chain: Box[] } {
let box = findBoxCoords(pos, grid);
let chain: Box[] = [box];
while (true) {
let candidatePos;
if (dir === Cardinal.EAST) {
candidatePos = new Coord(box.l.x + 2, pos.y);
} else {
candidatePos = new Coord(box.r.x - 2, pos.y);
}
if (grid.get(candidatePos.serialize()) === '#') {
return { chain, canMove: false };
}
if (grid.get(candidatePos.serialize()) === '.') {
return { chain, canMove: true };
} else {
box = findBoxCoords(candidatePos, grid);
if (!chain.includes(box))
if (dir === Cardinal.WEST) {
chain.splice(0, 0, box); // Place at the start
} else {
chain.push(box);
}
}
}
}
Then, for a "vertical chain", which unlike a horizontal one can feature staggered boxes, the function iteratively explores boxes above (if moving North) or below (if moving South), and stops if encountering a space or a wall. It finally returns the chain of connected boxes and whether further movement in the specified direction is possible:
function findVerticalChain(
pos: Coord,
grid: Grid,
dir: Cardinal.NORTH | Cardinal.SOUTH
) {
let box = findBoxCoords(pos, grid);
let chain: Box[] = [box];
let stack: Box[] = [box];
while (stack.length > 0) {
const curr = stack.pop()!;
const candidatePos: Coord[] = [];
if (dir === Cardinal.NORTH) {
candidatePos.splice(0, 0, new Coord(curr.l.x, curr.l.y - 1));
candidatePos.push(new Coord(curr.r.x, curr.r.y - 1));
} else {
candidatePos.splice(0, 0, new Coord(curr.l.x, curr.l.y + 1));
candidatePos.push(new Coord(curr.r.x, curr.r.y + 1));
}
if (candidatePos.some((p) => grid.get(p) === '#')) {
return { chain, canMove: false };
}
for (const p of candidatePos) {
const cell = grid.get(p.serialize());
if (cell === '[' || cell === ']') {
const newBoxCoords = findBoxCoords(p, grid);
if (
!chain.some((box) => box === newBoxCoords) &&
!stack.some((box) => box === newBoxCoords)
) {
if (dir === Cardinal.NORTH) {
// Add at the start if moving North
chain.splice(0, 0, newBoxCoords);
stack.splice(0, 0, newBoxCoords);
} else {
chain.push(newBoxCoords); // or at the end if moving South
stack.push(newBoxCoords);
}
}
}
}
}
return { chain, canMove: true };
}
What about the bug I mentioned at the start? Well, it was understandably linked to the way I identified the chain…
Imagine a case like this, which at some point happens in the real input:
##############
##......##..##
##....[]....## D
##...[][]...## B C
##....[]....## A
##.....@....##
##############
The robot is meant to move upwards, and there's four boxes in the chain: the logic of my function, which locates the boxes in a chain one row after the other, would of course find boxes B and C after box A, and then box D would be considered a "child" of both boxes B and C.
I did have a check to prevent the same box from being added twice, however the problem lay in the way I added the discovered boxes to the chain, since the order - as I soon realised - is crucial to the way I shifted the boxes - upwards in this case. Long story short, without sorting the boxes properly, my program would shift the C box before the D one, resulting in the poor D box losing its right half… :(
##############
##....[.##..## D
##...[][]...## B C
##....[]....## A
##.....@....##
##..........##
##############
The solution to the bug was simply to sort the chain of boxes by the value of y before applying the shift, and after that everything run smoothly 🚀
The general function was then fairly similar to the one from part 1, this time taking into account the double width of the boxes during the movements:
function shiftBoxes(grid: Grid, box: Coord, dir: Cardinal) {
if (dir === Cardinal.WEST || dir === Cardinal.EAST) {
const { canMove, chain } = findHorizontalChain(box, grid, dir);
if (!canMove) {
return false;
}
if (dir === Cardinal.WEST) {
for (let i = 0; i < chain.length; i++) {
const newLeft = move(chain[i].l, dir);
const newRight = move(chain[i].r, dir);
grid.set(newLeft.serialize(), '[');
grid.set(newRight.serialize(), ']');
grid.set(chain[i].r.serialize(), '.');
}
} else {
for (let i = chain.length - 1; i >= 0; i--) {
const newRight = move(chain[i].r, dir);
const newLeft = move(chain[i].l, dir);
grid.set(newRight.serialize(), ']');
grid.set(newLeft.serialize(), '[');
grid.set(chain[i].l.serialize(), '.');
}
}
} else {
const { canMove, chain } = findVerticalChain(box, grid, dir);
if (!canMove) {
return false;
}
if (dir === Cardinal.NORTH) {
for (let i = 0; i < chain.length; i++) {
const newLeft = move(chain[i].l, dir);
const newRight = move(chain[i].r, dir);
grid.set(newLeft.serialize(), '[');
grid.set(newRight.serialize(), ']');
grid.set(chain[i].l.serialize(), '.');
grid.set(chain[i].r.serialize(), '.');
}
} else {
for (let i = chain.length - 1; i >= 0; i--) {
const newRight = move(chain[i].r, dir);
const newLeft = move(chain[i].l, dir);
grid.set(newRight.serialize(), ']');
grid.set(newLeft.serialize(), '[');
grid.set(chain[i].l.serialize(), '.');
grid.set(chain[i].r.serialize(), '.');
}
}
}
return true;
}
Boy, that was painful!