aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--charm.cpp233
-rwxr-xr-xfullcomp.sh2
-rwxr-xr-xfullcompMT.sh2
-rw-r--r--ipow.h76
5 files changed, 312 insertions, 2 deletions
diff --git a/.gitignore b/.gitignore
index 619517f..d8d70d0 100644
--- a/.gitignore
+++ b/.gitignore
@@ -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
diff --git a/ipow.h b/ipow.h
new file mode 100644
index 0000000..62ba416
--- /dev/null
+++ b/ipow.h
@@ -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;
+ }
+}