From e2d219b331a878bbb3c9dcef9ea4e218b2e3ee06 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Sun, 11 Dec 2022 21:59:21 -0500 Subject: refactor --- src/bin/2020/day1.rs | 41 ++ src/bin/2020/day2.rs | 79 +++ src/bin/2020/day3.rs | 64 ++ src/bin/2020/day4.rs | 137 ++++ src/bin/2020/day5.rs | 96 +++ src/bin/2020/day6.rs | 59 ++ src/bin/2020/day7.rs | 102 +++ src/bin/2020/day8.rs | 133 ++++ src/bin/2020/day9.rs | 74 +++ src/bin/2020/main.rs | 42 ++ src/bin/2021/day1.rs | 36 + src/bin/2021/day10.rs | 109 ++++ src/bin/2021/day11.rs | 82 +++ src/bin/2021/day12.rs | 99 +++ src/bin/2021/day13.rs | 144 ++++ src/bin/2021/day14.rs | 94 +++ src/bin/2021/day15.rs | 68 ++ src/bin/2021/day16.rs | 210 ++++++ src/bin/2021/day17.rs | 106 +++ src/bin/2021/day18.rs | 257 ++++++++ src/bin/2021/day19.rs | 293 +++++++++ src/bin/2021/day2.rs | 73 +++ src/bin/2021/day20.rs | 108 +++ src/bin/2021/day21.rs | 215 ++++++ src/bin/2021/day22.rs | 216 ++++++ src/bin/2021/day23.rs | 1736 +++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2021/day24.rs | 337 ++++++++++ src/bin/2021/day25.rs | 96 +++ src/bin/2021/day3.rs | 102 +++ src/bin/2021/day4.rs | 167 +++++ src/bin/2021/day5.rs | 123 ++++ src/bin/2021/day6.rs | 47 ++ src/bin/2021/day7.rs | 42 ++ src/bin/2021/day8.rs | 185 ++++++ src/bin/2021/day9.rs | 71 ++ src/bin/2021/main.rs | 74 +++ src/bin/2022/day1.rs | 38 ++ src/bin/2022/day10.rs | 93 +++ src/bin/2022/day11.rs | 181 ++++++ src/bin/2022/day2.rs | 136 ++++ src/bin/2022/day3.rs | 62 ++ src/bin/2022/day4.rs | 69 ++ src/bin/2022/day5.rs | 141 ++++ src/bin/2022/day6.rs | 38 ++ src/bin/2022/day7.rs | 136 ++++ src/bin/2022/day8.rs | 156 +++++ src/bin/2022/day9.rs | 236 +++++++ src/bin/2022/main.rs | 46 ++ 48 files changed, 7249 insertions(+) create mode 100644 src/bin/2020/day1.rs create mode 100644 src/bin/2020/day2.rs create mode 100644 src/bin/2020/day3.rs create mode 100644 src/bin/2020/day4.rs create mode 100644 src/bin/2020/day5.rs create mode 100644 src/bin/2020/day6.rs create mode 100644 src/bin/2020/day7.rs create mode 100644 src/bin/2020/day8.rs create mode 100644 src/bin/2020/day9.rs create mode 100644 src/bin/2020/main.rs create mode 100644 src/bin/2021/day1.rs create mode 100644 src/bin/2021/day10.rs create mode 100644 src/bin/2021/day11.rs create mode 100644 src/bin/2021/day12.rs create mode 100644 src/bin/2021/day13.rs create mode 100644 src/bin/2021/day14.rs create mode 100644 src/bin/2021/day15.rs create mode 100644 src/bin/2021/day16.rs create mode 100644 src/bin/2021/day17.rs create mode 100644 src/bin/2021/day18.rs create mode 100644 src/bin/2021/day19.rs create mode 100644 src/bin/2021/day2.rs create mode 100644 src/bin/2021/day20.rs create mode 100644 src/bin/2021/day21.rs create mode 100644 src/bin/2021/day22.rs create mode 100644 src/bin/2021/day23.rs create mode 100644 src/bin/2021/day24.rs create mode 100644 src/bin/2021/day25.rs create mode 100644 src/bin/2021/day3.rs create mode 100644 src/bin/2021/day4.rs create mode 100644 src/bin/2021/day5.rs create mode 100644 src/bin/2021/day6.rs create mode 100644 src/bin/2021/day7.rs create mode 100644 src/bin/2021/day8.rs create mode 100644 src/bin/2021/day9.rs create mode 100644 src/bin/2021/main.rs create mode 100644 src/bin/2022/day1.rs create mode 100644 src/bin/2022/day10.rs create mode 100644 src/bin/2022/day11.rs create mode 100644 src/bin/2022/day2.rs create mode 100644 src/bin/2022/day3.rs create mode 100644 src/bin/2022/day4.rs create mode 100644 src/bin/2022/day5.rs create mode 100644 src/bin/2022/day6.rs create mode 100644 src/bin/2022/day7.rs create mode 100644 src/bin/2022/day8.rs create mode 100644 src/bin/2022/day9.rs create mode 100644 src/bin/2022/main.rs (limited to 'src/bin') diff --git a/src/bin/2020/day1.rs b/src/bin/2020/day1.rs new file mode 100644 index 0000000..8e582d8 --- /dev/null +++ b/src/bin/2020/day1.rs @@ -0,0 +1,41 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result> { + Ok(parse::lines(fh).collect()) +} + +pub fn part1(ints: Vec) -> Result { + for i in &ints { + for j in &ints { + if i + j == 2020 { + return Ok(i * j); + } + } + } + Err(anyhow!("no numbers summing to 2020 found")) +} + +pub fn part2(ints: Vec) -> Result { + for i in &ints { + for j in &ints { + for k in &ints { + if i + j + k == 2020 { + return Ok(i * j * k); + } + } + } + } + Err(anyhow!("no numbers summing to 2020 found")) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 1).unwrap()).unwrap()).unwrap(), + 445536 + ); + assert_eq!( + part2(parse(parse::data(2020, 1).unwrap()).unwrap()).unwrap(), + 138688160 + ); +} diff --git a/src/bin/2020/day2.rs b/src/bin/2020/day2.rs new file mode 100644 index 0000000..9d25860 --- /dev/null +++ b/src/bin/2020/day2.rs @@ -0,0 +1,79 @@ +use advent_of_code::prelude::*; + +pub struct Line { + c: char, + n1: usize, + n2: usize, + password: String, +} + +impl std::str::FromStr for Line { + type Err = anyhow::Error; + + fn from_str(line: &str) -> Result { + let captures = + regex_captures!(r"^([0-9]+)-([0-9]+) (.): (.*)$", line) + .context("line failed to match regex")?; + let c = captures + .get(3) + .unwrap() + .as_str() + .parse() + .context("invalid policy char")?; + let n1 = captures + .get(1) + .unwrap() + .as_str() + .parse() + .context("invalid policy lower bound")?; + let n2 = captures + .get(2) + .unwrap() + .as_str() + .parse() + .context("invalid policy upper bound")?; + let password = captures.get(4).unwrap().as_str().to_string(); + Ok(Self { + c, + n1, + n2, + password, + }) + } +} + +impl Line { + fn valid_part_1(&self) -> bool { + let count = self.password.chars().filter(|c| *c == self.c).count(); + count >= self.n1 && count <= self.n2 + } + + fn valid_part_2(&self) -> bool { + (self.password.chars().nth(self.n1 - 1) == Some(self.c)) + ^ (self.password.chars().nth(self.n2 - 1) == Some(self.c)) + } +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::lines(fh)) +} + +pub fn part1(lines: impl Iterator) -> Result { + Ok(lines.filter(|l| l.valid_part_1()).count()) +} + +pub fn part2(lines: impl Iterator) -> Result { + Ok(lines.filter(|l| l.valid_part_2()).count()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 2).unwrap()).unwrap()).unwrap(), + 638 + ); + assert_eq!( + part2(parse(parse::data(2020, 2).unwrap()).unwrap()).unwrap(), + 699 + ); +} diff --git a/src/bin/2020/day3.rs b/src/bin/2020/day3.rs new file mode 100644 index 0000000..a2314ee --- /dev/null +++ b/src/bin/2020/day3.rs @@ -0,0 +1,64 @@ +use advent_of_code::prelude::*; + +pub struct Map { + grid: Grid, +} + +impl Map { + fn new(grid: Grid) -> Self { + Self { grid } + } + + fn rows(&self) -> usize { + self.grid.rows().0 + } + + fn tree_at(&self, row: Row, col: Col) -> Result { + // unwrap safe because cycle().nth() can never fail + Ok(*self.grid[row].iter().cycle().nth(col.0).unwrap()) + } + + fn trees_for_slope( + &self, + row_incr: usize, + col_incr: usize, + ) -> Result { + let mut trees = 0; + for r in 0..self.rows() / row_incr { + let row = r * row_incr; + let col = r * col_incr; + if self.tree_at(Row(row), Col(col))? { + trees += 1; + } + } + Ok(trees) + } +} + +pub fn parse(fh: File) -> Result { + Ok(Map::new(parse::bool_grid(parse::raw_lines(fh), b'#', b'.'))) +} + +pub fn part1(map: Map) -> Result { + map.trees_for_slope(1, 3) +} + +pub fn part2(map: Map) -> Result { + Ok(map.trees_for_slope(1, 1)? + * map.trees_for_slope(1, 3)? + * map.trees_for_slope(1, 5)? + * map.trees_for_slope(1, 7)? + * map.trees_for_slope(2, 1)?) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 3).unwrap()).unwrap()).unwrap(), + 292 + ); + assert_eq!( + part2(parse(parse::data(2020, 3).unwrap()).unwrap()).unwrap(), + 9354744432 + ); +} diff --git a/src/bin/2020/day4.rs b/src/bin/2020/day4.rs new file mode 100644 index 0000000..aed67cb --- /dev/null +++ b/src/bin/2020/day4.rs @@ -0,0 +1,137 @@ +use advent_of_code::prelude::*; + +const REQUIRED_KEYS: &[&str] = + &["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]; + +pub fn parse(fh: File) -> Result>> { + let mut res = vec![]; + let mut cur = HashMap::new(); + let mut lines = parse::raw_lines(fh).peekable(); + while lines.peek().is_some() { + for line in parse::chunk(&mut lines) { + for field in line.split(' ') { + let mut parts = field.split(':'); + let key = parts.next().with_context(|| { + format!("failed to parse field '{}'", field) + })?; + let value = parts.next().with_context(|| { + format!("failed to parse field '{}'", field) + })?; + cur.insert(key.to_string(), value.to_string()); + } + } + res.push(cur); + cur = HashMap::new(); + } + if !cur.is_empty() { + res.push(cur); + } + Ok(res) +} + +pub fn part1(passports: Vec>) -> Result { + let mut valid = 0; + for passport in passports { + let mut cur_valid = true; + for key in REQUIRED_KEYS { + if !passport.contains_key(&key.to_string()) { + cur_valid = false; + break; + } + } + if cur_valid { + valid += 1; + } + } + Ok(valid) +} + +pub fn part2(passports: Vec>) -> Result { + let mut valid = 0; + for passport in passports { + let mut cur_valid = true; + for key in REQUIRED_KEYS { + match passport.get(&key.to_string()) { + Some(val) => { + if !validate(key, val)? { + cur_valid = false; + break; + } + } + None => { + cur_valid = false; + break; + } + } + } + if cur_valid { + valid += 1; + } + } + Ok(valid) +} + +fn validate(key: &str, val: &str) -> Result { + match key { + "byr" => match val.parse::() { + Ok(year) => Ok((1920..=2002).contains(&year)), + Err(_) => Ok(false), + }, + "iyr" => match val.parse::() { + Ok(year) => Ok((2010..=2020).contains(&year)), + Err(_) => Ok(false), + }, + "eyr" => match val.parse::() { + Ok(year) => Ok((2020..=2030).contains(&year)), + Err(_) => Ok(false), + }, + "hgt" => { + if val.len() < 3 { + Ok(false) + } else if val.ends_with("in") { + match val[0..val.len() - 2].parse::() { + Ok(inches) => Ok((59..=76).contains(&inches)), + Err(_) => Ok(false), + } + } else if val.ends_with("cm") { + match val[0..val.len() - 2].parse::() { + Ok(inches) => Ok((150..=193).contains(&inches)), + Err(_) => Ok(false), + } + } else { + Ok(false) + } + } + "hcl" => Ok(val.len() == 7 + && val.starts_with('#') + && val[1..] + == val[1..] + .matches(|c: char| c.is_ascii_hexdigit()) + .collect::()), + "ecl" => Ok(val == "amb" + || val == "blu" + || val == "brn" + || val == "gry" + || val == "grn" + || val == "hzl" + || val == "oth"), + "pid" => Ok(val.len() == 9 + && val + == val + .matches(|c: char| c.is_ascii_digit()) + .collect::()), + _ => Err(anyhow!("invalid key found: {}", key)), + } +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 4).unwrap()).unwrap()).unwrap(), + 247 + ); + assert_eq!( + part2(parse(parse::data(2020, 4).unwrap()).unwrap()).unwrap(), + 145 + ); +} diff --git a/src/bin/2020/day5.rs b/src/bin/2020/day5.rs new file mode 100644 index 0000000..abfd400 --- /dev/null +++ b/src/bin/2020/day5.rs @@ -0,0 +1,96 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result> { + Ok(parse::raw_lines(fh).map(|line| seat_id(&line).unwrap())) +} + +pub fn part1(ids: impl Iterator) -> Result { + let mut max = 0; + for id in ids { + if id > max { + max = id; + } + } + Ok(max) +} + +pub fn part2(ids: impl Iterator) -> Result { + let mut seats = vec![false; 1024]; + for id in ids { + seats[id as usize] = true; + } + let first = seats + .iter() + .position(|b| *b) + .context("failed to find taken seat")?; + let seat = seats + .iter() + .skip(first) + .position(|b| !*b) + .context("failed to find free seat")? + + first; + if !seats[seat - 1] || seats[seat] || !seats[seat + 1] { + return Err(anyhow!("invalid seat found")); + } + Ok(seat.try_into()?) +} + +fn seat_id(desc: &str) -> Result { + if desc.len() != 10 { + return Err(anyhow!("invalid desc {}", desc)); + } + let row_desc = &desc[0..7]; + let col_desc = &desc[7..10]; + + let mut min_row = 0; + let mut max_row = 127; + for c in row_desc.chars() { + let mid = (max_row + min_row) / 2; + match c { + 'F' => { + max_row = mid; + } + 'B' => { + min_row = mid + 1; + } + _ => return Err(anyhow!("invalid desc {}", desc)), + } + } + if min_row != max_row { + return Err(anyhow!("bug")); + } + let row = min_row; + + let mut min_col = 0; + let mut max_col = 7; + for c in col_desc.chars() { + let mid = (max_col + min_col) / 2; + match c { + 'L' => { + max_col = mid; + } + 'R' => { + min_col = mid + 1; + } + _ => return Err(anyhow!("invalid desc {}", desc)), + } + } + if min_col != max_col { + return Err(anyhow!("bug")); + } + let col = min_col; + + Ok(row * 8 + col) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 5).unwrap()).unwrap()).unwrap(), + 978 + ); + assert_eq!( + part2(parse(parse::data(2020, 5).unwrap()).unwrap()).unwrap(), + 727 + ); +} diff --git a/src/bin/2020/day6.rs b/src/bin/2020/day6.rs new file mode 100644 index 0000000..114d05f --- /dev/null +++ b/src/bin/2020/day6.rs @@ -0,0 +1,59 @@ +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result> { + Ok(parse::raw_lines(fh)) +} + +pub fn part1(lines: impl Iterator) -> Result { + let mut yes = HashSet::new(); + let mut total = 0; + for line in lines { + if line.is_empty() { + total += yes.len(); + yes = HashSet::new(); + } else { + for c in line.chars() { + yes.insert(c); + } + } + } + total += yes.len(); + Ok(total) +} + +pub fn part2(lines: impl Iterator) -> Result { + let mut yes = HashSet::new(); + for c in 'a'..='z' { + yes.insert(c); + } + let mut total = 0; + for line in lines { + if line.is_empty() { + total += yes.len(); + yes = HashSet::new(); + for c in 'a'..='z' { + yes.insert(c); + } + } else { + for c in 'a'..='z' { + if !line.contains(c) { + yes.remove(&c); + } + } + } + } + total += yes.len(); + Ok(total) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 6).unwrap()).unwrap()).unwrap(), + 6930 + ); + assert_eq!( + part2(parse(parse::data(2020, 6).unwrap()).unwrap()).unwrap(), + 3585 + ); +} diff --git a/src/bin/2020/day7.rs b/src/bin/2020/day7.rs new file mode 100644 index 0000000..ac6c74a --- /dev/null +++ b/src/bin/2020/day7.rs @@ -0,0 +1,102 @@ +use advent_of_code::prelude::*; + +type Graph = HashMap>; + +pub fn parse(fh: File) -> Result { + let input = parse::string(fh); + let mut graph = Graph::new(); + for line in input.lines() { + let (k, v) = parse_line(line)?; + graph.insert(k, v); + } + Ok(graph) +} + +pub fn part1(graph: Graph) -> Result { + let mut colors = 0; + for color in graph.keys() { + if bag_contains(&graph, color, "shiny gold")? { + colors += 1; + } + } + Ok(colors) +} + +pub fn part2(graph: Graph) -> Result { + // subtract 1 to not count the shiny gold bag itself + count_bags(&graph, "shiny gold").map(|i| i - 1) +} + +fn parse_line(line: &str) -> Result<(String, Vec<(u64, String)>)> { + let captures = regex_captures!(r"^(.*) bags contain (.*)\.$", line) + .context("line failed to match regex")?; + let color = captures.get(1).unwrap().as_str(); + let contents = captures.get(2).unwrap().as_str(); + if contents == "no other bags" { + Ok((color.to_string(), vec![])) + } else { + Ok(( + color.to_string(), + contents + .split(", ") + .map(|s| { + let captures = + regex_captures!(r"^([0-9]+) (.*) bags?", s) + .context("line failed to match regex")?; + Ok(( + captures + .get(1) + .unwrap() + .as_str() + .parse() + .context("invalid number of bags")?, + captures.get(2).unwrap().as_str().to_string(), + )) + }) + .collect::>()?, + )) + } +} + +fn bag_contains(graph: &Graph, start: &str, target: &str) -> Result { + let mut to_check = graph + .get(&start.to_string()) + .context("failed to find starting color in graph")? + .clone(); + while let Some((_, next)) = to_check.pop() { + if next == target { + return Ok(true); + } + to_check.extend( + graph + .get(&next) + .context("failed to find next color in graph")? + .iter() + .cloned(), + ); + } + Ok(false) +} + +fn count_bags(graph: &Graph, color: &str) -> Result { + Ok(1 + graph + .get(&color.to_string()) + .context("failed to find starting color in graph")? + .iter() + .map(|(count, child)| Ok(count * count_bags(graph, child)?)) + .collect::>>()? + .iter() + .sum::()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 7).unwrap()).unwrap()).unwrap(), + 169 + ); + assert_eq!( + part2(parse(parse::data(2020, 7).unwrap()).unwrap()).unwrap(), + 82372 + ); +} diff --git a/src/bin/2020/day8.rs b/src/bin/2020/day8.rs new file mode 100644 index 0000000..06861f5 --- /dev/null +++ b/src/bin/2020/day8.rs @@ -0,0 +1,133 @@ +use advent_of_code::prelude::*; + +#[derive(Clone, Copy)] +enum OpType { + Nop, + Acc, + Jmp, +} + +impl std::str::FromStr for OpType { + type Err = Error; + + fn from_str(s: &str) -> std::result::Result { + Ok(match s { + "nop" => Self::Nop, + "acc" => Self::Acc, + "jmp" => Self::Jmp, + _ => return Err(anyhow!("invalid optype {}", s)), + }) + } +} + +#[derive(Clone, Copy)] +pub struct Op { + ty: OpType, + arg: i64, +} + +impl std::str::FromStr for Op { + type Err = Error; + + fn from_str(s: &str) -> std::result::Result { + let captures = regex_captures!(r"^([^ ]*) ((?:-|\+)[0-9]+)$", s) + .context("failed to parse line")?; + let ty = captures.get(1).unwrap().as_str().parse()?; + let arg = captures + .get(2) + .unwrap() + .as_str() + .parse() + .context("invalid arg")?; + Ok(Self { ty, arg }) + } +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::lines(fh).collect()) +} + +pub fn part1(opcodes: Vec) -> Result { + let (acc, success) = run(&opcodes)?; + if success { + return Err(anyhow!("unexpectedly succeeded")); + } + Ok(acc) +} + +pub fn part2(opcodes: Vec) -> Result { + for i in 0..opcodes.len() { + match opcodes[i].ty { + OpType::Nop => { + let mut attempt = opcodes.clone(); + attempt[i].ty = OpType::Jmp; + let (acc, success) = run(&attempt)?; + if success { + return Ok(acc); + } + } + OpType::Acc => {} + OpType::Jmp => { + let mut attempt = opcodes.clone(); + attempt[i].ty = OpType::Nop; + let (acc, success) = run(&attempt)?; + if success { + return Ok(acc); + } + } + } + } + Err(anyhow!("failed to find corrupted opcode")) +} + +fn run(opcodes: &[Op]) -> Result<(i64, bool)> { + let mut seen = vec![false; opcodes.len()]; + let mut pc = 0; + let mut acc = 0; + loop { + if pc >= opcodes.len() { + return Ok((acc, true)); + } else if seen[pc] { + return Ok((acc, false)); + } + seen[pc] = true; + + match opcodes[pc].ty { + OpType::Nop => { + pc += 1; + } + OpType::Acc => { + acc += opcodes[pc].arg; + pc += 1; + } + OpType::Jmp => { + let arg = opcodes[pc].arg; + if arg >= 0 { + if arg as usize > opcodes.len() + || pc > opcodes.len() - arg as usize + { + return Err(anyhow!("invalid jmp")); + } + pc += arg as usize; + } else { + if pc < (-arg as usize) { + return Err(anyhow!("invalid jmp")); + } + pc -= -arg as usize; + } + } + } + } +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 8).unwrap()).unwrap()).unwrap(), + 1928 + ); + assert_eq!( + part2(parse(parse::data(2020, 8).unwrap()).unwrap()).unwrap(), + 1319 + ); +} diff --git a/src/bin/2020/day9.rs b/src/bin/2020/day9.rs new file mode 100644 index 0000000..becae3b --- /dev/null +++ b/src/bin/2020/day9.rs @@ -0,0 +1,74 @@ +use advent_of_code::prelude::*; + +const WINDOW: usize = 25; + +pub fn parse(fh: File) -> Result> { + Ok(parse::lines(fh).collect()) +} + +pub fn part1(list: Vec) -> Result { + for i in 0..(list.len() - WINDOW) { + let set = &list[i..i + WINDOW]; + let n = list[i + WINDOW]; + if !valid(set, n) { + return Ok(n); + } + } + + Err(anyhow!("failed to find invalid number")) +} + +pub fn part2(list: Vec) -> Result { + let mut invalid = None; + for i in 0..(list.len() - WINDOW) { + let set = &list[i..i + WINDOW]; + let n = list[i + WINDOW]; + if !valid(set, n) { + invalid = Some(n); + } + } + if invalid.is_none() { + return Err(anyhow!("failed to find invalid number")); + } + let invalid = invalid.unwrap(); + + for i in 0..list.len() { + for j in i..list.len() { + let seq = &list[i..=j]; + if invalid == seq.iter().sum() { + return Ok(seq.iter().copied().min().unwrap() + + seq.iter().copied().max().unwrap()); + } + } + } + + Err(anyhow!("failed to find sequence summing to invalid number")) +} + +fn valid(set: &[u64], n: u64) -> bool { + for i in 0..set.len() { + for j in 0..set.len() { + if i == j { + continue; + } + let i = set[i]; + let j = set[j]; + if i + j == n { + return true; + } + } + } + false +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2020, 9).unwrap()).unwrap()).unwrap(), + 373803594 + ); + assert_eq!( + part2(parse(parse::data(2020, 9).unwrap()).unwrap()).unwrap(), + 51152360 + ); +} diff --git a/src/bin/2020/main.rs b/src/bin/2020/main.rs new file mode 100644 index 0000000..354f6b0 --- /dev/null +++ b/src/bin/2020/main.rs @@ -0,0 +1,42 @@ +#![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 day2; +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!(2020, opt.day, opt.puzzle, day1), + 2 => advent_of_code::day!(2020, opt.day, opt.puzzle, day2), + 3 => advent_of_code::day!(2020, opt.day, opt.puzzle, day3), + 4 => advent_of_code::day!(2020, opt.day, opt.puzzle, day4), + 5 => advent_of_code::day!(2020, opt.day, opt.puzzle, day5), + 6 => advent_of_code::day!(2020, opt.day, opt.puzzle, day6), + 7 => advent_of_code::day!(2020, opt.day, opt.puzzle, day7), + 8 => advent_of_code::day!(2020, opt.day, opt.puzzle, day8), + 9 => advent_of_code::day!(2020, opt.day, opt.puzzle, day9), + // NEXT PART + _ => panic!("unknown day {}", opt.day), + } + Ok(()) +} 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> { + Ok(parse::lines(fh).collect()) +} + +pub fn part1(ints: Vec) -> Result { + Ok(ints + .windows(2) + .map(|a| a[1] - a[0]) + .filter(|x| *x > 0) + .count()) +} + +pub fn part2(ints: Vec) -> Result { + Ok(ints + .windows(3) + .map(|a| a[0] + a[1] + a[2]) + .collect::>() + .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> { + Ok(parse::raw_lines(fh)) +} + +pub fn part1(lines: impl Iterator) -> Result { + 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) -> Result { + 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 = 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> { + 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 { + let mut flashes = 0; + for _ in 0..100 { + flashes += iterate(&mut map); + } + Ok(flashes) +} + +pub fn part2(mut map: Grid<(u8, bool)>) -> Result { + 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) -> 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>, + 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>, + 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>> { + 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>) -> Result { + Ok(paths_from1(&graph, &mut vec!["start"])) +} + +pub fn part2(graph: HashMap>) -> Result { + 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, +} + +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 { + paper.fold(folds[0].0, folds[0].1); + Ok(paper.total()) +} + +pub fn part2( + (mut paper, folds): (Paper, Vec<(bool, usize)>), +) -> Result { + 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, u8>) -> Vec { + 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, HashMap, 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, HashMap, u8>), +) -> Result { + 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, HashMap, u8>), +) -> Result { + 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, +} + +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 { + Ok(Map { + grid: parse::digit_grid(parse::raw_lines(fh)), + }) +} + +pub fn part1(map: Map) -> Result { + Ok(map + .dijkstra( + (Row(0), Col(0)), + (map.grid.rows() - 1, map.grid.cols() - 1), + ) + .0) +} + +pub fn part2(map: Map) -> Result { + 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 { + 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) -> impl Iterator { + bytes.flat_map(BitIter::new) +} + +struct LiteralU8(u8); + +impl FromIterator for LiteralU8 { + fn from_iter(iter: T) -> Self + where + T: IntoIterator, + { + let mut ret = 0; + for b in iter { + ret = (ret << 1) | u8::from(b); + } + Self(ret) + } +} + +struct LiteralU16(u16); + +impl FromIterator for LiteralU16 { + fn from_iter(iter: T) -> Self + where + T: IntoIterator, + { + 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 }, +} + +impl Packet { + fn parse(bits: &mut impl Iterator) -> (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 { + 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) -> (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 { + 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 { + 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 { + Ok(packet + .subpackets() + .map(|packet| u64::from(packet.version)) + .sum()) +} + +pub fn part2(packet: Packet) -> Result { + 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, + yrange: &std::ops::RangeInclusive, +) -> Option { + 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, std::ops::RangeInclusive)> { + 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 = + captures[1].parse().unwrap()..=captures[2].parse().unwrap(); + let yrange: std::ops::RangeInclusive = + captures[3].parse().unwrap()..=captures[4].parse().unwrap(); + Ok((xrange, yrange)) +} + +pub fn part1( + (xrange, yrange): ( + std::ops::RangeInclusive, + std::ops::RangeInclusive, + ), +) -> Result { + 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, + std::ops::RangeInclusive, + ), +) -> Result { + 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, Box), +} + +impl std::str::FromStr for Number { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result { + 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(mut iter: I) -> Self + where + I: Iterator, + { + 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> { + Ok(parse::lines(fh)) +} + +pub fn part1(numbers: impl Iterator) -> Result { + let sum: Number = numbers.sum(); + Ok(sum.magnitude()) +} + +pub fn part2(numbers: impl Iterator) -> Result { + 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, +} + +impl Scanner { + fn parse(lines: impl Iterator) -> 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) -> 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> { + let beacons = self.beacons.clone(); + ORIENTATIONS.iter().map(move |orientation| { + beacons.iter().map(|beacon| orientation(*beacon)).collect() + }) + } + + fn at_orientation 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, +} + +impl Scan { + fn parse(mut lines: impl Iterator) -> 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 { + Ok(Scan::parse(parse::raw_lines(fh))) +} + +pub fn part1(scan: Scan) -> Result { + let mut beacons: HashSet = 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 { + let mut beacons: HashSet = 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> { + 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) -> Result { + 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) -> Result { + 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, + map: Grid, + outer: bool, +} + +impl Image { + fn new(algorithm: Vec, map: Grid) -> Self { + Self { + algorithm, + map, + outer: false, + } + } + + fn enhance(&mut self) { + let mut new_map: Grid = 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, Option)] = &[ + (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 { + 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 { + for _ in 0..2 { + image.enhance(); + } + Ok(image.count_true()) +} + +pub fn part2(mut image: Image) -> Result { + 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 { + 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 { + 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 { + 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 { + 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, + y: std::ops::RangeInclusive, + z: std::ops::RangeInclusive, +} + +impl Range3D { + fn new( + x: std::ops::RangeInclusive, + y: std::ops::RangeInclusive, + z: std::ops::RangeInclusive, + ) -> 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 { + 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, + split_by: &std::ops::RangeInclusive, + ) -> Vec> { + 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 { + if self.range.contains(point) { + Some(self.on) + } else { + None + } + } +} + +#[derive(Debug)] +pub struct Reactor { + rules: Vec, +} + +impl Reactor { + fn parse(lines: impl Iterator) -> 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 { + Ok(Reactor::parse(parse::raw_lines(fh))) +} + +pub fn part1(reactor: Reactor) -> Result { + 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 { + let mut on: HashSet = 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 { + 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; 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 { + 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 for Pathfinder { + type Edges = Vec; + + 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 { + 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 { + let (cost, _path) = Pathfinder.dijkstra(burrow, Burrow::done(false)); + // for burrow in path { + // eprintln!("{}", burrow); + // } + Ok(cost) +} + +pub fn part2(burrow: Burrow) -> Result { + 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 { + 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 { + 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, 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, + 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 { + 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> { + 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) -> Result { + 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) -> Result { + 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, +} + +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 { + 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 { + 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 { + 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> { + Ok(parse::raw_lines(fh)) +} + +pub fn part1(lines: impl Iterator) -> Result { + 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) -> Result { + 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, +) -> Result<(i64, Vec)> { + 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, + marked: Vec, +} + +impl Board { + fn new(numbers: Vec) -> 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, + boards: Vec, +} + +impl Game { + fn parse(input: T) -> Result { + 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::, _>>()?; + 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::, _>>()?, + ); + } + 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::parse(fh) +} + +pub fn part1(game: Game) -> Result { + 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 { + 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, +} + +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>> { + 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::>() + .unwrap() + })) +} + +pub fn part1(coords: impl Iterator>) -> Result { + 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>) -> Result { + 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> { + Ok(parse::split(fh, b',').collect()) +} + +pub fn part1(mut fishes: Vec) -> Result { + 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) -> Result { + 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> { + Ok(parse::split(fh, b',').collect()) +} + +pub fn part1(crabs: Vec) -> Result { + 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) -> Result { + 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, Vec)>> { + 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, Vec)>, +) -> Result { + 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, Vec)>, +) -> Result { + 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 = one.chars().collect(); + // two: 5 + // three: 5 + let four = numbers.iter().find(|s| s.len() == 4).unwrap(); + let four: HashSet = four.chars().collect(); + // five: 5 + // six: 6 + let seven = numbers.iter().find(|s| s.len() == 3).unwrap(); + let seven: HashSet = seven.chars().collect(); + let eight = numbers.iter().find(|s| s.len() == 7).unwrap(); + let eight: HashSet = eight.chars().collect(); + // nine: 6 + + let mut length_five: Vec<_> = numbers + .iter() + .filter_map(|s| { + if s.len() == 5 { + Some(s.chars().collect::>()) + } else { + None + } + }) + .collect(); + let mut length_six: Vec<_> = numbers + .iter() + .filter_map(|s| { + if s.len() == 6 { + Some(s.chars().collect::>()) + } 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::>()) + .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> { + Ok(parse::digit_grid(parse::raw_lines(fh))) +} + +pub fn part1(map: Grid) -> Result { + 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) -> Result { + 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 = 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(()) +} diff --git a/src/bin/2022/day1.rs b/src/bin/2022/day1.rs new file mode 100644 index 0000000..1b48b29 --- /dev/null +++ b/src/bin/2022/day1.rs @@ -0,0 +1,38 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result> { + let mut elves = vec![]; + let mut lines = parse::raw_lines(fh).peekable(); + while lines.peek().is_some() { + let mut calories = 0; + for line in parse::chunk(&mut lines) { + calories += line.parse::()?; + } + elves.push(calories); + } + Ok(elves) +} + +pub fn part1(elves: Vec) -> Result { + Ok(elves.iter().copied().max().unwrap_or(0)) +} + +pub fn part2(mut elves: Vec) -> Result { + elves.sort(); + Ok(elves.iter().rev().copied().take(3).sum()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 1).unwrap()).unwrap()).unwrap(), + 67658 + ); + assert_eq!( + part2(parse(parse::data(2022, 1).unwrap()).unwrap()).unwrap(), + 200158 + ); +} diff --git a/src/bin/2022/day10.rs b/src/bin/2022/day10.rs new file mode 100644 index 0000000..8f7b617 --- /dev/null +++ b/src/bin/2022/day10.rs @@ -0,0 +1,93 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub struct Cpu { + x: i64, + history: Vec, +} + +impl Cpu { + fn new() -> Self { + Self { + x: 1, + history: vec![1], + } + } + + fn step(&mut self, op: Op) { + match op { + Op::Noop => { + self.history.push(self.x); + } + Op::Addx(v) => { + self.history.push(self.x); + self.x += v; + self.history.push(self.x); + } + } + } +} + +#[derive(Clone, Copy)] +pub enum Op { + Noop, + Addx(i64), +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::raw_lines(fh).map(|line| { + if line == "noop" { + Op::Noop + } else if let Some(v) = line.strip_prefix("addx ") { + Op::Addx(v.parse().unwrap()) + } else { + panic!("failed to parse {}", line) + } + })) +} + +pub fn part1(ops: impl Iterator) -> Result { + let mut cpu = Cpu::new(); + for op in ops { + cpu.step(op); + } + + let mut total = 0; + for cycle in [20, 60, 100, 140, 180, 220] { + let strength = i64::try_from(cycle).unwrap() * cpu.history[cycle - 1]; + total += strength; + } + Ok(total) +} + +pub fn part2(ops: impl Iterator) -> Result { + let mut cpu = Cpu::new(); + for op in ops { + cpu.step(op); + } + for (y, row) in cpu.history.chunks(40).enumerate() { + for (x, pos) in row.iter().enumerate() { + if i64::try_from(x).unwrap().abs_diff(*pos) <= 1 { + print!("#"); + } else { + print!("."); + } + } + println!(); + } + Ok(0) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 10).unwrap()).unwrap()).unwrap(), + 15680 + ); + assert_eq!( + part2(parse(parse::data(2022, 10).unwrap()).unwrap()).unwrap(), + 0 + ); +} diff --git a/src/bin/2022/day11.rs b/src/bin/2022/day11.rs new file mode 100644 index 0000000..faef195 --- /dev/null +++ b/src/bin/2022/day11.rs @@ -0,0 +1,181 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub struct Monkey { + items: VecDeque, + op: Box u64>, + divisor: u64, + modulo: u64, + test: u64, + if_true: usize, + if_false: usize, + + count: u64, +} + +impl std::fmt::Debug for Monkey { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct("Monkey") + .field("items", &self.items) + .finish() + } +} + +impl Monkey { + fn parse(mut it: impl Iterator) -> Monkey { + let line = it.next().unwrap(); + let cap = regex_captures!(r"^ Starting items: ([0-9, ]*)$", &line) + .unwrap(); + let items = cap[1].split(", ").map(|s| s.parse().unwrap()).collect(); + + let line = it.next().unwrap(); + let cap = regex_captures!( + r"^ Operation: new = old ([+*]) (\d+|old)$", + &line + ) + .unwrap(); + let op = if &cap[2] == "old" { + match &cap[1] { + "+" => Box::new(move |x| x + x) as Box u64>, + "*" => Box::new(move |x| x * x), + _ => unreachable!(), + } + } else { + let n: u64 = cap[2].parse().unwrap(); + match &cap[1] { + "+" => Box::new(move |x| x + n) as Box u64>, + "*" => Box::new(move |x| x * n), + _ => unreachable!(), + } + }; + + let line = it.next().unwrap(); + let cap = + regex_captures!(r"^ Test: divisible by (\d+)$", &line).unwrap(); + let test = cap[1].parse().unwrap(); + + let line = it.next().unwrap(); + let cap = + regex_captures!(r"^ If true: throw to monkey (\d+)$", &line) + .unwrap(); + let if_true = cap[1].parse().unwrap(); + + let line = it.next().unwrap(); + let cap = + regex_captures!(r"^ If false: throw to monkey (\d+)$", &line) + .unwrap(); + let if_false = cap[1].parse().unwrap(); + + assert!(it.next().is_none()); + + Self { + items, + op, + divisor: 0, + modulo: 0, + test, + if_true, + if_false, + count: 0, + } + } + + fn inspect(&mut self) -> Option<(u64, usize)> { + let Some(item) = self.items.pop_front() + else { return None }; + self.count += 1; + let item = (self.op)(item); + let item = item / self.divisor; + let item = item % self.modulo; + if item % self.test == 0 { + Some((item, self.if_true)) + } else { + Some((item, self.if_false)) + } + } + + fn catch(&mut self, item: u64) { + self.items.push_back(item); + } + + fn set_reduce(&mut self, divisor: u64, modulo: u64) { + self.divisor = divisor; + self.modulo = modulo; + } +} + +#[derive(Debug)] +pub struct Monkeys { + monkeys: Vec, +} + +impl Monkeys { + fn parse(it: impl Iterator) -> Self { + let mut monkeys = vec![]; + let mut it = it.peekable(); + while it.peek().is_some() { + let header = it.next().unwrap(); + let cap = regex_captures!(r"^Monkey (\d+):$", &header).unwrap(); + let monkey_idx: usize = cap[1].parse().unwrap(); + assert_eq!(monkey_idx, monkeys.len()); + monkeys.push(Monkey::parse(parse::chunk(&mut it))); + } + Self { monkeys } + } + + fn round(&mut self) { + for i in 0..self.monkeys.len() { + while let Some((item, to)) = self.monkeys[i].inspect() { + self.monkeys[to].catch(item); + } + } + } + + fn monkey_business(&self) -> u64 { + let mut counts: Vec<_> = + self.monkeys.iter().map(|m| m.count).collect(); + counts.sort_unstable(); + counts[counts.len() - 1] * counts[counts.len() - 2] + } + + fn set_reduce(&mut self, divisor: u64) { + let modulo = self.monkeys.iter().map(|m| m.test).product(); + for monkey in &mut self.monkeys { + monkey.set_reduce(divisor, modulo); + } + } +} + +pub fn parse(fh: File) -> Result { + Ok(Monkeys::parse(parse::raw_lines(fh))) +} + +pub fn part1(mut monkeys: Monkeys) -> Result { + monkeys.set_reduce(3); + for i in 0..20 { + monkeys.round(); + } + Ok(monkeys.monkey_business()) +} + +pub fn part2(mut monkeys: Monkeys) -> Result { + monkeys.set_reduce(1); + for i in 0..10_000 { + monkeys.round(); + } + Ok(monkeys.monkey_business()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 11).unwrap()).unwrap()).unwrap(), + 51075 + ); + assert_eq!( + part2(parse(parse::data(2022, 11).unwrap()).unwrap()).unwrap(), + 11741456163 + ); +} diff --git a/src/bin/2022/day2.rs b/src/bin/2022/day2.rs new file mode 100644 index 0000000..03a5360 --- /dev/null +++ b/src/bin/2022/day2.rs @@ -0,0 +1,136 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Copy, Clone, Eq, PartialEq)] +enum Outcome { + Lose, + Draw, + Win, +} + +impl Outcome { + fn score(self) -> u64 { + match self { + Self::Lose => 0, + Self::Draw => 3, + Self::Win => 6, + } + } +} + +impl std::str::FromStr for Outcome { + type Err = (); + + fn from_str(s: &str) -> Result { + Ok(match s { + "X" => Self::Lose, + "Y" => Self::Draw, + "Z" => Self::Win, + _ => return Err(()), + }) + } +} + +#[derive(Copy, Clone)] +enum Shape { + Rock, + Paper, + Scissors, +} + +impl Shape { + fn score(self) -> u64 { + match self { + Self::Rock => 1, + Self::Paper => 2, + Self::Scissors => 3, + } + } + + fn outcome(self, other: Self) -> Outcome { + match self { + Self::Rock => match other { + Self::Rock => Outcome::Draw, + Self::Paper => Outcome::Lose, + Self::Scissors => Outcome::Win, + }, + Self::Paper => match other { + Self::Rock => Outcome::Win, + Self::Paper => Outcome::Draw, + Self::Scissors => Outcome::Lose, + }, + Self::Scissors => match other { + Self::Rock => Outcome::Lose, + Self::Paper => Outcome::Win, + Self::Scissors => Outcome::Draw, + }, + } + } + + fn shape_for(self, outcome: Outcome) -> Self { + if Self::Rock.outcome(self) == outcome { + return Self::Rock; + } + if Self::Paper.outcome(self) == outcome { + return Self::Paper; + } + if Self::Scissors.outcome(self) == outcome { + return Self::Scissors; + } + unreachable!() + } +} + +impl std::str::FromStr for Shape { + type Err = (); + + fn from_str(s: &str) -> Result { + Ok(match s { + "A" | "X" => Self::Rock, + "B" | "Y" => Self::Paper, + "C" | "Z" => Self::Scissors, + _ => return Err(()), + }) + } +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::raw_lines(fh)) +} + +pub fn part1(lines: impl Iterator) -> Result { + Ok(lines + .map(|line| { + let mut parts = line.split(' '); + let them: Shape = parts.next().unwrap().parse().unwrap(); + let me: Shape = parts.next().unwrap().parse().unwrap(); + me.score() + me.outcome(them).score() + }) + .sum()) +} + +pub fn part2(lines: impl Iterator) -> Result { + Ok(lines + .map(|line| { + let mut parts = line.split(' '); + let them: Shape = parts.next().unwrap().parse().unwrap(); + let outcome: Outcome = parts.next().unwrap().parse().unwrap(); + let me = them.shape_for(outcome); + me.score() + outcome.score() + }) + .sum()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 2).unwrap()).unwrap()).unwrap(), + 13565 + ); + assert_eq!( + part2(parse(parse::data(2022, 2).unwrap()).unwrap()).unwrap(), + 12424 + ); +} diff --git a/src/bin/2022/day3.rs b/src/bin/2022/day3.rs new file mode 100644 index 0000000..a56baf4 --- /dev/null +++ b/src/bin/2022/day3.rs @@ -0,0 +1,62 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub fn parse( + fh: File, +) -> Result, HashSet)>> { + Ok(parse::raw_lines(fh).map(|line| { + let (first, second) = line.split_at(line.len() / 2); + let first: HashSet = first.chars().collect(); + let second: HashSet = second.chars().collect(); + (first, second) + })) +} + +pub fn part1( + sacks: impl Iterator, HashSet)>, +) -> Result { + Ok(sacks + .map(|(first, second)| { + priority(*first.intersection(&second).next().unwrap()) + }) + .sum()) +} + +pub fn part2( + mut sacks: impl Iterator, HashSet)>, +) -> Result { + let mut total = 0; + while let (Some(first), Some(second), Some(third)) = + (sacks.next(), sacks.next(), sacks.next()) + { + let first: HashSet = first.0.union(&first.1).copied().collect(); + let second: HashSet = + second.0.union(&second.1).copied().collect(); + let third: HashSet = third.0.union(&third.1).copied().collect(); + total += + priority(*(&(&first & &second) & &third).iter().next().unwrap()); + } + Ok(total) +} + +fn priority(c: char) -> u32 { + match c { + 'a'..='z' => u32::from(c) - u32::from('a') + 1, + 'A'..='Z' => u32::from(c) - u32::from('A') + 27, + _ => unreachable!(), + } +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 3).unwrap()).unwrap()).unwrap(), + 8493 + ); + assert_eq!( + part2(parse(parse::data(2022, 3).unwrap()).unwrap()).unwrap(), + 2552 + ); +} diff --git a/src/bin/2022/day4.rs b/src/bin/2022/day4.rs new file mode 100644 index 0000000..2fe98c5 --- /dev/null +++ b/src/bin/2022/day4.rs @@ -0,0 +1,69 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub struct Pair { + first: (i64, i64), + second: (i64, i64), +} + +impl Pair { + fn contains(&self) -> bool { + range_contains(self.first, self.second) + || range_contains(self.second, self.first) + } + + fn overlaps(&self) -> bool { + range_overlaps(self.first, self.second) + || range_overlaps(self.second, self.first) + } +} + +fn range_contains(a: (i64, i64), b: (i64, i64)) -> bool { + (a.0..=a.1).contains(&b.0) && (a.0..=a.1).contains(&b.1) +} + +fn range_overlaps(a: (i64, i64), b: (i64, i64)) -> bool { + (a.0..=a.1).contains(&b.0) || (a.0..=a.1).contains(&b.1) +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::raw_lines(fh).map(|line| { + let mut parts = line.split(','); + let first = parts.next().unwrap(); + let mut first_parts = first.split('-'); + let second = parts.next().unwrap(); + let mut second_parts = second.split('-'); + Pair { + first: ( + first_parts.next().unwrap().parse().unwrap(), + first_parts.next().unwrap().parse().unwrap(), + ), + second: ( + second_parts.next().unwrap().parse().unwrap(), + second_parts.next().unwrap().parse().unwrap(), + ), + } + })) +} + +pub fn part1(pairs: impl Iterator) -> Result { + Ok(pairs.filter(|pair| pair.contains()).count()) +} + +pub fn part2(pairs: impl Iterator) -> Result { + Ok(pairs.filter(|pair| pair.overlaps()).count()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 4).unwrap()).unwrap()).unwrap(), + 515 + ); + assert_eq!( + part2(parse(parse::data(2022, 4).unwrap()).unwrap()).unwrap(), + 883 + ); +} diff --git a/src/bin/2022/day5.rs b/src/bin/2022/day5.rs new file mode 100644 index 0000000..da1e5a2 --- /dev/null +++ b/src/bin/2022/day5.rs @@ -0,0 +1,141 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Default)] +pub struct Pile(Vec); + +impl Pile { + fn move_from(&mut self, other: &mut Self, n: usize) { + for _ in 0..n { + self.0.push(other.0.pop().unwrap()); + } + } + + fn unshift(&mut self, c: char) { + self.0.insert(0, c); + } + + fn push(&mut self, c: char) { + self.0.push(c); + } + + fn pop(&mut self) -> Option { + self.0.pop() + } + + fn top(&self) -> Option { + self.0.last().copied() + } +} + +struct Instruction { + count: usize, + from: usize, + to: usize, +} + +pub struct Crates { + piles: Vec, + instructions: Vec, +} + +pub fn parse(fh: File) -> Result { + let mut lines = parse::raw_lines(fh); + let mut piles: Vec = vec![]; + + for line in lines.by_ref() { + if line.starts_with(" 1 ") { + break; + } + + let pile_count = (line.len() + 1) / 4; + piles.resize_with(pile_count, Default::default); + + for (pile_idx, pile) in piles.iter_mut().enumerate() { + let idx = pile_idx * 4; + assert!([' ', '['].contains(&line.chars().nth(idx).unwrap())); + let crate_name = line.chars().nth(idx + 1).unwrap(); + if crate_name != ' ' { + pile.unshift(crate_name); + } + assert!([' ', ']'].contains(&line.chars().nth(idx + 2).unwrap())); + assert!([Some(' '), None].contains(&line.chars().nth(idx + 3))); + } + } + + assert_eq!(lines.next().unwrap(), ""); + + let mut instructions = vec![]; + for line in lines { + let captures = regex_captures!( + r"^move ([0-9]+) from ([0-9]+) to ([0-9]+)$", + &line + ) + .unwrap(); + let count = captures[1].parse().unwrap(); + let from = captures[2].parse().unwrap(); + let to = captures[3].parse().unwrap(); + instructions.push(Instruction { count, from, to }); + } + + Ok(Crates { + piles, + instructions, + }) +} + +fn part1_str(mut crates: Crates) -> Result { + for Instruction { count, from, to } in crates.instructions { + for _ in 0..count { + let c = crates.piles[from - 1].pop().unwrap(); + crates.piles[to - 1].push(c); + } + } + Ok(crates + .piles + .iter() + .map(|pile| pile.top().unwrap()) + .collect()) +} + +pub fn part1(crates: Crates) -> Result { + println!("{}", part1_str(crates)?); + Ok(0) +} + +fn part2_str(mut crates: Crates) -> Result { + for Instruction { count, from, to } in crates.instructions { + let mut tmp = vec![]; + for _ in 0..count { + let c = crates.piles[from - 1].pop().unwrap(); + tmp.push(c); + } + for c in tmp.iter().copied().rev() { + crates.piles[to - 1].push(c); + } + } + Ok(crates + .piles + .iter() + .map(|pile| pile.top().unwrap()) + .collect()) +} + +pub fn part2(crates: Crates) -> Result { + println!("{}", part2_str(crates)?); + Ok(0) +} + +#[test] +fn test() { + assert_eq!( + part1_str(parse(parse::data(2022, 5).unwrap()).unwrap()).unwrap(), + "PSNRGBTFT" + ); + assert_eq!( + part2_str(parse(parse::data(2022, 5).unwrap()).unwrap()).unwrap(), + "BNTZFPMMW" + ); +} diff --git a/src/bin/2022/day6.rs b/src/bin/2022/day6.rs new file mode 100644 index 0000000..6fe154f --- /dev/null +++ b/src/bin/2022/day6.rs @@ -0,0 +1,38 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result { + Ok(parse::string(fh)) +} + +pub fn part1(s: String) -> Result { + for (i, slice) in s.as_bytes().windows(4).enumerate() { + if slice.iter().copied().collect::>().len() == 4 { + return Ok(i + 4); + } + } + Err(anyhow!("couldn't find marker")) +} + +pub fn part2(s: String) -> Result { + for (i, slice) in s.as_bytes().windows(14).enumerate() { + if slice.iter().copied().collect::>().len() == 14 { + return Ok(i + 14); + } + } + Err(anyhow!("couldn't find marker")) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 6).unwrap()).unwrap()).unwrap(), + 1155 + ); + assert_eq!( + part2(parse(parse::data(2022, 6).unwrap()).unwrap()).unwrap(), + 2789 + ); +} diff --git a/src/bin/2022/day7.rs b/src/bin/2022/day7.rs new file mode 100644 index 0000000..d0101c9 --- /dev/null +++ b/src/bin/2022/day7.rs @@ -0,0 +1,136 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub enum Node { + Dir, + File(u64), +} + +impl Node { + fn new_dir() -> Self { + Self::Dir + } + + fn new_file(size: u64) -> Self { + Self::File(size) + } + + fn size(&self) -> u64 { + match self { + Self::Dir => 0, + Self::File(size) => *size, + } + } +} + +fn tree_size(tree: &Tree) -> u64 { + tree.bfs().map(|(_, tree)| tree.data().size()).sum() +} + +pub fn parse(fh: File) -> Result> { + let mut lines = parse::raw_lines(fh).peekable(); + let mut root = Tree::new(Node::Dir); + let mut path = vec![]; + + while let Some(cmdline) = lines.by_ref().next() { + let Some(captures) = ®ex_captures!( + r"^\$ (cd|ls)(?: (.*))?$", + &cmdline + ) + else { bail!("didn't match cmdline: '{}'", cmdline) }; + let Some(cmd) = captures.get(1) + else { bail!("no cmd found in cmdline: '{}'", cmdline) }; + + let pwd = root.at_mut(&path).unwrap(); + + match cmd.as_str() { + "cd" => { + let Some(arg) = captures.get(2) + else { bail!("no arg found for cd: '{}'", cmdline) }; + match arg.as_str() { + ".." => { + path.pop(); + } + "/" => path = vec![], + dirname => { + if pwd.at(&[dirname.to_string()]).is_none() { + pwd.add_child( + dirname.to_string(), + Node::new_dir(), + ); + } + path.push(dirname.to_string()); + } + } + } + "ls" => loop { + let Some(lsline) = lines.peek() + else { break }; + let Some(captures) = ®ex_captures!( + r"^(dir|[0-9]+) (.*)$", + lsline + ) + else { break }; + let Some(data) = captures.get(1) + else { break }; + let Some(name) = captures.get(2) + else { break }; + + let node = match data.as_str() { + "dir" => Node::new_dir(), + size => Node::new_file(size.parse().unwrap()), + }; + pwd.add_child(name.as_str().to_string(), node); + lines.next(); + }, + _ => unreachable!(), + } + } + + Ok(root) +} + +pub fn part1(tree: Tree) -> Result { + let mut total = 0; + for (_, tree) in tree.bfs() { + if matches!(tree.data(), Node::File(_)) { + continue; + } + let size = tree_size(tree); + if size <= 100_000 { + total += size; + } + } + Ok(total) +} + +pub fn part2(tree: Tree) -> Result { + let total = tree_size(&tree); + let free = 70_000_000 - total; + let needed = 30_000_000 - free; + let mut possible = vec![]; + for (_, tree) in tree.bfs() { + if matches!(tree.data(), Node::File(_)) { + continue; + } + let size = tree_size(tree); + if size > needed { + possible.push(size); + } + } + Ok(possible.iter().copied().min().unwrap()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 7).unwrap()).unwrap()).unwrap(), + 1297683 + ); + assert_eq!( + part2(parse(parse::data(2022, 7).unwrap()).unwrap()).unwrap(), + 5756764 + ); +} diff --git a/src/bin/2022/day8.rs b/src/bin/2022/day8.rs new file mode 100644 index 0000000..6ec110e --- /dev/null +++ b/src/bin/2022/day8.rs @@ -0,0 +1,156 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub fn parse(fh: File) -> Result> { + Ok(parse::digit_grid(parse::raw_lines(fh))) +} + +pub fn part1(trees: Grid) -> Result { + let mut total = 0; + for row in trees.each_row() { + 'tree: for col in trees.each_col() { + let tree = trees[row][col]; + + if trees + .each_col() + .take(col.0) + .all(|col| trees[row][col] < tree) + { + total += 1; + continue 'tree; + } + if trees + .each_col() + .skip(col.0 + 1) + .all(|col| trees[row][col] < tree) + { + total += 1; + continue 'tree; + } + if trees + .each_row() + .take(row.0) + .all(|row| trees[row][col] < tree) + { + total += 1; + continue 'tree; + } + if trees + .each_row() + .skip(row.0 + 1) + .all(|row| trees[row][col] < tree) + { + total += 1; + continue 'tree; + } + } + } + Ok(total) +} + +pub fn part2(trees: Grid) -> Result { + let mut max = 0; + for row in trees.each_row() { + for col in trees.each_col() { + let tree = trees[row][col]; + + let mut seen = false; + let left = trees + .each_col() + .take(col.0) + .rev() + .take_while(|col| { + if seen { + return false; + } + + let other = trees[row][*col]; + if other < tree { + true + } else { + seen = true; + true + } + }) + .count(); + + let mut seen = false; + let right = trees + .each_col() + .skip(col.0 + 1) + .take_while(|col| { + if seen { + return false; + } + + let other = trees[row][*col]; + if other < tree { + true + } else { + seen = true; + true + } + }) + .count(); + + let mut seen = false; + let up = trees + .each_row() + .take(row.0) + .rev() + .take_while(|row| { + if seen { + return false; + } + + let other = trees[*row][col]; + if other < tree { + true + } else { + seen = true; + true + } + }) + .count(); + + let mut seen = false; + let down = trees + .each_row() + .skip(row.0 + 1) + .take_while(|row| { + if seen { + return false; + } + + let other = trees[*row][col]; + if other < tree { + true + } else { + seen = true; + true + } + }) + .count(); + + let scenic = left * right * up * down; + if scenic > max { + max = scenic; + } + } + } + Ok(max) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 8).unwrap()).unwrap()).unwrap(), + 1851 + ); + assert_eq!( + part2(parse(parse::data(2022, 8).unwrap()).unwrap()).unwrap(), + 574080 + ); +} diff --git a/src/bin/2022/day9.rs b/src/bin/2022/day9.rs new file mode 100644 index 0000000..235ec44 --- /dev/null +++ b/src/bin/2022/day9.rs @@ -0,0 +1,236 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Debug)] +enum Direction { + Up, + Down, + Left, + Right, +} + +impl std::str::FromStr for Direction { + type Err = (); + + fn from_str(s: &str) -> Result { + Ok(match s { + "U" => Self::Up, + "D" => Self::Down, + "L" => Self::Left, + "R" => Self::Right, + _ => return Err(()), + }) + } +} + +#[derive(Debug)] +pub struct Move { + dir: Direction, + count: usize, +} + +impl Move { + fn parse(line: &str) -> Self { + let mut parts = line.split_whitespace(); + let dir = parts.next().unwrap().parse().unwrap(); + let count = parts.next().unwrap().parse().unwrap(); + Self { dir, count } + } +} + +pub struct Rope { + knots: Vec<(Row, Col)>, +} + +impl Rope { + pub fn new(len: usize) -> Self { + Self { + knots: vec![Default::default(); len], + } + } + + pub fn at(&self, pos: (Row, Col)) -> Option { + for (i, knot) in self.knots.iter().enumerate() { + if knot == &pos { + return Some(i); + } + } + None + } +} + +pub struct Map { + grid: std::collections::VecDeque>, + size: (Row, Col), + rope: Rope, +} + +impl std::fmt::Debug for Map { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + writeln!(f, "({}, {})", self.size.0 .0, self.size.1 .0)?; + for row in (0..self.size.0 .0).rev() { + for col in 0..self.size.1 .0 { + write!( + f, + "{}", + if let Some(idx) = self.rope.at((Row(row), Col(col))) { + char::from(b'0' + u8::try_from(idx).unwrap()) + } else if self.grid[row][col] { + '#' + } else { + '.' + } + )?; + } + writeln!(f)?; + } + Ok(()) + } +} + +impl Map { + fn new(len: usize) -> Self { + let mut grid = std::collections::VecDeque::new(); + grid.push_back(std::collections::VecDeque::new()); + grid[0].push_back(true); + Self { + grid, + size: (Row(1), Col(1)), + rope: Rope::new(len), + } + } + + fn mv(&mut self, mv: &Move) { + // println!("{:?}", mv); + for _ in 0..mv.count { + self.step(&mv.dir); + } + } + + fn step(&mut self, dir: &Direction) { + let (Row(row), Col(col)) = self.rope.knots[0]; + match dir { + Direction::Up => { + if row == self.size.0 .0 - 1 { + let mut row_contents = std::collections::VecDeque::new(); + row_contents + .resize_with(self.size.1 .0, Default::default); + self.grid.push_back(row_contents); + self.size.0 = Row(self.size.0 .0 + 1); + } + self.rope.knots[0].0 = Row(self.rope.knots[0].0 .0 + 1); + } + Direction::Down => { + if row == 0 { + let mut row_contents = std::collections::VecDeque::new(); + row_contents + .resize_with(self.size.1 .0, Default::default); + self.grid.push_front(row_contents); + for knot in &mut self.rope.knots { + knot.0 = Row(knot.0 .0 + 1); + } + self.size.0 = Row(self.size.0 .0 + 1); + } + self.rope.knots[0].0 = Row(self.rope.knots[0].0 .0 - 1); + } + Direction::Left => { + if col == 0 { + for i in 0..self.size.0 .0 { + self.grid[i].push_front(Default::default()); + } + for knot in &mut self.rope.knots { + knot.1 = Col(knot.1 .0 + 1); + } + self.size.1 = Col(self.size.1 .0 + 1); + } + self.rope.knots[0].1 = Col(self.rope.knots[0].1 .0 - 1); + } + Direction::Right => { + if col == self.size.1 .0 - 1 { + for i in 0..self.size.0 .0 { + self.grid[i].push_back(Default::default()); + } + self.size.1 = Col(self.size.1 .0 + 1); + } + self.rope.knots[0].1 = Col(self.rope.knots[0].1 .0 + 1); + } + } + + for i in 0..(self.rope.knots.len() - 1) { + if self.rope.knots[i + 1] + .0 + .0 + .abs_diff(self.rope.knots[i].0 .0) + > 1 + || self.rope.knots[i + 1] + .1 + .0 + .abs_diff(self.rope.knots[i].1 .0) + > 1 + { + if self.rope.knots[i + 1].0 .0 < self.rope.knots[i].0 .0 { + self.rope.knots[i + 1].0 .0 += 1; + } + if self.rope.knots[i + 1].0 .0 > self.rope.knots[i].0 .0 { + self.rope.knots[i + 1].0 .0 -= 1; + } + if self.rope.knots[i + 1].1 .0 < self.rope.knots[i].1 .0 { + self.rope.knots[i + 1].1 .0 += 1; + } + if self.rope.knots[i + 1].1 .0 > self.rope.knots[i].1 .0 { + self.rope.knots[i + 1].1 .0 -= 1; + } + } + } + self.grid[self.rope.knots.last().unwrap().0 .0] + [self.rope.knots.last().unwrap().1 .0] = true; + } +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::raw_lines(fh).map(|line| Move::parse(&line))) +} + +pub fn part1(moves: impl Iterator) -> Result { + let mut map = Map::new(2); + for mv in moves { + // println!("{:?}", map); + map.mv(&mv); + } + // println!("{:?}", map); + Ok(map + .grid + .iter() + .flat_map(|row| row.iter().copied()) + .filter(|cell| *cell) + .count()) +} + +pub fn part2(moves: impl Iterator) -> Result { + let mut map = Map::new(10); + for mv in moves { + // println!("{:?}", map); + map.mv(&mv); + } + // println!("{:?}", map); + Ok(map + .grid + .iter() + .flat_map(|row| row.iter().copied()) + .filter(|cell| *cell) + .count()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 9).unwrap()).unwrap()).unwrap(), + 6037 + ); + assert_eq!( + part2(parse(parse::data(2022, 9).unwrap()).unwrap()).unwrap(), + 2485 + ); +} diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs new file mode 100644 index 0000000..09a9248 --- /dev/null +++ b/src/bin/2022/main.rs @@ -0,0 +1,46 @@ +#![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 day2; +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!(2022, opt.day, opt.puzzle, day1), + 2 => advent_of_code::day!(2022, opt.day, opt.puzzle, day2), + 3 => advent_of_code::day!(2022, opt.day, opt.puzzle, day3), + 4 => advent_of_code::day!(2022, opt.day, opt.puzzle, day4), + 5 => advent_of_code::day!(2022, opt.day, opt.puzzle, day5), + 6 => advent_of_code::day!(2022, opt.day, opt.puzzle, day6), + 7 => advent_of_code::day!(2022, opt.day, opt.puzzle, day7), + 8 => advent_of_code::day!(2022, opt.day, opt.puzzle, day8), + 9 => advent_of_code::day!(2022, opt.day, opt.puzzle, day9), + 10 => advent_of_code::day!(2022, opt.day, opt.puzzle, day10), + 11 => advent_of_code::day!(2022, opt.day, opt.puzzle, day11), + // NEXT PART + _ => panic!("unknown day {}", opt.day), + } + Ok(()) +} -- cgit v1.2.3-54-g00ecf