Start working on charm

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;
+    }
+}