DEV Community

Discussion on: AoC Day 9: Marble Mania

Collapse
 
jenovs profile image
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";
?>
Collapse
 
rpalo profile image
Ryan Palo

Nice find!