Part 1



In [118]:

    
from tqdm import tqdm



In [119]:

    
nplayers = 493
last_worth = 71863



In [121]:

    
def move(state, pos, worth):
    score = 0
    update = (worth % 23 == 0)
    if update:
        pos = (pos - 7) % len(state)
        score += worth + state[pos]
        state = state[:pos] + state[pos + 1:]
        pos = pos % len(state)
    else:
        if len(state) == 1:
            state, pos = [0, 1], 1
        else:
            pos = (pos + 2) % len(state)
            state = state[:pos] + [worth] + state[pos:]
    worth += 1
    return state, pos, worth, score

def high_score(nplayers, last_worth):
    players = [0 for _ in range(nplayers)]
    state, pos = [0], 0
    worth = pos + 1
    for _ in tqdm(range(1, last_worth + 1)):
        state, pos, worth, score = move(state, pos, worth)
        players[worth % nplayers] += score
    return max(players)

Test

10 players; last marble is worth 1618 points: high score is 8317 13 players; last marble is worth 7999 points: high score is 146373 17 players; last marble is worth 1104 points: high score is 2764 21 players; last marble is worth 6111 points: high score is 54718 30 players; last marble is worth 5807 points: high score is 37305



In [122]:

    
nplayers_list   = [7, 10, 13, 17, 21, 30]
last_worth_list = [25, 1618, 7999, 1104, 6111, 5807]
high_scores     = [32, 8317, 146373, 2764, 54718, 37305]
for i, n in enumerate(nplayers_list):
    assert(high_score(n, last_worth_list[i]) == high_scores[i])









    



100%|██████████| 25/25 [00:00<00:00, 7939.55it/s]
100%|██████████| 1618/1618 [00:00<00:00, 71379.27it/s]
100%|██████████| 7999/7999 [00:00<00:00, 30546.81it/s]
100%|██████████| 1104/1104 [00:00<00:00, 172773.84it/s]
100%|██████████| 6111/6111 [00:00<00:00, 37925.24it/s]
100%|██████████| 5807/5807 [00:00<00:00, 41587.75it/s]

Solution



In [123]:

    
high_score(nplayers, last_worth)









    



100%|██████████| 71863/71863 [00:26<00:00, 2759.35it/s] 






    Out[123]:





367802

Part 2



In [49]:

    
class LinkedNode:
    
    def __init__(self, value):
        self.value  = value
        self.parent = self
        self.child  = self
        
    def link(self, node):
        self.child  = node
        node.parent = self
    
    def insert(self, value):
        node = LinkedNode(value)
        node.link(self.child)
        self.link(node)
    
    def dettach(self):
        self.child.parent = self.parent
        self.parent.child = self.child
    
    def shift(self, n):
        node = self
        if n > 0:
            for _ in range(n):
                node = node.child
        elif n < 0:
            for _ in range(-n):
                node = node.parent
        return node



In [56]:

    
def pull(last_worth):
    pulled_out = []
    node0, node1 = LinkedNode(0), LinkedNode(1)
    node0.link(node1)
    node1.link(node0)
    n = 2
    current = node1
    while n <= last_worth:
        if n % 23 != 0:
            current.child.insert(n)
            current = current.shift(2)
        elif n % 23 == 0:
            current = current.shift(-6)
            pulled_out.append(current.parent.value)
            current.parent.dettach()
        n += 1
    return pulled_out



In [69]:

    
def high_score(nplayers, last_worth):
    pulled = pull(last_worth)
    players = [0 for _ in range(nplayers)]
    i = 1
    while 23 * i <= last_worth:
        players[23 * i % nplayers] += pulled.pop(0) + 23 * i
        i += 1
    return max(players)

Test



In [72]:

    
nplayers_list   = [7, 10, 13, 17, 21, 30]
last_worth_list = [25, 1618, 7999, 1104, 6111, 5807]
high_scores     = [32, 8317, 146373, 2764, 54718, 37305]
for i, n in enumerate(nplayers_list):
    assert(high_score(n, last_worth_list[i]) == high_scores[i])

Solution



In [73]:

    
nplayers = 493
last_worth = 7186300
high_score(nplayers, last_worth)









    Out[73]:





2996043280