PROBLEM LawnMower /* the lawn mower problem with syntax to enforce that constants and sums are only used * in sub-trees under the "frog" symbol. (Original formulation by Koza did not use a grammar) */ CODE << public static int Width { get { return 16; } } public static int Height { get { return 16; } } enum Direction {West, East, North, South}; class Point { public int x; public int y; public Point(int x, int y) { this.x = x; this.y = y; } } class World { private bool[,] mowed = new bool[Width, Height]; public void SetCellMowed(Point p) { mowed[p.x, p.y] = true; } public bool IsCellMowed(Point p) { return mowed[p.x, p.y]; } } class MowerState { public Point Position { get; set;} public Direction Direction { get; set; } public World World { get; set; } public int Energy { get; set; } public int MowedCells { get; set; } public MowerState() { Energy = 0; MowedCells = 0; } public void TurnLeft() { if (Energy <= 0) return; // don't move when no energy left Energy--; switch(Direction) { case Direction.West: Direction = Direction.South; break; case Direction.South: Direction = Direction.East; break; case Direction.East: Direction = Direction.North; break; case Direction.North: Direction = Direction.West; break; } } public void Forward() { if(Energy <= 0) return; // don't move when no energy left Position = NextPosition; Energy--; if(!World.IsCellMowed(Position)) { World.SetCellMowed(Position); MowedCells++; } } public void Jump(int x, int y) { if(Energy <= 0) return; // don't move when no energy left while(x<0) x += Width; // make sure offset is positive for mod-operation while(y<0) y += Height; Position = new Point((Position.x + x) % Width, (Position.y + y) % Height); Energy--; if(!World.IsCellMowed(Position)) { World.SetCellMowed(Position); MowedCells++; } } public Point NextPosition { get { int x, y; switch(Direction) { case Direction.West: x = (Position.x + Width - 1) % Width; y = Position.y; return new Point(x, y); case Direction.South: x = Position.x; y = (Position.y + Height + 1) % Height; return new Point(x, y); case Direction.East: x = (Position.x + Width + 1) % Width; y = Position.y; return new Point(x, y); case Direction.North: x = Position.x; y = (Position.y + Height - 1) % Height; return new Point(x, y); } return new Point(-1,-1); } } } /* set of possible values for constants [-100, 100] */ int[] ints = Enumerable.Range(-100, 201).ToArray(); >> NONTERMINALS LawnMower<>. Sum<>. Expr<>. /* helper for expressions containing const and sum */ Frog<>. Prog2<>. TERMINALS Left. Forward. Const<> CONSTRAINTS x IN SET <> /* x \in [-100, 100] */ y IN SET <> /* y \in [-100, 100] */ . RULES LawnMower<> = Prog2<> | Frog<> | Left SEM << state.TurnLeft(); >> | Forward SEM << state.Forward(); >> . Sum<> = LOCAL << int x1, y1, x2, y2; >> Expr<> Expr<> SEM << x = x1 + x2; y = y1 + y2; >> . Expr<> = Const<> | Sum<> . Prog2<> = LawnMower<> LawnMower<> . Frog<> = LOCAL << int x; int y; >> Expr<> SEM << state.Jump(x, y); >> . MAXIMIZE << var world = new World(); var state = new MowerState() {Position = new Point(0,0), Energy = 2 * Height * Width, Direction = Direction.South, World = world}; world.SetCellMowed(state.Position); // set initial cell mowed // execute the mower program once LawnMower(state); return (double)state.MowedCells; >> END LawnMower.