# Please do not post homework
# Lucy Martinez, 05-01-22, Assignment 26
read `C26.txt`:

#----------------------Problem 3-----------------------#
# Write a procedure SGwyt(a,b) that finds the Sprague-Grundy value of the position [a,b] in Wythoff's game
# whose rules are the same as 2-pile Nim, except that one can also remove the SAME number of pennies from 
# both piles.

SGwyt:= proc(a,b) local L,k,C,c,i,j:
option remember:
L:=[]:
L:=[op(L),a,b]:
 
#C is the set of children of L
C:={seq(seq([ op(1..i-1,L),j,op(i+1..2,L)],j=0..L[i]-1),i=1..2)} union {seq([L[1]-j,L[2]-j],j=1..min(L))}:

mex({seq(SGwyt(C[i][1],C[i][2]),i=1..nops(C))}):
 
end:
SGwyt(3,3);
#             6


#----------------------Problem 4-----------------------#
# Write a procedure FindUP(L) that inputs a list L and outputs a pair of lists L1,L2 such that (conjecturally)
# L=[op(L1),op(L2)^infinity] i.e., after an initial segment L1, it starts being periodic of period nops(L2)

FindUP:=proc(L) local L1,L2,i:
L1:=[]:
L2:=FindPer(L):
for i from 1 while L2=FAIL do
 L2:=FindPer(L[i+1..nops(L)]):
 L1:=[op(L1),L[i]]:
od:
[op(L1),op(L2)]:
end:
FindUP([2,7,1,8,1,8,1,8]);
#              [2, 7, 1, 8]


#----------------------Problem 5-----------------------#
# By using FindUP(L) and SGwyt(a,b), find(if possible) conjectured ultimate periodic descriptions of 
# [seq(SGwyt(i,b)-b,b=0..infinity)] for i=0,1,2,3 (the further the better!)

for i from 1 to 10 do
 FindUP([seq(SGwyt(i,b)-b,b=0..500)]);
od;

#              [Period: 1, 1, -2]

#              [Period: 2, -1, -1]

#    [3, 3, 3, 3, -2, -5, -5, 2, Period: 2, 3, -2, -4, 3, -2]

#  [4, 4, 1, -1, 3, 1, 3, -7, -7, Period: -1, 3, 1, -1, 3, 1, -5, 3, 1, -1, -5, 1]

#  [5, 2, 2, -3, 2, 3, 4, -6, -6, -2, 2, 3, -3, 2, 3, -2, 2, -6, -2, 2, 3, -2, 2, 3, -2, 2, 
#   -6, Period: -2, 2, 3, -2, 2, 3, -2, 2, -6, -2, 2, 3, -2, 2, 3, -2, 2, 3, -7, 2, 3, -2, 
#  2, -7]

# [6, 6, 6, -2, 5, 5, -3, -3, -3, 4, -10, -9, 4, 4, 4, -3, 4, -3, -3, -8, 4, 4, 4, 4, -3, 
#  4, 4, -8, 4, 2, -8, -8, 4, 4, 4, -7, -3, Period: 4, 4, 4, 4, 4, -8, -8, 4, 4, 4, -8, -8]

# [7, 7, 4, 6, -4, -4, -2, -2, -5, 5, 5, 2, 5, -11, -4, 4, 5, -5, 4, -3, 5, -10, -4, 5, 5, 
#  5, 5, -3, 5, -9, -4, -4, 5, -10, 5, 5, 5, -3, 5, -3, -8, 5, -4, 4, 5, -10, -4, 4, -3, 5,
#  5, -3, -8, 5, -4, -3, 5, 5, 5, 5, -3, 5, -9, -3, -8, 2, 4, 4, 5, -10, 5, 5, -3, -8, 5, 
#  -3, -8, 5, -4, 4, 5, -3, 5, 5, -3, 5, -9, -3, -8, 2, -4, 3, 
# Period: 5, 5, 5, 5, -3, -8, 5, -3, -8, 5, 5, 5, 5, -10, -4, 4, -3, 5, -9, -1, -8, 2, 4, -3]


# [8, 5, 5, 7, -3, -3, -1, -4, -4, 6, 6, 6, 6, -13, -5, -1, -4, 2, 5, 5, 6, 6, 6, 
#  -12, -11, -4, -4, 5, -3, 5, 5, -11, -3, 5, -4, 6, 6, -4, 6, 6, -3, -10, -6, -4, 
#  -4, -2, 5, 5, 5, 6, -4, -1, -3, -5, 5, 3, -9, 6, -4, -3, 5, 6, -5, -1, -3, -5, 
#  5, 5, -4, 5, -4, -3, 5, 5, -5, 5, -3, 6, 6, -4, -4, -11, -3, 3, 5, 6, -5, 5,
#  -3, 5, 5, -4, -4, -11, -4, 6, 6, 6, -5, -1, -3, -5, Period: 6, -4, -4, 5, 5, -3,
#   4, 6, -5, 5, -3, 5, 5, 5, -9, -11, -4, 6, 6, 6, -5, -10, -3, -3]


# [9, 9, 9, 9, 4, 2, 7, 7, 7, 7, 7, -5, 7, -8, -13, -15, -14, -14, -14, 3, 7, 7, 7, -5,
#   -4, 6, -3, 6, -7, -3, -6, 3, 6, 6, 6, -3, -11, -7, -3, 7, 7, 2, -5, 5, -3, 5, 6, -11,
#   -4, -7, 3, -6, 5, 2, -5, 5, -5, 7, 7, 2, -6, -3, -3, 5, 5, -3, 6, -11, -5, 6, -3, 
#   2, -6, -3, -3, 6, 6, -3, 7, -3, -3, 5, 6, -3, -6, 7, -3, 6, 6, 6, -11, -7, -3, -6, 
#  -3, 2, -6, 7, 3, 6, 6, -3, 7, -7, 6, -6, -3, -5, 5, 7, -10, -4, 5, -5, 6, 3, -5, 6,
#  -3, 2, -6, 7, -10, -4, 5, 2, 4, Period: -3, -6, -4, 6, -5, 5, 7, -3, 6, 6, -5, -5, 
#  6, -6, -6, -3, 4, -6, 7, -3, 6, 6, 2, -6]


# [10, 10, 7, 5, 9, 7, -6, 8, 8, 8, 4, 7, -5, -7, -12, -12, -15, -13, -13, 4, 8, 5, 5, 
#  -3, -5, -3, 3, 4, 6, 4, 6, -6, -8, -12, 7, 4, 4, -5, 7, -1, -5, 7, -12, 3, 6, 6, 7,
#  -3, -6, -12, -3, 5, 6, 6, 6, 6, -13, 8, 8, 3, -5, -12, -8, -11, 6, -8, 7, 7, 7, -2, 
#  -7, 6, -4, 6, 6, -11, -5, -8, 4, -7, 6, 6, 7, 7, 4, 8, -8, -11, -5, -8, 4, -6, 6,
#  -2, 6, -3, -12, 5, -3, 5, 7, 7, 4, -6, -3, 6, 6, 6, -12, -6, 5, 6, -13, -8, 7, -6,
#   6, 7, 7, -3, 7, -3, -8, -13, 6, 6, 7, -7, 6, 6, -11, 6, -4, 8, -8, 7, -13, -8, 6,
#  -7, -4, -2, 6, -3, 5, 5, -8, -1, -5, 6, 4, -6, 6, 6, -7, 6, -5, 8, 5, 7, 7, -8, 6,
#  -7, -12, 6, 6, -3, 5, -12, -8, -11, 7, 7, -4, -6, 6, 6, 7, 7, -5, -3, -8, 7, 7, -8,
#  6, 7, -12, -2, 6, -3, 5, -12, 7, -11, 7, -8, 4, -6, 6, 6, -7, 6, -5, 8, -8, 7, 7, 7, 7,
#  -7, -12, -2, 6, -3, 5, -12, -8, -11, 7, 7, -4, 3, Period: 6, 6, -7, 6, -5, 8, -8, 7,
#   7, -8, 6, 7, -12, -2, 6, -3, 5, -12, -8, -11, 7, 7, 4, -6]