En este desafío sobre el código de prefijo , aprendimos que los códigos de prefijo son concatenables de manera única.

Eso significa que se pueden unir sin separador y sin ambigüedad.

Por ejemplo, como [1,2,45] es un código de prefijo, puedo unirlos sin separador como tal: 1245245112145, y no habrá ambigüedad.

Sin embargo, lo contrario no siempre es cierto.

Por ejemplo, [3,34] no es un código de prefijo. Sin embargo, puedo hacer lo mismo: 3333434334333, y no habrá ambigüedad. Solo necesitarías un analizador más inteligente.

Sin embargo, [1,11] no es concatenable de manera única, ya que 1111 puede interpretarse de 5 maneras.

Objetivo

Su tarea es escribir un programa / función que tome una lista de cadenas (ASCII) como entrada, y determinar si son concatenables de forma exclusiva.

Detalles

El duplicado cuenta como falso.

Puntuación

Este es el código de golf . La solución más corta en bytes gana.

Casos de prueba

Cierto:

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

Falso:

[1,1]
[1,2,112]
[1,23,4,12,34]
[1,2,35,4,123,58,8]

05AB1E , 15 bytes

En el teléfono, entonces la explicación tendrá que seguir más tarde. Código:

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

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Toma demasiada memoria para el último caso de prueba, por lo que podría no funcionar ...

CJam (54 bytes)

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

Toma entrada en stdin como una lista separada por nueva línea.

Demostración en línea

Si no tuviéramos que manejar palabras de código duplicadas, esto podría acortarse a 44:

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

O si CJam tuviera una resta de matriz que solo eliminara un elemento de la primera lista para cada elemento en el segundo, podría ser 48 ...

Disección

Este es el algoritmo Sardinas-Patterson pero no optimizado. Como cada sufijo colgante aparece solo una vez, ejecutar el bucle principal tantas veces como haya caracteres en la entrada (incluidos los separadores) garantiza que sea suficiente.

Tenga en cuenta que tuve que solucionar lo que podría decirse que es un error en el intérprete de CJam:

"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

Por lo tanto, la verificación del prefijo es complicada en 1$,<=lugar de\#!

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*&!