Drüben bei unseren Freunden bei Puzzling.SE wurde das folgende Rätsel gestellt: Ist dieses chromatische Rätsel immer lösbar? von Edgar G. Sie können es spielen hier .

Puzzle Erklärung

Bei einem m x nRaster mit Kacheln mit drei verschiedenen Farben können Sie zwei benachbarte Kacheln auswählen , wenn ihre Farben unterschiedlich sind . Diese beiden Kacheln werden dann in die dritte Farbe konvertiert, dh die eine Farbe, die von diesen beiden Kacheln nicht dargestellt wird. Das Rätsel ist gelöst, wenn alle Kacheln die gleiche Farbe haben . Anscheinend kann man beweisen, dass dieses Rätsel immer lösbar ist, wenn es weder durch 3 teilbar mnoch nteilbar ist.

Dies erfordert natürlich einen Lösungsalgorithmus. Sie werden eine Funktion oder ein Programm schreiben, das dieses Rätsel löst. Beachten Sie, dass Funktionen mit 'Nebenwirkungen' (dh die Ausgabe ist aktiviert stdoutund nicht in einem unangenehmen Datentyp-Rückgabewert) ausdrücklich zulässig sind.

Input-Output

Die Eingabe wird eine sein , m x nMatrix , bestehend aus den ganzen Zahlen 1, 2und 3(oder 0, 1, 2wenn praktisch). Sie können diese Eingabe in jedem vernünftigen Format vornehmen. Beide mund nsind >1und nicht durch 3 teilbar. Sie können davon ausgehen, dass das Rätsel nicht gelöst ist

Sie lösen dann das Rätsel. Dies beinhaltet eine wiederholte Auswahl zweier benachbarter Kacheln, die „konvertiert“ werden sollen (siehe oben). Sie geben die beiden Koordinaten dieser Kacheln für jeden Schritt aus, den Ihr Lösungsalgorithmus ausgeführt hat. Dies kann auch in jedem vernünftigen Ausgabeformat erfolgen. Sie können zwischen einer 0-basierten und einer 1-basierten Indexierung Ihrer Koordinaten wählen und festlegen, ob Zeilen oder Spalten zuerst indexiert werden sollen. Bitte erwähnen Sie dies jedoch in Ihrer Antwort.

Ihr Algorithmus sollte innerhalb einer angemessenen Zeit auf dem ursprünglichen 8x8-Gehäuse ausgeführt werden. Brute-Forcing ist ausdrücklich untersagt, dh Ihr Algorithmus sollte O(k^[m*(n-1)+(m-1)*n])mit kder für die Lösung erforderlichen Anzahl von Schritten ausgeführt werden. Die Lösung muss jedoch nicht optimal sein. Der in der verknüpften Frage angegebene Beweis kann Ihnen eine Vorstellung davon geben, wie dies zu tun ist (z. B. zuerst alle Spalten unter Verwendung nur vertikal benachbarter Kacheln und dann alle Zeilen).

Testfälle

In diesen Testfällen sind die Koordinaten 1-basiert und die Zeilen werden zuerst indiziert (wie MATLAB / Octave und wahrscheinlich viele andere).

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]

Auf Wunsch kann ich einen Pastebin größerer Testfälle posten, aber ich denke, das sollte ausreichen.

Ruby, 266 Bytes

Mehr oder weniger nur ein Port der Octave-Lösung, mit der Ausnahme, dass zuerst Zeilen und nicht Spalten aufgelöst werden. Input ist ein Array von Arrays, wobei die inneren Arrays die Zeilen sind. Ausgangsbewegungen sind [row, column, row, column]. Testsuite

->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 mit Erklärung

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

Oktave, 334 313 Bytes

Da die Herausforderung etwas abschreckend wirken mag, präsentiere ich meine eigene Lösung. Ich habe formal nicht bewiesen, dass diese Methode funktioniert (ich vermute, das wird der Beweis sein, dass der Algorithmus niemals in einer Schleife hängen bleibt), aber bisher funktioniert es perfekt, 100x100 Testfälle innerhalb von 15 Sekunden durchzuführen. Beachten Sie, dass ich mich für eine Funktion mit Nebenwirkungen entschieden habe und nicht für eine, die alle Koordinaten zurückgibt, da ich dadurch einige Bytes gespart habe. Koordinaten sind zeilenweise, 1-basiert und wie folgt formatiert row1 col1 row2 col2. Eingabefarben sind, 0,1,2da dies besser funktioniert mod, auf Kosten der Verwendung numelund nicht nnz. Golf-Version: Bearbeiten: Mit einer Technik aus der Antwort von Kevin Lau wurden einige weitere Bytes gespeichert.

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

Beispiel GIF des Lösungsalgorithmus:

Ungolfed-Version:

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 Bytes

Warnung Es gibt noch viel Arbeit, bevor ich mit dem Golfen fertig bin! Zumindest sollte ich das unter 500 Bytes aushalten können. Im Moment ist es die erste Lösung, die funktioniert hat, und ich arbeite immer noch daran.

Ich werde eine vollständige Erklärung geben, sobald ich fertig bin.

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

Rust, 496 495 Bytes

Leider kann ich OP nicht schlagen, aber für eine Rust-Antwort bin ich mit dem bytecount ziemlich zufrieden.

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)};

Eingabe: ein Zahlenvektor sowie die Anzahl der Spalten. Z.B

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

Ausgänge

 (row1,col1,row2,col2)

zur Kommandozeile.

Ich löse zuerst jede Zeile und löse dann die resultierende Spalte nur einmal, aber drucke die Schritte für alle Spalten. Also ist es eigentlich recht effizient :-P.

Mit der Formatierung:

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)
};

Bearbeiten: gibt jetzt die Farbe der Lösung zurück, die mir ein Semikolon ^^ erspart

Befunge , 197 368 696 754 Bytes

(Ja, ich spiele Reverse Code Golf, je mehr Bytes desto besser)

Ich dachte, es könnte eine Herausforderung sein, diesen Algorithmus in Befunge zu schreiben, und es könnte Spaß machen

Ich möchte, dass es sich um ein Community-Programm handelt. Wenn also jemand daran arbeiten möchte, tun Sie dies bitte.

Am Ende habe ich alles alleine gemacht, also werde ich alleine fertig (es ist fast fertig)

Was ist schon erledigt: ein trollförmiger Code

&: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\,"[ ":<        <

(Ja, es ist ein Troll, glaub mir)

Grundsätzlich liest es ein Array und berechnet die auszuführende Bewegung, um die Zeilen zu lösen, wenn eine Eingabe wie folgt erfolgt

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

(Das gesamte Array wird als Liste übergeben [Zeile1, Zeile2, Zeile3,…])

Ausgabe ist

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

Zeilen und Spalten beginnen beide bei 0.

Nun, da die Reihen gelöst sind, ist es fast geschafft! Hurra!

Erläuterung: (wird später aktualisiert)

Es gibt also 5 Hauptteile:

• Die erste Zeile in Grün liest die Eingabezeile und schreibt eine Zeile des Arrays
• Die zweite Zeile in Orange wechselt zur nächsten Zeile des Arrays
• Der dritte im Blau summiert eine Reihe
• Der vierte, in Pink, nimmt den Modul 3 der Summe, speichert ihn rechts von der betreffenden Reihe und geht zur nächsten Reihe
• Im roten Bereich schließlich der Teil, der die Zielfarbe aus der zuvor berechneten Zahl berechnet. Dieser Teil ist wirklich dumm und sollte wahrscheinlich umgeschrieben werden, aber ich habe nicht herausgefunden, wie ich das auf nette Weise machen kann (von 197 Bytes auf 368 mit nur diesem Teil)

Graue Teile sind Initialisierungen

Hier ist eine tiefere Erklärung des Moduls, das die zu kombinierenden to-Boxen findet (was hier übrigens codiert ist).

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

Der CALL-Teil ist, wenn der Befehlszeiger auf ein anderes Modul zeigt, um es zu Boxen zu kombinieren. Über den Eintrag 'B' gelangt man zu diesem Modul zurück

Hier ist ein Pseudocode: (currentx bezieht sich auf das Lesen des Arrays) Für:

    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:

Beachten Sie, dass Sie, wenn Sie es testen möchten, nachgestellte Leerzeichen und neue Zeilen einfügen müssen, damit genügend Speicherplatz für das Array vorhanden ist, wenn Sie das von mir verknüpfte Interpret verwenden möchten . 22 + die Anzahl der Zeilen in der Eingabe als abschließende Zeilen und 34 + die Anzahl der Spalten als abschließende Leerzeichen in einer Zeile sollten in Ordnung sein.

C 404 Bytes

Mein erster Code Golf, ich bin ziemlich zufrieden mit dem Ergebnis. Hat aber viel zu lange gedauert. Es ist nicht das Standard-C, sondern alles, was unter gcc ohne spezielle Flags kompiliert wird (und Warnungen ignoriert). Es gibt also eine verschachtelte Funktion. Die Funktion verwendet fdie Dimensionen mund nals erstes Argument und als drittes Argument einen (int-Zeiger) auf ein Array der Größe m× n(zuerst durch Zeilen indiziert). Die anderen Argumente sind Dummy-Argumente. Sie müssen nicht übergeben werden. Sie dienen nur dazu, Byte beim Deklarieren von Variablen zu sparen. Jedes geänderte Paar wird im Format in STDOUT geschrieben row1,col1:row1,col1;, wobei die Paare durch ein Semikolon getrennt werden. Verwendet eine 0-basierte Indizierung.

#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;}}

Ich habe einen etwas anderen Algorithmus als OP zum Lösen einzelner Zeilen / Spalten verwendet. Es geht ungefähr so ​​(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)

Die for(;~b;b--)Schleife wird genau zweimal ausgeführt und löst beim zweiten Durchgang Spalten anstelle von Zeilen. Dies geschieht durch Vertauschen nund mÄndern der Werte von ound, pdie in der Zeigerarithmetik zur Adressierung des Arrays verwendet werden.

Hier ist eine Version, die mit einem Test-Main ungolfed ist und das gesamte Array nach jeder Bewegung druckt (drücken Sie die Eingabetaste, um Schritt 1 zu machen):

#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);
};