Midnightsun CTF 2020

Snake++

Snake++

Snake Oil Co. has invented a special programming language to play their new and improved version of Snake. Beat the game to get the flag.

nc snakeplusplus-01.play.midnightsunctf.se 55555

Connecting to the remote server, we are greeted by a menu asking us to pick either playing as a human or a computer.

Chosing the human option, we find out that the game is a relatively normal version of Snake, but with a small twist: There are 2 different types of apples. A and B. Collecting an A-apple increases your score and length, while collecting a B-apple reduces it. Shooting a B-apple will make it disappear. Shooting an A-apple will also make it disappear, but you don't receive any points. So, you have to collect As while shooting Bs.

The commands are accepted one after another. Legal commands are "L" and "R" for turning the snake, "[Space]" to shoot and "[Empty]" to skip and just move the snake forward.

The goal of the game is to reach a score of 42.

Beating the game in human-mode predicatbly does not yeild the flag. Instead we get a prompt to automate the game using their speical purpose programming language.

No dice

The progamming language

Snake++ Programming Language
============================

Using the Snake++ programming language, you can analyze the snake's environment
and calculate its next move, just like in the regular game.

Registers and memory
--------------------

Snake++ operates on 8 registers and 3 memory areas.  We distinguish between
text and numbers. 

There are 4 registers than can hold text, named: apple, banana, cherry and
date.  There are 4 registers that can hold numbers, named: red, green, blue and
yellow.

All 3 memory areas are 30 by 20 cells in size (just like the map of the world).
There is one RW memory area for text (TEXTRAM), and one for numbers (NUMRAM).
There is also one readonly memory area for text (TEXTROM).

Comments
--------

Any line starting with the '#' character is ignored.

Loading, storing and assigning
------------------------------

The following operators allow loading from and storing into memory:

Loading from RAM: <register> ~<8~~~ <x> <y>;
Storing into RAM: <register> ~~~8>~ <x> <y>;
Loading from ROM: <register> ~<8=== <x> <y>;

Note that there is no operator to store into ROM.  The memory area is
automatically selected based on the register and the operator.  For instance,
to load a number from NUMRAM row 7, column 5 into the blue register:

	blue ~<8~~~ 5 7;

Likewise, to store a text from the apple register into TEXTRAM row 0, column
12:

	apple ~~~8>~ 12 0;

Finally, since there is only ROM for text data:

	banana ~<8=== 5 6;

Values can also be assigned to registers using the := operator:

	blue := 5;
	cherry := "abc";

Arithmetic
----------

The following arithmetic operations are defined on numbers: + - / *
And for text, only + is defined.
Formulas can be enclosed in parentheses.

e.g.:
	blue ~<8~~~ (red+6) (green/2);
	red := blue + green * 2;
	banana := cherry + "x" + date;

Statements
----------

A program in Snake++ consists of a sequence of statements, each ending with a
semicolon.  Each of the load, store and assignment operations described above
are statements.  There are also statements for logging numbers and text (log
and logText respectively), returning a value to the game, if-then-else
branching and sliding to a label.

Logging Statements
------------------

to log the value of the blue register + 3:

	log blue+3;

to log the banana text register:

	logText banana;

Return Statement
----------------

Returning a text value will end the Snake++ program and hand control back to
the Snake game in progress.  The returned value can be used to control the
snake, and should be "", " ", "L" or "R". (See game instructions).  Only text
values can be returned.

example:
	return "R";


If-Then-Else Statement
----------------------

Works as you'd expect:

if <condition> then <sequence of statements> fi;
if <condition> then <sequence of statements> else <sequence of statements> fi;

Of note is the condition. It is possible to compare numbers to numbers, or text
to text.

For numbers, the operators are: ==, <>, >, >=, <, <=
For text, the operators are: == and <>
In each case, <> means "does not equal".

Example:

	if blue < yellow-3 then 
		logText "Looking good"; 
	else 
		logText "This is not good";
		blue := yellow - 3;
	fi;


Labels and Slide Statement
--------------------------

It is possible to label a statement by placing a label in front of it.
Labels are sequences of characters enclosed with curly braces.
For instance, the following statement is labeled {example}:
	{example} blue := 5;

During execution, it is possible to slide over from the current statement to
another labeled statement.

Example:

	green := 0;
	{loop}
		green := green + 1;
		if green < 10 then
			log green;
			slide {loop};
		fi;

Caution: it is only possible to slide to a labeled statement in the same or the
encompassing codeblock.

Program execution
-----------------

The execution environment for your Snake++ program is kept alive during the
entire game.  Before the game moves the snake, it will execute your (entire)
Snake++ program to determine what to do.  You should use the return statement
to return one of "", " ", "R" or "L".

For each execution of your program, only the TEXTROM and registers will be
altered.  TEXTROM will contain the worldmap, as also seen when playing the game
as a human.  All registers are wiped. The coordinates of the head of the snake
are placed in the blue (X-coordinate) and yellow (Y-coordinate) registers.

High level ideas

My idea to solve this with as little work as possible was as follows:

Determine a path across the whole map that visits each square exactly once, and loops back on itself, known as a Hamiltonian path.

No dice

This ensures the snake never runs into a wall, or itself.

To account for the bad apples, before taking a step, I check if the field I'm about to land on has a "B" on it. If so, I shoot. Otherwise, I just take a step.

This is all that's required to solve the game, provided we are allowed enough execution time to run such an inefficient solution. Turns out, we are.

The code

#x
log blue;
#y
log yellow;
# own position
date ~<8=== blue yellow;
logText date;


#if I'm on a turn square, turn. else, do nothing (maybe shoot?)
#Am i on the bottom right?
if blue==28 then
    if yellow==17 then
        return "R";
    fi;
else
    if blue==2 then
        if yellow==18 then
            return "R";
        else
            if yellow==2 then
                # on the way up?
                if date == "^" then
                    return "R";
                fi;
            fi;
            if yellow==1 then
                if date == ">" then
                    return "R";
                fi;
            fi;
            if yellow==16 then
                if date == "v" then
                    return "L";
                fi;
            fi;
            if yellow==17 then
                if date == ">" then
                    return "L";
                fi;
            fi;
        fi;
    else
        if yellow==2 then
            # on the way up?
            if date == "^" then
                return "R";
            fi;
        fi;
        if yellow==1 then
            if date == ">" then
                return "R";
            fi;
        fi;
        if yellow==16 then
            if date == "v" then
                return "L";
            fi;
        fi;
        if yellow==17 then
            if date == ">" then
                return "L";
            fi;
        fi;
    fi;
fi;
# check if B is around us...
apple := "";
if date=="^" then
    apple ~<8=== blue yellow-1;
fi;
    
if date=="v" then
    apple ~<8=== blue yellow+1;
fi;

if apple =="B" then
    return " ";
fi;
return "";

The code takes around 20 seconds to execute. After that, we receive the following message:

A job well done using our proprietary programming language!
Here is something for your effort: midnight{Forbidden_fruit_is_tasty}