Rep-string: Difference between revisions
(→Tcl: Added two test patterns and output) |
m (Clarify task description & add format magic) |
||
Line 3: | Line 3: | ||
For example, the string <code>'10011001100'</code> is a rep-string as the leftmost four characters of <code>'1001'</code> are repeated three times and truncated on the right to give the original string. |
For example, the string <code>'10011001100'</code> is a rep-string as the leftmost four characters of <code>'1001'</code> are repeated three times and truncated on the right to give the original string. |
||
Note that the requirement for having the repeat occur two or more times means that the repeating unit is ''never'' longer than half the length of the input string. |
|||
The task is to: |
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). |
* 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 |
* Use the function to indicate the repeating substring if any, in the following: |
||
<pre>'1001110011' |
<dl><dd><pre>'1001110011' |
||
'1110111011' |
'1110111011' |
||
'0010010010' |
'0010010010' |
||
Line 17: | Line 19: | ||
'11' |
'11' |
||
'00' |
'00' |
||
'1'</pre> |
'1'</pre></dl> |
||
* Show your output on this page. |
* Show your output on this page. |
||
Revision as of 08:36, 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.
Note that the requirement for having the repeat occur two or more times means that the repeating unit is never longer than half the length of the input 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
version 1
<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
version 2
<lang rexx>/*REXX pgm determines if a string is a repString, returns min len repStr*/ @. = @.1 = 1001110011 @.2 = 1110111011 @.3 = 0010010010 @.4 = 1010101010 @.5 = 1111111111 @.6 = 0100101101 @.7 = 0100100 @.8 = 101 @.9 = 11 @.10 = 00 @.11 = 1
do k=1 while @.k\== say right(@.k,20) ' ' rep_string(@.k) end /*k*/
exit /*stick a fork in it, we're done.*/ /*───────────────────────────────────REP_STRING subroutine──────────────*/ rep_string: procedure; parse arg x; L=length(x)
do j=1 for L-1; p=left(x,j) if left(copies(p,L*L),L)==x then return 'rep string=' left(p,15) end /*j*/
return '(no repetitions)'</lang> output
1001110011 rep string= 10011 (length 5) 1110111011 rep string= 1110 (length 4) 0010010010 rep string= 001 (length 3) 1010101010 rep string= 10 (length 2) 1111111111 rep string= 1 (length 1) 0100101101 rep string= 01001011 (length 8) 0100100 rep string= 010 (length 3) 101 rep string= 10 (length 2) 11 rep string= 1 (length 1) 00 rep string= 0 (length 1) 1 (no repetitions)
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" "11" "00" "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 "11" has repetition (length: 1) of "1" "00" has repetition (length: 1) of "0" "1" is not a repeated string