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
| --> || --> ||| ||| |||| | || ||| || || || --> |||
The game very easily generalises any number of blocks, although for some numbers, not all configurations are solvable.
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.
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.