CS100, Spring 2000, Solutions to Prelim 3

Problem 1 [28 points]

best version:

    int[][] collapse(int[][] x) {
        int[][] y = new int [x.length] [x[0].length/2]; // collapsed array
        // process each row: i = #rows processsed = next row to process
            for (int i = 0; i < x.length;   i++) {
                // move "black" elements from x to y:
                // j = position of next black element in x to move
                    int k = 0; // where in y to store next element 
                    for (int j = i % 2 ; j < x[i].length ; j += 2) {
                        y[i][k] = x[i][j];  k++;
                    }
            }
        return y;
    }

remark: could keep track of i % 2 in a variable $start$:

    ...
    int start = 0; // position of first "black" element in row i
    for (int i = ...
        for (int j = start ...
        start = 1 - start;
    }
    ...

inefficient version that looks at each column in each row:

    int[][] collapse(int[][] x) {
        int[][] y = new int [x.length] [x[0].length/2]; // collapsed array
        // process each row: i = #rows processsed = next row to process
            for (int i = 0; i < x.length;   i++) {
                // move "black" elements from x to y:
                // j = next column in x to process
                    int k = 0; // where in y to store next element 
                    for (int j = 0; j < x[i].length ; j++) if (i+j % 2 == 0) {
                        y[i][k] = x[i][j];  k++;
                    }
            }
        return y;
    }

===============================================================================

Problem 2 [25 points]

// return bottom line of a canonical equivalent to key = (top, bottom)
String canon(String top, String bottom) {
    char[] b = new char[top.length()]; // canonical bottom line
    // move character mappings to b: (top[0..i-1], bottom[0..i-1]) already moved
        for (int i = 0; i < top.length(); i++)
            b [top.charAt(i) - 'a'] = bottom.charAt(i);
    return new String(b);
}

===============================================================================
 Problems 3a and 3b [28 points + 5 bonus points + 19 points]

// a rectangle
public class Rect {
    // instance variables for boundaries: left, right, top, bottom
        private int left; private int right; private int top; private int bottom;

    // constructor: create a Rect with left=l, right=r, top=t, bottom=b
    public Rect (int l, int r, int t, int b) {
        left = l; right = r; top = t; bottom = b;
    }

    // draw filled-in with color c
    public void paint(Graphics g, Color c) {
        g.setColor(c);
        g.fillRect(left, top, right-left, bottom-top);
    }

    // return a new Rect equal to the overlap (intersection) with r
    public Rect overlap(Rect r) {
        // compute x- and y- boundaries of intersection
            int xl = Math.max(left,   r.left);
            int xr = Math.min(right,  r.right);
            int yt = Math.max(top,    r.top);
            int yb = Math.min(bottom, r.bottom);
        return new Rect(xl,xr,yt,yb); // return overlap 
    }
}

// a window with rectangles
public class World extends Frame {
    private Rect[] r; // rectangles
    // create 300-by-300 world with n randomly placed rectangles
    public World(int n) {
        setSize(300,300); show();
        // instantiate Rects
            rects = new Rect[n];
            for (int i = 0 ; i < n; i++) {
                // random width 0..49, random height 0..49
                    int width  = (int) (Math.random() * 50);
                    int height = (int) (Math.random() * 50);
                // random position of rectangle fitting inside 300-by-300 world
                    int left = (int) (Math.random() * (300-width));
                    int top  = (int) (Math.random() * (300-height));
                r[i] = new Rect (left, left+width, top, top+height);
                //                     ^^^^^^^^^^  ^^^
                // there was a typo: left+width and top were switched
            }
    }

    // draw rects in green, overlaps of 2 rects in red, overlaps of 3  in black
    public void paint(Graphics g) {
        // paint each r[i] in Color.green
            for (int i = 0 ; i < r.length ; i++)
                r[i].paint(g, Color.green);
        // paint overlaps of pairs (r[i], r[j]) in Color.red
            for (int i = 0 ; i < r.length ; i++)
                for (int j = i+1 ; j < r.length ; j++)
                    r[i].overlap(r[j]).paint(g, Color.red);
        // paint overlaps of triples (r[i], r[j], r[k]) in Color.black
            for (int i = 0 ; i < r.length ; i++)
                for (int j = i+1 ; j < r.length ; j++)
                    for (int k = j+1 ; k < r.length ; k++)
                        r[i].overlap(r[j]).overlap(r[k]) .paint(g, Color.black);
    }
}