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