Simulation to find the minimum number of patrollers to cover a wall

Question

Problem description

Scarpi, who owns a restaurant, decided to remodel it with his friends because the interior of the restaurant is too old. The place where the restaurant is located is a very cold area in the snow town, so it is necessary to check the condition of the exterior walls periodically during the interior work.

The structure of the restaurant is completely round and the total circumference of the outer wall is n meters, and some points on the outer wall have vulnerable points which may be damaged in extreme cold. Therefore, we decided to periodically send friends to check whether the vulnerable points of the outer wall were not damaged during the internal construction. However, the inspection time was limited to 1 hour for quick construction. The distance that friends can travel for an hour is different, so try to get at least a few friends to check for vulnerabilities and the rest of the friends to help with the construction. For convenience, the north-facing point of the restaurant is represented by 0, and the location of the vulnerable point is indicated by the distance clockwise from the north-facing point. In addition, friends only move along the outer wall clockwise or counterclockwise from the starting point.

When given as a parameter the length of the outer wall n, an array containing the location of the weak point, and an array dist with the distance each friend can move for 1 hour, return the minimum number of friends that should be sent to check for the weak point. Complete the solution function.

Limitations

• \$n\$ is a natural number between \$1\$ and \$200\$, inclusive.
• A weakness has a length between \$1\$ and \$15\$, inclusive.
• Two different vulnerabilities are not given the same location.
• The location of the weak point is given in ascending order.
• The weak element is an integer greater than or equal to \$0\$ and less than \$n-1\$.
• The length of dist is \$1\$ or more and \$8\$ or less.
• The elements of dist are natural numbers between \$1\$ and \$100\$, inclusive.

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/
https://programmers.co.kr/learn/courses/30/lessons/60062
The first link is the website to the description and second link is the challenge site. But I don't think this would be of help since it's in Korean language.

This simulation is given finding the minimum numbers of patrollers, given patroller's coverage and position of the weak points. The weak points are the weak points on the wall that needs to be fixed. The wall is circular, and that's why there exists additional push_back when creating create_dist_btw_wp.

I stored the distances between weakpoints as vector, and tried to test all permutations of the patrollers.

#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

inline int num_patrolling(vector<int>::const_iterator cit, vector<int>::const_iterator cbegin) {
    return int(cit - cbegin) + 1;
}

vector<int>& create_dist_btw_wp(vector<int>& weak_points, int wall_length) {
    vector<int>* result = new vector<int>;
    for (int i = 1; i < weak_points.size(); ++i)
        result->push_back(weak_points[i] - weak_points[i - 1]);
    result->push_back(weak_points[0] + wall_length - weak_points.back());
    return *result;
}

int main() {
    int wall_length = 12;
    vector<int> weak_points = {1, 5, 6, 10};
    vector<int> patrol_dists = {1, 2, 3, 4};
    cout <<solution(wall_length, weak_points, patrol_dists) << endl;

    return 0;
}

// wp stands for weakpoints
// weak_points stores dist of wps at wall from 0
int solution(int wall_length, vector<int> weak_points, vector<int> patrol_dists) {
    if (weak_points.size() == 1)
        return 1;

    vector<int> dist_btw_wp = create_dist_btw_wp(weak_points, wall_length);

    sort(patrol_dists.begin(), patrol_dists.end());
    auto num_wp = weak_points.size();

    int ans = 0x3f3f3f3f;
    // TODO//
    // seems next_permutation is enough and 2 for loops inside
    // do_while loop seems overkill.
    // Needs to be checked
    do {
        for (int first_wp_idx = 0; first_wp_idx < num_wp; ++first_wp_idx) {
            int end_wp_idx = (first_wp_idx + num_wp - 1) % num_wp;
            bool wp_patrolled[20]{};

            auto it_patrol_dists = patrol_dists.cbegin();
            int patrolled_dist = 0;

            for (int cur_wp_idx = first_wp_idx; cur_wp_idx != end_wp_idx; (++cur_wp_idx) %= num_wp)
            {
                if (it_patrol_dists == patrol_dists.cend()) break; // can't patrol all

                wp_patrolled[cur_wp_idx] = true;
                patrolled_dist += dist_btw_wp[cur_wp_idx];
                if (patrolled_dist > *it_patrol_dists)
                {
                    ++it_patrol_dists;
                    patrolled_dist = 0;
                }
            }

            if (it_patrol_dists != patrol_dists.cend())
                ans = min(ans, num_patrolling(it_patrol_dists, patrol_dists.cbegin()));
        }
    } while (next_permutation(patrol_dists.begin(), patrol_dists.end()));

    return ans == 0x3f3f3f3f ? -1 : ans;
}

Answer 1

Avoid Using Namespace std

It is possible that #include <bits/stdc++.h> and using namespace std; was provided by the challenge site, in that case it might be better to delete that from the code when you answer the challenge.

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

As an example of how the using namespace std; can be confusing, while reviewing the code I found the code

    } while (next_permutation(patrol_dists.begin(), patrol_dists.end()));

since I don't know every std library routine I performed a search for next_permutation in the code. I ended up in the algorithm include header.

Include Headers

The code contains #include <string> and is missing #include <algorithm>. The string header is not necessary because string are not used in the program. The only reason the code was compiling on the challenge site is because the #include <bits/stdc++.h> was there. Make sure to include all the headers necessary.

Magic Numbers

There is a numeric constant in the solution() function (0x3f3f3f3f), it might be better to create symbolic constants for this to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier. In this particular instance it isn't clear what this value means.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Memory Leak

The function std::vector<int>& create_dist_btw_wp(std::vector<int>& weak_points, int wall_length) allocates a vector, but the vector is never deleted. In a larger program this would lead to a memory leak that could have serious side effects. If returning a reference was done for performance reasons, then at the end of the function solution() the vector should be deleted. If it was done for any other reason perhaps the function should be rewritten as

std::vector<int> create_dist_btw_wp(std::vector<int>& weak_points, int wall_length) {
    std::vector<int> result;
    
    for (size_t i = 1; i < weak_points.size(); ++i)
    {
        result.push_back(weak_points[i] - weak_points[i - 1]);
    }
    result.push_back(weak_points[0] + wall_length - weak_points.back());
    
    return result;
}

The memory allocated for the result vector in the function will automatically be deleted when the function ends, a copy of result is returned to the solution() function. That copy will be automatically deleted when the function solutions ends.

Use Code Blocks

Primarily for maintenance reasons it is a good habit to create code blocks within if statements, else clauses and within loops. Many bugs have been created during maintenance when one or more statements was added to an if statement or a loop. There is an example of this in the code above. It also makes the code a little easier to read. Vertical spacing should also be used to make the code more readable.

Complexity

The function solution() is too complex (does too much). Perhaps the contents of the outer for loop of the do while should be a function.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.