5 kyu
Josephus Survivor
4,245 of 16,827GiacomoSorbi
Loading description...
Mathematics
Combinatorics
Algorithms
Lists
Arrays
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.
This comment has been hidden.
Does anyone know what numbers they use for the final test at the end that keeps timing out?
In Python, both
nandkcan go up to 5000.That would be odd, because for this kata I wrote an algorithm that processes 5000 and under very quickly. However, when I submit my algorithm, the server times out. I believe they are using numbers upward of 1,000,000
As I said, all inputs are below 5000. However, your solution does seem to be too slow: for some inputs it works well, for many inputs it seems to take 300-800ms, and for some very unfavorable inputs like
n=4771,k=4331orn=4703,k=4744it seems to run for ~1.5s. Considering that there is 40 random tests, it seems that your solution is very likely to time out.I see. Quick question, I didn't submit any solution for this kata, so how exactly are you seeing if code is slow or not?
There is this mechanism which sometimes, under some circumstances, allows users to see the most recently attempted solution of another user. It is somewhat buggy and does not work always, but I was able to see one of your solutions, copy it, and test it.
This comment has been hidden.
The kata description says we can assume n>=1, but random test cases are sometimes generating n=0.
You need to mention the language you used
I was using Java
I have passed all the assertions, but I just can't understand what is meant by "Should work for random inputs too". I simply don't get it, call me newbie but please give me a hint... These are not other types, not negative n. What is it then??????
It means two things:
This needs to support a newer version of F#. Important (efficient) List functions and operations are missing (or crash) in the ancient version of F# that is supported. That means I have to fall-back to older functions that are many orders of magnitude slower and cause the submission tests to time out. Like others here, I'm opposed to a purely math solution being the only option.
This comment has been hidden.
For clarity, the ones I mention taking 3-4 seconds are the given tests on the webpage, these ones in this case: import Test.Hspec import Test.QuickCheck
import Josephus (josephus)
spec :: Spec spec = do describe "josephus" $ do it "works with integers" $ do josephus [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 1
shouldBe[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] josephus [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 2shouldBe[2, 4, 6, 8, 10, 3, 7, 1, 9, 5]And sorry about the code formatting, not sure what the delimeters are here, please let me know and I'll edit
Execution Timed Out (12000 ms)error is my code wromg im newbie
Not a kata issue.
Hint: Usually you get Execution Timed Out error when your code ran too slow, or when there is an infinite loop somewhere in your code.
got it! thanks!
Python fork
josephus_survivor(7,3) => means 7 people in a circle;) to be more language agnostic.
It passes all the sample tests in my IDE, but times out here. How could I optimize the performance of my method? I create an ArrayList and iterate through it removing elements until only one is left. I have an inkling that it's a math thing. Not my strongest suit
This algorithm might work, but you need a better data structure. Removing from an
ArrayListis relatively expensive, there are collections which will suit this task better.Or you can research for a math approach, but I think yours should work too, just takes much more memory than math one.
I was thinking you may be referring to a LinkedList, but I tested it, and its performance is worse than ArrayList's
I do mean LinkedList, and if it's slow it's possible it's still not used by you correctly. It can be difficult to tell without seeing your code. But I did not try to solve the kata with LinkedList so I dont guarantee it 100% works. I would expect it to, but I went with a math approach for my solution.
In C# I keep running into an issue where index is out of range. I suspect that something is wrong with my code or CodeWars itself has the issue. The size of the list had a count of 1. I'm accessing it at list[0] which should still be inbounds. However, it keeps saying my answer is out of bounds.
I'm able to place inside of a virtual C# simulator and it gets all of the correct answers with the algorithm in place. Not sure why it breaks in here.
Not a kata issue. Your code fails at this line
for the case below ~~
Obviously, trying to access index 18 from [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is impossible ^^
Fun challenge. For anyone whose solution times out, I would recommend rethinking your algorithm. It's tempting to think that you need to constantly iterate over each element of the array, but you actually don't.
I really dislike this kind of Kata. It's trivial to solve programmatically, but the programmatical solution is prevented through absurdly large test cases and hard-capped computation time. Instead, the solution is to calculate it. This isn't mathwars, this is codewars. Why is this flagged as an algorithm kata when the only "algorithm" is to implement a math formula that someone else came up with?
Choosing the right algorithm to use is part of a programmer's work. You've been warned at the end about the numbers being large. Nobody forces you to solve this kata, you can pass from it and solve the other one.
I know perfectly well what the work of a programmer entails. I'm saying that I don't like this kind of kata, because it's not actually a programming challenge. You can't even create your own algorithm to solve the issue, because the test cases really only allow for a super optimized solution. Either you're a mathematician, or you Google the solution and copy over the code.
Nothing about this is fun. It requires no creative problem solving, it doesn't reward trial and error nudging towards a good solution, and you don't actually learn anything from solving it -- it's just a hypothetical college math problem presented as a programming challenge. At least remove the algorithm tag and show it's just a mathematics kata.
I've created a solution that uses some loops and it worked just fine. It's in Javascript and ported it to Python where it worked fine too, maybe other languages behave different? That you couldn't find an algorithmic solution doesn't mean it doesn't exist. If you're curious about what it is, click
View Solutionunder this post.I've worked on it in Python. Tried my own version(s), timed out, googled around, and even the neat solutions on Stackoverflow either time out or have too many recursions. It's a 5 kyu challenge; that seems a bit harsh. Maybe JavaScript runs faster or something, I dunno, but I did not manage to get any programmatical solution to work, and I just don't want to just implement the formula off Wikipedia.
Have you seen my solution?
No; I haven't completed it yet, and I don't want to forfeit eligability. Maybe I'll change my mind about it later and try it again.
Well, then know there are algorithmic solutions that work. It's not a math only kata.
I think that is the programming part here, discovering the math and then implementing it. Looking at the wikipedia page, you're not going to reinvent that through trial and error.
The formula given is a recursive one, which will break, so your programming challenge is how do you make it non-recursive.
I see for PowerShell: 14 of 11,796 Is it possible to pass this kata in PS?
When you see these numbers, the 2nd is the total number of solves shared across all languages and the first is the number of solves in your language (PowerShell). So there have been 14 people solving this kata in PS, while - for example - 2958 in Python.
edit - I scrolled down to find the author of the PowerShell translation but it seems the user has deleted their profile:
https://www.codewars.com/kata/555624b601231dc7a400017a/discuss#5dd0a63797512c001dc87f0b
since it's a niche language, if you don't get a PowerShell user to help you on here your best bet would be to check the Codewars discord if you think there's a problem with the translation.
Wow. Really tough (took me 3 hours? C# pro(programming for living :) ) who programming for 1,5y from zero). Pretty practice for processing of edge cases.
Would be interesting, do more performance targeted version. That is what I would be scared by with my solution :D
idk how to optimise my code. Did by myself first. then by internet and there are no suitable solutions. Can smn help?
What could be wrong generally
Good luck, it is easier than it seems to be.
so im very annoyed my code passes all 38 tests, and times out on the very last one: josephusSurvivor(4687, 4892) man this is unfair :D no clue how to optimize rip
My code also timed out…… So sad
See my comment above for user noqwA (I hope moderator will not find it somehow inappropriate). Are there some tips.
Generally do NOT! do list of n elements - n times :D. Technically you not need to iterate more time than the "rest" of those numbers what you have.
So n = 7. First you iterate 7 times, secondly 6 times, ... because one number is each iteration removed.
What's up with these college boy math problems? How about a little creativity?
how to know which number is taken out ???is it random?
Read the instructions again, the second argument is the steps value you should use.
Every "k" number. (Be aware, it is not index, by itself! At the end of line, somehow you must move it back to right place at left side - I know dumbly described, but I do not know if I can here give more than small hints. If not marked as spoiler - what you will not see, if not completed :D ...)
e.g. n7 k3 (first sample test) = you have 1,2,3,4,5,6,7. First you remove third position, what is number 3. Then again 3rd position from their, so skip number 4,5 and remove the 3rd in row what is 6. Then again third - you skip 6, move back to begin, skip 1 and remove number 2 ... and some magic and you have it algorithmized :D
COBOL translation updated to new tests framework.
looks good, can be approved
Approved
COBOL translation kumited.
Thanks for translating :)
ofc :)
The first time we are to use a loop in COBOL \o/ exciting times boys!
Lucky you. I was excited at first, at last reach 7 kyu in Cobol! I thought. I searched. I had a peek at the solution reference. I renounced. :(
I would suggest that you do some 8 kyus to reach 7 kyu, by now dfhwze, me and elfein have been at it for month plus so kinda more used to this.
Also don't give up (really need more people using COBOL)
<3
If you know Josephus Permutation, it becomes easy ~
mm dont understand this list 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
I return 7, it shoulkd equal 10...dont see why
We neither if you don't tell the value of the other argument.
7,3
If the arguments are 7 and 3, that's explained in the description.
The e-eye of the tig-uurr!
Ruby 3.0 should be enabled.
It is not a hard kata, but depending of the language you're using you can be lacking some Array/List facilities and will demand some thinking. I agree it's more of a mathwars kind of problem. I suggest you to write it down step by step with pen and paper if you want to spot some error on your reasoning.
what is test6? how can I tell? I passed all of them except for it.
https://docs.codewars.com/training/troubleshooting/#print-input
This comment has been hidden.
My solution was to increase max recursion depth in python with
sys.setrecursionlimit(30000)is this cheating?
You should come up with a more efficient algo
This comment has been hidden.
Funny Kata! Arigatou Gozaimasu!
This kata has little to do with programming, and mostly to do with math. Respectfully, in my opinion, it should go on mathwars.com not codewars.com
Nope. It is one of those what MAY be solved by math, but not necessarily. See my solution. I am not math guy at all.
Need a test with consecutive numbers, like (19,20). I was able to get through all tests with a mistake in my code. Only cought it on Josephus Permutation.
In JavaScript I fail the test cases for the josephusSurvivor(14,2). It say expected 28, but got 13. The expected is actually outside the range of the input since I thought the max value would be 14, and from the test cases on the side 13 is the correct answer. Thought I would see if anyone else had a similar issue with the test cases.
You're reading the logs incorrectly, the error message is for (40,3), and there are more than 1500 completions in JS.
This comment has been hidden.
You have to avoid using recursion in your language because either:
I am using python..
Try printing something where you think it runs into infinite recursion, and if that indeed is the case, console buffer will fill quickly, and you should be able to see the point where it got stuck.
No it's not going into infinite recurssion and works fine when I run the code in local IDE on my computer.
And with which numbers are you testing it in your IDE?
I am checking with the same test case in my local IDE which shows error here. The test case is "josephus_survivor(1363,1310)" and it runs successfully on the local IDE and gives 951 as the result .
What errors? Maybe they're trying to tell you something... If it's recursion error, well.. maybe that's what it is.
How do you know that? Is that the last output you see before tests crash? Could you at least attempt the solution I proposed, instead of dismissing it outright? Maybe you'll spot something that wasn't obvious before.
Also it could be what @Chrono79 suggested, and using arrays may be too slow for some languages. (although looking at python tests, the numbers aren't that big)
In any case, the argument of tests working on your IDE and not here is something you see all the time, and without seeing your code, it's close to impossible to tell why it's failing. There's no magic with CW interpreter, but you may be using some external stuff that CW doesn't play nice with.
Case "josephus_survivor(1363,1310)" works fine in local IDE but not in CW. Meanwhile I found another test case "josephus_survivor(4450, 874)" and this time I found that local IDE also shows a similar error "maximum recursion depth exceeded while calling a Python object".
@B1ts--> "without seeing your code, it's close to impossible to tell why it's failing".
Should I share the code here so that you can know if I am doing any mistake.
You can paste your code here with proper markdown formatting (see this) and check 'Mark as having spoiler content' for your comment.
This comment has been hidden.
Thanks for sharing the code. The problem is that python has no tail recursion (AFAIK), and here it has a limit of around 1000 recursive calls before it crashes (but the tests go up to 5000). Funnily enough, I managed to get around this error with some quick googling of the error you received. So, you could try googling around and doing that, or rewriting your solution, so it requires less calls, or making it iterative ;-)
Thanks @B1ts, but I actually didn't had no idea that there might be any limit on number of times a function goes into recurssion.
Because your recursive calls aren't resolved until very end, they quickly fill up the call stack and crash the program, for a good reason :P Otherwise it could cause a buffer overflow.
You can use that, which is enough for the tests:
With 2000 you're never going to get into trouble. But there is a limit for a reason, and if you ever need 1,000,000 levels of recursion, you can't just increase the recursion limit, you'll have to rewrite the algorithm iteratively.
passes all tests but does not work.
Enjoyed Solving this Kata 😊
This comment has been hidden.
While it may be correct logic, it's terribly slow (it doesn't even pass sample tests in time), and random tests contain numbers of few thousand. You should look for a way to optimise those '++'s or look for another way to solve it.
@B1ts Yes I agree but it runs in under a second on other webpages, why does it timeout here after 12s?
I just created some more efficient code, now it works :)
This comment has been hidden.
delis anO(n)operation so your solution isO(n^2). You need a faster algorithm ;-)why does 2 get eliminated here why not 4? why does 7 get eliminated here why not 5? are the people chosen at random i though if input is 7,3 it means every third person is eliminated . Am i understanding it wrong ?
It's explained in the description. And, no, it's not random. They're in a circle. Maybe this is better (or not)
Try this one for better understanding (or not):
https://iguacel.github.io/josephus/
This comment has been hidden.
The PHP version seems to have an issue with the final test, I checked the time taken and output whats happening to ensure the checks are completed within the 12 second time frame, yet it still thinks my code is taking too long?
Codewars always takes a little longer than normal programmes.
I've tested your code and it passed at 5.5 second interval, closing.
This comment has been hidden.
Print the input?
What do you mean? Should I type my solution here?
No, use
print(n, k)in the editor. (assuming it's python)Looking for more tips. I solved by computing list, it works fine for test but not in attempt, due to lack of algorithem.
CFML, NASM, OCaml, and Prolog translations.
All approved, thanks :)
I think there is something wrong with this Kata, I am not able to choose python language. Whenever I am trying to choose Python, I does not response. What is the problem? I never wrote test cases before so There could be my own mistake also
should work now
This comment has been hidden.
This comment has been hidden.
The Haskell sample tests have the solution-method in them. Probably shouldn't!
fixed
C, Groovy, Kotlin, Nim, PowerShell, PureScript, Forth, Racket, Rust, Scala, and Swift translations.
This comment has been hidden.
Let me guess: altering the initial input? Or is it timing out for other reasons, then due to performance issues?
Such a nice kata Giacomo, although I failed 'Josephus Permutiations' and unlocked solutions, I learned from that and managed to solve this. Thanks for the amazing kata!
Thanks for your kind feedback :)
Factor translation
Approved :+1:
C++ translation Crystal translation Dart translation Julia translation R translation Reason translation TypeScript translation
I was faster :cool:
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Ruby? Well, I can still make the tests more intense: any suggestion?
This comment has been hidden.
GO Translation kumited - Please review and approve
Is there a flaw in the tests for PHP on this kata?
The first few sets of tests work and complete in under 0.3ms, but then the "testRandom" times out saying it took longer than 12 seconds to execute.
I can't imagine the random tests would take that much longer to run than all the others!
Not an issue. You need a faster algorithm ;-)
despite all other tests running in a fraction of a second?! Those "random" tests must be absolutely massive to take that long to run. Also, this is the second method I have tried to solve the kata, with the same outcome.
You can log the input using
echoto see how big the input size is.on the failed test, it doesnt output anything when I try to echo the inputs, it just gives the time out message :(
Oh, right, timeout causes that to happen.
In that case you can not run the loop if the input size is bigger than some number. It will fail fast, but you get to see the log.
Good theory, but unfortunately not the problem :/
Using the example tests, my code was able to determine that with 45,000 people and step size 2468, the final survivor would be 11,877. It did this in approx 10 seconds.
I added a clause at the start of the algorithm to quit if the number of people is above 20,000 or the step size is over 1,000 (for when running the "real" tests). This gave me an example of 1309 people and step size 2906. When I ran this as a test example, it completed in 5ms.
Another comment previously suggests the max limits would be around 5,000. If this is correct, my algorithm shouldn't be having a problem.
I can confirm you that the ceiling of the tests is
5000; 10 other people already solved it into PHP and I am not aware of any change in the server settings for this language: are you sure you cannot optimize?My code runs all of the following in under a second:
$this->assertEquals(4, josephus_survivor(7, 3)); $this->assertEquals(10, josephus_survivor(11, 19)); $this->assertEquals(1, josephus_survivor(1, 300)); $this->assertEquals(13, josephus_survivor(14, 2)); $this->assertEquals(100, josephus_survivor(100, 1)); $this->assertEquals(2639, josephus_survivor(5000, 30001)); $this->assertEquals(313, josephus_survivor(1309, 2906)); $this->assertEquals(1225, josephus_survivor(2335, 4990)); $this->assertEquals(474, josephus_survivor(5000, 4990));
The last 3 are examples from the real tests I extracted using echo's. I really don't think the code needs more optimisation :/
Is there a way I can send you the code to look at / test? This is something I feel this site is lacking... a way to get help checking over your code when you are stuck / having a problem.
I took a look at the PHP test code, and apparently random tests are ran 1000 times.
@GiacomoSorbi please change it to 40 times like the JS/Python/whatever other language version does ;-)
Done, thanks for the heads up!
Thanks for the fix. Funnily enough, the test now passes. with no problems.
I just noticed a contradiction between the Kata Description and the JavaScript random test cases when authoring the PHP translation to this Kata. The Description explicitly states:
But the value of
nin the JavaScript random tests seems to range from0to5000, both inclusive, if I read the code correctly. I originally wanted to edit the Kata myself to resolve this minor Issue but then realized that the edit button wasn't there.It is not there even after I approved your PHP translation?
I don't think so (the "Edit Kata" button should be to the left of "Add To Collection", right?), and are you sure you've approved my PHP translation to this Kata? ;) (FYI this Kata is "Josephus Survivor" not "Josephus Permutation")
My bad: as usual I got only a notification despite having multiple translations; approved now - does it change things for you?
Thanks for approving my translation, I can see the "Edit Kata" button now :D
PHP Translation Kumited - please carefully review and approve :D
This comment has been hidden.
In haskell translation module by default named Codewars.G964.Closet. Shold be Codewars.G964.Josephus. Thoughtful person can also easely find one possible solution :)
Fixed, cheers :)!
I've kumited an Elixir translation.
And I was not notified until now: approved, sorry for the delay!
This comment has been hidden.
This comment has been hidden.
No shortcut, no silver bullet for you, I fear: I would recommend you to start reading something like the famous CLRS and become more confident with both data structures and asymptotic analysis - that should cut it, but it will take a while - totally worth it ;)
I am having the same problem. Giacomo this is the book you are recommending correct? https://mitpress.mit.edu/books/introduction-algorithms
Precisely; mind you: it is rather hard core for a beginner, but if you manage to learn even just half of it, there will be very little left to fear in most interview you will do in your life ;)
use a recursive function---a function that calls itself as the return value.
can anyone provide an explanation for the currenlty available solutions(by g964, & unnamed)
Maybe you don't agree with the C# translation?
I don't agree with the notification system, mostly; feel free to work on a Clojure one, if you wish.
C# translation kumited, maybe Clojure to morrow if you agree.
Haskell translation kumited.
Both approved, thanks :)
This comment has been hidden.
Coffeescript translation kumited...
This comment has been hidden.
Which language do you think it is too easy to handle right now?
This comment has been hidden.
Enjoyable kata! I've written a Java translation if you want to take a look.
Thanks Angus: gladly approved; I am weak (to use an euphemism) in Java, but everything seemed ok; if not, anyone encountering problems could post here, so to notify the translator.
If you are interested, there is also the other "brother" Josephus kata waiting for a Java translation :)
This comment has been hidden.
This comment has been hidden.
I was considering the exact same option, but if a senior and much, much more skilled user like you had the thought too, to me it is pretty clear now how I should proceed.
The random range for
nis now 200 times more,kis 100 times more (the latter is mosty for show, but ok).Thanks to you for your kind words; I myself discovered this kind of permutation, recently when studying on the CLRS and then immediately I thought "now, that's something I want to bring on CW and see how people solve it" :)
Edit: for now it seems all the old solutions work the same, but we'll see about the new ones; any further suggestion to improve this kata is of course more than welcome :)
Nice Kata! This one was fun.
Glad you appreciated it and didn't expect to see someone completing it actually manipulating an array: interesting to see that even higher level languages can make it :)
In pre-set code, the function is named
josephus, whilejosephus_survivoris expected.Mh, I published it minutes ago and can't find the issue: maybe you got unlucky and got something I edited in seconds? Can you tell me the language, if it is not fixed yet :)?
Seems fine now, thanks!