Advent of Code 2023 - Day 14

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.

https://github.com/lud/adventofcode/blob/main/lib/solutions/2023/day14.ex

https://github.com/tywhisky/advent-of-code/blob/master/2023/day_14/solution.exs

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 -

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2023/day14.ex

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.

Not my proudest solve but it works:

https://github.com/woojiahao/aoc/blob/main/lib/aoc/2023/day_14.ex

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

• 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

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)

Part 1

dish |> tilt.() |> load.()

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)
|> load.()

Not proud of this solution, although runs under 3 seconds for part two.
A few comments:

• 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"
    |> 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()