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.


 
// Langton's ant  F#   https://rosettacode.org/wiki/Langton%27s_ant
 
// A list of cells which are black is maintained and then printed out at the end
 
type Cell = { X : int; Y : int }  
type Direction = | North | South | East| West // direction the ant is facing
 
let withinBounds (dim:int) (cell: Cell) = // ant's cell within dimensions ?
    cell.X < dim && cell.Y < dim && cell.X >= 0 && cell.Y >= 0  
 
let rotateLeft (currentDirection: Direction) =
    match currentDirection with 
        | North -> West | South -> East | East -> North | West -> South
 
let rotateRight (currentDirection: Direction ) =
    match currentDirection with 
        | North -> East | South -> West | East -> South | West -> North 
 
let nextCell (dir:Direction) (cell: Cell) = // compute next cell based on the direction
    match dir with
        | North -> {cell with Y = cell.Y + 1 }
        | South -> {cell with Y = cell.Y - 1 }
        | East ->  {cell with X = cell.X + 1 }
        | West ->  {cell with X = cell.X - 1 } 
 
let isBlackCell (blackCells: Cell list) (cell:Cell) =
    blackCells |> List.exists ( fun c -> c = cell)
 
let toggleCellColor (blackCells: Cell list) (cell: Cell) =
     if cell |> isBlackCell blackCells
     then blackCells |> List.where( fun c -> c <> cell) // remove the cell from list of black cells
     else cell::blackCells // add the cell to the list of black cells
 
let moveToCell (blackCells: Cell list) (currentDir : Direction) (cell: Cell) =
    let ndir = if cell |> isBlackCell blackCells  // next step direction is computed
                    then rotateLeft currentDir
                    else rotateRight currentDir
    let nlst  = cell |> toggleCellColor blackCells // next step updated list of black cells is computed
    let ncell = cell |> nextCell ndir  // next step cell is computedd
    (nlst, ndir, ncell) // return next step list of black cells, direction it will enter the cell, new cell 
 
let rec doStep (dim:int) (blackCells: Cell list) (dir : Direction) (cell: Cell) = 
        let (nlst, ndir, ncell) = moveToCell blackCells dir cell
        if withinBounds dim ncell // check if the next step is within bounds
            then doStep dim nlst ndir ncell // recursive call to next step
            else nlst, ndir, ncell
 
[<EntryPoint>]
let main _ =
   let dim = 100
   let (blacklist, _, _) = doStep dim []  North { X = dim/2 ; Y = dim/2 } // start with empty blacklist, facing north in the center
 
    // print out by row, 0th row is at the bottom
   seq { for row in [dim-1..-1..0] do for col in [0..dim-1]  -> (col,row) }
        |> Seq.iter (fun (row,col) -> if {X = row; Y = col } |> isBlackCell blacklist 
                                        then printf "#"  else printf " "
                                      if row = (dim - 1 )
                                        then printf "\n"  else  ()
                    )
   0 
 
 