source: branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs @ 13365

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using HeuristicLab.Grammars;

namespace CodeGenerator {
  public class BruteForceCodeGen {

    private string solverTemplate = @"

namespace ?PROBLEMNAME? {
  public sealed class ?IDENT?BruteForceSolver {
    private static int maxDepth = 20;

    private readonly ?IDENT?Problem problem;
    private readonly Random random;

    private IEnumerable<Tree> GenerateTrees(int parentState, int depth) {
      if(depth<=1) {
        if(Grammar.subtreeCount[parentState] == 0) 
          foreach(var terminal in CreateTerminalNodes(parentState, problem)) 
            yield return terminal;
      } else if(Grammar.subtreeCount[parentState] == 1) {
        for(int altIdx = 0; altIdx < Grammar.transition[parentState].Length; altIdx++) {
          var targetState = Grammar.transition[parentState][altIdx];
          foreach(var subtree in GenerateTrees(targetState, depth - 1)) {
            var solution = new Tree(altIdx, new Tree[1] {subtree});
            yield return solution;
          }
        }
      } else if(Grammar.subtreeCount[parentState] > 1) {
        var nums = Enumerable.Range(1, depth - 1);
        var depthCombinations = CartesianProduct(Enumerable.Repeat(nums, Grammar.subtreeCount[parentState]))
           .Where(comb => comb.Max() == depth - 1);
        foreach(var depthCombination in depthCombinations) {
          var trees = new IEnumerable<Tree>[Grammar.subtreeCount[parentState]];
          var depthCombinationEnumerator = depthCombination.GetEnumerator();
          depthCombinationEnumerator.MoveNext();
          for(int subtreeIdx = 0; subtreeIdx < Grammar.subtreeCount[parentState]; subtreeIdx++) {
            trees[subtreeIdx] = GenerateTrees(Grammar.transition[parentState][subtreeIdx], depthCombinationEnumerator.Current);
            depthCombinationEnumerator.MoveNext();
          }
          foreach(var e in CartesianProduct(trees)) {
            yield return new Tree(-1, e.ToArray()); // altIdx is ignored
          }
        }
      } 
    }

    public IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sets) {
      if(sets.Count() == 1) { 
        foreach(var e in sets.First()) {
          yield return new T[] {e};
        }
      }
      else {
        var firstSet = sets.First();
        foreach(var e in firstSet) {
          foreach(var p in CartesianProduct(sets.Skip(1))) {
            yield return new T[] {e}.Concat(p);
          }
        }
      }
    }

    private static IEnumerable<Tree> CreateTerminalNodes(int state, ?IDENT?Problem problem) {
      switch(state) {
        ?CREATETERMINALNODECODE?
        default: { throw new ArgumentException(""Unknown state index"" + state); }
      }
    }

    private void ParseArguments(string[] args) {
      var maxDepthRegex = new Regex(@""--maxDepth=(?<d>.+)"");

      var helpRegex = new Regex(@""--help|/\?"");
      
      foreach(var arg in args) {
        var maxDepthMatch = maxDepthRegex.Match(arg);
        var helpMatch = helpRegex.Match(arg);
        if(helpMatch.Success) { 
          PrintUsage(); Environment.Exit(0);
        } else if(maxDepthMatch.Success) {
           maxDepth = int.Parse(maxDepthMatch.Groups[""d""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
           if(maxDepth < 1 || maxDepth > 100) throw new ArgumentException(""max depth must lie in range [1 ... 100]"");
        } else {
           Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0); 
        }
      }
    }
    private void PrintUsage() {
      Console.WriteLine(""Find a solution using brute force tree search."");
      Console.WriteLine();
      Console.WriteLine(""Parameters:"");
      Console.WriteLine(""\t--maxDepth=<depth>\tSets the maximal depth of sampled trees [Default: 20]"");
      Console.WriteLine(""\t--help\tPrints this help text."");
    }



    public ?IDENT?BruteForceSolver(?IDENT?Problem problem, string[] args) {
      if(args.Length>1) ParseArguments(args);
      this.problem = problem;
      this.random = new Random();
    }

    public void Start() {
      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
      int n = 0;
      long sumDepth = 0;
      long sumSize = 0;
      var sumF = 0.0;
      var sw = new System.Diagnostics.Stopwatch();
      sw.Start();
      for(int depth = 1; depth < maxDepth; depth ++) {
        Console.WriteLine(""Depth {0}:"", depth);
        foreach(var t in GenerateTrees(0, depth)) {
          var f = problem.Evaluate(t);
          // t.PrintTree(0); Console.WriteLine();
          var size = t.GetSize();
          sumSize += size;
          sumDepth += depth;
          n++;    
          sumF += f;
          if (problem.IsBetter(f, bestF)) {
            bestF = f;
            t.PrintTree(0); Console.WriteLine();
            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, size, depth);
          }
          if (n % 1000 == 0) {
            sw.Stop();
            Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"",
                              n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
            sumSize = 0;
            sumDepth = 0;
            sumF = 0.0;
            sw.Restart();
          }
        }
        Console.WriteLine(""n={0}"",n);
      }
    }
  }
}";

    public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
      var solverSourceCode = new SourceBuilder();
      solverSourceCode.Append(solverTemplate)
        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
      ;

      problemSourceCode.Append(solverSourceCode.ToString());
    }

    private string GenerateCreateTerminalCode(IGrammar grammar, IEnumerable<TerminalNode> terminals) {
      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
      var sb = new SourceBuilder();
      var allSymbols = grammar.Symbols.ToList();
      foreach (var s in grammar.Symbols) {
        if (grammar.IsTerminal(s)) {
          sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
          var terminal = terminals.Single(t => t.Ident == s.Name);
          if (terminal.Constraints.Any(c => c.Type == ConstraintNodeType.Range)) {
            throw new NotSupportedException("Sorry the brute force solver does not support RANGE constraints");
          }
          sb.AppendFormat("{0}Tree t = null;", terminal.Ident).AppendLine();
          // create nested loop to produce all combinations of values (only set constraints)
          foreach (var constr in terminal.Constraints) {
            sb.AppendFormat("foreach(var {1} in problem.GetAllowed{0}_{1}()) {{;", terminal.Ident, constr.Ident).BeginBlock();
          }
          sb.AppendFormat("t = new {0}Tree();", terminal.Ident).AppendLine();

          foreach (var constr in terminal.Constraints) {
            sb.AppendFormat("t.{0} = {0};", constr.Ident);
          }
          sb.AppendLine("yield return t; ");

          foreach (var _ in terminal.Constraints) {
            sb.AppendLine("}").EndBlock();
          }


          sb.AppendLine(" break; }");
        }
      }
      return sb.ToString();
    }
  }
}