Zählen Sie Mills in Nine Men's Morris

21

Einführung

Nine Mens's Morris (auch Mills genannt) ist ein Brettspiel für zwei Spieler, das auf dem folgenden Brett gespielt wird (Bild von der verlinkten Wikipedia-Seite):

Mühle Bord

Jeder Spieler hat 9 Männer, schwarz und weiß gefärbt. Die konkreten Regeln sind für diese Herausforderung nicht wichtig, aber schauen Sie bei Interesse auf der Wikipedia-Seite nach.

Die Herausforderung

Bei einem Gitter als Eingabe, das einen bestimmten Boardstatus darstellt, wird die Gesamtanzahl der Mühlen mmit ausgegeben 0<=m<=8.
Drei gleichfarbige Männer bilden eine Mühle, wenn sie sich in einer geraden Reihe miteinander verbundener Punkte befinden. b2to f2ist keine Mühle, da die Männer von unterschiedlicher Farbe sind. Auch d2auf d5nicht eine Mühle bilden , da die drei Punkte miteinander verbunden werden müssen.
Die Tafel im Bild oben enthält zum Beispiel zwei Mühlen. Eins von f2bis f6und eins von e3bis e5.

Eingang

Die Tafel wird als 2D-Gitter mit 24 Punkten dargestellt, die wie im obigen Beispielbild dargestellt verbunden sind. In diesem Beispiel werden a-gfür die Spalten die Buchstaben von und 1-7für die Zeilen die Zahlen von verwendet. Sie können jedoch jedes sinnvolle Eingabeformat auswählen, sofern 24 eindeutige Koordinaten einem der folgenden Zustände zugeordnet werden:

  • Leeren
  • Aufgenommen von Schwarz
  • Aufgenommen von Weiß

Die konkrete Darstellung liegt bei Ihnen. Sie sind nicht auf "b" oder "w" für die Farben beschränkt.

Außerdem enthält Ihre Eingabe möglicherweise keine zusätzlichen Informationen.

Zusätzliche Bemerkungen

  • Sie müssen die Punkte nicht durch irgendwelche Werte abbilden. Wenn Sie die Eingabe als 2D-Array verwenden möchten, ist dies ebenfalls in Ordnung. Bedenken Sie jedoch, dass nicht alle darin enthaltenen Punkte verwendet werden und dass Sie die Verbindungen zwischen ihnen berücksichtigen müssen.
  • Die Eingabe ist möglicherweise leer. In diesem Fall müssen Sie Null ausgeben (leere Karte -> keine Mühlen).
  • Da jeder Spieler 9 Männer hat, enthält die Eingabe niemals mehr als 18 genommene Punkte.
  • Sie können leere Punkte in der Eingabe auslassen und daher nur Eingabepunkte, die verwendet werden.
  • Der Eingang kann beliebig bestellt werden. Sie können sich nicht auf eine bestimmte Bestellung verlassen.
  • Sie können davon ausgehen, dass die Eingabe immer gültig ist. Dies bedeutet, dass es nicht mehr als 9 Männer in jeder Farbe gibt und dass jeder Punkt einzigartig ist.

Regeln

  • Stellen Sie klar, welches Eingabeformat Sie in Ihrer Lösung verwenden. Das Bereitstellen eines Beispiellaufs Ihres Programms wird dringend empfohlen.
  • Funktion oder Vollprogramm erlaubt.
  • Standardregeln für die Eingabe / Ausgabe.
  • Es gelten Standardlücken .
  • Dies ist , also gewinnt die niedrigste Byte-Anzahl. Tiebreaker ist eine frühere Vorlage.

Testfälle

Das Eingabeformat ist hier eine Liste von Tupeln mit den Koordinaten wie im obigen Beispiel als erstes Element und dem Zustand des zweiten Punktelements. Ein von Weiß aufgenommener Punkt wird als "w" und ein von Schwarz aufgenommener Punkt als "b" markiert. Alle anderen Punkte werden ausgelassen und sind leer.

[("a4", "w"), ("b2", "b"), ("b4", "b"), ("c4", "b"), ("d1", "w") , ("d2", "w"), ("e3", "w"), ("e4", "w"), ("e5", "w"), ("f2", "b") , ("f4", "b"), ("f6", "b"), ("g4", "w")] -> 2
[("a1", "b"), ("a4", "b"), ("a7", "b"), ("b4", "b"), ("c4", "b") , ("d3", "w"), ("d2", "w"), ("d1", "w")] -> 3
[] -> 0
[("b4", "b"), ("a4", b "), (" c4 ", w")] -> 0
[("b4", "b"), ("a4", b "), (" c4 ", b")] -> 1
[("a1", "b"), ("a4", "b"), ("a7", "b"), ("b2", "b"), ("b4", "b") , ("b6", "b"), ("c3", "b"), ("c4", "b"), ("c5", "b"), ("e3", "w") , ("e4", "w"), ("e5", "w"), ("f2", "w"), ("f4", "w"), ("f6", "w") , ("g1", "w"), ("g4", "w"), ("g7", "w")] -> 8

Viel Spaß beim Codieren!

Denker
quelle
Verwandte - ein wenig.
Insertusernamehere
Ich gehe davon aus, dass die Farben sowohl zusammenhängend als auch ausgerichtet sein müssen, aber es ist ein bisschen unklar. Würden z. B. d2, d3, d5 der gleichen Farbe eine Mühle bilden?
Robert Benson
@RobertBenson Nein, es würde nicht weil d3und d5nicht verbunden sind. Die Regeln sagen: Three men of the same color form a mill when they are in a straight row of connected points.. Ich habe in diesem Abschnitt einige Beispiele hinzugefügt, um dies zu verdeutlichen, danke für den Kommentar!
Denker

Antworten:

4

APL (Dyalog Classic) , 26 bis 25 Byte

-1 danke an FrownyFrog

≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢

Probieren Sie es online!

Das Argument ist ein 3x3x3-Array aus 1(schwarz), ¯1(weiß) und 0(leer). Die erste Dimension ist die Verschachtelungstiefe der konzentrischen Quadrate. Die anderen beiden Dimensionen liegen entlang der vertikalen und horizontalen Achse.

000---------001---------002
 |           |           |
 |  100-----101-----102  |
 |   |       |       |   |
 |   |  200-201-202  |   |
 |   |   |       |   |   |
010-110-210     212-112-012
 |   |   |       |   |   |
 |   |  220-221-222  |   |
 |   |       |       |   |
 |  120-----121-----122  |
 |           |           |
020---------021---------022

Wir haben eine Mühle, wenn die Summierung entlang einer Achse a 3oder ergibt ¯3, außer wir müssen die vier Ecken verwerfen, wenn wir entlang der ersten Achse summieren.

{} ist eine Funktion mit implizitem Argument

↓⍵ist aufgeteilt - in unserem Fall wird ein 3x3x3-Würfel in eine 3x3-Matrix verschachtelter Länge-3-Vektoren umgewandelt

⍵⍪↓⍵ Nimmt man den Originalwürfel und klebt die 3x3-Matrix von 3-Vektoren darunter, so erhält man ein 4x3x3-gemischtes Array von Skalaren und Vektoren

+/Summen entlang der letzten Achse; Dies hat den kombinierten Effekt, dass der ursprüngliche Würfel entlang der letzten Achse +/⍵summiert wird ( ) und entlang der Mittelachse summiert wird, da wir eine Teilung vorgenommen haben ( +/↓⍵).

Jetzt müssen wir uns um den Spezialfall für die erste Achse kümmern.

+⌿⍵ summiert entlang der ersten Achse und gibt eine 3x3-Matrix zurück

4 2⍴ Aber wir dürfen die Ecken nicht zählen, also formen wir sie in eine 4x2-Matrix wie diese um:

ABC      AB
DEF  ->  CD
GHI      EF
         GH  ("I" disappears)

Jetzt interessieren wir uns nur für die letzte Spalte ( BDFH), also verwenden wir das Idiom⊢/

,verkettet sich BDFHmit der Matrix, die wir zuvor für die 2. und 3. Achse erhalten haben ( BDFHund die Matrix hat beide zufällig eine führende Dimension von 4)

fasst alles, was wir bisher erhalten haben, zu einem einzigen Vektor zusammen

| nimmt die absoluten Werte

{ }∩≢ filtert nur die drei - die Länge (≢) der Eingabe ist immer 3

zählt sie

ngn
quelle
Heh, ich wollte das gerade vorschlagen.
Adám
Können Sie sich für einen Moment bei chat.stackexchange.com/rooms/52405/apl anmelden ?
Adám
≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢ist eine kürzer :)
FrownyFrog
@FrownyFrog danke! bearbeitet in
ngn
4

JavaScript (ES6), 276 228 125 117 105 Bytes

a=>btoa`i·yø!9%z)ª»-ºü1j;ÝÈ%¥·¡ªÜ"·ç¹Ê1`.replace(/.../g,b=>(a[b[0]]+a[b[1]]+a[b[2]])/3&1||'').length

(Das obige enthält einige nicht druckbare ASCII-Zeichen, die hier nicht angezeigt werden. Daher ist hier eine Version ohne die btoa, die kopiert und ausgeführt werden kann.)

a=>'abcdefghijklmnopqrstuvwxajvdksglpbehqtwimrfnucox'.replace(/.../g,b=>(a[b[0]]+a[b[1]]+a[b[2]])/3&1||'').length

Teilt eine Referenzzeichenfolge in Buchstabentriolen, die mit den Mühlengruppenschlüsseln übereinstimmen. Die Eingabe erfolgt in Form eines Objekts, wobei die Tasten die Buchstaben sind a-x, die von links unten bis rechts oben beginnen und sich zuerst von links nach rechts bewegen. Die Werte gelten 1für Weiß, -1Schwarz und 0Leer.

Beispiel

{b:1,d:-1,e:1,f:-1,i:1,k:-1,l:-1,m:1,n:-1,r:1,u:-1} => 2
{j:1,d:-1,k:-1,l:-1,b:1,e:1,i:1,m:1,r:1,f:-1,n:-1,u:-1,o:1} => 2
{a:-1,j:-1,v:-1,k:-1,l:-1,h:1,e:1,b:1} => 3
{} => 0
{k:-1,j:-1,l:1} => 0
{k:-1,j:-1,l:1} => 1
{a:-1,j:-1,v:-1,d:-1,k:-1,s:-1,g:-1,l:-1,p:-1,i:1,m:1,r:1,f:1,n:1,u:1,c:1,o:1,x:1} => 8

Diese Beispiele stammen aus den Beispielen von OP, die in das Objekt Buchstabenschlüssel und Zahlenwert konvertiert wurden. Die erste stammt aus dem Beispielbild, während die anderen aus dem Beispielsatz stammen.

Mwr247
quelle
1
Gute Arbeit! Sie könnten die große Saite mit komprimieren atob.
ETHproductions
@ETHproductions Danke! Es scheint jedoch nicht druckbare ASCII-Zeichen zu verwenden, daher werde ich auch eines ohne einschließen btoa. Fand auch einige andere Verbesserungen, die es noch mehr nach unten bringen.
Mwr247,
2

Mathematica, 217 131 Bytes

Ich bin mir zwar sicher, dass dies nicht besonders wettbewerbsfähig ist, aber hier ist ein Eintrag für Sie.

Count[Total/@{{a1,d1,g1},{b2,d2,f2},{c3,d3,e3},{a4,b4,c4},{e4,f4,g4},{c5,d5,e5},{b6,d6,f6},{a7,d7,g7},{a1,a4,a7},{b2,b4,b6},{c3,c4,c5},{d1,d2,d3},{d5,d6,d7},{e3,e4,e5},{f2,f4,f6},{g1,g4,g7}}/.#/.{"w"->1,"b"->2},3|6]&

Eingabebeispiel:

{a4 -> "w", b2 -> "b", b4 -> "b", c4 -> "b", d1 -> "w", d2 -> "w", e3 -> "w", e4 -> "w", e5 -> "w", f2 -> "b", f4 -> "b", f6 -> "b", g4 -> "w"}

Das Zulassen von Koordinatennamen mit einem Zeichen spart trivial 51 Zeichen, was dies zu einer 166-Byte-Lösung macht. Das Benennen der Spieler 1 und 2 anstelle von "w" und "b" spart 17 weitere Charaktere.

So bekommen wir

Count[Total/@{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,a,j,v,d,k,s,g,l,p,b,e,h,q,t,w,r,i,m,f,u,n,c,o,x}~Partition~3,3|6]/.#&
Ein Simmons
quelle
Wenn ich die Eingabeformatierungsregeln richtig verstehe, sollten Sie sie als 1und aufnehmen können 2. das verwendete Beispiel wund b, aber ich bin mir ziemlich sicher, dass wir nicht darauf beschränkt sind.
Mwr247
@ Mwr247 Du hast recht. Sie können jedes gewünschte Format verwenden, sofern keine zusätzlichen Informationen hinzugefügt werden. Ich werde das klären, wenn ich zu Hause bin.
Denker
1

APL (Dyalog Unicode) , 50 Byte

"Die Lösung der Objekte"

Sie ist zwar länger (29 Zeichen) als die Lösung von @ ngn , verwendet jedoch einen völlig anderen Ansatz: Die Eingabe hat die gleiche Gesamtstruktur wie diese Lösung, jedoch werden alle Slots als Objekte dargestellt. Leere Slots (einschließlich der nicht vorhandenen mittleren Spalte) müssen leere Objekte sein. Alle schwarzen Männer müssen sich auf das Objekt "Schwarzer Mann" beziehen, und alle weißen Männer müssen sich auf das Objekt "Weißer Mann" beziehen. Alle Objekte können optional schön haben D isplay F orm s Lesbarkeit zu verbessern, so dass die Mittelsäule optional unsichtbar gemacht werden können.

+/1=(≢¨(,∪/,∪⌿⍤2),(⊢/4 2⍴∪⌿))

Probieren Sie es online!

+/ die Summe von

1=(... ) diejenigen in

≢¨() Die Zahlen von

  , das Gewirbelte

  ∪/ einzigartige Sets über

  , verkettet an

  ∪⌿⍤2 einzigartige setzt

,() Verkettet an

  ⊢/ die rechte Spalte von

  4 2⍴ die, in vier Zeilen und zwei Spalten umgeformt,

  ∪⌿ einzigartige Säulensätze

Ein atop- Operator, wie er mit AGL ( ä) geliefert wird , würde die Länge auf 27 Zeichen reduzieren .

Adam
quelle