3hours.rb

# 2015-05-31
# 制限時間３時間で迷路を解く問題
# http://okajima.air-nifty.com/b/2010/01/post-abc6.html

class Path
  attr_accessor :value, :prev, :f, :g, :h
  def initialize(value: nil, g: 0, h: 0, prev: nil)
    @value = value
    @g = g
    @h = h
    @f = g + h
    @prev = prev
  end

  def ==(path)
    @value == path.value
  end

  def inspect
    [@value, @g, @h, @f]
  end
end

def better_path? (path1,path2)
  path1.f < path2.f
end

def astar(open_list,close_list,goal_p,successor,cost_fn)
  if (open_list.empty?)
    nil
  else
    path = open_list.sort_by!(&:f).shift
    close_list.push(path)
    if (goal_p.(path.value))
      path
    else
      close_list.push(path)
      successor.(path.value).each{ |val|
        path2 = Path.new(value: val, g: path.g+1, h: cost_fn.(val),
                         prev: path)
        old = nil
        if (old = open_list.find{|old| old == path2})
          if (better_path?(path2,old))
            open_list.delete(old)
            open_list.push(path2)
          end
        elsif (old = close_list.find{|old| old == path2})
          if (better_path?(path2,old))
            close_list.delete(old)
            open_list.push(path2)
          end
        else
          open_list.push(path2)
        end
      }
      astar(open_list,close_list,goal_p,successor,cost_fn)
    end
  end
end







WALL = "*"

def string_to_map(str)
  map = []  
  str.chomp.split("\n").each{|line|
    map.push(line.chomp.split(''))
  }
  map
end

def map_to_string(ary)
  ary.map{|v|v.reduce(&:+)+"\n"}.reduce(&:+)
end

def wall?(map,(x,y))
  map[y][x] == WALL
end

def neighbours(map,pos)
  x,y = pos
  [[x,y-1],[x,y+1],[x-1,y],[x+1,y]].delete_if(&(method(:wall?).curry.(map)))
end

def finder_gen(val)
  -> (map) {
  for y in 0...map.length
    for x in 0...map[0].length
      if (map[y][x] == val)
        return [x,y]
      end
    end
  end
  nil
  }
end

def find_start(map)
  finder_gen("S").(map)
end

def find_goal(map)
  finder_gen("G").(map)
end

def manhattan_distance ((x1,y1),(x2,y2))
  (x1-x2).abs + (y1-y2).abs
end

def show_map(map)
  map.each{|line|
    line.each{|c|
      print c
    }
    print "\n"
  }
end

def solver(map_string)
  map = string_to_map(map_string)
  show_map(map)
  start = find_start(map)
  goal = find_goal(map)
  print [:start, start, :goal, goal], "\n"
  goal_p = ->(pos) { goal == pos}
  successor = method(:neighbours).curry.(map)
  cost_fn = method(:manhattan_distance).curry.(goal)
  start_path = Path.new(value: start, g: 0, h: cost_fn.(start), prev: nil)
  path = astar([start_path],[],goal_p,successor,cost_fn)
  if (path) 
      path_list = path_to_list(path)
      result = string_to_map(map_string)
      path_list.each{|(x,y)|
        result[y][x] = "$"
      }
      show_map(result)
      map_to_string(result)
  else
    nil
  end
end

def path_to_list(path)
  result = []
  rec = ->(path){
    result.push(path.value)
    if (path.prev)
      rec.(path.prev)
    end
  }
  rec.(path)
  result
end

def test () 
  maze = File.read("maze.txt")
  result = solver(maze)
  File.write("result.txt",result)
  nil
end

test()

string_to_arrayがないよ

本当だ。ありがとう。直した。