#OK to post homework
#Lucy Martinez, 02-06-2024, Assignment 6

with(numtheory):
with(NumberTheory):


# Problem 3, Part 1: Write a program SearchLC(q,n,k,K)
# that inputs q and n for GF(q)^n, 
# and k (for the dimension of the linear code, a certain subspace of GF(q)^n)
# and a very large positive integer K (say 1000)
# and keeps generating, K times, random lists, M, of k members of GF(q)^n,
# for each determines MinW(q,M) and outputs the one with
# the largest minimum weight.
# For Part 2 (the data), look after Problem 4
SearchLC:=proc(q,n,k,K) local L,i,j,M:
L:=[[seq(RV(q,n),j=1..k)]]:

for i from 1 to K do
 M:=[seq(RV(q,n),j=1..k)]:
 L:=[op(L),M]:
 if MinW(q,L[2])>=MinW(q,L[1]) then
  L:=subsop(1=NULL,L):
 else
  L:=subsop(2=NULL,L):
 fi:
od:
op(L):
end:





### DATA:
# Problem 3, Part 2: Run it, with K=1000 for q=2,3,5;
# 4<=n<=10 and 3<=k<=5


# q=2, k=3 and 4<=n<=10:
# for n from 4 to 10 do
#  SearchLC(2,n,3,1000);
# od;
# outputs
# [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
# [[1, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 0]]
# [[0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1], [1, 1, 0, 1, 1, 0]]
# [[0, 1, 0, 1, 0, 1, 1], [0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 1, 0, 1, 0]]
# [[0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1]]
# [[1, 1, 1, 1, 1, 1, 0, 0, 0],[1, 0, 1, 0, 0, 1, 1, 1, 1],[0, 1, 0, 1, 1, 0, 1, 1, 1]]
# [[0, 1, 1, 0, 0, 0, 1, 1, 1, 0],[0, 1, 1, 0, 1, 1, 0, 1, 0, 1],[1, 0, 1, 1, 0, 0, 1, 1, 0, 1]]


# q=2, k=4 and 4<=n<=10:
# for n from 4 to 10 do
#  SearchLC(2,n,4,1000);
# od;
# outputs
# [[1, 1, 0, 1],[1, 1, 0, 1],[1, 0, 1, 1],[0, 0, 0, 0]]
# [[0, 0, 0, 0, 0],[0, 1, 0, 1, 1],[0, 0, 0, 0, 0],[1, 0, 1, 0, 1]]
# [[0, 1, 1, 1, 0, 1], [0, 0, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1],[1, 0, 1, 1, 0, 0]]
# [[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 1],[0, 0, 1, 1, 0, 1, 0], [0, 1, 1, 0, 0, 0, 1]]
# [[0, 0, 1, 1, 0, 1, 1, 0],[0, 1, 0, 0, 1, 1, 0, 1],[1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1]]
# [[0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 1, 0, 0, 0, 0, 1],[1, 0, 0, 0, 1, 0, 1, 0, 1],[1, 1, 0, 0, 0, 1, 1, 0, 0]]
# [[1, 1, 0, 1, 1, 1, 0, 1, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[1, 1, 1, 1, 1, 0, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 0, 1, 0, 1]]


# q=2, k=5 and 4<=n<=10:
# for n from 4 to 10 do
#  SearchLC(2,n,5,1000);
# od;
# outputs
# [[0, 1, 1, 0], [0, 0, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0],[1, 0, 1, 0]]
# [[1, 1, 1, 0, 1], [0, 1, 0, 1, 1], [1, 0, 1, 1, 0],[1, 0, 1, 1, 0], [1, 0, 1, 1, 0]]
# [[0, 1, 0, 0, 0, 1], [0, 0, 0, 1, 0, 1], [0, 0, 1, 1, 0, 0],[1, 0, 1, 0, 1, 1], [0, 1, 1, 0, 1, 1]]
# [[1, 0, 1, 1, 0, 0, 1], [0, 1, 0, 0, 1, 1, 0],[1, 0, 1, 0, 0, 1, 0], [0, 0, 1, 1, 1, 0, 0],[0, 1, 0, 0, 1, 1, 0]]
# [[1, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 1, 1, 0, 1, 1],[0, 1, 0, 0, 1, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0, 0], [0, 1, 0, 1, 0, 0, 1, 0]]
# [[0, 1, 1, 1, 1, 1, 1, 0, 0],[0, 1, 0, 0, 1, 0, 1, 0, 1],[1, 1, 1, 0, 0, 0, 1, 0, 1],[1, 1, 0, 0, 1, 1, 0, 1, 0],[1, 0, 0, 0, 1, 1, 1, 0, 0]]
# [[1, 0, 1, 1, 1, 1, 1, 1, 1, 0],[1, 1, 1, 1, 0, 1, 1, 1, 0, 1],[0, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 0],[1, 1, 1, 0, 0, 0, 1, 0, 0, 0]]


# q=3, k=3 and 4<=n<=10:
# for n from 4 to 10 do
#  SearchLC(3,n,3,1000);
# od;
# outputs
# [[2, 2, 1, 1], [2, 2, 1, 1], [0, 0, 0, 0]]
# [[1, 1, 0, 2, 2], [0, 0, 0, 0, 0], [1, 1, 0, 2, 2]]
# [[1, 0, 2, 1, 2, 0], [0, 0, 0, 0, 0, 0], [0, 2, 2, 2, 1, 1]]
# [[1, 1, 2, 0, 1, 2, 1],[2, 1, 2, 2, 1, 0, 2],[2, 1, 1, 1, 0, 1, 1]]
# [[0, 0, 0, 0, 0, 0, 0, 0],[0, 1, 2, 0, 1, 1, 2, 0],[2, 1, 2, 2, 0, 1, 1, 1]]
# [[1, 0, 1, 2, 2, 1, 0, 2, 1], [2, 2, 0, 0, 1, 0, 2, 1, 2],[0, 1, 1, 1, 1, 0, 2, 2, 0]]
# [[1, 2, 1, 1, 0, 0, 2, 0, 2, 1], [1, 1, 1, 1, 2, 1, 1, 1, 2, 2],[2, 1, 2, 1, 1, 1, 0, 0, 2, 1]]


# q=3, k=4 and 4<=n<=10:
# for n from 4 to 10 do
#  SearchLC(3,n,4,1000);
# od;
# outputs
# [[0, 0, 0, 0], [1, 2, 2, 2], [2, 2, 0, 0], [2, 0, 2, 2]]
# [[1, 2, 1, 2, 0], [0, 2, 2, 0, 1], [2, 1, 1, 1, 2],[1, 1, 0, 1, 2]]
# [[2, 0, 0, 2, 1, 2], [0, 0, 0, 0, 0, 0], [1, 2, 0, 0, 1, 1], [1, 1, 2, 0, 1, 2]]
# [[2, 0, 0, 1, 1, 1, 2],[2, 2, 1, 0, 2, 2, 0],[0, 1, 1, 2, 2, 0, 0],[1, 1, 1, 1, 1, 2, 1]]
# [[2, 1, 0, 1, 0, 1, 1, 1], [1, 0, 1, 0, 1, 0, 0, 2],[2, 0, 2, 1, 1, 2, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
# [[2, 2, 0, 2, 0, 2, 0, 2, 1], [2, 0, 0, 2, 0, 1, 1, 0, 2],[1, 0, 0, 1, 2, 0, 0, 0, 2], [1, 0, 2, 1, 1, 0, 1, 2, 2]]
# [[1, 2, 0, 0, 1, 0, 1, 1, 2, 1], [2, 0, 1, 2, 0, 2, 0, 0, 0, 2],[2, 0, 2, 0, 1, 0, 0, 2, 1, 0], [1, 1, 0, 2, 2, 1, 0, 2, 2, 0]]


# q=3, k=5 and 4<=n<=10:
# for n from 4 to 10 do
#  SearchLC(3,n,5,1000);
# od;
# outputs
# [[2, 0, 0, 2],[2, 0, 0, 2], [2, 2, 1, 2],[0, 1, 1, 2],[0, 0, 2, 2]]
# [[1, 0, 1, 2, 2],[1, 0, 0, 0, 1], [2, 2, 1, 1, 2],[1, 2, 0, 2, 0], [2, 1, 0, 1, 0]]
# [[0, 1, 0, 1, 2, 2], [2, 1, 0, 0, 2, 1], [1, 0, 0, 1, 0, 1],[1, 0, 2, 2, 2, 2], [0, 0, 0, 0, 0, 0]]
# [[2, 1, 0, 2, 1, 0, 2], [0, 0, 2, 1, 2, 2, 1],[2, 2, 2, 1, 0, 0, 0], [2, 1, 1, 1, 2, 1, 1],[1, 1, 0, 2, 0, 1, 2]]
# [[0, 2, 0, 1, 1, 1, 0, 2], [1, 0, 1, 2, 0, 2, 2, 0],[1, 2, 1, 0, 0, 1, 0, 2], [0, 1, 1, 0, 1, 0, 0, 1],[1, 1, 2, 1, 1, 1, 1, 0]]
# [[0, 1, 1, 0, 0, 2, 1, 1, 0],[1, 2, 2, 1, 0, 0, 0, 2, 0],[0, 0, 1, 2, 0, 2, 1, 0, 1], [1, 0, 2, 1, 1, 1, 2, 2, 0],[0, 1, 2, 1, 1, 1, 0, 1, 0]]
# [[1, 0, 2, 1, 0, 1, 1, 1, 1, 1],[2, 2, 2, 0, 0, 2, 1, 1, 1, 1],[1, 1, 2, 1, 2, 1, 2, 1, 0, 0], [0, 2, 2, 2, 2, 2, 2, 2, 1, 1],[2, 1, 2, 1, 0, 2, 1, 0, 2, 1]]


# q=5, k=3, and 4<=n<=10;
# for n from 4 to 10 do
#  SearchLC(5,n,3,1000);
# od;
# outputs
# [[3, 0, 3, 4], [3, 0, 3, 4], [4, 1, 2, 0]]
# [[4, 1, 2, 1, 0], [0, 0, 0, 0, 0], [1, 1, 1, 0, 4]]
# [[0, 1, 3, 0, 2, 1], [4, 3, 4, 2, 4, 2], [1, 4, 0, 1, 3, 3]]
# [[3, 0, 1, 4, 2, 0, 0], [1, 2, 1, 3, 0, 1, 0],[3, 2, 1, 0, 2, 4, 2]]
# [[1, 0, 2, 2, 4, 2, 0, 4], [1, 0, 1, 4, 0, 0, 4, 4],[3, 4, 0, 1, 1, 4, 0, 1]]
# [[0, 2, 0, 2, 1, 1, 1, 1, 1], [1, 1, 3, 4, 4, 4, 4, 0, 0],[4, 3, 4, 1, 4, 1, 2, 4, 1]]
# [[4, 1, 0, 4, 0, 1, 2, 0, 3, 4], [0, 2, 0, 3, 1, 0, 1, 4, 2, 2], [4, 4, 2, 2, 2, 0, 3, 1, 2, 0]]


# q=5, k=4 and 4<=n<=10;
# for n from 4 to 10 do
#  SearchLC(5,n,4,1000);
# od;
# outputs
# [[1, 4, 0, 4], [1, 0, 2, 4], [4, 1, 1, 0], [3, 0, 4, 4]]
# [[4, 0, 3, 0, 3], [4, 0, 4, 4, 0], [0, 1, 2, 0, 3],[2, 0, 1, 3, 3]]
# [[2, 3, 2, 1, 3, 1], [1, 4, 1, 0, 0, 4], [0, 3, 1, 2, 0, 0],[2, 1, 1, 3, 4, 4]]
# [[4, 2, 4, 2, 3, 1, 1],[0, 4, 2, 3, 4, 1, 1],[4, 0, 4, 2, 0, 4, 0], [1, 0, 3, 0, 1, 4, 4]]
# [[3, 2, 0, 2, 4, 2, 0, 1], [2, 1, 1, 4, 3, 2, 4, 4],[1, 3, 4, 4, 2, 1, 3, 2], [4, 1, 4, 3, 2, 4, 3, 4]]
# [[4, 0, 1, 1, 3, 3, 1, 4, 1], [4, 1, 1, 2, 2, 2, 0, 2, 1], [3, 1, 3, 3, 3, 4, 2, 1, 4], [3, 4, 0, 0, 2, 2, 4, 3, 4]]
# [[3, 2, 4, 1, 2, 4, 2, 1, 2, 4], [4, 2, 3, 4, 0, 4, 4, 1, 1, 4], [2, 3, 0, 0, 0, 1, 2, 1, 3, 4], [1, 0, 0, 1, 2, 4, 3, 0, 0, 2]]


# q=5, k=5 and 4<=n<=10;
# for n from 4 to 10 do
#  SearchLC(5,n,5,1000);
# od;
# outputs
# [[2, 3, 0, 1], [3, 1, 1, 3], [4, 3, 4, 2], [2, 1, 1, 1],[0, 4, 4, 3]]
# [[3, 4, 3, 2, 0], [2, 0, 1, 1, 1], [0, 2, 1, 2, 3],[4, 0, 0, 1, 1], [4, 1, 2, 0, 0]]
# [[1, 2, 4, 4, 3, 4], [1, 2, 1, 4, 1, 3], [1, 0, 2, 3, 2, 2],[4, 2, 0, 0, 1, 3], [0, 2, 2, 4, 4, 4]]
# [[0, 3, 2, 0, 4, 4, 3],[4, 3, 4, 3, 1, 1, 4],[0, 2, 1, 0, 1, 0, 3], [4, 0, 4, 4, 3, 2, 4],[0, 2, 2, 1, 2, 2, 4]]
# [[2, 0, 1, 4, 0, 1, 0, 3],[3, 3, 4, 4, 4, 4, 1, 4],[2, 1, 4, 2, 3, 1, 0, 2],[1, 3, 1, 1, 1, 3, 1, 0],[3, 4, 1, 1, 2, 2, 2, 1]]
# [[3, 1, 2, 3, 2, 0, 3, 0, 2],[3, 2, 3, 3, 2, 3, 0, 1, 2],[2, 4, 4, 4, 0, 0, 1, 2, 4],[2, 1, 4, 4, 2, 4, 3, 2, 3],[0, 0, 0, 4, 2, 4, 2, 1, 0]]
# [[3, 2, 3, 2, 1, 1, 3, 4, 2, 4],[4, 4, 4, 3, 0, 1, 0, 4, 0, 0],[4, 2, 1, 3, 3, 2, 2, 0, 0, 2], [2, 3, 2, 0, 2, 3, 2, 2, 3, 1],[0, 0, 0, 3, 2, 3, 3, 0, 2, 3]]





