Livebook. solution using maps
https://github.com/newton-peixoto/advent-of-code/commit/df97e0fe72c3797e664cf392a51fcf38d982dd65#diff-03ac184df3657c047b4aab1cf312757da95a7cb83163b100662ca7a13ae8dc81R43
newton-peixoto
0
Andrew-Bekhiet
My solution is very similar to @seeplusplus
Didn’t realize I could use the rules to sort the pages, until I got a bit stuck in part 2 and decided to rethink the whole thing again
https://github.com/Andrew-Bekhiet/advent-of-code-2024/blob/master/Day-5/elixir.ex
0
bengtson
I used a sort function to Enum.sort based on the rules. This created a list of update entries each with {original_order, sorted_order). From there it was a simple sort for; part1 == and part 2 !=, then summing the middle value in each list.
Here’s the code for part 1 and part 2:
defmodule Aoc.Day05 do
def run() do
IO.puts("Part 1 : result: #{part1()}")
IO.puts("Part 2 : result: #{part2()}")
end
def part1() do
get_ordered_lists()
|> Enum.filter(fn {original, ordered} -> original == ordered end)
|> Enum.map(fn {l, _o} -> Enum.at(l, trunc(Enum.count(l) / 2)) end)
|> Enum.sum()
end
def part2() do
get_ordered_lists()
|> Enum.filter(fn {original, ordered} -> original != ordered end)
|> Enum.map(fn {_l, o} -> Enum.at(o, trunc(Enum.count(o) / 2)) end)
|> Enum.sum()
end
def get_ordered_lists() do
{rules, updates} = get_input()
updates
|> Enum.map(fn page_list -> {page_list, check_page_order(page_list, rules)} end)
end
def check_page_order(page_list, rules) do
page_list
|> Enum.sort(fn n1, n2 ->
rule = Map.get(rules, n1, [n1])
not Enum.member?(rule, n2)
end)
|> Enum.reverse()
end
# parsed_rules is map of page => [pages list must be after]
# parsed_update is list of updates, each update is a list of original order.
def get_input() do
[rules, updates] =
String.split(Atom.to_string(__MODULE__), ".")
|> List.last()
|> String.downcase()
|> then(fn day -> "lib/#{day}/input.txt" end)
|> File.read!()
|> String.split("\n\n")
parsed_rules =
rules
|> String.split("\n")
|> Enum.map(fn rule -> String.split(rule, "|") end)
|> Enum.map(fn [f, l] -> {String.to_integer(f), String.to_integer(l)} end)
|> Enum.group_by(fn {b, _a} -> b end)
|> Enum.map(fn {p, list} -> {p, list |> Enum.map(fn {_p, i} -> i end)} end)
|> Enum.into(%{})
parsed_updates =
updates
|> String.split("\n")
|> Enum.map(fn nums -> String.split(nums, ",") end)
|> Enum.map(fn list -> list |> Enum.map(fn strint -> String.to_integer(strint) end) end)
{parsed_rules, parsed_updates}
end
end
0
antoine-duchenet
Many problems in AoC are NOT the general case. Given input is built in a specific way to ensure there is a solution. Those “meta” bias can sometimes be used to find shortcuts.
0
rvnash
Interesting, I did not know that. It’s my first time trying AoC.
Another possible condition that would cause confusion is if the rule-set is not transitive.
1|2
2|3
3|11,2,3
No way to sort that to fit all the rules.
Another one would be if the rules form islands.
1|2
3|4
4,3,2,1
There are many ways to sort that like 1,2,3,4 and 1,3,2,4
Speaking of which, if the data has an even number of elements then there is not middle element.
I spent a lot of time fretting over these possibilities. I guess the best way to do this would be to check for them as assumptions before trying to handle them somehow.
0
Flo0807
Hey!
First, I have grouped the rules by their second number. For each number of a page, I get the relevant rules from this map. I then check whether the rest of my list has any numbers in common with the list of first numbers of the relevant rules. If so, it means that the page violates a rule.
Source Code:
https://github.com/Flo0807/adventofcode/blob/main/2024/05.livemd
0
lkuty
$ ./day05.exs
Part1. Sum: 4790
Part 1 + I/O done in 5729 µs
Part2. Sum: 6319
Part 2 done in 1605 µs
File day05.exs:
#!/usr/bin/env elixir
# AoC 2024. day 5.
defmodule Part1 do
@spec order_ok?([integer()], MapSet.t()) :: boolean()
def order_ok?(numbers, rules)
def order_ok?([], _set), do: true
def order_ok?([number | numbers], rules) do
# If for all the following `numbers` x after `number`, we cannot find a rule x|number
# Then `number` is at the right position
Enum.all?(numbers, fn x -> !MapSet.member?(rules, {x, number}) end)
&& order_ok?(numbers, rules)
end
end
# part 1. accumulates the data and at the same time solve part 1.
# it could be decoupled
start = System.monotonic_time(:microsecond)
{rules, bad_updates, sum} = File.stream!("../day05.txt")
|> Enum.reduce({MapSet.new(), [], 0}, fn line, {rules, updates, sum} ->
case Regex.run(~r/^(?:(\d+)\|(\d+))|\d+(?:,\d+)+/, line) do
[_, fst, snd] -> # first, accumulate the rules in the MapSet
{MapSet.put(rules, {String.to_integer(fst), String.to_integer(snd)}), updates, sum}
nil -> {rules, updates, sum}
[update] -> # then, check all the updates
update = update |> String.split(",") |> Enum.map(&String.to_integer/1)
if Part1.order_ok?(update, rules) do
# take the middle number and add it to sum
{rules, updates, sum + :lists.nth(div(length(update), 2) + 1, update)}
else
{rules, [update | updates], sum}
end
end
end)
IO.puts("Part1. Sum: #{sum}")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 1 + I/O done in #{elapsed} µs"
# part 2
start = System.monotonic_time(:microsecond)
Enum.reduce(bad_updates, 0, fn update, sum ->
update = Enum.sort(update, fn n1, n2 -> MapSet.member?(rules, {n1, n2}) end)
sum + :lists.nth(div(length(update), 2) + 1, update)
end)
|> IO.inspect(label: "Part2. Sum")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 2 done in #{elapsed} µs"
0
king-11
I used local topological sort over the local graph formed by pair of nodes in each updated runs under 30ms so seems fair enough
https://github.com/king-11/AdventOfCode/blob/main/lib/advent_of_code/day_05.ex
0
ken-kost
joelheaps
@king-11 Figured I’d rather bring some discussion here than Reddit.
Looks like it took about 36ms for the swap method in part 2. (Using Livebook, so bear with my formatting).
Edit: Got it down to around 29ms now.
Part 1
[rules, updates] = Kino.FS.file_path("day5_input.txt")
|> File.read!()
|> String.trim()
|> String.split("\n\n")
|> Enum.map(fn section ->
String.trim(section)
|> String.split("\n")
end)
rules = Enum.map(rules, fn pair ->
String.split(pair, "|")
|> Enum.map(&String.to_integer/1)
|> List.to_tuple()
end)
updates = Enum.map(updates, fn group ->
String.split(group, ",")
|> Enum.map(&String.to_integer/1)
end)
defmodule UpdateValidator do
@doc """
Check if all {x before y} rules pass for the given update.
"""
def is_valid_update?(update, rules) do
not Enum.any?(rules, fn {x, y} -> not is_before?(x, y, update) end)
end
@doc """
Check if x occurs before y in the given list
"""
def is_before?(x, y, list = [first | rest]) do
if x in list and y in list do
if y == first, do: false, else: is_before?(x, y, rest)
else
true
end
end
end
sum_middle_numbers = fn updates -> updates
|> Enum.map(& {length(&1) |> Integer.floor_div(2), &1}) # Get index of middle num.
|> Enum.map(fn {middle_index, update} ->
Enum.at(update, middle_index)
end) # Extract value at index
|> Enum.sum()
end
valid_updates = Enum.filter(updates, fn update ->
UpdateValidator.is_valid_update?(update, rules)
end)
result = sum_middle_numbers.(valid_updates)
----
Part 2
defmodule UpdateFixer do
import UpdateValidator
@doc """
Recursively applies fixes until no more
modifications are made (some fixes break other rules).
"""
def fix_update(update, rules) do
recursively_fix_update({true, update}, rules)
end
# Simply facilitates recursive calling.
defp recursively_fix_update({true, update}, rules) do
result = do_fix_update(update, rules)
recursively_fix_update(result, rules)
end
defp recursively_fix_update({false, update}, _), do: update
# Applies fixes for all rules by swapping values.
defp do_fix_update(update, rules, modified? \\ false)
defp do_fix_update(update, [], modified?), do: {modified?, update}
defp do_fix_update(update, [{x, y} | rules], modified?) do
{update_, modified?} = if not is_before?(x, y, update) do
# Swap values if this rule failed validation.
update_ = update
|> Enum.map(& {&1}) # Pack into tuple to make compat. with keyreplace
|> List.keyreplace(x, 0, {y})
|> List.keyreplace(y, 0, {x})
|> Enum.map(fn {val} -> val end)
{update_, true}
else
# Otherwise, pass update as-is.
{update, modified?}
end
# Check next rule.
do_fix_update(update_, rules, modified?)
end
end
start = System.monotonic_time(:microsecond)
result = updates -- valid_updates # Invalid updates
|> Enum.map(fn update -> UpdateFixer.fix_update(update, rules) end)
|> sum_middle_numbers.()
IO.puts("Part 2 result: #{result}")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 2 finished in #{elapsed / 1000}ms"
Part 2 result: ----
Part 2 finished in 29.442ms
0