⟦dd4be835b⟧

TextFile

           
           
             =============================================

              A FIRST ADA PROGRAM: BUILDING MAGIC SQUARES
            
             =============================================
           
           


This  is  an  exercise intended to be the very first program written the
first day of a hands-on Ada course.

The pre-requisites, and therefore the language elements it illustrates are:
   compilation units
   simple packages and package bodies, with clauses
   simple object declaration, enumeration types, simple array declaration
   simple statements: assignments, loops, procedure calls
   
   
---------------------------- 
Here  is  an  abstraction  of a square, or a checker board, on which one
wants to move a cursor and deposit tokens numbered from  1  to  N.  This
abstraction  is  expressed  under  the  form  of  the  following package
specification (built step by step in front of the students):

package Square is
    Size : constant := 5; -- dimension must be an odd number
    type Direction is (North, South, East, West, North_East,
                       North_West, South_East, South_West);
    procedure Go_To_Center;
    procedure Go (Which_Direction : in Direction);
    function Is_Already_Occupied return Boolean;
    procedure Deposit (Token : Positive);
    procedure Display;
end Square;

Moreover, this square has the following interesting characteristic: the
edges "wrap-around"; moving the cursor further east when you are at the
most east edge brings it on the west edge.


Using that abstract square or board, we want to build a "magic square". 
A magic square is a n by n square filled with integers from 1 to n**2,
such that all the sums along rows, columns and main diagonals are equals.
For instance:
              8  1  6
              3  5  7
              4  9  2     has the sum 15 in all rows, columns and diag.

A simple algorithm to compute such a magic square, when n is an odd number,
is the following:
  1. Go to the center of the board
  2. Go one step north, and deposit token #1
  3. repeat until all tokens are distributed:
       3.1 Go north-east
       3.2 If box has already received a token, go north_west (repeat if
             necessary)
       3.3 deposit the next token
       
The students are asked:
   1. to complete the body of package Square
   2. to write a 'main' program: procedure magic_square, to implement
          the algorithm

Here is a very simple and naive implementation:

with Square;
use Square;
procedure Magic_Square is
    Token : Positive := 1;
begin
    Go_To_Center;
    Go (North);
    loop
        Deposit (Token);
        exit when Token = Size ** 2;
        Token := Token + 1;
        Go (North_East);  
        while Is_Already_Occupied loop
            Go (North_West);
        end loop;
    end loop;  
    Display;
end Magic_Square;

and for the body of Square:

with Io;
package body Square is
 -- definition of the actual 'checker-board'
    subtype Edge is Natural range 0 .. Size - 1;
    Board : array (Edge, Edge) of Natural := (others => (others => 0));
 -- position of the cursor
    X, Y : Edge := Size / 2;

    procedure Go_To_Center is
    begin
        X := Size / 2;
        Y := Size / 2;
    end Go_To_Center;

    procedure Go (Which_Direction : in Direction) is
    begin
        case Which_Direction is

            when North =>   Y := (Y + 1) mod Size;
            when South =>   Y := (Y - 1) mod Size;
            when East  =>   X := (X + 1) mod Size;
            when West  =>   X := (X - 1) mod Size;
            when North_East => Go (North);
                               Go (East);
            when South_East => Go (South);
                               Go (East);
            when North_West => Go (North);
                               Go (West);
            when South_West => Go (South);
                               Go (West);
        end case;             
    end Go;                   

    function Is_Already_Occupied return Boolean is
    begin
        return Board (X, Y) > 0;
    end Is_Already_Occupied;

    procedure Deposit (Token : Positive) is
    begin
        Board (X, Y) := Token;
    end Deposit;

    procedure Display is
    begin
        for Y in reverse Edge loop
            for X in Edge loop
                Io.Put (Board (X, Y), Width => 3);
            end loop;  
            Io.New_Line;
        end loop;
    end Display;
end Square;

---------------------------------------------

For fast students, who finish before the others, several improvements
or alternative may be investigated:

A. To show the abstraction and information hiding aspect, one may
    wish to substitute another body for the package Square, for instance
    using an uni-dimensional array (see below)
    
B. The Square package is tight to the size 5. Change it in a
   generic package, where Size is a generic parameter, and have
   the procedure generic square instantiate is for various (odd) sizes from
   3 to 13.
   
The code given below implements suggestion A and B simultaneously. Note also
   the non-recursive version of procedure Go.
   
C. Introduce an exception Not_An_Odd_Number in the package Square and 
   check in the package body the parameter Size. Handle the exception in 
   some way in the procedure Magic_square.
   
D. Get rid of the Go_To_Center procedure, which is given initially just 
   for the sake of clarity.
   
E. Adjust automatically the Width parameter in the IO.Put call in the 
   body of Display to fit the largest token value (Size**2).

generic
    Size : in Positive := 5;-- dimension must be an odd number
package Square is
    type Direction is (North, South, East, West, North_East,
                       North_West, South_East, South_West);
    procedure Go_To_Center;
    procedure Go (Which_Direction : in Direction);
    function Is_Already_Occupied return Boolean;
    procedure Deposit (Token : Positive);
    procedure Display;
end Square;

with Io;
package body Square is
    -- definition of the actual 'checker-board' as a vector (just for
    --      the fun of it) with constant specification
    Size_2 : constant Positive := Size ** 2;
    subtype Edge is Natural range 0 .. Size ** 2 - 1;
    Board : array (Edge) of Natural := (others => 0);
    -- position of the cursor
    X : Edge := Size_2 / 2;

    procedure Go_To_Center is
    begin
        X := Size_2 / 2;
    end Go_To_Center;

    procedure Go (Which_Direction : in Direction) is
    begin
        case Which_Direction is
            when North | North_East | North_West =>
                X := (X - Size) mod Size_2;
            when South | South_East | South_West =>
                X := (X + Size) mod Size_2;
            when others =>
                null;
        end case;
        case Which_Direction is
            when East | North_East | South_East =>
                X := ((X / Size) * Size + (((X mod Size) + 1) mod Size));
            when West | North_West | South_West =>
                X := ((X / Size) * Size + (((X mod Size) - 1) mod Size));
            when others =>
                null;
        end case;
    end Go;

    function Is_Already_Occupied return Boolean is
    begin
        return Board (X) > 0;
    end Is_Already_Occupied;

    procedure Deposit (Token : Positive) is
    begin
        Board (X) := Token;
    end Deposit;

    procedure Display is
    begin
        for X in Edge loop
            if X mod Size = 0 then
                Io.New_Line;
            end if;
            Io.Put (Board (X), Width => 4);
        end loop;  
        Io.New_Line;
    end Display;
end Square;

with Square;
procedure Magic_Square is
    procedure Do_A_Magic_Square (Size : in Positive) is  
        package This_Square is new Square (Size);
        use This_Square;
        Token : Positive := 1;
    begin
        Go_To_Center;
        Go (North);
        loop
            Deposit (Token);
            exit when Token = Size ** 2;
            Token := Token + 1;
            Go (North_East);  
            while Is_Already_Occupied loop
                Go (North_West);
            end loop;
        end loop;  
        Display;
    end Do_A_Magic_Square;

begin  
    for Size in 3 .. 13 loop
        if Size mod 2 /= 0 then
            Do_A_Magic_Square (Size);
        end if;
    end loop;
end Magic_Square;

--------------------------------- Et voila !
DataMuseum.dk

Rational R1000/400 Tapes

⟦dd4be835b⟧ TextFile

Derivation

TextFile
