Le jeu BattleBlock Theatre contient parfois un puzzle qui est une version généralisée de Lights Out . Vous avez trois blocs adjacents, chacun indiquant un niveau entre 1 et 4 inclus avec des barres, par exemple:

|
||||
||

Si vous touchez un bloc, ce bloc ainsi que tout bloc adjacent augmentera son niveau (retour de 4 à 1). Le casse-tête est résolu lorsque les trois blocs affichent le même niveau (peu importe le niveau). Étant donné que l'ordre dans lequel vous touchez les blocs n'a pas d'importance, nous désignons une solution selon la fréquence à laquelle chaque bloc est touché. La solution optimale pour l'entrée ci-dessus serait 201:

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

Le jeu généralise très facilement n'importe quel nombre de blocs, bien que pour certains nombres, toutes les configurations ne soient pas résolubles.

Le défi

Étant donné une séquence de niveaux de blocs, indiquez à quelle fréquence chaque bloc doit être touché pour résoudre le puzzle. Par exemple, l'exemple ci-dessus serait donné en tant que 142et pourrait donner 201en conséquence. S'il n'y a pas de solution, renvoyez une sortie cohérente de votre choix, qui se distingue de toutes les solutions potentielles, par exemple, -1ou une chaîne vide.

Vous pouvez écrire une fonction ou un programme, prendre une entrée via STDIN, un argument de ligne de commande ou un argument de fonction, dans n'importe quel format de liste ou de chaîne pratique, et également sorti via une valeur de retour ou en imprimant sur STDOUT.

Votre code doit renvoyer des résultats corrects pour tous les cas de test dans une minute sur une machine raisonnable. (Ce n'est pas une limite complètement stricte, donc si votre solution prend une minute et dix secondes, c'est bien, mais si cela prend 3 minutes, ce n'est pas le cas. Un bon algorithme les résoudra facilement en quelques secondes.)

Il s'agit du code golf, donc la réponse la plus courte (en octets) l'emporte.

Exemples

Les solutions ne sont pas uniques, vous pouvez donc obtenir des résultats différents.

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

Pour autant que je sache, il y a exactement 4 solutions pour chaque entrée où le nombre de blocs est 0 mod 3, ou 1 mod 3, et il y a 0 ou 16 solutions où il est 2 mod 3.

Python 2, 115 octets

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

Ceci est la version golfée du programme que j'ai écrit en discutant du problème avec Martin.

L'entrée est une liste via STDIN. La sortie est une liste représentant la dernière solution trouvée s'il y a une solution, ou zéro s'il n'y en a pas. Par exemple:

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

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

Le port obligatoire. Merci à @Jakube pour la sauvegarde de 3 octets.

La méthode de saisie est la même que ci-dessus, essayez-la en ligne .

Explication (longue et pleine de logique!)

Tout d'abord, deux observations de base:

• Observation 1: Peu importe l'ordre dans lequel vous touchez les blocs

• Observation 2: Si vous touchez un bloc 4 fois, c'est équivalent à le toucher une fois

En d'autres termes, s'il existe une solution, il existe une solution où le nombre de touches est compris entre 0 et 3 inclus.

Puisque modulo 4 est si agréable, faisons-le aussi avec les blocs. Pour le reste de cette explication, le niveau de bloc 0 est équivalent au niveau de bloc 4.

Désignons maintenant a[k]le niveau actuel de bloc ket x[k]le nombre de fois où nous touchons le bloc kdans une solution. Soit négalement le nombre total de blocs. Comme l'a noté @Jakube, une solution doit satisfaire:

  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

où Cest le niveau final sur lequel se trouvent tous les blocs, entre 0 et 3 inclus (rappelez-vous que nous traitons le niveau 4 comme le niveau 0) et toutes les équations ci-dessus sont vraiment des congruences modulo 4.

Voici maintenant la partie amusante:

• Observation 3 : Si une solution existe, une solution existe pour tout niveau de bloc final 0 <= C <= 3.

Il y a trois cas basés sur le nombre de blocs modulo 3. L'explication pour chacun d'eux est la même - pour n'importe quel nombre de blocs, il existe un sous-ensemble de blocs qui, si vous touchez chacun d'eux une fois, augmente tous les niveaux de bloc de exactement 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

Cela explique pourquoi il existe 4 solutions pour 0 mod 3 et 1 mod 3, et généralement 16 solutions pour 2 mod 3. Si vous avez déjà une solution, toucher les blocs comme ci-dessus donne une autre solution qui se retrouve à un niveau de bloc plus élevé (enroulant autour).

Qu'est-ce que cela signifie? Nous pouvons choisir n'importe quel niveau de bloc final que Cnous voulons! Choisissons C = 0, car cela économise des octets.

Maintenant, nos équations deviennent:

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]

