[PeterP] Solving Project Euler #18 and #67 with the HP-71B

[Valentin Albillo]

.
Hi, all,

In another thread I recently started about SRC #012a - Then and Now: Probability, PeterP posted five days ago this message asking about this new topic.

PeterP Wrote:Just stumbled upon this Project Euler 18 and this Project Euler 67. I wonder if 67 could be solved by the 71b...

(I have been toying around on flights now solving pe problems on the HP41 for fun and to avoid killing even more brain cells already dying from getting older by watching movies).

Since it is mostly OT for my thread and further I've found that he deleted his post a few hours ago, I will respond to his question in this new thread I've created on his behalf ('cause he's way too busy with real-life matters).

V.

[Valentin Albillo]

  
Hi, PeterP,

PeterP Wrote:Just stumbled upon this Project Euler 18 and this Project Euler 67.

I guess you haven't read my article on solving PE's problems (heartily recommended !)

HP Article VA051 - Boldly Going - Climbing Project Euler

12-page article, featuring Project Euler, a fantastic project which attempts (and succeeds, in spades !) at providing a huge supply of challenging math+programming problems which are immensely fun to try and solve, learning loads of new concepts while sharpening your skills in the process.

In this article I tell my story with Project Euler and how I dealt with it back in 2011 using the vintage 1984 HP-71B (emulated & physical), which is orders of magnitude slower and less capable than the hardware/software combinations Project Euler's problems are intended for (i.e.: fast modern CPUs + high-level compiled languages), thus enormously upping the ante when tackling them with ancient hardware and interpreted BASIC. See for yourself how I did ! Seven carefully-selected sample PE problems discussed and solved, namely:


Project Euler problem #015 ─ Lattice paths
Project Euler problem #017 ─ Number letter counts
Project Euler problem #040 ─ Champernowne's constant
Project Euler problem #077 ─ Prime summations
Project Euler problem #093 ─ Arithmetic expressions
Project Euler problem #094 ─ Almost equilateral triangles
Project Euler problem #104 ─ Pandigital Fibonacci ends

PeterP Wrote:I wonder if 67 could be solved by the 71b...

But of course the HP-71B can solve those nearly-trivial problems with ease !

This is the original program I wrote 11 years ago to find and submit both answers to PE:

For PE18:

100  DESTROY ALL @ OPTION BASE 1 @ K=15 @ INTEGER A(K,K)
110  DATA 75,95,64,17,47,82,18,35,87,10,20,04,82,47,65,19,01,23,75,03
120  DATA 34,88,02,77,73,07,63,67,99,65,04,28,06,16,70,92,41,41,26,56
130  DATA 83,40,80,70,33,41,48,72,33,47,32,37,16,94,29,53,71,44,65,25
140  DATA 43,91,52,97,51,14,70,11,33,28,77,73,17,78,39,68,17,57,91,71
150  DATA 52,38,17,14,91,43,58,50,27,29,48,63,66,04,68,89,53,67,30,73
160  DATA 16,69,87,40,31,04,62,98,27,23,09,70,98,73,93,38,53,60,04,23
500  FOR I=1 TO K @ FOR J=1 TO I @ READ A(I,J) @ NEXT J @ NEXT I
510  FOR I=K TO 1 STEP -1 @ FOR J=1 TO I-1 @ A(I-1,J)=A(I-1,J)+MAX(A(I,J),A(I,J+1))
520  NEXT J @ NEXT I @ DISP "Max. sum:";A(1,1)

>RUN
       Max. sum: 1074

For PE67:

Same program, just change K=15 at line 100 to K=100 and the DATA statements, of course !

By the way, you'll need a large amount of RAM, just the A matrix needs 100x100x3 ~ 30 Kb, and the DATA statements (or much better, a previously created HP-71B file) containing the 2-digit numbers will require another 15 Kb or so to define the 5,050 values which will be read into matrix A at the beginning.

And come to that, you'd better find a way to automatically read them from the PE-supplied text file and make them available to the HP-71B. That is, if you don't cherish the idea of manually keying them in yourself.

Upon running the program, you'll get:

>RUN
       Max. sum: 7273

Best of luck with the remaining PE problems and, if you need help with solving some of them using the HP-71B, just ask and I'll see if I already created a solution in the distant past.

Best regards.
V.

[PeterP]

(10-28-2022 11:42 PM)Valentin Albillo Wrote:    
Hi, PeterP,

PeterP Wrote:Just stumbled upon this Project Euler 18 and this Project Euler 67.

I guess you haven't read my article on solving PE's problems (heartily recommended !)

HP Article VA051 - Boldly Going - Climbing Project Euler

12-page article, featuring Project Euler, a fantastic project which attempts (and succeeds, in spades !) at providing a huge supply of challenging math+programming problems which are immensely fun to try and solve, learning loads of new concepts while sharpening your skills in the process.

In this article I tell my story with Project Euler and how I dealt with it back in 2011 using the vintage 1984 HP-71B (emulated & physical), which is orders of magnitude slower and less capable than the hardware/software combinations Project Euler's problems are intended for (i.e.: fast modern CPUs + high-level compiled languages), thus enormously upping the ante when tackling them with ancient hardware and interpreted BASIC. See for yourself how I did ! Seven carefully-selected sample PE problems discussed and solved, namely:


Project Euler problem #015 ─ Lattice paths
Project Euler problem #017 ─ Number letter counts
Project Euler problem #040 ─ Champernowne's constant
Project Euler problem #077 ─ Prime summations
Project Euler problem #093 ─ Arithmetic expressions
Project Euler problem #094 ─ Almost equilateral triangles
Project Euler problem #104 ─ Pandigital Fibonacci ends

PeterP Wrote:I wonder if 67 could be solved by the 71b...

But of course the HP-71B can solve those nearly-trivial problems with ease !

This is the original program I wrote 11 years ago to find and submit both answers to PE:

For PE18:

100  DESTROY ALL @ OPTION BASE 1 @ K=15 @ INTEGER A(K,K)
110  DATA 75,95,64,17,47,82,18,35,87,10,20,04,82,47,65,19,01,23,75,03
120  DATA 34,88,02,77,73,07,63,67,99,65,04,28,06,16,70,92,41,41,26,56
130  DATA 83,40,80,70,33,41,48,72,33,47,32,37,16,94,29,53,71,44,65,25
140  DATA 43,91,52,97,51,14,70,11,33,28,77,73,17,78,39,68,17,57,91,71
150  DATA 52,38,17,14,91,43,58,50,27,29,48,63,66,04,68,89,53,67,30,73
160  DATA 16,69,87,40,31,04,62,98,27,23,09,70,98,73,93,38,53,60,04,23
500  FOR I=1 TO K @ FOR J=1 TO I @ READ A(I,J) @ NEXT J @ NEXT I
510  FOR I=K TO 1 STEP -1 @ FOR J=1 TO I-1 @ A(I-1,J)=A(I-1,J)+MAX(A(I,J),A(I,J+1))
520  NEXT J @ NEXT I @ DISP "Max. sum:";A(1,1)

>RUN
       Max. sum: 1074

For PE67:

Same program, just change K=15 at line 100 to K=100 and the DATA statements, of course !

By the way, you'll need a large amount of RAM, just the A matrix needs 100x100x3 ~ 30 Kb, and the DATA statements (or much better, a previously created HP-71B file) containing the 2-digit numbers will require another 15 Kb or so to define the 5,050 values which will be read into matrix A at the beginning.

And come to that, you'd better find a way to automatically read them from the PE-supplied text file and make them available to the HP-71B. That is, if you don't cherish the idea of manually keying them in yourself.

Upon running the program, you'll get:

>RUN
       Max. sum: 7273

Best of luck with the remaining PE problems and, if you need help with solving some of them using the HP-71B, just ask and I'll see if I already created a solution in the distant past.

Best regards.
V.

Wonderful! Thank you so much for the article which I will enjoy reading and learning from on this intercontinental flight. I made it through the first few PEs with the hp41 (and almost through 808, one of the more recent ones). I admit to having switched recently for them to quasi the 71b, using a similar basic emulation on my iOS, as alas, sadly, there is none for the 71b (which would make many things easier by using Math, Math2, and JPC. Who knows, maybe someone gets inspired and builds a port, I for one would buy one immediately).

We are stuck on the gate / runway for another 30’ at least it seems, so I get some extra time.

[rprosperi]

JFG's EMU71/DOS runs fine under DOSBox, which I believe works fine on IOS.

Just a thought...

[PeterP]

(10-29-2022 01:23 PM)rprosperi Wrote:  JFG's EMU71/DOS runs fine under DOSBox, which I believe works fine on IOS.

Just a thought...

You probably mean MacOS, right? Or is there a dosbox that works on the ipad / iphone?

[Massimo Gnerucci]

(10-29-2022 08:18 PM)PeterP Wrote:  

(10-29-2022 01:23 PM)rprosperi Wrote:  JFG's EMU71/DOS runs fine under DOSBox, which I believe works fine on IOS.

Just a thought...

You probably mean MacOS, right? Or is there a dosbox that works on the ipad / iphone?

I don't own a single iThing, but found this

[rprosperi]

(10-29-2022 08:18 PM)PeterP Wrote:  

(10-29-2022 01:23 PM)rprosperi Wrote:  JFG's EMU71/DOS runs fine under DOSBox, which I believe works fine on IOS.

Just a thought...

You probably mean MacOS, right? Or is there a dosbox that works on the ipad / iphone?

DOH!!!

Uh, yes I did mean MacOS... sorry, I am constantly mixing up the various iThings. Not what they are and what they do, just the names....

[rprosperi]

(10-29-2022 08:54 PM)Massimo Gnerucci Wrote:  

(10-29-2022 08:18 PM)PeterP Wrote:  You probably mean MacOS, right? Or is there a dosbox that works on the ipad / iphone?

I don't own a single iThing, but found this

Now that is interesting... I'll be getting an older iPhone in a few weeks (don't panic, it's just for play) from a client and may give this a go.

[Valentin Albillo]

.
Hi, PeterP,

(10-29-2022 11:27 AM)PeterP Wrote:  Wonderful! Thank you so much for the article which I will enjoy reading and learning from on this intercontinental flight. I made it through the first few PEs with the hp41 (and almost through 808, one of the more recent ones).

Don't feel bad about not being able to solve PE#808 with the 10-digit HP-41, the answer requires more digits, which reminds me of what I say in page 11 of my article in "The Rant" section; quoting:

Far too many problems require using more than 12 digits to solve them, so they can’t be solved using the HP-71B or any other 12-digit handheld computer or calculator even if using the best algorithms which otherwise could solve them quickly and efficiently [...]

Of course I can understand that PE problems are aimed at being solved with fast modern PC/laptops (not ancient calculators, even if emulated) using high-level compiled languages (not interpreted BASIC), but that said I also feel that fulfilling PE goals ("...for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context") can be achieved without resorting to artificially high limits and multiprecision results, as there’s an infinite number of interesting problems fulfilling the stated goal without needlessly forcing such limiting constraints [...]

I hope you enjoy my article and hopefully find it useful. Have a good trip back and best regards.
V.

[PeterP]

(10-29-2022 08:54 PM)Massimo Gnerucci Wrote:  

(10-29-2022 08:18 PM)PeterP Wrote:  You probably mean MacOS, right? Or is there a dosbox that works on the ipad / iphone?

I don't own a single iThing, but found this

wow! I will definitely give that a go. I am currently using a C64 emulator which is, well, ok. emu71 would be so much better & cooler! Thank you for sharing Massimo!

[PeterP]

(10-29-2022 11:40 PM)Valentin Albillo Wrote:  .

Don't feel bad about not being able to solve PE#808 with the 10-digit HP-41, the answer requires more digits, which reminds me of what I say in page 11 of my article
I hope you enjoy my article and hopefully find it useful. Have a good trip back and best regards.
V.

Indeed, loved the article, though I was careful not look at the code or explanation for those PE problems I have not solved. Very impressive feat to get through 150 in just a few days and be top 1%. But then again, not surprising given that its you :-)