So, I also realized its the fibonacci sequence for number of combinations of numbers. All I care about is counting sequential digits, we skip a character after every sequence. We just need to account for if the first character is a number and we are good. I did this in ruby. I didn’t really try for anything bonus points wise.

Pastebin because formatting doesn’t like & or <

My code also outputs 0 if the sequence itself is invalid(ends on a non-digit character, or has two non-digit characters in a row)

Thanks for the update on checking through solutions, and thanks in general for all the work you’ve put into this community!

Would just like to clarify: what are the valid decompressed strings? For an input of a333a3, should we return 2 (either a333 a3 or a3 33 a3) or 1 (since a333 a3 isn’t a possible compression – it would be a336 instead)? Do we have to handle cases like a00010, and if so, how?

Given an input c, outputs the number of distinct lists of strings lst such that:

1. ''.join(lst) == c
2. for every string s in lst, s consists of an arbitrary character followed by one or more characters from ‘0123456789’

Sure hope I didn’t mess this up, because I think the fundamental idea is quite elegant! Should run successfully for all “reasonable” inputs (as in, the numeric output fits in a uint64 and the input isn’t ridiculously long). Fundamental algorithm is O(n) if you assume all arithmetic is O(1). (If not, then I don’t know what the time complexity is, and I don’t feel like working it out.)

from functools import cache
from itertools import pairwise
from math import prod

@cache
def fibonacci(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

def main(compressed: str) -> int:
    is_fragment_start = [i == 0 or c not in '0123456789' for i, c in enumerate(compressed)]
    fragment_start_positions = [i for i, s in enumerate(is_fragment_start) if s]
    fragment_lengths = [stop - start for start, stop in pairwise(fragment_start_positions + [len(compressed)])]
    return prod(fibonacci(fragment_length - 1) for fragment_length in fragment_lengths)

if __name__ == '__main__':
    from argparse import ArgumentParser
    parser = ArgumentParser()
    parser.add_argument('compressed')
    print(main(parser.parse_args().compressed))

Idea: a00010 -> [a000, 10] -> [length 4, length 2] -> F(4) * F(2)
01a102b0305 -> [01, a102, b0305] -> [length 2, length 4, length 5] -> F(2) * F(4) * F(5)
where F(n) = fibonacci(n - 1) is the number of ways to partition a string of length n into a list of strings of length ≥2.

F(2) = 1 = fibonacci(1), F(3) = 1 = fibonacci(2), and F(n) = F(n - 2) + F(n - 1), so F is indeed just an offset version of the Fibonacci sequence.
To see why F(n) = F(n - 2) + F(n - 1), here are the ways to split up ‘abcde’: [‘ab’] + (split up ‘cde’), [‘abc’] + (split up ‘de’), and [‘abcde’], corresponding to F(5) = F(3) + F(2) + 1.
And the ways to split up ‘abcdef’: [‘ab’] + (split up ‘cdef’), [‘abc’] + (split up ‘def’), [‘abcd’] + (split up ‘ef’), and [‘abcdef’], corresponding to F(6) = F(4) + F(3) + F(2) + 1 = F(4) + F(5) = F(6 - 2) + F(6 - 1).
The same logic generalizes to all n >= 4.

A bit late to the party but here’s a Rust solution that is probably maybe correct: https://pastebin.com/Eaes7hU9

Very late, but C solution using fib: Git

#include 
#include 
#include 

size_t fib(size_t n)
{
	/* n=93 is the last fib(n) that fits in u64. */
	static size_t cache[94] = { 0, 1 };
	static size_t top_valid = 1;
	size_t a, b;

	if (top_valid >= n) {
		return cache[n];
	} else if (n >= sizeof(cache) / sizeof(*cache)) {
		fputs("Fib overflow\n", stderr);
		exit(EXIT_FAILURE);
	}

	a = cache[top_valid - 1];
	b = cache[top_valid];
	for (; top_valid < n; top_valid += 2) {
		a = cache[top_valid + 1] = a + b;
		b = cache[top_valid + 2] = a + b;
	}

	return cache[n];
}

int main(int argc, char **argv)
{
	char *p, c;
	size_t combos = 1;
	int digits = 0;
	

	if (argc != 2) {
		fputs("Bad invocation.\n", stderr);
	}

	if (!*(p = argv[1])) {
		goto done;
	}

	for (;;) {
		c = *++p;
		if (c < '0' || c > '9') {
			combos *= fib(digits);
			digits = 0;
			if (!c) {
				break;
			}
		} else {
			digits++;
		}
	}

done:
	printf("%zu\n", combos);

	return 0;
}

Zig would probably be a good language for a solution if there is a known maximum number of combinations, since it has large fixed-width types and comptime.