Разработка на коленке

"тут должна быть красивая цитата о программировании"

30 Days of Code

2016-12-14 18:26
30 days of code on hackerrank

Прошёл обучалку на hackerrank.com - 30 Days of Code. В течение 30 дней мне ежедневно нужно было решать какую-нибудь простую задачу. На самом деле простую, ничего сложного делать не приходилось. Моей целью было знакомство с платформой, точнее, насколько хорошо там работает OCaml. Оказалось, что очень хорошо. Там подключена Core и Str, чего сильно не хватает на codingame. Но не все задачи можно было решить на OCaml, потому что часть задач заключалась в реализации небольшого куска кода, который должен работать внутри предоставленного шаблона (шаблон редактировать нельзя). В итоге статистика такая:

  • 18 задач на OCaml.
  • 2 задачи на Java (пришлось вспомнить).
  • 10 задач решил на Python.

Из интересного запомнилось: регулярные выражения и реализация break через iter+raise (при решении задачи о 8 ферзях я использовал циклы).

Регулярные выражения

open Core.Std
open Str


let input () =
    let n = read_int () in
    List.init n (fun _ -> read_line ()) |> List.sort ~cmp:compare


let () =
    let pattern = Str.regexp "\\([a-z]+\\) [a-z.]+@gmail.com$" in
    input () |> List.iter ~f:(fun line ->
        if Str.string_match pattern line 0 then
            print_endline (Str.matched_group 1 line)
    )

List.iter + raise == break

open Core.Std


exception Not_prime


let is_prime num =
    try
        if num > 1 then (
            List.range 2 ((Int.of_float(sqrt (float num))) + 1)
            |> List.iter ~f:(fun i -> if num mod i = 0 then raise Not_prime);
            true
        )
        else raise Not_prime
    with Not_prime -> false

Заключение

Мне понравилось заниматься на hackerrank, но целиком уходить на эту площадку не буду. Пока буду заниматься и тут, и на codingame. Большой плюс hackerrank - наличие огромного количества простых задач, не только в рамках 30 days of code. По Python и функциональному программированию задач хватит на полгода вперёд. Мне этого достаточно, чтобы поддерживать себя в форме.

Решение задачи о 8 ферзях генетическим алгоритмом на OCaml

2016-12-09 22:26
genetic-algorithm

В этот раз взялся за реализацию генетического алгоритма на OCaml для решения задачи о 8 ферзях (не то, чтобы мне эта задача очень уж нравилась, но это пока тот уровень сложности, с которым я могу справиться без больших временных затрат).

Сам алгоритм довольно прост в реализации и больших вопросов не вызывает. По сути, мне нужно было разработать небольшой набор функций:

  • mutate, чтобы проводить небольшие мутации;
  • reproduce, чтобы создавать новые популяции на основе старых;
  • test, чтобы проверять, есть ли в популяции решение задачи;
  • find, чтобы запустить поиск решения.

Этого небольшого набора вполне достаточно, чтобы запустить поиск. Однако для меня интерес представляла не только разработка такого алгоритма, но и хотелось самому проверить эффективность некоторых эвристик при выборе родителей для следующей популяции, а заодно сделать что-то новое в OCaml. Из OCaml я выбрал модули, хоть я и применял их раньше, но в привычку не вошло (решение небольших задач на codingame не требует разработки своих модулей, а до больших задач ещё не дошёл). В качестве подопытных эвристик выступили стратегии:

  • брать всех подряд, никого не выкидывать;
  • выбрать одного лучшего (по сути, тут надежда только на мутации);
  • выбирать двух лучших, остальных выбрасывать.

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

module GA = struct
end

Популяция представляет собой список из 4 списков, в каждом по 8 чисел:

module GA = struct
   let create_population () =
      List.init 4 (fun _ -> List.init 8 (fun _ -> Random.int 8))
end

Для проверки состояния доски использовал количество пар ферзей, которые не атакуют друг друга. Для 8 ферзей такое число равно 28, если никто не находится под ударом. На этом факте основаны две функции, одна для оценки близости состояния к решению, а вторая, является ли состояние решением (количество неатакующих пар == 28).

