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.

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).

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.

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

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.

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.

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>

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.

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.

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")}));

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:

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

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₀ᵈ¹).

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)

Raquette, 70 octets

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))

Python, 58 à 55 octets

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)

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>

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]

Mathematica, 41 octets

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&

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

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!

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).

Pyth - 13 12 octets

!ssmm}d._k-Q

Essayez-le en ligne ici .

Ruby, 48 octets

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

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

Scala, 71 octets

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

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

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.

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)

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)

C # (compilateur interactif Visual C #) , 70 octets

l=>!l.Any(x=>l.Where((y,i)=>l.IndexOf(x)!=i).Any(z=>z.StartsWith(x)));

Essayez-le en ligne!

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.