# Okay to post homework
# Ryan Badi, February 4, 2024, Homework #5

Help := proc():
  printf("Available processes: HD(u, v) RV(q, n) RC(q, n, d, K) SPB(q, n, d) PlotkinBound(n, d)\n"):
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:

# Hamming Distance between two words of the same length
HD := proc(u, v) local i, hd:
  if nops(u) <> nops(v) then return FAIL fi:
  hd := 0:
  for i from 1 to nops(v) do if v[i] <> u[i] then hd := hd + 1 fi od:
  return hd:
end:

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

# Generates K words all within distance d of at least one other
RC := proc(q, n, d, K) local W, i, v, w:
  W := {RV(q, n)}:
  for i from 1 to K do:
    v := RV(q, n):
    if min(seq(HD(v, w), w in W)) >= d then W := W union {v} fi:
  od:
  return W:
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:

# 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):
  return {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:
  return 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:
  return S:
end:

Tasks345 := proc() local d, n, grc:
  printf("\nTask 3\n"):
  for d in [3, 5, 7] do:
    for n from 5 to 20 do:
      grc := nops(GRC(2, n, d)):
      printf("(q, d, n) = (%a, %a, %a)\tCardinality: %a\tDistance from SPB: %a\n", 2, d, n, grc, grc - SPB(2, n, d)):
    od:
  od:
  printf("\nTask 4\n"):
  for d in [3, 5, 7] do:
    for n from 5 to 10 do:
      grc := nops(GRC(3, n, d)):
      printf("(q, d, n) = (%a, %a, %a)\tCardinality: %a\tDistance from SPB: %a\n", 3, d, n, grc, grc - SPB(3, n, d)):
    od:
  od:
  printf("\nTask 5\n"):
  for d in [3, 5, 7] do:
    for n from 5 to 7 do:
      grc := nops(GRC(5, n, d)):
      printf("(q, d, n) = (%a, %a, %a)\tCardinality: %a\tDistance from SPB: %a\n", 5, d, n, grc, grc - SPB(5, n, d)):
    od:
  od:
end:

PlotkinBound := proc(n, d):
  if d mod 2 = 0 then:
    if n < 2 * d then return 2 * trunc(d / (2 * d - n)) fi:
	return 2 * trunc((d + 1) / (2 * d - n + 1)):
  fi:
  if d mod 2 = 0 then return 4 * d else return 4 * d + 4 fi:
end:

printf("Task 2.1\n(6, 2, 6): {000000, 111111}\n(3, 8, 1): {000, 001, 010, 011, 100, 101, 110, 111}\n(4, 8, 2): {0000, 1001, 1010, 0011, 1100, 0101, 0110, 1111}\n(5, 3, 4): Impossible. We may begin arbitrarily with 00000 and 01111. To be distant enough from 0000, a third word must contain 4 or 5 1's (1 or 0 0's). But no such words would be distant enough from 01111 (or any other arbitrary choice of a second word).\n(8, 30, 3): Impossible. As seen by the Sphere Packing Bound, M will have an upper limit of 2^8/9 = 28 < 30."):
printf("\nTask 2.2\nGoing from binary words of length n to length n-1 reduces the number of words by half. As such even if all removed words contribute to M (which is unlikely), M/2 valid words will still remain. Therefore M' >= M/2.\nIn the same logical vein, when going from n-1 to n, we double the available number of words to choose from. In the best case scenario, every single new word is valid, doubling the contribution to A.\n"):
printf("\nTask 2.3\nWe can simply take two linearly independent vectors as a basis. For instance, in q=2, we can 01 and 10 as a basis. From here, we take every linear combination of our two basis vectors up to a multiple of q. This yields q^2 vectors, each satisfying the desired conditions."\n):
printf("\nTask 2.4\nThe parity check ensures we have an even weight, as an odd parity will have a parity check of 1 and and even parity will have a parity check of 0. Further, because F has a minimum distance 1, E must have a minimum distance 2.\n"):
Tasks345():
for d from 2 to 20 do:
  for n from 2 to 2 * d do:
    spb := SPB(2, n, d):
	pb := PlotkinBound(n, d):
    if spb > pb then: printf("(q, n, d) = (%a, %a, %a): Sphere Packing Bound: %a\n", 2, n, d, spb) else printf("(q, n, d) = (%a, %a, %a): Plotkin Bound: %a\n", 2, n, d, pb) fi:
  od:
od: