 # AoC Day 9: Marble Mania

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. 🎅)

## Discussion  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 n2, 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

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)
point_value = 100*parse(Int, chunks)
return (num_players, point_value)
end

function main()
filename = ARGS  # julia arrays are 1-indexed!
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. Tiago Romero Garcia

## 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.

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

const readLines = (file, onLine) => {
crlfDelay: Infinity
});

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

const readFile = async file => {
const lines = [];
return lines;
}

module.exports = {
};
``````

#### 09-common.js

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

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 = 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 { players, marbles } = parseInput(lines);

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 { players, marbles } = parseInput(lines);

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

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

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

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 =  * 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

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);
\$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

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

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 """

iex> start_values = {0, 1, {[], 0, []}, %{}}
iex> Day09.marble(start_values, {1, 1, 23})
{{, 1, []}, %{}}
iex> Day09.marble(start_values, {2, 2, 23})
{{, 2, }, %{}}
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 ->

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

@doc """

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

@doc """

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({, 1, []})
{[], 0, }
iex> Day09.next({, 2, [1, 3]})
{[2, 0], 1, }
"""
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({, 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

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['prev'] = 0;
\$circle['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";
?>
`````` Carly Ho 🌈

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));
\$lastval = intval(trim(\$argv));

\$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);
\$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;
}
}

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));
\$lastval = intval(trim(\$argv));

\$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);
} 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

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);
return 1;
}

num_players = atoi(argv);
last_marble = atoi(argv);

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

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 += (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

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);
}
}
``````