Erase the loops

Question

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 code-golf, so the shortest solution in each language wins.

Answer 1

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)):
   $     -   last two links as a monad - f(Current):
 Ḣ       -     head {Current} -> first character
  Ȯ      -     print {that} (without trailing newline), and yield {that}
ṣ        -   split {Beheaded Current} at {that}
    Ṫ    -   tail

Answer 2

Haskell + hgl, 31 30 29 28 14 bytes

ysk$yS$hdS<*h'

Attempt This Online!

Explanation

We are using a parser to do this ysk will repeatedly apply a parser until reaching a fixed point, it prioritizes parses towards the front of the input by default so we just need to write a parser which closes a loop.

As I point out in my comment it doesn't matter if you prioritize loops by their start or end location.

Then the loop itself is yS$hdS<*h', i.e. parse a character, parse some number of characters, parse the same character again returning only the last parse.

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.

Answer 3

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>

Answer 4

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.

Answer 5

sed 4.2.2, 17

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

Try it online!

Answer 6

05AB1E, 6 bytes

ΔćD?¡θ

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

Try it online or verify all test cases.

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

Answer 7

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.

Answer 8

JavaScript (ES6), 44 bytes

f=s=>s==(s=s.replace(/(.).*\1/,"$1"))?s:f(s)

Try it online!

Answer 9

Perl 5 -p, 19 bytes

s/(.).*\1/$1/&&redo

Try it online!

Answer 10

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:              adefcbfggg -> adefggg
        # s[i] and s[j]:     ^  ^
        # s[i:j]:            ^^^
        s = s[:i] + s[j:]
        i += 1
    return s

Answer 11

brainfuck, 75 bytes

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

Try it online!

Answer 12

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.

Answer 13

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
      \+            # accumulative addition
                    # - positions equal to 1 are between the first 2 chars
   ▽≠1              # remove the part in between

Answer 14

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.

Answer 15

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

Answer 16

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.

Answer 17

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

Answer 18

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!

Answer 19

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.