Level: Medium from HackerRank
This week me and two other friends tackled the Magic Square Coding Challenge. It was great to work together to come to a solution. Seeing different point of views, and thought processes makes it more fun, all while being able to share out loud your own thoughts. This was our first medium level questioned we tackled. Below I will explain our brute force solution and the process we took to get there. We managed to get a few test cases passing. And in the future we will work on the algorithm to come up with a faster solution that goes over all the edge cases, as well as refactoring.
The Problem:
We define a magic square to be an n x n matrix of distinct positive integers from 1 to n² 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 x 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].
Example
$s = [[5, 3, 4], [1, 5, 8], [6, 4, 2]]
The matrix looks like this:
5 3 4
1 5 8
6 4 2We can convert it to the following magic square:
8 3 4
1 5 9
6 7 2This took three replacements at a cost of |5–8| + |8–9| + |4 -7| = 7.
Function Description
Complete the formingMagicSquare function in the editor below.
formingMagicSquare has the following parameter(s):
- int s[3][3]: a 3x3 array of integers
Returns
- int: the minimal total cost of converting the input square to a magic square
Input Format
Each of the 3 lines contains three space-separated integers of row .
The Solution:
function formingMagicSquare(s) {
// Length of array
let n = s[0].length
let newArr = [] // iterate through matrix, add each element to newArr
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
newArr.push(s[i][j])
}
} // print all corner numbers (index: 0,2,6,8) (values: 2-8,4-6,8-2,6-4)
// candidate pairs
// (1,9)(9,1)
// (3,7)(7,3)
// (2,8)(8,2)
// (4,6)(6,4) let changes = []
let result = 0
for (let i = 0; i < newArr.length; i++) { // NOTE: Work on writing a dynamic code block
switch (i) {
case 0: {
if (newArr[i] == 8) {
let beforeChange = newArr[8]
newArr[8] = 2
changes.push(Math.abs(beforeChange - newArr[8])) }
if (newArr[i] == 2) {
let beforeChange = newArr[8]
newArr[8] = 8
changes.push(Math.abs(beforeChange - newArr[8])) }
if (newArr[i] == 4) {
let beforeChange = newArr[8]
newArr[8] = 6
changes.push(Math.abs(beforeChange - newArr[8])) }
if (newArr[i] == 6) {
let beforeChange = newArr[8]
newArr[8] = 4
changes.push(Math.abs(beforeChange - newArr[8]))
}
}
break;
case 1:
if (newArr[i] == 1) {
let beforeChange = newArr[7]
newArr[7] = 9
changes.push(Math.abs(beforeChange - newArr[7]))
}
if (newArr[i] == 9) {
let beforeChange = newArr[7]
newArr[7] = 1
changes.push(Math.abs(beforeChange - newArr[7]))
}
if (newArr[i] == 3) {
let beforeChange = newArr[7]
newArr[7] = 7
changes.push(Math.abs(beforeChange - newArr[7]))
}
if (newArr[i] == 7) {
let beforeChange = newArr[7]
newArr[7] = 3
changes.push(Math.abs(beforeChange - newArr[7]))
}
break;
case 2: {
if (newArr[i] == 8) {
let beforeChange = newArr[6]
newArr[6] = 2
changes.push(Math.abs(beforeChange - newArr[6])) }
if (newArr[i] == 2) {
let beforeChange = newArr[6]
newArr[6] = 8
changes.push(Math.abs(beforeChange - newArr[6])) }
if (newArr[i] == 4) {
let beforeChange = newArr[6]
newArr[6] = 6
changes.push(Math.abs(beforeChange - newArr[6])) }
if (newArr[i] == 6) {
let beforeChange = newArr[6]
newArr[6] = 4
changes.push(Math.abs(beforeChange - newArr[6]))
} }
break;
case 3: {
if (newArr[i] == 1) {
let beforeChange = newArr[5]
newArr[5] = 9
changes.push(Math.abs(beforeChange - newArr[5]))
}
if (newArr[i] == 9) {
let beforeChange = newArr[5]
newArr[5] = 1
changes.push(Math.abs(beforeChange - newArr[5]))
}
if (newArr[i] == 3) {
let beforeChange = newArr[5]
newArr[5] = 7
changes.push(Math.abs(beforeChange - newArr[5]))
}
if (newArr[i] == 7) {
let beforeChange = newArr[5]
newArr[5] = 3
changes.push(Math.abs(beforeChange - newArr[5]))
}
break;
}
case 4: {
let beforeChange = newArr[i]
newArr[i] = 5
changes.push(Math.abs(beforeChange - newArr[i]))
break;
}
case 5: {
if (newArr[i] == 1) {
let beforeChange = newArr[3]
newArr[3] = 9
changes.push(Math.abs(beforeChange - newArr[3]))
}
if (newArr[i] == 9) {
let beforeChange = newArr[3]
newArr[3] = 1
changes.push(Math.abs(beforeChange - newArr[3]))
}
if (newArr[i] == 3) {
let beforeChange = newArr[3]
newArr[3] = 7
changes.push(Math.abs(beforeChange - newArr[3]))
}
if (newArr[i] == 7) {
let beforeChange = newArr[3]
newArr[3] = 3
changes.push(Math.abs(beforeChange - newArr[3]))
}
break;
}
case 6: {
if (newArr[i] == 8) {
let beforeChange = newArr[2]
newArr[2] = 2
changes.push(Math.abs(beforeChange - newArr[2])) }
if (newArr[i] == 2) {
let beforeChange = newArr[2]
newArr[2] = 8
changes.push(Math.abs(beforeChange - newArr[2])) }
if (newArr[i] == 4) {
let beforeChange = newArr[2]
newArr[2] = 6
changes.push(Math.abs(beforeChange - newArr[2])) }
if (newArr[i] == 6) {
let beforeChange = newArr[2]
newArr[2] = 4
changes.push(Math.abs(beforeChange - newArr[2]))
} }
break;
case 7:
if (newArr[i] == 1) {
let beforeChange = newArr[1]
newArr[1] = 9
changes.push(Math.abs(beforeChange - newArr[1]))
}
if (newArr[i] == 9) {
let beforeChange = newArr[1]
newArr[1] = 1
changes.push(Math.abs(beforeChange - newArr[1]))
}
if (newArr[i] == 3) {
let beforeChange = newArr[1]
newArr[1] = 7
changes.push(Math.abs(beforeChange - newArr[1]))
}
if (newArr[i] == 7) {
let beforeChange = newArr[1]
newArr[1] = 3
changes.push(Math.abs(beforeChange - newArr[1]))
}
break;
case 8: {
if (newArr[i] == 8) {
let beforeChange = newArr[0]
newArr[0] = 2
changes.push(Math.abs(beforeChange - newArr[0])) }
if (newArr[i] == 2) {
let beforeChange = newArr[0]
newArr[0] = 8
changes.push(Math.abs(beforeChange - newArr[0])) }
if (newArr[i] == 4) {
let beforeChange = newArr[0]
newArr[0] = 6
changes.push(Math.abs(beforeChange - newArr[0])) }
if (newArr[i] == 6) {
let beforeChange = newArr[0]
newArr[0] = 4
changes.push(Math.abs(beforeChange - newArr[0])) } }
break;
default:
} result = changes.reduce((acc, cur) => {
return acc + cur
})
}
console.log("Result: ", result)
return result
}
Thought Process:
I know it's overwhelming looking at the long block of code. But I’ll walk you through it. It will see really simple by the end of it. (Remember: this is the BRUTE FORCE)
The first step to solving this problem is to understand it.
-What is a Magic Square?
The picture to the left is the basic idea.
Wikipedia Definition:
In recreational mathematics, a square array of numbers, usually positive integers, is called a magic square if the sums of the numbers in each row, each column, and both main diagonals are the same.[1][2] The order of the magic square is the number of integers along one side (n), and the constant sum is called the magic constant.
Rules for Magic Square: (Recommend: As you read the following rules look at the picture above)
- 3 x 3 magic square needs to sum up to 15.
- 4 corners of the square need to be even numbers
- Middle square is going to always be a 5
- Numbers surrounding the 5 thats are not corners need to be odd numbers
- Diagonal corner numbers have the be either [2 and 8] or [4 and 6] because they have to add up to 10 since the sum of the diagonal should be 10 + 5(since 5 is always in the middle)
- Odd diagonals also have to add up to 10 so the pairs for those are [7 and 3] or [9 and 1]
Now that you have a clear understanding of what makes a magic square. I will guide you on our code.
- We got the length of one array in the 2D array.
- Iterated through the dynamic array and push the values to a new array
- Then we declared a new empty array and a counter that started at 0.
- Now we iterate for each number in the new array to check is they are following the previous rules mentioned. (This works because the numbers were pushed in order.)
- We check each number with a switch case. While keeping track of previous numbers and newly changed numbers.
- We then subtract the previous change number and the new number to get the difference. And push the difference to the changes array.
- We later sum all of the numbers in the changes array resulting in the total cost. Which we save in the results variable.
As you can see above we have a brute force solution that is NOT DRY! But we were really happy to have at least a working solution to pass some test cases. Now our job will be to think of the edge cases and make the changes accordingly.
I hope this blog brought some light to the magic square. Thank you for reading!
