Recursive function to calculate possible finish for darts

Question

I'm trying to write a recursive function in Java, to determine how to finish for a game of Darts. Basically, you have a maximum of 3 darts, en you have to finish with a double.

If you don't know the rule of Darts x01 games with Double Out finishing, it's difficult to understand this question... Let me try to explain. For simplicity, I keep the Bull's eye out of the equation for now.

Rules:

1) You have three darts which you can throw at number 1 through 20

2) A single hit can have a single, double or triple score

E.g. you can hit: single 20 = 20 points or double 20 = 40 points or triple 20 = 60 points

3) In one turn, you can score a maximum of 180 points (3x triple 20 = 3*60 = 180). Anything higher than 180 is impossible. This doesn't mean anything below 180 IS possible. 179 for example, is impossible as well, because the next best score is triple20+triple20+triple19 = 167

4) Normally, you start at 501, and you throw 3 darts, untill you have exactly 0 points left.

5) Now, in Double Out, it is required that the last dart hits a Double

E.g. if you have 180 points left, you cannot finish, because your last dart has to be a double. So the maximum (with ignoring the bulls eye) = triple20 + triple20 + double20 = 160 And if your score is 16, you can simply finish using 1 dart by hitting the double 8. Another example, if your score is 61, you can hit triple17 + double5 (= 51 + 10)

Current Code

Anyway, below is what I have so far. I know it's far from what I need, but no matter what I try, i always get stuck. Perhaps someone can share his thoughts on an another approach

private class Score{
    int number;    // the actual number, can be 1...20
    int amount;    // multiplier, can be 1, 2 or 3
    public Score(int number, int amount){
        this.number = number;    // the actual number, can be 1...20
        this.amount = amount;    // multiplier, can be 1, 2 or 3
    }
    public int value()
    {
        return number * amount;   // the actual score
    }

    public void increment()
    {
        if(this.amount == 0)
            this.amount = 1;

        this.number++;
        if(this.number >= 20)
        {
            this.number = 0;
            this.amount++;

            if(this.amount >= 3)
                 this.amount = 3;
        }
    }
}

public ArrayList<Score> canFinish(int desired, ArrayList<Score> score){

        // If this is the case -> we have bingo
        if(eval(score) == desired) return score;

        // this is impossible -> return null
        if(eval(score) > 170) return null;

        // I can't figure out this part!!
        Score dart3 = score.remove(2);
        Score dart2 = score.remove(1);

        if(dart2.eval() < 60){
            dart2.increment();
        }
        else if(dart3.eval() < 60){
            dart3.increment();
        }

        score.add(dart2);
        score.add(dart3);

        return canFinish(desired, score);
}

public int eval(ArrayList<Score> scores)
{
    int total = 0;
    for(Score score : scores){
        total += score.value();
    }
    return total;
}

I want to simply call:

ArrayList<Score> dartsNeeded = new ArrayList<Score>();
dartsNeeded.add(new Score(16, 2));   // Add my favourite double
dartsNeeded.add(new Score(0, 0));
dartsNeeded.add(new Score(0, 0));

// and call the function
dartsNeeded = canFinish(66, dartsNeeded);

// In this example the returned values would be:
// [[16,2],[17,2],[0,0]] -> 2*16 + 2*17 + 0*0 = 66
// So I can finish, by throwing Double 17 + Double 16

So, if it is impossible to finish, the function would return null, but if there is any possible finish, i reveive that ArrayList with the 3 darts that I need to make my desired score...

Short Summary

The problem is that the above code only helps to find 1 dart, but not for the combination of the two darts. So canFinish(66, darts) works -> but canFinish(120, darts) gives a StackOverflow Exception. For 120, I would expect to get somthing like triple20, double14, double16 or any other valid combination for that matter.

Answer 1

class RecursiveDartboard {

    public Set<Out> outsFor(int target) {
        HashSet<Out> outs = new HashSet<>();

        for (Score doubleScore : doubles()) {
            List<Score> scores = new ArrayList();
            scores.add(doubleScore);

            outs.addAll(recursiveOutsFor(target, scores)
                .stream()
                .filter(Optional::isPresent)
                .map(Optional::get)
                .collect(toList())
            );
        }

        return outs;
    }

    private List<Optional<Out>> recursiveOutsFor(int target, List<Score> scores) {
        List<Optional<Out>> outs = new ArrayList<>();

        Out possibleOut = new Out(scores);
        if (possibleOut.target() == target) {
            outs.add(of(possibleOut));
        } else if (scores.size() == 3) {
            outs.add(empty());
        } else {
            for (Score score : allPossibleScores()) {
                List<Score> nextScores = new ArrayList<>();
                nextScores.addAll(scores);
                nextScores.add(score);
                outs.addAll(recursiveOutsFor(target, nextScores));
            }
        }

        return outs;
    }
}

Answer 2

I ended up using the following functions. Which kind of is a combination of switch statments and recursion... Hope someone finds it as usefull as I

public static void getCheckout(int score, int fav_double, ICheckOutEvent listener)
{
    if(score > 170) return;
    if(score == 170) listener.onCheckOut("T20 T20 Bull");

    ArrayList<Dart> darts = new ArrayList<Dart>();
    darts.add(new Dart(fav_double, 2));
    darts.add(new Dart(0,0));
    darts.add(new Dart(0,0));

    darts = getDarts(score, darts);

    if(darts != null) {
        listener.onCheckOut(toString(darts));
        return;
    }

    for(int dubble = 20 ; dubble >= 1 ; dubble--)
    {
        if(dubble == fav_double) continue;

        darts = new ArrayList<Dart>();
        darts.add(new Dart(dubble, 2));
        darts.add(new Dart(0,0));
        darts.add(new Dart(0,0));
        darts = getDarts(score, darts);

        if(darts != null){
            listener.onCheckOut(toString(darts));
            return;
        }
    }   
}

public static ArrayList<Dart> getDarts(int desired, ArrayList<Dart> score)
{
    Dart dart1 = canFinish(desired);
    if(dart1 != null){
        score.set(0, dart1);
        return score;
    }

    int rest = desired - score.get(0).value();
    Dart dart2 = canScore(rest);
    if(dart2 != null)
    {
        score.set(0, score.get(0));
        score.set(1, dart2);
        return score;
    }

    Dart temp = score.get(1);

    if(temp.increment())
    {
        rest = desired - score.get(0).value() - temp.value();
        score.set(0, score.get(0));
        score.set(1, temp);

        Dart dart3 = canScore(rest);
        if(dart3 != null)
        {
            score.set(2, dart3);
            return score;
        }

        if(rest > 60 && temp.increment()) 
            temp.estimate(rest / 2);

        score.set(1, temp);
        return getDarts(desired, score);
    }

    return null;
}

public static int eval(ArrayList<Dart> scores)
{
    int total = 0;
    for(Dart score : scores){
        total += score.value();
    }
    return total;
}

public static Dart canFinish(int points)
{
    switch(points)
    {
        case 2: return new Dart(1, 2);
        case 4: return new Dart(2, 2);
        case 6: return new Dart(3, 2);
        case 8: return new Dart(4, 2);
        case 10: return new Dart(5, 2);
        case 12: return new Dart(6, 2);
        case 14: return new Dart(7, 2);
        // etc. etc.
        case 40: return new Dart(20, 2);
        case 50: return new Dart(25, 2);
    }

    return null;
}

public static Dart canScore(int points)
{
    switch(points)
    {
        case 1: return new Dart(1, 1);
        case 2: return new Dart(2, 1);
        case 3: return new Dart(3, 1);
        // etc. etc.
        case 20: return new Dart(20, 1);
        case 21: return new Dart(7, 3);
        case 22: return new Dart(11, 2);
        //case 23: impossible
        case 24: return new Dart(12, 2);
        // etc. etc.
        case 57: return new Dart(19, 3);
        case 60: return new Dart(20, 3);
    }

    return null;
}

And for completeness, here's the Dart class I created as a helper

private static class Dart{
    int number;
    int amount;
    public Dart(int number, int amount){
        this.number = number;
        this.amount = amount;
    }
    public int value()
    {
        return number * amount;
    }

    public void estimate(int estimate)
    {
        Dart temp = canScore(estimate);
        if(temp != null){
            this.amount = temp.amount;
            this.number = temp.number;
        } else{
            this.number = estimate / 3;
            if(number >= 19)
                this.number = 19;

            this.amount = 3;
        }
    }

    public boolean increment()
    {   
        if(this.amount == 3 && this.number == 20)
            return false;

        if(this.amount == 0)
            this.amount = 1;

        this.number++;
        if(this.number >= 20)
        {
            this.number = 20;
            this.amount++;

            if(this.amount >= 3){
                this.amount = 3;
            }
        }

        return true;
    }

    public String toString()
    {
        return "["+number+","+amount+"]";
    }
}

Answer 3

If you log the scores that canFinish tries, you can see that there are a lot of possibilities missed out. Values of 20 are ignored, and one dart is incremented completely before the other dart values are modified.

Instead, it can be solved recursively as follows. canFinish(desired, score) returns any combination of darts that can be added to score to give the total of desired. Call it with a list of however many darts you know, or any empty list to find any possibility.

canFinish(desired, score)
    if darts sum to desired, return desired
    if there are fewer than 3 darts in score
        for each possible value of a dart (if it's the last dart, check for a double)
            add dart to score
            if canFinish(desired, score) != null
                return canFinish(desired, score)
            end
            remove dart from score
        end
    end
    return null
end