0
\$\begingroup\$

Write a function that a receives file name and an integer N as arguments, that represent a binary file which contains N integers, which constitute a permutation. Return the number of cycles in the permutation.

Code

int countCyclesHelper(int* array, int N) {
  int i, first, current, temp, counter = 0;
  for (i = 0; i < N; i++) {
    first = i;
    current = first;
    while (1) {
      if (array[current] == -1) {
        break;
      }
      temp = array[current] - 1;
      array[current] = -1;
      current = temp;
      if (current == first) {
        counter++;
        break;
      }
    }
  } 
  return counter; 
}

int countCycles(char *name, int N) {
  char *buffer = (char*)malloc(N);
  int *array = (int*)malloc(N);
  int i, numberOfCycles;
  FILE *fp = fopen(name, "rb");
  fread(buffer, sizeof(buffer), 1, fp);
  for (i = 0; i < N; i++) {
    array[i] = buffer[i] - '0';
  }
  numberOfCycles = countCyclesHelper(array, N);
  free(buffer);
  free(array);
  fclose(fp);
  return numberOfCycles;
}

Example

Input (test.bin):

54321

Output:

3

Any review is appreciated.

\$\endgroup\$
  • \$\begingroup\$ Do you have a sample input file? \$\endgroup\$ – Josiah Jun 15 '18 at 6:19
  • \$\begingroup\$ @Josiah Edited the question with an example. \$\endgroup\$ – Itay4 Jun 15 '18 at 6:24
2
\$\begingroup\$

Unless you use a very old compiler, I suggest you to declare (and initialize) variables as late as possible and limit their scope. This prevents potential mistakes like

return current; /* whoops, meant counter! */

in countCyclesHelper.

Next, unless you got invalid input, only array[first] may be -1, otherwise one of your nodes in your (implicit) graph has two incoming edges and the original file didn't contain a valid permutation.

If we take both suggestions into account, we end up with the following countCyclesHelper:

int countCyclesHelper(int* array, int N) {
  int total_cycles = 0;

  for (int i = 0; i < N; i++) {
    const int first = i;
    int current = first;

    if (array[current] == -1) {
      /* already counted this cycle */
      continue;
    }

    while (1) {
      const int temp = array[current] - 1;
      array[current] = -1;
      current = temp;
      if (current == first) {
        counter++;
        break;
      }
    }
  } 
  return total_cycles; 
}

While I kept first, it's possible to replace it with i.


As you can see, I've added const at various places. If we don't intend to change a value it's usually a good idea to prevent it with const. This holds for example for your name in countCycles. We don't want to accidentally change the file name:

int countCycles(const char *name, int N)

Next, fread(buffer, sizeof(buffer), …) is—unfortunately—wrong, since buffer is a pointer. You end up with fread(buffer, sizeof(char*), …). Therefore, your program contained undefined behaviour, unless N <= sizeof(char*).

That being said, countCycles is an overkill, since you handle only single digit permutation indices. For any N >= 10the content ofarraywon't be a permutation. With this in mind, we can simplifycountCycles` a lot:

enum { MAXIMUM_DIGITS = 9 };

int countCycles(const char *name, int N) {
  if(N <= 0 || N > MAXIMUM_DIGITS) {
    return -1;
  }

  char buffer[MAXIMUM_DIGITS];

  FILE *fp = fopen(name, "rb");
  if(fread(buffer, N, 1, fp) != N) {
    fclose(fp);
    return -1;
  }
  fclose(fp);

  int array[MAXIMUM_DIGITS];

  for (int i = 0; i < N; i++) {
    array[i] = buffer[i] - '0';
  }
  return countCyclesHelper(array, N);
}

If MAXIMUM_DIGITS gets larger at some point, you probably need to switch to malloc again, but simple arrays with a static size work well enough for your use case.

\$\endgroup\$
2
\$\begingroup\$
  • Do not cast what malloc returns. It may lead to hard to find errors.

  • If N is greater than 256, array cannot constitute a permutation. Otherwise, there is no reason for array to exists; you can operate directly on buffer.

  • It seems that the array indexing is 1-based (if so, it must be clearly stated in the problem statement). The code however treats indexing as 0-based, leading to the very confusing subtraction temp = array[current] - 1.

    A cleaner approach is to explicitly convert the array to 0-based, eg:

    void rebase_to_0(int * array, int N) {
        for (int i = 0; i < N; i++) {
            array[i] -= 1;
        }
    }
    
  • first and i are synonymous; there is no need to have both.

  • You may want to verify that the input indeed represents a permutation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.