Permutation Promenade

Advent of Code 2017 Day 16

Try the simulator to watch one dance round using your puzzle input!

Part 1

1. Dancing arrays? Count me in!
2. Parsing each array mutation instruction
3. Writing each mutation instruction function
4. Executing each instruction
5. Testing the results

Dancing arrays? Count me in!

• What a fun challenge about in-place array mutation
• For the first time, the video referenced is a hoot!

Alright, let's get to the first task: regular expressions!

Parsing each array mutation instruction

The three patterns to match are:

• s followed by a 1- or 2-digit integer
• x followed by an integer, then a /, then another integer
• p followed by a letter, then a /, then another letter

Therefore, the / and second integer are optional.

My regular expression looks like this:

/(\w)([\d|\w]+)\/?([\d|\w]*)/g

• \w a letter
• [\d|\w]+ either a number or letter, 1 or more times
• \/? an optional /
• [\d|\w]* either a number or letter, 0 or more times

Using that expression, I capture:

s15
s, 15, empty

pg/b
p, g, b

x7/14
x, 7, 14

I'll need to do some damage control to ensure I account for the empty capture group in the s instruction.

A matchAll(), slice() and switch statement later...

With the example input of:

s1,x3/4,pe/b

My algorithm generates this list of instructions:

[ [ 's', 1 ], [ 'x', 3, 4 ], [ 'p', 'e', 'b' ] ]

Perfect!

Writing each mutation instruction function

I'll use a dictionary where:

• Keys are the letters designating each function
• Values are the function that does the in-place array mutation

It resembles this:

const moves = {
  s(X) {
    ...
  },
  x(X,Y) {
    ...
  },
  p(X,Y) {
    ...
  }
}

Spin

I use a combination of slice(), concat() and reversing the sign of the argument to start from the end of the list:

s(X) {
  programs = programs.slice(-X).concat(programs.slice(0,-X))
}

Exchange

I mimic the traditional means of swapping two values - using a temporary variable:

x(X,Y) {
  let temp = programs[X]
  programs[X] = programs[Y]
  programs[Y] = temp
}

Partner

I do almost the same as in Exchange, but I create two additional variables to store the target indices

p(X,Y) {
  let [x,y] = [programs.indexOf(X),programs.indexOf(Y)]
  let temp = programs[x]
  programs[x] = programs[y]
  programs[y] = temp
}

Executing each instruction

For each instruction
  If the first element is an 's'
    Call the appropriate moves function, passing the second element as the sole argument
  Else
    Call the appropriate moves function, passing the second and third elements as arguments

Testing my results

• Example input: Success!
• My puzzle input: Success!

Part 2

1. A pattern-recognition test
2. Extrapolating to 1 billion
3. A puzzle left unsolved
4. Just kidding: solved!

A pattern-recognition test

• My puzzle input includes 10,000 instructions
• Those instructions form a single dance
• I need to extrapolate 1 billion dances
• And find the order of the letters at that exact moment

I think to myself:

• How often do arrangements of letters repeat?

After some play-time using Set()s, storing tallies in dictionaries, and logging each time a specific letter arrangement appeared again, I discovered a magic number.

560,000

That seems to be the number of instructions between each arrangement's next appearance.

Extrapolating to 1 billion

• Initially, I misunderstood the instructions
• I thought each instruction was a dance

Thus, my equation was to solve for X where X =:
1000000000 - (560000 * X) = a number > 0 and < 560000

In that equation, X = 1785 and the number is 400000

I understood that as:

• The letter arrangements after 400000 instructions were the same as the letter arrangements after 1 billion instructions

I was wrong.

I tried the letter arrangements after 400001 just in case I was off by one.

I was wrong.

• I re-read the instructions
• Now I saw that each round of instructions was a dance

Thus, my equation was to solve for X where X =:
10000000000000 - (560000 * X) = a number > 0 and < 560000

In that equation, X = 17857142 and the number is 480000

I understood that as:

• The letter arrangements after 480000 instructions were the same as the letter arrangements after 1 billion instructions

I was wrong.

I tried the letter arrangements after 480001 just in case I was off by one.

I was wrong.

A puzzle left unsolved

• I'm likely misinterpreting the arithmetic somewhere
• Bummer. But, it's time to move on.

Just kidding: solved!

• I was off by one in the other direction: 479999!

I did it!!

• I solved both parts!
• I got some good practice with regular expressions and in-place array manipulation!
• I built a simulator to visualize one round of dance!
• I found the magic number and equation that unlocked an equation to solve Part 2!