• + 0 comments

    I wanted to do it the naive way without Googling what the valid permutations are.

    package main
    
    import (
        "bufio"
        "fmt"
        "io"
        "os"
        "strconv"
        "strings"
        "math"
    )
    
    func sum(s []int32) int32 {
        sum := int32(0)
        for i := range s {
            sum += s[i]
        }
        return sum
    }
    
    
    func isMagic(s [][]int32) bool {
        sums := []int32{
            sum(s[0]), sum(s[1]), sum(s[2]),
            s[0][0]+s[1][0]+s[2][0],                    
            s[0][1]+s[1][1]+s[2][1],                     
            s[0][2]+s[1][2]+s[2][2],                     
            s[0][0]+s[1][1]+s[2][2],                     
            s[0][2]+s[1][1]+s[2][0],                      
        }
        for i := range sums {
            if sums[i] != 15 {
                return false
            }
        }
        return true
    }
    
    func permutations(arr []int32)[][]int32{
        var helper func([]int32, int32)
        res := [][]int32{}
    
        helper = func(arr []int32, n int32){
            if n == 1{
                tmp := make([]int32, len(arr))
                copy(tmp, arr)
                res = append(res, tmp)
            } else {
                for i := 0; i < int(n); i++{
                    helper(arr, n - 1)
                    if n % 2 == 1{
                        tmp := arr[i]
                        arr[i] = arr[n - 1]
                        arr[n - 1] = tmp
                    } else {
                        tmp := arr[0]
                        arr[0] = arr[n - 1]
                        arr[n - 1] = tmp
                    }
                }
            }
        }
        helper(arr, int32(len(arr)))
        return res
    }
    
    func generateAllPossibleSquares() [][][]int32 {
        squares := permutations([]int32{1,2,3,4,5,6,7,8,9})
        validMagics := make([][][]int32, 8)
        validCounter := 0
        for _, s := range squares {
            square := [][]int32{s[0:3], s[3:6], s[6:9]}
            if isMagic(square) {
                validMagics[validCounter] = square
                validCounter += 1
            }
        }
        return validMagics
    }
    
    func cost(sq1 [][]int32, sq2 [][]int32) int32 {
        totalCost := int32(0)
        for i := range len(sq1) {
            for j := range len(sq1[i]) {
                totalCost += int32(math.Abs(float64(sq1[i][j] - sq2[i][j])))
            }
        }
        return totalCost
    } 
    
    /*
     * Complete the 'formingMagicSquare' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY s as parameter.
     */
    
    func formingMagicSquare(s [][]int32) int32 {
        // First, we need a function that calculates all the various sums. 
        // To find the closest magic square, we calculate the difference between each intersecting row
        // The smallest cost should be the difference between intersecting rows
        minCost := int32(math.MaxInt32)
        validMagics := generateAllPossibleSquares()
        for i := range validMagics {
            newCost := cost(s, validMagics[i])
            if newCost < minCost {
                minCost = newCost
            }
        }
        return minCost
    
    }
    
    func main() {
        reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)
    
        stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
        checkError(err)
    
        defer stdout.Close()
    
        writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)
    
        var s [][]int32
        for i := 0; i < 3; i++ {
            sRowTemp := strings.Split(strings.TrimRight(readLine(reader)," \t\r\n"), " ")
    
            var sRow []int32
            for _, sRowItem := range sRowTemp {
                sItemTemp, err := strconv.ParseInt(sRowItem, 10, 64)
                checkError(err)
                sItem := int32(sItemTemp)
                sRow = append(sRow, sItem)
            }
    
            if len(sRow) != 3 {
                panic("Bad input")
            }
    
            s = append(s, sRow)
        }
    
        result := formingMagicSquare(s)
    
        fmt.Fprintf(writer, "%d\n", result)
    
        writer.Flush()
    }
    
    func readLine(reader *bufio.Reader) string {
        str, _, err := reader.ReadLine()
        if err == io.EOF {
            return ""
        }
    
        return strings.TrimRight(string(str), "\r\n")
    }
    
    func checkError(err error) {
        if err != nil {
            panic(err)
        }
    }