vkryukov

Advent of Code 2025 - Day 8

Nice little problem. The right data structure is half the solution!

defmodule Y2025.Day08 do
  def pairs(enum) do
    l = enum |> Enum.with_index()
    for {a, i} <- l, {b, j} <- l, i < j, do: {a, b}
  end

  def norm([x1, y1, z1], [x2, y2, z2]),
    do: (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2)

  defmodule Circuits do
    def new(enum), do: Enum.into(enum, %{}, fn x -> {x, MapSet.new([x])} end)

    def fuze(circuits, c1, c2) do
      s1 = circuits[c1]
      s2 = circuits[c2]

      if s1 == s2 do
        circuits
      else
        s = MapSet.union(s1, s2)
        s |> Enum.reduce(circuits, fn el, circuits -> Map.put(circuits, el, s) end)
      end
    end

    def product_top_3_sizes(circuits) do
      circuits
      |> Enum.uniq_by(&elem(&1, 1))
      |> Enum.map(fn {_, v} -> MapSet.size(v) end)
      |> Enum.sort(:desc)
      |> Enum.take(3)
      |> Enum.product()
    end
  end

  def parse(s), do: s |> String.split("\n") |> Enum.map(&parse_line/1) |> Circuits.new()

  def parse_line(s), do: s |> String.trim() |> String.split(",") |> Enum.map(&String.to_integer/1)

  def fuze_while(circuits, start, fun) do
    Map.keys(circuits)
    |> pairs()
    |> Enum.map(fn {a, b} -> {a, b, norm(a, b)} end)
    |> Enum.sort_by(&elem(&1, 2))
    |> Enum.reduce_while(start, fun)
  end

  def part1(s, n) do
    circuits = parse(s)

    fuze_while(circuits, {circuits, 0}, fn {c1, c2, _}, {circuits, count} ->
      if count == n do
        {:halt, circuits |> Circuits.product_top_3_sizes()}
      else
        {:cont, {Circuits.fuze(circuits, c1, c2), count + 1}}
      end
    end)
  end

  def part2(s) do
    circuits = parse(s)

    n = map_size(circuits)

    fuze_while(circuits, circuits, fn {c1, c2, _}, circuits ->
      if MapSet.union(circuits[c1], circuits[c2]) |> MapSet.size() == n do
        {:halt, List.first(c1) * List.first(c2)}
      else
        {:cont, Circuits.fuze(circuits, c1, c2)}
      end
    end)
  end
end

13 comments

#advent-of-code #2025

3 431 13

2025-12-13 14:42:27 UTC

First 10 of 13 Posts

bjorng

Erlang Core Team

I implemented a union-find algorithm to group junction boxes into circuits. The combined runtime for both part is 0.4 seconds on my computer.

defmodule Day08 do
  def part1(input, n) do
    boxes = parse(input)
    boxes
    |> make_pairs
    |> Enum.take(n)
    |> group_part1(boxes)
    |> Enum.map(fn {_, {_, size}} -> size end)
    |> Enum.sort(:desc)
    |> Enum.take(3)
    |> Enum.product
  end

  defp group_part1(pairs, boxes) do
    forest = union_find_init(boxes)
    Enum.reduce(pairs, forest, fn pair, forest ->
      {_done?, forest} = add_pair(forest, pair)
      forest
    end)
  end

  def part2(input) do
    boxes = parse(input)
    boxes
    |> make_pairs
    |> group_part2(boxes)
    |> then(fn {{x1, _, _}, {x2, _, _}} ->
      x1 * x2
    end)
  end

  defp group_part2(pairs, boxes) do
    forest = union_find_init(boxes)
    Enum.reduce_while(pairs, forest, fn pair, forest ->
      {done?, forest} = add_pair(forest, pair)
      case done? do
        true ->
          {:halt, pair}
        false ->
          {:cont, forest}
      end
    end)
  end

  defp make_pairs(boxes) do
    boxes
    |> Enum.flat_map(fn a ->
      Enum.flat_map(boxes, fn b ->
        if a < b do
          [{squared_distance(a, b), {a, b}}]
        else
          []
        end
      end)
    end)
    |> Enum.sort
    |> Enum.map(&elem(&1, 1))
  end

  defp squared_distance({x1, y1, z1}, {x2, y2, z2}) do
    xd = x1 - x2
    yd = y1 - y2
    zd = z1 - z2
    xd * xd + yd * yd + zd * zd
  end

  defp parse(input) do
    input
    |> Enum.map(fn line ->
      line
      |> String.split(",")
      |> Enum.map(&String.to_integer/1)
      |> then(&List.to_tuple/1)
    end)
  end

  # Here follows an implementation of the union-find data structure.
  defp union_find_init(points) do
    points
    |> Enum.map(&{&1, {&1, 1}})
    |> Map.new
  end

  defp add_pair(forest, {a, b}) do
    pa = find(forest, a)
    pb = find(forest, b)
    if pa === pb do
      {false, forest}
    else
      union(forest, pa, pb)
    end
  end

  defp find(forest, p) do
    case forest do
      %{^p => {^p, _}} ->
        p
      %{^p => {parent, _}} ->
        find(forest, parent)
    end
  end

  defp union(forest, a, b) do
    {_, size_a} = Map.get(forest, a)
    {_, size_b} = Map.get(forest, b)
    size = size_a + size_b

    forest = if size_a > size_b do
      Map.put(forest, b, {a, size_b})
      |> Map.put(a, {a, size})
    else
      Map.put(forest, a, {b, size_a})
      |> Map.put(b, {b, size})
    end

    done? = size === map_size(forest)
    {done?, forest}
  end
end

Post #1

lkuty

#!/usr/bin/env elixir

# Advent of Code 2025. Day 8

defmodule M do
  def distance({x1,y1,z1},{x2,y2,z2}) do
    :math.sqrt((x2-x1)**2+(y2-y1)**2+(z2-z1)**2)
  end

  def find_with_index(lst, fun), do: find_with_index(lst, fun, 0)
  defp find_with_index([], _fun, _idx), do: {nil, nil}
  defp find_with_index([x | lst], fun, idx) do
    if fun.(x), do: {x, idx}, else: find_with_index(lst, fun, idx+1)
  end

  def add(lst, x), do: [x | lst]

  def delete_two(lst, idx1, idx2), do: delete_two(lst, idx1, idx2, 0)
  defp delete_two([], _idx1, _idx2, _idx), do: []
  defp delete_two(lst, idx1, idx2, idx) when idx > idx1 and idx > idx2, do: lst
  defp delete_two([_x | lst], idx1, idx2, idx) when idx == idx1 or idx == idx2, do: delete_two(lst, idx1, idx2, idx+1)
  defp delete_two([x | lst], idx1, idx2, idx), do: [x | delete_two(lst, idx1, idx2, idx+1)]

  def display_answer_for_part1(circuits) do
    circuits
    |> Enum.map(&MapSet.size/1)
    |> Enum.sort(:desc)
    |> Enum.take(3)
    |> Enum.product()
    |> IO.inspect(label: "Day 8. Part 1")
  end
end

n_pairs = 1000

points = File.read!("../day08.txt")
|> String.trim_trailing()
|> String.split("\n")
|> Enum.map(fn line -> [x,y,z] = String.split(line, ",") |> Enum.map(&String.to_integer/1) ; {x,y,z} end)

points
|> then(fn lst -> for p1 <- lst, p2 <- lst, p1 < p2, do: {p1,p2,M.distance(p1,p2)} end)
|> Enum.sort_by(fn {_p1, _p2, distance} -> distance end)
|> Enum.with_index(1)
|> Enum.reduce({[], nil}, fn {{p1, p2, _distance}, idx}, {circuits, last_connection_between_circuits} ->
  if idx == n_pairs+1, do: M.display_answer_for_part1(circuits)

  {circuit1, circuit_idx1} = M.find_with_index(circuits, fn circuit -> MapSet.member?(circuit, p1) end)
  {circuit2, circuit_idx2} = M.find_with_index(circuits, fn circuit -> MapSet.member?(circuit, p2) end)

  cond do
    circuit_idx1 == nil && circuit_idx2 == nil ->
      {[MapSet.new([p1,p2]) | circuits], last_connection_between_circuits}
    circuit_idx1 == nil ->
      {List.update_at(circuits, circuit_idx2, fn circuit -> MapSet.put(circuit, p1) end), {p1,p2}}
    circuit_idx2 == nil ->
      {List.update_at(circuits, circuit_idx1, fn circuit -> MapSet.put(circuit, p2) end), {p1,p2}}
    circuit_idx1 == circuit_idx2 ->
      {circuits, last_connection_between_circuits}
    true ->
      {circuits |> M.delete_two(circuit_idx1, circuit_idx2) |> M.add(MapSet.union(circuit1, circuit2)), {p1,p2}}
  end
end)
|> tap(fn {_circuits, {{x1,_,_},{x2,_,_}}} -> IO.puts("Day 8. Part 2: #{x1*x2}") end)

Post #2

hauleth

Parse

boxes =
  puzzle_input
  |> String.split()
  |> Enum.map(fn raw ->
    raw
    |> String.split(",")
    |> Enum.map(&String.to_integer/1)
    |> List.to_tuple()
  end)
  |> Enum.sort()

Setup

defmodule JunctionBoxes do
  def all_pairs([]), do: []

  def all_pairs([x | rest]) do
    for(y <- rest, do: {x, y}) ++ all_pairs(rest)
  end

  def dist2({ax, ay, az}, {bx, by, bz}) do
    dx = ax - bx
    dy = ay - by
    dz = az - bz

    dx ** 2 + dy ** 2 + dz ** 2
  end

  def group([], {a, b}), do: [MapSet.new([a, b])]
  def group([set | rest], {a, b}) do
    cond do
      a in set and b in set -> [set | rest]
      a in set or b in set -> set |> MapSet.put(a) |> MapSet.put(b) |> do_squash(rest, {a, b}, [])
      true -> [set | group(rest, {a, b})]
    end
  end

  defp do_squash(curr, [], _, acc), do: [curr | acc]
  defp do_squash(curr, [x | rest], {a, b}, acc) do
    if a in x or b in x do
      [MapSet.union(curr, x) | rest ++ acc]
    else
      do_squash(curr, rest, {a, b}, [x | acc])
    end
  end
end

sorted_pairs =
  JunctionBoxes.all_pairs(boxes)
  |> Enum.sort_by(fn {a, b} -> JunctionBoxes.dist2(a, b) end)

Part 1

sorted_pairs
|> Enum.take(1000)
|> Enum.reduce([], &JunctionBoxes.group(&2, &1))
|> Enum.map(&MapSet.size/1)
|> Enum.sort(:desc)
|> Enum.take(3)
|> Enum.product()

Part 2

box_count = length(boxes)

{a, b} =
  sorted_pairs
  |> Enum.reduce_while([], fn pair, acc ->
    new_acc = JunctionBoxes.group(acc, pair)

    if MapSet.size(hd(new_acc)) == box_count do
      {:halt, pair}
    else
      {:cont, new_acc}
    end
  end)

{ax, _, _} = a
{bx, _, _} = b

ax * bx

Not the most performant implementation (each part runs in about 3s on my machine), but it is good enough. It probably could use some clever algorithms, but I didn’t want to spend too much time on it.

EDIT: I have improved squashing of sets to make it run in 30ms each (sans creating and sorting list of pairs).

Post #3

Aetherus

My code is almost the same as yours, except one difference: I added an ID (generated with make_ref()) to each MapSet.t() so that I don’t have to compare two whole sets, instead I just compare their ID.

defmodule AoC2025.Day08 do
  def part1(points) do
    distances = calc_distances(points, [])

    initial_acc = Map.new(points, fn point ->
      {
        point,  # key = {x, y, z}
        {make_ref(), MapSet.new([point])}  # value = {set_id, set}
      }
    end)

    {distances, initial_acc}
    |> Stream.iterate(fn {[{_, p1, p2} | distances], acc} ->
      {id1, set1} = acc[p1]
      {id2, set2} = acc[p2]
      
      if id1 == id2 do
        {distances, acc}
      else
        {_, merged_set} = union = {id1, MapSet.union(set1, set2)}
        {distances, Enum.reduce(merged_set, acc, fn p, acc ->
          Map.put(acc, p, union)
        end)}
      end
    end)
    |> Enum.at(1000)
    |> elem(1)
    |> Map.values()
    |> Enum.uniq_by(&elem(&1, 0))
    |> Enum.map(&elem(&1, 1))
    |> Enum.map(&MapSet.size/1)
    |> Enum.sort(:desc)
    |> Enum.take(3)
    |> Enum.product()
  end

  def part2(points) do
    distances = calc_distances(points, [])

    initial_acc = Map.new(points, fn point ->
      {
        point,  # key = {x, y, z}
        {make_ref(), MapSet.new([point])}  # value = {set_id, set}
      }
    end)

    {distances, initial_acc, nil, nil}
    |> Stream.iterate(fn {[{_, p1, p2} | distances], acc, x1, x2} ->
      {id1, set1} = acc[p1]
      {id2, set2} = acc[p2]
      
      if id1 == id2 do
        {distances, acc, x1, x2}
      else
        {_, merged_set} = union = {id1, MapSet.union(set1, set2)}
        {distances, Enum.reduce(merged_set, acc, fn p, acc ->
          Map.put(acc, p, union)
          end), elem(p1, 0), elem(p2, 0)}
      end
    end)
    |> Enum.find(fn {_, acc, _, _} ->
      acc
      |> Map.values()
      |> Enum.map(&elem(&1, 0))
      |> Enum.uniq()
      |> length()
      |> Kernel.==(1)
    end)
    |> then(fn {_, _, x1, x2} ->
      x1 * x2
    end)
  end


  defp calc_distances([], acc) do
    Enum.sort(acc)
  end

  defp calc_distances([{x1, y1, z1} = p1 | t], acc) do
    acc =
      for {x2, y2, z2} = p2 <- t, reduce: acc do
        acc ->
          distance = (x1 - x2)**2 + (y1 - y2)**2 + (z1 - z2)**2
          [{distance, p1, p2} | acc]
      end

    calc_distances(t, acc)
  end
end

Post #4

lud

My solution takes 680ms, which is slow, I compute all distances upfront like many of you

I think I could optimize by keeping a double index position=>group and group=>positions to speed up the circuit merging, but I’m too lazy today

defmodule AdventOfCode.Solutions.Y25.Day08 do
  alias AoC.Input

  def parse(input, _part) do
    input
    |> Input.stream!(trim: true)
    |> Enum.map(&parse_line/1)
  end

  defp parse_line(line) do
    [x, y, z] = String.split(line, ",")

    {
      String.to_integer(x),
      String.to_integer(y),
      String.to_integer(z)
    }
  end

  def part_one(xyzs, n_pairs \\ 1000) do
    circuits = Map.new(Enum.with_index(xyzs), fn {xyz, circ} -> {circ, [xyz]} end)

    xyzs
    |> all_distances()
    |> Enum.take(n_pairs)
    |> Enum.reduce(circuits, fn {{a, b}, _}, circuits -> merge_circuits(circuits, a, b) end)
    |> Enum.map(fn {_, list} -> length(list) end)
    |> Enum.sort(:desc)
    |> Enum.take(3)
    |> Enum.product()
  end

  def part_two(xyzs, _ \\ nil) do
    circuits = Map.new(Enum.with_index(xyzs), fn {xyz, circ} -> {circ, [xyz]} end)

    xyzs
    |> all_distances()
    |> Enum.reduce_while(circuits, fn {{a, b}, _}, circuits ->
      circuits = merge_circuits(circuits, a, b)

      if single_circuit?(circuits),
        do: {:halt, x(a) * x(b)},
        else: {:cont, circuits}
    end)
  end

  defp all_distances(xyzs) do
    all_distances = for a <- xyzs, b <- xyzs, a < b, do: {{a, b}, distance(a, b)}
    Enum.sort(all_distances, fn {_, dist_a}, {_, dist_b} -> dist_a <= dist_b end)
  end

  defp merge_circuits(circuits, xyz_a, xyz_b) do
    {circ_a, group_a} = Enum.find(circuits, fn {_, items} -> xyz_a in items end)

    case Enum.find(circuits, fn {_, items} -> xyz_b in items end) do
      {^circ_a, _} ->
        circuits

      {circ_b, group_b} ->
        circuits
        |> Map.put(circ_b, group_a ++ group_b)
        |> Map.delete(circ_a)
    end
  end

  defp distance({xa, ya, za}, {xb, yb, zb}) do
    :math.sqrt(
      :math.pow(xb - xa, 2) +
        :math.pow(yb - ya, 2) +
        :math.pow(zb - za, 2)
    )
  end

  defp single_circuit?(map) do
    case Enum.uniq(Map.values(map)) do
      [_, _ | _] -> false
      [_] -> true
    end
  end

  defp x({x, _, _}), do: x
end

Post #5

hauleth

If you copy set instead of constructing it 2 separately, then == will be as fast for maps as it is for refs. So in this case:

a = MapSet.new([…])
b = a

a == b

Will be immediate.

Post #6

Aetherus

Is it also O(1) when comparing a and b using == when a != b?

Post #7

hauleth

AFAIK - no, but I think that in most cases it will be negligible. I would need to check how exactly map equality is implemented.

Post #8

rvnash

Fun!

Did the following:

Pre-computed distances^2 between all pairs and sorted that list (like most people) (no need to take sqrt)
Data structure for circuits is map of {unique_ids, MapSet of coordinates}
Look up coordinate pairs and either merge circuits or make no change. Each lookup is O(N), where N is number of circuits, can’t think how to improve this.
I also wonder about the if Enum.count(circuits) == 1 do statement. I don’t need the count, just need to know if it is 1 or not. Is there a faster way to see if an Enum has 1 element?

Processing time is about 250ms for part1 and part2.

defmodule RAoc.Solutions.Y25.Day08 do
  alias AoC.Input

  def parse(input, _part) do
    Input.read!(input)
    |> String.split("\n", trim: true)
    |> Enum.map(fn str ->
      [x, y, z] = String.split(str, ",")
      {String.to_integer(x), String.to_integer(y), String.to_integer(z)}
    end)
    |> MapSet.new()
  end

  def part_one(problem) do
    circuits = get_starting_circuits(problem)
    distances = get_sorted_distances(problem)
    # Run 10 iterations for sample problem, 1000 on full data set
    n = (Enum.count(problem) > 20 && 1000) || 10

    run_n_circuits(distances, circuits, n)
    |> Enum.sort_by(fn ms -> MapSet.size(ms) end, :desc)
    |> Enum.take(3)
    |> Enum.product_by(&MapSet.size/1)
  end

  def part_two(problem) do
    circuits = get_starting_circuits(problem)
    distances = get_sorted_distances(problem)

    {{x1, _, _}, {x2, _, _}} =
      last_two_after_run_til_one_circuit(distances, circuits)

    x1 * x2
  end

  defp run_n_circuits(distances, circuits, n) do
    Enum.reduce(1..n, {distances, circuits}, fn _,
                                                {[{_, coord1, coord2} | distances], circuits} ->
      {distances, add_to_circuits(circuits, coord1, coord2)}
    end)
    |> elem(1)
    |> Enum.map(fn {_id, ms} -> ms end)
  end

  defp last_two_after_run_til_one_circuit(distances, circuits) do
    Enum.reduce_while(distances, circuits, fn {_, coord1, coord2}, circuits ->
      circuits = add_to_circuits(circuits, coord1, coord2)

      if Enum.count(circuits) == 1 do
        {:halt, {coord1, coord2}}
      else
        {:cont, circuits}
      end
    end)
  end

  defp add_to_circuits(circuits, coord1, coord2) do
    c1 = circuit_containing(circuits, coord1)
    c2 = circuit_containing(circuits, coord2)

    case {c1, c2} do
      {c, c} ->
        # Already in same circuit
        circuits

      {c1, c2} ->
        # Combine seperate circuits
        circuits
        |> Map.delete(c1)
        |> Map.update!(c2, fn ms2 -> MapSet.union(Map.get(circuits, c1), ms2) end)
    end
  end

  defp circuit_containing(circuits, coord) do
    case Enum.find(circuits, fn {_, ms} ->
           MapSet.member?(ms, coord)
         end) do
      nil -> nil
      value -> elem(value, 0)
    end
  end

  defp get_sorted_distances(coords) do
    Enum.reduce(coords, {coords, []}, fn coord1, {others, distances} ->
      others = MapSet.delete(others, coord1)

      {others,
       [
         Enum.map(others, fn coord2 ->
           {dist_sq(coord1, coord2), coord1, coord2}
         end)
         | distances
       ]}
    end)
    |> elem(1)
    |> List.flatten()
    |> Enum.sort()
  end

  defp get_starting_circuits(coords) do
    # Circuits are {unique_id, MapSet}
    Enum.reduce(coords, %{}, fn coord, acc ->
      Map.put(acc, System.unique_integer([:positive, :monotonic]), MapSet.new([coord]))
    end)
  end

  defp dist_sq({x1, y1, z1}, {x2, y2, z2}) do
    xd = abs(x1 - x2)
    yd = abs(y1 - y2)
    zd = abs(z1 - z2)
    xd * xd + yd * yd + zd * zd
  end
end

Post #9

sevenseacat

Author of Ash Framework

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

My initial implementation was really silly - find the closest pair each time, and then update a list of MapSets - before I was like ohhhhhh this is a graph problem isn’t it?

So I precomputed all of the distances between each pair of junction boxes, started mucking around with graphs - looking at my solution now I think I over-optimized it and it works by chance (just because all nodes are connected to something, doesn’t mean they’re all in one big circuit…) but hey I’ll take it!

(The previous version I had is probably more accurate - on each join, checking if length(Graph.components(graph)) == 1)

Post #10

Load more posts