Project Euler, Problem 6 solution

Problem 6

OK, just the code without any clarifications because no one reads my blog.

JavaScript (SpiderMonkey):

var n = 100;
var sqsum = (n * (n + 1) * (2 * n + 1)) / 6;
var sumsq = (1 + n) * n / 2;
print(sumsq*sumsq - sqsum);

('n' is here just for clarity of formula)

(time: 0.02s memory: 4984 kB on usual PC)

Congratulations, the answer you gave to problem 6 is correct.
You are the 132085th person to have solved this problem.

UPDATED:
krewllobster has also offered an interesting and fast option:

var a = 0, b = 0, x = 1;
while (x < 101) {
    a += Math.pow(x,2);
    b += x;
    x += 1;
}
print(Math.pow(b,2) - a);

(time: 0.01s memory: 4984 kB)

Project Euler, Problem 16 solution

Problem 16

I like Free Software Foundation, Inc.
I like to use the right tool for the right job too.
So to get the number I typed 'bc' in the Linux command line and then '2^1000'.
Well, now I am ready to calculate the sum via JavaScript (SpiderMonkey):

 
var a="copypasted value from my command line as STRING";
var sum = 0;
for(var i = a.length - 1; i > -1; --i) sum += parseInt(a.charAt(i));
print(sum);

(time: 0.02s memory: 4984 kB on usual PC)

Congratulations, the answer you gave to problem 16 is correct.
You are the 70718th person to have solved this problem.

Project Euler, Problem 15 solution

Problem 15

"Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20×20 grid?"

This problem is about permutations and so called central binomial coefficient (the binomial theorem you must remember from the school). And do you remember the Pascal's triangle? If not, check it here. (If you still don't understand what I am talking about you can see the complete solution here).
All you need is to observe that for a NxN grid there are (2n)!/(n!)² possible ways of getting from one corner to the other one and in our case it will be 40!/(20!)². If you are still unable to calculate it you can use A000984.
But if you still want to get the answer by yourself, do not rush to crack factorials with your lovely brute force with 350 lines of C++ code, let's start from... little cheat.
We have some ways for cheat.
Of course we could use the J language to get the central binomial coefficient:
(! +:) 20x
or even more shorter:
20!40x
but it isn't real cheat. There is a better way: http://www.google.com/search?q=40+choose+20
Bingo? Btw. tell me truth, did you know that the Google calculator has the operator 'choose'? Brilliant, isn't? You just command "40 choose 20" and Google gives you the answer: please, master! Try the same way to ask Google for money ;)

Well, now let's start thinking.

Rudy Penteado from Brazil codes in Assembler language. He discovered that:
"This is what I find 2 months ago when I solved it:
Each movement in the horizontal is a zero.
Each movement in the vertical is a one.
1st binary# in this series:
0000000000000000000011111111111111111111
last:
1111111111111111111100000000000000000000
For the numbers in between, the amount of zeros should be the same as ones.
In other words, the ones and zeros have to be rearranged."

Easy, isn't? Try to code this in Assembler.
I won't. I did my solution with some magic too:

JavaScript (Spidermonkey)

var ans = 1;
for(var c = 40, d = 1; c > 20; --c, ++d) ans = (ans * c)/d;
print(ans);

// time: 0.02s memory: 4984 kB

Congratulations, the answer you gave to problem 15 is correct.
You are the 53180th person to have solved this problem.

Project Euler, Problem 8 solution

"Problem 8
Find the greatest product of five consecutive digits in the 1000-digit number."

Well, this problem can be solved even without computer.
Just use the best tool that you never had: your brain ;)
Use the "Find" command in your favorite text editor to highlight all 9 in the given 1000-digit number.
Is it not easy to find a combination of 99879?

But if you wanna code:

JavaScript (Spidermonkey)

var initial = [the given 1000-digit number as array of integers];
var answer = 0;
var sum = 0;
var bestsum = 0;
var tarr = [5];
for(var c = initial.length - 1; c --> 3;) {
    sum = 0;
    for(var s = c; s > c-5; --s)
        sum += initial[s];

    if(sum > bestsum) {
        bestsum = sum;
        for(var j = c, i = 4; j > c-5; --j, --i)
            tarr[i] = initial[j];
    }
}
answer = tarr[0] * tarr[1] * tarr[2] * tarr[3] * tarr[4];
print(answer);

Project Euler Solutions

Wow, the superman named Luckytoilet has collected the huge amount of Project Euler solutions (although there are mostly not solutions but answers)
If the link above is broken, try this one.

A little bit more about yourmyself

You I know a lot, but not well.

Swapping Two Variables

Well, after I get bored from something like this:

function swapTwoVariables(a, b) {
    var temp = a;
    b = a;
    a = temp;
    return [a, b];
}

I decided to recover in my mind how it can be done more nicely.
OK, right now I remember four ways (in pseudocode):

1) old good XOR:
A = 1, B = 9;
A = A xor B;
B = A xor B;
A = A xor B;

2) suppose we have no XOR in our programming language:
A = 1, B = 9;
A -= B += A -= B = -B;

3) probably you know the XCHG command

4) in some modern languages we can do:
[A, B] = [B, A]

Sure, not only Integers can be swapped in such a ways but some other types too.
If you know how to do it some other way, tell me, please.

Project Euler, Problem 7 solution

( http://projecteuler.net/problem=7 )
"Problem 7
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?"

Sure, I've written my stupid solution in C.
But after that I've discovered that the solution in J language can be done only with ONE line of code:

p: 10000

Amazing!

Btw. here is the C solution:

#include <stdio.h>
int main() {
    const int max = 10001;
    int count = 0;
    unsigned int i, j;

    for(i = 2; ; i++) {
        for(j = 2; j < i; j++) {
            if(i % j == 0)
                break;
        }
        if(i == j) {
            count++;
            if(count == max)
                break;
        }
    }
    printf("%dst prime number is: %d\n", max, i);
}

A little bit about myself

Well, I rarely write in my blog since most of the time I spend in SEOquake project. Although there is written "SEOquake TEAM", probably the most interesting feature of these web browser extensions is that they are developed and maintained by only one person (btw, the Opera version just sux). Only occasionally some people are helping me by digging into users feedback, translating the labels and texts into real English etc. (because my native language is not English but Russian, of course :). I'm just doing my job: coding. And because my job is not the focus of my interests, sometimes I write in this blog about some interesting (for me) things. Just to not forget. If you like some posts, feel free to comment and discuss them: it will be very pleasant to me.

Defence of a Kingdom

( http://www.spoj.pl/problems/DEFKIN/ )

ACHTUNG: there are as usual some underwater shitstones by SPOJ lamers, the test input file seems to be containing some garbage symbols etc. So we are forced to write in damned C++ (with sets).

#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>

using namespace std;

int cases, n, h, w, x, y, i, j, bestx, besty, dist, prev;
set<int> xs, ys;
set<int>::iterator it;
char scheisse;

int main() {
    scanf("%d%c", &cases, &scheisse);
    while(cases--) {
        scanf("%d %d %d%c", &w, &h, &n, &scheisse);
        for(i = 0; i < n; i++) {
            scanf("%d %d%c", &x, &y, &scheisse);
            xs.insert(x);
            ys.insert(y);
        }
        xs.insert(w+1), ys.insert(h+1);
        bestx = besty = 0;

        prev = 0;
        for(it = xs.begin(); it != xs.end(); it++) {
            dist = (*it) - prev - 1;
            bestx = max(dist, bestx);
            prev = (*it);
        }

        prev = 0;
        for(it = ys.begin(); it != ys.end(); it++) {
            dist = (*it) - prev - 1;
            besty = max(dist, besty);
            prev = (*it);
        }
        printf("%d\n", (bestx*besty));

        xs.clear(), ys.clear();
    }
}

Divisor Summation

( http://www.spoj.pl/problems/DIVSUM/ )

#include <stdio.h>
#include <math.h>
int main() {
    long long int n,i,t,d,k,l;
    scanf("%lld",&t);
    while(t--) {
        d = 0;
        scanf("%lld",&n);
        k = sqrt(n);
        for(i = 1; i <= k; i++) {
            if((n%i) == 0) {
                d = d+i;
                l = n/i;
                if(i != l)
                    d = d+l;
            }
        }
        printf("%lld\n",d-n);
    }
    return 0;
}

Factorial

( http://www.spoj.pl/problems/FCTRL/ )

C99 strict:

#include <stdio.h>
// gcc factorial.c -std=c99 -time -o factorial_c99
int zeta(int n) {
    int ret = 0;
    for(int p = 5; p <= n; p*=5)
        ret += n/p;
    return ret;
}

int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        printf("%d\n", zeta(n));
    }
    return 0;
}

JavaScript (Rhino):

ACHTUNG: this code perfectly runs at http://www.ideone.com/, but not by SPOJ lamers.

importPackage(java.io);
importPackage(java.lang);
 
var reader = new BufferedReader( new InputStreamReader(System['in']) );
var t = reader.readLine();
var num = null;

function zeta(n) {
    var ret = 0;
    for(var p = 5; p <= n; p *= 5)
        ret += parseInt(n/p);
    return ret.toString();
}

while(t--) {
    num = reader.readLine();
    if(!num)
        break;

    System.out.println( zeta(num) );
}

Number Steps

( http://www.spoj.pl/problems/NSTEPS/ )

//#include <cstdio> // decomment to compile as C++
// g++ number_steps.c -time -o number_steps_cpp
#include <stdio.h>
// gcc number_steps.c -time -o number_steps_c
// gcc number_steps.c -std=c99 -time -o number_steps_c99

int main() {
    int t,a,b;
    scanf("%d ",&t);
    while(t--) {
        scanf("%d %d", &a, &b);
        if(a!=b && a-b!=2) {printf("No Number\n");continue;}
        if(a%2==0 && b%2==0) printf("%d\n", a+b);
        else printf("%d\n", a+b-1);
    }
    return 0;
}

Adding Reversed Numbers

( https://www.spoj.pl/problems/ADDREV/ )

//#include <cstdio> // to compile as C++
#include <stdio.h>

int rev(int num) {
    int res = 0;
    while(num > 0) {
        res = res*10 + num%10;
        num /= 10;
    }
    return res;
}

int main() {
    int cases, x, y;
    scanf("%d", &cases);
    while(cases--) {
        scanf("%d %d", &x, &y);
        printf("%d\n", rev(rev(x)+rev(y)));
    }
    return 0;
}

Small factorials

( http://www.spoj.pl/problems/FCTRL2/ )

%% for SPOJ lamers use -module(tested).
-module(small_factorials).
-export([main/0]).

main() -> 
    {ok, [No_of_cases]} = io:fread( "", "~d" ), 
    loop(No_of_cases). 

loop(0) ->
    %%halt(1).
    done;
loop(No_of_cases) -> 
    {ok, [Number]} = io:fread("", "~d"), 
    ResultFactorial = find_factorial( Number, 1 ), 
    io:format( "~p~n", [ResultFactorial] ), 
    loop( No_of_cases - 1 ).

find_factorial( 0, Product ) -> 
    Product; 
find_factorial( Number, Product ) -> 
    find_factorial( Number-1, Product * Number ).

Size Contest

( https://www.spoj.pl/problems/SIZECON/ )

#include <stdio.h>
int a,s;
int main(n){
    for(scanf("%d",&a);
        a--;
        scanf("%d",&n),
        s+=(n>0)*n);
    printf("%d",s);
return 0;
}

Harry and big doughnuts

( http://www.spoj.pl/problems/DOUGHNUT/ )

Erlang:

%%for SPOJ lamers use -module(tested).
-module(doughnut).
-export([main/0]).

main() ->
    {ok,[Count]} = io:fread("", "~d"),
    loop(Count).

loop(Count) ->
    case io:fread( "", "~d ~d ~d" ) of
    {ok,[C,K,W]} ->
        if
        C * W =< K ->
            io:fwrite("~s~n", [yes]);
        true -> 
            io:fwrite("~s~n", [no])
        end,
     
        if
        Count > 1 ->
            loop(Count-1);
        true ->
            done
        end;

    eof ->
        done
    end.

C/C++:

#include <stdio.h> // compile as C
//#include <cstdio> // decomment to compile as C++
int main() {
    int t, c, k, w;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d %d", &c, &k, &w);
        if(c*w <= k) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

Brainf F##k Writing

(http://www.spoj.pl/problems/BFWRITE/)
++++++++++[>++++++++>+++>++++++++++>+++++++++++<<<<-]>+++.---.-.-----.>++.>+++++.>+++++.<<.>.>-----.<-----.+..-.<.>---.>+++++++++.<++++.>----.----.--.<.

Project Euler, Problem 4 solution

(http://projecteuler.net/problem=4)
"Problem 4
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."

#include <stdio.h>
#include <stdbool.h>

bool is_palindrome(unsigned int const num) {
    unsigned int res = 0;
    unsigned int n = num;
    while(n > res) {
        res = res*10 + n%10;
        n /= 10;
    }
    return n == res;
}

int main() {
    int i, j, c = 0;
    unsigned int res = 0;
    /*
    The palindrome can be written as:
        abccba
    Which then simpifies to:
        100000a + 10000b + 1000c + 100c + 10b + a 
    And then:
        100001a + 10010b + 1100c
    Factoring out 11, you get:
        11(9091a + 910b + 100c)
    So the palindrome must be divisible by 11.
    Seeing as 11 is prime, at least one of the numbers 
    must be divisible by 11.
    So brute force only with less numbers to be checked:
    lets iterate only through the highest 100
    */
    for(i = 999; i > 899; --i) {
        for(j = 999; j > 899; --j) {
            res = i*j;
            ++c;
            if(is_palindrome(res)) {
                printf("\nThe largest palindrome is %d \
                    \nIs product of %d and %d \
                    \nDetected at iteration %d\n\n", \
                    res, i, j, c);
                i = 899;
                break;
            }
        }
    }
    return 0;
}

P.S.: If the memory consumption is the cornerstone for you, feel free to experiment with variable types.

UPDATE from 06 May 2012:

There is something wrong with 'is_palindrome' method.
I did a simple test:

#include <stdio.h>
#include <stdbool.h>
bool is_palindrome(unsigned int const num) {
    unsigned int res = 0;
    unsigned int n = num;
    while(n > res) {
        res = res*10 + n%10;
        n /= 10;
    }
    return n == res;
}

int main() {
    int i;
    for(i = 100; i < 600; ++i) {
        if(is_palindrome(i))
            printf("%d\n", i);
    }
    return 0;
}

And the output was:
110
220
330
440
550

But 111, 222, 212, 585 etc. are palindromic numbers too!