2 kyu
The position of a digital string in a infinite digital string
335 of 1,179myjinxin2015
Loading description...
Algorithms
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.
The kata is great but I'm having a hard time solving it, can anyone point me in the right direction?
Excellent kata!
I have a small remark. The description is not precise.
It is not just a combination. It is the infinite sequence of digits defined as the concatenation of the sequence of strings representing the consecutive numbers from 1 to infinity.
Good Morning!
Can anyone please explain the main problem? If I would find an index of a subsequence in a string I would use indexOf in C#. At the second case he said that I can create my own string if I can´t find this subsequence...Okay, the subsequence I searchd is at the first position, cause I created a string on my own. Seems I don´t understand the problem...
Greetings Noha
Did you just create any string you wanted? Well then it's wrong. The string (part of it) is given to you, but you have to expand it yourself. It's numbers from 1 to infinity, joined together in a string. Note that using this method, you will eventually run out of memory.
Okay...so far so good... But from where I get a new string?
This method is given in c# public static long findPosition(string str) {
}
The parameter is a string, not infinit. In the first test case I should find "456" in "...3456...". With IndexOf I get 4 for "456", but 3 expect...Why? "...3456..." as parameter is a fixed string, not an infinit string... In the next testcase for the given string "...444546..." it should return position 79. 79 for a string with a Length of 12??
This makes no sense in C#...What have I missunderstood?
Greetings Noha
You misunderstood the problem.
The "needle" string is given to you as the argument
str. The "haystack" string is not given to you as an explicit value, but it is fixed, has a predetermined, well known form: it's a string created by concatenation of all narural numbers. It starts with"12345678910111213"and continues up to infinity, or, if you prefer, as long as you need to find in it all numbers given to you as inputs.As said above, the
indexOfwill not work well for this problem, because the haystack is very, very, very large. If you want to, you can try to create it withstring.Join("", Enumerable.Range(1, Infinity)), which, obviously, will not work, because there is not enough memory to build such a large string (you can replace theInfinitywith a sufficiently large numeric value, but it will be still too much to build such string).The whole trick to this difficult task is to not build the haystack, but to exploit its well known structure and find the answer without building the long string.
Now I understand the problem, I didn´t noticed that the number string grows like [1,2,3,...,inf]. Okay, this seems manageable... I have a few ideas... Thanks for your request and help!
brainstroming. lol.
any ideas so far? I feel like training an AI model to try find the sequence would be easier that brute forcing it lol
Someone please kindly tell me what article should I read to help me solve this kata.Thank you all. Onegai, Sensei
Really nice kata, I really underestimated it and thought people are joking about edge cases, but they are not joking and I spend few days having fun solving it, this is the most brainstorming kata I've ever solved, thank you!
Also this kata is more difficult than 1 kyu katas that I solved, so it's either this kata is underrated or those katas are overrated.
This comment has been hidden.
Resolving: Not a kata suggestion
Bravo.
This comment has been hidden.
You are not correct. There is always only one number that is the first appearance
Incredible kata. It took me so long to find the solution. At first, there was an attempt to cover all the corner cases, which was huge. But then...
Execution Timed Out (12000 ms) :/
If you are trying to make an actual string up to the number, this won't work. :)
I really enjoyed this kata in the beginning, but with all these corner cases, it became a bit of a hazzle. Nice idea though, thank you!
The idea is simple but there are so many corner cases to consider. Thanks to the given samples covering nearly all corner cases, or I wouldn't be able to solve this.
Every time i see @myjinxin2015 kata i know i will have a hard time to solve it, in the other hand i enjoy it alot.
One of the most interesting kata's. A very simple problem, yet so tricky to get right.
Shouldn't it be "The position of a digital string in a(n) infinite digital string" ?
This comment has been hidden.
I was pressing
attemptmultiple times to make sure my code isnt making any very rare mistakes, and I think I found a mistake in the c# translation author's solution. It thinks that the index of 4949 should be 18685 when its actually two less (18683) This is really rare and you can easily pass the random tests but i thought id mention it.Hi,
I tested 8 solutions in python/JS (most upvoted and users I trust about having a proper solution) and they all find 18685 for that input. Now,I'm not entirely sure which one of yours or the translator's solution found 18683 when I read your sentence. Could you clarify, plz?
This can be checked pretty easily:
k it was a brainfart
I have thought of a quicker algorithm but there are so many cases to consider and they are realy cumbersome! I can never think of all of them without the test cases. This is basically test-driven programming.
The hardest kata I've ever solved... It took 3 weeks with several hours a day. Each time I discovered a new case, it destroyed my previous work...
This comment has been hidden.
Haven't solved it yet, but seems like the
Early Bird Numbertheory would help.Let me know if you find anything useful using this theory. I dug through whole interwebs using these keywords and got nowhere.
"Champernowne constant" can also be useful term. But for me, it was not.
this might help
This comment has been hidden.
Not complex ?!
I mean the core concept is actually very neat (simple), the implementation might involve some tedious details though.
I do not agree. The concept itself is very complex. It is no coincidence that we find no trace of it in mathematical literature (while Champernowne and the early birds are discussed). In fact, we discover the complexity of the problem ... by solving it!
This comment has been hidden.
This kata is terrific because you can be very close to the solution without getting this solution...
This comment has been hidden.
The hardest I solved. We had the same approach ;)
Great kata! Getting the correct approach to solve it analytically didn't take that long but considering all the edge cases is pretty tedious. I don't even know if I managed to cover all of them.
Same as you, but I finally solved it after considering all the cases...
Came up with a technique to solve it analytically. It simple to explain informally but there are soooooo many subtleties :)
Lots of runtime errors.
I think there's a bug with the random tests in Haskell. The expected value and actual value that it gives seem to be flipped.
Corrected. Thank you for your feedback ;-)
Wonderful Kata! I managed to implement a correct algorithm but ... it takes way much more than 16 seconds to execute! Just as an example, this test "555899959741198" must give a result of "1686722738828503" ... that's a huge number, just only to iterate. I have to figure out something to make it super efficient, otherwise I will never manage to stay within the 16 seconds! Thanks for this Kata ... I hope I will manage to make it.
This comment has been hidden.
The task is formulated so easy, but I've spend about 5 hours to solve it. myjinxin2015, you've made excellent kata. Thank you!
Happy coding
^_^The task is formulated so easy, but I've spent about 5 hours to solve it. myjinxin2015, you've made excellent kata. Thank you!
myjinxin2015 great job. Very, very challenging and particular. Took me very long to solve it but was absolutely worth it.
Happy coding
^_^This comment has been hidden.
I managed the pass the shorter ones, but the ones with result being higher than 10^9 beats me in performance, it gets very slow (~45s). A hint for you: you don't have to track of the whole huge string, only the part you have to examine, and you have a limit for that.
Perhaps you can starting from this kata, which is simpler one: https://www.codewars.com/kata/challenge-fun-number-8-numbers-concatenation/discuss#5abccc77a88ee7496a0000cb
This comment has been hidden.
The most challening task is to be able to detect a pattern. If the string is split into smaller pieces and these pieces are consecutive to eachother you might have found a pattern. Once you have the pattern you can calculate the position of the first number of the pattern. I am trying to help without spoling the kata.
By the way, myjinxin2015, this is one of the mosy singular and challenging katas I have done. Congratulations. Keep it up!
This comment has been hidden.
Fixed
This comment has been hidden.
Thanks. Happy coding
^_^This comment has been hidden.
to think out a clever way is harder than coding out the way ;-)
I thought I had a way using Sieve and streams, but the way I translated it was too inefficient and I run out of time.
need some idea? ;-)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Don't worry, it took me 3 weeks ;)
This comment has been hidden.
Yes, but it doesn't help at all.
This comment has been hidden.
Okay. @Voile, If you saw this, Please add them. otherwise, I'll add them in tomorrow(now I'm on my bed)
@myjinxin2015
Have you added the extra edge cases? ;-)
oh no. completely forgot this.. so, plz..
Sorry, myjinxin, but your solution (JS) fails at all these edge cases ;-)
I'm going to comment out your solution and replace it with mine for now.
All added ;-)
Thank you :-)
Let me check JS.. EDIT: Funny part about leading zeros ;-)
I think there's a typo in the kata description.
it says:
It should be 79 instead of 76.
corrected, thx.
Thank you.
Thanks ;-)
This comment has been hidden.
except that 363773 is the index your solution output, not the sequence of digit your searching for... ;)
@Voile Why you changed the expected value of testcase
"040"to-1?"...400401..."if I'm right, this is a
assert_NOT_equalstest to invalidate wrong solutions or cheat ;)resolved ;-)
Java translation!
2*200, since I discovered with my python solution could fail on some particular edge cases===to==in the description (I thought it was more common to the different languages than===. Good?)Please, review!
thanks for your hard work ;-)
@Blind4Basics
I painstakingly added all the extra tests to all my languages. (That's what you get when you're responsible for all the translations in a kata ;-))
Oh, by the way, the
not equal to -1test was in the Python version because of a cheater a few days ago. It's not actually needed for the tests.Yeah, I suspected something like that. I was thinking that it wouldn't hurt to put it in the java implementation too. Sure I can delete it for Java? (I don't know how the cheat worked with python. Didn't see/serach that cheatting solution).
Damn... That means that my solution isn't valide anymore... So sad... ;)
This comment has been hidden.
Sorry, I haven't got a notice of this translation. Now it's approved ;-)
This comment has been hidden.
Which language? Thanks ;-)
Ah. Ruby. @Voile ;-)
Ah. Ruby. @Voile ;-)
All fixed.
(Because working with translations is a pain I directly edited the kata.)
@cyril-lemaire
By the way, I just found that your solution has a flaw ;-)
I've added some more test cases to expose the flaw in your solutions's logic. Time to refactor! ;-)
Ah... oh indeed the key tries to loop as much as possible without considering non looping solutions! Crap and here I thought my ugly patches had the work done x)
I should have kept the list of test cases that bugged me, maybe it'd been useful to add some, sorry about that :/ (PS: How do you notice such flaws?)
Well, I was editing my translations to fix a few things, and then I noticed your Ruby solution was invalidated. So I went to check what happened, and you know the rest ;-)
I see, well thanks for notifying me! I'll see to fix that tonight (and if I'm stuck on this kata for another 3 hours I guess that'd make it a 6 kyu fix? ;-))
:P
Thanks for another excellent kata,
@myjinxin2015, and props for the outstanding work on the test cases - it's very robust and accounts for all types of edge cases. 👍👍Thanks for your solution ;-)
@docgunthrop
Well, not so much, since apparently after exposing someone else's flaw in his solution your solution is invalidated as well! ;-)
Please try again and make your code even lengthier :P
(Trivia: It took me around 30 minutes to finish the kata. I guess that'd make it a
2kyu? ;-))Yes. It worth this ranking ;-) Thanks.
Took me... A lot longer. :(
30 mins, that long? I did it in like 15...
Approved
This comment has been hidden.
You misstyped the name of the function (it's called keepIncorrect and in test cases it's findPosition) :)
Uhh, no incorrect now :]