Ancient edits for 2021 day 12

quickdudley

May 1, 2023, 9:14 PM

B5AQD4U2QCQGHWMJMU2DSDWLHRBEMHFXKKIAEYLN4B5HB2I5FFHAC

Dependencies

• [2] ZJJQGKN5 Add comment
• [3] NULMDMUU some functions for 2021 day 12

Change contents

• edit in 2021/day12.rs at line 1
  [3.33]→[2.0:211](∅→∅),[2.211]→[3.34:65](∅→∅),[3.33]→[3.34:65](∅→∅)
  − // I plan to use an unusual approach to this problem: it is not based on

  − // graph traversals but on transformations of directed graphs under which

  − // the number of paths bettween the start and end is invariant.

  − #![feature(hash_drain_filter)]
• edit in 2021/day12.rs at line 2
  [3.96]

  [3.96]
  + use std::collections::BTreeSet;

  + use std::collections::VecDeque;
• replacement in 2021/day12.rs at line 10
  [3.249]→[3.249:299](∅→∅)
  − let mut graph = build_graph(&mut parse_edges(
  [3.249]

  [3.299]
  + let graph = build_graph(&mut parse_edges(
• replacement in 2021/day12.rs at line 17
  [3.463]→[3.463:491](∅→∅)
  − trim_graph(&mut graph);
  [3.463]

  [3.491]
  + println!("{} paths", count_paths(&graph));

  + }

  +

  + fn count_paths(graph: &HashMap<usize, HashMap<usize, u128>>) -> u128 {

  + let mut q: VecDeque<(usize, BTreeSet<usize>)> = once((0, BTreeSet::new())).collect();

  + let mut r: HashMap<usize, HashMap<BTreeSet<usize>, u128>> = once((0, once((BTreeSet::new(), 1)).collect())).collect();

  + while let Some((n, p)) = q.pop_front() {

  + match (r.get(&n).and_then(|s| s.get(&p)), graph.get(&n)) {

  + (Some(c), Some(e)) => {

  + let c = *c;

  + let mut next_p = p.clone();

  + next_p.insert(n);

  + for (t, w) in e.iter().filter(|(t,_)| !p.contains(t)) {

  + let d = c * *w;

  + r.entry(*t).or_insert_with(|| HashMap::new()).entry(next_p.clone()).and_modify(|g| *g += d).or_insert(d);

  + q.push_back((*t, next_p.clone()));

  + }

  + }

  + _ => {}

  + }

  + }

  + r.get(&1).map(|z| z.iter().map(|(_,n)| *n).sum()).unwrap_or(0)
• edit in 2021/day12.rs at line 59
  [3.969]→[3.969:2117](∅→∅)
  − 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

  − }

  −