anti-particle solver

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.cc
 * Author: theleader
 *
 * Created on March 24, 2017, 8:38 PM
 */

#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>

// boards are expressed as strings with slashes in them.
// coords are (x,y) with (0,0) top left.


using namespace std;

vector<string> split(string s, string to_split){
    vector<string> output;
    int x=0;
    int limit=0;
    while(limit != string::npos){
        limit = s.find(to_split, x);
        output.emplace_back(s.substr(x, limit-x));
        x = limit+to_split.length();
    }
    return output;
}
template <class T> // vector concatenation,.
vector<T> operator+(const vector<T> & x, const vector<T> & y){
    vector<T> z = x;
    z.insert(z.end(), y.begin(), y.end());
    return z;
}

class point{
public:
    int x;
    int y;
    point(int x, int y):x(x),y(y){};
    point(){}; //map requires ctor with no args
    bool operator==(const point & p){
        return (x==p.x && y==p.y);
    }
};
class history_string{ // a string with history
public:
    string  s;
    vector<point> history;
    history_string(string s, vector<point> h):s(s),history(h){};
    history_string(){}; //map requires ctor with no args
    bool operator==(const history_string hs){
        return (s == hs.s);
    }


};

// printing:
ostream & operator<<(ostream & os, const point & p){
    os << "("<< p.x << "," << p.y<<")";
    return os;
}

ostream & operator<<(ostream & os, const history_string & hs){
    os << "[" << hs.s << "]:";
    for(const point & i : hs.history){
        os << i;
    }
    return os;
}



map<string, history_string> * table = new map<string, history_string>; // lookup table.
//do not forget to free this

vector<point> component(string s, point p){ // returns the set of points in the connected component. (0,0) is the top left.
    //throws if p is out of bounds
    vector<point> output {p};
    vector<string> board = split(s, "/");
    //note: this should be accessed y,x
    int height = board.size();
    int width = board.at(0).length();
    char lookFor = board.at(p.y).at(p.x); // DO NOT modify.
    if(lookFor == '.'){
        return vector<point>{};
    }
    /*for each unchecked point, check all of its neighbors, if they're the same
     color, then add them to the output and unchecked lists
     }*/
    vector<point> unchecked {p};
    vector<point> checked {};
    while(unchecked.size() != 0){
        //check the adjacent to the point
        vector<point> newUnchecked {};
        for(point & checking : unchecked){
            vector<point> neighbors {point(checking.x-1, checking.y),
                                     point(checking.x+1, checking.y) ,
                                     point(checking.x, checking.y-1),
                                     point(checking.x, checking.y+1)};
            for(point & neighbor : neighbors){
                /* check each neighbor of the point
                 * when will a point not be added into the output?
                 * if that point is out of bounds
                 * if that point is . or does not match
                 * if that point is in output */
                if(neighbor.x < 0 || neighbor.y < 0 || neighbor.x >= width|| neighbor.y >= height ){
                    continue;
                }
                if(board.at(neighbor.y).at(neighbor.x) == '.' || board.at(neighbor.y).at(neighbor.x) != lookFor ){
                    continue;
                }
                bool alreadyChecked = false;
                for(point & checkedPoint : checked){
                    if(neighbor == checkedPoint){
                        alreadyChecked = true;
                        break;
                    }
                }
                if(alreadyChecked){
                    continue;
                }
                output.push_back(neighbor);
                newUnchecked.push_back(neighbor);
            }
            checked.push_back(checking);
        }
        unchecked = newUnchecked;
    }
    return output;
}
string remove(string str, point p){
    //removes a single block from the board and moves everything above down
    //does not remove the entire connected component.
    string s = "";
    vector<string> board = split(str, "/");
    for(int row=0; row<board.size(); row++){
        for(int col=0; col < board.at(0).length(); col++){
            //if col match and 0th row, add .
            //if col match and row is less than or equal to p.y, but not zero, add previous row
            //else, add as is.
            if(col == p.x){
                if(row == 0){
                    s=s+".";
                } else if (row <= p.y){
                    s=s+board.at(row-1).at(col);
                }
                else{
                    s=s+board.at(row).at(col);
                }
            }else{
                s=s+board.at(row).at(col);
            }
        }
        if(row+1 < board.size()){
            s=s+"/";
        }
    }
    return s;
}
bool emptyColumn(string str, int c){ //determine if a column is empty
    vector<string> board = split(str, "/");
    for(int row=0; row<board.size(); row++){
        if(board.at(row).at(c) != '.'){
            return false;
        }
    }
    return true;
}
string removeCol(string str , int c){//removes an entire column, and adds empty spots on the right.
    vector<string> board = split(str, "/");
    string s = "";
    for(int row=0; row<board.size(); row++){
        for(int col=0; col < board.at(0).length()-1; col++){
            if(col >= c){
                s=s+board.at(row).at(col+1);
            } else {
                s=s+board.at(row).at(col);
            }
        }
        if(row+1 < board.size()){
            s=s+"/";
        }
    }
    return s;
}
string removeComponent(string s, point p){
    //removes the entire component, and moves all empty rows to the left
    vector<point> toRemove = component(s, p); // must go from top down
    vector<string> board = split(s, "/");
    for(int i=0; i<board.size();i++){
        for(point & p : toRemove){
            if(p.y == i){
                s = remove(s, p);
            }
        }
    }
    string ns = s;
    //must go right to left
    for(int i=board.at(0).size()-1; i>=0;i-- ){
        if(emptyColumn(s, i)){
            ns=removeCol(ns, i);
        }
    }
    return ns;
}
int score(string str){
    int x =0;
    for(int i=0;i<str.length();i++){
        if(str.at(i) != '.' && str.at(i) != '/'){
            x++;
        }
    }
    return x;
}
history_string solve(string str){
    /* For each point on the grid: get its connected components
     * for each component of size at least 2:
     *     create a new string with the component removed, and solve the string
     *     this gives us a list of history-strings
     * choose the one with the fewest, and return (that string, history with the chosen component pre-pended)
     *
     */
    //if it's already in the lookup table, don't do it again,
    if(table->find(str) != table->end()){
        return table->at(str);
    }
    vector<string> board = split(str, "/");
    vector<point> candidates {};
    //first make a list of possible places to choose places.
    vector<point> seen {};
    for(int y=0; y<board.size();y++){
        for(int x=0;x<board.at(0).length();x++){
            bool alreadySeenThisPoint = false;
            for(point & p : seen){
                if (p == point(x, y)){
                    alreadySeenThisPoint = true;
                    break;
                }
            }
            if(alreadySeenThisPoint){
                continue;
            }
            vector<point> theComponent = component(str, point(x,y));
            if(theComponent.size() >= 2){
                candidates.push_back(theComponent.at(0));
                seen = seen + theComponent;
            }
        }
    }
    if(candidates.size() ==0){ //we're done!
        history_string result = history_string(str, vector<point> {});
        (*table)[str] = result;
        return result;
    }
    vector<history_string>  candidateResults {};
    //recursively call this function for each component
    for(point & i : candidates){
        candidateResults.push_back(solve(removeComponent(str, i)));
    }
    //find the result with the smallest score:
    int argmin =-1;
    int minScore = str.size()+1;
    for(int i=0; i < candidateResults.size();i++){
        history_string hs = candidateResults.at(i);
        int score_this = score(hs.s) ;
        if(score_this < minScore){
            argmin = i;
            minScore = score_this;
        }
    }
    //we're done!
    history_string result = candidateResults.at(argmin);
    result.history = vector<point>{candidates.at(argmin)}+result.history;
    (*table)[str] = result;
    return result;
}

void show_removing_point(string str, point p){ // shows the string with the point to be removed
    vector<string> board = split(str, "/");
    for(int row=0; row < board.size(); row++){
        for(int col = 0; col < board.at(0).size() ; col++){
            cout << board.at(row).at(col);
            if(p.x == col && p.y == row){
                cout << "<";
            }else{
                cout << " ";
            }
        }
        cout << "\n";
    }
    cout << "tiles remaining: " << score(str) << "\n";

}
void show_solve(string str){ //graphically show how it is solved
    history_string hs = solve(str);
    for(point & p : hs.history){
        //print the string before removal and the point to be removed
        show_removing_point(str, p);
        cout << "removing point at " << p << "\n";
        str = removeComponent(str, p);
    }
    //show ending solution
    cout << "Final board : \n";
    show_removing_point(str, point(-3, -3));
    cout << "\n";
}
/*
 *
 */
void test_cases(){
    //test insertion and deletion, and printing
    //expected : [A1B2C3]:(3,4)(65,21)(512,3)
    (*table)["ABC"] =history_string("A1B2C3", vector<point>{point(3,4), point(65,21), point(512,3)});
    cout << (*table)["ABC"] << "\n";
    //test finding connected components:
    //expected: 3
    //expected: (2,0)
    //expected: (1,1)
    string testBoard  = "123456/234561/134125/131256/333162/5277..";
    cout << split(testBoard, "/").at(0).at(2) << "\n";
    for (point & p : component(testBoard, point(2, 0))){
        cout << p << " ";
    }
    cout << "\n";
    //expected : (1,1) (1,2) (1,3) (1,4) (0,4) (2,4)
    for (point & p : component(testBoard, point(1, 1))){
        cout << p << " ";
    }
    cout << "\n";
    // no output expected;
    for (point & p : component(testBoard, point(5, 5))){
        cout << p << " ";
    }
    //testing removing a point:
    //expected: 12.456/233561/134125/134256/333162/5277..
    cout << remove(testBoard, point(2,3))<<"\n";
    //expected: .23456/134561/234125/131256/333162/5277..
    cout << remove(testBoard, point(0,3))<<"\n";
    //testing removing an entire column
    string out =  remove(".32/.63/134", point(0,2));
    cout << out << "\n";// .32/.63/.34
    cout << emptyColumn(out, 1) << "\n"; // false
    cout << emptyColumn(out, 0) << "\n"; // true
    cout << removeCol(out, 0) << "\n"; // expected: 32/63/34
    //testing removing an entire component
    cout << removeComponent("3224/1111/5611/3422", point(1,0)) << "\n"; //
    cout << removeComponent("3..4/1111/5611/3422", point(0,1)) << "\n"; //
    cout << removeComponent("..../3.../56../3422", point(2,3)) << "\n"; //
    //testing solving
    show_solve("3224/1111/3611/6422");
    show_solve("3422/1113/5622");
    //
}
int main(int argc, char** argv) {
    //test_cases();
    cout << "enter the grid, use . for a blank tile, use / for new line, and use numbers/letters for the cells";
    string s;
    getline(cin,s);
    show_solve(s);
    delete table;
    table = nullptr;
    return 0;
}