Advent of Code 2015 Day 10
Part 1
- What's the best way to count?
- My first use of
Map()
? - 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
Running my algorithm 40 times generated the correct answer almost instantly!
Part 2
- Getting the correct answer...eventually
- Getting the correct answer much faster
Getting the correct answer...eventually
- I updated
40
to50
- 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!
Top comments (0)