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

問題 : http://nabetani.sakura.ne.jp/hena/ordf07walk/
実装リンク集 : https://qiita.com/Nabetani/items/cf93b63acc8a313c88bb

当日は ruby の実装をお見せしたんだけど、なんとなくここでは python。

python2 でも python3 でも動くと思う。
慣れない class を使ってみた。

python

class Walker:
  def __init__( self, src ):
    self._map = [[int(x) for x in list(line)] for line in src.split("/")]
    self._visited=[[False for x in range(5)] for y in range(5) ]

  def visited(self,x,y):
    return self._visited[y][x]

  def map(self,x,y):
    return self._map[y][x]

  def visit(self, x, y):
    self._visited[y][x]=True

  def walk(self, x, y):
    self.visit(x,y)
    nb0 = [[x+n[0], y+n[1]] for n in [[0,-1],[0,1],[-1,0],[1,0]]]
    nb1 = [n for n in nb0 if n[0] in range(5) and n[1] in range(5) and not self.visited(n[0], n[1]) ]
    cur = self.map(x,y)
    nb = [n for n in nb1 if abs(cur - self.map(n[0],n[1]))<2 ]
    for n in nb:
      self.walk( n[0], n[1] )

def solve( src ):
  w=Walker(src)
  w.walk(2,0)
  return "/".join([
    "".join(["*" if w.visited(x,y) else str(w.map(x,y)) for x in range(5) ])
    for y in range(5)
  ])

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

test( "12345/29496/19485/09594/82457", "*****/*9*9*/*9*8*/*9*9*/82**7" );
test( "12345/11011/65432/71999/65432", "*****/*****/*****/*1999/*****" );
test( "11111/11111/11111/11111/11111", "*****/*****/*****/*****/*****" );

いつも通りテストデータの大半は省略。
順当な深さ優先探索。

リスト内包表記をたくさん使ってみた。
Walker の walk で、nb0, nb1, nb の辺りが美しくない。たくさん条件のある if をを書くよりこの方がいいかと思ったけど、微妙。