tło

Rozważ (zamknięty) łańcuch prętów, z których każdy ma całkowitą długość. Ile odrębnych polominoów bez dziur można utworzyć za pomocą danego łańcucha? Innymi słowy, ile różnych nie przecinających się wielokątów z bokami wyrównanymi do osi można utworzyć za pomocą danego łańcucha?

Spójrzmy na przykład. Rozważmy szczególny łańcuch składający się z 8 prętów o długości 1 i 2, które możemy przedstawić jako [1, 1, 2, 2, 1, 1, 2, 2]. Do rotacji i tłumaczeń istnieje tylko 8 możliwych poliominoesów (liczymy różne odbicia):

Ten pierwszy pręt jest granatowy, a następnie przemierzamy wielokąt w kierunku przeciwnym do ruchu wskazówek zegara .

Kierunek obrotu nie wpływa na wynik w powyższym przykładzie. [3, 1, 1, 1, 2, 1, 1]Zastanówmy się jednak nad innym łańcuchem , który daje następujące 3 poliominoes:

Zauważ, że nie uwzględniamy odbicia ostatniego poliomino, ponieważ wymagałoby to przejścia w prawo.

Gdybyśmy mieli bardziej elastyczny łańcuch o tej samej długości, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]faktycznie bylibyśmy w stanie utworzyć oba odbicia wśród niektórych innych poloninoów, w sumie 9:

Wyzwanie

Biorąc pod uwagę opis łańcucha, jako szyku lub podobnego elementu, określ liczbę różnych poliominoesów, które możesz utworzyć (do rotacji i translacji) za pomocą prętów w porządku , poruszając się po obwodzie w kierunku przeciwnym do ruchu wskazówek zegara.

Napisz pełny program i dołącz polecenia do kompilacji (jeśli dotyczy) i uruchom kod z wiersza poleceń. Dołącz także link do bezpłatnego kompilatora / tłumacza dla twojego języka.

Twój program powinien odczytać dane wejściowe ze STDIN. Pierwsza linia zawiera całkowitą M . Kolejne M linii to przypadki testowe, z których każda będzie oddzieloną spacją listą długości prętów. Twój program powinien wypisać M linii do STDOUT, z których każda składa się z jednej liczby całkowitej - liczby różnych poliominoes, które można utworzyć.

Musisz użyć tylko jednego wątku.

Twój program nie może zużywać więcej niż 1 GB pamięci w dowolnym momencie. (Nie jest to całkowicie ścisły limit, ale będę monitorować wykorzystanie pamięci pliku wykonywalnego i zabijać każdy proces, który konsekwentnie zużywa więcej niż 1 GB lub skoki znacznie powyżej niego).

Aby zapobiec nadmiernej ilości obliczeń wstępnych, Twój kod nie może być dłuższy niż 20 000 bajtów i nie wolno odczytywać żadnych plików.

Nie wolno również optymalizować pod kątem wybranych wybranych przypadków testowych (np. Przez zakodowanie wyników ich). Jeśli podejrzewam, że tak, zastrzegam sobie prawo do generowania nowych zestawów testów porównawczych. Zestawy testowe są losowe, więc wydajność Twojego programu na nich powinna być reprezentatywna pod względem działania na dowolnych danych wejściowych. Jedynym założeniem, jakie możesz przyjąć, jest to, że suma długości wędek jest parzysta.

Punktacja

Dostarczyłem zestawy wzorcowe dla łańcuchów N = 10, 11, ..., 20 prętów. Każdy zestaw testowy zawiera 50 losowych łańcuchów o długości od 1 do 4 włącznie.

Twój wynik główny to największy N, dla którego Twój program ukończy cały zestaw testów w ciągu 5 minut (na moim komputerze, pod Windows 8). Przerywaczem remisów będzie rzeczywisty czas zajęty przez program na tym zestawie testowym.

Jeśli ktoś pobije największy zestaw testowy, będę dodawał większe.

Przypadki testowe

Możesz użyć następujących przypadków testowych, aby sprawdzić poprawność swojej implementacji.

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

Znaleźć plik wejściowy z tymi tutaj .

Tabela liderów

   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

Aktualizacje: Dodano pierwszą linię, cktóra wybucha wcześnie, jeśli odległość jest zbyt daleko od początku (co było celem zmiennej rlen, ale zapomniałem napisać ją w pierwszej wersji). Zmieniłem to, aby zużywać znacznie mniej pamięci, ale kosztem czasu. Teraz rozwiązuje dla mnie N = 20 w niecałe 5 minut.

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

Połącz z

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

Python 3 (z 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))

Uruchom z ./pypy <filename>.

To jest implementacja referencyjna, którą napisałem, omawiając pytanie z Martinem. Nie został stworzony z myślą o szybkości i jest dość zuchwały, ale powinien zapewnić dobrą podstawę do rozpoczęcia.

N = 18 zajmuje około 2,5 minuty na moim skromnym laptopie.

Algorytm

Obroty są sprawdzane przez przekształcenie każdego kształtu w serię Fdo przodu, Ado obrotu przeciwnie do ruchu wskazówek zegara i Cdo obrotu zgodnie z ruchem wskazówek zegara w każdym punkcie sieci na granicy kształtu - nazywam to ciągiem kątowym . Dwa kształty są obrotowo identyczne, jeśli ich ciągi kątowe są cyklicznymi permutacjami. Zamiast zawsze sprawdzać to, porównując bezpośrednio dwa ciągi kątowe, gdy znajdziemy nowy kształt, przed zapisaniem przekształcamy go w postać kanoniczną. Kiedy mamy nowego kandydata, przechodzimy do formy kanonicznej i sprawdzamy, czy już ją mamy (wykorzystując w ten sposób haszowanie, zamiast iteracji przez cały zestaw).

Łańcuch kątowy służy również do sprawdzenia, czy kształt jest uformowany przeciwnie do ruchu wskazówek zegara, upewniając się, że liczba As przekracza liczbę Cs o 4.

Samo przecięcie jest naiwnie sprawdzane poprzez przechowywanie każdego punktu sieci na granicy kształtu i sprawdzanie, czy punkt jest odwiedzany dwukrotnie.

Algorytm rdzenia jest prosty, umieszczając pierwszy pręt po prawej stronie, a następnie wypróbowując wszystkie możliwości dla pozostałych prętów. Jeśli pręty dojdą do punktu, który jest zbyt daleko od początku (tj. Suma pozostałych długości prętów jest mniejsza niż odległość punktu Manhattan od punktu początkowego), wówczas przedwcześnie przestajemy szukać tego poddrzewa.

Aktualizacje (najnowsze pierwsze)

• 6/12: Wprowadzono kanoniczną formę, dodano kilka mikrooptymalizacji
• 5/12: Naprawiono błąd w wyjaśnieniu algorytmu. Uczyniono liniowy algorytm kwadratowego sprawdzania permutacji cyklicznej za pomocą permutacji cyklicznych A, B iff Podciąg metody B + B (nie mam pojęcia, dlaczego wcześniej tego nie zrobiłem).