Flo0807

Flo0807

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:

https://github.com/Flo0807/adventofcode/blob/main/2024/07.livemd

0
Post #21
lkuty

lkuty

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

1
Post #22
cblavier

cblavier

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

0
Post #23
gazzer82

gazzer82

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
Post #24
billylanchantin

billylanchantin

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
Post #25
woojiahao

woojiahao

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
0
Post #26
ntalfer

ntalfer 

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
0
Post #27
cblavier

cblavier

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

2
Post #28
dimitarvp

dimitarvp

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

1
Post #29
cblavier

cblavier

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

2
Post #30