Project Euler #11 : Largest product in a grid(Brute Force)

This problem is actually hard to find efficient algorithms.  Difficulty rating is 5%.

I tried to solve it using the greed algorithm, but the greed algorithm doesn't always give the best results, but it's hard to expect a speedup because of the sorting time.

Because sorting 400 data itself is basically more asymptotic than it is to compute all the products sequentially. I thought there was nothing to be gained from sorting.

 

The greed algorithm that I first thought is;

It was a way to compute the nearest product in turn, starting with the largest number, and ending there if the current maximum is greater than the next quadratic number.

With this algorithm, we can get the largest multiplier, but I thought it would be efficient.

The greed algorithm that I thought of the second time was to check the order of the largest number in order and find the number of products when four numbers are arranged in a row. .

So in conclusion I thought the best algorithm was to calculate in an ignorant way. Of course, there may be a better algorithm. Even in the ignorant way, the computation time is very small at 0ms.

 

//--------------------------------------------------------------------
//  Project Euler #11 - Largest product in a grid
//    - by Aubrey Choi
//    - created at 2014-12-28
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

void solve1()
{
  char s[] = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 \
  49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 \
  81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 \
  52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 \
  22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 \
  24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 \
  32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 \
  67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 \
  24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 \
  21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 \
  78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 \
  16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 \
  86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 \
  19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 \
  04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 \
  88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 \
  04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 \
  20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 \
  20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 \
  01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
  int v[20*20];
  int c = 0;
  int d[4] = { 1, 20, 21, 19 };

  for( char *p = strtok(s, " \n") ; p ; p = strtok(0, " \n") )
  {
    v[c++] = atoi(p);
  }
  
  int max = 0;
  for( int i = 0 ; i < 20 ; i++ )
  {
    for( int j = 0 ; j < 20 ; j++ )
    {
      int u = i*20 + j;
      if( j < 20-3 )
      {
        int c = 1;
        for( int k = 0 ; k < 4 ; k++ ) c *= v[u+d[0]*k];
        if( max < c ) max = c;
      }
      if( i < 20-3 )
      {
        int c = 1;
        for( int k = 0 ; k < 4 ; k++ ) c *= v[u+d[1]*k];
        if( max < c ) max = c;
      }
      if( i < 20-3 && j < 20-3 )
      {
        int c = 1;
        for( int k = 0 ; k < 4 ; k++ ) c *= v[u+d[2]*k];
        if( max < c ) max = c;
      }
      if( i < 20-3 && j >= 3 )
      {
        int c = 1;
        for( int k = 0 ; k < 4 ; k++ ) c *= v[u+d[3]*k];
        if( max < c ) max = c;
      }
    }
  }
  printf("Ans = %d\n", max);
}

int main()
{
  clock_t t;

  t = clock();
  solve1();
  printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

  return 0;
}