#!/usr/bin/env ruby

class Othello
	class Stone
		@reverse
		attr_accessor :reverse
	
		def initialize(i, c)
			@i = i
			@c = c
		end
		
		NUM_BLACK = 1
		NUM_WHITE = -1
		NUM_EMPTY = 0
		
		@@black = Stone::new(NUM_BLACK, '●')
		@@white = Stone::new(NUM_WHITE, '○')
		@@empty = Stone::new(NUM_EMPTY, '  ')
		
		def to_i; return @i; end
		def to_s; return @c; end
		def Stone::load(x)
			if x.kind_of?(Fixnum)
				case x
				when NUM_BLACK; return @@black
				when NUM_WHITE; return @@white
				end
			end
			return @@empty
		end
		
		def Stone::black; return @@black; end
		def Stone::white; return @@white; end
		def Stone::empty; return @@empty; end
		
		@@black.reverse = @@white
		@@white.reverse = @@black
		@@empty.reverse = @@empty
		
		private :initialize
		private :reverse=
	end
	
	class State

		BLACK = Othello::Stone::black
		WHITE = Othello::Stone::white
		EMPTY = Othello::Stone::empty
		
		FIRST_STONE = BLACK	#黒が先手
	
		@board
		@board_size
		@order
		
		attr_accessor :board
		protected :board=
		attr_reader :board_size
		attr_accessor :order
		protected :order=
		
		def get_nocheck(i, j)
			return @board[(i * @board_size) + j]
		end
		def set_nocheck(i, j, v)
			@board[(i * @board_size) + j] = v
		end
		
		protected :get_nocheck
		protected :set_nocheck
		
		def [](i, j)
			if i < 0 || j < 0 || i >= @board_size || j >= @board_size then raise 'Index out of bounds!' end
			return get_nocheck(i, j)
		end
		def []=(i, j, v)
			if i < 0 || j < 0 || i >= @board_size || j >= @board_size then raise 'Index out of bounds!' end
			set_nocheck(i, j, v)
		end
		
		def board_dump
			num = 0
			@board.each_with_index{|item, i|
				num += (item.to_i * (3 ** i))
			}
			return num 
		end
		
		def board_load(board_state)
			if board_state.kind_of?(Integer) then
				@board = []
				board_state += ((3 ** (@board_size ** 2)) - 1) / 2
				while board_state > 0
					mod = board_state % 3
					@board << Stone::load(mod - 1)
					board_state -= mod
					board_state /= 3
				end
				while @board.size < @board_size ** 2
					@board << EMPTY
				end
			else
				@board = board_state
			end
			return self
		end
		
		def all_iterator
			i = 0
			j = 0
			while i < @board_size
				yield(i, j)
				j += 1
				if j == @board_size then
					j = 0
					i += 1
				end
			end
		end
	
		def initialize(board_size, board_state = nil, order = FIRST_STONE)
			@board_size = board_size
			if board_state then
				board_load(board_state)
			else
				@board = []
				all_iterator{|i, j| set_nocheck(i, j, EMPTY)}
				init_upper = (board_size / 2).ceil
				init_lower = init_upper - 1
				
				set_nocheck(init_lower, init_lower, WHITE)
				set_nocheck(init_lower, init_upper, BLACK)
				set_nocheck(init_upper, init_lower, BLACK)
				set_nocheck(init_upper, init_upper, WHITE)
			end
			
			@order = order
		end
		
		def is_black?(i, j); return self[i, j] == BLACK; end
		def is_white?(i, j); return self[i, j] == WHITE; end
		def is_empty?(i, j); return self[i, j] == EMPTY; end
		
		def clone
			#copy = dup
			#copy.board = @board.clone
			#return copy
			
			#return Marshal::load(Marshal::dump(self))
			
			return State::new(@board_size, @board.clone, @order)
		end
		
		def order_skip
			#copy = clone
			#copy.order = @order.reverse
			#return copy
			
			return State::new(@board_size, @board.clone, @order.reverse)
		end

=begin
		def directional_iterator(i, j, down, right)
			move = 0
			while true
				i += down
				if i < 0 || i >= @board_size then break end
				j += right
				if j < 0 || j >= @board_size then break end
				move += 1
				yield(get_nocheck(i, j), move)
				#puts "#{i},#{j},#{self[i, j].to_s}"	#Debug
			end
		end
		
		def up(i, j);			directional_iterator(i, j, -1,  0){|item, move| yield(item, move)};	end
		def down(i, j);		directional_iterator(i, j,  1,  0){|item, move| yield(item, move)};	end
		def left(i, j);		directional_iterator(i, j,  0, -1){|item, move| yield(item, move)};	end
		def right(i, j);		directional_iterator(i, j,  0,  1){|item, move| yield(item, move)};	end
		def right_up(i, j);	directional_iterator(i, j, -1,  1){|item, move| yield(item, move)};	end
		def right_down(i, j);	directional_iterator(i, j,  1,  1){|item, move| yield(item, move)};	end
		def left_up(i, j);		directional_iterator(i, j, -1, -1){|item, move| yield(item, move)};	end
		def left_down(i, j);	directional_iterator(i, j,  1, -1){|item, move| yield(item, move)};	end
