use std.io; var myers = func(src,dst,show_table=0) { (src,dst)=(split("\n",src),split("\n",dst)); append(src,""); append(dst,""); var (src_len,dst_len)=(size(src),size(dst)); var mat=[]; setsize(mat,dst_len*src_len); forindex(var i;mat) { mat[i]=0; } var visited=[]; setsize(visited,dst_len*src_len); forindex(var i;visited) { visited[i]=0; } forindex(var y;dst) forindex(var x;src) mat[y*src_len+x]=(src[x]==dst[y]); if (show_table) { var curve=[ ["+---","| "], ["+---","| \\ "] ]; var s=""; forindex(var y;dst) { forindex(var t;curve[0]) { forindex(var x;src) { s~=curve[mat[y*src_len+x]][t]; } s~=["+","|"][t]~"\n"; } } forindex(var i;src) s~="+---"; print(s~"+\n"); } var (total,path,vec)=([],[],[[0,0,-1]]); visited[0]=1; while(size(vec)) { append(total,vec); var tmp=[]; forindex(var i;vec) { var elem=vec[i]; var (x,y)=(elem[1],elem[0]); # find solution if (x==src_len-1 and y==dst_len-1) { append(path,vec[i]); for(var (prev,iter)=(elem[2],size(total)-1);iter>0;iter-=1) { var t=total[iter-1][prev]; append(path,t); prev=t[2]; } if (show_table) { for(var t=size(path)-1;t>=0;t-=1) print("("~path[t][1]~","~path[t][0]~")",t==0?"":"->"); println(); } # reverse path for(var t=0;t<size(path)/2;t+=1) (path[t],path[-1-t])=(path[-1-t],path[t]); # print diff for(var t=1;t<size(path);t+=1) { var (prev_x,prev_y)=(path[t-1][1],path[t-1][0]); var (x,y)=(path[t][1],path[t][0]); var (sub_x,sub_y)=(x-prev_x,y-prev_y); if (sub_x==1 and sub_y==1) { if (show_table) println(" ",src[prev_x]); } elsif (sub_x==1 and sub_y==0) { println("\e[31m - ",src[prev_x],"\e[0m"); } elsif (sub_x==0 and sub_y==1) { println("\e[32m + ",dst[prev_y],"\e[0m"); } } return; } # do bfs if (mat[y*src_len+x]==1) { if (x+1<src_len and y+1<dst_len and visited[(y+1)*src_len+x+1]==0) { append(tmp,[y+1,x+1,i]); visited[(y+1)*src_len+x+1]=1; } } else { if (x+1<src_len and visited[y*src_len+x+1]==0) { append(tmp,[y,x+1,i]); visited[y*src_len+x+1]=1; } if (y+1<dst_len and visited[(y+1)*src_len+x]==0) { append(tmp,[y+1,x,i]); visited[(y+1)*src_len+x]=1; } } } vec=tmp; } } func(diff) { diff( "var a=0;\nvar b=1;\nprint(\"hello \",a);\nvar c=2;\nc=[];\nvar d=3;\nvar l=list();\nvar q=queue();\n", "var a=0;\nvar b=1;\nb=[];\nprintln(\"hello \",a);\nvar c=2;\nvar d=3;\nprintln(\"hello world!\");\nvar l=list();\nvar q=queue();\n", 1 ); print("\n"); diff( "A\nB\nC\nA\nB\nB\nA\n", "C\nB\nA\nB\nA\nC\n", 1 ); print("\n"); diff( io.readfile("test/bf.nas"), io.readfile("test/bfconvertor.nas") ); }(myers);