Show HN: Betting game puzzle (Hamming neighbor sum in linear time)

In Spain, there's a betting game called La Quiniela: https://es.wikipedia.org/wiki/La_Quiniela_(Espa%C3%B1a) Players predict the outcome of 14 football matches (home win, draw, away win). You win money if you get at least 10 correct, and the prize amount depends on the number of winners. Since all bets are public, the number of winners and the corresponding payouts can be estimated for each of the 3^14 possible outcomes. We can also estimate their probabilities using bookmaker odds, allowing us to compute the expected value for each prediction. As a side project, I wanted to analyze this, but ran into a computational bottleneck: to evaluate a prediction, I had to sum the values of all its Hamming neighbors up to distance 4. That’s nearly 20,000 neighbors per prediction (1+28+364+2912+16016=19321): S_naive = sum from k=0 to r of [(d! / ((d-k)! * k!)) * (q-1)^k] (d=14, q=3, r=4) This took days to run in my first implementation. Optimizing and doing it with matrices brought it down to ... Read full article.