Initial

7 files changed, 615 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..cb56aa9
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+*.o
+sim
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..009c5bc
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,20 @@
+CXX = g++
+CXXFLAGS = -Wall -Wextra -std=c++11 -g -fwrapv
+TARGET = sim
+
+.PHONY: all clean remake
+
+all: $(TARGET)
+
+clean:
+	rm -f $(TARGET) *.o
+
+remake: clean
+	$(MAKE) all
+
+
+$(TARGET): $(patsubst %.cpp,%.o,$(wildcard *.cpp))
+	$(CXX) -o $@ $^
+
+%.o: %.cpp $(wildcard *.h)
+	$(CXX) $(CXXFLAGS) -c -o $@ $<
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..ce93d37
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,229 @@
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <string>
+#include <unordered_map>
+#include <cstdlib>
+#include <cctype>
+#include <cassert>
+#include <sys/time.h>
+#include "params.h"
+#include "world.h"
+
+using namespace std;
+
+
+void trim(string &str){
+	while(str.size()>0&&isspace(str[0]))str.erase(0,1);
+	while(str.size()>0&&isspace(str.back()))str.erase(str.size()-1,1);
+}
+
+void squashSpaces(string &str){
+	bool sp=false;
+	for(size_t i=0;i<str.size();i++){
+		if(isspace(str[i])){
+			if(sp){
+				str.erase(i,1);
+				i--;
+			} else {
+				str[i]=' ';
+				sp=true;
+			}
+		} else {
+			sp=false;
+		}
+	}
+}
+
+vector<string> splittrim(const string &str,char sep){
+	if(str.size()==0)return {};
+	vector<string> res;
+	size_t cursor=0;
+	while(true){
+		size_t idx=str.find(sep,cursor);
+		if(idx==string::npos){
+			string s=str.substr(cursor);
+			trim(s);
+			res.push_back(s);
+			return res;
+		}
+		string s=str.substr(cursor,idx-cursor);
+		trim(s);
+		res.push_back(s);
+		cursor=idx+1;
+	}
+}
+
+void lowercase(string &str){
+	for(size_t i=0;i<str.size();i++){
+		str[i]=tolower(str[i]);
+	}
+}
+
+Argument parseArgument(const string &str,const unordered_map<string,Location> &labels,Location ip){
+	if(str[0]=='#'||str[0]=='%'){
+		bool remote=str[0]=='%';
+		if(isdigit(str[1]))return {arg_t::var,remote,atoi(str.data()+1),{}};
+		else return {arg_t::name,remote,0,str.substr(1)};
+	} else if(str[0]=='@'){
+		if(labels.find(str.substr(1))==labels.end()){
+			return {arg_t::undeflabel,false,0,str.substr(1)};
+		}
+		Location ref=labels.find(str.substr(1))->second;
+		assert(ref.bank==ip.bank);
+		return {arg_t::number,false,ref.bank-ip.bank,{}};
+	} else if(str[0]=='$'){
+		return {arg_t::constant,false,0,str.substr(1)};
+	} else if(isdigit(str[0])){
+		return {arg_t::number,false,atoi(str.data()),{}};
+	} else {
+		assert(false);
+	}
+}
+
+Team assemble(const string &source){
+	Team team;
+	unordered_map<string,Location> labels;
+
+	for(string line : splittrim(source,'\n')){
+		if(line.size()==0)continue;
+
+		string word1=line.substr(0,line.find(' '));
+		string word2r=line.find(' ')==string::npos?"":line.substr(line.find(' ')+1);
+		if(word1=="published"){
+			string word2=word2r.substr(0,word2r.find(' '));
+			string word3r=word2r.find(' ')==string::npos?"":word2r.substr(word2r.find(' ')+1);
+			if(word2=="name"){
+				team.name=word3r;
+			}
+		} else if(word1=="bank"){
+			team.banks.emplace_back();
+		} else if(word1[0]=='@'){
+			assert(line.find(' ')==string::npos);
+			assert(labels.find(word1.substr(1))==labels.end());
+			labels[word1.substr(1)]={(int)team.banks.size()-1,(int)team.banks.back().size()};
+		} else {
+			assert(team.banks.size()>0);
+			vector<string> args=splittrim(word2r,',');
+			vector<Argument> pargs;
+			for(const string &s : args){
+				pargs.push_back(parseArgument(s,labels,
+					{(int)team.banks.size()-1,(int)team.banks.back().size()}));
+			}
+			if(word1=="jump"||word1=="turn"||word1=="scan")assert(pargs.size()==1);
+			else if(word1=="die"||word1=="move")assert(pargs.size()==0);
+			else if(word1=="create")assert(pargs.size()==3);
+			else assert(pargs.size()==2);
+
+			Script &s=team.banks.back();
+			if(word1=="set")s.push_back(Instruction::make(ins_t::set,{pargs[0],pargs[1]}));
+			else if(word1=="add")s.push_back(Instruction::make(ins_t::add,{pargs[0],pargs[1]}));
+			else if(word1=="sub")s.push_back(Instruction::make(ins_t::sub,{pargs[0],pargs[1]}));
+			else if(word1=="comp")s.push_back(Instruction::make(ins_t::comp,{pargs[0],pargs[1]}));
+			else if(word1=="trans")s.push_back(Instruction::make(ins_t::trans,{pargs[0],pargs[1]}));
+			else if(word1=="jump")s.push_back(Instruction::make(ins_t::jump,{pargs[0]}));
+			else if(word1=="bjump")s.push_back(Instruction::make(ins_t::bjump,{pargs[0],pargs[1]}));
+			else if(word1=="die")s.push_back(Instruction::make(ins_t::die,{}));
+			else if(word1=="move")s.push_back(Instruction::make(ins_t::move,{}));
+			else if(word1=="turn")s.push_back(Instruction::make(ins_t::turn,{pargs[0]}));
+			else if(word1=="scan")s.push_back(Instruction::make(ins_t::scan,{pargs[0]}));
+			else if(word1=="create")s.push_back(Instruction::make(ins_t::create,{pargs[0],pargs[1],pargs[2]}));
+			else assert(false);
+		}
+	}
+
+	int bank=0;
+	for(Script &script : team.banks){
+		int pos=0;
+		for(Instruction &ins : script){
+			for(Argument &arg : ins.args){
+				if(arg.type==arg_t::undeflabel){
+					assert(labels.find(arg.name)!=labels.end());
+					assert(labels[arg.name].bank==bank);
+					arg.type=arg_t::number;
+					arg.num=labels[arg.name].pos-pos;
+				}
+			}
+			pos++;
+		}
+		bank++;
+	}
+
+	return team;
+}
+
+string preprocess(istream &file){
+	unordered_map<string,string> defines;
+
+	string result;
+
+	string line;
+	while(getline(file,line)){
+		if(line.find(';')!=string::npos){
+			line.erase(line.find(';'));
+		}
+		trim(line);
+		if(line.size()==0)continue;
+		squashSpaces(line);
+		lowercase(line);
+
+		string word1=line.substr(0,line.find(' '));
+		if(word1=="define"){
+			string word2r=line.find(' ')==string::npos?"":line.substr(line.find(' ')+1);
+			string word2=word2r.substr(0,word2r.find(' '));
+			string word3r=word2r.find(' ')==string::npos?"":word2r.substr(word2r.find(' ')+1);
+			assert(defines.find(word2.substr(1))==defines.end());
+			assert(word3r[0]=='{');
+			string value=word3r.substr(1);
+			assert(word3r.find('}')==string::npos||word3r.find('}')==word3r.size()-1);
+			if(word3r.back()!='}'){
+				while(true){
+					char c=file.get();
+					if(c=='}')break;
+					value+=c;
+				}
+				assert(file.get()=='\n');
+			} else {
+				value.erase(value.size()-1);
+			}
+			defines[word2.substr(1)]=value;
+		} else {
+			while(line.find('&')!=string::npos){
+				size_t start=line.find('&')+1;
+				size_t end=line.find_first_not_of("abcdefghijklmnopqrstuvwxyz0123456789._",start);
+				if(end==string::npos)end=line.size();
+				assert(defines.find(line.substr(start,end-start))!=defines.end());
+				line=line.substr(0,start-1)+defines.find(line.substr(start,end-start))->second+line.substr(end);
+			}
+			result+=line+'\n';
+		}
+	}
+
+	return result;
+}
+
+
+int main(int argc,char **argv){
+	struct timeval tv;
+	gettimeofday(&tv,nullptr);
+	srand(tv.tv_sec*1000000+tv.tv_usec);
+
+	World world;
+	vector<Team> teams;
+	for(int i=1;i<argc;i++){
+		ifstream f(argv[i]);
+		assert(f);
+		teams.push_back(assemble(preprocess(f)));
+	}
+
+	for(const Team &t : teams){
+		Robot &r=world.create(&t,2,t.banks.size(),false);
+		for(int i=0;i<(int)t.banks.size();i++){
+			r.load(i,t.banks[i]);
+		}
+	}
+
+	for(int i=0;i<C::autoTimeout;i++){
+		world.tick();
+	}
+}
diff --git a/params.cpp b/params.cpp
new file mode 100644
index 0000000..5b71e86
--- /dev/null
+++ b/params.cpp
@@ -0,0 +1,33 @@
+#include "params.h"
+
+namespace C {
+
+	const int autoTimeout=80000;
+	const int elimTrigger=25000;
+
+	const int baseDuration[]={
+		2, // set
+		2, // add
+		2, // sub
+		2, // comp
+		14, // trans
+		1, // jump
+		2, // bjump
+		1, // die
+		20, // move
+		8, // turn
+		8, // scan
+		100, // create
+	};
+
+	const int numInstructions=(int)ins_t::__num_instructions;
+
+	const int pen_transinstr=1;
+	const int pen_remote=6;
+	const int pen_createbank=25;
+	const int pen_createmobilemult=1;
+	const int pen_createmobile=120;
+	const int pen_createiset1=40;
+	const int pen_createiset2=100;
+
+}
diff --git a/params.h b/params.h
new file mode 100644
index 0000000..464068a
--- /dev/null
+++ b/params.h
@@ -0,0 +1,38 @@
+#pragma once
+
+#define SIZE 20
+
+enum class ins_t{
+	set, // #dst, $src
+	add, // #dst, $src
+	sub, // #dst, $src
+	comp, // $v1, $v2
+	trans, // $src, $dst
+	jump, // $pos
+	bjump, // $bank, $pos
+	die, // -
+	move, // -
+	turn, // $dir
+	scan, // #dst
+	create, // $is, $nbanks, $move
+
+	__num_instructions
+};
+
+namespace C {
+
+	extern const int numInstructions;
+
+	extern const int autoTimeout;
+	extern const int elimTrigger;
+
+	extern const int baseDuration[];
+	extern const int pen_transinstr;
+	extern const int pen_remote;
+	extern const int pen_createbank;
+	extern const int pen_createmobilemult;
+	extern const int pen_createmobile;
+	extern const int pen_createiset1;
+	extern const int pen_createiset2;
+
+}
diff --git a/world.cpp b/world.cpp
new file mode 100644
index 0000000..e99ce97
--- /dev/null
+++ b/world.cpp
@@ -0,0 +1,199 @@
+#include <cstdlib>
+#include <cassert>
+#include "world.h"
+
+using namespace std;
+
+
+Argument::~Argument(){}
+
+
+Instruction Instruction::make(ins_t op,vector<Argument> args){
+	return {op,args};
+}
+
+
+void Robot::load(int idx,const Script &scr){
+	banks[idx]=scr;
+}
+
+void Robot::tick(World &world){
+	waited++;
+	Instruction ins=resolve(world);
+	int dur=calcDuration(ins);
+	if(dur<waited)return;
+	waited=0;
+	execute(ins,world);
+}
+
+Instruction Robot::resolve(World &world){
+	Instruction ins=banks.at(ip.bank).at(ip.pos);
+	for(Argument &arg : ins.args){
+		switch(arg.type){
+			case arg_t::number:
+				break;
+			case arg_t::var:
+				assert(!arg.remote);
+				arg.type=arg_t::number;
+				arg.num=vars.at(arg.num-1);
+				break;
+			case arg_t::name:
+				assert(arg.name=="active");
+				arg.type=arg_t::number;
+				if(!arg.remote){
+					arg.num=active;
+				} else {
+					Robot *target=world.targetbot(this);
+					if(target)arg.num=target->active;
+					else arg.num=0;
+				}
+				break;
+			case arg_t::constant:
+				assert(false);
+			default:
+				assert(false);
+		}
+	}
+	return ins;
+}
+
+int Robot::calcDuration(Instruction &ins){
+	int d=0;
+	for(const Argument &arg : ins.args){
+		if(arg.remote)d+=C::pen_remote;
+	}
+	int base=C::baseDuration[(int)ins.op];
+	switch(ins.op){
+		case ins_t::set: d+=base;
+		case ins_t::add: d+=base;
+		case ins_t::sub: d+=base;
+		case ins_t::comp: d+=base;
+		case ins_t::trans: d+=base+C::pen_transinstr*banks.at(ins.args[0].num).size();
+		case ins_t::jump: d+=base;
+		case ins_t::bjump: d+=base;
+		case ins_t::die: d+=base;
+		case ins_t::move: d+=base;
+		case ins_t::turn: d+=base;
+		case ins_t::scan: d+=base;
+		case ins_t::create: d+=(base+C::pen_createbank*ins.args[1].num)*C::pen_createmobilemult+C::pen_createmobile*ins.args[2].num+C::pen_createiset1*(ins.args[0].num==1)+C::pen_createiset2*(ins.args[0].num==2);
+		default: assert(false);
+	}
+	return d;
+}
+
+
+World::World(){
+	memset(&board[0][0],0,SIZE*SIZE*sizeof(Robot*));
+}
+
+World::~World(){
+	for(int y=0;y<SIZE;y++){
+		for(int x=0;x<SIZE;x++){
+			if(board[y][x])delete board[y][x];
+		}
+	}
+}
+
+Robot& World::create(const Team *team,int iset,int nbanks,bool mobile){
+	int x,y;
+	while(true){
+		x=rand()%SIZE;
+		y=rand()%SIZE;
+		if(!board[y][x])break;
+	}
+	board[y][x]=new Robot();
+	board[y][x]->team=team;
+	board[y][x]->banks.resize(nbanks);
+	board[y][x]->iset=iset;
+	board[y][x]->mobile=mobile;
+	board[y][x]->heading=rand()%4;
+	return *board[y][x];
+}
+
+void World::tick(){
+	for(int y=0;y<SIZE;y++){
+		for(int x=0;x<SIZE;x++){
+			if(board[y][x])board[y][x]->tick(*this);
+		}
+	}
+}
+
+Robot* World::targetbot(const Robot *r){
+	for(int y=0;y<SIZE;y++){
+		for(int x=0;x<SIZE;x++){
+			if(board[y][x]==r){
+				switch(r->heading){
+					case 0: return board[y][(x+1)%SIZE];
+					case 1: return board[(y+SIZE-1)%SIZE][x];
+					case 2: return board[y][(x+SIZE-1)%SIZE];
+					case 3: return board[(y+1)%SIZE][x];
+				}
+			}
+		}
+	}
+	assert(false);
+}
+
+
+ostream& operator<<(ostream &os,const Argument &arg){
+	if(arg.remote){
+		switch(arg.type){
+			case arg_t::number: return os<<arg.num;
+			case arg_t::var: assert(false);
+			case arg_t::name: return os<<'%'<<arg.name;
+			case arg_t::constant: assert(false);
+			case arg_t::undeflabel: return os<<"\x1B[31;43mUNDEFLABEL\x1B[0m";
+		}
+	} else {
+		switch(arg.type){
+			case arg_t::number: return os<<arg.num;
+			case arg_t::var: return os<<'#'<<arg.num;
+			case arg_t::name: return os<<'#'<<arg.name;
+			case arg_t::constant: return os<<'$'<<arg.name;
+			case arg_t::undeflabel: return os<<"\x1B[31;43mUNDEFLABEL\x1B[0m";
+		}
+	}
+}
+
+ostream& operator<<(ostream &os,const ins_t &type){
+	switch(type){
+		case ins_t::set: return os<<"set";
+		case ins_t::add: return os<<"add";
+		case ins_t::sub: return os<<"sub";
+		case ins_t::comp: return os<<"comp";
+		case ins_t::trans: return os<<"trans";
+		case ins_t::jump: return os<<"jump";
+		case ins_t::bjump: return os<<"bjump";
+		case ins_t::die: return os<<"die";
+		case ins_t::move: return os<<"move";
+		case ins_t::turn: return os<<"turn";
+		case ins_t::scan: return os<<"scan";
+		case ins_t::create: return os<<"create";
+		default: assert(false);
+	}
+}
+
+ostream& operator<<(ostream &os,const Instruction &ins){
+	os<<ins.op;
+	bool first=true;
+	for(const Argument &arg : ins.args){
+		if(first)os<<' ';
+		else os<<", ";
+		first=false;
+		os<<arg;
+	}
+	return os;
+}
+
+ostream& operator<<(ostream &os,const Team &team){
+	os<<"TEAM: "<<team.name<<endl;
+	int bank=0;
+	for(const Script &scr : team.banks){
+		os<<"Bank "<<bank<<endl;
+		for(const Instruction &ins : scr){
+			os<<'\t'<<ins<<endl;
+		}
+		bank++;
+	}
+	return os;
+}
diff --git a/world.h b/world.h
new file mode 100644
index 0000000..ccbdbcf
--- /dev/null
+++ b/world.h
@@ -0,0 +1,94 @@
+#pragma once
+
+#include <iostream>
+#include <string>
+#include <array>
+#include <vector>
+#include <cstdint>
+#include "params.h"
+
+using namespace std;
+
+
+struct Location{
+	int bank; // 0-based
+	int pos; // 0-based
+};
+
+
+enum class arg_t{
+	number,
+	var,
+	name,
+	constant,
+	undeflabel,
+};
+
+struct Argument{
+	arg_t type;
+	bool remote;
+	int num;
+	string name;
+
+	~Argument();
+};
+
+struct Instruction{
+	ins_t op;
+	vector<Argument> args;
+
+	static Instruction make(ins_t op,vector<Argument> args);
+};
+
+using Script = vector<Instruction>;
+
+class Team;
+class World;
+
+class Robot{
+	Location ip={0,0};
+	int waited=0;
+	array<uint16_t,20> vars;
+	uint16_t active;
+
+	Instruction resolve(World &world);
+	int calcDuration(Instruction &ins);
+	void execute(Instruction &ins,World &world);
+
+public:
+	const Team *team;
+	vector<Script> banks;
+	int iset;
+	bool mobile;
+
+	int heading;
+
+	void load(int idx,const Script &scr);
+
+	void tick(World &world);
+};
+
+class Team{
+public:
+	string name;
+	vector<Script> banks;
+};
+
+class World{
+public:
+	Robot *board[SIZE][SIZE];
+	
+	World();
+	~World();
+
+	Robot& create(const Team *team,int iset,int nbanks,bool mobile);
+
+	void tick();
+	Robot* targetbot(const Robot *r);
+};
+
+
+ostream& operator<<(ostream &os,const Argument &arg);
+ostream& operator<<(ostream &os,const ins_t &type);
+ostream& operator<<(ostream &os,const Instruction &ins);
+ostream& operator<<(ostream &os,const Team &team);