OK, I solved coinSums after some struggle, using a recursive function that pulled the top coin value then reran itself with the remaining coin values… and it works and passes the test, but uses straight forward logic, like you would typically do it on paper (in fact writing out my solution on paper is how I came up with the algorithm).
But after solving, I checked the solution in the hint, and it’s what I typically call Matrix Magic. I’ve seen solutions like that in the past, and they make my head hurt and my eyes cross.
I can follow the loops, and I see what it’s doing, adding itself to previous values at the interval of the value of the coin in question, and occasionally my mind starts to grasp the big picture, and the pattern at play, but for the life of me I can’t full wrap my head around the logic of why it works. Worse, I can’t wrap my head around how I’d ever come up with that just looking at a problem.
So, is there a name for this kind of algorithm, and a good resource that explains how and why it works, and how to identify when and where to apply it? I’d ask someone to explain it, but shy of a whiteboard with pretty illustrations, and I can’t imagine how it could be put into words that would make more sense than the code itself.
Here was the solution in the hint:
(warning SPOILER ALERT- If you haven’t solved this problem before you should attempt it first)
function coinSums(n) {
const ways = Array(n + 1).fill(0);
ways[0] = 1
for (let x of [1, 2, 5, 10, 20, 50, 100, 200])
for (let i = x; i <= n; i++)
ways[i] += ways[i - x];
return ways[n]
}
coinSums(200);
HERES THE CHALLENGE i’M TALKING ABOUT:
I’ve tried to google this in the past, but not sure what its called, and ended up down a rabbit hole digging into serious Matrix Arithmatic typically used to solve the secrets of the universe.