пс. ищите все другие мои решения проблем Advent of Code здесь.
День 17
Подробности челленджа смотрите здесь.
Во-первых, давайте добавим функцию хэш (которая возвращает MD5 в виде шестнадцатеричной строки, как мы часто делали в этом году).
Затем добавьте функцию step, которая будет принимать позицию (x, y) и путь (например, "hijklDU"), ведущий вверх к нему и возвращает кортеж новой позиции и пути, если мы не собираемся выходить за пределы сетки. Затем мы можем использовать это для создания более полезных функций, чтобы сделать шаг в направлении вверх, вниз, влево и вправо направления.
Теперь мы можем собрать все воедино и написать функцию для поиска всех путей от (0, 0) до (3, 3) в сетке.
Одна небольшая деталь, которую вы, возможно, заметили в строке 5 выше, заключается в том, что мы сокращаем пути, которые достигли цели, это соответствует дополнительным деталям, раскрытым в части 2 ниже.
Для каждой из позиций (и пути, ведущего к ней) мы используем вышеупомянутые вверх, вниз, влево и right выполняет поиск следующих позиций, до которых мы можем добраться отсюда (при условии, что правильные двери открыты в соответствии с хэш-значением MD5).
И да, это снова задача Обход дерева порядка уровней! Забавно, что мы снова и снова видим разные реинкарнации этой конкретной проблемы во время мероприятия AOC в этом году.
Еще одна деталь, на которую следует обратить внимание в приведенном выше фрагменте кода — возможно, что пути может не быть (как на примере в описании проблемы). Вот почему мы завершаем Seq.unfold, когда ни одна из текущих позиций не дает возможного следующего хода.
Теперь мы можем очень легко ответить на часть 1.
Часть 2
Вам интересно, насколько на самом деле надежно это решение для обеспечения безопасности, и поэтому вы решаете
находить все более и более длинные пути, которые по-прежнему обеспечивают доступ к хранилищу. Вы
помните, что пути всегда заканчиваются, когда они впервые достигают нижней правой комнаты
(то есть они никогда не могут пройти через нее, только заканчиваться на нем).
Например:
Если бы ваш пароль был ihgpwlah, самый длинный путь занял бы 370 шагов.
С kglvqrro самый длинный путь был бы 492 шага.
С ulqzkmiv самый длинный путь составит 830 шагов.
Какова длина самого длинного пути, ведущего к хранилищу?
