Un-de-duplicating strings

Question

Introduction

Let's observe the following string:

AABBCCDDEFFGG

You can see that every letter has been duplicated, except for the letter E. That means that the letter E has been de-duplicated. So, the only thing we need to do here is to reverse that process, which gives us the following un-de-duplicated string:

AABBCCDDEEFFGG

Let's take a harder example:

AAAABBBCCCCDD

You can see that there is an uneven number of consecutive B's, so that means that one of the BB was de-duplicated from the original string. We only need to un-de-duplicate this letter, which gives us:

AAAABBBBCCCCDD

The challenge

Given a non-empty de-duplicated string, consisting of only alphabetic characters (either only uppercase or only lowercase), return the un-de-duplicated string. You can assume that there will always be at least one de-duplicated character in the string.

Test cases

AAABBBCCCCDDDD    -->    AAAABBBBCCCCDDDD
HEY               -->    HHEEYY
AAAAAAA           -->    AAAAAAAA
N                 -->    NN
OOQQO             -->    OOQQOO
ABBB              -->    AABBBB
ABBA              -->    AABBAA

This is code-golf, so the shortest valid submission in bytes wins!

I'm not sure I understand the challenge. Why does ABBB map to AABBBB, not AABBBBBB? — Dennis, Dec 15 '16 at 23:14
@Dennis If you seperate each group of characters into groups of 2, you would get the following: A BB B. The characters that aren't paired (and therefore not duplicated) need to be duplicated, resulting in AA BB BB, which is the un-de-duplicated string. — Adnan, Dec 15 '16 at 23:33
So: Ensure that every run of characters has an even number of elements by adding at most one element to the run? — Mad Physicist, Dec 16 '16 at 12:13

Luis Mendo · Accepted Answer · 2016-12-15 23:54:30Z

20

MATL, 7 bytes

Y'to+Y"

Try it online! Or verify all test cases.

Let's take 'ABBA' as example input.

Y'   % Implicit input. Run-length decoding
     % STACK: 'ABA', [1 2 1]
t    % Duplicate top of the stack
     % STACK: 'ABA', [1 2 1], [1 2 1]
o    % Modulo 2
     % STACK: 'ABA', [1 2 1], [1 0 1]
+    % Add, element-wise
     % STACK: 'ABA', [2 2 2]
Y"   % Run-length encoding. Implicit display
     % STACK: 'AABBAA'

edited Dec 15 '16 at 23:54

answered Dec 15 '16 at 22:50

Luis Mendo

93k9 gold badges109 silver badges334 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

11

Retina, 11 bytes

(.)\1?
$1$1

Try it online - contains all test cases

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 15 '16 at 22:49

mbomb007

22.3k5 gold badges53 silver badges129 bronze badges

1

\$\begingroup\$ I expected Retina to win. \$\endgroup\$ – Adám Dec 16 '16 at 14:53
\$\begingroup\$ @Adám Yeah, it's pretty short, but that MATL answer is great. All the golfing languages ended up with shorter solutions. \$\endgroup\$ – mbomb007 Dec 16 '16 at 14:57

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

8

Perl, 16 bytes

15 bytes of code + -p flag.

s/(.)\1?/$1$1/g

To run it:

perl -pe 's/(.)\1?/$1$1/g' <<< 'HEY'

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 15 '16 at 22:40

Dada

8,3571 gold badge13 silver badges43 bronze badges

add a comment |

nimi · Accepted Answer · 2016-12-15 22:37:51Z

7

Haskell, 36 bytes

u(a:b:c)=a:a:u([b|a/=b]++c)
u x=x++x

Usage example: u "OOQQO" -> "OOQQOO".

If the string has at least 2 elements, take two copies of the first and append a recursive call with

the second element an the rest if the first two elements differ or
just the rest

If there are less than two elements (one or zero), take two copies of the list.

answered Dec 15 '16 at 22:37

nimi

34.8k3 gold badges30 silver badges93 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Brachylog, 17 bytes

@b:{~b#=.l#e,|}ac

Try it online!

Explanation

Example input: "ABBB"

@b                  Blocks: Split into ["A", "BBB"]
  :{          }a    Apply the predicate below to each element of the list: ["AA", "BBBB"]
                c   Concatenate: "AABBBB"

    ~b#=.             Output is the input with an additional element at the beginning, and
                        all elements of the output are the same (e.g. append a leading "B")
        .l#e,         The length of the Output is an even number
             |        Or: Input = Output (i.e. do nothing)

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

Ruby, 21 bytes

20 bytes plus the -p flag.

gsub(/(.)\1?/){$1*2}

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 15 '16 at 22:43

Value Ink

11.2k1 gold badge11 silver badges40 bronze badges

add a comment |

Community · Accepted Answer · 2017-04-13 12:39:03Z

JavaScript (ES6), 37 30 bytes

Saved 7 bytes by using the much more efficient '$1$1' like [other] [answers] did

s=>s.replace(/(.)\1?/g,'$1$1')

Test cases

let f =

s=>s.replace(/(.)\1?/g,'$1$1')

console.log(f("AAABBBCCCCDDDD"));   //  -->  AAAABBBBCCCCDDDD
console.log(f("HEY"));              //  -->  HHEEYY
console.log(f("AAAAAAA"));          //  -->  AAAAAAAA
console.log(f("N"));                //  -->  NN
console.log(f("OOQQO"));            //  -->  OOQQOO
console.log(f("ABBB"));             //  -->  AABBBB
console.log(f("ABBA"));             //  -->  AABBAA

Greg Martin · Accepted Answer · 2016-12-15 23:35:33Z

4

Mathematica, 41 bytes

s=StringReplace;s[s[#,a_~~a_->a],b_->b~~b]&

Unnamed function that inputs a string and outputs a string. Completely deduplicate then completely undeduplicate. Not real short, but I couldn't do better for now.

answered Dec 15 '16 at 23:35

Greg Martin

14.4k3 gold badges16 silver badges64 bronze badges

add a comment |

MildlyMilquetoast · Accepted Answer · 2016-12-16 01:09:45Z

Befunge 98, 24 bytes

#@~#;:::#@,~-:!j;$,;-\,;

Try it Online!

$ can be easily replaced with -, and the 2nd @ with ;.

I think this can be golfed further due to the - at the beginning of both -, (or $, above) and -\,.

How?

Stack notation:  bottom [A, B, C, D] top

#@~     Pushes the first character onto the stack (C henceforth) and ends if EOF
#;      No-op to be used later
:::     Now stack is [C, C, C, C]

#@,~    Prints C, and if EOF is next (odd consecutive Cs), prints again and ends
        Lets call the next character D

-       Now stack is [C, C, C-D]
:!j;    If C == D, go to "$," Else, go to "-\,"

===(C == D)===

$,      C == D (i.e. a pair of Cs) so we discard top and print C (Stack is now [C])
;-\,;   Skipped, IP wraps, and loop starts again

===(C != D)===

-       Stack is [C, C-(C-D)]  By expanding: [C, C - C + D] or just [C, D]
\,      Prints C (Stack is now [D])

;#@~#;  This is skipped, because we already read the first character of a set of Ds,
        and this algorithm works by checking the odd character in a set of
        consecutive similar characters. We already read D, so we don't
        need to read another character.

Community · Accepted Answer · 2020-06-17 09:04:33Z

Java 7, 58 bytes

String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

Ungolfed:

String c(String s){
  return s.replaceAll("(.)\\1?", "$1$1");
}

Test code:

Try it here.

class M{
  static String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

  public static void main(String[] a){
    System.out.println(c("AABBCCDDEFFGG"));
    System.out.println(c("AAAABBBCCCCDD"));
    System.out.println(c("AAABBBCCCCDDDD"));
    System.out.println(c("HEY"));
    System.out.println(c("AAAAAAA"));
    System.out.println(c("N"));
    System.out.println(c("OOQQO"));
    System.out.println(c("ABBB"));
    System.out.println(c("ABBA"));
  }
}

Output:

AABBCCDDEEFFGG
AAAABBBBCCCCDD
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

PHP, 65 bytes, no regex

while(""<$c=($s=$argv[1])[$i])if($c!=$s[++$i]||!$k=!$k)echo$c.$c;

takes input from command line argument. Run with -r.

regex? In PHP, the regex used by most answers duplicates every character. would be 44 bytes:

<?=preg_replace("#(.)\1?#","$1$1",$argv[1]);

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 16 '16 at 11:14

Titus

14.2k1 gold badge15 silver badges41 bronze badges

add a comment |

Riley · Accepted Answer · 2016-12-16 16:16:28Z

Brain-Flak 69 Bytes

Includes +3 for -c

{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>{({}<>)<>}<>

Try it Online!

Explanation:

Part 1:
{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>

{                                                  }   # loop through all letters
 (   {}     [ {} ]<(())>){((<{}{}>))}{}                # equals from the wiki   
                                                       # but first:
  ((  <>))<>                                           # push the top letter on the other 
                                                       # stack twice  
             (  )                                      # push the second letter back on
                                       {        }      # if they were equal:
                                        (<    >)       # push a 0 to exit this loop
                                          {}{}         # after popping the 1 from the 
                                                       # comparison and the next letter
                                                       # (the duplicate)
                                                 {}    # pop the extra 0
                                                    <> # switch stacks

Part 2 (at this point, everything is duplicated in reverse order):
{({}<>)<>}<>

{        }   # for every letter:
 ({}<>)      # move the top letter to the other stack
       <>    # and switch back
          <> # Finally switch stacks and implicitly print

Dennis · Accepted Answer · 2016-12-15 23:44:15Z

1

Jelly, 9 bytes

Œgs€2ṁ€€2

Try it online!

answered Dec 15 '16 at 23:44

Dennis

200k40 gold badges342 silver badges782 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

V 10 bytes

Í¨.©±½/±±

TryItOnline

Just a find and replace regex like all of the rest in the thread. The only difference is that I can replace anything that would require a \ in front of it with the character with the same ascii value, but the high bit set. (So (, 00101000 becomes ¨, 10101000)

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 16 '16 at 3:37

nmjcman101

3,3846 silver badges17 bronze badges

add a comment |

Brad Gilbert b2gills · Accepted Answer · 2016-12-16 04:47:26Z

1

Perl 6, 17 bytes

s:g/(.)$0?/$0$0/

with -p command-line switch

Example:

$ perl6 -pe 's:g/(.)$0?/$0$0/' <<< 'AAABBBCCCCDDDD
> HEY
> AAAAAAA
> N
> OOQQO
> ABBB
> ABBA'
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA

answered Dec 16 '16 at 4:47

Brad Gilbert b2gills

12.7k1 gold badge14 silver badges33 bronze badges

add a comment |

rnso · Accepted Answer · 2016-12-16 06:07:54Z

Racket 261 bytes

(let((l(string->list s))(r reverse)(c cons)(e even?)(t rest)(i first))(let p((l(t l))(ol(c(i l)'())))
(cond[(empty? l)(list->string(if(e(length ol))(r ol)(r(c(i ol)ol))))][(or(equal?(i ol)(i l))(e(length ol)))
(p(t l)(c(i l)ol))][(p(t l)(c(i l)(c(i ol)ol)))])))

Ungolfed:

(define (f s)
  (let ((l (string->list s)))
    (let loop ((l (rest l))
               (ol (cons (first l) '())))
      (cond
        [(empty? l)
         (list->string(if (even? (length ol))
                          (reverse ol)
                          (reverse (cons (first ol) ol))))]
        [(or (equal? (first ol) (first l)) 
             (even? (length ol)))
         (loop (rest l) (cons (first l) ol))]
        [else
         (loop (rest l) (cons (first l) (cons (first ol) ol)))] ))))

Testing:

(f "ABBBCDDEFFGGG")

Output:

"AABBBBCCDDEEFFGGGG"

Emigna · Accepted Answer · 2016-12-16 07:19:58Z

05AB1E, 10 bytes

.¡vy¬ygÉ×J

Try it online!

Explanation

.¡           # split string into groups of the same char
  v          # for each group
   y         # push the group
    ¬        # push the char the group consists of
     yg      # push the length of the group
       É     # check if the length of the group is odd
        ×    # repeat the char is-odd times (0 or 1)
         J   # join to string

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Python3, 102 94 bytes

from collections import*
lambda s:"".join(c*(s.count(c)+1&-2)for c in OrderedDict.fromkeys(s))

Thanks to xnor for saving 8 bytes! -> bithack.

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 16 '16 at 5:07

Yytsi

3,6721 gold badge13 silver badges34 bronze badges

\$\begingroup\$ This doesn't keep the letters in the right order. \$\endgroup\$ – xnor Dec 16 '16 at 5:19
\$\begingroup\$ @xnor Thanks for mentioning! Fixed. \$\endgroup\$ – Yytsi Dec 16 '16 at 5:33
\$\begingroup\$ Looks good. You can write the expression x+x%2 as x&-2. \$\endgroup\$ – xnor Dec 16 '16 at 5:54
\$\begingroup\$ @xnor I tried s.count(c)&-2 and it returned an empty string... :/ Any thoughts? \$\endgroup\$ – Yytsi Dec 16 '16 at 6:07
1

\$\begingroup\$ Oh, you're right and I made a mistake. I think x+1&-2 should do it. Evens go to themselves and odds round up to evens. \$\endgroup\$ – xnor Dec 16 '16 at 8:09

| show 3 more comments

Billywob · Accepted Answer · 2016-12-16 09:56:34Z

R, 81 bytes

r=rle(el(strsplit(scan(,""),"")));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

Reads a string from stdin, splin into vector of characters and perform run-length encoding (rle). Subsequently repeat the each values from the rle, the sum of the lengths and the lengths mod 2.

If we can read input separated by space (implicitly as a vector/array of characters) then we can skip the splitting part and the program reduces to 64 bytes:

r=rle(scan(,""));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

><> (Fish) 39 bytes

0v ;oo:~/:@@:@=?!voo
 >i:1+?!\|o !:  !<

Pretty sure this can be golfed a lot using a different technique.

It takes an input and compares against the current stack item, if it's different it'll print the first stack item twice, if the same it prints them both.

The stack when empty gets supplied with a 0 which prints nothing so can be appended on whenever.

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 16 '16 at 10:36

Teal pelican

1,3385 silver badges13 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Pyth, 15 bytes

Vrz8p*+hN%hN2eN

Verify all test cases here.

Thanks to Luis Mendo for the methodology.

Explanation

Vrz8p*+hN%hN2eN    z autoinitializes to the input
 rz8               run-length encode the input, returned as list of tuples (A -> [[1,"A"]])
V                  for every element N in this list
      +hN          add the head element of N (the number in the tuple)
         %hN2      to the head element of N mod 2
     *       eN    repeat the tail element of N that many times (the letter in the tuple)
    p              print repeated character without trailing newline

As is often the case, I feel like this could be shorter. I think there should be a better way to extract elements from the list than what I am using here.

Community · Accepted Answer · 2017-04-13 12:39:02Z

PowerShell, 28 bytes

$args-replace'(.)\1?','$1$1'

Try it online! (includes all test cases)

Port of the Retina answer. The only points of note are we've got $args instead of the usual $args[0] (since the -replace will iterate over each item in the input array, we can golf off the index), and the '$1$1' needs to be single quotes so they're replaced with the regex variables rather than being treated as PowerShell variables (which would happen if they were double-quote).

Steadybox · Accepted Answer · 2016-12-17 15:51:44Z

1

C, 67 bytes

i;f(char*s,char*d){i=*s++;*d++=i;*d++=i;*s?f(i-*s?s:++s,d):(*d=0);}

Call with:

int main()
{
    char *in="AAABBBCCCCDDDD";
    char out[128];
    f(in,out);
    puts(out);
}

answered Dec 17 '16 at 15:51

Steadybox

16k5 gold badges34 silver badges83 bronze badges

add a comment |

Mitch Schwartz · Accepted Answer · 2016-12-18 11:47:58Z

1

brainfuck, 22 bytes

,
[
  [>->+<<-]
  >[>..<<]
  >,
]

Try it online.

Prints the current character twice, unless it's equal to a character that was just printed twice.

edited Dec 18 '16 at 11:47

answered Dec 18 '16 at 9:16

Mitch Schwartz

5,0191 gold badge21 silver badges25 bronze badges

add a comment |

Un-de-duplicating strings

Introduction

The challenge

Test cases

24 Answers 24

MATL, 7 bytes

Retina, 11 bytes

Perl, 16 bytes

Haskell, 36 bytes

Brachylog, 17 bytes

Explanation

Ruby, 21 bytes

JavaScript (ES6), 37 30 bytes

Test cases

Mathematica, 41 bytes

Befunge 98, 24 bytes

Java 7, 58 bytes

PHP, 65 bytes, no regex

Brain-Flak 69 Bytes

Jelly, 9 bytes

V 10 bytes

Perl 6, 17 bytes

Example:

Racket 261 bytes

05AB1E, 10 bytes

Python3, 102 94 bytes

R, 81 bytes

><> (Fish) 39 bytes

Pyth, 15 bytes

Explanation

PowerShell, 28 bytes

C, 67 bytes

brainfuck, 22 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions