Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Pointers

realloc

  • Please log in to reply
22 replies to this topic

#13 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 20 March 2010 - 05:40 AM

I dont think that is it. I tried it but same error. What i realise is that happens the first time i call the realloc function. Lets say i had set that long pointer to hold 40 long values. It is on the first call i make to adjust the array to size 41 it fails. It does not get pass that.
  • 0

#14 dargueta

dargueta

    I chown trolls.

  • Moderator
  • 4854 posts
  • Programming Language:C, Java, C++, PHP, Python, JavaScript, Perl, Assembly, Bash, Others
  • Learning:Objective-C

Posted 20 March 2010 - 07:21 AM

Oooh, a challenge. I like these. Gimme a bit and I'll figure something else out that won't work. :D
  • 0

sudo rm -rf / && echo $'Sanitize your inputs!'


#15 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 20 March 2010 - 07:29 AM

LOL. Like the enthusiasm. I spent a lot of time on this and still haven't figured it out.
  • 0

#16 dargueta

dargueta

    I chown trolls.

  • Moderator
  • 4854 posts
  • Programming Language:C, Java, C++, PHP, Python, JavaScript, Perl, Assembly, Bash, Others
  • Learning:Objective-C

Posted 21 March 2010 - 04:30 PM

Wild guess...make atracker unsigned, along with anything else that doesn't absolutely have to be able to take a negative value.
  • 0

sudo rm -rf / && echo $'Sanitize your inputs!'


#17 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 21 March 2010 - 06:31 PM

***SIGHHHH***** No luck still... I think i have to rethink my approach towards solving this problem. I made some other changes and tested on a windows box and it ran without the segmentation error but my row was incorrect from the exact column where i was getting the segment error on my linux box. The error lies in realloc.

This is the scenario

Let * equal 1 chunk of memory, say.

//allocate storage for 3 rows of pointers
//unsigned long **Array;

Array = malloc( (x_size + 2) * sizeof(long *));

//then allocate storage for an array of long values
for (i = 0; i < (x_size + 2); i++)
    {
        Array[i] = malloc( (y_size + 1) * sizeof(long));
    }

//No i am going to assume it all looks something like this in memory

Array[1]**************************
Array[2]**************************
Array[3]**************************

//What i want to do is increase the lenght of any particular array at any point in time
//it could then probably look like this 

Array[1]**************************
Array[2]**************************************************
Array[3]**************************************************************

/*but now I'm wondering if realloc cannot create the required space for a particular row
what happens then. I think in a 1D Array it would move the entire chunk into new 
location if it could not create the entire space in from that initial memory 
position. So Im wondering now if the long pointers are bounded within that start 
position since it is an array of pointers. Lets say Array[2] could not realloc further
 from that point....what would happen..Bare in mind this program crashes before 
realloc returns and the pointer going into realloc in never null(i think). 
*/


This assignment is long over due. So ill get back to it some other time. I wont suggest you waste any more time on it. Thanks for the help...
  • 0

#18 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 24 March 2010 - 07:44 PM

The problem is the same as before. This time i will describe the entire thing. I managed to get pass the realloc problem. For some reason now the program only works for the first two test input. after that the result is wrong. The result is the amount of entries in the last row. Here is the problem:

Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created. 

For example, consider stamps whose values are limited to 1 cent and 3 cents and suppose that you can use at most 5 stamps. It's easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren't much harder: 
6 = 2*3 
7 = 2*3+1 
8 = 2*3+2*1 
9 = 3*3 
10 = 3*3+1 
11 = 3*3+2*1 
12 = 4*3 
13 = 4*3+1. 
However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13. 

The first line of the input file has K, the total number of stamps that can be used, followed by N, the number of stamp values. The second and subsequent lines list all the N stamp values, 15 per line. Your job is to compute and print M, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set. 

You may assume that 1 <= N <= 500 and 1 <= K <= 500. No stamp value will exceed 10,000. Long integers (signed 32-bit) will be adequate for all solutions.
 
------------------------------------ 
20 1 
1 
 
Ans: 20 
------------------------------------- 
40 3 
1 2 5 
 
Ans: 197 
-------------------  ------------------ 
6 10 
1 2 9 31 255 480 4 15 63 127 
 
Ans: 720 
------------------------------------- 
334 14 
1 2 4 15 9 31 63 2100 3500 127 255 511 1000 1999 
 
Ans: 1151938

This is my attemp thus far:

//using the coin problem approach to solve this problem

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

#define MaxSize 500
#define true 1
#define false -1;


long getMinimum(long t1, long t2)
{    
    if (t1 > t2)         
        return t2;    
    return t1;
}

void initializeArray(unsigned long **a,long xsize, long ysize)
{    //xsize = the amount of different numbers; each in its own row
    //ysize = the number limit. Used for now. we will dynamically allocate the rest
    // set row 1 to the column value
    //set the first row and first column to 0
    //set everthing else to -1(null)
    
    printf("In initialise--->xsize: %ld, ysize: %ld\n",xsize,ysize);
    long i,j;
    long count = 0;
    for(i = 0; i <= xsize; i++){
        for(j = 0; j <= ysize; j++)
        {                            
                if (i == 1 && j != 0) //if row 1 set to j                                    
                    a[i][j] = j;                    
                else    
                if (i == 0 || j == 0)  //if row 0 or col 0 set to 0                
                    a[i][j] = 0;
                else                
                    a[i][j] = -1;                
        }    
    }
}


void mergeSort(int A[],int lo,int hi){
  void merge(int [],int ,int, int);
  if (lo < hi){
     long mid = (lo + hi) / 2;  //get the midpoint subscript
     mergeSort(A,lo,mid);      //sort first half
     mergeSort(A,mid+1,hi);    //sort second half
     merge(A,lo,mid,hi);      //merge sorted halves
     }
}
void merge(int A[],int lo,int mid,int hi)
{
  //A[lo..mid] and A[mid+1..hi] are sorted;
  //merge the pieces so that A[lo..hi] are sorted;
    static long T[MaxSize];
    long i = lo;
    long j = mid + 1;
    long k = lo;
  
    while (i <=mid || j <= hi)
    {
        if (i > mid) T[k++] = A[j++];     //A[lo..mid] completely processed
        else if (j > hi) T[k++] = A[i++]; //A[mid+1..hi] completely processed
        else if (A[i] < A[j]) T[k++] = A[i++]; //neither part completed
        else T[k++] = A[j++];
    }
    for(j = lo; j <=hi; j++) A[j] = T[j]; //copy merge elements back to A  
}


void initializeArray_1d(int A[], long lo, long hi, long value)
{
    int i;
    for ( i = 0; i < hi; i++)
        A[i] = value;
}

int main()
{
    FILE * pFile;
    unsigned long **a;     /* this is the array name */
    int *A_count;  //used to keep track of the amount on a given row
    long x_size, y_size, hold, value;
    int temp_array[MaxSize];    //used to hold stamp values
    int i, j ;
    pFile = fopen("INPUTC.txt","r");
    if(pFile == NULL)
        perror ("The following error occurred: ");
        
    fscanf(pFile,"%ld",&y_size);
    fscanf(pFile,"%ld",&x_size); 
    
    //make space for an array of size x_size to keep track of how many items on each row
    A_count = malloc( (x_size + 1) * sizeof(int));   
    
    //set 1 to x_size to y_size. This will increase as the array grows
    for(i = 0; i <= x_size; i++){
          if (i > 0 && i <= x_size) A_count[i] = y_size;
          else A_count[i] = 0;
          //printf("A_count[%d] = %d\n",i,A_count[i]);
          }
    
    printf("xsize: %ld, ysize: %ld\n",x_size,y_size);
    
    /*  allocate storage for an array of pointers*/
    a = malloc( (x_size + 1) * sizeof(long *));        
    
    /* for each pointer, allocate storage for an array of long values */
    for (i = 0; i < (x_size + 1); i++)
        a[i] = malloc( (y_size + 1) * sizeof(long));
    

    /* Initialise all arrays */
    initializeArray_1d(temp_array,0,MaxSize,32000);        
    initializeArray(a,x_size,y_size);
    
    //Load stamp values in temp_array 
    temp_array[0] = 0;
    for(i = 1; i <= x_size; i++)    
        fscanf(pFile,"%d",&temp_array[i]); 
        
    //sort temp_array
    mergeSort(temp_array,0,MaxSize -1 );  
    
   /* printf("printing the contents of temp_array\n");
    for(i = 0; i <= x_size; i++)
        printf("temparray[%d]: %d  \n",i,temp_array[i]);*/
        
    printf("\n");        
    
    for(i = 2; i <= x_size; i++)
    {
        /* For every row: calculate the amount of coins needed to make the jth(column) value.
         * When a value greater than j is found stop processing that row; this means that the item in just before
         * the jth one would represent the max unbroken list using only K amount of stamps.
         */
          hold = 0;
          j = 0;
          while (hold <= y_size)//iterate through each row until an invalid value is found
          {
                if (j > 0)  //put value into array from second pass onward                
                   a[i][j - 1] = hold;                   
                             
                if(j <= y_size) //we dont make a new entry
                {
                    if (j - temp_array[i] < 0) hold = a[i - 1][j];
                        else
                            hold = getMinimum ( a[i - 1][j] , a[i][j - temp_array[i]] + 1);                            
                }
                else
                if(j > y_size) //we make a new entry
                {
                    if (A_count[i - 1] >= j)  //considering the case where there exist a value directly above
                    {
                        //printf("toplow--> i: %d ->> %d vs %d; hold: %ld\n",i,A_count[i-1],j,hold);                  
                        if (j - temp_array[i] < 0) hold = a[i - 1][j];
                        else
                            hold = getMinimum ( a[i - 1][j] , a[i][j - temp_array[i]] + 1);
                            
                        a[i] = realloc(a[i], (j + 1) * sizeof(long));                        
                    }
                    else
                    {    
                        hold =  a[i][j - temp_array[i]] + 1;                     
                        a[i] = realloc(a[i], (j + 1) * sizeof(long));   
                    } 
                    if (hold <= y_size ) A_count[i] = A_count[i] + 1; 
                }                    
                j++;
          }         
    }

    for(i = 0; i <= x_size; i++)
    {
        for (j = 0; j <= A_count[i] ; j++)
            printf("%2ld ",a[i][j]);
        printf("\nrow %d above\n",i);
    }
    
    /* The answer would be the amount of values in the last row*/
    printf("sizeof A_count[%ld]: %d\n",x_size,A_count[x_size]);
    
    for (i = 0; i <= x_size; i++) 
        free(a[i]);    
    free(a);
    
    return 0;
}
Help needed
  • 0

