Twoim zadaniem jest więc wzięcie bloku 3x3, w którym -oznaczają puste miejsca i *średnie wypełnione miejsca, na przykład:

-**
-*-
*-*

i przestawiaj blok tak, *aby tworzył X, jak poniżej:

*-*
-*-
*-*

Wejście: kwadraty 3x3 jak wyżej, mogą to być 3 linie, tablica lub dowolnie.

Wyjście: Najkrótsza liczba ruchów, które można przestawić na X. Każdy ruch polega na odwróceniu 2 dotykających się znaków, które są względem siebie poziomo, pionowo od siebie lub ukośnie. Jeśli nie jest to możliwe, zwróć niemożliwe wyjście, na przykład 999lub -4242. 5jest najmniejszą taką liczbą.

Przypadki testowe:

1) Wyjście: 1

-**
-*-
*-*

2) Wyjście: -1

-*-
-*-
*-*

3) Wyjście: 3

---
-**
***

4) Wyjście: 0

*-*
-*-
*-*

Możesz zastąpić puste i niepuste znaki, ale pamiętaj, aby podać, który z nich jest w poście

Code Golf

Pamiętaj, to jest kod golfowy, który wygrywa najkrótszy kod!

Python 3 , 104 78 bajtów

lambda n:-(sum(n)!=5)or sum(n[1::2])+n[4]*(max(n,n[6:],n[::3],n[2::3])>=[1]*3)

Wypróbuj online!

Edycja: Zastosowano zarówno sugestie @Jonathan Allan, jak i @ xnor, aby drastycznie zmniejszyć liczbę bajtów.

Dane wejściowe to lista ciągów o długości 9 z zerami i jedynek, z których jednymi jest *s.

Oto kilka spostrzeżeń:

• Nigdy nie musimy przesuwać gwiazd już w odpowiednich komórkach. Każda źle umieszczona gwiazda ma 5 otaczających komórek, których nie można jednocześnie zablokować (w przeciwnym razie odpowiedź ma już wartość -1).
• Koszt każdej źle umieszczonej gwiazdy wynosi 1 lub 2 i wynosi 2 tylko wtedy, gdy jest otoczony trzema prawidłowo umieszczonymi gwiazdami.
• Koszt każdej źle umieszczonej gwiazdy jest od siebie niezależny.

Dlatego najpierw sprawdzamy, czy ciąg ma pięć, a następnie liczymy następujące rzeczy:

• Liczba źle umieszczonych gwiazd (= gwiazd o nieparzystych indeksach)
• Liczba niesłuszna gwiazd koszt 2 (= w komórkach 0124, 0346, 2458, 4678są jedynkami)
  • Uwzględnij n[4]jako jeden, a następnie przetestuj ekstrakcję dla każdego zakresu jako '111'.
  • Ponieważ taka gwiazda jest co najwyżej jedna, możemy bezpiecznie używać maxzamiast niej sum.

Galareta , 26 bajtów

5ḶḤd3ạŒ!Ṁ€€ḅ1Ṃ
T’d3Ç-L=5Ɗ?

Wypróbuj online!

Weź płaską listę jako dane wejściowe.

Szkoda, że ​​Jelly nie ma „wielowymiarowych prawdomównych wskaźników” ... T€ṭ€"JẎ również działa, ale zajmuje jeszcze 1 bajt.

Algorytm: Istnieje 5 bieżących pozycji bloku i 5 celów (miejsc docelowych), algorytm próbuje każdej z 5! dopasowanie i wyprowadzenie minimalnej sumy [źródła, celu] odległości Czebyszewa.

Haskell , 176 132 126 104 bajtów

w=0:1:w
m a|sum a/=5=5|1>0=sum$[a!!4|3<-sum.map(a!!)<$>[[0,1,2],[0,3,6],[2,5,8],[6,7,8]]]++zipWith(*)a w

Wypróbuj online!

Pobiera listę liczb całkowitych z 1 jako niepustym znakiem. Sumuje liczbę niezerowych kwadratów o indeksie parzystym, a następnie dodaje 1, jeśli zostanie znaleziony jeden z wzorów podwójnego ruchu (kwadrat środkowy i kolumna / rząd krawędzi całkowicie wypełnione). Ostatnia część jest trochę marnowana, myślę, że prawdopodobnie mogłaby zostać znacznie ulepszona w porównaniu z tą metodą brutalnej siły. Zwraca 5 (niemożliwe wyjście) przy niemożliwym wejściu.

Python 2 , 194 192 bajtów

from itertools import*
f=lambda l,k=0:-(sum(l)!=5)or[1,0]*4!=l[:-1]and k<4and-~min(f(l[:a]+[l[b]]+l[a+1:b]+[l[a]]+l[b+1:],k+1)for a,b in combinations(range(9),2)if max(b/3-a/3,abs(a%3-b%3))<2)

Wypróbuj online!

JavaScript (ES6), 123 bajty

Pobiera dane wejściowe jako 9-bitową liczbę całkowitą. Rozwiązuje zagadkę, naiwnie stosując zasady, co do których udowodniono, że nie jest najkrótszym podejściem.

f=(n,k=b=-1)=>n^341?k>2?b:[3,6,9,10,17,18,20,34,36].map(m=>[1,8,8].map(M=>(x=n&(m*=M))&-x^x||f(n^m,k+1)))|b:!~b|k<b?b=k+1:b

Wypróbuj online!

Skomentował

f = (                           // f = recursive function taking:
  n,                            //   n = input
  k =                           //   k = number of moves, initialized to -1
  b = -1                        //   b = best result so far, initialized to -1
) =>                            //
  n ^ 341 ?                     // if n does not match the target pattern:
    k > 2 ?                     //   if we've already done more than 3 moves:
      b                         //     we're not going to find a solution -> abort
    :                           //   else:
      [3,6,9,10,17,18,20,34,36] //     for each swap bitmask m
      .map(m =>                 //     and
      [1,8,8]                   //     for each multiplier M:
      .map(M =>                 //       apply the multiplier to m and
        (x = n & (m *= M))      //       apply the final bitmask to n -> this gives x
        & -x                    //       isolate the least significant bit of x
        ^ x ||                  //       if it's the only bit set,
        f(n ^ m, k + 1)         //       then swap the bits and make a recursive call
      )) | b                    //     end of both map() loops; return b
  :                             // else:
    !~b | k < b ? b = k + 1 : b //   this is a solution in k+1 moves: update b

Uwaga : ten kod wykonuje niektóre nielegalne ruchy poza górną część planszy, gdy m jest pomnożone przez 64. Ale są one po prostu ignorowane, ponieważ nie mogą prowadzić do rozwiązania krótszego niż najlepsze rozwiązanie legalne.

Poniżej znajduje się 9 podstawowych masek bitowych wymiany i wzorzec docelowy. Najważniejszy jest lewy górny róg.

000  000  001  001  010  010  010  100  100     101
011  110  001  010  001  010  100  010  100     010 (341)
(3)  (6)  (9)  (10) (17) (18) (20) (34) (36)    101

Galaretka , 26 bajtów

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ

Wypróbuj online!

Link monadyczny.

W jaki sposób?

