Эй, фулстеки, давайте тренировать навыки. Предлагаю разминать извилины, как мне кажется, это интересно делать используя иную, непривычную, парадигму. Большинство разработчиков имеют развитой скилл алгоритмизации — задача превращается в кирпичики, которые нужно соединить, продумать последовательность ходов, которая приводит к желаемому заключению.
Вот тут, неделю назад, был упомянут Пролог, хотелось бы ответить, что язык Пролог подходит для решения задачек. Я уже затрагивал эту тему, и приводил несколько доступных мне решений случайных задач с сайта с заданиями на алгоритмы, хотелось бы показать, что любое сложное решение доступно изложению на декларативном языке, да и работать оно может не медленнее (ну-у, может, заметно не очень медленнее).
Взяться за представления следующей задачки долго не получалось, и вот уже получено первое решение, демонстрирую задачу и узнаю, на сколько оно сильно медленно.
Пролог интересен тем, что можно сотворить дедуктивную программу, которая показывает множество решений и может даже ограничивать его, но не дает способ перебора,
алгоритм будет выработан решателем интерпретатором.
Так вот, задача такова:
- 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.
