Sean McLemon | Advent of Code

2018-12-09 - Marble Mania

(original .ipynb)

class Marble(object):
    def __init__(self, value):
        self.value = value
        self.previous_marble = None
        self.next_marble = None

class MarbleGame(object):
    def __init__(self, players):
        self.players = [0] * players
        
        self.current_value = 0
        self.current_player = 0
        
        # initialize the zero marble
        zero_marble = Marble(self.current_value)
        zero_marble.next_marble = zero_marble
        zero_marble.previous_marble = zero_marble
        
        self.head_marble = zero_marble
        self.current_marble = self.head_marble
        
    def advance_turn(self):
        self.current_player = (self.current_player + 1) % len(self.players)
        self.current_value += 1
        
    def add_marble(self):
        clockwise_one_marble = self.current_marble.next_marble
        clockwise_two_marble = clockwise_one_marble.next_marble
        
        new_marble = Marble(self.current_value + 1)
        
        if new_marble.value % 23 == 0:
            self.add_to_score(new_marble.value)
            self.advance_turn()
            return
        
        # connect clockwise_one_marble and new marble
        clockwise_one_marble.next_marble = new_marble
        new_marble.previous_marble = clockwise_one_marble
        
        # connect new_marble and clockwise_two_marble
        new_marble.next_marble = clockwise_two_marble
        clockwise_two_marble.previous_marble = new_marble
        
        self.current_marble = new_marble
        self.advance_turn()


    def add_to_score(self, marble_value):
        # first add new new marble's value to the new player's score
        self.players[self.current_player] += marble_value
        
        # next find the 7th counter-clockwise marble 
        marble = self.current_marble
        for i in range(7):
            marble = marble.previous_marble

        # then add its value to the player's score
        self.players[self.current_player] += marble.value
        
        # and connect them up
        previous_marble = marble.previous_marble
        next_marble = marble.next_marble
        previous_marble.next_marble = next_marble
        next_marble.previous_marble = previous_marble
        
        # can we delete the marble? it shouldn't have any references so should be GC'd, but it
        # should be safe to do this anyway
        del marble
        
        self.current_marble = next_marble
        
    def dump_marbles(self):
        marbles = [ 0 ]
        marble = self.head_marble.next_marble

        while marble.value != 0:
            marbles.append(marble.value)
            marble = marble.next_marble
            
        print(marbles)
        print(this.current_marble.value)
        

def run_game(players, last_marble):
    game = MarbleGame(players)

    while game.current_value < last_marble:
        game.add_marble()

    return max(game.players)

# test input
assert 32 == run_game(9, 25)
assert 8317 == run_game(10, 1618)
assert 146373 == run_game(13, 7999)
assert 2764 == run_game(17, 1104)
assert 54718 == run_game(21, 6111)
assert 37305 == run_game(30, 5807)

# Part 1
print("part one:", run_game(403, 71920))

# Part 2
print("part two:", run_game(403, 71920 * 100))

part one: 439089
part two: 3668541094