Est-ce un code de préfixe?

33

En théorie de l'information, un "code de préfixe" est un dictionnaire dans lequel aucune des clés n'est un préfixe d'un autre. En d'autres termes, cela signifie qu'aucune des chaînes ne commence par aucune des autres.

Par exemple, {"9", "55"}est un code de préfixe, mais {"5", "9", "55"}n'est pas.

Le principal avantage de ceci est que le texte encodé peut être écrit sans séparateur entre eux et qu'il sera toujours déchiffrable de manière unique. Cela apparaît dans des algorithmes de compression tels que le codage de Huffman , qui génère toujours le code de préfixe optimal.

Votre tâche est simple: à partir d’une liste de chaînes, déterminez s’il s’agit ou non d’un code de préfixe valide.

Votre contribution:

  • Sera une liste de chaînes dans un format raisonnable .

  • Ne contiendra que des chaînes ASCII imprimables.

  • Ne contiendra aucune chaîne vide.

Votre sortie sera une valeur de vérité / falsey : vérité si c'est un code de préfixe valide, et falsey si ce n'est pas le cas.

Voici quelques cas de test réels:

["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"]

Voici quelques cas de test faux:

["4", "42"]                             
["1", "2", "3", "34"]                   
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]

C'est du code-golf, donc les échappatoires standard s'appliquent, et la réponse la plus courte en octets est gagnante.

DJMcMayhem
la source
Voulez-vous une valeur de vérité cohérente ou pourrait-elle être par exemple "un nombre entier positif" (qui peut varier entre différentes entrées).
Martin Ender
@ MartinBüttner N'importe quel entier positif convient.
DJMcMayhem
@DrGreenEggsandHamDJ Je ne pense pas que cette réponse vise à aborder la cohérence des résultats, d'où la question. ;)
Martin Ender
Juste par curiosité: le défi dit: "Le plus grand avantage de cela est que le texte encodé peut être écrit sans séparateur entre eux et qu'il sera toujours déchiffrable de manière unique.". Comment quelque chose comme 001être uniquement déchiffrable? Ce pourrait être l'un 00, 1ou l' autre 0, 11.
Joba
2
@Joba Cela dépend de ce que sont vos clés. Si vous avez 0, 00, 1, 11toutes les clés, il ne s'agit pas d'un préfixe-code, car 0 correspond au préfixe 00 et 1 au préfixe 11. Un code de préfixe indique qu'aucune des clés ne commence par une autre clé. Ainsi, par exemple, si vos clés sont, 0, 10, 11il s’agit d’un code de préfixe et uniquement déchiffrable. 001n'est pas un message valide, mais 0011ou 0010sont uniquement déchiffrable.
DJMcMayhem

Réponses:

11

Pyth, 8 octets

.AxM.PQ2

Suite de tests

Prenez les 2 permutations d'éléments de l'entrée, mappez chacune sur l'index d'une chaîne dans l'autre (0 pour un préfixe) et indiquez si tous les résultats sont vrais (non nuls).

isaacg
la source
12

Haskell, 37 octets

f l=[x|x<-l,y<-l,zip x x==zip x y]==l

Chaque élément xde lest répété une fois pour chaque élément dont il s'agit d'un préfixe, ce qui correspond exactement à une liste pour une liste sans préfixe, ce qui donne la liste d'origine. La propriété de préfixe est vérifiée en zippant les deux listes avec x, ce qui coupe les éléments au-delà de x.

Xnor
la source
C'est une solution élégante (+1)
Michael Klein
9

Java, 128 127 126 125 124 121 121 octets

(Merci @Kenny Lau, @Maltysen, @Patrick Roberts, @Joba)

Object a(String[]a){for(int i=0,j,l=a.length;i<l;i++)for(j=0;j<l;)if(i!=j&a[j++].startsWith(a[i]))return 1<0;return 1>0;}

Ungolfed

Object a(String[] a) {
    for (int i = 0, j, l = a.length; i < l; i++) 
        for (j = 0; j < l;) 
            if (i != j & a[j++].startsWith(a[i])) return 1<0;
    return 1>0;
}

Sortie

[Hello, World]
true

[Code, Golf, Is, Cool]
true

[1, 2, 3, 4, 5]
true

[This, test, case, is, true]
true

