day 17 (incomplete)

example/day16.txt

@@ -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

example/day17.txt

@@ -0,0 +1 @@
+>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>

input/day16.txt

@@ -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

src/day15.rs

@@ -1,13 +1,28 @@
 //! Day 15: Beacon Exclusion Zone
 
-use std::collections::HashSet;
-
+use itertools::Itertools;
 use once_cell::sync::Lazy;
 use regex::Regex;
 
 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(|| {
         Regex::new("Sensor at x=(-?\\d+), y=(-?\\d+): closest beacon is at x=(-?\\d+), y=(-?\\d+)")
             .unwrap()
@@ -17,7 +32,8 @@ fn parse_input(input: &[String]) -> Vec<(Coord, Coord)> {
         .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(),
@@ -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
 }
 
-fn beacon_exclude(pos: Coord, closest: Coord, excluded: &mut HashSet<Coord>, row: i32) {
-    let dist = mdist(pos, closest);
+fn line_possible_positions(sensors: &[Sensor], y: i32, min: i32, max: i32) -> Vec<Coord> {
+    let mut x = min;
+    let mut res = Vec::new();
 
-    for x in pos.0 - dist..pos.0 + dist {
-        let point = (x, row);
-        if point != closest && mdist(pos, point) <= dist {
-            excluded.insert(point);
-        }
+    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;
             }
         }
 
-fn beacon_exclude_section(pos: Coord, closest: Coord, excluded: &mut HashSet<Coord>, limit: i32) {
-    let dist = mdist(pos, closest);
-
-    for y in 0..=limit {
-        for x in 0..=limit {
-            let point = (x, y);
-            if mdist(pos, point) <= dist {
-                excluded.insert(point);
-            }
+        if !jumped {
+            res.push((x, y));
+            x += 1;
         }
     }
+    res
 }
 
 fn _part1(input: Vec<String>, row: i32) -> String {
     let sensors = parse_input(&input);
-    let mut excluded = HashSet::new();
 
-    sensors
+    let x_minmax = sensors
         .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 {
     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 x in 0..limit {
-            let point = (x, y);
-            if !excluded.contains(&point) {
-                dbg!(&point);
-                let f = point.0 * 4000000 + point.1;
-                return f.to_string();
+        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!("not found")
+    panic!("distress beacon not found")
 }
 
 pub fn part1(input: Vec<String>) -> String {
-    _part1(input, 2000000)
+    _part1(input, 2_000_000)
 }
 
 pub fn part2(input: Vec<String>) -> String {
-    _part2(input, 4000000)
+    _part2(input, 4_000_000)
 }
 
 #[cfg(test)]
@@ -122,11 +152,11 @@ mod tests {
 
     #[test]
     fn t_part1() {
-        assert_eq!(part1(crate::read_input(DAY)), "");
+        assert_eq!(part1(crate::read_input(DAY)), "5166077");
     }
 
     #[test]
     fn t_part2() {
-        assert_eq!(part2(crate::read_input(DAY)), "");
+        assert_eq!(part2(crate::read_input(DAY)), "13071206703981");
     }
 }

src/day16.rs

@@ -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");
+    }
+}

src/day17.rs

@@ -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)), "");
+    }
+}

src/main.rs

@@ -23,6 +23,8 @@ mod day12;
 mod day13;
 mod day14;
 mod day15;
+mod day16;
+mod day17;
 
 pub(crate) fn read_input(day: u8) -> Vec<String> {
     read_input_file(path!("input" / format!("day{}.txt", day)))
@@ -79,6 +81,8 @@ days! {
     13, day13,
     14, day14,
     15, day15,
+    16, day16,
+    17, day17,
 }
 
 fn main() {