#OK to post homework
#Blair Seidler, 4/10/22, Assignment 20
with(combinat):

Help:=proc():
print(`ConjLP(R), ProveLP(R,M,C), Nim(N), NimL(k,N), Nim2V(a,b), Nim2VL(N)`):
end:

#1. Write a procedure ConjLP(R) that inputs a finite set of positive integers R, and outputs the pair
# [M,C] where M is a positive integer ≥ 2 and C is a subset of {0,1,...,M-1} such that PR(n,R)[1]=0
# if and only if n mod M belongs to C. For exmaple, ConjLP({1,2}) should output [3,{0}]
# [Hint, first output LP(10000,R), call it, L, say, then look for the smallest M such that
# convert(L mod M,set) has less than M elements. This is your conjectured M. Then, for that M,
# convert(L mod M,set) is your conjectured C.
ConjLP:=proc(R) local L,M,C,l,maxl,i,j,k,N,D:
maxl:=10*add(R):
N:={seq(i,i=1..maxl)}:
L:=convert(LP(maxl,R),set):
for M from 1 to floor(maxl/2) do
  C:=convert(L mod M,set):
  if nops(C)<M then
    D:={seq(seq(j*M+k,k in C),j in 0..ceil(maxl/M))} intersect N:
    if D subset L then
      RETURN([M,C]):
    fi:
  fi:
od:
RETURN(FAIL):
end:

#2. [A little bit challenging, but do your best] Write a procedure ProveLP(R,M,C)
# that proves automatically the conjecture that indeed n is a losing position for the R-game
# iff n mod M belongs to C, or returns FAIL.
# Hint: the defining propery of the set of losing positions of a game is that every legal move
# (in this game, subtracting an element of R), is NOT in that set, and for every element, n,
# NOT in that set, there exists an element r, in R, such that n-r is in the set.
ProveLP:=proc(R,M,C) local i:
for i from 1 to 4*add(R) do
  if i mod M in C then
    if PR(i,R)[1]=1 then
      printf("Counterexample: %d=%d mod %d is a winning position\n",i,i mod M,M):
      return(false):
    fi:
  else
    if PR(i,R)[1]=0 then
      printf("Counterexample: %d=%d mod %d is a losing position\n",i,i mod M,M):
      return(false):
    fi:
  fi:
od:
true:
end:

#3. The classical game of k-file Nim consists of k piles having n[1],..., n[k] pennies respectively,
# and a legal move consists of taking as many pennies as one wishes (from 1 to the whole pile) from
# ONE pile. For exmaple from the position [3,2,2] one can reach, in one move
# [2,2,2],[1,2,2],[0,2,2];[3,1,2],[3,0,2];[3,2,1],[3,2,0];
# Write a procedure Nim(N) that inputs a list of non-negative integers of length k:=nops(N) and
# outputs 0,{} if it is a losing position, and 1,S, if it is a winning positiion where S is a list
# of pairs {[a,b]} meaning: remove b pennies from the a-th pile. For example
# Nim([3,3]) should output "0,{}" while Nim([7,3]) should output 1,{[1,4]}
# [Modified April 7, 2022: By symmety, the winning vs. losing status is invariant under permutation,
# so it would be more efficient just to output the list of weakly-increasing (or if you wish,
# weakly-decreasing) losing positions.
Nim:=proc(N) local p,r,W,i,n:
option remember:
n:=nops(N):
W:={}:
for p from 1 to n do
  for r from N[p] to 1 by -1 do
    if Nim(N-[seq(0,i=1..p-1),r,seq(0,i=p+1..n)])[1]=0 then
      W:=W union {[p,r]}:
    fi:
  od:
od:
if nops(W)=0 then RETURN(0,{}): fi:
1,W:
end:

#4. Write a procedure NimL(k,N) that inputs a positive integer k, another positive integer N and
# outputs the set of lists of length k with entries ≤ N that are losing positions for k-pile Nim.
# For example NimL(2,3); should output {[0,0],[1,1],[2,2],[3,3]}

WIpos:=proc(k,N) local i,P,p,prev:
if k=1 then RETURN({seq([i],i=0..N)}): fi:
prev:=WIpos(k-1,N):
P:={}:
for p in prev do
  P:=P union {seq([i,op(p)],i=0..p[1])}:
od:
P:
end:

NimL:=proc(k,N) local P,p,L:
P:=WIpos(k,N):
L:={}:
for p in P do
  if Nim(p)[1]=0 then L:=L union {p}: fi:
od:
L:
end:

#5.

(* It looks like the losing positions have one of the following forms:

[0,a,a]
[1,b,b+1] with b even
[2,b,b+2] with b>2 and b mod 4 in {0,1}
[3,b,c] with b>3 and b mod 4 in {0,1} and c=b+3-(b mod 4)
[4,b,b+4] with b mod 8 in {0,1,2,3}

I'm sure there's a pattern, but I don't have an easy way to express it.
*)

#6. Conisder a variant of 2-pile Nim where in addition to the Nim moves of removing any number
# of pennies in one of the piles, a player is also allowed to remove the SAME number of pennies
# from both piles. Write a procedure Nim2V(a,b) that inputs non-negative integers a and b and
# outputs 0,{} or 1,S where the members of S are either of the form [i,0],[0,i],[i,i]. For example,
# Nim2V(2,1) should output 0,{}
# Nim2V(3,2) should output 1,{[1,1],[2,0]}
Nim2V:=proc(a,b) local N,W,i,d:
option remember:
if a<0 or b<0 then RETURN(FAIL):
elif a=0 and b=0 then RETURN(0,{}):
elif a=0 or b=0 then RETURN(1,{[a,b]}): fi:
N:=[a,b]:
W:={}:
for i from 1 to min(a,b) do
  for d in {[0,i],[i,0],[i,i]} do
    if Nim2V(op(N-d))[1]=0 then
      W:=W union {d}:
    fi:
  od:
od:
for i from min(a,b)+1 to max(a,b) do
  if a>b and Nim2V(op(N-[i,0]))[1]=0 then
    W:=W union {[i,0]}:
  elif Nim2V(op(N-[0,i]))[1]=0 then
    W:=W union {[0,i]}:
  fi:
od:
if nops(W)=0 then RETURN(0,{}): fi:
1,W:
end:

#7. write a procedure Nim2VL(N) that inputs a positive integer N and outputs the LIST of pairs
# [a,b], 0 <= a <= b <= N, that are losing positions for the above game. with increasing order of
# the first component.
Nim2VL:=proc(N) local a,b,L:
L:=[]:
for a from 0 to N do
  for b from a to N do
    if Nim2V(a,b)[1]=0 then
      L:=[op(L),[a,b]]:
    fi:
  od:
od:
L:
end:

#8. Characterize such losing pairs.

(* Output of #7:
Nim2VL(50);
 [[0, 0], [1, 2], [3, 5], [4, 7], [6, 10], [8, 13], [9, 15], 
  [11, 18], [12, 20], [14, 23], [16, 26], [17, 28], [19, 31], 
  [21, 34], [22, 36], [24, 39], [25, 41], [27, 44], [29, 47], 
  [30, 49]]

Given a list of losing pairs, I can come up with a way to construct the next one:

[a,b] is the next losing pair if a, b are nonnegative, neither a nor b appears in any
previous losing position, and b-a is not equal to the difference of any prior pair.

I suppose that we could also say this as
L[0]=[0,0]
L[i]=[a[i],a[i]+i] such that a[i] is smallest nonnegative not in {seq(a[i],i=0..i-1),seq(a[i]+i,i=0..i-1)}

*)


#### Included from C20.txt ####
#April 4, 2022, C20.txt
Help20:=proc(): print(` P12(n), PR(n,R), LP(N,R) `):end:

#PILE Of pennies , so the STATE of the game is the "number of pennies"
#LEGAL MOVE: REMOVE ONE OR TWO PENNIES
#YOU LOST IF there is no pennies: 
#
#******
#***
#WE WANT A FUNCTION THAT INPUTS n and outputs 1 if is a winning position and 0 if it a losing position
#ALSO THE WINNING MOVE
#
#P12(n): 1-pile Nim with {1,2} removal
P12:=proc(n) local i,S:
option remember:



S:={}:

for i from 1 to min(2,n) do
 if P12(n-i)[1]=0 then
   S:=S union {i}:
 fi:
od:
if S={} then
 0,S:
else
 1,S:
fi:

end:

#PR(n,R): Inputs a pos. integer n and a set of POSITIVE integers R
#outputs 0,{} or 1,S where 0 means losing and S is the set of winning moves
PR:=proc(n,R) local i,S:
option remember:


S:={}:

for i in R do
 if i<=n and PR(n-i,R)[1]=0 then
   S:=S union {i}:
 fi:
od:
if S={} then
 0,S:
else
 1,S:
fi:

end:
#
#LP(N,R): Inputs a pos. integer N and a removal set R outputs the
#list of losing positions <=N
LP:=proc(N,R) local L,i:
L:=[]:
for i from 1 to N do
 if PR(i,R)[1]=0 then
  L:=[op(L),i]:
 fi:
od:
L:
end: