sevenseacat

sevenseacat

Author of Ash Framework

Advent of Code 2025 - Day 10

Well some of us wanted a difficulty spike - and today we got one :sweat_smile:

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2025/day10.ex

I don’t think there’s any way to solve part 2 in the “naive” way (eg. with a breadth-first search). There’s no way to reduce the search space enough.

The brainwave is that each set of buttons/target joltage can be modelled as a set of simultaneous equations. Of course they’re not nice simultaneous equations, because there’s more variables (buttons) than equations (output values), and you need to add constraints for non-negative and whole numbers….

Name                     ips        average  deviation         median         99th %
day 10, part 1         78.99       12.66 ms     ±3.07%       12.63 ms       13.76 ms
day 10, part 2          6.90      144.82 ms     ±6.17%      141.61 ms      175.05 ms

Most Liked

hauleth

hauleth

Even with this PRs it doesn’t work, as the solver always used downloaded HiGHS binary instead of using user-provided one. In addition to that HiGHS 1.9.0 (which is downloaded) has some bug, which causes wrong result for my input, and if I change version to 1.12.0 it fails, as it requires additional external libraries (OpenBLAS IIRC). I have forked Dantzig to remove the HiGHS downloader (as it is working improperly anyway) in general and make it more into “CPLEX library” that can be then used with any solver and move solvers downloading and management to separate libs. Something like Nx or Ecto is doing. That way it can use Z3, HiGHS or anything else that can ingest this particular file format (and potentially implement other export formats as well).

@mudasobwa I was also thinking about implementing SMT-LIB generator in Elixir, so it would provide a way to use any SMT solver with Elixir without worrying about compiling binaries and stuff.

mudasobwa

mudasobwa

Creator of Cure

There is no interface, Cure invokes z3 via Erlang port https://github.com/am-kantox/cure-lang/blob/main/src%2Fsmt%2Fcure_smt_process.erl

antoine-duchenet

antoine-duchenet

Yes, my solution does not use any solver library:

