PROBLEM LINK: CodeChef: Practical coding for everyone
Author: [Setter’s name]:anvinjoice | CodeChef User Profile for Anvin Joice | CodeChef
Tester: [Tester’s name]:anvinjoice | CodeChef User Profile for Anvin Joice | CodeChef
Editorialist: [Editorialist’s name]:anvinjoice | CodeChef User Profile for Anvin Joice | CodeChef
DIFFICULTY : BEGINNER
PREREQUISITES:
Nill
PROBLEM:
We define a magic square to be an n×n matrix of distinct positive integers from 1 to n2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant. You will be given a 3×3 matrix s of integers in the inclusive range [1,9] . We can convert any digit a to any other digit b in the range [1,9] at cost of |a-b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line. Note: The resulting magic square must contain distinct integers in the inclusive range [1,9] .
#EXPLANATION:
The general idea is to find all possible 3×3 magic squares and, for each one, compute the cost of changing s into a known magic square. The result is the smallest of these costs.
We know that s will always be 3×3 . There are 8 possible magic squares for a 3×3 matrix. There are two ways to approach this:
Compute all 8 magic squares by examining all permutations of integers 1,2,…9 , and for each one, check if it forms a magic square if the permutation is inserted into the square starting from the upper-left-hand corner.
Find all possible magic squares somewhere (e.g., via a web search) and hard-code them into your solution.
We compute the cost of turning the input square into a particular magic square by summing the cost of changing all its cells into the corresponding cells of the magic square.
#SOLUTIONS
Setter's Solution
PYTHON
def formingMagicSquare(s):
# reform the array to one dimension
s = s[0] + s[1] + s[2]
# these are all forms of a 3x3 magic array
magic = [[8, 1, 6, 3, 5, 7, 4, 9, 2], [6, 1, 8, 7, 5, 3, 2, 9, 4],
[4, 3, 8, 9, 5, 1, 2, 7, 6], [2, 7, 6, 9, 5, 1, 4, 3, 8],
[2, 9, 4, 7, 5, 3, 6, 1, 8], [4, 9, 2, 3, 5, 7, 8, 1, 6],
[6, 7, 2, 1, 5, 9, 8, 3, 4], [8, 3, 4, 1, 5, 9, 6, 7, 2]]
mini = 2**64
# brute force the difference
for arr in magic:
diff = 0
for i, j in zip(s, arr):
diff += abs(i - j)
mini = min(diff, mini)
return mini
Tester's Solution
Same Person
Editorialist's Solution
Same Person