Old 06-4-2014, 11:16 AM   #321
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default 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
Reincarnate is offline   Reply With Quote
Old 06-4-2014, 11:16 AM   #322
kaiten123
FFR Player
 
Join Date: May 2008
Age: 30
Posts: 1,114
Default 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.
kaiten123 is offline   Reply With Quote
Old 06-4-2014, 04:07 PM   #323
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

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


Code:
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).

Last edited by Reincarnate; 06-4-2014 at 04:22 PM..
Reincarnate is offline   Reply With Quote
Old 06-4-2014, 07:24 PM   #324
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,046
Default 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)

Code:
	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]);
	}
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music
stargroup100 is offline   Reply With Quote
Old 06-4-2014, 07:44 PM   #325
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default 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
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-4-2014, 10:38 PM   #326
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread



My code took 9 minutes :(

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



Proud member of Team No

Last edited by leonid; 06-4-2014 at 11:21 PM..
leonid is offline   Reply With Quote
Old 06-4-2014, 11:20 PM   #327
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default 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

Last edited by Reincarnate; 06-4-2014 at 11:25 PM..
Reincarnate is offline   Reply With Quote
Old 06-4-2014, 11:46 PM   #328
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,046
Default Re: The Project Euler thread

PARI/GP is god

never underestimate PARI/GP
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music
stargroup100 is offline   Reply With Quote
Old 06-4-2014, 11:55 PM   #329
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default 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..
__________________



Proud member of Team No

Last edited by leonid; 06-4-2014 at 11:58 PM..
leonid is offline   Reply With Quote
Old 06-5-2014, 12:27 AM   #330
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread



cool
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-5-2014, 05:42 AM   #331
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 28
Posts: 4,131
Default Re: The Project Euler thread

Quote:
Originally Posted by Reincarnate View Post
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
I'm deciding to start fresh because I made my original account years ago; I never kept my code or notes or anything organized so it just became an unorganized mess.

I'm trying to learn a bit of Python at the moment, so that's what I've been coding in. However, at least from my viewpoint, Python is horrifically slow (one source whose credibility I did not check which I found interesting regarding programming languages vs speed: here). On the bright side, in the case that Python is slower than other programming languages I've used, this forces me to come up with more efficient algorithms.

Only did the first 15 for now:


New friend key:
Code:
95430157644057_56e54c547c0f732b3b941aec7177ce58
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing

Last edited by reuben_tate; 06-5-2014 at 10:07 AM..
reuben_tate is offline   Reply With Quote
Old 06-5-2014, 06:47 AM   #332
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread



Really messy
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-5-2014, 07:11 AM   #333
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

Reuben: even in Python, most problems can be done in under a second
Reincarnate is offline   Reply With Quote
Old 06-5-2014, 07:16 AM   #334
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread

I did this RSA problem by manual empirical pattern recognizing with lots of experiments, small examples, and blind guessworks

And then I saw the real way of solving it in the thread. I feel like I cheated through this, but I guess what I learned in this thread will help me on other problems
@Reincarnate Check my code in the thread if you want to see what I mean
http://projecteuler.net/thread=182&page=4#171693
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-5-2014, 07:59 AM   #335
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

Quote:
Originally Posted by leonid View Post
I did this RSA problem by manual empirical pattern recognizing with lots of experiments, small examples, and blind guessworks

And then I saw the real way of solving it in the thread. I feel like I cheated through this, but I guess what I learned in this thread will help me on other problems
@Reincarnate Check my code in the thread if you want to see what I mean
http://projecteuler.net/thread=182&page=4#171693
If it works, it works. May be worth going back and doing it the "right" way though (or at least reading the forum).
Reincarnate is offline   Reply With Quote
Old 06-5-2014, 08:10 AM   #336
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 28
Posts: 4,131
Default Re: The Project Euler thread

Quote:
Originally Posted by Reincarnate View Post
Reuben: even in Python, most problems can be done in under a second
Well, of course. I guess what I'm trying to get at is that if you use a language that is of magnitudes times faster than another, then you can get away with more "lazy" solutions with the faster programming language.
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing
reuben_tate is offline   Reply With Quote
Old 06-5-2014, 08:17 AM   #337
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,046
Default Re: The Project Euler thread

PARI/GP

seriously ALL HAIL PARI/GP
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music
stargroup100 is offline   Reply With Quote
Old 06-5-2014, 08:53 AM   #338
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread



Had me stumped for a few minutes
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-5-2014, 10:01 AM   #339
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread



I used Ruby this time because GP has no hash tables ?_?
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-5-2014, 12:43 PM   #340
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread



fun
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are Off
[IMG] code is On
HTML code is Off

Forum Jump



All times are GMT -5. The time now is 07:20 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution