Chez nos amis de Puzzling.SE , le puzzle suivant a été posté: Ce puzzle chromatique est-il toujours résoluble? par Edgar G. Vous pouvez y jouer ici .

Explication de puzzle

m x nAvec une grille avec des carreaux de trois couleurs différentes, vous pouvez sélectionner deux carreaux adjacents , si leurs couleurs sont différentes . Ces deux carreaux sont ensuite convertis en la troisième couleur, à savoir la couleur non représentée par ces deux carreaux. Le casse-tête est résolu si toutes les tuiles ont la même couleur . Apparemment, on peut prouver que ce puzzle est toujours soluble, si mni nest divisible par 3.

Bien sûr, cela demande un algorithme de résolution. Vous allez écrire une fonction ou un programme qui résout ce casse-tête. Notez que les fonctions avec des «effets secondaires» (c'est-à-dire que la sortie est activée stdoutplutôt que dans une valeur de retour de type de données peu pratique) sont explicitement autorisées.

Entrée sortie

L'entrée sera une m x nmatrice consistant en les nombres entiers 1, 2et 3(ou 0, 1, 2si cela convient). Vous pouvez prendre cette entrée dans n'importe quel format sain. Les deux met ne nsont >1pas divisibles par 3. Vous pouvez supposer que le casse-tête n’a pas été résolu

Vous allez ensuite résoudre le puzzle. Cela impliquera une sélection répétée de deux tuiles adjacentes à «convertir» (voir ci-dessus). Vous allez générer les deux coordonnées de ces tuiles pour chaque étape prise par votre algorithme de résolution. Cela peut aussi être dans n'importe quel format de sortie sain. Vous êtes libre de choisir entre l'indexation de vos coordonnées basée sur 0 et celle basée sur 1, et d'indiquer si les lignes ou les colonnes sont indexées en premier. Veuillez toutefois mentionner cela dans votre réponse.

Votre algorithme doit s'exécuter dans un délai raisonnable sur le boîtier 8x8 d'origine. Le brusquement forcé est explicitement interdit, c'est-à-dire que votre algorithme doit s'exécuter O(k^[m*(n-1)+(m-1)*n])avec kle nombre d'étapes nécessaire à la solution. La solution n’est cependant pas obligée d’être optimale. La preuve donnée dans la question liée peut vous donner une idée de la procédure à suivre (par exemple, commencez par faire toutes les colonnes en n'utilisant que des tuiles adjacentes verticalement, puis toutes les lignes).

Cas de test

Dans ces cas de test, les coordonnées sont basées sur 1 et les lignes sont indexées en premier (comme MATLAB / Octave et probablement beaucoup d'autres).

Input: 
[1 2]
Output: (result: all 3's)
[1 1],[1,2]


Input:
[ 1 2
  3 1 ]
Output: (result: all 1's)
[1 1],[2 1]        (turn left column into 2's)
[2 1],[2 2]        (turn right column into 3's)
[1 1],[1 2]        (turn top row into 1's)
[2 1],[2 2]        (turn bottom row into 1's)

Input:
[1 2 3 2
 3 2 1 1]

Output: (result: all 3's)
[1 1],[1 2] 
[1 3],[1 4] 
[1 2],[1 3] 
[1 1],[1 2] 
[1 2],[1 3] 
[1 1],[1 2]
[1 3],[1 4]
[2 1],[2 2]
[1 1],[2 1]
[1 2],[2 2]
[1 3],[2 3]
[1 4],[2 4]

Si vous le souhaitez, je peux poster une pâte contenant des cas de test plus volumineux, mais je pense que cela devrait suffire.

Ruby, 266 octets

Plus ou moins juste un port de la solution Octave, sauf qu'il résout d'abord les lignes au lieu des colonnes. L'entrée est un tableau de tableaux, les tableaux intérieurs étant les rangées. Les mouvements de sortie sont [row, column, row, column]. Suite de tests

->m{t=->v{v.size*v.inject(:+)%3}
s=->a,x,r{g=t[a]
(q=(r=0..a.size-2).find{|i|a[i]!=a[i+1]&&g!=a[i]}||r.find{|i|a[i]!=a[i+1]}
a[q,2]=[t[a[q,2]]]*2
p r ?[x,q,x,q+1]:[q,x,q+1,x])while[]!=a-[g]}
m.size.times{|i|s[m[i],i,1]}
m=m.shift.zip *m
m.size.times{|i|s[m[i],i,p]}}

Ungolfed avec explication

->m{                                  # Start lambda function, argument `m`
  t=->v{v.size*v.inject(:+)%3}        # Target color function
  s=->a,x,r{                          # Function to determine proper moves
                                      #   a = row array, x = row index, r = horizontal
    g=t[a]                            # Obtain target color
    (
      q=(r=0..a.size-2).find{|i|      # Find the first index `i` from 0 to a.size-2 where...
        a[i]!=a[i+1]                  # ...that element at `i` is different from the next...
        &&g!=a[i]                     # ...and it is not the same as the target color
      } || r.find{|i|a[i]!=a[i+1]}    # If none found just find for different colors
      a[q,2]=[t[a[q,2]]]*2            # Do the color flipping operation
      p r ?[x,q,x,q+1]:[q,x,q+1,x]    # Print the next move based on if `r` is truthy
    ) while[]!=a-[g]}                 # While row is not all the same target color, repeat
m.size.times{|i|                      # For each index `i` within the matrix's rows...
  s[m[i],i,1]                         # ...run the solving function on that row
                                      #   (`r` is truthy so the moves printed are for rows)
}
m=m.shift.zip *m                      # Dark magic to transpose the matrix
m.size.times{|i|s[m[i],i,p]}}         # Run the solving function on all the columns now
                                      #   (`r` is falsy so the moves printed are for columns)

Octave, 334 313 octets

Puisque le défi peut sembler un peu intimidant, je présente ma propre solution. Je n'ai pas prouvé formellement que cette méthode fonctionne (je suppose que cela reviendra à prouver que l'algorithme ne restera jamais bloqué dans une boucle), mais jusqu'à présent, cela fonctionne parfaitement, en effectuant 100x100 tests en 15 secondes. Notez que j'ai choisi d'utiliser une fonction avec des effets secondaires plutôt que celle qui renvoie toutes les coordonnées, car cela m'a sauvé quelques octets. Les coordonnées sont les lignes principales, les bases 1 et le format row1 col1 row2 col2. Couleurs d'entrée sont plus 0,1,2que cela fonctionne mieux avec mod, au prix d'avoir à utiliser numelplutôt que nnz. Version golfée: Édition: sauvegardé quelques octets supplémentaires en utilisant une technique de la réponse de Kevin Lau.

function P(p)
k=0;[m,n]=size(p);t=@(v)mod(sum(v)*numel(v),3);for c=1:n
p(:,c)=V(p(:,c));end
k=1;for r=1:m
p(r,:)=V(p(r,:));end
function a=V(a)
while any(a-(g=t(a)))
isempty(q=find(diff(a)&a(1:end-1)-g,1))&&(q=find(diff(a),1));
a([q q+1])=t(a([q q+1]));if k
disp([r q r q+1])
else
disp([q c q+1 c])
end;end;end;end

Exemple GIF de l'algorithme de résolution:

Version non-golfée:

function solveChromaticPuzzle(p)
[m,n]=size(p);                           % Get size
t=@(v)mod(sum(v)*numel(v),3);            % Target colour function
for c=1:n                                % Loop over columns
    p(:,c)=solveVec(p(:,c));             % Solve vector
end
for r=1:m                                % Loop over rows
    p(r,:)=solveVec(p(r,:));
end
    function a=solveVec(a)               % Nested function to get globals
        g=t(a);                          % Determine target colour
        while(any(a~=g))                 % While any is diff from target...
            % Do the finding magic. Working left-to-right, we find the
            % first pair that can be flipped (nonzero diff) that does not
            % have the left colour different from our goal colour
            q=min(intersect(find(diff(a)),find(a~=g)));
            if(isempty(q))               % In case we get stuck...
                q=find(diff(a),1);       % ... just flip the first possible
            end;
            a([q q+1])=t(a([q q+1]));    % Do the actual flipping.
            if(exist('r'))               % If we're working per row
                disp([r q r q+1])        % Print the pair, using global row
            else
                disp([q c q+1 c])        % Print the pari, using global col
            end
        end
    end
end

Lua, 594 575 559 octets

Attention Il reste encore beaucoup de travail avant que je ne termine ce golf! Je devrais pouvoir prendre moins de 500 octets, à tout le moins. Pour le moment, c'est la première solution qui a fonctionné, et j'y travaille encore.

Je vais fournir une explication complète une fois que j'ai terminé.

function f(t)s=#t a=","for i=1,s do p=t[i]for i=1,s
do p.Q=p.Q and p.Q+p[i]or p[i]end p.Q=(p.Q*#p)%3 for i=1,s do for j=1,#p-1 do
x=p[j]y=p[j+1]u=x~=y and(p.S and p.R==p.S or x~=p.Q)v=(x+y)*2p[j]=u and v%3or x
p[j+1]=u and v%3or y print(i..a..j,i..a..j+1)end
p.R=p.S p.S=table.concat(p)end end
for i=1,s do Q=Q and Q+t[i][1]or t[i][1]end Q=(Q*s)%3 for i=1,s
do for j=1,s-1 do p=t[j]q=t[j+1]x=p[1]y=q[1]u=x~=y and(S and R==S or x~=Q)v=(x+y)*2
for k=1,#p do p[k]=u and v%3or x q[k]=u and v%3or y
print(j..a..k,j+1..a..k)end Y=Y and Y..x or x end
R=S S=Y end end

Rouille, 496 495 octets

Malheureusement, je ne peux pas battre OP, mais pour une réponse de Rust, je suis assez satisfait du décompte.

let s=|mut v:Vec<_>,c|{
let p=|v:&mut[_],f,t|{
let x=|v:&mut[_],i|{
let n=v[i]^v[i+1];v[i]=n;v[i+1]=n;
for k in f..t+1{print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});}};
let l=v.len();let t=(1..4).find(|x|l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
let mut i=0;while i<l{let c=v[i];if c==t{i+=1;}else if c==v[i+1]{
let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};x(v,j);}else{x(v,i);}}t};
p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|{p(x,i,i)}).collect::<Vec<_>>(),0,c-1usize)};

Entrée: un vecteur de nombres ainsi que le nombre de colonnes. Par exemple

s(vec!{1,2,1,3},2);

les sorties

 (row1,col1,row2,col2)

à la ligne de commande.

Je résous d'abord toutes les lignes, puis la colonne résultante une seule fois, mais j'imprime les étapes pour toutes les colonnes. Donc c'est en fait assez efficace :-P.

Avec formater:

let s=|mut v:Vec<_>,c|{  
    let p=|v:&mut[_],f,t|{     // solves a single row/column
        let x=|v:&mut[_],i|{   // makes a move and prints it 
            let n=v[i]^v[i+1]; // use xor to calculate the new color
            v[i]=n;
            v[i+1]=n;
            for k in f..t{
                print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});
            }
        };
        let l=v.len();
        // find target color
        // oh man i am so looking forward to sum() being stabilized
        let t=(1..4).find(|x|(l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
        let mut i=0;
        while i<l{
            let c=v[i];
            if c==t{             // if the color is target color move on
                i+=1;
            }else if c==v[i+1]{ // if the next color is the same
                                // find the next possible move
                let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};
                x(v,j);
            }else{              // colors are different so we can make a move
                x(v,i);         
            }
        }
        t
    };
    // first solve all rows and than sovle the resulting column c times 
    p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|p(x,i,i)).collect::<Vec<_>>(),0,c-1usize)
};

Edit: renvoie maintenant la couleur de la solution qui me permet d'économiser un point-virgule ^^

Befunge , 197 368 696 754 octets

(oui, je fais du golf inversé, plus il y a d'octets, mieux c'est)

Je pensais que cela pourrait être un défi d'écrire cet algorithme dans Befunge et que ça pourrait être amusant

Je voudrais que ce soit un programme communautaire, alors si quelqu'un veut y travailler, je vous en prie, faites-le.

À la fin, j'ai tout fait seul jusqu'à présent, alors je vais finir tout seul (c'est presque fini)

Ce qui est encore fait: un code en forme de troll

&:19p&:09p:v:p94g92g90  <
 v94+1:g94&_$59g1+59p1-:|
 >p59gp1-: ^    vp95g93$<
v94\-1<v:g<     >  v
>g:1+v^_$v^90p94g92<
v5p94<   3>1+59p   ^
>9gg+\:^ %g   v93:g95<           v3_2         v
v1pg95g94<^95<>g-v>$v^           v ^-%3*2\gg9<
>9g39g+59g-1-|v-1_^ #^pg95+g92g90<1_09g:29g+5^
       ;  >  >  09g:29g+59gg\3%-# !^v         <
          ^p95<                  ^  <
     v  p96-1+g90g92<
     v                  p95_@
            >59g1+:39g-19g-^
     v    >p 79g:59gg\1+59gp$$$$$29g49pv
    > p59g^ |<<<<<<<<<<<<<<<<<<!-g96g94<
>:79^>29g49p>69g1+59gg49g:59gg\1+49p- v
^\-\6+gg95+1\g< v         !-g96:<-1g94_^
>"]",52*,::59g^v_::1+59gg\59gg-v^ <
^ .-g93g95,.-g<>:69g- v  v-g96:_1+^
>+" [,]",,,\29^       >#v_$:49g2-v
^1:.-g93g95,.-g92\,"[ ":<        <

(oui, c'est un troll, crois-moi)

Fondamentalement, il lit un tableau et calcule le mouvement à faire pour résoudre les lignes, en prenant une entrée comme

(number of rows) (number of columns) 1 2 3 1 1 3 2 1 2 ....

(tout le tableau est passé sous forme de liste [rangée1, rangée2, rangée3,…])

la sortie est

[col row],[col',row']
[col2 row2],[col2',row2']
...

les lignes et les colonnes commencent à 0.

Maintenant que les lignes sont résolues, c'est presque terminé! Hourra!

Explication: (sera mis à jour plus tard)

Donc, il y a 5 parties principales:

• Le premier, en vert, lit la ligne d’entrée et écrit une ligne du tableau.
• Le second, en orange, passe à la ligne suivante du tableau
• La troisième, en bleu, résume une rangée
• Le quatrième, en rose vif, prend le module 3 de la somme, l'enregistre à la droite de la ligne concernée et passe à la ligne suivante.
• Enfin, dans le rouge, la partie qui calcule la couleur cible à partir du nombre calculé précédemment. Cette partie est vraiment stupide et devrait probablement être réécrite, mais je n’ai pas compris comment je pouvais le faire de façon agréable (de 197 octets à 368 avec seulement cette partie)

Les parties grises sont des initialisations

Voici une explication plus détaillée du module qui trouve les cases à combiner (codé ici, au fait)

                                       B
            @                          v
            |                  !-g96g94<
ENTRY>29g49p>69g1+59gg49g:59gg\1+49p- v
                v         !-g96:<-1g94_^
               v_::1+59gg\59gg-v^ <
               >:69g- v  v-g96:_1+^
                      >#v_$:49g2-v
                    CALL<        <

La partie CALL est lorsque le pointeur d’instruction se dirige vers un autre module, à combiner à des cases. Il revient à ce module via l'entrée 'B'

Voici un pseudo-code: (currentx est lié à la lecture du tableau) Pour:

    69g1+59gg  // read target color
    49g:59gg\1+49p // read current color and THEN shift the currentx to the next box
    if ( top != top ){  // if the current color is bad
        49g1-          //  put the current place  (or currentx - 1) in the stack
        While:
            if ( :top != 69g ){   // if you didn't reach the end of the list
                ::1+              // copy twice, add 1
                if ( 59gg == \59gg ){ // if the next color is the same than current
                   1+                // iterate
                   break While;
                }
            }

        : // copies j (the previous raw iterator)
        if ( top == 69g ){  // if you reached the end of the row (which mean you can't swap with the color after that point)
            $:              // discard j's copy and copy target
            49g2-           // put the place just before the color change on the stack
            combine_with_next;
        } else {
            combine_with_next;
        }
        29g49p   // back to the beginning of the row (there was some changes int the row)
    }

    if ( 49g != 69g ) // if you didn't reach the end of the list
        break For:

Notez que si vous voulez le tester, vous devrez mettre un espace de fin et de nouvelles lignes afin qu'il y ait suffisamment d'espace pour stocker le tableau, si vous souhaitez utiliser le lien d' interprétation que j'ai lié. 22 + le nombre de lignes en entrée en tant que lignes de fin et 34 + le nombre de colonnes en tant qu'espaces de fin sur une ligne devraient être corrects.

C, 404 octets

Mon premier code de golf, je suis assez content de la façon dont cela s'est passé. A pris beaucoup trop de temps, cependant. Ce n'est pas complètement C standard, juste ce que compilera sous gcc sans drapeaux spéciaux (et ignorant les avertissements). Donc, il y a une fonction imbriquée là-dedans. La fonction fprend les dimensions met en ntant que son premier argument, et comme son troisième argument prend prend un (pointeur int) vers un tableau de taille m× n(indexé par les premières lignes). Les autres arguments sont des arguments factices, vous n'avez pas besoin de les transmettre, ils sont juste là pour économiser des octets lors de la déclaration de variables. Il écrit chaque paire modifiée dans STDOUT au format row1,col1:row1,col1;, le point-virgule séparant les paires. Utilise l'indexation basée sur 0.

#define A a[i*o+p
#define B A*c
f(m,n,a,i,j,o,p,b,c,d)int*a;{
int t(x){printf("%d,%d:%d,%d;",b?i:c+x,b?c+x:i,b?i:c+1+x,b?c+1+x:i);}
o=n;p=b=1;for(;~b;b--){
for(i=0;i<m;i++){c=j=0;
for(;j<n;)c+=A*j++];d=c*n%3;
for(j=0;j<n-1;j++) 
while(A*j]^d|A*j+p]^d){
for(c=j;B]==B+p];c++);
if(c<n-2&B]==d&2*(B+p]+A*(c+2)])%3==d)
B+p]=A*(c+2)]=d,t(1);else
B]=B+p]=2*(B]+B+p])%3,
t(0);}}o=m;p=m=n;n=o;o=1;}}

