Advent of Code 2025 - Day 11

hauleth

Graph traversals

Parse

graph =
  puzzle_input
  |> String.split("\n", trim: true)
  |> Map.new(fn <<from::binary-3>> <> ": " <> rest ->
    {from, String.split(rest)}
  end)

Implementation

defmodule Servers do
  def paths(graph, from, to), do: paths(graph, from, to, [from])

  defp paths(_graph, to, to, acc), do: [Enum.reverse(acc)]

  defp paths(graph, from, to, acc) do
    if next = graph[from] do
      Stream.flat_map(next, &paths(graph, &1, to, [&1 | acc]))
    else
      []
    end
  end

  def paths_through(graph, from, to, required),
    do: path_through(graph, from, to, MapSet.new(required), %{})

  defp path_through(_graph, to, to, required, memo),
    do: {if(Enum.empty?(required), do: 1, else: 0), memo}

  defp path_through(graph, from, to, required, memo) do
    state = MapSet.delete(required, from)

    with :error <- Map.fetch(memo, {from, state}),
         {:ok, next} <- Map.fetch(graph, from) do
      {sum, memo} =
      Enum.reduce(next, {0, memo}, fn n, {sum, acc} ->
        {c, next_acc} = path_through(graph, n, to, state, acc)

        {c + sum, next_acc}
      end)

      {sum, Map.put(memo, {from, state}, sum)}
    else
      :error -> {0, memo}
      {:ok, val} -> {val, memo}
    end
  end
end

Part 1

Servers.paths(graph, "you", "out") |> Enum.count()

Part 2

Servers.paths_through(graph, "svr", "out", ["dac", "fft"])
|> elem(0)

6 comments

#advent-of-code #2025

1 796 6

2025-12-14 07:05:14 UTC

Showing Posts 1 to 6

Show Best Posts
Show All (oldest first)
Show All (newest first)

lud

A similar solution but I divided the work in multiple steps:

count(svr -> fft) * count(fft -> dac) * count(dac -> out)

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

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

  defp parse_line(line) do
    <<inp::binary-size(3), ": ", rest::binary>> = line
    {inp, String.split(rest)}
  end

  def part_one(full_io) do
    count_paths(full_io, "you", "out")
  end

  defp count_paths(full_io, start, finish) do
    counts = count_paths_loop(full_io, start, finish, Map.put(%{"out" => 0}, finish, 1))
    Map.fetch!(counts, start)
  end

  defp count_paths_loop(full_io, current, finish, acc) do
    exits = Map.fetch!(full_io, current)

    acc =
      Enum.reduce(exits, acc, fn exit_, acc ->
        if Map.has_key?(acc, exit_) do
          acc
        else
          count_paths_loop(full_io, exit_, finish, acc)
        end
      end)

    value = Enum.sum_by(exits, &Map.fetch!(acc, &1))

    Map.put(acc, current, value)
  end

  def part_two(full_io) do
    {step1, step2} =
      if count_paths(full_io, "fft", "dac") > 0 do
        {"fft", "dac"}
      else
        true = count_paths(full_io, "dac", "fft") > 0
        {"dac", "fft"}
      end

    count_paths(full_io, "svr", step1) *
      count_paths(full_io, step1, step2) *
      count_paths(full_io, step2, "out")
  end
end

Edit: simplified the parse, taking inspiration from hauleth’s

Post #1

antoine-duchenet

The quickest day for me until now, which is surprising for day 11/12:

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

  defp part1(input) do
    input
    |> parse_input()
    |> count("you", "out")
  end

  defp part2(input) do
    map = parse_input(input)

    dac_fft = count(map, "svr", "dac") * count(map, "dac", "fft") * count(map, "fft", "out")
    fft_dac = count(map, "svr", "fft") * count(map, "fft", "dac") * count(map, "dac", "out")

    dac_fft + fft_dac
  end

  defp count(_, to, to), do: 1

  defp count(map, from, to) do
    Performance.memoize({from, to}, fn ->
      map
      |> Map.get(from, [])
      |> Enum.map(&count(map, &1, to))
      |> Enum.sum()
    end)
  end

  defp parse_input(input) do
    input
    |> Enum.map(&parse_line/1)
    |> Map.new()
  end

  defp parse_line(<<from::bytes-size(3), ": ", to::binary>>), do: {from, Utils.splitrim(to, " ")}
end

Pretty similar to the solutions above, except that I use my Performance.memoize helper instead of the usual cache/memo Map. I takes ~5ms to run on my machine for part 2.

Post #2

sevenseacat

Author of Ash Framework

Sad to think it’ll be over tomorrow Guess I’ll have to amuse myself in the rest of December by revisiting old puzzles I never solved!

Part 1 was super straightforward - this is a directed graph, and the two nodes are pretty close together.

For part 2, the nodes are not close together, they’re at opposite ends of the graph

So I used a similar BFS approach to the puzzle with counting the timelines in the beam splitter (day 7) though this code ended up being a lot nicer! I split it into three parts - svr to fft, fft to dac, and then dac to out, multiplying the numbers together at the end.

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

Name                     ips        average  deviation         median         99th %
day 11, part 1        321.81        3.11 ms     ±5.50%        3.05 ms        3.57 ms
day 11, part 2        176.86        5.65 ms     ±3.21%        5.61 ms        6.12 ms

Post #3

newton-peixoto

Pretty much copy and paste my solution from day 07

https://github.com/newton-peixoto/advent-of-code/blob/main/2025/livebooks/day-11.livemd

Post #4

bjorng

Erlang Core Team

defmodule Day11 do
  def part1(input) do
    map = parse(input)
    count_paths(map, "you")
  end

  defp count_paths(_map, "out"), do: 1
  defp count_paths(map, label) do
    Enum.reduce(Map.get(map, label), 0, fn label, count ->
      count + count_paths(map, label)
    end)
  end

  def part2(input) do
    map = parse(input)
    count_paths_part2(map, "svr", 0, MapSet.new())
    |> elem(0)
  end

  defp count_paths_part2(_map, "out", flags, memo) do
    n = if seen_both?(flags), do: 1, else: 0
    {n, memo}
  end
  defp count_paths_part2(map, label, seen, memo) do
    seen = update_seen(seen, label)
    key = {label, seen}
    case memo do
      %{^key => n} ->
        {n, memo}
      %{} ->
        Enum.reduce(Map.get(map, label), {0, memo}, fn label, {count, memo} ->
          {new_count, memo} = count_paths_part2(map, label, seen, memo)
          {count + new_count, memo}
        end)
        |> then(fn {count, memo} ->
          {count, Map.put(memo, key, count)}
        end)
    end
  end

  defp update_seen(seen, "fft"), do: Bitwise.bor(seen, 1)
  defp update_seen(seen, "dac"), do: Bitwise.bor(seen, 2)
  defp update_seen(seen, _), do: seen

  defp seen_both?(flags), do: flags === 3

  defp parse(input) do
    input
    |> Enum.map(fn line ->
      [label | outs] = String.split(line, [": ", " "])
      {label, outs}
    end)
    |> Map.new
  end
end

Post #5

lkuty

#!/usr/bin/env elixir

# Advent of Code 2025. Day 11

Mix.install([
  {:memoize, "~> 1.4.4"},
])

defmodule M do
  def paths_1(map), do: paths_1(map, ["you"])
  defp paths_1(map, froms) do
    tos = Enum.reduce(froms, [], fn
      "out", tos -> ["out" | tos]
      from, tos -> map[from] ++ tos
    end)
    if Enum.all?(tos, & &1 == "out"), do: tos, else: paths_1(map, tos)
  end

  #########################################################
  # Start of extra code to display paths

  def tab(depth, display_first \\ false)
  def tab(_depth, true), do: ""
  def tab(depth, false), do: String.duplicate("          ", depth)

  def seen(seen_dac, seen_fft), do: "#{if seen_dac, do: "!", else: "."}#{if seen_fft, do: "!", else: "."}"

  def display_paths_2(map), do: display_paths_2(map, "svr", false, false, true, 0)
  def display_paths_2(_map, "out", true, true, display_first, display_depth) do
    IO.puts "#{tab(display_depth, display_first)} out !"
  end
  def display_paths_2(_map, "out", _, _, display_first, display_depth) do
    IO.puts "#{tab(display_depth, display_first)} out"
  end
  def display_paths_2(map, "dac" = from, seen_dac, seen_fft, display_first, display_depth) do
    IO.write "#{tab(display_depth, display_first)} #{from}#{seen(seen_dac, seen_fft)} -> "
    [fst | rest] = map[from]
    display_paths_2(map, fst, true, seen_fft, true, display_depth+1)
    Enum.each(rest, fn to ->
      display_paths_2(map, to, true, seen_fft, false, display_depth+1)
    end)
  end
  def display_paths_2(map, "fft" = from, seen_dac, seen_fft, display_first, display_depth) do
    IO.write "#{tab(display_depth, display_first)} #{from}#{seen(seen_dac, seen_fft)} -> "
    [fst | rest] = map[from]
    display_paths_2(map, fst, seen_dac, true, true, display_depth+1)
    Enum.each(rest, fn to ->
      display_paths_2(map, to, seen_dac, true, false, display_depth+1)
    end)
  end
  def display_paths_2(map, from, seen_dac, seen_fft, display_first, display_depth) do
    IO.write "#{tab(display_depth, display_first)} #{from}#{seen(seen_dac, seen_fft)} -> "
    [fst | rest] = map[from]
    display_paths_2(map, fst, seen_dac, seen_fft, true, display_depth+1)
    Enum.each(rest, fn to ->
      display_paths_2(map, to, seen_dac, seen_fft, false, display_depth+1)
    end)
  end

  # End of extra code to display paths
  #########################################################

  # Memoization using the memoize library
  def paths_2(map), do: paths_2(map, "svr", false, false)

  defp paths_2(_map, "out", true, true), do: 1
  defp paths_2(_map, "out", _seen_dac, _seen_fft), do: 0
  defp paths_2(map, from, seen_dac, seen_fft) do
    seen_dac = (if from == "dac", do: true, else: seen_dac)
    seen_fft = (if from == "fft", do: true, else: seen_fft)
    Memoize.Cache.get_or_run({__MODULE__, :paths, [from, seen_dac, seen_fft]}, fn ->
      Enum.reduce(map[from], 0, fn to, total ->
        val = paths_2(map, to, seen_dac, seen_fft)
        total+val
      end)
    end)
  end

  # Memoization without a library
  def paths_3(map) do
    {_memo, total} = paths_3(map, "svr", false, false, %{})
    total
  end

  defp paths_3(_map, "out", true, true, memo), do: {memo, 1}
  defp paths_3(_map, "out", _seen_dac, _seen_fft, memo), do: {memo, 0}
  defp paths_3(map, from, seen_dac, seen_fft, memo) do
    seen_dac = (if from == "dac", do: true, else: seen_dac)
    seen_fft = (if from == "fft", do: true, else: seen_fft)
    case Map.get(memo, [from, seen_dac, seen_fft]) do
      nil ->
        {memo, total} = Enum.reduce(map[from], {memo, 0}, fn to, {memo, total} ->
          {memo, val} = paths_3(map, to, seen_dac, seen_fft, memo)
          {Map.put(memo, [from, seen_dac, seen_fft], total+val), total+val}
        end)
        {Map.put(memo, [from, seen_dac, seen_fft], total), total}
      total -> {memo, total}
    end
  end
end

map = File.read!("../day11.txt")
|> String.trim_trailing()
|> String.split("\n")
|> Enum.reduce(%{}, fn line, map ->
  {d, ds} = String.split(line, ": ") |> then(fn [d, ds] -> {d, String.split(ds)} end)
  Map.put(map, d, ds)
end)

M.paths_1(map) |> length() |> IO.inspect(label: "Day 11. Part 1")

# M.display_paths_2(map) # useful with test data
M.paths_2(map) |> IO.inspect(label: "Day 11. Part 2")
M.paths_3(map) |> IO.inspect(label: "Day 11. Part 2")

Post #6

— All posts loaded —