DEV Community

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

Posted on

1

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!

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay