Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Re: Solving Meta Sentences

by abstracts (Hermit)
on Jun 05, 2002 at 05:52 UTC ( #171730=note: print w/replies, xml ) Need Help??

in reply to Solving Meta Sentences

One thing comes to mind that should speed up your search. Notice that the letters qw/c d j k m p q z/ do not appear anywhere in the words you have in the DATA. This means that the number of occurences of these letters depends only on the initial sentence beginning (the example you listed has only "three c's, three d's, one j, two k's two m's two p's, one q and one z" regardless of how many times the other letters occur).

With this in mind, we can group these letters and their counts to the beginning of the sentence (plus the "and" that appears before "z" plus the remaining letters themselves) giving us an initial sequence of:
"Any Perlmonk could write a sentence using three cs three ds one j two ks two ms two ps one q and one z . a b e f g h i l n o r s t u v w x y"
with only 18 letters left to match instead of 26.

Also notice that there is a minimum of number occurences for each letter. In our running example, "s" cannot appear less than 8 times (highlighted). This should make you start closer to the solution.

Also, "0 no" does not need to be there in the __DATA__ section because all letters exist at least once (in mentioning their names).

I hope these things help you find more solutions faster.

Replies are listed 'Best First'.
Re: Re: Solving Meta Sentences
by gumby (Scribe) on Jun 12, 2002 at 22:21 UTC
    At first glance, it would seem more rewarding to formulate this as a linear algebra problem. Let x_i take the value of the number of times some letter appears in the sentence and set up constraints in the x_i. There are numerous ways of solving the resulting system (Fourier-Motzkin say).

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://171730]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2019-11-20 17:08 GMT
Find Nodes?
    Voting Booth?
    Strict and warnings: which comes first?

    Results (100 votes). Check out past polls.