It’s Thanksgiving Week here in the US, and we’re just a few days away from the start of the Advent of Code 2024. However, I’m still catching up with last year’s problems, so I’ll keep writing and posting about them.
Day 13 sets us on an island that is supposed to be covered in lava, but is actually covered in ash and rock. And mirrors, which make moving around tricky. Your task is to figure out where the mirrors are by checking for reflections.
As always, head to the problem description for a full rundown, but in general, you are given a list of patterns you see, and you have to find out where the line of symmetry is in the pattern. It may be a vertical line or a horizontal line, but there is a line there somewhere that each pattern reflects around.
Once you find the line of symmetry, you do a calculation on it and add them all up to give you a final answer.
Approach
This one seemed simple enough, but Rust complicated it for me. Or rather, I complicated it unnecessarily. I wound up rewriting the code to make Part 2 work.
Part 1
You store each pattern of ash (.) and rock (#) in a Vec<Vec<char>> to make finding and indexing easier. Then, you start checking columns and rows looking for where the reflection happens. As soon as you find one (there is only one in each pattern), you do the calculation, like so:
// Find a mirrored column
if let Some(col) = find_mirrored_column(&pattern, 0){
sum += col;
// Find a mirrored row
} else if let Some(row) = find_mirrored_row(&pattern, 0){
sum += 100*row;
}
i += 1;So how do you find where the reflection happens? As an example, here’s the find_mirrored_column() function:
fn find_mirrored_column(pattern: &Vec<Vec<char>>, diff:usize) -> Option<usize>{
for c in 0..pattern[0].len()-1{
if col_diff(&pattern, c, c+1) <= diff {
if check_col(&pattern, c, diff){
return Some(c+1);
}
}
}
None
}You walk through each column pair, c and c+1, and use col_diff() to ensure they are identical. The col_diff() function returns the number of differences between the two columns — if the differences between them are not bigger than diff, then this may be the column you want. For Part 1, diff=0, because you need an exact match.
Here’s col_diff() which returns the number of differences between the two columns:
fn col_diff(pattern: &Vec<Vec<char>>, c1: usize, c2: usize) -> usize{
let mut d = 0;
for r in 0..pattern.len(){
if pattern[r][c1] != pattern[r][c2]{
d += 1
}
}
d
}However, this might not be the column you want — remember that the reflection needs to be from the line of reflection to the edge of the mirror. That’s where check_col() comes in — it makes sure the other columns around this possible line of reflection are similarly mirrored:
fn check_col(pattern: &Vec<Vec<char>>, c: usize, diff:usize) -> bool{
let mut c1 = c;
let mut c2 = c+1;
while c1>=0 && c2<pattern[0].len(){
if col_diff(pattern, c1, c2) > diff{ return false; }
if c1>0 { c1-=1; c2+=1; }
else { break; }
}
true
}Note the if c1>0 check — this is necessary because you’re using unsigned numbers. If this weren’t there, you might underflow and panic when c1 == 0.
If this checks out, then you know this column is the line of reflection, and move on. There are similar helper functions for row checking — take a look at my code for the full breakdown.
Part 2
The complication with part 2 is that there is an unspecified smudge on every mirror. Whether the smudge mimics ash or a rock, and where it is on the mirror, is unknown. Now you need to find a new axis of symmetry on the mirror, knowing there is a smudge somewhere.
The key here is new — the old axis may be valid still, but the new one is the one you want now.
Here’s my original thinking on this:
So here’s what I think I need to do:
- For part 1, save the axis we found — a tuple of R or C and the number of the row or column
- Check each horizontal and vertical axis
- Is the difference between the two rows or columns off by one?
- Is it the one we found before?
- If so, keep looking
- Else, return the tuple as R or C and the number
- Is the difference between the two rows or columns off by one?
I need to rewrite the part 1 code to store the initial axis somewhere.
I also need to rewrite the code which checks for the mirror axis — or at least duplicate it for part 2. It needs to check that whatever we find, it’s not the one we originally found.
Then I saw the problem — not only do I need to check if the lines at the axis of symmetry differ by zero or one char, but I need to check that all the lines radiating out also differ y zero or one chars…
So now I should rewrite the whole thing to use the Vec<char>
However, no battle plan survives contact with the enemy, and after some implementation issues, what I actually did was this.
I did need to track where the original line of reflection was for each pattern, since it would be different for part 2. So I introduced reflections, a Vec<(char, usize)> to store the original line of symmetry from part 1:
// Find a mirrored column
if let Some(col) = find_mirrored_column(&pattern, 0){
reflections.push(('C', col));
sum += col;
// Find a mirrored row
} else if let Some(row) = find_mirrored_row(&pattern, 0){
reflections.push(('R', row));
sum += 100*row;
}
i += 1;Then, I need to modify the way I checked for a line of symmetry. Since the smudge could be anywhere, all of the row and column checking code needs to look for a one-off match. I also have to check if the line of reflection found was the same as part 1, and ignore it if so.
In reality, I didn’t really modify anything — I rewrote the whole thing. You can drill back into the git history to see how bad the original was.
One thing to call out is the new find_mirrored_column2() function, which handles checking whether the line of symmetry was the same as previously found:
fn find_mirrored_column2(pattern: &Vec<Vec<char>>, diff:usize, prev: (char, usize)) -> Option<usize>{
for c in 0..pattern[0].len()-1{
if col_diff(&pattern, c, c+1) <= diff && prev != ('C', c+1) {
if check_col(&pattern, c, diff){
return Some(c+1);
}
}
}
None
}The && prev != ('C', c+1) was added to ignore the any previously found line of symmetry. This call also set diff=1 so I was tolerant of any differences in mirrored lines to account for a smudge.
Summary
This one took me a while — you can see my code here, and dig into the git history for the gory details.
My original approach created strings out of each column and row for comparison, which was overly complicated and failed utterly when part 2 was revealed. The rewrite did straight comparisons in the Vec which allowed me to introduce a diff parameter for part 2. I also had to store the part 1 results, which is unusual for me, but always seems to appear somewhere in the AoC.