Better up my logic

During a competition I came across a problem which at that time I was unable to solve.
But now I have developed a code for that problem. Now I request you people to please better up my logic since in this code the logic is too complex, although it is working correctly.
the problem is:

On the wrapper of a bar of chocolate, the specified amount of componenets must be in NON_INCREASING order. Means

Water 50%
Taurine 30%
Lime

is likely to be true, but

Water
Cocoa-butter
cocoa-powder 40%
Lecithine

is absolutely wrong.
Now the task is to write a program that determines whether an inscription of components on a chocolate bar.

the input file contains the number of components N(1<=N<=5000). each of the following lines contains the descriptions of one component. each description contain a non-spaced name of component. then there is a space followed by a number 1 or 0. 1 if the % of the component is given and zero if the percentage of component is not given.
A number 00 indicates the end of input file.

Following is the code:

Code:

#include<stdio.h> void checkarr(int *,int); int main() { FILE *fp; int *amnt,i,flag=0,n; char *name; fp=fopen("prob1.txt","r"); if(fp==NULL) { printf("Error opening file"); exit(1); } fscanf(fp,"%d",&n); while(n!=0) { free(amnt); amnt=(int *)malloc(n*sizeof(int)); for(i=0;i<n;i++) { fscanf(fp,"%s%d",name,&flag); if(flag==0) amnt[i]=-1; else fscanf(fp,"%d",&amnt[i]); } checkarr(amnt,n); fscanf(fp,"%d",&n); } fclose(fp); return 0; } void checkarr(int *amnt,int n) { int flag=0; int i,sum=0,temp=0; for(i=n-1;i>=0;i++) { if(amnt[i]==-1) amnt[i]=temp; else temp=amnt[i]; } for(i=0;i<n;i++) { sum=sum+amnt[i]; if(amnt[i]<amnt[i+1]) { flag=0; break; } flag=1; } if(sum>100) flag=0; if(flag==0) printf("NO\n"); else printf("YES\n"); }

the output of the attached file must be:

NO
YES
NO

Err... if you assume that there is some suitably small upper bound on the number of characters of each component name, then you don't need dynamic memory allocation for this, and yet can quite easily use fscanf to read the component name.

Basically, you just need to keep track of the current, previous and total amounts. If the current amount is greater than the previous, you print NO and then skip until the 00 is read. If the total is greater than 100, you also print NO then skip until 00 is read. Otherwise, when 00 is read, you print YES.

It's as simple as checking if the input sequence is in decreasing order.
Pseudo code

Code:

prev = 0; start: cur = get_cur_input() // if EOF break, etc... if( cur > prev ) { printf("NO!\n") } else { prev = cur; goto start; }

Actually your code is wrong,

free(amnt);
Where's amnt pointer pointing when the first time loop is executed?

Quote:

Originally Posted by Bayint Naung

It's as simple as checking if the input sequence is in decreasing order.
Pseudo code

Code:

prev = 0; start: cur = get_cur_input() // if EOF break, etc... if( cur > prev ) { printf("NO!\n") } else { prev = cur; goto start; }

Actually your code is wrong,

free(amnt);
Where's amnt pointer pointing when the first time loop is executed?

about the statement
free(amnt);
i except that it had to be in the end of loop. right?

after that I think it is not so simple to check

if(cur>prev)
.
.
.

what you will do if the amount of the ingredient is not given. Check out the input file?

Quote:

Originally Posted by laserlight

Err... if you assume that there is some suitably small upper bound on the number of characters of each component name, then you don't need dynamic memory allocation for this, and yet can quite easily use fscanf to read the component name.

Basically, you just need to keep track of the current, previous and total amounts. If the current amount is greater than the previous, you print NO and then skip until the 00 is read. If the total is greater than 100, you also print NO then skip until 00 is read. Otherwise, when 00 is read, you print YES.

I am sorry. I think I am unable to explain my code and the problem clearly.
Actually i am allocating memory for the amount of components not for the name of components.
Also how can there be a predetermined upper bond for the array since the number of components will be known at run time. Thirdly it is not so simple to check whether the amount of current component is greater than the previous or not since amount of some of the components are not given.

please check out the input file attached.

Quote:

Originally Posted by C_programmer.C

Actually i am allocating memory for the amount of components not for the name of components.

You don't need to do that. It is true that you did not allocate memory for the component names, and in this you are wrong since you use fscanf with %s rather than reading character by character.

Quote:

Originally Posted by C_programmer.C

Also how can there be a predetermined upper bond for the array since the number of components will be known at run time.

Since the array that I am talking about is the array of characters that should contain the name, there can be a pre-determined upper bound. If the upper bound is not known or is too large, you have to handle it yourself, but just assume first, e.g., assume that the longest component name will be 99 characters, so you make name an array of 100 characters (+1 for the null character).

Quote:

Originally Posted by C_programmer.C

Thirdly it is not so simple to check whether the amount of current component is greater than the previous or not since amount of some of the components are not given.

It is simple: just consider the amount to be 0.

The logic seems straightforward, I would think:
1) Start at total percentage = 100, with an "unknown count" of 0.
2) If you read an ingredient with an unknown percentage, add 1 to the unknown count.
2b) If instead you read an ingredient with a known percentage, subtract (read percentage)*(unknown count + 1) from the total percentage.
3) Repeat.
4) If your total percentage ends up < 0, NO otherwise YES.

Quote:

Originally Posted by tabstop

The logic seems straightforward, I would think:
1) Start at total percentage = 100, with an "unknown count" of 0.
2) If you read an ingredient with an unknown percentage, add 1 to the unknown count.
2b) If instead you read an ingredient with a known percentage, subtract (read percentage)*(unknown count + 1) from the total percentage.
3) Repeat.
4) If your total percentage ends up < 0, NO otherwise YES.

One minor ammendment. If your total is < 0 or your total is exactly zero and unknown > 0, NO otherwise YES.

Quote:

Originally Posted by tabstop

The logic seems straightforward, I would think:
1) Start at total percentage = 100, with an "unknown count" of 0.
2) If you read an ingredient with an unknown percentage, add 1 to the unknown count.
2b) If instead you read an ingredient with a known percentage, subtract (read percentage)*(unknown count + 1) from the total percentage.
3) Repeat.
4) If your total percentage ends up < 0, NO otherwise YES.

well what if the components are given in this form

3
water
glucose 35
cocoa-powder

this composition is possible but your logic will prove it wrong

Well, how exactly are you supposed to treat components whose amount is unknown? For example, suppose you are given 101 components, all of which have unknown amounts. Do you print YES or do you print NO? Frankly, there is nothing stated about that in what you have given, so I would simply print YES, hence my suggestion of assuming that components with no amount given be treated as if they have an amount of 0.

Incidentally, your example is that of an invalid format, so we should print NO anyway.

Quote:

Originally Posted by C_programmer.C

well what if the components are given in this form

3
water
glucose 35
cocoa-powder

this composition is possible but your logic will prove it wrong

Actually, the logic is sound. That isn't valid input, by the way, since it's missing the 0/1 to tell you whether to expect an explicit percentage.

Take a careful look at item 2b in tabstop's instructions though. You are multiplying the known percentage (35 in this case) by the count of previous unknowns plus 1 (for the current, known ingredient). The reason this works is because we know that anything prior to an explicit 35% must be at least 35%. Thus, we assume it is the smallest possible value, allowing for the "most room" for subsequent ingredients. Basically, tabstop's logic works out to the following in your case:

water is unknown
glucose is 35%
assume water is also 35%
that totals 70%
we have 30% left
cocoa powder is unknown
do we have any room left for more ingredients?
yes, we have 30% of the substance left to account for, so there is room to add cocoa powder
we have no more ingredients
YES, this is legit

Try coding it up (with my amendment), and add the water/glucose/cocoa powder set to your input file, you should get the correct results. Post your updated program if you have problems with it.