Il existe de nombreux types de trains, allant des voies en bois comme Brio, au contrôle entièrement numérique de minuscules répliques métalliques parfaites de trains réels, mais elles nécessitent toutes une voie à concevoir, en utilisant idéalement autant de vos pièces que possible.

Donc, votre tâche est de déterminer si, étant donné l'entrée des pièces disponibles, il est possible de construire un circuit fermé complet en utilisant tous les éléments, et sinon, combien de pièces restera du circuit maximum possible.

Puisqu'il s'agit d'un train simplifié, il n'y a que 3 éléments: grande courbe, petite courbe et droite. Ceux-ci sont tous basés sur une grille carrée:

• "Big Curve" est un coin à 90 degrés, couvrant 2 unités dans chaque dimension
• "Little Curve" est un coin à 90 degrés, couvrant une unité dans chaque direction
• "Straight" est un élément droit, 1 unité de long

Cela signifie que le circuit minimum possible est formé de 4 petites courbes - c'est un cercle, de rayon 1 unité. Cela peut être étendu en ajoutant des paires d'éléments droits pour former divers ovales. Il existe d'autres circuits possibles en ajoutant plus de courbes ou en mélangeant les types de courbes.

Cet ensemble de train ne comprend aucune jonction ni aucune méthode pour les voies à traverser, il n'est donc pas valable pour deux éléments de se connecter à la même extrémité d'un autre élément (pas de formations Y) ou de se croiser (pas de formations X) . De plus, c'est un ensemble de trains, donc toute formation qui ne permet pas à un train de passer n'est pas valide: les exemples incluent les lignes droites se rencontrant à des angles de 90 degrés (il doit toujours y avoir une courbe entre les lignes droites perpendiculaires) et les courbes se rencontrant à des angles de 90 degrés (les courbes doivent couler).

Vous souhaitez également utiliser autant de pièces que possible, en ignorant leur type, vous opterez donc toujours pour un circuit qui contient plus de bits. Enfin, vous n'avez qu'un seul train, donc toute solution qui aboutit à plusieurs circuits est inacceptable .

Contribution

Soit un tableau de trois entiers, tous supérieurs ou égaux à 0, correspondant au nombre de grandes courbes, de petites courbes et de lignes droites disponibles, ou de paramètres passés à votre programme, dans le même ordre.

Sortie

Un nombre correspondant au nombre de pièces restantes lors de la construction du circuit maximum possible pour les éléments fournis.

Données de test

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

Remarques

• 2 lignes droites et une petite courbe équivalent à une grande courbe, mais utilisez plus de pièces, donc sont préférées - ne devrait jamais être une situation où cette combinaison est laissée, s'il y a de grandes courbes dans le circuit
• 4 petites courbes peuvent généralement être échangées pour 4 lignes droites, mais pas si cela entraîne une intersection du circuit
• Le train est également idéalisé - les éléments de voie occupent les largeurs indiquées, il est donc valable que les courbes traversent un seul quadrillage sans se croiser, dans certains cas. La grille définit simplement les dimensions des éléments. En particulier, deux grandes courbes peuvent être placées de sorte que le carré de la grille en haut à gauche du diagramme d'exemple soit également le carré en bas à droite d'une autre grande courbe allant de gauche à haut (avec le diagramme montrant une allant de droite à bas)
• Une petite courbe peut tenir dans l'espace vide sous une grande courbe (carré de grille en bas à droite au-dessus). Une deuxième grande courbe pourrait également utiliser cet espace, décalée d'un côté et d'un vers le bas depuis le premier
• Une petite courbe ne peut pas tenir sur le même espace de grille que l'extérieur d'une grande courbe - principalement parce qu'il n'y a aucun moyen de s'y connecter qui ne se coupe pas illégalement

[JavaScript (Node.js)], 1220 octets

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

Essayez-le en ligne!

Remarque: L'entrée est en fait la variable q au début. [2,6,4] prendra également pas mal de temps car il s'agit d'une solution de force brute sans optimisation.

En fait, je l'ai fait parce qu'il n'y a pas eu de réponse depuis plus d'un an et j'étais juste un peu curieux de savoir si c'était possible.

Code d'origine:

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

je dois d'abord inclure un graphique des tuiles que j'ai utilisées.

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.

Désolé si l'écriture est difficile à lire, je n'ai pas l'habitude d'expliquer comment fonctionne mon code.

PS J'ai en fait aussi fait quelques fonctions pour dessiner les cartes au format png mais bien sûr celles-ci ont été supprimées pour économiser au moins un peu d'espace.