7
\$\begingroup\$

Consider the array:

original_array1[17] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

I want to sort it in such a way that:

  1. Sum of adjacent numbers should be a perfect square
  2. You cannot reuse a number

So a possible solution is:

16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8 17

I write a C++ program to get this done using a recursive function and it works.

I was wondering how can I improve the program to:

  1. Make it more readable and easy to understand (variable names, better handling or elimination of boundary conditions, comments etc.)
  2. Use better library functions or C++ language features to make the code compact.
  3. Is there a better algorithm/strategy that I can use instead of using recursive functions.

The motivation for this came from a daily problem posted on brilliant.org, I thought I would solve it by writing a program. But now I want to ask the community for pointers on how to become better at coding in general.

Here is the code have:

//Compile using g++ -std=c++11 arrange.cpp 

#include <iostream>
#include <cstdint>
#include <cmath>

using namespace std;

int original_array1[17] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

bool isSumPerfectSquare(int x, int y) {  
    long double sr = sqrt((long double)x + (long double)y);
    return ((sr - floor(sr)) == 0);
}

int * ArrangeNumbers(int * done, int * remaining, int size_done, int size_remaining) {
    static int ctr = 0;
    // cout<<"ArrangeNumbers() "<< (ctr++) << endl<<"    ";
    // if(done != nullptr) {
    //  for(int jj = 0; jj<size_done;jj++) {
    //      cout<<done[jj]<<" ";
    //  }
    // }
    // cout<<" | ";
    // if(remaining != nullptr) {
    //  for(int jj = 0; jj<size_remaining;jj++) {
    //      cout<<remaining[jj]<<" ";
    //  }
    // }
    // cout<<endl;
    if(size_remaining == 1) { // Border Case 1: Last number remaining, lets check if pairs up with the last number in sorted array
        if(isSumPerfectSquare(done[size_done-1],remaining[0])) {
            int * finally_done = (int *) calloc(size_done+1,sizeof(int));
            for(int jj = 0; jj<size_done;jj++) {
                finally_done[jj] = done[jj];
            }
            finally_done[size_done] = remaining[0];
            return finally_done;
        } else {
            return nullptr;
        }
    } else if(size_done == 0) { // Border Case 2:  Come back and choose the first number again
        int * done1 = (int *) calloc(size_done+1,sizeof(int));
        int * remaining1 = (int *) calloc(size_remaining-1,sizeof(int));

        for(int kk = 0; kk<size_remaining;kk++) {
            done1[0] = remaining[kk];
            for(int ll = 0; ll<kk;ll++) {
                remaining1[ll] = remaining[ll];
            }
            for(int ll = kk+1; ll<size_remaining;ll++) {
                remaining1[ll-1] = remaining[ll];
            }
            int * sr_arr = ArrangeNumbers(done1, remaining1, size_done+1, size_remaining-1);
            if(sr_arr != nullptr) {
                free(done1);
                free(remaining1);
                return sr_arr;
            }
        }
        free(done1);
        free(remaining1);
        return nullptr;
    } else {
        int * done1 = (int *) calloc(size_done+1,sizeof(int));
        int * remaining1 = (int *) calloc(size_remaining-1,sizeof(int));

        // Copy array till now
        if(done != nullptr) {
            for(int jj = 0; jj<size_done;jj++) {
                done1[jj] = done[jj];
            }
        }

        // Choose next number and respawn
        for(int kk = 0; kk<size_remaining;kk++) {
            if(isSumPerfectSquare(done1[size_done-1],remaining[kk])) {
                done1[size_done] = remaining[kk];
                for(int ll = 0; ll<kk;ll++) {
                    remaining1[ll] = remaining[ll];
                }
                for(int ll = kk+1; ll<size_remaining;ll++) {
                    remaining1[ll-1] = remaining[ll];
                }
                int * sr_arr = ArrangeNumbers(done1, remaining1, size_done+1, size_remaining-1);
                if(sr_arr != nullptr) {
                    free(done1);
                    free(remaining1);
                    return sr_arr;
                }
            }
        }
        free(done1);
        free(remaining1);
        return nullptr;
    }
}

int main() {
    int * sorted_array = ArrangeNumbers(nullptr, original_array1, 0, 17);
    cout<<"Original Array :";
    for(int i = 0; i<17;i++) {
        cout<<" "<<original_array1[i];
    }
    cout<<endl<<"Sorted Array   :";
    if(sorted_array != nullptr) {
        for(int i = 0; i<17;i++) {
            cout<<" "<<sorted_array[i];
        }
        free(sorted_array);
    }
    cout<<endl;
    return 0;
}

\$\endgroup\$
6
\$\begingroup\$

Compilation options

Use more warnings, e.g. g++ -std=c++11 -Wall -Wextra. This will identify the unused variable ctr, for instance.

Avoid using namespace std

Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Choice of type

If all the numbers are guaranteed to be positive, consider using an unsigned type for the array elements.

