Lecture Notes for CS 509, Advanced Programming II

6 April 2004, Assignment 3 Code Review

Outline

• Design

• Testing

• Problems

Exhaustive Search

• Given a set P of n planar points, find all regular polygons.

• Rely on our old friend exhaustive search.

  find_polygons(s)
  
    answer = { }
  
    for each ss in powerset(s)
        if is-regular-polygon(ss)
          answer += { ss }
  
    return answer
  

• This is a short, correct, and wickedly expensive solution.

  • An n-element set has 2ⁿ subsets.

Know the Problem

• This is a problem with a lot of structure.

  • Find it and exploit it to produce a better solution.

• Given n planar points, pick any two.
  

  • Is this an edge of a regular polygon?

• If it is, we can derive the other vertices from it.

  • And then look for the vertices in the set.

Generating Polygons

• For every line, generate polygons and check.

  find_polys(s)
    s' = s
    polys = { }
    while s not empty
      p1 = pick s
      foreach p2 in s
        check(p1, p2, polys, s')
        check(p2, p1, polys, s')
  
    return polys
  
  check(p1, p2, polys, points)
  
    for i = 3 to points.size()
      rp = generate(i, p1, p2)
      if rp in points
        polys += rp
  

• This algorithm takes O() time' .

Can We Do Better?

• Although not exponential, polygon searching is still expensive.

  • Search for points that may not exist.

  • Search through everything rather than a subset.

• Can we hone the search to look at only existing things intelligently?
  

  • Rather than look at points, look at edges.

• Only same-sized edges can be in the same polygon.

Edge-Sorted Search

• Sort the edges by length into buckets.

• Find the polygons in each bucket.

  find_polys(s)
    while s.size > 2
      p1 = pick s
      foreach p2 in s
        edges[dist(p1, p2)] += (p1, p2)
  
    polys = { }
    foreach e in edges
      polys += chains(e->second)
  
    return polys
  
  chains(edges)
    g = create_graph(edges)
    return dfs_cycle_find(g)
  

• This algorithm takes O(n² log n) time .

But Wait - There's Less!

• What kind of graph are we dealing with?

  • A complete graph, a graph with all edges.

• There's no need to sort the edges.

  • Just fill the n-by-n adjacency matrix with edge distances.

  • Run the dfs cycle finder over the matrix.

    • Being careful of floating point numbers.

• This algorithm has O(n²) behavior.

Tests

• There were eight tests.

  1. Empty

  2. Garbage

  3. An odd number of coordinates.

  4. A non-number input.

  5. Simple square.

  6. Simple octagon, one octagon and two squares.

  7. Duplicate triangle points.

  8. Orientation test.

What Happened

	c	n	-	+	y
Empty					5
Garbage		1			4
Odd		1			4
Non-number		2			3
Square		2			3
Octagon					5
Duplicate		2			3
Orientation		4			1

• Crashed, wrong, not completely wrong, almost right, right.

Symmetry

• Symmetric relations are a useful design technique.

  • Exploiting symmetry can simplify design.

  • The absence of symmetry suggests a problem.

• For example, which is better

  int main ()
    polygon T
    T.read_input(std::cin)
    T.find_polys()
  

  or

  int main ()
    polygon T
    T.read_input(std::cin)
    T.find_polys()
    T.write_output(std::cout)
  

  Why?

Understand Why Input Ended

• This code failed for non-integer input. Why?

  std::copy(
    std::istream_iterator(std::cin), 
    std::istream_iterator(),
    std::back_inserter(v))
  
  validation(v)
  

• Check to make sure input ended for the right reason.

  std::copy(...)
  
  if not std::cin.eof()
    error: Input error while reading points.
  
  validation(v)
  

No Loops

• Replace loops

  while true
    in >> x
    if in.eof()
      break
    if in.fail()
      abort("Data format error for x value")
    in >> y
    if in.eof()
      abort("! x value but no y value")
    if in.fail()
      abort("Data format error for y value")
    point tmp(x,y)
    point_list.push_back(tmp)
  

  with generic algorithms.

  std::copy(
    std::istream_iterator<point>(std::cin),
    std::istream_iterator<point>(),
    std::back_inserter(point_list))
  

Points to Remember

• There is a better way - find it.

• You can't solve a problem you don't understand.

  • The greater the understanding, the better the solution.

• Make friends with symmetry.

  • Double your productivity, halve your problems.

• I-O in C++ is tricky.

  • Keep it simple.

This page last modified on 28 April 2004.