main.rs (1770B)
1 fn main() {
2 let input = std::fs::read_to_string("input.txt")
3 .unwrap()
4 .trim()
5 .split(',')
6 .map(|x| x.parse::<i32>().unwrap())
7 .collect::<Vec<i32>>();
8 // 341534
9 println!("Part 1: {}", part_1(&input));
10 // 93397632
11 println!("Part 2: {}", part_2(&input));
12 }
13
14 fn part_1(input: &Vec<i32>) -> i32 {
15 let pos_weight = {
16 let mut tmp = std::collections::HashMap::<i32, i32>::new();
17 for i in input {
18 tmp.insert(*i, **tmp.get(i).get_or_insert(&0) + 1);
19 }
20 tmp
21 };
22 let mut min_cost = None;
23 // for linear costs, sufficient to just check the already occupied positions
24 for align in pos_weight.keys() {
25 let mut cost = 0;
26 for (pos, weight) in pos_weight.iter() {
27 cost += (pos - align).abs() * weight;
28 }
29 min_cost = match min_cost {
30 None => Some(cost),
31 Some(min_cost) => Some(min_cost.min(cost)),
32 }
33 }
34 min_cost.unwrap()
35 }
36
37 fn part_2(input: &Vec<i32>) -> i32 {
38 let pos_weight = {
39 let mut tmp = std::collections::HashMap::<i32, i32>::new();
40 for i in input {
41 tmp.insert(*i, **tmp.get(i).get_or_insert(&0) + 1);
42 }
43 tmp
44 };
45 let mut min_cost = None;
46 let min_align = *input.iter().min().unwrap();
47 let max_align = *input.iter().max().unwrap();
48 for align in min_align..=max_align {
49 let mut cost = 0;
50 for (pos, weight) in pos_weight.iter() {
51 let dist = (pos - align).abs();
52 cost += dist * (dist + 1) / 2 * weight;
53 }
54 min_cost = match min_cost {
55 None => Some(cost),
56 Some(min_cost) => Some(min_cost.min(cost)),
57 }
58 }
59 min_cost.unwrap()
60 }