Re: Panagrams (#86)

Ruby
1

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

Simon Kröger [email protected] 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.

2

Daniel M. [email protected] 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 [email protected] 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.)

3

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 :slight_smile:

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

cheers

Simon