Rep-string: Difference between revisions
m (→Python: Procedural: Use rep-string.) |
(→Python: Functional: New!) |
||
Line 159: | Line 159: | ||
'101' has a repetition length of 0 i.e. *not* a rep-string |
'101' has a repetition length of 0 i.e. *not* a rep-string |
||
'1' has a repetition length of 0 i.e. *not* a rep-string</pre> |
'1' has a repetition length of 0 i.e. *not* a rep-string</pre> |
||
===Python: Functional=== |
|||
<lang python>>>> from itertools import accumulate, cycle, islice |
|||
>>> |
|||
>>> def reps(text): |
|||
return [rep for rep in accumulate(text[:len(text) // 2]) |
|||
if ''.join(islice(cycle(rep),len(text))) == text] |
|||
>>> matchstr = """\ |
|||
1001110011 |
|||
1110111011 |
|||
0010010010 |
|||
1010101010 |
|||
1111111111 |
|||
0100101101 |
|||
0100100 |
|||
101 |
|||
1 |
|||
""" |
|||
>>> print('\n'.join('%r has reps %r' % (line, reps(line)) for line in matchstr.split())) |
|||
'1001110011' has reps ['10011'] |
|||
'1110111011' has reps ['1110'] |
|||
'0010010010' has reps ['001'] |
|||
'1010101010' has reps ['10', '1010'] |
|||
'1111111111' has reps ['1', '11', '111', '1111', '11111'] |
|||
'0100101101' has reps [] |
|||
'0100100' has reps ['010'] |
|||
'101' has reps [] |
|||
'1' has reps [] |
|||
>>> </lang> |
|||
===Python: Regexp=== |
===Python: Regexp=== |
Revision as of 02:25, 12 May 2013
Given a series of ones and zeroes in a string, define a repeated string or rep-string as a string which is created by repeating a substring of the first N characters of the string two or more times, truncated on the right to the length of the input string.
For example, the string '10011001100'
is a rep-string as the leftmost four characters of '1001'
are repeated three times and truncated on the right to give the original string.
The task is to:
- Write a function/subroutine/method/... that takes a string and returns an indication of if it is a rep-string and the repeated string. (Either the string that is repeated, or the number of repeated characters would suffice).
- Use the function to indicate the repeating substring if any, in the following
'1001110011' '1110111011' '0010010010' '1010101010' '1111111111' '0100101101' '0100100' '101' '1'
- Show your output on this page.
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
/* REXX ***************************************************************
- 11.05.2013 Walter Pachl
- /
runSample(arg) return
method repstring(Arg) public static
Parse Arg s maxlen = ('s').length.max(20) sq=('s').right(maxlen) n=s.length() Loop l=s.length()%2 to 1 By -1 If s.substr(l+1,l)=s.left(l) Then Leave End If l>0 Then Do rep_str=s.left(l) Loop i=1 By 1 If s.substr(i*l+1,l)<>rep_str Then Leave End If rep_str.copies(n).left(s.length())=s Then Say sq 'has a repetition length of' rep_str.length() 'i.e. rep_str' Else Say sq 'is not a repeated string' End Else Say sq 'is not a repeated string' Return
method runSample(arg) public static
parse arg samples if samples = then - samples = - '1001110011' - '1110111011' - '0010010010' - '1010101010' - '1111111111' - '0100101101' - '0100100' - '101' - '1'
loop w_ = 1 to samples.words() repstring(samples.word(w_)) end return
</lang>
- Output:
'1001110011' has a repetition length of 5 i.e. '10011' '1110111011' has a repetition length of 4 i.e. '1110' '0010010010' has a repetition length of 3 i.e. '001' '1010101010' has a repetition length of 4 i.e. '1010' '1111111111' has a repetition length of 5 i.e. '11111' '0100101101' is not a repeated string '0100100' has a repetition length of 3 i.e. '010' '101' is not a repeated string '1' is not a repeated string
Perl 6
<lang perl6>for <1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 1> {
.say; if /^ (.+) $0+ (.*$) <?{ $0.substr(0,$1.chars) eq $1 }> / { say ' ' x $0.chars, "$0\n"; } else { say " (no repeat)\n"; }
}</lang>
- Output:
1001110011 10011 1110111011 1110 0010010010 001 1010101010 1010 1111111111 11111 0100101101 (no repeat) 0100100 010 101 (no repeat) 1 (no repeat)
Python
Python: Procedural
<lang python>def is_repeated(text):
'check if the first part of the string is repeated throughout the string' len_text = len(text) for rep_len in range(len_text // 2, 0, -1): reps = (len_text + rep_len) // rep_len if (text[:rep_len] * reps).startswith(text): return rep_len # equivalent to boolean True as will not be zero return 0 # equivalent to boolean False
matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 1 """ for line in matchstr.split():
ln = is_repeated(line) print('%r has a repetition length of %i i.e. %s' % (line, ln, repr(line[:ln]) if ln else '*not* a rep-string'))</lang>
- Output:
'1001110011' has a repetition length of 5 i.e. '10011' '1110111011' has a repetition length of 4 i.e. '1110' '0010010010' has a repetition length of 3 i.e. '001' '1010101010' has a repetition length of 4 i.e. '1010' '1111111111' has a repetition length of 5 i.e. '11111' '0100101101' has a repetition length of 0 i.e. *not* a rep-string '0100100' has a repetition length of 3 i.e. '010' '101' has a repetition length of 0 i.e. *not* a rep-string '1' has a repetition length of 0 i.e. *not* a rep-string
Python: Functional
<lang python>>>> from itertools import accumulate, cycle, islice >>> >>> def reps(text): return [rep for rep in accumulate(text[:len(text) // 2]) if .join(islice(cycle(rep),len(text))) == text]
>>> matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 1 """ >>> print('\n'.join('%r has reps %r' % (line, reps(line)) for line in matchstr.split())) '1001110011' has reps ['10011'] '1110111011' has reps ['1110'] '0010010010' has reps ['001'] '1010101010' has reps ['10', '1010'] '1111111111' has reps ['1', '11', '111', '1111', '11111'] '0100101101' has reps [] '0100100' has reps ['010'] '101' has reps [] '1' has reps [] >>> </lang>
Python: Regexp
This version, inspired by the Perl 6 entry uses the regexp substitute where what the match is substituted with is returned by a function. <lang python>import re
matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 1"""
def _checker(matchobj):
g0, (g1, g2, g3, g4) = matchobj.group(0), matchobj.groups() if not g4 and g1 and g1.startswith(g3): return '%r repeats %r' % (g0, g1) return '%r is not a rep-string' % (g0,)
def checkit(txt):
print(re.sub(r'(.+)(\1+)(.*)|(.*)', _checker, txt))
checkit(matchstr)</lang>
- Output:
'1001110011' repeats '10011' '1110111011' repeats '1110' '0010010010' repeats '001' '1010101010' repeats '1010' '1111111111' repeats '11111' '0100101101' is not a rep-string '0100100' repeats '010' '101' is not a rep-string '1' is not a rep-string
REXX
<lang rexx>/* REXX ***************************************************************
- 11.05.2013 Walter Pachl
- /
Call repstring '1001110011' Call repstring '1110111011' Call repstring '0010010010' Call repstring '1010101010' Call repstring '1111111111' Call repstring '0100101101' Call repstring '0100100' Call repstring '101' Call repstring '1' Exit
repstring: Parse Arg s sq='s' n=length(s) Do l=length(s)%2 to 1 By -1
If substr(s,l+1,l)=left(s,l) Then Leave End
If l>0 Then Do
rep_str=left(s,l) Do i=1 By 1 If substr(s,i*l+1,l)<>rep_str Then Leave End If left(copies(rep_str,n),length(s))=s Then Say sq 'has a repetition length of' length(rep_str), 'i.e.' 'rep_str' Else Say sq 'is not a repeated string' End
Else
Say sq 'is not a repeated string'
Return</lang> Output:
'1001110011' has a repetition length of 5 i.e. '10011' '1110111011' has a repetition length of 4 i.e. '1110' '0010010010' has a repetition length of 3 i.e. '001' '1010101010' has a repetition length of 4 i.e. '1010' '1111111111' has a repetition length of 5 i.e. '11111' '0100101101' is not a repeated string '0100100' has a repetition length of 3 i.e. '010' '101' is not a repeated string '1' is not a repeated string