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

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

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.

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, сделать обработку ошибок и проверку на кривые данные. Хотя кривых данных в тестах не бывает, тут я уже делаю это просто для практики.