Advent of Code 2024 - Day 4

Not sure how Elixir-y my solution turned out to be, but it works at least.

defmodule Aoc2024.Day4 do
  @moduledoc false

  defp get_input(file) do
    File.read!(file)
    |> String.split("\n")
    |> Enum.filter(fn line_data -> line_data != "" end)
  end

  defp value(grid, x, y) do
    Enum.fetch!(Enum.fetch!(grid, y), x)
  end

  defp diagonal(grid, x, y, x_incr, y_incr) do
    if x < 0 or x >= length(List.first(grid)) or y < 0 or y >= length(grid) do
      []
    else
      [value(grid, x, y) | diagonal(grid, x_incr.(x, 1), y_incr.(y, 1), x_incr, y_incr)]
    end
  end

  def part1(file) do
    search_word = "XMAS"
    lines = get_input(file)
    horizontal = lines
    grid = Enum.map(lines, &String.split(&1, "", trim: true))
    vertical = Enum.zip(grid) |> Enum.map(fn row -> Tuple.to_list(row) |> Enum.join("") end)

    last_x = length(List.first(grid)) - 1
    last_y = length(grid) - 1

    downright =
      (for x <- 0..last_x do
         diagonal(grid, x, 0, &+/2, &+/2)
       end ++
         for y <- 1..last_y do
           diagonal(grid, 0, y, &+/2, &+/2)
         end)
      |> Enum.map(&Enum.join(&1, ""))

    downleft =
      (for x <- 0..last_x do
         diagonal(grid, x, 0, &-/2, &+/2)
       end ++
         for y <- 1..last_y do
           diagonal(grid, last_x, y, &-/2, &+/2)
         end)
      |> Enum.map(&Enum.join(&1, ""))

    forward = Regex.compile!(search_word)
    backward = Regex.compile!(String.reverse(search_word))

    (horizontal ++ vertical ++ downright ++ downleft)
    |> Enum.map(fn s -> (Regex.scan(forward, s) ++ Regex.scan(backward, s)) |> Enum.count() end)
    |> Enum.sum()
  end

  defp xmas?(grid, x, y) do
    top_left = value(grid, x, y)
    top_right = value(grid, x + 2, y)
    center = value(grid, x + 1, y + 1)
    bottom_left = value(grid, x, y + 2)
    bottom_right = value(grid, x + 2, y + 2)

    center == "A" and
      ((top_left == "M" and bottom_right == "S") or (top_left == "S" and bottom_right == "M")) and
      ((top_right == "M" and bottom_left == "S") or (top_right == "S" and bottom_left == "M"))
  end

  def part2(file) do
    lines = get_input(file)
    grid = Enum.map(lines, &String.split(&1, "", trim: true))
    last_x = length(List.first(grid)) - 1
    last_y = length(grid) - 1

    for x <- 0..(last_x - 2), y <- 0..(last_y - 2) do
      if xmas?(grid, x, y), do: 1, else: 0
    end
    |> Enum.sum()
  end
end

Also, for part 2 we kept with the “skip through the binary” approach. We stop as soon as we know we do not have an X and move on. Also realised you can stop two before the end of the row and column as otherwise the X will extend out of bounds.

  def day4_2() do
    grid = "./day_4_input.txt" |> File.read!()
    line_length = line_length(grid, 0)
    find_x(grid, {0, 0}, line_length, 0)
  end

  @m "M"
  @a "A"
  @s "S"

  def find_x(binary, {x, y}, line_length, count) do
    if mas_se?(binary, line_length) || sam_se?(binary, line_length) do
      <<_::binary-size(2), rest::binary>> = binary

      count =
        if mas_sw?(rest, line_length) || sam_sw?(rest, line_length) do
          count + 1
        else
          count
        end

      next(binary, {x, y}, line_length, count)
    else
      next(binary, {x, y}, line_length, count)
    end
  end

  # This bounds check essentially.
  def next(binary, {x, y}, line_length, count) do
    if x + 1 > line_length - 4 do
      if y + 1 > line_length - 4 do
        # We stop because we are at max Y depth
        count
      else
        # Skip to next row
        <<_::binary-size((line_length - x)), rest::binary>> = binary
        find_x(rest, {0, y + 1}, line_length, count)
      end
    else
      # Move right
      <<_::binary-size(1), rest::binary>> = binary
      find_x(rest, {x + 1, y}, line_length, count)
    end
  end

  def mas_se?(<<@m, rest::binary>>, line_length) do
    case southeast_once(rest, line_length) do
      <<@a, after_a::binary>> -> match?(<<@s, _::binary>>, southeast_once(after_a, line_length))
      _ -> false
    end
  end

  def mas_se?(_, _), do: false

  def sam_se?(<<@s, rest::binary>>, line_length) do
    case southeast_once(rest, line_length) do
      <<@a, after_a::binary>> -> match?(<<@m, _::binary>>, southeast_once(after_a, line_length))
      _ -> false
    end
  end

  def sam_se?(_, _), do: false

  def mas_sw?(<<@m, rest::binary>>, line_length) do
    case southwest_once(rest, line_length) do
      <<@a, after_a::binary>> -> match?(<<@s, _::binary>>, southwest_once(after_a, line_length))
      _ -> false
    end
  end

  def mas_sw?(_, _), do: false

  def sam_sw?(<<@s, rest::binary>>, line_length) do
    case southwest_once(rest, line_length) do
      <<@a, after_a::binary>> -> match?(<<@m, _::binary>>, southwest_once(after_a, line_length))
      _ -> false
    end
  end

  def sam_sw?(_, _), do: false

  def southwest_once(binary, line_length) do
    skip = line_length - 2
    <<_::binary-size(skip), rest::binary>> = binary
    rest
  end

  # May need bounds checks? so we don't wrap the line? Or handle higher up. But there is
  # a max X coord of line_length - 4, one for new line, one for last char and one for pen char and one to 0 index.
  def southeast_once(binary, line_length) do
    skip = line_length
    <<_::binary-size(skip), rest::binary>> = binary
    rest
  end

It’s fast.

Awesome

Oh nice, I managed to beat this. I compared vs your solution:

Operating System: macOS
CPU Information: Apple M1 Max
Number of Available Cores: 10
Available memory: 64 GB
Elixir 1.17.1
Erlang 27.1
JIT enabled: true

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 32 s

Benchmarking part 1 ...
Benchmarking sevenseascat ...
Calculating statistics...
Formatting results...

Name                   ips        average  deviation         median         99th %
part 1              310.86        3.22 ms     ±4.15%        3.20 ms        3.58 ms
sevenseascat        107.63        9.29 ms     ±4.02%        9.11 ms       10.24 ms

Comparison:
part 1              310.86
sevenseascat        107.63 - 2.89x slower +6.07 ms

Memory usage statistics:

Name            Memory usage
part 1               4.32 MB
sevenseascat        14.35 MB - 3.33x memory usage +10.04 MB

**All measurements for memory usage were the same**

Reduction count statistics:

Name                 average  deviation         median         99th %
part 1              415.50 K     ±0.01%       415.49 K       415.59 K
sevenseascat        826.31 K     ±0.00%       826.31 K       826.31 K

Comparison:
part 1              415.49 K
sevenseascat        826.31 K - 1.99x reduction count +410.81 K

I’m well behind but I think I managed this. Grids in functional languages fill me with dread but I took the following approach for part 1 was first check the for a match like this:

  @samx "SAMX"
  @xmas "XMAS"
  @new_line "\n"
  defp check_line(<<>>, hits), do: hits

  defp check_line(<<@samx, _::binary>> = line, hits) do
    <<_::binary-size(3), rest::binary>> = line
    check_line(rest, hits + 1)
  end

  defp check_line(<<@xmas, _::binary>> = line, hits) do
    <<_::binary-size(3), rest::binary>> = line
    check_line(rest, hits + 1)
  end

  defp check_line(<<_::binary-size(1), rest::binary>>, hits), do: check_line(rest, hits)

Then turn the binary into columns and each diagonal. The trick for the diagnonals is to iterate along the top row, then down the rightmost column for sout east diagonals. Then go from top right to back along the top row and down the leftmost column.

Anyway it came out a bit more verbose than I hoped can probably simplify it a bit.

  def day4_1() do
    grid = "./day_4_input.txt" |> File.read!()

    line_length = line_length(grid, 0)
    row_count = check_line(grid, 0)
    ne_count = north_east_diagonal(grid, line_length)
    se_count = south_east_diagonal(grid, line_length)
    column_count = column_count(grid, line_length)
    row_count + ne_count + se_count + column_count
  end

  @samx "SAMX"
  @xmas "XMAS"
  @new_line "\n"
  defp check_line(<<>>, hits), do: hits

  defp check_line(<<@samx, _::binary>> = line, hits) do
    <<_::binary-size(3), rest::binary>> = line
    check_line(rest, hits + 1)
  end

  defp check_line(<<@xmas, _::binary>> = line, hits) do
    <<_::binary-size(3), rest::binary>> = line
    check_line(rest, hits + 1)
  end

  defp check_line(<<_::binary-size(1), rest::binary>>, hits), do: check_line(rest, hits)

  # We include the new line in the count because it makes the rest of the stuff work better
  defp line_length(<<@new_line, _::binary>>, count), do: count + 1
  defp line_length(<<_::binary-size(1), rest::binary>>, count), do: line_length(rest, count + 1)

  def column_count(grid, line_length) do
    Enum.reduce(0..(line_length - 1), "", fn x, lines ->
      columns({x, line_length - 2}, grid, line_length, lines)
    end)
    |> check_line(0)
  end

  def columns({_, y}, _, _, acc) when y < 0, do: <<acc::binary, @new_line>>

  def columns({x, y}, grid, line_length, acc) do
    char = :binary.part(grid, x + y * line_length, 1)
    columns({x, y - 1}, grid, line_length, <<acc::binary, char::binary>>)
  end

  def south_east_diagonal(grid, line_length) do
    se_diagonal_index({line_length - 2, 0}, line_length - 2, [])
    |> Enum.reduce("", fn diagonal_indexes, acc ->
      line =
        diagonal_indexes
        |> Enum.reduce("", fn {x, y}, acc ->
          char = :binary.part(grid, x + y * line_length, 1)
          <<acc::binary, char::binary>>
        end)

      <<acc::binary, line::binary, @new_line>>
    end)
    |> check_line(0)
  end

  # We've gone past bottom left.
  def se_diagonal_index({0, y}, last_idx, acc) when y == last_idx, do: acc

  # This is the first case hit - the top right
  def se_diagonal_index({last_idx, 0}, last_idx, acc) do
    se_diagonal_index({last_idx - 1, 0}, last_idx, [[{last_idx, 0}] | acc])
  end

  # This is the switch up case, where we round the corner on the top left hand side going down
  def se_diagonal_index({x, _}, last_idx, acc) when x < 0 do
    se_diagonal_index({0, 1}, last_idx, acc)
  end

  # this is going along the top row, we heading backwards on the x axis
  def se_diagonal_index({x, 0} = current_cell, last_idx, acc) do
    diagonal = [
      current_cell | Enum.map(1..(last_idx - x), fn y_coord -> {x + 1 * y_coord, y_coord} end)
    ]

    se_diagonal_index({x - 1, 0}, last_idx, [diagonal | acc])
  end

  # this is going down the leftmost column.
  def se_diagonal_index({0, y} = current, last_idx, acc) do
    diagonal = [current | Enum.map(1..(last_idx - y), fn y_coord -> {y_coord, y + y_coord} end)]
    se_diagonal_index({0, y + 1}, last_idx, [diagonal | acc])
  end

  def north_east_diagonal(grid, line_length) do
    # It's - 2, 1 because of the newline char at the end of each line 1 because of the 0 index
    # We start at X of 2 because first few rows can never match as they are too short.
    ne_diagonal_idx({0, 0}, line_length - 2, [])
    |> Enum.reduce("", fn diagonal_indexes, acc ->
      line =
        diagonal_indexes
        |> Enum.reduce("", fn {x, y}, acc ->
          char = :binary.part(grid, x + y * line_length, 1)
          <<acc::binary, char::binary>>
        end)

      <<acc::binary, line::binary, @new_line>>
    end)
    |> check_line(0)
  end

  def ne_diagonal_idx({last_idx, y}, last_idx, acc) when y >= last_idx, do: acc

  def ne_diagonal_idx({0, 0}, last_idx, acc) do
    ne_diagonal_idx({1, 0}, last_idx, [[{0, 0}] | acc])
  end

  def ne_diagonal_idx({x, 0}, last_idx, acc) when x > last_idx do
    ne_diagonal_idx({x - 1, 1}, last_idx, acc)
  end

  def ne_diagonal_idx({x, 0} = current_cell, last_idx, acc) do
    diagonal = [current_cell | Enum.map(1..x, fn y_coord -> {x - 1 * y_coord, y_coord} end)]
    ne_diagonal_idx({x + 1, 0}, last_idx, [diagonal | acc])
  end

  def ne_diagonal_idx({x, y} = current, last_idx, acc) do
    diagonal = [
      current | Enum.map(1..(last_idx - y), fn y_coord -> {x - 1 * y_coord, y + y_coord} end)
    ]

    ne_diagonal_idx({x, y + 1}, last_idx, [diagonal | acc])
  end

