billylanchantin

billylanchantin

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
Post #31
leifmetcalf

leifmetcalf

Iterating backwards, like in https://write.as/leif/notes-for-advent-of-code-2024 :

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
Post #32
dpreston

dpreston

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
0
Post #33
mwilsoncoding

mwilsoncoding

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
Post #34
jarlah

jarlah

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

https://github.com/jarlah/advent_of_code/blob/master/lib/2024/day_7/OperatorPermutations.ex

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

https://github.com/jarlah/advent_of_code/blob/master/lib/2024/day_7/Input.ex#L37

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

0
Post #35
dpreston

dpreston

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
Post #36
jarlah

jarlah

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

1
Post #37
jarlah

jarlah

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

1
Post #38
dpreston

dpreston

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
Post #39
jarlah

jarlah

ah that might need some refactoring indead … maybe i should go with strings for the operators instead of the actual functions .. and pattern matching and short curcuit

0
Post #40