пс. ищите все другие мои решения проблем Advent of Code здесь.

День 11

Подробности челленджа смотрите здесь.

Сегодня, пожалуй, первое испытание AOC, действительно сложное и требующее долгих размышлений, и мне оно очень понравилось!

Во-первых, давайте смоделируем проблемную область.

и нам понадобится способ определить, сгорели ли микрочипы или мы преуспели в нашей миссии после переезда.

По своей сути проблема здесь похожа на проблему Обход дерева порядков уровней, которую мы видели вчера, где на каждый ход у вас есть нет. из последующих ходов, которые вы можете сделать:

  • учитывая этаж, на который приземляется лифт, вы можете взять 1 или 2 предмета с этажа на следующем ходу.
  • учитывая этаж, на который приземляется лифт, вы можете двигаться вверх или вниз по этажу

Например, учитывая это состояние:

F4 .  .  .  .  .  
F3 E  HG HM LG .  
F2 .  .  .  .  .  
F1 .  .  .  .  LM

Вот 6 возможных комбинаций предметов, которые можно загрузить в лифт для следующего хода:

  • HG
  • HM
  • LG
  • HG, HM
  • HG, LG
  • HM, LG

кроме того, вы также можете перемещать лифт вверх или вниз, что дает в общей сложности 12 возможных ходов с этой точки.

Хитрость, однако, заключается в том, чтобы убедиться, что вы не сделаете ход, который приведет к состоянию, в котором вы уже были ранее. Одной этой оптимизации достаточно, чтобы решить первую часть задачи менее чем за минуту, но для второй части этого было недостаточно…

Ключевым моментом для второй оптимизации является то, что сами элементы не имеют значения, т.е. все три из этих конфигураций представляют одну и ту же проблему:

F4 .  .  .  .  .  
F3 .  .  .  LG .  
F2 .  HG .  .  .  
F1 E  .  HM .  LM
F4 .  .  .  .  .  
F3 .  .  .  HG .  
F2 .  LG .  .  .  
F1 E  .  LM .  HM
F4 .  .  .  .  .  
F3 .  HG .  .  .  
F2 .  .  .  LG .  
F1 E  .  LM .  HM

потому что суть проблемы не изменилась:

  • лифты на 1 этаже
  • есть элемент, Генератор которого находится на 3 этаже, а микросхема на 1 этаже
  • есть элемент, Генератор которого находится на 2 этаже, а микросхема на 1 этаже

Таким образом, если мы сможем представить состояния таким образом, мы сможем идентифицировать эквивалентные состояния и избежать их повторения.

Имея это в виду, давайте переопределим метод ToString типа State, чтобы такое состояние

F4 .  .  .  .  .  
F3 E  HG HM LG .  
F2 .  .  .  .  .  
F1 .  .  .  .  LM

представлен как «3-(3, 1)(3, 3)», где кортежи представляют (этаж генератора, уровень микрочипа) для каждого элемента, а порядок определяется только значениями пола.

Итак, теперь мы можем углубиться в суть решения.

Здесь следует отметить пару вещей:

  • Я использую изменяемый HashSet вместо неизменяемого Set F# по соображениям производительности, но не подвергаю эту изменчивость улица
  • Функция itemCombos возвращает все возможные комбинации предметов, которые могут быть загружены в лифт, она выполняет дополнительную работу по созданию дубликатов (и затем отфильтровывает их с помощью Seq.distinct ), но может быть легко устранено
  • для каждой комбинации предметов мы генерируем 1 или 2 новых состояния в зависимости от того, как может двигаться лифт
  • каждое новое состояние добавляется в кеш, используя его строковое представление выше
  • те состояния, которые приводят к поджариванию микросхем, игнорируются и не используются для генерации еще большего количества состояний

Решение части 1 выглядит так:

Часть 2

Вы входите в чистую комнату, отделяющую вестибюль от изолированной зоны, и надеваете
защитный костюм.

Однако при входе в изолированную зону содержания вы замечаете некоторые дополнительные
части на первом этаже, которые не были указаны в записи снаружи:

Генератор элерия.
Микрочип, совместимый с элерием.
Генератор дилития.
Микрочип, совместимый с дилитием.
Они работают так же, как и другие генераторы и микрочипы. Вам также нужно будет
довести их до сборки.

Какое минимальное количество шагов требуется, чтобы доставить все объекты,
включая эти четыре новых, на четвертый этаж?

С обеими оптимизациями первая часть заняла 1 с, а вторая — 8 с на моем ПМБ, что очень приятно!

Ссылки