Berapa banyak mesa yang dimulai dengan string yang diberikan?

11

Mari kita sebut daftar string yang tidak kosong sebagai mesa jika kondisi berikut ini berlaku:

  1. Setiap string yang terdaftar tidak kosong dan hanya menggunakan karakter yang muncul di string pertama.
  2. Setiap string berturut-turut persis satu karakter lebih panjang dari string sebelumnya.
  3. Tidak ada string dalam daftar adalah subsequence dari string lain dalam daftar.

Istilah "mesa" berasal dari memvisualisasikan seperti ini (di mana xkarakter harus beragam):

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

NB: Ini adalah fakta matematis bahwa hanya sedikit mesa yang dimulai dengan string tertentu. Perhatikan perbedaan antara berikutnya vs substring ; misalnya, 'anna' adalah urutan (tetapi bukan substring) dari 'pisang'.

Tantangan:

  • Tulis program terpendek yang menggunakan string input alfanumerik non-kosong sembarang dan menghasilkan jumlah mesa yang dimulai dengan string itu.

Input (stdin):

  • String alfanumerik yang tidak kosong.

Output (stdout):

  • Jumlah mesa yang dimulai dengan string input.

Mencetak:

  • Pemenangnya adalah program dengan jumlah byte terkecil.

Contoh mesa

Hanya satu mesa yang dimulai dengan a:

a

Hanya satu mesa yang dimulai dengan aa:

aa

Banyak mesa dimulai dengan ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
code-golf res
sumber
Bagaimana keunikan mesa ditentukan? Misalnya, saya bisa saja ab, bbbsebagai seorang mesa hanya dengan berhenti pada semester kedua. Apakah itu valid? Atau apakah harus selalu dibuat selama mungkin? Juga, jika ada beberapa kemungkinan penyusunan ulang dari nthistilah (seperti baa, aba, aab), apakah mereka juga dihitung sebagai mesa terpisah juga (menyediakan tentu saja mereka semua mengikuti aturan)?
mellamokb
@ellamokb - Mereka mesa yang berbeda jika mereka berbeda dengan cara apa pun. Misalnya, ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaayang mesa berbeda.
res
@ellamokb - Anda memunculkan pertanyaan bagus lainnya; misalnya, berapa banyak panjang maksimum mesa yang dimulai dengan string yang diberikan, dan berapa panjang maksimumnya. Versi lain dari pertanyaan ini akan memperbaiki alfabet ukuran tertentu (ukuran alfabet akan menjadi input), dan akan mempertimbangkan semua mesa (didefinisikan ulang tanpa syarat # 1) yang hanya menggunakan huruf dari alfabet yang diberikan - lagi-lagi hanya ada banyak.
res

Jawaban:

2

Ruby, 142 karakter

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

Algoritma ini konstruktif, yaitu membangun semua kemungkinan mesa untuk string input dan menghitungnya. Itu membuat program ini benar-benar lambat - tapi hei, itu codegolf.

Contoh berjalan:

> a
1
> aa
1
> ab
43
Howard
sumber
Saya berharap bahwa semua mesa yang dimulai dengan beberapa string biner nontrivial dengan panjang 3 (mis. aab) Memiliki panjang yang layak, tapi saya tidak yakin - program Anda telah berjalan sekitar satu jam untuk contoh itu. NB: Tidak akan ada output yang layak untuk input apa pun yang melibatkan lebih dari dua huruf berbeda; misalnya, beberapa mesa yang dimulai dengan abcmemiliki panjang lebih besar dari angka Ackermann ke - 7000 .
res
Saya telah membangun versi yang dioptimalkan dalam C #, dan setelah saya membuat 300,000entri dengan aabsaya masih melihat 10 istilah pertama atau lebih semuanya identik. Jadi saya pikir itu tidak mungkin untuk sesuatu yang lebih besar dari dua karakter. Setidaknya, bukan tanpa kecerdasan dan perhitungan heuristik.
mellamokb