Homework 01: The "I Left My Dishes in the Rain" Problem

In this assignment, you will create a single Python file main.py. In this file, you must implement the flood function.

Both the file name and the function name must match exactly as specified.

When submitting your solution:

1. Zip the file main.py into .zip archive with arbitrary name.
2. Upload the .zip file to the BRUTE evaluation system.

Imagine you left your dishes (represented by a 2D elevation map) out in the rain, and now water has pooled on them. Your task is to complete the flood function so that it computes the resulting elevation map after flooding, assuming an infinite rain and negligible water viscosity.

As a true DIY enthusiast, you create your own dishes. Although you are undeniably good at it, your dishes can sometimes have unusual shapes. Therefore, your flood function must work correctly on any generic 2D elevation map. We assume the 2D elevation map is placed freely on a table, thus water is free to flow away from the borders of the 2D elevation map (there is no wall surrounding the 2D elevation map). Since the table on which the elevation map is placed is impermeable, the edges of the elevation map are also the only place where water can leave the area.

The image above shows the expected outcome when using the default terrain generation settings provided in the sample code below. Notice how the water level stops just in time, avoiding spilling over the edges of the elevation map.

Input:
[[1.3 0.9 0.8 0.7 1.2 1.8 2.  1.5 1.3 1.5]
 [1.5 1.4 1.  0.7 1.  1.5 1.7 1.5 1.6 1.8]
 [1.4 1.2 0.8 0.9 0.9 1.  1.1 1.2 1.4 1.5]
 [0.9 1.3 1.5 1.5 1.3 1.  0.8 0.7 0.9 0.8]
 [1.  1.4 1.8 1.7 1.4 0.9 0.5 0.3 0.6 0.8]
 [1.3 1.4 1.5 1.5 1.1 0.7 0.3 0.  0.6 1.3]
 [1.  1.2 1.2 1.2 0.8 0.7 0.6 0.1 0.5 1.1]
 [0.7 0.8 1.2 0.9 0.7 0.6 0.7 0.2 0.3 0.7]
 [0.9 0.7 1.1 0.8 0.8 1.  1.  0.3 0.2 0.7]
 [1.1 0.6 0.7 0.8 1.2 1.5 1.7 1.1 0.8 1.2]]
Output:
[[1.3 0.9 0.8 0.7 1.2 1.8 2.  1.5 1.3 1.5]
 [1.5 1.4 1.  0.7 1.  1.5 1.7 1.5 1.6 1.8]
 [1.4 1.2 0.9 0.9 0.9 1.  1.1 1.2 1.4 1.5]
 [0.9 1.3 1.5 1.5 1.3 1.  0.8 0.7 0.9 0.8]
 [1.  1.4 1.8 1.7 1.4 0.9 0.7 0.7 0.7 0.8]
 [1.3 1.4 1.5 1.5 1.1 0.7 0.7 0.7 0.7 1.3]
 [1.  1.2 1.2 1.2 0.8 0.7 0.7 0.7 0.7 1.1]
 [0.7 0.8 1.2 0.9 0.7 0.7 0.7 0.7 0.7 0.7]
 [0.9 0.7 1.1 0.8 0.8 1.  1.  0.7 0.7 0.7]
 [1.1 0.6 0.7 0.8 1.2 1.5 1.7 1.1 0.8 1.2]]

Please note that your algorithm may be tested on multiple elevation maps, with sizes up to 1000×1000, and must meet the specified time limits in the BRUTE evaluation system.

You can obtain maximum of 6 points:

• 2 points for elevation maps of size up-to 10×10 (10 tests, 5s maximum per test)
• 2 points for elevation maps of size up-to 100×100 (10 tests, 10s maximum per test)
• 2 points for elevation maps of size up-to 1000×1000 (10 tests, 20s maximum per test)

Please note: the BRUTE evaluation can take up to 6 minutes to return the results.

The starter code which is provided bellow includes a main, which helps you both test and visualize your flood function. We provide two helper functions terrain_generator and visualize_scene.

• The terrain_generator uses a Fourier-based fractal terrain generation method to help you test your code on “naturally” looking landscapes (in contrast to pure random noise). Similar techniques are often used to generate random, yet believable, words in video games (e.g. Minecraft). Feel free to adjust the beta parameter which changes the terrain roughness (this may be particularly useful for large-scale elevation maps).

• The visualize_scene function allows you to easily visualize the input and output of the flood function. The resulting 3D visualizations are shown in the images above. Please ensure you have installed the trimesh package (via pip install trimesh) to enable the visualizations.

To run these tests, simply execute the main module as a standalone script.

Below is a basic code structure you can use. Copy-paste the following code and complete the flood function according to the description above. Then submit your final main.py.

import numpy as np
import heapq
 
def flood(elev):
	"""
	Compute the flood level across a 2D elevation map.
	:param elev: 2D np.array (matrix) of size n x m representing the elevation of each cell
	:return: 2D np.array (matrix) of size n x m representing the elevation of each cell after flooding
	"""
	# TODO Implement
	return elev + 1
 
 
def visualize_scene(ground_hm, water_hm):
	"""
	Visualizes a 3D scene composed of ground and water elevation/height maps (the input/output of your code).
	:param ground_hm: 2D np.array (matrix) of size n x m representing the elevation of each cell
	:param water_hm: 2D np.array (matrix) of size n x m representing the elevation of each cell after flooding
	"""
	try:
		import trimesh
	except ImportError:
		print("trimesh package is not available! Please install it via pip:\n\npip install trimesh")
		return
 
	ground_hm, water_hm = np.array(ground_hm), np.array(water_hm)
	ground_meshes, water_meshes = [], []
 
	for y, x in np.ndindex(ground_hm.shape):
		g, w = ground_hm[y, x], water_hm[y, x]
		if g:
			box = trimesh.creation.box(extents=[1, 1, g])
			box.apply_translation([x + 0.5, y + 0.5, g / 2])
			box.visual.face_colors = [220, 220, 220, 255]
			ground_meshes.append(box)
		if w>g:
			box = trimesh.creation.box(extents=[1, 1, w-g])
			box.apply_translation([x + 0.5, y + 0.5, (w+g) / 2])
			box.visual.face_colors = [50, 150, 255, 150]
			water_meshes.append(box)
	ground_combined = trimesh.util.concatenate(ground_meshes) if ground_meshes else None
	water_combined  = trimesh.util.concatenate(water_meshes)  if water_meshes else None
 
	def get_outlines(mesh):
		if mesh is None:
			return None
		edges = mesh.face_adjacency_edges[mesh.face_adjacency_angles > np.radians(30)]
		return trimesh.path.Path3D(**trimesh.path.exchange.misc.edges_to_path(edges, mesh.vertices.copy())) if len(edges) else None
 
	ground_outline = get_outlines(ground_combined)
	water_outline  = get_outlines(water_combined)
 
	scene = trimesh.Scene([ground_combined, ground_outline, water_combined, water_outline])
	scene.camera_transform = scene.camera.look_at(
		points=scene.bounds,
		rotation=trimesh.transformations.euler_matrix(np.pi / 3, 0, np.pi / 5),
		distance=20,
	)
	scene.show()
 
 
def terrain_generator(shape, beta=5.0):
	"""
	Generates a synthetic terrain height map of the given shape
	:param shape: tuple with the dimensions (rows, cols) of the terrain grid
	:param beta: controls the roughness of the terrain
	:return: 2D np.array (matrix) of size n x m representing the elevation of each cell
	"""
	rows, cols = shape
	noise = np.random.randn(rows, cols) + 1j * np.random.randn(rows, cols)
	fx = np.fft.fftfreq(rows).reshape(-1, 1)
	fy = np.fft.fftfreq(cols).reshape(1, -1)
	f = np.sqrt(fx ** 2 + fy ** 2)
	f[0, 0] = 1.0 # Avoid division by zero
	noise *= 1.0 / (f ** (beta / 2))
	noise[0, 0] = 0
	terrain = np.fft.ifft2(noise).real
	terrain = (terrain - terrain.min()) / (terrain.max() - terrain.min())
	return np.round(terrain * 2, 1)
 
 
if __name__ == "__main__":
	np.random.seed(123) # COMMENT OUT FOR RANDOM MAPS
 
	# Generates random terrain
	ground_hm = terrain_generator((10, 10)) # change the size of elevation map here
 
	# Run algorithm
	water_hm = flood(ground_hm)
 
	# Visualize the result
	# Please install: pip install trimesh
	print(f"Input:\n{ground_hm}\nOutput:\n{water_hm}")
	visualize_scene(ground_hm, water_hm)

In case you have any questions, please contact:

David Pařil: parildav@fel.cvut.cz

Good luck! :)