####################################### From Class Procedures:
#(linear to code)
# LtoC(q,M): inputs a list of basis vectors for our linear code over GF(q)
# outputs all codewords (the actual subset of GF(q)^n with q^k elements)
LtoC:=proc(q,M) local n,k,C,i,M1,c:
option remember:
n:=nops(M[1]):
k:=nops(M):
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(x,y) = HD(x-y mod q, [0$n])


# MinW(q,M): The minimal weight of the Linear code generated by M over GF(q)
MinW:=proc(q,M) local C,n,c:
n:=nops(M[1]):
C:=LtoC(q,M):
min(seq( HD(c,[0$n]),c in (C minus {[0$n]}) )):
end:


#Nei(q,c): all the neighbors of the vector c in Fqn(q,n)
# here, we are changing the i-th term in the list to a=0..q-1
Nei:=proc(q,c) local n,i,a:
n:=nops(c):
{seq(seq([op(1..i-1,c),a,op(i+1..n,c)]  ,a=0..q-1),i=1..n)}:

end:


# SP(q,c,t): the set of all vectors in Fqn(q,n) whose distance is <=t from c
SP:=proc(q,c,t) local S,s,i:
S:={c}:
for i from 1 to t do
 S:=S union {seq(op(Nei(q,s)), s in S)}:
od:
S:
end:


# GRC(q,n,d): outputs q-ary codes with minimum distance d, length n
GRC:=proc(q,n,d) local A,S,v:
A:=Fqn(q,n):
S:={}:
while A<>{} do
 v:=A[1]: #first element in A, not random
 S:=S union {v}:
 A:=A minus SP(q,v,d-1):
od:
S:
end:


# MinD(C): The minimal (Hamming) distance of the code C
MinD:=proc(C) local i,j:
min(seq(seq(HD(C[i],C[j]),j=i+1..nops(C)),i=1..nops(C))):
end:


#CV(S,n): the characteristic vector of the subset S of {1,...,n}
# For example CV({1,2},4); should output [1,1,0,0]
CV:=proc(S,n) local v,i:
v:=[]:
for i from 1 to n do
 if member(i,S) then
  v:=[op(v),1]:
 else
  v:=[op(v),0]:
 fi:
od:
v:
end:



BDtoC:=proc(BD,n) local s,C:
C:={seq(CV(s,n),s in BD)}:
C:=C union subs({0=1,1=0},C):
C union {[0$n],[1$n]}:
C:
end:


#Alphabet {0,1,...q-1}, Fqn(q,n): {0,1,...,q-1}^n
Fqn:=proc(q,n) local S,a,v:
option remember:
if n=0 then
 RETURN({[]}):
fi:

S:=Fqn(q,n-1):

{seq(seq([op(v),a],a=0..q-1), v in S)}:

end:


#HD(u,v): The Hamming distance between two words (of the same length)
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:

#SPB(q,n,d): The best you can hope for (as far as the size of C) for q-ary (n,2*t+1) code
SPB:=proc(q,n,t) local i:
trunc(q^n/add(binomial(n,i)*(q-1)^i,i=0..t)):
end:


#RV(q,n): A random word of length n in {0,1,..,q-1}
RV:=proc(q,n) local ra,i:
ra:=rand(0..q-1):
[seq( ra(), i=1..n)]:
end:

#RC(q,n,d,K): inputs q,n,d, and K and keeps picking K+1 (thanks to Nuray) random vectors
#whenever the new vector is not distance <=d-1 from all the previous one 
RC:=proc(q,n,d,K) local C,v,i,c:
C:={RV(q,n)}:
for i from 1 to K do
 v:=RV(q,n):
  if min(seq(HD(v,c), c in C))>=d then
   C:=C union {v}:
  fi:
od:
C:
end: