From: Chris Cacciatore <truce.tringstein@...>
Date: 2009-06-30T04:57:40+09:00
Subject: Re: Plot the Shape (#211)

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)

-- 
Posted via http://www.ruby-forum.com/.