Part 1: Find the next string in Lexicographical_order that matches these rules:
- Must contain three neighboring, ascending letters (
- Must not contain any of the letters
- Must contain two distinct pairs of letters
This is pretty similar to Advent of Code: Day 5, although it cannot quite be done with purely regular expressions.
def is_valid(password): numeric = list(map(ord, password)) return ( # Include an increasing subsequence any( numeric[i] + 2 == numeric[i + 1] + 1 == numeric[i + 2] for i in range(len(password) - 2) ) # May not contain i, o, or l and not any(c in password for c in 'iol') # Must have at least two different pairs and len(set(re.findall(r'(.)\1', password))) >= 2 ) def increment(password): numeric = list(map(ord, password)) index = -1 while True: numeric[index] += 1 if numeric[index] <= ord('z'): break else: numeric[index] = ord('a') index -= 1 return ''.join(map(chr, numeric)) def next_valid(password): while True: password = increment(password) if is_valid(password): return password print(next_valid(sys.argv))
Basically, there are two interesting problems: finding out if a string
incrementing one to the next value.
For the first, we check each of the three cases in order. We can tell if there is an ascending sequence by first converting to numeric values (
ord will return the unicode codepoint for a character) the comparing three adjacent values. The second test just checks if
any character is
in the string. The last actually does use regular expressions again to find all pairs of letters; then, by converting them into a set removes duplicates and counts unique values.
For the second problem (
increment), we use the numeric form again and start at the end of the string. We’ll increment each character working back towards the front of the string, stopping as soon as we don’t have to carry. Then, we convert the password back into a string using the inverse of
And, that’s it. It’s certainly not the most efficient code, but it still takes only a few seconds.
Part 2: Find the next string matching the same rules after the one you found in part 1.
Just run the same program again on the first one’s input.