Ile mes zaczyna się od danego ciągu?

11

Nazwijmy niepustą listę ciągów mesą, jeśli spełnione są następujące warunki:

  1. Każdy wymieniony ciąg jest niepusty i używa tylko znaków występujących w pierwszym ciągu.
  2. Każdy kolejny ciąg znaków ma dokładnie jeden znak dłuższy niż poprzedni ciąg.
  3. Żaden ciąg na liście nie jest podciągiem żadnego innego ciągu na liście.

Termin „mesa” pochodzi od takiej wizualizacji (gdzie xs mają być różnymi znakami):

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

NB: Jest to matematyczny fakt, że tylko skończona liczba mes zaczyna się od danego łańcucha. Należy zwrócić uwagę na rozróżnienie między podciąg vs. fragmentu ; np. „anna” jest podsekwencją (ale nie podciągiem) „banana”.

Wyzwanie:

  • Napisz najkrótszy program, który pobiera dowolny niepusty pusty alfanumeryczny ciąg wejściowy i wyświetla liczbę mes, które zaczynają się od tego ciągu.

Wejście (standardowe wejście):

  • Dowolny niepusty ciąg alfanumeryczny.

Wyjście (standardowe wyjście):

  • Liczba mes, które zaczynają się od ciągu wejściowego.

Punktacja:

  • Zwycięzcą jest program z najmniejszą liczbą bajtów.

Przykładowe mesa

Tylko jedna mesa zaczyna się od a:

a

Tylko jedna mesa zaczyna się od aa:

aa

Wiele mes zaczyna się od ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf res
źródło
Jak określa się wyjątkowość mesy? Na przykład mógłbym ab, bbbjako mesa, po prostu zatrzymać się na drugim semestrze. Czy to jest ważne? Czy zawsze muszą być wykonane tak długo, jak to możliwe? Ponadto, jeśli istnieje wiele możliwych rearanżacji w nthperspektywie (takie jak baa, aba, aab), czy słupkiem jako odrębne płaskowyże, jak również (pod warunkiem oczywiście, że wszyscy przestrzegają zasad)?
mellamokb
@mellamokb - Są to różne mesy, jeśli różnią się w jakikolwiek sposób. Na przykład ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaasą różne płaskowyże.
res
@mellamokb - Przywołujesz inne dobre pytania; np. ile mes o maksymalnej długości zaczyna się od danego ciągu i jaka jest ta maksymalna długość. Inne wersje tych pytań naprawiałyby alfabet o danym rozmiarze (rozmiar alfabetu byłby danymi wejściowymi) i uwzględniałyby wszystkie mesy (zdefiniowane na nowo bez warunku nr 1), które używają tylko liter z danego alfabetu - znowu jest ich tylko wiele.
res

Odpowiedzi:

2

GolfScript ( 106 103 znaków)

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

Gdzieś w sercu jest oczywiście jakiś kod z Czy ciąg X jest podsekwencją ciągu Y?

Peter Taylor
źródło
2

Ruby, 142 znaki

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

Ten algorytm jest konstruktywny, tzn. Buduje wszystkie możliwe mesy dla ciągu wejściowego i je zlicza. To sprawia, że ​​program jest naprawdę, bardzo wolny - ale hej, to codegolf.

Przykładowe przebiegi:

> a
1
> aa
1
> ab
43
Howard
źródło
Miałem nadzieję, że wszystkie mesy zaczynające się od nietrywialnych ciągów binarnych o długości 3 (np. aab) Mają możliwą długość, ale nie jestem pewien - twój program działa na około godzinę dla tego przykładu. Uwaga: Dane wyjściowe zawierające więcej niż dwie różne litery nie będą możliwe. np. niektóre mesy, które zaczynają się od abcmają długość większą niż 7000-ty numer Ackermann .
res
Zbudowałem zoptymalizowaną wersję w C #, a po wygenerowaniu 300,000wpisów aabnadal widziałem, że pierwsze 10 warunków jest identycznych. Myślę więc, że może być niewykonalne dla czegoś większego niż dwie postacie. Przynajmniej nie bez inteligencji i obliczeń heurystycznych.
mellamokb