Advent of Code 2024 - Day 7

I should try this.

defmodule Aoc2024.Solutions.Y24.Day07 do
  alias AoC.Input

  def parse(input, _part) do
    input
    |> Input.stream!(trim: true)
    |> Enum.map(fn line ->
      [result, equation] = String.split(line, ":")
      equation_parts = equation |> String.trim() |> String.split(" ")
      {String.to_integer(result), Enum.map(equation_parts, &String.to_integer/1)}
    end)
  end

  def part_one(problem) do
    Enum.reduce(problem, 0, fn {result, parts}, acc ->
      if valid_equation?(parts, [:+, :*], result), do: result + acc, else: acc
    end)
  end

  def part_two(problem) do
    {solution, problem} =
      Enum.reduce(problem, {0, []}, fn {result, parts}, {solution, next_parts} ->
        if valid_equation?(parts, [:+, :*], result),
          do: {solution + result, next_parts},
          else: {solution, [{result, parts} | next_parts]}
      end)

    Enum.reduce(problem, solution, fn {result, parts}, acc ->
      if valid_equation?(parts, [:+, :*, :||], result), do: result + acc, else: acc
    end)
  end

  defp valid_equation?([part | rest_of_parts], operators, result) do
    length(rest_of_parts)
    |> generate_operator_combinations(operators)
    |> Enum.reduce_while(false, fn combination, acc ->
      if calculate_equation(combination, rest_of_parts, part) == result do
        {:halt, true}
      else
        {:cont, acc}
      end
    end)
  end

  defp generate_operator_combinations(length, operators) do
    Enum.reduce(1..length, [[]], fn _, acc ->
      for symbol <- operators,
          combination <- acc do
        [symbol | combination]
      end
    end)
  end

  defp calculate_equation(_, [], solution), do: solution

  defp calculate_equation([:+ | operators], [number | numbers], solution) do
    calculate_equation(operators, numbers, solution + number)
  end

  defp calculate_equation([:* | operators], [number | numbers], solution) do
    calculate_equation(operators, numbers, solution * number)
  end

  defp calculate_equation([:|| | operators], [number | numbers], solution) do
    calculate_equation(operators, numbers, String.to_integer("#{solution}" <> "#{number}"))
  end
end

Part 2 is slow. :disappointed:

Solution for 2024 day 7
part_one: 5540634308362 in 56.43ms
part_two: 472290821152397 in 16.31s

I calculate all possible combinations of sums and then check if there is at least one sum that matches the test input of a row. For performance reasons, it may be better to first create a list of all possible combinations of operators. Then you could iterate over this list, calculate the result, and stop early if a sum matches the test input.

I improved my performance of part 2 by using a mathematical approach, too.

def concat_nums(a, b) do
  a * Integer.pow(10, Integer.digits(b) |> length) + b
end

Edit: Updated my solution and improved performance

My source code:

concat/2 is faster and simpler than my usage of log 10 and power. Now down to 40 ms.

1 Like

yeah but my version of concat feels a bit like cheating :stuck_out_tongue:

Thanks @cblavier for the pointer, updated mine to the same technique and got it down from:

Solution for 2024 day 7
part_one: 12553187650171 in 4.28ms
part_two: 96779702119491 in 32.84ms

to:

Solution for 2024 day 7
part_one: 12553187650171 in 4.18ms
part_two: 96779702119491 in 8.49ms

Out of interest, is anyone aware of a tool for profiling a run like this to run slow parts to optimise, other than just A/B testing, or general knowledge?

Thanks!

1 Like

LOC: 11

defmodule Aoc2024.Day07 do
  def part1(file), do: main(file, [&+/2, &*/2])
  def part2(file), do: main(file, [&+/2, &*/2, &concat/2])
  def main(file, fs), do: file |> f2ls(&p/1) |> Enum.reduce(0, &(&2 + value(&1, fs)))
  def f2ls(f, fun), do: f |> File.read!() |> String.trim() |> String.split("\n") |> Enum.map(fun)
  def p(l), do: l |> String.replace(":", "") |> String.split() |> Enum.map(&String.to_integer/1)
  def value([out, in1 | rest], fs), do: if(search?(out, in1, rest, fs), do: out, else: 0)
  def search?(out, acc, [], _), do: out == acc
  def search?(out, acc, [h | t], fs), do: Enum.any?(fs, &search?(out, &1.(acc, h), t, fs))
  def concat(a, b), do: Integer.undigits(Integer.digits(a) ++ Integer.digits(b))
end

In my actual solution, f2ls and p are better named via an import:

import Aoc2024.Util
#...
def main(file, fs), do: file |> file_to_lines(&parse/1) |> Enum.reduce(0, &(&2 + value(&1, fs)))
def parse(line), do: line |> String.replace(":", "") |> line_to_list_of_ints

But that bumps up the line count.

3 Likes

Skipped using string to integer and just concatenated the integers, got it down to sub 20ms

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(" ") |> Enum.map(&String.to_integer/1)}
    end)
  end

  @impl true
  def part_one(data) do
    solve(data, false)
  end

  @impl true
  def part_two(data) do
    solve(data, true)
  end

  defp solve(data, has_concat) do
    data
    |> Enum.chunk_every(50)
    |> Task.async_stream(fn chunk ->
      chunk
      |> Enum.filter(fn {test_value, numbers} ->
        form_test_value?(numbers, test_value, has_concat)
      end)
      |> General.map_sum(fn {test_value, _} -> test_value end)
    end)
    |> Enum.reduce(0, fn {:ok, res}, acc -> acc + res end)
  end

  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, false) do
    form_test_value?([a * b | rest], test_value, false) or
      form_test_value?([a + b | rest], test_value, false)
  end

  defp form_test_value?([a | [b | rest]], test_value, true) do
    form_test_value?([a * b | rest], test_value, true) or
      form_test_value?([a + b | rest], test_value, true) or
      form_test_value?([concat(a, concat(0, b)) | rest], test_value, true)
  end

  defp concat(a, 0), do: a
  defp concat(a, b), do: concat(a * 10 + rem(b, 10), div(b, 10))
end
defmodule D7 do
  def p1(file) do
    operators = [&Kernel.+/2, &Kernel.*/2]
    solve(operators, file)
  end

  def p2(file) do
    operators = [&Kernel.+/2, &Kernel.*/2, &String.to_integer("#{&1}#{&2}")]
    solve(operators, file)
  end

  defp solve(operators, file) do
    file
    |> File.read!()
    |> String.split("\n")
    |> Enum.map(fn line ->
      line
      |> String.split([":", " "], trim: true)
      |> Enum.map(&String.to_integer/1)
    end)
    |> Task.async_stream(fn [res | numbers] ->
      if possibly_true?(operators, res, numbers) do
        res
      else
        0
      end
    end)
    |> Enum.reduce(0, fn {:ok, n}, acc -> acc + n end)
  end

  def possibly_true?(_, res, [n]) do
    res == n
  end

  def possibly_true?(operators, res, [n1, n2 | rest]) do
    Enum.any?(operators, fn op ->
      possibly_true?(operators, res, [op.(n1, n2) | rest])
    end)
  end
end

That’s impressive!
But let’s be clear, I don’t want you in my team! :laughing:

2 Likes

Yeah @billylanchantin is amazing but I’d torment him quite a while for proper function and variable names. :003:

1 Like

I think search?/4 should be renamed s?/4

2 Likes

Haha thanks y’all :slight_smile: Don’t worry, I think my AOC code is unreadable too. It’d never get merged in prod! But I’m going for fewest LOC (w/ the stock formatter), so it is what it is sometimes.

1 Like

Iterating backwards, like in Notes for Advent of Code 2024 — Leif's Website :

defmodule Day7 do
  def input() do
    File.read!("/home/leif/Documents/aoc/7")
  end

  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      [objective, xs] = String.split(line, ": ")
      objective = String.to_integer(objective)
      xs = String.split(xs) |> Enum.map(&String.to_integer/1)
      {objective, xs}
    end)
  end

  def go(input) do
    input
    |> parse()
    |> Stream.filter(fn {objective, xs} -> go_rec(objective, Enum.reverse(xs)) end)
    |> Stream.map(&elem(&1, 0))
    |> Enum.sum()
  end

  defp go_rec(obj, [x]) do
    obj == x
  end
  
  defp go_rec(obj, [x | xs]) do
    next_power_of_10 =
      cond do
        x < 10 -> 10
        x < 100 -> 100
        x < 1000 -> 1000
      end

    (rem(obj, next_power_of_10) == x and go_rec(div(obj, next_power_of_10), xs)) or
      (rem(obj, x) == 0 and go_rec(div(obj, x), xs)) or
      (x <= obj and go_rec(obj - x, xs))
  end
end

:timer.tc(Day7, :go, [Day7.input()])

Runs in 5.5ms.

1 Like

Skipping the input file parsing and showing just juicy bits …

  # takes the parsed list of integers [result, a, b, c ...] 
  # and an optional flag to activate concatination
  def search([result | operands], concat? \\ false) do
    # if a valid combination is found, return the calculated result for the final summation
    if search(result, operands, concat?), do: result, else: 0
  end

  # handle the last 2 operands, if the total result is a match, pass true back down the chain
  def search(result, [a, b], concat?) do
    cond do
      a + b == result -> true
      a * b == result -> true
      concat? and a <~> b == result -> true
      true -> false
    end
  end

  # for the preceeding operands, prepend the rolling total to the remaining list tail
  # shortcircuit if the total is already greater than the provided result
  def search(result, [a, b | tail], concat?) do
    cond do
      result < a -> false
      search(result, [a + b | tail], concat?) -> true
      search(result, [a * b | tail], concat?) -> true
      concat? and search(result, [a <~> b | tail], concat?) -> true
      true -> false
    end
  end

  # custom concat operator, the operands have a maximum of 3 digits in the input file
  def left <~> right when right < 10, do: left * 10 + right
  def left <~> right when right < 100, do: left * 100 + right
  def left <~> right when right < 1000, do: left * 1000 + right

My first solution had an exhaustive search of all the operation/operand combination and then ignored all the duplicate solutions. Using cond to return as soon as the first combo was found dropped the part 2 from 800ms to 60ms.
Calling the search function asynchronously cut part 2 time by 60% and memory by 95%!

  def part2(input) do
    input
    |> Enum.map(&search(&1, true))
    |> Enum.sum()
  end

  def part2a(input) do
    input
    |> Task.async_stream(&search(&1, true))
    |> Enum.reduce(0, fn {:ok, x}, acc -> acc + x end)
  end
Name                     ips        average  deviation         median         99th %
part 1                414.96        2.41 ms     ±5.17%        2.36 ms        2.97 ms
part 1 - async        109.09        9.17 ms     ±5.02%        9.11 ms       10.70 ms
part 2 - async         49.66       20.14 ms     ±8.52%       19.76 ms       26.21 ms
part 2                 16.82       59.46 ms     ±2.38%       59.19 ms       64.41 ms

Name                   average  deviation         median         99th %
part 1                 3.18 MB     ±0.00%        3.18 MB        3.18 MB
part 1 - async         1.08 MB     ±0.18%        1.08 MB        1.09 MB
part 2 - async         1.25 MB     ±0.88%        1.25 MB        1.28 MB
part 2                51.33 MB     ±0.00%       51.33 MB       51.33 MB

I still haven’t looked at answers from this thread (closed my eyes and scrolled to the reply section :stuck_out_tongue_closed_eyes: ). I’m on part 2, but sleep debt is kicking in and I’ll likely have to continue catching up in the morning.

Here’s my part 1 solution for now:

#!/usr/bin/env elixir

