CPS 104

Problem P1

Words

Write a C program which reads characters from stdin, and then prints 26
lines, one for each lower-case letter of the alphabet. The line for
letter X should contain (N&0x3f) copies of X, when N words ENDING in X
appear in the input that your program read.  A "word" is defined as a
sequence of upper or lower-case letters surrounded by non-letters.
Treat the beginning of the file, and the end of file as non-letters.
Consider upper and lower case letters equivalent for output purposes.
[Note: (N&0x3f) is equal to the remainder of N divided by 64, and is
used here to ensure that your program computed accurately the number N,
without requiring your program to print long lines of output.] There
won't be more than 1000000 total characters in the input.

You program must not use any C++ classes, or any subroutines not
defined within your program, except the tools below. Programs will be
evaluated on the basis of their simplicity (usually, short programs are
simpler than longer ones), and their "speed".

Speed will be judged by timing your program's execution, and observing
"user time", using the command "/bin/time -p program <
/usr/tmp/charstst4". You can approximate "time", by estimating the
number of variables and constants your program references during its
execution. The smaller this number, the faster (better) the program.
"Shortness", also called "elegance" is obtained by counting the number
of C "tokens" in your program.  A "token" is a C word, or variable
name, or operator symbol or parenthesis, or constant.  (Comments are
not counted, and strings and long names each count as one token,
regardless of their length.)

Tools:

This program requires that it read input from stdin, and print output
(implicitly on stdout). You may make use of two library subroutines,
"int getchar()" and "int putchar(int c)" which are declared in the
standard C library. These are described below:

NAME

getchar - get a byte from a stream

SYNOPSIS

#include <stdio.h>

int getchar(void);

DESCRIPTION

getchar()

The getchar() function obtains the next byte (if present) as an
unsigned char converted to an int, from stdin, and advances the
associated file position indicator for stdin.

The integer returned for a valid character c is the ASCII code for c.
If an end-of-file is encountered, the value EOF (equal to -1) is
returned instead.

NAME

putchar - put a byte on a stream

SYNOPSIS

#include <stdio.h>

int putchar(int c);

DESCRIPTION

putchar()

The putchar() function appends the byte specified by c (converted to an
unsigned char) to stdout.

RETURN VALUES

putchar() returns the value that was written.



Your background:

You should be familiar with the simple arithmetic operations on
integers that C allows, such as +, -, comparisons, and the use of
integers as array indices. You should also know the C representations
for characters: 'X' represents the ASCII code for the character X, and
in particular, '\n' represents the ASCII code for the "end of line"
character, which should be appended to the end of each line of
characters your program prints. You might need to know certain
characteristics of the ASCII code: (1) Every character read has a code
between 0 and 255; (2) the codes for the lower-case letters are
sequential integers, between 'a' and 'z' inclusive; (3) the codes for
the upper-case letters are sequential integers, between 'A' and 'Z'
inclusive; (4) the codes for the digits are sequential integers,
between '0' and '9' inclusive.

Approach to solving this problem:

This problem can be solved by several different algorithms, and its
statement deliberately gives no clue as to which one to use. Further,
while I have presented several facts about the C language, and the
ASCII code, using only these facts may not lead to a successful
solution, and some of these facts may not be helpful. If a method of
solving the problem does not leap to mind immediately, I suggest that
you consider how you might solve the problem by hand. Possibly your
by-hand solution can be translated into one that C will accept. I
suggest you find one solution that should work, code and debug it, and
test it on short sequences of input that you create, comparing the
results your program gets with ones you get by hand.  Your first
solution may not be a particularly good one; you may want to replace it
with a better one which you discover during coding or, even after
testing. Just make sure the one you finally turn in works. As a target,
I think you can write a program whose "speed figure of merit" as
defined above is less than 20N+2000, where there are N characters to
read.