YeungYeah 的乱写地

Advent of Code 2023: Day5

 Posts  

题目具体可以看 这里

简单概括描述就是： 给定一些整数输入 seeds，并且给出一些 mapping (list list (dst, src, length))，如果 seed 落在 [src, src + length] 这个区间里面，就 map 成 (dst + seed - src)。求经过多次 mapping 之后，seeds 当中的最小值。

暴力 with F#

看到题目很直观的一个想法就是对于输入的每个 seed 都扫一遍所有的 mapping，得到一个最终的 seed，并从中求最小值。part1 很轻松就过掉，但是到了 part2 的时候，每两个 seed 表示输入的是 [seed1, seed1 + seed2] 区间内的所有 seeds，加起来超过 198 亿个 seeds。

最开始直接用 F# 写了一个暴力法模拟，但是跑了一段时间后可能因为数量太多直接给我中断了。于是手动把输入分成了两半，然后跑两次，一次大概要跑 8 分钟，不过能跑到正确的答案。

既然这么耗时，第一时间想到的就是用多线程并行来跑。在 F# 当中，可以很简单地通过 async block + Async.Parallel 实现并行计算，看起来能跑满七八个核。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

seeds
|> Seq.map (fun (a, b) ->
	async {
		let allSeeds =
			[| for i in a .. (a + b - (int64 1)) do
				   yield i |]

		return maps |> Array.fold (fun seeds map -> seed2Map seeds map) allSeeds |> Seq.min

	})
|> Async.Parallel
|> Async.RunSynchronously
|> Array.min

在 F# 当中使用多线程跑，5 分钟多点就能跑完。

既然跑得慢，那么切换到一个跑得更快的语言，用 Rust 来写，应该能提升不少。

暴力 with Rust

先用 Rust 写了个逻辑一样的暴力模拟，基本上就是把 F# 写的逻辑搬了过来，4 分钟左右能跑完。这个速度比我在 F# 用多线程来跑还快！Rust 的性能果然名不虚传。

然后继续用多线程的方法又写了一版，每两个 seed 作为一组，开一个线程来逐个 seed 处理。然后一分钟左右就能跑完，确实快，Rust 实在是太强辣。

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

let mut handlers = vec![];
for (start, cnt) in seeds {
	let maps_clone = maps.clone();
	let handler = thread::spawn(move || {
		(start..start + cnt)
			.map(|seed| {
				maps_clone
					.iter()
					.fold(seed, |seed, map| seed_2_map(seed, &map))
			})
			.min()
			.unwrap()
	});
	handlers.push(handler);
}

handlers
	.into_iter()
	.map(|handler| handler.join().unwrap())
	.min()
	.unwrap()

真正的解法

之前暴力的解法是逐个 seed 做多次 mapping 得到结果再找最小值，但是这个数量太多，需要跑的次数太多。但实际也不需要每个 seed 做 mapping，完全可以根据区间来做 mapping.

对于一个 seeds 的区间 range，经过一轮 mapping 后，

  • 如果跟其中的一个 map 有交集，可以取这个交集出来做 mapping
  • 交集部分两个端点进行 mapping 可以得到新 range
  • 非交集部分取出来得到新 range，继续和其他的 map 进行处理
  • 如果都没有交集，那么直接进入下一轮 mapping

具体代码如下

 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

#[derive(Copy, Clone)]
struct Range {
    start: u64,
    end: u64,
}

impl Range {
    fn new(start: u64, end: u64) -> Range {
        Range { start, end }
    }

    fn is_empty(&self) -> bool {
        self.start >= self.end
    }

    fn intersect(&self, other: Range) -> Range {
        Range {
            start: self.start.max(other.start),
            end: self.end.min(other.end),
        }
    }

    fn difference(&self, other: Range) -> (Range, Range) {
        let left_diff = Range::new(self.start, self.end.min(other.start));
        let right_diff = Range::new(self.start.max(other.end), self.end);
        (left_diff, right_diff)
    }
}

let mut ranges = seeds;
for map in maps {
	let mut mapped_ranges = vec![];
	while let Some(range) = ranges.pop() {
		let mut has_intersect = false;
		for (target, source, len) in map.iter() {
			let mapped_range = Range {
				start: *source,
				end: *source + len,
			};

			let intersection = range.intersect(mapped_range);
			if intersection.is_empty() {
				continue;
			}

			has_intersect = true;
			mapped_ranges.push(Range {
				start: intersection.start - *source + *target,
				end: intersection.end - *source + *target,
			});

			let (left_diff, right_diff) = range.difference(mapped_range);
			if !left_diff.is_empty() {
				ranges.push(left_diff);
			}
			if !right_diff.is_empty() {
				ranges.push(right_diff);
			}

			break;
		}

		if !has_intersect {
			mapped_ranges.push(range);
		}
	}
	ranges = mapped_ranges;
}

ranges.iter().map(|range| range.start).min().unwrap()

切换到这个解法后，直接 0.05s 秒了！

一个小问题：对于这种需要三个嵌套循环的代码逻辑，如果转成使用函数式编程的思路，比如用 F# 来实现，该怎么办呢？具体请看下回分解。

相关文章：