c++ - Recursive String Transformations -

c++ - Recursive String Transformations -

edit: i've made main alter of using iterators maintain track of successive positions in bit , character strings , pass latter const ref. now, when re-create sample inputs onto multiple times test clock, finishes within 10 seconds long bit , character strings , 50 lines of sample input. but, still when submit, codeeval says process aborted after 10 seconds. mention, don't share input "extensions" of sample input work, i'm not sure how proceed. thoughts on additional improvement increment recursive performance appreciated.

note: memoization suggestion not figure out how implement in case since i'm not sure how store bit-to-char correlation in static look-up table. thing thought of convert bit values corresponding integer risks integer overflow long bit strings , seems take long compute. farther suggestions memoization here appreciated well.

this 1 of moderate codeeval challenges. don't share sample input or output moderate challenges output "fail error" says "aborted after 10 seconds," code getting hung somewhere.

the assignment simple enough. take filepath single command-line argument. each line of file contain sequence of 0s , 1s , sequence of , bs, separated white space. determine whether binary sequence can transformed letter sequence according next 2 rules:

1) each 0 can converted non-empty sequence of (e.g, 'a', 'aa', 'aaa', etc.)

2) each 1 can converted non-empty sequences of or bs (e.g., 'a', 'aa', etc., or 'b', 'bb', etc) (but not mixture of letters)

the constraints process 50 lines file , length of binary sequence in [1,150] , of letter sequence in [1,1000].

the obvious starting algorithm recursively. came each bit, collapse entire next allowed grouping of characters first, test shortened bit , character strings. if fails, add together 1 character killed character grouping @ time , phone call again.

here finish code. removed cmd-line argument error checking brevity.

#include <iostream> #include <fstream> #include <string> #include <iterator> using namespace std; //typedefs typedef string::const_iterator str_it; //declarations //use const ref , iterators save time on copying , erasing bool transformline(const string & bits, str_it bits_front, const string & chars, str_it chars_front); int main(int argc, char* argv[]) { //check there @ to the lowest degree 2 command line arguments: binary executable , file name //ignore additional arguments if(argc < 2) { cout << "invalid command line argument. no input file name provided." << "\n" << "goodybe..."; homecoming -1; } //create input stream , open file ifstream in; in.open(argv[1], ios::in); while(!in.is_open()) { char* name; cout << "invalid file name. please come in file name: "; cin >> name; in.open(name, ios::in); } //variables string line_bits, line_chars; //reserve space constraints cut down resizing time later line_bits.reserve(150); line_chars.reserve(1000); int line = 0; //loop on lines (<=50 constraint, ignore rest) while((in >> line_bits >> line_chars) && (line < 50)) { line++; //impose bit , char constraints if(line_bits.length() > 150 || line_chars.length() > 1000) continue; //skip line (transformline(line_bits, line_bits.begin(), line_chars, line_chars.begin()) == true) ? (cout << "yes\n") : (cout << "no\n"); } //close file in.close(); homecoming 0; } bool transformline(const string & bits, str_it bits_front, const string & chars, str_it chars_front) { //using iterators store current length local const //can create these const because they're not altered here int bits_length = distance(bits_front, bits.end()); int chars_length = distance(chars_front, chars.end()); //check success rule if(bits_length == 0 && chars_length == 0) homecoming true; //check fail rules: //1. next bit 0 next char b //2. bits length 0 (but char not, previous if) //3. char length 0 (but bits length not, previous if) if((*bits_front == '0' && *chars_front == 'b') || bits_length == 0 || chars_length == 0) homecoming false; //we know chars_length != 0 => chars_front != chars.end() //kill bit , phone call recursively each possible reduction of front end char grouping bits_length = distance(++bits_front, bits.end()); //current char grouping tracker const char curr_char_type = *chars_front; //use const compiler can optimize int curr_pos = distance(chars.begin(), chars_front); //position of current front end in char string //since chars 0-indexed, next length of current char grouping //start searching curr_pos , length relative curr_pos subtract it!!! int curr_group_length = chars.find_first_not_of(curr_char_type, curr_pos)-curr_pos; //make sure isn't lastly group! if(curr_group_length < 0 || curr_group_length > chars_length) curr_group_length = chars_length; //distance end exactly distance(chars_front, chars.end()) = chars_length //kill curr_char_group //if curr_group_length = char_length create chars_front = chars.end() //and mean chars_length 0 on next recurssive call. chars_front += curr_group_length; curr_pos = distance(chars.begin(), chars_front); //call recursively, adding char current grouping until 1 less starting point int added_back = 0; while(added_back < curr_group_length) { if(transformline(bits, bits_front, chars, chars_front)) homecoming true; //insert 1 char current grouping else { added_back++; chars_front--; //represents adding 1 character grouping } } //if here recursive checks failed initial must fail homecoming false; }

they give next test cases, code solves correctly:

sample input:

1| 1010 aaaaabbbbaaaa

2| 00 aaaaaa

3| 01001110 aaaabaaabbbbbbaaaaaaa

4| 1100110 bbaababba

correct output:

1| yes

2| yes

3| yes

4| no

since transformation possible if , if copies of are, tried copying each binary , letter sequences onto various times , seeing how clock goes. long bit , character strings , many lines has finished in under 10 seconds.

my question is: since codeeval still saying running longer 10 seconds don't share input, have farther suggestions improve performance of recursion? or maybe totally different approach?

thank in advance help!

here's found:

pass constant reference strings , other big info structures should passed constant reference. allows compiler pass pointer original object, rather making re-create of info structure.

call functions once, save result calling bits.length() twice. should phone call 1 time , save result in constant variable. allows check status 1 time again without calling function.

function calls expensive time critical programs.

use constant variables if not going modify variable after assignment, utilize const in declaration:

const char curr_char_type = chars[0];

the const allows compilers perform higher order optimization , provides safety checks.

change info structures since perform inserts maybe in middle of string, should utilize different info construction characters. std::string info type may need reallocate after insertion , move letters farther down. insertion faster std::list<char> because linked list swaps pointers. there may trade off because linked list needs dynamically allocate memory each character.

reserve space in strings when create destination strings, should utilize constructor preallocates or reserves room largest size string. prevent std::string reallocating. reallocations expensive.

don't erase need erase characters in string? using starting , ending indices, overwrite existing letters without have erase entire string. partial erasures expensive. finish erasures not.

for more assistance, post code review @ stackexchange.

c++ string recursion