From: "Simon Kröger" <SimonKroeger@...>
Date: 2006-07-10T05:29:17+09:00
Subject: [SOLUTION][QUIZ] Panagrams (#86)

Hi,

here is my solution: (some remarks are below)
----------------------------------------------------------------------
require 'narray'

class NArray;
  include Enumerable;
  srand(1)
end

class Fixnum
  NUMS = %w(zero one two three four five six seven eight nine ten eleven) +
    %w(twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen)
  TENS = %w(no teen twenty thirty forty fifty sixty seventy eighty ninety)

  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
    freq = NArray.int(26)
    each_byte do |b|
      freq[b - ?a] += 1 if b >= ?a and b <= ?z
      freq[b - ?A] += 1 if b >= ?A and b <= ?Z
    end
    freq
  end
end

text = "This is a pangram from simon, it contains "
nums = NArray[*(0..99).map{|i| i.to_english.to_na + (i>1 ? 's' : '').to_na}]
seed = text.to_na + 'and'.to_na + 1
guess = NArray.int(26).fill!(1)
real = seed + nums[true, guess].sum(1)
rnd = NArray.float(26)

while real != guess
  guess.add! rnd.random!.mul!(real.sbt!(guess)).round
  real.fill!(0).add!(seed).add!(nums[true, guess].sum(1))
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)
----------------------------------------------------------------------

I always wanted to look at NArray because a well known rubyist keeps
promoting it - if it's good enough for the Nasa than it may be good
enough for word puzzles :)

This algorithm is stupid, but why use a scissor if u can have a chain saw?
NArray is such a chain saw, so it doesn't really matter how well you aim.

Ok, the details. First a two dimensional NArray is created containing the
frequencies of all 26 letters in the words 'zero' upto 'ninety-nine'. (nums)

seed contains the frequencies of the static part of the sentence - the
preamble the 'and' and 1 of each letter.

guess is the actual guess and will change over time (very often) I start
with a 1 for every letter (which is obviously wrong)

real contains the frequencies for all letters if one would spell out the
sentence described in guess (one 'a', one 'b', one 'c'... for the initial
guess). To get this we select the lines from nums that correspond to the
numbers (26 times 'one' for the first guess) and sums every column up.
(you start to see the chain saw?)

Ok, now we can start the massacre.

If real == guess we are ready, if not we calculate the error for each
letter (in one step of course: real.sbt!(guess)).
We multiply each error with a random value 0 <= rand < 1
(in one step: rnd.ramdom!.mul!) and add this randomized error back onto
the guess. (again, one step)

All that is left is to calculate the real frequencies again and check
if we hit the spot.

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

cheers

Simon