const std = @import("std");
const path = "../data/day03/input.txt";
const retSize = u24;
const lineSize = getLineSize();
fn first() anyerror!retSize {
const input = @embedFile(path);
var lines = std.mem.split(u8, input, "\n");
var ones: [lineSize]retSize = undefined;
var zeros: [lineSize]retSize = undefined;
while (lines.next()) |line| {
for (line) |bit, idx| {
if (bit == '0') {
zeros[idx] += 1;
} else {
ones[idx] += 1;
}
}
}
var gammaRate: [lineSize]u8 = undefined;
var epsilonRate: [lineSize]u8 = undefined;
for (ones) |val, i| {
if (val > zeros[i]) {
gammaRate[i] = '1';
epsilonRate[i] = '0';
} else {
gammaRate[i] = '0';
epsilonRate[i] = '1';
}
}
const gr = try std.fmt.parseUnsigned(retSize, &gammaRate, 2);
const er = try std.fmt.parseUnsigned(retSize, &epsilonRate, 2);
return gr * er;
}
fn second() anyerror!retSize {
const input = @embedFile(path);
var lines = std.mem.tokenize(u8, input, "\n");
var buffer: [1000 * lineSize * 100]u8 = undefined;
var fba = std.heap.FixedBufferAllocator.init(&buffer);
const allocator = fba.allocator();
var lines_array = std.ArrayList(retSize).init(allocator);
defer lines_array.deinit();
var lines_array2 = std.ArrayList(retSize).init(allocator);
defer lines_array2.deinit();
while (lines.next()) |line| {
try lines_array.append(try std.fmt.parseUnsigned(retSize, line, 2));
try lines_array2.append(try std.fmt.parseUnsigned(retSize, line, 2));
}
const ox = try getOxigenRating(allocator, &lines_array);
const co = try getCO2Rating(allocator, &lines_array2);
return ox * co;
}
fn getOxigenRating(allocator: std.mem.Allocator, oxigen: *std.ArrayList(retSize)) anyerror!retSize {
var to_remove = std.ArrayList(usize).init(allocator);
defer to_remove.deinit();
var idx: usize = lineSize;
while (oxigen.items.len > 1) : (idx -= 1) {
var ones: retSize = 0;
var zeros: retSize = 0;
// count ones and zeros
for (oxigen.items) |line| {
if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {
ones += 1;
} else {
zeros += 1;
}
}
// std.debug.print("{d} {d} {d}", .{ones, zeros, idx-1});
for (oxigen.items) |line, i| {
if (ones >= zeros) {
if ((line & (@as(retSize, 1) <<| idx - 1)) == 0) {
try to_remove.append(i);
}
} else {
if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {
try to_remove.append(i);
}
}
}
std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));
for (to_remove.items) |i| {
_ = oxigen.swapRemove(i);
}
try to_remove.resize(0);
// std.debug.print("{d}\n", .{oxigen.items.len});
}
return oxigen.items[0];
}
fn getCO2Rating(allocator: std.mem.Allocator, co2: *std.ArrayList(retSize)) anyerror!retSize {
var to_remove = std.ArrayList(usize).init(allocator);
defer to_remove.deinit();
var idx: usize = lineSize;
while (co2.items.len > 1) : (idx -= 1) {
var ones: retSize = 0;
var zeros: retSize = 0;
// count ones and zeros
for (co2.items) |line| {
if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {
ones += 1;
} else {
zeros += 1;
}
}
// std.debug.print("{d} {d} {d}", .{ones, zeros, idx-1});
for (co2.items) |line, i| {
if (zeros <= ones) {
if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {
try to_remove.append(i);
}
} else {
if ((line & (@as(retSize, 1) <<| idx - 1)) == 0) {
try to_remove.append(i);
}
}
}
std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));
for (to_remove.items) |i| {
_ = co2.swapRemove(i);
}
try to_remove.resize(0);
// std.debug.print("{d}\n", .{co2.items.len});
}
return co2.items[0];
}
fn getLineSize() usize {
const input = @embedFile(path);
var ret: usize = 0;
for (input) |bit, idx| {
if (bit == '\n') {
ret = idx;
break;
}
}
return ret;
}
pub fn main() anyerror!void {
var timer = try std.time.Timer.start();
_ = try first();
const f = timer.lap() / 1000;
_ = try second();
const s = timer.lap() / 1000;
std.debug.print("Day 3 \t\tfirst: {d}µs \t\tsecond: {d}µs\n", .{ f, s });
}
test "first" {
try std.testing.expectEqual(@as(retSize, 3847100), try first());
}
test "second" {
try std.testing.expectEqual(@as(retSize, 4105235), try second());
}