source: branches/HeuristicLab.Problems.GPDL/Examples/multi-output-multiplier.txt @ 17578

PROBLEM MultiOutputMultiplier

CODE <<
  const int N = 4;
  class State { public bool[] x1; public bool[] x2; public bool[] output; }
  private void GenerateProblemData(int n, out bool[][] a, out bool[][] b, out bool[][] expectedOutput) {
    var nConfigurations = (int)Math.Pow(2, n);
    var e = from i in Enumerable.Range(0, nConfigurations)
            from j in Enumerable.Range(0, i+1)
            select new {a = ToBitArray(N, i), b = ToBitArray(N, j), res = ToBitArray(2*N, i*j) };
    
    a = e.Select(x=>x.a).ToArray();
    b = e.Select(x=>x.b).ToArray();
    expectedOutput = e.Select(x=>x.res).ToArray();
  }
  
  private bool[] ToBitArray(int n, int x) {
    var b = new bool[n];
    for(int i=0; i<n; i++) {
      b[n - i - 1] = (x % 2) == 0;
      x = x / 2;
    }
    if(x>0) throw new ArgumentException();
    return b;
  }
>>

NONTERMINALS
  Expr<<State state, out bool res>>.
  Assign<<State state, out bool res>>.
  AND<<State state, out bool res>>.
  AND1<<State state, out bool res>>.
  XOR<<State state, out bool res>>.
  OR<<State state, out bool res>>.
  

TERMINALS
  InputA<<out int id>> 
    CONSTRAINTS
      id IN SET << Enumerable.Range(0, N) >>
  .
  
  InputB<<out int id>> 
    CONSTRAINTS
      id IN SET << Enumerable.Range(0, N) >>
  .
  
  Output<<out int id>>  
    CONSTRAINTS
      id IN SET << Enumerable.Range(0, 2 * N) >>
  .

RULES
  Expr<<State state, out bool res>> =                   LOCAL << int id; >>
    Assign<<state, out res>>
    | AND<<state, out res>>
    | AND1<<state, out res>>
    | XOR<<state, out res>>
    | OR<<state, out res>>
    | InputA<<out id>>                                                          SEM<< res = state.x1[id]; >>
    | InputB<<out id>>                                                          SEM<< res = state.x2[id]; >>
    | Output<<out id>>                                                          SEM<< res = state.output[id]; >>
  .                                                                             
                                                                                
  Assign<<State state, out bool res>> =                 LOCAL << int outId; >>
    Output<<out outId>>  Expr<<state, out res>>                        SEM<< state.output[outId] = res; >>
  .
  
  AND<<State state, out bool res>> =                    LOCAL << bool resA, resB; >>
    Expr<<state, out resA>> Expr<<state, out resB>>           SEM << res = resA & resB; >>
  .
  AND1<<State state, out bool res>> =                   LOCAL << bool resA, resB; >>
    Expr<<state, out resA>> Expr<<state, out resB>>           SEM << res = resA & !resB; >>
  .
  XOR<<State state, out bool res>> =                    LOCAL << bool resA, resB; >>
    Expr<<state, out resA>> Expr<<state, out resB>>           SEM << res = resA ^ !resB; >>
  .
  OR<<State state, out bool res>> =                     LOCAL << bool resA, resB; >>
    Expr<<state, out resA>> Expr<<state, out resB>>           SEM << res = resA | resB; >>
  .

MINIMIZE
  <<
    bool[][] a, b, expectedOutput;
    GenerateProblemData(N, out a, out b, out expectedOutput);
    
    int sumErr = 0;
    for(int i=0; i<expectedOutput.Length; i++) {
      bool tmp;
      // evaluate tree for inputs a and b
      var state = new State();
      state.x1 = a[i]; state.x2 = b[i]; state.output = new bool[2*N];
      Expr(state, out tmp);

      // count incorrect bits
      for(int j=0;j<state.output.Length;j++) {
        if(state.output[j] != expectedOutput[i][j]) sumErr++;
      }
    }
    return (double)sumErr;
  >>
END MultiOutputMultiplier.