0
\$\begingroup\$

I'm trying to solve the problem given here.

Arrange given numbers to form the biggest number | Set 1

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are > {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, > 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

A simple solution that comes to our mind is to sort all numbers in descending order, but simply sorting doesn’t work. > For example, 548 is greater than 60, but in output 60 comes before 548. As a second example, 98 is greater than 9, but > 9 comes before 98 in output.

So how do we go about it? The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use > it to sort numbers.

Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y > appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, > else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

Following is the implementation of the above approach. To keep the code simple, numbers are considered as strings, the vector is used instead of a normal array.

I'm getting the required output but the written code looks like code bloat(I mean could've have written better simpler and easy code). Can somebody suggest a better way of doing it. This is my code

#include <iostream>
#include <string>
#include <algorithm>

bool comp(const int32_t ia, const int32_t ib) {
    const std::string a = std::to_string(ia);
    const std::string b = std::to_string(ib);

    int32_t i = 0;
    if (a.size() == b.size()) {
        while (i < a.size()) {
            if (a.at(i) == b.at(i)) {
                ++i;
                
                continue;
            }
            else if (a.at(i) > b.at(i))
                return true;
            else
                return false;
        }
    } else {
        int32_t min_size = static_cast<int32_t>(std::min(a.size(), b.size()));
        int32_t max_size = static_cast<int32_t>(std::max(a.size(), b.size()));
        
        while (i < min_size) {
            if (a.at(i) == b.at(i)) {
                ++i;
                
                continue;
            }
            else if (a.at(i) > b.at(i))
                return true;
            else
                return false;
        }
        
        const char temp = a.at(0);
        const std::string& max_str = (a.size() > b.size()) ? a : b;
        if (max_str == b) {
            while (i < max_size) {
                if (temp >= max_str.at(i++))
                    return true;
                else
                    return false;
            }
        } else {
            while (i < max_size) {
                if (temp >= max_str.at(i++))
                    return false;
                else
                    return true;
            }
        }
    }
}

int32_t main() {
    int32_t arr[] = { 546, 548, 54, 60 };
    int32_t arr_size = sizeof(arr) / sizeof(*arr);

    std::sort(arr, arr + arr_size, comp);
    for (const int val : arr)
        std::cout << val;
    std::cout << std::endl;

    return 0;
}
\$\endgroup\$
4
  • \$\begingroup\$ Use the C++ STL container classes such as std::vector and use iterators. \$\endgroup\$
    – pacmaninbw
    Feb 21, 2021 at 14:18
  • \$\begingroup\$ In the future please add the text of the problem as well as the link since links can break. \$\endgroup\$
    – pacmaninbw
    Feb 21, 2021 at 14:45
  • 1
    \$\begingroup\$ Please don’t edit the code in the question; it makes the answers nonsensical. If you want a new review with modified code, ask another question. \$\endgroup\$
    – indi
    Feb 21, 2021 at 15:46
  • \$\begingroup\$ That is a shocking amount of code for something that could be return a+b > b+a; once a and b are assigned! \$\endgroup\$ Feb 22, 2021 at 13:15

2 Answers 2

4
\$\begingroup\$

The code is broken

Before asking “can this code be sexier”, you should be asking “does this code work”.

Spoiler: it doesn’t.

Always test your code

You have written a function comp(a, b). You haven’t written any tests for it. You’ve used it in a single case and got the correct answer, but that means very little.

At the bare minimum, you should have a test suite that has two test cases: one for when a and b are equal, and one for when they are not.

For example, for the “equal” test case, you can just generate bunch of random numbers between 0 and some maximum. Here’s what that might look like using the Catch2 test framework:

#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"

#include <cstdint> // need for std::size_t, std::uint32_t
#include <limits>

// include the header with comp() declared

TEST_CASE("comparing equal")
{
    constexpr auto num_trials = std::size_t{10};

    constexpr auto min_val = std::int32_t{0};
    constexpr auto max_val = std::numeric_limits<std::int32_t>::max();

    auto value = GENERATE(take(num_trials, random(min_val, max_val)));

    INFO("value = " << value);
    CHECK_FALSE(comp(value, value)); // value cannot be less-than itself
}

This compiles (with warnings, more on that later), and runs, and all tests pass. That’s what happened for me, anyway. You may or may not get all tests passing, because there is a critical bug in your code. We’ll get back to that in the next section, but for now, I’ll just assume all tests passed.

So now for the “unequal” test case, you just list a bunch of pairs of numbers, where the first number should always compare less-than the second:

TEST_CASE("comparing unequal")
{
    auto data = GENERATE(table<std::uint32_t, std::uint32_t>({
        // single digit numbers
        {1, 0},
        {9, 0},
        {9, 8},
        // ... etc.
        // multi-digit numbers
        {111, 110},
        {124, 123},
        {130, 120},
        {130, 129},
        {200, 100},
        {200, 109},
        {200, 190},
        {200, 199},
        // ... etc.
        // other interesting cases, add as many as you please

        {1, 110}, // this works, but...
        {112, 1}, // try this one!

        {321, 3212}, // okay...
        {3214, 321}, // ... also okay...
        {3213, 321}, // ... but uh-oh!
    }));

    INFO("a = " << std::get<0>(data));
    INFO("b = " << std::get<1>(data));

    CHECK(comp(std::get<0>(data), std::get<1>(data)));

    CHECK_FALSE(comp(std::get<1>(data), std::get<0>(data)));
}

Again, compile and run. This time, there are failures.

Why does those cases fail? I’ll explain later, but for now I’ll just say that your algorithm will fail for some cases where one number is <pattern>, and the second number is <pattern>D<something> where the digit D is the same as the first digit of the pattern. For example, 545 and 54 (the former should come first, to get 54554, rather than 54545) would fail, but 565 and 56 work (56556 is less than 56565).

This is why we write tests.

Turn on warnings

If you compile with g++ or clang (and probably any other compiler), and turn warnings on… which you always should… you will get a warning like this:

warning: control reaches end of non-void function [-Wreturn-type]

(I actually get two warnings, and both matter, but the second isn’t as critical, because you’re only going to be dealing with small sizes. I’ll mention it later, though.)

What that warning is telling is you that you have a function—comp()—that returns something—something that is not void—but somehow it is possible to reach the end of the function—the closing }—without returning a value.

We can figure out exactly what is going on later, but for now, let’s hack a nasty little fix to shut the warning up. At the very end of comp(), right before the closing brace, add the following two lines:


    std::cerr << "you have a bug!" <<
        "\n    a = " << ia <<
        "\n    b = " << ib <<
        '\n';
    return false;

If the compiler is right, and if it is possible to get to the end of this function without returning a value, this will display an error message, and then just return false. So compile the test code again, and run it and…

… you get the same results as before… but now there are 10 messages in the output:

you have a bug!
    a = 1867888929
    b = 1867888929
you have a bug!
    a = 1276619030
    b = 1276619030
you have a bug!
    a = 1911218783
    b = 1911218783
... [ and so on ]

(The random numbers will be different, of course, but the pattern—the same number appearing for both a and b—will be the same.)

The compiler was right. You have a bug.

Looking at the messages printed, it seems to only happen when a equals b. Before we caught the bug, the function was just returning gibberish whenever a and b were equal… but you didn’t notice, because it didn’t matter to the algorithm (and also because you didn’t test), because when a and b are equal, the function could either return true or false and it makes no difference. It is undefined behaviour, and just happens to “work” on my platform (and probably yours, but who’s to say, because you didn’t test)… but on other platforms, anything could happen.

This is why we turn on warnings, and fix them.

Summary

Although your code appeared to be working, writing some tests and turning on warnings revealed:

  1. There are cases where it fails.
  2. Even when it appears to work, there is dangerous undefined behaviour.

You should always write tests to test your code; oftentimes it will blow your mind how it can fail in surprising and unexpected ways.

You should also always turn on all warnings, and then fix them. Some people even recommend turning warnings into errors, so that even a single warning will kill the compile. That’s not bad advice.

Code review

General issues

Overall, the biggest issue with your code is that it is—as you suspected—wildly overcomplicated. It is so ridiculously overcomplicated, that at least two expert level C++ programmers looked at your code and missed critical bugs, and/or failed to understand what was actually going on. (And I’m not even counting myself; I probably missed stuff, too.) That should be a sign.

There are two general rules that would make a HUGE difference:

  • Break up complicated functions into simpler ones. There are multiple parts of comp() that really should be broken out into separate functions. You have 4 loops in comp(); 1 is the max you should aim for… and even that might be too much, because of the second rule.
  • Avoid writing loops. If you find yourself writing a loop, stop… think about what you’re actually trying to do… it’s probably some standard algorithm. In that case, use that algorithm.

The second rule is really the most important, because when you stop yourself from writing naked loops and think in terms of algorithms instead:

  • Your code becomes easier to understand. std::mismatch(a.begin(), a.begin() + min_size, b.begin(), b.begin() + min_size) is already complicated, but I can still tell at a glance roughly what’s going on much easier than I can with a manual loop.
  • Complications are easier to spot. It is trivial to spot the difference between std::mismatch(p, p + max_str.size(), max_str.begin(), max_str.end()) and std::mismatch(max_str.begin(), max_str.end(), p, p + max_str.size()). Spotting the difference between those two loops? Not so much.
  • Mistakes are easier to spot. That first loop is just return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());. But because of the complexity of the loop, you didn’t realize you’d failed to account for the situation where the two strings are equal, and you get to the end of the loop without returning anything.
  • Especially when dealing with standard algorithms, they’re already tested and optimized. You can almost never beat them without serious sorcery (and even then, often not).

Review

bool comp(const int32_t ia, const int32_t ib)

You use int32_t throughout, but there are two problems with that.

  • First, it’s not int32_t. It’s std::int32_t, and you have to include <cstdint>. The reason it appears to work for you is probably that you’re using a C++ compiler/library that also doubles as a C compiler/library, and they just include int32_t without the std:: to be lazy. But it’s not guaranteed to work everywhere.
  • Second, int32_t is not portable in any case. All the fixed-width types are platform dependent. The moment you use one, you make your code less portable. And in this case, there’s no reason whatsoever for using one.

There’s absolutely no reason to use int32_t and not int. Using the wrong type breaks your code in some places (like returning it from main()). Where it doesn’t, it just makes your code unnecessarily unportable.

const std::string a = std::to_string(ia);
const std::string b = std::to_string(ib);

While these work fine, they’re unnecessarily inefficient. You already know the maximum size string you’ll need, and you know that both ia and ib should be greater than or equal to zero. You could use arrays and numeric_limits<type>::digits10(), and then to_chars() to do all this lightning fast, and with no memory allocation, something like so:

auto a_chars = std::array<char, std::numeric_limits<decltype(ia)>::digits10() + 2>{};
auto b_chars = std::array<char, std::numeric_limits<decltype(ib)>::digits10() + 2>{};

std::to_chars(a_chars.data(), a_chars.data() + a_chars.size(), ia);
std::to_chars(b_chars.data(), b_chars.data() + b_chars.size(), ib);

Or, better yet, move all that into its own function.

int32_t i = 0;

This is bad practice for a number of reasons.

First, you should only declare variables where you’re going to use them; unless you have a damn good reason, you should never declare them up at the top of a function.

And you should especially not reuse a variable for different things throughout a function. i is used as a loop counter in both branches of that if, for two (or more) entirely different loops. That’s bad. You don’t need it at all for either of the first two loops; in the first loop, it should just be a local counter for a for, if anything, and in the second loop, the same, and after you could set it using min_size.

if (a.size() == b.size()) {
    while (i < a.size()) {
        if (a.at(i) == b.at(i)) {
            ++i;
            
            continue;
        }
        else if (a.at(i) > b.at(i))
            return true;
        else
            return false;
    }
} else {

Alright, so what exactly is going on here? The manual loop just complicates what is actually a very simple thing. If the two strings are the same size, you go through looking for any mismatched characters, and if you find a mismatched pair, you return true if the character in a is less than the character in b.

What you don’t account for, though, is what happens if all the characters are equal. In that case, you just fall out of the loop and continue on… and eventually get to the end of the function, which returns nothing. That’s your critical bug.

This is what the code above is actually doing, using algorithms to make everything clearer:

if (a.size() == b.size())
{
    auto [it_a, it_b] = std::mismatch(a.begin(), a.end(), b.begin()); // don't need b.end(), because the sizes are the same
    if (it_a != a.end()) // don't need to check it_b, because the sizes are the same
    {
        return *it_a < *it_b;
    }
    else
    {
        // what happens here?
        //
        // your current code does nothing, so the program continues on to the
        // end of the function, which has no return statement... thus, the bug
    }
}

So what is supposed to happen if the two strings are equal? Logically, I’d think, you would return false, because if the two strings are equal, then ia is not less-than ib. So:

if (a.size() == b.size())
{
    auto [it_a, it_b] = std::mismatch(a.begin(), a.end(), b.begin());
    if (it_a != a.end())
    {
        return *it_a < *it_b;
    }
    else
    {
        return false;
    }
}

But searching for the first mismatch and then returning true if the first char is less than the second is just a lexicographical compare:

if (a.size() == b.size())
{
    return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

But that’s just what std::string’s operator< does:

if (a.size() == b.size())
{
    return a < b;
}

In other words, if the two strings are same size, return true only if a is lexicographically less than b. If you reason about your code at a higher level, rather than getting bogged down with loops, you can spot these simplifications much more easily. In other words, don’t focus on the details, step back and think about the big picture.

int32_t min_size = static_cast<int32_t>(std::min(a.size(), b.size()));
int32_t max_size = static_cast<int32_t>(std::max(a.size(), b.size()));

Forcing int32_t here introduces potential bugs. None are likely to trigger in reality, because the lengths of the two strings should be very, very small, even for 64- or 128-bit integers. However, there’s no sensible reason to tempt fate.

The first potential bug is truncation if the size is greater than what would fit in an int32_t. Again, that will never happen in reality, but again, why play dangerously for no good reason?

The second potential bug is what a decent compiler with warnings turned on will warn you about. Comparing signed and unsigned values is a craps shoot. If you are mixing signedness in a comparison, you can get absurdities like -1 > 1u.

There’s no reason to force-cast any of the above into int32_t… or to force-cast it into anything. Just use auto, and everything works:

auto const min_size = std::min(a.size(), b.size());
auto const max_size = std::min(a.size(), b.size());

Much less typing, too. Or:

auto const [min_size, max_size] = std::minmax(a.size(), b.size());

That works just as well.

while (i < min_size) {
    if (a.at(i) == b.at(i)) {
        ++i;
        
        continue;
    }
    else if (a.at(i) > b.at(i))
        return true;
    else
        return false;
}

The next naked loop; what exactly is this one doing? Well, it’s going from 0 (which is the value of i at the start of the loop, though it isn’t immediately obvious from the code), to the minimum size of the two strings, and doing a lexicographical comparison. In other words:

if (auto const res = a.compare(0, min_size, b); res != 0)
{
    return res < 0;
}

We don’t even need to check which one is smaller here, because we’re using the minimum size.

Now from this point on is where the problems really start. At this point, you’ve dealt with the case where the two strings have equal length (of course, you need to fix the bug when they’re exactly equal). You’ve also dealt with the case where you have a short string and a long string, and the first part of the long string is either greater or less than the short string. So what you have now is the case where you have a short string, and a longer string that starts with the short string. In other words: the short string is <pattern>, and the long string is <pattern><something>.

So what happens next?

Well, what you do is get the first digit of <pattern>, and then compare it with every digit in <something>. But does that make sense?

Consider when <pattern> is 42, and <something> is 41 or 49:

  • With 41, you compare the first 4 with the 4 in 41… it’s >=, so you return true.

    No problem, 42 should compare less than 4241, because 424241 is greater than 424142.

  • With 49, you compare the first 4 with the 4 in 49… it’s >=, so you return true.

    But 42 should compare less than 4249, because 424249 is NOT greater than 424942.

So your algorithm doesn’t work.

As for the rest of the function, I won’t review it in detail (because it needs to be rewritten), but I’ll just say:

  • Avoid std::string.at(). It’s unnecessary. You know for a fact the string is not empty, so a[0] is guaranteed to work.
  • You do some trickery with multiple loops to handle the two cases where a is shorter or longer than b, but that just caused confusion (as you saw). Instead, just do something like:
if (a.size() < b.size())
    some_helper_function(a, b);
else
    some_helper_function(b, a);

This is clearer, and safer.

Suggestions for fixing

First, write test cases. Especially consider test cases that might be troublesome.

Your function basically has two paths, one for when the two numbers have equal amounts of digits, and one for when they don’t. So you probably need (at least) three test cases:

TEST_CASE("equal values")
{
    // ...
}

TEST_CASE("unequal values with the same digit count")
{
    // ...
}

TEST_CASE("unequal values with different digit counts")
{
    // ...
}

In the latter case, you should check a bunch of of cases, but especially some cases where the short value is repeated one or more times, like:

  • 1 and 11
  • 1 and 1111111
  • 12 and 1212
  • 12 and 12121212
  • 21 and 2121
  • 21 and 21212121

And you should check cases where the short value is repeated, then followed by something that will make it sort before or after, like:

  • 45 and 451
  • 45 and 454
  • 45 and 459
  • 45 and 4545451
  • 45 and 4545454
  • 45 and 4545459
  • 54 and 541
  • 54 and 545
  • 54 and 549
  • 54 and 5454541
  • 54 and 5454545
  • 54 and 5454549

Once you have your test cases set up, you should think about what makes one number sort before or after another… especially when there is a repeated pattern. Like, does 56 come before or after 561, 565 and 569, and why? What about 56 and 5656561, 5656565, and 5656569? I’ll give you one tip: it’s all about lexical comparisons with the short pattern… repeated lexical comparisons with the short pattern, not just one-and-done.

And of course, turn on warnings, and heed them.

\$\endgroup\$
4
  • \$\begingroup\$ +5. I hope your review is not taken as discouraging or frustrating as there is a lot to learn here. Thanks! \$\endgroup\$
    – Aganju
    Feb 22, 2021 at 4:30
  • \$\begingroup\$ You missed the third issue with std::int32_t: it's a signed type, so a poor fit in an unsigned problem domain. \$\endgroup\$ Feb 22, 2021 at 13:07
  • \$\begingroup\$ Eww, I see what you mean about int32_t everywhere - int32_t main() is only legal by chance... (I'm assuming OP's platform has int that happens to be the same type). \$\endgroup\$ Feb 22, 2021 at 13:23
  • \$\begingroup\$ Thanks for the detailed explanation and good suggestions for writing better code. I learned a lot from you. \$\endgroup\$
    – Harry
    Feb 22, 2021 at 13:48
1
\$\begingroup\$

Simplify the Returns

There is no need for the complex if statements such as

if (a.at(i) > b.at(i))
    return true;
else
    return false;

These can be simplified to

return (a.at(i) > b.at(i));

There is no need for the continue; statement in any of the loops since they are all embedded in if statements and the following code is outside the body of the current if clause.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the suggestions. I've made the suggested changes of you and it's more elegant than before. \$\endgroup\$
    – Harry
    Feb 21, 2021 at 15:42
  • \$\begingroup\$ It’s probably also worth mentioning that all of those loops look like variations on string::compare(). The first one (before the original code was edited, of course), basically looks like just return a < b; (ignoring bugs where nothing gets returned). \$\endgroup\$
    – indi
    Feb 21, 2021 at 15:44
  • \$\begingroup\$ I think the part of the code which @pacmaninbw is saying is not repetition because I'm returning different value in the if and else part for the same conditions \$\endgroup\$
    – Harry
    Feb 21, 2021 at 15:52
  • \$\begingroup\$ Sorry, your correct about the duplication I missed that. \$\endgroup\$
    – pacmaninbw
    Feb 21, 2021 at 16:11

Your Answer

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

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