Lecture 32

Announcements

Talking Points

None of this material is in the textbook.

What makes code good?

Short answer: nothing.

Better question: what makes one piece of code better or worse than another?

Consider the following two code samples:

int x = a;
int y = b;
// swap x and y:
int tmp = x; // x = a, y = b, tmp = a
x = y;       // x = b, y = b, tmp = a
y = tmp;     // x = b, y = a, tmp = a

int x = a;
int y = b;
// swap x and y:
x -= y;    // x = a-b,         y = b
y += x;    // x = a-b,         y = b+(a-b) = a
x = y - x; // x = a-(a-b) = b, y = a

Which one is a better way of swapping two variables?

Speed₁, Speed₂, Clarity, Correctness

Some code runs quickly, and some code runs REALLY quickly. It is hard to write code that is slower than a human.

Some code can be written in seconds, and some code is takes years to write.

Some code is confusing, and some code is REALLY confusing. It is hard to write code that doesn't require effort to understand.

Some code is good enough, and some code is almost right. It is possible, though very rarely done, to write code that is provably correct.

Examples: Counting rooms

Goal: count the number of square rooms.

In what ways are the following good or bad?

robot.say(16 + " rooms");

int count = 1; 
while(robot.check("E")) { 
    robot.go("E"); 
    count += 1; 
} 
robot.say(count*count + " rooms");

int width = 1; 
while(robot.check("E")) { 
    robot.go("E"); 
    width += 1; 
}
int height = 1; 
while(robot.check("S")) { 
    robot.go("S"); 
    height += 1; 
}
robot.say(width*height + " rooms");

while(robot.check("N")) robot.go("N");
while(robot.check("W")) robot.go("W");
int count = 1; 
while(robot.check("E")) { 
    robot.go("E"); 
    count += 1; 
}
while (robot.check("S")) {
    robot.go("S");
    while(robot.check("W")) robot.go("W");
    count += 1; 
    while(robot.check("E")) { 
        robot.go("E"); 
        count += 1; 
    }
}
robot.say(count + " rooms");

ArrayList<String> visited = new ArrayList<String>();
String directions = "NSEW";
int x = 132;
int y = -11;
while (true) {
    int dir = (int)(Math.random()*4);
    char cdir = directions.charAt(dir);
    if (robot.check(cdir)) {
        robot.go(cdir);
        if (cdir == 'N') y += 1;
        if (cdir == 'S') y -= 1;
        if (cdir == 'E') x += 1;
        if (cdir == 'W') x -= 1;
        String room = x+","+y;
        if (!visited.contains(room)) {
            visited.add(room);
            robot.say(visited.size()+" rooms so far");
        }
    }
    
}

// how we got where we are: something like [N, N, E, S, E, E, N, W]
ArrayList<String> trail = new ArrayList<String>(); 

// distinct rooms we know of: something like ["0,0", "1,0", "1,-1"]
ArrayList<String> rooms = new ArrayList<String>();

 // what's left to explore: something like ["0,0,W", "0,0,S", "0,1,S"]
ArrayList<String> pending = new ArrayList<String>();

// we start in some room; let's call that room 0,0
int x = 0;
int y = 0;

// remember we are here and which doors we haven't tried yet
rooms.add(x+","+y);
if (robot.check("N")) { 
    pending.add(x+","+y+",N"); 
    rooms.add(x+","+(y-1)); 
}
if (robot.check("S")) { 
    pending.add(x+","+y+",S"); 
    rooms.add(x+","+(y+1)); 
}
if (robot.check("E")) { 
    pending.add(x+","+y+",E"); 
    rooms.add((x+1)+","+y); 
}
if (robot.check("W")) { 
    pending.add(x+","+y+",W"); 
    rooms.add((x-1)+","+y); 
}

// check one door at a time until we've checked them all
while (pending.size() > 0) {
    // remove a room,door pair from the end of the pending list
    String[] xyd = pending.get(pending.size()-1).split(",");
    pending.remove(pending.size()-1);
    
    // back up along our own trail to that cell
    int cx = Integer.parseInt(xyd[0]);
    int cy = Integer.parseInt(xyd[1]);
    while (cx != x || cy != y) {
        String dir = trail.get(trail.size()-1);
        trail.remove(trail.size()-1);
        if (dir.equals("N")) { robot.go("S"); y += 1; }
        if (dir.equals("S")) { robot.go("N"); y -= 1; }
        if (dir.equals("E")) { robot.go("W"); x -= 1; }
        if (dir.equals("W")) { robot.go("E"); x += 1; }
    }
    
    // move in an unexplored direction, add that movement to our trail
    trail.add(xyd[2]);
    robot.go(xyd[2]);
    if (xyd[2].equals("N")) y -= 1;
    if (xyd[2].equals("S")) y += 1;
    if (xyd[2].equals("E")) x += 1;
    if (xyd[2].equals("W")) x -= 1;
    
    // add any doors to new rooms to our lists
    if (robot.check("N") && !rooms.contains(x+","+(y-1))) {
        pending.add(x+","+y+",N");
    rooms.add(x+","+(y-1)); 
    }
    if (robot.check("S") && !rooms.contains(x+","+(y+1))) {
    pending.add(x+","+y+",S");
    rooms.add(x+","+(y+1));
    }
    if (robot.check("E") && !rooms.contains((x+1)+","+y)) {
    pending.add(x+","+y+",E");
    rooms.add((x+1)+","+y);
    }
    if (robot.check("W") && !rooms.contains((x-1)+","+y)) {
    pending.add(x+","+y+",W");
    rooms.add((x-1)+","+y);
    }
}

// We've kept track of every room; return the length of that list
robot.say(rooms.size() + " rooms");