Langton's ant is a cellular automaton that models an ant sitting on a plane of cells, all of which are white initially, the ant facing in one of four directions.

Each cell can either be black or white.

The ant moves according to the color of the cell it is currently sitting in, with the following rules:

   If the cell is black, it changes to white and the ant turns left;
   If the cell is white, it changes to black and the ant turns right;
   The ant then moves forward to the next cell, and repeat from step 1.

This rather simple ruleset leads to an initially chaotic movement pattern, and after about 10000 steps, a cycle appears where the ant moves steadily away from the starting location in a diagonal corridor about 10 cells wide.
Conceptually the ant can then walk infinitely far away.



Task

Start the ant near the center of a 100x100 field of cells, which is about big enough to contain the initial chaotic part of the movement.

Follow the movement rules for the ant, terminate when it moves out of the region, and show the cell colors it leaves behind.



The problem has received some analysis; for more details, please take a look at the Wikipedia article   (a link is below)..



See also

   Wikipedia:   Langton's ant.


Related task

   Rosetta Code:   Conway's Game of Life.


BEGIN
    # size of board for Langton's ant #
    INT max board = 100;
    [ 1 : max board, 1 : max board ]CHAR board;
    # start with the board all white #
    CHAR white = " ", black = "#";
    FOR r TO 1 UPB board DO FOR c TO 2 UPB board DO board[ r, c ] := white OD OD;
    # possible ant directions #
    INT head left = 0, head up = 1, head right = 2, head down = 3;
    # returns the new direction if we turn left from curr direction #
    OP LEFT = ( INT curr direction )INT:
       IF   curr direction = head left  THEN head down
       ELIF curr direction = head down  THEN head right
       ELIF curr direction = head right THEN head up
       ELSE                                  head left
       FI ; # LEFT #
    # returns the new direction if we turn right from curr direction #
    OP RIGHT = ( INT curr direction )INT:
       IF   curr direction = head left  THEN head up
       ELIF curr direction = head up    THEN head right
       ELIF curr direction = head right THEN head down
       ELSE                                  head left
       FI ; # RIGHT #
    # move the ant until it leaves the board #
    INT ant row := max board OVER 2;
    INT ant col := max board OVER 2;
    INT ant direction := head up;
    INT max row := 1;
    INT max col := 1;
    INT min row := max board;
    INT min col := max board;
    INT moves := 0;
    WHILE ant row >= 1 LWB board AND ant row <= 1 UPB board
      AND ant col >= 2 LWB board AND ant col <= 2 UPB board
    DO
        moves +:= 1;
        IF ant row > max row THEN max row := ant row FI;
        IF ant col > max col THEN max col := ant col FI;
        IF ant row < min row THEN min row := ant row FI;
        IF ant col < min col THEN min col := ant col FI;
        IF board[ ant row, ant col ] = white THEN
            # ant turns right on a white square #
            ant direction := RIGHT ant direction;
            board[ ant row, ant col ] := black
        ELSE
            # ant turns left on a black square #
            ant direction :=  LEFT ant direction;
            board[ ant row, ant col ] := white
        FI;
        # move the ant #
        IF     ant direction = head up    THEN ant row -:= 1
        ELIF   ant direction = head down  THEN ant row +:= 1
        ELIF   ant direction = head left  THEN ant col -:= 1
        ELSE # ant direction = head right #    ant col +:= 1
        FI
    OD;
    # show resultant position #
    print( ( "After ", whole( moves, 0 ), " moves."
           , " Showing rows ", whole( min row,0 ), " to ", whole( max row, 0 )
           , " columns ", whole( min col,0 ), " to ", whole( max col, 0 )
           , newline
           )
         );
    FOR r FROM min row TO max row DO
        print( ( board[ r, min col : max col ], newline ) )
    OD
END