Problem 11
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
After all this time, I still haven't figured out a good way to import information from txt files.
So I hard coded it... as an array, a multidimensional array, a constant multidimensional array
const DATA: [[u32;20]; 20] = [
[08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08],
...
[01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]];
So that worked out. Obviously I cut the center out for this post but it is in the code.
Once that was out of the way, I was able to focus on the logic. Now, I separated much of the logic into different functions. While I could pass the values through to them, since I'm not editing the grid, I decided to keep it immutable and as a constant. It honestly makes reading the code easier (for me) but I'm not sure if that's really the best way to go about it. In this instance though, I think it's the best way.
Here's my main function:
fn main(){
let mut max_sum: u32 = 0;
for x in 0..DATA.len(){
for y in 0..DATA[x].len(){
let sum = eval(x as u32, y as u32);
if sum > max_sum{max_sum = sum};
}
}
println!("{}", max_sum);
}
I tried to keep my main function as brief as possible. so the loop is pretty straight forward.
Loop through each line, then loop through each number. I declared a sum and if that sum is greater than the max, it replaces it. If not continue to the next. The sum is equal to the return of a function eval that passes in the x and y numbers (numerical locations in the grid).
So what does eval do?
fn eval(x: u32, y: u32) -> u32 {
let data_vec: Vec<u32> = vec![eval_vertical(x,y), eval_right(x,y),
eval_diag_r(x,y), eval_diag_l(x,y)];
let ans = data_vec.iter().fold(std::u32::MIN, |a,b| a.max(*b));
ans
}
As you can see it does a few things. First, it creates a vector. Then it sorts that vector and sets ans to the max value in that vector and returns that from the function.
The vector itself is set to the values of all these functions. Each function does basically the same thing. It multiplies the values of the number and then the 3 down for vertical, the 3 right for right and then the diags right and left. I even put in a requirement for x and y positions so it didn't error out by going over the index.
fn eval_vertical(x: u32, y: u32) -> u32{
let x: usize = x as usize;
let y: usize = y as usize;
if x > 16 {
return 0;
}
DATA[x][y] * DATA[x+1][y] * DATA[x+2][y] * DATA[x+3][y]
}
fn eval_right(x: u32, y: u32) -> u32{
let x: usize = x as usize;
let y: usize = y as usize;
if y > 16{
return 0;
}
DATA[x][y] * DATA[x][y+1] * DATA[x][y+2] * DATA[x][y+3]
}
fn eval_diag_r(x: u32, y: u32) -> u32{
let x: usize = x as usize;
let y: usize = y as usize;
if y > 16 || x > 16 {
return 0;
}
DATA[x][y] * DATA[x+1][y+1] * DATA[x+2][y+2] * DATA[x+3][y+3]
}
fn eval_diag_l(x: u32, y: u32) -> u32{
let x: usize = x as usize;
let y: usize = y as usize;
if y < 3 || x > 16 {
return 0;
}
DATA[x][y] * DATA[x+1][y-1] * DATA[x+2][y-2] * DATA[x+3][y-3]
}
As you can see, they're closely repetitive and could merit a rewrite using recursion and even a direction argument with a match case... shrug. But that's not what I did.
It could cut the code size in half though.
Anyways, that's the code.
I didn't see any other rust answer. To the next problem.
No comments:
Post a Comment