DEV Community

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

Posted on

Elves Look, Elves Say

#adventofcode #algorithms #programming #javascript

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)