¿Cuántas mesas comienzan con una cadena dada?

11

Llamemos a una lista de cadenas no vacía una mesa si se cumplen las siguientes condiciones:

  1. Cada cadena de la lista no está vacía y usa solo caracteres que aparecen en la primera cadena.
  2. Cada cadena sucesiva tiene exactamente un carácter más largo que la cadena anterior.
  3. Ninguna cadena en la lista es una subsecuencia de cualquier otra cadena en la lista.

El término "mesa" es de visualización como esta (donde los xs deben ser varios caracteres):

    xx..x
    xx..xx
    xx..xxx
    .
    .
    .
    xx..xxx..x

NB: Es un hecho matemático que solo finitamente muchas mesas comienzan con una cadena dada. Tenga en cuenta la distinción entre subsecuencia versus subcadena ; por ejemplo, 'anna' es una subsecuencia (pero no una subcadena) de 'banana'.

Desafío:

  • Escriba el programa más corto que tome una cadena de entrada alfanumérica no vacía arbitraria y genere el número de mesas que comienzan con esa cadena.

Entrada (stdin):

  • Cualquier cadena alfanumérica no vacía.

Salida (stdout):

  • El número de mesas que comienzan con la cadena de entrada.

Puntuación:

  • El ganador es el programa con el menor número de bytes.

Mesas de ejemplo

Solo una mesa comienza con a:

a

Solo una mesa comienza con aa:

aa

Muchas mesas comienzan con ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf res
fuente
¿Cómo se determina la unicidad de una mesa? Por ejemplo, yo podría tener ab, bbbcomo una mesa con sólo detenerse en el segundo período. ¿Es eso válido? ¿O siempre tienen que hacerse el mayor tiempo posible? Además, si hay varias posibles reordenamientos del nthplazo (tales como baa, aba, aab), es lo que todos cuentan como mesas separadas, así (siempre, por supuesto, todos siguen las reglas)?
mellamokb
@mellamokb: son mesas diferentes si difieren de alguna manera. Por ejemplo, ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaason diferentes mesas.
res
@mellamokb: traes otras buenas preguntas; por ejemplo, cuántas mesas de longitud máxima comienzan con una cadena dada y cuál es esa longitud máxima. Otras versiones de estas preguntas arreglarían un alfabeto de un tamaño determinado (el tamaño del alfabeto sería la entrada), y considerarían todas las mesas (redefinidas sin la condición # 1) que usan solo letras del alfabeto dado; de nuevo, solo hay muchas.
res

Respuestas:

2

GolfScript ( 106 103 caracteres)

n-..&1/:Z;]]0,\{.@+\{['']:E+.-2=,)E\{{`{+}+Z/}%}*{:x`{\1,+\{1$(@={\}*;}/0=!}+1$?!{.);[x]+\}*}/;}%.}do;,

En algún lugar del corazón, por supuesto, hay algún código de ¿Es la cadena X una subsecuencia de la cadena Y?

Peter Taylor
fuente
2

Ruby, 142 caracteres.

m=->l{[*l[0].chars].repeated_permutation(l[-1].size+1).reduce(1){|s,x|l.any?{|y|x*''=~/#{[*y.chars]*'.*'}/}?s:s+m[l+[x*'']]}}
p m[[gets.chop]]

Este algoritmo es constructivo, es decir, construye todas las mesas posibles para la cadena de entrada y las cuenta. Hace que el programa sea realmente lento, pero bueno, es codegolf.

Ejecuciones de ejemplo:

> a
1
> aa
1
> ab
43
Howard
fuente
Esperaba que todas las mesas que comiencen con algunas de las cadenas binarias no triviales de longitud 3 (por ejemplo aab) sean de longitud factible, pero no estoy seguro: su programa ha estado ejecutándose aproximadamente una hora para ese ejemplo. NB: No habrá salida factible para ninguna entrada que involucre más de dos letras distintas; por ejemplo, algunas de las mesas que comienzan abctienen una longitud mayor que el número 7000 de Ackermann .
res
He creado una versión optimizada en C #, y después de generar 300,000entradas con aab, todavía veía que los primeros 10 términos eran idénticos. Así que creo que podría no ser factible para algo más grande que dos caracteres. Al menos, no sin cierta inteligencia y cálculos heurísticos.
mellamokb