Using specific numbers to reach a target number

Question

For my assignment, I have to allow the player to select 6 numbers from two different lists as they please.

List<Integer> large = Arrays.asList(25, 50, 75, 100);
List<Integer> small = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
            7, 7, 8, 8, 9, 9, 10, 10);

After they have selected their numbers say [100, 3, 5, 6, 9, 5] they then generate a target number of lets say for example 299 and they then can only use the numbers selected as a means of reaching the target using ONLY multiplication, addition, subtraction and division. So they could input for instance, 100 * 3 + 5 - 6 to reach the 299 target and this would be checked and scored appropriately.

Unfortunately I don't really have much to go on and I'm a bit confused on how to go about even starting to do that, I'm not looking for a straight up answer, maybe some pointers or external help would be much appreciated.

See [subset sum problem](http://en.wikipedia.org/wiki/Subset_sum_problem). — Maroun, Mar 19 '14 at 14:55
@MarounMaroun I don't think the OP has been asked to _solve_ the problem but to _verify a solution_ provided by the program user. This is obviously much easier as it merely involves parsing an expression. — Boris the Spider, Mar 19 '14 at 14:59

score 1 · Answer 1 · answered Mar 19 '14 at 15:15

Is this helpful?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;


public class JavaApplication97 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] s = {1, 2, 3, 4};
        List<Integer> large = new ArrayList<>(Arrays.asList(25, 50, 75, 100));
        List<Integer> small = new ArrayList<>(Arrays.asList(1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10));
        List<Integer> yourNumbers = new ArrayList<>();
        int numbersToSelect = 6;
        while (numbersToSelect > 0) {
            System.out.println("Choose " + numbersToSelect + " numbers from these numbers : " + large + " or " + small);
            Integer input = in.nextInt();
            boolean isItThere = false;
            if (large.contains(input)) {
                isItThere = true;
                large.remove(input);
            } else if (small.contains(input)) {
                isItThere = true;
                small.remove(input);
            }

            if (isItThere) {
                yourNumbers.add(input);
                numbersToSelect--;
                System.out.println("Number " + input + " is added");
            } else {
                System.out.println("There is no such number");
            }
        }
    }
}

Sample output :

Choose 6 numbers from these numbers : [25, 50, 75, 100] or [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
25
Number 25 is added
Choose 5 numbers from these numbers : [50, 75, 100] or [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
25
There is no such number
Choose 5 numbers from these numbers : [50, 75, 100] or [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
5
Number 5 is added
Choose 4 numbers from these numbers : [50, 75, 100] or [1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
5
Number 5 is added
Choose 3 numbers from these numbers : [50, 75, 100] or [1, 1, 2, 2, 3, 3, 4, 4, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
5
There is no such number
Choose 3 numbers from these numbers : [50, 75, 100] or [1, 1, 2, 2, 3, 3, 4, 4, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
100
Number 100 is added
Choose 2 numbers from these numbers : [50, 75] or [1, 1, 2, 2, 3, 3, 4, 4, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
6
Number 6 is added
Choose 1 numbers from these numbers : [50, 75] or [1, 1, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9, 10, 10]
50
Number 50 is added

score 1 · Accepted Answer · answered Mar 19 '14 at 16:02

If we follow Bedmas (brackets exponents division multiplication addition subtraction) we can break this down into a simple function.

First turn the equation into a list of components:

100 * 3 + 5 - 6

changes to

["100", "*", "3", "+", "5", "-", "6"]

Now evaluate every element to make sure that they are valid. ie) Each value in the list of components must be in the selection list or have the value, */+-, Also if there are n nums, then there should be n-1 syms

To get the result we can then evaluate the list,.. merging num-sym-num sections as we go, in the order of bedmas

In pseudo:

func int compute_val(ListString eqn)
    while not eqn.length is 1
        if "*" in eqn
            index = eqn.getIndex("*")
            replace eqn[index -1:index +1] with str((int) eqn[index -1] * (int)eqn[index +1])
        else if "/" in eqn
            index = eqn.getIndex("/")
            replace eqn[index -1:index +1] with str((int) eqn[index -1] / (int)eqn[index +1])
        else if "+" in eqn
            index = eqn.getIndex("+")
            replace eqn[index -1:index +1] with str((int) eqn[index -1] + (int)eqn[index +1])
        else if "-" in eqn
            index = eqn.getIndex("-")
            replace eqn[index -1:index +1] with str((int) eqn[index -1] - (int)eqn[index +1])
    return (int)eqn[0]

This would be the progression of the list as the equation is evaluated in the loop

["100", "*", "3", "+", "5", "-", "6"]  --> ["300", "+", "5", "-", "6"]  --> 
["305", "-", "6"]  --> ["299"]

score 0 · Answer 3 · edited May 23 '17 at 10:31

You need multiple steps, and as I guess this is a homework task I'm not going to give a complete answer, however:

Parse the input string of the user
Calculate the result
Check if the result equals the target number

While 2 and 3 are trivial, the first part is probably the hardest for you and the core of the task. You can get more information on that task here: Smart design of a math parser?

Using specific numbers to reach a target number

3 Answers3