On Thu, 03 Aug 2006 01:08:21 +0900, Peter Hickman wrote:

> Here's how it goes on my box:
> 
> [Latin]$ time ruby latin2.rb > r5
> 
> real    0m16.283s
> user    0m15.380s
> sys     0m0.498s
> 
> Which means that your computer is about as crap as mine :)

Yes.  I was really suprised to see that your timings where longer than
mine :)  But I am happy with the speed of my computer, though emacs
startup is a bit slow... :)

> I will add it 
> to the pages and make it a download. I think I need a table summarising 
> the timings.

I just realised that it is better to move the permutations on the
row string (the ones that use String#tr) outside the row permutations,
to avoid recalculating the rows each time. The only method I changed is
print_solution.  The program runs almost twice as fast now! (0m7.8s on my
computer).

Regards,
Kristof

----------------- latin.rb, version 2 -----------------------

require 'permutation'

$size = (ARGV.shift || 5).to_i
MaxVal = $size-1

RowPermutations = Permutation.new($size).map{|p| p.value}
BaseStr = (2..$size).to_a.join
StrPermutations = Permutation.new($size-1).map{|p| p.project(BaseStr)}

StartColumns = (1..MaxVal).to_a
def init_columns(el)
   a = StartColumns.dup
   a.delete_at(el-1)
   return a
end

def insert(sqr, num, row, columns)
   insert(sqr, num, row+1, columns) if (row == num)
   columns.each do |col|
      next if sqr[row][col] != ?.
      sqr[row][col] = num + ?1
      if (row == MaxVal)
         insert(sqr, num+1, 1, init_columns(num+1))
      elsif (num == MaxVal && row == MaxVal - 1)
         print_solution(sqr)
      else
         insert(sqr, num, row+1, columns - [col])
      end
      sqr[row][col] = ?.
   end
end

def print_solution(sqr)
   StrPermutations.each do |sp|
      newsqr = sqr.map { |r| r.tr(BaseStr, sp) }
      RowPermutations.each do |rp|
         rp.each do |r|
            print newsqr[r]
            print ":"
         end
         puts
      end
   end
end

$square = [("1" + BaseStr)] +
   Array.new($size-1) { |i| (i+2).to_s + "." * ($size - 1) }

insert($square, 0, 1, StartColumns)