# Advent of Code 2023 - Day 14

My solution finishes both parts in 5 seconds on my computer. That time should be possible to reduce by optimizing my rather naive tilt/2 function, but I decided to instead optimize the use of my time and leave as is.

My solution:

3 Likes

My beginnerâ€™s solution, Day 14 part 1. Parabolic Reflector Dish

defmodule Day14 do
def part1(input), do:
input
|> String.split("\n")
|> Enum.map(&String.graphemes/1)
|> List.zip
|> Enum.reduce(0, fn column, acc -> column
|> Tuple.to_list
|> Enum.chunk_by(&(&1=="#"))
|> Enum.map(&Enum.sort(&1, :desc))
|> List.flatten
|> Enum.reverse
|> Enum.with_index(1)
|> then(&(for {"O", n} <- &1, reduce: 0 do acc -> acc + n end))
|> Kernel.+(acc)
end)
end
3 Likes

My solution completes part 2 in less than a second but I have the same feeling that the tilt could be improved.

I lost so much time with wrong scores until I decided to print all scores in the loop and see that 64 was never coming. This was because my scoring function works with northbound rows but each cycle leaves the platform in eastbound rows.

So I had to add that final rotate() before scoring and it was fine:

rows_loop_start
|> apply_cycles(cycles_left)
|> rotate()
|> score()

But before I lost like 30 minutes to re-learn the concepts of division, multiplication, remainders and allâ€¦ My 2nd grade teacher would be proud.

1 Like
Part 1

I use a queue to save the index of â€ś.â€ť each I saw when recursive.
If I met â€ś#â€ť, empty the queue.
If I met â€śOâ€ť, replace the position by List.replace/3

Part 2

I just use four times Enum.zip/1 for four directions, the rocks move as same as Part 1.

Regarding that loop of 1000000000 iterations, when encountering a number of this magnitude, I realized the need for a modulus operation. I located the starting point and the endpoint of the loop in the input, enabling me to skip redundant segments and calculate the final result directly. Itâ€™s worth noting the off-by-one issue.

oh hey I didnâ€™t know these threads were a thing!

Iâ€™ve been cataloging all my daily solutions on GitHub, todayâ€™s is here -

It can still probably be optimized a heap, because I rewrote big parts to get part 2 to work, so some of the old parts probably suck. But part 2 runs in 1.5 seconds so thatâ€™s good enough for me.

Notes:

• I have a previously-created PathGrid helper module that takes a grid like this one and turns it into a grid with walls (the static rocks), floor, and units (the rollable rocks)
• Two stages for each tilt - roll and unstack
• roll ignores the presence of other rollable rocks, and moves each rock as far as it can in the right direction
• unstack takes each pile of rocks at the same coordinate, and unstacks them in the right direction
• Part 2 does the same thing as other people - find when there is a loop in the output after each spin, then you can work out what the end result would be by fastforwarding.
1 Like

Not my proudest solve but it works:

Will look at the other solutions to see how to better tackle this

1 Like
• I keep my north on the right, so that I can just multiply the rock value with its index then add them up.
• Tilt to the west = rotate the whole dish 90 degree clockwise then tilt to the north.

## Input parsing

Here I map each rounded rock ?O to 1 because each rounded rock generates 1 * index unit of load.

I map each empty space ?. to 0 because itâ€™s empty and thus generates no load.

I map each square rock ?# to 0.0 because it also generates no load, but itâ€™s different than a ?.. Later we can see that when the dish is tilted, the integers can move around, while the float number 0.0 canâ€™t.

dish =
puzzle_input
|> String.split("\n")
|> Enum.map(&String.to_charlist/1)
|> Enum.map(fn line ->
Enum.map(line, fn
?O -> 1
?. -> 0
?# -> 0.0
end)
end)

## Function to rotate the dish

Rotating 90 degree clockwise is equivalent to vertically flipping 180 degree then transpose.

rotate = fn dish ->
dish
|> Enum.reverse()
|> Enum.zip_with(&Function.identity/1)
end

## Function to tilt the dish to the north

line |> Stream.chunk_by(&is_integer/1) puts the rounded rocks (mapped to 1) and empty spaces (mapped to 0) to the same chunk so they can swap their positions, while square rocks (mapped to 0.0) are grouped with no rounded rocks nor empty spaces, so they canâ€™t move. Sorting each chunk moves the rounded stones to the right side (north) in their own chunks.

tilt = fn dish ->
dish
|> Enum.map(fn line ->
line
|> Stream.chunk_by(&is_integer/1)
|> Enum.map(&Enum.sort/1)
|> List.flatten()
end)
end

## Function to calculate the total load

dish
|> Stream.map(fn line ->
line
|> Stream.with_index(1)
|> Stream.map(&Tuple.product/1)
|> Enum.sum()
end)
|> Enum.sum()
|> trunc()
end

Finally, we need to rotate the input once so that the north is on the right.

dish = rotate.(dish)

## Part 2

cycle = fn dish ->
dish
|> tilt.()
|> rotate.()
|> tilt.()
|> rotate.()
|> tilt.()
|> rotate.()
|> tilt.()
|> rotate.()
end

before_loop_start =
{dish, MapSet.new()}
|> Stream.iterate(fn {dish, seen} ->
{cycle.(dish), MapSet.put(seen, dish)}
end)
|> Enum.find_index(fn {dish, seen} -> dish in seen end)

loop_length =
dish
|> Stream.iterate(cycle)
|> Stream.drop(before_loop_start)
|> Enum.reduce_while(MapSet.new(), fn dish, seen ->
if dish in seen do
{:halt, seen}
else
{:cont, MapSet.put(seen, dish)}
end
end)
|> MapSet.size()

remainder = rem(1_000_000_000 - before_loop_start + loop_length, loop_length)

dish
|> Stream.iterate(cycle)
|> Enum.at(before_loop_start - loop_length + remainder)
1 Like

Not proud of this solution, although runs under 3 seconds for part two.

• This is probably the worst bit: I did not specifically look for when the repeated cycle begins, I just tried a few numbers for the length of the initial run. The point is that as long as itâ€™s enough to get into the cycles, it will be good enough to find the cycle length. The upside is that I only need two grids at any given time.
• As others, just one direction of tilting (for me the easiest seemed â€śto the leftâ€ť), and use grid transformations to get the other directions. This could definitely be optimised.
defmodule Main do
def run() do
get_input()
|> Enum.map(&String.to_charlist/1)
# |> solve1()
|> solve2()
end

def get_input() do
# "testinput14"
"input14"
|> String.trim()
|> String.split("\n")
end

def transpose(ls) do
ls |> List.zip() |> Enum.map(&Tuple.to_list/1)
end

def flip_lr(ls) do
ls |> Enum.map(&Enum.reverse/1)
end

def flip_ud(ls) do
ls |> Enum.reverse()
end

def tilt_row_left(l) do
(l ++ ~c"#")
|> Enum.reduce({~c"", ~c"", ~c""}, fn c, {lsf, os, ds} ->
# state: { line_so_far, accumulated_O_s, accumulated_dots }
case c do
?. -> {lsf, os, ds ++ ~c"."}
?O -> {lsf, os ++ ~c"O", ds}
?# -> {lsf ++ os ++ ds ++ ~c"#", ~c"", ~c""}
end
end)
|> elem(0)
|> Enum.drop(-1)
end

def count_os(l) do
l |> Enum.filter(fn c -> c == ?O end) |> Enum.count()
end

def value(ls) do
ls
|> Enum.map(&count_os/1)
|> Enum.reverse()
|> Enum.with_index(1)
|> Enum.map(fn {n,i} -> n*i end)
|> Enum.sum()
end

def solve1(ls) do
ls
# |> IO.inspect(width: 20)
|> transpose()
|> Enum.map(&tilt_row_left/1)
|> transpose()
# |> IO.inspect(width: 20)
|> value()
end

def cycle(ls) do
ls |> transpose() |> Enum.map(&tilt_row_left/1)
|> transpose() |> Enum.map(&tilt_row_left/1) # after N,W, oriented orig
|> transpose() |> flip_lr() |> Enum.map(&tilt_row_left/1)
|> transpose() |> flip_lr() |> Enum.map(&tilt_row_left/1)
|> flip_ud() |> flip_lr()
end

def run_cycles(ls, n) do
1..n |> Enum.reduce(ls, fn _, gg -> cycle(gg) end)
end

def solve2(ls) do
initial = 150
ee = run_cycles(ls,initial)
period = 1 .. 1_000
|> Enum.reduce_while(ee, fn n, gg ->
if (ng = cycle(gg)) == ee do {:halt, n} else {:cont, ng} end
end)
run_cycles(ee, rem(1_000_000_000 - initial,period))
|> value()
end

end

:timer.tc(&Main.run/0)
|> IO.inspect()
2 Likes

I am not sure if I had fun doing it or I did not have fun doing it. Took way longer experimenting with the rotational logic than I should have.

def run(input \\ input()) do
input = parse(input)

{run_1(input), run_2(input)}
end

defp run_1(input), do: input |> tilt() |> get_load()

@cycle 1_000_000_000
def run_2(input) do
1..@cycle
|> Enum.reduce_while({input, %{}}, fn idx, {dish, cache} ->
new_dish = roll(dish)
hash = :erlang.phash2(new_dish)

case cache[hash] do
nil ->
{:cont, {new_dish, Map.put(cache, hash, idx)}}

existing_idx ->
diff = idx - existing_idx
{:halt, {new_dish, @cycle - div(@cycle - existing_idx, diff) * diff - existing_idx - 1}}
end
end)
|> then(fn {dish, n} -> Enum.reduce(0..n, dish, fn _, acc -> roll(acc) end) end)
end

def parse(data \\ input()) do
data
|> Transformers.lines()
|> Enum.map(&String.graphemes/1)
|> turn()
end

defp roll(dish), do: Enum.reduce(1..4, dish, fn _, acc -> turn(tilt(acc)) end)

defp tilt(dish) do
Enum.map(dish, fn row ->
row
|> Enum.chunk_by(&(&1 == "#"))
|> Enum.map(&Enum.sort/1)
|> Enum.flat_map(& &1)
end)
end

defp turn(dish) do
dish
|> Transformers.transpose()
|> Enum.map(&Enum.reverse/1)
end

tilted_dish
|> Enum.flat_map(fn row -> Enum.with_index(row, 1) end)
|> Enum.reduce(0, fn {value, idx}, acc -> acc + ((value == "O" && idx) || 0) end)
end
end
1 Like

I didnâ€™t have fun cuz it was too late at night, and I really wanted to sleep

1 Like

Started out generalizing part 1 cause I figured that would come up in part 2. Iâ€™m thinking I overcomplicated things a bit though after looking at some of yâ€™allâ€™s solutions.

Part 1
defmodule Part1 do
defstruct [:cs, :rs, :sz]
alias __MODULE__, as: P

def parse(input) do
lines =
input
|> String.split("\n", trim: true)

sz = length(lines)

{cs, rs} =
for {line, y} <- lines |> Enum.with_index(),
{char, x} <- String.graphemes(line) |> Enum.with_index(),
reduce: {MapSet.new(), MapSet.new()} do
{cs, rs} ->
case char do
"#" -> {MapSet.put(cs, [y, x]), rs}
"O" -> {cs, MapSet.put(rs, [y, x])}
_ -> {cs, rs}
end
end

%P{cs: cs, rs: rs, sz: sz}
end

def stringify(%P{cs: cs, rs: rs, sz: sz}) do
for y <- 0..(sz - 1) do
for x <- 0..(sz - 1) do
coord = [y, x]

cond do
MapSet.member?(cs, coord) -> "#"
MapSet.member?(rs, coord) -> "O"
true -> "."
end
end
|> Enum.join()
|> Kernel.<>("\n")
end
|> Enum.join()
end

def print(%P{} = p) do
p
|> stringify()
|> IO.puts()
end

def tilt(%P{} = p, :north), do: tilt(p, [1, 0])
def tilt(%P{} = p, :west), do: tilt(p, [0, 1])
def tilt(%P{} = p, :south), do: tilt(p, [-1, 0])
def tilt(%P{} = p, :east), do: tilt(p, [0, -1])

def tilt(%P{cs: cs, sz: sz} = p, delta) do
axis = Enum.find_index(delta, &(&1 != 0))
axis_delta = Enum.at(delta, axis)
axis_pos = if axis_delta < 0, do: sz - 1, else: 0

0..(sz - 1)
|> Stream.map(fn off_axis_pos ->
off_axis_pos
|> List.duplicate(2)
|> List.replace_at(axis, axis_pos)
end)
|> Stream.concat(
for coord <- cs do
List.update_at(coord, axis, &(&1 + axis_delta))
end
)
|> Enum.reduce(p, fn initial, p ->
roll(p, initial, delta)
end)
end

def roll(
%P{cs: cs, rs: rs, sz: sz} = p,
initial,
delta
) do
axis = Enum.find_index(delta, &(&1 != 0))
axis_delta = Enum.at(delta, axis)
axis_limit = if axis_delta < 0, do: -1, else: sz
init_axis_pos = Enum.at(initial, axis)
off_axis_pos = Enum.at(initial, 1 - axis)

rs =
init_axis_pos..axis_limit//axis_delta
|> Stream.map(fn axis_pos ->
off_axis_pos
|> List.duplicate(2)
|> List.replace_at(axis, axis_pos)
end)
|> Stream.take_while(fn coord -> not MapSet.member?(cs, coord) end)
|> Stream.filter(fn coord -> MapSet.member?(rs, coord) end)
|> Stream.with_index()
|> Enum.reduce(rs, fn {coord, offset}, rs ->
rs
|> MapSet.delete(coord)
|> MapSet.put(List.replace_at(coord, axis, init_axis_pos + offset * axis_delta))
end)

%P{p | rs: rs}
end

def total_load(%P{rs: rs, sz: sz}) do
rs
|> Enum.map(fn [y, _] -> sz - y end)
|> Enum.sum()
end
end

input
|> Part1.parse()
|> Part1.tilt(:north)
Part 2
defmodule Part2 do
alias Part1, as: P

def spin(%P{} = p) do
p
|> P.tilt(:north)
|> P.tilt(:west)
|> P.tilt(:south)
|> P.tilt(:east)
end
end

p = Part1.parse(input)

{p, c0, c1} =
Stream.iterate(1, &(&1 + 1))
|> Enum.reduce_while({p, %{}, -1}, fn i, {p, acc, c} ->
p = Part2.spin(p)
s = Part1.stringify(p)
acc = Map.update(acc, s, 1, &(&1 + 1))

cond do
acc[s] == 3 ->
{:halt, {p, c, i - c}}

acc[s] == 2 and c < 0 ->
{:cont, {p, acc, i}}

true ->
{:cont, {p, acc, c}}
end
end)

n = rem(1_000_000_000 - (c0 + c1), c1)
1..n
|> Enum.reduce(p, fn _, p -> Part2.spin(p) end)

Iâ€™ve only done part 1 and realized I was trying to be too clever and have to redo the whole thing for part 2. I thought I would be able to basically do a single pass by pattern matching on binaries but it didnâ€™t work out and I just wanted to get an answer.

defmodule Day14 do
@moduledoc """
Day14 AoC Solutions
"""

alias AocToolbox.Input

def input(:test),
do: """
O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....
"""
def input(:real), do: Input.load(__DIR__ <> "/input.txt")

def solve(1, mode) do
__MODULE__.Part1.solve(input(mode))
end

def solve(2, mode) do
__MODULE__.Part2.solve(input(mode))
end

defmodule Part1 do
def solve(input) do
{rock_map, _, max_cols, max_rows} = parse(input)
IO.inspect({max_cols, max_rows})

0..(max_cols - 1)
|> Enum.reduce(rock_map, fn col, r_m ->
case Map.get(r_m, col) do
nil -> r_m
cells -> Map.put(r_m, col, roll_rocks(cells))
end
end)
|> Enum.reduce(0, fn {k, bin}, sum -> sum_bin(bin, max_rows) + sum end)
end

defp sum_bin(bin, max_row, acc \\ 0)
defp sum_bin(<<>>, _, acc), do: acc |> IO.inspect()

defp sum_bin(<<row::8, 1::8, rest::binary>>, max_row, acc),
do: sum_bin(rest, max_row, acc + max_row - row)

defp sum_bin(<<_row::8, 0::8, rest::binary>>, max_row, acc), do: sum_bin(rest, max_row, acc)

defp roll_rocks(column, roll_to \\ nil, acc \\ <<>>)
defp roll_rocks(<<>>, _, acc), do: acc
# no more rocks, if this one can roll it rolls all the way to the to
defp roll_rocks(<<row::8, roller?::8>>, nil, acc) when roller? == 1,
do: <<acc::binary, 0, roller?>>

defp roll_rocks(<<row::8, roller?::8>>, roll_to, acc) when roller? == 1,
do: <<acc::binary, 1 + roll_to, roller?>>

# no more rocks but this one cannot roll so it stays put
defp roll_rocks(<<row::8, roller?::8>>, _, acc), do: <<acc::binary, row, roller?>>

# top remaining rock can roll up to last rock
defp roll_rocks(<<_row::8, roller?::8, rest::binary>>, nil, acc)
when roller? == 1,
do: roll_rocks(rest, 0, <<acc::binary, 0::8, roller?::8>>)

defp roll_rocks(<<_row::8, roller?::8, rest::binary>>, roll_to, acc)
when roller? == 1,
do: roll_rocks(rest, 1 + roll_to, <<acc::binary, 1 + roll_to::8, roller?::8>>)

# top remaining rock cannot roll so becomes the next blocker
defp roll_rocks(<<row::8, 0::8, rest::binary>>, _, acc),
do: roll_rocks(rest, row, <<acc::binary, row::8, 0::8>>)

def parse(input) do
input
|> String.graphemes()
|> Enum.reduce({%{}, 0, 0, 0}, fn g, {acc, column, max_column, row} ->
case g do
"." ->
{acc, column + 1, max_column, row}

"O" ->
{Map.update(acc, column, <<row, 1>>, fn curr -> <<curr::binary, row, 1>> end),
column + 1, max_column, row}

"#" ->
{Map.update(acc, column, <<row, 0>>, fn curr -> <<curr::binary, row, 0>> end),
column + 1, max_column, row}

"\n" ->
{acc, 0, max(max_column, column), row + 1}
end
end)
end
end
end

Trying to figure out why my rotation and tilt approach is not ever finding a repeat. Can anyone tell me how many iterations it took them to get the cycle in the example data?

In the example, the repeating part begins after three cycles, and it is seven cycles long.

1 Like