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[100];
		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;

	}

}
Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: