main.rs (2579B)
1 fn main() {
2 let input = std::fs::read_to_string("input.txt")
3 .unwrap()
4 .trim()
5 .split('\n')
6 .map(|s| {
7 s.chars()
8 .map(|c| c.to_digit(10).unwrap())
9 .collect::<Vec<u32>>()
10 })
11 .collect::<Vec<Vec<u32>>>();
12 // 652
13 println!("Part 1: {}", part_1(&input));
14 // 2938
15 println!("Part 2: {}", part_1(&enlarge_map(&input)));
16 }
17
18 fn enlarge_map(risk: &Vec<Vec<u32>>) -> Vec<Vec<u32>> {
19 fn increase_risk(r: u32, inc: u32) -> u32 {
20 let mut r = r + inc;
21 while r > 9 {
22 r -= 9;
23 }
24 r
25 }
26
27 let x_max = risk.len();
28 let y_max = risk[0].len();
29 let mut risk = risk.clone();
30 for x in 0..x_max {
31 for inc in 1..5 {
32 for y in 0..y_max {
33 let new_risk = increase_risk(risk[x][y], inc);
34 risk[x].push(new_risk);
35 }
36 }
37 }
38 for inc in 1..5 {
39 for x in 0..x_max {
40 risk.push(risk[x].iter().map(|&r| increase_risk(r, inc)).collect());
41 }
42 }
43
44 risk
45 }
46
47 fn part_1(risk: &Vec<Vec<u32>>) -> u32 {
48 let x_max = risk.len();
49 let y_max = risk[0].len();
50
51 let mut cost = vec![vec![None; y_max]; x_max];
52 cost[0][0] = Some(0);
53 loop {
54 let mut updated = false;
55 for x in 0..x_max {
56 for y in 0..y_max {
57 for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)] {
58 if ((x as i32) + dx >= 0 && (x as i32) + dx < x_max as i32)
59 && ((y as i32) + dy >= 0 && (y as i32) + dy < y_max as i32)
60 {
61 match (
62 cost[(x as i32 + dx) as usize][(y as i32 + dy) as usize],
63 cost[x][y],
64 ) {
65 (Some(sub_cost), Some(old_cost)) => {
66 if sub_cost + risk[x][y] < old_cost {
67 cost[x][y] = Some(sub_cost + risk[x][y]);
68 updated = true;
69 }
70 }
71 (Some(sub_cost), None) => {
72 cost[x][y] = Some(sub_cost + risk[x][y]);
73 updated = true;
74 }
75 _ => (),
76 }
77 }
78 }
79 }
80 }
81 if !updated {
82 return cost[x_max - 1][y_max - 1].unwrap();
83 }
84 }
85 }