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]
Improve this question
\$\endgroup\$
5
  • \$\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\$ Commented May 2, 2016 at 2:20
  • \$\begingroup\$ Are you sure this isn't equivalent to the halting problem? \$\endgroup\$ Commented May 2, 2016 at 2:21
  • \$\begingroup\$ Can you demonstrate why this is equivalent to the halting problem? \$\endgroup\$ Commented May 2, 2016 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\$ Commented May 2, 2016 at 2:52
  • \$\begingroup\$ @feersum Here's a poly time algorithm for this problem: en.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_algorithm \$\endgroup\$ Commented May 2, 2016 at 3:00

2 Answers 2

Reset to default
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...

Improve this answer
\$\endgroup\$
7
  • 3
    \$\begingroup\$ It's extremely impressive that you're able to type that on your phone. \$\endgroup\$ Commented May 2, 2016 at 15:03
  • 3
    \$\begingroup\$ @DrGreenEggsandHamDJ It took about 40 minutes... \$\endgroup\$ Commented May 2, 2016 at 15:04
  • 2
    \$\begingroup\$ @Adnan I wonder what your phone keyboard's text predictor thinks of all that garbage symbols :-) \$\endgroup\$ Commented May 2, 2016 at 21:13
  • 1
    \$\begingroup\$ @LuisMendo Haha, it only happened once that I sent a random 05AB1E program to a friend. \$\endgroup\$ Commented May 2, 2016 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\$ Commented May 3, 2016 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*&!
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.