FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE:
MoveTower(disk - 1, source, spare, dest)
move disk from source to dest
MoveTower(disk - 1, spare, dest, source)
END IF
Previously, I succeeded doing this for the Microtronic - the Microtronic doesn't offer a native stack, nor programmatic access to the RAM! RAM is only for program memory (-> Harvard Architecture), and writable memory is register memory only. So implementing a stack for recursion is not so straight forward, but it is possible by shifting its set of 16 "extra registers" up and down to emulate push and pop operations to a stack (altogether, the Microtronic has 2x 16 4bit registers):
Also, there are no computed or "indirect" jumps - it is not possible to put a return address in a register (or memory) location and simply jump "indirectly" to the address stored there.
Hence, I used numeric jump labels and something I called a "jump block" - to do a computed jump (i.e., a return from a recursive call or subroutine to a variable address), I am comparing a register that I set up to act as "return" register to these numeric jump labels and execute conditional jumps accordingly. Putting the 2 techniques together I was then able to implement both a value and a return stack and hence could execute the recursive version of the towers of Hanoi for up to n=4 disks; you can find the Microtronic program here to get the idea: https://github.com/lambdamikel/picoram2090/blob/main/software/1.1/HANOI.MIC
Would the same techniques work for the Science Fair? In particular, since the Science Fair offers indexed memory access - load & store to the data region from 0x50 - 0x5F via the Y "index" register is possible, using the op-codes `AM (4)` and `MA (5)`, I though at least the stack implementation should be much more straight forward:
4 | AM | 4 | M(Y) <- A
5 | MA | 5 | A <- M(Y)
And indeed, using the Y-register as index into the data region, and being able to do "stack arithmetics" using the `AIY (B)` op-code
B | AIY n | B n | Y <- Y + n
worked like a charm - much more straight-forward than on the Microtronic!
Like with the Microtronic, "computed" jumps to computed target addresses stored in memory or a register are impossible, so I require the same "jump block" mechanism for the Science Fair as well.
Unfortunately, I ran out of program space on the Science Fair - I would have needed exactly 15 more nibbles! My program overlaps with the data region (from 0x50 on) that I would need for the (value and return) stack - but in principle, the ideas are sound, and it should work (if I only had more space...)
But here is the program so far:
// CONCLUSIONS - DOESN'T HAVE ENOUGH MEMORY :-(
// JUMP BLOCK OVERLAPS DATA REGION (50... )
//
// Towers of HANOI on the Science Fair Microcomputer Trainer
// (C) 2024 by LambdaMikel
//
// Memory and registers need to be set up manually:
//
// 1. Load n = 1, 2, 3, 4 into B (@ 6C)
// 2. Point Y (@ 6E) to 53
// 3. Load Label 0 into 53
//
// 4. Set up first stack frame by hand:
// 50 = SOURCE : A
// 51 = DEST : C
// 52 = SPARE : B
// 53 = RET : 0
//
//
// MoveTower(n, source, dest, spare)
//
00 2 CH GET n value from B: A <- B
01 C CIA 1 A <> 1 ? -> FLAG = 1, JUMP REC. CASE
02 F JUMP REC CASE @ OB - JUMP executed when FLAG = 1 (A <> 1)
03 0
04 B
// A = 1
// Base case
// Y points to RET label
// move disk from source to dest
// no mem space for output! only n display
05 1 A0 HEX DISP
06 2 CH Store n value back into B: A -> B
07 F JUMP JUMP BLOCK @ 50
08 5
09 0
// A > 1
// Recursive case
// Y points to RET label
// Compute n - 1 by adding F (= Sub 1)
0A 9 AIA F (= SUB 1)
0B F
0C 2 CH Store A = n-1 into B: A -> B
// Prepare first recursive call:
//
// MoveTower(disk-1, source, spare, dest)
// Stack:
// <50, 51, 52, 53>
// Y points to 53
//
// SOURCE <- SOURCE
// DEST <- SPARE
// SPARE <- DEST
// Subtract 1 from Y, 53 -> 52
// Load A with cur. SPARE (= 52)
0D B AIY Y <- Y + F (= Y - 1)
0E F
0F 5 MA A <- M(Y = 52 = SPARE)
// Store cur. SPARE into new DEST (55 = 52 + 3)
// DEST <- SPARE
10 B AIY Y <- Y + 3
11 3
12 4 AM A -> M(Y = 52 + 3 = 55)
// SPARE (56) <- DEST (51)
// FROM 55 to 51: SUB 4 = ADD C
13 B AIY Y <- Y + C (= -4)
14 C
15 5 MA A <- M(Y = 51 = DEST)
// Store cur. DEST into new SPARE (56 = 51 + 5)
16 B AIY Y <- Y + 5
17 5
18 4 AM A -> M(Y = 51 + 5 = 56)
// Load cur. SOURCE (50) into new SOURCE (54)
19 B AIY Y <- Y + A (= -6)
1A A
1B 5 MA A <- M(Y = 56 - 6 = 50)
// Store cur. SOURCE into new SOURCE (54 = 50 + 4)
1C B AIY Y <- Y + 4
1D 4
1E 4 AM A -> M(Y = 50 + 4 = 54)
// Set up new RET label 1 (1 -> @ 57 = JUMP to 28)
1F B AIY Y <- Y + 3 (57 = 54 + 3)
20 3
21 8 TIA 1
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.