Advent of Code 2016 - Day 21

Useful Links

Concepts and Packages Demonstrated

Problem Intro

This puzzle involves scrambling a password based on a series of instructions. We start with an input string and apply a sequence of operations to it.

The operations include:

swap position X with position Y
swap letter X with letter Y
rotate left/right X steps
rotate based on position of letter X
reverse positions X through Y
move position X to position Y

Our input data is a list of these instructions.

Part 1

What is the result of scrambling abcdefgh?

My approach is to create a Scrambler class that encapsulates the logic for each operation. The class will have a method for each type of instruction, and a main scramble method that iterates through the instructions and applies them one by one.

I’ve used regular expressions to parse each instruction and extract the necessary parameters.

Here’s a snippet from the Scrambler class showing the main logic:

class Scrambler:
    # ... (constants for instruction types)
    
    def __init__(self, scramble_input: str) -> None:
        self._scramble_input = scramble_input
        self._scramble_value = self._scramble_input
        
    # ... (property for scramble_value)
    
    def scramble(self, instructions: list):
        for instruction in instructions:
            self._execute_instruction(instruction)
    
    def _execute_instruction(self, instruction:str, reverse=False):
        if instruction.startswith(Scrambler.SWAP_POSITION):
            self.scramble_value = self._swap_position(instruction, self.scramble_value)
        elif instruction.startswith(Scrambler.SWAP_LETTER):
            self.scramble_value = self._swap_letters(instruction, self.scramble_value)
        # ... (other instructions)

Each _swap_..., _rotate_..., etc. method implements the logic for a specific instruction. For example, _swap_position extracts the two positions from the instruction and swaps the characters at those indices.

Part 2

What is the result of unscrambling fbgdceah?

Now we need to reverse the process. This means we need to process the instructions in reverse order and, for some instructions, reverse the operation itself.

swap position and swap letter are their own inverses, so we can use the same logic.
rotate left becomes rotate right and vice-versa.
reverse is its own inverse.
move position X to position Y becomes move position Y to position X.

The trickiest one is rotate based on position of letter X. The rotation amount depends on the index of a letter before the rotation. To reverse this, we can try rotating left one step at a time and, after each rotation, check if performing the original forward rotation on the new string produces our target string. If it does, we’ve found the original unscrambled string.

Here’s the unscramble method and the modified _execute_instruction method:

    def unscramble(self, instructions: list):
        for instruction in reversed(instructions):
            self._execute_instruction(instruction, reverse=True)
    
    def _execute_instruction(self, instruction:str, reverse=False):
        # ... (same as before, but passing the reverse flag)

The reverse flag is then used in methods like _rotate and _move_position to alter their behavior.

For the _rotate_based method, the reverse logic looks like this:

    def _rotate_based(self, instruction: str, src: str, reverse=False) -> str:
        # ... (forward logic)
        if reverse:
            target = src
            new_val = src
            for _ in range(len(src)):
                new_val = self._rotate_left_n(1, new_val)
                if target == self._rotate_based(instruction, new_val):
                    break
            return new_val

Results

Here’s the output of the program:

Part 1 input: abcdefgh
Scramble=gfdhecba

Part 2 input: fbgdceah
Unscramble=dhaegfbc
Execution time: 0.0020 seconds

This puzzle was a nice exercise in string manipulation and thinking about how to reverse operations. The rotate based instruction was a fun little twist!

‹›