Merge branch 'master' of tronto.net:h48

2 files changed, 97 insertions, 1 deletions

diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 17c594f..391c97b 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -277,6 +277,37 @@ gendata_h48k2(gendata_h48_arg_t *arg)
         static const uint8_t shortdepth = 8;
         static const uint64_t capacity = 10000019;
         static const uint64_t randomizer = 10000079;
+
+        /*
+         * A good base value for the k=2 tables have few positions with value
+         * 0, because those are treated as lower bound 0 and require a second
+         * lookup in another table, and at the same time not too many positions
+         * with value 3, because some of those are under-estimates.
+         *
+         * The following values for the base have been hand-picked. I first
+         * performed some statistics on the frequency of these values, but
+         * they turned out to be unreliable. I have not figured out why yet.
+         * In the end I resorted to generating the same table with multiple
+         * base value and see what was best.
+         *
+         * A curious case is h3, which has this distribution for base 8:
+         *   [0] = 6686828
+         *   [1] = 63867852
+         *   [2] = 392789689
+         *   [3] = 477195231
+         *
+         * and this for base 9:
+         *   [0] = 70554680
+         *   [1] = 392789689
+         *   [2] = 462294676
+         *   [3] = 14900555
+         *
+         * I ended up picking base 8 to have a much lower count of elements
+         * with value 0, at the cost of a less precise estimate for the higher
+         * values. But I am not 100% confident this is the optimal choice,
+         * so I'll leave it here for future considerations.
+         */
+         
         static const uint8_t base[] = {
                 [0]  = 8,
                 [1]  = 8,
diff --git a/tools/expected_distributions.h b/tools/expected_distributions.h
index 0f3fec3..202edf9 100644
--- a/tools/expected_distributions.h
+++ b/tools/expected_distributions.h
@@ -43,6 +43,71 @@ uint64_t expected_h48[12][9][21] = {
                         [3] = 41281787,
                 },
         },
+        [2] = {
+                [2] = {
+                        [0] = 6391286,
+                        [1] = 55494785,
+                        [2] = 252389935,
+                        [3] = 155993794,
+                },
+        },
+        [3] = {
+                [2] = {
+                        [0] = 6686828,
+                        [1] = 63867852,
+                        [2] = 392789689,
+                        [3] = 477195231,
+                },
+
+        },
+        [4] = {
+                [2] = {
+                        [0] = 77147213,
+                        [1] = 543379415,
+                        [2] = 1139570251,
+                        [3] = 120982321,
+                },
+        },
+        [5] = {
+                [2] = {
+                        [0] = 82471284,
+                        [1] = 687850732,
+                        [2] = 2345840746,
+                        [3] = 645995638,
+                },
+        },
+        [6] = {
+                [2] = {
+                        [0] = 85941099,
+                        [1] = 804752968,
+                        [2] = 4077248182,
+                        [3] = 2556374551,
+                },
+        },
+        [7] = {
+                [2] = {
+                        [0] = 88529761,
+                        [1] = 897323475,
+                        [2] = 6126260791,
+                        [3] = 7936519573,
+                },
+        },
+        [8] = {
+                /* Unknown */
+                [2] = {0},
+        },
+        [9] = {
+                /* Unknown */
+                [2] = {0},
+        },
+        [10] = {
+                /* Unknown */
+                [2] = {0},
+        },
+        [11] = {
+                /* Unknown */
+                [2] = {0},
+        },
 };
 
 static bool
@@ -82,7 +147,7 @@ unknown_h48(uint8_t h, uint8_t k)
         if (k == 4 && h != 0)
                 return true;
 
-        return k == 2 && h > 1;
+        return k == 2 && h > 7;
 }
 
 STATIC bool