Part 1
Description
The input is a compressed text. A marker like (AxB) means: take the next A characters and repeat them B times. In this first version, markers inside a repeated section are not expanded. Part 1 asks for the length of the decompressed text.
Solution
I only need the length, not the text itself, so I never build the decompressed text. I pasted the input into A6 and deal with one marker per row. Row 8 works on A6, and every later row works on the text left over after the previous section.
For the text in question, one row finds the first marker and reads its two numbers:
B8: =FIND("(",TRIM($A$6)) ← where the marker starts
D8: =FIND("x",TRIM($A$6))
F8: =FIND(")",TRIM($A$6)) ← where it ends
C8: =--MID(LEFT(TRIM($A$6),D8-1),B8+1,9) ← A, the characters to repeat
E8: =--MID(LEFT(TRIM($A$6),F8-1),D8+1,9) ← B, the repeat count
The length this marker adds is the letters before it, plus A × B for its section. Then I cut the whole marker and its A characters off the text, and the next row starts from what remains:
G8: =B8-1+C8*E8
I8: =MID(A6,F8+C8+1,10^6)
Row 9 is the same, with I8 in place of TRIM($A$6) (so B9: =FIND("(",I8), and so on), and I filled down. After 13 markers the text is used up (I20 is empty), so the answer is the sum of column G:
B2: =SUM(G8:G20)
If there were still letters after the last marker, their count would need adding.
There is a shorter formula:
B2: =REDUCE(HSTACK(A6:B6),SEQUENCE(100),
LAMBDA(a,v,
LET(
z,INDEX(a,1,1),
o,FIND("(",z),
p,FIND("x",z),
q,FIND(")",z),
l,--MID(LEFT(z,p-1),o+1,9),
m,--MID(LEFT(z,q-1),p+1,9),
result,IF(z="",INDEX(a,1,2)+IFERROR(o-1+m*l,LEN(z)),
HSTACK(IFERROR(MID(z,q+l+1,8^5),""),
INDEX(a,1,2)+IFERROR(o-1+m*l,LEN(z)))
),
Part1,IF(columns(a)=1,
a,
result
),
Part1
)
)
)
Part 2
Description
Now markers inside a repeated section are expanded too, and so on repeatedly. The text can get very long, so again I only calculate its length.
Solution
I still use one row per marker, in the order the markers appear, but now the next row starts right after the marker, not after its section. The markers inside the section get their own rows, and mine has more than a thousand of them (rows 25 to 1066). The columns B to F are the same as before, except that F, the position of the ), now means “characters used up so far”: the letters in front of the marker plus the marker itself. The text left over is:
I25: =MID(A6,F25+1,8^5)
For each marker I need to know how many times the letters in front of it will be repeated. That is the product of the repeat counts of all earlier markers whose section still covers this spot. A section still covers the spot when the characters used since it ended (the sum of the F values after it) are no more than its length. Column L works that out (this is row 27, and in later rows the ranges simply grow by one row):
L27: =LET(a,$F$26:F26,
b,SEQUENCE(ROWS(a)),
c,REDUCE($F$24,b,LAMBDA(p,q,VSTACK(p,SORT(SUM(TAKE(a,-q)))))),
d,SORT(c,,-1),
e,$C$25:C26,
f,$E$25:E26,
g,IF(d<=e,PRODUCT(IF(d<=e,f,"")),0),
TAKE(SORT(g,,-1),1))
ccollects, for every earlier marker, how many characters have been used since it, anddsorts them to line up with the markers.gis the product of the repeat counts of the markers that still cover this spot, and 0 for the others, and the last line takes the largest value, which is that product.- L25 and L26 are 0, because there are no letters in front of the first two markers.
Column M counts the letters in front of each marker, times that multiplier. Letters beyond the end of the previous marker’s section (more than C25 of them) are counted once, as the formula says:
M26: =IF(B26-1>C25,C25*L26+B26-1-C25,(B26-1)*L26)
N25: =SUM($M$25:M25) ← running total
The last marker is in row 1066. After it come a few more letters, and each one repeats as often as the next row’s multiplier says (L1067). The next row has no marker, so it shows an error, and I add those letters myself:
D2: =N1066+LEN(I1066)*L1067
A caveat. These rules fit my input, but I haven’t tested them on other inputs. For instance, letters that come after an inner section has ended, while an outer section is still open, would be counted once here instead of being repeated.
A fix for this is using this formula:
D2: =LET(
s,A6,
n,LEN(s),
k,SEQUENCE(n),
ch,MID(s,k,1),
op,FILTER(k,ch="("),
cl,FILTER(k,ch=")"),
xx,FILTER(k,CODE(ch)=120),
l,--MID(s,op+1,xx-op-1),
m,--MID(s,xx+1,cl-xx-1),
w,REDUCE(SEQUENCE(n,,1,0),SEQUENCE(ROWS(op)),
LAMBDA(w,i,
IF((k>=INDEX(cl,i)+1)*(k<=INDEX(cl,i)+INDEX(l,i)),
w*INDEX(m,i),
w
)
)
),
Part2, SUM(w*(CODE(ch)>=65)*(CODE(ch)<=90)),
Part2
)