I am trying, to sum up score for a little dice game I made. The dice has the following values: 1-6, the player can select target, LOW = n < 4, 1,2,3. The rest of the targets, 4, 5, 6, 7, 8, 9, 10, 11 and 12.
When a throw is done, sum up the total sum of the dices, based on target value. What this means, is, if LOW is select, then everything below 4, is summed up. Otherwise, the process, must sum each dice till it reaches the target sum, and continue.
If, a throw is done, and I selected 6 as target, and get the following set: {1, 1, 4, 2, 5, 6}. We have a 6, 5 1=6, and 4 2=6, we are left with 1 which is not counted.
Constraints:
- 1-6 dice values.
- Everything (Target) below 4, is summed up.
- Everything (Target) selecting between 4, 5, 6, 7, 8, 9, 10, 11, & 12, is processed differently.
- 6 dices, can produces any number between
1-6. This means,[6,6,6,6,6,6], or[1,1,3,5,4,2], or some other set.
The only thing important, is the sum that is calculated and nothing else, as long as it matches the input of dices.
For example:
- If the
targetis12and a list of numbers is[6, 6, 6, 6, 6, 6]then return value should be36. - If we receive a list of numbers
[1, 3, 4, 5, 6, 6]and atargetis should be12(5 1 6=12and also5 4 3=12, however, numbers can only be used once and not reused, therefore only one of the combinations can contribute the result).
Below is a method, which gives the occurrences of a dice.
public static TreeMap<Integer, Integer> countOccurrences(List<Integer> numbers){
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int i = 0;
for(int n: numbers) {
if(map.containsKey(n)) {
i = map.get(n);
map.put(n, i);
}
else
map.put(n, 1);
}
return map;
}
Results:
Occurrences: {1=2, 2=1, 4=1, 5=1, 6=1}
Sample code
public static void main(String[] args) {
System.out.println(sum(combinationSum(List.of(1, 2, 4, 6, 6, 6), 12)));
System.out.println(combinationSum(List.of(1, 3, 3, 6, 5, 6), 12));
System.out.println(combinationSum(List.of(1, 2, 1, 4, 5, 6), 6));
}
public static int sum(List<List<Integer>> numbers)
{
int sum = 0;
int n = 0;
while(n < numbers.size()){
sum = numbers.get(n).stream().mapToInt(Integer::intValue).sum();
n;
}
return sum;
}
public static List<List<Integer>> combinationSum(List<Integer> candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> ds = new ArrayList<Integer>();
findCombinations(res, ds, target, candidates, 0);
return res;
}
private static void findCombinations(List<List<Integer>> res, List<Integer> ds, int target, List<Integer> arr, int index ){
if(target == 0){res.add(new ArrayList<>(ds)); return;}
for(int i= index ; i<arr.size(); i ){
if(i>index && arr.get(i) == arr.get(i-1)) continue;
if(arr.get(i) > target) break;
ds.add(arr.get(i));
findCombinations( res, ds, target-arr.get(i) , arr, i 1);
ds.remove(ds.size()-1 );
}
}
Produces:
24
[[1, 6, 5], [1, 5, 6], [3, 3, 6], [3, 3, 6], [6, 6]]
[[1, 1, 4], [1, 5], [2, 4], [1, 5], [6]]
Live running: https://www.jdoodle.com/ia/sHY
CodePudding user response：
Update
In order to find the maximum possible score of the list, we maximize the number of non-overlapping combinations that we can construct from it.
For we need to take the following steps:
Find all the possible combinations which produce the
targetsum. We can not reject any combinations on the fly, because we can't know in advance which of them can be used in the optimal solution. For instance, iftargetis6and a list of number is[3,3,2,2,1,1], there will be the following combinations:[3,3],[2,2,1,1]and[3,2,1]appear two times. If we pick[3,3], which is the shortest combination, we will not be able to construct any combinations and resulting score will be wrong (6). Instead, we need to choose two combinations[3,2,1]which well give the result12. That proves that we can't rely on the combination size, we need to explore all the combinations and then choose the optimal set of combinations.Generate all possible groups of combinations that fit to the given list of numbers and find a group having the maximum number of combinations in it.
In the code below both steps are implemented recursively.
Expalanation:
The enty point, this method that kicks in the process.
public static int sumRecursively(List<Integer> numbers, int target) {
Deque<List<Integer>> combinations = new ArrayDeque<>();
generateCombinations(numbers, combinations, new ArrayList<>(), target);
return processCombinations(combinations, numbers, target);
}
Step 1. Generating all the combinations.
Recursive method responsible for generating the set of combinations (implemented as void to avoid wrapping a combination with an additional collection and then throwing this wrapper away):
private static void generateCombinations(List<Integer> numbers,
Queue<List<Integer>> combinations,
List<Integer> combination,
int currentSum) {
if (currentSum == 0) { // base case - a combination has been found
combinations.add(combination);
return;
}
// recursive case
for (Integer next : numbers) { // loop is need only to discard the elements that exceed the currentSum - pay attention to the condition below and break clause at the end of the loop (we will bread out of the loop after the first encountered element that fits to the current sum)
if (next > currentSum) continue;
List<Integer> newNumbers = new ArrayList<>(numbers);
newNumbers.remove(next);
// there two opportunities for each number: use it, or ignore it
// add next number
List<Integer> newCombination = new ArrayList<>(combination);
newCombination.add(next);
getCombinations(newNumbers, combinations, newCombination, currentSum - next);
// ignore next number
getCombinations(newNumbers, combinations, new ArrayList<>(combination), currentSum);
break;
}
}
Step 2. Generating the groups of combinations.
Method below is responsible choosing the group that fits to the given list (i.e. we can construct all the combinations in the group from list elements) and has the maximum number of combinations in it.
All the functionality related to the procissing the the group of combinations (which represents a List<List<Integer>>) is incapsulated in a class CombinationGroup to make the code cleaner.
public static int processCombinations(Deque<List<Integer>> combinations,
List<Integer> numbers,
int target) {
List<CombinationGroup> combinationGroups = new ArrayList<>();
generateGroups(combinationGroups, combinations, new CombinationGroup(target));
return combinationGroups.stream()
.filter(group -> group.canConstruct(numbers))
.mapToInt(group -> group.getCombCount() * target)
.max()
.orElse(0);
}
The following method is responsible for creating the all possible groups of previosly descovered combinations. There's also a small optimization: total number of elements in each group should not exceed the number of elements in the source list:
public static void generateGroups(List<CombinationGroup> groups,
Deque<List<Integer>> combinations,
CombinationGroup group) {
if (combinations.isEmpty()) {
groups.add(group);
return;
}
Deque<List<Integer>> combinationsCopy = new ArrayDeque<>(combinations);
List<Integer> comb = null;
while (!combinationsCopy.isEmpty() && (comb == null || !group.canAdd(comb))) {
comb = combinationsCopy.removeLast();
}
// adding the combination
if (comb != null) {
CombinationGroup groupWithNewComb = group.copy();
groupWithNewComb.addCombination(comb);
generateGroups(groups, combinationsCopy, groupWithNewComb);
}
// ignoring the combination
generateGroups(groups, combinationsCopy, group);
}
Class CombinationGroup used in the methods above:
public class CombinationGroup {
private List<List<Integer>> combinations = new ArrayList<>();
private int combCount; // number of combinations
private int size; // total number of elements in the list of combinations
private int sizeLimit;
public CombinationGroup(int sizeLimit) {
this.sizeLimit = sizeLimit;
}
public boolean canAdd(List<Integer> combination) {
return size combination.size() <= sizeLimit;
}
public boolean addCombination(List<Integer> combination) {
if (!canAdd(combination)) return false;
combinations.add(combination);
size = combination.size();
combCount ;
return true;
}
public CombinationGroup copy() {
CombinationGroup copy = new CombinationGroup(this.sizeLimit);
for (List<Integer> comb : combinations) {
copy.addCombination(comb);
}
return copy;
}
public boolean canConstruct(List<Integer> numbers) {
if (numbers.size() < size) return false;
Map<Integer, Long> frequencyByValueNumb = getFrequencies(numbers.stream());
Map<Integer, Long> frequencyByValueComb = getFrequencies();
return frequencyByValueNumb.keySet().stream() // each element that prent this CombinationGroup appears in the given list of numbers appears at least the same number of times - that means we construct all these combinations from the given list
.allMatch(key -> frequencyByValueNumb.get(key) >= frequencyByValueComb.getOrDefault(key, 0L));
}
public Map<Integer, Long> getFrequencies() {
return getFrequencies(combinations.stream().flatMap(List::stream));
}
public Map<Integer, Long> getFrequencies(Stream<Integer> stream) {
return stream.collect(Collectors.groupingBy(
Function.identity(),
Collectors.counting()
));
}
public int getCombCount() {
return combCount;
}
@Override
public String toString() {
return "CombinationGroup{"
"combinations=" combinations
'}';
}
}
main()
public static void main(String[] args) {
System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
System.out.println(sumRecursively(List.of(1, 3, 3, 6, 5), 12));
System.out.println(sumRecursively(List.of(1, 2, 1, 4, 5, 6), 6));
}
Output:
24
12
18
Simplified algorithm
(doesn't maximizes the number of combinations)
In order to ensure that all the elements in each combination are unique, we to track indices that have been already used. I.e. each time we find a combination which sums up to the target number, we should prohibit the usage of elements that have been used in this combination, but not earlier (because there can be many combinations which are not able to produce the target, and therefore any element should eligible to be used until we didn't construct a complete combination that gives the target using this element).
To track the elements that are taken, we need an object that would be visible in every recursive branch. And we are already passing a list of numbers while making every recursive call, what if we would modify it each time we found a combination that produces the target number by removing the elements that have been use in this combination? If we took this road after the first combination, thing would become complicated because we will not be able to rely on the indices (because they can change in an unpredictable way) while constructing a single combination - it's crucial to ensure that each element that belongs to a particular combination is used only once withing a combination. Since values of elements might be identical, we should use the iteration order to construct each combination properly, but each removal of elements would create a mess. So, is there a better way?
We can maintain an array of boolean values, each element is this array would indicate whether a number at a particular index already belongs to a combination that gives the target or not.
Instead of clattering the recursive method with the code that manipulates with this boolean array, I've encapsulated it within a class with simple and self-explanatory methods, and sumRecursively() makes use of an instance of this class.
public class CombinationTracker {
private boolean[] isUsed;
public CombinationTracker(int size) {
this.isUsed = new boolean[size];
}
public boolean indexIsUsed(int ind) {
return isUsed[ind];
}
public boolean allNotUsed(List<Integer> indices) {
// return indices.stream().noneMatch(i -> isUsed[i]); // this line does the same as the loop below
boolean result = true;
for (int idx: indices) {
if (isUsed[idx]) {
result = false;
break;
}
}
return result;
}
public void setIsUsed(List<Integer> indices) {
for (int ind: indices)
setIsUsed(ind);
}
public void setIsUsed(int ind) {
isUsed[ind] = true;
}
}
Using this approach, we are able to construct combinations from numbers that are not used yet, and iterate over the list of numbers starting from a particular position by passing the index while making a recursive call. We can be sure that any of the elements that reside prier to the current position would not be added to the current combination.
Now, a quick recap on recursion.
Every recursive implementation consists of two parts:
Base case - that represents an edge-case (or a set of edge-cases) for which the outcome is known in advance. For this problem, there are two edge-cases:
we've managed to find a combination that gives the target number, i.e.
currentSum == target, and the result would be equal totarget;the end of the list is reached (and the combination doesn't result to the target), the result would be
0(this edge-case resolves automatically by termination condition of theforloop in the recursive case, and therefore no need to treat it separately).
Recursive case - a part of a solution where recursive calls are made and where the main logic resides. In the recursive case we're iterating over the list of numbers and at each iteration step (if the index is not yet used) we are making one or two recursive calls depending on a value of the current element (depending whether we exceed the target or not). In the general, we have two opportunities: either take the current element, or ignore it. The results of these recursive calls would be added together and produce the return value of the recursive case.
Since we need a couple of additional parameters, it's a good practice to create an auxiliary overloaded method (that will be used in the client code) which expects only a list of numbers and a target value and delegates the actual work to the recursive method.
That's how it might look like.
public static int sumRecursively(List<Integer> numbers, int target) {
return sumRecursively(new ArrayList<>(numbers),
new ArrayList<>(),
new CombinationTracker(numbers.size()),
0, 0, target);
}
The actual recursive method:
private static int sumRecursively(List<Integer> numbers,
List<Integer> combination,
CombinationTracker tracker,
int currentIndex,
int currentSum, int target) {
if (currentSum == target && tracker.allNotUsed(combination)) { // base case - a combination has been found
tracker.setIsUsed(combination);
return target;
}
// recursive case
int result = 0;
for (int i = currentIndex; i < numbers.size(); i ) {
int next = numbers.get(i);
if (tracker.indexIsUsed(i)) continue;
if (currentSum next > target) continue;
// there are two opportunities for each number: either use next number, or ignore it
// add next number
if (next currentSum <= target) {
List<Integer> newCombination = new ArrayList<>(combination);
newCombination.add(i);
result = sumRecursively(numbers, newCombination, tracker, i 1, currentSum next, target);
}
// ignore next number
result = sumRecursively(numbers, new ArrayList<>(combination), tracker, i 1, currentSum, target);
}
return result;
}
main()
public static void main(String[] args) {
System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
System.out.println(sumRecursively(List.of(6, 6, 6, 6, 6, 6), 12));
}
Output:
12
36
CodePudding user response：
UPD.
Got a comment that code "sucks" due to performance issues...
First of all, I do believe you have missed a point the SO community is not a kind of service which solves code interview puzzles, generally speaking, if you came here with a puzzle you already failed, so, such comments are unacceptable.
At second, yes, the code suffers from performance issues just because it is a naive bruteforce solution - I had spent on it about 15 minutes (for example, figuring out all possible combinations with target sum has O(2^N) complexity, if it does not match performance expectations that means any code based on such idea has poor performance). BTW, if you had expectations about the performance you was need to:
- provide correct input constraints (saying
there is 6 numbersis not correct) - provide good testcases instead of saying
code does not work- that allows us to eliminate bad ideas about algorithm.
Some idea:
it seems that we do not need to compute all possible combinations with target sum, because singletons are always preferable over N-lets, pairs are either the same or do not influence on the result or interchangeable with N-lets (e.g. in case of [2,2,8,10,10] we would prefer to eliminate pairs first), but whether it is true for higher N's completely unclear - it is better to have some testcases.
Not sure I properly understand the problem, but I believe the solution is following:
public class TargetNumber {
public static void main(String[] args) {
System.out.println(score(new int[]{1, 2, 1, 4, 5, 6}, 6));
}
public static int score(int[] candidates, int target) {
List<List<Integer>> combinations = getUniqueCombinations(candidates, target);
Map<Integer, Integer> freqs = new HashMap<>();
for (int n : candidates) {
freqs.merge(n, 1, Integer::sum);
}
return score(0, combinations, freqs, target);
}
public static int score(int offset, List<List<Integer>> combinations, Map<Integer, Integer> freqs, int target) {
if (offset == combinations.size()) {
return 0;
}
int result = 0;
List<Integer> comb = combinations.get(offset);
Map<Integer, Integer> nfreq = reduce(freqs, comb);
if (nfreq != null) {
result = Math.max(result, target score(offset, combinations, nfreq, target));
}
result = Math.max(result, score(offset 1, combinations, freqs, target));
return result;
}
public static Map<Integer, Integer> reduce(Map<Integer, Integer> freqs, List<Integer> comb) {
Map<Integer, Integer> result = new HashMap<>(freqs);
for (int n : comb) {
if (result.merge(n, -1, Integer::sum) < 0) {
return null;
}
}
return result;
}
public static List<List<Integer>> getUniqueCombinations(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
getUniqueCombinations(candidates, target, 0, new ArrayList<>(), result);
return result;
}
public static void getUniqueCombinations(int[] candidates, int target, int index, List<Integer> solution, List<List<Integer>> result) {
for (int i = index, n = candidates.length; i < n; ) {
int num = candidates[i];
if (num > target) {
break;
}
solution.add(num);
if (num == target) {
result.add(new ArrayList<>(solution));
}
getUniqueCombinations(candidates, target - num, i 1, solution, result);
solution.remove(solution.size() - 1);
while (i < n && num == candidates[i]) {
i ;
}
}
}
}