Combien de mesas commencent par une chaîne donnée?

11

Appelons une liste de chaînes non vide une mesa si les conditions suivantes sont réunies:

  1. Chaque chaîne répertoriée n'est pas vide et utilise uniquement les caractères qui apparaissent dans la première chaîne.
  2. Chaque chaîne successive a exactement un caractère de plus que la chaîne précédente.
  3. Aucune chaîne de la liste n'est une sous- séquence de toute autre chaîne de la liste.

Le terme "mesa" vient de la visualisation comme ceci (où les xs doivent être différents caractères):

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

NB: C'est un fait mathématique que seulement un nombre fini de mesas commencent par une chaîne donnée. Notez la distinction entre sous- séquence et sous-chaîne ; Par exemple, 'anna' est une sous-séquence (mais pas une sous-chaîne) de 'banana'.

Défi:

  • Écrivez le programme le plus court qui prend une chaîne d'entrée alphanumérique non vide arbitraire et génère le nombre de mesas commençant par cette chaîne.

Entrée (stdin):

  • Toute chaîne alphanumérique non vide.

Sortie (sortie standard):

  • Nombre de mesas commençant par la chaîne d'entrée.

Notation:

  • Le gagnant est le programme avec le moins d'octets.

Exemple mesas

Une seule mesa commence par a:

a

Une seule mesa commence par aa:

aa

Beaucoup de mesas commencent par ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf res
la source
Comment détermine-t-on l'unicité d'une mesa? Par exemple, j'aurais pu ab, en bbbtant que mesa, simplement en m'arrêtant au deuxième trimestre. Est-ce que c'est valable? Ou faut-il toujours les faire le plus longtemps possible? De plus, s'il y a plusieurs réarrangements possibles du nthterme ( par exemple baa, aba, aab), ils font tout compte comme mesas séparé, ( à condition bien sûr qu'ils suivent toutes les règles)?
mellamokb
@mellamokb - Ce sont des mesas différents s'ils diffèrent de quelque façon que ce soit. Par exemple, ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaasont différentes mesas.
res
@mellamokb - Vous soulevez d'autres bonnes questions; par exemple, combien de mesas de longueur maximale commencent par une chaîne donnée, et quelle est cette longueur maximale. D'autres versions de ces questions fixeraient un alphabet de taille donnée (la taille de l'alphabet serait l'entrée) et prendraient en compte toutes les mesas (redéfinies sans condition # 1) qui n'utilisent que des lettres de l'alphabet donné - là encore, il n'y en a qu'un nombre fini.
res

Réponses:

2

Rubis, 142 caractères

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]]

Cet algorithme est constructif, c'est-à-dire qu'il construit toutes les mesas possibles pour la chaîne d'entrée et les compte. Cela rend le programme vraiment, vraiment lent - mais bon, c'est du codegolf.

L'exemple s'exécute:

> a
1
> aa
1
> ab
43
Howard
la source
J'espérais que toutes les mesas commençant par certaines des chaînes binaires non triviales de longueur 3 (par exemple aab) sont de longueur réalisable, mais je ne suis pas sûr - votre programme a fonctionné environ une heure pour cet exemple. NB: Il n'y aura pas de sortie réalisable pour toute entrée impliquant plus de deux lettres distinctes; par exemple, certaines des mesas qui commencent par abcont une longueur supérieure au 7000e nombre d'Ackermann .
res
J'ai construit une version optimisée en C #, et après avoir généré des 300,000entrées avec, aabje voyais toujours les 10 premiers termes tous identiques. Je pense donc que cela pourrait ne pas être possible pour plus de deux caractères. Du moins, non sans intelligence et calculs heuristiques.
mellamokb