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

[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.