Advent of Code 2019 Day 4
Task: Solve for X where...
X = the number of valid passwords
Example input
Only sample passwords are given:
122345
111123
135679
111111
223450
123789
The puzzle input is in the form:
Number-Number
It represents:
- The lower-upper bounding numbers for a range of integers
Part 1
- Sub-routine: Check for increasing numbers
- Sub-routine: Check for identical adjacent digits
- Works, but slow: Check every number in the range
- Works, but faster: Check only as many numbers as needed
Sub-routine: Check for increasing numbers
As one of the rules states:
Going from left to right, the digits never decrease; they only ever increase or stay the same
I interpret that as:
A number whose digits only increase or stay the same is one in which:
If you were to make a list from each character in order from left to right
And compare that list
With a list of the same values, but sorted in ascending order
Then both lists would match
Written as an algorithm:
Coerce the integer to a string
Split the string into a list of characters maintaining the same order as in the integer
Copy the list and sort it in ascending order
Compare both lists and check whether any digits are not in the same order
Return true if all digits are in the same order in both lists
Two illustrated examples:
Integer
223450
String
'223450'
As list
['2','2','3','4','5','0']
As sorted list
['0','2','2','3','4','5']
Not equal: False
Integer
111123
String
'111123'
As list
['1','1','1','1','2','3']
As sorted list
['1','1','1','1','2','3']
Equal: True
Sub-routine: Check for identical adjacent digits
As one of the rules states:
Two adjacent digits are the same (like 22 in 122345)
I interpret that as:
Start by assuming there are no repeat digits
Check each digit except the first one
Compare the current digit to the prior one
If the prior digit is the same as the current digit
Rule fulfilled
Stop the search
Return whether a repeat digit was found or not
Written as an algorithm:
Set a flag as false
For i from the second digit to the last
If the digit at position i is equal to the digit at position i - 1
Update flag to true
Break
An illustrated example:
Integer
122345
As a list of digits
[1,2,2,3,4,5]
Starting at location 2
[1,2,2,3,4,5]
*
Check the prior digit
[1,2,2,3,4,5]
? *
Not equal, continue
[1,2,2,3,4,5]
*
Check the prior digit
[1,2,2,3,4,5]
? *
Equal: Return true
Works, but slow: Check every number in the range
- My puzzle input range spans about 400,000 numbers
- Checking each one shouldn't take long
A written description of my working algorithm
Extract the lower and upper bounding integers
Set a tally at 0
Starting from the lower
Do as long as the current number is not greater than the upper bounding integer
Increment the tally by 1 if:
The number features digits that are the same or increasing in value from left to right
And the number features at least two adjacent identical digits
Increment the number by 1
Works, but faster: Check only as many numbers as needed
For a number like 223450, the next non-decreasing number is 223455 - a difference of 5.
Five iterations are therefore knowingly wasted.
For a number like 108457, the next non-decreasing number is 111111 - a difference of 2654.
That's significantly more wasted iterations.
For a number like 500000, the next non-decreasing number is 555555 - a difference of 55555.
That's exponentially more wasted iterations.
There's a pattern here that can help immediately skip wasted iterations for any decreasing number:
Knowing the number is decreasing
Create a placeholder for the next non-decreasing number
Check each digit except the first one
Compare the current digit to the prior one
If the current digit is greater than the prior one
Create a new number containing all digits up to but not including the current digit, followed by as many digits equal to the prior one as needed so that the result digit is as long as the original number
Return the new number
An illustrated example:
Integer
108457
As a list of digits
[1,0,8,4,5,7]
Starting at location 2
[1,0,8,4,5,7]
*
Check the prior digit
[1,0,8,4,5,7]
? <
Less than prior digit! Time to skip numbers!
Keep all digits before < digit
[1]
Join to become a string
'1'
Pad the end with that digit, repeating enough times to become a 6-digit number
Return new number
111111
A written description of my working algorithm
Extract the lower and upper bounding integers
Set a tally at 0
Starting from the lower
Do as long as the current number is not greater than the upper bounding integer
Increment the tally by 1 if:
The number features at least two adjacent identical digits
Increment the number by 1
If the number is a decreasing number
Update it to the next non-decreasing number
Part 2
- A regular expression that finds two or more adjacent identical digits
- A working algorithm
A regular expression that finds two or more adjacent identical digits
As the new rule states:
Contain two adjacent matching digits that are not part of a larger group of matching digits
After a lot of trial and error and fiddling around with Regexr.com, I created a usable RegEx:
/(\d)\1+/g
It matches:
- One digit between 0-9
- That same digit one or more times
Here, it finds three matches:
112233
Here, it finds one:
123444
Here, it finds two:
111122
Only the first and third of those three are valid passwords.
Thus, the final check I must do is:
Check if the list of matches includes any of length two
Those examples again:
112233 -> 3 of length 2: VALID
123444 -> 0 of length 2: INVALID
111122 -> 1 of length 2: VALID
A working algorithm
Extract the lower and upper bounding integers
Set a tally at 0
Starting from the lower
Do as long as the current number is not greater than the upper bounding integer
Increment the tally by 1 if:
There is at least one match containing exactly two of the same digit from the list of matches derived from testing the number using the regular expression
Increment the number by 1
If the number is a decreasing number
Update it to the next non-decreasing number
Two major accomplishments
- Optimizing my algorithm to only run on non-decreasing numbers
- Discovering a regular expression that unlocked the correct answer to Part 2
Top comments (0)