Skip to content

Instantly share code, notes, and snippets.

@forrestthewoods

forrestthewoods/aoc2020_complete.rs

Created December 25, 2020 23:35
Show Gist options
  • Save forrestthewoods/a46ea526af8e3d951c6992c793711926 to your computer and use it in GitHub Desktop.
Save forrestthewoods/a46ea526af8e3d951c6992c793711926 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
aoc2020_complete.rs
mod data;
/*
pub mod day00 {
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY00);
writeln!(&mut result, "Day 00, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY00);
writeln!(&mut result, "Day 00, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn part1(_input: &str) -> usize {
0
}
fn part2(_input: &str) -> usize {
0
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
}
#[test]
fn verify() {
}
}
}
*/
mod util {
pub trait StripCarriageReturn {
fn strip_carriage_return(&self) -> String;
}
impl StripCarriageReturn for &str {
fn strip_carriage_return(&self) -> String {
self.replace("\r", "")
}
}
}
pub mod game_console {
use itertools::Itertools;
use std::collections::HashSet;
#[derive(Copy, Clone)]
pub enum Op {
Acc(isize),
Jmp(isize),
Nop(isize),
}
#[derive(Copy, Clone)]
pub enum RunResult {
Loop(isize),
Finish(isize),
}
#[derive(Clone)]
pub struct GameConsole {
instruction_ptr: isize,
accumulator: isize,
pub ops: Vec<Op>,
}
impl From<&str> for Op {
#[inline]
fn from(line: &str) -> Op {
let (op, arg) = line.split(" ").collect_tuple().unwrap();
let arg: isize = arg.parse().unwrap();
match op {
"acc" => Op::Acc(arg),
"jmp" => Op::Jmp(arg),
"nop" => Op::Nop(arg),
_ => unreachable!("Unexpected op string [{}]", op),
}
}
}
impl GameConsole {
pub fn new(input: &str) -> GameConsole {
GameConsole {
instruction_ptr: 0,
accumulator: 0,
ops: input.lines().map_into::<Op>().collect(),
}
}
pub fn run(&mut self) -> RunResult {
let mut visited: HashSet<isize> = Default::default();
loop {
// Test for end of program
if self.instruction_ptr == self.ops.len() as isize {
return RunResult::Finish(self.accumulator);
}
// Test for infinite loop
if !visited.insert(self.instruction_ptr) {
return RunResult::Loop(self.accumulator);
}
// Execute next instruction
match &self.ops[self.instruction_ptr as usize] {
Op::Acc(value) => {
self.accumulator += value;
self.instruction_ptr += 1;
}
Op::Jmp(value) => {
self.instruction_ptr += value;
}
Op::Nop(_) => self.instruction_ptr += 1,
}
}
}
}
}
pub mod day01 {
use itertools::Itertools;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let nums = parse_data(crate::data::DAY01);
let answer_part1 = part1(&nums);
writeln!(&mut result, "Day 1, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&nums);
writeln!(&mut result, "Day 1, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_data(data: &str) -> Vec<i32> {
data.lines()
.map(|s| s.parse::<i32>().unwrap())
.sorted()
.collect()
}
// nums must be sorted
fn part1(nums: &[i32]) -> i32 {
let mut lo = 0;
let mut hi = nums.len() - 1;
while nums[lo] + nums[hi] != 2020 {
if nums[lo] + nums[hi] < 2020 {
lo += 1;
} else {
hi -= 1;
}
}
nums[lo] * nums[hi]
}
// nums must be sorted
fn part2(nums: &[i32]) -> i32 {
let mut hi = 2;
loop {
let mut lo = 0;
while lo < hi - 1 {
let a = nums[lo];
let c = nums[hi];
// Too far
if a + c > 2020 {
break;
}
// Not far enough
let b = 2020 - a - c;
if b > c {
break;
}
// Does B exist?
if let Ok(_) = &nums[lo + 1..hi].binary_search(&b) {
return a * b * c;
}
lo += 1;
}
hi += 1;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let test_data = "1721\n979\n366\n299\n675\n1456";
let test_nums = parse_data(test_data);
assert_eq!(part1(&test_nums), 514579); // 299 * 1721 = 514579
assert_eq!(part2(&test_nums), 241861950); // 366 * 675 * 979 = 241861950
}
#[test]
fn verify() {
let data = crate::data::DAY01;
let nums = parse_data(data);
assert_eq!(part1(&nums), 121396);
assert_eq!(part2(&nums), 73616634); // 117 * 426 * 1477
}
}
}
pub mod day02 {
use lazy_static::lazy_static;
use regex::Regex;
use std::fmt::Write;
struct Entry {
lo: usize,
hi: usize,
letter: char,
password: String,
}
pub fn run() -> String {
let mut result = String::with_capacity(128);
let entries = parse_data(crate::data::DAY02);
let answer_part1 = part1(&entries);
writeln!(&mut result, "Day 2, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&entries);
writeln!(&mut result, "Day 2, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_data(data: &str) -> Vec<Entry> {
lazy_static! {
static ref REGEX: Regex =
Regex::new(r"(?P<lo>\d+)-(?P<hi>\d+) (?P<letter>[a-z]): (?P<password>[a-z]+)")
.unwrap();
}
data.lines()
.map(|line| {
let caps = REGEX.captures(line).unwrap();
Entry {
lo: caps["lo"].parse().unwrap(),
hi: caps["hi"].parse().unwrap(),
letter: caps["letter"].parse().unwrap(),
password: caps["password"].parse().unwrap(),
}
})
.collect()
}
fn part1(entries: &[Entry]) -> usize {
entries
.iter()
.filter(|entry| {
let char_count = entry
.password
.chars()
.filter(|&c| c == entry.letter)
.count();
char_count >= entry.lo && char_count <= entry.hi
})
.count()
}
fn part2(entries: &[Entry]) -> usize {
entries
.iter()
.filter(|entry| {
let bytes = entry.password.as_bytes();
let lo = bytes[entry.lo - 1] as char;
let hi = bytes[entry.hi - 1] as char;
(lo == entry.letter) ^ (hi == entry.letter)
})
.count()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let test_data = "1-3 a: abcde\n1-3 b: cdefg\n2-9 c: ccccccccc";
let data = parse_data(test_data);
assert_eq!(part1(&data), 2);
assert_eq!(part2(&data), 1);
}
#[test]
fn verify() {
let data = parse_data(crate::data::DAY02);
assert_eq!(part1(&data), 398);
assert_eq!(part2(&data), 562);
}
}
}
pub mod day03 {
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let (trees, width) = parse_data(crate::data::DAY03);
let answer_part1 = part1(&trees, width);
writeln!(&mut result, "Day 3, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&trees, width);
writeln!(&mut result, "Day 3, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_data(data: &str) -> (Vec<bool>, usize) {
// Width of first line
let width = data.lines().next().unwrap().len();
// # == tree
let trees = data
.lines()
.flat_map(|line| line.chars())
.map(|c| c == '#')
.collect();
(trees, width)
}
fn part1(trees: &[bool], width: usize) -> usize {
const X_STEP: usize = 3;
const Y_STEP: usize = 1;
test_slope(trees, width, X_STEP, Y_STEP)
}
fn part2(trees: &[bool], width: usize) -> usize {
let slopes: Vec<(usize, usize)> = vec![(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)];
let result = slopes
.iter()
.map(|(slope_x, slope_y)| test_slope(trees, width, *slope_x, *slope_y))
.product();
result
}
fn test_slope(trees: &[bool], width: usize, slope_x: usize, slope_y: usize) -> usize {
let height = trees.len() / width;
let num_steps = height / slope_y;
(1..num_steps)
.map(|step| step * slope_y * width + (step * slope_x) % width)
.filter(|&idx| trees[idx])
.count()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let test_data = "..##.......\n#...#...#..\n.#....#..#.\n..#.#...#.#\n.#...##..#.\n..#.##.....\n.#.#.#....#\n.#........#\n#.##...#...\n#...##....#\n.#..#...#.#";
let (trees, width) = parse_data(test_data);
assert_eq!(part1(&trees, width), 7);
assert_eq!(part2(&trees, width), 336);
}
#[test]
fn verify() {
let (trees, width) = parse_data(crate::data::DAY03);
assert_eq!(part1(&trees, width), 184);
assert_eq!(part2(&trees, width), 2431272960);
}
}
}
pub mod day04 {
use itertools::Itertools;
use std::collections::{HashMap, HashSet};
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY04);
writeln!(&mut result, "Day 4, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY04);
writeln!(&mut result, "Day 4, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn part1(raw_data: &str) -> usize {
let required_keys: HashSet<_> = vec!["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]
.into_iter()
.collect();
raw_data
.lines()
.group_by(|line| line.trim().is_empty())
.into_iter()
.filter(|(empty, _)| !empty)
.map(|(_, group)| {
group
.into_iter()
.flat_map(|l| l.split_whitespace())
.map(|kvp| kvp.split(":").next().unwrap())
.collect::<HashSet<&str>>()
})
.filter(|keys| required_keys.iter().all(|key| keys.contains(key)))
.count()
}
fn part2(raw_data: &str) -> usize {
let required_keys: HashSet<_> = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]
.iter()
.collect();
let valid_eye_colors: HashSet<_> = ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"]
.iter()
.collect();
raw_data
.lines()
.group_by(|line| line.trim().is_empty())
.into_iter()
.filter(|(empty, _)| !empty)
.map(|(_, group)| {
group
.into_iter()
.flat_map(|l| l.split_whitespace())
.map(|kvp| kvp.split(":").tuples().next().unwrap())
.collect::<HashMap<&str, &str>>()
})
.filter(|keys| {
required_keys.iter().all(|&key| {
match keys.get(key) {
Some(value) => {
let valid = match *key {
"byr" => value
.parse::<i32>()
.map_or(false, |year| (1920..=2002).contains(&year)),
"iyr" => value
.parse::<i32>()
.map_or(false, |year| (2010..=2020).contains(&year)),
"eyr" => value
.parse::<i32>()
.map_or(false, |year| (2020..=2030).contains(&year)),
"hgt" => {
let n = value.len() - 2;
let height = (&value[..n]).parse::<i32>().unwrap_or(0);
let height_str = &value[n..];
match height_str {
"cm" => (150..=193).contains(&height),
"in" => (59..=76).contains(&height),
_ => false,
}
}
"hcl" => {
let value_bytes = value.as_bytes();
value_bytes.len() == 7
&& value_bytes[0] == '#' as u8
&& value_bytes
.iter()
.skip(1)
.all(|&b| b.is_ascii_hexdigit())
}
"ecl" => valid_eye_colors.contains(value),
"pid" => {
value.len() == 9
&& value.as_bytes().iter().all(|&v| v.is_ascii_digit())
}
"cid" => true, // always valid
_ => false, // required key not present
};
valid
}
None => false,
}
})
})
.count()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1(crate::data::_DAY04_EXAMPLE_1), 2);
assert_eq!(part2(crate::data::_DAY04_EXAMPLE_2), 0);
assert_eq!(part2(crate::data::_DAY04_EXAMPLE_3), 4);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY04), 247);
assert_eq!(part2(crate::data::DAY04), 145);
}
}
}
pub mod day05 {
use itertools::Itertools;
use std::collections::HashSet;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY05);
writeln!(&mut result, "Day 5, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY05);
writeln!(&mut result, "Day 5, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn pos_from_pass(pass: &str) -> (u32, u32) {
let row = pass
.chars()
.take(7)
.map(|c| if c == 'B' { 1 } else { 0 })
.fold(0, |acc, v| acc << 1 | v);
let col = pass
.chars()
.skip(7)
.map(|c| if c == 'R' { 1 } else { 0 })
.fold(0, |acc, v| acc << 1 | v);
(row, col)
}
fn id_from_pos(pos: (u32, u32)) -> u32 {
pos.0 * 8 + pos.1
}
fn id_from_pass(pass: &str) -> u32 {
let pos = pos_from_pass(pass);
id_from_pos(pos)
}
fn part1(input: &str) -> u32 {
input.lines().map(|line| id_from_pass(line)).max().unwrap()
}
fn part2(input: &str) -> u32 {
let mut seats: HashSet<u32> = Default::default();
let mut min_row = 127;
let mut max_row = 0;
for line in input.lines() {
let pos = pos_from_pass(line);
min_row = std::cmp::min(pos.0, min_row);
max_row = std::cmp::max(pos.0, max_row);
seats.insert(id_from_pos(pos));
}
let all_seats: HashSet<u32> = (min_row + 1..=max_row - 1)
.cartesian_product(0..=7)
.map(|pos| id_from_pos(pos))
.collect();
let missing_seats: Vec<_> = all_seats.difference(&seats).collect();
assert!(missing_seats.len() == 1);
*missing_seats[0]
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(id_from_pass("FBFBBFFRLR"), 357);
assert_eq!(id_from_pass("BFFFBBFRRR"), 567);
assert_eq!(id_from_pass("FFFBBBFRRR"), 119);
assert_eq!(id_from_pass("BBFFBBFRLL"), 820);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY05), 980);
assert_eq!(part2(crate::data::DAY05), 607);
}
}
}
pub mod day06 {
use crate::util::*;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let data = crate::data::DAY06.strip_carriage_return();
let answer_part1 = part1(&data);
writeln!(&mut result, "Day 6, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&data);
writeln!(&mut result, "Day 6, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn mask_from_char(c: char) -> u32 {
1u32 << (c as u32 - 'a' as u32)
}
fn part1(data: &str) -> u32 {
data.split("\n\n")
.map(|group| {
group
.split_whitespace()
.flat_map(|person| person.chars())
.map(|c| mask_from_char(c))
.fold(0u32, |acc, v| acc | v)
.count_ones()
})
.sum()
}
fn part2(data: &str) -> u32 {
data.split("\n\n")
.map(|group| {
group
.split_whitespace()
.map(|person| {
person
.chars()
.map(|c| mask_from_char(c))
.fold(0, |acc, v| acc | v)
})
.fold(std::u32::MAX, |acc, p| acc & p)
.count_ones()
})
.sum()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let data = crate::data::_DAY06_EXAMPLE_1.strip_carriage_return();
assert_eq!(part1(&data), 11);
assert_eq!(part2(&data), 6);
}
#[test]
fn verify() {
let data = crate::data::DAY06.strip_carriage_return();
assert_eq!(part1(&data), 6549);
assert_eq!(part2(&data), 3466);
}
}
}
pub mod day07 {
use petgraph::prelude::*;
use regex::Regex;
use std::collections::HashMap;
use std::fmt::Write;
type BagGraph<'a> = petgraph::Graph<&'a str, usize, petgraph::Directed, u32>;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let graph = build_graph(crate::data::DAY07);
let answer_part1 = part1(&graph);
writeln!(&mut result, "Day 7, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&graph);
writeln!(&mut result, "Day 7, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn build_graph(data: &str) -> BagGraph {
let bag_re = Regex::new(r"(.+) bags contain").unwrap();
let children_re = Regex::new(r"(\d+) (.+?) bags?[,.]").unwrap();
let mut graph = BagGraph::new();
let mut nodes: HashMap<&str, NodeIndex<u32>> = Default::default();
for line in data.lines() {
let caps = bag_re.captures(line).unwrap();
let bag = &caps.get(1).unwrap().as_str();
let parent_idx = *nodes.entry(bag).or_insert_with(|| graph.add_node(bag));
for child_cap in children_re.captures_iter(line) {
let child_count: usize = child_cap.get(1).unwrap().as_str().parse().unwrap();
let child_name: &str = child_cap.get(2).unwrap().as_str();
let child_idx = *nodes
.entry(child_name)
.or_insert_with(|| graph.add_node(child_name));
graph.add_edge(parent_idx, child_idx, child_count);
}
}
graph
}
fn part1(graph: &BagGraph) -> usize {
let shiny_gold_idx = graph
.node_indices()
.find(|i| graph[*i] == "shiny gold")
.unwrap();
let mut space = petgraph::algo::DfsSpace::new(&graph);
graph
.node_indices()
.filter(|&idx| idx != shiny_gold_idx)
.filter(|&idx| {
petgraph::algo::has_path_connecting(&graph, idx, shiny_gold_idx, Some(&mut space))
})
.count()
}
fn part2(graph: &BagGraph) -> usize {
let shiny_gold_idx = graph
.node_indices()
.find(|i| graph[*i] == "shiny gold")
.unwrap();
let mut nodes = vec![(1, shiny_gold_idx)];
let mut sum = 0;
while !nodes.is_empty() {
let (parent_count, node_idx) = nodes.pop().unwrap();
for edge in graph.edges_directed(node_idx, petgraph::Direction::Outgoing) {
sum += parent_count * edge.weight();
nodes.push((parent_count * edge.weight(), edge.target()));
}
}
sum
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let graph1 = build_graph(crate::data::_DAY07_EXAMPLE_1);
let graph2 = build_graph(crate::data::_DAY07_EXAMPLE_2);
assert_eq!(part1(&graph1), 4);
assert_eq!(part2(&graph1), 32);
assert_eq!(part2(&graph2), 126);
}
#[test]
fn verify() {
let graph = build_graph(crate::data::DAY07);
assert_eq!(part1(&graph), 335);
assert_eq!(part2(&graph), 2431);
}
}
}
pub mod day08 {
use crate::game_console::*;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY08);
writeln!(&mut result, "Day 8, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY08);
writeln!(&mut result, "Day 8, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn part1(data: &str) -> isize {
let mut game_console = GameConsole::new(data);
let result = game_console.run();
match result {
RunResult::Loop(value) => return value,
_ => unreachable!("Day08 part1 expected an infinite loop"),
}
}
fn part2(data: &str) -> isize {
let base_console = GameConsole::new(data);
let mut console = base_console.clone();
for i in 0..console.ops.len() {
let op = &mut console.ops[i];
match op {
Op::Jmp(value) => *op = Op::Nop(*value),
Op::Nop(value) => *op = Op::Jmp(*value),
_ => continue,
}
match console.run() {
RunResult::Finish(value) => return value,
_ => (),
}
console = base_console.clone()
}
unreachable!("Day08 Part2 failed to find a solution");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1(crate::data::_DAY08_EXAMPLE_1), 5);
assert_eq!(part2(crate::data::_DAY08_EXAMPLE_1), 8);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY08), 1446);
assert_eq!(part2(crate::data::DAY08), 1403);
}
}
}
pub mod day09 {
use itertools::Itertools;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let nums = parse_input(crate::data::DAY09);
let answer_part1 = part1(&nums, 25);
writeln!(&mut result, "Day 9, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&nums, 69316178);
writeln!(&mut result, "Day 9, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_input(input: &str) -> Vec<i64> {
input.lines().map(|line| line.parse().unwrap()).collect()
}
fn part1(data: &[i64], n: usize) -> i64 {
// returns true if sorted nums contains pair that sums to value
let check_slice = |nums: &[i64], v: i64| -> bool {
let mut lo = 0;
let mut hi = nums.len() - 1;
while lo < hi {
let a = nums[lo];
let b = nums[hi];
let s = a + b;
if s == v {
return true;
} else if s > v {
hi -= 1;
} else {
lo += 1;
}
// sum can not possibly be found within [lo..=hi]
if a > v || b < v / 2 {
break;
}
}
false
};
// removes a number and adds a number. slice sorted before and after
let slide_slice = |nums: &mut [i64], to_remove: i64, to_add: i64| {
let idx = nums.binary_search(&to_remove).unwrap();
nums[idx] = to_add;
nums.sort_unstable();
};
// initialize window
let mut nums: Vec<i64> = data[..n].iter().cloned().sorted().collect();
for i in n..data.len() {
let v = data[i];
if !check_slice(&nums, v) {
return v;
}
let to_remove = data[i - n];
slide_slice(&mut nums, to_remove, v);
}
unreachable!("Failed to find answer");
}
fn part2(data: &[i64], sum: i64) -> i64 {
for i in 0..data.len() - 2 {
let mut j = i + 1;
let mut slice_sum: i64 = data[i];
while j < data.len() {
// grow slice
slice_sum += data[j];
// found slice
if slice_sum == sum {
let (min, max) = data[i..j + 1].iter().minmax().into_option().unwrap();
return min + max;
}
// slice sum is too large, early out
if slice_sum >= sum {
break;
}
j += 1;
}
}
unreachable!("Failed to find answer");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn example() {
let nums = parse_input(crate::data::_DAY09_EXAMPLE_1);
assert_eq!(part1(&nums, 5), 127);
assert_eq!(part2(&nums, 127), 62);
}
#[test]
fn verify() {
let nums = parse_input(crate::data::DAY09);
assert_eq!(part1(&nums, 25), 69316178);
assert_eq!(part2(&nums, 69316178), 9351526);
}
}
}
pub mod day10 {
use std::collections::HashMap;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let nums = parse_input(crate::data::DAY10);
let answer_part1 = part1(&nums);
writeln!(&mut result, "Day 10, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&nums);
writeln!(&mut result, "Day 10, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_input(input: &str) -> Vec<u8> {
let mut nums: Vec<_> = Default::default();
nums.push(0);
nums.extend(input.lines().map(|l| l.parse::<u8>().unwrap()));
nums.push(*nums.iter().max().unwrap() + 3);
nums.sort();
nums
}
fn part1(nums: &[u8]) -> usize {
let counts = nums
.windows(2)
.map(|window| window[1] - window[0])
.fold((0, 0), |acc, diff| {
(acc.0 + (diff == 1) as usize, acc.1 + (diff == 3) as usize)
});
counts.0 * counts.1
}
fn part2(nums: &[u8]) -> usize {
fn recursive_calc(jolts: u8, nums: &[u8], memo: &mut HashMap<u8, usize>) -> usize {
if let Some(count) = memo.get(&jolts) {
*count
} else {
let sum = (1..=3)
.map(|offset| jolts + offset)
.filter(|next_jolts| nums.binary_search(&next_jolts).is_ok())
.map(|next_jolts| recursive_calc(next_jolts, nums, memo))
.sum::<usize>()
.max(1);
memo.insert(jolts, sum);
sum
}
}
let mut memo: HashMap<u8, usize> = Default::default();
let result = recursive_calc(nums[0], nums, &mut memo);
result
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1(&parse_input(crate::data::_DAY10_EXAMPLE_1)), 35);
assert_eq!(part1(&parse_input(crate::data::_DAY10_EXAMPLE_2)), 220);
assert_eq!(part2(&parse_input(crate::data::_DAY10_EXAMPLE_1)), 8);
assert_eq!(part2(&parse_input(crate::data::_DAY10_EXAMPLE_2)), 19208);
}
#[test]
fn verify() {
let nums = parse_input(crate::data::DAY10);
assert_eq!(part1(&nums), 1656);
assert_eq!(part2(&nums), 56693912375296);
}
}
}
pub mod day11 {
use fts_vecmath::point2::*;
use fts_vecmath::vector2::*;
use std::collections::hash_map::DefaultHasher;
use std::collections::HashSet;
use std::fmt::Write;
use std::hash::Hasher;
const FLOOR: u8 = '.' as u8;
const EMPTY: u8 = 'L' as u8;
const OCCUPIED: u8 = '#' as u8;
type Pos = Point2<isize>;
type Offset = Vector2<isize>;
const OFFSETS: [Offset; 8] = [
Offset { x: -1, y: -1 },
Offset { x: 0, y: -1 },
Offset { x: 1, y: -1 },
Offset { x: -1, y: 0 },
Offset { x: 1, y: 0 },
Offset { x: -1, y: 1 },
Offset { x: 0, y: 1 },
Offset { x: 1, y: 1 },
];
pub fn run() -> String {
let mut result = String::with_capacity(128);
let (grid, width) = parse_input(crate::data::DAY11);
let answer_part1 = part1(&grid, width);
writeln!(&mut result, "Day 11, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&grid, width);
writeln!(&mut result, "Day 11, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_input(input: &str) -> (Vec<u8>, isize) {
let width = input.lines().next().unwrap().chars().count();
let grid: Vec<u8> = input
.lines()
.flat_map(|l| l.chars())
.map(|c| c as u8)
.collect();
(grid, width as isize)
}
fn part1(grid: &[u8], width: isize) -> usize {
let mut states: HashSet<u64> = Default::default();
let height = grid.len() as isize / width;
let mut grid: Vec<u8> = grid.iter().cloned().collect();
let mut next_grid: Vec<u8> = grid.clone();
loop {
let mut hasher = DefaultHasher::new();
hasher.write(&grid);
let hash = hasher.finish();
if !states.insert(hash) {
return grid.iter().filter(|&&seat| seat == OCCUPIED).count();
}
for row in 0..height {
for col in 0..width {
let idx = (row * width + col) as usize;
if grid[idx] == FLOOR {
continue;
}
let pos = Pos::new(col, row);
let num_occupied = OFFSETS
.iter()
.map(|&offset| pos + offset)
.filter(|p| (0..width).contains(&p.x) && (0..height).contains(&p.y))
.map(|p| (p.y * width + p.x) as usize)
.filter(|&idx| grid[idx] == OCCUPIED)
.count();
if grid[idx] == EMPTY && num_occupied == 0 {
next_grid[idx] = OCCUPIED;
} else if grid[idx] == OCCUPIED && num_occupied >= 4 {
next_grid[idx] = EMPTY;
} else {
next_grid[idx] = grid[idx];
}
}
}
std::mem::swap(&mut grid, &mut next_grid);
}
}
fn part2(grid: &[u8], width: isize) -> usize {
let mut states: HashSet<u64> = Default::default();
let height = grid.len() as isize / width;
let mut grid: Vec<u8> = grid.iter().cloned().collect();
let mut next_grid: Vec<u8> = grid.clone();
let is_valid_pos = |p: Pos| (0..width).contains(&p.x) && (0..height).contains(&p.y);
loop {
let mut hasher = DefaultHasher::new();
hasher.write(&grid);
let hash = hasher.finish();
if !states.insert(hash) {
return grid.iter().filter(|&&seat| seat == OCCUPIED).count();
}
for row in 0..height {
for col in 0..width {
let idx = (row * width + col) as usize;
if grid[idx] == FLOOR {
continue;
}
let pos = Pos::new(col, row);
// This is the simple version that is easy to understand and is fast
let mut num_occupied = 0;
for &offset in &OFFSETS {
let mut p = pos;
loop {
p += offset;
if !is_valid_pos(p) {
break;
}
let idx = (p.y * width + p.x) as usize;
let tile = grid[idx];
if tile == OCCUPIED {
num_occupied += 1;
break;
} else if tile == EMPTY {
break;
}
}
}
/*
// This is the overcomplicated iterator version that is twice as slow
let num_occupied = OFFSETS
.iter()
.filter_map(|&offset| {
[offset]
.iter()
.cycle()
.enumerate()
.map(|(i, &offset)| pos + offset * (i + 1) as isize)
.take_while(|&pos| is_valid_pos(pos))
.map(|pos| grid[(pos.y * width + pos.x) as usize])
.filter(|&tile| tile != FLOOR)
.take_while(|&tile| tile == OCCUPIED)
.next()
})
.count();
*/
// This is a still overcomplicated version that is also twice as slow
/*
let num_occupied = OFFSETS
.iter()
.filter_map(|&offset| {
(1..).map(|i| pos + offset * i)
.take_while(|&pos| is_valid_pos(pos))
.map(|pos| grid[(pos.y * width + pos.x) as usize])
.filter(|&tile| tile != FLOOR)
.take_while(|&tile| tile == OCCUPIED)
.next()
})
.count();
*/
if grid[idx] == EMPTY && num_occupied == 0 {
next_grid[idx] = OCCUPIED;
} else if grid[idx] == OCCUPIED && num_occupied >= 5 {
next_grid[idx] = EMPTY;
} else {
next_grid[idx] = grid[idx];
}
}
}
std::mem::swap(&mut grid, &mut next_grid);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let (grid, width) = parse_input(crate::data::_DAY11_EXAMPLE_1);
assert_eq!(part1(&grid, width), 37);
assert_eq!(part2(&grid, width), 26);
}
#[test]
fn verify() {
let (grid, width) = parse_input(crate::data::DAY11);
assert_eq!(part1(&grid, width), 2361);
assert_eq!(part2(&grid, width), 2119);
}
}
}
pub mod day12 {
use fts_vecmath::point2::*;
use fts_vecmath::vector2::*;
use std::fmt::Write;
type Pos = Point2<i32>;
type Dir = Vector2<i32>;
type RotMat = (i32, i32, i32, i32);
#[derive(Copy, Clone)]
enum Action {
North = 0,
East,
South,
West,
Left,
Right,
Forward,
}
const COMPASS: [Action; 4] = [Action::North, Action::East, Action::South, Action::West];
const FACING_DIR: [Dir; 4] = [
Dir { x: 0, y: 1 },
Dir { x: 1, y: 0 },
Dir { x: 0, y: -1 },
Dir { x: -1, y: 0 },
];
// Rotation Matrix
// cosθ -sinθ -> 0 1
// sin0 cos0 2 3
const ROTATE_LEFT: [RotMat; 3] = [
(0, -1, 1, 0), // 90
(-1, 0, 0, -1), // 180
(0, 1, -1, 0), // 270
];
const ROTATE_RIGHT: [RotMat; 3] = [
(0, 1, -1, 0), // -90
(-1, 0, 0, -1), // -180
(0, -1, 1, 0), // -270
];
fn rotate(rot: RotMat, dir: Dir) -> Dir {
Dir::new(dir.x * rot.0 + dir.y * rot.1, dir.x * rot.2 + dir.y * rot.3)
}
impl From<char> for Action {
fn from(c: char) -> Action {
match c {
'N' => Action::North,
'E' => Action::East,
'S' => Action::South,
'W' => Action::West,
'L' => Action::Left,
'R' => Action::Right,
'F' => Action::Forward,
_ => unreachable!("Unexpected value [{}]", c),
}
}
}
pub fn run() -> String {
let mut result = String::with_capacity(128);
let data = parse_input(crate::data::DAY12);
let answer_part1 = part1(&data);
writeln!(&mut result, "Day 12, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&data);
writeln!(&mut result, "Day 12, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse_input(input: &str) -> Vec<(Action, i32)> {
input
.lines()
.map(|line| {
(
line.chars().next().unwrap().into(),
line[1..].parse().unwrap(),
)
})
.collect()
}
fn part1(data: &[(Action, i32)]) -> i32 {
let mut pos = Pos::new(0, 0);
let mut facing = Action::East;
for (action, value) in data {
match action {
Action::North => pos.y += value,
Action::South => pos.y -= value,
Action::East => pos.x += value,
Action::West => pos.x -= value,
Action::Forward => pos += FACING_DIR[facing as usize] * value,
Action::Left => {
facing = COMPASS[(facing as i32 - value / 90).rem_euclid(4) as usize]
}
Action::Right => {
facing = COMPASS[(facing as i32 + value / 90).rem_euclid(4) as usize]
}
}
}
pos.x.abs() + pos.y.abs()
}
fn part2(data: &[(Action, i32)]) -> i32 {
let mut pos = Pos::new(0, 0);
let mut waypoint = Dir::new(10, 1);
for (action, value) in data {
match action {
Action::North => waypoint.y += value,
Action::South => waypoint.y -= value,
Action::East => waypoint.x += value,
Action::West => waypoint.x -= value,
Action::Forward => pos += waypoint * value,
Action::Left => {
waypoint = rotate(ROTATE_LEFT[(*value / 90) as usize - 1], waypoint)
}
Action::Right => {
waypoint = rotate(ROTATE_RIGHT[(*value / 90) as usize - 1], waypoint)
}
}
}
pos.x.abs() + pos.y.abs()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let data = parse_input(crate::data::_DAY12_EXAMPLE_1);
assert_eq!(part1(&data), 25);
assert_eq!(part2(&data), 286);
}
#[test]
fn verify() {
let data = parse_input(crate::data::DAY12);
assert_eq!(part1(&data), 1589);
assert_eq!(part2(&data), 23960);
}
}
}
pub mod day13 {
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY13);
writeln!(&mut result, "Day 0, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY13);
writeln!(&mut result, "Day 0, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn part1(input: &str) -> i32 {
let mut lines = input.lines();
let earliest_time: i32 = lines.next().unwrap().parse().unwrap();
let buses: Vec<i32> = lines
.next()
.unwrap()
.split(",")
.filter(|&v| v != "x")
.map(|v| v.parse().unwrap())
.collect();
let (bus, time) = buses
.iter()
.map(|bus| {
(
bus,
(earliest_time as f32 / *bus as f32).ceil() as i32 * bus,
)
})
.min_by_key(|(_, time)| *time)
.unwrap();
(time - earliest_time) * bus
}
fn part2(input: &str) -> usize {
let line = input.lines().skip(1).next().unwrap();
let buses: Vec<(usize, usize)> = line
.split(",")
.enumerate()
.filter(|(_, s)| *s != "x")
.map(|(i, bus)| (i, bus.parse().unwrap()))
.collect();
let mut n = buses[0].1;
let mut step = buses[0].1;
for (i, bus) in &buses[1..] {
let mut tn = n + i;
while tn % bus != 0 {
tn += step;
}
n = tn - i;
step *= bus;
}
n
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1(crate::data::_DAY13_EXAMPLE_1), 295);
assert_eq!(part2(crate::data::_DAY13_EXAMPLE_1), 1068781);
assert_eq!(part2("\n17,x,13,19"), 3417);
assert_eq!(part2("\n67,7,59,61"), 754018);
assert_eq!(part2("\n67,x,7,59,61"), 779210);
assert_eq!(part2("\n67,7,x,59,61"), 1261476);
assert_eq!(part2("\n1789,37,47,1889"), 1202161486);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY13), 333);
assert_eq!(part2(crate::data::DAY13), 690123192779524);
}
}
}
pub mod day14 {
use lazy_static::lazy_static;
use regex::Regex;
use std::collections::HashMap;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY14);
writeln!(&mut result, "Day 14, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY14);
writeln!(&mut result, "Day 14, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn part1(input: &str) -> u64 {
lazy_static! {
static ref MASK_REGEX: Regex = Regex::new(r"mask = (.+)").unwrap();
}
lazy_static! {
static ref WRITE_REGEX: Regex = Regex::new(r"mem\[(\d+)\] = (\d+)").unwrap();
}
let mut memory: HashMap<usize, u64> = Default::default();
let mut set_mask: u64 = 0;
let mut clear_mask: u64 = std::u64::MAX;
for line in input.lines() {
if let Some(caps) = MASK_REGEX.captures(line) {
let mask = caps.get(1).unwrap().as_str();
set_mask = mask
.chars()
.rev()
.enumerate()
.filter(|(_, c)| *c == '1')
.fold(0, |acc, (i, _)| acc | (1 << i));
clear_mask = mask
.chars()
.rev()
.enumerate()
.filter(|(_, c)| *c == '0')
.fold(std::u64::MAX, |acc, (i, _)| acc & !(1 << i));
} else if let Some(caps) = WRITE_REGEX.captures(line) {
let register: usize = caps.get(1).unwrap().as_str().parse().unwrap();
let mut value: u64 = caps.get(2).unwrap().as_str().parse().unwrap();
value |= set_mask;
value &= clear_mask;
*memory.entry(register).or_default() = value;
} else {
unreachable!("Did not match line: [{}]", line);
}
}
memory.iter().map(|(_, v)| v).sum()
}
fn part2(input: &str) -> u64 {
lazy_static! {
static ref MASK_REGEX: Regex = Regex::new(r"mask = (.+)").unwrap();
}
lazy_static! {
static ref WRITE_REGEX: Regex = Regex::new(r"mem\[(\d+)\] = (\d+)").unwrap();
}
let mut memory: HashMap<u64, u64> = Default::default();
let mut set_mask: u64 = 0;
let mut floating_bits: Vec<u64> = Default::default();
for line in input.lines() {
if let Some(caps) = MASK_REGEX.captures(line) {
let mask = caps.get(1).unwrap().as_str();
set_mask = mask
.chars()
.rev()
.enumerate()
.filter(|(_, c)| *c == '1')
.fold(0, |acc, (i, _)| acc | (1 << i));
let floating_mask: u64 = mask
.chars()
.rev()
.enumerate()
.filter(|(_, c)| *c == 'X')
.fold(0, |acc, (i, _)| acc | (1 << i));
floating_bits.clear();
for i in 0..36 {
if (floating_mask & (1 << i)) != 0 {
floating_bits.push(i);
}
}
} else if let Some(caps) = WRITE_REGEX.captures(line) {
let base_register: u64 = caps.get(1).unwrap().as_str().parse().unwrap();
let value: u64 = caps.get(2).unwrap().as_str().parse().unwrap();
let pow = 2_usize.pow(floating_bits.len() as u32);
for permutation in 0..pow {
let mut final_register = base_register | set_mask;
for idx in 0..floating_bits.len() {
if permutation & (1 << idx) != 0 {
final_register |= 1 << floating_bits[idx];
} else {
final_register &= !(1 << floating_bits[idx]);
}
}
*memory.entry(final_register).or_default() = value;
}
} else {
unreachable!("Did not match line: [{}]", line);
}
}
memory.iter().map(|(_, v)| v).sum()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1(crate::data::_DAY14_EXAMPLE_1), 165);
assert_eq!(part2(crate::data::_DAY14_EXAMPLE_2), 208);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY14), 15018100062885);
assert_eq!(part2(crate::data::DAY14), 5724245857696);
}
}
}
pub mod day15 {
use std::collections::HashMap;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = solve(crate::data::DAY15, 2020);
writeln!(&mut result, "Day 15, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = solve(crate::data::DAY15, 30_000_000);
writeln!(&mut result, "Day 15, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn solve(input: &str, target_turn: usize) -> usize {
let mut prev_num = 0;
let mut history: HashMap<usize, (usize, usize)> = input
.split(",")
.map(|n| n.parse::<usize>().unwrap())
.enumerate()
.map(|(i, v)| {
prev_num = v;
let turn = i + 1;
(v, (turn, turn))
})
.collect();
let mut turn = history.len() + 1;
loop {
let prev_turns = history.get(&prev_num).unwrap();
let next_num = (turn - 1) - prev_turns.0;
if turn == target_turn {
return next_num;
}
let turns = history.entry(next_num).or_insert((turn, turn));
*turns = (turns.1, turn);
prev_num = next_num;
turn += 1;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(solve("0,3,6", 2020), 436);
assert_eq!(solve("1,3,2", 2020), 1);
assert_eq!(solve("2,1,3", 2020), 10);
assert_eq!(solve("1,2,3", 2020), 27);
assert_eq!(solve("2,3,1", 2020), 78);
assert_eq!(solve("3,2,1", 2020), 438);
assert_eq!(solve("3,1,2", 2020), 1836);
}
#[test]
fn verify() {
assert_eq!(solve(crate::data::DAY15, 2020), 273);
assert_eq!(solve(crate::data::DAY15, 30_000_000), 47205);
}
}
}
pub mod day16 {
use std::collections::HashSet;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let (answer_part1, answer_part2) = solve(crate::data::DAY16);
writeln!(&mut result, "Day 16, Problem 1 - [{}]", answer_part1).unwrap();
writeln!(&mut result, "Day 16, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn solve(input: &str) -> (usize, usize) {
let my_ticket_idx = input.find("your ticket").unwrap();
let nearby_tickets_idx = input.find("nearby tickets").unwrap();
// Parse rules
let rules: Vec<_> = input[..my_ticket_idx]
.lines()
.filter(|line| !line.is_empty())
.map(|line| {
let parts: Vec<_> = line.split(":").collect();
let key = parts[0];
let parts: Vec<_> = parts[1].split(" ").collect();
let split = parts[1].find("-").unwrap();
let lo: usize = parts[1][..split].parse().unwrap();
let hi: usize = parts[1][split + 1..].parse().unwrap();
let range_a = lo..=hi;
let split = parts[3].find("-").unwrap();
let lo: usize = parts[3][..split].parse().unwrap();
let hi: usize = parts[3][split + 1..].parse().unwrap();
let range_b = lo..=hi;
(key, range_a, range_b)
})
.collect();
// Parse all tickets
let tickets: Vec<Vec<usize>> = input[nearby_tickets_idx..]
.lines()
.skip(1)
.map(|line| {
line.split(",")
.map(|num| num.parse::<_>().unwrap())
.collect()
})
.collect();
// Solve part 1
let part1 = tickets
.iter()
.flat_map(|ticket| ticket.iter())
.filter(|num| {
rules
.iter()
.all(|rule| !rule.1.contains(num) && !rule.2.contains(num))
})
.sum();
// Compute valid tickets
let valid_tickets: Vec<_> = tickets
.iter()
.filter(|ticket| {
ticket.iter().all(|num| {
rules
.iter()
.any(|rule| rule.1.contains(num) || rule.2.contains(num))
})
})
.collect();
// Build container with all possibile matches
let num_rules = rules.len();
// Rule to index
let mut possible_positions: Vec<HashSet<usize>> =
(0..num_rules).map(|_| (0..num_rules).collect()).collect();
// First pass
for ticket_value_idx in 0..num_rules {
for ticket in &valid_tickets {
let value = ticket[ticket_value_idx];
for rule_idx in 0..num_rules {
let rule = &rules[rule_idx];
if !rule.1.contains(&value) && !rule.2.contains(&value) {
possible_positions[rule_idx].remove(&ticket_value_idx);
}
}
}
}
// Loop and removed solved one-by-one
let mut solved: HashSet<usize> = Default::default();
while solved.len() != num_rules {
for rule_idx in 0..num_rules {
if !solved.contains(&rule_idx) && possible_positions[rule_idx].len() == 1 {
let solved_pos = *possible_positions[rule_idx].iter().next().unwrap();
for idx in 0..num_rules {
if rule_idx != idx {
possible_positions[idx].remove(&solved_pos);
}
}
solved.insert(rule_idx);
}
}
}
// Each set should have exactly one remaining possibility
let solved_positions: Vec<usize> = possible_positions
.iter()
.map(|set| *set.iter().next().unwrap())
.collect();
// Parse my ticket
let my_ticket: Vec<usize> = input[my_ticket_idx..nearby_tickets_idx]
.lines()
.skip(1)
.filter(|line| !line.is_empty())
.flat_map(|line| line.split(",").map(|num| num.parse::<usize>().unwrap()))
.collect();
// Multiple the correct 6 numbers
let part2 = rules
.iter()
.enumerate()
.filter(|(_, rule)| rule.0.contains("departure"))
.map(|(i, _)| solved_positions[i])
.map(|idx| my_ticket[idx])
.product();
(part1, part2)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let (part1, _) = solve(crate::data::_DAY16_EXAMPLE_1);
assert_eq!(part1, 71);
}
#[test]
fn verify() {
let (part1, part2) = solve(crate::data::DAY16);
assert_eq!(part1, 21071);
assert_eq!(part2, 3429967441937);
}
}
}
pub mod day17 {
use fts_vecmath::point3::*;
use fts_vecmath::vector3::*;
use fts_vecmath::vector4::*;
use itertools::Itertools;
use std::collections::HashSet;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY17);
writeln!(&mut result, "Day 17, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY17);
writeln!(&mut result, "Day 17, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn part1(input: &str) -> usize {
type Pos = Point3<i32>;
type Offset = Vector3<i32>;
let offsets: Vec<Offset> = (-1..=1)
.cartesian_product(-1..=1)
.cartesian_product(-1..=1)
.filter_map(|((x, y), z)| match (x, y, z) {
(0, 0, 0) => None,
_ => Some(Offset::new(x, y, z)),
})
.collect();
let dim = input.lines().count() as i32;
let mut grid: HashSet<Pos> = input
.lines()
.enumerate()
.flat_map(|(row, line)| {
line.chars()
.enumerate()
.filter_map(move |(col, c)| match c {
'#' => Some(Pos::new(col as i32 - dim / 2, row as i32 - dim / 2, 0)),
'.' => None,
_ => unreachable!("Unexpected input char [{}]", c),
})
})
.collect();
let mut min_pos = Pos::new(-dim / 2 - 1, -dim / 2 - 1, -1);
let mut max_pos = Pos::new(dim / 2 + 1, dim / 2 + 1, 1);
for _ in 0..6 {
let mut next_grid: HashSet<Pos> = Default::default();
for x in min_pos.x..=max_pos.x {
for y in min_pos.y..=max_pos.y {
for z in min_pos.z..=max_pos.z {
let pos = Pos::new(x, y, z);
let mut count = 0;
for offset in &offsets {
let neighbor = pos + *offset;
if grid.contains(&neighbor) {
count += 1;
}
if count > 3 {
break;
}
}
let active = grid.contains(&pos);
if (active && (count == 2 || count == 3)) || (!active && count == 3) {
min_pos = fts_vecmath::point3::min(min_pos, pos - Offset::one());
max_pos = fts_vecmath::point3::max(max_pos, pos + Offset::one());
next_grid.insert(pos);
}
}
}
}
std::mem::swap(&mut grid, &mut next_grid);
}
grid.len()
}
fn part2(input: &str) -> usize {
type Pos = Vector4<i32>;
type Offset = Vector4<i32>;
let offsets: Vec<Offset> = (-1..=1)
.cartesian_product(-1..=1)
.cartesian_product(-1..=1)
.cartesian_product(-1..=1)
.filter_map(|(((x, y), z), w)| match (x, y, z, w) {
(0, 0, 0, 0) => None,
_ => Some(Offset::new(x, y, z, w)),
})
.collect();
let dim = input.lines().count() as i32;
let mut grid: HashSet<Pos> = input
.lines()
.enumerate()
.flat_map(|(row, line)| {
line.chars()
.enumerate()
.filter_map(move |(col, c)| match c {
'#' => Some(Pos::new(col as i32 - dim / 2, row as i32 - dim / 2, 0, 0)),
'.' => None,
_ => unreachable!("Unexpected input char [{}]", c),
})
})
.collect();
for _ in 0..6 {
let mut next_grid: HashSet<Pos> = Default::default();
let maybe_pos: HashSet<Pos> = grid
.iter()
.flat_map(|&pos| offsets.iter().map(move |offset| pos + *offset))
.collect();
for pos in maybe_pos {
let mut count = 0;
for offset in &offsets {
let neighbor = pos + *offset;
if grid.contains(&neighbor) {
count += 1;
}
if count > 3 {
break;
}
}
let active = grid.contains(&pos);
if (active && (count == 2 || count == 3)) || (!active && count == 3) {
next_grid.insert(pos);
}
}
std::mem::swap(&mut grid, &mut next_grid);
}
grid.len()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1(crate::data::_DAY17_EXAMPLE_1), 112);
assert_eq!(part2(crate::data::_DAY17_EXAMPLE_1), 848);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY17), 211);
assert_eq!(part2(crate::data::DAY17), 1952);
}
}
}
pub mod day18 {
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(crate::data::DAY18);
writeln!(&mut result, "Day 18, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(crate::data::DAY18);
writeln!(&mut result, "Day 18, Problem 2 - [{}]", answer_part2).unwrap();
result
}
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
enum Token {
LeftParen,
RightParen,
Plus,
Multiply,
Num(usize),
Space,
}
impl std::fmt::Display for Token {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Token::LeftParen => write!(f, "("),
Token::RightParen => write!(f, ")"),
Token::Plus => write!(f, "+"),
Token::Multiply => write!(f, "*"),
Token::Num(v) => write!(f, "{}", v),
Token::Space => write!(f, " "),
}
}
}
fn parse_input(input: &str) -> Vec<Vec<Token>> {
let mut result: Vec<_> = Default::default();
for line in input.lines().map(|line| line.as_bytes()) {
let mut line_result: Vec<Token> = Default::default();
let mut idx = 0;
while idx < line.len() {
let token = match line[idx] as char {
'(' => Token::LeftParen,
')' => Token::RightParen,
'+' => Token::Plus,
'*' => Token::Multiply,
' ' => Token::Space,
_ => {
let end = line[idx..]
.iter()
.enumerate()
.find_map(|(i, v)| match v.is_ascii_digit() {
false => Some(idx + i),
true => None,
})
.unwrap_or(line.len());
let span = &line[idx..end];
let s: &str = std::str::from_utf8(span).unwrap();
idx = end;
Token::Num(s.parse().unwrap())
}
};
// Increment non-nums
match token {
Token::Num(_) => (),
_ => idx += 1,
}
// Push non-white space
match token {
Token::Space => (),
_ => line_result.push(token),
}
}
result.push(line_result);
}
result
}
fn part1(input: &str) -> usize {
let mut data = parse_input(input);
fn value_from_slice2(slice: &[Token]) -> usize {
let mut sum = true;
slice.iter().fold(0, |mut acc, token| {
match token {
Token::Plus => sum = true,
Token::Multiply => sum = false,
Token::Num(n) => {
if sum {
acc += n;
} else {
acc *= n;
}
}
_ => unreachable!(),
}
acc
})
}
data.iter_mut()
.map(|entry| {
while let Some(end) = entry.iter().position(|v| *v == Token::RightParen) {
let pos = entry[..end]
.iter()
.rev()
.position(|v| *v == Token::LeftParen)
.unwrap();
let begin = end - pos - 1;
let slice = &entry[begin + 1..end];
let value = value_from_slice2(slice);
entry.drain(begin..=end).last();
entry.insert(begin, Token::Num(value));
}
value_from_slice2(&entry)
})
.sum()
}
fn part2(input: &str) -> usize {
let mut data = parse_input(input);
// inclusive [begin, end]
fn collapse_range(tokens: &mut Vec<Token>, begin: usize, mut end: usize) -> usize {
// Collapse sums
while let Some(idx) = &tokens[begin..=end].iter().position(|v| *v == Token::Plus) {
let lo = begin + idx - 1;
let hi = begin + idx + 1;
let (a, b) = match (&tokens[lo], &tokens[hi]) {
(Token::Num(a), Token::Num(b)) => (*a, *b),
_ => unreachable!(),
};
// Replace three values with one
tokens.drain(lo..=hi).last();
tokens.insert(lo, Token::Num(a + b));
end -= 2;
}
// Collapse multiplies
while let Some(idx) = &tokens[begin..=end]
.iter()
.position(|v| *v == Token::Multiply)
{
let lo = begin + idx - 1;
let hi = begin + idx + 1;
let (a, b) = match (&tokens[lo], &tokens[hi]) {
(Token::Num(a), Token::Num(b)) => (*a, *b),
_ => unreachable!(),
};
// Replace three values with one
tokens.drain(lo..=hi).last();
tokens.insert(lo, Token::Num(a * b));
end -= 2;
}
// Collapse parens
if end - begin + 1 == 3 {
tokens.remove(end);
tokens.remove(begin);
end -= 2;
}
assert_eq!(tokens[begin..=end].len(), 1);
match tokens[begin] {
Token::Num(v) => v,
_ => unreachable!(),
}
}
data.iter_mut()
.map(|entry| {
while let Some(end) = entry.iter().position(|v| *v == Token::RightParen) {
let pos = entry[..end]
.iter()
.rev()
.position(|v| *v == Token::LeftParen)
.unwrap();
let begin = end - pos - 1;
collapse_range(entry, begin, end);
}
let end = entry.len() - 1;
collapse_range(entry, 0, end)
})
.sum()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(part1("1 + 2 * 3 + 4 * 5 + 6"), 71);
assert_eq!(part1("1 + (2 * 3) + (4 * (5 + 6))"), 51);
assert_eq!(part1("2 * 3 + (4 * 5)"), 26);
assert_eq!(part1("5 + (8 * 3 + 9 + 3 * 4 * 3)"), 437);
assert_eq!(part1("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), 12240);
assert_eq!(
part1("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"),
13632
);
assert_eq!(part2("1 + 2 * 3 + 4 * 5 + 6"), 231);
assert_eq!(part2("1 + (2 * 3) + (4 * (5 + 6))"), 51);
assert_eq!(part2("2 * 3 + (4 * 5)"), 46);
assert_eq!(part2("5 + (8 * 3 + 9 + 3 * 4 * 3)"), 1445);
assert_eq!(part2("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), 669060);
assert_eq!(
part2("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"),
23340
);
}
#[test]
fn verify() {
assert_eq!(part1(crate::data::DAY18), 31142189909908);
assert_eq!(part2(crate::data::DAY18), 323912478287549);
}
}
}
pub mod day19 {
use crate::util::*;
use std::collections::HashMap;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let input = crate::data::DAY19.strip_carriage_return();
let (rules, messages) = parse_input(&input);
let answer_part1 = part1(&rules, &messages);
writeln!(&mut result, "Day 19, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&rules, &messages);
writeln!(&mut result, "Day 19, Problem 2 - [{}]", answer_part2).unwrap();
result
}
#[derive(Debug, Clone)]
enum Rule {
Subrules(Vec<Vec<usize>>),
Char(char),
}
fn parse_input(input: &str) -> (HashMap<usize, Rule>, Vec<&str>) {
let sections: Vec<&str> = input.split("\n\n").collect();
let rules: HashMap<usize, Rule> = sections[0]
.lines()
.map(|line| {
let parts: Vec<_> = line.split(":").map(|part| part.trim()).collect();
let id: usize = parts[0].parse().unwrap();
let rule = match parts[1] {
"\"a\"" => Rule::Char('a'),
"\"b\"" => Rule::Char('b'),
_ => {
let subrules: Vec<_> = parts[1].split("|").map(|s| s.trim()).collect();
let subrules = subrules
.iter()
.map(|subrule| {
subrule
.trim()
.split(" ")
.map(|n| n.parse::<usize>().unwrap())
.collect()
})
.collect();
Rule::Subrules(subrules)
}
};
(id, rule)
})
.collect();
let messages: Vec<&str> = sections[1].lines().collect();
(rules, messages)
}
fn part1(rules: &HashMap<usize, Rule>, messages: &[&str]) -> usize {
fn validate_message(msg: &str, rules: &HashMap<usize, Rule>) -> bool {
let mut open: Vec<(&str, Vec<usize>, Vec<usize>)> = vec![(msg, vec![0], vec![])];
while !open.is_empty() {
let (msg, mut path, mut visited) = open.pop().unwrap();
if msg.is_empty() || path.is_empty() {
continue;
}
let next_rule = path.remove(0);
visited.push(next_rule);
let rule = rules.get(&next_rule).unwrap();
match rule {
Rule::Char(c) => {
if msg.chars().next().unwrap() == *c {
if path.is_empty() && msg.len() == 1 {
// End of the line!
return true;
} else if msg.len() > 1 {
open.push((&msg[1..], path.clone(), visited.clone()));
}
}
}
Rule::Subrules(branches) => {
for branch in branches {
let new_path: Vec<_> =
branch.iter().chain(path.iter()).copied().collect();
open.push((msg, new_path, visited.clone()))
}
}
}
}
false
}
messages
.iter()
.filter(|msg| validate_message(msg, &rules))
.count()
}
fn part2(orig_rules: &HashMap<usize, Rule>, messages: &[&str]) -> usize {
let mut rules: HashMap<usize, Rule> = orig_rules.clone();
rules.insert(8, Rule::Subrules(vec![vec![42], vec![42, 8]]));
rules.insert(11, Rule::Subrules(vec![vec![42, 31], vec![42, 11, 31]]));
part1(&rules, messages)
// 214 too low
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let data_example1 = crate::data::_DAY19_EXAMPLE_1.strip_carriage_return();
let (rules, messages) = parse_input(&data_example1);
assert_eq!(part1(&rules, &messages), 2);
let data_example1 = crate::data::_DAY19_EXAMPLE_2.strip_carriage_return();
let (rules, messages) = parse_input(&data_example1);
assert_eq!(part1(&rules, &messages), 3);
assert_eq!(part2(&rules, &messages), 12);
}
#[test]
fn verify() {
let input = crate::data::DAY19.strip_carriage_return();
let (rules, messages) = parse_input(&input);
assert_eq!(part1(&rules, &messages), 136);
assert_eq!(part2(&rules, &messages), 256);
}
}
}
pub mod day20 {
use crate::util::*;
use fts_vecmath::point2::*;
use fts_vecmath::vector2::*;
use regex::Regex;
use std::collections::{HashMap, HashSet};
use std::fmt::Write;
type Pos = Point2<i8>;
type Offset = Vector2<i8>;
type TileId = usize;
type BorderId = usize;
type Orient = usize;
const TOP: usize = 0;
const RIGHT: usize = 1;
const BOTTOM: usize = 2;
const LEFT: usize = 3;
const ORIENTS: [[usize; 4]; 8] = [
[0, 1, 2, 3],
[3, 0, 1, 2],
[2, 3, 0, 1],
[1, 2, 3, 0],
[4, 5, 6, 7],
[7, 4, 5, 6],
[6, 7, 4, 5],
[5, 6, 7, 4],
];
pub fn run() -> String {
let mut result = String::with_capacity(128);
let input = crate::data::DAY20.strip_carriage_return();
let (answer_part1, answer_part2) = solve(&input);
writeln!(&mut result, "Day 20, Problem 1 - [{}]", answer_part1).unwrap();
writeln!(&mut result, "Day 20, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse(input: &str) -> Vec<(TileId, Vec<Vec<u8>>)> {
let id_re = Regex::new(r"Tile (\d+):").unwrap();
input
.split("\n\n")
.map(|section| {
// omg this is gross
let id: usize = id_re
.captures(section.lines().next().unwrap())
.unwrap()
.get(1)
.unwrap()
.as_str()
.parse()
.unwrap();
let tile: Vec<Vec<u8>> = section
.lines()
.skip(1)
.map(|line| line.as_bytes().to_vec())
.collect();
(id, tile)
})
.collect()
}
// rotate right 90 degrees
fn rotate(tile: &mut Vec<Vec<u8>>) {
let width = tile[0].len();
let mut temp = tile.clone();
for row in 0..width {
for col in 0..width {
let r = col;
let c = width - row - 1;
temp[r][c] = tile[row][col];
}
}
*tile = temp;
}
// flip about Y axis
fn flip(tile: &mut Vec<Vec<u8>>) {
let width = tile[0].len();
for row in 0..width {
let tile_row = &mut tile[row];
for col in 0..width / 2 {
let c = width - col - 1;
let left = tile_row[col];
let right = tile_row[c];
tile_row[col] = right;
tile_row[c] = left;
}
}
}
fn solve(input: &str) -> (usize, usize) {
let tiles = parse(input);
// Extract borders for each tile
let tile_borders: Vec<(TileId, [Vec<u8>; 8])> = tiles
.iter()
.map(|(id, tile)| {
let top: Vec<u8> = tile[0].clone();
let right: Vec<u8> = tile.iter().map(|row| *row.last().unwrap()).collect();
let bottom: Vec<u8> = tile.last().unwrap().iter().rev().copied().collect();
let left: Vec<u8> = tile.iter().rev().map(|row| *row.first().unwrap()).collect();
let t2: Vec<u8> = top.iter().rev().copied().collect();
let r2: Vec<u8> = left.iter().rev().copied().collect();
let b2: Vec<u8> = bottom.iter().rev().copied().collect();
let l2: Vec<u8> = right.iter().rev().copied().collect();
(*id, [top, right, bottom, left, t2, r2, b2, l2])
})
.collect();
let tile_borders2: HashMap<TileId, &[Vec<u8>; 8]> = tile_borders
.iter()
.map(|(id, borders)| (*id, borders))
.collect();
let mut unplaced_tiles: HashSet<TileId> =
tile_borders.iter().map(|(tile_id, _)| *tile_id).collect();
let mut board: HashMap<Pos, (TileId, Orient)> = Default::default();
let mut open_tiles: HashMap<Pos, Vec<(BorderId, &Vec<u8>)>> = Default::default();
// Initialize
let tile = &tile_borders[0];
unplaced_tiles.remove(&tile.0);
board.insert(Pos::new(0, 0), (tile.0, 0));
open_tiles.insert(Pos::new(0, 1), vec![(BOTTOM, &tile.1[TOP])]);
open_tiles.insert(Pos::new(1, 0), vec![(LEFT, &tile.1[RIGHT])]);
open_tiles.insert(Pos::new(0, -1), vec![(TOP, &tile.1[BOTTOM])]);
open_tiles.insert(Pos::new(-1, 0), vec![(RIGHT, &tile.1[LEFT])]);
let mut closed: HashSet<Pos> = Default::default();
while !unplaced_tiles.is_empty() {
// Pick a spot that hasn't been filled
let pos = *open_tiles.iter().next().unwrap().0;
let constraints = open_tiles.remove(&pos).unwrap();
// Test all unplaced tiles
let mut placed_tile: Option<TileId> = None;
for &unplaced_tile in &unplaced_tiles {
let unplaced_tile_borders = *tile_borders2.get(&unplaced_tile).unwrap();
// Does it have all borders
for orient_idx in 0..8 {
let orient = &ORIENTS[orient_idx];
let matches = constraints.iter().all(|constraint| {
constraint
.1
.iter()
.rev()
.zip(unplaced_tile_borders[orient[constraint.0]].iter())
.all(|(a, b)| a == b)
});
if matches {
// Success!
board.insert(pos, (unplaced_tile, orient_idx));
let neighbor = pos + Offset::new(0, 1);
if !board.contains_key(&neighbor) && !closed.contains(&neighbor) {
let border = &unplaced_tile_borders[orient[TOP]];
open_tiles
.entry(neighbor)
.or_default()
.push((BOTTOM, border));
}
// These four blocks could probably be generalized
let neighbor = pos + Offset::new(1, 0);
if !board.contains_key(&neighbor) && !closed.contains(&neighbor) {
let border = &unplaced_tile_borders[orient[RIGHT]];
open_tiles.entry(neighbor).or_default().push((LEFT, border));
}
let neighbor = pos + Offset::new(0, -1);
if !board.contains_key(&neighbor) && !closed.contains(&neighbor) {
let border = &unplaced_tile_borders[orient[BOTTOM]];
open_tiles.entry(neighbor).or_default().push((TOP, border));
}
let neighbor = pos + Offset::new(-1, 0);
if !board.contains_key(&neighbor) && !closed.contains(&neighbor) {
let border = &unplaced_tile_borders[orient[LEFT]];
open_tiles
.entry(neighbor)
.or_default()
.push((RIGHT, border));
}
placed_tile = Some(unplaced_tile);
break;
}
}
if placed_tile.is_some() {
break;
}
}
if let Some(tile_to_remove) = placed_tile {
unplaced_tiles.remove(&tile_to_remove);
} else {
closed.insert(pos);
}
}
let mut corner = Pos::new(0, 0);
for (&pos, _) in &board {
corner = fts_vecmath::point2::min(corner, pos);
}
let dim = (tile_borders.len() as f32).sqrt() as i8;
let offset = dim - 1;
// Find corners
let ll = board.get(&corner).unwrap().0;
let lr = board.get(&(corner + Offset::new(offset, 0))).unwrap().0;
let ul = board.get(&(corner + Offset::new(0, offset))).unwrap().0;
let ur = board
.get(&(corner + Offset::new(offset, offset)))
.unwrap()
.0;
// part1 is product of corners
let part1 = ul * ur * ll * lr;
let mut ocean: Vec<Vec<u8>> = Default::default();
// Correctly orient tiles
let ul_pos = corner + Offset::new(0, offset);
let lr_pos = ul_pos + Offset::new(offset, -offset);
let edge_len = tiles[0].1.len();
let mut oriented_tiles: HashMap<Pos, Vec<Vec<u8>>> = Default::default();
for tile_row in (lr_pos.y..=ul_pos.y).rev() {
for tile_col in ul_pos.x..=lr_pos.x {
let tile_pos = Pos::new(tile_col, tile_row);
let &(tile_id, mut tile_orient) = board.get(&tile_pos).unwrap();
let mut tile = tiles
.iter()
.find(|(id, _)| tile_id == *id)
.unwrap()
.1
.clone();
// Flip and rotate
if tile_orient > 3 {
flip(&mut tile);
tile_orient -= 4;
}
while tile_orient > 0 {
rotate(&mut tile);
tile_orient -= 1;
}
oriented_tiles.insert(tile_pos, tile);
}
}
// Build ocean with borders removed
for tile_row in (lr_pos.y..=ul_pos.y).rev() {
for row in 1..edge_len - 1 {
let mut ocean_row: Vec<u8> = Default::default();
for tile_col in ul_pos.x..=lr_pos.x {
let tile_pos = Pos::new(tile_col, tile_row);
let tile = oriented_tiles.get(&tile_pos).unwrap();
let tile_row = &tile[row];
for col in 1..edge_len - 1 {
ocean_row.push(tile_row[col]);
}
}
ocean.push(ocean_row);
}
}
let sea_monster: Vec<Offset> = vec![
Offset::new(18, 0),
Offset::new(0, 1),
Offset::new(5, 1),
Offset::new(6, 1),
Offset::new(11, 1),
Offset::new(12, 1),
Offset::new(17, 1),
Offset::new(18, 1),
Offset::new(19, 1),
Offset::new(1, 2),
Offset::new(4, 2),
Offset::new(7, 2),
Offset::new(10, 2),
Offset::new(13, 2),
Offset::new(16, 2),
];
// Look for sea monster
let r: Box<dyn Fn(&mut Vec<Vec<u8>>)> =
Box::new(|mut ocean: &mut Vec<Vec<u8>>| rotate(&mut ocean));
let f: Box<dyn Fn(&mut Vec<Vec<u8>>)> =
Box::new(|mut ocean: &mut Vec<Vec<u8>>| flip(&mut ocean));
let transforms: Vec<_> = vec![&r, &r, &r, &f, &r, &r, &r];
let ocean_dim = ocean.len();
assert_eq!(ocean[0].len(), ocean_dim);
let mut transform_iter = transforms.iter();
let part2 = loop {
// Check for sea monster
let mut num_sea_monsters = 0;
for row in 0..ocean_dim - 3 {
for col in 0..ocean_dim - 19 {
let pos = Pos::new(col as i8, row as i8);
let is_sea_monster = sea_monster
.iter()
.map(|offset| pos + *offset)
.all(|p| ocean[p.y as usize][p.x as usize] == '#' as u8);
if is_sea_monster {
num_sea_monsters += 1;
}
}
}
// Count number of non-sea monster waves
if num_sea_monsters > 0 {
let num_waves = ocean
.iter()
.flat_map(|row| row.iter())
.filter(|&&v| v == '#' as u8)
.count();
break num_waves - num_sea_monsters * sea_monster.len();
}
// Apply transform
transform_iter.next().unwrap()(&mut ocean);
};
(part1, part2)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let input = crate::data::_DAY20_EXAMPLE_1.strip_carriage_return();
let (part1, part2) = solve(&input);
assert_eq!(part1, 20899048083289);
assert_eq!(part2, 273);
}
#[test]
fn verify() {
let input = crate::data::DAY20.strip_carriage_return();
let (part1, part2) = solve(&input);
assert_eq!(part1, 83775126454273);
assert_eq!(part2, 1993);
}
}
}
pub mod day21 {
use itertools::Itertools;
use std::collections::{HashMap, HashSet};
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let (answer_part1, answer_part2) = solve(crate::data::DAY21);
writeln!(&mut result, "Day 21, Problem 1 - [{}]", answer_part1).unwrap();
writeln!(&mut result, "Day 21, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse(input: &str) -> Vec<(Vec<&str>, Vec<&str>)> {
input
.lines()
.map(|line| {
let parts: Vec<_> = line.split(" (contains ").collect();
let ingredients = parts[0].split(" ").collect();
// Trim closing paren
let len = parts[1].len();
let allergens = parts[1][..len - 1].split(", ").collect();
(ingredients, allergens)
})
.collect()
}
fn solve(input: &str) -> (usize, String) {
let data = parse(input);
let all_ingredients: HashSet<&str> = data
.iter()
.flat_map(|(ingredients, _)| ingredients.iter().copied())
.collect();
let mut maybe_allergen: HashMap<&str, HashSet<&str>> = Default::default();
// First pass
for (ingredients, allergens) in &data {
let ingredients_set: HashSet<_> = ingredients.iter().copied().collect();
for &allergen in allergens {
if !maybe_allergen.contains_key(allergen) {
maybe_allergen.insert(allergen, ingredients_set.clone());
} else {
let new_set = maybe_allergen
.get(allergen)
.unwrap()
.intersection(&ingredients_set)
.copied()
.collect();
maybe_allergen.insert(allergen, new_set);
}
}
}
// Reduce
let mut bad_ingredients: HashSet<&str> = Default::default();
let mut solved_allergens: HashMap<&str, &str> = Default::default();
loop {
let solved_allergen = maybe_allergen.iter().find_map(|(allergen, ingredients)| {
if ingredients.len() == 1 && !bad_ingredients.contains(allergen) {
Some((allergen, *ingredients.iter().next().unwrap()))
} else {
None
}
});
if let Some((allergen, ingredient)) = solved_allergen {
solved_allergens.insert(allergen, ingredient);
for (_, ingredients) in &mut maybe_allergen {
ingredients.remove(ingredient);
bad_ingredients.insert(ingredient);
}
} else {
break;
}
}
let safe_ingredients: HashSet<_> = all_ingredients.difference(&bad_ingredients).collect();
let part1 = data
.iter()
.flat_map(|(ingredients, _)| ingredients.iter())
.filter(|ingredient| safe_ingredients.contains(ingredient))
.count();
let part2: String = solved_allergens
.iter()
.sorted_by_key(|(allergen, _)| *allergen)
.map(|(_, ingredient)| ingredient)
.join(",");
(part1, part2)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let (part1, part2) = solve(crate::data::_DAY21_EXAMPLE_1);
assert_eq!(part1, 5);
assert_eq!(part2, "mxmxvkd,sqjhc,fvjkl");
}
#[test]
fn verify() {
let (part1, part2) = solve(crate::data::DAY21);
assert_eq!(part1, 2280);
assert_eq!(
part2,
"vfvvnm,bvgm,rdksxt,xknb,hxntcz,bktzrz,srzqtccv,gbtmdb"
);
}
}
}
pub mod day22 {
use crate::util::*;
use std::collections::hash_map::DefaultHasher;
use std::collections::{HashSet, VecDeque};
use std::fmt::Write;
use std::hash::{Hash, Hasher};
pub fn run() -> String {
let mut result = String::with_capacity(128);
let input = crate::data::DAY22.strip_carriage_return();
let answer_part1 = part1(&input);
writeln!(&mut result, "Day 22, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = part2(&input);
writeln!(&mut result, "Day 22, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse(input: &str) -> Vec<VecDeque<u8>> {
input
.split("\n\n")
.map(|section| {
section
.lines()
.skip(1)
.map(|line| line.parse::<u8>().unwrap())
.collect()
})
.collect()
}
fn part1(input: &str) -> usize {
let mut decks = parse(input);
let winner_idx = loop {
let a = decks[0].pop_front().unwrap();
let b = decks[1].pop_front().unwrap();
let winner_idx = if a > b { 0 } else { 1 };
decks[winner_idx].push_back(a.max(b));
decks[winner_idx].push_back(a.min(b));
let loser_idx = 1 - winner_idx;
if decks[loser_idx].is_empty() {
break winner_idx;
}
};
decks[winner_idx]
.iter()
.rev()
.enumerate()
.map(|(i, v)| (i + 1) * (*v as usize))
.sum()
}
fn part2(input: &str) -> usize {
let mut decks = parse(input);
fn play_recursive_game(decks: &mut Vec<VecDeque<u8>>) -> usize {
let mut game_states: HashSet<u64> = Default::default();
let mut duplicate_round = move |decks: &Vec<VecDeque<u8>>| -> bool {
let mut hasher = DefaultHasher::new();
decks[0].hash(&mut hasher);
decks[1].hash(&mut hasher);
let hash = hasher.finish();
let new_state = game_states.insert(hash);
!new_state
};
loop {
if duplicate_round(&decks) {
return 0;
}
let a = decks[0].pop_front().unwrap();
let b = decks[1].pop_front().unwrap();
let winner_idx = if decks[0].len() >= a as usize && decks[1].len() >= b as usize {
// Recursive combat!
let mut new_decks: Vec<VecDeque<u8>> = vec![
decks[0].iter().take(a as usize).copied().collect(),
decks[1].iter().take(b as usize).copied().collect(),
];
play_recursive_game(&mut new_decks)
} else {
if a > b {
0
} else {
1
}
};
let cards = [a, b];
decks[winner_idx].push_back(cards[winner_idx]);
decks[winner_idx].push_back(cards[1 - winner_idx]);
let loser_idx = 1 - winner_idx;
if decks[loser_idx].is_empty() {
return winner_idx;
}
}
}
let winner_idx = play_recursive_game(&mut decks);
decks[winner_idx]
.iter()
.rev()
.enumerate()
.map(|(i, v)| (i + 1) * (*v as usize))
.sum()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(
part1(&crate::data::_DAY22_EXAMPLE_1.strip_carriage_return()),
306
);
assert_eq!(
part2(&crate::data::_DAY22_EXAMPLE_1.strip_carriage_return()),
291
);
}
#[test]
fn verify() {
let input = crate::data::DAY22.strip_carriage_return();
assert_eq!(part1(&input), 33559);
assert_eq!(part2(&input), 32789);
}
}
}
pub mod day23 {
use itertools::Itertools;
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = solve("952316487", 100, true);
writeln!(&mut result, "Day 23, Problem 1 - [{}]", answer_part1).unwrap();
let answer_part2 = solve("952316487", 10_000_000, false);
writeln!(&mut result, "Day 23, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn solve(input: &str, num_steps: usize, part1: bool) -> String {
let mut nums: Vec<usize> = input
.chars()
.map(|c| c.to_string().parse::<usize>().unwrap())
.collect();
// Part2: add n..=1_000_000
if !part1 {
nums.reserve(1_000_0001);
for i in 10..=1_000_000 {
nums.push(i);
}
assert_eq!(nums.len(), 1_000_000);
}
let last_num = if part1 { 9 } else { 1_000_000 };
// Initialize linked list
let mut linked_list: Vec<usize> = Default::default();
linked_list.resize(nums.len() + 1, 0);
for (&num, &next) in nums.iter().tuple_windows() {
linked_list[num] = next;
}
linked_list[0] = 0; // unused
linked_list[*nums.last().unwrap()] = nums[0]; // wrap
// Run N steps
let mut cur_value = nums[0];
for _step in 0..num_steps {
// Remove three cups
let a = linked_list[cur_value];
let b = linked_list[a];
let c = linked_list[b];
linked_list[cur_value] = linked_list[c];
// Identify destination cup
let mut dst = cur_value - 1;
while dst == a || dst == b || dst == c || dst == 0 {
if dst <= 1 {
dst = last_num;
} else {
dst -= 1;
}
}
// Insert
let next = linked_list[dst];
linked_list[dst] = a;
linked_list[c] = next;
// Advance
cur_value = linked_list[cur_value];
}
if part1 {
let mut answer: Vec<usize> = Default::default();
cur_value = 1;
for _ in 0..nums.len() - 1 {
cur_value = linked_list[cur_value];
answer.push(cur_value);
}
answer.iter().map(|v| v.to_string()).join("")
} else {
let a = linked_list[1];
let b = linked_list[a];
(a * b).to_string()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let input = "389125467";
assert_eq!(solve(&input, 10, true), "92658374");
assert_eq!(solve(&input, 100, true), "67384529");
assert_eq!(solve(&input, 10_000_000, false), "149245887792");
}
#[test]
fn verify() {
let input = "952316487";
assert_eq!(solve(input, 100, true), "25398647");
assert_eq!(solve(&input, 10_000_000, false), "363807398885");
}
}
}
pub mod day24 {
use fts_vecmath::point2::*;
use fts_vecmath::vector2::*;
use regex::Regex;
use std::collections::{HashMap, HashSet};
use std::fmt::Write;
type Pos = Point2<i8>;
type Offset = Vector2<i8>;
#[derive(Copy, Clone, Debug)]
enum HexDir {
W,
E,
SW,
SE,
NW,
NE,
}
pub fn run() -> String {
let mut result = String::with_capacity(128);
let (answer_part1, answer_part2) = solve(crate::data::DAY24);
writeln!(&mut result, "Day 24, Problem 1 - [{}]", answer_part1).unwrap();
writeln!(&mut result, "Day 24, Problem 2 - [{}]", answer_part2).unwrap();
result
}
fn parse(input: &str) -> Vec<Vec<HexDir>> {
let re = Regex::new("(w|e|sw|se|nw|ne)").unwrap();
input
.lines()
.map(|line| {
re.captures_iter(line)
.map(|cap| match &cap[1] {
"w" => HexDir::W,
"e" => HexDir::E,
"sw" => HexDir::SW,
"se" => HexDir::SE,
"nw" => HexDir::NW,
"ne" => HexDir::NE,
_ => unreachable!(),
})
.collect()
})
.collect()
}
fn move_pos(pos: Pos, dir: HexDir) -> Pos {
// [EvenRowOffsets, OddRowOffsets]
const OFFSETS: [[Offset; 6]; 2] = [
[
Offset { x: -1, y: 0 }, // W
Offset { x: 1, y: 0 }, // E
Offset { x: -1, y: 1 }, // SW
Offset { x: 0, y: 1 }, // SE
Offset { x: -1, y: -1 }, // NW
Offset { x: 0, y: -1 }, // NE
],
[
Offset { x: -1, y: 0 }, // W
Offset { x: 1, y: 0 }, // E
Offset { x: 0, y: 1 }, // SW
Offset { x: 1, y: 1 }, // SE
Offset { x: 0, y: -1 }, // NW
Offset { x: 1, y: -1 }, // NE
],
];
let idx = if pos.y % 2 == 0 { 0 } else { 1 };
pos + OFFSETS[idx][dir as usize]
}
fn solve(input: &str) -> (usize, usize) {
let data = parse(input);
let mut board: HashMap<Pos, bool> = Default::default();
// Part 1
for steps in &data {
let pos = steps
.iter()
.fold(Pos::zero(), |pos, step| move_pos(pos, *step));
let is_black = board.entry(pos).or_default();
*is_black = !*is_black;
}
let part1 = board.iter().filter(|(_, is_black)| **is_black).count();
// Part 2
const DIRS: [HexDir; 6] = [
HexDir::W,
HexDir::E,
HexDir::SW,
HexDir::SE,
HexDir::NW,
HexDir::NE,
];
for _day in 0..100 {
let mut new_board: HashMap<Pos, bool> = Default::default();
// All tiles that might flip (this could be better)
let tiles: HashSet<Pos> = board
.iter()
.filter(|(_, is_black)| **is_black)
.flat_map(|(pos, _)| {
let pos = *pos;
DIRS.iter().map(move |dir| move_pos(pos, *dir))
})
.collect();
// Check all tiles
for &pos in &tiles {
// Current tile is black
let is_black = *board.get(&pos).unwrap_or(&false);
// Count neighbors
let black_neighbors = DIRS
.iter()
.map(|dir| move_pos(pos, *dir))
.map(|pos| board.get(&pos).unwrap_or(&false))
.filter(|is_black| **is_black)
.count();
// Maybe flip
if is_black && (black_neighbors == 0 || black_neighbors > 2) {
new_board.insert(pos, false);
} else if !is_black && black_neighbors == 2 {
new_board.insert(pos, true);
} else {
new_board.insert(pos, is_black);
}
}
board = new_board;
}
let part2 = board.iter().filter(|(_, is_black)| **is_black).count();
(part1, part2)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
let steps = parse("nwwswee");
assert_eq!(
Pos::zero(),
steps[0]
.iter()
.fold(Pos::zero(), |pos, step| move_pos(pos, *step))
);
let (part1, part2) = solve(crate::data::_DAY24_EXAMPLE_1);
assert_eq!(part1, 10);
assert_eq!(part2, 2208);
}
#[test]
fn verify() {
let (part1, part2) = solve(crate::data::DAY24);
assert_eq!(part1, 346);
assert_eq!(part2, 3802);
}
}
}
pub mod day25 {
use std::fmt::Write;
pub fn run() -> String {
let mut result = String::with_capacity(128);
let answer_part1 = part1(18356117, 5909654);
writeln!(&mut result, "Day 25, Problem 1 - [{}]", answer_part1).unwrap();
result
}
fn transform(subject_number: usize, loop_size: usize) -> usize {
let mut value = 1;
for _ in 0..loop_size {
value = (value * subject_number) % 20201227;
}
value
}
fn calc_loop_size(subject_number: usize, desired_result: usize) -> usize {
let mut loop_count = 0;
let mut value = 1;
while value != desired_result {
value = (value * subject_number) % 20201227;
loop_count += 1;
}
loop_count
}
fn part1(card_public_key: usize, door_public_key: usize) -> usize {
let card_loop_size = calc_loop_size(7, card_public_key);
transform(door_public_key, card_loop_size)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn examples() {
assert_eq!(transform(7, 8), 5764801);
assert_eq!(part1(5764801, 17807724), 14897079);
}
#[test]
fn verify() {
assert_eq!(part1(18356117, 5909654), 16902792);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment