文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >问答首页 >网格中最大的产品: Euler 11项目

问网格中最大的产品: Euler 11项目
EN

Code Review用户
提问于 2020-03-04 15:22:10
回答 2查看 203关注 0票数 0

欧拉11 -网格中最大的产品项目：

在下面的20 × 20网格中，沿着对角线的四个数字被标记为红色。08 02 22 97 38 15 00 40 00 75 04 05 07 78 12 50 77 91 49 49 99 40 17 81 18 57 60 87 17 40 43 69 48 04 56 00 00 81 49 31 73 55 14 14 29 71 40 67 53 03 03 30 13 36 65 52 95 95 04 60 11 68 56 01 32 56 71 02 36 22 31 16 71 51 63 89 41 36 54 22 40 28 66 33 80 24 47 32 60 99 03 44 75 53 78 36 84 84 35 17 17 50 5032 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 70 67 67 26 20 68 02 12 20 63 94 39 08 40 66 49 94 21 24 55 05 66 73 99 26 17 78 76 78 96 83 14 34 34 89 63 72 36 23 09 75 45 35 14 00 61 33 97 34 34 33 33 33 17 53 28 22 22 75 31 34 03 04 62 14 14 14 09 56 16 14 09 92 16 42 96 35 35 55 55 58 58 24 24 24 85 5786 56 00 48 35 71 89 07 44 44 37 44 60 21 58 51 54 17 58 19 19 80 81 68 94 47 28 28 73 13 52 17 77 04 89 55 40 04 08 83 97 99 16 07 97 32 16 26 26 79 27 98 66 88 68 87 57 20 72 03 46 67 46 55 32 32 93 93 04 42 16 73 25 39 11 24 72 24 18 08 46 32 32 62 76 36 36 41 72 30 36 34 62 99 67 67 74 04 36 16 16 1620 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 57 05 54 01 70 54 71 51 54 69 16 92 33 48 61 43 01 89 19 67 48这些数字的乘积为26 × 63 × 78 × 14 = 1788696。在20×20网格中，四个相邻数在同一方向(向上、向下、左、右或对角)的最大乘积是什么？

我做#ProjectEuler100100挑战是为了学习锈病。我仍然有很多地方，借用检查器打我的脸，但这是预料之中的；一般来说，我只是做编译器说的，它是快乐的。我想我正在慢慢地了解那里。

有一件事是一个持续的意外痛苦，那就是整型输入。我不清楚你实际上是如何处理整数类型的，而我现在所做的是如此丑陋，以至于它肯定是错误的。

就在我做自己的功能的时候，我开始怀疑我已经偏离了轨道。一定有更好的办法。

做这件事的首选方法是什么？有没有比as更好的方法来转换基本整数类型？

下面是我的欧拉项目问题11解决方案的核心：( 全解在我的GitHub回购中)

代码语言：javascript
复制
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
}

此外，如果有人能告诉我如何正确地传递一个二维数组(我可以将外层更改为&[]，但无法想出如何改变内部层而不是Vec)，那就太好了。

programming-challenge
rust
EN

回答 2

Code Review用户

回答已采纳

发布于 2020-03-04 22:01:32

代码评审：

  1. 您不需要使用u64，因为输入数据都是u8，所以像下面的代码一样使用Vec<u8>，并在一行中解析所有输入数据：
代码语言：javascript
复制
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
}
  1. 将分块与CHUNK_SIZE of 20一起使用，而不是grid: &[Vec<u64>]使用grid: &[&[u8]]：
代码语言：javascript
复制
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
}
  1. 另外，您可以在Rust中使用二维数组而不是Vec<Vec<u64>>：
代码语言：javascript
复制
let mut grid = [[0_u8; 20]; 20];

然后简单地查找并打印最大值：

代码语言：javascript
复制
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
}
  1. 此外，您也可以直接使用网格：
代码语言：javascript
复制
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, ], ];
  1. 这里不需要额外的括号和: i64：
代码语言：javascript
复制
let ret1: i64 = (lft as i64) + (rgt as i64);

这样做是可行的：

代码语言：javascript
复制
let ret1 = lft as i64 + rgt as i64;
  1. 使用for _ in 0..4而不是四个find_elem(...)作为上面的示例。
  2. 您可以使用u32而不是u64，因为255 * 255 * 255 * 255 = 4_228_250_625 = 0xfc05_fc01用于四个相邻数字的乘积。
票数 1
EN

Code Review用户

发布于 2020-03-06 01:37:51

除了使用move关键字之外，我对此非常满意。我不明白这是怎么回事，只在编译器告诉我的时候才加进去。也许我会在堆叠溢出的时候问这个问题。

总之：

代码语言：javascript
复制
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)
}
票数 0
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://codereview.stackexchange.com/questions/238374

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档