PA4

Due: Friday, Mar 17 at 11:59 PM(extended to Mon Mar 20th 11:59pm)

• -20% on Saturday, Mar 18
• -40% on Monday, Mar 19
• Not accepted late.

Objectives

• Write loops that contain nested if-else statements.
• Pass arrays as method arguments and return values.
• Manipulate, copy, and compare arrays of numbers.
• Generate random numbers based on an algorithm.

Honor Code

This assignment should be viewed as a take-home exam and must be completed individually. Your work must conform to the JMU Honor Code. Authorized help is limited to general discussion on Piazza, the lab assistants assigned to CS 149/159, and the instructor. Copying work from another student or the Internet is an Honor Code violation and will be grounds for a reduced or failing grade in the course.

Background

In this assignment, you will write methods that simulate a game for learning to do math in your head:

Math Dice®

The Fast, Fun Dice Game of Mental Math

Math becomes more fun when you think on the fly! Roll the [n-sided die] to get a target number. Roll the [other dice] and combine these numbers using addition, subtraction, multiplication, division, or [modulo] to build an equation that is [equal to] the target. This mentally challenging and fun dice game helps players sharpen math skills by solving problems in a fun new way.

Source: http://www.thinkfun.com/products/math-dice/ [with modifications for PA4 in square brackets]

We recommend that you play Math Dice Classic online to get a feel for the game. For PA4, we will use the % (remainder) operator instead of ^ (raise to power). You will also have any number of dice to work with, not just three. For simplicity, you will not have to implement the order of operations. There will be no parentheses, and all operators will be evaluated left to right using the same precedence. For example, 1 + 2 * 3 will be 9, not 7. And finally, you will not be able to change the order of the dice.

Requirements

Create two files from scratch: MathDice.java and MathDiceTest.java. At the top of MathDice, define the constants:

• public static final int PLUS = 1;
• public static final int MINUS = 2;
• public static final int TIMES = 3;
• public static final int DIVIDE = 4;
• public static final int MODULO = 5;

Your main task will be to implement the following methods in MathDice (and test each of them in MathDiceTest):

• public static int[] rollDice(int count, long seed)

  Given the number of dice and a seed for java.util.Random, this method creates an array of random integers with values between 1 and 6 (inclusive). The values must correspond to the sequence of integers generated from Random.nextInt(int) using the provided seed, so that you can predict the expected return values in JUnit. If count is negative, then the method should return null.

• public static int evaluate(int[] dice, int[] opers)

  Given an array of dice values and operators between them, this method computes the resulting value. For example, if dice is {1, 2, 3} and opers is {PLUS, TIMES}, then the return value would be 9 (i.e., 1 + 2 * 3, without respect to order of operations). If either parameter is null, or if the length of dice is not exactly one more than the length of opers, then the method should return 0.

• public static int[] solve(int target, int[] dice)

  Given a target value and an array of dice, this method returns the first possible solution using the five available operations. For example, if target is 9 and dice is {1, 2, 3}, the return value would be {PLUS, TIMES}. If no solution is possible, then the method should return null. Likewise if the given dice array has a length of zero or is null, then the method should return null.

• public static double difficulty(int[] dice)

  Given a set of dice values, this method approximates how difficult it is to find a solution for them. Specifically, it invokes the solve method for each of the target values 1 to 144, and then returns the percentage of target values that don't have a solution. If the given dice array has a length of zero or is null, then the method returns 0.0.

JUnit is the recommended way to "run" this assignment. However, you may also refer to MathDiceDriver.java which illustrates how your methods might be used in an application.

Algorithm for solve

There are many ways to implement the solve method. For this assignment, we will just use a brute-force approach: one that tries every possibility. Note that for each operator, there are five choices: +, -, *, /, and %. That means there are 5ⁿ possible solutions, where n is the number of operators. For example, if dice were {1, 2, 3}, then there would be two operators and 25 possible solutions:

+ + + - + * + / + %

- + - - - * - / - %

* + * - * * * / * %

/ + / - / * / / / %

% + % - % * % / % %

You can generate each of these solutions using nested loops:

    for (int i = 1; i <= 5; i++) {
        opers[0] = i;
        for (int j = 1; j <= 5; j++) {
            opers[1] = j;
            System.out.println(Arrays.toString(opers));
        }
    }

Organized into five columns, the output of the above loops is:

[1, 1] [1, 2] [1, 3] [1, 4] [1, 5]

[2, 1] [2, 2] [2, 3] [2, 4] [2, 5]

[3, 1] [3, 2] [3, 3] [3, 4] [3, 5]

[4, 1] [4, 2] [4, 3] [4, 4] [4, 5]

[5, 1] [5, 2] [5, 3] [5, 4] [5, 5]

Make sure you see the connection between the operators, the code, and the output above. If you don't, ask questions before reading on!

To solve a Math Dice problem with five operators, there would be five nested loops:

    for (int i = 1; i <= 5; i++) {
        opers[0] = i;
        for (int j = 1; j <= 5; j++) {
            opers[1] = j;
            for (int k = 1; j <= 5; j++) {
                opers[2] = j;
                for (int l = 1; j <= 5; j++) {
                    opers[3] = j;
                    for (int m = 1; j <= 5; j++) {
                        opers[4] = j;
                    }
                }
            }
        }
    }

The only problem is, you don't know in advance how many dice there will be. That's where recursion comes to the rescue! Notice how the above loop pattern repeats. We can reformulate this structure by writing the first loop and then (recursively) calling a method to handle the other loops:

    for (int i = 1; i <= 5; i++) {
        opers[index] = i;
        
method(index + 1);  // repeat the current method
    }

Make sure you see the connection between the nested loops and the recursive code above. If you don't, ask questions before reading on!

To save you some time on the assignment, here is a partial implementation of such a method. Note that it will return the first solution found, so be careful when testing dice with multiple solutions. Paste the following code directly after your solve method in MathDice.java:

    /**
     * Recursively search for solutions beginning at the given index.
     *
     * @param target the original target amount (from the solve method)
     * @param dice the original dice values (from the solve method)
     * @param opers the current operators (to be assigned recursively)
     * @param index the current index of the opers array to assign
     * @return true if opers contains a solution, false otherwise
     */
    private static boolean search(int target, int[] dice, int[] opers, int index) {

        // recursive step: try every operation at this index
        boolean found = false;
        for (int i = 1; i <= 5; i++) {
            opers[index] = i;
            found = search(target, dice, opers, index + 1);
            // return immediately when a solution is found
            if (found) {
                break;
            }
        }
        return found;
    }

To complete this method, you'll need to write the base case (i.e., an if statement at the top) that determines when to stop the recursion. Inside that if statement, you should evaluate the current solution and return true if it's correct (or false if it's not). Then figure out how to call this search method from the solve method to get the whole process started.

Submission

Combine your MathDice.java and MathDiceTest.java into a zip file, and submit via Web-CAT. Do not include MathDiceDriver.java or any other files in your zip archive. There will be no Canvas submission for this assignment.