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

В реализации на Скала я увидел операцию "(value % n)" и пояснение, что значения value,n -это: type class "Integral" требующий от типа "T" возможности вычислять остаток от деления и иметь значение "zero".

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

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

Задача 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.

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

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

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

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

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

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.

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

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

Это представление, о том, что я хорошо отношусь к декларативному способу выражения мыслей, а выражать все последовательностью команд и переходов между ними, мне кажется архаичным и устаревшим, ведь так делали наши деды, деды соединяли проводками контакты на коммутационной панели и получали мигание лампочек, а у нас монитор и распознавание голоса, как находясь на таком уровне эволюции можно все еще задумываться, о следовании команд… Мне кажется, если выражать программу логическим языком, она будет выглядеть понятнее, и это можно произвести в технологию, на это была сделана ставка еще в 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