Альманах конкурсов по функциональному программированию за 2012 год

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

Книга выпущена только в виде электронного издания и распространяется на безвозмездной основе (но всякий всегда может перечислить благодарность в пользу ФП(ФП), и я буду этому очень рад). Скачать её можно здесь ^[1]. Те, кто ещё не может отказаться от бумажных вариантов книг, всегда смогут воспользоваться технологией печати по требований (print on demand) и заказать себе экземпляр в малой типографии (о возникновении возможности для этого я сообщу дополнительно в официальном блоге ФП(ФП): haskell98.blogspot.ru ^[2]).

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

Конкурс № 6. Расшифровка кода на языке Haskell

В январе 2012 года всем желающим была предложена задача по расшифровке исходного файла на языке программирования Haskell. Файл был зашифрован циклическим применением к нему при помощи операции XOR некоего пароля. Собственно, пароль и необходимо было найти, чтобы расшифровать файл, после чего его необходимо было запустить, функция main выдала бы на экран некоторый семизначный код, который и надо было опубликовать в комментарии к конкурсу.

• Заметка для Хаброхабра по результатам конкурса: Расшифровка кода на языке Haskell (конкурс по ФП в январе 2012) ^[3].

Конкурс № 7. Мат в один ход

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

• Заметка для Хаброхабра по результатам конкурса: Шахматные задачи на мат в один ход: решение на языке Haskell ^[4].

Конкурс № 8. Переливание жидкости из сосуда в сосуд

В марте на конкурс была дана задача из разряда «математических бильярдов». Вот её формулировка: У Вас есть два сосуда, один объёмом 5 литров, а другой объёмом 8 литров. Вы можете наливать сосуды до края какой-то жидкостью (будьте осторожны, возможно, что она едкая или ядовитая) из крана. Вы можете выливать жидкость из сосуда в технологическую раковину. Вы можете переливать жидкость из сосуда в сосуд так, что либо в первом сосу-де закончится жидкость, либо второй наполнится до краёв (что произойдёт ранее). Ваша задача — отмерить 2 литра жидкости.

• Заметка для Хаброхабра по результатам конкурса: Измерение объёмов при помощи двух заданных сосудов: решение на языке Haskell ^[5].

Конкурс № 9. Кельтская алхимия — трансмутация слов

В апреле всем желающим участникам конкурсов по функциональному программированию была предложена задача по преобразованию слов друг в друга. Старинная детская игра — преобразование мухи в слова (и обратно). Другими словами, для заданной пары слов одинаковой длины необходимо найти цепочку преобразования, которая заключается в следующем. На каждом шаге можно поменять ровно одну букву (не добавить, не убрать, а именно по-менять — заменить одну букву другой) так, чтобы вновь получившееся слово входило в состав лексикона языка. Каждое вновь получаемое в цепочке трансмутаций слово должно быть в начальной форме. Если существует такая последовательность от начального слова к целевому, то трансмутация объявляется успешной. При этом, как полагается, такая цепочка должна быть кратчайшей — если на пути есть всякие циклы, то они не нужны.

• Заметка для Хаброхабра по результатам конкурса: Трансмутации слов друг в друга: решение на языке Haskell ^[6].

Конкурс № 10. Арифметические задачи для первого класса

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

• Заметка для Хаброхабра по результатам конкурса: Решение арифметических задач — вероятностный подход против регулярных выражений ^[7].

Конкурс № 11. Вычисление расстояния между точками

В качестве задачи на июнь всем добрым коллегам была дана задача, которая неоднократно встречалась на всяких олимпиадах по программированию. Однако в неё была внесена новый нюанс, который делал задачу намного сложнее. Вот условие: Демиург задумал поместить новую разумную расу на планету во Вселенной так, чтобы она как можно быстрее освоила весь доступный космос. Для этих целей он собрал перечень всех планет, находящихся в поясе Златовласки, после чего решил найти среди них две, наиболее близко расположенные друг к другу. Разумная раса должна быть расположена на одной из таких планет. Это, по замыслу Демиурга, позволит максимально быстро обеспечить освоение космоса. Помогите Демиургу найти две планеты, находящиеся на наименьшем расстоянии друг от друга.

• Заметка для Хаброхабра по результатам конкурса: Поиск кратчайшего расстояния между точками в трёхмерном пространстве ^[8].

Конкурс № 12. Управление лифтами

В июле задача была из области автоматического управления. Конечно, она всё также сводилась к поиску на графе, для чего всяко можно использовать алгоритм A*. Тем не менее, большинство участников выбрали реализацию ad hoc, в том числе и победитель. А соорганизатором конкурса выступил великолепный afiskon ^[9].

• Заметка для Хаброхабра по результатам конкурса: Управление лифтами: решение на языке Haskell ^[10].

Конкурс № 13. В своём ли уме Валет

Один коллега вызвал меня на спор о том, можно ли на функциональных языках решать логические задачи так же хорошо, как и на языках логического программирования, типа Prolog. Он предложил мне решить задачу из книги Р. М. Смаллиана «Алиса в стране смекалки», рассказав жуткую историю о том, что некто из его товарищей по работе не смогли оси-лить эту задачу на традиционных (императивных) языках: Тройка думает, что Туз не в своём уме. Четвёрка думает, что Тройка и Двойка обе не могут быть не в своём уме. Пятёрка думает, что Туз и Четвёрка либо оба не в своём уме, либо оба в своём уме. Шестёрка думает, что Туз и Двойка оба в своём уме. Семёрка думает, что Пятёрка не в своём уме. Валет думает, что Шестёрка и Семёрка обе не могут быть не в своём уме. В своём ли уме Валет?

• Заметка для Хаброхабра по результатам конкурса: Решение логических задач на языке Haskell: в своём ли уме Валет? ^[11].

Конкурс № 14. Расширение логических задач на большие пространства поиска

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

• Заметка для Хаброхабра по результатам конкурса: Поиск скрывающегося Доктора X среди пациентов — решение более сложных логических задач ^[12].

Конкурс № 15. Головоломка «Шарики и отверстия»

В октябре уважаемым участникам конкурсов была предложена задача на решение голово-ломки, опубликованной в брошюре № 16 коллекции «Занимательные головоломки» от компании DeAgostini. Итак, имеется шесть планок, в которых вырезаны сквозные отвер-стия и на которые наклеены шарики. Необходимо сложить эти планки в брусок по три план-ки в два уровня. Соответственно, шарик входит в дырку, плоская поверхность может быть прижата к плоской поверхности или к дырке. Остальные варианты сочленения планок не-возможны. Шарики могут торчать снизу и сверху бруска — тут ничего не возбраняется.

• Заметка для Хаброхабра по результатам конкурса: Шарики и дырки — один из вариантов плотной упаковки на языке Haskell ^[13].

Конкурс № 16. Раскраска карты

Ещё довольно давно с автором связался добрый соратник ФП(ФП) Алексей Кишкин и предложил на конкурс задачу по раскраске карты. Задача, казалось бы, банальная, однако при попытках реализации перед конкурсантом возникают различного рода трудности. И, как обычно, дьявол прячется в деталях. К тому же, очень хотелось посмотреть на различные варианты решения на разных языках программирования.

• Заметка для Хаброхабра по результатам конкурса: Раскрашиваем карту при помощи языка Haskell ^[14].

Конкурс № 17. Сборка кубика Рубика

Задача в декабре была просто на сборку кубика Рубика: У меня есть 4 кубика Рубика. Младший сын их достал и полностью перемешал все цвета на них, хотя изначально они были в полностью собранном состоянии. Это для меня печаль, поскольку я люблю порядок и полный орднунг. А алгоритмы сбора я как-то забыл, хотя дав-но и помнил. Но сегодня забыл. Посему прошу помощи у уважаемого сообщества — напи-шите мне программу, которая для заданного кубика Рубика даёт кратчаший алгоритм его перевода в целевое состояние, когда на каждой грани есть плашки только одного цвета.

• Заметка для Хаброхабра по результатам конкурса: Алгоритм A* и кубик Рубика: реализация на языке Haskell ^[15].

Дополнительные ссылки

Осталось привести только некоторые ссылки, чтобы любой заинтересовавшийся мог скачать себе описанный Альманах, а также дополнительные материалы, если кто-то заинтересуется. Вот некоторые мои книги для скачивания:

• Альманах «Конкурсы по функциональному программированию за 2012 год» ^[1] — данный том является вторым выпуском ежегодного Альманаха «Конкурсы по функциональному программированию», который составляется по результатам проводимых автором конкурсов в сети Интернет. Альманах структурирует и сводит воедино всю информацию, касающуюся конкурсных задач и их решений при помощи языка функционального программирования Haskell.
• Другие 14 эссе о языке Haskell и функциональном программировании — серьёзные ^[16] — в данном томе представлено новые 14 статей автора, которые в разное время были опубликованы в различных источниках — в научно-практическом журнале «Практика функционального программирования» (с дополнениями, которые не были включены в опубликованные статьи), на различных ресурсах в сети Интернет, на тематическом ресурсе Хаброхабр. Статьи сгруппированы в трёх частях — «мета», теоретическая и практическая части. В книге сделан упор на практические знания, предлагается решение некоторых прикладных задач при помощи языка функционального программирования Haskell.
• Альманах «Конкурсы по функциональному программированию за 2011 год» ^[17] — данный том является первым выпуском ежегодного Альманаха «Конкурсы по функциональному программированию», который составляется по результатам проводимых автором конкурсов в сети Интернет. Альманах структурирует и сводит воедино всю информацию, касающуюся конкурсных задач и их решений при помощи языка функционального программирования Haskell.
• Воспитание естественнонаучного мировоззрения у детей дошкольного и младшего школьного возраста. Том 1. Некоторые рекомендации родителям ^[18] — в книге предлагается описание личного опыта автора в деле воспитания у детей естественнонаучного мировоззрения, системного подхода к познанию окружающего мира и кибернетического метода исследования. По возможности книга написана простым языком, в ней приведены многочисленные примеры, методики и подходы. При этом книга не является педагогическим изданием, в ней всего лишь описывается авторское видение на проблемы воспитания детей. Книга будет интересна любому родителю, который хочет воспитать в своих детях тягу к науке и технологиям.
• 14 занимательных эссе о языке Haskell и функциональном программировании ^[19] — в книге представлено 14 статей автора, которые в разное время были опубликованы или подготовлены к публикации в научно-популярном журнале для школьников и учителей «Потенциал». Статьи расположены и связаны таким образом, чтобы они представляли собой логически последовательное повествование от начал к более сложным темам. Также в книге сделан упор на практические знания, предлагается решение многих прикладных задач при помощи языка функционального программирования Haskell.
• Методы получения, представления и обработки знаний с НЕ-факторами ^[20] — в монографии рассматриваются три последовательных процесса работы со знаниями — получение, представление и обработка, причём акцент сделан на так называемых НЕ-факторах, то есть факторах неопределённости, которые обычно присутствуют в знаниях экспертов. Приводится обзор современных методов, подходов и технологий извлечения, представления и обработки таких знаний, даётся богатый список специализированной литературы.

Все те, кто перечислит свою благодарность ^[21] в Фонд Поддержки Функционального Программирования ФП(ФП), смогут рассчитывать на персональный электронный экземпляр какой-либо моей книги (на выбор благодарного читателя) с моим автографом и дарственной надписью. Для этого после перечисления благодарности достаточно связаться со мной по электронной почте darkus.14@gmail.com ^[22] или прислать личное сообщение здесь.

Автор: Darkus

Источник ^[23]