Determine if a string is collapsible: Difference between revisions
m (used braces instead of parentheses, moved a period.) |
m (added another related task.) |
||
Line 84:
:* [https://rosettacode.org/wiki/Determine_if_a_string_has_all_unique_characters determine if a string has all unique characters].
:* [https://rosettacode.org/wiki/Determine_if_a_string_has_all_the_same_characters determine if a string has all the same characters].
:* [https://rosettacode.org/wiki/Determine_if_a_string_is_squeezable determine if a string is squeezable].
<br><br>
|
Revision as of 00:23, 22 November 2019
Determine if a character string is collapsible.
And if so, collapse the string (by removing immediately repeated characters).
If a character string has immediately repeated character(s), the repeated characters are to be deleted (removed), but not the primary (1st) character(s).
An immediately repeated character is any character that is immediately followed by an
identical character (or characters). Another word choice could've been duplicated character, but that
might have ruled out (to some readers) triplicated characters ··· or more.
{This Rosetta Code task was inspired by a newly introduced (as of around November 2019) PL/I BIF: collapse.}
- Examples
In the following character string:
The better the 4-wheel drive, the further you'll be from help when ya get stuck!
Only the 2nd t, e, and l are repeated characters, indicated
by underscores (above), even though they (those characters) appear elsewhere in the character string.
So, after collapsing the string, the result would be:
The beter the 4-whel drive, the further you'l be from help when ya get stuck!
Another example:
In the following character string:
headmistressship
The "collapsed" string would be:
headmistreship
- Task
Write a subroutine/function/procedure/routine··· to locate repeated characters and collapse (delete) them from the character string. The character string can be processed from either direction.
Show all output here, on this page:
- the original string and its length
- the resultant string and its length
- the above strings should be "bracketed" with <<< and >>> (to delineate blanks)
- «««Guillemets may be used instead for "bracketing" for the more artistic programmers, shown used here»»»
Use (at least) the following five strings, all strings are length seventy-two (characters, including blanks), except the 1st string:
string number ╔╗ 1 ║╚═══════════════════════════════════════════════════════════════════════╗ ◄■■■■■■ a null string (length zero) 2 ║"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln ║ 3 ║..1111111111111111111111111111111111111111111111111111111111111117777888║ 4 ║I never give 'em hell, I just tell the truth, and they think it's hell. ║ 5 ║ --- Harry S Truman ║ ◄■■■■■■ has many repeated blanks ╚════════════════════════════════════════════════════════════════════════╝
- Related tasks
Factor
<lang factor>USING: formatting io kernel sbufs sequences strings ; IN: rosetta-code.string-collapse
- (collapse) ( str -- str )
unclip-slice 1string >sbuf [ over last over = [ drop ] [ suffix! ] if ] reduce >string ;
- collapse ( str -- str ) [ "" ] [ (collapse) ] if-empty ;
- .str ( str -- ) dup length "«««%s»»» (length %d)\n" printf ;
- show-collapse ( str -- )
[ "Before collapse: " write .str ] [ "After collapse: " write collapse .str ] bi nl ;
- collapse-demo ( -- )
{ "" "\"If I were two-faced, would I be wearing this one?\" --- Abraham Lincoln " "..1111111111111111111111111111111111111111111111111111111111111117777888" "I never give 'em hell, I just tell the truth, and they think it's hell. " " --- Harry S Truman " "The better the 4-wheel drive, the further you'll be from help when ya get stuck!" "headmistressship" "aardvark" "😍😀🙌💃😍😍😍🙌" } [ show-collapse ] each ;
MAIN: collapse-demo</lang>
- Output:
(Using some extra test cases from the Go entry.)
Before collapse: «««»»» (length 0) After collapse: «««»»» (length 0) Before collapse: «««"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln »»» (length 72) After collapse: «««"If I were two-faced, would I be wearing this one?" - Abraham Lincoln »»» (length 70) Before collapse: «««..1111111111111111111111111111111111111111111111111111111111111117777888»»» (length 72) After collapse: «««.178»»» (length 4) Before collapse: «««I never give 'em hell, I just tell the truth, and they think it's hell. »»» (length 72) After collapse: «««I never give 'em hel, I just tel the truth, and they think it's hel. »»» (length 69) Before collapse: ««« --- Harry S Truman »»» (length 72) After collapse: ««« - Hary S Truman »»» (length 17) Before collapse: «««The better the 4-wheel drive, the further you'll be from help when ya get stuck!»»» (length 80) After collapse: «««The beter the 4-whel drive, the further you'l be from help when ya get stuck!»»» (length 77) Before collapse: «««headmistressship»»» (length 16) After collapse: «««headmistreship»»» (length 14) Before collapse: «««aardvark»»» (length 8) After collapse: «««ardvark»»» (length 7) Before collapse: «««😍😀🙌💃😍😍😍🙌»»» (length 8) After collapse: «««😍😀🙌💃😍🙌»»» (length 6)
Go
<lang go>package main
import "fmt"
// Returns collapsed string, original and new lengths in // unicode code points (not normalized). func collapse(s string) (string, int, int) {
r := []rune(s) le, del := len(r), 0 for i := le - 2; i >= 0; i-- { if r[i] == r[i+1] { copy(r[i:], r[i+1:]) del++ } } if del == 0 { return s, le, le } r = r[:le-del] return string(r), le, len(r)
}
func main() {
strings:= []string { "", `"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln `, "..1111111111111111111111111111111111111111111111111111111111111117777888", "I never give 'em hell, I just tell the truth, and they think it's hell. ", " --- Harry S Truman ", "The better the 4-wheel drive, the further you'll be from help when ya get stuck!", "headmistressship", "aardvark", "😍😀🙌💃😍😍😍🙌", } for _, s := range strings { cs, olen, clen := collapse(s) fmt.Printf("original : length = %2d, string = «««%s»»»\n", olen, s) fmt.Printf("collapsed: length = %2d, string = «««%s»»»\n\n", clen, cs) }
}</lang>
- Output:
original : length = 0, string = «««»»» collapsed: length = 0, string = «««»»» original : length = 72, string = «««"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln »»» collapsed: length = 70, string = «««"If I were two-faced, would I be wearing this one?" - Abraham Lincoln »»» original : length = 72, string = «««..1111111111111111111111111111111111111111111111111111111111111117777888»»» collapsed: length = 4, string = «««.178»»» original : length = 72, string = «««I never give 'em hell, I just tell the truth, and they think it's hell. »»» collapsed: length = 69, string = «««I never give 'em hel, I just tel the truth, and they think it's hel. »»» original : length = 72, string = ««« --- Harry S Truman »»» collapsed: length = 17, string = ««« - Hary S Truman »»» original : length = 80, string = «««The better the 4-wheel drive, the further you'll be from help when ya get stuck!»»» collapsed: length = 77, string = «««The beter the 4-whel drive, the further you'l be from help when ya get stuck!»»» original : length = 16, string = «««headmistressship»»» collapsed: length = 14, string = «««headmistreship»»» original : length = 8, string = «««aardvark»»» collapsed: length = 7, string = «««ardvark»»» original : length = 8, string = «««😍😀🙌💃😍😍😍🙌»»» collapsed: length = 6, string = «««😍😀🙌💃😍🙌»»»
Julia
<lang julia>const teststrings = [
"", """"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln """, "..1111111111111111111111111111111111111111111111111111111111111117777888", """I never give 'em hell, I just tell the truth, and they think it's hell. """, " --- Harry S Truman "]
function collapse(s)
len = length(s) if len < 2 return s, len, s, len end result = last = s[1] for c in s[2:end] if c != last last = c result *= c end end return s, len, result, length(result)
end
function testcollapse(arr)
for s in arr (s1, len1, s2, len2) = collapse(s) println("«««$s1»»» (length $len1)\n collapses to:\n«««$s2»»» (length $len2).\n") end
end
testcollapse(teststrings)
</lang>
- Output:
«««»»» (length 0) collapses to: «««»»» (length 0). «««"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln »»» (length 72) collapses to: «««"If I were two-faced, would I be wearing this one?" - Abraham Lincoln »»» (length 70). «««..1111111111111111111111111111111111111111111111111111111111111117777888»»» (length 72) collapses to: «««.178»»» (length 4). «««I never give 'em hell, I just tell the truth, and they think it's hell. »»» (length 72) collapses to: «««I never give 'em hel, I just tel the truth, and they think it's hel. »»» (length 69). ««« --- Harry S Truman »»» (length 72) collapses to: ««« - Hary S Truman »»» (length 17).
Condensed version:
<lang julia>const teststrings = [
"", """"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln """, "..1111111111111111111111111111111111111111111111111111111111111117777888", """I never give 'em hell, I just tell the truth, and they think it's hell. """, " --- Harry S Truman "]
collapse(s) = (t = isempty(s) ? "" : s[1:1]; for c in s if c != t[end] t *= c end; end; t)
for s in teststrings
n, t = length(s), collapse(s) println("«««$s»»» (length $n)\n collapses to:\n«««$t»»» (length $(length(t))).\n")
end </lang>
Perl
<lang perl>use strict; use warnings; use utf8; binmode STDOUT, ":utf8";
my @lines = split "\n", <<~'STRINGS';
"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln ..1111111111111111111111111111111111111111111111111111111111111117777888 I never give 'em hell, I just tell the truth, and they think it's hell. --- Harry S Truman The American people have a right to know if their president is a crook. --- Richard Nixon AАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑ AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA STRINGS
for (@lines) {
my $squish = s/(.)\1+/$1/gr; printf "\nLength: %2d <<<%s>>>\nCollapsible: %s\nLength: %2d <<<%s>>>\n", length($_), $_, $_ ne $squish ? 'True' : 'False', length($squish), $squish
}</lang>
- Output:
Length: 0 <<<>>> Collapsible: False Length: 0 <<<>>> Length: 72 <<<"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln >>> Collapsible: True Length: 70 <<<"If I were two-faced, would I be wearing this one?" - Abraham Lincoln >>> Length: 72 <<<..1111111111111111111111111111111111111111111111111111111111111117777888>>> Collapsible: True Length: 4 <<<.178>>> Length: 72 <<<I never give 'em hell, I just tell the truth, and they think it's hell. >>> Collapsible: True Length: 69 <<<I never give 'em hel, I just tel the truth, and they think it's hel. >>> Length: 72 <<< --- Harry S Truman >>> Collapsible: True Length: 17 <<< - Hary S Truman >>> Length: 72 <<<The American people have a right to know if their president is a crook. >>> Collapsible: True Length: 71 <<<The American people have a right to know if their president is a crok. >>> Length: 72 <<< --- Richard Nixon >>> Collapsible: True Length: 17 <<< - Richard Nixon >>> Length: 120 <<<AАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑ>>> Collapsible: False Length: 120 <<<AАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑ>>> Length: 72 <<<AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA>>> Collapsible: True Length: 1 <<<A>>>
Perl 6
Technically, the task is asking for a boolean. "Determine if a string is collapsible" is answerable with True/False, so return a boolean as well.
<lang perl6>map {
my $squish = .comb.squish.join; printf "\nLength: %2d <<<%s>>>\nCollapsible: %s\nLength: %2d <<<%s>>>\n", .chars, $_, .chars != $squish.chars, $squish.chars, $squish
}, lines
q:to/STRINGS/;
"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln ..1111111111111111111111111111111111111111111111111111111111111117777888 I never give 'em hell, I just tell the truth, and they think it's hell. --- Harry S Truman The American people have a right to know if their president is a crook. --- Richard Nixon AАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑ AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA STRINGS
</lang>
- Output:
Length: 0 <<<>>> Collapsible: False Length: 0 <<<>>> Length: 72 <<<"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln >>> Collapsible: True Length: 70 <<<"If I were two-faced, would I be wearing this one?" - Abraham Lincoln >>> Length: 72 <<<..1111111111111111111111111111111111111111111111111111111111111117777888>>> Collapsible: True Length: 4 <<<.178>>> Length: 72 <<<I never give 'em hell, I just tell the truth, and they think it's hell. >>> Collapsible: True Length: 69 <<<I never give 'em hel, I just tel the truth, and they think it's hel. >>> Length: 72 <<< --- Harry S Truman >>> Collapsible: True Length: 17 <<< - Hary S Truman >>> Length: 72 <<<The American people have a right to know if their president is a crook. >>> Collapsible: True Length: 71 <<<The American people have a right to know if their president is a crok. >>> Length: 72 <<< --- Richard Nixon >>> Collapsible: True Length: 17 <<< - Richard Nixon >>> Length: 72 <<<AАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑ>>> Collapsible: False Length: 72 <<<AАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑAАΑ>>> Length: 72 <<<AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA>>> Collapsible: True Length: 1 <<<A>>>
REXX
<lang rexx>/*REXX program "collapses" all immediately repeated characters in a string (or strings).*/ @.= /*define a default for the @. array. */ parse arg x /*obtain optional argument from the CL.*/ if x\= then @.1= x /*if user specified an arg, use that. */
else do; @.1= @.2= '"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln ' @.3= ..1111111111111111111111111111111111111111111111111111111111111111177788 @.4= "I never give 'em hell, I just tell the truth, and they think it's hell. " @.5= ' --- Harry S Truman ' end
do j=1; L= length(@.j) /*obtain the length of an array element*/ say copies('═', 105) /*show a separator line between outputs*/ if j>1 & L==0 then leave /*if arg is null and J>1, then leave. */ say ' length='right(L, 3) " input=«««" || @.j || '»»»' new= collapse(@.j) w= length(new) say ' length='right(w, 3) " output=«««" || new || '»»»' end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ collapse: procedure; parse arg y 1 $ 2 /*get a value from arg; get 1st char. */
do k=2 to length(y) /*traipse through almost all the chars.*/ _= substr(y, k, 1) /*pick a character from Y*/ if _==right($, 1) then iterate /*Same character? Skip it.*/ $= $ || _ /*append char., it's diff.*/ end /*j*/ return $</lang>
- output when using the internal default inputs:
═════════════════════════════════════════════════════════════════════════════════════════════════════════ length= 0 input=«««»»» length= 0 output=«««»»» ═════════════════════════════════════════════════════════════════════════════════════════════════════════ length= 72 input=«««"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln »»» length= 70 output=«««"If I were two-faced, would I be wearing this one?" - Abraham Lincoln »»» ═════════════════════════════════════════════════════════════════════════════════════════════════════════ length= 72 input=«««..1111111111111111111111111111111111111111111111111111111111111111177788»»» length= 4 output=«««.178»»» ═════════════════════════════════════════════════════════════════════════════════════════════════════════ length= 72 input=«««I never give 'em hell, I just tell the truth, and they think it's hell. »»» length= 69 output=«««I never give 'em hel, I just tel the truth, and they think it's hel. »»» ═════════════════════════════════════════════════════════════════════════════════════════════════════════ length= 72 input=««« --- Harry S Truman »»» length= 17 output=««« - Hary S Truman »»» ═════════════════════════════════════════════════════════════════════════════════════════════════════════
zkl
<lang zkl>fcn collapsible(str){ // no Unicode
sink:=Sink(String); str.reduce('wrap(c1,c2){ if(c1!=c2) sink.write(c2); c2 },""); // prime with \0 cstr:=sink.close(); return(str.len()!=cstr.len(), cstr);
}</lang> <lang zkl>strings:= 0'^ "If I were two-faced, would I be wearing this one?" --- Abraham Lincoln ..1111111111111111111111111111111111111111111111111111111111111117777888 I never give 'em hell, I just tell the truth, and they think it's hell.
--- Harry S Truman
The American people have a right to know if their president is a crook.
--- Richard Nixon
The better the 4-wheel drive, the further you'll be from help when ya get stuck! headmistressship aardvark^ .split("\n");
- <<<
foreach s in (strings){
println("Before: %3d >>>%s<<<".fmt(s.len(),s)); _,cstr:=collapsible(s); println("After: %3d >>>%s<<<\n".fmt(cstr.len(),cstr));
}</lang>
- Output:
Before: 0 >>><<< After: 0 >>><<< Before: 72 >>>"If I were two-faced, would I be wearing this one?" --- Abraham Lincoln <<< After: 70 >>>"If I were two-faced, would I be wearing this one?" - Abraham Lincoln <<< Before: 72 >>>..1111111111111111111111111111111111111111111111111111111111111117777888<<< After: 4 >>>.178<<< Before: 72 >>>I never give 'em hell, I just tell the truth, and they think it's hell. <<< After: 69 >>>I never give 'em hel, I just tel the truth, and they think it's hel. <<< Before: 72 >>> --- Harry S Truman <<< After: 17 >>> - Hary S Truman <<< Before: 72 >>>The American people have a right to know if their president is a crook. <<< After: 71 >>>The American people have a right to know if their president is a crok. <<< Before: 72 >>> --- Richard Nixon <<< After: 17 >>> - Richard Nixon <<< Before: 80 >>>The better the 4-wheel drive, the further you'll be from help when ya get stuck!<<< After: 77 >>>The beter the 4-whel drive, the further you'l be from help when ya get stuck!<<< Before: 16 >>>headmistressship<<< After: 14 >>>headmistreship<<< Before: 8 >>>aardvark<<< After: 7 >>>ardvark<<<