title: Recursive function to calculate possible finish for darts
body: <p>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.</p>
  
  <p>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.</p>
  
  <p><strong>Rules:</strong></p>
  
  <p>1) You have three darts which you can throw at number 1 through 20</p>
  
  <p>2) A single hit can have a single, double or triple score</p>
  
  <p>E.g. you can hit:
  single 20 = 20 points or
  double 20 = 40 points or
  triple 20 = 60 points</p>
  
  <p>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</p>
  
  <p>4) Normally, you start at 501, and you throw 3 darts, untill you have exactly 0 points left.</p>
  
  <p>5) Now, in Double Out, it is required that the last dart hits a Double</p>
  
  <p>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)</p>
  
  <p><strong>Current Code</strong></p>
  
  <p>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</p>
  
  <pre><code>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 &gt;= 20)
          {
              this.number = 0;
              this.amount++;
  
              if(this.amount &gt;= 3)
                   this.amount = 3;
          }
      }
  }
  
  public ArrayList&lt;Score&gt; canFinish(int desired, ArrayList&lt;Score&gt; score){
  
          // If this is the case -&gt; we have bingo
          if(eval(score) == desired) return score;
  
          // this is impossible -&gt; return null
          if(eval(score) &gt; 170) return null;
  
          // I can't figure out this part!!
          Score dart3 = score.remove(2);
          Score dart2 = score.remove(1);
  
          if(dart2.eval() &lt; 60){
              dart2.increment();
          }
          else if(dart3.eval() &lt; 60){
              dart3.increment();
          }
  
          score.add(dart2);
          score.add(dart3);
  
          return canFinish(desired, score);
  }
  
  public int eval(ArrayList&lt;Score&gt; scores)
  {
      int total = 0;
      for(Score score : scores){
          total += score.value();
      }
      return total;
  }
  </code></pre>
  
  <p>I want to simply call:</p>
  
  <pre><code>ArrayList&lt;Score&gt; dartsNeeded = new ArrayList&lt;Score&gt;();
  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]] -&gt; 2*16 + 2*17 + 0*0 = 66
  // So I can finish, by throwing Double 17 + Double 16
  </code></pre>
  
  <p>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...</p>
  
  <p><strong>Short Summary</strong></p>
  
  <p>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.</p>