Quantas mesas começam com uma determinada sequência?

11

Vamos chamar uma lista não vazia de strings de mesa se as seguintes condições forem válidas :

  1. Cada sequência listada não está vazia e usa apenas caracteres que ocorrem na primeira sequência.
  2. Cada sequência sucessiva tem exatamente um caractere a mais que a sequência anterior.
  3. Nenhuma sequência na lista é uma subsequência de qualquer outra sequência na lista.

O termo "mesa" é visualizado desta maneira (onde os xs devem ter vários caracteres):

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

NB: É um fato matemático que apenas finitas mesas começam com uma determinada sequência. Observe a distinção entre subsequência vs. substring ; por exemplo, 'anna' é uma subsequência (mas não uma substring) de 'banana'.

Desafio:

  • Escreva o programa mais curto que pega uma sequência de entrada alfanumérica arbitrária e não vazia e gera o número de mesas que começam com essa sequência.

Entrada (stdin):

  • Qualquer sequência alfanumérica não vazia.

Saída (stdout):

  • O número de mesas que começam com a sequência de entrada.

Pontuação:

  • O vencedor é o programa com o menor número de bytes.

Mesas de exemplo

Apenas uma mesa começa com a:

a

Apenas uma mesa começa com aa:

aa

Muitas mesas começam com ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf res
fonte
Como é determinada a singularidade de uma mesa? Por exemplo, eu poderia ter ab, bbbcomo mesa, apenas parando no segundo mandato. Isso é válido? Ou eles sempre precisam ser feitos o maior tempo possível? Além disso, se houver vários rearranjos possíveis do nthtermo (como baa, aba, aab), não todos eles contam como mesas separadas bem (desde é claro que todos eles seguem as regras)?
Mellamokb
@mellamokb - São mesas diferentes se diferem de alguma forma. Por exemplo, ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaasão diferentes mesas.
res
@mellamokb - Você traz outras boas perguntas; por exemplo, quantas mesas de comprimento máximo começam com uma determinada sequência e qual é esse comprimento máximo. Outras versões dessas perguntas fixariam um alfabeto de determinado tamanho (o tamanho do alfabeto seria a entrada) e considerariam todas as mesas (redefinidas sem a condição nº 1) que usam apenas letras do alfabeto fornecido - novamente, existem apenas finitas.
res

Respostas:

2

GolfScript ( 106 103 caracteres)

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

Em algum lugar do coração, é claro, há algum código da string X é uma subsequência da string Y?

Peter Taylor
fonte
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]]

Esse algoritmo é construtivo, ou seja, cria todos os tabelas possíveis para a sequência de entrada e os conta. Isso torna o programa muito, muito lento - mas ei, é um codegolf.

Exemplo é executado:

> a
1
> aa
1
> ab
43
Howard
fonte
Eu esperava que todas as tabelas que começassem com algumas das seqüências binárias não triviais de comprimento 3 (por exemplo aab) sejam viáveis, mas não tenho certeza - seu programa está em execução há cerca de uma hora para esse exemplo. NB: Não haverá saída viável para qualquer entrada que envolva mais de duas letras distintas; por exemplo, algumas das mesas que começam com abccomprimento maior que o número 7000º Ackermann .
res
Criei uma versão otimizada em C # e, depois de gerar 300,000entradas com aab, continuava vendo os 10 primeiros termos sendo todos idênticos. Então, acho que pode não ser viável para algo maior que dois caracteres. Pelo menos, não sem alguma inteligência e cálculos heurísticos.
Mellamokb