В теории информации «префиксный код» - это словарь, в котором ни один из ключей не является префиксом другого. Другими словами, это означает, что ни одна из строк не начинается ни с одной другой.
Например, {"9", "55"}
это код префикса, но {"5", "9", "55"}
это не так.
Самым большим преимуществом этого является то, что закодированный текст может быть записан без разделителя между ними, и он все равно будет уникально дешифруемым. Это проявляется в алгоритмах сжатия, таких как кодирование Хаффмана , которое всегда генерирует оптимальный код префикса.
Ваша задача проста: по заданному списку строк определить, является ли он допустимым префиксным кодом.
Ваш вклад:
Будет список строк в любом разумном формате .
Будет содержать только печатаемые строки ASCII.
Не будет содержать пустых строк.
В результате вы получите значение true / falsey : Truthy, если это правильный код префикса, и false, если это не так.
Вот несколько настоящих тестов:
["Hello", "World"]
["Code", "Golf", "Is", "Cool"]
["1", "2", "3", "4", "5"]
["This", "test", "case", "is", "true"]
["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011",
"0110", "11001", "00110", "10011", "11000", "00111", "10010"]
Вот несколько ложных тестовых случаев:
["4", "42"]
["1", "2", "3", "34"]
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]
Это код-гольф, поэтому применяются стандартные лазейки, и выигрывает кратчайший ответ в байтах.
источник
001
быть уникально дешифруемым? Это может быть00, 1
или0, 11
.0, 00, 1, 11
все ключи, это не префикс-код, потому что 0 - префикс 00, а 1 - префикс 11. Код префикса - это то, где ни один из ключей не начинается с другого ключа. Так, например, если ваши ключи -0, 10, 11
это префиксный код и уникально дешифруемый.001
не является действительным сообщением, но0011
или0010
является уникально дешифруемым.Ответы:
Pyth, 8 байт
Тестирование
Возьмите все 2 элемента перестановки входных данных, сопоставьте каждую с индексом одной строки в другой (0 для префикса) и верните, все ли результаты верны (ненулевые).
источник
Haskell, 37 байт
Каждый элемент
x
изl
повторяются один раз для каждого элемента , что это префикс, который ровно один раз для приставки свободного списка, давая первоначальный список. Свойство prefix проверяется путем сжатия обоих списковx
, что обрезает элементы за пределами длиныx
.источник
Java,
128127126125124121 байт(Спасибо, Кенни Лау, @Maltysen, @Patrick Roberts, @Joba)
Ungolfed
Выход
источник
&
работать вместо&&
?int
и вернуть0
и1
? Это сэкономило бы несколько байтов. Также я забываю, допустимо ли это в Java, но если вы объявитеi
,j
иl
во внешнемfor
цикле, который бы спас один байт от одной точки с запятой.indexOf(a[i])==0
в этом случае нет сбережений.Python 2, 48
51байтДля каждого элемента
a
изl
, функцияa.find
находит индекс первого вхожденияa
во входной строке, давая-1
для отсутствия. Итак,0
указывает префикс. В списке без префиксов отображение этой функции возвращает только один0
дляa
себя. Функция проверяет, что это так для каждогоa
.51 байт:
Замените
~
символ с кодом ASCII 128 или выше.Для каждого элемента
a
вl
, копия включена для каждого элемента, который является его префиксом. Для списка без префиксов единственным таким элементом являетсяa
сам по себе, так что это дает исходный список.источник
CJam, 14 байтов
Тестирование.
объяснение
источник
JavaScript ES6,
654340 байтМое предыдущее решение, которое обрабатывало строковые массивы всех символов UTF-8:
Мне удалось избежать,
JSON.stringify
так как задача определяет только печатные символы ASCII.Тест
источник
Haskell, 49 байтов
Это имеет несколько частей:
Если два списка равны, то элемент является только префиксом самого себя, и он действителен.
источник
Сетчатка , 19 байт
Число байтов предполагает кодировку ISO 8859-1.
Входные данные должны быть разделены переводом строки. Вывод
0
для фальши и1
правды.Попробуйте онлайн! (Немного изменен для поддержки нескольких разделенных пробелами тестовых случаев вместо этого.)
объяснение
Сортировка строк на входе. Если префикс существует, он окажется прямо перед строкой, которая его содержит.
Попробуйте сопоставить (
M
) полную строку, которая также находится в начале следующей строки.m
Активизирует многострочный режим таким образом, что^
матчи линии начала и1
гарантирует , что мы только рассчитывать на максимум один матч , так что выход0
или1
.Чтобы поменять местами
0
и1
в результате мы посчитаем количество0
с.источник
Java, 97 байт
Использует большинство приемов, найденных в ответе @ Marv , но также использует цикл foreach и равенство ссылок на строки.
Unminified:
Обратите внимание, что, как я уже сказал, здесь используется равенство строк. Это означает, что код может вести себя странно из-за интернирования String . Код работает при использовании аргументов, переданных из командной строки, а также при использовании чего-то, считываемого из командной строки. Если вы хотите жестко закодировать значения для тестирования, вам нужно вручную вызвать конструктор String, чтобы интернирование не происходило:
источник
PostgreSQL,
186, 173 байтаВыход:
На этот раз нет живой демо. http://sqlfiddle.com поддерживает только 9.3 и для запуска этой демонстрации 9.4 требуется.
Как это работает:
y
LEFT OUTER JOIN
к той же производной таблице, основанной на том жеi
(id), но с другим,oridinal
которые начинаются с префиксаy.z LIKE u.z||'%'
c
(начальный массив) и использоватьEVERY
функцию группировки. Если каждая строка из второй таблицыIS NULL
означает, что префиксов нет.Введите, если кому-то интересно:
РЕДАКТИРОВАТЬ:
SQL Server 2016+
реализация:LiveDemo
Примечание. Это список, разделенный запятыми, а не реальный массив. Но основная идея такая же, как в
PostgreSQL
.РЕДАКТИРОВАТЬ 2:
На самом деле
WITH ORDINALITY
можно заменить:SqlFiddleDemo
источник
Брахилог , 8 байт
Попробуйте онлайн!
Выходы через предикат успеха / неудачи. Занимает более 60 секунд в последнем достоверном тестовом примере,
["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"]
но быстро передает его с добавленным байтом, который исключает большое количество возможностей раньше, чем программа делает иначе (Ċ
перед проверкой перестановок, а неᵈ
после проверок перестановок, чтобы ограничить длину подсписка до два).Менее тривиальные 9 байт вариантов , чем
¬(⊇Ċpa₀ᵈ)
которые выполняются в разумных сроках являются¬(⊇o₁a₀ᵈ)
,¬(⊇o↔a₀ᵈ)
и¬(⊇oa₀ᵈ¹)
.источник
Perl 6 , 24 байта
Попробуйте онлайн!
Вау, на удивление коротко при использовании длинного встроенного.
объяснение
источник
Ракетка, 70 байт
источник
Python,
5855 байтисточник
a.index(b)==0
немного короче. В качестве альтернативы, вы могли бы сделать0**sum(a.index(b)for a in l for b in l)
.index
выдает исключение, когдаb
не найдено. А потому что так и должно быть==
, нет>=
. Однакоfind
работает. (И это тоже короче!)find
. Сонный мозг сонный. Вторая версия также должна работатьfind
.len(l)
заключается в том, что, поскольку мы перебираем всеb
s для каждогоa
, всегда будет хотя бы одно совпадение для каждогоa
. Поэтому мы проверяем, совпадает ли количество совпадений с количеством элементов.JavaScript (ES6), 52
54Редактирование 2 байт сохраненного ТНХ @Neil
Тест
источник
!w.indexOf(v)
?Mathematica
75 6968 байтБолтливый как обычно. Но Мартин Б смог уменьшить код на 7 байтов.
Метод 1: Сохранение вывода в
Array
(68 байт)
Метод 2: Сохранение вывода в
List
(69 байт)
источник
a~Drop~{#}~StringStartsQ~a[[#]]
работать. ТакжеArray
следует сохранить несколько байтовLength
, особенно потому, что это позволит вам использоватьJoin@@
вместоFlatten@
(при условии, что вы используетеFlatten
только для одного уровня).Array
позже.Mathematica, 41 байт
источник
APL (Dyalog Unicode) , 13 байтов SBCS
-2 байта:
Попробуйте онлайн!
Объяснение:
источник
~2∊+\⊃¨∘.⍷⍨⎕
J , 17 байт
Попробуйте онлайн!
Примечание: я действительно написал это, прежде чем посмотреть на ответ APL, чтобы подойти к нему без предвзятости. Оказывается, подходы практически идентичны, что интересно. Я думаю, что это естественное решение для "массива мышления"
Возьмите вход в штучной упаковке, потому что строки имеют неравную длину.
Создайте таблицу функций
/~
каждого элемента в паре с каждым элементом и посмотрите, есть ли совпадение в начале{.@E.
. Это даст матрицу результатов 1-0.Суммируйте его дважды,
1#.1#.
чтобы получить одно число, представляющее «все единицы в матрице», и посмотрите, совпадает ли это число с длиной ввода#=
. Если это так, то единственным совпадением префикса являются сам совпадения, т. Е. У нас есть код префикса.сортировочное решение, 18 байт
Попытка при другом подходе. Это решение сортирует и смотрит на соседние пары.
Попробуйте онлайн!
источник
R , 48 байт
Попробуйте онлайн!
Объяснение:
outer(s,s,startsWith)
выводит матрицу логики, проверяющую,s[i]
является ли префиксs[j]
. Еслиs
это префиксный код, то в результате есть ровноlength(s)
ИСТИННЫЕ элементы, соответствующие диагональным элементам (s[i]
сам по себе является префиксом).источник
function(s)all(colSums(outer(s,s,startsWith))<2)
но этоstartsWith
функция, о которой я не знал! Хорошая находка.TRUE
иFALSE
...==
на>
. :-))Pyth -
1312 байтПопробуйте это онлайн здесь .
источник
Рубин, 48 байтов
Использует аргументы в качестве входных данных и стандартный вывод в качестве выходных.
источник
Скала, 71 байт
источник
Ракетка 130 байт
Ungolfed:
Тестирование:
Выход:
источник
C (gcc) , 93 байта
Попробуйте онлайн!
Простое двойное использование цикла
strstr(a,b)==a
для проверки предпочтений. В основном добавлено, поскольку пока не существует ответа C.источник
05AB1E , 13 байтов
Слишком долго. Изначально у меня было 9-байтовое решение, но в тестовом случае с дублированным ключом оно не удалось.
Попробуйте онлайн или проверьте все контрольные примеры .
Объяснение:
источник
Japt , 8 байт
Попытайся
источник
C # (интерактивный компилятор Visual C #) , 70 байт
Попробуйте онлайн!
источник
Stax , 6 байт
Запустите и отладьте его
Это производит ненулевой для правды.
Общая идея заключается в рассмотрении каждой пары строк на входе. Если индекс подстроки одного в другом всегда равен нулю, то это неверный префиксный код. В stax возвращается индекс несуществующей подстроки
-1
. Таким образом, все индексы парных подстрок могут быть умножены вместе.Это тот же алгоритм, что и в pyth-решении Исаака, но я разработал его независимо.
источник