Rust Implementation of Problem 67
View source code here on GitHub!
Includes
Problem Solution
- pub fn problems::p0067::p0067() -> utils::Answer
1/*
2Project Euler Problem 67
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
113
127 4
132 4 6
148 5 9 3
15
16That is, 3 + 7 + 4 + 9 = 23.
17
18Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file
19containing a triangle with one-hundred rows.
20
21NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem,
22as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty
23billion years to check them all. There is an efficient algorithm to solve it. ;o)
24*/
25use crate::include::triangles::reduce_triangle;
26use crate::include::utils::{get_data_file,Answer};
27
28
29pub fn p0067() -> Answer {
30 let mut rows: Vec<Vec<u8>> = vec![];
31 for line in get_data_file("p0067_triangle.txt").trim().lines() {
32 rows.push(line.split(' ').map(|x| x.parse::<u8>().unwrap()).collect::<Vec<u8>>());
33 }
34 return Answer::Int(reduce_triangle(rows).into());
35}