The goal of this puzzle is to write the artificial intelligence for the popular snake game.

Game rules

• when the snake eats an apple, it grows by one unit
• eaten apples will reappear in the same place once the snake is not over them anymore.
• the snake starts in the left corner, its length is 3 cases, its tail is in position (1,0), its body is in position (0,0) and its head is in position (0,1). The positions are expressed (row number, column number).
• the game ends when the snake bites itself or hits a wall
• each apple eaten adds 100 points to the score
• each move made substracts 1 point from the score

You can find a demo illustrating this game here

Input Specifications

Your program must take a single command line argument: the name of a file.
The input file is structured as follows:

1. the first line contains r c, two integeres representing the number of rows and columns
2. the r following lines contain the game board definition, a game board line is composed of
   1. '.' character which represents a space
   2. '+' character which represents an apple
   3. '#' character which represents a wall

Example:

6 9
.........
..##+##..
.+.......
.......+.
..##+##..
.........

Output Specifications

The output result should printed on the standard output. It will contain all the moves you have made, a move is represented by one of the 4 following letters:

• u (up)
• d (down)
• l (left)
• r (right)

Only the first 10000 moves count, any additional moves will be ignored.

For the previous example, a possible output is:

rrrddllluurrrddllluurrrddllluurrrddrrrdlllllluuurrrddrrrdlllllluuurrrddrrrdlllddllluuuuurrrddrrrdlllddlllluruuuurrrddrrrurddllllddlllluruuuurrrddrrruurdddllllddlllluruluruurrrddrrruurdddddluulllddllllurulurulurrrrddrrruurdddddluulllddllllururrulllururrrddrrruurdddddluu

This output has a score of 3531. There can be better solutions and obviously worse ones too.

Scoring

100 points is added to your score for each apple eaten, 1 point is substracted from the score for each move made.

Demonstration

Rules: Use the left, right, up and down keys to move the snake. The game ends when the snake hits a # or bites itself. Each move substracts 1 point from the score, each + adds 100 points.

You can also use this as simulator of your solution by entering your list of moves in the move list text area and click on replay moves. You can even edit the board to enter your own board.