Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package com
import scala.collection.mutable.ArrayBuffer
object MagicSquare {
def main(args: Array[String]): Unit = {
val target = Array[Array[Int]](
Array[Int](4, 8, 2),
Array[Int](4, 5, 7),
Array[Int](6, 1, 6)
)
println(formingMagicSquare(target))
// val candidates = getAllCandidates
// for (item <- candidates) {
// for (row <- item) {
// println(row.mkString("\t"))
// }
// println("\n")
// }
}
def formingMagicSquare(s: Array[Array[Int]]): Int = {
val candidates = getAllCandidates
var cost = Int.MaxValue
for (candidate <- candidates) {
var currentCost = 0
for ((row, rowIndex) <- candidate.zipWithIndex) {
for ((item, columnIndex) <- row.zipWithIndex) {
currentCost += Math.abs(item - s(rowIndex)(columnIndex))
}
}
if (currentCost < cost) cost = currentCost
}
cost
}
def getAllCandidates(): Array[Array[Array[Int]]] = {
val numberPairs = Array[Array[Int]](
Array[Int](1, 9),
Array[Int](2, 8),
Array[Int](3, 7),
Array[Int](4, 6)
)
val positions = ArrayBuffer[Array[Pair]]()
val A = Array[Pair](Pair(Point(0, 0), Point(2, 2)), Pair(Point(2, 2), Point(0, 0)))
val B = Array[Pair](Pair(Point(0, 1), Point(2, 1)), Pair(Point(2, 1), Point(0, 1)))
val C = Array[Pair](Pair(Point(0, 2), Point(2, 0)), Pair(Point(2, 0), Point(0, 2)))
val D = Array[Pair](Pair(Point(1, 0), Point(1, 2)), Pair(Point(1, 2), Point(1, 0)))
val permutations = getAllPermutations(4, ArrayBuffer[Int](0, 1, 2, 3))
for (item <- permutations) {
for (a <- A){
for (b <- B){
for (c <- C){
for (d <- D){
val temp = Array[Pair](a, b, c, d)
positions += Array[Pair](
temp(item(0)), temp(item(1)), temp(item(2)), temp(item(3))
)
}
}
}
}
}
val candidates = ArrayBuffer[Array[Array[Int]]]()
for (pairs <- positions) {
val matrix = Array.ofDim[Int](3, 3)
matrix(1)(1) = 5
for ((pair, index) <- pairs.zipWithIndex) {
matrix(pair.left.x)(pair.left.y) = numberPairs(index)(0)
matrix(pair.right.x)(pair.right.y) = numberPairs(index)(1)
}
candidates += matrix
}
candidates.toArray.filter(isValid(_))
}
case class Pair(left: Point, right: Point)
case class Point(x: Int, y: Int)
def isValid(target: Array[Array[Int]]): Boolean = {
val STANDARD = 15
var valid = true
var index = 0
if (STANDARD.equals(target(1)(1) + target(0)(0) + target(2)(2)) == false) valid = false
if (STANDARD.equals(target(1)(1) + target(0)(2) + target(2)(0)) == false) valid = false
while(index < 3 && valid) {
if (STANDARD.equals(target(0)(index) + target(1)(index) + target(2)(index)) == false) valid = false
if (STANDARD.equals(target(index)(0) + target(index)(1) + target(index)(2)) == false) valid = false
index += 1
}
valid
}
def getAllPermutations(count: Int, candidates: ArrayBuffer[Int]): ArrayBuffer[ArrayBuffer[Int]] = {
val container = ArrayBuffer[ArrayBuffer[Int]]()
traverse(count, candidates, ArrayBuffer[Int](), container)
container
}
def traverse(count: Int, candidates: ArrayBuffer[Int], bag: ArrayBuffer[Int], container: ArrayBuffer[ArrayBuffer[Int]]): Unit = {
val candidatesLength = candidates.length
if (candidatesLength >= count) {
if (count.equals(1)) {
for (item <- candidates) {
val finalBag = bag.clone()
finalBag += item
container += finalBag
}
} else {
for ((item, index) <- candidates.zipWithIndex) {
val nextBag = bag.clone()
nextBag += item
val nextCandidates = candidates.slice(0, index) ++ candidates.slice(index + 1, candidatesLength)
traverse(count - 1, nextCandidates, nextBag, container)
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.