1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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;
}
|
