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

Here is my pretty naive straightforward implementation :

defmodule Y2024.D05 do
  use Day, input: "2024/05", part1: ~c"c", part2: ~c"c"

  defp part1(input) do
    {rules, updates} = parse_input(input)

    updates
    |> Enum.reject(&invalid?(&1, rules))
    |> Enum.map(&Enum.at(&1, div(Enum.count(&1), 2)))
    |> Enum.sum()
  end

  defp part2(input) do
    {rules, updates} = parse_input(input)

    updates
    |> Enum.filter(&invalid?(&1, rules))
    |> Enum.map(&reorder(&1, rules))
    |> Enum.map(&Enum.at(&1, div(Enum.count(&1), 2)))
    |> Enum.sum()
  end

  defp invalid?(update, rule_or_rules), do: not valid?(update, rule_or_rules)

  defp valid?(update, {f, s}) do
    case {Enum.find_index(update, &(&1 == f)), Enum.find_index(update, &(&1 == s))} do
      {nil, _} -> true
      {_, nil} -> true
      {fi, si} when fi < si -> true
      _ -> false
    end
  end

  defp valid?(update, rules), do: Enum.all?(rules, &valid?(update, &1))

  defp reorder(update, rules) do
    {f, s} = Enum.find(rules, &invalid?(update, &1))
    {fi, si} = {Enum.find_index(update, &(&1 == f)), Enum.find_index(update, &(&1 == s))}

    modified =
      update
      |> List.replace_at(fi, s)
      |> List.replace_at(si, f)

    if valid?(modified, rules), do: modified, else: reorder(modified, rules)
  end

  defp parse_input(input) do
    [rules_chunk, updates_chunk] = input
    {parse_rules(rules_chunk), parse_updates(updates_chunk)}
  end

  defp parse_rules(rules), do: Enum.map(rules, &parse_rule/1)
  defp parse_updates(updates), do: Enum.map(updates, &parse_update/1)

  defp parse_rule(<<f::bytes-size(2), "|", s::bytes-size(2)>>), do: {parse_page(f), parse_page(s)}

  defp parse_update(update) do
    update
    |> Utils.splitrim(",")
    |> Enum.map(&parse_page/1)
  end

  defp parse_page(page), do: String.to_integer(page)
end

It solves part 2 in less than 800ms which is seems pretty decent for a very suboptimal solution !

Edit : simple optimisations reduce the execution time to < 130ms for part 2 .

Not really been making an effort to keep up this year. Stuck on this one b/c my intuition is apparently wrong. My thought was use the rules to make an acyclic directed graph with edges where every left hand value is incident upon right hand value. Then checking the updates just means there has to be a path between each consecutive pair of page numbers. Works great for the example data but apparently none of the updates from the real input data meet this condition. Any insight into why my logic is wrong?

def do_order(graph, [[a,b] | rest]) do 
  :digraph.add_vertex(graph, a)
  :digraph.add_vertex(graph, b)
  :digraph.add_edge(graph, a, b)
  do_order(graph, rest)
end

def solve(rules, updates) do 
  updates
  |> Enum.map(&Enum.chunk_every(&1, 2, 1, :discard))
  |> Enum.filter(&Enum.all?(&1, fn [a,b] -> :digraph.get_path(rules, a, b) end)
  |> Enum.map(fn update -> Enum.at(update, div(length(update), 2)) |> hd() end)
  |> Enum.sum()
end

EDIT:
I’m apparently doing something wrong with the process of adding edges to the graph. There are 1176 rules in my data set but I end up with a graph that contains only 632 edges. I can’t figure out why …