unexpected call

Project Euler problem 11~

  1: class Program
  2:     {
  3:         // alt+select for vertical selection for massive comma insert ftw!
  4:         static readonly int[][] mapJagged = new int[20][] 
  5:         { 
  6:             new int[] {08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08},
  7:             new int[] {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00},
  8:             new int[] {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65},
  9:             new int[] {52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91},
 10:             new int[] {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
 11:             new int[] {24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
 12:             new int[] {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
 13:             new int[] {67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21},
 14:             new int[] {24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
 15:             new int[] {21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95},
 16:             new int[] {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92},
 17:             new int[] {16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57},
 18:             new int[] {86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
 19:             new int[] {19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40},
 20:             new int[] {04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
 21:             new int[] {88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
 22:             new int[] {04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36},
 23:             new int[] {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16},
 24:             new int[] {20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54},
 25:             new int[] {01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48}
 26:         };
 27: 
 28:         static void Main(string[] args)
 29:         {
 30:             var sw = new Stopwatch();
 31: 
 32:             Console.WriteLine("The greatest product of four adjacent numbers in any direction");
 33:             sw.Start();
 34:             var sum1 = AllDirection();
 35:             sw.Stop();
 36:             Console.WriteLine(string.Format("plain loop brute force way(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 37: 
 38:             sw.Reset();
 39:            
 40:             Console.WriteLine("Press any key to exit");
 41:             Console.ReadKey();
 42:         }
 43: 
 44:         /// <summary>
 45:         /// so basically this method calculate horizentally, vertically
 46:         /// diagonally (\) and {/)
 47:         /// nothing special i guess
 48:         /// maybe i should try multi-dimensional array instead of jagged array
 49:         /// read it somewhere there is a speed difference between(sigh, couldnt find the link anymore)
 50:         /// i guess all four check can be done parallel, but since the whole time takes only 1500ish tick
 51:         /// probablly a lot faster than spin up a thread(or even the time to queue up the work in threadpool)
 52:         /// </summary>
 53:         /// <returns>greatest product</returns>
 54:         static int AllDirection()
 55:         {
 56:             var max = 0;
 57:             var cur = 0;
 58:             var len = 20;
 59:             for (int i = 0; i < len; i++)
 60:             {
 61:                 for (int j = 0; j < len; j++)
 62:                 {
 63:                     if (j + 3 < len)
 64:                     {
 65:                         // Vertical
 66:                         cur = mapJagged[j][i] * mapJagged[j + 1][i] * mapJagged[j + 2][i] * mapJagged[j + 3][i];
 67:                         if (cur > max)
 68:                             max = cur;
 69: 
 70:                         // Horizental
 71:                         cur = mapJagged[i][j] * mapJagged[i][j + 1] * mapJagged[i][j + 2] * mapJagged[i][j + 3];
 72:                         if (cur > max)
 73:                             max = cur;
 74:                     }
 75: 
 76:                     if (j + i + 3 < len)
 77:                     {
 78:                         // Diagonally from Top Left (\)
 79:                         cur = mapJagged[j + i + 0][j + 0]
 80:                             * mapJagged[j + i + 1][j + 1]
 81:                             * mapJagged[j + i + 2][j + 2]
 82:                             * mapJagged[j + i + 3][j + 3];
 83:                         if (cur > max)
 84:                             max = cur;
 85: 
 86:                         cur = mapJagged[j + 0][j + i + 0]
 87:                             * mapJagged[j + 1][j + i + 1]
 88:                             * mapJagged[j + 2][j + i + 2]
 89:                             * mapJagged[j + 3][j + i + 3];
 90:                         if (cur > max)
 91:                             max = cur;
 92: 
 93:                         //Diagonally from Top Right (/)
 94:                         cur = mapJagged[j + i + 0][len - j - 1]
 95:                             * mapJagged[j + i + 1][len - j - 2]
 96:                             * mapJagged[j + i + 2][len - j - 3]
 97:                             * mapJagged[j + i + 3][len - j - 4];
 98:                         if (cur > max)
 99:                             max = cur;
100: 
101:                         cur = mapJagged[j + 0][len - j - i - 1]
102:                             * mapJagged[j + 1][len - j - i - 2]
103:                             * mapJagged[j + 2][len - j - i - 3]
104:                             * mapJagged[j + 3][len - j - i - 4];
105:                         if (cur > max)
106:                             max = cur;
107:                     }
108:                 }
109:             }
110: 
111:             return max;
112:         }
113:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s