1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
use std::collections::hash_map::Entry;
use std::collections::HashMap;
use crate::input::Input;
pub fn solve(input: &mut Input) -> Result<u64, String> {
let target_rocks_count = input.part_values(2022, 1_000_000_000_000_u64);
let mut grid = Grid::new();
let mut seen = HashMap::new();
let mut direction_iterator = input.text.bytes().enumerate().cycle();
for (current_rock_count, &(rock_width, rock_bitmask)) in ROCK_SEQUENCE
.iter()
.cycle()
.enumerate()
.take(target_rocks_count.min(100_000) as usize)
{
let (mut rock_bottom_y, mut rock_left_x) = (grid.highest_rock + 3, 2);
for (direction_idx, direction) in direction_iterator.by_ref() {
let pushed_x = rock_left_x + if direction == b'<' { -1 } else { 1 };
let push_possible = pushed_x >= 0
&& pushed_x + rock_width as i32 <= Grid::WIDTH as i32
&& grid.can_place_rock(rock_bitmask, pushed_x as usize, rock_bottom_y);
if push_possible {
rock_left_x = pushed_x;
}
if rock_bottom_y != 0
&& grid.can_place_rock(rock_bitmask, rock_left_x as usize, rock_bottom_y - 1)
{
rock_bottom_y -= 1;
continue;
}
grid.settle_rock(rock_bitmask, rock_left_x as usize, rock_bottom_y);
if input.is_part_two() {
let rock_and_direction_idx =
(current_rock_count % ROCK_SEQUENCE.len(), direction_idx);
match seen.entry(rock_and_direction_idx) {
Entry::Vacant(entry) => {
entry.insert((current_rock_count, grid.highest_rock));
}
Entry::Occupied(entry) => {
let (last_seen_rock_drop_iteration, last_seen_highest_rock) = *entry.get();
let rocks_per_cycle =
(current_rock_count - last_seen_rock_drop_iteration) as u64;
let remaining_rocks = target_rocks_count - current_rock_count as u64;
if remaining_rocks % rocks_per_cycle == 0 {
let remaining_cycles = remaining_rocks / rocks_per_cycle;
let highest_rock_growth = grid.highest_rock - last_seen_highest_rock;
return Ok(grid.highest_rock as u64
+ remaining_cycles * highest_rock_growth as u64
- 1);
}
}
}
}
break;
}
}
Ok(grid.highest_rock as u64)
}
type Rock = u16;
const ROCK_SEQUENCE: [(usize, Rock); 5] = [
(4, 0b0000_0000_0000_1111),
(3, 0b0000_0010_0111_0010),
(3, 0b0000_0100_0100_0111),
(1, 0b0001_0001_0001_0001),
(2, 0b0000_0000_0011_0011),
];
struct Grid {
data: [u8; Self::MAX_HEIGHT],
highest_rock: usize,
}
impl Grid {
const WIDTH: usize = 7;
const MAX_HEIGHT: usize = 8192;
const fn new() -> Self {
Self {
data: [0; Self::MAX_HEIGHT],
highest_rock: 0,
}
}
fn can_place_rock(&self, rock: Rock, left_edge_x: usize, bottom_edge_y: usize) -> bool {
rock & ((u16::from(self.data[bottom_edge_y] >> left_edge_x) & 0b1111)
+ ((u16::from(self.data[bottom_edge_y + 1] >> left_edge_x) & 0b1111) << 4)
+ ((u16::from(self.data[bottom_edge_y + 2] >> left_edge_x) & 0b1111) << 8)
+ ((u16::from(self.data[bottom_edge_y + 3] >> left_edge_x) & 0b1111) << 12))
== 0
}
fn settle_rock(&mut self, rock: Rock, left_edge_x: usize, bottom_edge_y: usize) {
self.data[bottom_edge_y] |= ((rock & 0b1111) as u8) << left_edge_x;
self.data[bottom_edge_y + 1] |= (((rock >> 4) & 0b1111) as u8) << left_edge_x;
self.data[bottom_edge_y + 2] |= (((rock >> 8) & 0b1111) as u8) << left_edge_x;
self.data[bottom_edge_y + 3] |= (((rock >> 12) & 0b1111) as u8) << left_edge_x;
let rock_height = (4 - rock.leading_zeros() / 4) as usize;
self.highest_rock = self.highest_rock.max(bottom_edge_y + rock_height);
}
}
#[test]
pub fn tests() {
use crate::input::{test_part_one, test_part_two};
let test_input = ">>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>";
test_part_one!(test_input => 3068);
test_part_two!(test_input => 1_514_285_714_288);
let real_input = include_str!("day17_input.txt");
test_part_one!(real_input => 3117);
test_part_two!(real_input => 1_553_314_121_019);
}