Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
char *working = NULL, *longest = NULL;
int size = 0, size_longest = 0;
void f(int z, int r, int t, int s, char last) {
if (last == '#') {
if (z) f(z-1, r, t, s, 'z');
if (r) f(z, r-1, t, s, 'r');
if (t) f(z, r, t-1, s, 't');
if (s) f(z, r, t, s-1, 's');
}
else {
working[size++] = last;
if (size > size_longest) {
size_longest = size;
working[size] = '\0';
strcpy(longest, working);
}
if (last == 'z') {
if (z) f(z-1, r, t, s, 'z');
else if (r) f(z, r-1, t, s, 'r'); // optimization
}
else if (last == 't') {
if (z) f(z-1, r, t, s, 'z');
if (r) f(z, r-1, t, s, 'r');
}
else if (last == 'r') {
if (s) f(z, r, t, s-1, 's');
if (t) f(z, r, t-1, s, 't');
}
else { // if (last == 's')
if (s) f(z, r, t, s-1, 's');
else if (t) f(z, r, t-1, s, 't'); // optimization
}
}
--size;
}
void g(int z, int r, int t, int s) {
working = malloc(z+r+t+s+1);
longest = malloc(z+r+t+s+1);
if (!working || !longest) {
printf("memory allocation failed\n");
exit(EXIT_FAILURE);
}
size = size_longest = 0;
printf("%d: z%d r%d t%d s%d: ", z+r+t+s, z, r, t, s);
clock_t start = clock();
f(z, r, t, s, '#');
clock_t end = clock();
printf("%f secs\n", (double)(end - start) / CLOCKS_PER_SEC);
printf("%d %s\n\n", size_longest, longest);
free(working);
free(longest);
}
int main(int argc, char **argv) {
if (argc != 5) {
fprintf(stderr, "Usage: %s Z R T S\n", argv[0]);
exit(EXIT_FAILURE);
}
g(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]), atoi(argv[4]));
return 0;
}