Created
July 17, 2019 23:26
-
-
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).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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