/** **/ ====== Homework 01: The "I Left My Dishes in the Rain" Problem ====== ==== Overview ==== 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: - Zip the file ''main.py'' into **.zip archive** with arbitrary name. - Upload the .zip file to the [[https://cw.felk.cvut.cz/brute/|BRUTE]] evaluation system. ==== Problem statement ==== Imagine you left your dishes (represented by a [[https://en.wikipedia.org/wiki/Heightmap|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. {{ :courses:be5b33pge:practices:hw01_example_solution.png?nolink&900 |}} 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. {{ :courses:be5b33pge:practices:screenshot_from_2025-04-02_01-38-55.png?nolink&400 |}} 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. ==== Grading ==== You can obtain maximum of **6 points**: * **2 points** for elevation maps of size up-to **10x10** (10 tests, **5s maximum** per test) * **2 points** for elevation maps of size up-to **100x100** (10 tests, **10s maximum** per test) * **2 points** for elevation maps of size up-to **1000x1000** (10 tests, **20s maximum** per test) Please note: the BRUTE evaluation can take up to **6 minutes** to return the results. ==== Testing Your Code Localy ==== 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. If you are having **troubles running trimesh**, please try the following: - ''pip install trimesh'' - ''pip install scipy'' - ''pip install "pyglet<2"'' To run these tests, simply execute the ''main'' module as a standalone script. ==== Starter Code ==== 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: [[mailto:parildav@fel.cvut.cz|David Pařil: parildav@fel.cvut.cz]] Good luck! :) {{ :courses:be5b33pge:practices:screenshot_from_2025-04-01_23-54-18.png?nolink&1200 |}}