Advent of Code: Day 11

Source

Part 1: Find the next string in Lexicographical_order that matches these rules:

• Must contain three neighboring, ascending letters (ghi)
• Must not contain any of the letters i, o, or l
• 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[1]))

Basically, there are two interesting problems: finding out if a string is_valid and 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 ord: chr.

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.

comments powered by Disqus