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

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

printf("Task 2\n"):
RB := [[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0]]:
for i from 1 to 5 do: for j from 1 to 11 do: printf("%a", RB[i][j]): od: printf("\n"): od:
printf("The initials RB can be more readily seen by using a different set of characters. One can verify that the correspondance between the two is one to one.\n"):
for i from 1 to 5 do: for j from 1 to 11 do: if RB[i][j] = 1 then: printf("⬛"): else: printf(" "): fi: od: printf("\n"): od:
RB_collapsed := [seq(op(RB[i]), i = 1..5)]:
printf("Collapse to a vector with the following:\nRB_collapsed := [seq(op(RB[i]), i = 1..5)]: %a\n", RB_collapsed):

printf("\nTask 3\n"):
for n from 5 to 16 do:
  for d in [3, 5, 7] do:
	m := max(seq(nops(RC(2, n, d, 1000)), i = 1..10)):
	printf("Max found for RC(%a, %a, %a, %a): %a\n", 2, n, d, 1000, m):
  od:
od:
printf("These values are noticeably less than those in the book.\n"):

printf("\nTask 4\nAccording to the Sphere Packing Bound, we may observe M = trunc(q^n/add(binomial(n,i)*(q-1)^i,i=0..t)). Beyond this, we are only interested in scenarios in which q=2, t=(3-1)/2=1, and n=s^r-1. Substituting, we get M = 2^(2^r - r - 1)\n"):