Copy that solution

Question

This copy machine program prints the solution to a well-known puzzle.  Explanation of the syntax will follow.

• What solution will be printed for which well-known puzzle?

 EXECUTION CODE

 .-->  LoopA-1: (LoopB-4:)          'LoopA-1' --> ExecutionLocation  ; halt/hang
|
|.-->  LoopA:   (LoopB-3:)        Decremented --> DecrementMe
|      LoopA+1:                   Decremented --> NegativeDoubleMe
|      LoopA+2:                          '-1' --> IncrementMe
|
|.-->  LoopB through LoopB+8:                no-op                   ; 9 no-ops
|.-->  LoopB+9:               @ RemainderBy48 --> PrintMe
|
|      LoopB+10:              NegativeDoubled --> NegativeDoubleMe
|      LoopB+11:             AddedLoopBPlus11 --> Subtract4TimesFromMe
|      LoopB+12:             Subtract4TimesMe --> IncrementMe
`----  LoopB+13:             Subtracted4Times --> ExecutionLocation  ; loop back

 VARIABLES, MOSTLY AUTOMATIC    (initial values given, final values in comments)

    ExecutionLocation:     LoopA      ; ..., LoopB+13, LoopA-1: execution begins
                                      ;   at LoopA and halts (hangs) at LoopA-1

          DecrementMe:       17       ; ...,     4,        3,        2
          Decremented:       16       ; ...,     3,        2,        1
           LimitedBy2:        2       ; ...,     2,        2,        1
     AddedLoopBPlus11:    LoopB+13    ; ..., LoopB+13, LoopB+13, LoopB+12

     NegativeDoubleMe:       15       ; ..., -2,  4, -8
        RemainderBy48:       15       ; ..., -2,  4, -8:  same-sign remainder of
                                      ;   NegativeDoubleMe's value divided by 48
      NegativeDoubled:      -30       ; ...,  4, -8. 16

          IncrementMe:       -1       ; ...,     1,        2,        3
     Subtract4TimesMe:        0       ; ...,     2,        3,        4
 Subtract4TimesFromMe:    LoopB+13    ; ..., LoopB+12, LoopB+12, LoopB+12
     Subtracted4Times:    LoopB+9     ; ..., LoopB+4,  LoopB,    LoopA-1

              PrintMe:       ""       ; contents are printed and reset to ""
                                      ;    ("" = empty text = print nothing)

 TEXT CONSTANTS TO BE PRINTED    (numerical addresses of these locations matter)

                  -40:    " Cll"
      -39 through -25:       ""
                  -24:     " Ar"
       -23 through -9:       ""
                   -8:     " Br"
         -7 through 7:       ""
                    8:    " Arr"
         9 through 23:       ""
                   24:     " Bl"
        25 through 39:       ""
                   40:     " Cl"
        41 through 44:       ""

  Explanation of syntax

 TYPICAL INSTRUCTION, COPIES THE VALUE AT ONE LOCATION TO ANOTHER LOCATION

      LoopB+13:          Subtracted4Times --> ExecutionLocation     ; loop back
      ---------          ----------------     -----------------     -----------
    location whose       copy the value at     copy that value        comment
   numerical address       this ocation        to this location
 is not -40 through 44


 INSTRUCTIONS WITH BUILT-IN CONSTANTS

  LoopA-1:    (LoopB-4:)        'LoopA-1' --> ExecutionLocation     ; halt/hang
  LoopA+2:                           '-1' --> IncrementMe
  --------    ----------        ---------     -----------------     -----------
  location    equivalent      directly copy   copy that constant        comment
   whose       location       the constant     to this location
  numerical                between ' ' quotes,
  address is                 with no look-up
 not -40 through 44


 LOCATIONS WITH TEXT CONSTANTS

             -40:           " Cll"
 -39 through -25:              ""
 ----------------           ------
  location whose             text
 numerical address        constant to
   is specific            be printed

                    location(s) whose numerical address is explicit

       LoopB+9:               @ RemainderBy48 --> PrintMe
                    ( @ RemainderBy48 means: FROM Location is specified by
                                          the value found at RemainderBy48 )

Answer 1

Your program solves

the Towers of Hanoi (with four discs). I remark that this was an easy guess just from the string constants. Three letters A,B,C, and letters l,r. A,B,C must represent positions rather than discs, in order left to right. (They can't be discs because when solving the ToH each disc always moves in the same direction. But making them be positions makes a lot of sense. So e.g. Arr means to move the top thing from position A two places right, to C.)

OK, so let's proceed.

I assume that the name ExecutionLocation is to be taken seriously: this is the program counter, and what the machine does at each step is to look up the instruction found there and obey it.
So, if this ever gets the value LoopA-1 then, as the comment says, execution will halt or more precisely spin around in circles.
And a superficial top-level view of the computation is: we start at LoopA and repeatedly run through to LoopB+13, at which point we return to a location determined by the current value of Subtracted4Times and once again run forward to LoopB+13. Obviously this may perform different-but-related calculations depending on just how far back we jump each time.

The instructions are not perfectly explicit about this, but

when V is the name of a variable, "--> V" means to change the value of the variable rather than to write to the address given by the current value of the variable.

And the instructions are even less explicit about this, but

these "automatic variables" are actually doing some magic. It operates on the various groups of variables listed in the table, so that e.g. when you set DecrementMe this sets the values of Decremented, LimitedBy2, and AddedLoopBPlus11, in that order and in the obvious way given their names. The increment/subtract group is a bit different from the others, having two "inputs"; when you set IncrementMe, the incremented value goes into Subtract4TimesMe, and that when either Subtract4TimesMe or Subtract4TimesFromMe changes, we update Subtracted4Times.

I shall refrain from spoilering literally everything in what follows, to reduce clutter a bit. I'll try to hide the things that give the most away.

I'm going to give the variables shorter names:

dec Decremented
lim LimitedBy2
add AddedLoopBPlus11
rem RemainderBy48
neg NegativeDoubled
sub Subtract4TimesMe
frm Subtract4TimesFromMe
sbt Subtracted4Times

So. Let's put A at location 1000 (so B is at 1003). If, as at the start of execution, we begin at A then here is what happens; each row shows the state of things after doing the operation on that row. x is the value of Decremented when we arrive at A; iniitially it's 16.

1000 : dec := dec-1, lim := min(2,dec-1), add := 1014 + min(2,dec-1)
1001 : rem := dec rem 48, neg := -2*dec
1002 : sub := 0, sbt set to whatever it is [it'll change before it's next used]
1003 : nop
1004 : nop
1005 : nop
1006 : nop
1007 : nop
1008 : nop
1009 : nop
1010 : nop
1011 : nop
1012 : output string number rem
1013 : rem := neg rem 48, neg := -2*neg
1014 : frm := add, [sbt := frm-4*sub but this is always overwritten before next use]
1015 : sub := sub+1, sbt := frm-4*sub
1016 : go back to location sbt

It looks as if for most of the program's execution we're going to have dec large enough that add=1016, and we're going to return to location 1000 quite often. So let's analyse what happens in those cases.

Suppose we start at 1000 with dec=x+1, and suppose dec >= 3. Then successively we do: dec=x, lim=2, add=1016, rem=x rem 48, neg=-2x, sub=0, output string number (x rem 48), rem=-2x rem 48, neg=4x, frm=1016, sub=1, sbt=1012.

Now we return to 1012 and do a lot of that again: output string (-2x rem 48), rem=(4x rem 48), neg=-8x, frm=1016, sub=2, sbt=1008.

Now we return to 1008 and do a lot of that again: output string (4x rem 48), rem=(-8x rem 48), neg=16x, frm=1016, sub=3, sbt=1004.

And again: output string (-8x rem 48), rem=(16x rem 48), neg=-32x, frm=1016, sub=4, sbt=1000.

And now we get back to location 1000 where we will be subtracting 1 from x, so before we look at what that does let's see what the net effect of all this has been.

We have output strings x, -2x, 4x, -8x mod 48, which turns out to mean that if x=0 or x=16 we output nothing, and that if 1 <= x <= 15 we output just one thing, which in descending order of x starting at 15, goes: Ar Arr Br Ar Cll Cl Ar Arr Br Bl Cll Br Ar Arr Br. This does in fact solve the Towers of Hanoi starting with 4 discs in position A.

Let's have a bit more insight into what's going on here; that sequence isn't some arbitrary thing that humn has found a random way to obfuscate.

Here's one way to describe

how to solve the ToH. Number your moves from 1. On odd-numbered moves, move the smallest disc, in a consistent direction. On even-numbered moves, perform a solution of the ToH without that smallest disc, in the opposite direction. (So this is a recursive description.)

Now, the locations that have nonempty strings in are +- 8, 24, 40; that is, the odd numbers times 8. So if we start with any x that isn't already a multiple of 16 and negate-and-double it a few times, exactly one of the numbers we get will be one of these. Note also that

we have "r" or "ll" -- i.e., a "clockwise" movement -- in negative positions, and "l" or "rr" -- i.e., an "anticlockwise" movement -- in positive ones. The number of negations we do depends on the parity of the number of 2s dividing x, which matches the way that alternating discs move in alternating directions.

After how many negate-and-double operations will we reach an index with a nonempty string -- that is, one that's an odd multiple of 8? If x is odd, it will be after 3 such operations; if x is twice an odd number, it will be after 2; if x is 4x an odd number, it will be after 1; if x is already an odd multiple of 8, it will be before we do any negate-and-double operations. (It never happens that x is already a multiple of 16.) That is:

On odd-numbered turns, where x is 15,13,...,1, we'll negate-and-double three times before printing. The index will be minus (8 times 15,13,...,1 mod 48), which yields a repeating sequence of -24, -8, -40. That's Ar, Br, Cll. So: on the first turn we move the smallest disc from A to B, on the third we move it from B to C, on the fifth we move it from C to A, etc. On odd turns the smallest disc moves clockwise.
On twice-odd-numbered turns, where x is 14,10,...,2, we'll negate-and-double only twice before printing. This gives us the repeating sequence +8,+40,+24, or Arr, Cl, Bl. On twice-odd turns the second disc moves anticlockwise.
On 4x-odd-numbered turns, we get the same sequence as for odd turns. On 4x-odd turns the third disc moves clockwise.
And on 8x-odd-numbered turns (there is only one), we get the same sequence as for even turns. On 8x-odd turns the fourth disc moves anticlockwise.

We're almost done, except that all the program analysis above assumes that x isn't small. What happens once that "limit-by-2" operation yields 1 or 0?

It yields 1 when x=1; that is, when we arrive at location 1000 with dec=2. This is our last move in the game. Instead of going to locations 1012, 1008, 1004, 1000, we will therefore go to locations 1011, 1007, 1003, 999. The first three of these behave exactly the same as their successors, so actually everything proceeds as before. And finally, instead of returning to 1000 we go to 999, where we spin for ever.