Forming a Magic Square
Forming a Magic Square
+ 0 comments this is my solution in c++, hope anyone can optimal it
#include<iostream> #include<math.h> using namespace std; int main() { int arr[3][3]={0}; int arr1[9] = {8, 3, 4, 1, 5, 9, 6, 7, 2}; int arr2[9] = {6, 1, 8, 7, 5, 3, 2, 9, 4}; int arr3[9] = {2, 7, 6, 9, 5, 1, 4, 3, 8}; int arr4[9] = {4, 9, 2, 3, 5, 7, 8, 1, 6}; int arr5[9] = {6, 7, 2, 1, 5, 9, 8, 3, 4}; int arr6[9] = {2, 9, 4, 7, 5, 3, 6, 1, 8}; int arr7[9] = {8, 1, 6, 3, 5, 7, 4, 9, 2}; int arr8[9] = {4, 3, 8, 9, 5, 1, 2, 7, 6}; int count1 = 0; int count2 = 0; int count3 = 0; int count4 = 0; int count5 = 0; int count6 = 0; int count7 = 0; int count8 = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cin >> arr[i][j]; } } int arrTemp[9]={0}; int m = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { arrTemp[m] = arr[i][j]; m++; } } for (int i = 0; i < 9; i++) { count1 += abs(arrTemp[i] - arr1[i]); count2 += abs(arrTemp[i] - arr2[i]); count3 += abs(arrTemp[i] - arr3[i]);`` count4 += abs(arrTemp[i] - arr4[i]); count5 += abs(arrTemp[i] - arr5[i]); count6 += abs(arrTemp[i] - arr6[i]); count7 += abs(arrTemp[i] - arr7[i]); count8 += abs(arrTemp[i] - arr8[i]); } cout << min(count1, min(count2, min(count3, min(count4, min(count5, min(count6, min(count7, count8))))))); return 0; }
+ 0 comments This is my java 8 (15) solution, feel free to ask me any questions.
follow these steps:
1. Find all permutations of 9 objects taken 3 which has sum is 15.
2. From the first step, find out all permutaions matrix square 3 x 3.
3. Filter all permutations matrix squares and occumulate magic squares 3 x 3.
4. Calculate minimum cost.public static int formingMagicSquare(List<List<Integer>> s) { int minimumCost = Integer.MAX_VALUE; // Build up 3x3 magic square List<List<List<Integer>>> magicSquares = findAllMagicSquare(9, 3, 15); // Calculate minimum cost for (List<List<Integer>> magicSquare : magicSquares) { int cost = calculateReplacementCost(s, magicSquare); // Update minimum cost if(cost < minimumCost) { minimumCost = cost; } } return minimumCost; }
private static List<List<List<Integer>>> findAllMagicSquare(int n, int k, int desiredSum) { // Construct all matrix K x K List<List<List<Integer>>> squares = permuteSquares(n, k, desiredSum); // Create a array list to store all magic squares List<List<List<Integer>>> magicSquares = new ArrayList<>(); // Iterate through each squares to find valid magic squares for(List<List<Integer>> square : squares) { if(isMagicSquare(square)) { magicSquares.add(square); } } return magicSquares; }
private static List<List<List<Integer>>> permuteSquares(int n, int k, int desiredSum) { // Construct all possible permutations N objects taken K List<List<Integer>> rows = permute(n, k, desiredSum); // Create convenient collections List<List<Integer>> current = new ArrayList<>(); List<List<List<Integer>>> results = new ArrayList<>(); boolean used[] = new boolean[rows.size() + 1]; // Construct all permutaions of rows taken K (squares), // store into results list permuteSquaresHelper(k, used, rows, current, results); return results; }
private static void permuteSquaresHelper(int k, boolean[] used, List<List<Integer>> rows, List<List<Integer>> current, List<List<List<Integer>>> results) { // Base case: if k is 0, add current into results if(k == 0) { results.add(new ArrayList<>(current)); return; } // Recursive case int n = rows.size(); for(int i = 0; i < n; i++) { if(!used[i]) { List<List<Integer>> updatedCurrent = new ArrayList<>(current); updatedCurrent.add(rows.get(i)); used[i] = true; permuteSquaresHelper(k - 1, used, rows, updatedCurrent, results); used[i] = false; //backtracking } } }
/** * Find all permutaions n items taken k having sum is desired sum, * in range [1:N] * * @param n Last value to permute * @return List of generated permutaions */ private static List<List<Integer>> permute(int n, int k, int desiredSum) { List<List<Integer>> results = new ArrayList<>(); List<Integer> current = new ArrayList<>(); boolean used[] = new boolean[n + 1]; permuteHelper(n, k, desiredSum, used, current, results); return results; }
private static void permuteHelper(int n, int k, int desiredSum, boolean used[], List<Integer> current, List<List<Integer>> results) { // Basecase: if k is 0 store current into results if(k == 0) { // Calculate sum of current list int sum = 0; for (int num : current) { sum += num; } if (sum == desiredSum) { results.add(new ArrayList<>(current)); } return; } // Recursive case: for(int i = 1; i <= n; i++) { if(!used[i]) { current.add(i); used[i] = true; permuteHelper(n, k - 1, desiredSum, used, current, results); used[i] = false; //backtrack current.remove(current.size() - 1); } } }
private static boolean isMagicSquare(List<List<Integer>> matrix) { // If the given matrix isn't contained unique integers // then return false. if(!isAllUniqueSquare(matrix)) { return false; } // Get the size of the given matrix (assuming it's square) int n = matrix.size(); // Sum of the first row (initial value) int desiredSum = matrix.get(0).stream().reduce(Integer::sum).orElse(0); // Check horizontal sums for (List<Integer> row : matrix) { int rowSum = row.stream().reduce(Integer::sum).orElse(0); if (rowSum != desiredSum) { return false; } } // Check vertical sums for (int col = 0; col < n; col++) { int colSum = 0; for (int row = 0; row < n; row++) { colSum += matrix.get(row).get(col); } if (colSum != desiredSum) { return false; } } // Check the main diagonal sum (top-left to bottom-right) int mainDiagonalSum = 0; for (int i = 0; i < n; i++) { mainDiagonalSum += matrix.get(i).get(i); } if (mainDiagonalSum != desiredSum) { return false; } // Check the secondary diagonal sum (top-right to bottom-left) int secondaryDiagonalSum = 0; for (int i = 0; i < n; i++) { secondaryDiagonalSum += matrix.get(i).get(n - i - 1); } if (secondaryDiagonalSum != desiredSum) { return false; } // If all checks pass, the given matrix is a magic square return true; }
/** * This method validates the given square matrix is * unique integers or not * * @param List of integers that represents rows of * a square. * @return Return false if the matrix doesn't contain * unique elements, * Otherwise return true. */ private static boolean isAllUniqueSquare(List<List<Integer>> square) { Set<Integer> set = new HashSet<>(); for(List<Integer> row : square) { set.addAll(row); } return square.size()*square.size() == set.size(); }
/** * Calculate replacement cost of a square matrix and * a square magic. * * @param matrix List of list integers that represents * matrix rows. * @param squareMagic List of list integers that represents * square magic rows. */ private static int calculateReplacementCost(List<List<Integer>> matrix, List<List<Integer>> squareMagic) { int cost = 0; int numberOfRows = matrix.size(); int numberOfCols = matrix.get(0).size(); //Iterate through all given matrix items to calculate //replacement cost. for(int row = 0; row < numberOfRows; row++) { for(int col = 0; col < numberOfCols; col++) { //Get the value from matrix int value = matrix.get(row).get(col); //Get the value from magic square int magic = squareMagic.get(row).get(col); if(value != magic) { cost += Math.abs(value - magic); } } } return cost; }
+ 0 comments Here's java code. All you need is to remember one magic square...
- then derive 3 more squares by rotating it in clockwise direction.
- Then take transpose of any of the magic square, that'll be your 5th magic square
- now to obtain 3 more magic squares, rotate the 5th magic square 3 more times.
- Now traverse in each magic square and calculate the cell difference
- store the minimum difference you get
- return that minimum difference
public static int formingMagicSquare(List<List<Integer>> s) { // Write your code here int[][][] magicSquares = { {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}}, {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}}, {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}}, {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}}, {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}}, {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}}, {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}}, {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}} }; int minCost = Integer.MAX_VALUE; for (int[][] magicSquare : magicSquares) { int cost = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cost += Math.abs(s.get(i).get(j) - magicSquare[i][j]); } } minCost = Math.min(minCost, cost); } return minCost; }
+ 0 comments hey can someone help me out with this problem? im new to competitive programming and my friend sent me this. he wants me to solve it but as i said, im still new so can yall teach me? here is the problem https://www.hackerrank.com/newbie-challenge
+ 2 comments I have a genuine doubt and I think it is valid, there is a hidden test case in this problem which is given as,
4 5 8 2 4 1 1 9 7
and we can do the calc and replace a few elements and get the magic square as,
5 6 8 3 4 2 1 9 7
Where we are changing |1-2| = 1 +|2-3|=1 + |4-5| = 1+ |5-6|=1 = 4 So, by 4 units of cost we will be able to make the given square as a magic square but the answer for the test case is given as 14. What am I missing here?! Or is my question valid?!
Sort 1132 Discussions, By:
Please Login in order to post a comment