3 kyu
Topology #0.1: Converging Coins (Performance edition)
Loading description...
Mathematics
Graph Theory
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Phew, I did it. I was on the (more or less) right track with the easier version of this kata and already knew how to improve performance. A bit surprised to see the reference solution is 5 times more performant than mine ... Can't see yet how you did that. Still struggling with Python syntax. I must be overlooking something: maybe combine coins once they've met? Any pointers, anyone?
This comment has been hidden.
Thanks for the quick reply! Can't imagine that updating that memoization container while looping would make a lot of difference, but I'll give that a go. And I will study ecolan's solution as well, but I have to admit that reading and understanding code is a lot more difficult than writing it. Especially when you just about grasp the basics of the language. ;-)
This comment has been hidden.
Solved!! This has been gnawing at me for 3 months, I was on the right path with the basic edition already, but could not get my optimization right until I tried again today. @Blind4Basics I think we used the same approach
but your solution has lower space complexity(edit: I refactored mine with a more space-efficient bookkeeping.) All in all this could be a 2-kyu Kata :-) Thanks!I'm as happy as you are, because this thing has been on my mind for quite some time as well, but I had to make some progress in understanding Python syntax, before I could give it a crack. Having solved the easier version first (which took me a full day, I'm ashamed to admit) this one took me half an hour or so. So I think 3kyu is rated quite nicely.
This optimization is obvious and dumb, I totally should have thought of it. Well done good sir, and thank you for your work.
This comment has been hidden.
I don't know what is the first acronym (S...), so hard to tell... :s
From what I found, it seems it's related to adjacency matrices, and the complexity seems to be in n^2 for a square matrix. That will never pass this version, nope. Second way sounds far better, yes.
This comment has been hidden.
I suggest to emphasize in the kata description that
errrr, but it's already there, and the user is supposed to solve the easy version first which behaves in the exact same way.
Yes it's there, I'm just suggesting that it could be written a bit more clearly.
honestly, for a perf version and 3kyu, I don't see the need for the emphasis.
No need at all, just a suggestion to polish the kata description which I thought you'd appreciate.
I have been able to pass medium tests but now I am stuck on max-coin. I have been trying to optimize BFS starting from all unique coins. Basically, I want to remove all redundancies from BFS. I feel that I still have a lot of room for BFS optimization Im just not sure if it is worth it. Should I scrap it and try something else? I just want to know if I am stuck in the dead end.
It seems that max coin tests and huge tests require different approaches and different optimizations. I tempted to consider two different algorithms based on the number of coins. Does it make sense?
Is there one universal approach that handles max-coin and huge tests? Is there a simple elegant solution to this kata or does it require step-wise optimization? I have been considering various all-pairs shortest-paths algorithms but I feel that it would be difficult to extract number of steps.
hi,
from what I can see of your code, it looks like you're using the kind of algorithm/approach used in the original kata. You need something better. it's still doable with a bfs, I think, but you need better "additions" to the basic algo so that you reach the expected time complexity.
All current solutions use the exact same algorithm/approach to solve the max coins and huge tests.
'hope this helps...
This comment has been hidden.
note: there is an obvious logical flaw at the very beginning of your code (meaning a kind of test missing. .. x) ). Refresh the trainer: I just added the related test. ;)
Nice kata; haven't solved it yet, though. Could you be a little more precise on the expected time complexity in terms of number of vertices, number of edges, and number of coins?
Hi,
Errr, I'd like to not spell it out, and I'm actually not entirely sure either... Using
V,E,Cfor vertices, edges and coins, does that satisfy you if I say you need better thanO(V*E*C)? (I guess, it's almost like spelling it out anyway, no? :o )This comment has been hidden.
(actually.... ;o )
I'd like to give possite feedback, but don't see the option to do so. I think I missed it when I I submitted my first solution. I'd also like to approve the kata and give it a 3 or 4 kyu rating, but not sure I have enough honor points to do so.
not following what you mean, sorry.
you don't see the "kyu badges", you mean? Would be pretty weird (and should lead to raising an issue if so)
you ranked it already (at 3). And you cannot approve it anyway because it needs more votes and rank suggestions yet.
I meant positive not "possite". I see the kyu badges. But so far this kata has a "like" rating of "100% of 1". It should have 100% of 2.
weird. First time I hear about the buttons for rating disappearing. Could you make a screenshot?
It might something to do with the fact that
zLukiecolban is not eligible for a reward for this kata (forfeited it or edited). Maybe their solution does not count?what's the link with ecolban??
Sorry, misremembered the name :/
Sorry. Now I see the satisfaction buttons. You now have 100% of 2!
I'm hesitating to add some tests with a high number of coins (like 100-200 coins), but that will be hard to fit in the time limit, maybe. Opinions?
ok, I just realized I could optimize one more thing. the gain should allow the "max coins" batch of tests. Unpublishing for now.