Daniel Pedigo

As most of you can tell, I’ve been pretty fascinated with Project Euler for quite some time (I have a lot more challenges done than I’ve actually posted).  However, these last few weeks I’ve been neglecting Project Euler and keeping myself busy with a few other “challenge”-type websites that I’ve found.   If any of you are interested in having hours and hours disappear in the blink of an eye, keep reading.  Seriously, I’m not joking.

First up is an amazingly clever riddle website titled Notpron.  Think of this as a no holds barred, anything goes type of riddle.  The first few levels are quite easy, as to give you a grasp on how it works, but they become much harder as you progress. I’ve spent countless hours on Notpron over the last few weeks only to progress to level 18.  There are 140 levels available.  According to the website, only 3 people have been “certified” as having completed all of the levels.  I definitely recommend everyone gives this website a try.

My next recommendation is a website called Bright Shadows.  Bright shadows has many different categories of challenges available in hopes that there will be a category suitable to you.  As most of these challenges require programming experience, I would not recommend this website to anyone that is not at least a little bit familiar with programming concepts.  Some of the categories include: programming, Cryptography, Steganography, logic, and my favorite, cracking.  Regardless, I still give this website an A+ for finally convincing me to whip out a disassembler and “go at it”.

My last recommendation (not because the others are any better) for challenge websites is Project Euler.  This website is based around challenging mathematical/computer programming problems.  Even someone like me, who would rather be doing things that are not math related, should still find this website to be a lot of fun.

Even though I’ve recommended a few websites to check out, there are still many more out there that are a lot of fun.  A few runner-ups include:

• Electrica
• +Ma’s Reversing
• Hack This Site

If any one knows of any other websites similar to these worth mentioning, leave a comment and I’ll add it to the list.

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;
}

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;
}