Tags: coding 

Rating:

# Midnight Sun CTF 2020 Quals - Snake++
>###### tags: `coding`
>[email protected]
## Attachments
`nc snakeplusplus-01.play.midnightsunctf.se 55555`

## Challenge
There are two modes of snake game, for human and for AI.
When you select AI mode, the log file which is zipped and base64 encoded is given.
These are rules of snake game.
```
Instructions
------------

You are about to play a game of snake.
The snake can be controlled with 4 actions with the following keys:

'' (nothing, or just enter) Keep going
' ' (space) Fire
'L' Turn left
'R' Turn right

In the world, there are 2 types of items you can eat by colliding with them:

'A' Apple Grows snake by 1
'B' Bad apple Shrinks snake by 1

The snake can shoot at one of these apples to make it disappear. To do so, the
head of the snake must be facing the apple before you press Space.

If the snake collides with the world boundary, you lose.
If the snake reaches length 42, you win.

Good luck!

--- Press enter to continue ---
```
And snake AI is programmed by new language.
Below is a description of the syntax of this programming 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.
```

## Solution
### Algorithm
- My team member coded BFS using Snake Language, but it was caught by the time limit. After that, he advised me that I should make a heuristic algorithm.

- The algorithm that I thought was
![](https://i.imgur.com/B1GWdSZ.png)

1. snake goes up.
2. then hits the wall.
3. turn right.
4. move forward until it hits the right wall.
5. turn right and move forward until it hits the bottom wall.
6. turn right(therefore, looking to the left.).
7. Check if there is an apple on the vertical line.
1. if there is an apple(no matter it is bad or not), turn right.
2. else, move forward(then repeat step7).
8. while moving upward, check if the snake is facing an apple.
1. if it is facing good apple(A), eat it.
2. if it is facing bad apple(B), shoot it.
9. repeat!
- The problem occurs when bad apples are at the bottom. But it's just -1 so I just ignored it.

---
### Solver
#### python interact
This file interacts with snake game. You should run it in debug mode(because flag doesn't have "Result: ")!
```python:interact.py=
from pwn import *
from base64 import b64decode
import zipfile
from os import getcwd

p = remote("snakeplusplus-01.play.midnightsunctf.se",55555)

p.sendlineafter("Your choice: ","2");
for _ in range(2):
p.sendlineafter("--- Press enter to continue ---","");

with open("code.txt", "r") as file_code:
p.sendafter("Enter your program code, and end with a . on a line by itself\n",file_code.read())
p.sendlineafter("--- Press enter to start ---","");

p.recvuntil("Result: ")
data = p.recvline()
p.close()

with open("res.zip", "w") as res:
res.write(b64decode(data))

res_zip = zipfile.ZipFile(getcwd()+"/res.zip")
res_zip.extractall(getcwd())
res_zip.close()

with open("game.log", "r") as game_log:
print("game_log:")
print(game_log.read())

with open("program.log", "r") as program_log:
print("program_log:")
print(program_log.read())
```
#### my own snake
```=
banana ~<8=== blue yellow; #get snake's status
if yellow == 2 then #2, not 1
if banana == "^" then
logText "up";
return "R";
fi;
fi;
if blue == 27 then #27, not 28
if banana == ">" then
logText "right";
return "R";
fi;
fi;
if yellow == 17 then #17, not 18
if banana == "v" then
logText "down";
return "R";
fi;
fi;
if banana == "<" then
blue := blue - 1; #it must be blue-1 because snake is moving!
{loop}
yellow := yellow - 1; #check above
banana ~<8=== blue yellow;
if banana == "A" then #found
return "R"; #turn right
fi;
if banana == "B" then #found
return "R"; #turn right
fi;
if yellow == 1 then #not found
return ""; #keep moving to left side
fi;
slide {loop};
fi;
if banana == "^" then
red := yellow - 1;
banana ~<8=== blue red; #check in front of the snake
logText banana;
if banana == "B" then
return " ";
fi;
fi;

return "";
.
```

output : `midnight{Forbidden_fruit_is_tasty}`

Original writeup (https://hackmd.io/@whysw/BJk69qeO8).