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.