Elves Look, Elves Say

Advent of Code 2015 Day 10

Part 1

1. What's the best way to count?
2. My first use of Map()?
3. New approach: Walking the line

What's the best way to count?

• I'm well-trained by now to tally the number of times any given character appears in a string
• Often, however, order hasn't mattered
• When it did, I could rely on alphabetical order
• But here, there's no alphabet...and order is very important

Could I still use an object to tally each number?

My first use of Map()?

Per MDN's page:

The Map object holds key-value pairs and remembers the original insertion order of the keys

That's what I want, right?

Using one of the examples:

1211

With Map(), I could build this object:

{ '1': 1 }
{ '1': 1, '2': 1 }
{ '1': 2, '2': 1 }
{ '1': 3, '2': 1 }

And in order, generate a new sequence:

1321

Uh, oh. That's not what I wanted.

I wanted:

1 1 1 2 2 1

Hmm, seems like I need another approach.

New approach: Walking the line

Back to this example:

1211

My algorithm as pseudocode:

Do 40 times
  Set next as an empty string
  Set i as 0
  Do as long as i is less than the length of the sequence
    Set count to 1
    Set j to one more than i
    Do as long as j is less than the length of the sequence and the character at j is the same as the character at i
      Increment count by 1
      Increment j by 1
    Concatenate next with count and the character at i
    Set i to j
  Set sequence to next

Return the length of sequence

My algorithm, animated:

GIF

Running my algorithm 40 times generated the correct answer almost instantly!

Part 2

1. Getting the correct answer...eventually
2. Getting the correct answer much faster

Getting the correct answer...eventually

• I updated 40 to 50
• Re-ran my program
• Waiting several seconds
• Then generated the correct answer!

Getting the correct answer much faster

• I updated my algorithm to use arrays instead of strings
• Re-ran my program
• Waited a second
• Then generated the same correct answer!

My optimized algorithm in JavaScript:

function lookAndSay(digits, times) {
  let sequence = digits.split('')
  for (let times = 0; times < 50; times++) {
    let next = [], i = 0
    while (i < sequence.length) {
      let count = 1, j = i + 1
      while (j < sequence.length && sequence[j] == sequence[i]) {
        count++
        j++
      }
      next.push(count, sequence[i])
      i = j
    }
    sequence = next
  }
  return sequence.length
}
// Part 1
lookAndSay(input, 40)
// Part 2
lookAndSay(input, 50)

I did it!!

• I solved both parts!
• By writing an algorithm...for the first time in a few Days!
• Then writing a faster algorithm that uses arrays instead of strings!
• I learned how mathematically interesting this puzzle's subject matter really is, thanks to the linked video in Part 2!

2015 is turning out to be a really fun year of puzzles so far!