defmodule Day7.Part1 do
  defp parse(str) do
    [target_str, numbers] =
      str
      |> String.trim()
      |> String.split(":")

    target =
      target_str
      |> String.to_integer()

    args =
      numbers
      |> String.split(" ", trim: true)
      |> Enum.map(&String.to_integer/1)

    max_bit_length =
      args
      |> Enum.reduce(
        0,
        fn n, max_bit_len ->
          bit_len = ceil(:math.log2(n))
          if bit_len > max_bit_len, do: bit_len, else: max_bit_len
        end
      )

    %{target: target, args: args, max_bit_length: max_bit_length}
  end

  defp intercalate(bit_length, argv, separators) do
    case {argv, separators} do
      {<<h::size(^bit_length), h_2::size(^bit_length)>>, <<s::size(1)>>} ->
        <<h::size(bit_length), s::1, h_2::size(bit_length)>>

      {<<h::size(^bit_length), h_2::size(^bit_length), argv_tail::bits>>,
       <<s::size(1), sep_tail::bits>>} ->
        tail = <<h_2::size(bit_length), argv_tail::bits>>
        rest = intercalate(bit_length, tail, sep_tail)
        <<h::size(bit_length), s::size(1), rest::bits>>
    end
  end

  # expects args to be reversed
  defp calculate(bit_length, instructions) do
    case instructions do
      <<a::size(^bit_length)>> ->
        a

      <<a::size(^bit_length), op::size(1), b::bits>> ->
        b = calculate(bit_length, b)

        case op do
          0 -> a + b
          1 -> a * b
        end
    end
  end

  defp count_if_possible(%{target: target, args: args, max_bit_length: bit_length}) do
    argv =
      args
      |> Enum.reduce(
        <<>>,
        fn n, bitstring ->
          # reverses order of args
          <<n::size(bit_length), bitstring::bitstring>>
        end
      )

    argc = args |> Enum.count()
    ops_count = argc - 1

    limit = Bitwise.bsl(1, ops_count + 1)

    Stream.unfold(
      {0, <<0::size(ops_count)>>},
      fn {index, <<i::size(ops_count)>>} = state ->
        if index >= limit, do: nil, else: {state, {index + 1, <<i + 1::size(ops_count)>>}}
      end
    )
    |> Stream.transform(
      nil,
      fn e, nil ->
        {[e |> elem(1)], nil}
      end
    )
    |> Enum.reduce_while(
      0,
      fn op_combo, acc ->
        instructions = intercalate(bit_length, argv, op_combo)
        total = calculate(bit_length, instructions)
        if target == total, do: {:halt, acc + target}, else: {:cont, acc}
      end
    )
  end

  def solve() do
    File.stream!("07/input.txt")
    |> Stream.transform(
      nil,
      fn line, nil ->
        {[parse(line)], nil}
      end
    )
    |> Enum.reduce(
      0,
      fn scenario, acc ->
        acc + count_if_possible(scenario)
      end
    )
    |> IO.puts()
  end
end

Day7.Part1.solve()
1 Like

this is propably highly non performant way to solve the equations. But I figured after a while i could stop solving equation when i found one that matched the wanted result. That speeded it up from hours to 5 mins … for Part1

now im waiting for the part2 answer … will NOT use 5 minutes … hopefully less than 30 min …

tips on improving peformance? i havent even looked at other solutions yet. Just scrolled quickly down

the “problem elephant” in the room is of course this bit of code

which tries to “weed out” too high numbers … but i might remove it … or change the limit …since the largest possible number in the input file is 15 digits i can just check if combined digits is larger than 15 and fail if so

a few things I’m noticing immediately:

  • you don’t need to handle the - and / operators, which reduces your permutations by a lot
  • you generate the permutations list each time for set of operands, you could generate them once in advance and reuse them (there are also solutions that don’t require pregenerated permutations at all, but I haven’t compared the speeds directly)
  • double_pipe/2doesn’t need to handle floats, and you can check your puzzle input to confirm the max char length of the individual operands is 3 and just handle that
2 Likes

oh … my … gawd … i just “assumed” i needed to use all operators … :man_facepalming:

1 Like

and since i dont need / i dont need to handle floats … duh!

1 Like

you may also want to use the restricted +, * & || operator set to short-circuit the calculation if you go over the target as you can never come back down

2 Likes