package net.ciklum.icfpc11.plan

/**
 * blabla
 * @author vic
 */
@Typed
final class ConstantPlanner {

    enum Operation { ZERO, DBL, SUCC }

    static final class Constant {
        int value
        int pathLength
        int obtainedFrom
        Operation obtainedBy

        Constant(int value, int pathLength, int obtainedFrom, Operation obtainedBy) {
            this.value = value
            this.pathLength = pathLength
            this.obtainedFrom = obtainedFrom
            this.obtainedBy = obtainedBy
        }

        String toString() { "$obtainedBy->$value" }
    }

    List<Constant> constants = []

    ConstantPlanner() {
        constants = [
            new Constant(0, 0, 0, Operation.ZERO),
            new Constant(1, 1, 0, Operation.SUCC),
        ]
    }

    private static ConstantPlanner theInstance

    static ConstantPlanner getInstance() {
        if (theInstance == null) {
            theInstance = new ConstantPlanner()
        }
        theInstance
    }

    List<Constant> findPath(int target) {
        for (int i = constants.size(); i<=target; i++) {
            addConstant(i)
        }

        return getPathTo(target)
    }

    public String pathToString(List<Constant> path) {
        "(${path.size()})${path.join(';')}"
    }

    private List<Constant> getPathTo(int constant) {
        List<Constant> res = []
        Constant c = constants[constant]
        for(;;) {
            res.add c
            if (c.value == 0) break
            c = constants[c.obtainedFrom]
        }
        return res.reverse()
    }

    private void addConstant(int index) {
        Constant prev = constants[index - 1]
        constants.add(new Constant(index, prev.pathLength + 1, index - 1, Operation.SUCC))
        if (index % 2 == 0) {
            if (constants[index / 2].pathLength < prev.pathLength) {
                constants[-1].obtainedFrom = index / 2
                constants[-1].obtainedBy = Operation.DBL
                constants[-1].pathLength = constants[index / 2].pathLength + 1
            }
        }
    }

}