diff options
author | tomsmeding <tom.smeding@gmail.com> | 2016-12-14 20:19:02 +0100 |
---|---|---|
committer | tomsmeding <tom.smeding@gmail.com> | 2016-12-14 20:19:02 +0100 |
commit | 2d02f553aa4cc4ded630628eccdf34f55937cee5 (patch) | |
tree | d5377ebdff68788725b5820d5331ce7b6c9d4a84 /2015/day19.cpp | |
parent | 97b4c5d86cc12447ac6845e25a863e26a88aec35 (diff) |
Add 2015 sources
Diffstat (limited to '2015/day19.cpp')
-rw-r--r-- | 2015/day19.cpp | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/2015/day19.cpp b/2015/day19.cpp new file mode 100644 index 0000000..7afa3e7 --- /dev/null +++ b/2015/day19.cpp @@ -0,0 +1,89 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <unordered_map> +#include <vector> +#include <utility> + +using namespace std; + +bool search(const vector<pair<string,string>> &repls,const string &target,string from,int depth){ + if(from==target)return true; + if(depth<=0)return false; + int i,j,r,l; + const int fromlen=from.size(),nrepls=repls.size(); + for(i=0;i<fromlen;i++){ + for(r=0;r<nrepls;r++){ + l=repls[r].first.size(); + if(fromlen-i<l)continue; + for(j=0;j<l;j++)if(from[i+j]!=repls[r].first[j])break; + if(j<l)continue; + if(search(repls, + target, + from.substr(0,i)+repls[r].second+from.substr(i+repls[r].first.size()), + depth-1)){ + cerr<<repls[r].first<<" -> "<<repls[r].second<<" (at "<<i<<" in "<<from<<')'<<endl; + return true; + } + } + } + return false; +} + +int cheat(const vector<pair<string,string>> &repls,const string &target,string from){ + int i,r,j,l; + int depth; + const int fromlen=from.size(),nrepls=repls.size(); + for(depth=0;from!=target;depth++){ + for(i=0;i<fromlen;i++){ + for(r=0;r<nrepls;r++){ + l=repls[r].first.size(); + if(fromlen-i<l)continue; + for(j=0;j<l;j++)if(from[i+j]!=repls[r].first[j])break; + if(j<l)continue; + from=from.substr(0,i)+repls[r].second+from.substr(i+repls[r].first.size()); + i=fromlen+41; break; + } + } + if(i!=fromlen+42)return -1; + cout<<from<<endl; + } + return depth; +} + +int main(void){ + ifstream in("day19.txt"); + string line,target; + int a,b; + vector<pair<string,string>> repls; + while(true){ + getline(in,line); + if(line.size()==0){ + getline(in,target); + break; + } + if(!in)break; + a=line.find(' '); + b=line.find(' ',a+1); + // repls.emplace_back(line.substr(0,a),line.substr(b+1)); + repls.emplace_back(line.substr(b+1),line.substr(0,a)); //reversed + } + + // repls={{"H","HO"},{"H","OH"},{"O","HH"},{"e","O"},{"e","H"}}; + // repls={{"HO","H"},{"OH","H"},{"HH","O"},{"O","e"},{"H","e"}}; //reversed + // target="HOHOHO"; + + //for(const pair<string,string> &p : repls)cout<<"repl: "<<p.first<<" -> "<<p.second<<endl; + //cout<<"target: "<<target<<endl; + + cout<<cheat(repls,"e",target)<<endl; + + int depth; + for(depth=1;;depth++){ + cerr<<"Starting depth "<<depth<<"..."<<endl; + // const bool res=search(repls,target,"e",depth); + const bool res=search(repls,"e",target,depth); //reversed + if(res)break; + } + cout<<depth<<endl; +} |