Practice Final 4 Solutions

void melt(Lexicon& lex, string& a, string& b, string soFar, Set<string>& set)
{
    if (lex.contains(soFar))
    {
        set.add(soFar);
    }

    if (!lex.containsPrefix(soFar))
    {
        return;
    }

    if (!a.empty())
    {
        char thisOne = a[0];
        a = a.substr(1);

        melt(lex, a, b, soFar, set);
        melt(lex, a, b, soFar + thisOne, set);

        // Failure to add this back results in sadness.
        a = thisOne + a;
    }

    if (!b.empty())
    {
        char thisOne = b[0];
        b = b.substr(1);

        melt(lex, a, b, soFar, set);
        melt(lex, a, b, soFar + thisOne, set);

        // Failure to add this back results in sadness.
        b = thisOne + b;
    }
}

Set<string> melt(string a, string b)
{
    Lexicon lex("EnglishWords.txt");
    Set<string> set;
    melt(lex, a, b, "", set);
    return set;
}

Graph::Graph(Grid<bool> matrix) {
    _matrix = matrix;
    _numNodes = matrix.numCols();
    _numEdges = 0;

    // Notice that the inner loop does not start
    // with j = 0. See note about this below.
    for (int i = 0; i < _numNodes; i++) {
        for (int j = i; j < _numNodes; j++) {
            if (_matrix[i][j]) {
                _numEdges++;
            }
        }
    }

    // Note: Because of self-loops, counting up ALL
    // edges in the graph and then dividing by two
    // does not work!
}

Graph::~Graph() {
}

void Graph::checkValid(int n1) const {
    if (n1 < 0 || n1 >= _numNodes) {
        error("Invalid index!");
    }
}

void Graph::addEdge(int n1, int n2) {
    checkValid(n1);
    checkValid(n2);
    if (!_matrix[n1][n2]) {
        _matrix[n1][n2] = _matrix[n2][n1] = true;
        _numEdges++;
    }
}

void Graph::removeEdge(int n1, int n2) {
    checkValid(n1);
    checkValid(n2);
    if (_matrix[n1][n2]) {
        _matrix[n1][n2] = _matrix[n2][n1] = false;
        _numEdges--;
    }
}

bool Graph::edge(int n1, int n2) const {
    checkValid(n1);
    checkValid(n2);
    return _matrix[n1][n2];
}

Set<int> Graph::neighbors(int n1) const {
    checkValid(n1);
    Set<int> set;
    for (int i = 0; i < _numNodes; i++) {
        if (_matrix[n1][i]) {
            set.add(i);
        }
    }
    return set;
}

int Graph::nodeCount() const {
    return _numNodes;
}

int Graph::edgeCount() const {
    return _numEdges;
}

bool ping(Node*& head, int value)
{
    // Find value;
    Node *current = head;
    while (current != nullptr && current->data != value)
    {
        current = current->next;
    }

    // Not found.
    if (current == nullptr) {
        return false;
    }

    // Found! Increment.
    current->pCnt++;

    // First of all, if nothing to do, just leave function.
    if (current->prev == nullptr || current->prev->pCnt >= current->pCnt) {
        return true;
    }

    // Otherwise, work backward to find where target node should be injected.
    Node *insertBefore = current->prev;
    while (insertBefore->prev != nullptr && insertBefore->prev->pCnt < current->pCnt)
    {
        insertBefore = insertBefore->prev;
    }

    // Remove node from list. We know current->prev is not null, so this is safe.
    current->prev->next = current->next;
    // However, its next pointer could be null, so be careful here.
    if (current->next != nullptr) {
        current->next->prev = current->prev;
    }

    // Now wire node into new position.
    current->next = insertBefore;
    current->prev = insertBefore->prev;

    insertBefore->prev = current;
    // Guard against segfault in event that the target node has become head.
    if (current->prev != nullptr) {
        current->prev->next = current;
    }

    // If the target node has nothing before it, it's the new head of the list!
    if (current->prev == nullptr) {
        head = current;
    }

    return true;
}

int threshSum(TreeNode* root, int threshold) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        if (root->data >= threshold) {
            return root->data;
        }
        return 0;
    }

    // If root->data < threshold, then everything in its left subtree is
    // < threshold as well, since this is a BST -- so it would be wasteful to
    // go into the leftsubtree in that case.
    if (root->data < threshold) {
        return threshSum(root->right, threshold);
    } else {
        return threshSum(root->left, threshold) + threshSum(root->right, threshold);
    }
}

bool findExit(Cell *current, Cell*& goal, HashSet<Cell*>& set)
{
    if (current == nullptr)
    {
        return false;
    }

    if (set.contains(current)) {
        return false;
    }
    set.add(current);

    if (current->content == "exit")
    {
        goal = current;
        return true;
    }
    else if (findExit(current->up, goal, set))
    {
        return true;
    }
    else if (findExit(current->down, goal, set))
    {
        return true;
    }
    else if (findExit(current->left, goal, set))
    {
        return true;
    }
    else if (findExit(current->right, goal, set))
    {
        return true;
    }
    else
    {
        return false;
    }
}

Cell* findExit(Cell *start)
{
    Cell *goal = nullptr;
    HashSet<Cell*> set;
    findExit(start, goal, set);
    return goal;
}