DEV Community

Cover image for Elves Look, Elves Say
Robert Mion
Robert Mion

Posted on

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
Enter fullscreen mode Exit fullscreen mode

With Map(), I could build this object:

{ '1': 1 }
{ '1': 1, '2': 1 }
{ '1': 2, '2': 1 }
{ '1': 3, '2': 1 }
Enter fullscreen mode Exit fullscreen mode

And in order, generate a new sequence:

1321
Enter fullscreen mode Exit fullscreen mode

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

I wanted:

1 1 1 2 2 1
Enter fullscreen mode Exit fullscreen mode

Hmm, seems like I need another approach.

New approach: Walking the line

Back to this example:

1211
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

My algorithm, animated:
Animation of my algorithm

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)
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)