Advent of Code 2020 - Day 9

Todays challenge was mostly a matter of chunking data in a fitting matter for the questions asked:

https://github.com/LostKobrakai/aoc2020/commit/2734ef2469be42ebcffe9f09d5ce539a2521d608

Edit:
Used a little more time to actually use the proper type for the fifo accumulator needed in part 2: :queue.

https://github.com/LostKobrakai/aoc2020/commit/18dc68ea581b65183db492672bcdf12e5c49d57f

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.

https://github.com/adamu/AdventOfCode2020/blob/main/day9/day9part2.exs

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.

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