Refactor by removing nested for loop

[kimtaehong]

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<int>, and tried to test all permutations of the patrollers.

During refactoring, I've come to an idea that nested for loop inside do_while loop seems overkill and wanted to change this into simple for loop.[line 31:55]
What I've tried doesn't seem to work, and I can't see the difference between these two.

Was my original idea that this can be done in 1 dimensional for loop is of problem? or my implementation is wrong?

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;
}

// 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;
}

    do {
        bool wp_patrolled[20]{};
        int patrolled_dist = 0;
        auto it_patrol_dists = patrol_dists.cbegin();
        for (int cur_wp_idx = 0; cur_wp_idx < num_wp; ++cur_wp_idx)
        {
            if (it_patrol_dists == patrol_dists.cend()) break;

            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()));

[doug4]

Not exactly sure what the code is supposed to do. Some additional comments inside the function would help. Maybe explain the purpose of each loop. Also explain why you are creating permutations of weak points around a wall. I don't understand why weak points around a wall (presumably fixed locations) can be permuted to be in different orders (thus not fixed locations).

Stating that a nested loop looks like overkill does not justify removing it. Discovering a logical error or a redundancy can justify removing the nested loop. You may be correct--I don't have the time to do the analysis.

What I see here is a O(n! * n^2) algorithm. The outer loop doing the next_permutation is O(n!). Each of the inner loops is O(n).

By removing the nested loop, you are removing 1 level of complexity. So, the algorithm will not run the same.

Take a few minutes to write down in English what each version of the algorithm does, then write down how you expect the second version to compensate for the reduced complexity. You need more analysis than "seems overkill" and some hand waving.