2 people like it.

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: 

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 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 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
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 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
module Seq

from Microsoft.FSharp.Collections
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

More information

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

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.