import Data.List (intercalate)

xor a b = (a || b) && not (a && b)

triangle [] = []
triangle l@(x:xs) = [l] ++ (triangle $ zipWith xor l xs)

num2string _ _ 0 = "1"
num2string result var n
	| mod n 2 == 0 = num2string result (pred var) $ div n 2
	| n == 1 = (var:result)
	| otherwise = num2string (var:result) (pred var) $ div n 2

letter x n
	| n <= 1 = x
	| otherwise = letter (succ x) (pred n)

zhegalkin [] = []
zhegalkin l
	| l == [] = "1"
	| (length l) /= 2 ^ varCount = error "Incorrect list length"
	| otherwise = intercalate "+" $ filter (/= "") $ map stringFactor $ zip (map head (triangle l)) [0..]
	where	stringFactor x
			| fst x = num2string "" (letter 'A' varCount) $ snd x
			| otherwise = []
		varCount = truncate $ logBase 2 $ fromIntegral $ length l