Rust Implementation of Problem 18

View source code here on GitHub!

Includes

Problem Solution

pub fn problems::p0018::p0018() -> utils::Answer
 1/*
 2Project Euler Problem 18
 3
 4Thinking from the bottom up got the answer
 5
 6Problem:
 7
 8By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top
 9to bottom is 23.
10
11.. code-block::
12
13     3
14    7 4
15   2 4 6
16  8 5 9 3
17
18That is, 3 + 7 + 4 + 9 = 23.
19
20Find the maximum total from top to bottom of the triangle below:
21
22.. code-block::
23
24                              75
25                            95  64
26                          17  47  82
27                        18  35  87  10
28                      20  04  82  47  65
29                    19  01  23  75  03  34
30                  88  02  77  73  07  63  67
31                99  65  04  28  06  16  70  92
32              41  41  26  56  83  40  80  70  33
33            41  48  72  33  47  32  37  16  94  29
34          53  71  44  65  25  43  91  52  97  51  14
35        70  11  33  28  77  73  17  78  39  68  17  57
36      91  71  52  38  17  14  91  43  58  50  27  29  48
37    63  66  04  68  89  53  67  30  73  16  69  87  40  31
38  04  62  98  27  23  09  70  98  73  93  38  53  60  04  23
39
40NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67,
41is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a
42clever method! ;o)
43*/
44use crate::include::triangles::reduce_triangle;
45use crate::include::utils::Answer;
46
47
48pub fn p0018() -> Answer {
49    let rows = vec![
50        vec![75, ],
51        vec![95, 64],
52        vec![17, 47, 82],
53        vec![18, 35, 87, 10],
54        vec![20,  4, 82, 47, 65],
55        vec![19,  1, 23, 75,  3, 34],
56        vec![88,  2, 77, 73,  7, 63, 67],
57        vec![99, 65,  4, 28,  6, 16, 70, 92],
58        vec![41, 41, 26, 56, 83, 40, 80, 70, 33],
59        vec![41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
60        vec![53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
61        vec![70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
62        vec![91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
63        vec![63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
64        vec![ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23]
65    ];
66    return Answer::Int(reduce_triangle(rows).into());
67}

Tags: combinatorics, path-finding