We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Forming a Magic Square
  2. Discussions

Forming a Magic Square

Sort by

recency

|

38 Discussions

|

  • strawmsc
     + 0 comments

    Idk why all the python answers assume you'd have access to a list of all magic squares when doing this problem.I guess to game the hackerrank rankings? Not very helpful for people actually trying to learn. Anyways, Here's how I would solve this on an actual test, including code to find all magic squares:

    def is_magic(s):
    
    # Rows
    if not all(sum(row) == 15 for row in s):
        return False

    # Columns
    for col in range(3):
        if s[0][col] + s[1][col] + s[2][col] != 15:
            return False

    # Diagonals
    if (s[0][0] + s[1][1] + s[2][2] != 15 or
        s[0][2] + s[1][1] + s[2][0] != 15):
        return False

    return True
    
    
def formingMagicSquare(s):
    magic_squares = []
    
    for perm in permutations(range(1, 10)): 
        
        square = [list(perm[0:3]), list(perm[3:6]), list(perm[6:9])]
        
        if is_magic(square):
            magic_squares.append(square)


    min_cost = math.inf
    for square in magic_squares:
        cost = 0
        for i in range(3):
            for j in range(3):
                cost+=abs(s[i][j] - square[i][j])
        
        min_cost = min(min_cost,cost)
    
    return min_cost

  • kocsis_tamas_ol1
     + 0 comments

    I have no clue how you supossed to figure this out on your own without serious matrix theory knowladge, and the knowladge of this silly trivia magic array, here is the info: There are fixed 9 numbers in 3x3 magic array, there is no other choice. Thje example gives this. The only different arrays can either 90 degree rotations of this magic array. Or a reflection on the middle, then this can also be rotated 90 degrees 3 times to get different versions. Good luck figuring this out on an interview.. ???

    int matrix_diff(vector>& A, vector>& B){ int diff=0; for(int i=0;i

    void transpose(vector>& A){ for(int i=0; i

    void reflect(vector>& A){ for(int i=0; i

    int formingMagicSquare(vector> s) { std::vector> magic = {{8,3,4},{1,5,9},{6,7,2}}; //there is only one magic array, and its 8 versions, by 3* 90degree rotation, then 1 reflection and 3rotations again //make another version, then compare diff to s, and record minimum; int min_global_diff=matrix_diff(s, magic);

    //try 3 rotations
auto magic_rotation = magic;
for(int rot=0; rot<4; rot++){ //do a 90 degree rotatiom by transpose+reflect
    transpose(magic_rotation);
    reflect(magic_rotation);
    min_global_diff = min(min_global_diff, matrix_diff(s, magic_rotation));
}

//now just do 1 reflection before 3 rotations again
auto magic_reflect_rot = magic; 
reflect(magic_reflect_rot); 
//again 3 90 degree rotations
for(int rot=0; rot<4; rot++){ //do a 90 degree rotatiom by transpose+reflect
    transpose(magic_reflect_rot);
    reflect(magic_reflect_rot);
    min_global_diff = min(min_global_diff, matrix_diff(s, magic_reflect_rot));
}

return min_global_diff;

    }

  • michael_chen_0
     + 0 comments

    Python 3:

    import itertools
from collections.abc import Iterable


def formingMagicSquare(s: Iterable[Iterable[int]]) -> int:
    s_flat = (*itertools.chain.from_iterable(s),)
    return min(
        sum(abs(i - j) for i, j in zip(magic_square, s_flat))
        for magic_square in (
            (2, 7, 6, 9, 5, 1, 4, 3, 8),
            (2, 9, 4, 7, 5, 3, 6, 1, 8),
            (4, 3, 8, 9, 5, 1, 2, 7, 6),
            (4, 9, 2, 3, 5, 7, 8, 1, 6),
            (6, 1, 8, 7, 5, 3, 2, 9, 4),
            (6, 7, 2, 1, 5, 9, 8, 3, 4),
            (8, 1, 6, 3, 5, 7, 4, 9, 2),
            (8, 3, 4, 1, 5, 9, 6, 7, 2),
        )
    )

  • filipe_gomes_ar1
     + 0 comments

    Solution in CPP, building all magic squares:

    #include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int>> matrix;

vector<matrix> magicSquares;
matrix m;

int cost(int a, int b) {
  return abs(a - b);
}

int complement(int a) {
  return 10 - a;
}

bool between(int a, int b, int c) {
  return a >= b && a <= c;
}

void generateMagicSquares() {
  for (int a = 1; a <= 9; ++a) {
    for (int c = 1; c <= 9; ++c) {
      if (a == c || a == complement(c)) continue;

      int d = 5 + c - a;
      int b = 15 - c - a;

      if (a == b || a == complement(b)) continue;
      if (a == d || a == complement(d)) continue;
      if (b == c || b == complement(c)) continue;
      if (b == d || b == complement(d)) continue;
      if (c == d || c == complement(d)) continue;

      if (between(d, 1, 9) && between(b, 1, 9)) {
        vector<int> line1 = {a, b, c};
        vector<int> line2 = {d, 5, complement(d)};
        vector<int> line3 = {complement(c), complement(b), complement(a)};
        matrix m = {line1, line2, line3};
        magicSquares.push_back(m);
      }
    }
  }
}

int distance(matrix& a, matrix& b) {
  int dist = 0;

  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      dist += cost(a[i][j], b[i][j]);
    }
  }

  return dist;
}

int main () {
  int aux, minCost = INT32_MAX;
  generateMagicSquares();

  for (int i = 0; i < 3; ++i) {
    m.push_back(vector<int>());
    for (int j = 0; j < 3; ++j) {
      cin >> aux;
      m[i].push_back(aux);
    }
  }

  for (matrix& magicSquare : magicSquares) {
    minCost = min(minCost, distance(m, magicSquare));
  }

  cout << minCost << endl;
  return 0;
}

  • BSharp
     + 0 comments

    Not as bad a question as some people here make out.

    1. Generate all permutations of list [1,2,3,4,5,6,7,8,9] (the list is a flattened square 3x3 2D array)

    2. Filter for lists that are magic (the criteria are in the question)

    3. Calculate distance from input array to each magic square

    4. Return minimum distance