El juego BattleBlock Theater ocasionalmente contiene un rompecabezas que es una versión generalizada de Lights Out . Tienes tres bloques adyacentes, cada uno de los cuales indica un nivel entre 1 y 4 inclusive con barras, por ejemplo:

|
||||
||

Si tocas un bloque, entonces ese bloque, así como cualquier bloque adyacente, incrementará su nivel (retrocediendo de 4 a 1). El rompecabezas se resuelve cuando los tres bloques muestran el mismo nivel (no importa qué nivel). Como el orden en el que toca los bloques no importa, denotamos una solución por la frecuencia con la que se toca cada bloque. La solución óptima para la entrada anterior sería 201:

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

El juego generaliza fácilmente cualquier número de bloques, aunque para algunos números, no todas las configuraciones son solucionables.

El reto

Dada una secuencia de niveles de bloque, regrese la frecuencia con la que se debe tocar cada bloque para resolver el rompecabezas. Por ejemplo, el ejemplo anterior se daría como 142y podría dar 201como resultado. Si no hay solución, devuelva un resultado consistente de su elección, que se distingue de todas las soluciones potenciales, por ejemplo, -1o una cadena vacía.

Puede escribir una función o programa, recibir información a través de STDIN, argumento de línea de comando o argumento de función, en cualquier lista conveniente o formato de cadena, y generar de manera similar a través de un valor de retorno o imprimiendo en STDOUT.

Su código debe devolver resultados correctos para todos los casos de prueba dentro de un minuto en una máquina razonable. (Este no es un límite completamente estricto, por lo que si su solución demora un minuto y diez segundos, está bien, pero si demora 3 minutos, no lo es. Un buen algoritmo los resolverá fácilmente en segundos).

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Ejemplos

Las soluciones no son únicas, por lo que puede obtener resultados diferentes.

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

Hasta donde yo sé, hay exactamente 4 soluciones para cada entrada donde el número de bloques es 0 mod 3, o 1 mod 3, y hay 0 o 16 soluciones donde es 2 mod 3.

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

Esta es la versión de golf del programa que escribí mientras discutía el problema con Martin.

La entrada es una lista a través de STDIN. La salida es una lista que representa la última solución encontrada si hay una solución, o cero si no la hay. Por ejemplo:

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

El puerto obligatorio. Gracias a @Jakube por el ahorro de 3 bytes.

El método de entrada es el mismo que el anterior, pruébelo en línea .

Explicación (¡larga y llena de lógica!)

Primero, dos observaciones básicas:

• Observación 1: no importa en qué orden toque los bloques

• Observación 2: si tocas un bloque 4 veces, es equivalente a tocarlo una vez

En otras palabras, si hay una solución, entonces hay una solución donde el número de toques está entre 0 y 3 inclusive.

Como el módulo 4 es muy bueno, hagámoslo también con los bloques. Para el resto de esta explicación, el nivel de bloque 0 es equivalente al nivel de bloque 4.

Ahora denotemos a[k]ser el nivel actual de bloque ky x[k]la cantidad de veces que tocamos el bloque ken una solución. Deje también nser el número total de bloques. Como ha notado @Jakube, una solución debe satisfacer:

  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

dónde C es el nivel final en el que terminan todos los bloques, entre 0 y 3 inclusive (recuerde que estamos tratando el nivel 4 como nivel 0) y todas las ecuaciones anteriores son realmente congruencias módulo 4.

Ahora aquí está la parte divertida:

• Observación 3 : Si existe una solución, existe una solución para cualquier nivel de bloque final 0 <= C <= 3.

Existen tres casos basados ​​en el número de bloques del módulo 3. La explicación para cada uno de ellos es la misma: para cualquier número de bloques, existe un subconjunto de bloques que, si toca cada uno de ellos una vez, aumenta todos los niveles de bloque en exactamente 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

Esto explica por qué hay 4 soluciones para 0 mod 3y 1 mod 3, y generalmente 16 soluciones para2 mod 3 . Si ya tiene una solución, tocar los bloques como se muestra arriba le da otra solución que termina en un nivel de bloque más alto (envolviendo).

Entonces, ¿qué significa esto? ¡Podemos elegir cualquier nivel de bloque final Cque queramos! Vamos a elegir C = 0, porque esto ahorra en bytes.

Ahora nuestras ecuaciones se convierten en:

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]

Y reorganizar:

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]

Entonces, lo que podemos ver es que, si lo hemos hecho x[0], podemos usar todas las ecuaciones, excepto la última, para descubrir las demás.x[k] . La última ecuación es una condición adicional que debemos verificar.

Esto nos da un algoritmo:

• Pruebe todos los valores para x[0]
• Usa las ecuaciones anteriores para resolver todas las demás x[k]
• Compruebe si se cumple la última condición. Si es así, guarde la solución.

Eso da la solución anterior.

Entonces, ¿por qué a veces no tenemos solución 2 mod 3? Echemos un vistazo a estos dos patrones nuevamente:

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

Ahora considere las ecuaciones en esas posiciones, es decir, para la primera:

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]

Añádelos:

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

Para el segundo:

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]

Agréguelos nuevamente:

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

Entonces, si (a[1] + a[4] + a[7] + a[10])y (a[0] + a[3] + a[6] + a[9])no son iguales, entonces no tenemos solución. Pero si son iguales, obtenemos 16 soluciones. Esto fue para el n = 11caso, pero por supuesto esto se generaliza a cualquier número que sea2 mod 3 : tome la suma de cada tercer elemento a partir del segundo y compárela con la suma de cada tercer elemento a partir del primero.

Ahora, finalmente, ¿es posible descubrir qué x[0]tiene que ser en lugar de probar todas las posibilidades? Después de todo, dado que restringimos nuestro nivel objetivo Ca 0, solo hay uno x[0]que da una solución en el caso 0 mod 3o 1 mod 3(as 4 solutions / 4 final levels = 1 solution for a specific final level).

¡La respuesta es sí! Podemos hacer esto para 0 mod 3:

 .X..X
.X..X.

Lo que se traduce en:

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]   /

Restando da:

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

Del mismo modo 1 mod 3, podemos hacer este patrón:

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

Lo que da:

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

Estos, por supuesto, se generalizan al extender los índices en incrementos de 3.

Porque 2 mod 3, dado que tenemos dos subconjuntos que cubren cada bloque, en realidad podemos elegir cualquiera x[0]. De hecho, esto es cierto para x[0], x[1], x[3], x[4], x[6], x[7], ...(básicamente cualquier índice no congruente con 2 mod 3, ya que no están cubiertos por ninguno de los subconjuntos).

Así que tenemos una forma de elegir un en x[0]lugar de probar todas las posibilidades ...

... pero la mala noticia es que esto no se guarda en 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

Pyth, 72 76 73 66 39 38 caracteres

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

edit 4: Realizado, que los cálculos Q[N]-Q[N+1]+solution[-3]yQ[-2]-Q[-1]+solution[-3] son ident. Por lo tanto, calculo en exceso la solución por 1, y filtro las soluciones, donde la última entrada es 0. Luego hago estallar la última entrada. Afortunadamente, los casos especiales no necesitan un tratamiento adicional con este enfoque. -27 caracteres

editar 3: Aplicar algunos trucos de golf de FryAmTheEggman: -7 personaje

editar 2: Usar filtro, reducir y mapear: -3 caracteres

editar 1: en mi primera versión no imprimí nada, si no había solución. No creo que esté permitido, por lo tanto, +4 personaje.

Espera una lista de enteros como entrada [1,4,2] y genera una solución válida [2,0,1]si hay una, de lo contrario, una lista vacía [].

Explicación:

Deje Qser la lista de 5 niveles yY la lista de la solución. Deben mantenerse las siguientes ecuaciones:

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

Por lo tanto, si usamos cualquiera Y0y Y1, podemos calcular Y2, Y3y Y4de la siguiente manera.

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

Que todos los niveles, excepto el último, son iguales (porque no usamos la ecuación = Q4 + Y3 + Y4. Para verificar, si este último también es igual a los otros niveles, simplemente podemos verificar si (Q3 - Q4 + Y2) mod 4 == 0. Observe que la parte izquierda sería el valor Y5Si calculo la sexta parte de la solución, simplemente puedo verificar si es cero.

En mi enfoque, simplemente itero sobre todos los inicios posibles ( [0,0], a [3,3]) y calculo la longitud (entrada) -1 entradas más y filtro todas las soluciones que terminan con un cero.

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

es básicamente lo siguiente:

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]

luego filtro estas posibles soluciones por otras válidas:

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

a esta lista de soluciones agrego una lista vacía, para que tenga al menos un elemento

 +....]Y

y tome la primera solución h, haga estallar el último elemento pe imprímalo

 Ph

Tenga en cuenta que esto también funciona si solo hay un bloque. En mi enfoque obtengo la posición inicial [0,0] y no la extiende. Como la última entrada es 0, imprime la solución [0].

El segundo caso especial (2 bloques) no es tan especial después de todo. No estoy seguro, por qué complicaba demasiado las cosas antes.

Ruby, 320 313 caracteres

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*''

Definitivamente se puede jugar más al golf. No genera nada para rompecabezas sin solución.

Versión sin golf:

#!/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 * ''

Bien, este fue divertido. Aquí está el algoritmo básico, con la {n}representación de n "touch" es en el número arriba del n, como se demuestra en uno de los ejemplos:

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

Me quedé perplejo por un momento aquí. ¿Cómo puedo convertir el 111...1110en una serie de mismos números? Así que comparé mi solución y la solución correcta (nota: todos los recuentos "táctiles" son uno mayor de lo que deberían ser porque la entrada está indexada en 1, mientras que la salida está indexada en 0):

3033233103233301320210
0330130000130202221111

Noté que cada número estaba uno lejos del correcto mod 4, así que los marqué con +s, -sy =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)

Eso funcionó por un tiempo, ¡hasta que me di cuenta de que a veces el resultado final era 111...11112o 11...1113también! Afortunadamente, la aplicación repetida de la fórmula mágica que no tiene sentido pero que funciona también los solucionó.

Entonces, ahí lo tienes. Un programa que comienza teniendo sentido, pero que se degrada y se vuelve más y más feo a medida que avanza. Muy típico para una solución de código de golf, creo. :)

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

MANIFESTACIÓN

Estoy seguro de que esto se puede jugar más golf ..

Aquí están los resultados de los casos de prueba:

[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]

El algoritmo primero se asegura de que los valores de todos los bloques, excepto el último bloque, sean los mismos (al iterar y agregar a los "recuentos táctiles" de todos los bloques excepto los primeros 2). Luego, si el número de bloques lo permite ( (num_of_blocks - 1) % 3 != 1), regresa y se asegura de que los valores del resto de los bloques coincidan con el último bloque. Imprime xsi no hay solución.