#C19.txt: April 2, 2020
#Simulating and Studying the card game War with cards 1,...2*n
Help:=proc(): print(` RandDeck(n), OneGameV(n,K), OneGame(n,K), ManyGames(n,K,t,M), DistD(P), WarGF(n,t) , WarGFplus(n,t), PlayGame(INI) , FIN(INI)`): end:

with(combinat):

#RandDeck(n): A random starting position with cards 1, ..., 2*n, The output
#is a list of length 2 with the decks of the first player
RandDeck:=proc(n) local i,pi:
pi:=randperm(2*n):


[[seq(pi[i],i=1..n)], [seq(pi[i],i=n+1..2*n)]]:
end:

#OneMove(P): One move in a 2-player War where the winning card and card won goes to the BOTTOM of the winner's deck
#with the won card exactly at the bottom, and the winning card on top of it. Try
#OneMove([[3,1,4],[2,5,6]]); should return [[1,4,3,2],[5,6]].

OneMove:=proc(P) local a,b:
option remember:
if P[1]=[] then
print(`Player2 won`):
RETURN(FAIL):
fi:


if P[2]=[] then
print(`Player1 won`):
RETURN(FAIL):
fi:

a:=P[1][1]:

b:=P[2][1]:

if a<b then
[[op(2..nops(P[1]),P[1])],[op(2..nops(P[2]),P[2]),b,a]]:
else
[[op(2..nops(P[1]),P[1]),a,b], [op(2..nops(P[2]),P[2])]]:
fi:

end:

#OneGameV(n,K): VERBOSE VERSION.Simulates one game with 2*n cards, two players and the deck being {1, ..., 2*n}
#it prints out all the intermedia steps. K is the maximum length allowed. Try:
#OneGameV(4,100);
OneGameV:=proc(n,K) local P,i:
P:=RandDeck(n):
print(`The starting decks are`):
print(P[1],P[2]):


for i from 1 to K while P[1]<>[] and P[2]<>[] do
P:=OneMove(P):
print(P[1],P[2]):
od:

if i=K+1 then
 print(`The game did not end in less than`, K, ` moves `):
elif  P[1]=[] then
 print(`Player Right won and it took`, i-1, `moves `):
elif  P[2]=[] then
 print(`Player Left won and it took`, i-1, `moves `):
else
print(`Something is wrong`):
fi:
i-1:
end:


#OneGame(n,K): TERSE version.Simulates one game with 2*n cards, two players and the deck being {1, ..., 2*n}
#Returns the pair [winner, numer of moves]
#OneGame(4,100);
OneGame:=proc(n,K) local P,i:
P:=RandDeck(n):

for i from 1 to K while P[1]<>[] and P[2]<>[] do
P:=OneMove(P):
od:

if i=K+1 then
 RETURN(FAIL):
elif  P[1]=[] then
  RETURN([2,i-1]):
elif  P[2]=[] then
  RETURN([1,i-1]):
else
 RETURN(FAIL):
fi:

end:

#ManyGames(n,K,t,M): inputs a positive integer n and a large pos. integer K, a variable t runs
#outputs the triple
#[G.f for duration if Left won,G.f for duration if Right won,Number of Games that did not end in K moves]
ManyGames:=proc(n,K,t,M) local f1,f2,f3,i,G:
f1:=0:
f2:=0:
f3:=0:

for i from 1 to M do
 G:=OneGame(n,K):
 if G=FAIL then
    f3:=f3+1:
 elif G[1]=1 then
  f1:=f1+t^G[2]:
 elif G[1]=2 then
   f2:=f2+t^G[2]:
 fi:
od:

[f1,f2,f3]:


end:

#DistD(P): The distance of a pair from the end.
#Try
#DistD([[1,2,3],[4,5,6]]);
DistD:=proc(P) local Q:
option remember:

if P[1]=[] or P[2]=[] then
 RETURN(0):
fi:

Q:=OneMove(P):
DistD(Q)+1:
end:



#WarGF(n,t): The distance generating function to the end of all initial decks

WarGF:=proc(n,t) local S,s:
S:=permute(2*n):

S:={seq([[op(1..n,s)],[op(n+1..2*n,s)]], s in S)}:

add(t^DistD(s), s in S):

end:

#########################################
#Added April 2, 2020 before class
#WarGFplus(n,t): The distance generating function to the end of all initial decks
#also returns the maximal length and the champions
WarGFplus:=proc(n,t) local S,s,rec,cha,su,val:
S:=permute(2*n):

S:={seq([[op(1..n,s)],[op(n+1..2*n,s)]], s in S)}:

rec:=0:

cha:={}:

su:=0:

for s in S do
val:=DistD(s):
su:=su+t^val:
if val>rec then
 rec:=val:
 cha:={s}:
elif val=rec then
 cha:=cha union {s}:
fi:
od:
[su,rec,cha]:

end:




#PlayGame(INI):Plays a game with initial deck INI. 
#Try:
#PlayGame([[1,2],[3,4]]);
PlayGame:=proc(INI) local P,co:
P:=INI:
print(`The starting decks are`):
print(P[1],P[2]):
co:=0:

while P[1]<>[] and P[2]<>[] do
co:=co+1:
P:=OneMove(P):
print(P[1],P[2]):
od:

print(`The game lasted`, co, `moves `):

if P[2]=[] then
 print(`The Left player won, its final deck was `):
 print(P[1]):
else
 print(`The Right player won, its final deck was `):
 print(P[2]):
fi:

[co,P]:
end:



#FIN(INI):Plays a game with initial deck INI. Only outputs the number of moves and the final deck
#Try:
#FIN([[1,2],[3,4]]);
FIN:=proc(INI) local P,co:
P:=INI:

co:=0:

while P[1]<>[] and P[2]<>[] do
co:=co+1:
P:=OneMove(P):
od:


if P[2]=[] then
  RETURN([co,P[1]]):
else
  RETURN([co,P[2]]):
fi:

end: