Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2026 added lawn mower problem. create a OSGA for solving the compiled problem directly

File size: 5.0 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. Interestingly, this increases success rates in
4 * comparison with the original formulation where functions could be combined freely.
5 */
6CODE <<
7  public static int Width { get { return 16; } }
8  public static int Height { get { return 16; } }
9
10  enum Direction {West, East, North, South};
11
12  class Point {
13    public int x;
14    public int y;
15    public Point(int x, int y) {
16      this.x = x; this.y = y;
17    }
18  }
19
20  class World {
21    private bool[,] mowed = new bool[Width, Height];
22    public World() {
23      Reset();
24    }
25    public void Reset() {
26      for(int col = 0; col < Width; col++)
27        for(int row = 0; row < Height; row++) {
28          mowed[col, row] = false;
29        }
30    }
31    public void SetCellMowed(Point p) {
32      mowed[p.x, p.y] = true;
33    }
34    public bool IsCellMowed(Point p) {
35      return mowed[p.x, p.y];
36    }
37  }
38
39  class MowerState {
40    public Point Position { get; set;}
41    public Direction Direction { get; set; }
42    public World World { get; set; }
43    public int Energy { get; set; }
44    public int MowedCells { get; set; }
45   
46    public MowerState() {
47      Energy = 0;
48      MowedCells = 0;
49    }
50 
51    public void TurnLeft() {
52      if (Energy <= 0) return; // don't move when no energy left
53      Energy--;
54      switch(Direction) {
55        case Direction.West: Direction = Direction.South; break;
56        case Direction.South: Direction = Direction.East; break;
57        case Direction.East: Direction = Direction.North; break;
58        case Direction.North: Direction = Direction.West; break;
59      }
60    }
61 
62    public void Forward() {
63      if(Energy <= 0) return; // don't move when no energy left
64      Position = NextPosition;
65      Energy--;
66      if(!World.IsCellMowed(Position)) {
67        World.SetCellMowed(Position);
68        MowedCells++;
69      }
70    }
71
72    public void Jump(int x, int y) {
73      if(Energy <= 0) return; // don't move when no energy left
74      while(x<0) x += Width; // make sure offset is positive for mod-operation
75      while(y<0) y += Height;
76      Position = new Point((Position.x + x) % Width, (Position.y + y) % Height);
77      Energy--;
78      if(!World.IsCellMowed(Position)) {
79        World.SetCellMowed(Position);
80        MowedCells++;
81      }
82    }
83 
84    public Point NextPosition {
85      get {
86        int x, y;
87        switch(Direction) {
88          case Direction.West:
89            x = (Position.x + Width - 1) % Width;
90            y = Position.y;
91            return new Point(x, y);
92          case Direction.South:
93            x = Position.x;
94            y = (Position.y + Height + 1) % Height;
95            return new Point(x, y);
96          case Direction.East:
97            x = (Position.x + Width + 1) % Width;
98            y = Position.y;
99            return new Point(x, y);
100          case Direction.North:
101            x = Position.x;
102            y = (Position.y + Height - 1) % Height;
103            return new Point(x, y);
104        }
105        return new Point(-1,-1);
106      }
107    }
108  }
109
110World CreateWorld() {   
111  return new World();
112}
113
114World world;
115/* set of possible values for constants [-100, 100] */
116int[] ints = Enumerable.Range(-100, 201).ToArray();
117>>
118INIT <<
119  world = CreateWorld();
120>>
121
122NONTERMINALS
123  LawnMower<<MowerState state>>.
124  Sum<<out int x, out int y>>.
125  Expr<<out int x, out int y>>. /* helper for expressions containing const and sum */
126  Frog<<MowerState state>>.
127  Prog2<<MowerState state>>.
128
129TERMINALS
130  Left.
131  Forward.
132  Const<<out int x, out int y>>
133    CONSTRAINTS
134      x IN SET <<ints; >> /* x \in [-100, 100] */
135      y IN SET <<ints; >> /* y \in [-100, 100] */
136  .
137
138RULES
139  LawnMower<<MowerState state>> =
140    Prog2<<state>>
141    | Frog<<state>>
142    | Left                                             SEM << state.TurnLeft(); >>
143    | Forward                                          SEM << state.Forward(); >>
144  .
145   
146  Sum<<out int x, out int y>> =                        LOCAL << int x1, y1, x2, y2; >>
147    Expr<<out x1, out y1>>
148    Expr<<out x2, out y2>>                             SEM << x = x1 + x2; y = y1 + y2; >>
149  .
150
151  Expr<<out int x, out int y>> =
152    Const<<out x, out y>>
153    | Sum<<out x, out y>>
154  .
155
156  Prog2<<MowerState state>> =
157    LawnMower<<state>>
158    LawnMower<<state>>
159  .
160 
161  Frog<<MowerState state>> =                          LOCAL << int x; int y; >>
162     Expr<<out x, out y>>                             SEM << state.Jump(x, y); >>
163  .
164
165MAXIMIZE
166  <<   
167    world.Reset();
168    var state = new MowerState() {Position = new Point(0,0),
169                                  Energy = 2 * Height * Width,
170                                  Direction = Direction.South,
171                                  World = world};
172    while(state.Energy > 0) {
173      LawnMower(state);
174    }
175    return (double)state.MowedCells;
176  >> 
177END LawnMower.
Note: See TracBrowser for help on using the repository browser.