Task

Solve the   Towers of Hanoi   problem with recursion.




 
[Towers of Hanoi task for Rosetta Code.]
[EDSAC program, Initial Orders 2.]
 
            T100K   [load program at location 100 (arbitrary)]
            GK
[Number of discs, in the address field]
      [0]   P3F     [<--- edit here, value 1..9]
[Letters to represent the rods]
      [1]   LF      [left]
      [2]   CF      [centre]
      [3]   RF      [right]
 
[Main routine. Enter with acc = 0]
      [4]   T1F     [1F := 0]
      [5]   A5@     [initialize recursive subroutine]
            G104@
            A@      [number of discs]
            T1F     [pass to subroutines]
            A1@     [source rod]
            T4F     [pass to subroutines]
            A3@     [target rod]
            T5F     [pass to subroutines]
     [13]   A13@    [call subroutine to write header ]
            G18@
     [15]   A15@    [call recursive subroutine to write moves ]
            G104@
            ZF      [stop]
 
[Subroutine to write a header]
[Input:  1F = number of discs (in the address field)]
        [4F = letter for starting rod]
        [5F = letter for ending rod]
[Output: None. 1F, 4F, 5F must be preserved.]
     [18]   A3F     [plant return link as usual]
            T35@
            A1F     [number of discs]
            L512F   [shift 11 left to make output char]
            T39@    [plant in message]
            A4F     [starting rod]
            T53@    [plant in message]
            A5F     [ending rod]
            T58@    [plant in message]
            A36@    [O order for first char of message]
            E30@    [skip next order (code for 'O' is positive)]
     [29]   A37@    [restore acc after test below]
     [30]   U31@    [plant order to write next character]
     [31]   OF      [(planted) write next character]
            A2F     [inc address in previous order]
            S37@    [finished yet?]
            G29@    [if not, loop back]
     [35]   ZF      [(planted) exit with acc = 0]
     [36]   O38@    [O order for start of message]
     [37]   O61@    [O order for exclusive end of message]
     [38]   #F
     [39]   PFK2048F!FDFIFSFCFSF!FFFRFOFMF!F
     [53]   PF!FTFOF!F
     [58]   PF@F&F
     [61]
 
[Subroutine to write a move of one disc.]
[Input:  1F = disc number 1..9 (in the address field)]
        [4F = letter for source rod]
        [5F = letter for target rod]
[Output: None. 1F, 4F, 5F must be preserved.]
[Condensed to save space; very similar to previous subroutine.]
     [61]   A3FT78@A1FL512FT88@ A4FT96@A5FT101@A79@E73@
     [72]   A80@
     [73]   U74@
     [74]   OFA2FS80@G72@
     [78]   ZF      [(planted) exit with acc = 0]
     [79]   O81@
     [80]   O104@
     [81]   K2048FMFOFVFEF!F#F
     [88]   PFK2048F!FFFRFOFMF!F
     [96]   PF!FTFOF!F
    [101]   PF@F&F
    [104]
 
[Recursive subroutine to move discs 1..n, where 1 <= n <= 9.]
[Call with n = 0 to initialize.]
[Input:  1F = n (in the address field)]
        [4F = letter for source rod]
        [5F = letter for target rod]
[Output: None. 1F, 4F, 5F must be preserved.]
    [104]   A3F     [plant link as usual ]
            T167@
[The link will be saved in a stack if recursive calls are required.]
            S1F     [load -n]
            G115@   [jump if n > 0]
[Here if n = 0. Initialize; no recursive calls.]
            A169@   [initialize push order to start of stack]
            T122@
            A1@     [find total of the codes for the rod letters]
            A2@
            A3@
            T168@   [store for future use]
            E167@   [jump to link]
[Here with acc = -n in address field]
    [115]   A2F     [add 1]
            G120@   [jump if n > 1]
[Here if n = 1. Just write the move; no recursive calls.]
    [117]   A117@   [call write subroutine]
            G61@
            E167@   [jump to link]
[Here if n > 1. Recursive calls are required.]
    [120]   TF      [clear acc]
            A167@   [load link order]
    [122]   TF      [(planted) push link order onto stack]
            A122@   [inc address in previous order]
            A2F
            T122@
[First recursive call. Modify parameters 1F and 5F; 4F stays the same]
            A1F     [load n]
            S2F     [make n - 1]
            T1F     [pass as parameter]
            A168@   [get 3rd rod, neither source nor target]
            S4F
            S5F
            T5F
    [133]   A133@   [recursive call]
            G104@
[Returned, restore parameters]
            A1F
            A2F
            T1F
            A168@
            S4F
            S5F
            T5F
[Write move of largest disc]
    [142]   A142@
            G61@
[Second recursive call. Modify parameters 1F and 4F; 5F stays the same]
[Condensed to save space; very similar to first recursice call.]
            A1FS2FT1FA168@S4FS5FT4F
    [151]   A151@G104@A1FA2FT1FA168@S4FS5FT4F
[Pop return link off stack]
            A122@   [dec address in push order]
            S2F
            U122@
            A170@   [make A order with same address]
            T165@   [plant in code]
    [165]   AF      [(planted) pop return link from stack]
            T167@   [plant in code]
    [167]   ZF      [(planted) return to caller]
[Constants]
    [168]   PF      [(planted) sum of letters for rods]
    [169]   T171@   [T order for start of stack]
    [170]   MF      [add to T order to make A order, same address]
[Stack: placed at end of program, grows into free space.]
    [171]
            E4Z     [define entry point]
            PF      [acc = 0 on entry]
[end]
 