@Voile that is a much cleaner way to do what I ended up doing..

i'll refactor this into something that only uses space proportional to len(signature) later.. currently using space linear in n

edit: https://www.codewars.com/kata/reviews/59615449fd2549f7f10000dc/groups/596193700fe92eab740001b4

Hey man! Thanks for your observation. You're right, the reference actually employs a greedy approach. I tried a bunch of cases and it always seemed to be giving the optimal solution, so I thank you for disproving that. The final example you give is particularly odd; I'll have to look into that. I'll unpublish the kata for now, since this is a relatively large problem and I can't fix it right now.

I believe that there's a bug with the reference solution. My code fails this test case:

weight=325, plates=[50, 45, 35, 25, 20, 15, 10, 2.5] -> [50, 45, 45] should equal [50, 50, 35, 2.5, 2.5]

Here, two 50s and 4 45s gives 280, and then 45 from the bar on top of that gives 325. My code finds the optimal solution (using as few plates as possible) while the reference gives one with more plates. My code is a bit slow as I'm currently iterating through all multisets rather than attempting a DP approach, but I found this as I was testing and thought it would be worth pointing out.

edit: found another case.

weight=760, plates=[45, 35, 25, 15, 10, 2.5] -> [45, 45, 45, 45, 45, 45, 35, 35, 15, 2.5] should equal [45, 45, 45, 45, 45, 45, 45, 35, 2.5, 2.5, 2.5]

the solution I find uses 10 weights while the reference uses 11.

another potentially more concerning one

weight=925, plates=[50, 25, 10] -> [50, 50, 50, 50, 50, 50, 50, 50, 10, 10, 10, 10] should equal "What a shitty gym, I'm cancelling my subscription!"

that shows the reference rejecting a valid solution.

If you count for each iteration of your loop, your algorithm is O(N^2) where N is the length of the input string. Using a counter makes one pass over the entire string, then gives you constant time lookups for the loop. You end up using O(N) time and space for this solution.

Just as an aside - if you were to try to build the counter by using repeated calls to str.count, you would be incurring a quadratic time penalty, because you'd have to call str.count for each letter in the input.

Agree. I'm not seeing how the second beggar in the 3 beggar example gets 7 coins. I took a look at the kata you referenced and it looks like following those rules the first beggar would be the one getting 7 coins here.

edit: actually it looks like they are forced to take turns grabbing whatever is at the head of the list, so the detailed description for 3 beggars would be something like:

[1, 2, 3, 4, 5] are the piles of gold; the first beggar gets [1, 4], the second gets [2, 5], and the third gets [3], so the totals are [5, 7, 3]

:)

This was a real treat. Thanks for posting it!

Was confused for a second reading your function definitions... specifically the first arguments to encode and decode. Thought it was some fancy pattern matching because of the as syntax in defining the functions. :'(

Upvoted but it's probably best practice to avoid overshadowing keywords in function arguments in general :')

I actually fixed that comment and re-uploaded my solution a few minutes after I submitted this one... I was pretty embarrassed about that! Good catch!

Thank you~

Very good observation on centered sum!

Just a niptick: i varies from 3 to n // 2, so it is O(n) solution, not constant (aka O(1)) ;-)

Might help to emphasize the shape of the output for larger n - would help people like me who don't look at the example outputs carefully..