Prefer using std::array over raw (C-style) arrays.

Checking for perfect square

It's good that we have a self-contained function for checking whether a number is a perfect square. However, it has accuracy problems when values reach the limit of a double's mantissa. It's also relatively slow, due to the use of std::sqrt(). One thing we could do instead is to create a std::set (or std::unordered_set) of the possible square numbers, and then simply test for membership of that set.

That looks something like this:

#include <algorithm>
#include <unordered_set>

unsigned original_array1[17] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

bool isSumPerfectSquare(unsigned x) {
    static auto const squares =
        []{
            std::unordered_set<unsigned> s;
            auto max = *std::max_element(std::begin(original_array1), std::end(original_array1));
            for (auto value = 1u, diff = 1u;  value < max * 2;  value += (diff += 2))
                s.insert(value);
            return s;
        }();

    return squares.find(x) != squares.end();
}

Prefer new[] and delete[]

When writing C++, prefer the new and delete operators and their array counterparts rather than C-style std::malloc(), std::calloc(), std::realloc() and std::free(). Prefer smart pointers and collections to bare pointers.

However, this algorithm shouldn't need any allocations at all, if we modify the input in place.

Here's how I'd do that, using std::swap to move each candidate in turn to the front of the array:

// shuffle [a..b), given preceding number
bool arrange_numbers(unsigned prev, unsigned *a, unsigned *b)
{
    if (a == b) {
        // no more numbers; we've done it!
        return true;
    }

    for (unsigned *p = a;  p != b;  ++p) {
        if (is_perfect_square(prev + *p)) {
            std::swap(*a, *p);
            if (arrange_numbers(*a, a+1, b)) {
                // found a match
                return true;
            }
            // reinstate the order, for our caller
            std::swap(*a, *p);
        }
    }

    // no satisfactory solution
    return false;
}


bool arrange_numbers(std::array<unsigned,17>& array)
{
    unsigned *a = array.begin();
    unsigned *b = array.end();

    for (unsigned *p = a;  p != b;  ++p) {
        std::swap(*a, *p);
        if (arrange_numbers(*a, a+1, b)) {
            // found a match
            return true;
        }
    }

    // no matches
    return false;
}

Full modified code

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


std::array<unsigned,17> numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

bool is_perfect_square(unsigned x) {
    static auto const squares =
        []{
            std::unordered_set<unsigned> s;
            auto max = *std::max_element(numbers.begin(), numbers.end());
            for (auto value = 1u, diff = 1u;  value < max * 2;  value += (diff += 2))
                s.insert(value);
            return s;
        }();

    return squares.find(x) != squares.end();
}


// shuffle [a..b), given preceding number
bool arrange_numbers(unsigned prev, unsigned *a, unsigned *b)
{
    if (a == b) {
        // no more numbers; we've done it!
        return true;
    }

    for (unsigned *p = a;  p != b;  ++p) {
        if (is_perfect_square(prev + *p)) {
            std::swap(*a, *p);
            if (arrange_numbers(*a, a+1, b)) {
                // found a match
                return true;
            }
            // reinstate the order, for our caller
            std::swap(*a, *p);
        }
    }

    // no satisfactory solution
    return false;
}


bool arrange_numbers(std::array<unsigned,17>& array)
{
    unsigned *a = array.begin();
    unsigned *b = array.end();

    for (unsigned *p = a;  p != b;  ++p) {
        std::swap(*a, *p);
        if (arrange_numbers(*a, a+1, b)) {
            // found a match
            return true;
        }
    }

    // no matches
    return false;
}


int main()
{
    std::cout << "Original array:";
    for (auto i: numbers) {
            std::cout << " " << i;
    }
    std::cout << '\n';

    if (arrange_numbers(numbers)) {
        std::cout << "Sorted array:";
        for (auto i: numbers) {
            std::cout << " " << i;
        }
        std::cout << '\n';
    }
}
\$\endgroup\$
4
\$\begingroup\$

Better strategy at the first glance does not exist. Consider a graph formed by the numbers an array, with the edges connecting vertices which add up to a perfect square. The problem then is reduced to finding a Hamiltonian path. The problem is known to be NP-complete. There is an algorithm solving it in \$O(n^2 2^n)\$ time; in general case it is better than brute force, but still exponential.

Your case could have a better asymptotic, because the graph has a very particular structure. For starters, for path to exist the should be no more than 2 vertices of the degree 1 (if the array had 18, there would be 3 such vertices). Also your graph is very sparsely connected, and has quite a few vertices of degree 2. This suggests a heuristic similar to the Warnsdorf's rule: start with a vertex of the least degree, and always inspect the neighbors in the ascending order of degrees (smallest first).

For example in your array, starting with 16 (degree 1) forces the resulting sequence with not a single branch point.

\$\endgroup\$
  • \$\begingroup\$ Even if you can reduce a problem to an NPC problem, it does not mean the original problem is necessarily hard. \$\endgroup\$ – Juho Feb 8 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.