オフラインリアルタイムどう書く E20 の実装例

問題：http://nabetani.sakura.ne.jp/hena/orde20maze/
実装リンク集：https://qiita.com/Nabetani/items/7baf181b4a1b7eacc79a

もともと ruby で書いていたんだけど、なんとなく python に移植した。

python2or3

MAZE = """
01 2345 6 789A CD E FG JKLM
PQR ST UVW X YZ 06CIO 17 JPV
EK 39F RX GMSY 5B HNT """

def neibours(s):
  n=[ [MAZE[x-1],MAZE[x+1] ] for x in range(len(MAZE)) if MAZE[x]==s ]
  return [ x for x in sum(n,[]) if not x.isspace() ]

def solve(src):
  visited={}
  q=[ (src[0], 0) ]
  while True:
    cur, dist = q.pop(0)
    if cur in visited:
      continue
    visited[cur]=True
    for n in neibours(cur):
      if n==src[1]:
        return str(dist+1)
      if not( n in visited ):
        q.append( ( n, dist+1 ) )

def test( src, expected ):
  actual = solve( src )
  okay  =actual == expected
  print( repr( [ ( "ok" if okay else "**NG**"), src, actual, expected ] ) )

test( "DE", "13" );
test( "EK", "1" );

いつも通りテストケースの大半は省略。

画像で配布されている迷路をどうコード上に表現するかという問題。
私は、隣接セルが隣の文字になるような文字列を用意することにした。
上記の「MAZE」という文字列。

本来なら一旦 dict に入れたりして検索を早くするべきだけど、面倒なので毎回線形探索している。その分遅いけど、まあ今回の問題なら良いと思う。

あとは普通に幅優先探索で。
まあこの問題の場合は深さ優先でもうまくいくはずだけどね。