All IG Problems

Here is a list of all the IG problems we’ve worked on in IGs throughout the quarter! We hope this is helpful in studying for the final.

IG1: sumDigits()

Topics: strings, transition to C++
📦 Starter code

Implement the int sumDigits(string s) function from the code below:

/* The sumDigits function returns the sum of all the digits in s.
   The function ignores negative numbers and only sums the individual
   digits. For example, `sumDigits("ab1c3d56--21x")` should return `18` (which is `1 + 3 + 5 + 6 + 2 + 1`).
   An empty string should return `0`. 
   You are welcome to use functions from the `cctype` and `strlib.h` libraries.
*/
int sumDigits(string s) {
    // code here!
 
     
}

int main() {
    string s = getLine("Enter a string with numbers and characters and punctuation, etc.: ");
    int sum = sumDigits(s);
    cout << "The sum of the digits in the string: " << sum << endl;
    return 0;
}

Solution:

int sumDigitsSolution(string s) {
    int sum = 0;
    for (int ch : s) {
        if (isdigit(ch)) {
            int digit = charToInteger(ch);
            sum += digit;
        }
    }
    return sum;
}

IG2: tokenLengthMatcher()

Topics: Sets, Maps
📦 Starter code
For this week, we’d like you two to work on the following function that takes inspiration from the Search Engine portion of A2. Specifically, we’ll have you implement: Set<string> tokenLengthMatcher(Map<string, Set<string>>& index, int length); which will take in an inverted index index and an integer length and require you to return a Set<string> that is the union of all URLs corresponding to all tokens in index that are of length length.

/* The tokenLengthMatcher function returns a Set of all URLs from index that correspond to a token that is of
    length length.
    You can assume that the inverted index is properly formed.
*/
Set<string> tokenLengthMatcher(Map<string, Set<string>>& index, int length) {
    // code here!
    
    
    
    
    
}

Solution:

Set<string> tokenLengthMatcher(Map<string, Set<string>>& index, int length) {
    // takes in an inverted index index and an
    // integer length and returns a
    // Set<string> that is the union of all URLs corresponding
    // to all tokens in index that are of length length.
    Set<string> lengthSet;
    for (string key : index) {
        if (key.length() == length) {
            lengthSet += index[key];
        }
    }
    return lengthSet;
}

IG3: printRange()

Topics: recursion
📦 Starter code

For this week, we’d like you to work on the following recursive function, printRange(int x, int y). It was a midterm problem from a number of years ago, and it has been reformulated slightly so it will hopefully fit into a ten- or fifteen-minute session:

Write a recursive function named printRange(int x, int y) that accepts integer parameters x and y and prints the sequential integers between x and y inclusive (x will always be less than or equal to y). The first half should be printed with the greater-than character ('>') separating consecutive values. The second half should be printed with the less-than character ('<') separating consecutive values. When there are two values in the middle of the range, those two values should be separated by a pair of dashes ("--"). The following table shows several calls and their expected outputs:

Call                    Output
printRange(1, 9);       1 > 2 > 3 > 4 > 5 < 6 < 7 < 8 < 9
printRange(1, 10);      1 > 2 > 3 > 4 > 5 -- 6 < 7 < 8 < 9 < 10
printRange(23, 29);     23 > 24 > 25 > 26 < 27 < 28 < 29
printRange(13, 14);     13 -- 14
printRange(-8, -8);     -8

• Notice that in the first output, 5 is in the middle with the numbers before it separated by greater-than and the numbers after it separated by less-than.
• In the second output, there is no “middle” number, so there is a double-dash between the 5 and the 6
• In the third output, 26 is in the middle with numbers before it separated by greater-than and numbers after it separated by less-than.
• In the fourth output, there is no “middle” number.
• The last output has no separators because that range includes one number.
• Hints:
  • Start by considering the following base cases:
    1. what if the integers are the same?
    2. what if the integers are only one apart?
  • Your recursive case should be, exactly, printRange(x + 1, y - 1). This may seem unintuitive at first, but this means that you will need to print twice in your recursive code block. Figure out where those two cout calls should be, and you will solve the problem.

void printRange(int x, int y) {
    // TODO: your solution here!

}

Solution:

void printRangeSolution(int x, int y) {
    if (x == y) {
        cout << x;
    } else if (x == y - 1) {
        cout << x << " -- " << y;
    } else {
        cout << x << " > ";
        printRange(x + 1, y - 1);
        cout << " < " << y;
    }
}

IG4: Midterm Review

Topics: Midterm review, data structures, recursive backtracking
📦 Starter code

This week, we gave you the option to review whichever problem you found trickier on the midterm.

Midterm Problem 3

You will simulate reading a stream of lowercase letters one character at a time (left to right). After processing each new character, output the first character that has appeared exactly once so far. If no such character exists (i.e., every character seen so far has repeated), output an underscore _.

As you scan the input string from its first character to its last, you build an output string of the same length. At position i of the output, you must place the current first non-repeating character among the prefix s[0..i]. If there is no non-repeating character at that moment, place “_”.

You must use exactly two of these data structures in your implementation: Stack, Queue, Set, Map. You may not use a Vector.

string firstNonRepeatingStream(const string s);

The following is a sample function that calls your function, and the output:

void p3() {
    Vector<string> inputStrings = {"aabcbcdbe", "abcdeaf", "", "aabbccdd", "abbbac"};
    for (string s : inputStrings) {
        string outputString = firstNonRepeatingStream(s);
        cout << "Input string: " << s <<  ", Output string: " << outputString << endl;
    }
}

Expected output from the code above:

Input string: aabcbcdbe, Output string: a_bbc_ddd
Input string: abcdeaf, Output string: aaaaabb
Input string: , Output string:
Input string: aabbccdd, Output string: a_b_c_d_
Input string: abbbac, Output string: aaaa_c

Walkthrough example (first few steps for "aabcbcdbe"):

• Start: seen = {}, first non-repeating = none

1. read a -> counts: a=1; first non-repeating: a -> output so far: "a"
2. read a -> counts: a=2; no non-repeating yet -> output so far: "a_"
3. read b -> counts: a=2, b=1; first non-repeating: b -> output so far: "a_b"
4. read c -> counts: a=2, b=1, c=1; first is still b -> output so far: "a_bb"
5. read b -> counts: a=2, b=2, c=1; first becomes c -> output so far: "a_bbc"
6. read c -> counts: a=2, b=2, c=2; none -> '_' -> output so far: "a_bbc_"
7. read d -> counts: a=2, b=2, c=2, d=1; first=d -> output so far: "a_bbc_d"
8. read b -> counts: a=2, b=3, c=2, d=1; first=d -> output so far: "a_bbc_dd"
9. read e -> counts: a=2, b=3, c=2, d=1, e=1; first=d -> output so far: "a_bbc_ddd"

Your code here:

string firstNonRepeatingStream(const string s) {
    Map<char,int> freq;
    Queue<char> q;
    string result;
   






 




    
    return result;

Midterm Problem 6

For this problem, rewrite your maze Depth First Search (DFS) solution from assignment 2 to use a recursive helper function:

/*
 * populates path with the solution to maze. 
 * path will start with a single GridLocation of {0, 0}. 
 * visited will have {0, 0} in the set already
*/

void solveMazeDFSRecursiveHelper(Grid<bool>& maze, 
                                 Vector<GridLocation> &path, 
                                 Set<GridLocation> &visited);

Recall from assignment 2 that you wrote the following function, which you should use in your solution:

Set<GridLocation> generateValidMoves(Grid<bool>& g, GridLocation cur);

Your recursive helper function will be called by the following function:

Vector<GridLocation> solveMazeDFSRecursive(Grid<bool>& maze) {
    GridLocation start = {0, 0};
    Set<GridLocation> visited;
    Vector<GridLocation> solution;
    solution.add(start);
    visited.add(start);
    solveMazeDFSRecursiveHelper(maze, solution, visited);
    return solution;
}

Notes:

• As with assignment 2, you can assume that a maze has one and only one solution.
• Recall that the generateValidMoves function has already determined that a location is valid, so you do not need to concern yourself with any true or false values in the maze grid.
• We have defined the pathEnd and mazeExit GridLocations for you in the function.

Your code here:

/*
 * populates path with the solution to maze. 
 * path will start with a single GridLocation of {0, 0}. 
 * visited will have {0, 0} in the set already
*/

void solveMazeDFSRecursiveHelper(Grid<bool>& maze, 
                                 Vector<GridLocation> &path, 
                                 Set<GridLocation> &visited) {
    GridLocation pathEnd = path[path.size() - 1];
    GridLocation mazeExit = {maze.numRows() - 1, maze.numCols() - 1};

    // your code here:

Solutions can be found in the 106B midterm exam solutions.

IG5: TangoPuzzle

Topics: Classes, dynamic memory, open-ended brainstorming

We’re coming out of the class design assignment, so we’re going to have a slightly higher level IG problem — rather than writing any code, you will be given a problem and we’ll have you brainstorm how you might implement this class from scratch!

We’ll call the class to implement the TangoPuzzle class. It is supposed to model the LinkedIn puzzle that Yasmine and some 106B SLs are big fans of. You’re more than welcome to play it here if you’d like!

This is a photo of what the Tango puzzle looks like before the user has interacted with it at all:

And this is what it looks like once successfully completed:

To summarize:

• Pretend you are working for LinkedIn – it is your job to pretend to be the developer and think about how you would implement the Tango game!
• We have a 6x6 grid.
• Each cell in the grid can contain a Sun (), Moon (), or Nothing.
• Some cells in the grid start off with Sun/Moon items already placed as hints.
• Each row needs to end with exactly 3 suns and 3 moons; each column needs to end with exactly 3 suns and 3 moons.
• We can never have more than adjacent 2 tiles with the same symbol in it — e.g., at most 2 suns, or at most 2 moons back to back.
• Some edges between cells have an xor an = sign:
  • If there is an = sign, the cells must be the same (Sun/Sun or Moon/Moon).
  • If there is an x sign, the cells must be opposites (Sun/Moon or Moon/Sun).

Feel free to work through the initial stages of desiging this problem any way you’d like – if this means doing it in a more pseudocode style, that’s great – feel free to take notes however. If you prefer doing things closer to actual C++ code, feel free to structure out a private/public part of the class in a Qt cpp file and do it that way. The world is your oyster! We just want you to get experience designing a class themselves, since this isn’t something you get much practice with in 106B. Appreciate the fact that you now have the skills to build practically anything you’d like through the power of class design!

Here are some things to think about if you’re stuck:

• How might we want to represent the underlying grid structure of the puzzle?
  • This gets into the idea of needing to represent a 2D grid structure in a 1D array in memory — some diagrams here might help you!
• How do we want to represent the items that are placed in each slot in the grid?
  • So many options here – Yasmine’s gut instinct is to use an enum here e.g.

   enum class Item {
      SUN, 
      MOON, 
      NOTHING
  };
  

  which you saw in A6! But perhaps you might choose to represent each item with an integer, e.g. 0 = sun, 1 = moon, and 2 = nothing. That’s fine too! Just good to brainstorm different possibilities.
• What private methods might be helpful here? Maybe we want something to be able to check if a puzzle is completed, if a row is valid, if a column is valid, if the puzzle state is valid overall, etc. many options here.

We didn’t provide solutions for this problem, since the exercise was more in brainstorming. Feel free to swing by Yasmine or Chris’s OH to discuss this further if you’re interested!

IG6: hasCycle()

Topics: Linked lists, Set, big-O runtime
📦 Starter code

This week’s IG problem will have you detect whether or not a linked list has a cycle! I thought this one might be fun because the elegant solution is one that is a bit obscure (and we wouldn’t expect you to generate this method on your own).

You will implement the following function signature:

bool hasCycle(Node* front);

You can assume that the following Node struct has been defined (regular node for a singly-linked list that you are used to).

struct Node {
    int data;
    Node *next;
};

Given a pointer front to the start of a linked list, return true if the list contains a cycle, and false otherwise. For example, when calling hasCycle() on the following list, we’d expect the function to return false:

But if we called it on this next list, the function should return true.

Here’s another example of a linked list containing a different cycle; a call to hasCycle() on this list should also return true.

Solutions:
Option 1: Using a Set to keep track of seen Nodes This first solution is the one that I would expect is more likely for you to be able to come up with. It involves keeping track of a Set of seen nodes – if we ever encounter a node that is already contained within the set, we can assume there was a cycle present:

bool hasCycle(Node* front){
    Set<Node*> visited;

    Node* cur = front;
    while (cur != nullptr) {
        if (visited.contains(cur)) {
            return true;  // we've seen this exact node before --> must contain a cycle, early return true
        }
        visited.add(cur);
        cur = cur->next;
    }

    return false; // reached the end, so no cycle :)
}

Option 2: Floyd’s Tortoise & Hare algorithm (slow and fast pointer) This one is fun! It involves keeping track of a slow pointer, which we advance by 1 spot each iteration, and a fast pointer, which gets advanced by 2 spots in the list each iteration. It uses the clever idea that if a cycle exists, these two pointers will eventually meet up and point to the same node. I wouldn’t expect you to come up with this on their own, but it’s a fun thing to be aware of!

bool hasCycle(Node *front) {
    if (front == nullptr || front->next == nullptr) {
        return false; // a cycle is not possible here
    }
    
    Node* slow = front;
    Node* fast = front;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next; // advance 1 spot in the list -- tortoise!
        fast = fast->next->next; // advance 2 spots in the list -- hare!
        
        /* if our tortoise and hare ever meet up, a cycle exists. */
        if (slow == fast) {
            return true;
        }
    }
    
    return false; // this will happen if fast reaches the end of the linked list, indicating no cycle!
}