Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 9847 was 9847, checked in by gkronber, 11 years ago

#2026 lawn mower programs are only executed once. This makes the problem much harder.

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>>
104INIT <<
105>>
106
107NONTERMINALS
108  LawnMower<<MowerState state>>.
109  Sum<<out int x, out int y>>.
110  Expr<<out int x, out int y>>. /* helper for expressions containing const and sum */
111  Frog<<MowerState state>>.
112  Prog2<<MowerState state>>.
113
114TERMINALS
115  Left.
116  Forward.
117  Const<<out int x, out int y>>
118    CONSTRAINTS
119      x IN SET <<ints; >> /* x \in [-100, 100] */
120      y IN SET <<ints; >> /* y \in [-100, 100] */
121  .
122
123RULES
124  LawnMower<<MowerState state>> =
125    Prog2<<state>>
126    | Frog<<state>>
127    | Left                                             SEM << state.TurnLeft(); >>
128    | Forward                                          SEM << state.Forward(); >>
129  .
130   
131  Sum<<out int x, out int y>> =                        LOCAL << int x1, y1, x2, y2; >>
132    Expr<<out x1, out y1>>
133    Expr<<out x2, out y2>>                             SEM << x = x1 + x2; y = y1 + y2; >>
134  .
135
136  Expr<<out int x, out int y>> =
137    Const<<out x, out y>>
138    | Sum<<out x, out y>>
139  .
140
141  Prog2<<MowerState state>> =
142    LawnMower<<state>>
143    LawnMower<<state>>
144  .
145 
146  Frog<<MowerState state>> =                          LOCAL << int x; int y; >>
147     Expr<<out x, out y>>                             SEM << state.Jump(x, y); >>
148  .
149
150MAXIMIZE
151  <<   
152    var world = new World();
153    var state = new MowerState() {Position = new Point(0,0),
154                                  Energy = 2 * Height * Width,
155                                  Direction = Direction.South,
156                                  World = world};
157    world.SetCellMowed(state.Position); // set initial cell mowed
158    // execute the mower program once
159    LawnMower(state);
160    return (double)state.MowedCells;
161  >> 
162END LawnMower.
Note: See TracBrowser for help on using the repository browser.