"Candy Crush" a string

Question

Given a non-empty string (or an integer, or a list/array if you prefer) composed exclusively of digits in the range [1-9], your task is to write a function (or a whole program) that applies a "Match-3 type of rule" from left to right and outputs the resulting string, like this :

[parameter] "12223" -> [returned value] "13"

Meaning, while parsing the string from left to right if you encounter the same digit repeated 3 or more times successively, this whole group of digits must "disappear", resulting in the concatenation of the left and right part of the remaining string.

Each time you deal with a group, you must start again from the left end and reiterate the same process until the string no longer changes (normally when you finally reach the right end).

If the string becomes empty at the end of the process, you should output an empty string, or the digit 0, or an empty list/array as you prefer.

---

Test cases :

"1" -> "1"
"31122213" -> "33"
"44555554446" -> "6"
"1322232223222311" -> "1311"
"111" -> ""
"7789998877" -> ""

This is code-golf, so the shortest solution in bytes wins.

Answer 1

Python 3.8, 67 bytes

import re
f=lambda a:(f,str)[a==(b:=re.sub(r"(.)\1\1+","",a,1))](b)

Try it online!

Answer 2

sed -E, 18 bytes

Port of Arnauld's JavaScript answer.

:l
s/(.)\1\1+//
tl

Try it online!

Explanation

$ info '(sed)Programming Commands'

:l           # Specify the location of label 'l' for branch commands
s/(.)\1\1+// # Erase the first instance of 3 or more consecutive equal characters
tl           # Branch to label only if there has been a succesful 's'ubstitution

Answer 3

Vyxal, 9 bytes

(Ġ:‡ḢḢǑ⟇f

Try it Online!

Why use fixed point when you can do too much work?

(         # Over each character
 Ġ        # Group identical items
  :   Ǒ   # Find the first group where...
   ‡--    # Next two as lambda
    ḢḢ    # Removing the first two items yields a truthy result
       ⟇  # Remove the group at the index
        f # Flatten the result.

Answer 4

JavaScript (ES6), 42 bytes

Supports less digits than the more generic version below.

f=s=>s-(s=s.replace(/(.)\1\1+/,''))?f(s):s

Try it online!

---

JavaScript (ES6), 43 bytes

f=s=>s==(s=s.replace(/(.)\1\1+/,''))?s:f(s)

Try it online!

Answer 5

05AB1E, 12 bytes

ΔDγ.Δg3@}õ.;

Try it online or verify all test cases.

.Δ...} could alternatively be D...Ïн and/or g3@ could alternatively be 7b@ for equal-bytes alternatives:

Try it online or verify all test cases.

Explanation:

Δ             # Loop until the result no longer changes (using the implicit input):
 D            #  Duplicate the current integer
  γ           #  Split the copy into parts of equal adjacent digits
   .Δ   }     #  Pop and find the first that's truthy for (or -1 if none are):
     g        #   Push the length of the group
      3@      #   Check whether this length is >= 3
         õ    #  Push an empty string ""
          .;  #  Replace the first occurrence of the found 3+ digits group with this ""
              # (after the loop, the result is output implicitly)

   D          #  Duplicate the list of parts of equal adjacent digits
    7b        #  Push 7, and convert it to a binary-string: "111"
      @       #  Check for each value in the copy whether it's >= 111
       Ï      #  Only keep the parts for which this is truthy
        н     #  Pop and keep the first element (or "" if none were)

Answer 6

Jelly, 14 bytes

Œɠ>2i1œPŒgFµÐL

Try it online!

Takes input as a list of digits, outputs as a list. Outputs [] if the result is empty. The TIO footer converts to/from numbers to lists (and converts [] to 0)

How it works

Œɠ>2i1œPŒgFµÐL - Main link. Takes a list of digits D on the left
           µÐL - Until a fixed point is reached, do the following:
Œɠ             -   Run lengths of equal adjacent elements
  >2           -   Greater than 2?
    i1         -   Find the first truthy index, i
        Œg     -   Group equal adjacent elements
      œP       -   Split, removing the element at the index i
          F    -   Flatten

Answer 7

Retina 0.8.2, 12 bytes

+1`(.)\1\1+

Try it online! Link includes test cases. Explanation: Same regex as before naturally; the 1 executes it once (because Retina defaults to global search and replace) while the + repeats until the string no longer changes.

Answer 8

Japt v2.0a0, 10 bytes

e/(.)\1\1+

Try it

e          recursively replace...
/(.)\1\1+    regex: three or more of the same character
           with empty string

Answer 9

Pip, 21 bytes

Wa~`(.)\1\1+`a:$`.$'a

Try it online!

Explanation

Wa~`(.)\1\1+`a:$`.$'a
                       ; a is first command-line argument (implicit)
W                      ; While
 a~                    ;  the first match in a
   `        `          ;  of this regex:
    (.)                ;   any character
       \1\1+           ;   followed by the same character 2 or more times
                       ;  exists:
               $`      ;   Portion of the string left of the match
                  $'   ;   Portion of the string right of the match
                 .     ;   Concatenate
             a:        ;   Assign back to a
                    a  ; After the loop exits, output the final value of a

Answer 10

Arturo, 56 53 bytes

f:$[s][(=s:<=replace s{/(.)\1\1+(.*)}"$2"s)?->s->f s]

Try it

-3 bytes thanks to @Neil

I couldn't get the regex everyone else is using to work, because it wanted to replace all instances of three or more of the same digit at the same time.

Arturo, 69 bytes

g:$[a][(=a:<=flatten filter.first chunk a=>[&]=>[2<size&]a)?->a->g a]

Try it

A version that works on arrays.

Answer 11

Raku, 33 bytes

{($_,{S/(.)$0$0+//}...*eq*).tail}

Try it online!

This is a sequence of successive modifications to the input string, ending when the last two elements are equal (* eq *). Then tail picks off just the last element.

Answer 12

Charcoal, 33 bytes

Ｗ⊕⌕⭆Φθλ⁼κ§θλ11≔Φθ∨‹λ⊖ι⁻✂θ⊖ι⊕λ¹κθθ

Try it online! Link is to verbose version of code. Explanation: Tricky without any regex or grouping primitives.

Ｗ⊕⌕⭆Φθλ⁼κ§θλ11

Map overlapping pairs of characters into 1 if equal or 0 if unequal and search for a substring match of 11. While one is found...

≔Φθ∨‹λ⊖ι⁻✂θ⊖ι⊕λ¹κθ

... extract the characters prior to the match and all those where the substring from the match to the character contains at least two different characters.

θ

Output the final string.

Answer 13

V (vim), 6 bytes

ò툱±«

Try it online!

If you check the V wiki on regexes there are a lot of shortcuts. This line basically expands to:

while(match found){ :%s/\(.\)\1\1\+// }

which removes the first 3 found matching characters and then repeats until there are none left.

Answer 14

Julia 1.0, 53 bytes

!x=x==(y=replace(x,r"(.)\1\1+"=>"";count=1)) ? x : !y

Try it online!

very similar to several other answers: regex, compare, recursion

Answer 15

C function, 108 bytes

Try it online with a driver program

char*c(char*s) {
    char *p=s,*q;
    while(*p){
        q=p;
        while(*++q==*p);
        p=q-p>=3?strcpy(p,q),c(s):q;
    }
    return s;
}

Here is one that hopefully meets the community standards; I'm sorry the first one didn't. I left just a few extra whitespace for clarity, hope that's OK.

Answer 16

Excel (ms365), 124 bytes

Formula in B1:

=LET(x,SORT(TOCOL(REPT(ROW(1:9),SEQUENCE(,LEN(A1),3))),,-1),REDUCE(A1,x,LAMBDA(y,z,SUBSTITUTE(y,@SORTBY(x,FIND(x,y),),,1))))

Note: For testing, drag this down when absolute referencing is applied to ROW($1:$9). Took it of in final answer to save bytes.

Answer 17

Haskell, 68 63 bytes

until((==)=<<f)f
f(x:r)|(_:_:_,b)<-span(==x)r=b|1<3=x:f r
f s=s

Attempt This Online! The function f recursively goes through the string and removes the first group it encounters. until((==)=<<f)f is short for until(\x->f x==x)f and applies f to the input string until a fixed-point is found.

Previous 68 bytes approach

(""%)
s%(x:r)|(_:_:_,b)<-span(==x)r=""%(s++b)|y<-s++[x]=y%r
s%t=s++t

Attempt This Online!

Answer 18

Haskell, 94 bytes

f xs=case break((>=3).length)$group xs of{(ys,[])->concat ys;(ys,zs)->f$concat(ys<>drop 1 zs)}

Answer 19

Scala, 93 bytes

Golfed version. Try it online!

def f(s:Q):Q={var r="""(.)\1\1+""".r.replaceFirstIn(s, "");if(s==r)s else f(r)}
type Q=String

Ungolfed version. Try it online!

import scala.annotation.tailrec
import scala.util.matching.Regex

object Main {
  def main(args: Array[String]): Unit = {
    println(removeTriplets("31122213"))
    println(removeTriplets("44555554446"))
    println(removeTriplets("1322232223222311"))
    println(removeTriplets("7789998877"))
  }

  @tailrec
  def removeTriplets(s: String): String = {
    val tripletPattern: Regex = """(.)\1\1+""".r
    val replaced = tripletPattern.replaceFirstIn(s, "")
    if (s == replaced) s else removeTriplets(replaced)
  }
}