Day 16

Here we have a sequence of 'dance moves' that reorder the elements of a list. We're given a long sequence of moves and need to come up with the order of the elements after all the moves have been executed.

import string
import pandas as pd
import numpy as np

dance_seq = open('H:/python_jiggering/day16_input.txt').read()
dance_seq = dance_seq.split(',')
dance_seq[:5]

['pa/c', 'x7/9', 's5', 'x15/8', 'pn/j']

dancers = string.ascii_letters[:16]
dancers

'abcdefghijklmnop'

So there are three types of moves here:

• Moving a set from the end to the front
• Exchanging two characters by name
• Exchange two characters by position

Here's a function that can take in the sequence and a move and then spit back the sequence:

def dance(seq, move):
    move_type = move[:1]
    move = move[1:]
    if move_type == 's':
        move = int(move)
        seq = seq[-move:] + seq[:-move]
    elif move_type == 'x':
        # Use a little trick with upper and lower case
        positions = move.split('/')
        left, right = int(positions[0]), int(positions[1])
        left_val, right_val = seq[left], seq[right]
        seq = seq.replace(left_val, right_val.upper()).replace(right_val, left_val.upper())
    elif move_type == 'p':
        positions = move.split('/')
        left_val, right_val = positions[0], positions[1]
        seq = seq.replace(left_val, right_val.upper()).replace(right_val, left_val.upper())
    seq = seq.lower()  
    return(seq)

Now do dance ur butt off

for i in range(len(dance_seq)):
    dancers = dance(dancers, dance_seq[i])
dancers

'padheomkgjfnblic'

Part 2

They basically want me to just iterate this thing one billion times? This isn't really feasible so we have to look for some sort of shortcut. I suspect that there is a cycle within the dance that we can find and then do some arithmetic to figure out where we end up.

I think what we can do is store the position along the sequence and the order of the dancers. When we return to the same position in the dance and same sequence of dancers, we'll have a cycle.

Maybe we can take a more naive approach here and just see if we can find a cycle without worrying about whether the next instructions are the same or not:

dance_list = [string.ascii_letters[:16]]
dancers = string.ascii_letters[:16]
counter = 0
dance_len = len(dance_seq)

while True:
    for i in range(len(dance_seq)):
        dancers = dance(dancers, dance_seq[i])
    dance_list.append(dancers)
    if(len(np.unique(np.array(dance_list))) < len(dance_list)):
        break

print(len(dance_list))
print(dance_list[0])
print(dance_list[-1])

61
abcdefghijklmnop
abcdefghijklmnop

Okay... that was actually incredibly easy. As I'm writing this I've solved almost every puzzle for 2017 and somehow this one took me the longest. I tried a lot of similar things but none were quite this simple. Previously I had been looking for cycles that started part way through one iteration of the dance and ended part way through another.

leftovers = (10**9) % 60
dancers = string.ascii_letters[:16]

for j in range(leftovers):
    for i in range(len(dance_seq)):
        dancers = dance(dancers, dance_seq[i])
dancers

'bfcdeakhijmlgopn'