Holen Sie sich zwei aus einem

12

Wie wir in dieser Frage gesehen haben, können komplexe logische Aussagen in Form von einfachen Verknüpfungen von verallgemeinerten Minesweeper ausgedrückt werden. Generalized Minesweeper hat jedoch immer noch Redundanzen.

Um diese Redundanzen zu vermeiden, definieren wir ein neues Spiel namens "Generalized-1 Minesweeper".

Generalized-1 Minesweeper ist eine Version von Minesweeper, die auf einem beliebigen Graphen gespielt wird. Der Graph hat zwei Arten von Eckpunkten, einen "Indikator" oder einen "Wert". Ein Wert kann entweder ein oder aus sein (eine Mine oder ein Blindgänger), sein Status ist dem Spieler jedoch unbekannt. Ein Indikator zeigt an, dass genau eine der benachbarten Zellen eingeschaltet ist (eine Mine). Indikatoren gelten selbst nicht als Minen.

Das folgende Board für Generalized Minesweeper zeigt uns beispielsweise, dass die Zellen A und B entweder beide Minen sind oder keine von ihnen Minen sind.

Einfaches Spiel

(In der Grafik sind die Anzeigen grau markiert, während die Werte weiß sind.)

Anders als bei normalen Minensuchbooten, bei denen Sie auf Werte klicken, die deaktiviert sind, um Indikatoren anzuzeigen, gibt es bei Generalized Minesweeper keine solche Mechanik. Ein Spieler bestimmt einfach, für welche Zustände des Graphen seine Indikatoren erfüllt werden können.

Dein Ziel ist es, einen 2Generalized-1 Minesweeper zu machen. In Generalized-1 Minesweeper erstellen Sie eine Struktur, bei der es 8 bestimmte Zellen gibt, für die in allen möglichen Wertekonfigurationen genau zwei Zellen vorhanden sind. Dies bedeutet, dass es sich genauso verhält wie 2bei herkömmlichen Minensuchbooten. Wenn Sie Ihre Lösung schreiben, sollten Sie keine spezifischen Werte für Wertezellen berücksichtigen. (In Beantwortung der Frage von H.PWiz ist es zulässig, dass einige Wertezellen vom Staat ableitbar sind.)

Wertung

Ihre Antworten werden anhand der Anzahl der Eckpunkte im endgültigen Diagramm minus 8 (für die 8 Eingaben) bewertet, wobei eine niedrigere Punktzahl besser ist. Wenn zwei Antworten mit dieser Metrik übereinstimmen, ist der Gleichstand die Anzahl der Kanten.

math code-challenge game graph-theory atomic-code-golf Post Rock Garf Hunter
quelle
Verbindet eine Kante immer einen Indikatorscheitelpunkt und einen Wertscheitelpunkt?
Xnor
@xnor Um deine Punktzahl zu maximieren, sollten sie es tun, aber ich habe nicht das Gefühl, dass ich das zu einer Regel machen muss. Kanten, die keine Werte mit Indikatoren verbinden, ändern das Verhalten des Diagramms nicht.
Post Rock Garf Hunter
Wenn 6 von der Punktzahl abgezogen wird, wie lauten die 6 Eingaben? Gibt es nicht 8 Zellen?
Xnor
@xnor Sorry sollte 8. Jetzt behoben sein.
Post Rock Garf Hunter
Was meinen Sie mit "Struktur ... so, dass es 8 bestimmte Zellen gibt, auf denen die einzig möglichen Wertekonfigurationen genau zwei Zellen haben"? Sollen die einzig möglichen Konfigurationen nur zwei Minen haben?
Dylnan

Antworten:

7

42 Ecken, 56 Kanten

Minen-Netzwerk

Jede Variable ist ein Wertscheitelpunkt, und jedes Feld ist ein Indikatorscheitelpunkt mit Kanten zu den darin enthaltenen Variablen. Die Eingänge sind x 1 , ..., x 8 . Hier ist zum Beispiel eine Lösung mit Minen bei x 3 und x 5 , wobei Minen grün hervorgehoben sind.

Minen Netzwerklösung

Die horizontalen Zwänge stellen sicher, dass genau eines der A und genau eines der A ist b eine Mine hat. In diesen beiden Spalten enthält r keine Mine, in den anderen sechs Spalten jedoch. (Beachten Sie, dass a und b nicht beide eine Mine in derselben Spalte haben können.) Jeder Eingang x befindet sich gegenüber dem r in seiner Spalte, sodass genau zwei Eingänge Minen haben, wie gewünscht.

Zum k Eingaben werden 5k+2Scheitelpunkte ( 3kWert und 2k+2Indikator) und 7kKanten verwendet. Hier k=8gibt Eingänge 42 Ecken und Kanten 56.

xnor
quelle
3

50 Ecken, 89 Kanten

Basierend auf dem Logikgatter aus der Antwort von H.PWiz.

  A&B      C&D      E&F      G&H
   |        |        |        |
b--1--a  d--1--c  f--1--e  h--1--g
|  |  |  |  |  |  |  |  |  |  |  |
1--?--1  1--?--1  1--?--1  1--?--1
|     |  |     |  |     |  |     |
A     B  C     D  E     F  G     H

Jedes *ist eingeschaltet, wenn die beiden entsprechenden Eingänge eingeschaltet sind. Um den Fall einer einzigen Eingabe handhaben , verwenden wir die Zwischenwerte a=A&!Busw. anschließen alle drei Werte a, bund A&Ban den Eingang eines sekundären Ebene von Gates gibt uns einen effektiven Eingang A|B(das spart Eckpunkte über !(!A&!B)):

      *              *
      |              |
   #--1--#        #--1--#
   |  |  |        |  |  |
   1--?--1        1--?--1
  |||   |||      |||   |||
  A|B   C|D      E|F   G|H

Diese *s sind eingeschaltet, wenn zwei ihrer Eingänge (entsprechend vier der ursprünglichen Eingänge) eingeschaltet sind, mit Ausnahme der oben bereits behandelten Paare. In der Zwischenzeit können wir die #*#Knoten mit einem letzten Tor verbinden. Wir haben daher folgende Ergebnisse:

A&B
C&D
E&F
G&H
(A|B)&(C|D)         [4 cases]
(E|F)&(G|H)         [4 cases]
(A|B|C|D)&(E|F|G|H) [16 cases]

Diese decken alle 28 Fälle von zwei Eingängen ab. Es bleibt dann ein letzter Indikator mit diesen sieben Werten zu verbinden. Wenn weniger als zwei Eingänge eingeschaltet sind, ist keiner dieser Eingänge eingeschaltet, sodass die Anzeige ausgeschaltet ist. Wenn mehr als zwei Eingänge eingeschaltet sind, sind mehrere dieser Eingänge eingeschaltet und die Anzeige ist ausgeschaltet.

Neil
quelle
Ah, ich hatte eine ähnliche Idee, aber am Ende entstand eine kompliziertere Version davon. Gut gemacht!
Nur die Hälfte des
Ich bin nicht davon überzeugt, dass es 43 Eckpunkte gibt. Sie zeigen deutlich 42, Sie sagen also, Sie brauchen nur noch einen, um alles anzuschließen?
H.PWiz
Eigentlich, wenn ich richtig die Grafik , die Sie beschreiben gezeichnet haben, denke ich , es ermöglicht Staaten wie ACE, BDF, ADG...
H.PWiz
@ H.PWiz Ich verstehe was du meinst ... Ich denke, vielleicht kann ich das mit zusätzlichen Kanten lösen, um den Ausdruck zu geben (a&b)+((a|b)&(c|d))+(c&d)+((a|b|c|d)&(e|f|g|h))+(e&f)+((e|f)&(g|h))+(g&h)==1, sieht das für dich richtig aus?
Neil
Vielleicht, obwohl dieser Ausdruck für mich so aussieht, als würde er das Problem vollständig lösen. Und ich habe keine Ahnung, welche Kanten Sie hinzufügen können, um das zu bekommen ...
H.PWiz
2

197 Eckpunkte, 308 Kanten

