Advent of Code 2023: Day5

The specific problem can be seen here

A simple summary description is: Given some integer inputs as seeds, and some mappings (list list (dst, src, length)), if a seed falls in the range [src, src + length], it is mapped to (dst + seed - src). The question is to find the minimum value among the seeds after several mappings.

Brute Force with F#

A very intuitive idea when seeing the problem is to scan all mappings for each input seed, get a final seed, and find the minimum value from it. Part1 is easily passed, but when it comes to part2, each pair of seeds represents all seeds in the range [seed1, seed1 + seed2], adding up to more than 19.8 billion seeds.

At first, I wrote a brute force simulation in F#, but it was interrupted after running for a while, possibly because there were too many seeds. So I manually split the input in half, ran it twice, each time took about 8 minutes, but it could get to the correct answer.

Since it is so time-consuming, the first thing that comes to mind is to use multi-threading for parallel computation. In F#, it can be easily implemented with async block + Async.Parallel, which seems to be able to run on seven or eight cores.

 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

Using multi-threading in F#, it can be finished in just over 5 minutes.

Since it's slow, switching to a faster language, like Rust, should improve a lot.

Brute Force with Rust

First, I wrote a brute force simulation in Rust with the same logic, basically moving the logic written in F# over, and it could be finished in about 4 minutes. This speed is even faster than when I used multi-threading in F#! The performance of Rust is indeed well-deserved.

Then I wrote another version using multi-threading, with every two seeds as a group, and a thread was opened to handle each seed. Then it could be finished in about one minute, indeed fast, Rust is just too strong.

 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()

The Real Solution

The previous brute force method was to do multiple mappings for each seed to get the result and then find the minimum value, but the quantity was too large, and the number of times needed to run was too many. But in fact, you don't need to do mapping for each seed, you can do mapping according to the range.

For a range of seeds, after one round of mapping,

• If it intersects with one of the maps, you can take this intersection out for mapping
• The two endpoints of the intersection part can be mapped to get a new range
• The non-intersection part is taken out to get a new range, and continue to deal with other maps
• If there is no intersection, then directly enter the next round of mapping

The specific code is as follows

 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()

After switching to this solution, it only takes 0.05s!

A small question: For this kind of code logic that needs three nested loops, if it is converted to use functional programming thinking, such as using F# to implement, what should we do? Please see the next episode for the specific solution.