Entreco - 1 year ago 107
Java Question

# Recursive function to calculate possible finish for darts

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();
}

return canFinish(desired, score);
}

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

I want to simply call:

``````ArrayList<Score> dartsNeeded = new ArrayList<Score>();

// 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.

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 = 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 = 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();
}
}

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+"]";
}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download