Prologin 2013 artificial intelligence in brainfuck
Here is a bot I wrote for the final of Prologin, the French national contest in Computer Science. Note that, this was (badly) hacked in less than 24 hours.
You can find the problem statement here (pdf in French). Basically, you had to write an artificial intelligence for a game where you can buy two kind of boats, one to attack other boats and the other to settle island which produce gold.
jouer_tour
static char const * const program=R"BRAINFUCK_WHAT( > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > [^ - ] > [^ - ] + + + + + + + + + + + [ - < + + + + + + + + + + > ] < - . - - - - - - - - . + + + + + + + + + + + + + + . - - - - - - - - - - - - - - - - - - - - . + + + + + + + + + + . + + + . - - - - - - - . + + + + + + + + + + + + + + . [^ - ] [^ - ] + + + + + + + + + + . [ - < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < - . + + + + + + + + + + + + . - . + + + + + . + . - - . + + + . - - - - - - - - - - - - . + + + + + + + + + . - - - - - - - - - - - - - . [^ - ] < , < , [ > + < - ] > [ [^ - ] > > + < < ] > [^ - ] + + + + + + + + + + . [^ - ] > [^ - ] > [^ - ] > [^ - ] > ] [^ - ] > [^ - ] + + + + + + + + [ - < + + + + + + + + + + > ] < + + + + . - - - - - - - - - - - - - - - - - - - . + + + + + + + + . + + + . . - - - - - - - . + + + + + + + + + + + + + + + + + + + + + + + + + + . - - - - - - - - - - - . - - - - - - - - - - - - - - - . + + + + + + + + + + + + + . . - - - - - - - - - - - - - - - - - . + + + + + + + + . + + + + + . [^ - ] [^ - ] + + + + + + + + + + . [ - > [^ - ] > [^ - ] + + + + + + + + [ - < + + + + + + + + + + > ] < + + + + . - - - - - - - - - - - - - - - - - - - . + + + + + + + + . + + + . . - - - - - - - . + + + + + + + + + + + + + + + + + + + + + + + + + + . - - - - - - - - - - - . - - - - - - - - - - - - - - - . + + + + + + + + + + + + + . . - - - - - - - - - - - - - - - - - . + + + + + + + + . + + + + + . [^ - ] [^ - ] + + + + + + + + + + . [ - < [ - > > > > > > > > > > > + > + < < < < < < < < < < < < ] > > > > > > > > > > > [ - < < < < < < < < < < < + > > > > > > > > > > > ] < < < < < < < < < < < > [ - > > > > > > > > > > + > > + < < < < < < < < < < < < ] > > > > > > > > > > [ - < < < < < < < < < < + > > > > > > > > > > ] < < < < < < < < < - > > > > > > > > > < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < + + + + + + + + . - - - . + + + + + + + + + + . + . - - - - - - - - - - - - - - - . - - - - - - . + + + . - . + + + + + + + + + + + + + + + + + + + . - - - - - - - - - - - - - - - . - - - - . + + + + + + + + + + + + + + + + + + + + . + + + . - - - - - - - - - - - - - - - - - - - - - - - - - . + + + + + + + + + + + + + + + + + . - . + + + + . - - - - - - - - - - . + + + + + + + + + + + . - - - - - - - - - - - . + + + + + + . - . [^ - ] > [^ - ] + + + + + + + + + + . [ - > [&1 - < + > ] < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*1 - > + < ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > [&2 - < < + > > ] < < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*2 - > > + < < ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > > [&3 - < < < + > > > ] < < < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*3 - > > > + < < < ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > > > [&4 - < < < < + > > > > ] < < < < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*4 - > > > > + < < < < ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > > > > [&5 - < < < < < + > > > > > ] < < < < < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*5 - > > > > > + < < < < < ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > > > > > [&6 - < < < < < < + > > > > > > ] < < < < < < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*6 - > > > > > > + < < < < < < ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > > > > > > [&7 - < < < < < < < + > > > > > > > ] < < < < < < < > > > > > > > > [ - < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > > > > > > > > > ] < < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] + > > > > > > > > [*7 - > > > > > > > + < < < < < < < ] - > > > > [^ - ] > > [^ - ] > [^ - ] < < < < < [ - > > + > > > > > + < < < < < < < ] > > [&2 - < < + > > ] < [ - > + > > > > > > + < < < < < < < ] > [&1 - < + > ] > > > > < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < - . + + + + + + + + + + + + . - - - . + + + . - . - - - - - . + + + + + + + + + + . - - - - - - - - - - - - - - . + + + + + + + + + + + + + . [^ - ] > [^ - ] + + + + + + + + + + . [^ - ] > [^ - ] > [^ - ] < < < < < > > > > [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < + + + + + + + + . - - - . + + + + + + + + + + . + . - - - - - - - - - - - - - - - . - - - - - - . + + + + + + + + + + . + + + . - - - - - - - . + + + + + + + + + + + + + + . [^ - ] [^ - ] + + + + + + + + + + . [ - < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < + + + + + . + + + + + . - - - - - - - - . + + + + + + + + + . - - - - - - - - - - - - - - - - . + + + + + + + + + + . + + + . - - - - - - - . - - - - - - . + + + + + + + + + + + . + + + + + . + + + + + + . - - - - - - - - - - - - - - - - . + + + + + + + + + + + + + + + + . - - - . [^ - ] > [^ - ] + + + + + + + + + + . [ < , [ - > + < < < < [ - > + > + < < ] > [&1 - < + > ] > > + + < [ - > - - < ] > > [ - < - > ] < [ [^ - ] < < < [^ - ] > > > < < < < < < < [*8 - > > > > > > > > + < < < < < < < < ] > > > > > > > < < < < < < [ - > > + > + < < < ] > > [&2 - < < + > > ] < [ - > + > > + < < < ] > [&1 - < + > ] > > > > < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < . + . + + + + + + + + + + + . - - - - . - - - - - - - - - - - . + + . + + . + + + + + + + + + + + + + . [^ - ] > [^ - ] + + + + + + + + + + . [^ - ] < < < < < < [ - > > > > > > > > + < < < < < < < < ] > [ - > > > > > > > > + < < < < < < < < ] > > > > > > > {D2 [ < < < + > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > - < < [^ - ] ] + < < < < - ] > > > > - ] > > + < < < ] > > > } > {D2 [ < < < < + > > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > > - < < < [^ - ] ] + < < < < - ] > > > > - ] > > > + < < < < ] > > > } < < < < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < . + . + + + + + + + + + + + . - - - - . - - - - - - - - - - - . + + . + + . + + + + + + + + + + + + + . [^ - ] > [^ - ] + + + + + + + + + + . [^ - ] < < < [ - < + > > > > > > + < < < < < ] < [*1 - > + < ] > > [ - > + > > > > + < < < < < ] > [&1 - < + > ] > > > {D2 [ < < < + > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > - < < [^ - ] ] + < < < < - ] > > > > - ] > > + < < < ] > > > } > {D2 [ < < < < + > > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > > - < < < [^ - ] ] + < < < < - ] > > > > - ] > > > + < < < < ] > > > } < < < < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < . + . + + + + + + + + + + + . - - - - . - - - - - - - - - - - . + + . + + . + + + + + + + + + + + + + . [^ - ] > [^ - ] + + + + + + + + + + . [^ - ] < < < [ - < + > > > > > > + < < < < < ] < [*1 - > + < ] > > [ - > + > > > > + < < < < < ] > [&1 - < + > ] > > > {D2 [ < < < + > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > - < < [^ - ] ] + < < < < - ] > > > > - ] > > + < < < ] > > > } > {D2 [ < < < < + > > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > > - < < < [^ - ] ] + < < < < - ] > > > > - ] > > > + < < < < ] > > > } < < < < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < . + . + + + + + + + + + + + . - - - - . - - - - - - - - - - - . + + . + + . + + + + + + + + + + + + + . [^ - ] > [^ - ] + + + + + + + + + + . [^ - ] < < < [ - < + > > > > > > + < < < < < ] < [*1 - > + < ] > > [ - > + > > > > + < < < < < ] > [&1 - < + > ] > > > {D2 [ < < < + > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > - < < [^ - ] ] + < < < < - ] > > > > - ] > > + < < < ] > > > } > {D2 [ < < < < + > > > > - ] < < < [ > + + [ < < < < + > > > - [ < < < [^ - ] < + > > > > - ] < < < < [*4 > > > > + < < < < - ] > [ > > > > - [ > > > - < < < [^ - ] ] + < < < < - ] > > > > - ] > > > + < < < < ] > > > } < < < < [^ - ] > [^ - ] + + + + + + + + + + [ - < + + + + + + + + + + > ] < . + . + + + + + + + + + + + . - - - - . - - - - - - - - - - - . + + . + + . + + + + + + + + + + + + + . [^ - ] > [^ - ] + + + + + + + + + + . [^ - ] > [^ - ] > [^ - ] > [^ - ] > [ [^ - ] > [^ - ] > [^ - ] > ] > > ] ] > ] > [^ - ] > [^ - ] > < < < < < < < [*3 - > > > + < < < ] < < [*3 - > > > + < < < ] < [*3 - > > > + < < < ] < [*3 - > > > + < < < ] > > > > > > > > > > > ] + [ - < < < + ] < < < < < < < < [ < < < < < < < < ] > > > > > > > > - > > > > > > > > ] < + [ - < < < < < < < < + ] > > > > > > > > > > [^ - ] > [^ - ] < < < < < < < < < < < < ] < ])BRAINFUCK_WHAT";
This is the brainfuck program in itself, as you can see it is written inside a C++11 raw string literal, indeed I had to write the interface to the server (Stechec2) myself (strangely enough, there wasn't a brainfuck interface already written).
The algorithm I implemented is simple:
- For each island on the map
- Build a "galion" (attack boat) with a probability of 3/4, a "caravel" (settler boat) otherwise
- For each cell on the map
- List the boats on this cell
- For each boat
- Colonise at his position
- List the island on the map
- For each island
- If it is mine, continue
- continue with a probability of 1/2
- If (the boat is a galion and the island is owned by the enemy) or (the boat is a caravel and the island is neutral)
- Let (fy, fx) be the position of the boat and (ty, tx) be the position of the island
- Repeat 5 times
- Move the boat to (ty, tx)
- (ty, tx)=((ty+fy)/2, (tx+fx)/2)
Note that I do not test whether I own the boats before moving them, it's not important, the server returns a non-fatal error when a non-owned boat is moved, and I ignore the error code returned. For multi-turn moves, I try to move the boat on the island itself, then half-way through, then quarter-way through, etc… the boat will move to the first reachable cell and the server will return errors for the subsequent moves.
Also, this artificial stupidity will tend to move to the first islands in the order returned by the server, in practice it was penalised by starting on the lower right corner (the island where returned in a left-to-right top-to-bottom order).
There is some optimisations in the code, the goal was to speed up the execution of brainfuck, without these optimisations, the code would still run but much slower:
- [*n >n+<n-] move the cell n cases towards the right (the loop is not executed)
- [&n <n+>n-] move the cell n cases towards the left
- [^-] reset the cell
- {D2 a lot of code} divide by two
Some brainfuck extension used to debug the code:
- % display on stderr the index and value of the current cell
- $ display on stderr the remaining of the line
To improve the readability (and writability) of brainfuck, I use cpp (the C preprocessor), so I used (and abused) #define and #include. The call to function of the API was done by writing their name to stdout (followed by a newline), so I have a lot of #define in the file call_function.bf for doing that. On the other hand, passing parameters and reading the return value was done directly into brainfuck memory (if you are looking for a cheat in the code, this is it), stdin was filled with std::rand().
So here is the code as I wrote it :
jouer_tour.bf
#include "call_function.bf" #include "structure.bf" $ =========================== $ =========================== $ ========== DEBUT ========== $ =========================== $ =========================== >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> $ ===================================== $ = Debut de la phase de construction = $ ===================================== MES_ILES_2 CALL_1 [ Pour chaque ile - clear flag < CONSTRUIRE_2 HERE 0* | 0 | y | x <,<,[>+<-]> un bateau au hasrd (3/4 galion /// 1/4 caravelle) HERE r*| 0 | 0 | y | x [[-]>>+<<] > CALL_1 [^-]>[^-]>[^-]>[^-]> ] $ ============================================ $ = Debut de la phase d assignation de tache = $ ============================================ FOREACH_CELL_7 <<<<<<<<<->>>>>>>>> HERE y | x | m1| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |*0 | y | x < LISTE_BATEAUX_POSITION_2 > CALL_1 [ Pour chaque bateau sur la case #define DEPLACER_FLAG_END \ >>>>>>>>[ deplacement en fin \ - mise a zero du flag \ <<<<<<<<[*8 ->>>>>>>>+<<<<<<<<] \ + remise du flag \ >>>>>>>>>>>>>>>> \ ] \ <<<<<<<< deplacement de end m 1 en end \ [*8 ->>>>>>>>+<<<<<<<<] \ +>>>>>>>> - mise a zero du flag >[&1 -<+>]< copy id DEPLACER_FLAG_END [*1 ->+<] Retour <<<<<<<< [<<<<<<<<] >>>>>>>> - mise a zero du flag >>[&2 -<<+>>]<< copy posy DEPLACER_FLAG_END [*2 ->>+<<] Retour <<<<<<<< [<<<<<<<<] >>>>>>>> - mise a zero du flag >>>[&3 -<<<+>>>]<<< copy posx DEPLACER_FLAG_END [*3 ->>>+<<<] Retour <<<<<<<< [<<<<<<<<] >>>>>>>> - mise a zero du flag >>>>[&4 -<<<<+>>>>]<<<< copy joueur DEPLACER_FLAG_END [*4 ->>>>+<<<<] Retour <<<<<<<< [<<<<<<<<] >>>>>>>> - mise a zero du flag >>>>>[&5 -<<<<<+>>>>>]<<<<< copy btype DEPLACER_FLAG_END [*5 ->>>>>+<<<<<] Retour <<<<<<<< [<<<<<<<<] >>>>>>>> - mise a zero du flag >>>>>>[&6 -<<<<<<+>>>>>>]<<<<<< copy or DEPLACER_FLAG_END [*6 ->>>>>>+<<<<<<] Retour <<<<<<<< [<<<<<<<<] >>>>>>>> - mise a zero du flag >>>>>>>[&7 -<<<<<<<+>>>>>>>]<<<<<<< copy deplacable DEPLACER_FLAG_END [*7 ->>>>>>>+<<<<<<<] HERE : 1 | end id | end py | eetc | eetc | eetc | eetc | eetc | 0*| id | py | px | etc $ I HAVE A BOAT >%< $ IS NAME - BATEAU CELL: m1*| id | posy | posx | joueur | type | or | deplacable >>>>[^-]>>[^-]>[^-]<< HERE: m1| id | posy | posx | 0 | type*| 000 <<< [->>+>>>>>+<<<<<<<] >>[&2 -<<+>>] < [->+>>>>>>+<<<<<<<] >[&1 -<+>] >>>> HERE: m1| id | posy | posx | 0 | type | 0 | 0 | 0*| posy | posx < COLONISER_2 > CALL_1 [^-]>[^-]>[^-] <<<<< HERE: m1| id | posy | posx | 0 | type*| 0000 >>>> HERE: m1| id | posy | posx | 0 | type | 0 | 0 | 0 |*0 LISTE_ILES_2 CALL_1 [ Pour toute ile $ => I HAVE AN ISLAND >%>%<< $ IS NAME - mise du flag a zero HERE id | fy | fx | 0 | type | 0 | 0 | 0 | 0*| ty | tx < INFO_ILE_JOUEUR_2 > CALL_1 HERE 0 | j*| y | x [<,[- >+< HERE id | fy | fx | 0 | type | 0 | 0 | 0*| j | ty | tx <<<[->+>+<<] >[&1 -<+>] >> HERE id | fy | fx | 0 | type | 0 | type | 0*| j | ty | tx ++<[->--<]>>[-<->]< j = 0 and type=0 ok j = 0 and type=1 fail j = 2 and type=1 ok j = 2 and type=0 fail 2 m 2*type m j HERE id | fy | fx | 0 | type | 0 | 0 | ok?*| 0 | ty | tx [ [^-] <<<[^-]>>> CLEAN type <<<<<<<[*8 ->>>>>>>>+<<<<<<<<] >>>>>>> HERE 0 | fy | fx | 0 | 0 | 0 | 0 | 0*| id | ty | tx <<<<<<[->>+>+<<<] >>[&2 -<<+>>]< HERE 0 | fy | fx*| 0 | fy | 0 | 0 | 0*| id | ty | tx [->+>>+<<<] >[&1 -<+>] >>>> HERE 0 | fy | fx | 0 | fy | fx | 0 | 0*| id | ty | tx < DEPLACER_2 > CALL_1 [^-] #define DIVIDE_TFY_BY_TWO \ {D2 \ x[<<<t0+>>>x-] \ <<<t0[>++y[ \ <<<<t1+ \ >>>t0-[<<<t1[^-]<t2+>>>>t0-] \ <<<<t2[*4 >>>>t0+<<<<t2-] \ >t1[>>>>y-[>>x-<<y[^-]]+<<<<t1-] \ >>>>y-]>>x+<<<t0]>>> \ } #define DIVIDE_TFX_BY_TWO \ {D2 \ x[<<<<t0+>>>>x-] \ <<<t0[>++y[ \ <<<<t1+ \ >>>t0-[<<<t1[^-]<t2+>>>>t0-] \ <<<<t2[*4 >>>>t0+<<<<t2-] \ >t1[>>>>y-[>>>x-<<<y[^-]]+<<<<t1-] \ >>>>y-]>>>x+<<<<t0]>>> \ } <<<<<<[->>>>>>>>+<<<<<<<<] >[->>>>>>>>+<<<<<<<<] >>>>>>> HERE 0 | 0 | 0 | 0 | fy | fx | 0 | 0 | id | tfy*| tfx DIVIDE_TFY_BY_TWO > DIVIDE_TFX_BY_TWO <<< HERE 0 | 0 | 0 | 0 | fy | fx | 0 | 0*| id | tfy | tfx < DEPLACER_2 > CALL_1 [^-] HERE 0 | 0 | 0 | 0 | fy | fx | 0 | 0*| id | tfy | tfx <<<[-<+>>>>>>+<<<<<]<[*1 ->+<] >>[->+>>>>+<<<<<]>[&1 -<+>]> >> DIVIDE_TFY_BY_TWO > DIVIDE_TFX_BY_TWO <<< < DEPLACER_2 > CALL_1 [^-] HERE 0 | 0 | 0 | 0 | fy | fx | 0 | 0*| id | tfy | tfx <<<[-<+>>>>>>+<<<<<]<[*1 ->+<] >>[->+>>>>+<<<<<]>[&1 -<+>]> >> DIVIDE_TFY_BY_TWO > DIVIDE_TFX_BY_TWO <<< < DEPLACER_2 > CALL_1 [^-] HERE 0 | 0 | 0 | 0 | fy | fx | 0 | 0*| id | tfy | tfx <<<[-<+>>>>>>+<<<<<]<[*1 ->+<] >>[->+>>>>+<<<<<]>[&1 -<+>]> >> DIVIDE_TFY_BY_TWO > DIVIDE_TFX_BY_TWO <<< < DEPLACER_2 > CALL_1 [^-] >[^-]>[^-]>[^-] > [ CLEAN [^-]>[^-]>[^-]> ] >> ] ]>] >[^-]>[^-]> HERE id | fy | fx | 0 | type | 0 | 0 | 0 | 0 | 0 | 0 | ?* | y | x <<<<<<<[*3->>>+<<<] <<[*3->>>+<<<] <[*3->>>+<<<] <[*3->>>+<<<] >>>>>>>>>>> HERE id | fy | fx | 0 | type | 0 | 0 | 0 | ?*| ty | tx $ END OF ISLAND LOOP % ] fin pour toute ile +[-<<<+] HERE : 1 | end id | end py | eetc | eetc | eetc | eetc | eetc | 0*| 0 $ MY BOAT IS GONE :( Retour <<<<<<<< [<<<<<<<<] >>>>>>>> ->>>>>>>> ] fin pour chaque bateau <+[-<<<<<<<<+] >>>>>>>>> END_FOREACH_CELL_7 $ ========================= $ ========================= $ ========== FIN ========== $ ========================= $ =========================
structure.bf
#define FOREACH_CELL_7 \ TAILLE_TERRAIN_2 \ CALL_1 \ [-> \ TAILLE_TERRAIN_2 \ CALL_1 \ [- \ < \ HERE *y | x \ [->>>>>>>>>>>+>+<<<<<<<<<<<<] \ HERE *0 | x | 0 ||||| y | y \ >>>>>>>>>>>[-<<<<<<<<<<<+>>>>>>>>>>>] \ <<<<<<<<<<< \ HERE *y | x | 0 ||||| 0 | y \ >[->>>>>>>>>>+>>+<<<<<<<<<<<<] \ HERE y |*0 | 0 ||||| x | y | x \ >>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>] \ HERE y | x | 0 |||||*0 | y | x #define END_FOREACH_CELL_7 \ >[^-]>[^-]<<<<<<<<<<<< \ ] \ <]
call_function.bf
#define CALL_1 \ [^-]++++++++++. #define MES_ILES_2 \ [^-]>[^-]+++++++++++[-<++++++++++>]<-. \ --------. \ ++++++++++++++. \ --------------------. \ ++++++++++. \ +++. \ -------. \ ++++++++++++++.[^-] #define CONSTRUIRE_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<-. \ ++++++++++++. \ -. \ +++++. \ +. \ --. \ +++. \ ------------. \ +++++++++. \ -------------.[^-] #define INFO_ILE_JOUEUR_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<+++++. \ +++++. \ --------. \ +++++++++. \ ----------------. \ ++++++++++. \ +++. \ -------. \ ------. \ +++++++++++. \ +++++. \ ++++++. \ ----------------. \ ++++++++++++++++. \ ---.[^-] #define TAILLE_TERRAIN_2 \ [^-]>[^-]++++++++[-<++++++++++>]<++++. \ -------------------. \ ++++++++. \ +++. \ . \ -------. \ ++++++++++++++++++++++++++. \ -----------. \ ---------------. \ +++++++++++++. \ . \ -----------------. \ ++++++++. \ +++++.[^-] #define LISTE_ID_BATEAUX_POSITION_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<++++++++. \ ---. \ ++++++++++. \ +. \ ---------------. \ ------. \ ++++++++++. \ -----. \ -----. \ +++. \ -. \ +++++++++++++++++++. \ ---------------. \ ----. \ ++++++++++++++++++++. \ +++. \ -------------------------. \ +++++++++++++++++. \ -. \ ++++. \ ----------. \ +++++++++++. \ -----------. \ ++++++. \ -.[^-] #define LISTE_BATEAUX_POSITION_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<++++++++. \ ---. \ ++++++++++. \ +. \ ---------------. \ ------. \ +++. \ -. \ +++++++++++++++++++. \ ---------------. \ ----. \ ++++++++++++++++++++. \ +++. \ -------------------------. \ +++++++++++++++++. \ -. \ ++++. \ ----------. \ +++++++++++. \ -----------. \ ++++++. \ -.[^-] #define DEPLACER_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<. \ +. \ +++++++++++. \ ----. \ -----------. \ ++. \ ++. \ +++++++++++++.[^-] #define LISTE_ILES_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<++++++++. \ ---. \ ++++++++++. \ +. \ ---------------. \ ------. \ ++++++++++. \ +++. \ -------. \ ++++++++++++++.[^-] #define COLONISER_2 \ [^-]>[^-]++++++++++[-<++++++++++>]<-. \ ++++++++++++. \ ---. \ +++. \ -. \ -----. \ ++++++++++. \ --------------. \ +++++++++++++.[^-]
The interpreter being:
prologin.cc
/// // This file has been generated, if you wish to // modify it in a permanent way, please refer // to the script file : gen/generator_cxx.rb // #include "prologin.hh" #include "jouer_tour" #include <fstream> #include <stdexcept> #include <iostream> #include <vector> #include <stack> #include <cstdlib> #include <cstring> void bf_exec(); void exec(std::string const &call, std::vector<int>::iterator mem); inline int conv_ply(int p){ if(p==-1) return -1; return p==adversaire(); } /// // Fonction appelée au début de la partie // void partie_init() { std::srand(42); } /// // Fonction appelée à chaque tour // void jouer_tour() { int exec_count=0; std::stack<char const *> stack; char const *end=program+std::strlen(program), *ip=program; std::vector<int> memory(4200); std::vector<int>::iterator mp=memory.begin(); std::string buf_out; while(ip!=end){ ++exec_count; switch(*ip){ case '<': --mp; break; case '>': ++mp; break; case '+': ++*mp; break; case '-': --*mp; break; case '[': if(exec_count>10000000){ std::cerr << "\nSTOP (TIMEOUT PREVENTION) with " << exec_count << "exec\n"; return; } if(*(ip+1)=='^'){ // optimisation *mp=0; while(*ip!=']') ++ip; } else if(*(ip+1)=='*'){ // optimisation *(mp+*(ip+2)-'0')=*mp; *mp=0; while(*ip!=']') ++ip; } else if(*(ip+1)=='&'){ // optimisation *(mp-*(ip+2)+'0')=*mp; *mp=0; while(*ip!=']') ++ip; } else if(*mp) stack.push(ip); else{ std::size_t c=1; while(c){ ++ip; if(*ip=='[') ++c; else if(*ip==']') --c; } } break; case ']': if(*mp) ip=stack.top(); else stack.pop(); break; case '.': if(*mp=='\n'){ exec(buf_out, mp); buf_out.clear(); } else buf_out+=static_cast<char>(*mp); break; case '%': //std::cerr << "[@" << (mp-memory.begin()) << "] " << *mp << std::endl; break; case ',': *mp=std::rand()&1; break; case '$': while(*ip!='\n'){ /*std::cerr << *ip;*/ ++ip; } //std::cerr << std::endl; break; case '{': if(*(ip+1)=='D' && *(ip+2)=='2'){ // Optimisation *mp= *mp/2; while(*ip!='}') ++ip; } break; } ++ip; } } /// // Fonction appelée à la fin de la partie // void partie_fin() { } void exec(std::string const &function, std::vector<int>::iterator mem){ if(function=="TAILLE_TERRAIN") *mem=TAILLE_TERRAIN; else if(function=="FIN_PARTIE") *mem=FIN_PARTIE; else if(function=="MAX_JOUEURS") *mem=MAX_JOUEURS; else if(function=="REVENU_ILE") *mem=REVENU_ILE; else if(function=="REVENU_VOLCAN") *mem=REVENU_VOLCAN; else if(function=="OR_INITIAL") *mem=OR_INITIAL; else if(function=="CARAVELLE_COUT") *mem=CARAVELLE_COUT; else if(function=="GALION_COUT") *mem=GALION_COUT; else if(function=="CARAVELLE_DEPLACEMENT") *mem=CARAVELLE_DEPLACEMENT; else if(function=="GALION_DEPLACEMENT") *mem=GALION_DEPLACEMENT; else if(function=="LIMITE_BATEAUX") *mem=LIMITE_BATEAUX; else if(function=="info_terrain"){ position pos; pos.y=*++mem; pos.x=*++mem; mem-=2; *mem=info_terrain(pos); } else if(function=="info_ile_joueur"){ position pos; pos.y=*++mem; pos.x=*++mem; mem-=2; *mem=conv_ply(info_ile_joueur(pos)); } else if(function=="info_ile_or"){ position pos; pos.y=*++mem; pos.x=*++mem; mem-=2; *mem=info_ile_or(pos); } else if(function=="info_bateau"){ bateau b=info_bateau(*++mem-1); *--mem=b.id+1; *++mem=b.pos.y; *++mem=b.pos.x; *++mem=conv_ply(b.joueur); *++mem=b.btype; *++mem=b.nb_or; *++mem=b.deplacable; } else if(function=="bateau_existe"){ bool b=bateau_existe(*++mem-1); *--mem=b; } else if(function=="liste_bateaux_position"){ position pos; pos.y=*++mem; pos.x=*++mem; mem-=2; std::vector<int>::iterator cell=mem-1; std::vector<bateau> l=liste_bateaux_position(pos); for(auto it=l.begin(); it!=l.end(); ++it){ *++cell=1; *++cell=it->id+1; *++cell=it->pos.y; *++cell=it->pos.x; *++cell=conv_ply(it->joueur); *++cell=it->btype; *++cell=it->nb_or; *++cell=it->deplacable; } *++cell=0; } else if(function=="liste_id_bateaux_position"){ position pos; pos.y=*++mem; pos.x=*++mem; mem-=2; std::vector<int>::iterator cell=mem-1; std::vector<int> l=liste_id_bateaux_position(pos); for(auto it=l.begin(); it!=l.end(); ++it) *++cell=*it+1; *++cell=0; } else if(function=="liste_iles"){ std::vector<int>::iterator cell=mem-1; std::vector<position> l=liste_iles(); for(auto it=l.begin(); it!=l.end(); ++it){ *++cell=1; *++cell=it->y; *++cell=it->x; } *++cell=0; } else if(function=="mes_iles"){ std::vector<int>::iterator cell=mem-1; std::vector<position> l=mes_iles(); for(auto it=l.begin(); it!=l.end(); ++it){ *++cell=1; *++cell=it->y; *++cell=it->x; } *++cell=0; } else if(function=="id_dernier_bateau_construit"){ *mem=id_dernier_bateau_construit(); } else if(function=="construire"){ bateau_type t=static_cast<bateau_type>(*++mem); position pos; pos.y=*++mem; pos.x=*++mem; mem-=3; *mem=construire(t, pos); /*if(!*mem) std::cerr << "CONSTRUIRE " << t << " " << pos.y << " " << pos.x << "\n";*/ } else if(function=="deplacer"){ int id=*++mem-1; position pos; pos.y=*++mem; pos.x=*++mem; mem-=3; *mem=deplacer(id, pos); /*if(!*mem) std::cerr << "DEPLACER " << id << " -> " << pos.y << " " << pos.x << "\n";*/ } else if(function=="coloniser"){ position pos; pos.y=*++mem; pos.x=*++mem; mem-=2; *mem=coloniser(pos); /*if(!*mem) std::cerr << "COLONISER " << pos.y << " " << pos.x << "\n";*/ } else if(function=="charger"){ int id, nor; id=*++mem-1; nor=*++mem; mem-=2; *mem=charger(id, nor); } else if(function=="decharger"){ int id, nor; id=*++mem-1; nor=*++mem; mem-=2; *mem=decharger(id, nor); } else if(function=="transferer"){ int nor, src, dst; nor=*++mem; src=*++mem-1; dst=*++mem-1; mem-=3; *mem=transferer(nor, src, dst); } else if(function=="score"){ if(*++mem) *--mem=score(mon_joueur()); else *--mem=score(adversaire()); } else if(function=="tour_actuel"){ *mem=tour_actuel(); } else{ for(auto it=function.begin(); it!=function.end(); ++it) std::cerr << "<-> " << static_cast<int>(*it) << "\n"; throw std::runtime_error("function not found: "+function); } }
I used the following make target :
Makefile
bf:
@echo 'static char const * const program=R"BRAINFUCK_WHAT(' > jouer_tour
@cpp jouer_tour.bf | sed -e 's/^#.*//' >> jouer_tour
@echo ')BRAINFUCK_WHAT";' >> jouer_tourIf you look into the code, you'll notice some sub-optimal constructs and instructions that could be simplified, the goal was not to produce easy-to-read brainfuck (supposing this is possible), but to have a working bot by the end of the contest to shame people with bugged code.
So… as you can see, some organizer were very busy.