Looking at your code I see which rabbit hole you experienced. I experienced the same and just dropped all code and started from scratch.

You made it, which is the most important

at least part2 didnt kill my soul

https://github.com/jarlah/advent_of_code/blob/master/lib/2024/day_4/Part2.ex

Part1 was so hard! I think i must have digged my self into a rabbit hole or something, because the natural “human approach” is often translatable into a program.

First i started to look for horizontals and verticals, and made a count function for both. Easy. Then i made a new function for counting diagonals. Thats where the hell began. But i still dont know why.

Anyway. Due to me wanting total control and be able to cross reference, my program outputs this

[
  {0, 4, 3, 7, "XMAS"},
  {0, 5, 0, 8, "XMAS"},
  {1, 1, 1, 4, "SAMX"},
  {1, 6, 4, 6, "SAMX"},
  {2, 3, 5, 6, "SAMX"},
  {2, 3, 5, 0, "SAMX"},
  {3, 9, 6, 9, "XMAS"},
  {3, 9, 6, 6, "XMAS"},
  {4, 0, 4, 3, "XMAS"},
  {4, 3, 4, 6, "SAMX"},
  {6, 0, 9, 3, "SAMX"},
  {6, 2, 9, 5, "SAMX"},
  {6, 4, 9, 1, "SAMX"},
  {6, 6, 9, 9, "SAMX"},
  {6, 6, 9, 3, "SAMX"},
  {6, 8, 9, 5, "SAMX"},
  {6, 9, 9, 9, "SAMX"},
  {9, 5, 9, 8, "XMAS"}
]

which is start row id, start col id, end row id, end col id and the word it found

https://github.com/jarlah/advent_of_code/blob/master/lib/2024/day_4/Part1.ex

i almost never publishes unpolished code like this, but i cant stand working on it more

Saw a meme about day 4 on r/adventofcode, so my part 1 solution was somewhat overengineered - but it was an easy jump to part 2 as a result.

For fun, tried to write the whole thing in a local-variable-free style, which makes for very arrow-shaped functions.

Part 1:

