Advent of Code 2020 - Day 9

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.

GitHub

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

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

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")

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.

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

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

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

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

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()