day-4

Solution in Python for the day 4 puzzle of the 2019 edition of the Advent of Code annual programming challenge.

🎄🌟🌟 Secure Container 🎄🌟🌟

🔍📖 Annotated Statements

You arrive at the Venus fuel depot only to discover it's protected by a password. The Elves had written the password on a sticky note, but someone threw it out.

No luck!

However, they do remember a few key facts about the password:

It is a six-digit number.
The value is within the range given in your puzzle input.
Two adjacent digits are the same (like 22 in 122345).
Going from left to right, the digits never decrease; they only ever increase or stay the same (like 111123 or 135679).                                                                                  

Six digits numbers can still individually evaluated without requiring too much CPU time.

Other than the range rule, the following are true:

111111 meets these criteria (double 11, never decreases).
223450 does not meet these criteria (decreasing pair of digits 50).
123789 does not meet these criteria (no double).

Understood.

How many different passwords within the range given in your puzzle input meet these criteria?

Your puzzle input is 168630-718098.

Iterating it is!

📃➡ Input Contents Format

The input is only 13 characters long, meaning that input contents can be passed directly through the command line instead of relying on a file.

$ ./day_4.py 168630-718098

⚙🚀 Implementation

💾🔍 Content Decoding

The solving method is likely to process the numbers by doing a per-digit processing, meaning that a list of digits is expected to be more convenient than a simple integer containing all the digits.

def decode(argument: str) -> tuple[list[int], ...]:
    char_lists = map(list, argument.split('-'))
    range_ = tuple(list(map(int, clist)) for clist in char_lists)
    return range_

📝 Note

This method could be avoided by hard-coding the input 168630-718098 directly into the solve() method. However, this would be no fun and sometimes I an in the mood of taking the long way home.

💡🙋 Puzzle Solving

For the fun lets use a depth-first recursion. The goal is to repeat the following operations:

1. Test if the two last digits are in descending order (i.e digits[-1] < digits[-2]), if True return zero.
2. Test if all digits are present, if True then
   1. Test if two or more adjacent digits are the same (see note below), if True return 1 since the corresponding password is valid. Oppositely return zero.
3. Not all digits are present, we compute lower and upper ranges.
4. Loop over all ten digits
   1. Append this digit to the digits computed in parent.
   2. Expedite iteration (i.e continue iterating) if the obtained value is out of the range.
   3. If the obtained is in range than call recursively the function, accumulate the result.
5. Return the accumulated value.

📝 Note

Since digits are equal or increasing the further to the right, if two digits are identical they must be adjacent, thus this test is implemented simply by comparing lengths of the list against length of the set.

def count_pwd(range_: tuple[list[int], ...],
              digits: list[int], length: int) -> int:
    digit_index = len(digits)
    decreasing_digit = digit_index >= 2 and digits[-1] < digits[-2]
    if decreasing_digit:
        return 0
    stop = digit_index == length
    if stop:
        same_adjacent_digits = len(set(digits)) < len(digits)
        return 1 if same_adjacent_digits else 0
    min_digits = range_[0][:1+digit_index]
    max_digits = range_[1][:1+digit_index]
    pwd_count = 0
    for next_digit in range(10):
        next_digits = digits.copy()
        next_digits.append(next_digit)
        if not min_digits <= next_digits <= max_digits:
            continue
        pwd_count += count_pwd(
            range_=range_, digits=next_digits, length=length)
    return pwd_count

Contents	Answer
168630-718098	1686

😰🙅 Part Two

🥺👉👈 Annotated Description

An Elf just remembered one more important detail: the two adjacent matching digits are not part of a larger group of matching digits.

This means that adjacent matching digits must be of even length. This means that one out more group of adjacent digits is exactly two chars wide.

Given this additional criterion, but still ignoring the range rule, the following are now true:

112233 meets these criteria because the digits never decrease and all repeated digits are exactly two digits long.
123444 no longer meets the criteria (the repeated 44 is part of a larger group of 444).
111122 meets the criteria (even though 1 is repeated more than twice, it still contains a double 22).

Understood.

How many different passwords within the range given in your puzzle input meet all of the criteria?

Same logic for computing the answer.

🤔🤯 Solver Implementation

A first solution consists in relying on a Counter() object and check once all the digits are computed that there is at least one digit which is encountered two times.

if stop:
    same_adjacent_digits = len(set(digits)) < len(digits)
    if not same_adjacent_digits:
        return 0
    for digit, encounters in Counter(digits).most_common():
        if 2 == encounters:
            return 1
    return 0

Contents	Answer
168630-718098	1145