solve day8

2 files changed, 213 insertions, 0 deletions

diff --git a/src/day08.zig b/src/day08.zig
new file mode 100644
index 0000000..53421b3
--- /dev/null
+++ b/src/day08.zig
@@ -0,0 +1,211 @@
+const std = @import("std");
+const print = std.debug.print;
+
+pub fn solve(part: []u8, reader: *std.Io.Reader, allocator: std.mem.Allocator) !void {
+    if (std.mem.eql(u8, part, "1")) {
+        try part1(reader, allocator);
+    } else {
+        try part2(reader, allocator);
+    }
+}
+
+const Coord = struct {x: i64, y: i64, z: i64};
+const Pair = struct {c1: Coord, c2: Coord, d: usize};
+
+fn cmp(_: void, a: Pair, b: Pair) std.math.Order { 
+    return std.math.order(a.d, b.d);
+}
+
+const Context = struct {
+
+    pub fn hash(_: Context, coord: Coord) u64 {
+        return @intCast(coord.x * coord.y * coord.z);
+    }
+    
+    pub fn eql(_: Context, coord1: Coord, coord2: Coord) bool {
+        return coord1.x == coord2.x and coord1.y == coord2.y and coord1.z == coord2.z;
+    }
+};
+
+
+fn part1(reader: *std.Io.Reader, allocator: std.mem.Allocator) !void {
+
+    var queue = std.PriorityQueue(Pair, void, cmp).init(allocator, {});
+    defer queue.deinit();
+
+    try queue.ensureTotalCapacity(1000000);
+
+    var list = try std.ArrayList(Coord).initCapacity(allocator, 100);
+    defer list.deinit(allocator);
+
+    var map = std.HashMap(Coord, usize, Context, 80).init(allocator);
+    defer map.deinit();
+
+    var sets = try std.ArrayList(std.ArrayList(Coord)).initCapacity(allocator, 100);
+    defer sets.deinit(allocator);
+
+    while (reader.takeDelimiter('\n')) |line| {
+        if (line == null) break;
+
+
+        var split = std.mem.splitScalar(u8, line.?, ',');
+        const x = try std.fmt.parseInt(i64, split.next().?, 10);
+        const y = try std.fmt.parseInt(i64, split.next().?, 10);
+        const z = try std.fmt.parseInt(i64, split.next().?, 10);
+
+        try list.append(allocator, Coord{.x = x, .y = y, .z = z});
+    } else |_| {}
+
+    for (list.items,0..) |c1,i| {
+        for (list.items,0..) |c2,j| {
+            if (i <= j) continue;
+            const d = std.math.pow(usize,@abs(c2.x - c1.x), 2) + std.math.pow(usize,@abs(c2.y - c1.y), 2) + std.math.pow(usize,@abs(c2.z - c1.z),2);
+            try queue.add(Pair{.c1 = c1, .c2 = c2, .d = d});
+        }
+    }
+
+    for (0..1000) |_| {
+        const pair = queue.remove();
+        const v1 = map.get(pair.c1);
+        const v2 = map.get(pair.c2);
+        if (v1 == null and v2 == null) {
+            const n = sets.items.len;
+            try map.put(pair.c1, n);
+            try map.put(pair.c2, n);
+            try sets.append(allocator, try std.ArrayList(Coord).initCapacity(allocator, 0));
+            try sets.items[n].append(allocator,pair.c1);
+            try sets.items[n].append(allocator,pair.c2);
+        } else if (v1 != null and v2 == null) {
+            try sets.items[v1.?].append(allocator,pair.c2);
+            try map.put(pair.c2, v1.?);
+        } else if (v1 == null and v2 != null) {
+            try sets.items[v2.?].append(allocator,pair.c1);
+            try map.put(pair.c1, v2.?);
+        } else {
+            if (v1.? < v2.?) {
+                try sets.items[v1.?].appendSlice(allocator, sets.items[v2.?].items);
+                for (sets.items[v2.?].items) |c| {
+                    try map.put(c, v1.?);
+                }
+                sets.items[v2.?].shrinkAndFree(allocator, 0);
+            } else if (v2.? < v1.?) {
+                try sets.items[v2.?].appendSlice(allocator, sets.items[v1.?].items);
+                for (sets.items[v1.?].items) |c| {
+                    try map.put(c, v2.?);
+                }
+                sets.items[v1.?].shrinkAndFree(allocator, 0);
+            }
+        }
+    }
+
+    var max1: usize = 0;
+    var max2: usize = 0;
+    var max3: usize = 0;
+
+    for (sets.items) |set| {
+        const l = set.items.len;
+        if (l > max1) {
+            max3 = max2;
+            max2 = max1;
+            max1 = l;
+        } else if (l > max2) {
+            max3 = max2;
+            max2 = l;
+        } else if (l > max3) {
+            max3 = l;
+        }
+    }
+
+    print("{d}\n", .{max1 * max2 * max3});
+}
+
+
+fn part2(reader: *std.Io.Reader, allocator: std.mem.Allocator) !void {
+    var queue = std.PriorityQueue(Pair, void, cmp).init(allocator, {});
+    defer queue.deinit();
+
+    try queue.ensureTotalCapacity(100000);
+
+    var list = try std.ArrayList(Coord).initCapacity(allocator, 100);
+    defer list.deinit(allocator);
+
+    var map = std.HashMap(Coord, usize, Context, 80).init(allocator);
+    defer map.deinit();
+
+    var sets = try std.ArrayList(std.ArrayList(Coord)).initCapacity(allocator, 100);
+    defer sets.deinit(allocator);
+
+    while (reader.takeDelimiter('\n')) |line| {
+        if (line == null) break;
+
+
+        var split = std.mem.splitScalar(u8, line.?, ',');
+        const x = try std.fmt.parseInt(i64, split.next().?, 10);
+        const y = try std.fmt.parseInt(i64, split.next().?, 10);
+        const z = try std.fmt.parseInt(i64, split.next().?, 10);
+
+        try list.append(allocator, Coord{.x = x, .y = y, .z = z});
+    } else |_| {}
+
+    for (list.items,0..) |c1,i| {
+        for (list.items,0..) |c2,j| {
+            if (i <= j) continue;
+            const d = std.math.pow(usize,@abs(c2.x - c1.x), 2) + std.math.pow(usize,@abs(c2.y - c1.y), 2) + std.math.pow(usize,@abs(c2.z - c1.z),2);
+            try queue.add(Pair{.c1 = c1, .c2 = c2, .d = d});
+        }
+    }
+
+    var output: i64 = 0;
+
+    while(true) {
+        const pair = queue.remove();
+        const v1 = map.get(pair.c1);
+        const v2 = map.get(pair.c2);
+        if (v1 == null and v2 == null) {
+            const n = sets.items.len;
+            try map.put(pair.c1, n);
+            try map.put(pair.c2, n);
+            try sets.append(allocator, try std.ArrayList(Coord).initCapacity(allocator, 0));
+            try sets.items[n].append(allocator,pair.c1);
+            try sets.items[n].append(allocator,pair.c2);
+        } else if (v1 != null and v2 == null) {
+            try sets.items[v1.?].append(allocator,pair.c2);
+            try map.put(pair.c2, v1.?);
+            if (sets.items[v1.?].items.len == list.items.len) {
+                output = pair.c1.x * pair.c2.x;
+                break;
+            }
+        } else if (v1 == null and v2 != null) {
+            try sets.items[v2.?].append(allocator,pair.c1);
+            try map.put(pair.c1, v2.?);
+            if (sets.items[v2.?].items.len == list.items.len) {
+                output = pair.c1.x * pair.c2.x;
+                break;
+            }
+        } else {
+            if (v1.? < v2.?) {
+                try sets.items[v1.?].appendSlice(allocator, sets.items[v2.?].items);
+                for (sets.items[v2.?].items) |c| {
+                    try map.put(c, v1.?);
+                }
+                sets.items[v2.?].shrinkAndFree(allocator, 0);
+                if (sets.items[v1.?].items.len == list.items.len) {
+                    output = pair.c1.x * pair.c2.x;
+                    break;
+                }
+            } else if (v2.? < v1.?) {
+                try sets.items[v2.?].appendSlice(allocator, sets.items[v1.?].items);
+                for (sets.items[v1.?].items) |c| {
+                    try map.put(c, v2.?);
+                }
+                sets.items[v1.?].shrinkAndFree(allocator, 0);
+                if (sets.items[v2.?].items.len == list.items.len) {
+                    output = pair.c1.x * pair.c2.x;
+                    break;
+                }
+            }
+        }
+    }
+
+    print("{d}\n", .{output});
+}
diff --git a/src/main.zig b/src/main.zig
index 79979e4..e4e9a53 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -8,6 +8,7 @@ const day04 = @import("day04.zig");
 const day05 = @import("day05.zig");
 const day06 = @import("day06.zig");
 const day07 = @import("day07.zig");
+const day08 = @import("day08.zig");
 
 pub fn main() !void {
     if (std.os.argv.len != 3) {
@@ -41,6 +42,7 @@ pub fn main() !void {
         5 => day05.solve(args[2], stdin, allocator),
         6 => day06.solve(args[2], stdin, allocator),
         7 => day07.solve(args[2], stdin, allocator),
+        8 => day08.solve(args[2], stdin, allocator),
         else => print("Day not yet implemented", .{}),
     };
 }