# Thread: Help with C combinatronics problem

1. ## 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).

2. The correct term is "combinatorics".

3. Originally Posted by john.c
The correct term is "combinatorics".
Yeah sorry :P
This is my sad attempt at this problem

4. I shared my first attempt in the previous post. This is my second and different attempt which works way better but I don't think it's a completely valid solution for this problem.

5. 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);```

6. 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;
}```

7. If you draw a picture of what can follow what (a state diagram), and allow for the fact that you have to end where you can start (so it is a loop) you get

Code:
```necklace_length( t, r, s, e )
if minimum( t, r ) is zero
return minimum( s, e )
else
return s + e + min(t,r)*2```
I'll leave it up to you to code in C.

8. 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.

9. Originally Posted by john.c
Do you have example input/output? Post it.
Example input/output:

s = 12, r = 17, t = 20, e = 20, TOT = 69
RESULT=67

s = 13, r = 11, t = 14, e = 18, TOT = 56
RESULT=54

s = 7, r = 14, t = 12, e = 10, TOT = 43
RESULT=42

s = 13, r = 20, t = 12, e = 17, TOT = 62
RESULT=55

Regarding the solution by hamster_nz, while correct, is not the solution requested. The problem requires a recursive function and is in the context of combinatorics.

10. 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.
John, your solution is most probably what the problem was asking for. Thank you very much! If you don't mind could you please add some comments or a brief explanation of what it does so that I can better understand it and learn from it? Thank you!

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

12. 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.

13. Originally Posted by john.c
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.
The examples are from the problem itself, and my instructor (after I asked) told me that for simplicity the problem assumes the necklace to be just a straight line, so no circle.

Thank you for the explanation, your solution IS pretty straightforward, and your further details helped a lot, since my goal was not to just solve the problem but to learn and better understand how to approach this kind of problems. I really appreciate the time you dedicated to me and my issue.
Also, sorry for my poor English throughout this thread, but it is not my first (nor second) language.

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

15. 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.