Connect 4: Spot the Fake!

35

Bank został włamany, a wszyscy lokalni bandyci mafii mają niezwykłe alibi: grali w Connect 4! Aby pomóc w dochodzeniu, należy napisać program do sprawdzania wszystkich zajętych plansz Connect 4, aby sprawdzić, czy pozycje rzeczywiście są pozycjami z ważnej gry Connect 4 i nie zostały pospiesznie poskładane jak tylko policja zapukała do drzwi.

Zasady łączenia 4: graczy Ri Yzmieniaj je, aby upuszczać kafelki ich koloru do kolumn siatki 7x6. Kiedy gracz upuszcza płytkę do kolumny, spada ona, aby zająć najniższą niewypełnioną pozycję w tej kolumnie. Jeśli graczowi uda się uzyskać na planszy poziomy, pionowy lub ukośny układ czterech płytek tego samego koloru, wówczas wygrywa i gra kończy się natychmiast.

Na przykład (z Ruruchomieniem) poniżej jest niemożliwa pozycja Connect 4.

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |R| | | | |
| | |Y| | | | |
|R| |Y| | | | |

Twój program lub funkcja musi pobrać płytę Connect 4 i zwrócić albo

  • Wartość falsy wskazująca, że ​​pozycja jest niemożliwa lub
  • Ciąg o numerach od 1 do 7, zawierającą jedną możliwą sekwencję ruchów prowadzące do tej pozycji (kolumny są ponumerowane 1się 7od lewej do prawej, a więc sekwencji 112, na przykład, oznacza czerwony ruch w kolumnie 1, a następnie za pomocą żółtego przenieść w kolumnie 1, a następnie czerwony ruch w kolumnie 2). Możesz wybrać numerację kolumny inną niż 1234567, jeśli chcesz, o ile podasz w swoim rozwiązaniu. Jeśli chcesz zwrócić listę w innym formacie; na przykład jako tablica [2, 4, 3, 1, 1, 3], to też jest w porządku, o ile łatwo jest zobaczyć, jakie są ruchy.

Możesz wybrać czytanie planszy w dowolnym rozsądnym formacie, w tym za pomocą liter innych niż Ri Ydla graczy, ale musisz określić, który gracz będzie pierwszy. Możesz założyć, że na planszy zawsze będzie 6x7, z dwoma graczami.

Możesz założyć, że pozycje, które otrzymujesz, są przynajmniej fizycznie możliwe do stworzenia na standardowej planszy Connect 4; tzn. że nie będzie żadnych „pływających” elementów. Możesz założyć, że tablica nie będzie pusta.

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź. Obowiązują standardowe luki.

Przykłady

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | | --> 1234567 (one possible answer)
| | | | | | | |
|R|Y|R|Y|R|Y|R|

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |R| | | | | --> false
| | |Y| | | | |
|R| |Y| | | | |

| | | | | | | |
| | |Y| | | | |
| | |R| | | | |
| | |Y| | | | | --> 323333 (only possible answer)
| | |R| | | | |
| |Y|R| | | | |

| | | | | | | |
| | | | | | | |
| | | | | | | |     
| | | | | | | | --> false (this is the position arising after
| |Y|Y|Y|Y| | |     the moves 11223344, but using those moves
| |R|R|R|R| | |     the game would have ended once R made a 4)

| | | | | | | |
| | | | | | | |
|Y| | | | | | |     
|R|Y| | | | | | --> 2134231211 (among other possibilities)
|R|R|Y| | | | |
|Y|R|R|Y| | | |

| | | | | | | |
| | | | | | | |
|Y| | | | | | |     
|R|Y| | | | | | --> false (for example, 21342312117 does not
|R|R|Y| | | | |     work, because Y has already made a diagonal 4)
|Y|R|R|Y| | |R|

| | | | | | | |
| | | | | | | |
| | | | | | | |     
| | | | | | | | --> 112244553 or similar
|Y|Y| |Y|Y| | |
|R|R|R|R|R| | |
John Gowers
źródło
John, z ciekawości, czy wiesz, czy istnieje algorytm nie-brutalnej siły?
Jonasz

Odpowiedzi:

9

Galaretka , 57 bajtów

ŒṪŒ!µ0ịŒṬ¬a³ZU,Ɗ;ŒD$€Ẏṡ€4Ḅo1%15;Ḋ€ṢṚ$Ƒƙ$Ȧȧœị³$2R¤ṁ$ƑµƇṪṪ€

Pobiera macierz, w której 0jest wypełniona, 1odtwarzana jako pierwsza i 2odtwarzana jako druga. Daje listę 1-indeksowanych kolumn, pustych, jeśli zidentyfikowano fałszywkę.

Wypróbuj online! (zbyt nieefektywny, aby uruchomić więcej niż 7 sztuk w mniej niż minutę)

Uwaga:

  1. Zakłada, że ​​nie ma żadnych elementów „pływających” (napraw to, przygotowując wcześniej ZṠṢ€Ƒȧdla +6 bajtów)
  2. Zakłada, że ​​pusta tablica jest fałszywa
Jonathan Allan
źródło
11

JavaScript (ES6),  202 194 187  183 bajtów

240

m=>(p=[...'5555555'],g=(c,s=o='')=>/2|4/.test(m)?['',0,2,4].some(n=>m.join``.match(`(1|3)(.{1${n}}\\1){3}`))?o:p.map((y,x)=>m[m[y][x]--^c||p[g(c^6,s+x,p[x]--),x]++,y][x]++)&&o:o=s)(2)

Wypróbuj online!

W jaki sposób?

g2413

Robiąc to, upewnia się, że nie będziemy mieli żadnego szeregu czterech kolejnych nieparzystych wartości, dopóki wszystkie parzyste wartości nie znikną (tzn. Jeśli strona wygra, musi to być ostatni ruch).

yxp[x]

Skomentował

m => (                            // m[] = input matrix
  p = [...'5555555'],             // p[] = next row for each column
  g = (c,                         // g = recursive function taking c = color,
          s = o = '') =>          //     s = current solution, o = final output
    /2|4/.test(m) ?               // if the matrix still contains at least a 2 or a 4:
      ['', 0, 2, 4]               //   see if we have four consecutive 1's or 3's
      .some(n =>                  //   by testing the four possible directions
        m.join``                  //   on the joined matrix, using
        .match(                   //   a regular expression where the number of characters
          `(1|3)(.{1${n}}\\1){3}` //   between each occurrence is either 1, 10, 12 or 14
        )                         //   (horizontal, diagonal, vertical, anti-diagonal)
      ) ?                         //   if we have a match:
        o                         //     abort and just return the current value of o
      :                           //   else:
        p.map((y, x) =>           //     for each cell at (x, y = p[x]):
          m[                      // 
            m[y][x]--             //       decrement the value of the cell
            ^ c ||                //       compare the original value with c
            p[                    //       if they're equal:
              g(                  //         do a recursive call with:
                c ^ 6,            //           the other color
                s + x,            //           the updated solution
                p[x]--            //           the updated row for this column
              ),                  //         end of recursive call
              x                   //         then:
            ]++,                  //         restore p[x]
            y                     //         and restore m[y][x]
          ][x]++                  //         to their initial values
        ) && o                    //     end of map(); yield o
    :                             // else:
      o = s                       //   we've found a solution: copy s to o
)(2)                              // initial call to g() with c = 2
Arnauld
źródło
Uwaga: Zapytałem „Czy możemy założyć, że pusta tablica nie zostanie podana jako dane wejściowe?” - jeśli będziemy musieli sobie z tym poradzić, twój kod będzie wymagał poprawki.
Jonathan Allan
nie wiem dlaczego, f([ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,2,0,2,0,0], [0,2,2,0,2,2,0], [1,1,1,1,1,1,1] ])kończy się 0 i f([ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,2,0,2,0,0], [2,2,2,0,2,2,1], [1,1,1,1,1,1,1] ])powinno być prawdą
Nahuel Fouilleul
@NahuelFouilleul Dziękujemy za zgłoszenie tego. Naprawiłem kod dodany dodałem te przypadki testowe.
Arnauld
2

Python 2 , 295 285 bajtów

def f(a):
 if 1-any(a):return[]
 p=sum(map(len,a))%2
 for i in R(7):
	if a[i][-1:]==`p`:
	 b=a[:];b[i]=b[i][:-1];L=f(b)
	 if L>1>(`1-p`*4in','.join([J((u[j]+' '*14)[n-j]for j in R(7))for n in R(12)for u in[b,b[::-1]]]+b+map(J,zip(*[r+' '*7for r in b])))):return L+[i]
R=range;J=''.join

Wypróbuj online!

-10 podziękowania dla Jo Kinga .

Dane wejściowe to lista ciągów znaków reprezentujących kolumny; z „1” dla czerwonego i „0” dla żółtego. Ciągi nie są wypełnione. Tak więc przypadek (falsey):

| | | | | | | |
| | | | | | | |
|Y| | | | | | |
|R|Y| | | | | |
|R|R|Y| | | | |
|Y|R|R|Y| | |R|

jest wprowadzany jako:

[
  '0110',
  '110',
  '10',
  '0',
  '',
  '',
  '1'
]

Dane wyjściowe to lista indeksów kolumn, indeksowanych 0, które mogłyby utworzyć tablicę; lub Nonejeśli nie jest poprawny.

Akceptuje pustą tablicę jako prawidłową (zwraca pustą listę []zamiast None).

To podejście jest rekurencyjne od ostatniego ruchu do pierwszego ruchu: na podstawie parytetu całkowitej liczby wykonanych ruchów usuwamy ostatni ruch czerwony lub ostatni ruch żółty (lub kończy się niepowodzeniem, jeśli nie jest to możliwe); sprawdź wynikową planszę, aby sprawdzić, czy przeciwnik ma 4 w rzędzie (w takim przypadku się nie powiedzie, ponieważ gra powinna już się zatrzymać); w przeciwnym razie powtarzaj się, dopóki tablica nie będzie pusta (co jest ważne).

Kod 4 w rzędzie jest najbardziej nadęty. Wszystkie ciągi diagonalne macierzy bsą generowane przez:

[
    ''.join(
        (u[j]+' '*14)[n-j] for j in range(7)
    )
    for u in[b,b[::-1]]for n in range(12) 
]

która najpierw wymienia przekątne „opadające”, a następnie „opadające”.

Chas Brown
źródło