Skip to content

Instantly share code, notes, and snippets.

@marksto
Created July 17, 2019 23:26
Show Gist options
  • Save marksto/cd087e00277656d24d134254e955e4cb to your computer and use it in GitHub Desktop.
Save marksto/cd087e00277656d24d134254e955e4cb to your computer and use it in GitHub Desktop.
The efficient recursive solution extracted from the BrickPileProblem.java (https://gist.github.com/marksto/ec0fb1d727f31b7b6db7cf7fed97f56e).
private static class RecursiveBrickPileSolver extends BrickPileSolver {
// NOTE: The 'ConcurrentHashMap' implementation should be used instead
// in case this object is to be shared between multiple threads.
final Map<Integer, double[]> cache = new HashMap<>();
public RecursiveBrickPileSolver(double brickMass) {
super(brickMass);
}
private double m(int row, int pos) {
if (pos < 0 || pos > row) {
return 0d;
}
return m;
}
private double W_m(int row, int pos) {
return 0.5*(W(row, pos) + m(row, pos));
}
private double W_impl(int row, int pos) {
if (pos < 0 || pos > row) {
return 0d;
}
double[] cachedRow = cache.computeIfAbsent(
row,
key -> new double[row + 1]
);
double result = cachedRow[pos];
if (result == 0d) {
result = W_m(row, pos);
cachedRow[pos] = result;
}
return result;
}
@Override
public double W(int row, int pos) {
return W_impl(row-1, pos-1) + W_impl(row-1, pos);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment