Este desafío no se trata del juego Snake.

Imagine una serpiente 2D formada dibujando una línea horizontal de longitud n. En los puntos enteros a lo largo de su cuerpo, esta serpiente puede girar su cuerpo en 90 grados. Si definimos que el frente de la serpiente esté en el extremo izquierdo para comenzar, la rotación moverá la parte posterior de la serpiente y la parte delantera se mantendrá en su lugar. Al hacer rotaciones repetidas, puede hacer muchas formas diferentes de cuerpo de serpiente.

Reglas

1. Una parte del cuerpo de la serpiente no puede solaparse con otra.
2. Tiene que ser posible alcanzar la orientación final sin que ninguna parte del cuerpo de la serpiente se superponga en el medio. Dos puntos que se tocan se cuentan como superpuestos en este problema.
3. Considero que una serpiente y su reverso tienen la misma forma.

Tarea

Hasta la rotación, la traslación y la simetría de espejo, ¿cuál es el número total de diferentes formas de cuerpo de serpiente que se pueden hacer?

Ejemplo de rotación de parte del cuerpo de la serpiente. Imagínese n=10y la serpiente está en su orientación inicial de una línea recta. Ahora gire en el punto 490 grados en sentido antihorario. Obtenemos la serpiente de 4a 10(la cola de la serpiente) que se encuentra en posición vertical y la serpiente de 0a 4posición horizontal. La serpiente ahora tiene un ángulo recto en su cuerpo.

Aquí hay algunos ejemplos gracias a Martin Büttner.

Comenzamos con la serpiente horizontal.

Ahora giramos desde la posición 4.

Terminamos después de la rotación en esta orientación.

Ahora consideremos esta orientación de una serpiente diferente.

Ahora podemos ver un movimiento ilegal donde habría una superposición causada durante la rotación.

Puntuación

Su puntaje es el mayor npara el cual su código puede resolver el problema en menos de un minuto en mi computadora.

Cuando ocurre una rotación, moverá la mitad de la serpiente con ella. Tenemos que preocuparnos si alguna de esta parte que se rota podría superponerse a una parte de la serpiente durante la rotación. Por simplicidad, podemos suponer que la serpiente tiene un ancho cero. Solo puede girar en un punto particular de la serpiente hasta 90 grados en sentido horario o antihorario. Porque, nunca puedes doblar por completo la serpiente en dos, ya que eso habría implicado dos rotaciones en el mismo punto en la misma dirección.

Formas que no se pueden hacer

Un ejemplo simple de una forma que no se puede hacer es una capital T. Una versión más sofisticada es

(Gracias a Harald Hanche-Olsen por este ejemplo)

En este ejemplo, todas las líneas horizontales adyacentes están separadas 1 como las verticales. Por lo tanto, no existe un movimiento legal desde esta posición y, dado que el problema es reversible, no hay forma de llegar desde la posición inicial.

Idiomas y bibliotecas

Puede usar cualquier idioma que tenga un compilador / intérprete / etc. para Linux y cualquier biblioteca que también esté disponible gratuitamente para Linux.

Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de ubuntu en un procesador AMD FX-8350 de ocho núcleos. Esto también significa que necesito poder ejecutar su código. Como consecuencia, solo use software gratuito fácilmente disponible e incluya instrucciones completas sobre cómo compilar y ejecutar su código.

Python 3 - puntaje provisional: n = 11 (n = 13 con PyPy *)

Como no hubo respuestas en la primera semana, aquí hay un ejemplo en Python para alentar la competencia. He intentado que sea razonablemente legible para que las ineficiencias puedan identificarse fácilmente y dar ideas para otras respuestas.

Acercarse

• Comience con la serpiente recta y encuentre todas las posiciones que se pueden alcanzar legalmente en un solo movimiento.
• Encuentre todos los puestos que se pueden alcanzar legalmente desde esos puestos, que aún no se han identificado.
• Repita hasta que no se pueda encontrar más, y devuelva el número de posiciones encontradas por completo.

Código

(ahora con algunos doctests y afirma después de mi primer intento incorrecto)

