^{Diese Herausforderung ist völlig abgezockt stark inspiriert von All Light , entwickelt von Soulgit Spielen.}

Herausforderung

Sie sind ein Elektriker und es ist Ihre Aufgabe, alle Lichter an die Batterie anzuschließen.

• Die Lichter und die Batterie sind in einem Raster angeordnet.
• Sie können eine Leuchte oder Batterie an die nächstgelegene Leuchte oder Batterie im Norden, Süden, Osten und Westen anschließen.
• Der Akku kann beliebig viele Anschlüsse haben.
• Jede Leuchte gibt an, wie viele Verbindungen erforderlich sind. Sie müssen genau so viele Verbindungen zu diesem Licht herstellen.
• Sie können einzelne Verbindungen oder doppelte Verbindungen zwischen zwei Leuchten (oder Leuchte und Batterie) herstellen.
• Drähte können sich nicht kreuzen.
• Von jedem Licht muss ein Pfad zur Batterie vorhanden sein.
• Mindestens eine gültige Lösung ist garantiert vorhanden.

Geben Sie unter Berücksichtigung der Position der Batterie und jeder Lampe sowie der Anzahl der Verbindungen, die jede Lampe benötigt, die Verbindungen zwischen ihnen aus, die diese Eigenschaften zulassen.

Gewinnbedingung

Das ist Code-Golf , also gewinnt der kürzeste Code in jeder Sprache.

Testfälle

I / O ist wie gewohnt flexibel.

Für die Eingabe verwende ich ein 2D-Array mit der Größe des Gitters, in dem positive ganze Zahlen für Lichter, Nullen für Leerzeichen und -1 für die Batterie gespeichert sind. Eine andere gute Wahl könnte eine Liste von Leuchten sein, wobei eine Leuchte ein Tupel ist, das die Position der Leuchte und die Anzahl der erforderlichen Verbindungen enthält.

Für die Ausgabe verwende ich eine Liste von Verbindungen, wobei eine Verbindung ein Tupel ist, das die Startposition und die Endposition enthält. Wenn eine Verbindung doppelt vorhanden ist, werden zwei in der Liste aufgeführt (eine andere Möglichkeit besteht darin, diesen Parameter in das Tupel aufzunehmen). Eine andere gute Option könnte eine Art Rasterlayout sein.

Wenn Sie ein Koordinatensystem verwenden, können Sie den Startindex und den Index angeben. Meine Beispiele sind 0-indiziert und verwenden (0, 0) als obere linke Ecke (Zeile, Spalte). (Ich verwende {} nur, um eine andere Art von Trennzeichen einzuführen, damit es einfacher zu lesen ist, nicht weil es sich um Mengen handelt.)

Hier ist eine grafische Ansicht der Testfälle: Tests 1-12

Test 1:

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

Test 2:

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

Test 3:

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

Test 4:

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

Test 5:

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

Test 6:

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

Test 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)}]

Test 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)}]

Test 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 ]

Test 10:

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

Test 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 ]

Test 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 Byte

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

Probieren Sie es online!

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