# Append and erase

Given one line that consists of only letters, process as following:

• You maintain a string that's empty at the beginning.
• If the next input character is in the string, remove it from the string.
• If the next input character isn't in the string, append it to the string.

Output the final state of the string.

You can safely assume the input consists at least one character (i.e. non-empty), but there's no guarantee that the output isn't empty.

Pseudocode (Feel free to golf this):

str = EMPTY
for each character ch in input
if ch exists in str
remove all ch from str
else
append ch to str
print str


The input matches the regular expression ^[A-Za-z]+$. Sample test cases: ABCDBCCBE -> ADCBE ABCXYZCABXAYZ -> A aAABBbAbbB -> aAbB GG -> (empty)  The input can be given in any applicable way, but it must be treated as a string, and the same for output. The program should not exit with an error. The shortest program in each language wins! Extra (Optional): Please explain how your program works. Thank you. • May the line be empty? – user202729 Nov 28 '17 at 15:37 • @user202729 No. I changed a little (it does not invalidate any answer) so the input is never empty. – iBug Nov 28 '17 at 16:03 • So why did you reject ais523's edit suggestion (link)? – user202729 Nov 28 '17 at 16:09 ## 32 Answers # Haskell, 44 42 bytes foldl(#)"" s#x|z<-filter(/=x)s=z++[x|z==s]  Try it online! Edit: -2 bytes thanks to Zgarb! Explanation: The second line defines a function (#) which takes a string s and a character x and performs either the remove or append. This is achieved by filtering out every occurrence of x in s, resulting in the string z. If x does not occur in s, then z is equal to s and z++[x|z==s] yields the original string with x appended. Otherwise [x|z==s] yields the empty string and only the filtered string is returned. foldl(#)"" is an anonymous function which takes a string and adds one character after the other the initially empty string "" with the function (#). • 42 bytes by reusing the filter. – Zgarb Nov 25 '17 at 18:38 # Jelly, 3 bytes œ^/  Try it online! Full program. • Why is œ^/ not enough? – Jonathan Allan Nov 27 '17 at 0:06 • @JonathanAllan The program should not exit with an error. – Erik the Outgolfer Nov 27 '17 at 12:44 • the input is never empty Well, now it works. – user202729 Nov 28 '17 at 16:10 # J, 21 19 bytes #~~:&.|.(2|*)1#.=/~  How it works: =/~ - makes a table of equality of the characters in the string:  a =. 'ABCXYZCABXAYZ' ]b =: =/~ a 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1  1#. - sum of each row by base 1 conversion (how many times the letter occurs)  ]c =: 1#. b 3 2 2 2 2 2 2 3 2 2 3 2 2  ~:&.| - reverse, then apply nub sieve (is the char unique) and reverse again. Thus I find the last occurrences of the characters in the string:  ]d =. ~:&.|. a 0 0 0 0 0 0 1 0 1 1 1 1 1  * - multiplies the count by 1 for the last position of the character in the sring, by 0 otherwise, computed by the above ~:&.|  ]e =. c * d 0 0 0 0 0 0 2 0 2 2 3 2 2  2| - modulo 2 (sets to 0 the positions of the chars that have even count):  ]f =. 2| e 0 0 0 0 0 0 0 0 0 0 1 0 0  #~ - copy the right argument left arg. times (~ reverses the places of the args) ]f # a A Try it online! # Brainfuck, 95 bytes ,[<<<[[->+>>>+<<<<]>>>[-<+<->>]<<[[-]<]>[[-]>>[-]>[[-<+>]>]<<[<]<<]<<]<[->>>>[-]<<<]>>>>[->+<]>>[>]>>,]<<<[.<]  Try It Online ### How It Works , Gets first input [ Starts loop <<< Go to start of string [ Loop over the string [->+>>>+<<<<] Duplicates the current char of the string >>>[-<+<->>] Duplicates and subtracts the inputted char from the duplicate of the string char <<[[-]<] If the char is different to the input, remove the difference > If the char is the same [ [-]>>[-]>[[-<+>]>]<<[<]<< Remove the char from the string and sets the inputted char to 0 ] << Moves to the next char of the string ] >>>[->+<] adds the inputted char to the string >>[>]>>, gets the next input ] <<<[.<] prints the string  # Haskell, 47 bytes Another one bytes the dust thanks to Bruce Forte. import Data.List foldl1(\x y->union(x\\y)$y\\x)


Try it online!

Takes a list of Strings.

Symmetric difference is annoying...

• ++ saves 2 bytes over union with this method. – Ørjan Johansen Dec 1 '17 at 10:18

## Retina, 16 bytes

+1(.)(.*?)\1
$2  Try it online! # R, 9284 77 bytes for(i in el(strsplit(scan(,y<-''),y)))y=c(y[y!=i],if(!i%in%y)i);cat(y,sep='')  Try it online! -15 bytes thanks to djhurio ### Explanation djhurio provided an excellent R answer avoiding a for loop -- as R programmers instinctively do as a rule (myself included). Here's an R answer that utilizes a for loop (and saves a few bytes in the process). • x=scan(,''); -- assign the input into the variable x • y=''; -- create an empty string in a variable called y • for(i in el(strsplit(x,''))) -- for every character i in x • y=c(y[y!=i],if(!i%in%y)i) -- assign to y every element of y that is not equal to i, appending i if i was not already in y • cat(y,sep='') -- print the elements of y with no space between them ### Note If you click the TIO link above, you'll find in the header library(methods); this is to deal with the error djhurio experienced regarding the el() function -- the function is provided by the methods package, which in any version of R I've used, is loaded by default, but for whatever reason isn't by TIO. If library(methods) is removed from the header and unlist is substituted for el, I gain four bytes, but so would djhurio, putting our byte counts at 96 88 and 99 respectively. • Nice one. Never thought for loop will be shorter. You can make it even more shorter by omitting else statement for(i in el(strsplit(scan(,y<-''),y)))y=c(y[y!=i],if(!i%in%y)i);cat(y,sep=''). – djhurio Nov 26 '17 at 15:56 • @djhurio -- I know, it's almost never the case that in R a for loop will help with anything. Regarding your suggestion: Great idea! The suggestion is now incorporated in the answer. – duckmayr Nov 26 '17 at 16:11 • @djhurio -- fair enough; I was too busy looking at the difference introduced by omitted the else statement I didn't see how you had changed the beginning. Editing now. Great work! – duckmayr Nov 26 '17 at 18:10 • @djhurio @duckmayr there's a 73 byte solution that is basically taking this solution and using a slightly different approach to extracting characters. I didn't really feel like posting it as a separate answer. Also note that ...[[1]] is longer than el(...) but shorter than unlist(...), provided that ... is a list of length 1. – Giuseppe Nov 27 '17 at 19:52 • scratch that, I found a 70 bye answer since 0 is the nul character and gets converted to the empty string. – Giuseppe Nov 27 '17 at 19:56 # MATL, 6 bytes vi"@X~  Doesn't work in the TIO environment, but works fine on the MATLAB implementation, and thanks to a fresh patch, you may try it on MATL Online X~ equals setxor, or symmetric difference, which does exactly what the challenge asks. The rest is just looping over the input i"@ and starting with an empty string by concatenating the entire stack which is empty at the start (thanks Luis Mendo). # Python 2, 56 bytes -2 bytes thanks to xnor. -3 bytes thanks to ovs. lambda s:reduce(lambda a,c:a.replace(c,'')+c[c in a:],s)  Try it online! Literally just golfed the pseudocode. :P • Save 2 bytes: s=(s+c).replace(c,c[c in s:]). – xnor Nov 25 '17 at 23:33 • @xnor That's some basic golfing executed very cleverly. Thanks! – totallyhuman Nov 25 '17 at 23:34 • -1 byte : s=s.replace(c,'')+c[c in s:] – ovs Nov 26 '17 at 9:32 • 56 bytes using reduce – ovs Nov 26 '17 at 9:37 # JavaScript (ES6), 60 bytes s=>[...s].map(c=>s=s.match(c)?s.split(c).join:s+c,s='')&&s  ### Test cases let f = s=>[...s].map(c=>s=s.match(c)?s.split(c).join:s+c,s='')&&s console.log(f("ABCDBCCBE")) // -> ADCBE console.log(f("ABCXYZCABXAYZ")) // -> A console.log(f("aAABBbAbbB")) // -> aAbB console.log(f("GG")) // -> (empty) • I ported @MartinEnder's Retina answer and it was only 45 bytes... – Neil Nov 25 '17 at 19:44 # q, 38 bytes ""{$[y in x;except;,][x;y]}/


# APL+WIN, 19 bytes

Logic similar to Galen's J solution.

(2|+⌿⌽<\⌽c∘.=c)/c←⎕


# Wolfram Language (Mathematica), 36 bytes

#//.{a___,x_,b___,x_,c___}:>{a,b,c}&


Try it online!

Takes input and output as a list of characters.

## How it works

Uses //. (alias ReplaceRepeated) to find two repeated characters and delete both, until no more repeated characters exist. If the character occurs more than twice, Mathematica will always delete the first two occurrences. So if a character occurs an odd number of times, its last instance will always be the one to survive.

# Prolog 81 byte

a([],O,O).
a([I|J],K,O):-delete(K,I,F),(K=F->append(K,[I],M),a(J,M,O);a(J,F,O)).


Non-obfuscated version:

append_and_eraze([], Output, Output).
append_and_eraze([I | Input], Interim, Output) :-
delete(Interim, I, Filtered),
( Interim = Filtered ->
append(Interim, [I], Interim1),
append_and_eraze(Input, Interim1, Output)
;
append_and_eraze(Input, Filtered, Output)
).

1. delete/3 ensures that its third argument unifies with its first argument, with all instances of second argument removed from it.
2. If those turn out to be the same, we append the element (it wasn't removed).
3. append/3 as per its name, appends an element to list.
4. We recur on the elements of the input until we hit the [] (empty list), at which point the intermediate result will unify with desired result.

Test:

?- append_and_eraze(ABCDBCCBE, [], X), string_codes(Y, X).
X = [65, 68, 67, 66, 69],
Y = "ADCBE".

?- append_and_eraze(ABCXYZCABXAYZ, [], X), string_codes(Y, X).
X = [65],
Y = "A".

?- append_and_eraze(aAABBbAbbB, [], X), string_codes(Y, X).
X = [97, 65, 98, 66],
Y = "aAbB".

?- append_and_eraze(GG, [], X), string_codes(Y, X).
X = [],
Y = "".


Some Prologs treat strings in double quotes as lists, SWI can be configured to do the same, but for the sake of simplicity, I used string_codes/2 to format output nicely.

# Perl 5, 28 + 2 (-pF) = 30 bytes

$\=~s/$_//g||($\.=$_)for@F}{


Try it online

# R, 84 bytes

y=el(strsplit(scan(,""),""));cat(unique(y[colSums(outer(y,y,"=="))%%2>0],,T),sep="")


Try it online!

Another solution, but there are better R answers here.

# R, 88 bytes

z=table(y<-el(strsplit(scan(,""),"")));cat(setdiff(unique(y,,T),names(z[!z%%2])),sep="")


Try it online!

Thanks to Giuseppe for -7 bytes!

1. scan(,"") read input from stdin.
2. y<-el(strsplit(scan(,""),"")) split input by characters and save as y.
3. z=table(y<-el(strsplit(scan(,""),""))) compute frequencies of each character and save resulting table as z;
4. unique(y,,T) take unique characters from the right side.
5. names(z[!z%%2]) select only even counts and extract names.
6. setdiff(unique(y,,T),names(z[!z%%2])) remove characters with even count.
7. cat(setdiff(unique(y,,T),names(z[!z%%2])),sep="") print the output.
• The reason for your error is that el() comes from the methods package, which while typically loaded by default, is not by TIO (discussed in my answer below) – duckmayr Nov 26 '17 at 0:43
• why are you using rev(unique(rev(y)))? Wouldn't just unique(y) work? ooohhh wait I see, you want the unique characters from right to left. In that case unique(y,,T) (setting fromLast=T) will be 88 bytes. – Giuseppe Nov 27 '17 at 20:01

## Alice, 9 bytes

/X&@
\io/


Try it online!

### Explanation

Basically a port of Erik's answer. Apart from a bit of IP redirection the code is really just:

i&Xo@


which does:

i   Read all input.
&X  Fold symmetric multiset difference over the input.
o   Output the result.
@   Terminate.


# APL (Dyalog), 16 bytes

{(,⍨~∩)/⍣(≢⍵)⊖⍵}


Try it online!

If errors were allowed, this would've been 9 bytes:

(,⍨~∩)/∘⊖

• What do you mean by errors? – FrownyFrog Nov 25 '17 at 21:51
• @FrownyFrog The 9-byte version would throw a DOMAIN ERROR if the string is empty, since (,⍨~∩) doesn't have a predefined identity element. – Erik the Outgolfer Nov 26 '17 at 10:29

# Pyth, 15 bytes

Vz?:kN)=-kN=+kN


Try it online!

# Ruby, 53 bytes

->s{s.reverse.uniq.select{|c|s.count(c)%2>0}.reverse}


Try it online!

Input and output are both an array of chars. Test code calls .chars and .join for convenience.

## Explanation

Uses the fact that the letters in the resulting string appear an odd number of times and in the order from right to left.

->s{                # lambda function taking char-array argument
s.reverse           # reverse the input
.uniq               # get unique characters
.select{|c|         # select only those which...
s.count(c)%2>0      # appear in the input array an odd number of times
}.reverse           # reverse back and return
}


# Pyth, 13 bytes

{_xD_Qf%/QT2Q


Takes in input as list of characters. Test it out!

      f     Q            (f)ilter input (Q)
/QT              On how many times (/) each character (T) appears in the
input (Q)
%   2             Only allow odd numbers of occurences (when x % 2 = 1)
_xD_Q                   Sort (D) descending (the first _) by the location (x) of
the last (the second _) inde(x) of the target character
in the input (Q)
{                        Remove duplicates


# Röda, 34 bytes

{a=[]a-=_ if[_1 in a]else a+=_1;a}


Try it online!

This is a direct translation of the pseudocode. It treats input and output as streams of characters.

Explanation:

{                    /* Anonymous function                   */
a=[]             /* initialize a                         */
/* For each character _1 in the stream: */
a-=_ if[_1 in a] /*  Remove it from a if a contains it   */
else a+=_1;      /*  Otherwise append it to a            */
a                /* Push characters in a to the stream   */
}


# Python 3, 73 bytes

Not the shortest, but I like this approach.

lambda s:''.join(c*(s.count(c)%2)*(i==s.rfind(c))for i,c in enumerate(s))


Try it online!

Loops through the string, keeping only those characters where:

• (s.count(c)%2) == 0 - The character appears an even number of times.
• (i==s.rfind(c)) - The current index is the last appearance of the character in question.

# REXX, 102 bytes

a=arg(1)
s=''
do while a>''
b=right(a,1)
if countstr(b,a)//2 then s=b||s
a=changestr(b,a,'')
end
say s


Try it online!

How it works: Take the rightmost letter, see if the number of occurrences is even or odd (which also doubles as a truth value) and if odd, add it to the output string. Then remove all occurrences of the letter from the input string. Repeat until input is depleted.

# Perl 5, 22 + 1 (-p) = 23 bytes

s/(.)(.*?)\1/$2/&&redo  Try it online! # Java 8, 93 bytes A lambda from String to String. Just an implementation of the pseudocode in the question. s->{String o="";for(char c:s.toCharArray())o=o.indexOf(c)<0?o+c:o.replace(c+"","");return o;}  Try It Online # Java 8, 182 bytes Here's another lambda of the same type that uses streams! It's probably more efficient. s->s.join("",s.chars().mapToObj(c->(char)c+"").filter(c->s.replaceAll("[^"+c+"]","").length()%2>0).distinct().sorted((c,d)->s.lastIndexOf(c)-s.lastIndexOf(d)).toArray(String[]::new))  Try It Online ## Ungolfed s -> s.join( "", s.chars() .mapToObj(c -> (char) c + "") .filter(c -> s.replaceAll("[^" + c + "]", "").length() % 2 < 0) .distinct() .sorted((c, d) -> s.lastIndexOf(c) - s.lastIndexOf(d)) .toArray(String[]::new) )  # R, 70 bytes function(s){for(i in utf8ToInt(s))F=c(F[F!=i],i*!i%in%F);intToUtf8(F)}  Try it online! I was encouraged by djhurio to post this solution; djhurio's answer can be found here. This uses the same idea as duckmayr's answer, but it leverages a numeric approach by converting the string to its codepoints rather than splitting it into characters, and is a function rather than a full program so it can return the new string rather than printing to stdout. function(s) { for(i in utf8ToInt(s)) # convert string to codepoints and iterate over it F=c(F[F!=i], # remove duplicates and append i*!i%in%F) # 0 if in F, i otherwise intToUtf8(F) # collapse from codepoints to string }  One important observation is that F is initialized to FALSE or 0 and utf8ToInt(0)=="", so this will succeed for the empty string as well as correctly collapsing the codepoints. # PHP, 71+1 bytes while(~$c=$argn[$i++])$s=strstr($s,$c)?strtr($s,[$c=>""]):$s.$c;echo$s;


Run as pipe with -nR or try it online.

# Python 3.6, 69 bytes

lambda a:"".join({c:1 for c in a[::-1] if a.count(c)%2}.keys())[::-1]


Try it online!

Dict insertion order is preserved in Python 3.6 .

# SNOBOL4 (CSNOBOL4), 97 95 bytes

	S =INPUT
N	S LEN(1) . C REM . S :F(O)
O C :S(R)
O =O C :(N)
R	O C =:S(R)F(N)
O	OUTPUT =O
END


Try it online!

	S =INPUT			;* read input
N	S LEN(1) . C REM . S :F(O)	;* take the first character of S and assign it to C,
;* assign the remainder to S, and if S has no characters left, goto O
O C :S(R)			;* if C matches anything in O, goto R, otherwise go to next line
O =O C :(N)			;* append C to O and goto N
R	O C =:S(R)F(N)			;* as long as C matches O, replace it with ''
;* (unassigned variables default to the null string)
;* then goto N once it fails to match
O	OUTPUT =O			;* output the string
END					;* terminate the program
`