# Joey Reichert # 640:640 Spring 2013 # February 11, 2013 # hw6.txt # I give permission to post Help:=proc() : print("ConWay1(L,R,i); ConWay(L,R); Sig(L,R); AveSig(n,k,K)"): end: # Problem #1 # Write a program ConWay1(L,R,i) that inputs # two directed graphs on {1, ...n} # (where n=nops(L)=nops(R)) representing a # partizan game, and an integer i between # 1 and n, representing a game-position # (alias "game" in Conway's sense) and outputs # it in Conway's format, as a pair of # sets of simpler "games" where the very # bottoms are empty sets. ConWay1:=proc(L,R,i) local n, j: return [{seq(ConWay1(L,R,j), j in L[i])},{seq(ConWay1(L,R,j), j in R[i])}]: end: # Problem #2 # Using ConWay1(L,R,i) above write a # one-line program, ConWay(L,R), that inputs # two directed graphs in the above format and # outputs the list of length n:=nops(L) (=nops(R)) # whose i-th entry is ConWay1(L,R) ConWay:= proc(L,R) local i: return [seq(ConWay1(L,R,i), i in 1..nops(L))]: end: # Problem #3 # Define the signature of a partizan game given # as a pair of directed graphs (L,R) the expression # a*"Zero"+b*"Positive"+c*"Negative"+ d*"Fuzzy" # where a+b+c+d=n, and there are a "Zero" positions, # b "Positive" positions etc. # Write a program Sig(L,R) that inputs a pair # of directed graphs with the same number of # vertices and output its signature. Sig:= proc(L,R) local G: return add(WhatKind(G), G in ConWay(L,R)); end: # Problem #4 # By using RandDi(n,k) in C5.txt, # 2*K times, write a program # AveSig(n,k,K), that picks K random games # and outputs their average signature. # What do you get for AveSig(10,3,100)? # Do you get similar results all the time? AveSig:= proc(n,k,K) local i: return add(Sig(RandGame(n,k),RandGame(n,k)),i=1..K)/K; end: # AveSig(10,3,100) = 1.64*Positive+1.91*Negative+4.83*Fuzzy+1.62*Zero # Similar results every time ### OLD STUFF ### # CanLeftWin(G): Can left win the game G? CanLeftWin:=proc(G) local L: option remember: return evalb(true in {seq(not CanRightWin(L), L in G[1])}); end: # CanRightWin(G): Can left win the game G? CanRightWin:=proc(G) local R: option remember: return evalb(true in {seq(not CanLeftWin(R), R in G[2])}); end: # WhatKind(G): Is the game positive, negative, zero, or fuzzy? # Zero if player 1 always wins # Fuzzy if player 2 always wins # Positive if left always wins # Negative if right always wins WhatKind:=proc(G) local a,b: a:=CanLeftWin(G): b:=CanRightWin(G): if a and b then return `Fuzzy`; elif a and not b then return `Positive`; elif b and not a then return `Negative`; else return `Zero`; fi: end: #RandDi(n,k): a random directed graph with n #vertices and (usually) outdegree k RandDi:=proc(n,k) local ra,i,j: ra:=rand(1..n): [seq({seq(ra(),i=1..k)} minus {j} ,j=1..n)]: 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: ### END OLD STUFF ###