Security Through Obscurity

Advent of Code 2016 Day 4

Part 1

1. Bring on the gauntlet!
2. A simple regex to get letters and numbers
3. Preparing the extracted parts
4. Tallying each letter's occurrence in the string
5. The trickiest part: sorting the letters correctly
6. Finishing my working algorithm
7. Testing and celebrating

Bring on the gauntlet!

An outline of my tasks ahead:

• Start with multi-line input as usual
• Reduce to a sum, as is often the case
• Extract the letters and numbers
• Reduce a string to a dictionary of each letter's counts
• Sort the keys by number and alphabetical order
• Keep only the first five keys
• Compare to a string
• If both are equal, add to the sum, otherwise add 0

A simple regex to get letters and numbers

From this string:

aaaaa-bbb-z-y-x-123[abxyz]

I need these:

aaaaa bbb z y x 123 abxyz 

To get them, I just need this:

/\w+/g

• \w matches any word, digit or whitespace
• + matches 1 or more

In essence, it matches and separates each part that isn't a - or [ or ].

Preparing the extracted parts

My regex returns a list of matches full of other metadata.

I just need each matched sub-string.

Using spread and map() I can get what I need:

let parts = [...name.matchAll(/\w+/g)].map(el => el[0])

Now I've got:

['aaaaa','bbb','z','y','x','123','abxyz']

Next, I need to separate the id and checksum:

let [id, checksum] = parts.slice(-2)

• slice(-2) creates an array only the last two items
• I store both items into separate variables using array deconstruction

Lastly, I need one string from the remaining parts:

parts.slice(0,-2).join('')

• slice(0,-2) creates an array with all but the last two items
• join('') concatenates each item together into one string

Tallying each letter's occurrence in the string

For this example:

'aaaaabbbzyx'

I need to create this array:

[ ['a': 5], ['b': 3], ['z': 1], ['y': 1], ['x': 1] ]

My algorithm in JavaScript:

Object.entries(
  parts
    .slice(0,-2)
    .join('')
    .split('')
    .reduce(
      (tallies, letter) => {
        tallies[letter] = (tallies[letter] || 0) + 1
        return tallies
      }, {}
    )
)

• Object.entries() will generate a nested array where each inner array has two items: the letter and the count
• parts.slice(0,-2).join('').split('') creates the string, then splits it into an array of single-character strings
• reduce() generates the dictionary of letters and their counts
• tallies[letter] = (tallies[letter] || 0) + 1 sets as the value for any given letter it's current value - or 0 if there is none yet - then increments it by 1

The trickiest part: sorting the letters correctly

Now that I've got this:

[ ['a': 5], ['b': 3], ['z': 1], ['y': 1], ['x': 1] ]

I really want this:

[ ['a': 5], ['b': 3], ['x': 1], ['y': 1], ['z': 1] ]

Way overthinking it

Create an empty string
Create an index at 0
Do as long as the string's length is less than 5
  If the number associated with the letter in the nested array at the current index is the only instance of that number among all the nested arrays
    Add the letter to the string
  Else
    Create a collection of all nested arrays with that number
    Sort the collection alphabetically by key
    Add the letter of the first item in the sorted collection
    Remove the array with that letter from the original collection

I couldn't get that to work.

But that's ok, because I found a much simpler, eloquent and concise solution!

I just needed sort()

Sort the nested arrays by tally in descending order
If two or more tallies are equal, sort those by letter in alphabetical order

My algorithm in JavaScript:

.sort(
  (a, b) => b[1] - a[1] || (a[0] > b[0] ? 1 : -1)
)

I was shocked when I noticed it worked!

And very delighted!

Finishing my working algorithm

I now have a sorted nested array.

The rest of my chained-method statement looks like this:

parts
// earlier methods
.slice(0,5)
.map(el => el[0])
.join('') ? +id : 0

• slice(0,5) extracts the first five nested arrays
• map(el => el[0]) keeps only the letter from each array
• join('') concatenates the letters into a string
• ? +id : 0 will make sense in a moment

My full algorithm in JavaScript:

return input.reduce((sum, line) => {
  let parts = [...line.matchAll(/\w+/g)].map(el => el[0])
  let [id, checksum] = parts.slice(-2)
  return sum += checksum == Object.entries(
    parts
      .slice(0,-2)
      .join('')
      .split('')
      .reduce(
        (tallies, letter) => {
          tallies[letter] = (tallies[letter] || 0) + 1
          return tallies
        }, {}
      )
    ).sort(
      (a, b) => b[1] - a[1] || (a[0] > b[0] ? 1 : -1)
     )
     .slice(0,5)
     .map(el => el[0])
     .join('') ? +id : 0
}, 0)

The parts I omitted until now:

• sum += checksum == ... ? +id : 0 increments sum by either the number-coerced id string, or by 0, depending on the 5-character string generated by the rest of the algorithm

Testing and celebrating

• It worked on the example strings!
• It worked on my puzzle input!

Part 2

1. Enter: charCodes, modulo and find...!
2. Creating an alphabet array
3. Identifying the correct new letter
4. Find...ing the correct real name

Enter: charCodes, modulo and find...!

• charCodes to generate an array of a-z
• modulo to identify the correct new letter
• find... to manually search for North Pole object storage or something like it

Creating an alphabet array

I need this:

['a', 'b', '...', 'y', 'z']

I could certainly make it manually by typing it out fully.

But I'd rather generate it programmatically.

I need an array with 26 items:

new Array(26)

Where each item is a letter.

But I only really have indices to work with:

new Array(26).fill(null).map((el, index) => //??? )

What can I use that will evaluate to the letters a-z?

charCodes!

'a'.charCodeAt(0) // 97
'b'.charCodeAt(0) // 98
'z'.charCodeAt(0) // 113

And to get the letter mapped to a charCode:

String.fromCharCode(97) // 'a'

Thus, filling in the ??? in my algorithm:

new Array(26).fill(null).map(
  (el, index) => String.fromCharCode(index + 97)
)

Voila! I've got my alphabet array!

Identifying the correct new letter

• Say the letter is b and the id is 40
• b is at index 1 since it is the second letter of the alphabet
• 1 + 40 = 41
• 41 % 26 = 15
• The real letter is at index 15: p

When codified as an algorithm, the steps above are accomplished for any given letter in this single line:

alphabet[(alphabet.indexOf(letter) + id) % alphabet.length]

My full algorithm in JavaScript:

input.forEach(line => {
  let parts = [...line.matchAll(/\w+/g)].map(el => el[0])
  let [id, checksum] = parts.slice(-2)
  let alphabet = new Array(26).fill(null).map(
    (el, index) => String.fromCharCode(i + 97)
  )
  console.log(
    parts
      .slice(0,-2)
      .join('-')
      .split('')
      .map(letter => {
        return letter == '-' ? ' ' : 
        alphabet[
          (alphabet.indexOf(letter) + +id) % alphabet.length
        ]
      })
      .join(''), id
  )
})

Find...ing the correct real name

With my full algorithm in JavaScript complete, it was time to browse the real names for references to storage.

colorful egg storage
radioactive flower storage
magnetic fuzzy dye storage
weaponized basket storage
classified radioactive scavenger hunt storage
cryogenic scavenger hunt storage
fuzzy bunny storage
northpole object storage

That last one was it!

I submitted the numeric ID, and it was the correct answer!

I did it!!

• I solved both parts!
• I practiced a bunch of fundamental programming techniques!
• I wrote detailed explanations in hopes they help future beginner programmers feel more comfortable with JavaScript!