ProjectEuler Problem 8

No posts in a long time, but this will now become a blog about projecteuler :) This problem was very easy to do in C++ (Or any other language). Just throw the big number into a string and get substrings of it. here it is:

#include
#include
using namespace std;

int main() {

    string big_number = "7316717...........52963450";

    unsigned long long biggest = 0;
    unsigned long long test_biggest = 0;

    for(int i=0; i        string convert_me = big_number.substr(i, 5); //Get the substring


        for(int j=0; j<5; j++) {
            if(convert_me[j]-'0' == 0)
                break;

            if(test_biggest == 0) {
                test_biggest = convert_me[j]-'0';
                continue;
            }

            test_biggest *= convert_me[j]-'0';

            if(j==4)
                biggest = ( (test_biggest > biggest) ? test_biggest : biggest);
        }

        test_biggest = 0;
    }

    cout << biggest << endl;
    return 0;
}

time: 0.002s



Optimizations would be simple but not needed as its such a simple problem. (e.g, increment i by 4 if it finds a zero)

      --NotMyFault

Project Euler Problem 11 in C

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

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

    So the main problem I had here was how to deal with such a huge amount of numbers! I decided to put them in an array but there was a problem there too. All the single digit numbers in the grid were prefixed by a zero so the grid would keep its nice square shape. This caused a major headache for me as a number prefaced by a zero is considered octal in C and C++! So after deleting all the 0's I was set.

    Next thing I did was make the code to search through all the numbers looking for the highest multiples. This wasn't too hard but I ran into a bit of bother with the array indexing. Anywhoo, here's my code:

#include 

int main()
{

    int array[20][20]=
    {
{ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
{52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 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,  3, 45,  2, 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,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
{24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
{16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
{86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
{ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
{20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
{ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48},
    };

    unsigned long long highest=0;
    unsigned long long test=0;

    int one=0;
    int two=0;
    int three=0;
    int four=0;

    int i=0;
    int j=0;

    //check for horizontal highest//
    for(i=0; i<20; i++)
    {

        for(j=0; j<17; j++)
        {
            test=(array[i][j]*array[i][j+1]*array[i][j+2]*array[i][j+3]);

            if(test>highest)
            {
                highest=test;

                one=array[i][j];
                two=array[i][j+1];
                three=array[i][j+2];
                four=array[i][j+3];
            }

        }//end of j for loop

    }//end of i for loop


    //test for vertical highest//
    for(i=0; i<17; i++)
    {

        for(j=0; j<20; j++)
     {

            test=(array[i][j]*array[i+1][j]*array[i+2][j]*array[i+3][j]);

            if(test>highest)
            {
                highest=test;
                one=array[i][j];
                two=array[i+1][j];
                three=array[i+2][j];
                four=array[i+3][j];
            }

     }//end of j for loop

    }//end of i for loop


    //check for diagonal-right highest//
    for(i=3; i<20; i++)
    {

        for(j=0; j<17; j++)
        {

        test=(array[i][j]*array[i-1][j-1]*array[i-2][j-2]*array[i-3][i-3]);

            if(test>highest)
            {
                highest=test;
                one=array[i][j];
                two=array[i-1][j-1];
                three=array[i-2][j-2];
                four=array[i-3][j-3];
            }

        }//end j for loop

    }//end i for loop


    //check for diagonal-left highest//
    for(i=0; i<17; i++)
    {

        for(j=0; j<17; j++)
        {

        test=(array[i][j]*array[i+1][j-1]*array[i+2][j-2]*array[i+3][j-3]);

            if(test>highest)
            {
                highest=test;
                one=array[i][j];
                two=array[i+1][j-1];
                three=array[i+2][j-2];
                four=array[i+3][j-3];
            }

        }//end j for loop

    }//end i for loop


    printf("%d\n", highest);

    return 0;
}

Execution Time: 0.157 s



    Yes, it's horribly un-optimized but it does the job! That's all for now.
       NotMyFault

Project Euler Problem 5 in C

    I'm surprised that everyone doesn't get this. It's very simple, doesn't take a lot of time to code and shouldn't take too long to run. Here's the problem:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

    So nice and easy. Here's my solution in C. It only took 20 lines :D

#include <stdio.h>

int main()
{

   int i=1;

   while(1)
   {
      if(i%11==0 && i%12==0 && i%13==0 
         && i%14==0 && i%15==0 && i%16==0 
         && i%17==0 && i%18==0 && i%19==0 
         && i%20==0) 
      {
          printf("%d\n", i);
          return 0;
      }

      i++;
   }

return 0;
}

Execution Time: 1.859 s

    The execution time is horribly slow so if anyone wants to comment on how to make it quicker, be my guest!
       NotMyFault

Project Euler Problem 4 in C

    So I've finished another one! This time it's problem number 4. Here's the problem for those of you un-familiar with Project Euler:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

    Not too hard. I tried to this a bit different and more optimized than when I did this problem in C++ so here's what I came out with:

#include <stdio.h>
#include <string.h>

int isPalindrome(const int *pTest)
{
    char string[6];
    int length=0;

    sprintf(string, "%d", (*pTest) );
    length=strlen(string);

    switch(length)
    {
        case 5:
        if(string[0]==string[4] && string[1]==string[3])
            return 1;

        case 6:
    if(string[0]==string[5]&&string[1]==string[4]&&string[2]==string[3])
            return 1;

        default:
            return 0;
    };  //End of switch statment

    return 0;
}

int main()
{
    int test=0;
    int *pTest=&test;
    int highest=0;
    int *pHighest=&highest;
    int i=0;
    int j=0;

    for(i=1000; i>100; i--)
    {
        for(j=1000; j>100; j--)
        {
            test=i*j;

            if(isPalindrome(pTest) && (*pTest)>(*pHighest) )
            {
                highest=i*j;
            }
        }
    }

    printf("%d\n", highest);
    return 0;
}

Execution Time: 0.485 s



    So what I did was had 2 nested for loops and sent the product of the two ints (i and j) to the function isPalindrome() Then I used sprinf() to change the int to a string which I found the length of and checked if it was a palindrome or not.
    So there you have it, Project Euler problem 4.
       NotMyFault

Project Euler Problem 7 in C

    ProjectEuler once more! In my opinion, it's logical to do this problem before Problem 3 as Problem 3 requires prime numbers too. Also, Problem 3 has the issue of it being an awkward problem due to the high number... Anyways, here's the Problem:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?

    And here's my code:

#include <stdio.h>
#include <math.h>

int isPrime(int test)
{
    int calculateTo = (int) sqrt(test);

    for(int i=3; i<=calculateTo; i+=2)
    {
        if(test%i==0)
            return 0;
    }

    return 1;
}

int main()
{
    int howHigh=10001;
    int counter=1;

    while (1)
    {
        for(int i=3; ; i+=2)
        {
            if( isPrime(i) )
                counter++;

            if(counter==howHigh)
            {
                printf("%d\n", i);
                return 0;
            }
        }

    }

    return 1;
}

Execution Time: 0.187 s

    Not too shabby in my opinion! So that's just about it.
       NotMyFault

Project Euler Problem 2 in C

    So ProjectEuler once again. This time it's problem two. Problem is:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

    So it involves going up to 4 million... that was a bit confusing. Originally, I had an array of ints (int fib[4000000]) but that didn't last too long as every time I ran it it would crash. To get around that, I lowered the figure down until it was still reaching all the fibonacci series below 4,000,000 but wasn't going to crash the program. So here's the code:

#include <stdio.h>

int main()
{
    long int fib[400000]={400000, 0};
    long int total=2; //fib[1] is not added as the loop starts at fib[2]
    int i=0;

    fib[0]=1;
    fib[1]=2;

    for(int i=2; i<=400000; i++)
    {
        fib[i]=fib[i-2]+fib[i-1];
        if(fib[i]>4000000)
            goto end;
        if(fib[i]%2==0)
            total+=fib[i];
    }

end:
    printf("%d\n", total);
    return 1;
}

Execution time: 0.171 s

    Yeah, yeah. I know. Don't use goto but it was just so handy! again, all comments welcome.
       NotMyFault

Project Euler Problem 1 in C

    I enjoy the Project Euler problems. I've never asked for help even though I've struggeled a lot at them. Even still I've only done ~10 in my preferred language, C++. I'm now learning a little C and I've decided that Project Euler would be a great place to practise what I've learned. So here's my solution to problem 1 in C:

#include <stdio.h>

int main(void)
{
    int total=0;
    int i=0;

    while(i<1000)
    {
        if(i%3==0 || i%5==0)
            total+=i;
        i++;
    }

    printf("%d", total);
}

Execution time: 0.042 s


    That's all then. I'll post up my solutions to the other problems as I finish them. All comments welcome.
       NotMyFault