gudujarlson
BAN USERThis problem can be simplified by considering each coil to be a sequence of moves where each move is a pair of direction (up, down, left, right) and distance (1,2,3,...). For n=1 the sequences for each coil are:
U2 R2 D3
D2 L2 U3
For n=2 they are:
U2 R2 D4 L4 U6 R6
D2 L2 U4 R4 D6 L6
We observe a simple pattern. The direction follows the repeating sequence U, R, D, L for coil #1 and D, L, U, R for coil #2. The distance follows the sequence 2,2,4,4,6,6,...,2i,2i (except the last 2 values are 2i-1 when n is odd). We can use this simple pattern to our advantage. Code follows:
public class YahooCoils {
public static void main(String[] args) {
dumpcoils(1);
dumpcoils(2);
dumpcoils(3);
dumpcoils(4);
}
static void dumpcoils(int n) {
int a[][] = new int[4*n][4*n];
initializeMatrix(a, n);
dumpcoil(2*n, 2*n - 1, 0, a);
dumpcoil(2*n - 1, 2*n, 2, a);
}
static void initializeMatrix(int a[][], int n) {
int k = 1;
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < a[0].length; ++j) {
a[i][j] = k++;
if (n <= 2) {
System.out.print(String.format("%02d", a[i][j]) + " ");
}
else {
System.out.print(String.format("%03d", a[i][j]) + " ");
}
}
System.out.print("\n");
}
}
static void dumpcoil(int i, int j, int step, int a[][]) {
int distance = 2;
int k = 0;
while (i < a.length && j < a.length && i >= 0 && j >= 0) {
System.out.print(a[i][j] + " ");
switch (step % 4) {
case 0:
--i;
break;
case 1:
++j;
break;
case 2:
++i;
break;
case 3:
--j;
break;
}
k++;
if (k == distance) {
k = 0;
++step;
if (step % 2 == 0) {
distance += 2;
}
}
}
System.out.print("\n");
}
}
I'm no computer scientist, but I don't think this problem can be considered to be the same as the subset sum or knapsack problems, because the result set is not a subset of the input set. In any case, it is actually quite simple to solve using recursion with a running time approximately equal to the number of valid coin combinations (292) by using 2 optimizations:
1) sort the coins in descending order
2) when processing the last coin in the combo (i.e. deepest recursion level), realize that there is only 0 or 1 valid combo left.
For arbitrary sets of coins and sum (e.g. {3,7,11,13} and 103), the running time can be worse and some memoization of hasValidCombo(offset,sum) might be able to help. This requires more thought.
Code:
import java.util.ArrayList;
import java.util.Arrays;
public class YahooCoinCombos {
public static void main(String[] args) {
int coins[] = new int[] {1, 5, 10, 25, 50};
//int coins[] = new int[] {3, 7, 11, 13, 17};
dump(coins, findCombos(coins, 100));
}
static void dump(int coins[], ArrayList<int[]> comboList) {
System.out.println("Found " + comboList.size() + " combinations");
for (int[] combo : comboList) {
int sum = 0;
for (int i = 0; i < combo.length; ++i) {
if (i != 0) {
System.out.print(" + ");
}
System.out.print(combo[i] + "*" + coins[i]);
sum += combo[i] * coins[i];
}
System.out.print(" = " + sum + "\n");
}
}
static ArrayList<int[]> findCombos(int coins[], int sum) {
Arrays.sort(coins);
reverse(coins);
ArrayList<int[]> result = new ArrayList<int[]>();
int combo[] = new int[coins.length];
int iterations = findCombos(result, coins, combo, 0, sum);
System.out.println("iterations=" + iterations);
return result;
}
static void reverse(int a[]) {
int mid = a.length/2;
for (int i = 0; i < mid; ++i) {
swap(a, i, a.length - i - 1);
}
}
static void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
static int findCombos(ArrayList<int[]> result, int coins[], int combo[], int offset, int sum) {
int iterations = 1;
if (sum == 0) {
int validCombo[] = new int[offset];
System.arraycopy(combo, 0, validCombo, 0, offset);
result.add(validCombo);
return iterations;
}
if (offset < coins.length - 1) {
for(int i = 0; ; ++i) {
if (sum < 0) {
return iterations;
}
combo[offset] = i;
iterations += findCombos(result, coins, combo, offset + 1, sum);
sum -= coins[offset];
}
}
else if (sum % coins[offset] == 0) {
combo[offset] = sum / coins[offset];
return findCombos(result, coins, combo, offset + 1, 0);
}
else {
return iterations;
}
}
}
This can be optimized 2 ways:
1) Sort the coins in descending order
2) When processing the last and smallest coin (the penny), realize that the only valid multiplier is n / coin.
I will post code below.
Note that the algorithm can be optimized for the average case by storing the candidate subsequences in a tree sorted by value (e.g. TreeMap) and then ending the linear search when candidate.value > v, but it would still be O(n^2) in the worst case.
- gudujarlson April 08, 2013Given the input {5,4,6,3,7}, your solution returns the value 4, however the maximum sorted subsequence is {5,6,7} or {4,6,7}.
- gudujarlson April 08, 2013
The path with the maximum sum can to found in O(N*M) time using the following algorithm.
1) Create an auxiliary matrix B to store the maximum sum of a path from a starting node (0,0...N-1) to node x,y
2) Working from top to bottom, set the value of every other node in B to the maximum of value of its 1-3 parents ({x-1,y-1}, {x-1,y}, and {x-1,y+1}). This can be considered to be a breadth first traversal of a DAG and thus this algorithm resembles Dijkstra's shortest path algorithm.
3) Working from bottom to top, follow the path in B with the maximum value (greedy search).
Code follows. I have also included a brute force algorithm and use it to verify the correctness of the faster algorithm. The brute force algorithm could be easily modified to print all possible paths.
- gudujarlson May 01, 2013