WCC 2012-23

WCC2012_23.groovy

public class WCC2012_23 {
    Expression bestSolution = null
    BigDecimal target = null
    List list

    enum Operation {
        plus('+'), minus('-'), multiply('*'), div('/')
        String symbol

        Operation(String symbol) {
            this.symbol = symbol
        }
    }

    class Expression {
        Expression parent
        Operation operation
        BigDecimal value
        BigDecimal result
        BigDecimal dist
        List subList

        public String toString() {
            if (parent.parent == null) {
                return this.value
            }
            if ((parent.operation < this.operation) && (parent.parent.parent != null)) {
                return "(${parent}) ${operation.symbol} ${value}"
            } else {
                return "${parent} ${operation.symbol} ${value}"
            }
        }
    }

    WCC2012_23(BigDecimal x, List a) {
        this.target = x
        this.list = a
        this.bestSolution = new Expression(dist: a.min { Math.abs(x - it) })
    }

    void walk(List list, Expression parent) {
        list.eachWithIndex { BigDecimal value, idx ->
            def subList = new ArrayList(list)
            subList.remove(idx)
            Operation.each { op ->
                if (parent.result == null || parent.result > value) {
                    def result = parent.result ? parent.result."$op"(value) : value
                    def dist = Math.abs(target - result)
                    def newExpression = new Expression(parent: parent, operation: op, value: value,
                            result: result, subList: subList, dist: dist)
                    if (newExpression.dist < bestSolution.dist) {
                        bestSolution = newExpression
                        println "New best: ${bestSolution} = $bestSolution.result"
                    }
                    if (newExpression.dist == 0) {
                        if (newExpression.subList.size() > bestSolution.subList.size()) {
                            bestSolution = newExpression;
                            println "New best: ${bestSolution} = $bestSolution.result"
                        }
                    } else {
                        walk(subList, newExpression)
                    }
                }
            }
        }
    }

    Expression solve() {
        walk(list, new Expression())
        return bestSolution
    }

    static main(args) {
//        WCC2012_23 wcc = new WCC2012_23(952, [25, 50, 75, 100, 6, 3])
        WCC2012_23 wcc = new WCC2012_23(522, [100, 5, 5, 2, 6, 8])
        def response = wcc.solve()
        println "\nBest solution: ${response} = ${response.result}"
    }

}