# Shaurya Baranwal Homework 5 due February 4, 2024

#---------------------------------------------------------------------

#All the functions needed to do certain parts will be up here, but other parts to write function will be in their respective places

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:=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:=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:


my_SPB := proc(n) 2^n / (1 + n) end:

#---------------------------------------------------------------------

# Part 1, Chapter 2 of Hill's Book, exercises 2.1, 2.2, 2.3, 2.4

#---------------------------------------------------------------------

# Exercise 2.1
# _____________
# i) [000000,111111] ii) [000, 101, 110, 011, 001, 010, 100, 111] iii) [0000, 1100, 0011, 1111, 1010, 0101, 0111, 1110] iv) not possible v) not possible

# Exercise 2.2
# _____________
# By looking at the last digit we know that at least half of them will either end in 1's or 0's. So we then achieve >=M/2, By deleting the last coordinate we then have n-1. By this we have that M=A2(n,d), which now becomes M=2A2(n-1,d).

# Exercise 2.3 
# _____________
# I'm not to sure how to prove this and where to start. 

# Exercise 2.4
# _____________
# I'm not to sure what to do here. 

#---------------------------------------------------------------------

# Part 3, Use GRC(q,n,d) with q=2, d=3,5,7, and 5 ≤ n ≤20, for each case find the cardinality. Also, find the Sphere-Packing Bound

#---------------------------------------------------------------------

q := 2:
d := [3,5,7]:
n := [seq(5..20)]:
elem := []:
printf("-------------------------------------------\n With q=%a\n", q):
for i in n do:
  for j in d do:
    elem := nops(GRC(q,i,j)):
    printf("With d=%a, n=%a, the cardinality is %a.\n", j, i, elem);
  od:
od:

#---------------------------------------------------------------------

# Part 4, Use GRC(q,n,d) with q=3, d=3,5,7, and 5 ≤ n ≤10, for each case find the cardinality. Also, find the Sphere-Packing Bound

#---------------------------------------------------------------------

q := 3:
d := [3,5,7]:
n := [seq(5..10)]:
elem := []:
printf("-------------------------------------------\n With q=%a\n", q):
for i in n do:
  for j in d do:
    elem := nops(GRC(q,i,j)):
    printf("With d=%a, n=%a, the cardinality is %a.\n", j, i, elem);
  od:
od:

#---------------------------------------------------------------------

# Part 5, Use GRC(q,n,d) with q=5, d=3,5,7, and 5 ≤ n ≤7, for each case find the cardinality. Also, find the Sphere-Packing Bound

#---------------------------------------------------------------------

q := 5:
d := [3,5,7]:
n := [seq(5..7)]:
elem := []:
printf("-------------------------------------------\n With q=%a\n", q):
for i in n do:
  for j in d do:
    elem := nops(GRC(q,i,j)):
    printf("With d=%a, n=%a, the cardinality is %a.\n", j, i, elem);
  od:
od:

#---------------------------------------------------------------------

# Part 7

#---------------------------------------------------------------------

PlotkinBound := proc(n, d) 2*floor(d/(2*d - n)) end:

for d from 2 to 20 do:
  t := trunc((d-1)/2):
  for n from 2 to 2*d-1 do:
    if PlotkinBound(n,d) > my_SPB(n) then print("PlotkinBound"): fi:
    if PlotkinBound(n,d) < my_SPB(n) then print("Sphere Packing Bound"): fi:
    if PlotkinBound(n,d) = my_SPB(n) then print("Equal"): fi:
  od:
od: