This topic is about Day 9 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276
The join code is:
39276-eeb74f9a
1 Like
Todays challenge was mostly a matter of chunking data in a fitting matter for the questions asked:
Edit:
Used a little more time to actually use the proper type for the fifo accumulator needed in part 2: :queue.
2 Likes
The test input worked for my part 2, but the real input failed. I missed the bit about adding the smallest and largest values in my readthrough.
defmodule Day09.Window do
defstruct numbers: [], revmap: nil
def new(ls) do
%__MODULE__{
numbers: ls,
revmap: MapSet.new(for x <- ls, y <- ls, x < y, do: x + y)
}
end
def add(window, num) do
if num in window.revmap do
{_, rest} = List.pop_at(window.numbers, 0)
{:ok, new(rest ++ [num])}
else
{:error, num}
end
end
end
defmodule Day09 do
alias Day09.Window
@preamble 25
def readinput() do
File.read!("9.input.txt")
|> String.split("\n", trim: true)
|> Enum.map(&String.to_integer/1)
end
def part1(input \\ readinput()) do
preamble =
input
|> Enum.take(@preamble)
|> Window.new()
loop(Enum.drop(input, @preamble), preamble)
end
def loop([head | rest], preamble) do
case Window.add(preamble, head) do
{:ok, newpreamble} -> loop(rest, newpreamble)
{:error, num} -> num
end
end
def part2(input \\ readinput()) do
badval = part1()
find(input, badval)
end
def find(input, badval) do
case addupto(input, badval) do
{:ok, run} -> weakness(Enum.take(input, run) |> Enum.sort())
{:error, _} -> find(tl(input), badval)
end
end
def addupto([head | tail], badval, total \\ 0, idx \\ 0) do
cond do
total + head == badval -> {:ok, idx - 1}
total + head > badval -> {:error, idx}
true -> addupto(tail, badval, total + head, idx + 1)
end
end
def weakness(sorted), do: List.first(sorted) + List.last(sorted)
end
I used gb_trees for part 1, shorten the code.
Part1
defmodule T do
def run(_window, [], _tree), do: nil
def run([window_head | window_tail], [number | rest], tree) do
iterator = :gb_trees.iterator_from(div(number, 2), tree)
case iterate(number, tree, :gb_trees.next(iterator)) do
:no_pair_found ->
number
:found_pair ->
tree = :gb_trees.delete(window_head, tree)
tree = :gb_trees.insert(number, nil, tree)
run(window_tail ++ [number], rest, tree)
end
end
def iterate(_number, _tree, :none), do: :no_pair_found
def iterate(number, _tree, {key1, _, _}) when key1 > number, do: :no_pair_found
def iterate(number, tree, {key1, _, new_iterator}) do
if number - key1 != key1 && :gb_trees.is_defined(number - key1, tree) do
:found_pair
else
iterate(number, tree, :gb_trees.next(new_iterator))
end
end
end
tree = :gb_trees.empty()
{init, rest} =
File.read!("input")
|> String.split("\n")
|> Enum.map(&String.to_integer/1)
|> Enum.split(25)
tree =
init
|> Enum.reduce(tree, &:gb_trees.insert(&1, nil, &2))
T.run(init, rest, tree)
|> IO.inspect()
Part2:
defmodule T do
def run(numbers, start_index, length, goal) do
slice = Enum.slice(numbers, start_index, length)
cond do
Enum.sum(slice) == goal -> Enum.min(slice) + Enum.max(slice)
Enum.sum(slice) > goal -> run(numbers, start_index + 1, 1, goal)
true -> run(numbers, start_index, length + 1, goal)
end
end
end
numbers =
File.read!("input")
|> String.split("\n")
|> Enum.map(&String.to_integer/1)
T.run(numbers, 0, 1, 14_144_619)
|> IO.inspect()
Hello,
my first time post here, but I joined the board and solve AOC in Elixir since 2019. Last year I tried to do everything using tail-recursive but this year try to utilize more built-in function from Enum, such as find_value or comprehensions.
defmodule Aoc2020Day09 do
import Enum
def solve1(input, preamble \\ 25) do
ns =
input
|> String.trim()
|> String.split("\n")
|> map(&String.to_integer(&1))
p = take(ns, preamble)
rem = drop(ns, preamble)
find_invalid_number(rem, p)
end
def find_invalid_number([], _p) do
raise "failed"
end
def find_invalid_number([h | t], ps = [_ | tp]) do
options = for i <- ps, j <- ps, (fn x, y -> x != y end).(i, j), do: i + j
if h in options do
find_invalid_number(t, tp ++ [h])
else
h
end
end
def solve2(input) do
target = solve1(input)
ns =
input
|> String.trim()
|> String.split("\n")
|> map(&String.to_integer(&1))
r =
0..length(ns)
|> Stream.map(fn i -> drop(ns, i) end)
|> find_value(fn xs -> find_contiguous_range(xs, 0, [], target) end)
min(r) + max(r)
end
def find_contiguous_range([], acc, vs, target) when acc == target do
vs
end
def find_contiguous_range([], _acc, _vs, _target) do
false
end
def find_contiguous_range([h | t], acc, vs, target) do
cond do
h + acc == target -> [h | vs]
h + acc > target -> false
h + acc < target -> find_contiguous_range(t, acc + h, [h | vs], target)
end
end
end
Ahh, :queue is pretty cool. I looked into :array, but didn’t think of queue, although that seems perfectly fitted for a sliding window.
In the end I used lists, but implemented the sliding window with recursion to avoid inefficiently reading from / appending to the end of arbitrary-length lists.
Parts 1 and 2 complete in about a millisecond each, so I think it’s ok.
I know how that feels. I once had a situation where test input worked, my real input did not work, but inputs from my friends worked. Seems like there was a special case my input had which I did not take into account. Also, in yesterday’s solution, I had replaced “nop” and “jmp” both with “nop” and it still worked (I realized the typo later).
Anyways, staying true to the thread topic, here’s my solution for the day, nothing special, good old brute forcing 
defmodule AdventOfCode.Y2020.Day9 do
use AdventOfCode.Helpers.InputReader, year: 2020, day: 9
def run_1, do: input!() |> process() |> find_invalid()
def run_2, do: input!() |> process() |> contiguous_list()
def process(input), do: Enum.map(String.split(input, "\n"), &String.to_integer/1)
defp find_invalid(data) do
{frame, [v | _] = next} = Enum.split(data, 25)
(invalid?(v, MapSet.new(frame)) && v) || find_invalid(tl(frame) ++ next)
end
def invalid?(value, frame), do: Enum.empty?(Enum.filter(frame, &((value - &1) in frame)))
defp contiguous_list(data), do: contiguous_list(find_invalid(data), data)
defp contiguous_list(value, [h | rest]) do
case contiguous_list(List.wrap(h), rest, value) do
:bigger -> contiguous_list(value, rest)
lst -> Enum.max(lst) + Enum.min(lst)
end
end
def contiguous_list(data, [h | rest], value) do
lst = [h | data]
case Enum.sum(lst) do
^value -> lst
n when n > value -> :bigger
_ -> contiguous_list(lst, rest, value)
end
end
end
I also took a brute force approach. I’m sure there is ample room for optimization, but after struggling so much with the last two days, I was just happy to be able to get this right away.
defmodule Day9 do
@input File.stream!("lib/input", [:trim_bom])
|> Stream.map(&String.trim(&1))
|> Enum.map(&String.to_integer(&1))
def first_invalid() do
last_valid =
@input
|> Stream.with_index()
|> Stream.chunk_every(26, 1, :discard)
|> Stream.map(fn list -> Enum.reverse(list) end)
|> Stream.map(fn [head | rest] -> {head, combinations(rest, 2)} end)
|> Stream.take_while(fn {{val, _ndx}, pairs} ->
Enum.any?(pairs, fn pair ->
Enum.reduce(pair, 0, fn {item, _i}, acc -> acc + item end) == val
end)
end)
|> Stream.map(fn {{_val, ndx}, _} -> ndx end)
|> Enum.reverse()
|> List.first()
{Enum.at(@input, last_valid + 1), last_valid + 1}
end
def combinations(list, k) do
len = Enum.count(list)
if k > len do
:error
else
combine(list, len, k, [], [])
end
end
def combine(_, _, 0, _, _) do
[[]]
end
def combine(list, _, 1, _, _) do
list
|> Enum.map(&[[&1]])
end
def combine(list, len, k, current_combo, all_combos) do
list
|> Stream.unfold(fn [h | t] -> {{h, t}, t} end)
|> Stream.take(len)
|> Enum.reduce(all_combos, fn {x, sublist}, acc ->
sublist_len = Enum.count(sublist)
current_combo_len = Enum.count(current_combo)
if k > sublist_len + current_combo_len + 1 do
# current combo not k-sized but not enough elements to produce another full combo
acc
else
new_curr_combo = [x | current_combo]
new_curr_combo_len = current_combo_len + 1
case new_curr_combo_len do
# k-sized combo found, add it to the list
^k -> [new_curr_combo | acc]
# curr combo not k-sized so try with sub list
_ -> combine(sublist, sublist_len, k, new_curr_combo, acc)
end
end
end)
end
def valid_slice(list, start, stop, target) do
slice =
list
|> Enum.slice(start, stop - start)
sum = Enum.sum(slice)
cond do
sum == target -> Enum.sum([Enum.min(slice), Enum.max(slice)])
sum > target -> valid_slice(list, start + 1, start + 2, target)
sum < target -> valid_slice(list, start, stop + 1, target)
end
end
def part1() do
elem(first_invalid(), 0)
end
def part2() do
{target, max} = first_invalid()
sublist = Enum.slice(@input, 0..(max - 1))
valid_slice(sublist, 0, 1, target)
end
end
combinations =
for a <- options, b <- options, uniq: true do
[a, b] |> Enum.sort() |> List.to_tuple()
end
umm, what? Is generating combinations really that simple? That’s brilliant.
1 Like
This is the first version that worked, I later realized part 1 is a bit stupid and inefficient… but I’m not in the mood to patch it up right now
defmodule Aoc2020.Day09 do
def part1({input, preamble_size}) do
numbers =
input
|> Enum.reverse()
|> Enum.drop(1)
test_numbers =
input
|> Enum.drop(preamble_size)
|> Enum.reverse()
for number <- test_numbers, reduce: {[], numbers} do
{seq, numbers} ->
{[{number, check_number(number, numbers, preamble_size - 1)} | seq],
Enum.drop(numbers, 1)}
end
|> elem(0)
|> Enum.find(&match?({_, false}, &1))
|> elem(0)
end
def part2({input, _}, value) do
numbers = Enum.to_list(input)
find_contiguous(numbers, value)
end
defp find_contiguous(numbers, value) do
case find_range(numbers, value) do
false ->
find_contiguous(Enum.drop(numbers, 1), value)
{min, max} ->
min + max
end
end
defp find_range([first | _] = numbers, value), do: find_range(numbers, {value, first, first}, 0)
defp find_range([], _, _), do: false
defp find_range(_, {value, _, _}, _) when value < 0, do: false
defp find_range(_, {0, min, max}, _), do: {min, max}
defp find_range([number | numbers], {value, min, max}, n) do
find_range(numbers, {value - number, min(min, number), max(max, number)}, n + 1)
end
defp check_number(_, [], 0), do: false
defp check_number(_, _, 0), do: false
defp check_number(a, [b | rest], n) do
!!(rest
|> Enum.take(n)
|> Enum.find(&(&1 + b === a)) ||
check_number(a, rest, n - 1))
end
def input_stream(path, preamble) do
{File.stream!(path)
|> Stream.map(&parse/1), preamble}
end
defp parse(line) do
line
|> String.trim()
|> String.to_integer()
end
end
input = Aoc2020.Day09.input_stream("input.txt", 25)
sum =
Aoc2020.Day09.part1(input)
|> IO.inspect(label: "part1")
Aoc2020.Day09.part2(input, sum)
|> IO.inspect(label: "part2")
part 1 and 2 - O(n m)
defmodule Advent.Day9 do
@preamble 25
def start(part \\ :part1, file \\ "/tmp/input.txt") do
File.read!(file)
|> String.split()
|> Enum.map(&String.to_integer/1)
|> find_invalid_number(part)
end
defp find_sequence(v, _, acc, sum_acc) when sum_acc == v, do: Enum.max(acc) + Enum.min(acc)
defp find_sequence(v, t, acc, sum_acc) when sum_acc > v, do: find_sequence(v, t, acc |> tl(), sum_acc - List.first(acc))
defp find_sequence(v, [h|t], acc, sum_acc), do: find_sequence(v, t, acc ++ [h], sum_acc + h)
defp find_invalid_number(list, :part2), do:
find_invalid_number(list, :part1) |> find_sequence(list, [], 0)
defp find_invalid_number(list, :part1), do: list |> Enum.split(@preamble) |> find_invalid_number()
defp find_invalid_number({lst1, lst2}), do: [] |> get_sum(lst1) |> find_invalid_number(lst2, lst1)
defp find_invalid_number(map_sum, lst2, lst1), do:
Enum.reduce_while(lst2, {lst1, map_sum}, fn o, {lst, msum} ->
case has_key?(msum, o) > 0 do
false -> {:halt, o}
true -> new_list = remove_last(lst)
{:cont, { [o] ++ new_list, [get_sum(%{}, o, new_list)] ++ remove_last(msum)} }
end
end)
defp has_key?(msum, value), do: Enum.find(msum, -1, fn map -> Map.has_key?(map, value) end)
defp remove_last(lst), do: lst |> Enum.reverse() |> tl() |> Enum.reverse()
defp get_sum(acc, [_v]), do: acc
defp get_sum(acc, [h1|t]), do: ([get_sum(%{}, h1, t)] ++ acc) |> get_sum(t)
defp get_sum(acc, _h1, []), do: acc
defp get_sum(acc, h1, [h2|t]), do: get_sum(Map.put(acc, h1 + h2, 1), h1, t)
end
defmodule Aoc.Y2020.D9 do
use Aoc.Boilerplate,
transform: fn raw ->
raw
|> String.split("\n")
|> Enum.map(&String.to_integer/1)
end
@preamble 25
defguard sums_to_needed_sum(first, second, needed_sum) when first + second == needed_sum
def part1(input \\ processed()) do
input
|> Enum.chunk_every(@preamble + 1, 1, :discard)
|> Enum.find_value(fn chunk ->
{last, chunk} = List.pop_at(chunk, -1)
if valid?(chunk, last), do: false, else: last
end)
end
def part2(input \\ processed()) do
invalid_number = input |> part1()
Stream.iterate(2, &(&1 + 1))
|> Enum.find_value(fn chunk_size ->
input
|> Enum.chunk_every(chunk_size, 1, :discard)
|> Enum.find_value(fn chunk ->
sum = Enum.sum(chunk)
if sum == invalid_number do
{min, max} = Enum.min_max(chunk)
min + max
end
end)
end)
end
def valid?(list, next) do
get_two(list, next) != nil
end
def get_two([_first | rest] = list, needed_sum) do
get_two(list, rest, needed_sum)
end
def get_two([], _needed_sum), do: nil
def get_two(list, remainder, needed_sum) when length(list) == 1,
do: get_two(remainder, needed_sum)
def get_two([first | [second | _rest]], _remainder, needed_sum)
when sums_to_needed_sum(first, second, needed_sum) do
{first, second}
end
def get_two([first | [_second | rest]], remainder, needed_sum) do
get_two([first | rest], remainder, needed_sum)
end
end
i tried something different with #AdventofCode2020 Day 9. I did not solve it. I tried to understand and refactor a Day 9 solution from somebody else.
The code (from Martin Gausby and @LostKobrakai) is rewritten or commented here: https://github.com/Introduction-to-Functional-Programming/simple_exercises/blob/main/adolfont/adventofcode/2020/day_09/lib/day09.ex.
I learned a lot.
