Baerentsen.space
Posts Tags Categories Keyboards Portfolio Projects
Baerentsen.space

Contents

AoC 2024/15: 🎄 The Misadventures of the Lanternfish Warehouse Robot 🎅

   1834 words   9 minutes 

🎄 The Misadventures of the Lanternfish Warehouse Robot 🎅

Advent of Code 2024-15

We’re deep under the ocean in our mini-submarine (again!), when the glow of a school of lanternfish catches your eye.

It turns out that these industrious lanternfish have built an elaborate network of warehouses to store food for their ever-growing population. Unfortunately, disaster has struck! A malfunctioning robot is wreaking havoc in one of their most critical warehouses, pushing boxes around with reckless abandon.

🐟 The Problem

The warehouse is represented as a grid where:

  • # marks walls.
  • . represents empty spaces.
  • @ is the robot’s current position.
  • O marks the locations of boxes.

The robot moves according to a set of instructions (<, >, ^, v), attempting to:

  1. Move in the specified direction.
  2. Push any box (O) in its path, provided there is space behind it.
  3. Do nothing if a move would cause the robot or a box to collide with a wall (#) or another box.

An example looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########

Our task is to simulate the robot’s movement and calculate the sum of all box GPS coordinates once the robot has finished its instructions.

The GPS Coordinates can be calculated using:

GPS Coordinate=100×row distance+column distance

Personally I love these grid problems, as it allows for graphical debugging and they are generally easier to brute-force, as a non-professional programmer.

🎁 Part 1

The challenge starts with a regular warehouse layout and the robot’s list of movements. Using Python, we simulate each move, accounting for:

  • Box movement (or blockage by walls or other boxes).
  • Robot positioning.
  • Calculating the GPS coordinates of boxes at the end.

0. Helper functions

As mentioned, I have helper functions for grid work.

File to grid

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def toGrid(input, parser=None):
    """
    Converts input (file or data) into a grid (list of lists).
    
    Args:
        input (str): The file path or data to be converted into a grid.
        parser (function, optional): A parser function to process each line before adding to the grid. 
                                     Defaults to None.
    
    Returns:
        list: A 2D list (grid) representation of the input.

    Raises:
        FileNotFoundError: If the file cannot be found (if input is a file path).
        ValueError: If the parser function is invalid.
    """
    if parser is not None and not callable(parser):
        raise ValueError("The parser must be a callable function.")

    grid = []
    try:
        with open(input) as file:
            for line in file:
                grid.append(parser(list(line.rstrip())) if parser else list(line.rstrip()))  # Use parser or default processing
    except FileNotFoundError:
        raise FileNotFoundError(f"The file '{input}' was not found.")
    except IOError as e:
        raise IOError(f"Error reading file '{input}': {e}")
    
    return grid

Adding tuples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def addTuples(x: tuple, y: tuple):
	"""
	Adds two tuples element-wise.
	
	Args:
	x (tuple): The first tuple.
	y (tuple): The second tuple.
	
	Returns:
	tuple: A tuple with the sum of corresponding elements of x and y.
	
	Raises:
	TypeError: If x or y are not tuples.
	
	"""

	if not isinstance(x, tuple) or not isinstance(y, tuple):
		raise TypeError("Both inputs must be tuples.")
	
	return (x[0] + y[0], x[1] + y[1])

Get grid values

I’m not listing the whole function, as it can be found on my [gitea repo][https://gitea.baerentsen.space/FrederikBaerentsen/AdventOfCode/src/branch/master/fred.py]. But the main idea can be seen here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def get_value_in_direction(grid:list, position:set, direction:str=None, length:int=1, type:str=None):
    """
    Get the value(s) in a specified direction from a given position in a grid.
    If no direction is provided, returns the value at the current position.

    Args:
        grid (list of list of int/float/str): The 2D grid.
        position (set): A set containing x (row index) and y (column index) as integers.
        direction (str, optional): The direction to check. Defaults to None.
        length (int, optional): The number of steps to check in the given direction. Default is 1.
        type (str, optional): The type of result to return ('list' or 'str'). Defaults to None.

    Returns:
        list or str: A list or string of values in the specified direction, or a single value.

    Raises:
        ValueError: If direction is invalid or position is not a set of two integers.
        TypeError: If grid is not a list of lists.
    """

1. Setting Up the Warehouse

The next thing we do is load the warehouse layout and identify the starting position of the robot (@).

1
2
3
4

for r, row in enumerate(grid):
    for c, col in enumerate(row):
        if grid[r][c] == '@':
            start = (r, c)
  • The grid represents the warehouse as a 2D array of characters (#, ., O, @).
  • We loop through the grid to find the robot’s starting coordinates (start).

2. Moving the Robot

Each movement (<, >, ^, v) is processed one by one. The robot attempts to move in the specified direction. We define a dictionary to map directions to their respective coordinate changes:

1
2
3
4
5
6

directions = {
    '^': (-1, 0),  # Move up
    'v': (1, 0),   # Move down
    '>': (0, 1),   # Move right
    '<': (0, -1),  # Move left
}

The robot’s logic for handling moves is as follows:

  1. Check the space in the desired direction:

    • If it’s a wall (#), the robot stays put.
    • If it’s empty (.), the robot moves there.
    • If it’s a box (O), the robot attempts to push it.

  2. Handling box pushing:

    • The robot checks if the box can be moved (i.e., if the space behind it is empty).
    • If the box can move, it’s pushed into the empty space, and the robot moves into the box’s previous position.

Here’s the box-pushing logic in action:

1
2
3
4
5
6

if next == 'O':  # Box in the way
    next_pos = (pos[0] + direction[0], pos[1] + direction[1])
    if grid[next_pos[0]][next_pos[1]] == '.':  # Can push
        grid[next_pos[0]][next_pos[1]] = 'O'  # Move box
        grid[pos[0]][pos[1]] = '.'  # Leave robot's current space
        pos = next  # Update robot's position

This ensures the robot pushes the box properly while respecting boundaries.

3. Calculating the GPS Sum

After processing all the moves, we calculate the GPS coordinates for all remaining boxes (O). The formula is:

[ \text{GPS Coordinate} = 100 \times \text{row index} + \text{column index} ]

1
2
3
4
5

result = 0
for r, row in enumerate(grid):
    for c, char in enumerate(row):
        if char == 'O':  # Found a box
            result += (100 * r + c)

This loop iterates through the final grid, adding up the GPS values for all boxes.

Final Grid Visualization

As the robot moves, we can print out the grid to track its progress, which is helpful for debugging or just appreciating the chaotic beauty of the robot’s path:

1
2
3

def print_grid(grid):
    for row in grid:
        print("".join(row))

🎁 Part 2: Expanding the Warehouse

For Part 2, the lanternfish reveal that the warehouse has a scaled-up version where everything (except the robot) is twice as wide:

  • Walls (#) become ##.
  • Boxes (O) become [].
  • Empty spaces (.) become ...

This change means boxes can now align side-by-side and be pushed together. To solve this, the program needed to:

  1. Adjust for the expanded grid.
  2. Ensure box movements accounted for their increased size and alignment.

Scaling Up for Part 2

In Part 2, the lanternfish introduce a scaled-up warehouse where:

  • Walls (#) are doubled into ##.
  • Boxes (O) become [] to represent their increased size.
  • Empty spaces (.) become ...

When reading part 2, my immediate thought was how hard can that be, followed by viewing the example and changing my mind to I’m skipping Part 2 today. I decided to try my luck with a slightly changed Part 1 code and hope for the best.

1. Resizing the Grid

We start by transforming the grid into its scaled-up version. Each tile is expanded horizontally:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

new_grid = []
for row in grid:
    new_row = ""
    for char in row:
        if char == '#':
            new_row += '##'
        elif char == 'O':
            new_row += '[]'
        elif char == '.':
            new_row += '..'
        elif char == '@':
            new_row += '@.'
    new_grid.append(new_row)

This creates a new grid that is twice as wide as the original.

2. Adapting the Robot’s Movements

The robot logic from Part 1 remains the same, but now it must account for the fact that boxes ([]) take up two spaces. For example:

  • When the robot pushes a box, it must check both spaces of the box.
  • If the box moves, both spaces must be updated accordingly.

To check which boxes can move, we can recursively go through the boxes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def canBeMoved(pos, direction, boxes2move):
	if pos in boxes2move:
		return None

	current = get_value_in_direction(grid, pos)
	if current == '#':
		return '#'

	if current in ['[', ']']:
		boxes2move.append(pos)
		adjacent_checks = [
			addTuples(pos, directions[f"{direction}-right"]),
			addTuples(pos, directions[f"{direction}-left"]),
			addTuples(pos, directions[direction]),
		]
		for next_pos in adjacent_checks:
			if canBeMoved(next_pos, direction, boxes2move):
				return True
	return boxes2move

To move the boxes we call:

1
2
3
4
5
6
7
8

def move_boxes(boxes, direction, positions, grid):
	"""Helper function to move boxes and update grid."""
	boxes = sorted(boxes, reverse=(direction == 'down'))
	prev_values = {b: grid[b[0]][b[1]] for b in boxes}
	for box in boxes:
		new_pos = addTuples(box, directions[direction][1])
		grid[box[0]][box[1]] = '.'
		grid[new_pos[0]][new_pos[1]] = prev_values[box]

What caused me a bit of a headache was a case like this:

1
2
3
4
5
6
7

##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##.....@....##
##############

Here we get a list like [(4,6),(4,7),(3,5),(3,6),(3,7),(3,8)] and going through the list we first move (4,6) and the grid becomes:

1
2
3
4
5
6
7

##############
##......##..##
##..........##
##...[[[]...##
##.....]....##
##.....@....##
##############

The rest of the numbers follow:

1
2
3
4
5
6
7

##############
##......##..##
##..........##
##...[[]]...##
##.....@....##
##..........##
##############

1
2
3
4
5
6
7

##############
##......##..##
##...[[]]...##
##..........##
##.....@....##
##..........##
##############

This is all sorts of wrong! But it can easily be solved using boxes = sorted(boxes, reverse=(direction == 'down')) such that we move the lowest value boxes first when going up and highest value boxes when going down.

3. Calculating the GPS for Wide Boxes

For wide boxes ([]), the GPS coordinate is based on the closest edge of the box:

[ \text{GPS Coordinate} = 100 \times \text{row index} + \text{column index of left edge} ]

This is an incredible easy change, as we just replace the search for O with [.

Holiday Wrap-Up

The lanternfish are thrilled, and the malfunctioning robots are finally under control. The warehouse glows with festive lights as the lanternfish celebrate your heroic efforts.

My complete Advent of Code can be found on my Gitea page https://gitea.baerentsen.space/FrederikBaerentsen/AdventOfCode

Happy coding, and Merry Christmas! 🎄

Updated on 2024-12-16
 Advent of Code, Python, Programming
Back | Home