1 | PROBLEM 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 | */
|
---|
6 | CODE <<
|
---|
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 |
|
---|
110 | World CreateWorld() {
|
---|
111 | return new World();
|
---|
112 | }
|
---|
113 |
|
---|
114 | World world;
|
---|
115 | /* set of possible values for constants [-100, 100] */
|
---|
116 | int[] ints = Enumerable.Range(-100, 201).ToArray();
|
---|
117 | >>
|
---|
118 | INIT <<
|
---|
119 | world = CreateWorld();
|
---|
120 | >>
|
---|
121 |
|
---|
122 | NONTERMINALS
|
---|
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 |
|
---|
129 | TERMINALS
|
---|
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 |
|
---|
138 | RULES
|
---|
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 |
|
---|
165 | MAXIMIZE
|
---|
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 | >>
|
---|
177 | END LawnMower.
|
---|