Advent of Code 2024 - Day 7

I like recursion Back in 1996-98, I did a lot of Scheme (MIT Scheme) and fell in love with that language, FP in general and tail recursion (and TCO of course). We had a teacher in Belgium who went to the USAs and was exposed to all of it. I had a really good time.

Excluding I/O, when I call C for the produced? function using a NIF, the code executes ± 3 times faster.

#!/usr/bin/env elixir

# AoC 2024. day 7.

###########################################################
# Part 1

defmodule Part1 do
  def produced?(test_value, numbers), do: produced?(test_value, numbers, nil)
  def produced?(test_value, [], value), do: value == test_value
  def produced?(test_value, [x | numbers], nil), do: produced?(test_value, numbers, x)
  def produced?(test_value, _numbers, value) when value > test_value, do: false
  def produced?(test_value, [x | numbers], value) do
    produced?(test_value, numbers, value*x) || produced?(test_value, numbers, value+x)
  end
end

File.stream!("../day07.txt")
|> Stream.map(fn line -> Regex.scan(~r/\d+/, line) |> Enum.map(fn [x] -> String.to_integer(x) end) end)
|> Enum.reduce(0, fn [test_value | numbers], sum ->
  if Part1.produced?(test_value, numbers), do: sum+test_value, else: sum
end)
|> IO.inspect(label: "Part 1")

###########################################################
# Part 2

defmodule Part2 do
  def produced?(test_value, numbers), do: produced?(test_value, numbers, nil)
  def produced?(test_value, [], value), do: value == test_value
  def produced?(test_value, [x | numbers], nil), do: produced?(test_value, numbers, x)
  def produced?(test_value, _numbers, value) when value > test_value, do: false
  def produced?(test_value, [x | numbers], value) do
    produced?(test_value, numbers, value*x) ||
    produced?(test_value, numbers, value+x) ||
    produced?(test_value, numbers, value*10**ndigits(x)+x)
  end
  @spec ndigits(pos_integer()) :: pos_integer()
  defp ndigits(x), do: trunc(:math.floor(:math.log(x)/:math.log(10))+1)
end

File.stream!("../day07.txt")
|> Stream.map(fn line -> Regex.scan(~r/\d+/, line) |> Enum.map(fn [x] -> String.to_integer(x) end) end)
|> Enum.reduce(0, fn [test_value | numbers], sum ->
  if Part2.produced?(test_value, numbers), do: sum+test_value, else: sum
end)
|> IO.inspect(label: "Part 2")

My original version ran in 0.9 seconds for both parts. Since that was a little bit slow for my taste I optimized the concatenation of integers. My first version did it like so:

String.to_integer(Integer.to_string(a) <> Integer.to_string(b))

I rewrote that to operate directly on the integers. That reduced the time to 0.1 seconds for both parts.

The version shown here includes additional refactoring to share the solutions for parts 1 and 2.

https://github.com/bjorng/advent-of-code/blob/main/2024/day07/lib/day07.ex

My solution is to inverse the calculation from right to left, for example:

3267: 81 40 27

I try

3267: 27 40 81  (initial)
  3240 (= 3267 - 27): 40 81
    3200 (= 3240 - 40): 81
      3119 (= 3200 - 81):  => false
    81 (= 3140 / 40): 81
      0 (= 81 - 81):  => true

I accidentally deleted my code ToT

And for the inverse of concatenation, it’s just

defp truncate(a, b) when a < b, do: nil

defp truncate(a, 0), do: a

defp truncate(a, b) when rem(a, 10) != rem(b, 10), do: nil

defp truncate(a, b), do: truncate(div(a, 10), div(b, 10))

When you measure time execution, do you take I/O into consideration or not (time taken to read the file) ? I wanted to avoid it but since I am using Stream I/O and CPU are interleaved.

I rewrote my solution.

defmodule AoC2024.Day07 do
  def part_1(input) do
    input
    |> Enum.filter(fn {result, rev_operands} ->
      solvable_1?(result, rev_operands)
    end)
    |> Enum.map(&elem(&1, 0))
    |> Enum.sum()
  end

  def part_2(input) do
    input
    |> Enum.filter(fn {result, rev_operands} ->
      solvable_2?(result, rev_operands)
    end)
    |> Enum.map(&elem(&1, 0))
    |> Enum.sum()
  end

  defp solvable_1?(target, []) do
    target == 0
  end

  defp solvable_1?(target, [h | t]) do
    solvable_1?(target - h, t) or
    (rem(target, h) == 0 and solvable_1?(div(target, h), t))
  end

  defp solvable_2?(target, []) do
    target == 0
  end
  
  defp solvable_2?(target, [h | t]) do
    solvable_2?(target - h, t) or
    (rem(target, h) == 0 and solvable_2?(div(target, h), t)) or
    ((truncated = truncate(target, h)) && solvable_2?(truncated, t))
  end

  defp truncate(a, b) when a < b, do: false

  defp truncate(a, 0), do: a

  defp truncate(a, b) when rem(a, 10) != rem(b, 10), do: false

  defp truncate(a, b) do
    truncate(div(a, 10), div(b, 10))
  end
end

Much easier than yesterday! I still went through a few iterations before landing on this one:

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day07.ex

This takes about 250ms to run on my machine for part 2.

My aim for this year is to have each solution run in less than a second - we’ll see how far I get lol

I use the time reported by mix test.

Running ExUnit with seed: 794416, max_cases: 16

....
Finished in 0.1 seconds (0.00s async, 0.1s sync)
4 tests, 0 failures

So that includes all I/O, as well as the time for running the examples.

20 lines

Relatively simple day!

defmodule AOC.Y2024.Day7 do
  @moduledoc false

  use AOC.Solution

  @impl true
  def load_data() do
    Data.load_day(2024, 7)
    |> Enum.map(fn line -> String.split(line, ":") end)
    |> Enum.map(fn [test_value, numbers] ->
      {String.to_integer(test_value),
       numbers |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)}
    end)
  end

  @impl true
  def part_one(data) do
    data
    |> Enum.filter(fn {test_value, numbers} -> form_test_value?(numbers, test_value) end)
    |> General.map_sum(fn {test_value, _} -> test_value end)
  end

  @impl true
  def part_two(data) do
    data
    |> Enum.filter(fn {test_value, numbers} -> form_test_value?(numbers, test_value, true) end)
    |> General.map_sum(fn {test_value, _} -> test_value end)
  end

  defp form_test_value?(numbers, test_value, has_concat \\ false)
  defp form_test_value?([acc | _], test_value, _) when acc > test_value, do: false
  defp form_test_value?([test_value], test_value, _), do: true
  defp form_test_value?([_], _, _), do: false

  defp form_test_value?([a | [b | rest]], test_value, has_concat) do
    initial =
      form_test_value?([a * b | rest], test_value, has_concat) or
        form_test_value?([a + b | rest], test_value, has_concat)

    if has_concat do
      initial or form_test_value?([String.to_integer("#{a}#{b}") | rest], test_value, has_concat)
    else
      initial
    end
  end
end

This was much easier than yesterday!

And I’m always proud of myself when I manage to write recursive code (mostly because I don’t need recursive code very often in my daily job)

Part1

defmodule Advent.Y2024.Day07.Part1 do
  def run(puzzle) do
    puzzle
    |> parse()
    |> Enum.filter(fn {result, nums} -> eval(result, nums) end)
    |> Enum.map(&elem(&1, 0))
    |> Enum.sum()
  end

  def parse(puzzle) do
    puzzle
    |> String.split("\n")
    |> Enum.map(fn equation ->
      [result, numbers] = String.split(equation, ": ")
      numbers = numbers |> String.split(" ") |> Enum.map(&String.to_integer/1)
      {String.to_integer(result), numbers}
    end)
  end

  def eval(result, numbers, total \\ nil)
  def eval(result, [], total), do: total == result
  def eval(result, [number | tail], nil), do: eval(result, tail, number)
  def eval(result, _numbers, total) when total > result, do: false

  def eval(result, [number | tail], total) do
    eval(result, tail, total + number) or eval(result, tail, total * number)
  end
end

Part2

defmodule Advent.Y2024.Day07.Part2 do
  alias Advent.Y2024.Day07.Part1

  def run(puzzle) do
    puzzle
    |> Part1.parse()
    |> Task.async_stream(fn {result, nums} -> {eval(result, nums), result} end)
    |> Stream.map(fn {:ok, output} -> output end)
    |> Stream.filter(fn {eval, _result} -> eval end)
    |> Stream.map(fn {_eval, result} -> result end)
    |> Enum.sum()
  end

  def eval(result, numbers, acc \\ nil)
  def eval(result, [], acc), do: acc == result
  def eval(result, [number | tail], nil), do: eval(result, tail, number)
  def eval(result, _numbers, acc) when acc > result, do: false

  def eval(result, [number | tail], acc) do
    eval(result, tail, acc + number) or
      eval(result, tail, acc * number) or
      eval(result, tail, concat(acc, number))
  end

  defp concat(a, b) when b < 10, do: a * 10 + b
  defp concat(a, b) when b < 100, do: a * 100 + b
  defp concat(a, b) when b < 1000, do: a * 1000 + b
end

It takes about 10ms for part1 and 40ms for part2
edit: using Task.async_stream and part 2 is now running in 20ms