About the SCM Challenge at CppCon 2016 – Pirates

In 2016, I agreed to write a programming challenge for CppCon, at the request of the fine folks at Waterfront International. The SCM Challenge, as it became known, was a series of programming challenges written that year by yours truly, as well as Herb Sutter and Jason Turner. Herb went for something deep about deferred memory reclamation (you can read more about it here); Jason went for a constexpr-related challenge, which shouldn’t surprise anyone as constexpr is Jason’s « One True (Technical) Love »… I, looking at the calendar and noticing my challenge would air on Talk Like a Pirate Day, decided I would write a pirates-related challenge.

I’ve been one of SCM Challenge authors in 2016, 2017 and 2018, and I’ve been asked quite a few times in the past to discuss these challenges (and potential answers) publicly, so I took some time and went through my archives to get back what I wrote, what I was aiming for, and what the solutions I envisioned were.

The Challenge

In 2016, I went for a three part challenge where people trying to solve the puzzle would need to solve the first part to get to the second part, and then solve the second part to get the final boss part. I heard from many participants that they found the first part to be harder than the other two, but that probably says more about CppCon 2016 attendees and the way they approach programming problems than it does about the challenge itself.

Informally, the steps of that challenge were:

  • There exists a cove with a key that cannot be accessed; find a way to fool the system and get a working key nonetheless
  • There is a combination to a safe that needs to be expressed in such a way as to make it look like a function can be overloaded based on return type
  • There is a need to use a user-defined literal to declare and initialize a variable with a single expression using a user-defined literal, but with some interesting restrictions

The general idea I had in mind was to let people enjoy C++ programming while trying to find creative ways to perform unusual tasks. I feared (slightly) that people might criticize this challenge on the grounds that it could be said to present C++ as tricky or experts-only (or use some other criticism one too often reads about the language), but then, there are tricks in all programming languages, and in the end I simply decided to have fun and go along with my plan.

One thing you have to know before reading further is that there are « language version constraints » in the challenges, as some things were trickier to do in the past than they are today; C++ has evolved immensely in the last decade, after all. Thus, the maintainers of the test site for the challenge were kind enough to accomodate me by enforcing compiler options that restricted the set of features one could use to a specific version of C++. If you did not try the challenge back then, know that it is more interesting if you respect those restrictions.

Let’s go through these challenges one by one.

First Step

The first step was presented as follows:

C++ Pirates have roamed the seas for a long time. They have hidden treasures in many a secret cove. The following is one such cove:

#include <iostream>
#include <string>
using namespace std;
class secret_cove {
   class hidden_password {
   };
public:
   template <class K>
      string accept(K k) {
         return k(*this, hidden_password{});
      }
   string key_to_next_level(hidden_password) const {
      return "sesame!";
   }
};
struct legal_key {
   template <class PWD>
      string operator()(const secret_cove &sc, PWD pwd) const {
         return sc.key_to_next_level(pwd);
      }
};
// Implement Skeleton Key here
int main() {
   secret_cove hideout;
   cout << hideout.accept(legal_key()) << endl;
}

In this code, C++ Pirates think they have found a way to control access to the key to the next level, by requiring users to first obtain an instance of secret_cove::hidden_password which is hidden, private, within secret_cove.

The expected way to obtain a hidden_password instance is through the secret_cove::accept() member function, which will call back a K object and pass it a secret_cove::hidden_password instance. The C++ Pirates see this as a way to force users to use such objects as a legal_key, which can use a hidden_password but cannot really keep it in a meaningful manner.

Your task is to be a C++ Pirate trying to access secret_cove::key_to_next_level() without first passing through secret_cove::accept(). Since C++ Pirates are very much « old school », you are not allowed to use any C++ feature since C++11 (you are limited to C++03 and less).

Your answer must be such that the following code compiles and works without modifiying secret_cove in any way:

cout << hideout.key_to_next_level(skeleton_key()) << endl;

… as the skeleton_key is the key to open all coffers.

Once you have found the skeleton_key, the next challenge will be revealed.

The idea

Restricting oneself to C++03 and less, there aren’t that many options to solve this one. I’ve been told by attendees that week that they had found this first part of the challenge to be the hardest of the three; it’s a matter of mindset, probably.

Part of the difficulty was in the way skeleton_key was presented. Indeed, if you look at this:

cout << hideout.key_to_next_level(skeleton_key()) << endl;

… you might think that skeleton_key should be a function.

It so happens that it also can be a constructor, and that skeleton_key could be a struct or a class; now, that was deliberately not spelled out in the challenge’s proposal, which could be one of the reasons why some people found it… challenging.

Once one sees skeleton_key as a class, the problem becomes: how does one convert a skeleton_key to some type that is not really accessible such as secret_cove::hidden_password if one cannot even use that name in class skeleton_key.

The trick is not to do it explictly; instead, let the compiler know how to proceed if it needs to do so:

struct skeleton_key {
   template <class T> operator T() const { return T(); }
};

By writing an implicit conversion operator to some type T, one can make it possible for the compiler to convert a skeleton_key object to any default T, which was sufficient in this case to overcome the challenge.

Note that in C++11, one could express the same thing as

struct skeleton_key {
   template <class T> operator T() const { return {}; }
};

… but the challenge becomes very easy to solve in practice as one can simply write

cout << hideout.key_to_next_level({}) << endl;

… and be done with it. Note that something as simple adding a defaulted default constructor to secret_code::hidden_password would block this. However, as stated previously, this one had to be solved with tools from older times.

Second Step

The second step in the C++ Pirates challenge was expressed as follows:

Once you have accessed the secret cove, the next step is to unlock a safe. This requires understanding the safe’s combination. Since C++ Pirates are more clever than your average pirate, the trick is not really to decode what sequence of numbers is required to unlock the safe, but to find a way to ensure all three outputs in main() below give precisely the same output, given that all three values passed to trick are integers found inclusively between 0 and 9 (you are not expected to validate these inputs):

 #include <iostream>
 #include <string>
 using namespace std;
 struct combination {
    int first, second, third;
    constexpr combination(int first, int second, int third) noexcept
       : first{ first }, second{ second }, third{ third } {
    }
    constexpr bool operator==(const combination &c) const noexcept {
       return first == c.first && second == c.second && third == c.third;
    }
    constexpr bool operator!=(const combination &c) const noexcept {
       return !(*this == c);
    }
 };
 ostream& operator<<(ostream &os, const combination &c) {
    return os << c.first << c.second << c.third;
 }
 // YOU CODE GOES HERE
 int main() {
    string str_comb = trick(1, 2, 3);
    int int_comb = trick(1, 2, 3);
    combination comb_comb = trick(1, 2, 3);
    cout << str_comb << endl;
    cout << int_comb << endl;
    cout << comb_comb << endl;
 }

The Idea

In this case once again, I was guilty of deliberately misguiding participants. The trick() function seems to be such that it overloading based on return type, something which is not supported in C++.

However, if one realizes that trick can be a class or a struct instead of a function, and that trick(int,int,int) can in fact be trick::trick(int,int,int), one can solve this challenge with conversion operators again, albeit using a different tactic.

Note that we were in 2016, so C++17 was not out yet. With C++14 and prior, a simple solution to this challenge would be:

struct trick {
   int one, two, three;
   trick(int one, int two, int three) : one{ one }, two{ two }, three{ three } {
   }
   operator string() const { return to_string(one) + to_string(two) + to_string(three); }
   operator int() const { return one * 100 + two * 10 + three; }
   operator combination() const { return{ one, two, three }; }
};

… which lets one create a trick instance with three integers, and then convert that trick in either a string, an int or a combination depending on the context. For added fun, it looks to the untrained eye as a way to write a function with multiple return types depending on context.

Now, after two conversion-related challenges, there remained the third challenge. Again, misguiding participants was part of the fun…

Third Step

Here’s how that final step in the 2016 challenge was described to participants:

Real C++ Pirates know how to get rich. Once you’ve found your way to the treasure room, you can hope to shout « Rich, I’m Rich, So Rich! ». But there’s a trick: this will only work (a) if you can define and initialize the cash variable in main() in a single expression, using the _rich user-defined literal but (b) adding only the initialization of cash, and (c) without explicitly writing the namespace-qualified name for this literal (for example, expressing 2s as std::chrono::operator""s(2) would turn you into fishmeat). As you know, cheaters will have to walk the plank…

namespace cpp_pirate {
   struct rich_im_rich_so_rich {
      unsigned long long amount;
      constexpr rich_im_rich_so_rich(unsigned long long amount) : amount{ amount } {
      }
      friend ostream& operator<<(ostream &os, const rich_im_rich_so_rich &rrisr) {
         return os << rrisr.amount;
      }
   };
   constexpr rich_im_rich_so_rich operator"" _rich(unsigned long long amount) {
      return{ amount };
   }
}
 int main() {
    // YOUR CODE GOES HERE
    cout << cash << endl;
 } 

The Idea

This one is easy to do if one is aware of Immediately Invoked Function Expressions (IIFE), a nice feature of C++ which lets one create an anonymous lambda expression and invoke it all in one fell swoop. Note that IIFEs open up the door for a number of interesting programming tricks, but we’ll return to that at some point in the future.

Lambdas being scopes (among other things), one can use them to insert a very local using directive and benefit from that using directive without it spilling outside of the lambda.

Knowing that, a nice solution to that third and last part of the 2016 challenge would be:

int main() {
   auto cash = [] { using namespace cpp_pirate; return 1'000'000_rich; }();
   cout << cash << endl;
}

Note that we could even have made cash a const variable using this trick!

Thoughts

Writing programming challenges is a fun job. Since writing quizzes and exams is part of my dayjob (along with teaching programming and doing a number of not-so-glamorous things), I must say that giving a helping hand for the CppCon challenges was something I did with a smile.

The nature of such challenges in a big, specialized event such as CppCon is something I’ve wondered about from day one, however. Should I go for something deep that makes people think? Something that pushes the boundaries of the language? Something to make people experiment with features I want them to know more about? Should I push my « WG21 agenda items » by giving participants a feel for the things I want to see included in the language? (that last one would be a bit machiavellian to me, but it is an actual option…)

In 2016, I went for fun and curiosities. Things that are not difficult to do, not expert-level at all, but require a « twist of the mind », thinking a bit outside of the box. When I saw the other challenges that year, I wondered for a while if I should have been more political; Herb’s challenge, for example, went for a more profound reflection on programming practice with C++, and I think it gave people a feel for some areas where we can make the language better, as well as an idea of the directions the committee is steering C++ these days.

(Note: I’ve enjoyed programming in C++ since the late 1980’s, but it’s clear to me that the experience of programming in C++ has become significantly more enjoyable in the last decade than it used to be. Someone, somewhere, is doing a good job with that language… Not perfect, of course, but quite good).

CppCon and similar events also show how amazing and talented the C++ programming community is. We have inventive, creative, hard-working people all around the globe using that amazing language in ways unforeseen and feeding us with ideas as to how we can make it better. WG21 meetings, where we discuss and debate ideas and proposals, are addictive. I love the language, I love the people that work on it, and I feel privileged to meet these brilliant users at conferences.

So I went for a challenge that was meant to be fun. I wasn’t known much from the international community back in 2016, so I expected to be low-profile and people to wonder who the hell was « that Pirates Challenge guy », but every day, people I sometimes knew but mostly did not, came to me asking for tricks and clues in order to solve this or that part (I shut up, listened and smiled, obviously). In the end, a number of people went through the entire challenge, participants seemed to have enjoyed it, and I personally did too.

On to the 2017 challenge now…

Further Reading

The conversion trick used for the skeleton_key has sometimes been named the PassKey Idiom. It’s a trick I’ve been using on occasion since 2005 or so, but I first heard it named as such by Ben Deane, who has pointed me to a 2016 article by Arne Mertz which you can find at https://arne-mertz.de/2016/10/passkey-idiom/. If you can read French, I have a (somewhat older) explanation at http://h-deb.clg.qc.ca/Sujets/Client-Serveur/Programmation-par-preuves.html if you want another take on it.

If you want to know more about IIFEs, you can check http://blog2.emptycrate.com/content/complex-object-initialization-optimization-iife-c11 by Jason Turner, http://herbsutter.com/2013/04/05/complex-initialization-for-a-const-variable/ by Herb Sutter, http://www.bfilipek.com/2016/11/iife-for-complex-initialization.html by Bartlomiej Filipek or http://www.elbeno.com/blog/?p=1645 by Ben Deane, among others. If you read French, you will find more links on https://h-deb.clg.qc.ca/Sujets/Divers–cplusplus/Lambda-expressions.html#iife

If you want to know more about User-Defined Literals (UDL), https://en.cppreference.com/w/cpp/language/user_literal is a nice starting point. Andrzej Krzemieński has a nice series on the subject at http://akrzemi1.wordpress.com/2012/08/12/user-defined-literals-part-i/, http://akrzemi1.wordpress.com/2012/10/23/user-defined-literals-part-ii/ and http://akrzemi1.wordpress.com/2012/10/29/user-defined-literals-part-iii/; there are of course many other interesting texts on the topic. Arthur O’Dwyer has some interesting thoughts on (global) using directives and how they interact with UDLs at https://quuxplusone.github.io/blog/2018/03/21/namespaces-for-udls/ If you read French, you will find more links on https://h-deb.clg.qc.ca/Sujets/Divers–cplusplus/litteraux_maison.html.