source: branches/HeuristicLab.Problems.GPDL/Examples/LawnMower.txt @ 11023

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<<MowerState state>>. 
  Sum<<out int x, out int y>>.
  Expr<<out int x, out int y>>. /* helper for expressions containing const and sum */
  Frog<<MowerState state>>.
  Prog2<<MowerState state>>.

TERMINALS
  Left.
  Forward.
  Const<<out int x, out int y>>
    CONSTRAINTS
      x IN SET <<ints; >> /* x \in [-100, 100] */
      y IN SET <<ints; >> /* y \in [-100, 100] */
  .

RULES
  LawnMower<<MowerState state>> = 
    Prog2<<state>>
    | Frog<<state>>
    | Left                                             SEM << state.TurnLeft(); >>
    | Forward                                          SEM << state.Forward(); >>
  .
    
  Sum<<out int x, out int y>> =                        LOCAL << int x1, y1, x2, y2; >>
    Expr<<out x1, out y1>>
    Expr<<out x2, out y2>>                             SEM << x = x1 + x2; y = y1 + y2; >>
  .

  Expr<<out int x, out int y>> =
    Const<<out x, out y>>
    | Sum<<out x, out y>>
  .

  Prog2<<MowerState state>> = 
    LawnMower<<state>> 
    LawnMower<<state>>
  .
  
  Frog<<MowerState state>> =                          LOCAL << int x; int y; >>
     Expr<<out x, out y>>                             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.