last day (96 days later) » 

3:52 PM
1
A: Finding duplicate values in a single string of characters in r

JulianThe following code does exactly what you ask for. Try it with str_groups('1101101101'). It returns a list of 3-vectors. Note that the first triple is (1, 3, 4) because the character at the 10th position is also a 1. is1 <- function (d) identical(d, 1) str_groups <- function (s) { digits <- ...

 
This is really great. Thanks a lot Julian. This is amazing. You deserve much more than this bounty.
Also Julian, it will be great if you can give me some insights on reducing the complexity for the code? Thanks. :)
 
You're welcome. To be honest, I don't think the runtime complexity can be reduced, because the task inherently requires looking at the remainder of the list for every element in the list. The lines marked with ### already serve to avoid duplicate work, but the order of complexity remains quadratic. (Edit) You might be able to optimize this by first generating a list with the positions of all 1 digits. However, the code would become more complicated.
 
I was thinking on similar lines, like generate a list of all 1's and find all possible Arithmetic Progressions.
I tried doing this. str_groups('110110110110110'). I got 4 triplets. Now, I have a doubt. Two of the triplets that I got were, 1 3 5 and 1 6 3. Now, ` 1 3 5 ` corresponds to the position of 1 at 1 4 7 10 13 and ` 1 6 3 ` corresponds to the position of 1 at 1 7 13. So, they give the same information which appears to be redundant. Anyway we can remove this?
 
Yes. I have edited my answer to rule out such sub-patterns with larger intervals. The newly inserted code is marked with ##<.
 
I don't think it still works. Try running it str_groups('1101101101101101'). Two of the output comes out to be 1 3 6 and 4 6 3. By the first pattern, it is, 1 4 7 10 13 16 and by the second it is, 4 10 16 which again appears to be redundant.
 
3:52 PM
Good call. I have now edited the post again to cover those cases as well.
 
it is also missing out some of the patterns. See for yourself. str_groups('1111101010111111') . Gives only two triplets, 1 1 5 and 11 1 6. As you can see, the 1 is appearing at 5 7 9 11 as well. Therefore, there should be an additional triplet 5 2 4.
Hi Julian. I just wanted to say that, it ddoesn't work for some cases. For example, in this case as well, str_groups('1111111101010101010101') , it gives only one output as 1 1 8 and not the alternate 1 at the end of the string. It will be great if you can tell me.
 
Hi
 
Hey! Your edit's have been really fruitful. But I guess the original algorithm is missing out on some patterns.
 
I have just explained where the issue comes from in a comment on my answer, because I initially missed your invitation for the chat.
It has to do with the new addition (lines marked ##<) which is a bit over-eager filtering out sub-patterns with larger pitch.
I'm already working on a solution, please bear with me in the meanwhile. :P
 
Oh! Great. My bad. I might have missed your comment.
Not a problem Julian. :)
 
3:57 PM
If you find any more issues, don't hesitate to report them to me.
 
That's really nice of you. Thanks again. :)
 
(By the way, how do you start a chat room like this? I have never used this SO feature before.)
 
As the comments were increasing in the chat, the SO suggests that such kind of discussion be moved to chat.
A option comes below the add comment button, so as to maintain the brevity of the post. Otherwise, the comments extend too much in length at times.
 
So it's just offered automatically when the time is there. How convenient.
 
Precisely.
 
4:03 PM
This fix is going to take longer than the other ones, by the way. I have to re-think several parts of the algorithm.
 
Oh! Alright. Will be eagerly waiting for it. :)
 
 
2 hours later…
5:43 PM
Does this chat still work?
I have posted a new version that I hope does not contain any more faults
it finds more unique patterns in 1111101010111111 than you might expect. :-)
 
6:03 PM
Hey! Sorry for this. :)
 
np
 
Let me try. Thanks again. :)
 
Even if this isn't the final solution, at least the new algorithm is better designed and better written than the previous. :P
(You can get rid of the is1 function, by the way.)
 
Seems so as well. :D
 
I try to not be overly optimistic, still fuzz-testing. :P
 
6:13 PM
I am trying it right now on several examples. Seems perfect uptill now. :)
 
hm i'm afraid i found an issue
in 00111010111111111110, it reports (10, 4, 3) which is a subset of (9, 1, 11)
otherwise it does that one perfectly as well...
 
Oh! :(
Yup, it has been working well on the examples that I tried uptil now.
 
this simply shouldn't happen, the algorithm should already catch cases like this one... now checking what could cause this
 
Alright.
 
ah, found it :-)
now going to edit my answer again
done
(still testing)
 
6:27 PM
I also found one string in which the previous code gave an incorrect answer.
Let me try the new code.
It corrected the previous problem.
 
6:47 PM
I have tried 5 random strings with this new version and I didn't find a problem with any of them
I think it's entirely correct now
If you agree, I'll edit the post one more time to let future readers know that it is 100% correct.
 
It seems to be correct this time. Although, I am testing on several more right now to be sure.
 