defmodule PatternFinder do
  defmodule Grid do
    defstruct [:by_char, :by_pos]

    def init do
      %__MODULE__{
        by_char: %{},
        by_pos: %{}
      }
    end

    def add(g, char, pos) do
      %{g |
        by_char: Map.update(g.by_char, char, MapSet.new([pos]), &MapSet.put(&1, pos)),
        by_pos: Map.put(g.by_pos, pos, char)
      }
    end

    def get(g, pos) do
      Map.fetch(g.by_pos, pos)
    end

    def where(g, char) do
      Map.fetch!(g.by_char, char)
    end
  end

  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.map(&String.graphemes/1)
    |> Stream.with_index()
    |> Stream.flat_map(fn {chars, row} ->
      chars
      |> Enum.with_index()
      |> Enum.map(fn {c, col} ->
        {{row, col}, c}
      end)
    end)
    |> Enum.reduce(Grid.init(), fn {pos, char}, grid ->
      Grid.add(grid, char, pos)
    end)
  end

  @patterns [
    %{
      start_at: "X",
      neighbors: %{
        "M" => {0,1},
        "A" => {0,2},
        "S" => {0,3}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {0,-1},
        "A" => {0,-2},
        "S" => {0,-3}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {1,0},
        "A" => {2,0},
        "S" => {3,0}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {-1,0},
        "A" => {-2,0},
        "S" => {-3,0}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {1,1},
        "A" => {2,2},
        "S" => {3,3}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {-1,1},
        "A" => {-2,2},
        "S" => {-3,3}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {1,-1},
        "A" => {2,-2},
        "S" => {3,-3}
      }
    },
    %{
      start_at: "X",
      neighbors: %{
        "M" => {-1,-1},
        "A" => {-2,-2},
        "S" => {-3,-3}
      }
    },
  ]

  def matches(grid) do
    @patterns
    |> Enum.flat_map(fn pattern ->
      grid
      |> Grid.where(pattern.start_at)
      |> Enum.filter(fn {row, col} ->
        pattern.neighbors
        |> Enum.all?(fn {expected_char, {row_off, col_off}} ->
          case Grid.get(grid, {row + row_off, col + col_off}) do
            :error -> false
            {:ok, char} -> char == expected_char
          end
        end)
      end)
    end)
  end
end

PatternFinder.read("input.txt")
|> PatternFinder.matches()
|> IO.inspect()
|> length()
|> IO.inspect()

Part 2:

defmodule PatternFinder do
  defmodule Grid do
    defstruct [:by_char, :by_pos]

    def init do
      %__MODULE__{
        by_char: %{},
        by_pos: %{}
      }
    end

    def add(g, char, pos) do
      %{g |
        by_char: Map.update(g.by_char, char, MapSet.new([pos]), &MapSet.put(&1, pos)),
        by_pos: Map.put(g.by_pos, pos, char)
      }
    end

    def get(g, pos) do
      Map.fetch(g.by_pos, pos)
    end

    def where(g, char) do
      Map.fetch!(g.by_char, char)
    end
  end

  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.map(&String.graphemes/1)
    |> Stream.with_index()
    |> Stream.flat_map(fn {chars, row} ->
      chars
      |> Enum.with_index()
      |> Enum.map(fn {c, col} ->
        {{row, col}, c}
      end)
    end)
    |> Enum.reduce(Grid.init(), fn {pos, char}, grid ->
      Grid.add(grid, char, pos)
    end)
  end

  @patterns [
    %{
      start_at: "A",
      neighbors: %{
        {-1,-1} => "M",
        {1,-1} => "M",
        {-1,1} => "S",
        {1,1} => "S"
      }
    },
    %{
      start_at: "A",
      neighbors: %{
        {-1,-1} => "S",
        {1,-1} => "M",
        {-1,1} => "S",
        {1,1} => "M"
      }
    },
    %{
      start_at: "A",
      neighbors: %{
        {-1,-1} => "S",
        {1,-1} => "S",
        {-1,1} => "M",
        {1,1} => "M"
      }
    },
    %{
      start_at: "A",
      neighbors: %{
        {-1,-1} => "M",
        {1,-1} => "S",
        {-1,1} => "M",
        {1,1} => "S"
      }
    },
  ]

  def matches(grid) do
    @patterns
    |> Enum.flat_map(fn pattern ->
      grid
      |> Grid.where(pattern.start_at)
      |> Enum.filter(fn {row, col} ->
        pattern.neighbors
        |> Enum.all?(fn {{row_off, col_off}, expected_char} ->
          case Grid.get(grid, {row + row_off, col + col_off}) do
            :error -> false
            {:ok, char} -> char == expected_char
          end
        end)
      end)
    end)
  end
end

PatternFinder.read("input.txt")
|> PatternFinder.matches()
|> IO.inspect()
|> length()
|> IO.inspect()

I do benchmarking for all of my solutions - here’s my 2024 day 4

Name                     ips        average  deviation         median         99th %
day 04, part 1       0.109 K     9206.98 μs     ±3.53%     9049.48 μs    10099.13 μs
day 04, part 2       0.120 K     8363.73 μs     ±4.76%     8099.29 μs     9391.84 μs

That was on my M1 Max though…