Пришло время предпринять опасное стремление победить британскую разведку. Цель этой задачи - написать кратчайший код, который решит нонограмму.
Что такое нонограмма?
Правила просты. У вас есть сетка квадратов, которые должны быть либо заполнены черным, либо оставить пустым. Рядом с каждой строкой сетки указаны длины чёрных квадратов в этой строке. Над каждым столбцом указаны длины чёрных квадратов в этом столбце. Ваша цель - найти все черные квадраты. В этом типе головоломки числа - форма дискретной томографии, которая измеряет, сколько непрерывных линий заполненных квадратов есть в любой данной строке или столбце. Например, подсказка «4 8 3» будет означать, что имеются наборы из четырех, восьми и трех заполненных квадратов в указанном порядке, по крайней мере, с одним пустым квадратом между последовательными группами. [ 1 ] [ 2 ]
Таким образом, решение вышеупомянутого Nonogram будет:
Детали реализации
Вы можете представлять Нонограмму так, как вам хочется, и использовать ее в качестве входной информации любым способом, который вы считаете подходящим для вашего языка. То же самое касается вывода. Цель этой задачи - буквально просто выполнить работу; если вы можете решить нонограмму с любым выводом вашей программы, это действительно. Одно предостережение: нельзя использовать онлайн-решатель :)
Эта проблема очень сложна с точки зрения алгоритма (np-complete) в том смысле, что не существует полностью эффективного решения, и поэтому вы не будете наказаны за то, что не можете решить более крупные задачи, хотя ваш ответ будет в значительной степени вознагражден, если он способен обрабатывать большие дела (см. бонус). В качестве теста мое решение работает примерно до 25x25 в течение 5-10 секунд. Чтобы обеспечить гибкость различных языков, достаточно хороши решения, которые занимают менее 5 минут для неграммы 25x25.
Вы можете принять загадку всегда в квадрате NxN nonogram.
Вы можете использовать этот онлайн-пазл, чтобы проверить свои решения.
счет
Вы, конечно, можете свободно использовать любой язык, который хотите, и поскольку это кодовый гольф, записи будут отсортированы в следующем порядке: accuracy -> length of code -> speed.
однако, не расстраивайтесь по языкам игры в гольф, ответы на всех языках, которые показывают попытки игры в гольф интересным образом будет проголосовано!
бонус
Я на самом деле узнал о Кроссвордах от криптографической Рождественской открытки выпущенной британской разведки здесь . Первая часть была в основном массивной Нонограммой 25х25. Если ваше решение способно решить эту проблему, вы получите слава :)
Чтобы упростить вашу жизнь с точки зрения ввода данных, я представил, как я представлял данные для этой конкретной головоломки для свободного использования. Первые 25 строк - это строки-подсказки, за которыми следует разделительная строка '-', за которыми следуют 25 строк столбцов, за которыми следует строка-разделитель '#', а затем представление сетки с заполненными квадратными подсказками.
7 3 1 1 7
1 1 2 2 1 1
1 3 1 3 1 1 3 1
1 3 1 1 6 1 3 1
1 3 1 5 2 1 3 1
1 1 2 1 1
7 1 1 1 1 1 7
3 3
1 2 3 1 1 3 1 1 2
1 1 3 2 1 1
4 1 4 2 1 2
1 1 1 1 1 4 1 3
2 1 1 1 2 5
3 2 2 6 3 1
1 9 1 1 2 1
2 1 2 2 3 1
3 1 1 1 1 5 1
1 2 2 5
7 1 2 1 1 1 3
1 1 2 1 2 2 1
1 3 1 4 5 1
1 3 1 3 10 2
1 3 1 1 6 6
1 1 2 1 1 2
7 2 1 2 5
-
7 2 1 1 7
1 1 2 2 1 1
1 3 1 3 1 3 1 3 1
1 3 1 1 5 1 3 1
1 3 1 1 4 1 3 1
1 1 1 2 1 1
7 1 1 1 1 1 7
1 1 3
2 1 2 1 8 2 1
2 2 1 2 1 1 1 2
1 7 3 2 1
1 2 3 1 1 1 1 1
4 1 1 2 6
3 3 1 1 1 3 1
1 2 5 2 2
2 2 1 1 1 1 1 2 1
1 3 3 2 1 8 1
6 2 1
7 1 4 1 1 3
1 1 1 1 4
1 3 1 3 7 1
1 3 1 1 1 2 1 1 4
1 3 1 4 3 3
1 1 2 2 2 6 1
7 1 3 2 1 1
#
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
А вот для вашего удобства немного другая версия; кортеж через запятую (строка, столбец), где каждый элемент является списком списков.
([[7, 3, 1, 1, 7],
[1, 1, 2, 2, 1, 1],
[1, 3, 1, 3, 1, 1, 3, 1],
[1, 3, 1, 1, 6, 1, 3, 1],
[1, 3, 1, 5, 2, 1, 3, 1],
[1, 1, 2, 1, 1],
[7, 1, 1, 1, 1, 1, 7],
[3, 3],
[1, 2, 3, 1, 1, 3, 1, 1, 2],
[1, 1, 3, 2, 1, 1],
[4, 1, 4, 2, 1, 2],
[1, 1, 1, 1, 1, 4, 1, 3],
[2, 1, 1, 1, 2, 5],
[3, 2, 2, 6, 3, 1],
[1, 9, 1, 1, 2, 1],
[2, 1, 2, 2, 3, 1],
[3, 1, 1, 1, 1, 5, 1],
[1, 2, 2, 5],
[7, 1, 2, 1, 1, 1, 3],
[1, 1, 2, 1, 2, 2, 1],
[1, 3, 1, 4, 5, 1],
[1, 3, 1, 3, 10, 2],
[1, 3, 1, 1, 6, 6],
[1, 1, 2, 1, 1, 2],
[7, 2, 1, 2, 5]],
[[7, 2, 1, 1, 7],
[1, 1, 2, 2, 1, 1],
[1, 3, 1, 3, 1, 3, 1, 3, 1],
[1, 3, 1, 1, 5, 1, 3, 1],
[1, 3, 1, 1, 4, 1, 3, 1],
[1, 1, 1, 2, 1, 1],
[7, 1, 1, 1, 1, 1, 7],
[1, 1, 3],
[2, 1, 2, 1, 8, 2, 1],
[2, 2, 1, 2, 1, 1, 1, 2],
[1, 7, 3, 2, 1],
[1, 2, 3, 1, 1, 1, 1, 1],
[4, 1, 1, 2, 6],
[3, 3, 1, 1, 1, 3, 1],
[1, 2, 5, 2, 2],
[2, 2, 1, 1, 1, 1, 1, 2, 1],
[1, 3, 3, 2, 1, 8, 1],
[6, 2, 1],
[7, 1, 4, 1, 1, 3],
[1, 1, 1, 1, 4],
[1, 3, 1, 3, 7, 1],
[1, 3, 1, 1, 1, 2, 1, 1, 4],
[1, 3, 1, 4, 3, 3],
[1, 1, 2, 2, 2, 6, 1],
[7, 1, 3, 2, 1, 1]])
источник
s=[].fill([].fill(0,0,25),0,25);s[3][3]=s[3][4]=s3[3][12]=s3[3][13]=s3[3][21]=s[8][6]=s[8][7]=s[8][10]=s[8][14]=s[8][15]=s[8][18]=s[16][6]=s[16][11]=s[16][16]=s[16][20]=s[21][3]=s[21][4]=s[21][9]=s[21][10]=s[21][15]=s[21][20]=s[21][21]=1;
Ответы:
Brachylog ,
7069 байтДля этого требуется список из двух списков (сначала указатели строк, а затем столбцы). Каждый индикатор представляет собой список (для ситуаций, как
[3,1]
в одной строке).Эта версия занимает около 3 минут, чтобы решить 5 на 5 пример задачи.
Гораздо более эффективная версия, 91 байт
Попробуйте онлайн!
Это не полная грубая сила: единственное отличие состоит в том, что она накладывает ограничения на значения ячеек, так что число 1 в каждой строке и столбце соответствует числам, указанным в качестве индикаторов на входе. Единственная часть грубой силы состоит в том, чтобы найти одну сетку с теми ограничениями, для которых «блоки» 1 соответствуют тому, что задано в качестве индикации.
Это займет около 0,05 секунд на 5 на 5 примере испытания. Это все еще слишком медленно для бонусного случая, поскольку я понятия не имею, как выразить блоки единиц, разделенные одним или несколькими нулями, в терминах ограничений.
объяснение
Я объясню ниже версию 93 байтов. Единственное различие между ними заключается в обращении к предикату 3, которого нет в 70-байтовой версии, и в нумерации предикатов (поскольку их на один меньше).
Основной предикат:
Предикат 1: заставляет строки иметь определенную длину, и каждая ячейка равна 0 или 1.
Предикат 2: ограничение переменной должно быть 0 или 1
Предикат 3: сумма 1 в списке должна быть равна сумме индикаторов (например, если индикатор [3: 1], то в списке должна быть сумма 4)
Предикат 4: Убедитесь, что блоки единиц соответствуют индикатору
Предикат 5: Истинно для блоков 1 с, иначе ложно
источник
Haskell,
242 230 201 199 177 163 160 149131 байтНаконец, до 200 байт, кредит @Bergi. Огромное спасибо @nimi за помощь почти вдвое уменьшить размер.
Вау. Почти вдвое меньше, отчасти из-за меня, но в основном из-за @nimi.
Волшебная функция есть
(#)
. Находит все решения данной нонограммы.Это может решить все случаи, но может быть очень медленным, так как его сложность составляет около
O(2^(len a * len b))
. Быстрый тест показал 86 ГБ, выделенных для 5x5 nonogram.Интересный факт: он работает для всех неграмм, а не только для квадратных.
Как это устроено:
a#b
: Даны списки списков целых чисел, которые представляют количество квадратов, генерируют все сетки (map(chunk$length b).mapM id$a>>b>>[[0,1]]
) и фильтруют результаты, чтобы сохранить только действительные.g
: Учитывая потенциальную нонограмму, она суммирует пробеги 1 по горизонтали.источник
m(chunk$l b)
иreplicate(l$a>>b)
import Data.Lists
достаточно, потому что он реэкспортируетData.List
иData.List.Split
.Pyth,
917271 байтПрограмма , которая принимает данные из списка формы ,
[size, [horizontal clues], [vertical clues]]
где каждый ключ представляет собой список целых чисел (пустые ключи являются пустым списком[]
), и печатает каждое решение, перевод строка разделена, в виде бинарной решетки , где1
затенен и0
является незатушеванным ,Это грубая сила, примерно так
O(2^n^2)
. Это займет очень много времени для больших головоломок, но разрешит любой произвольный размер, если будет достаточно времени.Попробуйте онлайн
Как это устроено
Программа генерирует каждый возможный макет, беря повторяющееся декартово произведение
[0, 1]
с длиной, равнойsize^2
. Затем это разделяется на куски, давая список для каждой горизонтальной линии. Каждая строка кодируется по длине серии, фильтруется по наличию1
и выравнивается, оставляя ключ к этой строке. Это тогда проверено против ввода. Вышеописанный процесс повторяется для транспонирования кусков, проверки вертикальных линий. Если есть совпадение, каждый фрагмент объединяется, и объединенные фрагменты объединяются на новых строках и печатаются неявно с последующим переводом строки.Спасибо @ Pietu1998 за несколько советов
источник
=ZhZ
равно=hZ
иFN
равноV
.Javascript (ES6),
401386333 байтаЭто ранняя попытка. Это не очень эффективно, но мне было любопытно протестировать решение, используя регулярные выражения для двоичного представления строк и столбцов.
Например, он переведет подсказку
[3,1]
в следующее регулярное выражение:Прямо сейчас, эта версия не принимает в расчет квадратные ключи. Я, вероятно, добавлю это позже.
Код
Выход
Решение отображается в двоичном формате. Такие как:
Тестовое задание
Это простой тест на примере сетки.
источник
Haskell, 109 байт
Отказ от ответственности: это получено из ответа @ ThreeFx . Я помог ему сформулировать свой ответ, но он, похоже, потерял интерес, чтобы включить мои последние существенные улучшения, поэтому я публикую их как новый ответ.
Пример использования:
[[2],[3],[3],[3,1],[1]] # [[2],[3],[4],[2],[2]]
->[[" ## "," ### ","### ","### #"," #"]]
.Грубая сила. Попробуйте все комбинации
и
#
, разделите int на части#
, посчитайте длины и сравните с вводом.источник
PHP,
751833 (720)753724726710691680682 байтаМне не терпелось создать специализированный инкремент последовательности и еще раз попробовать мой декартовый генератор;
но отбросил декартову в пользу отступления, чтобы быстрее решить большую головоломку.
$r
для подсказок строк,$c
для подсказок столбцов и$s
для квадратных подсказок.invalid argument supplied for foreach
если не находит решения.\n
и удалите два других перевода строки.описание
1) из подсказок
строк генерируют возможные строки, которые удовлетворяют квадратным подсказкам
и запоминают их числа для каждого индекса строки.
2) Возврат по комбинации строк:
если комбинация удовлетворяет подсказкам столбца, ищите глубже или возвращайте успешную комбинацию,
иначе попробуйте следующую возможность для этой строки.
3) решение для печати
Последнее игра в гольф оказало серьезное влияние на производительность;
но я удалил задания профилирования для окончательных тестов.
Замените
$n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];
на,
if(($p[$y][$i[$y]]>>$x&1)-$v){$k=($v=!$v)||$n==$h[$z++];$n=1;}else$n++;
чтобы отменить последний шаг в гольф.
Примеры
Для небольшого примера (от
17 до 21около12876,75,3 мс) используйтедля рождественской головоломки:
5037,845,5около 36 секундпоместите данные из вопроса в файл
christmas.nonogram
и используйте этот код для импорта:сломать
источник
$d
должно быть в правильном порядке дляforeach