Одной из малоизвестных парадигм программирования, которая кажется весьма подходящей для игры в код, является перекрывающееся ориентированное программирование (ООП) *. При написании частично идентичного кода многие байты можно сохранить, просто перекрывая идентичные части и запоминая каким-то образом, где начинаются две строки исходного кода. Ваша задача состоит в том, чтобы написать две пересекающиеся программы или функции compress
и decompress
со следующими характеристиками:
* Не используйте в производственном коде, вероятно.
compress
compress
берет две строки в любом удобном формате и максимально перекрывает их. То есть строка s
с минимальной длиной возвращается так, что обе входные строки являются подстрока s
. Кроме того, возвращается некоторый вывод, который идентифицирует начальный и конечный индексы обеих строк.
Примеры: (Точный IO-формат зависит от вас)
compress("abcd", "deab") -> "deabcd" ((2,5),(0,3))
compress("abcd", "bc") -> "abcd" ((0,3),(1,2))
compress("abc", "def") -> "abcdef" ((0,2),(3,5)) or "defabc" ((3,5),(0,2))
decompress
decompress
вычисляет обратную функцию compress
, которой дается строка и два начальных и конечных индекса (в формате, в котором они возвращаются вашим compress
), возвращают две исходные строки. Вам нужно только обрабатывать действительные входные данные. Равенство должно выполняться для всех строк s1
, s2
:
(s1, s2) == decompress (compress (s1, s2))
Примеры: (обратные compress
примеры)
decompress "deabcd" ((2,5),(0,3)) -> "abcd" "deab"
decompress "abcd" ((0,3),(1,2)) -> "abcd" "bc"
decompress "abcdef" ((0,2),(3,5)) -> "abc" "def"
or (whichever version your "compress" generates)
decompress "defabc" ((3,5),(0,2)) -> "abc" "def"
счет
Ваша оценка - это размер строки, возвращаемой вызовом compress("<code of compress>", "<code of decompress>")
. Так как это код-гольф, тем ниже оценка.
Пример:
Предположим, что код для вашей функции compress
is c=abcd
и код для decompress
is d=efghi
. Затем compress("c=abcd", "d=efghi")
дает "c=abcd=efghi"
(и индексы, но те, которые не влияют на выигрыш), так что счет length "c=abcd=efghi" = 12
.
Дополнительные правила
- В духе этого вызова ваши
compress
иdecompress
должны совпадать хотя бы в одном персонаже. Вы можете достичь этого тривиально, добавив комментарий, но учтите, что это увеличит ваш счет, и могут быть более короткие решения, использующие частично совпадающий код. compress
иdecompress
должен иметь возможность обрабатывать строки, содержащие любые печатные символы ASCII, а также все символы, которые вы использовали для определенияcompress
иdecompress
.- Индексы могут быть нулевыми или одноиндексными.
- Ваши программы или функции не обязательно должны быть названы
compress
иdecompress
.
Ответы:
GNU Пролог, 105 баллов
(Это требует GNU Prolog, потому что
prefix
иsuffix
не переносимы.)Пролог имеет одно интересное, главное преимущество для этой задачи; Вы можете написать функцию для обработки нескольких шаблонов вызовов (т. е. вы можете не только дать функции вход для получения соответствующего выхода, вы можете дать функции выход для получения соответствующего ввода). Таким образом, мы можем определить функцию, которая может обрабатывать как сжатие, так и распаковку, что приводит к 105-байтовой передаче, которая определяет функцию,
o
которая работает в обоих направлениях. (Между прочим, я в основном написал это как декомпрессор - как это проще - и получил компрессор «бесплатно».) В общем, мы могли бы ожидать очень короткую программу на Прологе для этой задачи, если бы не тот факт, что она настолько плохая при обработке строк (как с точки зрения отсутствующих примитивов, так и с точки зрения рассматриваемых примитивов, имеющих ужасно длинные имена).Первый аргумент
o
- это кортеж строк, например"abcd"-"deab"
. Второй аргумент имеет форму, похожую на"deabcd"-4/6-4/4
; это довольно стандартный вложенный кортеж, и это означает, что строка «deabcd», первая строка имеет длину 4 и заканчивается шестым символом, вторая строка имеет длину 4 и заканчивается четвертым символом. (Обратите внимание, что строка в GNU Prolog - это просто список кодов символов, что делает отладку раздражающей, потому что реализация предпочитает последнюю интерпретацию по умолчанию.) Если вы дадитеo
один аргумент, он выведет другой для вас (таким образом, работая как компрессор, если вы дадите первый аргумент, и как декомпрессор, если вы дадите второй). Если вы дадите ему оба аргумента, он проверит, что сжатое представление соответствует заданным строкам. Если вы дадите ему нулевые аргументы, он сгенерирует вывод примерно так:Вышеприведенное описание формата ввода / вывода также в значительной степени является всего лишь описанием программы; в программе не так много всего. Единственная тонкость связана с подсказками порядка оценки; нам нужно убедиться, что программа не только использует стратегию поиска, которая гарантированно завершается, но и выдает максимально короткую строку вывода.
При сжатии мы начинаем с
length(C,_)
(«C
имеет длину»), что является уловкой, которую я использовал во многих ответах на пролог и брахилог; если это первое, что видит Пролог, это заставит его расставить приоритеты, уменьшив длинуC
над чем-либо еще. Это гарантирует, что у нас есть минимальная длинаC
. Порядок ограничений вs
тщательно выбран, так что поиск займет конечное время для каждой возможной длины кандидатаC
;A
сдерживаетсяC
(мы не знаемC
, но мы знаем , целевое значение , которое мы имеем для ее длины),M
наA
,U
поA
, иL
поU
, так ни один из запросов не может принимать неограниченное время.При распаковке мы даем
C
непосредственно пользователю. Это снова гарантирует, что программа будет работать за конечное время из-за той же последовательности ограничений. (Люди, которые знают о порядке оценки Пролога, заметят, что определениеs
при распаковке очень неэффективно; размещениеlength(A,M)
иlength(U,L)
первое будет быстрее, но перемещениеlength(A,M)
к началу может вызвать бесконечный цикл при сжатии, потому что в то же времяA
неM
связано ни с чем, ни с чем-либо связанным .)источник
Брахилог ,
5046 байтПопробуйте онлайн!
Распаковка:
Попробуйте онлайн!
Сохранено 5 байтов благодаря @ ais523
объяснение
Хорошая сторона декларативных языков заключается в том, что мы можем повторно использовать один и тот же код как для сжатия, так и для распаковки. Таким образом, код для сжатия точно такой же, как и для распаковки , с дополнительным
~
в начале.Это
~
говорит Brachylog об обратном порядке аргументов (то есть, использовать входные данные как выходные данные и выходные данные как входные данные). Поскольку сжатие не имеет~
, он фактически выполняет предикат в стандартном порядке. Поскольку распаковка имеет только один, он запускает его с входом в качестве вывода и выходом в качестве ввода.Таким образом, мы можем использовать один и тот же код (по модулю extra
~
) как для сжатия, так и для распаковки: сжатие обеспечивает две строки в качестве входных данных, а переменную - в качестве выходных, а декомпрессия - предоставление индексов и сжатой строки в качестве выходных данных, а переменную - в качестве входных данных. ,Очевидно, это также означает, что мы должны быть немного откровенны в отношении нашего кода сжатия, чтобы интерпретатор мог запускать его «назад». Вот почему сам компрессор немного длинный.
Вот разбивка кода для Compress (и, следовательно, также для распаковки):
источник
Желе ,
5850 байт-1 байт благодаря ais523 (используйте
⁾
для двухбайтовой строки)Это вполне может быть вполне пригодным для игры в гольф ...
Сжатие принимает два строковых аргумента и возвращает список:
[[[startA, lengthA], [startB, lengthB]], compressedString]
Декомпрессия принимает один аргумент (такой список) и возвращает две * строки:
Перекрытый код:
Один индексированные.
* это может быть неочевидно из-за неявного форматирования печати Jelly, поэтому код в TryItOnline, на который ссылается выше, имеет дополнительный байт (a
Y
в конце) для вставки перевода строки между этими двумя в печатном выводе.Я начал с одной программы, которая использовала глубину первого (или единственного) аргумента для выбора между сжатием и распаковкой, но наличие неиспользуемой ссылки в коде распаковки (первая строка) и одного перекрывающего байта короче на семь байтов ,
Как?
источник
“ṫḣ”
может быть обработано на 1 байт с помощью синтаксиса Jelly для 2-символьных строк.