PDX.rb I Spy 2011-12-06

tic-tac-toe-count-fun-bug.rb

require 'rubygems'

def row(i)
  [i % 3, (i/3) % 3, (i/9) % 3]
end

def row_number(r)
  r[0]+3*r[1]+9*r[2]
end


def board(i)
  [ row(i), row(i/27), row(i/(27*27)) ]
end

def board_number(b)
  row_number(b[0]) + 27*row_number(b[1]) + 27*27*row_number(b[2])
end

raise "Aieeee!" if (0...3**9).any? do |board_num|
  board_num != board_number(board(board_num))
end

def valid?(b)
  b = board(b) unless b.is_a? Array
  xs = b.flatten.count(1)
  os = b.flatten.count(2)
  (xs == os || xs == os+1) && (!wins?(b,1) || !wins?(b,2))
end

def wins?(b,p)
  b = board(b) unless b.is_a? Array
  lines_of_3 = b + b.transpose
  lines_of_3 << (0...3).collect { |i| b[i][i] }
  lines_of_3 << (0...3).collect { |i| b[i][3-i-1] }
  lines_of_3.include? [p,p,p]
end

def draw(b)
  b = board(b) unless b.is_a? Array
  b.collect { |r| r.join(' ') }.join("\n")
end

def canonicalize(b,mode=:transpose)
  b = board(b) unless b.is_a? Array
  alternatives = case mode
                 when :transpose;  [canonicalize(b,:left_right),canonicalize(b.transpose,:left_right)]
                 when :left_right; [canonicalize(b,:top_bottom),canonicalize(b.collect { |r| r.reverse },:top_bottom)]
                 when :top_bottom; [             b,                          b.reverse]
                 end
  alternatives.collect {|x| board_number(x) }.min
end

unique_boards = 0
(0...3**9).each { |i| (puts draw(i), "==="; unique_boards += 1) if valid?(i) && canonicalize(i) == i }
print "There are #{unique_boards} unique 3x3 boards.\n"

unique_boards = Hash.new(0)
(0...3**9).each { |i| unique_boards[canonicalize(i)] += 1 if valid?(i) }
print "There are #{unique_boards.count} unique 3x3 boards.\n"
unique_boards.each {|b,count| puts draw(b), "#{count} ---", "Board is valid: #{valid?(b).inspect}"}

puts unique_boards.keys.sort.inspect

def canonicalize(b)
  b = board(b) unless b.is_a? Array
  alternatives = [b,b.reverse]
  alternatives |= alternatives.map { |x| x.collect { |r| r.reverse } }
  alternatives |= alternatives.map { |x| x.transpose }
  alternatives.collect {|x| board_number(x) }.min
end

unique_boards = 0
(0...3**9).each { |i| unique_boards += 1 if valid?(i) && canonicalize(i) == i }
print "There are #{unique_boards} unique 3x3 boards.\n"

unique_boards = Hash.new(0)
(0...3**9).each { |i| unique_boards[canonicalize(i)] += 1 if valid?(i) }
print "There are #{unique_boards.count} unique 3x3 boards.\n"