# OK to post

# PART 2: TYPOS
# -----------------------
# For (a) the "channel+noise" should be 0100
# For (b) the "channel+noise" should be 0001

# PART 3: LC() PROCEDURE
# -----------------------

# outputs 1 with probability 1/N, 0 otherwise
LC:=proc(N)
    if rand(1..N)() = 1 then
        return 1;
    else
        return 0;
    fi;
end;

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

# PART 4: TestCode() PROCEDURE
# -----------------------
TestCode:=proc(q,n,C,N,K) local i,j,co,v,v1,T:
    co:=0;
    T:=DecodeT(q,n,C);

    for i from 1 to K do:
        v:=C[rand(1..nops(C))()];
        v1:=copy(v);

        for j from 1 to nops(v1) do:
            v1[j]:=v1[j]+LC(N) mod q;
        end;

        if T[v1] <> v then
            co:=co+1;
        fi;
    od;

    return evalf(co/K);
end;

# PART 5: RUNNING TestCode()
# -----------------------

possibleN:=[2,3,4,5,6,7,8,9,10,15,20,30];
C:=GRC(2,7,3);

for i from 1 to nops(possibleN) do:
    #TestCode(2,7,C,possibleN[i],10000);
od;

# PART 6: SA() PROCEDURE
# -----------------------

# get vector of smallest weight among a
minW:=proc(A) local n,a,w,best,bestW:
    n:=nops(A[1]);
    best:=A[1];
    bestW:=HD(A[1],[0$n]);

    for a in A do:
        w:=HD(a,[0$n]);

        if w < bestW then
            best:=a;
            bestW:=w;
        fi;
    od;

    return best;
end;

# SA(q,n,M): inputs a basis M of a linear [n,nops(M),d] code outputs Slepian's
# standard array as a matrix of vectors containing all the vectors in GF(q)^n (alas Fqn(q,n))
# such that the first row an ordering of the members of the actual code (LtoC(M)) with
# [0$n] the first entry and the first columns are the coset representatives
SA:=proc(q,n,M) local SL,C,A,r,coset:
    C:=LtoC(q,M);
    C:=C minus {[0$n]}:

    SL:=[[[0$n],op(C)]];
    A:=Fqn(q,n) minus {op(SL[1])};

    while nops(A) > 0 do:
        coset:=minW(A);

        SL:=[op(SL), [coset$n]+SL[1] mod q];
        A:=A minus {op(SL[nops(SL)])};
    od;

    return SL;
end;

############################################################## OLD CODE ##############################################################

# LtoC(q,M): inputs a list of basis vectors for our linear code over GF(q)
# outputs all the codewords (the actual subset of GF(q)^n with q^k elements)
LtoC:=proc(q,M) local n,k,C,i,M1,c:
    option remember;
    
    k:=nops(M);
    n:=nops(M[1]);

    if k=1 then
        return {seq(i*M[1] mod q, i=0..q-1)};
    fi;

    M1:=M[1..k-1];
    C:=LtoC(q, M1);
    return {seq(seq(c + i*M[k] mod q, i=0..q-1), c in C)};
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(c[1..i-1]), a, op(c[i+1..n])], 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;

Fqn:=proc(q,n) local S,a,v:
	option remember:
	if n=0 then
		return {[]};
	fi;

	S:=Fqn(q,n-1);
	return { seq(seq([op(v),a],a=0..q-1), v in S) };
end;

# hamming distance
HD:=proc(u,v) local i, c:
	# TODO: type checking
	
	if nops(u) <> nops(v) then
		return FAIL;
	fi;

	c:=0;
	for i from 1 to nops(u) do
		if u[i] <> v[i] then
			c:=c+1;
		fi;
	od;

	return c;
end;

# NN(C,v), inputs a code C (subset of Fqn(q,n) where n:=nops(v)) finds 
# the set of members  of C closest to v
NN:=proc(C,v) local i,rec,cha:
    cha:={C[1]};
    rec:=HD(C[1],v);

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

    return cha;
end;

# constructs once and for all a table that sends every member of Fqn(q,n) to one
# of C's nearest neighbors
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;

    return op(T);
end;