Scrambled Letters and Hash
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-08-16 14:08:18

## [Advent of Code 2016 Day 21](https://adventofcode.com/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.

```js
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).

```js
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

```js
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.

```js
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.

```js
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.

```js
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 `case`s.

Let's write it!

```js
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 `case`s:
```js
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!
![Discovering how rotate works](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kb2n2s5pyfmrvd5lmif7.gif)

### 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:
```js
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!