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

Comments

[Mustafa Haddara]

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]

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]

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

[Tiago Romero]

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]

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]

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]

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

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]

Nice find!

[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[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]

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]

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.