The Light Up Game

Question

The Challenge

The game Light Up! is a simple puzzle game where the objective is to light up every cell in an n-by-n array with light bulbs. However, there are blocks in the way that will prevent light from traveling, and no lightbulb can be places such that another lightbulb shines light on it. Each light bulb has light coming from it in only the horizontal and vertical directions.

You must make a program that takes in an array of 5 numbers. Your program must convert each numbers into a 5-bit binary number, which will define at what places in the array there are blocks. If there is a 1, there is a block at the spot, but if there is a 0, there is not a block. Each number converted to binary defines a row, like:

[5,6,5,6,5] -> [00101, 00110, 00101, 00110, 00101] ->

. . B . B
. . B B .
. . B . B
. . B B .
. . B . B

Where B = blocks that block light

Your program must take this array and find the solutions (places where you need to put light) and give it back as an array of 5 numbers.

Example:

Input: [1,5,9,13,17]

Which translates to [00001, 00101, 01001, 01101, 10001]

Making the array:

. . . . B
. . B . B
. B . . B
. B B . B
B . . . B

A solution for this array is

L ~ ~ ~ B
~ L B ~ B
~ B ~ L B
~ B B ~ B
B L ~ ~ B

~ = Light L = Lightbulb

Which gives the binary array of lights [10000, 01000, 00010, 00000, 01000]

And translates back to [16, 8, 2, 0, 8]

Output: [16, 8, 2, 0, 8]

Rules

• Two lightbulbs can not be in the same row or column if there is no block between them.
• A lightbulb's light can only travel horizontally and vertically, and will stop if there is a block in the way
• Your program must take in an array [a,b,c,d,e] and output in the same form
• If there are no way the array can be solved, your program must not give output or state "No Output."
• This is a [code-golf] challenge, lowest amount in bytes wins!

Answer 1

CJam, 79 73 68 bytes

32q~:Q,m*{Q.&:|!},{Q]{2b5Ue[}f%~..-_z]{Wa/_1fb.f|1a*}f%~z..|:|1a=}=p

This will work only using the Java interpreter. It should terminate eventually with default switches, but it becomes reasonably fast by increasing the maximum heap size.

At the cost of 7 more bytes (for a total of 75 bytes), we can speed up the code significantly.

q~32b:Q;Y25#{Q&!},{Q]{2b25Ue[}/.m5/_z]{Wa/_1fb.f|1a*}f%~z..|:|1a=}=32bU5e[p

It still requires a little patience, but you can this version online in the CJam interpreter.

Test run

$ alias='java -jar -Xmx4G /usr/local/share/cjam/cjam-0.6.5.jar'
$ time cjam lights-short.cjam <<< '[1 5 9 13 17]'
[2 8 4 16 4]

real    0m44.287s
user    3m47.426s
sys     0m1.821s
$ time cjam lights-fast.cjam <<< '[1 5 9 13 17]'
[2 8 4 16 4]

real    0m1.926s
user    0m2.383s
sys     0m0.098s

This gives us the following solution for the test case:

. . . L B
. L B . B
. B L . B
L B B . B
B . L . B

Idea

For a given vector of wall placements, we iterate over all 33,554,432 vectors of light bulb placements, searching for one that satisfies the criteria.

If the bitwise AND of any pair of corresponding integers is non-zero, the spot is occupied by both a wall and a light bulb. We immediately discard such vectors.

We now convert the integers of wall and bulb placements to binary and subtract the resulting two-dimensional arrays. The result is a single 5 × 5 array, where 0 indices an empty space, 1 indicates a light bulb and -1 indicates a wall.

We take this array and its transpose, and do the following for each row of each of them:

• For all runs of non-walls, we replace each 0 or 1 with the number of 1s in this run.

• Then, we replace the -1s with 1s.

We transpose the second array again (effectively applying the above to its columns) and take the element-wise bitwise OR of both arrays.

If there is any 0 left, the corresponding spot is not reached by light. Likewise, if there is any number greater than 1, the are two non-separated light bulbs in the same row or column. Thus, a valid solution with produce an array that consists entirely of 1s.

Code

32q~:Q   e# Push 32, evaluate the input, and store the result in Q.
,m*      e# Get the length of Q (5) and push the vectors of {0, ..., 31}^5.
{        e# Filter; for each vector V:
  Q.&    e#   Take the bitwise and of the elements of V and Q.
  :|!    e#   Bitwise OR the results, and apply logical NOT.
},       e# Keep V if the result was 1.
{        e# Find; for each vector V:
  Q]     e#   Push Q and wrap V and Q in a array.
  {      e#   Map the following block over each of them:
    2b   e#     Convert the component to base 2.
    5Ue[ e#     Left-pad with 0s to a length of 5.
  }f%    e#
  ~      e#   Dump the modified V and Q on the stack.
  ..-    e#   Apply doubly vectorized subtraction.
  _z]    e#   Push a transposed copy of the result. Wrap both in an array.
  {      e#   Map the following block over each of them:
    Wa/  e#     Split at -1.
    _1fb e#     Add the integers of each chunk to count the number of 1s.
    .f|  e#     Vectorized mapped bitwise OR to replace each integer with the
         e#     number of 1s (possibly incremented).
    1a*  e#     Rejoin the chunks, separating by 1s.
  }f%    e#
  ~      e#   Dump both results on the stack.
  z      e#   Transpose the second one.
  ..|    e#   Doubly vectorized bitwise OR.
  :|     e#   Reduce the array by set union.
  1a=    e#   Check if the result is [1].
}=       e# If it is, push the vector and terminate the loop.
p        e# Print the item on the stack.

If there is no solution, p will be called on an empty stack, throwing an error and producing no output.