[9846] | 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.
|
---|