main.rs (3191B)
1 fn main() {
2 let input = std::fs::read_to_string("input.txt")
3 .unwrap()
4 .trim()
5 .split('\n')
6 .map(|x| {
7 x.chars()
8 .map(|y| y.to_digit(10).unwrap())
9 .collect::<Vec<_>>()
10 })
11 .collect::<Vec<_>>();
12 // 560
13 println!("Part 1: {}", part_1(&input));
14 // 959136
15 println!("Part 2: {}", part_2(&input));
16 }
17
18 fn part_1(input: &Vec<Vec<u32>>) -> u32 {
19 let mut risk_level = 0;
20 for x in 0..input.len() {
21 for y in 0..input[0].len() {
22 let mut is_low_point = true;
23 is_low_point &= x == 0 || input[x][y] < input[x - 1][y];
24 is_low_point &= x == input.len() - 1 || input[x][y] < input[x + 1][y];
25 is_low_point &= y == 0 || input[x][y] < input[x][y - 1];
26 is_low_point &= y == input[0].len() - 1 || input[x][y] < input[x][y + 1];
27 if is_low_point {
28 risk_level += input[x][y] + 1;
29 }
30 }
31 }
32 risk_level
33 }
34
35 fn part_2(input: &Vec<Vec<u32>>) -> usize {
36 let mut basin_sizes = std::collections::BinaryHeap::<usize>::new();
37 for x in 0..input.len() {
38 for y in 0..input[0].len() {
39 let mut is_low_point = true;
40 is_low_point &= x == 0 || input[x][y] < input[x - 1][y];
41 is_low_point &= x == input.len() - 1 || input[x][y] < input[x + 1][y];
42 is_low_point &= y == 0 || input[x][y] < input[x][y - 1];
43 is_low_point &= y == input[0].len() - 1 || input[x][y] < input[x][y + 1];
44 if is_low_point {
45 // find the basin size
46 let mut basin = std::collections::HashSet::<(usize, usize)>::new();
47 let mut queue = vec![(x, y)];
48 while let Some((x, y)) = queue.pop() {
49 basin.insert((x, y));
50 if x > 0
51 && input[x - 1][y] != 9
52 && input[x - 1][y] >= input[x][y]
53 && !basin.contains(&(x - 1, y))
54 {
55 queue.push((x - 1, y));
56 }
57 if x < input.len() - 1
58 && input[x + 1][y] != 9
59 && input[x + 1][y] >= input[x][y]
60 && !basin.contains(&(x + 1, y))
61 {
62 queue.push((x + 1, y));
63 }
64 if y > 0
65 && input[x][y - 1] != 9
66 && input[x][y - 1] >= input[x][y]
67 && !basin.contains(&(x, y - 1))
68 {
69 queue.push((x, y - 1));
70 }
71 if y < input[0].len() - 1
72 && input[x][y + 1] != 9
73 && input[x][y + 1] >= input[x][y]
74 && !basin.contains(&(x, y + 1))
75 {
76 queue.push((x, y + 1));
77 }
78 }
79 basin_sizes.push(basin.len());
80 }
81 }
82 }
83 basin_sizes.pop().unwrap() * basin_sizes.pop().unwrap() * basin_sizes.pop().unwrap()
84 }