Thread: Help with C combinatronics problem

  1. #1
    Registered User
    Join Date
    Nov 2021
    Posts
    9

    Lightbulb 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).
    Last edited by ihaterecursion; 11-25-2021 at 05:17 PM. Reason: typo

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,239
    The correct term is "combinatorics".
    Post your brute force solution.
    Your logic makes me feel like a dick. - Bob Fossil

  3. #3
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    Quote Originally Posted by john.c View Post
    The correct term is "combinatorics".
    Post your brute force solution.
    Yeah sorry :P
    This is my sad attempt at this problem
    Last edited by ihaterecursion; 11-25-2021 at 06:31 PM. Reason: posted on pastebin

  4. #4
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    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. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    1,239
    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);
    Last edited by john.c; 11-25-2021 at 07:42 PM.
    Your logic makes me feel like a dick. - Bob Fossil

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,239
    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;
    }
    Your logic makes me feel like a dick. - Bob Fossil

  7. #7
    Registered User
    Join Date
    Sep 2020
    Posts
    301
    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. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    1,239
    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.
    Your logic makes me feel like a dick. - Bob Fossil

  9. #9
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    Quote Originally Posted by john.c View Post
    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. #10
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    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. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,377
    Best to clarify the "necklace" with your instructor before settling on a solution.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Dec 2017
    Posts
    1,239
    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 logic makes me feel like a dick. - Bob Fossil

  13. #13
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    Quote Originally Posted by john.c View Post
    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. #14
    Registered User
    Join Date
    Dec 2017
    Posts
    1,239
    Your English is excellent. Anyone could have misspoke and said combinatronics, especially in a computer context. Combinatorics is a strange word.
    Your logic makes me feel like a dick. - Bob Fossil

  15. #15
    Registered User
    Join Date
    Sep 2020
    Posts
    301
    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.
    Last edited by hamster_nz; 11-26-2021 at 10:33 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-09-2014, 06:46 PM
  2. Problem passing argument into function, basic problem
    By tsdad in forum C++ Programming
    Replies: 7
    Last Post: 05-22-2013, 12:09 PM
  3. Replies: 2
    Last Post: 01-06-2013, 07:49 AM
  4. Replies: 1
    Last Post: 12-07-2012, 10:00 AM
  5. Replies: 4
    Last Post: 10-16-2008, 07:30 PM

Tags for this Thread