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

Задача 391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1: rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]]
Return true. All 5 rectangles together form an exact cover of a rectangular region.
…
Example 3:rectangles =
[ [1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]]
Return false. Because there is a gap in the top center.

У того, кто в детстве не писал на Прологе — нет сердца, а у того, кто пишет на нём сегодня — нет мозгов. (оригинал)

Если вас всегда терзали мучительные сомнения — что за фигня это Логическое Программирование (ЛП) и вообще зачем оно нужно? То это статья для вас.

Можно по-разному разделить языки программирования на группы (часто их называют парадигмами программирования), например, вот так:

• структурное: программа разбивается на блоки — подпрограммы (изолированные друг от друга), а основными элементами управления являются последовательность команд, ветвление и цикл.
• объектно-ориентированное: задача моделируется в виде объектов, которые отправляют друг другу сообщения. Объекты обладают свойствами и методами. Абстракция. Инкапсуляция. Полиморфизм. Ну в общем, все в курсе.
• функциональное: базовым элементом является функция и сама задача моделируется в виде функции, а, точнее, чаще всего в виде их композиции, если f(.) и g(.) — это функции, то f(g(.)) — это их композиция.
• логическое: вот тут, как правило, начинается феерия — если про первые три написаны сотни статей, книг, обзоров, презентаций и учебников, то здесь мы в лучшем случае видим что-то про Prolog и разработки времён Pink Floyd и Procol Harum (ну хоть с музыкой им тогда повезло) и на этом история заканчивается.

Вот эту оплошность я и собираюсь сегодня исправить.

Важнейший тезис этой статьи:

Логическое программирование != Prolog.

И вообще последний вам скорее всего не нужен. А вот первое вполне может быть.

Структура статьи:

• Что такое Пролог и почему он вам скорее всего не нужен
• Зачем оно надо, или краткое введение в Answer Set Programming
• Решаем задачи на ASP
• Комбинаторная оптимизация
• Вероятностное ЛП: ProbLog
• ЛП на классической логике FO(.) и IDP
• Sketched Answer Set Programming
• Экспериментальный анализ
• Тестирование и корректность программ
• Заключение

Вступление

Как то мне посчастливилось выбирать тему дипломной работы по специальности программная инженерия, и я выбрал написание экспертной системы, причем именно на языке Пролог. Хоть в промышленном программировании он почти не используется, он интересен в теоретическом плане позволяет самым быстрым способом прикоснуться к интеллектуальным системам(ИС). Также сам язык интересен в спортивном плане, так как заставляет мыслить в непривычной манере, отличной от мышления процедурного программирования и ООП, что является хорошой тренировкой для мозгов.

Использовалась реализация Prolog — Visual Prolog, с встроенными библиотеками GUI. Но если
вы хотите написать GUI на Qt/C++, то в документации есть инструкция, как импортировать программу в DLL, и скомпилировать ее вместе с C/C++ проектом. Отсюда следует, что совместить можно и с другими языками.

Вообще когда я работал над этим проектом, я не нашел примеров достаточно не примитивных, но в то же время и не настолько больших, как наворочен

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

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

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

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

Так вот, задача такова:

1. Trapping Rain Water II
   Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
   Note:
   Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
   Example:
   
   
   
   Given the following 3x6 height map:
   [
   [1,4,3,1,3,2],
   [3,2,1,3,2,4],
   [2,3,3,2,3,1]
   ]
   Return 4.

Каждое воскресенье в нашей компании принято устраивать весёлые викторины, это одна из них.

Загадка

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

• Для начала, представим подозреваемых. Есть три мужчины (Джордж, Джон, Роберт) и три женщины (Барбара, Кристина, Иоланда). Каждый человек находится в отдельной комнате (ванная, столовая, кухня, гостиная, кладовая, кабинет). В каждой комнате найдено подозрительное оружие (сумка, огнестрельное оружие, газ, нож, яд, верёвка). Вопрос: кого нашли на кухне?
• Подсказка 1. При мужчине на кухне нет ни верёвки, ни ножа, ни сумки. Оружие не является огнестрельным. Вопрос: какое оружие найдено на кухне?

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

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

Это представление, о том, что я хорошо отношусь к декларативному способу выражения мыслей, а выражать все последовательностью команд и переходов между ними, мне кажется архаичным и устаревшим, ведь так делали наши деды, деды соединяли проводками контакты на коммутационной панели и получали мигание лампочек, а у нас монитор и распознавание голоса, как находясь на таком уровне эволюции можно все еще задумываться, о следовании команд… Мне кажется, если выражать программу логическим языком, она будет выглядеть понятнее, и это можно произвести в технологию, на это была сделана ставка еще в 80-х.

Что же, введение затянулось....

Путешественники, привет.

Если вы это читаете предлагаю продолжение того "занимательного" материала, который я писал перед этим. Если вы немного проследили за мыслью, которая изветвилась в три статьи, а основной то посыл — был, только в том, чтобы показать интерес к декларативному подходу. Он почему то не велик, как будто эСКюэЛ не стал общедоступным и обязательным, ведь без него невозможно подумать, а как можно обработать данные иначе. Правда, ведь лучше сформулировать задачу и не заботиться о том, во что это воплощается.

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

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

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

Хватит вызывать заинтересованность, начинаю...

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

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

Я написал реализацию которая в среднем была вот такого вида скорости, значит есть еще 90 процентов решений, которых я не заметил, что кто-то знает как ее решить еще быстрее и он молчит, и посмотрев две предыдущие статьи не сказал: ах, если это вопрос производительности, тогда все понятно — тут пролог не подходит. Но с производительностью сейчас все нормально, представить себе программу, которая будет запущена на слабом железе не возможно, "в конце концов, зачем об этом думать?"

Вызов

Решить задачу еще быстрее, там был питон и было время, и есть на питоне более быстрое решение?

Мне сообщают "Runtime: 2504 ms, faster than 1.55% of Python3 online submissions for Wildcard Matching."

Привет, сообщество разработчиков, надо довести дело до конца.

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

Попробую продолжить выпендриваться демонстрировать.

Коротко напомню задачу:

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

Хардкорно я получил от него 66 и проверил свое решение — пока все работало. Но не может быть все так просто.

Зачем было делать так много тестов, хочу проверить дальше...

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

Итак, выбираю Питон.

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

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

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

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

1. Итак

Тут выбираем ближайшее к самым сложным задание, и пытаемся его решить на Prolog, необходимо продемонстрировать насколько он занимателен.

2. Задача 44. Wildcard Matching

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

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

Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)

Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:

• Отличная статья ---пресс служба университета---> невразумительный пресс-релиз.
• Пресс релиз ---занятный перевод---> непонятная статья на гиктаймс

Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.

Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.

О чём пойдёт речь:

• История задачи
  
  • Латинский квадрат
  • Задача о восьми ферзях
• Три типа задачи "о ферзях"
  
  • Расстановка N ферзей
  • Подсчет числа решений
  • Дополнение до N ферзей
  • Вариации задачи
• Модели и сложность
  
  • Линейный поиск для N ферзей
  • Как считать число решений на практике
  • Дополнение до N
• Выводы

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

Здесь вы не найдёте устаревшего посыла «функциональное программирование спасёт мир!»; мой список состоит из куда менее популярных наименований. Готов поспорить, многие из читателей вообще не слышали о большинстве языков и парадигм, о которых пойдёт речь, так что надеюсь, вам будет так же интересно с ними разбираться, как и мне.

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

В задачах искусственного интеллекта применяются различные модели представления знаний и методы вычислений — мягкие вычисления, генетические алгоритмы, нейросети, логические модели и другие подходы. Все эти методы основаны на символьных вычислениях и поэтому могут быть реализованы на основе языка PROLOG.
Здесь мы рассмотрим методы построения интеллектуальных систем на основе логического подхода, который наиболее близок природе логического программирования и часто применяется в экспертных системах.

Публикация первой части ( habrahabr.ru/post/274603 ) вызвала довольно обширную и интересную дискуссию по различным аспектам языка применения ПРОЛОГ.
Цель была – показать опытным, и не очень, программистам, что ничего сложного в Прологе нет, и каждый может его применять в работе.
Почему-то не было вопросов непосредственно по тексту публикации. Буду думать, что там все понятно.
Приступим к рассмотрению более практических аспектов программирования на языке Пролог.

Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения. В то же время, Интернет основан на символьной информации, поэтому практически все современные программисты сталкиваются с необходимостью обрабатывать символьные структуры данных, а ведь для этого и предназначен язык логического программирования ПРОЛОГ. Этот язык – идеальный для работы с символьными структурами, текстовыми файлами и для построения интеллектуальных программ.

Представьте себе высокоуровневый язык, в котором не нужно указывать КАК получить результат, вместо этого нужно просто указать ЧТО вы хотите получить. При этом область применения языка не ограничена и язык способен решать те же задачи, что и любой другой высокоуровневый язык, наподобие JAVA. Кажется фантастикой, не правда ли? Однако такой язык есть и называется он PROLOG. Посмотрим как PROLOG справляется с этой задачей на примере загадывания прологу некоторых загадок и попросим PROLOG выдать доказательство теоремы.

Эта статья является ответом на статью «Задача Эйнштейна на Прологе». В ней автор пишет, что Пролог очень хорошо подходит для решения этой задачи и что суммарное количество строк почти совпадает с условиями задачи. Здесь я хочу показать, что на C# количество строк кода может быть примерно тем же. Я просто скопирую решение на Прологе и немного изменю синтаксис. Сначала приведу итоговый результат, а потом распишу функции. Вот что получилось:

Есть много материала по решению запутанных задачек на Прологе (например, страница Hakan Kjellerstrand о B-Prolog). Однако часто приводятся задачи, которые либо создавались для решения вручную (имеют маленькое пространство поиска), либо изначально ориентированы на решение при помощи логического программирования.

Я хочу показать мое решение на Прологе задачи AAAAAA с первого раунда Facebook Hacker Cup 2014. Задача имеет достаточно большое пространство поиска и создана с прицелом на решение опытными спортивными программистами на распространенных языках программирования.

Приступающие к изучению и/или работе с SWI-Prolog (http://www.swi-prolog.org/) часто сталкивается зачастую с не очень «дружелюбным интерфейсом командной строки вот в таком стиле:

dm@dms:~> swipl
% library(swi_hooks) compiled into pce_swi_hooks 0.00 sec, 3,856 bytes
% /home/dm/.plrc compiled 0.00 sec, 656 bytes
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 5.10.2)
Copyright (c) 1990-2010 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- 

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

Как это исправить?

Наберите в командной строке „help.“

?- help.