25
\$\begingroup\$

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.


Thanks to @Linus for helpful sandbox comments!

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

JavaScript (ES6), 74 bytes

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>

\$\endgroup\$
  • \$\begingroup\$ Very nice, shorter than what I would have thought of. \$\endgroup\$ – ETHproductions Sep 26 '16 at 23:04
5
\$\begingroup\$

Perl, 38 31 30 29 bytes

This should should leave the non-golfing languages far behind...

-1 for $-[0] 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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Riley Sep 27 '16 at 13:57
  • 1
    \$\begingroup\$ @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) \$\endgroup\$ – Ton Hospel Sep 27 '16 at 14:13
  • \$\begingroup\$ Printing $-[0] gives the numbers I would expect. Does @{\@-} act like $-[0] because of the regex context but not when printing for some reason? $-[0] is a byte shorter than @{\@-} if they are the same. \$\endgroup\$ – Riley Sep 27 '16 at 14:22
  • \$\begingroup\$ "@{\@-}" is not the same as @{\@-} (without "). \$\endgroup\$ – Riley Sep 27 '16 at 14:38
  • \$\begingroup\$ @Riley No, but "@{\@-}" is the same as "@-". And this should also be true for a regex substitution but it isn't. Simularly $-[0] 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 \$\endgroup\$ – Ton Hospel Sep 27 '16 at 15:58
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Python 2, 117 104 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

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Quelklef Sep 26 '16 at 23:47
  • \$\begingroup\$ 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)) \$\endgroup\$ – Quelklef Sep 26 '16 at 23:51
  • \$\begingroup\$ 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. \$\endgroup\$ – Quelklef Sep 26 '16 at 23:59
  • \$\begingroup\$ 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. \$\endgroup\$ – Fund Monica's Lawsuit Sep 27 '16 at 3:32
  • \$\begingroup\$ @Quelklef The meta forbids taking additional parameters. \$\endgroup\$ – mbomb007 Sep 27 '16 at 13:21
1
\$\begingroup\$

Perl 53 52

Includes +1 for -p

for($i=0;$i<length;){$i=(s/(.).{$i}\1/\1/)?0:$i+1;}

Try it on ideone.

\$\endgroup\$
1
\$\begingroup\$

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...

\$\endgroup\$
1
\$\begingroup\$

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[1];$s[$i];$i=++$i*!$c)$s=preg_replace("#(.).{".+$i."}\\1#","$1",$s,1,$c);echo$s;   
\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Titus Sep 29 '16 at 13:06
  • \$\begingroup\$ @Titus very good ideas. I had't see this Thank You \$\endgroup\$ – Jörg Hülsermann Sep 29 '16 at 13:58
  • \$\begingroup\$ 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];) \$\endgroup\$ – Titus Sep 29 '16 at 17:39
  • \$\begingroup\$ @Titus Yes indeed I go back to $i+=0 and will try your proposal later. What do mean with hammer? \$\endgroup\$ – Jörg Hülsermann Sep 29 '16 at 18:18
  • \$\begingroup\$ @Titus okay the same problem if puzzle or something else like (.)//1 but it is okay with your proposal or the $i´=0 \$\endgroup\$ – Jörg Hülsermann Sep 29 '16 at 22:12
1
\$\begingroup\$

Ruby, 75 64 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
\$\endgroup\$
1
\$\begingroup\$

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?)

Try it on ideone.

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
                              -- else 0?a      else restart with a 0-condensation

c=(0?)                        -- main function, initialise m with 0
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.