# Re: Panagrams (#86)

**URL:** <https://www.ruby-forum.com/t/re-panagrams-86/97611>\
**Category:** Ruby\
**Created:** [July 8, 2006, 7:10pm UTC](https://www.ruby-forum.com/t/re-panagrams-86/97611 "2006-07-08T19:10:51Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [July 8, 2006, 7:10pm UTC](https://www.ruby-forum.com/t/re-panagrams-86/97611/1 "2006-07-08T19:10:51Z")

</div>

Oops. I accidentally sent this just to Simon; it was supposed to go  
to the list:

Simon Kröger [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> Well, what’s an iteration in your code?
> 
> I found a solution (the same) to your sentence above after  
> 255062 full circles over all 26 letters. (changing only some  
> of them each time) It took 36s on my laptop. (Pentium M 2.1 GHz)
> 
> I ran it again and it took 134s and did 10105853 changes to  
> the original guess (counting each changed count separately).

I think here we see part of the reason why Simon’s code works faster.  
He’s using a different search algorithm than we are. What I’m doing,  
and I suspect that what Christoffer is doing as well, is taking an  
initial set of 26 letter counts, figuring out the sentence that works  
out to,(\*) and then with the 26 counts in the worked out sentence  
choosing a random value in between to get a new slate of letter  
counts.

However, it would appear that Simon is recalculating the whole  
sentence after each letter re-adjustment, rather than recalculating it  
only after adjusting all 26 counts. This apparently leads to a much  
faster solution.

> Obviously (at least with my algorithm) it depends on luck.  
> And for the total Time it takes it depends on your PC and  
> optimization.

My PC specs out at faster than yours, even if I am running ruby under  
cygwin, that doesn’t turn sub-minute times into over an hour. I think  
the “adjust one and recalculate” approach is just a faster approach.

(\*) Or something equivalent after optimization. I don’t actually  
build the sentence each time. But the point is that I do adjust the  
frequencies of all letters between recalculating the letter counts  
found in the sentence.

==================================

Having now changed to that method, (change one letter and recalculate)  
I’m now getting sub-minute times reasonably frequently. I’m still not  
getting anywhere near the times quoted, but I’m going to try some  
other optimizations to see what I can get.

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [July 8, 2006, 7:39pm UTC](https://www.ruby-forum.com/t/re-panagrams-86/97611/2 "2006-07-08T19:39:06Z")

</div>

Daniel M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> Having now changed to that method, (change one letter and recalculate)  
> I’m now getting sub-minute times reasonably frequently. I’m still not  
> getting anywhere near the times quoted, but I’m going to try some  
> other optimizations to see what I can get.

Indeed:  
$ time ruby /cygdrive/c/Temp/sallowsgram2.rb  
30607

Daniel M.'s sallowsgram program produced a sentence with eight  
'a’s, one ‘b’, three 'c’s, five 'd’s, thirty-eight 'e’s, eight 'f’s,  
seven 'g’s, ten 'h’s, si xteen 'i’s, one ‘j’, one ‘k’, four 'l’s, four  
'm’s, twenty-two 'n’s, fourteen 'o’s, three 'p’s, one ‘q’, thirteen  
'r’s, twenty-nine 's’s, twenty-five 't’s, five 'u’s, seven 'v’s, eight  
'w’s, two 'x’s, five 'y’s, and one ‘z’.

real 0m7.685s  
user 0m7.468s  
sys 0m0.046s

On the other hand, using this as a prefix:  
"The program from removed\_email\_address@domain.invalid produced a sentence with "  
yielded no result after over two hours and 33 million iterations over  
all 26 letters.

I’m thinking that there may be times when the algorithm wanders off  
and gets stuck in a region where there are no solutions. I’m going to  
try a tweak to let it get out of cages like that.

(Of course, there may actually be no solution with that prefix.  
Writing a program to prove that, though, is more than just a weekend  
project.)

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [July 8, 2006, 11:59pm UTC](https://www.ruby-forum.com/t/re-panagrams-86/97611/3 "2006-07-08T23:59:57Z")

</div>

Daniel M. wrote:

> Daniel M.'s sallowsgram program produced a sentence with eight  
> 'a’s, one ‘b’, three 'c’s, five 'd’s, thirty-eight 'e’s, eight 'f’s,  
> seven 'g’s, ten 'h’s, si xteen 'i’s, one ‘j’, one ‘k’, four 'l’s, four  
> 'm’s, twenty-two 'n’s, fourteen 'o’s, three 'p’s, one ‘q’, thirteen  
> 'r’s, twenty-nine 's’s, twenty-five 't’s, five 'u’s, seven 'v’s, eight  
> 'w’s, two 'x’s, five 'y’s, and one ‘z’.
> 
> real 0m7.685s  
> user 0m7.468s  
> sys 0m0.046s

These numbers don’t say much. My algorithm:

With srand(1):  
Time: 19.703s

With srand(2):  
Time: 3.36s

With srand(3):  
Time: 0.781s

but of course it looks much better than hours.  
We will know more tomorrow 🙂

I would be interested in a version without random, but i don’t  
have much time until tomorrow night.

cheers

Simon