task143.cpp

#include <iostream>
#include <vector>
#include <iterator>
#include <iomanip>
#include <string>
#include <tuple>

using namespace std;

using matrix = vector<vector<unsigned int>>;

namespace {

// number of digits in a number
unsigned long GetWidth(unsigned long n) {
    unsigned long r = 1;
    for (; n; ++r, n = n / 10);
    return r;
}

// prints 2D array. Zero element is replaced with spaces
void PrintArray(const matrix &a, unsigned long n) {
    auto width = GetWidth(2 * n - 1);

    for (const auto &row : a) {
        for (auto e : row) {
            if (e) {
                cout << std::setw(width) << e << " ";
            } else {
                cout << string(width + 1, ' ');
            }
        }
        cout << endl;
    };
}

}


// Собственно поэлементно рисуем раскладку в порядке увеличения
// номеров блоков. Для этого используем простенькую state-machine
// где состояние отвечает за рисование одной линии. Двигаемся
// по одному элементу за раз.
namespace method1
{

using StateHandler = bool (*)(const matrix& a, unsigned int n, int& r, int& c, int& it);

bool LeftRightHandler(const matrix& a, unsigned int n, int& r, int& c, int& it)
{
    if (c+1 < 2*n-1 && a[r][c+1] == 0) {
        ++c;
        return false;
    }
    return true;
};

bool LeftUpHandler(const matrix& a, unsigned int n, int& r, int& c, int& it)
{
    if (r-1 >= it && a[r-1][c-1] == 0) {
        --c;
        --r;
        return false;
    }
    return true;
};

bool LeftDownHandler(const matrix& a, unsigned int n, int& r, int& c, int& it)
{
    if (r+1 < n && a[r+1][c-1] == 0) {
        --c;
        ++r;
        return false;
    }
    ++it;
    return true;
};

StateHandler Handlers[] = {LeftRightHandler, LeftUpHandler, LeftDownHandler};

void Solve(unsigned int n) {
    matrix a(n, vector<unsigned int>(2*n-1));
    int r = n-1, c = 0;
    int state = 0;
    bool stateChange = false;
    unsigned int current = 1;
    int it = 0;

    do {
        if (stateChange) {
            state = (state + 1) % 3;
        } else {
            a[r][c] = current++;
        }
        stateChange = Handlers[state](a, n, r, c, it);
    } while (current < n*n+1);

    PrintArray(a, n);
}

}

// На задачу можно посмореть так, сначала рисуем "оболочку"
// пирамиды, потом решаем аналогичную задачу рисования пирамиды
// внутри пирамиды и т.д. DrawPyramid рисует пирамиду без внутренностей
namespace method2
{

struct Box
{
    int x1,y1,x2,y2;
};

unsigned int DrawPyramid(matrix& a, unsigned long n, const Box& b, unsigned int current)
{
    for (auto c = b.x1; c <= b.x2; ++c) a[b.y2][c] = current++;
    auto x = b.x2;
    auto y = b.y2;
    if (current < n*n+1)
        for (auto i = b.y1; i < b.y2; ++i) a[--y][--x] = current++;
    if (current < n*n+1)
        for (auto i = b.y1+1; i < b.y2; ++i) a[++y][--x] = current++;
    return current;
}

void Solve(unsigned int n)
{
    matrix a(n, vector<unsigned int>(2*n-1));

    Box rect = {0, 0, (int)(2*n-2), (int)(n-1)};
    unsigned int current = 1;

    while(rect.y1 <= rect.y2) {
        current = DrawPyramid(a, n, rect, current);
        rect.x1 += 2;
        ++rect.y1;
        rect.x2 -= 2;
        --rect.y2;
    }

    PrintArray(a, n);
}

};

// У предыдущих алгоритмов есть один фатальный недостаток
// Они используют дополниельную память. Алгоритм ниже этого
// не делает, для заданных коодинат он возвращает либо номер блока
// пирамиды , либо ноль если блок с коордигатами к пирамиде не относится
namespace method3
{
// возврящает длину основания, стороны и смещение
tuple<unsigned int, unsigned int, unsigned int> GetIterationParams(unsigned int it,unsigned int n)
{
    unsigned int side1 = 2*(n-2*it)-1;
    unsigned int side2 = side1 > 2 ? ((side1 - 2) >> 1) : 0;
    return std::make_tuple(side1, side2, 2*it);
}

// для номера итерации возврящаяет начальный номер
// используется цикл
unsigned int GetIterationStart(unsigned int it,unsigned int n)
{
    unsigned int count = 1;
    for(unsigned int i = 0; i < it; ++i, n-= 2) {
        unsigned int number = 2*(2*n-1)-2;
        count += number;
    }
    return count;
}

// для номера итерации возврящаяет начальный номер
// делает это без использования цикла
unsigned int GetIterationStart1(unsigned int it,unsigned int n)
{
    unsigned int count = 1;
    if (it > 0)
        count += it*(4*n-4) - 8*((it-1)*it)/2;
    return count;
}


unsigned int GetValueAtPosition(unsigned int r, unsigned int c, unsigned int n)
{
    unsigned int center_x = ((2*n) >> 1) - 1;
    int x = c - center_x;
    if (abs(x) <= r) {
        if (2*abs((int)r-abs(x)) <= n) {
            int it = abs((int)r-abs(x));
            auto start = GetIterationStart(it,n);
            auto counts = GetIterationParams(it,n);
            if (it < n-1-r) {
                return start + std::get<0>(counts) + std::get<1>(counts) - x;
            }
        }
        int it = n - 1 - r;
        auto start = GetIterationStart(it,n);
        auto counts = GetIterationParams(it,n);
        return start + c - std::get<2>(counts);
    }
    return 0;
}

void Solve(unsigned int n)
{
    auto width = GetWidth(2*n-1);

    for (unsigned int r = 0; r < n; ++r) {
        for (unsigned int c = 0; c < 2*n-1; ++c) {
            auto e = GetValueAtPosition(r, c, n);
            if (e) {
                cout << std::setw(width) << e << " ";
            } else {
                cout << string(width+1, ' ');
            }
        }
        cout << endl;
    }
}

};

int main() {
    for (int i = 1; i < 11; ++i) {
        cout << endl << "Pyramid of height " << i << endl;

        method1::Solve(i);
        method2::Solve(i);
        method3::Solve(i);
    }
    return 0;
}