[111, 010, 000, 1101, 1010, 1000, 0111, 0010, 1011, 0110, 11001, 00110, 10011, 11000, 00111, 10010]
true

[4, 42]
false

[1, 2, 3, 34]
false

[This, test, case, is, false, t]
false

[He, said, Hello]
false

[0, 00, 00001]
false

[Duplicate, Duplicate, Keys, Keys]
false
Marv
la source
1
Idk sur Java, mais &travaillerait au lieu de &&?
Maltysen
1
Oui, enregistre un autre octet. En Java, l’utilisation d’opérateurs au niveau des bits avec des opérandes booléens se comporte comme les opérateurs logiques normaux, à la différence près qu’ils ne court-circuitent pas ce qui n’est pas nécessaire dans ce cas.
Mars
Ne pourriez-vous pas simplement changer le type de retour de la fonction intet renvoyer 0et 1? Cela permettrait d'économiser plusieurs octets. Aussi j'oublie si cela est valable en Java mais si vous déclarez i, jet à l' lintérieur de l'extérieur forboucle qui sauverait un octet d'un moins - virgule.
Patrick Roberts
@ PatrickRoberts Maltysen a déjà suggéré cela auparavant, mais cela n’est pas valable selon la définition la plus élevée du vote vérité / falsey . Mettre les déclarations dans la boucle est cependant parfaitement valide et assez évident maintenant que j'y réfléchis. Est ce que vous obtenez pour jouer au golf à 4 heures du matin: ^)
Marv
3
@Joba Je suis presque sûr que ce n'est pas valide, car indexOf renvoie -1 lorsque la chaîne n'est pas trouvée. il faudrait le faire, indexOf(a[i])==0auquel cas il n'y aurait pas d'économies.
Pokechu22
6

Python 2, 48 51 octets

lambda l:all(1/map(a.find,l).count(0)for a in l)

Pour chaque élément ade l, la fonction a.findtrouve l'index de la première occurrence de adans la chaîne d'entrée, donnant -1une absence. Donc, 0indique un préfixe. Dans une liste sans préfixe, le mappage cette fonction retourne une seule 0pour alui - même. La fonction vérifie que c'est le cas pour tous a.


51 octets:

lambda l:[a for a in l for b in l if b<=a<b+'~']==l

Remplacez-le ~par un caractère de code ASCII 128 ou supérieur.

Pour chaque élément adans lune copie est incluse pour chaque élément qui est un préfixe de celui - ci. Pour une liste sans préfixe, le seul élément de ce type est alui - même, ce qui donne la liste d'origine.

Xnor
la source
4

CJam, 14 octets

q~$W%2ew::#0&!

Suite de tests.

Explication

q~   e# Read and evaluate input.
$    e# Sort strings. If a prefix exists it will end up directly in front 
     e# of a string which contains it.
W%   e# Reverse list.
2ew  e# Get all consecutive pairs of strings.
::#  e# For each pair, find the first occurrence of the second string in the first.
     e# If a prefix exists that will result in a 0, otherwise in something non-zero.
0&   e# Set intersection with 0, yielding [0] for falsy cases and [] for truthy ones.
!    e# Logical NOT.
Martin Ender
la source
4

JavaScript ES6, 65 43 40 octets

a=>!/(.*)\1/.test(''+a.sort().join``)
      ^            ^               ^ embedded NUL characters

Ma solution précédente, qui traitait les tableaux de chaînes de tous les caractères UTF-8:

a=>!/[^\\]("([^"]*\\")*[^\\])",\1/.test(JSON.stringify(a.sort()))

J'ai pu éviter JSON.stringifycar le défi spécifie uniquement les caractères ASCII imprimables.

Tester

f=a=>!/(\0.*)\1/.test('\0'+a.sort().join`\0`) // since stackexchange removes embedded NUL characters

O.textContent += 'OK: '+
[["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"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))
<pre id=O></pre>

Patrick Roberts
la source
3

Haskell, 49 octets

g x=[1|z<-map((and.).zipWith(==))x<*>x,z]==(1<$x)

Cela a deux parties:

-- Are two lists (or strings) equal for their first min(length_of_1,length_of_2) elements, i.e. is one the prefix of the other?
(and.).zipWith(==)

-- Check whether one element is the prefix of the other, for all pairs of elements (including equal pairs)
map((and.).zipWith(==))x<*>x

-- This is a list of 1's of length (number of elements that are the prefix of the other)
[1|z<-map((and.).zipWith(==))x<*>x,z]

-- This is the input list, with all the elements replaced with 1's
(1<$x)

Si les deux listes sont égales, un élément n'est que son préfixe et est valide.

Michael Klein
la source
3

Retina , 19 octets

Le nombre d'octets suppose un codage ISO 8859-1.

O`.+
Mm1`^(.+)¶\1
0

L'entrée doit être séparée par saut de ligne. La sortie est 0pour la fausseté et 1pour la vérité.

Essayez-le en ligne! (Légèrement modifié pour prendre en charge plusieurs scénarios de test séparés par des espaces.)

Explication

O`.+

Triez les lignes dans l'entrée. Si un préfixe existe, il se terminera directement devant une chaîne qui le contient.

Mm1`^(.+)¶\1

Essayez de faire correspondre ( M) une ligne complète qui se trouve également au début de la ligne suivante. Le mmode multiligne activé ^correspond aux débuts de ligne et 1garantit que nous comptons au plus une correspondance telle que la sortie soit 0ou 1.

0

Pour échanger 0et 1dans le résultat, nous comptons le nombre de 0s.

Martin Ender
la source
3

Java, 97 octets

Object a(String[]a){for(String t:a)for(String e:a)if(t!=e&t.startsWith(e))return 1<0;return 1>0;}

Utilise la plupart des astuces trouvées dans la réponse de @ Marv , mais utilise également l'égalité de la boucle foreach et de la référence de chaîne.

Non minée:

Object a(String[]a){
    for (String t : a)
        for (String e : a)
            if (t != e & t.startsWith(e))
                return 1<0;
    return 1>0;
}

Notez que, comme je l’ai dit, cela utilise une égalité de référence de chaîne. Cela signifie que le code peut se comporter étrangement en raison de l' internalisation de chaîne . Le code fonctionne lorsque vous utilisez des arguments transmis à partir de la ligne de commande, ainsi que lorsqu’un élément lu à partir de la ligne de commande est utilisé. Si vous souhaitez coder en dur les valeurs à tester, vous devrez cependant appeler manuellement le constructeur String pour que l'internement ne se produise pas:

System.out.println(a(new String[] {new String("Hello"), new String("World")}));
System.out.println(a(new String[] {new String("Code"), new String("Golf"), new String("Is"), new String("Cool")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("4"), new String("5")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("true")}));
System.out.println(a(new String[] {new String("111"), new String("010"), new String("000"), new String("1101"), new String("1010"), new String("1000"), new String("0111"), new String("0010"), new String("1011"), new String("0110"), new String("11001"), new String("00110"), new String("10011"), new String("11000"), new String("00111"), new String("10010")}));
System.out.println(a(new String[] {new String("4"), new String("42")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("34")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("false"), new String("t")}));
System.out.println(a(new String[] {new String("He"), new String("said"), new String("Hello")}));
System.out.println(a(new String[] {new String("0"), new String("00"), new String("00001")}));
System.out.println(a(new String[] {new String("Duplicate"), new String("Duplicate"), new String("Keys"), new String("Keys")}));
Pokechu22
la source
@Jo King Voir la seconde partie de ma réponse; c'est un peu compliqué et dépend de la façon dont l'entrée est spécifiée. Cependant, je ne me rappelle pas avoir écrit cela
Pokechu22 le
3

PostgreSQL, 186 , 173 octets

WITH y AS(SELECT * FROM t,LATERAL unnest(c)WITH ORDINALITY s(z,r))
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

Sortie:

entrez la description de l'image ici

Pas de démo en direct cette fois. http://sqlfiddle.com ne prend en charge que la version 9.3 et pour exécuter cette démonstration, la version 9.4 est requise.

Comment ça marche:

  1. Scinder le tableau de chaînes avec un nombre et le nommer y
  2. Obtenez tout y
  3. LEFT OUTER JOINvers la même table dérivée basée sur le même i(id), mais avec des oridinalnoms différents commençant par préfixey.z LIKE u.z||'%'
  4. Regrouper les résultats en fonction de c(tableau initial) et utiliser la EVERYfonction de regroupement. Si chaque ligne de la deuxième table IS NULLsignifie qu’il n’ya pas de préfixe.

Entrée si quelqu'un est intéressé:

CREATE TABLE t(i SERIAL,c text[]);

INSERT INTO t(c)
SELECT '{"Hello", "World"}'::text[]
UNION ALL SELECT  '{"Code", "Golf", "Is", "Cool"}'
UNION ALL SELECT  '{"1", "2", "3", "4", "5"}'
UNION ALL SELECT  '{"This", "test", "case", "is", "true"}'         
UNION ALL SELECT  '{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011","0110", "11001", "00110", "10011", "11000", "00111", "10010"}'
UNION ALL SELECT  '{"4", "42"}'
UNION ALL SELECT  '{"1", "2", "3", "34"}'                   
UNION ALL SELECT  '{"This", "test", "case", "is", "false", "t"}'
UNION ALL SELECT  '{"He", "said", "Hello"}'
UNION ALL SELECT  '{"0", "00", "00001"}'
UNION ALL SELECT  '{"Duplicate", "Duplicate", "Keys", "Keys"}';

MODIFIER:

SQL Server 2016+ la mise en oeuvre:

WITH y AS (SELECT *,z=value,r=ROW_NUMBER()OVER(ORDER BY 1/0) FROM #t CROSS APPLY STRING_SPLIT(c,','))
SELECT y.c, IIF(COUNT(u.z)>0,'F','T')
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z+'%' 
GROUP BY y.c;

LiveDemo

Note: C'est une liste séparée par des virgules, pas un vrai tableau. Mais l’idée principale est la même que dans PostgreSQL.


EDIT 2:

En fait, WITH ORDINALITYpourrait être remplacé:

WITH y AS(SELECT *,ROW_NUMBER()OVER()r FROM t,LATERAL unnest(c)z)
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

SqlFiddleDemo

lad2025
la source
3

Brachylog , 8 octets

¬(⊇pa₀ᵈ)

Essayez-le en ligne!

Sorties via prédicat succès / échec. Prend plus de 60 secondes sur le dernier cas de test truthy ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] mais passe rapidement avec un octet supplémentaire qui élimine un grand nombre de possibilités plus tôt que le programme ne les ( Ċavant de vérifier les permutations plutôt que après les permutations de contrôle, afin de limiter la longueur de la sous - liste à deux).

¬(     )    It cannot be shown that
   p        a permutation of
  ⊇         a sublist of the input
      ᵈ     is a pair of values [A,B] such that
    a₀      A is a prefix of B.

Moins trivial 9 octets variantes que ¬(⊇Ċpa₀ᵈ)qui fonctionnent dans des délais raisonnables sont ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ)et ¬(⊇oa₀ᵈ¹).

Chaîne non liée
la source
Si ce défi utilisait "deux valeurs distinctes et cohérentes" au lieu de "vérité / fausseté", cela ne prendrait que 5 octets.
Unrelated String
2

Perl 6 , 24 octets

{.all.starts-with(.one)}

Essayez-le en ligne!

Wow, étonnamment court tout en utilisant un long intégré.

Explication

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)
Jo King
la source
J'ai écrit une réponse de 50 octets mais la tienne vient de faire sauter la mienne hors de l'eau.
bb94 le
1
@ bb94 Oui, j'ai commencé avec une réponse similaire, mais j'ai rencontré le même problème que le vôtre, avec des ensembles avec des clés dupliquées qui renvoient la vérité. Écrire cette réponse était incroyablement satisfaisant
Jo King
1

Raquette, 70 octets

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))
Winny
la source
1

Python, 58 à 55 octets

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)
DJMcMayhem
la source
a.index(b)==0est un peu plus court. Alternativement, vous pourriez faire 0**sum(a.index(b)for a in l for b in l).
Mego
@ Mego Cela ne fonctionne pas car indexlève une exception quand best introuvable. Et parce que ça devrait l'être ==, non >=. Cependant, findfonctionne. (Et c'est plus court aussi!)
DJMcMayhem
Oups, je voulais taper find. Cerveau endormi est somnolent. La deuxième version devrait également fonctionner avec find.
Mego
@ Mego Je ne suis pas sûr d'avoir la deuxième version. Cela ne retournerait-il pas toujours 0?
DJMcMayhem
@ Mego Cela ne fonctionne que si toutes les chaînes sont identiques. La raison pour laquelle nous le comparons len(l)est que puisque nous parcourons tous les bs a, il y aura toujours au moins un match par match a. Nous vérifions donc si le nombre de correspondances est le même que le nombre d'éléments.
DJMcMayhem
1

