[Vilor]

Сообщение от Vilor Прикрепил фигурки в dwg.

[Дмитррр]

Сообщение от Vilor напишите сколько времени заняло решение?

За минут 10 нашёл решение если разрешить переворачивать фигуры на другую сторону. Без этого разрешения дальше думать лень пока. Да и неизвестно, запрещён ли переворот фигур на другую сторону.

[Vilor]

Сообщение от Дмитррр запрещён ли переворот фигур

фигуры чур не переворачивать (в смысле поворачивать конечно можно, а вот "зеркалить" - нет).

[Pavel_V]

У блоков ручки в неудобных местах. Лень переделывать. Ну неужели трудно было в углах, а не в центре сделать базовые точки?

[BURAN988]

Сообщение от Vilor Прикрепил фигурки в dwg.

DWG-тетрис?

[Дмитррр]

Что-то без переворота/отзеркаливания не хочет собираться. Тут возникает другой вопрос. Как доказать, что сбор невозможен, если он невозможен...

[Vilor]

Сообщение от Дмитррр Что-то без переворота/отзеркаливания не хочет собираться

нарисуй пжста решение с переворачиванием.

Сообщение от Дмитррр Как доказать, что сбор невозможен, если он невозможен

а может возможен?
на первых этапах мне тоже захотелось понять решаема ли задача. Например: посчитать количество одинарных/ двойных / тройных сторон с внутренними углами - которые точно будут соприкасаться с другими фигурами, но понял, что подходящих для внутренних углов вариантов наружных углов фигур всегда больше. Поэтому остановился на том, что количество исходных составляющих фигуры прямоугольников и площадь заданного прямоугольника сверил - сошлось. Если развивать тему то это наверное выйдет в классификацию типа <внутренний угол без выступа за границы угла> / <внутренний угол с выступом за границы угла через 1 клетку справа> / <внутренний угол с выступом за границы угла через 1 клетку слева> и т.д.... . ChatGPT понял несколько фигур, но советы раздает как построить домик или собрать человечка, а не вписать. Поэтому забросил это описание, ибо математику начальной школы предпочитаю проверять автоматизированными способами - слишком сложно. Проще подбором в каждое место текущей сборки каждую фигуру каким-нибудь скриптом тыкать и тогда этот скрипт и скажет решаемо или нет.

----- добавлено через ~2 мин. -----

Сообщение от BURAN988 DWG-тетрис?

точно

[Fogel]

В принципе оно можно... берём фигурку, и поочерёдно помещаем во все точки - 12*5*4 - 240 вариантов. Проверяем на габаритные условия (чтоб не вылезала) проверяем чтоб "глухих" углов не оставляла в которые уже ничего не войдёт... Выходит 160 вариантов (условно). Делаем для всех фигурок и начинаем комбинировать варианты. Сдаётся мне, что сиё можно сделать даже в экселе, правда вот сколько он будет считать... Подобным образом я решил получить все варианты расположения цифр в судоку, так бедняга двое суток пыхтел

[Нубий-IV]

Сообщение от Fogel берём фигурку, и поочерёдно помещаем во все точки - 12*5*4 - 240 вариантов

Есть версия перебора фильтрацией списков: Ферзи и множества. Кто на Лиспе пишет - должно зайти. Автокад же ж.

[Дмитррр]

Сообщение от Нубий-IV Кто на Лиспе пишет - должно зайти. Автокад же ж.

Тут любой язык программирования сгодится. И автокад не нужен. Берём матрицу 5х12 и перебором пробуем заполнить её блоками.Задача хоть не совсем примитивная, но и совсем сложной её не назвать.

Сообщение от Vilor нарисуй пжста решение с переворачиванием.

[Нубий-IV]

Сообщение от Дмитррр Тут любой язык программирования сгодится

Ну ОК, плюсы так плюсы. Сначала на выходных было скучно, а потом весело:

Код:

[Выделить все]

 
#include <algorithm>
#include <assert.h>
#include <climits>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>

/************************************* ID *************************************/

class ID
{
public:
    operator int() const
    {
        return m_id;
    }

    bool operator==(ID id) const
    {
        return m_id == id.m_id;
    }

    bool operator!=(ID id) const
    {
        return m_id != id.m_id;
    }

    static ID const Empty;

private:
    friend class IDGenerator;

    ID(int id)
        : m_id(id)
    {
        assert(id >= 0);
    }

    int m_id;
};

ID const ID::Empty = {0};

/******************************** IDGenerator *********************************/

class IDGenerator
{
public:
    ID get_next_id()
    {
        return ID(++m_count);
    }

    int get_count() const
    {
        return m_count;
    }

private:
    int m_count = 0;
};

/*********************************** Point ************************************/

struct Point
{
    explicit Point(int x, int y)
        : x(x), y(y)
    {
    }

    bool operator==(Point p) const
    {
        return x == p.x && y == p.y;
    }

    bool operator!=(Point p) const
    {
        return x != p.x || y != p.y;
    }

    bool operator<(Point p) const
    {
        if (y < p.y)
            return true;

        if (y > p.y)
            return false;

        return x < p.x;
    }

    int x;
    int y;
};

/********************************* FieldSize **********************************/

struct FieldSize
{
    explicit FieldSize(int width, int height)
        : width(width), height(height)
    {
        assert(width > 0);
        assert(height > 0);
    }

    int width;
    int height;
};

/********************************** Rotation **********************************/

Point rotate_0(Point point)
{
    return Point{point.x, point.y};
}

Point rotate_90(Point point)
{
    return Point{-point.y, point.x};
}

Point rotate_180(Point point)
{
    return Point{-point.x, -point.y};
}

Point rotate_270(Point point)
{
    return Point{point.y, -point.x};
}

using Rotation = Point (*)(Point);

/********************************** Position **********************************/

class Position
{
public:
    Position(FieldSize size,
             std::vector<Point> const &points,
             Rotation rotate)
        : m_field_size(size)
    {
        assert(size.width > 0);
        assert(size.height > 0);
        assert(points.size() > 0);

        int x_min = INT_MAX;
        int y_min = INT_MAX;
        int x_max = 0;
        int y_max = 0;

        for (Point const point : points)
        {
            Point const rotated_point = rotate(point);

            x_min = std::min(x_min, rotated_point.x);
            y_min = std::min(y_min, rotated_point.y);
            x_max = std::max(x_max, rotated_point.x);
            y_max = std::max(y_max, rotated_point.y);
        }

        m_width = x_max - x_min;
        m_height = y_max - y_min;

        m_num_positions_x = std::max(0, m_field_size.width - m_width);
        m_num_positions_y = std::max(0, m_field_size.height - m_height);
        m_num_positions = m_num_positions_x * m_num_positions_y;

        m_points_normilized.reserve(points.size());
        for (Point const point : points)
        {
            Point const rotated_point = rotate(point);
            Point const normilized_point{rotated_point.x - x_min,
                                         rotated_point.y - y_min};
            m_points_normilized.push_back(normilized_point);
        }

        std::sort(m_points_normilized.begin(), m_points_normilized.end());
    }

    int get_num_positions() const
    {
        return m_num_positions;
    }

    void export_to(std::vector<Point> &points) const
    {
        for (int y = 0; y < m_num_positions_y; ++y)
            for (int x = 0; x < m_num_positions_x; ++x)
                for (Point const point : m_points_normilized)
                    points.push_back(Point{point.x + x, point.y + y});
    }

    bool operator==(Position const &p) const
    {
        assert(m_points_normilized.size() == p.m_points_normilized.size());

        return m_width == p.m_width &&
               m_height == p.m_height &&
               std::equal(m_points_normilized.begin(),
                          m_points_normilized.end(),
                          p.m_points_normilized.begin());
    }

private:
    FieldSize m_field_size;
    int m_width;
    int m_height;
    int m_num_positions_x;
    int m_num_positions_y;
    int m_num_positions;
    std::vector<Point> m_points_normilized;
};

/*********************************** Shape ************************************/

class Shape
{
public:
    Shape(ID id,
          FieldSize size,
          std::vector<Point> const &points)
        : m_id(id),
          m_num_points(points.size()),
          m_num_positions(0),
          m_current_pos(0)
    {
        assert(size.width > 0);
        assert(size.height > 0);
        assert(points.size() > 0);

        Position positions_candidates[] = {
            Position(size, points, rotate_0),
            Position(size, points, rotate_90),
            Position(size, points, rotate_180),
            Position(size, points, rotate_270)};

        std::vector<Position const *> positions;

        for (Position const &position : positions_candidates)
            if (position.get_num_positions() != 0)
            {
                bool duplicate = false;

                for (int i = 0; i < positions.size(); ++i)
                    if (position == *positions[i])
                    {
                        duplicate = true;
                        break;
                    }

                if (!duplicate)
                {
                    positions.push_back(&position);
                    m_num_positions += position.get_num_positions();
                }
            }

        m_positions_points.reserve(m_num_positions * m_num_points);

        for (Position const *position : positions)
            position->export_to(m_positions_points);

        assert(m_positions_points.size() == m_num_positions * m_num_points);
    }

    ID get_id() const
    {
        return m_id;
    }

    int get_num_points() const
    {
        return m_num_points;
    }

    Point get_point(int index) const
    {
        assert(index >= 0);
        assert(index < m_num_points);
        assert(m_current_pos + index < m_positions_points.size());

        return m_positions_points[m_current_pos + index];
    }

    int get_num_positions() const
    {
        return m_num_positions;
    }

    void move_to_position(int position_index)
    {
        assert(position_index < m_num_positions);
        assert(position_index * m_num_points < m_positions_points.size());

        m_current_pos = position_index * m_num_points;
    }

private:
    ID m_id;
    size_t m_num_points;
    size_t m_num_positions;
    size_t m_current_pos;
    std::vector<Point> m_positions_points;
};

/*********************************** Field ************************************/

class Field
{
public:
    Field(FieldSize size)
        : m_size(size),
          m_num_points(size.width * size.height),
          m_num_points_filled(0),
          m_field(m_num_points, ID::Empty)
    {
        assert(size.width > 0);
        assert(size.height > 0);
    }

