Parse nested digit-lead strings

Question

The task

A string S is constructed with the following process:

1. Start with S being the empty string.
2. Insert at some position of S a string of the form ds, where d is a nonzero digit and s is a string of d lowercase ASCII letters. We say ds is a constituent of S.
3. Go to step 2 or stop.

Your task is to take such a string as input, and output its constituents concatenated into a single string, in the order of appearance of their leading digits. The output must be a single string, and there can't be any delimiters (including newlines) between the constituents. You can choose whether the input and output strings have quotes. Note that the input and output will never be empty.

Example

Let's construct a string with the above process. The structure of the constituents is highlighted in the final result.

S = ""              // Insert "3abc"
S = "3abc"          // Insert "2gh" after 'a'
S = "3a2ghbc"       // Insert "1x" before '3'
S = "1x3a2ghbc"     // Insert "3tty" after '3'
S = "1x33ttya2ghbc" // Final result
     └┘│└┴┴┘│└┴┘││
       └────┴───┴┘

The output is obtained by concatenating the constituents in the order of their digits. In this case, the correct output is

"1x3abc3tty2gh"

Rules and scoring

You can write a full program or a function. the lowest byte count wins, and standard loopholes are disallowed.

Test cases

1k -> 1k
4asdf -> 4asdf
111xyz -> 1z1y1x
8whatever3yes -> 8whatever3yes
8what3yesever -> 8whatever3yes
1x33ttya2ghbc -> 1x3abc3tty2gh
63252supernestedstrings2ok -> 6trings3eds2st5perne2su2ok
9long3yes4lo2ngwords11here -> 9longrdsre3yes4lowo2ng1e1h
9abc8de7fg6hi5jk4lm3o2pq1rstuvwxyzabcdefghijklmnopqrst -> 9abcopqrst8deijklmn7fgdefgh6hizabc5jkwxy4lmuv3ost2pq1r

Answer 1

JavaScript (ES6), 68 bytes

f=s=>s&&f(s.replace(/\d\D+$/,m=>(s=m.slice(0,i=++m[0]),m.slice(i))))+s

Explanation

Based on a simple concept:

• Match the last digit n followed by n letters in the input string
• Remove it from the input string and add it to the start of the output string
• Repeat until the input string is empty

Recursion was the shortest way to do this in JavaScript.

f=s=>
  s&&                        // if the input string is empty, return the empty string
  f(                         // prepend the constituent before it
    s.replace(/\d\D+$/,m=>(  // match the last digit followed by every remaining letter
      s=m.slice(0,n=++m[0]), // set s to the constituent (n followed by n letters)
                             // (we must use s because it is our only local variable)
      m.slice(n)             // replace the match with only the letters after it
    ))
  )+s                        // append the constituent

<input type="text" id="input" value="9long3yes4lo2ngwords11here" />
<button onclick="result.textContent=f(input.value)">Go</button>
<pre id="result"></pre>

Answer 2

Haskell, 89 bytes

fst.p
p(d:s)|(h,(g,r))<-p<$>span('9'<)s,(a,b)<-splitAt(read[d])$h++r=(d:a++g,b)
p e=(e,e)

Try it online! Example usage: fst.p $ "1x33ttya2ghbc" yields "1x3abc3tty2gh".

Answer 3

Python 3, 173 159 bytes

k='123456789';y='';i=0
for t in x:
 i+=1
 if t in k:
  y+=t;n=int(t);m=0
  for z in x[i:]:
   if n:  
    if z in k:m+=int(z)+1
    if m<1:y+=z;n-=1
    m-=m>0

Try it online!

Probably not the golfiest Python implementation.

The logic is almost straightforward: it scans the string. When it finds a digit it starts adding the characters that follow, as many as required (i.e. until the count corresponds to the digit). If it encounters digits before completing the task, it adds them to a counter corresponding to the number of characters to skip. When the counter reaches zero, it goes back to adding characters (i.e. until the count corresponds to the initial digit).

Note: Saved 14 bytes thanks to Wheat Wizard and HyperNeutrino

Answer 4

Java 8, 152 bytes

s->{String t=s,r="";for(char c;!s.isEmpty();c=t.charAt(0),s=s.replace(t=c+(t.substring(1,c-47)),""),r=t+r)t=s.replaceAll(".*(\\d\\D+$)","$1");return r;}

Explanation:

Try it here.

s->{                        // Method with String as both parameter and return-type
  String t=s,               //  Temp-String, starting at the input-String
         r="";              //  Result-String, starting empty
  for(char c;!s.isEmpty();  //  Loop as long as the input-String `s` is not empty
                            //    After every iteration:
      c=t.charAt(0),        //     Get the leading digit from `t` as character
      s=s.replace(t=c+(t.substring(1,c-47))
                            //     Set `t` to the last substring (digit + `c` letters),
                  ,""),     //     and remove that sub-string from String `s`
      r=t+r)                //     And add the substring at the start of result-String `r`
    t=s.replaceAll(".*(\\d\\D+$)","$1");
                            //   Get the last digit + everything after it,
                            //   and set this substring to `t`
                            //  End of loop (implicit / single-line body)
  return r;                 //  Return result-String
}                           // End of method

Answer 5

Python 2, 151 147 135 bytes

d,D=[],[]
for c in input():
 if'/'<c<':':x=[[c]];d=x+d;D+=x
 else:y=d[0];y+=c;d=d[len(y)>int(y[0]):]
print''.join(''.join(w)for w in D)

Try it online!

Explanation:

The code keeps two lists of constituent groups, d and D.

Each character of the string is then scanned:

• If it is a digit, a new group is added to both lists
• Otherwise, the character is added to the latest group in d

When a group has the same length as its digit, the group is removed from d.

At the end, the D is concatenated, as the groups in D are in the original order.

Example:

Input = '1121xwyzv'
d = [], D = []
Loop each character in the input

c='1'
    d=[[1]], D=[[1]]
c='1'
    d=[[1], [1]], D=[[1], [1]]
c='2'
    d=[[2], [1], [1]], D=[[1], [1], [2]]
c='1'
    d=[[1], [2], [1], [1]], D=[[1], [1], [2], [1]]
c='x'
    d=[[1x], [2], [1], [1]], D=[[1], [1], [2], [1x]]
latest group in d is full:
    d=[[2], [1], [1]], D=[[1], [1], [2], [1x]]
c='w'
    d=[[2w], [1], [1]], D=[[1], [1], [2w], [1x]]
c='y'
    d=[[2wy], [1], [1]], D=[[1], [1], [2wy], [1x]]
latest group in d is full:
    d=[[1]], D=[[1], [1], [2wy], [1x]]
c='z'
    d=[[1z], [1]], D=[[1], [1z], [2wy], [1x]]
latest group in d is full:
    d=[[1]], D=[[1], [1z], [2wy], [1x]]
c='v'
    d=[[1v]], D=[[1v], [1z], [2wy], [1x]]
latest group in d is full:
    d=[], D=[[1v], [1z], [2wy], [1x]]
print D in order:
    '1v1z2wy1x'