# HW 5, Pablo Blanco
# OK to post
 
# Sphere Packing Bound for q=2
# M <= 2^n/(1+n+\binom{n}{2}+...+\binom{n}{t})

# 2.1
# (6,2,6). Consider codes (1$6) and (0$6) 
# (3,8,1). There are 8 distinct binary codes on 3 coordinates, so take all of them and they satisfy this.
#
# (4,8,2). I don't think this is possible. It's unclear me what the sphere 
# packing bound is for even d, but if it uses t = \ceil{d/2}, then that 
# should disprove this case because 1 + n = 5 because then the packing bound # is SPB = 2^4/5 < 2^3/2 = 2^3 = 8 = M. 
#
# (5,3,4). This is impossible. Suppose there is such a set of codes S.
# Pick two distinct codes c1 and c2. Then they differ on four coordinates
# WLOG assume the first four coordinates. c1 = (0,0,0,0,1), c2=(1,1,1,1,i)
# up to complementation and relabeling. where i \in {0,1}. a third code
# c3 could not satisfy the first 3 distinct coordinates on the first four
# coordinates so it overlaps with c1 or c2.
#
# (8,30,3). Impossible. Use sphere packing bound and see that
# M <= 2^8/(1+8) < 29. However, the desired M value exceeds this.

# 2.2
# Consider truncating the last coordinate in every code. 
# Let S be a set of codes satisfying (n,M,d). Let A be the codes in S with
# last coordinate 0. Let B be the codes in S with last coordinate 1.
# WLOG, let |A| \ge |B|. So we have that |A|\ge M/2. Let M' be A after 
# truncating the last coordinate, we note that the vectors in M'
# satisfy their d-differences in their initial 1st through (n-1)-th 
# coordinate. As a result, M' has difference d and we have (n-1,M/2, d) 
# codes.

# 2.3 
# not sure how to do this one :(

# 2.4
# the vectors E_n are in bijection to the vectors (F_2)^{n-1} because their n-th coordinate is determined by
# their first (n-1) coordinates, which is equivalent to a parity check on them.

# data is formatted as (q,n,d) followed by the code cardinality.
                            # (2, 5, 3):                                4
                            # (2, 6, 3):                                8
                            # (2, 7, 3):                                16
                            # (2, 8, 3):                                16
                            # (2, 9, 3):                                32
                            # (2, 10, 3):                                64
                            # (2, 11, 3):                               128
                            # (2, 12, 3):                               256
                            # (2, 13, 3):                               512
                            # (2, 14, 3):                               1024
                            # (2, 15, 3):                               2048
                            # (2, 16, 3):                               2048
                            # (2, 17, 3):                               4096
                            # (2, 18, 3):                               8192
                            # (2, 19, 3):                              16384
                            # (2, 20, 3):                              32768
                            # (2, 5, 5):                                2
                            # (2, 6, 5):                                2
                            # (2, 7, 5):                                2
                            # (2, 8, 5):                                4
                            # (2, 9, 5):                                4
                            # (2, 10, 5):                                8
                            # (2, 11, 5):                                16
                            # (2, 12, 5):                                16
                            # (2, 13, 5):                                32
                            # (2, 14, 5):                                64
                            # (2, 15, 5):                               128
                            # (2, 16, 5):                               256
                            # (2, 17, 5):                               512
                            # (2, 18, 5):                               512
                            # (2, 19, 5):                               1024
                            # (2, 20, 5):                               2048
                            # (2, 5, 7):                                1
                            # (2, 6, 7):                                1
                            # (2, 7, 7):                                2
                            # (2, 8, 7):                                2
                            # (2, 9, 7):                                2
                            # (2, 10, 7):                                2
                            # (2, 11, 7):                                4
                            # (2, 12, 7):                                4
                            # (2, 13, 7):                                8
                            # (2, 14, 7):                                16
                            # (2, 15, 7):                                32
                            # (2, 16, 7):                                32
                            # (2, 17, 7):                                64
                            # (2, 18, 7):                               128
                            # (2, 19, 7):                               256
                            # (2, 20, 7):                               512

                          # (3, 5, 3):                             9
                          # (3, 6, 3):                             24
                          # (3, 7, 3):                             72
                          # (3, 8, 3):                             198
                          # (3, 9, 3):                             519
                          # (3, 10, 3):                             1390
                          # (3, 5, 5):                              3
                          # (3, 6, 5):                              3
                          # (3, 7, 5):                                8
                          # (3, 8, 5):                                18
                          # (3, 9, 5):                              39
                          # (3, 10, 5):                                83
                          # (3, 5, 7):                                1
                          # (3, 6, 7):                                1
                          # (3, 7, 7):                              3
                          # (3, 8, 7):                              3
                          # (3, 9, 7):                              3
                          # (3, 10, 7):                                9

                            # (5, 5, 3):                                74
                            # (5, 6, 3):                                265
                            # (5, 7, 3):                               1113
                            # (5, 5, 5):                                5
                            # (5, 6, 5):                                13
                            # (5, 7, 5):                                39
                            # (5, 5, 7):                                1
                            # (5, 6, 7):                                1
                            # (5, 7, 7):                                5



# Class code
#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:

#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:
# end class code

# the following optimized procedure for GRC is due to Robert (running times were too slow)
GRCrdb:=proc(q,n,d) local S,A,v:
A:=MutableSet(Fqn(q,n)):
S:={}:
sphere := SP(q, [0 $ n], d - 1):
while not empty(A) do
 v:=A[1]:
 S:=S union {v}:
 sp := map(x -> (x + v) mod q, sphere):
 A &minus MutableSet(sp):
od:
S:
end:
# 

# this is the code I used to obtain my data
dataRun := proc(q,N) local n,d:
d:=3:
n:=5:
while d < 8 do: 
 while n < N+1 do:
  print(q,n,d):
  print(nops(GRCrdb(q,n,d))):
  n:=n+1:
 od:
 n:=5:
 d:=d+2: 
od:

end: