Home/

...

/

Problem Challenge 1

Problem Challenge 1

Problem statement

Given a binary matrix representing an image, we want to flip the image horizontally, then invert it.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [0,1,1][0, 1, 1] horizontally results in [1,1,0][1, 1, 0].

To invert an image means that each 00 is replaced by 11, and each 11 is replaced by 00. For example, inverting [1,1,0][1, 1, 0] results in [0,0,1][0, 0, 1].

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Problem Challenge 1 lesson:

Press + to interact
Python 3.5
def flip_and_invert_image(matrix):
  if not matrix:
    return []
  C = len(matrix[0])
  for row in matrix:
    for i in range((C+1)//2):
      row[i], row[C - i - 1] = row[C - i - 1] ^ 1, row[i] ^ 1
    
  return matrix
 
def main():
    print(flip_and_invert_image([[1,0,1], [1,1,1], [0,1,1], [0,1,1]]))
    print(flip_and_invert_image([[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]))
 
main()

Sample input #1

Input: [
  [1,0,1],
  [1,1,1],
  [0,1,1]
]

Orange cells in the table represent the final state of the rows.

Outer loop iteration

Inner loop iteration

Line number

C

row

i

row[i]

row[C - i - 1]

-

-

2

3

-

-

-

-

1

-

3

3

[1, 0, 1]

-

-

-

1

1

4-5

3

[0, 0, 0]

0

0

0

1

2

4-5

3

[0, 1, 0]

1

1

1

2

-

3

3

[1, 1, 1]

-

-

-

2

1

4-5

3

[0, 1, 0]

0

0

0

2

2

4-5

3

[0, 0, 0]

1

0

0

3

-

3

3

[0, 1, 1]

-

-

-

3

1

4-5

3

[0, 1, 1]

0

0

1

3

2

4-5

3

[0, 0, 1]

1

0

0

Sample input #2

Input: [
  [1,1,0,0],
  [1,0,0,1],
  [0,1,1,1], 
  [1,0,1,0]
]

Outer loop iteration

Inner loop iteration

Line number

C

row

i

row[i]

row[C - i - 1]

-

-

2

4

-

-

-

-

1

-

3

4

[1, 1, 0, 0]

-

-

-

1

1

4-5

4

[1, 1, 0, 0]

0

1

0

1

2

4-5

4

[1, 1, 0, 0]

1

1

0

2

-

3

4

[1, 0, 0, 1]

-

-

-

2

1

4-5

4

[0, 0, 0, 0]

0

0

0

2

2

4-5

4

[0, 1, 1, 0]

1

1

1

3

-

3

4

[0, 1, 1, 1]

-

-

-

3

1

4-5

4

[0, 1, 1, 1]

0

0

1

3

2

4-5

4

[0, 0, 0, 1]

1

0

0

4

-

3

4

[1, 0, 1, 0]

-

-

-

4

1

4-5

4

[1, 0, 1, 0]

0

1

0

4

2

4-5

4

[1, 0, 1, 0]

1

0

1

Step-by-step solution construction

The first step in our solution is flipping the image, where each row of the matrix is reversed. This can be achieved by iterating over the row elements and swapping the ithith element from the left with the ithith element from the right. Consider the following example:

input row: [1, 0, 2, 3] 

i = 0
ith element from the left =  1
ith element from the right = 3
Row after swapping: [3, 0, 2, 1]

i = 1
ith element from the left =  0
ith element from the right = 2
Row after swapping: [3, 2, 0, 1]

When we reach the middle of our row, we stop the flipping process.

Press + to interact
Python 3.5
def printing_matrix(matrix, cur_row_index = -1, cur_row_sym=""):
    outputstr = ""
    for i, row in enumerate(matrix, start=1):
        if cur_row_sym != "":
            if cur_row_index == i:
                outputstr += cur_row_sym + " "
            else:
                outputstr += "  "
        for i in row:
            outputstr += str(i) + " "
        outputstr += "\n"
 
    return outputstr[:-2]
def flip_and_invert_image(matrix):
    if not matrix:
        return []
    C = len(matrix[0])
    print("Input matrix: ")
    print(printing_matrix(matrix))
    print("Flipping the rows")
    j, k = 1, 1
    for row in matrix:
        print("\tOuter loop iteration: ", j, sep="")
        j += 1
        print("\t\tTaking the row: ", row)
        for i in range((C+1)//2):
            print("\t\tInner loop iteration: ", k, sep="")
            k += 1
            if i == (C - i - 1):
                print("\t\t\ti: ", i)
                print("\t\t\tSince we've reached the middle of our row, we stop here.")
            else:
                print("\t\t\tSwapping indices ", i, " and ",C - i - 1, " of the row", sep="")
            row[i], row[C - i - 1] = row[C - i - 1], row[i]
            print("\t\t\tUpdated matrix: ")
            printStr = printing_matrix(matrix, j-1, ">").replace("\n", "\n\t\t\t\t")
            print("\t\t\t\t" + printStr)
        k = 1
        print()
    return matrix
def main():
    input = [[[1,0,1], [1,1,1], [0,1,1]], [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]]
    for i in input:
        # print("Flipped matrix: ", flip_and_invert_image(i), sep = "")
        print("Flipped matrix:\n", printing_matrix(flip_and_invert_image(i)), sep = "")
        print(("-"*100)+"\n")
main()

The next step is inverting our row elements. This can be done by taking the XOR of each element with 1.

Recall that XOR of 0 and 1 returns 1, and XOR of 1 and 1 returns 0.

For example, for the row elements [1,0,1,1][1, 0, 1, 1]:

  • 1 XOR 1 = 0
  • 0 XOR 1 = 1
  • 1 XOR 1 = 0
  • 1 XOR 1 = 0

The resulting row will be [0,1,0,0][0, 1, 0, 0], which is the inverted version of our input.

Let’s see the above step below:

Press + to interact
Python 3.5
def printing_matrix(matrix, cur_row_index = -1, cur_row_sym=""):
    outputstr = ""
    for i, row in enumerate(matrix, start=1):
        if cur_row_sym != "":
            if cur_row_index == i:
                outputstr += cur_row_sym + " "
            else:
                outputstr += "  "
        for i in row:
            outputstr += str(i) + " "
        outputstr += "\n"
 
    return outputstr[:-2]
def flip_and_invert_image(matrix):
    if not matrix:
        return []
    C = len(matrix[0])
    print("Input matrix: ")
    print(printing_matrix(matrix))
    print("")
    j, k = 1, 1
    for row in matrix:
        print("Outer loop iteration: ", j, sep="")
        j += 1
        print("\tTaking the row: ", row)
        for i in range((C+1)//2):
            print("\tInner loop iteration: ", k, sep="")
            k += 1
            if i == (C - i - 1):
                print("\t\ti: ", i)
                print("\t\tSince we've reached the middle of our row, we stop here.")
            else:
                print("\t\tSwapping indices ", i, " and ",C - i - 1, " of the row", sep="")
            row[i], row[C - i - 1] = row[C - i - 1], row[i]
            print("\t\tUpdated matrix: ")
            printStr = printing_matrix(matrix, j-1, ">").replace("\n", "\n\t\t\t\t")
            print("\t\t\t\t" + printStr)
            print("")
            if i == (C - i - 1):
                print("\t\tInverting the row element at index: ", i, sep = "")
            else:
                print("\t\tInverting the row elements at indices ", i, " and ", C - i - 1, sep = "")
            row[i], row[C - i - 1] = row[i] ^ 1, row[C - i - 1] ^ 1
            print("\t\tMatrix with inverted row: ")
            printStr = printing_matrix(matrix, j-1, ">").replace("\n", "\n\t\t\t\t")
            print("\t\t\t\t" + printStr)
            print("")
        k = 1
        print()
    return matrix
def main():
    input = [[[1,0,1], [1,1,1], [0,1,1]], [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]]
    for i in input:
        print("Flipped and inverted matrix:\n", printing_matrix(flip_and_invert_image(i)), sep = "")
        print(("-"*100)+"\n")
main()