Scrambled Letters and Hash

Advent of Code 2016 Day 21

Part 1

1. More fun with regular expressions, strings and arrays
2. Analyzing each operation
3. Writing each function
4. Testing manually on the example
5. Using length and conditions to extract each operation's details
6. Testing on the example and my puzzle input

More fun with regular expressions, strings and arrays

• Regular expressions because I need to extract each operation and its specific instructions
• Strings because that's what I'll be moving
• Arrays because that's how I'll be storing each String

Analyzing each operation

The categories are:

• swap
• rotate
• reverse
• move

swap and rotate have two variants:

• swap has position and letter
• rotate has a static amount in one of two directions and a dynamic amount in one direction

Thankfully, I've had lots of practice with these operations in past puzzles.

Still, let's get to writing each function!

Writing each function

1. swap position
2. swap letter
3. rotate right/left
4. rotate based on position
5. reverse
6. move

swap position

swap position X with position Y means that the letters at indexes X and Y (counting from 0) should be swapped.

swapPositions(X,Y) {
  let temp = password[X]
  password[X] = password[Y]
  password[Y] = temp
}

swap letter

swap letter X with letter Y means that the letters X and Y should be swapped (regardless of where they appear in the string).

swapLetters(X,Y) {
  let [Xindex,Yindex] = [
    password.indexOf(X), password.indexOf(Y)
  ]
  password[Xindex] = Y
  password[Yindex] = X
}

rotate right/left

rotate left/right X steps means that the whole string should be rotated

rotateDirection(dir,X) {
  for (let i = 0; i < X; i++) {
    switch (dir) {
      case "right":
        password.unshift(password.pop())
        break;
      case "left":
        password.push(password.shift())
        break;
    }
  }
}

rotate based on position

rotate based on position of letter X means that the whole string should be rotated to the right based on the index of letter X (counting from 0) as determined before this instruction does any rotations. Once the index is determined, rotate the string to the right one time, plus a number of times equal to that index, plus one additional time if the index was at least 4.

rotateBasedOn(X) {
  let position = password.indexOf(X)
  ops.rotateDirection(
    "right", 
    position >= 4 ? position + 2 : position + 1
  )
}

reverse

reverse positions X through Y means that the span of letters at indexes X through Y (including the letters at X and Y) should be reversed in order.

reverse(X,Y) {
  let indices = new Array(Y - X + 1)
    .fill(null)
    .map((item, index) => index + X)
  let newOrder = indices
    .slice()
    .reverse()
    .map(num => password[num])
  indices.forEach((pos, index) => {
    password[pos] = newOrder[index]
  })
}

move

move position X to position Y means that the letter which is at index X should be removed from the string, then inserted such that it ends up at index Y.

move(X,Y) {
  password.splice(Y, 0, password.splice(X, 1)[0])
}

Testing manually on the example

• I haven't written the regular expressions to parse the input
• But I know to which function each operation corresponds
• So, I can test my functions on the example

The example operations are:

swap position 4 with position 0
swap letter d with letter b
reverse positions 0 through 4
rotate left 1 step
move position 1 to position 4
move position 3 to position 0
rotate based on position of letter b
rotate based on position of letter d

Re-written as my functions:

swapPositions(4,0)
swapLetters('d','b')
reverse(0,4)
rotateDirection('left',1)
move(1,4)
move(3,0)
rotateBasedOn('b')
rotateBasedOn('d')

And the results after each step, starting from abcde:

swapPositions(4,0)        -> ebcda - Success!
swapLetters('d','b')      -> edcba - Success!
reverse(0,4)              -> abcde - Success!
rotateDirection('left',1) -> bcdea - Success!
move(1,4)                 -> bdeac - Success!
move(3,0)                 -> abdec - Success!
rotateBasedOn('b')        -> ecabd - Success!
rotateBasedOn('d')        -> decab - Success!

It's nice to know my functions work on the example input.

I hope they'll work on my puzzle input.

But first, I need to parse each operation of the input into the proper function to call with the proper arguments.

Using length and conditions to extract each operation's details

• I wonder, can I leverage the count of each operation's phrases?

1       2         3  4        5        6      7
swap    position  X  with     position Y
swap    letter    X  with     letter   Y
rotate  left      X  steps
rotate  based     on position of       letter X
reverse positions X  through  Y
move    position  X  to       position Y

My observations:

• Only one is 4 phrases: rotate left/right X steps
• Only one is 7 phrases: the other rotate
• Only one is 5 phrases: reverse
• The other three are equal phrases: only one has letter as its second phrase, and only one has move as its first phrase

This sounds like a nested switch statement, or at least a switch statement with an if...else clause in one of its cases.

Let's write it!

input.forEach(line => {
  let parts = line.split(' ')
  switch (parts.length) {
    case 7:
      rotateBasedOn(parts[6])
      break;
    case 4:
      rotateDirection(parts[1], +parts[2])
      break;
    case 5:
      reverse(+parts[2], +parts[4])
      break;
    case 6:
      if (parts[1] == 'letter') {
        swapLetters(parts[2], parts[5])
      } else if (parts[0] == 'move') {
        move(+parts[2], +parts[5])
      } else if (parts[0] == 'swap') {
        swapPositions(+parts[2], +parts[5])
      }
      break;
  }
})

Testing on the example and my puzzle input

• It worked on the example password and list of instructions!
• It worked on my example password and input!

Part 2

1. Is it as simple as...reverse()?
2. Reversing (most) of the things
3. Testing and...failing, again
4. Making and checking hash stamps
5. Understanding the letter-position rotate operation
6. Implementing and testing

Is it as simple as...reverse()?

• Can I just reverse the order of my input instructions...
• ...and process them using my newly assigned scrambled password?

I'll try:

• I ran it
• I got a new password string
• I reset my code to no longer reverse the order
• I ran it again
• I did not get the expected scrambled password

Why not?

• Oh, because I need to reverse the order and direction inherent to each operation!
• Woah, what a fun twist!
• Hopefully this won't be too difficult

Reversing (most) of the things

First, which functions are unaffected?

• swap position X with position Y
• swap letter X with letter Y
• reverse positions X through Y
• move position X to position Y

Next, which functions require an easy switch?

• rotate left/right X steps
• rotate based on position of letter X

For left/right, I just need to swap my cases:

rotateDirection(dir,X) {
  for (let i = 0; i < X; i++) {
    switch (dir) {
      case "left": // was "right"
        password.unshift(password.pop())
        break;
      case "right": // was "left"
        password.push(password.shift())
        break;
    }
  }
}

For based on position, I can leave my function the way it is, since passing right into rotateDirection will now correctly rotate characters left.

Testing and...failing, again

• I ran it on the Part 1 example, and it worked!
• I ran it on my Part 1 string, abcdefgh, and it failed
• I ran it on my Part 2 string in both directions, and it failed

I need to see where the first failure is.

That means I need to store the password at each stage, forward and backward.

Making and checking hash stamps

I'll initialize two lists:

let stamps = [[],[]]

In each Part's algorithm, I'll push the newly-updated password to the end of the respective list:

// In Part 1: scrambling 'abcdefgh`
stamps[0].push(password.join(''))

// In Part 2: unscrambling 'bfheacgd`
stamps[1].push(password.join(''))

I'll know that my Part 2 algorithm is working when the arrays are inversely identical.

For now, I just want to compare the last few passwords in my Part 1 list with the first few passwords in my Part 2 list.

The password immediately before processing the last operation of my puzzle input using the string abcdefgh is:

done:  'bfheacgd'
prior: 'heacgdbf'

The password in the same index - but starting from bfheacgd - is:

start: 'bfheacgd'
next:  not 'heacgdbf'

An error at the last - first? - operation!

What's the operation?

rotate based on position of letter e

Oh boy, that's the super-specific, tricky one.

Makes sense that it is the culprit.

Let's dive deep into what could be happening.

Understanding the letter-position rotate operation

As mentioned above, this operation:

rotate based on position of letter e

causes this change in password:

heacgdbf
bfheacgd

Per the rule:

• Store the location of e: 1
• Rotate the password right at least once
• Then again the amount of times equal to the stored location
• Then once more if the stored location was 4 or more

In the case of e: 1 + 1 = 2

Thus, the string rotates right twice.

Cool! But...

...I need a dependable formula for knowing how many rotations to perform on a password, based on where a letter ends up. Not where it started!

I need to walk through how each letter would move for any given string.

...

That was the funnest revelation of this puzzle!

Implementing and testing

Now I have a legend:

let map = [9,1,6,2,7,3,8,4]

That I can use in my function:

rotateBasedOn(X) {
  let position = password.indexOf(X)
  ops.rotateDirection(
    "right", // corresponds to "left"
    map[position] // evaluates to correct number of steps
  )
}

And with that, I test again:

• It worked on the example input, backward and forward!
• Same for Part 1!
• And for Part 2!

I did it!!

• I solved both parts!
• I successfully broke down how the rotate based on position of letter X worked in order to create a usable legend!
• I made a GIF of how I did it, too!
• And I wrote a bunch of - in my opinion - readable JavaScript that demonstrates several array manipulation methods!

What a delicious, savory, clever puzzle!