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

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

Рефакторинг битвы против 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 часа;
  • при решении пользовался только документацией, а не усиленным гуглением, что и как работает.

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

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

Умножение матриц на OCaml (с модулями)

2016-08-19 01:53

У меня новое развлечение - курс Нейронные сети. Сейчас у меня ликбез по линейной алгебре, а конкретно - умножение матриц. В одном уроке нужно было перемножить матрицы, что мне показалось неплохой возможностью написать кусок кода на OCaml.

Задача

Перемножить матрицы

    [1 0 0 0]   [1  2  3]   [3 0 0]
2 * [0 1 0 0] * [5  6  7] * [0 3 0] =
    [0 0 1 0]   [9 10 11]   [0 0 3]
    [0 0 0 1]   [4  8 12]

Решение

В этот раз мне хотелось сделать отдельный модуль с сигнатурой и без конкретных типов в сигнатурах.

matrix.mli

open Core.Std

type t

val of_list: int list list -> t

val of_array: int array array -> t

val mult_to_matrix: t -> t -> t

val mult_to_int: t -> int -> t

val to_string: t -> string

matrix.ml

open Core.Std


type t = int array array


let of_array a =
    Array.map a ~f: Array.copy


let of_list lst =
    List.to_array (List.map lst ~f: List.to_array)


let mult_to_matrix m1 m2 =
    let dimx = Array.length m1 in
    let dimy = Array.length m2.(0) in

    let vector_length = Array.length m2 in
    let mult_lines line_number column_number =
        List.range 0 vector_length
        |> List.map ~f:(fun k -> m1.(line_number).(k) * m2.(k).(column_number))
        |> List.reduce ~f:(+)
        |> Option.value ~default:0
    in

    let product = Array.make_matrix ~dimx ~dimy 0 in
    for i = 0 to dimx - 1 do
        for j = 0 to dimy - 1 do
            product.(i).(j) <- mult_lines i j
        done;
    done;

    product


let mult_to_int matrix multiplier =
    matrix |> Array.map ~f:(fun line -> Array.map line ~f:(fun i -> i * multiplier))


let to_string matrix =
    Array.map matrix ~f:(fun line ->
        Array.map line ~f:Int.to_string |> String.concat_array ~sep:", "
    ) |> String.concat_array ~sep: "; "

product.ml

open Core.Std


let () =
    let a = Matrix.of_array [|
        [|1; 0; 0; 0|];
        [|0; 1; 0; 0|];
        [|0; 0; 1; 0|];
        [|0; 0; 0; 1|];
    |] in
    let b = Matrix.of_list [
        [1; 2;  3];
        [5; 6;  7];
        [9; 10; 11];
        [4; 8;  12]
    ] in
    let c = Matrix.of_list [
        [3; 0; 0];
        [0; 3; 0];
        [0; 0; 3];
    ] in

    Matrix.mult_to_int (Matrix.mult_to_matrix (Matrix.mult_to_matrix a b) c) 2
    |> Matrix.to_string
    |> printf "%s\n"

Заключение

Результат прошёл проверку задания, хотя решить задачу вручную на листе бумаги было бы гораздо быстрее, потому что достаточно было из третьей матрицы сделать единичную, а потом умножить матрицу b на 6. Но сейчас мне важно практиковаться в разработке на OCaml.

Записи процесса разработки в этот раз не будет, во-первых, разработка была не в один присест, а во-вторых, ничего интересного там нет.

Быстрая сортировка (quicksort) на OCaml

2016-08-08 18:02

Дошёл черёд до реализации быстрой сортировки на OCaml, пока я слушаю курс по алгоритмам (Algorithmic Toolbox). Поскольку основная цель - практика программирования на OCaml, то этот раз я не стал заниматься разработкой partion с ручным перемещением элементов списка, а заменил её двумя вызовами List.filter. Код для тестирования взял из сортировки слиянием, а функцию генерации тестовых данных сделал как в сортировке подсчётом, чтобы в список входили отрицательные числа.

Исходный код:

open Core.Std


let rec quicksort lst =
    let open List in
    match lst with
    | [] | [_] -> lst
    | hd :: tl ->
            let left = quicksort (filter tl (fun i -> i <= hd)) in
            let right = quicksort (filter tl (fun i -> i > hd)) in
            concat [left; [hd]; right]


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 100) - 50 :: create_test_data (size - 1)


let render color text =
    sprintf "\027[38;5;%dm%s\027[0m\n" color text


let render_success data qs_sorted sorted =
    let color = 2 in
    let message = "Ok" in
    if List.length data < 20 then
        [
            message;
            "Data: " ^ (List.to_string data ~f:string_of_int);
            "Quicksort: " ^ (List.to_string qs_sorted ~f:string_of_int);
            "List sort: " ^ (List.to_string sorted ~f:string_of_int);
        ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""
    else
        render color (message ^ " size: " ^ (string_of_int (List.length data)))


let render_error data qs_sorted sorted =
    let color = 1 in
    let message = "Error"in
    [
        message;
        "Data: " ^ (List.to_string data ~f:string_of_int);
        "Quicksort: " ^ (List.to_string qs_sorted ~f:string_of_int);
        "List sort: " ^ (List.to_string sorted ~f:string_of_int);
    ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""



let rec test size =
    let data = create_test_data size in
    let qs_sorted = quicksort data in
    let sorted = List.sort data ~cmp:compare in
    match compare sorted qs_sorted with
    | 0 -> (
        printf "%s%!" (render_success data qs_sorted sorted);
        if size > 0 then
            test (size - 1)
    )
    | _ -> printf "%s%!" (render_error data qs_sorted sorted)


let () =
    printf "Let's begin\n";
    test 1000

Quicksort3

Ещё сделал quicksort3, где список разбивается на три части. С практической точки зрения этот код скорее бесполезен, но для тренировки разработки на OCaml подойдёт.

open Core.Std


let rec quicksort3 lst =
    let open List in
    match lst with
    | [] | [_] -> lst
    | hd :: _ ->
        match map [(<); (=); (>)] (fun f -> filter lst (fun i -> f i hd)) with
        | [l; c; r] -> concat [quicksort3 l; c; quicksort3 r]
        | _ -> assert false

Сортировка подсчётом на OCaml и на Python 3

2016-08-04 22:20

Сортировку подсчётом решил сделать и на Python и на OCaml. Просто было интересно, записать процесс работы и посмотреть потом со стороны.

Python

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

В записи между 3:36 и 5:36 пауза, мне нужно было отойти от комьютера, поэтому там экран статичен.

А ещё заметил, что из-за того, что пишу этот код сразу на двух языках, то немного путаюсь. Например, попытался вставить в питоновском коде else if, вместо elif.

Полный исходник:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


import random


def counting_sort(data, min_number, max_number):
    n = max_number - min_number + 1  # [0, n]
    counters = [0] * n

    for v in data:
        counters[v - min_number] += 1

    result = []
    for v, count in enumerate(counters):
        result.extend([v + min_number] * count)

    return result


def create_test_data(size):
    min_number = random.randint(-10, 10)
    max_number = random.randint(min_number + 1, 15)
    data = [random.randint(min_number, max_number) for _ in range(size)]
    return data, min_number, max_number


def main():
    for size in range(10):
        data, min_number, max_number = create_test_data(size)
        sorted_by_counting_sort = counting_sort(data, min_number, max_number)
        sorted_by_sorted = sorted(data)
        if sorted_by_counting_sort != sorted_by_sorted:
            print('Error!')
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print('Sorted:        {}'.format(sorted_by_sorted))
            break
        elif size < 15:
            print('Ok for size {}'.format(size))
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print()
    else:
        print('Ok!')


if __name__ == '__main__':
    main()

OCaml

Потом была очередь разработки алгоритма на OCaml. Здесь я решил, что не честно ждать от фукнции генерации тестовых данных, чтобы она возвращала минимальный и максимальный элементы. Поэтому поиск этих элементов вынес в саму функцию сортировки подсчётом. Таким образом должно было получиться O(3*n), то есть O(n).

Попытка записать и загрузить процесс разработки закончилась ошибкой:

~ Upload failed: Sorry, your asciicast is too big.
~ Retry later by running: asciinema upload ./tmp9e2k0bwd-asciinema.json

Поэтому просто исходник:

open Core.Std


let counting_sort = function
    | [] -> []
    | data -> (
        let min_elt = match List.min_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let max_elt = match List.max_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let n = max_elt - min_elt + 1 in
        let counters = Array.create n 0 in

        let rec count = function
        | [] -> ()
        | h :: tl -> (
            counters.(h - min_elt) <- (counters.(h - min_elt) + 1);
            count tl;
        )
        in

        count data;

        Array.foldi counters ~init:[] ~f:(fun i accum v -> accum @ Array.to_list (Array.create v (i + min_elt)))
    )


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 10) - 5 :: create_test_data (size - 1)


let () =
    for i = 0 to 10 do
        let data = create_test_data i in
        let sorted_by_count = counting_sort data in
        let sorted_by_std = List.sort data ~cmp:compare in
        if sorted_by_count <> sorted_by_std then
            (
                printf "Error\n";
                data |> List.to_string ~f:string_of_int |> printf "Data: %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std: %s\n\n";
            )
        else
            (
                printf "Ok\n";
                data |> List.to_string ~f:string_of_int |> printf "Data:  %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std:   %s\n\n";
            )
    done

Заключение

Программировать на OCaml мне по-прежнему сложно. Жаль, что запись не сохранилась. Её большой размер обусловлен постоянными переключенями между vim и utop, где я смотрел сигнатуры функций и писал простой тестовый код.

Ещё я понял, что тестирующий код лучше помещять в рекурсивную функцию (с хвостовой рекурсией), если нужно прерывать тест после нахождения ошибки, так как в OCaml нет break, чтобы прервать выполнение цикла.