Here’s my approach with a Map: advent-of-code-2024/lib/advent_of_code2024/day5.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

Easy part 1, I had to think more for part 2. I thought my approach would take an infinite time, but it didn’t (about 40ms)

I implemented a bubble sort like approach:

• traverse the list of numbers
• every time we find an invalid number (compared to all previous ones), swap them
• then recursive call to traverse and fix the new swapped list.

Part 1

defmodule Advent.Y2024.Day05.Part1 do
  def run(puzzle) do
    {rules, updates} = parse(puzzle)

    updates
    |> Enum.filter(&valid?(&1, rules))
    |> Enum.map(&Enum.at(&1, &1 |> length |> div(2)))
    |> Enum.sum()
  end

  def parse(puzzle) do
    [rules, updates] = String.split(puzzle, "\n\n")

    rules =
      for rule <- String.split(rules, "\n"), reduce: MapSet.new() do
        acc ->
          [p1, p2] = String.split(rule, "|")
          MapSet.put(acc, {String.to_integer(p1), String.to_integer(p2)})
      end

    updates =
      for pages <- String.split(updates, "\n") do
        for page <- String.split(pages, ","),
            page = String.to_integer(page),
            do: page
      end

    {rules, updates}
  end

  def valid?(update, rules) do
    update
    |> Enum.reduce({[], true}, fn
      _page, {prev, false} ->
        {prev, false}

      page, {prev, _valid?} ->
        valid? = not Enum.any?(prev, &MapSet.member?(rules, {page, &1}))
        {[page | prev], valid?}
    end)
    |> elem(1)
  end
end

Part 2

defmodule Advent.Y2024.Day05.Part2 do
  alias Advent.Y2024.Day05.Part1

  def run(puzzle) do
    {rules, updates} = Part1.parse(puzzle)

    updates
    |> Enum.reject(&Part1.valid?(&1, rules))
    |> Enum.map(&for {p, i} <- Enum.with_index(&1), into: %{}, do: {i, p})
    |> Enum.map(&fix_update(&1, rules))
    |> Enum.map(&Map.get(&1, &1 |> Enum.count() |> div(2)))
    |> Enum.sum()
  end

  def fix_update(update, rules) do
    for i <- 1..(Enum.count(update) - 1), j <- 0..(i - 1), reduce: {nil, true} do
      {indexes, false} ->
        {indexes, false}

      {nil, true} ->
        {first, second} = {Map.get(update, j), Map.get(update, i)}

        if MapSet.member?(rules, {second, first}) do
          {{i, j}, false}
        else
          {nil, true}
        end
    end
    |> then(fn
      {nil, true} -> update
      {{i, j}, false} -> update |> swap(i, j) |> fix_update(rules)
    end)
  end

  defp swap(update, i, j) do
    update |> Map.put(i, Map.get(update, j)) |> Map.put(j, Map.get(update, i))
  end
end