Ligue 4: Descubra os Falsos!

35

O banco foi invadido e todos os bandidos da máfia local têm um álibi incomum: eles estavam em casa jogando o Connect 4! Para ajudar na investigação, você é solicitado a escrever um programa para validar todas as placas do Connect 4 que foram confiscadas para verificar se as posições são de fato posições de um jogo válido do Connect 4 e não foram montadas às pressas assim que a polícia bateu na porta.

As regras para conectar 4: jogadores Re Yrevezar-se para soltar peças de sua cor em colunas de uma grade 7x6. Quando um jogador coloca um ladrilho na coluna, ele cai para ocupar a posição mais baixa não preenchida nessa coluna. Se um jogador conseguir obter uma sequência horizontal, vertical ou diagonal de quatro peças de sua cor no tabuleiro, ele vence e o jogo termina imediatamente.

Por exemplo (com Rpartida), a seguir é uma posição impossível do Connect 4.

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

Seu programa ou função deve receber uma placa Connect 4 e retornar

  • Um valor falso, indicando que a posição é impossível ou
  • Uma cadeia de números de 1 a 7, o que indica uma possível sequência de movimentos que conduzem a que a posição (as colunas são numeradas 1a 7partir da esquerda para a direita, e portanto a sequência de 112, por exemplo, indica um movimento vermelho na coluna 1, seguido por um movimento amarelo na coluna 1, seguido de um movimento vermelho na coluna 2). Você pode escolher uma numeração de coluna que não seja 1234567, se desejar, desde que você especifique em sua solução. Se você deseja retornar a lista em algum outro formato; por exemplo, como uma matriz [2, 4, 3, 1, 1, 3], isso também é bom, desde que seja fácil ver quais são os movimentos.

Você pode ler o quadro em qualquer formato razoável, incluindo o uso de letras que não sejam Re Ypara os jogadores, mas você deve especificar qual jogador será o primeiro. Você pode assumir que o tabuleiro sempre será 6x7, com dois jogadores.

Você pode assumir que as posições que você recebe são pelo menos fisicamente possíveis de serem criadas em uma placa Connect 4 padrão; isto é, que não haverá peças 'flutuantes'. Você pode assumir que o quadro não ficará vazio.

Isso é código de golfe, então a resposta mais curta vence. Aplicam-se brechas padrão.

Exemplos

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | | --> 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
fonte
John, por curiosidade, você sabe se existe um algoritmo de força não-bruta?
Jonah

Respostas:

9

Gelatina , 57 bytes

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

Toma uma matriz onde 0não está preenchida, é 1reproduzida primeiro e 2reproduzida depois. Rende uma lista de colunas indexadas em 1, vazias se uma farsa foi identificada.

Experimente online! (ineficiente demais para que mais de 7 peças sejam executadas em menos de um minuto)

Nota:

  1. Pressupõe que nenhuma peça "flutuante" esteja presente (corrija isso adicionando ZṠṢ€Ƒȧ+6 bytes)
  2. Pressupõe que o tabuleiro vazio seja falso
Jonathan Allan
fonte
11

JavaScript (ES6),  202 194 187  183 bytes

240 0

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)

Experimente online!

Quão?

g241 13

Ao fazer isso, garante que não executemos quatro valores ímpares consecutivos até que todos os valores pares tenham desaparecido (ou seja, se um lado vencer, esse deve ser o último movimento).

yxp[x]

Comentado

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
fonte
Note que perguntei "Podemos assumir que o tabuleiro vazio não será fornecido como entrada?" - se tivermos que lidar com isso, seu código precisará de um ajuste.
Jonathan Allan
Eu não sei por que, 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] ])termina 0 e 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] ])deve ser verdade
Nahuel Fouilleul 21/01
@NahuelFouilleul Obrigado por denunciar isso. Corrigi o código e adicionei esses casos de teste.
Arnauld
2

Python 2 , 295 285 bytes

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

Experimente online!

-10 thx para Jo King .

Entrada é uma lista de cadeias que representam as colunas; com '1' para vermelho e '0' para amarelo. As strings não são preenchidas com ''. Portanto, o caso (falsey):

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

é inserido como:

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

Saída é uma lista de índices de coluna, indexados em 0, que podem fazer parte do quadro; ou Nonese não for válido.

Aceita o tabuleiro vazio como válido (retorna a lista vazia em []vez de None).

Essa abordagem é recursiva do último movimento para o primeiro movimento: com base na paridade do número total de movimentos realizados, removemos o último movimento Vermelho ou o último movimento Amarelo (ou falharemos se isso não for possível); verifique o tabuleiro resultante para ver se o oponente tem 4 em linha (nesse caso, falha, porque o jogo já deveria ter parado); caso contrário, recorra até que o quadro esteja vazio (o que é válido).

O código 4 em linha é a parte mais inchada. Todas as cadeias diagonais da matriz bsão geradas por:

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

que primeiro lista as diagonais "inclinadas para baixo" e depois as "inclinadas para cima".

Chas Brown
fonte