Panagrams (#86)

#1

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. 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
#2

So is it “pangram” or “panagram”?

#3

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

#4

On Jul 7, 2006, at 10:13 AM, Matthew M. wrote:

So is it “pangram” or “panagram”?

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

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

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

James Edward G. II

#5

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 B.
#6

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

#7

On Sat, Jul 08, 2006 at 02:34:23AM +0900, removed_email_address@domain.invalid wrote:

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

#8

On Jul 7, 2006, at 12:34 PM, removed_email_address@domain.invalid wrote:

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

Not at all. Please do.

James Edward G. II

#9

On Sat, Jul 08, 2006 at 03:18:26AM +0900, James Edward G. II wrote:

On Jul 7, 2006, at 12:34 PM, removed_email_address@domain.invalid wrote:

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

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

#10

On 7/8/06, removed_email_address@domain.invalid removed_email_address@domain.invalid wrote:

On Sat, Jul 08, 2006 at 03:38:36AM +0900, removed_email_address@domain.invalid wrote:

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

And here’s to you, Mr. Robinson…

martin

#11

On Sat, Jul 08, 2006 at 03:38:36AM +0900, removed_email_address@domain.invalid wrote:

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

#12

James Edward G. II wrote:

On Jul 7, 2006, at 12:34 PM, removed_email_address@domain.invalid wrote:

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

Not at all. Please do.

James Edward G. 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

#13

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

This is the pangram from simon, there are four a’s, one b, one c,
Simon

Just for the sake of nitpicking, seems like the following ending
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
sentence… :frowning:
-Mat

#14

On Jul 7, 2006, at 12:39 PM, removed_email_address@domain.invalid wrote:

Brian

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

I was wondering where you can get an athlon64 300+ :slight_smile:

#15

Mat S. wrote:

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… :frowning:
-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

#16

Simon Kröger wrote:

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

#17

Have you tried with different sentances?

#18

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

#19

On Jul 7, 2006, at 5:27 PM, Simon Kröger wrote:

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
ran my current version for about 15 minutes yielding no correct
result. And my preamble is taken from the original links sent to the
list as description.

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

-Mat

#20

Christoffer Lernö removed_email_address@domain.invalid writes:

Is it the optimization or the algorithm I got wrong?
I agree that Simon must be using a different, better algorithm. I
think I’m using the same one that you are, (the randomized Robinsoning
described on the linked page, which is what the perl program there
uses) and with the same prefix get an answer in 16990348 iterations
(so twice as long) and it takes just over 83 minutes.

I /really/ don’t think that the difference between this and the
sub-10-second versions is just luck. I’m going to run the program in
a loop in the background today just to check the luck angle - if every
run takes on the order of an hour to produce output, then clearly
there’s another approach we’re missing.