defmodule Y2025.D10 do
  use Day, input: "2025/10", part1: ~c"l", part2: ~c"l"

  defp part2(input) do
    lines = input |> parse_input() |> Enum.with_index()

    lines
    |> Map.new(fn {_, idx} -> {idx, 1000} end)
    |> Stream.unfold(fn old_map ->
      new_map =
        Enum.reduce(lines, old_map, fn {l, idx}, acc ->
          maybe_new_min = maybe_min_presses(l)
          Map.update!(acc, idx, &min(&1, maybe_new_min))
        end)

      old_sum = old_map |> Map.values() |> Enum.sum()
      new_sum = new_map |> Map.values() |> Enum.sum()

      {min(old_sum, new_sum), new_map}
    end)
    |> Stream.map(&IO.inspect/1)
    |> Stream.transform({nil, 100, 100}, &until_stable/2)
    |> Enum.take(1)
    |> hd()
  end

  defp until_stable(value, {last_value, requirement, count}) do
    case {value == last_value, count} do
      {true, 0} ->
        {:halt, {value, requirement, count - 1}}

      {true, 1} ->
        {[value], {value, requirement, count - 1}}

      {true, _} ->
        {[], {value, requirement, count - 1}}

      {false, _} ->
        {[], {value, requirement, requirement - 1}}
    end
  end

  defp maybe_min_presses(%{lights: _, buttons: buttons, requirements: requirements}) do
    target_map = index(requirements)

    repair(buttons, target_map)
  end

  defp repair(buttons, target_map) do
    [initial_candidate] =
      buttons
      |> Enum.sort_by(&Enum.count/1, :desc)
      |> Enum.take(1)

    target_sum =
      target_map
      |> Map.values()
      |> Enum.sum()

    initial_presses = div(target_sum, length(initial_candidate))

    buttons_map =
      buttons
      |> Enum.map(&{&1, if(&1 == initial_candidate, do: initial_presses, else: 0)})
      |> Map.new()

    initial_map =
      target_map
      |> Map.keys()
      |> Enum.map(&if Enum.member?(initial_candidate, &1), do: initial_presses, else: 0)
      |> index()

    repair_rec(initial_map, target_map, buttons_map)
  end

  defp repair_rec(target_map, target_map, buttons_map) do
    buttons_map
    |> Map.values()
    |> Enum.sum()
  end

  defp repair_rec(current_map, target_map, buttons_map) do
    candidates =
      buttons_map
      |> Map.keys()
      |> Enum.map(&{score(&1, current_map, target_map), &1})
      |> Enum.sort_by(&elem(&1, 0), :desc)

    add = Enum.take(candidates, Enum.random(1..3))
    sub = Enum.take(candidates, -Enum.random(1..3))

    mutations =
      if Enum.random(0..3) == 0 do
        candidates
        |> Enum.shuffle()
        |> Enum.take(Enum.random(1..3))
      else
        []
      end

    {next_map, new_buttons_map} =
      add
      |> Enum.concat(sub)
      |> Enum.concat(mutations)
      |> Enum.reduce({current_map, buttons_map}, &apply_button/2)

    repair_rec(next_map, target_map, new_buttons_map)
  end

  defp apply_button({score, button}, {current_map, buttons_map}) do
    dir =
      cond do
        score > 0 and Map.get(buttons_map, button) > 0 and Enum.random(0..49) == 0 -> -1
        score > 0 -> 1
        score < 0 and Map.get(buttons_map, button) > 0 -> -1
        true -> 0
      end

    new_map =
      Enum.reduce(button, current_map, fn idx, acc ->
        Map.update!(acc, idx, &(&1 + dir))
      end)

    new_buttons_map = Map.update!(buttons_map, button, fn count -> count + dir end)

    {new_map, new_buttons_map}
  end

  defp score(button, current_map, target_map) do
    Enum.reduce(button, 0, fn idx, acc ->
      c = Map.fetch!(current_map, idx)
      t = Map.fetch!(target_map, idx)

      cond do
        c < t ->
          acc + Math.sqrt(t - c)

        c > t ->
          acc - Math.sqrt(c - t)

        true ->
          acc
      end
    end)
  end

  defp index(lights) do
    lights
    |> Enum.with_index()
    |> Enum.reduce(%{}, fn {light, idx}, acc -> Map.put(acc, idx, light) end)
  end

  defp parse_input(input), do: Enum.map(input, &parse_line/1)

  defp parse_line(line) do
    [lights | rest] =
      ~r/[\[\(\{]([\d\.\#,]+)[\}\)\]]/
      |> Regex.scan(line)
      |> Enum.map(&Enum.at(&1, 1))

    {buttons, [requirements]} =
      rest
      |> Enum.map(
        &(&1
          |> Utils.splitrim(",")
          |> Enum.map(fn num_str -> String.to_integer(num_str) end))
      )
      |> Enum.split(-1)

    %{lights: Utils.splitrim(lights, ""), buttons: buttons, requirements: requirements}
  end
end

It’s basically a recursive reparation approach with genetic programming inspiration. Those parameters converged “pretty quickly” :

  • A single iteration takes around ~1 second, it processes all the machines
  • We wait for the minimum (sum) to be stable for 100 iterations
  • Each iteration “repairs” each machine until it reaches the target numeric counters state, keeping track of the button presses count
  • The initial state (numeric counters and presses count) is filled with a very rough approximation, it is reset on each reparation
  • Each reparation step presses between 1 and 3 buttons, prioritized by a score (how relevant each button is to converge)
  • Each reparation step unpresses between 1 and 3 buttons, prioritized by a score (how irrelevant each button is to converge)
  • There is 25% chance that 1 to 3 additional buttons (mutations) get triggered, pressed or unpressed depending on their relevance to converge
  • There is a slight 2% chance that any button that should be pressed would be unpressed (only if it can be unpressed, it helps to converge quicker by jumping out of rabbit holes caused by the very basic / poor scoring method)

It took ~5min20sec to give the answer for my input, but I suspect it may vary a lot :grin:

Where Next?

Popular in Challenges Top

maennchen
Ok, that was a rough one today. I haven’t found a way to improve the algorithm further. Part 1 runs in .5 seconds, Part 2 in ~ 5 minutes...
New
sasajuric
Note: This topic is to talk about Day 12 of the Advent of Code. For general discussion about the Advent of Code 2018 and links to topics...
New
bjorng
This topic is about Day 16 of the Advent of Code 2021. We have a private leaderboard (shared with users of Erlang Forums): https://adve...
New
dominicletz
This topic is about Day 8 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/le...
New
christhekeele
Continuation of Advent of Code 2022​:christmas_tree:, Day 1: Day 2! Leaderboard:
New
shritesh
This was way too easy after the last few days. Simple map, filter and count. https://github.com/shritesh/advent/blob/main/2023/06.livemd
New
Aetherus
This topic is about Day 4 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/le...
New
Aetherus
I spent 3 hours struggling in part 2, until I noticed a very basic mistake :joy: Here’s my code: https://github.com/Aetherus/advent-of-...
New
igorb
Today is a brute-force day: advent-of-code-2024/lib/advent_of_code2024/day6.ex at main · ibarakaiev/advent-of-code-2024 · GitHub Takes a...
New
bjorng
This topic is about Day 14 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/l...
New

Other popular topics Top

danschultzer
None of the current solutions worked well for me, so I went ahead and built a user management system from scratch. This project took far...
548 29377 241
New
vertexbuffer
Hello, can anybody help here..? I have a list of players and I what to delete an element, but every for loop the list is reverting to ori...
New
senggen
Erlang/OTP 25 [erts-13.2.2] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] 15:22:35.803 [error] gen_event {lager_file_backend...
New
chrismccord
As promised, the first release candidate of Phoenix 1.3.0 is out! This release focuses on code generators with improved project structure...
New
shahryarjb
Hello, I have map which I want to convert it to string like this: the map: %{last_name: "tavakkoli", name: "shahryar"} the string I ne...
New
msaraiva
Surface is an experimental library built on top of Phoenix LiveView and its new LiveComponent API that aims to provide a more declarative...
564 43622 214
New
JakeBecker
TL;DR: I’ve just released an implementation of Microsoft’s IDE-independent Language Server Protocol for Elixir. It adds language support ...
1144 53690 245
New
AngeloChecked
What learn first? Rust or Elixir Hi Elixir community! I’m here because i want learn a new language. I’m a junior developer and mainly i ...
New
dokuzbir
I want to highlight html closing tags when i click a html tag. That works in .html files but doesnt work for html.eex templates. How can...
New
AstonJ
Seen any cool LiveView demos, sample apps or examples? Please post them here! :003:
New

We're in Beta

About us Mission Statement