I didn’t try to use any optimized search algorithm or anything, as I knew that the problem space was very small and specific and that computers are really fast. So I figured I would just write a brute-force iterate through every row and column type of an algorithm (in Big O notation being O(mn) or just O(n2) if the original grid is square), knowing it would return in milliseconds.
I quickly realized that each iteration was not dependent any previous iteration for its calculations, so I decided it might be a good time to try out the new Parallel.For loops in the .NET 4 Framework that would multi-thread the iterations of the loops. Here’s the implementation I threw together:
using System;
using System.Linq;
using System.Threading.Tasks;
namespace Find34Grid
{
public class Program
{
private static readonly int[][] Grid = new []
{
new [] {16,3,2,13,15,10,3,6,41,15,14,4,12,8,7,1,12},
new [] {5,10,22,8,4,5,16,7,9,7,6,12,5,11,10,8,5},
new [] {9,6,7,12,14,11,2,13,16,3,2,13,15,10,3,6,5},
new [] {41,15,14,4,12,8,7,2,5,10,11,8,4,5,16,9,15},
new [] {16,3,2,13,15,10,3,6,15,10,16,2,3,13,16,2,3},
new [] {5,10,11,8,4,5,16,9,4,5,5,11,10,8,5,11,10},
new [] {9,6,7,12,14,11,2,13,14,11,9,7,6,12,9,7,6},
new [] {41,15,14,4,12,8,7,1,12,8,4,14,15,1,14,15,1},
new [] {9,7,6,12,5,11,10,8,5,11,10,3,6,41,15,14,4},
new [] {4,14,15,1,9,7,6,12,9,7,5,16,9,9,7,6,12},
new [] {12,8,13,13,4,14,15,1,4,14,11,2,13,16,3,2,13}
};
private const int MagicSum = 34;
public static void Main(string[] args)
{
Parallel.For(0, Grid.Length - 3, i =>
{
Parallel.For(0, Grid[i].Length - 3, j =>
{
int[] sums = new []
{
Grid[i].Skip(j).Take(4).Sum(), // Row 1
Grid[i+1].Skip(j).Take(4).Sum(), // Row 2
Grid[i+2].Skip(j).Take(4).Sum(), // Row 3
Grid[i+3].Skip(j).Take(4).Sum(), // Row 4
new [] { Grid[i][j], Grid[i+1][j], Grid[i+2][j], Grid[i+3][j]}.Sum(), // Column 1
new [] { Grid[i][j+1], Grid[i+1][j+1], Grid[i+2][j+1], Grid[i+3][j+1]}.Sum(), // Column 2
new [] { Grid[i][j+2], Grid[i+1][j+2], Grid[i+2][j+2], Grid[i+3][j+2]}.Sum(), // Column 3
new [] { Grid[i][j+3], Grid[i+1][j+3], Grid[i+2][j+3], Grid[i+3][j+3]}.Sum(), // Column 4
new [] { Grid[i][j], Grid[i+1][j+1], Grid[i+2][j+2], Grid[i+3][j+3]}.Sum(), // Diagonal 1
new [] { Grid[i][j+3], Grid[i+1][j+2], Grid[i+2][j+1], Grid[i+3][j]}.Sum() // Diagonal 2
};
if (sums.All(x => x == MagicSum))
{
Console.WriteLine("y (row): {0}\nx (column): {1}", i, j);
}
});
});
Console.ReadLine();
}
}
}
Nothing special and certainly did the job. I didn’t really notice a performance improvement in anyway, but that was expected for such a small problem. I don’t really expect a whole lot of feedback on such straightforward code, but if there is a cleaner or more efficient way to utilize Parallel.For or Parallel.ForEach, please don’t hesitate to let me know via commenting to this post. Thanks!
