main.rs (5175B)
1 use std::collections::VecDeque;
2
3 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
4 enum Pos {
5 Left,
6 Right,
7 }
8
9 impl Pos {
10 fn calc_mult(pos_stack: &VecDeque<Pos>) -> u64 {
11 pos_stack
12 .iter()
13 .map(|p| match p {
14 Self::Left => 3,
15 Self::Right => 2,
16 })
17 .product()
18 }
19 }
20
21 #[derive(Debug, Clone, Copy)]
22 struct Snailfish {
23 value: u32,
24 depth: i32,
25 pos: Pos,
26 }
27
28 impl Snailfish {
29 fn parse(s: &str) -> Vec<Snailfish> {
30 let mut res = Vec::new();
31 let mut prev_char = None;
32 let mut curr_depth = 0;
33 for c in s.chars() {
34 match (prev_char, c.to_digit(10)) {
35 (Some('['), Some(v)) => res.push(Snailfish {
36 value: v,
37 depth: curr_depth,
38 pos: Pos::Left,
39 }),
40 (Some(','), Some(v)) => res.push(Snailfish {
41 value: v,
42 depth: curr_depth,
43 pos: Pos::Right,
44 }),
45 (_, None) => match c {
46 '[' => curr_depth += 1,
47 ']' => curr_depth -= 1,
48 _ => (),
49 },
50 _ => (),
51 }
52 prev_char = Some(c);
53 }
54 res
55 }
56
57 fn sum(a: &Vec<Snailfish>, b: &Vec<Snailfish>) -> Vec<Snailfish> {
58 let mut sum = a
59 .iter()
60 .chain(b.iter())
61 .map(|&v| v)
62 .collect::<Vec<Snailfish>>();
63 for v in sum.iter_mut() {
64 v.depth += 1;
65 }
66 Self::reduce(sum)
67 }
68
69 fn reduce(mut val: Vec<Snailfish>) -> Vec<Snailfish> {
70 loop {
71 let mut new_val = Vec::<Snailfish>::new();
72 let mut reduced = false;
73 // explode
74 let mut carry = 0;
75 for mut v in val.into_iter() {
76 if !reduced && v.pos == Pos::Right && v.depth > 4 {
77 reduced = true;
78 let left = new_val.pop().unwrap();
79 let mut pair_pos = Pos::Left;
80 if let Some(last) = new_val.last_mut() {
81 last.value += left.value;
82 if last.pos == Pos::Left && v.depth - 1 == last.depth {
83 pair_pos = Pos::Right;
84 }
85 }
86 new_val.push(Snailfish {
87 value: 0,
88 depth: v.depth - 1,
89 pos: pair_pos,
90 });
91 carry = v.value;
92 } else {
93 v.value += carry;
94 carry = 0;
95 new_val.push(v);
96 }
97 }
98 val = new_val;
99 if reduced {
100 continue;
101 }
102 // split
103 // need to be a separate loop as first rule only triggers on Right elem
104 let mut new_val = Vec::<Snailfish>::new();
105 for v in val.into_iter() {
106 if !reduced && v.value >= 10 {
107 reduced = true;
108 new_val.push(Snailfish {
109 value: v.value / 2,
110 depth: v.depth + 1,
111 pos: Pos::Left,
112 });
113 new_val.push(Snailfish {
114 value: (v.value + 1) / 2,
115 depth: v.depth + 1,
116 pos: Pos::Right,
117 });
118 } else {
119 new_val.push(v);
120 }
121 }
122 val = new_val;
123 if !reduced {
124 break;
125 }
126 }
127 val
128 }
129
130 fn magnitude(val: &Vec<Snailfish>) -> u64 {
131 let mut res = 0;
132 let mut pos = std::collections::VecDeque::<Pos>::new();
133 for v in val {
134 while pos.len() < v.depth as usize {
135 pos.push_back(Pos::Left);
136 }
137 *pos.back_mut().unwrap() = v.pos;
138 res += v.value as u64 * Pos::calc_mult(&pos);
139 while let Some(&Pos::Right) = pos.back() {
140 pos.pop_back();
141 }
142 if let Some(back) = pos.back_mut() {
143 *back = Pos::Right;
144 }
145 }
146 res
147 }
148 }
149
150 fn main() {
151 let input = std::fs::read_to_string("input.txt")
152 .unwrap()
153 .trim()
154 .split('\n')
155 .map(|s| Snailfish::parse(s))
156 .collect::<Vec<Vec<_>>>();
157 // 4207
158 println!("Part 1: {}", part_1(&input));
159 // 4635
160 println!("Part 2: {}", part_2(&input));
161 }
162
163 fn part_1(input: &Vec<Vec<Snailfish>>) -> u64 {
164 let sum = input
165 .clone()
166 .into_iter()
167 .reduce(|a, b| Snailfish::sum(&a, &b))
168 .unwrap();
169 Snailfish::magnitude(&sum)
170 }
171
172 fn part_2(input: &Vec<Vec<Snailfish>>) -> u64 {
173 let mut max_magnitude = 0;
174 for a in input.iter() {
175 for b in input.iter() {
176 max_magnitude = max_magnitude.max(Snailfish::magnitude(&Snailfish::sum(a, b)));
177 }
178 }
179
180 max_magnitude
181 }