11
\$\begingroup\$

Let's call a non-empty list of strings a mesa if the following conditions hold:

  1. Each listed string is non-empty and uses only characters that occur in the first string.
  2. Each successive string is exactly one character longer than the preceding string.
  3. No string in the list is a subsequence of any other string in the list.

The term "mesa" is from visualizing like this (where the xs are to be various characters):

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

NB: It's a mathematical fact that only finitely many mesas begin with a given string. Note the distinction between subsequence vs. substring; e.g., 'anna' is a subsequence (but not a substring) of 'banana'.

Challenge:

  • Write the shortest program that takes an arbitrary non-empty alphanumeric input string and outputs the number of mesas that begin with that string.

Input (stdin):

  • Any non-empty alphanumeric string.

Output (stdout):

  • The number of mesas that begin with the input string.

Scoring:

  • The winner is the program with the least number of bytes.

Example mesas

Only one mesa starts with a:

a

Only one mesa starts with aa:

aa

Many mesas start with ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa
\$\endgroup\$
  • \$\begingroup\$ How is the uniqueness of a mesa determined? For instance, I could have ab, bbb as a mesa just by stopping at the second term. Is that valid? Or do they always have to be made as long as possible? Also, if there are multiple possible rearrangements of the nth term (such as baa, aba, aab), do they all count as separate mesas as well (providing of course they all follow the rules)? \$\endgroup\$ – mellamokb Apr 23 '12 at 14:12
  • \$\begingroup\$ @mellamokb -- They're different mesas if they differ in any way at all. E.g., ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaa are different mesas. \$\endgroup\$ – r.e.s. Apr 23 '12 at 14:55
  • \$\begingroup\$ @mellamokb -- You bring up other good questions; e.g., how many maximum-length mesas start with a given string, and what is that maximum length. Other versions of these questions would fix an alphabet of given size (alphabet size would be the input), and would consider all mesas (redefined without condition #1) that use only letters from the given alphabet -- again there are only finitely many. \$\endgroup\$ – r.e.s. Apr 23 '12 at 15:20
2
\$\begingroup\$

GolfScript (106 103 chars)

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

Somewhere in the heart, of course, is some code from Is string X a subsequence of string Y?

\$\endgroup\$
2
\$\begingroup\$

Ruby, 142 characters

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

This algorithm is constructive, i.e. it builds all possible mesas for the input string and counts them. It makes the program really, really slow - but hey, it is codegolf.

Example runs:

> a
1
> aa
1
> ab
43
\$\endgroup\$
  • \$\begingroup\$ I was hoping that all mesas beginning with some of the nontrivial binary strings of length 3 (e.g. aab) are of feasible length, but I'm not sure -- your program has been running about an hour for that example. NB: There won't be feasible output for any input involving more than two distinct letters; e.g., some of the mesas that begin with abc have length greater than the 7000th Ackermann number. \$\endgroup\$ – r.e.s. Apr 23 '12 at 16:51
  • \$\begingroup\$ I've built an optimized version in C#, and after I generated 300,000 entries with aab I still was seeing the first 10 or so terms being all identical. So I think it might not be feasible for anything larger than two characters. At least, not without some intelligence and heuristic calculations. \$\endgroup\$ – mellamokb Apr 24 '12 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.