# source:branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL.Views/3.4/Resources/LawnMower.txt@9872

Last change on this file since 9872 was 9872, checked in by gkronber, 9 years ago

#2026 removed unused files

File size: 4.7 KB
Line
1PROBLEM LawnMower
2/* the lawn mower problem with syntax to enforce that constants and sums are only used
3 * in sub-trees under the "frog" symbol. (Original formulation by Koza did not use a grammar)
4 */
5CODE <<
6  public static int Width { get { return 16; } }
7  public static int Height { get { return 16; } }
8
9  enum Direction {West, East, North, South};
10
11  class Point {
12    public int x;
13    public int y;
14    public Point(int x, int y) {
15      this.x = x; this.y = y;
16    }
17  }
18
19  class World {
20    private bool[,] mowed = new bool[Width, Height];
21
22    public void SetCellMowed(Point p) {
23      mowed[p.x, p.y] = true;
24    }
25    public bool IsCellMowed(Point p) {
26      return mowed[p.x, p.y];
27    }
28  }
29
30  class MowerState {
31    public Point Position { get; set;}
32    public Direction Direction { get; set; }
33    public World World { get; set; }
34    public int Energy { get; set; }
35    public int MowedCells { get; set; }
36
37    public MowerState() {
38      Energy = 0;
39      MowedCells = 0;
40    }
41
42    public void TurnLeft() {
43      if (Energy <= 0) return; // don't move when no energy left
44      Energy--;
45      switch(Direction) {
46        case Direction.West: Direction = Direction.South; break;
47        case Direction.South: Direction = Direction.East; break;
48        case Direction.East: Direction = Direction.North; break;
49        case Direction.North: Direction = Direction.West; break;
50      }
51    }
52
53    public void Forward() {
54      if(Energy <= 0) return; // don't move when no energy left
55      Position = NextPosition;
56      Energy--;
57      if(!World.IsCellMowed(Position)) {
58        World.SetCellMowed(Position);
59        MowedCells++;
60      }
61    }
62
63    public void Jump(int x, int y) {
64      if(Energy <= 0) return; // don't move when no energy left
65      while(x<0) x += Width; // make sure offset is positive for mod-operation
66      while(y<0) y += Height;
67      Position = new Point((Position.x + x) % Width, (Position.y + y) % Height);
68      Energy--;
69      if(!World.IsCellMowed(Position)) {
70        World.SetCellMowed(Position);
71        MowedCells++;
72      }
73    }
74
75    public Point NextPosition {
76      get {
77        int x, y;
78        switch(Direction) {
79          case Direction.West:
80            x = (Position.x + Width - 1) % Width;
81            y = Position.y;
82            return new Point(x, y);
83          case Direction.South:
84            x = Position.x;
85            y = (Position.y + Height + 1) % Height;
86            return new Point(x, y);
87          case Direction.East:
88            x = (Position.x + Width + 1) % Width;
89            y = Position.y;
90            return new Point(x, y);
91          case Direction.North:
92            x = Position.x;
93            y = (Position.y + Height - 1) % Height;
94            return new Point(x, y);
95        }
96        return new Point(-1,-1);
97      }
98    }
99  }
100
101/* set of possible values for constants [-100, 100] */
102int[] ints = Enumerable.Range(-100, 201).ToArray();
103>>
104
105NONTERMINALS
106  LawnMower<<MowerState state>>.
107  Sum<<out int x, out int y>>.
108  Expr<<out int x, out int y>>. /* helper for expressions containing const and sum */
109  Frog<<MowerState state>>.
110  Prog2<<MowerState state>>.
111
112TERMINALS
113  Left.
114  Forward.
115  Const<<out int x, out int y>>
116    CONSTRAINTS
117      x IN SET <<ints; >> /* x \in [-100, 100] */
118      y IN SET <<ints; >> /* y \in [-100, 100] */
119  .
120
121RULES
122  LawnMower<<MowerState state>> =
123    Prog2<<state>>
124    | Frog<<state>>
125    | Left                                             SEM << state.TurnLeft(); >>
126    | Forward                                          SEM << state.Forward(); >>
127  .
128
129  Sum<<out int x, out int y>> =                        LOCAL << int x1, y1, x2, y2; >>
130    Expr<<out x1, out y1>>
131    Expr<<out x2, out y2>>                             SEM << x = x1 + x2; y = y1 + y2; >>
132  .
133
134  Expr<<out int x, out int y>> =
135    Const<<out x, out y>>
136    | Sum<<out x, out y>>
137  .
138
139  Prog2<<MowerState state>> =
140    LawnMower<<state>>
141    LawnMower<<state>>
142  .
143
144  Frog<<MowerState state>> =                          LOCAL << int x; int y; >>
145     Expr<<out x, out y>>                             SEM << state.Jump(x, y); >>
146  .
147
148MAXIMIZE
149  <<
150    var world = new World();
151    var state = new MowerState() {Position = new Point(0,0),
152                                  Energy = 2 * Height * Width,
153                                  Direction = Direction.South,
154                                  World = world};
155    world.SetCellMowed(state.Position); // set initial cell mowed
156    // execute the mower program once
157    LawnMower(state);
158    return (double)state.MowedCells;
159  >>
160END LawnMower.
Note: See TracBrowser for help on using the repository browser.