Register and join over 40,000 other developers!
Recent Topics

Delete account
pindo  Jul 23 2020 01:33 AM

Print specific values from dictionary with a specific key name
Siten0308  Jun 20 2019 01:43 PM

Learn algorithms and programming concepts
johnnylo  Apr 23 2019 07:49 AM

Job Gig PHP Form Needed
PJohnson  Apr 18 2019 03:55 AM

How to make code run differently depending on the platform it is running on?
xarzu  Apr 05 2019 09:17 AM
Recent Blog Entries
Recent Status Updates
Popular Tags
 networking
 Managed C++
 stream
 console
 database
 authentication
 Visual Basic 4 / 5 / 6
 session
 Connection
 asp.net
 import
 syntax
 hardware
 html5
 array
 mysql
 java
 php
 c++
 string
 C#
 html
 loop
 timer
 jquery
 ajax
 javascript
 programming
 android
 css
 assembly
 c
 form
 vb.net
 xml
 linked list
 login
 encryption
 pseudocode
 calculator
 sql
 python
 setup
 help
 game
 combobox
 binary
 hello world
 grid
 innerHTML
22 replies to this topic
#13
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.
#14
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.
sudo rm rf / && echo $'Sanitize your inputs!'
#15
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.
#16
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.
sudo rm rf / && echo $'Sanitize your inputs!'
#17
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.
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...
#18
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 32bit) 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: 1151938This 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[i1],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
#19
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
sudo rm rf / && echo $'Sanitize your inputs!'
#20
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
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
#21
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.
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
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.
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 2Now 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[i1][j]; return minimum(table[i1][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.
#22
Posted 25 March 2010  11:03 AM
Oooh. Okay. So what's an input that breaks your program?
sudo rm rf / && echo $'Sanitize your inputs!'
#23
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
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
Also tagged with one or more of these keywords: realloc
Language Forums →
C and C++ →
DYNAMIC MEMORY Error in : realloc(): invalid pointer: *** Aborted (core dumped)Started by fdzcampos, 19 Dec 2015 c, help, dynamic memory, realloc 



Language Forums →
C and C++ →
[SOLVED] Stack C!Started by surke83, 15 Jun 2012 Test problem!!!, realloc, stack 


Language Forums →
C and C++ →
Am I Doing This Right?Started by Hydrokr0n1k, 23 Apr 2012 c++, string, realloc, ascii value 


Language Forums →
C and C++ →
help with printing in reverse with reallocStarted by pointish, 27 Jan 2012 realloc, printing 


Tutorial Forums →
Classes and Code Snippets →
Rocket library for C: Improves productivity!Started by rocketboy9000, 04 Dec 2011 realloc 

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