/r/dailyprogrammer Intermediate 206 by h2g2_researcher

#include <iostream>
#include <array>
#include <cassert>
#include <future>
#include <string>
#ifndef NDEBUG
#include <fstream>
#include <sstream>
#endif

using namespace std;

template <typename T>
bool isPowOf2(T val)
{
    return val == 1 || (val % 2 == 0 && isPowOf2(val / 2));
};

#ifndef NDEBUG
template <class T>
struct FakeFuture{
    T val; T get() const { return val; }; FakeFuture operator=(const T& v) { val = v; return *this; }
};
#endif

/*
Creates an array of 4 tiles. Each sub-tile is SIZE/2.
Tiles are swizzled:
+-+-+
|0|2|
+-+-+
|1|3|
+-+-+
x- left to right, y- is top to bottom.
This keeps data physically close near each other in the cache, for much improved
lookup times when accessing lots of data in the same region.
*/
template <typename T>
class TiledArray
{
    array<T*, 4> data;
    array<T*, 4> buildData(size_t size, T* ptr) const
    {
        const auto stride = size*size/4;
        array<T*, 4> result;
        for (auto i = 0u; i < result.size(); ++i)
        {
            result[i] = ptr + stride*i;
        }
        return result;
    }
    const size_t SIZE;
    char& getValue(size_t x, size_t y) const
    {
        assert(x < SIZE);
        assert(y < SIZE);
        auto nextSize = SIZE / 2;
        const size_t index = (x < nextSize ? 0 : 2) + (y < nextSize ? 0 : 1);
        return (SIZE > 2 ? TiledArray(nextSize, data[index]).at(x%nextSize, y%nextSize) : *data[index]);
    }
public:
    // sideSize must be a power of 2.
    // ptr must point to an array with at elast sideSize^2 elements.
    TiledArray(size_t sideSize, T* ptr) : data(buildData(sideSize, ptr)), SIZE(sideSize)
    {
        assert(isPowOf2(sideSize));
    }
    TiledArray(const TiledArray&) = default;
    TiledArray(TiledArray&& r) : data(move(r.data)), SIZE(r.SIZE) {}

    size_t size() const { return SIZE; }

    static size_t num_elements(size_t size) { assert(isPowOf2(size)); return size*size; }
    static size_t num_subtiles(size_t size) { assert(isPowOf2(size)); return size > 1 ? 1 + 4*num_subtiles(size / 2) : 0; }

    size_t num_elements() const { return num_elements(SIZE); }
    size_t num_subtiles() const { return num_subtiles(SIZE); }

    const T& at(size_t x, size_t y) const
    {
        return getValue(x, y);
    }

    T& at(size_t x, size_t y)
    {
        return getValue(x, y);
    }

    TiledArray<T> getSubtile(unsigned int index) const
    {
        assert(index < 4 && SIZE > 1);
        return TiledArray<T>(SIZE / 2, data[index]);
    }

    T* ptr()
    {
        return data[0];
    }

    const T* ptr() const
    {
        return data[0];
    }

    TiledArray<T> operator=(const TiledArray<T>& r) const
    {
        this->data = r.data;
        this->SIZE = r.SIZE;
        return *this;
    }

    TiledArray<T> operator=(TiledArray<T>&& r) const
    {
        this->data = move(r.data);
        this->SIZE = move(r.SIZE);
        return *this;
    }
};

// results must point to an array with at least 1 element per subtile in arr.
// Counts the number of times val appears, and places this number in results.
// results is also filled for each subarray.
// This will create a lookup table of the number of plants in each tile.
int countElements(const TiledArray<char> arr, int* results, char val, const int* start, const size_t size)
{
    assert(results - start < static_cast<int>(size));
    switch (arr.size())
    {
    case 0:
    case 1:
        assert(false);
        break;
    case 2:
        *results = count(arr.ptr(), arr.ptr() + arr.num_elements(), val);
        break;
    default:
    {
        auto subSize = arr.getSubtile(0).num_subtiles();
#ifdef NDEBUG
        array<future<int>, 4> subResults;
#else
        array<FakeFuture<int>, 4> subResults;
#endif
        for (auto i(0u); i < subResults.size(); ++i)
        {
            auto resultBuffer = results + 1 + i*subSize;
#ifdef NDEBUG
            subResults[i] = async(countElements, arr.getSubtile(i), resultBuffer, val, start, size);
#else
            subResults[i] = countElements(arr.getSubtile(i), resultBuffer, val, start, size);
#endif
        }
        *results = 0;
        for (auto& res : subResults)
        {
            *results += res.get();
        }
    }
    }
    return *results;
}

struct Circle
{
    int x, y, r;
};

bool isPointWithinCircle(int x, int y, const Circle& circle)
{
    x -= circle.x;
    y -= circle.y;
    return (x*x + y*y) < (circle.r*circle.r);
};

// Count the number of 'val' appearences on the specified tile within the specified circle.
// The size cache given *must* be generated using 'val', or else the results are undefined.
int evaluateCircle(const TiledArray<char> data, const int* sizeCache, const Circle& circle, char val)
{
    assert(data.size() > 0);

    // Check for whether the circle is close enough to this tile to affect it.
    if (circle.x < 0 - circle.r || circle.x > static_cast<int>(data.size()) + circle.r
        || circle.y < 0 - circle.r || circle.y > static_cast<int>(data.size()) + circle.r)
    {
        return 0;
    }

    // Check all whether all four corners of the tile are inside the circle.
    const bool topLeft = isPointWithinCircle(0, 0,circle);
    const bool topRight = isPointWithinCircle(data.size() - 1, 0,circle);
    const bool bottomLeft = isPointWithinCircle(0, data.size() - 1,circle);
    const bool bottomRight = isPointWithinCircle(data.size() - 1, data.size() - 1,circle);

    if (data.size() == 1u)
    {
        // Sizecache doesn't go to this resolution, but there's only one square anyway, so just read from it.
        return (data.at(0, 0) == val && (topLeft||topRight||bottomLeft||bottomRight) && circle.x != 0 && circle.y != 0 ? 1 : 0);
    }

    int result = 0;
    if (topLeft && topRight && bottomLeft && bottomRight)
    {
        // Whole tile is covered.
        result = *sizeCache;

        // Check whether we've stomped on a plant.
        if (circle.x < static_cast<int>(data.size()) && circle.x >= 0 && circle.y < static_cast<int>(data.size()) && circle.y >= 0 && data.at(circle.x,circle.y) == val)
            --result;
    }
    else
    {
        int sizeCacheStride = data.getSubtile(0).num_subtiles();
        for (int i(0); i < 4; ++i)
        {
            int x = i < 2 ? 0 : data.size() / 2;
            int y = i % 2 == 0 ? 0 : data.size() / 2;
            result += evaluateCircle(data.getSubtile(i), sizeCache + 1 + i*sizeCacheStride, { circle.x - x, circle.y - y, circle.r }, val);
        }
    }
    return result;
}

struct Result
{
    int x, y, value;
};


// Each tile gets searched in its own thread.
vector<Result> searchForMaximum(const TiledArray<char>& masterData, const int* masterSizeCache,
    const TiledArray<char>& thisData, const int* thisSizeCache, int topLeftX, int topLeftY, int radius, char val)
{
    if (thisData.size() == 1)
    {
        return vector<Result>{{ topLeftX, topLeftY, evaluateCircle(masterData, masterSizeCache, { topLeftX, topLeftY, radius }, val) }};
    }
    else
    {
#ifdef NDEBUG
        array<future<vector<Result>>, 4> subResults;
#else
        array<FakeFuture<vector<Result>>, 4> subResults;
#endif
        for (auto i(0u); i < subResults.size(); ++i)
        {
            auto subTile = thisData.getSubtile(i);
            const int* sizeCache = thisSizeCache + 1 + i*subTile.num_subtiles();
            int x = topLeftX + (i < 2 ? 0 : subTile.size());
            int y = topLeftY + (i % 2 == 0 ? 0 : subTile.size());
            // Search subtiles recursively.
#ifdef NDEBUG
            subResults[i] = async(searchForMaximum, masterData, masterSizeCache, subTile, sizeCache, x, y, radius, val);
#else
            subResults[i] = searchForMaximum(masterData, masterSizeCache, subTile, sizeCache, x, y, radius, val);
#endif
        }
        // result stores ALL the best results.
        vector<Result> result;
        int currentBest = -1;
        for (auto& fres : subResults)
        {
            auto res = fres.get();
            if (res.front().value > currentBest)
            {
                result = res;
                currentBest = res.front().value;
            }
            else if (res.front().value == currentBest)
            {
                move(begin(res), end(res), back_inserter(result));
            }
        }
        return result;
    }
}

