Compare commits
3 commits
Author | SHA1 | Date | |
---|---|---|---|
2f7d33f7fd | |||
b3768bc2c2 | |||
4951abb7f2 |
8 changed files with 535 additions and 46 deletions
10
example/day16.txt
Normal file
10
example/day16.txt
Normal file
|
@ -0,0 +1,10 @@
|
||||||
|
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
|
||||||
|
Valve BB has flow rate=13; tunnels lead to valves CC, AA
|
||||||
|
Valve CC has flow rate=2; tunnels lead to valves DD, BB
|
||||||
|
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
|
||||||
|
Valve EE has flow rate=3; tunnels lead to valves FF, DD
|
||||||
|
Valve FF has flow rate=0; tunnels lead to valves EE, GG
|
||||||
|
Valve GG has flow rate=0; tunnels lead to valves FF, HH
|
||||||
|
Valve HH has flow rate=22; tunnel leads to valve GG
|
||||||
|
Valve II has flow rate=0; tunnels lead to valves AA, JJ
|
||||||
|
Valve JJ has flow rate=21; tunnel leads to valve II
|
1
example/day17.txt
Normal file
1
example/day17.txt
Normal file
|
@ -0,0 +1 @@
|
||||||
|
>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
|
50
input/day16.txt
Normal file
50
input/day16.txt
Normal file
|
@ -0,0 +1,50 @@
|
||||||
|
Valve DJ has flow rate=0; tunnels lead to valves ZH, AA
|
||||||
|
Valve LP has flow rate=0; tunnels lead to valves AA, EE
|
||||||
|
Valve GT has flow rate=0; tunnels lead to valves FJ, AW
|
||||||
|
Valve RO has flow rate=5; tunnels lead to valves NO, FD, QV, BV
|
||||||
|
Valve PS has flow rate=0; tunnels lead to valves FY, UV
|
||||||
|
Valve QV has flow rate=0; tunnels lead to valves EB, RO
|
||||||
|
Valve MV has flow rate=0; tunnels lead to valves FL, EB
|
||||||
|
Valve RN has flow rate=0; tunnels lead to valves AW, LQ
|
||||||
|
Valve HF has flow rate=0; tunnels lead to valves QN, HW
|
||||||
|
Valve PY has flow rate=19; tunnel leads to valve SN
|
||||||
|
Valve AT has flow rate=0; tunnels lead to valves YQ, UY
|
||||||
|
Valve UY has flow rate=3; tunnels lead to valves KV, ID, AT, PB, PG
|
||||||
|
Valve YI has flow rate=0; tunnels lead to valves FL, FD
|
||||||
|
Valve EB has flow rate=8; tunnels lead to valves MV, GQ, QV
|
||||||
|
Valve ID has flow rate=0; tunnels lead to valves NO, UY
|
||||||
|
Valve FY has flow rate=15; tunnels lead to valves LQ, PS
|
||||||
|
Valve GQ has flow rate=0; tunnels lead to valves EB, KM
|
||||||
|
Valve HW has flow rate=0; tunnels lead to valves FJ, HF
|
||||||
|
Valve CQ has flow rate=17; tunnels lead to valves KM, GO
|
||||||
|
Valve AW has flow rate=20; tunnels lead to valves RN, GT, WH, MX
|
||||||
|
Valve BV has flow rate=0; tunnels lead to valves RO, ZH
|
||||||
|
Valve PB has flow rate=0; tunnels lead to valves UY, AA
|
||||||
|
Valve MX has flow rate=0; tunnels lead to valves AW, YG
|
||||||
|
Valve DE has flow rate=4; tunnels lead to valves MM, PZ, PG, DS, EP
|
||||||
|
Valve AA has flow rate=0; tunnels lead to valves EP, PB, LP, JT, DJ
|
||||||
|
Valve QN has flow rate=23; tunnels lead to valves SN, HF
|
||||||
|
Valve GO has flow rate=0; tunnels lead to valves CQ, MK
|
||||||
|
Valve PZ has flow rate=0; tunnels lead to valves IJ, DE
|
||||||
|
Valve PG has flow rate=0; tunnels lead to valves UY, DE
|
||||||
|
Valve FL has flow rate=18; tunnels lead to valves MV, YI
|
||||||
|
Valve DS has flow rate=0; tunnels lead to valves DE, ZH
|
||||||
|
Valve ZH has flow rate=11; tunnels lead to valves YQ, BV, DJ, DS, SB
|
||||||
|
Valve KV has flow rate=0; tunnels lead to valves UY, IJ
|
||||||
|
Valve UV has flow rate=9; tunnels lead to valves MM, PS, YG
|
||||||
|
Valve WH has flow rate=0; tunnels lead to valves JT, AW
|
||||||
|
Valve FD has flow rate=0; tunnels lead to valves YI, RO
|
||||||
|
Valve FJ has flow rate=24; tunnels lead to valves HW, GT
|
||||||
|
Valve JT has flow rate=0; tunnels lead to valves AA, WH
|
||||||
|
Valve SN has flow rate=0; tunnels lead to valves PY, QN
|
||||||
|
Valve KM has flow rate=0; tunnels lead to valves GQ, CQ
|
||||||
|
Valve LQ has flow rate=0; tunnels lead to valves RN, FY
|
||||||
|
Valve NO has flow rate=0; tunnels lead to valves ID, RO
|
||||||
|
Valve SB has flow rate=0; tunnels lead to valves ZH, IJ
|
||||||
|
Valve MK has flow rate=25; tunnel leads to valve GO
|
||||||
|
Valve YG has flow rate=0; tunnels lead to valves MX, UV
|
||||||
|
Valve IJ has flow rate=16; tunnels lead to valves EE, KV, PZ, SB
|
||||||
|
Valve EP has flow rate=0; tunnels lead to valves AA, DE
|
||||||
|
Valve MM has flow rate=0; tunnels lead to valves UV, DE
|
||||||
|
Valve YQ has flow rate=0; tunnels lead to valves AT, ZH
|
||||||
|
Valve EE has flow rate=0; tunnels lead to valves LP, IJ
|
1
input/day17.txt
Normal file
1
input/day17.txt
Normal file
File diff suppressed because one or more lines are too long
118
src/day15.rs
118
src/day15.rs
|
@ -1,13 +1,28 @@
|
||||||
//! Day 15: Beacon Exclusion Zone
|
//! Day 15: Beacon Exclusion Zone
|
||||||
|
|
||||||
use std::collections::HashSet;
|
use itertools::Itertools;
|
||||||
|
|
||||||
use once_cell::sync::Lazy;
|
use once_cell::sync::Lazy;
|
||||||
use regex::Regex;
|
use regex::Regex;
|
||||||
|
|
||||||
type Coord = (i32, i32);
|
type Coord = (i32, i32);
|
||||||
|
|
||||||
fn parse_input(input: &[String]) -> Vec<(Coord, Coord)> {
|
struct Sensor {
|
||||||
|
pos: Coord,
|
||||||
|
beacon: Coord,
|
||||||
|
radius: i32,
|
||||||
|
}
|
||||||
|
|
||||||
|
impl Sensor {
|
||||||
|
fn new(pos: Coord, beacon: Coord) -> Self {
|
||||||
|
Self {
|
||||||
|
pos,
|
||||||
|
beacon,
|
||||||
|
radius: mdist(pos, beacon),
|
||||||
|
}
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
fn parse_input(input: &[String]) -> Vec<Sensor> {
|
||||||
static LINE_REGEX: Lazy<Regex> = Lazy::new(|| {
|
static LINE_REGEX: Lazy<Regex> = Lazy::new(|| {
|
||||||
Regex::new("Sensor at x=(-?\\d+), y=(-?\\d+): closest beacon is at x=(-?\\d+), y=(-?\\d+)")
|
Regex::new("Sensor at x=(-?\\d+), y=(-?\\d+): closest beacon is at x=(-?\\d+), y=(-?\\d+)")
|
||||||
.unwrap()
|
.unwrap()
|
||||||
|
@ -17,7 +32,8 @@ fn parse_input(input: &[String]) -> Vec<(Coord, Coord)> {
|
||||||
.iter()
|
.iter()
|
||||||
.map(|line| {
|
.map(|line| {
|
||||||
let cap = LINE_REGEX.captures(line).unwrap();
|
let cap = LINE_REGEX.captures(line).unwrap();
|
||||||
(
|
|
||||||
|
Sensor::new(
|
||||||
(
|
(
|
||||||
cap.get(1).unwrap().as_str().parse().unwrap(),
|
cap.get(1).unwrap().as_str().parse().unwrap(),
|
||||||
cap.get(2).unwrap().as_str().parse().unwrap(),
|
cap.get(2).unwrap().as_str().parse().unwrap(),
|
||||||
|
@ -35,73 +51,87 @@ fn mdist(p1: Coord, p2: Coord) -> i32 {
|
||||||
(p1.0.abs_diff(p2.0) + p1.1.abs_diff(p2.1)) as i32
|
(p1.0.abs_diff(p2.0) + p1.1.abs_diff(p2.1)) as i32
|
||||||
}
|
}
|
||||||
|
|
||||||
fn beacon_exclude(pos: Coord, closest: Coord, excluded: &mut HashSet<Coord>, row: i32) {
|
fn line_possible_positions(sensors: &[Sensor], y: i32, min: i32, max: i32) -> Vec<Coord> {
|
||||||
let dist = mdist(pos, closest);
|
let mut x = min;
|
||||||
|
let mut res = Vec::new();
|
||||||
|
|
||||||
for x in pos.0 - dist..pos.0 + dist {
|
while x <= max {
|
||||||
let point = (x, row);
|
let mut jumped = false;
|
||||||
if point != closest && mdist(pos, point) <= dist {
|
for sensor in sensors {
|
||||||
excluded.insert(point);
|
let dist = mdist((x, y), sensor.pos);
|
||||||
|
if dist <= sensor.radius {
|
||||||
|
let jump = sensor.radius - dist + 2 * x.abs_diff(sensor.pos.0) as i32 + 1;
|
||||||
|
x += jump;
|
||||||
|
jumped = true;
|
||||||
|
break;
|
||||||
}
|
}
|
||||||
}
|
}
|
||||||
}
|
|
||||||
|
|
||||||
fn beacon_exclude_section(pos: Coord, closest: Coord, excluded: &mut HashSet<Coord>, limit: i32) {
|
if !jumped {
|
||||||
let dist = mdist(pos, closest);
|
res.push((x, y));
|
||||||
|
x += 1;
|
||||||
for y in 0..=limit {
|
|
||||||
for x in 0..=limit {
|
|
||||||
let point = (x, y);
|
|
||||||
if mdist(pos, point) <= dist {
|
|
||||||
excluded.insert(point);
|
|
||||||
}
|
|
||||||
}
|
}
|
||||||
}
|
}
|
||||||
|
res
|
||||||
}
|
}
|
||||||
|
|
||||||
fn _part1(input: Vec<String>, row: i32) -> String {
|
fn _part1(input: Vec<String>, row: i32) -> String {
|
||||||
let sensors = parse_input(&input);
|
let sensors = parse_input(&input);
|
||||||
let mut excluded = HashSet::new();
|
|
||||||
|
|
||||||
sensors
|
let x_minmax = sensors
|
||||||
.iter()
|
.iter()
|
||||||
.for_each(|(pos, closest)| beacon_exclude(*pos, *closest, &mut excluded, row));
|
.flat_map(|s| {
|
||||||
|
let ycorrect = (s.pos.1.abs_diff(row) as i32).min(s.radius);
|
||||||
|
[s.pos.0 - s.radius + ycorrect, s.pos.0 + s.radius - ycorrect]
|
||||||
|
})
|
||||||
|
.minmax();
|
||||||
|
let (min, max) = match x_minmax {
|
||||||
|
itertools::MinMaxResult::NoElements => panic!("no sensors"),
|
||||||
|
itertools::MinMaxResult::OneElement(x) => (x, x),
|
||||||
|
itertools::MinMaxResult::MinMax(min, max) => (min, max),
|
||||||
|
};
|
||||||
|
|
||||||
excluded.len().to_string()
|
let n_possible = line_possible_positions(&sensors, row, min, max).len();
|
||||||
|
let beacons_in_row = sensors
|
||||||
|
.iter()
|
||||||
|
.filter_map(|s| {
|
||||||
|
if s.beacon.1 == row {
|
||||||
|
Some(s.beacon)
|
||||||
|
} else {
|
||||||
|
None
|
||||||
|
}
|
||||||
|
})
|
||||||
|
.unique()
|
||||||
|
.count();
|
||||||
|
|
||||||
|
let res = max - min + 1 - n_possible as i32 - beacons_in_row as i32;
|
||||||
|
res.to_string()
|
||||||
}
|
}
|
||||||
|
|
||||||
fn _part2(input: Vec<String>, limit: i32) -> String {
|
fn _part2(input: Vec<String>, limit: i32) -> String {
|
||||||
let sensors = parse_input(&input);
|
let sensors = parse_input(&input);
|
||||||
let mut excluded = HashSet::new();
|
|
||||||
|
|
||||||
sensors
|
|
||||||
.iter()
|
|
||||||
.enumerate()
|
|
||||||
.for_each(|(i, (pos, closest))| {
|
|
||||||
println!("bc {}", i);
|
|
||||||
beacon_exclude_section(*pos, *closest, &mut excluded, limit);
|
|
||||||
});
|
|
||||||
|
|
||||||
for y in 0..limit {
|
for y in 0..limit {
|
||||||
for x in 0..limit {
|
let positions = line_possible_positions(&sensors, y, 0, limit);
|
||||||
let point = (x, y);
|
if let Some(pos) = positions.first() {
|
||||||
if !excluded.contains(&point) {
|
if positions.len() > 1 {
|
||||||
dbg!(&point);
|
panic!("more than 1 distress beacon found")
|
||||||
let f = point.0 * 4000000 + point.1;
|
|
||||||
return f.to_string();
|
|
||||||
}
|
}
|
||||||
|
|
||||||
|
let freq = pos.0 as i64 * 4_000_000 + pos.1 as i64;
|
||||||
|
return freq.to_string();
|
||||||
}
|
}
|
||||||
}
|
}
|
||||||
|
|
||||||
panic!("not found")
|
panic!("distress beacon not found")
|
||||||
}
|
}
|
||||||
|
|
||||||
pub fn part1(input: Vec<String>) -> String {
|
pub fn part1(input: Vec<String>) -> String {
|
||||||
_part1(input, 2000000)
|
_part1(input, 2_000_000)
|
||||||
}
|
}
|
||||||
|
|
||||||
pub fn part2(input: Vec<String>) -> String {
|
pub fn part2(input: Vec<String>) -> String {
|
||||||
_part2(input, 4000000)
|
_part2(input, 4_000_000)
|
||||||
}
|
}
|
||||||
|
|
||||||
#[cfg(test)]
|
#[cfg(test)]
|
||||||
|
@ -122,11 +152,11 @@ mod tests {
|
||||||
|
|
||||||
#[test]
|
#[test]
|
||||||
fn t_part1() {
|
fn t_part1() {
|
||||||
assert_eq!(part1(crate::read_input(DAY)), "");
|
assert_eq!(part1(crate::read_input(DAY)), "5166077");
|
||||||
}
|
}
|
||||||
|
|
||||||
#[test]
|
#[test]
|
||||||
fn t_part2() {
|
fn t_part2() {
|
||||||
assert_eq!(part2(crate::read_input(DAY)), "");
|
assert_eq!(part2(crate::read_input(DAY)), "13071206703981");
|
||||||
}
|
}
|
||||||
}
|
}
|
||||||
|
|
250
src/day16.rs
Normal file
250
src/day16.rs
Normal file
|
@ -0,0 +1,250 @@
|
||||||
|
//! Day 16: Proboscidea Volcanium
|
||||||
|
|
||||||
|
use std::collections::HashMap;
|
||||||
|
|
||||||
|
use once_cell::sync::Lazy;
|
||||||
|
use regex::Regex;
|
||||||
|
|
||||||
|
#[derive(Debug, Clone)]
|
||||||
|
struct Valve {
|
||||||
|
name: String,
|
||||||
|
flow: u16,
|
||||||
|
connections: Vec<u16>,
|
||||||
|
}
|
||||||
|
|
||||||
|
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
|
||||||
|
struct CacheKey {
|
||||||
|
open: u64,
|
||||||
|
valve: u64,
|
||||||
|
remaining: u8,
|
||||||
|
pressure: u64,
|
||||||
|
do_open: bool,
|
||||||
|
}
|
||||||
|
|
||||||
|
fn parse_input(input: &[String]) -> Vec<Valve> {
|
||||||
|
static LINE_REGEX: Lazy<Regex> = Lazy::new(|| {
|
||||||
|
Regex::new("Valve (\\w{2}) has flow rate=(\\d+); tunnels? leads? to valves? ([\\w, ]+)")
|
||||||
|
.unwrap()
|
||||||
|
});
|
||||||
|
|
||||||
|
let ttable = input
|
||||||
|
.iter()
|
||||||
|
.enumerate()
|
||||||
|
.map(|(i, line)| {
|
||||||
|
let cap = LINE_REGEX
|
||||||
|
.captures(line)
|
||||||
|
.unwrap_or_else(|| panic!("could not parse line: {}", line));
|
||||||
|
(cap.get(1).unwrap().as_str().to_string(), i as u16)
|
||||||
|
})
|
||||||
|
.collect::<HashMap<_, _>>();
|
||||||
|
|
||||||
|
input
|
||||||
|
.iter()
|
||||||
|
.map(|line| {
|
||||||
|
let cap = LINE_REGEX
|
||||||
|
.captures(line)
|
||||||
|
.unwrap_or_else(|| panic!("could not parse line: {}", line));
|
||||||
|
Valve {
|
||||||
|
name: cap.get(1).unwrap().as_str().to_owned(),
|
||||||
|
flow: cap.get(2).unwrap().as_str().parse().unwrap(),
|
||||||
|
connections: cap
|
||||||
|
.get(3)
|
||||||
|
.unwrap()
|
||||||
|
.as_str()
|
||||||
|
.split(", ")
|
||||||
|
.map(|n| *ttable.get(n).unwrap())
|
||||||
|
.collect(),
|
||||||
|
}
|
||||||
|
})
|
||||||
|
.collect()
|
||||||
|
}
|
||||||
|
|
||||||
|
fn dfs(
|
||||||
|
cache: &mut HashMap<(u64, u16, u16), u16>,
|
||||||
|
valves: &[Valve],
|
||||||
|
current: usize,
|
||||||
|
opened: u64,
|
||||||
|
rate: u16,
|
||||||
|
steps: u16,
|
||||||
|
) -> u16 {
|
||||||
|
if steps == 0 {
|
||||||
|
return 0;
|
||||||
|
}
|
||||||
|
|
||||||
|
if let Some(&released) = cache.get(&(opened, steps, current as u16)) {
|
||||||
|
return released;
|
||||||
|
}
|
||||||
|
|
||||||
|
let mut released = 0;
|
||||||
|
|
||||||
|
// we have 2 options: open the valve or go to any of the connections
|
||||||
|
|
||||||
|
// Can we open the current valve and does it makes sense to do it ?
|
||||||
|
if opened & (1 << current) == 0 && valves[current].flow > 0 {
|
||||||
|
let next_opened = opened | 1 << current;
|
||||||
|
let next_rate = rate + valves[current].flow;
|
||||||
|
released = dfs(cache, valves, current, next_opened, next_rate, steps - 1);
|
||||||
|
}
|
||||||
|
|
||||||
|
for next in valves[current].connections.iter().copied() {
|
||||||
|
let rel = dfs(cache, valves, next as usize, opened, rate, steps - 1);
|
||||||
|
released = released.max(rel);
|
||||||
|
}
|
||||||
|
|
||||||
|
released += rate;
|
||||||
|
cache.insert((opened, steps, current as u16), released);
|
||||||
|
released
|
||||||
|
}
|
||||||
|
|
||||||
|
fn dfs_elephant(
|
||||||
|
cache: &mut HashMap<(u64, u16, u16, u16), u16>,
|
||||||
|
valves: &[Valve],
|
||||||
|
me: usize,
|
||||||
|
elephant: usize,
|
||||||
|
opened: u64,
|
||||||
|
rate: u16,
|
||||||
|
steps: u16,
|
||||||
|
) -> u16 {
|
||||||
|
if steps == 0 {
|
||||||
|
return 0;
|
||||||
|
}
|
||||||
|
|
||||||
|
if let Some(&released) = cache.get(&(opened, steps, me as u16, elephant as u16)) {
|
||||||
|
return released;
|
||||||
|
}
|
||||||
|
|
||||||
|
// both we and the elephant have 2 options: open valve/go next
|
||||||
|
let me_can_open = opened & (1 << me) == 0 && valves[me].flow > 0;
|
||||||
|
let ele_can_open = me != elephant && opened & (1 << elephant) == 0 && valves[elephant].flow > 0;
|
||||||
|
|
||||||
|
let mut released = 0;
|
||||||
|
|
||||||
|
// I open valve, elephant moves
|
||||||
|
if me_can_open {
|
||||||
|
let next_opened = opened | 1 << me;
|
||||||
|
let next_rate = rate + valves[me].flow;
|
||||||
|
|
||||||
|
for elephant_next in valves[elephant].connections.iter().copied() {
|
||||||
|
released = released.max(dfs_elephant(
|
||||||
|
cache,
|
||||||
|
valves,
|
||||||
|
me,
|
||||||
|
elephant_next as usize,
|
||||||
|
next_opened,
|
||||||
|
next_rate,
|
||||||
|
steps - 1,
|
||||||
|
));
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
// Elephant opens valve, I move
|
||||||
|
if ele_can_open {
|
||||||
|
let next_opened = opened | 1 << elephant;
|
||||||
|
let next_rate = rate + valves[elephant].flow;
|
||||||
|
|
||||||
|
for me_next in valves[me].connections.iter().copied() {
|
||||||
|
released = released.max(dfs_elephant(
|
||||||
|
cache,
|
||||||
|
valves,
|
||||||
|
me_next as usize,
|
||||||
|
elephant,
|
||||||
|
next_opened,
|
||||||
|
next_rate,
|
||||||
|
steps - 1,
|
||||||
|
));
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
// Both open valves
|
||||||
|
if me_can_open && ele_can_open {
|
||||||
|
let next_opened = opened | 1 << me | 1 << elephant;
|
||||||
|
let next_rate = rate + valves[me].flow + valves[elephant].flow;
|
||||||
|
released = released.max(dfs_elephant(
|
||||||
|
cache,
|
||||||
|
valves,
|
||||||
|
me,
|
||||||
|
elephant,
|
||||||
|
next_opened,
|
||||||
|
next_rate,
|
||||||
|
steps - 1,
|
||||||
|
));
|
||||||
|
}
|
||||||
|
|
||||||
|
// Both move
|
||||||
|
if !me_can_open || !ele_can_open {
|
||||||
|
for me_next in valves[me].connections.iter().copied() {
|
||||||
|
for elephant_next in valves[elephant].connections.iter().copied() {
|
||||||
|
released = released.max(dfs_elephant(
|
||||||
|
cache,
|
||||||
|
valves,
|
||||||
|
me_next as usize,
|
||||||
|
elephant_next as usize,
|
||||||
|
opened,
|
||||||
|
rate,
|
||||||
|
steps - 1,
|
||||||
|
));
|
||||||
|
}
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
released += rate;
|
||||||
|
cache.insert((opened, steps, me as u16, elephant as u16), released);
|
||||||
|
released
|
||||||
|
}
|
||||||
|
|
||||||
|
pub fn part1(input: Vec<String>) -> String {
|
||||||
|
let valves = parse_input(&input);
|
||||||
|
let mut cache = HashMap::new();
|
||||||
|
|
||||||
|
let valve = valves
|
||||||
|
.iter()
|
||||||
|
.enumerate()
|
||||||
|
.find(|(_, v)| v.name == "AA")
|
||||||
|
.unwrap()
|
||||||
|
.0;
|
||||||
|
let res = dfs(&mut cache, &valves, valve, 0, 0, 30);
|
||||||
|
|
||||||
|
res.to_string()
|
||||||
|
}
|
||||||
|
|
||||||
|
pub fn part2(input: Vec<String>) -> String {
|
||||||
|
let valves = parse_input(&input);
|
||||||
|
let mut cache = HashMap::new();
|
||||||
|
|
||||||
|
let valve = valves
|
||||||
|
.iter()
|
||||||
|
.enumerate()
|
||||||
|
.find(|(_, v)| v.name == "AA")
|
||||||
|
.unwrap()
|
||||||
|
.0;
|
||||||
|
let res = dfs_elephant(&mut cache, &valves, valve, valve, 0, 0, 26);
|
||||||
|
|
||||||
|
res.to_string()
|
||||||
|
}
|
||||||
|
|
||||||
|
#[cfg(test)]
|
||||||
|
mod tests {
|
||||||
|
use super::*;
|
||||||
|
|
||||||
|
const DAY: u8 = 16;
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_example1() {
|
||||||
|
assert_eq!(part1(crate::read_example(DAY)), "1651");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_example2() {
|
||||||
|
assert_eq!(part2(crate::read_example(DAY)), "1707");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_part1() {
|
||||||
|
assert_eq!(part1(crate::read_input(DAY)), "1906");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_part2() {
|
||||||
|
assert_eq!(part2(crate::read_input(DAY)), "2548");
|
||||||
|
}
|
||||||
|
}
|
143
src/day17.rs
Normal file
143
src/day17.rs
Normal file
|
@ -0,0 +1,143 @@
|
||||||
|
//! Day 17: Pyroclastic Flow
|
||||||
|
|
||||||
|
use std::collections::HashSet;
|
||||||
|
|
||||||
|
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
|
||||||
|
struct Coord(i64, i64);
|
||||||
|
|
||||||
|
impl Coord {
|
||||||
|
fn sx(self, dx: i64) -> Self {
|
||||||
|
Self(self.0 + dx, self.1)
|
||||||
|
}
|
||||||
|
|
||||||
|
fn sy(self, dy: i64) -> Self {
|
||||||
|
Self(self.0, self.1 + dy)
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
fn parse_input(input: &[String]) -> Vec<i64> {
|
||||||
|
let line = input.first().unwrap();
|
||||||
|
line.chars()
|
||||||
|
.filter_map(|c| match c {
|
||||||
|
'>' => Some(1),
|
||||||
|
'<' => Some(-1),
|
||||||
|
_ => None,
|
||||||
|
})
|
||||||
|
.collect()
|
||||||
|
}
|
||||||
|
|
||||||
|
fn rock_coords(rock_i: usize, h: i64) -> Vec<Coord> {
|
||||||
|
// bottom left coord
|
||||||
|
let coord = Coord(2, h + 3);
|
||||||
|
|
||||||
|
match rock_i % 5 {
|
||||||
|
0 => vec![coord, coord.sx(1), coord.sx(2), coord.sx(3)],
|
||||||
|
1 => vec![
|
||||||
|
coord.sx(1),
|
||||||
|
coord.sy(1),
|
||||||
|
coord.sx(1).sy(1),
|
||||||
|
coord.sx(2).sy(1),
|
||||||
|
coord.sx(1).sy(2),
|
||||||
|
],
|
||||||
|
2 => vec![
|
||||||
|
coord,
|
||||||
|
coord.sx(1),
|
||||||
|
coord.sx(2),
|
||||||
|
coord.sx(2).sy(1),
|
||||||
|
coord.sx(2).sy(2),
|
||||||
|
],
|
||||||
|
3 => vec![coord, coord.sy(1), coord.sy(2), coord.sy(3)],
|
||||||
|
4 => vec![coord, coord.sx(1), coord.sy(1), coord.sx(1).sy(1)],
|
||||||
|
_ => panic!(),
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
// returns new height
|
||||||
|
fn drop_rock(
|
||||||
|
rock_i: usize,
|
||||||
|
grid: &mut HashSet<Coord>,
|
||||||
|
h: i64,
|
||||||
|
shifts: &[i64],
|
||||||
|
si: &mut usize,
|
||||||
|
) -> i64 {
|
||||||
|
let mut coords = rock_coords(rock_i, h);
|
||||||
|
let mut coords_shifted;
|
||||||
|
|
||||||
|
loop {
|
||||||
|
let shift = shifts[*si % shifts.len()];
|
||||||
|
*si += 1;
|
||||||
|
coords_shifted = coords.iter().map(|c| c.sx(shift)).collect::<Vec<_>>();
|
||||||
|
|
||||||
|
// check shift
|
||||||
|
if coords_shifted
|
||||||
|
.iter()
|
||||||
|
.any(|c| c.0 < 0 || c.0 > 6 || grid.contains(c))
|
||||||
|
{
|
||||||
|
coords_shifted = coords;
|
||||||
|
}
|
||||||
|
|
||||||
|
let coords_dropped = coords_shifted.iter().map(|c| c.sy(-1)).collect::<Vec<_>>();
|
||||||
|
if coords_dropped.iter().any(|c| c.1 < 0 || grid.contains(c)) {
|
||||||
|
grid.extend(coords_shifted.iter());
|
||||||
|
return h.max(coords_shifted.iter().map(|c| c.1).max().unwrap_or_default() + 1);
|
||||||
|
}
|
||||||
|
coords_shifted = coords_dropped;
|
||||||
|
coords = coords_shifted.clone();
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
fn drop_rocks(shifts: &[i64], n: usize) -> String {
|
||||||
|
let mut h = 0;
|
||||||
|
let mut grid: HashSet<Coord> = HashSet::new();
|
||||||
|
let mut si = 0;
|
||||||
|
|
||||||
|
for i in 0..n {
|
||||||
|
h = drop_rock(i, &mut grid, h, shifts, &mut si);
|
||||||
|
|
||||||
|
if i > 0 && i % 1_000_000 == 0 {
|
||||||
|
println!("prog: {}M", i / 1_000_000);
|
||||||
|
grid.retain(|c| c.1 < h - 5);
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
h.to_string()
|
||||||
|
}
|
||||||
|
|
||||||
|
pub fn part1(input: Vec<String>) -> String {
|
||||||
|
let shifts = parse_input(&input);
|
||||||
|
drop_rocks(&shifts, 2022)
|
||||||
|
}
|
||||||
|
|
||||||
|
pub fn part2(_input: Vec<String>) -> String {
|
||||||
|
// 10092
|
||||||
|
// let shifts = parse_input(&input);
|
||||||
|
// drop_rocks(&shifts, 1_000_000_000_000)
|
||||||
|
String::new()
|
||||||
|
}
|
||||||
|
|
||||||
|
#[cfg(test)]
|
||||||
|
mod tests {
|
||||||
|
use super::*;
|
||||||
|
|
||||||
|
const DAY: u8 = 17;
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_example1() {
|
||||||
|
assert_eq!(part1(crate::read_example(DAY)), "3068");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_example2() {
|
||||||
|
assert_eq!(part2(crate::read_example(DAY)), "");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_part1() {
|
||||||
|
assert_eq!(part1(crate::read_input(DAY)), "3173");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_part2() {
|
||||||
|
assert_eq!(part2(crate::read_input(DAY)), "");
|
||||||
|
}
|
||||||
|
}
|
|
@ -23,6 +23,8 @@ mod day12;
|
||||||
mod day13;
|
mod day13;
|
||||||
mod day14;
|
mod day14;
|
||||||
mod day15;
|
mod day15;
|
||||||
|
mod day16;
|
||||||
|
mod day17;
|
||||||
|
|
||||||
pub(crate) fn read_input(day: u8) -> Vec<String> {
|
pub(crate) fn read_input(day: u8) -> Vec<String> {
|
||||||
read_input_file(path!("input" / format!("day{}.txt", day)))
|
read_input_file(path!("input" / format!("day{}.txt", day)))
|
||||||
|
@ -79,6 +81,8 @@ days! {
|
||||||
13, day13,
|
13, day13,
|
||||||
14, day14,
|
14, day14,
|
||||||
15, day15,
|
15, day15,
|
||||||
|
16, day16,
|
||||||
|
17, day17,
|
||||||
}
|
}
|
||||||
|
|
||||||
fn main() {
|
fn main() {
|
||||||
|
|
Loading…
Reference in a new issue