В вымышленном 2D-мире набор инструкций 2D-печати для объекта может быть представлен в виде списка целых чисел следующим образом:

1 4 2 1 1 2 5 3 4

Каждое число представляет высоту объекта в этой конкретной точке. Приведенный выше список преобразуется в следующий объект при печати:

      #
 #    # #
 #    ###
 ##  ####
#########

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

      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Мы определяем способность объекта быть единицами воды, которую объект может удерживать, когда он полностью заполнен; в этом случае 11.

Строго говоря, единица воды ( ~) может существовать в месте, если и только если она окружена двумя сплошными блоками ( #) в одной строке.

Вызов

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

Можно предположить, что список содержит хотя бы один элемент, и все элементы находятся в диапазоне от 1 до 255.

Тестовые случаи

+-----------------+--------+
|      Input      | Output |
+-----------------+--------+
| 1               |      0 |
| 1 3 255 1       |      0 |
| 6 2 1 1 2 6     |     18 |
| 2 1 3 1 5 1 7 1 |      7 |
| 2 1 3 1 7 1 7 1 |      9 |
| 5 2 1 3 1 2 5   |     16 |
| 80 80 67 71     |      4 |
+-----------------+--------+

Haskell, 54 байта

f l=(sum$zipWith min(scanl1 max l)$scanr1 max l)-sum l

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

Orig:

      #
 #    # #
 #    ###
 ##  ####
#########

Слева:

      #~~
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Правильно:

~~~~~~#
~#~~~~#~#
~#~~~~###
~##~~####
#########

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

Минимум:

      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Наконец, количество воды - это сумма этого списка, который содержит как воду, так и землю, за вычетом суммы исходного списка, который содержит только землю.

Желе, 10 байт

U»\U«»\S_S

Хотя для APL требуется несколько скобок и J двухсимвольных символов, алгоритм в Jelly прекрасен.

     »\          Scan maximums left to right
U»\U             Scan maximums right to left
    «            Vectorized minimum
       S_S       Sum, subtract sum of input.

Попробуй это здесь .

МАТЛ , 14

Мой ответ Matlab переведен на MATL. алгоритм xnor.

Y>GPY>P2$X<G-s

объяснение

Y>: cummax()(ввод неявно помещается в стек)

G: толчок ввода (снова)

P: flip()

Y>: cummax()

P: flip()

2$X<: min([],[])(минимум с двумя аргументами)

G: толчок ввода (снова)

-: -

s: sum()

Дьялог АПЛ, 17 байт

+/⊢-⍨⌈\⌊⌽∘(⌈\⌽)

Это монадическая последовательность, которая принимает входной массив справа.

Алгоритм почти такой же, как у xnor, хотя я нашел его независимо. Он сканирует максимум в обоих направлениях (в обратном направлении, переворачивая массив, сканируя и снова переворачивая), и находит векторизованный минимум из них. Затем вычитается исходный массив и суммы.

Другой способ сделать это - разделить массив в каждом месте, но это дольше.

Попробуй это здесь .

Матлаб, 47

Также используя алгоритм xnor.

@(x)sum(min(cummax(x),flip(cummax(flip(x))))-x)

MATLAB, 116 113 109 106 байт

n=input('');s=0;v=0;l=nnz(n);for i=1:l-1;a=n(i);w=min([s max(n(i+1:l))]);if a<w;v=v+w-a;else s=a;end;end;v

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

Ungolfed код:

inputArray = input('');
leftHighPoint = inputArray(1);
volume = 0;
numPoints = nnz(inputArray);

for i = 1:numPoints-1
    currentPoint = inputArray(i); % Current value
    lowestHigh = min([max(inputArray(i+1:numPoints)) leftHighPoint]);

    if currentPoint < lowestHigh
        volume = volume + lowestHigh - currentPoint;
    else 
        leftHighPoint = currentPoint;
    end
end
volume

В первый раз, когда я пытался что-то сыграть в гольф, MATLAB, кажется, не лучший способ сделать это в ....

ES6, 101 байт

a=>(b=[],a.reduceRight((m,x,i)=>b[i]=m>x?m:x,0),r=m=0,a.map((x,i)=>r+=((m=x>m?x:m)<b[i]?m:b[i])-x),r)

Еще один порт алгоритма @ xnor.

Python 2 , 68 байт

lambda l:sum(min(max(l[:i+1]),max(l[i:]))-v for i,v in enumerate(l))

Попробуйте онлайн!

Пип -l , 19 байт

$+J(ST0XgZD1`0.*0`)

Принимает входные числа в качестве аргументов командной строки. Или добавьте -rфлаг, чтобы они воспринимались как stdin: попробуйте онлайн!

объяснение

В отличие от всех других ответов, в Пипе было на самом деле короче построить (измененную версию) ASCII-арт и сосчитать единицы воды.

Начнем с gсписка аргументов.

[1 4 2 1 5 2 3]

0Xgсоздает список строк из n нулей для каждого n в g.

[0 0000 00 0 00000 00 000]

ZD1затем объединяет эти строки в цепочку, используя 1для заполнения любых пробелов в результирующем прямоугольном вложенном списке:

[[0 0 0 0 0 0 0] [1 0 0 1 0 0 0] [1 0 1 1 0 1 0] [1 0 1 1 0 1 1] [1 1 1 1 0 1 1]]

STпреобразует этот список в строку В -lфлаг указывает , что списки отформатирован следующим образом : каждый вложенный список соединены без сепаратора, а на верхнем уровне разделителем является символ новой строки. Таким образом, мы получаем эту многострочную строку - по сути, диаграмму объекта, но вверх ногами:

0000000
1001000
1011010
1011011
1111011

Затем мы найдем все совпадения регулярного выражения `0.*0`. Это соответствует двум самым внешним стенам и всему между ними на каждой линии.

[0000000 001000 011010 0110]

Jобъединяет эти строки в одну большую строку и $+суммирует ее, давая число 1s - равное количеству воды, которое может удерживать объект.

6