#ifndef NDEBUG
// Saves me typing/pasting/piping in test inputs all the time when debugging.
istringstream input{
    "4 4 2\n"
    "....\n"
    "....\n"
    "..x.\n"
    "....\n"
};
#define cin input
#endif

int main()
{
    int height, width, radius;
    cin >> height >> width >> radius;
    cin.ignore();
    int requiredSize = 1;
    while (requiredSize < height || requiredSize < width)
        requiredSize *= 2;

    // Create a tiled data buffer to hold the data
    cout << "Building data buffer.\n";
    vector<char> dataBuffer(TiledArray<char>::num_elements(requiredSize), ' ');
    TiledArray<char> data(requiredSize,dataBuffer.data());

#ifndef NDEBUG
    int nPlants = 0;
    ofstream dataMirror{ "raw_data.txt" };
#endif

    // Read data into the array.
    cout << "Reading in data.\n";
    for (int row(0); row < height; ++row)
    {
        string line;
        getline(cin, line);
        assert(line.size() >= static_cast<size_t>(width));
        for (int col(0); col < width; ++col)
        {
            data.at(col, row) = line.at(col);
#ifndef NDEBUG
            if (line.at(col) == 'x')
            {
                nPlants++;
            }
#endif
        }
#ifndef NDEBUG
        dataMirror << line << '\n';
#endif
    }
#ifndef NDEBUG
    dataMirror << "Plants found: " << nPlants;
#endif

    cout << "Creating a size cache.\n";
    vector<int> sizeCache( data.num_subtiles(), -1 );
    countElements(data, sizeCache.data(), 'x',sizeCache.data(),sizeCache.size());

    // Do the search
    cout << "Searching...\n";
    auto results = searchForMaximum(data, sizeCache.data(), data, sizeCache.data(), 0, 0, radius, 'x');

    // Output the results.
    for (auto& res : results)
    {
        cout << "Sprinkler at (" << res.x << ',' << res.y << ") covers " << res.value << " plants.\n";

        // The map:

        for (int row(0); row < height; ++row)
        {
            for (int col(0); col < width; ++col)
            {
                auto watered = isPointWithinCircle(col, row, { res.x, res.y, radius });
                auto plant = data.at(col, row) == 'x';
                auto isSprinkler = row == res.y && col == res.x;
                auto val = isSprinkler ? 'O' : (watered ? (plant ? '$' : '~') : (plant ? 'x' : '.'));
                cout << val;
            }
            cout << '\n';
        }
    }
#ifndef NDEBUG
    // Dumping some raw buffers to files allows me to check that the analysis was sane.
    ofstream dataBufferFile{ "data_buffer.txt" };
    dataBufferFile << "Address: 0x" << reinterpret_cast<void*>(dataBuffer.data())
        << " size: " << dataBuffer.size() << '\n';

    copy(begin(dataBuffer), end(dataBuffer), ostream_iterator<char>(dataBufferFile));

    ofstream sizeCacheFile{ "size_cache.txt" };
    sizeCacheFile << "Address: 0x" << reinterpret_cast<void*>(sizeCache.data())
        << " size: " << sizeCache.size()*sizeof(int) << " (" << sizeCache.size() << ") elements." << '\n';
    copy(begin(sizeCache), end(sizeCache), ostream_iterator<int>(sizeCacheFile, "\n"));
#endif
}