[Day 13] Point of Incidence // Advent of Code 2023 (Python)

Point of Incidence

Advent of Code
With your help, the hot springs team locates an appropriate spring which launches you neatly and precisely up to the…adventofcode.com

---

Part One

With your help, the hot springs team locates an appropriate spring which launches you neatly and precisely up to the edge of Lava Island.

There’s just one problem: you don’t see any lava.

You do see a lot of ash and igneous rock; there are even what look like gray mountains scattered around. After a while, you make your way to a nearby cluster of mountains only to discover that the valley between them is completely full of large mirrors. Most of the mirrors seem to be aligned in a consistent way; perhaps you should head in that direction?

As you move through the valley of mirrors, you find that several of them have fallen from the large metal frames keeping them in place. The mirrors are extremely flat and shiny, and many of the fallen mirrors have lodged into the ash at strange angles. Because the terrain is all one color, it’s hard to tell where it’s safe to walk or where you’re about to run into a mirror.

You note down the patterns of ash (.) and rocks (#) that you see as you walk (your puzzle input); perhaps by carefully analyzing these patterns, you can figure out where the mirrors are!

For example:

#.##..##.
..#.##.#.
##…#
##…#
..#.##.#.
..##..##.
#.#.##.#.

#…##..#
#…#..#
..##..###
#####.##.
#####.##.
..##..###
#…#..#

To find the reflection in each pattern, you need to find a perfect reflection across either a horizontal line between two rows or across a vertical line between two columns.

In the first pattern, the reflection is across a vertical line between two columns; arrows on each of the two columns point at the line between the columns:

123456789

<
#.##..##.
..#.##.#.
##…#
##…#
..#.##.#.
..##..##.
#.#.##.#.
<
123456789

In this pattern, the line of reflection is the vertical line between columns 5 and 6. Because the vertical line is not perfectly in the middle of the pattern, part of the pattern (column 1) has nowhere to reflect onto and can be ignored; every other column has a reflected column within the pattern and must match exactly: column 2 matches column 9, column 3 matches 8, 4 matches 7, and 5 matches 6.

The second pattern reflects across a horizontal line instead:

1 #…##..# 1
2 #…#..# 2
3 ..##..### 3
4v#####.##.v4
5^#####.##.^5
6 ..##..### 6
7 #…#..# 7

This pattern reflects across the horizontal line between rows 4 and 5. Row 1 would reflect with a hypothetical row 8, but since that’s not in the pattern, row 1 doesn’t need to match anything. The remaining rows match: row 2 matches row 7, row 3 matches row 6, and row 4 matches row 5.

To summarize your pattern notes, add up the number of columns to the left of each vertical line of reflection; to that, also add 100 multiplied by the number of rows above each horizontal line of reflection. In the above example, the first pattern’s vertical line has 5 columns to its left and the second pattern’s horizontal line has 4 rows above it, a total of 405.

Find the line of reflection in each of the patterns in your notes. What number do you get after summarizing all of your notes?

---

A mirror maze?! I have always loved them since childhood!

Let’s understand the problem! We are given a pattern of ash (.) and rocks (#) and we need to figure out a line of mirrors which can be either be in between rows or columns casting a perfect reflection in our pattern!

Let’s study the example with a visualization, for the given input:

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

We can observe that the line of reflection is in b/w 5th and 6th column and our 1st column can be ignored!

Pattern 1

Similarly, for another example:

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

We can see that line of reflection is in b/w 4th and 5th row and our 1st row can be ignored!

Pattern 2

Now, the puzzle wants us to summarize these patterns and add up:

• the number of columns to the left of each vertical line of reflection
• add 100 multiplied by the number of rows above each horizontal line of reflection

So, for the given example, the answer becomes:

5 (pattern 1) + 4 (pattern 2) * 100 = 405

This is pretty interesting! My mind is trying to wander toward the Palindrome approach, especially for even numbers, but let me first write some test code for the base case given above!

💡 A quick analysis of puzzle input shows that we will have multiple patterns to process, so we will structure our code accordingly!

Let’s write code now, as mentioned, my initial idea is to just follow the naive palindrome approach, where I will try to compare ch[i] == ch[i-1] and will do a fan out approach to go both ways till we run out of bounds:

Now we can adapt the same approach to go row by row, and then if not found, we go column by column and then return the point as per the calculation for horizontal line v/s vertical line as per the puzzle.

.

.

Few debugging sessions later!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_13/point_of_incidence.py"
✅ summarize_pattern passed

[Done] exited with code=0 in 0.065 seconds

This is a bit bruteforce approach, but seems pretty fast for 2 patterns, 0.065 seconds, let’s load up our puzzle input and see how it runs as we seem to only have 100 patterns!

I am sure there will be a nutty edge case somewhere in here!

Let’s run this! 🤞

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_13/point_of_incidence.py"
❗️ Summarizing all patterns in Part 1: XXXXXX

[Done] exited with code=0 in 0.051 seconds

Woah! We have an answer in just 0.051 seconds! 🤯

Let’s input this in the answer box and….

👯‍♀️👯‍♀️👯‍♀️

Correct in first try and with an amazing runtime! Though I am sure as soon as I click on Part Two, it’s going to wreck our code! 🤓

Here’s our raw code till now, we will optimise it in Part 2, like always:

# Day 13 - Point of Incidence

from enum import Enum

class Mode(Enum):
    ROW = "row"
    COLUMN = "column"

def is_perfect_reflection(prev, next, pattern, mode):
    if mode == Mode.ROW:
        while prev >= 0 and next < len(pattern):
            if pattern[prev] != pattern[next]:
                return False
            prev -= 1
            next += 1

        return True

    elif mode == Mode.COLUMN:
        while prev >= 0 and next < len(pattern[0]):
            for i in range(len(pattern)):
                if pattern[i][prev] != pattern[i][next]:
                    return False
            prev -= 1
            next += 1

        return True

    raise Exception("Invalid mode")

def find_point_of_reflection(pattern, mode):
    if mode == Mode.ROW:
        for i in range(1, len(pattern)):
            if pattern[i-1] == pattern[i]:
                if is_perfect_reflection(i-1, i, pattern, Mode.ROW):
                    return i

    if mode == Mode.COLUMN:
        for j in range(1, len(pattern[0])):
            prev_col, next_col = [], []
            for i in range(0, len(pattern)):
                prev_col.append(pattern[i][j-1])
                next_col.append(pattern[i][j])
            if prev_col == next_col:
                if is_perfect_reflection(j-1, j, pattern, Mode.COLUMN):
                    return j

def analyze_pattern(pattern):
    pattern_grid = [list(row) for row in pattern.strip().split("\n")]

    # Find the point of reflection row by row
    point = find_point_of_reflection(pattern_grid, Mode.ROW)
    if point:
        return point * 100

    # Find the point of reflection column by column
    point = find_point_of_reflection(pattern_grid, Mode.COLUMN)
    if point:
        return point

    raise Exception("No point of reflection found")

def summarize_patterns(patterns):
    sum = 0
    for pattern in patterns.split("\n\n"):
        sum += analyze_pattern(pattern)

    return sum

def part_one():
    with open("day_13/input.txt", "r") as f:
        patterns = f.read()
    sum = summarize_patterns(patterns)

    print(f"❗️ Summarizing all patterns in Part 1: {sum}")

def test_summarize_patterns():
    patterns = """#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#"""
    sum = summarize_patterns(patterns)
    assert sum == 405, f"Expected 405, got {sum}"
    print("✅ summarize_pattern passed")

if __name__ == "__main__":
    test_summarize_patterns()
    part_one()

---

Part Two

You resume walking through the valley of mirrors and — SMACK! — run directly into one. Hopefully nobody was watching, because that must have been pretty embarrassing.

Upon closer inspection, you discover that every mirror has exactly one smudge: exactly one . or # should be the opposite type.

In each pattern, you’ll need to locate and fix the smudge that causes a different reflection line to be valid. (The old reflection line won’t necessarily continue being valid after the smudge is fixed.)

Here’s the above example again:

#.##..##.
..#.##.#.
##…#
##…#
..#.##.#.
..##..##.
#.#.##.#.

#…##..#
#…#..#
..##..###
#####.##.
#####.##.
..##..###
#…#..#

The first pattern’s smudge is in the top-left corner. If the top-left #were instead ., it would have a different, horizontal line of reflection:

1 ..##..##. 1
2 ..#.##.#. 2
3v##…#v3
4^##…#^4
5 ..#.##.#. 5
6 ..##..##. 6
7 #.#.##.#. 7

With the smudge in the top-left corner repaired, a new horizontal line of reflection between rows 3 and 4 now exists. Row 7 has no corresponding reflected row and can be ignored, but every other row matches exactly: row 1 matches row 6, row 2 matches row 5, and row 3 matches row 4.

In the second pattern, the smudge can be fixed by changing the fifth symbol on row 2 from . to #:

1v#…##..#v1
2^#…##..#^2
3 ..##..### 3
4 #####.##. 4
5 #####.##. 5
6 ..##..### 6
7 #…#..# 7

Now, the pattern has a different horizontal line of reflection between rows 1 and 2.

Summarize your notes as before, but instead use the new different reflection lines. In this example, the first pattern’s new horizontal line has 3 rows above it and the second pattern’s new horizontal line has 1 row above it, summarizing to the value 400.

In each pattern, fix the smudge and find the different line of reflection. What number do you get after summarizing the new reflection line in each pattern in your notes?

---

And…

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

We are back to permutations and combinations! 🪦

💭 Carrying on with our brute force approach, since our code was pretty blazing fast, we can extend our solution by adding some extra steps and loops.

Introducing ‘smudges’, where exactly one character in each pattern is incorrect and needs to be flipped to find a new line of reflection. We can follow these steps:

1. Identify the Smudge: Iterate through each cell of the pattern.
   a. For each cell, flip its value (from . to # or vice versa)
   b. then check if this change results in a valid reflection line different from the original.
   c. if yes, this is the smudge we need to fix, else continue loop
2. Summarize the Patterns: Calculate the summary based on the new reflection lines.

Let’s try this?

💡This approaches hinges upon the fact that puzzle states, there’s exactly 1 smudge in each pattern!

❗️Edge case: We need to ensure, that everytime we find a new reflection point, we need to compare it with original reflection point along with the mode, as sometimes the value can be same, but it can be for rows and columns respectively.
(new_reflection_point, mode) != (original_reflection_point, original_mode)

Tons of debugging later!

Masterpiece!

Let’s see if it works for our new test case?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_13/point_of_incidence.py"
✅ summarize_pattern_with_smudges passed

[Done] exited with code=0 in 0.071 seconds

✅ in just 0.071 seconds! This gives me hope!

Let’s run it for the puzzle input?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/tempCodeRunnerFile.python"
‼️ Summarizing all patterns in Part 2: XXXXX

[Done] exited with code=0 in 0.281 seconds

Done! Let’s see if our answer is correct? 👀

And…

🥁

Here’s our code with a bruteforce approach, works pretty quick on my M1 Macbook Pro. I might come back later to solve this in a more novel way, but since I am already running behind in AdventOfCode, I will just move on! 😃

# Day 13 - Point of Incidence

from enum import Enum
import itertools

class Mode(Enum):
    ROW = "row"
    COLUMN = "column"

class MirrorPatternAnalyzer:
    def __init__(self, pattern):
        self.pattern = [list(row) for row in pattern.strip().split("\n")]

    @staticmethod
    def flip_char(char):
        return "#" if char == "." else "."

    def is_perfect_reflection(self, index, mode):
        if mode == Mode.ROW:
            prev, next = index - 1, index
            while prev >= 0 and next < len(self.pattern):
                if self.pattern[prev] != self.pattern[next]:
                    return False
                prev -= 1
                next += 1
            return True

        elif mode == Mode.COLUMN:
            prev, next = index - 1, index
            while prev >= 0 and next < len(self.pattern[0]):
                if any(
                    self.pattern[row][prev] != self.pattern[row][next]
                    for row in range(len(self.pattern))
                ):
                    return False
                prev -= 1
                next += 1
            return True

        raise ValueError("Invalid mode")

    def find_point_of_reflection(self, mode):
        range_to_check = range(
            1, len(self.pattern) if mode == Mode.ROW else len(self.pattern[0])
        )
        for i in range_to_check:
            if self.is_perfect_reflection(i, mode):
                return i
        return None

    def try_fix_smudge_and_find_reflection(
        self, original_reflection_point, original_mode
    ):
        for i in range(len(self.pattern)):
            for j in range(len(self.pattern[i])):
                self.pattern[i][j] = MirrorPatternAnalyzer.flip_char(self.pattern[i][j])
                for mode in [Mode.ROW, Mode.COLUMN]:
                    new_reflection_point = self.find_point_of_reflection(mode)
                    if new_reflection_point and (new_reflection_point, mode) != (
                        original_reflection_point,
                        original_mode,
                    ):
                        return new_reflection_point, mode
                self.pattern[i][j] = MirrorPatternAnalyzer.flip_char(self.pattern[i][j])
        return original_reflection_point, original_mode

    def analyze(self, with_smudge=False):
        for mode in [Mode.ROW, Mode.COLUMN]:
            reflection_point = self.find_point_of_reflection(mode)
            if reflection_point is not None:
                if with_smudge:
                    (
                        new_reflection_point,
                        new_mode,
                    ) = self.try_fix_smudge_and_find_reflection(reflection_point, mode)
                    if new_mode == Mode.ROW:
                        return new_reflection_point * 100
                    else:
                        return new_reflection_point
                else:
                    return (
                        reflection_point * 100 if mode == Mode.ROW else reflection_point
                    )
        raise Exception("No valid reflection line found")

def summarize_patterns(patterns, with_smudges=False):
    total_sum = 0
    for i, pattern in enumerate(patterns.split("\n\n")):
        analyzer = MirrorPatternAnalyzer(pattern)
        total_sum += analyzer.analyze(with_smudge=with_smudges)
    return total_sum

def part_one():
    with open("day_13/input.txt", "r") as f:
        patterns = f.read()
    sum = summarize_patterns(patterns)

    print(f"❗️ Summarizing all patterns in Part 1: {sum}")

def test_summarize_patterns():
    patterns = """#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#"""
    sum = summarize_patterns(patterns)
    assert sum == 405, f"Expected 405, got {sum}"
    print("✅ summarize_pattern passed")

def part_two():
    with open("day_13/input.txt", "r") as f:
        patterns = f.read()
    sum = summarize_patterns(patterns, with_smudges=True)
    print(f"‼️ Summarizing all patterns in Part 2: {sum}")

def test_summarize_patterns_with_smudges():
    patterns = """#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#"""

    sum = summarize_patterns(patterns, with_smudges=True)
    assert sum == 400, f"Expected 400, got {sum}"
    print("✅ summarize_pattern_with_smudges passed")

if __name__ == "__main__":
    test_summarize_patterns()
    part_one()

    test_summarize_patterns_with_smudges()
    part_two()

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Well, here’s my attempt to solve all 25 problems of…
Well, here’s my attempt to solve all 25 problems of Advent of Code 2023 with Python! 🎄 - GitHub …github.com