Di arah teman-teman kami di Puzzling.SE , teka-teki berikut diposting: Apakah teka-teki berwarna ini selalu dapat dipecahkan? oleh Edgar G. Anda dapat memainkannya di sini .

Penjelasan teka-teki

Diberi m x nkisi dengan ubin dengan tiga warna berbeda, Anda dapat memilih dua ubin yang berdekatan , jika warnanya berbeda . Kedua ubin ini kemudian dikonversi ke warna ketiga, yaitu, satu warna yang tidak diwakili oleh dua ubin ini. Teka-teki diselesaikan jika semua ubin memiliki warna yang sama . Rupanya, seseorang dapat membuktikan bahwa teka-teki ini selalu dapat dipecahkan, jika tidak ada matau tidak ndapat dibagi oleh 3.

Tentu saja, ini memohon algoritma penyelesaian. Anda akan menulis fungsi atau program yang memecahkan teka-teki ini. Perhatikan bahwa fungsi dengan 'efek samping' (yaitu, output aktif stdoutdaripada dalam beberapa nilai pengembalian tipe data canggung) diizinkan secara eksplisit.

Input output

Input akan menjadi m x nmatriks yang terdiri dari bilangan bulat 1, 2dan 3(atau 0, 1, 2jika nyaman). Anda dapat mengambil input ini dalam format waras apa pun. Kedua mdan nyang >1dan tidak habis dibagi 3. Anda mungkin menganggap teka-teki yang tidak terpecahkan

Anda kemudian akan memecahkan teka-teki. Ini akan melibatkan pemilihan berulang dua ubin yang berdekatan untuk 'dikonversi' (lihat di atas). Anda akan menampilkan dua koordinat ubin ini untuk setiap langkah yang diambil algoritma penyelesaian Anda. Ini juga mungkin dalam format output yang waras. Anda bebas memilih antara pengindeksan berbasis 0 dan 1 berdasarkan koordinat Anda, dan apakah baris atau kolom diindeks terlebih dahulu. Tolong sebutkan ini dalam jawaban Anda.

Algoritme Anda harus berjalan dalam waktu yang wajar pada kasing 8x8 asli. Brute-forcing itu sepenuhnya dilarang secara eksplisit, yaitu algoritma Anda harus berjalan di bawah O(k^[m*(n-1)+(m-1)*n])dengan ksejumlah langkah yang diperlukan untuk solusi. Namun solusinya tidak harus optimal. Bukti yang diberikan dalam pertanyaan yang ditautkan dapat memberi Anda ide tentang bagaimana melakukan ini (misalnya, pertama-tama lakukan semua kolom hanya menggunakan petak yang berdekatan secara vertikal, lalu lakukan semua baris)

Uji kasus

Dalam kasus uji ini, koordinatnya berbasis 1 dan baris diindeks terlebih dahulu (seperti MATLAB / Oktaf dan mungkin banyak lainnya).

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]

Jika diinginkan, saya dapat memposting pastebin kasus uji yang lebih besar, tapi saya pikir ini sudah cukup.

Ruby, 266 byte

Lebih atau kurang hanya port dari solusi Oktaf, kecuali itu memecahkan baris terlebih dahulu bukan kolom. Input adalah larik array, dengan larik dalam menjadi baris. Keluaran bergerak adalah [row, column, row, column]. Suite uji

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

Tidak diganggu dengan penjelasan

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

Oktaf, 334 313 byte

Karena tantangannya mungkin tampak agak menakutkan, saya menghadirkan solusi saya sendiri. Saya tidak secara formal membuktikan bahwa metode ini bekerja (saya kira itu akan datang untuk membuktikan bahwa algoritma tidak akan pernah terjebak dalam satu lingkaran), tetapi sejauh ini ia bekerja dengan sempurna, melakukan 100x100 testcases dalam 15 detik. Perhatikan bahwa saya memilih untuk menggunakan fungsi dengan efek samping daripada yang mengembalikan semua koordinat karena itu menyelamatkan saya beberapa byte. Koordinat adalah baris-utama, berbasis 1, dan diformat sebagai row1 col1 row2 col2. Warna input 0,1,2karena ini bekerja lebih baik dengan mod, dengan biaya harus menggunakan numeldaripada nnz. Versi golf: Edit: menyimpan beberapa byte lagi dengan menggunakan teknik dari jawaban 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

Contoh GIF dari algoritma penyelesaian:

Versi tidak disatukan:

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

Peringatan Masih banyak pekerjaan sebelum saya selesai bermain golf ini! Saya harus bisa mengambilnya di bawah 500 Bytes, setidaknya. Untuk saat ini, ini solusi pertama yang berhasil, dan saya masih mengerjakannya.

Saya akan memberikan penjelasan lengkap setelah saya selesai.

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 byte

Sayangnya saya tidak bisa mengalahkan OP, tetapi untuk jawaban Rust saya cukup puas dengan bytecount.

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

