# HW 6 Spring 2024 - Pablo Blanco
# OK to post


# Exercise 5.1
# This is not a linear code because M is not of the form q^k; in particular, 24 is not a power of 2

# Exercise 5.2
# [n, n-1, 2]
# d >= 2 because two vectors cannot be different on exactly one coordinate (this would mean odd weight)
# d <= 2 because you can construct a pair of vectors with distance 2. Let v be a vector, pick two coordinates and
# add 1 to both coordinates in mod 2. The new vector is also even but differs by two coordinates.

# Let e_i = 1s on exactly the ith and (i+1)st coordinates for i\in[n-1]. 
# Then, we have a generator matrix with each row i equal to e_i. 
# We can change this to standard for by the following: For each row j, add the vectors e_k for k > j.
# Let c be the vector with 1 on the last coordinate and f_i be the vector with 1 only in i-th coordinate.
# the resulting standard for generating matrix has rows f_i+c.
# e.g.
# 1 0 0 1
# 0 1 0 1
# 0 0 1 1
# an identity matrix with an additional 1s column added to the right.

# Exercise 5.3
# only became clear to me after seeing the solution

# Exercise 5.4
# (a) taking the even vectors from a code keeps it closed under addition so it is a vector space (also closed under
# scalar multiplication) and so it is linear
#
# (b) Consider example 5.3(ii) with an extra coordinate to ensure all vectors are even-weight. Then, we clearly
# have n=8, M=2^4. We verify that d = 4. We see that any two even codewords must have even distance between each
# other. Since that distance was >= 3 originally (and the new distance is at least this), it follows that d=4 
# after this change.


# Exercise 5.5
# Assume that there are both even and odd code-words. Fix an odd codeword x.
# Let S be the odd codewords and E be the even ones. Note that the sum of two odd codewords is an even
# codeword. Consider the map \varphi: S \to E given by v\mapsto v+x. This function is bijective because
# it is its own inverse. As a result |S|=|E| and we are done.

# SearchLC results: formatted as (n,q,k)
#                            4, 2, 3
#           [[1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1]]
#                            4, 2, 4
#    [[1, 1, 0, 0], [0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 0, 1]]
#                            5, 2, 3
#      [[1, 1, 1, 0, 1], [0, 0, 1, 0, 1], [0, 1, 0, 0, 1]]
#                            5, 2, 4
#      [[0, 1, 1, 0, 0], [1, 0, 1, 0, 0], [1, 1, 0, 0, 0], 
#        [1, 1, 1, 1, 0]]
#                            5, 2, 5
#      [[1, 1, 0, 1, 1], [0, 0, 0, 1, 1], [0, 1, 1, 1, 1], 
#        [0, 1, 0, 0, 1], [0, 1, 0, 1, 0]]
#                            6, 2, 3
#  [[1, 1, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1], [0, 1, 1, 1, 0, 1]]
#                            6, 2, 4
# [[1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0], 
#   [0, 1, 0, 1, 0, 0]]
#                            6, 2, 5
# [[1, 1, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1], [0, 1, 1, 1, 0, 1], 
#   [0, 1, 0, 0, 0, 1], [0, 1, 0, 1, 1, 1]]
#                            7, 2, 3
#        [[0, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1], 
#          [1, 1, 0, 1, 1, 1, 1]]
#                            7, 2, 4
#        [[0, 1, 0, 1, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0], 
#          [1, 1, 1, 1, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0]]
#                            7, 2, 5
#        [[0, 0, 0, 0, 1, 1, 1], [1, 1, 0, 0, 1, 1, 1], 
#          [1, 0, 1, 0, 1, 1, 1], [1, 0, 0, 1, 1, 1, 1], 
#          [1, 0, 0, 0, 0, 1, 1]]
#                            8, 2, 3
#     [[1, 1, 1, 0, 1, 1, 1, 1], [0, 0, 1, 0, 1, 1, 1, 1], 
#       [0, 1, 0, 0, 1, 1, 1, 1]]
#                            8, 2, 4
#     [[0, 1, 1, 1, 0, 0, 1, 0], [1, 0, 1, 1, 0, 0, 1, 0], 
#       [1, 1, 0, 1, 0, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1, 0]]
#                            8, 2, 5
#     [[1, 1, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 0, 1, 1, 1], 
#       [0, 1, 1, 1, 0, 1, 1, 1], [0, 1, 0, 0, 0, 1, 1, 1], 
#       [0, 1, 0, 1, 1, 1, 1, 1]]
#                            9, 2, 3
#  [[1, 1, 1, 1, 0, 1, 0, 1, 1], [0, 0, 1, 1, 0, 1, 0, 1, 1], 
#    [0, 1, 0, 1, 0, 1, 0, 1, 1]]
#                            9, 2, 4
#  [[1, 0, 1, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 1, 0], 
#    [0, 0, 0, 1, 1, 1, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1, 1, 0]]
#                            9, 2, 5
#  [[0, 0, 1, 0, 0, 0, 0, 1, 0], [1, 1, 1, 0, 0, 0, 0, 1, 0], 
#    [1, 0, 0, 0, 0, 0, 0, 1, 0], [1, 0, 1, 1, 0, 0, 0, 1, 0], 
#    [1, 0, 1, 0, 1, 0, 0, 1, 0]]
#                            10, 2, 3
#[[1, 1, 0, 1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 1, 0], 
#  [0, 1, 1, 1, 0, 0, 0, 0, 1, 0]]
#                            10, 2, 4
#[[0, 1, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1], 
#  [1, 1, 0, 0, 0, 0, 1, 0, 0, 1], [1, 1, 1, 1, 0, 0, 1, 0, 0, 1]]
#                            10, 2, 5
#[[0, 0, 0, 0, 1, 1, 0, 0, 0, 1], [1, 1, 0, 0, 1, 1, 0, 0, 0, 1], 
#  [1, 0, 1, 0, 1, 1, 0, 0, 0, 1], [1, 0, 0, 1, 1, 1, 0, 0, 0, 1], 
#  [1, 0, 0, 0, 0, 1, 0, 0, 0, 1]]
#                            4, 3, 3
#           [[2, 1, 1, 2], [1, 2, 1, 2], [1, 1, 2, 2]]
#                            4, 3, 4
#    [[2, 1, 0, 0], [1, 2, 0, 0], [1, 1, 1, 0], [1, 1, 0, 1]]
#                            5, 3, 3
#      [[2, 2, 2, 0, 0], [1, 0, 2, 0, 0], [1, 2, 0, 0, 0]]
#                            5, 3, 4
#      [[1, 1, 1, 1, 1], [0, 2, 1, 1, 1], [0, 1, 2, 1, 1], 
#        [0, 1, 1, 2, 1]]
#                            5, 3, 5
#      [[0, 0, 1, 2, 0], [2, 1, 1, 2, 0], [2, 0, 2, 2, 0], 
#        [2, 0, 1, 0, 0], [2, 0, 1, 2, 1]]
#                            6, 3, 3
#  [[0, 2, 0, 0, 0, 1], [2, 0, 0, 0, 0, 1], [2, 2, 1, 0, 0, 1]]
#                            6, 3, 4
# [[2, 0, 1, 1, 2, 1], [1, 1, 1, 1, 2, 1], [1, 0, 2, 1, 2, 1], 
#   [1, 0, 1, 2, 2, 1]]
#                            6, 3, 5
# [[1, 1, 1, 0, 1, 1], [0, 2, 1, 0, 1, 1], [0, 1, 2, 0, 1, 1], 
#   [0, 1, 1, 1, 1, 1], [0, 1, 1, 0, 2, 1]]
#                            7, 3, 3
#        [[1, 1, 2, 0, 0, 0, 1], [0, 2, 2, 0, 0, 0, 1], 
#          [0, 1, 0, 0, 0, 0, 1]]
#                            7, 3, 4
#        [[2, 1, 1, 2, 0, 1, 1], [1, 2, 1, 2, 0, 1, 1], 
#          [1, 1, 2, 2, 0, 1, 1], [1, 1, 1, 0, 0, 1, 1]]
#                            7, 3, 5
#        [[1, 0, 0, 1, 2, 2, 0], [0, 1, 0, 1, 2, 2, 0], 
#          [0, 0, 1, 1, 2, 2, 0], [0, 0, 0, 2, 2, 2, 0], 
#          [0, 0, 0, 1, 0, 2, 0]]
#                            8, 3, 3
#     [[2, 1, 1, 2, 1, 2, 1, 1], [1, 2, 1, 2, 1, 2, 1, 1], 
#       [1, 1, 2, 2, 1, 2, 1, 1]]
#                            8, 3, 4
#     [[0, 1, 2, 0, 2, 1, 0, 0], [2, 2, 2, 0, 2, 1, 0, 0], 
#       [2, 1, 0, 0, 2, 1, 0, 0], [2, 1, 2, 1, 2, 1, 0, 0]]
#                            8, 3, 5
#     [[0, 1, 0, 1, 1, 2, 0, 2], [2, 2, 0, 1, 1, 2, 0, 2], 
#       [2, 1, 1, 1, 1, 2, 0, 2], [2, 1, 0, 2, 1, 2, 0, 2], 
#       [2, 1, 0, 1, 2, 2, 0, 2]]
#                            9, 3, 3
#  [[1, 1, 2, 1, 1, 1, 0, 1, 2], [0, 2, 2, 1, 1, 1, 0, 1, 2], 
#    [0, 1, 0, 1, 1, 1, 0, 1, 2]]
#                            9, 3, 4
#  [[1, 2, 1, 0, 2, 2, 0, 2, 1], [0, 0, 1, 0, 2, 2, 0, 2, 1], 
#    [0, 2, 2, 0, 2, 2, 0, 2, 1], [0, 2, 1, 1, 2, 2, 0, 2, 1]]
#                            9, 3, 5
#  [[2, 2, 1, 0, 0, 2, 0, 2, 0], [1, 0, 1, 0, 0, 2, 0, 2, 0], 
#    [1, 2, 2, 0, 0, 2, 0, 2, 0], [1, 2, 1, 1, 0, 2, 0, 2, 0], 
#    [1, 2, 1, 0, 1, 2, 0, 2, 0]]
#                            10, 3, 3
#[[1, 1, 1, 1, 1, 0, 2, 1, 2, 0], [0, 2, 1, 1, 1, 0, 2, 1, 2, 0], 
#  [0, 1, 2, 1, 1, 0, 2, 1, 2, 0]]
#                            10, 3, 4
#[[1, 0, 1, 2, 1, 1, 2, 1, 1, 0], [0, 1, 1, 2, 1, 1, 2, 1, 1, 0], 
#  [0, 0, 2, 2, 1, 1, 2, 1, 1, 0], [0, 0, 1, 0, 1, 1, 2, 1, 1, 0]]
#                            10, 3, 5
#[[2, 1, 2, 0, 1, 1, 1, 0, 0, 1], [1, 2, 2, 0, 1, 1, 1, 0, 0, 1], 
#  [1, 1, 0, 0, 1, 1, 1, 0, 0, 1], [1, 1, 2, 1, 1, 1, 1, 0, 0, 1], 
#  [1, 1, 2, 0, 2, 1, 1, 0, 0, 1]]
#                            4, 5, 3
#           [[4, 3, 2, 4], [3, 4, 2, 4], [3, 3, 3, 4]]
#                            4, 5, 4
#    [[2, 4, 3, 1], [1, 0, 3, 1], [1, 4, 4, 1], [1, 4, 3, 2]]
#                            5, 5, 3
#      [[1, 3, 4, 4, 0], [0, 4, 4, 4, 0], [0, 3, 0, 4, 0]]
#                            5, 5, 4
#      [[0, 1, 4, 1, 2], [4, 2, 4, 1, 2], [4, 1, 0, 1, 2], 
#        [4, 1, 4, 2, 2]]
#                            5, 5, 5
#      [[2, 0, 1, 0, 2], [1, 1, 1, 0, 2], [1, 0, 2, 0, 2], 
#        [1, 0, 1, 1, 2], [1, 0, 1, 0, 3]]
#                            6, 5, 3
#  [[0, 0, 0, 4, 0, 4], [4, 1, 0, 4, 0, 4], [4, 0, 1, 4, 0, 4]]
#                            6, 5, 4
# [[2, 2, 0, 4, 1, 1], [1, 3, 0, 4, 1, 1], [1, 2, 1, 4, 1, 1], 
#   [1, 2, 0, 0, 1, 1]]
#                            6, 5, 5
# [[0, 0, 4, 2, 0, 2], [4, 1, 4, 2, 0, 2], [4, 0, 0, 2, 0, 2], 
#   [4, 0, 4, 3, 0, 2], [4, 0, 4, 2, 1, 2]]
#                            7, 5, 3
#        [[1, 3, 2, 4, 4, 0, 1], [0, 4, 2, 4, 4, 0, 1], 
#          [0, 3, 3, 4, 4, 0, 1]]
#                            7, 5, 4
#        [[0, 0, 2, 3, 3, 1, 3], [4, 1, 2, 3, 3, 1, 3], 
#          [4, 0, 3, 3, 3, 1, 3], [4, 0, 2, 4, 3, 1, 3]]
#                            7, 5, 5
#        [[0, 2, 4, 0, 3, 0, 4], [4, 3, 4, 0, 3, 0, 4], 
#          [4, 2, 0, 0, 3, 0, 4], [4, 2, 4, 1, 3, 0, 4], 
#          [4, 2, 4, 0, 4, 0, 4]]
#                            8, 5, 3
#     [[0, 4, 3, 2, 4, 3, 3, 3], [4, 0, 3, 2, 4, 3, 3, 3], 
#       [4, 4, 4, 2, 4, 3, 3, 3]]
#                            8, 5, 4
#     [[2, 0, 0, 0, 3, 4, 2, 3], [1, 1, 0, 0, 3, 4, 2, 3], 
#       [1, 0, 1, 0, 3, 4, 2, 3], [1, 0, 0, 1, 3, 4, 2, 3]]
#                            8, 5, 5
#     [[4, 3, 4, 1, 1, 0, 2, 1], [3, 4, 4, 1, 1, 0, 2, 1], 
#       [3, 3, 0, 1, 1, 0, 2, 1], [3, 3, 4, 2, 1, 0, 2, 1], 
#       [3, 3, 4, 1, 2, 0, 2, 1]]
#                            9, 5, 3
#  [[4, 2, 3, 0, 2, 1, 3, 1, 2], [3, 3, 3, 0, 2, 1, 3, 1, 2], 
#    [3, 2, 4, 0, 2, 1, 3, 1, 2]]
#                            9, 5, 4
#  [[1, 3, 4, 1, 2, 0, 2, 3, 4], [0, 4, 4, 1, 2, 0, 2, 3, 4], 
#    [0, 3, 0, 1, 2, 0, 2, 3, 4], [0, 3, 4, 2, 2, 0, 2, 3, 4]]
#                            9, 5, 5
#  [[4, 1, 4, 4, 0, 1, 0, 3, 0], [3, 2, 4, 4, 0, 1, 0, 3, 0], 
#    [3, 1, 0, 4, 0, 1, 0, 3, 0], [3, 1, 4, 0, 0, 1, 0, 3, 0], 
#    [3, 1, 4, 4, 1, 1, 0, 3, 0]]
#                            10, 5, 3
#[[4, 3, 0, 3, 0, 1, 1, 4, 2, 0], [3, 4, 0, 3, 0, 1, 1, 4, 2, 0], 
#  [3, 3, 1, 3, 0, 1, 1, 4, 2, 0]]
#                            10, 5, 4
#[[4, 1, 2, 4, 3, 0, 1, 4, 1, 3], [3, 2, 2, 4, 3, 0, 1, 4, 1, 3], 
#  [3, 1, 3, 4, 3, 0, 1, 4, 1, 3], [3, 1, 2, 0, 3, 0, 1, 4, 1, 3]]
#                            10, 5, 5
#[[3, 2, 0, 0, 1, 0, 3, 0, 3, 4], [2, 3, 0, 0, 1, 0, 3, 0, 3, 4], 
#  [2, 2, 1, 0, 1, 0, 3, 0, 3, 4], [2, 2, 0, 1, 1, 0, 3, 0, 3, 4], 
#  [2, 2, 0, 0, 2, 0, 3, 0, 3, 4]]
#


