phishman3579
BAN USERSince every List has two choices, it's essentially a binary decision. You can think of it as a 3 bit binary number.
e.g.
000
001
010
.....
101
110
111
If you can get the binary representation and convert it to each choice, you can come up with the answer.
For example,
if the first bit is zero then choose 'quick'
if the second bit is one then choose 'red'
if the third bit is zero then choose 'fox'
private static String binary(int numOfBits, int value) {
StringBuilder builder = new StringBuilder();
while (numOfBits>0) {
int a = value % 2;
if (a>0) builder.append("1");
else builder.append("0");
value /= 2;
numOfBits--;
}
return builder.toString();
}
private static List<String> solve(List<String[]> input) {
List<String> result = new LinkedList<String>();
int size = input.size();
int max = (int) ((Math.pow(2, size)) - 1);
List<String> binaryValues = new LinkedList<String>();
for (int i = 0; i<=max; i++) {
String binary = binary(size, i);
binaryValues.add(binary);
}
for (String s : binaryValues) {
StringBuilder builder = new StringBuilder();
for (int i=0; i<s.length(); i++) {
if (s.charAt(i)=='0')
builder.append(input.get(i)[0]);
else
builder.append(input.get(i)[1]);
builder.append(" ");
}
result.add(builder.toString());
}
return result;
}
Get all subsets of the input set.
Create a Map<Integer,Set<List>>, where the all Lists in the Set have the same sum (which is the key in the map).
Then iterate through each value of the Map,
If the length of the Set is equal to bin size and each element of the input set is contained in the Set of Lists then you have an answer.
private static String binary(int numOfBits, int value) {
StringBuilder builder = new StringBuilder();
while (numOfBits>0) {
int a = value % 2;
if (a>0) builder.append("1");
else builder.append("0");
value /= 2;
numOfBits--;
}
return builder.toString();
}
private static List<List<Integer>> subsets(int[] array) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
int size = array.length;
int max = (int) ((Math.pow(2, size)) - 1);
List<String> binaryValues = new LinkedList<String>();
for (int i = 1; i<=max; i++) {
String binary = binary(size, i);
binaryValues.add(binary);
}
for (String s : binaryValues) {
List<Integer> list = new LinkedList<Integer>();
for (int i=0; i<s.length(); i++) {
if (s.charAt(i)=='1')
list.add(array[i]);
}
result.add(list);
}
return result;
}
private static int sum(List<Integer> list) {
int result = 0;
for (int i : list) {
result += i;
}
return result;
}
private static int totalOfElements(Set<List<Integer>> list) {
int result = 0;
for (List<Integer> l : list) {
result += l.size();
}
return result;
}
private static List<Set<List<Integer>>> solve(int[] items, int bins) {
List<List<Integer>> subsets = subsets(items);
Map<Integer,Set<List<Integer>>> hash = new HashMap<Integer,Set<List<Integer>>>();
for (List<Integer> l : subsets) {
int sum = sum(l);
Set<List<Integer>> s = hash.get(sum);
if (s==null)
s = new HashSet<List<Integer>>();
s.add(l);
hash.put(sum, s);
}
List<Set<List<Integer>>> list = new LinkedList<Set<List<Integer>>>();
for (Set<List<Integer>> l : hash.values()) {
if (l.size()==bins && totalOfElements(l)==items.length)
list.add(l);
}
return list;
}
You can get all possible subsets of the input set.
The sum each value in each subset.
Add the subset to a Map<Integer,List<Set>>, where the key is the sum and the List contains the subset.
You can then iterate through the Map's values which is a List of Sets.
If the List of Sets size (e.g. List<Set>.size()) if equal to the 'bin' size and the List contains each element of the original Set then you have an answer.
private static String binary(int numOfBits, int value) {
StringBuilder builder = new StringBuilder();
while (numOfBits>0) {
int a = value % 2;
if (a>0) builder.append("1");
else builder.append("0");
value /= 2;
numOfBits--;
}
return builder.toString();
}
private static List<Set<Integer>> subsets(int[] array) {
List<Set<Integer>> result = new LinkedList<Set<Integer>>();
int size = array.length;
int max = (int) ((Math.pow(2, size)) - 1);
List<String> binaryValues = new LinkedList<String>();
for (int i = 1; i<=max; i++) {
String binary = binary(size, i);
binaryValues.add(binary);
}
for (String s : binaryValues) {
Set<Integer> set = new HashSet<Integer>();
for (int i=0; i<s.length(); i++) {
if (s.charAt(i)=='1')
set.add(array[i]);
}
result.add(set);
}
return result;
}
private static int sum(Set<Integer> set) {
int result = 0;
for (int i : set) {
result += i;
}
return result;
}
private static int totalOfElements(List<Set<Integer>> list) {
int result = 0;
for (Set<Integer> s : list) {
result += s.size();
}
return result;
}
private static List<List<Set<Integer>>> solve(int[] items, int bins) {
List<Set<Integer>> subsets = subsets(items);
Map<Integer,List<Set<Integer>>> hash = new HashMap<Integer,List<Set<Integer>>>();
for (Set<Integer> s : subsets) {
int sum = sum(s);
List<Set<Integer>> l = hash.get(sum);
if (l==null)
l = new LinkedList<Set<Integer>>();
l.add(s);
hash.put(sum, l);
}
List<List<Set<Integer>>> list = new LinkedList<List<Set<Integer>>>();
for (List<Set<Integer>> l : hash.values()) {
if (l.size()==bins && totalOfElements(l)==items.length)
list.add(l);
}
return list;
}
Using recursion, you can keep track of the previous direction and compare it to the next direction.
- phishman3579 February 15, 2015