# Erase the loops

A nice simple one!

You are given a finite sequence. Find the earliest pair of equal elements, if any (where "earliest" refers to the position of the second element of the pair), and collapse them and the interval of elements between them into a single copy of the repeated element. E.g. abcda -> a. Repeat this operation until all elements are distinct, and return the resulting final sequence.

Note that the order of the collapsing operations matters.

(This arises in the construction of the "loop-erased random walk", which has important applications.)

### Example

Input: abcbbcdeaeec

a[bcb]bcdeaeec
a(b)bcdeaeec
a[bb]cdeaeec
a(b)cdeaeec
[abcdea]eec
(a)eec
a[ee]c
a(e)c


Output: aec

### Input/Output

You can assume that the input sequence is either a string of printable non-whitespace characters or a list (array, tuple, etc) of nonnegative integers (your choice). You can assume that it has at least 1 element. The output sequence should be in the same form as the input.

### Test cases

x            -> x
xxxx         -> x
ioioioio     -> io
1234321      -> 1
xyzxyzxyz    -> xyz
123213132    -> 132
abcbbcdeaeec -> aec


This is , so the shortest solution in each language wins.

• Removed my comment asking for a test case where it's important to enforce the rule where "earliest" refers to the position of the second element of the pair. I'm actually unable to find any counterexample and I'm now almost convinced that it doesn't matter at all. Commented Aug 14 at 15:02
• @Arnauld You are right. It shouldn't actually matter. If there is a case where the two metrics differ then you have nested loops, and it doesn't matter if you remove the inner one first, it won't disrupt the outer one which will be removed next just the same as if the inner had never been removed. Commented Aug 14 at 15:04
• @Arnauld Do you have such an example? It seems plausible that consistently doing it the other way always gives the same result. Commented Aug 14 at 15:05
• I'm also almost convinced. Interesting though this point is, I don't think it warrants complicating things by editing the question. It's correctly specified as is, and it would be somewhat unusual to try to do it the other way. Commented Aug 14 at 15:17
• At least one can't just do the replacements in whatever order -- for instance axbayb cares whether you collapse a's first or b's. But this requires overlapping intervals, so the same one will be chosen whether you compare by their left or right endpoints. If this choice matters, then one interval is contained within the other, and so it should be safe to delete the inner one first or not, since the outer one will be deleted regardless.
– xnor
Commented Aug 14 at 22:04

# Jelly,  9  8 bytes

ṣḢȮ$ṪµL¿  A full program that accepts a string and prints the erased string. Try it online! Or see the test-suite. #### How? I think this is right, if not do let me know of a counterexample. Rather than iteratively collapsing the string between the "first pair" to become that character (as defined), we can instead iteratively remove everything between the first character and its last occurrence, inclusive (even if it only appears once) and record the first character of the input at each step. I think this works because one of these things is true at each step: 1. The first character doesn't reappear 2. The "first pair" is the same as this choice 3. This choice wraps the "first pair", so the collapsed string would be removed at a later step anyway ṣḢȮ$ṪµL¿ - Link: list, A
¿ - while...
L  - ...condition: length (is non-zero)
µ   - ...action: monadic chain - f(Current (initially A)):

# Reflection

This answer is pretty tight, but there was definitely some room for improvement on hgl that we see could see in earlier versions of this answer.

• This might be shorter with a regex if hgl flavored regexes could handle back-references. Implementing that is a big undertaking, but I always have to mention it.
• There's probably good cause to have Rv h' as a built-in, and might as well add Rv h_ too.
• Converting this answer gives gkY$yS$rX".@_.*_" (+3 bytes) or without regex, gkY$yS$lA hdS<*h' (+3 bytes). I think we could benefit from building in lA hdS and lA hd.
• There could be a function to sandwich a parser between two copies of another parser. Basically
f x y = x <> y <> x

And it should probably have preloaded variants for h' and h_.
• There should be a "splits such that ..." builtin. Also useful here.
• It seems predictable enough that common ways this will be used are "splits such that the first section ..." and "splits such that the second section ..." so those should be built in as well.
• There should be an analog to tk (take) that takes off the back of the list. This would make it easier to check if a section starts and ends with the same thing.
• (@~) should have higher precedence than (<). Currently it's just at the default.

Of course none of these suggestions would actually end up making a shorter answer.

# C (clang), 42 bytes

f(*s){*s&&wcscpy(s,wcsrchr(s,*s))+f(++s);}


Try it online!

# C (clang), 40 bytes

f(*s){*wcscpy(s,wcsrchr(s,*s))&&f(++s);}


Try it online!

This one needs the following header:

#include <wchar.h>


# Japt v2.0a0, 11 bytes

e/(.).*\1/Ï


Try it

Explanation: Recursively replace matches of the RegEx /(.).*\1/g--which matches a character, many different characters, and that same first character--with the first character.

# sed 4.2.2, 17

:
s/(.).*\1/\1/
t


Try it online!

# 05AB1E, 6 bytes

ΔćD?¡θ


Port of @JonathanAllan's Jelly answer, so make sure to upvote that answer as well!

Explanation:

Δ       # Loop until the result no longer changes (aka, until it's an empty string ""):
ć      #  Extract head; push remainder-string and first character separately
#  (which will use the implicit input-string in the first iteration)
D?    #  Duplicate it; and pop and output this first character (without newline)
¡   #  Split the remainder-string on this character
θ  #  Pop and leave just the last part for the next iteration


# Python, 45 bytes

lambda x:re.sub(r"(.).*\1",r"\1",x)
import re


Attempt This Online!

I no longer think the non-greediness of my first attempt below is necessary nor that overlap may be a problem. This echos @Jonathan Allan's observation and probably others, too.

### Python, 47 bytes

lambda x:re.sub(r"(.).*?(?=\1)","",x)
import re


Attempt This Online!

### How?

Similar to other regex based answers. Things that may or may not be Python specific: re.sub only finds non-overlapping matches. Therefore we use a look ahead assertion for the second copy of the repeat element so it remains available for further matches. *? is a non greedy version of *. Here it makes sure the match stretches only to the first reoccurrence of the repeat element.

f=s=>s==(s=s.replace(/(.).*\1/,"$1"))?s:f(s)  Try it online! # Perl 5-p, 19 bytes s/(.).*\1/$1/&&redo


Try it online!

# Python, 61 bytes

f=lambda s,i=0:i<len(s)and f(s[:i]+s[s.rfind(s[i]):],i+1)or s


Attempt This Online!

Goes one by one through characters of the string, collapsing the range between the current character and its final occurrence. Using abcbabadeefcbfggg as an example:

abcbabadeefcbfggg -> adeefcbfggg -> adeefcbfggg -> adefcbfggg -> adefggg -> adefg
^                     ^               ^               ^              ^
^               ^                ^                 ^             ^


Makes use of the same observations that Wheat Wizard and Jonathan Allan have made:

• It does not matter whether the "earliest" pair is based on the first or second element:
cAdBeBfAg -> cAg <=> cAdBeBfAg -> cAdBfAg -> cAg
^     ^                ^ ^        ^   ^

• Assuming the "earliest" pair is based on the first element, it does not matter whether the first element is paired with the earliest or latest second element:
bAcAdAe -> bAe <=> bAcAdAe -> bAdAe -> bAe
^   ^              ^ ^        ^ ^


Ungolfed:

def f(s):
i = 0
while i < len(s):
j = s.rfind(s[i])
# remove s[i:j]
# s[i] and s[j]:     ^  ^
# s[i:j]:            ^^^
s = s[:i] + s[j:]
i += 1
return s

• 44 bytes:f=lambda x:x and x[0]+f(x[x.rfind(x[0])+1:]) Commented Aug 15 at 5:24
• @Albert.Lang Thanks for the suggested golf. We also have 42 bytes with f=lambda s:s and s[0]+f(s.split(s[0])[-1]), a direct port of Jonathan Allan's answer. I'd prefer to keep this specific answer as is, though. I came up with this approach independently, and the specifics are a bit more unique compared to the various solutions derived from Jonathan Allan's implementation and/or these shorter Python solutions. Commented Aug 15 at 6:56

# brainfuck, 75 bytes

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


Try it online!

# Retina 0.8.2, 12 10 bytes

(.).*\1
$1  Try it online! Link includes test cases. Explanation: Port of @noodleman's answer, but assumes @JonathanAllan's observation to save 2 bytes thanks to @att. 17 bytes to follow the challenge description exactly: +r\2.*((.).*)$1


Try it online! Link includes test cases. Explanation: The r indicates right-to-left matching, so as many characters from the right as possible are matched that still allow a pair of identical characters to be matched.

• The order of collapsing definitely matters. However it may work to consistently define "first" in a different way as discussed. Commented Aug 14 at 16:03
• is +  necessary?
– att
Commented Aug 14 at 23:27
• @att Given @‌JonathanAllan's claim, no.
– Neil
Commented Aug 14 at 23:54

# Uiua, 19 bytes

⍥⍣(▽≠1\+⊸=⊢⊸▽¬⊸◰)∘∞


Try it online!

### Explanation

⍥⍣(▽≠1\+⊸=⊢⊸▽¬⊸◰)∘∞

⍥⍣(             )∘∞ # repeat until error (fixed point)
¬⊸◰    # mask of all duplicates
⊢⊸▽       # get the first
⊸=          # mask where the string equals the duplicate
# - positions equal to 1 are between the first 2 chars
▽≠1              # remove the part in between


# Bash, 46 bytes

c=${1:0:1} s=${1:1}
echo $c${s:+$0${s##*$c}}  Try it online! Print the first character, recurse with ${s##*$c}, the string removing the longest prefix ending with that first character. Recursion is guarded by ${s:+ } checking that the rest of the string is non-empty.

# Pyth, 7 bytes

#=ecQph


Try it online!

Uses the same principle as Jonathan Allan's Jelly answer, be sure to upvote that as well.

### Explanation

#=ecQphQ    # implicitly add Q
# implicitly assign Q = eval(input())
#           # loop until error
hQ    # take the first element of Q (will error when Q is the empty string)
p      # print with no trailing newline
cQ       # split Q on instances of this character
e         # take the last element of the split
=  Q       # assign to Q


# Charcoal, 13 bytes

ＷΦθ¬λ«ι≔⊟⪪θιθ


Try it online! Link is to verbose version of code. Explanation: Effectively a port of @JonathanAllan's Jelly answer.

ＷΦθ¬λ«


Repeat while the string has a first character.

ι


Output that character.

≔⊟⪪θιθ


Truncate the string after the last occurrence of that character by splitting and taking the last piece.

# Vyxal, 7 bytes

hṡt)↔∩h


Try it Online!

Port of Jonathan Allan's Jelly answer, go upvote that!

Note: Due to a Vyxal bug, this uses ṡ (regex split) instead of / (regular split), so this can't handle any regex special characters. Everything else should work fine though.

    ↔   # Collect while the result is unique
---)    # Last four elements as a lambda
ṡ      # Split
h       # On first character
t     # And get the last item
∩h # Take the head of each collected string


# APL(Dyalog Unicode), 21 bytes SBCS

Direct implementation of @Jonathan Allan's idea.

⊃¨≢⊢∘(⊢↓⍨0⊥⊢⍸⍤=⊃)⍀⍤⍴⊂


Try it on APLgolf!

⊃¨≢⊢∘(⊢↓⍨0⊥⊢⍸⍤=⊃)⍀⍤⍴⊂
≢⊢∘(          )⍀⍤⍴⊂     ⍝ Apply repeatedly and collect intermediate results
⊃¨                        ⍝ The first items of each intermediate result
(⊢↓⍨0⊥⊢⍸⍤=⊃)         ⍝ Drop the prefix that ends at the last occurrence of the first item
⊢↓⍨                 ⍝ Drop the prefix
0⊥               ⍝  that ends at the last
⊢⍸⍤=⊃          ⍝    occurrences of the first item


# K (ngn/k), 19 bytes

*'-1_({||\|x=*x}_)\


Try it online!

# Ruby, 26 bytes

->s{s.gsub /(.).*\1/,'\1'}


Try it online!

Non-recursive, non-iterative solution, which seems to cover all possible cases, I can't think of any counterexample.

Basically, if you have something like: a......a..a....a.a....aaa, it's going to become a, no matter what's in between, and a greedy search seems to be the best way.