    FieldSize get_size() const
    {
        return m_size;
    }

    bool is_full() const
    {
        return m_num_points_filled == m_num_points;
    }

    bool put_down(Shape const &shape)
    {
        ID const shape_id = shape.get_id();
        int const num_shape_points = shape.get_num_points();

        for (int i = 0; i < num_shape_points; ++i)
        {
            Point const point = shape.get_point(i);

            assert(point.x >= 0);
            assert(point.y >= 0);
            assert(point.x < m_size.width);
            assert(point.y < m_size.height);

            ID &field_id = id_at(point.x, point.y);
            if (field_id == ID::Empty)
                field_id = shape_id;
            else
            {
                for (int j = 0; j < i; j++)
                {
                    Point const point = shape.get_point(j);
                    id_at(point.x, point.y) = ID::Empty;
                }
                return false;
            }
        }
        m_num_points_filled += num_shape_points;
        return true;
    }

    void put_up(Shape const &shape)
    {
        ID const shape_id = shape.get_id();
        int const num_shape_points = shape.get_num_points();

        for (int i = 0; i < num_shape_points; ++i)
        {
            Point const point = shape.get_point(i);

            assert(point.x >= 0);
            assert(point.y >= 0);
            assert(point.x < m_size.width);
            assert(point.y < m_size.height);
            assert(id_at(point.x, point.y) == shape.get_id());

            id_at(point.x, point.y) = ID::Empty;
        }
        m_num_points_filled -= num_shape_points;

        assert(m_num_points_filled >= 0);
    }

    ID get_id(int x, int y) const
    {
        assert(x >= 0);
        assert(y >= 0);
        assert(x < m_size.width);
        assert(y < m_size.height);

        return id_at(x, y);
    }

private:
    ID &id_at(int x, int y)
    {
        assert(x >= 0);
        assert(y >= 0);
        assert(x < m_size.width);
        assert(y < m_size.height);

        return m_field[x + m_size.width * y];
    }

    ID const &id_at(int x, int y) const
    {
        assert(x >= 0);
        assert(y >= 0);
        assert(x < m_size.width);
        assert(y < m_size.height);

        return m_field[x + m_size.width * y];
    }

    FieldSize m_size;
    int m_num_points;
    int m_num_points_filled;
    std::vector<ID> m_field;
};

/******************************** ConsoleWriter *******************************/

struct ConsoleWriter
{
    char char_by_id(ID id)
    {
        assert(id >= 0);
        assert(id < 2 * 26);

        if (id == ID::Empty)
            return ' ';
        else
            return 'A' + id - 1;
    }

    void write(Field const &field)
    {
        FieldSize const size = field.get_size();

        std::cout << '+' << std::string(size.width, '-') << "+\n";
        for (int y = 0; y < size.height; ++y)
        {
            std::cout << '|';
            for (int x = 0; x < size.width; ++x)
                std::cout << char_by_id(field.get_id(x, y));
            std::cout << "|\n";
        }
        std::cout << '+' << std::string(size.width, '-') << "+\n\n" << std::flush;
    }
};

/********************************** Tangram ***********************************/

class Tangram
{
public:
    Tangram(FieldSize size)
        : m_field(size)
    {
        assert(size.width > 0);
        assert(size.height > 0);
    }

    Tangram &reserve_shapes(int num_shapes)
    {
        assert(num_shapes > 0);

        m_shapes.reserve(num_shapes);
        return *this;
    }

    Tangram &add_shape(std::vector<Point> const &points)
    {
        assert(points.size() > 0);

        m_shapes.emplace_back(Shape(m_id_generator.get_next_id(),
                                    m_field.get_size(),
                                    points));
        return *this;
    }

    void solve()
    {
        place_shape(0);
    }

private:
    void place_shape(int shape_index)
    {
        assert(shape_index >= 0);
        assert(shape_index <= m_shapes.size());

        if (shape_index == m_shapes.size() || m_field.is_full())
        {
            m_console_writer.write(m_field);
            return;
        }

        Shape &shape = m_shapes[shape_index];
        int const num_poisitions = shape.get_num_positions();

        for (int pos = 0; pos < num_poisitions; ++pos)
        {
            shape.move_to_position(pos);

            if (m_field.put_down(shape))
            {
                place_shape(shape_index + 1);
                m_field.put_up(shape);
            }
        }
    }

    Field m_field;
    std::vector<Shape> m_shapes;
    IDGenerator m_id_generator;
    ConsoleWriter m_console_writer;
};

/************************************ Test ************************************/

#define TEST(name)        \
    std::cerr << "TEST: " \
              << name << '\n';

#define CHECK(expr)                            \
    if (!(expr))                               \
    {                                          \
        std::cerr << "TEST: FAILED: "          \
                  << #expr                     \
                  << " (" << __FILE__          \
                  << ':' << __LINE__ << ")\n"; \
        return false;                          \
    }

#define STATUS()                 \
    std::cerr << "TEST: OK\n\n"; \
    return true;

/********************************** Test Set **********************************/

bool test_Id()
{
    TEST("Id");

    IDGenerator generator;
    ID id1 = generator.get_next_id();
    ID id2 = generator.get_next_id();

    CHECK(generator.get_count() == 2);
    CHECK(!(id1 == ID::Empty));
    CHECK(!(id2 == ID::Empty));
    CHECK(!(id1 == id2));
    CHECK(id1 != ID::Empty);
    CHECK(id2 != ID::Empty);
    CHECK(id1 != id2);

    STATUS();
}

bool test_Point()
{
    TEST("Point");

    Point p1{0, 0};
    Point p2{1, 0};
    Point p3{0, 1};

    CHECK((p1 == p1) == true);
    CHECK((p2 == p2) == true);
    CHECK((p3 == p3) == true);

    CHECK((p1 != p2) == true);
    CHECK((p2 != p1) == true);

    CHECK((p1 != p3) == true);
    CHECK((p3 != p1) == true);

    CHECK((p2 != p3) == true);
    CHECK((p3 != p2) == true);

    CHECK((p1 < p1) == false);
    CHECK((p2 < p2) == false);
    CHECK((p3 < p3) == false);

    if ((p1 < p2) == true)
        CHECK((p2 < p1) == false);
    if ((p2 < p1) == true)
        CHECK((p1 < p2) == false);

    if ((p1 < p3) == true)
        CHECK((p3 < p1) == false);
    if ((p3 < p1) == true)
        CHECK((p1 < p3) == false);

    if ((p2 < p3) == true)
        CHECK((p3 < p2) == false);
    if ((p3 < p2) == true)
        CHECK((p2 < p3) == false);

    if ((p1 < p2) == true && (p2 < p3) == true)
        CHECK((p1 < p3) == true);
    if ((p1 < p3) == true && (p3 < p2) == true)
        CHECK((p1 < p2) == true);

    if ((p2 < p1) == true && (p1 < p3) == true)
        CHECK((p2 < p3) == true);
    if ((p2 < p3) == true && (p3 < p1) == true)
        CHECK((p2 < p1) == true);

    if ((p3 < p1) == true && (p1 < p2) == true)
        CHECK((p3 < p2) == true);
    if ((p3 < p1) == true && (p2 < p1) == true)
        CHECK((p3 < p1) == true);

    STATUS();
}

bool test_Rotation()
{
    TEST("Rotation");

    Point p{1, 2};

    CHECK(rotate_0(p) == Point(1, 2));
    CHECK(rotate_90(p) == Point(-2, 1));
    CHECK(rotate_180(p) == Point(-1, -2));
    CHECK(rotate_270(p) == Point(2, -1));

    STATUS();
}

bool test_Position()
{
    TEST("Position");

    {
        using P = Position;
        using FS = FieldSize;

        std::vector<Point> shape{Point{0, 0}};

        CHECK(P(FS{1, 1}, shape, rotate_0).get_num_positions() == 1);
        CHECK(P(FS{1, 2}, shape, rotate_0).get_num_positions() == 2);
        CHECK(P(FS{2, 1}, shape, rotate_0).get_num_positions() == 2);
        CHECK(P(FS{2, 2}, shape, rotate_0).get_num_positions() == 4);
    }
    {
        using P = Position;
        using FS = FieldSize;

        std::vector<Point> shape{Point{0, 0}};

        CHECK(P(FS{1, 1}, shape, rotate_0) == P(FS{1, 1}, shape, rotate_90));
        CHECK(P(FS{1, 1}, shape, rotate_0) == P(FS{1, 1}, shape, rotate_180));
        CHECK(P(FS{1, 1}, shape, rotate_0) == P(FS{1, 1}, shape, rotate_270));

        CHECK(P(FS{1, 1}, shape, rotate_90).get_num_positions() == 1);
        CHECK(P(FS{1, 2}, shape, rotate_90).get_num_positions() == 2);
        CHECK(P(FS{2, 1}, shape, rotate_90).get_num_positions() == 2);
        CHECK(P(FS{2, 2}, shape, rotate_90).get_num_positions() == 4);

        CHECK(P(FS{1, 1}, shape, rotate_180).get_num_positions() == 1);
        CHECK(P(FS{1, 2}, shape, rotate_180).get_num_positions() == 2);
        CHECK(P(FS{2, 1}, shape, rotate_180).get_num_positions() == 2);
        CHECK(P(FS{2, 2}, shape, rotate_180).get_num_positions() == 4);

        CHECK(P(FS{1, 1}, shape, rotate_270).get_num_positions() == 1);
        CHECK(P(FS{1, 2}, shape, rotate_270).get_num_positions() == 2);
        CHECK(P(FS{2, 1}, shape, rotate_270).get_num_positions() == 2);
        CHECK(P(FS{2, 2}, shape, rotate_270).get_num_positions() == 4);
    }
    {
        using P = Position;
        using FS = FieldSize;

        std::vector<Point> shape{Point{0, 0}, Point{1, 0}};

        CHECK(P(FS{1, 1}, shape, rotate_0).get_num_positions() == 0);
        CHECK(P(FS{1, 2}, shape, rotate_0).get_num_positions() == 0);
        CHECK(P(FS{2, 1}, shape, rotate_0).get_num_positions() == 1);
        CHECK(P(FS{2, 2}, shape, rotate_0).get_num_positions() == 2);
        CHECK(P(FS{3, 2}, shape, rotate_0).get_num_positions() == 4);
        CHECK(P(FS{3, 3}, shape, rotate_0).get_num_positions() == 6);
    }
    {
        using P = Position;
        using FS = FieldSize;

        std::vector<Point> shape{Point{0, 0}, Point{1, 0}};

        CHECK(P(FS{1, 1}, shape, rotate_90).get_num_positions() == 0);
        CHECK(P(FS{1, 2}, shape, rotate_90).get_num_positions() == 1);
        CHECK(P(FS{2, 1}, shape, rotate_90).get_num_positions() == 0);
        CHECK(P(FS{2, 2}, shape, rotate_90).get_num_positions() == 2);
        CHECK(P(FS{3, 2}, shape, rotate_90).get_num_positions() == 3);
        CHECK(P(FS{3, 3}, shape, rotate_90).get_num_positions() == 6);

        CHECK(P(FS{1, 1}, shape, rotate_180).get_num_positions() == 0);
        CHECK(P(FS{1, 2}, shape, rotate_180).get_num_positions() == 0);
        CHECK(P(FS{2, 1}, shape, rotate_180).get_num_positions() == 1);
        CHECK(P(FS{2, 2}, shape, rotate_180).get_num_positions() == 2);
        CHECK(P(FS{3, 2}, shape, rotate_180).get_num_positions() == 4);
        CHECK(P(FS{3, 3}, shape, rotate_180).get_num_positions() == 6);

        CHECK(P(FS{1, 1}, shape, rotate_270).get_num_positions() == 0);
        CHECK(P(FS{1, 2}, shape, rotate_270).get_num_positions() == 1);
        CHECK(P(FS{2, 1}, shape, rotate_270).get_num_positions() == 0);
        CHECK(P(FS{2, 2}, shape, rotate_270).get_num_positions() == 2);
        CHECK(P(FS{3, 2}, shape, rotate_270).get_num_positions() == 3);
        CHECK(P(FS{3, 3}, shape, rotate_270).get_num_positions() == 6);
    }
    {
        std::vector<Point> shape{Point{0, 0}, Point{1, 0}};
        Position position(FieldSize{3, 2}, shape, rotate_0);
        int num_positions = position.get_num_positions();

        CHECK(num_positions == 4);

        std::vector<Point> positions;
        positions.reserve(num_positions * shape.size());
        position.export_to(positions);

        CHECK(positions[0] == Point(0, 0));
        CHECK(positions[1] == Point(1, 0));

        CHECK(positions[2] == Point(1, 0));
        CHECK(positions[3] == Point(2, 0));

        CHECK(positions[4] == Point(0, 1));
        CHECK(positions[5] == Point(1, 1));

        CHECK(positions[6] == Point(1, 1));
        CHECK(positions[7] == Point(2, 1));
    }

    STATUS();
}

bool test_Shape()
{
    TEST("Shape");

    {
        IDGenerator gen;
        ID id = gen.get_next_id();
        std::vector<Point> points{Point{0, 0}};
        Shape shape(id, FieldSize{1, 1}, points);

        CHECK(shape.get_id() == id);
        CHECK(shape.get_num_points() == 1);
        CHECK(shape.get_num_positions() == 1);
        CHECK(shape.get_point(0) == Point(0, 0));
        shape.move_to_position(0);
        CHECK(shape.get_point(0) == Point(0, 0));
    }
    {
        IDGenerator gen;
        ID id = gen.get_next_id();
        std::vector<Point> points{Point{0, 0}};
        Shape shape(id, FieldSize{2, 1}, points);

        CHECK(shape.get_id() == id);
        CHECK(shape.get_num_points() == 1);
        CHECK(shape.get_num_positions() == 2);
        shape.move_to_position(0);
        CHECK(shape.get_point(0) == Point(0, 0));
        shape.move_to_position(1);
        CHECK(shape.get_point(0) == Point(1, 0));
    }
    {
        IDGenerator gen;
        ID id = gen.get_next_id();
        std::vector<Point> points{Point{0, 0}, Point{1, 0}};
        Shape shape(id, FieldSize{2, 1}, points);

        CHECK(shape.get_id() == id);
        CHECK(shape.get_num_points() == 2);
        CHECK(shape.get_num_positions() == 1);
        CHECK(shape.get_point(0) == Point(0, 0));
        CHECK(shape.get_point(1) == Point(1, 0));
        shape.move_to_position(0);
        CHECK(shape.get_point(0) == Point(0, 0));
        CHECK(shape.get_point(1) == Point(1, 0));
    }
    {
        IDGenerator gen;
        ID id = gen.get_next_id();
        std::vector<Point> points{Point{0, 0}, Point{0, 1}};
        Shape shape(id, FieldSize{2, 1}, points);

        CHECK(shape.get_id() == id);
        CHECK(shape.get_num_points() == 2);
        CHECK(shape.get_num_positions() == 1);
        CHECK(shape.get_point(0) == Point(0, 0));
        CHECK(shape.get_point(1) == Point(1, 0));
        shape.move_to_position(0);
        CHECK(shape.get_point(0) == Point(0, 0));
        CHECK(shape.get_point(1) == Point(1, 0));
    }
    {
        IDGenerator gen;
        ID id = gen.get_next_id();
        std::vector<Point> points{Point{0, 0}, Point{1, 0}};
        Shape shape(id, FieldSize{2, 2}, points);

        CHECK(shape.get_id() == id);
        CHECK(shape.get_num_points() == 2);
        CHECK(shape.get_num_positions() == 4);
        shape.move_to_position(0);
        CHECK(shape.get_point(0) == Point(0, 0));
        CHECK(shape.get_point(1) == Point(1, 0));
        shape.move_to_position(1);
        CHECK(shape.get_point(0) == Point(0, 1));
        CHECK(shape.get_point(1) == Point(1, 1));
        shape.move_to_position(2);
        CHECK(shape.get_point(0) == Point(0, 0));
        CHECK(shape.get_point(1) == Point(0, 1));
        shape.move_to_position(3);
        CHECK(shape.get_point(0) == Point(1, 0));
        CHECK(shape.get_point(1) == Point(1, 1));
    }
    {
        IDGenerator gen;
        ID id = gen.get_next_id();
        std::vector<Point> points{Point{0, 0}, Point{1, 0}, Point{0, 1}};
        Shape shape(id, FieldSize{2, 2}, points);

        CHECK(shape.get_id() == id);
        CHECK(shape.get_num_points() == 3);
        CHECK(shape.get_num_positions() == 4);
    }

    STATUS();
}

