[QUIZ] Panagrams (#86)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Darren Kirby

One thing that interests me are word puzzles and language oddities. One such
example is the self-documenting panagram. If a panagram is a sentence that uses
every letter in the alphabet, then a self-documenting panagram is a sentence
that enumerates its own letter count. Simple enough, but what if we state that
the letter count must be spelled ie: 'twenty-seven' instead of '27'. Now we
have a challenge.

A while back I wrote a script in Python that finds these sentences. Today I
rewrote it in Ruby and it found me this sentence:

Darren's ruby panagram program found this sentence which contains exactly
nine 'a's, two 'b's, five 'c's, four 'd's, thirty-five 'e's, nine 'f's,
three 'g's, nine 'h's, sixteen 'i's, one 'j', one 'k', two 'l's, three 'm's,
twenty-seven 'n's, fourteen 'o's, three 'p's, one 'q', fifteen 'r's,
thirty-four 's's, twenty-two 't's, six 'u's, six 'v's, seven 'w's, six 'x's,
seven 'y's, and one 'z'.

My script does have its problems, and I would love to see what kind of code the
Ruby experts could come up with to find self-documenting panagrams.

There is a lot more info on self-documenting panagrams at this address:

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

 

[Matthew Moss]

So is it "pangram" or "panagram"?

 

[Matthew Moss]

Nevermind, answered my own question with the dictionary: pangram.

 

[James Edward Gray II]

So is it "pangram" or "panagram"?

Good catch, I didn't even notice the name discrepancy. Pangram does
appear to be the correct term.

James Edward Gray II

 

[Brown, Warren]

So is it "pangram" or "panagram"?

The word is "pangram". Some people misspell it as "panagram",
probably due to an association with the word "anagram", another word
puzzle favorite.

- Warren Brown

 

[brian.mattern]

Is it a spoiler if we post a resulting pangram (no code)?

I got one in:
real 1m17.089s
user 1m8.444s
sys 0m2.492s

on an athlon 64 300+

Brian

 

[brian.mattern]

Is it a spoiler if we post a resulting pangram (no code)?

I got one in:
real 1m17.089s
user 1m8.444s
sys 0m2.492s

on an athlon 64 300+

Brian

Actually, I lied. Almost correct, but at least one number is off...

 

[James Edward Gray II]

Is it a spoiler if we post a resulting pangram (no code)?

Not at all. Please do.

James Edward Gray II

 

[brian.mattern]

Not at all. Please do.

How about:

rephorm@boru ~/code/ruby/quiz/pangram $ time ruby pangram.rb > p
real 0m28.613s
user 0m27.474s
sys 0m1.000s

rephorm@boru ~/code/ruby/quiz/pangram $ cat p
a ruby quiz solution found this sentence enumerating four a's, two b's,
two c's, three d's, thirty-four e's, nine f's, three g's, eight h's,
sixteen i's, one j, one k, three l's, two m's, twenty-five n's, fifteen
o's, one p, two q's, eleven r's, twenty-nine s's, twenty-five t's, nine
u's, four v's, nine w's, three x's, six y's, and two z's

rephorm@boru ~/code/ruby/quiz/pangram $ ruby verify.rb p
Sentence passes!



It looks like the exact wording of the prelude has a large effect on how
quickly a solution can be found.

Brian

 

[brian.mattern]

It looks like the exact wording of the prelude has a large effect on how
quickly a solution can be found.

... and a good bit of luck rolling the rand() dice

 

[Martin DeMello]

... and a good bit of luck rolling the rand() dice

And here's to you, Mr. Robinson....

martin

 

[tsuraan]

Actually, I lied. Almost correct, but at least one number is off...

I was wondering where you can get an athlon64 300+

 

[Simon Kröger]

Not at all. Please do.

James Edward Gray II

This is the pangram from simon, there are four a's, one b, one c, one d,
thirty-two e's, seven f's, four g's, nine h's, eleven i's, one j, one k,
two l's, four m's, twenty n's, eighteen o's, two p's, one q, thirteen
r's, twenty-seven s's, eighteen t's, six u's, four v's, six w's, three
x's, four y's, one z.
Time: 8.39s

cheers

Simon

 

[Mat Schaffer]

This is the pangram from simon, there are four a's, one b, one c, =20
one d,
thirty-two e's, seven f's, four g's, nine h's, eleven i's, one j, =20
one k,
two l's, four m's, twenty n's, eighteen o's, two p's, one q, thirteen
r's, twenty-seven s's, eighteen t's, six u's, four v's, six w's, three
x's, four y's, one z.
Time: 8.39s

cheers

Simon

Just for the sake of nitpicking, seems like the following ending =20
would be more appropriate:
"...three x's, four y's and one z."

Now if only I could figure out how to actually generate a working =20
sentence....
-Mat

 

[Simon Kröger]

On Jul 7, 2006, at 4:47 PM, Simon Kröger wrote:

Just for the sake of nitpicking, seems like the following ending would
be more appropriate:
"...three x's, four y's and one z."

more like this?

This is a pangram from simon, it contains six a's, one b, two c's, two
d's, thirty e's, eight f's, three g's, seven h's, fifteen i's, one j,
one k, one l, four m's, twenty-four n's, sixteen o's, two p's, one q,
nine r's, twenty-nine s's, twenty-one t's, three u's, five v's, seven
w's, three x's, five y's and one z
Time: 6.172s

Now if only I could figure out how to actually generate a working
sentence....
-Mat

well, I'm not sure if it is possible for every start of a sentence,
perhaps try another. (any thoughts from the mathematicians out there?)

cheers

Simon

 

[Simon Kröger]

This is a pangram from simon, it contains six a's, one b, two c's, two
d's, thirty e's, eight f's, three g's, seven h's, fifteen i's, one j,
one k, one l, four m's, twenty-four n's, sixteen o's, two p's, one q,
nine r's, twenty-nine s's, twenty-one t's, three u's, five v's, seven
w's, three x's, five y's and one z
Time: 6.172s

Sorry for replying to myself, i thought this might be interesting:

This is a pangram from simon, it contains six a's, one b, two c's, two
d's, twenty-six e's, ten f's, four g's, five h's, fifteen i's, one j,
one k, one l, four m's, twenty-four n's, eighteen o's, two p's, one q,
nine r's, twenty-nine s's, eighteen t's, six u's, three v's, seven w's,
four x's, four y's and one z
Time: 22.562s

It's another solution for the same beginning.

cheers

Simon

 

[Christoffer Lernö]

This is really crazy.

Either people have optimized things a whole lot better than me (not =20
unlikely, I haven't made any real attempts at optimizing things), or =20
I am using a bad algorithm.

I didn't time the solution:

a ruby quiz solution found this sentence enumerating four a's, two =20
b's, two c's, three d's, thirtyfour e's, nine f's, three g's, eight =20
h's, sixteen i's, one j, one k, three l's, two m's, twentyfive n's, =20
fifteen o's, one p, two q's, eleven r's, twentynine s's, twentyfive =20
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

 

[Mat Schaffer]

more like this?

This is a pangram from simon, it contains six a's, one b, two c's, two
d's, thirty e's, eight f's, three g's, seven h's, fifteen i's, one j,
one k, one l, four m's, twenty-four n's, sixteen o's, two p's, one q,
nine r's, twenty-nine s's, twenty-one t's, three u's, five v's, seven
w's, three x's, five y's and one z
Time: 6.172s


well, I'm not sure if it is possible for every start of a sentence,
perhaps try another. (any thoughts from the mathematicians out there?)

I think the method by which you get there plays a big part too. I =20
ran my current version for about 15 minutes yielding no correct =20
result. And my preamble is taken from the original links sent to the =20=

list as description.

Feels like it would be cheating to read and mimic the perl =20
implementation on the site.

-Mat=

 

[brian.mattern]

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

 

[Simon Kröger]

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

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).

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

cheers

Simon