|
| 1 | +use std::{collections::HashMap, fs}; |
| 2 | + |
| 3 | +struct Rock { |
| 4 | + rows: Vec<Vec<usize>>, |
| 5 | + base_y: usize, |
| 6 | +} |
| 7 | + |
| 8 | +fn generate_rock(kind: usize) -> Rock { |
| 9 | + const X: usize = 2; |
| 10 | + let base_y = 3; |
| 11 | + let rows = match kind % 5 { |
| 12 | + 0 => vec![vec![X, X + 1, X + 2, X + 3]], |
| 13 | + 1 => vec![vec![X + 1], vec![X, X + 1, X + 2], vec![X + 1]], |
| 14 | + 2 => vec![vec![X, X + 1, X + 2], vec![X + 2], vec![X + 2]], |
| 15 | + 3 => vec![vec![X], vec![X], vec![X], vec![X]], |
| 16 | + 4 => vec![vec![X, X + 1], vec![X, X + 1]], |
| 17 | + _ => unreachable!(), |
| 18 | + }; |
| 19 | + Rock { rows, base_y } |
| 20 | +} |
| 21 | + |
| 22 | +fn history_idx(history: &[Vec<usize>], y_base: usize, y_offset: usize) -> Option<usize> { |
| 23 | + let y = y_base + y_offset; |
| 24 | + (y < history.len()).then_some(history.len() - 1 - (history.len() - y - 1)) |
| 25 | +} |
| 26 | + |
| 27 | +fn adjust(rock: &mut Rock, history_x: &[Vec<usize>], step: (i32, i32)) -> bool { |
| 28 | + // Check y-axis bounds. |
| 29 | + let new_base_y = if step.1 < 0 { |
| 30 | + if rock.base_y == 0 { |
| 31 | + return false; |
| 32 | + } |
| 33 | + rock.base_y - step.1.unsigned_abs() as usize |
| 34 | + } else { |
| 35 | + rock.base_y + step.1 as usize |
| 36 | + }; |
| 37 | + for (y_offset, row) in rock.rows.iter().enumerate() { |
| 38 | + for &x in row { |
| 39 | + // Check x-axis bounds. |
| 40 | + let x = match step.0 { |
| 41 | + step if step > 0 => { |
| 42 | + if x == 6 { |
| 43 | + return false; |
| 44 | + } |
| 45 | + x + step as usize |
| 46 | + } |
| 47 | + step if step < 0 => { |
| 48 | + if x == 0 { |
| 49 | + return false; |
| 50 | + } |
| 51 | + x - step.unsigned_abs() as usize |
| 52 | + } |
| 53 | + _ => x, |
| 54 | + }; |
| 55 | + // Given the new position, check for collisions. |
| 56 | + if let Some(hist_idx) = history_idx(history_x, new_base_y, y_offset) { |
| 57 | + if history_x[hist_idx].contains(&x) { |
| 58 | + return false; |
| 59 | + } |
| 60 | + } |
| 61 | + } |
| 62 | + } |
| 63 | + for row in rock.rows.iter_mut() { |
| 64 | + for x in row.iter_mut() { |
| 65 | + *x = (*x as isize + step.0 as isize) as usize; |
| 66 | + } |
| 67 | + } |
| 68 | + rock.base_y = new_base_y; |
| 69 | + true |
| 70 | +} |
| 71 | + |
| 72 | +fn ceiling(history_x: &[Vec<usize>]) -> Vec<usize> { |
| 73 | + (0..=6) |
| 74 | + .map(|x_index| { |
| 75 | + history_x |
| 76 | + .iter() |
| 77 | + .rev() |
| 78 | + .take_while(|x| !x.contains(&x_index)) |
| 79 | + .count() |
| 80 | + }) |
| 81 | + .collect() |
| 82 | +} |
| 83 | + |
| 84 | +fn settle_rock<'a>( |
| 85 | + rocks: &mut impl Iterator<Item = (usize, Rock)>, |
| 86 | + jet: &mut impl Iterator<Item = (usize, &'a u8)>, |
| 87 | + history_x: &mut Vec<Vec<usize>>, |
| 88 | +) -> (Vec<usize>, usize, usize) { |
| 89 | + let (rock_idx, mut rock) = rocks.next().unwrap(); |
| 90 | + rock.base_y += history_x.len(); |
| 91 | + let jet_idx = loop { |
| 92 | + let (jet_idx, x_step) = jet.next().unwrap(); |
| 93 | + let step = (if *x_step == b'>' { 1 } else { -1 }, 0); |
| 94 | + adjust(&mut rock, history_x, step); |
| 95 | + if !adjust(&mut rock, history_x, (0, -1)) { |
| 96 | + break jet_idx; |
| 97 | + } |
| 98 | + }; |
| 99 | + // Merge the rock rows into the history. |
| 100 | + for (offset, r) in rock.rows.into_iter().enumerate() { |
| 101 | + if let Some(idx) = history_idx(history_x, rock.base_y, offset) { |
| 102 | + history_x[idx].extend(r); |
| 103 | + } else { |
| 104 | + history_x.push(r); |
| 105 | + } |
| 106 | + } |
| 107 | + (ceiling(history_x), rock_idx, jet_idx) |
| 108 | +} |
| 109 | + |
| 110 | +fn solve(num_rocks: usize, jet_pattern: &[u8]) -> usize { |
| 111 | + let mut rocks_fallen = 0; |
| 112 | + let mut history_x = Vec::with_capacity(100); |
| 113 | + let mut cache = HashMap::new(); |
| 114 | + let mut jet = jet_pattern.iter().enumerate().cycle(); |
| 115 | + let mut rocks = (0..5).map(generate_rock).enumerate().cycle(); |
| 116 | + while rocks_fallen < num_rocks { |
| 117 | + let state = settle_rock(&mut rocks, &mut jet, &mut history_x); |
| 118 | + rocks_fallen += 1; |
| 119 | + if let Some((rocks_fallen_before, height_before)) = cache.get(&state) { |
| 120 | + let blocks_in_cycle = rocks_fallen - rocks_fallen_before; |
| 121 | + let remaining = num_rocks - rocks_fallen; |
| 122 | + let repeats = remaining / blocks_in_cycle; |
| 123 | + let reminder = remaining - (repeats * blocks_in_cycle); |
| 124 | + let mut total_height = history_x.len() + (history_x.len() - height_before) * repeats; |
| 125 | + for _ in 0..reminder { |
| 126 | + let height_now = history_x.len(); |
| 127 | + settle_rock(&mut rocks, &mut jet, &mut history_x); |
| 128 | + total_height += history_x.len() - height_now; |
| 129 | + } |
| 130 | + return total_height; |
| 131 | + } |
| 132 | + cache.insert(state, (rocks_fallen, history_x.len())); |
| 133 | + } |
| 134 | + history_x.len() |
| 135 | +} |
| 136 | + |
| 137 | +fn main() { |
| 138 | + let file = fs::read_to_string("aoc2022/inputs/day17.input").unwrap(); |
| 139 | + println!("part 1: {}", solve(2022, file.as_bytes())); |
| 140 | + println!("part 2: {}", solve(1000000000000, file.as_bytes())); |
| 141 | +} |
0 commit comments