Istnieje wiele różnych rodzajów zestawów pociągów, od drewnianych torów, takich jak Brio, po w pełni cyfrowe sterowanie doskonałymi malutkimi metalowymi replikami prawdziwych pociągów, ale wszystkie one wymagają zaprojektowania torów, idealnie wykorzystując jak najwięcej twoich elementów.

Zatem Twoim zadaniem jest ustalenie, czy przy danym wejściu dostępnych elementów możliwe jest zbudowanie pełnego obwodu zamkniętego przy użyciu wszystkich elementów, a jeśli nie, ile elementów pozostanie z maksymalnego możliwego obwodu.

Ponieważ jest to uproszczony zestaw pociągów, istnieją tylko 3 elementy: duża krzywa, mała krzywa i prosta. Wszystkie są oparte na kwadratowej siatce:

• „Big Curve” to narożnik 90 stopni, obejmujący 2 jednostki w każdym wymiarze
• „Mała krzywa” to narożnik 90 stopni, obejmujący jedną jednostkę w każdym kierunku
• „Prosto” to prosty element o długości 1 jednostki

Oznacza to, że minimalny możliwy obwód składa się z 4 małych krzywych - jest to okrąg o promieniu 1 jednostki. Można to rozszerzyć, dodając pary prostych elementów w celu utworzenia różnych owali. Możliwe są inne obwody, dodając więcej krzywych lub mieszając rodzaje krzywych.

Ten zestaw pociągów nie zawiera żadnych skrzyżowań ani metod krzyżowania torów, więc dwa elementy nie mogą łączyć się z tym samym końcem innego elementu (bez formacji Y) lub przecinać się nawzajem (bez formacji X) . Dodatkowo jest to zestaw pociągów, więc każda formacja, która nie pozwala na przejazd pociągu, nie jest ważna: przykłady obejmują proste spotykające się pod kątem 90 stopni (zawsze musi istnieć krzywa między prostopadłymi prostymi) i krzywe spotykające się pod kątem 90 stopni (krzywe muszą płynąć).

Chcesz również użyć jak największej liczby elementów, ignorując ich typ, więc zawsze wybierzesz obwód, który ma więcej bitów. Wreszcie masz tylko jeden ciąg, więc każde rozwiązanie, które powoduje wiele obwodów, jest niedopuszczalne .

Wkład

Albo tablica trzech liczb całkowitych, wszystkie większe lub równe 0, odpowiadające liczbie dostępnych dużych krzywych, małych krzywych i prostych lub parametrom przekazanym do programu, w tej samej kolejności.

Wydajność

Liczba odpowiadająca liczbie elementów pozostałych po zbudowaniu maksymalnego możliwego obwodu dla przewidzianych elementów.

Dane testowe

Minimal circuit using big curves
Input: [4,0,0]
Output: 0

Slightly more complicated circuit
Input: [3,1,2]
Output: 0

Incomplete circuit - can't join
Input: [3,0,0]
Output: 3

Incomplete circuit - can't join
Input: [3,1,1]
Output: 5

Circuit where big curves share a centre
Input: [2,2,0]
Output: 0

Bigger circuit
Input: [2,6,4]
Output: 0

Circuit where both concave and convex curves required
Input: [8,0,0] or [0,8,0]
Output: 0

Circuit with left over bit
Input: [5,0,0] or [0,5,0]
Output: 1

Uwagi

• 2 proste i mała krzywa są równoważne dużej krzywej, ale używaj większej liczby elementów, więc są preferowane - nigdy nie powinno być sytuacji, w której ta kombinacja jest pozostawiona, jeśli w obwodzie są jakieś duże krzywe
• 4 małe krzywe można zwykle zamienić na 4 proste, ale nie, jeśli spowodowałoby to przecięcie się obwodu
• Zestaw pociągu jest również idealizowany - elementy torów przyjmują pokazane szerokości, więc w niektórych przypadkach krzywe mogą przechodzić przez pojedynczy kwadrat siatki bez przecinania się. Siatka po prostu określa wymiary elementu. W szczególności można umieścić dwie duże krzywe, tak aby kwadrat siatki w lewym górnym rogu przykładowego diagramu byłby również prawym dolnym kwadratem innej dużej krzywej biegnącej od lewej do góry (z diagramem pokazującym jedną biegnącą od prawej do dołu)
• Mała krzywa może zmieścić się w pustej przestrzeni pod dużą krzywą (prawy dolny kwadrat siatki powyżej). Druga duża krzywa mogłaby również wykorzystać tę przestrzeń, przesunięta o jedną i drugą w dół od pierwszej
• Mała krzywa nie może zmieścić się na tej samej przestrzeni siatki, co zewnętrzna duża krzywa - głównie dlatego, że nie ma sposobu na połączenie się z nią, która nie przecina się nielegalnie

[JavaScript (Node.js)], 1220 bajtów

f=r=>{var a=[{n:0,d:[[0,-1,"0000000101011"],[1,-1,"0011111111111"],[0,0,"0111101111111"],[1,0,"1100010000000"]],e:[2,-1,1]},{n:0,d:[[-1,-1,"1001111111111"],[0,-1,"0000010010110"],[-1,0,"0110000100000"],[0,0,"1101111011111"]],e:[-2,-1,3]},{n:1,d:[[0,0,"0011101111111"]],e:[1,0,1]},{n:1,d:[[0,0,"1001111011111"]],e:[-1,0,3]},{n:2,d:[[0,0,"1111101011111"]],e:[0,-1,0]}],e=r=>{var a=r.d,e=r.e,n=[];return a.forEach(r=>{var a=r[2];n.push([-r[1],r[0],""+a[10]+a[5]+a[0]+a[8]+a[3]+a[11]+a[6]+a[1]+a[9]+a[4]+a[12]+a[7]+a[2]])}),{d:n,e:[-e[1],e[0],e[2]]}};i=((r,a)=>{for(var n=0;n<r.d;n++,a=e(a));var p=!1;return a.d.forEach(a=>{var e=r[`${r.p.x+a[0]},${r.p.y+a[1]}`];void 0===e&&(e="00000000000000");for(var n="",d=0;d<13;d++)"1"===e[d]&&"1"===a[2][d]&&(p=!0),n+=e[d]===a[2][d]?e[d]:"1";r[`${r.p.x+a[0]},${r.p.y+a[1]}`]=n}),r.p.x+=a.e[0],r.p.y+=a.e[1],r.d=(r.d+a.e[2])%4,!p});var n=[],p=(r,e)=>{a.forEach(a=>{var d=Object.assign({},r);if(d.p=Object.assign({},r.p),!(e[a.n]<=0)&&i(d,a)){if(d.ps+=a.n,0==d.p.x&&0==d.p.y&&0==d.d)return void n.push(d);var s=Object.assign([],e);s[a.n]-=1,p(d,s)}})};p({p:{x:0,y:0},d:0,ps:""},Object.assign([],r));var d=0;n.forEach(r=>{r.ps.length>d&&(d=r.ps.length)}),console.log(r[0]+r[1]+r[2]-d)};

Wypróbuj online!

Uwaga: Dane wejściowe to tak naprawdę zmienna q na początku. [2,6,4] zajmie również sporo czasu, ponieważ jest to rozwiązanie brutalnej siły bez optymalizacji.

Zrobiłem to, ponieważ nie było odpowiedzi od ponad roku i byłem po prostu ciekawy, czy to możliwe.

Kod oryginalny:

var q = [4, 2, 4];
var t = [
    {
        n: 0,
        d: [
            [0, -1, "0000000101011"],
            [1, -1, "0011111111111"],
            [0, 0, "0111101111111"],
            [1, 0, "1100010000000"]
        ],
        e: [2, -1, 1],

    },
    {
        n: 0,
        d: [
            [-1, -1, "1001111111111"],
            [0, -1, "0000010010110"],
            [-1, 0, "0110000100000"],
            [0, 0, "1101111011111"]
        ],
        e: [-2, -1, 3]
    },
    {
        n: 1,
        d: [
            [0, 0, "0011101111111"]
        ],
        e: [1, 0, 1]
    },
    {
        n: 1,
        d: [
            [0, 0, "1001111011111"]
        ],
        e: [-1, 0, 3]
    },
    {
        n: 2,
        d: [
            [0, 0, "1111101011111"]
        ],
        e: [0, -1, 0]
    },
];

r = (p) => {
    var d = p.d; var e = p.e; var o = [];
    d.forEach(i => {
        var d = i[2];
        o.push([-i[1], i[0], "" + d[10] + d[5] + d[0] + d[8] + d[3] + d[11] + d[6] + d[1] + d[9] + d[4] + d[12] + d[7] + d[2]])
    });
    return { d: o, e: [-e[1], e[0], e[2]] };
};

i = (g, p) => {
    //console.log(g.p, g.d);
    for (var i = 0; i < g.d; i++ , p = r(p));
    var c = false;
    p.d.forEach(d => {
        var v = g[`${g.p.x + d[0]},${g.p.y + d[1]}`];
        if (v === undefined) v = "00000000000000";
        var o = "";
        for (var i = 0; i < 13; i++) {
            if (v[i] === '1' && d[2][i] === '1')
                c = true;
            o += (v[i] === d[2][i]) ? v[i] : '1';
        }
        //console.log(o);
        g[`${g.p.x + d[0]},${g.p.y + d[1]}`] = o;
    });
    g.p.x += p.e[0];
    g.p.y += p.e[1];
    g.d = (g.d + p.e[2]) % 4;
    return !c;
};

var l = [];
var re = (g, p) => {
    t.forEach(piece => {
        var gr = Object.assign({}, g);
        gr.p = Object.assign({}, g.p);
        if (p[piece.n] <= 0)
            return;
        if (i(gr, piece)) {
            gr.ps += piece.n;
            if (gr.p.x == 0 && gr.p.y == 0 && gr.d == 0) {
                l.push(gr);
                return;
            }
            var ti = Object.assign([], p);
            ti[piece.n] -= 1;
            re(gr, ti);
        }
    });
};
var gr = { p: { x: 0, y: 0 }, d: 0, ps: "" };
re(gr, Object.assign([], q));

var c = 0;
var lo = 0;
l.forEach(g => {
    if (g.ps.length > lo) {
        require("./draw.js")(g, `outs/out${c++}.png`)
        lo = g.ps.length;
    }
});

console.log(q[0] + q[1] + q[2] - lo);

najpierw powinienem dołączyć grafikę użytych kafelków.

The sections of this tile were given a number and
used for comparison and overlap handling later.

So there first thing is the array t at the start. 
This is a collection of track pieces that contain
    n[ame]: the index of the input array.
    d[ata]: the offset from the current tile and the Tile bit values.
    e[nd]: the relative offset and rotation that the piece provides.

function r[otate] ( p[iece] )
    this outputs a piece that is rotated by 90 degrees
    by rearranging the tile bits and the end offset

function i[nsert] ( g[rid], p[iece] )
    this modifies the passed in grid trying to place down each tile of the piece.
    if it hits a point where 2 tiles intersect it sets a flag c[ollision]
    it then adjusts the current p[osition] and and d[irection] stored in the grid.
    then it returns !c[ollision]

function re[peat] ( g[rid], p[eices] )
    this iterates across all nodes which
        creates a copy of the g[rid] as gr[id].
        checks if the piece is available if not continue
        if the peice is added without a collision
            add piece name to gr[id].ps[piece string];
            it checks if its back at the start
                add gr[id] to l[ist]
                return as no more pieces can be added without a collision.
            clone peices remove the used peice ti[nput]
            call re[peate] (gr[id], ti[nput])

call re[peate] with empty grid

search l[ist] for longest piece string
and output input added together minus the length of the longest string.

Przepraszam, jeśli napis jest trudny do odczytania Nie jestem przyzwyczajony do wyjaśniania, jak działa mój kod.

PS Właściwie stworzyłem też kilka funkcji do rysowania map do png, ale oczywiście zostały one usunięte, aby zaoszczędzić przynajmniej trochę miejsca.