[11659] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
[11847] | 3 | using System.Diagnostics;
|
---|
[11659] | 4 | using System.Linq;
|
---|
[11799] | 5 | using System.Runtime.InteropServices;
|
---|
[11659] | 6 | using System.Runtime.Remoting.Messaging;
|
---|
| 7 | using System.Text;
|
---|
[11799] | 8 | using System.Text.RegularExpressions;
|
---|
[11847] | 9 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
[11659] | 10 |
|
---|
| 11 | namespace HeuristicLab.Problems.GrammaticalOptimization {
|
---|
[11847] | 12 | public class SantaFeAntProblem : ISymbolicExpressionTreeProblem {
|
---|
[11659] | 13 | private const string grammarString = @"
|
---|
| 14 | G(A):
|
---|
[12876] | 15 | A -> l | r | m | ?(A)(A) | lA | rA | mA |?(A)(A)A
|
---|
[11659] | 16 | ";
|
---|
[11847] | 17 | // for tree-based GP in HL we need a different grammar for the same language
|
---|
| 18 | // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
|
---|
| 19 | private const string hlGrammarString = @"
|
---|
| 20 | G(A):
|
---|
| 21 | A -> l | r | m | P | I
|
---|
| 22 | P -> AA | AAA
|
---|
| 23 | I -> AA
|
---|
| 24 | ";
|
---|
[11770] | 25 |
|
---|
| 26 |
|
---|
[11708] | 27 | // original koza grammar
|
---|
[11659] | 28 | // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
|
---|
[11708] | 29 | //
|
---|
| 30 | // here we use a modified grammar which has only one syntax tree for each sentence
|
---|
[11659] | 31 |
|
---|
[12893] | 32 | public IEnumerable<string> OptimalSentences {
|
---|
| 33 | get {
|
---|
| 34 | return new string[]
|
---|
| 35 | {
|
---|
| 36 | "?(m)(ll?(m)(r))mr",
|
---|
| 37 | "?(m)(rr?(m)(l))ml",
|
---|
| 38 | "r?(m)(ll?(m)(r))m",
|
---|
| 39 | "l?(m)(rr?(m)(l))m",
|
---|
| 40 | "mr?(m)(ll?(m)(r))",
|
---|
| 41 | "ml?(m)(rr?(m)(l))",
|
---|
| 42 | "?(m)(ll?(m)(l))ml",
|
---|
| 43 | "?(m)(rr?(m)(r))mr",
|
---|
| 44 | "l?(m)(ll?(m)(l))m",
|
---|
| 45 | "r?(m)(rr?(m)(r))m",
|
---|
| 46 | "ml?(m)(ll?(m)(l))",
|
---|
| 47 | "mr?(m)(rr?(m)(r))",
|
---|
| 48 | };
|
---|
| 49 | }
|
---|
| 50 | }
|
---|
[11659] | 51 |
|
---|
| 52 | private readonly IGrammar grammar;
|
---|
[12099] | 53 | public string Name { get { return "SantaFeAnt"; } }
|
---|
[11659] | 54 |
|
---|
| 55 | public SantaFeAntProblem() {
|
---|
| 56 | this.grammar = new Grammar(grammarString);
|
---|
[11857] | 57 | this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
|
---|
[11659] | 58 | }
|
---|
| 59 |
|
---|
[11732] | 60 | public double BestKnownQuality(int maxLen) {
|
---|
[11659] | 61 | // for now only an upper bound is returned, ideally all food pellets are discovered
|
---|
| 62 | return 89;
|
---|
| 63 | }
|
---|
| 64 |
|
---|
| 65 | public IGrammar Grammar {
|
---|
| 66 | get { return grammar; }
|
---|
| 67 | }
|
---|
| 68 |
|
---|
| 69 | public double Evaluate(string sentence) {
|
---|
| 70 | var ant = new Ant();
|
---|
| 71 | int p = 0;
|
---|
| 72 | Run(ant, sentence, ref p);
|
---|
| 73 | return ant.FoodEaten;
|
---|
| 74 | }
|
---|
| 75 |
|
---|
[11976] | 76 | private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false) {
|
---|
[11659] | 77 | while (!ant.Done()) {
|
---|
[11976] | 78 | if (p >= sentence.Length) {
|
---|
| 79 | if (stopAfterFirst) return;
|
---|
| 80 | p = 0; // restart
|
---|
| 81 | }
|
---|
[11659] | 82 | switch (sentence[p]) {
|
---|
| 83 | case 'r': {
|
---|
| 84 | ant.TurnRight();
|
---|
| 85 | p++;
|
---|
| 86 | break;
|
---|
| 87 | }
|
---|
| 88 | case 'l': {
|
---|
| 89 | ant.TurnLeft();
|
---|
| 90 | p++;
|
---|
| 91 | break;
|
---|
| 92 | }
|
---|
| 93 | case 'm': {
|
---|
| 94 | ant.Move();
|
---|
| 95 | p++;
|
---|
| 96 | break;
|
---|
| 97 | }
|
---|
| 98 | case '?': {
|
---|
| 99 | p++; // skip p
|
---|
| 100 | if (ant.IsFoodAhead()) {
|
---|
| 101 | if (sentence[p] != '(') throw new ArgumentException();
|
---|
| 102 | p++;
|
---|
| 103 | Run(ant, sentence, ref p); // it cannot happen that we run over the the end of the sentence here
|
---|
| 104 | if (ant.Done()) return;
|
---|
| 105 | if (sentence[p] != '(') throw new ArgumentException();
|
---|
| 106 | p++;
|
---|
| 107 | Skip(sentence, ref p);
|
---|
| 108 | } else {
|
---|
| 109 | if (sentence[p] != '(') throw new ArgumentException();
|
---|
| 110 | p++;
|
---|
| 111 | Skip(sentence, ref p);
|
---|
| 112 | if (sentence[p] != '(') throw new ArgumentException();
|
---|
| 113 | p++;
|
---|
| 114 | Run(ant, sentence, ref p); // it cannot happen that we run over the the end of the sentence here
|
---|
| 115 | }
|
---|
| 116 | break;
|
---|
| 117 | }
|
---|
[11976] | 118 | case '.': {
|
---|
| 119 | // nop
|
---|
| 120 | p++;
|
---|
| 121 | ant.Nop();
|
---|
| 122 | break;
|
---|
| 123 | }
|
---|
[11659] | 124 | case ')': {
|
---|
| 125 | p++; // skip
|
---|
| 126 | return; // caller must continue processing
|
---|
| 127 | }
|
---|
| 128 | default: {
|
---|
| 129 | throw new ArgumentException();
|
---|
| 130 | }
|
---|
| 131 | }
|
---|
| 132 | }
|
---|
| 133 | }
|
---|
| 134 |
|
---|
[11976] | 135 | private static void Skip(string sentence, ref int p) {
|
---|
[11659] | 136 | int openCount = 1;
|
---|
| 137 | while (openCount > 0) {
|
---|
| 138 | if (sentence[p] == '(') openCount++;
|
---|
| 139 | else if (sentence[p] == ')') openCount--;
|
---|
| 140 | p++;
|
---|
| 141 | }
|
---|
| 142 | }
|
---|
[11727] | 143 |
|
---|
[11832] | 144 | public string CanonicalRepresentation(string phrase) {
|
---|
[11980] | 145 | //phrase = phrase.Replace("A", ".");
|
---|
[11832] | 146 | var sb = new StringBuilder(phrase);
|
---|
| 147 | string canonicalPhrase = phrase;
|
---|
[11747] | 148 | string oldPhrase;
|
---|
| 149 | do {
|
---|
[11799] | 150 | oldPhrase = canonicalPhrase;
|
---|
[11977] | 151 | sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
|
---|
| 152 | //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
|
---|
[11799] | 153 | canonicalPhrase = sb.ToString();
|
---|
| 154 | } while (canonicalPhrase != oldPhrase);
|
---|
[11980] | 155 | return canonicalPhrase;
|
---|
[11727] | 156 | }
|
---|
[11832] | 157 |
|
---|
| 158 | public IEnumerable<Feature> GetFeatures(string phrase) {
|
---|
[12893] | 159 | for (int idx = 0; idx < 15; idx++) {
|
---|
| 160 | foreach (var t in Grammar.TerminalSymbols)
|
---|
| 161 | yield return new Feature(t.ToString(), phrase.Length > idx ? phrase[idx] == t ? 1 : 0 : 0);
|
---|
| 162 | }
|
---|
[12290] | 163 | //var ant = new Ant(false);
|
---|
| 164 | //int p = 0;
|
---|
| 165 | //Run(ant, phrase.Replace('A', '.'), ref p, true);
|
---|
| 166 | //yield return new Feature(ant.PosX + "x" + ant.PosY + "-" + ant.Heading, 1.0);
|
---|
[11832] | 167 | }
|
---|
[11847] | 168 |
|
---|
[11857] | 169 | public IGrammar TreeBasedGPGrammar { get; private set; }
|
---|
[11847] | 170 | public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
|
---|
| 171 | var sb = new StringBuilder();
|
---|
| 172 | ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
|
---|
| 173 | return sb.ToString();
|
---|
| 174 | }
|
---|
| 175 | private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb) {
|
---|
| 176 | if (node.SubtreeCount == 0) {
|
---|
| 177 | // terminal
|
---|
| 178 | sb.Append(node.Symbol.Name);
|
---|
| 179 | } else if (node.Symbol.Name == "I") {
|
---|
| 180 | Debug.Assert(node.SubtreeCount == 2);
|
---|
| 181 | sb.Append("?(");
|
---|
| 182 | ConvertTreeToSentence(node.GetSubtree(0), sb);
|
---|
| 183 | sb.Append(")(");
|
---|
| 184 | ConvertTreeToSentence(node.GetSubtree(1), sb);
|
---|
| 185 | sb.Append(")");
|
---|
| 186 | } else {
|
---|
| 187 | foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
|
---|
| 188 | }
|
---|
| 189 | }
|
---|
[12893] | 190 | public bool IsOptimalPhrase(string phrase) {
|
---|
| 191 | var firstNonTerminalIdx = new Sequence(phrase).FirstNonTerminalIndex;
|
---|
| 192 | if (firstNonTerminalIdx == -1) firstNonTerminalIdx = phrase.Length;
|
---|
| 193 | return OptimalSentences.Any(s => s.Substring(0, firstNonTerminalIdx) == phrase.Substring(0, firstNonTerminalIdx));
|
---|
| 194 | }
|
---|
| 195 |
|
---|
[11659] | 196 | }
|
---|
| 197 |
|
---|
| 198 | public class Ant {
|
---|
[11976] | 199 | private int maxSteps = 600;
|
---|
| 200 | public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
|
---|
[11659] | 201 | public enum HeadingEnum { North, East, South, West };
|
---|
| 202 | public int FoodEaten { get; private set; }
|
---|
| 203 | private readonly char[][] world = new char[32][];
|
---|
| 204 | private int posX;
|
---|
| 205 | private int posY;
|
---|
| 206 | private int steps;
|
---|
| 207 | private HeadingEnum heading;
|
---|
[11976] | 208 | public int PosX { get { return posX; } }
|
---|
| 209 | public int PosY { get { return posY; } }
|
---|
| 210 | public HeadingEnum Heading { get { return heading; } }
|
---|
| 211 | private bool recordTrail = false;
|
---|
| 212 | private StringBuilder trailBuilder;
|
---|
[11659] | 213 |
|
---|
[11976] | 214 | public string Trail {
|
---|
| 215 | get {
|
---|
| 216 | if (!recordTrail) throw new NotSupportedException();
|
---|
| 217 | else return trailBuilder.ToString() + heading; // add final heading as state
|
---|
| 218 | }
|
---|
| 219 | }
|
---|
[11730] | 220 |
|
---|
[11976] | 221 | public Ant(bool recordTrail = false) {
|
---|
[11659] | 222 | world[00] = " ### ".ToCharArray();
|
---|
| 223 | world[01] = " # ".ToCharArray();
|
---|
| 224 | world[02] = " # .###.. ".ToCharArray();
|
---|
| 225 | world[03] = " # # # ".ToCharArray();
|
---|
| 226 | world[04] = " # # # ".ToCharArray();
|
---|
| 227 | world[05] = " ####.##### .##.. . ".ToCharArray();
|
---|
| 228 | world[06] = " # . # ".ToCharArray();
|
---|
| 229 | world[07] = " # # . ".ToCharArray();
|
---|
| 230 | world[08] = " # # . ".ToCharArray();
|
---|
| 231 | world[09] = " # # # ".ToCharArray();
|
---|
| 232 | world[10] = " . # . ".ToCharArray();
|
---|
| 233 | world[11] = " # . . ".ToCharArray();
|
---|
| 234 | world[12] = " # . # ".ToCharArray();
|
---|
| 235 | world[13] = " # # . ".ToCharArray();
|
---|
| 236 | world[14] = " # # ...###. ".ToCharArray();
|
---|
| 237 | world[15] = " . .#... # ".ToCharArray();
|
---|
| 238 | world[16] = " . . . ".ToCharArray();
|
---|
| 239 | world[17] = " # . . ".ToCharArray();
|
---|
| 240 | world[18] = " # # .#... ".ToCharArray();
|
---|
| 241 | world[19] = " # # # ".ToCharArray();
|
---|
| 242 | world[20] = " # # . ".ToCharArray();
|
---|
| 243 | world[21] = " # # . ".ToCharArray();
|
---|
| 244 | world[22] = " # . ...#. ".ToCharArray();
|
---|
| 245 | world[23] = " # . # ".ToCharArray();
|
---|
| 246 | world[24] = " ..##..#####. # ".ToCharArray();
|
---|
| 247 | world[25] = " # # ".ToCharArray();
|
---|
| 248 | world[26] = " # # ".ToCharArray();
|
---|
| 249 | world[27] = " # .#######.. ".ToCharArray();
|
---|
| 250 | world[28] = " # # ".ToCharArray();
|
---|
| 251 | world[29] = " . # ".ToCharArray();
|
---|
| 252 | world[30] = " .####.. ".ToCharArray();
|
---|
| 253 | world[31] = " ".ToCharArray();
|
---|
| 254 |
|
---|
| 255 | posX = 0;
|
---|
| 256 | posY = 0;
|
---|
| 257 | heading = HeadingEnum.East;
|
---|
| 258 | FoodEaten = 0;
|
---|
| 259 | steps = 0;
|
---|
[11976] | 260 |
|
---|
| 261 | this.recordTrail = recordTrail;
|
---|
| 262 | if (this.recordTrail) trailBuilder = new StringBuilder();
|
---|
[11659] | 263 | }
|
---|
| 264 |
|
---|
| 265 | public bool Done() {
|
---|
| 266 | return steps > maxSteps;
|
---|
| 267 | }
|
---|
| 268 |
|
---|
| 269 | public void TurnRight() {
|
---|
| 270 | if (steps <= maxSteps) {
|
---|
| 271 | steps++;
|
---|
| 272 | if (heading == HeadingEnum.West) heading = HeadingEnum.North;
|
---|
| 273 | else heading++;
|
---|
| 274 | }
|
---|
| 275 | }
|
---|
| 276 |
|
---|
| 277 | public void TurnLeft() {
|
---|
| 278 | if (steps <= maxSteps) {
|
---|
| 279 | steps++;
|
---|
| 280 | if (heading == HeadingEnum.North) heading = HeadingEnum.West;
|
---|
| 281 | else heading--;
|
---|
| 282 | }
|
---|
| 283 | }
|
---|
| 284 |
|
---|
| 285 | public void Move() {
|
---|
| 286 | if (steps <= maxSteps) {
|
---|
| 287 | steps++;
|
---|
| 288 | MoveInternal(ref posX, ref posY);
|
---|
| 289 | if (world[posY][posX] == '#') {
|
---|
| 290 | FoodEaten++;
|
---|
| 291 | world[posY][posX] = '.';
|
---|
| 292 | }
|
---|
[11976] | 293 | if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
|
---|
[11659] | 294 | }
|
---|
| 295 | }
|
---|
| 296 |
|
---|
[11976] | 297 | public void Nop() {
|
---|
| 298 | // wait one time step
|
---|
| 299 | if (steps <= maxSteps) {
|
---|
| 300 | steps++;
|
---|
| 301 | }
|
---|
| 302 | }
|
---|
| 303 |
|
---|
[11659] | 304 | private void MoveInternal(ref int posX, ref int posY) {
|
---|
| 305 | switch (heading) {
|
---|
| 306 | case HeadingEnum.North:
|
---|
| 307 | posY = (posY + 31) % 32;
|
---|
| 308 | break;
|
---|
| 309 | case HeadingEnum.East:
|
---|
| 310 | posX = (posX + 1) % 32;
|
---|
| 311 | break;
|
---|
| 312 | case HeadingEnum.South:
|
---|
| 313 | posY = (posY + 1) % 32;
|
---|
| 314 | break;
|
---|
| 315 | case HeadingEnum.West:
|
---|
| 316 | posX = (posX + 31) % 32;
|
---|
| 317 | break;
|
---|
| 318 | }
|
---|
| 319 | }
|
---|
| 320 |
|
---|
| 321 | public bool IsFoodAhead() {
|
---|
| 322 | int nextPosX = posX;
|
---|
| 323 | int nextPosY = posY;
|
---|
| 324 | MoveInternal(ref nextPosX, ref nextPosY);
|
---|
[11976] | 325 |
|
---|
| 326 | if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
|
---|
| 327 |
|
---|
[11659] | 328 | return world[nextPosY][nextPosX] == '#';
|
---|
| 329 | }
|
---|
| 330 | }
|
---|
| 331 | }
|
---|