Ryan Palo

Posted on Dec 9, 2018

AoC Day 9: Marble Mania

#adventofcode #discuss

It's the weekend, and I'm using that to get caught up since I was starting fall behind throughout last week. Hopefully, you're able to keep up with this hectic pace!

On Day 9's challenge, the elves are teaching us marble games! Given a series of moves, we'll be simulating the game and calculating scores.

Let's get rolling! (Eh? Eh? A little bit of marble humor there, just for you. 🎅)

Top comments (16)

Mustafa Haddara • Dec 9 '18 • Edited

My first approach was just to brute force this, using a big array and inserting/removing as needed.

For the Part 1 input, this was...fine. It ran in less than half a second.

For the Part 2 input, however, it didn't simply scale up 100x! (0.5 seconds * 100 = 50 seconds = still Fast Enough). I'm guessing all of the array slicing/copies meant that this brute force algorithm was actually n², so scaling up the input size by 100 meant scaling up the run time by 10,000!

It took me a second to realize the trick was to use a circular doubly-linked list. Then, iterating through "clockwise" is following the next pointer, while iterating "counter-clockwise" is the prev pointer.

Here's what that looks like in Julia:

function find_winning_player(input)
    num_players, final_marble_value = parse_input(input)
    marbles = Circle(0)
    points = map(c->Int(c), zeros(num_players))

    current_marble = 1
    current_player = 1

    while current_marble <= final_marble_value
        if current_marble % 23 == 0
            # do weird point stuff
            points[current_player] += current_marble
            to_remove = marbles
            for _ in 1:7
                to_remove = to_remove.prev
            end
            points[current_player] += to_remove.value
            # delete to_remove
            to_remove.prev.next = to_remove.next
            to_remove.next.prev = to_remove.prev
            marbles = to_remove.next
        else
            # insert
            one_ahead = marbles.next
            two_ahead = one_ahead.next

            next_marble = Circle(current_marble, one_ahead, two_ahead)

            one_ahead.next = next_marble
            two_ahead.prev = next_marble
            marbles = next_marble
        end
        current_marble += 1
        current_player += 1
        if current_player > num_players
            current_player = 1
        end
    end

    return maximum(points)
end

mutable struct Circle
    value::Int
    prev::Circle
    next::Circle
    function Circle(value::Int) 
        c = new()
        c.value = value
        c.prev = c
        c.next = c
        return c
    end

    Circle(value::Int, prev::Circle, next::Circle) = new(value, prev, next)
end

function parse_input(input)
    chunks = split(input, " ")
    num_players = parse(Int, chunks[1])
    point_value = 100*parse(Int, chunks[7])
    return (num_players, point_value)
end

function main()
    filename = ARGS[1]  # julia arrays are 1-indexed!
    input = split(read(filename, String), "\n")[1]
    test_input = "10 players; last marble is worth 1618 points"

    println(find_winning_player(input))
end

main()

Creating an initial node that points to itself feels weird, but to be fair that models the circle idea correctly.

Joe Zack • Dec 9 '18

Heh yeah...I put too much thought into how those first couple turns would go with the circular linked list. Turns out it "just worked" :)

Mustafa Haddara • Dec 10 '18

I know, right?! It's like magic.

Tiago Romero Garcia • Dec 9 '18 • Edited

JavaScript solution

The trick for this one is to use a circular linked list. You need to handle pointers to both right and left nodes for each addition and removal.

Then, traversing clockwise is just moving rightward and counter-clockwise is leftward.

reader.js

const fs = require('fs');
const readline = require('readline');

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

    return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

09-common.js

class Node {
    constructor(value) {
        this.value = value;
        this.right = this;
        this.left = this;
    }

    addToRight(neighbor) {
        if (this.right) {
            this.right.left = neighbor;
        }
        neighbor.right = this.right;
        neighbor.left = this;
        this.right = neighbor;
    }

    visitLeft(times = 1) {
        let node = this;
        for (let i = 0; i < times; i++) {
            node = node.left
        }
        return node;
    }

    remove() {
        const left = this.left;
        const right = this.right;
        left.right = right;
        right.left = left;
        this.right = null;
        this.left = null;
    }
}

const parseInput = input => {
    const inputRegex = /^(?<players>\d+) players; last marble is worth (?<marbles>\d+) points$/;
    const { players, marbles } = input.match(inputRegex).groups;
    return { players: +players, marbles : +marbles};
};

const getPlayerScores = (players, marbles) => {
    const playerScores = Array.from({ length: players }, p => 0);

    let currentMarble = new Node(0);
    for (let i = 1; i <= marbles; i++) {
        const newMarble = new Node(i);

        if (i % 23 > 0) {
            currentMarble.right.addToRight(newMarble);
            currentMarble = newMarble;
        }
        else {
            const currentPlayer = i % players;
            const marbleToBeRemoved = currentMarble.visitLeft(7);
            playerScores[currentPlayer] += i + marbleToBeRemoved.value;
            currentMarble = marbleToBeRemoved.right;
            marbleToBeRemoved.remove(); 
        }
    }

    return playerScores;
}

module.exports = {
    parseInput,
    getPlayerScores
};

09a.js

const { readFile } = require('./reader');

const {
    parseInput,
    getPlayerScores
} = require('./09-common');

(async () => {
    const lines = await readFile('09-input.txt');

    const { players, marbles } = parseInput(lines[0]);

    const playerScores = getPlayerScores(players, marbles);

    const highScore = Math.max(...playerScores.values());

    console.log(`The highest score is ${highScore}`);
})();

09b.js

const { readFile } = require('./reader');

const {
    parseInput,
    getPlayerScores
} = require('./09-common');

(async () => {
    const lines = await readFile('09-input.txt');

    const { players, marbles } = parseInput(lines[0]);

    const playerScores = getPlayerScores(players, marbles*100);

    const highScore = Math.max(...playerScores.values());

    console.log(`The highest score is ${highScore}`);
})();

Ali Spittel • Dec 10 '18

Python has a super-powered C doubly linked list built in, so I feel like I'm totally cheating here, but:

import re
from collections import deque

def get_sequence(max, players):
    sequence = deque()
    scores = [0] * players
    for marble in range(0, max + 1):
        if marble % 23 == 0 and marble > 0:
            current_player = marble % players
            sequence.rotate(-7)
            scores[current_player] += marble + sequence.pop()
        else:
            sequence.rotate(2)
            sequence.append(marble)
    return scores


with open('input.txt', 'r') as f:
    for line in f:
        players, last_marble = [int(n) for n in re.findall(r'\d+', line)]
        scores = get_sequence(last_marble, players)
        print(max(scores))
        large_scores = get_sequence(last_marble * 100, players)        
        print(max(large_scores))

When I was whiteboarding this out, I was noticing a mathematical pattern. Didn't fully go down that road, but I'd be super interested to see if someone did this using arithmetic instead of a linked list.

E. Choroba • Dec 9 '18 • Edited

For the part 1, I used the naive solution with an array. It took about 0.55s.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ max };

my $input = <>;
my ($players, $points) = $input =~ /(\d+)/g;

my $player = 1;
my $marble = 0;
my $current = 0;
my @circle = ($marble);
my %score;
while ($marble != $points) {
    ++$marble;

    if ($marble % 23) {
        my $pos = ($current + 2) % @circle;
        splice @circle, $pos, 0, $marble;
        $current = $pos;

    } else {
        $score{$player} += $marble;
        my $remove = $current - 7;
        $remove += @circle if $remove < 0;
        $remove %= @circle;
        $score{$player} += (splice @circle, $remove, 1)[0];
        $current = $remove;
    }

    ++$player;
    $player %= $players;
}

say max(values %score);

For part 2, it took 2h 47m, so I decided to switch to linked lists. Using POSIX::_exit I skipped the final global destruction, which saved me almost 1 second, so the program finished in 8s.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
use POSIX qw{ _exit };

use List::Util qw{ max };

use constant { PREV  => 0,
               NEXT  => 1,
               VALUE => 2 };

my $input = <>;
my ($players, $points) = $input =~ /(\d+)/g;
$points *= 100;

my $player = 1;
my $marble = 0;
my $current = [];
$current->[PREV]  = $current;
$current->[NEXT]  = $current;
$current->[VALUE] = 0;

my %score;
while ($marble != $points) {
    ++$marble;

    if ($marble % 23) {
        my $before = $current->[NEXT];
        my $after  = $before->[NEXT];
        my $insert = [$before, $after, $marble];
        $before->[NEXT] = $insert;
        $after->[PREV] = $insert;
        $current = $insert;

    } else {
        my $remove = $current;
        $remove = $remove->[PREV] for 1 .. 7;
        $score{$player} += $marble + $remove->[VALUE];
        my ($before, $after) = @$remove[PREV, NEXT];
        $before->[NEXT] = $after;
        $after->[PREV]  = $before;
        $current = $after;
    }

    ++$player;
    $player %= $players;
}

say max(values %score);
_exit(0);

Joe Zack • Dec 9 '18

I think this has been my favorite problem so far.

I wrote a helper method "cycle" that would move $x left or right and made for an easy translation from the problem description to code.

Part B was a nice surprise for a lazy Sunday morning :)

štef • Dec 9 '18

I managed to do this in elixir! As elixir is immutable it cant have real circular data structures so i had to use zippers

The second challenge took 3 s :)

defmodule Day09 do
  @doc """
  Calcualte challenge

      iex> Day09.run({9, 25, 23})
      32
  """
  def run(config) do
    start_values = {0, 1, {[], 0, []}, %{}}
    {_, players_score} = marble(start_values, config)
    {_, score} = Enum.max_by(players_score, fn {_, v} -> v end)
    score
  end

  @doc """
  Adds a marble

      iex> start_values = {0, 1, {[], 0, []}, %{}}
      iex> Day09.marble(start_values, {1, 1, 23})
      {{[0], 1, []}, %{}}
      iex> Day09.marble(start_values, {2, 2, 23})
      {{[0], 2, [1]}, %{}}
      iex> Day09.marble(start_values, {3, 3, 23})
      {{[1, 2, 0], 3, []}, %{}}
      iex> Day09.marble(start_values, {9, 22, 23})
      {{[5, 21, 10, 20, 2, 19, 9, 18, 4, 17, 8, 16, 0], 22, [11, 1, 12, 6, 13, 3, 14, 7, 15]}, %{}}
      iex> Day09.marble(start_values, {9, 25, 23})
      {{[20, 24, 2, 19, 18, 4, 17, 8, 16, 0], 25, [10, 21, 5, 22, 11, 1, 12, 6, 13, 3, 14, 7, 15]}, %{4 => 32}}

  """
  def marble(
        {player, marble, marbles, players_score},
        {players_count, highest_marble, divisible_marble} = config
      ) do
    cond do
      marble > highest_marble ->
        {marbles, players_score}

      rem(marble, divisible_marble) == 0 ->
        {removed_marble, marbles} = remove_marble(marbles)

        players_score =
          Map.update(
            players_score,
            player,
            marble + removed_marble,
            &(&1 + marble + removed_marble)
          )

        marble(
          {rem(player + 1, players_count), marble + 1, marbles, players_score},
          config
        )

      true ->
        marbles = add_marble(marble, marbles)

        marble(
          {rem(player + 1, players_count), marble + 1, marbles, players_score},
          config
        )
    end
  end

  @doc """
  Add a marble

      iex> Day09.add_marble(1, {[], 0, []})
      {[0], 1, []}
      iex> Day09.add_marble(2, {[0], 1, []})
      {[0], 2, [1]}
      iex> Day09.add_marble(3, {[0], 2, [1]})
      {[1, 2, 0], 3, []}
      iex> Day09.add_marble(4, {[1, 2, 0], 3, []})
      {[0], 4, [2, 1, 3]}
  """
  def add_marble(marble, marbles) do
    {previous, current, next} = next(marbles)
    {[current | previous], marble, next}
  end

  @doc """
  Add a marble

      iex> Day09.remove_marble({[5, 21, 10, 20, 2, 19, 9, 18, 4, 17, 8, 16, 0], 22, [11, 1, 12, 6, 13, 3, 14, 7, 15]})
      {9, {[18, 4, 17, 8, 16, 0], 19, [2, 20, 10, 21, 5, 22, 11, 1, 12, 6, 13, 3, 14, 7, 15]}}
  """
  def remove_marble(marbles) do
    {previous, current, next} = Enum.reduce(1..7, marbles, fn _, marbles -> previous(marbles) end)
    [new_current | next] = next
    {current, {previous, new_current, next}}
  end

  @doc """
  Moves to the right

      iex> Day09.next({[], 0, []})
      {[], 0, []}
      iex> Day09.next({[0], 1, []})
      {[], 0, [1]}
      iex> Day09.next({[0], 2, [1, 3]})
      {[2, 0], 1, [3]}
  """
  def next({[], current, []}), do: {[], current, []}

  def next({previous, current, []}) do
    next = Enum.reverse([current | previous])
    [current | next] = next
    {[], current, next}
  end

  def next({previous, current, next}) do
    previous = [current | previous]
    [current | next] = next
    {previous, current, next}
  end

  @doc """
  Moves to the left

      iex> Day09.previous({[], 1, [0, 2]})
      {[0, 1], 2, []}
      iex> Day09.previous({[0], 2, [1, 3]})
      {[], 0, [2, 1, 3]}
  """
  def previous({[], current, next}) do
    previous = Enum.reverse([current | next])
    [current | previous] = previous
    {previous, current, []}
  end

  def previous({previous, current, next}) do
    next = [current | next]
    [current | previous] = previous
    {previous, current, next}
  end
