Practice Final 5 Solutions

bool canGuard(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals,
              Vector<pirateT> rotation, int minsLeft)
{
    // Check whether the two most recent additions are rivals. This check could
    // be done before making the recursive call. (See sample solution 2 for an
    // example of that.)
    if (rotation.size() > 1)
    {
        string name1 = rotation[rotation.size() - 2].pirateName;
        string name2 = rotation[rotation.size() - 1].pirateName;

        if (!rivals[name1][name2])
        {
            return false;
        }
    }

    // We've successfully kept watch for the full 480 minutes.
    if (minsLeft <= 0)
    {
        for (pirateT p : rotation)
            cout << p.pirateName << endl;

        return true;
    }

    // This check is not strictly necessary. If crew vector is empty, the loop
    // below is skipped over and we return false at the end of the function
    // anyway.
    if (crew.size() == 0)
    {
        return false;
    }

    for (int i = 0; i < crew.size(); i++)
    {
        pirateT thisOne = crew.remove(i);
        rotation.add(thisOne);
        int thisTime = min(thisOne.timeOwed, 60);

        if (canGuard(crew, rivals, rotation, minsLeft - thisTime))
        {
            return true;
        }

        // We do need to add back to the crew vector in the correct position.
        // Otherwise, the vector we're iterating over is changing underneath
        // our feet.
        crew.insert(i, thisOne);
        rotation.remove(rotation.size() - 1);
    }

    return false;
}

bool canGuard(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals)
{
   Vector<pirateT> rotation;
   return canGuard(crew, rivals, rotation, 480);
}

bool canGuard(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals,
              int minsLeft, string previous)
{
   if (minsLeft <= 0)
   {
      return true;
   }

   // Not strictly necessary. Would skip loop and return false below.
   if (crew.size() == 0)
   {
      return false;
   }

   for (int i = 0; i < crew.size(); i++)
   {
      pirateT thisOne = crew.remove(i);
      int thisTime = min(thisOne.timeOwed, 60);

      if (previous == "" || rivals[previous][thisOne.pirateName])
      {
         if (canGuard(crew, rivals, minsLeft - thisTime, thisOne.pirateName))
         {
            return true;
         }
      }

      crew.insert(i, thisOne);
   }

   return false;
}

bool canGuard(Vector<pirateT> crew, Map<string, Map<string, bool>>& rivals)
{
   return canGuard(crew, rivals, 480, "");
}

Queue<int> _gobbleLengths;  // To store the lengths of gobbled strings.

CharGobbler::CharGobbler()
{
    _capacity = kInitialCapacity;
    _size = 0;
    _array = new char[kInitialCapacity];
}

CharGobbler::~CharGobbler()
{
    delete [] _array;
}

void CharGobbler::gobble(string s)
{
    // New length will be (_size + s.length()). Expand first if necessary.
    if (_size + s.length() > _capacity)
    {
        resize((_size + s.length()) * 2);
    }

    // Copy characters into array starting at position _size.
    for (int i = 0; i < s.length(); i++)
    {
        _array[_size + i] = s[i];
    }

    // Update _size and track length of newly added string.
    _size += s.length();
    _gobbleLengths.enqueue(s.length());
}

void CharGobbler::digest(int n)
{
    // We can't digest more strings that we already have. Note that we don't
    // need a separate variable to track number of strings; we can just use
    // the queue's size.
    //
    // If this causes n to become 0, this function will still work. The
    // remaining operations effectively become no-ops.
    if (n > _gobbleLengths.size())
    {
        n = _gobbleLengths.size();
    }

    int removeLength = 0;

    // Calculate total number of characters to be removed.
    for (int i = 0; i < n; i++)
    {
        removeLength += _gobbleLengths.dequeue();
    }

    // Shift remaining characters over in array.
    for (int i = removeLength; i < _size; i++)
    {
        _array[i - removeLength] = _array[i];
    }

    // Update array length.
    _size -= removeLength;

    // Shrink array if necessary. Not worried about <= vs. < here or the impact
    // of integer truncation.
    if (_size < 0.25 * _capacity)
    {
        resize(_capacity / 2);
    }
}

void CharGobbler::trim()
{
    resize(_size);
}

void CharGobbler::resize(int n)
{
    // We can never reduce the length of the array to something less than _size.
    if (n < _size)
    {
        error("Invalid resize parameter.");
    }

    char *newArray = new char[n];

    // We only have to copy up to (_size - 1), inclusive. We can leave
    // uninitialized garbage values in the array after that. It's okay to
    // initialized all other cells to some arbitrary placeholder value,
    // although that would be a waste of time.
    for (int i = 0; i < _size; i++)
    {
        newArray[i] = _array[i];
    }

    // Must delete old array before setting equal to new one.
    delete [] _array;
    _array = newArray;

    _capacity = n;
}

void seekAndDestroy(Node *head)
{
    HashSet<Node *> validNodes;
    HashSet<Node *> extraneousNodes;

    // Loop through to keep track of all valid nodes in the list.
    for (Node *current = head; current != nullptr; current = current->next)
    {
        validNodes.add(current);
    }

    // Now loop through to gather up all invalid nodes in the list. If we
    // delete an invalid node as we see it, we could inadvertently delete a
    // node multiple times. Instead, we gather them in a set (which removes
    // duplicates) and delete everything in the set after the fact.
    for (Node *current = head; current != nullptr; current = current->next)
    {
        if (!validNodes.contains(current->prev))
        {
            extraneousNodes.add(current->prev);
        }
    }

    // Now delete all the unique extraneous nodes. Note: It's safe to use
    // delete on a nullptr in C++ (the language is smart enough to know that
    // nullptr isn't a valid pointer, so using delete on nullptr doesn't do
    // anything and doesn't generate any errors). Hence, we don't have to
    // worry about any special checks here to deal with the possibility of
    // there being a nullptr in the extraneousNodes set. :)
    for (Node *trash : extraneousNodes)
    {
        delete trash;
    }
}

void fixPrevLinks(Node *head)
{
    Node *current = head;
    Node *previous = nullptr;

    while (current != nullptr)
    {
        current->prev = previous;

        previous = current;
        current = current->next;
    }
}

bool isLinkedList(Node *root)
{
    if (root == nullptr)
    {
        return true;
    }

    if (root->left != nullptr && root->right != nullptr)
    {
        return false;
    }

    // If we get here, these might both be nullptr (returns true), or one of
    // them might be nullptr (returns true), and the other is evaluated
    // (determines final return value). This avoids messy-looking condition
    // checks to determine which child is non-null if exactly one is non-null,
    // but that approach would be equally valid.
    return isLinkedList(root->left) && isLinkedList(root->right);
}

bool isLinkedList(Node *root)
{
    if (root == nullptr)
    {
        return true;
    }

    if (root->left != nullptr && root->right != nullptr)
    {
        return false;
    }

    // If we get here, we know the children aren't both empty. We either have
    // exactly one child or zero.

    if (root->left != nullptr)
    {
        return isLinkedList(root->left);
    }

    if (root->right != nullptr)
    {
        return isLinkedList(root->right);
    }

    // We can only get here if this node has zero children.
    return true;
}