5 kyu
Don't Eat the Last Cake!
590 of 1,780SagePtr
Loading description...
Puzzles
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.
Rust translation ready for review.
Could it be pointed in the task you are going to play yourself? As now it causes some dissatisfaction to return and write its behaviour in losing positions after failure of playing with yourself.
Added this requirement to the description
do you guys think these are actually toast instead of cakes?
This took me 5 days!!! I really want to say this is far too difficult to be 5 kyu but the solution is really simple once you get it. Thanks for the great kata :)
Should've just used functions or static functions since the methods is supplied with the needed parameters each time.
Well, it's this way now.
And it has been this way for seven years.
People had all kinds of bad habits in the bad old days.
And some that weren't so bad - but, granted, this was not one of those.
Haskell translation
seems to be approved
Tests are failing weirdly not marking my victory correctly: there are 15 cakes on the table; you decide to go first your turn: there are now 15 cakes on the table; you eat 1 cake my turn: there are now 14 cakes on the table; I eat 3 cakes your turn: there are now 11 cakes on the table; you eat 1 cake my turn: there are now 10 cakes on the table; I eat 2 cakes your turn: there are now 8 cakes on the table; you eat 1 cake my turn: there are now 7 cakes on the table; I eat 3 cakes your turn: there are now 4 cakes on the table; you eat 1 cake my turn: there are now 3 cakes on the table; I eat 3 cakes your turn: there are now 0 cakes on the table; you eat 0 cakes
These are the Haskell sample tests right?
I can't explain how you got this; the logic doesn't seem to allow it. Does it help to reset the tests? ( Save your code before resetting! )
If not, please post your code ( properly marked up and spoilered ).
It's a reallllly cooool kata!
Enjoy it very much, have so much fun~
thanks~
This is a good kata. You can solve it by basic logic, or you can go and turn it into an example for (basic) AI and write paths&decisiontrees.
Which, given the shortest solution for this, complete overkill, but still fun in and on itself.
There seems to be a bug in the example cases: I have the following output:
You ate 1 cake, 1 cake still left ✘ Game over: stalemate
Problem is that it doesn't follow it's own rule 4: "If one of the players has no valid moves (e.g one cake left and previous move was one cake), that player will lose his turn and be skipped. Then the other player will be forced to eat the last cake. This is the ONLY case of turn skipping."
Problem is in example tests, line 38, where 0 must be added in the list of allowed moves in the case above.
Nah, just a missinterpretation on your side.
2 cakes are left. YOU eat 1 cake. ENEMY now has to skip because he can't chose 1 again (as described in rule 4). YOU have to eat the last cake (aka, stalemate loss), because you can chose 1 again (as enemy effectively was forced to chose 0)
This comment has been hidden.
Well, I solved it by making a very simplistic (after all you only ever have 3 choices for each state) decision tree. It's by no means as complex as even a basic 'real' tree, but still other people solved it in +-5 lines of code by reverse Engineering the game logic. It's really your call whether you want to do the same and get the easy logic solution, or instead use this as decision tree training.
This comment has been hidden.
Love it. This riddle made me think a bit.
there is a problem with this kata, i just submitted a solution that doesnt make sense and it passed.
This comment has been hidden.
There seem to be a problem with submitting this kata. Run Tests works fine but submit gives a null pointer exception stacktrace. Looks like its coming from the test framework.
java.lang.NullPointerException at java.util.regex.Matcher.getTextLength(Matcher.java:1283) at java.util.regex.Matcher.reset(Matcher.java:309) at java.util.regex.Matcher.(Matcher.java:229) at java.util.regex.Pattern.matcher(Pattern.java:1093) at clojure.core$re_matcher.invokeStatic(core.clj:4674) at clojure.core$re_find.invokeStatic(core.clj:4716) at clojure.core$re_find.invoke(core.clj:4716) at codewars.runners.java$class_name.invokeStatic(java.clj:14) at codewars.runners.java$class_name.invoke(java.clj:11) at codewars.runners.java$source_code_file.invokeStatic(java.clj:35) at codewars.runners.java$source_code_file.invoke(java.clj:30) at clojure.core$map$fn__4785.invoke(core.clj:2646) at clojure.lang.LazySeq.sval(LazySeq.java:40) at clojure.lang.LazySeq.seq(LazySeq.java:49) at clojure.lang.RT.seq(RT.java:521) at clojure.lang.SeqIterator.hasNext(SeqIterator.java:38) at com.sun.tools.javac.api.ClientCodeWrapper.wrapJavaFileObjects(ClientCodeWrapper.java:140) at com.sun.tools.javac.api.JavacTool.getTask(JavacTool.java:132) at com.sun.tools.javac.api.JavacTool.getTask(JavacTool.java:107) at com.sun.tools.javac.api.JavacTool.getTask(JavacTool.java:64) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) at clojure.lang.Reflector.invokeMatchingMethod(Reflector.java:93) at clojure.lang.Reflector.invokeInstanceMethod(Reflector.java:28) at codewars.runners.java$compile_and_load.invokeStatic(java.clj:83) at codewars.runners.java$compile_and_load.doInvoke(java.clj:79) at clojure.lang.RestFn.invoke(RestFn.java:460) at codewars.runners.java$fn__599.invokeStatic(java.clj:111) at codewars.runners.java$fn__599.invoke(java.clj:105) at clojure.lang.MultiFn.invoke(MultiFn.java:229) at codewars.runners$run.invokeStatic(runners.clj:22) at codewars.runners$run.invoke(runners.clj:17) at codewars.core$_main$fn__664.invoke(core.clj:40) at clojure.lang.AFn.call(AFn.java:18) at java.util.concurrent.FutureTask.run(FutureTask.java:266) at java.lang.Thread.run(Thread.java:745)
I really enjoyed this kata ~ vary interesting, thank you for sharing!
I think there may be a problem with the win conditions for the case where you start with 2 cakes. As first round the opponent can choose the same number as you, it would make sense to go first and eat 1 cake. The opponent can then also eat 1 cake as it is the first round and the move is open to him. When I put that in, it said my solution was incorrect but it worked if I assumed the stalemate condition still applied (even though it was round 1).
Only the first player gets the freedom to pick any of the 3 numbers. The first move of the second player is subject to the restriction. So if you start with 2 cakes and volunteer to play first, picking 1 will stalemate your opponent and you are forced to eat the last cake.
490 cakes? (Actual number encountered during random tests)
We'd both die of overeating.
This is definitely a challenging problem that requires above-average skill in algorithm design, if the solution is required to scale like this and still run all tests in under 6 seconds.
I thought I had a decent solution that scaled a lot better than O(2^N) (my first working solution before improvements) until it hit random testing and all hell broke loose.
Java: My solution works fine for the first test cases but when I submit it it apears to add the numbers I return rather than subtract them.
400 submitted solutions. If this is still an issue, please reraise ( with extensive debug output )
This comment has been hidden.
Very interesting. I love this kata.
这道题第一次让我无从下手，看上去并不难，但是却找不到突破口。。。good kata！
你解决了吗？搞了两小时，搞不定。有思路吗
我想应该选择先手，多于5个时，想办法给对手剩下5个，你就赢了，我猜的，你试试？
Please clarify what is meant by rule 3 "doesn't effect the first move, only to subsequent."
If I eat 2 cakes on the first move, can my opponent eat 2 on the second move?
If you eat 2 cakes on the first move, your opponent can not eat 2 on the second move.
Closing.
That took me a long time to figure out, but was a fun puzzle and helped me see the value of pattern recognition (and starting slow and simple when abstract mathematical problem-solving isn't your forte). I slowly plotted out my system, going through each number of cakes from 1 to 14, trying out all the possibilities for each move, until I noticed clear patterns. Then when I tried out what I had come up with it worked :D
According the rule number 3: "This doesn't effect the first move, only to subsequent." If I am the starter and eat 3 cake at first the opponent can eat 3 cakes too. I could not find a nice solution therefore I checked a solution and run some test for example: there are 12 cakes: Using [3,3,0,1][cakes % 4] rules for moving the starter is a winner but if i keep the rule the opponet should be a winner
Maybe I misunderstand the rules or there is a mistake in my workflow. Could you explain what is wrong ? Thanks
very first move of the whole game, not once per player.
If you are the starter, your opponent will do the second move as his first move.
This comment has been hidden.
LOL. I've bruteforced all game possibilities. At least I am caching previously computed solutions. Very nice kata!
Is there some limit in terms of a minimum number of cakes on the table?
There will be cake.
So,
1This comment has been hidden.
When you've solved the kata, you can fork your solution and look at
Preloaded. It's in there.Really fun Kata!
Still struggling with this one, won't give up easily. Great food for thoughts!
May be I got the description wrong. Because according to the output:
5 cakes on the table. You decided to move last I ate 3 cakes , 2 cakes still left You ate 1 cake , 1 cake still left
One poisoned cake still left for the opponent. I should win. But it is written - GameOver. Where is the mistake?
Since you ate 1 cake in your move, your opponent can't copy by eating the last cake. Thus, he is forced to skip his move. And as such, you will have eat it in your next turn.
This is the ONLY case where a move can be skipped. It's the 4th rule in the description.
Resolved
This kata can only be solved by luck... i mean as soon as there are 2 cakes you either lose or it's a stalemate and that's god knows why your fault. And you can't fully avoid the 2 because your opponent chooses his number of cakes by random...
Fix your game, SagePtr.
LOL! First of all, why do you assume your opponent chooses a number at random? And far more importantly, why does that matter at all? It would be quite a bit harder to avoid 2 if he did NOT choose randomly after all. As the kata description clearly states the player who has to make a move with 2 cakes left on the table loses. Always. No luck here, my friend - just eat your cakes with reservation! This, by far, is one of the more well written and enjoyable katas I've stumbled upon.
I don't quite understand the rule "You cannot copy your opponent's previous move, likewise they cannot copy yours. If your opponent takes one cake, next move you can only choose between two or three. If you take three cakes, your opponent can only choose one or two. This doesn't effect the first move, only to subsequent." for example, i move first with 2, then can enemy move 2? b/c "This doesn't effect the first move, only to subsequent" So you cannot copy after first move of anyone or first move of both?
Never mind, this doesnt affect the solution, as long as you can decide who go first then it's all ok
Is a stalemate supposed to count as a failure? According to the instructions your turn is skipped, and the opponent loses. Consider the simple example of a game starting with 5 cakes
I go first 1 > 3 > 2 - I lose 2 > 1 > 2 - I lose 3 > 1 > 0 > 1 - Stalemate in my favor You go first 1 > 3 > 1 - I win (So you would not choose this) 2 > 1 > 2 - I win (So you would not choose this) 3 > 1 > 0 > 1 - Stalemate in your favor
In this sceenario I can't win 100% of the time. Even if I choose who goes first my best case scenario is a stalemate in my favor
Yes, sometimes stalemate is the only way to win, if you make your opponent make stalemate.
Loved this one!
You should definitely check that the player can play with itself... Or it will end up with answers such as mine...
I think it does in the test cases when you submit the solution.
Nope, Mine still works
The task does not require a player to play against himself, only against an opponent.
You get to choose who goes first, and that is allowed to influence your strategy. If you don't get to decide, your strategy need not make sense.
This comment has been hidden.
Python tests contain
1as starting count. And failed due to lose. Is this reasonable?Yes, because you can choose who moves first
I've solved this kata, ending in victory but it's not passing me due to a stalemate exception. Any info on this?
This happens if 2 cakes are left and you eat one of them. Try to avoid this situation.
why can't I do that? If there are 2 cakes and I ate one, the opponent will take the last...
He cannot eat one cake, because you ate one cake on previous turn.
I feel sorry for asking but I really can't get my head around this one. And even dumber as it is apparently an easy one... I thought about multiple approaches:
You should find strategy, how to decrease number of cakes without giving opponent chance to win. Each your move not only shortens cakes amount, but also prevents opponent from eating same number of cakes as you.
The key really is who moves first!
Math, write out the a few cases, do you notice a pattern? Then your code should try and force the other player into the position you don't want. The code that's running this definitely is just taking two instances of your class(add some System.out.println's) very easy to detect.
For an added challenge, write your solution so that you can still play the game even if your opponent gets to decide who goes first (and thus, can beat you).
I.e. your Player should still be able to follow all of the rules for legal plays, even when it is going to lose.
Now THAT was a really fun kata!
Nice when a problem simplifies down to ~nothing. =D
I agree with the other comments regarding this kata's simplicity, yet it will soon be rated around 4 kyu when it leaves beta. The programming knowledge required to solve this does not extend beyond if/else statements and basic OOP. I feel this is around 6 kyu, but are others raising their rating due to the pattern recognition involved? What is the community's approach to mentally challenging yet programmatically simple kata?
You raise a good point. Its definitely more difficult to determine a ranking for these types of challenges. Being a skilled programmer is just as much about being able to solve problems and doing so in a simple mannor, and not just about how skilled you are at writing complex logic. Not only is this a problem solving challenge, but also a rules/requirements challenge, so that helps to increase its ranking a bit. With that said I personally think it is a 5 kyu (which the author also estimated it as). Moderators sometimes override the average ranking determined by the community, but we are trying to get to the point where they don't ever need to.
Thanks for the response. In the future I won't determine my rating solely based on the simplest solution possible. That minimal rating must be boosted by the difficulty of achieving that simple solution. Sounds good!
I still think there's value in what this exercise really gets at, most algorithms today are simply math. How you write that formula in your code is up to you, but this is a math problem, not particularly a coding exercise.
My solution passes every test case, repeatedly. When I submit, the gameplay shows that I win. However, the "easy test" says I ate the last cookie. Mathmatically the gameplay shows otherwise. Disparity between test case and submit test?
That's really interesting. Can you post your code? It didn't do this to me, so I'll need your code to test it.
First test case prints verbose log of game. Other test cases don't print any logs, they only return results, so you will see log of the first game only. And they differ from example test cases.
SagePtr, I figured that much - but thank you for clarifying. I am still working on the challenge - I'm using simple logic so time to change my approach.
I'm in the exact same situation as you were 5 months ago... Any non-spoiler tips for a confused soul?
Unfortunately no. I moved on to other Kata. Thanks for reminder, time to come back and give it another go.
Remember that if there are 2 cakes left and you eat 1, you will cause a stalemate and eat the last cookie as well. If that doesn't help, I recommend making a spreadsheet of which moves are safe and unsafe. I found this very helpful.
This is a very interesting problem because it looks harder than it actually is. On paper, I worked through a bunch of games with small numbers of cakes until I saw how bigger games can be reduced to smaller games. That led to a simple strategy.
Thanks, this was really fun. The extra rule (no repeating opponent's moves) made this a lot more challenging than the version of this problem I've come across before. I had to build a solver for the whole game (which turned out to be too slow to pass the submission test cases) and use that to find a pattern I could use to build a simple solution. Great kata.
I would really enjoy a kata that involved a minimax strategy. It's been a while since I've worked on any problem with minimax.
This was a fun kata. It has a very simple solution that takes a bit of exploration to come to.