JavaScript (ES6), 52 54

Éditez 2 octets enregistrés thx @Neil

a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

Tester

f=a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

O.textContent += 'OK: '+
[["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"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))
<pre id=O></pre>

edc65
la source
!w.indexOf(v)?
Neil
@Neil à droite, merci
edc65
1

Mathematica 75 69 68 octets

Loquace comme d'habitude. Mais Martin B a pu réduire le code de 7 octets.

Méthode 1: stockage de la sortie dans un Array

(68 octets)

f@a_:=!Or@@(Join@@Array[a~Drop~{#}~StringStartsQ~a[[#]]&,Length@a])

f@{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", "0110", "11001", "00110", "10011", "11000", "00111", "10010"}

Vrai


f@{"He", "said", "Hello"}

Faux


Méthode 2: stockage de la sortie dans un List

(69 octets)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]
DavidC
la source
Les règles de priorité devraient faire l' a~Drop~{#}~StringStartsQ~a[[#]]affaire. Vous Arraydevriez aussi économiser quelques octets Length, surtout parce que cela vous permettra d’utiliser Join@@plutôt que de Flatten@(à condition que vous n’utilisiez Flattenque pour un seul niveau).
Martin Ender
Merci pour la suggestion. Je regarderai Arrayplus tard.
DavidC
1

Mathematica, 41 octets

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&
Un simmons
la source
1

APL (Dyalog Unicode) , SBCS 13 octets

-2 octets:

≢=∘≢∘⍸∘.(⊃⍷)⍨

Essayez-le en ligne!

Explication:

≢=∘≢∘⍸∘.(⊃⍷)⍨   Monadic function train
               "Find": Convert the right argument into a boolean vector,
                where ones correspond to instances of the left argument
              Take the first item of the above vector (i.e., only prefixes)
     ∘.(  )⍨   Commutative outer product: take the above function and apply
               it for each possible pair of elements in the input
               If the input is a prefix code, the above should have a number of ones
               equal to the length of the input (i.e., each item is a prefix of only itself)
               To test this...
              Find the location of all ones in the above
   ≢∘          Take the length of the above
≢=∘            Compare to the length of the input
voidhawk
la source
~2∊+\⊃¨∘.⍷⍨⎕­
NDGN
1

J , 17 octets

#=1#.1#.{.@E.&>/~

Essayez-le en ligne!

Note: En fait, j’ai écrit ceci avant de regarder la réponse de l’APL pour l’aborder sans parti pris. Il s'avère que les approches sont presque identiques, ce qui est intéressant. Je suppose que c’est la solution naturelle de "matrice de tableaux"

Prenez une entrée en boîte car les chaînes sont de longueur inégale.

Créez une table /~de fonctions propres de chaque élément associé à chaque élément et voyez s'il y a une correspondance au début {.@E.. Cela produira une matrice de 1-0 résultats.

1#.1#.Faites la somme deux fois pour obtenir un nombre unique représentant "toutes les unités de la matrice" et voyez si ce nombre est identique à la longueur de l'entrée #=. Si c'est le cas, les seules correspondances de préfixe sont des correspondances automatiques, c'est-à-dire que nous avons un code de préfixe.

solution de tri, 18 octets

0=1#.2{.@E.&>/\/:~

Tentative d'approche différente. Cette solution trie et examine les paires adjacentes.

Essayez-le en ligne!

Jonas
la source
1

R , 48 octets

function(s)sum(outer(s,s,startsWith))==length(s)

Essayez-le en ligne!

Explanation: outer(s,s,startsWith)génère une matrice de logiques en vérifiant s'il s[i]s'agit ou non d'un préfixe s[j]. Si sest un code de préfixe, alors il y a exactement des length(s)éléments VRAI dans le résultat, correspondant aux éléments diagonaux ( s[i]est un préfixe de lui-même).

Robin Ryder
la source
1
J'ai trouvé un tas d'autres alternatives à 48 octets, function(s)all(colSums(outer(s,s,startsWith))<2)mais il reste que startsWithc'est une fonction que je ne connaissais pas! Belle trouvaille.
Giuseppe
1
@ Giuseppe J'ai essayé plusieurs façons de vérifier si la matrice est une matrice d'identité, mais je ne pouvais pas l'obtenir sous 48 octets non plus. Je pensais que c'était le moyen le plus facile à comprendre, mais je suis sûr que quelqu'un va jouer au golf!
Robin Ryder
47 octets en inversant TRUEet FALSE...
Giuseppe
@ Giuseppe Est-ce permis? Les règles demandent explicitement la vérité lorsque l'entrée est un code de préfixe valide. (Votre lien également vers la version à 48 octets, mais je suppose que votre suggestion est de remplacer == par >. :-))
Robin Ryder Le
0

Ruby, 48 octets

Utilise les arguments comme entrée et stdout comme sortie.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?
ezrast
la source
0

Scala, 71 octets

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)
Jacob
la source
0

Raquette 130 octets

(define g #t)(for((n(length l)))(for((i(length l))#:unless(= i n))(when(string-prefix?(list-ref l i)(list-ref l n))(set! g #f))))g

Ungolfed:

(define(f l)
  (define g #t)
  (for ((n (length l)))
    (for ((i (length l)) #:unless (= i n))
      (when (string-prefix? (list-ref l i) (list-ref l n))
        (set! g #f))))g)

Essai:

(f [list "Hello" "World"])             
(f [list "Code" "Golf" "Is" "Cool"])
(f [list "1" "2" "3" "4" "5"])
(f [list "This" "test" "case" "is" "true"])          
(f [list "111" "010" "000" "1101" "1010" "1000" "0111" "0010" "1011" 
         "0110" "11001" "00110" "10011" "11000" "00111" "10010"])

(f [list "4" "42"])                             
(f [list "1" "2" "3" "34"])                   
(f [list "This" "test" "case" "is" "false" "t"])
(f [list "He" "said" "Hello"])
(f [list "0" "00" "00001"])
(f [list "Duplicate" "Duplicate" "Keys" "Keys"])

Sortie:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f
rnso
la source
0

C (gcc) , 93 octets

p(r,e,f,i,x)char**r;{for(f=i=0;i<e;++i)for(x=0;x<e;++x)f|=x!=i&&strstr(r[i],r[x])==r[i];r=f;}

Essayez-le en ligne!

Double simple pour la boucle en utilisant strstr(a,b)==apour vérifier les préfices. Principalement ajouté puisqu'il ne semble pas encore y avoir de réponse en C.

LambdaBeta
la source
88 octets
ceilingcat le
0

05AB1E , 13 octets

2.ÆDí«ε`Å?}O_

Trop long .. Au départ, j’avais une solution de 9 octets, mais elle a échoué pour le scénario de test de clé dupliqué.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

2.Æ             # Get all combinations of two elements from the (implicit) input-list
   Dí           # Duplicate and reverse each pair
     «          # Merge the lists of pairs together
      ε         # Map each pair to:
       `        #  Push both strings to the stack
        Å?      #  And check if the first starts with the second
          }O    # After the map: sum to count all truthy values
            _   # And convert it to truthy if it's 0 or falsey if it's any other integer
                # (which is output implicitly as result)
Kevin Cruijssen
la source
0

Japt , 8 octets

á2 ËrbÃe

L'essayer

á2 ËrbÃe     :Implicit input of array
á2           :Permutations of length 2
   Ë         :Map each pair
    r        :  Reduce by
     b       :  Get the index of the second in the first - 0 (falsey) if it's a prefix
      Ã      :End map
       e     :All truthy (-1 or >0)
Hirsute
la source
0

Stax , 6 octets

å·↑↑¶Ω

Exécuter et déboguer

Cela produit non-zéro pour la vérité.

L'idée générale est de considérer chaque paire de chaînes de l'entrée. Si l'indice de sous-chaîne de l'un dans l'autre est égal à zéro, il ne s'agit pas d'un code de préfixe valide. En stax, l'index d'une sous-chaîne non existante donne -1. De cette façon, tous les index de sous-chaîne par paire peuvent être multipliés ensemble.

Il s’agit du même algorithme que la solution pyth d’isaacg, mais je l’ai développé indépendamment.

récursif
la source