Rep-string: Difference between revisions
(→Python: Functional: Update example due to task modification.) |
(→Python: Regexp: Update example due to task modification.) |
||
Line 247: | Line 247: | ||
0100100 |
0100100 |
||
101 |
101 |
||
11 |
|||
00 |
|||
1""" |
1""" |
||
Line 269: | Line 271: | ||
'0100100' repeats '010' |
'0100100' repeats '010' |
||
'101' is not a rep-string |
'101' is not a rep-string |
||
'11' repeats '1' |
|||
'00' repeats '0' |
|||
'1' is not a rep-string</pre> |
'1' is not a rep-string</pre> |
||
Revision as of 04:33, 13 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' '11' '00' '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
<lang perl>foreach (qw(1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 1)) {
print "$_\n"; if (/^(.+)\1+(.*$)(?(?{ substr($1, 0, length $2) eq $2 })|(?!))/) { print ' ' x length $1, "$1\n\n"; } else { print " (no repeat)\n\n"; }
}</lang>
- Output:
1001110011 10011 1110111011 1110 0010010010 001 1010101010 1010 1111111111 11111 0100101101 (no repeat) 0100100 010 101 (no repeat) 1 (no repeat)
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' for x in range(len(text)//2, 0, -1): if text.startswith(text[x:]): return x return 0
matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 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 '11' has a repetition length of 1 i.e. '1' '00' has a repetition length of 1 i.e. '0' '1' has a repetition length of 0 i.e. *not* a rep-string
Python: Functional
This returns all the possible repeated substrings <lang python>>>> def reps(text):
return [text[:x] for x in range(1, 1 + len(text) // 2) if text.startswith(text[x:])]
>>> matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 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 [] '11' has reps ['1'] '00' has reps ['0'] '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 11 00 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 '11' repeats '1' '00' repeats '0' '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
Tcl
<lang tcl>proc repstring {text} {
set len [string length $text] for {set i [expr {$len/2}]} {$i > 0} {incr i -1} {
set sub [string range $text 0 [expr {$i-1}]] set eq [string repeat $sub [expr {int(ceil($len/double($i)))}]] if {[string equal -length $len $text $eq]} { return $sub }
} error "no repetition"
}</lang> Demonstrating: <lang tcl>foreach sample {
"1001110011" "1110111011" "0010010010" "1010101010" "1111111111" "0100101101" "0100100" "101" "1"
} {
if {[catch {
set rep [repstring $sample] puts [format "\"%s\" has repetition (length: %d) of \"%s\"" \ $sample [string length $rep] $rep]
}]} {
puts [format "\"%s\" is not a repeated string" $sample]
}
}</lang>
- Output:
"1001110011" has repetition (length: 5) of "10011" "1110111011" has repetition (length: 4) of "1110" "0010010010" has repetition (length: 3) of "001" "1010101010" has repetition (length: 4) of "1010" "1111111111" has repetition (length: 5) of "11111" "0100101101" is not a repeated string "0100100" has repetition (length: 3) of "010" "101" is not a repeated string "1" is not a repeated string