bool tests_failed()
{
    return !test_Id() ||
           !test_Point() ||
           !test_Rotation() ||
           !test_Position() ||
           !test_Shape();
}

/*********************************** Timer ************************************/

class Timer
{
public:
    static void Start(char const *msg)
    {
        std::cerr << msg << '\n';
        start_time = std::clock();
    }

    static void Stop()
    {
        std::clock_t stop_time = std::clock();
        std::cerr << (stop_time - start_time) / 1000.0 << " s" << std::endl;
    }

private:
    static std::clock_t start_time;
};

std::clock_t Timer::start_time;

/************************************ main ************************************/

int main()
{
    if (tests_failed())
        return 1;

    Tangram(FieldSize{2, 2}) // 4 решения
        .reserve_shapes(2)
        .add_shape(std::vector<Point>{
            Point{0, 0},
            Point{1, 0},
        })
        .add_shape(std::vector<Point>{
            Point{0, 0},
            Point{1, 0},
        })
        .solve();

    Tangram tangram(FieldSize{12, 5});
    tangram.reserve_shapes(12)
        .add_shape( // 1
            std::vector<Point>{
                Point{0, 0},
                Point{1, 0},
                Point{2, 0},
                Point{2, 1},
                Point{3, 1},
            })
        .add_shape( // 2
            std::vector<Point>{
                Point{0, 0},
                Point{1, 0},
                Point{2, 0},
                Point{3, 0},
                Point{4, 0},
            })
        .add_shape( // 3
            std::vector<Point>{
                Point{0, 0},
                Point{0, 1},
                Point{0, 2},
                Point{0, 3},
                Point{1, 3},
            })
        .add_shape( // 4
            std::vector<Point>{
                Point{0, 0},
                Point{1, 0},
                Point{2, 0},
                Point{2, 1},
                Point{2, 2},
            })
        .add_shape( // 5
            std::vector<Point>{
                Point{0, 0},
                Point{1, 0},
                Point{0, 1},
                Point{1, 1},
                Point{0, 2},
            })
        .add_shape( // 6
            std::vector<Point>{
                Point{0, 0},
                Point{1, 0},
                Point{0, 1},
                Point{0, 2},
                Point{1, 2},
            })
        .add_shape( // 7
            std::vector<Point>{
                Point{1, 0},
                Point{2, 0},
                Point{0, 1},
                Point{1, 1},
                Point{1, 2},
            })
        .add_shape( // 8
            std::vector<Point>{
                Point{0, 0},
                Point{1, 0},
                Point{1, 1},
                Point{1, 2},
                Point{2, 2},
            })
        .add_shape( // 9
            std::vector<Point>{
                Point{1, 0},
                Point{0, 1},
                Point{1, 1},
                Point{2, 1},
                Point{1, 2},
            })
        .add_shape( // 10
            std::vector<Point>{
                Point{2, 0},
                Point{0, 1},
                Point{1, 1},
                Point{2, 1},
                Point{3, 1},
            })
        .add_shape( // 11
            std::vector<Point>{
                Point{2, 0},
                Point{1, 1},
                Point{2, 1},
                Point{0, 2},
                Point{1, 2},
            })
        .add_shape( // 12
            std::vector<Point>{
                Point{1, 0},
                Point{1, 1},
                Point{0, 2},
                Point{1, 2},
                Point{2, 2},
            });
        
        Timer::Start("Solve ...");
            tangram.solve();
        Timer::Stop();
}

Жуткая черновая версия с неизвестным числом багов. Раздел тестов - это те баги, которые уже попались. Начиная прямо с ошибки в операторе сравнения точек, где из 24 тестов один таки не прошел. Желающие могут поискать остальные.

Если ответ найдет - он выкидывается псевдографикой в консоль в таком виде:

Код:

[Выделить все]

+------------+
|AAAKKJJJJIFF|
|HHAAKKJGIIIF|
|DHLLLKGGGIFF|
|DHHLCCCCGEEE|
|DDDLCBBBBBEE|
+------------+

Сообщение от Дмитррр Задача хоть не совсем примитивная, но и совсем сложной её не назвать.

А теперь про сложность. Релизная версия думает всего ничего:

Код:

[Выделить все]

 7x5 =  0.1 сек
 8x5 =  1.8 сек
 9x5 =  27  сек
10x5 = 329  сек

Очевидно, полностью 11 столбиков будут считаться час, а 12 - день. И это уже вторая версия. В первой позиции генерировались на лету, так что ждать надо было сильно дольше. А тут они предвычисляются до начала решения. И повторные повороты выбрасываются тоже сразу. Дальше должны быть оптимизация расположения в памяти и многопоточность, они на пару должны где-то на порядок дело ускорить. Кому не лень - могут поразвлечься. Или таки надо списковую версию проверять, как в статье по ссылке.

Пошли первые решения, примерно по три в час.

Но, предположительно, до конца надо ждать больше, чем рабочий день, так что полный список, видимо, только на выходных.

[Дмитррр]

Хе. Всё-таки рано я сдался значит. Повертел полчаса-час и убедил себя в том, что задача с подвохом на переворот и не стал искать дальше. Но задача оказалась неожиданно сложной. Не думал, что так много вариантов для перебора будет. Тем более мозгом можно сразу отсеивать нежизнеспособные.

[Нубий-IV]

Полный счет занял 39823 сек (11 часов). Найдено 46 решений, половина из которых - поворот на 180°. Надо было догадаться сразу у первой фигуры на стадии предвычисления повороты на 180° и 270° заблокировать, в 5.5 часов уложился бы. И многопоточный поиск можно запустить (даже просто собрать 4 версии программы, на первом уровне рекурсии перебирать позиции 0...n/4, n/4...n/2 и т.п., да запустить их все).

Код:

[Выделить все]

AAAKKJJJJIFF
HHAAKKJGIIIF
DHLLLKGGGIFF
DHHLCCCCGEEE
DDDLCBBBBBEE

AAAJJJJGGICC
HHAAJKGGIIIC
DHLLLKKGFIFC
DHHLEEKKFFFC
DDDLEEEBBBBB

BBBBBAAAJJJJ
CCCCLLLAAJGG
CKKHHLFFIGGD
EEKKHLFIIIGD
EEEKHHFFIDDD

BBBBBGAAAEEE
CFFIGGGLAAEE
CFIIIKGLLLHD
CFFIJKKLHHHD
CCJJJJKKHDDD

BBBBBIKKEEEA
JDDDIIIKKEEA
JFFDLIGGKHAA
JJFDLGGHHHAC
JFFLLLGHCCCC

BBBBBIFFJJJJ
CCCCIIIFLJGG
CKKHHIFFLGGD
EEKKHAALLLGD
EEEKHHAAADDD

BBBBBIHHCCCC
DDDKIIIHCFFF
EEDKKILHHFGF
EEDJKKLAAGGG
EJJJJLLLAAAG

BBBBBIKKJJJJ
FFFAIIIKKJCC
FEFALIGGKHDC
EEAALGGHHHDC
EEALLLGHDDDC

CCCCHGBBBBBJ
CAHHHGGDDDJJ
AAHKGGIFFDLJ
AEEKKIIIFDLJ
AEEEKKIFFLLL

CCCCKKLLLGGA
CIEEEKKLGGAA
IIIEEHKLJGAD
FIFHHHJJJJAD
FFFHBBBBBDDD

CCCCGGBBBBBL
CFFGGKKAALLL
DFHHGIKKAAAL
DFFHIIIKJEEE
DDDHHIJJJJEE

CCCCBBBBBEEE
CAGHHFFFKKEE
AAGGHFLFIKKD
AGGJHHLIIIKD
AJJJJLLLIDDD

CCCCBBBBBGGJ
CADDDEEEGGJJ
AADHHKEEIGLJ
AFDFHKKIIILJ
AFFFHHKKILLL

CCCCDDDGJJJJ
CIHHDLGGGJKK
IIIHDLLLGKKE
FIFHHLAAAKEE
FFFBBBBBAAEE

DDDBBBBBEEEA
DGHHCCCCIEEA
DGGHCLKIIIAA
GGJHHLKKIFAF
JJJJLLLKKFFF

DDDBBBBBEEEA
DGHHFFFKKEEA
DGGHFLFIKKAA
GGJHHLIIIKAC
JJJJLLLICCCC

DDDILLLAAACC
DKIIILHHGAAC
DKKIFLFHGGGC
EEKKFFFHHGJC
EEEBBBBBJJJJ

DDDIHHBBBBBC
DAIIIHKKCCCC
DAGILHHKKFFF
AAGGLEEEKFJF
AGGLLLEEJJJJ

