8
\$\begingroup\$

Given any four-digit number that consists of at least two different digits, if you form a number by arranging its digits in descending order, and subtract the number formed by arranging its digits in ascending order, and repeat, you should eventually arrive at 6174, Kaprekar's Constant.

How can I make improvements to my code? Is my code readable and simple to understand?

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>

//at least two digits must be distinct
bool isUnique(int num)
{
constexpr int numlength = 4;
std::vector<int> digits;

for(int i = 0; i < numlength ; ++i)
{
    int digit = num%10;
    digits.push_back(digit);
    num /= 10;
}

//If digits are all equal return false.
if ( std::adjacent_find( digits.begin(), digits.end(), std::not_equal_to<int>() ) == digits.end() )
{
    return false;
}else
{
    return true;
}

}

int KaprekarsConstant(int num)
{
constexpr int kaprekarsConst = 6174;
constexpr int lengthRequirement = 4;

static int iteration = 0;

if(std::to_string(num).length() == lengthRequirement && isUnique(num))
{
    int difference = num;
    std::string sNum;

        while(difference != kaprekarsConst)
        {
            sNum = std::to_string(difference);

            std::sort(sNum.begin(),sNum.end(),std::greater<int>());
            int ascendNum = stoi(sNum);

            std::sort(sNum.begin(),sNum.end(),std::less<int>());
            int descendNum = stoi(sNum);

            difference = ascendNum - descendNum;

            ++iteration;
        }
}
return iteration;
}
\$\endgroup\$
  • \$\begingroup\$ Is your posted code indented as intended? (The easiest way to post code is to paste it into the question editor, highlight it, and press Ctrl-K to mark it as a code block.) \$\endgroup\$ – 200_success Jul 11 '18 at 6:20
  • \$\begingroup\$ I pressed four spaces to code block. Thanks for the info. \$\endgroup\$ – austingae Jul 11 '18 at 7:01
10
\$\begingroup\$

First and foremost, your toolset for programming needs a style formatter. Common formatters include clang-format and AStyle.


#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>

Get in the habit of organizing your headers. When you have a long list of them, nobody wants to search them linearly. I recommend organizing them into ascending groups of code quality, with each group sorted alphabetically.

  1. Prototype/Interface header for this implementation (if applicable).
  2. Other headers from the same project.
  3. Non-standard headers from non-popular vendors (Mnmlstc, CppIterTools)
  4. Non-standard headers from popular vendors (QT, Folly, EASTL, ABSL)
  5. Boost headers
  6. C++ Library headers (<iostream>, <vector>, <cstdint>)
  7. C Library headers.

Only include what you need. You don't need <iostream>.


// at least two digits must be distinct
bool isUnique(int num) {
  constexpr int numlength = 4;
  std::vector<int> digits;

  for (int i = 0; i < numlength; ++i) {
    int digit = num % 10;
    digits.push_back(digit);
    num /= 10;
  }

  // If digits are all equal return false.
  if (std::adjacent_find(digits.begin(), digits.end(),
                         std::not_equal_to<int>()) == digits.end()) {
    return false;
  } else {
    return true;
  }
}

The fact that you had to include a comment to describe what this function does should be a clue that you should pick a better name for this function.

Why does isUnique() care about the length of the number? A number length of 4 is an implementation detail of your Kaprekar calculation. isUnique should only be concerned with checking if there is a non-unique digit.

Don't be afraid to write more functions. Functions should be short and simple. You have two sections in this one function: int-to-char conversion and distinct element checking.

The expression in the if statement at the end generates a boolean. Instead of branching, just return the result of the expression.

bool hasNonUniqueChar(std::string const& str) {
  return std::adjacent_find(str.begin(), str.end(), std::not_equal_to())
      != str.end();
}

bool hasNonUniqueDigit(int num) {
  auto const digits = std::to_string(num);
  return hasNonUniqueChar(digits);
}

int KaprekarsConstant(int num) {

KaprekarsConstant is probably going to make people think this is a constant value being returned, not the number of iterations. Consider renaming the function appropriately.

  constexpr int kaprekarsConst = 6174;
  constexpr int lengthRequirement = 4;

Don't think you really need either of these. Kaprekar can be calculated for any number of digits. Comparing to a known result seems like cheating. What you should be calculating is the number of iterations to the point a cycle happens.

  static int iteration = 0;

Why static? If the callee wants an accumulation of all the iterations, they can add it up themselves.

  if (std::to_string(num).length() == lengthRequirement && isUnique(num)) {

You convert the number to a string here, then convert it again in isUnique. You are throwing away work you've already done.

    int difference = num;
    std::string sNum;

    while (difference != kaprekarsConst) {

Again, this is (a) cheating and (b) a problem. Again, you want to calculate values until you find a value you've previously encountered. For 3-digit and 4-digit values, they converge to one value and then infinitely repeats.

      sNum = std::to_string(difference);

I said previously that comparing to \$6174\$ was a problem. Consider the input \$2111\$.

$$2111 - 1112 = 999$$

Notice that \$999\$ is no longer a 4-digit number. That's an issue. Continuing,

$$999 - 999 = 0 \\ 0 - 0 = 0$$

See the problem with comparing to \$6174\$? We've converged to \$0\$ and are now stuck in an infinite loop. There are \$77\$ four-digit numbers that converge to \$0\$ if leading zeros are discarded. If we preserved those leading-zeros, as Kaprekar did in the original formulation, then

$$2111 - 1112 = 0999 \\ 9990 - 0999 = 8991 \\ 9981 - 1899 = 8082 \\ 8820 - 288 = 8532 \\ 8532 - 2358 = 6174 \\ 7641 - 1467 = 6174 $$

      std::sort(sNum.begin(), sNum.end(), std::greater<int>());
      int ascendNum = stoi(sNum);

Make sure you namespace qualify symbols and avoid using namespace std;.

      std::sort(sNum.begin(), sNum.end(), std::less<int>());

How about std::reverse?

\$\endgroup\$
  • \$\begingroup\$ Why put the C library headers last? I thought a.) They were generally eschewed in C++ b.) That by including them last they get final say on their implementation. \$\endgroup\$ – AGirlHasNoName Jul 11 '18 at 16:09
  • 1
    \$\begingroup\$ While they are eschewed, sometimes they are needed to write platform specific code. Those libraries often require transitive inclusion as they are not self-contained and that needs to be documented. Whether you include them first or last doesn't matter as once their included, that is the implementation. This is only a recommendation. By sorting groups from most specific (this prototype) to most general (this system), any dependency that relies on transitive includes are caught immediately. \$\endgroup\$ – Snowhawk Jul 11 '18 at 19:29
10
\$\begingroup\$

I'm assuming the indenting is cut and paste problems, but going through this:

#include <iostream>

You don't use iostream, so don't include it

#include <string>
#include <algorithm>
#include <vector>
#include <functional>

I'd recommend you sorted the #includes. It makes it a lot easier to find things if you have a lot of them and avoids a certain class of problem with merging file changes

//at least two digits must be distinct
bool isUnique(int num)

Given the comment, isUnique is not a good name. It's looking for 2 distinct digits, not - well, it's not looking for anything unique. contains_2_distinct_digits perhaps?

{
    constexpr int numlength = 4;
    std::vector<int> digits;

    for(int i = 0; i < numlength ; ++i)

for is not a function call. It's a keyword. Put a space after it.

    {
        int digit = num%10;
        digits.push_back(digit);
        num /= 10;
    }

The 4 doesn't really belong here (see below).

    //If digits are all equal return false.
    if ( std::adjacent_find( digits.begin(), digits.end(), std::not_equal_to<int>() ) == digits.end() )

I wouldn't have the space after the ( there.

This code is somewhat inconsistent with the use of spaces. You have a space after commas and brackets here, but not further down. Pick a style and stick to it.

    {
        return false;
    }else

I'd recommend against dangling the else off the }. Either put it on its own line or use '} else {'

    {
        return true;
    }

You don't really need that if. Just

    return std::adjacent_find(digits.begin(), digits.end(), std::not_equal_to<int>()) != digits.end();

}

int KaprekarsConstant(int num)

TBH I'd expect a name like that to return the constant (actually I wouldn't expect with that name it'd even be a function). This isn't returning that. It's returning how many iterations it takes to stabilise.

{
    constexpr int kaprekarsConst = 6174;
    constexpr int lengthRequirement = 4;

You have this 4 here and you use 4 for the passing in isUnique. This is fragile, should you ever want to deal with a similar property for numbers with digits other than 4.

    static int iteration = 0;

There's no need for this to be static

    if(std::to_string(num).length() == lengthRequirement && isUnique(num))

if is not a function call

    {
        int difference = num;
        std::string sNum;

sNum only needs to exist in the while loop, so put it there. You should attempt to declare variables at the point of use where possible.

            while(difference != kaprekarsConst)

while is not a function call. Put a space after it.

If you wanted to generalise this to n digits, I wouldn't define kaprekarsConst. You'd just check if the newly evaluated difference matched the previous difference.

            {
                sNum = std::to_string(difference);

                std::sort(sNum.begin(),sNum.end(),std::greater<int>());
                int ascendNum = stoi(sNum);

                std::sort(sNum.begin(),sNum.end(),std::less<int>());
                int descendNum = stoi(sNum);

As has been suggested, this is already sorted, so you could just reverse it.

                difference = ascendNum - descendNum;

                ++iteration;
            }
    }
    return iteration;
}
\$\endgroup\$
  • \$\begingroup\$ Any specific reason for suggesting snake_case for the function name rather than sticking with camelCase? \$\endgroup\$ – Toivo Säwén Jul 11 '18 at 11:25
  • 1
    \$\begingroup\$ @ToivoSäwén err. well (a) the standard library uses snake_case, and (b) I personally find it much easier to read. My brain keeps stopping at the capital letters. \$\endgroup\$ – Tom Tanner Jul 12 '18 at 9:41
6
\$\begingroup\$

Your code's unusual indentation makes it a bit harder to read than it should, but I believe it was a copy-and-paste problem. Apart from that, your code is quite good, but perfectible.

Consistency is a virtue

I don't understand why you turn your number into a vector in is_unique while you use std::to_string for the same purpose (iterating over digits) in KaprekarsConstant. Be consistent, or the reader will wonder why you chose different methods. In the same way, you have the same constant known as numlength and lengthRequirement (different names and, worse, different cases).

It's hard to read code written by someone else, so make it as easy as possible by setting conventions and sticking to it.

Explore <algorithm> further

I like that you chose std::adjacent_find in combination with std::not_equal_to. It's the most efficient here. That said, for a 4-digit sequence, you could also have chosen std::unique, since it is more expressive and you won't incur a real performance loss:

auto duplicates = std::unique(str.begin(), str.end());
if (std::distance(str.begin(), duplicates) > 1) return true;

In the other function, rather than sorting twice and specifying sorting order, I'd have chosen to first sort, then reverse. It's slightly more efficient and less verbose:

std::sort(str.begin(), str.end());
auto rhs = std::stoi(str);
std::reverse(str.begin(), str.end());
auto lhs = std::stoi(str);

Handling unexpected input

If I call your KaprekarsConstant function with 6174, it will return 0; but if I call it with 1111, or 654321, it will return 0 also. You don't make any difference between a valid number and an invalid one. That's a problem you need to address.

There are many possibilities to do it. The first question you need to ask yourself is whether you expect the user to test the number first (if (is_valid_kaprekar_number(n)) std::cout << count_kaprekar_iterations(n))*. In that case, you shouldn't test it again inside count_kaprekar_iterations. But that seems fragile. If not, you need to find a way to report to the client that the number is invalid: returning -1 or another error constant is a bit old-fashioned, throwing an exception is rather unwieldy, so I would suggest to use std::optional: it can represent success or failure and, in the case of success, contain the return value.

Miscellaneous

  • don't make iterations static, or initialize it back to 0 at each function call. But don't make it static.

Complete working example

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

bool is_valid_kaprekar_number(std::string str_repr) {
    if (str_repr.size() != 4) return false;
    auto duplicates = std::unique(str_repr.begin(), str_repr.end());
    return std::distance(str_repr.begin(), duplicates) > 1;
}

std::optional<int> count_kaprekar_iterations(int n) {
    constexpr int kaprekar_constant = 6174;
    std::string str_repr = std::to_string(n);
    if (!is_valid_kaprekar_number(str_repr)) return {};
    int iterations = 0;
    while (std::stoi(str_repr) != kaprekar_constant) {
        std::sort(str_repr.begin(), str_repr.end());
        int rhs = std::stoi(str_repr);
        std::reverse(str_repr.begin(), str_repr.end());
        int lhs = std::stoi(str_repr);
        str_repr = std::to_string(lhs-rhs);
        ++iterations;
    }
    return iterations;
}

int main() {
    auto input = 8452;
    auto result = count_kaprekar_iterations(input);
    if (result) std::cout << "number of iteration is: " << *result;
    else std::cout << input << " isn't a valid number"; 
}

* I took the liberty to change function names, because yours aren't the most expressive

\$\endgroup\$
3
\$\begingroup\$
  • KaprekarsConstant is a weird name for a function. I'd expect it to be a constant.

  • isUnique doesn't really tell what it does, what property is unique of a number? has_unique_digits might be a better name.

  • Also, isUnique returns the opposite of the expected result (isUnique(1111) == false).

  • Is there a specific reason for all the conversions from int to std::string and back, and to std::vector<int> for isUnique, when one representation would suffice?

  • The second call to std::sort could be replaced with std::reverse

  • Any specific reason that kaprekarsConstant is restricted to 4-digit numbers only? "Kaprekars Routine" works on all numbers, after all.

\$\endgroup\$
  • \$\begingroup\$ For your third point, 1111 is suppose to return false. For your fifth point, is std::reverse faster than std::sort? For your sixth point, KaprekarsConstant is restricted to only four digits. I'll take a look on your fourth point. \$\endgroup\$ – austingae Jul 11 '18 at 7:41
  • \$\begingroup\$ @austingae: For KaprekarsConstants logic to work, yes. But the function's name isUnique doesn't indicate that. \$\endgroup\$ – hoffmale Jul 11 '18 at 7:47
  • 2
    \$\begingroup\$ @austingae, I think the point is that isUnique() is poorly named for what it does - it's actually testing that there are at least two distinct digits, and so should be named as such (or the return value (and its use) inverted to match the name). \$\endgroup\$ – Toby Speight Jul 11 '18 at 7:48

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.