{"header":{"message":"Ancient edits for 2021 day 12","description":null,"timestamp":"2023-05-01T21:14:14.236361291Z","authors":[{}]},"hash":"B5AQD4U2QCQGHWMJMU2DSDWLHRBEMHFXKKIAEYLN4B5HB2I5FFHAC","authors":[{"login":"quickdudley","key":"5B8LBcp1Xe7XYwo2o8k8whShcE6RkhkJA4PjbgBQDwKK"}],"deps":{"hashes":[["B5AQD4U2QCQGHWMJMU2DSDWLHRBEMHFXKKIAEYLN4B5HB2I5FFHAC","Ancient edits for 2021 day 12"],["AA",null],["ZJJQGKN5MXLZLGF7GTID446PR6XQ2LSOP3BKD5OECUFI2FX4G4RAC","Add comment"],["NULMDMUUK5JASG23MB2EIYNUF665YLOBSRDNE2TCXY5OAO4SFNUQC","some functions for 2021 day 12"]],"deps":["ZJJQGKN5MXLZLGF7GTID446PR6XQ2LSOP3BKD5OECUFI2FX4G4RAC"],"known":["NULMDMUUK5JASG23MB2EIYNUF665YLOBSRDNE2TCXY5OAO4SFNUQC"]},"hunks":[{"Edit":{"inode":{"change":3,"pos":33},"path":"2021/day12.rs","line":1,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":33},"to":{"change":2,"start":0,"end":211},"introduced_by":2},{"previous":"","flag":"DELETED","from":{"change":2,"pos":211},"to":{"change":3,"start":34,"end":65},"introduced_by":2},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":33},"to":{"change":3,"start":34,"end":65},"introduced_by":3}],"inode":{"change":3,"pos":33}}},"contents":[{"Del":"// I plan to use an unusual approach to this problem: it is not based on\n// graph traversals but on transformations of directed graphs under which\n// the number of paths bettween the start and end is invariant.\n"},{"Del":"#![feature(hash_drain_filter)]\n"}]}},{"Edit":{"inode":{"change":3,"pos":33},"path":"2021/day12.rs","line":2,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":96}],"down_context":[{"change":3,"pos":96}],"flag":"BLOCK","start":0,"end":64,"inode":{"change":3,"pos":33}}},"contents":[{"Add":"use std::collections::BTreeSet;"},{"Add":"use std::collections::VecDeque;"}]}},{"Replacement":{"inode":{"change":3,"pos":33},"path":"2021/day12.rs","line":10,"ins":{"up_context":[{"change":3,"pos":249}],"down_context":[{"change":3,"pos":299}],"flag":"BLOCK","start":65,"end":111,"inode":{"change":3,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":249},"to":{"change":3,"start":249,"end":299},"introduced_by":3}],"inode":{"change":3,"pos":33}},"ins_contents":[{"Add":" let graph = build_graph(&mut parse_edges("}],"del_contents":[{"Del":" let mut graph = build_graph(&mut parse_edges(\n"}]}},{"Replacement":{"inode":{"change":3,"pos":33},"path":"2021/day12.rs","line":17,"ins":{"up_context":[{"change":3,"pos":463}],"down_context":[{"change":3,"pos":491}],"flag":"BLOCK","start":112,"end":1124,"inode":{"change":3,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":463},"to":{"change":3,"start":463,"end":491},"introduced_by":3}],"inode":{"change":3,"pos":33}},"ins_contents":[{"Add":" println!(\"{} paths\", count_paths(&graph));"},{"Add":"}"},{"Add":""},{"Add":"fn count_paths(graph: &HashMap>) -> u128 {"},{"Add":" let mut q: VecDeque<(usize, BTreeSet)> = once((0, BTreeSet::new())).collect();"},{"Add":" let mut r: HashMap, u128>> = once((0, once((BTreeSet::new(), 1)).collect())).collect();"},{"Add":" while let Some((n, p)) = q.pop_front() {"},{"Add":" match (r.get(&n).and_then(|s| s.get(&p)), graph.get(&n)) {"},{"Add":" (Some(c), Some(e)) => {"},{"Add":" let c = *c;"},{"Add":" let mut next_p = p.clone();"},{"Add":" next_p.insert(n);"},{"Add":" for (t, w) in e.iter().filter(|(t,_)| !p.contains(t)) {"},{"Add":" let d = c * *w;"},{"Add":" r.entry(*t).or_insert_with(|| HashMap::new()).entry(next_p.clone()).and_modify(|g| *g += d).or_insert(d);"},{"Add":" q.push_back((*t, next_p.clone()));"},{"Add":" }"},{"Add":" }"},{"Add":" _ => {}"},{"Add":" }"},{"Add":" }"},{"Add":" r.get(&1).map(|z| z.iter().map(|(_,n)| *n).sum()).unwrap_or(0)"}],"del_contents":[{"Del":" trim_graph(&mut graph);\n"}]}},{"Edit":{"inode":{"change":3,"pos":33},"path":"2021/day12.rs","line":59,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":969},"to":{"change":3,"start":969,"end":2117},"introduced_by":3}],"inode":{"change":3,"pos":33}}},"contents":[{"Del":"fn trim_graph(graph: &mut HashMap>) -> bool {\n use std::collections::HashSet;\n let mut ever_changed = false;\n loop {\n let mut changed = false;\n let reachable: HashSet<_> = graph\n .values()\n .flat_map(|e| e.keys())\n .copied()\n .chain(once(0))\n .collect();\n let reached: HashSet<_> = graph.keys().copied().collect();\n graph\n .drain_filter(|s, e| {\n e.drain_filter(|t, n| {\n if *n == 0 || !reached.contains(t) {\n changed = true;\n true\n } else {\n false\n }\n })\n .for_each(drop);\n if *s > 1 && (!reachable.contains(s) || e.is_empty()) {\n changed = true;\n true\n } else {\n false\n }\n })\n .for_each(drop);\n if changed {\n ever_changed = true;\n } else {\n break;\n }\n }\n ever_changed\n}\n\n"}]}}],"owner":"quickdudley","repo":"adventofcode","token":"MCuitqqiFUGpxCJFlx3WrtwFFCOVe+zOQeIBnbes0uY=","login":null}

…

Dependencies

Change contents