# Day 14: Reflector Dish

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python` with any of the "short names" listed in this page of supported languages):

``````<details>
<summary>Part 1</summary>

```python
```

</details>
``````

1. DataWraith
I think I came up with an interesting way to solve this. My first attempt at implementing the idea didn't work, so I gave up and solved it the way everybody else did. Today I had a bit of time to...

I think I came up with an interesting way to solve this.

My first attempt at implementing the idea didn't work, so I gave up and solved it the way everybody else did. Today I had a bit of time to revisit this puzzle, and I managed to make my initial idea work.

Algorithm

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.

Rust
``````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();
}
}
}
``````
2. RheingoldRiver
I'm ridiculously pleased with my solution to part 1. Although I accidentally rolled south first instead of north first & barely missed top 1000, I was able to get top 1000 on part 2, which is...

I'm ridiculously pleased with my solution to part 1. Although I accidentally rolled south first instead of north first & barely missed top 1000, I was able to get top 1000 on part 2, which is pretty much my best-case goal.

Part 1
``````class Solver:

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

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

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

1 vote
3. scarecrw
Part 1 was a breeze, and I even correctly predicted a good chunk of part 2. I then proceeded to muck about making mistake after mistake with the cycle index until I actually got it working. Oh...

Part 1 was a breeze, and I even correctly predicted a good chunk of part 2. I then proceeded to muck about making mistake after mistake with the cycle index until I actually got it working. Oh well, I'm still pleased with how most of my solution turned out, especially tilting in a single line!

``````{-# LANGUAGE NumericUnderscores #-}

module Main (main) where

import Data.List (transpose, sort, intercalate, elemIndex)
import AOCTools (splitBy)

main :: IO ()
main = do
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 platform = sum \$ zipWith (*) [1..] rowCounts where
rowCounts = map (length . filter (=='O')) (reverse platform)

solve1 :: [String] -> Int

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
``````
1 vote
4. whs
Two more languages to go. And of course it has to be Go today. I learned Go on the job during my first year. My first large open source contribution was written in Go (dnscontrol), and the...

Two more languages to go. And of course it has to be Go today. I learned Go on the job during my first year. My first large open source contribution was written in Go (dnscontrol), and the maintainer even blogged that he have seen many new contributor mention that it was their first Go code.

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() {
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))
}

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
}

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
}
``````
1 vote
5. first-must-burn
(edited )
Golang solution Not much to say about the solution -- it was a straightforward simulation. I continue to get a lot of use out of my Grid class when I need to deal with directions in the grid. I...

Golang solution

Not much to say about the solution -- it was a straightforward simulation. I continue to get a lot of use out of my Grid class when I need to deal with directions in the grid.

I had to stop doing the puzzles at midnight as it was messing up my sleep cycle, but I was able to get the solution in about an hour, which is okay for me. I wish the leaderboard had times on it so I could compare my own start time. I seem to remember this from previous years, but I can't find it now. But I'm not losing much because I haven't come close to breaking the top 1000 yet.

For grins, I ran an estimate of the time to finish the brute force solution to part 2. Without any attempt to optimize, it was around 108 days.

1 vote
6. lily
Forgot to post this last night. I wasn't quite able to get top 1000 on part 2, but thought I did pretty well otherwise. Part 2 was pretty simple once I realized I needed to detect cycles. Solution...

Forgot to post this last night. I wasn't quite able to get top 1000 on part 2, but thought I did pretty well otherwise. Part 2 was pretty simple once I realized I needed to detect cycles.

Solution
``````# 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)

for y, row in enumerate(platform):
for char in row:
if char == "O":

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:
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

``````
1 vote
7. jzimbel
Elixir For some reason I have a lot of trouble wrapping my head around the math/logic to extrapolate a repeating sequence of values, not starting at index 0, to the nth element. This time, after...

Elixir

For some reason I have a lot of trouble wrapping my head around the math/logic to extrapolate a repeating sequence of values, not starting at index 0, to the nth element. This time, after working it out again, I actually bothered to write a little function to do it. No more tears on these problems in the future. ðŸ¥²

New `Sequence` module

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
``````
Part 1 and part 2

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

def part1(input) do
input
|> G.from_input()
|> tilt(:n)
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])