Task

In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains,
completely filling all convex enclosures in the chart with water.



9               ██           9               ██    
8               ██           8               ██    
7     ██        ██           7     ██≈≈≈≈≈≈≈≈██    
6     ██  ██    ██           6     ██≈≈██≈≈≈≈██    
5 ██  ██  ██  ████           5 ██≈≈██≈≈██≈≈████    
4 ██  ██  ████████           4 ██≈≈██≈≈████████    
3 ██████  ████████           3 ██████≈≈████████    
2 ████████████████  ██       2 ████████████████≈≈██
1 ████████████████████       1 ████████████████████


In the example above, a bar chart representing the values [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] has filled, collecting 14 units of water.

Write a function, in your language, from a given array of heights, to the number of water units that can be held in this way, by a corresponding bar chart.

Calculate the number of water units that could be collected by bar charts representing each of the following seven series:

   [[1, 5, 3, 7, 2],
    [5, 3, 7, 2, 6, 4, 5, 9, 1, 2],
    [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1],
    [5, 5, 5, 5],
    [5, 6, 7, 8],
    [8, 7, 7, 6],
    [6, 7, 10, 7, 6]]


See, also:

 Four Solutions to a Trivial Problem – a Google Tech Talk by Guy Steele
 Water collected between towers on Stack Overflow, from which the example above is taken)
 An interesting Haskell solution, using the Tardis monad, by Phil Freeman in a Github gist.


	cpu	8086
	org	100h
section	.text
	jmp	demo
	;;;	Calculate the amount of water a row of towers will hold
	;;;	Note: this will destroy the input array.
	;;;	Input: DX = tower array, CX = length of array
	;;;	Output: AX = amount of water	
water:	xor	ax,ax		; Amount of water starts at zero	
	xor	bx,bx		; BH = zero, BL = block count
.scanr:	mov	di,dx		; DI = right edge of towers
	add	di,cx
.rloop:	dec	di
	cmp	di,dx		; Reached beginning?
	jl	.out		; Then calculation is done.
	cmp	bh,[di]		; Otherwise, if the tower is zero,
	je	.rloop		; Keep scanning
	xor	bl,bl		; Set block count to zero
	mov	si,dx		; SI = left scanning edge
.scanl:	cmp	bh,[si]		; Is the column empty?
	je	.unit		; Then see whether to add an unit of water
	dec	byte [si]	; Otherwise, remove block from tower
	inc	bx		; And count it
	jmp	.next
.unit:	test	bl,bl		; Any blocks?
	jz	.next		
	inc	ax		; If so, add unit of water
.next:	inc	si		; Scan rightward
	cmp	si,di		; Reached the right edge?
	jbe	.scanl		; If not, keep going
	shr	bl,1		; If more than 1 block,
	jnz	.scanr		; Keep going
.out:	ret
	;;;	Calculate and print the amount of water for each input
demo:	mov	si,series
.loop:	lodsw			; Load pointer
	test	ax,ax		; If 0,
	jz	.done		; we're done.
	xchg	ax,dx
	lodsw			; Load length
	xchg	ax,cx
	push	si		; Keep array pointer
	call	water		; Calculate amount of water
	call	prax		; Print AX 
	pop	si		; Restore array pointer
	jmp 	.loop
.done:	ret
	;;;	Print AX as number
prax:	mov	bx,num		; Pointer to end of number string
	mov	cx,10 		; Divisor
.dgt:	xor	dx,dx		; Divide by 10 
	div	cx
	add	dl,'0'		; Add ASCII 0 to remainder
	dec	bx		; Store digit
	mov	[bx],dl
	test	ax,ax		; If number not zero yet
	jnz	.dgt		; Find rest of digits
	mov	dx,bx		; Print number string
	mov	ah,9
	int	21h
	ret
section	.data
	db	'*****'		; Output number placeholder
num:	db	' $'
	;;;	Series
t1:	db	1,5,3,7,2
t2:	db	5,3,7,2,6,4,5,9,1,2
t3:	db	2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1
t4:    	db	5,5,5,5
t5:	db	5,6,7,8
t6:    	db	8,7,7,6
t7:	db    	6,7,10,7,6
t_end:	equ	$
	;;;	Lengths and pointers
series:	dw	t1,t2-t1
	dw	t2,t3-t2 
	dw	t3,t4-t3 
	dw	t4,t5-t4
	dw	t5,t6-t5
	dw	t6,t7-t6
	dw	t7,t_end-t7
	dw	0