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