Praming Puzles & Colf: Condense a String

Having spend some time on this site I have come to enjoy things being as short as possible. That may be the reason why I'm recently kind of offended by strings containing the same characters more than once. Your job is to write a function or program which condenses a given string according to the following rules:

• Start with a 0-condensation, that is look for the first (leftmost) pair of the same characters with 0 other characters between them. If such a pair is found, remove one of the two characters and restart the algorithm by performing another 0-condensation. If no such pair is found, proceed with the next step. Examples:
programming -C0-> programing
aabbcc -C0-> abbcc
test -C0-> test

• Then perform a 1-condensation, that is look for the first pair of same characters with 1 other character between them. If such a pair is found remove one of them and all characters between them and restart with a 0-condensation. If no such pair is found, proceed with the next step. Examples:
abacac -C1-> acac
java -C1-> ja

• Continue with a 2-condensation and so on up to a n-condensation with n being the length of the original string, each time restarting after a condensation removed some letters. Examples:
programing -C2-> praming
abcdafg -C3-> afg

The resulting string is called condensed and contains each character at most once.

Input:

A lower case string of printable ascii-characters.

Output:

The condensed string according to the rules above.

Examples:

examples     -> es
programming  -> praming
puzzles      -> puzles
codegolf     -> colf
andromeda    -> a
abcbaccbabcb -> acb
if(x==1):x++ -> if(x+
fnabnfun     -> fun
abcdefae     -> abcde

Detailed examples to clarify how the algorithm works:

fnabnfun -C0-> fnabnfun -C1-> fnabnfun -C2-> fnfun -C0-> fnfun -C1-> fun -C0-> fun
-C1-> fun -C2-> ... -C8-> fun

abcbaccbabcb -C0-> abcbacbabcb -C0-> abcbacbabcb -C1-> abacbabcb -C0-> abacbabcb
-C1-> acbabcb -C0-> acbabcb -C1-> acbcb -C0-> acbcb -C1-> acb -C0-> acb
-C1-> ... -C12-> acb

Your approach doesn't have to implement the algorithm from above as long as your solution and the algorithm return the same output for all allowed inputs. This is a challenge.

• @MartinEnder Riley's test case is still necessary, because it's the only one my Retina solution doesn't work on. Sep 27 '16 at 13:27
• @mbomb007 Ah, I see. Good point. Sep 27 '16 at 13:40
• Will the input string ever contain non-printable characters like spaces? Sep 27 '16 at 13:58
• @mbomb007 No, to assume printable ascii characters only is fine. Sep 27 '16 at 14:30
• @mbomb007 However as far as I know, a space is considered a printable ascii character, e.g. here. Sep 27 '16 at 15:22

f=
(s,n=0,m=s.match((.).{${n}}\\1))=>s[n]?m?f(s.replace(...m)):f(s,n+1):s ; <input oninput=o.textContent=f(this.value)><pre id=o> • Very nice, shorter than what I would have thought of. Sep 26 '16 at 23:04 Perl, 383130 29 bytes This should should leave the non-golfing languages far behind... -1 for$- thanks to Riley

-1 for @{-} thanks to Dada

Includes +1 for -p

Give input on STDIN

condense.pl:

#!/usr/bin/perl -p
s/(.)\K.{@{-}}\1// while/./g

This 27 byte version should work but it doesn't because perl doesn't interpolate @- in a regex (see https://stackoverflow.com/questions/39521060/why-are-etc-not-interpolated-in-strings)

#!/usr/bin/perl -p
s/(.)\K.{@-}\1// while/./g
• How does the @{\@-} part work? I thought @- held the indexes of each match, so how does it "count up" on every iteration. Also, if you print @{\@-} before and after each substitution it only ever prints 1 or 2. Sep 27 '16 at 13:57
• @Riley The /./g progresses by 1 in the string each time, except when the string changes, then it's reset to 0. If you print @- after the /./g but before the s/// you will see it going up (use a test where the remaining string is large enough) Sep 27 '16 at 14:13
• Printing $- gives the numbers I would expect. Does @{\@-} act like$- because of the regex context but not when printing for some reason? $- is a byte shorter than @{\@-} if they are the same. Sep 27 '16 at 14:22 • "@{\@-}" is not the same as @{\@-} (without "). Sep 27 '16 at 14:38 • @Riley No, but "@{\@-}" is the same as "@-". And this should also be true for a regex substitution but it isn't. Simularly$- should work but doesn't. PS: You probably somehow had scalar context applied to @- when you did your print, so you always got 1 or 2 Sep 27 '16 at 15:58

CJam, 35 bytes

rL{_,{{(_@_@#I={I)>]sj}*}h]s}fI}j

Try it online!

rL{                            }j   | run recursion on input
_,{                      }fI     | for I from 0 to length(input)
{                 }h]s        | one pass & clean up
(_@                          | slice and store leading element A
_@#I={      }*            | if next A is I steps away
I)>                 | slice off I+1 element
]sj              | clean up & recursion

You can see the individual condensations by inserting ed

Python 2, 117104 101 bytes

Recursively do the necessary replacements. I build the regex dynamically.

import re
def f(s,i=0):t=re.sub(r"(.)%s\1"%("."*i),r"\1",s);e=s==t;return i>len(t)and t or f(t,i*e+e)

Try it online

• The two return lines can be condensed into return i>len(t) and t or s!=t and f(t) or f(t,i+1) for a net of -4 bytes Sep 26 '16 at 23:47
• Another 2 bytes can be shaved off by changing that to return t if i>len(t)else s!=t and f(t)or f(t,i+1)) Sep 26 '16 at 23:51
• Even more by e=s==t;return i>len(t)and t or f(t,i*e+e) and then you can remove the i=0 in the function definition, but you'll have to call with 0 start. Sep 26 '16 at 23:59
• I'm going to assume that the four spaces are there not because you're using four spaces but because SE automatically expands them. If that's not the case, you can change all your spaces to either tabs or a single space for -9 bytes.
– Nic
Sep 27 '16 at 3:32
• @Quelklef The meta forbids taking additional parameters. Sep 27 '16 at 13:21

Perl 53 52

Includes +1 for -p

for($i=0;$i<length;){$i=(s/(.).{$i}\1/\1/)?0:$i+1;} Try it on ideone. Mathematica, 101 bytes NestWhile[i=0;StringReplace[#,a_~~_~RepeatedNull~i++~~a_:>a,1]&,#,SameQ,2,ByteCount@#]&~FixedPoint~#& There should be a way to make this shorter... PHP, 90 Bytes for($s=$argv[$c=1];$s[$i=++$i*!$c];)$s=preg_replace("#(.).{{$i}}\\1#","$1",$s,1,$c);echo$s;

or 92 Bytes

for($s=$argv;$s[$i];$i=++$i*!$c)$s=preg_replace("#(.).{".+$i."}\\1#","$1",$s,1,$c);echo$s; • 1) first version: +$i instead of $i+=0 (-2). 2) for loop instead of while can save two bytes and allow to remove curlys (-4). 3)$i=++$i*!$c instead of $i=$c?0:$i+1 (-1). 4) \\2 is not needed, remove parentheses (-2). 5) You can allow limit 9 instead of 1 for speed (+0) Sep 29 '16 at 13:06 • @Titus very good ideas. I had't see this Thank You Sep 29 '16 at 13:58 • Now that I think again ... +$i doesn´t work in every case. Try hammer. PHP doesn´t complain about the empty braces in the regex; but it doesn´t match as wanted. By the way: I count 91, not 90. But try the new 1) for($s=$argv[$c=1];$s[$i=++$i*!$c];) Sep 29 '16 at 17:39 • @Titus Yes indeed I go back to$i+=0 and will try your proposal later. What do mean with hammer? Sep 29 '16 at 18:18
• @Titus okay the same problem if puzzle or something else like (.)//1 but it is okay with your proposal or the $i´=0 Sep 29 '16 at 22:12 Ruby, 7564 57 bytes (56 bytes of code + p command line option.) Using string interpolation inside a regex to control the length of the matches that are replaced. i=0 ~/(.).{#{i}}\1/?sub($&,$1)&&i=0: i+=1while i<$_.size

Test:

$ruby -p condense.rb <<< fnabnfun fun Haskell, 97 88 bytes (0?) (a:s)!(b:t)|a==b=a:t|1<3=a:s!t s!_=s m?s|length s<m=s|a<-s!drop m s=sum[m+1|a==s]?a Try it online! Old 97 byte bersion: (a:s)!(b:t)|a==b=a:t|1<3=a:s!t s!_=s m?s|length s==m=s|a<-s!drop m s=(last$0:[m+1|a==s])?a
c=(0?)

Explanation:

(a:s)!(b:t)|a==b = a:t         --perform condensation
|1<3  = a:s!t       --recursively compare further
s   ! _         = s           --no condensation performed

The (!) function performs one n-condensation when given a string once whole and once with the first n characters removed, e.g. abcdbe and cdbe for a 2-condensation, by recursively comparing the two leading characters.

m?s|length s==m   = s         --stop before performing length-s-condensation
|a <- s!drop m s           --a is the m-condensation of s
= (last\$0:[m+1|a==s])?a   --disguised conditional:
-- if a==s       if the m-condensation did not change s
-- then (m+1)?a  then perform m+1-condensation