# OK to post

# PART 2: DRAWING INITIALS:
# -----------------------

# output (5x11):
####..#####
#...#.#....
#...#.####.
#...#.#....
####..#####

Initials:=[
    1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1,
    1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0,
    1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0,
    1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0,
    1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1
];

# PART 3: COMPARING RC() TO BEST POSSIBLE CODES:
# -----------------------

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

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

# inputs q,n,d,K and keeps picking K random vectors
# whenever the new vector is not distance <=d-1 from the previous ones, we accept it
RC:=proc(q,n,d,K) local C,v,i,c:
	C:={RV(q,n)};

	for i from 1 to K do
		v:=RV(q,n);
		if min(seq(HD(v,c), c in C)) >= d then
			C:=C union {v};
		fi;
	od;

	return C;
end;

# d=3, d=5:
for n from 5 to 16 do:
    Code:=RC(2,n,3,10000);
    print(cat("Code size for n=", n, ", d=3: ", nops(Code)));

    Code:=RC(2,n,5,10000);
    print(cat("Code size for n=", n, ", d=5: ", nops(Code)));
od;

# d=7:
for n from 7 to 16 do:
    Code:=RC(2,n,7,10000);
    print(cat("Code size for n=", n, ", d=7: ", nops(Code)));
od;

# after running the above code multiple times, it seems that the size of the codes
# generated varies greatly from run to run, which makes sense due to the random nature.

# the codes are also much, much smaller than what is given in the table, which again makes
# sense due to the random nature.

# PART 4: SIZE OF PERFECT HAMMING CODES:
# -----------------------

# sphere packing bound:
SPB:=proc(q,n,t) local i:
	trunc(q^n / add(binomial(n,i)*(q-1)^i, i=0..t));
end;

SPB(2, 2^r-1, 1);

# simplifying the expression given above, we get that the size of the perfect hamming codes as:
# 2^(2^r-1-r)
# so the size of the perfect hamming codes are always a power of 2