#Project 4

Help:=proc(): print(` Followers(W), Followers1(W) `):
print(`FindAllFollowers(W, AllFollowers)`):
print(`FindPyramid(Start, End), IsSubsequence(Sub, Seq),PyramidShape(PyramidResult)`): 
print(`genChainConnects, findPath(W1, W2, C),Reachable(W1, C)`): 
print(`genTreeConnects, findAllPyramids(N1, N2, connects),dfs(currPath, N, Connects) `): 
print(`PyramidResult(W1, W2)`): 
end:

read `ENGLISH.txt`:

#Followers(W): inputs a word in English and outputs all the set of all words
#obtained by inserting somewhere one letter
Followers:=proc(W) local N,A,W1,S,B1,B2,G:
A:=[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]:
N:=nops(W):
S:=convert(ENG()[N+1],set):
G:={}:
for B1 from 1 to N+1 do
 for B2 from 1 to nops(A) do
  W1:=[op(1..B1-1,W),A[B2],op(B1..N,W)]:
  if member(W1,S) then
   G:=G union {W1}:
  fi:
 od:
od:

G:
end:


#Followers1(W): inputs a word in English and outputs all the set of all words
#obtained by changing  one letter
Followers1:=proc(W) local N,A,W1,S,B1,B2,G:
A:=[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]:
N:=nops(W):
S:=convert(ENG()[N],set):
G:={}:
for B1 from 1 to N do
 for B2 from 1 to nops(A) do
  W1:=[op(1..B1-1,W),A[B2],op(B1+1..N,W)]:
  if W1<>W and member(W1,S) then
   G:=G union {W1}:
  fi:
 od:
od:

G:
end:



#Plan for finding all pyramids: Best way of going about it would be to pre-generate a map that gives all of the folowers for any given word. This map represents a digraph (directional graph), more specifically a tree of all follower relationships. From there it would be really quick to find any arbitrary pyramids, for example those going from length 9 to length 13, prune any pyramids with duplicate layers, or really anything with some basic tree traversal algorithms.

#Plan for chains: Same idea as for pyramids. Pregenerate a map representing all of followers. From there it's less a matter of how to do and more what to do. Graph traversal algorithms are pretty wide.

#for both pyramids and chains whether it's necessary or even faster to pregenerate all connections is up in the air. Depends on the specifics of our implementation of a map and the associated time complexity with accessing values given a key.

#plan for solver: Whether it's easier to solve from the top down or bottom up is up in the air. Would be interesting to figure out.

#---------------------------------------------------------
# FindAllFollowers : Recursive procedure to find all followers
FindAllFollowers := proc(W, AllFollowers)
    local F, WORD, NewFollowers;
    # Find the immediate followers of W
    F := Followers(W);
    NewFollowers := AllFollowers;
    # For each follower...
    for WORD in F do
        # If the follower is not already in AllFollowers...
        if not member(WORD, NewFollowers) then
            # Add the follower to AllFollowers
            NewFollowers := NewFollowers union {WORD};
            # Recursively find the followers of the follower
            NewFollowers := FindAllFollowers(WORD, NewFollowers);
        fi;
    od;
    # Return the set of all followers
    return NewFollowers;
end:

# Initial call to FindAllFollowers for [w,o,r,d]
#>WWW := [a];
#>AllFollowers := FindAllFollowers(WWW, {WWW});

#FindPyramid: finding pyramid input the fisrt word and the last word
#outputs all the pyramid possible
FindPyramid := proc(Start, End)
    local Paths, Queue, Current, Neighbors, Neighbor, i, j, k, result, NewPath;
    Queue := [[Start]];
    Paths := [];
    while 0 < nops(Queue) do
        Current := Queue[1];
        Queue := [op(2 .. nops(Queue), Queue)];
        if op(-1, Current) = End then
            Paths := [op(Paths), Current];
        else
            Neighbors := Followers(op(-1, Current));
            for Neighbor in Neighbors do
                if not member(Neighbor, Current) and nops(Neighbor) = nops(op(-1, Current)) + 1 and IsSubsequence(Neighbor, End) then
                    NewPath := [op(Current), Neighbor];
                    Queue := [op(Queue), NewPath];
                end if;
            end do;
        end if
    end do;
    if nops(Paths) = 0 then
        return "No pyramid found";
    else
        return Paths;
    end if
end proc:

#IsSubsequence(Sub, Seq) : checking if the subsequence is in the pyramid
#for example:
#IsSubsequence([a, d, s], [b, r, a, n, d, s]);
#(result)3 < 4   <---this means [a, d, s] is in the pyramid
#IsSubsequence([d, a, s], [b, r, a, n, d, s]);                            
#(result)3 < 2   <---this means [d, a, s] is not in the pyramid

IsSubsequence := proc(Sub, Seq)
    local i, j;
    i := 1;
    j := 1;
    while i <= nops(Sub) and j <= nops(Seq) do
        if Sub[i] = Seq[j] then
            i := i + 1;
        end if;
        j := j + 1;
    end do;
    return nops(Sub) < i;
end proc:

#shaping the pyramid
PyramidShape:=proc(PyramidResult) local i1,j1:
for i1 from 1 to nops(PyramidResult) do
    for j1 from 1 to nops(PyramidResult[i1]) do
        print(PyramidResult[i1][j1]);
    end do;
end do;
end proc:

#-------CHAINS-------------------------------------
#genChainConnects: this func pregenerates the connections 
genChainConnects:=proc() local chainConnects,i1,j1,currWords,currTable,word:
#pretty basic brute force, the 1...5 can be changed to whatever num to generate all connectons 
chainConnects:=[seq(i1,i1=1..5)]:  
for i1 from 1 to nops(chainConnects) do:   
 currTable:=table():    
 currWords:=ENG()[i1]:    
  for word in currWords do:     
   currTable[word]:=Followers1(word,currWords):    
  end do:     
 chainConnects[i1]:=copy(currTable):  
end do:    
chainConnects:   
end:

#findPath: finds paths from W1,W2. C is just connections
findPath := proc(W1, W2, C) local PENDING, N, currWord, currFollowers, WORD, PARENTS, PATH, PARENT; 
if nops(W1) <> nops(W2) then 
 return "error: different length"; 
end if; 

#a breath first search
PARENTS := table(); 
N := nops(W1); 
PENDING := DEQueue({W1}); 
for WORD in ENG()[N] do 
 PARENTS[WORD] := "none"; 
end do; 
PARENTS[W1] := W1; 
while empty(PENDING) = false do 
 currWord := op(pop_front(PENDING));

 #this is for if we can actually find the correct ending word 
 if currWord = W2 then 
  PATH := [W2]; 
  PARENT := PARENTS[W2]; 
   while PARENT <> W1 do 
    PATH := [PARENT, op(PATH)]; 
    PARENT := PARENTS[PARENT]; 
   end do; 
  return [W1, op(PATH)]; 
 end if;

#this is the iteration part
currFollowers := C[N][currWord]; 
for WORD in currFollowers do 
 if PARENTS[WORD] = "none" then 
  PARENTS[WORD] := currWord; 
  push_back(PENDING, {WORD}); 
 end if; 
end do; 
end do; 
return []; 
end proc:


#--------TREE--------------------------
#basic modification of findPath that keeps track of all words along the paths
Reachable := proc(W1, C) local PENDING, N, CONNECTS, currWord, currFollowers, WORD, allWords, SEEN, TREE; 
SEEN := table(); 
TREE := {}; 
N := nops(W1); 
PENDING := DEQueue({W1}); 
for WORD in ENG()[N] do 
 SEEN[WORD] := 0; 
end do; 

SEEN[W1] := 1; 
while empty(PENDING) = false do 
 currWord := op(pop_front(PENDING)); 
 TREE := TREE union {currWord}; 
 currFollowers := C[N][currWord]; 

 for WORD in currFollowers do 
  if SEEN[WORD] = 0 then 
   SEEN[WORD] := 1; 
   push_back(PENDING, {WORD}); 
  end if; 
 end do; 
end do; 
return TREE; 
end proc;

#genTreeConnects: generates tree connects, 1..5 again should be changed.
#Very straightforward brute force
genTreeConnects := proc() local treeConnects, i1, j1, currWords, possWords, currTable, WORD; 
treeConnects := [seq(i1, i1 = 1 .. 5)]; 
for i1 to nops(treeConnects) do 
 currTable := table(); 
 currWords := ENG()[i1]; 
 possWords := ENG()[i1 + 1]; 
  for WORD in currWords do
   currTable[WORD] := Followers(WORD, possWords); 
  end do;
 treeConnects[i1] := copy(currTable); 
end do; 
treeConnects; 
end proc;

#findAllPyramids(N1, N2, Connects): read dfs function first!
#This just applies that function. you choose both the start and end lengths
findAllPyramids := proc(N1, N2, Connects) local WORD, startWords, PYRAMIDS; 
startWords := ENG()[N1]; 
PYRAMIDS := {}; 
for WORD in startWords do 
 PYRAMIDS := PYRAMIDS union {dfs([WORD], N2, Connects)}; 
end do; 
PYRAMIDS; 
end proc;

#dfs(currPath, N, Connects): just a depth first search
dfs := proc(currPath, N, Connects) local WORD, PYRAMIDS; 
if nops(currPath[-1]) = N then
 return {currPath}; 
end if; 
PYRAMIDS := {}; 
for WORD in Connects[nops(currPath[-1])][currPath[-1]] do
 PYRAMIDS := PYRAMIDS union {dfs([op(currPath), WORD], N, Connects)}; 
end do;
 op(PYRAMIDS); 
end proc;

##basic modification of findPath that keeps track of all words along the paths
Reachable := proc(W1, C) local PENDING, N, CONNECTS, currWord, currFollowers, WORD, allWords, SEEN, TREE; 
SEEN := table(); 
TREE := {}; 
N := nops(W1); 
PENDING := DEQueue({W1}); 
for WORD in ENG()[N] do 
 SEEN[WORD] := 0; 
end do; 

SEEN[W1] := 1; 
while empty(PENDING) = false do 
 currWord := op(pop_front(PENDING)); 
 TREE := TREE union {currWord}; 
 currFollowers := C[N][currWord]; 

 for WORD in currFollowers do 
  if SEEN[WORD] = 0 then 
   SEEN[WORD] := 1; 
   push_back(PENDING, {WORD}); 
  end if; 
 end do; 
end do; 
return TREE; 
end proc;

#genTreeConnects: generates tree connects, 1..5 again should be changed.
#Very straightforward brute force
genTreeConnects := proc() local treeConnects, i1, j1, currWords, possWords, currTable, WORD; 
treeConnects := [seq(i1, i1 = 1 .. 5)]; 
for i1 to nops(treeConnects) do 
 currTable := table(); 
 currWords := ENG()[i1]; 
 possWords := ENG()[i1 + 1]; 
  for WORD in currWords do
   currTable[WORD] := Followers(WORD, possWords); 
  end do;
 treeConnects[i1] := copy(currTable); 
end do; 
treeConnects; 
end proc;

#findAllPyramids(N1, N2, Connects): read dfs function first!
#This just applies that function. you choose both the start and end lengths
findAllPyramids := proc(N1, N2, Connects) local WORD, startWords, PYRAMIDS; 
startWords := ENG()[N1]; 
PYRAMIDS := {}; 
for WORD in startWords do 
 PYRAMIDS := PYRAMIDS union {dfs([WORD], N2, Connects)}; 
end do; 
PYRAMIDS; 
end proc;

#dfs(currPath, N, Connects): just a depth first search
dfs := proc(currPath, N, Connects) local WORD, PYRAMIDS; 
if nops(currPath[-1]) = N then
 return {currPath}; 
end if; 
PYRAMIDS := {}; 
for WORD in Connects[nops(currPath[-1])][currPath[-1]] do
 PYRAMIDS := PYRAMIDS union {dfs([op(currPath), WORD], N, Connects)}; 
end do;
 op(PYRAMIDS); 
end proc;

#=====ADDED
PyramidResult := proc(W1, W2) local N1, N2, Connects, PYRAMIDS, PYRAMID, Solutions;
N1 := nops(W1);
N2 := nops(W2);
Connects := genTreeConnects();
PYRAMIDS := findAllPyramids(N1, N2, Connects);
Solutions := {};
for PYRAMID in PYRAMIDS do
 if op(1, PYRAMID) = W1 and op(-1, PYRAMID) = W2 then
  Solutions := Solutions union {PYRAMID};
 end if;
end do;
return Solutions;
end proc;