# OK to post homework
# Lucy Martinez, 04-10-22, Assignment 20
read `C20.txt`:
with(combinat):
#----------------------Problem 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 e 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 example, 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,min,i, temp, j:
L:=LP(10000,R);
 
for i from 1 to 2000 do
temp:=convert(L mod i,set);
 if nops(temp)<i then
  RETURN(i,temp):
 fi:
od:
end:

ConjLP({1,2});
#                  3, {0}


#----------------------Problem 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) from ONE pile. 
# For example 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 if length k:=nops(N) and outputs 0,{} if it is a losing position, and 1,S, 
# if it is a winning position 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]}

Nim:=proc(N) local k,S,i,T,j,a:
option remember:
k:=nops(N):
S:={}:

if N=[0$k] then
 RETURN(0,S):
fi: 

# choose a pile, and then choose how much to remove and see if it works
 
for i from 1 to k do
for j from 1 to N[i] do 
 if j<=N[i] and Nim( [seq(N[a],a=1..i-1) ,N[i]-j, seq(N[a],a=i+1..k)] )[1]=0 then
  S:=S union {[i,j]}:
 fi:
od:
od:
 
if S={} then
 0,S:
else
 1,S:
fi:

end:

Nim([3,3]);
#               0, {}


Nim([7,3]);
#               1, {[1, 4]}


Nim([2,3]);
#               1, {[2, 1]}


#----------------------Problem 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]}

NimL:= proc(k,N) local S,i, j ,All, L ,a:
S:={}:

L:=[seq(seq(j$i,i=1..k),j=0..N)]:
All:=permute(L,k):

for a in All do
 if Nim(a)[1]<>1 then
  S:=S union {a}:
 fi:
od:
S:
end:


NimL(2,3);
#            {[0, 0], [1, 1], [2, 2], [3, 3]}


#----------------------Problem 6-----------------------#

# Consider 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]}

Nim2V:= proc(a,b) local S,i,j,N,T:
option remember:
S:={}:
N:=[]:
N:=[op(N),a,b]:
 
if a=0 and b=0 then
 RETURN(0,S):
fi:

for i from 1 to 2 do 
for j from 1 to N[i] do
 if j<=a and Nim2V(a-j,b)[1]=0 then
  S:=S union {[j,0]}:
 elif j<=b and Nim2V(a,b-j)[1]=0 then
  S:=S union {[0,j]}:
 elif j<=a and j<=b and Nim2V(a-j,b-j)[1]=0 then
  S:=S union {[j,j]}:
 fi:
od:
od:

if S={} then
 0,S:
else
 1,S:
fi:

end:
Nim2V(3,2);
#               1, {[1, 1], [2, 0]}

Nim2V(4,3);
#               1, {[2, 2]}

Nim2V(2,1);
#               0, {}


#----------------------Problem 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 S, L,All,a,i,j:
option remember:
S:={}:
L:=[seq(seq(j$i,i=1..2),j=0..N)]:
All:=permute(L,2):

for a in All do
 if a[1]<=a[2] and Nim2V(a[1],a[2])[1]<>1 then
  S:=S union {a}:
 fi:
od:
S:
end: