Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Solving Meta Sentences

by YuckFoo (Abbot)
on May 29, 2002 at 17:25 UTC ( #170159=CUFP: print w/ replies, xml ) Need Help??

As follow up to this node about meta-sentences:

"Any Perlmonk could write a sentence using four a's, one b, three c's, three d's, thirty-one e's, six f's, two g's, five h's, ten i's, one j, two k's, four l's, two m's, twenty-three n's, sixteen o's, two p's, one q, eleven r's, twenty-nine s's, twenty t's, seven u's, four v's, nine w's, four x's, six y's, and one z."

Hopefully the code is straight forward. Each letter has a {claim}, {count} and {score} field. A {claim} is made. The sentence is analyzed, updating the {count} fields. {score} = {claim} - {count}. If {score} is nonzero it is added to 'broke' list. Adjustments are make to the broke letters by changing their {claim} fields and the process repeats.

I'd be glad to clarify any questions about the code and feedback is welcome.

I tried many more complicated strategies, but this one seems to work best. I'm still not convinced every sentence beginning will resolve. My stategy is simply to produce opportunities for the synchronicity to happen.

To improve the algorithm, I need more sentence beginnings that I know have a resolution, for analysis. So please let me know of any successes you have.

YuckFoo

#!/usr/bin/perl use strict; my $GERM = "Any Perlmonk could write a sentence using\n"; my $RESET = 4096; my $PROB = .5; my $words = makewords(); my $letts = makeletters(); my ($sent, $iter, $best); while (1) { $sent = makesentence($GERM, $words, $letts); updatecounts($letts, $sent); my ($broke, $score) = scoreclaim($letts); if ($iter++ % $RESET == 0) { $best = $score; print "\n"; } if ($score == 0) { last; } elsif ($score < $best) { $best = join('', @{$broke}); $best = "$score-$best"; print "$iter $best\n"; $best = $score; } for my $letter (@{$broke}) { if (rand() < $PROB) { my $amount = int(rand(abs($letts->{$letter}{score}+1)))+1; if ($letts->{$letter}{score} > 0) { $amount *= -1; } $letts->{$letter}{claim} += $amount; } } } print "\n$sent\n"; #----------------------------------------------------------- sub scoreclaim { my ($letts) = @_; my ($total, @broke); for my $ch ('a'..'z') { my $score = $letts->{$ch}{claim} - $letts->{$ch}{count}; $letts->{$ch}{score} = $score; $total += abs($score); if (abs($letts->{$ch}{score}) > 0) { push(@broke, $ch); } } return (\@broke, $total); } #----------------------------------------------------------- sub updatecounts { my ($letts, $sent) = @_; for my $ch ('a'..'z') { $letts->{$ch}{count} = (() = $sent =~ m{$ch}ig); } } #----------------------------------------------------------- sub makesentence { my ($sent, $words, $letts) = @_; my ($num); for my $ch ('a'..'y') { $num = $letts->{$ch}{claim}; if ($num != 1) { $sent .= " $words->{$num} ${ch}'s,\n"; } else { $sent .= " $words->{$num} $ch,\n"; } } $num = $letts->{z}{claim}; $sent .= " and $words->{$num} z"; if ($num != 1) { $sent .= "'s"; } $sent .= '.'; return $sent; } #----------------------------------------------------------- sub makeletters { my $letters = {}; for my $ch ('a'..'z') { $letters->{$ch} = {}; $letters->{$ch}{claim} = 1; $letters->{$ch}{count} = 0; $letters->{$ch}{score} = 0; } return $letters; } #----------------------------------------------------------- sub makewords { my (%words, $line); while (chomp ($line = <DATA>)) { my ($key, $val) = split(' ', $line); $words{$key} = $val; } for ($line = 0; $line < 100; $line++) { if (!defined($words{$line})) { my $tens = int($line / 10); my $ones = $line - ($tens * 10); $tens .= '0'; $words{$line} = "$words{$tens}-$words{$ones}"; } } return \%words; } __DATA__ 0 no 1 one 2 two 3 three 4 four 5 five 6 six 7 seven 8 eight 9 nine 10 ten 11 eleven 12 twelve 13 thirteen 14 fourteen 15 fifteen 16 sixteen 17 seventeen 18 eighteen 19 nineteen 20 twenty 30 thirty 40 forty 50 fifty 60 sixty 70 seventy 80 eighty 90 ninety

Edit kudra, 2002-05-30 Added readmore

Comment on Solving Meta Sentences
Download Code
Re: Solving Meta Sentences
by jarich (Curate) on May 30, 2002 at 02:53 UTC
    To improve the algorithm, I need more sentence beginnings that I know have a resolution, for analysis. So please let me know of any successes you have.

    As robin pointed out here a number of successful sentences can be found at this site.

    Can you give us an idea of what kind of output we should expect? I ran your code (with my own starting string "I wish I could write a sentence using") and got lots of stuff like this:

    2 94-acdefghinorstuvwxy 3 89-cefghinorstuvwxy 4 68-cefghinortuvwy 7 45-efghinorstv 8 26-efhilnorstuvwx 10 22-fghinorstuwxy
    Will I get the full sentence if I wait long enough?

    It's certainly an interesting puzzle.

    jarich

      This output lines are just to convince you that the program is running. The first number is the number of iterations. Next is the score of the best attempt so far followed by the letters whose count is not right. Score of 5 means the whole sentence is 'off by 5'. Every $RESET iterations the best number is reset so you can see more work being done.

      I don't know if eventually a sentence will resolve. I tend to think some sentences don't have a solution. I've run the program for many millions of iterations over many hours and not found an answer. Even with a run this long I'm sure only a small fraction of possibilities were tried. I've also had it finish in five minutes.

      I think I need to run the same sentence many times to see if there is any consistancy about how many iterations it takes.

      GoodLuckFoo

      I know this was covered in Hofstadter's book 'Godel, Escher, Bach' (Excellent book, well worth reading), and seem to recall that if you could prove that every sentence would eventually terminate, or prove that a particular sentence would never terminate, then you would have just proven a rather major mathematical theory.

      Bonus points for proving it with a Perl script :)

Re: Solving Meta Sentences
by Abigail-II (Bishop) on May 30, 2002 at 14:30 UTC
Re: Solving Meta Sentences
by abstracts (Hermit) on Jun 05, 2002 at 05:52 UTC
    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.

      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?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://170159]
Approved by broquaint
Front-paged by MeowChow
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (9)
As of 2014-07-29 23:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (229 votes), past polls