M = [[6,1,8],[7,5,3],[2,9,4]]

print("Part a")

print("Given",M)

N=flip(M,'hori')

print("Flip horizontal",N)

N=flip(M,'vert')

print("Flip vertical",N)

N=rotate(M,'clock',1)

print("Rotate clockwise once",N)

N=rotate(M,'counter',1)

print("Rotate counter-clockwise once",N)

N=rotate(M,'clock',2)

print("Rotate clockwise twice",N)

N=rotate(M,'counter',2)

print("Rotate counter-clockwise twice",N)

N=rotate(M,'clock',3)

print("Rotate clockwise thrice",N)

N=rotate(M,'counter',3)

print("Rotate counter-clockwise thrice",N)

print("==========")

print("Part b")

allM = generate(M)

print("Equivalent magic squares to",M)

for m in allM:

print(m)

print("==========")

print("Part c")

allM = generate(M)

sortedM = sortAll(M)

print("Sorted magic squares to",M)

for m in sortedM:

print(m)

print("==========")

print("Part d")

P = [[6,16,8],[12,10,8],[12,4,14]]

answer = decompose(P)

print("There are",len(answer),"answers")

for a in answer:

print(P,"=",a[0],"+",a[1])

The output would be:

Part a

Given [[6, 1, 8], [7, 5, 3], [2, 9, 4]]

Flip horizontal [[2, 9, 4], [7, 5, 3], [6, 1, 8]]

Flip vertical [[8, 1, 6], [3, 5, 7], [4, 9, 2]]

Rotate clockwise once [[2, 7, 6], [9, 5, 1], [4, 3, 8]]

Rotate counter-clockwise once [[8, 3, 4], [1, 5, 9], [6, 7, 2]]

Rotate clockwise twice [[4, 9, 2], [3, 5, 7], [8, 1, 6]]

Rotate counter-clockwise twice [[4, 9, 2], [3, 5, 7], [8, 1, 6]]

Rotate clockwise thrice [[8, 3, 4], [1, 5, 9], [6, 7, 2]]

Rotate counter-clockwise thrice [[2, 7, 6], [9, 5, 1], [4, 3, 8]]

==========

Part b

Equivalent magic squares to [[6, 1, 8], [7, 5, 3], [2, 9, 4]]

[[6, 1, 8], [7, 5, 3], [2, 9, 4]]

[[8, 1, 6], [3, 5, 7], [4, 9, 2]]

[[8, 3, 4], [1, 5, 9], [6, 7, 2]]

[[4, 9, 2], [3, 5, 7], [8, 1, 6]]

[[2, 7, 6], [9, 5, 1], [4, 3, 8]]

[[4, 3, 8], [9, 5, 1], [2, 7, 6]]

[[2, 9, 4], [7, 5, 3], [6, 1, 8]]

[[6, 7, 2], [1, 5, 9], [8, 3, 4]]

==========

Part c

Sorted magic squares to [[6, 1, 8], [7, 5, 3], [2, 9, 4]]

[[2, 7, 6], [9, 5, 1], [4, 3, 8]]

[[2, 9, 4], [7, 5, 3], [6, 1, 8]]

[[4, 3, 8], [9, 5, 1], [2, 7, 6]]

[[4, 9, 2], [3, 5, 7], [8, 1, 6]]

[[6, 1, 8], [7, 5, 3], [2, 9, 4]]

[[6, 7, 2], [1, 5, 9], [8, 3, 4]]

[[8, 1, 6], [3, 5, 7], [4, 9, 2]]

[[8, 3, 4], [1, 5, 9], [6, 7, 2]]

==========

Part d

There are 2 answers [[6, 16, 8], [12, 10, 8], [12, 4, 14]] = [[4, 9, 2], [3, 5, 7], [8, 1, 6]] + [[2, 7, 6], [9, 5, 1], [4, 3, 8]]

[[6, 16, 8], [12, 10, 8], [12, 4, 14]] = [[2, 7, 6], [9, 5, 1], [4, 3, 8]] + [[4, 9, 2], [3, 5, 7], [8, 1, 6]]

4. [25 marks] (Magic square) A magic square is a 3x3 square with numbers filled in, such that the sum of each row (three rows), the sum of each column (three columns) and the sum of each diagonal (two diagonals) are the same. The following is a magic square filled with numbers 1 to 9, and the sum is always 15. 6 | || 8 Given any magic square, one can generate equivalent magic squares, by rotating it clockwise or counter-clockwise. You could rotate it once, twice, or three times. Rotating it four times comes back to the original one. You can also generate equivalent magic squares by flipping it either vertically or horizontally. One may want to check how many different equivalent magic squares can be generated by rotation and/or flipping. Here are three examples by rotating the magic square above clockwise once, counter-clock twice and flipping horizontally, respectively: 2 | 7 | 6 4 9 4 6. (a) [7 marks] Write two Python functions flip(M, d) and rotate (M,d,n) to generate a new magic square from an input magie square M based on the requested operation. def flip (M,d): A function to flip a magic square M in direction d (d is either vert or hori) Input: magic square M, direction d Output: return flipped magic square def rotate (M, d,n) : A function to rotate a magic square M in direction d (d is either elock or counter) for n magic square M, direction d, times n times Input: Output: return rotated magic square (b) [6 marks] Based on your functions, write a Python function generate (M) to return a list of all the equivalent magie squares M such that M can be generated from M by a call to rotate, a call to flip, or a call to both (F1ip then rotate or rotate then flip). The set of equivalent magie squares includes M itself. def generate (M) : A function to return all the equivalent magic squares to M, including M magic squat st of equivalent magi c squares (c) [6 marks] While we can find the list of equivalent magie squares, it is harder to compare them. Let us sort them in a standard order for ease of comparison. Treat the magic square as a list of 9 elements, e.g. the example magic square above is considered [6,1,8,7,5,3,2,9,4]]. Magic square Mi is before magic square Ma if the first element of M, is smaller than the first element of M2. If the first element is the same, compare the second element, and so on to determine the ordering. Write a Python function before (M1, M2) to determine whether Mi is before M2 in standard order. def before (M1, M2) : A function to determine whether M1 is before M2 in standard order Input: magic squares M1 and M2 Output: return True if M1 is before M2, False otherwise With your Python function before, it is casy to sort all the equivalent magic squares in standard order using the following simple sorting function. def sortAll (M) : allM - generate (M) sortedM - list () while allM: small, where - allM[0], O for i in range (1, len (allM) ) : if before (allM[i] , small): small, where - allM[i], i sortedM.append (small) del (allM[ where]) return sortedM (d) [6 marks] Given any two magic squares, a new magic square can be generated by adding the corresponding elements from the two magic squares in each cell. For example, adding the two magic squares on the left yields the magic square on the right. 2 | 7 | 6 | 1 4 9 | 2 3 5 7 = 8. 6 | 8 12 10 8 4 8. 12 4 14 It is easy to compute M = M1 + M2, if we know M1 and M2. It is harder to do the reverse, i.e., to decompose M back to M1 and M2. Assuming that M1 and M2 are equivalent to the example matrix above, write a Python function to decompose a given magic square M into its components M1 and M2 making use of your Python functions defined above, or otherwise. Note that you do not need to sort the answer. Any ordering is acceptable. def decompose (M) : A function to decompose M such that M = M1 + M2 Input: magic square M Output: return a list of [[M1,M2], [M1',M2'],...] Include the following statements in your .py file for testing