Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- You are given a two-dimensional integer matrix containing 1s and 0s.
- Return the maximum number of 1s you can get if you must flip a row and then flip a column.
- Constraints
- 1 ≤ n, m ≤ 250 where n and m are number of rows and columns in matrix.
- Example 1
- Input
- matrix = [
- [1, 0, 1],
- [0, 1, 0],
- [1, 0, 0]
- ]
- Output
- 8
- Explanation
- We can flip row 2 (i=1) to get:
- [[1, 0, 1],
- [1, 0, 1],
- [1, 0, 0]]
- And then flip column 2 (j=1) to get:
- [[1, 1, 1],
- [1, 1, 1],
- [1, 1, 0]]
- '''
- from random import randrange
- from copy import deepcopy
- # Function 1 - Flip elements
- def flip(element):
- if element == 0:
- element = 1
- elif element == 1:
- element = 0
- return element
- # Function 2 - Flip row's elements
- def flipRow(MATRIX, rowIndex):
- matrix = deepcopy(MATRIX)
- N = len(matrix)
- M = len(matrix[0])
- if rowIndex < 0 and rowIndex >= N:
- return matrix
- for i in range(N):
- if i == rowIndex:
- for j in range(M):
- matrix[i][j] = flip(matrix[i][j])
- return matrix
- # Function 3 - Flip column's elements
- def flipColumn(MATRIX, columnIndex):
- matrix = deepcopy(MATRIX)
- N = len(matrix)
- M = len(matrix[0])
- if columnIndex < 0 and columnIndex >= M:
- return matrix
- for j in range(M):
- if j == columnIndex:
- for i in range(N):
- matrix[i][j] = flip(matrix[i][j])
- return matrix
- # Function 4 - Flip both a row's and a column's elements
- def flipRowColumn(arxikos, rowIndex, columnIndex):
- MATRIX = deepcopy(arxikos)
- m1 = flipRow(MATRIX, rowIndex)
- m2 = flipColumn(m1, columnIndex)
- return m2
- # Function 5 - Sum of the elements of a 2D-matrix
- def sumMatrix(matrix):
- N = len(matrix)
- M = len(matrix[0])
- SUM = 0
- for i in range(N):
- for j in range(M):
- SUM += matrix[i][j]
- return SUM
- # Function 6 - Solve the problem
- def solve(arxikos):
- N = len(arxikos)
- M = len(arxikos[0])
- m2Solution = list()
- nSolution = 0
- mSolution = 0
- MAXSUM = 0
- # Here, I will scan all the possible ways and create all the NxM combinations of matrices
- # The matrix with the max sum of elements (the most possible '1's) will be returned as with its sum
- for nChange in range(N):
- MATRIX = deepcopy(arxikos)
- for mChange in range(M):
- # print(nChange, mChange)
- # print(MATRIX)
- m2 = flipRowColumn(MATRIX, nChange, mChange)
- # print(MATRIX, " ", m2)
- # print()
- # This is the changed matrix and I have to 'scan' it to find its sum
- SUM = sumMatrix(m2)
- if SUM > MAXSUM:
- MAXSUM = SUM
- nSolution = nChange
- mSolution = mChange
- m2Solution = m2.copy()
- return m2Solution, MAXSUM, nSolution, mSolution
- # Function 7 - Display a 2D-matrix
- def display(matrix):
- N = len(matrix)
- for i in range(N):
- print(matrix[i])
- # Function 8 - PrettySolve
- def prettySolve(arxikos):
- print("***********************************")
- print("Initial matrix: ")
- display(arxikos)
- m2Solution, MAXSUM, nSolution, mSolution = solve(arxikos)
- print()
- print("The max sum is", MAXSUM, "and can be achieved if I flip row with index", nSolution, "and column with index", mSolution)
- print("Final matrix after these 2 changes: ")
- display(m2Solution)
- print("***********************************")
- # Function 9 - Generate a random matrix NxM with '0's and '1's
- def randomizeMatrix(nBegin, nEnd, mBegin, mEnd):
- if nBegin > nEnd or mBegin > mEnd or nBegin != int(nBegin) or nEnd != int(nEnd) or mBegin != int(mBegin) or mEnd != int(mEnd):
- print("Not valid syntax for function '" + randomizeMatrix.__name__ + "'")
- return -1000
- N = randrange(nBegin, nEnd+1)
- M = randrange(mBegin, mEnd+1)
- matrix = [[0 for __ in range(M)] for _ in range(N)]
- for i in range(N):
- for j in range(M):
- matrix[i][j] = randrange(0, 2)
- return matrix
- # MAIN FUNCTION
- arxikos = [[1, 0, 1],
- [0, 1, 0],
- [1, 0, 0]]
- prettySolve(arxikos)
- arxikosRandom = randomizeMatrix(4, 7, 5, 8)
- prettySolve(arxikosRandom)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement