Lecture Notes for CS 509, Advanced Programming II

16 March 2004, Assignment 2 Code Review

Outline

• Design

• Testing

• Problems

Ouroborous Compression

• When you have a problem, play with it.

  • See how it behaves. What are the extreme points? Why?

• Any particular arrangement of strings can be compressed (possibly).

  gerbil kissing singer -> gerbilkissinger
  

• Some arrangements of strings produce better compressions than others.

  kissing singer gerbil -> kissingerbil
  

• Trying all arrangements is one possibility.

  • Take the best compression as the winner.

• This is a design technique known as exhaustive search.

Generating Arrangements

• Ouroborous compression has been reduced to producing string arrangements.

• This is known as generating permutations.

  • Gosh, I wish I had a function that permutes strings.

  • O.k. *poof* you've got it.

maximal-ouroboros-compression(strings)
  best, key = compress_string(strings)

  foreach p = generate-permutations(strings)
    s, k = compress-string(p)
    if s.len() < best.len()
      best = s
      key = k

  return best, key

Generating Permutations

• How do I generate permutations?

  • You could use the std::next-permutation() generic algorithm.

• Play with the problem. How do you permute one string?

  • Duh - the string itself.

• How do you permute two strings?

  • Permute one string, then stick the other one every place it fits.

  { kissing, singer } -> singer)
  singer -> { singer }
  { singer } -> { kissing singer, singer kissing }
  

• How do you permute three strings?

  • Remove one string, permute the remaining two strings, stick the third string back every place it fits.

  { kissing, singer, gerbil } -> { kissing, singer }
  { kissing, singer } -> { kissing singer, singer kissing }
  { kissing singer, singer kissing } -> { gerbil kissing singer,
  					kissing gerbil singer,
  					kissing singer gerbil,
  					gerbil singer kissing,
  					singer gerbil kissing,
  					singer kissing gerbil }
  

Permutation code

permutations(strings)

  if strings.size == 1
    return strings

  s = pick strings
  perms = { }
  for each p in permutations(strings)
    for each gap between words in p
      stick s in the gap and add the result to perms

  return perms

• This is not an intelligent approach.

  • It's wickedly expensive in time and space.

  • An incrementally generative approach takes less space.

    • But is more complicated and convolutes code.

    • See my solution for an example of an incrementally generative solution.

Tests

1. Empty test.

2. Kissing-singer-gerbil test.

3. Error test.

4. aaa-aa-a permutation tests.

5. aaa-aaa-aaa test.

6. aaa-bbb-ccc test.

Test Results

• With SaferSTL

  	c	n	-	+	y
  1	0	0	0	0	5
  2	0	1	0	0	4
  3	0	1	0	0	4
  4	0	3	0	0	2
  5	0	3	0	0	2
  6	0	2	0	0	3

• Without SaferSTL

  	c	n	-	+	y
  1	0	0	0	0	5
  2	0	0	0	0	5
  3	0	0	0	0	5
  4	0	2	0	0	3
  5	0	2	0	0	3
  6	0	1	0	0	4

Get IO Right

• Make sure you have something to work on before you go to work.

  while true
    getline(cin, s)
    if !s.empty() && notallblanks(s)
      strvec.push_back(s)
    if (cin.eof())
       break;
  

  • SaferSTL is designed to make this kind of code fail.

• Read, then test, then go to work.

  while getline(cin, s)
    if !s.empty() && notallblanks(s)
      strvec.push_back(s)
  
  if (not cin.eof())
    std::cerr << "! input error..."
  

To Name Something is to Create a World

