O jogo BattleBlock Theatre ocasionalmente contém um quebra-cabeça que é uma versão generalizada de Lights Out . Você tem três blocos adjacentes, cada um dos quais indica um nível entre 1 e 4, inclusive com barras, por exemplo:

|
||||
||

Se você tocar em um bloco, esse bloco, assim como qualquer bloco adjacente, aumentará seu nível (retornando de 4 para 1). O quebra-cabeça é resolvido quando os três blocos mostram o mesmo nível (não importa em que nível). Como a ordem em que você toca os blocos não importa, denotamos uma solução pela frequência com que cada bloco é tocado. A solução ideal para a entrada acima seria 201:

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

O jogo generaliza muito facilmente qualquer número de blocos, embora para alguns números, nem todas as configurações sejam solucionáveis.

O desafio

Dada uma sequência de níveis de bloco, retorne com que frequência cada bloco precisa ser tocado para resolver o quebra-cabeça. Por exemplo, o exemplo acima seria dado como 142e poderia render 201como resultado. Se não houver solução, retorne uma saída consistente de sua escolha, que seja distinguível de todas as soluções em potencial, por exemplo, -1ou uma string vazia.

Você pode escrever uma função ou programa, receber entradas via STDIN, argumento de linha de comando ou argumento de função, em qualquer formato conveniente de lista ou string, e gerar saída similarmente através de um valor de retorno ou imprimindo em STDOUT.

Seu código deve retornar resultados corretos para todos os casos de teste dentro de um minuto em uma máquina razoável. (Esse não é um limite completamente estrito; portanto, se a sua solução demorar um minuto e dez segundos, tudo bem, mas se demorar 3 minutos, não será. Um bom algoritmo os resolverá facilmente em segundos.)

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Exemplos

As soluções não são exclusivas, portanto, você pode obter 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

Até onde eu sei, existem exatamente 4 soluções para cada entrada em que o número de blocos é 0 mod 3 ou 1 mod 3 e existem 0 ou 16 soluções em que é 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 é a versão básica do programa que escrevi enquanto discutia o problema com Martin.

Entrada é uma lista via STDIN. Saída é uma lista que representa a última solução encontrada, se houver uma solução, ou zero, se não houver. Por exemplo:

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

Pitão, 32 29 bytes

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

O porto obrigatório. Obrigado a @Jakube pela economia de 3 bytes.

O método de entrada é o mesmo que o anterior, tente online .

Explicação (longa e cheia de lógica!)

Primeiro, duas observações básicas:

• Observação 1: Não importa em qual ordem você toca nos blocos

• Observação 2: se você tocar em um bloco 4 vezes, é equivalente a tocá-lo uma vez

Em outras palavras, se houver uma solução, existe uma solução em que o número de toques está entre 0 e 3, inclusive.

Como o módulo 4 é tão bom, vamos fazer isso com os blocos também. Para o restante desta explicação, o nível de bloco 0 é equivalente ao nível de bloco 4.

Agora, vamos denotar a[k]o nível atual do bloco ke x[k]o número de vezes que tocamos kno bloco em uma solução. Também nseja o número total de blocos. Como o @Jakube observou, uma solução deve satisfazer:

  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

onde Cé o nível final em que todos os blocos terminam, entre 0 e 3, inclusive (lembre-se de que estamos tratando o nível 4 como nível 0) e todas as equações acima são realmente congruências no módulo 4.

Agora, aqui está a parte divertida:

• Observação 3 : Se existe uma solução, existe uma solução para qualquer nível de bloco final 0 <= C <= 3.

Existem três casos baseados no número de blocos do módulo 3. A explicação para cada um deles é a mesma - para qualquer número de blocos, existe um subconjunto de blocos que, se você tocar em um deles uma vez, aumenta todos os níveis de bloco em exatamente 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

Isso explica por que existem 4 soluções para 0 mod 3e 1 mod 3, e geralmente 16 soluções para 2 mod 3. Se você já possui uma solução, tocar nos blocos conforme descrito acima fornece outra solução que acaba em um nível mais alto de bloco (quebra automática).

Então o que isso quer dizer? Podemos escolher qualquer nível de bloco final Cque quisermos! Vamos escolher C = 0, porque isso economiza em bytes.

Agora nossas equações se tornam:

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]

E reorganize:

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]

Então, o que podemos ver é, se tivermos x[0], podemos usar todas as equações, exceto a última, para descobrir todas as outras x[k]. A última equação é uma condição adicional que devemos verificar.

Isso nos dá um algoritmo:

• Tente todos os valores para x[0]
• Use as equações acima para calcular todas as outras x[k]
• Verifique se a última condição foi atendida. Nesse caso, salve a solução.

Isso dá a solução acima.

Então, por que às vezes não temos solução 2 mod 3? Vamos dar uma olhada nesses dois padrões novamente:

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

Agora considere as equações nessas posições, ou seja, para a primeira:

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]

Adicione-os:

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

Para o 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]

Adicione-os novamente:

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

Portanto, se (a[1] + a[4] + a[7] + a[10])e (a[0] + a[3] + a[6] + a[9])não são iguais, não temos solução. Mas se forem iguais, obteremos 16 soluções. Foi o n = 11caso, mas é claro que isso se generaliza para qualquer número que seja 2 mod 3- pegue a soma de cada terceiro elemento começando no segundo e compare com a soma de cada terceiro elemento começando no primeiro.

Agora, finalmente, é possível descobrir o que x[0]deve ser em vez de tentar todas as possibilidades? Afinal, como restringimos nosso nível de destino Ca 0, existe apenas um x[0]que fornece uma solução no caso 0 mod 3ou 1 mod 3(as 4 solutions / 4 final levels = 1 solution for a specific final level).

A resposta é sim! Podemos fazer isso por 0 mod 3:

 .X..X
.X..X.

Que se traduz em:

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

Subtrair fornece:

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

Da mesma forma 1 mod 3, podemos fazer esse padrão:

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

Que dá:

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

É claro que eles generalizam estendendo os índices em incrementos de 3.

Pois 2 mod 3, como temos dois subconjuntos que cobrem todos os blocos, podemos escolher qualquer um x[0]. De fato, isso é verdade para x[0], x[1], x[3], x[4], x[6], x[7], ...(basicamente qualquer índice não congruente 2 mod 3, pois eles não são cobertos por nenhum subconjunto).

Portanto, temos uma maneira de escolher um em x[0]vez de tentar todas as possibilidades ...

... mas a má notícia é que isso não economiza em 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 caractere

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

editar 4: Realizado, que os cálculos Q[N]-Q[N+1]+solution[-3]e Q[-2]-Q[-1]+solution[-3]são ident. Portanto, eu supercalculo a solução em 1 e filtro as soluções, onde a última entrada é 0. Então eu pop a última entrada. Felizmente, os casos especiais não precisam de um tratamento extra com essa abordagem. -27 caracteres

edit 3: Aplicando alguns truques de golfe de FryAmTheEggman: -7 character

editar 2: Usando filtro, reduza e mapeie: -3 caracteres

edit 1: Na minha primeira versão, não imprimi nada, se não houvesse solução. Eu não acho que isso é permitido, portanto, +4 caracteres.

Espera uma lista de números inteiros como entrada [1,4,2]e gera uma solução válida [2,0,1]se houver uma, caso contrário, uma lista vazia [].

Explicação:

Let QSer a lista de 5 níveis e Ya lista da solução. As seguintes equações devem ser válidas:

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

Portanto, se usarmos any Y0e Y1, podemos calcular Y2, Y3e Y4da seguinte maneira.

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

Todos os níveis, exceto o último, são iguais (porque não usamos a equação = Q4 + Y3 + Y4. Para verificar, se esse último também é igual aos outros níveis, podemos simplesmente verificar se (Q3 - Q4 + Y2) mod 4 == 0. Observe que a parte esquerda seria o valor Y5Se eu calcular a sexta parte da solução, posso simplesmente verificar se é zero.

Na minha abordagem, simplesmente itero sobre todas as possíveis partidas ( [0,0], para [3,3]) e calculo o comprimento (entrada) -1 mais entradas e filtre todas as soluções que terminam com zero.

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

é basicamente o seguinte:

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]

então eu filtrei essas soluções possíveis para soluções válidas:

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

a esta lista de soluções, anexo uma lista vazia, para que ela tenha pelo menos um item

 +....]Y

e pegue a primeira solução h, coloque o último elemento pe imprima-o

 Ph

Observe que isso também funciona, se houver apenas um bloco. Na minha abordagem, recebo a posição inicial [0,0] e não a estendo. Como a última entrada é 0, ela imprime a solução [0].

O segundo caso especial (2 blocos) não é tão especial, afinal. Não sei por que complicou demais as coisas 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 pode ser jogado mais. Não produz nada para quebra-cabeças insolúveis.

Versão não destruída:

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

Ok, este foi divertido. Aqui está o algoritmo básico, com a {n}representação de n "touch" es no número acima de n, como demonstrado em um dos exemplos:

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

Fiquei perplexo um pouco aqui. Como transformar isso 111...1110em uma série dos mesmos números? Então, comparei minha solução e a solução correta (nota: o "toque" conta todos com um valor maior do que deveria porque a entrada é indexada 1, enquanto a saída é indexada 0:

3033233103233301320210
0330130000130202221111

Notei que cada número foi um longe o correto mod 4, por isso marcou-los com +s, -s e =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)

Isso funcionou por um tempo, até que percebi que às vezes o resultado final foi 111...11112ou 11...1113bem! Felizmente, aplicar repetidamente a fórmula mágica que não faz sentido, mas funciona também resolveu isso.

Então, aí está. Um programa que começa a fazer sentido, mas que se degrada cada vez mais como feio. Muito típico para uma solução de código de golfe, eu acho. :)

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

Tenho certeza de que isso pode ser jogado ainda mais ..

Aqui estão os resultados dos casos de teste:

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

O algoritmo primeiro garante que os valores de todos os blocos, exceto o último bloco, sejam os mesmos (iterando e adicionando às "contagens de toque" de todos os blocos, exceto os 2 primeiros). Então, se o número de blocos permitir ( (num_of_blocks - 1) % 3 != 1), volte e verifique se os valores do restante dos blocos correspondem ao último bloco. Imprime xse não houver solução.