Category Archives: C++ Code

Solving large puzzles on HackerRank

I’ve solved quite a few puzzles on HackerRank, HackerRankbut this one had me stumped. The actual algorithm didn’t seem too hard, although there is a bit of a trick to it. The problem I had was extending the solution afterwards to handle large numbers. Usually, it’s enough to use ‘long long’ throughout, but it still wasn’t passing all the test cases.

In the end, I narrowed down the problem to the following code:

  long long maximiseScore( int N )
  {
    std::vector<long long> health( N, 0 );
    for ( size_t i = 0; i < N; ++i ) std::cin >> health[i];
    long long sum = std::accumulate( health.begin(), health.end(), 0 );
    // ...
  }

In case you didn’t spot it, the bug is that std::accumulate has inferred the type of the init parameter from 0 (zero), which is an int. So the sum is calculated as an int, then assigned into our long long variable. The solution is to cast the init to a long long (either using ‘LL’ or static_cast).

    long long sum = std::accumulate( health.begin(), health.end(), 0LL );

Leave a comment

Filed under C++, C++ Code, Programming

How to initialise data concisely in C++

In the past, creating a collection of dates was a chore, because you had to individually insert them into a container (e.g. declaring a vector on one line and then pushing dates into it on subsequent lines). With features like std::initializer_list from C++11 onwards, it’s now much easier to do this concisely.

Here’s some simple, concise code to create dates without all the hassle:

struct Date
{
    std::string Event;

    int Year;
    int Month;
    int Day;
};

void print( const Date& date )
{
    std::cout << date.Event << ": "<< date.Year << "/" << date.Month << "/" << date.Day << "\n";
}

void print( const std::vector<Date>& dates )
{
    for ( auto date : dates )
    {
        print( date );
    }
}

void test()
{
    std::cout << "Print date:\n";
    print( { "Today", 2015, 5, 5 } );

    std::cout << "Print dates:\n";
    print( {
        { "Christmas", 2015, 12, 25 },
        { "Spring Bank Holiday", 2016, 6, 30 }
           } );
}

This style is particularly useful when writing tests – you can write a whole test, including setting up the data, on a single line (or at least, in a single function call).

Another compelling use case comes when creating test cases for graph algorithms. Suppose you have the following data structures for an undirected, weighted graph:

struct Edge
{
    const size_t end1;
    const size_t end2;
    const size_t cost;
};

struct Graph
{
    size_t source;
    size_t nodes;
    std::vector<Edge> edges;
};

Then creating a test graph to pass into an algorithm is as simple as:

shortest_path( { 0, 4, { {0,1,24}, {0,3,20}, {2,0,3}, {3,2,12} } })

Leave a comment

Filed under C++, C++ Code, Programming

How to efficiently find the n’th biggest element in a collection

Looking at std::nth_element the other day, I noticed that it’s complexity is O(n) for a collection of size n, and wondered how that was achieved. A basic implementation of an algorithm to find the ith-biggest element might start by sorting the collection and index to the ith afterwards – complexity O(n*log(n)):

int ith_element_by_sorting( std::vector<int> input, int i )
{
    std::sort( std::begin(input), std::end(input) );
    return input[i];
}

It’s a small step to realise then that you don’t need to sort all n elements of the collection – only the first i elements, so complexity O(n*log(i)):

int ith_element_by_partial_sort( std::vector<int> input, int i )
{
    std::partial_sort( std::begin( input ), std::begin( input ) + i + 1, std::end( input ) );
    return input[i];
}

But the real trick is that you don’t need to do any sorting at all. That’s the approach taken by quickselect, which is the selection sibling to quicksort, and achieves O(n) complexity on average:

int partition( std::vector<int>& values, int left, int right, int pivot )
{
     auto pivotValue = values[ pivot ];

     std::swap( values[pivot], values[right] ); // Move pivot to end
     auto store_pos = left;

     for ( int j = left; j < right; ++j )
     {
         if ( values[j] < pivotValue )
         {
             std::swap( values[ store_pos ], values[j] );
             ++store_pos;
         }
     }

     std::swap( values[right], values[ store_pos ] );  // Move pivot to its final place

     return store_pos;
}

int quickselect( std::vector<int> values, int left, int right, int i )
{
    // Unordered - no need to sort values at all, 
    // instead we recursively partition only the subset of values
    // containing the i'th element, until we have either
    // a) trivial subset of 1
    // b) pivot is moved to exactly the location we wanted 
    while( 1 )
    {
         if ( left == right )
         {
             return values[left];
         }

         // Pick a pivot from middle of values.
         // Better options are a random pivot or median of 3
         auto pivot = (left + right)/2; 

         // Move anything smaller than values[pivot] to the left of pivot,
         // and return updated position of pivot
         pivot = partition( values, left, right, pivot );

         if ( pivot == i )
         {
             return values[i];
         }
         else if ( i < pivot )
         {
             right = pivot - 1;
         }
         else
         {
             left = pivot + 1;
         }
    }
}

