5
\$\begingroup\$

I have rolled a simple program for controlling a sliding tile puzzle via command line. I would like to hear comments on how to make it more idiomatic C++17 and efficient. Here is my code:

SlidingTilePuzzleNode.hpp

#pragma once
#include <ostream>
#include <stdexcept>
#include <unordered_map>
#include <vector>

class ZeroTileOutsideException : public std::logic_error {
public:
    ZeroTileOutsideException(std::string& error_message) 
    : 
        std::logic_error(error_message)
    {

    }
};

class SlidingTilePuzzleNode;

class SlidingTilePuzzleNodeRowSelector
{
public:
    SlidingTilePuzzleNodeRowSelector() = default;
    SlidingTilePuzzleNodeRowSelector(
        SlidingTilePuzzleNode* node,
        std::size_t start_index);
    int& operator[](std::size_t x);

private:
    SlidingTilePuzzleNode* m_node;
    std::size_t m_offset_index;
};

class SlidingTilePuzzleNode
{
public:
    SlidingTilePuzzleNode(std::size_t width, std::size_t height);
    SlidingTilePuzzleNode(const SlidingTilePuzzleNode& other);
    SlidingTilePuzzleNode& operator=(const SlidingTilePuzzleNode& other);
    SlidingTilePuzzleNode& operator=(SlidingTilePuzzleNode&& other);
    //SlidingTilePuzzleNode(SlidingTilePuzzleNode&& other);
    ~SlidingTilePuzzleNode();

    SlidingTilePuzzleNode slideUp();
    SlidingTilePuzzleNode slideDown();
    SlidingTilePuzzleNode slideLeft();
    SlidingTilePuzzleNode slideRight();

    std::size_t getWidth()  const { return m_width; }
    std::size_t getHeight() const { return m_height;  };

    SlidingTilePuzzleNodeRowSelector& operator[](size_t y);

    friend std::ostream& operator<<(
        std::ostream& out,
        SlidingTilePuzzleNode & node);

private:

    std::vector<int> m_state;
    std::unordered_map<std::size_t, SlidingTilePuzzleNodeRowSelector> m_row_map;
    std::size_t m_width;
    std::size_t m_height;
    std::size_t m_zero_tile_x;
    std::size_t m_zero_tile_y;

    // Let ...RowSelector access m_state:
    friend class SlidingTilePuzzleNodeRowSelector;
    // Check that a slide is possible:
    void checkOnSlideUp   () const;
    void checkOnSlideDown () const;
    void checkOnSlideLeft () const;
    void checkOnSlideRight() const;

    inline void setZeroTileCoordinates(std::size_t x, std::size_t y);
};

SlidingTilePuzzleNode.cpp

#include "SlidingTilePuzzleNode.hpp"
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <ios>
#include <iostream>
#include <ostream>
#include <string>

void SlidingTilePuzzleNode::checkOnSlideUp() const 
{
    if (m_zero_tile_y == 0) {
        ZeroTileOutsideException exception(std::string("'m_zero_tile_y == 0' upon slideUp"));
        throw exception;
    }
}

void SlidingTilePuzzleNode::checkOnSlideDown() const
{
    if (m_zero_tile_y == m_height - 1) {
        ZeroTileOutsideException exception(std::string("'m_zero_tile_y == m_height - 1' upon slideDown"));
        throw exception;
    }
}

void SlidingTilePuzzleNode::checkOnSlideLeft() const 
{
    if (m_zero_tile_x == 0) {
        ZeroTileOutsideException exception(
            std::string("'m_zero_tile_x == 0' upon slideLeft"));
        throw exception;
    }
}

void SlidingTilePuzzleNode::checkOnSlideRight() const 
{
    if (m_zero_tile_x == m_width - 1) {
        ZeroTileOutsideException exception(
            std::string("'m_zero_tile_x == m_width - 1' upon slideRight"));
        throw exception;
    }
}

// Initial constructor building the solved slide puzzle:
SlidingTilePuzzleNode::SlidingTilePuzzleNode(std::size_t width,
                                             std::size_t height) 
    : 
    m_width(width),
    m_height(height),
    m_zero_tile_x(width - 1),
    m_zero_tile_y(height - 1)
{
    // Copy the state:
    m_state.resize(m_width * m_height);
    std::size_t n{};
    std::generate(m_state.begin(), m_state.end(), [n = 1]() mutable {
        return n++; 
    });

    // Deal with the empty tile:
    m_state[width * height - 1] = 0;

    // Build the row index:
    for (std::size_t y = 0; y < m_height; y++) {
        SlidingTilePuzzleNodeRowSelector row_selector(this, y * width);
        m_row_map[y] = row_selector;
    }
}

// Copy constructor.
SlidingTilePuzzleNode::SlidingTilePuzzleNode(const SlidingTilePuzzleNode& other) 
{
    // Copy the easy stuff.
    this->m_height      = other.m_height;
    this->m_width       = other.m_width;
    this->m_zero_tile_x = other.m_zero_tile_x;
    this->m_zero_tile_y = other.m_zero_tile_y;
    this->m_state       = other.m_state;

    std::size_t y = 0;

    for (auto const& entry : other.m_row_map) {
        SlidingTilePuzzleNodeRowSelector row_selector(this, y);
        this->m_row_map[entry.first] = row_selector;
        y += m_width;
    }
}

// Copy assignment.
SlidingTilePuzzleNode& SlidingTilePuzzleNode::operator=(const SlidingTilePuzzleNode& other)
{
    this->m_height      = other.m_height;
    this->m_width       = other.m_width;
    this->m_zero_tile_x = other.m_zero_tile_x;
    this->m_zero_tile_y = other.m_zero_tile_y;
    this->m_state       = other.m_state;
    this->m_row_map     = other.m_row_map;

    // Correct the map values to row selectors of this tile:
    for (auto& entry : m_row_map) {
        SlidingTilePuzzleNodeRowSelector row_selector(this, entry.first);
        entry.second = row_selector;
    }

    return *this;
}

// Move assignment.
SlidingTilePuzzleNode& SlidingTilePuzzleNode::operator=(SlidingTilePuzzleNode&& other)
{
    m_height      = other.m_height;
    m_width       = other.m_width;
    m_zero_tile_x = other.m_zero_tile_x;
    m_zero_tile_y = other.m_zero_tile_y;
    m_state       = std::move(other.m_state);
    m_row_map     = std::move(other.m_row_map);

    std::size_t y = 0;

    for (auto& entry : m_row_map) {
        SlidingTilePuzzleNodeRowSelector row_selector(this, y);
        entry.second = row_selector;
        y += m_width;
    }

    return *this;
}

SlidingTilePuzzleNode::~SlidingTilePuzzleNode() = default;

SlidingTilePuzzleNode SlidingTilePuzzleNode::slideUp()
{
    checkOnSlideUp();
    SlidingTilePuzzleNode node(*this);
    auto x2 = m_zero_tile_x;
    auto y2 = m_zero_tile_y - 1;
    std::swap(node[m_zero_tile_y][m_zero_tile_x], node[y2][x2]);
    node.setZeroTileCoordinates(x2, y2);
    return node;
}

SlidingTilePuzzleNode SlidingTilePuzzleNode::slideDown()
{
    checkOnSlideDown();
    SlidingTilePuzzleNode node(*this);
    auto x2 = m_zero_tile_x;
    auto y2 = m_zero_tile_y + 1;
    std::swap(node[m_zero_tile_y][m_zero_tile_x], node[y2][x2]);
    node.setZeroTileCoordinates(x2, y2);
    return node;
}

SlidingTilePuzzleNode SlidingTilePuzzleNode::slideLeft() 
{
    checkOnSlideLeft();
    SlidingTilePuzzleNode node(*this);
    auto x2 = m_zero_tile_x - 1;
    auto y2 = m_zero_tile_y;
    std::swap(node[m_zero_tile_y][m_zero_tile_x], node[y2][x2]);
    node.setZeroTileCoordinates(x2, y2);
    return node;
}

SlidingTilePuzzleNode SlidingTilePuzzleNode::slideRight()
{
    checkOnSlideRight();
    SlidingTilePuzzleNode node(*this);
    auto x2 = m_zero_tile_x + 1;
    auto y2 = m_zero_tile_y;
    std::swap(node[m_zero_tile_y][m_zero_tile_x], node[y2][x2]);
    node.setZeroTileCoordinates(x2, y2);
    return node;
}

SlidingTilePuzzleNodeRowSelector::SlidingTilePuzzleNodeRowSelector(
    SlidingTilePuzzleNode* node,
    std::size_t start_index) 
    :
    m_node(node),
    m_offset_index(start_index) 
{

}

int& SlidingTilePuzzleNodeRowSelector::operator[](std::size_t x) 
{
    return m_node->m_state.at(m_offset_index + x);
}

SlidingTilePuzzleNodeRowSelector& SlidingTilePuzzleNode::operator[](std::size_t y) 
{
    return m_row_map[y];
}

std::ostream& operator<<(std::ostream& out, SlidingTilePuzzleNode& node) 
{
    const auto max_tile_number = node.getHeight() * node.getWidth() - 1;
    const auto max_tile_number_length = 
        static_cast<std::size_t>(
            std::floor(std::log10(max_tile_number)) + 1);

    for (std::size_t y = 0; y < node.getHeight(); y++) {
        if (y > 0) {
            out << '\n';
        }

        for (std::size_t x = 0; x < node.getWidth(); x++) {
            if (x > 0) {
                out << " ";
            }

            out << std::setfill(' ')
                << std::setw(max_tile_number_length) 
                << node[y][x];
        }
    }

    return out;
}

inline void SlidingTilePuzzleNode::setZeroTileCoordinates(std::size_t x, std::size_t y)
{
    m_zero_tile_x = x;
    m_zero_tile_y = y;
}

main.cpp

#include "SlidingTilePuzzleNode.hpp"
#include <iostream>
#include <sstream>

static SlidingTilePuzzleNode createSourceNode(
    std::size_t width, 
    std::size_t height)
{
    SlidingTilePuzzleNode node(width, height);
    int number = 1;

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            node[y][x] = number++;
        }
    }

    node[node.getHeight() - 1][node.getWidth() - 1] = 0;
    return node;
}

int main()
{
    SlidingTilePuzzleNode node(4, 4);
    std::string bar(11, '-');
    try {
        while (true) {
            std::cout 
                << node
                << "\n"
                << bar
                << '\n';

            char choice = static_cast<char>(std::cin.get());
            // Ignore all the leftover chars:
            std::cin.clear();
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

            switch (choice) {   
            case 'u':
                node = node.slideUp();
                break;

            case 'd':
                node = node.slideDown();
                break;

            case 'l':
                node = node.slideLeft();
                break;

            case 'r':
                node = node.slideRight();
                break;

            case 'q':
                return 0;
            }
        }
    }
    catch (ZeroTileOutsideException& ex) {
        std::cerr << "Can't move outside of the box.\n";
    }

    return 0;
}
\$\endgroup\$
3
  • \$\begingroup\$ ZeroTileOutsideException exception(std::string("'m_zero_tile_y == m_height - 1' upon slideDown")); this line looks weird. Are you using MSVC? This is their non-standard extension that allows non-lvalues to be passed as lvalue-references. Perhaps you wanted to take string in the constructor by const reference? \$\endgroup\$ Feb 9, 2019 at 10:02
  • 1
    \$\begingroup\$ @Incomputable Yes, I wrote this using Visual Studio 2017. \$\endgroup\$
    – coderodde
    Feb 9, 2019 at 10:06
  • \$\begingroup\$ @coderodde Just use ZeroTileOutsideException exception("'m_zero_tile_y == m_height - 1' upon slideDown");. \$\endgroup\$
    – L. F.
    Feb 15, 2019 at 0:54

1 Answer 1

3
\$\begingroup\$

Here are some suggestions that may help you improve your code.

Be careful with signed and unsigned

In a few places, the code compares an int x or 'y' with std::size_t values width and height. For consistency, it would be better to declare x and y also as std::size_t. Even better, see the next suggestion.

Eliminate unused code

The createSourceNode function is unused and can be eliminated. Code that isn't used doesn't need to be written or maintained, which leads to better overall code quality.

Write portable code

As noted in the comments:

Are you using MSVC? This is their non-standard extension that allows non-lvalues to be passed as lvalue-references.

This is very easy to fix by changing the constructor. Instead of this:

ZeroTileOutsideException(std::string& error_message)

use this:

ZeroTileOutsideException(std::string error_message) 

Now it complies with standards, and should still work just fine in MSVC. By avoiding non-portable extensions, you make your code easier to port and maintain for years to come.

Eliminate unused variables

The variable n in the constructor for SlidingTilePuzzleNode is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.

Use const where practical

Generally, this code does a good job of using const, but it should also be applied to the ostream<< operator as in:

std::ostream& operator<<(std::ostream& out, const SlidingTilePuzzleNode& node) 

This will require some changes to the code implementing it, but really should be possible to print the node without altering it. That also leads directly to the next suggestion.

Provide const versions of access methods

In addtion to the two operator[] functions you already have, I'd suggest adding these:

int SlidingTilePuzzleNodeRowSelector::operator[](std::size_t x) const
{
        return m_node->m_state.at(m_offset_index + x);
}

const SlidingTilePuzzleNodeRowSelector& SlidingTilePuzzleNode::operator[](std::size_t y) const
{
        return m_row_map.at(y);
}

This allows you to use the same handy notation in a const-correct way.

Rethink the class interface

It's generall a bad idea to provide direct access to internal class data structures, and especially bad in a public interface. The non-const versions of the functions mentioned above should be private, for instance. Another useful thing to do would be to make SlidingTilePuzzleNodeRowSelector a private class inside SlidingTilePuzzleNode. See C.9 for more detail on that principle.

Don't use an exception for unexceptional events

Users do all kinds of interesting things when interacting with computers, and in this case, it's not at all exceptional that a user would attempt an invalid move. For that reason, I would suggest instead that a return value from the various slide methods indicating success or failure would make more sense.

Check the logic

I think there's is a problem with the logic of the moves. If we start with this:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0
-----------

And then mov "u" (for Up), the reult is this:

u
 5  6  7  4
 1  2  3  8
13 14 15  0
 9 10 11 12
-----------

That's not typically how sliding puzzles actually work. If yours is intended to work this way, a bit more documentation for the user or as comments in the code at least, might be needed.

\$\endgroup\$

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.