DEV Community

Cover image for Secure Container
Robert Mion
Robert Mion

Posted on

Secure Container

Advent of Code 2019 Day 4

Task: Solve for X where...

X = the number of valid passwords
Enter fullscreen mode Exit fullscreen mode

Example input

Only sample passwords are given:

122345
111123
135679
111111
223450
123789
Enter fullscreen mode Exit fullscreen mode

The puzzle input is in the form:

Number-Number
Enter fullscreen mode Exit fullscreen mode

It represents:

  • The lower-upper bounding numbers for a range of integers

Part 1

  1. Sub-routine: Check for increasing numbers
  2. Sub-routine: Check for identical adjacent digits
  3. Works, but slow: Check every number in the range
  4. 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
Enter fullscreen mode Exit fullscreen mode

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

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

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

String
'111123'

As list
['1','1','1','1','2','3']

As sorted list
['1','1','1','1','2','3']

Equal: True
Enter fullscreen mode Exit fullscreen mode

Sub-routine: Check for identical adjacent digits

As one of the rules states:

Two adjacent digits are the same (like 22 in 122345)
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

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

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

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

Part 2

  1. A regular expression that finds two or more adjacent identical digits
  2. 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
Enter fullscreen mode Exit fullscreen mode

After a lot of trial and error and fiddling around with Regexr.com, I created a usable RegEx:

/(\d)\1+/g
Enter fullscreen mode Exit fullscreen mode

It matches:

  • One digit between 0-9
  • That same digit one or more times

Here, it finds three matches:

112233
Enter fullscreen mode Exit fullscreen mode

Here, it finds one:

123444
Enter fullscreen mode Exit fullscreen mode

Here, it finds two:

111122
Enter fullscreen mode Exit fullscreen mode

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

Those examples again:

112233 -> 3 of length 2: VALID
123444 -> 0 of length 2: INVALID
111122 -> 1 of length 2: VALID
Enter fullscreen mode Exit fullscreen mode

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

Two major accomplishments

  1. Optimizing my algorithm to only run on non-decreasing numbers
  2. Discovering a regular expression that unlocked the correct answer to Part 2

Top comments (0)