Жадный алгоритм на OCaml :: Разработка на коленке tinycode.ru

Записался слушателем курса Algorithmic Toolbox (бесплатно халявный вариант).

Сегодня утром слушал про жадный алгоритм для поиска групп детей, у которых разница в возрасте не должна превышать год. Поскольку халявщикам нельзя отправлять свои решения, а платить за этот курс я не планирую, то написал свой жадный алгоритм на OCaml, вместо предлагаемых в курсе питона и С++.

Условия под которые писался этот код:

данные вводятся из терминала;
возраст даётся в месяцах, чтобы не возиться с преобразованием и обойтись одной функцией ввода;
рекурсия должна быть хвостовой.

let scan_int () = Scanf.scanf " %d" (fun x -> x)


let rec scan_ages = function (* Возраст в месяцах *)
    | 0 -> []
    | n -> scan_int () :: scan_ages (n - 1)


let print_groups lst =
    print_endline "Groups: ";

    List.iter (fun sub_list ->
        sub_list |> List.map string_of_int
                 |> String.concat " "
                 |> print_endline
    ) lst


let find_groups lst =
    let max_diff = 12 in
    let rec _find lst first group total =
        match lst with
        | [] -> (
            match group with
            | [] -> total
            | _ -> group :: total)
        | hd :: tl -> (
            match compare (hd - first) max_diff with
            | 0 | -1 -> _find tl first (hd :: group) total
            | 1 -> _find tl hd [hd] (group :: total)
            | _ -> invalid_arg "Wrong answer from compare!")
    in

    match List.sort compare lst with
    | [] -> []
    | hd :: tl -> _find tl hd [hd] []


let () =
    scan_int () |> scan_ages
                |> List.sort compare
                |> find_groups
                |> print_groups;

Тестирование

Потом, следуя рекомендациям курса, я начал писать тесты. Первым делом мне понадобился способ создавать тестовую выборку.

let make_test () =
    let rec gen n =
        match compare n 0 with
        | 0 | 1 -> (Random.int 115) + 6 :: gen (n - 1) (* Возраст от 6 месяцев до 10 лет *)
        | _ -> []
    in
    gen ((Random.int 100) + 1) (* От одного до 100 детей в группе *)

Помимо тестовых данных нужна функция проверки равенства двух списков групп:

let compare_groups g1 g2 =
    let sorted lst =
        List.map (List.sort compare) lst |> List.sort compare
    in
    let even = match compare (List.length g1) (List.length g2) with
    | 0 -> sorted(g1) = sorted(g2)
    | _ -> false
    in
    even

И ещё нужна реализация алгоритма разбиения каким-нибудь простым способом. Для этого я выбрал тот же жадный алгоритм, но в императивном стиле, потому что по поводу правильности жадного алгоритма у меня сомнений не было, а вот функциональная реализация вызывала подозрения.

let greedy_iter lst =
    let sorted_lst = List.sort compare lst in
    let groups = ref [] in
    let i = ref 0 in
    while !i < List.length sorted_lst do
        let first = List.nth sorted_lst !i in
        let group = ref [first] in
        i := !i + 1;
        while !i < List.length sorted_lst && compare 12 ((List.nth sorted_lst !i) - first) >= 0 do
            group := (List.nth sorted_lst !i) :: !group;
            i := !i +1;
        done;
        groups := !group :: !groups
    done;
    !groups

И код запуска теста

let test () =
    for i = 0 to 50 do
        let ages = make_test () in
        let g1 = greedy_iter ages in
        let g2 = find_groups ages in
        if compare_groups g1 g2 then
            print_endline "Ok"
        else begin
            print_endline "Error";
            print_endline "Ages: ";
            ages |> List.map string_of_int |> String.concat " " |> print_endline;
            print_endline "Imperative:";
            print_groups g1;
            print_endline "----";
            print_endline "Functional:";
            print_groups g2;
            print_endline "";
        end
    done


let () =
    test();

Работа обеих реализаций оказалась одинаковой.

Заключение

Писать код на OCaml становится всё проще. Эта реализация алгоритма наверняка содержит недостатки, которые можно убрать, но сейчас в этом нет смысла. Мне нужно нарабатывать практику работы с языком.

На будущее: нужно посмотреть, как принято тестировать код на OCaml.