Implementing and fixing a recursion method in Java

Question

    public boolean generateProblems(Integer[] nums, int start) {

    if (start == nums.length) {
        return false;
    }

    for (int i = -range; i < range; i++) {
        nums[start] = nums[start] + i;
        System.out.println(printArray(nums));
        Target game = new Target(nums, target);
        if (game.solutionSize() == difficulty) {
            if (!possibleGames.contains(game.getValues())) {
                possibleGames.add(game.getValues());
            }
            return false;
        }

        if (generateProblems(nums, start + 1)) {
            return true;
        }
        nums[start] = nums[start] - i;

    }

    return false;

}

Overview: In the game, 24, you must add, subtract, divide, and multiply four numbers to reach the target, 24. I have a similar, more abstract class called Target, which takes an array of integers and counts (and solves) the solutions to reach a given target value.

I have another class called TargetGenerator which takes a "seed array", a target value, the range, and the number of solutions requested (difficulty). What it should do is call the method, generateProblems, to get a list of possible games such that this combination will only contain difficulty solutions. These possible games are bounded by the initial seed array plus/minus the range. (The seed, {2,3,4,5} with a range 3 is bounded from {-1,0,1,2} up to, but not including, {5,6,7,8}.)

However, the issue I'm having is I have no bloody idea why this isn't working. .Printing out the combinations tried in the console indicates it starts fine, but doesn't end up well.

With a seed of {6,2,3,12}, target of 24, and a range of 3:

2 2 3 12 
2 -2 3 12 
2 -2 -1 12 
2 -2 -1 8 
2 -2 -1 9 
2 -2 -1 10 
A few more lines later is where it messes up...
2 1 1 12 
2 1 1 13 
2 1 2 10 
2 1 2 6 
2 1 2 7 
2 1 3 7 
....Few hundred more combinations later...
9 -1 -23 -46 
9 -1 -23 -45 
9 -1 -23 -44 
9 -1 -23 -43 
....And now I'm sad :(

It seems to me there's something wrong with what happens when it reaches the end of the "loop" (when start == nums.length) and it subtracts when it's not supposed to. However, I don't have the debugging know-how to figure out whats wrong.

(I'll give the entire code if any of you want)

Try printing out the values of the intermediate values and/or conditionals each time, so you can see why the program is making the unexpected decision. That should show you the bug in your logic. Then all you need to do is figure out what it should be doing instead at that point. — keshlam
– keshlam, Commented Feb 6, 2014 at 5:03

Dabo · Accepted Answer · 2014-02-07 14:27:20Z

1

I hope it is already not relevant, and you solved it by your self, but if not here what i found wrong with your function. As i understand, you only need to check all posible combinations within given range, if you can reach your target number or not. If so you don't really have to return anything from your generateProblems (you can, but the way you did it just add complexity), you only need to check all your combinations. This is how you can do it :

public void generateProblems(Integer[] nums, int start) 
{

    if (start != nums.length) 
    {
        for (int i = -range; i < range; i++) 
        {
            nums[start] = nums[start] + i;

            action(nums);
            generateProblems(nums, start + 1);         

            nums[start] = nums[start] - i;
        }
    }
}

Inside the action(nums); goes your logic

answered Feb 7, 2014 at 14:27

Dabo

2,3832 gold badges21 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mike Over a year ago

Thank you so much! This works like a charm for checking all the possibilities. However, I'm now running into a really weird issue with my List of solutions. Despite accurately determining the correct values, when I add it to my list, it will only list the original num. For example, the seed {5,4,3,8} will only print out {5,4,3,8} as a solution even though when I printed out the String it adds to the list, it prints out the correct numbers!

Collectives™ on Stack Overflow

Implementing and fixing a recursion method in Java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related