J'ai utilisé un algorithme légèrement différent de l'OP pour résoudre des lignes / colonnes individuelles. Cela ressemble à ceci (pseudocode):

for j in range [0, rowlength):
    while row[j] != targetCol or row[j+1] != targetCol:
        e=j
        while row[e] == row[e+1]:
            e++             //e will never go out of bounds
        if e<=rowLength-3 and row[e] == targetCol 
                and (row[e+1] != row[e+2] != targetCol):
            row.changeColor(e+1, e+2)
        else:
            row.changeColor(e, e+1)

La for(;~b;b--)boucle s'exécute exactement deux fois. Au deuxième passage, elle résout des colonnes au lieu de lignes. Ceci est effectué en échangeant net en mmodifiant les valeurs de oet pqui sont utilisées dans l'arithmétique de pointeur pour adresser le tableau.

Voici une version non golfée, avec un test principal, et imprime le tableau entier après chaque coup (appuyez sur enter pour l'étape 1 tour):

#define s(x,y)b?x:y,b?y:x
#define A a[i*o+p
#define B A*e
f(m,n,a,i,j,o,p,b,c,d,e)int*a;{

    int t(x){
        printf("%d,%d:%d,%d;\n",s(i,e+x),s(i,e+1+x));
        getchar();
        printf("\n");
        for(int i2=0;i2<(b?m:n);i2++){
            for(int j2=0;j2<(b?n:m);j2++){
                printf("%d ",a[i2*(b?n:m)+j2]);
            }
            printf("\n");
        }
        printf("\n");
    }

    printf("\n");
    b=1;
    for(int i2=0;i2<(b?m:n);i2++){
        for(int j2=0;j2<(b?n:m);j2++){
            printf("%d ",a[i2*(b?n:m)+j2]);
        }
        printf("\n");
    }
    printf("\n");

    o=n;p=1;
    for(b=1;~b;b--){
        for(i=0;i<m;i++){
            c=0;
            for(j=0;j<n;j++) c+= a[i*o+p*j];
            d=0;
            d = (c*n)%3;
            for(j=0;j<n-1;j++) {
                while(a[i*o+p*j]!=d||a[i*o+p*j+p]!=d){
                    for(e=j;a[i*o+p*e]==a[i*o+p*e+p];e++);
                    if(e<=n-3 && a[i*o+p*e]==d 
                            && 2*(a[i*o+p*e+p]+a[i*o+p*(e+2)])%3==d){
                        a[i*o+p*e+p]=a[i*o+p*(e+2)]=d;
                        t(1);
                    }else{
                        a[i*o+p*e]=a[i*o+p*e+p] = 2*(a[i*o+p*e]+a[i*o+p*e+p])%3;
                        t(0);
                    }
                }
            }
        }
        o=m;p=m=n;n=o;o=1;
    }
}

main(){
    int g[11][11] = 
    {
        {0,2,1,2,2,1,0,1,1,0,2},
        {2,1,1,0,1,1,2,0,2,1,0},
        {1,0,2,1,0,1,0,2,1,2,0},
        {0,0,2,1,2,0,1,2,0,0,1},
        {0,2,1,2,2,1,0,0,0,2,1},
        {2,1,1,0,1,1,2,1,0,0,2},
        {1,0,2,1,0,1,0,2,2,1,2},
        {0,0,2,1,2,0,1,0,1,2,0},
        {1,2,0,1,2,0,0,2,1,2,0},
        {2,1,1,0,1,1,2,1,0,0,2},
        {0,2,1,0,1,0,2,1,0,0,2},
    };
    #define M 4
    #define N 7
    int grid[M][N];
    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            grid[i][j] = g[i][j];
        }
    }
    f(M,N,grid[0],0,0,0,0,0,0,0,0);
};