10
\$\begingroup\$

In this challenge about prefix code, we learnt that prefix codes are uniquely concatenable.

That means, they can be joined together without separator, and without ambiguity.

For example, since [1,2,45] is a prefix code, I can join them together without separator as such: 1245245112145, and there will be no ambiguity.

However the converse is not always true.

For example, [3,34] is not a prefix code. However, I can do the same: 3333434334333, and there will be no ambiguity. You would just need a smarter parser.

However, [1,11] is not uniquely concatenable, because 1111 can be interpreted in 5 ways.

Goal

Your task is to write a program/function that takes a list of strings (ASCII) as input, and determine if they are uniquely concatenable.

Details

Duplicate counts as false.

Scoring

This is . Shortest solution in bytes wins.

Testcases

True:

[12,21,112]
[12,112,1112]
[3,4,35]
[2,3,352]

False:

[1,1]
[1,2,112]
[1,23,4,12,34]
[1,2,35,4,123,58,8]
\$\endgroup\$
  • \$\begingroup\$ Just to make sure I understand the challenge correctly, it is not uniquely concatenable if one of the strings is composed of any combination of the other ones? You should make that details more clear. \$\endgroup\$ – DJMcMayhem May 2 '16 at 2:20
  • \$\begingroup\$ Are you sure this isn't equivalent to the halting problem? \$\endgroup\$ – feersum May 2 '16 at 2:21
  • \$\begingroup\$ Can you demonstrate why this is equivalent to the halting problem? \$\endgroup\$ – Leaky Nun May 2 '16 at 2:35
  • \$\begingroup\$ I didn't say it was, but wondered it might be. After some more thought I believe it isn't. \$\endgroup\$ – feersum May 2 '16 at 2:52
  • \$\begingroup\$ @feersum Here's a poly time algorithm for this problem: en.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_algorithm \$\endgroup\$ – isaacg May 2 '16 at 3:00
5
\$\begingroup\$

05AB1E, 15 bytes

On the phone, so explanation will have to follow later. Code:

gF¹N>ã})€`€JDÚQ

Uses CP-1252 encoding. Try it online!.

Takes too much memory for the last test case, so that might not work...

\$\endgroup\$
  • 3
    \$\begingroup\$ It's extremely impressive that you're able to type that on your phone. \$\endgroup\$ – DJMcMayhem May 2 '16 at 15:03
  • 3
    \$\begingroup\$ @DrGreenEggsandHamDJ It took about 40 minutes... \$\endgroup\$ – Adnan May 2 '16 at 15:04
  • 2
    \$\begingroup\$ @Adnan I wonder what your phone keyboard's text predictor thinks of all that garbage symbols :-) \$\endgroup\$ – Luis Mendo May 2 '16 at 21:13
  • 1
    \$\begingroup\$ @LuisMendo Haha, it only happened once that I sent a random 05AB1E program to a friend. \$\endgroup\$ – Adnan May 2 '16 at 21:56
  • \$\begingroup\$ I'm guessing that this works by placing an upper bound on the length of the shortest collision. Am I right? \$\endgroup\$ – Peter Taylor May 3 '16 at 7:26
4
\$\begingroup\$

CJam (54 bytes)

q_N/:A\,{_Am*:${~1$,<=},{~\,>}%La:L-}*A,A_&,-A*](\M*&!

Takes input on stdin as newline-separated list.

Online demo

If we didn't have to handle duplicate codewords, this could be shortened to 44:

q_N/\,{_W$m*:${~1$,<=},{~\,>}%La:L-}*](\M*&!

Or if CJam had an array subtraction which only removed one item from the first list for each item in the second, it could be 48...

Dissection

This is the Sardinas-Patterson algorithm but de-optimised. Since each dangling suffix only comes up at most once, running the main loop as many times as there are characters in the input (including separators) guarantees to be sufficient.

Note that I had to work around what is arguably a bug in the CJam interpreter:

"abc" "a" #   e# gives 0 as the index at which "a" is found
"abc" "d" #   e# gives -1 as the index at which "d" is found
"abc" ""  #   e# gives an error

So the prefix check is complicated to 1$,<= instead of \#!

e# Take input, split, loop once per char
q_N/\,{
  e# Build the suffixes corresponding to top-of-stack and bottom-of-stack
  _W$m*
  e# Map each pair of Cartesian product to the suffix if one is the prefix of the other;
  e# otherwise remove from the array
  :${~1$,<=},{~\,>}%
  e# Filter out empty suffixes iff it's the first time round the loop
  La:L-
}*
e# If we generated an empty suffix then we've also looped enough times to generate all
e# of the keywords as suffixes corresponding to the empty fix, so do a set intersection
e# to test this condition.
](\M*&!
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.