6610 bytes (unminified)
"Good boy" C program that meets all challenge criteria. Uses 10s complement for negative numbers. Also included, a test harness and test cases.
/*
Read input from STDIN. The input must conform to VALIDINPUT:
NONZERODIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
POSITIVENUMBER = NONZERODIGIT *98DIGIT
NEGATIVENUMBER = "-" POSITIVENUMBER
NUMBER = NEGATIVENUMBER / POSITIVENUMBER / "0"
VALIDINPUT = NUMBER SP NUMBER *1LF EOF
Check syntax of input. If input is correct, add the two numbers and print
to STDOUT.
LSB => least significant byte
MSB => most significant byte
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <assert.h>
#define NUL ('\0')
/*
maximum characters in VALIDINPUT:
'-' 1
POSITIVENUMBER MAXDIGITS
' ' 1
'-' 1
POSITIVENUMBER MAXDIGITS
LF 1
*/
#define MAXDIGITS (99)
#define MAXVALIDINPUT (2*MAXDIGITS+4)
void die() { printf("E\n"); exit(1); }
/*
Add two NUMBERs and print the result to STDOUT. The NUMBERS have
been separated into POSITIVENUMBERS and sign information.
Arguments:
first - pointer to LSB of 1st POSITIVENUMBER
firstSize - size of 1st POSITIVENUMBER
firstNegative - is 1st # negative?
second - pointer to LSB of 2nd POSITIVENUMBER
secondSize - size of 2nd POSITIVENUMBER
secondNegative - is 2nd # negative?
carry - carry from previous place?
Returns:
sum[] - sum
addNUMBERs() - carry to next place?
- Don't use complementDigit(popDigit(p,s),n). Side-effects generate two pops.
*/
#define popDigit(p,s) ((s)--,(*(p++)-'0'))
#define complementDigit(c,n) ((n) ? 9-(c) : (c))
#define pushSum(c) (*(--sumPointer)=(c))
#define openSum() (pushSum(NUL))
#define closeSum() ;
char sum[MAXVALIDINPUT];
char *sumPointer = sum+sizeof(sum);
int addNUMBERs(char *first, int firstSize, bool firstNegative,
char *second, int secondSize, bool secondNegative,
int previousCarry) {
int firstDigit, secondDigit;
int mySum;
int myCarry;
/*
1st half of the problem.
Build a stack of digits for "first" and "second"
numbers. Each recursion of addNUMBERs() contains one digit
of each number for that place. I.e., the 1st call holds
the MSBs, the last call holds the LSBs.
If negative, convert to 10s complement.
*/
assert((firstSize > 0) && (secondSize > 0));
if (firstSize > secondSize) {
firstDigit = popDigit(first, firstSize);
firstDigit = complementDigit(firstDigit, firstNegative);
secondDigit = 0;
} else if (secondSize > firstSize) {
firstDigit = 0;
secondDigit = popDigit(second, secondSize);
secondDigit = complementDigit(secondDigit, secondNegative);
} else {
// same size
firstDigit = popDigit(first, firstSize);
firstDigit = complementDigit(firstDigit, firstNegative);
secondDigit = popDigit(second, secondSize);
secondDigit = complementDigit(secondDigit, secondNegative);
}
// recursion ends at LSB
if ((firstSize == 0) && (secondSize == 0)) {
// if negative, add 1 to complemented LSB
if (firstNegative) {
firstDigit++;
}
if (secondNegative) {
secondDigit++;
}
myCarry = previousCarry;
} else {
myCarry = addNUMBERs(first, firstSize, firstNegative,
second, secondSize, secondNegative,
previousCarry);
}
/*
2nd half of the problem.
Sum the digits and save them in first[].
*/
mySum = firstDigit + secondDigit + ((myCarry) ? 1 : 0);
if ((myCarry = (mySum > 9))) {
mySum -= 10;
}
pushSum(mySum + '0');
return(myCarry);
}
// Handle the printing logic.
void addAndPrint(char *first, int firstSize, bool firstNegative,
char *second, int secondSize, bool secondNegative,
int previousCarry) {
openSum();
addNUMBERs(first, firstSize, firstNegative,
second, secondSize, secondNegative,
previousCarry)
closeSum();
if (*sumPointer<'5') {
// it's positive
for (; *sumPointer=='0'; sumPointer++) {} // discard leading 0s
// if all zeros (sumPointer @ NUL), back up one
sumPointer -= (*sumPointer == NUL) ? 1 : 0;
printf("%s\n", sumPointer);
} else {
// it's negative
char *p;
// discard leading 0s (9s in 10s complement)
for (; *sumPointer=='9' && *sumPointer; sumPointer++) {}
// if -1 (sumPointer @ EOS), back up one
sumPointer -= (*sumPointer == NUL) ? 1 : 0;
for (p=sumPointer; *p; p++) {
*p = '0' + ('9' - *p); // uncomplement
// special handling, +1 for last digit
*p += (*(p+1)) ? 0 : 1;
}
printf("-%s\n", sumPointer);
}
return;
}
/*
Lex a number from STDIN.
Arguments:
bufferPointer - pointer to a pointer to a buffer, use as
**buffer = c; // put "c" in the buffer
*buffer += 1; // increment the buffer pointer
(*buffer)++; // also increments the buffer pointer
All sorts of side-effects:
- getc(stdin)
- ungetc(...,stdin)
- modifies value of **bufferPointer
- modifies value of *bufferPointer
Returns:
lexNUMBER() - number of bytes added to *bufferPointer,
*1 if POSITIVENUMBER,
*-1 if NEGATIVENUMBER
*bufferPointer - points to the LSB of the number parsed + 1
*/
#define pushc(c) (*((*bufferPointer)++)=c)
bool lexNUMBER(char **bufferPointer) {
char c;
int size = 0;
bool sign = false;
/* lex a NUMBER */
if ((c=getchar()) == '0') {
pushc(c);
c = getchar();
size++;
} else {
if (c == '-') {
sign = true;
c = getchar();
// "-" isn't a digit, don't add to size
}
if (c == '0') {
die();
}
for (size=0; isdigit(c); size++) {
if (size >= MAXDIGITS) {
die();
}
pushc(c);
c = getchar();
}
}
if (size < 1) {
die();
}
ungetc(c,stdin); // give back unmatched character
return (sign);
}
int main() {
int c;
char buffer[MAXVALIDINPUT];
char *bufferPointer;
char *first, *second;
int firstSize, secondSize;
bool firstNegative, secondNegative;
bufferPointer = buffer + 1; // hack, space for leading digit
// parse 1st number
first = bufferPointer;
firstNegative = lexNUMBER(&bufferPointer);
firstSize = bufferPointer - first;
*(bufferPointer++) = NUL; // hack, space for EOS
bufferPointer++; // hack, space for leading digit
// parse separating blank
if ((c=getchar()) != ' ') {
die();
}
// parse 2nd number
second = bufferPointer;
secondNegative = lexNUMBER(&bufferPointer);
secondSize = bufferPointer - second;
*(bufferPointer++) = NUL; // hack, space for EOS
// parse end of input
c = getchar();
if (! ((c == EOF) || ((c == '\n') && ((c=getchar()) == EOF))) ) {
die();
}
// Some very implementation-specific massaging.
*(--first) = '0'; // prefix with leading 0
*(first+(++firstSize)) = NUL; // add EOS
*(--second) = '0'; // prefix with leading 0
*(second+(++secondSize)) = NUL; // add EOS
// add and print two arbitrary precision numbers
addAndPrint(first, firstSize, firstNegative,
second, secondSize, secondNegative, false);
return(0);
}
Here's a little test harness and a few test cases to get you started. Feel free to tear out the excessive use of perl. The system it was developed on didn't have a modern bash.
#!/bin/bash
#
# testharness.sh
#
# Use as: bash testharness.sh program_to_be_tested < test_data
#
# Each line in the test data file should be formatted as:
#
# INPUT = bash printf string, must not contain '"'
# OUTPUT = perl string, must not contain '"'
# (inserted into the regex below, use wisely)
# TESTNAME = string, must not contain '"'
# GARBAGE = comments or whatever you like
# INPUTQUOTED = DQUOTE INPUT DQUOTE
# OUTPUTQUOTED = DQUOTE OUTPUT DQUOTE
# TESTQUOTED = DQUOTE TESTNAME DQUOTE
# TESTLINE = INPUTQUOTED *WSP OUTPUTQUOTED *WSP TESTQUOTED GARBAGE
TESTPROGRAM=$1
TMPFILE=testharness.$$
trap "rm $TMPFILE" EXIT
N=0 # line number in the test file
while read -r line; do
N=$((N+1))
fields=$(perl -e 'split("\"",$ARGV[0]);print "$#_";' "$line")
if [[ $fields -lt 5 ]]; then
echo "skipped@$N"
continue
fi
INPUT=$(perl -e 'split("\"",$ARGV[0]);print "$_[1]";' "$line")
OUTPUT=$(perl -e 'split("\"",$ARGV[0]);print "$_[3]";' "$line")
TESTNAME=$(perl -e 'split("\"",$ARGV[0]);print "$_[5]";' "$line")
printf -- "$INPUT" | $TESTPROGRAM > $TMPFILE
perl -e "\$t='^\\\s*$OUTPUT\\\s*\$'; exit (<> =~ \$t);" < $TMPFILE
if [[ $? -ne 0 ]]; then # perl -e "exit(0==0)" => 1
echo "ok $TESTNAME"
else
echo -n "failed@$N $TESTNAME," \
"given: \"$INPUT\" expected: \"$OUTPUT\" received: "
cat $TMPFILE
echo
fi
done
A small set of test cases:
"0 0" "0" "simple, 0+0=0"
"1 1" "2" "simple, 1+1=2"
"" "E" "error, no numbers"
"0" "E" "error, one number"
"0 0" "E" "error, two/too much white space"
"0 0 " "E" "error, trailing characters"
"01 0" "E" "error, leading zeros not allowed"
"-0 0" "E" "error, negative zero not allowed
"0 -0" "E" "error, negative zero not allowed here either
"1 1\n" "2" "LF only allowed trailing character
"\0001 1\n" "E" "error, try to confuse C string routines #1"
"1\00 1\n" "E" "error, try to confuse C string routines #2"
"1 \0001\n" "E" "error, try to confuse C string routines #3"
"1 1\000\n" "E" "error, try to confuse C string routines #4"
"1 1\n\000" "E" "error, try to confuse C string routines #5"
"-1 -1" "-2" "add all combinations of -1..1 #1"
"-1 0" "-1" "add all combinations of -1..1 #2"
"-1 1" "0" "add all combinations of -1..1 #3"
"0 -1" "-1" "add all combinations of -1..1 #4"
"0 0" "0" "add all combinations of -1..1 #5"
"0 1" "1" "add all combinations of -1..1 #6"
"1 -1" "0" "add all combinations of -1..1 #7"
"1 0" "1" "add all combinations of -1..1 #8"
"1 1" "2" "add all combinations of -1..1 #9"
"0 123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" "0+99 digits should work"
"100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "99 digits+99 digits should work"
"500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "test for accumulator overflow"
"-123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 0" "-123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" "0+negative 99 digits work"
"-100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 -100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "-200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "99 digits+99 digits (both negative) should work"
"-500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 -500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "-1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "test for negative accumulator overflow"
"1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 0" "E" "error, 100 digits"
Why no warnings? gcc warnings are broken and warn about perfectly correct stuff like
putchar(c) == EOF || exit(1)
. – FUZxxl – 2015-12-02T11:55:06.5432I love how clear your spec became with a single use of the word "otherwise". Very well written (in my opinion). Too bad the challenge is only in C, but I can see why it has to be that way. – Rainbolt – 2014-05-02T21:07:58.887
3Without warnings + code-golf + C? This is bound to be interesting! – Fors – 2014-05-02T21:09:21.627
Decimal integers? "space-separated" == "whitespace-separated"? – Glenn Randers-Pehrson – 2014-05-02T21:25:56.860
@GlennRanders-Pehrson Yes decimal and horizontal white space separated as you say. – None – 2014-05-02T21:29:19.443
1stdin or command line? – r3mainer – 2014-05-02T21:36:17.360
2Could we get a strict acceptable input format? Such as no extra whitespace (or anything not a number) before the first number, any amount of horizontal whitespace (i.e. horizontal tabs and spaces) between the two numbers, and nothing except a linefeed or a carriage return together with a linefeed after the second number? – Fors – 2014-05-02T21:41:10.800
1Is the input terminated by newline+EOF or just EOF? – user12205 – 2014-05-02T22:22:06.483
1Since it's a code-golf, you should probably give the exact error message to display. – Michael M. – 2014-05-02T22:55:24.257
3Also, does space-separated mean 1) separated by one character with ASCII value 32, 2) separated by an arbitrary number of character with ASCII value 32, 3) separated by any one ASCII whitespace character (32, 10, 9, possibly 13?), 4) separated by an arbitrary number of a single whitespace character from the set of ASCII whitespace characters, or 5) separeted by an arbitrary number of any combination of the set of ASCII whitespace characters? – user12205 – 2014-05-02T23:00:12.500
do I understand correctly we must reject inputs where either number is 100 characters or longer? – John Dvorak – 2014-05-03T06:00:32.413
@JanDvorak Yes that is right. – None – 2014-05-03T06:01:52.467
Which version of gcc? – dmckee --- ex-moderator kitten – 2014-05-03T07:20:15.897
@dmckee gcc 4.8.2 – None – 2014-05-03T08:17:07.797
100 digits? I'm pretty sure that will overflow. – nyuszika7h – 2014-05-03T13:37:54.907
Added some precision to the input definition. – Scott Leadley – 2014-05-03T19:17:28.230
Are negative numbers allowed? If so, the ABNF (with ;s) should be changed to: POSITIVENUMBER = 1*100DIGIT; NEGATIVENUMBER = "-" POSITIVENUMBER; NUMBER = NEGATIVE NUMBER / POSITIVENUMBER; VALIDINPUT = NUMBER SP NUMBER *1LF – Scott Leadley – 2014-05-04T10:39:45.753
@Scottleadley. Yes they are. Could you edit it as I can't right now? – None – 2014-05-04T10:59:06.230
@Lembik Also adjusted digit count from 100 to 99 to conform to "less than 100 digits long". – Scott Leadley – 2014-05-04T11:40:38.660
@ScottLeadley I am not 100% confident with ABNF so I just wanted to check but I think 001 is not a valid number. Does the ABNF you entered follow that rule? Also, the LF should be optional. Does 1*LF do that? – None – 2014-05-04T14:35:45.413
@Lembik 1*99DIGIT allows leading zeros. 1LF is short for 01LF, i.e. an optional LF. – Scott Leadley – 2014-05-04T14:50:28.313
@Lembick If you want to exclude leading zeros, use
NONZERODIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"; POSITIVENUMBER = NONZERODIGIT *98DIGIT
– Scott Leadley – 2014-05-04T14:56:19.697@Lembick Just realized that the current spec outlaws 0. Easiest fix (for you) is:
NUMBER = NEGATIVENUMBER / POSITIVENUMBER / "0"
. Tacking it on to POSITIVENUMBER allows -0. – Scott Leadley – 2014-05-04T18:39:20.787@Lembick I'm sure the compiler gods will smite us for this ugly syntax graph, but it seems to be complete. – Scott Leadley – 2014-05-04T23:59:07.493