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