Wie viele Mesas beginnen mit einer bestimmten Zeichenfolge?

11

Nennen wir eine nicht leere Liste von Zeichenfolgen eine Mesa, wenn die folgenden Bedingungen erfüllt sind:

  1. Jede aufgelistete Zeichenfolge ist nicht leer und verwendet nur Zeichen, die in der ersten Zeichenfolge vorkommen.
  2. Jede aufeinanderfolgende Zeichenfolge ist genau ein Zeichen länger als die vorhergehende Zeichenfolge.
  3. Keine Zeichenfolge in der Liste ist eine Teilsequenz einer anderen Zeichenfolge in der Liste.

Der Begriff "Mesa" stammt aus der folgenden Visualisierung (wobei die xs verschiedene Zeichen sein sollen):

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

NB: Es ist eine mathematische Tatsache, dass nur endlich viele Mesas mit einer bestimmten Zeichenfolge beginnen. Beachten Sie die Unterscheidung zwischen Teilfolge vs. String ; zB ist 'anna' eine Teilsequenz (aber keine Teilzeichenfolge) von 'banana'.

Herausforderung:

  • Schreiben Sie das kürzeste Programm, das eine beliebige nicht leere alphanumerische Eingabezeichenfolge verwendet und die Anzahl der Mesas ausgibt, die mit dieser Zeichenfolge beginnen.

Eingabe (stdin):

  • Jede nicht leere alphanumerische Zeichenfolge.

Ausgabe (stdout):

  • Die Anzahl der Mesas, die mit der Eingabezeichenfolge beginnen.

Wertung:

  • Der Gewinner ist das Programm mit der geringsten Anzahl von Bytes.

Beispiel mesas

Nur eine Mesa beginnt mit a:

a

Nur eine Mesa beginnt mit aa:

aa

Viele Mesas beginnen mit ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf res
quelle
Wie wird die Einzigartigkeit einer Mesa bestimmt? Zum Beispiel könnte ich habe ab, bbbals Mesa nur durch am zweiten Begriff zu stoppen. Ist das gültig? Oder müssen sie immer so lange wie möglich gemacht werden? Wenn es auch sind mehrere möglichen Umlagerungen des nthBegriffs (wie baa, aba, aab), tun sie alle zählen als getrenntes Mesas sowie (vorausgesetzt natürlich alles , was sie an den Regeln)?
Mellamokb
@mellamokb - Sie sind verschiedene Mesas, wenn sie sich in irgendeiner Weise unterscheiden. Zum Beispiel ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaasind verschiedene Mesas.
Res
@mellamokb - Sie werfen andere gute Fragen auf; Beispiel: Wie viele Mesas mit maximaler Länge beginnen mit einer bestimmten Zeichenfolge und wie hoch ist diese maximale Länge? Andere Versionen dieser Fragen würden ein Alphabet mit einer bestimmten Größe festlegen (Alphabetgröße wäre die Eingabe) und alle Mesas (ohne Bedingung Nr. 1 neu definiert) berücksichtigen, die nur Buchstaben aus dem angegebenen Alphabet verwenden - wieder gibt es nur endlich viele.
Res

Antworten:

2

GolfScript ( 106 103 Zeichen)

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

Irgendwo im Herzen ist natürlich ein Code aus Ist String X eine Teilfolge von String Y?

Peter Taylor
quelle
2

Ruby, 142 Zeichen

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

Dieser Algorithmus ist konstruktiv, dh er erstellt alle möglichen Mesas für die Eingabezeichenfolge und zählt sie. Es macht das Programm wirklich sehr, sehr langsam - aber hey, es ist Codegolf.

Beispielläufe:

> a
1
> aa
1
> ab
43
Howard
quelle
Ich hatte gehofft, dass alle Mesas, die mit einigen der nichttrivialen Binärzeichenfolgen der Länge 3 (z. B. aab) beginnen, eine realisierbare Länge haben, aber ich bin mir nicht sicher - Ihr Programm wurde für dieses Beispiel ungefähr eine Stunde lang ausgeführt. NB: Für Eingaben mit mehr als zwei unterschiedlichen Buchstaben ist keine Ausgabe möglich. Beispielsweise haben einige der Mesas, die mit beginnen, abceine Länge, die größer als die 7000. Ackermann-Zahl ist .
Res
Ich habe eine optimierte Version in C # erstellt und nachdem ich 300,000Einträge mit generiert hatte, sah aabich immer noch, dass die ersten 10 Begriffe alle identisch waren. Daher denke ich, dass es für etwas, das größer als zwei Zeichen ist, möglicherweise nicht machbar ist. Zumindest nicht ohne Intelligenz und heuristische Berechnungen.
Mellamokb