More Practice Problems (Post-Midterm)

void printSumsOf(int n) {
    /* Handle edge cases. */
    if (n < 0) error("Can't make less than nothing from more than nothing.");
    printSumsRec(n, {});
}

/* Print all ways to sum up to n, given that we've already broken off the numbers
 * given in soFar.
 */
void printSumsRec(int n, Vector<int> soFar) {
    /* Base case: Once n is zero, we need no more numbers. */
    if (n == 0) {
        printAsSum(soFar);
    } else {
        /* The next number can be anything between 1 and n, inclusive. */
        for (int i = 1; i <= n; i++) {
            printSumsRec(n - i, soFar + i);
        }
    }
}

/* Prints a Vector<int> nicely as a sum. */
void printAsSum(Vector<int>& sum) {
    /* The empty sum prints as zero. */
    if (sum.isEmpty()) {
        cout << 0 << endl;
    } else {
        /* Print out each term, with plus signs interspersed. */
        for (int i = 0; i < sum.size(); i++) {
            cout << sum[i];
            if (i + 1 != sum.size()) cout << " + ";
        }
        cout << endl;
    }
}

void listKOrderings(Set<string> choices, int k) {
    /* Quick edge case check: if we want more items than there are options, there
    * are no orderings we can use.
    */
    if (k < choices.size()) {
        listOrderingHelper(choices, k, {});
    }
}
void listOrderingHelper(Set<string> choices, int k, Vector<string> soFar) {
    /* Base case: If no more terms are needed, print what we have. */
    if (k == 0) {
        cout << soFar << endl;
    }
    /* Recursive case: What comes next? Try all options. */
    else {
        for (string choice: choices) {
            listOrderingHelper(choices - choice, k - 1, soFar + choice);
        }
    }
}

void printMultCompoundWords(Lexicon& dict) {
    for (string word : dict) {
        if (isMultCompoundWord(word, dict)) {
            cout << word << endl;
        }
    }
}

bool isMultCompoundWord(string word, Lexicon& dict) {
    /* In an unusual twist, our base case is folded into the recursive step. We
    * will try all possible splits into two pieces, and if one of them happens
    * to be a pair of words, we stop.
    */
 
    /* Try all ways of splitting things. */
    for (int i = 1; i < word.length(); i++) {
        /* Only split if the first part is a word. */
        if (dict.contains(word.substr(0, i))) {
            string remaining = word.substr(i);
            /* We're done if the remainder is either a word or a compound word. */
            if (dict.contains(remaining) || isMultCompoundWord(remaining, dict)) {
                return true;
            }
        }
    }
    /* Nothing works; give up. */
    return false;
}

string longestCommonSubsequence(string s1, string s2) {
	if (s1.length() == 0 || s2.length() == 0) {
		return "";
 	} else if (s1[0] == s2[0]) {
 		return s1[0] + longestCommonSubsequence(s1.substr(1), 
 							s2.substr(1));
 	} else {
 		string choice1 = longestCommonSubsequence(s1, s2.substr(1));
		string choice2 = longestCommonSubsequence(s1.substr(1), s2);
		if (choice1.length() >= choice2.length()) {
			return choice1;
		} else {
			return choice2;
		}
	}
}

string crackHelper(string soFar, int maxLength) {
	if (login(soFar)) {
		return soFar;
	}
	if (soFar.size() == maxLength) {
		return "";
	}
	for (char c = 'a'; c <= 'z'; c++) {
		string password = crackHelper (soFar + c, maxLength);
		if (password != "") {
			return password;
		}
 		// Also check uppercase
 		char upperC = toupper(c);
 		password = crackHelper (soFar + upperC, maxLength);
		if (password != "") {
 			return password;
 		}
 	}
	return "";
}

string crack(int maxLength) {
	if (maxLength < 0) {
 		error("max length cannot be negative!);";
	}
 	return crackHelper("", maxLength);
}

/* Returns the reciprocal of this fraction. If the fraction is zero, this
 * operation is not defined, and the function calls error().
 */
Fraction reciprocal();

Fraction Fraction::reciprocal() {
    if (numerator() == 0) {
        error("I can't divide by zero. (Maybe you can, though?)");
    }

    return Fraction(denominator(), numerator());
}

/* Divides this fraction by the fraction given in the parameter. If that
 * fraction is zero, calls error().
 */
void divide(Fraction rhs);

void Fraction::divide(Fraction rhs) {
    multiply(rhs.reciprocal());
}

class BigNum {
public:
    BigNum(int value = 0); // Default to zero unless specified otherwise.
    ~BigNum();

    std::string toString() const; // Get a string representation
    void add(const BigNum& value);
private:
    int* digits; // Stored in reverse order
    int allocatedSize; // In # of digits
    int numDigits; // In # of digits.
    void reserve(int space); // Ensure we have space to hold numDigits digits
    int numDigitsOf(int value) const; // How many digits are in value?
};

BigNum::BigNum(int value) {
    /* Set up an initial array of elements. */
    digits = new int[kDefaultSize]; // Some reasonable default
    allocatedSize = kDefaultSize;

    /* Count how many digits are in our number. 0 is an edge case, so we'll make
    * this work by reducing the number of digits down to the last one.
    */
    numDigits = numDigitsOf(value);

    if(numDigits >= allocatedSize) error("Input too big!");

    /* Copy the number into the array, one digit at a time. */
    for (int i = 0; i < numDigits; i++) {
        digits[i] = value % 10;
        value /= 10;
    }
}

int BigNum::numDigitsOf(int value) const {
    /* Pro C++ tip: Since this function doesn't read or write any member
    * variables, this should either be a free function or a static member
    * function. We didn't discuss those sorts of concerns in CS106B, though.
    */
    int result = 1; // All numbers have at least one digit.

    /* We've already counted one digit. Now count the rest. */
    while (value >= 10) {
        result++;
        value /= 10;
    }
    return result;
}

BigNum::~BigNum() {
    delete[] digits;
}

string BigNum::toString() const {
    /* Because characters are stored in reverse order, we have to scan them
    * backwards to make our number.
    */
    string result;
    for (int i = numDigits - 1; i >= 0; i--) {
        result += to_string(digits[i]);
    }
    return result;
}

void BigNum::add(const BigNum& value) {
    /* First, ensure we have space to hold the result. Adding two numbers produces
    * a result whose size is at most one digit bigger than either input number.
    */
    int digitsToVisit = max(numDigits, value.numDigits);
    reserve(1 + digitsToVisit);

    /* Use the grade school algorithm to add the numbers. */
    int carry = 0;
    for (int i = 0; i < digitsToVisit; i++) {

        int sum;
        if (i < numDigits && i < value.numDigits) sum = digits[i] + value.digits[i] + carry;
        else if (i < numDigits) sum = digits[i] + carry;
        else sum = value.digits[i] + carry;

        /* Write the one's place. */
        digits[i] = sum % 10;
        /* Store the carry. */
        carry = sum / 10;
    }

    /* We need at least as many digits as before, plus one if there is a final
    * carry.
    */
    numDigits = digitsToVisit;
    if (carry != 0) {
        numDigits ++;
    }
    if (carry == 1) digits[digitsToVisit] = 1;
}

/* Reserving space uses the regular "double in size" trick. */
void BigNum::reserve(int space) {
    /* If we have the space, then we don't need to do anything. */
    if (space <= allocatedSize) return;

    /* Double and copy. We deliberately don't just grow to the size requested,
    * since that may not be efficient.
    */
    allocatedSize *= 2;
    int* newDigits = new int[allocatedSize];
    for (int i = 0; i < numDigits; i++) {
        newDigits[i] = digits[i];
    }
    delete[] digits;
    digits = newDigits;
}

#pragma once

class RingBufferQueue {
public:
	// Same as before!
private:
	// Same as before! Except with the following new variable:
    // NEW
    void grow();        // Resize if we need more space  
};

// Same as before! Except with the following new method:

// NEW
void RingBufferQueue::grow() {
    /* Get twice as much space as we used to have. */
    int* newElems = new int[allocatedSize * 2];
    
    /* Copy the elements over. Start at the position given by the head, and
     * use modular arithmetic to walk forward, wrapping around if necessary.
     */
    for (int i = 0; i < size(); i++) {
        newElems[i] = elems[(head + i) % allocatedSize];
    }
    
    /* Replace the old array. */
    delete[] elems;
    elems = newElems;
    
    /* Our copy operation pushed everything to the front of the ring buffer
     * array. Update the head to look there as well.
     */
    head = 0;
    
    /* Remember that we just increased our size. */
    allocatedSize *= 2;
}

RingBufferQueue.h

#pragma once

#include <iostream>
using namespace std;
class RingBufferQueue {
public:
    RingBufferQueue();
    ~RingBufferQueue();
    bool isEmpty() const;
    bool isFull() const;
    int size() const;
    void enqueue(int elem);
    int dequeue();
    int peek() const;
private:
    int* _elements;
    int _capacity;
    int _size;
    int _head;
    friend ostream& operator <<(ostream& out, const RingBufferQueue& queue);
    void enlarge();
};

RingBufferQueue.cpp

#include "RingBufferQueue.h"

static int kDefaultCapacity = 5;
RingBufferQueue::RingBufferQueue() {
    _capacity = kDefaultCapacity;
    _elements = new int[_capacity];
    _head = 0;
    _size = 0;
}
RingBufferQueue::~RingBufferQueue() {
    delete[] _elements;
}
void RingBufferQueue::enqueue(int elem) {
    if (isFull()) {
        enlarge();
    }
    int tail = (_head + _size) % _capacity;
    _elements[tail] = elem;
    _size++;
}
int RingBufferQueue::dequeue() {
    int front = peek();
    _head = (_head + 1) % _capacity;
    _size--;
    return front;
}
int RingBufferQueue::peek() const {
    if (isEmpty()) {
        error("Can't peek at an empty queue!");
    }
    return _elements[_head];
}
bool RingBufferQueue::isEmpty() const {
    return _size == 0;
}
bool RingBufferQueue::isFull() const {
    return _size == _capacity;
}
int RingBufferQueue::size() const {
    return _size;
}
void RingBufferQueue::enlarge() {
    int *larger = new int[_capacity * 2];
    for (int i = 0; i < _size; i++) {
        larger[i] = _elements[(_head + i) % _capacity];
    }
    delete[] _elements;
    _elements = larger;
    _capacity *= 2;
    _head = 0;
}
ostream& operator <<(ostream& out, const RingBufferQueue& queue) {
    out << "{";
    if (!queue.isEmpty()) {
        // We can access the inner ‘_elements’ member variables because
        // this operator is declared as a friend of the RingBufferQueue class
        out << queue._elements[queue._head];
        for (int i = 1; i < queue.size(); i++) {
            int index = (queue._head + i) % queue._capacity;
            out << ", " << queue._elements[index];
        }
    }
    out << "}";
    return out;
}