13
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – musicman523 Apr 21 '18 at 18:29
  • \$\begingroup\$ 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]. \$\endgroup\$ – user202729 Apr 22 '18 at 11:55
  • \$\begingroup\$ Somewhat reminds me of the Blossom algorithm. \$\endgroup\$ – user202729 Apr 22 '18 at 15:22
  • 2
    \$\begingroup\$ @user202729 I guarantee that the input has a solution satisfying all the conditions \$\endgroup\$ – musicman523 Apr 22 '18 at 16:40
  • 1
    \$\begingroup\$ This seems similar to a Hashi puzzle. I think many of the same steps to solving either of them are the same. \$\endgroup\$ – Οurous May 11 '18 at 2:59
2
\$\begingroup\$

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

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)
)
\$\endgroup\$
  • \$\begingroup\$ Fails for this test case. \$\endgroup\$ – user202729 Apr 24 '18 at 6:40
  • \$\begingroup\$ Is there a shortcut for /[1-9]/ in JavaScript RegEx? \$\endgroup\$ – Zacharý May 13 '18 at 13:30
  • \$\begingroup\$ @Zacharý I don't think so. Usually [0-9] is used \$\endgroup\$ – l4m2 May 13 '18 at 14:44
  • \$\begingroup\$ Silly me! I thought that's what you wrote \$\endgroup\$ – Zacharý May 13 '18 at 18:59
  • \$\begingroup\$ @Zacharý What?? \$\endgroup\$ – l4m2 May 13 '18 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.