Thread: Results for *easy* contest:

  1. #1
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490

    Results for *easy* contest:

    Prelude's comments:
    *ClownPimp*
    -----------
    effciency: 5
    elegance: 4
    portability: 4

    Extras: Does not work with floating-point.

    Notes:
    While This program works and is decent enough, there are a few points where
    I feel that it falls short of being robust. The use of gets for example. All
    in all I have little to snipe at with the quick inspection I performed so
    ClownPimp recieves a high rating.


    Dual-Catfish
    ------------
    effciency: 3
    elegance: 1
    portability: 0

    Extras: Does not work with floating-point.

    Notes:
    One would wonder why the awful scores for this program. I included the fact
    that I had to write a driver to run the calculator, but that is only a small
    portion of the scoring. This program did not compile as given, functions
    were used before definition, a header file was omitted (resulting in
    undefined behavior when a function from said file was used), and once I
    fixed all of these errors the program still did not work correctly. I will
    give Dual-Catfish some credit, the add function works quite well, but the
    others do not. Seeing as how a program must be able to compile before being
    portable, I gave that category a rating of 0. The undefined behavior and
    erroneous processing seriously hurt elegance, and I took two points away
    from efficiency because if a program gives the incorrect output, it doesn't
    matter how fast it did so.

    ygfperson's comments:
    this contest came out easy to judge. out of the 2 entries, only 1 worked.

    *ClownPimp*:
    efficiency: 3. There's no serious lack of it. I feel that he could have used inline functions in some places to speed things up.
    elegance: 5. The program is organized in a modular fashion, and it takes shortcuts where it needs to. (ie: a-b = a + -b).
    portability: 3. It compiles fine. He even put in an int main() function to make life easier. But because portability is also a measure of the program's ability, I subtracted 2 points because it can't multiply negative numbers. (neg * neg, pos * neg, and neg * pos all equal 0).

    Extras: none (although I did see some effort toward that direction)

    Notes:
    Great program (except for the multiplication flaw). It works as expected.

    Dual-Catfish:
    efficiency: 2. There's some lack of efficiency.
    elegance: 1. I feel he could have replaced most of the stuff in bitwise_sub() with a bitwise_add() call and a negation. In negation, he also uses plus signs instead of calling his own add function. Even then, there are some avoidable mistakes.
    portability: 0. The program doesn't work. It took work to get it to compile.

    Extras: none

    Notes:
    It's a good first try, but it could use a lot of improvement. Some stupid mistakes were made, like using pluses despite the ban on anything outsite ~,&,|,^. The fact that it doesn't do multiplication or division at all, or subtraction correctly, makes this decision easy.

    Other notes: Prelude mentioned that she had to write a driver for Dual-Catfish's entry. If that was int main(), it should be known that that wasn't required. (only the function itself). That won't affect results, anyway. (No offense, Catfish... )

    Scores:
    clownpimp: ((5+4+4)/3 + (3+5+3)/3)/2 = 8/3 = 4
    dual-catfish: ((3+1+0)/3 + (2+1+0)/3)/2 = 7/6 = 1.17

    congrats, *ClownPimp*!

    about judges: govtcheez asked us to go ahead, and ABCGum couldn't be reached, so there are two judges.
    Last edited by ygfperson; 07-18-2002 at 04:55 PM.

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    *ClownPimp*'s entry:
    Code:
    // calc.cpp
    // a four-function calculator 
    // author: *ClownPimp*
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    //#include <float.h>  dammit I couldnt get it to work
    #include <string.h>
    
    
    struct MATH_ERROR {
        const char *msg;
        MATH_ERROR(const char *message)
            :msg(message)
        {}
    };
    
    struct PARTS{
        int sign:1;
        int exp:8;
        int base:23;
    };
    
    union FLOAT{
        float fl;
        PARTS parts;
    };
    
    
    
    void  calc_func(char *input, int &total);
    int   parseInput(const char *input, char &op, int &val);
    bool  isSupportedOperator(char c);
    void  swap(int &, int &);
    int   add(int, int);
    int   sub(int, int);
    int   mul(int, int);
    int   divide(int, int); // div(int, int) already defined in stdlib
    int   overflow(int, int, int);
    
    // i dont know why, but I love macros
    #define isnegative(x)   ((x) >> (sizeof(x)*8-1))  // sizeof(x)*8-1 is a constant
    #define abs(x)          ((x) < (0)? add(1, ~x): (x)) 
    
    
    void calc_func(char *input, int &total)
    {
        char op;
        int val;
    
        // ive never used a try/catch block before, just thought
        // id give it a try
        try {
            if (parseInput(input, op, val))
                puts("invalid input");
    
            else {
                switch(op) {
                    
                case '=':
                    total = val;
                    break;
                
                case '+':
                    total = add(total, val);
                    break;
    
                case '-':
                    total = sub(total, val);
                    break;
    
                case '*':
                    total = mul(total, val);
                    break;
    
                case '/':
                    total = divide(total, val);
                    break;
                }
            }
        }
        catch (MATH_ERROR me) {
            printf("error: %s\n", me.msg);
        }
    }
    
    int parseInput(const char *input, char &op, int &val)
    {
        bool got_op = false, got_val = false;
    
        while (*input) {
        
            if (isSupportedOperator(*input) && !got_op) {
                op = *input;
                got_op = true;
            }
            else if (isdigit(*input) || (got_op && *input == '-')) {
                val = atoi(input);
                got_val = true;
                break;
            }
    
            ++input;
        }
    
        return (got_op == true && got_val == true) ? 0: -1;
    }
    
    bool isSupportedOperator(char c)
    { 
        return c == '*' || c == '/' || c == '+' || c == '-' || c == '=';
    }
    
    int overflow(int A, int B, int result)
    {
        // if A and B are of the same sign and the result is not
        // of the same sign of A and B, then overflow occured.
        // (ie if 100 + 100 = -something, then we know overflow occured)
        return (isnegative(A) == isnegative(B)) &&
               (isnegative(A) == !isnegative(result));
    }
    
    void swap(int &x, int &y)
    {
        int t = x;
        x = y;
        y = t;
    }
    
    
    int add(int A, int B)
    {
        int carry = 0, result = 0, mask = 1;
        
        for (int i = 0; i < sizeof(int)*8; ++i) {
            result |= (mask << i) & (A ^ B ^ carry);
            carry  = ((A ^ B) & carry) | (A & B);  // dont bother masking the other bits
            carry <<= 1;                           // because we dont care about them        
        }
        
        if (overflow(A, B, result))
                throw MATH_ERROR("overflow");
    
        return result;
        
    }
    
    int sub(int A, int B)
    {
        // didnt know if i could do -A or even ~A+1 here
        return add(A, add(1, ~B));
    }
    
    int mul(int A, int B)
    {
        int result = 0;
    
        // make sure we are adding the larger value
        if (B > A)
            swap(A, B);
    
        for (int i = 0; i < B; ++i)
            result = add(A, result);
    
        // check if input had opposite signs
        if (isnegative(A) != isnegative(B)) 
            return add(1, ~result);
        return result;
    }
    
    int divide(int A, int B)
    {
        int a, b, c, high, low, middle, overflow = false;
    
        if (B == 0)
            throw MATH_ERROR("divide by zero");
    
        a = abs(A);  
        b = abs(B);
        high = a;    
        low = 1;
    
        if (b > a)
            return 0;
       
        do {
            // low + (high-low)/2 instead of (high+low)/2
            // necessary to avoid overflow with large numbers
            middle = add(low, sub(high, low) >> 1);
            try {
                c = mul(middle, b);
            }
            catch(MATH_ERROR me) {
                overflow = 1; 
            }
    
            if (overflow || c > a) {// if overflow occured we know 'c' was too high 
                overflow = false;
                high = middle;
            }    
            else 
                low = middle;
        
        }while (!(a >= c && c > a-b));
    
        // check if input has opposite signs
        if (isnegative(A) != isnegative(B)) 
            return add(1, ~middle);   
        return middle;
    }
    
    int main()
    {
        int total = 0;
        char buf[100];
        
        gets(buf);
        while (buf[0] != 'q') {
            calc_func(buf, total);
            printf("total: %d\n", total);
            gets(buf);
        }
    
        return 0;
    }

  3. #3
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    Dual-Catfish's entry:
    Code:
    #include <cstring>
    #include <climits>
    #include <cmath>
    
    void calc_func(char *input, int &total)
    {
    	using namespace std;
    
    	int iFinalDigit = 0; // The final digit we get from the character array; 
    	char pcszDigits[] = "0123456789"; // String of characters for strpbrk to search for;
    
    	char *szExtracted = strpbrk(input, pcszDigits);
    
    	if (szExtracted == NULL) {
    		return;
    	} else {
    		iFinalDigit = atoi(szExtracted);
    	}
    
    
    	char cOperation = input[0];
    	*input++;
    
    	if (strchr(input, '-') != NULL)
    	{
    		iFinalDigit = ~iFinalDigit + 1;
    	}
    
    	switch (cOperation)
    	{
    	 case '/':
    //		 bitwise_div(total, iFinalDigit);
    		 break;
    	 case '*':
    //		 bitwise_mult(total, iFinalDigit);
    		 break;	
    	 case '+':
    		 if (iFinalDigit > 0)
    		 {
    			bitwise_add(total, iFinalDigit);
    		 } else {
    			bitwise_sub(total, ~iFinalDigit + 1);
    		 }
    		 break;
    	 case '-':
    		 if (iFinalDigit < 0)
    		 {
    			bitwise_add(total, ~iFinalDigit + 1);
    		 } else {
    			bitwise_sub(total, ~iFinalDigit + 1);
    		 }
    
    		 break;
    	 case '%':
    //		 bitwise_mod(total, iFinalDigit);
    		 break;
    	}
    	return;
    }
    
    void bitwise_add(int &total, int iInput)
    {
    	using namespace std;
    	for (int i = 1; i <= USHRT_MAX + 1; i <<= 1)// We loop through the each bit that
    	{											// Can be set in an integer;
    		if ((iInput & i) && (!(total & i)))		// if (The number to add has the bit set, and
    		{										// the total doesn't have the bit set)
    			total |= i;							// OR the bit to the total;
    			
    		} else if (iInput & i && total & i) {	// if (Both the number to add and the total
    												// have the bit set)
    			for (int ii =  i << 1; ii <= USHRT_MAX + 1; ii <<= 1) // Loop through each possible bit
    			{													  // That an integer can have set
    				if (!(total & ii))								  // if (total doesn't have the bit set)
    				{												  // We now have an open slot to OR the bit in
    					total &= ~i;		// Remove the initial bit which we couldn't set
    					total |= ii;		// OR on the new bit
    					break;
    
    				} else {
    
    					total &= ~ii;		// If we're down here, then we know that total has this bit set
    				}						// We have to remove it because a more significant bit will be 
    										// Set once it's found;
    			}
    		} 
    	}
    }
    
    void bitwise_sub(int &total, int iInput)
    {
    	// The complete opposite of the bitwise_add() function
    	using namespace std; 
    	for (int i = 1; i <= USHRT_MAX + 1; i <<= 1)
    	{											
    		if ((iInput & i) && (!(total & i)))	
    		{									
    			for (int ii = i << 1; ii < USHRT_MAX + 1; ii <<= 1)
    			{
    				if (!(total & ii))
    				{
    					total |= ii;
    				} else {
    					total |= i;
    					total &= ~ii;
    					break;
    				}
    			}
    			
    		} else if (iInput & i && total & i) {
    								
    			total &= ~i;
    		} 
    	}
    }

  4. #4
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,823
    "i know it's against the rules...but i hope you can make an exception

    *bump*"

    Ya coulda asked

  5. #5
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    god-dern... that's a fast response
    nearly didn't have time to delete out my bumping post

  6. #6
    Registered User Dual-Catfish's Avatar
    Join Date
    Sep 2001
    Posts
    802
    Noooo, you idiots, my entry is clearly superior. How could you make such a blunder?

    clownpimp: ((5+4+4)/3 + (3+5+3)/3)/2 = 8/3 = 4
    dual-catfish: ((3+1+0)/3 + (2+1+0)/3)/2 = 7/6 = 5.54

  7. #7
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    I noticed i did make a mistake, but that was in clownpimp's row. 8/3 should be 8/2.

    [sarcasm]Oh. I'm sorry. Please forgive our humble selves for overlooking the falliable arithmetic we have chosen to solve our problems. While we're at it, we also overlooked your service in the armed forces. We've compared you to our president, and we find you a better leader. Please take your place as the rightful leader of us, and our humble comrades. We are less than nothing. Do whatever your vastly-superior mind wants with us.
    [/sarcasm]

  8. #8
    "The Oldest Member Here" Xterria's Avatar
    Join Date
    Sep 2001
    Location
    Buffalo, NY
    Posts
    1,039
    how the heck do you even run a program with no main()? catfish you bunholio

  9. #9
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    the judges write up a primitive int main to run the program. it was meant to be that way.

  10. #10
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    >it can't multiply negative numbers. (neg * neg, pos * neg, and neg * pos all equal 0).

    doh! i forgot to take the abs of the numbers then work out the sign at the end like I did with the divide function, how could i have missed that *bangs head on table*

  11. #11
    x4000 Ruski's Avatar
    Join Date
    Jun 2002
    Location
    Outer Space!
    Posts
    542
    So what are these easy contests all about??
    what does signature stand for?

  12. #12
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    there was an easy and a hard contest where you could sign up. the easy one was to add, subtract, multiply, and divide using only bitwise operations. the hard one was to create a fractal generator. i'm not sure if i want to continue the two-contest format...
    Last edited by ygfperson; 07-26-2002 at 06:55 AM.

  13. #13
    x4000 Ruski's Avatar
    Join Date
    Jun 2002
    Location
    Outer Space!
    Posts
    542
    So are the contests for everyone who wants?
    what does signature stand for?

  14. #14
    Registered User fletch's Avatar
    Join Date
    Jul 2002
    Posts
    176
    When is the next contest?
    "Logic is the art of going wrong with confidence."
    Morris Kline

  15. #15
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    Originally posted by Ruski
    So are the contests for everyone who wants?
    yes. you don't need to sign up either, although it's preferred. you just need to get an entry sent to my e-mail address before the deadline.

    When is the next contest?
    sometime soon. i'll put up another thread for more info.

    to mods: feel free to unsticky the "results" threads when you feel enough time has passed.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Incorrect results from fmod()?
    By karlthetruth in forum C Programming
    Replies: 4
    Last Post: 04-11-2008, 09:12 AM
  2. how to run an exe command in c++ and get back the results?
    By mitilkhatoon in forum C++ Programming
    Replies: 5
    Last Post: 09-21-2006, 06:00 PM
  3. Results of March Monthly Contest
    By PJYelton in forum Contests Board
    Replies: 23
    Last Post: 04-17-2005, 09:46 AM
  4. 72hour GDC Results
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 07-05-2004, 11:46 PM
  5. Same seed for srand yields different results
    By codegirl in forum C++ Programming
    Replies: 3
    Last Post: 06-23-2003, 02:39 PM