In my previous blog-post I described a coding convention for the Intel 8048 and used an embedded implementation of the Towers of Hanoi program as an example. It had a rudimentary user interface; outputting merely the column numbers between each step, which advanced on a button press.
Towers of Hanoi is an interesting toy program, and here we explore a different implementation, targeted at a 1K ZX81.
A standard ZX81 has 8K of built-in ROM + 1K of RAM which is shared between the user program (+variables); the 8K ROM's system variables; the 32x24 screen (which expands from 25 bytes to 793 bytes depending on how much is displayed on it); the 33b printer buffer and the machine stack used by the ROM. All this is described in Chapter 27 of the user manual.
So, in some respects it has less usable memory than an Intel 8048 (because 1K + 64b > 1K-system variables-screen...), but in others it has more (because the ROM is useful library code that would have to be included in the Intel 8048 equivalent). In addition, BASIC is generally less compact than assembler (and ZX81 BASIC is even worse).
The Listing
It doesn't look like there's much here, but a surprising amount thought went into it. You can run a javascript version of a zx81 from
here, but many other emulators are available. To prove it will work in 1K, you will need to type
POKE 16389,68 [Newline]
NEW [Newline] to set the RAMTOP top of BASIC to the end of memory on a 1kB ZX81.
It's not obvious how to type the graphics, but the top line is 2 spaces, then ▗ █ ▙ 6 spaces Graphic Shift 5, 6 spaces Graphic Shift 8. The rest can be deduced fairly easily then.
The application will use 634 bytes. An earlier version used a mere 41 bytes more and this was enough to cause an out of memory error.
Using The Screen
The most significant change to the ZX81 version is to use the screen to provide a graphical representation of the puzzle. Because we still need to save space, it's essential to use the ZX81 block graphics (rather than whole characters) and I chose to move a ring by unplotting a ring's old position while plotting its new position rather than, e.g. animating the movement (which would have been very slow on the ZX81 anyway).
In the first version I used loops and plot commands to generate the puzzle, but it uses less memory to print the puzzle out directly. I could save another 4 bytes by assigning the graphics for the spaces and the poles to R$ and substituting R$ at the end of lines 10 to 30.
I also save a bit of space by calculating the minimum pole spacing. It looks like there isn't enough room between poles, but this isn't correct, because at maximum we only ever need space for a 7 pixel wide ring and a 6 pixel wide ring. Therefore 7+1+6+1=15 pixels is enough between the poles.
This means the graphics take up: (8+15+15+7)/2=23 chars for row 4, 22 chars for row 3; 21 chars for row 2 and 20 chars for row 1(because the end of the higher rows are only ever filled with shorter rings). That's 86 bytes in total. The Column->Column moves are also displayed and this takes 4 bytes.
Moving The Rings
This is relatively simple: we have a string, R$, which is used as a byte array (to save space) to hold the number of occupied rings on each column. The width of each ring to move is determined by the current level: 1 for level 0 up to 7 for level 6. S and D determine the start and end coordinate. We plot to the ring we move to, while unplotting the ring we move from except for when x=0 in order to leave the pole. At the end we adjust the number of occupied rings, -1 for the source ring and +1 for the destination ring.
Memory-Saving Techniques
This program uses the normal ZX81 BASIC memory saving techniques. '0', '1' and '3' are replaced by NOT PI, SGN PI and INT PI to save 5 bytes each time. Values in the printable character range are replaced by CODE "x", saving 3 or 4 bytes each time; while other values use VAL "nnn" to save 3 bytes each time. This also applies to line numbers, so that placing the Hanoi function itself below line 1000 saves several bytes.
Using R$ as a byte array involves a number of clumsy VAL, CODE and CHR$ conversions, but replacing R$ with a DIM R(D) array would end up costing another 9 bytes, so it's a net saving to use R$.
Hanoi Algorithm Change
It turns out we can make the Hanoi algorithm itself less recursive than in the Intel 8048 version. In that version we pushed the source and destination columns on each call, but in fact that was done to demonstrate how to manage the data structure.
It's not necessary to do that. The original source and destination values can be restored after each recursive call, because 6-S-D is a reversible operation. Similarly, because L is decremented at the beginning of each call (instead of passing L-1 as a parameter to each call), then by incrementing it at the end of the function, it too, doesn't need to be saved.
Conclusion
The constraints and capabilities of running Hanoi on a different platform and language present challenges and opportunities which this ZX81 implementation amply demonstrates, not in the least by the 4:30 minutes of patience needed to fully run it for 7 rings (vs <1s for the Intel 8048 version). Finally, this implementation circumvents the ZX81 BASIC's lack of support for stack data structures to reduce the amount of recursive memory needed, which begs the question: how much recursion is really needed to implement the algorithm?
