Talk:Rep-string: Difference between revisions
→Draft statust: for a while longer? |
→Clarification: added a follow-up. -- ~~~~ |
||
Line 19: | Line 19: | ||
:::: Yes it is. Repeat "10" twice, then truncate to the original length (which is three), that yields "101". There is nothing in the task description that says the repeat string has to ''appear'' in the result string, as in the case when the string is replicated, then truncated to the original length. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:10, 13 May 2013 (UTC) |
:::: Yes it is. Repeat "10" twice, then truncate to the original length (which is three), that yields "101". There is nothing in the task description that says the repeat string has to ''appear'' in the result string, as in the case when the string is replicated, then truncated to the original length. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:10, 13 May 2013 (UTC) |
||
::::: The task description is not just the first paragraph; if you continue reading, it says the repeating group can't be longer than half the length, from which one may pretty easily infer the intended interpretation of the initial description, seems to me. --[[User:TimToady|TimToady]] ([[User talk:TimToady|talk]]) |
::::: The task description is not just the first paragraph; if you continue reading, it says the repeating group can't be longer than half the length, from which one may pretty easily infer the intended interpretation of the initial description, seems to me. --[[User:TimToady|TimToady]] ([[User talk:TimToady|talk]]) |
||
:::::: The task description was amended twice after I had entered the REXX version 2 example. With the latest task requirements, 101 isn't a rep-string. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:29, 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. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 07:22, 13 May 2013 (UTC) |
Revision as of 19:29, 13 May 2013
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)
- Yes it is. Repeat "10" twice, then truncate to the original length (which is three), that yields "101". There is nothing in the task description that says the repeat string has to appear in the result string, as in the case when the string is replicated, then truncated to the original length. -- Gerard Schildberger (talk) 19:10, 13 May 2013 (UTC)
- The task description was amended twice after I had entered the REXX version 2 example. With the latest task requirements, 101 isn't a rep-string. -- Gerard Schildberger (talk) 19:29, 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)
- A task requirement is that the repeat occur two or more times. One repeat doesn't meet that requirement. -- Gerard Schildberger (talk) 19:10, 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)
- Hi Walter. I meant that Ledrugs' original code gave the wrong answer for these, not that they weren't rep-strings. Sorry for the confusion. Ledrugs' method was a great new way of solving things and I had to unlearn how I was doing things to figure out what he was doing. I thought that the corner cases of '11' and '00' needed mental investigation and that made me look at the limit of a range and think it - the original code, would need tweaking. --Paddy3118 (talk) 19:15, 13 May 2013 (UTC)
Draft status
I guess we might want to keep this task as draft a while longer due to the nature of the questions above. --Paddy3118 (talk) 19:26, 13 May 2013 (UTC)