#19 dargueta

dargueta

    I chown trolls.

  • Moderator
  • 4854 posts
  • Programming Language:C, Java, C++, PHP, Python, JavaScript, Perl, Assembly, Bash, Others
  • Learning:Objective-C

Posted 24 March 2010 - 07:57 PM

How am I supposed to interpret the output? I tried 20 and 1 and it gives me this:
xsize: 1, ysize: 20
In initialise--->xsize: 1, ysize: 20

 0 
row 0 above
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 
row 1 above
sizeof A_count[1]: 20

  • 0

sudo rm -rf / && echo $'Sanitize your inputs!'


#20 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 25 March 2010 - 03:45 AM

The only line that matters in the output is:
sizeof A_count[1]: 20

The rest is just debugging and tracking info i printed. You can comment out the rest.

In the explanation of the the problem above this is an example of the input and output:

SAMPLE INPUT (file INPUT.TXT):
5 2
1 3

SAMPLE OUTPUT (file OUTPUT.TXT):
13

where 5 is the amount of stamps you are allowed to use, 2 is the amount of different stamp values and 1 and 3 are the actual stamp values.

for example
40 3
1 6 10

would mean: use no more than 40 stamps, there are three different stamps and they are 1 6 10. Sorry about the confusion
  • 0

#21 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 25 March 2010 - 04:32 AM

Maybe i shoud be a bit more discriptive. My approach uses two arrays. One to hold the stamp values and one a 2d array to represent a table im trying to fill

example stamps[3]:1 6 10

would represent the three values in the stamp value array.

The other is a table that will give the best possible way to fill any position in the table

e.g.

   j  1  2  3  4  5  6  7  8  9  10  11  12
1 0  0  0  0  0  0  0  0  0  0   0    0   0

so the best way to make zero stamps. (the row) is using zero stamps

   j  1  2  3  4  5  6  7  8  9  10  11  12
0 0  0  0  0  0  0  0  0  0  0   0    0   0
1 0  1  2  3  4  5  6  7  8  9  10  11  12

the best way to make 1 to 12 stamps would be values from 1 to 12 since we only use the 1stamp to make each item.

   j  1  2  3  4  5  6  7  8  9   10  11  12
 0 0  0  0  0  0  0  0  0  0  0    0    0   0
1 0  1  2  3  4  5  6  7  8  9   10  11  12
2 0  1  2  3  4  5  1  2  3  4    5    6   2 
Now how did i get row 2. Simple.

I take the minimum value between table[2 - 1][j] (if it exist) and table[2][j - data[2]] + 1

so the algorithm would run like
int fillTable(int table[][max], int ,int){
          if (i == 1) return j; //fill row 1
          if (j - data[i] < 0) return table[i-1][j];
          return minimum(table[i-1][j], table[i][j - data[i]] + 1);
}
This is all fine for a static table. But for this problem

The max stamps i can with stamp values 1 , 6, 10 using only the 1stamp and a max of 20 stamps is 20. but if i can use lets say 1stamp and 6stamp then i may be able to make even greater values. Likewise if i can use all the stamps while remaining between 20stamps total used i can make even greater values. So row 1 may stop a 20, but row 2 may go all the way up to 40 and three maybe and even greater number.

If we look at row two we will see that for any j the best way to make that value using the given stamps uses x amount of stamps..and i can use back tracking to figure out how much of each stamp i used.
  • 0

#22 dargueta

dargueta

    I chown trolls.

  • Moderator
  • 4854 posts
  • Programming Language:C, Java, C++, PHP, Python, JavaScript, Perl, Assembly, Bash, Others
  • Learning:Objective-C

Posted 25 March 2010 - 11:03 AM

Oooh. Okay. So what's an input that breaks your program?
  • 0

sudo rm -rf / && echo $'Sanitize your inputs!'


#23 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 25 March 2010 - 04:31 PM

It will work with

20 1
1

Ans: 20

or this

40 3
1 2 5

Ans: 197


but not this
6 10
1 2 9 31 255 480 4 15 63 127

Ans: 720
-------------------------------------

This one in particular

6 10
1 2 9 31 255 480 4 15 63 127


Ans: 720

i get a result of 707 and not 720. Now if it works fine for this first two.
I know the algorithm works. But some where as array sizes and values increase things
get fuzzy
  • 0





Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download