5 kyu
Card Game
279 of 656tonylicoding
Loading description...
Mathematics
Algorithms
Performance
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.
Here's a hint let both Alice and Bob play optimaly, the best way
I have solved everything except the performance test
LC translation
my code seems logical but that performance test is really making some problems.
Very nice kata, a little bit tricky finding the optimal solution.
This comment has been hidden.
This comment has been hidden.
I like recursion, but there's an easy non-recursive solution.
Iterate instead of recurse, or raise the recursion limit ( not available in all languages ). Not a kata problem. Closing.
For 13 cards: 5 should equal 4
What's wrong in this?
Alice took 1, Bob 6, left 6
Alice took 3, Bob 1, left 2
Alice took 1, Bob 1, left 0
Alice totally took 5, test says 4.
Remember the instructions : Bob also tries to play optimally.
In your case, Bob could take 9 cards by playing it smarter so Alice would be able to only take 4 cards.
This comment has been hidden.
Does anyone have any hints for handling the performance tests? I've backed myself into a corner and a hint would go a long way :)
This comment has been hidden.
It can be done. This in itself is a hint.
Closing.
Random Tests Small Tests For n = 69 : expected 30n to equal 8n Completed in 1ms Medium Tests For n = 85853 : expected 42906n to equal 26n Completed in 1ms Performance Tests For n = 428708124794396147 : expected 107177031198598953n to equal 88n how is it possible?
Next time, please use the question label for a question, the issue label is reserved for problems with the kata itself.
And to answer your question : keep in mind that both players play optimally. For example, with
n = 69, Bob can constrain Alice to take only one card each time it is her turn. The beginning of that game is:n = 69 : expected 30n to equal 8n - is too little number n = 85853 : expected 42906n to equal 26n - is too little number For n = 428708124794396147 : expected 107177031198598953n to equal 88n - is too little number
even for optimal game
Putting a performance test at the end trully is a dick move. At least it should be announced in the instructions.
It tells you right in the second sentence that the number of cards goes up to
10**18though?Edit: I've added the
performancetag to be even more clear.This comment has been hidden.
Not entirely sure what you mean but Bob and Alice both try to get as many cards as possible.
This comment has been hidden.
How should I know how many cards bob will take?
if the number of cards is even, the players can either take half of the cards from the stack, or only 1 card -- as they choose;
According to: The aim of the game is to collect the most cards.
This test is wrong: test.assert_equals(card_game(100000000000), 99999999950)
Because after first round: Alice should take: 50000000000 and Bob should take: 25000000000 cards....
And if the answer is: 99999999950 -> means that Bob took only 50 cards at all
This comment has been hidden.
The aim is to have the most cards at the end. Not take the most of them each turn. Sometimes it's better to just take one.
Tell me someone. Why is the result 8 for 12 wrong?
This comment has been hidden.
12,11,10,5,4,2,1
alice -9 bob -3
I don't understand this. 12 is an even number so why is only 1 cards taken first?
Try to play the game on a piece of paper and try different strategies and try to find the best one.
I'm trying to figure out n = 12 and this is how to get 9 and 3
n = 12
Alice Turn: Alice = 1, Bob = 0, Remain = 12 - 1= 11
Bob Turn: Alice = 1, Bob = 1, Remain = 12 - 2 = 10
Alice Turn: Alice = 5 + 1 = 6, Bob = 1, Remain = 12 - 7 = 5
Bob Turn: Alice = 6, Bob = 1 + 1 = 2, Remain = 12 - 8 = 4
Alice Turn: Alice = 6 + 1 = 7, Bob = 2, Remain = 12 - 9 = 3
Bob Turn: Alice = 8, Bob = 2 + 1 = 3, Remain = 1
Alice Turn: Alice = 8 + 1 = 9, Bob = 3, Remain = 0
The following moves give a final score of 9: [1, 5, 2, 1].
TS translation, please review and approve.
JS translation, please review and approve.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Try to draw out the example - many people who tried this problem first came up with your solution. However, it might not be the optimal approach.
This comment has been hidden.
This comment has been hidden.
Add bigger sample tests
Just saying, but having
-1collections this kata is a part of... this makes me laugh :DI have learned a very important lesson in this coding excersise. DO NOT multiply by 0.5, it is not the same as / 2 due to the rounding errors introduced by a decimal number. I knew how to solve this problem at the very beginning of reading the scenario and how play would be optimally accounted for, but i did not take into account floating point errors and kept coming up about 40 to 50 cards off an the large number tests. I am new to newer languages of programming such as Java or Python, but used basic way back in the early 80's, lol. Solving my dilemma cost me about 16 hours! I will ensure that I use division by 2,3, etc rather than multiplying by .5,.33333, or any other decimal going forward.
If you're using IEEE754 numbers ( floating point ), you can multiply by
0.5just as well as dividing by2, but your integer precision will be limited to53bits.If you're using arbitrary precision integers ( such as Python integers, JS
BigInts, or HaskellIntegers ), you can divide by2- but in Python you will still have to make sure you're using integer division ( which is not/) - and in JS you will have to divide by2n( which is not2, but it will tell you so ).I'm afraid you learned a very important lesson ( it is! ) just a bit wrong.
Amazing kata! Really satisfying to complete after failing to solve it the first few tries. This deserves the upvotes.
Ruby fork resolving issue https://www.codewars.com/kata/61fef3a2d8fa98021d38c4e5/discuss/python#6203baae778de2f27b3f326b (for Ruby)
There was already a sample test for 28, which is an anti-greedy example :-)
.
Python fork resolving issue https://www.codewars.com/kata/61fef3a2d8fa98021d38c4e5/discuss/python#6203baae778de2f27b3f326b
.
Java fork resolving issues:
if you don't explain further the difference, hard to tell what to do about those two forks ;o
.
the sample tests are still missing the "anti-greedy-algo" case, at least in python.
C Translation kumited. This includes both the Kacarott extra sample test and updated description.
AFAIK there's gonna be a merge conflict anyway.
approve factor first pls
approved by someone
Factor translation
n = 12(to fail greedy algorithms)Please review and approve :)
This is approvable
How can the result be 9 for n=12 - the last sample test for java:
assertEquals(9, Solution.cardGame(12));
I find the result 8 on paper. Am I wrong??
This comment has been hidden.
I agree
But the optimal (non-obvious) method should be demonstrated somehow.
Who said that? Figuring out the optimal strategy is a part of the task - you not being able to solve this kata yourself doesn't mean that nobody can do it.
...you realize he already solved the kata, right...?
Sure, but then add the label "puzzle" when removing that part of the description.
Do you realize that his first comments were "oh no, why can't I get the correct result, isn't X a correct strategy? I don't understand :("?
So, you're taking the first meaning of the sentence while totally ignoring the context to give your answer, ok...
Why? There is no hidden information here. Its simply an algorithm question, what are the best moves to make, to get the most cards?
Personally, I would like to suggest to use smaller numbers such as
8or even9(to show what is means byBob plays optimally.)Factor translation was approved, which reverted the description
Could a mod provide a full ranking votes breakdown for this kata?
Currently it is:
I added another 6
I switched to
6too, so assuming no other changes happened it's become:6 kyux55 kyux4?x1I'd have approved this kata if there was a clear "winner" but with the average difficulty of
~5.5, it should probably wait for more feedback.yes let's wait a bit more, there is no rush
Ruby translation kumited, including a much more clear description with an additional detailed example. Please check and approve
Cheers
This issue is not fixed.
Like change
Ntonfor python rightyeah still not fixed for Java
I'm actually surprized the solution is that simple... Does anyone have a proof that this is really optimal?
This comment has been hidden.
Manual notification
Does this answer your question?
Closing now.
This suggestion was not handled in any way.
The range of N is enlarged for performance requirements (favoring a specific algorithm) - Since N can go up to 10^18, the time complexity has to be much lower than linear.
There's no need to run 1000 tests, or at least to have 1000 assertions in Python.
A naive solution, which analyzes all possible game states, times out for relatively small
N(N = 400is already too much for my code (tested in Python, idk about Java)). Unless a more efficient solution exists which you still want to prohibit, the input range could be greatly reduced.A more efficient solution exists ;-)
Firstly, if you're positive there's an "inefficient" solution which still passes the tests for relatively big
N, I'd like to see it, or hear how it can be done. Secondly, don't resolve suggestions not addressed to you.There's no need to run 1000 tests.
Closed by mistake, sorry
It should be stated more clearly that taking half the cards is optional, and the player can always choose to take only 1 card if such move is optimal.
The parameter name should be in snake_case for Python and in camelCase for Java.
change
card_game(N)tocard_game(n)...The solution should be imported explicitly in Python.
What am I doing wrong?
You're not obliged to take half the cards, hence this play is not optimal.
The description doesn't convey this very clearly, so this should have been raised as an issue, not the stuff you've written below.
Fine, but if Bob plays optimally, he will take as much as possible, right? (so less is left for Ann)
How could Ann obtain 23 cards?
No? Greedy strategy is not optimal for maximizing the score.
The following moves give a final score of
23:[1, 13, 1, 5, 2, 1].Description should specify:
"tries to get as many cards as possible for himself"
There's already an explanation of how a game with
10cards plays out. Explanations for4and5cards are a part of the10case, and these cases are simple enough to figure them out yourself.See question above
going along with this issue: the sample tests are currently totally useless, since a greedy approach is enough to pass all of them.