Hintergrund

Man betrachte eine (geschlossene) Kette von Stäben, von denen jede eine ganzzahlige Länge hat. Wie viele verschiedene lochfreie Polyominoe können Sie mit einer bestimmten Kette bilden? Oder mit anderen Worten, wie viele verschiedene sich nicht selbst schneidende Polygone mit achsenausgerichteten Seiten können Sie mit einer bestimmten Kette bilden?

Schauen wir uns ein Beispiel an. Betrachten Sie eine bestimmte Kette, die aus 8 Stäben der Länge 1 und 2 besteht, die wir als darstellen können [1, 1, 2, 2, 1, 1, 2, 2]. Bis auf Rotationen und Übersetzungen gibt es nur 8 mögliche Polyominoe (wir zählen verschiedene Reflexionen):

Dieser erste Stab ist dunkelblau, und dann durchlaufen wir das Polygon im Gegenuhrzeigersinn .

Die Drehrichtung beeinflusst das Ergebnis im obigen Beispiel nicht. Betrachten wir jedoch eine andere Kette [3, 1, 1, 1, 2, 1, 1], die die folgenden 3 Polyominoe ergibt:

Beachten Sie, dass wir nicht eine Reflexion des letzten polyomino sind, weil sie im Uhrzeigersinn Traversal erfordern würde.

Wenn wir eine flexiblere Kette mit der gleichen Länge [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]hätten, könnten wir tatsächlich beide Reflexionen unter einigen anderen Polyoninoen bilden, insgesamt 9:

Die Herausforderung

Wenn Sie eine Kette, ein Array oder ähnliches beschreiben, bestimmen Sie die Anzahl der verschiedenen Polyominoe, die Sie bilden können (bis zu Rotationen und Verschiebungen), indem Sie die Stäbe der Reihe nach verwenden, während Sie sich im Gegenuhrzeigersinn um den Umfang bewegen .

Bitte schreiben Sie ein vollständiges Programm und fügen Sie Befehle ein, um (falls zutreffend) Ihren Code zu kompilieren und über die Befehlszeile auszuführen. Bitte fügen Sie auch einen Link zu einem kostenlosen Übersetzer / Dolmetscher für Ihre Sprache bei.

Ihr Programm sollte die Eingabe von STDIN lesen. Die erste Zeile wird für eine ganze Zahl enthalten , M . Die nächsten M Zeilen sind Testfälle, von denen jede eine durch Leerzeichen getrennte Liste von Stablängen ist. Ihr Programm sollte M Zeilen an STDOUT ausgeben, von denen jede aus einer einzelnen Ganzzahl besteht - der Anzahl der verschiedenen Polyominoe, die gebildet werden können.

Sie dürfen nur einen Thread verwenden.

Ihr Programm darf zu keinem Zeitpunkt mehr als 1 GB Speicher belegen. (Dies ist keine völlig strenge Beschränkung, aber ich werde die Speichernutzung Ihrer ausführbaren Datei überwachen und jeden Prozess beenden, der durchweg mehr als 1 GB belegt oder deutlich darüber liegt.)

Um übermäßige Vorberechnungen zu vermeiden, darf Ihr Code nicht länger als 20.000 Byte sein und Sie dürfen keine Dateien lesen.

Sie dürfen auch nicht auf die ausgewählten Testfälle hin optimieren (z. B. durch Hardcodierung der Ergebnisse). Wenn ich das vermute, behalte ich mir das Recht vor, neue Benchmark-Sets zu generieren. Die Testsätze sind zufällig, daher sollte die Leistung Ihres Programms für die Leistung bei willkürlichen Eingaben repräsentativ sein. Die einzige Annahme, die Sie machen dürfen, ist, dass die Summe der Stablängen gerade ist.

Wertung

Ich habe Benchmark-Sets für Ketten mit N = 10, 11, ..., 20 Stangen bereitgestellt . Jeder Testsatz enthält 50 zufällige Ketten mit Längen zwischen 1 und einschließlich 4.

Ihre primäre Punktzahl ist die größte N, für die Ihr Programm den gesamten Testsatz innerhalb von 5 Minuten abschließt (auf meinem Computer unter Windows 8). Der Tie Breaker ist die tatsächliche Zeit, die Ihr Programm für diesen Testsatz benötigt.

Wenn jemand das größte Test-Set schlägt, werde ich immer größere hinzufügen.

Testfälle

Mit den folgenden Testfällen können Sie die Richtigkeit Ihrer Implementierung überprüfen.

Input                            Output

1 1                              0
1 1 1 1                          1
1 1 1 1 1 1                      1
1 1 1 1 1 1 1 1                  3
1 1 1 1 1 1 1 1 1 1              9
1 1 1 1 1 1 1 1 1 1 1 1          36
1 1 1 1 1 1 1 1 1 1 1 1 1 1      157
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  758
1 1 2 2 1 1 2 2                  8
1 1 2 2 1 1 2 2 1 1              23
1 1 2 2 1 1 2 2 1 1 2 2          69
1 2 1 2 1 2 1 2                  3
1 2 1 2 1 2 1 2 1 2 1 2          37
1 2 3 2 1 2 3 2                  5
1 2 3 2 1 2 3 2 1 2 3 2          23
3 1 1 1 2 1 1                    3
1 2 3 4 5 6 7                    1
1 2 3 4 5 6 7 8                  3
1 2 3 4 5 6 7 8 9 10 11          5
2 1 5 3 3 2 3 3                  4
4 1 6 5 6 3 1 4                  2
3 5 3 5 1 4 1 1 3                5
1 4 3 2 2 5 5 4 6                4
4 1 3 2 1 2 3 3 1 4              18
1 1 1 1 1 2 3 3 2 1              24
3 1 4 1 2 2 1 1 2 4 1 2          107
2 4 2 4 2 2 3 4 2 4 2 3          114

Eine Eingabedatei mit diesen finden Sie hier .

Bestenliste

   User          Language       Max N      Time taken (MM:SS:mmm)

1. feersum       C++ 11         19         3:07:430

2. Sp3000        Python 3       18         2:30:181

C ++ 11

Aktualisierungen: Es wurde die erste Zeile hinzugefügt, die cfrüh ausbricht, wenn der Abstand zu weit vom Ursprung entfernt ist (das war der ganze Zweck der Variablen rlen, aber ich habe vergessen, sie in der ersten Version zu schreiben). Ich habe es geändert, um viel weniger Speicher zu verwenden, aber auf Kosten der Zeit. Es löst jetzt N = 20 in knapp 5 Minuten für mich.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <ctime>

#define M std::map
#define MS 999
#define l (xM*2+1)

#define KITTENS(A,B)A##B
#define CATS(A,B)KITTENS(A,B)
#define LBL CATS(LBL,__LINE__)
#define unt unsigned
#define SU sizeof(unt)
#define SUB (SU*8)
#define newa (nb^SZ||fail("blob"),nb+++blob)

#define D

struct vec {int x, y;};


unt s[MS*2];
int xM, sl[MS];
vec X[MS];

struct a;
struct a  { M<unt,unt>v;};

#define SZ ((1<<29)/sizeof(a))
a*blob;
unt nb;


int fail(const char*msg)
{
    printf("failed:%s", msg);
    exit(1);
    return 1;
}

struct
{
    unt*m;
    bool operator()(int x, int y) { return m[(x+l*y)/SUB] >> (x+l*y)%SUB & 1; }
    void one(int x, int y) { m[(x+l*y)/SUB] |= 1U << (x+l*y)%SUB; }
    void zero(int x, int y) { m[(x+l*y)/SUB] &= ~(1U << (x+l*y)%SUB); }
} g;

unt c(a*A, vec x, unt rlen, unt sn) {
    if((unt)x.y+abs(x.x) > rlen) return 0;
    if(!rlen) {
        vec *cl=X, *cr=X, *ct=X;
        for(unt i=1; i<sn; i++) {
            #define BLAH(Z,A,B,o,O) \
                if(X[i].A o Z->A || (X[i].A == Z->A && X[i].B O Z->B)) \
                   Z = X+i

            BLAH(cl,x,y,<,>);
            BLAH(cr,x,y,>,<);
            BLAH(ct,y,x,>,>);
        }
        unt syms = 1;
        #define BLA(H,Z) {bool sy=1;for(unt o=0; o<sn; o++) sy &= (int)(1|-(H))*sl[o] == sl[(Z-X+o)%sn]; syms += sy;}
        BLA(~o&1,cl)
        BLA(1,ct)
        BLA(o&1,cr)

        #ifdef D
            //printf("D");for(int i=0;i<sn;i++)printf(" %u",sl[i]);printf("\n");
            if(syms==3) fail("symm");
        #endif

        return syms;
    }
    if(!(x.x|x.y|!sn)) return 0;
    X[sn] = x;

    unt k = 0;
    for(auto it: A->v) {
        int len = it.first;
        bool ve = sn&1;
        int dx = ve?0:len, dy = ve?len:0;

        #define PPCG(O)(x.x O (ve?0:z), x.y O (ve?z:0))
        #define MACR(O) { \
            vec v2 = {x.x O dx, x.y O dy}; \
            if(v2.y<0||(!v2.y&&v2.x<0)||abs(v2.x)>xM||v2.y>xM) \
                goto LBL; \
            for(int z=1; z<=len; z++) \
                if(g PPCG(O)) \
                    goto LBL; \
            for(int z=1; z<=len; z++) \
                g.one PPCG(O); \
            sl[sn] = O len; \
            k += c(blob+it.second, v2, rlen - len, sn+1); \
            for(int z=1; z<=len; z++) \
                g.zero PPCG(O); \
            } LBL: \

    MACR(+);
    MACR(-);
    }

    return k;
}

void stuff(a *n, unt j, unt r, unt len1)
{
    unt t=0;
    for(unt i=j; i<j+r; i++) {
        t += s[i];
        if((int)t > xM || (len1 && t>len1)) break;
        if(len1 && t < len1) continue;
        int r2 = r-(i-j)-1;
        if(r2) {
            unt x;
            if(n->v.count(t))
                x = n->v[t];
            else
                n->v[t] = x = newa - blob;
            stuff(blob+x, i+1, r2, 0);
        } else n->v[t] = -1;
    }
}

int main()
{
    time_t tim = time(0);
    blob = new a[SZ];
    int n;
    scanf("%u",&n);
    while(n--) {
        nb = 0;
        unt ns=0, tl=0;
        while(scanf("%u",s+ns)) {
            tl += s[ns];
            if(++ns==MS) return 1;
            if(getchar() < 11) break;
        }
        xM = ~-tl/2;
        g.m = (unt*)calloc((xM+1)*l/SU + 1,4);

        memcpy(s+ns, s, ns*SU);

        unt ans = 0;
        for(unt len1 = 1; (int)len1 <= xM; len1++) {
            a* a0 = newa;
            for(unt i=0; i<ns; i++)
                stuff(a0, i, ns, len1);
            ans += c(a0, {}, tl, 0);
            for(unt i=0; i<nb; i++)
                blob[i].v.clear();
        }
        printf("%d\n", ans/4);
        free(g.m);
    }

    tim = time(0) - tim;
    printf("time:%d",(int)tim);
    return 0;
}

Kompilieren mit

g++ --std=c++11 -O3 feersum.cpp -o feersum.exe

Python 3 (mit PyPy ) - N = 18

ANGLE_COMPLEMENTS = {"A": "C", "F": "F", "C": "A"}
MOVE_ENUMS = {"U": 0, "R": 1, "D": 2, "L": 3}
OPPOSITE_DIR = {"U": "D", "D": "U", "L": "R", "R": "L", "": ""}

def canonical(angle_str):
    return min(angle_str[i:] + angle_str[:i] for i in range(len(angle_str)))

def to_angles(moves):
    """
    Convert a string of UDLR to a string of angles where
      A -> anticlockwise turn
      C -> clockwise turn
      F -> forward
    """

    angles = []

    for i in range(1, len(moves)):
        if moves[i] == moves[i-1]:
            angles.append("F")
        elif (MOVE_ENUMS[moves[i]] - MOVE_ENUMS[moves[i-1]]) % 4 == 1:
            angles.append("C")
        else:
            angles.append("A")

    if moves[0] == moves[len(moves)-1]:
        angles.append("F")
    elif (MOVE_ENUMS[moves[0]] - MOVE_ENUMS[moves[len(moves)-1]]) % 4 == 1:
        angles.append("C")
    else:
        angles.append("A")

    return "".join(angles)

def solve(rods):
    FOUND_ANGLE_STRS = set()

    def _solve(rods, rod_sum, point=(0, 0), moves2=None, visited=None, last_dir=""):
        # Stop when point is too far from origin
        if abs(point[0]) + abs(point[1]) > rod_sum:
            return

        # No more rods, check if we have a valid solution
        if not rods:
            if point == (0, 0):
               angle_str = to_angles("".join(moves2))

               if angle_str.count("A") - angle_str.count("C") == 4:
                   FOUND_ANGLE_STRS.add(canonical(angle_str))

            return

        r = rods.pop(0)

        if not visited:
            visited = set()
            move_dirs = [((r, 0), "R")]
            moves2 = []

        else:
            move_dirs = [((r,0), "R"), ((0,r), "U"), ((-r,0), "L"), ((0,-r), "D")]

        opp_dir = OPPOSITE_DIR[last_dir]

        for move, direction in move_dirs:
            if direction == opp_dir: continue

            new_point = (move[0] + point[0], move[1] + point[1])
            added_visited = set()
            search = True

            for i in range(min(point[0],new_point[0]), max(point[0],new_point[0])+1):
                for j in range(min(point[1],new_point[1]), max(point[1],new_point[1])+1):
                    if (i, j) != point:
                        if (i, j) in visited:
                            search = False

                            for a in added_visited:
                                visited.remove(a)

                            added_visited = set()                            
                            break

                        else:
                            visited.add((i, j))
                            added_visited.add((i, j))

                if not search:
                    break

            if search:
                moves2.append(direction*r)
                _solve(rods, rod_sum-r, new_point, moves2, visited, direction)
                moves2.pop()

            for a in added_visited:
                visited.remove(a)

        rods.insert(0, r)
        return

    _solve(rods, sum(rods))
    return len(FOUND_ANGLE_STRS)

num_rods = int(input())

for i in range(num_rods):
    rods = [int(x) for x in input().split(" ")]
    print(solve(rods))

Laufen Sie mit ./pypy <filename>.

Dies ist die Referenzimplementierung, die ich geschrieben habe, als ich die Frage mit Martin besprochen habe. Es wurde nicht mit dem Gedanken an Geschwindigkeit gemacht und ist ziemlich kitschig, aber es sollte eine gute Basis sein, um die Dinge anzufangen.

N = 18 dauert auf meinem bescheidenen Laptop ungefähr 2,5 Minuten.

Algorithmus

Die Drehungen werden überprüft, indem jede Form in eine Reihe von FVorwärts-, ALinks- und CRechtsdrehungen an jedem Gitterpunkt an der Grenze der Form umgewandelt wird - ich nenne dies eine Winkelzeichenfolge . Zwei Formen sind rotatorisch identisch, wenn ihre Winkelketten zyklische Permutationen sind. Anstatt dies immer durch direkten Vergleich zweier Winkelzeichenfolgen zu überprüfen, konvertieren wir eine neue Form vor dem Speichern in eine kanonische Form. Wenn wir einen neuen Kandidaten haben, konvertieren wir in die kanonische Form und prüfen, ob wir diese bereits haben (und nutzen so das Hashing, anstatt den gesamten Satz zu durchlaufen).

Die Winkelzeichenfolge wird auch verwendet, um zu überprüfen, ob die Form gegen den Uhrzeigersinn geformt wurde, indem sichergestellt wird, dass die Anzahl As die Anzahl Cs um 4 überschreitet .

Die Selbstüberschneidung wird naiv überprüft, indem jeder Gitterpunkt an der Grenze der Form gespeichert und überprüft wird, ob ein Punkt zweimal besucht wird.

Der Kernalgorithmus ist einfach: Platzieren Sie die erste Stange nach rechts und probieren Sie dann alle Möglichkeiten für die verbleibenden Stangen aus. Wenn die Stäbe einen Punkt erreichen, der zu weit vom Ursprung entfernt ist (dh die Summe der verbleibenden Stablängen ist kleiner als der Manhattan-Abstand des Punkts vom Ursprung), hören wir vorzeitig auf, diesen Teilbaum zu suchen.

Updates (neueste zuerst)

• 6/12: Einführung der kanonischen Form, einige Mikrooptimierungen hinzugefügt
• 5/12: Fehler in der Algorithmuserklärung behoben. Den quadratischen Algorithmus zur Prüfung der zyklischen Permutation mit den zyklischen A- und B-Permutationen linear gemacht, wenn A eine Teilzeichenfolge der B + B-Methode ist (ich habe keine Ahnung, warum ich das nicht früher getan habe).