У Санты странный (и опасный!) способ выбора паролей — вот как он описан в головоломке:
Все это — длинный способ сказать:
-
Чтобы найти следующий пароль Санты, мы должны увеличить существующий пароль, состоящий из восьми символов.
-
Мы увеличиваем пароль до тех пор, пока не будут выполнены три правила.
Инкрементирование букв
На первый взгляд это выглядит раздражающе просто, но на самом деле мне потребовалось некоторое время, чтобы разобраться.
Если существующий пароль abc, мы увеличим его до abd. Все хорошо, но что произойдет, когда мы дойдем до abz? Мы увеличиваем так же, как и число, и начинаем со следующего столбца, так что получаем aca.
Я предполагал, что следующим паролем после zzzzzzzz будет aaaaaaaa, но, к счастью, в реальной головоломке мы никогда не сталкиваемся с такой ситуацией. В итоге я решил считать пароль числом Base 26, но это не помогло в решении задачи.
Вот как я в итоге увеличивал пароль Санты, что включало в себя рекурсия!
def incr_string(s):
if len(s):
l, r = s[:-1], s[-1]
if r == 'z':
return incr_string(l) + 'a'
else:
return l + chr(ord(r) + 1)
else:
return ''
Здесь мы разбиваем строку на две части: (i) все до последней буквы и (ii) последнюю букву. Если нам повезло, и нам не придется превращать z в a, мы преобразуем его в число Ascii, добавляем единицу, а затем снова преобразуем его в символ.
Если последний символ — z, мы снова обращаемся к функции, чтобы увеличить строку без последнего символа, а затем возвращаем результат с буквой ‘a’ на конце. И, конечно же, если существующий пароль abcdzzzz, мы забираемся в рекурсию!
Правила
После того, как мы увеличили пароль, пришло время проверить, соответствует ли он всем правилам:
1) Пароль должен включать одну возрастающую прямую из минимум трех букв, например, abc, bcd, cde и так далее, вплоть до xyz. Они не могут пропускать буквы; abd не считается.
Благодаря второму правилу, приведенному ниже, у меня получился небольшой список тройных букв, которые действительно разрешены:
if sum(map(s.count, ['abc', 'bcd', 'cde',
'def', 'efg', 'fgh',
'pqr', 'qrs', 'rst',
'stu', 'tuv', 'uvw',
'vwx', 'wxy', 'xyz'])):
Однако в мегатреде было много, возможно, лучших способов поиска возрастающих прямых, включая циклический просмотр слова и проверку последовательных букв:
has_straight = False
for i in range(len(password) - 2):
if ord(password[i]) == ord(password[i+1])-1 and
ord(password[i]) == ord(password[i+2])-2:
has_straight = True
break
Удивительно, но я не нашел никого, кто бы использовал подход RegEx для поиска трех последовательных букв.
2) Пароли не должны содержать буквы i, o или l, так как эти буквы могут быть приняты за другие символы и поэтому сбивают с толку.
К этому моменту все стало намного проще, как, например, подсчет гласных в День 5:
if sum(map(s.count, 'iol')) == 0:
3) Пароли должны содержать как минимум две разные, не пересекающиеся пары букв, например aa, bb или zz.
Здесь мне понадобился RegEx, и мне действительно нужно было лучше прочитать головоломку, поскольку я полностью пропустил слово «разные». Дольше, чем мне хотелось бы признать, я разрешал пароли типа abcxxdxx, не замечая, что пары должны быть разными.
Прежде всего, нам нужен работающий RegEx. Шаблон для поиска одинаковых непересекающихся пар букв в строке — (.)1, в чем вы можете убедиться здесь. Я использовал findall(), чтобы получить все совпадающие пары, которые я затем запихнул в набор, чтобы убедиться, что у меня есть более одной разной пары:
if len(set(re.findall(r'(.)1', s))) > 1:
Вот, собственно, и все. Возьмите существующий пароль (вход головоломки) и увеличивайте его до тех пор, пока он не будет соответствовать правилам.
Необычно для Advent of Code, во второй части нужно было просто найти второй пароль, так что больше писать код не пришлось. Вперед!