Langton's ant

Implementation of Langton's ant route.. Takes first 1000 steps and returns only black fields.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69:

type Color =  Black | White
type Direction =  Up | Down | Left | Right
type Position = { X : int; Y : int }
type Field = { Pos : Position; Color : Color }
type Ant = {  Pos : Position; Direction : Direction }

module Utils = 
    let toTuple position = (position.X, position.Y)    
    let fromTuple position = { X = fst position; Y = snd position }
    let toLeft       = function | Up -> Left | Right -> Up | Down -> Right | Left -> Down
    let toRight      = function | Up -> Right | Right -> Down | Down -> Left | Left -> Up
    let invert = function
        | f when f.Color = Black -> {f with Color=White }
        | f                      -> {f with Color=Black }
    let move position = function
        | Up    -> {position with Y=position.Y+1}
        | Right -> {position with X=position.X+1}
        | Down  -> {position with Y=position.Y-1}
        | Left  -> {position with X=position.X-1}

module Board = 
    open Utils
    let getColor field = field.Color
    let getField (fields:Map<int*int,Field>) position =
        match fields.TryFind(position) with
        | Some(f) -> f
        | None    -> { Pos = fromTuple position; Color = White }
    let getNewDirection ant color = 
        let fn = match color with 
                 |White -> toRight
                 |Black -> toLeft
        fn ant.Direction
    let move ant newDirection =
        { Direction = newDirection; Pos = move ant.Pos newDirection },      // new ant
        ant                                                             // old ant
open Utils
open Board


let printFields (fields:Map<int*int,Field>) =
    seq { for k in fields -> k.Key, (sprintf "[%d,%d]-%A" k.Value.Pos.X k.Value.Pos.Y k.Value.Color) }
    |> Seq.sortBy fst
    |> Seq.map snd
    |> String.concat ", "
    
let makeStep (ant:Ant) (fields:Map<int*int,Field>) =
    toTuple ant.Pos
    |> getField fields
    |> getColor
    |> getNewDirection ant
    |> move ant

let rec antRoute ant fields = 
    seq {
        let newAnt, oldPosition = match makeStep ant fields with
                                  | newAnt, oldAnt -> newAnt, (toTuple oldAnt.Pos)
        let invertedField = oldPosition |> getField fields |> invert
        yield invertedField
        yield! antRoute newAnt (fields.Add(oldPosition, invertedField))
    }

// go
let ant = { Pos = {X=0; Y=0;}; Direction = Up }
antRoute ant Map.empty
    |> Seq.take 1000 
    |> Seq.filter (fun f -> f.Color = Black)
    |> Seq.toList
    |> List.sortBy (fun f -> f.Pos)
    |> List.iter (fun f -> printfn "[%d,%d]-%A" f.Pos.X f.Pos.Y f.Color)

union case Color.Black: Color

union case Color.White: Color

type Direction =
  | Up
  | Down
  | Left
  | Right

Full name: Script.Direction

union case Direction.Up: Direction

union case Direction.Down: Direction

union case Direction.Left: Direction

union case Direction.Right: Direction

type Position =
{X: int;
Y: int;}

Full name: Script.Position

Position.X: int

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

Position.Y: int

type Field =
{Pos: Position;
Color: Color;}

Full name: Script.Field

Field.Pos: Position

Multiple items
Field.Color: Color

--------------------
type Color =
| Black
| White

Full name: Script.Color

type Ant =
{Pos: Position;
Direction: Direction;}

Full name: Script.Ant

Ant.Pos: Position

Multiple items
Ant.Direction: Direction

--------------------
type Direction =
  | Up
  | Down
  | Left
  | Right

Full name: Script.Direction

val toTuple : position:Position -> int * int

Full name: Script.Utils.toTuple

val position : Position

val fromTuple : int * int -> Position

Full name: Script.Utils.fromTuple

val position : int * int

val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst

val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd

val toLeft : _arg1:Direction -> Direction

Full name: Script.Utils.toLeft

val toRight : _arg1:Direction -> Direction

Full name: Script.Utils.toRight

val invert : _arg1:Field -> Field

Full name: Script.Utils.invert

val f : Field

Field.Color: Color

type Color =
| Black
| White

Full name: Script.Color

val move : position:Position -> _arg1:Direction -> Position

Full name: Script.Utils.move

module Utils

from Script

val getColor : field:Field -> Color

Full name: Script.Board.getColor

val field : Field

val getField : fields:Map<(int * int),Field> -> int * int -> Field

Full name: Script.Board.getField

val fields : Map<(int * int),Field>

Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>

member Map.TryFind : key:'Key -> 'Value option

union case Option.Some: Value: 'T -> Option<'T>

union case Option.None: Option<'T>

val getNewDirection : ant:Ant -> color:Color -> Direction

Full name: Script.Board.getNewDirection

val ant : Ant

val color : Color

val fn : (Direction -> Direction)

Ant.Direction: Direction

val move : ant:Ant -> newDirection:Direction -> Ant * Ant

Full name: Script.Board.move

val newDirection : Direction

module Board

from Script

val printFields : fields:Map<(int * int),Field> -> string

Full name: Script.printFields

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val k : System.Collections.Generic.KeyValuePair<(int * int),Field>

property System.Collections.Generic.KeyValuePair.Key: int * int

val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf

property System.Collections.Generic.KeyValuePair.Value: Field

module Seq

from Microsoft.FSharp.Collections

val sortBy : projection:('T -> 'Key) -> source:seq<'T> -> seq<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.sortBy

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

module String

from Microsoft.FSharp.Core

val concat : sep:string -> strings:seq<string> -> string

Full name: Microsoft.FSharp.Core.String.concat

val makeStep : ant:Ant -> fields:Map<(int * int),Field> -> Ant * Ant

Full name: Script.makeStep

val antRoute : ant:Ant -> fields:Map<(int * int),Field> -> seq<Field>

Full name: Script.antRoute

val newAnt : Ant

val oldPosition : int * int

val oldAnt : Ant

val invertedField : Field

member Map.Add : key:'Key * value:'Value -> Map<'Key,'Value>

val ant : Ant

Full name: Script.ant

val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty

val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take

val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.filter

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sortBy

val iter : action:('T -> unit) -> list:'T list -> unit

Full name: Microsoft.FSharp.Collections.List.iter

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/aZ
Posted:	12 years ago
Author:	stejcz
Tags:	sample , learning f# , wiki , algorithm