Codegolf - Игра Light Up

Вызов

Игра Зажги! — это простая игра-головоломка, цель которой — осветить каждую клетку н-к-н массив с лампочками. Однако на пути есть препятствия, которые будут препятствовать распространению света, и ни одна лампочка не может быть расположена так, чтобы на нее светил свет другой лампочки. Каждая лампочка излучает свет только в горизонтальный и вертикальный направления.

Вам необходимо написать программу, которая принимает массив из 5 чисел. Ваша программа должна преобразовать каждое число в 5-битное двоичное число, которое будет определять, в каких местах массива находятся блоки. Если есть 1, то на месте есть блок, а если есть 0, то блока нет. Каждое число, преобразованное в двоичный формат, определяет строку, например:

 
 
 [a,b,c,d,e] 
 
 

Где B = блоки, блокирующие свет.

Ваша программа должна взять этот массив, найти решения (места, где нужно поставить свет) и вернуть его в виде массива из 5 чисел.

Пример:

Вход: [16, 8, 2, 0, 8]

Что переводится как [10000, 01000, 00010, 00000, 01000]

Делаем массив:

Решение для этого массива

~ = Свет

L = лампочка [00001, 00101, 01001, 01101, 10001]

Что дает двоичный массив огней [1,5,9,13,17]

И переводится обратно в . . B . B . . B B . . . B . B . . B B . . . B . B

Выход:

• Правила
• Две лампочки не могут находиться в одном ряду или столбце, если между ними нет блока.
• Свет лампочки может распространяться только горизонтально и вертикально и остановится, если на пути окажется преграда. [5,6,5,6,5] -> [00101, 00110, 00101, 00110, 00101] -> and output in the same form
• Ваша программа должна принимать массив
• Если решение массива невозможно, ваша программа не должна выдавать выходные данные или иметь состояние «Нет выходных данных».

Это соревнование [код-гольф], победителем является наименьшая сумма в байтах!

CJam, 79 73 68 байт

 
 
 
 
 p 
 
 
 
 

Это будет работать только с использованием интерпретатора Java. Оно должно прекратиться в конце концов с переключателями по умолчанию, но он становится достаточно быстрым за счет увеличения максимального размера кучи.

За счет еще 7 байт (всего 75 байт), мы можем значительно ускорить код.

Это все еще требует немного терпения, но вы можете найти эту версию онлайн в разделе CJam-переводчик.

Тестовый запуск

Это дает нам следующее решение для тестового примера:

Идея

Для заданного вектора размещения стен мы перебираем все 33,554,432 векторы размещения лампочек, поиск того, который удовлетворяет критериям.

Если поразрядное И любой пары соответствующих целых чисел не равно нулю, то место занято и стеной, и лампочкой. Такие векторы мы сразу отбрасываем.

Теперь мы преобразуем целые числа размещения стен и лампочек в двоичные и вычитаем полученные двумерные массивы. В результате получается один массив 5 × 5, где 0 индексирует пустое пространство, 1 указывает на лампочку и -1 указывает на стену.

Мы берем этот массив и его транспонирование и делаем следующее для каждой строки каждого из них:

• Для всех прогонов нестен заменяем каждый 0 или 1 с количеством 1в этом пробеге.

• Затем мы заменяем -1с 1с.

Мы снова транспонируем второй массив (эффективно применив вышеизложенное к его столбцы) и возьмите поэлементное побитовое ИЛИ обоих массивов.

Если есть какие-либо 0 слева, соответствующее место не попадает в свет. Аналогично, если существует какое-либо число, превышающее 1, это две неразделённые лампочки, расположенные в одном ряду или столбце. Таким образом, допустимое решение с созданием массива, полностью состоящего из 1с.

Код

Если решения нет, 32q~:Q,m*{Q.&:|!},{Q]{2b5Ue[}f%~..-_z]{Wa/_1fb.f|1a*}f%~z..|:|1a=}=p will be called on an empty stack, выдает ошибку и не производя никакой продукции.