Flash Flash Revolution (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)

 Reincarnate 06-4-2014 11:16 AM

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

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

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

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

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)

 leonid 06-4-2014 07:44 PM

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

 leonid 06-4-2014 10:38 PM

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

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

PARI/GP is god

never underestimate PARI/GP

 leonid 06-4-2014 11:55 PM

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

cool

 reuben_tate 06-5-2014 05:42 AM

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

Really messy

 Reincarnate 06-5-2014 07:11 AM

Reuben: even in Python, most problems can be done in under a second

 leonid 06-5-2014 07:16 AM

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

 Reincarnate 06-5-2014 07:59 AM

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

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

PARI/GP

seriously ALL HAIL PARI/GP

 leonid 06-5-2014 08:53 AM

Had me stumped for a few minutes

 leonid 06-5-2014 10:01 AM

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

 leonid 06-5-2014 12:43 PM

fun

 Reincarnate 06-5-2014 07:36 PM

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

blah too tired to do more, zzzztime

 leonid 06-6-2014 12:44 AM

http://projecteuler.net/problem=466

This one's deceptively difficult

 Reincarnate 06-6-2014 12:49 AM

Actually one of the easier ones in the upper-400 series, however

 leonid 06-6-2014 01:31 AM

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

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

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

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

The xor cipher one is fun though

 leonid 06-7-2014 06:45 AM

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

easy

 Reincarnate 06-7-2014 08:06 AM

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

also update (Python timings):

Total time for problems 1 through 70: 16.428783 seconds

 leonid 06-8-2014 02:51 AM

phew

 leonid 06-8-2014 05:20 AM

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

woot

 Reincarnate 06-8-2014 11:17 AM

Total time for problems 1 through 80: 25.627359 seconds

 leonid 06-8-2014 11:41 AM

easy

 leonid 06-8-2014 06:03 PM

not easy

 beary605 06-8-2014 07:39 PM

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

In Python though yes

 Reincarnate 06-8-2014 09:20 PM

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

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

really tough

 Reincarnate 06-9-2014 01:10 AM

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

OMG finally.

 leonid 06-9-2014 11:35 PM

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

I just don't have much to say lol

 leonid 06-10-2014 12:22 AM

 stargroup100 06-10-2014 02:39 AM

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

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

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

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

oh shit that's the method I came up with LOL

 rushyrulz 06-10-2014 06:40 PM

fair enough

 leonid 06-11-2014 06:48 AM

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

 rushyrulz 06-11-2014 07:42 AM

first one that I actually used pencil and paper for.

 leonid 06-11-2014 09:52 AM

woot

 leonid 06-13-2014 06:47 PM

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

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

But it is a 2-partition problem.. unless mod 10^16 part is giving any twist

 Reincarnate 06-13-2014 08:53 PM

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

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

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

level up \o/

 leonid 06-14-2014 03:44 AM

easy

 leonid 06-14-2014 04:24 AM

easy

 leonid 06-14-2014 05:55 AM

tricky

 leonid 06-14-2014 08:18 AM

Why am I doing physics on PE

 Reincarnate 06-14-2014 08:47 AM

Still a fun little problem

 Reincarnate 06-14-2014 08:51 AM

Ps try the new problem, easy one

 leonid 06-14-2014 08:55 AM

 leonid 06-14-2014 09:13 AM

easy

 leonid 06-14-2014 11:03 AM

ok :P

 Reincarnate 06-14-2014 11:32 AM

Nicely done :)

 leonid 06-14-2014 12:23 PM

Two awards at once

 leonid 06-14-2014 02:13 PM

That was a scary one

 Reincarnate 06-14-2014 02:43 PM

Scary?

 leonid 06-14-2014 02:47 PM

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

 Reincarnate 06-14-2014 02:51 PM