Эта задача не об игре Змея.

Представьте, что 2-ая змея сформирована, рисуя горизонтальную линию длины n. В целочисленных точках вдоль своего тела эта змея может вращать свое тело на 90 градусов. Если мы определим переднюю часть змеи как крайнюю левую для начала, вращение переместит заднюю часть змеи, а передняя часть останется на месте. Делая многократные повороты, он может создавать множество различных форм тела змеи.

правила

1. Одна часть тела змеи не может перекрывать другую.
2. Должна быть возможность достичь окончательной ориентации без перекрытия между собой частей тела змеи. Две точки, которые касаются, считаются перекрывающимися в этой задаче.
3. Я считаю змею и ее оборотную сторону одинаковой формы.

задача

Что касается вращения, перемещения и зеркальной симметрии, какое общее количество различных форм тела змеи можно создать?

Пример поворота части тела змеи. Представьте, n=10и змея находится в начальной ориентации по прямой линии. Теперь поверните на 490 градусов против часовой стрелки. Мы получаем змею , 4чтобы 10(хвост змеи) лежал вертикально и змеи от 0к 4лежащей горизонтально. Змея теперь имеет один прямой угол в своем теле.

Вот несколько примеров благодаря Мартину Бюттнеру.

Начнем с горизонтальной змеи.

Теперь мы вращаемся из положения 4.

Мы заканчиваем после поворота в этой ориентации.

Теперь давайте рассмотрим эту ориентацию другой змеи.

Теперь мы можем видеть нелегальный ход, когда во время поворота возникнет перекрытие.

Гол

Ваша оценка - самая большая, nза которую ваш код может решить проблему менее чем за одну минуту на моем компьютере.

Когда вращение происходит, оно перемещает половину змеи вместе с ним. Нам нужно беспокоиться о том, может ли какая-либо из вращающихся частей перекрывать часть змеи во время вращения. Для простоты можно предположить, что змея имеет нулевую ширину. Вы можете вращать только в определенной точке змеи до 90 градусов по часовой стрелке против часовой стрелки. Ведь вы никогда не сможете полностью сложить змею пополам, так как это повлекло бы за собой два поворота в одной и той же точке в одном направлении.

Формы, которые не могут быть сделаны

Простой пример формы, которую невозможно сделать, - это заглавная T. Более сложная версия

(Спасибо Харальду Ханче-Олсену за этот пример)

В этом примере все соседние горизонтальные линии разделены на 1, как и вертикальные. Таким образом, нет легального движения с этой позиции, и, поскольку проблема обратима, нет возможности добраться туда из начальной позиции.

Языки и библиотеки

Вы можете использовать любой язык со свободно доступным компилятором / интерпретатором и т. Д. для Linux и любых библиотек, которые также свободно доступны для Linux.

Моя машина Время будет работать на моей машине. Это стандартная установка Ubuntu на восьмиъядерный процессор AMD FX-8350. Это также означает, что мне нужно иметь возможность запустить ваш код. Как следствие, используйте только легкодоступное бесплатное программное обеспечение и, пожалуйста, включите подробные инструкции по компиляции и запуску вашего кода.

Python 3 - предварительная оценка: n = 11 (n = 13 с PyPy *)

Поскольку в течение первой недели не было ответов, вот пример на Python для поощрения конкуренции. Я попытался сделать его достаточно читабельным, чтобы можно было легко выявить недостатки и дать идеи для других ответов.

Подход

• Начните с прямой змеи и найдите все позиции, которые могут быть юридически достигнуты за один ход.
• Найдите все позиции, которые могут быть законно достигнуты из тех позиций, которые еще не были определены.
• Повторяйте, пока больше не сможете найти, и верните количество найденных позиций в целом.

Код

(теперь с некоторыми doctests и утверждает после моей неправильной первой попытки)

'''
Snake combinations

A snake is represented by a tuple giving the relative orientation at each joint.
A length n snake has n-1 joints.
Each relative orientation is one of the following:

0: Clockwise 90 degrees
1: Straight
2: Anticlockwise 90 degrees

So a straight snake of length 4 has 3 joints all set to 1:

(1, 1, 1)

x increases to the right
y increases upwards

'''


import turtle


def all_coords(state):
    '''Return list of coords starting from (0,0) heading right.'''
    current = (1, 0)
    heading = 0
    coords = [(0,0), (1,0)]
    for item in state:
        heading += item + 3
        heading %= 4
        offset = ((1,0), (0,1), (-1,0), (0,-1))[heading]
        current = tuple(current[i]+offset[i] for i in (0,1))
        coords.append(current)
    return coords


def line_segments(coords, pivot):
    '''Return list of line segments joining consecutive coords up to pivot-1.'''
    return [(coords[i], coords[i+1]) for i in range(pivot+1)]


def rotation_direction(coords, pivot, coords_in_final_after_pivot):
    '''Return -1 if turning clockwise, 1 if turning anticlockwise.'''
    pivot_coord = coords[pivot + 1]
    initial_coord = coords[pivot + 2]
    final_coord = coords_in_final_after_pivot[0]
    initial_direction = tuple(initial_coord[i] - pivot_coord[i] for i in (0,1))
    final_direction = tuple(final_coord[i] - pivot_coord[i] for i in (0,1))
    return (initial_direction[0] * final_direction[1] -
            initial_direction[1] * final_direction[0]
            )


