Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs @ 11659

Last change on this file since 11659 was 11659, checked in by gkronber, 9 years ago

#2283 initial import of implementation of grammatical optimization problem instances

File size: 6.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Runtime.Remoting.Messaging;
5using System.Text;
6
7namespace HeuristicLab.Problems.GrammaticalOptimization {
8  public class SantaFeAntProblem : IProblem {
9    private const string grammarString = @"
10G(A):
11A -> l | r | m | ?(A)(A) | AA | AAA
12";
13    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
14
15
16    private readonly IGrammar grammar;
17
18    public SantaFeAntProblem() {
19      this.grammar = new Grammar(grammarString);
20    }
21
22    public double GetBestKnownQuality(int maxLen) {
23      // for now only an upper bound is returned, ideally all food pellets are discovered
24      return 89;
25    }
26
27    public IGrammar Grammar {
28      get { return grammar; }
29    }
30
31    public double Evaluate(string sentence) {
32      var ant = new Ant();
33      int p = 0;
34      Run(ant, sentence, ref p);
35      return ant.FoodEaten;
36    }
37
38    private void Run(Ant ant, string sentence, ref int p) {
39      while (!ant.Done()) {
40        if (p >= sentence.Length) p = 0; // restart
41        switch (sentence[p]) {
42          case 'r': {
43              ant.TurnRight();
44              p++;
45              break;
46            }
47          case 'l': {
48              ant.TurnLeft();
49              p++;
50              break;
51            }
52          case 'm': {
53              ant.Move();
54              p++;
55              break;
56            }
57          case '?': {
58              p++; // skip p
59              if (ant.IsFoodAhead()) {
60                if (sentence[p] != '(') throw new ArgumentException();
61                p++;
62                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
63                if (ant.Done()) return;
64                if (sentence[p] != '(') throw new ArgumentException();
65                p++;
66                Skip(sentence, ref p);
67              } else {
68                if (sentence[p] != '(') throw new ArgumentException();
69                p++;
70                Skip(sentence, ref p);
71                if (sentence[p] != '(') throw new ArgumentException();
72                p++;
73                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
74              }
75              break;
76            }
77          case ')': {
78              p++; // skip
79              return;     // caller must continue processing
80            }
81          default: {
82              throw new ArgumentException();
83            }
84        }
85      }
86    }
87
88    private void Skip(string sentence, ref int p) {
89      int openCount = 1;
90      while (openCount > 0) {
91        if (sentence[p] == '(') openCount++;
92        else if (sentence[p] == ')') openCount--;
93        p++;
94      }
95    }
96  }
97
98  public class Ant {
99    private const int maxSteps = 600;
100    public enum HeadingEnum { North, East, South, West };
101    public int FoodEaten { get; private set; }
102    private readonly char[][] world = new char[32][];
103    private int posX;
104    private int posY;
105    private int steps;
106    private HeadingEnum heading;
107
108    public Ant() {
109      world[00] = " ###                            ".ToCharArray();
110      world[01] = "   #                            ".ToCharArray();
111      world[02] = "   #                    .###..  ".ToCharArray();
112      world[03] = "   #                    #    #  ".ToCharArray();
113      world[04] = "   #                    #    #  ".ToCharArray();
114      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
115      world[06] = "            #       .        #  ".ToCharArray();
116      world[07] = "            #       #        .  ".ToCharArray();
117      world[08] = "            #       #        .  ".ToCharArray();
118      world[09] = "            #       #        #  ".ToCharArray();
119      world[10] = "            .       #        .  ".ToCharArray();
120      world[11] = "            #       .        .  ".ToCharArray();
121      world[12] = "            #       .        #  ".ToCharArray();
122      world[13] = "            #       #        .  ".ToCharArray();
123      world[14] = "            #       #  ...###.  ".ToCharArray();
124      world[15] = "            .   .#...  #        ".ToCharArray();
125      world[16] = "            .   .      .        ".ToCharArray();
126      world[17] = "            #   .      .        ".ToCharArray();
127      world[18] = "            #   #      .#...    ".ToCharArray();
128      world[19] = "            #   #          #    ".ToCharArray();
129      world[20] = "            #   #          .    ".ToCharArray();
130      world[21] = "            #   #          .    ".ToCharArray();
131      world[22] = "            #   .      ...#.    ".ToCharArray();
132      world[23] = "            #   .      #        ".ToCharArray();
133      world[24] = " ..##..#####.   #               ".ToCharArray();
134      world[25] = " #              #               ".ToCharArray();
135      world[26] = " #              #               ".ToCharArray();
136      world[27] = " #     .#######..               ".ToCharArray();
137      world[28] = " #     #                        ".ToCharArray();
138      world[29] = " .     #                        ".ToCharArray();
139      world[30] = " .####..                        ".ToCharArray();
140      world[31] = "                                ".ToCharArray();
141
142      posX = 0;
143      posY = 0;
144      heading = HeadingEnum.East;
145      FoodEaten = 0;
146      steps = 0;
147    }
148
149    public bool Done() {
150      return steps > maxSteps;
151    }
152
153    public void TurnRight() {
154      if (steps <= maxSteps) {
155        steps++;
156        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
157        else heading++;
158      }
159    }
160
161    public void TurnLeft() {
162      if (steps <= maxSteps) {
163        steps++;
164        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
165        else heading--;
166      }
167    }
168
169    public void Move() {
170      if (steps <= maxSteps) {
171        steps++;
172        MoveInternal(ref posX, ref posY);
173        if (world[posY][posX] == '#') {
174          FoodEaten++;
175          world[posY][posX] = '.';
176        }
177      }
178    }
179
180    private void MoveInternal(ref int posX, ref int posY) {
181      switch (heading) {
182        case HeadingEnum.North:
183          posY = (posY + 31) % 32;
184          break;
185        case HeadingEnum.East:
186          posX = (posX + 1) % 32;
187          break;
188        case HeadingEnum.South:
189          posY = (posY + 1) % 32;
190          break;
191        case HeadingEnum.West:
192          posX = (posX + 31) % 32;
193          break;
194      }
195    }
196
197    public bool IsFoodAhead() {
198      int nextPosX = posX;
199      int nextPosY = posY;
200      MoveInternal(ref nextPosX, ref nextPosY);
201      return world[nextPosY][nextPosX] == '#';
202    }
203  }
204}
Note: See TracBrowser for help on using the repository browser.