4 kyu
Bribe the Guards of the Crown Jewels
160 of 234ecolban
Loading description...
Dynamic Programming
Algorithms
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.
I don't understand the underlying maths: e.g. if we start at 7, and the jewels are behind doors number 10, we haveto pay 7 + 8 + 9 + 10 = 34, however the description says it is 26. Where is 26 coming from?
You can skip door 8 and go directly to door 9. You end up paying 7 + 9 + 10 = 26.
This comment has been hidden.
Yeah. This is one of the first katas I wrote and I misunderstood the purpose of preloaded. Thanks for correcting it.
.
python new test frameworks
Thanks! Approved.
.
This comment has been hidden.
This one had me stuck for a while. I think the description of the problem is somewhat confusing. It kinda makes it sound like you are expected to do the binary search, just starting from the optimal position, rather than from the middle of the list. This part: You are better off if you first go to room 7. In the worst case the guard will direct you to the right(i.e., higher numbered rooms) and then you go to room 9. should probably emphasize that you're not just picking room 9 because it happens to be in the middle of 8,9,10, but actually choosing the most "cost efficient" room at each step. And it's only made more confusing by the fact that a "nudged" binary search will solve the simple cases, which made me go crazy thinking that i must be on the right track and only failing harder cases because of some dumb mistake, like not splitting the list properly or something.
But apart from that, i think it is an interesting problem, searching for the worst outcome of making the best choice rather than the best choice itself.
This comment has been hidden.
Read the description of the kata again. It explains why a simple binary search is not the solution.
This comment has been hidden.
This doesn't make any sense to me. I think you're asking to find the path to the door with the minumum cost given some worst case scenario, but what is your definition of worst case scenario? It seems completely arbitrary.
It's not that the final door has the highest cost (per your explanation for ([5, 1, 2, 4, 3]), 8)). It's not that the path to the door is the longest (per your explanation for [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 26). It's not choosing the first door that results in the highest possible costs and finding the min cost among the resulting possible paths (per your explanation for ([1, 2, 3, 4, 5]), 9)).
I don't know what else it could be. The test cases and explanations seem contradictory.
The worst case scenario is the scenario where you end up spending the most money. Take the case where the bribes list is
[5, 1, 2, 4, 3]. You ask the guard at the second room after paying him $1. If you are lucky, he'll say it's the room he's guarding, and he'll let you in. Your total cost is $1. But if you are less lucky, he'll say the room is to the left. In this case you end up paying $1 + $5 = $6. If you are even less lucky, the guard points to the right. You know that the crown jewels is in one of the three last rooms but it will cost you and addtional $7 to get into the room. So, ussuming that every time you ask a guard where the crown jewel are you get the "unluckiest" answer, you end up paying $8.I think your explanations are wrong and that's what confusing me.
For that example, if you start with the third door ($2) and you have to go right ($4) and then right again ($3) it costs $9. It would make sense if this was the absolute worst case and then you have to optimize the path to minimize cost ($8), but if you start with room 4 ($4) then go left ($1) and left again ($5) it costs $10 and the minimum cost to that door is $6 if you choose door 2 and just go left. If you're going to say "you can't just pick door 2 if door 1 is the worst case" then how do you justify you explanation for ([1, 2, 3, 4, 5], 9)? Once you find wcs is behind door 5, why can you arbitrarily start at door 4 to minimize cost? You're not getting the "unluckiest" answer when you start at 4.
It seems like there are more rules you haven't explain (specifically about choosing first and/or last door to get "worst case" and how many steps you can take when minimizing cost) and I can't extract them from the test cases and explanations. Almost like it's "find the worst case scenario given some cost function and then minimize an additional cost function given the worst case scenario". It seems very convoluted.
Also, I think this is a really interesting problem and am in no way trying to disparage you. I just really want to solve it, which is why I'm frustrated that I can't follow your logic.
Look at it as a game. You choose the door, I tell you to go right or left or stay put. You choose the doors so as to minimize the cost. I choose the direction so as to maximize the cost. My choices of direction have to be consistent, i.e., there must always be a door that fits all my directions. If we both play optimally, what cost do we end up with? If we play the game of
[5, 1, 2, 4, 3], I can force the cost to be at least $8 no matter what you do. But you can ensure that the cost is not higher than $8 no matter what I do. So $8 is the answer to this game.Since I am working against your objective of lowering the cost to a minimum and my moves are the best for me but the worst for you, you can think of my moves as the "worst case".
That makes way more sense. Thank you.
I was not thinking about the problem from a game theory perspective.
I'd suggest including some of this explanation in the problem statement unless you think it takes away from the intent of the kata.
I just read the description like 5 times and still don't get your idea of a worst case scenario. Obviously you need the sum of all the bribes in the worst case scenario which is that you guess the right door after attempting all the others first. But that doesn't involve any coding, so I'm back at square one totally clueless about what I'm supposed to do.
I haven't solved it yet, but you don't need to add all the bribes as you see in the example doing a binary search.
You need to pick the best possible combination of guards, in correct order, that would cost you the least amount of bribes if the jewels are in the worst possible room for you.
This comment has been hidden.
Recursion is a good approach. Are you solving the same problem instance more than once?
I dont think so.
This comment has been hidden.
JavaScript translation
Haskell translation
Thanks for the translations. Approved!
Approved ;-)
Thanks!
Python 3 should be enabled because Python 2 is going to be deprecated soon.
Fixed. Please mark as resolved if you're satisfied.
;-)
A really good Kata, thanks. I used pen, paper and thinking. Top notch.
Thanks. I'm glad you enjoyed it.
Maybe I'm not understanding the setup, but it seems to me like the answers are wrong?
test.assert_equals(least_bribes([1, 2, 3, 4, 5]), 9) If I pay $3 for the middle door and $4 for the fourth door, that is the worst cost for knowing which door the treasure is behind. 3+4=7 < 9
test.assert_equals(least_bribes([5, 1, 2, 4, 3]), 8) Similarly, pay $2, $3: 5 < 8
test.assert_equals(least_bribes([3, 2, 5, 4, 1]), 10) Again, worst case is $5, $4 = 9 which is less than 10
Once you have determined which room the crown jewels are located in, you still need to bribe the guard in front of that room to get in.
test.assert_equals(least_bribes([1, 2, 3, 4, 5]), 9): If you pay $3 for the middle door, the guard says "right", then you pay $4 for the 4th door, and the guard there says right again, then you have to pay $5 to get into the 5th room. In total you are paying $3 + $4 + $5 = $12 > $10. The correct strategy is to start with door 4 and pay $4. If the guard says right, you pay an extra $5 to get into room 5. If the guard says "left", you go to door 2, ad then (in the worst case) to door 3. In the worst case you end up paying $4+$2+$3 = $9.The second case (
test.assert_equals(least_bribes([5, 1, 2, 4, 3]), 8)) is explained in my answer to Christian below.This comment has been hidden.
Thanks for the comment. Here is the strategy for this example:
This comment has been hidden.