线索

网上已有其他人的解法:《HackerRank Forming a Magic Square 魔方代价问题》,但是看起来比较麻烦。看了Magic square的定义,发现有其规律性,加上对称的镜像,就只有8种样本模式。因此对输入的模式与样本模式进行匹配并计算出相差多少,排序后找到最小值即可。

代码解读

如下图,magic square共有两种模式,镜像对称,且每种模式可以旋转90°后产生一种变种,所以共8种。

MagicSquare

  • 定义8种样本模式的list
    cell_templates = [
        [1,3,9,7,6,8,4,2],
        [3,9,7,1,8,4,2,6],
        [9,7,1,3,4,2,6,8],
        [7,1,3,9,2,6,8,4],
        # mirror magic square
        [7,9,3,1,6,2,4,8],
        [9,3,1,7,2,4,8,6],
        [3,1,7,9,4,8,6,2],
        [1,7,9,3,8,6,2,4]
    ]

  • 将输入的三维数组进行组装
    cell_now = [s[0][1],s[1][2],s[2][1],s[1][0]\
                ,s[0][0],s[0][2],s[2][2],s[2][0]]
  • 找出所有相差的值
    for cell_template in cell_templates:
        cost_tmp = cost 
        for i in range(0,8):
            cost_tmp += abs(cell_template[i]-cell_now[i])
        cost_list.append(cost_tmp)
        print(cost_tmp)
        print(cell_template)
  • 排序找出最小值
    sorted_cost_list = sorted(cost_list, key=lambda x:x)
    minimun_cost = sorted_cost_list[0]

思考

这种方法的前提是已经找到了这magic square的模型,已经有理论后才可去找到规律抽象出模式去实现。

但若是想用计算机发现这种模型呢?值得思考。

还有,解决问题的奥义应该是简化问题,而非复杂。用这种方法比线索里的博客讲的要简洁得多。生活中做事情也一样,知道其本质的前提下,精简它。

附上总代码

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the formingMagicSquare function below.
def formingMagicSquare(s):
    cost_list = []

    cost = 0
    # fix center num
    if s[1][1] != 5:
        cost = abs(5-s[1][1])
        s[1][1] = 5
    # judge the 2\4\6\8 cell
    cell_templates = [
        [1,3,9,7,6,8,4,2],
        [3,9,7,1,8,4,2,6],
        [9,7,1,3,4,2,6,8],
        [7,1,3,9,2,6,8,4],
        # mirror magic square
        [7,9,3,1,6,2,4,8],
        [9,3,1,7,2,4,8,6],
        [3,1,7,9,4,8,6,2],
        [1,7,9,3,8,6,2,4]
    ]
    cell_now = [s[0][1],s[1][2],s[2][1],s[1][0]\
                ,s[0][0],s[0][2],s[2][2],s[2][0]]
    for cell_template in cell_templates:
        cost_tmp = cost 
        for i in range(0,8):
            cost_tmp += abs(cell_template[i]-cell_now[i])
        cost_list.append(cost_tmp)
    sorted_cost_list = sorted(cost_list, key=lambda x:x)
    minimun_cost = sorted_cost_list[0]
    return minimun_cost




if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = []

    for _ in range(3):
        s.append(list(map(int, input().rstrip().split())))

    result = formingMagicSquare(s)

    fptr.write(str(result) + '\n')

    fptr.close()

后记

发布博客后搜了一下自己的标题,发现有个MathBlog也写了这个问题,更详细美观,这个博客是专注于数学问题的,mark下来有空看。