これが出来るからって優秀とは限らないんじゃね？

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

ホットエントリになっているを見て知ったのでやってみました。ブコメをさらっと読んでプログラミング。A*とかダイクストラ法とか全く知らない状態でスタート。使用した言語は Ruby。結局、1時間20分ぐらいかな。完全に書き殴りなのでひどいもんです。

直感的には、ちゃんと最短経路を求めると思うのだけど、数学的にこれが最短と証明できるかどうかよくわからないなあ。

思ったんだけど、これって A* とか知ってれば楽なのかな*1？もしそうならほぼ知識の問題だけど、たかが一つのアルゴリズムを知ってるだけで優秀と判別するのは相当リスキーなんじゃないかなあ。有名なアルゴリズムを知らないでアルゴリズムに強いってのは無いので、駄目な人をはじく問題としてはいいけど、優秀かどうかなんてこれで判るのかなあ。
あと当然だけど、こんなの一般的な IT 業界では全く使わない種類の知識だったりするし、もし必要な場合は適宜勉強して使い物になれば良いと思っているので、これが出来ないからといってプログラマとして駄目とは思わないなあ。

class Table
  def initialize
    @ary = []
  end

  def get_ary
    @ary
  end
  
  def []( x, y )
    @ary[y][x]
  end
end


class Point
  def initialize( c )
    if ( c == 42 )
      @state = :WALL
    elsif ( c == 32 )
      @state = :SPACE
    elsif ( c == 83 )
      @state = :START
    elsif ( c == 71 )
      @state = :GOAL
    else
      p c
      raise
    end
  end

  def state
    @state
  end
  
  def marking
    @mark = true
  end

  def marked?
    @mark
  end

  def marking2
    @mark2 = true
  end
  def marked2?
    @mark2
  end

  def num
    if ( @state == :WALL )
      9999999
    else
      @num
    end
  end

  def num=( x )
    @num = x
  end


  def rooting
    @root = true
  end

  def rooted?
    @root
  end
  
  def pos
    @pos
  end

  def pos=( x )
    @pos = x
  end
end


$table = Table.new
ary = $table.get_ary
tmp = []

x = 0
y = 0

start = nil
goal = nil

data = File.read( "data" )
data.each_byte{|c|
  if ( c == 10 )
    ary << tmp
    tmp = []
    y += 1
    x = -1
  else
    tmp << Point.new( c )
    tmp.last.pos = [x,y]
    if tmp.last.state == :START
      start = tmp.last
    elsif tmp.last.state == :GOAL
      goal = tmp.last
    end
  end
  x += 1
}

def f( cur, prev )
  if cur.state == :WALL
    return
  end

  if cur.marked?
    if cur.num <= prev.num + 1
      return
    end
  end
  cur.marking
  cur.num = prev.num + 1
  if ( cur.state != :GOAL )
    f( $table[ cur.pos[0] + 1, cur.pos[1] ]    , cur )
    f( $table[ cur.pos[0]    , cur.pos[1] + 1 ], cur )
    f( $table[ cur.pos[0] -1 , cur.pos[1] ]    , cur )
    f( $table[ cur.pos[0]    , cur.pos[1] - 1 ], cur )
  end
end

tmp = Object.new
def tmp.num
  -1
end
f( start, tmp )


# ary.each{|gyo|
#   gyo.each{|retu|
#     case retu.state
#     when :WALL
#       print "**"
#     when :SPACE
#       print retu.num.to_s.rjust( 2, "0" )
#     when :START
#       print "SS"
#     when :GOAL
#       print "GG"
#     else
#       raise
#     end
#   }
#   puts
# }



def ff( cur, prev )
  if cur.state == :WALL
    return
  end

  if ( cur.state != :START )
    next1 = $table[ cur.pos[0] + 1, cur.pos[1] ]
    next2 = $table[ cur.pos[0]    , cur.pos[1] + 1 ]
    next3 = $table[ cur.pos[0] -1 , cur.pos[1] ]
    next4 = $table[ cur.pos[0]    , cur.pos[1] - 1 ]

    nexts = [next1, next2, next3, next4]
    nexts = nexts.reject{|item| item == prev }
    nexts = nexts.reject{|item| item.marked2? }
    nexts.each{|one| one.marking2 }
    nex = nexts.min{|a,b| a.num - b.num }
    nex.rooting
    ff( nex, cur )
  end
end

ff( goal, tmp )

ary.each{|gyo|
  gyo.each{|retu|
    case retu.state
    when :WALL
      print "*"
    when :SPACE
      if ( retu.rooted? )
        print "$"
      else
        print " "
      end
    when :START
      print "S"
    when :GOAL
      print "G"
    else
      raise
    end
  }
  puts
}

*1:A* 知らなかったけど有名っぽい