4
\$\begingroup\$

I am thinking about the following problem:

Consider a 3-numbers lock, i.e. a lock which has three little number wheels that opens whenever the sum of these three numbers equals 75. I know, this doesn't make sense for a lock, but just imagine this. The number wheels have numbers 3, 15, 17, 35, 40, 25, 5, 13. I am allowed to use numbers multiple times, i.e. in order to reach 75, I could use the combination 25, 25, 25.

I want to come up with all possible combinations to solve this puzzle. I have a solution and it works fine for just 3 different number wheels. But since I am using 3 for-loops for this, I know I cannot extend this code to work for, say a 100 number-wheels lock. I don't even know if this was possible (maybe recursively, but I always have troubles understanding recursion). Anyways, I really want to make this code look a little nicer. It is okay for me to leave the number of iterations the same, but I really want to get rid of the 3 for-loops, because I kind of want to extend this code to be a 10-numbers lock and in that case I would have 10 for-loops which looks ridiculous. There should be a way to leave out the for loops, I think

So, enough said. Here is my solution:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestClass {

    public static void main(String[] args) {
        
        List<List<Integer>> solutions = new ArrayList<>();
        List<Integer> combinations = new ArrayList<Integer>();
        
        List<Integer> numbers = new ArrayList<Integer>();
        numbers.add(3);
        numbers.add(15);
        numbers.add(17);
        numbers.add(35);
        numbers.add(40);
        numbers.add(25);
        numbers.add(5);
        numbers.add(13);
        
        int target = 75;
        
        int var1 = 3;
        int var2 = 3;
        int var3 = 3;
        
        for (int i = 0; i < numbers.size(); i++) {
            var1 = numbers.get(i);
            for (int j = 0; j < numbers.size(); j++) {
                var2 = numbers.get(j);
                for (int k = 0; k < numbers.size(); k++) {
                    var3 = numbers.get(k);
                    
                    int sum = var1 + var2 + var3;
                    if (sum == target) {
                        combinations.add(var1);
                        combinations.add(var2);
                        combinations.add(var3);

                        Collections.sort(combinations);
                        if (!solutions.contains(combinations)) {
                            solutions.add(combinations);
                        }
                        combinations = new ArrayList<>();
                    }
                }
            }
        }
    
        for (List<Integer> solution: solutions) {
            System.out.println(solution);
        }
        
    }
}

Any ideas, please share them with me :-)

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Vogel612
    May 7 at 12:06
  • \$\begingroup\$ oh, ok. I didn't know that. \$\endgroup\$
    – Luk
    May 7 at 12:59
1
\$\begingroup\$

you need the function

public static List<Integer> get_next_highest(List<Integer> combinations, List<Integer> numbers) {
    for(int i=0; i < combinations.size(); i++) {
        if(combinations[i]<numbers.size()-1) {
            combinations[i]++;
            return combinations;
        }
        else combinations[i] = 0;   
    }
    return null;
}

here, to simplify I've made combinations have indices (otherwise can't just do combinations[i]++, would need to find the next highest number in numbers)...

for eg. if numbers=[25 30 60 80] and combinations=[0 0 2 1]

this corresponds to the wheel positions [25 25 60 30]

if you pass the value of combinations [3 3 3 3] the function will return a null so make sure to do a check and stop when it does.

This will loop you through all possible combinations if you start at [0 0 0 0]

Specifically in the order [0 0 0 0] [1 0 0 0 ] [2 0 0 0] [3 0 0 0] [0 1 0 0] [1 1 0 0] ... [3 3 3 3]

should be fairly easy to sum up numbers[combinations[i]]

since you specified no for loops here's the recursive version

public static List<Integer> get_next_highest(List<Integer> combinations, List<Integer> numbers, int i=1) {
    if(i==combinations.size()) return null;
    if(combinations[i]<numbers.size()) {
            combinations[i]++;
            return combinations;
    }
    else {
        combinations[i] = 0;
        return get_next_highest(combinations, numbers, i+1);
    }
}

it does the same thing

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestClass {

    public static void main(String[] args) {
        
        List<List<Integer>> solutions = new ArrayList<>();
        List<Integer> combinations = new ArrayList<Integer>();
        
        List<Integer> numbers = new ArrayList<Integer>();
        numbers.add(3);
        numbers.add(15);
        numbers.add(17);
        numbers.add(35);
        numbers.add(40);
        numbers.add(25);
        numbers.add(5);
        numbers.add(13);
        
        int target = 75;
        int num_wheels = 3;
        
        for (int i = 0; i < num_wheels; i++) combinations.add(0);
        
        for (; combinations != null; combinations=get_next_highest(combinations, numbers)) {
            int sum = 0;
            for(Integer x : combinations) sum += numbers[x];
            if (sum == target) {
                 temp = new ArrayList<>();
                 for(Integer x : combinations) temp.add(numbers[x]);
                 Collections.sort(temp);
                 if (!solutions.contains(temp)) solutions.add(temp);
             }
        }
    
        for (List<Integer> solution: solutions) {
            System.out.println(solution);
        }
        
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Hi, thx a lot for your answer! Unfortunately, I don't really understand how to apply this function to my problem. Could you try and integrate it into my example? ... also: I am thinking there might be a neat solution that makes use of streams. I have updated my question a little bit with these thoughts \$\endgroup\$
    – Luk
    May 7 at 10:15
  • \$\begingroup\$ you can replace your triple loop with this function, loop until the get_next_highest returns a null, otherwise it doesn't deviate from the original post much \$\endgroup\$
    – user993732
    May 7 at 13:34
  • \$\begingroup\$ oh, and you also have to do sum of numbers[combinations[i]] instead of sum of combinations[i] \$\endgroup\$
    – user993732
    May 7 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.