diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | Makefile | 20 | ||||
| -rw-r--r-- | main.cpp | 229 | ||||
| -rw-r--r-- | params.cpp | 33 | ||||
| -rw-r--r-- | params.h | 38 | ||||
| -rw-r--r-- | world.cpp | 199 | ||||
| -rw-r--r-- | world.h | 94 |
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; +} @@ -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); |