Last Time with this Program ... I swear!

This is a discussion on Last Time with this Program ... I swear! within the C Programming forums, part of the General Programming Boards category; Okay. I ran this program with MAX = 6, LOWER = 3, and it ran just fine. However, when I ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    38

    Last Time with this Program ... I swear!

    Okay. I ran this program with MAX = 6, LOWER = 3, and it ran just fine. However, when I tried to bump LOWER up to 4 (and made all the appropriate hard-code changes), the program just loves to crash on me. (Yes, it even said so.)

    I'm trying to figure out what's causing the program to crash mid-calculation. It seems like I'm possibly going out-of-bounds on an array somewhere, but I can't figure out why. Perhaps someone here will have a better clue:

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include <limits.h>		/* for CHAR_BIT */
    #include <combination.h>
    
    #define MAX 18
    #define LOWER 4
    #define UPPER (MAX*(MAX-1)/2)
    #define BITMASK(b) (1 << ((b) % CHAR_BIT))
    #define BITSLOT(b) ((b) / CHAR_BIT)
    #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
    #define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
    #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    
    void increment(char* bitarray, int n);
    int test_all_zero(char* bitarray, int n);
    void make_matrix(char [][BITNSLOTS(MAX)], char* U_array, int n);
    void invert(char* bitarray);
    void display(char [][BITNSLOTS(MAX)], int n);
    int check_sum(char* bitarray, int n);
    
    main(){
           char matrix_array[MAX][BITNSLOTS(MAX)];
           int i,j;
           int combination[LOWER];
           int solution_found = 0;
          
           for (i=0; i<MAX; i++){
               memset(matrix_array[i], 0, BITNSLOTS(MAX));
               }
          
           char U_array[BITNSLOTS(UPPER)];
           memset(U_array, 0, BITNSLOTS(UPPER));
    
           while ((check_sum(U_array, UPPER) < LOWER) ||
                  (check_sum(U_array, UPPER) > (UPPER - LOWER))){
                  increment(U_array, UPPER);
                  }
                  
           make_matrix(matrix_array, U_array, MAX);
           for (i=0; i<LOWER; i++){
               combination[i] = i;
               }
           
           char test_array[LOWER][BITNSLOTS(MAX)];
           char intersection[BITNSLOTS(MAX)];
    
           for (i=0; i<LOWER; i++){
               for (j=0; j<UPPER; j++){
                   test_array[i][j] = matrix_array[combination[i]][j];
                   }
               }
           
           /* THIS SECTION HAS TO BE HARD-CODED.  FOR DIFFERENT VALUES
              OF "LOWER," PLEASE CHANGE THE CODE IN THIS SECTION. */
    
           for (i=0; i<BITNSLOTS(MAX); i++){
               intersection[i] = (test_array[0][i] & test_array[1][i] 
                                & test_array[2][i] & test_array[3][i]);
               }
           if (BITTEST(intersection, combination[0]) && 
               BITTEST(intersection, combination[1]) &&
               BITTEST(intersection, combination[2]) &&
               BITTEST(intersection, combination[3])){
               solution_found++;
               }
           else{
                invert(U_array);
                make_matrix(matrix_array, U_array, MAX);
                for (i=0; i<LOWER; i++){
                    for (j=0; j<UPPER; j++){
                        test_array[i][j] = matrix_array[combination[i]][j];
                        }
                    }
                for (i=0; i<BITNSLOTS(MAX); i++){
                    intersection[i] = (test_array[0][i] & test_array[1][i] 
                                     & test_array[2][i] & test_array[3][i]);
                    }
                if (BITTEST(intersection, combination[0]) && 
                    BITTEST(intersection, combination[1]) &&
                    BITTEST(intersection, combination[2]) &&
                    BITTEST(intersection, combination[3])){
                    solution_found++;
                    }
                }
           
           while ((solution_found == 0) && (next_comb(combination, LOWER, MAX))){
                 while ((check_sum(U_array, UPPER) < LOWER) ||
                        (check_sum(U_array, UPPER) > (UPPER - LOWER))){
                        increment(U_array, UPPER);
                        }
                 
                 make_matrix(matrix_array, U_array, MAX);
                 
                 for (i=0; i<LOWER; i++){
                     for (j=0; j<UPPER; j++){
                         test_array[i][j] = matrix_array[combination[i]][j];
                         }
                     }
                     
                 for (i=0; i<BITNSLOTS(MAX); i++){
                     intersection[i] = (test_array[0][i] & test_array[1][i] 
                                      & test_array[2][i] & test_array[3][i]);
                     }
                 if (BITTEST(intersection, combination[0]) && 
                     BITTEST(intersection, combination[1]) &&
                     BITTEST(intersection, combination[2]) &&
                     BITTEST(intersection, combination[3])){
                     solution_found++;
                     }
                 else{
                      invert(U_array);
                      make_matrix(matrix_array, U_array, MAX);
                      for (i=0; i<LOWER; i++){
                          for (j=0; j<UPPER; j++){
                              test_array[i][j] = matrix_array[combination[i]][j];
                              }
                          }
                      for (i=0; i<BITNSLOTS(MAX); i++){
                          intersection[i] = (test_array[0][i] & test_array[1][i] 
                                           & test_array[2][i] & test_array[3][i]);
                          }
                      if (BITTEST(intersection, combination[0]) && 
                          BITTEST(intersection, combination[1]) &&
                          BITTEST(intersection, combination[2]) &&
                          BITTEST(intersection, combination[3])){
                          solution_found++;
                          }
                      }
                 }
           /* END OF HARD-CODE */
    
           
           if (solution_found > 0){
              make_matrix(matrix_array, U_array, MAX);
              display(matrix_array, MAX);
              printf("Solution found.");
              }
           else{
                printf("No solution found.");
                }
           
           getch();
    }
    
    void increment(char* bitarray, int n){
         int i = 0;
         while (i < n){
               if (!BITTEST(bitarray, i)){
                  BITSET(bitarray, i);
                  i = n;
                  }
               else{
                    BITCLEAR(bitarray, i);
                    i++;
                    }
               }
    }
                    
    int test_all_zero(char* bitarray, int n){
        int i;
        for (i=0; i<n; i++){
            if (BITTEST(bitarray, i)){
               return 0;
               }
            else{
                 return 1;
                 }
            }
    }
    
    void invert(char* bitarray){
         int i;
         for (i=0; i<(UPPER/CHAR_BIT)+1; i++){
             bitarray[i] ^= 0xFF;
             }
    }
    
    void make_matrix(char bitarray[][BITNSLOTS(MAX)], char* U_array, int n){
         int i,j,k;
         for (i=0, j=0; i<n; i++, j++){
             BITSET(bitarray[i], j);
             }
         for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
             if (j >= n){
                i++;
                j = i+1;
                }
             if (BITTEST(U_array, k)){
                BITSET(bitarray[i], j);
                BITSET(bitarray[j], i);
                }
             else{
                  BITCLEAR(bitarray[i], j);
                  BITCLEAR(bitarray[j], i);
                  }
             }
    }
    
    void display(char bitarray[][BITNSLOTS(MAX)], int n){
         int i, j;
         for (i=0; i<n; i++){
             for (j=0; j<n; j++){
                 if (BITTEST(bitarray[i], j)){
                    printf("1");
                    }
                 else{
                      printf("0");
                      }
                 }
             printf("\n");
             }
         printf("\n");
    }
    
    int check_sum(char* bitarray, int n){
        int i;
        int sum = 0;
        for (i=0; i<n; i++){
            if (BITTEST(bitarray, i)){
               sum++;
               }
            }
        return sum;
    }
    And here's <combination.h>, since I know someone's going to ask for it:
    Code:
    /* Prints out a combination like {1, 2} */
    void printc(int comb[], int k) {
    	printf("{");
    	int i;
    	for (i = 0; i < k; ++i)
    		printf("%d, ", comb[i] + 1);
    	printf("\b\b}\n");
    }
    
    /*
    	next_comb(int comb[], int k, int n)
    		Generates the next combination of n elements as k after comb
    
    	comb => the previous combination ( use (0, 1, 2, ..., k) for first)
    	k => the size of the subsets to generate
    	n => the size of the original set
    
    	Returns: 1 if a valid combination was found
    		0, otherwise
    */
    int next_comb(int comb[], int k, int n) {
    	int i = k - 1;
    	++comb[i];
    	while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
    		--i;
    		++comb[i];
    	}
    
    	if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
    		return 0; /* No more combinations can be generated */
    
    	/* comb now looks like (..., x, n, n, n, ..., n).
    	Turn it into (..., x, x + 1, x + 2, ...) */
    	for (i = i + 1; i < k; ++i)
    		comb[i] = comb[i - 1] + 1;
    
    	return 1;
    }

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Haven't looked it over but I noticed this:

    #include <combination.h>

    it looks like this is a homebrew header file you made yourself?

    the syntactically correct way is:

    #include "combination.h"

    include with the <> only looks in the standard list of system directories while the quotes "" look in the current directory where your program is in addition to the system directories. This doesn't mean you should use the quotes for everything though

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Well, I moved combination.h so that it's in the standard directory now.

  4. #4
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by DonFord81 View Post
    Well, I moved combination.h so that it's in the standard directory now.
    I believe in that case the best thing to do is to create a new directory in the standard directory and explicitly set it in the angle brackets.
    Code:
    #include <mine/combination.h>
    No confusion that way

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    I feel stupid. I wasn't incrementing the matrix if no solution was found...

    Back to the drawing board, I suppose.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Quote Originally Posted by DonFord81 View Post
    I feel stupid. I wasn't incrementing the matrix if no solution was found...

    Back to the drawing board, I suppose.
    Well there are more problems... The main one being that stuff like:

    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)


    causes undefined behavior... Because your dividing an int... Thus whatever is left is cut off... example: if you do BITNSLOTS(MAX) which you do quite often in the code one example:

    Code:
    char test_array[LOWER][BITNSLOTS(MAX)]
    With MAX = 18 for example, you get 18+8-1 / 8 ... which evaluates to 1.625 but since its treated as an int, the decimal is chopped off and thus is evaluated to 1.

    Then you go on to try to increment far past 0:
    Code:
           for (i=0; i<LOWER; i++){
               for (j=0; j<UPPER; j++){
                   test_array[i][j] = matrix_array[combination[i]][j];
                   }
               }
    here for example... UPPER is evaluated (18*(18-1)/2) when array elements past test_array[i][0] don't exist.


    But that's just one thing... There seemed to be many inconsistencies throughout the program I'm afraid.

    [edit2] - As for it running with MAX 6, LOWER 3... I think it was blind luck again caused by undefined behavior... If you try to run it several times... half the times it works, half the times it goes bonkers... Again pointing to undefined behavior.

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Well, I changed the code, and in the interest of keeping my promise, I'm just re-posting to this note.

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include <limits.h>		/* for CHAR_BIT */
    #include <combination.h>
    
    #define MAX 6
    #define LOWER 3
    #define UPPER (MAX*(MAX-1)/2)
    #define BITMASK(b) (1 << ((b) % CHAR_BIT))
    #define BITSLOT(b) ((b) / CHAR_BIT)
    #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
    #define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
    #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    
    void increment(char* bitarray, int n);
    int test_all_zero(char* bitarray, int n);
    void make_matrix(char [][BITNSLOTS(MAX)], char* U_array, int n);
    void invert(char* bitarray);
    void display(char [][BITNSLOTS(MAX)], int n);
    
    main(){
           char matrix_array[MAX][BITNSLOTS(MAX)];
           char U_array[BITNSLOTS(UPPER)];
           int i,j;
           int combination[LOWER];
           int tests_run = 0;
           int intersections = 0;
           int solutions_found = 0;
          
           for (i=0; i<MAX; i++){
               memset(matrix_array[i], 0, BITNSLOTS(MAX));
               }
           memset(U_array, 0, BITNSLOTS(UPPER));
                  
           for (i=0; i<LOWER; i++){
               combination[i] = i;
               }
    
           make_matrix(matrix_array, U_array, MAX);
           for (i=0; i<LOWER; i++){
               for (j=0; j<LOWER; j++){
                   if (BITTEST(matrix_array[combination[i]], combination[j])){
                      intersections++;
                      }
                   }
               }
           if (intersections == (LOWER*LOWER)){
              intersections = 0;
              solutions_found++;
              }
           else{
                invert(U_array);
                make_matrix(matrix_array, U_array, MAX);
                for (i=0; i<LOWER; i++){
                    for (j=0; j<LOWER; j++){
                        if (BITTEST(matrix_array[combination[i]], combination[j])){
                           intersections++;
                           }
                        }
                    }
                if (intersections == (LOWER*LOWER)){
                   intersections = 0;
                   solutions_found++;
                   }
                }
           tests_run++;
           increment(U_array, UPPER);
           
           while ((!test_all_zero(U_array, UPPER)) && (tests_run == solutions_found)){
                 while (next_comb(combination, LOWER, MAX)){
                       make_matrix(matrix_array, U_array, MAX);
                       for (i=0; i<LOWER; i++){
                           for (j=0; j<LOWER; j++){
                               if (BITTEST(matrix_array[combination[i]], combination[j])){
                               intersections++;
                               }
                           }
                       }
                       if (intersections == (LOWER*LOWER)){
                          intersections = 0;
                          solutions_found++;
                          }
                       else{
                            invert(U_array);
                            make_matrix(matrix_array, U_array, MAX);
                            for (i=0; i<LOWER; i++){
                                for (j=0; j<LOWER; j++){
                                    if (BITTEST(matrix_array[combination[i]], combination[j])){
                                       intersections++;
                                       }
                                    }
                                }
                            if (intersections == (LOWER*LOWER)){
                               intersections = 0;
                               solutions_found++;
                               }
                            }
                 }
                 tests_run++;
                 increment(U_array, UPPER);
           }
           
           if (tests_run != solutions_found){
              printf("r(%d, %d) > %d", LOWER, LOWER, MAX);
              }
           else{
                printf("r(%d, %d) %c %d", LOWER, LOWER, 243, MAX);
                }
           getch();
    }
    
    void increment(char* bitarray, int n){
         int i = 0;
         while (i < n){
               if (!BITTEST(bitarray, i)){
                  BITSET(bitarray, i);
                  i = n;
                  }
               else{
                    BITCLEAR(bitarray, i);
                    i++;
                    }
               }
    }
                    
    int test_all_zero(char* bitarray, int n){
        int i;
        for (i=0; i<n; i++){
            if (BITTEST(bitarray, i)){
               return 0;
               }
            else{
                 return 1;
                 }
            }
    }
    
    void invert(char* bitarray){
         int i;
         for (i=0; i<(UPPER/CHAR_BIT)+1; i++){
             bitarray[i] ^= 0xFF;
             }
    }
    
    void make_matrix(char bitarray[][BITNSLOTS(MAX)], char* U_array, int n){
         int i,j,k;
         for (i=0, j=0; i<n; i++, j++){
             BITSET(bitarray[i], j);
             }
         for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
             if (j >= n){
                i++;
                j = i+1;
                }
             if (BITTEST(U_array, k)){
                BITSET(bitarray[i], j);
                BITSET(bitarray[j], i);
                }
             else{
                  BITCLEAR(bitarray[i], j);
                  BITCLEAR(bitarray[j], i);
                  }
             }
    }
    
    void display(char bitarray[][BITNSLOTS(MAX)], int n){
         int i, j;
         for (i=0; i<n; i++){
             for (j=0; j<n; j++){
                 if (BITTEST(bitarray[i], j)){
                    printf("1");
                    }
                 else{
                      printf("0");
                      }
                 }
             printf("\n");
             }
         printf("\n");
    }
    This time, it consistently gives me that r(LOWER, LOWER) is always greater than MAX. I've even tested this for values that I know it should not be true for (LOWER = 3, MAX = 6).

    I think I've solved the "increment past 0" error, but I could be wrong... help?

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Sparrowhawk View Post
    Well there are more problems... The main one being that stuff like:

    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)


    causes undefined behavior... Because your dividing an int... Thus whatever is left is cut off... example: if you do BITNSLOTS(MAX) which you do quite often in the code one example:

    Code:
    char test_array[LOWER][BITNSLOTS(MAX)]
    With MAX = 18 for example, you get 18+8-1 / 8 ... which evaluates to 1.625 but since its treated as an int, the decimal is chopped off and thus is evaluated to 1.

    Well, I don't even get the "Then you go on to try to increment far past 0", but your post here makes no sense whatsoever. I haven't read the original post, I'm not going to read so much code just to fix a bug.

    So
    Code:
    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    "causes undefined behavior"? How can such a simple expression cause undefined behaviour? I think you mean it wouldn't do whatever he expects. And I agree, I think it should be:
    Code:
    #define BITNSLOTS(nb) (((nb) + CHAR_BIT - 1) / CHAR_BIT)
    But most of the time the original version would work perfectly. It's a perfectly valid way to evaluate ceil(nb / CHAR_BIT) (pseudo-code style, not C style).

    With MAX = 18 for example, you get 18+8-1 / 8 ... which evaluates to 1.625
    I really wonder how you managed to get it here. Let's assume you are right saying it evaluates to 18+8-1/8, that would make it 25.875. However, it actually evaluates to (18+8-1)/8, which is 25/8, which is 3.125. Since it's truncated, the result is 3. Which happens to be ceil(18/8) = ceil(2.25) = 3.

    So I wonder how you manage to get 1.625 out of that.

  9. #9
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    18+8-1 / 8 ... which evaluates to 1.625

    25/8 = 3
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Quote Originally Posted by EVOEx View Post
    Well, I don't even get the "Then you go on to try to increment far past 0", but your post here makes no sense whatsoever. I haven't read the original post, I'm not going to read so much code just to fix a bug.

    So
    Code:
    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    "causes undefined behavior"? How can such a simple expression cause undefined behaviour? I think you mean it wouldn't do whatever he expects. And I agree, I think it should be:
    Code:
    #define BITNSLOTS(nb) (((nb) + CHAR_BIT - 1) / CHAR_BIT)
    But most of the time the original version would work perfectly. It's a perfectly valid way to evaluate ceil(nb / CHAR_BIT) (pseudo-code style, not C style).

    With MAX = 18 for example, you get 18+8-1 / 8 ... which evaluates to 1.625
    I really wonder how you managed to get it here. Let's assume you are right saying it evaluates to 18+8-1/8, that would make it 25.875. However, it actually evaluates to (18+8-1)/8, which is 25/8, which is 3.125. Since it's truncated, the result is 3. Which happens to be ceil(18/8) = ceil(2.25) = 3.

    So I wonder how you manage to get 1.625 out of that.

    Hmm you're definitely right about that I don't know how I got 1.625 from 18+8-1/8... With respect to the rest of what I wrote though, it's pretty irrelevant but I meant more "it doesn't do what he expects" as you said so I misspoke there. Then again I took the time to look at the code and tried to work this out so a lot of things were going in and out of my head with regards to what was going on within the program and I was consciously switching values of MAX and LOWER around to see what happened... Either way the second part still stands that UPPER ends up going too far past. By which I mean if

    Code:
    char test_array[LOWER][BITNSLOTS(MAX)]
    was used and max was lets use the MAX 18 example... so it evalutes to 3. Well UPPER evaluates to (18*(18-1)/2) which is 153, a number much greater than 2. 2 being the last array element.

    Well in his original program he was incrementing the j operator while it was <UPPER(MAX)... while the array elements that j was used to access only went up to BITNSLOTS(MAX).

    Vart-I'm a little disappointed my calculator isn't spitting out a 1.625 to be honest

  11. #11
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Here you go Don, try this code out, compile and run it and you should see the problem

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include <limits.h>		/* for CHAR_BIT */
    #include "combination.h"
    
    #define MAX 6
    #define LOWER 3
    #define UPPER (MAX*(MAX-1)/2)
    #define BITMASK(b) (1 << ((b) % CHAR_BIT))
    #define BITSLOT(b) ((b) / CHAR_BIT)
    #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
    #define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
    #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    
    void increment(char* bitarray, int n);
    int test_all_zero(char* bitarray, int n);
    void make_matrix(char [][BITNSLOTS(MAX)], char* U_array, int n);
    void invert(char* bitarray);
    void display(char [][BITNSLOTS(MAX)], int n);
    
    int main(){
           char matrix_array[MAX][BITNSLOTS(MAX)];
           char U_array[BITNSLOTS(UPPER)];
           int i,j;
           int combination[LOWER];
           int tests_run = 0;
           int intersections = 0;
           int solutions_found = 0;
          
           for (i=0; i<MAX; i++){
               memset(matrix_array[i], 0, BITNSLOTS(MAX));
               }
           memset(U_array, 0, BITNSLOTS(UPPER));
                  
           for (i=0; i<LOWER; i++){
               combination[i] = i;
               }
    
           make_matrix(matrix_array, U_array, MAX);
           for (i=0; i<LOWER; i++){
               for (j=0; j<LOWER; j++){
                   if (BITTEST(matrix_array[combination[i]], combination[j])){
                      intersections++;
    				  printf("intersection 1: %i\n", intersections);
                      }
                   }
               }
           if (intersections == (LOWER*LOWER)){
              intersections = 0;
              solutions_found++;
              }
           else{
                invert(U_array);
                make_matrix(matrix_array, U_array, MAX);
                for (i=0; i<LOWER; i++){
                    for (j=0; j<LOWER; j++){
                        if (BITTEST(matrix_array[combination[i]], combination[j])){
                           intersections++;
    					   printf("intersection 2: %i\n", intersections);
                           }
                        }
                    }
                if (intersections == (LOWER*LOWER)){
                   intersections = 0;
    			   printf("Set inter 0 #1\n");
                   solutions_found++;
                   }
                }
           tests_run++;
           increment(U_array, UPPER);
           
           while ((!test_all_zero(U_array, UPPER)) && (tests_run == solutions_found)){
                 while (next_comb(combination, LOWER, MAX)){
                       make_matrix(matrix_array, U_array, MAX);
                       for (i=0; i<LOWER; i++){
                           for (j=0; j<LOWER; j++){
                               if (BITTEST(matrix_array[combination[i]], combination[j])){
    						   printf("intersection 3: %i\n", intersections);
                               intersections++;
                               }
                           }
                       }
                       if (intersections == (LOWER*LOWER)){
                          intersections = 0;
    					  printf("Set inter 0 #2\n");
                          solutions_found++;
                          }
                       else{
                            invert(U_array);
                            make_matrix(matrix_array, U_array, MAX);
                            for (i=0; i<LOWER; i++){
                                for (j=0; j<LOWER; j++){
                                    if (BITTEST(matrix_array[combination[i]], combination[j])){
    									printf("intersection 4: %i\n", intersections);
                                       intersections++;
                                       }
                                    }
                                }
                            if (intersections == (LOWER*LOWER)){
                               intersections = 0;
    						   printf("Set inter 0 #3\n");
                               solutions_found++;
                               }
                            }
                 }
                 tests_run++;
                 increment(U_array, UPPER);
           }
           
           if (tests_run != solutions_found){
              printf("r(%d, %d) > %d", LOWER, LOWER, MAX);
              }
           else{
                printf("r(%d, %d) %c %d", LOWER, LOWER, 243, MAX);
                }
           getch();
    }
    
    void increment(char* bitarray, int n){
         int i = 0;
         while (i < n){
               if (!BITTEST(bitarray, i)){
                  BITSET(bitarray, i);
                  i = n;
                  }
               else{
                    BITCLEAR(bitarray, i);
                    i++;
                    }
               }
    }
                    
    int test_all_zero(char* bitarray, int n){
        int i;
        for (i=0; i<n; i++){
            if (BITTEST(bitarray, i)){
               return 0;
               }
            else{
                 return 1;
                 }
            }
    }
    
    void invert(char* bitarray){
         int i;
         for (i=0; i<(UPPER/CHAR_BIT)+1; i++){
             bitarray[i] ^= 0xFF;
             }
    }
    
    void make_matrix(char bitarray[][BITNSLOTS(MAX)], char* U_array, int n){
         int i,j,k;
         for (i=0, j=0; i<n; i++, j++){
             BITSET(bitarray[i], j);
             }
         for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
             if (j >= n){
                i++;
                j = i+1;
                }
             if (BITTEST(U_array, k)){
                BITSET(bitarray[i], j);
                BITSET(bitarray[j], i);
                }
             else{
                  BITCLEAR(bitarray[i], j);
                  BITCLEAR(bitarray[j], i);
                  }
             }
    }
    
    void display(char bitarray[][BITNSLOTS(MAX)], int n){
         int i, j;
         for (i=0; i<n; i++){
             for (j=0; j<n; j++){
                 if (BITTEST(bitarray[i], j)){
                    printf("1");
                    }
                 else{
                      printf("0");
                      }
                 }
             printf("\n");
             }
         printf("\n");
    }

  12. #12
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    You're right! That's a pretty big problem there...

    I'm dedicating today to finishing this. And after explaining what I actually want the program to be doing to my professor last night, I think I'm a step ahead.

    Thanks for all your help, guys. I hope to report a working program by the end-of-day.

  13. #13
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    I know this might be just me, but your use of macros makes your program a billion times harder to understand and debug. I try to avoid using them at all costs, except single value versions like #define COM1 0x3F8 etc. What is everyone elses opinion of macros such as the ones he's using here?

  14. #14
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Okay ... *sigh*...

    I've overhauled the program after writing out, in English, what I ideally want the program to do. Here's the "English" version of the program:

    Code:
    zero all arrays;
    create matrix;
    set first combination = "0, 1, 2, 3, 4";
    if this combination fails{
       try next combination;  /* "0, 1, 2, 3, 5", etc. */
       }
       if all possible combinations fail{
          invert matrix;
          set first combination = "0, 1, 2, 3, 4";
          if this combination fails{
             try next combination;
             }
          if all possible inverted combinations fail{
             matrix fails;
             "r(LOWER, LOWER) > DIM";
             end program;
             }
          }
       }
    else{
         increment matrix;
         start all over again;
         }
    
    if program does not find a failure{
       "r(LOWER, LOWER) ≤ DIM";
       end program;
       }
    And, here's the code I've written:
    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include <limits.h>		/* for CHAR_BIT */
    #include <combination.h>
    
    #define DIM 6
    #define LOWER 3
    #define UPPER (DIM*(DIM-1)/2)
    #define BITMASK(b) (1 << ((b) % CHAR_BIT))
    #define BITSLOT(b) ((b) / CHAR_BIT)
    #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
    #define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
    #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    
    void increment(char* bitarray, int n);
    int test_all_zero(char* bitarray, int n);
    void make_matrix(char [][BITNSLOTS(DIM)], char* U_array, int n);
    void invert(char* bitarray);
    void display(char [][BITNSLOTS(DIM)], int n);
    
    int main(){
               char matrix_array[DIM][BITNSLOTS(DIM)];
               char U_array[BITNSLOTS(UPPER)];
               int i,j;
               int combination[LOWER];
          
               for (i=0; i<DIM; i++){
                   memset(matrix_array[i], 0, BITNSLOTS(DIM));
                   }
               memset(U_array, 0, BITNSLOTS(UPPER));
    
               start:
    /* Since the all-zero matrix will suffice to solve the problem... */
               increment(U_array, UPPER);
               while (!test_all_zero(U_array, UPPER)){
                     make_matrix(matrix_array, U_array, DIM);
                     for (i=0; i<LOWER; i++){
                         combination[i] = i;
                         }
                     for (i=0; i<LOWER; i++){
                         for (j=0; j<LOWER; j++){
                             if (!BITTEST(matrix_array[combination[i]], combination[j])){
                                while (next_comb(combination, LOWER, UPPER)){
                                      for (i=0; i<LOWER; i++){
                                          for (j=0; j<LOWER; j++){
                                              if (!BITTEST(matrix_array[combination[i]], combination[j])){
                                                 continue;
                                                 }
                                              else{
                                                   goto start;
                                                   }
                                              }
                                          }
                                      }
                                invert(U_array);
                                make_matrix(matrix_array, U_array, DIM);
                                for (i=0; i<LOWER; i++){
                                    combination[i] = i;
                                    }
                                for (i=0; i<LOWER; i++){
                                    for (j=0; j<LOWER; j++){
                                        if (!BITTEST(matrix_array[combination[i]], combination[j])){
                                           while (next_comb(combination, LOWER, UPPER)){
                                                 for (i=0; i<LOWER; i++){
                                                     for (j=0; j<LOWER; j++){
                                                         if (!BITTEST(matrix_array[combination[i]], combination[j])){
                                                            continue;
                                                            }
                                                         else{
                                                              invert(U_array);
                                                              goto start;
                                                              }
                                                         }
                                                     }
                                                 }
                                           printf("r(%d, %d) > %d", LOWER, LOWER, DIM);
                                           getch();
                                           return (0);
                                        }
                                        else{
                                             invert(U_array);
                                             goto start;
                                             }
                                    }
                                }
                             }
                             else{
                                  goto start;
                                  }
                         }
                     }
               }
               printf("r(%d, %d) %c %d", LOWER, LOWER, 243, DIM);        
               getch();
               return (1);
    }
    
    void increment(char* bitarray, int n){
         int i = 0;
         while (i < n){
               if (!BITTEST(bitarray, i)){
                  BITSET(bitarray, i);
                  i = n;
                  }
               else{
                    BITCLEAR(bitarray, i);
                    i++;
                    }
               }
    }
                    
    int test_all_zero(char* bitarray, int n){
        int i;
        for (i=0; i<n; i++){
            if (BITTEST(bitarray, i)){
               return 0;
               }
            else{
                 return 1;
                 }
            }
    }
    
    void invert(char* bitarray){
         int i;
         for (i=0; i<(UPPER/CHAR_BIT)+1; i++){
             bitarray[i] ^= 0xFF;
             }
    }
    
    void make_matrix(char bitarray[][BITNSLOTS(DIM)], char* U_array, int n){
         int i,j,k;
         for (i=0, j=0; i<n; i++, j++){
             BITSET(bitarray[i], j);
             }
         for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
             if (j >= n){
                i++;
                j = i+1;
                }
             if (BITTEST(U_array, k)){
                BITSET(bitarray[i], j);
                BITSET(bitarray[j], i);
                }
             else{
                  BITCLEAR(bitarray[i], j);
                  BITCLEAR(bitarray[j], i);
                  }
             }
    }
    
    void display(char bitarray[][BITNSLOTS(DIM)], int n){
         int i, j;
         for (i=0; i<n; i++){
             for (j=0; j<n; j++){
                 if (BITTEST(bitarray[i], j)){
                    printf("1");
                    }
                 else{
                      printf("0");
                      }
                 }
             printf("\n");
             }
         printf("\n");
    }
    Now, the program keeps returning the "fail" statement, when I know it should be returning the "success" statement.

    What am I doing wrong now?

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Sparrowhawk View Post
    Well there are more problems... The main one being that stuff like:

    #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
    For furure reference, adding denominator-minus-one to the numerator before division, is the standard way of rounding upwards when doing integer division.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple program closing at end, no time to read...
    By Jake.c in forum C Programming
    Replies: 8
    Last Post: 09-08-2008, 02:20 PM
  2. help with basic program
    By JOlszewski in forum C Programming
    Replies: 3
    Last Post: 02-01-2006, 03:19 PM
  3. program not working...please look at this
    By JOlszewski in forum C Programming
    Replies: 3
    Last Post: 01-30-2006, 09:33 PM
  4. Replies: 3
    Last Post: 03-21-2004, 05:02 PM
  5. worst time to program
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 06-10-2002, 11:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21