Advertisement
makispaiktis

BinarySearchIO - Flip rows, columns with deepcopy

Jan 9th, 2021 (edited)
432
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.28 KB | None | 0 0
  1. '''
  2. You are given a two-dimensional integer matrix containing 1s and 0s.
  3. Return the maximum number of 1s you can get if you must flip a row and then flip a column.
  4. Constraints
  5. 1 ≤ n, m ≤ 250 where n and m are number of rows and columns in matrix.
  6. Example 1
  7. Input
  8. matrix = [
  9.    [1, 0, 1],
  10.    [0, 1, 0],
  11.    [1, 0, 0]
  12. ]
  13. Output
  14. 8
  15.  
  16. Explanation
  17. We can flip row 2 (i=1) to get:
  18. [[1, 0, 1],
  19. [1, 0, 1],
  20. [1, 0, 0]]
  21. And then flip column 2 (j=1) to get:
  22.  
  23. [[1, 1, 1],
  24. [1, 1, 1],
  25. [1, 1, 0]]
  26. '''
  27. from random import randrange
  28. from copy import deepcopy
  29.  
  30. # Function 1 - Flip elements
  31. def flip(element):
  32.     if element == 0:
  33.         element = 1
  34.     elif element == 1:
  35.         element = 0
  36.     return element
  37.  
  38.  
  39. # Function 2 - Flip row's elements
  40. def flipRow(MATRIX, rowIndex):
  41.     matrix = deepcopy(MATRIX)
  42.     N = len(matrix)
  43.     M = len(matrix[0])
  44.     if rowIndex < 0 and rowIndex >= N:
  45.         return matrix
  46.     for i in range(N):
  47.         if i == rowIndex:
  48.             for j in range(M):
  49.                 matrix[i][j] = flip(matrix[i][j])
  50.     return matrix
  51.  
  52.  
  53. # Function 3 - Flip column's elements
  54. def flipColumn(MATRIX, columnIndex):
  55.     matrix = deepcopy(MATRIX)
  56.     N = len(matrix)
  57.     M = len(matrix[0])
  58.     if columnIndex < 0 and columnIndex >= M:
  59.         return matrix
  60.     for j in range(M):
  61.         if j == columnIndex:
  62.             for i in range(N):
  63.                 matrix[i][j] = flip(matrix[i][j])
  64.     return matrix
  65.  
  66. # Function 4 - Flip both a row's and a column's elements
  67. def flipRowColumn(arxikos, rowIndex, columnIndex):
  68.     MATRIX = deepcopy(arxikos)
  69.     m1 = flipRow(MATRIX, rowIndex)
  70.     m2 = flipColumn(m1, columnIndex)
  71.     return m2
  72.  
  73.  
  74.  
  75. # Function 5 - Sum of the elements of a 2D-matrix
  76. def sumMatrix(matrix):
  77.     N = len(matrix)
  78.     M = len(matrix[0])
  79.     SUM = 0
  80.     for i in range(N):
  81.         for j in range(M):
  82.             SUM += matrix[i][j]
  83.     return SUM
  84.  
  85.  
  86.  
  87. # Function 6 - Solve the problem
  88. def solve(arxikos):
  89.     N = len(arxikos)
  90.     M = len(arxikos[0])
  91.     m2Solution = list()
  92.     nSolution = 0
  93.     mSolution = 0
  94.     MAXSUM = 0
  95.     # Here, I will scan all the possible ways and create all the NxM combinations of matrices
  96.     # The matrix with the max sum of elements (the most possible '1's) will be returned as with its sum
  97.     for nChange in range(N):
  98.         MATRIX = deepcopy(arxikos)
  99.         for mChange in range(M):
  100.             # print(nChange, mChange)
  101.             # print(MATRIX)
  102.             m2 = flipRowColumn(MATRIX, nChange, mChange)
  103.             # print(MATRIX, "    ", m2)
  104.             # print()
  105.             # This is the changed matrix and I have to 'scan' it to find its sum
  106.             SUM = sumMatrix(m2)
  107.             if SUM > MAXSUM:
  108.                 MAXSUM = SUM
  109.                 nSolution = nChange
  110.                 mSolution = mChange
  111.                 m2Solution = m2.copy()
  112.     return m2Solution, MAXSUM, nSolution, mSolution
  113.  
  114.  
  115. # Function 7 - Display a 2D-matrix
  116. def display(matrix):
  117.     N = len(matrix)
  118.     for i in range(N):
  119.         print(matrix[i])
  120.  
  121.  
  122. # Function 8 - PrettySolve
  123. def prettySolve(arxikos):
  124.     print("***********************************")
  125.     print("Initial matrix: ")
  126.     display(arxikos)
  127.     m2Solution, MAXSUM, nSolution, mSolution = solve(arxikos)
  128.     print()
  129.     print("The max sum is", MAXSUM, "and can be achieved if I flip row with index", nSolution, "and column with index", mSolution)
  130.     print("Final matrix after these 2 changes: ")
  131.     display(m2Solution)
  132.     print("***********************************")
  133.  
  134.  
  135. # Function 9 - Generate a random matrix NxM with '0's and '1's
  136. def randomizeMatrix(nBegin, nEnd, mBegin, mEnd):
  137.     if nBegin > nEnd or mBegin > mEnd or nBegin != int(nBegin) or nEnd != int(nEnd) or mBegin != int(mBegin) or mEnd != int(mEnd):
  138.         print("Not valid syntax for function '" + randomizeMatrix.__name__ + "'")
  139.         return -1000
  140.     N = randrange(nBegin, nEnd+1)
  141.     M = randrange(mBegin, mEnd+1)
  142.     matrix = [[0 for __ in range(M)] for _ in range(N)]
  143.     for i in range(N):
  144.         for j in range(M):
  145.             matrix[i][j] = randrange(0, 2)
  146.     return matrix
  147.  
  148.  
  149. # MAIN FUNCTION
  150. arxikos = [[1, 0, 1],
  151.            [0, 1, 0],
  152.            [1, 0, 0]]
  153. prettySolve(arxikos)
  154.  
  155. arxikosRandom = randomizeMatrix(4, 7, 5, 8)
  156. prettySolve(arxikosRandom)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement