Решение задачи о поиске двоичного периода числа на Haskell

Не так давно на хабре проскочила заметка, в которой автор описывал задачи, требующие решения для получения доступа на некую зарубежную биржу фриланса. Одна из задач звучала так: имеется некоторое целое число N в диапазоне от 1 до 1,000,000,000. Необходимо найти двоичный период этого числа. Что такое двоичный период ? Это количество символов двоичной последовательности наименьшей длины, которая будучи повторена минимум 2 раза приведет при её зацикливании к получению этого самого числа N на длине двоичного представления N.

На примерах это будет выглядеть так. Двоичный период чисел 1 или 0 не определен, так как двоичная "0" или "1" даже воспроизводя образ чисел 1 или 0 будет повторяться максимум 1 раз.

Двоичный период числа 127 равен 1, так как двоичное представление числа 127 - суть "1111111" (7 единиц), и двоичная последовательность наименьшей длины, которая при зацикливании воссоздаст двоичное представление числа 127 - это 1. А длина двоичного представления единицы тоже равна одному.

Рассмотрим число 955. Двоичное представление его есть "1110111011". Видно, что паттерн "1110" при повторе его 3 раза (третий раз - только первые 2 знака) даст нам полное повторение двоичного представления числа 955. Длина этого паттерна равна 4, а значит и двоичный период тоже равен 4.

Итак, суть понятна. Попробуем решить эту задачу на Haskell.


Ниже приведу код, который получился у меня, и кратко прокомментирую его.

===

{- вычисление двоичного периода числа -}

binaryStr :: Int -> String -> String
binaryStr 0 []  = "0"
binaryStr 0 acc = acc
binaryStr n acc =  binaryStr
                   (div n 2)
                   ((head $ show $ mod n 2) : acc)

calcPeriod :: String -> Int -> Int -> Int
calcPeriod _     _     0  = 0
calcPeriod bStr shift max =
    let lst1 = drop shift bStr in
    let lst2 = take (length lst1) $ cycle $ take shift bStr in
    if lst1 == lst2 then shift
    else calcPeriod bStr (shift+1) (max-1)

main :: IO ()
main = do
    numStr <-getLine
    let bStr = binaryStr (read numStr :: Int) []
    let cyclesCnt = div (length bStr) 2
    let r = calcPeriod bStr 1 cyclesCnt
    if r == 0 then
        putStrLn $"Sorry, binary period for \"" ++ bStr ++ "\" is not found..."
    else
        putStrLn $ "Binary period for \"" ++ bStr ++ "\" is " ++ (show r)
===

binaryStr получает на вход целое число и возвращает в виде строки двоичное представление этого числа.

caclPeriod - это основная функция, которая и выполняет, собственно, расчет двоичного периода числа. Работает она следующим образом: в цикле от 1 до половины длины двоичного представления числа   (начинаем с самых коротких строк) формируется 2 списка: первый (lst1) -это двоичное представление нашего числа, у которого пропушены первые shift символов. То есть, если у нас shift - 2, а двоичное представление числа - "10011101", то lst - список "011101".

Второй список (lst2) формируется так: берется "отрезанная от начала первого списка" двоичная последовательность и просто "размножается" на длину этого первого списка. Для нашего примера выше мы получаем список "101010", то есть, первые 2 символа - "10", размноженные на длину 6 нашего первого списка ("011101"). Ну и последнее действие - простое сравнение полученных списков на равенство. Если списки равны, то "отрезанная" часть позволяет методом копирования получить двоичное представление нашего искомого числа, а значит и является двоичным периодом числа (не забываем, что мы идем в цикле от меньших длин к 

бОльшим, то есть, первое же равенство списков вернет нам правильный результат). 

Ну а остальная часть - функция main, которая, по сути, лишь принимает входные данные и выдает на экран результат.

Для интереса проверим, есть ли двоичный период у числа 1,000,000,000. После запуска

получаем следующий ответ:

==

Sorry, binary period for "111011100110101100101000000000" is not found...

==

Вот такая печаль.

На этом все. Надеюсь, что вам было интересно )

Дополнение.

Слегка оптимизировал код для того, чтобы он более соответствовал духу функциональности, что ли... ) В общем, получилось чуть короче, но в ущерб скорости выполнения (а кому сейчас легко ?). Итак:
===
{- вычисление двоичного периода числа (модифицированный вариант -}

int2bin 0 = []
int2bin n = int2bin (n `div` 2) ++ [n `mod` 2]

myMin [] = 0
myMin lst = minimum lst

bPeriod lst = myMin $ filter (>0) $ map (\sh -> 
                    if (take (length lst - sh) $ cycle $ take sh lst) == drop sh lst then sh else 0
              ) [1.. (length lst) `div` 2]

main = do
    bStr <- getLine
    print $ (bPeriod . int2bin) (read bStr :: Int)
====

Возвращает 0, если бинарного периода нет, ну или само значение бинарного периода, если он, все-таки, есть.