Number Puzzle Assignment

[brendono978]

Hi everybody. I decided to make an account here because I could use some help writing some code. This is what I need to do:

Write a C program that will read in two lines of data. The first data line contains an integer N and the second data line contains N different positive integers. The program should arrange these integers so that every number that is less than or equal to N occurs in its proper numeric place and all other numbers are in increasing order. You may assume that N <= 20. The data should be read into your program via calls to the fscanf function. The name of the data is located on the command line as argv[1].

Example: If the input is

7
2 7 8 1 20 9 5

The output would be: 1 2 8 9 5 20 7

Now, I know that I could sort the numbers into increasing order using a bubble sort, and I know that I could sort them all in numeric order by reading them into an array and then printing them from within a for loop, but I am confused as to how to do both at the same time.

[Martin B]

I don't think you should sort.
Use two arrays. Read the numbers into the first array, and then scan it N times, looking for numbers to add to the second array:

unsigned int n;
for (n = 1; n <= N; n++) {
}

In each scan you are looking for one of:
1. n itself
2. The least number greater than those you have already added to the second array (you need to keep track of the highest one you have added so far).

You then add this number to the second array.

[Adak]

I'll be the contrarian, and go with

read in pivot number

if(number <= pivot) {
  deal with it
}
else {
  deal with it
}

If you want to sort - then sort, but only sort the numbers that should be sorted - so having two arrays (one for not sorting, and one for sorting), is a good idea.

[brendono978]

Right, but they all need to be in one array in order to be printed correctly.

[Martin B]

Right, but they all need to be in one array in order to be printed correctly.

The algorithm I'm suggesting does put them all in the second array.

You could perform the algorithm and write the results to the original array.
In fact, that would be better because each scan would then be 1 shorter than the last.

[Adak]

No, they don't need to be all in one array to be printed correctly. This is your world (the data, the structures you choose, etc), and you can set it up as you wish.

Make it accurate, efficient and clear.

[Martin B]

The algorithm I'm suggesting does put them all in the second array.

You could perform the algorithm and write the results to the original array.
In fact, that would be better because each scan would then be 1 shorter than the last.

Oh, and another advantage of overwriting the original array is that you no longer have to keep track of the maximum number you have found; all the remaining numbers are greater.

[brendono978]

Well, I wrote it as best as I could. Now I'm getting a segmentation fault. Any ideas?\

/********************************************/
/* Programmer: Brendon O'Connell            */
/*                                          */
/* Program 61: Number Puzzle                */
/*                                          */
/* Approximate Completion Time: x minutes   */
/********************************************/

#include <stdio.h>

#include <stdlib.h>

void swap( int *a, int *b ) {

  int temp = *a ;

  *a = *b ;

  *b = temp ;

}

int main( int argc, char *argv[] ) {

  FILE* fin ;

  FILE* fin2 ;

  int i, N ;

  int *a, *b ;

  fin = fopen( argv[1], "r" ) ;

  fin2 = fopen( argv[2], "r" ) ;

  printf( "Please enter the number of integers that you wish to enter." ) ;

  fscanf( fin, "%d" , &N ) ;

  a = ( int * ) malloc ( sizeof( int ) * N ) ; 

  b = ( int * ) malloc ( sizeof( int ) * N ) ;

  printf( "Please enter your integers." ) ;

  for( i = 0 ; i <= N ; i++ ) {

    fscanf( fin2, "%d", &a[i] ) ;

    }

  for( i = 0 ; i <= N ; i++ ) {

    if( a[i] <= N ) a[i] = b[i] ;

    else if( a[i] < a[ (i - 1) ] ) swap( &a[i], &a[ (i - 1) ] ) ;

  }

  return 0 ;

  fclose( fin ) ;

}

[brendono978]

Anybody?

[Adak]

Right off, <=N is a fault, overrunning the boundary of the array. Just < N.

fclose(fin) goes before the return 0 ;)

From your description in post #1, it seems your output should:

1 2 5 7 8 20 9

That brings all numbers less than == 7, into sorted order, and leaves the numbers greater than 7, in their original order.

Please clarify.

[brendono978]

So basically I want to do something like this in my second for loop:

if( a[i] < N ) bubblesort( a[i] ) = b[i] ;

else a[i] = b[i] ;

Right?

[Adak]

This is my take on your program. It has some subtleties in it, that are hard to explain, in text. Especially, the part where numbers are moved over to the b[] array.

I put in notes for what I found wrong, as much as possible. Some things, I just had to change, rather than tweak.

/********************************************/
/* Programmer: Brendon O'Connell            */
/*                                          */
/* Program 61: Number Puzzle                */
/*                                          */
/* Approximate Completion Time: x minutes   */
/********************************************/

#include <stdio.h>
#include <stdlib.h>


void swap( int *b, int i, int j ) {
  int temp = b[i];
  b[i] = b[j];
  b[j] = temp ;
}

int main( int argc, char *argv[] ) {
  FILE* fin ;
  int i, j, k, N, temp ;
  int *a, *b ;

  strcpy(argv[1], "brendon.txt"); //change as needed. Done for my convenience
  fin = fopen( argv[1], "r" ) ;
  
  //don't ask the user to enter something, and then 
  //have that something, read from a file
  fscanf( fin, "%d" , &N ) ;

  /* calloc sets the array values to all 0's - malloc doesn't */
  a = calloc ( sizeof( int ) * N, 10 ) ;  //no cast is needed in C
  b = calloc ( sizeof( int ) * N, 10 ) ;

  printf( "\n\n\n\n Reading %d integers.", N ) ;
  for( i = 0 ; i < N ; i++ ) {     //<N, not <=N
    fscanf( fin, "%d", &a[i] ) ;  //not fin2
  }

  //check the input
  printf("\n\n Original input a[]: ");
  for(i=0;i<N;i++)
    printf(" %2d ", a[i]);

  
  for( i = 0, j=0; i < N ; i++ ) {  //<, not <=
    if( a[i] <=N )       //yes, <= is needed here       
      b[j++] = a[i];     //not a[i] = b[i]
  }
  k=j;  //save the value of j;
  printf("\n\n Before sorting b[]: ");
  for(i=0;i<N;i++)
    printf(" %2d ", b[i]);

  //now sort b[]
  for(i=0;i<k-1;i++) {
    for(j=i+1;j<k;j++) {
      if(b[i] > b[j]) 
        swap(b, i, j);
    }
  }
  printf("\n\n  After sorting b[]: ");
  for(i=0;i<N;i++)
    printf(" %2d ", b[i]);

  /*
    now add a[] elements THAT HAVE VALUE > N, into the tail end of 
    b[], in their same order they're in, in a[i]. The first value to
    go into b[], will go in at b[++k].
  */

  for(i=0;i<N;i++) {
    if(a[i] > N) 
      b[k++] = a[i];
  }
  printf("\n\n       Final output: ");
  for(i=0;i<N;i++)
    printf(" %2d ", b[i]);

  printf("\n\n\n");
  fclose( fin );
  (void) getchar();
  return 0 ;

}
/*
Write a C program that will read in two lines of data. The first data line contains an integer N and the second data line contains N different positive integers. The program should arrange these integers so that every number that is less than or equal to N occurs in its proper numeric place and all other numbers are in increasing order. You may assume that N <= 20. The data should be read into your program via calls to the fscanf function. The name of the data is located on the command line as argv[1].

Example: If the input is

7
2 7 8 1 20 9 5

The output would be: 1 2 8 9 5 20 7 <<== wrong I believe
the output would be: 1 2 5 7 8 20 9
*/

BTW, this kind of code, even with 20 numbers, will be done in 1 second or less, on any modern PC.

[Martin B]

This isn't answering the original requirement. The numbers > N don't go at the end of the array, they go in between the numbers <= N, which are in their "proper place", i.e., 1 first, 2 second, 7 seventh.

brendono978 has given the correct output in his first post. 1, 2, 5 and 7 are in their "proper place". The rest are sorted.

1 2 8 9 5 20 7

[Martin B]

My program, which produces the correct output, permutes the array as follows:

2 7 8 1 20 9 5
1 7 8 2 20 9 5
1 2 8 7 20 9 5
1 2 8 7 20 9 5
1 2 8 9 20 7 5
1 2 8 9 5 7 20
1 2 8 9 5 20 7

Note that the array is being arranged from left to right.

[Adak]

Array indeces in C begin with zero, not one.

If Brendon has any problems tweaking the program I posted, to affect that logic, he'll let me know.

Thanks for the explanation.

[Martin B]

Array indeces in C begin with zero, not one.

"Proper place" is in terms of the word problem, not the C problem.

[brendono978]

Array indeces in C begin with zero, not one.

If Brendon has any problems tweaking the program I posted, to affect that logic, he'll let me know.

Thanks for the explanation.

Uh, actually, I do. Your program is, well, honestly, overly complicated, and prints out the incorrect answer. I found a much easier way to achieve the same output using four arrays.

/***************************************************/
/* Programmer: Brendon O'Connell                   */
/*                                                 */
/* Program 61: Number Puzzle                       */
/*                                                 */
/* Approximate Completion Time: 180 minutes        */
/***************************************************/

#include <stdio.h>

#include <stdlib.h>

void bubblesort( int a[], int N ) {

  int temp, i, j ;

  for( i = 0 ; i < N ; i++ ) {

    for( j = 0 ; j < (N - 1) ; j++ ) {

      if( a[j] > a[j+1] ) {
       
	temp = a[j] ;

	a[j] = a[j+1] ;

	a[j+1] = temp ;

  }

}

}

}

int main( int argc, char *argv[] ) {

  FILE* fin ;

  int i, N, j = 0, l = 0 ;

  int *a, *b, *c, *d ;

  fin = fopen( argv[1], "r" ) ;

  fscanf( fin, "%d" , &N ) ;

  a = ( int * ) malloc ( sizeof( int ) * N ) ; 

  b = ( int * ) malloc ( sizeof( int ) * N ) ;

  c = ( int * ) malloc ( sizeof( int ) * N ) ;

  d = ( int * ) malloc ( sizeof( int ) * N ) ;

  for( i = 0 ; i < N ; i++ ) {

    fscanf( fin, "%d", &a[i] ) ;

  }

  for( i = 0 ; i < N ; i++ ) {

    if( a[i] <= N ) {

      b[ ( a[i] - 1 ) ] = a[i] ;

    }

    else if( a[i] > N ) {

      c[j] = a[i] ;

      j++ ;

    }

  }

  bubblesort( c, j ) ;

  for( i = 0; i < N ; i++ ) {

    d[i] = b[i] ;

    if( d[i] == 0 ) {

      d[i] = c[l] ;

      l++ ;

    }

  }

  for( i = 0; i < N ; i++ ) {

    printf( " %d ", d[i] ) ;

    } 

  fclose( fin ) ;

  return 0 ;

}

[Adak]

When you don't accurately and unambiguously define the assignment, the answers you get back are not going to be all correct.

Congrats to Martin B. He was able to decipher and define the assignment, correctly.

[brendono978]

I'm pretty sure it was very clearly defined. So please, stop making excuses; this thread is solved.

[Adak]

You called a matching assignment "sorting", in your description of the problem.

When you are assigning a number to the element with a matching index, that is a matching assignment, NOT a sorting. And THAT'S where I went wrong.

I tweaked YOUR code, using YOUR description. Considering that it was free, and timely, you might have the courtesy to say thanks for trying.

[brendono978]

Oh, I apologize, I thought I had already thanked you. Thanks for trying, and my bad for giving you a bad description.