Zainspirowany odpowiedzią Python Bubblera ; gra w golfa na miarę Jelly ...

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ - Link: length 9 list of ones & zeros, X
“ċȤ‘                       - list of code-page indices     = [232,154]
    Ḥ                      - double                        = [464,308]
     B                     - to binary     = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0]]
        $                  - last two links as a monad:
       U                   -   upend       = [[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
      ;                    -   concatenate = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0],[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
           ¥               - last two links as a dyad:
          a                -   logical AND (vectorises)
         =                 -   equal? (vectorises)
                Ɗ          - last three links as a monad:
             Ḋ             -   dequeue X (remove leftmost element)
               2           -   literal two
              m            -   modulo slice (keeps the "edge-elements") 
            ;              - concatenate
                 Ạ€        - all? for €ach (edge-elements: no-op
                           -                else: 1 for any cost-2 element 0 otherwise)
                   S       - sum
                    ɓ      - new dyadic chain ^that on the right; X on the left
                     S     - sum X
                       5   - literal five
                      n    - not equal?
                        N  - negate (-1 if not exactly 5 1s, 0 otherwise)
                         ȯ - logical OR with right

JavaScript, 85 bajtów

s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

To jest wyrażenie regularne odpowiedzi Bubblera .

Wprowadź jako ciąg 0/1.

f=
s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

document.write('<table>'+('<tr>'+'<td><label><input type=checkbox><span></span></label>'.repeat(3)).repeat(3)+'</table>');
document.write('Answer: <output id=o></output>');
U=()=>o.value=f(ii.map(i=>i.checked?1:0).join``);
ii=[...document.querySelectorAll('input')];
ii.forEach((i,p)=>{
i.checked=!(p%2);
i.oninput=U;
});
U()

label{display:block;position:relative;overflow:hidden;width:20px;height:20px;}
input{position:absolute;top:-200%;}
input~span{width:100%;height:100%;display:block;border:1px solid black;box-sizing:border-box;}
input:focus~span{border-color:red;}
input:checked~span{background:#ace;}

Stax , 23 22 bajtów

Ç╙╤Ü┤└åVτ┐├Y-²▼░█∩¡3ëâ

Uruchom i debuguj

Ten program pobiera tablicę [0, 1]jako dane wejściowe i zwraca całkowitą liczbę ruchów lub pusty ciąg, jeśli żadne rozwiązanie nie jest możliwe.

Rozważ te wskaźniki dla siatki

0 1 2
3 4 5
6 7 8

• Jeśli 1na wejściu nie ma dokładnie 5 s, to nie ma rozwiązania, więc nie produkujemy.
• Środkami każdej strony są nieprawidłowe pozycje. Są to wskaźniki 1, 3, 5 i 7. Zsumowanie odległości dla każdej 1z tych pozycji da wynik końcowy.
• Dla każdego 1w niewłaściwej pozycji jego odległość wynosi 1 lub 2. Będzie 2, jeśli jest otoczona przez inne 1s. Na przykład, jeśli istnieją 1indeksy [0, 1, 2, 4], to odległość dla niepoprawnego1 wynosi 2.

• Mając to na uwadze, rozważ ten pseudo-kod, aby uzyskać odległość przyczyniającą się do wyniku przez indeks 1.

  1. Odczytaj 4 bity z indeksów [1, 0, 2, 4]. To stawia nieprawidłową pozycję w najbardziej znaczącej pozycji.
  2. Konwertuj te bity na liczbę bod 0 do 15.
  3. Gdy 0 <= b <= 7odległość wynosi 0. Gdy 8 <= b <= 14odległość wynosi 1. Gdy b == 15odległość wynosi 2. Można to obliczyć za pomocą dzielenia liczb całkowitych przez b * 2 / 15.

Tak więc całkowitą odległość można obliczyć, powtarzając ten proces 4 razy i obracając siatkę pomiędzy nimi.

1#5=4*  if the number of 1s is 5, then 4, else 0
D       repeat the rest of the program that many times
  x     push the value in the x register, which is initially the input
  3/    split into 3 rows
  rM    rotate 90 degrees
  $X    flatten back into single array, and save the "rotated" array in the X register
  A|2E  get the digits of 2^10 i.e. [1,0,2,4]
  @     read the bits from the current rotation at indices [1,0,2,4]
  :b    convert bits to integer
  H15/  double, then divide by 2
  +     add to running total

Uruchom ten

Excel, 86 81 bajtów

=SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3))/(SUM(A1:C3)=5)

Stare: Kiedy wystąpił „niemożliwy” wynik-1

=IF(SUM(A1:C3)=5,SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3)),-1)

Używa 1wypełnionego i 0pustego wejścia w zakresie A1:C3. Można dalej grać w golfa, jeśli możemy zwrócić wartości inne niż -1„niemożliwe”. Zwraca a#DIV/0! błąd w niemożliwych siatkach

Działa na tej samej logice co odpowiedź Python Bubblera .