-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday11.rs
182 lines (157 loc) · 6.03 KB
/
day11.rs
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
// vi: set shiftwidth=4 tabstop=4 expandtab:
use common::input::check_answer;
use common::input::get_answers;
use common::input::get_first_line_from_file;
use std::time::Instant;
const INPUT_FILEPATH: &str = "../resources/year2018_day11_input.txt";
const ANSWERS_FILEPATH: &str = "../resources/year2018_day11_answer.txt";
type Int = i32;
type InputContent = usize;
fn get_input_from_str(string: &str) -> InputContent {
string.parse().unwrap()
}
fn get_power_level(x: usize, y: usize, serial: InputContent) -> Int {
let rack_id = x + 10;
let power = (rack_id * y + serial) * rack_id;
let digit: Int = ((power / 100) % 10).try_into().unwrap();
let ret = digit - 5;
assert!((-5..5).contains(&ret));
ret
}
/*
From the original grid, a cumulative grid can be computed.
x x
+------+---+ +------+---+
| | | |######| |
y +------+ | y +------+ |
| | | |
| | | |
+----------+ +----------+
g(x,y) c(x,y) = g(0, 0) + ... + g(x, 0)
+ g(0, 1) + ... + g(x, 1)
+ ...
+ g(0, y) + ... + g(x, y)
Then, the sum on an arbitrary sub-grid can be computed:
x1 x2
+----+---+-+
| |
| |
y1 + +---+ |
| |###| |
y2 + +---+ |
| |
| |
+----------+
sum(g(x,y) for x,y on the surface) is
x1 x2 x1 x2 x1 x2 x1 x2
+----+---+-+ +----+---+-+ +----+---+-+ +----+---+-+
|########| | |########| | |###| | |###| |
|########| | |--------+ | |###| | |---+ |
y1 +####+---+ | + | +###| | + |
|####|###| | - | | - |###| | + | |
y2 +----+---+ | + | +---+ | + |
| | | | | | | |
| | | | | | | |
+----------+ +----------+ +----------+ +----------+
c(x2,y2) - c(x2,y1-1) - c(x1-1,y2) + c(x1-1,y1-1)
Then each contribution is either counted:
- (1-0-0+0) = 1 time for a point in the sub-grid
- (1-1-1+1) = 0 time for a point in the upper-left corner
- (1-1-0+0) = 0 time for a point in the left corner or upper corner
This principle can be used to compute the values in the cumulative grid:
c(x,y) = g(x,y) + c(x,y-1) + c(x-1,y) - c(x-1,y-1)
*/
fn get_max_square(serial: InputContent, square_size: usize) -> (Int, usize, usize) {
const X_MAX: usize = 300;
const Y_MAX: usize = 300;
// Compute cumulative grid
let mut cum: [[Int; Y_MAX + 1]; X_MAX + 1] = [[0; Y_MAX + 1]; X_MAX + 1];
for x in 1..=X_MAX {
for y in 1..=Y_MAX {
let pow_x_y = get_power_level(x, y, serial);
cum[x][y] = pow_x_y + cum[x - 1][y] + cum[x][y - 1] - cum[x - 1][y - 1];
}
}
// Compute score for windows
let mut scores = Vec::new();
for x in 1..=(X_MAX - square_size + 1) {
let (x1, x2) = (x - 1, x + square_size - 1);
for y in 1..=(Y_MAX - square_size + 1) {
let (y1, y2) = (y - 1, y + square_size - 1);
let s = cum[x2][y2] + cum[x1][y1] - cum[x2][y1] - cum[x1][y2];
scores.push((s, x, y));
}
}
*scores.iter().max().unwrap()
}
fn get_max_square2(serial: InputContent) -> (Int, usize, usize, usize) {
const X_MAX: usize = 300;
const Y_MAX: usize = 300;
// Compute cumulative grid
let mut cum: [[Int; Y_MAX + 1]; X_MAX + 1] = [[0; Y_MAX + 1]; X_MAX + 1];
for x in 1..=X_MAX {
for y in 1..=Y_MAX {
let pow_x_y = get_power_level(x, y, serial);
cum[x][y] = pow_x_y + cum[x - 1][y] + cum[x][y - 1] - cum[x - 1][y - 1];
}
}
// Compute score for windows
let mut scores = Vec::new();
for square_size in 1..=X_MAX {
for x in 1..=(X_MAX - square_size + 1) {
let (x1, x2) = (x - 1, x + square_size - 1);
for y in 1..=(Y_MAX - square_size + 1) {
let (y1, y2) = (y - 1, y + square_size - 1);
let s = cum[x2][y2] + cum[x1][y1] - cum[x2][y1] - cum[x1][y2];
scores.push((s, x, y, square_size));
}
}
}
*scores.iter().max().unwrap()
}
fn part1(serial: InputContent) -> (usize, usize) {
let (_score, x, y) = get_max_square(serial, 3);
(x, y)
}
fn part2(serial: InputContent) -> (usize, usize, usize) {
let (_score, x, y, size) = get_max_square2(serial);
(x, y, size)
}
fn main() {
let before = Instant::now();
let data = get_input_from_str(&get_first_line_from_file(INPUT_FILEPATH));
let (ans, ans2) = get_answers(ANSWERS_FILEPATH);
let solved = true;
let res = part1(data);
check_answer(&format!("{},{}", res.0, res.1), ans, solved);
let res2 = part2(data);
check_answer(&format!("{},{},{}", res2.0, res2.1, res2.2), ans2, solved);
println!("Elapsed time: {:.2?}", before.elapsed());
}
#[cfg(test)]
mod tests {
use super::*;
const SKIP_SLOW: bool = true;
#[test]
fn test_power_level() {
assert_eq!(get_power_level(3, 5, 8), 4);
assert_eq!(get_power_level(122, 79, 57), -5);
assert_eq!(get_power_level(217, 196, 39), 0);
assert_eq!(get_power_level(101, 153, 71), 4);
}
#[test]
fn test_get_max_square() {
assert_eq!(get_max_square(18, 3), (29, 33, 45));
assert_eq!(get_max_square(42, 3), (30, 21, 61));
assert_eq!(part1(18), (33, 45));
assert_eq!(part1(42), (21, 61));
assert_eq!(get_max_square(18, 16), (113, 90, 269));
assert_eq!(get_max_square(42, 12), (119, 232, 251));
if !SKIP_SLOW {
assert_eq!(get_max_square2(18), (113, 90, 269, 16));
assert_eq!(get_max_square2(42), (119, 232, 251, 12));
assert_eq!(part2(18), (90, 269, 16));
assert_eq!(part2(42), (232, 251, 12));
}
}
}