From 3ffc9de9efd3b3650eaf3ccc77e434fa000a9a08 Mon Sep 17 00:00:00 2001 From: Orfeas <38209077+0xfea5@users.noreply.github.com> Date: Thu, 7 Dec 2023 06:56:53 +0200 Subject: day5 --- day02/solution.zig | 6 +- day04/solution.zig | 6 +- day05/example.txt | 33 +++++++ day05/solution.zig | 276 +++++++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 309 insertions(+), 12 deletions(-) create mode 100644 day05/example.txt diff --git a/day02/solution.zig b/day02/solution.zig index 5e8d6f6..b40274d 100644 --- a/day02/solution.zig +++ b/day02/solution.zig @@ -45,10 +45,10 @@ pub fn parseBall(text: []const u8) Ball { const trimmed = mem.trim(u8, text, &std.ascii.whitespace); var splitBalls = mem.splitScalar(u8, trimmed, ' '); - const nballs = std.fmt.parseInt(u64, splitBalls.next() orelse unreachable, 10) catch unreachable; + const nballs = std.fmt.parseInt(u64, splitBalls.next().?, 10) catch unreachable; var color: Color = undefined; color = blk: { - const s = splitBalls.next() orelse unreachable; + const s = splitBalls.next().?; if (mem.eql(u8, s, "red")) { break :blk .red; @@ -152,7 +152,7 @@ pub fn main() !void { var splitGame = mem.splitScalar(u8, line, ':'); _ = splitGame.next(); - const game = try parseGame(splitGame.next() orelse unreachable); + const game = try parseGame(splitGame.next().?); try games.append(game); } diff --git a/day04/solution.zig b/day04/solution.zig index 081277a..6f67569 100644 --- a/day04/solution.zig +++ b/day04/solution.zig @@ -39,12 +39,12 @@ fn parseCard(text: []const u8) !Card { var prefix = mem.splitScalar(u8, text, ':'); _ = prefix.next(); // ignore 'Card ##' prefix - const postfix = prefix.next() orelse unreachable; + const postfix = prefix.next().?; var allNumbers = mem.splitScalar(u8, postfix, '|'); - var winningText = mem.splitScalar(u8, allNumbers.next() orelse unreachable, ' '); - var ownedText = mem.splitScalar(u8, allNumbers.next() orelse unreachable, ' '); + var winningText = mem.splitScalar(u8, allNumbers.next().?, ' '); + var ownedText = mem.splitScalar(u8, allNumbers.next().?, ' '); // split produces some empty strings that must be ignored later while (winningText.next()) |numText| { diff --git a/day05/example.txt b/day05/example.txt new file mode 100644 index 0000000..f756727 --- /dev/null +++ b/day05/example.txt @@ -0,0 +1,33 @@ +seeds: 79 14 55 13 + +seed-to-soil map: +50 98 2 +52 50 48 + +soil-to-fertilizer map: +0 15 37 +37 52 2 +39 0 15 + +fertilizer-to-water map: +49 53 8 +0 11 42 +42 0 7 +57 7 4 + +water-to-light map: +88 18 7 +18 25 70 + +light-to-temperature map: +45 77 23 +81 45 19 +68 64 13 + +temperature-to-humidity map: +0 69 1 +1 0 69 + +humidity-to-location map: +60 56 37 +56 93 4 diff --git a/day05/solution.zig b/day05/solution.zig index 059a120..c22af8b 100644 --- a/day05/solution.zig +++ b/day05/solution.zig @@ -9,15 +9,279 @@ const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace); var gpa = std.heap.GeneralPurposeAllocator(.{}){}; const allocator = gpa.allocator(); -pub fn part1() void { - // Part 1 goes here +// +// I represent the input in the form of: +// +// Input = [ +// Map [ +// Translation { +// src = Range { +// begin, +// len, +// }, +// dst = Range { +// begin, +// len, +// } +// } +// ... +// ] +// ... +// ] +// +// I filled unmapped areas with identity maps (1-1 translation src -> dest) +// to avoid edge cases. +// +// +const Range = struct { + begin: i64, + len: i64, +}; + +const Translation = struct { + src: Range, + dst: Range, +}; + +const Map = struct { + ranges: ArrayList(Translation), + + pub fn init() Map { + const ranges = ArrayList(Translation).init(allocator); + + return Map{ + .ranges = ranges, + }; + } + + pub fn deinit(self: *@This()) void { + self.ranges.deinit(); + } +}; + +fn parseSeeds(text: []const u8) ArrayList(i64) { + var result = ArrayList(i64).init(allocator); + var textNumbers = mem.splitScalar(u8, text, ' '); + + // Ignore header + _ = textNumbers.next(); + + while (textNumbers.next()) |textNum| { + const n = std.fmt.parseInt(i64, textNum, 10) catch unreachable; + result.append(n) catch unreachable; + } + + return result; +} + +fn parseTranslation(text: []const u8) Translation { + var splitNums = mem.splitScalar(u8, text, ' '); + const dst_begin = std.fmt.parseInt(i64, splitNums.next().?, 10) catch unreachable; + const src_begin = std.fmt.parseInt(i64, splitNums.next().?, 10) catch unreachable; + const len = std.fmt.parseInt(i64, splitNums.next().?, 10) catch unreachable; + + return Translation{ + .src = .{ + .begin = src_begin, + .len = len, + }, + .dst = .{ + .begin = dst_begin, + .len = len, + }, + }; +} + +fn translationLess(@"_": void, lhs: Translation, rhs: Translation) bool { + return rangeLess(@"_", lhs.src, rhs.src); +} + +fn parseMap(text: []const u8) Map { + var splitLines = mem.splitScalar(u8, text, '\n'); + var translations = ArrayList(Translation).init(allocator); + defer translations.deinit(); + + // Ignore header + _ = splitLines.next(); + + while (splitLines.next()) |line| { + translations.append(parseTranslation(line)) catch unreachable; + } + mem.sort(Translation, translations.items, {}, translationLess); + + var gapFilled = ArrayList(Translation).init(allocator); + const items = translations.items; + + // Fill gap from 0 up to the first segment + if (items[0].src.begin > 0) { + gapFilled.append(.{ .src = .{ + .begin = 0, + .len = items[0].src.begin, + }, .dst = .{ + .begin = 0, + .len = items[0].src.begin, + } }) catch unreachable; + } + + // Fill intermediate gaps + for (items[0 .. items.len - 1], 0..) |tr, i| { + const curr = tr.src; + const next = items[i + 1].src; + gapFilled.append(items[i]) catch unreachable; + if (rangeAdjacent(curr, next) == null) { + gapFilled.append(.{ .src = .{ + .begin = curr.begin + curr.len, + .len = next.begin - curr.begin - curr.len, + }, .dst = .{ + .begin = curr.begin + curr.len, + .len = next.begin - curr.begin - curr.len, + } }) catch unreachable; + } + } + + // Fill gap from the end of the last segment to +infinity + const len = items.len; + gapFilled.append(.{ .src = .{ + .begin = items[len - 1].src.begin, + .len = 4_000_000_000, + }, .dst = .{ + .begin = items[len - 1].src.begin, + .len = 4_000_000_000, + } }) catch unreachable; + + return Map{ + .ranges = gapFilled, + }; +} + +fn evalSeed(seed: i64, maps: []const Map) i64 { + var s = seed; + + for (maps) |map| { + for (map.ranges.items) |range| { + if (range.src.begin <= s and s < range.src.begin + range.src.len) { + s += range.dst.begin - range.src.begin; + break; + } + } + } + + return s; +} + +fn rangeLess(_: void, lhs: Range, rhs: Range) bool { + return lhs.begin < rhs.begin or (lhs.begin == rhs.begin and lhs.len > rhs.len); +} + +fn rangeMin(lhs: Range, rhs: Range) Range { + return if (rangeLess({}, lhs, rhs)) lhs else rhs; } -pub fn part2() void { - // Part 2 goes here +fn rangeMax(lhs: Range, rhs: Range) Range { + return if (rangeLess({}, lhs, rhs)) rhs else lhs; +} + +fn rangeOverlap(lhs: Range, rhs: Range) ?Range { + const min = rangeMin(lhs, rhs); + const max = rangeMax(lhs, rhs); + + if (min.begin + min.len <= max.begin) { + return null; + } + + return Range{ + .begin = max.begin, + .len = @min(min.begin + min.len - max.begin, max.len), + }; +} + +fn rangeAdjacent(lhs: Range, rhs: Range) ?Range { + const min = rangeMin(lhs, rhs); + const max = rangeMax(lhs, rhs); + + if (min.begin + min.len != max.begin) { + return null; + } + + return Range{ + .begin = max.begin, + .len = @min(min.begin + min.len - max.begin, max.len), + }; +} + +pub fn part1(seeds: []const i64, maps: []const Map) void { + var ans: i64 = std.math.maxInt(i64); + + for (seeds) |seed| { + const s = evalSeed(seed, maps); + ans = @min(ans, s); + } + + print("{d}\n", .{ans}); +} + +fn evalNextState(m: Map, ranges: ArrayList(Range)) ArrayList(Range) { + var result = ArrayList(Range).init(allocator); + + // Translate all seed range(s) + for (ranges.items) |r| { + + // For every translation + for (m.ranges.items) |t| { + const overlap = rangeOverlap(t.src, r) orelse continue; + + result.append(.{ + .begin = t.dst.begin + overlap.begin - t.src.begin, + .len = overlap.len, + }) catch unreachable; + } + } + + assert(result.items.len > 0); + mem.sort(Range, result.items, {}, rangeLess); + + return result; +} + +fn evalLowest(startRange: Range, maps: []const Map) i64 { + var ranges = ArrayList(Range).init(allocator); + defer ranges.deinit(); + + // Start with a single seed range + ranges.append(startRange) catch unreachable; + + // For every map + for (maps) |m| { + const nextRanges = evalNextState(m, ranges); + ranges.deinit(); + ranges = nextRanges; + } + + return ranges.items[0].begin; +} + +pub fn part2(seeds: []const i64, maps: []const Map) void { + var ans: i64 = std.math.maxInt(i64); + + for (0..seeds.len / 2) |i| { + const begin: i64 = @intCast(seeds[i * 2]); + const len: i64 = @intCast(seeds[i * 2 + 1]); + + ans = @min(ans, evalLowest(.{ .begin = begin, .len = len }, maps)); + } + print("{d}\n", .{ans}); } pub fn main() !void { - part1(); - part2(); + var splitLines = mem.splitSequence(u8, fin, "\n\n"); + const seedsText = splitLines.next().?; + const seeds = parseSeeds(seedsText); + + var maps = ArrayList(Map).init(allocator); + while (splitLines.next()) |mapText| { + maps.append(parseMap(mapText)) catch unreachable; + } + + part1(seeds.items, maps.items); + part2(seeds.items, maps.items); } -- cgit v1.2.3