papa2fire

4 ms·

1.
by papa2fire 2y ago
Following your suggestion, I’ve implemented the PSA algorithm (the optimized one) in C++. It might be tricky to understand without an explanation, especially since (1) it’s generalized for any dimensionality, and (2) I manually implemented
2.
by papa2fire 2y ago
Ohh, very interesting, thanks! I’m not entirely sure, but yes, I’d say my naive implementation uses the hockey stick principle. That said, I think many implementations are possible. We could also eliminate recursion by using an index array
3.
by papa2fire 2y ago
To understand recursion, and given that we know the initial value of r (r=4), I suggest replacing the recursive calls with a simple copy-paste of the function body. You’ll see that it’s just four nested loops each one iterating over the 14
4.
by papa2fire 2y ago
I still have trouble understanding your code. I don’t get why you’re still using ‘probas’ and the inverse probability (line 186:187). I suggest creating an array of 3^14 random numbers and simply using it as input to the function to sum Ham
5.
by papa2fire 2y ago
The key point is that your code takes as input ‘probas’, a 3x14 table with probabilities of independent events. From this, you assume the structure of the space by multiplying result of 14 events. Here, you can apply the trick of grouping n
6.
by papa2fire 2y ago
My algorithm reduces the number of summations by computing all expected values at once, so I can't compute just a single value individually. For a single value, I think the naive approach is the only option. In my first naive implement
7.
by papa2fire 2y ago
11 seconds in colab implementing the basic transformation with reshape, roll, and flatten 4 seconds in google apps script by handling indices in loops instead of rearranging elements
8.
by papa2fire 2y ago
Excuse me sir, to me all topics here feel like a wendy's so I thought this was the right place. Thanks for the suggestion, I’ll post it there too!
9.
Show HN: Betting game puzzle (Hamming neighbor sum in linear time)
56 points by papa2fire 2y ago|16 comments