let evaluate population =
    let under_attack (l1, c1) (l2, c2) =
        c1 = c2 || (abs (l1 - l2)) = (abs (c1 - c2))
    in

    let rec foldi i accum = function
        | [] -> assert false
        | [x] -> accum
        | x :: xs -> foldi (i + 1) (List.foldi xs ~init:accum ~f:(fun i' accum x' ->
                accum + if under_attack (i, x) ((i' + i + 1), x') then 0 else 1)) xs
    in

    foldi 0 0 population

let is_safe population =
    (* This is only for 8 cells on board,
    * for other sizes max_value should be ((1 + n) / 2 * n). *)

    let max_value = 28 in
    evaluate population = max_value

Мутация и создание потомков простое и понятное.

let mutate population =
    let n = Random.int (List.length population) in
    List.mapi population ~f:(fun i x -> if i = n then (Random.int 8) else x)

let reproduce population1 population2 =
    let n = Random.int (List.length population1) in

    let (left, _) = List.split_n population1 n in
    let (_, right) = List.split_n population2 n in

    left @ right

Далее идёт функция поиска решения. Она содержит в себе подсчёт количества шагов, а также возможность принимать функцию, которая будет фильтровать популяцию перед выбором родителей. Если такая функция не предоставлена, то для создания потомков будет использована вся популяция.

let find ?choose_parents population =
    let choose_parents = match choose_parents with
        | None -> (fun x -> x)
        | Some x -> x
    in

    let nextgen population =
        let population_size = List.length population in

        let population' = choose_parents population in

        let len = List.length population' in

        let rec aux i =
            if i > 0 then (
                let n = Random.int len in
                let a = List.nth_exn population' n in
                let b = List.nth_exn population' n in
                let child = reproduce a b in
                if Random.int 10 < 3 then
                    mutate child :: aux (i - 1)
                else
                    child :: aux (i - 1)
            )
            else
                []
        in
        aux population_size
    in

    let steps_number = ref 0 in

    let rec find_solution population =
        steps_number := !steps_number + 1;

        if List.exists population ~f:is_safe then
            List.filter population ~f:is_safe |> List.hd_exn
        else
            nextgen population |> find_solution
    in

    let solution = find_solution population in

    (solution, !steps_number)

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

let () =
    Random.init 10; (* Always init by the same number for testibility. *)
    let population = GA.create_population () in
    List.iter population ~f:(fun i -> printf "%s --> evaluate = %d\n" (GA.to_string i) (GA.evaluate i));
    printf "\n";

    let cmp a b = -(compare (GA.evaluate a) (GA.evaluate b)) in

    let choose_better_two population =
        match List.sort population ~cmp with
        | a :: b :: _ -> [a; b]
        | _ -> assert false
    in

    let choose_better_one population =
        [List.sort population ~cmp |> List.hd_exn]
    in

    let choices = [
        None, "all";
        Some (choose_better_one), "only better one";
        Some (choose_better_two), "get best two"
        ]
    in

    let inits = [1; 10; 100; 42] in

    List.iter inits ~f:(fun init ->
        printf "Init by: %d\n" init;
        List.iter choices ~f:(fun (choose_parents, name) ->
            Random.init init; (* Always init by the same number for testibility. *)

            let solution, steps_number = match choose_parents with
            | None -> GA.find population
            | Some choose_parents -> GA.find ~choose_parents population
            in

            printf "%s -- Solved by <%s> in %d steps.\n" (GA.to_string solution) name steps_number
        );
        printf "\n";
    )

Результат

0 4 1 5 2 7 1 1 --> evaluate = 23
7 7 7 6 6 0 2 2 --> evaluate = 18
7 2 2 1 7 2 0 4 --> evaluate = 20
6 3 5 6 3 2 0 0 --> evaluate = 17

Init by: 1
7 1 4 2 0 6 3 5 -- Solved by <all> in 36126 steps.
5 3 6 0 7 1 4 2 -- Solved by <only better one> in 1180 steps.
2 4 1 7 5 3 6 0 -- Solved by <get best two> in 505 steps.

Init by: 10
6 4 2 0 5 7 1 3 -- Solved by <all> in 48993 steps.
1 4 6 0 2 7 5 3 -- Solved by <only better one> in 57 steps.
0 4 7 5 2 6 1 3 -- Solved by <get best two> in 199 steps.

Init by: 100
4 0 7 3 1 6 2 5 -- Solved by <all> in 27041 steps.
4 7 3 0 2 5 1 6 -- Solved by <only better one> in 527 steps.
0 4 7 5 2 6 1 3 -- Solved by <get best two> in 185 steps.

Init by: 42
2 5 3 0 7 4 6 1 -- Solved by <all> in 2339 steps.
3 5 7 1 6 0 2 4 -- Solved by <only better one> in 2834 steps.
4 6 0 3 1 7 5 2 -- Solved by <get best two> in 1353 steps.

Заключение

Из результатов работы алгоритма видно, что при выборе лучших представителей популяции можно быстрее найти решение. Для сравнения стратегий <only better one> и <get best two> слишком мало данных. Возможно для каждой из этих стратегий нужно подбирать более подходящие вероятности мутаций. В данный момент оставлю вопрос открытым.

Ну и ссылка на сам репозиторий - ocaml-genetic-algorithm

8 Queens puzzle на OCaml методом минимальных конфликтов

2016-12-06 23:14
8 queens puzzle

Сделал небольшой перерыв в своих занятиях на codingame, чтобы больше уделить внимания "зелёной книге" (Искусственный интеллект. Питер Норвиг). В теме про локальный поиск мне очень понравилась эвристика с минимальными конфликтами, и я решил написать её реализацию для задачи о 8 ферзях (на самом деле для произвольного количества ферзей, но об этом ниже).

Сначала я сделал версию с кучей хардкода, большим количеством кусков закоментированного кода, неудачной реализацией вложенных циклов через рекурсию - [1]. Эта версия почти всегда работала. Почти, потому что она не обрабатывала граничные условия в виде пустой доски или доски с 1 и 2 ферзями. Но это меня не смущало, потому что это было проблемой реализации обхода данных, что на OCaml у меня порой вызывает затруднения.

В таком виде, помимо очевидных проблем, меня не устраивало то, что количество конфликтов считается каждый раз для всех ферзей, поэтому я задумал реализацию, в которой матрица конфликтов должна храниться постоянно, а пересчитываться только для изменившихся данных (и даже несмотря на это, программа долго работает уже с 500 ферзями).

Потом было несколько неудачных попыток реализовать задуманное, но в итоге у меня получилось решение, которое на данный момент меня почти устраивает. Почти, потому что хочется наглядную визуализацию шахматной доски, пусть и в терминале, а ещё неплохо бы прикрутить выгрузку в JSON всех шагов поиска решения с последующей визуализацией в браузере. Но это пока только в планах.

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

let under_attack board i1 i2 =
    board.(i1) = board.(i2) || (abs (i1 - i2)) = (abs (board.(i1) - board.(i2)))


let allsafe board =
    let under_attack = under_attack board in

    let last_index = (Array.length board) - 1 in
    try
        for i1 = 0 to (last_index - 1) do
            for i2 = i1 + 1 to last_index do
                if under_attack i1 i2 then raise Wrong
            done
        done;
        true
    with Wrong -> false

Репозиторий ocaml-8queens

Новый Level up на codingame, теперь 13

2016-11-21 21:23
13

На днях получил 13 уровень, практически вскарабкался на очередную высоту (как енот на рисунке). Из решённых задач - 100% в Easy, и одна нерешённая в Medium (про марсоход). Марсоход пока делать не буду, переключусь на задачи связанные с поиском в Hard. Только сперва сделаю паузу. Во-первых, хочу разобраться с некоторыми алгоритмами поиска. А во-вторых, нужно снова садиться за книги по OCaml.

Чтобы решать задачи на codingame мне вполне хватает простых функций и базовых типов, иногда мне понадобилось определять свои типы (варианты и записи), но на этом всё. Т.е. будь у меня в руках Python, то я бы мог ограничиться def, а структуры данных создавать на основе tuple и dict. Но я начал решать задачи на codingame не только для тренировки в решении алгоритмических задач, а ещё и для изучения OCaml. Поэтому сейчас мне нужно разобраться с модулями, классами, объектами и функторами, прежде чем я начну писать код. Вполне возможно, что использование этих вещей для решения задач будет большим переусложнением, но меня это устроит.

К сожалению, на OCaml там пишет совсем немного людей, из-за этого нет возможности учиться на примерах. Всё чаще в списке решений на OCaml встречается вот такая картинка.

alone

Ещё я зарегистрировался на hackerrank.com, где сейчас прохожу их "30 day of code". В отличии от codingame, там есть возможность использовать Core. На самом деле, именно это меня в нём привлекло.

How to split string in OCaml by delimiter

2016-11-15 21:54
How to split string in OCaml by delimiter

Из-за того, что на codingame доступна только стандартная библиотека OCaml, да и то не вся, приходится писать свои мелкие функции. С каждой итерацией функции всё больше похожи на что-то пригодное для продакшена.

В этот раз я снова написал функцию для разбиения строки на подстроки.

let split str ~on:delim =
    let open String in

    let rec _split acc str =
        try
            let pos = index str delim in
            _split ((sub str 0 pos) :: acc) (sub str (pos + 1) ((length str) - pos - 1))
        with Not_found -> str :: acc
    in

   _split [] str |> List.filter (fun s -> s <> "") |> List.rev

let () =
    "This is a long message with two spaces after next word  and still there is shouldn't be an empty string in a list "
    |> split ~on:' '
    |> String.concat "\n"
    |> print_endline

Отсутствие библиотек всё чаще заставляет задуматься о переходе на hackerrank, где есть Core. Если писать решения для обычных задач ещё можно, то участвовать в соревнованиях может быть сложно. А с другой стороны так я получаю больше практики и лучше понимаю, как работает OCaml.