Invertiere ein Minesweeper Board

32

Minesweeper ist ein beliebtes Computerspiel, bei dem Sie wahrscheinlich viel Zeit damit verschwendet haben, die Zellen, die Minen sind, in einem rechteckigen Raster anzuzeigen, basierend auf Hinweisen darauf, wie viele benachbarte Minen jede Nicht-Minenzelle hat. Und falls Sie es noch nicht gespielt haben, tun Sie dies hier .

Eine raffinierte mathematische Tatsache über ein Minesweeper-Gitter (auch bekannt als Board) ist, dass:

Ein Brett und sein Komplement haben die gleiche Gesamtzahl an Minen . ( Beweis )

Das heißt, wenn Sie ein vollständig aufgedecktes Minesweeper-Gitter haben, entspricht die Summe aller Zahlen auf diesem Gitter, dh die Minensumme , der Minensumme des Komplements des Gitters, das das Gitter ist, in dem jede Mine ersetzt wurde mit einer Nichtmine und jede Nichtmine durch eine Mine ersetzt.

Zum Beispiel für das Minesweeper-Gitter

**1..
34321
*2**1

Die Minensumme beträgt 1 + 3 + 4 + 3 + 2 + 1 + 2 + 1 = 17.

Die Ergänzung des Gitters ist

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

das hat mir insgesamt 2 + 4 + 3 + 4 + 4 = 17 wieder.

Schreiben Sie ein Programm, das ein beliebiges Minesweeper-Gitter in Textform aufnimmt, wobei *eine Mine und 1durch 8die Anzahl der Minen neben einer Nicht-Minenzelle dargestellt wird. Sie können .oder 0oder (Leerzeichen) verwenden, um Zellen ohne Minennachbarn Ihrer Wahl darzustellen. Sie können davon ausgehen, dass das Eingaberaster korrekt markiert ist, dh, jede Nicht-Minenzelle gibt genau die Gesamtzahl der Minen an, die orthogonal oder diagonal unmittelbar daneben liegen.

Ihr Programm braucht die Ergänzung des Gitters im gleichen Format drucken (mit dem gleichen ., 0oder wie Sie in der Eingabe erwartet).

Der kürzeste Code in Bytes gewinnt.

  • Anstelle eines Programms können Sie eine Funktion schreiben, die das Eingaberaster als Zeichenfolge verwendet und das Komplement-Raster ausgibt oder zurückgibt.
  • Ein abschließender Zeilenumbruch in der Eingabe oder Ausgabe ist in Ordnung, es sollten jedoch keine anderen Zeichen als die das Raster bildenden vorhanden sein.
  • Sie können davon ausgehen, dass ein 1 × 1-Raster die kleinste Eingabe ist.

Testfälle

Alle Ein- und Ausgänge könnten getauscht werden, da das Komplement des Komplements das ursprüngliche Gitter ist. Die Gitter können auch für weitere Testfälle gedreht werden.

Eingang:

111
1*1
111

Ausgabe:

***
*8*
***

Eingang:

.

Ausgabe:

*

Eingang:

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

Ausgabe:

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

Eingabe: ( Cut The Knot-Beispiel )

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

Ausgabe:

24***4**
***7**64
*8**7***
******8*
4**7****
*33**5*3
Calvins Hobbys
quelle
TI-BASIC kann keine leere Eingabezeile akzeptieren. Ist die Verwendung eines Endebegrenzers (zum Beispiel ?) in der Zeile nach der letzten Zeile der Karte akzeptabel, oder kann ich die Anzahl der Eingabezeilen über die Befehlszeile eingeben?
Lirtosiast
@ThomasKwa Ein Endebegrenzer klingt gut für TI-BASIC und andere Sprachen mit seltsamen Zeilenumbrüchen.
Calvins Hobbys

Antworten:

12

Pyth, 39 38 Bytes

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

Probieren Sie es online aus: Demonstration

Der Hauptalgorithmus ist wirklich einfach. Ich iteriere einfach über jede Zelle, nehme das umgebende 3x3-Kästchen (oder kleiner, wenn sich die Zelle am Rand befindet) und drucke einen Stern oder die Anzahl der Nicht-Sterne in diesem Kästchen.

Erläuterung:

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
quelle
Wirklich ordentlich, +1
MKII
22

CJam, 58 57 Bytes

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

Die Eingabe sollte nicht mit einem Zeilenvorschub enden. Die Ausgabe enthält 0für Zellen ohne Minen in der Nähe.

Probieren Sie es online im CJam-Interpreter aus .

Idee

Wir beginnen mit dem Auffüllen der Eingabematrix mit einer Zeile und einer Spalte von Sternchen.

Zur Eingabe

*4*
**2

das führt zu

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

Jetzt generieren wir alle möglichen Änderungen, die sich aus dem Drehen der Zeilen und Spalten 0, -1 oder 1 Einheiten nach oben / links ergeben:

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

Wir verwerfen die "Auffüllorte" von jeder Umdrehung, dh

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

und bilden Sie eine einzelne Matrix, indem Sie die entsprechenden Zeichen jeder Umdrehung verketten:

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

Das erste Zeichen jeder Position ist das ursprüngliche Zeichen.

  • Wenn es sich nicht um ein Sternchen handelt, muss es durch ein Sternchen ersetzt werden.

  • Wenn es sich um ein Sternchen handelt, entspricht die Anzahl der Nicht-Sternchen in dieser Zeichenfolge der Anzahl der benachbarten Minen.

Wie es funktioniert

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
quelle
7
Ich habe Angst - das ist unglaublich.
Deusovi
Sie, Sir, haben gerade das System kaputt gemacht. +1! Darf ich fragen, wo Sie diese Theorie gefunden haben?
GamrCorps
9
@IonLee Das bin alles ich. Eigentlich ist es eine ziemlich einfache Idee: Anstatt die Zellen um eine bestimmte Zelle herum zu überprüfen, bewegen wir das gesamte Gitter herum und beobachten, was in die Zelle fällt.
Dennis
Bravo! Daran hätte ich nie gedacht.
GamrCorps
7

Rubin, 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]<=>?*]}}

Ungolfed im Testprogramm:

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

Oktave, 76

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

Erläuterung

  • Konvertieren Sie die Eingabezeichenfolge mit strsplitund in eine Zeichenfolgenmatrix cell2mat.

  • Holen Sie sich die logische Matrix, die enthält, 1wo es keine *in der ursprünglichen Matrix gibt.

  • Nehmen Sie seine Faltung mit einer 3x3-Matrix von Einsen.

  • Maskiere es mit der inversen logischen Matrix und setze sie *an die Stelle der Maske.

  • Hinweis: Zellen ohne Minennachbarn werden als dargestellt 0.

Ausführung

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