[8059] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using System;
|
---|
| 23 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
| 24 |
|
---|
| 25 | namespace HeuristicLab.Problems.LawnMower {
|
---|
| 26 | public class Interpreter {
|
---|
| 27 | private enum Heading {
|
---|
| 28 | South,
|
---|
| 29 | East,
|
---|
| 30 | North,
|
---|
| 31 | West
|
---|
| 32 | };
|
---|
| 33 |
|
---|
| 34 | private class MowerState {
|
---|
| 35 | public Heading Heading { get; set; }
|
---|
| 36 | public Tuple<uint, uint> Position { get; set; }
|
---|
| 37 | public int Energy { get; set; }
|
---|
| 38 | public MowerState() {
|
---|
| 39 | Heading = Heading.South;
|
---|
| 40 | Position = new Tuple<uint, uint>(0, 0);
|
---|
| 41 | Energy = 0;
|
---|
| 42 | }
|
---|
| 43 | }
|
---|
| 44 |
|
---|
| 45 |
|
---|
| 46 | public static bool[,] EvaluateLawnMowerProgram(int length, int width, ISymbolicExpressionTree tree) {
|
---|
| 47 |
|
---|
| 48 | bool[,] lawn = new bool[length, width];
|
---|
| 49 | var mowerState = new MowerState();
|
---|
| 50 | mowerState.Heading = Heading.South;
|
---|
| 51 | mowerState.Energy = length * width * 2;
|
---|
| 52 | lawn[mowerState.Position.Item1, mowerState.Position.Item2] = true;
|
---|
| 53 | EvaluateLawnMowerProgram(tree.Root, ref mowerState, lawn);
|
---|
| 54 |
|
---|
| 55 | return lawn;
|
---|
| 56 | }
|
---|
| 57 |
|
---|
| 58 |
|
---|
| 59 | private static Tuple<int, int> EvaluateLawnMowerProgram(ISymbolicExpressionTreeNode node, ref MowerState mowerState, bool[,] lawn) {
|
---|
| 60 | if (mowerState.Energy <= 0) return new Tuple<int, int>(0, 0);
|
---|
| 61 |
|
---|
| 62 | if (node.Symbol is ProgramRootSymbol) {
|
---|
| 63 | return EvaluateLawnMowerProgram(node.GetSubtree(0), ref mowerState, lawn);
|
---|
| 64 | } else if (node.Symbol is StartSymbol) {
|
---|
| 65 | return EvaluateLawnMowerProgram(node.GetSubtree(0), ref mowerState, lawn);
|
---|
| 66 | } else if (node.Symbol is Left) {
|
---|
| 67 | switch (mowerState.Heading) {
|
---|
| 68 | case Heading.East: mowerState.Heading = Heading.North;
|
---|
| 69 | break;
|
---|
| 70 | case Heading.North: mowerState.Heading = Heading.West;
|
---|
| 71 | break;
|
---|
| 72 | case Heading.West: mowerState.Heading = Heading.South;
|
---|
| 73 | break;
|
---|
| 74 | case Heading.South:
|
---|
| 75 | mowerState.Heading = Heading.East;
|
---|
| 76 | break;
|
---|
| 77 | }
|
---|
| 78 | return new Tuple<int, int>(0, 0);
|
---|
| 79 | } else if (node.Symbol is Forward) {
|
---|
| 80 | int dRow = 0;
|
---|
| 81 | int dCol = 0;
|
---|
| 82 | switch (mowerState.Heading) {
|
---|
| 83 | case Heading.East:
|
---|
| 84 | dCol++;
|
---|
| 85 | break;
|
---|
| 86 | case Heading.North:
|
---|
| 87 | dRow--;
|
---|
| 88 | break;
|
---|
| 89 | case Heading.West:
|
---|
| 90 | dCol--;
|
---|
| 91 | break;
|
---|
| 92 | case Heading.South:
|
---|
| 93 | dRow++;
|
---|
| 94 | break;
|
---|
| 95 | }
|
---|
| 96 | uint newRow = (uint)((mowerState.Position.Item1 + lawn.GetLength(0) + dRow) % lawn.GetLength(0));
|
---|
| 97 | uint newColumn = (uint)((mowerState.Position.Item2 + lawn.GetLength(1) + dCol) % lawn.GetLength(1));
|
---|
| 98 | mowerState.Position = new Tuple<uint, uint>(newRow, newColumn);
|
---|
| 99 | mowerState.Energy = mowerState.Energy - 1;
|
---|
| 100 | lawn[newRow, newColumn] = true;
|
---|
| 101 | return new Tuple<int, int>(0, 0);
|
---|
| 102 | } else if (node.Symbol is Constant) {
|
---|
| 103 | var constNode = node as ConstantTreeNode;
|
---|
| 104 | return constNode.Value;
|
---|
| 105 | } else if (node.Symbol is Sum) {
|
---|
| 106 | var p = EvaluateLawnMowerProgram(node.GetSubtree(0), ref mowerState, lawn);
|
---|
| 107 | var q = EvaluateLawnMowerProgram(node.GetSubtree(1), ref mowerState, lawn);
|
---|
| 108 | return new Tuple<int, int>(p.Item1 + q.Item1,
|
---|
| 109 | p.Item2 + q.Item2);
|
---|
| 110 | } else if (node.Symbol is Prog) {
|
---|
| 111 | EvaluateLawnMowerProgram(node.GetSubtree(0), ref mowerState, lawn);
|
---|
| 112 | return EvaluateLawnMowerProgram(node.GetSubtree(1), ref mowerState, lawn);
|
---|
| 113 | } else if (node.Symbol is Frog) {
|
---|
| 114 | var p = EvaluateLawnMowerProgram(node.GetSubtree(0), ref mowerState, lawn);
|
---|
| 115 |
|
---|
| 116 | uint newRow = (uint)((mowerState.Position.Item1 + lawn.GetLength(0) + p.Item1 % lawn.GetLength(0)) % lawn.GetLength(0));
|
---|
| 117 | uint newCol = (uint)((mowerState.Position.Item2 + lawn.GetLength(1) + p.Item2 % lawn.GetLength(1)) % lawn.GetLength(1));
|
---|
| 118 | mowerState.Position = new Tuple<uint, uint>(newRow, newCol);
|
---|
| 119 | mowerState.Energy = mowerState.Energy - 1;
|
---|
| 120 | lawn[newRow, newCol] = true;
|
---|
| 121 | return new Tuple<int, int>(0, 0);
|
---|
| 122 | } else {
|
---|
| 123 | throw new ArgumentException("Invalid symbol in the lawn mower program.");
|
---|
| 124 | }
|
---|
| 125 | }
|
---|
| 126 |
|
---|
| 127 | }
|
---|
| 128 | }
|
---|