Given a compressed string, give the number of ways it can be decompressed.

  • A compressed string is a string where substrings of repeated characters are changed to a format similar to aaa -> a3
  • For example for the string aaabbhhhh33aaa the compressed string would be a3b2h432a3

As an example of counting decompressing options. Say you have the input a333b2. This can be read as a333 b2 or a3 33 b2 so you would need to return the value 2 as there are 2 options.

You must accept the input as a command line argument (entered when your app is ran) and print out the result

(It will be called like node main.js aaaaa or however else to run apps in your language)

You can use the solution tester in this post to test you followed the correct format https://programming.dev/post/1805174

Checking through the solutions of last weeks problems should be happening this weekend monday + tuesday. Been getting too much work and theres a game jam thats been going on but should be able to go through them all then. I may do the easy one last since it cant be checked using the solutions tester so that one will take a bit longer.

Will also try to go through and give solutions to these ones as well on the weekend and will try to do solutions as soon as possible from now on so you can see if you failed the test cases. For the ones done last week, after I go through them all ill give 1 extra day from then on for any resubmissions

  • brie@beehaw.org
    1·
    1 year ago

    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.