4
\$\begingroup\$

Recently, I have gotten around implementing the rainfall challenge (which was the designated community challenge of August 2016) for practice purposes and would like to have some hints and improvements for my code. The implementation is in c++, and it is (in my opinion) quite lengthy, so please bear with me.

The project is split into two files: square_vector.h, which contains a general square_vector class which stores elements in a normal (= one dimensional) vector while adding functionality for treating the vector as a two dimensional array. The other file, main.cpp, contains the actual logic and code for the solution.

The idea of this solution is to iterate over each tile of the map and tracking to which sink the water flows to (or to a tile of which it is known to what basin it belongs), keeping track of the amount of tracked tiles in the process. Although I did not actively optimize for speed, any hints on possible performance increases are very much appreciated (however, as I said above, all other hints and improvements are naturally welcome as well).


square_vector.h

#pragma once

#include <vector>
#include <cstddef>
#include <utility>
#include <ostream>

template<typename T>
class square_vector {
    std::size_t side_length;
    std::vector<T> data;

    public:
    square_vector(std::size_t side_length) : side_length(side_length),
            data(side_length * side_length) { }

    std::size_t get_side_length() const { return side_length; }

    T& operator[](std::size_t index) { return data[index]; }
    T operator[](std::size_t index) const { return data[index]; }

    typename std::vector<T>::iterator begin() { return data.begin(); }
    typename std::vector<T>::iterator end() { return data.end(); }
    typename std::vector<T>::const_iterator begin() const {
        return data.begin(); 
    }
    typename std::vector<T>::const_iterator end() const { return data.end(); }

    std::size_t convert_coordinate_to_index(
            const std::pair<std::size_t, std::size_t>& coordinate) const;

    std::pair<std::size_t, std::size_t> convert_index_to_coordinate(
            std::size_t index) const;
};

template<typename T>
std::size_t square_vector<T>::convert_coordinate_to_index(
        const std::pair<std::size_t, std::size_t>& coordinate) const {
    return coordinate.first + coordinate.second * side_length;
}

template<typename T>
std::pair<std::size_t, std::size_t> square_vector<T>::convert_index_to_coordinate(
        std::size_t index) const {
    std::size_t x = index % side_length;
    std::size_t y = index / side_length;
    return std::make_pair(x, y);
}

main.cpp

#include <iostream>
#include <utility>
#include <cstddef>
#include <array>
#include <algorithm>

#include "square_vector.h"

std::vector<std::size_t> find_neighbour_indices(const square_vector<int>& map,
        std::size_t index) {
    static const std::array<std::pair<int, int>, 4> neighbour_offsets = {{
        {0, -1}, {1, 0}, {0, 1}, {-1, 0}
    }};

    std::vector<std::size_t> neighbours(4);
    std::size_t neighbours_index = 0;

    auto coordinate = map.convert_index_to_coordinate(index);

    for (const auto& offset : neighbour_offsets) {

        int x = coordinate.first + offset.first;
        int y = coordinate.second + offset.second;

        if (x >= 0 && y >= 0
                && static_cast<std::size_t>(x) < map.get_side_length()
                && static_cast<std::size_t>(y) < map.get_side_length()) {
            neighbours[neighbours_index] = map.convert_coordinate_to_index(
                    {x, y});
            ++neighbours_index;
        }
    }

    neighbours.resize(neighbours_index);
    return neighbours;
}

std::pair<unsigned, std::size_t> trace_tile(const square_vector<int>& map,
         square_vector<unsigned>& basins, std::size_t tile_index,
         unsigned next_basin_number) {

    std::vector<std::size_t> tile_path_indices;

    std::size_t current_index = tile_index;

    int joins_into_basin = 0;

    while (true) {
        if (basins[current_index]) {
            joins_into_basin = basins[current_index];
            break;
        }

        tile_path_indices.push_back(current_index);

        auto neighbour_indices = find_neighbour_indices(map, current_index);
        std::size_t lowest_neighbour = current_index;

        bool is_sink = true;

        for (std::size_t neighbour : neighbour_indices) {
            if (map[neighbour] < map[current_index]) {
                is_sink = false;
                lowest_neighbour = map[neighbour] < map[lowest_neighbour] ?
                    neighbour : lowest_neighbour;
            }
        }

        if (is_sink) {
            break;
        }

        current_index = lowest_neighbour;
    }

    unsigned basin_number;
    if (joins_into_basin) {
        basin_number = joins_into_basin;
    } else {
        basin_number = next_basin_number;
    }

    for (std::size_t tile : tile_path_indices) {
        basins[tile] = basin_number;
    }

    return {basin_number, tile_path_indices.size()};
}

std::vector<std::size_t> find_basins_and_sizes(
        const square_vector<int>& map) {

    square_vector<unsigned> basins(map.get_side_length());
    std::vector<std::size_t> basin_sizes;

    unsigned basin_number = 1;

    const std::size_t map_size = map.get_side_length() * map.get_side_length();
    for (std::size_t i = 0; i < map_size; ++i) {
        auto basin_data = trace_tile(map, basins, i, basin_number);

        if (basin_data.first == basin_number) {
            basin_sizes.push_back(basin_data.second);
            ++basin_number;
        } else {
            basin_sizes[basin_data.first - 1] += basin_data.second;
        }
    }

    return basin_sizes;
}

int main() {
    std::size_t map_size;
    std::cin >> map_size;

    square_vector<int> map(map_size);

    for (int& height : map) {
        std::cin >> height;
    }

    auto basin_sizes = find_basins_and_sizes(map);

    std::sort(basin_sizes.begin(), basin_sizes.end(),
            std::greater<std::size_t>());

    std::string delimiter(std::max(map_size, basin_sizes.size()) * 2 - 1, '-');
    std::cout << delimiter << '\n';

    for(std::size_t size : basin_sizes) {
        std::cout << size << ' ';
    }

    std::cout << '\n';
}

Thank you in advance!

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.