16

Напишите программу или функцию, которая не требует ввода, но печатает или возвращает постоянное текстовое изображение прямоугольника, состоящего из 12 различных пентомино :

Прямоугольник может иметь любые размеры и быть в любой ориентации, но все 12 пентомино должны использоваться ровно один раз, поэтому он будет иметь область 60. Каждое пентомино должно состоять из другого печатаемого символа ASCII (вам не нужно использовать письма сверху).

Например, если вы решили вывести это решение прямоугольника пентамино размером 20 × 3:

Вывод вашей программы может выглядеть примерно так:

00.@@@ccccF111//=---
0...@@c))FFF1//8===-
00.ttttt)))F1/8888=-

В качестве альтернативы вам может быть проще сыграть в гольф с этим решением 6 × 10:

Подойдет любое решение для прямоугольника, ваша программа должна напечатать только одно. (Завершающий перевод строки в выводе в порядке.)

Этот замечательный веб-сайт содержит множество решений для разных размеров прямоугольников, и, вероятно, стоит просмотреть их, чтобы убедиться, что ваше решение максимально короткое. Это код-гольф, выигрывает самый короткий ответ в байтах.

code-golf kolmogorov-complexity geometry grid Кальвин Хобби
источник

15

Бонус, если это «квин» в пите.

mbomb007

@ mbomb007 Это почти невозможно с помощью всего 12 блоков: P

Sp3000

Я не думаю, что места должны быть разрешены на границах. Но так как они есть, могу ли я пропустить завершающие пробелы? Получу ли я бонус, если я распечатаю вертикальное решение 5х12 с буквой I в конце?

Джон Дворжак

@ Sp3000, а как насчет программы Пайета, состоящей исключительно из прямоугольных решений пентомино?

Джон Дворжак

@JanDvorak Вы не можете пропустить конечные пробелы, если они у вас есть. Они символы, как и остальные печатные ASCII.

Увлечения Кэлвина

1

Pyth, 37 байт

jc4.HC"&f3ªªwril3:[·)ÌDU[r)ÌDA»

демонстрация

Использует очень простой подход: используйте шестнадцатеричные байты в качестве чисел. Преобразовать в шестнадцатеричное число, основание 256 кодировать это. Это дает волшебную строку выше. Чтобы декодировать, используйте основную функцию декодера Pyth 256, преобразуйте в шестнадцатеричный код, разделите на 4 фрагмента и соедините на новых строках.

isaacg
источник

5

CJam (44 байта)

Задано в формате xxd, поскольку оно содержит управляющие символы (включая необработанную вкладку, которая очень плохо работает с MarkDown):

0000000: 2202 7e0d 8ef3 570d e085 e168 cf27 092c
0000010: a235 0c22 3235 3662 3562 332f 5f2c 2c2e
0000020: 7b32 2f27 412b 662b 7d7a 4e2a

который декодирует что-то по линии

"MAGIC STRING"256b5b3/_,,.{2/'A+f+}zN*

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

Основной принцип заключается в том, что, поскольку ни один фрагмент не охватывает более 5 строк, мы можем компактно кодировать смещение от линейной функции номера строки (фактически, в базе 5, хотя я не пытался определить, будет ли это всегда так). ).

Питер Тейлор
источник

5

Bash + общие утилиты Linux, 50

xxd -s20 -p -c2 $0
#<30 bytes of binary data>

Чтобы воссоздать это из закодированного base64:

base64 -d <<< eHhkIC1zMjAgLXAgLWMyICQwCiMiImaSaZlmkDAAMwSjRKNEqoGogYhRVVF7UXu7d3s= > pent.sh

Поскольку существует 12 пентамино, их цвета легко кодируются в шестнадцатеричных блоках.

Выход:

$ ./pent.sh
2222
6692
6999
6690
3000
3304
a344
a344
aa81
a881
8851
5551
7b51
7bbb
777b
$

Цифровая травма
источник

4

J, 49 байт

u:64++/\|:3#.inv 1377859090 1567813024 1337683230

Вы можете выбрать буквы таким образом, чтобы максимальные приращения между вертикально смежными буквами были равны 2. Мы используем этот факт для кодирования вертикальных приращений в base3. После этого мы создаем текущие суммы и добавляем смещение, чтобы получить ASCII-коды букв.

Определенно гольф. (Мне еще предстоит найти способ ввода чисел base36 с повышенной точностью, но простой base36 должен сохранять только 3 байта.)

Выход:

AAA
ABA
BBB
DBC
DCC
DCC
DEE
DFE
FFE
FGE
FGG
GGH
HHH
IIH
JII
JJI
JKK
JKL
KKL
LLL

Попробуйте это онлайн здесь.

randomra
источник

Очень хорошо. При кодировании base-256, применяя эту разностную кодировку в CJam, выдается 33 байта ( 48-байтовая версия без b256 ).

Питер Тейлор

Это круто! Это также будет работать с 4x15, который будет хорошо работать для упаковки четырех чисел в байт, если вы храните данные по ширине, а не по длине. Вам понадобится макет, в котором U-пентамино направлено правильно. Есть много в ссылке на вопрос.

Уровень Река St

@steveverrill Для этого вам понадобится начальное смещение, потому что в первой строке будет более 4 частей, поэтому вы не можете кодировать их в base4. С этим дополнительным смещением (например, 3#i.5которое есть 0 0 0 1 1 1 ... 4 4 4) оно может работать, но, вероятно, не будет короче (по крайней мере, так, как я пытался).

Рандомра

2

Microscript II , 66 байт

Начнем с простого ответа.

"00.@@@ccccF111//=---\n0...@@c))FFF1//8===-\n00.ttttt)))F1/8888=-"

Ура неявной печати.

SuperJedi224
источник

1

Рубин

Rev 3, 55 байтов

i=1
'S, OJ1*$HCH(#%0'.bytes{|e|puts "%x"%i+=e*130&9011}

В качестве дальнейшего развития идеи Рандомры рассмотрим таблицу результатов и различий ниже. Таблицу различий можно сжать, как и раньше, и расширить, умножив на 65 = двоичный код 1000001 и применив маску 11001100110011. Однако Ruby не работает предсказуемо с 8-битными символами (он обычно интерпретирует их как Unicode.)

Удивительно, но последний столбец полностью ровный. Из-за этого при сжатии мы можем выполнить смещение прав на данные. Это гарантирует, что все коды являются 7-битными ASCII. В расширении мы просто умножаем на 65 * 2 = 130 вместо 65.

Первый столбец также полностью ровный. Поэтому мы можем добавить 1 к каждому элементу (32 к каждому байту), где необходимо, чтобы избежать каких-либо управляющих символов. Ненужный 1 удаляется с помощью маски 10001100110011 = 9011 вместо 11001100110011.

Solution 59 of document linked in question

Start0001

Out  Diff
2223 2222
2433 0210
2433 0000
4445 2012
6555 2110
6577 0022
6687 0110
6887 0200
8897 2010
aa99 2202
caa9 2010
cab9 0010
cbbb 0102
cdbd 0202
cddd 0020

Хотя я использую 15 байтов для таблицы, я действительно использую только 6 бит каждого байта, что в сумме составляет 90 бит. На самом деле существует только 36 возможных значений для каждого байта, что составляет в общей сложности 2,21E23. Это соответствовало бы 77 битам энтропии.

Rev 2, 58 байт, используя инкрементальный подход Рандомры

i=0
'UPEIP@bPHPBETTEPRADT'.bytes{|e|puts "%x"%i+=e*65&819}

Наконец, что-то короче наивного решения. Инкрементальный подход Рандомры, с методом байтовой упаковки Rev 1.

Rev 1, 72 байта, версия для гольфа rev 0

Некоторые изменения были внесены в базовую линию, чтобы приспособить переупорядочение кода по причинам, связанным с игрой в гольф, но все же оно длится дольше, чем наивное решение.

i=0
'UPUIYD&!)$&V*).);c+*'.bytes{|e|i+=1;puts "%x"%(i/2*273+(e*65&819))}

Смещения кодируются в каждый символ магической строки в базе 4 в формате BAC, то есть с 1, представляющим правый символ, с 16, представляющим средний символ, и левым символом, вставленным в позицию 4. Чтобы извлечь их, код ascii умножается на 65 (двоичный код 1000001), чтобы получить BACBAC, затем он добавляется к 819 (двоичный код 1100110011), чтобы получить.A.B.C .

У некоторых из кодов ascii установлен 7-й бит, т.е. они на 64 больше, чем требуется, чтобы избежать управляющих символов. Поскольку этот бит удаляется маской 819, это несущественно, за исключением случаев, когда значение Cравно 3, что вызывает перенос. Это должно быть исправлено только в одном месте (вместо того g, чтобы использовать c.)

Rev 0, версия без гольфа

a= %w{000 010 000 201 100 100 011 021 110 120 011 112 111 221 211 221 122 123 112 222}
i=2
a.each{|e|puts "%x"%(i/2*273+e.to_i(16));i+=1}

Выход

объяснение

Из следующего решения я вычитаю базовую линию, давая смещение, которое я сохраняю как данные. Базовая линия восстанавливается в виде шестнадцатеричного числа в коде i/2*273(273 десятичных = 111 шестнадцатеричных).

solution   baseline   offset
AAA        AAA        000
ABA        AAA        010
BBB        BBB        000
DBC        BBB        201
DCC        CCC        100
DCC        CCC        100
DEE        DDD        011
DFE        DDD        021
FFE        EEE        110
FGE        EEE        120
FGG        FFF        011
GGH        FFF        112
HHH        GGG        111
IIH        GGG        221
JII        HHH        211
JJI        HHH        221
JKK        III        122
JKL        III        123
KKL        JJJ        112
LLL        JJJ        222

Уровень реки St
источник

Похоже, по сути, тот же подход, что и у меня, но вам удалось избежать единственной дельты 4, которая заставила меня кодировать в базе 5. Похоже, я выбрал неправильную маркировку для фрагментов.

Питер Тейлор

Я видел твой ответ после того, как отправил свой. Я не могу следовать Cjam, но из того, что вы сказали в своем ответе, это похожий подход. На самом деле у меня только одна 3таблица во всей таблице (прямо возле нижней части), поэтому я думаю, что, увеличив базовую линию чуть более чем на 0,5 каждой строки, можно фактически использовать базу 3. Не стесняйтесь попробовать это. (По причинам, связанным с игрой в гольф, мне кажется, мне придется немного изменить базовую линию, что дает мне больше 3-х, и, к сожалению, похоже, что она будет на 1 байт длиннее, чем простое решение в Ruby.)

Level River St

В случае, если раньше я не понимал, я хотел поздравить вас с лучшей работой, а не обвинить вас в копировании. И я не собираюсь пытаться использовать скорость роста 2,5, потому что я не думаю, что это превзойдет подход кодирования различий рандомы.

Питер Тейлор

@PeterTaylor спасибо, я понял, что ты меня поздравляешь. С другой стороны, вы пришли в первую очередь с той же идеей и сделали ее намного короче, так что поздравляю и вас. С разностным подходом рандомера, наконец, я могу стать короче, чем наивное решение. Это будет хорошо работать и в 4х15 (при правильном расположении пентомино). Именно так я бы сделал это на C или любом другом языке, который хорошо работает со строками 8.bit. Поскольку Ruby поддерживает Unicode, он пытается интерпретировать 8-битные строки как Unicode и может выдавать некоторые раздражающие сообщения об ошибках.

Уровень Река St

0

Foo, 66 байт

"00.@@@ccccF111//=---\n0...@@c))FFF1//8===-\n00.ttttt)))F1/8888=-"

Теос
источник

Это символ за символом, идентичным решению Microscript II выше ... Я предполагаю, что эти языки связаны?

Даррел Хоффман

1

@DatrelHoffman не совсем, foo просто печатает все в кавычках

Teoc

Распечатать прямоугольник Пентомино

Ответы:

Pyth, 37 байт

CJam (44 байта)

Bash + общие утилиты Linux, 50

Выход:

J, 49 байт

Microscript II , 66 байт

Рубин

Rev 3, 55 байтов

Rev 2, 58 байт, используя инкрементальный подход Рандомры

Rev 1, 72 байта, версия для гольфа rev 0

Rev 0, версия без гольфа

Foo, 66 байт