Inverter uma prancha de caça-minas

32

O Campo Minado é um popular jogo de computador que você provavelmente perdeu tempo jogando, ao tentar revelar as células que são minas em uma grade retangular, com base em dicas de quantas minas vizinhas cada célula não-mina possui. E caso você não tenha jogado, faça-o aqui .

Um fato matemático interessante sobre uma grade do Campo Minado (aka placa) é que:

Uma placa e seu complemento têm o mesmo número total da mina . ( Prova )

Isto é, se você tiver uma grade do Campo Minado completamente revelada, a soma de todos os números nessa grade, ou seja, o total da mina , será igual ao total da mina do complemento da grade, que é a grade na qual todas as minas foram substituídas por um não-mineiro e todo não-mineiro substituído por um.

Por exemplo, para a grade Campo Minado

**1..
34321
*2**1

o total da mina é 1 + 3 + 4 + 3 + 2 + 1 + 2 + 1 = 17.

O complemento da rede é

24***
*****
3*44*

que tem o meu total 2 + 4 + 3 + 4 + 4 = 17 novamente.

Escreva um programa que leva em uma grade Minesweeper arbitrário em forma de texto, onde *representa uma mina e 1através 8representam o número de minas adjacentes a uma célula não meu. Você pode usar .ou 0ou (espaço) para representar células sem vizinhos de minas, sua escolha. Você pode assumir que a grade de entrada será marcada corretamente, ou seja, cada célula que não é da mina denotará com precisão o número total de minas imediatamente adjacentes a ela, ortogonal ou diagonalmente.

Seu programa precisa imprimir o complemento da grade no mesmo formato (usando o mesmo ., 0ou como você esperava na entrada).

O código mais curto em bytes vence.

  • Em vez de um programa, você pode escrever uma função que pega a grade de entrada como uma string e imprime ou retorna a grade do complemento.
  • Uma nova linha à direita na entrada ou saída é boa, mas não deve haver outros caracteres além daqueles que formam a grade.
  • Você pode assumir que uma grade 1 × 1 será a menor entrada.

Casos de teste

Todas as entradas e saídas podem ser trocadas, pois o complemento do complemento é a grade original. As grades também podem ser giradas para outros casos de teste.

Entrada:

111
1*1
111

Saída:

***
*8*
***

Entrada:

.

Saída:

*

Entrada:

*11*1.1**1...1***1.....1*****1..........

Saída:

1**2***11*****1.1*******1...1***********

Entrada: ( exemplo Cut The Knot )

**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*

Saída:

24***4**
***7**64
*8**7***
******8*
4**7****
*33**5*3
Passatempos de Calvin
fonte
O TI-BASIC não pode aceitar uma linha de entrada vazia. O uso de um delimitador final (por exemplo ?) na linha após a linha final do quadro é aceitável ou posso levar o número de linhas de entrada pela linha de comando?
lirtosiast
@ThomasKwa Um delimitador final parece bom para o TI-BASIC e outros idiomas que possuem limitações estranhas de nova linha.
9789 Calvin's Hobbies

Respostas:

12

Pitão, 39 38 bytes

j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z

Experimente online: Demonstração

O algoritmo principal é realmente simples. Eu simplesmente itero sobre cada célula, pego a caixa 3x3 ao redor (ou menor quando a célula está na borda) e imprimo uma estrela ou o número de não estrelas nessa caixa.

Explicação:

j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z  implicit: .z = list of input strings
 .e                                 .z  map each index k, line b of .z to:
    .e                             b      map each index Y, char Z of b to:
         K\*                                assign "*" to K
                         +K.z               insert K at the front of .z
                        :    k+k3           slice from k to k+3
               :RtWYY+Y2                    take the slice from Y-1 or 0 
                                            to Y+2 for each line
              s                             join, this gives the 3x3 rectangle
                                             (or smaller on the border)
             -                   K          remove all "*"s
            l                               take the length
        +K                                   "*" + ^
       -                          Z         remove Z from this string
      h                                     and take the first char
                                            (if cell=mine take the number, 
                                             otherwise take the number)
  s                                       join the chars of one line
j                                       join by newlines
Jakube
fonte
Realmente limpo, +1
MKII
22

CJam, 58 57 bytes

0WX]2m*qN/{'*f+z}2*f{\~@m<fm<W<}:..+{W<{_'*#'*@'*-,?}/N}/

A entrada não deve terminar com um avanço de linha. A saída contém 0células sem minas próximas.

Experimente online no intérprete CJam .

Idéia

Começamos preenchendo a matriz de entrada com uma linha e uma coluna de asteriscos.

Para entrada

*4*
**2

isto resulta em

*4**
**2*
****

Agora, geramos todas as modificações possíveis resultantes da rotação das linhas e colunas 0, -1 ou 1 unidades para cima / esquerda:

*4** **** **2* **4* **** ***2 4*** **** *2**
**2* *4** **** ***2 **4* **** *2** 4*** ****
**** **2* *4** **** ***2 **4* **** *2** 4***

Descartamos os "locais de preenchimento" de cada rotação, ou seja,

*4* *** **2 **4 *** *** 4** *** *2*
**2 *4* *** *** **4 *** *2* 4** ***

e forme uma única matriz concatenando os caracteres correspondentes de cada rotação:

******4** 4*******2 **24*****
*******4* *4****2** 2***4****

O primeiro caractere de cada posição é seu caractere original.

  • Se for um não-asterisco, deverá ser substituído por um asterisco.

  • Se for um asterisco, o número de não asteriscos nessa cadeia é o número de minas vizinhas.

Como funciona

0WX]2m*   e# Push the array of all vectors of {0,-1,1}^2.
qN/       e# Read all input from STDIN and split at linefeeds.
{'*f+z}2* e# Append a '*' to each row and transpose rows with columns. Repeat.
f{        e# For each vector [A B], push the modified input Q; then:
  \~      e#   Swap Q with [A B] and dump A and B on the stack.
  @m<     e#   Rotate the rows of Q B units up.
  fm<     e#   Rotate each row of the result A units left.
  W<      e#   Discard the last row.
}         e# This pushes all nine rotations with Manhattan distance 1.
:..+      e# Concatenate the corresponding characters for each position.
{         e# For each row:
  W<      e#   Discard the character corresponding to the last column.
  {       e#   For each remaining string:
    _'*#  e#     Find the first index of '*' in a copy.
    '*    e#     Push '*'.
    @'*-, e#     Count the non-asterisks in the string.
    ?     e#     Select '*' if the index is non-zero, the count otherwise.
  }/      e#
  N       e#   Push a linefeed.
}/        e#
Dennis
fonte
7
Estou com medo - isso é incrível.
Deusovi 29/09/15
Você acabou de quebrar o sistema. +1! Posso perguntar onde você encontrou essa teoria?
GamrCorps
9
@IonLee Este é tudo meu. Na verdade, é uma idéia bastante simples: em vez de verificar as células em torno de uma determinada célula, movemos toda a grade e observamos o que cai dentro da célula.
Dennis
Bravo! Eu nunca pensaria nisso.
GamrCorps
7

Ruby, 119

->s{w=1+s.index('
')
s.size.times{|c|t=0;9.times{|i|(s+?**w*2)[c+i/3*w-w+i%3-1]<?0||t+=1}
print [t,?*,'
'][s[c]<=>?*]}}

Sem jogar no programa de teste:

f=->s{
  w=1+s.index("\n")                          #width of board
  s.size.times{|c|                           #iterate through input
    t=0;                                     #number of digits surrounding current cell
    9.times{|i|                              #iterate through 3x3 box (centre must be * if this ever gets printed.)
      (s+"*"*w*2)[c+i/3*w-w+i%3-1]<"0"||t+=1 #copy of s has plenty of * appended to avoid index errors
    }                                        #add 1 every time a number is found.
  print [t,"*","\n"][s[c]<=>"*"]             #if * print t. if after * in ACSII it's a number, print *. if before, it's \n, print \n
  }
}


f['**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*']
Level River St
fonte
2

Oitava, 76

m=@(s)char(conv2(b=(cell2mat(strsplit(s)'))~='*',ones(3),'same').*~b-6*b+48)

Explicação

  • Converta a string de entrada na matriz de strings usando strsplite cell2mat.

  • Obtenha a matriz lógica que contém 1onde não há *na matriz original.

  • Tome sua convolução com uma matriz 3x3 de 1's.

  • Mascare-o com a matriz lógica inversa e coloque-o *no lugar da máscara.

  • Nota: Células sem vizinhos de minas são representadas como 0.

Execução

>> m(['**100' 10 '34321' 10 '*2**1'])   %// `10` is newline
ans =

24***
*****
3*44*

>> m(['24***' 10 '*****' 10 '3*44*'])
ans =

**100
34321
*2**1
taça
fonte