int ith_element_by_quickselect( const std::vector<int>& input, int i )
{
    return quickselect( input, 0, input.size()-1, i );
}

int ith_element( const std::vector<int>& input, int i )
{
    if ( i < 0 || i >= input.size() )
    {
        std::ostringstream ss;
        ss << "Input '" << i << "' outside range [0," << input.size() << ")";
        throw std::out_of_range( ss.str() );
    }

    return ith_element_by_quickselect( input, i );
}

Here’s some test code to check that the implementation works:

template <typename F, typename T>
void should_be( T t, F f, const std::string& message )
{
    try
    {
        std::ostringstream ss;

        auto got = f();
        if ( got != t )
        {
            ss << message << " got " << got << ", expected " << t;
            throw std::runtime_error( ss.str() );
        }
        else
        {
            ss << "OK: " << message << ": got " << got;
            std::cout << ss.str() << "\n";
        }
    }
    catch( const std::exception& ex )
    {
        // Report error if either f() threw or we found unexpected value
        std::cout << "ERROR: " << ex.what() << "\n";
    }
}

template <typename F>
void should_throw( F f, const std::string& message )
{
    try
    {
        f();
    }
    catch( const std::exception& ex )
    {
        std::cout << "OK: " << message << ": threw \"" << ex.what() << "\"\n";
        return;
    }

    std::cout << "ERROR: " << message << " should have thrown\n";
}

#define SHOULD_BE( t, expr ) should_be( t, [](){ return expr; }, #expr )
#define SHOULD_THROW( expr ) should_throw( [](){ expr; }, #expr )

void testIthElement()
{
    SHOULD_THROW( ith_element( {}, 0 ) );
    SHOULD_THROW( ith_element( {1,2}, -1 ) );
    SHOULD_THROW( ith_element( {1,2,3}, 3 ) );

    SHOULD_BE( 1, ith_element( {1}, 0 ) );
    SHOULD_BE( 0, ith_element( {0,1,2,3,4,5,6,7,8}, 0 ) );
    SHOULD_BE( 2, ith_element( {0,1,2,3,4,5,6,7,8}, 2 ) );
    SHOULD_BE( 6, ith_element( {5,4,7,6,1,2,0,8,3}, 6 ) );
    SHOULD_BE( 8, ith_element( {5,4,7,6,1,2,0,8,3}, 8 ) );
    SHOULD_BE( 5, ith_element( {5,5,5,5,5,5}, 1 ) );
}

Here’s the output:
QuickSelect

In fact, reviewing old posts on this blog, I found this link that dates back to 2013, when std::nth_element was only required by the standard to have worst-case O(N^2) complexity, with O(N) on average – precisely what you’d get from quickselect. Now though, thanks to introselect, O(N) is possible.

Leave a comment

Filed under C++, C++ Code, Programming

Tech Book: Effective Modern C++, Scott Meyers

EffectiveModernC++When Scott Meyers announced his retirement from C++ duties, I thought I’d get a copy of his latest book. There’s plenty in it to interest even seasoned C++ developers – as always, Scott’s insight and in-depth examples are worth studying. I’ve tried out most of the C++11 features, but still learnt a lot working through this book.

Uniform Initialisation and Auto
Meyers points out that compared to parentheses or just plain “=”, braced initialisation can be used in the most contexts, avoids his famous “C++’s most vexing parse”, and will issue compiler errors if narrowing occurs. However, for types that can take a std::initialiser_list in their constructor, the compiler is required to favour std::initialiser_list over any other interpretation. That’s a deterrent to use of braced initialisation with types that have a std::initializer_list constructor – and also precludes using auto with braced initialisation.

auto x = { 4 }; // type of x is inferred to be std::initializer_list&lt;int&gt;!

How to use the new “= delete” idiom
Meyers recommends declaring deleted methods as public to get better error messages from compilers that check for accessibility before deleted status. He also points out that you can declare non-member functions as deleted (I’d only seen examples of copy-constructor/copy-assignment operator as deleted before).

Use of noexcept on move operations
This one is a classic example of a combination of language features having an unexpected effect. std::vector::push_back offers the strong exception guarantee. It can achieve this using any copy constructor and being sure not to change the original contents of the vector until any new elements or copies have been constructed. Hence, move constructors are only preferred if it is exception-safe to do so – which means they must be marked as noexcept (and if that isn’t appropriate, you just won’t get move semantics pushing instances of your type into a std::vector).

Recursion with constexpr
Having toyed with template meta-programming in the past, this use of constexpr appeals to me:

constexpr int pow( int b, int exp ) noexcept
{
    return (exp == 0 ? 1 : b * pow( b, exp-1 ));
}
constexpr auto eight = pow( 2, 3 );

void testConstExpr()
{
    std::cout &lt;&lt; &quot;2^3 = &quot; &lt;&lt; eight &lt;&lt; &quot;\n&quot;;
}

It’s much more succinct than the equivalent TMP version, and still performs the calculation at compile time.

Summary
In the past, I’ve recommended Effective C++ for developers who have little experience of the language and wish to improve their skills. I think this book is a bit too advanced for that, particularly given the chapters on template type deduction and decltype being in the first part of the book! So read this book if you’ve got a few years’ experience of C++ already, but look at Effective C++ (3rd Edition) to improve on the basics.

Four stars

Leave a comment

Filed under C++, C++ Code, Programming, Tech Book

How to write generic, duck-typing code in F#

When writing generic code in C++, it’s easy to imply constraints in the generic type when developing a template. For example:

template<class T> 
class Announcer{
public:
	static void announce( const T& t )
	{
		std::cout << "And now from " <<  t.country << ", we have: ";
		bool first = true;
		for ( auto person : t.people )
		{
			std::cout << person;
			if (!first) std::cout << "\n";
			first = false;
		}
	}
};

Here, we’re assuming that T has two properties, ‘country’ and ‘people’, with the latter being enumerable (i.e. supports begin/end methods and iterators). This is one of the attractions of C++ for generic code – although, in the future, concepts will enable you to document the constraints in order to make it easier for developers to use your library, and for the compiler to give clearer errors.

What about something similar in F#? I found Tomas Petricek’s post from StackOverflow very useful.

type IHasCountryProperty =
    abstract Country : string

type Announcer<'T when 'T :> IHasCountryProperty>( item : 'T) =
    member this.Announce() =
        printfn "And now the party from %s" item.Country

let inline countrifiedItem<'T when 'T : (member Country : string)> (item : 'T) =
    {
        new IHasCountryProperty with
            member this.Country = (^T : (member Country : string) item)
    }

type London() =
    member this.Country = "England"

// Use it
let city = London()
Announcer( countrifiedItem city ).Announce()

The Announcer class uses a member constraint with statically resolved type parameters which bind to the Country property. Then, the inline static function ‘countrifiedItem’ uses static member constraints to capture the existing Country property on any other type, even if like ‘London’ it doesn’t support the IHasCountryProperty. The consensus seems to be that this approach is encouraged because it documents the requirements on ‘T in an interface.

Leave a comment

Filed under C++, C++ Code, F#, Programming

C++: std::make_array (N4315)

I read in May 2015’s CVU that there’s a proposal for std::make_array, a utility method in the same family as std::make_tuple and std::make_pair.

This would be a useful shorthand:

// Existing usage
std::array<double, 3> a = { 1.1, 2.2, 3.3 };

// Proposed usage
auto a = std::make_array( 1.1, 2.2, 3.3 };

The obvious benefit is that you would no longer need to specify the number of elements in the array, making the code more maintainable.

Leave a comment

Filed under C++, C++ Code

How to achieve pattern matching in C++ using boost::regex

Suppose you are parsing text input and need to handle the string representation of a field that could have several formats. In that case, using regular expressions is appealing because you can try a number of patterns sequentially (taking the most likely first) and exit when you get a match.

When I tried to do this in C++, I found it hard to find an easy example to follow. Here’s the way I’ve been doing it, based on a simple example to parse a length that could be in any of several units of measure:

    #include <boost/algorithm/string_regex.hpp>

    void parse( const std::string& candidate )
    {
        boost::smatch value;

        if ( boost::regex_search( candidate, value, boost::regex( "(.*)ft(.*)in" )) )
        {
            auto feet = atol( value[1].str().c_str() );
            auto inches = atof( value[2].str().c_str() );
            std::cout << "Matched " << feet << " feet and " << inches << " inches\n";
        }

        if ( boost::regex_search( candidate, value, boost::regex( "(.*)m(.*)cm" )) )
        {
            auto metres = atol( value[1].str().c_str() );
            auto centimetres = atof( value[2].str().c_str() );
            std::cout << "Matched " << metres << " metres and " << centimetres << " centimetres\n";
        }

        if ( boost::regex_search( candidate, value, boost::regex( "([0-9]+)mm" )) )
        {
            auto millimetres = atol( value[1].str().c_str() );
            std::cout << "Matched " << millimetres << " millimetres\n";
        }

        throw std::runtime_error( (boost::format( "Failed to match candidate '%1%' with ft/in, m/cm or mm" ) % candidate).str() );
    }

This only uses a fraction of what can be done with regex – the point is to show how to use boost::regex. One gotcha is that, as per the code above, the string matches that are written into value are indexed from 1 – for some reason, the zero’th index accesses the whole candidate expression. Another gotcha is that boost::regex is one of the few boost libraries that isn’t just implemented using templates in a header file, so you also have to add the appropriate .lib into the linker inputs.

1 Comment

Filed under C++, C++ Code, Programming