# Plot the Shape (#211)

**URL:** <https://www.ruby-forum.com/t/plot-the-shape-211/171137>\
**Category:** Ruby\
**Created:** [June 26, 2009, 9:31pm UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137 "2009-06-26T21:31:34Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [June 26, 2009, 9:31pm UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/1 "2009-06-26T21:31:34Z")

</div>

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

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](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](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](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](http://rubyquiz.strd6.com)

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

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [June 29, 2009, 1:43am UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/2 "2009-06-29T01:43:13Z")

</div>

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](http://github.com/sandropaganotti/Ruby-Quiz-Repository/blob/222c931fcca22e1b89ae764efaa463b376b90eb9/211_plot_the_shape.rb)

Sandro

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [June 29, 2009, 3:45am UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/3 "2009-06-29T03:45:27Z")

</div>

> ## 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, []

# ☹ 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]]

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [June 29, 2009, 9:57pm UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/4 "2009-06-29T21:57:33Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [June 29, 2009, 5:21pm UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/5 "2009-06-29T17:21:55Z")

</div>

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.

> **[Snipt - Søk Forbrukslån & Smålån Uten Sikkerhet (2021)](https://snipt.org)**
>
> Snipt.org gir deg best informasjon om lån uten sikkerhet. Her finner du også info om banker som tilbyr forbrukslån som ikke har sikkerhet.

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

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [July 6, 2009, 12:37am UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/6 "2009-07-06T00:37:34Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [July 1, 2009, 6:38pm UTC](https://www.ruby-forum.com/t/plot-the-shape-211/171137/7 "2009-07-01T18:38:56Z")

</div>

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