Day 11: Reactor

var outputs: Hash[String, List[String]] = []
for line in File.read_to_string("inputs/day_11.txt").split("\n"): {
    var parts = line.split(": ")
    outputs[parts[0]] = parts[1].split(" ")
}

var cached_paths: Hash[String, Integer] = []
define paths_between(start: String, end: String): Integer {
    if start == end: {
        return 1
    }

    if start == "out": {
        return 0
    }

    var key = start ++ end

    with cached_paths.get(key) as Some(paths): {
        return paths
    }

    var paths = 0
    for output in outputs[start]: {
        paths += paths_between(output, end)
    }

    cached_paths[key] = paths
    return paths
}

print("Part 1: {}".format(paths_between("you", "out")))

var queue = ["svr"]
var first_midpoint = ""

do: {
    var device = queue.shift()

    if device == "dac": {
        first_midpoint = "dac"
        break
    }

    if device == "fft": {
        first_midpoint = "fft"
        break
    }

    for output in outputs[device]: {
        queue.push(output)
    }
} while queue

var second_midpoint = (first_midpoint == "dac" ? "fft" : "dac")

print("Part 2: {}".format(
    paths_between("svr", first_midpoint)
    * paths_between(first_midpoint, second_midpoint)
    * paths_between(second_midpoint, "out")
))

use aoc_2025::timed_run;
use std::collections::HashMap;
use std::collections::HashSet;
use std::io;
use std::vec::Vec;

struct Input {
  graph: HashMap<String, Vec<String>>,
}

impl Input {
  fn read_from_stdin() -> Input {
    Input {
      graph: io::stdin()
        .lines()
        .map(|l| {
          let tmp = l.unwrap();
          let (key, values) = tmp.split_once(": ").unwrap();
          (
            key.to_string(),
            values.split(' ').map(|s| s.to_string()).collect(),
          )
        })
        .chain([("out".to_string(), vec![])])
        .collect(),
    }
  }
}

fn lexicographical_order_from<T: Clone + Eq + std::hash::Hash, F: FnMut(&T)>(
  graph: &HashMap<T, Vec<T>>,
  start: T,
  mut f: F,
) {
  // First pass to compute the number of parents for each node reachable from the starting point.
  let mut num_parents = HashMap::<T, u64>::new();
  let mut visited = HashSet::<T>::new();
  let mut st = vec![start.clone()];
  while !st.is_empty() {
    let cur = st.pop().unwrap();
    if !visited.insert(cur.clone()) {
      continue;
    }
    for child in &graph[&cur] {
      *num_parents.entry(child.clone()).or_insert(0) += 1;
      st.push(child.clone());
    }
  }
  // Second pass for the actual lexicographical order. Only visiting a node once we visited all its
  // parents.
  st.push(start);
  while !st.is_empty() {
    let cur = st.pop().unwrap();
    f(&cur);
    for child in &graph[&cur] {
      let np = num_parents.get_mut(child).unwrap();
      *np -= 1;
      if *np == 0 {
        st.push(child.clone());
      }
    }
  }
}

fn part1(input: &Input) -> u64 {
  let mut num_paths_to = HashMap::<String, u64>::new();
  let start = "you".to_string();
  num_paths_to.insert(start.clone(), 1);
  lexicographical_order_from(&input.graph, start, |n| {
    let num_to_n = num_paths_to[n];
    for child in &input.graph[n] {
      *num_paths_to.entry(child.clone()).or_insert(0) += num_to_n;
    }
  });
  num_paths_to["out"]
}

#[derive(Clone)]
struct PathData {
  none: u64,
  dac: u64,
  fft: u64,
  both: u64,
}

fn part2(input: &Input) -> u64 {
  let mut num_paths_to = HashMap::<String, PathData>::new();
  let start = "svr".to_string();
  num_paths_to.insert(
    start.clone(),
    PathData {
      none: 1,
      dac: 0,
      fft: 0,
      both: 0,
    },
  );
  lexicographical_order_from(&input.graph, start, |n| {
    let num_to_n = num_paths_to[n].clone();
    for child in &input.graph[n] {
      let cnum = num_paths_to.entry(child.clone()).or_insert(PathData {
        none: 0,
        dac: 0,
        fft: 0,
        both: 0,
      });
      match n.as_str() {
        "fft" => {
          cnum.fft += num_to_n.none;
          cnum.both += num_to_n.dac;
        }
        "dac" => {
          cnum.dac += num_to_n.none;
          cnum.both += num_to_n.fft;
        }
        _ => {
          cnum.none += num_to_n.none;
          cnum.dac += num_to_n.dac;
          cnum.fft += num_to_n.fft;
          cnum.both += num_to_n.both;
        }
      }
    }
  });
  num_paths_to["out"].both
}

fn main() {
  let input = Input::read_from_stdin();
  timed_run("Part 1", || part1(&input));
  timed_run("Part 2", || part2(&input));
}

def parse_input(lines: list[str]) -> dict[str, list[str]]:
  deviceIO = {}
  for line in lines:
    input, output = map(str.strip, line.split(':'))
    deviceIO[input] = output.split()
  return deviceIO

def count_paths(deviceIO: dict[str, list[str]], node: str, end: str, memo: set[str]) -> int:
  if node in memo:
    return memo[node]
  paths = 0
  for n in deviceIO[node]:
    if n == end:
      return 1
    paths += count_paths(deviceIO, n, end, memo)
  memo[node] = paths
  return paths

def part_one(deviceIO: dict[str, list[str]]) -> int:
  return count_paths(deviceIO, 'you', 'out', {})

def part_two(deviceIO: dict[str, list[str]]) -> int:
  deviceIO['out'] = []
  return (
          count_paths(deviceIO, 'svr', 'fft', {})
          * count_paths(deviceIO, 'fft', 'dac', {})
          * count_paths(deviceIO, 'dac', 'out', {})
  )

def main() -> None:
  with open('11.in') as file:
    lines = [line.rstrip() for line in file]

  input = parse_input(lines)
  print('Part 1:', part_one(input))
  print('Part 2:', part_two(input))

if __name__ == '__main__':
  main()