Advent of Code

[@Find_the_truth]

Вот спасибо)) Как раз искал какие-нибудь задачки) А тут еще и на новогоднюю тематику! =)

[@StGeass]

Code Wars тогда себе добавьте, там есть и на новогоднюю тематику тоже, в том числе довольно сложные.

[@Find_the_truth]

Это было жестоко… Уже 3ий день не могу оторваться от задач. Сложные, местами, но затягивают. А система проверки решения — вообще нечто.

[@toxicmt]

Попробуйте еще наш формат ru.hexlet.io/games ;)

[@JIghtuse]

Да, странно, что до сих пор не было поста. Участвую с первого дня, задачки забавные. Изредка даже удаётся в Leaderboard попасть.

[@Mrrl]

Нет, подход «реши простые задачки, тогда откроем сложные» — это не очень интересно. Приятнее идти от самых трудных.

[@impwx]

Вторая часть не принципиально сложнее первой. На самом деле, это скорее маленькое дополнительное условие.

[@Mrrl]

Это повеселее. Сначала я их понял так, что дни можно открывать только по порядку.

[@Mrrl]

Кстати, вторая задача про молекулу была NP-полной, или только квазиполиномиальной?

[@iDeBugger]

Да, NP-полная, насколько я понимаю. И вообще на самом деле это порождающая грамматика Хомского.

О решении усложнённой задачи про молекулу

В задаче про то как из e надо получить длинную молекулу я действовал полным перебором, но не пытаясь построить молекулу от е, а наоборот, пытаясь сократить результирующую молекулу до е, применяя правила в обратном порядке. Если при этом добавить некоторое количество «жадности» алгоритму, то есть сначала «сворачивать» максимально длинные подцепочки, то результат получается за какое-то совершенно смешное количество итераций. Мне интересно, а как другие её решали?

[@Mrrl]

Скрытый текст

Я тоже шёл в обратную сторону. Но оказалось, что жадный алгоритм быстро попадает в тупик и не может из него выбраться. Анализ показал, что тупиком является цепочка CaRnFAr, перед которой не идёт атом Th (и возможно, несколько атомов Ca). После того, как я запретил эти цепочки, алгоритм быстро что-то нашёл.

[@iDeBugger]

Видимо, мне просто повезло со входными данными :)