Guest User

Odds of navigating a random maze

a guest
Nov 25th, 2014
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.78 KB | None | 0 0
  1. import random
  2.  
  3. def testMaze(n):
  4.     # there is a doorway connecting cell a,b to cell a,b+1 iff
  5.     # columnConnections[a][b] = 1
  6.     columnConnections = [[0 for x in range(n-1)] for x in range(n)];
  7.     for a in range(0, n):
  8.         for b in range(0, n-1):
  9.             columnConnections[a][b] = random.choice([0,1])
  10.     # there is a doorway connecting cell a,b to cell a+1,b iff
  11.     # rowConnections[a][b] = 1
  12.     rowConnections = [[0 for x in range(n)] for x in range(n-1)];
  13.     for a in range(0, n-1):
  14.         for b in range(0, n):
  15.             rowConnections[a][b] = random.choice([0,1])
  16.    
  17.     #print columnConnections
  18.     #print rowConnections
  19.    
  20.     connectivityMatrix = [[0 for x in range(n)] for x in range(n)]
  21.     connectivityMatrix[random.choice(range(n))][random.choice(range(n))] = 1
  22.     #connectivityMatrix[0][0] = 1
  23.     for repeat in range(n*n):
  24.         for x in range(n):
  25.             for y in range(n):
  26.                 if connectivityMatrix[x][y] == 1:
  27.                     if y < n-1 and columnConnections[x][y] == 1:
  28.                         connectivityMatrix[x][y+1] = 1;
  29.                     if y > 0 and columnConnections[x][y-1] == 1:
  30.                         connectivityMatrix[x][y-1] = 1;
  31.                     if x < n-1 and rowConnections[x][y] == 1:
  32.                         connectivityMatrix[x+1][y] = 1;
  33.                     if x > 0 and rowConnections[x-1][y] == 1:
  34.                         connectivityMatrix[x-1][y] = 1;
  35.     #print connectivityMatrix
  36.    
  37.     total = -1;
  38.     for row in connectivityMatrix:
  39.         total = total + sum(row)
  40.    
  41.     #print total
  42.     #Test if this randomly generated maze is connected.
  43.     return total
  44.  
  45. total = 0
  46. n = 3
  47. rep = 500
  48. for x in range(rep):
  49.     total = total + testMaze(n)
  50.  
  51. print total / (rep + 0.0)
Advertisement
Add Comment
Please, Sign In to add comment