[Day 14] Parabolic Reflector Dish // Advent of Code 2023 (Python)

Parabolic Reflector Dish (via DALL-E 3)

Advent of Code
You reach the place where all of the mirrors were pointing: a massive parabolic reflector dish attached to the side of…adventofcode.com

---

Part One

You reach the place where all of the mirrors were pointing: a massive parabolic reflector dish attached to the side of another large mountain.

The dish is made up of many small mirrors, but while the mirrors themselves are roughly in the shape of a parabolic reflector dish, each individual mirror seems to be pointing in slightly the wrong direction. If the dish is meant to focus light, all it’s doing right now is sending it in a vague direction.

This system must be what provides the energy for the lava! If you focus the reflector dish, maybe you can go where it’s pointing and use the light to fix the lava production.

Upon closer inspection, the individual mirrors each appear to be connected via an elaborate system of ropes and pulleys to a large metal platform below the dish. The platform is covered in large rocks of various shapes. Depending on their position, the weight of the rocks deforms the platform, and the shape of the platform controls which ropes move and ultimately the focus of the dish.

In short: if you move the rocks, you can focus the dish. The platform even has a control panel on the side that lets you tilt it in one of four directions! The rounded rocks (O) will roll when the platform is tilted, while the cube-shaped rocks (#) will stay in place. You note the positions of all of the empty spaces (.) and rocks (your puzzle input). For example:

O…#…
O.OO#…#
…##…
OO.#O…O
.O…O#.
O.#..O.#.#
..O..#O..O
…O..
#…###..
#OO..#…

Start by tilting the lever so all of the rocks will slide north as far as they will go:

OOOO.#.O..
OO..#…#
OO..O##..O
O..#.OO…
…#.
..#…#.#
..O..#.O.O
..O…
#…###..
#…#…

You notice that the support beams along the north side of the platform are damaged; to ensure the platform doesn’t collapse, you should calculate the total load on the north support beams.

The amount of load caused by a single rounded rock (O) is equal to the number of rows from the rock to the south edge of the platform, including the row the rock is on. (Cube-shaped rocks (#) don’t contribute to load.) So, the amount of load caused by each rock in each row is as follows:

OOOO.#.O.. 10
OO..#…# 9
OO..O##..O 8
O..#.OO… 7
…#. 6
..#…#.# 5
..O..#.O.O 4
..O… 3
#…###.. 2
#…#… 1

The total load is the sum of the load caused by all of the rounded rocks. In this example, the total load is 136.

Tilt the platform so that the rounded rocks all roll north. Afterward, what is the total load on the north support beams?

---

Cool! Let’s review the problem in terms of chronology and we shall break down what needs to be done to get our answer?

We have 2 types of rocks:

• # Cube shape rocks, that stay in place
• O Rounded rocks, that rolls!

Given an initial state of platform represented by a 2D matrix, we need to ensure that the north side beam can handle the load if we start to tilt the platform, so we can need to calculate the state of platform when it is tilted towards North direction!

Let’s see a quick viz:

We can observe how all O rocks have moved along their columns towards North while # have stayed put.

And then, base case allows us to calculate the load bearing capacity of the north support beam by sum(number of "O” rocks * number of rows from the rock to the south edge of the platform), like:

So, we need to write code in 2 parts:

1. To generate the north_tilted state
2. To calculate the total load on north beam

But first, let’s write the base test case along with some skelton code to structure our thought process:

Perfect, now let’s implement our methods and do some debugging!

Now for tilting our platform, we can just go through our platform and then for each instance of O we can try to move it upward in column till we get another O or # and then move on the next one!

Here, some code for that with an Tile(Enum) to keep code tidy!

Let’s debug and see if it is working correctly, and actually we can write a test case just to verify the tilt_platform function:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
✅ tilt_platform passed

[Done] exited with code=0 in 0.087 seconds

Let’s see a beautiful visualisation of platform tilting to north as we h̶u̶m̶a̶n̶s̶ coders can appreciate:

Beautiful! 🤩

Now, let’s implement our load calculation function, as it’s clear from our visualization above, all we need to do is to sum(number of "O” rocks * number of rows from the rock to the south edge of the platform)

Let’s write some code, seems pretty simple:

And let’s run both of our test cases?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
✅ tilt_platform passed
✅ calculate_load_on_north_beam passed

[Done] exited with code=0 in 0.056 seconds

Noice! Pretty quick as well. Let’s load up our puzzle input and run this code?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
❗️ Total load on the north beam is XXXXXX

[Done] exited with code=0 in 0.07 seconds

We get an answer, let’s input this in our answer box, I have a good feeling about this one!

Ez! 🕶

Here’s our code till now, we will optimise it in next part, as preoptimization is futile:

# Day 14 - Parabolic Reflector Dish

from enum import Enum

class TiltDirection(Enum):
    North = 1
    South = 2
    East = 3
    West = 4

class Tile(Enum):
    Empty = "."
    CubeRock = "#"
    RoundRock = "O"

def tilt_platform(platform_state, direction=TiltDirection.North):
    # well, we only care about north for now
    if direction != TiltDirection.North:
        NotImplementedError("Only TiltDirection.North is supported for now")

    # split the platform state into rows
    platform_state = [list(row) for row in platform_state.split("\n")]

    for i, row in enumerate(platform_state):
        for j, tile in enumerate(row):
            if tile == Tile.RoundRock.value:
                # move this rock upwards in column
                row_idx, col_idx = i, j
                while (
                    row_idx - 1 >= 0
                    and platform_state[row_idx - 1][col_idx] == Tile.Empty.value
                ):
                    platform_state[row_idx][col_idx] = Tile.Empty.value
                    platform_state[row_idx - 1][col_idx] = Tile.RoundRock.value
                    row_idx -= 1

    return platform_state

def calculate_load_on_north_beam(tilted_platform_state):
    total_load = 0
    load_factor = len(tilted_platform_state)

    for row in tilted_platform_state:
        total_load += load_factor * row.count(Tile.RoundRock.value)
        load_factor -= 1

    return total_load

def part_one():
    with open("day_14/input.txt") as f:
        platform_state = f.read()

    tilted_platform_state = tilt_platform(platform_state, TiltDirection.North)
    total_load = calculate_load_on_north_beam(tilted_platform_state)
    print(f"❗️ Total load on the north beam is {total_load}")

def test_tilt_platform():
    platform_state = """O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#...."""

    expected_platform_state = """OOOO.#.O..
OO..#....#
OO..O##..O
O..#.OO...
........#.
..#....#.#
..O..#.O.O
..O.......
#....###..
#....#...."""

    tilted_platform_state = tilt_platform(platform_state, TiltDirection.North)
    assert tilted_platform_state == [
        list(row) for row in expected_platform_state.split("\n")
    ], f"Expected {expected_platform_state}, got {tilted_platform_state}"
    print("✅ tilt_platform passed")

def test_calculate_load_on_north_beam():
    platform_state = """O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#...."""

    tilted_platform_state = tilt_platform(platform_state, TiltDirection.North)
    total_load = calculate_load_on_north_beam(tilted_platform_state)
    assert total_load == 136, f"Expected 136, got {total_load}"
    print("✅ calculate_load_on_north_beam passed")

if __name__ == "__main__":
    test_tilt_platform()
    test_calculate_load_on_north_beam()
    part_one()

---

Part Two

The parabolic reflector dish deforms, but not in a way that focuses the beam. To do that, you’ll need to move the rocks to the edges of the platform. Fortunately, a button on the side of the control panel labeled “spin cycle” attempts to do just that!

Each cycle tilts the platform four times so that the rounded rocks roll north, then west, then south, then east. After each tilt, the rounded rocks roll as far as they can before the platform tilts in the next direction. After one cycle, the platform will have finished rolling the rounded rocks in those four directions in that order.

Here’s what happens in the example above after each of the first few cycles:

After 1 cycle:
…#…
…#…O#
…OO##…
.OO#…
…OOO#.
.O#…O#.#
…O#…
…OOOO
#…O###..
#..OO#…

After 2 cycles:
…#…
…#…O#
…##…
..O#…
…OOO#.
.O#…O#.#
…O#…O
…OOO
#..OO###..
#.OOO#…O

After 3 cycles:
…#…
…#…O#
…##…
..O#…
…OOO#.
.O#…O#.#
…O#…O
…OOO
#…O###.O
#.OOO#…O

This process should work if you leave it running long enough, but you’re still worried about the north support beams. To make sure they’ll survive for a while, you need to calculate the total load on the north support beams after 1000000000 cycles.

In the above example, after 1000000000 cycles, the total load on the north support beams is 64.

Run the spin cycle for 1000000000 cycles. Afterward, what is the total load on the north support beams?

---

Well, haven’t we got used to ever increasing exponential scale of Part Two! 👀

Let’s dive in…

Our foresight of using TiltDirection(Enum) was correct, we do need to tilt in other directions, but thankfully we still only care about north support beams!

So, seems like we can to do 1000000000 — one billion cycles where each cycle means:

• tilts the platform four times so that the rounded rocks roll north, then west, then south, then east.

Before thinking how we can optimise without doing 1000000000 repeatitions, let’s just implement and test tilt_platform for other 3 directions:

I know, I know, a lot of dup code, we will fix this in final code!

And we can modify our tilt_platform to basically use a switch case to call relevant method. Also, introducing tilt_platform_cycle where we can pass num_cycles where each cycle is defined as:

Let’s test our tilt code for the base case given in the part 2 of the puzzle:

Let’s run this?

And….nope! It failed!

💡 Edge case: Well, when we go to tilt_platform_south since it’s traversing from (0,0) -> (i,j) (from top left to bottom right), it won’t be able to move a O rock if it has another O rock below it, but later in iteration, if we move the bottom most rock of the group, the rocks above it should also follow!

This will never be a problem when we do tilt_platform_north and tilt_platform_west since we are starting from top left aka (0,0) in our loop.

💭 An easy way to fix this is to, for tilt_platform_south and tilt_platform_east, just iterate from bottom right (i,j) to top left (0,0) and it should automatically take care of the edge cases without having to make our code too complicated!

This shall ensure our group won’t be blocked by neighbours while tilting east or south.

After a few debugging sessions! It works! 🤓

Here’s a quick visuzliation of 1 cycle, with our platform_state

roll north, then west, then south, then east.

Let’s see if our test cases work?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
✅ tilt_platform_cycle with 1 cycle passed
✅ tilt_platform_cycle with 2 cycles passed
✅ tilt_platform_cycle with 3 cycles passed

[Done] exited with code=0 in 0.073 seconds

How about checking our testcase — 1 billion times and see if we get 64 load as given in the puzzle!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
✅ test_calculate_load_on_north_beam passed

[Done] exited with code=0 in 0.075 seconds

0.075 seconds // Looking at this fast runtime, I am just tempted to run it for A billion cycles for the puzzle input as it is just 100x100 and our runtime is just O(n²)!

Are you game? Yes? Let’s do it!

🤞

Well, 3 minutes later, doesn’t seem likely! 🥲

I should have had put some std::out just to know which cycle our code is on currently! So, added some logging in parallel, just to gauge the speed:

Let’s see how many cycles we do for puzzle input in 10 seconds for fun:

~300 cycles in 10 seconds

So, it should just take us 33,333,333.33 seconds ~ 555,555.56 minutes ~ 9,259.26 hours ~ 385.80 days, which is just over 1 year! 🤯

Yep! It’s difficult for human brain to estimate large numbers! Let’s optimise now?!

One of my early hypothesis is that we are spending so much time tilting our platform_state that we are bound to get repeated inputs for multiple directions! We can probably make it faster by just introducing a cache to track input and output for tilt_platform function!

Let’s test that, using our same unscientific test above (it will be interesting to see how memory size grows as these are 4 computations per cycle, totalling to 4 billion computations!):

Added cache!

~300 / 10 seconds, no avail!

Let’s rethink now! Brute force won’t work clearly!

I still firmly beleive there has to be some kind of a repeatition after a while and we just need to find the cycle here!

Added some logging, let’s see our test input:

Clearly we can see, there is some cycle going on here!

💡Now, all we need to do is, find the cycle length and find the cycle elements, and then by the magic of modulus % we can directly find the platform_state, as if what it will be after 1000000000 cycles!

.

.

30 minutes and some debugging later!

.

.

Whipped up this spaghetti code (I promise, I will fix this):

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
✅ tilt_platform_cycle with 1 cycle passed
✅ tilt_platform_cycle with 2 cycles passed
✅ tilt_platform_cycle with 3 cycles passed
✅ test_calculate_load_on_north_beam_1000000000_cycles passed

[Done] exited with code=0 in 0.073 seconds

Finally! 🙏

Now, let’s run for our puzzle input?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_14/parabolic_reflector_dish.py"
‼️ Total load on the north beam after 1000000000 cycles is XXXXX

[Done] exited with code=0 in 4.166 seconds

We have an answer in 4.166 seconds, let’s put this in the answer box and…

Finally 🙏

Here’s our pythonic and optimized code:

# Day 14 - Parabolic Reflector Dish

from enum import Enum

class TiltDirection(Enum):
    North = "NORTH"
    South = "SOUTH"
    East = "EAST"
    West = "WEST"

class Tile(Enum):
    Empty = "."
    CubeRock = "#"
    RoundRock = "O"

def tilt_platform(platform_state, direction):
    rows, cols = len(platform_state), len(platform_state[0])
    delta = {
        TiltDirection.North: (0, -1),
        TiltDirection.South: (0, 1),
        TiltDirection.East: (1, 0),
        TiltDirection.West: (-1, 0)
    }[direction]

    def is_valid_position(row, col):
        return 0 <= row < rows and 0 <= col < cols

    def move_rock(start_row, start_col):
        row, col = start_row, start_col
        while is_valid_position(row + delta[1], col + delta[0]) and \
                platform_state[row + delta[1]][col + delta[0]] == Tile.Empty.value:
            platform_state[row][col] = Tile.Empty.value
            row, col = row + delta[1], col + delta[0]
            platform_state[row][col] = Tile.RoundRock.value

    if direction in [TiltDirection.North, TiltDirection.West]:
        range_func = range
    else:
        range_func = lambda start, end: range(end - 1, start - 1, -1)

    for i in range_func(0, rows):
        for j in range_func(0, cols):
            if platform_state[i][j] == Tile.RoundRock.value:
                move_rock(i, j)

    return platform_state

def tilt_platform_cycle(platform_state, num_cycles=1):    
    platform_cache = {}  # Cache for storing seen platform states
    cycle_patterns = []  # List to store unique states forming a cycle
    cycle_start_point = None

    for idx in range(1, num_cycles+1):
        # Tilt platform in all directions
        for direction in [TiltDirection.North, TiltDirection.West, TiltDirection.South, TiltDirection.East]:
            platform_state = tilt_platform(platform_state, direction)

        # Generate a key for the current state
        platform_state_key = "\n".join([" ".join(map(str, row)) for row in platform_state])
       
        # Check if the current state has been seen before
        if platform_state_key in platform_cache:
            if cycle_start_point is None:
                cycle_start_point = platform_cache[platform_state_key]
                cycle_patterns.append(platform_state_key)
                continue

            # Start of the cycle found, calculate the index in the cycle pattern
            if platform_state_key == cycle_patterns[0]:
                cycle_length = len(cycle_patterns)
                cycle_index = (num_cycles - cycle_start_point) % cycle_length
                return [list(row) for row in cycle_patterns[cycle_index].split("\n")]

            # New state in the cycle
            if platform_state_key not in cycle_patterns:
                cycle_patterns.append(platform_state_key)
            continue

        # Store the new state in the cache
        platform_cache[platform_state_key] = idx
        if cycle_start_point is not None and platform_state_key not in cycle_patterns:
            cycle_patterns.append(platform_state_key)

    return platform_state

def calculate_load_on_north_beam(tilted_platform_state):
    return sum((len(tilted_platform_state) - i) * row.count(Tile.RoundRock.value)
               for i, row in enumerate(tilted_platform_state))

def part_one():
    with open("day_14/input.txt") as f:
        platform_state = f.read()

    # split the platform state into rows
    platform_state = [list(row) for row in platform_state.split("\n")]

    tilted_platform_state = tilt_platform(platform_state, TiltDirection.North)
    total_load = calculate_load_on_north_beam(tilted_platform_state)
    print(f"❗️ Total load on the north beam is {total_load}")

def part_two():
    with open("day_14/input.txt") as f:
        platform_state = f.read()

    # split the platform state into rows
    platform_state = [list(row) for row in platform_state.split("\n")]

    tilted_platform_state = tilt_platform_cycle(platform_state, 1000000000)
    total_load = calculate_load_on_north_beam(tilted_platform_state)
    print(f"‼️ Total load on the north beam after 1000000000 cycles is {total_load}")

def test_tilt_platform_cycle():
    platform_state_og = """O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#...."""

    expected_platform_state_with_1_cycle = """.....#....
....#...O#
...OO##...
.OO#......
.....OOO#.
.O#...O#.#
....O#....
......OOOO
#...O###..
#..OO#...."""

    expected_platform_state_with_2_cycles = """.....#....
....#...O#
.....##...
..O#......
.....OOO#.
.O#...O#.#
....O#...O
.......OOO
#..OO###..
#.OOO#...O"""

    expected_platform_state_with_3_cycles = """.....#....
....#...O#
.....##...
..O#......
.....OOO#.
.O#...O#.#
....O#...O
.......OOO
#...O###.O
#.OOO#...O"""

    # split the platform state into rows
    platform_state = [list(row) for row in platform_state_og.split("\n")]
    expected_platform_state_with_1_cycle = [
        list(row) for row in expected_platform_state_with_1_cycle.split("\n")
    ]
    tilted_platform_state = tilt_platform_cycle(platform_state, 1)
    assert (
        tilted_platform_state == expected_platform_state_with_1_cycle
    ), f"Expected {expected_platform_state_with_1_cycle}, got {tilted_platform_state}"
    print("✅ tilt_platform_cycle with 1 cycle passed")

    # reseting platform_state
    platform_state = [list(row) for row in platform_state_og.split("\n")]
    expected_platform_state_with_2_cycles = [
        list(row) for row in expected_platform_state_with_2_cycles.split("\n")
    ]
    tilted_platform_state = tilt_platform_cycle(platform_state, 2)
    assert (
        tilted_platform_state == expected_platform_state_with_2_cycles
    ), f"Expected {expected_platform_state_with_2_cycles}, got {tilted_platform_state}"
    print("✅ tilt_platform_cycle with 2 cycles passed")

    # reseting platform_state
    platform_state = [list(row) for row in platform_state_og.split("\n")]
    expected_platform_state_with_3_cycles = [
        list(row) for row in expected_platform_state_with_3_cycles.split("\n")
    ]
    tilted_platform_state = tilt_platform_cycle(platform_state, 3)
    assert (
        tilted_platform_state == expected_platform_state_with_3_cycles
    ), f"Expected {expected_platform_state_with_3_cycles}, got {tilted_platform_state}"
    print("✅ tilt_platform_cycle with 3 cycles passed")

def test_tilt_platform():
    platform_state = """O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#...."""

    expected_platform_state = """OOOO.#.O..
OO..#....#
OO..O##..O
O..#.OO...
........#.
..#....#.#
..O..#.O.O
..O.......
#....###..
#....#...."""
    # split the platform state into rows
    platform_state = [list(row) for row in platform_state.split("\n")]
    tilted_platform_state = tilt_platform(platform_state, TiltDirection.North)
    assert tilted_platform_state == [
        list(row) for row in expected_platform_state.split("\n")
    ], f"Expected {expected_platform_state}, got {tilted_platform_state}"
    print("✅ tilt_platform passed")

def test_calculate_load_on_north_beam():
    platform_state = """O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#...."""
    # split the platform state into rows
    platform_state = [list(row) for row in platform_state.split("\n")]
    tilted_platform_state = tilt_platform(platform_state, TiltDirection.North)
    total_load = calculate_load_on_north_beam(tilted_platform_state)
    assert total_load == 136, f"Expected 136, got {total_load}"
    print("✅ test_calculate_load_on_north_beam passed")

def test_calculate_load_on_north_beam_1000000000_cycles():
    platform_state = """O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#...."""
    # split the platform state into rows
    platform_state = [list(row) for row in platform_state.split("\n")]
    tilted_platform_state = tilt_platform_cycle(platform_state, 1000000000)
    total_load = calculate_load_on_north_beam(tilted_platform_state)
    assert total_load == 64, f"Expected 64, got {total_load}"
    print("✅ test_calculate_load_on_north_beam_1000000000_cycles passed")

if __name__ == "__main__":
    test_tilt_platform()
    test_calculate_load_on_north_beam()
    part_one()

    test_tilt_platform_cycle()
    test_calculate_load_on_north_beam_1000000000_cycles()
    part_two()

I am sure there is more juice left to squeeze as we can further optimize this, but I am tired now! I will most likely come back during holidays to optimise this to atleast sub-second compute time.

Stay tuned!

---

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