From: Sander Land <sander.land@...>
Date: 2009-02-03T04:06:27+09:00
Subject: Re: [QUIZ] Hexagonal Grid Game Board (#190)

Here is my solution.
Pastie: http://pastie.org/377536
The pastie still has the comment on the distances function as
returning the distance between two hexes, but I changed this to return
an array of all distances from some position, since the breadth-first
search was already calculating this anyway.


class Hex
 attr_accessor :neighbours,:distance
 def initialize(row,col,rows,cols)
  @neighbours =
[[-1,-1],[-1,0],[0,-1],[0,1],[1,0],[1,1]].map{|r,c|[row+r,col+c]}.select{|r,c|
r>=0 && c>=0 && r<rows && c<cols}
  @obstructed = col==3 && row!=rows-1  ||  col==6 && row!=0 # double barrier
 end
 def obstructed?; @obstructed ;end
end

class HexBoard < Array
 def initialize(rows=9, cols=9)
   super(rows) {|row| Array.new(cols) {|col| Hex.new(row,col, rows,cols) }}
 end
 # Distance from position to each hex
 def distances(position,&block)
   each{|row| row.each{|hex| hex.distance = nil } }
   bfs_distance([position],0, &block);
   map{|row| row.map &:distance }
 end
 # Breadth-first search distance
 def bfs_distance(hexes,dist, &block)
   q = []
   hexes.map{|r,c| self[r][c] }.each{|hex|
     next if hex.distance || block_given? && yield(hex)
     hex.distance = dist
     q += hex.neighbours
   }
   bfs_distance(q.uniq,dist+1, &block) unless hexes.empty?
 end
 # Draw solution
 def draw(from=[4,4],&block)
   distances(from,&block).each_with_index{|dists,row| puts "#{row}:#{'
'*(size - row)}#{dists.map{|x|x||'#'}.join ' '}\n" }
 end
end

board = HexBoard.new
board.draw
board.draw([0,0],&:obstructed?)