5 kyu
Can you get the loop ?
1,250 of 29,345Devouring
Loading description...
Algorithms
Linked Lists
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.
Seems broken for Kotlin. No Node implementation available. I like to code locally and not in the browser. Am I missing something?
I don't understand the Hash part. Am I allowed to use a HashMap or not?
The intention behind the task is to solve it without hashing. However, some languages do not block this, and if you can use HashMap in your language to solve the challenge, good for you! But you will miss an opportunity to learn a nice algorithm :)
This comment has been hidden.
This comment has been hidden.
It's broken in php.
$node->next()returns only the same object, which has nothing in it except thenextmethod. Literally. What should I do with it if the objects don't even differ from each other in any way and it falls into an endless cycle?The fact that objects have no attributs does not mean that they do not differ in any way form each other. They are different nodes, and you can easily check if they are the same, or different node.
The fact that nodes have no readable property does not make the kata broken.
i don't even know what this is about
find the answer was not too diffcult, solve the timeout problem was important! feel fun with this KATA
Hello, I need help. I use c++ and for self-checking I wrote the Node class with similar methods myself. The problem is that the tests are running correctly on my computer (when I type in test examples), but when I test the code here, it gives a completely different value. What could this be related to?
Anyone solved this Kata in php? I am struggling how to optain the value of a node.
You don't need the nodes' values. They might not even have values.
This comment has been hidden.
I'm kinda lost with the input format here. Looking at the test cases, I'm not really getting it. Is there like a ready-made object I should be using, or am I just missing something?
look more carefuly at the description : it mentions the method
getNext()to get the nextnode. So, in order to get the next node, you can donode = node.getNext().the
nodeobject is given as an argument, and is an instance of a custom class defined somewhere else. As the challenge require you don't modify these, it does not really matter what its implementation is.This comment has been hidden.
The Node class should be in the description, honestly it is hard to think of a solution without being able to access to Node value or something
It doesn't depend on using the node value. The values could all be identical. The nodes don't even need to store a value inside of them.
This comment has been hidden.
This comment has been hidden.
test said "don't mutate nodes". suggest test to ensure nodes are not mutated.
(I overrode the class in my solution, but it was probably outside the intent of the author)
How exactly to go about that probably depends a lot on the language.
I think the intention of the kata boils down to that the only way one should interact with a node is through next and identity comparison (is node A the same node as node B? yes/no)
Some languages (like haskell) can enforce that.
For python one would probably need to get a bit crazy and always return new objects on next so that they can't be tracked (remembered, specifically) in any way - but still have them comparable through
==. I then started looking at comparisons for js and started crying. why is this language still in use in the current year?the description doesn't bother to mention what the restrictions are, which I think is unfortunate. It would be good if they explicitly stated that you may do X and Y, instead of listing a few things that aren't allowed, which isn't all that helpful
it doesn't help that some translations (python, anyway) makes no attempt whatsoever at discouraging solutions that mark/remember nodes
the description explicitly says "do not mutate the nodes" which is actually one of the more common solutions in JavaScript since it's one of the quickest.
In JavaScript, it'd be simple enough to add a test with a light solution (say 5 loop) that verifys the nodes themselves haven't been altered.
even though there's always ways around it, a basic test would ensure that you know you're circumventing the intended solution.
This comment has been hidden.
i just stated an assumption based on what is written. that's then left for the author to answer or not.
but, i do appreciate the read.
The author hasn't been on Codewars for over 9 years, so I'm afraid you are left with just whoever cares enough about this kata enough 😅.
I do actually agree that a simple non-mutation check would be a nice improvement, but there is actually work being done on a solution which would solve the mutation problem and all the others at the same time, so adding the mutation checks on this kata might not be necessary soon anyway.
This comment has been hidden.
tyj
Why the hell is the Node class not in the description? It only makes mention of
node.next, but I have no idea how to access the value of the Node.Who says the nodes have a value at all? I believe it is intentional that we are given only limited information about the Node type, to show us that it can be solved without any additional information.
I also don't see how the value of the Node would help at all, regardless.
Aren't we supposed to use the value of the Node to identify those we've seen before?
No, a node is not identified by its value, there could be duplicate values in the chain (supposing nodes would hold comparable values) and the solution would not change.
This comment has been hidden.
You shoul tell us the concept, because many of us are lost in this kata!
Al final lo hiciste po!
This comment has been hidden.
Thing is, the general idea here is that nodes do not necessarily have to hold any values, and if they do, the values do not necessarily have to be unique. The important part is identity of nodes. The image does not mean to show that nodes hold values, and in many languages they don't. All what is needed to solve this problem is check of "is this node the same node as the other node" which is easy to do in languages with references, but in Haskell, translator decided to go with an implementation of
Eqfor nodes backed by an internal, non-public, and deliberately undocumented identifier. All what you can do, and all what is actually needed to solve the task, isnode1 == node2, which returnsTrueifnode1andnode2hold the same node, andFalseif not.I do not know if it is a good, idiomatic approach for Haskell. It might be, or might be not, no idea. But the idea is that all you need to know to solve the task is equality of nodes, and not values held by the nodes.
Yes, thanks for your reply, as far as I know a zipper or a tagging is an approach to create unique identifiers for nodes, but the problem was that I could not wrap my head around how to implement either one when the list contains a cycle. I get now that I should not have thought about the numbers inside nodes as values but as tagging(enumeration), but, by convention, is it not a value that goes inside the circle while it's representing a node? Anyway, it left me wondering, if those numbers were to represent values, how would I implement an identifier for a node(nodes are cycled by 'Tying the Knot'), that's something I will look into.
This comment has been hidden.
Your solution is not O(n). The
x not in arradds an additional O(n) factor to it, making it O(n^2).This comment has been hidden.
Having the code properly formatted would greatly help.
Yeah just fixed it a bit. Hope it helps better that way. Sorry for the trouble, didn't see right away how it was after I copied it.
This comment has been hidden.
This comment has been hidden.
The expected answer (see the sample tests when in doubt) is a number:
If it return 1, I get expected 1 to deeply equal 2. If it return 2, I get expected 2 to deeply equal 1. I'm logging the loop, so I know there's only one running.
Your current code is wrong and fails the second sample test, start over from scratch. Sometimes it helps.
This comment has been hidden.
I don't know in Kotlin but in C++ looks like the node doesn't have any value, all it has is the next node. You can see that when they are instantiating the nodes in the tests, they only set the next and that's all.
Scala translation
Fun challenge, learned something new
Learnt something new with this Kata, very cool, thanks!
Execution Timed Out with Random tests in JS
That's a problem with your code, not a kata issue:
Yes, I finally found! Sorry!
How did you fix this? Im confused because for me it just mentiones 3 passed test and random test timed out but it doesn't mention what exactly the random test was for me to debug the problem.
Random tests generate 100 test cases, each with a list which has 10-20k nodes in the initial, "prefix" part, and 10-20k nodes in the loop part. Your solution is able to handle 3-5 such tests before timing out.
just skip this if you're doing PHP, it makes no sense and it's just garbage
Do you mean to say this can't be done in PHP?
Because the fact that it's available in PHP tells us that it has been implemented in PHP, there are pre-determined and random unit tests in PHP, and that those have been completed.
This comment has been hidden.
Yes, there is. Your problem is the linear search.
Can you give a clue about what will I do.
hey why dont you keep a track of all node addresses, then when they start repeating break. But before you break allow just the current node that signalled "hey, am already on the list". That node is your head to the loop. NB: Just allow one node's address to repeat.
Hi man. I did do it like you said. But it gave time error. I already solved this kata. There is a very different solution without address list.
I think some random tests have too long lists like more than 8000 nodes. And the time given for testing process is out before the algorithm loops through the exisiting nodes.
Long lists are deliberate. You have to find a solution which does not time out with long lists.
This comment has been hidden.
>it pases the fixed tests with 8k nodes but times out with the random tests
ペイン
This comment has been hidden.
I think they should either decrease the number of nodes in some tests or increase the time given for testing process
The purpose of the code timing out is to help recognize inefficient code. If you are passing all of the other tests and timing out for some that means that there is a more efficient solution that should be used to solve the problem.
Time restriction is unfortunate, would be nice if I could verify that my logic is sound or how close my implementation is to meeting the time restriction - unfortunate reason to be unable to complete the kata when I wrote something that wasn't even egregious in time complexity.
What fix would you suggest? The required time complexity is a whole point of this task, so performance requirement is definitely going to stay. The kata is also tagged with the
performancetag, so a need for a performant solution is hinted quite directly. What would be a way expected by you to fix your issue?Not a kata issue, that's a problem with your code.
Two ideas:
#1 - Include words in the description that indicate this kata is a performance challenge. For users who come across this kata randomly (like myself) that would make it clear that performance is an important factor. Right now performance is not mentioned in the description body at all. Because of that, I was rather surprised when I failed the kata because the code did not execute quickly enough.
#2 - Provide greater completion detail for the "Random" category of the Attempt tests. For example, if I could see that my code passed for all except the 1 or 2 test cases with the largest node chains before timing out, I would feel better about making it more efficient to complete the kata. Right now I have no idea how close I am to completing it.
Thank you for your suggestions. Not all of them are possible to apply easily, but the kata description could mention performance requirements more explici, why not. Its late here now, but tomorrow I will try and add some note on performance to the description.
A word of advice tho: when attempting many 5kyu+ kata, its usually reasonable to expect performance requirements of some kind. The higher the rank, the more performant solution is usually needed.
It's tagged as PERFORMANCE already and tags are part of the description. Yours is a suggestion, not a kata issue.
@hobovsky: check this https://www.codewars.com/kata/52a89c2ea8ddc5547a000863/discuss#636cd96eefec7b0057026b6c you already proposed adding a note, but first you should check pending translations.
Oh, thank you for reminding me. I think I did go through the translations at some point, but I cannot remember exactly now what was the conclusion, so I have to re-check :)
I have a general question, does anyone know where the function getNext() is from and if it is possible to see the code for it or see if there are more functions available from that library?
In what language?
Anyway, in every language, the method to fetch a next node is provided by the kata itself. It's not provided by any library, it comes from the code of the kata.
Having said that, it should not be really relevant how
getNextlooks inside. Everything what's important is that the only operation avaialble on nodes is "get next node", and it's sufficient to solve the problem.just implement your own linked list
it is not provided by the Kata for PHP. no idea what Node is
In PHP, the
Nodeclass is more or less:All what is needed to oslve the kata is to know that class is named
Nodeand that it has the methodNode nextNode(). I will see how to make this clearer.Ok completely fluked this one
This comment has been hidden.
This comment has been hidden.
Hi, python user here. I'm totally lost on this, i'm not sure how i'm supposed to extract even a single value. I've read most things about linkedlists and sorts, but if i try something like node.next or something i can't even extract the value. Can someone help me how i'm supposed to even print a single value, that's all i need.
The node is an object so I don't think you can print it but you can try to put it in an array then print it so you can see the length
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Oh, and BTW it would be nice if the description mentioned that this is a performance related kata.
Solution given by you as an example consistently times out for me. I cannot get an O(n^2) solutions to work.
There were some old solutions visible on solution pages, because they did not get invalidated after update of tests. I re-verified them and most of them got invalidated and disappeared, but I could miss some.
I still plan to update Python and other languages to disable solutions with O(n) space complexity or which mutate nodes, but for now I have no good idea how. But time performance requirements and expected time complexity should be more or less consistent accross languages.
I added
performancetag. I will add a note in the description too, after reviewing, and eventually approving, pending translations.Thanks!
Nice kata =)
Interesting challenge, I tried a lot of approaches and failed alot before getting a solution that didn't time out. Would it be possible to leave the expected time and space complexity in the Kata description to make it clearer when beginning the Kata what is expected? Also, it is not obvious how high the random tests go but in python I pass the random tests as long as the tests dont go higher than node len(16500) which is not clear to me if I have a) actually beat the challenge and it's not optimised for python or b) lucked out with the random tests and didn't really beat it
Thank you vary much one more time! Its really great kata. In the begin I don
t understadt what you wont. But now I made solution I have little bit more exp. and skills in the write codding!This comment has been hidden.
I didnt have a chance to run your code, but just reading it it seems to have insufficient time complexity and is most probably too slow.
Expected approach is O(n) in time, and O(1) in space, while your solution seems to be O(n^2) in time and O(n) in space.
Just run your code and indeed it's just too slow. You'd have to find some more performant algorithm.
It would be also helpful if you used proper code formatting when posting code blocks :)
Resolving as not a kata issue.
Can anyone explain the terms of the assignment? It is more or less clear what should be at the output and it is not at all clear what is at the input. It is impossible to understand.
Your function gets the start node of a long chain of nodes. But somewhere this chain starts to loop. You should count and return the numbers of nodes that create the loop.
This comment has been hidden.
I was wondering when a first solution abusing this fact will appear. now i know :)
I failed in C# because of time outs. Then I limited the maximum amount of nodes to 1000 in the loop to see if I find the problem in the response with a return 0. It is expected to find over 700.000 nodes in a loop so I think we have time out issues with that.
I am not exactly sure what your test with
nodes.Count < 1000is trying to prove, but your code uses an inefficient approach which is expected to time out.Your solution being slow is not a kata issue.
Citation: "Thanks to shadchnev, I broke all of the methods from the Hash class." That means the Hashtable and GetHashCode won't work or is slowed down, right?
Solutions based on hashing are restricted in some languages, they are not in some others, what should be fixed.
In general, a performant solution to this problem does not require hashing, it can be solved in O(n) time and O(1) space.
Кто нибудь может нормально обьяснить условия задания? Более менее понятно, что должно быть на выходе и нифига непонятно что на входе. Ни на английском ни на рауукосм понять невозможно.
Hi - if you want people to help you please post in English in Discourse; most people are using it as 2nd language and it's not difficult to use automatic translator to ask simple questions.
To answer your question - please see this earlier detailled comment (you can try to autotranslate it, if that helps you better), while you wait for native speaker to reply otherwise.
https://www.codewars.com/kata/52a89c2ea8ddc5547a000863/discuss/python#62b889b62e87b00031333e60
Thank you very much! Earlier comment really better explain task.
You are welcome, glad it helps a bit! :+1:
C: the input structure should be
const-qualifiedAddressed with this fork, please verify.
approved
Why don't add a
void *field on the struct Node? I think it would help with the performanceIt would not really help, why would it?
Whole point of the kata is to find and use a performant algorithm. There exists one which is O(n) in time and O(1) in space and requires no additional pointers.
I think we could store a index on the pointer. But i gonna try find out that solution with complexity O(N) :)
Hello, My code pass all the tests, but fails the attempt with message "Execution timed out 12s" . Can anyone help me?
Then it doesn't pass all the tests, it passes all the tests until it times out. Either your code is too slow or it has an infinite loop.
This comment has been hidden.
Definitely the hardest kata I have done, and my poor solution wouldn't even work in the wild.
Some advice I would give - for the best solutions, the tail length does not matter. Just focus on determining the length of the loop.
I wanted to run this on my local machine, does anyone know what the class LoopDetector looks like please.
Thanks so much hobosky! Quick question if ya dont mind, where did you find this/did you write it yourself?
Just asking because I felt like I was missing some information for this kata, and this really helps me understand the class we are working with
This comment has been hidden.
That's a problem with your code, not a kata issue.:
It's failing with big loops.
I didn't expect such big loops. Thank you)
Hi can someone please explain what the tail represents in this problem
"tail" is this chain of nodes "hanging" from the loop.
There were a couple of complaints already about the wording, so I will think how to improve it.
Could you please check this update and tell me if description is better? https://www.codewars.com/kumite/633319f6defafd237eec228e?sel=633319f6defafd237eec228e
Thanks!
I got "Maximum call stack exceeded" error in JavaScript. I use Set in my solution. I passed all tests, but fail at attempt
Perhaps because of my poor English, I don’t understand at all what is required of me in this kata. :/
Please, can someone help me to understand problem of this kata. And, yeah, if you know russian language it would be more clearer for me. Thanks!
Вот статья на вики по поводу linked list - Связный список
В данной задаче у тебя есть связный список, состоящий из узлов (node), каждый из которых по сущности объект с указателем на следующий узел. Чтобы посмотреть следующий узел, ты можешь либо использовать синтаксис node.next или node.getNext(). Обрати внимание, что по условиям этой задачи связный список всегда содержит начальный узел (tail) и цикл (loop). Суть задания - пройтись по связному списку и вычислить длину цикла (когда твой текущий узел будет указывать на уже посещенный).
// const A = new Node(), B = new Node();
// A.setNext(B), B.setNext(A);
// assert.deepEqual(loop_size(A), 2);
В данном тесте длина цикла равна 2, т.к. A -> B -> A (цикл состоит из двух узлов)
// const A = new Node(), B = new Node(), C = new Node();
// A.setNext(B), B.setNext(C), C.setNext(C);
// assert.deepEqual(loop_size(A), 1);
В данном тесте длина цикла равна 1, т.к. A -> B -> C -> C (узел C указывает сам на себя, цикл состоит из одного узла)
Надеюсь такое объяснение поможет тебе лучше понять данную задачу.
Спасибо за помощь!
I got the tests to pass, but the "attempt" tests are too difficult to debug at 6k loop size. Anyone have suggestions or tips?
This comment has been hidden.
This comment has been hidden.
It looks that you fail a test with a single node pointing to itself.
Also please note that you should not modify existing nodes.
node.visited = trueis not something you need, and Id have to check if tests verify whether nodes are not modified. Tests should fail when you change nodes.You're right, I missed the note. Thank you very much
Really not easy to understand what's the problem. Could you plz explain more, for better understand.
It's impossible to answer your "question" since you don't make it clear what you don't understand - for example, here is the first paragraph from Wikipedia article about linked lists:
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence.
Do you understand all of the words/concepts in this small paragraph? If not, then you need to read more.
If you do understand all the concepts, then let me try to rephrase this kata:
Referring to the illustration, if you start at node A and only use the
node.nextattribute, you will visit - in order - B then C then 1 then 2 then 3 .... then 10 then 11 then 12 then 1 aha!! we have reached a node, 1, that we have already visited before. In other words, our linked list contains a loop. The loop is of size 12 since it begins at node #1 and goes all the way to node #12 before returning to node #1.Can you figure out a way to "measure" the size of such a loop (in the case, size = 12) in a general linked list, using only the "vist next node" operations (i.e.
node.nextin this kata) ?This comment has been hidden.
I didn't understand, what exact problem I have to solve?
The task is explained in the description. If you don't understand it, you are most likely not able to solve it at the moment. I advice you to get more familiarized with linked lists solving some amount of easier katas related with this data structure.
No need to write to me arrogantly. Write only to the point. You need to play Sherlock Holmes somewhere else please.
Me give linked list. You find how big loop. You use node.next attribute only.
akar-0 was trying to help you and he just wrote a cordial message and behaved in a civilised way as should anyone in comment sections.
This comment has been hidden.
The message is bad and tests need to be fixed a bit to make messages better.
But still your solution is not what is expected. You are not supposed to modify nodes. Your assignment
node.number = countshould not be there.I will try to fix tests to make messages clearer.
This comment has been hidden.
It's not how you ask for help.
This is how you ask for help: https://docs.codewars.com/training/troubleshooting#post-discourse
This comment has been hidden.
Please use a spoiler flag so that users who did not solve the kata cannot see it (I put the flag for you this time). Also, use markdown tags to format your code or it is not usage. Please refer to the documentation about this and more things: https://docs.codewars.com/training/troubleshooting/#post-discourse
The
currNode in achieved_nodeshas O(n) complexity and is placed inside of the main loop, effectively making your solution O(n^2).This comment has been hidden.
The description contains following:
Is this not sufficient?
No, it is not possible to run the tests locally in an IDE without the
Nodeclass.Oh sorry, I did not state I was trying to solve it in Java.
Nodealso implements a util method to generate the full StructureNode.createChain(a, b);Oh awesome, thanks a lot for your effort!
This comment has been hidden.
Please use a spoiler flag. I see you solved the kata so I assume you actually don't need help anymore.
This comment has been hidden.
Randomly passed a code that should be too slow.
This comment has been hidden.
Unfortunately, I cannot reproduce your issue and tests in Java seem to work correctly for me. Could you share your code so we could see what could be the issue?
no answer from OP, closing
i'm very confused, in some test cases count the self reference as 1 like A -> A, but in other cases the self reference is ignored like A -> B -> C -> C (the test case expect 1 :s), I don't catch the logic
you need to specify what language you are using along with your code with the spoiler flag to get help
i can't give you any help other than to refer some algorithms and reread the description
python
by me also too is the same problem in JavaScript
It doesn't matter for a solution, but the description might be misleading for a lot of people since in some cases node == node.next.
How exactly is this confusing? Such situation happens when the loop consists just of a single node. Do you mean that such tiny loops can be confusing?
What exactly is a tail in the case of
node == node.next, is there some 'tail' that points to anodethat this functions starts with? Or are we always starting at the start of a linked list?. If so how many elements has a tail in the case ofnode == node.nextand how many has a loop? Well from the solution the amount of elelemtns in this loop is 1, therefore tail has 0 elements, so is there always a so called tail?Also starting Node A (picture) is a head of a linked list so how it is a part of a 'tail' which from what I understand should refere to a end of a linked list (null, None etc.) in this case the linked list has no end- therefore there is no tail.
So probably the confusion comes from wording used by kata description. You read "tail" as a tail of a list (i.e. its last node), while description means the tail as "this loose end hanging out of the circular loop". I thought the image would be explanatory enough, but apparently it is not. Another potentially confusing thing is that description says that there's always a tail, while in some cases it's possible to have only a loop, without a tail.
I will think how to make the description less confusing, and if you have any proposal for wording, let me know.
Very good kata to practice with pointers and references! Thank you)
This comment has been hidden.
duplicate of this issue (no sample tests in Ruby)
I had to lookup an algorithm for this, a mind bender for sure
I cannot get the values in JS for some reason, so I don't understand exactly what I have to do :S
This comment has been hidden.
I am pretty certain that C tests are rather OK. You could share your code so we could look for some problems with it.
Does your solution return correct answers for two consecutive invocations, one after another? I guess your problem could have something to do with some stale state passed between test cases, but its difficult to tell without seeing the code.
This comment has been hidden.
Gah, what an overlook... I just forgot to add new element in
push_back_darrayin case of reallocation.So, is the issue resolved?
The issue is resolved, but my solution didn't fit in time limits. Now i see why XD.
(Python) Could someone point me to a source explaining exactly the thing this kata calls "nodes"?
Honestly, I have no idea what these "nodes" even are, Spyder doesn't recognize the "Node()" function as a name, There's this tutorial: https://www.tutorialspoint.com/python/python_nodes.htm which suggests it's just when you make a class yourself and put in attributes that point to other attributes, in a very general sense. Searching on this site: https://docs.python.org/3/search.html?q=nodes doesn't give me any results that seem to be what I'm looking for. And so on...
Really, it seems I can only find talk about "nodes" in python that mean very different things depending on context and nothing like "The Python Nodes" which is what this kata seems to take for granted.
Search for single linked lists.
See https://en.wikipedia.org/wiki/Node_(computer_science).
As for "why don't we speak 'Node' much when using python", I would suggest u read a similar question on so, it answered my similar concern.
Be very careful with the time complexity. I added a null check and because of that the maximum time has been exceeded.
this looks interesting
This comment has been hidden.
You have to find length of a loop in a list of nodes.
This comment has been hidden.
Javascript. Yesterday it shows "Out of time" but today it's "Max buffer size 1,5 mb" on second test. What data in second test?
On attempt: "Expected 9983 got undefined". You're serious? It's too many
I think its not enough :)
My code pass the first test, but in the second one it gives me passed out time. It might be that my code is not doing the solution in a proper way, but I also think that maybe the test cases are wrong.
Same thing here; passes the sample tests, but when I want to "submit", it "times out"... ...On the other hand, I must admit I coded it "in a rush" and in the most "obvious/naive/straightforward" way (I was even surprised to see that my "very first attempt" immediatly passed the sample tests); so there might possibly be a way to "make the code more efficient"... (It seems quite likely, as the "issue" seems to have been reported many times; and while those people's code is hidden, the replies state that tey weren't "efficient enough", so...)
(Yeah, now I'm thinking of it, there seems to be an obvious way to make the code more efficient: I'm gonna try it :) ) EDIT: LOL: in fact, it wasn't even necessary to do try the "complex/subtle/far-fetched" thing: I simply did the "little stpd trick" that had previously come to my mind, but which I had rejected thinking "nah this would be too stpd xD" ==> but that thing actually worked (to my biggest surprise) RE-EDIT: Now I'm seeing the solutions: I probably should have done the "subtle trick" rather than the "barbaric one" I used... ==> The highest rated solutions use that "trick" I had though of, but was too lazy to implement (as the "barbaric trick" just worked)... But apparently, "something" must have changed since the creation of this Kata: surprisingly, it seems like most submitted solutions simply consist in the "obvious algorithm" with "no trick at all", and apparently, they didn't experience "Time Out"...
Something is wrong (C). I get correct values for FourNodesWithLoopSize3, NoTail and TinyLoop on my PC, but these tests fail here for some reason...
The C version of the kata seems to be OK.
I think something is wrong with your solution.
Thanks! I'll give it another go.
This comment has been hidden.
Try another kata ;-)
You need to learn data structures, specifically LinkedList. Look for a course online, choosing a data structure to solve a problem is usually the most crucial step :)
C#
Im stopping for now as obviously Im missing something. My tests pass but I get a time out at the actual attempt. I'm using a single linear loop to go through all of the nodes, adding them to a List and checking if the current node I am at is present in the list. If present, It means I have looped through all of them, so then I just return the count - the index of the current node. I guess it should have a simpler solution judging by some of the comments in the Discussion but Im stuck for now, will come back to it later. I dont really see how you can figure this out without looping through all the nodes, because you only have node.next, and nothing else to indicate what text or something this node has (Judging by the image, they should have some text in them), I tried using the node itself, text, Text, GetText, value, Value, but none seem to give me any values. I also tried using reflection to print out the properties and also got only .next.
it seems you have more than one problem with your approach:
I suggest doing some more research (i.e. googling) and looking for some loop detection algorithms. you will definitely find something.
@hobovsky
Thanks for the suggestion. Its actually what I did and it helped me solve the problem. I read about the problem and the theory behind the solution, after looking at some different algorithms for that I wrote down one I particularly liked and after understanding how and why it worked I used it to solve the problem and was actually quite amazed at how inefficient I had been approaching the problem. My solution used to run at about 108. something ms on the basic tests, and the solution I submitted ran the same tests with a new one I made with 1 million cycles faster than that. Again, thanks for the suggestion and for future readers I really recommend reading up on this as it does make a lot of sense when it finally clicks
This comment has been hidden.
See this : https://docs.codewars.com/training/troubleshooting/
Nice Kata ;)
Using Ruby.
The the
Nodeclass is not in the description.When running "Test", I get an unexpected error:
Even when I tried with a very simple solution that's wrong but should not "break":
You get that error because you can't run tests. The author has configured the tests to show you how the tail and loop are created.
That said i'm confused as heck about what the Node even has. It doesn't seem to have a value available with
.valueso how we determine loop from tail I have no ideaInside "Sample Test" block after declaration of
create_chain_for_testmethod add these two lines:That is enough to make test run.
Rust translation ready for review. Fyi, I used the arena pattern because not leaking memory in reference cycles is really hard in a non garbage collected language.
hi, if I dont have the last element in the LinkedList (None) how can I solve this, any hints woyld be great. becuse we cant work wih node.value I will always get a prepended object (memeoryreference) wich dont give much. node will always show memoryreference and it will consider anything else but None, so how can I get the end of the linkedList? any hints?. should I recursive this?
You cannot get the end of the list, because there's no end. Nodes are connected in a loop, and there's no last node.
The fact that nodes are pointed by reference is helpful though. you can still compare references for equality, so
node1 == node2will betrueif both variables point to the same instance of a node. You can use this fact to find the loop.great explanation, thank you very much! Learned a lot of those tiny sentances.
There needs to be more of a description here than just briefly mentioning the two methods added as properties on the 'node' object argument. I have to console log just to clarify everything for myself. You have a node.setNext method that you didn't even mention in the description of this Kata. This is obviously crucial in solving this. Please update the description to include a clear picture of what your passing into the function as an argument.
The description explicitly states:
You do not need
node.setNext()nor should you use it. The only part of the interface that you need is mentioned in the description:node.next.Cheers.
No, it's not.
setNextis an implementation detail and not a part of the interface.getNext( )is all you need to solve the kata.Python new test framework should be used (Refer this & this for more detail)
Ruby 3.0 should be enabled (Refer this & this for more detail)
added for python
This comment has been hidden.
Maybe this way: you are given A as input node. You need to find out how many nodes is between node 1 and node 12 (inclusive), or between node 4 and node 3, or node 8 and node 7.
You do not need to determine what is the first node of the loop (i.e. node 1), but just how long the loop is.
its not even a value really. those "node" things are objects. every object stores the next object in the chain, nothing like ints or strings, just a single reference. in essence, you are completely correct, the loop could be really long and the tail part might end further that Z part.
Got the premise down. Able to do all of the established tests and up to 56 of the random tests... then it times out. Currently trying to optimize it.
you just need to find the first revisited node, it's as simple as that, and your code shouldn't time out if you get it right, since it's o(n)
I was storing each of the nodes and then iterating through the node list to find a repeat. I had to google other algorithms to use because iterating through a massive list to find a revisted node was taking too long. I wouldn't say "it's as simple as that." I understand that you need to find the first revisted node... but HOW you quickly find the first revisited node is the crux of the problem that I couldn't discover completely on my own without google algorithm help.
You got it though, congratulations!
for some reason I just couldn't get console.log() to work in Javascript. (Probably something really obvious). Had to use C++ instead. Otherwise a simple and fun Kata.
This comment has been hidden.
You can simply treat it as
It's all what is needed to solve the kata.
thank you!
This is a great kata! The obvious solution worked fine for me, but failed the efficiency test. After looking at some algoritms, found a much more efficient way to solve it :) Very satisfied with it.
This comment has been hidden.
Search for a famous algorithm to detect cycles ...
it's simpler than that, do some search and you'll find the idea to solve it. Also as a general tip, don't ever use mutable data types as default parameters. Instead do this: def foo(arg = None): if arg is None: arg = []
It seems like searching in list takes too long. Searching in unsorted list got O(n) complexity. And you are doing this search for every node, so there are n searches, which means that complexity of your solution is O(n^2). And I think they got test with the giant amount of nodes.
Also, as already mentioned that here before, you are using mutable type as default parameter. In this main will be empty only for the very first test. In the second test main will be containing all the nodes that have been added there in the first test. In the third test main will be containing all the nodes that have been added in the first test and then in the second test, and so on. That means that in the last test main will be containing all the nodes from all previous tests, the search will be extremely low.
This comment has been hidden.
Note on recursion is IMO not necessary. I think it's your task to know when recursion is a good tool, and when it's not. If you decide to use it, you should already know (or find out) if it's applicable to your problem, in your language, etc.
Recursion, just like every other tool, has its advantages and disadvantages. Here, the latter outweigh the former. You just picked the wrong tool for the job.
Pretty fun and surprised not to see my solution already proposed, finally I saw only loops
This comment has been hidden.
Hello, i have returned to this Kata and subsequently i must apologise for my impulsive critique. I simply didn't realize how it could be done because i am a bit new to Java algorithms. I did not really find this Kata too difficult, about as difficult as other 6th Kyu, but i will surely take my time to see other solutions and also JoJoSmith10 shared article which proved very interesting at face value.
Don't waste your time with this kata, it seems interesting, and with more intuition to the problem it could have been a pretty fun 6th kyu Kata. But you can find plenty more friendly Kata that cover the same subjects.
I really enjoyed this kata and solved in both java and python. I was looking forward to reading the article but was having trouble finding it. Could the link to "Dmitry's article" please be added to the problem statement (Kata description) since I had trouble finding it. I was able to find it thanks to user: gayanw who posted the link as: http://blog.ostermiller.org/find-loop-singly-linked-list
Thanks!
This comment has been hidden.
No indication is given on how to distinguish tail from loop.
I was a little annoyed with how easily this could be solved with recursion, but when you used recursion you run into an overflow error. This isn't the first problem that I've seen do this, but I think it limits the possible number of solutions.
Maybe it's a Python thing?
Having the same issue in javascript here
Recursion is simply not suitable for some problems because it's limited by their size. Recursion uses call stack, and memory assigned for a it is usually not very large and the stack cannot grow indefinitely, that's why large problems can overflow it. If you really want to use recursion, sometimes you need to redesign it in some way. "Simulate" it with an explicit, in-memory stack, take advantage of tail recursion (if possible), etc.
It's not a problem with the kata, its a flaw of the naive recursive approach.
WoW I made it. This Kata was easy but managing speed is very difficult. You need to keep your algo. very fast. I tried to rerun the program three times in order to catch the server required time.
Error: Cannot access protected property Node::$next
not an issue, a question. You're returning null/None/nil/whatever is the equivalent in PHP. (or just the wrong kind of data structure)
I have a question its different with this kata but does anybody know how to find the position where it starts connecting? When I was working on this kata this question pop in my head.
once you return to it you know that's where loops starts :)
Response received but no data was written to STDOUT or STDERR while submitting a solution in ruby.
hello i have a question i'm coding this kata on java and i would like to know we have to create the Node class our self if yes what will be the operation
No, Node class already exists ( I tried to cheat by creating one but, no way, it would be a duplicate => compilation error :-) ) but is not available to run tests on our beloved machine.
if you want to write in your own IDE just create abstract class with abstract method, then write in IDE and test in codewars :)
This comment has been hidden.
You are mutating the nodes by adding an
idproperty; the kata requires not to mutate the nodesMaybe I should start learning C++ since Python always shows timeout status in many katas on CodeWar :(
Python is ver slow compared to languages like C. My C attempts take a fraction of the time even though it follows the same general framework as the python equivalent. :)
you know what? Python slow
The description states 'don't mutate the nodes', but in python the simplest solution seems to include adding an attribute (e.g. 'visit_index') to each node while traversing the linked list. If adding such an attribute should not be done, there should be a test that checks that the nodes are not mutated.
Use id()
This comment has been hidden.
No, it's a problem with your code.
This comment has been hidden.
Python time restriction is too strict
Some katas require fast solutions some do not. This is not an issue.
im also getting time out. My tests are all passing, and i am only using one loop. ;(
happening to me too guess python is just a slow language
This comment has been hidden.
Because it's too slow.
Passing the tests but timing out on the actual attempt with python. (just using a stored list of visited nodes and checking back with each new node to see if the circle is joined)
I want to be able to read up and come back to this one after I've learned about it rather than just look at other's solutions.
I know there is likely a more efficient way. Can anyone tell me the search term I should be looking up to find the correct technique to make the code efficient enough to complete the kata?
This comment has been hidden.
Thank you kindly.
What was the suggestion?
I can't see the implementation of the Node class in PHP, so I'm not sure how to identify the node to check it. Is there some Node.ID attribute?
Good question. I am struggling also with the node check.
This comment has been hidden.
did you figure it out?
This comment has been hidden.
try this link :-https://imgur.com/Rc6RPT5
.
Now it's fixed. Thanks @G_kuldeep!
the image is no longer available
This comment has been hidden.
In haskell, attempting to run the code just results in "File name does not match module name".
This comment has been hidden.
The function in JavaScript is named
loop_size. According to Javascript conventions, it should followcamelCase, which means it should be calledloopSize.This comment has been hidden.
The picture is not loading (empty). Does anybody have a backup somewhere? I'm curious :)
why after using $node->hetNext() i gotted similar node?
python answer seems to be very slow, cant find proper solution
I'm unable to get anywhere on the JavaScript implementation. Can we please have a complete view of the Node class/object implementation? Neither node.next or node.getNext() appear to be doing anything. Also, the nodes have no values, as near as I can tell. Which could be the issue with trying to determine if the next are doing anything.
These nodes apparently have no values or identifying properties. I can't tell if my attempts to increment them is working at all. This description really needs more info on how to use these nodes.
In some languages you can get away with mutating the nodes, like in Python and PHP (maybe in some others too).
This comment has been hidden.
This comment has been hidden.
Image is alive, must be some issue on your side. Try this link instead.
Some content blocking policies for
httpcontent onhttpspages?I got home from work and can see it fine. So it was something with my protocol there. Thanks.
This comment has been hidden.
Not an issue. Your solution is inefficient.
thanks a lot. Your answer helps me a lot. I didn't consider efficiency before.
The Ruby solution almost cheating LOL.
This comment has been hidden.
it seems that the Hash class is actually overridden so that you cannot use it at all, in ruby. Meaning you're searching for another method. But that should effectively be in the description.
ah no, it's actually said at the end:
Ah, gotcha. I swappped out the Hash class for a list and it worked. Not sure why the OP decided to break the hash class but it definitely caused me a lot of confusion and headaches because I did not see that comment. OP should make it very obvious before deciding to completely remove one of the most core data structures in computer science. Things would have been way more clear if OP broke the methods by having them raise NotImplementedError or something.
Impossible, because the test framework uses hashes for some default arguments, so the exceptions are raised during the tests. Currently, it's silent because all the overriden method are returning
nil. I thought about putting a message to the console, but for the same reason, it showes itself during the test suite even for a valid solution. So... that will stay that way, unfortunately.I'm hitting brick wall with PHP.
I have O(n) complexity but it is still timing out. Has anyone solved this in PHP?
In C# I believe my solution complexity is O(n) and I still get a timout. Does that seem correct, can it be done faster than O(n)?
O(n)is an optimal solution. You're either running into an infinite loop or your algorithm is not inefficient enough.There is no implementation of the Node class so it is not possible to get the solution and test cases running in an IDE instead of using the CodeWars web GUI
Not an issue. Everything is preloaded and accessible after you complete the kata.
This comment has been hidden.
JavaScript sample tests are the default "TODO" tests from creating a new Kata.
I really struggled at first because of the lack of sample tests. I ended up just guessing based on comments that you could new Node() and passed that into loop_size in a test. Then console.logged it to see what I was actually dealing with. That gave me a look at the Node object. From there, the light bulbs started to go on, and I created this really ugly test. My first CW test! :-P
added sample tests :)
This comment has been hidden.
the picture explains very clearly how it is possible
Tried to solve this in Java and none of the usual methods of the Node class work. There is no wa to solve this without knowing how a Node is implemented
I have to agree. I'm a developer and I understand data structures but a node is one of the most abstract data types of them all. Without the interface somehow being exposed, or without one even being told what the public methods are here, I can see how code warriors could spend hours guessing as to what the operations to call on a node are to solve this problem. I think this Kata is an over simplistic one artificially made to be more difficult in providing the least information as possible about the ADT it wants you to work with. However, in this case I do believe that a little research goes a long way if one doesn't already have an understanding of what a node is and how to use it.
Are you kidding? The description explicitly says you can use
.getNext()to get the next node.This comment has been hidden.
Being unfamiliar with something != something is mysterious and can't be understood. This kata is very simple OOP + the simplest data structure; ideally you must be familiar with both, especially when you're doing a task which includes these concepts.
This comment has been hidden.
All nodes are different as all nodes are instantiated independently. If you don't want to search for the specific (classic) algorithm, you can simply go with a "store the nodes somewhere and check if I've encountered any of them already" approach (at least it worked for me in Python).
This is as much as I can tell without spoiling anything.
I tried exactly that in PHP but when you compare them they are identical, even the unique ID's I mentioned before. I just tried making every check I did strict and I did see different results but still can't get this. Think this may stay unsolved for quite a while
In any algorithm you choose there's a "compare 2 nodes for identity" part. You must be doing something wrong if all the nodes are identical for you.
Are you sure you're moving through the linked list correctly? If you are indeed stuck in place, you'll be comparing the node with itself, hence "they are identical".
@FArekkusu Adam is right this makes no sense. I still have no idea what to do. Heck I've never even heard of nodes in Python!
What do you expect if you don't know even the most foundational terma in CS? There is only so much spoonfeeding possible. We don't explain what every English word in the description means, for example.
Also, there is a thing called Google. Use it.
This comment has been hidden.
There are some pending translations, and the author is long gone, so could any power-user check them and approve them if they're ok? I would do it, but the languages of those translations I'm not familiar enough with (C, C++).
C and C++ are approved
This comment has been hidden.
rank changed to 5 kyu.
This comment has been hidden.
Just tested Python with my past solution and still works, maybe the problem is in your code?
me too,test is OK,but attempting timeout
I'd say it should be like 4 or even 5 kyu, not 3.
And please someone add a mention about immutable nodes to the task description (or at least mention it in test cases output). Now it's unclear and makes people hate.
note added to the description
tips : nodes immutable
description updated
Ruby version is broken.
this easy for 3kyu - 5kyu is more suitable
Why the hell is this a 3kyu? This is 5-6.
Old kata rankings are almost always overranked.
This comment has been hidden.
I really really stumbled until I checked the comments and saw people saying "don't modify the input". I think this should really be required text in the kata description!
This comment has been hidden.
This comment has been hidden.
Object equality does not even exist mathematically (or in pure functional languages like Haskell), so, no. "Equal value = equal node" should be good enough though.
The missing (and hence failing) sample tests and the comment "broke all of the methods from the Hash class" made me believe I cannot use Hash and Array to store the visited nodes.
This made me find a much simpler solution without storing.
I like it.
This comment has been hidden.
In PHP this was stupid simple (but only becouse you can change the object you test on)
C Translation Kumited
Many 4kyu katas are a lot harder than this 3kyu kata. My opinion is that this should be put at 5kyu.
rank updated
This comment has been hidden.
Description:
That's why it's 3 kyu, I think. The problem is that it isn't checked in Python.
Is the javascript Attempt broken? When I try the Attempt I get the following:
The instructions say nothing about implementing a start object or a setNext method, so I've neither called nor implemented either.Tip of advice do not modify the input.
python 2.7 code passes all tests but fails due to the timeout issues when I press Attempt
This comment has been hidden.
issue still there for pyton
it's not an issue, that's just your code that is wrong (3500 completions in python!)
Kotlin translation
PHP Translation Kumited - please carefully review and approve :D
I keep getting this error:
"Network Error
This error was caused due to an issue processing the web request, not because of an issue executing your code. You can retry the request."
without being able to edit or resumbit code.
I think I am just stuck in an infinite loop, but this isn't the usual error.
Why this kata was locked?
!?
I don't know anything about Nodes. Can someone give me a hint how should I start to solve this kata? I cannot get any fix starting point, not even understand the details... I was really surprised when read the "it should be a 5kyu or 6kyu, not a 3kyu" comments while I am unable to start it...
Hi, I had the same feelings when I started on CW and found this kata. If you don't know anything about classes and objects, begin there. If that part is good, check on "linked lists" and that should be good after that. Formally, a node is a
Nodeobject with two fields: a value and a successor. Here, the value has no interest and only the successor is needed, which you can access with the methodnode.getNext()(the exact call might depend on the language).Actually, I have finished this kata already. :) It was only the understanding of this task what got stuck me in the same place. I was searching for a complex task to solve, but figured out it is not that complex, just have to step back and look from another angle. After you realize the problem, the solution is not that hard. Thanks the reply btw :)
I think with a better description and an example or two, this could be bumped down to 4 or 5kyu. Nevertheless, was fun to do. :D
don't think the py version is too easy for kyu3 ??? also, i don't figure out how i can make a translation (really wantin' to make the C version )
I agree with most other comments that said the description needs to say that you can not modify the input. I was quite confused why my code wasn't working at first. But once I found that out, it all made sense. I suppose one could say that that's part of the kata, but if that's the case, then all these comments should be marked as spoilers. If not, then just put in the description.
I know absolutely nothing about nodes, yet I don't understand why this is 3 kyu. Nothing special, at least in Java.
The c# kata works fine and is very explenational but the javascript kata is very useless and doesn't even seem to work (using the exact same logic as C# kata)
I believe there's something wrong in C# - when I test my solution (run sample tests button), it passes, but when I try to solve kata (attempt button) I got timeout on first test - FourNodesWithLoopSize3. It finds loop correctly - it enters to if nicely, shows "3" as expected and it doesn't go any further, but for some reason I got timeout. Hardcoding "return 3" inside of the loop returns the same result.
You will need to optimise your code. For example, what is the big O lookup time for a C# List? Are there faster implementations?
That means you failed the next test. So look into that one instead :)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Don't mutate the input.
Nowhere does it say that you may not modify the input, e.g. adding properties. Also, the error messages you get give you no hint whatsoever that you are not allowed to modify the input.
That said, I solved it by adding a flag prop to the nodes, ad then doing a second sweep to remove the flags. So there's also nothing that keeps you from modifying it, as long as you put it back.
Not a bad problem, but it's way too easy for 3kyu. The only difficult thing about it is figuring out that you have to leave the input as it was.
I can log the right answers, but when I return them, I get simply "value is not what was expected" without any further information. This occurs for all but the first test.
whoops. I was modifying the input, which is a no-no.
It seems too easy for 3ku. Nice kata, anyway.
The javascript version appears to be calling the function twice, which leads to incorrect numbers regardless. Please fix this!
At least for the node version, it looks like it's calling my function twice (e.g., if my function is a single comment.log(), I see it twice). It returns 0 universally past the first case. I think it's broken.
This comment has been hidden.
if (answer) return answer;
I had this problem, but it was apparently because I was modifying the input. If you solve this kata without modifying the input, then you probabaly won't have this problem.
This comment has been hidden.
This comment has been hidden.
Why is there no report button to report hateful users that can't solve a puzzle nor even stay calm?
Don't mutate the input.
This comment has been hidden.
I still don't understand why mutating or not the input would be relevant to this. My first answer mutate the input, returned the right answer and I was getting “Value is not what was expected”. That's fine, but if I hardcode the return to the right answer it works, and the input is being mutated all the same. I even console.log a test to see if the result coming from the algorithm and the hardcoded version are the same, and they are, but only the hardcoded version is accepted as correct. Would anyone be bothered to explain why?
Would be nice to have the code of the Node class, to know what to expect and specifically what solution implement.
Haskell
That was fun!
Beside that it was totally ok to have test cases with a zero tail, I would recommend not to state that there is ALWAYS a tail and a loop.
This comment has been hidden.
Fixed
This comment has been hidden.
Seems like you're following bad practices if you're mutating an object passed to your function when that is not the function's purpose. The only time you should mutate an argument is when that is the explicit goal of the function.
Imagine calling the built-in min() function on a list, only to find that the function has removed all the items in the list except the minimum.
Would have been nice to know what "Node" class was being used for writing of the test in java.I usually do the exercises offline , but was not able to in this case
That allowed me to code offline. Pretty trivial.
Thanks
Does anyone else feel that this kata complexity (3 kuy) is overestimated and it actually deserves a lower ranking?
I agree, it is straightforward, no traps, should be 5kyu or even 6kyu...
rank updated
This comment has been hidden.
This was no challenge whatsoever, not sure why it's ranked 3 kyu? At the very least it's trivial to solve in java.
Simple in python as well. The nature of the problem seems straight forward in a language-independent sense.
it would be nice to add tests without loops
i agree, but it's too late now to make breaking changes to the specifications :/
Nice Kata! Will just leave couple of useful references to algorithms:
http://www.siafoo.net/algorithm/11
https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
It would have been helpfull to know in advance that the hashcode contract (Java) is broken on purpose.
the ruby version is broken. It's ignoring the results.
Don't mutate the input.
I have a problem in JavaScript
second test:
if i return 0: log 0 Expected 23 got 0 log 0 (not passed)
if i return loop size: log 23 log 0 (not passed)
tests starting from the second call function twice first time the returned value is correct, but function is called the second time and returned value becomes 0 and test doesnt get passed.
For some reason after getting a correct answer, starting from the 2nd test case, the function
loop_sizeis called again. Despite this fact the kata is solvable. I managed to override this probable bug by using global scope in addition to local.