Bei dieser Herausforderung geht es nicht um das Spiel Snake.

Stellen Sie sich eine 2D-Schlange vor, die durch Zeichnen einer horizontalen Längenlinie gebildet wird n. An ganzzahligen Punkten entlang ihres Körpers kann diese Schlange ihren Körper um 90 Grad drehen. Wenn wir die Vorderseite der Schlange so definieren, dass sie sich ganz links befindet, bewegt die Drehung den hinteren Teil der Schlange und der vordere Teil bleibt stehen. Durch wiederholte Rotationen können viele verschiedene Schlangenkörperformen hergestellt werden.

Regeln

1. Ein Teil des Körpers der Schlange kann einen anderen nicht überlappen.
2. Es muss möglich sein, die endgültige Ausrichtung zu erreichen, ohne dass sich Teile des Körpers der Schlange dazwischen überlappen. Zwei Punkte, die sich berühren, werden in diesem Problem als überlappend gezählt.
3. Ich betrachte eine Schlange und ihre Rückseite als dieselbe Form.

Aufgabe

Wie viele verschiedene Schlangenkörperformen können bis zu Rotation, Translation und Spiegelsymmetrie hergestellt werden?

Beispiel einer Rotation eines Teils des Schlangenkörpers. Stellen Sie sich vor n=10und die Schlange befindet sich in ihrer Startausrichtung einer geraden Linie. Drehen Sie nun um 490 Grad gegen den Uhrzeigersinn. Wir lassen die Schlange von 4bis 10(den Schwanz der Schlange) vertikal liegen und die Schlange von 0bis 4horizontal liegen. Die Schlange hat jetzt einen rechten Winkel in ihrem Körper.

Hier einige Beispiele dank Martin Büttner.

Wir beginnen mit der horizontalen Schlange.

Jetzt drehen wir uns von Position 4.

Wir landen nach der Rotation in dieser Ausrichtung.

Betrachten wir nun diese Ausrichtung einer anderen Schlange.

Wir können jetzt eine illegale Bewegung sehen, bei der es während der Rotation zu einer Überlappung kommen würde.

Ergebnis

Ihre Punktzahl ist die größte, nfür die Ihr Code das Problem auf meinem Computer in weniger als einer Minute lösen kann.

Wenn eine Rotation stattfindet, bewegt sie eine Hälfte der Schlange mit. Wir müssen uns Sorgen machen, ob irgendein Teil dieses gedrehten Teils einen Teil der Schlange während der Drehung überlappen könnte. Der Einfachheit halber können wir annehmen, dass die Schlange die Breite Null hat. Sie können nur an einer bestimmten Stelle in der Schlange bis zu 90 Grad im Uhrzeigersinn oder gegen den Uhrzeigersinn drehen. Denn Sie können die Schlange niemals vollständig in zwei Teile falten, da dies zwei Umdrehungen am gleichen Punkt in die gleiche Richtung zur Folge gehabt hätte.

Formen, die nicht gemacht werden können

Ein einfaches Beispiel für eine Form, die nicht hergestellt werden kann, ist ein Kapital T. Eine anspruchsvollere Version ist

(Vielen Dank an Harald Hanche-Olsen für dieses Beispiel)

In diesem Beispiel sind alle benachbarten horizontalen Linien 1 voneinander entfernt, ebenso wie die vertikalen. Es gibt daher keinen legalen Wechsel von dieser Position und da das Problem umkehrbar ist, gibt es keine Möglichkeit, von der Startposition dorthin zu gelangen.

Sprachen und Bibliotheken

Sie können jede Sprache verwenden, die einen frei verfügbaren Compiler / Interpreter / etc. für Linux und alle Bibliotheken, die auch für Linux frei verfügbar sind.

Meine Maschine Die Timings werden auf meiner Maschine ausgeführt. Dies ist eine Standard-Ubuntu-Installation auf einem AMD FX-8350 Eight-Core-Prozessor. Dies bedeutet auch, dass ich Ihren Code ausführen kann. Verwenden Sie daher nur leicht verfügbare freie Software und fügen Sie bitte vollständige Anweisungen zum Kompilieren und Ausführen Ihres Codes bei.

Python 3 - vorläufige Punktzahl: n = 11 (n = 13 mit PyPy *)

Da es in der ersten Woche keine Antworten gab, finden Sie hier ein Beispiel in Python, um den Wettbewerb zu fördern. Ich habe versucht, es einigermaßen lesbar zu machen, damit Ineffizienzen leicht identifiziert werden können, um Ideen für andere Antworten zu geben.

Ansatz

• Beginnen Sie mit der geraden Schlange und finden Sie alle Positionen, die legal erreicht werden können, in einem Zug.
• Finden Sie alle Positionen, die legal von diesen Positionen aus erreicht werden können, die noch nicht identifiziert wurden.
• Wiederholen Sie diesen Vorgang, bis keine weiteren mehr gefunden werden können, und geben Sie die Anzahl der insgesamt gefundenen Positionen zurück.

Code

(jetzt mit einigen Doktrinen und Behauptungen nach meinem falschen ersten Versuch)

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

Ergebnisse

Auf meinem Computer ist die längste Schlange, die in weniger als 1 Minute berechnet werden kann, Länge 11 (oder Länge 13 mit PyPy *). Dies ist offensichtlich nur eine vorläufige Punktzahl, bis wir herausfinden, wie die offizielle Punktzahl von Lembiks Maschine stammt.

Zum Vergleich sind hier die Ergebnisse für die ersten Werte von 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)

Bitte lassen Sie mich wissen, wenn sich herausstellt, dass eine dieser Angaben falsch ist.

Wenn Sie ein Beispiel für eine Anordnung haben, die nicht entfaltet werden kann, können Sie die Funktion verwenden neighbours(snake), um alle in einem Schritt erreichbaren Anordnungen als Test des Codes zu finden. snakeist ein Tupel von Gelenkrichtungen (0 für im Uhrzeigersinn, 1 für gerade, 2 für gegen den Uhrzeigersinn). Zum Beispiel ist (1,1,1) eine gerade Schlange der Länge 4 (mit 3 Gelenken).

Visualisierung

Um eine Schlange oder eine der von neighboursIhnen zurückgegebenen Schlangen zu visualisieren , können Sie die Funktion verwenden display(snake). Dies akzeptiert ein Tupel wie die anderen Funktionen, aber da es nicht vom Hauptprogramm verwendet wird und daher nicht schnell sein muss, akzeptiert es auch eine Zeichenfolge.

display((1,1,2,0)) ist äquivalent zu display("1120")

Wie Lembik in den Kommentaren erwähnt, sind meine Ergebnisse identisch mit denen von OEIS A037245, bei denen Schnittpunkte während der Rotation nicht berücksichtigt werden. Dies liegt daran, dass es für die ersten Werte von n keinen Unterschied gibt - alle Formen, die sich nicht selbst schneiden, können durch Falten einer geraden Schlange erreicht werden. Die Richtigkeit des Codes kann getestet werden, indem neighbours()mit einer Schlange aufgerufen wird, die ohne Kreuzung nicht entfaltet werden kann. Da es keine Nachbarn hat, trägt es nur zur OEIS-Sequenz bei und nicht zu dieser. Das kleinste mir bekannte Beispiel ist diese Schlange der Länge 31, die Lembik dank David K ​​erwähnt hat :

(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') gibt folgende Ausgabe:

Tipp: Wenn Sie die Größe des Anzeigefensters ändern und die Anzeige erneut aufrufen, wird die Schlange an die neue Fenstergröße angepasst.

Ich würde gerne von jedem hören, der ein kürzeres Beispiel ohne Nachbarn hat. Ich vermute, dass das kürzeste derartige Beispiel das kleinste n markiert, für das sich die beiden Sequenzen unterscheiden.

* Beachten Sie, dass jedes Inkrement von n ungefähr dreimal so lange dauert, sodass das Erhöhen von n = 11 auf n = 13 fast das Zehnfache der Zeit erfordert. Aus diesem Grund erlaubt PyPy nur, n um 2 zu erhöhen, obwohl es erheblich schneller als der Standard-Python-Interpreter läuft.

C ++ 11 - funktioniert fast :)

Nachdem ich diesen Artikel gelesen hatte , sammelte ich ein bisschen Weisheit von dem Typ, der anscheinend 25 Jahre lang an dem weniger komplizierten Problem gearbeitet hatte, selbstvermeidende Pfade auf einem quadratischen Gitter zu zählen.

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

Erstellen der ausführbaren Datei

Kompilieren mit Ich verwende MinGW unter Win7 mit g ++ 4.8 für "Linux" -Builds, sodass die Portabilität nicht zu 100% garantiert ist.g++ -O3 -std=c++11

Es funktioniert auch (irgendwie) mit einem Standard-MSVC2013-Projekt

Durch Aufheben der Definition erhalten NDEBUGSie Spuren der Algorithmusausführung und eine Zusammenfassung der gefundenen Konfigurationen.

Aufführungen

Mit oder ohne Hash-Tabellen arbeitet der Microsoft-Compiler miserabel: Die Erstellung von g ++ ist dreimal schneller .

Der Algorithmus verwendet praktisch keinen Speicher.

Da die Kollisionsprüfung ungefähr in O (n) liegt, sollte die Rechenzeit in O (nk ⁿ ) liegen, wobei k etwas niedriger als 3 ist.
Auf meinem [email protected] dauert n = 17 ungefähr 1:30 (ungefähr 2 Millionen) Schlangen / Minute).

Ich bin noch nicht mit der Optimierung fertig, aber ich würde nicht mehr als einen x3-Gewinn erwarten, also kann ich im Grunde hoffen, unter einer Stunde vielleicht n = 20 oder unter einem Tag n = 24 zu erreichen.

Das Erreichen der ersten bekannten nicht biegbaren Form (n = 31) würde zwischen einigen Jahren und einem Jahrzehnt dauern, sofern keine Stromausfälle vorliegen.

Formen zählen

Eine Schlange der Größe N hat N-1- Gelenke.
Jedes Gelenk kann gerade gelassen oder nach links oder rechts gebogen werden (3 Möglichkeiten).
Die Anzahl der möglichen Faltungen beträgt somit 3 ^N-1 .
Kollisionen reduzieren diese Zahl etwas, sodass die tatsächliche Zahl nahe bei 2,7 ^{N-1 liegt}

Viele solcher Faltungen führen jedoch zu identischen Formen.

Zwei Formen sind identisch, wenn es entweder eine Rotation oder eine Symmetrie gibt , die sich ineinander verwandeln kann.

Definieren wir ein Segment als einen geraden Teil des gefalteten Körpers.
Zum Beispiel würde eine Schlange der Größe 5, die am 2. Gelenk gefaltet ist, 2 Segmente haben (eines 2 Einheiten lang und das zweite 3 Einheiten lang).
Das erste Segment wird Kopf und der letzte Schwanz genannt .

Konventionell richten wir den Kopf der Schlangen horizontal aus, wobei der Körper nach rechts zeigt (wie in der ersten Abbildung des OP).

Wir bezeichnen eine gegebene Figur mit einer Liste vorzeichenbehafteter Segmentlängen, wobei positive Längen eine rechte Faltung und negative eine linke Faltung anzeigen.
Die Anfangslänge ist gemäß Konvention positiv.

Segmente und Biegungen trennen

Wenn wir nur die verschiedenen Möglichkeiten betrachten, wie eine Schlange der Länge N in Segmente aufgeteilt werden kann, erhalten wir eine Aufteilung, die mit den Zusammensetzungen von N identisch ist .

Mit dem gleichen Algorithmus wie auf der Wiki-Seite gezeigt, ist es einfach, alle 2 ^N-1 möglichen Partitionen der Schlange zu generieren .

Jede Trennwand erzeugt wiederum alle möglichen Faltungen, indem entweder alle ihre Gelenke nach links oder rechts gebogen werden. Eine solche Faltung wird als Konfiguration bezeichnet .

Alle möglichen Partitionen können durch eine ganze Zahl von N-1 Bits dargestellt werden, wobei jedes Bit das Vorhandensein einer Verbindung darstellt. Wir werden diese ganze Zahl einen Generator nennen .

Trennwände

Wenn wir feststellen, dass das Biegen einer bestimmten Partition vom Kopf nach unten dem Biegen der symetrischen Partition vom Schwanz nach oben entspricht, können wir alle Paare symetrischer Partitionen finden und eins von zwei eliminieren.
Der Generator einer symmetrischen Partition ist der Generator der Partition, der in umgekehrter Bitreihenfolge geschrieben ist, was trivial einfach und billig zu erkennen ist.

Dadurch wird fast die Hälfte der möglichen Partitionen eliminiert, mit Ausnahme der Partitionen mit "palindromischen" Generatoren, die durch Bitumkehr unverändert bleiben (z. B. 00100100).

Auf horizontale Symetrien achten

Mit unseren Konventionen (eine Schlange zeigt nach rechts) erzeugt die allererste Biegung, die nach rechts angewendet wird, eine Familie von Faltungen, die horizontal symmetrisch zu denen sind, die sich nur durch die erste Biegung unterscheiden.

Wenn wir entscheiden, dass die erste Biegung immer rechts ist, eliminieren wir alle horizontalen Symmetrien auf einen Schlag.

Palindrome aufwischen

Diese beiden Schnitte sind effizient, aber nicht genug, um diese lästigen Palindrome zu behandeln.
Die gründlichste Überprüfung im allgemeinen Fall ist wie folgt:

Betrachten Sie eine Konfiguration C mit einer palindromischen Partition.

• Wenn wir jede Biegung in C invertieren , erhalten wir eine horizontale Symmetrie von C.
• Wenn wir C umkehren (Biegen vom Schwanz nach oben anwenden), wird dieselbe Figur nach rechts gedreht
• Wenn wir beide C umkehren und umkehren, wird dieselbe Figur nach links gedreht.

Wir könnten jede neue Konfiguration mit den 3 anderen vergleichen. Da wir jedoch bereits Konfigurationen generieren, die mit einer Rechtskurve beginnen, müssen wir nur eine mögliche Symmetrie überprüfen:

• Das umgekehrte C beginnt mit einer Linkskurve, die konstruktionsbedingt nicht dupliziert werden kann
• Von den umgekehrten und invertierten Umkehrkonfigurationen beginnt nur eine mit einer Rechtskurve.
  Dies ist die einzige Konfiguration, die wir möglicherweise duplizieren können.

Eliminieren von Duplikaten ohne Speicher

Mein ursprünglicher Ansatz bestand darin, alle Konfigurationen in einer riesigen Hash-Tabelle zu speichern, um Duplikate zu beseitigen, indem ich das Vorhandensein einer zuvor berechneten symetrischen Konfiguration überprüfe.

Dank des oben genannten Artikels wurde klar, dass Partitionen und Faltungen, die als Bitfelder gespeichert sind, wie jeder numerische Wert verglichen werden können.
Um ein Mitglied eines symetrischen Paares zu eliminieren, können Sie einfach beide Elemente vergleichen und systematisch das kleinste (oder das größte, wie Sie möchten) beibehalten.

Das Testen einer Konfiguration auf Duplizierung bedeutet also, die symetrische Partition und, wenn beide identisch sind, die Faltung zu berechnen. Es wird überhaupt kein Speicher benötigt.

Reihenfolge der Erzeugung

Die Kollisionsprüfung ist eindeutig der zeitaufwändigste Teil, daher ist die Reduzierung dieser Berechnungen eine große Zeitersparnis.

Eine mögliche Lösung besteht darin, eine "Ragdoll-Schlange" zu haben, die in einer flachen Konfiguration beginnt und allmählich gebogen wird, um zu vermeiden, dass die gesamte Schlangengeometrie für jede mögliche Konfiguration neu berechnet wird.

Durch Auswahl der Reihenfolge, in der die Konfigurationen getestet werden, sodass höchstens eine Stoffpuppe für jede Gesamtzahl von Gelenken gespeichert wird, können wir die Anzahl der Instanzen auf N-1 begrenzen.

Ich benutze einen rekursiven Scan des Sake vom Schwanz abwärts und füge auf jeder Ebene ein einzelnes Gelenk hinzu. Daher wird eine neue Ragdoll-Instanz auf der übergeordneten Konfiguration mit einer einzigen zusätzlichen Biegung erstellt.

Dies bedeutet, dass Biegungen in einer sequentiellen Reihenfolge angewendet werden, was in fast allen Fällen ausreicht, um Selbstkollisionen zu vermeiden.

Wenn eine Selbstkollision erkannt wird, werden die Biegungen, die zu der beleidigenden Bewegung führen, in allen möglichen Reihenfolgen angewendet, bis eine legitime Faltung gefunden wird oder alle Kombinationen erschöpft sind.

Statische Prüfung

Bevor ich überhaupt über bewegliche Teile nachdachte, fand ich es effizienter, die statische Endform einer Schlange auf Selbstüberschneidungen zu testen.

Dies geschieht durch Zeichnen der Schlange auf einem Gitter. Jeder mögliche Punkt wird vom Kopf abwärts aufgezeichnet. Wenn es eine Selbstüberschneidung gibt, fallen mindestens zwei Punkte auf dieselbe Stelle. Dies erfordert genau N Diagramme für jede Schlangenkonfiguration für eine konstante O (N) -Zeit.

Der Hauptvorteil dieses Ansatzes besteht darin, dass der statische Test allein einfach gültige selbstvermeidende Pfade auf einem quadratischen Gitter auswählt, wodurch der gesamte Algorithmus getestet werden kann, indem die dynamische Kollisionserkennung verhindert und sichergestellt wird, dass die richtige Anzahl solcher Pfade gefunden wird.

Dynamische Prüfung

Wenn sich eine Schlange um ein Gelenk faltet, fegt jedes gedrehte Segment einen Bereich, dessen Form alles andere als trivial ist.
Natürlich können Sie Kollisionen überprüfen, indem Sie die Einbeziehung in alle diese überstrichenen Bereiche einzeln testen. Eine globale Überprüfung wäre effizienter, aber angesichts der Komplexität der Bereiche kann ich mir keine vorstellen (außer vielleicht die Verwendung einer GPU, um alle Bereiche zu zeichnen und eine globale Trefferprüfung durchzuführen).

Da der statische Test die Start- und Endpositionen jedes Segments berücksichtigt, müssen wir nur die Schnittpunkte mit dem überprüfen Bögendie von jedem rotierenden Segment überstrichen werden.

Nach einer interessanten Diskussion mit Trichoplax und ein bisschen JavaScript , um mich zu orientieren, kam ich auf diese Methode:

Um zu versuchen, es in ein paar Worten auszudrücken, wenn Sie anrufen

• C. das Rotationszentrum,
• S ein rotierendes Segment beliebiger Länge und Richtung, das nicht enthält C ,
• L die Linie verlängert sich S.
• H die zu L orthogonale Linie durch C. ,
• I der Schnittpunkt von L und H ,

_{(Quelle: free.fr )}

Für jedes Segment, das nicht enthält I , wird der überstrichene Bereich durch 2 Bögen begrenzt (und 2 Segmente, die bereits durch die statische Prüfung ).

Wenn ich in das Segment falle, muss auch der von I überstrichene Bogen berücksichtigt werden.

Dies bedeutet, dass wir jedes unbewegliche Segment gegen jedes rotierende Segment mit 2 oder 3 Segment-mit-Bogen-Schnittpunkten prüfen können

Ich habe die Vektorgeometrie verwendet, um trigonometrische Funktionen insgesamt zu vermeiden.
Vektoroperationen erzeugen kompakten und (relativ) lesbaren Code.

Der Schnittpunkt von Segment zu Bogen erfordert einen Gleitkomma-Vektor, die Logik sollte jedoch immun gegen Rundungsfehler sein.
Ich fand diese elegante und effiziente Lösung in einem obskuren Forumsbeitrag. Ich frage mich, warum es nicht weiter verbreitet ist.

Funktioniert es?

Das Sperren der dynamischen Kollisionserkennung führt zu einer korrekten Anzahl von Pfaden mit Selbstvermeidung bis zu n = 19, daher bin ich ziemlich sicher, dass das globale Layout funktioniert.

Die dynamische Kollisionserkennung führt zu konsistenten Ergebnissen, obwohl die Überprüfung von Biegungen in unterschiedlicher Reihenfolge (vorerst) fehlt.
Infolgedessen zählt das Programm Schlangen, die vom Kopf nach unten gebogen werden können (dh mit gefalteten Gelenken in der Reihenfolge des zunehmenden Abstands vom Kopf).