# OK to post

# PART 1: CCshopF() PROCEDURE:
# -----------------------

CCshopF:=proc(N,q,x,K,R,W) local C,c,n:
	C:={};
	for n from 2 to N do:
		C:=C union CCshop(n,q,x,K);
	od;

	for c in C do:
		if c[2] < R or c[3] < W then
			C:= C minus {c};
		fi;
	od;

	return C;
end;

# nops(CCshopF(30,2,x,10000,1/2,5)) = 8
# nops(CCshopF(30,3,x,10000,1/2,5)) = 12
# nops(CCshopF(30,5,x,10000,1/2,5)) = 0

# PART 2: CtoDual() PROCEDURE:
# -----------------------

CtoDual:=proc(n,q,x,g) local A,a,h,H,c,i,k:
	A:=AllFactors(n,q,x); # i cant figure out how to have maple divide polynomials mod q so i'm just going with this stupid solution
	for a in A do:
		if collect(expand(a*g mod q) mod q, x) = x^n-1 mod q then
			h:=a;
			break;
		fi;
	od;

	k:=degree(h,x);
	c:=[seq(coeff(h,x,k-i), i=0..k)];

	for i from 1 to n-k do:
		H[i]:=[0$(i-1), op(c), 0$(n-k-i)];
	od;

	return [seq(H[i], i=1..n-k)];
end;

# PART 3: PROVING VD:
# -----------------------

# BASE CASE:

# [  1    1 ]
# [ a_1 a_2 ] is a vandermonde matrix with det = a_2-a_1 = prod((a_i-a_j), r >= i > j)

# INDUCTION HYPOTHESIS:

# Assume that the determinant of the vandermonde matrix

# [      1           1      ...       1     ]
# [     a_1         a_2     ...      a_r    ]
# [  (a_1)^2      (a_2)^2   ...   (a_r)^2   ]
# [     ...         ...     ...      ...    ]
# [ (a_1)^(r-1) (a_2)^(r-1) ... (a_r)^(r-1) ]

# is prod(a_i-a_j, r >= i > j)

# INDUCTION STEP:

# For the r+1 case, the vandermonde matrix, V, is

# [      1           1      ...       1       ]
# [     a_1         a_2     ...     a_(r+1)   ]
# [  (a_1)^2      (a_2)^2   ...   (a_(r+1))^2 ]
# [     ...         ...     ...      ...      ]
# [  (a_1)^r      (a_2)^r   ...   (a_(r+1))^r ]

# Let V_i be the ith row of the matrix. If we map V_i -> V_i - (a_1)V_(i-1) for i=2..(r+1), we get the matrix

# [  1             1           ...               1               ]
# [  0          a_2-a_1        ...          a_(r+1)-a_1          ]
# [  0      a_2*(a_2-a_1)      ...     a_(r+1)*(a_(r+1)-a_1)     ] (this is so hard to read, i wish i had latex)
# [ ...           ...          ...              ...              ]
# [  0  (a_2)^(r-1)*(a_2-a_1)  ... (a_(r+1))^(r-1)*(a_(r+1)-a_1) ]

# Since this matrix was obtained by taking elementary row operations from V, its determinant is equal to V
# So,

#             [          a_2-a_1        ...          a_(r+1)-a_1          ]
#             [      a_2*(a_2-a_1)      ...     a_(r+1)*(a_(r+1)-a_1)     ]
# det V = det [            ...          ...              ...              ]
#             [  (a_2)^(r-1)*(a_2-a_1)  ... (a_(r+1))^(r-1)*(a_(r+1)-a_1) ]

#                                             [      1      ...         1       ]
#                                             [     a_2     ...      a_(r+1)    ]
# = (a_2-a_1)*(a_3-a_1)*...*(a_(r+1)-a_1)*det [     ...     ...        ...      ]
#                                             [ (a_2)^(r-1) ... (a_(r+1))^(r-1) ]

# The matrix on the right is clearly a vandermonde matrix, so by our assumption, it has determinant prod(a_i-a_j, r+1 >= i > j >= 2).
# We can rewrite the expression to be prod(a_i-a_1, r+1 >= i)*prod(a_i-a_j, r+1 >= i > j >= 2), which is clearly prod(a_i-a_j, r+1 >= i > j).
# Thus, by induction, the determinant of the vandermonde matrix must be prod(a_i-a_j, r >= i > j). QED

# PARTS 4 & 5:
# -----------------------

# I'm skipping the extra challenges because I have a lot of work this weekend :(

############################################################## OLD CODE ##############################################################

CCshop:=proc(n,q,x,K) local C,S,M,g,w:
S:=AllFactors(n,q,x):
C:={}:

for g in S do
  M:=CtoL(n,x,g):
  if q^nops(M)<=K then
   w:=MinW(q,M):
   C:=C union {[g,evalf(nops(M)/n),w]}:
  fi:
od:
C:
end:

CtoL:=proc(n,x,g) local r,L,i:
r:=degree(g,x):
L:=[seq(coeff(g,x,i),i=0..r)]:
[seq([0$i,op(L), 0$(n-r-1-i)],i=0..n-r-1)]:
end:

MinW:=proc(q,M) local n,C,c:
n:=nops(M[1]):
C:=LtoC(q,M):

min( seq(HD(c,[0$n]), c in C minus {[0$n]} )):

end:

with(combinat):
#AllFactors(n,q,x): all the factors of x^n-1 mod q (q is a prime) 
AllFactors:=proc(n,q,x) local S,s:
S:=Factor(x^n-1) mod q:
S:=powerset({op(S)}) minus {{},{op(S)}}:

{seq(expand(convert(s,`*`)) mod q,s in S)} minus {0}:
end:

LtoC:=proc(q,M) local n,k,C,c,i,M1:
option remember:
k:=nops(M):
n:=nops(M[1]):
if k=1 then
 RETURN({seq(i*M[1] mod q,i=0..q-1) }):
fi:
M1:=M[1..k-1]:
C:=LtoC(q,M1):
{seq(seq(c+i*M[k] mod q,i=0..q-1),c in C)}:
end:

HD:=proc(u,v) local i,co:
co:=0:
for i from 1 to nops(u) do
  if u[i]<>v[i] then
      co:=co+1:
  fi:
od:
co:
end: