Video Game & Web Developer

Connect

Print Numbers in a Spiral Recursively in C++

In my last post I talked about printing numbers in a spiral in C++. The way I implemented the solution to the problem at the time was to create a n x n matrix of integers and one by one fill it with the numbers going from the center towards the perimeters until all cells were filled. In this post I have implemented another solution to the same problem using recursion. The idea came from reading this post.

If we take a closer look at how the numbers are printed we will be able to observe a pattern.

Let’s look at what happens when we increase n one by one.

When n = 1 the output is as follows:

1

When n = 2:

1 2
4 3

When n = 3:

7 8 9
6 1 2
5 4 3

When n = 4:

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

We deduce the pattern to be:

When n is even:

P C
C C

When n is odd:

C C
C P

This means that when n is even we add a new column to the right of the previous matrix and a new row at the bottom. The new column starts with the number (n – 1)(n – 1) + 1 and increases as we go down. The final row goes from n x to (n – 1)(n – 1) + n in that order.

When n is odd we a add a new column to the left of the previous matrix and a new row at the top. The new column has the numbers between (n - 1)(n - 1) + 1 and increases as we go up. The final row goes from (n – 1)(n – 1) + n to n x n.

An interesting aspect of this is the fact that when I compared the running time for this algorithm against that of the iterative one, I found out that when I tested it for n = 1000 the recursive algorithm took 1650 ms in average compared to 110 ms the iterative algorithm took to run. That means the iterative solution is 15 times faster than the recursive one!

The implementation in C++:

/*******************************************************************
* Title: Print First n^2 Numbers in a Spiral
* Description: Prints the first n^2 numbers in a spiral recursively
* Programmer: Carlos F. Perea
* Date: August 29th, 2013
*******************************************************************/
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <time.h>
 
#define SEPARATOR " "
 
using namespace std;
 
/**
* Converts an integer to a string
* @param    integer
* @return   string
*/
string integerToString(int integer)
{
    ostringstream outputStream;
    outputStream << integer;
    return outputStream.str();
}
 
/**
* Returns the difference in milliseconds of two points in time
* @param    clock_t     start time
* @param    clock_t     end time
* @return   difference
*/
double diffclock(clock_t clock1, clock_t clock2) 
{ 
    double diffticks = clock1 - clock2;
    double diffms = (diffticks * 1000) / CLOCKS_PER_SEC;
    return diffms;
} 
 
/**
* Builds a vector of strings representing numbers in a spiral
* @param    n
* @return   vector<string>  Vector containing each line of the output
*/
vector<string> buildSpiral(int n)
{
    vector<string> result;
    // return empty if n is equal or less than 0
    if (n <= 0)
        return result;
    // if n is 1 then just add the 1
    if (n == 1)
    {
        result.push_back(integerToString(1) + SEPARATOR);
        return result;    
    }
    // determine whether n is even or odd
    bool isEven;
    (n % 2 == 0) ? isEven = true : isEven = false;
    // the first new element
    int count = (n - 1)*(n - 1) + 1;
    // the last element
    int limit = n * n;
    // build the spiral for n - 1
    result = buildSpiral(n - 1);
    if (isEven)
    {
        // add elements to the right of the matrix (creating the new column)
        // elements increase from top to bottom
        for (int i = 0; i < result.size(); ++i)
        {
            result.at(i) += integerToString(count) + SEPARATOR;
            ++count;
        }
        // create the new row of elements
        string finalString = "";
        int remaining = limit - count;
        while (remaining >= 0)
        {
            finalString += integerToString(count + remaining) + SEPARATOR;
            --remaining;
        }
        // add it to the end of the matrix
        result.push_back(finalString);
    }
    else
    {
        // add elements to the left of the matrix (creating the new column)
        // elements increase from bottom to top
        for (int i = result.size() - 1; i >= 0; --i)
        {
            result.at(i) = integerToString(count) + SEPARATOR + result.at(i);
            ++count;
        }
        // create the new row of elements
        string finalString = "";
        while (count <= limit)
        {
            finalString += integerToString(count) + SEPARATOR;
            ++count;
        }
        // add it to the beginning of the matrix
        result.insert(result.begin(), finalString);
    }
    return result;
}
 
/**
* Prints the vector of strings
* @param    vector<string>
* @return   void
*/
void print(vector<string> list)
{
    for (int i = 0; i < list.size(); ++i)
    {
        cout << list.at(i) << endl;
    }
}
 
/**
* POINT OF ENTRY
*/
int main()
{
    int n = 1000;
    clock_t begin=clock();
    vector<string> matrix = buildSpiral(n);
    clock_t end=clock();
    cout << "Time elapsed: " << double(diffclock(end, begin)) << " ms"<< endl;
    print(matrix);
    return 0;
}
0 Comments ,

Print Numbers in a Spiral in C++

I saw this problem and wanted to implement a possible solution to it. The basic problem is given a number n, print numbers 1 through n^2 in a spiral starting from the center and moving outwards clock-wise.
The end result should look like this:

Spiral C++
I chose to implement the solution with a n x n matrix. Although this solution has a time and spatial complexity of O(n^2), the solution is pretty straight forward and easy to understand. We start by selecting the middle of the matrix and placing the first number in that cell. We achieve the spiraling traversal by having a variable named direction that indicates to us which direction we are going. If for example we’re going left and the cell on top is empty (0) then we change direction and starting going up. If our direction is right, and the cell on the bottom is empty (0) we change direction and start moving down. This process is done until we reach the number n^2.

Implementation:

/*******************************************************************
* Title: Print First n^2 Numbers in a Spiral
* Description: Prints the first n^2 numbers in a spiral
* Programmer: Carlos F. Perea
* Date: August 25th, 2013
*******************************************************************/
#include <iostream>
#include <stdlib.h> 
#include <vector>
#include <string>
 
#define LEFT    0
#define RIGHT   1
#define UP      2
#define DOWN    3
 
using namespace std;
 
/**
* Creates a nxn matrix
* @param    n   Integer
* @return   Matrix
*/
vector<vector<int> > createMatrix(int n)
{
    vector<vector<int> > matrix;
    for (int i = 0; i < n; ++i)
    {
        vector<int> row;
        for (int j = 0; j < n; ++j)
        {
            row.push_back(0);
        }
        matrix.push_back(row);
    }
    return matrix;
}
 
/**
* Returns the number of digits in a number
* @param    n   Integer
* @return   Number of digits
*/
int numberOfDigits(int n)
{
    int digits = 0;
    while (n > 0)
    {
        n = n / 10;
        ++digits;
    }
    return digits;
}
 
/**
* Checks if a string is a number
* @param    string
* @return   True if the string is a positive number, false otherwise
*/
bool isNumber(string s)
{
    for (int i = 0; i < s.size(); ++i)
    {
        if (!isdigit(s.at(i)))
            return false;
    }
    return true;
}
 
/**
* Prints the first n^2 numbers in a spiral from the center out in clock-wise rotation
* @param    n   Integer
* @return   void
*/
void printSpiral(int n)
{
    if (n <= 0)
        return;
 
    int n2 = n * n;
    int size = n;
    // check whether this number is even
    // if it is, then make the table 1 row and column bigger so that all numbers fit
    if (n % 2 == 0)
        size = n + 1;
 
    vector<vector<int> > matrix = createMatrix(size);
    int direction = RIGHT;
    int x = (size - 1) / 2;
    int y = x;
    int counter = 1;
    // start the first and second element
    matrix.at(y).at(x) = counter;
    ++counter;
    if (counter <= n2)
    {
        matrix.at(y).at(x + 1) = counter;
        ++x;
        ++counter;
    }
    while (counter <= n2)
    {
        switch (direction)
        {
            case LEFT:
            {
                // check if the element on top is empty
                if (y - 1 >= 0 && matrix.at(y - 1).at(x) == 0)
                {
                    direction = UP;
                    matrix.at(y - 1).at(x) = counter;
                    --y;
                }
                // check if we are still within bounds
                else if (x - 1 >= 0)
                {
                    matrix.at(y).at(x - 1) = counter;
                    --x;
                }
                else
                    return;
                break;
            }
            case RIGHT:
            {
                // check if the element on bottom is empty
                if (y + 1 <= size - 1 && matrix.at(y + 1).at(x) == 0)
                {
                    direction = DOWN;
                    matrix.at(y + 1).at(x) = counter;
                    ++y;
                }
                // check if we are still within bounds
                else if (x + 1 <= size - 1)
                {
                    matrix.at(y).at(x + 1) = counter;
                    ++x;
                }
                else
                    return;
                break;
            }
            case UP:
            {
                // check if the element on right is empty
                if (x + 1 <= size - 1 && matrix.at(y).at(x + 1) == 0)
                {
                    direction = RIGHT;
                    matrix.at(y).at(x + 1) = counter;
                    ++x;
                }
                // check if we are still within bounds
                else if (y - 1 >= 0)
                {
                    matrix.at(y - 1).at(x) = counter;
                    --y;
                }
                else
                    return;
                break;
            }
            case DOWN:
            {
                // check if the element on left is empty
                if (x - 1 >= 0 && matrix.at(y).at(x - 1) == 0)
                {
                    direction = LEFT;
                    matrix.at(y).at(x - 1) = counter;
                    --x;
                }
                // check if we are still within bounds
                else if (y + 1 <= size - 1)
                {
                    matrix.at(y + 1).at(x) = counter;
                    ++y;
                }
                else
                    return;
                break;
            }
        }
        ++counter;
    } 
 
    // print the numbers
    int maxDigits = numberOfDigits(n2);
    for (int i = 0; i < matrix.size(); ++i)
    {
        for (int j = 0; j < matrix.at(0).size(); ++j)
        {
            if (matrix.at(i).at(j) == 0)
                cout << " ";
            else
            {
                int value = matrix.at(i).at(j);
                // the following is done to make sure all numbers are printed pretty
                int digits = numberOfDigits(value);
                int spaces = maxDigits - digits;
                for (int s = 0; s < spaces; ++s)
                    cout << " ";
                cout << value << " ";    
            }
        }
        cout << endl;
    }
}
 
/**
* POINT OF ENTRY
*/
int main()
{
    string input;
    int n;
    cout << "===== Print First n^2 Numbers in a Spiral =====" << endl;
    cout << "Value for n: ";
    cin >> input;
    if (isNumber(input))
    {
        cout << "Result:" << endl;
        n = atoi(input.c_str());
        printSpiral(n);
    }
    else
    {
        cout << "Invalid input" << endl;
    }
    return 0;
}
0 Comments ,

Check If a String Contains a Palindrome in C++

Question: Find whether an input string contains a palindrome?
Example :
Input Samples: “1234xyzyx5678″, “abcdefeabc”
Output: A boolean value, true if the string contains a palindrome, false otherwise. (In this example input string conatins “xyzyx” and “efe”, both strings contain palindromes)

Solution: This problem can be solved using a stack-based approach. In short, if a pop can be done then the string contains a palindrome, otherwise it doesn’t contain a palindrome.

/**
* Description: Evaluates whether a string contains a palindrome
* Author: Carlos F. Perea
* URL: http://cperea.com
* License: Open
*/
#include <iostream>
#include <string>
#include <stack>
#include <assert.h>
 
using namespace std;
 
/**
* Checks whether a string contains a palindrome
* @param string	String to be checked
* @return   bool	True if the string contains a palindrome, false otherwise
*/
bool isPalindrome(string str)
{
	stack<char> s;
	for (int i = 0; i < str.size(); ++i)
	{
		char currentCharacter = str.at(i);
		if (!s.empty())
		{
			char topCharacter = s.top();
			// if this character is the same as the previous character then return true
			if (currentCharacter == topCharacter)
				return true;
			if (s.size() > 1)
			{
			    s.pop();
			    // remove the element on top, this is done to remove the "pivot" character
			    // when the palindrome is of odd size
			    char secondOnTop = s.top();	// gets the second character on top
                // check if the current character is the same as the one two spaces before
                if (currentCharacter == secondOnTop)
                    return true;
                else
                    s.push(topCharacter);
			}
		}
		s.push(currentCharacter);
	}
	return false;
}
 
