Is it a prefix code?

Question

In information theory, a "prefix code" is a dictionary where none of the keys are a prefix of another. In other words, this means that none of the strings starts with any of the other.

For example, {"9", "55"} is a prefix code, but {"5", "9", "55"} is not.

The biggest advantage of this, is that the encoded text can be written down with no separator between them, and it will still be uniquely decipherable. This shows up in compression algorithms such as Huffman coding, which always generates the optimal prefix code.

Your task is simple: Given a list of strings, determine whether or not it is a valid prefix code.

Your input:

• Will be a list of strings in any reasonable format.

• Will only contain printable ASCII strings.

• Will not contain any empty strings.

Your output will be a truthy/falsey value: Truthy if it's a valid prefix code, and falsey if it isn't.

Here are some true test cases:

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

Here are some false test cases:

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

This is code-golf, so standard loopholes apply, and shortest answer in bytes wins.

Answer 1

Pyth, 8 bytes

.AxM.PQ2

Test suite

Take all 2 element permutations of the input, map each to the index of one string in the other (0 for a prefix) and return whether all results are truthy (non-zero).

Answer 2

Haskell, 37 bytes

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

Each element x of l is repeated once for every element that it's a prefix of, which is exactly once for a prefix-free list, giving the original list. The prefix property is checked by zipping both lists with x, which cuts off elements beyond the length of x.

Answer 3

Java, 128 127 126 125 124 121 bytes

(Thanks @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;
}

Output

[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

Answer 4

Python 2, 48 51 bytes

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

For each element a of l, the function a.find finds the index of the first occurrence of a in the input string, giving -1 for an absence. So, 0 indicates a prefix. In a prefix-free list, mapping this function returns only a single 0 for a itself. The function checks that this is the case for every a.

---

51 bytes:

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

Replace ~ with a character with ASCII code 128 or higher.

For each element a in l, a copy is included for each element that's a prefix of it. For a prefix-free list, the only such element is a itself, so this gives the original list.

Answer 5

CJam, 14 bytes

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

Test suite.

Explanation

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.

Answer 6

JavaScript ES6, 65 43 40 bytes

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

My previous solution, which handled string arrays of all UTF-8 characters:

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

I was able to avoid JSON.stringify since the challenge specifies printable ASCII characters only.

Test

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>

Answer 7

Haskell, 49 bytes

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

This has a couple parts:

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

If the two lists are equal, then an element is only the prefix of itself, and it's valid.

Answer 8

Retina, 19 bytes

Byte count assumes ISO 8859-1 encoding.

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

The input should be linefeed-separated. Output is 0 for falsy and 1 for truthy.

Try it online! (Slightly modified to support multiple space-separated test cases instead.)

Explanation

O`.+

Sort the lines in the input. If a prefix exists it will end up directly in front of a string which contains it.

Mm1`^(.+)¶\1

Try to match (M) a complete line which is also found at the beginning of the next line. The m activates multiline mode such that ^ matches line beginnings and the 1 ensures that we only count at most one match such that the output is 0 or 1.

0

To swap 0 and 1 in the result, we count the number of 0s.

Answer 9

Java, 97 bytes

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

Uses most of the tricks found in @Marv's answer, but also makes use of the foreach loop and string reference equality.

Unminified:

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

Note that, as I said, this uses string reference equality. That does mean that the code can behave oddly due to String interning. The code does work when using arguments passed from the command line, and also when using something read from the command line. If you want to hardcode the values to test, though, you'd need to manually call the String constructor to force interning to not occur:

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

Answer 10

PostgreSQL, 186, 173 bytes

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

Output:

No live demo this time. http://sqlfiddle.com supports only 9.3 and to run this demo 9.4 is required.

How it works:

1. Split string array with number and name it y
2. Get all y
3. LEFT OUTER JOIN to the same derived table based on the same i(id), but with different oridinal that start with prefix y.z LIKE u.z||'%'
4. Group result based on c (initial array) and use EVERY grouping function. If every row from second table IS NULL it means there is no prefixes.

---

Input if someone is interested:

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

EDIT:

SQL Server 2016+ implementation:

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: It is comma separated list, not real array. But the main idea is the same as in PostgreSQL.

---

EDIT 2:

Actually WITH ORDINALITY could be replaced:

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

Answer 11

Brachylog, 8 bytes

¬(⊇pa₀ᵈ)

Try it online!

Outputs through predicate success/failure. Takes more than 60 seconds on the last truthy test case ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] but passes it quickly with an added byte which eliminates a large number of possibilities earlier than the program does otherwise (Ċ before checking permutations rather than ᵈ after checking permutations, to limit the length of the sublist to two).

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

Less trivial 9-byte variants than ¬(⊇Ċpa₀ᵈ) which run in reasonable time are ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ), and ¬(⊇oa₀ᵈ¹).

Answer 12

Perl 6, 24 bytes

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

Try it online!

Wow, surprisingly short while using a long built-in.

Explanation

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)

Answer 13

Racket, 70 bytes

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

Answer 14

JavaScript (ES6), 52 54

Edit 2 bytes saved thx @Neil

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

Test

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>

Answer 15

Mathematica 75 69 68 bytes

Loquacious as usual. But Martin B was able to reduce the code by 7 bytes.

Method 1: Storing output in an Array

(68 bytes)

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

True

---

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

False

---

Method 2: Storing output in a List

(69 bytes)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]

Answer 16

Mathematica, 41 bytes

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

Answer 17

APL (Dyalog Unicode), 13 bytes^SBCS

-2 bytes:

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

Try it online!

Explanation:

≢=∘≢∘⍸∘.(⊃⍷)⍨  ⍝ 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

Answer 18

J, 17 bytes

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

Try it online!

Note: I actually wrote this before looking at the APL answer, to approach it without bias. Turns out the approaches are almost identical, which is interesting. I guess this is the natural "array thinknig" solution

Take boxed input because the strings are of unequal length.

Create a self-function table /~ of each element paired with each element and see if there is a match at the start {.@E.. This will produce a matrix of 1-0 results.

Sum it twice 1#.1#. to get a single number representing "all ones in the matrix", and see if that number is the same as the length of the input #=. If it is, the only prefix matches are self matches, ie, we have a prefix code.

sorting solution, 18 bytes

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

Attempt at different approach. This solution sorts and looks at adjacent pairs.

Try it online!

Answer 19

R, 48 bytes

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

Try it online!

Explanation: outer(s,s,startsWith) outputs a matrix of logicals checking whether s[i] is a prefix of s[j]. If s is a prefix code, then there are exactly length(s) TRUE elements in the result, corresponding to the diagonal elements (s[i] is a prefix of itself).

Answer 20

Pyth - 13 12 bytes

!ssmm}d._k-Q

Try it online here.

Answer 21

Ruby, 48 bytes

Uses arguments as input and stdout as output.

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

Answer 22

Python, 58 55 bytes

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

Answer 23

Scala, 71 bytes

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

Answer 24

Racket 130 bytes

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

Testing:

(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"])

Output:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f

Answer 25

C (gcc), 93 bytes

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

Try it online!

Simple double for loop using strstr(a,b)==a to check for prefices. Mainly added since there doesn't seem to be a C answer yet.

Answer 26

05AB1E, 13 bytes

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

Too long.. Initially I had a 9-byte solution, but it failed for the duplicated key test case.

Try it online or verify all test cases.

Explanation:

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)

Answer 27

Japt, 8 bytes

á2 ËrbÃe

Try it

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

Answer 28

C# (Visual C# Interactive Compiler), 70 bytes

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

Try it online!

Answer 29

Stax, 6 bytes

å·↑↑¶Ω

Run and debug it

This produces non-zero for truthy.

The general idea is to consider every pair of strings in the input. If the substring index of one in the other is ever zero, then it's not a valid prefix code. In stax, index of a non-existing substring yields -1. This way, all the pair-wise substring indices can be multiplied together.

This is the same algorithm as isaacg's pyth solution, but I developed it independently.