Advent of Code: Day 16

For Day 16, the challenge is to rearrange characters according to a given "dance" a billion times and find where they end up. My Python solution is below:

import string
with open("input.txt", "r") as o:
    commands = o.read().split(",")

order = list(string.ascii_lowercase[:16])

def dance(order, commands):
    order = order[:]
    for command in commands:
        if command[0] == "s":
            num = int(command[1:])
            order = order[-num:] + order[:-num]
        elif command[0] == "x":
            c = command[1:].split("/")
            a = int(c[0])
            b = int(c[1])
            order[a], order[b] = order[b], order[a]
        elif command[0] == "p":
            c = command[1:].split("/")
            a = order.index(c[0])
            b = order.index(c[1])
            order[a], order[b] = order[b], order[a]
    return order

print "Part 1", "".join(dance(order, commands))

def part2(order, commands):
    original_order = order

    # Find the smallest cycle
    i = 1
    order = dance(order, commands)
    while not order == original_order:
        i += 1
        order = dance(order, commands)

    # Skip as many cycles as possible
    for i in range(1000000000 % i):
        order = dance(order, commands)
    return order

print "Part 2", "".join(part2(order, commands))

I just brute force it until I find the first cycle - then skip as many as I can before finishing off the billion iterations. I think I could optimize the dance method a little by modifying the list in place rather than making new ones using the substring - but the code would be a lot less clean.

Advent of Code runs every day up to Christmas, you should join in!.

Show Comments

Get the latest posts delivered right to your inbox.