Головоломка сверху-спереди - это головоломка, в которой вам необходимо построить трехмерную (обычно кубическую) форму блоков, учитывая три ортогональных вида: вид сверху, вид спереди и вид сбоку.
Например, дан вид сверху, спереди и сбоку следующим образом:
Top: Front: Side:
. . . . . . . . . . . .
. x x . . x x . . x x .
. x x . . x x . . x x .
. . . . . . . . . . . .
In this problem, the side view is taken from the right.
Куб 2x2x2 (с объемом 8) удовлетворял бы этому решению, но это выполнимо в объеме 4, если у нас есть следующая структура слоя:
. . . . . . . .
. x . . . . x .
. . x . . x . .
. . . . . . . .
Есть также несколько неразрешимых договоренностей. Взять, к примеру:
Top: Front: Side:
. . . . . . . . . . . .
. . . . . . x . . . . .
. x . . . . . . . x . .
. . . . . . . . . . . .
Если вид сверху говорит, что блок является вторым слева, нет никакого способа, который мог бы соответствовать виду спереди, который говорит, что блок должен быть третьим слева. Так что это расположение невозможно.
Ваша задача состоит в том, чтобы создать программу, которая, учитывая произвольную головоломку 4x4 с верхней стороны, пытается решить ее за наименьшее количество кубов или объявляет ее неразрешимой.
Ваша программа примет в качестве входных данных последовательность из 48 битов, представляющих вид сверху, спереди и сбоку. Они могут быть в любом формате, который вы хотите (6-байтовая строка, строка из 0 и 1, 12-значное шестнадцатеричное число и т. Д.), Но порядок битов должен отображаться следующим образом:
Top: 0x00 Front: 0x10 Side: 0x20
0 1 2 3 0 1 2 3 0 1 2 3
4 5 6 7 4 5 6 7 4 5 6 7
8 9 a b 8 9 a b 8 9 a b
c d e f c d e f c d e f
Другими словами, биты идут в порядке слева направо, сверху вниз, сверху, затем спереди, затем сбоку.
Затем ваша программа выведет либо серию из 64 битов, указывающую заполненные кубы в сетке 4x4x4, либо указывает, что сетка неразрешима.
Ваша программа будет оценена путем запуска батареи из 1 000 000 тестовых случаев.
Тестовые данные будут получены путем взятия MD5-хешей целых чисел от «000000» до «999999» в качестве строк, извлечения первых 48 бит (12 шестнадцатеричных чисел) каждого из этих хешей и использования их в качестве входных данных для top-front- боковая загадка. В качестве примера, вот некоторые из тестовых входов и головоломок, которые они генерируют:
Puzzle seed: 000000 hash: 670b14728ad9
Top: Front: Side:
. x x . . . . x x . . .
x x x x . x . x x . x .
. . . . . x x x x x . x
x . x x . . x . x . . x
Puzzle seed: 000001 hash: 04fc711301f3
Top: Front: Side:
. . . . . x x x . . . .
. x . . . . . x . . . x
x x x x . . . x x x x x
x x . . . . x x . . x x
Puzzle seed: 000157 hash: fe88e8f9b499
Top: Front: Side:
x x x x x x x . x . x x
x x x . x . . . . x . .
x . . . x x x x x . . x
x . . . x . . x x . . x
Первые два неразрешимы, в то время как последний имеет решение со следующими слоями, спереди назад:
x . . . . . . . x x x . x x x .
. . . . x . . . . . . . . . . .
x . . . . . . . . . . . x x x x
x . . . . . . . . . . . x . . x
There are a total of 16 blocks here, but it can probably be done in less.
Оценка вашей программы будет определяться по следующим критериям в порядке убывания приоритета:
- Наибольшее количество раскрытых дел.
- Наименьшее количество блоков, необходимых для решения этих случаев.
- Самый короткий код в байтах.
Вы должны самостоятельно представить и рассчитать балл, что требует от вашей программы прохождения всех 1 000 000 тестовых случаев.
Ответы:
Python: 5360 тестовых случаев, решенных с использованием 69519 блоков, 594 байта
Это должны быть оптимальные значения.
Подходить:
Сначала я проверим, является ли тестовый пример действительно разрешимым. Я делаю это, инициализируя список длиной 64 единицами и устанавливая все позиции в ноль, если там соответствующий пиксель трех представлений равен нулю. Затем я просто смотрю на головоломку со всех трех направлений и смотрю, совпадают ли виды с входными. Если они равны, головоломка разрешима (мы уже нашли худшее решение), в противном случае она неразрешима.
Затем я делаю ветвистый подход для нахождения оптимального решения.
Ветвление: меня есть рекурсивная функция. Глубина рекурсии говорит о том, сколько значений уже зафиксировано. При каждом вызове функции я вызываю себя дважды, если значение в текущем индексе равно 1 (это значение может быть 0 или 1 в оптимальном решении), или один раз, если значение равно 0 (оно должно быть равно нулю в Оптимальным решением).
Ограничение: здесь я использую две разные стратегии.
Я вычисляю виды с трех сторон в каждом вызове функции и смотрю, соответствуют ли они входным значениям. Если они не совпадают, я не вызываю функцию рекурсивно.
Я храню лучшее решение в памяти. Там уже больше фиксированных в текущей ветке, чем в лучшем решении, я уже могу закрыть эту ветку. Дополнительно я могу оценить нижнюю границу для количества активированных блоков, которые не являются фиксированными. И состояние становится
#number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) < #number of activated blocks in the best solution.
Вот код Python. Он определяет функцию,
f
которая ожидает 3 списка, содержащие 1 и 0, и возвращает либо 0 (неразрешимый), либо список из 1 и 0, представляющий оптимальное решение.Длина кода составляет 596 байт / символов. И вот тестовая структура:
Вы можете найти версию программы без гольфа здесь . Это также немного быстрее.
Результаты:
5360 из 1000000 головоломок разрешимы. Всего нам нужно 69519 блоков. Количество блоков варьируется от 6 до 18 блоков. Самая сложная головоломка заняла около 1 секунды. Это головоломка с семенем
"347177"
, которое выглядити имеет оптимальное решение с 18 кубиками. Ниже приведено несколько сверху для каждого из слоев:
Общее время выполнения для всех тестовых случаев составило около 90 секунд. Я использовал PyPy для выполнения моей программы. CPython (интерпретатор Python по умолчанию) немного медленнее, но также решает все головоломки всего за 7 минут.
Вы можете найти полный вывод здесь : вывод не требует пояснений. Например, результат для загадки выше:
источник
5360 дел решено 69519 блоками; 923 байта
Это тоже оптимально. Вызов с массивом единиц и нулей. Выдает
NullPointerException
неправильный ввод. Некоторая эффективность принесена в жертву гольфу. Он все еще завершается в течение разумного времени для всех 1000000 тестовых входов.Стратегия:
Я действительно играл в эту головоломку совсем немного, когда мне было 10. Это использует мой подход.
Шаг 1:
Сформируйте куб с большинством блоков, которые соответствуют заданным представлениям.
Шаг 2:
Создайте список съемных частей. (Любая часть с этим имеет другую часть в своем входе, столбец в ней, а луч - в.)
Шаг 3:
Испытайте все возможные способы хранения или удаления каждого съемного элемента. (С помощью рекурсивной грубой силы с обрезкой.)
Шаг 4:
Держите лучший действительный куб.
Ungolfed:
Полная программа:
источник