Страницы

Поиск по вопросам

понедельник, 1 октября 2018 г.

Код-гольф: Увеличиваем цифры

Задача: Написать код минимально возможной длины, выводящий полученную на вход, строку из цифр большим, символьным шрифтом. Шрифт должен быть в точности такой, как указан тут, в вопросе.
Пример
На вход получена строка "0123456789", на стандартный вывод программа должна вывести:
### # ##### ##### # ####### ##### ####### ##### ##### # # ## # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ##### ##### # # ###### ###### # ##### ###### # # # # # ####### # # # # # # # # # # # # # # # # # # # # # # # ### ##### ####### ##### # ##### ##### # ##### #####
Правила и ограничения
Программа может, но не обязана быть оформленной в виде функции. Если она функция - синтаксис объявления этой функции (int main() {} для C) не учитывается в размере, важен размер самого рабочего кода. Входная строка может поступать в программу любым, удобным вам, способом: в виде переменной, указанной в тестовом примере непосредственно перед кодом, в виде параметра функции или со стандартного ввода. Входная строка может содержать только цифры Результат должен быть выведен на стандартный вывод в текстовом виде. Если стандартный вывод направлен на терминал, экран считать достаточной ширины для вывода всего контрольного примера c запасом. Переход на новую строку обозначайте (явно или не явно) любым символом/комбинацией символов, использующейся для перевода строки на вашей платформе (Например,
или
). Шрифт результата должен в точности соответствовать указанному выше. Между цифрами на выводе должен быть минимум один пробел (цифры не должны сливаться). Шрифт считается моноширинным, т.е. вокруг единицы может быть больше пустого пространства т.к. ее изображение ýже остальных цифр. В программе запрещено использовать любые встроенные в язык и библиотеки к нему функции сжатия и кодирования данных (Такие как: zip/unzip, base64) Программа должна содержать шрифт (или код его формирующий) непосредственно в своем теле. Получать шрифт из внешних источников (ввод, диск, сеть, память видеоадаптера, bios) запрещено Размер программы учитывается в байтах. Побеждает программа имеющая минимальный размер

Конкурс окончен
Первое место занимает @RusArt с ответом на 05AB1E, длиной всего 91 "байт".
Втрое место занимает @Anton Petrusevich с ответом на perl, длиной 150 байт.
И третье место достается @retorta с ответом на python, длиной 161 байт.
В ответах рассмотрены самые разные способы сжатия шрифта. При подготовке к конкурсу я рассматривал большинство из них. Самым простым для реализации и в то же время достаточно эффективным оказалось сжатие до 70 байт в 7 битной, горизонтальной, кодировке (оригинальное моя кодировка представлена в ответе на postgresql. Даже удалось попасть в диапазон допустимых символов, поменяв 6-7 биты и вычтя 2. Правда не все участники заморачивались и тратили драгоценные байты на кодирование в диапазон печатных символов с 0x20 до 0x7E. Применяли кодирование как есть, часто с 8 битом или залезая вообще в диапазон управляющих. В принципе такое кодирование имеет право на жизнь, программы на той платформе, где писались работают. Хотя мне и не очень нравится когда программу нельзя напечатать на принтере, ввести по новой с листа и что бы при этом она продолжила работать (Вы не сможете опубликовать свой код в книге ;) ).
Победителем была использована совершенно другая кодировка шрифта. Словарь из 16 возможных 7и символьных элементов шрифта (в битовом кодировании) и кодовая таблица с номерами частей для каждого символа, которая благодаря нестандартной кодовой странице языка 05AB1E заняла 35 "байт" (технически в этом языке используются 256 графем, которые принято считать "байтами" потому что их именно 256 и если бы реально существовала такая кодовая таблица, то их все действительно можно было бы закодировать одним байтом). К сожалению подобное кодирование в других языках невозможно в принципе, в связи с тем, что из 256 значений байта в кодировке ASCII 31 используется для управляющих кодов, а 128 старших значений плохо переносятся между платформами.
Подобный подход со словарем в принципе был использован еще в нескольких ответах, но там не применялось бинарное кодирование в результате чего шрифт занимает гораздо больше места. В процессе подготовки конкурса я рассматривал даже несколько вариантов кодирования со словарем. Например, две комбинации ##### и # #, встречающиеся очень часто, предполагалось кодировать двумя битами со значениями 10 и 11, а остальные варианты 5и битным значением, первый бит которого 0, что бы отличить от первых двух и остальные 4 бита номер варианта. На практике же это давало совсем небольшой выигрыш в кодировании шрифта и при этом код декодирования оказывался слишком сложным и в код-гольфе неприменимым и опять же в обычном ascii коде уложить это очень сложно.
В ответах можно найти и совершенно иные способы кодирования, например, кодирование повторов # и пробелов просто количествами подряд, представленном в ответе @Qwertiy
К сожалению никто из участников не пробовал использовать вертикальное кодирование, т.е. где элементом выступает 7 бит кодируемого символа берущихся из него по вертикали. А при таком способе кодирования получается очень много повторов. Присмотритесь к цифрам 5689 у них отличаются только 1 и последняя вертикаль, остальные одинаковы. При кодировании повторов в такой строке удается достичь практически такого же сжатия как и в случае с словарем и битовым кодированием. Но на практике гольфа опять же слабо применимое из за роста объема декодирующего кода.

Альтернативный рейтинг
К сожалению не удалось сформулировать правила так, что бы они действительно отражали то, чего я хотел от конкурса. Во многих ответах используются символы не работающие в другой кодировке символов или функции близкие по смыслу к base64, т.е. представляющие закодированную строку как одно большое число, в результате чего в коде отсутствует собственноручное ее декодирование. В данном альтернативном рейтинге я отражаю результаты, как бы они выглядели, если бы правила были точно сформулированы.
Anton Petrusevich, ответ на perl, длиной 150 байт Андрей, ответ на C#, длиной 176 байт Visman, ответ на PHP, длиной 235 байт

Пожалуйста, указывайте в ответе количество байт, чтобы проще было выявить победителя.
execute("ru.stackoverflow.com", "674415"); .cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23px 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:center 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fold 11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1ani 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50% 0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3ani 11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100% 50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin:0 50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg) rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg) rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0) rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}}



Ответ

05AB1E, -78 91 86 bytes
7F"‰ʒØTs“c7н7ƒÔΛ`"255öb7ô"KƶΘå驨ÈÐjη½ñ4BØ„ZƤ™Ωë₄´Ø#Ã.Dι¯ƒ“T"255öhIS7*N+èHè)»1'#‡0' ‡
Попробовать
Словарь в 255-й системе счисления:
‰ʒØTs“c7н7ƒÔΛ`
При преобразовании в двоичную и разделении на группы по 7 получаем это:
['1000001', '0011100', '0100010', '0001000', '0011000', '0101000', '0111110', '0000001', '1000000', '1111111', '1000010', '0000010', '1111110', '0000100', '0010000', '0111111']
Сам шрифт кодируется в 16-й системе счисления (в словаре 16 элементов)
1200021 3453336 6076889 6076709 8AAA9BB 988C706 608C006 9AD3EEE 6006006 600F706
В программе он также переведен в 255-ю систему счисления:
KƶΘå驨ÈÐjη½ñ4BØ„ZƤ™Ωë₄´Ø#Ã.Dι¯ƒ“T
Прогоняется цикл от 0 до 6, в каждой итерации ввод пользователя преобразуется в индексы шрифта, которые в свою очередь восстанавливаются по словарю. В конце программа все собирает и заменяет 0 на пробел и 1 на #.
UPD Заменил использование • на явное преобразование системы счисления.
ö = pop a,b push int(a, b)
UPD Исправил цифру 3, заодно самоликвидировался костыль и код получился меньше
Расшифровка
7 - кладем в стек число 7 F - берем из стека число a, в интервале от 0 до a выполняем следующие команды "‰ʒØTs“c7н7ƒÔΛ`" - кладем в стек строку 255 - кладем в стек число 255 ö - берем из стека a и b, выполняем преобразование системы счисления числа a с основания b к основанию 10, кладем результат в стек b - берем из стека число, преобразуем число в двоичную систему счисления, кладем результат в стек 7 - кладем в стек число 7 ô - берем из стека a и b, делим a на группы по b элементов, кладем в стек массив "KƶΘå驨ÈÐjη½ñ4BØ„ZƤ™Ωë₄´Ø#Ã.Dι¯ƒ“T" - кладем в стек строку 255 - кладем в стек число 255 ö - берем из стека a и b, выполняем преобразование системы счисления числа a с основания b к основанию 10, кладем результат в стек h - берем из стека число, переводим его в 16-ю систему счисления I - кладем в стек пользовательский ввод S - берем из стека строку и кладем массив ее символов 7 - кладем в стек число 7 * - берем из стека a и b, умножаем, кладем в стек результат. Тут массив умножается на число, то есть каждый элемент массива умножается на число N - кладем в стек текущий итератор из команды F (2-я по счету, N = [0..6]) + - берем из стека a и b, складываем, кладем в стек результат è - берем из стека a и b (a - шрифт, b - индекс), кладем в стек a[b] (код из словаря) H - переводим число из 16-й системы в 10-ю è - берем из стека a и b (a - словарь, b - индекс), кладем в стек a[b] (часть рисунка) ) - тут играет роль end F » - на этот момент в стеке есть строки с частями рисунка, команда соединяет их в одну и вставляет между ними перенос на новую строку 1 - кладем в стек число 1 '# - кладем в стек символ # ‡ - берем из стека a,b,c (a - рисунок, b - 1, c - #), в a заменяем b на с 0 - кладем в стек число 0 ' - кладем в стек пробел ‡ - берем из стека a,b,c (a - рисунок, b - 0, c - пробел), в a заменяем b на с в конце программа сама выводит на экран последний элемент стека (наш рисунок)

Комментариев нет:

Отправить комментарий