Computer Algorithms II Lecture Notes

2 October 2007 • Assignment 1 Code Review

Outline

• Problem and Solution Design.

• Testing.

• Coding comments.

The Problem

• What's the problem?

  • Neaten up circle-and-line diagrams.

• How do you solve this problem?

  • You need to be able to

    1. Read shapes.

    2. Neaten shapes.

    3. Output neatened shapes.

• How do you do that?

Design by Wishful Thinking

• In design by wishful thinking you

  • Figure out what you need.

  • Wish for it.

  • *Poof* There it is.

  • Use it to solve the problem.

• Also known as top-down design or structured refinement.

The Solution

• What do you need?

  A shape reader. *poof* read-shapes()
  A shape neatener. *poof* neaten-shapes()
  A shape writer. *poof* write-shapes()

• And there you go:

  main()
    write-shapes(std::cout, 
      neaten-shapes(
        read-shapes(std::cin)))
  

About Those Wishes

• Are we done? Can we watch tv now?

• Unless you have a genii (or a good system library), there's more work to do.

• The orignal problem, now solved, has been replaced by three other problems:

  1. Reading shapes.

  2. Neatening shapes.

  3. Writing shapes.

Three New Problems

• Of the three new problems,

  • Writing shapes has an easy solution.

  • Reading shapes has a solution, maybe not easy.

  • Neatening shapes seems like a hard problem.

• The next-problem choice is up to you.

  • Hardest first, easiest first.

  • Important first, less important first.

Shape Neatening

• What's the problem?

  • Given a set of circles and lines, make them neat.

    • Uniform radii, centers horizontally, vertically, and diagonally alligned.

    • Lines horizontal, vertical or diagonal, center-to-center aligned.

• How do we solve this problem? What do we wish for?

Snap To Grid

• Many drawing programs use snap-to-grid to make neat freehand drawings.

  • Key points (centers, end-points, radii) are constrained to coinside with grid points.

Wishful Thinking

• Given a set of messy shapes, return a set of neatened shapes.

• What to wish for?

  • Neaten shapes by snapping to the grid.

• Grid? What grid?

  • Unfortunately, each drawing needs its own grid.

  • Generate a grid for the shapes.

Neatening

• Successful wishing leads to

  shapes neaten-shapes(shapes)
    return 
      neaten(shapes, make-grid(shapes))
  

• The remaining problems are

  • Generate a grid.

  • Snap shapes to the grid.

• Snapping shapes is easy.

Grid Behavior

• To make a grid, understand what it does.

  

• A grid groups coordinates on each axis along specific values.

Making Grids

• Make a histogram of the coordinates along each axis.

  • Bucket size is the approximately the average circle radius.

  • Non-empty buckets should not be adjacent.

    • Play with the bucket size, or dump one bucket into the other.

• Tip: just use circles; add lines once circles are snapped.

Example

• Bucket size is the average circle diameter.

• The coordinate c snapped is

  d*bno + d/2 = d*(bno + 0.5)
  

Comments

• Snapping to grid is fast and simple, but it isn't robust.

  • Getting good histograms is difficult.

  • Moderately sloppy drawings confuse it.

  • Isolated circles are mis-neatened.

  • Diagonals confuse it.

• Ignoring lines loses a lot of information.

Review

• The story so far:

  

Reading Shapes

• From the problem: read a bunch of strokes, classify them as shapes.

• I wish I had:

  • A stoke reader.

  • A stroke classifier.

• Stroke reading's easy; that leaves classifying strokes.

Stroke Types

• Here's some strokes:

  

  How do you tell them apart?

Stroke Characteristics

• Line stokes are long and thin; circle stokes are not.

• “Long and thin” means what?

  • Line stroke height (or width) is much greater than line stroke width (or height).

  • Circle stroke height and width are about the same.

Classifying Strokes

• Surround each stroke in a tight box (the bounding box).

• If the bounding box aspect ratio (height/width) is around 1, the stroke's a circle.

  • Otherwise it's a line.

  • If height > width, it's vertical, otherwise it's horizontal.

• But...

Ambiguous Strokes

• What about these strokes?

  

• How can diagonal lines be distinguised from circles?

Diagonal Strokes

• A diagonal stroke is larger than its bounding box.

  • Length > height and width.

• But what's a circle's length?

  • What's a line's lenght?

    • The distance between the start and end.

  • It's the same for a circle.

Classifying Strokes Revised

• If the bounding box aspect ratio isn't 1, the stroke's a line.

• Otherwise

  • Compute the distance between the first and last points in the stroke.

  • If the length's larger or near the bounding box size, the stroke's a diagonal line.

  • Otherwise it's a circle.

Summary

• The whole* story:

  

• *Grotty, uninteresting details omitted.

  • See the code for every last detail.

The Test Cases

• A single node.

• A vertical dumbell.

• A horizontal dumbell.

• A star.

• All points calculated with no jitter (that is, they're already neat).

The Test Results

• Not too good:

  • Two assignments didn't compile.

  • The rest didn't get one test right.

Test Your Code

• Test your code - it's important.

• The tests don't have to be complicated.

  • Simple tests applied consistently do the trick.

• Testing your own code is hard.

  • Your own child never needs a spanking.

  • Get someone else to do it.

• Code a little, test a little.

Follow Directions

cout << "Enter input-file name:  ";
getline(cin, fileName);

• Where did this come from? Not from the assignment.

• Much depends on your abiblity to follow directions.

  *** Dumbbell test
  
  ! Unexpected input: "Enter input-file name:  ".
  

Don't Prompt

• Don't prompt for input, don't decorate output.

  // prompt symbol for start of program
  cerr << ">";
  

• Much depends on your abiblity to follow directions.

  *** Dumbbell test
  
  ! Unexpected input: ">>".
  

Know your tools

• What does this code do?

  radius = sqrt((centerY + centerX)^2 + 
                (maxY + holdMaxYx)^2);
  

• It's also interesting to comtemplate what this code was supposed to do.

  • Your co-workers might not appriceate the opportunity, though.

• Can you write a test to find this error?

No Marimba Ponies

if 
  ((((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) ==
   ((yVals.at(checkY) - minY)/(xVals.at(checkX)))) || 
   ((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) == 
   ((yVals.at(checkY) - minY)/(xVals.at(checkX))) - 1)) || 
   ((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) == 
   ((yVals.at(checkY) - minY)/(xVals.at(checkX))) - 2) || 
   ((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) ==
   ((yVals.at(checkY) - minY)/(xVals.at(checkX))) - 3) || 
   ((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) == 
   ((yVals.at(checkY) - minY)/(xVals.at(checkX))) + 1) ||
   ((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) == 
   ((yVals.at(checkY) - minY)/(xVals.at(checkX))) + 2) || 
   ((maxY - yVals.at(checkY))/(maxX - xVals.at(checkX)) == 
   ((yVals.at(checkY) - minY)/(xVals.at(checkX))) + 3)) 
   { ... }

Points to Remember

• Understand the problem

  • You can't solve it if you can't understand it.

• Think before you program.

  • A little thinking replaces a lot of typing.

• Test your code; find your errors before others do.

• Use good programming practice.

• Know your tools.