ADTs!

Thursday, July 3

Section materials curated by JuliĂĄn RodrĂ­guez CĂĄrdenas, and Sean Szumlanski, drawing upon materials from previous quarters.

This week’s section exercises explore Grids, Maps, Sets, and Stacks! By the end of this week you'll be well-versed in all kinds of ADTs, which we'll learn about in class, and know the best use cases for each of them.

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter project

1. Grid Basics (grid.cpp)

Topic: Grids

a. Maximum of a Row in a Grid

Write a function named maxRow that takes a grid of non-negative integers (numbers from 0 to infinity) and an in-bounds grid location and returns the maximum value in the row of that grid location.

Solution 
// solution1 (manally loop through the row in the grid)
int maxRow(Grid<int>& grid, GridLocation loc) {
    int max = -1;
    for (int col = 0; col < grid.numCols(); col ++) {
        if (grid[loc.row][col] > max) {
            max = grid[loc.row][col];
        }
    }
    return max;
}

// solution2(use GridLocationRange)
int maxRow(Grid<int>& grid, GridLocation loc) {
    int max = -1;
    int endCol = grid.numCols() - 1;
    for (GridLocation cell : GridLocationRange(loc.row, 0, loc.row, endCol)) {
        if (grid[cell] > max) {
            max = grid[cell];
        }
    }
    return max;
}

b. Average value

Write a function named avgNeighborhood that takes a grid and a grid location and returns the average of all the values in the neighborhood of the grid location. A neighborhood is defined as all cells in a grid that border the grid location in all four directions(N, S, E, W). If the average is not an integer, return a truncated average.

Solution 
// solution1 (we put the 4 locations in a Vector and loop over them)
int avgNeighborhood(Grid<int>& grid, GridLocation loc) {
    Vector<GridLocation> possibleLocations = {
        {loc.row - 1, loc.col}, // north
        {loc.row + 1, loc.col}, // south
        {loc.row, loc.col + 1}, // east
        {loc.row, loc.col - 1}  // west
    };

    int sum = 0;
    int numValidLocations = 0;
    for (GridLocation dir : possibleLocations) {
        if (grid.inBounds(dir)) {
            sum += grid[dir];
            numValidLocations += 1;
        }
    }
    return sum / numValidLocations;
}

// solution2 (Don't do this please!! We manually get all 4 locations and sum them up)
int avgNeighborhood(Grid<int>& grid, GridLocation loc) {
    int sum = 0;
    int numValidLocations = 0;

    GridLocation north {loc.row - 1, loc.col};
    if (grid.inBounds(north)) {
        sum += grid[north];
        numValidLocations += 1;
    }

    GridLocation south {loc.row + 1, loc.col};
    if (grid.inBounds(south)) {
        sum += grid[south];
        numValidLocations += 1;
    }

    GridLocation east {loc.row, loc.col + 1};
    if (grid.inBounds(east)) {
        sum += grid[east];
        numValidLocations += 1;
    }

    GridLocation west {loc.row, loc.col - 1};
    if (grid.inBounds(west)) {
        sum += grid[west];
        numValidLocations += 1;
    }

    return sum / numValidLocations;
}

2. Friends (friendlist.cpp)

Topic: Maps, Sets

a. Building the friendList

Write a function named friendList that takes in a file name, reads friend relationships from the file, and writes them to a Map. friendList should return the populated Map. Friendships are bi-directional, so if Abby is friends with Barney, Barney is friends with Abby. The file contains one friend relationship per line, with names separated by a single space. You do not have to worry about malformed entries.

If an input file named buddies.txt looked like this:

Barney Abby
Abby Clyde

Then the call of friendList("buddies.txt") should return a resulting map that looks like this:

{"Abby":{"Barney", "Clyde"}, "Barney":{"Abby"}, "Clyde":{"Abby"}}

Here is the function prototype you should implement:

Map<string, Set<string> > friendList(String filename)

Solution 
Map<string, Set<string> > friendList(string filename) {
    ifstream in;
    Vector<string> lines;

    if (openFile(in, filename)) {
        lines = readLines(in);
    }

    Map<string, Set<string> > friends;
    for (string line: lines) {
        Vector<string> people = stringSplit(line, " ");
        string s1 = people[0];
        string s2 = people[1];
        friends[s1] += s2;
        friends[s2] += s1;
    }
    return friends;
}

b. Finding common friends

Write a function named mutualFriends that takes in the friendList above, and two strings representing two friends, and returns the names of the mutual friends they have in common. For example, if the friendList is {"Abby":{"Barney", "Clyde"}, "Barney":{"Abby"}, "Clyde":{"Abby"}} and friend1 is Barney and friend2 is Clyde, then your function should return {"Abby"}

Solution 
Set<string> mutualFriends(Map<string, Set<string> >& friendList, string friend1, string friend2) {
    return friendList[friend1] * friendList[friend2];
}

3. Twice (twice.cpp)

Topic: Sets

Write a function named twice that takes a vector of integers and returns a set containing all the numbers in the vector that appear exactly twice.

Example: passing {1, 3, 1, 4, 3, 7, -2, 0, 7, -2, -2, 1} returns {3, 7}.

Bonus: do the same thing, but you are not allowed to declare any kind of data structure other than sets.

Solution 
// solution
Set<int> twice(Vector<int>& v) {
    Map<int, int> counts;
    for (int i : v) {
        counts[i]++;
    }
    Set<int> twice;
    for (int i : counts) {
        if (counts[i] == 2) {
            twice += i;
        }
    }
    return twice;
}

// bonus
Set<int> twice(Vector<int>& v) {
    Set<int> once;
    Set<int> twice;
    Set<int> more;
    for (int i : v) {
        if (once.contains(i)) {
            once.remove(i);
            twice.add(i);
        } else if (twice.contains(i)) {
            twice.remove(i);
            more.add(i);
        } else if (!more.contains(i)) {
            once.add(i);
        }
    }
    return twice;
}

4. Check Balance (balance.cpp)

Topic: Stacks

Write a function named checkBalance that accepts a string of source code and uses a Stack to check whether the braces/parentheses are balanced. Every ( or { must be closed by a } or ) in the opposite order. Return the index at which an imbalance occurs, or -1 if the string is balanced. If any ( or { are never closed, return the string's length.

Here are some example calls:

//   index    0123456789012345678901234567
checkBalance("if (a(4) > 9) { foo(a(2)); }") 
// returns -1 (balanced)

//   index    01234567890123456789012345678901
checkBalance("for (i=0;i<a;(3};i++) { foo{); )")
// returns 15 because } is out of order

//   index    0123456789012345678901234
checkBalance("while (true) foo(); }{ ()")
// returns 20 because } doesn't match any {

//   index    01234567
checkBalance("if (x) {")
// returns 8 because { is never closed
Solution 
int checkBalance(string code) {
    Stack<char> parens;
    for (int i = 0; i < code.length(); i++) {
        char c = code[i];
        if (c == '(' || c == '{') {
            parens.push(c);
        } else if (c == ')' || c == '}') {
            if (parens.isEmpty()) {
                return i;
            }
            char top = parens.pop();
            if ((top == '(' && c != ')') || (top == '{' && c != '}')) {
                return i;
            }
        }
    }

    if (parens.isEmpty()) {
        return -1; // balanced
    } 
    return code.length();
}

5. Debugging Deduplicating (deduplicate.cpp)

Topics: Vector, strings, debugging

Consider the following incorrect C++ function, which accepts as input a Vector<string> and tries to modify it by removing adjacent duplicate elements:

⚠️ WARNING! The following function is buggy. 🐜

void deduplicate(Vector<string> vec) {
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == vec[i + 1]) { 
            vec.remove(i);
        }
    }
}

The intent behind this function is that we could do something like this:

Vector<string> hiddenFigures = {
    "Katherine Johnson",
    "Katherine Johnson",
    "Katherine Johnson",
    "Mary Jackson",
    "Dorothy Vaughan",
    "Dorothy Vaughan"
};

deduplicate(hiddenFigures);
// hiddenFigures = ["Katherine Johnson", "Mary Jackson", "Dorothy Vaughan”]

The problem is that the above implementation of deduplicate does not work correctly. In particular, it contains three bugs. First, find these bugs by writing test cases that pinpoint potentially erroneous situations in which the provided code might fail, then explain what the problems are, and finally fix those errors in code.

Solution

There are three errors here:

  1. Calling .remove() on the Vector while iterating over it doesn’t work particularly nicely. Specifically, if you remove the element at index i and then increment i in the for loop, you’ll skip over the element that shifted into the position you were previously in.
  2. There’s an off-by-one error here: when i = vec.size() - 1, the indexing vec[i + 1] reads off the end of the Vector.
  3. The Vector is passed in by value, not by reference, so none of the changes made to it will persist to the caller.

Here are corrected versions of the code:

// solution 1
void deduplicate(Vector<string>& vec) {
    for (int i = 0; i < vec.size() - 1; ) {
        if (vec[i] == vec[i + 1]) {
            vec.remove(i);
        } else {
            i++;
        }
    }
}

// solution 2
void deduplicate(Vector<string>& vec) {
    for (int i = vec.size() - 1; i > 0; i--) {
        if (vec[i] == vec[i - 1]) {
            vec.remove(i);
        }
    }
}