Talk:Rep-string
Inspiration
The task was inspired by this question on stackoverflow. --Paddy3118 (talk) 19:45, 10 May 2013 (UTC)
Clarification
The task needs some clarifation. What is a repeat? Is string "10" itself repeated once? Is string "101" a repeat of "10"? When finding a repeated substring "if any", what's the preferred answer for "1111", is it "1" or "11", or even "111" and "1111"? There needs be a clear definition of the word "repeat", not just relying on whatever the first sample solution says, beause can be too arbitrary. --Ledrug (talk) 03:53, 12 May 2013 (UTC)
- I think I was most sloppy about "a series of ones and zeroes in a string": I meant a series of ones or zeroes. .. Oh wait .. Re-reading your question, repeat means "two or more times" which is in the description.
- Alternatively:
- Take a string of ones and zeroes X.
- Find out if there is at least one string Y of ones and/or zeroes that when repeated and truncated on the right to the same length as X is both equal to X and contains at least two repetitions of Y.
- If any valid Y is found then X is a rep-string.
- Hope this helps :-) --Paddy3118 (talk) 08:22, 12 May 2013 (UTC)
- To answer the question: Is string "101" a repeat of "10"? Yes. Repeated (twice, and then truncated) to the original length of three. -- Gerard Schildberger (talk) 07:22, 13 May 2013 (UTC)
- By the way, almost all programming examples have incorrect output, showing strings to be non-reps, whilest in fact, they are. -- Gerard Schildberger (talk) 07:22, 13 May 2013 (UTC)
- To get sane output, you need the restriction that the repeating unit must be no more than half of the length of the input string. Otherwise, the longest “repeating” unit is potentially the whole string, which is nuts. Any decision procedure for this needs to be able to reject a string as well as to find the repetition if it exists. (I'll update the task description momentarily.) –Donal Fellows (talk) 08:26, 13 May 2013 (UTC)
- By the way, almost all programming examples have incorrect output, showing strings to be non-reps, whilest in fact, they are. -- Gerard Schildberger (talk) 07:22, 13 May 2013 (UTC)
Reason for update request
Ledrug posted a great algorithm for Python that worked on the previous list of examples but would have failed on a string of all ones or all zeroes without a (very) minor tweak. I applied the tweak but thought that:
'11' '00'
Should added to the list of mandatory test strings. --Paddy3118 (talk) 04:51, 13 May 2013 (UTC)
- Why should these be nom-reps?? --Walterpachl (talk) 16:40, 13 May 2013 (UTC)