# OK to post

# PART 2: EXERCISES FROM HILL'S BOOK:
# -----------------------

# - exercise 5.1 -
# no, a linear q-ary [n,k,d] code is a q-ary (n,q^k,d) code, but 24 is not a power of 2 
# so this is not possible

# - exercise 5.2 -
# the parameters of En are [n,n-1,2]
# a possible generating matrix is:
# (n-1) x n
# [ 1 0 0 0 ... 0 1 ]
# [ 0 1 0 0 ... 0 1 ]
# [ ........... 0 1 ]
# [ 0 0 0 0 ... 1 1 ]

# - exercise 5.3 -
# Let x,y in C. Then x+y is in C since both x and y are in V(n,q) and we have that
# (x+y)H^T = xH^T + yH^T = 0+0 = 0

# Let x in C and a in GF(q). Then ax is in C since x is in V(n,q) and we have  that
# (ax)H^T = a(xH^T) = a(0) = 0

# - exercise 5.5 -
# First note that w(x+y) = w(x) + w(y) - 2w(x intersect y), so if x and y both have even weight,
# then w(x+y) is even. And if x has even weight and y odd, then w(x+y) is odd.

# Now, assume that in a linear code C, at least 1 of the codewords as odd weight (if they all have
# even weight the proof is done.) Label the odd-weight codeword x. Then, for every codeword y in C
# such that y =/= x, x+y must be in C and have odd weight as shown earlier. So for every even-weight codeword
# y, there exists an odd weight codeword x+y. x itself is included since 0+x=x. Thus, the code must have
# half even and half odd-weight codewords.

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

# randomly generates linear codes and ouputs the one of largest minimum weight
SearchLC:=proc(q,n,k,K): local i,j,M,w,bestM,bestW:
    bestW:=0;
    bestM:=[];

    for i from 1 to K do:
        M:=[];
        for j from 1 to k do:
            M:=[op(M), RV(q,n)];
        od;

        w:=MinW(q,M);
        if w > bestW then
            bestW:=w;
            bestM:=M;
        fi;
    od;

    return bestM;
end;

# PART 4: SF() PROCEDURE:
# -----------------------

# gets a row from a matrix
GetRow:=proc(M,r) local v,i,n:
    v:=[];
    n:=nops(M[1]);

    for i from 1 to n do:
        v:=[op(v),M[r,i]];
    od;

    return v;
end;

# sets a row in a matrix
SetRow:=proc(M,r,v) local i,M1:
    M1:=copy(M);
    
    for i from 1 to nops(v) do:
        M1[r,i]:=v[i];
    od;

    return M1;
end;

# gets a column from a matrix
GetCol:=proc(M,c) local v,i,n:
    v:=[];
    n:=nops(M);
    
    for i from 1 to n do:
        v:=[op(v),M[i,c]];
    od;

    return v;
end;

# sets a column in a matrix
SetCol:=proc(M,c,v) local i,M1:
    M1:=copy(M);
    
    for i from 1 to nops(v) do:
        M1[i,c]:=v[i];
    od;

    return M1;
end;

# returns matrix M in standard form
SF:=proc(q,M) local k,n,i,j,S,rj,cj,ri:
    k:=nops(M);
    n:=nops(M[1]);
    S:=copy(M);

    for i from 1 to k do: # algorithm is iterated from 1 to k
        # if S_ii = 0, then we need to perform a swap:
        if S[i,i] = 0 then 
            for j from i+1 to k while S[j,i] = 0 do od; # look for available row

            if j<=k then # swap rows
                rj:=GetRow(S,j);
                S:=SetRow(S,j, GetRow(S,i));
                S:=SetRow(S,i,rj);

            else # look to swap columns

                for j from i+1 to n while S[i,j] = 0 do od; # look for available col

                # swap cols
                cj:=GetCol(S,j);
                S:=SetCol(S,j, GetCol(S,i));
                S:=SetCol(S,i,cj);
            fi;
        fi;

        # scale row to have leading entry 1
        ri:=GetRow(S,i);
        ri:=(ri*(ri[i]&^(-1) mod q)) mod q;
        S:=SetRow(S,i,ri);

        for j from 1 to k do:
            if j <> i then
                rj:=GetRow(S,j);
                rj:=(rj - (rj[i] * ri mod q)) mod q;
                S:=SetRow(S,j,rj);
            fi;
        od;
    od;

    return S;
end;

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

# a random word of length n in {0, ..., q-1}
RV:=proc(q,n):
	return [seq(rand(0..q-1)(),1..n)];
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;

# 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;

# MinW(q,M): The minimal weight of the linear code generated by M over GF(q)
MinW:=proc(q,M) local n,c,C:
    n:=nops(M[1]);
    C:=LtoC(q,M);

    return min(seq(HD(c, [0$n]), c in C minus {[0$n]}));
end;