Input: vektor angka serta jumlah kolom. Misalnya

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

output

 (row1,col1,row2,col2)

ke baris perintah.

Saya pertama-tama memecahkan setiap baris dan kemudian menyelesaikan kolom yang dihasilkan hanya sekali, tetapi mencetak langkah-langkah untuk semua kolom. Jadi sebenarnya cukup efisien :-P.

Dengan formating:

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

Sunting: sekarang mengembalikan warna solusi yang menyelamatkan saya titik koma ^^

Befunge , 197 368 696 754 Bytes

(ya, saya sedang melakukan beberapa kode golf terbalik, semakin banyak byte semakin baik)

Saya berpikir itu bisa menjadi tantangan untuk menulis algoritma ini di Befunge dan itu bisa menyenangkan

Saya ingin ini menjadi program komunitas, jadi jika ada yang ingin mengerjakannya, silakan lakukan.

Pada akhirnya, saya membuat semuanya sendirian sejauh ini, jadi saya akan menyelesaikannya sendiri (hampir selesai)

Apa yang sudah dilakukan: kode berbentuk 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\,"[ ":<        <

(Ya, itu troll, percayalah)

Pada dasarnya, ini membaca sebuah array dan menghitung langkah yang harus dilakukan untuk menyelesaikan baris, diberi input sebagai

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

(seluruh array dilewatkan sebagai daftar [row1, row2, row3, ...])

output adalah

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

baris dan cols keduanya dimulai pada 0.

Sekarang baris diselesaikan, hampir selesai! Hore!

Penjelasan: (akan diperbarui nanti)

Jadi ada 5 bagian utama:

• Yang pertama, berwarna hijau, membaca baris input dan menulis satu baris array
• Yang kedua, dalam warna oranye, beralih ke baris berikutnya dari array
• Yang ketiga, dengan warna biru, merangkum satu baris
• Yang keempat, dalam warna pink, mengambil modulus 3 dari jumlah, menyimpannya di sebelah kanan baris yang bersangkutan, dan pergi ke baris berikutnya
• Akhirnya, di bagian merah, bagian yang menghitung warna target dari angka yang dihitung sebelumnya. Bagian ini benar-benar bodoh dan mungkin harus ditulis ulang, tetapi saya tidak tahu bagaimana saya bisa melakukan itu dengan cara yang baik (diteruskan dari 197 byte menjadi 368 hanya dengan bagian itu)

Bagian abu-abu adalah inisialisasi

Berikut ini adalah penjelasan yang lebih dalam tentang modul yang menemukan kotak to untuk digabungkan (yang dikodekan di sini, by the way)

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

Bagian CALL adalah ketika penunjuk instruksi pergi ke modul lain, untuk menggabungkan ke kotak. Ia kembali ke modul ini melalui entri 'B'

Berikut adalah beberapa kode pseudo: (currentx terkait dengan membaca array) Untuk:

    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:

Perhatikan bahwa jika Anda ingin mengujinya, Anda harus meletakkan beberapa trailing space dan trailing baris baru sehingga ada cukup ruang untuk menyimpan array, jika Anda ingin menggunakan interpretasi yang saya tautkan. 22 + jumlah baris dalam input sebagai garis trailing, dan 34 + jumlah kolom sebagai spasi tambahan pada satu baris harus ok.

C, 404 byte

Golf kode pertama saya, saya cukup senang dengan hasilnya. Butuh waktu terlalu lama. Ini tidak sepenuhnya standar C, hanya apa pun yang akan dikompilasi di bawah gcc tanpa bendera khusus (dan mengabaikan peringatan). Jadi ada fungsi bersarang di sana. Fungsi fmengambil dimensi mdan nsebagai argumen pertama, dan karena argumen ketiga dibutuhkan mengambil (int pointer) ke array ukuran m× n(diindeks oleh baris pertama). Argumen lain adalah argumen dummy, Anda tidak perlu meneruskannya, mereka hanya di sana untuk menyimpan byte pada mendeklarasikan variabel. Ini menulis setiap pasangan berubah menjadi STDOUT dalam format row1,col1:row1,col1;, dengan tanda titik koma memisahkan pasangan. Menggunakan pengindeksan berbasis 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;}}

Saya menggunakan algoritma yang sedikit berbeda dari OP untuk memecahkan baris / kolom individu. Bunyinya seperti ini (kodesemu):

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)

The for(;~b;b--)mengeksekusi lingkaran tepat dua kali, di kedua pass memecahkan kolom bukannya baris. Ini dilakukan dengan menukar ndan m, dan mengubah nilai-nilai odan pyang digunakan dalam aritmatika pointer untuk mengatasi array.

Berikut adalah versi yang tidak dikenali, dengan tes utama, dan mencetak seluruh array setelah setiap gerakan (tekan enter untuk langkah 1 giliran):

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