Thread: optimizing

  1. #1
    Registered User
    Join Date
    Dec 2005
    Location
    Canada
    Posts
    267

    optimizing

    I've recently made a new friend, recursion, and decided to try out some of topcoder's 1000-point problems. Right now, I'm stuck on this problem. I have a working solution but it goes beyond the 2 second limit with the last example.
    I've tried looking at other people's code but I can't figure out the logic behind their code.

    This is my code, how can I Improve it?
    Code:
    #include <string>
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Wizarding
    {
    	string s1; //spell
    	int p;     //power
    	void cs(string s, string r, std::vector<bool> c)
    	{
    		int tempp = 1;
    		for (int i = 0; i < s.length(); i++)
    			tempp *= (s[i]-'A'+1);
    		tempp %= 77077;
    		if (tempp > p)
    		{
    			this->s1 = s;
    			this->p = tempp;
    		}
    		{
    			bool a = 0;
    			for (int i = 0; i < c.size(); i++) if (c[i]!= true) {a=true;break;}
    			if (a && s.length() == 1)
    				return;
    		}
    		
    		//replace
    		for (int i = 0; i < s.length(); i++)
    		{
    			if (c[i])
    				continue;
    			string temps = s;
    			temps[i] = r[s[i]-'A'];
    			c[i] = true;
    			cs(temps, r, c);
    			c[i] = false;
    		}
    		//remove
    		for (int i = 0; s.length()!= 1 && i < s.length(); i++)
    		{
    			string temps = s;
    			temps.erase(temps.begin()+i);
    			std::vector<bool> tempc;
    			for (int j = 0; j < c.size(); j++) if (j != i) tempc.push_back(c[j]);
    			cs(temps, r, tempc);
    		}
    	}
    	public:
    		string counterspell(string spell, string rules);
    };
    
    string Wizarding::counterspell(string spell, string rules)
    {
    	s1 = spell;
    	p = 0;
    	std::vector<bool> c(spell.length(), false);
    	for (int i = 0; i < spell.length(); i++)
    		if (rules[spell[i]-'A'] == '-') c[i] = true;
    	cs(spell, rules, c);
    	return this->s1;
    }

    OS: Windows 7, XUbuntu 11.10, Arch Linux
    IDE: CodeBlocks
    Compiler: GCC

  2. #2
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    The link requires membership. Describe what the program's meant to do.

  3. #3
    Registered User
    Join Date
    Dec 2005
    Location
    Canada
    Posts
    267
    asdf
    Wizarding

    Problem Statement
    A spell is defined by its incantation, the word spoken when the spell is being cast. If you know the incantation of a spell, you can create counterspells in the following manner. First, you can optionally delete any number of characters from the original incantation. Note that empty incantations are not valid so you cannot delete all characters. Then, you can replace any number of the remaining characters according to a set of replacement rules. The replacement rules tell you which letters can be replaced, and the letters with which they can be replaced. For example, if the original incantation is "AA" and the allowed replacement is 'A' to 'Z', the following counterspells are possible: "AA", "A", "Z", "ZZ", "AZ", "ZA".



    The best counterspell is the one with the greatest power. The power of a spell is the product of all its character values modulo 77077, where the value for a character is its position in the alphabet (character 'A' has value 1, character 'B' value 2, character 'C' value 3, and so on). The best possible counterspell for "AA" in the example above is "ZZ", which has a power of 676.



    Please note that if the allowed replacements are 'A' to 'B' and 'B' to 'C', the counterspell for "AB" is "BC" not "CC". You cannot change a character that has already been changed, even if it would lead to a more powerful spell.



    You will be given a String spell, the incantation of the spell you are going to counter, and a String rules, the allowed replacements for letters. The first character in rules is the allowed replacement for the letter 'A', the second for 'B' and so on. The character '-' is used to denote a letter that cannot be replaced. Your program must return a String, the most powerful counterspell available. If multiple return values are possible, return the shortest among them. If a tie still exists return the lexicographically earliest.

    Definition

    Class: Wizarding
    Method: counterspell
    Parameters: String, String
    Returns: String
    Method signature: String counterspell(String spell, String rules)
    (be sure your method is public)


    Constraints
    - spell will contain between 1 and 13 characters, inclusive.
    - spell will contain only uppercase letters ('A'-'Z').
    - rules will contain exactly 26 characters.
    - rules will contain only uppercase letters ('A'-'Z') and dashes ('-').

    Examples
    0)


    "AA"

    "Z-------------------------"

    Returns: "ZZ"

    The example from the problem statement.
    1)


    "AB"

    "ZS------------------------"

    Returns: "ZS"

    The possible counterspells are "AB", "A", "B", "Z", "S", "ZB", "AS" and "ZS".

    "ZS" is the most powerful.
    2)


    "ZZZZ"

    "-------------------------Z"

    Returns: "ZZZZ"

    3)


    "ABCDE"

    "ZYXXYXZZXYXXZZXZYYXZZZX---"

    Returns: "ZXXE"

    4)


    "ABCDEABCDEABC"

    "ACBDESKADSLOEDDDASDBADEDAE"

    Returns: "CCDECCECC"

    OS: Windows 7, XUbuntu 11.10, Arch Linux
    IDE: CodeBlocks
    Compiler: GCC

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I can't be bothered reading over the description of what the code is supposed to do, so I'll just give tips based on what the code does poorly, just by looking at it. As such I might miss higher-level optimisations.

    Don't pass everything by value, especially not the vector. Pass everything by reference, or const-reference as appropriate.

    "s.length()!= 1 &&" should not be part of the condition in one of your for-loops as s does not change during the loop. Put it in an if-statement surrounding the loop instead.
    Given how the vector will only contain relatively few items, you may find it faster to use vector<char> instead, avoiding the vector<bool> specialisation.

    With reference to this:
    Code:
    			if (a && s.length() == 1)
    				return;
    Why don't you check the length of s against 1 before you even bother to loop through the c vector? In fact you already have some brackets around it, so just put an "if (s.length() == 1)" in front of it and remove it from the later if-statement.

    You could premanipulate your strings before calling cs to subtract 'A' from each letter, and then add 'A' back to each char once you have your result. Do this last as it will probably make debugging harder. Or you could prepend a lot of dummy characters to that string, to save the need to subtract 'A' all the time, which would leave everything readable.

    There is probably a higher level optimisation opportunity being missed, but I'm not prepared to spend the time to try and understand the problem statement at the moment.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Dec 2005
    Location
    Canada
    Posts
    267
    nvm, I think i can find it myself... eventually...
    /*Those kinds of changes would only make minor improvements on it's performance, but thanks anyways. I'll keep those in mind for my next project.

    I can't copy/paste other people's code so here's a screenshot of one of them. Can someone explain to me the logic behind this code? (it's mainly solve's args that are confusing me)
    Attachment 7749*/
    Last edited by h_howee; 01-06-2008 at 02:49 AM.

    OS: Windows 7, XUbuntu 11.10, Arch Linux
    IDE: CodeBlocks
    Compiler: GCC

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem building Quake source
    By Silvercord in forum Game Programming
    Replies: 16
    Last Post: 07-11-2010, 09:13 AM
  2. optimizing repetitive code
    By R.Stiltskin in forum C++ Programming
    Replies: 12
    Last Post: 08-24-2008, 11:05 AM
  3. Optimizing my code
    By Lina in forum C Programming
    Replies: 30
    Last Post: 10-22-2006, 01:31 PM
  4. optimizing my quaternion code
    By confuted in forum Game Programming
    Replies: 9
    Last Post: 08-16-2003, 08:50 PM
  5. optimizing bubble sort
    By Sargnagel in forum C Programming
    Replies: 14
    Last Post: 01-23-2003, 06:27 AM