Hamming Codes in CF

import {log, floor, ceil} from "math.cf"


# Prep

[Bit] ->> Num
XOR_reduce = [] => 0
XOR_reduce = bits >\> (^) 0    # reduce using XOR operator


# Encoding

Num -> Bool
is_power_of_two = x <= 0 => False
is_power_of_two = x % 2 == 1 => False
is_power_of_two = x => ceil <- log 2 x == floor <- log 2 x


[Bit] ->> [Num]
parity_spots = [] => 0
parity_spots = {
  bits => [0..2..length bits]''0,
  indices \\> is_power_of_two indices,
}

[Bit], [Num], Num ->> [Bit]
create_message_without_ps = [], _, _ => []
create_message_without_ps = _, [], _ => []
create_message_without_ps = _, _, x < 0 => []
create_message_without_ps = _, _, x % 1 != 0 => []
create_message_without_ps = (b, ...bs), (n, ...ns), i =>
  n == i
    ? [0, ... create_message_without_ps [b, ...bs] ns i+1]    # Adds a 0 to the list, burns the index
    : [b, ... create_message_without_ps bs [n, ...ns] i+1]    # Adds the current bit to the list, burns it


Num, Num ->> [Num]
get_bits_indices = _, 0 => []
get_bits_indices = with input(idx, maxlen) do:
  #! Bad solution, temporary
  current = Mut idx
  indices = Mut []
  count = Mut 0
  skipping = Mut False
  while current < maxlen:
    if not skipping:
      indices = Mut [...indices, current]
    if count == idx:
      skipping = Mut not skipping
      count = Mut 0
    ++ current
    ++ count
  return Const indices


[Bit], Num ->> [Bit]
get_bits_to_check = [], _ => []
get_bits_to_check = bits, idx => bits[get_bits_indices <- idx length bits]


[Bit], [Num] ->> [Bit]
ajust_sequence = [], _ => []
ajust_sequence = bits, [] => bits
ajust_sequence = (bits, parity_indices)
  with (zip bits [0..])''0 as (bit, i) =>
  i in parity_indices
    ? XOR_reduce get_bits_to_check bits i
    : bit


[Bit] ->> [Bit]
create_message = [] => []
create_message = with input(bits) do:
  spots = parity_spots bits
  seq = create_message_without_ps bits spots 0
  final = ajust_sequence seq spots
  return @final


# Decoding

[Bit] ->> Num
find_error = {
  bits => zip bits [0..],
  bits ''> 0,     # normally a single quote, double here to not mess with the colors, creates a map from the list
  (bit, index) \\> Bool bit,     # filter to have only the 1-bits
  (bit, index) => index,
  XOR_reduce,
  location => @location,
}