#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3

    Pangram using recursion


    I am supposed to write a program that determines if a sentence is a pangram (contains all 26 letters of the alphabet at least once.)

    Here is my code:

    Code:
    #include <iostream>
    #include <string>
    #include <set>
    using namespace std;
    /*
    Write a program called isPangram that takes a string
    and returns true if that string is a pangram.alphabet at least once.
    A pangram is a sentence that uses every letter of the
    */
    
    bool isPangram(string s, int index, int last)
    {
        if (index >= 26)
        {
            return true;
        }
        else
        {
            return isPangram(s, ++index, ++last);
        }
    
    }
    
    bool isPangram(string s)
    {
        return isPangram(s, 0, s.size() - 1);
    }
    Here is my code with the other code.

    Code:
    #include <iostream>
    #include <string>
    #include <set>
    using namespace std;
    /*
    Write a program called isPangram that takes a string
    and returns true if that string is a pangram.alphabet at least once.
    A pangram is a sentence that uses every letter of the
    */
    
    bool isPangram(string s, int index, int last)
    {
        if (index >= 26)
        {
            return true;
        }
        else
        {
            return isPangram(s, ++index, ++last);
        }
    
    }
    
    bool isPangram(string s)
    {
        return isPangram(s, 0, s.size() - 1);
    }
    
    
    void test(string str)
    {
    	if (isPangram(str))
    	{
    		cout << "\"" << str << "\"" << " is a pangram." << endl;
    	}
    	else
    	{
    		cout << "\"" << str << "\"" << " is not a pangram." << endl;
    	}
    }
    
    int main()
    {
    	test("this is a test");
    	test("THE quick BROWN fox JUMPS over THE lazy DOG!!");
    	test("THE quick BROWN fox JUMPed over THE lazy DOG!!");
    	test("THE quick BROWN fox JUMPed over THE layyy DOG!!");
    	test("T.V. quiz jock, Mr. PhD, bags few lynx");
    	test("NBC glad. Why? Fox TV jerks quiz PM.");
    	test("JFK got my VHS, PC and XLR web quiz.");
    	test("Jaded zombies acted quietly but kept driving their oxen forward.");
    	test("How razorback-jumping frogs can level six piqued gymnasts!");
    	test("Few black taxis drive up major roads on quiet hazy nights.");
    	test("Have a pick: twenty six letters -- no forcing a jumbled quiz!");
    	test("Jaded zombies acted quietly but kept running their oxen forward.");
    	test("How razorback-jumping frogs can level seven piqued gymnasts!");
    	test("Few orange taxis drive up major roads on quiet hazy nights.");
    	test("Have a pick: twenty seven letters -- no forcing a jumbled quiz!");
    }
    I am having trouble coming up with a way for the function to check to see if each character it checks is unique. I cannot use global or static variables, and I cannot use any loops.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    I'd say you'd do well to have this function
    bool isPangram(string s)
    convert the string to lower or upper case (or make a new string with fixed case) before passing the string off to your other isPangram.

    Your program could work more accurately if it had a test for alphabet characters in the string.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    > I cannot use global or static variables, and I cannot use any loops.
    But do you know how to write isPangram() using a loop?

    Recursion is just a loop in disguise, so the first step is knowing how to do it in the obvious way before trying to do it in the non-obvious way.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3
    Here is my updated code.

    Code:
    #include <iostream>
    #include <string>
    #include <set>
    using namespace std;
    /*
    Write a program called isPangram that takes a string
    and returns true if that string is a pangram.alphabet at least once.
    A pangram is a sentence that uses every letter of the
    */
    
    bool isPangram(string s, int index, int last)
    {
    
        if (index >= 26)
        {
            return true;
        }
        else if (index < 26)
        {
            return false;
        }
        else
        {
            
            return isPangram(s, ++index, ++last);
        }
    
    }
    
    bool isPangram(string s)
    
    {
        s = "abcdefghijklmnopqrstuvwxyz";
        return isPangram(s, 0, s.size() - 1);
    }
    Now it outputs false for every test case.

    To check if a string contained all 26 letters of the alphabet, I would loop through the string, check each index, and if an element in each index did not match another index before it, then it would be unique. I would also have to make a case for lower/upper case. But because I cannot use a loop, I'm stuck.





    Originally Posted by salem
    > I cannot use global or static variables, and I cannot use any loops.
    But do you know how to write isPangram() using a loop?

    Recursion is just a loop in disguise, so the first step is knowing how to do it in the obvious way before trying to do it in the non-obvious way.
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    Salem really advises "write the program with a loop". You didn't write that program. You chatted about it.

    Why are you checking indexes? You need to test
    that you came to the end of the string.
    Characters. You need to test characters! And mark those found!


    You call isPangram with a single string argument. Yes?
    isPangram(string s)
    immediately replaces the input. That problem will appear later.
    isPangram calls isPangram with three argument signature with 0 for the second argument.

    What happens in 3 argument isPangram?
    Code:
    if (index >= 26)
        {
            return true;
        }
        else if (index < 26)
        {
            return false;
        }
    index is 0. Therefore 3 argument isPangram immediately returns false.

    I'd condense those 8 lines of code to
    Code:
    return 26 <= index;
    clearly indicating that the program will return, and it returns 0 or 1 .
    Last edited by b49P23TIvg; November 27th, 2012 at 06:15 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3
    I'm trying a different approach. Because sets do not allow duplicates, it should be easier to get unique characters.


    Code:
        //have is Pangram take a set (will be empty initially)
        //Note: the set must be passed by reference
        //if set is 26, return true
        //if index == size and set is not 26, return false
        //else add current character to set if it's a letter
        //recursively call isPangram with index + 1
    
    bool isPangram(string s, set<string> &mySet, int index)
    {
        if (mySet.size() == 26)
            return true;
        if (index == mySet.size() && mySet.size() != 26)
            return false;
        else
        {
            if(isalpha(s[0]))
            {
                mySet.insert(s);
            }
        }
        return isPangram(s, mySet, index++);
    }
    
    bool isPangram(string s)
    {
        set<string> mySet;
        return isPangram(s, mySet,0);
    }
    When I run my program, all outcomes are false. It reads not a pangram for everything.
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    Sets! Great idea!

    Make a set of characters, and insert a character at a time.

    mySet.insert(s[0]); // assuming s changes from the front in recursive calls

    Allowing sets, recursion looks dumber and dumber.
    [code]Code tags[/code] are essential for python code and Makefiles!
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3
    Here is my entire code

    Code:
    #include <iostream>
    #include <string>
    #include <set>
    #include <algorithm>
    using namespace std;
    /*
    Write a program called isPangram that takes a string
    and returns true if that string is a pangram.alphabet at least once.
    A pangram is a sentence that uses every letter of the
    */
    
        //have is Pangram take a set (will be empty initially)
        //Note: the set must be passed by reference
        //if set is 26, return true
        //if index == size and set is not 26, return false
        //else add current character to set if it's a letter
        //recursively call isPangram with index + 1
    
    
    
    bool isPangram(string s, int index, set<char> &mySet)
    {
        if (mySet.size() == 26)
            return true;
        if (index == mySet.size() && mySet.size() != 26)
            return false;
        else
        {
            if(isalpha(s[0]))
            {
    
                transform(s.begin(), s.end(), s.begin(), ::tolower);
                mySet.insert(s[0]);
            }
        }
        return isPangram(s, index++, mySet);
    }
    
    bool isPangram(string s)
    {
        set<char> mySet;
        return isPangram(s, 0, mySet);
    }
    
    
    
    void test(string str)
    {
    	if (isPangram(str))
    	{
    		cout << "\"" << str << "\"" << " is a pangram." << endl;
    	}
    	else
    	{
    		cout << "\"" << str << "\"" << " is not a pangram." << endl;
    	}
    }
    
    int main()
    {
    	test("this is a test");
    	test("THE quick BROWN fox JUMPS over THE lazy DOG!!");
    	test("THE quick BROWN fox JUMPed over THE lazy DOG!!");
    	test("THE quick BROWN fox JUMPed over THE layyy DOG!!");
    	test("T.V. quiz jock, Mr. PhD, bags few lynx");
    	test("NBC glad. Why? Fox TV jerks quiz PM.");
    	test("JFK got my VHS, PC and XLR web quiz.");
    	test("Jaded zombies acted quietly but kept driving their oxen forward.");
    	test("How razorback-jumping frogs can level six piqued gymnasts!");
    	test("Few black taxis drive up major roads on quiet hazy nights.");
    	test("Have a pick: twenty six letters -- no forcing a jumbled quiz!");
    	test("Jaded zombies acted quietly but kept running their oxen forward.");
    	test("How razorback-jumping frogs can level seven piqued gymnasts!");
    	test("Few orange taxis drive up major roads on quiet hazy nights.");
    	test("Have a pick: twenty seven letters -- no forcing a jumbled quiz!");
    }
    I don't know why it's always returning false.


    Originally Posted by b49P23TIvg
    Sets! Great idea!

    Make a set of characters, and insert a character at a time.

    mySet.insert(s[0]); // assuming s changes from the front in recursive calls

    Allowing sets, recursion looks dumber and dumber.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    38
    Rep Power
    3
    I figured it out. I needed to use the post fix increment on index, and compare index to the size of the string.

    Thanks for the help, everyone.

IMN logo majestic logo threadwatch logo seochat tools logo