advent-of-code

commit 185e0a182a748919924efac18623b2440c23ef6d
parent 94348ec92bad1b3a63a603fda1aa60427cb190da
Author: amin <dev@aminmesbah.com>
Date:   Tue, 11 Dec 2018 05:37:44 +0000

Add solution for 09-1

FossilOrigin-Name: b7ab8d9f1a38a9bf94e9e281d7927cf01b4d82eed2bb9c2ea9a7367a15442f06
Diffstat:
A
day_09.zig
 | 
108
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 108 insertions(+), 0 deletions(-)
diff --git a/day_09.zig b/day_09.zig
@@ -0,0 +1,108 @@
+const std = @import("std");
+const debug = std.debug;
+const LinkedList = std.LinkedList;
+const mem = std.mem;
+
+const Node = LinkedList(u32).Node;
+const debug_logging: bool = false;
+
+pub fn main() void {
+    var allocator = &std.heap.DirectAllocator.init().allocator;
+    debug.warn("09-1: {}\n", computeHighScore(allocator, 465, 71498));
+}
+
+fn printTurn(player_turn: ?u32, circle: LinkedList(u32), current_num: u32) void {
+    if (player_turn) |t| {
+        logDebug("[{}] ", t);
+    } else {
+        logDebug("[-] ");
+    }
+
+    var it = circle.first;
+    var i: usize = 0;
+    while (it) |node| : ({ it = node.next; i += 1; }) {
+        if (i >= circle.len) {
+            break;
+        }
+        if (node.data == current_num) {
+            logDebug("({}) ", node.data);
+        } else {
+            logDebug("{} ", node.data);
+        }
+    }
+
+    logDebug("\n");
+}
+
+fn computeHighScore(allocator: *mem.Allocator, num_players: u32, num_marbles: u32) !u32 {
+    var scores = try allocator.alloc(u32, num_players);
+    defer allocator.free(scores);
+    for (scores) |*s| {
+        s.* = 0;
+    }
+
+    var circle = LinkedList(u32).init();
+
+    var initial_marble = try circle.createNode(0, allocator);
+    defer circle.destroyNode(initial_marble, allocator);
+
+    circle.first = initial_marble;
+    circle.last = circle.first;
+    circle.first.?.next = circle.first;
+    circle.first.?.prev = circle.first;
+    circle.len = 1;
+
+    var current: *Node = circle.first orelse unreachable;
+    var last_played: u32 = 0;
+    var turn: u32 = 1;
+
+    printTurn(null, circle, current.data);
+    while (last_played < num_marbles) : (last_played += 1) {
+        var to_be_played = last_played + 1;
+
+        if (to_be_played % 23 == 0) {
+            var to_remove = current.prev.?.prev.?.prev.?.prev.?.prev.?.prev.?.prev orelse unreachable;
+            defer circle.destroyNode(to_remove, allocator);
+
+            var to_make_current = to_remove.next orelse unreachable;
+            circle.remove(to_remove);
+            current = to_make_current;
+
+            scores[turn] += (to_be_played + to_remove.data);
+        } else {
+            var new_marble = try circle.createNode(to_be_played, allocator);
+            var two_clockwise_from_current = current.next.?.next orelse unreachable;
+            circle.insertBefore(two_clockwise_from_current, new_marble);
+            current = new_marble;
+        }
+        printTurn(turn + 1, circle, current.data);
+        turn += 1;
+        turn %= num_players;
+    }
+
+    var high_score: u32 = 0;
+    for (scores) |s| {
+        if (s > high_score) {
+            high_score = s;
+        }
+    }
+    logDebug("High Score: {}\n", high_score);
+    return high_score;
+}
+
+test "compute high score" {
+    var allocator = &std.heap.DirectAllocator.init().allocator;
+    debug.warn("\n");
+    debug.assert(32 == try computeHighScore(allocator, 9, 25));
+    debug.assert(8317 == try computeHighScore(allocator, 10, 1618));
+    debug.assert(146373 ==  try computeHighScore(allocator, 13, 7999));
+    debug.assert(2764 == try computeHighScore(allocator, 17, 1104));
+    debug.assert(54718 == try computeHighScore(allocator, 21, 6111));
+    debug.assert(37305 == try computeHighScore(allocator, 30, 5807));
+}
+
+fn logDebug(comptime format_str: []const u8, args: ...) void {
+    if (debug_logging) {
+        debug.warn(format_str, args);
+    }
+}