Google Code Jam 2017 1B - Stable Neigh-bors

Question

Last week I participated in Google code Jam round 2B and miserably failed. I still decided to finish the second question, for practice. Here it is:

Problem

You are lucky enough to own N pet unicorns. Each of your unicorns has either one or two of the following kinds of hairs in its mane: red hairs, yellow hairs, and blue hairs. The color of a mane depends on exactly which sorts of colored hairs it contains:

A mane with only one color of hair appears to be that color. For example, a mane with only blue hairs is blue.
A mane with red and yellow hairs appears orange.
A mane with yellow and blue hairs appears green.
A mane with red and blue hairs appears violet.

You have R, O, Y, G, B, and V unicorns with red, orange, yellow, green, blue, and violet manes, respectively.

You have just built a circular stable with N stalls, arranged in a ring such that each stall borders two other stalls. You would like to put exactly one of your unicorns in each of these stalls. However, unicorns need to feel rare and special, so no unicorn can be next to another unicorn that shares at least one of the hair colors in its mane. For example, a unicorn with an orange mane cannot be next to a unicorn with a violet mane, since both of those manes have red hairs. Similarly, a unicorn with a green mane cannot be next to a unicorn with a yellow mane, since both of those have yellow hairs.

Is it possible to place all of your unicorns? If so, provide any one arrangement.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with seven integers: N, R, O, Y, G, B, and V.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if it is not possible to place all the unicorns, or a string of N characters representing the placements of unicorns in stalls, starting at a point of your choice and reading clockwise around the circle. Use R to represent each unicorn with a red mane, O to represent each unicorn with an orange mane, and so on with Y, G, B, and V. This arrangement must obey the rules described in the statement above.

If multiple arrangements are possible, you may print any of them.

[...]

Sample

Input

4
6 2 0 2 0 2 0
3 1 0 2 0 0 0
6 2 0 1 1 2 0
4 0 0 2 0 0 2

Output    

Case #1: RYBRBY
Case #2: IMPOSSIBLE
Case #3: YBRGRB
Case #4: YVYV

Here is my code :

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <functional>

//Problem B

typedef long long num;
typedef std::map<char, num> unicorns_t;

static const std::map<char, std::vector< char >> okNeighbor = {
    { 'R', { 'Y', 'B', 'G' } },
    { 'O', { 'B' } },
    { 'Y', { 'R', 'B', 'V' } },
    { 'G', { 'R' } },
    { 'B', { 'R', 'O', 'Y' } },
    { 'V', { 'Y' } },
    { 'A', { 'R', 'O', 'Y', 'G', 'B', 'V' } }
};

static const std::vector<char> colors = { 'R', 'O', 'Y', 'G', 'B', 'V' };

static const std::string IMPOSSIBLE = "IMPOSSIBLE";

std::string solution;
unicorns_t unicorns;
num nUnicorns;

bool isSolved()
{
    if( solution.empty() ) return false;
    const auto& options = okNeighbor.at( solution.front() );
    return ( solution.size() == nUnicorns and std::find( options.begin(), options.end(), solution.back() ) != options.end() );
}

std::string solve( )
{
    std::vector< char > options;
    if     ( solution.empty() )             options = std::cref( colors );
    else if( solution.size() == nUnicorns ) options = std::cref( okNeighbor.at( solution.front() ) );
    else                                    options = std::cref( okNeighbor.at( solution.back()  ) );

    for( const auto& option : options )
    {
        if( !unicorns[ option ] ) continue;
        solution.push_back( option );
        --unicorns[ option ];

        if( isSolved() )          return solution;
        if( solve(), isSolved() ) return solution;

        solution.pop_back();
        ++unicorns[ option ];
    }
    return IMPOSSIBLE;
}

int main()
{
    num cases;
    std::cin >> cases;

    for( num i = 1; i <= cases; ++ i )
    {
        nUnicorns = 0;
        std::cin >> nUnicorns;

        std::cin >> unicorns[ 'R' ] >> unicorns[ 'O' ] >> unicorns[ 'Y' ];
        std::cin >> unicorns[ 'G' ] >> unicorns[ 'B' ] >> unicorns[ 'V' ];

        solution = "";
        std::cout << "Case #" << i << ": " << solve() << "\n";
    }
}

I would really appreciate comments about coding style, efficiency or anything else that would come to mind.

Answer 1

Avoid typedefs that obfuscate the underlying type

These typedefs

typedef long long num;
typedef std::map<char, num> unicorns_t;

make it actually harder hard to read and understand the code. At least give them understandable names if you think these are necessary:

typedef long long longnum; // or largenum
typedef std::map<char, num> unicornsMap;

With modern c++ prefer using statements over typedef BTW

using longnum = long long;
using unicornsMap = std::map<char, num>;

the readability is more intuitive.

Prefer function parameters instead of global variables

Instead of keeping state in these gloal variables

std::string solution;
unicorns_t unicorns;
num nUnicorns;

use function parameters:

bool isSolved(const std::string& solution)
{
    // ...
}

this will make your code more reusable.

Encapsulate data in a class instead of using global variables

Again, something like

class UnicornSolver {
public:
    UnicornSolver(const std::map<char, std::vector< char >>& okNeighbors) 
    : okNeighbors_(okNeighors) {}
    std::string solve();
private:
    bool isSolved(const std::string& solution);

    const std::map<char, std::vector< char >>& okNeighbors_;
};

will enhance reusability of your code, e.g. if the rule set defined in okNeighbours should be changed.

Always use proper scoping

For sake of maintainability you should always proper scoping in conditional statements. Rather than writing something like

if     ( solution.empty() )             options = std::cref( colors );   else if( solution.size() == nUnicorns ) options =

std::cref( okNeighbor.at( solution.front() ) ); else options = std::cref( okNeighbor.at( solution.back() ) );

use curly braces to clarify scoping (even if there's only a single statement):

if ( solution.empty() ) {
    options = std::cref( colors );
}
else if( solution.size() == nUnicorns ) { 
    options = std::cref( okNeighbor.at( solution.front() ) );
}
else { 
    options = std::cref( okNeighbor.at( solution.back()  ) );
}

Not only that it is more readable, it is less error prone if additional statements should be added in the future.

Don't misuse the comma operator to call side effects

Stuff like

if( solve(), isSolved() ) return solution;

is incredibly hard to read, and in combination with the recursion just makes it hard to understand what's going on.

You should make your intend and progam flow clear:

 if(isSolved()) {
     return solution;
 }
 else {
     // Recurse
     solve();
 }

Avoid recursive function calls, use a std::stack instead

Recursive function calls make it harder to grasp the workflow of your code. Also the funtion call stack is limited, and if your functions would have parameters you could easily run out of available stack space.

Well in your case you could replace the recursive calls simply with a loop, because there aren't any parameters to be stack saved at all:

std::string solution;
while(!isSolved(solution)) {
    solve(solution);
}

If you really need to keep parameters stack saved for iterations, you can use a loop in combination with a std::stack.

Avoid using unusual (old) keywords

Every experienced C++ programmer would stumble over a statement like

nUnicorns and std::find( options.begin(), options.end(), solution.back() ) != options.end() );
       // ^^^

Sure it works and may be even more clear for beginners, we would prefer to see

nUnicorns && std::find( options.begin(), options.end(), solution.back() ) != options.end() );
       // ^^

It is crystal clear what && means in that context, and it is not the same as the binary operation &.