def intersects(arc, line):
    '''Return True if the arc intersects the line segment.'''
    if line_segment_cuts_circle(arc, line):
        cut_points = points_cutting_circle(arc, line)
        if cut_points and cut_point_is_on_arc(arc, cut_points):
            return True


def line_segment_cuts_circle(arc, line):
    '''Return True if the line endpoints are not both inside or outside.'''
    centre, point, direction = arc
    start, finish = line
    point_distance_squared = distance_squared(centre, point)
    start_distance_squared = distance_squared(centre, start)
    finish_distance_squared = distance_squared(centre, finish)
    start_sign = start_distance_squared - point_distance_squared
    finish_sign = finish_distance_squared - point_distance_squared
    if start_sign * finish_sign <= 0:
        return True


def distance_squared(centre, point):
    '''Return the square of the distance between centre and point.'''
    return sum((point[i] - centre[i]) ** 2 for i in (0,1))


def cut_point_is_on_arc(arc, cut_points):
    '''Return True if any intersection point with circle is on arc.'''
    centre, arc_start, direction = arc
    relative_start = tuple(arc_start[i] - centre[i] for i in (0,1))
    relative_midpoint = ((relative_start[0] - direction*relative_start[1])/2,
                         (relative_start[1] + direction*relative_start[0])/2
                         )
    span_squared = distance_squared(relative_start, relative_midpoint)
    for cut_point in cut_points:
        relative_cut_point = tuple(cut_point[i] - centre[i] for i in (0,1))
        spacing_squared = distance_squared(relative_cut_point,
                                           relative_midpoint
                                           )
        if spacing_squared <= span_squared:
            return True


def points_cutting_circle(arc, line):
    '''Return list of points where line segment cuts circle.'''
    points = []
    start, finish = line
    centre, arc_start, direction = arc
    radius_squared = distance_squared(centre, arc_start)
    length_squared = distance_squared(start, finish)
    relative_start = tuple(start[i] - centre[i] for i in (0,1))
    relative_finish = tuple(finish[i] - centre[i] for i in (0,1))
    relative_midpoint = tuple((relative_start[i] +
                               relative_finish[i]
                               )*0.5 for i in (0,1))
    determinant = (relative_start[0]*relative_finish[1] -
                   relative_finish[0]*relative_start[1]
                   )
    determinant_squared = determinant ** 2
    discriminant = radius_squared * length_squared - determinant_squared
    offset = tuple(finish[i] - start[i] for i in (0,1))
    sgn = (1, -1)[offset[1] < 0]
    root_discriminant = discriminant ** 0.5
    one_over_length_squared = 1 / length_squared
    for sign in (-1, 1):
        x = (determinant * offset[1] +
             sign * sgn * offset[0] * root_discriminant
             ) * one_over_length_squared
        y = (-determinant * offset[0] +
             sign * abs(offset[1]) * root_discriminant
             ) * one_over_length_squared
        check = distance_squared(relative_midpoint, (x,y))
        if check <= length_squared * 0.25:
            points.append((centre[0] + x, centre[1] + y))
    return points


def potential_neighbours(candidate):
    '''Return list of states one turn away from candidate.'''
    states = []
    for i in range(len(candidate)):
        for orientation in range(3):
            if abs(candidate[i] - orientation) == 1:
                state = list(candidate)
                state[i] = orientation
                states.append(tuple(state))
    return states


def reachable(initial, final):
    '''
    Return True if final state can be reached in one legal move.

    >>> reachable((1,0,0), (0,0,0))
    False

    >>> reachable((0,1,0), (0,0,0))
    False

    >>> reachable((0,0,1), (0,0,0))
    False

    >>> reachable((1,2,2), (2,2,2))
    False

    >>> reachable((2,1,2), (2,2,2))
    False

    >>> reachable((2,2,1), (2,2,2))
    False

    >>> reachable((1,2,1,2,1,1,2,2,1), (1,2,1,2,1,1,2,1,1))
    False

    '''
    pivot = -1
    for i in range(len(initial)):
        if initial[i] != final[i]:
            pivot = i
            break

    assert pivot > -1, '''
        No pivot between {} and {}'''.format(initial, final)
    assert initial[pivot + 1:] == final[pivot + 1:], '''
        More than one pivot between {} and {}'''.format(initial, final)

    coords_in_initial = all_coords(initial)
    coords_in_final_after_pivot = all_coords(final)[pivot+2:]
    coords_in_initial_after_pivot = coords_in_initial[pivot+2:]
    line_segments_up_to_pivot = line_segments(coords_in_initial, pivot)

    direction = rotation_direction(coords_in_initial,
                                   pivot,
                                   coords_in_final_after_pivot
                                   )

    pivot_point = coords_in_initial[pivot + 1]

    for point in coords_in_initial_after_pivot:
        arc = (pivot_point, point, direction)
        if any(intersects(arc, line) for line in line_segments_up_to_pivot):
            return False
    return True


def display(snake):
    '''Display a line diagram of the snake.

    Accepts a snake as either a tuple:

    (1, 1, 2, 0)

    or a string:

    "1120"

    '''
    snake = tuple(int(s) for s in snake)
    coords = all_coords(snake)

    turtle.clearscreen()
    t = turtle.Turtle()
    t.hideturtle()
    s = t.screen
    s.tracer(0)

    width, height = s.window_width(), s.window_height()

    x_min = min(coord[0] for coord in coords)
    x_max = max(coord[0] for coord in coords)
    y_min = min(coord[1] for coord in coords)
    y_max = max(coord[1] for coord in coords)
    unit_length = min(width // (x_max - x_min + 1),
                      height // (y_max - y_min + 1)
                      )

    origin_x = -(x_min + x_max) * unit_length // 2
    origin_y = -(y_min + y_max) * unit_length // 2

    pen_width = max(1, unit_length // 20)
    t.pensize(pen_width)
    dot_size = max(4, pen_width * 3)

    t.penup()
    t.setpos(origin_x, origin_y)
    t.pendown()

    t.forward(unit_length)
    for joint in snake:
        t.dot(dot_size)
        t.left((joint - 1) * 90)
        t.forward(unit_length)
    s.update()


def neighbours(origin, excluded=()):
    '''Return list of states reachable in one step.'''
    states = []
    for candidate in potential_neighbours(origin):
        if candidate not in excluded and reachable(origin, candidate):
            states.append(candidate)
    return states


def mirrored_or_backwards(candidates):
    '''Return set of states that are equivalent to a state in candidates.'''
    states = set()
    for candidate in candidates:
        mirrored = tuple(2 - joint for joint in candidate)
        backwards = candidate[::-1]
        mirrored_backwards = mirrored[::-1]
        states |= set((mirrored, backwards, mirrored_backwards))
    return states


def possible_snakes(snake):
    '''
    Return the set of possible arrangements of the given snake.

    >>> possible_snakes((1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1))
    {(1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1)}

    '''
    reached = set()
    candidates = set((snake,))

    while candidates:
        candidate = candidates.pop()
        reached.add(candidate)
        new_candidates = neighbours(candidate, reached)
        reached |= mirrored_or_backwards(new_candidates)
        set_of_new_candidates = set(new_candidates)
        reached |= set_of_new_candidates
        candidates |= set_of_new_candidates

    excluded = set()
    final_answers = set()
    while reached:
        candidate = reached.pop()
        if candidate not in excluded:
            final_answers.add(candidate)
            excluded |= mirrored_or_backwards([candidate])

    return final_answers


def straight_derived_snakes(length):
    '''Return the set of possible arrangements of a snake of this length.'''
    straight_line = (1,) * max(length-1, 0)
    return possible_snakes(straight_line)


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    import sys
    arguments = sys.argv[1:]
    if arguments:
        length = int(arguments[0])
    else:
        length = int(input('Enter the length of the snake:'))
    print(len(straight_derived_snakes(length)))

Полученные результаты

На моей машине самая длинная змея, которую можно вычислить менее чем за 1 минуту, имеет длину 11 (или длину 13 с PyPy *). Это, очевидно, лишь предварительная оценка, пока мы не узнаем, какая официальная оценка у машины Лембика.

Для сравнения, вот результаты для первых нескольких значений n:

 n | reachable orientations
-----------------------------
 0 | 1
 1 | 1
 2 | 2
 3 | 4
 4 | 9
 5 | 22
 6 | 56
 7 | 147
 8 | 388
 9 | 1047
10 | 2806
11 | 7600
12 | 20437
13 | 55313
14 | 148752
15 | 401629
16 | 1078746
17 | MemoryError (on my machine)

Пожалуйста, дайте мне знать, если какой-либо из них окажется неправильным.

Если у вас есть пример договоренности, которую нельзя развернуть, вы можете использовать эту функцию, neighbours(snake)чтобы найти любые договоренности, достижимые за один шаг, в качестве теста кода. snakeявляется набором направлений соединения (0 для часовой стрелки, 1 для прямой, 2 для против часовой стрелки). Например (1,1,1) - прямая змея длиной 4 (с 3 суставами).

Визуализация

Чтобы визуализировать змею, которую вы имеете в виду, или любую змею, возвращенную neighboursвами, вы можете использовать функцию display(snake). Он принимает кортеж, как и другие функции, но, поскольку он не используется основной программой и, следовательно, не требует быстрой работы, он также примет строку для вашего удобства.

display((1,1,2,0)) эквивалентно display("1120")

Как упоминает Лембик в комментариях, мои результаты идентичны OEIS A037245, который не учитывает пересечения во время вращения. Это связано с тем, что для первых нескольких значений n нет разницы - все фигуры, которые не пересекаются, могут быть получены путем складывания прямой змеи. Корректность кода можно проверить, позвонив neighbours()со змеей, которую нельзя развернуть без пересечения. Поскольку у него нет соседей, он будет вносить вклад только в последовательность OEIS, а не в эту. Самый маленький пример я знаю это длина 31 змея Lembik упоминалось, благодаря David K :

(1,1,1,1,2,1,2,1,1,1,1,1,1,2,1,1,1,2,1,1,2,2,1,0,1,0,1,1,1,1)

display('111121211111121112112210101111') дает следующий вывод:

Совет: если вы измените размер окна дисплея, а затем снова вызовете display, змея будет соответствовать новому размеру окна.

Я хотел бы услышать от любого, у кого есть более короткий пример без соседей. Я подозреваю, что самый короткий такой пример будет отмечать наименьшее n, для которого отличаются две последовательности.

* Обратите внимание, что каждое приращение n занимает примерно 3 раза больше, поэтому увеличение с n = 11 до n = 13 требует почти в 10 раз больше времени. Вот почему PyPy позволяет увеличивать n только на 2, даже если он работает значительно быстрее, чем стандартный интерпретатор Python.

C ++ 11 - почти работает :)

Прочитав эту статью , я собрал кусочки мудрости у того парня, который, по-видимому, 25 лет работал над менее сложной проблемой подсчета самоуничтожающихся путей на квадратной решетке.

#include <cassert>
#include <ctime>
#include <sstream>
#include <vector>
#include <algorithm> // sort

using namespace std;

// theroretical max snake lenght (the code would need a few decades to process that value)
#define MAX_LENGTH ((int)(1+8*sizeof(unsigned)))

#ifndef _MSC_VER
#ifndef QT_DEBUG // using Qt IDE for g++ builds
#define NDEBUG
#endif
#endif

#ifdef NDEBUG
inline void tprintf(const char *, ...){}
#else
#define tprintf printf
#endif

void panic(const char * msg)
{
    printf("PANIC: %s\n", msg);
    exit(-1);
}

// ============================================================================
// fast bit reversal
// ============================================================================
unsigned bit_reverse(register unsigned x, unsigned len)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16)) >> (32-len);
}

// ============================================================================
// 2D geometry (restricted to integer coordinates and right angle rotations)
// ============================================================================

// points using integer- or float-valued coordinates
template<typename T>struct tTypedPoint;

typedef int    tCoord;
typedef double tFloatCoord;

typedef tTypedPoint<tCoord> tPoint;
typedef tTypedPoint<tFloatCoord>  tFloatPoint;

template <typename T>
struct tTypedPoint {
    T x, y;

    template<typename U> tTypedPoint(const tTypedPoint<U>& from) : x((T)from.x), y((T)from.y) {} // conversion constructor

    tTypedPoint() {}
    tTypedPoint(T x, T y) : x(x), y(y) {}
    tTypedPoint(const tTypedPoint& p) { *this = p; }
    tTypedPoint operator+ (const tTypedPoint & p) const { return{ x + p.x, y + p.y }; }
    tTypedPoint operator- (const tTypedPoint & p) const { return{ x - p.x, y - p.y }; }
    tTypedPoint operator* (T scalar) const { return{ x * scalar, y * scalar }; }
    tTypedPoint operator/ (T scalar) const { return{ x / scalar, y / scalar }; }
    bool operator== (const tTypedPoint & p) const { return x == p.x && y == p.y; }
    bool operator!= (const tTypedPoint & p) const { return !operator==(p); }
    T dot(const tTypedPoint &p) const { return x*p.x + y * p.y; } // dot product  
    int cross(const tTypedPoint &p) const { return x*p.y - y * p.x; } // z component of cross product
    T norm2(void) const { return dot(*this); }

    // works only with direction = 1 (90° right) or -1 (90° left)
    tTypedPoint rotate(int direction) const { return{ direction * y, -direction * x }; }
    tTypedPoint rotate(int direction, const tTypedPoint & center) const { return (*this - center).rotate(direction) + center; }

    // used to compute length of a ragdoll snake segment
    unsigned manhattan_distance(const tPoint & p) const { return abs(x-p.x) + abs(y-p.y); }
};


struct tArc {
    tPoint c;                        // circle center
    tFloatPoint middle_vector;       // vector splitting the arc in half
    tCoord      middle_vector_norm2; // precomputed for speed
    tFloatCoord dp_limit;

    tArc() {}
    tArc(tPoint c, tPoint p, int direction) : c(c)
    {
        tPoint r = p - c;
        tPoint end = r.rotate(direction);
        middle_vector = ((tFloatPoint)(r+end)) / sqrt(2); // works only for +-90° rotations. The vector should be normalized to circle radius in the general case
        middle_vector_norm2 = r.norm2();
        dp_limit = ((tFloatPoint)r).dot(middle_vector);
        assert (middle_vector == tPoint(0, 0) || dp_limit != 0);
    }

    bool contains(tFloatPoint p) // p must be a point on the circle
    {
        if ((p-c).dot(middle_vector) >= dp_limit)
        {
            return true;
        }
        else return false;
    }
};

// returns the point of line (p1 p2) that is closest to c
// handles degenerate case p1 = p2
tPoint line_closest_point(tPoint p1, tPoint p2, tPoint c)
{
    if (p1 == p2) return{ p1.x, p1.y };
    tPoint p1p2 = p2 - p1;
    tPoint p1c =  c  - p1;
    tPoint disp = (p1p2 * p1c.dot(p1p2)) / p1p2.norm2();
    return p1 + disp;
}

// variant of closest point computation that checks if the projection falls within the segment
bool closest_point_within(tPoint p1, tPoint p2, tPoint c, tPoint & res)
{
    tPoint p1p2 = p2 - p1;
    tPoint p1c = c - p1;
    tCoord nk = p1c.dot(p1p2);
    if (nk <= 0) return false;
    tCoord n = p1p2.norm2();
    if (nk >= n) return false;
    res = p1 + p1p2 * (nk / n);
    return true;
}

// tests intersection of line (p1 p2) with an arc
bool inter_seg_arc(tPoint p1, tPoint p2, tArc arc)
{
    tPoint m = line_closest_point(p1, p2, arc.c);
    tCoord r2 = arc.middle_vector_norm2;
    tPoint cm = m - arc.c;
    tCoord h2 = cm.norm2();
    if (r2 < h2) return false; // no circle intersection

    tPoint p1p2 = p2 - p1;
    tCoord n2p1p2 = p1p2.norm2();

    // works because by construction p is on (p1 p2)
    auto in_segment = [&](const tFloatPoint & p) -> bool
    {
        tFloatCoord nk = p1p2.dot(p - p1);
        return nk >= 0 && nk <= n2p1p2;
    };

    if (r2 == h2) return arc.contains(m) && in_segment(m); // tangent intersection

    //if (p1 == p2) return false; // degenerate segment located inside circle
    assert(p1 != p2);

    tFloatPoint u = (tFloatPoint)p1p2 * sqrt((r2-h2)/n2p1p2); // displacement on (p1 p2) from m to one intersection point

    tFloatPoint i1 = m + u;
    if    (arc.contains(i1) && in_segment(i1)) return true;
    tFloatPoint i2 = m - u;
    return arc.contains(i2) && in_segment(i2);
}

// ============================================================================
// compact storage of a configuration (64 bits)
// ============================================================================
struct sConfiguration {
    unsigned partition;
    unsigned folding;

    explicit sConfiguration() {}
    sConfiguration(unsigned partition, unsigned folding) : partition(partition), folding(folding) {}

    // add a bend
    sConfiguration bend(unsigned joint, int rotation) const
    {
        sConfiguration res;
        unsigned joint_mask = 1 << joint;
        res.partition = partition | joint_mask;
        res.folding = folding;
        if (rotation == -1) res.folding |= joint_mask;
        return res;
    }

    // textual representation
    string text(unsigned length) const
    {
        ostringstream res;

        unsigned f = folding;
        unsigned p = partition;

        int segment_len = 1;
        int direction = 1;
        for (size_t i = 1; i != length; i++)
        {
            if (p & 1)
            {
                res << segment_len * direction << ',';
                direction = (f & 1) ? -1 : 1;
                segment_len = 1;
            }
            else segment_len++;

            p >>= 1;
            f >>= 1;
        }
        res << segment_len * direction;
        return res.str();
    }

    // for final sorting
    bool operator< (const sConfiguration& c) const
    {
        return (partition == c.partition) ? folding < c.folding : partition < c.partition;
    }
};

// ============================================================================
// static snake geometry checking grid
// ============================================================================
typedef unsigned tConfId;

class tGrid {
    vector<tConfId>point;
    tConfId current;
    size_t snake_len;
    int min_x, max_x, min_y, max_y;
    size_t x_size, y_size;

    size_t raw_index(const tPoint& p) { bound_check(p);  return (p.x - min_x) + (p.y - min_y) * x_size; }
    void bound_check(const tPoint& p) const { assert(p.x >= min_x && p.x <= max_x && p.y >= min_y && p.y <= max_y); }

    void set(const tPoint& p)
    {
        point[raw_index(p)] = current;
    }
    bool check(const tPoint& p)
    {
        if (point[raw_index(p)] == current) return false;
        set(p);
        return true;
    }

public:
    tGrid(int len) : current(-1), snake_len(len)
    {
        min_x = -max(len - 3, 0);
        max_x = max(len - 0, 0);
        min_y = -max(len - 1, 0);
        max_y = max(len - 4, 0);
        x_size = max_x - min_x + 1;
        y_size = max_y - min_y + 1;
        point.assign(x_size * y_size, current);
    }

    bool check(sConfiguration c)
    {
        current++;
        tPoint d(1, 0);
        tPoint p(0, 0);
        set(p);
        for (size_t i = 1; i != snake_len; i++)
        {
            p = p + d;
            if (!check(p)) return false;
            if (c.partition & 1) d = d.rotate((c.folding & 1) ? -1 : 1);
            c.folding >>= 1;
            c.partition >>= 1;
        }
        return check(p + d);
    }

};

// ============================================================================
// snake ragdoll 
// ============================================================================
class tSnakeDoll {
    vector<tPoint>point; // snake geometry. Head at (0,0) pointing right

    // allows to check for collision with the area swept by a rotating segment
    struct rotatedSegment {
        struct segment { tPoint a, b; };
        tPoint  org;
        segment end;
        tArc    arc[3];
        bool extra_arc; // see if third arc is needed

        // empty constructor to avoid wasting time in vector initializations
        rotatedSegment(){}
        // copy constructor is mandatory for vectors *but* shall never be used, since we carefully pre-allocate vector memory
        rotatedSegment(const rotatedSegment &){ assert(!"rotatedSegment should never have been copy-constructed"); }

        // rotate a segment
        rotatedSegment(tPoint pivot, int rotation, tPoint o1, tPoint o2)
        {
            arc[0] = tArc(pivot, o1, rotation);
            arc[1] = tArc(pivot, o2, rotation);
            tPoint middle;
            extra_arc = closest_point_within(o1, o2, pivot, middle);
            if (extra_arc) arc[2] = tArc(pivot, middle, rotation);
            org = o1;
            end = { o1.rotate(rotation, pivot), o2.rotate(rotation, pivot) };
        }

        // check if a segment intersects the area swept during rotation
        bool intersects(tPoint p1, tPoint p2) const
        {
            auto print_arc = [&](int a) { tprintf("(%d,%d)(%d,%d) -> %d (%d,%d)[%f,%f]", p1.x, p1.y, p2.x, p2.y, a, arc[a].c.x, arc[a].c.y, arc[a].middle_vector.x, arc[a].middle_vector.y); };

            if (p1 == org) return false; // pivot is the only point allowed to intersect
            if (inter_seg_arc(p1, p2, arc[0])) 
            { 
                print_arc(0);  
                return true;
            }
            if (inter_seg_arc(p1, p2, arc[1]))
            { 
                print_arc(1); 
                return true;
            }
            if (extra_arc && inter_seg_arc(p1, p2, arc[2])) 
            { 
                print_arc(2);
                return true;
            }
            return false;
        }
    };

public:
    sConfiguration configuration;
    bool valid;

    // holds results of a folding attempt
    class snakeFolding {
        friend class tSnakeDoll;
        vector<rotatedSegment>segment; // rotated segments
        unsigned joint;
        int direction;
        size_t i_rotate;

        // pre-allocate rotated segments
        void reserve(size_t length)
        {
            segment.clear(); // this supposedly does not release vector storage memory
            segment.reserve(length);
        }

        // handle one segment rotation
        void rotate(tPoint pivot, int rotation, tPoint o1, tPoint o2)
        {
            segment.emplace_back(pivot, rotation, o1, o2);
        }
    public:
        // nothing done during construction
        snakeFolding(unsigned size)
        {
            segment.reserve (size);
        }
    };

    // empty default constructor to avoid wasting time in array/vector inits
    tSnakeDoll() {}

    // constructs ragdoll from compressed configuration
    tSnakeDoll(unsigned size, unsigned generator, unsigned folding) : point(size), configuration(generator,folding)
    {
        tPoint direction(1, 0);
        tPoint current = { 0, 0 };
        size_t p = 0;
        point[p++] = current;
        for (size_t i = 1; i != size; i++)
        {
            current = current + direction;
            if (generator & 1)
            {
                direction.rotate((folding & 1) ? -1 : 1);
                point[p++] = current;
            }
            folding >>= 1;
            generator >>= 1;
        }
        point[p++] = current;
        point.resize(p);
    }

    // constructs the initial flat snake
    tSnakeDoll(int size) : point(2), configuration(0,0), valid(true)
    {
        point[0] = { 0, 0 };
        point[1] = { size, 0 };
    }

    // constructs a new folding with one added rotation
    tSnakeDoll(const tSnakeDoll & parent, unsigned joint, int rotation, tGrid& grid)
    {
        // update configuration
        configuration = parent.configuration.bend(joint, rotation);

        // locate folding point
        unsigned p_joint = joint+1;
        tPoint pivot;
        size_t i_rotate = 0;
        for (size_t i = 1; i != parent.point.size(); i++)
        {
            unsigned len = parent.point[i].manhattan_distance(parent.point[i - 1]);
            if (len > p_joint)
            {
                pivot = parent.point[i - 1] + ((parent.point[i] - parent.point[i - 1]) / len) * p_joint;
                i_rotate = i;
                break;
            }
            else p_joint -= len;
        }

        // rotate around joint
        snakeFolding fold (parent.point.size() - i_rotate);
        fold.rotate(pivot, rotation, pivot, parent.point[i_rotate]);
        for (size_t i = i_rotate + 1; i != parent.point.size(); i++) fold.rotate(pivot, rotation, parent.point[i - 1], parent.point[i]);

        // copy unmoved points
        point.resize(parent.point.size()+1);
        size_t i;
        for (i = 0; i != i_rotate; i++) point[i] = parent.point[i];

        // copy rotated points
        for (; i != parent.point.size(); i++) point[i] = fold.segment[i - i_rotate].end.a;
        point[i] = fold.segment[i - 1 - i_rotate].end.b;

        // static configuration check
        valid = grid.check (configuration);

        // check collisions with swept arcs
        if (valid && parent.valid) // ;!; parent.valid test is temporary
        {
            for (const rotatedSegment & s : fold.segment)
            for (size_t i = 0; i != i_rotate; i++)
            {
                if (s.intersects(point[i+1], point[i]))
                {
                    //printf("! %s => %s\n", parent.trace().c_str(), trace().c_str());//;!;
                    valid = false;
                    break;
                }
            }
        }
    }

    // trace
    string trace(void) const
    {
        size_t len = 0;
        for (size_t i = 1; i != point.size(); i++) len += point[i - 1].manhattan_distance(point[i]);
        return configuration.text(len);
    }
};

// ============================================================================
// snake twisting engine
// ============================================================================
class cSnakeFolder {
    int length;
    unsigned num_joints;
    tGrid grid;

    // filter redundant configurations
    bool is_unique (sConfiguration c)
    {
        unsigned reverse_p = bit_reverse(c.partition, num_joints);
        if (reverse_p < c.partition)
        {
            tprintf("P cut %s\n", c.text(length).c_str());
            return false;
        }
        else if (reverse_p == c.partition) // filter redundant foldings
        {
            unsigned first_joint_mask = c.partition & (-c.partition); // insulates leftmost bit
            unsigned reverse_f = bit_reverse(c.folding, num_joints);
            if (reverse_f & first_joint_mask) reverse_f = ~reverse_f & c.partition;

            if (reverse_f > c.folding)
            {
                tprintf("F cut %s\n", c.text(length).c_str());
                return false;
            }
        }
        return true;
    }

    // recursive folding
    void fold(tSnakeDoll snake, unsigned first_joint)
    {
        // count unique configurations
        if (snake.valid && is_unique(snake.configuration)) num_configurations++;

        // try to bend remaining joints
        for (size_t joint = first_joint; joint != num_joints; joint++)
        {
            // right bend
            tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint,1).text(length).c_str());
            fold(tSnakeDoll(snake, joint, 1, grid), joint + 1);

            // left bend, except for the first joint
            if (snake.configuration.partition != 0)
            {
                tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint, -1).text(length).c_str());
                fold(tSnakeDoll(snake, joint, -1, grid), joint + 1);
            }
        }
    }

public:
    // count of found configurations
    unsigned num_configurations;

    // constructor does all the work :)
    cSnakeFolder(int n) : length(n), grid(n), num_configurations(0)
    {
        num_joints = length - 1;

        // launch recursive folding
        fold(tSnakeDoll(length), 0);
    }
};

// ============================================================================
// here we go
// ============================================================================
int main(int argc, char * argv[])
{
#ifdef NDEBUG
    if (argc != 2) panic("give me a snake length or else");
    int length = atoi(argv[1]);
#else
    (void)argc; (void)argv;
    int length = 12;
#endif // NDEBUG

    if (length <= 0 || length >= MAX_LENGTH) panic("a snake of that length is hardly foldable");

    time_t start = time(NULL);
    cSnakeFolder snakes(length);
    time_t duration = time(NULL) - start;

    printf ("Found %d configuration%c of length %d in %lds\n", snakes.num_configurations, (snakes.num_configurations == 1) ? '\0' : 's', length, duration);
    return 0;
}

Сборка исполняемого файла

Скомпилируйте с использованием MinGW под Win7 с g ++ 4.8 для сборок "linux", поэтому переносимость не гарантируется на 100%.g++ -O3 -std=c++11

Это также работает (вроде) со стандартным проектом MSVC2013

Отменив определение NDEBUG, вы получаете следы выполнения алгоритма и сводку найденных конфигураций.

Выступления

с хеш-таблицами или без них компилятор Microsoft работает ужасно: сборка g ++ происходит в 3 раза быстрее .

Алгоритм практически не использует памяти.

Поскольку проверка столкновений примерно в O (n), время вычислений должно быть в O (nk ⁿ ), где k немного меньше 3.
На моем i3-2100@3.1 ГГц n = 17 занимает около 1:30 (около 2 миллионов) змеи / мин).

Я не закончил оптимизацию, но я не ожидал бы большего, чем прирост в 3 раза, поэтому в принципе я могу надеяться достичь n = 20 за час или n = 24 за день.

Достижение первой известной несгибаемой формы (n = 31) займет от нескольких лет до десятилетия, при условии отсутствия перебоев в электроснабжении.

Подсчет фигур

N размер змея N-1 суставы.
Каждый сустав может быть оставлен прямым или согнутым влево или вправо (3 варианта).
Таким образом, число возможных складываний составляет 3 ^N-1 .
Столкновения несколько уменьшат это число, поэтому фактическое число близко к 2,7 ^N-1

Однако многие такие складки приводят к одинаковым формам.

две формы идентичны, если есть вращение или симметрия, которая может преобразовать одну в другую.

Давайте определим сегмент как любую прямую часть сложенного тела.
Например, змея размера 5, сложенная во 2-м суставе, будет иметь 2 сегмента (один длиной 2 единицы, а второй длиной 3 единицы).
Первый сегмент будет назван голова , а последний хвост .

По договоренности мы ориентируем голову змей горизонтально, направив тело вправо (как на первом рисунке ОП).

Мы обозначаем данную фигуру списком длин сегментов со знаком, причем положительные длины указывают на сворачивание справа, а отрицательные - на сворачивание слева.
Начальная длина положительна по соглашению.

Разделение сегментов и изгибов

Если мы рассмотрим только различные способы, которыми змея длины N может быть разбита на сегменты, мы получим перераспределение, идентичное композициям N.

Используя тот же алгоритм, который показан на вики-странице, легко сгенерировать все 2 ^N-1 возможных раздела змеи.

Каждая перегородка, в свою очередь, генерирует все возможные сгибы, применяя левый или правый изгибы ко всем своим соединениям. Одно такое складывание будет называться конфигурацией .

Все возможные разделы могут быть представлены целым числом из N-1 битов, где каждый бит представляет наличие соединения. Мы назовем это целое число генератором .

Обрезка перегородок

Заметив, что сгибание данного раздела от головы вниз эквивалентно сгибанию симметричного раздела от хвоста вверх, мы можем найти все пары симметричных разделов и устранить одно из двух.
Генератор симметричного раздела - это генератор раздела, записанный в обратном битовом порядке, который легко и дешево обнаружить.

Это исключит почти половину возможных разделов, за исключением разделов с «палиндромными» генераторами, которые остаются неизменными при обращении битов (например, 00100100).

Забота о горизонтальной симметрии

С нашими соглашениями (змея начинает указывать вправо), самый первый изгиб, примененный справа, создаст семейство сгибов, которое будет горизонтальной симметрией от тех, которые отличаются только первым сгибом.

Если мы решим, что первый изгиб всегда будет направо, мы устраняем все горизонтальные симметрии одним большим ударом.

Зачистка палиндромов

Эти два сокращения эффективны, но их недостаточно, чтобы позаботиться об этих надоедливых палиндромах.
Наиболее тщательная проверка в общем случае выглядит следующим образом:

рассмотрим конфигурацию C с палиндромной перегородкой.

• если мы инвертируем каждый изгиб в C, мы получим горизонтальную симметрию C.
• если мы повернем C (применяя изгибы от хвоста вверх), мы получим ту же фигуру повернутой вправо
• если мы оба повернем и инвертируем C, мы получим одну и ту же фигуру повернутой влево.

Мы могли бы проверить каждую новую конфигурацию против 3 других. Однако, поскольку мы уже генерируем только конфигурации, начиная с правого поворота, у нас есть только одна возможная симметрия для проверки:

• перевернутая буква C начнется с левого поворота, который по конструкции невозможно воспроизвести
• из перевернутой и перевернутой конфигурации только одна будет начинаться с правого поворота.
  Это единственная конфигурация, которую мы можем дублировать.

Устранение дубликатов без хранения

Мой первоначальный подход состоял в том, чтобы хранить все конфигурации в огромной хеш-таблице, чтобы исключить дубликаты путем проверки наличия ранее вычисленной симметричной конфигурации.

Благодаря вышеупомянутой статье стало ясно, что, поскольку разделы и свертки хранятся в виде битовых полей, их можно сравнивать как любое числовое значение.
Таким образом, чтобы исключить одного члена из симметричной пары, вы можете просто сравнить оба элемента и систематически оставить самый маленький (или самый большой, как вам нравится).

Таким образом, тестирование конфигурации на дублирование равнозначно вычислению симметричного раздела, а если оба идентичных, - свертывание. Память не нужна вообще.

Порядок генерации

Очевидно, что проверка столкновений будет наиболее трудоемкой частью, поэтому сокращение этих вычислений значительно экономит время.

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

Выбирая порядок, в котором тестируются конфигурации, так что для каждого общего количества соединений может храниться не более ragdoll, мы можем ограничить количество экземпляров N-1.

Я использую рекурсивное сканирование сакэ с хвоста вниз, добавляя по одному суставу на каждом уровне. Таким образом, новый экземпляр ragdoll создается поверх родительской конфигурации с одним дополнительным изгибом.

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

Когда обнаруживается самостолкновение, изгибы, которые приводят к нарушающему ходу, применяются во всех возможных порядках, пока не будет найдено законное сворачивание или пока не исчерпаны все комбинации.

Статическая проверка

Прежде чем думать о движущихся деталях, я обнаружил, что эффективнее проверить статическую окончательную форму змеи на самопересечение.

Это делается путем рисования змеи на сетке. Каждая возможная точка изображена с головы вниз. Если есть самопересечение, по крайней мере, пара точек попадет в одно и то же место. Это требует ровно N графиков для любой конфигурации змеи в течение постоянного O (N) времени.

Основным преимуществом этого подхода является то, что один только статический тест просто выберет действительные пути самообращения на квадратной решетке, что позволяет протестировать весь алгоритм, запретив динамическое обнаружение столкновений и убедившись, что мы находим правильное количество таких путей.

Динамическая проверка

Когда змея складывается вокруг одного сустава, каждый повернутый сегмент охватывает область, форма которой совсем не тривиальна.
Очевидно, что вы можете проверять столкновения, проверяя включение во всех таких областях по отдельности. Глобальная проверка была бы более эффективной, но, учитывая сложность областей, о которой я не могу думать (за исключением, может быть, использования графического процессора для рисования всех областей и выполнения глобальной проверки попадания).

Так как статический тест заботится о начальной и конечной позиции каждого сегмента, нам просто нужно проверить пересечения с дугами, проходящими по каждому вращающемуся сегменту .

После интересной дискуссии с trichoplax и небольшим количеством JavaScript, чтобы разобраться, я разработал этот метод:

Чтобы попытаться изложить это в нескольких словах, если вы звоните

• С центр вращения,
• S вращающийся сегмент произвольной длины и направления, который не содержит C ,
• L линия, продолжающая S
• H линия, ортогональная L, проходящая через C ,
• Я пересечение L и H ,

_{(источник: free.fr )}

Для любого сегмента, который не содержит I , область развертки ограничена 2 дугами (и 2 сегментами, уже проверенными статической проверкой).

Если я попадаю в сегмент, дуга, пройденная мной, также должна быть принята во внимание.

Это означает, что мы можем проверить каждый неподвижный сегмент на каждом вращающемся сегменте с 2 или 3 пересечениями сегмент с дугой

Я использовал векторную геометрию, чтобы вообще избежать тригонометрических функций.
Векторные операции создают компактный и (относительно) читаемый код.

Пересечение сегмента с дугой требует вектора с плавающей запятой, но логика должна быть защищена от ошибок округления.
Я нашел это элегантное и эффективное решение в неясном сообщении на форуме. Интересно, почему это не так широко освещается.

Это работает?

Ингибирование динамического обнаружения столкновений приводит к правильному самодостаточному количеству путей до n = 19, так что я уверен, что глобальный макет работает.

Динамическое обнаружение столкновений дает согласованные результаты, хотя проверка изгибов в другом порядке отсутствует (на данный момент).
Как следствие, программа подсчитывает змей, которые могут быть согнуты от головы вниз (то есть со сложенными суставами в порядке увеличения расстояния от головы).