В игре Freecell вам поручено построить четыре кучи фундамента от туза до короля по схеме, в которой вы строите вниз чередующимися цветами. Однако вы можете создавать только одну карту за раз, поэтому вам предоставляется четыре «свободных клетки», каждая из которых может содержать одну карту, чтобы помочь вам перемещать целые последовательности. Идея состоит в том, что вы вкладываете отдельные карты в свободные ячейки и из них, как требуется, чтобы помочь вам решить игру.
Ваша задача - создать программу, которая решит эти игры за наименьшее количество ходов.
Ваша программа примет последовательность из 52 карточек в следующем формате:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
Который будет рассматриваться в первоначальном макете в следующем порядке:
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52
И вернуть список ходов, чтобы решить игру. Каждый ход будет в этом формате:
- Число, представляющее номер кучи (
1
сквозной8
), или свободная ячейка (A
доD
), представляющая исходную кучу. - Другой номер или буква, представляющая кучу или свободную ячейку назначения, или
F
для основания этой масти.
Вывод будет выглядеть примерно так:
18 28 3A 8B 8C 85 B5 35 4F etc.
Как только карта помещена в фундамент, она не может быть удалена. Поскольку одновременно перемещается только одна карта, перемещение последовательности из 3 карт требует 5 ходов, а последовательность из 5 карт требует 9 ходов.
Если игра неразрешима, ваша программа должна указывать как таковую. Однако ваша программа должна быть способна решить любую разрешимую игру.
Ваша программа будет оценена по 32 768 сделкам, найденным в оригинальной программе Microsoft FreeCell. Для того чтобы ваша программа была действительной, она должна успешно завершить каждую сделку, кроме сделки № 11 982 , которая не может быть разрешена . Ваша оценка будет равна общему количеству ходов, необходимых для совершения этих 32 767 сделок, с более коротким кодом, являющимся тай-брейком.
Файл со всеми колодами в формате, требуемом вышеуказанной спецификацией, доступен для загрузки здесь (файл 5,00 МБ): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks
источник
Ответы:
C 64 643 байта, оценка: ~ 6,5 млн.
Следующий фрагмент стека (любезно предоставленный Mego) выводит весь код в виде отдельного автономного файла C:
Показать фрагмент кода
Скачать оригинальный источник здесь . Используйте GCC и запустите
make
затем, следуя указаниям в файле readme.Мое форматирование плохое (все разные файлы находятся в одном блоке кода), и это может быть больше (12 тыс. Байт). Любая помощь будет любимой!
Часть кода не моя. Я использовал это из незащищенного авторского права источника. Тем не менее, я исправил метод ввода / вывода в рамках задачи (долгая задача, так как я ужасен в C (5 часов). Мне также пришлось переписать большую часть кода и отладить все. Большое спасибо моему отцу за помощь и за то, что он резиновая утка (и указание на мои ошибки в управлении памятью), и за всех в TNB, кто имел дело с моей злобой о segfaults и C.
источник