3
\$\begingroup\$

This problem is from MIT Course and I have implemented it in C++. Review this code and how can I improve it complexity-wise and with better features available in C++.

Let’s say we have a whole bunch of people in line waiting to see a baseball game. They are all hometown fans and each person has a team cap and is wearing it. However, not all of them are wearing the caps in the same way – some are wearing their caps in the normal way, and some are wearing them backwards.

People have different definitions of normal and backwards but you, the gatekeeper thinks that the cap on the left below is being normally worn and the one on the right is being worn backwards.

You are the gatekeeper and can only let them in to the stadium if the entire group has their caps on in the same way – either all forwards or all backwards. Because everyone has different definitions of forward and backward, you can’t tell them to wear their cap forwards or backwards. You can only tell them to flip their caps. The good news is that each person knows what position they are in the line, starting with the first person having position 0 and the last one position n – 1.

You can say things like:

Person in position i please flip your cap.
People in positions i through j (inclusive) please flip your caps.

What you would like to do is to minimize the number of requests you have to shout out to save your voice.

#include <iostream>
#include <vector>
#include <tuple>

std::vector< std::tuple<std::size_t, std::size_t, char> > please_conform(std::vector<char>& caps,
                                                    int forward_count, int backward_count)
{
    std::vector< std::tuple<std::size_t, std::size_t, char> > positions;
    std::size_t start = 0, end;

    for (std::size_t i = 0; i < caps.size()-1; ++i)
    {
        if (i+1 == caps.size()-1)
        {
            if (caps[i] != caps[i+1])
            {
                end = i;
                positions.push_back(std::make_tuple(start, end, caps[end]));
                if (caps[end] == 'F')
                {
                    forward_count++;
                }
                else
                {
                    backward_count++;
                }
                start = i+1;
                end = i+1;
                positions.push_back(std::make_tuple(start, end, caps[end]));
                if (caps[end] == 'F')
                {
                    forward_count++;
                }
                else
                {
                    backward_count++;
                }
            }
            else
            {
                end = i+1;
                positions.push_back(std::make_tuple(start, end, caps[end]));
                if (caps[end] == 'F')
                {
                    forward_count++;
                }
                else
                {
                    backward_count++;
                }
            }
        }
        else
        {
            if (caps[i] != caps[i+1])
            {
                end = i;
                positions.push_back(std::make_tuple(start, end, caps[end]));
                if (caps[end] == 'F')
                {
                    forward_count++;
                }
                else
                {
                    backward_count++;
                }
                start = i+1;
            }
        }
    }
    return positions;
}

void speak_commands(std::vector< std::tuple<std::size_t, std::size_t, char> >& positions,
                                                    int forward_count, int backward_count)
{
    char cap_to_flip;
    if (forward_count < backward_count)
    {
        cap_to_flip = 'F';
    }
    else
    {
        cap_to_flip = 'B';
    }

    for (std::size_t i = 0; i < positions.size(); ++i)
    {
        if (std::get<2>(positions[i]) == cap_to_flip &&
                  std::get<0>(positions[i]) == std::get<1>(positions[i]))
        {
            std::cout << "People in position " << std::get<0>(positions[i]) << " flip your cap!\n";
        }
        else if (std::get<2>(positions[i]) == cap_to_flip &&
                  std::get<0>(positions[i]) != std::get<1>(positions[i]))
        {
            std::cout << "People in positions " << std::get<0>(positions[i]) << " through " << std::get<1>(positions[i]) << " flip your caps!\n";
        }
    }
}

int main()
{
    std::vector<char> caps = {'F', 'F', 'B', 'B', 'B', 'F', 'B', 'B',
                                                  'B', 'F', 'F', 'B', 'F'};

    if (caps.empty())
    {
        std::cout << "Empty list!!!\n";
    }

    int forward_count = 0, backward_count = 0;
    std::vector< std::tuple<std::size_t, std::size_t, char> > res =
                      please_conform(caps, forward_count, backward_count);

    speak_commands(res, forward_count, backward_count);

}
\$\endgroup\$
4
\$\begingroup\$

The good:

  • Using std::size_t for indexing a std::vector.
  • Properly using std:: where necessary.

:)


The bad:

  • bug: forward_count and backward_count are passed by value into please_conform. They appear to be output parameters, so they must be passed by reference.

  • bug: Although we warn the user when encountering an empty list, we carry on running the program, which will cause serious problems in please_conform with the end condition of i < caps.size() - 1. We need to return from main, or move the empty check to the start of please_conform.

  • We should pass the caps vector into please_conform by const&, not &, since we don't intend to change it. Similarly the positions argument to speak_commands should be a const&.

  • A bool would be better than a char to represent cap direction, since it only has two possible values and is easy to flip. An even better choice would be an enum class, since that would also add type-safety (and we easily could supply a "flip" function).

  • int may not cover the appropriate range for the forward and backward counts. I'd suggest using std::size_t.


The ugly:

  • Use a struct instead of a tuple. This saves typing, and lets us give meaningful names to the member variables, instead of trying to remember what e.g. std::get<1>() is referring to.

  • please_conform is not an informative name. Perhaps something like find_adjacent_ranges or find_runs would be better.

  • please_conform() has a lot of repetition. Since we increment forward_count or backward_count in every branch, it might be best to do this at the start of each loop iteration (and count the last item outside of the loop).

  • please_conform() finds "runs" of the same cap direction. We can do this more easily with two for loops: an outer loop to increment the "start" index of each run, and an inner loop to find the "end" index (which will be the "start" index of the next run). We can use std::find for the inner loop.

  • If we store the "forward" and "backward" ranges in two separate vectors, we can simplify the "speak_commands" function considerably, since we don't have to check each range to see if the direction matches the one we want to flip.


Applying some of the suggestions above:

#include <iostream>
#include <vector>

struct range
{
    std::size_t start = 0;
    std::size_t size = 0;
};

struct ranges
{
    std::vector<range> ranges;
    std::size_t total = 0;
};

void find_ranges(std::vector<bool> const& caps, ranges& forward, ranges& backward)
{
    forward = ranges();
    backward = ranges();

    if (caps.empty())
        return;

    for (std::size_t i = 0; i != caps.size(); )
    {
        bool style = caps[i];
        std::size_t start = i;
        std::size_t end = (std::find(caps.begin() + i + 1, caps.end(), !style) - caps.begin());
        std::size_t size = (end - i);

        ranges& rs = (style ? forward : backward);
        rs.ranges.push_back({start, size});
        rs.total += size;

        i += size;
    }
}

void speak_commands(std::vector<range> const& ranges)
{
    for (auto const& r : ranges)
    {
        if (r.size == 1)
            std::cout << "Person in position " << r.start << " please flip your cap.\n";
        else
            std::cout << "People in positions " << r.start << " through " << (r.start + r.size - 1) << " (inclusive) please flip your caps.\n";
    }
}

int main()
{
    std::vector<bool> caps = { true, true, false, false, false, true, false, false, false, true, true, false, true };

    ranges forward, backward;
    find_ranges(caps, forward, backward);

    ranges const& to_flip = (backward.total <= forward.total ? backward : forward);
    speak_commands(to_flip.ranges);
}
\$\endgroup\$
2
\$\begingroup\$

Parameter Passage to Functions
The code isn't exactly working as expected, the variables forward_count and backward_count that are passed from main() into please_conform() are being passed by value rather than by reference so they are still zero when the function please_conform() returns. The vector caps is being passed by reference when it should be passed by value because the vector is not being changed in please_conform(). It might be better if the variables forward_count and backward_count were local to please_conform and a single variable possible of type char was returned that indicated the direction.

Duplication of Code
This code repeats several times in the function please_conform():

            positions.push_back(std::make_tuple(start, end, caps[end]));
            if (caps[end] == 'F')
            {
                forward_count++;
            }
            else
            {
                backward_count++;
            }

There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code multiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well.

Complexity
The functions please_conform() and speak_commands() are both too complex and should be broken into smaller functions. Both functions violate the Single Responsibility Principle that states

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

One of the functions that should be added for please_conform() is described in Duplication if Code above. It is important to note that if the tuple contained one more field which was the character indicating the director there would be less duplication of code and the variables forward_count and backward_count would not be need in please_conform().

The comparison of forward_count and backward_count in the begining of the function speak_commands() would probably be better as it's own function. This function could iterate through the tuples incrementing forward_count and backward_count and then return the direction that wins the comparison. This function could be called either by main() or by speak_commands()

The idea behind this is to keep breaking actions up into smaller and smaller functions until each function does only one thing.

Here is one possible re-write of the speak_command() function.

char which_cap_to_flip(std::vector< std::tuple<std::size_t, std::size_t, char> >& positions)
{
    unsigned forward_count = 0;
    unsigned backward_count = 0;

    for (auto cap: positions)
    {
        if (std::get<2>(cap) == 'F')
        {
            forward_count++;
        }
        else
        {
            backward_count++;
        }
    }

    return  (forward_count < backward_count) ? 'F' : 'B';
}

void speak_commands(std::vector< std::tuple<std::size_t, std::size_t, char> >& positions)
{
    char cap_to_flip = which_cap_to_flip(positions);

    for (std::size_t i = 0; i < positions.size(); ++i)
    {
        if (std::get<2>(positions[i]) == cap_to_flip &&
            std::get<0>(positions[i]) == std::get<1>(positions[i]))
        {
            std::cout << "People in position " << std::get<0>(positions[i]) << " flip your cap!\n";
        }
        else if (std::get<2>(positions[i]) == cap_to_flip &&
                 std::get<0>(positions[i]) != std::get<1>(positions[i]))
        {
            std::cout << "People in positions " << std::get<0>(positions[i]) << " through " << std::get<1>(positions[i]) << " flip your caps!\n";
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.