Pecahkan puzzle berwarna

35

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.

8x8 puzzle tiga warna

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.

Sanchises
sumber
Saya ingin melihat versi tantangan kode ini, di mana tujuannya adalah untuk memecahkan serangkaian teka-teki dengan gerakan total paling sedikit.
Mego
@Mego, saya pasti mempertimbangkan ini. Namun, aku takut bahwa ini akan berubah menjadi DFS atau BFS yang akan membawa selamanya untuk menjalankan; atau, untuk mencegah hal ini, serangkaian pembatasan yang tidak jelas (seperti 'harus berjalan dalam satu jam' yang disukai orang-orang dengan komputer besar, atau yang akan mengharuskan saya untuk menguji semua solusi). Dan lebih jauh lagi, tantangan saat ini tidak memiliki jawaban, jadi saya ragu bahwa versi yang lebih sulit yang memerlukan heuristik dll akan terbukti lebih populer ... Tapi mungkin jika tantangan ini mengambil momentum saya dapat mengirimkan tantangan saudara seperti Anda menggambarkan.
Sanchises
Saya pikir saya akan mencoba melakukannya di Lua, tetapi mungkin lebih lama dari solusi 324 Bytes Anda ^^
Katenkyo
@Katenkyo Hanya ada satu cara untuk mengetahuinya! Saya menantikan untuk melihat solusi Anda.
Sanchises
Anda harus menunggu sedikit dengan sedih, Anda mencegah solusi brute-force jadi saya harus menemukan solusi yang pendek di lua: p
Katenkyo

Jawaban:

5

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)
Nilai Tinta
sumber
Menarik untuk melihat bahwa port antara dua bahasa non-golf masih dapat membuat perbedaan ~ 20%. Bisakah Anda menambahkan penjelasan singkat? (Terutama baris 3 - Saya diam-diam berharap saya dapat menggunakannya dalam jawaban saya karena intersectkata kunci ini sangat besar)
Sanchises
@menanamkan penjelasan telah ditambahkan. Mengenai intersect, saya tidak tahu apakah Anda dapat memperbaiki cara saya bekerja karena Ruby findpada dasarnya beroperasi pada fungsi, dan functionkata kunci Anda sama besar.
Nilai Tinta
Saya sebenarnya masih bisa menggunakan metode Anda untuk find- terima kasih! Tetap saja, tidak ada yang bisa mengalahkanmu ...
Sanchises
13

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:

masukkan deskripsi gambar di sini

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
Sanchises
sumber
Baru diketahui, tetapi nama saya bukan Kenny Lau ... itu adalah pengguna lain dan nama pengguna saya secara khusus menyatakan bahwa saya bukan Kenny
Value Ink
7

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
Katenkyo
sumber
5

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

bergerigis
sumber
5

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)

gambar

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.

Maliafo
sumber
Hanya ingin tahu, mengapa ini tidak bersaing?
Nilai Tinta
Karena bagian ini: 'Saya ingin ini menjadi program komunitas'. Saya pikir saya akan sedikit selingkuh kalau tidak
Maliafo
Saya memiliki hasil 197 Bytes, apakah Anda bekerja di bawah windows? (dan dihitung \r\nbukan \nhanya?)
Katenkyo
Hm, saya kira saya menyalin beberapa jejak saat menghitung byte, terima kasih
Maliafo
Jika pada akhirnya akulah satu-satunya yang membuatnya, aku akan menghapus menyebutkan, tapi aku harap aku tidak akan
Maliafo
2

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);
};
Norg74
sumber
Hanya ingin tahu: mengapa Anda memilih algoritma yang berbeda (dalam hal penghematan byte)?
Sanchises
1
Saya pikir ini lebih menarik ketika orang datang dengan solusi yang berbeda, dan dari beberapa tes cepat saya kira kedua metode akan hampir sama dalam hitungan byte. Saya mungkin akan mencoba algoritma Anda juga dan melihat apakah saya bisa lebih rendah.
Norg74
Posting ini di sini karena saya tidak punya cukup perwakilan untuk mengomentari pertanyaan. Apakah akan berlaku untuk brute force pada setiap baris, lalu setiap kolom secara terpisah? Itu secara teknis tidak "memaksa sepenuhnya" dan harus lebih rendah dari batasan kompleksitas waktu yang ditentukan. Saya sebenarnya mempertimbangkan untuk melakukan itu.
Norg74
Penyebutan yang kasar itu dimaksudkan untuk mengintensifkan ucapan 'waktu yang masuk akal', jadi lihatlah sebagai «O (...). Saya tahu ada area abu-abu antara brute force dan algoritma yang masuk akal, jadi gunakan penilaian Anda sendiri apakah Anda merasa itu bekerja untuk memecahkan teka-teki atau jika itu hanya sedikit modifikasi pada DFS atau BFS yang merupakan agnostik dari 'kemajuan'. .
Sanchises