Dragon Checksum

Advent of Code 2016 Day 16

Part 1

1. I fear for Part 2
2. Personal challenge: code golf

I fear for Part 2

Why? Because Part 1 seems straightforward and easy.

• One loop to generate a long string
• Another loop to halve it until its length is odd

And the length is a number in the hundreds.

Part 2's length could be in the millions or billions!

Personal challenge: code golf

Code golf: do it in as few lines as possible.

Generate a long enough string:

Set a to the puzzle input string
Do as long as the string's length is less than the amount specified
  Set b to a
    Split b at each character into an array
      Reverse the array
        For each character in the array
          Return the result of subtracting the number from 1
    Concatenate each character into a string
  Set a to the concatenation of a, 0, b
Extract only the first subset of characters matching the specified length

Halve the string until its length is odd:

Set checksum as an empty string
Do as long as the extracted string's length is even
  For i from 0 to the extracted string's length, incrementing by 2 each iteration
    If the the numbers at i and i + 1 are equal
      Concatenate checksum with 1
    Else
      Concatenate checksum with 0
Return checksum

My JavaScript, which I'd rate as a par for its length:

const part1 = (input, length) => {
  while (input.length < length) {
    input += "0" + input.split('').reverse().map(el => 1 - +el).join('')
  }
  input = input.slice(0, length)
  while (input.length % 2 !== 1) {
    let checksum = ""
    for (let i = 0; i < input.length; i += 2) {
      checksum += +input[i] == +input[i + 1] ? "1" : "0"
    }
    input = checksum
  }
  return input
}

Good news:

• It generates the correct answer for the example inputs and my puzzle input!

Bad news:

• I still fear that it could not handle disk lengths in the millions

Part 2

1. As expected, a performance test
2. What are my options?
3. Checksum loop: from strings to arrays for a speed boost
4. Dragon curve: from strings to arrays
5. Strings and arrays for a speed boost
6. Only arrays for a speed boost
7. splice() for a final speed boost
8. Comparing Part 1 and Part 2 Round 5 algorithms

As expected, a performance test

Can my algorithm handle disk lengths in the tens of millions?

...

Nope. It crushes under the pressure.

Well, the second part does.

After several seconds, it can generate a string of the required length.

Sadly, the first attempt it makes at halving that string causes the program to crash.

What are my options?

• Give up and celebrate earning one gold star. Psh. Not yet.
• Use arrays instead of strings...hoping that will speed things up
• Attempt to identify some pattern in the dragon curve or checksum process that will unlock a shortcut to the correct answer

I opt for refactoring my code to use arrays.

Checksum loop: from strings to arrays for a speed boost

In my current algorithm, I am repeatedly creating a string - one longer than the next - starting from an empty string.

The first time I do this using the disk length of 30M+, I am creating 30M+ strings, each string one longer than the previous!

That means that by the time I've got a string 30M in length, I'm immediately overwriting it with a string 30M...and 1 in length.

That feels silly!

Instead, I'll start with an array that is my known ending length in that iteration, and gradually fill it with the correct values.

How my new algorithm works:

Prior to starting the checksum loop:
  Extract only the first subset of characters matching the specified length
    Split the string into an array of characters
      Coerce each character to a number

The checksum loop:
  Set checksum as an array with length equal to half that of the incoming array
  Do as long as the initial/halved array's length is even
    For i from 0 to the array's length, incrementing by 2 each iteration, and index from 0, incrementing by 1 each iteration
      If the the numbers at i and i + 1 are equal
        Store 1 as the value at index in checksum
      Else
        Store 0 as the value at index in checksum
Return a string of the concatenated numbers in checksum

My JavaScript:

const part2 = (input, length) => {
  while (input.length < length) {
    input += "0" + input.split('').reverse().map(el => 1 - +el).join('')
  }
  input = input.slice(0, length).split('').map(Number)
  while (input.length % 2 !== 1) {
    let checksum = new Array(input.length / 2)
    for (let i = 0, index = 0; i < input.length; i += 2, index++) {
      checksum[index] = input[i] == input[i + 1] ? 1 : 0
    }
    input = checksum
  }
  return input.join('')
}

Did that work?

• When running it, there is still a several-second delay before the string to be checksum'd is generated
• But almost immediately after that, the correct answer is generated!

It worked!

But I feel like it could work even faster!

Dragon curve: from strings to arrays

• I want to make the first phase take less time to compute
• That means optimizing the dragon curve generation portion
• Since converting the checksum portion from using strings to arrays made it faster, perhaps doing the same for this portion will have the same effect

In my current algorithm, the same silliness mentioned earlier is happening:

• My while loop is creating and destroying strings of length one greater than the previous length
• I instead should seek to create and populate a single array each iteration

What if I try this:

Split the input string into an array of strings
  Coerce each string to a number

Do as long as the length of the array of numbers is less than the amount specified
  Create an array with length double and one greater than the current array
    For each item in the array, with i as the current index
      If i is less than the middle index of the array
        Set the value as the value in the same index of the smaller, original array
      Else, if i is equal to the middle index
        Set the value to 0
      Else, if i is greater than the middle index
        Set the value as the value in the smaller array equal to the difference of the middle index, 1, and i
  Re-assign the smaller array pointer to the newly filled in array

Spoiler alert:

• I used map() to achieve the For loop in the pseudocode above.
• map() creates a copy of an array.
• I'll realize soon why doing this is antithetic to my goal

Did this work?

• Nope
• Worse, my program terminated before it could generate an answer
• I must be doing something wrong

Strings and arrays for a speed boost

Perhaps it's foolish to create an array of which half the values I have already placed.

Instead, maybe I should leverage my smaller accumulated string and just generate an array for the cloned, reversed part. Then concatenate them together.

What if I try this:

Do as long as the length of the input/accumulated string is less than the amount specified
  Create an array the same length as the string
  For i counting down from one less than the length
  and j counting up from 0 toward the length
    Set the value at j in new array to the numeric value subtracted from 1 at i in the original string
  Concatenate together the original string with '0' and with the concatenated version of the new array

Did this work, and make things seem a bit faster?

• Yup!

However, I still am not happy with parts of its performance:

• The last few iterations of the loop are noticeably, progressively slower
• The part where I slice off the unneeded numbers is also very slow

What are my options still?

• I'm still using a string. Could I try again to only ever use arrays?
• Is slice() the best method for attaining an array of the the exact disk length needed?

Only arrays for a speed boost

• I saw a performance boost when building an array for only the cloned portion of the string
• Maybe I'll see one if I leverage an array instead of a string for both parts

What if I try this:

Split the input string into an array of strings
  Coerce each string to a number

Do as long as the length of the array of numbers is less than the amount specified
  Create an array the same length as the array from the recent iteration
  For i counting down from one less than the length
  and j counting up from 0 toward the length
    Set the value at j in new array to the numeric value subtracted from 1 at i in the original string
  Concatenate together the recent array and an array containing 0 and the array just now created

Did this work, and make things seem a bit faster?

• Yup!

However, I still am not happy with one part of its performance:

• The part where I slice off the unneeded numbers is also very slow

splice() for a final speed boost

• slice() creates a copy of an array where only a subset is included
• splice() modifies an array

I want to modify my 30M+-element array, removing only approximately a million items from the end.

Thankfully, this is an easy change in JavaScript.

Thus far, I've used:

list = list.slice(0, disk_usage_length)

Using splice() instead:

list.splice(disk_usage_length)

Why one argument?

• The first argument is the index from which to start adding/deleting
• If no other argument is supplied, splice() will delete all remaining values in the array

Did this work, and make things seem a bit faster?

• Yup!

Comparing Part 1 and Part 2 Round 5 algorithms

Part 1's algorithm created string after string after string:

const part1 = (input, length) => {
  while (input.length < length) {
    input += "0" + input.split('').reverse().map(el => 1 - +el).join('')
  }
  input = input.slice(0, length)
  while (input.length % 2 !== 1) {
    let checksum = ""
    for (let i = 0; i < input.length; i += 2) {
      checksum += +input[i] == +input[i + 1] ? "1" : "0"
    }
    input = checksum
  }
  return input
}

Part 2 Round 5's algorithm creates as few arrays as possible, joins them together, and modifies instead of copying:

const part2 = (input, length) => {
  let answer = input.split('').map(Number)
  while (answer.length < length) {
    let reversedClone = new Array(answer.length)
    for (var i = answer.length - 1, j = 0; i >= 0; i--, j++) {
        reversedClone[j] = 1 - answer[i]
    }
    answer = answer.concat([0,...reversedClone])
  }
  answer.splice(length)
  while (answer.length % 2 !== 1) {
    let checksum = new Array(answer.length / 2)
    for (let i = 0, index = 0; i < answer.length; i += 2, index++) {
      checksum[index] = answer[i] == answer[i + 1] ? 1 : 0
    }
    answer = checksum
  }
  return answer.join('')
}

I did it!!

• I solved both parts!
• I refactored my Part 1 algorithm to not only be capable of finishing and generating the correct answer for Part 2, but running in under five seconds instead of what felt like close to a minute!
• I was reminded of - and learned more about - the performance of arrays as compared to strings, and methods like map(), concat(), slice() and splice()

I guessed correctly that Part 2 would be a performance test.

What surprised me was how much knowledge I ultimately extracted from this puzzle...even after I solved Part 2 the first time!