Demonstration of ChessBoard Traveling (CoderByte)

Question

Problem

Have the function ChessboardTraveling(str) read str which will be a string consisting of the location of a space on a standard 8x8 chessboard with no pieces on the board along with another space on the chessboard.

The structure of str will be the following:

\$(x,y)(a,b)\$ where \$(x, y)\$ represents the position you are currently on with \$x\$ and \$y\$ ranging from 1 to 8 and \$(a, b)\$ represents some other space on the chessboard with \$a\$ and \$b\$ also ranging from 1 to 8 where \$a > x\$ and \$b > y\$. Your program should determine how many ways there are of traveling from \$(x, y)\$ on the board to \$(a, b)\$ moving only up and to the right.

Example: if str is \$(1,1)(2, 2)\$ then your program should output 2 because there are only two possible ways to travel from space \$(1, 1)\$ on a chessboard to space \$(2, 2)\$ while making only moves up and to the right.

Are there any improvements I can make?

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

std::string delete_Punctuation(std::string& str)
{
    std::string noPunctString = "";

    str.insert(str.length()/2," ");

    for (auto character : str)
    {
        if (!ispunct(character))
        {
            noPunctString.push_back(character);
        }
    }

    return str = noPunctString;
}

bool check_If_PointXY_Is_Less_Than_PointAB(std::vector<int> v)
{
     return (v.at(2) > v.at(0) && v.at(3) > v.at(1));
}

long long int find_Factorial(unsigned int n)
{
    if (n == 0)
    {
       return 1;
    }

    return n * find_Factorial(n - 1);
}

int number_Of_Steps(std::string& str)
{
    str = delete_Punctuation( str );

    std::istringstream iss( str );

    std::vector<int> coll((std::istream_iterator<int>( iss )),std::istream_iterator<int>());

    int steps = 0;

    if (check_If_PointXY_Is_Less_Than_PointAB(coll))
    {
        int xDistance = coll.at(2) - coll.at(0);
        int yDistance = coll.at(3) - coll.at(1);

        int totalDistance = xDistance + yDistance;

        //combination formula
        steps = find_Factorial(totalDistance)/(find_Factorial(xDistance) * (find_Factorial(totalDistance - xDistance)));
    }

    return steps;
}

Answer 1

I see some things that may help you improve your code.

Fix the input parsing

The idea is sound but the implementation is flawed. Instead of the complex method currently used, I'd recommend using this single function:

std::replace_if(str.begin(), str.end(), 
        [](char ch){ return !std::isdigit(ch); }, ' ');

Using this, we're guaranteed that the string will contain only spaces and digits.

Use objects

I'd suggest that one could make good use of a Point2D object to make calculations very clear:

struct Point2D {
    int x = 0;
    int y = 0;
    int dx(const Point2D &other) const {
        return x - other.x;
    }
    int dy(const Point2D &other) const {
        return y - other.y;
    }
    friend std::istream& operator>>(std::istream &in, Point2D &p) {
        return in >> p.x >> p.y;
    }
};

Reduce the numerical range for calculations

The current code uses a generic factorial which boils down to $$\frac{(dx + dy)!}{dx! dy!}$$ The maximum for \$dx\$ or \$dy\$ is 7, so the largest factorial required is \$14! = 87178291200\$. ... Or is it? In fact, we could consider instead how to generically calculate $$\frac{n!}{m!}$$ with \$m < n\$. A simple way to do this is like so:

constexpr unsigned factDelta(unsigned n, unsigned m) {
    return n > m ? n * factDelta(n-1, m) : 1;
}

And the ordinary factorial function could be expressed as:

constexpr unsigned fact(unsigned n) {
    return factDelta(n, 1);
}

This can reduce the range of the multiplications somewhat, especially if we always choose the larger of \$dx\$ or \$dy\$ to divide. This means that the return value will always be \$<= 7! = 5040\$ which easily fits into an unsigned. Note, however, that these functions will overflow if they're given numbers outside that range. For that reason, I'd recommend making them static functions and/or doing range checking.

Don't alter passed parameters

The current number_Of_Steps() routine takes a reference to a string and then alters the string. It's not strictly wrong, but it's probably not the best interface design. I would not expect that the passed string was altered. Two ways to address this would be to pass a const reference or to simply declare the argument as std::string str which makes a local copy. Because of the need to alter the string (by removing punctuation), I'd recommend the latter approach.

A worked example

Here's an alternative function that uses the functions and objects described above:

int alt(std::string str) {
    std::replace_if(str.begin(), str.end(), 
            [](char ch){ return !std::isdigit(ch); }, ' ');
    std::istringstream in(str);
    Point2D a; 
    Point2D b;
    in >> a >> b;
    int dx = b.dx(a);
    int dy = b.dy(a);
    if (dx <= 0 || dy <= 0) {
        return 0;
    }
    int m = dx + dy;
    if (dy > dx) {
        std::swap(dx, dy);
    }
    return factDelta(m, dx) / fact(dy);
}

Answer 2

My Test Setup:

• Microsoft Visual Studio 2017
• C++17
• Optimizations disabled

At a Glance

1. number_Of_Steps should take a const std::string&. It is best practice to only give as much access to data as needed, and no more. As such, the return statement in delete_Punctuation should just return noPunctString, instead of assigning str = noPunctString and then returning it. Then just create a new string in number_Of_Steps and assign it to delete_Punctuation(str)

2. In delete_Punctuation, std::string::push_back(char) is a time consuming process. Because you're expecting single digit inputs anyway, just allocate a struct of four integers. Better yet, allocate 4 unsigned chars. They will be able to store single digit numbers at the expense of only 1 byte instead of 4 (depending on system specification ofcourse)

3. If you decide to create a struct, check_If_PointXY_Is_Less_Than_PointAB won't have to take a vector of integers anymore, and instead an easy to read struct object. This will turn return (v.at(2) > v.at(0) && v.at(3) > v.at(1)); into return v.a > v.x && v.b > v.y;.

4. find_Factorial should probably return an unsigned long long int because there is no way it can be negative. Plus you will be able to represent a larger number without overflowing.

5. In number_Of_Steps, variable steps should be an unsigned long long int because find_Factorial returns that. Otherwise you risk truncation. Although in your specific case, it doesn't need to be.

   • As a result, number_Of_Steps should return an unsigned long long int

6. Prefer brace initialization over the standard equal sign. This answer on StackOverflow explains it quite well, but basically it is a more safe way to initialize objects.

During My Testing

Input used: (1,1)(2,2)

---

1. delete_Punctuation(std::string&) actually produces string 11 22, and as a result your istringstream interprets only 2 numbers (11 and 22) instead of 4. This is a problem because check_If_PointXY_Is_Less_Than_PointAB(std::vector<int>) expects the vector to have at least 4 inputs.

2. Majority of the time, you never want to pass a container by value, so in your case check_If_PointXY_Is_Less_Than_PointAB should take a const std::vector<int>&

3. I would honestly just scrap the whole vector thing in general, and use a struct with 4 values as my x, y, a, and b, because using an std::istream_iterator<int>(iss) is far less efficient in this case.

Except the input, everything else seemed to work quite well.

User Input

The #1 rule of programming: All user input is evil.

For example purposes, say that your std::istringstream interpreted 4 integers. What if the characters in that input string happened to be a carriage returns, and end of file characters, or a solid blocks? You wouldn't get the correct result, even if the stream throws no exceptions. So you always have to check.

Luckily for you, you specified how you want your input to be, and any competent user should oblige by it.

In such a simple program as yours, I would:

• remove all the spaces within the input string.
• check whether the string's length is equal to 10, because (x,y)(a,b) is 10 characters long.
  • if not, notify the user and ask them to input again or exit.
• I would then use std::isdigit to verify that str.at(1) your x, str.at(3) your y, str.at(5) your a, and str.at(7) your b are numerical.
• As I am verifying, I'm placing those numbers into a struct containing x, y, a, b
• If all my input is successful, I proceed calculating and returning the result to the user.

Style & Preprocessor

Nothing to much to say here, but do keep in mind the length of function and variable names. Name them something short and concise, but descriptive. For example, check_If_PointXY_Is_Less_Than_PointAB could become is_XY_Less, because in your case, that clearly conveys the purpose of the function.

Remove unnecessary headers (in your case <functional> and <iostream>), but do include the ones you need (like <cctypes> for std::ispunct and std::isdigit).