• Make sure it's a world you want to live in.

  void
  findfromcomp (
    string & st1, string & st2, int &i1, int &i2,
    vector <pair <int, int> >&ckey1, 
    vector <pair <int, int> >&ckey2, 
    int &comp_i, int &comp_j, 
    vector <pair <string, int> >&ipvec, 
    vector <pair <string, int> >&newipvec,
    vector <vector <pair <int, int> > >&key,
    vector <vector <pair <int, int> > >&newkey,
    vector <indi> &compressed, int i, int j) {
  
  void rrcompress(
    int idi,int idj,int idc,string &st1,int &i1,
    vector <pair <int, int> >&ckey1,
    string &st2, int &i2, 
    vector <pair <int, int> >&ckey2,
    vector <pair <string, int> >&newipvec,
    vector <vector <pair <int, int> > >&newkey,
    vector <indi> &compressed,
    vector <pair <string,int> >&ipvec,
    vector <vector <pair <int, int> > >&key,
    vector <pair <string,int> >&fipvec,
    vector <vector <pair <int, int> > >&fkey,
    vector <int> &refvec,vector<int> &stadded,
    vector <indi> &indices) {
  

Use typedefs

• Use typedefs to define type synonyms.

  typedef std::pair<int, int> int_pair;
  typedef std::vector<ipair>  ipair_vec;
  typedef std::pair<std::string, int> strint_pair;
  typedef std::vector<strint_pair> strint_pairs;
  

• And give the typedefs meaningful names.

  • Names should indicate purpose or function, not structure.

    • Sorry Hungarians.

  typedef std::pair<int, int> key;
  typedef std::vector<key>  keys;
  typedef std::pair<std::string, int> string_offset;
  typedef std::vector<string_offset> string_offsets;
  

• Well chosen typedefs make code easier to read.

  • They also make it easier to change.

Control Complexity

• Good programmers control complexity.

  • Bad programmers fall prey to it, or, even worse, don't even recognize it.

• What is complexity?

  • A rule of thumb: more than two or three of anything is complex.

    • More than two or three parameters is complex.

    • Nesting statements more than two or three deep is complex.

    • Comments more than two or three lines are complex.

Comment Well

• What do these comments mean?

  // ou1**+ou2** 
  
  // ou2** + ou1**  
  
  // ou2 + ou1** 
  
  // ou1 + ou2**
  
  // ou1** + ou2 
  
  // ou2** +ou1 
  

• You are writing comments to communicate with other people.

  • Make sure you do communicate.

Write it Once

• Duplicate code is bad code.

  • Almost duplicate code is worse.

  /*single+mixed*/
  // ou2 + ou1**
  
  if (ou1.getKey().size() > 1) && (comm < 0)
     && (ou2.getKey().size() == 1)
    comm* = -1
    int fl = ou1.getFirstLength()
    int ll = ou1.getLastLength()
    list<uncom_key> k = ou1.getKeyWithoutFirst()
    return combineMixedCase1(
      str2, str1, key2, k, sz2, sz1, comm, fl, ll)
  
  // ou1 + ou2**
  
  else if (ou2.getKey().size() > 1) && (comm >= 0)
          && (ou1.getKey().size() == 1)
    int fl = ou2.getFirstLength()
    int ll = ou2.getLastLength()
    list<uncom_key> k = ou2.getKeyWithoutFirst()
    return combineMixedCase1(
      str1, str2, key1, k, sz1, sz2, comm, fl, ll)
  

Factor Common Code

• Factor common code into subroutines.

  static bool
  p(ou1, ou2) 
    return (ou1.getKey().size() > 1) && 
           (ou2.getKey().size() == 1)
  
  static int 
  f(ou, str1, str2, key, sz1, sz2, comm) 
    int f = ou.getFirstLength()
    int l = ou.getLastLength()
    list<uncom_key> k = ou.getKeyWithoutFirst()
    return combineMixedCase1(
      str1, str2, key, k, sz1, sz2, comm, f, l)
  
  if b(ou1, ou2) && (comm < 0)
    comm *= -1
    return 
      f(ou1, str2, str1, key2, sz2, sz1, comm)
  
  if b(ou2, ou1) && (comm >= 0)
    return 
      f(ou2, str1, str2, key1, sz1, sz2, comm)
  

Points to Remember

• Play with the problem to find its secrets.

• Make sure you have something to work on before you go to work.

• Use typedefs to clarify your code.

  • Provide meaningful information and allow for easy changes.

• Control complexity, don't let it control you.

  • More than two or three is complex.

This page last modified on 18 March 2004.