Sean McLemon | Advent of Code

2017-12-16 - Permutation Promenade

(original .ipynb)

puzzle_input_str = open("puzzle_input/day16.txt").read()


def init_programs(limit):
    curr = ord("a")
    programs = []
    while curr <= ord(limit):
        programs.append(chr(curr))
        curr += 1
    return programs

        
def spin(programs, x):
    new_programs = []
    while x > 0:
        new_programs.insert(0, programs.pop())
        x -= 1
    return new_programs + programs
    

def exchange(programs, a, b):
    new_programs = [c for c in programs]
    a_val = new_programs[a]
    b_val = new_programs[b]
    new_programs[a] = b_val
    new_programs[b] = a_val
    return new_programs


def partner(programs, a, b):
    return exchange(programs, programs.index(a), programs.index(b))


def read_int(sequence, pos):
    ints = []
    
    while pos < len(sequence) and sequence[pos].isdigit():
        ints.append(sequence[pos])
        pos += 1
        
    return int("".join(ints)), pos


def dance(programs, sequences):
    n = 0
    while n < len(sequences):
        sequence = [c for c in sequences[n]]
        command = sequence[0]
        pos = 1
        
        if command == "s":
            x, pos = read_int(sequence, pos)
            programs = spin(programs, x)
        elif command == "x":
            a, pos = read_int(sequence, pos)
            pos += 1 # should be a "/"
            b, pos = read_int(sequence, pos)
            programs = exchange(programs, a, b)
        elif command == "p":
            a = sequence[pos]
            b = sequence[pos+2]
            programs = partner(programs, a, b)
            pos += 3
        else:
            raise Exception(f"unknown command: {command}")
            
        n += 1
        
    return programs
    

def part_one(input_str, limit="p"):
    programs = init_programs(limit)
    sequences = input_str.split(",")
    return "".join(dance(programs, sequences))
    

assert "baedc" == part_one("s1,x3/4,pe/b", "e")
print("part one:", part_one(puzzle_input_str))

part one: ebjpfdgmihonackl

# gonna assume we hit a pattern, and just need to find how frequently it repeats
def part_two(input_str, limit="p"):
    programs = init_programs(limit)
    sequences = input_str.split(",")
    
    iterations = 0
    seen = set([input_str])
    pattern_at_iteration = {0:input_str}
    
    max_iterations = 1_000_000_000
    
    while iterations < max_iterations: # we hopefully won't hit this
        programs = dance(programs, sequences)
        pattern = "".join(programs)
        if pattern in seen:
            return pattern_at_iteration[max_iterations % iterations]
        iterations += 1
        
        seen.add(pattern)
        pattern_at_iteration[iterations] = pattern
        
print("part two:", part_two(puzzle_input_str))

part two: abocefghijklmndp