Advent of Code 2023 Days 13 and 14 Highlights
Work and life came to derail my AoC schedule a bit, but I’m catching up now :) I will need to revisit day 12 since I took a road that proven to be wrong with my Elixir solution, but the other days so far are solved, and here is the highlights from the days 13 and 14 solutions. The next post will be about days 15 and 16 - I decided to split them to not make the post too long :)
Let’s dive in.
Day 13 in Rust: Bitwise XOR comes to the rescue
I tried some binary fiddling for day 12, but it failed. Yet for some reason, looking at the task for day 13 I felt that it can be represented neatly with binary again. This time I hit the jack pot :)
The core idea was to represent each row and column as a single unsigned integer. For example, this row:
#.##..##.can be interpreted as this binary number:
101100110
which is 358 in decimal.
If we convert all rows of the first test case like this, we’ll get 358, 90, 385, 385, 90, 102, 346 so you can
easily see that we can find our reflection line between rows with 385.
So, let’s do some parsing straight to the integers:
use std::collections::HashMap;
#[derive(Debug, Clone)]
pub struct Pattern {
rows: Vec<u32>,
cols: Vec<u32>,
}
pub fn parse_input(input: &str) -> Vec<Pattern> {
let mut patterns = vec![];
for pattern in input.trim().split("\n\n") {
let mut rows = vec![];
let mut char_cols: HashMap<usize, Vec<_>> = HashMap::new();
for row in pattern.split("\n") {
let mut row_binary = vec![];
for (col, ch) in row.chars().enumerate() {
let ch = match ch {
'.' => "0",
'#' => "1",
_ => panic!("unknown character: {ch:#?}"),
};
row_binary.push(ch);
char_cols.entry(col).and_modify(|char_col| char_col.push(ch)).or_insert(vec![ch]);
}
rows.push(u32::from_str_radix(&row_binary.join(""), 2).unwrap());
}
let cols = (0..(*char_cols.keys().max().unwrap() + 1))
.into_iter()
.map(|col| u32::from_str_radix(&char_cols[&col].join(""), 2).unwrap())
.collect();
patterns.push(Pattern { rows, cols });
}
patterns
}We need to maintain a hashmap from column index to a vector of bits in the column while we’re going through the rows, but otherwise it’s straightforward.
A function to find symmetry is also easy enough, though I spent a bit of time with random off-by-one errors:
fn find_symmetry(pattern: &Pattern) -> Option<(Option<usize>, Option<usize>)> {
let mut row = 0;
while row < pattern.rows.len() - 1 {
let mirror_half_size = (row + 1).min(pattern.rows.len() - row - 1);
let mut reflected = true;
for offset in 0..mirror_half_size {
if pattern.rows[row - offset] != pattern.rows[row + offset + 1] {
reflected = false;
break;
}
}
if reflected {
// task uses 1-indexes
return Some((Some(row + 1), None));
}
row += 1;
}
let mut col = 0;
while col < pattern.cols.len() - 1 {
let mirror_half_size = (col + 1).min(pattern.cols.len() - col - 1);
let mut reflected = true;
for offset in 0..mirror_half_size {
if pattern.cols[col - offset] != pattern.cols[col + offset + 1] {
reflected = false;
break;
}
}
if reflected {
// same as above, adjust for 1-indexed task
return Some((None, Some(col + 1)));
}
col += 1;
}
None
}And then we can find the required sum and solve part 1:
fn symmetry_summary(symmetry: (Option<usize>, Option<usize>)) -> usize {
match symmetry {
(Some(row), None) => 100 * row,
(None, Some(col)) => col,
_ => unreachable!(),
}
}
pub fn p1(patterns: &Vec<Pattern>) -> usize {
patterns.iter().map(|p| symmetry_summary(find_symmetry(p, (None, None)).unwrap())).sum()
}Day 13 Part 2
The part 2 now requires us to check the symmetry for a case where some single bit is flipped. We also must ensure that we don’t accidentally return the previous symmetry that we used.
Flipping a bit in a binary number can be achieved with the help of a
bitwise XOR operation (^ in Rust).
Consider the previous example row:
101100110
We want to flip the first (leftmost) bit here. We know that the number is 9 bits long (for each row, the number
is length of columns long; for each column - length of rows long, so we don’t need to do any additional calculation
to know how much bits we have). We will need to xor this with 1 << 9 == 100000000
(see left shift):
101100110
xor 100000000
---------
res 001100110
Both << and ^ are very efficient operations. So, to solve the part 2 we need to do a couple simple modifications.
First, we need the find_symmetry function to ignore the previously found symmetry. We can pass an additional
argument to it to achieve it:
fn find_symmetry(
pattern: &Pattern,
prev_answer: (Option<usize>, Option<usize>),
) -> Option<(Option<usize>, Option<usize>)> {
let mut row = 0;
while row < pattern.rows.len() - 1 {
// previous code to find reflection
if reflected {
let candidate = (Some(row + 1), None);
if candidate != prev_answer {
return Some(candidate);
}
}
row += 1;
}
let mut col = 0;
while col < pattern.cols.len() - 1 {
// previous code to find reflection
if reflected {
// same as above, adjust for 1-indexed task
let candidate = (None, Some(col + 1));
if candidate != prev_answer {
return Some(candidate);
}
}
col += 1;
}
None
}
Second, we need to do flip single bits in each grid position. It’s important to flip the bit both in the row
and the column number, otherwise we won’t be able to use our existing find_symmetry logic!
fn find_unsmudged_symmetry(pattern: &Pattern) -> Option<(Option<usize>, Option<usize>)> {
let prev_answer = find_symmetry(pattern, (None, None)).unwrap();
for smudge_row in 0..pattern.rows.len() {
for smudge_col in 0..pattern.cols.len() {
let mut unsmudged_pattern = pattern.clone();
// we use bitwise xor to flip a corresponding bit located at (smudge_row, smudge_col)
let row_bit = pattern.cols.len() - smudge_col - 1;
let new_row_number = unsmudged_pattern.rows[smudge_row] ^ (1 << row_bit);
unsmudged_pattern.rows[smudge_row] = new_row_number;
let col_bit = pattern.rows.len() - smudge_row - 1;
let new_col_number = unsmudged_pattern.cols[smudge_col] ^ (1 << col_bit);
unsmudged_pattern.cols[smudge_col] = new_col_number;
match find_symmetry(&unsmudged_pattern, prev_answer) {
None => continue,
Some(new_symmetry) => {
return Some(new_symmetry);
}
}
}
}
None
}And then, the part 2 is solved:
pub fn p2(patterns: &Vec<Pattern>) -> usize {
patterns.iter().map(
|pattern| symmetry_summary(find_unsmudged_symmetry(pattern).unwrap())
).sum()
}
In all honestly, I don’t know if it would’ve been fast enough to do it with plain Vec<Vec<_>> grids.
But I’m happy with my solution and I think it’s pretty neat + a good example of using bitwise operators!
Day 14 in Julia: Not hard when you just have rotr90 in the stdlib :)
Looking at the task I had a strong sensation that we will need to tilt the platform to all other directions in the part 2, and it turned out to be correct :) I knew that Julia has useful matrix rotation functions in the standard library, so the language choice was easy. It’s not hard to write this stuff, but it’s not very fun.
As always, I’m using Pipe package and parsing is a delightful one-liner because of it
(I split it to another line for it to fit in the code block box, though):
parse_input(input) = (
@pipe input |> strip |> split(_, "\n") |> collect.(_) |> mapreduce(permutedims, vcat, _)
)This gives us the following matrix for the test input:
julia> test_input
10×10 Matrix{Char}:
'O' '.' '.' '.' '.' '#' '.' '.' '.' '.'
'O' '.' 'O' 'O' '#' '.' '.' '.' '.' '#'
'.' '.' '.' '.' '.' '#' '#' '.' '.' '.'
'O' 'O' '.' '#' 'O' '.' '.' '.' '.' 'O'
'.' 'O' '.' '.' '.' '.' '.' 'O' '#' '.'
'O' '.' '#' '.' '.' 'O' '.' '#' '.' '#'
'.' '.' 'O' '.' '.' '#' 'O' '.' '.' 'O'
'.' '.' '.' '.' '.' '.' '.' 'O' '.' '.'
'#' '.' '.' '.' '.' '#' '#' '#' '.' '.'
'#' 'O' 'O' '.' '.' '#' '.' '.' '.' '.'
To tilt it north, we will need to go column by column starting from the southernmost part (the last row).
Every time we encounter a round stone (O),
we increment the number of rocks we are carrying by one. Once we hit a cube-shaped rock (#), we deposit all
the rocks we are currently carrying behind it (we cannot carry more rocks than there are free spaces behind
the cube shaped rock). Once we reach the first row, we check the carrying value again, and deposit all rocks
that reached the first row.
function tilt_north(input)
tilted = fill('.', size(input))
for col = 1:size(tilted)[2]
carrying = 0
for row = (size(input)[1]):-1:1
if input[row, col] == '#'
tilted[row, col] = '#'
offset = 1
while carrying > 0
tilted[row+offset, col] = 'O'
carrying -= 1
offset += 1
end
elseif input[row, col] == 'O'
carrying += 1
end
end
offset = 1
while carrying > 0
tilted[offset, col] = 'O'
carrying -= 1
offset += 1
end
end
tilted
endSeeing it in action is very satisfying:
julia> tilt_north(test_input)
10×10 Matrix{Char}:
'O' 'O' 'O' 'O' '.' '#' '.' 'O' '.' '.'
'O' 'O' '.' '.' '#' '.' '.' '.' '.' '#'
'O' 'O' '.' '.' 'O' '#' '#' '.' '.' 'O'
'O' '.' '.' '#' '.' 'O' 'O' '.' '.' '.'
'.' '.' '.' '.' '.' '.' '.' '.' '#' '.'
'.' '.' '#' '.' '.' '.' '.' '#' '.' '#'
'.' '.' 'O' '.' '.' '#' '.' 'O' '.' 'O'
'.' '.' 'O' '.' '.' '.' '.' '.' '.' '.'
'#' '.' '.' '.' '.' '#' '#' '#' '.' '.'
'#' '.' '.' '.' '.' '#' '.' '.' '.' '.'
Also important to note that this function doesn’t mutate the input: we need to use it to remember where the
cube-shaped rocks are. So instead we create a new matrix filling it with . and then placing all the cube-shaped
rocks whenever we encounter them and depositing the round rocks that we are carrying on the aforementioned conditions.
We can then calculate the beam load and solve part 1:
function beam_load(input)
max_row = size(input)[1]
[max_row - pos[1] + 1 for pos in findall(x -> x == 'O', input)] |> sum
end
p1(input) = tilt_north(input) |> beam_loadDay 14 Part 2
For the part 2, we need to be able to tilt the platform in all direction, as we expected, and we will also need
to find a cycle - it’s obvious that the task doesn’t expect us to do 1_000_000_000 tilts, so it’s a reasonable
assumption that there will be a cycle that we can use to calculate this much faster than simulating all the tilts.
Let’s start with the full tilting around implementation. As mentioned, we can just use standard library
functions for rotating a matrix here: rotr90
is the one we need. Every time we rotate the matrix and use our tilt_north function, we will do the tilting necessary
and after three 90 degree rotations we do one more so we’ll be back 360 degrees - so we don’t need to do any additional
coordinate transformations, since we’ve come full circle. So, the cycle function is another one-liner
(again split on two lines for clarity):
cycle(input) = (
input |> tilt_north
|> rotr90 |> tilt_north
|> rotr90 |> tilt_north
|> rotr90 |> tilt_north
|> rotr90
)
Now we just need to do it until we find a cycle. We will need to remember where the cycle starts,
how long does it last, and what is the cycle_state we reach to avoid redoing the tilting:
function find_cycle(input)
prev, next, iters = Dict(), input, 0
while next ∉ keys(prev)
prev[next] = iters
next = cycle(next)
iters += 1
end
(prev[next], iters - prev[next], next)
endAnd then some basic modular arithmetic gives us solution for the part 2:
function p2(input)
(start, len, cycle_state) = find_cycle(input)
additional_moves = (1000000000 - start) % len
for _ = 1:additional_moves
cycle_state = cycle(cycle_state)
end
beam_load(cycle_state)
end
In my case, the cycle starts at iteration 115 and has a length of 42 iterations. 3 additional moves are needed.
This means, we just need to be able to do 115 + 42 + 3 = 160 full tilt-rotations to arrive at the answer.
For me, this takes ~0.046 seconds, which is much better than 287_500 seconds (~ 3 and 1/3 days) it would’ve taken
to brute force :)
If you enjoyed this content, you can sponsor me on Github to produce more videos / educational blog posts.
And if you're looking for consulting services, feel free to contact me .