Plot the Shape (#211)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this
    quiz until 48 hours have elapsed from the time this message was
    sent.

  2. Support Ruby Q. by submitting ideas and responses
    as often as you can!
    Visit: http://rubyquiz.strd6.com/suggestions

  3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion. Please reply to
the original quiz message, if you can.

RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Plot the Shape (#211)

Kvetha Rubyists,

This week’s quiz was submitted by Alan at
http://rubyquiz.strd6.com/suggestions

Somewhere on a 10x20 grid is a 10 block shape. The shape parts are all
adjacent, either horizontally, vertically or diagonally.

Write a simple algorithm that will list the co-ordinates of the 10
parts of the shape. Try to minimize lookups to the grid.

Here is an example shape to get started (you may need to copy into a
monospaced font):

0123456789ABCDEFGHIJ
0…
1…
2…@@…
3…@…
4…@@@@@…
5…@…
6…@…
7…
8…
9…

Have Fun!


-Daniel
http://rubyquiz.strd6.com

P.S. Submitting quiz ideas is fun and easy. Visit
http://rubyquiz.strd6.com/suggestions to find out more!

Hello,
Here’s my solution, it works also with grid with different sizes but it
does
not
check the adjacency of the shape parts.

http://github.com/sandropaganotti/Ruby-Quiz-Repository/blob/222c931fcca22e1b89ae764efaa463b376b90eb9/211_plot_the_shape.rb

Sandro

Plot the Shape (#211)

Somewhere on a 10x20 grid is a 10 block shape. The shape parts are all
adjacent, either horizontally, vertically or diagonally.

Write a simple algorithm that will list the co-ordinates of the 10
parts of the shape. Try to minimize lookups to the grid.

Six little methods. The first two started with some simplifying
assumptions:

  • The grid is stored in a “convenient” data-structure
  • The grid only contains one shape
  • The shape doesn’t violate any of the rules
    The third dispenses with the convenient structure and simply
    brute-force scans the whole grid. The last three build on each other
    until the sixth iteration attempts to follow the part adjacency rules
    and minimize lookups (and is super-super-ugly-code :-).

#!/usr/bin/env ruby

$input = <<-EO


…@@…
…@…
…@@@@@…
…@…
…@…



EO

def foo1

assuming the grid is stored hash-like, keyed on coordinate

grid = {}
$input.split.each_with_index{|line, y|
line.split(//).each_with_index{|char, x|
grid[[x,y]] = char
}
}

reject by value and return the keys

grid.reject{|k,v| v != “@”}.keys
end

def foo2

assuming the grid is stored hash-like, keyed on value

grid = {}
$input.split.each_with_index{|line, y|
line.split(//).each_with_index{|char, x|
(grid[char] ||= []) << [x,y]
}
}

return the value

grid[’@’]
end

def foo3

grid is stored nested-array-liked, indexed by row then column

grid = $input.split

rows, cols, parts = grid.size, grid[0].size, []

:frowning: my ‘clever’ duck is defeated by 1.8’s String#[]

rows.times{|r| cols.times{|c| parts << [c,r] if grid[r][c] == 64 }}
parts
end

def foo4

grid is stored nested-array-liked, indexed by row then column

grid = $input.split

rows, cols, parts, checked = grid.size, grid[0].size, [], {}

until (parts.size == 10)
# pick a random spot
r, c = rand(rows), rand(cols)
next if checked[[r,c]] # skip if we’ve already checked this
one
checked[[r,c]] = true
next unless grid[r][c] == 64 # skip if this one isn’t a part
parts << [c,r] # store if it is a part
end

parts
end

def foo5

grid is stored nested-array-liked, indexed by row then column

grid = $input.split

rows, cols, parts, checked = grid.size, grid[0].size, [], {}

until (parts.size == 10)
# pick a random spot
r, c = rand(rows), rand(cols)
next if checked[[r,c]] # skip if we’ve already checked this
one
checked[[r,c]] = true
next unless grid[r][c] == 64 # skip if this one isn’t a part
parts << [c,r] # store if it is a part

# check the current parts neighbors
(-1..1).each do |dc|
  (-1..1).each do |dr|
    cprime = (c + dc).abs
    rprime = (r + dr).abs
    next if checked[[rprime,cprime]]       # skip if we've already

checked this one
checked[[rprime,cprime]] = true
next unless grid[rprime][cprime] == 64 # skip if this one isn’t
a part
parts << [cprime,rprime] # store if it is a part
end
end
end

parts
end

def foo6

grid is stored nested-array-liked, indexed by row then column

grid = $input.split

rows, cols, parts, checked = grid.size, grid[0].size, [], {}

l = lambda {|r, c, parts, checked|
# check the current parts neighbors
(-1…1).each do |dc|
(-1…1).each do |dr|
cprime = (c + dc).abs
rprime = (r + dr).abs
next if checked[[rprime,cprime]] # skip if we’ve already
checked this one
checked[[rprime,cprime]] = true
next unless grid[rprime][cprime] == 64 # skip if this one isn’t
a part
parts << [cprime,rprime] # store if it is a part
l.call(rprime, cprime, parts, checked) # recurse to check more
neighbors
end
end
}

loop do
# pick a random starting spot
r, c = rand(rows), rand(cols)
next if checked[[r,c]] # skip if we’ve already checked this
one
checked[[r,c]] = true
next unless grid[r][c] == 64 # skip if this one isn’t a part
parts << [c,r] # store if it is a part
l.call(r, c, parts, checked)
break
end

parts
end

p foo1.sort
p foo2.sort
p foo3.sort
p foo4.sort
p foo5.sort
p foo6.sort

#(ruby 1.8.6)=>
[[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4],
[12, 6], [13, 5]]
[[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4],
[12, 6], [13, 5]]
[[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4],
[12, 6], [13, 5]]
[[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4],
[12, 6], [13, 5]]
[[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4],
[12, 6], [13, 5]]
[[8, 3], [8, 4], [9, 2], [9, 4], [10, 2], [10, 4], [11, 4], [12, 4],
[12, 6], [13, 5]]

My solution is in two parts:
-divide and conquerer until a ‘@’ is found
-use a recursive backtracker starting from the seed coord. found in
step 1.

I am not positive about my worst-case analysis on lookups.

-C

$map = File.new(ARGV[0]).inject([]){|a,line| a << line.split("")}
#vertical line
m = lambda {|x| (1…10).detect{|y| $map[y][x] == ‘@’}}
#horizontal line
n = lambda {|y| (1…20).detect{|x| $map[y][x] == ‘@’}}
#find a coordinate with an ‘@’; worst case 118 lookups
seed =
[[n.call(5),5],[n.call(6),6],[10,m.call(10)],[6,m.call(6)],[3,m.call(3)],[8,m.call(8)],
[16,m.call(16)],[13,m.call(13)],[18,m.call(18)]].detect{|a| a[1]
!= nil and a[0] != nil}
#recursive maze solver; worst case 80 lookups
$visits = {}
def m_solver(a,found)
x,y = a[0],a[1]
return if found >= 10
if $visits["#{y},#{x}"] == nil
puts “#{x-1 > 9 ? (x-1+55).chr : (x-1)},#{y-1}”
found += 1;$visits["#{y},#{x}"] = true
end
#vertical or horizontal
m_solver([x,y-1],found) if y-1 >= 1 and $map[y-1][x] == ‘@’ and
$visits["#{y-1},#{x}"] == nil
m_solver([x,y+1],found) if y+1 <= 10 and $map[y+1][x] == ‘@’ and
$visits["#{y+1},#{x}"] == nil
m_solver([x-1,y],found) if x-1 >= 1 and $map[y][x-1] == ‘@’ and
$visits["#{y},#{x-1}"] == nil
m_solver([x+1,y],found) if x+1 <= 20 and $map[y][x+1] == ‘@’ and
$visits["#{y},#{x+1}"] == nil
#diagonal
m_solver([x-1,y-1],found) if y-1 >= 1 and x-1 >= 1 and
$map[y-1][x-1] == ‘@’ and $visits["#{y-1},#{x-1}"] == nil
m_solver([x-1,y+1],found) if y+1 <= 10 and x-1 >= 1 and
$map[y+1][x-1] == ‘@’ and $visits["#{y+1},#{x-1}"] == nil
m_solver([x+1,y-1],found) if x+1 <= 20 and y-1 >= 1 and
$map[y-1][x+1] == ‘@’ and $visits["#{y-1},#{x+1}"] == nil
m_solver([x+1,y+1],found) if x+1 <= 20 and y+1 <= 10 and
$map[y+1][x+1] == ‘@’ and $visits["#{y+1},#{x+1}"] == nil
end
#worst case 198 lookups
m_solver(seed,0)

Here’s the first solution that came to my mind. Nothing tricky or
efficient really. Just gets the job done. It uses recursion to search
adjacent squares so as to meet the requirement/suggestion to avoid
merely doing a linear search of the whole game board (at least, that’s
what I read into it).

This supports boards of arbitrary size and can be configured via
constants to support a different maximum number of characters to
search for (and specific character to search for).

It assumes the board, if provided, is rectangular.

http://snipt.org/kmnm

(Just noticed I left in a hard-coded regex using the ‘@’ character;
otherwise this supports searching for a different character)

There were many good solutions to this week’s quiz, but Chris Howe’s
solution stands out as the best.

Chris’s solution consists of two parts: a Shape class that handles
creating the shape and tracking lookups to the grid and a ShapePlot
class that handles the guesses.

Chris also provides a mode that draws the board as it is searched. The
‘@’ characters represent the parts of the shape that have been
discovered so far, the ‘x’ characters represent misses, and the ‘.’
characters represent neighbors to the discovered shapes: the places
that the program will search next.

    +-------------------+
    |            x      |
    |                   |
    |                   |
    |                   |
    |    . x x .        |
    |x x x @ @ .        |
    |x @ @ @ x .        |
    |x x @ x x          |
    |  . x .       x    |
    |    x              |
    +-------------------+

As you can see the two 'x’s off to the side are random choices that
missed. The program continues to guess randomly a location with part
of the shape is found. A piece of the shape was then discovered near
the bottom left and the program began searching the neighbors of the
already discovered pieces to find the rest of it.

The default output of the program is to display one game in drawing
mode, and then run 999 more games to generate the statistics for the
average number of lookups. After 1000 plays the average number of
lookups is around 31.7.

Thank you Brabuhr, Chris Cacciatore, Chris Howe, Kendal Gifford, and
Sandro P. for your solutions this week!

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
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.w2-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