Recent searches
Search options
More fun with this week's @cassidoo coding problem, though I'm surprised that the simple memoised recursive solution seems to outperform the one based on repeated matrix squaring. I guess squaring a 365x365-element matrix takes a while... https://github.com/pozorvlak/cassidoo/blob/master/2024/04-04_dice_sum/dice_sum.py
@pozorvlak @cassidoo The divide and conquer of the matrix strategy combined with the memoized recursion of the other:
@pozorvlak @cassidoo Thanks. I don't think I've ever used this divide by two approach explicitly in a recursion before but I think it's going to be my go-to method for a large number of interview type questions now.
@dpiponi @pozorvlak This is probably not at all in the spirit of the thing, but if in reality I needed to do this I think I would use Sage and write:
def dice_sum(num_dice, num_sides, target):
R.<x> = ZZ[]
die = (1 - x^num_sides) * x / (1 - x)
dice = die ^ num_dice
return dice.numerator()[target]
@robinhouston @dpiponi I think that's a totally valid submission! My matrix code is really just a polynomial expansion in disguise. @cassidoo
@cassidoo @pozorvlak @dpiponi We've managed to get programmers to the point where they're comfortable treating functions as first-class objects. When are we going to see a mainstream programming language in which polynomials are a first-class data type?
@robinhouston @dpiponi I like to approach @cassidoo's coding challenges like I would an actual interview problem - write a naive implementation first, optionally write some more tests, then try to write a faster and/or cleverer version and check it agrees with the naive version. But people approach them on all sorts of levels - some people jump to the efficient version, others stop at the naive version, and some people try an off-the-wall approach.
@robinhouston @pozorvlak If the Sage code uses repeated squaring for powers, and you think of the "convolution" in my code as polynomial multiplication, I think the Sage code may be doing the same work as my code.
(I was tempted to use my own power series library for this.)
@pozorvlak @dpiponi Ah, cool! That makes sense. Yes, I'm sure it does use repeated squaring to compute powers.
I've realised my code would be better like this, to avoid the fiddliness of producing a rational function whose denominator is always 1:
def dice_sum(num_dice, num_sides, target) :
R.<x> = ZZ[]
die = (1 - x^num_sides) * x // (1 - x)
return (die ^ num_dice)[target]
@dpiponi @robinhouston @pozorvlak behind the scene, Sage uses Flint for dealing with univariate polynomials over Z.
So it's optimised a lot.
@dimpase @robinhouston @pozorvlak So it could, for example, be doing a (variant of) FFT behind the scenes to implement the convolution.
@dpiponi I think your code is doing less work: the convolution ensures you only calculate the target'th coefficient, whereas the Sage code will presumably calculate them all. My code calculates *up to* the target'th coefficient, but also does a bunch of pointless multiplications by zero. @robinhouston
@pozorvlak @dpiponi I've found with similar things in the past that that optimisation makes surprisingly little difference to the overall performance; but i haven't measured it with this problem specifically
@pozorvlak @dpiponi And obviously there are degenerate cases where it makes a big difference
@robinhouston by "that optimisation", do you mean "only calculate the term you care about" or "eliminate pointless multiplications by zero"? @dpiponi
@dpiponi @pozorvlak The former
@robinhouston @pozorvlak In the spirit of my original code here's a fast (off by one) Fibonacci calculator. It uses the fact that the number of ways of getting n by rolling *any* number of 2-sided dice is F_{N+1}. You can get a total of N either by getting N//2 followed by the remainder, or getting N//2-1, then a 2, then the remainder.
@dpiponi I guess my first recursive algorithm is worst-case O(n t), but probably much better than that because it can bail out early unless t is close to mn, and yours is O(m log n)? The matrix algo is O(log(n) t^3), which is a bad trade because t must be at least as big as n. Not sure what's up with dice_sum_unordered (which I added later) - I guess it's searching a smaller space, but getting less benefit from the cache? @cassidoo
@dpiponi whoops, turns out I wasn't actually bailing out if t was out of the achievable range! With that improvement, my recursive solution is almost as fast as yours:
> python dice_sum.py dice_sum_recursive: 0.0700306750004529us
dice_sum_unordered: 4039613.5409973795us
dice_sum_matrix: 41671.05000014999us
dice_sum_numpy: 57640.21680006408us
dice_sum_dan: 0.06897160840017022us
In addition I realised you can replace t with n*(m+1) - t if the latter is smaller. Doesn't make much difference on the recursive solutions, but it does make a huge difference to the O(t^3) matrix solutions.
https://github.com/pozorvlak/cassidoo/blob/master/2024/04-04_dice_sum/dice_sum.py
@pozorvlak @cassidoo @robinhouston That n*(m+1)-t trick is nice. I'll squirrel that one away for future use :)