^{Este desafío está completamente arrancado inspirado en All Light , desarrollado por Soulgit Games.}

Desafío

Usted es electricista y es su trabajo conectar todas las luces a la batería.

• Las luces y la batería están dispuestas en una cuadrícula.
• Puede conectar una luz o batería a la luz o batería más cercana a su norte, sur, este y oeste.
• La batería puede tener cualquier cantidad de conexiones.
• Cada luz especifica cuántas conexiones requiere. Debes hacer exactamente esa cantidad de conexiones con esa luz.
• Puede crear conexiones simples o dobles entre dos luces (o luz y batería).
• Los cables no pueden cruzarse.
• Debe haber un camino desde cada luz hasta la batería.
• Se garantiza que existe al menos una solución válida.

Dada la posición de la batería y cada luz, y la cantidad de conexiones que requiere cada luz, emite las conexiones entre ellas que admiten estas propiedades.

Condición de victoria

Este es el código de golf , por lo que gana el código más corto en cada idioma.

Casos de prueba

I / O es flexible como siempre.

Para la entrada, usaré una matriz 2d del tamaño de la cuadrícula que almacena enteros positivos para luces, ceros para espacios en blanco y -1 para la batería. Otra buena opción podría ser una lista de luces, donde una luz es una tupla que contiene la posición de la luz y el número de conexiones requeridas.

Para la salida, usaré una lista de conexiones, donde una conexión es una tupla que contiene la posición inicial y la posición final. Si una conexión se duplica, tendré 2 de ellos en la lista (otra opción es incluir este parámetro en la tupla). Otra buena opción podría ser algún tipo de diseño de cuadrícula.

Si está utilizando un sistema de coordenadas, puede especificar el índice inicial y desde dónde indexar. Mis ejemplos estarán indexados a 0 y usarán (0, 0) como la esquina superior izquierda (fila, columna). (Estoy usando {} simplemente para introducir otro tipo de delimitador para que sea más fácil de leer, no porque sean conjuntos).

Aquí hay una vista gráfica de los casos de prueba: Pruebas 1-12

Prueba 1:

[-1 | 0 | 1 ] => [{(0, 0), (0, 2)}]

Prueba 2:

[-1 | 0 | 2 ] => [{(0, 0), (0, 2)}, {(0, 0), (0, 2)}]

Prueba 3:

[-1 ] [ 0 ] => [{(0, 0), (2, 0)), ((0, 0), (2, 0)}] [ 2 ]

Prueba 4:

[ 1 | 0 |-1 | 0 | 2 ] => [{(0, 0), (0, 2)}, {(0, 2), (0, 4)}, {(0, 2), (0, 4)}]

Prueba 5:

[ 2 ] [ 0 ] [-1 ] => [{(0, 0), (2, 0)}, {(0, 0), (2, 0)}, {(2, 0), (4, 0)}] [ 0 ] [ 1 ]

Prueba 6:

[ 1 | 0 | 0 ] [ 0 | 0 | 0 ] => [{(0, 0), (2, 0)}, {(2, 0), (2, 2)}] [ 2 | 0 |-1 ]

Prueba 7:

[ 4 | 0 | 0 |-1 ] [ 0 | 0 | 0 | 0 ] => [{(0, 0), (0, 3)}, {(0, 0), (0, 3)}, [ 2 | 0 | 0 | 0 ] {(0, 0), (3, 0)}, {(0, 0), (3, 0)}]

Prueba 8:

[ 2 | 0 |-1 | 0 | 2 ] [{(0, 0), (0, 2)}, {(0, 0), (0, 2)}, [ 0 | 0 | 0 | 0 | 0 ] => {(0, 2), (0, 4)}, {(0, 2), (0, 4)}, [ 0 | 0 | 1 | 0 | 0 ] {(0, 2), (2, 2)}]

Prueba 9:

[ 0 | 0 | 2 | 0 | 0 ] [ 0 | 0 | 0 | 0 | 0 ] [ 1 | 0 |-1 | 0 | 1 ] => [{(0, 2), (2, 2)}, {(0, 2), (2, 2)}, {(2, 0), (2, 2)}, [ 0 | 0 | 0 | 0 | 0 ] {(4, 2), (2, 2)}, {(2, 4), (2, 2)}, {(2, 4), (2, 2)}] [ 0 | 0 | 2 | 0 | 0 ]

Prueba 10:

[-1 | 2 | 3 | 2 ] => [{(0, 0), (0, 3)}, {(0, 0), (0, 3)}, {(0, 0), (0, 3)}, {(0, 0), (0, 3)}]

Prueba 11:

[-1 | 0 | 0 | 0 ] [ 3 | 0 | 0 | 0 ] [ 3 | 0 | 0 | 3 ] => [{(0, 0), (1, 0)}, {(1, 0), (2, 0)}, {(1, 0), (2, 0)}, [ 0 | 0 | 0 | 0 ] {(2, 0), (2, 3)}, {(2, 3), (4, 3)}, {(2, 3), (4, 3)}] [ 0 | 0 | 0 | 2 ]

Prueba 12:

[ 2 | 0 | 0 ] [{(0, 0), (1, 0)}, {(0, 0), (1, 0)}, {(1, 0), (1, 1)}, [ 3 |-1 | 0 ] => {(1, 1), (2, 1)}, {(1, 1), (2, 1)}, {(2, 0), (2, 1)}, [ 2 | 5 | 1 ] {(2, 0), (2, 1)}, {(2, 1), (2, 2)}]

JavaScript (Node.js) , 393 391 378 bytes

a=>(R=[],f=(a,[x,...y],z,Y)=>x?f(a.map(t=>[...t]),y,z,Y)||f(a,y,[...z,x],Y.map(p=>p.map(q=>q-Y[x[0]][x[1]]?q:Y[x[2]][x[3]])),--a[x[0]][x[1]],--a[x[2]][x[3]]):/[1-9]/.test(a)|Y.some(t=>t.some(u=>u-Y[I][J]&&u))?0:z)(a=a.map(A=(b,i)=>b.map((x,j)=>x&&(A[i]+1&&R.push([i,A[i],i,j]),f[j]+1&&R.push([f[j],j,i,j]),A[I=i]=j,f[J=j]=i,x/=x>0))),[...R,...R],C=[],a.map(p=>p.map(q=>q&&++C)))

Pruébalo en línea!

a=>(
    a=a.map(
        A=(b,i)=>
            b.map(
                (x,j)=>
                    x&&(                                  // A[i]+1 <==> A[i] is NOT NaN
                        A[i]+1&&R.push([i,A[i],i,j]),     // Use A and f to store last
                        f[j]+1&&R.push([f[j],j,i,j]),     // existance of row and column
                        A[I=i]=j,f[J=j]=i,x/=x>0          // -1 => -Inf, +n => n
                    )
            ),
            R=[],
            f=([x,...y],z,Y)=>
                x?
                    f(
                        y,[...z,x],
                        Y.map(p=>p.map(q=>q-Y[x[0]][x[1]]?q:Y[x[2]][x[3]])), // merge
                        --a[x[0]][x[1]],--a[x[2]][x[3]]
                    )||
                    f(y,z,Y,++a[x[0]][x[1]],++a[x[2]][x[3]])
                :
                    /[1-9]/.test(a)|
                    Y.some(t=>t.some(u=>u-Y[I][J]&&u)) // not totally merged
                    ?0:z
    ),f)([...R,...R],[],a.map(p=>p.map(q=>q&&++C),C=0)
)