#OKEY.txt: A Maple package for simulating and analyzing the game OKEY
#written ny Nuray Kutlu with advice from Doron Zeilberger
Help:=proc():
print(`OKEY.txt: a Maple package for simulating and studying and experimenting with generalized Okey`):
print(``):
if nargs=0 then
print(`The main procedures are: `):
print(` Deal, Tile, MiddleDeck, FindRuns, FindSets, FindRunsWJ, FindSetsWJ, GenerateRandomGrouping, StartGame, RemoveRandomTile, SimulateGame, SimulateGameT`):
print(`Tools for experimenting: RandomGamesP, RandomGamesN, RandomGamesL, RandomGamesC, SimulateGameT`):

elif nargs = 1 and args[1]=RandomGamesP then
print(`RandomGamesP(L,R,K) that inputs integers L, R, K.`):
print(`Keeps r, k , s, l controlled and tests p from L to R, the number of players in a game K times.`):
print(`Returns a list of how many games resuluted in a winner for each p.`):

elif nargs = 1 and args[1]=RandomGamesC then
print(`RandomGamesC(L,R,K) that inputs integers L, R, K.`):
print(`Keeps  k , p, s, l controlled and tests r from L to R, the number of colors for tiles K times.`):
print(`Returns a list of how many games resuluted in a winner for each r.`):

elif nargs = 1 and args[1]=RandomGamesN then
print(`RandomGamesN(L,R,K) that inputs integers L, R, K.`):
print(`Keeps r, p , s, l controlled and tests p from L to R, the number of numbers for tiles K times.`):
print(`Returns a list of how many games resuluted in a winner for each k.`):

elif nargs = 1 and args[1]=RandomGamesL then
print(`RandomGamesL(L,R,K) that inputs integers L, R, K.`):
print(`Keeps r, k , p, s controlled and tests l from L to R, the minimum grouping value in a game K times.`):
print(`Returns a list of how many games resuluted in a winner for each l.`):


elif nargs=1 and args[1]=Deal then
print(`Deal(r,k,p,s) that inputs integers r,k,p,s and outputs a list of lists of length`):
print(`p let's call it L such that L[i] is the "hand" of player i, where L[i] is a random list of length s. For example for the usual game, try:`):
print(`Deal(4,13,4,14);`):

elif nargs=1 and args[1]=Tile then
print(`Tile(r,k) that inputs r and k and outputs the initial deck LIST of`):
print(`[i,j], 1<=i<=k, 1<=j<=r`):
print(`For example try`):
print(` Tile(4.13);`):

elif nargs=1 and args[1]=MiddleDeck then
print(`MiddleDeck(Hands,r,k) that inputs list of lists Hands, and integers r,k and outputs a list`):
print(`of tiles un-used in Hands, which consists of the tiles dispersed between the players.`):
print(`For example `):
print(`H:=Deal(4,13,4,14); MiddleDeck(H,4,13);`):


elif nargs=1 and args[1]=FindRuns then
print(`FindRuns(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`):
print(`the runs of size at least s without jokers found in Hand.`):
print(`For example, try:`):
print(`H:=Deal(4,13,4,14)[1]; `):
print(`FindRuns(H,4,13,3);`):

elif nargs=1 and args[1]=FindSets then
print(`FindSets(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`):
print(`the sets of size at least s without jokers found in Hand.`):
print(`H:=Deal(4,13,4,14)[1]; `):
print(`FindSets(H,4,13,3);`):

elif nargs=1 and args[1]=FindRunsWJ then
print(`FindRunsWJ(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`):
print(`the sets of size at least s with jokers found in Hand.`):
print(`H:=Deal(4,13,4,14)[1]; `):
print(`FindRunsWJ(H,4,13,3);`):

elif nargs=1 and args[1]=FindSetsWJ then
print(`FindSetsWJ(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`):
print(`the sets of size at least s with jokers found in Hand.`):
print(`H:=Deal(4,13,4,14)[1]; `):
print(`FindSetsWJ(H,4,13,3);`):

elif nargs=1 and args[1] = GenerateRandomGrouping then
print(`GenerateRandomGrouping(Hand,r,k,s) that inputs a list, Hand, and integers r (number of tile colors), `):
print(`k (number of tile colors), and s (minimum length of groupings) and outputs a random grouping and "extra tile" pair`):
print(`which are tiles leftover in your hand that are not yet grouped. Returns [Groups, NewHand]`):
print(`H:=Deal(4,13,4,14)[1]; `):
print(`GenerateRandomGrouping(H,4,13,3);`):

elif nargs=1 and args[1] = StartGame then
print(`StartGame(r,k,p,s, l) that inputs integers r, k, p, s, l and prints out the`):
print(`initial state of a game of Okey with p players each dealt a hand of length s with tiles`):
print(`numbered 1-k numbers and colored 1-r colors, and initial groupings of min length l`):
print(`Try StartGame(4,13,4,14, 3)`):

elif nargs=1 and args[1] = SimulateGame then
print(`SimulateGame(r,k,p,s, l) that inputs integers r, k, p, s, l and simulated`):
print(`a game of Okey with p players each dealt a hand of length s with tiles`):
print(`numbered 1-k numbers and colored 1-r colors, and initial groupings of min length l`):
print(`Try SimulateGame(4,13,4,14, 3)`):

elif nargs=1 and args[1] = SimulateGameT then
print(`SimulateGameT(r,k,p,s, l) that inputs integers r, k, p, s, l and simulated`):
print(`a game of Okey with p players each dealt a hand of length s with tiles`):
print(`numbered 1-k numbers and colored 1-r colors, and initial groupings of min length l`):
print(`Returns a pair of the number of moves played and the winning player (returns 0 if there is none).`):
print(`Try SimulateGameT(4,13,4,14, 3)`):

elif nargs=1 and args[1] = RemoveRandomTile then
print(`RemoveRandomTile(Tiles) picks a random tile from a list of tiles "Tiles", and returns a pair [tile to remove, list of rest of tiles]`):
print(`Try the following: `):
print(`H:=Deal(4,13,4,14)[1];`):
print(`LeftoverTiles:=GenerateRandomGrouping(H,4,13,3)[2];`):
print(`RemoveRandomTile(LeftoverTiles);`):

else
print(`There is no Help for`, args[1]):
fi:

end:


# Generalized OKEY r=4 k=13  p players (p>=1) and every player gets s random tiles
# 2*r sets of tiles labeled 1,...,k (later we will add the two jokers)
#2*r*k+2 tiles
#2*4*13+2 = 106
                              
#Next time:
#Write a Maple procedure convention the jokers are 0
#Tile(r,k) that inputs r and k and outputs the LIST of
#[i,j], 1<=i<=k, 1<=j<=r
Tile:=proc(r,k) local i,j,L:
L:=[seq(seq([i,j],j=1..r),i=1..k)]:
[op(L),op(L),0,0]:
end:

#Write a Maple procedure
#Deal(r,k,p,s) that inputs integers r,k,p,s and outputs a list of lists of length
#p let's call it L such that L[i] is the "hand" of player i, where L[i] is a random list of length s
# remember that p players, every player gets s tiles, 2
#use the Maple command rand()  
# basically every player has s tiles


Deal:=proc(r,k,p,s) local T, L, i, PD, tile, j:
T:= Tile(r,k):
if (p*s > nops(T)) then 
 print (`Not enough tiles for all players!`):
 RETURN(FAIL):
fi:
L:= []:
for i from 1 to p do:
 PD:=[];
  for j from 1 to s do:
   tile:= rand(1..nops(T))():
   PD:= [op(PD), T[tile]]:
   T:=subsop(tile=NULL, T):
  od:
L:= [op(L), PD]:
od:
L:
end:

# Write a Maple procedure 
# MiddleDeck(Hands,r,k) that outputs the middle deck (the tiles that are not dispersed)

MiddleDeck:=proc(Hands,r,k) local T, i, j , l:
T:= Tile(r,k):
for i from 1 to nops(Hands) do:
 for j from 1 to nops(Hands[i]) do:
  for l from 1 to nops(T) do:
   if (Hands[i][j] = T[l]) then:
    T := subsop(l = NULL, T):
    l := nops(T) + 1:
   fi:
  od:
 od:
od:
T:
end:


#FindRuns(Hand,r,k,s)
#with exactly s members

