S&SMC#10: My Original Solutions & Comments Message #4 Posted by Valentin Albillo on 7 June 2005, 5:15 a.m., in response to message #1 by Valentin Albillo
Hi all,
Thanks a lot to all of you interested in this small challenge of mine, we've
got a surprising number of clever programs for a variety of HP machines,
written in assorted languages including RPL, several RPN flavors, and
even BASIC.
Here's my original RPN solution for the HP-15C, a small, 52-step program
which uses matrix operations to find the solution quickly:
01 *LBL A 17 GTO 8 32 CLX 47 RCL MATRIX A
02 1 18 RCL MATRIX A 33 STO MATRIX C 48 -
03 MATRIX 0 19 *LBL 3 34 RCL I 49 MATRIX 7
04 10 20 GSB 5 35 STO 1 50 RETURN
06 STO I 21 X=0 ? 36 *LBL 1 51 *LBL 0
07 DIM A 22 GTO 0 37 1 52 RCL MATRIX C
08 DIM B 23 RCL MATRIX C 38 RCL+ B
09 DIM C 24 GSB 5 39 X<> 1
10 *LBL 2 25 X=0 ? 40 ISG C
11 MATRIX 1 26 GTO 2 41 *LBL 1
12 *LBL 8 27 RCL MATRIX C 42 X<> 1
13 RAN# 28 STO MATRIX A 43 DSE 1
14 RCL* I 29 GTO 3 44 GTO 1
15 INT 30 *LBL 5 45 RESULT B
16 uSTO A 31 STO MATRIX B 46 RCL MATRIX C
Note: Step 16 is a "User" STO operation, and must be entered while temporarily
in USER mode, a small "u" should appear next to the step number. All other
STO and RCL operations must be entered *out* of USER mode.
It doesn't use any allocatable numbered registers but the permanent ones,
namely R0-R1 (system indexes for matrix operations) and RI (index register
used here merely to hold the constant 10).
The program requires extremely very little user-provided heuristics. Not even the fact
that the digits must add up to 10 or that there can't be two 9's, say, is
made use of. Instead, the only thing the program knows is that it must
compute a function f(N), say, than when applied to a 10-digit N returns another
10-digit result where each digit represents a count of the corresponding
digit in the original number, so we have:
f(N) = M
Obviously, the value of N we're looking for has the unique property that when
f is applied to it, it returns unchanged, that is:
f(N) = N
The program simply goes on to solve this equation. There are a number of reasonable ways
we could proceed, but the most successful is to simply select an starting
value of N, say N0, then compute:
f(N0) -> N1, f(N1) -> N2, ...
till for some Ni we do have
Ni+1 = f(Ni) = Ni
As f(N) maps 10-digit numbers
into 10-digit numbers and there are only so many of them, we must have cycles, where successive applications
of f(N) eventually repeat some previous value. We are interested in the
1-cycle, where f(N) = N, but other cycles can and do exist.
To cater for this, my program initially selects a 10-digit value of N at
random, then keeps on applying f(N) to the resulting values while checking if some
cycle has been detected. If it is a 1-cycle, this is the solution and the
program stops with the solution in the display. Else, if the program has
stumbled into a greater order cycle, it simply restarts again, selecting
another random starting value. Eventually, it succeeds, provably after very few
restarts indeed, and the solution is displayed.
To maximize speed, my program uses a matrix representation for numbers,
where a 1x10 matrix represents a 10-digit number. This way we can make
use of the powerful and fast HP-15C matrix operations. Checking for
repetition, for instance, is as simple as testing if the Row Norm (MATRIX 7) of the
difference of two matrices is zero, which can be done in a few steps and
with no slow user-code loops involved.
To run the program, follow these steps:
- Allocate enough registers to dimension the three 1x10 matrices
needed (assuming this is the only program in program memory, 26 or any lower
number will do):
26, DIM (i)
MEM should display [ 26 30 9-1 ] (i.e., 26 numbered registers plus R0 and
RI + 30 registers reserved for matrices)
- Optionally, specify a seed for the random number generator. This step
is not necessary, as the program will always converge from any starting seed,
but if you want to repeat my timing, I always use PI in such cases:
PI, STO #RAN,
- Now simply run the program:
GSB A -> (after 2 min 56 sec) -> C 1 10
The program stops displaying the matrix which represents and holds the
solution found. You just need to display its elements as usual, for instance:
MATRIX 1, USER, RCL C -> (C1,1) -> 6
RCL C -> (C1,2) -> 2
RCL C -> (C1,3) -> 1
RCL C -> (C1,4) -> 0
RCL C -> (C1,5) -> 0
RCL C -> (C1,6) -> 0
RCL C -> (C1,7) -> 1
RCL C -> (C1,8) -> 0
RCL C -> (C1,9) -> 0
RCL C -> (C1,10) -> 0
which represents the unique solution: 6210001000
The program can be made a step shorter using a flag, but I like it better
as it is now. The equivalent version for the HP-71B, perhaps easier to
understand and translate to other languages, is:
10 DESTROY ALL @ OPTION BASE 0 @ DIM N(9),X(9),T(9) @ RANDOMIZE
20 FOR I=0 TO 9 @ N(I)=INT(RND*10) @ NEXT I
30 MAT X=N @ GOSUB 50 @ IF NOT CNORM(X) THEN MAT DISP T @ END
40 MAT X=T @ GOSUB 50 @ IF CNORM(X) THEN MAT N=T @ GOTO 30 ELSE 20
50 MAT T=ZER @ FOR I=0 TO 9 @ T(X(I))=T(X(I))+1 @ NEXT I @ MAT X=T-N @ RETURN
which is 5 lines, 195 bytes long. A shorter version is possible, namely this
4-liner:
1 DESTROY ALL @ OPTION BASE 0 @ DIM N(9),X(9),T(9) @ RANDOMIZE
2 FOR I=0 TO 9 @ N(I)=INT(RND*10) @ NEXT I @ MAT T=N
3 GOSUB 4 @ IF I THEN MAT DISP T @ END ELSE GOSUB 4 @ MAT N=T @ IF I THEN 2 ELSE 3
4 MAT X=T @ MAT T=ZER @ FOR I=0 TO 9 @ T(X(I))=T(X(I))+1 @ NEXT I @ MAT X=T-N @ I=CNORM(X)=0 @ RETURN
but I think this is really overkill, besides it's actually one byte longer and slightly slower.
Some (long) statistical tests reveal that this kind of program always finds
a solution after generating an average of 13.5 ten-digit numbers, though values
as low as 1 (directly stumbling upon the solution by chance) or as high as
100 (entering n-cycles repeatedly) are possible, though with very low probabilities.
Of course, even in the worst case of 100+ numbers generated and tested, an actual HP-71B can do it in just a few seconds and Emu71 takes usually
much less than a second.
See you in S&SMC#11, thanks for your interest and
Best regards from V.
|