Игра BattleBlock Theatre иногда содержит головоломку, которая является обобщенной версией Lights Out . У вас есть три смежных блока, каждый из которых указывает уровень от 1 до 4 включительно с барами, например:
|
||||
||
Если вы дотронетесь до блока, то этот блок, как и любой соседний блок, будет увеличивать свой уровень (переход от 4 до 1). Загадка решается, когда все три блока показывают один и тот же уровень (не имеет значения, какой уровень). Поскольку порядок, в котором вы касаетесь блоков, не имеет значения, мы обозначаем решение по частоте касания каждого блока. Оптимальным решением для вышеуказанного ввода будет 201
:
| --> || --> ||| |||
|||| | || |||
|| || || --> |||
Игра очень легко обобщает любое количество блоков, хотя для некоторых чисел не все конфигурации разрешимы.
Соревнование
Учитывая последовательность уровней блоков, верните, как часто нужно нажимать на каждый блок, чтобы решить головоломку. Например, приведенный выше пример будет приведен как 142
и может дать 201
в результате. Если решения не существует, верните какой-либо непротиворечивый вывод по вашему выбору, который отличается от всех потенциальных решений, например, -1
пустую строку.
Вы можете написать функцию или программу, получить ввод через STDIN, аргумент командной строки или аргумент функции, в любом удобном формате списка или строки и аналогичным образом вывести через возвращаемое значение или распечатать в STDOUT.
Ваш код должен возвращать правильные результаты для всех тестовых случаев в течение минуты на приемлемой машине. (Это не совсем строгий предел, поэтому, если ваше решение занимает минуту и десять секунд, это нормально, но если это займет 3 минуты, это не так. Хороший алгоритм легко решит их за секунды.)
Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.
Примеры
Решения не являются уникальными, поэтому вы можете получить разные результаты.
Input Output
1 0
11 00
12 No solution
142 201
434 101
222 000
4113 0230
32444 No solution
23432 10301
421232 212301
3442223221221422412334 0330130000130202221111
22231244334432131322442 No solution
111111111111111111111222 000000000000000000000030
111111111111111111111234 100100100100100100100133
412224131444114441432434 113013201011001101012133
Насколько я знаю, есть ровно 4 решения для каждого входа, где количество блоков равно 0 mod 3 или 1 mod 3, и есть 0 или 16 решений, где это 2 mod 3.
источник
Ответы:
Python 2, 115 байт
Это версия программы для гольфа, которую я написал, обсуждая проблему с Мартином.
Ввод представляет собой список через STDIN. Вывод представляет собой список, представляющий последнее найденное решение, если есть решение, или ноль, если его нет. Например:
Pyth,
3229 байтОбязательный порт. Спасибо @Jakube за сохранение 3 байтов.
Способ ввода такой же, как и выше, попробуйте онлайн .
Объяснение (длинное и полное логики!)
Сначала два основных замечания:
Наблюдение 1: Неважно, в каком порядке вы касаетесь блоков
Наблюдение 2: Если вы касаетесь блока 4 раза, это равносильно касанию его один раз
Другими словами, если есть решение, то есть решение, в котором число касаний составляет от 0 до 3 включительно.
Поскольку модуль 4 хорош, давайте сделаем это и с блоками. В остальной части этого объяснения уровень блока 0 эквивалентен уровню блока 4.
Теперь давайте обозначим
a[k]
текущий уровень блокаk
иx[k]
количество раз, которое мы касаемся блокаk
в решении. Также пустьn
будет общее количество блоков. Как отметил @Jakube, решение должно удовлетворять:где
C
- конечный уровень, на котором заканчиваются все блоки, от 0 до 3 включительно (помните, что мы рассматриваем уровень 4 как уровень 0), и все приведенные выше уравнения действительно являются конгруэнциями по модулю 4.Теперь вот самое интересное:
0 <= C <= 3
.Есть три случая, основанные на количестве блоков по модулю 3. Объяснение для каждого из них одинаково - для любого количества блоков существует подмножество блоков, которое, если вы прикоснетесь к каждому из них один раз, увеличит все уровни блоков на ровно 1.
Это объясняет, почему существует 4 решения для
0 mod 3
и1 mod 3
, и обычно 16 решений для2 mod 3
. Если у вас уже есть решение, прикосновение к блокам, как указано выше, дает другое решение, которое заканчивается на более высоком уровне блока (обтекание).Так что это значит? Мы можем выбрать любой конечный уровень блока, который
C
мы хотим! Давайте выберемC = 0
, потому что это экономит на байтах.Теперь наши уравнения становятся:
И переставить:
Итак, что мы можем видеть, если мы имеем
x[0]
, то мы можем использовать все уравнения, кроме последнего, чтобы выяснить все остальныеx[k]
. Последнее уравнение является дополнительным условием, которое мы должны проверить.Это дает нам алгоритм:
x[0]
x[k]
Это дает решение выше.
Так почему же мы иногда не получаем решения
2 mod 3
? Давайте снова посмотрим на эти две модели:Теперь рассмотрим уравнения в этих положениях, т.е. для первого:
Добавьте их:
Для второго:
Добавьте их снова:
Так что если
(a[1] + a[4] + a[7] + a[10])
и(a[0] + a[3] + a[6] + a[9])
не равны, то у нас нет решения. Но если они равны, то мы получаем 16 решений. Это было дляn = 11
случая, но, конечно, это обобщается на любое число, которое2 mod 3
- взять сумму каждого третьего элемента, начиная со второго, и сравнить с суммой каждого третьего элемента, начиная с первого.Теперь, наконец, возможно ли выяснить, что
x[0]
должно быть, вместо того, чтобы попробовать все возможности? В конце концов, поскольку мы ограничили наш целевой уровеньC
на 0, есть только один,x[0]
который дает решение в случае0 mod 3
или в1 mod 3
(как4 solutions / 4 final levels = 1 solution for a specific final level
).Ответ ... да! Мы можем сделать это для
0 mod 3
:Что переводится как:
Вычитание дает:
Точно так же, как
1 mod 3
мы можем сделать этот шаблон:Который дает:
Они, конечно, обобщаются путем увеличения индексов с шагом 3.
Поскольку
2 mod 3
у нас есть два подмножества, которые охватывают каждый блок, мы можем выбрать любойx[0]
. Фактически, это верно дляx[0], x[1], x[3], x[4], x[6], x[7], ...
(в основном, любого индекса, который не соответствует2 mod 3
, поскольку они не охватываются ни одним из подмножеств).Таким образом, у нас есть способ выбрать
x[0]
вместо того, чтобы попробовать все возможности ...... но плохая новость в том, что это не экономит байты (124 байта):
источник
J
вместоH
2 символов, если вы добавляете последний элементPJ
вместо нарезки.<J_1
,V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB
Pyth,
727673663938 символовредактировать 4: понял, что расчеты
Q[N]-Q[N+1]+solution[-3]
иQ[-2]-Q[-1]+solution[-3]
идентичны. Поэтому я пересчитываю решение на 1 и фильтрую решения, где последняя запись равна 0. Затем я выталкиваю последнюю запись. К счастью, особые случаи не требуют дополнительного лечения с таким подходом. -27 символовредактировать 3: применение некоторых трюков в гольф от FryAmTheEggman: -7 персонаж
редактировать 2: используя фильтр, уменьшить и отобразить: -3 символа
редактировать 1: в моей первой версии я ничего не печатал, если не было решения. Я не думаю, что это разрешено, поэтому +4 символа.
Ожидает список целых чисел в качестве входных данных
[1,4,2]
и выводит правильное решение,[2,0,1]
если оно есть, в противном случае - пустой список[]
.Объяснение:
Позвольте
Q
быть список 5 уровней иY
список решения. Следующие уравнения должны выполняться:Поэтому, если мы используем любое
Y0
иY1
, мы можем рассчитатьY2
,Y3
иY4
следующим образом.То, что все уровни, кроме последнего, равны (потому что мы не использовали уравнение
= Q4 + Y3 + Y4
. Чтобы проверить, равен ли этот последний также другим уровням, мы можем просто проверить, если(Q3 - Q4 + Y2) mod 4 == 0
. Обратите внимание, что левая часть будет значениемY5
Если я вычислю 6-ю часть решения, я могу просто проверить, равен ли он нулю.В моем подходе я просто перебираю все возможные запуски (
[0,0]
, to[3,3]
), вычисляю длину (input) -1 больше записей и фильтрую все решения, заканчивающиеся нулем.это в основном следующее:
затем я фильтрую эти возможные решения для действительных:
к этому списку решений я добавляю пустой список, чтобы в нем был хотя бы один элемент
и возьмите первое решение
h
, вытолкните последний элементp
и распечатайте егоОбратите внимание, что это также работает, если есть только один блок. В моем подходе я получаю стартовую позицию [0,0] и не расширяю ее. Поскольку последняя запись равна 0, она печатает решение [0].
Второй особый случай (2 блока) не такой уж особенный. Не уверен, почему я слишком усложнил вещи раньше.
источник
?**lQ]0qhQeQ<lQ3h+f!%-+ePQ@T_3eQ4mu+G]%+&H@G_3-@QH@QhH4UttQd^UT2]Y
составляет 66 байтов. Производительность немного пострадала, но для меня он все же проходит самый большой тестовый тест <1 с. Пинг мне, если вы хотите объяснения некоторых из гольфов; в этом комментарии недостаточно места;) Надеюсь, вам+<list><int>
имеет тот же эффект+<list>]<int>
, что и вы можете удалить первый]
. Также очень хорошее решение.~
? Похоже, это не было, когда я пытался~
наa
-~<list>]<int>
эквивалентноa<list><int>
.~
есть+=
, аa
есть.append()
Рубин,
320313 символовОпределенно можно играть в гольф больше. Ничего не выводит для неразрешимых головоломок.
Безголовая версия:
Хорошо, это было весело. Вот основной алгоритм,
{n}
представляющий n «прикосновений» к числу вышеn
, как показано на одном из примеров:Я был немного озадачен здесь. Как я могу превратить
111...1110
в серию одинаковых номеров? Таким образом, я сравнил свое решение и правильное решение (обратите внимание: число «касания» на единицу больше, чем должно быть, поскольку вход индексируется 1, а выход 0):Я заметил, что каждый номер был один от правильного
mod 4
, поэтому я пометил их с+
s,-
s и=
s:Это работало некоторое время, пока я не заметил, что иногда конечный результат был
111...11112
или11...1113
также! К счастью, многократное применение магической формулы, которая не имеет смысла, но работает, также разобрало их.Итак, вот оно. Программа, которая начинает иметь смысл, но с течением времени превращается во все более и более безобразное хакерство. Я думаю, что это довольно типичное решение для гольф-кода. :)
источник
exit if (r+=1)>5
на(r+=1)>5&&exit
. Кроме того,(code)while cond
синтаксис короче, чемwhile cond \n code \n end
.Python 2,
294 289 285 281273 байтаDEMO
Я уверен, что это может быть в дальнейшем.
Вот результаты тестовых случаев:
Алгоритм сначала проверяет, чтобы значения всех блоков, кроме последнего, были одинаковыми (путем итерации и добавления к «счетчикам касаний» всех блоков, кроме первых 2). Затем, если количество блоков позволяет это (
(num_of_blocks - 1) % 3 != 1
), возвращается и проверяет, соответствуют ли значения остальных блоков последнему блоку. Печатает,x
если нет решения.источник