source: trunk/sources/HeuristicLab.Problems.LawnMower/3.3/Interpreter.cs @ 9456

Last change on this file since 9456 was 9456, checked in by swagner, 7 years ago

Updated copyright year and added some missing license headers (#1889)

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