From: Chris Howe <chris@...>
Date: 2009-07-02T01:38:19+09:00
Subject: Re: [QUIZ] Plot the Shape (#211)

--0022152d6541cca4f7046da78ce0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Here is my solution. On average, for a 10x10 grid with a 10 sized shape, it
will plot the shape in about 31.7 guesses. If you change the neighbors
definition to exclude diagonals, it does it in around 24 guesses.  Worst
case scenario is of course the size of the grid.

I spent a fair amount of effort trying to collect statistical information
about the shapes I am generating, but experiments have shown that even
though there is a certain amount of non-uniformity in the distribution
across the board, it is not enough to gain a significant advantage in the
total number of guesses (probably less than a half a guess.)

--Chris

# The Shape class accomplishes a couple of things.
# First, it randomly generates shapes and provides some
# accounting, keeping track of how many lookups one does.

# Next, it acts as a kind of geometry manager for the board.
# (each, each_neighbors, get_neighbors. Changing the definition
# of each_neighbors can change the rules for what it means for
# squares to be adjacent.

# Finally, it keeps track of occupancy statistics for the board
# over successive regenerations of the shape.
class Shape
 attr_reader :h,:w,:l,:count
 def initialize(hh = 10, ww = 10, ll = 10)
  @h,@w,@l=hh,ww,ll #height,width, shape size
  @regens = @count = 0 #number of times shape generated, times dereferenced

  @stats = [] #used to count frequency of occupancy

  # seed the stats array with all 1s.
  h.times { |y| @stats[y] = [ 1 ] * w }
  @regens = h*w/(1.0 * l)
  rebuild
 end

 def each_neighbors(xxx,yyy=nil)
  if xxx.kind_of?( Array ) then
   x,y = xxx[0],xxx[1]
  else
   x,y = xxx,yyy
  end
  lowx,hix = [x-1,0].max, [x+1,w-1].min
  lowy,hiy = [y-1,0].max, [y+1,h-1].min
  (lowy..hiy).each do |yy|
   (lowx..hix).each do |xx|
    yield([xx,yy]) unless x==xx and y==yy
   end
  end
 end

 def get_neighbors(x,y=nil)
  result = []
  each_neighbors(x,y) do |coords|
   result.push(coords)
  end
  return result
 end

 def each
  h.times { |y| w.times { |x| yield [x,y] } }
 end

 def rebuild()
  @regens += 1 #increment the build count
  @count = 0 #clear the deref count

 #initialize board to contain only spaces
  @board=[]
  h.times { |y| @board[y] = [" "] * w  }

  neighbors = []
  shape = []

  l.times do
   if neighbors.length == 0 then
    # first piece - place it anywhere
    x,y = [w,h].map {|z| (rand*z).to_i}
   else
    # subsequent pieces - pick a random neighbor
    x,y = neighbors[ (rand * neighbors.length).to_i ]
   end
   @board[y][x] = "@" #mark occupancy
   @stats[y][x] += 1  #track occupancy

   shape |= [ [x,y] ] # add choice to list of shape coords

   # update neigbors
   neighbors -= [[x,y]]
   neighbors |= get_neighbors(x,y) - shape
  end
  return self
 end

 def to_s
  return @board.map { |x| x.join "" }.join("\n") + "\nTotal Lookups:
#{@count}\n"
 end

 def [](xx,yy=nil)
  if xx.kind_of?(Array) then
   x,y = xx[0],xx[1]
  else
   x,y = xx,yy
  end
  @count += 1
  return @board[y][x]
 end

 def stats
  norm_stats = []
  h.times do |y|
   norm_stats[y] = []
   w.times do |x|
    # correct stats for rotation and reflection symmetry
    norm_stats[y][x] = (@stats[y][x] + @stats[-y-1][x] + @stats[-y-1][-x-1]
+ @stats[y][-x-1] + @stats[x][y] + @stats[-x-1][y] + @stats[-x-1][-y-1] +
@stats[x][-y-1])/(8.0*@regens)
   end
  end
  return norm_stats
 end

 def statstring
  return stats.map { |y| y.map { |x| "%0.3f" % x}.join(" ") }.join("\n")
 end
end

class ShapePlot
 def initialize(r = Shape.new, c=0)
  @shape = r
  c.times {@shape.rebuild}
  @stats = @shape.stats
  @plays = 0
  @count = 0
  reset
 end

 def reset
  @guesses = []
  @members = []
  @neighbors = []
  @choices = []
  @shape.each { |coords| @choices << coords }
 end

 def to_s
  board = []
  @shape.each { |x,y| @shape.h.times { |y| board[y] = [ " " ] * @shape.w  }}
  @neighbors.each { |x,y| board[y][x] = "." }
  @guesses.each { |x,y| board[y][x] = "x" }
  @members.each { |x,y| board[y][x] = "@" }
  header = "+" + ("-"*(@shape.w*2-1)) + "+\n"
  return header + "|" + board.map{|x| x.join(" ")}.join("|\n|") + "|\n" +
header
 end

 def choose_random(p_list)
   sum = 0
   #choose from among the choices, probibilistiacally, weighted by
   #the occupation probabilities
   p_list.each { |p,c| sum += p }
   r = rand * sum
   p_list.each do |p,c|
     r -= p
     return c if r <= 0
   end

   # shouldnt ever be here, but return the last one anyway
   puts "BAAAAD"
   puts p_list
   puts @shape
   return p_list[-1][1]
 end

 def build_weighted(list)
  return list.map {|x| [ @stats[x[1]][x[0]], x ]}
 end

 def guess_none_known
  return choose_random( build_weighted( @choices ) )
 end

 def guess_some_known
  choices = @neighbors - @guesses
  return choose_random( build_weighted( choices ) )
 end

 def found_a_hit(coords)
  # update the members of the shape
  @members += [ coords ]
  x,y=coords
  # calculate the neigbors of the new piece
  @neighbors += @shape.get_neighbors(x,y)
  # the intersection of @members and @neighbors should be empty, but
  # we are subtracting out @guesses, which includes all @members when
  # we go to pick a choice list anyway...
 end

 def guess
  #choose a square to look at
  # if we know some part of the shape is known, restrict guesses
  # to neighbors of the stuff we know
  #if we dont know any of them yet, choose from the whole board
  x,y = coords = (@members.length > 0 ? guess_some_known : guess_none_known)
  @guesses += [coords]
  @choices -= [coords]
  if @shape[x,y]=="@" then
   found_a_hit(coords)
  end
 end

 def play( draw = false)
  reset

  # upldate statistics before we update the shape
  @stats = @shape.stats
  @shape.rebuild
  while @members.length < @shape.l
   guess
   puts self if draw
  end

  @plays +=1
  @count += @shape.count
  return @shape.count
 end

 def report
  mean = @count / (1.0 * @plays)
  puts "After #{@plays} plays, the mean score is: #{mean}"
 end
end

q = ShapePlot.new
q.play(true)
999.times { q.play }
q.report

--0022152d6541cca4f7046da78ce0--