advent-of-code

Solutions for Advent of Code.
git clone git://git.amin.space/advent-of-code.git
Log | Files | Refs | LICENSE

day_09.zig (3666B)

      1 const std = @import("std");
      2 const debug = std.debug;
      3 const heap = std.heap;
      4 const LinkedList = std.LinkedList;
      5 const mem = std.mem;
      6 
      7 const Node = LinkedList(u32).Node;
      8 const debug_logging: bool = false;
      9 
     10 pub fn main() void {
     11     var allocator = &std.heap.DirectAllocator.init().allocator;
     12     debug.warn("09-1: {}\n", computeHighScore(allocator, 465, 71498));
     13     debug.warn("09-2: {}\n", computeHighScore(allocator, 465, 71498 * 100));
     14 }
     15 
     16 fn printTurn(player_turn: ?u32, circle: LinkedList(u32), current_num: u32) void {
     17     if (player_turn) |t| {
     18         logDebug("[{}] ", t);
     19     } else {
     20         logDebug("[-] ");
     21     }
     22 
     23     var it = circle.first;
     24     var i: usize = 0;
     25     while (it) |node| : ({ it = node.next; i += 1; }) {
     26         if (i >= circle.len) {
     27             break;
     28         }
     29         if (node.data == current_num) {
     30             logDebug("({}) ", node.data);
     31         } else {
     32             logDebug("{} ", node.data);
     33         }
     34     }
     35 
     36     logDebug("\n");
     37 }
     38 
     39 fn computeHighScore(allocator: *mem.Allocator, num_players: u32, num_marbles: u32) !u32 {
     40     var scores = try allocator.alloc(u32, num_players);
     41     defer allocator.free(scores);
     42     for (scores) |*s| {
     43         s.* = 0;
     44     }
     45 
     46     const buf = try allocator.alloc(u8, num_marbles * @sizeOf(Node));
     47     defer allocator.free(buf);
     48 
     49     // TODO: Why does this explode my memory usage!?
     50     //const node_allocator = allocator;
     51 
     52     const node_allocator = &heap.FixedBufferAllocator.init(buf[0..]).allocator;
     53 
     54     var circle = LinkedList(u32).init();
     55 
     56     var initial_marble = try circle.createNode(0, node_allocator);
     57     defer circle.destroyNode(initial_marble, node_allocator);
     58 
     59     circle.first = initial_marble;
     60     circle.last = circle.first;
     61     circle.first.?.next = circle.first;
     62     circle.first.?.prev = circle.first;
     63     circle.len = 1;
     64 
     65     var current: *Node = circle.first orelse unreachable;
     66     var last_played: u32 = 0;
     67     var turn: u32 = 1;
     68 
     69     while (last_played < num_marbles) : (last_played += 1) {
     70         var to_be_played = last_played + 1;
     71 
     72         if (to_be_played % 23 == 0) {
     73             var to_remove = current.prev.?.prev.?.prev.?.prev.?.prev.?.prev.?.prev orelse unreachable;
     74             defer circle.destroyNode(to_remove, node_allocator);
     75 
     76             var to_make_current = to_remove.next orelse unreachable;
     77             circle.remove(to_remove);
     78             current = to_make_current;
     79 
     80             scores[turn] += (to_be_played + to_remove.data);
     81         } else {
     82             var new_marble = try circle.createNode(to_be_played, node_allocator);
     83             var two_clockwise_from_current = current.next.?.next orelse unreachable;
     84             circle.insertBefore(two_clockwise_from_current, new_marble);
     85             current = new_marble;
     86         }
     87         turn += 1;
     88         turn %= num_players;
     89     }
     90 
     91     var high_score: u32 = 0;
     92     for (scores) |s| {
     93         if (s > high_score) {
     94             high_score = s;
     95         }
     96     }
     97     logDebug("High Score: {}\n", high_score);
     98     return high_score;
     99 }
    100 
    101 test "compute high score" {
    102     var allocator = &std.heap.DirectAllocator.init().allocator;
    103     debug.warn("\n");
    104     debug.assert(32 == try computeHighScore(allocator, 9, 25));
    105     debug.assert(8317 == try computeHighScore(allocator, 10, 1618));
    106     debug.assert(146373 ==  try computeHighScore(allocator, 13, 7999));
    107     debug.assert(2764 == try computeHighScore(allocator, 17, 1104));
    108     debug.assert(54718 == try computeHighScore(allocator, 21, 6111));
    109     debug.assert(37305 == try computeHighScore(allocator, 30, 5807));
    110 }
    111 
    112 fn logDebug(comptime format_str: []const u8, args: ...) void {
    113     if (debug_logging) {
    114         debug.warn(format_str, args);
    115     }
    116 }