# All Light All Light All Light!

This challenge is completely ripped offheavily inspired by All Light, developed by Soulgit Games.

# Challenge

You are an electrician, and it's your job to wire up all the lights to the battery.

• The lights and battery are laid out in a grid.
• You can connect a light or battery to the nearest light or battery to its north, south, east, and west.
• The battery can have any number of connections.
• Each light specifies how many connections it requires. You must make exactly that many connections to that light.
• You can create single connections or double connections between two lights (or light and battery).
• Wires cannot cross.
• There must be a path from each light to the battery.
• At least one valid solution is guaranteed to exist.

Given the position of the battery and each light, and the number of connections each light requires, output the connections between them that admit these properties.

# Win Condition

This is , so the shortest code in each language wins.

# Test Cases

I/O is flexible as usual.

For input I will be using a 2d array the size of the grid which stores positive integers for lights, zeros for blank spaces, and -1 for the battery. Another good choice might be a list of lights, where a light is a tuple containing the light's position and number of required connections.

For output I will be using a list of connections, where a connection is a tuple containing the starting position and ending position. If a connection is doubled then I will have 2 of them in the list (another option is to include this parameter in the tuple). Another good option could be some sort of grid layout.

If you are using a coordinate system you may specify the starting index and where you index from. My examples will be 0-indexed and use (0, 0) as the top left corner (row, column). (I am using {} simply to introduce another type of delimiter so it is easier to read, not because they are sets.)

Here is a graphical view of the test cases: 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)}]

• Sandbox Apr 21, 2018 at 18:29
• I suggest having a test case such that there exists a solution satisfy every condition except "There must be a path from each light to the battery.". For example [1 | -1] [1 1]. Apr 22, 2018 at 11:55
• Somewhat reminds me of the Blossom algorithm. Apr 22, 2018 at 15:22
• @user202729 I guarantee that the input has a solution satisfying all the conditions Apr 22, 2018 at 16:40
• This seems similar to a Hashi puzzle. I think many of the same steps to solving either of them are the same. May 11, 2018 at 2:59

# JavaScript (Node.js), 393391 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)))


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

• Apr 24, 2018 at 6:40
• Is there a shortcut for /[1-9]/ in JavaScript RegEx? May 13, 2018 at 13:30
• @Zacharý I don't think so. Usually [0-9] is used
– l4m2
May 13, 2018 at 14:44
• Silly me! I thought that's what you wrote May 13, 2018 at 18:59
• @Zacharý What??
– l4m2
May 13, 2018 at 19:13