SHARE
TWEET

Untitled

a guest Sep 17th, 2019 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
  3.  
  4. Example 1:
  5.  
  6. 11110
  7. 11010
  8. 11000
  9. 00000
  10.  
  11. Output: 1
  12.  
  13. Example 2:
  14.  
  15. 11000
  16. 11000
  17. 00100
  18. 00011
  19.  
  20. Output: 3
  21.  
  22. Observations:
  23.  
  24. - Diagonals are not considered connected islands for this version of the question
  25. - If grid is all zeros, than islands equals 0
  26. - If grid is all ones, than islands equals 1
  27.  
  28. - The structure of a 2d grid of 1s and 0s is similar to that of a graph data structure, where nodes of an island are connected to 1 or more other nodes of the same island
  29. - For graphs, we can use Breath-First-Search algorithm to locate all the nodes in an island
  30. - We need an way to keep track of already visited nodes
  31. - Initially looks like 0(n) looks like best case scenerio since at least every node in the 2d matrix has to be visited once
  32. '''
  33. import random
  34.  
  35.  
  36. # input_matrix = [[0,0,1,1,0],
  37. #                 [1,0,0,0,1],
  38. #                 [1,1,1,1,1],
  39. #                 [0,0,0,0,0]] # 1
  40.  
  41. def generate_matrix(size=5):
  42.     # make sure there's a higher porpotion of ones to test call stack limitations
  43.     return [[random.choice([1,0,1,0,1]) for x in range(size)] for y in range(size)]
  44.  
  45.  
  46. def pretty_print(matrix):
  47.     print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in matrix]))
  48.  
  49.  
  50. # Attempt #1
  51. def locate_islands(input_matrix):
  52.     row, col, islands = 0, 0, 0
  53.     # pretty_print(input_matrix)
  54.    
  55.     for ir, row in enumerate(input_matrix):
  56.         for ic, node in enumerate(row):
  57.             if (node is 1):
  58.                 islands = islands + 1
  59.                 # print("starting node for BFS: {},{} is {}".format(ir, ic, node))
  60.                 bfs(ir, ic)
  61.                
  62.     print("output: ", islands)
  63.            
  64.    
  65.  
  66. def bfs(ir, ic):
  67.     # search to right, bottom, top, left of node
  68.     if (input_matrix[ir][ic] is not 1):
  69.         return 0
  70.  
  71.     input_matrix[ir][ic] = 2 # mark already visited with 2
  72.    
  73.     # print("Searching...", ic, ir)
  74.     if (ir+1 < len(input_matrix)) and (input_matrix[ir+1][ic] is 1):
  75.         bfs(ir+1, ic)
  76.  
  77.     if (ic+1 < len(input_matrix[ir])) and (input_matrix[ir][ic+1] is 1):
  78.         bfs(ir, ic+1)
  79.        
  80.     if (ic-1 > 0) and (input_matrix[ir][ic-1] is 1):
  81.         bfs(ir, ic-1)
  82.        
  83.     if (ir-1 > 0) and (input_matrix[ir-1][ic] is 1):
  84.         bfs(ir-1, ic)
  85.    
  86.     return 0
  87.    
  88. input_matrix = generate_matrix(size=5)
  89. locate_islands(input_matrix)
  90.  
  91. # increase the size of grid
  92. input_matrix = generate_matrix(size=2000)
  93. # RecursionError: maximum recursion depth exceeded while calling a Python object
  94. print(len(input_matrix)) # stackoverflow error!
  95. locate_islands(input_matrix)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top