During last CppCon, a set of C++ puzzles was presented within the SCM Challenge (thanks for an iPad BTW). While most of those puzzles were quite generic and simple, one puzzle did really stand out. The one I’m mentioning here was called “Don’t Repeat Yourself” and was introduced by Arthur O’Dwyer.
Here is problem statement:
Write a program that prints the numbers from 1 to N, then back down to 1, separated by whitespace. But Don’t Repeat Yourself: each word in your submitted source code must be unique! A “word” is defined as in Part 1. How large of an N can you achieve?
And that is the definition of a “word” from Part 1:
Write a function that returns true if every word in its input is unique. A “word” is defined as any maximal string of consecutive word characters, and a “word character” is defined as a digit, letter, or underscore. For example, the string “5+hello-world 0_9/a7” contains five words, all unique; so your function should return true. The string “abc+abc_+abc” contains three words, of which the first and last are both “abc”, so your function should return false.
This task, harmless at first sight, turns into a ridiculously hard riddle. “Uniqueness” means that it’s not possible to access any identifier – it can only be declared, but never touched again. The same applies to preprocessor statements, language keywords and so forth. Unfortunately, there’s no known “right” solution to this puzzle (at least for me). Arthur showed 3 possible solutions made by CppCon participants, including mine, during his lightning talk, but all those were hacks more or less. One exploited the trick with escape sequences in string literals, another used a plain assembled binary injected into the source code. Mine used the stack hack to get a read-write access to the function parameter.
The clean variant of my solution is shown below. It assumes libstdc++ environment and gcc compiler. Of course, there’s no compatibility with other compilers and/or standard libraries. A few notes on the solution:
– Optimization is turned off by a compiler-specific pragma to get access to the stack. Parameter passing would be optimized otherwise.
– User-defined literal is used to mimic the function syntax. Otherwise, it would not be possible to call the function.
– The function parameter N is accessed via stack frame address hack and via zero-sized alloca() hack.
– errno is used as another counter variable, thanks to the library-specific alias.
#include <iostream> using namespace std; __attribute__((optnone)) void operator "" _print( decltype(0ULL) ) { for(; errno <= ((uint64_t*)__builtin_alloca(0L))[3L];) cerr << ++*__errno_location() << " "; while( ((int64_t*)__builtin_frame_address(0))[-1L] ) cout << ((long*)alloca(0LL))[3]-- << " "; } int main() { // print numbers up to 500 and back 500_print; }