## Football Score Solver Example

For a Java Developer position I applied for I needed to write a sample program.  Here’s the problem it was intended to solve:

Please create a program that will calculate possible combinations of football scores that will total exactly 21 points.

For this program the following scores should be used.

• 2 points are gained for a Safety.
• 3 points are gained for a Field Goal.
• 6 points are gained for a Touchdown.

Only after a touchdown is scored may one of the following be attempted; however, the attempt can fail.

• 1 point can be gained for an Extra Point attempt.
• 2 points can be gained for a Two-point Conversion attempt.

I had some help from joannac_ on #xkcd-cs in identifying that this was a variation on the coin changing problem and a review of adapting that algorithm to this situation.  But the Java was all me.

This is what I wrote for a solution:

```import java.util.List;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class FootballSolver {
public static final int[] PLAYS = {
2,3,6,7,8
};

private int[] solutions;

public FootballSolver() {
// initialize solutions vector
int i;
solutions = new int;
for (i = 0; i < solutions.length; i++) {
solutions[i] = 0;
}

}

public static void main(String[] args) {
// TODO get final score from user
InputStreamReader isr	      = new InputStreamReader(System.in);
BufferedReader    br          = new BufferedReader(isr);
String            finalScore;
int               targetScore = 0;

while (true) {
try {
System.out.println("Enter target score:");
finalScore = br.readLine();

// parse integers out of input
targetScore = Integer.parseInt(finalScore);

// break out of loop
break;
}

catch (NumberFormatException nfex) {
System.out.println("Please enter a number.");
continue;
}

catch (java.io.IOException ioex) {
System.err.println(ioex.getMessage());
}

}

// call breakdown
new FootballSolver().breakdown(targetScore, 0, 0);
}

public void breakdown(int score, int playIndex, int solutionIndex) {
int solution = 0;
int i        = 0;

if (score == 0) {
// we are successful, print solution
/*
* I'm using the old fashioned incrementation to
* iterate the solutions list because I need to
* check if we're at the end of the list or not
* so I know wheter to print a comma or a newline.
*/
for (i = 0; i < solutionIndex; i++) {
solution = solutions[i];

System.out.print(solution);

switch (solution) {
case 2:
System.out.print(" (safety)");
break;
case 3:
System.out.print(" (field goal)");
break;
case 6:
System.out.print(" (touchdown)");
break;
case 7:
System.out.print(" (touchdown with extra point)");
break;
case 8:
System.out.print(" (touchdown with two-point conversion)");
break;
}

if (i == solutionIndex - 1) {
System.out.print("\n");
}

else {
System.out.print(", ");
}

}

}

else if (score > 0) {
for (i = playIndex; i < PLAYS.length; i++) {
solutions[solutionIndex] = PLAYS[i];
breakdown(score - PLAYS[i], i, solutionIndex + 1);
}

}

return;

}

}
```

1. #1 by Joshua on April 14, 2011 - 4:54 PM

BTW, Chad, Line 107 is recursion. Not this. 🙂

It’s recursion because the method calls itself as part of its execution. The exit clause is the score being < 0. It then pops back up to the next iteration of the for loop on line 105 and calls itself again. 😉