From: Mariano Kamp <mariano.kamp@...>
Date: 2006-11-22T23:39:02+09:00
Subject: Ruby hangs on OSX

--Apple-Mail-10--931944233
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

Hi,

   I encountered a strange problem.

   When running "ruby soduku_test.rb -n test_next_cell" the process  
hangs and eats up all of the assigned CPU . I have no idea why that  
is ... I asked a friend to run it on windows and it does work there.  
The program yield in a stack overflow.

   I recently reinstalled my computer and used darwinports. I don't  
think that I've seen that problem before. I also reinstalled ruby  
again, but with not much success and the same thing happens on  
another Mac too.

   Installing ruby the way I used to do it before, using the  
hivelogic tutorial, also didn't work.

   That are the versions that fail:

   ruby 1.8.5 (2006-08-25) [i686-darwin8.8.3] # darwin ports 1.3.1,  
gcc 4.0
   ruby 1.8.4 (2005-12-24) [i686-darwin8.8.3] # directly from the  
sources (hivelogic tutorial)
   ruby 1.8.2 (2004-12-25) [universal-darwin8.0] # comes with Tiger

   Both Macs (MB C2D, MBP CD) are running OSX 10.4.8 with all updates.

   uname -v:
Darwin Kernel Version 8.8.3: Wed Oct 18 21:57:10 PDT 2006;  
root:xnu-792.15.4.obj~4/RELEASE_I386

   A stack trace of the "working" run on Windows is below this mail.

   I attached the code. Unfortunately I haven't been able to isolate  
the problem, but at least the code consistently fails.

   Any ideas? Can somebody please try it out on another Mac? I will  
also do that later on.

Cheers,
Mariano


--Apple-Mail-10--931944233
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	name=sudoku_test.rb
Content-Disposition: attachment;
	filename=sudoku_test.rb

require 'test/unit'
require 'sudoku'

class SudokuTests < Test::Unit::TestCase
  def values(cells)
    cells.collect{|cell|if cell.value then cell.value else "." end}.join
  end

  def field1
    data = <<-EOF
    123456789
    ..4......
    ..5......
    ...1.3...
    ...789...
    ...564...
    ......4..
    ......5..
    987645321
    EOF
    
    Sudoku.new data
  end
  
  def test_solve
    field1.solve
  end

  def test_each
    count = 0
    field1.each {count+=1}
    assert_equal 81, count
  end

  def test_all_cells
    assert_equal 81, field1.send(:all_cells).size
  end
  
  def test_next_cell
    sudoku = field1
    assert cell = sudoku.row(5)[5]
    assert_equal cell, sudoku.send(:next_cell)
    old_values_count = 0
    0.upto(20) do 
      cell = sudoku.send(:next_cell)
      cell.value="2"
      assert cell.possible_values.size >= old_values_count
      old_values_count = cell.possible_values.size
    end
  end
  
  def test_possible_values
    sudoku = field1
    assert_equal "", sudoku.row(0)[0].possible_values.join  
    assert_equal "678", sudoku.row(1)[0].possible_values.join  
    assert_equal "2389", sudoku.row(1)[3].possible_values.join  
    assert_equal "126", sudoku.row(1)[6].possible_values.join  
  end
  
  
  def test_field
    sudoku = field1

    assert_equal "123456789", values(sudoku.row(0))
    assert_equal "987645321", values(sudoku.row(8))

    assert_equal "1.......9", values(sudoku.column(0))
    assert_equal "1.......9".reverse, values(sudoku.column(8))

    assert_equal "123..4..5", values(sudoku.box(0))
    assert_equal "4..5..321", values(sudoku.box(8))

    cell1 = sudoku.row(0)[0]
    assert_equal 21, cell1.dependent_cells.size

    assert_equal "1", cell1.value

    assert_equal "1.......9", values(cell1.column)
    assert_equal "123456789", values(cell1.row)
    assert_equal "123..4..5", values(cell1.box)
    
    cell2 = sudoku.row(3)[0]
    assert_equal nil, cell2.value
    
    assert_equal "1.......9", values(cell2.column)
    assert_equal "...1.3...", values(cell2.row)
    assert_equal ".........", values(cell2.box)
   
  end
