C++ Puzzle
Sleuthing with Krul

Bob Polis

What are you going to build?

Somewhere at a secret location on the web, is a message you'll need to find. You are given a starting URL, from which you retrieve a piece of plain text, using an HTTP GET request.

This text is source code, written in a mini-language, Krul, that I invented. Your task will be to write an interpreter for it, in order to be able to run the code you just downloaded.

If you run the first piece of code, you'll get a string as result. This string is a file name for the next piece of code to be downloaded. It is to be appended to the base URL for the next request to be successful.

You continue in this fashion, until you encounter a special instruction in the code, which signifies the hidden message is found. The string result of the last piece of code will be that message.

You'll build a command line tool (console application) for this in C++, which should print the message (and intermediate file names) to the standard output.

Requirements

You build a command line tool (console application) in C++.
You repeatedly download plain text from different URLs, which all have
https://www.bobpolis.com/krul/
as a base.
The first URL to download code from is formed by appending “start.txt” to the base URL. So this becomes:
https://www.bobpolis.com/krul/start.txt
You build an interpreter for the Krul language, as described further below.
You run the downloaded program, using your interpreter, which yields a string as a result.
The string you found is the file name of the next program to be downloaded. Would you have yielded the string “hooray.txt”, then the next URL to download from will be:
https://www.bobpolis.com/krul/hooray.txt
Print the string you found to the standard output.
Continue downloading and running code, until you encounter the “end” instruction. In that case the resulting string is the solution of the puzzle!
The only external library allowed is libcurl.¹

HTTP GET requests with `libcurl`

You'll use a very popular library, libcurl, for doing HTTP GET requests ². This library is available for almost every platform. It is capable of doing much more than just GET requests: it supports a plethora of networking protocols, and will make it easy to download web pages or API data, for example.

libcurl is a C library, so at least you'll need to write a C++ class to properly manage the connection to your C++ code. This is your opportunity to show you know how to handle resource management correctly.

The Krul interpreter

The interpreter you are going to write is not particularly complicated, but there are some nice challenges to get it implemented properly.

Krul uses reverse polish notation (RPN)³.

For example, the following code:

2
3
add
4
mul

yields “20” as a result.

In your implementation you'll use a stack to store values upon, or retrieve from. It is convenient to use a std::vector for that.

The example above will be easy to process, then: you push the value 2 onto the stack, then the value 3. Then, you'll call the function to execute the “add” instruction. It will pop the two values from the stack, adds them, and puts the result “5” onto the stack.

Next, 4 will be pushed onto the stack, and the “mul” instruction is executed. That will cause two values to be popped from the stack (5 and 4 in this case), multiplied, and, finally, the result “20” to be pushed onto the stack.

Please note! If I write: “pop two values from the stack”, it means that they are being read and removed from the stack. If subsequently the result of a calculation is pushed onto the stack, said result effectively replaces the two values we started with.

Please note! If you pop a value from the stack, it will be the last one pushed onto it. A stack works according to the “LIFO”-principle: last in, first out.

Design tip

You could see the interpreter as a kind of CPU. That is, as a kind of machine which processes instructions, and has certain resources at its disposal to do so.

You'll discover it's convenient to track line numbers with an integer value (for example, of type size_t), and to use it as an indicator from which line the next instruction should be read, and executed. A real CPU has a special register for that purpose, called the program counter. It always points to the next memory location from which the next instruction should be read. This is a simple mechanism, which also enables you to easily “jump” to another piece of code. All you need to do is to load the program counter with the location of the next instruction, and the rest follows suit!

Your interpreter also needs a stack for the values it works with, as descibed in the example above.

Other things you might need will become clear from the description below.

Detailed description of the Krul language

All values on the stack are strings.

This means that numerical calculations always need their values converted to integer first, before actual calculations can take place. Also, numerical results need to be converted to string first, before being pushed onto the stack.

After the last line of code, when there are no instructions left, the program should stop automatically. If the stack is not empty at that point, the last value on the stack is the end result of this Krul program.

Values & Types

42: Digits: integer literal. Push the given integer value, converted to string, onto the stack. The only allowed values are positive integers, or the value 0. (For negative values, a positive value is used, followed by a “neg” instruction.) The number 42 is just an example.
\text: Text to end of line. Consider all text after the backslash until end of line as a literal string, and push that onto the stack.
:label: Label definition. Consider all text after the colon until end of line as a label name, and remember it, together with the next line number, to enable you to jump to it later.
>label: Label reference. Push the line number, represented by the label, onto the stack. Please note: such a label reference could be encountered before you have seen the corresponding label definition. This allows for “jumping ahead”.
=var: Variable assignment. Consider all text after the equal sign until end of line as the name of a variable, to which you assign the current value on the stack. Then, remove the value from the stack.
$var: Variable reference. Push the variable's value onto the stack.

Any other literal text is to be interpreted as an instruction for the machine. All possible instructions are described below.

Integer operations

add

Add. Pop 2 values from the stack, convert to integer, add them, convert to string, and push the result onto the stack.

sub

Subtract. Pop 2 values from the stack, convert to integer, subtract the first from the second, convert the result to string, push onto the stack.

For example, the following code:

5
3
sub

yields 2 as a result, and that will be pushed onto the stack.

mul

Multiply. Pop 2 values from the stack, convert to integer, multiply them, convert to string, and push onto the stack.

div

Division with truncation. Pop 2 values from the stack, convert to integer, divide the second by the first, convert the result to string, and push that onto the stack

For example, the following code:

8
2
div

yields 4 as a result, and this value will be pushed onto the stack as a string.

mod

Modulo. Pop 2 values from the stack, convert to integer, calculate second % first, convert the result to string, and push that onto the stack.

For example, the following code:

7
3
mod

yields 1 as result, which will be pushed onto the stack (as string).

neg

Negate. Pop one value from the stack, convert to integer, invert its sign (from plus to minus, or vice versa), convert the result to string, and push it onto the stack.

abs

Absolute value. Pop one value from the stack, convert to integer, calculate the absolute value, convert the result to string, and push it onto the stack.

inc

Increment. Pop one value from the stack, convert to integer, add the value 1 to it, convert to string, and push it onto the stack.

dec

Decrement. Pop one value from the stack, convert to integer, subtract the value 1 from it, convert to string, and push onto the stack.

String operations

dup

Duplicate. Read one value from the stack (do not pop it from the stack), and push it onto the stack. The net result, therefore, is that the same value is now two times in a row on the stack.

rev

Reverse. Pop one value from the stack, do a string reverse, and push that onto the stack.

slc

Substring (slice). Pop 3 values from the stack, to, from, and the value to take a slice from. The from and to values are to be converted to integer, so you can derive the correct arguments for the substr() method of std::string from them. The from value is the string index for the first character to be used. The to value is the string index for the first character not to be included.

Please note: this is not exactly what substr() expects.

For example, the following code:

\abcdefghijklm
3
6
slc

yields “def” as a result.

idx

Index. Pop 2 values from the stack. The first is used as an index, which you convert to integer first. The second is the string value from which you want to take a single character, as selected by the index (zero-based). Push the indexed character onto the stack.

So:

\text
2
idx

yields “x” as a result.

cat

Concatenation. Pop 2 values from the stack, and combine them to make a single string value, by putting the first one after the second. Push the result onto the stack.

So:

\hello
\ world
cat

yields “hello world” as a result.

len

Length. Pop one value from the stack, determine its size (number of bytes), convert that numerical result to string, and push it onto the stack.

rot

Rotate (rot-13). Pop one value from the stack, apply a rot-13 ⁴ transformation to it, and push the result onto the stack.

enl

Add a newline. Pop one value from the stack, append a newline ('\n') to it, and push the result onto the stack.

Tests & Jumps

gto

Goto. Pop one value from the stack, interpret as a program line number, and make sure that the next instruction is taken from that line.

So:

>main
gto

continues interpreting instructions from the line which is referred to by the label :main (elsewhere in the code).

Please note: it could well be the case that :main appears later in the code. You will have to have all label definitions already stored somewhere beforehand, in order to be able to lookup the corresponding line numbers when the program is being interpreted.

This means it will be beneficial to build a two-pass interpreter. First time through the code to assemble all labels, second time to run the program.

geq

Goto if equal. Pop 3 values from the stack: first label value, then val2, and lastly val1. If val1 and val2 are equal, continue interpreting instructions from the line number represented by the label value. If they are not equal, simply continue with the next instruction.

So:

\hello
\there
>greeting
geq

The strings “hello” and “there” are not equal, so the next instruction will not be taken from the line number right after :greeting, but simply just from the line after the geq instruction.

Please note: this instruction performs a string comparison!

gne

Goto if not equal. Pop 3 values from the stack: first label value, then val2, and lastly val1. If val1 and val2 are not equal, continue taking instructions from the line number represented by the label value. Else, just continue with the next instruction.

So:

\hello
\there
>greeting
gne

will cause the program to continue from the line after the :greeting label, because the strings are not equal.

Please note: this instruction performs a string comparison!

glt

Goto if less. Pop 3 values from the stack: first label value, then val2, and lastly val1. Convert val1 and val2 to integer. If val1 is less than val2, continue by taking instructions from the line referred to by the label. Else, simply continue with the next instruction.

So:

2
3
>smaller
glt

2 is less than 3, so yes, the program continues from the line just after :smaller.

Please note: this instruction compares integers!

gle

Goto if less or equal. Pop 3 values from the stack: first label value, then val2, and lastly val1. Convert val1 and val2 to integer. If val1 is less than, or equal to val2, continue by taking instructions from the line referred to by the label. Else, simply continue with the next instruction.

So:

42
42
>here
gle

The two integers are equal, so the jump will be executed. We'll continue from the line after the :here label.

Please note: this instruction compares integers!

ggt

Goto if greater. Pop 3 values from the stack: first label value, then val2, and lastly val1. Convert val1 and val2 to integer. If val1 is greater than val2, continue by taking instructions from the line referred to by the label. Else, simply continue with the next instruction.

So:

10
37
>greater
ggt

10 is not greater than 37, so in this case we won't continue after the :greater label, but from the line right after the ggt instruction.

Please note: this instruction compares integers!

gge

Goto if greater or equal. Pop 3 values from the stack: first label value, then val2, and lastly val1. Convert val1 and val2 to integer. If val1 is greater than, or equal to val2, continue by taking instructions from the line referred to by the label. Else, simply continue with the next instruction.

So:

92
56
>this-place
gge

In this example, 92 is greater than 56, so the jump is carried out: we will continue from the line just after the :this-place label.

Please note: this instruction compares integers!

Functions

fun: Function. Store the line number of the next instruction on a separate stack (the call stack), and execute a gto.
ret: Return. Pop the last location from the call stack, and make sure that the next instruction is taken from that line.

Solution of this puzzle

end: End of search. The value on the stack is the secret message you are looking for! This instruction will only be present in the last program file you'll download.

Longer example

3 push 3 onto the stack
=cnt pop 3 from the stack and assign to cnt
\Hello, world push “Hello, world” onto the stack
enl append a newline to it
=hello assign the result to hello
\ push an empty string onto the stack
=result assign it to result
:loop define the next step as location loop
$result push result onto the stack
$hello push hello onto the stack
cat combine into a single string
=result assign it to result
$cnt push cnt onto the stack
dec subtract 1 from it
=cnt assign the result to cnt
$cnt push cnt onto the stack
0 push 0 onto the stack
>loop push location loop onto the stack
ggt if cnt > 0, go to loop, else continue
$result push result onto the stack — this is the end result

The end result is a 3 line string:

Hello, world
Hello, world
Hello, world

Tips

Don't be discouraged by the list of instructions you need to implement. It's less work than you think. Every instruction will be a short function with just a few lines of straightforward code.
Many of you will be tempted to apply a Command design pattern. That's perfectly fine, of course, but will give you more work than needed. Keep it simple! Just build an interpreter class which has the functions for every instruction.
A stack can be implemented easily with a std::vector ⁵. Use its methods push_back() and pop_back() to push and pop objects. Use back() to read the last value without popping it.
Consider adding a “out” instruction, which writes the last value on the stack to the standard output. This will come in handy when testing and debugging!
Keep the connection open until you're done with all requests. It will make your program significantly faster than when you would make a connection for every request, and close it afterwards, every time.
If you would like to be able to test your interpreter with locally stored Krul programs, add the possibility to read and run local files.
Allow comments in your Krul code, by interpreting all text from a literal “#” to end of line as a comment. POSIX users will then even be able to put a she-bang line at the top of their scripts:
```
#!/usr/bin/env krul
```
If you also make your script executable, you'll be able to run any such Krul script locally without any additional commands.
Finally, if you also add “err” and “in” instructions, for writing to standard error and reading from standard input, respectively, you have everything you need to make Krul command line scripts. This would also be good for writing your own (unit) tests!

The C++ Standard Library is of course allowed: we do not consider it an external library.↩︎
https://curl.haxx.se/libcurl/↩︎
https://en.wikipedia.org/wiki/Reverse_Polish_notation ↩︎
https://en.wikipedia.org/wiki/ROT13 ↩︎
https://en.cppreference.com/w/cpp/container/vector ↩︎

What are you going to build?

Requirements

HTTP GET requests with libcurl

The Krul interpreter

Design tip

Detailed description of the Krul language

Values & Types

Integer operations

String operations

Tests & Jumps

Functions

Solution of this puzzle

Longer example

Tips

HTTP GET requests with `libcurl`