import AOC

aoc 2023, 13 do
  def p1(input) do
    {xs, ys} = input |> grids() |> Enum.map(&calculate/1) |> Enum.unzip()
    combine = fn items -> items |> List.flatten() |> Enum.map(fn n -> (1 + n)/2 end) |> Enum.sum() end
    100*combine.(xs) + combine.(ys)
  end

  def p2(input) do
    {xs, ys} = input |> grids() |> Enum.map(&calculate_with_smudge/1) |> Enum.unzip()
    combine = fn items -> items |> List.flatten() |> Enum.map(fn n -> (1 + n)/2 end) |> Enum.sum() end
    100*combine.(xs) + combine.(ys)
  end

  def calculate(grid) do
    grid = grid |> Enum.map(fn {x, y} -> {2*x, 2*y} end) |> MapSet.new
    max_x = max_(grid, &get_x/1)
    max_y = max_(grid, &get_y/1)
    {1..max_x//2 |> Enum.filter(fn i -> x_reflect?(grid, i, max_x) end),
     1..max_y//2 |> Enum.filter(fn i -> y_reflect?(grid, i, max_y) end)}
  end

  @spec calculate_with_smudge(any()) :: {list(), list()}
  def calculate_with_smudge(grid) do
    {original_xs, original_ys} = calculate(grid)
    grid_set = grid |> MapSet.new()
    max_x = max_(grid_set , &get_x/1)
    max_y = max_(grid_set, &get_y/1)
    for x <- 0..max_x, y <- 0..max_y do
      calculate(invert(grid_set, {x, y}))
    end
    |> Enum.reject(fn {[], []} -> true; _ -> false end)
    |> Enum.reduce(fn {x, y}, {x2, y2} -> {x ++ x2, y ++ y2} end)
    |> then(fn {xs, ys} -> {Enum.uniq(xs) -- original_xs, Enum.uniq(ys) -- original_ys} end)
   end

  def invert(grid, p) do
    if MapSet.member?(grid, p) do
      MapSet.delete(grid, p)
    else
      MapSet.put(grid, p)
    end
  end

  def get_x({x, _}), do: x
  def get_y({_, y}), do: y

  def max_(grid, f), do: Enum.max_by(grid, f) |> then(f)

  def x_reflect?(grid, i, max) do
    grid
    |> Enum.group_by(&get_y/1)
    |> Enum.all?(
      fn {_, row} ->
        Enum.all?(
          row,
          fn {x, y} -> x_r = i + i - x; x_r > max || x_r < 0 || Enum.member?(grid, {x_r, y}) end
        )
      end)
  end

  def y_reflect?(grid, i, max) do
    grid
    |> Enum.group_by(&get_x/1)
    |> Enum.all?(
      fn {_, col} ->
        Enum.all?(
          col,
          fn {x, y} -> y_r = i + i - y; y_r > max  || y_r < 0 || Enum.member?(grid, {x, y_r}) end
        )
      end)
  end

  def grid(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index
    |> Enum.flat_map(
      fn {line, row} ->
        line
        |> String.split("", trim: true)
        |> Enum.with_index
        |> Enum.map(fn {char, col} -> {{row, col}, char} end)
        |> Enum.filter(fn {_, char} -> char == "#" end)
        |> Enum.map(&elem(&1, 0))
      end)
  end

  def grids(input) do
    input |> String.split("\n\n") |> Enum.map(&grid/1)
  end
end

Easier than yesterday

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

Today I learnt that you can match a 0-length binary part in a patter.

Each pattern is a list of string, so to change a smudge I need to update the string at list index Y and change a character in that string at index X. The following code works when X is zero.

  defp stream_changes(pattern) do
    yo = length(pattern) - 1
    xo = (pattern |> hd() |> String.length()) - 1

    Stream.resource(
      fn -> {0, 0} end,
      fn
        {_, y} when y > yo -> raise "expleted"
        {x, y} when x > xo -> {[], {0, y + 1}}
        {x, y} -> {[fix_pattern(pattern, x, y)], {x + 1, y}}
      end,
      fn _ -> nil end
    )
  end

  defp fix_pattern(pattern, x, y) do
    List.update_at(pattern, y, fn <<prev::binary-size(x), c, rest::binary>> ->
      new_c =
        case c do
          ?. -> ?#
          ?# -> ?.
        end

      <<prev::binary-size(x), new_c, rest::binary>>
    end)
  end

I used Stream.resource instead of Stream.unfold because it lets you return an empty list, which is convenient to reset the stream state to X=0 and Y+1.

I’m so not proud of my code. Just a pile of junk. Ctrl+C & Ctrl+V everywhere. Anyway, I post it here.

https://github.com/Aetherus/advent-of-code/blob/master/2023/day-13.livemd

I have optimized the code as much as possible to make it appear more comprehensible. If there are any parts that someone doesn’t understand, I am more than willing to add additional comments.

Solution

The approach I took for solving part 1 was not useful for part 1, so I had to rewrite my solver so that it was able to handle part 2.

My solution:

https://github.com/bjorng/advent-of-code-2023/blob/main/day13/lib/day13.ex

Nice usage of bit strings

Day 13

Setup

defmodule Day13 do
  def find_axes(list) do
    reversed = Enum.reverse(list)

    len = length(list)

    back = dbg(do_find(list, 0))
    front = dbg(do_find(reversed, 0))

    [
      if(back, do: div(len - back, 2) + back),
      if(front, do: div(len - front, 2))
    ]
    |> Enum.filter(& &1)
  end

  defp do_find([_], _), do: nil

  defp do_find([_ | a], n) when rem(n, 2) == 0, do: do_find(a, n + 1)

  defp do_find(a, n) do
    if palindrome?(a) do
      n
    else
      do_find(tl(a), n + 1)
    end
  end

  def palindrome?(list) do
    list == Enum.reverse(list)
  end

  def print_mirror({rows, cols, _, _}) do
    width = length(cols)

    display =
      for row <- rows do
        for digit <- Integer.digits(row, 2) do
          if digit == 1, do: "#", else: "."
        end
        |> List.to_string()
        |> String.pad_leading(width, ".")
      end

    IO.puts(Enum.intersperse(display, "\n"))
  end
end

mirrors =
  puzzle_input
  |> String.split("\n\n", trim: true)
  |> Enum.map(fn grid ->
    mirror =
      grid
      |> String.split("\n", trim: true)
      |> Enum.map(fn line ->
        for <<c <- line>>, do: if(c == ?#, do: 1, else: 0)
      end)

    rows = Enum.map(mirror, &Integer.undigits(&1, 2))
    cols = Enum.zip_with(mirror, &Integer.undigits(&1, 2))

    row = Day13.find_axes(rows)
    col = Day13.find_axes(cols)

    {rows, cols, row, col}
  end)

Part 1

Enum.map(mirrors, fn {_, _, row, col} ->
  List.first(col, 0) + List.first(row, 0) * 100
end)
|> Enum.sum()

Part 2

defmodule Day13.Part2 do
  import Bitwise

  def alternatives(list, a, n) do
    l = length(list)

    list =
      for i <- 0..n,
          d = bsl(1, i),
          j <- 0..l,
          desmudged = List.update_at(list, j, &bxor(&1, d)),
          v <- Day13.find_axes(desmudged),
          v not in a,
          do: v

    Enum.dedup(list)
  end
end

mirrors
|> Enum.with_index()
|> Enum.map(fn {{rows, cols, row, col}, _idx} ->
  row = List.first(Day13.Part2.alternatives(rows, row, length(cols)), 0)
  col = List.first(Day13.Part2.alternatives(cols, col, length(rows)), 0)

  row * 100 + col
end)
|> Enum.sum()

My beginner’s solution, Day 13 part 1. Point of Incidence

defmodule Day13 do

  def part1(input) do
    parse(input)
    |> Enum.map(fn pattern -> pattern
         |> reflection()
         |> case do 
              index when is_number(index) -> 100 * index
              list -> Enum.reverse(list) |> List.zip |> Enum.map(&Tuple.to_list/1) |> reflection()
            end |> tap(&IO.puts(&1))
       end)
    |> Enum.sum
  end

  def reflection(righthand, lefthand \\ [])
  def reflection([head | tail], []), do: reflection(tail, [head])
  def reflection([head | tail], lefthand) do
    length = [[head|tail], lefthand]
      |> Enum.map(&length/1)
      |> Enum.min

    if Enum.take([head|tail], length) == Enum.take(lefthand, length) do
      length(lefthand)
    else
      reflection(tail, [head | lefthand])
    end
  end
  def reflection([], lefthand), do: lefthand # now it's reversed

  def parse(raw_note) do
    raw_note
    |> String.split("\n\n")
    |> Enum.map(&parse_pattern/1)
  end
  def parse_pattern(raw_pattern) do
    raw_pattern
    |> String.split("\n")
    |> Enum.map(&parse_line/1)
  end
  def parse_line(raw_line) do
    raw_line
    |> String.graphemes
    |> Enum.map(&(case &1 do "." -> :ash; "#" -> :rock; end))
  end
    
end

Went with Nx again for today’s problem.

defmodule Part1 do
  def parse(input) do
    for pattern <- String.split(input, "\n\n") do
      for line <- String.split(pattern, "\n", trim: true) do
        String.graphemes(line)
        |> Enum.map(fn c -> if c == "#", do: 1, else: 0 end)
      end
      |> Nx.tensor(type: :u8, names: [:y, :x])
    end
  end

  def summarize(patterns) do
    for pattern <- patterns do
      {axis, {index, _}} =
        reflect(pattern)

      left = index + 1
      if axis == :x, do: left, else: 100 * left
    end
    |> Enum.sum()
  end

  def reflect(pattern) do
    [:x, :y]
    |> Enum.map(fn axis -> {axis, reflect_along(pattern, axis)} end)
    |> Enum.max_by(fn {_, {_, size}} -> size end)
  end

  def reflect_along(pattern, axis) do
    0..Nx.axis_size(pattern, axis)
    |> Enum.reduce({-1, -1}, fn index, {_, prev_size} = prev ->
      {_, next_size} = next = reflect_at(pattern, axis, index)
      if next_size > prev_size, do: next, else: prev
    end)
  end

  def reflect_at(pattern, axis, index), do: reflect_at(pattern, axis, index, index + 1)

  def reflect_at(pattern, axis, left, right) do
    if left < 0 or right >= Nx.axis_size(pattern, axis) do
      reflection(left + 1, right - 1)
    else
      left_tensor = pattern[Keyword.new([{axis, left}])]
      right_tensor = pattern[Keyword.new([{axis, right}])]

      if left_tensor != right_tensor do
        {-1, -1}
      else
        reflect_at(pattern, axis, left - 1, right + 1)
      end
    end
  end

  def reflection(left, right) when left > right, do: {-1, -1}

  def reflection(left, right) do
    size = div(right - left, 2)
    {left + size, size}
  end
end

input
|> Part1.parse()
|> Part1.summarize()

defmodule Part2 do
  def summarize(patterns) do
    for pattern <- patterns do
      {axis, {index, _}} =
        reflect(pattern)

      left = index + 1
      if axis == :x, do: left, else: 100 * left
    end
    |> Enum.sum()
  end

  def reflect(pattern) do
    [:x, :y]
    |> Enum.map(fn axis -> {axis, reflect_along(pattern, axis)} end)
    |> Enum.max_by(fn {_, {_, size}} -> size end)
  end

  def reflect_along(pattern, axis) do
    0..Nx.axis_size(pattern, axis)
    |> Enum.reduce({-1, -1}, fn index, prev ->
      {start, size, smudge} = reflect_at(pattern, axis, index)
      if smudge, do: {start, size}, else: prev
    end)
  end

  def reflect_at(pattern, axis, index), do: reflect_at(pattern, axis, index, index + 1, false)

  def reflect_at(pattern, axis, left, right, smudge) do
    if left < 0 or right >= Nx.axis_size(pattern, axis) do
      reflection(left + 1, right - 1, smudge)
    else
      left_tensor = pattern[Keyword.new([{axis, left}])]
      right_tensor = pattern[Keyword.new([{axis, right}])]

      if left_tensor != right_tensor do
        if smudge or
             Nx.equal(left_tensor, right_tensor)
             |> Nx.logical_not()
             |> Nx.sum() != Nx.tensor(1, type: :u64) do
          {-1, -1, false}
        else
          reflect_at(pattern, axis, left - 1, right + 1, true)
        end
      else
        reflect_at(pattern, axis, left - 1, right + 1, smudge)
      end
    end
  end

  def reflection(left, right, _) when left > right, do: {-1, -1, false}

  def reflection(left, right, smudge) do
    size = div(right - left, 2)
    {left + size, size, smudge}
  end
end

input
|> Part1.parse()
|> Part2.summarize()

I probably over complicated parsing the input, but it worked really well. One thing that got highlighted (for me again) was that the :ets module is kind of non-ergonomic. Like there’s no update_or_insert or insert_new type of functions. I was feeling pretty clever about how easy it was to add the smudge factor to part 1 and make it reusable.

defmodule Day13 do
  @moduledoc """
  Day13 AoC Solutions
  """

  alias AocToolbox.Input

  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, smudges \\ 0) do
      :ets.new(:grids, [:set, :protected, :named_table])

      solution =
        input
        |> parse()
        |> grids_to_ets()
        |> find_symmetry(smudges)

      :ets.delete(:grids)
      solution
    end

    def parse(input) do
      input
      |> String.split("\n\n")
      |> Enum.map(&Input.lines/1)
      |> Enum.with_index()
      |> Enum.flat_map(&stream_to_grid/1)
    end

    defp stream_to_grid({stream, grid}) do
      stream
      |> Enum.with_index()
      |> Enum.flat_map(fn {line, row} ->
        line
        |> String.graphemes()
        |> Enum.with_index()
        |> Enum.map(fn {g, col} -> {{grid, row, col}, g} end)
      end)
    end

    defp grids_to_ets(grids) do
      for {{g, r, c}, v} <- grids, reduce: 0 do
        gg ->
          :ets.insert(:grids, {{g, r, c}, v})

          [{:max_row, r}, {:max_col, c}]
          |> Enum.each(fn {max, i} ->
            if :ets.member(:grids, {g, max}) do
              :ets.update_element(
                :grids,
                {g, max},
                {2, max(i, :ets.lookup_element(:grids, {g, max}, 2))}
              )
            else
              :ets.insert(:grids, {{g, max}, i})
            end
          end)

          max(g, gg)
      end
    end

    defp find_symmetry(max_grid, smudges) do
      0..max_grid
      |> Task.async_stream(fn g ->
        max_row = :ets.lookup_element(:grids, {g, :max_row}, 2)
        max_col = :ets.lookup_element(:grids, {g, :max_col}, 2)

        grid = get_grid(g, max_row, max_col)

        Enum.find_value([{1, max_row}, {2, max_col}], fn {orientation, max} ->
          find_axis(grid, max, orientation, smudges)
        end)
      end)
      |> Enum.reduce({0, 0}, fn {:ok, {axis, n}}, {verts, horizs} ->
        case axis do
          :vertical -> {verts + n, horizs}
          :horizontal -> {verts, horizs + n * 100}
        end
      end)
      |> Tuple.to_list()
      |> Enum.sum()
    end

    defp get_grid(grid, max_row, max_col) do
      for r <- 0..max_row,
          c <- 0..max_col do
        :ets.lookup(:grids, {grid, r, c})
      end
    end

    defp find_axis(grid, max, orientation, smudges) when orientation in [1, 2] do
      grid
      |> Enum.group_by(fn [{k, _v}] ->
        elem(k, orientation)
      end)
      |> do_find_axis(max, 1, elem({:horizontal, :vertical}, orientation - 1), smudges)
    end

    defp do_find_axis(rows_or_cols, max, maybe_axis \\ 1, orientation, smudges)

    defp do_find_axis(_rows_or_cols, max, maybe_axis, _orientation, _smudges)
         when max < maybe_axis,
         do: false

    defp do_find_axis(rows_or_cols, max, maybe_axis, orientation, smudges) do
      case 0..(maybe_axis - 1)
           |> Enum.map(fn i -> {i, 2 * maybe_axis - 1 - i} end)
           |> Enum.filter(fn {l, r} -> r <= max end)
           |> Enum.reduce_while(smudges, fn {l, r}, acc ->
             case acc - count_diffs(l, r, rows_or_cols, orientation) do
               n when n < 0 -> {:halt, false}
               n -> {:cont, n}
             end
           end) do
        0 ->
          {orientation, maybe_axis}

        _ ->
          do_find_axis(rows_or_cols, max, maybe_axis + 1, orientation, smudges)
      end
    end

    defp count_diffs(l, r, groups, orientation) do
      [l, r] =
        [l, r]
        |> Enum.map(fn i ->
          groups[i]
          |> Enum.map(fn [{k, v}] ->
            case orientation do
              :horizontal -> {elem(k, 2), v}
              :vertical -> {elem(k, 1), v}
            end
          end)
        end)
        |> Enum.map(fn elems -> MapSet.new(elems) end)

      MapSet.difference(l, r) |> MapSet.size()
    end

  end

  defmodule Part2 do
    def solve(input) do
      input
      |> Part1.solve(1)
    end
  end
end

One of my favorite things about AoC is seeing the various different approaches. What I’ve learned is that the way the data gets structured really dictates how you are able to approach the logic. Often when I’m trying to understand the solutions from others I find I’m struggling because I set up the data so differently that I can’t shift my head around to the flow of the data through their solution.