Go

Yeeeaaay graphs! This one has been a pleasure to program and here comes my solution, with pruning of irrelevant branches (cursed nodes) and memoïzation for better performance.

package main

import (
	"aoc/utils"
	"fmt"
	"slices"
	"strings"
)

type graph map[string][]string

func graphFromInput(input chan string) graph {
	g := graph{}
	for line := range input {
		firstSplit := strings.Split(line, ":")
		currentNode := firstSplit[0]
		followers := strings.Fields(firstSplit[1])
		g[currentNode] = followers
	}
	return g
}

var memo = make(map[string]map[string]int)

func (g *graph) dfsUntil(currentNode, targetNode string, cursedNodes map[string]any) int {
	subMemo, ok := memo[currentNode]
	if !ok {
		memo[currentNode] = make(map[string]int)
	} else {
		sum, ok := subMemo[targetNode]
		if ok {
			return sum
		}
	}

	followers, _ := (*g)[currentNode]
	sum := 0
	for _, follower := range followers {
		if follower == targetNode {
			memo[currentNode][targetNode] = 1
			return 1
		} else if _, ok := cursedNodes[follower]; ok {
			continue
		}
		sum += g.dfsUntil(follower, targetNode, cursedNodes)
	}

	memo[currentNode][targetNode] = sum
	return sum
}

func stepOne(input chan string) (int, error) {
	g := graphFromInput(input)
	return g.dfsUntil("you", "out", make(map[string]any)), nil
}

func (g *graph) dfsFromSvrToOut(
	currentNode string, hasDac, hasFft bool, cursedNodes map[string]any) int {

	if currentNode == "dac" && hasFft {
		return g.dfsUntil("dac", "out", cursedNodes)
	}

	hasDac = hasDac || currentNode == "dac"
	hasFft = hasFft || currentNode == "fft"

	followers := (*g)[currentNode]
	sum := 0
	for _, follower := range followers {
		switch follower {
		case "out":
			if hasDac && hasFft {
				return 1
			} else {
				return 0
			}
		default:
			sum += g.dfsFromSvrToOut(follower, hasDac, hasFft, cursedNodes)
		}
	}
	return sum
}

func (g *graph) getCursedNodes() map[string]any {
	cursedNodes := make(map[string]any)

	for node := range *g {
		if node == "dac" || node == "fft" || node == "svr" {
			continue
		}

		fftToNode := g.dfsUntil("fft", node, cursedNodes)
		dacToNode := g.dfsUntil("dac", node, cursedNodes)
		nodeToFft := g.dfsUntil(node, "fft", cursedNodes)
		nodeToDac := g.dfsUntil(node, "dac", cursedNodes)

		if dacToNode > 0 {
			continue
		}

		if fftToNode > 0 && nodeToDac > 0 {
			continue
		}

		if nodeToFft == 0 {
			cursedNodes[node] = nil
		}
	}

	return cursedNodes
}

func stepTwo(input chan string) (int, error) {
	g := graphFromInput(input)
	cursedNodes := g.getCursedNodes()
	for cursedKey := range cursedNodes {
		delete(g, cursedKey)
		for gkey := range g {
			g[gkey] = slices.DeleteFunc(g[gkey], func(n string) bool {
				return n == cursedKey
			})
		}
	}
	memo = make(map[string]map[string]int)
	sum := g.dfsUntil("svr", "out", nil)
	return sum, nil
}

func main() {
	input, err := utils.DownloadTodaysInputFile()
	if err != nil {
		_ = fmt.Errorf("%v\n", err)
	}

	utils.RunStep(utils.ONE, input, stepOne)
	utils.RunStep(utils.TWO, input, stepTwo)
}

I have also finally written a function to automatically download the input file (which will prove useful for… ehm… tomorrow):

func DownloadTodaysInputFile() (FilePath, error) {
	today := time.Now().Day()
	url := fmt.Sprintf("https://adventofcode.com/2025/day/%d/input", today)

	client := &http.Client{}
	req, err := http.NewRequest("GET", url, nil)
	if err != nil {
		return FilePath(""), err
	}

	// const sessionValue = 'hehehehehehe'
	req.Header.Set("Cookie", fmt.Sprintf("session=%s", sessionValue))
	resp, err := client.Do(req)
	if err != nil {
		return FilePath(""), err
	}

	data, err := io.ReadAll(resp.Body)
	if err != nil {
		return FilePath(""), err
	}

	path := fmt.Sprintf("day%d.txt", today)
	f, err := os.Create(path)
	if err != nil {
		return FilePath(""), err
	}
	defer f.Close()

	_, err = f.Write(data)
	if err != nil {
		return FilePath(""), err
	}

	return FilePath(path), nil
}

Rust

Part 1 was very straight forward. I overcomplicated it a bit by using an actual graph library, but I’m used to using it.

I originally tried to brute force Part 2, which of course failed. I then reverted to dynamic programming, which worked well.

use std::collections::{HashMap, VecDeque};

use graphrs::{Graph, GraphSpecs};

use crate::solver::DaySolver;

pub struct Day11Solver;

impl DaySolver for Day11Solver {
    fn part1(&self, input: String) -> String {
        let mut graph: Graph<String, ()> = Graph::new(GraphSpecs::directed_create_missing());
        let edges = input.lines()
            .flat_map(|line| {
                let (start, end_str) = line.split_once(": ").unwrap();
                end_str.split_whitespace()
                    .map(|end| (start.to_string(), end.to_string()))
            })
            .collect();
        graph.add_edge_tuples(edges).unwrap();

        let mut frontier = VecDeque::from([vec!["you".to_string()]]);

        let mut path_count = 0;

        while let Some(path) = frontier.pop_front() {
            let last = path.last().unwrap();

            if last == "out" {
                path_count += 1;
            } else {
                graph
                    .get_successor_node_names(last.to_string())
                    .unwrap()
                    .into_iter()
                    .filter(|next| !path.contains(next))
                    .map(|next| {
                        let mut new_path = path.clone();
                        new_path.push(next.clone());
                        new_path
                    })
                    .for_each(|new_path| frontier.push_back(new_path));
            }
        }

        path_count.to_string()
    }

    fn part2(&self, input: String) -> String {
        let mut graph: Graph<String, ()> = Graph::new(GraphSpecs::directed_create_missing());
        let edges = input.lines()
            .flat_map(|line| {
                let (start, end_str) = line.split_once(": ").unwrap();
                end_str.split_whitespace()
                    .map(|end| (start.to_string(), end.to_string()))
            })
            .collect();
        graph.add_edge_tuples(edges).unwrap();

        how_many_paths(
            &mut HashMap::new(),
            &graph,
            ("svr".to_string(), false, false),
        )
            .to_string()

    }
}

fn how_many_paths(
    cache: &mut HashMap<(String, bool, bool), usize>,
    graph: &Graph<String, ()>,
    current: (String, bool, bool),
) -> usize {
    if let Some(&c) = cache.get(&current) {
        c
    } else {
        let (node, has_dac, has_fft) = &current;
        if node == "out" {
            let count = if *has_dac && *has_fft { 1 } else { 0 };
            cache.insert(current, count);
            count
        } else {
            let count = graph
                .get_successor_node_names(node.clone())
                .unwrap()
                .into_iter()
                .map(|next| {
                    let next_state = (next.to_string(), *has_dac || next == "dac", *has_fft || next == "fft");
                    how_many_paths(cache, graph, next_state)
                })
                .sum();
            cache.insert(current, count);
            count
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part1() {
        let input = include_str!("../../inputs/test/11");

        let solver = Day11Solver {};
        assert_eq!("5", solver.part1(input.to_string()));
    }

    #[test]
    fn part2() {
        let input = include_str!("../../inputs/test/11-2");

        let solver = Day11Solver {};
        assert_eq!("2", solver.part2(input.to_string()));
    }
}

nushell

I’m still travelling, so another phone attempt. Jet lag says sleep, so just part 1 for now:

def part1 [filename: string] {
  mut input = open $filename | lines |
    each { parse '{index}: {children}' | update children { split row " " } | first } |
    insert paths { null }
  print $"Data loaded, ($input | length) devices"

  $input = explore-path $input you
  $input | where index == you | get 0.paths
}

def explore-path [devices, start: string] {
  print $"Exploring ($start)"
  let dev = $devices | where index == $start | first
  if ($dev | get paths) != null {
    print "Already explored"
    return $devices
  }

  # Shadow with mutable version
  mut devices = $devices
  mut paths = 0
  let is_out = $dev | get children | where ($it == out) | is-not-empty
  if $is_out {
    print $"Found an out device: ($start)"
    $paths = 1
  } else {
    for child in ($dev | get children ) {
      $devices = explore-path $devices $child
      $paths += $devices | where index == $child | get 0.paths
    }
  }

  # Shadow with immutable... wtf
  let paths = $paths
  print $"Setting paths for ($start) to ($paths)"
  $devices = $devices | update paths { |row| if $row.index == $start {  
$paths } else {} }
   $devices
}

Haskell

import Control.Arrow
import Data.Char
import Text.ParserCombinators.ReadP

import Data.Array qualified as A
import Data.Map.Strict qualified as M

parse = M.fromList . fst . last . readP_to_S (((,) <$> (munch1 isAlpha <* string ": ") <*> (munch1 isAlpha `sepBy` char ' ')) `endBy` char '\n')

out = 0 :: Int -- index of out node

buildAdjList m = (keys, adj)
  where
    keys = M.insert "out" out . snd . M.mapAccumWithKey (\a k _ -> (succ a, a)) (succ out) $ m
    adj = A.listArray (out, out + M.size m) $ [] : (fmap (keys M.!) <$> M.elems m)

findPaths adj src dest = go src
  where
    go i
      | i == dest = 1 :: Int
      | otherwise = sum $ (r A.!) <$> (adj A.! i)

    r = A.listArray bounds $ go <$> A.range bounds
    bounds = A.bounds adj

part1 (keys, adj) = findPaths adj (keys M.! "you") out

-- Since graph must be acyclic, one of fft_dac or dac_fft will be 0
part2 (keys, adj)
  | fft_dac /= 0 = svr_fft * fft_dac * dac_out
  | otherwise = svr_dac * dac_fft * fft_out
    where
      [svr, fft, dac] = (keys M.!) <$> ["svr", "fft", "dac"]
      svr_fft = findPaths adj svr fft
      fft_dac = findPaths adj fft dac
      dac_out = findPaths adj dac out

      svr_dac = findPaths adj svr dac
      dac_fft = findPaths adj dac fft
      fft_out = findPaths adj fft out

main = getContents >>= print . (part1 &&& part2) . buildAdjList . parse

The graph in my input (and I assume everyone else’s too) is DAG so one can use transfer matrices for the first part (after severing connections going out of “out”) and the second one topological sorting and just count paths between each node separately and multiply them. First part could be done much easily using the machinery of part2 but I wanted to use my favourite object transfer matrices for the solution. Second part runs in about 0.09 seconds.

from pathlib import Path

import networkx as nx
import numpy as np

cwd = Path(__file__).parent.resolve()


def parse_input(file_path):
  with file_path.open("r") as fp:
    data = list(map(str.strip, fp.readlines()))

  nodes = [y for line in data for y in line.replace(':','').split(' ')]
  M = np.zeros((len(nodes), len(nodes)))

  for line in data:
    from_node = line.split(':')[0]
    to_nodes = line.split(': ')[-1].split(' ')
    I0 = nodes.index(from_node)
    I1 = [nodes.index(n) for n in to_nodes]
    M[I0, I1] = 1

  return M, nodes


def count_paths_between(ind0, ind1, M):
  '''
  counts paths by severing any outgoing connection from node ind1
  and using transfer matrices. Stopping condition is having the
  same positive number of paths for 10 cycles.
  '''

  vec = np.zeros((M.shape[0]))
  vec[ind0] = 1
  nhistory = []
  A = M.T.copy()
  A[:, ind1] = 0
  A[ind1, ind1] = 1
  counter = 0

  while True:
    vec = A@vec
    nhistory.append(vec[ind1])
    counter +=1

    if len(nhistory)>10 and (len(set(nhistory[-10:]))==1 and  nhistory[-1]!=0):
      return nhistory[-1]


def count_paths_dag(G, source, target):

  npaths = {node: 0 for node in G.nodes()}
  npaths[source] = 1

  for node in nx.topological_sort(G):
    for nbr in G.successors(node):
      npaths[nbr] += npaths[node]

  return npaths[target]


def solve_problem1(file_name, path_nodes=None):

  M, nodes = parse_input(Path(cwd, file_name))

  if path_nodes is None:
    npaths = count_paths_between(nodes.index("you"), nodes.index("out"), M)

  else:
    G = nx.from_numpy_array(M, create_using=nx.DiGraph(),
                            nodelist=nodes)

    # assumed G is a DAG, below will raise error if not
    sorted_nodes = list(nx.topological_sort(G))

    sorted_path_nodes = sorted(path_nodes, key=sorted_nodes.index)

    #make sure path nodes are not topoligically equivalent
    for node1, node2 in zip(sorted_path_nodes[:-1], sorted_path_nodes[1:]):
      assert nx.has_path(G, node1, node2)

    npaths = np.prod([count_paths_dag(G, node1, node2) for node1, node2 in
                      zip(sorted_path_nodes[:-1], sorted_path_nodes[1:])])

  return npaths

if __name__ == "__main__":

  assert solve_problem1("test_input1") == 5
  assert solve_problem1("input") == 431

  assert solve_problem1("test_input2", ["svr","dac","fft","out"]) == 2
  assert solve_problem1("input",  ["svr","dac","fft","out"]) == 358458157650450

Kotlin

This was substantially easier than yesterday’s problem. Especially considering I still haven’t done Part 2 from yesterday.

Anyway, here is my Part 2 solution for today. Given how quickly Part 1 ran without a cache, I didn’t think Part 2 would be much different, until my computer fans spun up and stayed there for over a minute. So I added a cache and re-ran it and it ran in 31ms.

const val end = "out"
var map: Map<String, List<String>>? = null
val problemVertices = "dac" to "fft"
val cache: MutableMap<Pair<String, Pair<Boolean, Boolean>>, Long> = mutableMapOf()

fun main() {
    val input = getInput(11)
    map = parseInput1(input)
    val total = countPaths2("svr", false to false).first
    println(total)
}

fun countPaths2(vertex: String, problemVerticesEncountered: Pair<Boolean, Boolean>): Pair<Long, Pair<Boolean, Boolean>> {
    val otherVertices = map!![vertex]!!
    var total = 0L
    val nextProblemVerticesEncountered =
        (problemVerticesEncountered.first || vertex == problemVertices.first) to (problemVerticesEncountered.second || vertex == problemVertices.second)
    for (otherVertex in otherVertices) {
        val key = otherVertex to nextProblemVerticesEncountered
        if (cache.contains(key)) {
            total += cache[key]!!
        } else if (otherVertex == end) {
            if (nextProblemVerticesEncountered.first && nextProblemVerticesEncountered.second) {
                total++
            }
        } else {
            total += countPaths2(otherVertex, nextProblemVerticesEncountered).first
        }
    }
    cache[vertex to nextProblemVerticesEncountered] = total
    return total to nextProblemVerticesEncountered
}


fun parseInput1(input: String): Map<String, List<String>> = input.lines()
    .filter { it.isNotBlank() }
    .associate {
        val split = it.split(": ")
        split[0] to split[1].split(" ").toList()
    }

Python

Part 1 can be done with simple dfs / backtracking, even without memoization.

Part 2 needed to have dp / memoization to finish in a reasonable time. Initially, I also checked for cycles in the path, but I removed the check once I realized there were none. Also, instead of adding booleans / int to my memoization function, I chose to compute both path arrangements (svr -> fft -> dac -> out AND svr -> dac -> fft -> out) and add them up.

from collections import defaultdict

# build the adjacency graph from the input data
def build_graph(data: str):
    rules_data = data.splitlines()
    graph = defaultdict(list)
    for rule_data in rules_data:
        from_node, to_nodes = rule_data.split(": ")
        graph[from_node].extend(to_nodes.split(' '))
    return graph

# simply dfs every path from 'you' until we reach 'out'
# this is what I initially used for part 1
def count_paths_dfs(data: str, start = "you", end = "out"):
    graph = build_graph(data)

    paths_to_end = 0
    stack = [start]     # currently active paths
    while stack:
        node = stack.pop()
        if node == end:
            # we reached end, no need to check further
            paths_to_end += 1
            continue
        # every node connected to current node is a potential path
        stack.extend(graph[node])
    
    return paths_to_end

# memoized version of counting paths from start to end
def count_paths_memo(graph: defaultdict[list], start = "you", end = "out"):
    # I used to have some code to check for cycles, but thankfully it wasn't needed

    # its pretty much same logic as count_paths_dfs, except recursive and with memoization
    memo = {}
    def backtrack(curr: str):
        if curr in memo:
            return memo[curr]        
        if curr == end:
            ans = 1
        else:
            ans = sum(backtrack(conn) for conn in graph[curr])
        memo[curr] = ans
        return ans
    
    return backtrack(start)

# Optimized part 1 using memoization (not necessary, but faster)
def part1_with_memoiz(data: str, start = "you", end = "out"):
    graph = build_graph(data)
    return count_paths_memo(graph, start, end)

# Part 2 requires counting paths from "svr" to "out", 
#   including only those paths that go through both "fft" and "dac"
# Instead of adding booleans / int to my memoization function, 
#   I chose to compute all path arrangements and add them up
def part2(data: str):
    graph = build_graph(data)

    # getting from start to one requirement
    svr_to_fft = count_paths_memo(graph, "svr", "fft")
    svr_to_dac = count_paths_memo(graph, "svr", "dac")
    # getting from one requirement to the other
    fft_to_dac = count_paths_memo(graph, "fft", "dac")
    dac_to_fft = count_paths_memo(graph, "dac", "fft")
    # the final push to out
    fft_to_out = count_paths_memo(graph, "fft", "out")
    dac_to_out = count_paths_memo(graph, "dac", "out")

    # total paths = (start -> fft -> dac -> out) + (start -> dac -> fft -> out)
    svr_to_out = (
        svr_to_dac * dac_to_fft * fft_to_out +
        svr_to_fft * fft_to_dac * dac_to_out
    )
    return svr_to_out

sample_p1 = """aaa: you hhh
you: bbb ccc
bbb: ddd eee
ccc: ddd eee fff
ddd: ggg
eee: out
fff: out
ggg: out
hhh: ccc fff iii
iii: out"""
assert (t := count_paths_dfs(sample_p1)) == 5, f"Expected 5, got {t}"
assert (t := part1_with_memoiz(sample_p1)) == 5, f"Expected 5, got {t}"

sample_p2 = """svr: aaa bbb
aaa: fft
fft: ccc
bbb: tty
tty: ccc
ccc: ddd eee
ddd: hub
hub: fff
eee: dac
dac: fff
fff: ggg hhh
ggg: out
hhh: out"""
assert (t := part2(sample_p2)) == 2, f"Expected 2, got {t}"

Uiua

If it’s stupid but it works…

link (You’ll need to up the execution limit)

# AOC2025day11 - mazes.
# Uncomment for Part 1
D ← "aaa: you hhh\nyou: bbb ccc\nbbb: ddd eee\nccc: ddd eee fff\nddd: ggg\neee: out\nfff: out\nggg: out\nhhh: ccc fff iii\niii: out"
# Uncomment for Part 2
# D ← "svr: aaa bbb\naaa: fft\nfft: ccc\nbbb: tty\ntty: ccc\nccc: ddd eee\nddd: hub\nhub: fff\neee: dac\ndac: fff\nfff: ggg hhh\nggg: out\nhhh: out"
# D      ← &fras "randomAOC/AOC2025day11.txt"
Tabs   ← ⊜(⊙□°⊂⊜∘¬⊸∊": ")⊸≠@\nD
Nexts  ← ⍣(°□⊡˜⨂⊙Tabs|[])
Part₁  ← ⊙◌⧻path(˙≠°⊏Nexts|≍"out")"you"

Part₂ ← (
  ⊙◌⧻path(˙≠°⊏Nexts|≍"fft")"svr"
  ⊙◌⧻path(˙≠°⊏Nexts|≍"dac")"fft"
  ⊙◌⧻path(˙≠°⊏Nexts|≍"out")"dac"
  ××
)
# Only one will be right for the test data, depending on dataset.
⊃Part₁ Part₂

Rust

After the struggles of yesterday, nice to have an easy one. Still havent solved yesterdays pt2, struggling to understand z3 + rust.

Hope everyone else isnt too demoralised by the last 2 days!

   fn count_paths2(
        paths: &HashMap<&str, Vec<&str>>,
        seen: &mut HashMap<String, usize>,
        node: &str,
        dest: &str,
    ) -> usize {
        if let Some(c) = seen.get(node) {
            return *c;
        }
        if node == dest {
            seen.insert(node.to_string(), 1);
            return 1;
        }

        let Some(next) = paths.get(node) else {
            return 0;
        };
        let mut total_paths = 0;
        for node in next {
            total_paths += count_paths2(paths, seen, node, dest)
        }
        seen.insert(node.to_string(), total_paths);
        total_paths
    }

    #[test]
    fn test_y2025_day11_part2() {
        let input = include_str!("../../input/2025/day_11.txt");
        let mut paths: HashMap<&str, Vec<&str>> = HashMap::new();
        input.lines().for_each(|line| {
            let (source, dests) = line.split_once(":").unwrap();
            let dests = dests.split(" ").collect::<Vec<&str>>();
            paths.insert(source, dests);
        });

        // srv -> fft -> dac -> out

        let mut total1 = 1;
        {
            let mut seen = HashMap::new();
            total1 *= count_paths2(&paths, &mut seen, "svr", "fft");
        }
        {
            let mut seen = HashMap::new();
            total1 *= count_paths2(&paths, &mut seen, "fft", "dac");
        }
        {
            let mut seen = HashMap::new();
            total1 *= count_paths2(&paths, &mut seen, "dac", "out");
        }

        // srv -> dac -> fft -> out

        let mut total2 = 1;
        {
            let mut seen = HashMap::new();
            total2 *= count_paths2(&paths, &mut seen, "svr", "dac");
        }
        {
            let mut seen = HashMap::new();
            total2 *= count_paths2(&paths, &mut seen, "dac", "fft");
        }
        {
            let mut seen = HashMap::new();
            total2 *= count_paths2(&paths, &mut seen, "fft", "out");
        }

        println!("total: {}", total1 + total2);
        assert_eq!(total1 + total2, 509312913844956);
    }

Rust

Somehow got the right answer for part 1 iteratively, but it wasn’t actually correct at all, so switched to the standard recursion + memoisation. Gotta love just chucking an iterator into the value type of a HashMap and going BRRRR (1.2 ms).

pub fn day11(input: &str) -> (u64, u64) {
    let array = input.trim().lines();
    let mut conns = HashMap::new();
    for line in array {
        let mut iter = line.split_whitespace();
        conns.insert(&iter.next().unwrap()[0..3], iter);
    }

    fn find_path<'a>(
        start: &'a str,
        end: &'a str,
        conns: &HashMap<&'a str, SplitWhitespace<'a>>,
        devices: &mut HashMap<&'a str, u64>,
    ) -> u64 {
        let mut sum = 0;
        let Some(list) = conns.get(start) else {
            return 0;
        };
        for i in list.clone() {
            if i == end {
                sum += 1;
            } else if let Some(precomp) = devices.get(i) {
                sum += precomp;
            } else {
                sum += find_path(i, end, conns, devices);
            }
        }
        devices.insert(start, sum);
        sum
    }

    let part1 = find_path("you", "out", &conns, &mut HashMap::new());
    // If dac -> fft and fft -> dac are both non-zero, then there are loops. That makes an
    // infinite number of paths so the question posed would be meaningless.
    let dac_to_fft = find_path("dac", "fft", &conns, &mut HashMap::new());
    let part2 = if dac_to_fft == 0 {
        find_path("svr", "fft", &conns, &mut HashMap::new())
            * find_path("fft", "dac", &conns, &mut HashMap::new())
            * find_path("dac", "out", &conns, &mut HashMap::new())
    } else {
        find_path("svr", "dac", &conns, &mut HashMap::new())
            * dac_to_fft
            * find_path("fft", "out", &conns, &mut HashMap::new())
    };
    (part1, part2)
}

C++

Dynamic programming and recursion - it’s the AoC classic. Nothing tricky here, which is a relief after yesterday.

No sign of Dijkstra’s yet, which is a surprise. Maybe it’ll be tomorrow’s puzzle? 25th is usually an open goal if you’ve done the rest of the puzzles, but I don’t know if that applies to the new shorter format.

#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_map.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <vector>

namespace {

using Map =
    boost::unordered::unordered_flat_map<std::string, std::vector<std::string>>;

auto read(const std::string &name) {
  auto rval = Map{};
  auto ih = std::ifstream{name};
  if (!ih)
    throw std::runtime_error{"file?"};
  auto line = std::string{};
  while (std::getline(ih, line)) {
    auto ss = std::istringstream{line};
    auto tmp = std::string{};
    ss >> tmp;
    auto key = tmp.substr(0, tmp.size() - 1);
    auto value = std::vector<std::string>{};
    while (ss >> tmp)
      value.push_back(std::move(tmp));
    rval[key] = std::move(value);
  }
  return rval;
}

auto part1() {
  auto map = read("11.1.txt");
  auto current = std::vector<std::vector<std::string>>{};
  auto paths = boost::unordered::unordered_flat_set<std::vector<std::string>>{};

  current.push_back(std::vector<std::string>{"you"});

  while (!current.empty()) {
    auto next_up = decltype(current){};
    std::swap(current, next_up);
    for (const auto &next : next_up) {
      auto &outputs = map.at(next.back());
      for (auto &output : outputs) {
        if (output == "you")
          continue;
        auto token = next;
        token.push_back(output);
        if (output == "out") {
          paths.insert(std::move(token));
        } else {
          current.push_back(std::move(token));
        }
      }
    }
  }

  return paths.size();
}

struct Route {
  std::string current;
  bool has_fft, has_dac;
};
struct RouteHash {
  std::size_t operator()(const Route &p) const {
    std::size_t seed = 0;
    boost::hash_combine(seed, p.current);
    boost::hash_combine(seed, p.has_fft);
    boost::hash_combine(seed, p.has_dac);
    return seed;
  }
};
auto operator==(const Route &a, const Route &b) {
  return a.current == b.current && a.has_fft == b.has_fft &&
         a.has_dac == b.has_dac;
}
auto cache = boost::unordered::unordered_flat_map<Route, size_t, RouteHash>{};

auto count_target(Route start, const Map &map) -> size_t {
  auto outputs = map.at(start.current);
  if (start.current == "dac")
    start.has_dac = true;
  if (start.current == "fft")
    start.has_fft = true;

  auto rval = size_t{};
  for (auto &output : outputs) {
    if (auto f = cache.find({output, start.has_fft, start.has_dac});
        f != cache.end()) {
      rval += f->second;
      continue;
    }
    if (output == "out") {
      if (start.has_dac && start.has_fft) {
        ++rval;
      }
      continue;
    }
    rval += count_target({output, start.has_fft, start.has_dac}, map);
  }
  cache[start] = rval;
  return rval;
}

auto part2() {
  auto map = read("11.2.txt");
  return count_target({"svr", false, false}, map);
}

} // namespace

auto main() -> int {
  BOOST_LOG_TRIVIAL(info) << "Day 11";
  BOOST_LOG_TRIVIAL(info) << "1: " << part1();
  BOOST_LOG_TRIVIAL(info) << "2: " << part2();
}

Haskell

Oh, this one was easy (dynamic programming at last!). Still haven’t figured out the right way to approach yesterday’s part two, though.

import Data.List  
import Data.Map (Map)  
import Data.Map qualified as Map  

readInput =  
  Map.fromList  
    . map ((\(name : outs) -> (init name, outs)) . words)  
    . lines  

part1 input = go "you"  
  where  
    go "out" = 1  
    go name = maybe 0 (sum . map go) $ input Map.!? name  

part2 input = let (both, _, _, _) = pathsFrom "svr" in both  
  where  
    pathsFrom =  
      (Map.!)  
        . Map.insert "out" (0, 0, 0, 1)  
        . Map.fromList  
        . (zip <*> map findPaths)  
        $ Map.keys input ++ concat (Map.elems input)  
    findPaths n =  
      let (both, dac, fft, none) =  
            unzip4 $ maybe [] (map pathsFrom) (input Map.!? n)  
       in case n of  
            "dac" -> (sum both + sum fft, sum dac + sum none, 0, 0)  
            "fft" -> (sum both + sum dac, 0, sum fft + sum none, 0)  
            _ -> (sum both, sum dac, sum fft, sum none)  

main = do  
  input <- readInput <$> readFile "input11"  
  print $ part1 input  
  print $ part2 input