#Ross' hw2.txt #This is fully available for public posting should there be any reason at all to do so. Help:=proc(): print("RanMat(n,k), HowManySigulars(n,k,K), AveLosing(n,k,K), ProbWinStupid(G,i), pwn(k,i), pwni(N,i)"): end: #RanMat(n,k) Produces a random nxn matrix with entries in [k]. RanMat:=proc(n::posint,k::posint) local i,j,M: with(linalg); M:=matrix(n,n): for i from 1 to n do for j from 1 to n do M[i,j]:=rand(1..k)(): od: od: op(M): end: #HowManySigulars (sp.?) generates K random matrices and checks #how many of them are singular mod k. HowManySigulars:=proc(n::posint, k::posint, K::posint) local i,count,M: with(linalg); count:=0: for i from 1 to K do M:=RanMat(n,k): if det(M) mod k=0 then count:=count+1: fi: od: RETURN(count): end: #AveLosing(n,k,K) checks K random games of size n with average number of moves k # and sees what percentage of positions were losing. AveLosing:=proc(n::posint,k,K::posint) local i,j,G,L,count: with(linalg); count:=0: for i from 1 to K do G:=RandGame(n,k): L:=WL(G): count:=count+(add(j, j in L))/n: od: count:=count/K: RETURN(count): end: #ProbWinStupid(G,i) shows the probability of winning at vertex i in a game G if each #player plays randomly. ProbWinStupid:=proc(G,i::posint) local j,l,s: option remember: with(linalg); if IsCyclic(G) then print("Error: The Graph is Cyclic"): RETURN(FAIL): fi: if G[i]={} then RETURN(0): fi: l:=nops(G[i]): s:=1-add(ProbWinStupid(G,j), j in G[i])/nops(G[i]): RETURN(s): end: #Checks Prob Win Stupid for penny game with pile N and moves k and position i pwni:=proc(k::posint,i::posint) local j,l: option remember: if i=1 then RETURN(0): fi: l:=min(i-1,k): RETURN(1-add(pwni(l,i-j), j=1..l)/l): end: #prints pwni for all i in a given game pwn:=proc(k,N) local j: option remember: RETURN(seq(pwni(k,j),j=1..N)): end: #The Rest of the Code is lovingly swiped from Dr. Z and the class website. #IsCyclic Checks were removed to speed up runtime. #IsCyclic(G): inputs a directed graph (described as #a list of sets, andoutputs true (false) if it has #a cycle IsCyclic:=proc(G) local i,M1,M: option remember: M:=AM(G): M1:=M: #Soon-to-be PhD candidate #Jacob Baron thinks that it safer to do nops(G)+1 for i from 1 to nops(G)+1 do if trace(M1)>0 then RETURN(true): fi: M1:=evalm(M1*M): od: false: end: #fGi(G,i), inputs a directed graph G and #an integer i between 1 and nops(G) and outputs #0(resp. 1) if vertex i is a Losing (Winning) position fGi:=proc(G,i) local M,m: option remember: if G[i]={} then RETURN(0): fi: M:=G[i]: if {seq(fGi(G,m), m in M)}={1} then RETURN(0): else RETURN(1): fi: end: with(linalg): #AM(G): adjacency matrix of G (written a matrix M) #M[i,j]=1 (0) of j belongs (does not belong) #to G[i] AM:=proc(G) local n,i,j,M: n:=nops(G): M:=matrix(n,n): for i from 1 to n do for j from 1 to n do if j in G[i] then M[i,j]:=1: else M[i,j]:=0: fi: od: od: op(M): end: #WL(G): Winning list #Inputs a directed G (representing a game) #and outputs a list of length nops(G) such that #L[i]=0 or 1 according to whether position (vertex) i #is a losing or winning position WL:=proc(G) local i: [seq(fGi(G,i),i=1..nops(G))]: end: #RandGame(n,k): inputs pos. integers n and k #and outputs a random digraph that has the #property that out of vertex i all the labels #are less i, and there are (usually) k outgoing #edges RandGame:=proc(n,k) local L,i,tomas,j: L:=[{}]: for i from 2 to n do tomas:={seq(rand(1..i-1)(),j=1..k)}: L:=[op(L), tomas]: od: L: end: