Point of Incidence

Advent of Code 2023 Day 13

Part 1

Taking a good hard look at my skills

A mirror pun, get it?

This is going to be a complex solution, given how I understand the problem.

Examining some patterns very closely

The first example:

#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

The first likely candidate for reflection point I saw is between these two rows:

##......#
##......#

However, as the view widens:

#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.

The top line and the bottom line are off by one: the top-left cell's #.

But this demonstrates an important use case to handle:

• There are likely to be multiple places in each pattern where two adjacent rows or columns are identical

And only one of them must be a true reflection, right?

The first pattern in my puzzle input had me concerned for a bit:

   ><
 ######.#.#.
 .#..#...###
 .####....##
 .####..###.
 #....##.##.
 ......#.###
 #.##.#.#.##
 .####.#..#.
 ..##....##.
v##..##.....v
^##..##.....^
 ..##....##.
 .####.#..#.
 #.##.#.#.##
 ......#.###
 #....##..#.
 .####..###.
   ><

Is the true reflection on the column or the row?

The column meets the left edge after two expanding twice.

It's reflections are all solid.

The row continues on in both directions for a while.

It all looks solid...

...until here, where the bottom line has only a single character being off:

         !
 #....##.##.
 ......#.###
 #.##.#.#.##
 .####.#..#.
 ..##....##.
v##..##.....v
^##..##.....^
 ..##....##.
 .####.#..#.
 #.##.#.#.##
 ......#.###
 #....##..#.
         !

It took me a while to notice this.

But once I did, I calmed down.

Because it was a small but important confirmation that I can trust there will only ever be one true reflection.

Even on an edge!

Like in this pattern, also from my input:

.#.####.#..#.#.#.
#...#.###...###.#
..#..#.#.#..#.##.
..#..#.#.#..#.#..
#...#.###...###.#
.#.####.#..#.#.#.
..#.##..###.....#
.###..#.....#####
.###....#.....###
.....##.#...###.#
.###.#...#.##.##.
###...###.#.###..
###...###.#.###..

The only place I can visually find two adjacent rows or columns is the rows at the very bottom, with the point of reflection being between them.

Is that correct?

Rows 3 and 4 are off by one character.

And no adjacent columns are identical.

So, it looks like the reflection point can be right up against an edge.

Well, this is all enough to start thinking about how I might programmatically find the point of reflection.

First algorithm: find all identical adjacent rows and columns in a pattern

How I'm thinking I'll do this for rows:

For each row except the last
  Check whether the current row is identical to the next
    If it is, add them to a list of matches

How I'll do this for columns:

For each character in the first row except the last
  Generate two strings from the characters in each row matching the index of the current and next character
  Check whether they are identical
    If they are, add them to a list of matches

For the example:

#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

I anticipate having these lists:

rows: [[2,3]]
cols: [[4,5]]

I'll 'code this up' before continuing with the fun part of exploring subsequent rows or columns for pairs.

My algorithm in JavaScript:

let rows = [], cols = []
for (let i = 0; i < pattern.length - 1; i++) {
  if (pattern[i] == pattern[i + 1]) {
    rows.push([i, i+1])
  }
}
for (let j = 0; j < pattern[0].length - 1; j++) {
  let colA = pattern.map(line => line[j]).join('')
  let colB = pattern.map(line => line[j + 1]).join('')
  if (colA == colB) {
    cols.push([j, j+1])
  }
}

Works as expected!

Now for the fun - and harder? - part...

Programmatically walking away from each mirror

For this part, I dove straight into the code.

And it got complicated fast!

First, I realized it would be easier to store all matches in a single array, matches. Rows and columns would be designated by the new first item:

  let matches = []
  for (let i = 0; i < pattern.length - 1; i++) {
    if (pattern[i] == pattern[i + 1]) {
      matches.push(['row', i, i+1])
    }
  }
  for (let j = 0; j < pattern[0].length - 1; j++) {
    let colA = pattern.map(line => line[j]).join('')
    let colB = pattern.map(line => line[j + 1]).join('')
    if (colA == colB) {
      matches.push(['col', j, j+1])
    }
  }

With this change, I could use a switch statement to decide which path to walk down:

let winner = matches.map(m => {
  switch (m[0]) {
    case 'row':
      // walk down the rows
      break;
    case 'col':
      // walk down the cols
      break;

From here, each case got pretty lengthy. But it should be understandable.

case 'row':
  let top = m[1]
  let bottom = m[2]
  let height = pattern.length
  while (pattern[top] == pattern[bottom]) {
    top--
    bottom++
  }
  if (top < 0 || bottom == height) {
    return true
  } else {
    return false
  }

What's it doing?

• It starts at the two identical rows
• As long as the row strings are identical...
• ...It moves to the next row up and the next row down
• Once there is a mismatch...
• ...as long as one of the rows is out of bounds
• ...we have a winner
• Otherwise, it found a mismatch too early and thus a loser candidate for the reflection

I do the same thing for columns. The code is longer because of the need for generating a string from each character in the appropriate columns:

case 'col':
  let left = m[1]
  let right = m[2]
  let width = pattern[0].length
  let colA = pattern.map(line => line[left]).join('')
  let colB = pattern.map(line => line[right]).join('')
  while (colA == colB) {
    left--
    right++
    colA = pattern.map(line => line[left]).join('')
    colB = pattern.map(line => line[right]).join('')
  }
  if (left < 0 || right == width) {
    return true
  } else {
    return false
  }

With a few key console.log() statements in place, I see this when running it on the example input's two patterns:

[ [ 'row', 2, 3 ], [ 'col', 4, 5 ] ]
0 5
0 9
[ false, true ]
[ [ 'row', 3, 4 ], [ 'col', 2, 3 ], [ 'col', 6, 7 ] ]
0 7
1 4
5 8
[ true, false, false ]

Confirmed:

• It found all the right candidates for reflection
• Both numbers are equidistant from the starters
• There is only one true item in each array

An edge case I anticipated

What if the reflection is smack-dab in the middle?

#...#
#.#.#
#.#.#
#...#

..#..
.#.#.
#.#.#
#.#.#
.#.#.
..#..

As I regrettably expected, my algorithm never terminates its while loop.

Why not?

Because undefined is equal to undefined.

And when attempting to access an out-of-bounds index of an array, JavaScript returns undefined.

How do I account for this?

• Another condition in my while loop!

For rows:

while (
  pattern[top] == pattern[bottom] 
  && (
    pattern[top] !== undefined 
    || pattern[bottom] !== undefined
  )
) { }

For columns:

while (
  colA == colB 
  && (
    !colA.includes('undefined') 
    || !colB.includes('undefined')
  )
) { }

This revised code successfully terminates the while loop and still identifies the correct reflection along a row.

Could the reflection ever be in the middle?

If it were in the middle, wouldn't that mean the reflection would be the same for the column and the row?

And if that were the case, it would break the rule of the puzzle.

Hmm.

Maybe my algorithm is now accounting for a non-use case.

Oh well. At least I know I can count on it to identify such a use case.

Time to test on a few of my puzzle input patterns to feel extra confident it will generate the correct answer.

Testing on some more sample patterns

######.#.#.
.#..#...###
.####....##
.####..###.
#....##.##.
......#.###
#.##.#.#.##
.####.#..#.
..##....##.
##..##.....
##..##.....
..##....##.
.####.#..#.
#.##.#.#.##
......#.###
#....##..#.
.####..###.

It found both possible reflections and correctly said the column was the winner.

..#.#.#
...#.##
##.#..#
##.#...
...#.##
..#.#.#
####..#
##.#.#.
####..#
..#####
##..###

It found the only possible reflection and correctly said it was the winner.

....#.##.#...
#......#.#...
##...###.....
##...###.....
#....#.#.#...
....#.##.#...
.#######.....
.#..##.#.##.#
.##.##...##.#
.######.####.
.#.##....#.#.
.#.##....#.#.
.######.####.
.##.##...##.#
.#..##.#.##.#
.#######.....
....#.##.#...

It found both possible reflections and correctly said the lower row was the winner.

I'm feeling good about this.

Time to calculate the summary!

Summarizing the pattern notes

I need the index of the winning reflection:

let reflection = matches[winner.indexOf(true)]

Similar to above, I'll switch on whether it is a row or col:

switch (reflection[0]) {
  case 'row':
    // add rows above and multiply by 100
    break;
  case 'col':
    // add columns to the left
    break;
}

Lastly, I'll increment my accumulating sum by the appropriate amounts:

switch (reflection[0]) {
  case 'row':
    sum += (reflection[1] + 1) * 100
    break;
  case 'col':
    sum += reflection[1] + 1
    break;
}

Running and checking

When I run it on the example input, I generate the correct answer!

And when I run it on my puzzle input, I generate the correct answer, too!

Woohoo!!!

It feels great when hard work and triple-checking pays off.

Part 2

What I read: check every pixel!

After finishing Part 1, I am so ready to move on from this puzzle.

Honestly, I was hoping Part 2 would seem so unachievable that I could call it quits and celebrate earning one gold star.

But this...seems doable!

Ugh! I mean...yay!

The important rule

locate and fix the smudge that causes a different reflection line to be valid

That's critical, because it may be possible that changing a pixel still results in the same reflection line being valid. Thus, that pixel is not the smudge.

At least that's how I understand it.

Writing a refactored and expanded algorithm

Cloning a pattern

Each pattern is a multiline string and, thus, immutable.

So, any operation I perform on the string to make something new will not change the original string, as long as I don't overwrite the variable storing it.

My code can be as simple as:

let clone = pattern.split('\n').map(line => line.split(''))

I now have a 2D array of characters in a grid, ready for one to be changed.

Toggling each character's opposite

I will need to check every permutation of the pattern where a single different character is toggled between it's original state and its opposite (. or #).

Queue the nested for loop:

for (let row = 0; row < clone.length; row++) {
  for (let col = 0; col < clone[row].length; col++) {
    clone[row][col] = clone[row][col] == '#' ? '.' : '#'
  }
}

Reassembling the new pattern

The for loop leaves me with nested arrays of 1-character strings. I want an array of strings.

let newPattern = clone.map(line => line.join(''))

Up 'til now, altogether

I overlooked how cloning should happen inside the for loop, since it must happen on each character.

After some head-scratching minutes, I saw all permutations printed:

pattern = pattern.split('\n')  
for (let row = 0; row < pattern.length; row++) {
  for (let col = 0; col < pattern[row].length; col++) {
    let clone = pattern.slice()
      .map(line => line.split(''))
    clone[row][col] = clone[row][col] == '#' ? '.' : '#'
    clone = clone.map(line => line.join(''))
  }
}

Wrapping code in functions

In Part 1 I just had to find possible reflections and a winner once. Now I'll have to do it thousands of times:

• On the original pattern to identify the smudged reflection
• On each de-smudged permutation

Does a pattern have two adjacent identical rows or columns?

function findMatches(stamp) {
  let matches = []
  // find matching rows
  // find matching columns
  return matches.length ? matches : null
}

Does the pattern have any winning reflections?

function findWinner(stamp, matches) {
  // walk along the vertical or horizontal
  return matches[winner.indexOf(true)]
}

Incorporating the functions into the for cloning loop

Several nested if statements later, and it at least works:

let matches = findMatches(clone)
if (matches) {
  let winner = findWinner(clone, matches)
  if (winner) {
    if (winner.join('') !== pattern.join('')) {
      // calculate the proper sum
      }
    }
  }
}

Fast-forward: about the last few hours

When I ran my algorithm on the first example input, I got two possible smudges.

After very close study, both seemed valid.

But the author clearly states:

every mirror has exactly one smudge: exactly one . or # should be the opposite type

So how could I have found two??!

Well, a lot of reddit-scavenging later, and one user perfectly summarized my internal logic problem:

There are two places where you could fix the smudge since it's a disagreement between two points and you could turn a . into a # or vice versa, but that still counts as fixing one smudge.

They are absolutely right.

How could I not see that?

My algorithm was even correctly generating the same new reflection for each smudge.

Fast-forward: about the last few hours again

With that working, I ran my algorithm on the example and generated the correct answer for Part 2.

I ran it on my puzzle input and encountered an error.

After inspecting the pattern, I discovered a use case I clearly overlooked:

• When - after removing the smudge - there are two winners: the original reflection and the new reflection

My already over-complicated algorithm only accounted for a single potential match to be true.

So, I had to account for two matches to be true...and rectify that by identifying the match that isn't the original pattern's winner.

Making this adjustment had my brain swinging between confidence and confusion as I repeatedly scanned the console's logs for clues as to what I might be doing wrong.

I was able to generate the correct summarized note (a.k.a. sum) for the pattern that revealed this use case.

Then I ran my algorithm on my puzzle input again.

A new pattern was halting it.

This caused me to double-check my work and fix another gap in my algorithm.

Eventually, I resolved the issue by changing one number that incorrectly assumed an array length of 1 (an array containing a 3-element array) and should have assumed a length of 3 (that same 3-element array, but not nested).

Making this change generated the correct answer for this latest pattern.

Crossing the finish line

I ran my program once more on my puzzle input.

It generated no errors.

It generated a number.

That number was the correct answer!!!

What a rush!

This puzzle felt like it would never end.

So much troubleshooting.

So much unnecessary confusion.

But now it's over. I solved it.

And I'm sure the next 11 days will be filled with more puzzles that present even more difficult challenges.

I'm so glad I stuck it out and earned two gold stars today.