2020-12-23 - Crab Cups
(original .ipynb)
Day 23 input is 9 digit string representing the arrangement of 9 cups in a circle, labelled 1-9 (mine is 364289715). Part 1 involves applying a given shuffle of these cups 100 times. Part 2 involves increasing the cups (to 1 million, each cup after the initial 9 is just labelled after the place in the initial configuration it is, so the 10th cup is 10, the 11th cup is 11, etc) and applying the shuffle 10 million times.
NOTE: My solution is horrendously inefficient and Part 2 does not complete in a reasonable time. To get my answer I ran it locally with pypy, tweaked a few bits and then ran it overnight. :-/ there is definitely a faster way to get this. Another one for the "revisit" queue.
test_input_str = "389125467"
puzzle_input_str = "364289715"
# IMMEDIATE THOUGHT: this problem is not TOO tough but it involves manually following some number-shuffling
# and repetition over a small number of iterations (100). I can GUARANTEE that Part 2
# involves doing this over an impossible number of iterations
# The crab picks up the three cups that are immediately clockwise of the current cup. They are removed
# from the circle; cup spacing is adjusted as necessary to maintain the circle.
#
# The crab selects a destination cup: the cup with a label equal to the current cup's label minus one.
# If this would select one of the cups that was just picked up, the crab will keep subtracting one
# until it finds a cup that wasn't just picked up. If at any point in this process the value goes
# below the lowest value on any cup's label, it wraps around to the highest value on any cup's label instead.
#
# The crab places the cups it just picked up so that they are immediately clockwise of the destination cup.
# They keep the same order as when they were picked up.
#
# The crab selects a new current cup: the cup which is immediately clockwise of the current cup.
def circular_pop(cups, pop_index):
if (pop_index > len(cups)-1):
pop_index = 0
return cups.pop(pop_index)
def circular_get(cups, index):
return cups[index % len(cups)]
def insert_cups(cups, index, move_cups):
adjusted_index = index % (1+len(cups))
#print("inserting", move_cups, "into index", adjusted_index, "(where", cups[adjusted_index], "is)")
while move_cups:
cups.insert(adjusted_index, move_cups.pop())
def decrement_label(label, max_label):
label -= 1
if label == 0:
label = max_label
return label
def solve(input_str, moves, pad_input_to=None):
cups = [int(s) for s in input_str]
max_label = len(cups)
current_index = 0
if pad_input_to:
print("range", len(cups), 1+pad_input_to)
cups += [n for n in range(len(cups), 1+pad_input_to)]
print(cups[-1])
while moves > 0:
if moves % 10000 == 0:
print("moves", moves)
current_cup = cups[current_index]
pick_up = [circular_pop(cups, current_index + 1) for cup in range(3)]
destination_label = decrement_label(current_cup, max_label)
while destination_label in pick_up:
destination_label = decrement_label(destination_label, max_label)
destination_index = (1 + cups.index(destination_label)) % len(cups)
insert_cups(cups, destination_index, pick_up)
current_index = (cups.index(current_cup) + 1) % len(cups)
moves -= 1
pivot_index = cups.index(1) + 1
if pad_input_to:
print(pivot_index, pivot_index+1)
print(cups[pivot_index-1], cups[pivot_index], cups[pivot_index+1], cups[pivot_index]*cups[pivot_index+1])
return ""
return "".join([str(s) for s in cups[pivot_index:] + cups[:pivot_index]])[:-1]
assert "92658374" == solve(test_input_str, 10)
assert "67384529" == solve(test_input_str, 100)
print(solve(puzzle_input_str, 100))
98645732
#print(solve(puzzle_input_str, 10_000_000, 1_000_000))
#print(solve("389125467", 1000, 1_000_000))
print(solve(test_input_str, 10_000_000, 1_000_000)) #5396
#[c for c in range(1+9,20)]
range 9 1000001 1000000 moves 10000000 moves 9990000 moves 9980000 moves 9970000