[8059] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[11594] | 3 | * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[8059] | 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;
|
---|
[8131] | 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
[8059] | 25 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
| 26 |
|
---|
| 27 | namespace HeuristicLab.Problems.LawnMower {
|
---|
| 28 | public class Interpreter {
|
---|
| 29 | private enum Heading {
|
---|
| 30 | South,
|
---|
| 31 | East,
|
---|
| 32 | North,
|
---|
| 33 | West
|
---|
| 34 | };
|
---|
| 35 |
|
---|
| 36 | private class MowerState {
|
---|
| 37 | public Heading Heading { get; set; }
|
---|
| 38 | public Tuple<uint, uint> Position { get; set; }
|
---|
| 39 | public int Energy { get; set; }
|
---|
| 40 | public MowerState() {
|
---|
| 41 | Heading = Heading.South;
|
---|
| 42 | Position = new Tuple<uint, uint>(0, 0);
|
---|
| 43 | Energy = 0;
|
---|
| 44 | }
|
---|
| 45 | }
|
---|
| 46 |
|
---|
| 47 |
|
---|
| 48 | public static bool[,] EvaluateLawnMowerProgram(int length, int width, ISymbolicExpressionTree tree) {
|
---|
| 49 |
|
---|
| 50 | bool[,] lawn = new bool[length, width];
|
---|
| 51 | var mowerState = new MowerState();
|
---|
| 52 | mowerState.Heading = Heading.South;
|
---|
| 53 | mowerState.Energy = length * width * 2;
|
---|
| 54 | lawn[mowerState.Position.Item1, mowerState.Position.Item2] = true;
|
---|
[8163] | 55 | EvaluateLawnMowerProgram(tree.Root, mowerState, lawn, tree.Root.Subtrees.Skip(1).ToArray());
|
---|
[8059] | 56 | return lawn;
|
---|
| 57 | }
|
---|
| 58 |
|
---|
| 59 |
|
---|
[8163] | 60 | private static Tuple<int, int> EvaluateLawnMowerProgram(ISymbolicExpressionTreeNode node, MowerState mowerState, bool[,] lawn, IEnumerable<ISymbolicExpressionTreeNode> adfs) {
|
---|
[8059] | 61 | if (mowerState.Energy <= 0) return new Tuple<int, int>(0, 0);
|
---|
| 62 |
|
---|
| 63 | if (node.Symbol is ProgramRootSymbol) {
|
---|
[8163] | 64 | return EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
|
---|
[8059] | 65 | } else if (node.Symbol is StartSymbol) {
|
---|
[8163] | 66 | return EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
|
---|
[8059] | 67 | } else if (node.Symbol is Left) {
|
---|
| 68 | switch (mowerState.Heading) {
|
---|
| 69 | case Heading.East: mowerState.Heading = Heading.North;
|
---|
| 70 | break;
|
---|
| 71 | case Heading.North: mowerState.Heading = Heading.West;
|
---|
| 72 | break;
|
---|
| 73 | case Heading.West: mowerState.Heading = Heading.South;
|
---|
| 74 | break;
|
---|
| 75 | case Heading.South:
|
---|
| 76 | mowerState.Heading = Heading.East;
|
---|
| 77 | break;
|
---|
| 78 | }
|
---|
| 79 | return new Tuple<int, int>(0, 0);
|
---|
| 80 | } else if (node.Symbol is Forward) {
|
---|
| 81 | int dRow = 0;
|
---|
| 82 | int dCol = 0;
|
---|
| 83 | switch (mowerState.Heading) {
|
---|
| 84 | case Heading.East:
|
---|
| 85 | dCol++;
|
---|
| 86 | break;
|
---|
| 87 | case Heading.North:
|
---|
| 88 | dRow--;
|
---|
| 89 | break;
|
---|
| 90 | case Heading.West:
|
---|
| 91 | dCol--;
|
---|
| 92 | break;
|
---|
| 93 | case Heading.South:
|
---|
| 94 | dRow++;
|
---|
| 95 | break;
|
---|
| 96 | }
|
---|
| 97 | uint newRow = (uint)((mowerState.Position.Item1 + lawn.GetLength(0) + dRow) % lawn.GetLength(0));
|
---|
| 98 | uint newColumn = (uint)((mowerState.Position.Item2 + lawn.GetLength(1) + dCol) % lawn.GetLength(1));
|
---|
| 99 | mowerState.Position = new Tuple<uint, uint>(newRow, newColumn);
|
---|
| 100 | mowerState.Energy = mowerState.Energy - 1;
|
---|
| 101 | lawn[newRow, newColumn] = true;
|
---|
| 102 | return new Tuple<int, int>(0, 0);
|
---|
| 103 | } else if (node.Symbol is Constant) {
|
---|
| 104 | var constNode = node as ConstantTreeNode;
|
---|
| 105 | return constNode.Value;
|
---|
| 106 | } else if (node.Symbol is Sum) {
|
---|
[8163] | 107 | var p = EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
|
---|
| 108 | var q = EvaluateLawnMowerProgram(node.GetSubtree(1), mowerState, lawn, adfs);
|
---|
[8059] | 109 | return new Tuple<int, int>(p.Item1 + q.Item1,
|
---|
| 110 | p.Item2 + q.Item2);
|
---|
| 111 | } else if (node.Symbol is Prog) {
|
---|
[8163] | 112 | EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
|
---|
| 113 | return EvaluateLawnMowerProgram(node.GetSubtree(1), mowerState, lawn, adfs);
|
---|
[8059] | 114 | } else if (node.Symbol is Frog) {
|
---|
[8163] | 115 | var p = EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
|
---|
[11594] | 116 | int x = p.Item1;
|
---|
| 117 | int y = p.Item2;
|
---|
| 118 | while (x < 0) x += lawn.GetLength(0);
|
---|
| 119 | while (y < 0) y += lawn.GetLength(1);
|
---|
| 120 | var newRow = (uint)((mowerState.Position.Item1 + x) % lawn.GetLength(0));
|
---|
| 121 | var newCol = (uint)((mowerState.Position.Item2 + y) % lawn.GetLength(1));
|
---|
[8059] | 122 | mowerState.Position = new Tuple<uint, uint>(newRow, newCol);
|
---|
| 123 | mowerState.Energy = mowerState.Energy - 1;
|
---|
| 124 | lawn[newRow, newCol] = true;
|
---|
| 125 | return new Tuple<int, int>(0, 0);
|
---|
[8131] | 126 | } else if (node.Symbol is InvokeFunction) {
|
---|
| 127 | var invokeNode = node as InvokeFunctionTreeNode;
|
---|
| 128 |
|
---|
| 129 | // find the function definition for the invoke call
|
---|
| 130 | var functionDefinition = (from adf in adfs.Cast<DefunTreeNode>()
|
---|
| 131 | where adf.FunctionName == invokeNode.Symbol.FunctionName
|
---|
| 132 | select adf).Single();
|
---|
| 133 | // clone the function definition because we are replacing the argument nodes
|
---|
[11594] | 134 | functionDefinition = (DefunTreeNode)functionDefinition.Clone();
|
---|
[8131] | 135 | // find the argument tree nodes and their parents in the original function definition
|
---|
| 136 | // toList is necessary to prevent that newly inserted branches are iterated
|
---|
| 137 | var argumentCutPoints = (from parent in functionDefinition.IterateNodesPrefix()
|
---|
| 138 | from subtree in parent.Subtrees
|
---|
| 139 | where subtree is ArgumentTreeNode
|
---|
| 140 | select new { Parent = parent, Argument = subtree.Symbol as Argument, ChildIndex = parent.IndexOfSubtree(subtree) })
|
---|
| 141 | .ToList();
|
---|
| 142 | // replace all argument tree ndoes with the matching argument of the invoke node
|
---|
| 143 | foreach (var cutPoint in argumentCutPoints) {
|
---|
| 144 | cutPoint.Parent.RemoveSubtree(cutPoint.ChildIndex);
|
---|
| 145 | cutPoint.Parent.InsertSubtree(cutPoint.ChildIndex, (SymbolicExpressionTreeNode)invokeNode.GetSubtree(cutPoint.Argument.ArgumentIndex).Clone());
|
---|
| 146 | }
|
---|
[8163] | 147 | return EvaluateLawnMowerProgram(functionDefinition.GetSubtree(0), mowerState, lawn, adfs);
|
---|
[8059] | 148 | } else {
|
---|
| 149 | throw new ArgumentException("Invalid symbol in the lawn mower program.");
|
---|
| 150 | }
|
---|
| 151 | }
|
---|
| 152 | }
|
---|
| 153 | }
|
---|