Find the operations - with groovy

/* A "find-the-operations" problem

   Given the sequence

       1   2   3    4    5    6    7    8     9     =   2011

   Find the operations (+,-,*,/) to insert between the numbers.
   Arbitrary parenthizing is allowed.
   If there are solutions: How many?

   For the solution, I use the GPars framework http://gpars.codehaus.org/
   for achieving multi-threaded execution

   The Master task determines the different ways of parenthizing. In the
   example, we have C_8 = 1430 different ways to place the brackets.
   C_8 = (2n)!/((n+1)*n!^2) is the eighth Catalan number.

   For each bracket pattern, the slave substitutes the 4 operations
   at the 8 placeholders of the pattern. Thus, each slave performs
   2^(2*8) evaluations.

   The part that needs the most computing power is the execution of
   the computation (who wonders?)

   In order to avoid losing hits due to precision problems, I use rational numbers.

   My final implementation in C++ improved performance by a factor of 10'000, showing that
   the choice of language *is* important. Anyway, the Groovy implementation shows a lot
   of tricks that can be played with this language. Its power is its expressiveness,
   approaching closely yet the "develop by config" vision. It is a very good choice for
   coding located near a user interface. It is a not so good choice for computational
   tasks like this one.

   See my github folder https://github.com/rplantiko/computeExpressions for the final
   implementation in C++

   Requires groovy class RationalNumber, see http://pastebin.com/J2fhdMSP


*/

import groovyx.gpars.*
import groovyx.gpars.actor.*
import groovyx.gpars.actor.Actors.*
import static groovyx.gpars.actor.Actors.actor
import java.util.concurrent.CountDownLatch

// An Enum for the basic operations (+,-,*,/)
import static Operation.*

//start the actors
File logfile = new File(/D:\groovy\log.txt/)

def master = new CalculatorMaster(numberOfActors:8,size:9,expectedResult:2011,logfile:logfile)
master.allOperations.each { println it }
master.start()
master.waitUntilDone()

println "\nDone"


// Messages
private final class Operations { int size; List<List> data; int expectedResult  }
private final class Result { List<List> data }

//Worker actor
final class CalculatorActor extends AbstractPooledActor {
  void act() {
    loop {
      react {message ->
        switch (message) {
          case Operations:
            Result r = new Result(data:[])
            message.data.each {
              List<List> result = new Combinator(
                message.size,
                it,
                new RationalNumber( message.expectedResult,1) ).findMatches()
              if (result.size > 0) r.data.push( result )
              }
            reply r
            }
          }
      }
    }
  }

//Master actor
final class CalculatorMaster extends AbstractPooledActor {

    int expectedResult = 6
    int size = 5
    int numberOfActors = 5
    File logfile

    private CountDownLatch startupLatch = new CountDownLatch(1)
    private CountDownLatch doneLatch

    private int startTasks() {
      List<List<Integer>> operations = getAllOperations()
      int cnt = sendTasksToWorkers( operations )
      doneLatch = new CountDownLatch(cnt)
      operations.size
    }

    private List createWorkers() {
        return (1..numberOfActors).collect {new CalculatorActor().start()}
    }

    public List<List<Integer>> getAllOperations() {
      List<List<Integer>> operations = []
      buildOperation( [], operations )
      return operations
      }

    private void buildOperation( List<Integer> operation, List<List<Integer>> operations ) {
      def k = operation.size()
      def s = k > 0 ? operation.sum() : 0
      if (k < size - 2) {
        (k+2).times {
          if (s+it<k+2) {
// copy this trunk
            ArrayList child = new ArrayList( operation )
// Add the current index
            child.push it
// Recur to next lower level
            buildOperation( child, operations )
            }
          }
        }
       else {
// Lowest level reached - another operation is complete
        assert size-s >= 1
        operation.push( size-s-1 )     // The last index can be computed
        operations.push( operation )   // Push to result
        }
      }

    private int sendTasksToWorkers(List<List> operations) {
        List<AbstractPooledActor> workers = createWorkers()
        int cnt = 0
        operations.each {
          workers[cnt % numberOfActors] << new Operations(size:size,expectedResult:expectedResult,data:[it])
          cnt += 1
        }
        return cnt
    }

    public void waitUntilDone() {
        startupLatch.await()
        doneLatch.await()
    }

    void act() {
        int numberOfOperations = startTasks()
        startupLatch.countDown()
        println "$numberOfOperations operations"
        logfile.write "$numberOfOperations operations\n"
        loop {
            react {
                switch (it) {
                    case Result:
                        print "."
                        it.data.each {
                          if (it) println ""
                          it.each {
                            println it
                            logfile << it << "\n"
                            }
                          }
                        doneLatch.countDown()
                }
            }
        }
    }
}


class Combinator {

  ArrayList allocation = []
  final RationalNumber expectedResult
  final int size
  private acc = []
  List<List> result = []
  private final static Operation[] ops = [ PLUS, MINUS, TIMES, BY ];

  public Combinator( int size, ArrayList operations, RationalNumber expectedResult) {
    assert operations.size == size - 1
    assert operations.sum()  == size - 1
    this.size = size
    this.expectedResult = expectedResult
    int numOpCount = 0
    size.times {
      allocation.push it + 1
      if (it >= 1) {
        numOpCount += operations[it-1]
        assert numOpCount <= it
        operations[it-1].times {
          allocation.push ANY
          }
        }
      }
    }

  public List findMatches() {

    final BigInteger differentAllocations = 1 << 2*(size-1)

// Look for the places with operations - needs to be done only once
    List<Integer> allocIndex = []
    allocation.eachWithIndex { it, index ->
      if (it instanceof Operation) {
        allocIndex.push index
        }
      }
    assert allocIndex.size == size - 1

    differentAllocations.times { iAlloc ->
      (size-1).times { i ->
        allocation[allocIndex[i]] = ops[iAlloc & 0x3]
        iAlloc = iAlloc >> 2
        }
      if (Calculator.evaluate(allocation).equals(expectedResult)) {
        result.push new ArrayList(allocation)
        }
      }

    return result

    }


  }


class Calculator {
  public static Object evaluate(ArrayList input) {
    def exception = null
    Operation x;
    def stack = new Calculator.ExecutionStack()
    input.each {
      if (it instanceof Operation) {
        stack.apply it
        }
      else {
        stack.push new RationalNumber(it,1)
        }
      }
    return stack.result
    }

  static class ExecutionStack {
    private Stack s = []
    def apply = { op ->
      def right = s.pop()
      def left  = s.pop()
      s.push op.apply( left, right )
      }
    def push = { arg -> s.push( arg ) }
    public getResult() { s.pop() }
    }

  }

enum Operation {
  PLUS({ a,b -> a+b }, '+'),
  MINUS({ a,b -> a-b }, '-'),
  TIMES({ a,b -> a*b }, '*'),
  BY({ a,b -> a/b }, '/')
  private final Closure op;
  private final String glyph;
  Operation(Closure op, String glyph) { this.op = op; this.glyph = glyph }
  Operation(String glyph) { this.glyph = glyph }
  def apply = { a,b -> op(a,b) }
  public static final ANY = TIMES;
  public String toString() { glyph }
  }


assert Calculator.evaluate([1,2,3,PLUS,PLUS]) == new RationalNumber( 6, 1 )
assert Calculator.evaluate([1,2,PLUS,3,TIMES,6,4,MINUS,MINUS]) == new RationalNumber( 7, 1 )
assert Calculator.evaluate([1,0,BY]) == RationalNumber.DIV_BY_ZERO
assert Calculator.evaluate([2,1,MINUS]) == new RationalNumber( 1, 1 )