Is it a prefix code?

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.

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

• Do you want a consistent truthy value or could it be e.g. "some positive integer" (which might vary between different inputs). – Martin Ender May 2 '16 at 6:50
• @MartinBüttner Any positive integer is fine. – DJMcMayhem May 2 '16 at 6:51
• @DrGreenEggsandHamDJ I don't think that answer is meant to address the consistency of outputs at all, hence the question. ;) – Martin Ender May 2 '16 at 6:52
• Just out of curiosity: The challenge says: "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.". How would something like 001 be uniquely decipherable? It could be either 00, 1 or 0, 11. – Joba May 2 '16 at 13:21
• @Joba It depends on what your keys are. If you have 0, 00, 1, 11 all as keys, this is not a prefix-code because 0 is a prefix of 00, and 1 is a prefix of 11. A prefix code is where none of the keys starts with another key. So for example, if your keys are 0, 10, 11 this is a prefix code and uniquely decipherable. 001 is not a valid message, but 0011 or 0010 are uniquely decipherable. – DJMcMayhem May 2 '16 at 16:10

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

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.

• This is an elegant solution (+1) – Michael Klein May 2 '16 at 17:39

Java, 128127126125124 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

• idk bout java, but would & work instead of &&? – Maltysen May 2 '16 at 2:18
• Right, saves another byte. In Java, using bitwise operators with boolean operands behave just like normal logical operators, except they don't short circuit which isn't needed in this case. – Marv May 2 '16 at 2:21
• Couldn't you just change the return type of the function to int and return 0 and 1? That would save several bytes. Also I forget if this is valid in Java but if you declare i, j, and l inside the outer for loop that would save one byte from one less semicolon. – Patrick Roberts May 2 '16 at 7:15
• @PatrickRoberts Maltysen suggested this before, but this is not valid according to the most upvoted definition of truthy/falsey. Putting the declarations in the loop however is perfectly valid and pretty obvious now that I think about it. Thats what you get for golfing at 4 in the morning :^) – Marv May 2 '16 at 9:38
• @Joba Pretty sure that isn't valid since indexOf returns -1 when the string isn't found; it would need to be indexOf(a[i])==0 in which case there are no savings. – Pokechu22 May 2 '16 at 14:49

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.

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.


JavaScript ES6, 6543 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>

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.

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.

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

• @Jo King See the second half of my answer; it's a bit complicated and depends on how input is specified. I don't remember actually writing this, though – Pokechu22 Apr 13 at 3:38

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

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

• If this challenge used "two distinct and consistent values" instead of "truthy/falsy", this would only take 5 bytes. – Unrelated String Apr 16 at 4:48

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
.one    # Only one other string (i.e. itself)

• I wrote a 50 byte answer but yours just blew mine out of the water. – bb94 Apr 14 at 7:40
• @bb94 Yeah, I started with a similar answer but ran into the same problem as yours with sets with duplicated keys returning truthy. Writing this answer was incredibly satisfying – Jo King Apr 14 at 8:13

Racket, 70 bytes

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


Python, 58 55 bytes

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

• a.index(b)==0 is a bit shorter. Alternatively, you could do 0**sum(a.index(b)for a in l for b in l). – Mego May 2 '16 at 7:46
• @Mego That doesn't work because index throws an exception when b isn't found. And because it should be ==, not >=. However, find works. (And it's shorter too!) – DJMcMayhem May 2 '16 at 7:54
• Whoops, I meant to type find. Sleepy brain is sleepy. The second version should also work with find. – Mego May 2 '16 at 8:13
• @Mego I'm not sure if I get the second version. Wouldn't that always return 0? – DJMcMayhem May 2 '16 at 8:14
• @Mego That only works if every string is the same. The reason we compare it to len(l) is since we're iterating through all bs on each a, there will always be at least one match per a. So we check if the number of matches is the same as the number of elements. – DJMcMayhem May 2 '16 at 8:32

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>

• !w.indexOf(v)? – Neil May 2 '16 at 10:00
• @Neil right, thanks – edc65 May 2 '16 at 12:26

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]

• The precedence rules should make a~Drop~{#}~StringStartsQ~a[[#]] work. Also Array should save some bytes over Length, especially because it will allow you to use Join@@ instead of Flatten@ (provided, you're using Flatten only for a single level). – Martin Ender May 2 '16 at 14:28
• Thanks for the suggestion. I'll look into Array later. – DavidC May 2 '16 at 14:47

Mathematica, 41 bytes

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


APL (Dyalog Unicode), 13 bytesSBCS

-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

• ~2∊+\⊃¨∘.⍷⍨⎕­ – ngn Apr 12 at 19:38

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!

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

• I've found a bunch of other 48 byte alternatives, like function(s)all(colSums(outer(s,s,startsWith))<2) but it remains that startsWith is a function I didn't know about! Nice find. – Giuseppe Apr 11 at 16:20
• @Giuseppe I tried several ways of checking whether the matrix is an identity matrix, but couldn't get it under 48 bytes either. I thought this way was the easiest to understand, but I'm sure someone will golf it down! – Robin Ryder Apr 11 at 18:01
• 47 bytes by inverting TRUE and FALSE... – Giuseppe Apr 11 at 18:24
• @Giuseppe Is that allowed? The rules explicitly ask for truthy when the input is a valid prefix code. (Also your link is to the 48 byte version, but I am guessing that your suggestion is to replace == with >. :-) ) – Robin Ryder Apr 12 at 8:00

Pyth - 13 12 bytes

!ssmm}d._k-Q


Ruby, 48 bytes

Uses arguments as input and stdout as output.

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


Scala, 71 bytes

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


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


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.

05AB1E, 13 bytes

2.ÆDí«εÅ?}O_


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

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)


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)


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!

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.