Flash Flash Revolution
Page 5 of 6 1234 5 6
Show 80 post(s) from this thread on one page

Flash Flash Revolution (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)
-   -   The Project Euler thread (http://www.flashflashrevolution.com/vbz/showthread.php?t=120818)

Reincarnate 06-4-2014 11:16 AM
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 06-4-2014 11:16 AM
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 06-4-2014 04:07 PM
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).

stargroup100 06-4-2014 07:24 PM
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]);
        }

leonid 06-4-2014 07:44 PM
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 06-4-2014 10:38 PM
Re: The Project Euler thread
 


My code took 9 minutes :(

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

Reincarnate 06-4-2014 11:20 PM
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 06-4-2014 11:46 PM
Re: The Project Euler thread
 
PARI/GP is god

never underestimate PARI/GP

leonid 06-4-2014 11:55 PM
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 06-5-2014 12:27 AM
Re: The Project Euler thread
 


cool

reuben_tate 06-5-2014 05:42 AM
Re: The Project Euler thread
 
Quote:
Originally Posted by Reincarnate (Post 4145954)
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

leonid 06-5-2014 06:47 AM
Re: The Project Euler thread
 


Really messy

Reincarnate 06-5-2014 07:11 AM
Re: The Project Euler thread
 
Reuben: even in Python, most problems can be done in under a second

leonid 06-5-2014 07:16 AM
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

Reincarnate 06-5-2014 07:59 AM
Re: The Project Euler thread
 
Quote:
Originally Posted by leonid (Post 4146067)
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).

reuben_tate 06-5-2014 08:10 AM
Re: The Project Euler thread
 
Quote:
Originally Posted by Reincarnate (Post 4146065)
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.

stargroup100 06-5-2014 08:17 AM
Re: The Project Euler thread
 
PARI/GP

seriously ALL HAIL PARI/GP

leonid 06-5-2014 08:53 AM
Re: The Project Euler thread
 


Had me stumped for a few minutes

leonid 06-5-2014 10:01 AM
Re: The Project Euler thread
 


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

leonid 06-5-2014 12:43 PM
Re: The Project Euler thread
 


fun

Reincarnate 06-5-2014 07:36 PM
Re: The Project Euler thread
 
I am going to be going through the problems, posting a cumulative timing of all problems from 1 through whatever problem I am on, using Python (including time taken to import any external stuff I write/use for each problem, individually):

So far:

Total time for problems 1 through 10: 0.734290 seconds

edit:

Total time for problems 1 through 25: 3.879866 seconds

edit:

Total time for problems 1 through 40: 7.787901 seconds

Reincarnate 06-6-2014 12:25 AM
Re: The Project Euler thread
 
blah too tired to do more, zzzztime

leonid 06-6-2014 12:44 AM
Re: The Project Euler thread
 
http://projecteuler.net/problem=466

This one's deceptively difficult

Reincarnate 06-6-2014 12:49 AM
Re: The Project Euler thread
 
Actually one of the easier ones in the upper-400 series, however

leonid 06-6-2014 01:31 AM
Re: The Project Euler thread
 
It's taking inclusion-exclusion to the extreme
Or I'm doing the wrong approach

By the way, how does one get his posts become permanent?

Reincarnate 06-6-2014 01:34 AM
Re: The Project Euler thread
 
For permanent posts, you must either:
1. Get in early enough to post on the first four pages
Or
2: If you're on page 5+, get enough Kudos on your post so an admin can make it permanent.

rushyrulz 06-6-2014 04:03 PM
Re: The Project Euler thread
 
God...

31 ms runtime (this solution was tedious as fuck)

I liked this problem though since it made me refamiliarize myself with regexes as well as a bit of file I/O

stargroup100 06-7-2014 12:29 AM
Re: The Project Euler thread
 
I hated that one

I don't like those kinds of problems lol

I mean, it was pretty easy and trivial but still annoying as fuck and fuck that problem

Reincarnate 06-7-2014 12:33 AM
Re: The Project Euler thread
 
The xor cipher one is fun though

leonid 06-7-2014 06:45 AM
Re: The Project Euler thread
 


