Advent of Code 2023

头一回听说这个玩意，看起来还挺有意思的，国际上挺火，也不是特别难，有空就写一点，顺便学习一下 Rust，以防入门第四次失败。

Day 1

Part 1

题意很简单，找到每一行第一个和最后一个数字，将其组成一个两位数，然后相加。样例也很人畜无害（很有 OI 的风格）：

plaintext 
1
2
3
4

1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet

比如第一行找出 1 和 2，就是 12，2、3 行同理，第 4 行则是两个 7，最后相加得到 12 + 38 + 15 + 77 = 142。

只是这样的话当然（看起来）很简单了，特别是当 Rust 提供了 str 的 find 和 rfind 之后。

对每行：

  • 分别记录每一行首末数字的位置，初始化为 0 和 len(str)+1，以及其对应的数字
  • 遍历 0-9 的每个数字，顺便更新上述四个变量
  • 最后将两个对应的数字拼起来，加进去

在上述第二步中，一开始筛选条件为“若本位数字下标大于最后一位下标，则更新”（即 number_last_match > last_index），然而当有且仅有第一位为数字时，不会更新。改为大于等于即可。这样例确实有股 OI 味儿，得学会自己出~

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

pub fn part_one(input: &str) -> Option<u32> {
    // separate input into lines
    let lines = input.lines();
    let mut sum = 0;
    let numbers = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"];
    for line in lines {
        let mut first_number = 0;
        let mut first_index: usize = line.len() + 1;
        let mut last_number = 0;
        let mut last_index: usize = 0;

        for i in 0..10 {
            if let Some(number_first_match) = line.find(numbers[i]) {
                if number_first_match < first_index {
                    first_number = i;
                    first_index = number_first_match;
                }
            }
            if let Some(number_last_match) = line.rfind(numbers[i]) {
                if number_last_match >= last_index { // If the only number is at [0], use this to record it
                    last_number = i;
                    last_index = number_last_match;
                }
            }
        }
        sum += first_number * 10 + last_number;
    }
    Some(sum as u32)
}

Part 2

其实就是在 P1 数字的基础上加上表示数字的单词。一听到要匹配多种字符串，啪的一下很快啊，拿出了正则表达式。只需要十个正则表达式，全部正着反着匹配一遍就行了……真的如此吗？

然而实际上，Rust 的 regex crate 使用的是自动机匹配，虽然比 PCRE 效率高，但它并不原生支持反向匹配；得把字符串和表达式都反过来，再匹配一遍，显然很不优雅。

突然想起，还有一个相比没那么丑陋、Part 1 用过的方案摆在眼前：匹配两次不就行了吗？

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

pub fn part_two(input: &str) -> Option<u32> {
        // separate input into lines
        let lines = input.lines();
        let mut sum = 0;
        let numbers = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"];
        let word_numbers = [
            "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        for line in lines {
            let mut first_number = 0;
            let mut first_index: usize = line.len() + 1;
            let mut last_number = 0;
            let mut last_index: usize = 0;

            for i in 0..10 {
                if let Some(word_first_match) = line.find(word_numbers[i]) {
                    if word_first_match < first_index {
                        first_number = i;
                        first_index = word_first_match;
                    }
                }
                if let Some(word_last_match) = line.rfind(word_numbers[i]) {
                    if word_last_match >= last_index {
                        last_number = i;
                        last_index = word_last_match;
                    }
                }
                if let Some(number_first_match) = line.find(numbers[i]) {
                    if number_first_match < first_index {
                        first_number = i;
                        first_index = number_first_match;
                    }
                }
                if let Some(number_last_match) = line.rfind(numbers[i]) {
                    if number_last_match >= last_index {
                        last_number = i;
                        last_index = number_last_match;
                    }
                }
            }
            sum += first_number * 10 + last_number;
        }
        Some(sum as u32)
}

Day 2

Part 1

每行代表一次 game，每次 game 进行多次随机抽取，共有 12 个红色、13 个绿色、14 个蓝色，问有哪几次 game 中，所有抽取都符合实际情况，也就是每次抽取的每种颜色都不超过实际数量。

plaintext 
1
2
3
4
5

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green

split，全都可以 split，第一次分行，第二次用 : 把 “Game X: " 截掉，第三次用 ; 分隔抽数，第四次用 , 分隔颜色，第五次用 `` 分隔数量和颜色。match 一下即可。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

pub fn part_one(input: &str) -> Option<u32> {
    let mut id_sum: u32 = 0;
    'game: for (index, game) in input.lines().enumerate() {
        // split "Game X: yyyyyyyyy"
        let content = game.split(": ").collect::<Vec<&str>>()[1];
        // split "X blue, Y red; XX green, YY yellow"
        let gotchas = content.split("; ").collect::<Vec<&str>>();
        let (mut red, mut green, mut blue) = (0, 0, 0);
        // Per gotcha: maximum 12 red, 13 green, 14 blue
        for gotcha in gotchas {
            let colors = gotcha.split(", ").collect::<Vec<&str>>();
            for color in colors {
                // color: "X blue/green/red"
                let color = color.split(" ").collect::<Vec<&str>>();
                let count = color[0].parse::<u32>().unwrap();
                match color[1] {
                    "blue" => blue = count,
                    "green" => green = count,
                    "red" => red = count,
                    _ => panic!("Unknown color: {}", color[1]),
                }
            }
            if red > 12 || green > 13 || blue > 14 {
                // this game is invalid, skip to next game
                continue 'game;
            }
        }
        id_sum += (index + 1) as u32;
    }
    Some(id_sum)
}

Part 2

Part 2 求出对每次 game，在能满足抽出数量的情况下，三种颜色各自的数量最小值。将这三个值相乘，再将每次 game 的乘积相加得到结果。

其实也一样，初始化一个最小值，然后对每一抽更新一下最小值。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

pub fn part_two(input: &str) -> Option<u32> {
    let mut id_sum: u32 = 0;
    for game in input.lines() {
        // split "Game X: yyyyyyyyy"
        let content = game.split(": ").collect::<Vec<&str>>()[1];
        // split "X blue, Y red; XX green, YY yellow"
        let gotchas = content.split("; ").collect::<Vec<&str>>();
        let (mut red, mut green, mut blue) = (0, 0, 0);
        // Get the maximum of each color
        for gotcha in gotchas {
            let colors = gotcha.split(", ").collect::<Vec<&str>>();
            for color in colors {
                // color: "X blue/green/red"
                let color = color.split(" ").collect::<Vec<&str>>();
                let count = color[0].parse::<u32>().unwrap();
                match color[1] {
                    "blue" => blue = cmp::max(blue, count),
                    "green" => green = cmp::max(green, count),
                    "red" => red = cmp::max(red, count),
                    _ => panic!("Unknown color: {}", color[1]),
                }
            }
        }
        let color_pow = red * green * blue;
        id_sum += color_pow;
    }
    Some(id_sum)
}

Day 3

Part 1

给定一个字符矩阵，找出其中周围有符号（非数字、非 . ）的数字，并将其相加。

也蛮简单的，就是一个要注意“周围”指的是八个方向，一个是如果在某行的最后仍然在记录数字，则将其截断。

第一个好理解，样例已经告诉我们了：

plaintext 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

这里 467 也算是周围有符号的数字。至于第二个问题，比如把它改成这样：

plaintext 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

467..114..
...*......
..35..633.
......#...
617*......
.....+.588
11592.....
......755.
...$.*....
.664.598..

由于代码的逻辑是遇到一个数字就记下来、遇到符号就停止，所以在 588 后不会停止，变成 58811592。不幸的是，并没有发现输入数据中有这种问题（苦笑）。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

pub fn part_one(input: &str) -> Option<u32> {
    // convert lines into a char matrix
    let lines = input.lines();
    let mut sum = 0;
    let mut matrix: Vec<Vec<char>> = Vec::new();
    for line in lines {
        matrix.push(line.chars().collect());
    }

    let mut curr = 0; // current number
    let mut is_part_number = false; // current number adjacent to a symbol
                                    // iterate through the matrix
    for (x, line) in matrix.iter().enumerate() {
        for (y, ch) in line.iter().enumerate() {
            if *ch >= '0' && *ch <= '9' {
                // ch is a number
                curr = curr * 10 + (*ch as u32 - '0' as u32);
                if !is_part_number {
                    // check char in 8 directions
                    if x > 0 && is_symbol(matrix[x - 1][y]) {
                        is_part_number = true;
                    } else if y > 0 && is_symbol(matrix[x][y - 1]) {
                        is_part_number = true;
                    } else if x < matrix.len() - 1 && is_symbol(matrix[x + 1][y]) {
                        is_part_number = true;
                    } else if y < matrix[x].len() - 1 && is_symbol(matrix[x][y + 1]) {
                        is_part_number = true;
                    } else if x > 0 && y > 0 && is_symbol(matrix[x - 1][y - 1]) {
                        is_part_number = true;
                    } else if x > 0 && y < matrix[x].len() - 1 && is_symbol(matrix[x - 1][y + 1]) {
                        is_part_number = true;
                    } else if x < matrix.len() - 1 && y > 0 && is_symbol(matrix[x + 1][y - 1]) {
                        is_part_number = true;
                    } else if x < matrix.len() - 1
                        && y < matrix[x].len() - 1
                        && is_symbol(matrix[x + 1][y + 1])
                    {
                        is_part_number = true;
                    }
                }
            } else {
                // ch is a letter
                if curr != 0 {
                    if is_part_number {
                        sum += curr;
                        println!("Add {}", curr)
                    }
                    curr = 0;
                    is_part_number = false;
                }
            }
        }
        // at the end of each line (including last), add the number
        if curr != 0 {
            if is_part_number {
                sum += curr;
                println!("Add {}", curr)
            }
            curr = 0;
            is_part_number = false;
        }
    }
    Some(sum)
}

fn is_symbol(char: char) -> bool {
    (char < '0' || char > '9') && char != '.'
}

Part 2

找出所有旁边有两串数字的星号，定义其值为这两个数字的乘积，求所有星号的值的和。

想出了两种思路。

第一种是开一个二维数组，为每串数字记录其编号，然后再扫一遍，对每个星号，统计周围 8 格中不同编号的个数。仍然是这个样例：

plaintext 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

那么第一行的编号数组就为 [1,1,1,0,0,2,2,2,0,0]（从 1 开始，无内容算 0）。但缺陷是数字的值需要再开个二维数组记录。

第二种是只扫星号，然后对每个星号，统计周围 8 格中数字的个数。数字只能横放在一行上，这给我们提供了巨大的方便，上中下三行可以分别处理。比如上面样例中第二行的星号，上一行三个位置数字情况为有、无、无，同一行为无、无，下一行为有、有、无，那么得出周围有 2 个数字，上面一个，下面一个。在确定周围有两个数字之后，即可再根据有数字的位置进行搜索，得到两个数字的值。这种方法可能重复对一个数字求值，但时空复杂度都比第一种低。

下面是第二种思路的做法。

rust 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

pub fn part_two(input: &str) -> Option<u32> {
    // convert lines into a char matrix
    let lines = input.lines();
    let mut sum = 0;
    let mut matrix: Vec<Vec<char>> = Vec::new();
    for line in lines {
        matrix.push(line.chars().collect());
    }

    for (x, line) in matrix.iter().enumerate() {
        for (y, ch) in line.iter().enumerate() {
            if *ch == '*' {
                // find numbers nearby
                let (
                    mut up_left,
                    mut up,
                    mut up_right,
                    mut left,
                    mut right,
                    mut down_left,
                    mut down,
                    mut down_right,
                ) = (false, false, false, false, false, false, false, false);
                let mut pow = 1;
                if x > 0 {
                    if y > 0 {
                        if is_digit(matrix[x - 1][y - 1]) {
                            up_left = true;
                        }
                    }
                    if is_digit(matrix[x - 1][y]) {
                        up = true;
                    }
                    if y < matrix[x].len() - 1 {
                        if is_digit(matrix[x - 1][y + 1]) {
                            up_right = true;
                        }
                    }
                }
                if y>0 && is_digit(matrix[x][y - 1]) {
                    left = true;
                }
                if y < matrix[x].len() - 1 && is_digit(matrix[x][y + 1]) {
                    right = true;
                }
                if x < matrix.len() - 1 {
                    if y > 0 {
                        if is_digit(matrix[x + 1][y - 1]) {
                            down_left = true;
                        }
                    }
                    if is_digit(matrix[x + 1][y]) {
                        down = true;
                    }
                    if y < matrix[x].len() - 1 {
                        if is_digit(matrix[x + 1][y + 1]) {
                            down_right = true;
                        }
                    }
                }
                // get number count
                let mut count = 0;
                match (up_left, up, up_right) {
                    (false, false, true) | (true, false, false) | (false, true, false) => {
                        count += 1
                    }
                    (true, true, false) | (false, true, true) => {
                        count += 1;
                        up = false; // to prevent calculating value twice
                    }
                    (true, false, true) => count += 2,
                    (true, true, true) => {
                        count += 1;
                        up_left = false; // as above
                        up_right = false;
                    }
                    (false, false, false) => {}
                }
                if left {
                    count += 1;
                }
                if right {
                    count += 1;
                }
                match (down_left, down, down_right) {
                    (false, false, true) | (true, false, false) | (false, true, false) => {
                        count += 1
                    }
                    (true, true, false) | (false, true, true) => {
                        count += 1;
                        down = false;
                    }
                    (true, false, true) => count += 2,
                    (true, true, true) => {
                        count += 1;
                        down_left = false;
                        down_right = false;
                    }
                    (false, false, false) => {}
                }
                println!("({}, {}) has {} numbers", x, y, count);
                if count != 2 {
                    // not a "gear"
                    continue;
                }
                if up_left {
                    pow *= get_value(&matrix[x - 1], y - 1);
                }
                if up {
                    pow *= get_value(&matrix[x - 1], y);
                }
                if up_right {
                    pow *= get_value(&matrix[x - 1], y + 1);
                }
                if left {
                    pow *= get_value(&matrix[x], y - 1);
                }
                if right {
                    pow *= get_value(&matrix[x], y + 1);
                }
                if down_left {
                    pow *= get_value(&matrix[x + 1], y - 1);
                }
                if down {
                    pow *= get_value(&matrix[x + 1], y);
                }
                if down_right {
                    pow *= get_value(&matrix[x + 1], y + 1);
                }
                sum += pow;
                println!("Adding {} at ({}, {})", pow, x, y);
            }
        }
    }
    Some(sum as u32)
}

fn is_digit(char: char) -> bool {
    char >= '0' && char <= '9'
}

// Since the value stays only on one line, we can just use one line.
fn get_value(matrix: &Vec<char>, y: usize) -> i32 {
    let mut start_y = y;
    let mut val = 0;
    while start_y > 0 && is_digit(matrix[start_y - 1]) {
        start_y -= 1;
    }
    while start_y < matrix.len() && is_digit(matrix[start_y]) {
        val = val * 10 + (matrix[start_y] as i32 - '0' as i32);
        start_y += 1;
    }
    val
}

写完才发现这八个位置各一个变量实在不优雅，但能用，应该可以改为 [[bool;3];3]。实际操作中，如果上面一行有多于两位连着的数字（即属于同一串数字），那么只能留一位为 true，否则会重复计算。

令人欣慰的是，只需要在 get_value 里借用一下 matrix 即可不转移所有权，从而避免了一个 Rust 新手与编译器旷日持久的战斗。

Day 4

Part 1

非常简单，长话短说就是刮刮乐，买了几张刮刮乐，要求出每张刮刮乐的中奖情况。

这里要特别感谢 itertools，由于输入数据中不一定只用一个空格分隔，能把多个空格当一个分隔符的 split_whitespace() 真的很好用。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

pub fn part_one(input: &str) -> Option<u32> {
    let lines = input.lines();
    let mut sum: u32 = 0;
    for line in lines{
        let mut win = 0;
        // process strings
        let content = line.split(": ").collect_vec()[1]; // cut "Card X: "
        let result = content.split(" | ").collect_vec();
        let winning_numbers = result[0];
        let own_numbers = result[1];
        let winning_set: HashSet<u32> = winning_numbers
            .split_whitespace()
            .map(|x| x.parse::<u32>().unwrap())
            .collect();
        let own_numbers: Vec<u32> = own_numbers
            .split_whitespace()
            .map(|x| x.parse::<u32>().unwrap())
            .collect();
        for number in own_numbers.iter() {
            if winning_set.contains(number) {
                win += 1;
            }
        }
        if win > 0 {
            sum += 2_u32.pow(win - 1);
        }
    }
    Some(sum)
}

Part 2

需要注意的是每一个编号的刮刮乐初始都有一张。

嘿嘿，用 Copilot 写函数式的代码真快乐。太华丽了。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

pub fn part_two(input: &str) -> Option<u32> {
    let lines = input.lines().collect_vec();
    let mut sum = 0; // cards scratched in total
    let mut cards_count = vec![1; lines.len()]; // every card has 1 copy
    let contents: Vec<&str> = lines
        .iter()
        .map(|x| x.split(": ").collect_vec()[1])
        .collect_vec();
    let results = contents
        .iter()
        .map(|x| x.split(" | ").collect_vec())
        .collect_vec();
    let winning_sets: Vec<HashSet<u32>> = results
        .iter()
        .map(|x| x[0])
        .map(|x| {
            x.split_whitespace()
                .map(|y| y.parse::<u32>().unwrap()) // Numbers that gets point for each card
                .collect()
        })
        .collect_vec();
    let own_numbers: Vec<Vec<u32>> = results
        .iter()
        .map(|x| x[1])
        .map(|x| {
            x.split_whitespace()
                .map(|y| y.parse::<u32>().unwrap()) // Numbers that gets point for each card
                .collect()
        })
        .collect_vec();
    for index in 0..cards_count.len() {
        println!("Has {} of card {}", cards_count[index], index);
        if cards_count[index] == 0 {
            break;
        }
        sum += cards_count[index];
        let winning_set = &winning_sets[index];
        let own_numbers = &own_numbers[index];
        let mut win = 0;
        print!("Intersect numbers: ");
        for number in own_numbers.iter() {
            if winning_set.contains(number) {
                win += 1;
                print!("{} ", number);
            }
        }
        println!("Win {} cards", win,);
        for i in 0..win {
            cards_count[index + 1 + i] += cards_count[index];
            println!(
                "Add {} copies of card {}",
                cards_count[index],
                index + 2 + i
            )
        }
    }
    Some(sum)
}

Day 5

Part 1

简单来说，就是给定映射关系，对每个数做 7 次映射，然后求出离得最近的两个结果。每个映射关系都是一个区间，这个条件让我残存的一丢丢算法竞赛思维立即想到了线段树。它确实很适合区间操作，但考虑到 AoC 并没有时空复杂度限制，写个暴力也能过。更重要的是，我不会。

倒是可以用二分，这个确实会，给区间排个序就行，但一旦有了写暴力的心思，就懒得钻研算法了……

但是，这道题真的是溢出狂魔啊……数据全都是 u32 的情况下，如果不改变数据格式，经常出现加溢出。一般有两种情况。

rust 
1
2
3
4
5
6
7

// old
soil = mapping.dst_start + *seed - mapping.src_start;
// new
soil = mapping
    .dst_start
    .wrapping_add(*seed)
    .wrapping_sub(mapping.src_start);

第一种是像上面这段代码出现的，dst_start 和 *seed 相加后容易溢出，将减法提前也一样会溢出，从而 panic。既然结果的 soil 肯定不会溢出，那么直接放任它溢出就可以了。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// old
if soil >= mapping.src_start
    && soil < mapping.src_start + mapping.length
// new
if soil >= mapping.src_start
    && soil
        < mapping
            .src_start
            .checked_add(mapping.length)
            .unwrap_or(u32::MAX)

区间开头不溢出，长度也不溢出，诶，加起来它就溢出了。反正被映射的数字都属于 u32 集合，遇到超出的时候，直接用 u32::MAX 代替就行了。或者直接用 saturating_add。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#[derive(Debug, PartialEq, Clone, Copy, Eq, PartialOrd, Ord)]
struct Mapping {
    dst_start: u32,
    src_start: u32,
    length: u32,
}

pub fn part_one(input: &str) -> Option<u32> {
    let items = input.split("\n\n").collect::<Vec<_>>();
    let seeds = items[0]
        .strip_prefix("seeds: ")
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse::<u32>().unwrap())
        .collect::<Vec<_>>();
    let process_mapping = |x: &str| -> Vec<Mapping> {
        x.lines()
            .skip(1)
            .map(|line| {
                let mut parts = line.split_whitespace();
                let dst_start = parts.next().unwrap().parse::<u32>().unwrap();
                let src_start = parts.next().unwrap().parse::<u32>().unwrap();
                let length = parts.next().unwrap().parse::<u32>().unwrap();
                Mapping {
                    dst_start,
                    src_start,
                    length,
                }
            })
            .collect::<Vec<_>>()
    };
    let seed_to_soil = process_mapping(items[1]);
    let soil_to_fertilizer = process_mapping(items[2]);
    let fertilizer_to_water = process_mapping(items[3]);
    let water_to_light = process_mapping(items[4]);
    let light_to_temperature = process_mapping(items[5]);
    let temperature_to_humidity = process_mapping(items[6]);
    let humidity_to_location = process_mapping(items[7]);

    let mut locations: Vec<u32> = vec![0; seeds.len()];
    for (index, seed) in seeds.iter().enumerate() {
        let mut soil = 0;
        let mut mapped = false;
        for mapping in seed_to_soil.iter() {
            if *seed >= mapping.src_start
                && *seed
                    < mapping
                        .src_start
                        .checked_add(mapping.length)
                        .unwrap_or(u32::MAX)
            {
                soil = mapping
                    .dst_start
                    .wrapping_add(*seed)
                    .wrapping_sub(mapping.src_start);
                mapped = true;
                break;
            }
        }
        // if not mapped, use the src number
        if !mapped {
            soil = *seed;
        }

        let mut fertilizer = 0;
        mapped = false;
        for mapping in soil_to_fertilizer.iter() {
            if soil >= mapping.src_start
                && soil
                    < mapping
                        .src_start
                        .checked_add(mapping.length)
                        .unwrap_or(u32::MAX)
            {
                fertilizer = mapping
                    .dst_start
                    .wrapping_add(soil)
                    .wrapping_sub(mapping.src_start);
                mapped = true;
                break;
            }
        }
        if !mapped {
            fertilizer = soil;
        }

        // highly repetitive part omitted

        locations[index] = location;
        println!("Seed {}, soil {}, fertilizer {}, water {}, light {}, temperature {}, humidity {}, location {}", seed, soil, fertilizer, water, light, temperature, humidity, location);
    }
    // sort locations
    locations.sort();
    Some(locations[0])
}

Part 2

题面意思改动很小，只是把第一行穷举的种子改为了数个区间的格式。样例的数据量不大，但实际输入动辄 20 亿。诚然，AoC 没有时空复杂度限制，但应该没人好意思写一个 20 亿次外层循环的暴力吧？虽然暴力跑比想正解快多了

由于第一问没有搞那些花活，第二问就不强上高级算法了。将计就计，直接以区间作为单位进行映射。其核心思想就是根据映射范围切割区间，分别进行映射。怎么有种编译原理实验的感觉呢 至于切割和映射的过程，个人建议对着样例画张图，能够极大地便于调试。在此奉上我画的图：

D5P2 样例解析
D5P2 样例解析

有了上一问的经验，此处并没有直接存储映射前后的差值，即使这样代码更简洁，因为 i32 相比 u32 天生就少了一半儿的能够表示的绝对值。相反，跟上一问一样使用 wrapping_add 和 wrapping_sub 放任溢出。

为了程序的简洁性，还使用了更多 lambda 表达式，读起来可能困难一点，但行数确实少了很多。

rust 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

pub fn part_two(input: &str) -> Option<u32> {
    let items = input.split("\n\n").collect::<Vec<_>>();
    let seeds = items[0]
        .strip_prefix("seeds: ")
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse::<u32>().unwrap())
        .collect::<Vec<_>>()
        .chunks(2)
        .map(|x| (x[0], x[0] + x[1]))
        .collect::<Vec<_>>();
    let process_mapping = |x: &str| -> Vec<Mapping> {
        let mut result = x
            .lines()
            .skip(1)
            .map(|line| {
                let mut parts = line.split_whitespace();
                let dst_start = parts.next().unwrap().parse::<u32>().unwrap();
                let src_start = parts.next().unwrap().parse::<u32>().unwrap();
                let length = parts.next().unwrap().parse::<u32>().unwrap();
                Mapping {
                    dst_start,
                    src_start,
                    length,
                }
            })
            .collect::<Vec<_>>();
        result.sort_by(|a, b| a.src_start.cmp(&b.src_start));
        result
    };
    let seed_to_soil = process_mapping(items[1]);
    let soil_to_fertilizer = process_mapping(items[2]);
    let fertilizer_to_water = process_mapping(items[3]);
    let water_to_light = process_mapping(items[4]);
    let light_to_temperature = process_mapping(items[5]);
    let temperature_to_humidity = process_mapping(items[6]);
    let humidity_to_location = process_mapping(items[7]);

    let mut min_position = u32::MAX;

    let transform_ranges =
        |original_ranges: Vec<(u32, u32)>, mappings: &Vec<Mapping>| -> Vec<(u32, u32)> {
            let mut result = vec![];
            'range: for range in original_ranges.iter() {
                let mut range_start = range.0; // "cut" the range from start
                let range_end = range.1; // include start, exclude end
                for mapping in mappings.iter() {
                    let mapping_start = mapping.src_start;
                    let mapping_end = mapping
                        .src_start
                        .checked_add(mapping.length)
                        .unwrap_or(u32::MAX);
                    if range_start < mapping_start {
                        // remove the part before the mapping, use original range start
                        if range_end < mapping_start {
                            // current range has ended
                            result.push((range_start, range_end));
                            break;
                        } else {
                            // current range has some overlap with current mapping
                            result.push((range_start, mapping_start));
                            range_start = mapping_start;
                        }
                    }
                    if range_start >= mapping_end {
                        continue;
                    }
                    // now it at least has some overlap
                    let new_start = cmp::max(range_start, mapping_start)
                        .wrapping_sub(mapping.src_start)
                        .wrapping_add(mapping.dst_start);
                    let new_end = cmp::min(range_end, mapping_end)
                        .wrapping_sub(mapping.src_start)
                        .wrapping_add(mapping.dst_start);
                    result.push((new_start, new_end));
                    if range_end <= mapping_end {
                        // current range has ended
                        continue 'range;
                    } else {
                        // current range has some left
                        range_start = mapping_end;
                    }
                }
                // if still has some left, add it
                if range_start < range_end {
                    result.push((range_start, range_end));
                }
            }
            result
        };
    for seed in seeds.iter() {
        let seed_ranges = vec![(seed.0, seed.1)];
        let soil_ranges = transform_ranges(seed_ranges, &seed_to_soil);
        let fertilizer_ranges = transform_ranges(soil_ranges, &soil_to_fertilizer);
        let water_ranges = transform_ranges(fertilizer_ranges, &fertilizer_to_water);
        let light_ranges = transform_ranges(water_ranges, &water_to_light);
        let temperature_ranges = transform_ranges(light_ranges, &light_to_temperature);
        let humidity_ranges = transform_ranges(temperature_ranges, &temperature_to_humidity);
        let location_ranges = transform_ranges(humidity_ranges, &humidity_to_location);
        for location_range in location_ranges.iter() {
            if location_range.0 < min_position {
                min_position = location_range.0;
            }
        }
    }

    Some(min_position)
}

Day 6

Part 1

船需要先原地蓄力，然后匀速运动，蓄力越久运动越快，时间取值均为离散值。求在给定时间下，有哪几种能够运动超过给定距离的可能，返回其数量。

初中数学题。设蓄力时间为 $x\ ms$，时间限制为 $t\ ms$，则匀速运动的时长为 $x-t\ ms$，匀速运动的距离为 $x(x-t)\ mm$。若给定距离为 $d$，则整道题就变成了求 $x(t-x) \ge d$ 的整数解，即 $\frac{t+\sqrt{t^2-4d}}{2}$ 和 $\frac{t-\sqrt{t^2-4d}}{2}$。

特别需要关注的是，题意为“超过”而非“不低于”，所以当两个根为整数的时候，这两个数不能算。我也不知道我是怎么写出如此抽象的代码的。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

pub fn part_one(input: &str) -> Option<u32> {
    let lines = input.lines().collect_vec();
    let times: Vec<u32> = lines[0]
        .split_whitespace()
        .filter_map(|x| x.parse().ok())
        .collect();
    let distances: Vec<u32> = lines[1]
        .split_whitespace()
        .filter_map(|x| x.parse().ok())
        .collect();
    let mut prod = 1;

    for (t, d) in times.iter().zip(distances.iter()) {
        let t = *t as f64;
        let d = *d as f64;
        let delta = ((t * t) - (4.0 * d)).sqrt();
        let x1 = (t + delta) / 2.0;
        let x2 = (t - delta) / 2.0;
        let count = if x1 == x1.floor() {
            x1 as u32 - 1
        } else {
            x1.floor() as u32
        } - if x2 == x2.ceil() {
            x2 as u32 + 1
        } else {
            x2.ceil() as u32
        } + 1;
        prod *= count;
    }
    Some(prod)
}

Part 2

从未见过 Part 2 比 Part 1 更简单的，但现在有了。之前需要解好几个方程，现在解一个就可以了。f64 直接秒杀。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

pub fn part_two(input: &str) -> Option<u32> {
    let lines = input.lines().collect_vec();
    let pattern = Regex::new(r"[^0-9]+").unwrap();
    let time = pattern.replace_all(lines[0], "").parse::<f64>().unwrap();
    let distance = pattern.replace_all(lines[1], "").parse::<f64>().unwrap();
    let delta = ((time * time) - (4.0 * distance)).sqrt();
    let x1 = (time + delta) / 2.0;
    let x2 = (time - delta) / 2.0;
    let count = if x1 == x1.floor() {
        x1 as u32 - 1
    } else {
        x1.floor() as u32
    } - if x2 == x2.ceil() {
        x2 as u32 + 1
    } else {
        x2.ceil() as u32
    } + 1;
    Some(count)
}

Day 7

Part 1

题面的意思很容易看出来，就是将所有的手牌按指定的排序规则进行排序。

这下是来学 Rust 排序的了。之前很多人说 Rust 的 duck-typing（即 trait 机制）很麻烦，我不以为意，直到我为了排序一个结构体写了四个 impl，以及 N 个 derive。

为牌的各种排列组合分别写判断条件不用想就知道很麻烦，所以直接为不同的排列赋上不同的权重，将其加和得到该手牌的总权重，排序起来会很方便。

所幸实际输入也很简单，过了样例便没有被卡住。

rust 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

#[derive(Debug)]
struct Hand {
    hand: Vec<Card>,
    bid: u32,
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Clone)]
enum Card {
    A = 14,
    K = 13,
    Q = 12,
    J = 11,
    T = 10,
    Nine = 9,
    Eight = 8,
    Seven = 7,
    Six = 6,
    Five = 5,
    Four = 4,
    Three = 3,
    Two = 2,
}

impl Ord for Hand {
    fn cmp(&self, other: &Self) -> Ordering {
        // how many of each card
        let self_dict = self.hand.iter().fold(HashMap::new(), |mut acc, card| {
            *acc.entry(card).or_insert(0) += 1;
            acc
        });
        let other_dict = other.hand.iter().fold(HashMap::new(), |mut acc, card| {
            *acc.entry(card).or_insert(0) += 1;
            acc
        });
        // Weight: 5 -> 30, 4 -> 20, 3 -> 10, 2 -> 5, 1 -> 1
        let self_weight = self_dict
            .iter()
            .map(|(_, count)| match count {
                5 => 30,
                4 => 20,
                3 => 10,
                2 => 5,
                1 => 1,
                _ => panic!("Invalid card count"),
            })
            .sum::<u32>();
        let other_weight = other_dict
            .iter()
            .map(|(_, count)| match count {
                5 => 30,
                4 => 20,
                3 => 10,
                2 => 5,
                1 => 1,
                _ => panic!("Invalid card count"),
            })
            .sum::<u32>();
        if self_weight > other_weight {
            return Ordering::Greater;
        } else if self_weight < other_weight {
            return Ordering::Less;
        } else {
            // compare `Card`s in descending order
            for (self_card, other_card) in self.hand.iter().zip(other.hand.iter()) {
                if self_card > other_card {
                    return Ordering::Greater;
                } else if self_card < other_card {
                    return Ordering::Less;
                }
            }
        }
        Ordering::Equal
    }
}

impl PartialOrd for Hand {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Hand {
    fn eq(&self, other: &Self) -> bool {
        self.bid == other.bid
    }
}

impl Eq for Hand {}

pub fn part_one(input: &str) -> Option<u32> {
    let mut hands: Vec<Hand> = input
        .lines()
        .map(|line| {
            let mut parts = line.split_whitespace();
            let hand = parts
                .next()
                .unwrap()
                .chars()
                .map(|c| match c {
                    'A' => Card::A,
                    'K' => Card::K,
                    'Q' => Card::Q,
                    'J' => Card::J,
                    'T' => Card::T,
                    '9' => Card::Nine,
                    '8' => Card::Eight,
                    '7' => Card::Seven,
                    '6' => Card::Six,
                    '5' => Card::Five,
                    '4' => Card::Four,
                    '3' => Card::Three,
                    '2' => Card::Two,
                    _ => panic!("Invalid card"),
                })
                .collect::<Vec<_>>();
            let bid = parts.next().unwrap().parse().unwrap();
            Hand { hand, bid }
        })
        .collect();
    hands.sort();

    let mut winnings: u32 = 0;
    for i in 1..=hands.len() {
        winnings += hands[i - 1].bid * i as u32;
    }
    Some(winnings)
}

Part 2

大悲，排序规则改了，卡的价值也改了。上面这一坨东西都要重写一遍了，唯独程序逻辑本身不用改，乐。

易证明结论，在讨论牌型时，将 J 全部当作除 J 外数量最多的牌即可。这一点体现在 merge_j 中。其他地方跟 Part 1 基本没有区别。

弃了，过了样例没过正经输入，先晾在这儿吧。 当我一筹莫展之时，我在一篇帖子中看到有人提到 JJJJJ 的特例。的确，在之前错误代码 merge_j 的逻辑中，如果只有 J 没有其他卡，则这个牌组中一张卡都没有。输出也可以验证 JJJJJ 位列最后一位。

rust 
1
2
3
4

    dict.remove(&Card2::J);
    if let Some(max_card) = max_card {
        *dict.entry(max_card).or_insert(0) += j_count;
    }

此时应该在 else 分支中插入五张 J。不得不说 Copilot 比我想得更远，将 max_card 定义为了 Option<&&Card2>，从而包含了不存在其他卡的情况…

rust 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Clone)]
enum Card2 {
    A = 14,
    K = 13,
    Q = 12,
    J = 1,
    T = 10,
    Nine = 9,
    Eight = 8,
    Seven = 7,
    Six = 6,
    Five = 5,
    Four = 4,
    Three = 3,
    Two = 2,
}

#[derive(Debug)]
struct Hand2 {
    hand: Vec<Card2>,
    bid: u32,
}

impl PartialOrd for Hand2 {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Hand2 {
    fn eq(&self, other: &Self) -> bool {
        self.bid == other.bid
    }
}

impl Eq for Hand2 {}

fn merge_j(dict: &mut HashMap<&Card2, i32>) {
    // get the number of j and card with largest count
    let mut j_count = 0;
    let mut max_count = 0;
    let mut max_card = None;
    let dict_clone = dict.clone();
    for (card, count) in dict_clone.iter() {
        if card == &&Card2::J {
            j_count = *count;
        } else if *count > max_count {
            max_count = *count;
            max_card = Some(card);
        }
    }
    dict.remove(&Card2::J);
    if let Some(max_card) = max_card {
        *dict.entry(max_card).or_insert(0) += j_count;
    } else {
        dict.insert(&Card2::J, j_count);
    }
}

impl Ord for Hand2 {
    fn cmp(&self, other: &Self) -> Ordering {
        let mut self_dict = self.hand.iter().fold(HashMap::new(), |mut acc, card| {
            *acc.entry(card).or_insert(0) += 1;
            acc
        });
        let mut other_dict = other.hand.iter().fold(HashMap::new(), |mut acc, card| {
            *acc.entry(card).or_insert(0) += 1;
            acc
        });
        merge_j(&mut self_dict);
        merge_j(&mut other_dict);
        let self_weight = self_dict
            .iter()
            .map(|(_, count)| match count {
                5 => 30,
                4 => 20,
                3 => 10,
                2 => 5,
                1 => 1,
                _ => panic!("Invalid card count"),
            })
            .sum::<u32>();
        let other_weight = other_dict
            .iter()
            .map(|(_, count)| match count {
                5 => 30,
                4 => 20,
                3 => 10,
                2 => 5,
                1 => 1,
                _ => panic!("Invalid card count"),
            })
            .sum::<u32>();
        if self_weight > other_weight {
            return Ordering::Greater;
        } else if self_weight < other_weight {
            return Ordering::Less;
        } else {
            // compare `Card`s in descending order
            for (self_card, other_card) in self.hand.iter().zip(other.hand.iter()) {
                if self_card > other_card {
                    return Ordering::Greater;
                } else if self_card < other_card {
                    return Ordering::Less;
                }
            }
        }
        Ordering::Equal
    }
}

pub fn part_two(input: &str) -> Option<u32> {
    let mut hands: Vec<Hand2> = input
        .lines()
        .map(|line| {
            let mut parts = line.split_whitespace();
            let hand = parts
                .next()
                .unwrap()
                .chars()
                .map(|c| match c {
                    'A' => Card2::A,
                    'K' => Card2::K,
                    'Q' => Card2::Q,
                    'J' => Card2::J,
                    'T' => Card2::T,
                    '9' => Card2::Nine,
                    '8' => Card2::Eight,
                    '7' => Card2::Seven,
                    '6' => Card2::Six,
                    '5' => Card2::Five,
                    '4' => Card2::Four,
                    '3' => Card2::Three,
                    '2' => Card2::Two,
                    _ => panic!("Invalid card"),
                })
                .collect::<Vec<_>>();
            let bid = parts.next().unwrap().parse().unwrap();
            Hand2 { hand, bid }
        })
        .collect();
    hands.sort();

    let mut winnings: u32 = 0;
    for i in 1..=hands.len() {
        winnings += hands[i - 1].bid * i as u32;
        println!("#{}: {:?}", i, hands[i - 1]);
    }
    Some(winnings)
}

Day 8

Part 1

迷你模拟题，给定一个可以重复走的方向序列和一张有向图，求从 AAA 到 ZZZ 所需的步数。甚至不需要自己找最短路径。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

pub fn part_one(input: &str) -> Option<u32> {
    let mut steps: u32 = 0;
    let mut curr_pos = "AAA";
    let lines = input.lines().collect::<Vec<_>>();
    let seq = lines[0];
    let mut direction = HashMap::<&str, (&str, &str)>::new();
    for line in lines[2..].iter() {
        // AAA = (BBB,CCC)
        let mut line = line.split(" = ");
        let key = line.next().unwrap();
        let mut line = line.next().unwrap().split(", ");
        let left = line.next().unwrap();
        let right = line.next().unwrap();
        direction.insert(key, (&left[1..], &right[0..3]));
    }
    while curr_pos != "ZZZ" {
        let index: usize = steps as usize % seq.len();
        curr_pos = match seq.chars().nth(index).unwrap() {
            'R' => direction.get(curr_pos).unwrap().1,
            'L' => direction.get(curr_pos).unwrap().0,
            _ => curr_pos,
        };
        steps += 1;
    }
    Some(steps)
}

Part 2

我曾经以为 P2 就是大号的 P1，用一样的思路解决就行，直到程序跑了 45 分钟都没出结果，我才意识到这个 P2 可能有点儿太大了。

// TODO

Day 9

这道题我觉得我思路挺怪的，虽然没什么问题，也能过测试，但就是不对。观察下面的样例：

plaintext 
1
2
3
4

1   3   6  10  15  21  28
  2   3   4   5   6   7
    1   1   1   1   1
      0   0   0   0

题目要求得出数列的下一个数。相邻的数减上几轮全都会变为 0，大胆猜测原数列为一个多项式函数。于是想到直接将原方程求出来即可。样例中的差分法可以很方便地求出次数，然后用一些第三方库（如 polyfit_rs）求出各个系数，代入求出 $f(len(\text{nums}))$即可。

如果这个思路真的可行，那么第二问就很容易了：得出数列的前一个数，直接代入求出 $f(-1)$ 就行了。

可是不对，为什么呢？

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

fn diff(nums: &Vec<i32>) -> u32 {
    let mut degree: u32 = 0;
    if nums.iter().all(|&x| x == nums[0]) {
        // special case
        return 0;
    }
    let mut diff = nums.clone();
    loop {
        // 0 3 6 9 12 15
        // -> 3 3 3 3 3
        // -> 0 0 0 0
        // then, times = 1; this is y=ax+b
        diff = diff
            .iter()
            .tuple_windows()
            .map(|(a, b)| b - a)
            .collect_vec();
        degree += 1;
        // if all diff is same, return times
        if diff.iter().all(|&x| x == diff[0]) {
            return degree;
        }
    }
}

pub fn part_one(input: &str) -> Option<i64> {
    let lines = input.lines().collect::<Vec<_>>();
    let mut sum = 0;
    for line in lines {
        let nums = line
            .split_whitespace()
            .map(|n| n.parse::<i32>().unwrap())
            .collect_vec();
        let degree = diff(&nums);
        let x_values = (0..nums.len()).map(|x| x as f64).collect_vec();
        let y_values = nums.iter().map(|&x| x as f64).collect_vec();
        let coefficients = polyfit_rs::polyfit(&x_values, &y_values, degree as usize).unwrap();
        let mut next = 0.0;
        // next = f(len(nums))
        for i in 0..degree as usize + 1 {
            next += coefficients[i] * (nums.len() as f64).powi(i as i32);
        }
        println!("{}", next.round() as i64);
        sum += next.round() as i64;
    }
    Some(sum)
}

Day 10

Part 1

给出的一张图描述了管道的连接情况，其中有个 S 点在管道的环路中，求出从某个点出发沿主（含 S 的）环路最远的距离。基本就是相当于要我们把环路找出来。

样例不得不使用 ASCII 字符代替 Unicode 制表符，毕竟很多语言对 Unicode 字符串的支持都挺……一般的。但我们看样例的时候可以进行一点儿替换：F -> ┌、7->┐、J->┘、L->└。

在我最初的实现中，直接使用一个 DFS，从 S 点周围的管道出发，寻找能连上的管道。注意：

  • 检查周围节点能否连上时，不仅要检查其管道是否指向本节点，而且还要检查本节点的管道是否指向它；
  • 由于上面的原因，不要直接从 S 开始 DFS，因为 S 点没有管道，自然连不上其他节点。

上面这个方法并没有修改地图本身（主要是 S 点）。但在第二部分中，有一个完全闭合的管道环路做起来会更舒服，所以我更新了第一部分的实现，找到 S 点后，依据四周的管道连接情况，将 S 修改为真正的管道。

rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

static LEFT_CONNECT: [char; 3] = ['-', 'L', 'F'];
static RIGHT_CONNECT: [char; 3] = ['-', 'J', '7'];
static TOP_CONNECT: [char; 3] = ['|', 'F', '7'];
static BOTTOM_CONNECT: [char; 3] = ['|', 'J', 'L'];

fn dfs(map: &Vec<Vec<char>>, map_dist: &mut Vec<Vec<Option<u32>>>, x: usize, y: usize) {
    let curr = map[x as usize][y as usize];
    let curr_dist = map_dist[x as usize][y as usize];
    if curr_dist.is_none() {
        return;
    }

    if x > 0 && TOP_CONNECT.contains(&map[x - 1][y]) && BOTTOM_CONNECT.contains(&curr) {
        let new_dist = curr_dist.unwrap() + 1;
        if map_dist[x - 1][y].is_none() || map_dist[x - 1][y].unwrap() > new_dist {
            map_dist[x - 1][y] = Some(new_dist);
            dfs(map, map_dist, x - 1, y);
        }
    }
    if x < map.len() - 1 && BOTTOM_CONNECT.contains(&map[x + 1][y]) && TOP_CONNECT.contains(&curr) {
        let new_dist = curr_dist.unwrap() + 1;
        if map_dist[x + 1][y].is_none() || map_dist[x + 1][y].unwrap() > new_dist {
            map_dist[x + 1][y] = Some(new_dist);
            dfs(map, map_dist, x + 1, y);
        }
    }
    if y > 0 && LEFT_CONNECT.contains(&map[x][y - 1]) && RIGHT_CONNECT.contains(&curr) {
        let new_dist = curr_dist.unwrap() + 1;
        if map_dist[x][y - 1].is_none() || map_dist[x][y - 1].unwrap() > new_dist {
            map_dist[x][y - 1] = Some(new_dist);
            dfs(map, map_dist, x, y - 1);
        }
    }
    if y < map[x].len() - 1
        && RIGHT_CONNECT.contains(&map[x][y + 1])
        && LEFT_CONNECT.contains(&curr)
    {
        let new_dist = curr_dist.unwrap() + 1;
        if map_dist[x][y + 1].is_none() || map_dist[x][y + 1].unwrap() > new_dist {
            map_dist[x][y + 1] = Some(new_dist);
            dfs(map, map_dist, x, y + 1);
        }
    }
}

pub fn part_one(input: &str) -> Option<u32> {
    let mut max_dist = 0;
    // array of array of chars
    let mut map = input
        .lines()
        .map(|line| line.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let mut map_dist = vec![vec![None; map[0].len()]; map.len()];
    for x in 0..map.len() {
        for y in 0..map[x].len() {
            if map[x][y] != 'S' {
                continue;
            }
            let (mut up, mut down, mut left, mut right) = (false, false, false, false);
            if x > 0 && TOP_CONNECT.contains(&map[x - 1][y]) {
                up = true;
            }
            if x < map.len() - 1 && BOTTOM_CONNECT.contains(&map[x + 1][y]) {
                down = true;
            }
            if y > 0 && LEFT_CONNECT.contains(&map[x][y - 1]) {
                left = true;
            }
            if y < map[x].len() - 1 && RIGHT_CONNECT.contains(&map[x][y + 1]) {
                right = true;
            }
            map_dist[x][y] = Some(0);
            match (up, down, left, right) {
                (true, true, false, false) => map[x][y] = '|',
                (false, false, true, true) => map[x][y] = '-',
                (true, false, true, false) => map[x][y] = 'J',
                (false, true, false, true) => map[x][y] = 'F',
                (true, false, false, true) => map[x][y] = 'L',
                (false, true, true, false) => map[x][y] = '7',
                _ => (),
            }
            dfs(&map, &mut map_dist, x, y)
        }
    }
    for row in map_dist {
        for col in row {
            if let Some(dist) = col {
                max_dist = max_dist.max(dist);
            }
        }
    }
    Some(max_dist)
}

Part 2

我们在第一部分找出了 S 点连接的主管道，第二部分则要求我们求出主管道包含的面积。由于第一问写下的 DFS 函数已经记录了主管道上所有点到 S 的距离，所以只要跑一遍，主管道范围的边界就确定了。

下一步就是数有哪些字符在主管道范围内了。本身的想法是按行遍历，完全忽略横向边界，维护一个 bool 变量判定是否在边界内，穿越一次边界就将其反转；又想了想，在一个字符内除了 | 跨越一整个边界外，那些弯弯折折的管道都只跨越上半/下半边界。CHANGE_<UP/DOWN>_HALF 就是记录这些字符的数组。当且仅当当前字符不属于主管道，且字符的上下半都在边界内时，计数器加一。

很抽象是吧，或许看到下面的图你会明白点。

plaintext 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

.┌----┐┌┐┌┐┌┐┌-┐....
.|┌--┐||||||||┌┘....
.||.┌┘||||||||└┐....
┌┘└┐└┐└┘└┘||└┘.└-┐..
└--┘.└┐...└┘S┐┌-┐└┐.
....┌-┘..┌┐┌┘|└┐└┐└┐
....└┐.┌┐||└┐|.└┐└┐|
.....|┌┘└┘|┌┘|┌┐|.└┘
....┌┘└-┐.||.||||...
....└---┘.└┘.└┘└┘...
rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

static CHANGE_UP_HALF: [char; 3] = ['|', 'J', 'L'];
static CHANGE_DOWN_HALF: [char; 3] = ['|', 'F', '7'];

pub fn part_two(input: &str) -> Option<u32> {
    // array of array of chars
    let mut map = input
        .lines()
        .map(|line| line.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let mut map_dist = vec![vec![None; map[0].len()]; map.len()];
    for x in 0..map.len() {
        for y in 0..map[x].len() {
            if map[x][y] != 'S' {
                continue;
            }
            let (mut up, mut down, mut left, mut right) = (false, false, false, false);
            if x > 0 && TOP_CONNECT.contains(&map[x - 1][y]) {
                up = true;
            }
            if x < map.len() - 1 && BOTTOM_CONNECT.contains(&map[x + 1][y]) {
                down = true;
            }
            if y > 0 && LEFT_CONNECT.contains(&map[x][y - 1]) {
                left = true;
            }
            if y < map[x].len() - 1 && RIGHT_CONNECT.contains(&map[x][y + 1]) {
                right = true;
            }
            map_dist[x][y] = Some(0);
            match (up, down, left, right) {
                (true, true, false, false) => map[x][y] = '|',
                (false, false, true, true) => map[x][y] = '-',
                (true, false, true, false) => map[x][y] = 'J',
                (false, true, false, true) => map[x][y] = 'F',
                (true, false, false, true) => map[x][y] = 'L',
                (false, true, true, false) => map[x][y] = '7',
                _ => (),
            }
            dfs(&map, &mut map_dist, x, y)
        }
    }

    let mut count = 0;
    for x in 0..map.len() {
        let (mut up_half, mut down_half) = (false, false);
        for y in 0..map[x].len() {
            if map_dist[x][y].is_some() && CHANGE_UP_HALF.contains(&map[x][y]) {
                up_half = !up_half;
            }
            if map_dist[x][y].is_some() && CHANGE_DOWN_HALF.contains(&map[x][y]) {
                down_half = !down_half;
            }
            if up_half && down_half && map_dist[x][y].is_none() {
                count += 1;
            }
        }
    }
    Some(count)
}