Solve the BattleBlock Theater Puzzle

Question

The game BattleBlock Theater occasionally contains a puzzle which is a generalised version of Lights Out. You've got three adjacent blocks, each of which indicates a level between 1 and 4 inclusive with bars, e.g.:

|
||||
||

If you touch a block, then that block as well as any adjacent block will increment its level (wrapping back from 4 to 1). The puzzle is solved when all three blocks show the same level (it doesn't matter which level). Since, the order you touch the blocks in doesn't matter, we denote a solution by how often each block is touched. The optimal solution for the above input would be 201:

|    --> || --> |||     |||
||||     |      ||      |||
||       ||     ||  --> |||

The game very easily generalises any number of blocks, although for some numbers, not all configurations are solvable.

The Challenge

Given a sequence of block levels, return how often each block needs to be touched to solve the puzzle. E.g. the above example would be given as 142 and could yield 201 as a result. If there is no solution, return some consistent output of your choice, which is distinguishable from all potential solutions, e.g. -1 or an empty string.

You may write a function or program, take input via STDIN, command-line argument or function argument, in any convenient list or string format, and similarly output via a return value or by printing to STDOUT.

Your code should return correct results for all test cases within a minute on a reasonable machine. (This is not a completely strict limit, so if your solution takes a minute and ten seconds, that's fine, but if it takes 3 minutes, it isn't. A good algorithm will easily solve them in seconds.)

This is code golf, so the shortest answer (in bytes) wins.

Examples

Solutions are not unique, so you may get different results.

Input                          Output

1                              0
11                             00
12                             No solution
142                            201
434                            101
222                            000
4113                           0230
32444                          No solution
23432                          10301
421232                         212301
3442223221221422412334         0330130000130202221111
22231244334432131322442        No solution
111111111111111111111222       000000000000000000000030
111111111111111111111234       100100100100100100100133
412224131444114441432434       113013201011001101012133

As far as I know, there are exactly 4 solutions for each input where the number of blocks is 0 mod 3, or 1 mod 3, and there are 0 or 16 solutions where it is 2 mod 3.

Answer 1

Python 2, 115 bytes

n=input()
for F in range(4):
 t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n)
 if x<1:print t[:-1];break

This is the golfed version of the program I wrote while discussing the problem with Martin.

Input is a list via STDIN. Output is a list representing the last solution found if there is a solution, or zero if there isn't. For example:

>>>
[1, 4, 2]
[2, 1, 1]
>>>
[1, 2]
0
>>>
map(int,"3442223221221422412334")
[2, 3, 3, 2, 1, 3, 2, 0, 0, 2, 1, 3, 2, 2, 0, 0, 2, 2, 3, 1, 1, 3]

---

Pyth, 32 29 bytes

V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB

The obligatory port. Thanks to @Jakube for the 3 byte saving.

Input method is the same as above, try it online.

---

Explanation (long and full of logic!)

First, two basic observations:

• Observation 1: It doesn't matter which order you touch the blocks

• Observation 2: If you touch a block 4 times, it's equivalent to touching it once

In other words, if there is a solution then there is a solution where the number of touches is between 0 and 3 inclusive.

Since modulo 4 is so nice, let's do that with the blocks too. For the rest of this explanation, block level 0 is equivalent to block level 4.

Now let's denote a[k] to be the current level of block k and x[k] to be the number of times we touch block k in a solution. Also let n be the total number of blocks. As @Jakube has noted, a solution must satisfy:

  a[0]   + x[0] + x[1]
= a[1]   + x[0] + x[1] + x[2]
= a[2]          + x[1] + x[2] + x[3]
= a[3]                 + x[2] + x[3] + x[4]
...
= a[n-1]                                     ...  + x[n-2] + x[n-1] + x[n]
= a[n]                                       ...           + x[n-1] + x[n]
= C

where C is the final level all blocks end up on, between 0 and 3 inclusive (remember we're treating level 4 as level 0) and all equations above are really congruences modulo 4.

Now here's the fun part:

• Observation 3: If a solution exists, a solution exists for any final block level 0 <= C <= 3.

There are three cases based on the number of blocks modulo 3. The explanation for each of them is the same — for any number of blocks, there exists a subset of blocks which, if you touch each of them once, increases all block levels by exactly 1.

0 mod 3 (touch every third block starting from the second):
    .X. / .X. / .X.

1 mod 3 (touch every third block starting from the first):
    X. / .X. / .X. / .X

2 mod 3 (touch every third block starting from either the first or second):
    X. / .X. / .X. / .X.
    .X. / .X. / .X. / .X

This explains why there are 4 solutions for 0 mod 3 and 1 mod 3, and usually 16 solutions for 2 mod 3. If you have a solution already, touching the blocks as above gives another solution which ends up at a higher block level (wrapping around).

So what does this mean? We can pick any final block level C we want! Let's pick C = 0, because this saves on bytes.

Now our equations become:

0 = a[0] + x[0] + x[1]
0 = a[1] + x[0] + x[1] + x[2]
0 = a[2] + x[1] + x[2] + x[3]
0 = a[3] + x[2] + x[3] + x[4]
...
0 = a[n-1] + x[n-2] + x[n-1] + x[n]
0 = a[n] + x[n-1] + x[n]

And rearrange:

x[1] = -a[0] - x[0]
x[2] = -a[1] - x[0] - x[1]
x[3] = -a[2] - x[1] - x[2]
x[4] = -a[3] - x[2] - x[3]
...
x[n] = a[n-1] - x[n-2] - x[n-1]
x[n] = a[n] - x[n-1]

So what we can see is, if we have x[0], then we can use all the equations except the last to find out every other x[k]. The last equation is an additional condition we must check.

This gives us an algorithm:

• Try all values for x[0]
• Use the above equations to work out all of the other x[k]
• Check if the last condition is satisfied. If so, save the solution.

That gives the solution above.

So why do we sometimes get no solution for 2 mod 3? Let's take a look at these two patterns again:

X. / .X. / .X. / .X.
.X. / .X. / .X. / .X

Now consider the equations at those positions, i.e. for the first one:

0 = a[0] + x[0] + x[1]
0 = a[3] + x[2] + x[3] + x[4]
0 = a[6] + x[5] + x[6] + x[7]
0 = a[9] + x[8] + x[9] + x[10]

Add them up:

0 = (a[0] + a[3] + a[6] + a[9]) + (x[0] + x[1] + ... + x[9] + x[10])

For the second one:

0 = a[1] + x[0] + x[1] + x[2]
0 = a[4] + x[3] + x[4] + x[5]
0 = a[7] + x[6] + x[7] + x[8]
0 = a[10] + x[9] + x[10]

Add them up again:

0 = (a[1] + a[4] + a[7] + a[10]) + (x[0] + x[1] + ... + x[9] + x[10])

So if (a[1] + a[4] + a[7] + a[10]) and (a[0] + a[3] + a[6] + a[9]) are not equal, then we have no solution. But if they are equal, then we get 16 solutions. This was for the n = 11 case, but of course this generalises to any number that is 2 mod 3 — take the sum of every third element starting from the second, and compare to the sum of every third element starting from the first.

Now finally, is it possible to figure out what x[0] has to be instead of trying all of the possibilities? After all, since we restricted our target level C to be 0, there is only one x[0] which gives a solution in the 0 mod 3 or 1 mod 3 case (as 4 solutions / 4 final levels = 1 solution for a specific final level).

The answer is... yes! We can do this for 0 mod 3:

 .X..X
.X..X.

Which translates to:

0 = a[2] + x[1] + x[2] + x[3]   -> 0 = (a[2] + a[5]) + (x[1] + ... + x[5])
0 = a[5] + x[4] + x[5]          /


0 = a[1] + x[0] + x[1] + x[2]   -> 0 = (a[1] + a[4]) + (x[0] + x[1] + ... + x[5])
0 = a[4] + x[3] + x[4] + x[5]   /

Subtracting gives:

x[1] = (a[2] + a[5]) - (a[1] + a[4])

Similarly for 1 mod 3 we can do this pattern:

 .X..X.
X..X..X

Which gives:

x[0] = (a[2] + a[5]) - (a[0] + a[3] + a[6])

These of course generalise by extending the indices by increments of 3.

For 2 mod 3, since we have two subsets which cover every block, we can actually pick any x[0]. In fact, this is true for x[0], x[1], x[3], x[4], x[6], x[7], ... (basically any index not congruent to 2 mod 3, as they are not covered by either subset).

So we have a way of picking an x[0] instead of trying all possibilities...

... but the bad news is that this doesn't save on bytes (124 bytes):

def f(n):s=[];L=len(n);B=sum(n[~-L%3::3])-sum(n[-~L%3::3]);x=A=0;exec"s+=B%4,;A,B=B,-n[x]-A-B;x+=1;"*L*(L%3<2or B<1);print s

Answer 2

Pyth, 72 76 73 66 39 38 character

Ph+f!eTmu+G%+&H@G_3-@QH@QhH4UtQd^UT2]Y

edit 4: Realized, that the calculations Q[N]-Q[N+1]+solution[-3] and Q[-2]-Q[-1]+solution[-3] are ident. Therefore I overcalculate the solution by 1, and filter the solutions, where the last entry is 0. Then I pop the last entry. Luckily the special cases doesn't need an extra treatment with this approach. -27 character

edit 3: Applying some golfing tricks from FryAmTheEggman: -7 character

edit 2: Using filter, reduce and map: -3 character

edit 1:In my first version I didn't printed anything, if there was no solution. I don't think that's allowed, therefore +4 character.

Expects a list of integers as input [1,4,2] and outputs a valid solution [2,0,1] if there is one, otherwise an empty list [].

Explanation:

Let Q be the list of 5 levels and Y the list of the solution. The following equations have to hold:

  Q0 + Y0 + Y1 
= Q1 + Y0 + Y1 + Y2
= Q2      + Y1 + Y2 + Y3
= Q3           + Y2 + Y3 + Y4
= Q4                + Y3 + Y4

Therefore if we use any Y0 and Y1, we can calculate Y2, Y3 and Y4 in the following way.

Y2 = (Q0 - Q1     ) mod 4
Y3 = (Q1 - Q2 + Y0) mod 4
Y4 = (Q2 - Q3 + Y1) mod 4

Than all levels exept the last one are equal (because we didn't used the equation = Q4 + Y3 + Y4. To check, if this last one is also equal to the other levels, we can simply check if (Q3 - Q4 + Y2) mod 4 == 0. Notice, that the left part would be the value Y5. If I calculate the 6th part of the solution, I can simply check, if it is zero.

In my approach I simply iterate over all possible starts ([0,0], to [3,3]), and calculate length(input)-1 more entries and filter all solutions that end with a zero.

mu+G%+&H@G_3-@QH@QhH4UtQd^UT2   generates all possible solutions

it's basically the following:

G = start value           //one of "^UT2", [0,0], [0,1], ..., [9,9]
                          //up to [3,3] would be enough but cost 1 char more
for H in range(len(Q)-1): //"UtQ"
   G+=[(H and G[-3])+(Q(H)-Q(H+1))%4] //"+G%+&H@G_3-@QH@QhH4"
   //H and G[-3] is 0, when H is empty, else G[-3]

then I filter these possible solutions for valid ones:

f!eT //only use solutions, which end in 0

to this list of solutions I append an empty list, so that it has at least one item in it

 +....]Y

and take the first solution h, pop the last element p and print it

 Ph

Notice, that this also works, if there is only one block. In my approach I get the starting position [0,0] and doesn't extend it. Since the last entry is 0, it prints the solution [0].

The second special case (2 blocks) isn't that special after all. Not sure, why I overcomplicated things earlier.

Answer 3

Ruby, 320 313 chars

m=gets.chop.chars.map{|x|x.to_i-1}
a=m.map{0}
t=->n{m[n]+=1
m[n-1]+=1if n>0
m[n+1]+=1if n<m.size-1
m.map!{|x|x%4}
a[n]=(a[n]+1)%4}
t[0]until m[0]==1
(2...m.size).map{|n|t[n]until m[n-1]==1}
r=0
while m.uniq.size>1&&m[-1]!=1
(0...m.size).each_with_index{|n,i|([1,3,0][i%3]).times{t[n]}}
(r+=1)>5&&exit
end
$><<a*''

Can definitely be golfed more. Outputs nothing for unsolvable puzzles.

Ungolfed version:

#!/usr/bin/ruby

nums = gets.chomp.chars.map {|x| x.to_i-1 }
touches = nums.map {0}

# our goal: make all the numbers 1
# utility function
touch = ->n {
    nums[n] += 1
    nums[n-1] += 1 if n > 0
    nums[n+1] += 1 if n < (nums.length-1)
    nums.map! {|x| x % 4 }
    touches[n] = (touches[n] + 1) % 4
}

# first, start with the very first number
touch[0] until nums[0] == 1

# then, go from index 2 to the end to make the previous index right
(2...nums.length).each {|n|
    touch[n] until nums[n-1] == 1
}

iters = 0
if nums.uniq.length != 1
    # I have no idea why this works
    while nums[-1] != 1
        (0...nums.length).each_with_index {|n, i|
            ([1, 3, 0][i % 3]).times { touch[n] }
        }
        if (iters += 1) > 5
            puts -1
            exit
        end
    end
end

puts touches * ''

Okay, this one was fun. Here's the basic algorithm, with {n} representing n "touch"es on the number above the n, as demonstrated on one of the examples:

we want each number to be a 1
first make the first number a 1
3442223221221422412334
2}
1242223221221422412334
 {3} now keep "touch"ing until the number to the left is a 1
1131223221221422412334
  {2}
1113423221221422412334
   {2}
1111243221221422412334
... (repeat this procedure)
1111111111111111111110

I got stumped for a bit here. How can I turn the 111...1110 into a series of same numbers? So I compared my solution and the correct solution (note: the "touch" counts all are one greater than they should be because the input is 1-indexed, while the output is 0-indexed):

3033233103233301320210
0330130000130202221111

I noticed that each number was one away from the correct one mod 4, so I marked them with +s, -s, and =s:

3033233103233301320210 original program output
+-=+-=+-=+-=+-=+-=+-=+ amount to modify by (+1, -1, or 0 (=))
4334534404534602621511 result (the correct answer)

0330130000130202221111 (the original solution, digits equal to result mod 4)

That worked for a while, until I noticed that sometimes the final result was 111...11112 or 11...1113 as well! Fortunately, repeatedly applying the magical formula that makes no sense but works also sorted these out.

So, there you have it. A program that starts out making sense, but degrades into more and more ugly hackiness as it goes. Quite typical for a code golf solution, I think. :)

Answer 4

Python 2, 294,289,285,281 273 bytes

n=input();l=len(n);s=[0]*l
for i in range(2,l):
 a=(n[i-2]-n[i-1])%4;s[i]+=a;n[i-1]+=a;n[i]+=a
 if i+1<l:n[i+1]+=a
 n=[a%4for a in n]
if l%3>1 and n!=[n[0]]*l:print"x"
else:
 for i in range(l%3,l-1,3):s[i]+=(n[l-1]-n[l-2])%4
 m=min(s);s=[(a-m)%4 for a in s];print s

DEMO

I'm sure this can be golfed further..

Here are the results from the test cases:

[1]
-> [0]

[1,1]
-> [0, 0]

[1,2]
-> x

[1,4,2]
-> [2, 0, 1]

[4,3,4]
-> [1, 0, 1]

[2,2,2]
-> [0, 0, 0]

[4,1,1,3]
-> [0, 2, 3, 0]

[3,2,4,4,4]
-> x

[2,3,4,3,2]
-> [0, 0, 3, 3, 1]

[4,2,1,2,3,2]
-> [2, 0, 2, 3, 3, 1]

[3,4,4,2,2,2,3,2,2,1,2,2,1,4,2,2,4,1,2,3,3,4]
-> [0, 3, 3, 0, 1, 3, 0, 0, 0, 0, 1, 3, 0, 2, 0, 2, 2, 2, 1, 1, 1, 1]

[2,2,2,3,1,2,4,4,3,3,4,4,3,2,1,3,1,3,2,2,4,4,2]
-> x

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2]
-> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0]

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4]
-> [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 3, 3]

[4,1,2,2,2,4,1,3,1,4,4,4,1,1,4,4,4,1,4,3,2,4,3,4]
-> [1, 0, 3, 0, 0, 3, 2, 3, 1, 0, 0, 1, 0, 3, 1, 1, 3, 1, 0, 0, 2, 1, 2, 3]

The algorithm first makes sure that the values of all blocks except the last block are the same (by iterating through and adding to the "touch counts" of all blocks except the first 2). Then, if the number of blocks allows for it ((num_of_blocks - 1) % 3 != 1), goes back and makes sure the values of the rest of the blocks match the last block. Prints x if there is no solution.