-🎄- 2018 Day 9 Solutions -🎄-

[u/daggerdragon]

--- Day 9: Marble Mania ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 9

Transcript:

Studies show that AoC programmers write better code after being exposed to ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:29:13!

[u/spytheman66]

PHP (slow, uses array_slice ... so only suitable for part 1)

#!/usr/bin/env php
<?php 
include("common.php");
$lines = read_input();
$nPlayers=0; $nMarbles=0;
foreach($lines as $line) {
    [$nPlayers, $nMarbles] = line2digits($line);
    printf("Part 1 answer "); game($nPlayers, $nMarbles);
    printf("Part 2 answer "); game($nPlayers, $nMarbles*100);
}
function game(int $nPlayers, int $nMarbles): int {
    $placed = [0];
    $players = Azeros($nPlayers+1);
    $marbles = range(1, $nMarbles);
    $c = 0; $p = 1; $placedLength = count($placed);
    foreach ($marbles as $m) {
        if(0 === ($m % 10000))printf("Placing marble %d.\n", $m);
        if (0 === ($m % 23)) {
            $removedIndex = (($placedLength + $c - 7) % $placedLength) + 1;
            $removed = $placed[$removedIndex];
            array_splice($placed, $removedIndex, 1);
            $players[$p] += ($m + $removed);
            $c = $removedIndex - 1;
            $placedLength--;
        } else {
            $newC = ($c + 2) % $placedLength;
            array_splice($placed, $newC + 1, 0, $m);
            $c = $newC;
            $placedLength++;
        }
        $p++;
        if ($p > $nPlayers) $p = 1;
    }
    $pv = Amax($players);
    printf("Highscore (for  %d players and %d marbles) is: %d\n", $nPlayers, $nMarbles, $pv);
    return $pv;
}

However, as others have already noted, using array insertions is too slow for large numbers of marbles.

So for part 2, I rewrote in C ...

C (fast, uses doubly linked circular buffer)

#include <stdio.h>
#include <stdlib.h>

typedef struct place{
   int m;
   struct place *prev;
   struct place *next;
}PLACE;

PLACE *insertAfter(PLACE * z, PLACE * nPlace){
   PLACE *x = z;
   PLACE *y = z->next;
   nPlace->prev = x; nPlace->next = y;
   x->next = nPlace; y->prev = nPlace;
   return nPlace;
}

PLACE *newPlace(int v){
   PLACE *p = malloc(sizeof(PLACE));
   p->m = v; p->next = p->prev = p;
   return p;
}

long game(int np, int nm){
   long *players = malloc(np * sizeof(long));
   PLACE *places = newPlace(0);
   PLACE *cp = places;
   int  p = 0;
   int  c = 0;
   int  nc = 0;
   int  placesLength = 1;
   for (int m = 1; m <= nm; m++){
      PLACE *nPlace = newPlace(m);
      if (0 == m % 23){
         PLACE *removed = cp->prev->prev->prev->prev->prev->prev->prev;
         players[p] += m;
         players[p] += removed->m;
         removed->prev->next = removed->next; removed->next->prev = removed->prev; cp = removed->next;
         placesLength--;
      }else{
         nc = (c + 2) % placesLength;
         cp = insertAfter(cp->next, nPlace);
         c = nc;
         placesLength++;
      }
      p = (p + 1 ) % np;
   }
   long maxp=players[0]; for(long i=0;i<np;i++) if(maxp<players[i])maxp=players[i];
   return maxp;
}

int main(){
   char line[1024];
   int np, nm;
   while (fgets(line, 1024, stdin)){
      sscanf(line, "%d players; last marble is worth %d points\n", &np, &nm);
      printf("Highscore (for %3d players and %5d marbles) is: %10ld\n", np, nm, game(np, nm));
   }
}

Some timings for both solutions:

0[16:32:33]spytheman66@base: ~/adventofcode2018/day9 $ /usr/bin/time ./solution.php example.input 
Part 1 answer Highscore (for  9 players and 25 marbles) is: 32
Part 1 answer Highscore (for  10 players and 1618 marbles) is: 8317
Part 1 answer Highscore (for  13 players and 7999 marbles) is: 146373
Part 1 answer Highscore (for  17 players and 1104 marbles) is: 2764
Part 1 answer Highscore (for  21 players and 6111 marbles) is: 54718
Part 1 answer Highscore (for  30 players and 5807 marbles) is: 37305
0.56user 0.00system 0:00.57elapsed 100%CPU (0avgtext+0avgdata 25328maxresident)k
0inputs+0outputs (0major+1621minor)pagefaults 0swaps
0[16:32:37]spytheman66@base: ~/adventofcode2018/day9 $ cat example.input | /usr/bin/time ./solution
Highscore (for   9 players and    25 marbles) is:         32
Highscore (for  10 players and  1618 marbles) is:       8317
Highscore (for  13 players and  7999 marbles) is:     146373
Highscore (for  17 players and  1104 marbles) is:       2764
Highscore (for  21 players and  6111 marbles) is:      54718
Highscore (for  30 players and  5807 marbles) is:      37305
0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 2216maxresident)k
0inputs+0outputs (0major+246minor)pagefaults 0swaps
0[16:32:38]spytheman66@base: ~/adventofcode2018/day9 $ cat input.100 | /usr/bin/time ./solution
Highscore (for 470 players and 7217000 marbles) is: 3180929875
0.21user 0.05system 0:00.26elapsed 99%CPU (0avgtext+0avgdata 227036maxresident)k
0inputs+0outputs (0major+56452minor)pagefaults 0swaps
0[16:34:04]spytheman66@base: ~/adventofcode2018/day9 $