Entreco - 1 year ago 53

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

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 Source

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+"]";
}
}
```