Another CodeWars kata, by the same person who did Twice linear. It was annoying in a different way. Once again, a naive solution was out of question (or so I thought), so I kept trying to figure out a way to shortcut the whole problem with maths.
Generating the integer partitions (and their products) isn’t particularly difficult. There are plenty of resources out there about how to do it – though for some reason mostly in Python.
There is a pretty simple formula for finding the largest product. I lost the link to the Stack Overflow (or was it Stack Exchange?) question where I found it explained that the maximum would be made from 2s and 3s only (as many 3s as you can fit, obviously).
But that would only solve one third of the problem: while I got the range, I had no way to calculate the average or the median. Especially for the median, I couldn’t find even hints about how I could do that without generating the list.
So I ended up just generating the list “naively”, making all the integer partitions using recursion, then bruteforce map-reducing then unique sorting it. I was actually surprised that it worked. I guess I was paranoid about how big the numbers could get (since I’m sure eventually it’d be just too big).
Or maybe the way I generated the partitions was the “right way”? I tried looking for a way to find the product of partitions too, but I couldn’t find any way without generating the partitions first. And since my kinda-naive solution worked, I’m not motivated to keep looking either.