# OK to post homework
# Alex Varjabedian, 9-Feb-2024, Homework 7

Help := proc() print(`LC(N)\nTestCode(q, n, C, n, K)`) end:
with(linalg):

##################
# -------------- #
# PART 3 - LC(N) #
# -------------- #
##################

print(`PART 3`);

LC := proc(N) if rand(1..N)() = 1 then 1 else 0 fi end:

# Testing LC(N)
add(x[LC(10)],i=1..10000); 

####################################
# -------------------------------- #
# PART 4 - TestCode(q, n, C, N, K) #
# -------------------------------- #
####################################

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:

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:

NN := proc(C, v) local i, rec, cha:
cha := {C[1]}:
rec := HD(v, C[1]):
for i from 2 to nops(C) do
 if HD(v, C[i]) < rec then
  cha := {C[i]}:
  rec := HD(v, C[i]):
 elif HD(v, C[i]) = rec then
  cha := cha union {C[i]}:
 fi:
od:
cha:
end:

DecodeT := proc(q, n, C) local S, v, T:
S := Fqn(q, n):
for v in S do T[v] := NN(C, v)[1] od:
op(T):
end:

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

TestCode := proc(q, n, C, N, K) local T, v, v1, x, co, i:
co := 0:
for i from 1 to K do
 T := DecodeT(q, n, C):
 v := C[rand(1..nops(C))()]:
 v1 := []:
 for x in v do v1 := [op(v1), x + LC(N) mod q] od:
 if T[v1] <> v then co := co + 1 fi:
od:
evalf(co/K): # return failure rate
end:

###############################
# --------------------------- #
# PART 5 - Testing Testcode() #
# --------------------------- #
###############################

print(`PART 5`);

# Testing TestCode with GRC(2, 7, 3), and for each N = 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 30
C := GRC(2, 7, 3):	
for N from 2 to 10 do print(TestCode(2, 7, C, N, 10000)) od:
print(TestCode(2, 7, C, 15, 10000)):
print(TestCode(2, 7, C, 20, 10000)):
print(TestCode(2, 7, C, 30, 10000)):
print(`The failure rates decrease as N increases, and they seem to be roughly equally small when N = 20 or N = 30`);