diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | charm.cpp | 233 | ||||
| -rwxr-xr-x | fullcomp.sh | 2 | ||||
| -rwxr-xr-x | fullcompMT.sh | 2 | ||||
| -rw-r--r-- | ipow.h | 76 |
5 files changed, 312 insertions, 2 deletions
@@ -7,6 +7,7 @@ gluon neutrino randino photon +charm viewcompetition diff --git a/charm.cpp b/charm.cpp new file mode 100644 index 0000000..1434e8c --- /dev/null +++ b/charm.cpp @@ -0,0 +1,233 @@ +#include <iostream> +#include <fstream> +#include <sstream> +#include <vector> +#include <algorithm> +#include <utility> +#include <cstring> +#include <sys/time.h> + +#include "ipow.h" + +#define S (5) + +using namespace std; + +bool should_flip_board=false; + +struct Move; +class Board; + +Move protocol_get_move(void); +void protocol_put_move(ostream &s,Move m); + +int index_deltas[8][2]={{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1}}; + +struct Move{ + int neudir,from,dir; + string str(void){ + stringstream ss; + ss<<neudir<<' '<<from<<' '<<dir; + return ss.str(); + } +}; + +class Board{ +public: + int grid[S*S]; + int neuidx; + Board(void):neuidx(S*(S/2)+S/2){ + memset(grid,0,S*S*sizeof(int)); + grid[S*(S/2)+S/2]=3; + for(int i=0;i<S;i++){ + grid[i]=1; + grid[S*(S-1)+i]=2; + } + } + int moved(int at,int dir){ + int x=at%S,y=at/S,x2,y2; + while(true){ + x2=x+index_deltas[dir][0]; + y2=y+index_deltas[dir][1]; + if(x2<0||x2>=S||y2<0||y2>=S||grid[S*y2+x2]!=0)return S*y+x; + x=x2; + y=y2; + } + } + bool move(int at,int dir,int _newatcached=-1){ + int newat=_newatcached==-1?moved(at,dir):_newatcached; + if(newat==at)return false; + grid[newat]=grid[at]; + grid[at]=0; + if(grid[newat]==3)neuidx=newat; + return true; + } + void undomove(int at,int dir){ + int movedidx=moved(at,dir); + movedidx+=S*index_deltas[dir][1]+index_deltas[dir][0]; + grid[at]=grid[movedidx]; + grid[movedidx]=0; + if(grid[at]==3)neuidx=at; + } + bool isvalid(Move mv){ + int oldneuidx=neuidx; + //cerr<<"Called isvalid with move "; + //protocol_put_move(cerr,mv); + //print(); + if(!move(oldneuidx,mv.neudir)){ + //undomove(oldneuidx,mv.neudir); + return false; + } + if(!move(mv.from,mv.dir)){ + //undomove(mv.from,mv.dir); + undomove(oldneuidx,mv.neudir); + return false; + } + undomove(mv.from,mv.dir); + undomove(oldneuidx,mv.neudir); + return true; + } + void print(void){ + int x,y; + if(should_flip_board){ + for(y=S-1;y>=0;y--){ + for(x=S-1;x>=0;x--)cerr<<grid[S*y+x]<<' '; + cerr<<endl; + } + } else { + for(y=0;y<S;y++){ + for(x=0;x<S;x++)cerr<<grid[S*y+x]<<' '; + cerr<<endl; + } + } + } +}; + + +int scorefor(const Board &bd){ + int i,score=0; + for(i=0;i<S*S;i++){ + if(bd.grid[i]==1)score+=i/S; + else if(bd.grid[i]==2)score-=i/S; + else if(bd.grid[i]==3)score-=(i/S)*(i/S); + } + return score; +} + +bool sortscoresfunc(const pair<Move,int> &a,const pair<Move,int> &b){ + return a.second>b.second; +} + +Move calculate_move(Board &bd){ + vector<pair<Move,int>> poss; + Move m; + int nd,fr,d; + int newneu; + int score,oldneuidx; + //bd.print(); + for(nd=0;nd<8;nd++){ + newneu=bd.moved(bd.neuidx,nd); + if(newneu==bd.neuidx)continue; + for(fr=0;fr<S*S;fr++){ + if(bd.grid[fr]!=1)continue; + //cerr<<"fr="<<fr<<endl; + for(d=0;d<8;d++){ + m.neudir=nd; + m.from=fr; + m.dir=d; + if(bd.isvalid(m)){ + oldneuidx=bd.neuidx; + bd.move(oldneuidx,m.neudir,newneu); + bd.move(m.from,m.dir); + score=scorefor(bd); + bd.undomove(m.from,m.dir); + bd.undomove(oldneuidx,m.neudir); + poss.push_back({m,score}); + } + } + } + } + sort(poss.begin(),poss.end(),sortscoresfunc); + for(auto p : poss)cerr<<p.first.str()<<": "<<p.second<<endl; + return poss[ipow(rand()%(poss.size()/2+1),2)/(poss.size()/2+1)].first; +} + + +inline int flip_index(int idx){ + return S*(S-1-idx/S)+S-1-idx%S; +} +inline int flip_dir(int dir){ + return dir==-1?-1:(dir+4)%8; +} + +Move protocol_get_move(void){ + Move m; + char c=cin.peek(); + if(c=='q'||c=='Q')exit(0); + cin>>m.neudir>>m.from>>m.dir; + if(should_flip_board){ + m.neudir=flip_dir(m.neudir); + m.from=flip_index(m.from); + m.dir=flip_dir(m.dir); + } + cerr<<"Got: "; + protocol_put_move(cerr,m); + cin.ignore(1024,'\n'); + return m; +} + +void protocol_put_move(ostream &s,Move m){ + if(should_flip_board){ + s<<flip_dir(m.neudir)<<' '<<flip_index(m.from)<<' '<<flip_dir(m.dir)<<endl; + } else { + s<<m.neudir<<' '<<m.from<<' '<<m.dir<<endl; + } +} + +int main(void){ + Board bd; + Move mv; + string line; + struct timeval tv; + gettimeofday(&tv,NULL); + cerr<<"seed="<<(1000000*tv.tv_sec+tv.tv_usec)<<endl; + srand(1000000*tv.tv_sec+tv.tv_usec); + //srand(1430130052185291); + getline(cin,line); + if(line=="go"){ + should_flip_board=false; + mv.neudir=-1; mv.from=1; mv.dir=3; + bd.move(mv.from,mv.dir); + protocol_put_move(cout,mv); + } else { + if(line!="nogo")cerr<<"no0b "<<line<<" not in (go,nogo)"<<endl; + should_flip_board=true; + mv=protocol_get_move(); + bd.move(mv.from,mv.dir); + bd.print(); + mv=calculate_move(bd); + if(!bd.isvalid(mv)){ + cerr<<"calculate_move gave invalid move "<<mv.str()<<endl; + return 1; + } + bd.move(bd.neuidx,mv.neudir); + bd.move(mv.from,mv.dir); + protocol_put_move(cout,mv); + } + while(true){ + bd.print(); + mv=protocol_get_move(); + bd.move(bd.neuidx,mv.neudir); + bd.move(mv.from,mv.dir); + bd.print(); + mv=calculate_move(bd); + if(!bd.isvalid(mv)){ + cerr<<"calculate_move gave invalid move "<<mv.str()<<endl; + return 1; + } + bd.move(bd.neuidx,mv.neudir); + bd.move(mv.from,mv.dir); + protocol_put_move(cout,mv); + } + return 0; +} diff --git a/fullcomp.sh b/fullcomp.sh index 66609d9..bb4f59a 100755 --- a/fullcomp.sh +++ b/fullcomp.sh @@ -1,5 +1,5 @@ #!/usr/bin/env bash -BINARIES="./gluon ./neutrino ./randino" +BINARIES="./gluon ./neutrino ./randino ./charm" if [[ ! -e competitions ]]; then mkdir competitions || exit 1 diff --git a/fullcompMT.sh b/fullcompMT.sh index f8444db..7f4084e 100755 --- a/fullcompMT.sh +++ b/fullcompMT.sh @@ -1,5 +1,5 @@ #!/usr/bin/env bash -BINARIES="./gluon ./neutrino ./randino" +BINARIES="./gluon ./neutrino ./randino ./charm" if [[ ! -e competitions ]]; then mkdir competitions || exit 1 @@ -0,0 +1,76 @@ +//SOURCE: https://gist.github.com/orlp/3551590 +int64_t ipow(int32_t base, uint8_t exp) { + static const uint8_t highest_bit_set[] = { + 0, 1, 2, 2, 3, 3, 3, 3, + 4, 4, 4, 4, 4, 4, 4, 4, + 5, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5, 5, + 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 255, // anything past 63 is a guaranteed overflow with base > 1 + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, + }; + + uint64_t result = 1; + + switch (highest_bit_set[exp]) { + case 255: // we use 255 as an overflow marker and return 0 on overflow/underflow + if (base == 1) { + return 1; + } + + if (base == -1) { + return 1 - 2 * (exp & 1); + } + + return 0; + case 6: + if (exp & 1) result *= base; + exp >>= 1; + base *= base; + case 5: + if (exp & 1) result *= base; + exp >>= 1; + base *= base; + case 4: + if (exp & 1) result *= base; + exp >>= 1; + base *= base; + case 3: + if (exp & 1) result *= base; + exp >>= 1; + base *= base; + case 2: + if (exp & 1) result *= base; + exp >>= 1; + base *= base; + case 1: + if (exp & 1) result *= base; + default: + return result; + } +} |