24
\$\begingroup\$

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 , so the shortest solution in bytes wins.

\$\endgroup\$
13
  • 2
    \$\begingroup\$ I didn't expect it to be so easily achievable via regex :') \$\endgroup\$
    – Fhuvi
    Feb 24, 2023 at 14:24
  • 3
    \$\begingroup\$ Can we take input as a list of digits? \$\endgroup\$ Feb 24, 2023 at 14:34
  • 1
    \$\begingroup\$ @GregMartin Yes, i think the order can affect the result. With the test case "44555554446" -> "6", if you apply the process from right to left (or if you do it from left to right without returning to the left after each group), it gives "446" which isn't the correct result. Does this answer the question you asked ? \$\endgroup\$
    – Fhuvi
    Feb 26, 2023 at 23:35
  • 2
    \$\begingroup\$ Yes, and I realized I didn't read the instructions properly—I see now that runs of 3 or more are removed, not just exactly 3 :) \$\endgroup\$ Feb 27, 2023 at 1:41
  • 1
    \$\begingroup\$ @Fhuvi, thank you for posting this. One question: shouldn't this test case ""1322232223222311" -> "1311"" return the empty string ? \$\endgroup\$
    – F. Zer
    Feb 27, 2023 at 12:13

19 Answers 19

10
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – The Thonnu
    Feb 25, 2023 at 15:53
  • \$\begingroup\$ @UndoneStudios The lambda is recursive, so it has to be named. \$\endgroup\$ Feb 26, 2023 at 4:59
9
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I don't know if there's some unwritten rule in this StackExchange website, but these aren't 9 bytes. To store this program you need 19 bytes \$\endgroup\$ Feb 25, 2023 at 18:05
  • 7
    \$\begingroup\$ @ChristianVincenzoTraina Vyxal uses a SBCS (single-byte character system) which allows it to store each character as a single byte. If interpreted as a binary file the program would look like the bytes 28 bd 3a f6 be be f1 06 66. \$\endgroup\$
    – emanresu A
    Feb 25, 2023 at 19:49
  • \$\begingroup\$ I didn't know it, thank you. I think it's meant to exploit the blank/not printable ASCII characters, isn't it? \$\endgroup\$ Feb 27, 2023 at 8:36
  • \$\begingroup\$ @ChristianVincenzoTraina That’s right \$\endgroup\$
    – noodle man
    Mar 8, 2023 at 16:17
7
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ the first one could fail for a large enough string: s - s.replace(...) = Infinity - Infinity = NaN is falsey, so it would only be "crushed" once TIO \$\endgroup\$
    – c--
    Feb 24, 2023 at 17:45
  • 1
    \$\begingroup\$ @c-- Yes, that's what I meant by supports less digits than the (other) version. \$\endgroup\$
    – Arnauld
    Feb 24, 2023 at 20:53
  • \$\begingroup\$ I though you might have meant it didn't support leading zeros, which isn't an issue since OP asked for [1-9] \$\endgroup\$
    – c--
    Feb 24, 2023 at 21:40
6
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Yup, that's about as short as it's gonna get here. Tried a few different tricks to construct the string representation of the RegEx ("(.)%1%1+) in v1, but all attempts worked out much longer than 10 bytes. \$\endgroup\$
    – Shaggy
    Feb 24, 2023 at 16:30
  • \$\begingroup\$ @Shaggy I don't think this score can get shorter unless there's a shorter regex to match three or more of the same character, or if one of the other approaches on this page is somehow shorter in Japt (which is unlikely since we don't have a fixed-point function apply builtin) \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 16:34
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I think f:$[s][(=s:<=replace s{/(.)\1\1+(.*)}"$2"s)?->s->f s] works for 53 bytes. \$\endgroup\$
    – Neil
    Feb 24, 2023 at 18:07
  • \$\begingroup\$ @Neil Thanks a lot! \$\endgroup\$
    – chunes
    Feb 24, 2023 at 18:09
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 31 with a full program: get,{S/(.)$0$0+//}...*eq*>*.say \$\endgroup\$
    – naffetS
    Feb 24, 2023 at 19:57
  • \$\begingroup\$ $_=get;s/(.)$0$0+// xx$_;.say for 29 doing way too much work (very very slow) \$\endgroup\$
    – naffetS
    Feb 24, 2023 at 19:58
4
\$\begingroup\$

Charcoal, 33 bytes

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

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

W⊕⌕⭆Φθλ⁼κ§θλ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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ 77? \$\endgroup\$
    – ASCII-only
    Feb 26, 2023 at 6:33
  • 3
    \$\begingroup\$ 68? \$\endgroup\$
    – ASCII-only
    Feb 26, 2023 at 6:56
  • 1
    \$\begingroup\$ @mbx I deleted the other post showing the ChatGPT sequence, per your comment that ChatGPT references are banned. Thanks! \$\endgroup\$ Feb 27, 2023 at 13:01
  • 2
    \$\begingroup\$ @ASCII-only maybe add -m32 to compiler flags for s to fit in an int, otherwise it would segfault for a string on the stack: TIO. Of course this is not a guarantee as it requires 32 bit integers \$\endgroup\$
    – c--
    Mar 8, 2023 at 23:59
  • 1
    \$\begingroup\$ Building on @ASCII-only 67 (requires a little endian architecture) \$\endgroup\$
    – c--
    Jun 23, 2023 at 15:52
2
\$\begingroup\$

Excel (ms365), 124 bytes

enter image description here

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Haskell, 94 bytes

f xs=case break((>=3).length)$group xs of{(ys,[])->concat ys;(ys,zs)->f$concat(ys<>drop 1 zs)}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Hello and welcome to Code Golf! Nice answer :) I don't know Haskell at all, but isn't it possible to shorten your code a bit more? For example, can't candyCrushS be reduced to a single character or two? And are all these spaces mandatory? \$\endgroup\$
    – Fhuvi
    Mar 7, 2023 at 9:42
  • 1
    \$\begingroup\$ Thank you, @Fhuvi. I've saved 46 bytes with the edit. \$\endgroup\$
    – F. Zer
    Mar 8, 2023 at 17:37
0
\$\begingroup\$

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)
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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