The Project Euler thread

[leonid]

Re: The Project Euler thread



woohoo

[stargroup100]

Re: The Project Euler thread

leonid blasting through these

[leonid]

Re: The Project Euler thread



fun

[stargroup100]

Re: The Project Euler thread

after all of the fuss about problem 218 I decided to take a look for myself

as soon as I saw the problem I knew my method of approach. so excited to try this right now

EDIT: so after 30 min of pencil/paper I realized that I didn't even need to write any code

WHAT THE FUCK IS THAT SHIT



this question is fucking troll

[stargroup100]

Re: The Project Euler thread

ugh I really need to know how to code more efficiently and faster. I'm trying to blow through the early problems, and while they're obnoxiously easy, I find myself writing a lot of code, which ends up taking up a lot of time

often times my pencil/paper method is faster -__-


like for example, #35 asks to count up circular primes below 1 mil. code is approx 100 lines long, with the following output:

Took 0.485 seconds to generate prime list up to 1000000. problem35.html:46
For 11, all digit rotations are prime: 11 problem35.html:100
For 13, all digit rotations are prime: 13,31 problem35.html:100
For 17, all digit rotations are prime: 17,71 problem35.html:100
For 37, all digit rotations are prime: 37,73 problem35.html:100
For 79, all digit rotations are prime: 79,97 problem35.html:100
...
A total of ????? circular primes. problem35.html:111
Took 0.862 seconds.

im bad ;_;

[Reincarnate]

Re: The Project Euler thread

A little extra time preplanning goes a long way

For 35 you just need a simple sieve and a short rotator method

[kaiten123]

Re: The Project Euler thread

one thing you could do is keep anything you do more than once in its own method/function/etc. so you only write code once per program.
an extention of that is to have a library of common functions so you dont need to rewrite them. like one for generating primes and so on so you can just reuse it for many problems.

still,100 lines seems pretty excessive for that problem. what part is making it so long?
generating the primes should only take a few lines, rotating should only be a few lines, etc.

and lastly, theres usually multiple ways to solve a problem and the one that is fastest on paper might not be the fastest to code so you should keep coding time in mind while thinking of how to solve stuff.

[Reincarnate]

Re: The Project Euler thread

Here's a solution I just wrote for 35 in Python:

n = 10**6
isprime = [0,0]+[1 for i in range(n-1)]
for i in xrange(2,int(n**.5)+1):
    if isprime[i]==1:
        for j in xrange(i*i,n+1,i): isprime[j]=0
s=1
for i in xrange(3,n,2):
    if isprime[i]==1:
        if all(isprime[int(str(i)[r:] + str(i)[:r])]==1 for r in xrange(1,len(str(i)))):
            for r in xrange(len(str(i))):
                if isprime[int(str(i)[r:] + str(i)[:r])] == 1:
                    isprime[int(str(i)[r:] + str(i)[:r])]  = 0
                    s+=1
print s

This can be optimized further but my point is that the underlying logic is pretty straightforward and you can get a fast program without many lines of code (the above code runs in about half a second on my machine).

[stargroup100]

Re: The Project Euler thread

I'm using javascript atm. I'm not sure if that has any relevance but uh yeah. I do reuse a lot of my functions and stuff, and trust me when I say that I'm very familiar with basic concepts such as "fastest paper method might not be fastest to code"

it's not math or problem solving that's difficult for me. I can do more of these problems by hand than almost anyone else. I'm simply not super fluent in programming. a lot of complex algorithms are flying through my head all the time, but figuring out how to convert that into code is sometimes difficult

here's the main function I used to check for a circular prime (I use other functions but didn't post them)

	function check(num) {
		getdigits(num);
		var keepgoing = true;
		if (	(digits.indexOf(0) != -1) ||
				(digits.indexOf(2) != -1) ||
				(digits.indexOf(4) != -1) ||
				(digits.indexOf(5) != -1) ||
				(digits.indexOf(6) != -1) ||
				(digits.indexOf(8) != -1)	) keepgoing = false;
		if (keepgoing) {
			var temparr = [num];
			var commit = true;
			for (var k = 0; k < digits.length; k++) {
				rotatedigits();
				var newnum = getnum();
				if (temparr.indexOf(newnum) === -1) temparr.push(newnum);
				if (primes.indexOf(newnum) === -1) {
					commit = false;
					break;
				}
			}
			if (commit) {
				for (var k = 0; k < temparr.length; k++) {
					circprimes[temparr[k]] = 1;
				}
				console.log('For ' + num + ', all digit rotations are prime: ' + temparr);
				circcount = circcount + temparr.length;
			}
		}
		digits = [];
	}
	for (var k = 4; k < primes.length; k++) {
		if (!circprimes[primes[k]]) check(primes[k]);
	}

[leonid]

Re: The Project Euler thread

I used PARI/GP only for dealing with really large primes (used C before I knew about PARI/GP)

Even though Ruby is a very slow language, it served me well enough for almost all the remaining problems I solved, and very rarely did my codes go above 20 lines


Some people on PE try to solve every problem using ASM but that's just stretching it too far

Here's my friend code if anyone wants to add me 7432696421787_8325ecaf1469afb6ad991ac1dacb210c

[leonid]

Re: The Project Euler thread



My code took 9 minutes :(

EDIT: Tried the same algo on PARI/GP and it took 3 seconds

[Reincarnate]

Re: The Project Euler thread

Thinking of making an extra dummy account and starting fresh, using none of my old libraries.

leonid: problem is much faster in something like C++

Edit: nvm ninja'd, PARI/GP is very fast too for that one apparently XD

[stargroup100]

Re: The Project Euler thread

PARI/GP is god

never underestimate PARI/GP

[leonid]

Re: The Project Euler thread

My only complaint is I can't use GP non-interactively.

So I have to write code somewhere else and copy/paste into the interactive shell. Also since every command is supposed to be 1 line, I need to put a \ at the end of each line, so my code becomes ugly

Actually I think I can get it to work somehow, brb..

[leonid]

Re: The Project Euler thread



cool