DDDGGKKBBBBB
DAGGKKJJJJCC
DALGKHHJIFFC
AALEEEHIIIFC
ALLLEEHHIFFC

DDDHBBBBBGCC
DHHHLFFIGGGC
DHLLLFIIIKGC
EEAALFFIJKKC
EEEAAAJJJJKK

HHKBBBBBIEEE
CHKKDDDIIIEE
CHHKKLDGIFFF
CAALLLDGGFJF
CCAAALGGJJJJ

CFFLLLIAADDD
CFHHLIIIAAAD
CFFHLGIEEKKD
CCJHHGGEEEKK
JJJJGGBBBBBK

DCCCCIBBBBBJ
DCKKIIILLLJJ
DDDKKIGGLHHJ
EEAAKGGFLFHJ
EEEAAAGFFFHH

Но я все еще не уверен, что программа написана правильно. 60к кода (2 версии) за пару дней я вообще никогда не писал. Это я тут книжку про разработку через тестирование полистал. "Говнокод, покрытый тестами, превращается в золото". Впечатлился и решил попробовать. Получилась программа, которая вроде работает, но я не могу объяснить, почему.

Так что я бы посоветовал все-таки еще год-другой вручную поискать решения, вдруг пропущенные есть.

Сообщение от Дмитррр Не думал, что так много вариантов для перебора будет.

Удивительно другое. Число позиций одной фигуры 3x2 на поле 12x5 равно (12-3+1)x(5-2+1)=40. С учетом примерно трех поворотов (есть фигуры с 1, 2 и 4 поворотами) это дает 40x3≈100 вариантов. То есть вроде каждая фигура должна добавлять два порядка сложности, а не один. Всего 100^12=1'000'000'000'000'000'000'000'000 вариантов. А тут по скорости видно, что реально один порядок добавляется, всего 10^12=1'000'000'000'000. Что-то тут не сходится, по-моему.

[Дмитррр]

Сообщение от Нубий-IV Надо было догадаться сразу у первой фигуры на стадии предвычисления повороты на 180° и 270° заблокировать, в 5.5 часов уложился бы.

Ну, оптимизация тут может быть чуть ли не бесконечной. Например, напрашивается идея первую фигуру располагать только пристыкованной к левой границе. Вторую только пристыкованной к первой фигуре, третью ко второй и т.д. Если идёт перебор всех фигур во всех комбинациях, то это не должно пропустить решений.

Сообщение от Нубий-IV А тут по скорости видно, что реально один порядок добавляется, всего 10^12=1'000'000'000'000. Что-то тут не сходится, по-моему.

Ну тут надо код анализировать, а анализировать чужой код дело не менее простое, чем написать тот же код самому.
К тому тут ещё и количество клеток уменьшается, а не только количество фигур (если я верно понял, о чём речь).

[Нубий-IV]

Сообщение от Дмитррр тут ещё и количество клеток уменьшается

Исходная шутка была про "всего 200 позиций". Я тоже пошутил. Перебор идет в лоб, все возможные позиции для каждой фигуры.

У меня в детстве была головоломка - из 9 карточек квадрат сложить, чтобы узоры совпали. Мне на нее терпения не хватило. Когда во студентах добрался до компьютера, написал уже перебиралку. А когда Барсика изучал - сваял примитивную версию, для поразвлечься одной правой.

Кому скучно - можно пощелкать, это чуть удобнее, чем в автокаде блоки крутить.

[Солидворкер]

Попалась тут изящная задачка

Доказать, что уравнение a^n+b^n=c^n не имеет решений в натуральных числах при n>2

Если Вы не Эндрю Уайлс, то для Вас ослабим условие

a, b, c, n - простые числа

[BURAN988]

Сообщение от Солидворкер a, b, c, n - простые числа

Не разу не "ферматист", но если 0 - простое число, то при любом n

[Дмитррр]

Сообщение от Солидворкер Доказать, что уравнение a^n+b^n=c^n не имеет решений в натуральных числах при n>2

Согласно ВТФ a^n+b^n=c^n не имеет решений в натуральных числах при n>2. Таким образом утверждение, что уравнение a^n+b^n=c^n не имеет решений в натуральных числах при n>2, доказано.

[Солидворкер]

Сообщение от BURAN988 Не разу не "ферматист", но если 0 - простое число, то при любом n

Ноль - не простое число

----- добавлено через ~1 мин. -----

Сообщение от Дмитррр Согласно ВТФ a^n+b^n=c^n не имеет решений в натуральных числах при n>2. Таким образом утверждение, что уравнение a^n+b^n=c^n не имеет решений в натуральных числах при n>2, доказано.

Хотелось бы увидеть доказательство

[Дмитррр]

Сообщение от Солидворкер Хотелось бы увидеть доказательство

Я использовал теорему. На экзамене по математике при решении задач можно использовать любые теоремы. И при этом их не нужно доказывать.
Или задача загуглить доказательство? Ну, это не головоломка тогда. К тому же эти математические доказательства бывают такие замороченные, что даже моего высшего инженерного образования не хватает, чтобы опнять их.