Visualising a water filling algorithm

I was looking at the water filling problem described at “I Failed a Twitter Interview”. The problem is, given a topography expressed as an array of heights, to figure out the volume of water that will pool if it rains on that topography. I’m generally fairly rubbish at puzzles, and my solution to the problem only worked for a particular subset of the problem.

I was then trying to understand the solution the author presented, so I wrote a visualisation of it. I’ve included the code below, it produces a move-by-move visualisation of the state of the solver. Writing it helped me understand the elegance of the presented by the solution.

The output looks like the following (where ~ represents water):

                      _                      
    _     _          |8|                     
   |7|~~~|7|~_~~~~~~~| |       _             
   | |~~~| ||6|~~~~_~| |~~~~_~|6|            
   | |~~~| || |~_~|5|| |~~~|5|| |            
   | |~_~| || ||4|| || |~~~| || |    _  _    
 _ | ||3|| || || || || |~~~| || |~~~|3||3| _ 
|2|| || || || || || || |~~~| || |~~~| || ||2|
| || || || || || || || |~_~| || |~_~| || || |
Current Volume: 20

Code:

import java.util.Random; 
 
public class WaterLevel 
{ 
	private static final long PER_MOVE_SLEEP = 300; 
 
 
	public static void main(String[] args) throws java.lang.Exception 
	{ 
		calculateVolume(generate(10, 15), true); 
	} 
 
 
	public static void calculateVolume(final int[] land, final boolean showMoves) 
	{ 
		final int[] water = new int[land.length]; 
 
		int leftMax = 0; 
		int rightMax = 0; 
		int left = 0; 
		int right = land.length - 1; 
		int volume = 0; 
 
		while (left < right) 
		{ 
			leftMax = Math.max(leftMax, land[left]); 
			rightMax = Math.max(rightMax, land[right]); 
 
			final boolean movedLeft; 
			if (leftMax >= rightMax) 
			{ 
				volume += rightMax - land[right]; 
				water[right] = (rightMax - land[right]); 
				right--; 
				movedLeft = false; 
			} 
			else 
			{ 
				volume += leftMax - land[left]; 
				water[left] = (leftMax - land[left]); 
				left++; 
				movedLeft = true; 
			} 
 
			if (showMoves || left == right) 
			{ 
				// Render the state 
				render(land, water, left, right, volume, movedLeft); 
 
				// Wait until rendering the next frame 
				if (left != right) 
				{ 
					try 
					{ 
						Thread.sleep(PER_MOVE_SLEEP); 
					} 
					catch (InterruptedException e) 
					{ 
						throw new RuntimeException(e); 
					} 
				} 
			} 
		} 
	} 
 
 
	/** 
	 * Generate a topography 
	 * 
	 * @param maxHeight 
	 *      maximum height 
	 * @param width 
	 *      width 
	 * 
	 * @return 
	 */ 
	private static int[] generate(int maxHeight, int width) 
	{ 
		final Random random = new Random(); 
 
		int[] land = new int[width]; 
 
		for (int i = 0; i < land.length; i++) 
			land[i] = random.nextInt(maxHeight); 
 
 
		return land; 
	} 
 
 
	private static int max(final int... land) 
	{ 
		int max = land[0]; 
 
		for (int level : land) 
			max = Math.max(max, level); 
 
		return max; 
	} 
 
 
	/** 
	 * Render the map, showing the land - and on top of it, the computed water thus far (and also showing the left and right 
	 * pointers) 
	 * 
	 * @param land 
	 *      the land height 
	 * @param water 
	 *      the water depths computed so far 
	 * @param left 
	 *      the left pointer position 
	 * @param right 
	 *      the right pointer position 
	 * @param volume 
	 *      the current total volume 
	 * @param movedLeft 
	 *      true if we have just moved the left pointer (false if we've just moved the right) 
	 */ 
	public static void render(final int[] land, 
							  final int[] water, 
							  final int left, 
							  final int right, 
							  final int volume, 
							  final boolean movedLeft) 
	{ 
		// Compute max land level so we don't waste space rendering open air 
		final int max = max(land); 
 
		// Allocate enough space for the output 
		final StringBuilder sb = new StringBuilder((3 + max) * 3 * land.length); 
 
		// Render the pointer position (and indicate movement) 
		for (int i = 0; i < land.length; i++) 
		{ 
			if (i == left) 
				sb.append(movedLeft ? " > " : " . "); 
			if (i == right) 
			{ 
				sb.append(!movedLeft ? " < " : " . ").append('\n'); 
				break; 
			} 
			else 
				sb.append("   "); 
		} 
 
		// Now render the map 
		for (int altitude = (max + 1); altitude > 0; altitude--) 
		{ 
			for (int j = 0; j < land.length; j++) 
			{ 
				final int groundLevel = land[j]; 
 
				if (altitude - 1 == groundLevel) 
					if (water[j] != 0) 
						sb.append("~_~"); // Wet ground 
					else 
						sb.append(" _ "); // The ground 
				else if (groundLevel > altitude) 
					sb.append("| |"); // Below the ground 
				else if (groundLevel == altitude) 
				{ 
					sb.append("|" + altitude + "|"); // Just beneath the ground 
				} 
				else if (groundLevel + water[j] >= altitude) 
					sb.append("~~~"); // Underwater 
				else 
					sb.append("   "); 
			} 
			sb.append('\n'); 
		} 
 
		sb.append("Current Volume: ").append(volume).append("\n"); 
 
		System.out.println(sb); 
	} 
}