Final Remarks Message #18 Posted by Ex-PPC member on 8 June 2002, 11:35 p.m., in response to message #1 by Ex-PPC member
Thanks to all those people that posted and/or were interested in this thread. This time there
were fewer solutions given and no HP-calc code was produced, but I hope that at
least you enjoyed the challenged. Now, just some final notes:
- Mr. Ioannidis was able to find the maximum value for the 3x3 determinant, 412. This
is indeed correct.
- The minimum *non-zero* value es 1. One such arrangement is:
| 1 2 3 |
| 7 5 8 | = 1
| 4 6 9 |
- The minimum *non-zero* value for the 4x4 determinant is also 1. One solution is:
| 1 2 3 4 |
| 5 6 7 9 |
| 8 10 11 12 | = 1
| 16 15 13 14 |
A more economic notation for the above solution is:
det(1,2,3,4,5,6,7,9,8,10,11,12,16,15,13,14) = 1
- As for the additional, miscellaneous questions, here are two solutions:
det(1,2,3,4,5,6,16,8,12,15,10,9,14,7,11,13) = 4000
det(1,2,3,4,5,8,14,6,11,16,9,10,15,7,12,13) = 4444
- Finally, the solution to the maximum value for the 4x4 determinant, I'll leave
that for you. For instance, the following arrangement gives a suitably high value,
but ... is it the maximum possible value ? That's for you to find out:
det(16,9,7,4,8,1,13,11,3,12,15,5,6,10,2,14) = 39030
- Also, many of you were interested in recursion. Actually, it has little to do
with this challenge, as the most efficient procedure does not entail using recursion
at all, but it is an interesting topic in itself.
As was stated, some HP calculators do support recursive procedures natively, such
as the 71B BASIC, which supports recursive subprograms and user defined functions, and
also the RPL models, which by the very nature of their programming model being based
on a stack do also permit recursion very easily.
What to do when a programming language does not support recursion ? Simple, you fake it.
For instance, in the 41C normal recursion would be limited to 6 levels deep if using
XEQ. So the answer lies in not using XEQ (or GOSUB, GSB, etc. in other HP models), which
uses the internal, limited return stack, but simply to use that much-dreaded instruction,
GOTO (GTO, etc), together with a fake "return stack", created and maintained by ourselves,
typically in some structure like an array, or some suitable registers put aside for this.
Does this sound difficult, or does it require complex, lengthy programming to achieve it ?
Far from it, it's extremely simple, almost trivial. It has been mentioned here that the
"Towers of Hanoi" program would be a suitable test case, and it is. As an example, suppose
we were to implement this using a version of BASIC that does not support recursion.
As the only HP calculator that includes BASIC is the HP-71B and it does support recursion,
let's use some other version, say the most simple, limited BASIC of them all, the one used
in a famous contemporary of the HP-41C, the original Tandy Radio Shack TRS-80 Pocket Computer (exact clone of the Sharp PC-1211 Pocket Computer).
This is a perfect machine for the experiment, as its BASIC is as simple as it gets,
it has only 1.4 Kb of memory, and very few commands, not even multiple arrays or two-dimensional
arrays.
Well, in such limited machine/language you can use the simulated-return technique to program the entire
"Towers of Hanoi", simulated recursion and all, in just *six* (6) lines of BASIC. That qualifies
as absolutely trivial. You can try the technique in your favorite HP calc as well, see how
many lines/steps/bytes does it take you to program ToH simulating recursion.
You can test your program running this example, which on the TRS-80 PC-1 goes like this (N is
the number of disks, limited only by available memory, i.e: more than 50 disks possible)
RUN
N=3
FROM 1 TO 3
FROM 1 TO 2
FORM 3 TO 2
FROM 1 TO 3
FROM 2 TO 1
FROM 2 TO 3
FROM 1 TO 3
DONE
|