Ich habe mir diese Antwort gestern Abend ausgedacht, sie aber nicht veröffentlicht, weil sie so hoch war. Da schlägt es jedoch die andere Antwort um ein Vielfaches übertrifft, sollte ich es dennoch posten.

Ich verwende die folgenden Einstellungen für alle 28 Wertepaare in Zellen ABCDEFGH

   ?*
   |
?--1--?
|  |  |
1--?--1
|     |
A     B

?Stellt eine Wertezelle dar, die nicht in ABCDEFGH. Wenn hier ?*ist ON , Aund Bsind beide auf. Ansonsten AundB in jeder anderen Konfiguration sein könnte.

Ich verbinde alle 28 ?*s mit einer Indikatorzelle. Dies bedeutet, dass nur ein Paar ABCDEFGHzwei EIN hat . Welches ist ausreichend , dass genau zwei meiner Ausgangszellen zu erzwingen wird ON

H.PWiz
quelle
1
Beachten Sie, dass im Gate jede der 4 ?s einem der 4 Zustände von entspricht A B.
Post Rock Garf Hunter
@HeebyJeebyMan Interessant, das hatte ich nicht bedacht. Ich habe dieses Tor gerade durch Glück gefunden
H.PWiz
1

354 Knoten, 428 Kanten

Nur um zu beweisen, dass es möglich ist. Ich werde dies später mit einigem Zwischenspeichern verbessern.

(hoffentlich kein Codefehler)

Ich versuchte , ein Mathematica - Programm zu schreiben hier Programm Gültigkeit zu überprüfen, aber es funktioniert nicht wahrscheinlich funktionieren , weil es zu viele Variablen.

Das Ergebnis wurde von einem Computerprogramm generiert: Probieren Sie es online aus!

Ich benutze ein Tor, das so aussieht:


               (f)
                |
                |
               (#)
              /   \
             /     \
           (d)     (e)
          /           \
         /             \
       (#) --- (c) --- (#)
     .'                  '.
   .'                      '.
(a)                          (b)

wo (#)sind 1-Indikatoren, (a)..(f) sind Werte.

Dann,


c = (not a) and (not b)
d = (not a) and      b
e =      a  and (not b)
f =      a  xnor     b

Auch dieses Tor


(a) ----- (#) ----- (b)

gibt


b = not a

. Verwenden Sie diese beiden Arten von Toren, mit denen Sie beliebige Ausdrücke erstellen können.

Natürlich ist dies die Behauptung, dass (a)dies wahr sein muss:


(a) ----- (#)
user202729
quelle
1

81 Knoten, 108 Kanten

Mit 13 Knoten und 14 Kanten erstellen wir das folgende Adder-Gate (C (arry) = X UND Y, S (um) = X XOR Y):

X - 1 --------------?
   | |
   - 1 - S - 1 -? - 1
   | | |
   | C |
Y - 1 --------------?

Addiere mit vier Addierern M1, M2, M3, M4 A + B, C + D, E + F, G + H mit dem resultierenden Übertrag C1, C2, C3, C4 und der Summe S1, S2, S3. S4.

Verwenden Sie zwei Addierer M5, M6, um S1 + S2, S3 + S4 mit dem resultierenden Übertrag C5, C6 und der Summe S5, S6 zu addieren.

Füge mit einem Adder M7 S5 + S6 hinzu, um C7 und S7 zu erhalten.

Verbinden Sie nun alle Überträge mit einem einzelnen Anzeigeknoten wie dem folgenden:

C1- |
C2- |
C3- |
C4 - + - 1
C5- |
C6- |
C7- |

und erzwinge, dass S7 (das Modulo 2 der Summe von 8 Werten) durch diese Schaltung 0 ist:

S7--1 -? - 1

Ich behaupte, dass diese Schaltung genau zwei Werte zwingt, ABCDEFGHEIN zu sein, da es nur eine gerade Zahl sein kann (da S7 0 ist) und es nicht mehr als 3 EIN-Werte geben kann (da nur einer von C1-C7 EIN ist).

nur zur Hälfte
quelle