Advent of Code 2023 - Day 14

README.md

Advent of Code - Day 14

Day 14: Parabolic Reflector Dish

Objective: - Adjust a parabolic reflector dish by moving rocks on a platform, calculating the load on the north support beams after specific movements.

Part One: Tilt North

1. Initial Setup:

   • A grid representing the platform, with cells containing a rounded rock (O), a cube-shaped rock (#), or an empty space (.).

2. Tilting North:

   • On tilting north, all rounded rocks (O) move "upwards" until they hit the top or a cube-shaped rock. Cube-shaped rocks (#) don't move.

3. Calculating Load:

   • The load of each rounded rock is the number of rows from the rock to the south edge, including its own row.

Algorithm:

• Iterate through each cell from top to bottom.
• For each rounded rock (O), move it upwards in the grid as far as possible.
• Calculate the load for each rounded rock and sum them up.

Part Two: Spin Cycle

1. Spin Cycle Movement:

   • Each cycle consists of tilting the platform north, west, south, and east, in that order. Rounded rocks roll as far as they can in each direction before the next tilt.

2. Long-Term Calculation:

   • Calculate the total load on the north support beams after 1,000,000,000 cycles.

Challenges:

• Simulating 1,000,000,000 cycles directly is computationally impractical.
• Find a pattern or a way to predict the grid's state after a large number of cycles.

Possible Approaches:

• Simulate a small number of cycles to observe any patterns or repeating states.
• Look for a cycle in the grid's state to predict its state at any cycle number.

Algorithm:

• Implement the spin cycle movement for the grid.
• Identify patterns or repetitions in the grid states over several cycles.
• Use these patterns to calculate the load after 1,000,000,000 cycles.

index.js

/**
 * With my input I'm getting a number that is exactly 4 too low for part 2... it's almost as if
 * I'm off by 1 on each cycle somehow - but I'm just not feeling motivated to keep at it tonight
 **/
const fs = require('fs');

function readInput(filePath) {
    const data = fs.readFileSync(filePath, 'utf8');
    return data.trim().split('\n').map(line => line.split(''));
}

function tilt(platform, direction) {
    let transposed = direction % 2 === 0 ? transpose(platform) : platform;
    if (direction === 0 || direction === 3) transposed = transposed.map(row => row.reverse());

    for (let row of transposed) {
        for (let i = row.length - 1; i >= 0; i--) {
            if (row[i] === 'O') {
                let j = i;
                while (j < row.length - 1 && row[j + 1] === '.') {
                    j++;
                }
                if (j !== i) {
                    row[j] = 'O';
                    row[i] = '.';
                }
            }
        }
    }

    if (direction === 0 || direction === 3) transposed = transposed.map(row => row.reverse());
    if (direction % 2 === 0) transposed = transpose(transposed);

    return transposed;
}

function transpose(matrix) {
    return matrix[0].map((_, colIndex) => matrix.map(row => row[colIndex]));
}

function calculateLoad(platform) {
    let load = 0;
    for (let row = 0; row < platform.length; row++) {
        for (let col = 0; col < platform[row].length; col++) {
            if (platform[row][col] === 'O') {
                load += platform.length - row;
            }
        }
    }
    return load;
}

function platformToString(platform) {
    return platform.map(row => row.join('')).join('\n');
}

// ... [Previous code]

function main(filePath) {
    let platform = readInput(filePath);
    platform = tilt(platform, 0);
    const loadPartOne = calculateLoad(platform);
    console.log('Part One Load:', loadPartOne);

    platform = readInput(filePath); // Reset platform to initial state for part two
    const seenStates = new Map();
    let cycle = 0;
    while (cycle < 1000000000) {
        platform = tilt(tilt(tilt(tilt(platform, 0), 3), 2), 1);
        const platformString = platformToString(platform);
        if (seenStates.has(platformString)) {
            const firstAppearance = seenStates.get(platformString);
            const patternLength = cycle - firstAppearance;
            // Adjust the remaining cycles calculation to include the current cycle
            const remainingCycles = (1000000000 - cycle) % patternLength;
            for (let i = 0; i < remainingCycles; i++) {
                platform = tilt(tilt(tilt(tilt(platform, 0), 3), 2), 1);
            }
            break;
        }
        seenStates.set(platformString, cycle);
        cycle++;
    }

    const loadPartTwo = calculateLoad(platform);
    console.log('Part Two Load:', loadPartTwo);
}

main('map.txt');

main.py

from copy import deepcopy

def parse_input(data):
    """
    Convert the string input into a list of columns for easier manipulation.
    """
    return [''.join(line) for line in zip(*data.splitlines())]

def rotate(grid):
    """
    Rotate the grid 90 degrees by reversing all lines and returning the columns.
    """
    return [''.join(line) for line in zip(*map(reversed, grid))]

def tilt(grid):
    """
    Tilt the grid to move all rounded rocks to the left in each column.
    """
    new_grid = deepcopy(grid)
    for idx, column in enumerate(grid):
        segments = ''.join(column).split("#")  # Group rocks between cube-shaped rocks
        for seg_idx, segment in enumerate(segments):
            if segment:
                # Sort to move rounded rocks to the left
                segments[seg_idx] = ''.join(sorted(segment, reverse=True))
        new_grid[idx] = '#'.join(segments)
    return new_grid

def load(grid):
    """
    Calculate the total load on the platform.
    """
    return sum(sum(i * (cell == "O") for i, cell in enumerate(col[::-1], 1)) for col in grid)

def cycle(grid):
    """
    Perform a full cycle of rotations and tilts.
    """
    for _ in range(4):
        grid = rotate(tilt(grid))
    return grid

def spin_cycle(grid, cycles=1_000_000_000):
    """
    Simulate the spin cycle to find the total load after a large number of cycles.
    """
    curr_grid = deepcopy(grid)
    grid_history = [grid]  # Record the history of grid states
    loop_idx, loop_len = 0, 0
    for counter in range(cycles):
        curr_grid = cycle(curr_grid)
        if curr_grid in grid_history:
            loop_idx = grid_history.index(curr_grid)
            loop_len = counter + 1 - loop_idx
            print(f"Loop found after {counter} cycles, starting at {loop_idx} for {loop_len} cycles.")
            break
        grid_history.append(curr_grid)

    # Calculate load after cycles using the loop information
    final_state_idx = (cycles - loop_idx) % loop_len + loop_idx
    return load(grid_history[final_state_idx])

# Read the input data
with open('map.txt', 'r') as file:
    input_data = parse_input(file.read())

# Calculate the total load for Part 1 and Part 2
total_load_part1 = load(tilt(input_data))
total_load_part2 = spin_cycle(input_data)

print(f"PART 1 - Total Load after one north tilt: {total_load_part1}")
print(f"PART 2 - Total Load after 1,000,000,000 cycles: {total_load_part2}")

map.txt

......O........#....O..O.O#O.O.##.O#.O##.O#......O........O....O.#..OO#.OO.#..#.........#.O..#O..#.O
O#..O...O....O.#...##.O....O..O.#...#...O..O#.#.#......#.O##O#....#..O...O..#.#......#.#O..#..#....#
O....##.O#O##.O...#...#.#.......OO.##..###.OO..O.#.#.OO#O..##..O.O.#...#..O.#....O.##.O#OO..........
....O#.O..OO.#..OOOO#.......O.....O.#O......OOO#....O.....O......O.....#..OOO.....O...O.O##OO.....##
OO#..#.O.##..##..#........O..OO.......#..O.OO.OO..#O...OO.##...#.OOO...O.O.O..#.O..#..O.O.##.O...OOO
#.....#OO.O......O..####O...O.....O.......#..#OO#..#...O...OOO.#....O#.....O...........#O#OO...O..O.
#O.O......O...O.O...O##.O#..OO....O..##.OO#O.##O.#.#.......O.O#.....OOOO......#..OO###OO.......O..#.
#.O.OO...#...##.O..OO..#.......O.O.O.O......O#....##.OOO.O.....#O#..##...OO.......#OOO.O..O......##.
..O.OO.O.#O.O........#..##.#.OO.O..##.O...O.#.....#..O.#....O..#O..O.#OO......O........#.#....#O..#.
..O......OO.O............OO#....##....#......O.#..O..O...O.O..#O......O.OO#.#.......O....#....##.O.#
.....#.O#O.#..#.#.##....#O....O.O.O.OO......#..O.O..#..OOOO....#.#..O.#.O.O..O.O#.O...O#..#..O##.O..
O..O#.OO.#.##.#.........OO.#.....#OO...........O....O..OO..O.O###..O.O.#O...O.O...#...O..O#O...OO...
.#.#...OO...#.O...O.........#OO..#.....O....##.#.OO.#.#.#OOO...#OOO.O.O..O#......#.##..........O....
....#..#...#...#.......#..#......##..O........O.OO.#O..#O.#.......#..#..O.O#.#...O#..O...O#.O...O.#O
.#O#O.O..........#O##.O#.#.........##.#............#.#.....#..#OO...#O....#OO.O.OO.#..#...O#........
.#..#.O#O...##O....O.....##...OOO#...#O..#..O##O..#..OO.#...#O.....#.O...O#.O#.OO...###.#..O#O..OO..
...#...O....O.#....#..#.O#OO...O.O#.#....O..#OO.#.O....#O#...O...O..O.##O..#.......O.##....O##....O.
#...O...O...O#O##O.O.#.#.....#.O...#.....##..#.#OO....OO#.......#..O..O.#.#O...#.#.#.....OO.O...OO..
.O...OO.O.....##.O.##.#O.....#O..O.###..#..##.O.##O....OO..#O#....O.....O...#O#O...OO.........O..##O
.O..OO.#O.#...O...O...#...O....#.O.O.O....#O.###O.#..#..##OO.O...O.#.#.#..O...#.....O.#.O.O.#..O....
O...OO.#...O.#..#.O..O#..O#....##.#O.##...#......#O#O..O..#.##.....O...#O#..O.O...OO...OO..#.OO.O.OO
.O.O....O.O.##O#....##..##O......#.#O#..O..#...OO..O...O.#..#O#..#..#.O...#.O.OO....O#..O##.O..O..O.
....#..O..O.OO.#.O...#OOOOO.OO.O#..O....#.#O.##........#OO.#.#.O.#.OO#...#OO..#.OO...O..#.O.....O#.#
.#O...O......#OOO#..#..#....O...O..O.#O....#O#...O..#...OO.#.O.O...O..#..#..O..##.O##.....O.O..OO..#
..#O.##.#.......OOOO.OO.....O..O........##.O.OO....O###..#.O...#O.O.#OO.#....O.O.#..........#.OO....
.##...##.#......O.#.OO#...#..O##..#..##.O.......O#..O.O.#.O..#.....#..O#....O....OO.OO.O..#...O#..O.
..##O##O......O.#O.O.....#..#.#O#.O..#O#O..#OO.#..#.#.....##O.................O.....O#OO...##...O..O
....#O#O..O.#..O....#.....#.....#......O.#O........O#..O.O#..OO...#.#.O..##....O.....#......O#....#.
#.....#...O....OO..O##.OO....O.#..#O.........O..............O....##OO##.....#.##.O...#..O..#O#OO...O
...O.#O#...O..OO#...O.#O#.......#..O...O#.#..#O...#.O.O....O##...##...#.OO...O.O..OO#.#..........##.
.......#OO....#.#O#..........O.##.O.O#.....O.OO.O.OO##...##O...OO.O..O#.OO...O......O#O..O.O.##...OO
..O.O#.#.....OO............O.O..#.O#.O.O.#.##.#O.O...#.O.....O..#.#....O..#O#O....O.O.#..OOO..O..O..
..O.#.O.............#OO#.#O....#O#...OO..O##...#.....O...............#..#..O..O#....O..##...O..O.O#.
...........O.........##O#.#.O.O..O##........#..#....#O..##O..##.OO...O#.##..#..#.#O....O.O.#........
...............OOO.#........O....#.#O..##.O...O.O#.......#.#O.#...#O.......###.......O.OO...O.O..O.#
.#.O#....#......O...OO##..O#O...O.O#.O.##.OO...OOOO....OO....#.#....##.###.O.O..O..##....#..........
..OO.....OO#O.........O.#..O....#......#.#.#.#...##O.OO#.O......O..O.#O....O#...OOO....O..O.O..#..#O
#O...O.O.......##..#..O..O...O...O..O.#..#.#.O.OO............OO....#OOOO#...OO.#.O#OO....O##.O....#.
.O#..OOO.O.#.......O....#......O.OO.#......#..#.O.......###.#....#O..O....O#.O.....#O#....O#.#.....#
....OOO#.#..#.O..O....#...O.#...OO....#..OO.O#O..O....O.O...O...O#O..O..O......O.#O..O#O..........O#
..O..#.OO###....#..O....#.O..#.....O.O.#..OOO.O...##...O#..##..O#.O.......O.#.###...O.....O......O..
..O##..OO..O.O...O.#....OO.OOO.O........O......#.O..O..........O...O#OOO..O....O.#..O##O.......#....
O.O..OO##.#...#O#..#...O..#.......#O..###..OOO..O..#.O#.O..#....O.OO#.##..##O.......OO#OO..#.O....#O
...#..O.#........OO.O....OOO#.O..O#O.......O....O........#O#...#O#.#..OO..O....#O.O....O...O###.#...
O..#.......#..#.....O..OOO.#..#OO...#O.O...O.....##O.O.#O....#.....#...#.........OO.O....#...O#O#...
.O..O.#O....O#O.###....#O.O.....................###......O..#...O.OO.....#.......O..#...OO.......##.
............#O#..#.#.......#.##....#O.#....O.#...O...OOO.O.....#O..####O...O..#..#.O##....#OO##.#.#.
....O.#..#.....#...#OO#.##...O..OO....#....O#..O......OO.OO.#OO....#.O..#.....#.##..#.O...O.O#.##O..
...#OO#.O.O......#...O.O.....#......#.......................#.#.....O..O.#OO.#..OOO.OO.O.......#..#.
O#..#OO.OO.O#....##.O.#....OO..#.#.....O...O...#.O...O...O..#..O.....O..OO..O...O...O#....#...O.O...
.......OO.#O..#O#OO.#.............#....O.O#..#..#.....#..O.O#..#..##O.O.O...O.O.#O..OO..#O...OO...#.
#..#O.O.O.....O..O#.#............##O#....O.O#...#...............#OO..O.....#...OOO#.......OO...#....
..#...O...OO..#...O#O.O.O.O....O..#O#O......#.#....#..OO....#O...OO.O..O#.#O#OO.#...O.O.O..#....##.O
..#..O#..##.O...O..O....O.O.#.....#.O.OO..#.#.#...OO#....#..#O........OO.OO#.#..#..##O...O.OO.O#.#..
...#O..OO.O#OO..O#O#O....#O....#.O#.OO.##.......O.O.OO##.......#.O.O.#O.##.......O..O....##.#O..#..#
#....##...O.......#..#OO.........#O.O.O.O#...O......O.......OO##....O....#.#O.#.#.....O.OO..#...O.O.
.O..O#.....O.#..O..#..#O..O.O...O..O.#....#.....#.#.O...O..#.O.O.O....O....O.O..O#O.....O.O....O...O
.......O...O.O....O.O.OO...##..OOOOOO.O...O.##.O...#...O.O#O...#.O.O.O.........O..#..O.....##.#....#
...O..........#.O...O.O.OOO...##.....#OO.......O....#.....O.......#.#O.........O.##O#..##...O.O.#.O.
..OO#O.....O.##......O..#...#..OO.....#O#.O..#.O..#.O.#......O.#O.#..O.#.#.O..#.O......#.....O..#.O.
..O#...O..O.O.OO....#..O.......#..#.O.#....O..OO#.OO.O..#.#O..O.#.......O...O#.OO.......O#........O#
...OO....#..O...O.#....#.#OOO...O.#.#.#.O....OO...OO...#......#O..#..O.#O....#O...#..O..OO#....OO..O
.O.OO##....OO.#...O.......O...O.O.O.O.O.....O.O#..O#O......##O..#..###.O....O...O..#O.##O#....#..##.
.#..O.O....O#O..OO#........#O#.OOO...##.....O#..#.#..O#.OOO.O...#.....O#........O#O......##...O.....
..O#O.....O.#O...O...#.O.........#OO..#O.O.##..##O..OO....O...O.#.#...#..O...O#.O...O......#OO...#.#
O.........##.....###O.O.#.O##..##.O.#.O.OO......OOO...O#.O#..OO..........##.##O.O#O.O...##.O....O..O
O..##OO.OO.......#......O.#..#.....O...O#.O#..#...OO...#.O...#O.#.O..O..OOO#....O..O...#....O...#.O.
..#.....#OOO#..O..O.....O........#...O..OO.O.....OO....O.###.....#O.#..O..#...#.###O..O#...O.#...O..
O.O..#O..###.#....O#......###..#....O..OOO..O..O..OO..OO#O.....O..#..O##.#.#..OO..##..#.....O....O..
..O......O..#.......##..#O..OO.O.O....#..OOO..OO.#..#..OO.O...O.....#.OO#OOO.O.##.....O...O##.#...O.
O.OO.#O..#.#...#...##...O.#O....O##O...O##.OO#.O.###.#OO..OO#O......OOO..#OOOO...OO....#.O#.........
.#O#O#O.O.O....O.O.O...###O.O#.#OO#.O......#O#.O#O#........O...#OOO..OOO.........O...#O#...O......#.
.OO.O.#..#.#..O.....OO.O.O#.....O...O..O.#.OO.O.....#.....O.......O.OO......O...OO..O..O....#..O.#.O
.#...O#..O..#.#O...#O...O..O.....#.#.O#.OO#.#..#.....OO.#....O.#OO.....OO.O.O..O.O....#......O..OO..
...OO.##.O...#.#....##O.O..#.............#.#...#.#.#.OOO.##.......O#.O.O...OO....O..#....#.....O...O
.O...OO............#....O.#OO.#....#O....O###.#.....O.O.......#.O....#O...O...O.O.#..OO....#....#...
#.#......#O.....O..#.O.OO.........O...##....O....#..##OO..##O#..O.O......O....#.O..O......#..##....O
OOO....#.#.O.#.O#..#.....#O.O.O..O.OO.......#O.#......O##.O.#.#...#.#..OO#O.O...O..O..O.O.....#..#O.
##..O##..O...#.#..#..............#O..#O.O.O..#..O....O...#..#OO...O##....O...O...#O....OO...#.O..O..
.#...OO#.#O.......##..#O...O.#..#......O#O....#..OO..OO.#O..O...O.#.O.........O........#.##.##...O.#
...O.O..O...#O..O.O..OO.OO##O.O.O.#..#...O..##...O##O#O..#.#.O#.#O#..#..OO..O....O..OOOO..##..O.....
##........#............#....O.....O.#.O.#.O.O.#O...#O......O.#....O...#O#...OO#.#O##........O.......
OOO#O.OO..#.......OO.OO...O...##.O.##..O....OO...O.O.............##O......#.#..O..#O..##..#....#...O
.#O.......#O...O..#O......O#OO.O.O#.O......#O#......#..###.O.#.#..O#.....##.O.O...O..O.O.#..OO#.#.#O
.....O.O...O.#.....OO###..##.O.....O....#...O.O...........#O#..#O..#....#.O.......###...#..O.#....#O
#O.OO.........O#..#O.....O....O#......#....O..OOO..O.#.OO#...O..O##....##O..#..O#..O......O.OOO.O.OO
.#...O.#.#O....O..OO....#O..#...#O........#....O...O.....O..O..O.##.......O#...#..#O..#.#...O..O.O.O
......O..O...#....O....#OO#....#.#..##OO.....O.O.#......OO.O#..........#..O..#.O##.........###..O...
.O.O#..#O.#..#....O......O..OO.#O.O....O.#......#O.O.....O..OO#..O#.O.#....#...O.O...#O..#......##.O
......O.....O.#...#....#....O#O.##...O.......O.#.##.###O#.#........O.#O.O..#...#...#.O.....O.O.O#...
#.#O#.#..#.#.......#..#..#.....##O#.......#.#..##OO.........O.O....#O...O....O....#..##..#OO..O...OO
.O..#.O.O.......O....#.O........O...#O.#.....O#....#.......O.O...O...O#..##....O...#.OOO...O.#O##...
.......#..O..O...O....O#...O#....#O..O....##..#....##O....OO..#......#....O..#O.....O.O#OO..........
..O#......O.O......#.....#O.#.#.#.O...#OO.....O.O#.....O#.O.#.....OO.O.O.O....O..OO..##.#.....OO#..O
#O...O.#..#...OOO#...O......O#..O..O....###....OO..O#.#O..##.O#.O##....#.#.O#.##.....O.............O
.O.##.........#O....#..O#.O.#...O......O#.O#.OO#...O.O..........##.##O....O.#O#O..O.#...OO.O#.O.O...
#OO.O.OO.....O#....O.OO..###...O.....#..O##...O..###.O...#.O..#.O...O...OOO.#.O.#..O...O#..OO.#O...O
.###..#.OO#O..O.#..#.O..O...#....#.#..#O.O....#O....O#..#......#...#..O.....O.O.#O...O..O.....O#..#.
..###....OOOO......#O....O.....O.O.O..O.#O..##...#O#..#..#....#.O..#..O.......O...#.O#.#..#...O....#
......#O.#.......O..OO#O#....#.....OO#..#.OO..O.#....#...#O....#...O....O#.......O..#.O.#...#.#.O...