source: branches/HeuristicLab.Problems.GPDL.Backend/HeuristicLab.Problems.GPDL.Views/3.4/Resources/Multiplexer.txt

PROBLEM Multiplexer

NONTERMINALS
  Expr<<bool[] d, out bool o>>.
  AND<<bool[] d, out bool o>>.
  OR<<bool[] d, out bool o>>.
  NOT<<bool[] d, out bool o>>.
  IF<<bool[] d, out bool o>>.

TERMINALS
  A0. A1. A2. D0. D1. D2. D3. D4. D5. D6. D7.

RULES
  Expr<<bool[] d, out bool o>> =
    AND<<d, out o>>
    | OR<<d, out o>>
    | NOT<<d, out o>>
    | IF<<d, out o>>
    | A0                                                   SEM<< o = d[0]; >>
    | A1                                                   SEM<< o = d[1]; >>
    | A2                                                   SEM<< o = d[2]; >>
    | D0                                                   SEM<< o = d[3]; >>
    | D1                                                   SEM<< o = d[4]; >>
    | D2                                                   SEM<< o = d[5]; >>
    | D3                                                   SEM<< o = d[6]; >>
    | D4                                                   SEM<< o = d[7]; >>
    | D5                                                   SEM<< o = d[8]; >>
    | D6                                                   SEM<< o = d[9]; >>
    | D7                                                   SEM<< o = d[10]; >>
  .

  AND<<bool[] d, out bool o>> =                            LOCAL << bool o1, o2; >>
    Expr<<d, out o1>> Expr<<d, out o2>>                    SEM << o = o1 & o2; >>
  .

  OR<<bool[] d, out bool o>> =                             LOCAL << bool o1, o2; >>
    Expr<<d, out o1>> Expr<<d, out o2>>                    SEM << o = o1 | o2; >>
  .

  NOT<<bool[] d, out bool o>> =
    Expr<<d, out o>>                                       SEM << o = !o; >>
  .

  IF<<bool[] d, out bool o>> =                             LOCAL << bool pred; >>
    Expr<<d, out pred>>                                    SEM << if(pred) { >> 
    Expr<<d, out o>>                                       SEM << } else { >>
    Expr<<d, out o>>                                       SEM << } >>
  .

MINIMIZE
  << 
    int N = 11;
    bool[] d = new bool[N];
    int mistakes = 0;
    for(int i = 0; i < Math.Pow(2, N); i++) {
      // generate bit-vector and count number of 1-bits
      int x = i;
      for(int j = 0; j < N; j++) {
        d[N - j - 1] = ((x % 2) == 1);
        x = (x / 2);
      }
      bool target = d[3 + (d[0] ? 1:0) + 2 * (d[1] ? 1:0) + 4 * (d[2] ? 1:0)];

      // apply model
      bool p;
      Expr(d, out p);

      if(p != target) mistakes++;
    }
    return mistakes;
  >>
END Multiplexer.