PDA

View Full Version : Results for *easy* contest:



ygfperson
07-18-2002, 04:49 PM
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... :D)

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.

ygfperson
07-18-2002, 04:54 PM
*ClownPimp*'s entry:

// 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;
}

ygfperson
07-18-2002, 04:54 PM
Dual-Catfish's entry:

#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;
}
}
}

Govtcheez
07-19-2002, 06:40 AM
"i know it's against the rules...but i hope you can make an exception

*bump*"

Ya coulda asked :p

ygfperson
07-19-2002, 06:42 AM
god-dern... that's a fast response :)
nearly didn't have time to delete out my bumping post

Dual-Catfish
07-19-2002, 11:32 AM
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

ygfperson
07-19-2002, 04:15 PM
I noticed i did make a mistake, but that was in clownpimp's row. 8/3 should be 8/2.

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.

:D :p :p :p :D ;)

Xterria
07-20-2002, 07:35 PM
how the heck do you even run a program with no main()? catfish you bunholio

ygfperson
07-20-2002, 08:31 PM
the judges write up a primitive int main to run the program. it was meant to be that way.

*ClownPimp*
07-21-2002, 01:28 AM
>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*

Ruski
07-26-2002, 03:23 AM
So what are these easy contests all about?? :)

ygfperson
07-26-2002, 06:51 AM
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...

Ruski
07-26-2002, 06:57 AM
So are the contests for everyone who wants?

fletch
07-26-2002, 02:48 PM
When is the next contest?

ygfperson
07-26-2002, 07:58 PM
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.

Ruski
07-27-2002, 11:35 AM
Ok :) thanks ;)