1  #![feature(test)]
 2  
 3  use rustc_hash::FxHashMap;
 4  
 5  type Input<'a> = Vec<Node<'a>>;
 6  
 7  struct Node<'a> {
 8      size: u64,
 9      parent_id: Option<usize>,
10      names: FxHashMap<&'a str, usize>,
11      visited: bool,
12  }
13  
14  impl Node<'_> {
15      fn new(parent_id: Option<usize>) -> Self {
16          Self {
17              size: 0,
18              parent_id,
19              names: FxHashMap::default(),
20              visited: false,
21          }
22      }
23  }
24  
25  fn setup(input: &str) -> Input {
26      let mut nodes = vec![Node::new(None)];
27      let mut pwd = 0;
28      let mut visiting = None;
29      for line in input.trim().lines() {
30          let mut split = line.split(' ');
31          match (split.next(), split.next(), split.next()) {
32              (Some("$"), Some("cd"), Some(dir)) => {
33                  if dir == "/" {
34                      pwd = 0;
35                  } else if dir == ".." {
36                      pwd = nodes[pwd].parent_id.unwrap_or(0)
37                  } else {
38                      pwd = match nodes[pwd].names.get(dir) {
39                          Some(id) => *id,
40                          None => {
41                              let id = nodes.len();
42                              nodes.push(Node::new(Some(pwd)));
43                              nodes[pwd].names.insert(dir, id);
44                              id
45                          }
46                      }
47                  }
48              }
49              (Some(size), Some(_), None) => {
50                  if let Ok(size) = size.parse::<u64>() {
51                      if nodes[pwd].visited {
52                          continue;
53                      }
54                      visiting = Some(pwd);
55                      nodes[pwd].size += size;
56                  }
57              }
58              _ => {
59                  if let Some(v) = visiting {
60                      nodes[v].visited = true;
61                      visiting = None;
62                  }
63              }
64          }
65      }
66      for i in (1..nodes.len()).rev() {
67          if let Node {
68              size,
69              parent_id: Some(parent_id),
70              ..
71          } = nodes[i]
72          {
73              nodes[parent_id].size += size;
74          }
75      }
76      nodes
77  }
78  
79  fn part1(nodes: &Input) -> u64 {
80      nodes
81          .iter()
82          .map(|node| node.size)
83          .filter(|x| *x <= 100000)
84          .sum()
85  }
86  
87  fn part2(nodes: &Input) -> u64 {
88      let free = 70000000 - nodes[0].size;
89      nodes
90          .iter()
91          .map(|node| node.size)
92          .filter(|x| *x >= 30000000 - free)
93          .min()
94          .unwrap()
95  }
96  
97  aoc::main!(2022, 7, ex: 1);