=end
		
		DIRECTION_TARGETS = [
				[-1,  0],	#上を見る
				[ 1,  0],	#下を見る
				[ 0, -1],	#左を見る
				[ 0,  1],	#右を見る
				[-1,  1],	#右上を見る
				[ 1,  1],	#右下を見る
				[-1, -1],	#左上を見る
				[ 1, -1]	#左下を見る
			]
			
		['up', 'down', 'left', 'right', 'right_up', 'right_down', 'left_up', 'left_down'].each_with_index{|item, i|
			eval <<-__EVAL_STRING__
			def #{item}(i, j)
				move = 0
				while true
					i += #{DIRECTION_TARGETS[i][0]}
					if i < 0 || i >= @board_size then break end
					j += #{DIRECTION_TARGETS[i][1]}
					if j < 0 || j >= @board_size then break end
					move += 1
					yield(get_nocheck(i, j), move)
				end
			end
			__EVAL_STRING__
		}
		
		
		def directional_iterator!(i, j, down, right)
			move = 0
			while true
				i += down
				if i < 0 || i >= @board_size then break end
				j += right
				if j < 0 || j >= @board_size then break end
				move += 1
				set_nocheck(i, j, yield(get_nocheck(i, j), move))
				#puts "#{i},#{j},#{self[i, j].to_s}"	#Debug
			end
		end
				
		def mount(i, j)
			#ここにルールを書くこと
			if !is_empty?(i, j) then return nil end	#空であること
	
			after = before = self
			DIRECTION_TARGETS.each{|target|
				temp = after.clone		#メメント
				temp.directional_iterator!(i, j, *target){|item, move|
					case item
					when EMPTY; break
					when @order
						if move > 1 then after = temp end
						break
					end
					item.reverse
				}
			}
			
			if after != before then
				after[i, j] = order
				after.order = self.order.reverse
				return after
			else
				return nil
			end
		end
		
		def candidates
			candidates = {}
			all_iterator{|i, j|
				after = mount(i, j)
				candidates[[i, j]] = after if after
			}
			return candidates
		end
		
		def inspect
			#super::inspect
			str = "×"
			for i in (0...@board_size)
				str += sprintf(",%2d", i)
			end
			str += "\n"
			for i in (0...@board_size)
				str += " #{i},"
				str += (0...@board_size).collect{|j| self[i, j].to_s}.join(',')
				str += "\n"
			end
			str += "NEXT: #{@order.to_s}"
			return str
		end
	end
	
	ORDER_SKIP = [-1, -1] #スキップする
	
	class StateTree
	
		NODES_LIMIT = 300
		DEPTH_LIMIT = 12
	
		@root		# State
		attr_reader :root
		@children	# StateTree
		attr_reader :children
	
		def make_children(depth_limit)
			unless @made_children then
				@made_children = true
				candidates = @root.candidates
				if candidates.empty? then
					# 自身が手詰まりの場合、まずパスする。
					# その後の手があるか調べてみる。
					unless @root.order_skip.candidates.empty? then
						@children[Othello::ORDER_SKIP] = StateTree::new(@root.order_skip)
					end
				else
					candidates.each{|op, child_state|
						@children[op] = StateTree::new(child_state)
					}
				end
			end
			if depth_limit > 1 then
				@children.each{|op, child_tree|
					child_tree.make_children(depth_limit - 1)
				}
			end
		end
		
		def initialize(state)
			@root = state
			@children = {}
			@made_children = false
		end
		
		def is_leaf?
			return @children.empty?
		end
		
		def nodes
			size = 1
			@children.values.each{|child| size += child.nodes}
			return size
		end
		
		def carry(depth_limit, nodes_limit)
			depth_limit ||= DEPTH_LIMIT
			nodes_limit ||= NODES_LIMIT
			for i in (1..depth_limit)
				make_children(i)
				current_nodes = nodes
				puts "Depth: #{i}, Nodes: #{current_nodes}"
				if current_nodes > nodes_limit then break end
			end
		end
		
		def transit(op, depth_limit, nodes_limit)
			if @children.keys.include?(op) then
				next_tree = @children[op]
				next_tree.carry(depth_limit, nodes_limit)
				return next_tree
			else
				p op
				raise '手を確認してください!'
			end
		end
	end
	
	@tree
	attr_reader :tree
	
	def state; return @tree.root; end
	def candidates
		result = {}
		@tree.children.each{|op, child_tree|
			if op == ORDER_SKIP then break end
			result[op] = child_tree.root
		}
		return result
	end
	
	def black_stones
		number = 0
		state.board.each{|item| if item == State::BLACK then number+=1 end}
		return number
	end
	
	def white_stones
		number = 0
		state.board.each{|item| if item == State::WHITE then number+=1 end}
		return number
	end
	
	def initialize(board_size, depth_limit = nil, nodes_limit = nil)
		@tree = StateTree::new(State::new(board_size))
		@tree.carry(depth_limit, nodes_limit)
	end
	
	def mount!(op, depth_limit = nil, nodes_limit = nil)
		@tree = @tree.transit(op, depth_limit, nodes_limit)
		return self
	end
	
	def order_skip!(depth_limit = nil, nodes_limit = nil)
		return mount!(ORDER_SKIP, depth_limit, nodes_limit)
	end
	
	def completed?; @tree.is_leaf?; end
	
	def inspect; state.inspect; end
end

#テストコード
if $0 == __FILE__ then
	othello = Othello::new(6, 1)
	p othello
	p othello.candidates
	p othello.state.board_load(othello.state.board_dump)
	#p othello.state.board_load(othello.state.board_dump)
	#p othello.tree
end