Collapsing numbers

Question

Let's define the a function on natural numbers \$n\$, written as base 10 digits \$d_k\; d_{k-1}\; \dotsc\; d_1\; d_0\$, as follows:

As long as there are equal adjacent digits \$d_i\;d_{i-1}\$, replace them by their sum \$d_i+d_{i-1}\$ from left to right. If there were any such digits, repeat the same procedure.

In other words, in each iteration we greedily take all pairs of equal adjacent digits and replace them by their sum at the same time (using the left-most pair if they overlap).

Example

Let's take \$\texttt{9988}\$ for example:

1. The first adjacent digits which are equal are the two \$\texttt{9}\$
2. So we replace them by \$\texttt{9 + 9} = \texttt{18}\$ which gives us \$\texttt{1888}\$
3. Since we're still in the first left-right traversal and there were still two \$\texttt{8}\$s we need to first replace these
4. So we get \$\texttt{1816}\$
5. Something changed, so we need to do another iteration
6. But there are no such digits, so we stop

Therefore the \$9988^\text{th}\$ number in that sequence is \$1816\$.

Challenge

The first 200 terms are:

0,1,2,3,4,5,6,7,8,9,10,2,12,13,14,15,16,17,18,19,20,21,4,23,24,25,26,27,28,29,30,31,32,6,34,35,36,37,38,39,40,41,42,43,8,45,46,47,48,49,50,51,52,53,54,10,56,57,58,59,60,61,62,63,64,65,12,67,68,69,70,71,72,73,74,75,76,14,78,79,80,81,82,83,84,85,86,87,16,89,90,91,92,93,94,95,96,97,98,18,10,101,102,103,104,105,106,107,108,109,20,21,4,23,24,25,26,27,28,29,120,121,14,123,124,125,126,127,128,129,130,131,132,16,134,135,136,137,138,139,140,141,142,143,18,145,146,147,148,149,150,151,152,153,154,20,156,157,158,159,160,161,162,163,164,165,4,167,168,169,170,171,172,173,174,175,176,24,178,179,180,181,182,183,184,185,186,187,26,189,190,191,192,193,194,195,196,197,198,28

Your task is to generate that sequence, either

• given \$n\$, return the \$n^\text{th}\$ number in that sequence,
• given \$n\$, return the first \$n\$ numbers in that sequence
• or generate the sequence indefinitely.

You may choose your submission to use either \$0\$- or \$1\$-indexing, but please specify which.

Test cases

You may use the above given terms, however here are some larger ones:

222 -> 42
1633 -> 4
4488 -> 816
15519 -> 2019
19988 -> 2816
99999 -> 18189
119988 -> 21816
100001 -> 101
999999 -> 181818

Answer 1

Python 3, 128 bytes

def t(z):j=z and(z[0]==z[1:2])+1;return[str(int(z[0])*j),*t(z[j:])]if j else''
def c(n):r="".join(t(n));return r!=n and c(r)or r

Try it online!

Answer 2

Python 2, 97 96 93 bytes

def f(n):r=re.sub(r'(.)\1',lambda m:`int(m.group(1))*2`,n);return r!=n and f(r)or r
import re

Try it online!

---

Non regex version:

Python 2, 133 130 122 112 98 bytes

def f(n):
 r='';s=n
 while s:a=1+(s[0]==s[1:2]);r+=`int(s[0])*a`;s=s[a:]
 return r!=n and f(r)or r

Try it online!

Answer 3

Jelly, 11 bytes

DŒg+2/€FVµ¡

This is an unnecessarily slow, full program.

Try it online!

Alternate version, 12 bytes

DŒg+2/€FVµƬṪ

One byte longer, but much faster. Works as a program or a function.

Try it online!

How it works

DŒg+2/€FVµƬṪ  Main link. Argument: n (integer)

         µ    Combine the previous links into a chain. Begin a new one.
D               Decimal; yield n's digit array in base 10.
 Œg             Group adjacent, identical digits into subarrays.
   +2/€         Map non-overlapping, pairwise sum over the subarrays.
                If there is an odd number of digits in a subarray, the
                last digit will remain untouched.
       F        Flatten; dump all sums and digits into a single array.
        V       Eval; turn the result into an integer.
          Ƭ   Execute the chain 'til the results are no longer unique.
              Return all unique results.
           Ṫ  Tail; extract the last result.

The 11-byte version does the same, except it calls the link n times for input n, instead of calling it until a fixed point is reached.

Answer 4

Haskell, 70 bytes

until((==)=<<f)f
f(a:b:c)|a==b=show(2*read[a])++f c|1<2=a:f(b:c)
f a=a

Input is taken as a string.

Try it online!

Answer 5

Retina, 16 bytes

+`(.)\1
$.(2*$1*

Try it online! Link includes test cases. Explanation:

+`

Repeat until the input stops changing.

(.)\1

Replace pairs of adjacent digits...

$.(2*$1*

... with twice the digit. ($1* generates a string of $1 _s, 2* duplicates that, and $.( takes the length. Actually, the Retina engine is cleverer than that and just doubles $1.)

Answer 6

JavaScript, 48 47 46 bytes

Input and output as strings. Returns the nth term of the sequence.

f=s=>s-(s=s.replace(/(.)\1/g,x=>x/5.5))?f(s):s

Try it online

• 1 byte saved thanks to Arnauld
• 1 byte saved thanks to tsh

Answer 7

Perl 6, 37 bytes

{($_,{S:g[(\d)$0]=2*$0}...*==*)[*-1]}

Try it online!

This is a function which generates the nth term of the sequence, given n as its argument.

($_, { ... } ... * == *) is the sequence of successive changes to the input number, generated by the bracketed expression (a simple regex substitution) and stopping when * == *, that is, when the last two numbers in the sequence are equal. Then the [*-1] takes just the final element of that sequence as the return value.

Answer 8

C# (.NET Core), 231, 203, 200, 196, 192 bytes

EDIT: Function is now at 185 bytes plus 18 for using System.Linq;

Thanks to BMO (for 1>0 being equal to true plus newline removal) and Mr. XCoder (for f=!f statements)!

EDIT2: Down to 182 bytes plus 18 for using System.Linq thanks to dana for sharing a few golf tips!

EDIT3: Thanks to Embodiment of Ignorance for the int[] -> var, removal of short circuit && -> &, and changing up ToArray -> ToList! (178 bytes + 18 using)

EDIT4: Embodiment of Ignorance dropped 4 bytes by changing an assignment. Dummy me shoulda counted! Thanks again :D

p=>{var f=1>0;while(f){var t=p.Select(n=>n-48).ToList();p="";f=!f;for(var j=0;j<t.Count;j++){if(j<t.Count-1&t[j]==t[1+j]){p+=t[j]+t[++j];f=!f;continue;}p+=t[j];}};return p;};

Try it online!

Answer 9

Perl 5 -p, 21 bytes

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

Try it online!

Answer 10

Japt v2.0a0 -h, 15 14 bytes

Returns the nth term of the sequence.

Æ=s_r/(.)\1/ÏÑ

Try it

This should work for 10 bytes but there seems to be a bug in Japt's recursive replacement method.

e/(.)\1/ÏÑ

Answer 11

Groovy, 63 bytes

{s->r=/(\d)\1/
while(s=~r)s=s.replaceAll(r){(it[1]as int)*2}
s}

Try it online!

Answer 12

05AB1E, 11 bytes

Δγε2ôSO}˜J

Try it online or verify all test cases.

Explanation:

Δ             # Continue until the (implicit) input no longer changes:
 γ            #  Split the integer in chunks of the same adjacent digits
              #   i.e. 199999889 → [1,99999,88,9]
  ε     }     #  Map each to:
   2ô         #   Split it into parts of size 2
              #    i.e. 99999 → [99,99,9]
     €S       #   Split each part into digits
              #    i.e. [99,99,9] → [[9,9],[9,9],[9]]
       O      #   And take the sum of each part
              #    i.e. [[9,9],[9,9],[9]] → [18,18,9]
         ˜    #  Flatten the list
              #   i.e. [[1],[18,18,9],[16],[9]] → [1,18,18,9,16,9]
          J   #  Join everything together
              #   i.e. [1,18,18,9,16,9] → 118189169
              # (And output the result implicitly at the end)
              #  i.e. output = 28189169

Answer 13

Wolfram Language 108 bytes

ToExpression[""<>ToString/@Total/@Flatten[Partition[#,UpTo@2]&/@Split@IntegerDigits@#,1]]&~FixedPoint~#&

Explanation

IntegerDigits transforms the input number into a list of its digits.

Split groups consecutive repeated digits.

Partition[#, UpTo@2]&/@ breaks runs of like digits into lists of, at most, lengths of 2.

Flatten[...,1] eliminates occasional overly-nested braces--e.g., {{2,2}} becomes {2,2}

Total/@ sums totals of paired digits. Isolated digits need not be summed.

ToString converts the totals (and isolated digits) to strings.

""<> joins all the strings in the list.

ToExpression converts the outcome to an integer.

...~FixedPoint~#& applies the function until the result ceases to change.

Answer 14

C# (Visual C# Interactive Compiler) with flag /u:System.Text.RegularExpressions.Regex, 70 bytes

s=>{for(;s[0]!=(s[0]=Replace(s[0],@"(.)\1",m=>m.Value[0]*2-96+"")););}

Outputs by modifying the input. Takes in a list containing one string for input.

Thanks to @dana for golfing an entire 23 bytes!

Try it online!

Answer 15

Clean, 118 bytes

import StdEnv,Data.List
$[a,b:t]|a==b=[1,(a*2)rem 10]%(1-a/5,1)++ $t=[a: $[b:t]]
$l=l

limit o iterate$o map digitToInt

Try it online!

Takes the first repeated value (limit) from the infinite list of applications (iterate) of a lambda performing a single step of the collapsing process. Input taken as a [Char].

Answer 16

Red, 84 83 80 bytes

func[n][if parse s: form n[to some change[copy d skip d](2 * do d)to end][f s]s]

Try it online!

Returns the nth term of the sequence.

Explanation:

Red[]
f: func [ n ] [
    if parse s: form n [  ; parse the input converted to a string
        to some change [  ; find and change one or more
            copy d skip   ; digit (in fact any character, no predefined character classes)
            d             ; followed by itself
        ] (2 * do d)      ; with its doubled numeric value 
        to end            ; go to the end of the string
    ] [ f s ]             ; call the function with the altered string if parse returned true
    s                     ; finally return the string 
]

Answer 17

Scala, 84 bytes

s=>{var t=s
while(t!=(t="(\\d)\\1".r.replaceAllIn(t,m=>s"$m"(0)*2-96+""),t)._2){}
t}

Try it online!

Answer 18

C# (Visual C# Interactive Compiler), 111 bytes

s=>{var t=s;do{s=t;t="";for(int i=0;i<s.Length;)t+=s[i]%48*(s[i++]!=(s+0)[i]?1:2*++i/i);}while(t!=s);return t;}

Try it online!

HUGE credit to @ASCIIOnly for golfing ~30 ;) At first we were both posting updates simultaneously, but at some point he clearly went to town!

-2 thanks to @EmbodimentOfIgnorance!

Less golfed code...

// s is the input as a string
s=>{
  // t is another string used
  // to hold intermediate results
  var t=s;
  // the algorithm repeatedly
  // processes s and saves the
  // result to t
  do{
    // copy the last result to s
    // and blank out t
    s=t;
    t="";
    // iterate over s
    for(int i=0;i<s.Length;)
      // append either 1 or 2 times
      // the current digit to t
      t+=s[i]%48*
        // compare the current digit
        // to the next digit. to prevent
        // an out-of-bounds exception,
        // append a 0 to s which either
        // gets ignored or collapses
        // to 0
        (s[i++]!=(s+0)[i]
          // if they are different, then
          // the multiplier is 1
          ?1
          // if they are the same, then
          // the multiplier is 2, and we
          // have to increment i
          :2*++i/i);
  }
  // continue this until the input
  // and output are the same
  while(t!=s);
  return t;
}

Answer 19

Husk, 15 bytes

→U¡ödṁoṁodΣC2gd

Try it online!

Answer 20

Ruby -p, 39 34 bytes

-5 bytes thanks to Steffan

$_.gsub!(/(.)\1/){$1.to_i*2}&&redo

Attempt This Online!