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

---

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

Well, I moved combination.h so that it's in the standard directory now.

Quote:

---

Originally Posted by DonFord81

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

I feel stupid. I wasn't incrementing the matrix if no solution was found...

Back to the drawing board, I suppose.

Quote:

---

Originally Posted by DonFord81

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.

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?

Quote:

---

Originally Posted by Sparrowhawk

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.

18+8-1 / 8 ... which evaluates to 1.625

25/8 = 3

Quote:

---

Originally Posted by EVOEx

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 :p

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

---

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.

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?

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?

Quote:

---

Originally Posted by Sparrowhawk

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.

Anyone?

Quote:

---

Originally Posted by DonFord81

Anyone?

---

be patient

1. to zero arrays at the beginning enough to write

Code:

---

        char matrix_array[DIM][BITNSLOTS(DIM)] ={0};
        char U_array[BITNSLOTS(UPPER)] ={0};
        int combination[LOWER]={0};

---

No need to call memset

2.

Code:

---

#define BITMASK(b) (1 << ((b) % CHAR_BIT))

---

What bit do you want to set when b == 1?

3. test_all_zero instead of doing what its name suggests - checks only the

Code:

---

if (BITTEST(bitarray, 0))
                {
                        return 0;
                }
                else
                {
                        return 1;
                }

---

I could not compile and debug your program because some function is missing.

Do you pay attention to the compiler warnings?

The function that's probably missing for you is <combination.h>, which is not standard in the C library. I can include the code snippet I used for it, since I found it on an internet forum for such things.

I changed the test_all_zero code per your suggestion.

Code:

---

int test_all_zero(char* bitarray, int n){
    int i;
    int counter = 0;
    for (i=0; i<n; i++){
        if (!BITTEST(bitarray, i)){
          counter++;
          }
        }
    if (counter == n){
      return (1);
      }
    else{
        return (0);
        }
}

---

And here's the <combination.h> header file:

Code:

---

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

---

However, for DIM = 5 and LOWER = 3, I'm still getting an incorrect answer.

I can't figure out if my for/while loops are even engaging, since it seems that my program block is just getting skipped. Is that what's happening?

I still don't know what the program is doing wrong. I thought it might be something along the lines of having forgotten to run "make_matrix" after every instance of changing U_array, but I've checked the code, and I do run "make_matrix" after every change in U_array, so that's not the problem.

Can anyone please help me?