Today’s problem is really tense. I don’t think I can do it without libgraph.
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
2 Likes
Brute Enum.sort_by with String.contains?
def solve(input) do
[rules, pages] = String.split(input, "\n\n")
pages =
pages
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
line |> String.split(",") |> Enum.map(&String.to_integer/1)
end)
Enum.reduce(pages, {0, 0}, fn page, {p1, p2} ->
sorted =
Enum.sort_by(page, &Function.identity/1, fn l, r ->
String.contains?(rules, "#{l}|#{r}")
end)
mid = Enum.at(sorted, div(length(sorted), 2))
if page == sorted do
{p1 + mid, p2}
else
{p1, p2 + mid}
end
end)
end
Full: aoc2024/lib/day05.ex at master · ruslandoga/aoc2024 · GitHub
3 Likes
That’s very clever!
1 Like
Here is mine:
Here is my solution:
1 Like
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.
1 Like
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 
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:
group_bythe pairs to get a map of greater to lesser numbers- 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
1 Like
Here is mine:
defmodule Aoc2024.Solutions.Y24.Day05 do
alias AoC.Input
def parse(input, _part) do
[rules, updates] = input |> Input.read!() |> String.split("\n\n")
{parser(rules, "|"), parser(updates, ",")}
end
def part_one({rules, updates}) do
updates
|> Enum.map(&{&1, pair_up(&1)})
|> Enum.filter(fn {_, list} -> check_rules(list, rules) end)
|> Enum.map(fn {original, _} -> original end)
|> Enum.reduce(0, &(Enum.at(&1, div(length(&1), 2)) + &2))
end
def part_two({rules, updates}) do
updates
|> Enum.map(&{&1, pair_up(&1)})
|> Enum.filter(fn {_, list} -> not check_rules(list, rules) end)
|> Enum.map(fn {e, list} -> switch_by_rules(list, rules, e) end)
|> Enum.reduce(0, &(Enum.at(&1, div(length(&1), 2)) + &2))
end
defp check_rules([], _rules), do: true
defp check_rules([{a, b} | rest], rules) do
case Enum.find(rules, &(&1 == [a, b])) do
nil -> false
_ -> check_rules(rest, rules)
end
end
defp switch_by_rules([], _rules, solution), do: solution
defp switch_by_rules([{a, b} | rest], rules, solution) do
case Enum.find(rules, &(&1 == [a, b])) do
nil ->
solution = switch_up(solution, a, b)
switch_by_rules(pair_up(solution), rules, solution)
_ ->
switch_by_rules(rest, rules, solution)
end
end
defp pair_up(list) do
Enum.reduce(Enum.with_index(list), [], fn {_v, i}, acc ->
{heads, rest} = Enum.split(list, i + 1)
head = List.last(heads)
Enum.map(rest, fn e -> {head, e} end) ++ acc
end)
end
defp switch_up(list, a, b) do
Enum.map(list, fn e ->
cond do
e == a -> b
e == b -> a
true -> e
end
end)
end
defp parser(input, separator) do
input
|> String.trim()
|> String.split("\n")
|> Enum.map(fn e ->
Enum.map(String.split(e, separator), &String.to_integer(&1))
end)
end
end
Bench:
Solution for 2024 day 5
part_one: 4609 in 114.35ms
part_two: 5723 in 2.95s
Almost 3 seconds for part 2. 
If I keep this up… I won’t keep up. 
edit: I should make a comparison with stream.
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
2 Likes
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 
.
2 Likes
Naive solution using sort_by.
input = """
"""
[rules, updates] = input |> String.split("\n\n")
rules = for rule <- rules |> String.split("\n"),
[a, b] = rule |> String.split("|"),
a = String.to_integer(a),
b = String.to_integer(b)
do
{a, b}
end
updates = for update <- updates |> String.trim() |> String.split("\n"),
update = update |> String.trim() |> String.split(",") do
for page <- update,
page = String.to_integer(page) do
page
end
end
rule_sorter = fn a, b ->
a_precedes_b = Enum.any?(rules, &(&1 == {a, b}))
b_precedes_a = Enum.any?(rules, &(&1 == {b, a}))
cond do
b_precedes_a -> false
a_precedes_b -> true
true -> true
end
end
for update <- updates,
sorted = Enum.sort(update, rule_sorter),
sorted != update, # change to == for part 1, != for part 2
reduce: 0 do
acc ->
len = sorted |> Enum.count
mid_idx = floor(len / 2)
acc + Enum.at(sorted, mid_idx)
end
Making the following changes reduces the part 2 solve time from 4.2s to 44ms:
Change rules to use Maps and MapSets:
rules = for rule <- rules |> String.split("\n"),
[a, b] = rule |> String.split("|"),
a = String.to_integer(a),
b = String.to_integer(b),
reduce: %{}
do
acc ->
Map.update(acc, a, MapSet.new([b]), fn c -> MapSet.put(c, b) end)
end
Change the rule_sorter to accommodate:
rule_sorter = fn a, b ->
a_precedes_b = Map.get(rules, a, MapSet.new()) |> MapSet.member?(b)
b_precedes_a = Map.get(rules, b, MapSet.new()) |> MapSet.member?(a)
cond do
b_precedes_a -> false
a_precedes_b -> true
true -> true
end
end
LOC: 21
EDIT: 19 (found a shorter reorder)
defmodule Aoc2024.Day05 do
def part1(file), do: file |> main() |> elem(0)
def part2(file), do: file |> main() |> elem(1)
def main(file) do
{orders, [_ | updates]} = file |> file_to_lines |> Enum.split_while(&(&1 != ""))
orders = orders |> Enum.map(&to_integers(&1, "|")) |> Enum.group_by(&hd/1, &List.last/1)
updates = Enum.map(updates, &to_integers(&1, ","))
{corrects, incorrects} = Enum.split_with(updates, &c?(Enum.reverse(&1), orders))
{sum_middles(corrects), sum_middles(Enum.map(incorrects, &reorder(&1, orders, [])))}
end
def file_to_lines(file), do: file |> File.read!() |> String.trim() |> String.split("\n")
def to_integers(line, sep), do: line |> String.split(sep) |> Enum.map(&String.to_integer/1)
def sum_middles(lists), do: lists |> Enum.map(&Enum.at(&1, div(length(&1), 2))) |> Enum.sum()
def c?([h | t], o), do: if(Enum.any?(t, &(&1 in Map.get(o, h, []))), do: false, else: c?(t, o))
def c?([], _), do: true
def reorder(l, o), do: Enum.sort(l, &(&2 in Map.get(o, &1, [])))
end
1 Like
I got two stars with solutions similar to most people here, but what I don’t understand is how this problem is solvable in general. It only works because the elements of the update list all appear in the ordering rules. But what if an update list were to have some elements that don’t have any rules? They could essentially appear anywhere in the otherwise sorted list, making it impossible to know what the center page number is. How do the instructions rule out this possibility?
Part 1:
[rules, updates] = puzzle_input |> String.split("\n\n", trim: true)
rules =
rules
|> String.split(["\n", "|"])
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(2)
|> Enum.reduce(%{}, fn [x, y], acc -> Map.update(acc, x, [y], &[y | &1]) end)
updates =
updates
|> String.split("\n", trim: true)
|> Enum.map(fn update ->
update |> String.split(",") |> Enum.map(&String.to_integer/1)
end)
valid_update? = fn update, rules ->
for i <- 0..length(update), {a, b} = Enum.split(update, i) do
case {a, b} do
{_, []} ->
true
{a, [current | _]} ->
current_rules = Map.get(rules, current, [])
MapSet.disjoint?(MapSet.new(current_rules), MapSet.new(a))
end
end
|> Enum.all?(& &1)
end
updates
|> Enum.filter(&valid_update?.(&1, rules))
|> Enum.map(fn list -> Enum.at(list, div(length(list), 2)) end)
|> Enum.sum()
Part 2:
[rules, updates] = puzzle_input |> String.split("\n\n", trim: true)
rules =
rules
|> String.split(["\n", "|"])
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(2)
|> Enum.reduce(%{}, fn [x, y], acc -> Map.update(acc, x, [y], &[y | &1]) end)
updates =
updates
|> String.split("\n", trim: true)
|> Enum.map(fn update ->
update |> String.split(",") |> Enum.map(&String.to_integer/1)
end)
valid_update? = fn update, rules ->
for i <- 0..length(update), {a, b} = Enum.split(update, i) do
case {a, b} do
{_, []} ->
true
{a, [current | _]} ->
current_rules = Map.get(rules, current, [])
MapSet.disjoint?(MapSet.new(current_rules), MapSet.new(a))
end
end
|> Enum.all?(& &1)
end
updates
|> Enum.reject(&valid_update?.(&1, rules))
|> Enum.map(&Enum.sort(&1, fn a, b -> b in Map.get(rules, a, []) end))
|> Enum.map(fn list -> Enum.at(list, div(length(list), 2)) end)
|> Enum.sum()
I don’t think it is solvable in general. Counterexample:
1|2
2,1,3
Both 1,2,3 and 3,1,2 are correct re-orderings but with different middle numbers.
1 Like
Yes, exactly. We’re only lucky because something like that did not appear in the data.
