Na temat naszych przyjaciół z Puzzling.SE opublikowano następującą łamigłówkę: Czy tę łamigłówkę chromatyczną zawsze można rozwiązać? autor: Edgar G. Możesz zagrać tutaj .

Wyjaśnienie puzzli

Biorąc pod uwagę m x nsiatkę z kafelkami trzech różnych kolorów, możesz wybrać dowolne dwa sąsiednie kafelki , jeśli ich kolory są różne . Te dwa kafelki są następnie konwertowane na trzeci kolor, tj. Na jeden kolor nie reprezentowany przez te dwa kafelki. Układanka jest rozwiązana, jeśli wszystkie płytki mają ten sam kolor . Najwyraźniej można udowodnić, że ta łamigłówka jest zawsze do rozwiązania, jeśli ani mnie nmożna podzielić przez 3.

Oczywiście wymaga to algorytmu rozwiązywania. Napiszę funkcję lub program, który rozwiązuje tę zagadkę. Zauważ, że funkcje z „efektami ubocznymi” (tj. Wyjście jest włączone, stdouta nie w niektórych niezręcznych wartościach zwracanych przez dane) są wyraźnie dozwolone.

Wejście wyjście

Wejście będzie m x nmacierz składa się z liczb całkowitych 1, 2i 3(lub 0, 1, 2jeśli jest to wygodniejsze). Możesz wziąć to wejście w dowolnym rozsądnym formacie. Zarówno ma nsą >1i nie jest podzielna przez 3. Można założyć puzzli nie jest rozwiązany

Następnie rozwiążesz zagadkę. Będzie to wymagało powtórnego wyboru dwóch sąsiadujących ze sobą płytek do „konwersji” (patrz wyżej). Będziesz generować dwie współrzędne tych płytek dla każdego kroku, który wykonał algorytm rozwiązywania. Może to być również dowolny rozsądny format wyjściowy. Możesz swobodnie wybierać między indeksowaniem współrzędnych w oparciu o 0 lub w oparciu o 1, a także o tym, czy wiersze lub kolumny są najpierw indeksowane. Proszę jednak o tym wspomnieć w swojej odpowiedzi.

Twój algorytm powinien działać w rozsądnym czasie na oryginalnej obudowie 8x8. Brutalne wymuszanie go całkowicie jest wyraźnie niedozwolone, tzn. Twój algorytm powinien działać zgodnie O(k^[m*(n-1)+(m-1)*n])z kliczbą kroków potrzebnych do rozwiązania. Jednak rozwiązanie nie musi być optymalne. Dowód podany w połączonym pytaniu może dać ci wyobrażenie, jak to zrobić (np. Najpierw zrób wszystkie kolumny, używając tylko sąsiadujących pionowo płytek, a następnie zrób wszystkie rzędy)

Przypadki testowe

W tych przypadkach testowych współrzędne są oparte na 1, a wiersze są najpierw indeksowane (jak MATLAB / Octave i prawdopodobnie wiele innych).

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]

W razie potrzeby mogę opublikować zestawienie większych przypadków testowych, ale myślę, że powinno to wystarczyć.

Rubinowy, 266 bajtów

Mniej więcej tylko port rozwiązania Octave, tyle że najpierw rozwiązuje wiersze zamiast kolumn. Dane wejściowe to tablica tablic, przy czym tablice wewnętrzne są wierszami. Ruchy wyjściowe są [row, column, row, column]. Zestaw testowy

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

Nie obeznany z wyjaśnieniem

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

Oktawa, 334 313 bajtów

Ponieważ wyzwanie może wydawać się nieco zniechęcające, przedstawiam własne rozwiązanie. Nie udowodniłem formalnie, że ta metoda działa (przypuszczam, że sprowadzi się to do udowodnienia, że ​​algorytm nigdy nie utknie w pętli), ale jak dotąd działa idealnie, wykonując 100x100 testów w ciągu 15 sekund. Zauważ, że wybrałem funkcję z efektami ubocznymi, a nie taką, która zwraca wszystkie współrzędne, ponieważ zaoszczędziło mi to kilka bajtów. Współrzędne są główne, oparte na 1 i sformatowane jako row1 col1 row2 col2. Kolory wejściowe są, 0,1,2ponieważ działa to lepiej mod, kosztem konieczności używania numelzamiast nnz. Wersja w golfa: Edycja: zapisano kilka kolejnych bajtów przy użyciu techniki z odpowiedzi Kevina 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

Przykład GIF algorytmu rozwiązywania:

Wersja bez golfa:

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 bajtów

Ostrzeżenie Przed golfem jest jeszcze wiele pracy! Powinienem być w stanie wziąć to co najmniej poniżej 500 bajtów. Na razie jest to pierwsze rozwiązanie, które zadziałało i wciąż nad tym pracuję.

Po zakończeniu przedstawię pełne wyjaśnienie.

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

Rdza, 496 495 bajtów

Niestety nie mogę pokonać OP, ale jeśli chodzi o odpowiedź Rust, jestem całkiem zadowolony z bajtu.

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

Wkład: wektor liczb oraz liczba kolumn. Na przykład

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

wyjścia

 (row1,col1,row2,col2)

do wiersza poleceń.

Najpierw rozwiązuję każdy wiersz, a następnie wynikową kolumnę tylko raz, ale drukuję kroki dla wszystkich kolumn. Jest to więc całkiem wydajne :-P.

Z formowaniem:

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

Edycja: teraz zwraca kolor rozwiązania, co oszczędza mi średnik ^^

Befunge , 197 368 696 754 bajtów

(tak, robię golf w odwrotnym kodzie, im więcej bajtów, tym lepiej)

Pomyślałem, że napisanie tego algorytmu w Befunge może być wyzwaniem i może być świetną zabawą

Chciałbym, aby był to program społecznościowy, więc jeśli ktoś chce nad tym popracować, zrób to.

W końcu wszystko zrobiłem do tej pory sam, więc skończę sam (prawie gotowe)

Co jeszcze zostało zrobione: kod w kształcie trolla

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

(tak, to troll, uwierz mi)

Zasadniczo czyta tablicę i oblicza ruch do rozwiązania wierszy, biorąc pod uwagę dane wejściowe jako

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

(cała tablica jest przekazywana jako lista [wiersz 1, wiersz 2, wiersz 3,…])

wyjście jest

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

wiersze i kolumny zaczynają się od 0.

Teraz, gdy rzędy są rozwiązane, prawie gotowe! Brawo!

Objaśnienie: (zostanie zaktualizowany później)

Jest więc 5 głównych części:

• Pierwszy, w kolorze zielonym, odczytuje linię wejściową i zapisuje jeden wiersz tablicy
• Drugi, w kolorze pomarańczowym, przechodzi do następnego rzędu tablicy
• Trzeci, niebieski, sumuje rząd
• Czwarty, w kolorze różowym, bierze moduł 3 sumy, zapisuje go po prawej stronie danego wiersza i przechodzi do następnego rzędu
• Wreszcie na czerwono część, która oblicza kolor docelowy na podstawie poprzednio obliczonej liczby. Ta część jest naprawdę głupia i prawdopodobnie powinna zostać przepisana, ale nie wymyśliłem, jak mogę to zrobić w przyjemny sposób (przekazane z 197 bajtów do 368 tylko tą częścią)

Szare części są inicjalizacjami

Oto głębsze objaśnienie modułu, który znajduje pola do połączenia (które są tutaj zakodowane)

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

Część CALL ma miejsce, gdy wskaźnik instrukcji przechodzi do innego modułu, aby połączyć się z ramkami. Wraca do tego modułu poprzez wpis „B”

Oto pseudo kod: (currentx jest powiązany z odczytem tablicy) Dla:

    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:

Zauważ, że jeśli chcesz go przetestować, będziesz musiał wstawić trochę miejsca na końcu i nowych linii, aby było wystarczająco dużo miejsca do przechowywania tablicy, jeśli chcesz użyć interpretacji, którą połączyłem. 22 + liczba wierszy na wejściu jako końcowe linie, a 34 + liczba kolumn jako końcowe spacje w jednym wierszu powinny być prawidłowe.

C, 404 bajty

Mój pierwszy golf w golfa, jestem całkiem zadowolony z tego, jak się okazało. Jednak trwało to o wiele za długo. Nie jest to w pełni standardowy C, tylko cokolwiek skompiluje się pod gcc bez specjalnych flag (i ignorując ostrzeżenia). Jest tam więc funkcja zagnieżdżona. Funkcja fprzyjmuje wymiary mi njako pierwsze argumenty, a jako trzeci argument przenosi (wskaźnik wewnętrzny) do tablicy o rozmiarze m× n(najpierw indeksowane wierszami). Pozostałe argumenty są fałszywymi argumentami, nie musisz ich przekazywać, są one po prostu, aby zaoszczędzić bajty na deklarowaniu zmiennych. Zapisuje każdą zmienioną parę do STDOUT w formacie row1,col1:row1,col1;, z średnikiem oddzielającym pary. Wykorzystuje indeksowanie 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;}}

Użyłem nieco innego algorytmu niż OP do rozwiązywania pojedynczych wierszy / kolumn. To idzie mniej więcej tak (pseudokod):

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)

W for(;~b;b--)Wykonuje pętla dokładnie dwa razy, przy drugim przejściu rozwiązuje kolumn zamiast wierszy. Odbywa się to poprzez zamianę ni moraz zmianę wartości oip które są wykorzystywane w celu rozwiązania arytmetyki wskaźnik tablicy.

Oto wersja, która nie jest golfem, z testową kartą główną i drukuje całą tablicę po każdym ruchu (naciśnij klawisz Enter, aby przejść do kroku 1):

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