end
--Apple-Mail-10--931944233
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	name=sudoku.rb
Content-Disposition: attachment;
	filename=sudoku.rb

require 'set'

class Sudoku
  def initialize(data)
    cell_values = data.scan(/[.|\d]/)
    
    @rows = Array.new(9) do |row_index| 
      row = Array.new(9) do 
        cell_value = cell_values.shift
        cell_value = nil if cell_value == '.'
        cell = Cell.new(self, cell_value)
        cell.row_index = row_index
        cell
      end
    end
    
    @columns = Array.new(9) do |col_index|
      @rows.collect do |row|
        cell= row[col_index]
        cell.col_index=col_index
        cell
      end
    end
    
    @boxes = Array.new(9) do |box_index|
      from = box_index / 3 * 3
      to = from + 2
      @rows[from..to].collect do |row|
        from = (box_index % 3 * 3 )
        to = from + 2
        cells = row[from..to]
        cells.each do |cell|
          cell.box_index = box_index
        end
        cells
      end.flatten
    end
    
  end
  
  def row(index)
    @rows[index]
  end
  
  def column(index)
    @columns[index]
  end
  
  def box(index)
    @boxes[index]
  end
  
  def each
    all_cells.each {|c| yield c}
  end
  
  def solve
    iteration = 0
    while cell = next_cell and iteration < 55
      iteration+=1
      cell.value = cell.possible_values.first
    end
    if next_cell then puts "Not solved" else puts "Solved" end
    puts self.to_s
    puts "Done with #{iteration} iterations." 
  end
  
  # Returns a character based visualization 
  # of the Sudoku field
  def to_s
    rv = '    '+(0..8).to_a.join(' ') + "\n"
    @rows.each_with_index do |row, i|
      rv << "%3s:%s\n" % [i, row.collect{|c|c.value}.join(' ')]
    end
    rv
  end
    
  private
  def all_cells
    Set.new @rows.collect {|row|row.collect {|cell|cell}}.flatten
  end

  # Returns the next cell without a value
  # weighted by the number of possible values.
  # Cells with only a few possible values make
  # an easier target
  def next_cell
    all_cells.
      find_all{|c|c.value.nil?}. # only unsolved cells
      sort_by{|c|c.possible_values.size}. # less possibilities is better
      first
  end
  
end

class Cell
  attr_accessor :value
  attr_accessor :row_index, :col_index, :box_index
  
  def initialize(sudoku, value = nil)
    @sudoku, @value = sudoku, value
  end
  
  def column
    @column ||= @sudoku.column(col_index)
  end 
  
  def row
    @row ||= @sudoku.row(row_index)
  end
  
  def box
    @box ||= @sudoku.box(box_index)
  end
  
  def dependent_cells
    @dependent_cells ||= Set.new(column + row + box).to_a
  end
  
  def possible_values
    if value
      []
    else
      %w(1 2 3 4 5 6 7 8 9)-dependent_cells.collect{|cell|cell.value}
    end
  end
  
  def to_s
    "Cell #{row_index},#{col_index} value = #{value} possible values=#{possible_values.join(',')}"
  end
end
--Apple-Mail-10--931944233
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed



  1) Error:
test_next_cell(SudokuTests):
SystemStackError: stack level too deep
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:344:in `deq'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:343:in `deq'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:171:in  
`break_outmost_groups'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:197:in `text'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:258:in `pretty_print_cycle'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:224:in `group'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:247:in `nest'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:223:in `group'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:235:in `group_sub'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:222:in `group'
     [.. tons of repetition ]
     C:/dev/ruby/lib/ruby/1.8/pp.rb:142:in `object_address_group'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:192:in `pp_object'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:249:in `pretty_print'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:126:in `pp'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:224:in `group'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:247:in `nest'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:223:in `group'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:235:in `group_sub'
     C:/dev/ruby/lib/ruby/1.8/prettyprint.rb:222:in `group'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:126:in `pp'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:69:in `pp'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:105:in `guard_inspect_key'
     C:/dev/ruby/lib/ruby/1.8/pp.rb:69:in `pp'
     sudoku_test.rb:53:in `test_next_cell'

6 tests, 23 assertions, 0 failures, 1 errors
--Apple-Mail-10--931944233--