TAOCP 2.1 Exercise 9

The pile of cards is represented as a linked list, with `TOP` pointing to the first node and `NEXT` giving the link to the next node.

taocpmathematicsalgorithmsvolume-1medium

Section 2.1: Introduction

Exercise 9. [23] Write a MIX program that prints out the alphabetic names of the current contents of the card pile, starting at the top card, with one card per line, and with parentheses around cards that are face down.

Verified: no
Solve time: -

Solution

The pile of cards is represented as a linked list, with TOP pointing to the first node and NEXT giving the link to the next node. Exercise 6 shows that if CARD ← NODE(TOP) has been executed, then SUIT(CARD) refers to the suit of the top card; therefore the fields of a node may be copied into an ordinary variable and examined there. Exercise 7 shows that field specifications such as TOP(NEXT) are used to access link fields stored in memory.

The program should therefore proceed as follows. Starting with the node whose address is TOP, repeatedly:

  1. Copy the current node into a variable CARD.
  2. Print the alphabetic name of the card.
  3. If the card is face down, surround the printed name by parentheses.
  4. Replace the current node by its successor, NEXT.
  5. Stop when the end of the list is reached.

Since the exercise asks for a MIX program, we express these operations in MIXAL. We assume the conventions of the text for the node structure in Eq. (6), namely that the fields VALUE, SUIT, FACE, and NEXT are present, and that the alphabetic names of cards are available in tables, one for ranks and one for suits. We also assume a standard output unit and that 0 in the NEXT field denotes the end of the pile.

        ORIG    3000

START   LD1     TOP            * I1: current node address in index 1
LOOP    J1Z     DONE           * end of pile?

        LDA     0,1(FACE)      * face up or down?
        JAN     LEFTP          * negative means face down

PRINT   LDA     0,1(VALUE)     * get value field
        CHAR
        OUT     VALTAB(18)

        LDA     0,1(SUIT)      * get suit field
        CHAR
        OUT     SUITAB(18)

NEXTCD  LD1     0,1(NEXT)      * move to next card
        JMP     LOOP

LEFTP   OUT     LPAREN(18)     * print "("

        LDA     0,1(VALUE)
        CHAR
        OUT     VALTAB(18)

        LDA     0,1(SUIT)
        CHAR
        OUT     SUITAB(18)

        OUT     RPAREN(18)     * print ")"
        JMP     NEXTCD

DONE    HLT

TOP     CON     0
LPAREN  ALF     "(   "
RPAREN  ALF     ")   "

        END     START

The register indexed by 1 always contains the address of the current node. At LOOP, the program first tests whether this address is zero; if so, the pile has been exhausted. The FACE field determines whether parentheses are needed. The card name is produced from the VALUE and SUIT fields, one card per line, and after printing the program loads NEXT into index register 1, thereby advancing to the next node in the pile.

$\boxed{\text{The MIX program above prints the contents of the pile from top to bottom, enclosing face-down cards in parentheses.}}$