FindRuns:=proc(Hand, r, k, s) local i, j, left, right, Runs, Run, RunI:

if (k < s) then 
 print(`Bad Input!`):
fi:

Runs:= []:

for i from 1 to nops(Hand) do:
  RunI:= [i]:
  Run:= [Hand[i]]:
  left:= Hand[i]:
  right:= Hand[i]:
  for j from 1 to nops(Hand) do:
    if ((Hand[j][1] = (left[1] - 1)) and (Hand[j][2] = left[2])) then
     RunI:= [op(RunI), j]:
     Run:= [Hand[j], op(Run)]:
     left:= Hand[j]:
    elif ((Hand[j][1] = (right[1] + 1)) and (Hand[j][2] = right[2])) then
     RunI:= [op(RunI), j]:
     Run:= [op(Run), Hand[j]]:
     right:= Hand[j]:
    fi:
  od:
  if (nops(Run) >= s) then
   if (not member(Run,Runs)) then 
     Runs := [op(Runs), Run]:
   fi:
  fi:
od:
Runs:
end:

#FindSets(Hand,r,k,s)

FindSets:=proc(Hand,r,k,s) local Sets, SetI, i, j, Set, colors, number:

if (r < s) then 
 print(`Bad Input!`):
fi:

Sets:=[]:

for i from 1 to nops(Hand) do:
  SetI:=[i]:
  Set:= [Hand[i]]:
  colors:= [Hand[i][2]]:
  number:= Hand[i][1]:
  for j from 1 to nops(Hand) do:
    if ((Hand[j][1] = number) and (not (evalb( Hand[j][2] in colors)))) then
     SetI:= [op(SetI), j]:
     Set:= [Hand[j], op(Set)]:
     colors:= [op(colors), Hand[j][2]]:
    fi:
  od:
  if (nops(Set) >= s) then
   Set := sort(Set):
   if (not member(Set,Sets)) then 
     Sets:= [op(Sets), Set]:
   fi:
   for j from 1 to nops(SetI) do:
    subsop(SetI[j] = 1, Hand):
   od:
  fi:
od:

Sets:
end:

# Write FindRunsWJ and FindSetsWJ that finds runs and sets with jokers

#FindRunsWJ(Hand,r,k,s)
#with exactly s members

FindRunsWJ:=proc(Hand, r, k, s) local i, Runs, jokercount:

if (k < s) then 
 print(`Bad Input!`):
fi:

Runs:= []:

jokercount:= 0:

for i from 1 to nops(Hand) do:
 if (Hand[i] = 0) then
  jokercount++:
 fi:
od:

if (jokercount = 0) then
 Runs:= FindRuns(Hand, r, k, s):
elif (jokercount = 1) then
 Runs:= FindRuns(Hand, r, k, s-1):
 for i from 1 to nops(Runs) do
  if (nops(Runs[i]) = (s - 1)) then
   Runs[i] := [op(Runs[i]), 0]:
  fi:
 od:
else
 Runs:= FindRuns(Hand, r, k, s-2):
 for i from 1 to nops(Runs) do
  if (nops(Runs[i]) = (s - 1)) then
   Runs[i] := [op(Runs[i]), 0]:
  elif (nops(Runs[i]) = (s - 2)) then
   Runs[i] := [op(Runs[i]), 0]:
  fi:
 od:
fi:

Runs:
end:


FindSetsWJ:=proc(Hand, r, k, s) local i, Sets, jokercount:

if (k < s) then 
 print(`Bad Input!`):
fi:

Sets:= []:

jokercount:= 0:

for i from 1 to nops(Hand) do:
 if (Hand[i] = 0) then
  jokercount++:
 fi:
od:

if (jokercount = 0) then
 Sets:= FindSets(Hand, r, k, s):
elif (jokercount = 1) then
 Sets:= FindSets(Hand, r, k, s-1):
 for i from 1 to nops(Sets) do
  if (nops(Sets[i]) = (s - 1)) then
   Sets[i] := [op(Sets[i]), 0]:
  fi:
 od:
else
 Sets:= FindSets(Hand, r, k, s-2):
 for i from 1 to nops(Sets) do
  if (nops(Sets[i]) = (s - 1)) then
   Sets[i] := [op(Sets[i]), 0]:
  elif (nops(Sets[i]) = (s - 2)) then
   Sets[i] := [op(Sets[i]), 0]:
  fi:
 od:
fi:

Sets:
end:


GenerateRandomGrouping:= proc(Hand, r, k, s) local i, flagRS, Groups, Runs, Sets, flagsRS, Set, Run, NewHand:
 #flagRS will first check if there is more in findrunsWJ or findsetsWJ and prioritize 
 #starting with runs or sets based on that, but if they're equal then it prioritizes randomly
 Groups:= []:
 Runs:= FindRunsWJ(Hand, r, k , s):
 Sets:= FindSetsWJ(Hand, r, k, s):

NewHand:= Hand:
 
 flagRS := 0:
 if(nops(Runs) > nops(Sets)) then
  flagRS := 1:
 elif(nops(Sets) = nops(Runs)) then
  flagRS := rand(0..1)():
 fi:
 
 if(flagRS = 0) then
  while nops(Sets) <> 0 do:
   Set:= Sets[1]:
   Groups:= [op(Groups), Set]:
   NewHand := UpdateHands(NewHand, Set):
   Sets := FindSetsWJ(NewHand, r, k, s):
  od:
  Runs:= FindRunsWJ(NewHand, r, k, s):
  while nops(Runs) <> 0 do:
   Run:= Runs[1]:
   Groups:= [op(Groups), Run]:
   NewHand:= UpdateHands(NewHand, Run):
   Runs:= FindRunsWJ(NewHand, r, k, s):
  od:
 else
  while nops(Runs) <> 0 do:
   Run:= Runs[1]:
   Groups:= [op(Groups), Run]:
   NewHand:= UpdateHands(NewHand, Run):
   Runs:= FindRunsWJ(NewHand, r, k, s):
  od:
  Sets := FindSetsWJ(NewHand, r, k, s):
  while nops(Sets) <> 0 do:
   Set:= Sets[1]:
   Groups:= [op(Groups), Set]:
   NewHand := UpdateHands(NewHand, Set):
   Sets := FindSetsWJ(NewHand, r, k, s):
  od:
 fi:
[Groups, NewHand]:
end:

UpdateHands:=proc(Hand,Group) local i, j, k1, B, NewHand:

NewHand:= Hand:

 for i from 1 to nops(Group) do:
  j := 1:
  B:= 0:

  if(evalb(Group[i] <> NewHand[j])) then
   B:=1:
  fi:

  while B = 1 do:  
   j++:
   if(evalb(Group[i] = NewHand[j])) then
    B:=0:
   fi:
  od:

  NewHand:=subsop(j=NULL, NewHand):

 od:
 NewHand:
end:

#StartGame() starts a game of Okey with p players, s tiles per player,
# k numbers in the tiles, kr colors in the tiles, and sets of length l.
#It prints the starting state of the game.

StartGame:=proc(r,k,p,s, l) local Hands, PlayerGroups, i,j, Group, GHPair, PlayerTiles, Tiles, statement,ExtraTiles :
Hands:= Deal(r,k,p,s):
ExtraTiles:= MiddleDeck(Hands,r,k):
PlayerGroups := []:
PlayerTiles:= []:
for i from 1 to nops(Hands) do:
 GHPair:= GenerateRandomGrouping(Hands[i],r,k,l):
 Group:= GHPair[1]:
 Tiles:= GHPair[2]:
 PlayerGroups:= [op(PlayerGroups), Group]:
 PlayerTiles:= [op(PlayerTiles), Tiles]:
od:

#print(`The middle deck is currently: `):
statement:= "":
for i from 1 to nops(ExtraTiles) do:
 statement:= cat(op(statement), " ", ExtraTiles[i]):
od:

 #print(statement):
 #print(``):

for i from 1 to nops(Hands) do:
 if(nops(PlayerGroups[i]) = 0) then
  statement:= cat("Player ", i, " has no groupings and the leftover tiles ", op(PlayerTiles[i]), "."):
 else 
  statement:= cat("Player ", i, " has the groupings ", seq(cat(PlayerGroups[i][j], ", "), j = 1..nops(PlayerGroups[i])), " and the leftover tiles ", op(PlayerTiles[i]), "."):
 fi:
 #print(statement):
 #print(` `):
od:

[Hands, PlayerGroups, PlayerTiles, ExtraTiles]:
end:

#RemoveRandomTile(Tiles) picks a random tile from a list of tiles, and returns a pair 
#[tile to remove, list of rest of tiles]
RemoveRandomTile:=proc(Tiles) local i, TilesUpd:
 i:= rand(1..nops(Tiles))():
 TilesUpd:= UpdateHands(Tiles, [Tiles[i]]):
 [Tiles[i], TilesUpd]:
end:


SimulateGame:=proc(r,k,p,s, l) local GameStatus, Hands, PlayerGroups, PlayerTiles, ExtraTiles, TrashTiles, HandPart, prevTile, RandomGrouping, i, PotentialHand, statement:

GameStatus:= StartGame(r,k,p,s, l):

Hands:= GameStatus[1]:
PlayerGroups:= GameStatus[2]:
PlayerTiles:= GameStatus[3]:

ExtraTiles:= GameStatus[4]:
TrashTiles := []:

#The first player gets handled seperately, as it only has one choice of tile.
HandPart := RemoveRandomTile(ExtraTiles):
prevTile := HandPart[1]:
ExtraTiles := HandPart[2]:

Hands[1] := [op(Hands[1]), prevTile]:
RandomGrouping := GenerateRandomGrouping(Hands[1], r, k, l):
PlayerGroups[1] := RandomGrouping[1]:
PlayerTiles[1] := RandomGrouping[2]:

HandPart := RemoveRandomTile(PlayerTiles[1]):
prevTile:= HandPart[1]:
PlayerTiles[1] := HandPart[2]:

i := 2:
while (nops(ExtraTiles) <> 0) do:
 # First try regrouping and checking extra tile count. 
 # if it's not the same or less extra tiles, then pick something at random
 PotentialHand := [op(Hands[i]), prevTile]:
 RandomGrouping := GenerateRandomGrouping(PotentialHand, r, k, l):
 if (nops(PlayerTiles[i]) >= nops(RandomGrouping[2])) then 
  Hands[i] := PotentialHand:
  PlayerGroups[i] := RandomGrouping[1]:
  PlayerTiles[i] := RandomGrouping[2]:
 else 
  TrashTiles:= [op[TrashTiles], prevTile]:
  HandPart:= RemoveRandomTile(ExtraTiles):
  prevTile:= HandPart[1]:
  ExtraTiles := HandPart[2]:
  Hands[i] := [op(Hands[i]), prevTile]:
  RandomGrouping := GenerateRandomGrouping(Hands[i], r, k, l):
  PlayerGroups[i] := RandomGrouping[1]:
  PlayerTiles[i] := RandomGrouping[2]:
 fi:


 print(`i am player`):
 print(i):
 print(`my groupings are:`):
 print(PlayerGroups[i]):
 

 if(nops(PlayerTiles[i]) = 1) then
  statement := cat("Player ", i, " wins! Here are their groups: ", PlayerGroups[i]):
  print(statement):
  return:
 fi: 

 HandPart := RemoveRandomTile(PlayerTiles[i]):
 prevTile := HandPart[1]:
 print (` I removed `):
 print(prevTile):
 PlayerTiles[i] := HandPart[2]:
 print(`my leftover tiles are:`):
 print(PlayerTiles[i]):


 i := i+ 1:
 if (i = p+1) then
  i := 1:
 fi:
od:

print(`This game terminated since there are no middle tiles left.`)

end:


SimulateGameT := proc(r,k,p,s, l) local GameStatus, moves, Hands, PlayerGroups, PlayerTiles, ExtraTiles, TrashTiles, HandPart, prevTile, RandomGrouping, i, PotentialHand, statement:

GameStatus:= StartGame(r,k,p,s, l):

Hands:= GameStatus[1]:
PlayerGroups:= GameStatus[2]:
PlayerTiles:= GameStatus[3]:

ExtraTiles:= GameStatus[4]:
TrashTiles := []:

#The first player gets handled seperately, as it only has one choice of tile.
HandPart := RemoveRandomTile(ExtraTiles):
prevTile := HandPart[1]:
ExtraTiles := HandPart[2]:

Hands[1] := [op(Hands[1]), prevTile]:
RandomGrouping := GenerateRandomGrouping(Hands[1], r, k, l):
PlayerGroups[1] := RandomGrouping[1]:
PlayerTiles[1] := RandomGrouping[2]:

HandPart := RemoveRandomTile(PlayerTiles[1]):
prevTile:= HandPart[1]:
PlayerTiles[1] := HandPart[2]:

i := 2:
moves := 1:

while (nops(ExtraTiles) <> 0) do:
 moves := moves +1:
 # First try regrouping and checking extra tile count. 
 # if it's not the same or less extra tiles, then pick something at random
 PotentialHand := [op(Hands[i]), prevTile]:
 RandomGrouping := GenerateRandomGrouping(PotentialHand, r, k, l):
 if (nops(PlayerTiles[i]) >= nops(RandomGrouping[2])) then 
  Hands[i] := PotentialHand:
  PlayerGroups[i] := RandomGrouping[1]:
  PlayerTiles[i] := RandomGrouping[2]:
 else 
  TrashTiles:= [op[TrashTiles], prevTile]:
  HandPart:= RemoveRandomTile(ExtraTiles):
  prevTile:= HandPart[1]:
  ExtraTiles := HandPart[2]:
  Hands[i] := [op(Hands[i]), prevTile]:
  RandomGrouping := GenerateRandomGrouping(Hands[i], r, k, l):
  PlayerGroups[i] := RandomGrouping[1]:
  PlayerTiles[i] := RandomGrouping[2]:
 fi:

 HandPart := RemoveRandomTile(PlayerTiles[i]):
 prevTile := HandPart[1]:
 PlayerTiles[i] := HandPart[2]:

 
 if(nops(PlayerTiles[i]) <= 1) then
  return [moves,i]:
 fi: 

 i := i+ 1:
 if (i = p+1) then
  i := 1:
 fi:
od:

return [moves, 0]:

end:


# takes in a range L to R and tests K times to see how many games with 
# players from L to R result in winning games.
# the rest of the parameters are default (4, 13 , P, 14, 3)
# returns a list of length R - L + 1 of how many games resulted in someone winning
RandomGamesP:= proc(L, R, K) local i, j, count, List:
List:= []:
 for i from L to R do:
  count := 0:
  for j from 1 to K do:
   if (SimulateGameT(4, 13, i, 14, 3)[2] <> 0) then 
    count := count + 1:
   fi:
  od:
  List := [op(List), count]:
 od:
List:
end:

# takes in a range from L to R and tests K times to see how many games with
# group sizings from L to R result in winning games
# the rest of the parameters are (4, 13, 4, 14, L)
# returns a list of length R - L + 1 of how many games resulted in someone winning
RandomGamesL:= proc(L, R, K) local i, j, count, List:
List:= []:
 for i from L to R do:
  count := 0:
  for j from 1 to K do:
   if (SimulateGameT(4, 13, 4, 14, i)[2] <> 0) then 
    count := count + 1:
   fi:
  od:
  List := [op(List), count]:
 od:
List:
end:

# takes in a range from L to R and tests K times to see how many games with
# color/r values from L to R result in winning games
# the rest of the parameters are (C, 13, 4, 14, 3)
# returns a list of length R - L + 1 of how many games resulted in someone winning
RandomGamesC:= proc(L, R, K) local i, j, count, List:
List:= []:
 for i from L to R do:
  count := 0:
  for j from 1 to K do:
   if (SimulateGameT(i, 13, 4, 14, 3)[2] <> 0) then 
    count := count + 1:
   fi:
  od:
  List := [op(List), count]:
 od:
List:
end:

# takes in a range from L to R and tests K times to see how many games with
# number/k values from L to R result in winning games
# the rest of the parameters are (4, N, 4, 14, 3)
# returns a list of length R - L + 1 of how many games resulted in someone winning
RandomGamesN:= proc(L, R, K) local i, j, count, List:
List:= []:
 for i from L to R do:
  count := 0:
  for j from 1 to K do:
   if (SimulateGameT(4, i, 4, 14, 3)[2] <> 0) then 
    count := count + 1:
   fi:
  od:
  List := [op(List), count]:
 od:
List:
end: