From: Daniel Martin <martin@...>
Date: 2006-07-14T00:15:42+09:00
Subject: Re: [SUMMARY] Panagrams (#86)

Ruby Quiz <james@grayproductions.net> writes:

> Now that we know what to call them, the question becomes how do we
> generate self documenting pangrams?  The linked article described a
> technique called "Robbinsoning," which is a simple process.  The
> idea is that you start with some random distribution of letter
> counts, build the sentence, adjust the counts to reflect the actual
> sentence counts, rebuild, adjust, etc.  You can zero in on a
> solution in this fashion and most of the submitted solutions used
> something along these lines.

Note that the discussion of the different ways to solve this problem
pointed up two distinctly different "randomized Robbinsoning"
algorithms:

1) rebuild the sentence (or recalculate the frequencies) after each
letter adjustment.  This was what my code did.

2) Go through each letter doing randomized adjustments then, after all
letters have been adjusted, rebuild/recalculate.

To have my program use this second algorithm, you can change the "if"
bit in the main loop to:

 	      actual2 = 0
 	      lettershifts.each{ |y|
 	        g = 0xFF & (guessfreq >> y)
 	        a = 0xFF & (actualfreq >> y)
 	        if (g != a)
 	          d = (g-a).abs
 	          r1 = rand(d+1)
 	          r2 = rand(d+1)
 	          r1=r2 if r1 < r2
 	          r1=-r1 if a<g
 	          if (r1 != 0) then
 	            guessfreq += r1 << y
                    g += r1
 	          end
 	        end
                actual2 += enfreq[g]
 	      }
 	      actualfreq = actual2

But you *really* don't want to do that.  Adjusting all letters before
recalculating the frequencies turns this consistently-under-30-seconds
program into one that takes over an hour to complete.  Note that this
second algorithm is the one followed by the perl script on the page
linked to in the quiz description.

Also note that Simon Kroeger's (first posted) solution follows this
second algorithm but is still able to achieve phenomenally fast speed
because he is able to push all the operations in the lettershifts loop
above into NArray vector operations implemented in C.  In his
alternate solution to this quiz, he uses the first algorithm but needs
to loop over all the letter positions in ruby.  He reports that the
increased speed of the first algorithm and the comparative slowness of
doing the loop in ruby essentially cancel each other out, leading to
both solutions being roughly equivalent in terms of speed.