The grandprix challenges requires us to connect to a server where we can play an ascii game. According to the assignment text, we are advised to avoid the zebras.
Let’s check out the game first using netcat:
$ nc grandprix.shallweplayaga.me 2038 nc: using stream socket Use 'l' and 'r' to move. Don't crash. Press return to start |-----| | | | | | | | | | | | | | | | | | u | |-----|
The games starts with an empty field. Obviously, our position is indicated by an u. We fiddle around a little to learn how the game works. Sending an r moves the player one step right, a l one left and a s or an empty line moves the player straight forward.
r |-----| | | | | | | | | | | | | | | | | | u | |-----|
The more we move along, the more obstacles appear. A T marks a tree and the Zebras we were warned about are indicated by a Z.
The game requires us to act fast. If we think too long what the best move might be, we get an timeout.
|-----| | | | | | Z | | T | | | | Z | | Z | | | | u | |-----| Too slow!
On the other hand, if we do not take moment to make a wise move, we might crash into objects. This is what happens if we hit one of the said-to-be dangerous Zebras.
|-----| | | | | | | | | | Z | | T | | | | Z | | u | |-----| You hit a big zebra User lost game
Ouch!
So, the challenge is clear now. We have to play probably a lot of rounds in a fast an efficient way. Good luck we know someone who is good at repeatedly making simple decisions without getting bored: The computer!
Our little program shall use a tree containing all possible moves. A classic binary tree is of the table since we can make up to three moves at each position (left, straight, right). Our tree has to reflect this requirement. So we define a node as follows:
struct node {
char d;
int y;
int x;
struct node *s;
struct node *l;
struct node *r;
};
We also need a few helper functions to build and free the tree. Every time the server sends a new game board, we parse the board and build a new tree.
static void build_tree (struct node *nd); static struct node *make_node(int y, int x); static char getyx(int y, int x); static struct node *free_tree(struct node *nd);
The heart of our program is a function that finds the best way through the board. It prefers going straight forward, just like any sober human being would in the presence of dangerous Zebras:
int walk_tree (struct node *nd)
{
printf("%c", nd->d);
if (nd->d != ' ')
return NO_WAY;
if (nd->y == 1)
return OK;
if (nd->s && walk_tree(nd->s) == OK)
return OK;
if (nd->l && walk_tree(nd->l) == OK)
return OK;
if (nd->r && walk_tree(nd->r) == OK)
return OK;
return NO_WAY;
}
char find_way (struct node *nd)
{
if (nd->s && walk_tree(nd->s) == OK)
return 's';
if (nd->l && walk_tree(nd->l) == OK)
return 'l';
if (nd->r && walk_tree(nd->r) == OK)
return 'r';
return 's';
}
Now we can run our program until it receives a flag from the server. It takes a while and it helps to use a server with a fast pipe to run the code. Recognized obstacles are printed after the round number and the last character in each line shows the direction the player should move:
round 1: ->s round 2: ->s round 3: ->s round 4: Z~ ->s round 5: Z~ ->s round 6: Z~ r ->s [...] round 1041: ->s You won this game. Push a key to play again User won game The key is: all our prix belong to you
That’s it!
The key is: all our prix belong to you
Grab the source here: https://gist.github.com/danrl/5794505