# To obtain this data I used the following code:
#S:={2,3,5}:
#for q in S do:
# for n from 4 to 10 do:
#  for k from 3 to min(5,n) do:
#   print(n,q,k);
#   print(SearchLC(q,n,k, 10000));
#  od: 
# od:
#od: 


# inputs 
SearchLC := proc(q,n,k,K) local rv, i,j, basis, champ, memo, minw:
 champ := 0: 

for i from 1 to K do:
 rv := RV(q,n):
 basis := [seq(rv+[0$j, 1, 0$(n-(j+1))] mod q,j=0..(k-1))]:    # here we assume k < n but this is ok
 minw:=MinW(q,basis):                                          # I do this to avoid too many calls
 if  minw>champ then
  champ:=minw:
  memo:= basis:
 fi:
od:

memo:
end:


Help5:=proc(): print(`Nei(q,c), SP(q,c,t), GRC(q,n,d), GRCgs(q,n,d) , MinD(C), CV(S,n)`):
print(`BDtoC(BD,n)`):
end:

#Old code
#Jan. 29, 2024 C4.txt
Help4:=proc(): print(`Fqn(q,n), HD(u,v), RV(q,n) , RC(q,n,d,K), SPB(q,n,t), BDfano(), BDex212() `):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:

#Def. (n,M,d) q-ary code is a subset of Fqn(q,n) with M elements with
#minimal Hamming Distance d between any two members
#It can detect up to d-1 errors
#
#If d=2*t+1 correct t errors.
#
#
#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
#whenver 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:

BDfano:=proc():
{{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}:
end:




BDex212:=proc():
{{1,3,4,5,9},
{2,4,5,6,10},
{3,5,6,7,11},
{1,4,6,7,8},
{2,5,7,8,9},
{3,6,8,9,10},
{4,7,9,10,11},
{1,5,8,10,11},
{1,2,6,9,11},
{1,2,3,7,10},
{2,3,4,8,11}
}
end:

#end of old code

#Nei(q,c): all the neighbors of the vector c in Fqn(q,n)
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:=proc(q,n,d) local S,A,v:
A:=Fqn(q,n):
S:={}:
while A<>{} do:
 v:=A[1]:
 S:=S union {v}:
 A:=A minus SP(q,v,d-1):
od:
S:
end:


#GRCgs(q,n,d): George Spahn's version
GRCgs:=proc(q,n,d) local S,A,v:
print(`Warning: use at your own risk`):
A:=Fqn(q,n):
S:={}:
while A<>{} do:
 v:=A[rand(1..nops(A))()]:
 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}
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]}:
end:

##end of old stuff
#LtoC(q,M): inputs a list of basis vectors for our linear code over GF(q)
#outputs all the codewords (the actual subset of GF(q)^n with q^k elements
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:

#MinW(q,M): The minimal weight of the Linear code generated by M over GF(q)
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: