Tantangan ini bukan tentang game Snake.

Bayangkan ular 2d terbentuk dengan menggambar garis horizontal panjang n. Pada titik-titik integer di sepanjang tubuhnya, ular ini dapat memutar tubuhnya hingga 90 derajat. Jika kita menentukan bagian depan ular berada di paling kiri untuk memulai, rotasi akan memindahkan bagian belakang ular dan bagian depan akan tetap diletakkan. Dengan melakukan rotasi berulang dapat membuat banyak bentuk tubuh ular yang berbeda.

Aturan

1. Salah satu bagian tubuh ular tidak bisa tumpang tindih.
2. Harus dimungkinkan untuk mencapai orientasi akhir tanpa ada bagian tubuh ular yang saling tumpang tindih di antaranya. Dua titik yang disentuh dihitung sebagai tumpang tindih dalam masalah ini.
3. Saya menganggap ular dan kebalikannya adalah bentuk yang sama.

Tugas

Hingga rotasi, terjemahan dan simetri cermin, berapakah jumlah total bentuk tubuh ular yang berbeda yang dapat dibuat?

Contoh rotasi bagian tubuh ular. Bayangkan n=10dan ular itu berada dalam orientasi awal berupa garis lurus. Sekarang putar di titik 490 derajat berlawanan arah jarum jam. Kita mendapatkan ular dari 4ke 10(ekor ular) berbaring secara vertikal dan ular dari 0ke 4berbaring secara horizontal. Ular itu sekarang memiliki satu sudut kanan di tubuhnya.

Berikut adalah beberapa contoh terima kasih kepada Martin Büttner.

Kami mulai dengan ular horizontal.

Sekarang kita putar dari posisi 4.

Kami berakhir setelah rotasi dalam orientasi ini.

Sekarang mari kita perhatikan orientasi ular yang berbeda ini.

Kita sekarang dapat melihat langkah ilegal di mana akan terjadi tumpang tindih selama rotasi.

Skor

Skor Anda adalah yang terbesar di nmana kode Anda dapat menyelesaikan masalah dalam waktu kurang dari satu menit di komputer saya.

Ketika rotasi terjadi, ia akan memindahkan setengah dari ular bersamanya. Kita harus khawatir tentang apakah bagian yang diputar ini mungkin tumpang tindih dengan bagian ular selama rotasi. Untuk kesederhanaan kita dapat mengasumsikan ular memiliki lebar nol. Anda hanya dapat memutar pada titik tertentu dalam ular hingga 90 derajat searah jarum jam berlawanan arah jarum jam. Sebab, Anda tidak pernah dapat melipat penuh ular menjadi dua karena itu akan melibatkan dua rotasi pada titik yang sama dalam arah yang sama.

Bentuk yang tidak bisa dibuat

Contoh sederhana dari bentuk yang tidak dapat dibuat adalah modal T. Versi yang lebih canggih

(Terima kasih kepada Harald Hanche-Olsen untuk contoh ini)

Dalam contoh ini semua garis horizontal yang berdekatan adalah 1 terpisah seperti halnya yang vertikal. Karena itu tidak ada langkah hukum dari posisi ini dan karena masalahnya dapat dibalik maka tidak ada cara untuk sampai ke sana dari posisi awal.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga tersedia secara bebas untuk Linux.

Mesin saya Pengaturan waktu akan dijalankan di mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda. Sebagai konsekuensinya, hanya gunakan perangkat lunak gratis yang mudah tersedia dan harap sertakan instruksi lengkap cara menyusun dan menjalankan kode Anda.

Python 3 - skor sementara: n = 11 (n = 13 dengan PyPy *)

Karena tidak ada jawaban di minggu pertama, berikut adalah contoh dalam Python untuk mendorong persaingan. Saya sudah mencoba membuatnya mudah dibaca sehingga ketidakefisienan dapat diidentifikasi dengan mudah untuk memberikan ide untuk jawaban lain.

Pendekatan

• Mulailah dengan ular lurus dan temukan semua posisi yang dapat dicapai secara legal dalam satu gerakan.
• Temukan semua posisi yang dapat dicapai secara hukum dari posisi tersebut, yang belum diidentifikasi.
• Ulangi sampai tidak ada lagi yang bisa ditemukan, dan kembalikan jumlah posisi yang ditemukan sama sekali.

Kode

(sekarang dengan beberapa dokumen dan konfirmasi setelah upaya pertama saya yang salah)

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

Hasil

Di komputer saya, ular terpanjang yang dapat dihitung dalam waktu kurang dari 1 menit adalah panjang 11 (atau panjang 13 dengan PyPy *). Ini jelas hanya skor sementara sampai kami mengetahui berapa skor resmi dari mesin Lembik.

Sebagai perbandingan, berikut adalah hasil untuk beberapa nilai pertama dari 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)

Tolong beri tahu saya jika ada yang salah.

Jika Anda memiliki contoh pengaturan yang seharusnya tidak dapat dibuka, Anda dapat menggunakan fungsi ini neighbours(snake)untuk menemukan pengaturan yang dapat dijangkau dalam satu langkah, sebagai tes kode. snakeadalah tuple dari arah sambungan (0 untuk searah jarum jam, 1 untuk lurus, 2 untuk berlawanan arah jarum jam). Misalnya (1,1,1) adalah ular lurus dengan panjang 4 (dengan 3 sendi).

Visualisasi

Untuk memvisualisasikan ular yang ada dalam pikiran Anda, atau ular yang kembali neighbours, Anda dapat menggunakan fungsinya display(snake). Ini menerima tuple seperti fungsi lainnya, tetapi karena tidak digunakan oleh program utama dan karena itu tidak perlu cepat, itu juga akan menerima string, untuk kenyamanan Anda.

display((1,1,2,0)) setara dengan display("1120")

Seperti yang disebutkan Lembik dalam komentar, hasil saya identik dengan OEIS A037245 yang tidak memperhitungkan persimpangan selama rotasi. Ini karena untuk beberapa nilai pertama n tidak ada perbedaan - semua bentuk yang tidak berpotongan dapat dicapai dengan melipat ular lurus. Kebenaran kode dapat diuji dengan memanggil neighbours()dengan ular yang tidak dapat dibuka tanpa persimpangan. Karena tidak memiliki tetangga, ia hanya akan berkontribusi pada urutan OEIS, dan tidak untuk yang ini. Contoh terkecil yang saya ketahui adalah ular panjang 31 yang disebutkan Lembik, terima kasih kepada 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') memberikan hasil sebagai berikut:

Tip: Jika Anda mengubah ukuran jendela tampilan dan kemudian memanggil tampilan lagi, ular akan dipasang ke ukuran jendela baru.

Saya ingin mendengar dari siapa pun yang memiliki contoh lebih pendek tanpa tetangga. Saya menduga bahwa contoh yang paling pendek akan menandai n terkecil yang berbeda urutannya.

* Perhatikan bahwa setiap kenaikan n memakan waktu kira-kira 3 kali lebih lama, jadi meningkat dari n = 11 ke n = 13 membutuhkan hampir 10 kali lipat waktu. Inilah sebabnya mengapa PyPy hanya memungkinkan peningkatan n oleh 2, meskipun itu berjalan jauh lebih cepat daripada penerjemah Python standar.

C ++ 11 - hampir bekerja :)

Setelah membaca artikel ini , saya mengumpulkan sedikit hikmah dari pria yang tampaknya bekerja selama 25 tahun pada masalah yang tidak terlalu rumit dalam menghitung jalur penghindaran diri pada kisi persegi.

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

Membangun executable

Kompilasi dengan saya menggunakan MinGW di bawah Win7 dengan g ++ 4.8 untuk build "linux", jadi portabilitas tidak dijamin 100%.g++ -O3 -std=c++11

Ini juga berfungsi (semacam) dengan proyek MSVC2013 standar

Dengan membatalkan definisi NDEBUG, Anda mendapatkan jejak eksekusi algoritma dan ringkasan konfigurasi yang ditemukan.

Pertunjukan

dengan atau tanpa tabel hash, kompiler Microsoft berkinerja buruk: g ++ build 3 kali lebih cepat .

Algoritma ini praktis tidak menggunakan memori.

Karena pemeriksaan tabrakan kira-kira dalam O (n), waktu perhitungan harus dalam O (nk ⁿ ), dengan k sedikit lebih rendah dari 3.
Pada [email protected] saya, n = 17 membutuhkan waktu sekitar 1:30 (sekitar 2 juta ular / menit).

Saya belum selesai mengoptimalkan, tetapi saya tidak akan mengharapkan lebih dari keuntungan x3, jadi pada dasarnya saya bisa berharap untuk mencapai mungkin n = 20 di bawah satu jam, atau n = 24 di bawah sehari.

Mencapai bentuk tak terbendung pertama yang diketahui (n = 31) akan membutuhkan waktu antara beberapa tahun dan satu dekade, dengan asumsi tidak ada pemadaman listrik.

Menghitung bentuk

Sebuah N ukuran ular memiliki N-1 sendi.
Setiap sambungan dapat dibiarkan lurus atau ditekuk ke kiri atau ke kanan (3 kemungkinan).
Jumlah lipatan yang mungkin adalah 3 ^N-1 .
Tabrakan akan mengurangi jumlah itu, sehingga jumlah aktual mendekati 2,7 ^N-1

Namun, banyak lipatan seperti itu mengarah pada bentuk yang identik.

dua bentuk identik jika ada rotasi atau simetri yang dapat mengubah satu menjadi yang lain.

Mari kita mendefinisikan segmen sebagai bagian lurus dari tubuh terlipat.
Misalnya ular ukuran 5 yang dilipat pada sambungan kedua akan memiliki 2 segmen (satu panjang 2 unit dan panjang 3 unit kedua).
Segmen pertama akan dinamai kepala , dan ekor terakhir .

Dengan konvensi kami mengarahkan kepala ular secara horizontal dengan tubuh menunjuk ke kanan (seperti pada gambar OP pertama).

Kami menunjuk gambar tertentu dengan daftar panjang segmen yang ditandatangani, dengan panjang positif menunjukkan lipatan kanan dan negatif lipatan kiri.
Panjang awal positif dengan konvensi.

Memisahkan segmen dan tikungan

Jika kita hanya mempertimbangkan cara yang berbeda, ular dengan panjang N dapat dipecah menjadi segmen-segmen, kita berakhir dengan partisi ulang yang identik dengan komposisi N.

Dengan menggunakan algoritma yang sama seperti yang ditunjukkan pada halaman wiki, mudah untuk menghasilkan semua partisi 2 ^{N-1 yang} mungkin .

Setiap partisi pada gilirannya akan menghasilkan semua kemungkinan lipatan dengan menerapkan tikungan kiri atau kanan ke semua sambungannya. Satu lipatan seperti itu akan disebut konfigurasi .

Semua partisi yang mungkin dapat diwakili oleh integer dari bit N-1, di mana masing-masing bit mewakili keberadaan sambungan. Kami akan menyebut integer ini generator .

Memangkas partisi

Dengan memperhatikan bahwa menekuk partisi tertentu dari kepala ke bawah sama dengan menekuk partisi simetris dari ekor ke atas, kita dapat menemukan semua pasangan partisi simetris dan menghilangkan satu dari dua.
Generator partisi simetris adalah generator partisi yang ditulis dalam urutan bit terbalik, yang mudah dan murah untuk dideteksi.

Ini akan menghilangkan hampir setengah dari partisi yang mungkin, pengecualian menjadi partisi dengan generator "palindromic" yang dibiarkan tidak berubah oleh pembalikan bit (misalnya 00100100).

Merawat simetri horisontal

Dengan konvensi kami (ular mulai menunjuk ke kanan), tikungan pertama yang diterapkan ke kanan akan menghasilkan keluarga lipatan yang akan menjadi simetrik horizontal dari yang berlainan hanya dengan tikungan pertama.

Jika kita memutuskan bahwa tikungan pertama akan selalu ke kanan, kita menghilangkan semua simetrik horisontal dalam satu gerakan besar.

Mengepel palindrom

Kedua luka ini efisien, tetapi tidak cukup untuk merawat palindrom sial ini.
Pemeriksaan paling menyeluruh dalam kasus umum adalah sebagai berikut:

pertimbangkan konfigurasi C dengan partisi palindromic.

• jika kita membalikkan setiap tikungan dalam C, kita berakhir dengan simetri horizontal C.
• jika kita membalikkan C (menerapkan lengkungan dari ekor ke atas), kita mendapatkan angka yang sama diputar dengan benar
• jika kita berdua membalikkan dan membalikkan C, kita mendapatkan angka yang sama diputar ke kiri.

Kami dapat memeriksa setiap konfigurasi baru terhadap 3 lainnya. Namun, karena kami telah menghasilkan hanya konfigurasi yang dimulai dengan belokan kanan, kami hanya memiliki satu kemungkinan simetri untuk diperiksa:

• C terbalik akan mulai dengan belokan kiri, yang oleh konstruksi tidak mungkin untuk digandakan
• dari konfigurasi terbalik dan terbalik-terbalik, hanya satu yang akan mulai dengan belokan kanan.
  Itu adalah satu-satunya konfigurasi yang dapat kami duplikat.

Menghilangkan duplikat tanpa penyimpanan apa pun

Pendekatan awal saya adalah untuk menyimpan semua konfigurasi dalam tabel hash besar, untuk menghilangkan duplikat dengan memeriksa keberadaan konfigurasi simetrik yang sebelumnya dihitung.

Berkat artikel tersebut, menjadi jelas bahwa, karena partisi dan lipatan disimpan sebagai bitfields, mereka dapat dibandingkan seperti nilai numerik apa pun.
Jadi untuk menghilangkan satu anggota dari pasangan simetrik, Anda dapat membandingkan kedua elemen dan secara sistematis menyimpan yang terkecil (atau yang terbesar, sesuka Anda).

Dengan demikian, pengujian konfigurasi untuk jumlah duplikasi untuk menghitung partisi simetri, dan jika keduanya identik, lipat. Tidak perlu memori sama sekali.

Urutan generasi

Jelas pemeriksaan tabrakan akan menjadi bagian yang paling memakan waktu, sehingga mengurangi perhitungan ini adalah penghemat waktu utama.

Solusi yang mungkin adalah memiliki "ragdoll snake" yang akan dimulai dalam konfigurasi datar dan secara bertahap ditekuk, untuk menghindari penghitungan ulang seluruh geometri ular untuk setiap konfigurasi yang mungkin.

Dengan memilih urutan di mana konfigurasi diuji, sehingga paling banyak ragdoll disimpan untuk setiap jumlah sambungan, kita dapat membatasi jumlah instance hingga N-1.

Saya menggunakan pemindaian berulang dari sake dari ekor ke bawah, menambahkan satu sendi di setiap level. Jadi instance ragdoll baru dibangun di atas konfigurasi induk, dengan satu tikungan tambahan.

Ini berarti lengkungan diterapkan secara berurutan, yang tampaknya cukup untuk menghindari tabrakan diri di hampir semua kasus.

Ketika self-collision terdeteksi, tikungan yang mengarah ke langkah menyinggung diterapkan dalam semua pesanan yang mungkin sampai lipatan yang sah ditemukan atau semua kombinasi habis.

Pemeriksaan statis

Bahkan sebelum berpikir tentang memindahkan bagian, saya merasa lebih efisien untuk menguji bentuk akhir statis ular untuk persimpangan diri.

Ini dilakukan dengan menggambar ular di atas kisi-kisi. Setiap titik yang mungkin diplot dari kepala ke bawah. Jika ada persimpangan sendiri, setidaknya sepasang titik akan jatuh di lokasi yang sama. Ini membutuhkan tepat N plot untuk konfigurasi ular apa pun, untuk waktu O (N) yang konstan.

Keuntungan utama dari pendekatan ini adalah bahwa tes statis saja akan memilih jalur penghindaran diri yang valid pada kisi persegi, yang memungkinkan untuk menguji seluruh algoritma dengan menghambat deteksi tabrakan dinamis dan memastikan kami menemukan jumlah jalur yang benar.

Pemeriksaan dinamis

Ketika seekor ular terlipat di sekitar satu sendi, setiap segmen yang diputar akan menyapu area yang bentuknya tidak berarti apa-apa.
Jelas Anda dapat memeriksa tabrakan dengan menguji inklusi di semua area yang tersapu secara individual. Pemeriksaan global akan lebih efisien, tetapi mengingat kompleksitas area yang tidak dapat saya pikirkan (kecuali mungkin menggunakan GPU untuk menggambar semua area dan melakukan pemeriksaan global).

Karena tes statis menangani posisi awal dan akhir dari masing-masing segmen, kita hanya perlu memeriksa persimpangan dengan busur yang disapu oleh setiap segmen yang berputar.

Setelah diskusi yang menarik dengan trichoplax dan sedikit JavaScript untuk memahami, saya menemukan metode ini:

Untuk mencoba memasukkannya ke dalam beberapa kata, jika Anda menelepon

• C pusat rotasi,
• S segmen yang berputar dengan panjang sembarang dan arah yang tidak mengandung C ,
• L garis memanjang S
• H garis ortogonal ke L yang melewati C ,
• Saya persimpangan L dan H ,

_{(sumber: free.fr )}

Untuk setiap segmen yang tidak mengandung I , area sapuan diikat oleh 2 busur (dan 2 segmen sudah diurus dengan pemeriksaan statis).

Jika saya termasuk dalam segmen itu, busur yang disapu oleh saya juga harus diperhitungkan.

Ini berarti kita dapat memeriksa setiap segmen yang tidak bergerak terhadap setiap segmen yang berputar dengan 2 atau 3 segmen dengan persimpangan busur

Saya menggunakan geometri vektor untuk menghindari fungsi trigonometri sama sekali.
Pengoperasian vektor menghasilkan kode yang ringkas dan (relatif) dapat dibaca.

Persimpangan Segmen-ke-busur membutuhkan vektor titik mengambang, tetapi logika harus kebal terhadap kesalahan pembulatan.
Saya menemukan solusi elegan dan efisien ini dalam posting forum yang tidak jelas. Saya bertanya-tanya mengapa itu tidak dipublikasikan secara luas.

Apakah itu bekerja?

Menghambat deteksi tabrakan dinamis menghasilkan jalur penghindaran diri yang benar hingga n = 19, jadi saya cukup yakin tata letak global berfungsi.

Deteksi tabrakan dinamis menghasilkan hasil yang konsisten, meskipun pemeriksaan tikungan dalam urutan berbeda tidak ada (untuk saat ini).
Sebagai konsekuensinya, program menghitung ular yang dapat ditekuk dari kepala ke bawah (yaitu dengan sambungan dilipat agar jarak yang semakin jauh dari kepala).