K&R Solutions - 1.13, Part 2

Q: The same as part one, but vertical.

A:

#include <stdio.h>

int main(void) 
{
  int FREQUENCY_LENGTH = 10; 
  int frequencies[FREQUENCY_LENGTH];
  int i, j, c;
  int tally = 0;
  int highest = 0;

  // We're tallying in the exact same way.
  for (i = 0; i < FREQUENCY_LENGTH; ++i) {
    frequencies[i] = 0;
  }

  while ((c = getchar()) != EOF) {
    if (c == '.' || c == '\n' || c == '\t' || c == ' ' || c == ',') {
      if (tally > FREQUENCY_LENGTH) {
        tally = FREQUENCY_LENGTH - 1;
      }
      ++frequencies[tally];
      tally = 0;
    } else {
      ++tally;
    }
  }

  /* First, we need the height of the highest bar.
  *  At the top of the function, temp is set to zero. Normally a function
  *  wouldn't be this long, but we haven't got to that part fo the book yet.
  */
  for (i = 0; i < FREQUENCY_LENGTH; i++) {
    if (frequencies[i] > highest) {
      highest = frequencies[i];
    }
  }

  /* Now we keep drawing the bars untill our 'highest' variable, and everything
   * in our tallies is zeroed out.
   */
  while (highest) {
    // Remember there are no zero-length words so we skip 0. Feel free to play
    // around with this, because some junk data is getting stored in
    // frequencies[0]. Why?
    for(i = 1; i < FREQUENCY_LENGTH; i++) {
      if (frequencies[i] == highest) {
        printf(" | ");
        frequencies[i]--;
      } else {
        printf("   ");
      }
    }
    printf("\n");
    highest--;
  }

  /* Now we print a handy guide at the bottom.
   */
  for (i = 1; i < FREQUENCY_LENGTH; i++) {
    printf("---");
  }
  printf("-\n");
  for (i = 1; i < FREQUENCY_LENGTH; i++) {
    if (i == FREQUENCY_LENGTH - 1) {
      printf(" %d+", i);
    } else {
      printf(" %d ", i);
    }
  }
  printf("\n");

  return 0;
}
The worst of misery
Is when a nature framed for noblest things
Condemns itself in youth to petty joys,
And, sore athirst for air, breathes scanty life
Gasping from out the shallows.
Supercalifragilisticexpialidocious.

(ctrl+d)

       |                   
       |        |          
       |  |     |          
    |  |  |     |          
    |  |  |  |  |  |  |    
    |  |  |  |  |  |  |    
 |  |  |  |  |  |  |  |  | 
----------------------------
 1  2  3  4  5  6  7  8  9+ 

You can play around with this quite a bit. Removing one line and then changing one character, and we get a nice little graph:

       .                   
                .          
          .                
    .                      
             .     .  .    
                           
 .                       . 
----------------------------
 1  2  3  4  5  6  7  8  9+ 


'Build Your Own Lisp' Solutions: 3.12

Q: What does the 'typedef' keyword do exactly?


A: 'typedef' lets you define a type, which is to say, it lets you give a new name to a pre-existing type (which can be useful for organizational/readability purposes), or to define a struct as a new type, unique to your program.



K&R Solutions - 1.13, Part 1

Q: Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.

A:

#include <stdio.h>

int main(void) 
{
  /* Because of screen space and the limitations of terminal output, words
   * longer than ten are going to be categorized as greater than 10.
   * 
   * In this model, frequencies[0] is a one-character word, and frequencies[1]
   * is a two-character word. This 'off-by-one' behaviour seems unintuitive
   * and certainly leads to bugs, but there is a very good, low-level reason
   * that becomes very obvious when you learn a bit of assembly. You could find
   * a work-around (like leaving frequencies[0] unused), but it's better to get
   * use to thinking of things as starting with the 0th element because, in the
   * long run, there's no real avoiding it in programming.
   */
  int FREQUENCY_LENGTH = 10; 
  // It's tradition to capitalize this we won't be changing.
  int frequencies[FREQUENCY_LENGTH];
  int i, j, c;
  int tally = 0;

  /* Initialize all frequencies to 0 */
  /* The book hasn't told us this yet, but the easiest way to initiate all
   * elements in an array to 0 is simply to go:
   * int frequencies[10] = {0};
   * BUT doing it with what the book has tought us gives us a better feel for
   * the way that arrays work.
   */
  for (i = 0; i < FREQUENCY_LENGTH; ++i) {
    frequencies[i] = 0;
  }

  /* Count word-length frequencies */
  /* I'm missing colons and semi-colons here for the sake of space, but you get
   * the drift. In a professional setting, you would probably want to create 
   * a separate subroutine called is_word_barrier() to keep your code cleaner
   * and more readable, but we haven't got to that part of the book yet. 
   */
  while ((c = getchar()) != EOF) {
    if (c == '.' || c == '\n' || c == '\t' || c == ' ' || c == ',') {
      if (tally > FREQUENCY_LENGTH) {
        tally = FREQUENCY_LENGTH - 1;
      }
      ++frequencies[tally];
      tally = 0;
    } else {
      ++tally;
    }
  }

  /* Print horizontal-barred histogram */
  printf("\n");
  printf("Word Frequencies: Horizontal\n");
  printf("----------------------------\n");
  for (i = 0; i < FREQUENCY_LENGTH; ++i) {
    if (i != 0) {
      if (i == FREQUENCY_LENGTH - 1) {
        printf("%3d+ | ", i);
      } else {
        printf("%3d  | ", i);
      } 
      for (j = 0; j < frequencies[i]; ++j) {
        printf("-");
      }
      printf("\n");
    }
  }

  return 0;
}
The worst of misery
Is when a nature framed for noblest things
Condemns itself in youth to petty joys,
And, sore athirst for air, breathes scanty life
Gasping from out the shallows.
Supercalifragilisticexpialidocious.

(ctrl+d)

Word Frequencies: Horizontal
----------------------------
  1  | -
  2  | ----
  3  | -------
  4  | -----
  5  | ---
  6  | ------
  7  | ---
  8  | ---
  9+ | -


K&R Solutions - 1.12

Q: Write a program that prints its input one word per line.

A:

#include <stdio.h>

int main(void)
{
  char c;

  while ((c = getchar()) != EOF) {
    if (c == '\t' || c == '\n' || c == ' ') {
      printf("\n");
    } else {
      putchar(c);
    }
  }

  return 0;
}
> muh muh muh     moo cows
muh
muh
muh
moo
cows


SICP Solutions - 1.7

Q: Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value:

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these square-root and cube-root procedures.)


A:

;; The setup is the same, except for the names.
(define (cbrt-iter guess x)
  (if (good-enough? guess x)
    guess
    (cbrt-iter (improve guess x)
               x)))

(define (cube x)
  (* x x x))

(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))

(define (cbrt x)
  (cbrt-iter 1.0 x))

;; The formula in scheme.
(define (improve guess x)
  (/ 
    (+ (/ x (* guess guess)) (* 2 guess))
    3))

;; A few guesses.
(display (cbrt 8))
(newline)
(display (cbrt 27))
(newline)
(display (cbrt 60))
(newline)
2.0000049116755
3.00000054106418
3.91487458417134 ; My calculator gives 3.91486764117


'Build Your Own Lisp' Solutions: 3.11

Q: What is the continue keyword and what does it do?


A: In a while or for loop, 'continue' will skip the rest of the block and go straight to the next iteration of the loop. Here is a program that counts to twenty, using 'continue' to filter out undesirable multiples of three:

#include <stdio.h>

int main(void)
{
  int i = 0;

  while (++i <= 20) {
    if (i % 3 == 0) {
      continue;
    }
    printf("%d\n", i);
  }

  return 0;
}
1
2
4
5
7
8
10
11
13
14
16
17
19
20


'Build Your Own Lisp' Solutions: 3.10

Q: What is the break keyword and what does it do?


A: Break breaks out of a while loop or a for loop, from within the body of that loop. Here is a program that will run a loop over nine quintillion times on most computers, before the number gets too bug for 'unsigned int' and goes back to zero:

#include <stdio.h>

int main(void)
{
  unsigned int i = 0;

  while (++i) {
    printf("%d: Looping...\n", i);
  }

  return 0;
}
1: Looping...
2: Looping...
3: Looping...
4: Looping...
5: Looping...
6: Looping...
7: Looping...
8: Looping...
9: Looping...
10: Looping...
...
9223372036854775806: Looping...

Since nine quintillion is overkill for most programs, we can use a break statement to stop it at, say, three.

#include <stdio.h>

int main(void)
{
  unsigned int i = 0;

  while (++i) {
    printf("%d: Looping...\n", i);
    if (i == 3) {
      break;
    }
  }

  return 0;
}
1: Looping...
2: Looping...
3: Looping...


K&R Solutions - 1.11

Q: How would you test the word count program? What kinds of input are most likely to uncover bugs if there are any?


A: There is no perfect answer to this kind of question. Writing good test is really a matter of experience. Part of the reason all programs have bugs is that even the best test writers can't anticipate all the wild ways a program will be used by other people. Nevertheless, writing good tests is a good skill to develop, as you can filter out about 99% of potential bugs that way, and prevent unexpected behaviour when you make small changes to large programs.


The first thing I would do is test it will no characters at all, hoping for '0 0 0'. Next, test it with one word, then with one tab, then with one newline. The a tab and a newline, then a newline and a tab... you probably don't need the full 16, but instinct tells me that starting input with white space might cause problems. After that, a few short strings like 'two words' will cover the basics.


That might seem like a lot but, really, you write a test once, and get the peace of mind forever.



K&R Solutions - 1.10

Q: Write a program to copy its input to its output, replacing each tab by \t , each backspace by \b , and each backslash by \\ . This makes tabs and backspaces visible in an unambiguous way.

A:

#include <stdio.h>

int main(void)
{
  char c;

  while ((c = getchar()) != EOF) {
    if (c == '\t') {
      printf("\\t");
    } else if (c == '\b') {
      printf("\\b");
    } else if (c == '\\') {
      printf("\\\\");
    } else {
      putchar(c);
    }
  }

  return 0;
}
tab	example
tab\texample
\ example
\\ example
Backspace example doesn't work!
Backspace example doesn't work!

Denis Richie standing by the computer where he invented C

Notes:

Your terminal emulator takes care of automatically backspacing for you, so the final part of this exercise is long-obsolete.


Explicit backspaces were a problem Richie dealt with when they were developing C and Unix in the 70s. Their office computer didn't have a monitor, only a printer (teletype) which didn't show the characters you had already backspaced (in fact, it added the whitespace \b which was applied as a character deletion only after you saved the line); you just had to try to keep track of your corrections in your head.


According to people around back then, the reason C tends to be so terse, and keywords/variable names tended to be so short, is that backspacing was so frustratingly difficult to keep track of that they wanted to keep the lines as short as possible. This is contrary to the modern style, where clear names are considered extremely important.


It's pretty easy (and fun) to run Unix 6 on an emulator, to get a bit of a taste of what these people were dealing with back then. After trying to write a few small programs, you'll get a pretty good feeling for why old Unix culture discouraged long names.