source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs @ 13042

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  // 4-bit even parity
  public class EvenParityProblem : ISymbolicExpressionTreeProblem {
    // + == OR
    // * == AND
    private const string grammarString = @"
G(S):
S -> a | b | c | d | a*S | b*S | c*S | d*S | a+S | b+S | c+S | d+S | !S | (S)
";
    // A = AND, O = OR, N = NOT, C = Clause
    private const string hlGrammarString = @"
G(E):
E -> A | O | N | C | a | b | c | d 
A -> EE | EEE
O -> EE | EEE
N -> E
C -> E
    ";

    private readonly IGrammar grammar;
    public string Name { get { return "EvenParity"; } }

    public EvenParityProblem() {
      this.grammar = new Grammar(grammarString);
      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
    }

    public double BestKnownQuality(int maxLen) {
      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
      return 16;
    }

    public IGrammar Grammar {
      get { return grammar; }
    }

    public double Evaluate(string sentence) {
      var interpreter = new ExpressionInterpreter(); // for concurrent evaluation
      var vars = new bool[4];
      var nCorrect = 0;
      for (int b0 = 0; b0 <= 1; b0++)
        for (int b1 = 0; b1 <= 1; b1++)
          for (int b2 = 0; b2 <= 1; b2++)
            for (int b3 = 0; b3 <= 1; b3++) {
              vars[0] = b0 > 0;
              vars[1] = b1 > 0;
              vars[2] = b2 > 0;
              vars[3] = b3 > 0;

              var pred = interpreter.Interpret(sentence, vars);
              var target = (b0 > 0) ^ (b1 > 0) ^ (b2 > 0) ^ (b3 > 0);
              if (pred == target) nCorrect++;
            }
      return nCorrect;
    }

    public bool IsOptimalPhrase(string phrase) {
      throw new NotImplementedException();
    }

    public string CanonicalRepresentation(string phrase) {
      throw new NotImplementedException();
      return phrase;
    }

    public IEnumerable<Feature> GetFeatures(string phrase) {
      return new[] { new Feature(phrase, 1.0) };
    }

    public IGrammar TreeBasedGPGrammar { get; private set; }
    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
      var sb = new StringBuilder();

      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);

      return sb.ToString();
    }

    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
      if (treeNode.SubtreeCount == 0) {
        // terminal
        sb.Append(treeNode.Symbol.Name);
      } else {
        switch (treeNode.Symbol.Name) {
          case "O": {
              sb.Append("(");
              TreeToSentence(treeNode.Subtrees.First(), sb);
              foreach (var subTree in treeNode.Subtrees.Skip(1)) {
                sb.Append("+");
                TreeToSentence(subTree, sb);
              }
              sb.Append(")");
              break;
            }
          case "A": {
              TreeToSentence(treeNode.Subtrees.First(), sb);
              foreach (var subTree in treeNode.Subtrees.Skip(1)) {
                sb.Append("*");
                TreeToSentence(subTree, sb);
              }
              break;
            }
          case "N": {
              Debug.Assert(treeNode.SubtreeCount == 1);
              sb.Append("!(");
              TreeToSentence(treeNode.Subtrees.Single(), sb);
              sb.Append(")");
              break;
            }
          case "C": {
              Debug.Assert(treeNode.SubtreeCount == 1);
              sb.Append("(");
              TreeToSentence(treeNode.Subtrees.Single(), sb);
              sb.Append(")");
              break;
            }
          default: {
              Debug.Assert(treeNode.SubtreeCount == 1);
              TreeToSentence(treeNode.Subtrees.Single(), sb);
              break;
            }
        }
      }
    }
  }
}