Day 10: Factory

advent_of_code/2025/day-10.livemd

Awesome YAMAUCHI

@TORIFUKUKaiou

livebooks

Share to X

Share to Bluesky

More notebooks

Day 10: Factory

Part 1

defmodule Awesome do
  def combination(_, 0), do: [[]]
  def combination([], _), do: []

  def combination([x | xs], n) do
    for(y <- combination(xs, n - 1), do: [x | y]) ++ combination(xs, n)
  end
end

defmodule AdventOfCode2025Day10Part1Solver do
  def run(list) do
    Enum.reduce(list, [], &amp;solve/2)
    |> Enum.sum()
  end

  defp solve({pattern, buttons}, acc) do
    Range.new(1, Enum.count(buttons))
    |> Enum.reduce_while(nil, fn i, nil ->
      Awesome.combination(buttons, i)
      |> Enum.any?(fn selected_buttons -> do_solve(selected_buttons, pattern) end)
      |> if(do: {:halt, i}, else: {:cont, nil})
    end)
    |> List.wrap()
    |> Kernel.++(acc)
  end

  defp do_solve(selected_buttons, pattern) do
    init = String.duplicate(".", String.length(pattern)) |> String.to_charlist()
    
    selected_buttons
    |> Enum.reduce(init, fn list, acc ->
      Enum.reduce(list, acc, fn i, acc ->
        List.update_at(acc, i, fn 
          ?. -> ?#
          ?# -> ?.
        end)
      end)
    end)
    |> List.to_string()
    |> Kernel.==(pattern)    
  end
end

defmodule AdventOfCode2025Day10Part1 do
  def run(input) do
    input
    |> parse_input()
    |> solve()
  end

  defp solve(list), do: AdventOfCode2025Day10Part1Solver.run(list)

  defp parse_input(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(&amp;parse_line/1)
  end

  defp parse_line(line) do
    line =
      case String.split(line, "{", parts: 2) do
        [left, _] -> left
        [left] -> left
      end

    [_, pattern] = Regex.run(~r/\[([.#]+)\]/, line)
    buttons =
      Regex.scan(~r/\(([^)]*)\)/, line)
      |> Enum.map(fn [_, inside] ->
        inside
        |> String.split(",", trim: true)
        |> Enum.map(&amp;String.to_integer/1)
      end)

    {pattern, buttons}
  end
end

input = """
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
"""

AdventOfCode2025Day10Part1.run(input)

Part 2

Due to poor processing efficiency, this solution only produces results for the sample input.

defmodule AdventOfCode2025Day10Part2Solver do
  def run(list) do
    list
    |> Enum.reduce([], &amp;solve/2)
    |> Enum.sum()
  end

  def solve({joltage_levels, buttons}, acc) do
    max_value = Enum.max(joltage_levels)
    count_of_press = do_solve(joltage_levels, buttons, max_value, 0, List.duplicate(0, Enum.count(buttons)), List.duplicate(0, Enum.count(joltage_levels)), buttons, 100_000_000)

    [count_of_press | acc]
  end

  defp do_solve(joltage_levels, [], max_value, _index, as, acc, buttons, count_of_press) do
    if Enum.all?(as, &amp; &amp;1 == max_value) do
      count_of_press
    else
      if joltage_levels == acc do
        new_count_of_press = min(Enum.sum(as), count_of_press)
        updated_as = update_as(as, max_value)
        do_solve(joltage_levels, buttons, max_value, 0, updated_as, List.duplicate(0, Enum.count(joltage_levels)), buttons, new_count_of_press)
      else
        updated_as = update_as(as, max_value)
        do_solve(joltage_levels, buttons, max_value, 0, updated_as, List.duplicate(0, Enum.count(joltage_levels)), buttons, count_of_press)
      end
    end
  end

  defp do_solve(joltage_levels, [head | tail], max_value, index, as, acc, buttons, count_of_press) do
    new_acc = 
      head
      |> Enum.map(&amp; &amp;1 * Enum.at(as, index))
      |> Enum.zip_with(acc, fn x, y -> x + y end)
    
    do_solve(joltage_levels, tail, max_value, index + 1, as, new_acc, buttons, count_of_press)
  end

  defp update_as(as, max_value) do
    base = max_value + 1

    as
    |> Enum.reverse()
    |> inc_rev(base)
    |> Enum.reverse()
  end

  # 末尾（revの先頭）から+1して、baseで繰り上げ
  defp inc_rev([], _base), do: []

  defp inc_rev([d | rest], base) do
    if d + 1 < base do
      [d + 1 | rest]
    else
      [0 | inc_rev(rest, base)]
    end
  end
end


defmodule AdventOfCode2025Day10Part2 do
  def run(input) do
    input
    |> parse_input()
    |> solve()
  end

  defp solve(list), do: AdventOfCode2025Day10Part2Solver.run(list)

  defp parse_input(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(&amp;parse_line/1)
  end

  defp parse_line(line) do
    line =
      case String.split(line, "]", parts: 2) do
        [_left, right] -> right
        [right] -> right
      end

    joltage_levels =
      Regex.run(~r/{(.+)}/, line)
      |> Enum.at(1)
      |> String.split(",", trim: true)
      |> Enum.map(&amp;String.to_integer/1)
    buttons =
      Regex.scan(~r/\(([^)]*)\)/, line)
      |> Enum.map(fn [_, inside] ->
        inside
        |> String.split(",", trim: true)
        |> Enum.reduce(List.duplicate(0, Enum.count(joltage_levels)), fn n, acc ->
          index = String.to_integer(n)
          List.replace_at(acc, index, 1)
        end)
      end)

    {joltage_levels, buttons}
  end
end

input = """
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
"""

AdventOfCode2025Day10Part2.run(input)

Part 2 with Codex

After rewriting the code with the help of Codex, it is now able to produce the correct answer for the full input as well.

defmodule AdventOfCode2025Day10Part2SolverCodex do
  @max 9_223_372_036_854_775_807

  def run(list) do
    list
    |> Enum.map(&amp;solve_line/1)
    |> Enum.sum()
  end

  defp solve_line({target, buttons}) do
    solve(buttons, target)
  end

  defp solve(buttons, target) do
    m = length(buttons)

    n =
      case List.flatten(buttons) do
        [] -> 0
        flat -> Enum.max(flat) + 1
      end

    table = build_table(n, m, buttons, target)
    {table, pivot_cols} = gauss(table, m)
    pivot_set = MapSet.new(pivot_cols)

    free_cols =
      if m == 0 do
        []
      else
        for col <- 0..(m - 1), not MapSet.member?(pivot_set, col), do: col
      end

    lim = Enum.sum(target)
    table = Enum.map(table, &amp;List.to_tuple/1)
    free_cols = List.to_tuple(free_cols)
    pivot_cols = List.to_tuple(pivot_cols)

    dfs(0, List.duplicate(0, m), 0, table, free_cols, pivot_cols, lim, @max, m)
  end

  defp build_table(n, m, buttons, target) do
    base = List.duplicate(List.duplicate(0, m + 1), n)

    base =
      Enum.with_index(base)
      |> Enum.map(fn {row, idx} ->
        List.replace_at(row, m, Enum.at(target, idx))
      end)

    Enum.reduce(Enum.with_index(buttons), base, fn {button, col_idx}, acc ->
      Enum.reduce(button, acc, fn row_idx, acc2 ->
        List.update_at(acc2, row_idx, fn row ->
          List.replace_at(row, col_idx, 1)
        end)
      end)
    end)
  end

  defp gauss(table, var_count) do
    cond do
      var_count == 0 ->
        {table, []}

      table == [] ->
        {table, []}

      true ->
        n = length(table)
        last_col = var_count

        {table, _rank, pivots} =
          Enum.reduce(0..(var_count - 1), {table, 0, []}, fn col, {table, rank, pivots} ->
            case find_pivot(table, rank, col) do
              nil ->
                {table, rank, pivots}

              pivot_row ->
                table = swap_rows(table, rank, pivot_row)
                pivot_val = table |> Enum.at(rank) |> Enum.at(col)
                table = eliminate(table, rank, col, pivot_val, n, last_col)
                {table, rank + 1, pivots ++ [col]}
            end
          end)

        {table, pivots}
    end
  end

  defp find_pivot(table, start_row, col) do
    table
    |> Enum.drop(start_row)
    |> Enum.with_index(start_row)
    |> Enum.find_value(fn {row, idx} ->
      if Enum.at(row, col) != 0, do: idx, else: nil
    end)
  end

  defp swap_rows(table, i, i), do: table

  defp swap_rows(table, i, j) do
    row_i = Enum.at(table, i)
    row_j = Enum.at(table, j)

    table
    |> List.replace_at(i, row_j)
    |> List.replace_at(j, row_i)
  end

  defp eliminate(table, rank, col, pivot, n, _last_col) do
    if rank + 1 >= n do
      table
    else
      pivot_row = Enum.at(table, rank)
      pivot_t = List.to_tuple(pivot_row)

      Enum.reduce((rank + 1)..(n - 1), table, fn row_idx, acc ->
        row = Enum.at(acc, row_idx)
        val = Enum.at(row, col)

        if val == 0 do
          acc
        else
          g = gcd(pivot, val)
          t = div(val, g)
          tt = div(pivot, g)

          new_row =
            row
            |> Enum.with_index()
            |> Enum.map(fn {cell, j} ->
              if j < col do
                cell
              else
                cell * tt - elem(pivot_t, j) * t
              end
            end)

          List.replace_at(acc, row_idx, new_row)
        end
      end)
    end
  end

  defp dfs(idx, now, nowsum, table, free_cols, pivot_cols, lim, best, var_count) do
    cond do
      nowsum >= best ->
        best

      idx == tuple_size(free_cols) ->
        case back_solve(now, table, pivot_cols, var_count) do
          {:ok, filled} ->
            min(best, Enum.sum(filled))

          :invalid ->
            best
        end

      true ->
        col = elem(free_cols, idx)

        Enum.reduce(0..lim, best, fn c, acc_best ->
          new_sum = nowsum + c

          if new_sum >= acc_best do
            acc_best
          else
            new_now = List.replace_at(now, col, c)
            dfs(idx + 1, new_now, new_sum, table, free_cols, pivot_cols, lim, acc_best, var_count)
          end
        end)
    end
  end

  defp back_solve(now, table, pivot_cols, var_count) do
    rank = tuple_size(pivot_cols)

    if rank == 0 do
      {:ok, now}
    else
      result =
        Enum.reduce_while((rank - 1)..0//-1, now, fn row_idx, acc ->
          col = elem(pivot_cols, row_idx)
          row = Enum.at(table, row_idx)
          right = elem(row, var_count)

          right =
            if col + 1 <= var_count - 1 do
              Enum.reduce((col + 1)..(var_count - 1), right, fn j, acc2 ->
                acc2 - elem(row, j) * Enum.at(acc, j)
              end)
            else
              right
            end

          tm = elem(row, col)
          val = if tm != 0 and rem(right, tm) == 0, do: div(right, tm), else: nil

          cond do
            tm == 0 and right != 0 ->
              {:halt, :invalid}

            tm == 0 ->
              {:cont, acc}

            rem(right, tm) != 0 ->
              {:halt, :invalid}

            val < 0 ->
              {:halt, :invalid}

            true ->
              {:cont, List.replace_at(acc, col, val)}
          end
        end)

      case result do
        :invalid -> :invalid
        updated -> {:ok, updated}
      end
    end
  end

  defp gcd(a, b) do
    Integer.gcd(abs(a), abs(b))
  end
end

defmodule AdventOfCode2025Day10Part2Codex do
  def run(input) do
    input
    |> parse_input()
    |> solve()
  end

  defp solve(list), do: AdventOfCode2025Day10Part2SolverCodex.run(list)

  defp parse_input(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(&amp;parse_line/1)
  end

  defp parse_line(line) do
    target =
      Regex.run(~r/{([^}]+)}/, line)
      |> Enum.at(1)
      |> String.split(",", trim: true)
      |> Enum.map(&amp;String.to_integer/1)

    buttons =
      Regex.scan(~r/\(([^)]*)\)/, line)
      |> Enum.map(fn [_, inside] ->
        inside
        |> String.split(",", trim: true)
        |> Enum.map(&amp;String.to_integer/1)
      end)

    {target, buttons}
  end
end

input = """
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
"""

AdventOfCode2025Day10Part2Codex.run(input)

Other notebooks:

@DeSchoel

Elixir_Curriculum

BookSearch: Authors

deprecated_book_search_authors.livemd

tutorial advanced testing debugging sql jason kino youtube hidden_cell

2026-1-10
Ryo Wakabayashi
@RyoWakabayashi

elixir-learning

Image Classification Client

Image_classification_client.livemd

tutorial advanced data-science exla axon_onnx evision flow req kino nx

2023-6-25
@DeSchoel

Elixir_Curriculum

Games: Supervisor Setup

deprecated_games_supervisor_setup.livemd

tutorial advanced gen-server otp jason kino youtube hidden_cell

2026-1-10
Charlie Roth
@charlieroth

makemore

Makemore

makemore.livemd

tutorial advanced data-science explorer kino axon tucan kino_vega_lite

2024-1-4
Neven DREAN
@ndrean

RTC-HLS

Untitled notebook

ws-evision.livemd

tutorial advanced evision ex_cmd kino

2024-7-6
Membrane Framework
@membraneframework

membrane_demo

Speech to text

speech_to_text.livemd

tutorial advanced bumblebee exla membrane_core membrane_portaudio_plugin

2024-1-30
Ryo Wakabayashi
@RyoWakabayashi

elixir-learning

Amazon Translate

translate.livemd

advanced apis ex_aws_translate jason poison hackney sweet_xml kino ex_aws

2022-12-20

Back