Pythonの二重配列の思わぬ挙動につまづいたのでメモ

SwiftUIなど登場し、誰でも簡単にアプリが作れるようになってきている昨今。
時代にキャッチアップするのも重要だが、なかなか辛い。
年代を超えて大事なものは基礎だろうということで、LeetCodeでプログラミング練習。

簡単な魔法陣の問題をやってみる。
https://leetcode.com/explore/interview/card/top-interview-questions-hard/116/array-and-strings/828/

番兵法なるものでやってみようと思い、ipythonで下記のようにvisited_mapを用意する。すると....

In [1]: mat = [
   ...: [1,2,3],
   ...: [4,5,6]
   ...: ]

In [2]: h = len(mat)
    ...: w = len(mat[0])
    ...:

In [3]:  visited_map = [[False] * (w+2) ] * (h+2)

In [4]: visited_map
Out[4]:
[[False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False]]

In [5]: visited_map[1][1] = True

In [5]: visited_map
Out[5]:
[[False, True, False, False, False],
 [False, True, False, False, False],
 [False, True, False, False, False],
 [False, True, False, False, False]]

ﾌｧｯｯｯｯｯ！２列目が全部Trueになっとる。

にわかpython loverの私目はこの挙動がよくわかっていない。（あとで調べる。かも。）

とりあえず普通に初期化したらうまくいった。

In [6]:  visited_map = [[False for _ in range(w+2)] for _ in range(h+2)]

In [7]: visited_map
Out[7]:
[[False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False]]

In [8]: visited_map[1][1] = True

In [9]: visited_map
Out[9]:
[[False, False, False, False, False],
 [False, True, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False]]

ほんで作ったコードがこれ。これ直したら一発で動いてよかった。。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0:
            return []

        h = len(matrix)
        w = len(matrix[0])

        directions = [
            [0,1],
            [1,0],
            [0,-1],
            [-1,0]
        ]

        visited_map = [[False for _ in range(w+2)] for _ in range(h+2)]
        visited_map[0] = [True] * (w+2)
        visited_map[-1] = [True] * (w+2)
        for y in range(0, h+1):
            visited_map[y][0] = True
            visited_map[y][-1] = True

        res = []
        pwd = [0,0]
        dircnt = 0
        while True:       
            visited_map[pwd[0]+1][pwd[1]+1] = True
            res.append(matrix[pwd[0]][pwd[1]])

            direction = directions[dircnt % 4]
            next_point = [p+d for p, d in zip(pwd, direction)]

            if visited_map[next_point[0]+1][next_point[1]+1]:
                dircnt += 1
                direction = directions[dircnt % 4]
                next_point = [p+d for p, d in zip(pwd, direction)]

                if visited_map[next_point[0]+1][next_point[1]+1]:
                    break

            pwd = next_point  
        return res

というか、こんな長々とコード書いたが再帰を使えば一行でできるらしい。ほげっ
https://leetcode.com/explore/interview/card/top-interview-questions-hard/116/array-and-strings/828/discuss/20571/1-liner-in-Python-+-Ruby

勉強になる。
LeetCode、NDAとか守ってないらしくて批判されてるけど、個人的にはありがたいサイトである。プログラミングの筋トレが捗ります。ありがとうございマンモス。