Advent of Code 2023 - Day 9

I was expecting a hard one, this being Friday and all. But it was pleasant to work with.

advent_of_code/lib/2023/day_09.ex at master · code-shoily/advent_of_code (github.com)

Just the core:

defmodule Day09 do
  def reduce(list, field \\ &List.last/1) do
    reduce(list, [field.(list)], field)
  end

  defp reduce(list, acc, field) do
    if Enum.all?(list, &(&1 == 0)) do
      acc
    else
      new =
        list
        |> Enum.chunk_every(2, 1, :discard)
        |> Enum.map(fn [a, b] -> b - a end)

      reduce(new, [field.(new) | acc], field)
    end
  end
end

Part 1:

lines
|> Enum.map(fn line ->
  Day09.reduce(line)
  |> Enum.reduce(&+/2)
end)
|> Enum.sum()

Part 2:

lines
|> Enum.map(fn line ->
  Day09.reduce(line, &List.first/1)
  |> Enum.reduce(&-/2)
end)
|> Enum.sum()

A bit lenghty but optimizing for not having to call Enum.all?(list, fn n -> n == 0 end)

defmodule AdventOfCode.Y23.Day9 do
  alias AoC.Input, warn: false

  def read_file(file, _part) do
    Input.stream!(file, trim: true)
  end

  def parse_input(input, _part) do
    input |> Enum.map(&list_of_ints/1)
  end

  defp list_of_ints(str) do
    str |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)
  end

  def part_one(problem) do
    problem
    |> Enum.map(&next_num/1)
    |> Enum.sum()
  end

  def next_num(list) do
    List.last(list) + _next_num(list)
  end

  defp _next_num(list) do
    case diffs(list) do
      {_, true} ->
        0

      {diffs, _} ->
        last = List.last(diffs)
        sub = _next_num(diffs)
        last + sub
    end
  end

  defp diffs([h | t]) do
    {diffs, {_, all_zero?}} =
      Enum.map_reduce(t, {h, _all_zero? = true}, fn next, {prev, all_zero?} ->
        new = next - prev
        {new, {next, all_zero? and new == 0}}
      end)

    {diffs, all_zero?}
  end

  def prev_num([h | _] = list) do
    h - _prev_num(list)
  end

  defp _prev_num(list) do
    case diffs(list) do
      {_, true} ->
        0

      {[dh | _] = diffs, _} ->
        sub = _prev_num(diffs)
        dh - sub
    end
  end

  def part_two(problem) do
    problem
    |> Enum.map(&prev_num/1)
    |> Enum.sum()
  end
end

Share my failure on Part 1

I was trying polynomial regression, and it explodes

The regression function for working out the coefficients of the polynomial:

# The param `y` is a list of numbers.
regression = fn y ->
  y =
    y
    |> Nx.tensor(type: :f64)
    |> Nx.new_axis(0)
    |> Nx.transpose()

  {n, 1} = Nx.shape(y)

  v =
    0..(n - 1)
    |> Enum.to_list()
    |> Nx.tensor(type: :f64)

  x =
    for p <- 0..(n-1) do
      Nx.pow(v, p)
    end
    |> Nx.stack()
    |> Nx.transpose()

  xt = Nx.transpose(x)

  coeffs =
    xt
    |> Nx.dot(x)
    |> Nx.LinAlg.invert()
    |> Nx.dot(xt)
    |> Nx.dot(y)

  errors = Nx.subtract(y, Nx.dot(x, coeffs))

  {coeffs, errors}
end

And the function for predicting the last value of a line:

# x is the index of the yet-to-be-solved number in a line.
predict = fn x, {coeffs, errors} ->
  {n, 1} = Nx.shape(coeffs)

  x = 
  0..(n - 1)
  |> Enum.map(& x ** &1)
  |> Nx.tensor()
  |> Nx.new_axis(0)

  x
  |> Nx.dot(coeffs)
  |> Nx.add(errors)
  |> Nx.mean()
  |> Nx.to_number()
  |> round()
end

Not sure if unfold was the best choice for this use case but it ended up quite clean.

solve = fn first? ->
  File.stream!("input.txt")
  |> Stream.map(fn ln -> 
    String.split(ln)
    |> Enum.map(&String.to_integer/1)
    |> Stream.unfold(fn l ->
      case Enum.all?(l, & &1 == 0) do
        true -> nil
        false -> {Enum.at(l, first? && 0 || -1), Enum.zip_with(tl(l), l, &-/2)}
      end
    end)
    |> then(fn ends ->
      case first? do
        true -> ends |> Enum.reverse() |> Enum.reduce(&-/2)
        false -> ends |> Enum.sum()
      end
    end)
  end)
  |> Enum.sum()
end

IO.inspect(solve.(false), label: "Star 1")
IO.inspect(solve.(true), label: "Star 2")

yeah this day was very easy

in p1 I accumulated only last element of each sub-line before predicting history as I anticipated there would be memory issues in p2 if you were accumulating all sub-lines
…but p2 was as easy as p1

At first I used reduce_while/3 to solve it, but then switched to Stream.unfold/2 inspired by @lbm364dl:

https://github.com/ibarakaiev/advent-of-code-2023/blob/main/lib/advent_of_code/day_9.ex

Did not know there was an AoC thread here! This is my approach:

https://github.com/woojiahao/aoc/blob/main/lib/aoc/2023/day_9.ex

Busted out the recursive functions today:

Part 1

defmodule Part1 do
  def difference(history, fun), do: difference(history, [], fun)

  def difference(prev_diffs, rest_diffs, fun) do
    if Enum.all?(prev_diffs, &(&1 == 0)) do
      fun.(rest_diffs, 0)
    else
      next_diffs =
        prev_diffs
        |> Enum.chunk_every(2, 1, :discard)
        |> Enum.map(fn xs -> Enum.reduce(xs, &Kernel.-/2) end)

      difference(next_diffs, [prev_diffs | rest_diffs], fun)
    end
  end

  def predictr([], extrapolation), do: extrapolation

  def predictr([diffs | rest], extrapolation) do
    predictr(rest, extrapolation + List.last(diffs))
  end
end

histories
|> Enum.map(fn history -> Part1.difference(history, &Part1.predictr/2) end)
|> Enum.sum()

Part 2

defmodule Part2 do
  def predictl([], extrapolation), do: extrapolation

  def predictl([[first | _] | rest], extrapolation) do
    predictl(rest, first - extrapolation)
  end
end

histories
|> Enum.map(fn history -> Part1.difference(history, &Part2.predictl/2) end)
|> Enum.sum()

There’s a private leaderboard you can join using the code 3241528-139712b3.

My solution works with the test but the actual input sequences aren’t becoming all zeros at the end, there’s a single non-zero value that I’m unable to get rid of.

For example:

12 20 25 35 64 137 305 670 1420 2874 5537 10165 17840 30055 48809 76712 117100 174160 253065 360119 502912

becomes

[4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Maybe I’m misunderstanding the challenge.

defmodule Day09 do

  def part1(input) do
    parse(input)
   |> Enum.map(&prediction/1)
   |> Enum.sum
  end

  def prediction(sequence, last_values \\ []) do
    last = List.last(sequence)
    cond do
      [0] == Enum.uniq(sequence) -> Enum.sum(last_values)
      true -> prediction(next_sequence(sequence), last_values ++ [last])
    end
  end
    
  def next_sequence(sequence, new_sequence \\ [])
  def next_sequence([_last], new_sequence), do: new_sequence
  def next_sequence([head | tail], new_sequence) do
    new_value = abs(head - List.first(tail))
    next_sequence(tail, new_sequence ++ [new_value])
  end
  
  def parse(raw_report) do
    raw_report
    |> String.split("\n")
    |> Enum.map(fn line -> line
        |> String.split
        |> Enum.map(&String.to_integer/1)
        end)
  end
end