Solved Project Euler problems

General Discussions about ND1

Solved Project Euler problems

Postby oliver » Thu May 26, 2011 3:30 am

This is an effort to maintain a list of Project Euler (http://projecteuler.net) problems solved on ND1 and other RPL calculators (that is: HP-28, -48, -49, -50g).
Best run-times for each problem are included.

There's a Project Euler shared folder which contains some solutions, but not all. (So as not to spoil the harder problems, and those still open for solution submissions.)

This list is open to anyone with a MorphEngine or RPL calculator, who wants to contribute their solution result, or see which problems have a solution (and how long it might take to find it).

If you want to contribute, please add to this thread with the problem number, your run-time and the device you used.
I'll be updating the list in post #2, so that one's always complete.
If you have a better elapsed time for an already-solved problem, post that too, so it may become that problem's new best time to beat.
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Solved Problems List

Postby oliver » Thu May 26, 2011 4:13 am

#1 [ND1: <1s]
#2 [ND1: <1s]
#3 [ND1: <1s] one-liner
#4 [ND1: 10s (3GS), 1.2s (iPhone 5s)]
#5 [ND1: <1s] one-liner
#6 [ND1: <1s] one-liner in GS/ME
#7 [ND1: 1.9s] one-liner
#8 [ND1: <1s] one-liner in GS/ME
#9 [50g (Gilles): ?; ND1: <1s]
#10 [ND1: 39s (3GS), 3.4s (iPhone 5s)] one-liner
#11 [50g (Gilles): 40s, ND1: <1s]
#12 [ND1: 7s (3GS), 0.8s (iPhone 5s)]
#13 [ND1: <1s] one-liner in GS/ME
#14 [ND1: 8s (3GS), 1.4s (iPhone 5s)]
#15 [ND1: <1s] one-liner
#16 [ND1: <1s]
#17 [50g (Gilles): ?]
#18 [ND1: <1s]
#19 [50g, ND1: <1s]
#20 [ND1: <1s]
#21 [50g (Gilles): ?; ND1: 1.5s]
#22 [50g (Gilles): ?; ND1: 22s (3GS), 3.8s (iPhone 5s)]
#23 [ND1: 21s]
#24 [ND1: 20s (3GS), 1.9s (iPhone 5s)] one-liner
#25 [ND1: <1s]
#28 [ND1: <1s]
#29 [ND1: 11.5s]
#30 [50g (Gilles): ?; ND1: 2.5 min (3GS), 33s (iPhone 5s)]
#31 [ND1: <1s]
#33 [ND1: <1s]
#34 [50g (Gilles): ?; ND1: 45s (3GS), 5.5s (iPhone 5s)]
#35 [ND1: 44s (3GS), ~4s (iPhone 5s)]
#40 [ND1: <1s]
#41 [ND1: <1s]
#42 [ND1: 7.5s (3GS), 0.8s (iPhone 5s)]
#47 [50g (Gilles): ?; ND1: 123s (3GS), 15.3s (iPhone 5s)]
#48 [ND1: 3.8s (3GS), 0.38s (iPhone 5s)]
#49 [Emu48 (Gilles): 46s (3GS), ~5s (iPhone 5s)]
#52 [50g: ?] (Gilles)
#53 [ND1: 5.3s (3GS), 0.47s (iPhone 5s)]
#56 [ND1: 7.4s (3GS), 0.55s (iPhone 5s)]
#57 [ND1: 30s (3GS), 2.1s (iPhone 5s)]
#63 [ND1: <1s]
#64 [ND1: 5.5s (3GS), 0.8s (iPhone 5s)]
#67 [50g: 72s, ND1: <1s] one-liner in GS/ME
#69 [ND1: 11s (3GS), 1.3s (iPhone 5s)]
#71 [ND1: <1s]
#72 [ND1: 10s (3GS), 1.3s (iPhone 5s)]
#76 [ND1: <1s]
#77 [ND1: 2s (3GS)]
#80 [ND1: 82s (3GS), 8.6s (iPhone 5s)]
#97 [ND1: <1s] one-liner
#102 [ND1: <1s]
#119 [ND1: <1s]
#120 [ND1: <1s]
#123 [ND1: 7.5s (3GS), 0.6s (iPhone 5s)]
#124 [ND1: 7.6s (iPhone 5s)]
#131 [ND1: <1s]
#179 [ND1: ~15m (3GS), 126s (iPhone 5s)]
#188 [ND1: 14.5s (3GS), ~1.4s (iPhone 5s)] one-liner in GS/ME
#206 [50g: ?] (Gilles)
#214 [ND1: ~35m (3GS), ~3.5m (iPhone 5s)]
#303 [ND1: ~2m (3GS), ~12s (iPhone 5s)]
#304 [ND1: ~60m (3GS), ~6m (iPhone 5s)]
#317 [50g: ?] (Gilles)
#318 [ND1: 3.3s (3GS), ~0.3 (iPhone 5s)]
#329 [50g: ?] (Gilles)
#335 [50g: 11s, ND1: 0.2s] (val) one-liner in GS/ME
#356 [ND1: 33s (3GS), ~3s (iPhone 5s)]
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

How to bench

Postby oliver » Thu May 26, 2011 4:29 am

Quick note:
To bench your completed code in ND1, put your RPL(+) code, or RPL containing a call to your code, on the stack, and enter: Bench.RPL
Bench1.png
Bench1.png (4.12 KiB) Viewed 31153 times

This will run your code normally, and, when done, enter the elapsed time as a tagged object on the stack.
Bench2.png
Bench2.png (6.27 KiB) Viewed 31153 times

This also works with JavaScript code, as long as you wrap a call to in a short RPL program, as shown in the example. (That is, '#2' could be either an RPL or a JavaScript program.)

This requires the Bench shared folder.

You can Select All and Copy while you have Bench.RPL on the edit line, for easy subsequent Pastes of this command.
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

MorphEngine now a language option

Postby oliver » Sat Jun 25, 2011 5:23 am

MorphEngine is now available as a Language option when editing your user profile at projecteuler.net.
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Study Guide available

Postby oliver » Sun Jul 24, 2011 5:17 am

The code for ~50 solutions has been posted to
http://naivedesign.com/ND1/Project_Euler.html

Run times for both ND1 and CalcPad/Mac are included.

The solutions presented are all for already archived problems, for which there's no Project Euler-sanctioned means to share code anymore.
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Solved Project Euler problems

Postby Gilles » Mon Jul 30, 2012 4:15 pm

Hi,

i've solve some Euler projects in RPL that not presented here.
If there is an interest I can put the sources

Gilles (alias Nemo)

(I must say when I read some of them now, I can't sometimes even remember what I want do do ! - for exemple PB 49 but it goes fast (with Emu48)

For example , here is EULER 17 :
Code: Select all
«    -> n
  «
  {
   { 1 "one"} {2 "two"} { 3 "three"} { 4 "four"} { 5 "five"} { 6 "six"} { 7 "seven"} { 8 "eight"} { 9 "nine"} {10 "ten"}
   {11 "eleven"} {12 "twelve"} {13 "thirteen"} {14 "fourteen"} {15 "fifteen"} {16 "sixteen"}  {17 "seventeen"} {18 "eighteen"}
   {19 "nineteen"} {20 "twenty"} {30 "thirty"} {40 "forty"} {50 "fifty"} {60 "sixty"} {70 "seventy"} {80 "eighty"} {90 "ninety"}
  }

    « HEAD n == » Find

    IF DUP NOVAL <> THEN
      TAIL EVAL
    ELSE
      DROP 
      CASE
        'n<100'                     THEN n 10 IQUOT 10 * TXT n 10 IREMAINDER TXT END
        'n<1000 AND n MOD 100 == 0' THEN n 100 IQUOT TXT "hundred" END
        'n>100 AND n<=999'          THEN n 100 IQUOT TXT "hundredand" n 10 IREMAINDER TXT END
        'n==1000'                   THEN "onethousand" END
      END
    END
  »
»
'TXT' STO

«
 CLEAR
 1 1000 FOR i i TXT NEXT
 DEPTH 2 SWAP START + NEXT
 SIZE
»


This one is very slow even with full speed EMU48 (recursive process are _very_ slow with the HP50... Avoid them if you can ;)
It uses Gofer List Library http://www.musikwissenschaft.uni-mainz.de/~ag/hp49/README-GoferLists
As I use HPUserEdit, some specials could be missed with Drag and Drop :(
Gilles
 
Posts: 2
Joined: Mon Jul 30, 2012 7:17 am

Re: Solved Project Euler problems

Postby oliver » Tue Jul 31, 2012 12:19 am

Hi Gilles,

Welcome to this forum!

I know you've done great work with PE problems, and your RPL solutions to problems sure would be appreciated. As of this writing, this thread has about 500 views, so there's a certain amount of interest.

If you want, you could attach sources to a post for others to view. Maybe provide some commentary for something special or cool. If you should ever get ND1, there's another way for you to share the sources: from within the app, you'd download the Project Euler shared folder, add your solutions to it (though to be useful they should execute on ND1, so Goferlist commands would have to be converted to built-in commands (I think you'll find equivalents for all), etc.) and then upload it as "publicly viewable". You'd also post a note of what you added to http://forums.naivedesign.com/viewtopic.php?f=10&t=262, and then I'd make an updated version of Project Euler publicly available.

The purpose of this list to share which problems have been solved, and how long the run-time is. So, even if you don't want to post sources, just reporting which problem was solved and how long it takes to run on what platform (both 50g and Emu48 are fine) would already share some valuable information. For example, with the higher numbered problems, I wondered quite often which ones are even solvable on a (any) calculator. Just knowing that someone solved it with a run time of, say, one minute, let's me know that I could attempt to solve the problem myself.

If you submit that info, I will complete the list above. Since you go by your name at hp48.comp.sys, hpmuseum.org, and this forum now, I changed all references from "Nemo" to your name. I hope that's ok.

Thanks for your solution to #17. I'll study the source and attempt a ND1 conversion. I must say I avoided that PE problem until now because it scared me...

Again, welcome! Looking forward to your (great) submissions!

Oliver
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Solved Project Euler problems

Postby Gilles » Tue Jul 31, 2012 2:02 am

Thanks Oliver !

#49
(46 sec with EMU48)

The idea is simple :

1/ Take all the prime numbers between 1000-9999
2/ For each number, calculate a 'unique key' in function of the digits ( 1009 and 9001 may produce the same return value)
3/ Put all the numbers with the same 'key' in a sorted sub-list of a global list
4/ Filter only the list with 3 items or more, and calcute the Delta between the numbers... Note that a double DList (greek DELTA symbol LIST) command is interesting here.... { 133 166 199} DList DList -> {0}

This algorithm is not perfect in point 4 (you could have an 'intruder' number between 3 numbers , I knew that but Itried to see and it works.

RPL source in HPUserEdit format (change to .txt extension)
Attachments
PB049.hpprg.txt
(691 Bytes) Downloaded 1277 times
Gilles
 
Posts: 2
Joined: Mon Jul 30, 2012 7:17 am

Re: Solved Project Euler problems

Postby oliver » Fri Jan 10, 2014 11:04 pm

I updated post 2, the Solved Problems List, with timings for newer iPhone hardware.
Turns out the iPhone 5s is on average ~10x faster than an iPhone 3GS. Not bad.

If you're curious where your own iOS device stands performance-wise, use the following benchmark results for problem #10--computing all primes below 2 million--as a guide:

iPhone: >100s
iPhone 3GS: 39s
iPod touch 5th gen: 19.5s
iPhone 4S: 18s
iPhone 5: 10s
iPhone 5s: 3.4s (in 64-bit); (informational: in 32-bit: 4s)

iPhones have come a long way. The 5s is approx. 40x faster than the original iPhone. Not bad.
Part of the speed-up comes from its A7 CPU supporting 64-bit. (I quantified the speed-up from 64-bit at ~30%. Problem #10 is not so representative for the avg speed-up you get from going to 64-bit.)

[Note: the 5s timings are for ND1 running in 64-bit mode, available in version >=1.5.5.]
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm


Return to General

Who is online

Users browsing this forum: No registered users and 1 guest

cron