Project Euler: Problem #11

I’ve been so preoccupied as of late that I’ve completely neglected the website! I’ll try to be a little better in the future. So anyways, I’ve finally got around to posting the answer to Problem 11. It’s not at all a hard problem, in fact, I think the hardest part was filling that pesky multi-dimensional array with the values!

Problem #11:
Description: What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#define LENGTH 20
#define HEIGHT 20
 
int ProblemEleven()
{
  int result = 0;
 
  int g[][LENGTH] = {
    {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,40,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}
  };
 
  // first case : left <-> right
  for ( int i = 0; i < HEIGHT; i++ )
  {
    for ( int j = 0; j < (LENGTH - 3); j++ )
    {
      int temp = g[i][j] * g[i][j+1] * g[i][j+2] * g[i][j+3];
      if ( temp > result )
      {
        result = temp;
      }
    }
  }
 
  // second case : up <-> down
  for ( int i = 0; i < LENGTH; i++ )
  {
    for ( int j = 0; j < (HEIGHT - 3); j++ )
    {
      int temp = g[j][i] * g[j+1][i] * g[j+2][i] * g[j+3][i];
      if ( temp > result )
      {
        result = temp;
      }
    }
  }
 
  // third case : diagonal -> right
  for ( int i = 0; i < (LENGTH - 3); i++ )
  {
    for ( int j = 0; j < (HEIGHT - 3); j++ )
    {
      int temp = g[j][i] * g[j+1][i+1] * g[j+2][i+2] * g[j+3][i+3];
      if ( temp > result )
      {
        result = temp;
      }
    }
  }
 
  // fourth case : diagonal -> left
  for ( int i = LENGTH; i > 3; i-- )
  {
    for ( int j = 0; j < (HEIGHT - 3); j++ )
    {
      int temp = g[j][i] * g[j+1][i-1] * g[j+2][i-2] * g[j+3][i-3];
      if ( temp > result )
      {
        result = temp;
      }
    }
  }
 
  return result;
}
Continue reading » · Rating: · Written on: 11-28-08 · No Comments »

Project Euler: Problem #10

Okay, slightly off topic, but I’ve got to throw this out there. Never, ever, ever write something that people will see when it’s late at night and you’re tired. If you’re me, you will not only incorrectly express your feelings due to your terrible writing skills, but you’ll also make numerous mistakes misrepresenting the facts. That’s what happened bashing on the LC-3 assembly language the other night. To be honest, I’m not sure why I picked on LC-3. I’m going to avoid late night writing altogether. Oh, and Stephen, I wasn’t complaining about the number registers–that’s just silly.

There’s something about Project Euler and prime numbers that just go hand in hand it seems. If you’re ever in doubt in regards with how to solve a problem you’ll probably need to generate some prime numbers. No, seriously. So I’ve been talking about the day I would need to create a prime number sieve and that day has finally come. I decided to go ahead and implement a version of the Sieve of Eratosthenes for this and all future problems requiring me to calculate a list of prime numbers. This thing is insanely fast compared to my previous code examples for generating prime numbers; you can generate the first two million primes in under 2 seconds. If you were feeling (slightly) more adventurous, you could combine this sieve with Wheel Factorization to further optimize the code.

Problem #9:
Description: Find the sum of all the primes below two million.
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <math.h>
 
int* SieveOfEratosthenes( int size )
{
  int* primes = new int[size];
 
  // populate the array with numbers
  for ( int i = 0; i <= size; i++ )
  {
    primes[i] = i;
  }
 
  // one isn't prime... sorry.
  primes[1] = 0;
 
  for ( int i = 2; i <= sqrt(size); i++ )
  {
    if ( primes[i] != 0 )
    {
      for ( int j = (i * i); j <= size; j++ )
      {
        if ( primes[j] != 0 )
        {
          if ( (primes[j] % primes[i]) == 0 )
          {
            primes[j] = 0;
          }
        }
      }
    }
  }
 
  return primes;
}
 
INT64 ProblemTen()
{
  INT64 result = 0;
  int* primes = SieveOfEratosthenes(2000000);
 
  for ( int i = 0; i <= 2000000; i++ )
  {
    if ( primes[i] != 0 )
    {
      result += primes[i];
    }
  }
 
  return result;
}
Continue reading » · Rating: · Written on: 11-19-08 · No Comments »

Project Euler: Problem #9

Ahh, one of the most well-known theorems in math it seems: The Pythagorean theorem. This is a nice and easy problem to solve using a good ol’ brute force algorithm.

Problem #9
Description: Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int ProblemNine()
{
  for ( int a = 1; a <= 1000; a++ )
  {
    for ( int b = 1; b <= (1000 - a); b++ )
    {
      int c = 1000 - (a + b);
      if ( (a * a) + (b * b) == (c * c) )
      {
        return (a * b * c);
      }
    }
  }
}
Continue reading » · Rating: · Written on: 11-17-08 · No Comments »