Better up my logic

This is a discussion on Better up my logic within the C Programming forums, part of the General Programming Boards category; During a competition I came across a problem which at that time I was unable to solve. But now I ...

  1. #1
    Infant of C
    Join Date
    May 2010
    Location
    Karachi, Pakistan
    Posts
    118

    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
    Attached Files Attached Files

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    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.
    Last edited by laserlight; 01-10-2011 at 08:15 AM. Reason: OO versus 00 :o
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    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?

  4. #4
    Infant of C
    Join Date
    May 2010
    Location
    Karachi, Pakistan
    Posts
    118
    Quote Originally Posted by Bayint Naung View Post
    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?

  5. #5
    Infant of C
    Join Date
    May 2010
    Location
    Karachi, Pakistan
    Posts
    118
    Quote Originally Posted by laserlight View Post
    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.

  6. #6
    Infant of C
    Join Date
    May 2010
    Location
    Karachi, Pakistan
    Posts
    118
    please check out the input file attached.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Quote Originally Posted by tabstop View Post
    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.

  10. #10
    Infant of C
    Join Date
    May 2010
    Location
    Karachi, Pakistan
    Posts
    118
    Quote Originally Posted by tabstop View Post
    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

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Quote Originally Posted by C_programmer.C View Post
    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:

    1. water is unknown
    2. glucose is 35%
    3. assume water is also 35%
    4. that totals 70%
    5. we have 30% left
    6. cocoa powder is unknown
    7. do we have any room left for more ingredients?
    8. yes, we have 30% of the substance left to account for, so there is room to add cocoa powder
    9. we have no more ingredients
    10. 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. logic calculator
    By quintenmater in forum C Programming
    Replies: 13
    Last Post: 12-01-2010, 08:13 PM
  2. Handling logic and draw cycles
    By DavidP in forum Game Programming
    Replies: 1
    Last Post: 07-25-2009, 10:15 AM
  3. Digital Logic
    By strokebow in forum Tech Board
    Replies: 3
    Last Post: 12-09-2006, 12:05 PM
  4. Logic
    By LordBronz in forum C++ Programming
    Replies: 6
    Last Post: 05-23-2006, 05:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21