Brick pile (pyramid) problem solvers.

BrickPileProblem.java

package marksto.algorithms;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.runner.options.TimeValue;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;

import static java.lang.System.arraycopy;

/**
 * Benchmark                                    Mode  Cnt  Score   Error  Units
 * BrickPileProblem.checkIterativeEffective     avgt   10  0,068 ± 0,002  ms/op
 * BrickPileProblem.checkIterativeNonEffective  avgt   10  0,106 ± 0,009  ms/op
 * BrickPileProblem.checkRecursiveEffective     avgt   10  0,928 ± 0,031  ms/op
 * BrickPileProblem.checkRecursiveNonEffective  avgt   10  3,456 ± 0,045  ms/op
 */
public class BrickPileProblem {

    public static final double DEFAULT_BRICK_MASS = 1;

    abstract static class BrickPileSolver {

        protected double m;

        public BrickPileSolver(double brickMass) {
            this.m = brickMass;
        }

        public double solve(int row, int pos) {
            assertThat(pos >= 0 && pos <= row);
            return W(row, pos);
        }

        protected abstract double W(int row, int pos);
    }

    // --- RECURSIVE SOLUTIONS -------------------------------------------------

    private static class MemoizingRecursiveBrickPileSolver extends BrickPileSolver {

        // NOTE: Thanks to the absence of Tuples in the Java Core...
        static class MapKey {
            int row;
            int pos;

            public MapKey(int row, int pos) {
                this.row = row;
                this.pos = pos;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                MapKey mapKey = (MapKey) o;
                return row == mapKey.row && pos == mapKey.pos;
            }

            @Override
            public int hashCode() {
                return Objects.hash(row, pos);
            }
        }

        /*
         * IMPORTANT NOTICE:
         * In Java 9+ this can't be implemented in a shorter way with 'computeIfAbsent()' because of the known issue. For details see:
         * https://stackoverflow.com/questions/54824656/since-java-9-hashmap-computeifabsent-throws-concurrentmodificationexception-on
         */
        private static <I, O> Function<I, O> memoize(Function<I, O> fn) {
            final Map<I, O> cache = new HashMap<>();
            return in -> {
                if (cache.get(in) != null) {
                    return cache.get(in);
                } else {
                    O result = fn.apply(in);
                    cache.put(in, result);
                    return result;
                }
            };
        }

        private final Function<MapKey, Double> memoized = memoize(this::W_m);

        public MemoizingRecursiveBrickPileSolver(double brickMass) {
            super(brickMass);
        }

        private double W_m(MapKey key) {
            return (W(key.row, key.pos) + m) / 2;
        }

        private double W_impl(int row, int pos) {
            if (pos < 0 || pos > row) {
                return 0d;
            }
            return memoized.apply(new MapKey(row, pos));
        }

        @Override
        protected double W(int row, int pos) {
            return W_impl(row - 1, pos - 1) + W_impl(row - 1, pos);
        }
    }

    private static class EffectiveRecursiveBrickPileSolver 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 EffectiveRecursiveBrickPileSolver(double brickMass) {
            super(brickMass);
        }

        private double W_m(int row, int pos) {
            return (W(row, pos) + m) / 2;
        }

        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
        protected double W(int row, int pos) {
            return W_impl(row - 1, pos - 1) + W_impl(row - 1, pos);
        }
    }

    // --- ITERATIVE SOLUTION --------------------------------------------------

    private static class IterativeBrickPileSolver extends BrickPileSolver {

        public IterativeBrickPileSolver(double brickMass) {
            super(brickMass);
        }

        private double W_top(double onTop) {
            return (onTop + m) / 2;
        }

        private double W_top(double onTopL, double onTopR) {
            return W_top(onTopL) + W_top(onTopR);
        }

        @Override
        protected double W(final int row, final int pos) {
            // NOTE: This is the same as 'Math.min(pos, row - pos) + 1',
            //       but is better optimized by JIT compiler at runtime.
            int maxTopRowSize = (int) (0.5*row - Math.abs(0.5*row - pos) + 1);

            double[] topRowWs = new double[maxTopRowSize];
            double[] tmpRowWs = new double[topRowWs.length];

            int startPos = 0;
            int readTops = 0;
            int decStart = Math.max(pos, row - pos);

            for (int i = 0; i <= row; i++) {
                if (i < maxTopRowSize) {
                    readTops += 1;
                } else if (i > decStart) {
                    startPos += 1;
                    readTops -= 1;
                }

                for (int k = startPos; k < startPos + readTops; k++) {
                    int idx = k - startPos;
                    if (i == 0) {
                        tmpRowWs[idx] = 0d;
                    } else if (k == 0) {
                        tmpRowWs[idx] = W_top(topRowWs[idx]);
                    } else if (k == i) {
                        tmpRowWs[idx] = W_top(topRowWs[idx - 1]);
                    } else {
                        int dec = i > decStart ? 0 : -1;
                        tmpRowWs[idx] = W_top(topRowWs[idx + dec], topRowWs[idx + dec + 1]);
                    }
                }
                arraycopy(tmpRowWs, 0, topRowWs, 0, tmpRowWs.length);
            }

            return topRowWs[0];
        }
    }

    private static class EffectiveIterativeBrickPileSolver extends BrickPileSolver {

        public EffectiveIterativeBrickPileSolver(double brickMass) {
            super(brickMass);
        }

        private double W_top(double onTop) {
            return (onTop + m) / 2;
        }

        private double W_top(double onTopL, double onTopR) {
            return W_top(onTopL) + W_top(onTopR);
        }

        @Override
        protected double W(int row, int pos) {
            // NOTE: Leverages the fact of horizontal symmetry.
            //       Shaves off lots of extra steps and checks.
            int adjustedPos = Math.min(pos, row - pos);

            double[] blocks = new double[adjustedPos + 1];
            blocks[0] = 0;

            for (int i = 1; i <= row; i++) {
                int rangeStart = Math.max(0, (adjustedPos - 1) - (row - i));
                int rangeEnd = adjustedPos;

                double prev = blocks[rangeStart];

                for (int k = rangeStart; k <= rangeEnd; k++) {
                    if (k == 0 || k == i) {
                        blocks[k] = W_top(prev);
                    } else {
                        double curr = blocks[k];
                        blocks[k] = W_top(prev, curr);
                        prev = curr;
                    }
                }
            }

            return blocks[adjustedPos];
        }
    }

    // -------------------------------------------------------------------------

    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
                .include(BrickPileProblem.class.getSimpleName())
                .mode(Mode.AverageTime)
                .forks(1)
                .warmupIterations(5)
                .warmupTime(TimeValue.seconds(1))
                .measurementIterations(10)
                .measurementTime(TimeValue.seconds(1))
                .timeUnit(TimeUnit.MILLISECONDS)
                .build();

        new Runner(opt).run();
    }

    // -------------------------------------------------------------------------
    // NOTE: Naive recursion will not do in reasonable time,
    //       so the memoization technique is leveraged here.
    //       To tune the thread stack size, use '-Xss1024k'.

    @Benchmark
    public static void checkRecursiveNonEffective() {
        runChecks(new MemoizingRecursiveBrickPileSolver(DEFAULT_BRICK_MASS));
    }

    @Benchmark
    public static void checkRecursiveEffective() {
        runChecks(new EffectiveRecursiveBrickPileSolver(DEFAULT_BRICK_MASS));
    }

    // -------------------------------------------------------------------------
    // NOTE: The most fast & cognitively complex algorithms.
    //       It takes some real time to grok & support them.

    @Benchmark
    public static void checkIterativeNonEffective() {
        runChecks(new IterativeBrickPileSolver(DEFAULT_BRICK_MASS));
    }

    @Benchmark
    public static void checkIterativeEffective() {
        runChecks(new EffectiveIterativeBrickPileSolver(DEFAULT_BRICK_MASS));
    }

    // -------------------------------------------------------------------------

    private static void runChecks(BrickPileSolver pile) {
        assertThat(pile.solve(0, 0) == 0d);

        assertThat(pile.solve(1, 0) == 0.5d);
        assertThat(pile.solve(1, 1) == 0.5d);

        assertThat(pile.solve(2, 0) == 0.75d);
        assertThat(pile.solve(2, 1) == 1.5d);
        assertThat(pile.solve(2, 2) == 0.75d);

        assertThat(pile.solve(3, 0) == 0.875d);
        assertThat(pile.solve(3, 1) == 2.125d);
        assertThat(pile.solve(3, 2) == 2.125d);
        assertThat(pile.solve(3, 3) == 0.875d);

        double expRes322 = 306.48749781747574d;
        assertThat(pile.solve(322, 156) == expRes322);
        assertThat(pile.solve(322, 322 - 156) == expRes322);
    }

    private static void assertThat(boolean expression) {
        if (!expression) {
            throw new AssertionError();
        }
    }

}

double W(int row, int pos) {
    int adjustedPos = Integer.min(pos, row - pos);
    double[] blocks = new double[adjustedPos + 1];
    for (int i = 1; i <= row; i++) {
        int rangeStart = Integer.max(0, (adjustedPos - 1) - (row - i));
        double prev = blocks[rangeStart];
        for (int j = rangeStart; j <= adjustedPos; j++) {
            if (j != 0 && j != i) {
                double curr = blocks[j];
                blocks[j] = ((prev + 1) / 2) + ((curr + 1) / 2);
                prev = curr;
            } else blocks[j] = (prev + 1) / 2;
        }
    }
    return blocks[adjustedPos];
}

minified/obfuscated version (16 lines, as you requested)