int main()
{
	string testString1 = "1234xyzyx5678";
	string testString2 = "madam";
	string testString3 = "abcc";
	string testString4 = "not";
	string testString5 = "abcdefghijklmnopqrstuvwxyz";
	// test the different words
	assert(isPalindrome(testString1) == true);
	assert(isPalindrome(testString2) == true);
	assert(isPalindrome(testString3) == true);
	assert(isPalindrome(testString4) == false);
	assert(isPalindrome(testString5) == false);
	return 0;
}
0 Comments , ,

Implementation of a Trie in C++

A trie is a particular type of n-ary tree in which characters are stored in each node. Any particular branch in the tree may represent a word. For more information visit the Wikipedia article that deals with tries: http://en.wikipedia.org/wiki/Trie
A simple trie may look like this:

Tries

Source: TopCoder.com

Why should you learn tries?

  • Efficient information retrieval
  • Used to index and search for strings in text
  • Examples of usage include: finding longest prefix match, auto-complete, lexicographical order

Keep in mind that the trie’s root is always an empty string (represented by a space in this particular implementation).

The following code is an implementation of a trie in C++:

/****************************************************************************
* Name: main.cpp
* Author: Carlos F. Perea
* Description: Trie data structure
* Copyright: OPEN
****************************************************************************/
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
 
using namespace std;
 
/**
* Class: Node
* Represents a node within a trie tree
*/
class Node
{
public:
    char value;             // the character value (a-z)
    bool end;               // indicates whether this node completes a word
    Node * children[26];    // represents the 26 letters in the alphabet
    Node(char value);
    ~Node();
};
 
/**
* Constructor method
*/
Node::Node(char value)
{
    this->value = value;
    // Initializes all of the children with NULL value
    for (int i = 0; i < 26; ++i)
        children[i] = NULL;
}
 
/**
* Destructor method
*/
Node::~Node()
{
    // free resources
}
 
/**
* Class: Trie
* Represents a trie tree data structure
*/
class Trie
{
public:
    Trie();
    ~Trie();
    void addWord(string word);
    bool searchForWord(string word);
    void deleteWord(string word);
    Node * getRoot();
private:
    Node * root;
};
 
/**
* Constructor method
*/
Trie::Trie()
{
    // Initialize the trie
    root = new Node(' ');
    root->end = true;
}
 
/**
* Destructor method
*/
Trie::~Trie()
{
    // Free resources
}
 
/**
* Gets the root of the trie
* @return Node *    Pointer to the root node
*/
Node * Trie::getRoot()
{
    return root;
}
 
/**
* Add a word to the trie
* @param string Word to add to the trie
* @return void
*/
void Trie::addWord(string word)
{
    Node * currentNode = root;
 
    for (int i = 0; i < word.size(); ++i)
    {
        char currentChar = tolower(word.at(i));
        int index = currentChar - 'a';
        assert(index >= 0);     // Makes sure the character is between a-z
        if (currentNode->children[index] != NULL)
        {
            // check if the current node has the current character as one of its decendants
            currentNode = currentNode->children[index];
        }
        else
        {
            // the current node doesn't have the current character as one of its decendants
            Node * newNode = new Node(currentChar);
            currentNode->children[index] = newNode;
            currentNode = newNode;
        }
        if (i == word.size() - 1)
        {
            // the last character of the word has been reached
            currentNode->end = true;
        }
    }
}
 
/**
* Searches for a word in the trie
* @param string The word to search in the trie
* @return bool  True if it's found, false otherwise
*/
bool Trie::searchForWord(string word)
{
    Node * currentNode = root;
    for (int i = 0; i < word.size(); ++i)
    {
        char currentChar = tolower(word.at(i));
        int index = currentChar - 'a';
        assert(index >= 0);
        // if the current node has the current character as one of its decendants
        if (currentNode->children[index] != NULL)
            currentNode = currentNode->children[index];
        else
            return false;
        // makes sure the last node is marked as an end for a word
        if (i == word.size() - 1 && !currentNode->end)
            return false;
    }
    return true;
}
 
/**
* Deletes a word from the trie
* @param string The word to be deleted from the trie
* @return void
*/
void Trie::deleteWord(string word)
{
    Node * currentNode = root;
    Node * lastWord = root;
    for (int i = 0; i < word.size(); ++i)
    {
        char currentChar = tolower(word.at(i));
        int index = currentChar - 'a';
        assert(index >= 0);
        // if the current node has the current character as one of its decendants
        if (currentNode->children[index] != NULL)
            currentNode = currentNode->children[index];
        // the current node doesn't have the current character which means the word is not in the trie
        else
            return;
        if (i == word.size() - 1 && currentNode->end)
            currentNode->end = false;
    }
}
 
/**
* Traverse the trie in-order fashion to print the words in lexicographical order
*/
void alphabetize(Node * node, string prefix = "")
{
    if (node->end)
        cout << prefix << endl;
    for (int i = 0; i < 26; ++i)
    {
        if (node->children[i] != NULL)
        {
            string currentString = prefix + node->children[i]->value;
            alphabetize(node->children[i], currentString);
        }
    }
}
 
int main()
{
    Trie * t = new Trie();
    t->addWord("Carlos");
    t->addWord("Perea");
    t->addWord("Hello");
    t->addWord("Ball");
    t->addWord("Balloon");
    t->addWord("Show");
    t->addWord("Shower");
    alphabetize(t->getRoot());
    /*
    Outputs:
    ball
    balloon
    carlos
    hello
    perea
    show
    shower
    */
    return 0;
}
0 Comments ,

Jolly Jumpers – Programming Challenges

Problem: http://www.programming-challenges.com/english/pdfs/110201.pdf

This was another problem that got the “Solved” response from the online judge on my first submission!

Solution:

/*********************************************************************************
* Description: Jolly Jumpers - Problem 110201 (http://programming-challenges.com)
* Author: Carlos F. Perea
* Date: July 27th, 2013
* E-mail: contact@cperea.com
* URL: http://cperea.com
* License: OPEN
**********************************************************************************/
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cmath> 
 
using namespace std;
 
void print(const vector<int> & list)
{
    for (int i = 0; i < list.size(); ++i)
        cout << list.at(i) << " ";
    cout << endl;
}
 
void initializeList(vector<int> & list, int length)
{
    list.clear();
    for (int i = 0; i < length; ++i)
        list.push_back(0);
}
 
int main()
{
    vector<int> numbers;
    vector<int> differences;
    int n = 0;
 
    cin >> n;
 
    while (!cin.eof())
    {
        // saves the numbers inputed
        for (int i = 0; i < n; ++i)
        {
            int currentNumber;
            cin >> currentNumber;
            numbers.push_back(currentNumber);
        }
 
        // initializes the "difference" list
        initializeList(differences, n);
 
        // gets the n - 1 differences
        // the index of the array is the difference and the value is the number of occurrences
        for (int j = 0; j < n - 1; ++j)
        {
            int currentDifference = abs(numbers.at(j) - numbers.at(j + 1));
            if (currentDifference < differences.size())
                differences.at(currentDifference) += 1;
        }
 
        bool jolly = true;
 
        // checks if the difference array contains any zeroes which means the sequence is not a jolly number
        for (int k = 1; k < n; ++k)
        {
            if (differences.at(k) == 0)
            {
                jolly = false;
                break;
            }
        }
 
        if (jolly)
            cout << "Jolly" << endl;
        else
            cout << "Not jolly" << endl;
 
        numbers.clear();
        cin >> n;
    }
 
    return 0;
}
0 Comments , ,