end

Viktors Jenovs • Dec 9 '18

I did the part 1 using array and splicing and it took ~30 seconds to finish (and it was getting exponentially slower as the number of marbles increased).

So for the part 2 I tried to find the correct data structure, but not having CS background I spent a lot of time just googling around not finding anything suitable. Finally I looked at reddit for a hint and learned about Doubly Circular Linked List. After that implementation was quick and easy :)

<?php
$players = 463;
$marbles = 71787;

function play($players, $marbles) {
  $circle = [];
  $player = 0;
  $scores = [];
  $currentMarble = 0;

  for ($marble=0; $marble <= $marbles; $marble++) {
    if (!$marble) {
      $circle[0]['prev'] = 0;
      $circle[0]['next'] = 0;
    } else if ($marble % 23) {
      $newPrev = $circle[$currentMarble]['next'];
      $newNext = $circle[$newPrev]['next'];
      $circle[$newPrev]['next'] = $marble;
      $circle[$newNext]['prev'] = $marble;
      $circle[$marble] = ['prev' => $newPrev, 'next' => $newNext];

      $currentMarble = $marble;
    } else {
      $currScore = !empty($scores[$player]) ? $scores[$player] : 0;

      $taken = $currentMarble;
      for ($i=0; $i < 7; $i++) {
        $taken = $circle[$taken]['prev'];
      }

      $currentMarble = $circle[$taken]['next'];
      $leftMarble = $circle[$taken]['prev'];
      $circle[$currentMarble]['prev'] = $leftMarble;
      $circle[$leftMarble]['next'] = $currentMarble;

      $scores[$player] = $currScore + $marble + $taken;
      $i++;
    }
    $player = ++$player % $players;
  }

  return max($scores);
}


echo "Answer to Part 1: " . play($players, $marbles) . "\n";
echo "Answer to Part 2: " . play($players, $marbles * 100) . "\n";
?>

Ryan Palo • Dec 10 '18

Nice find!

Carly Ho 🌈 • Dec 9 '18

PHP

OKAY FINALLY. I had to up the PHP default memory limit by 8x to actually get the second part to run because I kept running into memory allocation problems, haha. Also learned a bunch about how references work in PHP to stop the program from segmentation faulting! Exciting!

Part 1 (brute force-ish):

<?php
$players = intval(trim($argv[1]));
$lastval = intval(trim($argv[2]));

$circle = array(0);
$elfscores = array_fill(0, $players, 0);
$elf = 0;
$insertpos = 1;
echo "Round 1"."\n";
$round = 1;
for ($i = 1; $i <= $lastval; $i++) {
  if ($i % 23 == 0) {
    $elfscores[$elf] += $i;
    $elfscores[$elf] += array_splice($circle, $insertpos-9, 1)[0];
    $insertpos = $insertpos-7;
  } else {
    array_splice($circle, $insertpos, 0, $i);
    $insertpos += 2;
    if ($insertpos >= count($circle)+1) {
      $insertpos = 1;
    }
  }
  $elf = ($elf+1) % $players;
  if ($elf == 0) {
    $round++;
    echo "Round ".$round." (".($lastval-$i)." marbles remaining)\n";
  }
}
echo max($elfscores);
die(1);

Part 2: (double circular linked list implementation)

<?php
ini_set('memory_limit', '1024M');
class Node {
  public $content;
  public $prev;
  public $next;

  function __construct($content, $prev=null, $next=null) {
    $this->content = $content;
    $this->prev = $prev;
    $this->next = $next;
  }

  function print() {
    return $this->content;
  }
}

class LinkedList {
  private $first;
  private $current;
  private $count;

  function __construct() {
    $this->count = 1;
    $node = new Node(0);
    $node->prev = &$node;
    $node->next = &$node;
    $this->first = &$node;
    $this->current = &$node;
  }

  function push($content) {
    $next = $this->current->next;
    $current = $this->current;
    $n = new Node($content, $current, $next);
    $next->prev = &$n;
    $current->next = &$n;
    $this->current = &$n;
    $this->count++;
  }

  function pop() {
    $n = $this->current;
    $val = $n->content;
    $next = &$n->next;
    $prev = &$n->prev;
    $prev->next = $next;
    $next->prev = $prev;
    $this->current = $next;
    unset($n);
    $this->count--;
    return $val;
  }

  function goClockwise($num) {
    for ($i = 0; $i < $num; $i++) {
      $this->current = &$this->current->next;
    }
  }

  function goCounterClockwise($num) {
    for ($i = 0; $i < $num; $i++) {
      $this->current = &$this->current->prev;
    }
  }

  function print() {
    $arr = array($this->first->print());
    $c = $this->first;
    while ($c->next != $this->first) {
      array_push($arr, $c->next->print());
      $c = $c->next;
    }
    echo join(" ", $arr)."\n";
    return;
  }
}

$players = intval(trim($argv[1]));
$lastval = intval(trim($argv[2]));

$circle = new LinkedList();
$elfscores = array_fill(0, $players, 0);
$elf = 0;
$round = 1;
for ($i = 1; $i <= $lastval; $i++) {
  if ($i % 23 == 0) {
    $elfscores[$elf] += $i;
    $circle->goCounterClockwise(7);
    $add = $circle->pop();
    $elfscores[$elf] += $add;
  } else {
    $circle->goClockwise(1);
    $circle->push($i);
  }
  $elf = ($elf+1) % $players;
  if ($elf == 0) {
    $round++;
    echo "Round ".$round." (".($lastval-$i)." marbles remaining)\n"; // so i can see how close the program is to finishing, ha ha ha
  }
}

echo max($elfscores);
die(1);

Rob Hoelz • Dec 10 '18

I did today's entry in C, both for fun and because writing linked lists just feels natural in C!

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

struct node {
    int64_t value;
    struct node *next;
    struct node *prev;
};

int
main(int argc, char **argv)
{
    int num_players;
    int last_marble;

    int i;
    struct node *current_node;
    struct node *node_pool;
    int current_player;
    int64_t *scores;
    int64_t max_score;

    if(argc < 3) {
        fprintf(stderr, "usage: %s [num players] [high score marble]\n", argv[0]);
        return 1;
    }

    num_players = atoi(argv[1]);
    last_marble = atoi(argv[2]);

    node_pool = malloc(sizeof(struct node) * (last_marble + 1));

    current_node = node_pool++;
    current_node->value = 0;
    current_node->next = current_node;
    current_node->prev = current_node;

    scores = malloc(sizeof(int64_t) * num_players);
    memset(scores, 0, sizeof(int64_t) * num_players);

    current_player = 0;

    for(i = 1; i <= last_marble; i++) {
        if(i % 23 == 0) {
            int j;
            struct node *prev;
            struct node *next;

            for(j = 0; j < 7; j++) {
                current_node = current_node->prev;
            }

            scores[current_player] += i;
            scores[current_player] += current_node->value;

            prev = current_node->prev;
            next = current_node->next;

            prev->next = next;
            next->prev = prev;

            current_node = next;

        } else {
            struct node *new_node;

            current_node = current_node->next;

            new_node = node_pool++;

            new_node->value = i;
            new_node->prev = current_node;
            new_node->next = current_node->next;
            current_node->next->prev = new_node;
            current_node->next = new_node;

            current_node = new_node;
        }

        current_player = (current_player + 1) % num_players;
    }

    max_score = 0;
    for(i = 0; i < num_players; i++) {
        if(scores[i] > max_score) {
            max_score = scores[i];
        }
    }

    printf("%ld\n", max_score);

    return 0;
}

Neil Gall • Dec 9 '18 • Edited

Circular data structures always come up in Advent of Code. You can obviously implement it with a linear array or list and modulo arithmetic but I think I'm going to have some fun with Kotlin today. Let's implement a real circular data structure:

class Circle<T> {
    private var value: T
    private var prev: Circle<T>
    private var next: Circle<T>

    constructor(value: T, prev: Circle<T>? = null, next: Circle<T>? = null) {
        this.value = value
        this.prev = prev ?: this
        this.next = next ?: this
    }
}

An interesting property of this data structure is that a reference to any node is a reference to the whole structure. So we don't need to separately keep track of the overall structure and the current node. Which implies some interesting possible operations on it:

operator fun plus(n: Int): Circle<T> = when {
    n == 0 -> this
    n < 0  -> minus(-n)
    n > 0  -> next.plus(n-1)
}

operator fun minus(n: Int): Circle<T> = when {
    n == 0 -> this
    n < 0  -> plus(-n)
    n > 0  -> prev.minus(n-1)
}

That is we can say circle + 2 to get the node 2 positions clockwise around the circle, or circle - 7 to get the node 7 positions counter-clockwise. It doesn't matter if this loops around one or more times past the starting point as it is a genuinely circular data structure.

The puzzle involves inserting and removing nodes, so let's implement those:

fun insertClockwise(value: T): Circle<T> {
    val node = Circle(value, this, next)
    next.prev = node
    this.next = node
    return node
}

fun insertAnticlockwise(value: T): Circle<T> {
    val node = Circle(value, prev, this)
    prev.next = node
    this.prev = node
    return node
}

fun remove(): Circle<T> {
    if (prev == this && next == this)
        throw IllegalStateException("can't remove the last node in a circle")
    prev.next = next
    next.prev = prev
    return next
}

Simple stuff, hard to get wrong. Just one corner case around removing the last node as we don't have a representation of an empty circle. The game doesn't require it anyway as we always start with the 0 marble.

Finally we need to see the content of the nodes in the circle. Kotlin's subscript syntax makes sense for this:

operator fun get(n: Int): T = when {
    n == 0 -> value
    else   -> plus(n).get(0)
}

When I started implementing the game I realised the players play in a round-robin fashion, and instead of keeping their scores in a Map or Array I could also use a Circle! Insert the correct number of zeros at the start of the game, then just use player += 1 to move to the next player at each step. I also had to add a subscript setter operation analagous to the getter, so the scores could be updated.

One final thing was needed to allow Circle to be used for the players: I had to be able to find the highest score. A simple approach is to allow extraction of a certain number of values:

fun take(n: Int): List<T> = when {
    n == 0 -> listOf()
    n > 0  -> listOf(value) + next.take(n-1)
    n < 0  -> prev.take(n+1) + listOf(value)
}

This data structure made implementing the game really easy:

fun game(marbles: Int, players: Int): Int {
    var circle = Circle(0)
    var player = (2..players).fold(Circle(0)) { c, _ -> c.insertClockwise(0) }

    (1..marbles).fold(Pair(circle, player)) { (circle, player), marble ->
        when {
            marble % 23 == 0 -> {
                player[0] += (marble + circle[-7]).toLong()
                Pair((circle - 7).remove(), player + 1)
            }
            else -> {
                Pair((circle + 1).insertClockwise(marble), player + 1)
            }
        }
    }

    return player.take(players).maxBy { it } ?: throw IllegalStateException()
}

There is likely a numerical solution to this puzzle - there certainly looks like there's some kind of binary pattern in the example - but this data structure is so simple my solution worked for all the test cases and the part 1 problem on first try. I had to up the default JVM heap size and change the score type from Int to Long for part 2 but it's still nothing to a modern computer, even this half-decade old Thinkpad.

Ryan Palo • Dec 10 '18

I found out (seems like a lot of other people did too) that rotating a doubly-linked list is way faster than inserting/removing with indices. Still felt like a boss when my code cranked through seven million possibilities in a few seconds :) Man, I love coding.

/// Day 9: Marble Mania
/// 
/// Figure out the scores of elves playing marbles

use std::collections::VecDeque;

/// Calculate what the highest player's score is
pub fn winning_score(number_of_players: usize, max_points: usize) -> usize {
    let mut marbles: VecDeque<usize> = VecDeque::new();
    let mut players: Vec<usize> = Vec::new();
    for _i in 0..number_of_players {
        players.push(0);
    }

    marbles.push_back(0);
    marbles.push_back(1);

    for i in 2..=max_points {
        if i % 100000 == 0 { println!("{}", i) };  // Speed testing feedback

        if i % 23 == 0 {
            players[i % number_of_players] += i;
            rotate_right(&mut marbles, 7);
            players[i % number_of_players] += marbles.pop_back().unwrap();
            rotate_left(&mut marbles, 1);
        } else {
            rotate_left(&mut marbles, 1);
            marbles.push_back(i);
        }
    }

    *players.iter().max().unwrap()
}

fn rotate_right(list: &mut VecDeque<usize>, times: usize) {
    for _i in 0..times {
        let value = list.pop_back().expect("Empty VecDeque");
        list.push_front(value);
    }
}

fn rotate_left(list: &mut VecDeque<usize>, times: usize) {
    for _i in 0..times {
        let value = list.pop_front().expect("Empty VecDeque");
        list.push_back(value);
    }
}

Ryan Palo • Dec 9 '18

@ben , I just realized that this series is going to be a nice stress-test of your Series dots CSS. 😬

Ben Halpern • Dec 9 '18

It’s true. At some point we’ll have to adjust it so it looks a bit better with many posts, but if it looks a bit goofy for a bit it’s not the end of the world.

View full discussion (16 comments)

DEV Community

AoC Day 9: Marble Mania

Top comments (16)

JavaScript solution

reader.js

09-common.js

09a.js

09b.js

Read next

What Do You Remember about the Early Days of webdev and HTML?

Programmatically displaying nav menu from an array and binding to its url property

What Are the Must-Know Software Architectures?

Have You Ever Gotten A Job through LinkedIn?