Et réorganisez:

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]

Donc, ce que nous pouvons voir, si nous avons x[0] , nous pouvons utiliser toutes les équations, sauf la dernière, pour découvrir toutes les autresx[k] . La dernière équation est une condition supplémentaire que nous devons vérifier.

Cela nous donne un algorithme:

• Essayez toutes les valeurs pour x[0]
• Utilisez les équations ci-dessus pour calculer toutes les autres x[k]
• Vérifiez si la dernière condition est remplie. Si oui, enregistrez la solution.

Cela donne la solution ci-dessus.

Alors pourquoi n'obtenons-nous parfois aucune solution 2 mod 3? Examinons à nouveau ces deux modèles:

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

Considérons maintenant les équations à ces positions, c'est-à-dire pour la première:

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]

Additionnez-les:

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

Pour le second:

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]

Ajoutez-les à nouveau:

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

Donc, si (a[1] + a[4] + a[7] + a[10])et (a[0] + a[3] + a[6] + a[9])ne sont pas égaux, nous n'avons pas de solution. Mais s'ils sont égaux, nous obtenons 16 solutions. C'était le n = 11cas, mais bien sûr, cela se généralise à tout nombre qui est2 mod 3 - prendre la somme de chaque troisième élément à partir du deuxième, et comparer à la somme de chaque troisième élément à partir du premier.

Maintenant enfin, est-il possible de comprendre ce qui x[0]doit être au lieu d'essayer toutes les possibilités? Après tout, puisque nous avons limité notre niveau cible Cà 0, il n'y en a qu'un x[0]qui donne une solution dans le cas 0 mod 3ou 1 mod 3(as 4 solutions / 4 final levels = 1 solution for a specific final level).

La réponse est oui! Nous pouvons le faire pour 0 mod 3:

 .X..X
.X..X.

Ce qui se traduit par:

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

La soustraction donne:

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

De même pour 1 mod 3nous pouvons faire ce modèle:

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

Qui donne:

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

Celles-ci se généralisent bien sûr en étendant les indices par incréments de 3.

Car 2 mod 3, puisque nous avons deux sous-ensembles qui couvrent chaque bloc, nous pouvons en choisir n'importe lequel x[0]. En fait, cela est vrai pour x[0], x[1], x[3], x[4], x[6], x[7], ...(essentiellement tout indice non conforme 2 mod 3, car ils ne sont couverts par aucun des sous-ensembles).

Nous avons donc un moyen de choisir un x[0]au lieu d'essayer toutes les possibilités ...

... mais la mauvaise nouvelle est que cela n'économise pas sur les octets (124 octets):

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 caractères

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

edit 4: Réalisé, que les calculs Q[N]-Q[N+1]+solution[-3]et Q[-2]-Q[-1]+solution[-3]sont ident. Par conséquent, je sur-calcule la solution par 1 et filtre les solutions, où la dernière entrée est 0. Ensuite, j'éclate la dernière entrée. Heureusement, les cas spéciaux n'ont pas besoin d'un traitement supplémentaire avec cette approche. -27 caractères

edit 3: Application de quelques astuces de golf de FryAmTheEggman: -7 caractère

modifier 2: Utiliser le filtre, réduire et mapper: -3 caractère

modifier 1: Dans ma première version, je n'ai rien imprimé, s'il n'y avait pas de solution. Je ne pense pas que ce soit autorisé, donc +4 caractère.

Attend une liste d'entiers en entrée [1,4,2]et génère une solution valide [2,0,1]s'il y en a une, sinon une liste vide[] .

Explication:

Soit Qla liste des 5 niveaux et Yla liste de la solution. Les équations suivantes doivent être respectées:

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

Par conséquent, si nous utilisons tout Y0et Y1, nous pouvons calculer Y2, Y3et Y4de la manière suivante.

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

Que tous les niveaux sauf le dernier sont égaux (parce que nous n'avons pas utilisé l'équation = Q4 + Y3 + Y4. Pour vérifier, si ce dernier est également égal aux autres niveaux, nous pouvons simplement vérifier si (Q3 - Q4 + Y2) mod 4 == 0. Remarquez que la partie gauche serait la valeur Y5Si je calcule la 6e partie de la solution, je peux simplement vérifier si elle est nulle.

Dans mon approche, je répète simplement tous les départs possibles ( [0,0], à [3,3]) et calcule la longueur (entrée) -1 entrées supplémentaires et filtre toutes les solutions qui se terminent par un zéro.

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

il s'agit essentiellement des éléments suivants:

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]

puis je filtre ces solutions possibles pour des solutions valides:

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

à cette liste de solutions j'ajoute une liste vide, pour qu'elle contienne au moins un élément

 +....]Y

et prenez la première solution h, éclatez le dernier élément pet imprimez-le

 Ph

Notez que cela fonctionne également s'il n'y a qu'un seul bloc. Dans mon approche, j'obtiens la position de départ [0,0] et ne la prolonge pas. Comme la dernière entrée est 0, il imprime la solution [0].

Le deuxième cas spécial (2 blocs) n'est pas si spécial après tout. Je ne sais pas pourquoi j'ai trop compliqué les choses plus tôt.

Rubis, 320 313 caractères

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

Peut certainement être joué au golf plus. Ne produit rien pour les puzzles insolubles.

Version non golfée:

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

D'accord, celui-ci était amusant. Voici l'algorithme de base, avec {n}représentant n "touch" es sur le nombre au-dessus de n, comme démontré sur l'un des exemples:

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

Je suis resté perplexe un peu ici. Comment puis-je transformer le 111...1110en une série de mêmes chiffres? J'ai donc comparé ma solution et la bonne solution (remarque: le nombre de "touch" est un supérieur à ce qu'il devrait être car l'entrée est indexée 1, tandis que la sortie est indexée 0):

3033233103233301320210
0330130000130202221111

J'ai remarqué que chaque numéro était éloigné de un du bon mod 4, alors je les ai marqués avec +s, -s et =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)

Cela a fonctionné pendant un certain temps, jusqu'à ce que je remarque que parfois le résultat final était 111...11112ou 11...1113aussi! Heureusement, l'application répétée de la formule magique qui n'a aucun sens mais qui fonctionne a également trié ces problèmes.

Alors voilà. Un programme qui commence à avoir du sens, mais se dégrade en hackiness de plus en plus laid au fur et à mesure. Je pense que c'est assez typique d'une solution de golf à code. :)

Python 2, 294 289 285 281 273 octets

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

Je suis sûr que cela peut être joué plus loin ..

Voici les résultats des cas de test:

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

L'algorithme s'assure d'abord que les valeurs de tous les blocs, à l'exception du dernier bloc, sont les mêmes (en itérant et en ajoutant au "nombre de contacts" de tous les blocs sauf les 2 premiers). Ensuite, si le nombre de blocs le permet ( (num_of_blocks - 1) % 3 != 1), revient en arrière et s'assure que les valeurs des autres blocs correspondent au dernier bloc. Imprime xs'il n'y a pas de solution.