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
71
72
73
74
75
76
|
const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const HashMap = std.HashMap;
const mem = std.mem;
const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const u64HashMap = HashMap(u64, void, u64ctx, 80);
const u64ctx = struct {
pub fn hash(_: @This(), k: u64) u64 {
return k;
}
pub fn eql(_: @This(), lhs: u64, rhs: u64) bool {
return lhs == rhs;
}
};
pub fn solve(galaxies: [][2]usize, popRows: u64HashMap, popCols: u64HashMap) !void {
var nEmpty: usize = 0;
var sDist: usize = 0;
for (galaxies[0..], 0..) |this, i| {
for (galaxies[i + 1 ..]) |other| {
const ai = @min(this[0], other[0]);
const aj = @min(this[1], other[1]);
const bi = @max(this[0], other[0]);
const bj = @max(this[1], other[1]);
sDist += bi - ai + bj - aj;
for (ai..bi) |row| {
if (popRows.get(row) == null) {
nEmpty += 1;
}
}
for (aj..bj) |col| {
if (popCols.get(col) == null) {
nEmpty += 1;
}
}
}
}
const part1 = sDist + nEmpty;
const part2 = sDist + nEmpty * 999_999;
print("{d}\n", .{part1});
print("{d}\n", .{part2});
}
pub fn main() !void {
var splitLines = mem.splitScalar(u8, fin, '\n');
var galaxies = ArrayList([2]usize).init(allocator);
var popRows = u64HashMap.init(allocator);
var popCols = u64HashMap.init(allocator);
defer galaxies.deinit();
var i: usize = 0;
while (splitLines.next()) |row| : (i += 1) {
for (row, 0..) |c, j| {
if (c == '#') {
try popRows.put(i, {});
try popCols.put(j, {});
try galaxies.append(.{ i, j });
}
}
}
try solve(galaxies.items, popRows, popCols);
}
|
