Junilu Lacar wrote:Seems to me a name like "distance" instead of windowSize would make more sense.
Using windowSize creates some dissonance with the usage of windowed(size = n), I think that's what was bothering me.
Hm, I still don't get this - it's the same concept. A "window" is the moving subset of the list/array that we're interested in performing a calculation over, and seeing how the result changes. You and I both Yes, you also use windowed(size = 2) to look at the changes between adjacent elements, and I don't, so I'm not particularly concerned with that other usage. The concept of a window is not limited to whether we actually use the windowed() method.
Junilu Lacar wrote:Also, while I'm not really averse to reaching outside of a closure
I'm not averse to it at all, especially if we're calling it a closure. That's the point, it's able to access free variables in scope. I'm not concerned with avoiding that just to avoid that.
Piet Souris wrote:Note that with all the fine optimalizations and Kotlin-excellenties, that it only works when the window-stepsize is 1 and the function to apply is suitable, like sum or prod. Try it when the function is say max (window).
Well, the specific combination of optimizations I got only works under those conditions, true. But the most important part of what I was doing, in my opinion, was going from an O(N*N) operation to an O(N) operation, by means of looking only at what's newly entering the window, and what's exiting. We don't need to calculate each new window from scratch. You may need to perform the calculation on the entire first
window, though that was not needed here. That technique can also be used for other step sizes, and retain O(N) overall.
The point about it only working for a suitable function is valid - but there are still a wide number of functions it can be applied to. The key is, we need to be able to pull elements out of the calculation as they exit the window, based only on their value. You give max() as a good example where that won't work easily - once the max value exits the window, how to we know what the new max value is? A fair point. I think there's still be a way to do this using a sorted collection, where we end up with O(N*log(N)) overall, still better than O(N*N). Still, there are many calculations out there that you can do this for. I've done something like this for applying least-squares curve-fitting to data points as they come in, for example.
Of course, most of these considerations are overkill for something like this day 1 exercise, where O(N*N) is just fine. Stephan's point about barfing out crude code to get a solution quickly is very much the case for me as well. (Though, curiously, my day 2 code came out pretty pristine this time.) Most commonly I have a lot of print statements as I go, that get commented out as I see things working correctly. And it's often one big main() method, unless and until I feel the need to extract methods.