some functions for 2021 day 12

Dependencies

• [2] E5UDZGDT Solution for 2021 day 9 part 1
• [*] HUHAFQLN 2021 day 1

Change contents

• file addition: day12.rs (----------)
  [4.16]
  + #![feature(hash_drain_filter)]

  + use std::collections::HashMap;

  + use std::iter::once;

  + use std::ops::Deref;

  +

  + fn main() {

  + use std::io::BufRead;

  + let filename = std::env::args().nth(1).expect("Expected filename");

  + let mut graph = build_graph(&mut parse_edges(

  + &mut std::io::BufReader::new(

  + std::fs::File::open(filename.deref()).unwrap(),

  + )

  + .lines()

  + .flat_map(Result::ok),

  + ));

  + trim_graph(&mut graph);

  + }

  +

  + fn parse_edges<I: Iterator<Item = S>, S: Deref<Target = str>>(

  + source: &mut I,

  + ) -> impl Iterator<Item = (String, String)> + '_ {

  + source.filter_map(|l| {

  + let mut s = l

  + .split('-')

  + .map(str::trim)

  + .map(std::borrow::ToOwned::to_owned);

  + let lhs = s.next()?;

  + let rhs = s.next()?;

  + match s.next() {

  + None => Some(()),

  + Some(_) => None,

  + }?;

  + Some((lhs, rhs))

  + })

  + }

  +

  + fn trim_graph(graph: &mut HashMap<usize, HashMap<usize, u128>>) -> bool {

  + use std::collections::HashSet;

  + let mut ever_changed = false;

  + loop {

  + let mut changed = false;

  + let reachable: HashSet<_> = graph

  + .values()

  + .flat_map(|e| e.keys())

  + .copied()

  + .chain(once(0))

  + .collect();

  + let reached: HashSet<_> = graph.keys().copied().collect();

  + graph

  + .drain_filter(|s, e| {

  + e.drain_filter(|t, n| {

  + if *n == 0 || !reached.contains(t) {

  + changed = true;

  + true

  + } else {

  + false

  + }

  + })

  + .for_each(drop);

  + if *s > 1 && (!reachable.contains(s) || e.is_empty()) {

  + changed = true;

  + true

  + } else {

  + false

  + }

  + })

  + .for_each(drop);

  + if changed {

  + ever_changed = true;

  + } else {

  + break;

  + }

  + }

  + ever_changed

  + }

  +

  + fn build_graph<

  + I: Iterator<Item = (S, T)>,

  + S: Deref<Target = str>,

  + T: Deref<Target = str>,

  + >(

  + source: &mut I,

  + ) -> HashMap<usize, HashMap<usize, u128>> {

  + let mut large = HashMap::new();

  + let mut small = HashMap::new();

  + number(&mut small, String::from("start"));

  + number(&mut small, String::from("end"));

  + let mut result = HashMap::new();

  + for (s, t) in source

  + .flat_map(|(s, t)| {

  + let s = s.deref();

  + let t = t.deref();

  + let (l, s, t) = if upper(s) {

  + (true, s, t)

  + } else if upper(t) {

  + (true, t, s)

  + } else {

  + (false, s, t)

  + };

  + if l {

  + let v = large.entry(s.to_owned()).or_insert_with(Vec::new);

  + let t = number(&mut small, t.to_owned());

  + let d = v.clone();

  + v.push(t);

  + Box::new(d.into_iter().map(move |s| (s, t)))

  + as Box<dyn Iterator<Item = (usize, usize)>>

  + } else {

  + let s = number(&mut small, s.to_owned());

  + let t = number(&mut small, t.to_owned());

  + Box::new(once((s, t)))

  + as Box<dyn Iterator<Item = (usize, usize)>>

  + }

  + })

  + .flat_map(|(s, t)| [(s, t), (t, s)])

  + .filter(|(s, t)| *s != 1 && *t != 0)

  + {

  + result

  + .entry(s)

  + .or_insert_with(HashMap::new)

  + .entry(t)

  + .and_modify(|v| *v += 1)

  + .or_insert(1);

  + }

  + result

  + }

  +

  + fn upper(x: &str) -> bool {

  + x.chars().next().map(char::is_uppercase).unwrap_or(false)

  + }

  +

  + fn number<K: Eq + std::hash::Hash>(

  + repo: &mut HashMap<K, usize>,

  + name: K,

  + ) -> usize {

  + let s = repo.len();

  + *repo.entry(name).or_insert(s)

  + }
• edit in 2021/Cargo.toml at line 37
  [2.5329]
  +

  + [[bin]]

  + name = "day12"

  + path = "day12.rs"