Ce défi ne concerne pas le jeu Snake.

Imaginez un serpent 2D formé en dessinant une ligne horizontale de longueur n . Aux points entiers le long de son corps, ce serpent peut faire pivoter son corps de 90 degrés. Si nous définissons l'avant du serpent comme étant à l'extrême gauche pour commencer, la rotation déplacera la partie arrière du serpent et la partie avant restera en place. En effectuant des rotations répétées, il peut créer de nombreuses formes de corps de serpent différentes.

Règles

1. Une partie du corps du serpent ne peut pas en chevaucher une autre.
2. Il doit être possible d'atteindre l'orientation finale sans qu'aucune partie du corps du serpent ne se chevauche. Deux points qui se touchent sont comptés comme se chevauchant dans ce problème.
3. Je considère un serpent et son revers comme ayant la même forme.

Tâche

Jusqu'à la rotation, la translation et la symétrie miroir, quel est le nombre total de formes de corps de serpent différentes qui peuvent être faites?

Exemple de rotation d'une partie du corps du serpent. Imaginez n=10et le serpent est dans son orientation de départ d'une ligne droite. Tournez maintenant au point 490 degrés dans le sens antihoraire. Nous obtenons le serpent de 4à 10(la queue du serpent) couché verticalement et le serpent de 0à 4couché horizontalement. Le serpent a maintenant un angle droit dans son corps.

Voici quelques exemples grâce à Martin Büttner.

Nous commençons par le serpent horizontal.

Maintenant, nous tournons de la position 4.

On se retrouve après la rotation dans cette orientation.

Considérons maintenant cette orientation d'un serpent différent.

Nous pouvons maintenant voir un mouvement illégal où il y aurait un chevauchement causé pendant la rotation.

But

Votre score est le plus élevé npour lequel votre code peut résoudre le problème en moins d'une minute sur mon ordinateur.

Lorsqu'une rotation se produit, elle déplace une moitié du serpent avec elle. Nous devons nous inquiéter de savoir si une partie de cette partie en rotation pourrait chevaucher une partie du serpent pendant la rotation. Pour simplifier, nous pouvons supposer que le serpent a une largeur nulle. Vous ne pouvez tourner qu'à un point particulier du serpent jusqu'à 90 degrés dans le sens horaire ou antihoraire. Car, vous ne pouvez jamais plier complètement le serpent en deux car cela aurait impliqué deux rotations au même point dans la même direction.

Formes impossibles à réaliser

Un exemple simple d'une forme qui ne peut pas être faite est une majuscule T. Une version plus sophistiquée est

(Merci à Harald Hanche-Olsen pour cet exemple)

Dans cet exemple, toutes les lignes horizontales adjacentes sont séparées de 1, tout comme les verticales. Il n'y a donc pas de mouvement légal à partir de cette position et comme le problème est réversible il n'y a donc aucun moyen d'y arriver depuis la position de départ.

Langues et bibliothèques

Vous pouvez utiliser n'importe quelle langue disposant d'un compilateur / interprète / etc disponible gratuitement. pour Linux et toutes les bibliothèques qui sont également disponibles gratuitement pour Linux.

Ma machine Les horaires seront exécutés sur ma machine. Il s'agit d'une installation ubuntu standard sur un processeur AMD FX-8350 à huit cœurs. Cela signifie également que je dois pouvoir exécuter votre code. Par conséquent, n'utilisez que des logiciels gratuits facilement disponibles et veuillez inclure des instructions complètes sur la façon de compiler et d'exécuter votre code.

Python 3 - score provisoire: n = 11 (n = 13 avec PyPy *)

Puisqu'il n'y a eu aucune réponse la première semaine, voici un exemple en Python pour encourager la compétition. J'ai essayé de le rendre raisonnablement lisible afin que les inefficacités puissent être facilement identifiées pour donner des idées pour d'autres réponses.

Approche

• Commencez avec le serpent droit et trouvez toutes les positions qui peuvent être légalement atteintes en un seul mouvement.
• Trouvez toutes les positions qui peuvent être légalement atteintes à partir de ces positions, qui n'ont pas encore été identifiées.
• Répétez jusqu'à ce qu'il n'y en ait plus et retournez le nombre total de positions trouvées.

Code

(maintenant avec quelques doctests et assert après ma première tentative incorrecte)

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

Résultats

Sur ma machine, le serpent le plus long qui peut être calculé en moins d'une minute est la longueur 11 (ou la longueur 13 avec PyPy *). Ce n'est évidemment qu'un score provisoire jusqu'à ce que nous découvrions le score officiel de la machine de Lembik.

À titre de comparaison, voici les résultats des premières valeurs 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)

Veuillez me faire savoir si l'un de ces éléments s'avère incorrect.

Si vous avez un exemple d'arrangement qui ne doit pas pouvoir être déplié, vous pouvez utiliser la fonction neighbours(snake)pour rechercher tous les arrangements accessibles en une seule étape, comme test du code.snakeest un tuple de directions communes (0 pour le sens horaire, 1 pour le droit, 2 pour le sens antihoraire). Par exemple (1,1,1) est un serpent droit de longueur 4 (avec 3 articulations).

Visualisation

Pour visualiser un serpent que vous avez en tête, ou l'un des serpents retournés par neighbours, vous pouvez utiliser la fonctiondisplay(snake) . Cela accepte un tuple comme les autres fonctions, mais comme il n'est pas utilisé par le programme principal et n'a donc pas besoin d'être rapide, il acceptera également une chaîne, pour votre commodité.

display((1,1,2,0)) est équivalent à display("1120")

Comme Lembik le mentionne dans les commentaires, mes résultats sont identiques à OEIS A037245 qui ne prend pas en compte les intersections lors de la rotation. En effet, pour les premières valeurs de n, il n'y a pas de différence - toutes les formes qui ne s'entrecoupent pas peuvent être atteintes en pliant un serpent droit. L'exactitude du code peut être testée en appelant neighbours()avec un serpent qui ne peut pas être déplié sans intersection. Comme il n'a pas de voisins, il ne contribuera qu'à la séquence OEIS et non à celle-ci. Le plus petit exemple que je connaisse est ce serpent de longueur 31 que Lembik a mentionné, grâce à 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') donne la sortie suivante:

Astuce: Si vous redimensionnez la fenêtre d'affichage, puis appelez à nouveau l'affichage, le serpent sera ajusté à la nouvelle taille de la fenêtre.

J'adorerais entendre quelqu'un qui a un exemple plus court sans voisin. Je soupçonne que l'exemple le plus court marquera le plus petit n pour lequel les deux séquences diffèrent.

* Notez que chaque incrément de n prend environ 3 fois plus de temps, donc passer de n = 11 à n = 13 nécessite presque 10 fois le temps. C'est pourquoi PyPy permet uniquement d'augmenter n de 2, même s'il s'exécute considérablement plus rapidement que l'interpréteur Python standard.

C ++ 11 - fonctionne presque :)

Après avoir lu cet article , j'ai recueilli des morceaux de sagesse de ce gars qui a apparemment travaillé pendant 25 ans sur le problème moins compliqué de compter les chemins d'auto-évitement sur un réseau carré.

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

Construire l'exécutable

Compiler avec J'utilise MinGW sous Win7 avec g ++ 4.8 pour les builds "linux", donc la portabilité n'est pas garantie à 100%.g++ -O3 -std=c++11

Il fonctionne également (en quelque sorte) avec un projet MSVC2013 standard

En définissant NDEBUG, vous obtenez des traces d'exécution de l'algorithme et un résumé des configurations trouvées.

Les performances

avec ou sans tables de hachage, le compilateur Microsoft fonctionne misérablement: la construction g ++ est 3 fois plus rapide .

L'algorithme n'utilise pratiquement pas de mémoire.

Étant donné que le contrôle de collision est à peu près en O (n), le temps de calcul doit être en O (nk ⁿ ), avec k légèrement inférieur à 3.
Sur mon [email protected], n = 17 prend environ 1:30 (environ 2 millions serpents / minute).

Je n'ai pas fini d'optimiser, mais je ne m'attendrais pas à plus d'un gain x3, donc en gros je peux espérer atteindre peut-être n = 20 en moins d'une heure, ou n = 24 en moins d'une journée.

Atteindre la première forme inflexible connue (n = 31) prendrait entre quelques années et une décennie, en supposant qu'aucune panne de courant.

Compter les formes

A N serpent de taille a N-1 articulations.
Chaque articulation peut être laissée droite ou pliée à gauche ou à droite (3 possibilités).
Le nombre de pliages possibles est donc de 3 ^N-1 .
Les collisions réduiront quelque peu ce nombre, de sorte que le nombre réel est proche de 2,7 ^N-1

Cependant, de nombreux pliages de ce type conduisent à des formes identiques.

deux formes sont identiques s'il y a soit une rotation soit une symétrie qui peuvent se transformer l'une en l'autre.

Définissons un segment comme n'importe quelle partie droite du corps plié.
Par exemple, un serpent de taille 5 plié à la 2e articulation aurait 2 segments (un de 2 unités de long et le second de 3 unités de long).
Le premier segment sera nommé tête et la dernière queue .

Par convention, nous orientons la tête du serpent horizontalement avec le corps pointé vers la droite (comme dans la première figure OP).

Nous désignons une figure donnée avec une liste de longueurs de segments signées, avec des longueurs positives indiquant un pliage à droite et des négatives un pliage à gauche.
La longueur initiale est positive par convention.

Séparation des segments et des coudes

Si nous considérons uniquement les différentes façons dont un serpent de longueur N peut être divisé en segments, nous nous retrouvons avec une répartition identique aux compositions de N.

En utilisant le même algorithme que celui montré sur la page wiki, il est facile de générer toutes les 2 ^N-1 partitions possibles du serpent.

Chaque cloison générera à son tour tous les plis possibles en appliquant des plis à gauche ou à droite à tous ses joints. Un tel pliage sera appelé configuration .

Toutes les partitions possibles peuvent être représentées par un entier de N-1 bits, où chaque bit représente la présence d'un joint. Nous appellerons cet entier un générateur .

Élagage des partitions

En remarquant que plier une partition donnée de la tête vers le bas équivaut à plier la partition symétrique de la queue vers le haut, nous pouvons trouver tous les couples de partitions symétriques et éliminer une sur deux.
Le générateur d'une partition symétrique est le générateur de la partition écrit dans l'ordre inverse des bits, ce qui est trivialement facile et bon marché à détecter.

Cela éliminera près de la moitié des partitions possibles, les exceptions étant les partitions avec des générateurs "palindromiques" qui restent inchangés par inversion de bits (par exemple 00100100).

Prendre soin des symétries horizontales

Avec nos conventions (un serpent commence à pointer vers la droite), le tout premier pli appliqué à droite produira une famille de pliages qui seront symétriques horizontaux de ceux qui ne diffèrent que par le premier pli.

Si nous décidons que le premier virage sera toujours vers la droite, nous éliminons toutes les symétries horizontales d'un seul coup.

Nettoyer les palindromes

Ces deux coupes sont efficaces, mais pas suffisantes pour prendre soin de ces palindromes embêtants.
La vérification la plus approfondie dans le cas général est la suivante:

considérons une configuration C avec une partition palindromique.

• si nous inversons chaque virage en C, nous nous retrouvons avec une symétrique horizontale de C.
• si nous inversons C (en appliquant des virages de la queue vers le haut), nous obtenons la même figure tournée vers la droite
• si nous inversons et inversons C tous les deux, nous obtenons la même figure tournée vers la gauche.

Nous pourrions vérifier chaque nouvelle configuration par rapport aux 3 autres. Cependant, comme nous ne générons déjà que des configurations commençant par un virage à droite, nous n'avons qu'une seule symétrie possible à vérifier:

• le C inversé commencera par un virage à gauche, ce qui est par construction impossible à reproduire
• sur les configurations inversée et inversée-inversée, une seule commencera par un virage à droite.
  C'est la seule configuration que nous pouvons éventuellement dupliquer.

Éliminer les doublons sans stockage

Mon approche initiale était de stocker toutes les configurations dans une énorme table de hachage, pour éliminer les doublons en vérifiant la présence d'une configuration symétrique précédemment calculée.

Grâce à l'article précité, il est devenu clair que, comme les partitions et les pliages sont stockés sous forme de champs binaires, ils peuvent être comparés comme n'importe quelle valeur numérique.
Donc, pour éliminer un membre d'une paire symétrique, vous pouvez simplement comparer les deux éléments et garder systématiquement le plus petit (ou le plus grand, comme vous le souhaitez).

Ainsi, tester une configuration pour la duplication revient à calculer la partition symétrique, et si les deux sont identiques, le pliage. Aucune mémoire n'est nécessaire du tout.

Ordre de génération

Il est clair que la vérification des collisions sera la partie la plus longue, donc la réduction de ces calculs est un gain de temps majeur.

Une solution possible est d'avoir un "serpent ragdoll" qui commencera dans une configuration plate et sera progressivement plié, pour éviter de recalculer la géométrie entière du serpent pour chaque configuration possible.

En choisissant l'ordre dans lequel les configurations sont testées, de sorte qu'au plus un chiffon soit stocké pour chaque nombre total de joints, nous pouvons limiter le nombre d'instances à N-1.

J'utilise une analyse récursive du saké de la queue vers le bas, en ajoutant une seule articulation à chaque niveau. Ainsi, une nouvelle instance de ragdoll est construite au-dessus de la configuration parent, avec un seul virage supplémentaire.

Cela signifie que les plis sont appliqués dans un ordre séquentiel, ce qui semble être suffisant pour éviter les auto-collisions dans presque tous les cas.

Lorsque l'auto-collision est détectée, les virages qui conduisent au mouvement offensant sont appliqués dans tous les ordres possibles jusqu'à ce que le repli légitime soit trouvé ou que toutes les combinaisons soient épuisées.

Contrôle statique

Avant même de penser aux pièces mobiles, j'ai trouvé plus efficace de tester la forme finale statique d'un serpent pour les auto-intersections.

Cela se fait en dessinant le serpent sur une grille. Chaque point possible est tracé de la tête vers le bas. S'il y a une auto-intersection, au moins une paire de points tombera au même endroit. Cela nécessite exactement N tracés pour toute configuration de serpent, pour un temps O (N) constant.

Le principal avantage de cette approche est que le test statique à lui seul sélectionnera simplement des chemins valables auto-évitables sur un réseau carré, ce qui permet de tester l'ensemble de l'algorithme en inhibant la détection de collision dynamique et en nous assurant de trouver le nombre correct de ces chemins.

Contrôle dynamique

Lorsqu'un serpent se replie autour d'une articulation, chaque segment pivoté balaie une zone dont la forme est tout sauf anodine.
De toute évidence, vous pouvez vérifier les collisions en testant l'inclusion dans toutes ces zones balayées individuellement. Une vérification globale serait plus efficace, mais compte tenu de la complexité des zones, je ne peux penser à aucune (sauf peut-être à l'aide d'un GPU pour dessiner toutes les zones et effectuer une vérification globale).

Étant donné que le test statique prend en charge les positions de début et de fin de chaque segment, il nous suffit de vérifier les intersections avec les arcs balayés par chaque segment en rotation.

Après une discussion intéressante avec trichoplax et un peu de JavaScript pour me repérer, j'ai trouvé cette méthode:

Pour essayer de le dire en quelques mots, si vous appelez

• C le centre de rotation,
• S un segment tournant de longueur et de direction arbitraires qui ne contient pas C ,
• L la ligne prolongeant S
• H la ligne orthogonale à L passant par C ,
• I l'intersection de L et H ,

_{(source: free.fr )}

Pour tout segment ne contenant pas de I , la zone balayée est délimitée par 2 arcs (et 2 segments déjà pris en charge par le contrôle statique).

Si je tombe dans le segment, l'arc balayé par I doit également être pris en compte.

Cela signifie que nous pouvons comparer chaque segment immobile contre chaque segment rotatif avec 2 ou 3 intersections segment-avec-arc

J'ai utilisé la géométrie vectorielle pour éviter complètement les fonctions trigonométriques.
Les opérations vectorielles produisent du code compact et (relativement) lisible.

L'intersection segment-arc nécessite un vecteur à virgule flottante, mais la logique doit être à l'abri des erreurs d'arrondi.
J'ai trouvé cette solution élégante et efficace dans un post obscur sur le forum. Je me demande pourquoi il n'est pas plus largement diffusé.

Est-ce que ça marche?

L'inhibition de la détection de collision dynamique produit le nombre de chemins auto-évitants corrects jusqu'à n = 19, donc je suis assez confiant que la disposition globale fonctionne.

La détection de collision dynamique produit des résultats cohérents, bien que la vérification des virages dans un ordre différent soit manquante (pour l'instant).
Par conséquent, le programme compte les serpents qui peuvent être courbés de la tête vers le bas (c'est-à-dire avec les articulations repliées par ordre croissant de distance de la tête).