Thread: Help with C combinatronics problem

Hi, I'm learning combinatronics and algorithms in C at uni and stumbled upon this problem which I'm struggling to solve. I'm posting here after trying for 3 days to write a decent solution, but the only one that works is basically a recursive brute force, which is less than ideal. I would really appreciate any help, especially with the recursive function.

A jeweler has z sapphires, r rubies, t topazes, and s emeralds to create a necklace by stringing one stone after another.
He must, however, meet the following rules:

- a sapphire must be followed immediately by either another sapphire or a ruby
- an emerald must be followed immediately by either another emerald or a topaz
- a ruby must be followed immediately by either an emerald or a topaz
- a topaz must be followed immediately by either a sapphire or a ruby.

Write a C function that calculates the length and displays the composition of a maximum-length necklace that obeys the above rules. The length of the necklace is the number of gemstones in it.
Remark: the length of the solution can vary between 1 and (z+r+t+s).
Hint: the exercise can be solved by adopting an approach similar to that of arrangements with repetition, if appropriately adopted to the requirements of the problem. Once the recursive model is set up, write the filter function (acceptability check) and the optimization function. We finally evaluate the possibility to introduce criteria of pruning.
Note: Pay attention to the increase of the execution time required to identify the solution as the values of the input parameters for the problem increase (number of available gems).

The correct term is "combinatorics".
Post your brute force solution.

Originally Posted by john.c

The correct term is "combinatorics".
Post your brute force solution.

Yeah sorry :P
This is my sad attempt at this problem

Do you have example input/output? Post it.

Problems with second solution:
In main:
You need to init k to 0.
val, max_sol, max_count, and j are not used.

Input of 3, 2, 4, 3 should yield 11 but your code says 10.
(Solution of length 11: 2 0 0 0 1 3 3 3 2 1 2)

The way you are timing it is only accurate to seconds. Usually we would use the clock() function.

Code:

clock_t start = clock(); // include <time.h>
// code you want to time
clock_t end = clock();
printf("Time: %f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);

This seems pretty fast. It's based on my analysis that an optimal string can always be created with all z's together and all s's together. The only change from a pure brute force method is the two lines marked "optimization". All that's different on those lines is the addition of the keyword "else". I have a couple of other ideas that could speed it up more if necessary.

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;
}

This is interesting. You are assuming that the word "necklace" means that we are creating a circle, which makes sense but I didn't think of it that way. I thought of it as a line. The instructions do not stress the circular aspect. The only clue is the word "necklace". You are probably correct, but the instructions should have emphasized that. An example would have helped. It's certainly a more interesting (and constrained) problem that way. I guess my code is no good then.

Best to clarify the "necklace" with your instructor before settling on a solution.

hamster_nz: you've made a typo since the "minimum( s, e )" should of course be maximum.

iloverecursion: "Necklace" should really mean a circle. But if those examples are from the problem description (as opposed to your own) then apparently it really is just a line.

As for comments, I really don't feel like adding them. The code is pretty straightforward except for the "else" optimizations, which just force all the z's (saphires) and s's (emeralds) together. (I wish they didn't use 'z' for saphire and 's' for emerald. That's just weird, but I stuck with it.)

Anyway, the first call is determined by last == '#' and is handled specially.
When last != '#', it is appended to working to build the string, and the string is saved as longest if the size has surpased size_longest.
size is decremented before returning from the function to "remove" the last element from working.

As for the idea that all z's and s's can occur together in an optimal string, it's from an analysis of (i.e., staring at) a diagram like the following. (Asterisks are used as arrow heads.)

Code:

.      /^\
       \ *
        s
       * \
      /   \
     /     *
    r*-----*t
     *     /
      \   /
       \ *
        z
       * \
       \_/

If you stare at the diagram for a while it seems obvious that an optimal string can have all z's together and all s's together. I believe this is true even in a circular necklace.

Your English is excellent. Anyone could have misspoke and said combinatronics, especially in a computer context. Combinatorics is a strange word.

opps... sorry for the error in my code. Glad john.c picked it up.

Oh, and yes, I have pretty much the same picture that john.c drew scribbled on a bit of scrap paper. The hard bit is deciding where to start to get the maximum...

I also understand that this wasn't the solution asked for, but I've been doing Project Euler problems for so long that obvious recursive solution with complexity of O(n^2) or something vs the trivial O(1) solution is just too hard to resist.