ejri.dev
1const std = @import("std");
2const Allocator = std.mem.Allocator;
3const ArrayList = std.ArrayList;
4
5const Range = struct {
6 low: usize,
7 high: usize,
8
9 pub fn compareByLow(_: void, a: Range, b: Range) bool {
10 return a.low < b.low;
11 }
12};
13
14pub fn run(allocator: Allocator, input: []u8) !struct { u64, u64 } {
15 var sections = std.mem.tokenizeSequence(u8, input, "\n\n");
16
17 var answer1: u64 = 0;
18 var answer2: u64 = 0;
19
20 var ranges = std.mem.tokenizeScalar(u8, sections.next().?, '\n');
21 var items = std.mem.tokenizeScalar(u8, sections.next().?, '\n');
22
23 var valid_ranges = try ArrayList(Range).initCapacity(allocator, 100);
24 defer valid_ranges.deinit(allocator);
25
26 var max: u64 = 0;
27
28 while (ranges.next()) |line| {
29 var range = std.mem.tokenizeScalar(u8, line, '-');
30
31 const low = try std.fmt.parseInt(u64, range.next().?, 10);
32 const high = try std.fmt.parseInt(u64, range.next().?, 10);
33
34 if (high > max) {
35 max = high;
36 }
37
38 try valid_ranges.append(allocator, .{ .low = low, .high = high });
39 }
40
41 while (items.next()) |line| {
42 const id = try std.fmt.parseInt(usize, line, 10);
43
44 for (valid_ranges.items) |range| {
45 if (range.low <= id and id <= range.high) {
46 answer1 += 1;
47 break;
48 }
49 }
50 }
51
52 std.mem.sort(Range, valid_ranges.items, {}, Range.compareByLow);
53
54 var merged_ranges = try ArrayList(Range).initCapacity(allocator, valid_ranges.items.len);
55 defer merged_ranges.deinit(allocator);
56 for (valid_ranges.items[0 .. valid_ranges.items.len - 1], 0..) |item, i| {
57 var other = &valid_ranges.items[i + 1];
58 if (item.high < other.low) {
59 try merged_ranges.append(allocator, item);
60 continue;
61 }
62
63 other.low = item.low;
64 if (other.high < item.high) {
65 other.high = item.high;
66 }
67 }
68 try merged_ranges.append(allocator, valid_ranges.getLast());
69
70 for (merged_ranges.items) |item| {
71 answer2 += item.high - item.low + 1;
72 }
73
74 return .{ answer1, answer2 };
75}