Another fun Advent of Code puzzle which tripped me up and made me learn things! This time I picked up a bit of dynamic programming practice. Here’s how I approached it using Rust.
Problem
This problem presents a grid and asks you to trace a path through from top to bottom, starting from ‘S’. Whenever you encounter a ’^’ symbol, the path needs to split in two either side of the ’^’ and continue through the grid.
.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............becomes
.......S.......
.......|.......
......|^|......
......|.|......
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............and ends up being
.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
.....|.|.|.....
....|^|^|^|....
....|.|.|.|....
...|^|^|||^|...
...|.|.|||.|...
..|^|^|||^|^|..
..|.|.|||.|.|..
.|^|||^||.||^|.
.|.|||.||.||.|.
|^|^|^|^|^|||^|
|.|.|.|.|.|||.|Part 1
The first part asks you to count how many times the path is split while moving through the grid. This isn’t just the number of ’^’ symbols present, since the path may not touch all of them.
I used a strut to hold the relevant data, with one of the key things I learnt from previous Advent of Codes that you can find all the points of interest - in this case, splitters - up front in a HashSet, to easily reference later.
#[derive(Eq, PartialEq, Hash, Debug, Clone, Copy)]
struct Position {
x: usize,
y: usize,
}
struct Layout<'a> {
width: usize,
height: usize,
start: Position,
splitters: HashSet<Position>,
map: Vec<&'a str>,
}
impl<'a> Layout<'a> {
fn from(input: &'a str) -> Self {
let mut layout = Layout {
width: 0,
height: 0,
start: Position { x: 0, y: 0 },
splitters: HashSet::new(),
map: vec![],
};
let mut count = 0;
for line in input.lines() {
layout.width = line.len();
line.chars().enumerate().for_each(|(i, c)| {
if c == 'S' {
layout.start = Position { x: i, y: count };
} else if c == '^' {
layout.splitters.insert(Position { x: i, y: count });
}
});
layout.map.push(line);
count += 1;
}
layout.height = count;
layout
}
}Using the example diagram, this gives
Layout {
width: 15,
height: 16,
start: Position { x: 7, y: 0 },
splitters: HashSet::from([
Position { x: 6, y: 4 },
Position { x: 10, y: 8 },
Position { x: 3, y: 10 },
Position { x: 8, y: 4 },
Position { x: 9, y: 10 },
Position { x: 7, y: 2 },
Position { x: 12, y: 12 },
Position { x: 1, y: 14 },
Position { x: 9, y: 6 },
Position { x: 5, y: 14 },
Position { x: 9, y: 14 },
Position { x: 7, y: 14 },
Position { x: 13, y: 14 },
Position { x: 2, y: 12 },
Position { x: 3, y: 14 },
Position { x: 7, y: 6 },
Position { x: 11, y: 10 },
Position { x: 6, y: 8 },
Position { x: 5, y: 6 },
Position { x: 4, y: 8 },
Position { x: 6, y: 12 },
Position { x: 5, y: 10 },
]),
map: vec![
".......S.......",
"...............",
".......^.......",
"...............",
"......^.^......",
"...............",
".....^.^.^.....",
"...............",
"....^.^...^....",
"...............",
"...^.^...^.^...",
"...............",
"..^...^.....^..",
"...............",
".^.^.^.^.^...^.",
"...............",
],
};The map field with the input diagram split into lines will be relevant for part two, but the key for part one is having the co-ordinates for the start and all splitters in the diagram.
Calculate beams
The approach now is to use the starting point as the base, then check if the splitters set contains the position immediately below the position being checked. If there is no splitter, then the next position is immediately below the current one. If there is a splitter, then there are now two new positions to check, one either side of the splitter encountered, and we need to keep count of the splitters encountered.
impl Layout {
...
fn calculate_splits(&self) -> u16 {
let mut beams = HashSet::from([self.start]);
let mut count = 0;
// repeat for each line in input
for _ in 0..self.height {
(count, beams) = self.step(beams, count);
}
count
}
fn step(&self, beams: HashSet<Position>, count: u16) -> (u16, HashSet<Position>) {
let mut updated_beams = HashSet::new();
let mut total = count;
// get next line from beam
// is (beam.x, beam.y + 1) a splitter?
for beam in beams {
// yes = increment and add (beam.x - 1, beam.y) and (beam.x + 1, beam.y)
if beam.y < self.height - 1 {
if self.splitters.contains(&Position {
x: beam.x,
y: beam.y + 1,
}) {
updated_beams.insert(Position {
x: beam.x - 1,
y: beam.y + 1,
});
updated_beams.insert(Position {
x: beam.x + 1,
y: beam.y + 1,
});
total += 1;
} else {
// no = push next row down
updated_beams.insert(Position {
x: beam.x,
y: beam.y + 1,
});
}
}
}
(total, updated_beams)
}
}This could also be written as a recursive function, returning when the beam y positions reach the input height.
Part 2
On to part 2! This asks for all possible paths through the grid, which sounds like a graph traversal problem. Traversal will find a path through, so we also need to make sure we backtrack and follow all paths made by splitters.
Breadth-first search sounds like it would fit here - we keep spreading outwards, either onto the next row or either side of a splitter, so we just need to keep adding the next position into the queue, and the algorithm will find all paths.
impl Layout {
...
fn part_2_search(&self) -> usize {
// queue to hold positions to search
let mut queue = vec![];
// total paths found
let mut count = 0;
queue.push(self.start);
// keep search going while there are still valid positions left
while !queue.is_empty() {
if let Some(current) = queue.pop() {
// base case: reached end of grid
// so update total paths
if current.y == self.height - 1 {
count += 1;
} else {
// if there are still valid positions for current,
// then list them all and add to queue
let mut neighbours = self.get_neighbours(current);
queue.append(&mut neighbours);
}
}
}
count
}
// find valid positions from current point
// either directly below, or if there is a splitter
// directly below, either side of current pos
fn get_neighbours(&self, pos: Position) -> Vec<Position> {
let mut neighbours = vec![];
if pos.y >= self.height {
return vec![];
}
if self.splitters.contains(&Position {
x: pos.x,
y: pos.y + 1,
}) {
neighbours.push(Position {
x: pos.x - 1,
y: pos.y,
});
neighbours.push(Position {
x: pos.x + 1,
y: pos.y,
});
} else {
neighbours.push(Position {
x: pos.x,
y: pos.y + 1,
});
}
neighbours
}
}Running this on the small, 15x16 example input grid works great, and finds the correct answer in a split second!
Running this on the actual input (my one is 141x142 grid) however, runs and runs and runs… and took so long that after five minutes I stopped it to have a bit of a re-think.
A bit of a re-think
Advent of Code puzzles usually test to see if you can solve the puzzle (part one) and that you’ve solved it in a way that can handle a lot of data (part two). This part two is pushing towards dynamic programming, ie memoisation and divide-and-conquer approaches. The breadth-first search approach with no memoisation ends up re-searching the same positions over and over again, and so is very slow.
To fix the algorithm for part two, we could either add memoisation so that paths are only checked once, or we could use a divide-and-conquer approach like the answer for part one. This would involve going line by line and incrementing the total paths for each position in the line, but only working on one line at a time. At the end of the grid, we then add up the totals for each column to get the overall score.
We can do this by creating an array with length the same as the input grid, all starting at 0. Whenever a beam moves through the column - the x position - increment the count. When encountering a splitter, duplicate the existing score to either side of the current x position and reset the current position.
.......S....... .......1.......
.......|....... .......1.......
......|^|...... ......1^1......
......|.|...... ......1.1......
.....|^|^|..... .....1^2^1.....
............... ...............
.....^.^.^..... .....^.^.^.....
............... ...............
....^.^...^.... ....^.^...^....
............... ...............
...^.^...^.^... ...^.^...^.^...
............... ...............
..^...^.....^.. ..^...^.....^..
............... ...............
.^.^.^.^.^...^. .^.^.^.^.^...^.
............... ...............
.......S....... .......1.......
.......|....... .......1.......
......|^|...... ......1^1......
......|.|...... ......1.1......
.....|^|^|..... .....1^2^1.....
.....|.|.|..... .....1.2.1.....
....|^|^|^|.... ....1^3^3^1....
............... ...............
....^.^...^.... ....^.^...^....
............... ...............
...^.^...^.^... ...^.^...^.^...
............... ...............
..^...^.....^.. ..^...^.....^..
............... ...............
.^.^.^.^.^...^. .^.^.^.^.^...^.
............... ...............As you can see, we don’t need to create an array for every row in the input grid, since each one essentially starts as a copy of the one above. We can just use a single array and work line-by-line through the input.
// add 0 for each point, and 1 for the starting point
. . . . . . . S . . . . . . .
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
// for the next line, copy the current score
// if it hits a splitter, move the current score to either side
. . . . . . . ^ . . . . . . .
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
// and keep repeating every time you reach a splitter
. . . . . . ^ . ^ . . . . . .
[0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0]Why does this work?
Look at the possible paths through the grid, and if a beam goes through a position then count it. We end up counting every time a path goes through a certain position, but by using a single array and working line by line, we don’t need to calculate every path before counting, just the point in each line that beams move through. This is an example of a divide and conquer algorithm - we’ve split the larger problem of finding every path to just working out the scores for each line.
Code time
This is really straightforward to code.
impl Layout {
...
fn calculate_part_2(&self) -> usize {
let mut count = vec![0; self.width];
// add start
count[self.start.x] = 1;
for line in self.map.iter() {
for (col, c) in line.chars().enumerate() {
if c == '^' {
// on splitter, update paths either side
// and reset
let current = count[col];
count[col - 1] += current;
count[col + 1] += current;
count[col] = 0;
}
}
}
count.iter().sum()
}
}This algorithm runs really quickly - about 0.01s on my laptop, compared with the minutes without an answer of the breadth-first search approach.