Hi!
Plese note that this message uses ISO 8859-7 and contains greek
letters. For MUAs not capable of displaying this encodig I added
transliteration as well as TeX notation.
At Sat, 8 Jul 2006 00:21:37 +0900, Brown, Warren wrote:
> So is it "pangram" or "panagram"?
The word is "pangram".
The origin of "pangram" is greek "pan gramma" ("παν γραμμα", TeX
notation "\pi\alpha\nu \gamma\rho\alpha\mu\mu\alpha") meaning "every
letter".
Josef 'Jupp' Schugt
aha right you are! I was using to_i in my code, and there lies my problem.
On 09/07/2006, at 8:17 PM, Tom Rauchenwald wrote:
"Tim Hollingsworth" <timhollingsworth@gmail.com> writes:
Hello
First post here, by the way. Greetings to all:) New to ruby, love it, slaps
on backs all round.While I haven't solved the pangram problem, I did find what appears to be a
bug in Numeric.divmod on large numbers, as can be seen when using
Bignum.modulo:irb(main):017:0> 1e22 % 1e21
=> 0.0
irb(main):018:0> 1e23 % 1e22
=> 9.99999999999999e+021whoops!
Not quite. 1e23 is a float, that's why you run into precision
problems. This has been discussed here not long ago.
If you use Bignums it works as expected:,----
> irb(main):001:0> 1e23.class
> => Float
> irb(main):002:0> (10**23).class
> => Bignum
> irb(main):003:0> 10**23 % 10**22
> => 0
`----Tom
From: Daniel Martin [mailto:martin@snowplow.org]
Sent: Monday, July 10, 2006 4:18 AMSimon Kröger <SimonKroeger@gmx.de> writes:
> (this is my second version, the other one is longer and
uses a slightly
> other algorithm (and is sometimes even faster) but i like this one)Huh. I must say that when I saw your program, it wasn't at all what I
expected - namely, you are changing all 26 letters at once, and then
recalculating. I had assumed you were doing one letter at a time,
which I found to be much, much faster than doing all 26 at once.
Ok, I will post my other version as soon as I'm home again.
Btw: nice idea to use Bignums 
I'm going to have to look into NArray, clearly. In fact, I think I'll
try converting my solution to use NArray.
yes, some of the stuff is a little bit mind bending (using 'true' or
'false' for slicing dimensions for example) but you get true C speed
while implementing in ruby - that's fun.
cheers
Simon
... and a good bit of luck rolling the rand() dice
On Sat, Jul 08, 2006 at 03:38:36AM +0900, brian.mattern@gmail.com wrote:
It looks like the exact wording of the prelude has a large effect on how
quickly a solution can be found.
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.... 
-Mat
On Jul 7, 2006, at 4:47 PM, Simon Kröger wrote:
James Edward Gray II wrote:
On Jul 7, 2006, at 12:34 PM, brian.mattern@gmail.com wrote:
Is it a spoiler if we post a resulting pangram (no code)?
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.39scheers
Simon
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
On Jul 7, 2006, at 22:47 , Simon Kröger wrote:
James Edward Gray II wrote:
On Jul 7, 2006, at 12:34 PM, brian.mattern@gmail.com wrote:
Is it a spoiler if we post a resulting pangram (no code)?
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.39scheers
Simon
"Kroeger, Simon (ext)" <simon.kroeger.ext@siemens.com> writes:
yes, some of the stuff is a little bit mind bending (using 'true' or
'false' for slicing dimensions for example) but you get true C speed
while implementing in ruby - that's fun.
Unfortunately, I can't actually use NArray on my fast machine as I
don't have VC 6.0 on it. (Windows, using the one-click installer)
"true C speed" on my 500Mhz K6 that's already heavily loaded with lots
of spamassassin work is significantly less impressive.
Huh. I must say that when I saw your program, it wasn't at all what I
expected - namely, you are changing all 26 letters at once, and then
recalculating. I had assumed you were doing one letter at a time,
which I found to be much, much faster than doing all 26 at once.Ok, I will post my other version as soon as I'm home again.
Here is the second version (which was my first version):
--------------------------------------------------------------------
require 'narray'
class NArray; include Enumerable; end
srand(1)
NUMS = %w(no one two three four five six seven eight nine ten eleven) +
%w(twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen)
TENS = [nil] + %w(teen twenty thirty forty fifty sixty seventy eighty ninety)
class Fixnum
def to_english
return NUMS[self] if self < 20
return TENS[self / 10] if (self % 10).zero?
TENS[self / 10] + '-' + NUMS[self % 10]
end
end
class String
def to_na
count = NArray.byte(26)
each_byte do |b|
count[b - ?a] += 1 if b >= ?a and b <= ?z
count[b - ?A] += 1 if b >= ?A and b <= ?Z
end
count
end
end
text = "This is a pangram from simon, it contains "
number = (0..99).map{|i| i.to_english.to_na + (i > 1 ? 's' : '').to_na}
guess = NArray.byte(26).fill!(1)
real = guess + text.to_na + 'and'.to_na + (number[1] * 26)
i, r, g, changed = nil, nil, nil, true
while changed do
changed = false
26.times do |i|
g = guess[i]
r = real[i]
if g != r
real.sbt! number[g]
guess[i] = g = (g < r ? g : r) + rand((g - r).abs + 1)
real.add! number[g]
changed = true
end
end
end
s = guess.zip([*(' a'..' z')]).map{|g, l| g.to_english + l + (g>1 ? "'s":"")}
result = text + s[0..-2].join(', ') + ' and ' + s.last + '.'
puts result
puts(result.to_na == guess)
--------------------------------------------------------------------
It's quite similar except the loop.
cheers
Simon
And here's to you, Mr. Robinson....
martin
On 7/8/06, brian.mattern@gmail.com <brian.mattern@gmail.com> wrote:
On Sat, Jul 08, 2006 at 03:38:36AM +0900, brian.mattern@gmail.com 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
Mat Schaffer 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
On Jul 7, 2006, at 4:47 PM, Simon Kröger wrote:
Have you tried with different sentances?
On 7/7/06, Christoffer Lernö <lerno@dragonascendant.com> wrote:
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
On Jul 7, 2006, at 22:47 , Simon Kröger wrote:
> James Edward Gray II wrote:
>> On Jul 7, 2006, at 12:34 PM, brian.mattern@gmail.com wrote:
>>
>>> Is it a spoiler if we post a resulting pangram (no code)?
>>
>> 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
>
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
On Sat, Jul 08, 2006 at 08:06:27AM +0900, Christoffer Lern? wrote:
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
Christoffer Lernö wrote:
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
Christoffer Lernö <lerno@dragonascendant.com> writes:
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:
...but it took my program 8018361 iterations.
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.
Simon Kröger <SimonKroeger@gmx.de> writes:
Here is the second version (which was my first version):
--------------------------------------------------------------------
--------------------------------------------------------------------It's quite similar except the loop.
Indeed, this is more what I expected - and this is a distinctly
different algorithm than the first solution you posted. In fact, your
main loop is pretty much identical to mine, except that you were using
NArray whereas I was using a bignum to hold the frequency. This meant
that it was much more cumbersome for me to extract each component and
update than it was for you.
I think that this algorithm itself is significantly faster than the
update-all-26-at-once version, and the only reason you see an
advantage to the update-all-26-at-once approach is because you can do
almost all of it by calling NArray vector operations.
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
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
On Jul 7, 2006, at 5:27 PM, Simon Kröger wrote:
Mat Schaffer 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.172sNow if only I could figure out how to actually generate a working
sentence....
-Matwell, I'm not sure if it is possible for every start of a sentence,
perhaps try another. (any thoughts from the mathematicians out there?)
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?)
Not all sentences can be completed to a pangram. Try a sentence
containing 999998 a's and a less than, say, 500 of all other letters.
Yes, I agree that such an example cannot be realized by en english
sentence, but a greater number of other letters could be allowed by
appropriately lowering the number of a's (it could be difficult to
prove, though).
In italian one can construct a counterexample with 'only' 1998 l's
(this is based on the fact that 1999 contains two l's, while 2000
containes 2, and no number less than 1000 contains l's).
Paolo Capriotti
require "integer"
class Pangrams
TIMES = 10000
def pos_add(str, arr26)
(0...str.length).each do |i|
next if (str[i]< "a"[0])||(str[i]>"z"[0])
arr26[str[i]-"a"[0]]+=1
end
arr26
end
def initialize
@cardinals = Array.new(50) {|i| i.to_i.to_english }
@ref_array = []
@cardinals.each do |num_str|
pos_vec = Array.new(26, 0)
pos_vec = self.pos_add(num_str, pos_vec)
pos_vec["s"[0]-"a"[0]] += 1 unless num_str == "one"
@ref_array << pos_vec
end
end
def do_pangram
@start_str = "This is Nasir's pangram and the count is "
@start_str_cnt_arr = Array.new(26, 0)
@start_str_cnt_arr = self.pos_add(@start_str, @start_str_cnt_arr)
@char_cnt_arr = Array.new(26, 0)
#@nchar_cnt_arr = Array.new(26, 0)
srand
#0.upto(25) {|x| @char_cnt_arr[x]=rand(@cardinals.length) } #init
loop do
0.upto(25) {|x| @char_cnt_arr[x]=rand(@cardinals.length) } #init
TIMES.times do
val = true
0.upto(25) do |idx|
t = self.evaluate_at(idx)
val &&= t
end
if val
puts "Solution found!"
puts print(@start_str, @char_cnt_arr)
exit
end
end
puts "#{TIMES} mark"
0.upto(25) do |idx|
puts "At #{idx} current=#{@char_cnt_arr[idx]}, actual=#{
self.count_char_at(idx)}"
end
puts "-----------------------------------"
end
end # do_pangram
def evaluate_at(idx)
current_cnt = @char_cnt_arr[idx]
actual_cnt = self.count_char_at(idx)
ret = true
if current_cnt != actual_cnt
#printf("*")
v1 = current_cnt - ((current_cnt-actual_cnt)*rand).round
v2 = current_cnt - ((current_cnt-actual_cnt)*rand).round
if actual_cnt > current_cnt
@char_cnt_arr[idx] = [v1,v2].max
else
@char_cnt_arr[idx] = [v1,v2].min
end
ret = false
end
ret
end
# index in char_cnt_arr, 'a' is 0 'z' is 25
# Gives the current count of the character in the string
def count_char_at(i)
count = @start_str_cnt_arr[i] # assume only orig string for start
count += 1 # always 1a, 1b etc
@char_cnt_arr.each do |cnt|
count += (@ref_array[cnt])[i] #ref_arr[0] is zero
end
count
end
def print(str, arr)
my_str = str
fmts = "%s %c, "
fmtp = "%s %c's, "
arr.each_with_index do |elm, i|
if elm==1
my_str << sprintf(fmts, @cardinals[elm], 97+i)
else
my_str << sprintf(fmtp, @cardinals[elm], 97+i)
end
end
yield my_str if block_given?
my_str
end
end #class
p = Pangrams.new
p.do_pangram
=begin
This re-uses quiz #25's solution by Glenn PArker.
The algorithm looks simple enough but there is something wrong with this
implementation that it does not converge, sometimes never.
Going by the Pangram defintion I am just comparing the current (guessed)
with actual (counted) and if different replacing the current with a random
number between current and actual (inclusive) with a bias towards actual.
This is what I understood it to be, but there is obviously something that I
am missing as this is terribly inefficient. (Mostly going into orbits)
You may notice that I have tried both changing current value one at a time
and also accumulating changes in @nchar_cnt_arr and changing in one go. The
convergence has been elusive in either case.
One way for me is to start looking at other solutions (which I will
certainly do), but it would be a great help if someone points me towards a
flaw in this.
Also since I am new to Ruby, any general suggestion in Ruby usage will be
greatly appreciated.
On a side note, has anyone tried any other algorithm besides RR?
Specifically has anyone tried simulated annealing or a variation? I tried
unsuccesfully (again) using SA yesterday.
=end
--
Nasir Khan
err... 2000 contains _one_ l in italian.
Paolo Capriotti
On 7/11/06, Paolo Capriotti <p.capriotti@gmail.com> wrote:
In italian one can construct a counterexample with 'only' 1998 l's
(this is based on the fact that 1999 contains two l's, while 2000
containes 2, and no number less than 1000 contains l's).