## $Id: s2-chevron.html,v 1.4 1996/09/21 21:28:25 ellard2 Exp ellard2 $
## Dan Ellard -- 10/09/94

A Discussion of Chevron Algorithms

This is a draft of a solution set for a problem set from 1994. The problem, which was part of the second assignment for CS50, was to write a program that prints a "chevron" of a given size. As an example, here's a chevron of size 2:

**
 **
  **
 **
**

Introduction

Almost everyone got their chevron program working (or was very close), and the general quality of the programs was very good.

However, some of the algorithms that were devised to generate the chevrons were quite a bit different than I would have expected, and some were quite a bit more complicated than I expected or hoped to see. While I enjoy a complicated algorithm from time to time, unnecessarily complicated algorithms are usually nothing but trouble. Therefore, I thought I'd take a few moments and write down a short discussion of several algorithms for printing a chevron.

For the sake of simplicity, I'm going to pretend that the assignment is just to write a program that takes a single number and prints a chevron of that size (with no error checking, instructions, etc). This will let me focus on the heart of the algorithm, and skip over the rest of the mechanics (although the rest of the stuff is very important, of course!).


Good Algorithms

Let's start off on a positive note.

Algorithm 1

Many people used an algorithm like the following:

/* ************************************************************ */
/* Dan Ellard
	chevron1.c-- The bread-and-butter chevron program.
*/
/* ************************************************************ */

#include	<stdio.h>
#include	"genlib.h"
#include	"simpio.h"

void		main ()
{
	int		size		= GetInteger ();
	int		row;
	int		spaces;
	int		stars;

	for (row = 0; row < size; row++) {
		for (spaces = 0; spaces < row; spaces++)
			printf (" ");
		for (stars = 0; stars < size; stars++)
			printf ("*");
		printf ("\n");
	}

	for (spaces = 0; spaces < size; spaces++)
		printf (" ");
	for (stars = 0; stars < size; stars++)
		printf ("*");
	printf ("\n");


	for (row = size - 1; row >= 0; row--) {
		for (spaces = 0; spaces < row; spaces++)
			printf (" ");
		for (stars = 0; stars < size; stars++)
			printf ("*");
		printf ("\n");
	}

	exit (0);
}

/* ***************** */
/* end of chevron1.c */
/* ***************** */
This is a perfectly good algorithm. (Of course, how it's written leaves something to be desired- it's horribly short on comments!) It identifies the three main parts of the chevron- the loop where the chevron is "moving to the right", the single middle line with as many spaces as stars, and the loop where the chevron is moving back to the left again.

Algorithm 2

Most people (at least, the majority of the homeworks I've seen) also realized that the middle line is just a special case of one of the loops: by letting the first for loop run up while row <= size (rather than row < size), or by starting the second main for loop at row = size (rather than row = size - 1), a line with the correct properties of the middle line gets produced. A program of this kind looks like the following:

/* ************************************************************ */
/* Dan Ellard
	chevron2.c--

	A variation on chevron1.c: noticing that the middle row of the
	chevron is just the next row that the first for loop would
	have printed, and letting it continue on.  (the same effect
	could be gotten by letting the second for loop start at row =
	size - 1.)

*/
/* ************************************************************ */

#include	<stdio.h>
#include	"genlib.h"
#include	"simpio.h"

void		main ()
{
	int		size		= GetInteger ();
	int		row;
	int		spaces;
	int		stars;

	for (row = 0; row <= size; row++) {
		for (spaces = 0; spaces < row; spaces++)
			printf (" ");
		for (stars = 0; stars < size; stars++)
			printf ("*");
		printf ("\n");
	}

	for (row = size - 1; row >= 0; row--) {
		for (spaces = 0; spaces < row; spaces++)
			printf (" ");
		for (stars = 0; stars < size; stars++)
			printf ("*");
		printf ("\n");
	}

	exit (0);
}

/* ***************** */
/* end of chevron2.c */
/* ***************** */
One again, this is a perfectly good algorithm, but the way that the middle line gets built as a sort of special case of the first or last loops needs a little extra comment (which I have not made in this program!).

If you gave 100 grizzled programmers this simplified chevron problem, and asked them to put together a C program to solve it, 99 of them would probably come up with something very much like the first or the second algorithms.

Algorithm 3

Of course, there's always that last programmer. Let's pretend, for a moment, that it's me. I notice that a chevron is symmetric (reflectively symmetric, for nit-pickers) around the middle row. There should be a nice symmetric way to do this- for example, some sort of loop that runs from from -size to size.

Modifying the first main loop from the previous algorithm to run from -size to zero, and the second loop to run from 1 to size, I realize that I can combine the loops into a single loop, plus a small amount of logic to make sure that I get the right sign on the number of spaces to print out (I wish C had an absolute value operator!). This gives the following:

/* ************************************************************ */
/* Dan Ellard
	chevron3.c--

	Another variation on chevron1.c: noticing that there is
	symmetry between the top and bottom of the chevron, making a
	single for loop which iterates from row = -size to row = size.

*/
/* ************************************************************ */

#include	<stdio.h>
#include	"genlib.h"
#include	"simpio.h"

void		main ()
{
	int		size		= GetInteger ();
	int		row;
	int		spaces;
	int		stars;
	int		spaces_needed;

	for (row = -size; row <= size; row++) {
		spaces_needed = (row < 0) ? size + row : size - row;

		for (spaces = 0; spaces < spaces_needed; spaces++)
			printf (" ");
		for (stars = 0; stars < size; stars++)
			printf ("*");
		printf ("\n");
	}

	exit (0);
}

/* ***************** */
/* end of chevron3.c */
/* ***************** */
That's certainly short and simple, but probably deserves a bit more commenting than the previous algorithms (and an awful lot more than I've given it).


NOT-SO-GOOD ALGORITHMS

Many people realized that the chevron always consisted of 2 * size + 1 rows, and made a loop like the following:

	for (row = 0; row < 2 * size + 1; row++) {
		if ( I'm in the top part )
			print a top-part row

		else if ( I'm in the middle )
			print the middle row

		else
			print a bottom-part row
	}
This works, but is very clumsy, especially because of the complicated formulas necessary to figure out how many spaces to print (particularly in the bottom-part row. It's much simpler to have different loops counting up or down in order to figure out the number of spaces directly from the index of the loop.

Stylistically, this algorithm is also very misleading. The if-else inside the loop is not a function of anything except the row and the size, so there really isn't any question which way you're going to go on each particular iteration. The if-else is essentially just a way to fake the single for-loop into behaving like two separate loops. Don't do it!


Please bring any errors or inconsistencies in this document to the attention of the author.

Dan Ellard <ellard@deas.harvard.edu>