Largest product in a grid: Project Euler 11

Question

Project Euler 11 — Largest product in a grid:

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?

I'm doing the #ProjectEuler100 challenge to learn Rust. I still have lots of places where the borrow checker slaps me in the face, but that is expected; generally I just do whatever the compiler says and it's happy. I think I'm slowly working my way to understanding there.

One thing that's been a constant unexpected pain is integer typing. It isn't clear to me how you're actually supposed to deal with integer types in practice, and what I'm doing right now is so ugly that it must be wrong.

It was at the point where I was making my own function just to do addition that I began to suspect I'd gone off the rails. There must be a better way.

What's the preferred way of doing this? Is there some better way than as to convert basic integer types?

Here are the guts to my solution of Project Euler problem 11: (The full solution is in my GitHub repo)

fn find_elem(grid: &[Vec<u64>], locx: usize, locy: usize) -> u64 {
    if locx < grid.len() {
        if locy < grid[locx].len() {
            return grid[locx][locy];
        }
    }
    0
}

fn add(lft: usize, rgt: i32) -> usize {
    // Returns 999 on negative
    let ret1: i64 = (lft as i64) + (rgt as i64);
    if ret1 < 0 {
        return 999;
    }
    ret1 as usize
}

fn search_grid(grid: &[Vec<u64>]) -> u64 {
    let mut max_found = 0;
    for direction in [(1, 0), (1, 1), (0, 1), (-1, 1)].iter() {
        for startx in 0..grid.len() {
            for starty in 0..grid[startx].len() {
                let result = find_elem(grid, startx, starty)
                    * find_elem(grid, add(startx, direction.0), add(starty, direction.1))
                    * find_elem(
                        grid,
                        add(startx, 2 * direction.0),
                        add(starty, 2 * direction.1),
                    )
                    * find_elem(
                        grid,
                        add(startx, 3 * direction.0),
                        add(starty, 3 * direction.1),
                    );
                if result > max_found {
                    max_found = result;
                }
            }
        }
    }
    max_found
}

Also, if anyone could tell me how to properly pass around a two-dimensional array in Rust (I could change the outer layer to &[], but couldn't figure out how to change the inner layer away from being a Vec), that'd be good.

It would probably be good to expand on how you're actually supposed to deal with integer types in practice, and what I'm doing right now is so ugly that it must be wrong with more specifics: what exactly feels wrong, etc. — Shepmaster, Mar 4 '20 at 15:57
I'm following the explicit advice that's in the "how to ask a question" guide. They say that the title should say what the code is supposed to do. The purpose of the code is to solve that particular problem. I initially had "A mess of integer types (in Rust)", which is my actual problem (to much integer type conversion/confusion) and got downvoted for it. I'm really confused about what I'm supposed to do to satisfy the codereview SE community. — Daniel Martin, Mar 4 '20 at 17:38
@πάνταῥεῖ it'd be useful to point to meta guidance on post titles (if there is any) and/or say specifically what could be improved. — Shepmaster, Mar 4 '20 at 18:04
I assume you are referring to this meta post? That makes sense, and I'll undo my changes. — Shepmaster, Mar 4 '20 at 18:44
The name of the challenge does not automatically reflect the contents of the challenge. I've added the problem description for you. In the future please do this yourself to prevent DVs and CVs. — L. F., Mar 5 '20 at 1:45

wasmup · Accepted Answer · 2020-03-05 09:08:53Z

Code review:
1. You don't need to use u64, since the input data is all u8, so use Vec<u8> like the following code and parse all the input data in one line:

fn main() {
    let s = "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";
    let grid: Vec<u8> = s.split_whitespace().map(|v| v.parse().unwrap()).collect();
    let mut max = 0;
    for row in 0..20 {
        for col in 0..20 {
            for direction in &[(0, 1), (1, 0), (1, -1), (1, 1)] {
                max = std::cmp::max(max, mul_4_adj(&grid, row, col, direction));
            }
        }
    }
    println!("max={}", max); // 70600674
}
// Calculate the product of four adjacent numbers in the same direction:
fn mul_4_adj(grid: &[u8], mut r: usize, mut c: usize, direction: &(i8, i8)) -> u32 {
    let mut f = 1;
    for _ in 0..4 {
        f *= grid[20 * r + c] as u32;
        let (row, col) = (r as i8 + direction.0, c as i8 + direction.1);
        if row < 0 || row >= 20 || col < 0 || col >= 20 {
            return 0;
        }
        r = row as usize;
        c = col as usize;
    }
    f
}

Using chunks with the CHUNK_SIZE of 20, instead of grid: &[Vec<u64>] use grid: &[&[u8]]:

fn main() {
    let s = "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";
    let v: Vec<u8> = s.split_whitespace().map(|v| v.parse().unwrap()).collect();
    let grid: Vec<_> = v.chunks(20).collect();
    let mut max = 0;
    for row in 0..grid.len() {
        for col in 0..grid[row].len() {
            for direction in &[(0, 1), (1, 0), (1, -1), (1, 1)] {
                max = std::cmp::max(max, mul_4_adj(&grid, row, col, direction));
            }
        }
    }
    println!("max={}", max); // 70600674
}
// Calculate the product of four adjacent numbers in the same direction:
fn mul_4_adj(grid: &[&[u8]], mut r: usize, mut c: usize, direction: &(i8, i8)) -> u32 {
    let mut f = 1;
    for _ in 0..4 {
        f *= grid[r][c] as u32;
        let (row, col) = (r as i8 + direction.0, c as i8 + direction.1);
        r = row as usize;
        c = col as usize;
        if row < 0 || col < 0 || r >= grid.len() || c >= grid[r].len() {
            return 0;
        }
    }
    f
}

Also instead of Vec<Vec<u64>> you may use a two-dimensional array in Rust:

let mut grid = [[0_u8; 20]; 20];

Then simply find and print the max:

fn main() {
    let gridstr = r#"
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
"#;
    let mut grid = [[0_u8; 20]; 20];
    let lines: Vec<_> = gridstr.trim().split("\n").collect();
    for row in 0..20 {
        let line: Vec<_> = lines[row].trim().split_whitespace().collect();
        for col in 0..20 {
            grid[row][col] = line[col].parse().unwrap();
        }
    }

    let mut max = 0;
    for row in 0..20 {
        for col in 0..20 {
            for direction in &[(0, 1), (1, 0), (1, -1), (1, 1)] {
                max = std::cmp::max(max, mul_4_adj(&grid, row, col, direction));
            }
        }
    }
    println!("max={}", max); // 70600674
}
// Calculate the product of four adjacent numbers in the same direction:
fn mul_4_adj(grid: &[[u8; 20]; 20], mut r: usize, mut c: usize, direction: &(i8, i8)) -> u32 {
    let mut f = 1;
    for _ in 0..4 {
        f *= grid[r][c] as u32;
        let (row, col) = (r as i8 + direction.0, c as i8 + direction.1);
        if row < 0 || row >= 20 || col < 0 || col >= 20 {
            return 0;
        }
        r = row as usize;
        c = col as usize;
    }
    f
}

Also you may use grid directly:

let grid = [ [ 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, ], ];

You don't need extra parenthesis and : i64 here:

let ret1: i64 = (lft as i64) + (rgt as i64);

This works:

let ret1 = lft as i64 + rgt as i64;

Use for _ in 0..4 instead of four find_elem(...) as the above examples.
You may use u32 instead of u64, since 255 * 255 * 255 * 255 = 4_228_250_625 = 0xfc05_fc01 for the product of four adjacent numbers.

I don't think you want break s in mul_4_adj, but rather return 0 - imagine a 3x3 block in the corner with very large values but surrounded by zeros on all sides. — Daniel Martin, Mar 5 '20 at 1:19
Is there any way to not refer to Vecs after I finish parsing without hard coding the size? — Daniel Martin, Mar 5 '20 at 1:22

Daniel Martin · Accepted Answer · 2020-03-06 01:37:51Z

I accepted the answer that gave me a bunch of good ideas; here's the final form I ended up with. I'm mostly happy with it, except for the use of the move keyword. I don't understand what that's doing and only added it when the compiler told me to. Specifically, I don't understand why it's needed with this code, but wasn't needed with some simple variants. Maybe I'll ask about that on stackoverflow.

Anyway:

fn parse_grid(gridstr: &str) -> Vec<Vec<u8>> {
    gridstr
        .trim()
        .split("\n")
        .map(|line| {
            line.trim()
                .split_whitespace()
                .map(|numstr| numstr.parse().expect("Expected a u8"))
                .collect()
        })
        .collect()
}

fn main() {
    let gridstr = r#"
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
"#;
    let gridholder = parse_grid(gridstr);
    let grid: Vec<&[u8]> = gridholder.iter().map(|x| &x[..]).collect();

    println!("{}", search_grid(&grid));
}

fn find_elem(grid: &[&[u8]], locx: isize, locy: isize) -> u64 {
    if locx >= 0 && (locx as usize) < grid.len() {
        if locy >= 0 && (locy as usize) < grid[locx as usize].len() {
            return u64::from(grid[locx as usize][locy as usize]);
        }
    }
    0
}

fn prod_4(grid: &[&[u8]], startx: usize, starty: usize, dirx: isize, diry: isize) -> u64 {
    let mut istartx = startx as isize;
    let mut istarty = starty as isize;
    let mut prod: u64 = 1;
    for _ in 0..4 {
        prod *= find_elem(grid, istartx, istarty);
        istartx += dirx;
        istarty += diry;
    }
    prod
}

fn search_grid(grid: &[&[u8]]) -> u64 {
    let directions = [(1, 0), (1, 1), (0, 1), (-1, 1)];
    directions
        .iter()
        .flat_map(move |dir| {
            (0..grid.len()).flat_map(move |startx| {
                (0..grid[startx].len())
                    .map(move |starty| prod_4(grid, startx, starty, dir.0, dir.1))
            })
        })
        .max()
        .unwrap_or(0)
}

Stack Exchange Network

current community

your communities

more stack exchange communities

Largest product in a grid: Project Euler 11

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged programming-challenge rust or ask your own question.

Hot Network Questions

Largest product in a grid: Project Euler 11

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged programming-challenge rust or ask your own question.

Related

Hot Network Questions