Advent of Code 2024 - Day 5

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

That’s very clever!

Here is mine:
https://github.com/Aetherus/advent-of-code/blob/60b58f9a2660e8233b8fa3a997adc81517d758f6/2024/day-05.livemd

Here is my solution:

https://github.com/bjorng/advent-of-code/blob/main/2024/day05/lib/day05.ex

Insert sort to the rescue

I took the time to check if all possible pairs were defined in the ordering rules, and indeed they are, which makes the puzzle much less hard than what it could have been

defmodule AdventOfCode.Solutions.Y24.Day05 do
  alias AoC.Input

  def parse(input, _part) do
    lines = Input.read!(input) |> String.trim()
    [pairs, updates] = String.split(lines, "\n\n")

    {parse_pairs(pairs), parse_updates(updates)}
  end

  defp parse_pairs(raw) do
    raw
    |> String.split("\n")
    |> Enum.map(fn line ->
      [a, b] = String.split(line, "|")
      {String.to_integer(a), String.to_integer(b)}
    end)
  end

  defp parse_updates(raw) do
    raw
    |> String.split("\n")
    |> Enum.map(fn line ->
      line |> String.split(",") |> Enum.map(&String.to_integer/1)
    end)
  end

  def part_one({pairs, updates}) do
    updates
    |> Enum.filter(&good_update?(&1, pairs))
    |> Enum.map(&at_middle/1)
    |> Enum.sum()
  end

  defp good_update?([_last], _) do
    true
  end

  defp good_update?([left | tail], pairs) do
    Enum.all?(tail, fn right -> {left, right} in pairs end) and good_update?(tail, pairs)
  end

  defp at_middle(list) do
    Enum.at(list, div(length(list), 2))
  end

  def part_two({pairs, updates}) do
    updates
    |> Enum.filter(&(not good_update?(&1, pairs)))
    |> Enum.map(&reorder(&1, pairs))
    |> Enum.map(&at_middle/1)
    |> Enum.sum()
  end

  defp reorder(bad_list, pairs) do
    Enum.reduce(bad_list, [], fn n, ordered -> insert(ordered, n, pairs) end)
  end

  defp insert([h | t], n, pairs) do
    if {h, n} in pairs,
      do: [h | insert(t, n, pairs)],
      else: [n, h | t]
  end

  defp insert([], n, _) do
    [n]
  end
end

Edit : no need for insert sort, this would just work:

  def part_two({pairs, updates}) do
    updates
    |> Enum.filter(&(not good_update?(&1, pairs)))
    |> Enum.map(fn list -> Enum.sort(list, &({&1, &2} in pairs)) end)
    |> Enum.map(&at_middle/1)
    |> Enum.sum()
  end

I basically sorted each update (int) based on existence in a set (int*int) on (left, right) and (right, left) (used IComparable). And returned a list of tuples where left element is original update and right is sorted (is desired) update

For part 1 - sum of median of left where left = right
For part 2 - sum of median of right where left <> right

Didn’t share the code because not a beam language. It was so much fun (and fast enough) that I decided not to go topo.

This is the second time I am bitten by part 2. For day 2 I had to use the solution by @bjorng to find the differences between his output and mine and thus find out where I had made an incorrect assumption since my code looked 100% correct (which it was with the wrong assumption). And now part 2 again. The code looks ok but the answer is wrong It is working with the sample data I hope to fix it before day 6.

It looks like there’s a lot of different approaches today, awesome

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day05.ex

The first problem this year that I thought was too slow with my naive implementation so I added a Task.async_stream to make it faster Now part 2 runs in 240ms which I will accept

edit: Some more optimization and I’m down to 7ms for part 2.

Name                     ips        average  deviation         median         99th %
day 05, part 1        1.01 K        0.99 ms     ±3.96%        0.98 ms        1.12 ms
day 05, part 2       0.133 K        7.52 ms     ±3.05%        7.50 ms        8.24 ms

First, I spent way too long trying to figure out a clever way to generate some kind of tree to represent the order, which I would then process everything through.

But I gave up on that and realised it can be much simpler:

1. group_by the pairs to get a map of greater to lesser numbers
2. Compare each pair to see if the RHS is in the map for the LHS

I also decided to implement two helper anonymous functions sorted? and greater? which are closures over the above map.

After the above preparation, each part runs in less than a ms.

def part1({updates, _greater?, sorted?}) do
  updates
  |> Enum.filter(sorted?)
  |> Enum.map(&Enum.at(&1, div(length(&1), 2)))
  |> Enum.sum()
end

def part2({updates, greater?, sorted?}) do
  updates
  |> Enum.reject(sorted?)
  |> Enum.map(&(Enum.sort(&1, greater?) |> Enum.at(div(length(&1), 2))))
  |> Enum.sum()
end

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2024/day5.exs