Conjunto de trem simplificado

27

Existem muitos tipos diferentes de conjuntos de trens, desde trilhos de madeira como o Brio, até controle totalmente digital, perfeitas réplicas metálicas minúsculas de trens reais, mas todos exigem que um trilho seja projetado, idealmente, usando o máximo possível de suas peças.

Portanto, sua tarefa é determinar se, dada a entrada das peças disponíveis, é possível construir um circuito fechado completo usando todos os elementos e, caso contrário, quantas peças serão deixadas no circuito máximo possível.

Como este é um conjunto de trens simplificado, existem apenas 3 elementos: curva grande, pequena curva e reta. Tudo isso é baseado em uma grade quadrada:

Grade quadrada mostrando grande curva e pequena curva

  • "Big Curve" é um canto de 90 graus, cobrindo 2 unidades em cada dimensão
  • "Little Curve" é um canto de 90 graus, cobrindo uma unidade em cada direção
  • "Reto" é um elemento reto, com 1 unidade de comprimento

Isso significa que o circuito mínimo possível é formado por 4 pequenas curvas - é um círculo, com raio de 1 unidade. Isso pode ser estendido adicionando pares de elementos retos para formar várias formas ovais. Existem outros circuitos possíveis adicionando mais curvas ou misturando os tipos de curva.

Este conjunto de trens não inclui junções ou métodos para cruzar as faixas, portanto, não é válido que dois elementos se conectem à mesma extremidade de um outro elemento (sem formações Y) ou cruzem entre si (sem formações X) . Além disso, é um conjunto de trens, portanto, qualquer formação que não permita a passagem de um trem não é válida: exemplos incluem retas que se encontram em ângulos de 90 graus (sempre deve haver uma curva entre retas perpendiculares) e curvas que se encontram em ângulos de 90 graus (as curvas devem fluir).

Você também deseja usar o maior número possível de peças, ignorando que tipo elas são, para sempre optar por um circuito com mais bits. Finalmente, você só tem um trem; portanto, qualquer solução que resulte em múltiplos circuitos é inaceitável. .

Entrada

Uma matriz de três números inteiros, todos maiores ou iguais a 0, correspondendo ao número de curvas grandes, pequenas curvas e retas disponíveis ou parâmetros passados ​​para o seu programa, na mesma ordem.

Saída

Um número correspondente ao número de peças restantes quando o circuito máximo possível para os elementos fornecidos é construído.

Dados de teste

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

Notas

  • 2 retas e uma pequena curva são equivalentes a uma grande curva, mas usam mais peças, portanto são preferidas - nunca deve ser uma situação em que essa combinação é deixada, se houver grandes curvas no circuito
  • Normalmente, 4 pequenas curvas podem ser trocadas por 4 retas, mas não se isso fizer com que o circuito se cruze
  • O conjunto de trens também é idealizado - os elementos da pista ocupam as larguras mostradas, portanto, é válido que as curvas passem por um único quadrado da grade sem interseção, em alguns casos. A grade apenas define as dimensões do elemento. Em particular, duas grandes curvas podem ser colocadas de modo que o quadrado da grade no canto superior esquerdo do diagrama de exemplo também seja o quadrado inferior direito de outra grande curva que corre da esquerda para cima (com o diagrama mostrando uma que funciona da direita para a parte inferior)
  • Uma pequena curva pode caber no espaço vazio sob uma grande curva (quadrado da grade inferior direito acima). Uma segunda grande curva também poderia usar esse espaço, deslocando uma transversal e outra abaixo da primeira
  • Uma curva pequena não pode caber no mesmo espaço da grade do lado de fora de uma grande curva - principalmente porque não há como conectar-se a ela que não se cruze ilegalmente
Mateus
fonte
Portanto, a saída para [5,0,0]ou [0,5,0]seria 1. Isso está correto? Você poderia adicionar um caso de teste?
Arnauld
@arnauld Sim, está correto. Sempre deve ser o número restante de elementos após a construção do circuito mais longo possível.
Matthew Matthew
Você poderia confirmar que essa é uma solução [8,0,0], com dois elementos 2x2 sobrepostos no centro da grade?
Arnauld
Sim, essa é a solução esperada para esse caso de teste.
Matthew
Não estou claro como funciona a auto-interseção. Você poderia ser mais explícito ao definir o que é permitido e o que é proibido?
Assistente de trigo

Respostas:

9

[JavaScript (Node.js)], 1220 bytes

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

Experimente online!

Nota: A entrada é realmente a variável q no início. [2,6,4] também levará bastante tempo, pois é uma solução de força bruta sem otimizações.

Na verdade, eu fiz isso porque não foi respondido há mais de um ano e fiquei curioso para saber se isso era possível.


Código original:

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

primeiro, devo incluir um gráfico das peças que usei.

telhas usadas

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.

Desculpe se a redação é difícil de ler, não estou acostumado a explicar como meu código funciona.

PS: Na verdade, eu também fiz algumas funções para desenhar os mapas em um png, mas é claro que eles foram removidos para economizar pelo menos algum espaço.

Cieric
fonte
Estou impressionado - eu meio que perdi a esperança nessa! Estaria interessado em uma redação
Matthew
@ Matthew, vou ver quando tiver tempo de escrever uma. Na verdade, pode demorar um pouco. Mas sim, normalmente esses são os meus tipos favoritos de quebra-cabeças. Mesmo que não seja curto, é divertido provar que é possível.
Cieric 18/10/19
@Matthew adicionou a redação.
Cieric
Existe uma razão pela qual você escolheu usar em p[a.n]-=1vez de p[a.n]--?
Jonathan Frech
Inicializar qassim não é um método de entrada permitido . Geralmente, crie um argumento de função ou leia-o de stdin.
Ørjan Johansen