New award (O:

I'm gonna stick to easier ones and eventually get back to p466
By the time I reach it, I should be smart enough to know what to do

leonid 06-7-2014 07:28 AM
Re: The Project Euler thread
 


easy

Reincarnate 06-7-2014 08:06 AM
Re: The Project Euler thread
 
some of the harder ones though are really beautiful problems, hope you can give them a try at some point (344, 361, and 415 in particular).

Reincarnate 06-7-2014 08:11 AM
Re: The Project Euler thread
 
also update (Python timings):

Total time for problems 1 through 70: 16.428783 seconds

leonid 06-8-2014 02:51 AM
Re: The Project Euler thread
 


phew

leonid 06-8-2014 05:20 AM
Re: The Project Euler thread
 


Ruby is not the best language if I need to check primality of over 10mil 14-digit numbers

leonid 06-8-2014 10:46 AM
Re: The Project Euler thread
 


woot

Reincarnate 06-8-2014 11:17 AM
Re: The Project Euler thread
 
Total time for problems 1 through 80: 25.627359 seconds

leonid 06-8-2014 11:41 AM
Re: The Project Euler thread
 


easy

leonid 06-8-2014 06:03 PM
Re: The Project Euler thread
 


not easy

beary605 06-8-2014 07:39 PM
Re: The Project Euler thread
 
Quote:
Originally Posted by Reincarnate (Post 4147417)
Total time for problems 1 through 80: 25.627359 seconds
hm, 25.6 seconds for all that? i have some optimizing to do :D

Reincarnate 06-8-2014 07:44 PM
Re: The Project Euler thread
 
In Python though yes

Reincarnate 06-8-2014 09:20 PM
Re: The Project Euler thread
 
Son of a...

Just solved problem 88, but it is tricky to get in decent runtime. Right now my best is only 14s. :(

EDIT: Oh FFS I am an idiot... much faster way to do this.

EDIT: 0.2 seconds -- can't believe I didn't do this in the first place.


EDIT:

Total time for problems 1 through 90: 28.940158 seconds

Reincarnate 06-8-2014 11:45 PM
Re: The Project Euler thread
 
Up to Problem 96, aaaghghghgh Sudoku. Nope. Bedtime

edit: (jk 97, 99, and 100 are quickfodder -- 96 and 98 can diaf)

edit: actually 98 isn't horrible either

edit: GAURUATUGH FINE I'LL DO SUDOKU. :( going to write the most fucking messiest code in the universe

edit: Yay, first 100 down

leonid 06-9-2014 01:02 AM
Re: The Project Euler thread
 


really tough

Reincarnate 06-9-2014 01:10 AM
Re: The Project Euler thread
 
nice one, leonid








EDIT:
Total time for problems 1 through 100: 32.591266 seconds

Code:
Problem 1 in 0.000006 s
Problem 2 in 0.000009 s
Problem 3 in 0.000562 s
Problem 4 in 0.295742 s
Problem 5 in 0.000037 s
Problem 6 in 0.000004 s
Problem 7 in 0.018113 s
Problem 8 in 0.010010 s
Problem 9 in 0.000072 s
Problem 10 in 0.427023 s
Problem 11 in 0.002001 s
Problem 12 in 0.353162 s
Problem 13 in 0.000264 s
Problem 14 in 2.009820 s
Problem 15 in 0.000026 s
Problem 16 in 0.000260 s
Problem 17 in 0.001162 s
Problem 18 in 0.000439 s
Problem 19 in 0.003114 s
Problem 20 in 0.000137 s
Problem 21 in 0.121356 s
Problem 22 in 0.014946 s
Problem 23 in 0.638417 s
Problem 24 in 0.124795 s
Problem 25 in 0.035268 s
Problem 26 in 0.013433 s
Problem 27 in 0.000009 s
Problem 28 in 0.000007 s
Problem 29 in 0.017878 s
Problem 30 in 1.653687 s
Problem 31 in 0.002773 s
Problem 32 in 0.481344 s
Problem 33 in 0.000229 s
Problem 34 in 0.227541 s
Problem 35 in 0.462930 s
Problem 36 in 0.519228 s
Problem 37 in 0.251382 s
Problem 38 in 0.001300 s
Problem 39 in 0.000364 s
Problem 40 in 0.000044 s
Problem 41 in 0.001595 s
Problem 42 in 0.004338 s
Problem 43 in 0.049111 s
Problem 44 in 0.271455 s
Problem 45 in 0.018607 s
Problem 46 in 0.012878 s
Problem 47 in 0.072932 s
Problem 48 in 0.003445 s
Problem 49 in 0.485125 s
Problem 50 in 0.197839 s
Problem 51 in 0.238479 s
Problem 52 in 0.641779 s
Problem 53 in 0.002342 s
Problem 54 in 0.067815 s
Problem 55 in 0.077687 s
Problem 56 in 0.414760 s
Problem 57 in 0.000912 s
Problem 58 in 0.293105 s
Problem 59 in 0.002044 s
Problem 60 in 5.083650 s
Problem 61 in 0.002605 s
Problem 62 in 0.045824 s
Problem 63 in 0.000028 s
Problem 64 in 0.242403 s
Problem 65 in 0.000090 s
Problem 66 in 0.032540 s
Problem 67 in 0.005123 s
Problem 68 in 0.040291 s
Problem 69 in 0.000160 s
Problem 70 in 0.790107 s
Problem 71 in 0.000006 s
Problem 72 in 0.062803 s
Problem 73 in 0.019348 s
Problem 74 in 1.181639 s
Problem 75 in 0.745507 s
Problem 76 in 0.070708 s
Problem 77 in 0.021643 s
Problem 78 in 6.514026 s
Problem 79 in 0.000227 s
Problem 80 in 0.007928 s
Problem 81 in 0.007150 s
Problem 82 in 0.010406 s
Problem 83 in 0.131738 s
Problem 84 in 0.001178 s
Problem 85 in 0.002586 s
Problem 86 in 1.702908 s
Problem 87 in 0.464952 s
Problem 88 in 0.270735 s
Problem 89 in 0.002017 s
Problem 90 in 0.075457 s
Problem 91 in 0.008651 s
Problem 92 in 0.207911 s
Problem 93 in 0.270968 s
Problem 94 in 0.000015 s
Problem 95 in 3.656271 s
Problem 96 in 0.216058 s
Problem 97 in 0.000015 s
Problem 98 in 0.147458 s
Problem 99 in 0.002978 s
Problem 100 in 0.000015 s

Total time for problems 1 through 100: 32.591266 seconds

leonid 06-9-2014 10:59 PM
Re: The Project Euler thread
 


OMG finally.

leonid 06-9-2014 11:35 PM
Re: The Project Euler thread
 
Wish people read my posts because I take extra time refining my code and explanations

As of now most of the posts I've made recently are still the very last post of each thread

stargroup100 06-10-2014 12:19 AM
Re: The Project Euler thread
 
I read them

I just don't have much to say lol

leonid 06-10-2014 12:22 AM
Re: The Project Euler thread
 
I'm talking about my posts in the euler problem threads btw, not this thread

stargroup100 06-10-2014 02:39 AM
Re: The Project Euler thread
 
OHHH

yeah it kinda sucks, cause nobody reads past the first three posts, let alone the first page

rushyrulz 06-10-2014 09:13 AM
Re: The Project Euler thread
 
Quote:
Originally Posted by Problem 23
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Finished problem 23 and it was an efficiency nightmare (i shud lrn 2 code b4tr)

Why do they pick 28,123 when the same is true for all numbers greater than 20,161?

stargroup100 06-10-2014 01:41 PM
Re: The Project Euler thread
 
Quote:
Originally Posted by rushyrulz (Post 4148210)
Finished problem 23 and it was an efficiency nightmare (i shud lrn 2 code b4tr)

Why do they pick 28,123 when the same is true for all numbers greater than 20,161?
I'm assuming this means that through conceptual analysis and proof, the lowest limit we can reduce down to is 28123. Even though the true limit is lower, this is the smallest upper bound we can actually prove in this way. If this is really true, I'm sure it's very well defined what they mean by "reduced any further by analysis". Clearly, brute force testing with a computer doesn't count.

Unless you're asking why the problem writer chose to use that number specifically, in which case I don't know and it's really the writer's free choice. Perhaps he just simply wanted an excuse to use larger numbers, despite the small increase. It does kinda make sense though; once you find the limit of your hand analysis, you have no choice but to use a computer, and only then can you reduce that limit. The problem probably wants to demonstrate an example of this.

I just tried this on my own and the 28123 limit is actually pretty easy to prove, and I really do have no idea how to get this down any lower.

Reincarnate 06-10-2014 03:47 PM
Re: The Project Euler thread
 
Quote:
Originally Posted by leonid (Post 4148151)
Wish people read my posts because I take extra time refining my code and explanations

As of now most of the posts I've made recently are still the very last post of each thread
I read them all (I scroll through the problem listings from time to time and check out new posts).

I just don't have much to add because I don't find those problems as interesting as some of the harder ones.

A comment though, I'm surprised about your approach to 181. That problems seems like it would have been really easy for you to hammer out and execute in quick runtime.


edit: Stargroup: Yes that's right -- in practice it's lower but the limit is analytically provable. Here is the proof: http://mathschallenge.net/full/sum_o...undant_numbers

stargroup100 06-10-2014 05:22 PM
Re: The Project Euler thread
 
oh shit that's the method I came up with LOL

rushyrulz 06-10-2014 06:40 PM
Re: The Project Euler thread
 
fair enough

leonid 06-11-2014 06:48 AM
Re: The Project Euler thread
 


Literally took me 3 minutes to solve
Now I ran out of easy problems

rushyrulz 06-11-2014 07:42 AM
Re: The Project Euler thread
 


first one that I actually used pencil and paper for.

leonid 06-11-2014 09:52 AM
Re: The Project Euler thread
 


woot

leonid 06-13-2014 06:47 PM
Re: The Project Euler thread
 


Easy

A question... Isn't problem 266 a 2-partition problem (NP-complete)?
I don't see any way other than having to run an exponential (or pseudo-polynomial) runtime algorithm that takes ages to finish

Reincarnate 06-13-2014 08:15 PM
Re: The Project Euler thread
 
There is a way

Every single problem gets tested against the minute-rule before release.

Problem 266 is doable in a lot less time than that, even

leonid 06-13-2014 08:37 PM
Re: The Project Euler thread
 
But it is a 2-partition problem.. unless mod 10^16 part is giving any twist

Reincarnate 06-13-2014 08:53 PM
Re: The Project Euler thread
 
Idk about this "two partition" thing but FWIW I can output the full result in Python in under 8 seconds

It's hard to say more without spoiling

leonid 06-13-2014 08:58 PM
Re: The Project Euler thread
 
http://en.wikipedia.org/wiki/Partition_problem

It's about sums instead of products here, but p266 becomes the same once you put logs on it

whatever, I'll get back to this later

Reincarnate 06-13-2014 09:06 PM
Re: The Project Euler thread
 
Hard to say more without spoiling, but there's something being overlooked (try to find another kind of problem that this is similar to)

leonid 06-14-2014 02:44 AM
Re: The Project Euler thread
 


level up \o/

leonid 06-14-2014 03:44 AM
Re: The Project Euler thread
 


easy

leonid 06-14-2014 04:24 AM
Re: The Project Euler thread
 


easy

leonid 06-14-2014 05:55 AM
Re: The Project Euler thread
 


tricky

leonid 06-14-2014 08:18 AM
Re: The Project Euler thread
 


Why am I doing physics on PE

Reincarnate 06-14-2014 08:47 AM
Re: The Project Euler thread
 
Still a fun little problem

Reincarnate 06-14-2014 08:51 AM
Re: The Project Euler thread
 
Ps try the new problem, easy one

leonid 06-14-2014 08:55 AM
Re: The Project Euler thread
 
After I solve harshad

leonid 06-14-2014 09:13 AM
Re: The Project Euler thread
 


easy

leonid 06-14-2014 11:03 AM
Re: The Project Euler thread
 


ok :P

Reincarnate 06-14-2014 11:32 AM
Re: The Project Euler thread
 
Nicely done :)

leonid 06-14-2014 12:23 PM
Re: The Project Euler thread
 


Two awards at once

leonid 06-14-2014 02:13 PM
Re: The Project Euler thread
 


That was a scary one

Reincarnate 06-14-2014 02:43 PM
Re: The Project Euler thread
 
Scary?

leonid 06-14-2014 02:47 PM
Re: The Project Euler thread
 


Just look at this. It's daunting when you first see it

Reincarnate 06-14-2014 02:51 PM
Re: The Project Euler thread
 
Oh yeah

For some reason I found that one surprisingly tricky for some reason


All times are GMT -5. The time now is 10:29 AM.
Page 5 of 6 1234 5 6
Show 80 post(s) from this thread on one page

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