Compare commits
3 commits
Author | SHA1 | Date | |
---|---|---|---|
2f7d33f7fd | |||
b3768bc2c2 | |||
4951abb7f2 |
10 changed files with 675 additions and 0 deletions
14
example/day15.txt
Normal file
14
example/day15.txt
Normal file
|
@ -0,0 +1,14 @@
|
||||||
|
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
|
||||||
|
Sensor at x=9, y=16: closest beacon is at x=10, y=16
|
||||||
|
Sensor at x=13, y=2: closest beacon is at x=15, y=3
|
||||||
|
Sensor at x=12, y=14: closest beacon is at x=10, y=16
|
||||||
|
Sensor at x=10, y=20: closest beacon is at x=10, y=16
|
||||||
|
Sensor at x=14, y=17: closest beacon is at x=10, y=16
|
||||||
|
Sensor at x=8, y=7: closest beacon is at x=2, y=10
|
||||||
|
Sensor at x=2, y=0: closest beacon is at x=2, y=10
|
||||||
|
Sensor at x=0, y=11: closest beacon is at x=2, y=10
|
||||||
|
Sensor at x=20, y=14: closest beacon is at x=25, y=17
|
||||||
|
Sensor at x=17, y=20: closest beacon is at x=21, y=22
|
||||||
|
Sensor at x=16, y=7: closest beacon is at x=15, y=3
|
||||||
|
Sensor at x=14, y=3: closest beacon is at x=15, y=3
|
||||||
|
Sensor at x=20, y=1: closest beacon is at x=15, y=3
|
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 @@
|
||||||
|
>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
|
38
input/day15.txt
Normal file
38
input/day15.txt
Normal file
|
@ -0,0 +1,38 @@
|
||||||
|
Sensor at x=2793338, y=1910659: closest beacon is at x=2504930, y=2301197
|
||||||
|
Sensor at x=2887961, y=129550: closest beacon is at x=2745008, y=-872454
|
||||||
|
Sensor at x=3887055, y=2785942: closest beacon is at x=4322327, y=2605441
|
||||||
|
Sensor at x=3957399, y=2164042: closest beacon is at x=3651713, y=1889668
|
||||||
|
Sensor at x=1268095, y=1265989: closest beacon is at x=1144814, y=2000000
|
||||||
|
Sensor at x=2093967, y=2103436: closest beacon is at x=2504930, y=2301197
|
||||||
|
Sensor at x=2980126, y=1348046: closest beacon is at x=3651713, y=1889668
|
||||||
|
Sensor at x=508134, y=3998686: closest beacon is at x=1123963, y=4608563
|
||||||
|
Sensor at x=2982740, y=3604350: closest beacon is at x=2756683, y=3240616
|
||||||
|
Sensor at x=2372671, y=3929034: closest beacon is at x=2756683, y=3240616
|
||||||
|
Sensor at x=437628, y=1124644: closest beacon is at x=570063, y=959065
|
||||||
|
Sensor at x=3271179, y=3268845: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=1899932, y=730465: closest beacon is at x=570063, y=959065
|
||||||
|
Sensor at x=1390358, y=3881569: closest beacon is at x=1123963, y=4608563
|
||||||
|
Sensor at x=554365, y=989190: closest beacon is at x=570063, y=959065
|
||||||
|
Sensor at x=2225893, y=2703661: closest beacon is at x=2504930, y=2301197
|
||||||
|
Sensor at x=3755905, y=1346206: closest beacon is at x=3651713, y=1889668
|
||||||
|
Sensor at x=3967103, y=3930797: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=3534099, y=2371166: closest beacon is at x=3651713, y=1889668
|
||||||
|
Sensor at x=3420789, y=1720583: closest beacon is at x=3651713, y=1889668
|
||||||
|
Sensor at x=2222479, y=3278186: closest beacon is at x=2756683, y=3240616
|
||||||
|
Sensor at x=100457, y=871319: closest beacon is at x=570063, y=959065
|
||||||
|
Sensor at x=1330699, y=2091946: closest beacon is at x=1144814, y=2000000
|
||||||
|
Sensor at x=598586, y=99571: closest beacon is at x=570063, y=959065
|
||||||
|
Sensor at x=3436099, y=3392932: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=3338431, y=3346334: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=3892283, y=688090: closest beacon is at x=3651713, y=1889668
|
||||||
|
Sensor at x=1485577, y=1929020: closest beacon is at x=1144814, y=2000000
|
||||||
|
Sensor at x=2991003, y=2951060: closest beacon is at x=2756683, y=3240616
|
||||||
|
Sensor at x=2855486, y=2533468: closest beacon is at x=2504930, y=2301197
|
||||||
|
Sensor at x=750865, y=1619637: closest beacon is at x=1144814, y=2000000
|
||||||
|
Sensor at x=3378101, y=3402212: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=3515528, y=2950404: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=163133, y=2640553: closest beacon is at x=-1016402, y=3057364
|
||||||
|
Sensor at x=1765550, y=3021994: closest beacon is at x=2756683, y=3240616
|
||||||
|
Sensor at x=534625, y=1056421: closest beacon is at x=570063, y=959065
|
||||||
|
Sensor at x=3418549, y=3380980: closest beacon is at x=3444757, y=3373782
|
||||||
|
Sensor at x=29, y=389033: closest beacon is at x=570063, y=959065
|
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
162
src/day15.rs
Normal file
162
src/day15.rs
Normal file
|
@ -0,0 +1,162 @@
|
||||||
|
//! Day 15: Beacon Exclusion Zone
|
||||||
|
|
||||||
|
use itertools::Itertools;
|
||||||
|
use once_cell::sync::Lazy;
|
||||||
|
use regex::Regex;
|
||||||
|
|
||||||
|
type Coord = (i32, i32);
|
||||||
|
|
||||||
|
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(|| {
|
||||||
|
Regex::new("Sensor at x=(-?\\d+), y=(-?\\d+): closest beacon is at x=(-?\\d+), y=(-?\\d+)")
|
||||||
|
.unwrap()
|
||||||
|
});
|
||||||
|
|
||||||
|
input
|
||||||
|
.iter()
|
||||||
|
.map(|line| {
|
||||||
|
let cap = LINE_REGEX.captures(line).unwrap();
|
||||||
|
|
||||||
|
Sensor::new(
|
||||||
|
(
|
||||||
|
cap.get(1).unwrap().as_str().parse().unwrap(),
|
||||||
|
cap.get(2).unwrap().as_str().parse().unwrap(),
|
||||||
|
),
|
||||||
|
(
|
||||||
|
cap.get(3).unwrap().as_str().parse().unwrap(),
|
||||||
|
cap.get(4).unwrap().as_str().parse().unwrap(),
|
||||||
|
),
|
||||||
|
)
|
||||||
|
})
|
||||||
|
.collect()
|
||||||
|
}
|
||||||
|
|
||||||
|
fn mdist(p1: Coord, p2: Coord) -> i32 {
|
||||||
|
(p1.0.abs_diff(p2.0) + p1.1.abs_diff(p2.1)) as i32
|
||||||
|
}
|
||||||
|
|
||||||
|
fn line_possible_positions(sensors: &[Sensor], y: i32, min: i32, max: i32) -> Vec<Coord> {
|
||||||
|
let mut x = min;
|
||||||
|
let mut res = Vec::new();
|
||||||
|
|
||||||
|
while x <= max {
|
||||||
|
let mut jumped = false;
|
||||||
|
for sensor in sensors {
|
||||||
|
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;
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
if !jumped {
|
||||||
|
res.push((x, y));
|
||||||
|
x += 1;
|
||||||
|
}
|
||||||
|
}
|
||||||
|
res
|
||||||
|
}
|
||||||
|
|
||||||
|
fn _part1(input: Vec<String>, row: i32) -> String {
|
||||||
|
let sensors = parse_input(&input);
|
||||||
|
|
||||||
|
let x_minmax = sensors
|
||||||
|
.iter()
|
||||||
|
.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),
|
||||||
|
};
|
||||||
|
|
||||||
|
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 {
|
||||||
|
let sensors = parse_input(&input);
|
||||||
|
|
||||||
|
for y in 0..limit {
|
||||||
|
let positions = line_possible_positions(&sensors, y, 0, limit);
|
||||||
|
if let Some(pos) = positions.first() {
|
||||||
|
if positions.len() > 1 {
|
||||||
|
panic!("more than 1 distress beacon found")
|
||||||
|
}
|
||||||
|
|
||||||
|
let freq = pos.0 as i64 * 4_000_000 + pos.1 as i64;
|
||||||
|
return freq.to_string();
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
panic!("distress beacon not found")
|
||||||
|
}
|
||||||
|
|
||||||
|
pub fn part1(input: Vec<String>) -> String {
|
||||||
|
_part1(input, 2_000_000)
|
||||||
|
}
|
||||||
|
|
||||||
|
pub fn part2(input: Vec<String>) -> String {
|
||||||
|
_part2(input, 4_000_000)
|
||||||
|
}
|
||||||
|
|
||||||
|
#[cfg(test)]
|
||||||
|
mod tests {
|
||||||
|
use super::*;
|
||||||
|
|
||||||
|
const DAY: u8 = 15;
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_example1() {
|
||||||
|
assert_eq!(_part1(crate::read_example(DAY), 10), "26");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_example2() {
|
||||||
|
assert_eq!(_part2(crate::read_example(DAY), 20), "56000011");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_part1() {
|
||||||
|
assert_eq!(part1(crate::read_input(DAY)), "5166077");
|
||||||
|
}
|
||||||
|
|
||||||
|
#[test]
|
||||||
|
fn t_part2() {
|
||||||
|
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)), "");
|
||||||
|
}
|
||||||
|
}
|
|
@ -22,6 +22,9 @@ mod day11;
|
||||||
mod day12;
|
mod day12;
|
||||||
mod day13;
|
mod day13;
|
||||||
mod day14;
|
mod day14;
|
||||||
|
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)))
|
||||||
|
@ -77,6 +80,9 @@ days! {
|
||||||
12, day12,
|
12, day12,
|
||||||
13, day13,
|
13, day13,
|
||||||
14, day14,
|
14, day14,
|
||||||
|
15, day15,
|
||||||
|
16, day16,
|
||||||
|
17, day17,
|
||||||
}
|
}
|
||||||
|
|
||||||
fn main() {
|
fn main() {
|
||||||
|
|
Loading…
Reference in a new issue