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

|

39 Discussions

|

  • victor_reial
     + 0 comments

    This is a way better problem than misery nim. Yes, you can know before hand all magic squares (as you can you know the xor solutions), but, here, you can even deduce all the magic squares or build them all during the interview, which is probably what is expected. However, building them somewhat efficiently instead of creating all 9! and then filtering

    Python best solution

    If you’re looking for solutions to the 3-month preparation kit in either Python or Rust, you can find them below: my solutions 

    def magic_squares(s):
    # Time complexity: O(1)
    # Space complexity (ignoring input): O(1)
    # Hard coded or not, both are O(1), since it's maximum of 9! to create all possible
    # squares, which is a costant (and that is the inefficient way)
    magic_squares_hard_coded = [
        [[2, 7, 6], [9, 5, 1], [4, 3, 8]],
        [[4, 9, 2], [3, 5, 7], [8, 1, 6]],
        [[8, 3, 4], [1, 5, 9], [6, 7, 2]],
        [[6, 1, 8], [7, 5, 3], [2, 9, 4]],
        [[6, 7, 2], [1, 5, 9], [8, 3, 4]],
        [[2, 9, 4], [7, 5, 3], [6, 1, 8]],
        [[4, 3, 8], [9, 5, 1], [2, 7, 6]],
        [[8, 1, 6], [3, 5, 7], [4, 9, 2]],
    ]
    magic_squares = magic_squares_creating_efficiently()

    minimum_cost = 99
    for square in magic_squares:
        cost = 0
        for i in range(0, 3):
            for j in range(0, 3):
                cost += abs(s[i][j] - square[i][j])

        minimum_cost = min(minimum_cost, cost)

    return minimum_cost


def magic_squares_creating_efficiently():
    # create magic squares
    blank_square = []
    for row in range(0, 3):
        row = []
        for column in range(0, 3):
            row.append(None)
        blank_square.append(row)

    possible_squares = []
    for row in range(0, 3):
        for column in range(0, 3):
            blank_square[row][column] = 9
            possible_squares.append([[cell for cell in row] for row in blank_square])
            blank_square[row][column] = None

    old_squares = []
    # start by big numbers to filter magic numbers faster
    for number in range(8, 0, -1):
        old_squares = possible_squares
        possible_squares = []
        for possible_square in old_squares:
            for row in range(0, 3):
                for column in range(0, 3):
                    if possible_square[row][column] is None:
                        # check row validity
                        sum_row = number
                        for j in range(0, 3):
                            if possible_square[row][j] is not None:
                                sum_row += possible_square[row][j]

                        if sum_row < 16:
                            # check column validity
                            sum_column = number
                            for i in range(0, 3):
                                if possible_square[i][column] is not None:
                                    sum_column += possible_square[i][column]

                            if sum_column < 16:
                                possible_square[row][column] = number
                                possible_squares.append(
                                    [[cell for cell in row] for row in possible_square]
                                )
                                possible_square[row][column] = None

    magic_squares = []
    for square in possible_squares:
        square_is_magic = True
        # check sum columns
        for column in range(0, 3):
            if square[0][column] + square[1][column] + square[2][column] != 15:
                square_is_magic = False
        # check sum rows
        for row in range(0, 3):
            if square[row][0] + square[row][1] + square[row][2] != 15:
                square_is_magic = False

        # check sum diagonals
        if square[0][0] + square[1][1] + square[2][2] != 15:
            square_is_magic = False
        if square[0][2] + square[1][1] + square[2][0] != 15:
            square_is_magic = False

        if square_is_magic:
            magic_squares.append(square)

    return magic_squares

  • 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;
}