Cargo.toml

[package]
name = "aoc25_11"
version = "0.1.0"
edition = "2024"

[dependencies]
lasso = "0.7.3"

main.rs

// Cargo.toml:
// [dependencies]
// lasso = "0.7.3"

use std::collections::{HashMap, HashSet};
use lasso::{Rodeo, Spur};

#[cfg(debug_assertions)]
use lasso::Key;


/// Errors.
#[derive(Debug)]
enum ParseError {
	MissingColon,
	EmptyKey,
	EmptyValueList,
}


/// From an input line like `key: a b c`, return a reference so a string slice
/// (smart pointer) of the string `key` and an iterator of string slices for
/// strings `a`, `b`, `c`.
/// Here we are _NOT_ allocating anything into the heap, we're just dealing with
/// string slices (smart pointers).
fn parse_line(row: &str) -> Result<(&str, impl Iterator<Item = &str>), ParseError> {
	// split_once returns None if there is no ':'
	let (key, rest) = row
			.split_once(':')
			.ok_or(ParseError::MissingColon)?;
	let key = key.trim();
	if key.is_empty() {
		return Err(ParseError::EmptyKey);
	}

	// Trim the part after ':' but don't require whitespace.
	let rest = rest.trim();
	if rest.is_empty() {
		// If empty list is not allowed
		return Err(ParseError::EmptyValueList);
		// If empty list *is* allowed, remove this check.
	}

	// No allocation: this is an iterator of &str.
	let iter = rest.split_whitespace();
	Ok((key, iter))
}


/// Main global state.
struct Mapper {
	outputs: HashMap<Spur, HashSet<Spur>>,
	interner: Rodeo,
	id_out: Spur,
	id_you: Spur,
}


impl Mapper {
	/// Create a new global state.
	fn new() -> Self {
		let mut interner = Rodeo::new();
		// Let's insert the known strings into the interner, and save their IDs.
		let id_out = interner.get_or_intern("out");
		let id_you = interner.get_or_intern("you");
		Mapper {
			outputs: HashMap::<Spur, HashSet<Spur>>::new(),
			interner,
			id_out,
			id_you
		}
	}


	/// Read line from input, and map each key with their associated output pin.
	/// If the input is `key: a b c`, here we're mapping with hashtables and sets
	/// `key` -> [`a`, `b`, `c`], and we're saving the state.
	fn ingest_line<S: AsRef<str>>(&mut self, row: S) {
		// Parse line.
		match parse_line(row.as_ref()) {
			Ok((key, iter)) => {
				// Create the set to hold all the output pins mapped from the key.
				let mut outputs = HashSet::<Spur>::new();
				// Insert the current key into the string interner OR get the ID.
				let key_id = self.interner.get_or_intern(key);

				// DEBUG , REMOVE!
				#[cfg(debug_assertions)]
				println!("ADD_KEY `{}`[{}]", key, key_id.into_usize());

				for i in iter {
					// Insert the output into the string interner OR get the ID.
					let output_id = self.interner.get_or_intern(i);
					// Insert the ID into the set of outputs.
					// Here we avoid duplicates, like `hello: abc xyz abc`, we'll have
					// only *one* `abc` inserted
					outputs.insert(output_id);

					// DEBUG, REMOVE!
					#[cfg(debug_assertions)]
					println!("   ADD_VAL `{}`[{}]", i, output_id.into_usize());
				}

				// Now map the device key ID to each outputs' IDs.
				// Basically with input `miao: bau arf` we're mapping miao -> [bau, arf].
				self.outputs.insert(key_id, outputs);
			},
			Err(_) => println!("Invalid line, dude! Calling 911 in progress ..."),
		}
	}


	/// Recursively count all the paths from the 'you' pin to the 'out' one.
	fn count(&self) -> u64 {
		let mut count = 0;
		// Create a stack of output pins.
		let mut stack = Vec::<Spur>::with_capacity(256);

		// Lets start with the 'you' pin: let's push it into the stack.
		stack.push(self.id_you);

		loop {
			// Pop a pin from the stack.
			match stack.pop() {
				Some(pin) => { 

					// DEBUG! REMOVE!
					#[cfg(debug_assertions)]
					println!("POP Current pin: `{}`[{}]", self.interner.resolve(&pin),
						pin.into_usize());

					// If we got the 'out' pin, increase the total counter, and do nothing.
					if pin == self.id_out {
						count += 1;
					} else {

						// If we got any other pin, lets check if it is a key to our mapper.
						if let Some(new_pins) = self.outputs.get(&pin) {
							// For each new pin mapped to the previous pin, push them into the
							// stack.
							for new_pin in new_pins {
								stack.push(*new_pin);

								// DEBUG! REMOVE!
								#[cfg(debug_assertions)]
								println!("   PUSH New pin: `{}`[{}]",
									self.interner.resolve(&new_pin), new_pin.into_usize());
							}
						}
					}
				},
				// Stack is empty? We're done, dude!
				None => break,
			}
		}
		// Return t3h l33t counter.
		count
	}
}


fn main() {
	#[cfg(debug_assertions)]
	println!("sizeof(Spur)=={}", std::mem::size_of::<Spur>());

	let mut mapper = Mapper::new();
	mapper.ingest_line("aaa: you hhh");
	mapper.ingest_line("you: bbb ccc");
	mapper.ingest_line("bbb: ddd eee");
	mapper.ingest_line("ccc: ddd eee fff");
	mapper.ingest_line("ddd: ggg");
	mapper.ingest_line("eee: out");
	mapper.ingest_line("fff: out");
	mapper.ingest_line("ggg: out");
	mapper.ingest_line("hhh: ccc fff iii");
	mapper.ingest_line("iii: out");

	println!("Count is: {}", mapper.count());
}