Secure Container
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-23 01:06:45

## [Advent of Code 2019 Day 4](https://adventofcode.com/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
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
```

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
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
```

After a lot of trial and error and fiddling around with [Regexr.com](https://regexr.com/), I created a usable RegEx:
```js
/(\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
1. Optimizing my algorithm to only run on non-decreasing numbers
2. Discovering a regular expression that unlocked the correct answer to Part 2