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

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

Читать полностью »