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:
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:
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
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.
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
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:
roll
and unstack
roll
ignores the presence of other rollable rocks, and moves each rock as far as it can in the right directionunstack
takes each pile of rocks at the same coordinate, and unstacks them in the right directionNot my proudest solve but it works:
Will look at the other solutions to see how to better tackle this
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)
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
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
load = fn dish ->
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)
dish |> tilt.() |> load.()
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)
|> load.()
Not proud of this solution, although runs under 3 seconds for part two.
A few comments:
defmodule Main do
def run() do
get_input()
|> Enum.map(&String.to_charlist/1)
# |> solve1()
|> solve2()
end
def get_input() do
# "testinput14"
"input14"
|> File.read!()
|> 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()
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.
defmodule AdventOfCode.Y2023.Day14 do
alias AdventOfCode.Helpers.{InputReader, Transformers}
def input, do: InputReader.read_from_file(2023, 14)
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)
|> get_load()
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
defp get_load(tilted_dish) do
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
I didn’t have fun cuz it was too late at night, and I really wanted to sleep
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.
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)
|> Part1.total_load()
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)
|> Part1.total_load()
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.