Fully matched numbers

Question

For the context of this challenge, a matched group is a digit \$n\$, followed by \$n\$ more matched groups. In the case of \$n = 0\$, that's the whole matched group. Digits only go up to 9.

For example, 3010200 is a valid matched group, as:

3       # 3, capturing three elements...
 0      # a 0 (group 1)
 1      # a 1 (group 2), capturing...
  0     # a 0
 2      # And a 2 (group 3), capturing...
  0     # a 0
  0     # and another 0.

A fully matched number is simply any valid matched group.

The list begins:

0, 10, 110, 200, 1110, 1200, 2010, 2100, 3000, 11110, 11200, 12010, 12100, 13000, 20110, 20200, 21010, 21100, 22000, 30010, 30100, 31000, 40000

(As usual, these are hand-generated :P)

Your task is to implement this sequence.

Standard code-golf and sequence rules apply.

Testcases

These are zero-indexed. Last testcase thanks to tjjfvi.

0 -> 0
1 -> 10
4 -> 1110
6 -> 2010
9 -> 11110
13 -> 13000 
18 -> 22000
22 -> 40000
64 -> 500000

Answer 1

APL (Dyalog Unicode), 29 25 bytes

1+⍣{1∧.=⌊\⌽+\1-⌽⍎¨⍕⍺}⍣⎕⊢0

Try it online!

⍣⎕⊢0: Starting at 0, iterate input times:
1+⍣{ ... }: Increment until the new value is fully matched.

The number ⍺ is fully matched if:
⍎¨⍕⍺: base-10 digit list
1-⌽: 1 minus each digit in the reversed list
+\: cumulative sums of this list
⌊\⌽: minimum of each suffix
1∧.=: All minima are equal to 1

Answer 2

Jelly, 11 bytes

DCSÐƤ«\ỊƑø#

Try it online!

Port of ovs's APL solution. Full program.

         ø#    Starting from 0, collect the first [input] integers satisfying:
DC             Subtract each decimal digit from 1.
  SÐƤ          Take the sum of each suffix.
     «\        Are the cumulative minima
       ỊƑ      all equal to 1?

ø# works by placing # in a niladic chain with no leading nilad, supplying it 0 as a starting value (note that it takes the number of values to gather from the last argument to the program, rather than anything within the link). The condition that the cumulative minima of the suffix sums are all 1 is equivalent to that the sum of the entire list is 1 and no suffix sum is less than 1.

Answer 3

Pip, 31 bytes

W1i:SNUQ$AL:{aRA_1+B.0MEa}M P*i

Outputs fully matched numbers indefinitely. Try it online!

Explanation

Observe that every fully matched number (other than 0) can be generated from a shorter fully matched number by taking a digit from the shorter number, incrementing it, and inserting a 0 after it: for example, 10 -> 110; 10 -> 200. If we apply this procedure to every f.m. number of length N, we generate a list of all f.m. numbers of length N+1; but the list will contain some duplicates.

W1i:SNUQ$AL:{aRA_1+B.0MEa}M P*i
                                 i is 0 (implicit); we're going to use it to store
                                 the list of all f.m. numbers of a given length
W1                               While 1 (infinite loop):
                            P*i   Print each element of i
            {            }M       Map this function to each f.m number in i:
                      MEa          Map this function to each index and corresponding
                                   digit of the number:
             a                      The number
              RA_                   Replace at the current index
                 1+B                with 1 plus the digit
                    .0              concatenated to 0
        $AL:                      Flatten the resulting list
      UQ                          Uniquify
    SN                            Sort in numeric order
  i:                              Assign back to i

Answer 4

Ruby, 53 bytes

0.step{|x|i=0;x.digits.all?{|d|0<i+=1-d}&&i==1&&p(x)}

Try it online!

Answer 5

Python 2, 76 bytes

Inspired by ovs's Ruby answer.

n=0
while 1:
 i=t=1
 for d in`n`:t*=i>0;i+=int(d)-1
 if t>0==i:print n
 n+=1

Try it online!

Explanation

For each number n, we loop over each digit d in its string representation. Let i begin at 1; at each digit, add that digit to i and subtract 1. Then for a number to be fully matched, i should never drop below 1 until after the last digit, when it should be exactly 0.

d:  2 0 1 0
i: 1 2 1 1 0

The for loop on the fourth line performs these calculations, tracking whether i is always greater than 0 in t. After the loop, if t is still 1 and i is 0, we print the number.

Answer 6

TypeScript Types, 295 bytes

//@ts-ignore
type a<T,N=[]>=T extends`${N["length"]}`?N:a<T,[...N,0]>;type b<T,N="1",M=[]>=N extends`${M["length"]}`?T:b<T extends`${infer C}${infer T}`?b<T,C>:0,N,[...M,0]>;type M<I,J=[],N=[]>=b<`${N["length"]}`>extends""?I extends J["length"]?N["length"]:M<I,[...J,0],[...N,0]>:M<I,J,[...N,0]>

Try It Online!

Works for 0, 1, 2, and 3, and hits the recursion limit after that.

---

TypeScript Types, 319 bytes

//@ts-ignore
type a<T,N=[]>=T extends`${N["length"]}`?N:a<T,[...N,0]>;type b<T,N="1",M=[]>=N extends`${M["length"]}`?T:b<T extends`${infer C}${infer T}`?b<T,C>:0,N,[...M,0]>;type M<I,J=[0],N=[]>=I extends 0?"0":b<`${N["length"]}0`>extends""?I extends J["length"]?`${N["length"]}0`:M<I,[...J,0],[...N,0]>:M<I,J,[...N,0]>

Try It Online!

Works for 0-8.

Answer 7

Vyxal, 14 bytes

λfḂ⌐¦ḂKv↓1=Π;ȯ

Try it Online!

Takes an integer n and returns first n elements of the sequence.

-1 thanks to @lyxal

Answer 8

Retina, 62 bytes

K`0
"$+"{`$
¶
/¶/{s`.+
2*$($.(*__)¶
+T`d`_d`[1-9]0(?=.*$)
¶0¶

Try it online! No test suite due to the way the program uses history. Outputs the nth fully matched number. Explanation:

K`0

Replace the input with zero.

"$+"{`

Repeat the script n times.

$
¶

Append a newline to make a working area to verify fully matched numbers.

/¶/{`

Repeat while the working area contains a newline.

s`.+
2*$($.(*__)¶

Increment the current value and duplicate it into the working area, deleting any previous content.

+T`d`_d`[1-9]0(?=.*$)

Attempt to reduce the working area to a single 0; any zero after a non-zero digit can be removed and the preceding digit decremented.

¶0¶

If the current value was fully matched then delete the working area, needed to avoid cluttering up the output, but also causing the inner loop to terminate.

Answer 9

Husk, 13 bytes

¥1mödm¬Go←+dN

Try it online!

Inspired by DLosc's and ovs's answers.

  mö        N  # for all natural numbers:
           d   # get the decimal digits,
       Go←+    # subtract one, & get the cumulativ sum;
               # now we want those with a final zero, and
               # no preceding zero:
     m¬        # logical not of all elements (zeros become 1s)
    d          # convert digits to decimal number;
¥1             # finally output whenever the answer is 1.

Answer 10

Haskell, 70 69 bytes

filter(0#)[0..]
a#x=a!divMod x 10
a!(d,m)|d<1=a==m|c<-a-m+1=m<=a&&c#d

Try it online!

• Thanks to @Unrelated String for saving 1 by using filter instead of list comprehension.

• k is an infinite sequence

We start from the end checking if the last digit(m) doesn't consume more groups than available a a-m>=0

Then we remove m groups and add 1 a=a-m+1 and move backwards.

At the end we must have exactly one group a-m+1==1

3010200  
      m  a   a=a-m+1
      0  0   1 
     0   1   2
    2    2   1
   0     1   2
  1      2   2
 0       2   3
3        3   1

Answer 11

05AB1E (legacy), 14 bytes

µ1NS-.sO.s€ßΘP

Given \$n\$, it outputs the 0-based \$n^{th}\$ value.

Uses the legacy version of 05AB1E, which outputs N implicitly after a while-loop. In the new version of 05AB1E, this program required an additional trailing }N to work.

Port of @ovs' APL answer.

Try it online or verify outputs until it times out on TIO.

Explanation:

µ              # While the counter_variable is not equal to the (implicit)
               # input-integer (the counter_variable is 0 by default):
  N            #  Push the current 0-based loop-index
   S           #  Convert it to a list of digits
 1  -          #  Subtract each from 1
     .s        #  Get the suffices of this list
       O       #  Sum each inner suffix-list
        .s     #  Get the suffices of this list again
          ۧ   #  Get the minimum of each inner suffix-list
            Θ  #  Check for each that they're equal to 1
             P #  And check if this is truthy for all of them
               #  (if this is 1: implicitly increase the counter_variable by 1)
               # (after the while-loop, the resulting index is output implicitly)

Answer 12

JavaScript (ES6), 71 bytes

Returns the n-th term, 1-indexed.

Based on ovs' Ruby answer.

n=>eval("for(k=-1;n-=!(i=g=n=>n?(i=-~i-n%10)<1|g(n/10|0):i-1)(k);)++k")

Try it online!

Answer 13

Python3, 182 bytes:

f,n=lambda x,c=[1]:f(x,c[:-2]+[c[-2]-1])if c[-1]==0 and len(c)>1 else(len(c)==1 and c[0]==0if not x else f(x[1:],c+[x[0]])),0
while(n:=n+1):
 if f(list(map(int,str(n-1)))):print(n-1)

Try it online!

Answer 14

Charcoal, 34 bytes

≔⁰ηＦＮ«⟦Ｉη⟧≦⊕ηＷ∨⁻Ση⊖Ｌη⊙Ｉη‹Σ…Ｉημμ≦⊕η

Try it online! Link is to verbose version of code. Outputs the first n numbers (could be trivially modified to output the 0-indexed nth number for the same byte count). Explanation:

≔⁰η

Start with 0.

ＦＮ«

Loop n times.

⟦Ｉη⟧

Output the found fully matched number.

≦⊕η

Try the next number.

Ｗ∨⁻Ση⊖Ｌη⊙Ｉη‹Σ…Ｉημμ≦⊕η

Keep trying the next number until a fully matched number is found. This is identified as a number having a digit sum of one less than its length but none of whose prefixes are a fully matched number.

Answer 15

Vyxal, 15 bytes

λf⌐ṘKṠ₍tg1=A;ȯt

Try it Online!

Mmm yes apl porting. Outputs nth fully matched number 0 indexed