Discussion on: AoC Day 9: Marble Mania

View post

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