Day 14: Reflector Dish

If you think about the problem of applying all the iterations as a walk through a graph with cycles, the natural thing to reach for is a cycle-detection algorithm, such as Brent's. My idea is to instead apply a trick from the pathfinding literature: contractions.

For example, given a path from A to E, A -> B -> C -> D -> E, we can start by moving from A to B, and then from B to C. Now that we know where the path leads, we can add a shortcut from A to C, skipping B.

Short-cuts are themselves subject to being short-cut: When we're at A again due to the cyclic nature of the problem, we move through the short-cut A--->C. If there is already a short-cut C--->E, we can combine the shortcuts to form a new shortcut A--->E.

We also store the length of the path that the shortcut shortcuts in order to be able to track how far along the overall 'path' of applying the required number of iterations we are.

If a shortcut overshoots the target, we clear all shortcuts and continue building new, shorter, shortcuts from the current position until we reach our target number of iterations.

The path length covered by shortcuts increases quickly until we overshoot -- at that point we start again with a small step size (no shortcuts) and build up momentum (increasingly longer shortcuts) until we reach the goal or overshoot again.

pub fn path_contraction<N, FN>(start: &N, mut successor: FN, iterations: usize) -> N
where
    N: Eq + Hash + Clone,
    FN: FnMut(&N) -> N,
{
    let mut shortcuts: HashMap<N, (N, usize)> = HashMap::default();

    let mut cur = start.clone();
    let mut cur_iter = 0;

    loop {
        if cur_iter == iterations {
            return cur;
        }

        // Step 1
        let (next1, iters_step1) = if let Some((next1, length1)) = shortcuts.get(&cur) {
            (next1.clone(), *length1)
        } else {
            let next1 = successor(&cur);
            (next1, 1)
        };

        // Step 2
        let (next2, iters_step2) = if let Some((next2, length2)) = shortcuts.get(&next1) {
            (next2.clone(), *length2)
        } else {
            let next2 = successor(&next1);
            (next2, 1)
        };

        // Combine
        if cur_iter + iters_step1 + iters_step2 <= iterations {
            shortcuts.insert(cur, (next2.clone(), iters_step1 + iters_step2));
            cur = next2;
            cur_iter += iters_step1 + iters_step2;
        } else if cur_iter + iters_step1 <= iterations {
            shortcuts.insert(cur, (next1.clone(), iters_step1));
            cur = next1;
            cur_iter += iters_step1;
        } else {
            let next = successor(&cur);
            cur = next;
            cur_iter += 1;

            shortcuts.clear();
        }
    }
}

class Solver:

    def __init__(self):
        with open('input.txt', 'r', encoding='utf-8') as f:
            self.lines = [line.strip() for line in f.readlines()]
        self.grid = Grid.read_from_lines(self.lines)

    def run(self):
        total = 0
        for col in self.grid.all_columns():
            new_col = self.roll_rocks_in_col(col)
            print(new_col)
            for i, rock in enumerate(new_col):
                if rock == 'O':
                    total += len(col) - i
        return total

    def roll_rocks_in_col(self, col):
        col_as_str = str(col)
        segments = col_as_str.split('#')
        result = []
        for segment in segments:
            result.append(segment.replace('.', "") + segment.replace('O', ""))
        return '#'.join(result)


if __name__ == '__main__':
    print(Solver().run())

For this part, my solution was a bit less elegant in terms of code, basically I didn't want to try and figure out modular math abstractly, so I just returned the list of all possible positions & the index where the loop started. Then I did the manipulation separately.

Since it's split across multiple files, see my repo

Read part2.py then test_fix.py then modular_math.py

{-# LANGUAGE NumericUnderscores #-}

module Main (main) where
    
import Data.List (transpose, sort, intercalate, elemIndex)
import AOCTools (splitBy)

main :: IO ()
main = do
    input <- readFile "./input.txt"
    putStrLn $ "Part 1: " ++ show (solve1 $ lines input)
    putStrLn $ "Part 2: " ++ show (solve2 $ lines input)

tiltNorth :: [String] -> [String]
tiltNorth = transpose . tiltWest . transpose

tiltSouth :: [String] -> [String]
tiltSouth = transpose . tiltEast . transpose

tiltWest :: [String] -> [String]
tiltWest = map reverse . tiltEast . map reverse

tiltEast :: [String] -> [String]
tiltEast = map $ intercalate "#" . map sort . splitBy "#"

calculateLoad :: [String] -> Int
calculateLoad platform = sum $ zipWith (*) [1..] rowCounts where
    rowCounts = map (length . filter (=='O')) (reverse platform)

solve1 :: [String] -> Int
solve1 = calculateLoad . tiltNorth

tiltCycle :: [String] -> [String]
tiltCycle = tiltEast . tiltSouth . tiltWest . tiltNorth

solve2 :: [String] -> Int
solve2 input = calculateLoad result where
     platforms = iterate tiltCycle input
     (cycleStart, cycleLength, cyclePattern) = findCycle 0 []
     result = cyclePattern !! ((1_000_000_000 - cycleStart) `mod` cycleLength)
     findCycle i prev = case elemIndex curr prev of
        Just x -> (i, x + 1, reverse (take (x+1) prev))
        Nothing -> findCycle (i+1) (curr:prev)
        where curr = platforms !! i

I thought about pattern detection, but I thought the problem probably can be designed to create very long patterns that is not feasibly storeable, or the pattern might lies in the individual rotations in a cycle. After seeing visualizations on Reddit, I decided to give the simplest solution a Go

package main

import (
	"bytes"
	"fmt"
	"io"
	"os"
	"slices"
	"strings"
)

func main() {
	input, err := io.ReadAll(os.Stdin)
	if err != nil {
		panic(err)
	}
	fmt.Println("start")

	problem := parse(input)
	// part 1
	//for shiftUp(problem) {
	//}

	// part 2
	steps := make([]string, 0, 10000)
	steps = append(steps, problemToString(problem))
	var repeatingIndex int
	iterationLeft := 0
	iterationCount := 1000000000
	for i := 0; i < iterationCount; i++ {
		spinCycle(problem)
		if i%1_000_000 == 0 {
			fmt.Printf("cycle %d\n", i)
		}
		problemString := problemToString(problem)
		repeatingIndex = slices.Index(steps, problemString)
		if repeatingIndex != -1 {
			fmt.Printf("found cycle at %d - %d\n", repeatingIndex, i)
			iterationLeft = iterationCount - i - 1
			break
		}
		steps = append(steps, problemString)
	}

	// at the break, problem == steps[repeatingIndex]
	patternLength := len(steps) - repeatingIndex
	problem = parse([]byte(steps[repeatingIndex+(iterationLeft%patternLength)]))

	fmt.Println(problemToString(problem))
	fmt.Println(countLoad(problem))
}

func problemToString(p [][]byte) string {
	var out strings.Builder
	for _, l := range p {
		out.Write(l)
		out.WriteRune('\n')
	}
	return out.String()
}

func parse(input []byte) [][]byte {
	return bytes.Split(bytes.TrimSpace(input), []byte{'\n'})
}

func spinCycle(p [][]byte) {
	for shiftUp(p) {
	}
	for shiftLeft(p) {
	}
	for shiftDown(p) {
	}
	for shiftRight(p) {
	}
}

func shiftUp(p [][]byte) bool {
	mutated := false
	for row, rowCh := range p {
		if row == 0 {
			continue
		}
		for col, colCh := range rowCh {
			if colCh != byte('O') {
				continue
			}
			if p[row-1][col] == byte('.') {
				p[row-1][col] = 'O'
				p[row][col] = '.'
				mutated = true
			}
		}
	}
	return mutated
}

func shiftLeft(p [][]byte) bool {
	mutated := false
	for row, rowCh := range p {
		for col, colCh := range rowCh {
			if col == 0 {
				continue
			}
			if colCh != byte('O') {
				continue
			}
			if p[row][col-1] == byte('.') {
				p[row][col-1] = 'O'
				p[row][col] = '.'
				mutated = true
			}
		}
	}
	return mutated
}

func shiftDown(p [][]byte) bool {
	mutated := false
	for row, rowCh := range p {
		if row == len(p)-1 {
			continue
		}
		for col, colCh := range rowCh {
			if colCh != byte('O') {
				continue
			}
			if p[row+1][col] == byte('.') {
				p[row+1][col] = 'O'
				p[row][col] = '.'
				mutated = true
			}
		}
	}
	return mutated
}

func shiftRight(p [][]byte) bool {
	mutated := false
	for row, rowCh := range p {
		for col, colCh := range rowCh {
			if col == len(rowCh)-1 {
				continue
			}
			if colCh != byte('O') {
				continue
			}
			if p[row][col+1] == byte('.') {
				p[row][col+1] = 'O'
				p[row][col] = '.'
				mutated = true
			}
		}
	}
	return mutated
}

func countLoad(p [][]byte) int64 {
	out := int64(0)
	for row, rowCh := range p {
		rowWeight := int64(len(p) - row)
		for _, c := range rowCh {
			if c == byte('O') {
				out += rowWeight
			}
		}
	}

	return out
}

# Advent of Code 2023
# Day 14: Parabolic Reflector Dish

with open("inputs/day_14.txt") as file:
    platform = [list(line.rstrip("\n")) for line in file.readlines()]
    size = len(platform)

def total_load(platform):
    total_load = 0

    for y, row in enumerate(platform):
        for char in row:
            if char == "O":
                total_load += size - y

    return total_load

seen = {}
part_1_finished = False
iteration = 0

while iteration < 1000000000:
    for _ in range(4):
        for x in range(size):
            for y in range(1, size):
                if platform[y][x] == "O" and platform[y - 1][x] == ".":
                    for new_y in range(y - 1, -1, -1):
                        if platform[new_y][x] != ".":
                            new_y += 1
                            break

                    platform[y][x] = "."
                    platform[new_y][x] = "O"

        if not part_1_finished:
            print(f"Part 1: {total_load(platform)}")
            part_1_finished = True

        platform = [list(reversed(row)) for row in zip(*platform)]

    key = "".join("".join(row) for row in platform)

    if key in seen:
        cycle_length = iteration - seen[key]
        iteration += (1000000000 - iteration) // cycle_length * cycle_length
    else:
        seen[key] = iteration

    iteration += 1

print(f"Part 2: {total_load(platform)}")

The function itself is short, but I wanted to make sure I'd have an easy time remembering how to use it when the next iteration of this "find the bazillionth iteration of some sequence" problem comes up again.

defmodule AdventOfCode.Sequence do
  @moduledoc """
  Functions for infinitely repeating sequences.
  """

  @doc """
  Given an indexed list describing the repeating segment of an infinitely repeating sequence,
  returns the value at `at_index` of the sequence.

  Indices in the list do not need to start at 0, but they do need to be contiguous,
  and the list must be ordered by index, ascending.

  `at_index` can be any integer.
  """
  @spec at(nonempty_list({a, index :: integer}), integer) :: a when a: term
  def at(repeat, i) do
    [{_value, start_index} | _] = repeat
    {value, _index} = Enum.at(repeat, Integer.mod(i - start_index, length(repeat)))
    value
  end
end

I find it very intuitive to model this kind of "cycle of repeated operations" problem as a stream pipeline.

defmodule AdventOfCode.Solution.Year2023.Day14 do
  alias AdventOfCode.Grid, as: G
  alias AdventOfCode.Sequence

  def part1(input) do
    input
    |> G.from_input()
    |> tilt(:n)
    |> rock_load()
  end

  def part2(input) do
    [:n, :w, :s, :e]
    |> Stream.cycle()
    |> Stream.scan(G.from_input(input), &tilt(&2, &1))
    |> Stream.drop(3)
    |> Stream.take_every(4)
    |> Stream.with_index(1)
    |> Enum.reduce_while(%{}, fn {grid, i}, indices ->
      case Map.fetch(indices, grid) do
        {:ok, repeat_start} -> {:halt, build_repeat_segment(indices, repeat_start, i - 1)}
        :error -> {:cont, Map.put(indices, grid, i)}
      end
    end)
    |> Sequence.at(1_000_000_000)
  end

  defp build_repeat_segment(indices, start_index, end_index) do
    repeat_indices = start_index..end_index//1

    indices
    |> Stream.filter(fn {_g, j} -> j in repeat_indices end)
    |> Stream.map(fn {g, j} -> {rock_load(g), j} end)
    |> Enum.sort_by(&elem(&1, 1))
  end

  defp tilt(grid, :n), do: do_tilt(grid, &G.cols/1, ?O, &G.from_cols/1)
  defp tilt(grid, :s), do: do_tilt(grid, &G.cols/1, ?., &G.from_cols/1)
  defp tilt(grid, :w), do: do_tilt(grid, &G.rows/1, ?O, &G.from_rows/1)
  defp tilt(grid, :e), do: do_tilt(grid, &G.rows/1, ?., &G.from_rows/1)

  defp do_tilt(grid, to_lanes, char_to_send_forward, from_lanes) do
    grid
    |> to_lanes.()
    |> Enum.map(fn lane ->
      lane
      |> Stream.map(fn {_coords, char} -> char end)
      |> Stream.chunk_by(&(&1 == ?#))
      |> Enum.flat_map(fn
        [?# | _] = l -> l
        l -> char_to_front(l, char_to_send_forward)
      end)
    end)
    |> from_lanes.()
  end

  defp char_to_front(l, char, acc \\ [])
  defp char_to_front([], _char, acc), do: acc
  defp char_to_front([char | rest], char, acc), do: [char | char_to_front(rest, char, acc)]
  defp char_to_front([other | rest], char, acc), do: char_to_front(rest, char, [other | acc])

  defp rock_load(grid) do
    grid
    |> G.rows()
    |> Stream.with_index()
    |> Stream.map(fn {row, i} -> (grid.height - i) * Enum.count(row, &match?({_, ?O}, &1)) end)
    |> Enum.sum()
  end
end