DataFrameラビリンスゲームソリューション？

Question

だから私は基本的に0が開いた四角を表すと1が壁を表す0と1とのデータフレームを作成して、迷路ゲームを作成することによって、私のpandsのスキルをテストしたかった：

df = pd.DataFrame(np.random.randint(0, 2, (10,11))) 

     0 1 2 3 4 5 6 7 8 9 10 
    0 0 1 0 0 0 1 0 0 0 1 0 
    1 1 1 1 1 0 1 1 0 0 1 1 
    2 1 0 1 1 0 0 0 0 1 0 1 
    3 0 0 1 0 0 0 0 1 1 0 0 
    4 1 1 1 0 1 0 1 0 0 1 0 
    5 0 1 0 0 1 1 1 1 1 0 1 
    6 1 0 1 1 0 1 0 0 1 0 1 
    7 1 1 1 1 1 0 1 1 1 1 0 
    8 1 1 1 0 0 0 1 0 1 1 0 
    9 0 0 1 1 1 0 1 1 0 0 0 

考えはしました0から10までの列0から列10への移動が可能かどうかを確認してください。 （2は、それが解決することができる最後の列にありますならば）私のソリューションでした：

def expand(col): 
    if col[0]==0: last0= 0 
    else: last0= 'x' 
    for ind in range(1, len(col)): 
     if col[ind]==0 and (last0=='x'): last0 = ind 
     if col[ind]==1: last0 = 'x' 
     if col[ind]==2 and last0!='x': 
      for val in range(last0, ind): 
       col[val]=2 
     if col[ind-1]==2 and col[ind]==0: col[ind]=2 
    return col 


def sol(df): 
    df[0] = df.apply(lambda x: 2 if x[0]==0 else x[0], axis=1) 
    for col in range(1, len(df.T)): 
     df[col] = df.apply(lambda x: 2 if x[col-1]==2 and x[col]==0 else x[col], axis=1) 
     df[col] = expand(df[col]) 
sol(df) 

正直なところ、私はそれが完全なソリューションではありません実現するまで、それは効率だのかなり自慢していました。それは右に2秒しか満たされないので、迷路が右に、次に上に、左に、右に進む必要があったならば。このコードでは解決できません。明らかに、コードを何度も繰り返すだけで、コードは左右に移動するので、巨大な迷路では遅くなります。

これを解決するうえで、効率的な方法は何と思いますか？

Answer 1

私は再帰的にそれを行うだろう：

• where_nextは、アレイと場所を取ります。最後の列にある場合は、Trueを返します。それ以外の場合は、現在の場所を1に設定し、隣接するすべての場所が0であり、その場所で再帰します。
• 最初の列のすべての0の場所で実行して初期化します。

---

def where_next(a, i, j): 
    a = a.copy() 
    n, m = a.shape 
    if j == 10: 
     return True 
    else: 
     results = [] 
     a[i, j] = 1 
     moves = [(i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j)] 
     for i_, j_ in moves: 
      if (0 <= i_ < n) and (0 <= j < m): 
       if a[i_, j_] == 0: 
        results.append(where_next(a, i_, j_)) 
     return any(results) 

df = pd.DataFrame(np.random.randint(0, 2, (10, 11))) 
a = df.values 
any([where_next(a, i, 0) for i in np.where(a[:, 0] == 0)[0]]) 

True 

---

print(df) 

    0 1 2 3 4 5 6 7 8 9 10 
0 1 1 1 1 0 0 0 0 1 1 1 
1 0 1 0 1 1 1 1 0 0 0 1 
2 0 0 0 0 1 0 0 0 0 0 0 
3 0 1 0 0 0 1 1 1 0 1 1 
4 0 0 1 0 1 0 0 0 0 0 1 
5 1 0 1 0 0 1 1 0 0 0 1 
6 0 0 0 1 1 1 1 0 0 1 0 
7 0 0 0 0 0 0 0 0 1 0 0 
8 0 1 1 1 1 1 0 0 1 0 1 
9 0 0 0 0 0 0 1 1 1 1 0