CareerCup

bool partistr(string input, vector<string> res, vector<vector<string>> & out) {
    
    if (res.size() == 3) {
        if (stoi(res[0]) == stoi(res[1]) + stoi(res[2])) {
            out.push_back(res);
            res.erase(res.begin());
        } else {
            res.clear();
        }
    }
    if (input.size() == 1) {
          if (res.size() == 2 && stoi(res[0]) == stoi(res[1]) + stoi(input)) {
              return true;
          }
    }

    for (int i = 1; i < input.size(); i++) {
        string curr = input.substr(input.length() - i, i);
        res.push_back(curr);
      
        auto rem = input.substr(0, input.length() - i);
        if (partistr(rem, res, out))
            return true;
        res.pop_back();
    }
    return false;
}

// 123, map 1 - > {A,B,C} 2->{D,E}, 12->{X}, 3->{P,Q}
// AEP...., XP, XQ
vector<string> getPermutation(map<string, vector<char>> input, string value) {
    if (input.find(value) != input.end()) {
        vector<string> result;
        for (auto c : input[value]) {
            string temp;
            temp.push_back(c);
            result.push_back(temp);
        }
        return result;
    }
    vector<string> result;
    for (int i = 1; i < value.length(); i++) {
        vector<string> p1 = getPermutation(input, value.substr(0 ,i));
        vector<string> p2 = getPermutation(input, value.substr(i));
        for (auto c1 : p1) {
            for (auto c2 : p2) {
                string temp (c1 + c2);
                result.push_back(temp);
            }
        }
    }
    return result;
}

int bfsShortest() {
    string input = "ABACB";
    map<string, char> lookup;
    lookup["AB"] = 'C';
    lookup["AC"] = 'B';
    lookup["BC"] = 'A';

    lookup["BA"] = 'C';
    lookup["CA"] = 'B';
    lookup["CB"] = 'A';
    
    set<string> visited;
    struct info {
        string input;
        int steps;
    };
    
    queue<info> q;

    info i;
    i.input = input;
    i.steps = 0;
    q.push(i);
    
    int minSteps = INT_MAX;
    
    while (!q.empty()) {
        info curr = q.front();
        q.pop();
        if (curr.input.length() == 1) {
            minSteps = min(minSteps, curr.steps);
        }
        visited.insert(curr.input);
        
        for (int i = 0; i < curr.input.length(); i++) {
            if (i > curr.input.length() - 2) break;
            string temp = curr.input.substr(i, 2);
            if (lookup.find(temp) != lookup.end()) {
                string modified = curr.input.substr(0, i) + lookup[temp] + curr.input.substr(i + 2);
                info m;
                m.input = modified;
                m.steps = curr.steps + 1;
                if (visited.find(modified) == visited.end())
                    q.push(m);
            }
        }
    }
    return (minSteps == INT_MAX) ? -1 : minSteps;
}

int findInInput(string target, vector<string> input, int offset) {
     for (int i = offset; i < input.size(); i++) {
         if (input[i] == target)
             return i;
     }
    return -1;
}
pair<int,int> findTarget(vector<string> target, vector<string> input, int offset) {
    pair<int,int> result;
    
    int beginIndex = -1, endIndex = -1;
    for (auto t : target) {
        int index = findInInput(t, input, offset);
        if (index == -1)
            break;
        (beginIndex == -1) ? beginIndex = index : endIndex = index;
    }
    result = make_pair(beginIndex, endIndex);
    return result;
}
void getMinClosure() {
    vector<string> target = { "eat", "in", "south"};
    vector<string> input = {"eat", "to", "eat", "in", "eat", "go", "bye",  "south"};
    
    int minDist = INT_MAX;
    for (int i = 0; i < input.size(); i++) {
        pair<int, int> range = findTarget(target, input, i);
        if (range.first != -1 && range.second != -1)
            minDist = min(minDist, range.second - range.first);
    }
}

vector<string> getPermutation(map<string, vector<char>> input, string value) {
    vector<string> values;
    vector<string> result, output;
    string currConcat, currStr;
    int index = 0, len = 1;
    
    result.push_back("");

    while (index < value.length()) {
        if (index + len <= value.length())
            currStr = value.substr(index, len);
        else
            currStr = value.substr(index);
        if (input.find(currStr) != input.end()) {
            vector<char> current = input[currStr];
            vector<string> temp;
            for (char c : current) {
                for (int i = 0; i < result.size(); i++) {
                    string res;
                    res += result[i];
                    res.push_back(c);
                    temp.push_back(res);
                }
            }
            currConcat += currStr;
            result = temp;
        }
        if (currConcat == value) {
            index = 0;
            len++;
            currConcat = "";
            output = result;
            result.clear();
            result.push_back("");
        } else {
            index += len;
        }
    }
    return output;
}

vector<int> interleave(const vector<vector<int>>& input) {
    vector<int> result;
    int index = 0;
    int maxSize = INT_MIN;
    
    for (auto i : input) {
        maxSize = max(maxSize, (int)i.size());
    }
    
    while (index < maxSize) {
        for (int i = 0; i < input.size(); i++) {
            if (index >= input[i].size())
                continue;
            result.push_back(input[i][index]);
        }
        index++;
    }
    return result;
}

bool startParse(const string& input, string& method) {
    int pos = input.find_last_of(',');
    string start = input.substr(pos + 1);
    method = input.substr(0, pos);
    return start == "start";
}

void callOrder(const vector<string>& input, int index, vector<vector<string>>& values, int depth) {
    if (index >= input.size())
        return;
    string methodName;
    if (startParse(input[index], methodName)) {
        values[depth].push_back(methodName);
        callOrder(input, index + 1, values, depth + 1);
    } else {
        callOrder(input, index + 1, values, depth - 1);
    }
}


int main(int argc, const char * argv[]) {
    vector<string> input = {"main,start", "foo,start", "foo,end", "boo,start", "boo,end", "main,end"};
    vector<vector<string>> methods;


    callOrder(input, 0, methods, 0);
    
    for (int i = 0; i < methods.size(); i++) {
        for (auto method : methods[i]) {
            cout << setfill(' ') << setw(i) << method << std::endl;
        }
    }
}

void maybeString(string input, int index, vector<string>& output) {
    
    if (index >= input.length()) {
        output.push_back(input);
        return;
    }
    if(input[index] == '?') {
    input[index] = '0';
    maybeString(input, index + 1, output);
    
    input[index] = '1';
    maybeString(input, index + 1, output);

    } else {
        maybeString(input, index + 1, output);
    }
}

void maybeString(string input, int index, vector<string>& output) {

if (index >= input.length()) {
output.push_back(input);
return;
}

if(input[index] == '?') {
input[index] = '0';
maybeString(input, index + 1, output);

input[index] = '1';
maybeString(input, index + 1, output);

} else {
maybeString(input, index + 1, output);
}
}

// 1->2->3->4->5
// 1->5->2->4->3
node* revLink(node*& first, node*& end) {
if (end == NULL)
return NULL;
node* node = revLink(first, end->next);
if (first == NULL || first->next == NULL)
return node;
if (first->val == end->val) {
first->next = NULL;
return node;
}


node* temp = first->next;
first->next = end;
end->next = temp;

cout << first->val << std::endl;
cout << first->next->val << std::endl;
cout << first->next->next->val << std::endl;

if (node == NULL)
node = first;

first = temp;

return node;
}

// 1->2->3->4->5
// 1->5->2->4->3
node* revLink(node*& first, node*& end) {
if (end == NULL)
return NULL;
node* node = revLink(first, end->next);
if (first == NULL || first->next == NULL)
return node;
if (first->val == end->val) {
first->next = NULL;
return node;
}


node* temp = first->next;
first->next = end;
end->next = temp;

cout << first->val << std::endl;
cout << first->next->val << std::endl;
cout << first->next->next->val << std::endl;

if (node == NULL)
node = first;

first = temp;

return node;
}