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.
001
be uniquely decipherable? It could be either00, 1
or0, 11
. \$\endgroup\$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 are0, 10, 11
this is a prefix code and uniquely decipherable.001
is not a valid message, but0011
or0010
are uniquely decipherable. \$\endgroup\$