#include <bits/stdc++.h>

using namespace std;

//*************************************************************
// HackerRank Prepare > Algorithms > Implementation: Encryption
//*************************************************************

// An English text needs to be encrypted using an encryption scheme. First,
// the spaces are removed from the text. Let L be the length of this
// text. Then, characters are written into a grid, whose rows and columns
// have the following constraints:
//
//      floor(sqrtL) <= row <= cols <= ceil(sqrtL)
//
// The encoded message is obtained by displaying the characters of each
// column, with a space between column texts.

string encryption(string s) {
    s.erase(remove_if(s.begin(),
                      s.end(),
                      [](uint8_t x){return isspace(x);}),
            s.end());
                                                
    double sqrtL = sqrt(s.size());
    size_t rows = floor(sqrtL);
    size_t cols = ceil(sqrtL);
    
    // ensure that rows x cols >= L

    // If multiple grids satisfy the above conditions, choose the one
    // with the minimum area, i.e. rows x cols

    while (rows * cols < s.size())
    {
        if (rows < cols)
            rows++;
        else
            cols++;
    }
    
    cout << "L: " << s.size() << " sqrtL: " << sqrtL << " rows: " << rows << " cols:  " << cols << endl;

    string result;

    // display the grid
    for (size_t row = 0; row < rows; row++)
    {
        cout << s.substr(row * cols, cols);
        cout << endl;
    }

    for (size_t col = 0; col < cols; col++)
    {
        for (size_t row = 0; row < rows; row++)
        {
            if (row * cols + col < s.size())
            {                
                result.push_back(s.at(row * cols + col));
            }
        }
        result.push_back(' ');
    }
    
    return result;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string s;
    //getline(cin, s);
    vector<string> input  = {"haveaniceday", "feedthedog", "chillout", "if man was meant to stay on the ground god would have given us roots"};
    vector<string> expected = {"hae and via ecy", "fto ehg ee dd", "clu hlt io", "imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau"};

    for (size_t i = 0; i < input.size(); i++)
    {
        string result = encryption(input[i]);
        cout << input[i] << endl;
        cout << result << endl;
        cout << expected[i] << endl;
        cout << "----------------" << endl;
    }

    return 0;
}