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

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

Clash of code

2016-10-05 15:42
clash of code

Попробовал участвовать в коротких (5-15 минут) соревнованиях - Clash of code. Получилось довольно странно: при том, что многое мне не понравилось, я всё равно буду в них участвовать, по крайней мере, в этом месяце.

Задачи достаточно простые. Пока что не встретил задач, которые бы требовали большого времени на решение или просто серьёзного обдумывания. Впрочем, это ожидаемо, вряд ли можно решить что-то сложное за 5 минут.

В Clash of code три номинации: самое короткое решение (code golf), самый быстрый программист (кто быстрее накодит) и что-то связанное с определением условия задачи по примерам (мне не попадалось). В code golf нет ограничений или группировки по языкам, что сразу ставит участников в неравные условия, OCaml заметно проигрывает python (во всяком случае при моём текущем уровне знания OCaml это так, на python я бы смог писать более короткие решения). Скоростные решения мне пока тоже не по зубам - приходится долго вспоминать, как сделать ту или иную вещь.

Код, написанный в рамках Clash of code, очень страшен. Если с code golf, по-другому быть не может, то в соревнованиях на скорость по-другому я пока не умею, либо быстро, либо красиво.

Вот так у меня выглядит поиск суммы всех чисел от 0 до (n-1), которые делятся без остатка на 3 или 5 или 7:

Array.init(read_int())(fun i->if i mod 3=0||i mod 5=0||i mod 7=0 then i else 0)|>Array.fold_left(+)0|>print_int

Это не то решение, которое ушло на codingame, там были дополнительные пробелы и строка была чуть длиннее.

Тем временем, я получил 11 уровень за решение задач (не Clash of code, за них уровень не повышают).

Заработал OCaml Addict

2016-09-24 02:22
OCaml Addict

Решил очередную задачу и получил Legend-ачивку "OCaml Addict" (профиль) за то, что помог Марвину выйти из двигателя. Сделал скриншот ачивки, а котика нарисовал просто так.

Решение задач у меня сейчас проходит примерно так:

  • Добиться прохождения всех тестов. На этом этапе идёт в ход всё плохое, что есть в программирование: magic number, magic string, хардкод, копипаст - большая часть из-за того, что я плохо знаю OCaml.
  • Убрать явные косяки, копипаст, magic numbers. В целом, сделать так, чтобы код можно было читать и понять. На этом этапе код часто уменьшается в размерах.
  • Ввести типы данных, избавиться от строк и чисел в math ... with, сделать обработку ошибок и проверку на кривые данные. Хотя кривых данных в тестах не бывает, тут я уже делаю это просто для практики.

Тестирование OCaml-модулей при помощи Alcotest

2016-09-16 20:01
alcotest terminal

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

Из списка библиотек для тестирования взял первый по списку - Alcotest. Когда не знаешь ничего, лучший способ разобраться - попробовать.

Для разработки первого теста взял первую задачу из списка 99 problems на ocaml.org - "Write a function last : 'a list -> 'a option that returns the last element of a list".

# last [ "a" ; "b" ; "c" ; "d" ];;
- : string option = Some "d"
# last [];;
- : 'a option = None

Т.е. нужно написать функцию, которая возвращает последний элемент списка или None.

Решение задачи

Чтобы проверить в работе Alcotest, я сперва написал решение задачи. Хоть это и не по канонам TDD, в соответствии с которыми сперва пишут тест, но меня это устраивает.

Интерфейс last.mli

val last: 'a list -> 'a option

Реализация last.ml

let rec last = function
    | [] -> None
    | [elem] -> Some elem
    | hd :: tl -> last tl

Тест test.ml

open Last


let empty_list () =
  Alcotest.(check (option reject)) "Last from empty list" None (last [])


let one_elem () =
  Alcotest.(check (option int)) "Last from empty list" (Some 1) (last [1])


let last_int () =
  Alcotest.(check (option int)) "Last int" (Some 2) (last [1; 2])


let last_char () =
  Alcotest.(check (option char)) "Last char" (Some 'a') (last ['b'; 'c'; 'a'])


let last_string () =
  Alcotest.(check (option string)) "Last string" (Some "hi") (last ["bye"; "hi"])


let () =
  Alcotest.run "Test Last.last function which should return last element of a list" [
      "test_set", [
        "Get last from empty list", `Quick, empty_list;
        "Get the only element from list", `Quick, one_elem;
        "Get the int from list", `Quick, last_int;
        "Get the char from list", `Quick, last_char;
        "Get the string from list", `Quick, last_string;
      ]
  ]

Сборка

$ ocamlbuild -pkg alcotest test.byte
Finished, 7 targets (7 cached) in 00:00:00.

И результат в терминале

$ ./test.byte
Testing Test Last.last function which should return last element of a list.
[OK]                test_set          0   Get last from empty list.
[OK]                test_set          1   Get the only element from list.
[OK]                test_set          2   Get the int from list.
[OK]                test_set          3   Get the char from list.
[OK]                test_set          4   Get the string from list.
The full test results are available in `_tests`.
Test Successful in 0.002s. 5 tests run.

Все тесты пройдены, все танцуют.

Эмуляция ошибки

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

Сперва я поломал функцию last

let rec last = function
    | _ -> None

Потом пересобрал тест и запустил

$ ocamlbuild -pkg alcotest test.byte
Finished, 7 targets (4 cached) in 00:00:00.
$ ./test.byte
Testing Test Last.last function which should return last element of a list.
[OK]                test_set          0   Get last from empty list.
[ERROR]             test_set          1   Get the only element from list.
[ERROR]             test_set          2   Get the int from list.
[ERROR]             test_set          3   Get the char from list.
[ERROR]             test_set          4   Get the string from list.
The full test results are available in `_tests`.
4 errors! in 0.003s. 5 tests run.

Ну и славно, значит ошибки искать тоже умеет. А ещё он умеет раскрашивать вывод.

alcotest terminal 2

Заключение

Alcotest на текущий момент меня устраивает, поэтому сейчас буду тестировать свой код при помощи этой библиотеки. Для моих скромных потребностей её хватает.

Рефакторинг битвы против Skynet

2016-08-31 19:47
skynet

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

Моя стратегия обороны была основана на том, что одна вершина не может быть напрямую связана более чем с одним шлюзом. Значит можно просто обрубать связи бот-шлюз, если такие есть, в противном случае выключать любую связь бот-вершина.

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

Первое решение

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

let read_network_config () =
    let init_data = read_line () in
    Scanf.sscanf init_data "%d %d %d" (fun n l e -> (n, l, e))


let create_disconnected_network nodes_number =
    Array.make_matrix nodes_number nodes_number 0


let connect_nodes network edges_number =
    for i = 0 to edges_number - 1 do
        let edge = read_line () in
        let n1, n2 = Scanf.sscanf edge "%d %d" (fun n1 n2 -> (n1, n2)) in
        network.(n1).(n2) <- 1;
        network.(n2).(n1) <- 1;
    done


let read_gateways gateway_number =
     Array.init gateway_number (fun i -> read_int ())


let search_nodes_to_disconnect network gateways skynet_agent_position =
    let to_destroy = Array.map (fun i -> if network.(i).(skynet_agent_position) = 1 then (Some i, Some skynet_agent_position) else (None, None)) gateways in
    let e = Array.fold_left (fun a b ->
        match a, b with
        | (None, None), (None, None) -> (None, None)
        | (Some x, Some y), (None, None) | (None, None), (Some x, Some y) -> (Some x, Some y)
    ) (None, None) to_destroy in

    let rec find_edge e =
        if e < Array.length network then
            if network.(skynet_agent_position).(e) = 1 then
                (
                    network.(skynet_agent_position).(e) <- 0;
                    network.(e).(skynet_agent_position) <- 0;
                    e
            )
            else find_edge (e + 1)
        else
            0
    in

    match e with
    | (None, None) -> (skynet_agent_position, find_edge 0)
    | (Some x, Some y) -> (
        network.(x).(y) <- 0;
        network.(y).(x) <- 0;
        (x, y)
    )


let disconnect_nodes (a, b) =
    Printf.printf "%d %d\n" a b


let () =
    let nodes_number, edges_number, gateway_number = read_network_config () in

    let network = create_disconnected_network nodes_number in
    connect_nodes network edges_number;

    let gateways = read_gateways gateway_number in

    while true do
        read_int () |> search_nodes_to_disconnect network gateways |> disconnect_nodes
    done

Рефакторинг

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

После рефакторинга

module Net = struct
    let connect network a b =
        network.(a).(b) <- 1;
        network.(b).(a) <- 1;
        ()

    let disconnect network a b =
        network.(a).(b) <- 0;
        network.(b).(a) <- 0;
        ()

    let has_direct_connection network a b =
        network.(a).(b) = 1

    let find_any_connected_node network node_number =
        let rec find num =
            if num < Array.length network then
                if network.(node_number).(num) = 1 then
                    num
                else
                    find (num + 1)
            else
                node_number
        in

        find 0

    let build nodes_number edges =
        let network = Array.make_matrix nodes_number nodes_number 0 in
        List.iter (fun (a, b) -> connect network a b) edges;
        network
end


let read_network_config () =
    let open Scanf in

    let nodes_number, edges_number, gateway_number =
        let init_data = read_line () in
        sscanf init_data "%d %d %d" (fun n l e -> (n, l, e))
    in

    let rec read_edges = function
        | 0 -> []
        | num -> sscanf (read_line ()) "%d %d" (fun a b -> (a, b)) :: read_edges (num - 1)
    in

    let edges = read_edges edges_number in

    let gateways =
        Array.init gateway_number (fun i -> read_int ()) |> Array.to_list
    in

    nodes_number, edges, gateways


let fight_with_skynet network gateways =
    let destroy_edge a b =
        Net.disconnect network a b;
        Printf.printf "%d %d\n" a b
    in

    let rec stop_skynet_agent () =
        let skynet_agent_position = read_int () in
        let agent_to_gateway_edges =
            List.filter (fun gateway ->
                Net.has_direct_connection network skynet_agent_position gateway)
            gateways
        in
        let connected_node = match agent_to_gateway_edges with
        | [] -> Net.find_any_connected_node network skynet_agent_position
        | connected_gateway :: tl -> connected_gateway
        in
        destroy_edge skynet_agent_position connected_node;

        stop_skynet_agent ()
    in

    stop_skynet_agent ()


let () =
    let nodes_number, edges, gateways = read_network_config () in
    let network = Net.build nodes_number edges in
    fight_with_skynet network gateways

Заключение

В итоге у меня получилось решение, которое и задачу решало, и меня устраивало (во всяком случае, с текущем уровнем знаний в OCaml).

Недостаток решения задач на соревнованиях - нужен только результат, а не поддерживаемый код. Довольно сложно убедить себя в необходимости дорабатывать код, если все тесты пройдены, а возвращаться к коду вряд ли понадобится.

Получил 7 уровень на codingame

2016-08-26 01:50
level up

Решил задачу на поиск ближайшего к пользователю дефибрилятора и получил 7 уровень (профиль). Почему для меня это событие:

  • все задачи были решены на OCaml;
  • последнюю задачу решил за 15 минут, а не за 3 часа;
  • при решении пользовался только документацией, а не усиленным гуглением, что и как работает.

Ещё узнал, как можно считывать из буфера или строки пустые строки между разделителями (например, если разделитель точка с запятой - %[^;];).

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