Advent of Code 2019: Day 4

Question

Advent of Code 2019: Day 4

I'm doing Advent of Code this year. Below is my attempt at day 4:

Problem

Part One

--- Day 4: Secure Container ---

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.

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).

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).

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

 

Part Two

--- Part Two ---

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

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).

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

---

Solution

from itertools import groupby

bounds = (265275, 781584)

rules = [
    # Digits are never decreasing
    lambda s: all(int(s[i]) <= int(s[i+1])
                  for i in range(len(s)-1)),
    # Two adjacent digits are equal.
    lambda s: any(s[i] == s[i+1] for i in range(len(s)-1)),
    # Two adjacent digits don't form a larger group.
    lambda s: any(len(list(v)) == 2 for _, v in groupby(s))
]


def test(num, rules):
    return all(f(str(num)) for f in rules)


def solve(bounds, rules):
    return sum(1 for i in range(bounds[0], bounds[1]+1) if test(i, rules))


def part_one():
    return solve(bounds, rules[:2])


def part_two():
    return solve(bounds, rules[::2])


print(part_one())  # 960
print(part_two())  # 626

---

Notes

I don't consider myself a beginner in Python, however I am not proficient in it either. I guess I would be at the lower ends of intermediate. I am familiar with PEP 8 and have read it in its entirety, thus, any stylistic deviations I make are probably deliberate. Nevertheless, feel free to point them out if you feel a particular choice of mine was sufficiently erroneous. I am concerned with best practices and readability, but also the performance of my code. I am not sure what tradeoff is appropriate, and would appreciate feedback on the tradeoffs I did make.

My style tends to over utilise functions. This is partly because I genuinely think separating functionality into functions is a good thing, but is also an artifiact of my development practices. I tend to write the program in a Jupyter notebook (the ability to execute arbitrary code excerpts in semi isolated cells is a very helpful development aid and lends itself naturally to one function per cell (with the added benefit of being able to easily test functions independently)). I would welcome thoughts on this, but unless it is particularly egregious, I am unlikely to change it.

Answer 1

Overall, it looks good to me. Just a couple observations. They aren't necessarily better or more pythonic, but you may see them in peoples code. Use whichever you find more readable:

The first rule turns the digits to ints to compare them, but the ascii for the digits compares the same as the integer digits ('0' < '1' ... < '9'). So the int() isn't needed. Also, a common idiom for comparing adjacent items in a list is to use zip(seq, seq[1:]). The first two rules could be coded as:

# Digits are never decreasing
lambda s: all(a <= b for a,b in zip(s, s[1:])),

# Two adjacent digits are equal.
lambda s: any(a == b for a,b in zip(s, s[1:])),

In a numeric context, True and False are converted to 1 and 0, respectively. So, solve can be coded as:

def solve(bounds, rules):
    return sum(test(i, rules) for i in range(bounds[0], bounds[1]+1))

Answer 2

Overall, I like this. To really nitpick, I don't really like the use of rules[::2]. [::2] conveys that we are picking out every even element of rules as if that was significant. But in this case, it is more like it just happens to be that the first and last rules are what we want to pick out and that happened to match up with choosing all even elements.

I would probably just name the rules as follows. If the visual grouping of the rules is important you could wrap them in a class as static methods.

from itertools import groupby

bounds = (265275, 781584)

def digits_never_decreasing(s):
    return all(int(s[i]) <= int(s[i+1]) for i in range(len(s)-1))

def adjacent_digits_equal(s):
    return any(s[i] == s[i+1] for i in range(len(s)-1))

def adjacent_digits_not_in_larger_group(s):
    return any(len(list(v)) == 2 for _, v in groupby(s))


def test(num, *rules):
    return all(f(str(num)) for f in rules)

def solve(bounds, *rules):
    return sum(1 for i in range(bounds[0], bounds[1]+1) if test(i, *rules))

def part_one():
    return solve(bounds, digits_never_decreasing, adjacent_digits_equal)

def part_two():
    return solve(bounds, digits_never_decreasing, adjacent_digits_not_in_larger_group)


print(part_one())  # 960
print(part_two())  # 626

Answer 3

The algorithm is non-optimal. While this brute force solution solves the task, it is very slow. It takes 2,435s to solve both parts of the task while my algorithm takes 0,032s.

I suggest to construct only suitable numbers (every next digit is greater or equal to previous) from the start, instead of checking all numbers in range. The amount of suitable numbers is small, so it is easy to check them for meeting part one's and part two's conditions.

Algorithm:

My input is "372304-847060", so start = 372304, end = 847060.

Implementation:

#!/usr/bin/python3

from collections import Counter

def find_first_value(number):
    fill_digit = 0
    max_fill_digit_found = False
    new_number = []
    for digit in number:
        digit = int(digit)
        if digit >= fill_digit and not max_fill_digit_found:
            fill_digit = digit
        else:
            max_fill_digit_found = True

        new_number.append(fill_digit)

    return new_number

def find_all_passwords(cur_value, end_value):
    length = len(cur_value)
    # Two lists comparison.
    # The comparison uses lexicographical ordering:
    # first the first two items are compared, and if they differ
    # this determines the outcome of the comparison;
    # if they are equal, the next two items are compared, and so on,
    # until either sequence is exhausted.
    while cur_value < end_value:
        idx = length - 1
        for dgt in range(cur_value[idx], 10):
            cur_value[idx] = dgt
            yield cur_value
            
        while cur_value[idx] == 9 and idx > 0:
            idx -= 1

        fill_dgt = cur_value[idx] + 1
        for i in range(idx, length):
            cur_value[i] = fill_dgt

def part_one(first_value, end_value):
    for val in find_all_passwords(first_value, end_value):
        # If all digits in the list are unique: the len(list) == len(set()).
        # Else at least one digit are repeated.
        if len(set(val)) < len(val):
            yield val

def part_two(first_value, end_value):
    for val in find_all_passwords(first_value, end_value):
        # Counts the occurence of every digit.
        cntr = Counter(val)
        # If the number contains some digit two times.
        if 2 in cntr.values():
            yield val

puzzle_input = "372304-847060"
start, end = puzzle_input.split('-')

first_value = find_first_value(start)
end = list(map(int, end))

print(sum(1 for _ in part_one(first_value.copy(), end)))
print(sum(1 for _ in part_two(first_value.copy(), end)))

Answer 4

Your code initially looks well organised, but is quite hard to follow.

To begin, you pass in nearly identical parameters to the two functions part_one and part_two and it is not immediately clear why. Next, using lambda functions as you currently are isn't recommended; as these are anonymous functions they won't have a name which can make debugging harder e.g if you get and error you'll be told it's in <lambda>:

In [35]: a = lambda s: any(s[i] == s[i+1] for i in range(len(s)-1))
In [36]: def adjacent(s):
    ...:     return any(s[i] == s[i+1] for i in range(len(s)-1))
In [37]: a
Out[37]: <function <lambda> at 0x105767cb0>

In [38]: adjacent
Out[38]: <function adjacent at 0x105aa29e0>

I would advocate the style seen in Kent's answer.

Another improvement is noticing that the answer to part two is a subset of values you generated for part one, so you should try to use that instead of having to regenerate and then filter another set of values.

---

A couple of extra things that you may want to consider:

From the Advent of Code about page:

every problem has a solution that completes in at most 15 seconds on ten-year-old hardware

This means that there is sometimes a trick or a shortcut that you can use to get to a solution faster, and potentially in fewer lines of code. For example, I'll share my solution:

from collections import Counter

def part_1(a, b):
    for i in range(a, b + 1):
        x = list(str(i))
        if x != sorted(x) or len(set(x)) == len(x):
            continue
        yield str(i)

def part_2(passwords):
    return sum(1 for x in passwords if 2 in Counter(x).values())


passwords = list(part_1(152085, 670283))
print(len(passwords))
print(part_2(passwords))

Here, part_1 is essentially a wrapper for range that is filtering the values we get.

• x != sorted(x) checks if the digits are increasing as a sorted string will always be increasing.
• len(set(x)) == len(x) tests if the number of unique digits is equal to the total number of digits, if true there cannot be any duplicated values.
• These two rules together also implicitly enforce the rule that some adjacent digits are the same, so we don't need to test for it.

part_2 uses a collections.Counter (a special kind of dictionary) to easily get the total number of each digit in the string and checking if 2 is in the values. In my opinion, this is very clear as it reads like a sentence.

Finally, you could easily improve the readability of my code by further abstracting the conditions in part_1, like so:

def increasing(x):
    return x == "".join(sorted(x))

def duplicates_in(x):
    return len(set(x)) != len(x)

def part_1(a, b):
    for i in range(a, b + 1):
        i = str(i)
        if not increasing(i) or not duplicates_in(i):
            continue
        yield i

Answer 5

One note, you can skip nearly all of the checks for part 1 by realizing that the second constraint is (almost) guaranteed by the first within the bounds. If your starting position is 37xxxx then only 456789 doesn't repeat a digit. Thus you can just construct all increasing values from 37xxxx to 84xxxx and subtract one.

DISCLAIMER: It seems as though the inputs vary per person, so this trick isn't valid for everyone

# With input 372xxx-84xxxx
# min value 377777, max value 799999
count = -1  # skip 456789
# This loop and/or sum can be collapsed upwards with cleverness
# that is unnecessary for such small ranges of numbers.
for a in range(3, 8):
 for b in range(7 if a == 3 else a, 10):
  for c in range(b, 10):
   for d in range(c, 10):
    for e in range(d, 10):
     for f in range(e, 10):
      count += 1
print(count)