Add 2015 sources

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