From: brian.mattern@...
Date: 2006-07-08T14:27:23+09:00
Subject: Re: [QUIZ] Panagrams (#86)

On Sat, Jul 08, 2006 at 08:06:27AM +0900, Christoffer Lern? wrote:
> This is really crazy.
> 
> Either people have optimized things a whole lot better than me (not  
> unlikely, I haven't made any real attempts at optimizing things), or  
> I am using a bad algorithm.
> 
> I didn't time the solution:
> 
> a ruby quiz solution found this sentence enumerating four a's, two  
> b's, two c's, three d's, thirtyfour e's, nine f's, three g's, eight  
> h's, sixteen i's, one j, one k, three l's, two m's, twentyfive n's,  
> fifteen o's, one p, two q's, eleven r's, twentynine s's, twentyfive  
> t's, nine u's, four v's, nine w's, three x's, six y's and two z's
> 
> ...but it took my program 8018361 iterations.
> 
> Is it the optimization or the algorithm I got wrong?
> 
> /Christoffer
> 

I ran mine again and after 10 minutes it hadn't found anything. I did a
basic "randomized Robisonizing" algorithm, so, I think the speed just
depends on luck.

from http://www.cs.indiana.edu/~tanaka/GEB/pangram.txt :

 randomized Robisonizing:
        let's say in candidate(N) which includes the phrase
        "...  eight `a's ..." actually contains 13 `a's.  then
        in candidate(N+1) you pick a random number R between 8
        and 13 (inclusive) and put the phrase "... [R] `a's
        ...".      you do this for each letter.


Brian