I now realise there's still also a slight optimization possible.
 
Will it help in reducing the time?
 
Yes
(still quadratic, but with a lower constant factor)
although it might not be a big difference
 
And what can it be?
Have you already done it in the code posted?
 
7:01 PM
i'm still writing it
ok i have posted it
now we obviously have to check again whether it's correct :P
(although it should not have introduced new errors)
 
Hahaahah. :D
 
three random strings, no errors. I think it's OK.
 
7:18 PM
Nope, got an error.
 
damn
 
Try this: str_groups('0101010111101010111')
Shows, Error in while (index1[back] > len - 2 * pitch) { :
argument is of length zero
str_groups('01010101111010101111000')
For this as well, shows same error.
 
posted a fix, try again
 
Alright.
 
hm it will still happen if the string is only zeros
 
7:23 PM
Oh! But the above weren't completely zeroes.
Let's try this code now.
 
now that's fixed as well
 
Oh! Great. :)
Is it possible, that I show a default list() or something like that instead of the above error if the string contains all zeroes?
 
with my latest edit, that's exactly what happens
(you might have just missed it)
 
Might be. Let me try.
 
7:41 PM
If I may be so free to ask... what do you need this for?
 
My bad for not telling you already.
I am doing a voluntary project for the Red Cross Society in my area.
 
(I seemed to recall something like that but couldn't find it on the page anymore.)
 
They wanted me to help them with their data so that they can all the more effectively reach the needy. I willingly took it up.
It is in the, why I put this question on bounty area.
 
ahh, and that disappeared because you awarded my answer :P
 
And I really really want to thank you for all your help. Wouldn't have been possible without your constant help.
I really appreciate it.
 
7:44 PM
you're welcome
 
Seems this is the perfect answer. :)
 
the all-zeros now works without error too, right?
 
Yup, it does.
 
so, i still don't fully understand...
 
I hope, I don't but if I get some errors, I will post.
Yeah?
 
7:45 PM
where does the red cross get such data from and why do they need such patterns?
or is that sensitive information?
 
Naa, it is actually their data of how many they have helped uptill now. Pretty much yes. :_
*:)
And in what frequency, that happened.
 
ok, well i'm glad your job is voluntary. ;)
 
Me too. :)
If you don't mind me asking, you a research scholar?
 
i don't mind
 
Or a professor already ( seeing your knowledge ) :P
 
7:50 PM
what do you mean by a "research scholar"? a phd student? (i'm not a phd student)
i'm not a professor either
 
Oh! My bad. :\
Seeing your great knowledge, that came to my mind.
 
i'm sort-of a professional programmer and data analyst (as in getting paid to do such things), but to be honest i'm also still a masters student
(i'm not at all offended by your suggestions)
i have a lot of training and experience to rely on though
 
Oh! Great. I am still an undergrad. I aspire to be in this field though.
You did your Masters in Computer Science with focus in Data Analysis?
 
cognitive artificial intelligence, with one course in datamining, but i have a long history of hobbyist programming and computer science related courses
and i've had a job as a research data analyst
 
That is amazing.
 
7:54 PM
how about your study program?
 
I am doing my undergrad in Information Technology.
Wish to either get a job or will go for a Masters in CS with focus on Data Analytics.
 
i have about 12 years of programming experience, from all different sources
 
That's like greatttt.
You from States?
 
so as you gaze up to my formidable knowledge, just keep in mind that it's a matter of time until you'll be just as proficient ;)
no, netherlands
 
Oh! I recently went to Harvard, met some really nice people from Netherlands in the conference. :)
 
7:58 PM
that sounds interesting, what kind of conference was it?
 
It was an academic simulation of what happens in an actual Model United Nations.
That is, the Harvard Model United Nations. ( the oldest conference in the world ).
* in an actual session of the United Nations.
 
right, i was about to ask that :P
people on my secondary school went to the dutch MUN
so i heard about it previously
 
Oh! That's quite big as well.
I know it's too much to ask of you right now, but, can you please add some algorithm/explanation besides the code, so that, I can probably understand it at a faster rate?
 
i can, on the condition that the amount of explanatory text is less than the amount of code, and on the condition that you make very clear what kind of explanation you want :P
 
Absolutely. I don't want you to type again so much, that you did for the actual code.
Just a basic algorithm would do just fine. :)
 
8:05 PM
like, pseudocode?
 
Precisely.
 
ok, will do
 
Thanks a lot again. :)
 
you're welcome
 
You are a savior.
 
8:06 PM
that is too much honour :)
i keep this room as a favourite, so we can stay in touch
 
The amount of effort that you spent for me, you deserve it completely. Believe me. :)
 
ok, thanks
 
Absolutely. I really would like to. :)
 
see you around and good luck with the red cross stuff
 
Sure. Thanks again. :)
 
 
2 hours later…
10:20 PM
For your information, I have added the pseudocode to my answer.
 
10:47 PM
just found out i could draw your attention: @u
ahem, @user3797829
 

  last day (96 days later) »