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