'''
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)))

Resultados

En mi máquina, la serpiente más larga que se puede calcular en menos de 1 minuto es la longitud 11 (o la longitud 13 con PyPy *). Obviamente, esto es solo un puntaje provisional hasta que descubramos cuál es el puntaje oficial de la máquina de Lembik.

A modo de comparación, aquí están los resultados para los primeros valores de 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)

Avíseme si alguno de estos resulta ser incorrecto.

Si tiene un ejemplo de un arreglo que no debería poder desplegarse, puede usar la función neighbours(snake)para encontrar cualquier arreglo accesible en un solo paso, como prueba del código. snakees una tupla de direcciones conjuntas (0 para sentido horario, 1 para derecho, 2 para sentido antihorario). Por ejemplo (1,1,1) es una serpiente recta de longitud 4 (con 3 articulaciones).

Visualización

Para visualizar una serpiente que tiene en mente, o cualquiera de las serpientes devueltas neighbours, puede usar la función display(snake). Esto acepta una tupla como las otras funciones, pero como no es utilizado por el programa principal y, por lo tanto, no necesita ser rápido, también aceptará una cadena, para su conveniencia.

display((1,1,2,0)) es equivalente a display("1120")

Como Lembik menciona en los comentarios, mis resultados son idénticos a OEIS A037245 que no tiene en cuenta las intersecciones durante la rotación. Esto se debe a que para los primeros valores de n no hay diferencia: todas las formas que no se intersectan a sí mismas se pueden alcanzar doblando una serpiente recta. La exactitud del código se puede probar llamando neighbours()a una serpiente que no se puede desplegar sin intersección. Como no tiene vecinos, solo contribuirá a la secuencia OEIS, y no a esta. El ejemplo más pequeño que conozco es esta serpiente de longitud 31 que Lembik mencionó, gracias a 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') da el siguiente resultado:

Consejo: Si cambia el tamaño de la ventana de visualización y luego vuelve a llamar, la serpiente se ajustará al nuevo tamaño de ventana.

Me encantaría saber de cualquiera que tenga un ejemplo más corto sin vecinos. Sospecho que el ejemplo más corto de este tipo marcará el n más pequeño para el que difieren las dos secuencias.

* Tenga en cuenta que cada incremento de n tarda aproximadamente 3 veces más, por lo que aumentar de n = 11 a n = 13 requiere casi 10 veces el tiempo. Es por eso que PyPy solo permite aumentar n en 2, a pesar de que se ejecuta considerablemente más rápido que el intérprete estándar de Python.

C ++ 11 - casi funciona :)

Después de leer este artículo , obtuve un poco de sabiduría de ese tipo que aparentemente trabajó durante 25 años en el problema menos complicado de contar caminos que se evitan en una red cuadrada.

#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;
}

Construyendo el ejecutable

Compile con Yo uso MinGW bajo Win7 con g ++ 4.8 para compilaciones "linux", por lo que la portabilidad no está 100% garantizada.g++ -O3 -std=c++11

También funciona (más o menos) con un proyecto estándar MSVC2013

Al no definir NDEBUG, obtiene rastros de la ejecución del algoritmo y un resumen de las configuraciones encontradas.

Actuaciones

con o sin tablas hash, el compilador de Microsoft funciona miserablemente: la compilación de g ++ es 3 veces más rápida .

El algoritmo prácticamente no usa memoria.

Dado que la verificación de colisión es aproximadamente en O (n), el tiempo de cálculo debe estar en O (nk ⁿ ), con k ligeramente inferior a 3.
En mi [email protected], n = 17 toma aproximadamente 1:30 (aproximadamente 2 millones serpientes / minuto).

No he terminado de optimizar, pero no esperaría más que una ganancia x3, así que básicamente puedo esperar alcanzar quizás n = 20 en menos de una hora, o n = 24 en menos de un día.

Alcanzar la primera forma imposible de doblar conocida (n = 31) tomaría entre unos años y una década, suponiendo que no haya cortes de energía.

Contando formas

Una serpiente de tamaño N tiene articulaciones N-1 .
Cada articulación puede dejarse recta o doblada hacia la izquierda o hacia la derecha (3 posibilidades).
El número de plegamientos posibles es, por lo tanto, 3 ^N-1 .
Las colisiones reducirán un poco ese número, por lo que el número real es cercano a 2.7 ^N-1

Sin embargo, muchos de estos pliegues conducen a formas idénticas.

dos formas son idénticas si hay una rotación o una simetría que puede transformar una en la otra.

Definamos un segmento como cualquier parte recta del cuerpo plegado.
Por ejemplo, una serpiente de tamaño 5 doblada en la segunda articulación tendría 2 segmentos (uno de 2 unidades de largo y el segundo de 3 unidades de largo).
El primer segmento se llamará cabeza y la última cola .

Por convención, orientamos la cabeza de las serpientes horizontalmente con el cuerpo apuntando hacia la derecha (como en la primera figura del OP).

Designamos una figura dada con una lista de longitudes de segmento con signo, con longitudes positivas que indican un plegado a la derecha y negativas a un plegado a la izquierda.
La longitud inicial es positiva por convención.

Separar segmentos y curvas

Si consideramos solo las diferentes formas en que una serpiente de longitud N puede dividirse en segmentos, terminamos con un reparto idéntico a las composiciones de N.

Usando el mismo algoritmo que se muestra en la página wiki, es fácil generar todas las 2 particiones ^N-1 posibles de la serpiente.

Cada partición a su vez generará todos los plegamientos posibles aplicando curvas a la izquierda o derecha a todas sus uniones. Uno de estos plegamientos se llamará configuración .

Todas las particiones posibles se pueden representar mediante un número entero de N-1 bits, donde cada bit representa la presencia de una unión. Llamaremos a este entero un generador .

Particiones de poda

Al notar que doblar una partición dada desde la cabeza hacia abajo es equivalente a doblar la partición simétrica desde la cola hacia arriba, podemos encontrar todas las parejas de particiones simétricas y eliminar una de cada dos.
El generador de una partición simétrica es el generador de la partición escrito en orden de bits inverso, que es trivialmente fácil y barato de detectar.

Esto eliminará casi la mitad de las particiones posibles, con la excepción de las particiones con generadores "palindrómicos" que no se modifican por la inversión de bits (por ejemplo, 00100100).

Cuidando las simetrías horizontales

Con nuestras convenciones (una serpiente comienza a apuntar a la derecha), la primera curva aplicada a la derecha producirá una familia de pliegues que serán simétricos horizontales de los que difieren solo en la primera curva.

Si decidimos que la primera curva siempre estará a la derecha, eliminaremos todas las simétricas horizontales de una sola vez.

Limpiando los palíndromos

Estos dos cortes son eficientes, pero no suficientes para cuidar estos molestos palíndromos.
La verificación más exhaustiva en el caso general es la siguiente:

considere una configuración C con una partición palindrómica.

• Si invertimos cada curva en C, terminamos con una simétrica horizontal de C.
• si invertimos C (aplicando curvas desde la cola hacia arriba), obtenemos la misma figura rotada a la derecha
• Si ambos invertimos e invertimos C, obtenemos la misma figura rotada a la izquierda.

Podríamos verificar cada nueva configuración contra las otras 3. Sin embargo, dado que ya generamos solo configuraciones que comienzan con un giro a la derecha, solo tenemos una simetría posible para verificar:

• la C invertida comenzará con un giro a la izquierda, que por construcción es imposible de duplicar
• fuera de las configuraciones invertidas e invertidas invertidas, solo una comenzará con un giro a la derecha.
  Esa es la única configuración que posiblemente podemos duplicar.

Eliminando duplicados sin almacenamiento

Mi enfoque inicial fue almacenar todas las configuraciones en una gran tabla hash, para eliminar duplicados al verificar la presencia de una configuración simétrica previamente calculada.

Gracias al artículo mencionado anteriormente, quedó claro que, dado que las particiones y los pliegues se almacenan como campos de bits, se pueden comparar como cualquier valor numérico.
Entonces, para eliminar un miembro de un par simétrico, simplemente puede comparar ambos elementos y mantener sistemáticamente el más pequeño (o el más grande, como desee).

Por lo tanto, probar una configuración para duplicación equivale a calcular la partición simétrica, y si ambas son idénticas, el plegamiento. No se necesita memoria en absoluto.

Orden de generación

Claramente, la verificación de colisión será la parte que más tiempo requiera, por lo que reducir estos cálculos es un gran ahorro de tiempo.

Una posible solución es tener una "serpiente de muñeca de trapo" que comenzará en una configuración plana y se doblará gradualmente, para evitar volver a calcular toda la geometría de la serpiente para cada configuración posible.

Al elegir el orden en el que se prueban las configuraciones, de modo que como máximo se almacene una muñeca de trapo para cada número total de uniones, podemos limitar el número de instancias a N-1.

Utilizo una exploración recursiva del sake desde la cola hacia abajo, agregando una sola articulación en cada nivel. Por lo tanto, se crea una nueva instancia de ragdoll sobre la configuración principal, con una sola curva adicional.

Esto significa que las curvas se aplican en un orden secuencial, lo que parece ser suficiente para evitar auto colisiones en casi todos los casos.

Cuando se detecta la auto-colisión, las curvas que conducen al movimiento ofensivo se aplican en todas las órdenes posibles hasta que se encuentre un plegado legítimo o se agoten todas las combinaciones.

Control estático

Antes incluso de pensar en las partes móviles, me pareció más eficiente probar la forma final estática de una serpiente para autointercepciones.

Esto se hace dibujando la serpiente en una cuadrícula. Cada punto posible se traza desde la cabeza hacia abajo. Si hay una auto-intersección, al menos un par de puntos caerán en la misma ubicación. Esto requiere exactamente N parcelas para cualquier configuración de serpiente, durante un tiempo constante de O (N).

La principal ventaja de este enfoque es que la prueba estática por sí sola simplemente seleccionará rutas válidas de auto evitación en una red cuadrada, lo que permite probar todo el algoritmo al inhibir la detección de colisión dinámica y asegurarse de que encontremos el recuento correcto de tales rutas.

Control dinámico

Cuando una serpiente se pliega alrededor de una articulación, cada segmento girado barrerá un área cuya forma es cualquier cosa menos trivial.
Claramente, puede verificar las colisiones probando la inclusión en todas las áreas barridas individualmente. Una verificación global sería más eficiente, pero dada la complejidad de las áreas no puedo pensar en ninguna (excepto tal vez usando una GPU para dibujar todas las áreas y realizar una verificación de impacto global).

Dado que la prueba estática se ocupa de las posiciones inicial y final de cada segmento, solo necesitamos verificar las intersecciones con los arcos barridos por cada segmento giratorio.

Después de una interesante discusión con trichoplax y un poco de JavaScript para orientarme, se me ocurrió este método:

Para tratar de ponerlo en pocas palabras, si llamas

• C el centro de rotación,
• S un segmento giratorio de longitud arbitraria y dirección que no contiene C ,
• L la línea que prolonga S
• H la línea ortogonal a L que pasa por C ,
• I la intersección de L y H ,

_{(fuente: free.fr )}

Para cualquier segmento que no contenga I , el área barrida está unida por 2 arcos (y 2 segmentos ya atendidos por la verificación estática).

Si I cae dentro del segmento, el arco barrido por I también debe tenerse en cuenta.

Esto significa que podemos verificar cada segmento inmóvil contra cada segmento giratorio con 2 o 3 intersecciones de segmento con arco

Usé geometría vectorial para evitar las funciones trigonométricas por completo.
Las operaciones vectoriales producen código compacto y (relativamente) legible.

La intersección de segmento a arco requiere un vector de punto flotante, pero la lógica debe ser inmune a los errores de redondeo.
Encontré esta solución elegante y eficiente en una oscura publicación del foro. Me pregunto por qué no se publicita más ampliamente.

¿Funciona?

La inhibición de la detección dinámica de colisión produce el recuento correcto de rutas de autoevaluación hasta n = 19, por lo que estoy bastante seguro de que el diseño global funciona.

La detección dinámica de colisión produce resultados consistentes, aunque falta la comprobación de curvas en diferente orden (por ahora).
Como consecuencia, el programa cuenta las serpientes que pueden doblarse de la cabeza hacia abajo (es decir, con las articulaciones plegadas en orden de distancia creciente de la cabeza).