diff options
author | Jesse Luehrs <doy@tozt.net> | 2022-12-11 21:59:21 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2022-12-11 22:16:30 -0500 |
commit | e2d219b331a878bbb3c9dcef9ea4e218b2e3ee06 (patch) | |
tree | 93e418011c45cab8d4070d3d33b377a9364f4a27 /src/bin/2021 | |
parent | 179467096141b7e8f67d63b89fd21e779a564fe6 (diff) | |
download | advent-of-code-e2d219b331a878bbb3c9dcef9ea4e218b2e3ee06.tar.gz advent-of-code-e2d219b331a878bbb3c9dcef9ea4e218b2e3ee06.zip |
refactor
Diffstat (limited to 'src/bin/2021')
-rw-r--r-- | src/bin/2021/day1.rs | 36 | ||||
-rw-r--r-- | src/bin/2021/day10.rs | 109 | ||||
-rw-r--r-- | src/bin/2021/day11.rs | 82 | ||||
-rw-r--r-- | src/bin/2021/day12.rs | 99 | ||||
-rw-r--r-- | src/bin/2021/day13.rs | 144 | ||||
-rw-r--r-- | src/bin/2021/day14.rs | 94 | ||||
-rw-r--r-- | src/bin/2021/day15.rs | 68 | ||||
-rw-r--r-- | src/bin/2021/day16.rs | 210 | ||||
-rw-r--r-- | src/bin/2021/day17.rs | 106 | ||||
-rw-r--r-- | src/bin/2021/day18.rs | 257 | ||||
-rw-r--r-- | src/bin/2021/day19.rs | 293 | ||||
-rw-r--r-- | src/bin/2021/day2.rs | 73 | ||||
-rw-r--r-- | src/bin/2021/day20.rs | 108 | ||||
-rw-r--r-- | src/bin/2021/day21.rs | 215 | ||||
-rw-r--r-- | src/bin/2021/day22.rs | 216 | ||||
-rw-r--r-- | src/bin/2021/day23.rs | 1736 | ||||
-rw-r--r-- | src/bin/2021/day24.rs | 337 | ||||
-rw-r--r-- | src/bin/2021/day25.rs | 96 | ||||
-rw-r--r-- | src/bin/2021/day3.rs | 102 | ||||
-rw-r--r-- | src/bin/2021/day4.rs | 167 | ||||
-rw-r--r-- | src/bin/2021/day5.rs | 123 | ||||
-rw-r--r-- | src/bin/2021/day6.rs | 47 | ||||
-rw-r--r-- | src/bin/2021/day7.rs | 42 | ||||
-rw-r--r-- | src/bin/2021/day8.rs | 185 | ||||
-rw-r--r-- | src/bin/2021/day9.rs | 71 | ||||
-rw-r--r-- | src/bin/2021/main.rs | 74 |
26 files changed, 5090 insertions, 0 deletions
diff --git a/src/bin/2021/day1.rs b/src/bin/2021/day1.rs new file mode 100644 index 0000000..fce763c --- /dev/null +++ b/src/bin/2021/day1.rs @@ -0,0 +1,36 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result<Vec<i64>> { + Ok(parse::lines(fh).collect()) +} + +pub fn part1(ints: Vec<i64>) -> Result<usize> { + Ok(ints + .windows(2) + .map(|a| a[1] - a[0]) + .filter(|x| *x > 0) + .count()) +} + +pub fn part2(ints: Vec<i64>) -> Result<usize> { + Ok(ints + .windows(3) + .map(|a| a[0] + a[1] + a[2]) + .collect::<Vec<_>>() + .windows(2) + .map(|a| a[1] - a[0]) + .filter(|x| *x > 0) + .count()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 1).unwrap()).unwrap()).unwrap(), + 1602 + ); + assert_eq!( + part2(parse(parse::data(2021, 1).unwrap()).unwrap()).unwrap(), + 1633 + ); +} diff --git a/src/bin/2021/day10.rs b/src/bin/2021/day10.rs new file mode 100644 index 0000000..d7b5f48 --- /dev/null +++ b/src/bin/2021/day10.rs @@ -0,0 +1,109 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result<impl Iterator<Item = String>> { + Ok(parse::raw_lines(fh)) +} + +pub fn part1(lines: impl Iterator<Item = String>) -> Result<u64> { + let mut total = 0; + for line in lines { + let mut open = vec![]; + for c in line.chars() { + match c { + '{' | '(' | '[' | '<' => { + open.push(c); + } + '}' | ')' | ']' | '>' => { + let c_open = open.pop(); + if let Some(c_open) = c_open { + let expected = match c_open { + '{' => '}', + '(' => ')', + '[' => ']', + '<' => '>', + _ => unreachable!(), + }; + if c != expected { + total += match c { + '}' => 1197, + ')' => 3, + ']' => 57, + '>' => 25137, + _ => unreachable!(), + }; + break; + } + } else { + break; + } + } + _ => break, + } + } + } + Ok(total) +} + +pub fn part2(lines: impl Iterator<Item = String>) -> Result<u64> { + let mut scores = vec![]; + for line in lines { + let mut open = vec![]; + let mut skip = false; + for c in line.chars() { + match c { + '{' | '(' | '[' | '<' => { + open.push(c); + } + '}' | ')' | ']' | '>' => { + let c_open = open.pop(); + if let Some(c_open) = c_open { + let expected = match c_open { + '{' => '}', + '(' => ')', + '[' => ']', + '<' => '>', + _ => unreachable!(), + }; + if c != expected { + skip = true; + break; + } + } else { + skip = true; + break; + } + } + _ => { + skip = true; + break; + } + } + } + if !skip { + scores.push(open.iter().rev().fold(0, |acc, c| { + acc * 5 + + match c { + '(' => 1, + '[' => 2, + '{' => 3, + '<' => 4, + _ => unreachable!(), + } + })); + } + } + scores.sort_unstable(); + Ok(scores[scores.len() / 2]) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 10).unwrap()).unwrap()).unwrap(), + 166191 + ); + assert_eq!( + part2(parse(parse::data(2021, 10).unwrap()).unwrap()).unwrap(), + 1152088313 + ); +} diff --git a/src/bin/2021/day11.rs b/src/bin/2021/day11.rs new file mode 100644 index 0000000..fac392e --- /dev/null +++ b/src/bin/2021/day11.rs @@ -0,0 +1,82 @@ +use advent_of_code::prelude::*; + +fn iterate(grid: &mut Grid<(u8, bool)>) -> usize { + let mut flashes = 0; + for (cell, _) in grid.cells_mut() { + *cell += 1; + } + + loop { + let mut new_flashes = 0; + let mut updates: Grid<u8> = Grid::default(); + updates.grow(grid.rows(), grid.cols()); + for ((row, col), (cell, flashed)) in grid.indexed_cells_mut() { + if *flashed { + continue; + } + if *cell > 9 { + *flashed = true; + new_flashes += 1; + for (row, col) in updates.adjacent(row, col, true) { + updates[row][col] += 1; + } + } + } + if new_flashes > 0 { + flashes += new_flashes; + for ((row, col), val) in updates.indexed_cells() { + grid[row][col].0 += val; + } + } else { + break; + } + } + + for (cell, flashed) in grid.cells_mut() { + if *flashed { + *cell = 0; + *flashed = false; + } + } + + flashes +} + +pub fn parse(fh: File) -> Result<Grid<(u8, bool)>> { + Ok(parse::digit_grid(parse::raw_lines(fh)) + .indexed_cells() + .map(|((row, col), cell)| ((row, col), (*cell, false))) + .collect()) +} + +pub fn part1(mut map: Grid<(u8, bool)>) -> Result<usize> { + let mut flashes = 0; + for _ in 0..100 { + flashes += iterate(&mut map); + } + Ok(flashes) +} + +pub fn part2(mut map: Grid<(u8, bool)>) -> Result<usize> { + let mut step = 1; + loop { + let flashes = iterate(&mut map); + if flashes == (map.rows().0 * map.cols().0) { + break; + } + step += 1; + } + Ok(step) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 11).unwrap()).unwrap()).unwrap(), + 1673 + ); + assert_eq!( + part2(parse(parse::data(2021, 11).unwrap()).unwrap()).unwrap(), + 279 + ); +} diff --git a/src/bin/2021/day12.rs b/src/bin/2021/day12.rs new file mode 100644 index 0000000..2770aa6 --- /dev/null +++ b/src/bin/2021/day12.rs @@ -0,0 +1,99 @@ +use advent_of_code::prelude::*; + +fn small(s: &str) -> bool { + s.bytes().all(|c| c.is_ascii_lowercase()) +} + +fn single_small<'a>(path: impl Iterator<Item = &'a str>) -> bool { + let mut set = HashSet::new(); + for s in path { + if !small(s) { + continue; + } + if set.contains(s) { + return false; + } + set.insert(s); + } + true +} + +fn paths_from1<'a>( + graph: &'a HashMap<String, HashSet<String>>, + path: &mut Vec<&'a str>, +) -> u64 { + let mut total = 0; + for neighbor in graph[path[path.len() - 1]].iter() { + if small(neighbor) && path.contains(&neighbor.as_ref()) { + continue; + } + if neighbor == "end" { + total += 1; + } else { + path.push(neighbor); + total += paths_from1(graph, path); + path.pop(); + } + } + total +} + +fn paths_from2<'a>( + graph: &'a HashMap<String, HashSet<String>>, + path: &mut Vec<&'a str>, +) -> u64 { + let mut total = 0; + for neighbor in graph[path[path.len() - 1]].iter() { + if neighbor == "start" { + continue; + } + if small(neighbor) + && path.contains(&neighbor.as_ref()) + && !single_small(path.iter().copied()) + { + continue; + } + if neighbor == "end" { + total += 1; + } else { + path.push(neighbor); + total += paths_from2(graph, path); + path.pop(); + } + } + total +} + +pub fn parse(fh: File) -> Result<HashMap<String, HashSet<String>>> { + let mut graph = HashMap::new(); + for line in parse::raw_lines(fh) { + let nodes: Vec<_> = line.split('-').map(|s| s.to_string()).collect(); + let edges = + graph.entry(nodes[0].clone()).or_insert_with(HashSet::new); + edges.insert(nodes[1].clone()); + let edges = + graph.entry(nodes[1].clone()).or_insert_with(HashSet::new); + edges.insert(nodes[0].clone()); + } + Ok(graph) +} + +pub fn part1(graph: HashMap<String, HashSet<String>>) -> Result<u64> { + Ok(paths_from1(&graph, &mut vec!["start"])) +} + +pub fn part2(graph: HashMap<String, HashSet<String>>) -> Result<u64> { + Ok(paths_from2(&graph, &mut vec!["start"])) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 12).unwrap()).unwrap()).unwrap(), + 3230 + ); + assert_eq!( + part2(parse(parse::data(2021, 12).unwrap()).unwrap()).unwrap(), + 83475 + ); +} diff --git a/src/bin/2021/day13.rs b/src/bin/2021/day13.rs new file mode 100644 index 0000000..75e547b --- /dev/null +++ b/src/bin/2021/day13.rs @@ -0,0 +1,144 @@ +use advent_of_code::prelude::*; + +#[derive(Default)] +pub struct Paper { + grid: Grid<bool>, +} + +impl Paper { + fn set(&mut self, row: Row, col: Col) { + self.grid.grow(Row(row.0 + 1), Col(col.0 + 1)); + self.grid[row][col] = true; + } + + fn fold(&mut self, horizontal: bool, coord: usize) { + let mut clone = Self::default(); + if horizontal { + clone.grid.grow( + self.grid.rows(), + Col(coord.max(self.grid.cols().0 - coord - 1)), + ); + for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() { + if *cell { + if coord > self.grid.cols().0 - coord - 1 { + if col < coord { + clone.set(Row(row), Col(col)); + } else if col > coord { + clone.set(Row(row), Col(coord * 2 - col)); + } + } else { + if col < coord { + clone.set( + Row(row), + Col(self.grid.cols().0 - coord * 2 - 1 + col), + ); + } else if col > coord { + clone.set( + Row(row), + Col(self.grid.cols().0 - col - 1), + ); + } + } + } + } + } else { + clone.grid.grow( + Row(coord.max(self.grid.rows().0 - coord - 1)), + self.grid.cols(), + ); + for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() { + if *cell { + if coord > self.grid.rows().0 - coord - 1 { + if row < coord { + clone.set(Row(row), Col(col)); + } else if row > coord { + clone.set(Row(coord * 2 - row), Col(col)); + } + } else { + if row < coord { + clone.set( + Row(self.grid.rows().0 - coord * 2 - 1 + row), + Col(col), + ); + } else if row > coord { + clone.set( + Row(self.grid.rows().0 - row - 1), + Col(col), + ); + } + } + } + } + } + *self = clone; + } + + fn total(&self) -> usize { + self.grid.cells().filter(|b| **b).count() + } +} + +impl std::fmt::Display for Paper { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> Result<(), std::fmt::Error> { + write!( + f, + "{}", + self.grid.display_packed(|b| if *b { '#' } else { '.' }) + ) + } +} + +pub fn parse(fh: File) -> Result<(Paper, Vec<(bool, usize)>)> { + let mut paper = Paper::default(); + let mut folds = vec![]; + for line in parse::raw_lines(fh) { + if line.is_empty() { + continue; + } + if let Some(fold) = line.strip_prefix("fold along ") { + let mut fold = fold.split('='); + let horizontal = fold.next().unwrap() == "x"; + let coord: usize = fold.next().unwrap().parse()?; + folds.push((horizontal, coord)); + } else { + let mut coords = line.split(','); + let x: usize = coords.next().unwrap().parse()?; + let y: usize = coords.next().unwrap().parse()?; + paper.set(Row(y), Col(x)); + } + } + Ok((paper, folds)) +} + +pub fn part1( + (mut paper, folds): (Paper, Vec<(bool, usize)>), +) -> Result<usize> { + paper.fold(folds[0].0, folds[0].1); + Ok(paper.total()) +} + +pub fn part2( + (mut paper, folds): (Paper, Vec<(bool, usize)>), +) -> Result<usize> { + for fold in folds { + paper.fold(fold.0, fold.1); + } + + println!("{}", paper); + Ok(paper.total()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 13).unwrap()).unwrap()).unwrap(), + 678 + ); + assert_eq!( + part2(parse(parse::data(2021, 13).unwrap()).unwrap()).unwrap(), + 95 + ); +} diff --git a/src/bin/2021/day14.rs b/src/bin/2021/day14.rs new file mode 100644 index 0000000..0080015 --- /dev/null +++ b/src/bin/2021/day14.rs @@ -0,0 +1,94 @@ +use advent_of_code::prelude::*; + +fn process(polymer: &[u8], rules: &HashMap<Vec<u8>, u8>) -> Vec<u8> { + let mut insertions = vec![]; + for (i, elements) in polymer.windows(2).enumerate() { + for (pattern, insert) in rules { + if pattern == elements { + insertions.push((i + 1, insert)); + } + } + } + let mut polymer = polymer.to_vec(); + for (idx, c) in insertions.iter().rev() { + polymer.insert(*idx, **c); + } + polymer +} + +pub fn parse(fh: File) -> Result<(Vec<u8>, HashMap<Vec<u8>, u8>)> { + let mut lines = parse::raw_lines(fh); + let polymer = lines.next().unwrap(); + lines.next(); + + let mut rules = HashMap::new(); + for line in lines { + let rule: Vec<_> = line.split(" -> ").collect(); + rules.insert(rule[0].as_bytes().to_vec(), rule[1].as_bytes()[0]); + } + Ok((polymer.as_bytes().to_vec(), rules)) +} + +pub fn part1( + (mut polymer, rules): (Vec<u8>, HashMap<Vec<u8>, u8>), +) -> Result<u64> { + for _ in 0..10 { + polymer = process(&polymer, &rules); + } + let mut elements = HashMap::new(); + for element in polymer { + let count = elements.entry(element).or_insert(0); + *count += 1; + } + Ok(elements.values().max().unwrap() - elements.values().min().unwrap()) +} + +pub fn part2( + (polymer, rules): (Vec<u8>, HashMap<Vec<u8>, u8>), +) -> Result<u64> { + let mut pairs = HashMap::new(); + for pair in polymer.windows(2) { + let count = pairs.entry([pair[0], pair[1]]).or_insert(0); + *count += 1; + } + + for _ in 0..40 { + let mut next = HashMap::new(); + for (pair, count) in &mut pairs { + let insert = rules[&pair[..]]; + let new_pair1 = [pair[0], insert]; + let new_pair2 = [insert, pair[1]]; + let next_count = next.entry(new_pair1).or_insert(0); + *next_count += *count; + let next_count = next.entry(new_pair2).or_insert(0); + *next_count += *count; + } + pairs = next; + } + let mut elements = HashMap::new(); + for (pair, count) in pairs { + let element_count = elements.entry(pair[0]).or_insert(0); + *element_count += count; + let element_count = elements.entry(pair[1]).or_insert(0); + *element_count += count; + } + let element_count = elements.entry(polymer[0]).or_insert(0); + *element_count += 1; + let element_count = + elements.entry(polymer[polymer.len() - 1]).or_insert(0); + *element_count += 1; + Ok(elements.values().max().unwrap() / 2 + - elements.values().min().unwrap() / 2) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 14).unwrap()).unwrap()).unwrap(), + 2874 + ); + assert_eq!( + part2(parse(parse::data(2021, 14).unwrap()).unwrap()).unwrap(), + 5208377027195 + ); +} diff --git a/src/bin/2021/day15.rs b/src/bin/2021/day15.rs new file mode 100644 index 0000000..ca7a72f --- /dev/null +++ b/src/bin/2021/day15.rs @@ -0,0 +1,68 @@ +use advent_of_code::prelude::*; + +pub struct Map { + grid: Grid<u8>, +} + +impl advent_of_code::graph::Graph<(Row, Col), (Row, Col)> for Map { + type Edges = advent_of_code::grid::Adjacent; + + fn edges(&self, v: (Row, Col)) -> Self::Edges { + self.grid.adjacent(v.0, v.1, false) + } + + fn edge(&self, _v: (Row, Col), e: (Row, Col)) -> ((Row, Col), u64) { + (e, u64::from(self.grid[e.0][e.1])) + } +} + +pub fn parse(fh: File) -> Result<Map> { + Ok(Map { + grid: parse::digit_grid(parse::raw_lines(fh)), + }) +} + +pub fn part1(map: Map) -> Result<u64> { + Ok(map + .dijkstra( + (Row(0), Col(0)), + (map.grid.rows() - 1, map.grid.cols() - 1), + ) + .0) +} + +pub fn part2(map: Map) -> Result<u64> { + let mut large_grid = Grid::default(); + large_grid.grow(Row(map.grid.rows().0 * 5), Col(map.grid.cols().0 * 5)); + for lrow in 0..5 { + for lcol in 0..5 { + for ((Row(row), Col(col)), val) in map.grid.indexed_cells() { + let mut val = val + lrow + lcol; + while val > 9 { + val -= 9; + } + large_grid[Row(usize::from(lrow) * map.grid.rows().0 + row)] + [Col(usize::from(lcol) * map.grid.cols().0 + col)] = val; + } + } + } + let large_map = Map { grid: large_grid }; + Ok(large_map + .dijkstra( + (Row(0), Col(0)), + (large_map.grid.rows() - 1, large_map.grid.cols() - 1), + ) + .0) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 15).unwrap()).unwrap()).unwrap(), + 441 + ); + assert_eq!( + part2(parse(parse::data(2021, 15).unwrap()).unwrap()).unwrap(), + 2849 + ); +} diff --git a/src/bin/2021/day16.rs b/src/bin/2021/day16.rs new file mode 100644 index 0000000..3177483 --- /dev/null +++ b/src/bin/2021/day16.rs @@ -0,0 +1,210 @@ +use advent_of_code::prelude::*; + +struct BitIter { + byte: u8, + pos: u8, +} + +impl BitIter { + fn new(byte: u8) -> Self { + Self { byte, pos: 0 } + } +} + +impl Iterator for BitIter { + type Item = bool; + + fn next(&mut self) -> Option<Self::Item> { + if self.pos >= 8 { + return None; + } + + let ret = self.byte.leading_ones() > 0; + self.byte <<= 1; + self.pos += 1; + Some(ret) + } +} + +fn bits(bytes: impl Iterator<Item = u8>) -> impl Iterator<Item = bool> { + bytes.flat_map(BitIter::new) +} + +struct LiteralU8(u8); + +impl FromIterator<bool> for LiteralU8 { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = bool>, + { + let mut ret = 0; + for b in iter { + ret = (ret << 1) | u8::from(b); + } + Self(ret) + } +} + +struct LiteralU16(u16); + +impl FromIterator<bool> for LiteralU16 { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = bool>, + { + let mut ret = 0; + for b in iter { + ret = (ret << 1) | u16::from(b); + } + Self(ret) + } +} + +pub struct Packet { + version: u8, + id: u8, + contents: PacketContents, +} + +enum PacketContents { + Literal { value: u64 }, + Operator { packets: Vec<Packet> }, +} + +impl Packet { + fn parse(bits: &mut impl Iterator<Item = bool>) -> (Self, usize) { + let LiteralU8(version) = bits.take(3).collect(); + let LiteralU8(id) = bits.take(3).collect(); + let mut nbits = 6; + let contents = if id == 4 { + let (value, size) = read_varnum(bits.by_ref()); + nbits += size; + PacketContents::Literal { value } + } else { + let mut packets = vec![]; + nbits += 1; + if bits.next().unwrap() { + let LiteralU16(subpacket_count) = bits.take(11).collect(); + nbits += 11; + for _ in 0..subpacket_count { + let (packet, size) = Self::parse(bits); + packets.push(packet); + nbits += size; + } + } else { + let LiteralU16(remaining_bits) = bits.take(15).collect(); + nbits += 15; + let mut remaining_bits = usize::from(remaining_bits); + while remaining_bits > 0 { + let (packet, size) = Self::parse(bits); + packets.push(packet); + nbits += size; + remaining_bits -= size; + } + } + PacketContents::Operator { packets } + }; + ( + Self { + version, + id, + contents, + }, + nbits, + ) + } + + fn subpackets(&self) -> impl Iterator<Item = &Self> { + let mut to_return = VecDeque::new(); + to_return.push_back(self); + Subpackets { to_return } + } + + fn eval(&self) -> u64 { + match &self.contents { + PacketContents::Literal { value } => *value, + PacketContents::Operator { packets } => match self.id { + 0 => packets.iter().map(|packet| packet.eval()).sum(), + 1 => packets.iter().map(|packet| packet.eval()).product(), + 2 => { + packets.iter().map(|packet| packet.eval()).min().unwrap() + } + 3 => { + packets.iter().map(|packet| packet.eval()).max().unwrap() + } + 4 => unreachable!(), + 5 => u64::from(packets[0].eval() > packets[1].eval()), + 6 => u64::from(packets[0].eval() < packets[1].eval()), + 7 => u64::from(packets[0].eval() == packets[1].eval()), + _ => unreachable!(), + }, + } + } +} + +fn read_varnum(bits: &mut impl Iterator<Item = bool>) -> (u64, usize) { + let mut ret = 0; + let mut nbits = 0; + while bits.next().unwrap() { + let LiteralU8(chunk) = bits.take(4).collect(); + ret = (ret << 4) | u64::from(chunk); + nbits += 5; + } + let LiteralU8(chunk) = bits.take(4).collect(); + ret = (ret << 4) | u64::from(chunk); + nbits += 5; + (ret, nbits) +} + +struct Subpackets<'a> { + to_return: VecDeque<&'a Packet>, +} + +impl<'a> Iterator for Subpackets<'a> { + type Item = &'a Packet; + + fn next(&mut self) -> Option<Self::Item> { + let next = self.to_return.pop_front(); + if let Some(next) = next { + match &next.contents { + PacketContents::Literal { .. } => {} + PacketContents::Operator { packets } => { + self.to_return.extend(packets.iter()); + } + } + } + next + } +} + +pub fn parse(fh: File) -> Result<Packet> { + let line = parse::raw_lines(fh).next().unwrap(); + let mut bits = bits(line.as_bytes().chunks(2).map(|bs| { + u8::from_str_radix(std::str::from_utf8(bs).unwrap(), 16).unwrap() + })); + let (packet, _) = Packet::parse(bits.by_ref()); + Ok(packet) +} + +pub fn part1(packet: Packet) -> Result<u64> { + Ok(packet + .subpackets() + .map(|packet| u64::from(packet.version)) + .sum()) +} + +pub fn part2(packet: Packet) -> Result<u64> { + Ok(packet.eval()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 16).unwrap()).unwrap()).unwrap(), + 979 + ); + assert_eq!( + part2(parse(parse::data(2021, 16).unwrap()).unwrap()).unwrap(), + 277110354175 + ); +} diff --git a/src/bin/2021/day17.rs b/src/bin/2021/day17.rs new file mode 100644 index 0000000..54ee4bb --- /dev/null +++ b/src/bin/2021/day17.rs @@ -0,0 +1,106 @@ +use advent_of_code::prelude::*; + +fn fire( + mut xv: i64, + mut yv: i64, + xrange: &std::ops::RangeInclusive<i64>, + yrange: &std::ops::RangeInclusive<i64>, +) -> Option<i64> { + let mut xpos = 0; + let mut ypos = 0; + let mut max_height = 0; + loop { + if xrange.contains(&xpos) && yrange.contains(&ypos) { + return Some(max_height); + } else if (xv >= 0 && xpos > *xrange.end()) + || (xv <= 0 && xpos < *xrange.start()) + || (ypos < *yrange.start()) + { + return None; + } + + xpos += xv; + ypos += yv; + if ypos > max_height { + max_height = ypos; + } + match xv.cmp(&0) { + Ordering::Greater => { + xv -= 1; + } + Ordering::Less => { + xv += 1; + } + _ => {} + } + yv -= 1; + } +} + +pub fn parse( + fh: File, +) -> Result<(std::ops::RangeInclusive<i64>, std::ops::RangeInclusive<i64>)> { + let line = parse::raw_lines(fh).next().unwrap(); + let captures = regex_captures!( + r"target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)", + &line, + ) + .unwrap(); + let xrange: std::ops::RangeInclusive<i64> = + captures[1].parse().unwrap()..=captures[2].parse().unwrap(); + let yrange: std::ops::RangeInclusive<i64> = + captures[3].parse().unwrap()..=captures[4].parse().unwrap(); + Ok((xrange, yrange)) +} + +pub fn part1( + (xrange, yrange): ( + std::ops::RangeInclusive<i64>, + std::ops::RangeInclusive<i64>, + ), +) -> Result<i64> { + let mut max_height = 0; + for xv in *xrange.start().min(&0)..=*xrange.end().max(&0) { + for yv in *yrange.start().min(&0) + ..=yrange.start().abs().max(yrange.end().abs()) + { + if let Some(height) = fire(xv, yv, &xrange, &yrange) { + if height > max_height { + max_height = height; + } + } + } + } + Ok(max_height) +} + +pub fn part2( + (xrange, yrange): ( + std::ops::RangeInclusive<i64>, + std::ops::RangeInclusive<i64>, + ), +) -> Result<u64> { + let mut count = 0; + for xv in *xrange.start().min(&0)..=*xrange.end().max(&0) { + for yv in *yrange.start().min(&0) + ..=yrange.start().abs().max(yrange.end().abs()) + { + if fire(xv, yv, &xrange, &yrange).is_some() { + count += 1; + } + } + } + Ok(count) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 17).unwrap()).unwrap()).unwrap(), + 5886 + ); + assert_eq!( + part2(parse(parse::data(2021, 17).unwrap()).unwrap()).unwrap(), + 1806 + ); +} diff --git a/src/bin/2021/day18.rs b/src/bin/2021/day18.rs new file mode 100644 index 0000000..6a7e73d --- /dev/null +++ b/src/bin/2021/day18.rs @@ -0,0 +1,257 @@ +use advent_of_code::prelude::*; + +#[derive(Clone)] +pub enum Number { + Value(u8), + Pair(Box<Number>, Box<Number>), +} + +impl std::str::FromStr for Number { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + Ok(Self::parse(s)) + } +} + +impl Number { + fn parse(s: &str) -> Self { + if s.starts_with('[') { + Self::parse_pair(s) + } else { + Self::parse_number(s) + } + } + + fn parse_pair(s: &str) -> Self { + let mut depth = 1; + let mut start = 1; + let mut children = vec![]; + for (i, c) in s.chars().enumerate().skip(1) { + match c { + '[' => { + depth += 1; + } + ',' => { + if depth == 1 { + children.push(Self::parse(&s[start..i])); + start = i + 1; + } + } + ']' => { + depth -= 1; + } + _ => {} + } + if depth == 0 { + children.push(Self::parse(&s[start..i])); + break; + } + } + let right = children.pop().unwrap(); + let left = children.pop().unwrap(); + Self::Pair(Box::new(left), Box::new(right)) + } + + fn parse_number(s: &str) -> Self { + Self::Value(s.as_bytes()[0] - b'0') + } + + fn reduce(&mut self) { + loop { + if !self.visit_explode() && !self.visit_split() { + break; + } + } + } + + fn visit_explode(&mut self) -> bool { + let mut idx = 0; + if let Some((explode_idx, (left, right))) = + self.find_to_explode(0, &mut idx) + { + idx = 0; + self.explode(explode_idx, left, right, &mut idx); + true + } else { + false + } + } + + fn find_to_explode( + &mut self, + depth: usize, + idx: &mut usize, + ) -> Option<(usize, (u8, u8))> { + match self { + Self::Value(_) => { + *idx += 1; + None + } + Self::Pair(left, right) => { + if depth == 4 { + let left = if let Self::Value(n) = **left { + n + } else { + panic!("unexpected pair") + }; + let right = if let Self::Value(n) = **right { + n + } else { + panic!("unexpected pair") + }; + *self = Self::Value(0); + Some((*idx, (left, right))) + } else { + left.find_to_explode(depth + 1, idx) + .or_else(|| right.find_to_explode(depth + 1, idx)) + } + } + } + } + + fn explode( + &mut self, + explode_idx: usize, + left_val: u8, + right_val: u8, + idx: &mut usize, + ) { + match self { + Self::Value(ref mut n) => { + if *idx + 1 == explode_idx { + *n += left_val; + } else if *idx == explode_idx + 1 { + *n += right_val; + } + *idx += 1; + } + Self::Pair(left, right) => { + left.explode(explode_idx, left_val, right_val, idx); + right.explode(explode_idx, left_val, right_val, idx); + } + } + } + + fn visit_split(&mut self) -> bool { + match self { + Self::Value(n) => { + if *n >= 10 { + *self = Self::Pair( + Box::new(Self::Value(*n / 2)), + Box::new(Self::Value(*n - *n / 2)), + ); + true + } else { + false + } + } + Self::Pair(left, right) => { + left.visit_split() || right.visit_split() + } + } + } + + fn magnitude(&self) -> u64 { + match self { + Self::Value(n) => u64::from(*n), + Self::Pair(left, right) => { + left.magnitude() * 3 + right.magnitude() * 2 + } + } + } +} + +impl std::ops::Add for Number { + type Output = Number; + fn add(self, other: Number) -> Self::Output { + let mut ret = Number::Pair(Box::new(self), Box::new(other)); + ret.reduce(); + ret + } +} + +impl std::ops::Add for &Number { + type Output = Number; + fn add(self, other: &Number) -> Self::Output { + let mut ret = + Number::Pair(Box::new(self.clone()), Box::new(other.clone())); + ret.reduce(); + ret + } +} + +impl std::ops::AddAssign for Number { + fn add_assign(&mut self, other: Number) { + *self = self.clone() + other; + } +} + +impl std::iter::Sum for Number { + fn sum<I>(mut iter: I) -> Self + where + I: Iterator<Item = Self>, + { + if let Some(first) = iter.next() { + let mut sum = first; + for num in iter { + sum += num; + } + sum + } else { + Number::Value(0) + } + } +} + +impl std::fmt::Display for Number { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> Result<(), std::fmt::Error> { + match self { + Self::Value(n) => write!(f, "{}", n), + Self::Pair(left, right) => { + write!(f, "[{},{}]", left, right) + } + } + } +} + +pub fn parse(fh: File) -> Result<impl Iterator<Item = Number>> { + Ok(parse::lines(fh)) +} + +pub fn part1(numbers: impl Iterator<Item = Number>) -> Result<u64> { + let sum: Number = numbers.sum(); + Ok(sum.magnitude()) +} + +pub fn part2(numbers: impl Iterator<Item = Number>) -> Result<u64> { + let nums: Vec<_> = numbers.collect(); + let mut max = 0; + for (i, n1) in nums.iter().enumerate() { + for (j, n2) in nums.iter().enumerate() { + if i == j { + continue; + } + let magnitude = (n1 + n2).magnitude(); + if magnitude > max { + max = magnitude; + } + } + } + Ok(max) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 18).unwrap()).unwrap()).unwrap(), + 3806 + ); + assert_eq!( + part2(parse(parse::data(2021, 18).unwrap()).unwrap()).unwrap(), + 4727 + ); +} diff --git a/src/bin/2021/day19.rs b/src/bin/2021/day19.rs new file mode 100644 index 0000000..735cb19 --- /dev/null +++ b/src/bin/2021/day19.rs @@ -0,0 +1,293 @@ +use advent_of_code::prelude::*; + +const ORIENTATIONS: &[&dyn Fn(Point) -> Point] = &[ + &|p| Point::new(p.y, p.z, p.x), + &|p| Point::new(-p.y, -p.z, p.x), + &|p| Point::new(p.z, -p.y, p.x), + &|p| Point::new(-p.z, p.y, p.x), + &|p| Point::new(p.y, -p.z, -p.x), + &|p| Point::new(-p.y, p.z, -p.x), + &|p| Point::new(p.z, p.y, -p.x), + &|p| Point::new(-p.z, -p.y, -p.x), + &|p| Point::new(p.x, -p.z, p.y), + &|p| Point::new(-p.x, p.z, p.y), + &|p| Point::new(p.z, p.x, p.y), + &|p| Point::new(-p.z, -p.x, p.y), + &|p| Point::new(p.x, p.z, -p.y), + &|p| Point::new(-p.x, -p.z, -p.y), + &|p| Point::new(p.z, -p.x, -p.y), + &|p| Point::new(-p.z, p.x, -p.y), + &|p| Point::new(p.x, p.y, p.z), + &|p| Point::new(-p.x, -p.y, p.z), + &|p| Point::new(p.y, -p.x, p.z), + &|p| Point::new(-p.y, p.x, p.z), + &|p| Point::new(p.x, -p.y, -p.z), + &|p| Point::new(-p.x, p.y, -p.z), + &|p| Point::new(p.y, p.x, -p.z), + &|p| Point::new(-p.y, -p.x, -p.z), +]; + +#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq)] +struct Point { + x: i16, + y: i16, + z: i16, +} + +impl Point { + fn new(x: i16, y: i16, z: i16) -> Self { + Self { x, y, z } + } +} + +impl std::ops::Add for Point { + type Output = Point; + fn add(self, other: Point) -> Self::Output { + Point { + x: self.x + other.x, + y: self.y + other.y, + z: self.z + other.z, + } + } +} + +impl std::ops::AddAssign for Point { + fn add_assign(&mut self, other: Point) { + self.x += other.x; + self.y += other.y; + self.z += other.z; + } +} + +impl std::ops::Sub for Point { + type Output = Point; + fn sub(self, other: Point) -> Self::Output { + Point { + x: self.x - other.x, + y: self.y - other.y, + z: self.z - other.z, + } + } +} + +impl std::ops::SubAssign for Point { + fn sub_assign(&mut self, other: Point) { + self.x -= other.x; + self.y -= other.y; + self.z -= other.z; + } +} + +impl std::fmt::Display for Point { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> Result<(), std::fmt::Error> { + write!(f, "({},{},{})", self.x, self.y, self.z) + } +} + +#[derive(Debug, Clone)] +struct Scanner { + beacons: Vec<Point>, +} + +impl Scanner { + fn parse(lines: impl Iterator<Item = String>) -> Self { + let mut beacons = vec![]; + for line in lines { + let mut parts = line.split(',').map(|i| i.parse().unwrap()); + let x = parts.next().unwrap(); + let y = parts.next().unwrap(); + let z = parts.next().unwrap(); + beacons.push(Point::new(x, y, z)) + } + Self { beacons } + } + + fn matches(&self, other: &HashSet<Point>) -> Option<(usize, Point)> { + for (i, beacons) in self.each_orientation().enumerate() { + let mut offsets = vec![]; + for beacon1 in &beacons { + for beacon2 in other { + offsets.push(*beacon2 - *beacon1); + } + } + for offset in offsets { + let matches = beacons + .iter() + .filter(|beacon| other.contains(&(**beacon + offset))) + .count(); + if matches == 0 { + panic!("bug"); + } + if matches >= 12 { + return Some((i, offset)); + } + } + } + None + } + + fn each_orientation(&self) -> impl Iterator<Item = Vec<Point>> { + let beacons = self.beacons.clone(); + ORIENTATIONS.iter().map(move |orientation| { + beacons.iter().map(|beacon| orientation(*beacon)).collect() + }) + } + + fn at_orientation<F: Fn(Point) -> Point>( + &self, + orientation: F, + offset: Point, + ) -> Self { + Self { + beacons: self + .beacons + .iter() + .map(|beacon| orientation(*beacon) + offset) + .collect(), + } + } +} + +#[derive(Debug)] +pub struct Scan { + scanners: Vec<Scanner>, +} + +impl Scan { + fn parse(mut lines: impl Iterator<Item = String>) -> Self { + let mut scanners = vec![]; + while lines.next().is_some() { + scanners.push(Scanner::parse(parse::chunk(&mut lines))); + } + Self { scanners } + } + + fn scanners(&self) -> &[Scanner] { + &self.scanners + } +} + +pub fn parse(fh: File) -> Result<Scan> { + Ok(Scan::parse(parse::raw_lines(fh))) +} + +pub fn part1(scan: Scan) -> Result<usize> { + let mut beacons: HashSet<Point> = HashSet::new(); + let mut skip = None; + for (i, scanner1) in scan.scanners().iter().enumerate() { + for (j, scanner2) in scan.scanners().iter().enumerate().skip(i + 1) { + if let Some((orientation, offset)) = + scanner2.matches(&scanner1.beacons.iter().copied().collect()) + { + let scanner2 = scanner2 + .at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner1.beacons.iter()); + beacons.extend(scanner2.beacons.iter()); + skip = Some((i, j)); + break; + } + } + if skip.is_some() { + break; + } + } + let skip = skip.unwrap(); + let mut scanners = scan.scanners().to_vec(); + scanners.remove(skip.1); + scanners.remove(skip.0); + + let mut found = None; + loop { + for (i, scanner) in scanners.iter().enumerate() { + if let Some((orientation, offset)) = scanner.matches(&beacons) { + let scanner = + scanner.at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner.beacons.iter()); + found = Some(i); + break; + } + } + if let Some(idx) = found { + scanners.remove(idx); + found = None; + } else { + break; + } + } + Ok(beacons.len()) +} + +pub fn part2(scan: Scan) -> Result<i16> { + let mut beacons: HashSet<Point> = HashSet::new(); + let mut skip = None; + let mut offsets = vec![]; + for (i, scanner1) in scan.scanners().iter().enumerate() { + for (j, scanner2) in scan.scanners().iter().enumerate().skip(i + 1) { + if let Some((orientation, offset)) = + scanner2.matches(&scanner1.beacons.iter().copied().collect()) + { + let scanner2 = scanner2 + .at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner1.beacons.iter()); + beacons.extend(scanner2.beacons.iter()); + skip = Some((i, j)); + offsets.push(Point::new(0, 0, 0)); + offsets.push(offset); + break; + } + } + if skip.is_some() { + break; + } + } + let skip = skip.unwrap(); + let mut scanners = scan.scanners().to_vec(); + scanners.remove(skip.1); + scanners.remove(skip.0); + + let mut found = None; + loop { + for (i, scanner) in scanners.iter().enumerate() { + if let Some((orientation, offset)) = scanner.matches(&beacons) { + let scanner = + scanner.at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner.beacons.iter()); + offsets.push(offset); + found = Some(i); + break; + } + } + if let Some(idx) = found { + scanners.remove(idx); + found = None; + } else { + break; + } + } + let mut max = 0; + for offset1 in &offsets { + for offset2 in &offsets { + let dist = *offset1 - *offset2; + let dist = dist.x.abs() + dist.y.abs() + dist.z.abs(); + if dist > max { + max = dist; + } + } + } + Ok(max) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 19).unwrap()).unwrap()).unwrap(), + 338 + ); + assert_eq!( + part2(parse(parse::data(2021, 19).unwrap()).unwrap()).unwrap(), + 9862 + ); +} diff --git a/src/bin/2021/day2.rs b/src/bin/2021/day2.rs new file mode 100644 index 0000000..5ae3596 --- /dev/null +++ b/src/bin/2021/day2.rs @@ -0,0 +1,73 @@ +use advent_of_code::prelude::*; + +pub enum Command { + Forward(i64), + Down(i64), + Up(i64), +} + +pub fn parse(fh: File) -> Result<impl Iterator<Item = Command>> { + Ok(parse::raw_lines(fh).map(|line| { + if let Some(n) = line.strip_prefix("forward ") { + Command::Forward(n.parse().unwrap()) + } else if let Some(n) = line.strip_prefix("down ") { + Command::Down(n.parse().unwrap()) + } else if let Some(n) = line.strip_prefix("up ") { + Command::Up(n.parse().unwrap()) + } else { + panic!("couldn't parse line: {}", line); + } + })) +} + +pub fn part1(commands: impl Iterator<Item = Command>) -> Result<i64> { + let mut horizontal = 0; + let mut vertical = 0; + for command in commands { + match command { + Command::Forward(n) => { + horizontal += n; + } + Command::Down(n) => { + vertical += n; + } + Command::Up(n) => { + vertical -= n; + } + } + } + Ok(horizontal * vertical) +} + +pub fn part2(commands: impl Iterator<Item = Command>) -> Result<i64> { + let mut aim = 0; + let mut horizontal = 0; + let mut vertical = 0; + for command in commands { + match command { + Command::Forward(n) => { + horizontal += n; + vertical += aim * n; + } + Command::Down(n) => { + aim += n; + } + Command::Up(n) => { + aim -= n; + } + } + } + Ok(horizontal * vertical) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 2).unwrap()).unwrap()).unwrap(), + 1694130 + ); + assert_eq!( + part2(parse(parse::data(2021, 2).unwrap()).unwrap()).unwrap(), + 1698850445 + ); +} diff --git a/src/bin/2021/day20.rs b/src/bin/2021/day20.rs new file mode 100644 index 0000000..4ff8b7d --- /dev/null +++ b/src/bin/2021/day20.rs @@ -0,0 +1,108 @@ +use advent_of_code::prelude::*; + +pub struct Image { + algorithm: Vec<bool>, + map: Grid<bool>, + outer: bool, +} + +impl Image { + fn new(algorithm: Vec<bool>, map: Grid<bool>) -> Self { + Self { + algorithm, + map, + outer: false, + } + } + + fn enhance(&mut self) { + let mut new_map: Grid<bool> = Grid::default(); + new_map.grow(self.map.rows() + 2, self.map.cols() + 2); + for row in 0..new_map.rows().0 { + for col in 0..new_map.cols().0 { + let neighbors: &[(Option<usize>, Option<usize>)] = &[ + (row.checked_sub(2), col.checked_sub(2)), + (row.checked_sub(2), col.checked_sub(1)), + (row.checked_sub(2), Some(col)), + (row.checked_sub(1), col.checked_sub(2)), + (row.checked_sub(1), col.checked_sub(1)), + (row.checked_sub(1), Some(col)), + (Some(row), col.checked_sub(2)), + (Some(row), col.checked_sub(1)), + (Some(row), Some(col)), + ]; + let neighbors = neighbors.iter().map(|neighbor| { + if let (Some(row), Some(col)) = neighbor { + self.map + .get(Row(*row)) + .and_then(|row| row.get(Col(*col)).copied()) + .unwrap_or(self.outer) + } else { + self.outer + } + }); + let mut idx = 0; + for neighbor in neighbors { + idx = idx * 2 + usize::from(neighbor); + } + new_map[Row(row)][Col(col)] = self.algorithm[idx] + } + } + self.map = new_map; + if self.outer { + self.outer = self.algorithm[511]; + } else { + self.outer = self.algorithm[0]; + } + } + + fn count_true(&self) -> usize { + if self.outer { + panic!("infinite"); + } + self.map.cells().filter(|c| **c).count() + } +} + +pub fn parse(fh: File) -> Result<Image> { + let mut lines = parse::raw_lines(fh); + let algorithm = lines.next().unwrap(); + let algorithm: Vec<_> = algorithm + .as_bytes() + .iter() + .map(|b| match b { + b'#' => true, + b'.' => false, + _ => panic!("bad algorithm"), + }) + .collect(); + lines.next().unwrap(); + let map = parse::bool_grid(lines, b'#', b'.'); + Ok(Image::new(algorithm, map)) +} + +pub fn part1(mut image: Image) -> Result<usize> { + for _ in 0..2 { + image.enhance(); + } + Ok(image.count_true()) +} + +pub fn part2(mut image: Image) -> Result<usize> { + for _ in 0..50 { + image.enhance(); + } + Ok(image.count_true()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 20).unwrap()).unwrap()).unwrap(), + 5306 + ); + assert_eq!( + part2(parse(parse::data(2021, 20).unwrap()).unwrap()).unwrap(), + 17497 + ); +} diff --git a/src/bin/2021/day21.rs b/src/bin/2021/day21.rs new file mode 100644 index 0000000..2cf6bfe --- /dev/null +++ b/src/bin/2021/day21.rs @@ -0,0 +1,215 @@ +use advent_of_code::prelude::*; + +#[derive(Clone)] +pub struct Game { + p1_pos: i64, + p2_pos: i64, + p1_score: i64, + p2_score: i64, + rolls: i64, + die_state: i64, +} + +impl Game { + fn new(p1: i64, p2: i64) -> Self { + Self { + p1_pos: p1, + p2_pos: p2, + p1_score: 0, + p2_score: 0, + rolls: 0, + die_state: 0, + } + } + + fn roll_deterministic(&mut self) -> i64 { + self.die_state += 3; + self.rolls += 3; + self.die_state * 3 - 3 + } + + fn score(&mut self, score: i64, p1: bool) { + if p1 { + self.p1_pos += score; + while self.p1_pos > 10 { + self.p1_pos -= 10; + } + self.p1_score += self.p1_pos; + } else { + self.p2_pos += score; + while self.p2_pos > 10 { + self.p2_pos -= 10; + } + self.p2_score += self.p2_pos; + } + } + + fn value(&self, threshold: i64) -> Option<i64> { + if self.p1_score >= threshold { + Some(self.p2_score * self.rolls) + } else if self.p2_score >= threshold { + Some(self.p1_score * self.rolls) + } else { + None + } + } + + fn run_dirac(&self, p1: bool) -> (i64, i64) { + let mut p1_wins = 0; + let mut p2_wins = 0; + { + let mut clone = self.clone(); + clone.score(3, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 1; + } else { + p2_wins += 1; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0; + p2_wins += wins.1; + } + } + { + let mut clone = self.clone(); + clone.score(4, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 3; + } else { + p2_wins += 3; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 3; + p2_wins += wins.1 * 3; + } + } + { + let mut clone = self.clone(); + clone.score(5, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 6; + } else { + p2_wins += 6; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 6; + p2_wins += wins.1 * 6; + } + } + { + let mut clone = self.clone(); + clone.score(6, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 7; + } else { + p2_wins += 7; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 7; + p2_wins += wins.1 * 7; + } + } + { + let mut clone = self.clone(); + clone.score(7, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 6; + } else { + p2_wins += 6; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 6; + p2_wins += wins.1 * 6; + } + } + { + let mut clone = self.clone(); + clone.score(8, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 3; + } else { + p2_wins += 3; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 3; + p2_wins += wins.1 * 3; + } + } + { + let mut clone = self.clone(); + clone.score(9, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 1; + } else { + p2_wins += 1; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0; + p2_wins += wins.1; + } + } + (p1_wins, p2_wins) + } +} + +pub fn parse(fh: File) -> Result<Game> { + let mut lines = parse::raw_lines(fh); + let p1 = lines + .next() + .unwrap() + .strip_prefix("Player 1 starting position: ") + .unwrap() + .parse() + .unwrap(); + let p2 = lines + .next() + .unwrap() + .strip_prefix("Player 2 starting position: ") + .unwrap() + .parse() + .unwrap(); + Ok(Game::new(p1, p2)) +} + +pub fn part1(mut game: Game) -> Result<i64> { + let mut p1 = true; + loop { + if let Some(value) = game.value(1000) { + return Ok(value); + } + let score = game.roll_deterministic(); + game.score(score, p1); + p1 = !p1; + } +} + +pub fn part2(game: Game) -> Result<i64> { + let (p1, p2) = game.run_dirac(true); + Ok(p1.max(p2)) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 21).unwrap()).unwrap()).unwrap(), + 1004670 + ); + assert_eq!( + part2(parse(parse::data(2021, 21).unwrap()).unwrap()).unwrap(), + 492043106122795 + ); +} diff --git a/src/bin/2021/day22.rs b/src/bin/2021/day22.rs new file mode 100644 index 0000000..ed8a0de --- /dev/null +++ b/src/bin/2021/day22.rs @@ -0,0 +1,216 @@ +use advent_of_code::prelude::*; + +#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)] +struct Point3D { + x: i64, + y: i64, + z: i64, +} + +impl Point3D { + fn new(x: i64, y: i64, z: i64) -> Self { + Self { x, y, z } + } +} + +#[derive(Debug, Clone, Hash, PartialEq, Eq)] +struct Range3D { + x: std::ops::RangeInclusive<i64>, + y: std::ops::RangeInclusive<i64>, + z: std::ops::RangeInclusive<i64>, +} + +impl Range3D { + fn new( + x: std::ops::RangeInclusive<i64>, + y: std::ops::RangeInclusive<i64>, + z: std::ops::RangeInclusive<i64>, + ) -> Self { + Self { x, y, z } + } + + fn contains(&self, point: &Point3D) -> bool { + self.x.contains(&point.x) + && self.y.contains(&point.y) + && self.z.contains(&point.z) + } + + fn intersects(&self, other: &Self) -> bool { + (self.x.contains(other.x.start()) + || self.x.contains(other.x.end()) + || other.x.contains(self.x.start()) + || other.x.contains(self.x.end())) + && (self.y.contains(other.y.start()) + || self.y.contains(other.y.end()) + || other.y.contains(self.y.start()) + || other.y.contains(self.y.end())) + && (self.z.contains(other.z.start()) + || self.z.contains(other.z.end()) + || other.z.contains(self.z.start()) + || other.z.contains(self.z.end())) + } + + fn intersected_ranges(&self, other: &Self) -> Vec<Self> { + let mut ret = vec![]; + let mut found = false; + for x in Self::split_dimension(&self.x, &other.x) { + for y in Self::split_dimension(&self.y, &other.y) { + for z in Self::split_dimension(&self.z, &other.z) { + let new = Self::new(x.clone(), y.clone(), z.clone()); + if other.intersects(&new) { + if found { + panic!("bug 1"); + } + found = true; + } else { + ret.push(new); + } + } + } + } + if !found { + panic!("bug 2"); + } + ret + } + + fn split_dimension( + to_split: &std::ops::RangeInclusive<i64>, + split_by: &std::ops::RangeInclusive<i64>, + ) -> Vec<std::ops::RangeInclusive<i64>> { + if split_by.start() <= to_split.start() { + if split_by.end() < to_split.start() { + panic!("bug 3"); + } else if split_by.end() >= to_split.end() { + vec![to_split.clone()] + } else { + vec![ + *to_split.start()..=*split_by.end(), + (*split_by.end() + 1)..=*to_split.end(), + ] + } + } else if split_by.start() > to_split.end() { + panic!("bug 4"); + } else { + if split_by.end() >= to_split.end() { + vec![ + *to_split.start()..=(*split_by.start() - 1), + *split_by.start()..=*to_split.end(), + ] + } else { + vec![ + *to_split.start()..=(*split_by.start() - 1), + split_by.clone(), + (*split_by.end() + 1)..=*to_split.end(), + ] + } + } + } + + fn size(&self) -> i64 { + (self.x.end() - self.x.start() + 1) + * (self.y.end() - self.y.start() + 1) + * (self.z.end() - self.z.start() + 1) + } +} + +#[derive(Debug, Clone)] +struct Rule { + on: bool, + range: Range3D, +} + +impl Rule { + fn parse(line: &str) -> Self { + let captures = regex_captures!( + r"^(\w+) x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)$", + line + ) + .unwrap(); + Self { + on: &captures[1] == "on", + range: Range3D::new( + captures[2].parse().unwrap()..=captures[3].parse().unwrap(), + captures[4].parse().unwrap()..=captures[5].parse().unwrap(), + captures[6].parse().unwrap()..=captures[7].parse().unwrap(), + ), + } + } + + fn contains(&self, point: &Point3D) -> Option<bool> { + if self.range.contains(point) { + Some(self.on) + } else { + None + } + } +} + +#[derive(Debug)] +pub struct Reactor { + rules: Vec<Rule>, +} + +impl Reactor { + fn parse(lines: impl Iterator<Item = String>) -> Self { + Self { + rules: lines.map(|line| Rule::parse(&line)).collect(), + } + } + + fn on(&self, point: &Point3D) -> bool { + for rule in self.rules.iter().rev() { + if let Some(on) = rule.contains(point) { + return on; + } + } + false + } +} + +pub fn parse(fh: File) -> Result<Reactor> { + Ok(Reactor::parse(parse::raw_lines(fh))) +} + +pub fn part1(reactor: Reactor) -> Result<u64> { + let mut total = 0; + for x in -50..=50 { + for y in -50..=50 { + for z in -50..=50 { + if reactor.on(&Point3D::new(x, y, z)) { + total += 1; + } + } + } + } + Ok(total) +} + +pub fn part2(reactor: Reactor) -> Result<i64> { + let mut on: HashSet<Range3D> = HashSet::new(); + for rule in reactor.rules { + let (intersected, nonintersected) = on + .into_iter() + .partition(|range| rule.range.intersects(range)); + on = nonintersected; + for range in intersected { + on.extend(range.intersected_ranges(&rule.range)); + } + if rule.on { + on.insert(rule.range); + } + } + Ok(on.iter().map(|range| range.size()).sum()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 22).unwrap()).unwrap()).unwrap(), + 570915 + ); + assert_eq!( + part2(parse(parse::data(2021, 22).unwrap()).unwrap()).unwrap(), + 1268313839428137 + ); +} diff --git a/src/bin/2021/day23.rs b/src/bin/2021/day23.rs new file mode 100644 index 0000000..c86f7c0 --- /dev/null +++ b/src/bin/2021/day23.rs @@ -0,0 +1,1736 @@ +use advent_of_code::prelude::*; + +static CONNECTIVITY1: &[&[&[usize]]] = &[ + &[ + &[], + &[1], + &[1, 2], + &[1, 2, 3], + &[1, 2, 3, 4], + &[1, 2, 3, 4, 5], + &[1, 2, 3, 4, 5, 6], + &[1, 2, 3, 4, 5, 6, 7], + &[1, 2, 3, 4, 5, 6, 7, 8], + &[1, 2, 3, 4, 5, 6, 7, 8, 9], + &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[1, 2, 11], + &[1, 2, 3, 4, 12], + &[1, 2, 3, 4, 5, 6, 13], + &[1, 2, 3, 4, 5, 6, 7, 8, 14], + &[1, 2, 11, 15], + &[1, 2, 3, 4, 12, 16], + &[1, 2, 3, 4, 5, 6, 13, 17], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[0], + &[], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[1, 0], + &[1], + &[], + &[3], + &[3, 4], + &[3, 4, 5], + &[3, 4, 5, 6], + &[3, 4, 5, 6, 7], + &[3, 4, 5, 6, 7, 8], + &[3, 4, 5, 6, 7, 8, 9], + &[3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[3, 4, 12], + &[3, 4, 5, 6, 13], + &[3, 4, 5, 6, 7, 8, 14], + &[11, 15], + &[3, 4, 12, 16], + &[3, 4, 5, 6, 13, 17], + &[3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[4, 12], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[4, 12, 16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[3, 2, 1, 0], + &[3, 2, 1], + &[3, 2], + &[3], + &[], + &[5], + &[5, 6], + &[5, 6, 7], + &[5, 6, 7, 8], + &[5, 6, 7, 8, 9], + &[5, 6, 7, 8, 9, 10], + &[3, 2, 11], + &[12], + &[5, 6, 13], + &[5, 6, 7, 8, 14], + &[3, 2, 11, 15], + &[12, 16], + &[5, 6, 13, 17], + &[5, 6, 7, 8, 14, 18], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[4, 12], + &[6, 13], + &[6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[4, 12, 16], + &[6, 13, 17], + &[6, 7, 8, 14, 18], + ], + &[ + &[5, 4, 3, 2, 1, 0], + &[5, 4, 3, 2, 1], + &[5, 4, 3, 2], + &[5, 4, 3], + &[5, 4], + &[5], + &[], + &[7], + &[7, 8], + &[7, 8, 9], + &[7, 8, 9, 10], + &[5, 4, 3, 2, 11], + &[5, 4, 12], + &[13], + &[7, 8, 14], + &[5, 4, 3, 2, 11, 15], + &[5, 4, 12, 16], + &[13, 17], + &[7, 8, 14, 18], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[], + &[8], + &[8, 9], + &[8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[6, 13], + &[8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[6, 13, 17], + &[8, 14, 18], + ], + &[ + &[7, 6, 5, 4, 3, 2, 1, 0], + &[7, 6, 5, 4, 3, 2, 1], + &[7, 6, 5, 4, 3, 2], + &[7, 6, 5, 4, 3], + &[7, 6, 5, 4], + &[7, 6, 5], + &[7, 6], + &[7], + &[], + &[9], + &[9, 10], + &[7, 6, 5, 4, 3, 2, 11], + &[7, 6, 5, 4, 12], + &[7, 6, 13], + &[14], + &[7, 6, 5, 4, 3, 2, 11, 15], + &[7, 6, 5, 4, 12, 16], + &[7, 6, 13, 17], + &[14, 18], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[], + &[10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[8, 14], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[8, 14, 18], + ], + &[ + &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[9, 8, 7, 6, 5, 4, 3, 2, 1], + &[9, 8, 7, 6, 5, 4, 3, 2], + &[9, 8, 7, 6, 5, 4, 3], + &[9, 8, 7, 6, 5, 4], + &[9, 8, 7, 6, 5], + &[9, 8, 7, 6], + &[9, 8, 7], + &[9, 8], + &[9], + &[], + &[9, 8, 7, 6, 5, 4, 3, 2, 11], + &[9, 8, 7, 6, 5, 4, 12], + &[9, 8, 7, 6, 13], + &[9, 8, 14], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[9, 8, 7, 6, 5, 4, 12, 16], + &[9, 8, 7, 6, 13, 17], + &[9, 8, 14, 18], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[], + &[6, 7, 8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[17], + &[6, 7, 8, 14, 18], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[8, 9], + &[8, 9, 10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[18], + ], + &[ + &[11, 2, 1, 0], + &[11, 2, 1], + &[11, 2], + &[11, 2, 3], + &[11, 2, 3, 4], + &[11, 2, 3, 4, 5], + &[11, 2, 3, 4, 5, 6], + &[11, 2, 3, 4, 5, 6, 7], + &[11, 2, 3, 4, 5, 6, 7, 8], + &[11, 2, 3, 4, 5, 6, 7, 8, 9], + &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[11, 2, 3, 4, 12], + &[11, 2, 3, 4, 5, 6, 13], + &[11, 2, 3, 4, 5, 6, 7, 8, 14], + &[], + &[11, 2, 3, 4, 12, 16], + &[11, 2, 3, 4, 5, 6, 13, 17], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[12, 4, 3, 2, 1, 0], + &[12, 4, 3, 2, 1], + &[12, 4, 3, 2], + &[12, 4, 3], + &[12, 4], + &[12, 4, 5], + &[12, 4, 5, 6], + &[12, 4, 5, 6, 7], + &[12, 4, 5, 6, 7, 8], + &[12, 4, 5, 6, 7, 8, 9], + &[12, 4, 5, 6, 7, 8, 9, 10], + &[12, 4, 3, 2, 11], + &[12], + &[12, 4, 5, 6, 13], + &[12, 4, 5, 6, 7, 8, 14], + &[12, 4, 3, 2, 11, 15], + &[], + &[12, 4, 5, 6, 13, 17], + &[12, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[13, 6, 5, 4, 3, 2, 1, 0], + &[13, 6, 5, 4, 3, 2, 1], + &[13, 6, 5, 4, 3, 2], + &[13, 6, 5, 4, 3], + &[13, 6, 5, 4], + &[13, 6, 5], + &[13, 6], + &[13, 6, 7], + &[13, 6, 7, 8], + &[13, 6, 7, 8, 9], + &[13, 6, 7, 8, 9, 10], + &[13, 6, 5, 4, 3, 2, 11], + &[13, 6, 5, 4, 12], + &[13], + &[13, 6, 7, 8, 14], + &[13, 6, 5, 4, 3, 2, 11, 15], + &[13, 6, 5, 4, 12, 16], + &[], + &[13, 6, 7, 8, 14, 18], + ], + &[ + &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[14, 8, 7, 6, 5, 4, 3, 2, 1], + &[14, 8, 7, 6, 5, 4, 3, 2], + &[14, 8, 7, 6, 5, 4, 3], + &[14, 8, 7, 6, 5, 4], + &[14, 8, 7, 6, 5], + &[14, 8, 7, 6], + &[14, 8, 7], + &[14, 8], + &[14, 8, 9], + &[14, 8, 9, 10], + &[14, 8, 7, 6, 5, 4, 3, 2, 11], + &[14, 8, 7, 6, 5, 4, 12], + &[14, 8, 7, 6, 13], + &[14], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[14, 8, 7, 6, 5, 4, 12, 16], + &[14, 8, 7, 6, 13, 17], + &[], + ], +]; + +static CONNECTIVITY2: &[&[&[usize]]] = &[ + &[ + &[], + &[1], + &[1, 2], + &[1, 2, 3], + &[1, 2, 3, 4], + &[1, 2, 3, 4, 5], + &[1, 2, 3, 4, 5, 6], + &[1, 2, 3, 4, 5, 6, 7], + &[1, 2, 3, 4, 5, 6, 7, 8], + &[1, 2, 3, 4, 5, 6, 7, 8, 9], + &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[1, 2, 11], + &[1, 2, 3, 4, 12], + &[1, 2, 3, 4, 5, 6, 13], + &[1, 2, 3, 4, 5, 6, 7, 8, 14], + &[1, 2, 11, 15], + &[1, 2, 3, 4, 12, 16], + &[1, 2, 3, 4, 5, 6, 13, 17], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[1, 2, 11, 15, 19], + &[1, 2, 3, 4, 12, 16, 20], + &[1, 2, 3, 4, 5, 6, 13, 17, 21], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[1, 2, 11, 15, 19, 23], + &[1, 2, 3, 4, 12, 16, 20, 24], + &[1, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[0], + &[], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + &[2, 11, 15, 19], + &[2, 3, 4, 12, 16, 20], + &[2, 3, 4, 5, 6, 13, 17, 21], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[2, 11, 15, 19, 23], + &[2, 3, 4, 12, 16, 20, 24], + &[2, 3, 4, 5, 6, 13, 17, 21, 25], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[1, 0], + &[1], + &[], + &[3], + &[3, 4], + &[3, 4, 5], + &[3, 4, 5, 6], + &[3, 4, 5, 6, 7], + &[3, 4, 5, 6, 7, 8], + &[3, 4, 5, 6, 7, 8, 9], + &[3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[3, 4, 12], + &[3, 4, 5, 6, 13], + &[3, 4, 5, 6, 7, 8, 14], + &[11, 15], + &[3, 4, 12, 16], + &[3, 4, 5, 6, 13, 17], + &[3, 4, 5, 6, 7, 8, 14, 18], + &[11, 15, 19], + &[3, 4, 12, 16, 20], + &[3, 4, 5, 6, 13, 17, 21], + &[3, 4, 5, 6, 7, 8, 14, 18, 22], + &[11, 15, 19, 23], + &[3, 4, 12, 16, 20, 24], + &[3, 4, 5, 6, 13, 17, 21, 25], + &[3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[4, 12], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[4, 12, 16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + &[2, 11, 15, 19], + &[4, 12, 16, 20], + &[4, 5, 6, 13, 17, 21], + &[4, 5, 6, 7, 8, 14, 18, 22], + &[2, 11, 15, 19, 23], + &[4, 12, 16, 20, 24], + &[4, 5, 6, 13, 17, 21, 25], + &[4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[3, 2, 1, 0], + &[3, 2, 1], + &[3, 2], + &[3], + &[], + &[5], + &[5, 6], + &[5, 6, 7], + &[5, 6, 7, 8], + &[5, 6, 7, 8, 9], + &[5, 6, 7, 8, 9, 10], + &[3, 2, 11], + &[12], + &[5, 6, 13], + &[5, 6, 7, 8, 14], + &[3, 2, 11, 15], + &[12, 16], + &[5, 6, 13, 17], + &[5, 6, 7, 8, 14, 18], + &[3, 2, 11, 15, 19], + &[12, 16, 20], + &[5, 6, 13, 17, 21], + &[5, 6, 7, 8, 14, 18, 22], + &[3, 2, 11, 15, 19, 23], + &[12, 16, 20, 24], + &[5, 6, 13, 17, 21, 25], + &[5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[4, 12], + &[6, 13], + &[6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[4, 12, 16], + &[6, 13, 17], + &[6, 7, 8, 14, 18], + &[4, 3, 2, 11, 15, 19], + &[4, 12, 16, 20], + &[6, 13, 17, 21], + &[6, 7, 8, 14, 18, 22], + &[4, 3, 2, 11, 15, 19, 23], + &[4, 12, 16, 20, 24], + &[6, 13, 17, 21, 25], + &[6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[5, 4, 3, 2, 1, 0], + &[5, 4, 3, 2, 1], + &[5, 4, 3, 2], + &[5, 4, 3], + &[5, 4], + &[5], + &[], + &[7], + &[7, 8], + &[7, 8, 9], + &[7, 8, 9, 10], + &[5, 4, 3, 2, 11], + &[5, 4, 12], + &[13], + &[7, 8, 14], + &[5, 4, 3, 2, 11, 15], + &[5, 4, 12, 16], + &[13, 17], + &[7, 8, 14, 18], + &[5, 4, 3, 2, 11, 15, 19], + &[5, 4, 12, 16, 20], + &[13, 17, 21], + &[7, 8, 14, 18, 22], + &[5, 4, 3, 2, 11, 15, 19, 23], + &[5, 4, 12, 16, 20, 24], + &[13, 17, 21, 25], + &[7, 8, 14, 18, 22, 26], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[], + &[8], + &[8, 9], + &[8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[6, 13], + &[8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[6, 13, 17], + &[8, 14, 18], + &[6, 5, 4, 3, 2, 11, 15, 19], + &[6, 5, 4, 12, 16, 20], + &[6, 13, 17, 21], + &[8, 14, 18, 22], + &[6, 5, 4, 3, 2, 11, 15, 19, 23], + &[6, 5, 4, 12, 16, 20, 24], + &[6, 13, 17, 21, 25], + &[8, 14, 18, 22, 26], + ], + &[ + &[7, 6, 5, 4, 3, 2, 1, 0], + &[7, 6, 5, 4, 3, 2, 1], + &[7, 6, 5, 4, 3, 2], + &[7, 6, 5, 4, 3], + &[7, 6, 5, 4], + &[7, 6, 5], + &[7, 6], + &[7], + &[], + &[9], + &[9, 10], + &[7, 6, 5, 4, 3, 2, 11], + &[7, 6, 5, 4, 12], + &[7, 6, 13], + &[14], + &[7, 6, 5, 4, 3, 2, 11, 15], + &[7, 6, 5, 4, 12, 16], + &[7, 6, 13, 17], + &[14, 18], + &[7, 6, 5, 4, 3, 2, 11, 15, 19], + &[7, 6, 5, 4, 12, 16, 20], + &[7, 6, 13, 17, 21], + &[14, 18, 22], + &[7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[7, 6, 5, 4, 12, 16, 20, 24], + &[7, 6, 13, 17, 21, 25], + &[14, 18, 22, 26], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[], + &[10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[8, 14], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[8, 14, 18], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[8, 7, 6, 5, 4, 12, 16, 20], + &[8, 7, 6, 13, 17, 21], + &[8, 14, 18, 22], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[8, 7, 6, 5, 4, 12, 16, 20, 24], + &[8, 7, 6, 13, 17, 21, 25], + &[8, 14, 18, 22, 26], + ], + &[ + &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[9, 8, 7, 6, 5, 4, 3, 2, 1], + &[9, 8, 7, 6, 5, 4, 3, 2], + &[9, 8, 7, 6, 5, 4, 3], + &[9, 8, 7, 6, 5, 4], + &[9, 8, 7, 6, 5], + &[9, 8, 7, 6], + &[9, 8, 7], + &[9, 8], + &[9], + &[], + &[9, 8, 7, 6, 5, 4, 3, 2, 11], + &[9, 8, 7, 6, 5, 4, 12], + &[9, 8, 7, 6, 13], + &[9, 8, 14], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[9, 8, 7, 6, 5, 4, 12, 16], + &[9, 8, 7, 6, 13, 17], + &[9, 8, 14, 18], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[9, 8, 7, 6, 5, 4, 12, 16, 20], + &[9, 8, 7, 6, 13, 17, 21], + &[9, 8, 14, 18, 22], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[9, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[9, 8, 7, 6, 13, 17, 21, 25], + &[9, 8, 14, 18, 22, 26], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + &[15, 19], + &[2, 3, 4, 12, 16, 20], + &[2, 3, 4, 5, 6, 13, 17, 21], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[15, 19, 23], + &[2, 3, 4, 12, 16, 20, 24], + &[2, 3, 4, 5, 6, 13, 17, 21, 25], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + &[4, 3, 2, 11, 15, 19], + &[16, 20], + &[4, 5, 6, 13, 17, 21], + &[4, 5, 6, 7, 8, 14, 18, 22], + &[4, 3, 2, 11, 15, 19, 23], + &[16, 20, 24], + &[4, 5, 6, 13, 17, 21, 25], + &[4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[], + &[6, 7, 8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[17], + &[6, 7, 8, 14, 18], + &[6, 5, 4, 3, 2, 11, 15, 19], + &[6, 5, 4, 12, 16, 20], + &[17, 21], + &[6, 7, 8, 14, 18, 22], + &[6, 5, 4, 3, 2, 11, 15, 19, 23], + &[6, 5, 4, 12, 16, 20, 24], + &[17, 21, 25], + &[6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[8, 9], + &[8, 9, 10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[18], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[8, 7, 6, 5, 4, 12, 16, 20], + &[8, 7, 6, 13, 17, 21], + &[18, 22], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[8, 7, 6, 5, 4, 12, 16, 20, 24], + &[8, 7, 6, 13, 17, 21, 25], + &[18, 22, 26], + ], + &[ + &[11, 2, 1, 0], + &[11, 2, 1], + &[11, 2], + &[11, 2, 3], + &[11, 2, 3, 4], + &[11, 2, 3, 4, 5], + &[11, 2, 3, 4, 5, 6], + &[11, 2, 3, 4, 5, 6, 7], + &[11, 2, 3, 4, 5, 6, 7, 8], + &[11, 2, 3, 4, 5, 6, 7, 8, 9], + &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[11, 2, 3, 4, 12], + &[11, 2, 3, 4, 5, 6, 13], + &[11, 2, 3, 4, 5, 6, 7, 8, 14], + &[], + &[11, 2, 3, 4, 12, 16], + &[11, 2, 3, 4, 5, 6, 13, 17], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[19], + &[11, 2, 3, 4, 12, 16, 20], + &[11, 2, 3, 4, 5, 6, 13, 17, 21], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[19, 23], + &[11, 2, 3, 4, 12, 16, 20, 24], + &[11, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[12, 4, 3, 2, 1, 0], + &[12, 4, 3, 2, 1], + &[12, 4, 3, 2], + &[12, 4, 3], + &[12, 4], + &[12, 4, 5], + &[12, 4, 5, 6], + &[12, 4, 5, 6, 7], + &[12, 4, 5, 6, 7, 8], + &[12, 4, 5, 6, 7, 8, 9], + &[12, 4, 5, 6, 7, 8, 9, 10], + &[12, 4, 3, 2, 11], + &[12], + &[12, 4, 5, 6, 13], + &[12, 4, 5, 6, 7, 8, 14], + &[12, 4, 3, 2, 11, 15], + &[], + &[12, 4, 5, 6, 13, 17], + &[12, 4, 5, 6, 7, 8, 14, 18], + &[12, 4, 3, 2, 11, 15, 19], + &[20], + &[12, 4, 5, 6, 13, 17, 21], + &[12, 4, 5, 6, 7, 8, 14, 18, 22], + &[12, 4, 3, 2, 11, 15, 19, 23], + &[20, 24], + &[12, 4, 5, 6, 13, 17, 21, 25], + &[12, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[13, 6, 5, 4, 3, 2, 1, 0], + &[13, 6, 5, 4, 3, 2, 1], + &[13, 6, 5, 4, 3, 2], + &[13, 6, 5, 4, 3], + &[13, 6, 5, 4], + &[13, 6, 5], + &[13, 6], + &[13, 6, 7], + &[13, 6, 7, 8], + &[13, 6, 7, 8, 9], + &[13, 6, 7, 8, 9, 10], + &[13, 6, 5, 4, 3, 2, 11], + &[13, 6, 5, 4, 12], + &[13], + &[13, 6, 7, 8, 14], + &[13, 6, 5, 4, 3, 2, 11, 15], + &[13, 6, 5, 4, 12, 16], + &[], + &[13, 6, 7, 8, 14, 18], + &[13, 6, 5, 4, 3, 2, 11, 15, 19], + &[13, 6, 5, 4, 12, 16, 20], + &[21], + &[13, 6, 7, 8, 14, 18, 22], + &[13, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[13, 6, 5, 4, 12, 16, 20, 24], + &[21, 25], + &[13, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[14, 8, 7, 6, 5, 4, 3, 2, 1], + &[14, 8, 7, 6, 5, 4, 3, 2], + &[14, 8, 7, 6, 5, 4, 3], + &[14, 8, 7, 6, 5, 4], + &[14, 8, 7, 6, 5], + &[14, 8, 7, 6], + &[14, 8, 7], + &[14, 8], + &[14, 8, 9], + &[14, 8, 9, 10], + &[14, 8, 7, 6, 5, 4, 3, 2, 11], + &[14, 8, 7, 6, 5, 4, 12], + &[14, 8, 7, 6, 13], + &[14], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[14, 8, 7, 6, 5, 4, 12, 16], + &[14, 8, 7, 6, 13, 17], + &[], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[14, 8, 7, 6, 5, 4, 12, 16, 20], + &[14, 8, 7, 6, 13, 17, 21], + &[22], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[14, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[14, 8, 7, 6, 13, 17, 21, 25], + &[22, 26], + ], + &[ + &[15, 11, 2, 1, 0], + &[15, 11, 2, 1], + &[15, 11, 2], + &[15, 11, 2, 3], + &[15, 11, 2, 3, 4], + &[15, 11, 2, 3, 4, 5], + &[15, 11, 2, 3, 4, 5, 6], + &[15, 11, 2, 3, 4, 5, 6, 7], + &[15, 11, 2, 3, 4, 5, 6, 7, 8], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[15, 11], + &[15, 11, 2, 3, 4, 12], + &[15, 11, 2, 3, 4, 5, 6, 13], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14], + &[15], + &[15, 11, 2, 3, 4, 12, 16], + &[15, 11, 2, 3, 4, 5, 6, 13, 17], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[], + &[15, 11, 2, 3, 4, 12, 16, 20], + &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[23], + &[15, 11, 2, 3, 4, 12, 16, 20, 24], + &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[16, 12, 4, 3, 2, 1, 0], + &[16, 12, 4, 3, 2, 1], + &[16, 12, 4, 3, 2], + &[16, 12, 4, 3], + &[16, 12, 4], + &[16, 12, 4, 5], + &[16, 12, 4, 5, 6], + &[16, 12, 4, 5, 6, 7], + &[16, 12, 4, 5, 6, 7, 8], + &[16, 12, 4, 5, 6, 7, 8, 9], + &[16, 12, 4, 5, 6, 7, 8, 9, 10], + &[16, 12, 4, 3, 2, 11], + &[16, 12], + &[16, 12, 4, 5, 6, 13], + &[16, 12, 4, 5, 6, 7, 8, 14], + &[16, 12, 4, 3, 2, 11, 15], + &[16], + &[16, 12, 4, 5, 6, 13, 17], + &[16, 12, 4, 5, 6, 7, 8, 14, 18], + &[16, 12, 4, 3, 2, 11, 15, 19], + &[], + &[16, 12, 4, 5, 6, 13, 17, 21], + &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22], + &[16, 12, 4, 3, 2, 11, 15, 19, 23], + &[24], + &[16, 12, 4, 5, 6, 13, 17, 21, 25], + &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[17, 13, 6, 5, 4, 3, 2, 1, 0], + &[17, 13, 6, 5, 4, 3, 2, 1], + &[17, 13, 6, 5, 4, 3, 2], + &[17, 13, 6, 5, 4, 3], + &[17, 13, 6, 5, 4], + &[17, 13, 6, 5], + &[17, 13, 6], + &[17, 13, 6, 7], + &[17, 13, 6, 7, 8], + &[17, 13, 6, 7, 8, 9], + &[17, 13, 6, 7, 8, 9, 10], + &[17, 13, 6, 5, 4, 3, 2, 11], + &[17, 13, 6, 5, 4, 12], + &[17, 13], + &[17, 13, 6, 7, 8, 14], + &[17, 13, 6, 5, 4, 3, 2, 11, 15], + &[17, 13, 6, 5, 4, 12, 16], + &[17], + &[17, 13, 6, 7, 8, 14, 18], + &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19], + &[17, 13, 6, 5, 4, 12, 16, 20], + &[], + &[17, 13, 6, 7, 8, 14, 18, 22], + &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[17, 13, 6, 5, 4, 12, 16, 20, 24], + &[25], + &[17, 13, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1], + &[18, 14, 8, 7, 6, 5, 4, 3, 2], + &[18, 14, 8, 7, 6, 5, 4, 3], + &[18, 14, 8, 7, 6, 5, 4], + &[18, 14, 8, 7, 6, 5], + &[18, 14, 8, 7, 6], + &[18, 14, 8, 7], + &[18, 14, 8], + &[18, 14, 8, 9], + &[18, 14, 8, 9, 10], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11], + &[18, 14, 8, 7, 6, 5, 4, 12], + &[18, 14, 8, 7, 6, 13], + &[18, 14], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[18, 14, 8, 7, 6, 5, 4, 12, 16], + &[18, 14, 8, 7, 6, 13, 17], + &[18], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20], + &[18, 14, 8, 7, 6, 13, 17, 21], + &[], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[18, 14, 8, 7, 6, 13, 17, 21, 25], + &[26], + ], + &[ + &[19, 15, 11, 2, 1, 0], + &[19, 15, 11, 2, 1], + &[19, 15, 11, 2], + &[19, 15, 11, 2, 3], + &[19, 15, 11, 2, 3, 4], + &[19, 15, 11, 2, 3, 4, 5], + &[19, 15, 11, 2, 3, 4, 5, 6], + &[19, 15, 11, 2, 3, 4, 5, 6, 7], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[19, 15, 11], + &[19, 15, 11, 2, 3, 4, 12], + &[19, 15, 11, 2, 3, 4, 5, 6, 13], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14], + &[19, 15], + &[19, 15, 11, 2, 3, 4, 12, 16], + &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[19], + &[19, 15, 11, 2, 3, 4, 12, 16, 20], + &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[], + &[19, 15, 11, 2, 3, 4, 12, 16, 20, 24], + &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[20, 16, 12, 4, 3, 2, 1, 0], + &[20, 16, 12, 4, 3, 2, 1], + &[20, 16, 12, 4, 3, 2], + &[20, 16, 12, 4, 3], + &[20, 16, 12, 4], + &[20, 16, 12, 4, 5], + &[20, 16, 12, 4, 5, 6], + &[20, 16, 12, 4, 5, 6, 7], + &[20, 16, 12, 4, 5, 6, 7, 8], + &[20, 16, 12, 4, 5, 6, 7, 8, 9], + &[20, 16, 12, 4, 5, 6, 7, 8, 9, 10], + &[20, 16, 12, 4, 3, 2, 11], + &[20, 16, 12], + &[20, 16, 12, 4, 5, 6, 13], + &[20, 16, 12, 4, 5, 6, 7, 8, 14], + &[20, 16, 12, 4, 3, 2, 11, 15], + &[20, 16], + &[20, 16, 12, 4, 5, 6, 13, 17], + &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18], + &[20, 16, 12, 4, 3, 2, 11, 15, 19], + &[20], + &[20, 16, 12, 4, 5, 6, 13, 17, 21], + &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22], + &[20, 16, 12, 4, 3, 2, 11, 15, 19, 23], + &[], + &[20, 16, 12, 4, 5, 6, 13, 17, 21, 25], + &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[21, 17, 13, 6, 5, 4, 3, 2, 1, 0], + &[21, 17, 13, 6, 5, 4, 3, 2, 1], + &[21, 17, 13, 6, 5, 4, 3, 2], + &[21, 17, 13, 6, 5, 4, 3], + &[21, 17, 13, 6, 5, 4], + &[21, 17, 13, 6, 5], + &[21, 17, 13, 6], + &[21, 17, 13, 6, 7], + &[21, 17, 13, 6, 7, 8], + &[21, 17, 13, 6, 7, 8, 9], + &[21, 17, 13, 6, 7, 8, 9, 10], + &[21, 17, 13, 6, 5, 4, 3, 2, 11], + &[21, 17, 13, 6, 5, 4, 12], + &[21, 17, 13], + &[21, 17, 13, 6, 7, 8, 14], + &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15], + &[21, 17, 13, 6, 5, 4, 12, 16], + &[21, 17], + &[21, 17, 13, 6, 7, 8, 14, 18], + &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19], + &[21, 17, 13, 6, 5, 4, 12, 16, 20], + &[21], + &[21, 17, 13, 6, 7, 8, 14, 18, 22], + &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[21, 17, 13, 6, 5, 4, 12, 16, 20, 24], + &[], + &[21, 17, 13, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2], + &[22, 18, 14, 8, 7, 6, 5, 4, 3], + &[22, 18, 14, 8, 7, 6, 5, 4], + &[22, 18, 14, 8, 7, 6, 5], + &[22, 18, 14, 8, 7, 6], + &[22, 18, 14, 8, 7], + &[22, 18, 14, 8], + &[22, 18, 14, 8, 9], + &[22, 18, 14, 8, 9, 10], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11], + &[22, 18, 14, 8, 7, 6, 5, 4, 12], + &[22, 18, 14, 8, 7, 6, 13], + &[22, 18, 14], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16], + &[22, 18, 14, 8, 7, 6, 13, 17], + &[22, 18], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20], + &[22, 18, 14, 8, 7, 6, 13, 17, 21], + &[22], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[22, 18, 14, 8, 7, 6, 13, 17, 21, 25], + &[], + ], +]; + +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] +enum Amphipod { + A, + B, + C, + D, +} +use Amphipod::*; + +impl Amphipod { + fn step_cost(&self) -> u64 { + match self { + A => 1, + B => 10, + C => 100, + D => 1000, + } + } +} + +impl std::str::FromStr for Amphipod { + type Err = anyhow::Error; + fn from_str(s: &str) -> std::result::Result<Self, Self::Err> { + match s { + "A" => Ok(A), + "B" => Ok(B), + "C" => Ok(C), + "D" => Ok(D), + _ => Err(anyhow::anyhow!(s.to_string())), + } + } +} + +impl std::fmt::Display for Amphipod { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> std::result::Result<(), std::fmt::Error> { + match self { + A => write!(f, "A"), + B => write!(f, "B"), + C => write!(f, "C"), + D => write!(f, "D"), + } + } +} + +// ############# +// #abcdefghijk# +// ###l#m#n#o### +// #p#q#r#s# +// ######### +#[derive(Debug, Clone, Copy, Default, Hash, PartialEq, Eq)] +pub struct Burrow { + spaces: [Option<Amphipod>; 27], + big: bool, +} + +impl Burrow { + fn to_big(self) -> Self { + let mut big = self; + + big.spaces[23] = self.spaces[15]; + big.spaces[24] = self.spaces[16]; + big.spaces[25] = self.spaces[17]; + big.spaces[26] = self.spaces[18]; + + big.spaces[15] = Some(D); + big.spaces[16] = Some(C); + big.spaces[17] = Some(B); + big.spaces[18] = Some(A); + big.spaces[19] = Some(D); + big.spaces[20] = Some(B); + big.spaces[21] = Some(A); + big.spaces[22] = Some(C); + + big.big = true; + + big + } + + fn path(&self, from: usize, to: usize) -> &[usize] { + if self.big { + CONNECTIVITY2[from][to] + } else { + CONNECTIVITY1[from][to] + } + } + + fn done(big: bool) -> Self { + let mut done = Self::default(); + + done.spaces[11] = Some(A); + done.spaces[15] = Some(A); + done.spaces[12] = Some(B); + done.spaces[16] = Some(B); + done.spaces[13] = Some(C); + done.spaces[17] = Some(C); + done.spaces[14] = Some(D); + done.spaces[18] = Some(D); + + if big { + done.spaces[19] = Some(A); + done.spaces[23] = Some(A); + done.spaces[20] = Some(B); + done.spaces[24] = Some(B); + done.spaces[21] = Some(C); + done.spaces[25] = Some(C); + done.spaces[22] = Some(D); + done.spaces[26] = Some(D); + done.big = true; + } + + done + } + + fn move_cost(&self, mv: Move) -> u64 { + self.spaces[mv.from].unwrap().step_cost() + * u64::try_from(self.path(mv.from, mv.to).len()).unwrap() + } + + fn make_move(&self, mv: Move) -> Self { + let mut new = *self; + let a = new.spaces[mv.from].take().unwrap(); + assert!(new.spaces[mv.to].is_none()); + new.spaces[mv.to] = Some(a); + new + } + + fn legal_moves(&self) -> Vec<Move> { + let mut ret = vec![]; + let size = if self.big { 27 } else { 19 }; + for (from, space) in self.spaces.iter().enumerate().take(size) { + if let Some(a) = space { + for to in 0..size { + if self.can_move(*a, from, to) { + ret.push(Move::new(from, to)); + } + } + } + } + ret + } + + fn can_move(&self, a: Amphipod, from: usize, to: usize) -> bool { + if !self.big && (from >= 19 || to >= 19) { + return false; + } + + // Amphipods will never stop on the space immediately outside any + // room. + if to == 2 || to == 4 || to == 6 || to == 8 { + return false; + } + + // Amphipods will never move from the hallway into a room unless that + // room is their destination room and that room contains no amphipods + // which do not also have that room as their own destination. + match a { + A => { + if to == 12 + || to == 13 + || to == 14 + || to == 16 + || to == 17 + || to == 18 + || to == 20 + || to == 21 + || to == 22 + || to == 24 + || to == 25 + || to == 26 + { + return false; + } + if self.big { + if to == 11 + && (self.spaces[15] != Some(A) + || self.spaces[19] != Some(A) + || self.spaces[23] != Some(A)) + { + return false; + } + if to == 15 + && (self.spaces[19] != Some(A) + || self.spaces[23] != Some(A)) + { + return false; + } + if to == 19 && self.spaces[23] != Some(A) { + return false; + } + if from == 23 + || (from == 19 && self.spaces[23] == Some(A)) + || (from == 15 + && self.spaces[23] == Some(A) + && self.spaces[19] == Some(A)) + || (from == 11 + && self.spaces[23] == Some(A) + && self.spaces[19] == Some(A) + && self.spaces[15] == Some(A)) + { + return false; + } + } else { + if to == 11 && self.spaces[15] != Some(A) { + return false; + } + if from == 15 + || (from == 11 && self.spaces[15] == Some(A)) + { + return false; + } + } + } + B => { + if to == 11 + || to == 13 + || to == 14 + || to == 15 + || to == 17 + || to == 18 + || to == 19 + || to == 21 + || to == 22 + || to == 23 + || to == 25 + || to == 26 + { + return false; + } + if self.big { + if to == 12 + && (self.spaces[16] != Some(B) + || self.spaces[20] != Some(B) + || self.spaces[24] != Some(B)) + { + return false; + } + if to == 16 + && (self.spaces[20] != Some(B) + || self.spaces[24] != Some(B)) + { + return false; + } + if to == 20 && self.spaces[24] != Some(B) { + return false; + } + if from == 24 + || (from == 20 && self.spaces[24] == Some(B)) + || (from == 16 + && self.spaces[24] == Some(B) + && self.spaces[20] == Some(B)) + || (from == 12 + && self.spaces[24] == Some(B) + && self.spaces[20] == Some(B) + && self.spaces[16] == Some(B)) + { + return false; + } + } else { + if to == 12 && self.spaces[16] != Some(B) { + return false; + } + if from == 16 + || (from == 12 && self.spaces[16] == Some(B)) + { + return false; + } + } + } + C => { + if to == 11 + || to == 12 + || to == 14 + || to == 15 + || to == 16 + || to == 18 + || to == 19 + || to == 20 + || to == 22 + || to == 23 + || to == 24 + || to == 26 + { + return false; + } + if self.big { + if to == 13 + && (self.spaces[17] != Some(C) + || self.spaces[21] != Some(C) + || self.spaces[25] != Some(C)) + { + return false; + } + if to == 17 + && (self.spaces[21] != Some(C) + || self.spaces[25] != Some(C)) + { + return false; + } + if to == 21 && self.spaces[25] != Some(C) { + return false; + } + if from == 25 + || (from == 21 && self.spaces[25] == Some(C)) + || (from == 17 + && self.spaces[25] == Some(C) + && self.spaces[21] == Some(C)) + || (from == 13 + && self.spaces[25] == Some(C) + && self.spaces[21] == Some(C) + && self.spaces[17] == Some(C)) + { + return false; + } + } else { + if to == 13 && self.spaces[17] != Some(C) { + return false; + } + if from == 17 + || (from == 13 && self.spaces[17] == Some(C)) + { + return false; + } + } + } + D => { + if to == 11 + || to == 12 + || to == 13 + || to == 15 + || to == 16 + || to == 17 + || to == 19 + || to == 20 + || to == 21 + || to == 23 + || to == 24 + || to == 25 + { + return false; + } + if self.big { + if to == 14 + && (self.spaces[18] != Some(D) + || self.spaces[22] != Some(D) + || self.spaces[26] != Some(D)) + { + return false; + } + if to == 18 + && (self.spaces[22] != Some(D) + || self.spaces[26] != Some(D)) + { + return false; + } + if to == 22 && self.spaces[26] != Some(D) { + return false; + } + if from == 26 + || (from == 22 && self.spaces[26] == Some(D)) + || (from == 18 + && self.spaces[26] == Some(D) + && self.spaces[22] == Some(D)) + || (from == 14 + && self.spaces[26] == Some(D) + && self.spaces[22] == Some(D) + && self.spaces[18] == Some(D)) + { + return false; + } + } else { + if to == 14 && self.spaces[18] != Some(D) { + return false; + } + if from == 18 + || (from == 14 && self.spaces[18] == Some(D)) + { + return false; + } + } + } + } + + // Once an amphipod stops moving in the hallway, it will stay in that + // spot until it can move into a room. + if from < 11 && to < 11 { + return false; + } + + // not actually a move + if from == to { + return false; + } + + // we don't have an unblocked path + for space in self.path(from, to) { + if self.spaces[*space].is_some() { + return false; + } + } + + true + } +} + +impl std::fmt::Display for Burrow { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> std::result::Result<(), std::fmt::Error> { + writeln!(f, "#############")?; + + write!(f, "#")?; + for i in 0..11 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}", a)?; + } else { + write!(f, ".")?; + } + } + writeln!(f, "#")?; + + write!(f, "###")?; + for i in 11..15 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f, "##")?; + + write!(f, " #")?; + for i in 15..19 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f)?; + + if self.big { + write!(f, " #")?; + for i in 19..23 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f)?; + write!(f, " #")?; + for i in 23..27 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f)?; + } + + write!(f, " #########")?; + + Ok(()) + } +} + +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] +struct Move { + from: usize, + to: usize, +} + +impl Move { + fn new(from: usize, to: usize) -> Self { + Self { from, to } + } +} + +struct Pathfinder; + +impl advent_of_code::graph::Graph<Burrow, Move> for Pathfinder { + type Edges = Vec<Move>; + + fn edges(&self, v: Burrow) -> Self::Edges { + v.legal_moves() + } + + fn edge(&self, v: Burrow, e: Move) -> (Burrow, u64) { + (v.make_move(e), v.move_cost(e)) + } +} + +pub fn parse(fh: File) -> Result<Burrow> { + let mut burrow = Burrow::default(); + let lines: Vec<_> = parse::raw_lines(fh).collect(); + + let captures = + regex_captures!(r"###(.)#(.)#(.)#(.)###", &lines[2]).unwrap(); + burrow.spaces[11] = Some(captures[1].parse()?); + burrow.spaces[12] = Some(captures[2].parse()?); + burrow.spaces[13] = Some(captures[3].parse()?); + burrow.spaces[14] = Some(captures[4].parse()?); + + let captures = + regex_captures!(r" #(.)#(.)#(.)#(.)#", &lines[3]).unwrap(); + burrow.spaces[15] = Some(captures[1].parse()?); + burrow.spaces[16] = Some(captures[2].parse()?); + burrow.spaces[17] = Some(captures[3].parse()?); + burrow.spaces[18] = Some(captures[4].parse()?); + + Ok(burrow) +} + +pub fn part1(burrow: Burrow) -> Result<u64> { + let (cost, _path) = Pathfinder.dijkstra(burrow, Burrow::done(false)); + // for burrow in path { + // eprintln!("{}", burrow); + // } + Ok(cost) +} + +pub fn part2(burrow: Burrow) -> Result<u64> { + let (cost, _path) = + Pathfinder.dijkstra(burrow.to_big(), Burrow::done(true)); + // for burrow in path { + // eprintln!("{}", burrow); + // } + Ok(cost) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(), + 10607 + ); + assert_eq!( + part2(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(), + 59071 + ); +} diff --git a/src/bin/2021/day24.rs b/src/bin/2021/day24.rs new file mode 100644 index 0000000..54788ec --- /dev/null +++ b/src/bin/2021/day24.rs @@ -0,0 +1,337 @@ +use advent_of_code::prelude::*; + +#[derive(Debug, Clone, Copy)] +pub enum Op { + Inp(Register), + Add(Register, Value), + Mul(Register, Value), + Div(Register, Value), + Mod(Register, Value), + Eql(Register, Value), +} + +#[derive(Debug, Clone, Copy)] +pub enum Register { + W, + X, + Y, + Z, +} +use Register::*; + +impl Register { + fn lvalue<'a>(&self, alu: &'a mut Alu) -> &'a mut i64 { + match self { + W => &mut alu.w, + X => &mut alu.x, + Y => &mut alu.y, + Z => &mut alu.z, + } + } + + fn rvalue(&self, alu: &Alu) -> i64 { + match self { + W => alu.w, + X => alu.x, + Y => alu.y, + Z => alu.z, + } + } +} + +impl std::str::FromStr for Register { + type Err = anyhow::Error; + fn from_str(s: &str) -> std::result::Result<Self, Self::Err> { + match s { + "w" => Ok(W), + "x" => Ok(X), + "y" => Ok(Y), + "z" => Ok(Z), + _ => Err(anyhow::anyhow!(s.to_string())), + } + } +} + +#[derive(Debug, Clone, Copy)] +pub enum Value { + Register(Register), + Number(i64), +} + +impl Value { + fn rvalue(&self, alu: &Alu) -> i64 { + match self { + Self::Register(r) => r.rvalue(alu), + Self::Number(n) => *n, + } + } +} + +impl std::str::FromStr for Value { + type Err = anyhow::Error; + fn from_str(s: &str) -> std::result::Result<Self, Self::Err> { + match s { + "w" => Ok(Self::Register(W)), + "x" => Ok(Self::Register(X)), + "y" => Ok(Self::Register(Y)), + "z" => Ok(Self::Register(Z)), + _ => Ok(Self::Number(s.parse()?)), + } + } +} + +#[derive(Debug)] +pub struct Alu { + w: i64, + x: i64, + y: i64, + z: i64, +} + +impl Alu { + fn new() -> Self { + Self { + w: 0, + x: 0, + y: 0, + z: 0, + } + } + + fn run(&mut self, ops: impl IntoIterator<Item = Op>, inp: i64) { + self.inp(W, Value::Number(inp)); + for op in ops { + match op { + Op::Inp(_) => { + break; + } + Op::Add(a, b) => { + self.add(a, b); + } + Op::Mul(a, b) => { + self.mul(a, b); + } + Op::Div(a, b) => { + self.div(a, b); + } + Op::Mod(a, b) => { + self.modulo(a, b); + } + Op::Eql(a, b) => { + self.eql(a, b); + } + } + } + } + + fn inp(&mut self, a: Register, b: Value) { + *a.lvalue(self) = b.rvalue(self) + } + + fn add(&mut self, a: Register, b: Value) { + *a.lvalue(self) += b.rvalue(self); + } + + fn mul(&mut self, a: Register, b: Value) { + *a.lvalue(self) *= b.rvalue(self); + } + + fn div(&mut self, a: Register, b: Value) { + *a.lvalue(self) /= b.rvalue(self); + } + + fn modulo(&mut self, a: Register, b: Value) { + *a.lvalue(self) %= b.rvalue(self); + } + + fn eql(&mut self, a: Register, b: Value) { + *a.lvalue(self) = i64::from(a.rvalue(self) == b.rvalue(self)); + } +} + +impl std::fmt::Display for Alu { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> std::result::Result<(), std::fmt::Error> { + writeln!(f, "Alu {{")?; + writeln!(f, " w: {}", self.w)?; + writeln!(f, " x: {}", self.x)?; + writeln!(f, " y: {}", self.y)?; + writeln!(f, " z: {}", self.z)?; + write!(f, "}}")?; + Ok(()) + } +} + +fn step( + alu: &mut Alu, + ops: &mut impl Iterator<Item = Op>, + val: &mut i64, + inp: i64, +) -> bool { + if !(1..=9).contains(&inp) { + return false; + } + *val *= 10; + *val += inp; + alu.run(ops, inp); + true +} + +fn run(inp: &[i64], ops: &[Op]) -> Option<i64> { + let mut val = 0; + let mut alu = Alu::new(); + let mut ops = ops.iter().copied().skip(1); + let mut ops = ops.by_ref(); + + if !step(&mut alu, &mut ops, &mut val, inp[0]) { + return None; + } + if !step(&mut alu, &mut ops, &mut val, inp[1]) { + return None; + } + if !step(&mut alu, &mut ops, &mut val, inp[2]) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, (z % 26) - 6) { + return None; + } + if !step(&mut alu, &mut ops, &mut val, inp[3]) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, (z % 26) - 4) { + return None; + } + if !step(&mut alu, &mut ops, &mut val, inp[4]) { + return None; + } + if !step(&mut alu, &mut ops, &mut val, inp[5]) { + return None; + } + if !step(&mut alu, &mut ops, &mut val, inp[6]) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, z % 26) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, z % 26) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, (z % 26) - 3) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, (z % 26) - 9) { + return None; + } + let z = alu.z; + if !step(&mut alu, &mut ops, &mut val, (z % 26) - 9) { + return None; + } + + if alu.z == 0 { + Some(val) + } else { + None + } +} + +pub fn parse(fh: File) -> Result<impl Iterator<Item = Op>> { + Ok(parse::raw_lines(fh).map(|line| { + let captures = regex_captures!( + r"(inp|add|mul|div|mod|eql) ([wxyz])(?: ([wxyz]|-?\d+))?", + &line + ) + .unwrap(); + match &captures[1] { + "inp" => Op::Inp(captures[2].parse().unwrap()), + "add" => Op::Add( + captures[2].parse().unwrap(), + captures[3].parse().unwrap(), + ), + "mul" => Op::Mul( + captures[2].parse().unwrap(), + captures[3].parse().unwrap(), + ), + "div" => Op::Div( + captures[2].parse().unwrap(), + captures[3].parse().unwrap(), + ), + "mod" => Op::Mod( + captures[2].parse().unwrap(), + captures[3].parse().unwrap(), + ), + "eql" => Op::Eql( + captures[2].parse().unwrap(), + captures[3].parse().unwrap(), + ), + _ => panic!("unknown opcode: {}", &captures[1]), + } + })) +} + +pub fn part1(ops: impl Iterator<Item = Op>) -> Result<i64> { + let ops: Vec<_> = ops.collect(); + for d1 in (1..=9).rev() { + for d2 in (1..=9).rev() { + for d3 in (1..=9).rev() { + for d5 in (1..=9).rev() { + for d7 in (1..=9).rev() { + for d8 in (1..=9).rev() { + for d9 in (1..=9).rev() { + let inp = &[d1, d2, d3, d5, d7, d8, d9]; + let ret = run(inp, &ops); + if let Some(n) = ret { + return Ok(n); + } + } + } + } + } + } + } + } + panic!("not found"); +} + +pub fn part2(ops: impl Iterator<Item = Op>) -> Result<i64> { + let ops: Vec<_> = ops.collect(); + for d1 in 1..=9 { + for d2 in 1..=9 { + for d3 in 1..=9 { + for d5 in 1..=9 { + for d7 in 1..=9 { + for d8 in 1..=9 { + for d9 in 1..=9 { + let inp = &[d1, d2, d3, d5, d7, d8, d9]; + let ret = run(inp, &ops); + if let Some(n) = ret { + return Ok(n); + } + } + } + } + } + } + } + } + panic!("not found"); +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 24).unwrap()).unwrap()).unwrap(), + 99299513899971 + ); + assert_eq!( + part2(parse(parse::data(2021, 24).unwrap()).unwrap()).unwrap(), + 93185111127911 + ); +} diff --git a/src/bin/2021/day25.rs b/src/bin/2021/day25.rs new file mode 100644 index 0000000..ed396c6 --- /dev/null +++ b/src/bin/2021/day25.rs @@ -0,0 +1,96 @@ +use advent_of_code::prelude::*; + +#[derive(Debug, Clone, Eq, PartialEq)] +pub enum Cell { + Down, + Right, + None, +} + +impl Default for Cell { + fn default() -> Self { + Self::None + } +} + +#[derive(Debug, Clone, Eq, PartialEq)] +pub struct Map { + grid: Grid<Cell>, +} + +impl Map { + fn step(&self) -> Self { + self.step_east().step_south() + } + + fn step_east(&self) -> Self { + let mut step = self.clone(); + for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() { + if *cell == Cell::Right { + let mut next = col + 1; + if next >= self.grid.cols().0 { + next = 0; + } + if self.grid[Row(row)][Col(next)] == Cell::None { + step.grid[Row(row)][Col(next)] = Cell::Right; + step.grid[Row(row)][Col(col)] = Cell::None; + } + } + } + step + } + + fn step_south(&self) -> Self { + let mut step = self.clone(); + for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() { + if *cell == Cell::Down { + let mut next = row + 1; + if next >= self.grid.rows().0 { + next = 0; + } + if self.grid[Row(next)][Col(col)] == Cell::None { + step.grid[Row(next)][Col(col)] = Cell::Down; + step.grid[Row(row)][Col(col)] = Cell::None; + } + } + } + step + } +} + +pub fn parse(fh: File) -> Result<Map> { + Ok(Map { + grid: parse::grid(parse::raw_lines(fh), |b| match b { + b'v' => Cell::Down, + b'>' => Cell::Right, + b'.' => Cell::None, + _ => panic!("unknown cell {}", b), + }), + }) +} + +pub fn part1(map: Map) -> Result<u64> { + let mut prev = map; + let mut i = 0; + loop { + i += 1; + let next = prev.step(); + if next == prev { + break; + } + prev = next; + } + Ok(i) +} + +pub fn part2(_: Map) -> Result<i64> { + todo!() +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 25).unwrap()).unwrap()).unwrap(), + 482 + ); +} diff --git a/src/bin/2021/day3.rs b/src/bin/2021/day3.rs new file mode 100644 index 0000000..70a3085 --- /dev/null +++ b/src/bin/2021/day3.rs @@ -0,0 +1,102 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result<impl Iterator<Item = String>> { + Ok(parse::raw_lines(fh)) +} + +pub fn part1(lines: impl Iterator<Item = String>) -> Result<u64> { + let (total_lines, by_pos) = pos_counts(lines)?; + let gamma: String = by_pos + .iter() + .map(|pos| if pos * 2 >= total_lines { '1' } else { '0' }) + .collect(); + let epsilon: String = by_pos + .iter() + .map(|pos| if pos * 2 >= total_lines { '0' } else { '1' }) + .collect(); + Ok(bin_str_to_int(&gamma) * bin_str_to_int(&epsilon)) +} + +pub fn part2(lines: impl Iterator<Item = String>) -> Result<u64> { + let mut oxygen: Vec<_> = lines.collect(); + let mut co2 = oxygen.clone(); + + for i in 0..oxygen[0].len() { + if oxygen.len() == 1 { + break; + } + let (total_lines, by_pos) = pos_counts(oxygen.iter().cloned())?; + let keep = if by_pos[i] * 2 >= total_lines { + '1' + } else { + '0' + }; + let new_oxygen = oxygen + .iter() + .filter(|l| l.chars().nth(i).unwrap() == keep) + .cloned() + .collect(); + oxygen = new_oxygen; + } + + for i in 0..co2[0].len() { + if co2.len() == 1 { + break; + } + let (total_lines, by_pos) = pos_counts(co2.iter().cloned())?; + let keep = if by_pos[i] * 2 >= total_lines { + '0' + } else { + '1' + }; + let new_co2 = co2 + .iter() + .filter(|l| l.chars().nth(i).unwrap() == keep) + .cloned() + .collect(); + co2 = new_co2; + } + + Ok(bin_str_to_int(&oxygen[0]) * bin_str_to_int(&co2[0])) +} + +fn pos_counts( + lines: impl Iterator<Item = String>, +) -> Result<(i64, Vec<i64>)> { + let mut by_pos = vec![]; + let mut total_lines = 0; + for line in lines { + total_lines += 1; + if by_pos.is_empty() { + by_pos.resize(line.len(), 0); + } + for (i, c) in line.chars().enumerate() { + if c == '1' { + by_pos[i] += 1; + } + } + } + Ok((total_lines, by_pos)) +} + +fn bin_str_to_int(s: &str) -> u64 { + let mut ret = 0; + for (i, c) in s.chars().rev().enumerate() { + if c == '1' { + ret += 2u64.pow(i.try_into().unwrap()); + } + } + ret +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 3).unwrap()).unwrap()).unwrap(), + 3009600 + ); + assert_eq!( + part2(parse(parse::data(2021, 3).unwrap()).unwrap()).unwrap(), + 6940518 + ); +} diff --git a/src/bin/2021/day4.rs b/src/bin/2021/day4.rs new file mode 100644 index 0000000..f733078 --- /dev/null +++ b/src/bin/2021/day4.rs @@ -0,0 +1,167 @@ +use advent_of_code::prelude::*; + +#[derive(Debug)] +struct Board { + numbers: Vec<u8>, + marked: Vec<bool>, +} + +impl Board { + fn new(numbers: Vec<u8>) -> Self { + let len = numbers.len(); + Self { + numbers, + marked: vec![false; len], + } + } + + fn won(&self) -> bool { + let wins = [ + [0, 1, 2, 3, 4], + [5, 6, 7, 8, 9], + [10, 11, 12, 13, 14], + [15, 16, 17, 18, 19], + [20, 21, 22, 23, 24], + [0, 5, 10, 15, 20], + [1, 6, 11, 16, 21], + [2, 7, 12, 17, 22], + [3, 8, 13, 18, 23], + [4, 9, 14, 19, 24], + ]; + wins.iter().any(|win| win.iter().all(|i| self.marked[*i])) + } + + fn mark(&mut self, called: u8) { + for (i, n) in self.numbers.iter().enumerate() { + if called == *n { + self.marked[i] = true; + } + } + } + + fn value(&self) -> u64 { + self.marked + .iter() + .zip(self.numbers.iter()) + .filter_map( + |(marked, n)| { + if !*marked { + Some(u64::from(*n)) + } else { + None + } + }, + ) + .sum() + } +} + +#[derive(Debug)] +pub struct Game { + inputs: Vec<u8>, + boards: Vec<Board>, +} + +impl Game { + fn parse<T: std::io::Read>(input: T) -> Result<Self> { + let mut lines = parse::raw_lines(input).peekable(); + + let line = lines.next().ok_or_else(|| anyhow!("missing line"))?; + let inputs = line + .trim() + .split(',') + .map(|s| s.parse()) + .collect::<Result<Vec<u8>, _>>()?; + lines.next(); + + let mut boards = vec![]; + while lines.peek().is_some() { + let mut numbers = vec![]; + for line in parse::chunk(&mut lines) { + numbers.extend( + line.split_whitespace() + .map(|s| s.parse()) + .collect::<Result<Vec<u8>, _>>()?, + ); + } + boards.push(Board::new(numbers)); + } + + Ok(Self { inputs, boards }) + } + + fn find_first_winner(self) -> Option<(u8, Board)> { + let Self { inputs, mut boards } = self; + let mut won = None; + for n in inputs { + for (i, board) in boards.iter_mut().enumerate() { + board.mark(n); + if board.won() { + won = Some((n, i)); + break; + } + } + if won.is_some() { + break; + } + } + won.map(|(n, i)| (n, boards.swap_remove(i))) + } + + fn find_last_winner(self) -> Option<(u8, Board)> { + let Self { inputs, mut boards } = self; + let mut last_won = None; + for n in inputs { + let mut won = vec![]; + for (i, board) in boards.iter_mut().enumerate() { + board.mark(n); + if board.won() { + won.push(i); + } + } + if boards.len() == won.len() { + last_won = Some((n, won[0])); + break; + } + for i in won.into_iter().rev() { + boards.swap_remove(i); + } + if boards.is_empty() { + break; + } + } + last_won.map(|(n, i)| (n, boards.swap_remove(i))) + } +} + +pub fn parse(fh: File) -> Result<Game> { + Game::parse(fh) +} + +pub fn part1(game: Game) -> Result<u64> { + if let Some((n, board)) = game.find_first_winner() { + Ok(u64::from(n) * board.value()) + } else { + bail!("couldn't find winner") + } +} + +pub fn part2(game: Game) -> Result<u64> { + if let Some((n, board)) = game.find_last_winner() { + Ok(u64::from(n) * board.value()) + } else { + bail!("couldn't find winner") + } +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 4).unwrap()).unwrap()).unwrap(), + 2745 + ); + assert_eq!( + part2(parse(parse::data(2021, 4).unwrap()).unwrap()).unwrap(), + 6594 + ); +} diff --git a/src/bin/2021/day5.rs b/src/bin/2021/day5.rs new file mode 100644 index 0000000..68bca56 --- /dev/null +++ b/src/bin/2021/day5.rs @@ -0,0 +1,123 @@ +use advent_of_code::prelude::*; + +#[derive(Default, Clone)] +struct Map { + grid: Grid<i64>, +} + +impl Map { + fn mark_horizontal( + &mut self, + x1: usize, + y1: usize, + x2: usize, + y2: usize, + ) -> bool { + self.grid + .grow(Row((y1 + 1).max(y2 + 1)), Col((x1 + 1).max(x2 + 1))); + if x1 == x2 { + for y in y1.min(y2)..=y1.max(y2) { + self.grid[Row(y)][Col(x1)] += 1; + } + true + } else { + false + } + } + + fn mark_vertical( + &mut self, + x1: usize, + y1: usize, + x2: usize, + y2: usize, + ) -> bool { + self.grid + .grow(Row((y1 + 1).max(y2 + 1)), Col((x1 + 1).max(x2 + 1))); + if y1 == y2 { + for x in x1.min(x2)..=x1.max(x2) { + self.grid[Row(y1)][Col(x)] += 1; + } + true + } else { + false + } + } + + fn mark_diagonal( + &mut self, + x1: usize, + y1: usize, + x2: usize, + y2: usize, + ) -> bool { + if x1.max(x2) - x1.min(x2) == y1.max(y2) - y1.min(y2) { + for i in 0..=(x1.max(x2) - x1.min(x2)) { + if x1 > x2 && y1 > y2 || x1 < x2 && y1 < y2 { + self.grid[Row(y1.min(y2) + i)][Col(x1.min(x2) + i)] += 1; + } else if x1 > x2 { + self.grid[Row(y2 - i)][Col(x2 + i)] += 1; + } else { + self.grid[Row(y1 - i)][Col(x1 + i)] += 1; + } + } + true + } else { + false + } + } + + fn count_overlapping(&self) -> usize { + self.grid.cells().filter(|x| **x >= 2).count() + } +} + +pub fn parse(fh: File) -> Result<impl Iterator<Item = Vec<usize>>> { + Ok(parse::raw_lines(fh).map(move |line| { + regex_captures!(r"^(\d+),(\d+) -> (\d+),(\d+)$", &line) + .unwrap() + .iter() + .skip(1) + .map(|s| s.unwrap().as_str().parse()) + .collect::<Result<_, _>>() + .unwrap() + })) +} + +pub fn part1(coords: impl Iterator<Item = Vec<usize>>) -> Result<usize> { + let mut map = Map::default(); + for nums in coords { + let _ = map.mark_horizontal(nums[0], nums[1], nums[2], nums[3]) + || map.mark_vertical(nums[0], nums[1], nums[2], nums[3]); + } + Ok(map.count_overlapping()) +} + +pub fn part2(coords: impl Iterator<Item = Vec<usize>>) -> Result<usize> { + let mut map = Map::default(); + for nums in coords { + if map.mark_horizontal(nums[0], nums[1], nums[2], nums[3]) { + continue; + } + if map.mark_vertical(nums[0], nums[1], nums[2], nums[3]) { + continue; + } + if map.mark_diagonal(nums[0], nums[1], nums[2], nums[3]) { + continue; + } + unreachable!(); + } + Ok(map.count_overlapping()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 5).unwrap()).unwrap()).unwrap(), + 6311 + ); + assert_eq!( + part2(parse(parse::data(2021, 5).unwrap()).unwrap()).unwrap(), + 19929 + ); +} diff --git a/src/bin/2021/day6.rs b/src/bin/2021/day6.rs new file mode 100644 index 0000000..039209e --- /dev/null +++ b/src/bin/2021/day6.rs @@ -0,0 +1,47 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result<Vec<usize>> { + Ok(parse::split(fh, b',').collect()) +} + +pub fn part1(mut fishes: Vec<usize>) -> Result<usize> { + for _ in 0..80 { + let mut new = 0; + for fish in fishes.iter_mut() { + if *fish == 0 { + *fish = 6; + new += 1; + } else { + *fish -= 1; + } + } + fishes.resize(fishes.len() + new, 8); + } + Ok(fishes.len()) +} + +pub fn part2(fishes: Vec<usize>) -> Result<usize> { + let mut by_age = VecDeque::new(); + by_age.resize(9, 0); + for fish in fishes { + by_age[fish] += 1; + } + for _ in 0..256 { + let new = by_age.pop_front().unwrap(); + by_age[6] += new; + by_age.push_back(new); + } + Ok(by_age.iter().sum()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 6).unwrap()).unwrap()).unwrap(), + 379114 + ); + assert_eq!( + part2(parse(parse::data(2021, 6).unwrap()).unwrap()).unwrap(), + 1702631502303 + ); +} diff --git a/src/bin/2021/day7.rs b/src/bin/2021/day7.rs new file mode 100644 index 0000000..56eaeb1 --- /dev/null +++ b/src/bin/2021/day7.rs @@ -0,0 +1,42 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result<Vec<usize>> { + Ok(parse::split(fh, b',').collect()) +} + +pub fn part1(crabs: Vec<usize>) -> Result<usize> { + Ok((0..=crabs.iter().copied().max().unwrap()) + .map(|start| { + crabs.iter().copied().map(|crab| crab.abs_diff(start)).sum() + }) + .min() + .unwrap()) +} + +pub fn part2(crabs: Vec<usize>) -> Result<usize> { + Ok((0..=crabs.iter().copied().max().unwrap()) + .map(|start| { + crabs + .iter() + .copied() + .map(|crab| { + let diff = crab.abs_diff(start); + diff * (diff + 1) / 2 + }) + .sum() + }) + .min() + .unwrap()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 7).unwrap()).unwrap()).unwrap(), + 333755 + ); + assert_eq!( + part2(parse(parse::data(2021, 7).unwrap()).unwrap()).unwrap(), + 94017638 + ); +} diff --git a/src/bin/2021/day8.rs b/src/bin/2021/day8.rs new file mode 100644 index 0000000..ca101ef --- /dev/null +++ b/src/bin/2021/day8.rs @@ -0,0 +1,185 @@ +use advent_of_code::prelude::*; + +pub fn parse( + fh: File, +) -> Result<impl Iterator<Item = (Vec<String>, Vec<String>)>> { + Ok(parse::raw_lines(fh).map(|line| { + let parts: Vec<_> = line.split(" | ").collect(); + ( + parts[0].split(' ').map(str::to_string).collect(), + parts[1].split(' ').map(str::to_string).collect(), + ) + })) +} + +pub fn part1( + lines: impl Iterator<Item = (Vec<String>, Vec<String>)>, +) -> Result<usize> { + let mut count = 0; + for (_, output) in lines { + let line_count = output + .iter() + .filter(|s| [2, 3, 4, 7].contains(&s.len())) + .count(); + count += line_count; + } + Ok(count) +} + +// 00 +// 1 2 +// 1 2 +// 33 +// 4 5 +// 4 5 +// 66 +pub fn part2( + lines: impl Iterator<Item = (Vec<String>, Vec<String>)>, +) -> Result<usize> { + let mut total = 0; + for (numbers, output) in lines { + let mut segments = ['x'; 7]; + + // zero: 6 + let one = numbers.iter().find(|s| s.len() == 2).unwrap(); + let one: HashSet<char> = one.chars().collect(); + // two: 5 + // three: 5 + let four = numbers.iter().find(|s| s.len() == 4).unwrap(); + let four: HashSet<char> = four.chars().collect(); + // five: 5 + // six: 6 + let seven = numbers.iter().find(|s| s.len() == 3).unwrap(); + let seven: HashSet<char> = seven.chars().collect(); + let eight = numbers.iter().find(|s| s.len() == 7).unwrap(); + let eight: HashSet<char> = eight.chars().collect(); + // nine: 6 + + let mut length_five: Vec<_> = numbers + .iter() + .filter_map(|s| { + if s.len() == 5 { + Some(s.chars().collect::<HashSet<_>>()) + } else { + None + } + }) + .collect(); + let mut length_six: Vec<_> = numbers + .iter() + .filter_map(|s| { + if s.len() == 6 { + Some(s.chars().collect::<HashSet<_>>()) + } else { + None + } + }) + .collect(); + + let idx = length_five + .iter() + .position(|set| set.difference(&one).count() == 3) + .unwrap(); + let three = length_five.swap_remove(idx); + let idx = length_five + .iter() + .position(|set| set.difference(&four).count() == 2) + .unwrap(); + let five = length_five.swap_remove(idx); + let two = length_five.remove(0); + + segments[0] = *seven.difference(&one).next().unwrap(); + segments[6] = three + .iter() + .copied() + .find(|c| { + !one.contains(c) && !four.contains(c) && !seven.contains(c) + }) + .unwrap(); + segments[3] = three + .iter() + .copied() + .find(|c| { + !one.contains(c) && *c != segments[0] && *c != segments[6] + }) + .unwrap(); + segments[4] = two + .iter() + .copied() + .find(|c| { + !one.contains(c) + && *c != segments[0] + && *c != segments[3] + && *c != segments[6] + }) + .unwrap(); + segments[2] = two + .iter() + .copied() + .find(|c| { + *c != segments[0] + && *c != segments[3] + && *c != segments[4] + && *c != segments[6] + }) + .unwrap(); + segments[1] = four + .iter() + .copied() + .find(|c| !one.contains(c) && *c != segments[3]) + .unwrap(); + segments[5] = eight + .iter() + .copied() + .find(|c| { + *c != segments[0] + && *c != segments[1] + && *c != segments[2] + && *c != segments[3] + && *c != segments[4] + && *c != segments[6] + }) + .unwrap(); + + let idx = length_six + .iter() + .position(|set| !set.contains(&segments[3])) + .unwrap(); + let zero = length_six.swap_remove(idx); + let idx = length_six + .iter() + .position(|set| !set.contains(&segments[2])) + .unwrap(); + let six = length_six.swap_remove(idx); + let idx = length_six + .iter() + .position(|set| !set.contains(&segments[4])) + .unwrap(); + let nine = length_six.swap_remove(idx); + + let numbers = + [zero, one, two, three, four, five, six, seven, eight, nine]; + + let value: Vec<_> = output + .iter() + .map(|s| s.chars().collect::<HashSet<_>>()) + .map(|set| numbers.iter().position(|num| &set == num).unwrap()) + .collect(); + let value = + value[0] * 1000 + value[1] * 100 + value[2] * 10 + value[3]; + total += value; + } + Ok(total) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 8).unwrap()).unwrap()).unwrap(), + 355 + ); + assert_eq!( + part2(parse(parse::data(2021, 8).unwrap()).unwrap()).unwrap(), + 983030 + ); +} diff --git a/src/bin/2021/day9.rs b/src/bin/2021/day9.rs new file mode 100644 index 0000000..c0c1b47 --- /dev/null +++ b/src/bin/2021/day9.rs @@ -0,0 +1,71 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result<Grid<u8>> { + Ok(parse::digit_grid(parse::raw_lines(fh))) +} + +pub fn part1(map: Grid<u8>) -> Result<u64> { + let mut risk = 0; + for ((row, col), pos) in map.indexed_cells() { + if map + .adjacent(row, col, false) + .map(|(row, col)| map[row][col]) + .all(|n| *pos < n) + { + risk += 1 + u64::from(*pos); + } + } + Ok(risk) +} + +pub fn part2(map: Grid<u8>) -> Result<u64> { + let mut low = vec![]; + for ((row, col), pos) in map.indexed_cells() { + if map + .adjacent(row, col, false) + .map(|(row, col)| map[row][col]) + .all(|n| *pos < n) + { + low.push((row, col)); + } + } + + let mut sizes = vec![]; + for (row, col) in low { + let mut basin: Grid<bool> = Grid::default(); + basin.grow(map.rows(), map.cols()); + let mut check = vec![(row, col)]; + let mut count = 0; + while let Some((row, col)) = check.pop() { + if basin[row][col] || map[row][col] == 9 { + continue; + } + + basin[row][col] = true; + count += 1; + + for (row, col) in basin.adjacent(row, col, false) { + if !basin[row][col] { + check.push((row, col)); + } + } + } + sizes.push(count); + } + sizes.sort_unstable(); + Ok(sizes[sizes.len() - 1] + * sizes[sizes.len() - 2] + * sizes[sizes.len() - 3]) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 9).unwrap()).unwrap()).unwrap(), + 570 + ); + assert_eq!( + part2(parse(parse::data(2021, 9).unwrap()).unwrap()).unwrap(), + 899392 + ); +} diff --git a/src/bin/2021/main.rs b/src/bin/2021/main.rs new file mode 100644 index 0000000..1d571dc --- /dev/null +++ b/src/bin/2021/main.rs @@ -0,0 +1,74 @@ +#![allow(clippy::cognitive_complexity)] +#![allow(clippy::missing_const_for_fn)] +#![allow(clippy::similar_names)] +#![allow(clippy::struct_excessive_bools)] +#![allow(clippy::too_many_arguments)] +#![allow(clippy::too_many_lines)] +#![allow(clippy::type_complexity)] +#![allow(clippy::collapsible_else_if)] +#![allow(clippy::collapsible_if)] +#![allow(clippy::comparison_chain)] + +use advent_of_code::prelude::*; + +mod day1; +mod day10; +mod day11; +mod day12; +mod day13; +mod day14; +mod day15; +mod day16; +mod day17; +mod day18; +mod day19; +mod day2; +mod day20; +mod day21; +mod day22; +mod day23; +mod day24; +mod day25; +mod day3; +mod day4; +mod day5; +mod day6; +mod day7; +mod day8; +mod day9; +// NEXT MOD + +#[paw::main] +fn main(opt: Opt) -> Result<()> { + #[allow(clippy::match_single_binding)] + match opt.day { + 1 => advent_of_code::day!(2021, opt.day, opt.puzzle, day1), + 2 => advent_of_code::day!(2021, opt.day, opt.puzzle, day2), + 3 => advent_of_code::day!(2021, opt.day, opt.puzzle, day3), + 4 => advent_of_code::day!(2021, opt.day, opt.puzzle, day4), + 5 => advent_of_code::day!(2021, opt.day, opt.puzzle, day5), + 6 => advent_of_code::day!(2021, opt.day, opt.puzzle, day6), + 7 => advent_of_code::day!(2021, opt.day, opt.puzzle, day7), + 8 => advent_of_code::day!(2021, opt.day, opt.puzzle, day8), + 9 => advent_of_code::day!(2021, opt.day, opt.puzzle, day9), + 10 => advent_of_code::day!(2021, opt.day, opt.puzzle, day10), + 11 => advent_of_code::day!(2021, opt.day, opt.puzzle, day11), + 12 => advent_of_code::day!(2021, opt.day, opt.puzzle, day12), + 13 => advent_of_code::day!(2021, opt.day, opt.puzzle, day13), + 14 => advent_of_code::day!(2021, opt.day, opt.puzzle, day14), + 15 => advent_of_code::day!(2021, opt.day, opt.puzzle, day15), + 16 => advent_of_code::day!(2021, opt.day, opt.puzzle, day16), + 17 => advent_of_code::day!(2021, opt.day, opt.puzzle, day17), + 18 => advent_of_code::day!(2021, opt.day, opt.puzzle, day18), + 19 => advent_of_code::day!(2021, opt.day, opt.puzzle, day19), + 20 => advent_of_code::day!(2021, opt.day, opt.puzzle, day20), + 21 => advent_of_code::day!(2021, opt.day, opt.puzzle, day21), + 22 => advent_of_code::day!(2021, opt.day, opt.puzzle, day22), + 23 => advent_of_code::day!(2021, opt.day, opt.puzzle, day23), + 24 => advent_of_code::day!(2021, opt.day, opt.puzzle, day24), + 25 => advent_of_code::day!(2021, opt.day, opt.puzzle, day25), + // NEXT PART + _ => panic!("unknown day {}", opt.day), + } + Ok(()) +} |