21
\$\begingroup\$

Introduction

Nine Mens's Morris (also called Mills) is a board game for two players which is played on the following board (image taken from the linked Wikipedia-page):

Mill board

Each player has 9 men, colored black and white. The concrete rules are not important for this challenge, but check out the Wikipedia-page if you are interested.

The Challenge

Given a grid as input, which represents a certain boardstate, output the total mill count m with 0<=m<=8.
Three men of the same color form a mill when they are in a straight row of connected points. b2 to f2 is not a mill since the men are of different color. Also d2 to d5 would not form a mill since the three points have to be connected.
The board in the image above contains two mills for example. One from f2 to f6 and one from e3 to e5.

Input

The board is represented as a 2D grid with 24 points which are connected as shown in the example image above. The example uses letters from a-g for the columns and numbers from 1-7 for the rows, but you may choose any reasonable input format as long as it maps 24 unique coordinates to one of the following states:

  • Empty
  • Taken by black
  • Taken by white

The concrete repersentation is up to you you are not restricted to "b" or "w" for the colors.

Besides this, your input may not contain any additional information.

Additional notes

  • You don't have to map the points by any kind of values. If you want to take the input as a 2D array, that's fine as well. But keep in mind that not all points in there are used and that you have to consider the connections between them.
  • The input might be empty, in which case you have to output zero (empty board -> no mills).
  • Since each player has 9 men, the input will never contain more than 18 taken points.
  • You may leave out emtpy points in the input and therefore only input points which are taken.
  • The input may be ordered in any way. You can't rely on a specific order.
  • You may assume that the input will always be valid. This means that there won't be more than 9 men of each color and that each point will be unique.

Rules

  • Make clear which input format you use in your solution. Providing an example run of your program is hightly encouraged.
  • Function or full program allowed.
  • Default rules for input/output.
  • Standard loopholes apply.
  • This is , so lowest byte-count wins. Tiebreaker is earlier submission.

Test cases

The input format here is a list of tuples with the coordinates as in the example above as first element and the state of the point second element. A point taken by white is marked as "w" and a point taken by black as "b". All other points are left out and are empty.

[("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

Happy Coding!

\$\endgroup\$
  • \$\begingroup\$ Related - a little. \$\endgroup\$ – insertusernamehere Feb 17 '16 at 19:19
  • \$\begingroup\$ I assume the colors must be contiguous as well as aligned, but it is a bit unclear. E.g. would d2, d3, d5 of the same color form a mill? \$\endgroup\$ – Robert Benson Feb 18 '16 at 14:33
  • \$\begingroup\$ @RobertBenson No it would not because d3 and d5 are not connected. Rules say: Three men of the same color form a mill when they are in a straight row of connected points.. I added some examples in this section tho to make it clear, thanks for the comment! \$\endgroup\$ – Denker Feb 18 '16 at 14:43
4
\$\begingroup\$

APL (Dyalog Classic), 26 25 bytes

-1 thanks to FrownyFrog

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

Try it online!

The argument is a 3x3x3 array of 1(black), ¯1(white), and 0(empty). The first dimension is along the concentric squares' nesting depth. The other two dimensions are along the vertical and horizontal axis.

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

We have a mill whenever summation along any axis yields a 3 or ¯3, except we must discard the four corners when summing along the first axis.

{} is a function with implicit argument

↓⍵ is split - in our case it turns a 3x3x3 cube into a 3x3 matrix of nested length-3 vectors

⍵⍪↓⍵ takes the original cube and glues the 3x3 matrix of 3-vectors below it, so we get a 4x3x3 mixed array of scalars and vectors

+/ sums along the last axis; this has the combined effect of summing the original cube along the last axis (+/⍵) and summing it along the middle axis due to the split we did (+/↓⍵)

Now we must take care of the special case for the first axis.

+⌿⍵ sums along the first axis, returning a 3x3 matrix

4 2⍴ but we must not count the corners, so we reshape it to a 4x2 matrix like this:

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

now we are only interested in the last column (BDFH), so we use the idiom ⊢/

, concatenates BDFH to the matrix we obtained before for the 2nd&3rd axis (BDFH and the matrix both happen to have a leading dimension of 4)

flattens everything we obtained so far into a single vector

| takes the absolute values

{ }∩≢ filters only the threes - the length (≢) of the input is always 3

counts them

\$\endgroup\$
  • \$\begingroup\$ Heh, I was just about to suggest that. \$\endgroup\$ – Adám Apr 13 '17 at 10:43
  • \$\begingroup\$ Can you join chat.stackexchange.com/rooms/52405/apl for a moment? \$\endgroup\$ – Adám Apr 13 '17 at 11:39
  • \$\begingroup\$ ≢{|∊(+/⍵⍪↓⍵),⊢/4 2⍴+⌿⍵}∩≢ is one shorter :) \$\endgroup\$ – FrownyFrog May 20 '18 at 15:27
  • \$\begingroup\$ @FrownyFrog thanks! edited in \$\endgroup\$ – ngn May 20 '18 at 19:42
4
+100
\$\begingroup\$

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

(the above contains some unprintable ascii characters that won't show up here, so here's a version without the btoa that can be copied and run)

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

Breaks a reference string into letter triplets that match up with mill group keys. Input is in the form of an object, where keys are the letters a-x, starting from the bottom left and ending in the top right, moving left-to-right first. Values are 1 for white, -1 for black, and 0 for blank.

Example

{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

These examples are taken from OP's examples, converted to the letter-key and number-value object. The first is from the example image, while the others are from the example set.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice job! You could compress the big string with atob. \$\endgroup\$ – ETHproductions Feb 25 '16 at 22:52
  • \$\begingroup\$ @ETHproductions Thanks! It seems to be using unprintable ascii characters though, so I'll include one without the btoa as well. Also found some other improvements that bring it down even more. \$\endgroup\$ – Mwr247 Feb 25 '16 at 23:22
2
\$\begingroup\$

Mathematica, 217 131 Bytes

While I'm sure this is not particularly competitive, here's an entry for you.

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]&

Input example:

{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"}

Allowing single-character coordinate names trivially golfs off 51 characters, making this a 166 byte solution. Naming the players 1 and 2 rather than "w" and "b" golfs off 17 further characters.

So we get

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]/.#&
\$\endgroup\$
  • \$\begingroup\$ If I understand the input formatting rules correctly, you should be able to take them in as 1 and 2. the example used w and b, but I'm fairly certain we're not restricted to that. \$\endgroup\$ – Mwr247 Feb 22 '16 at 19:44
  • \$\begingroup\$ @Mwr247 You are right. You can use any format you want, as long as it does not add additional information. I will clarify this when I'm home. \$\endgroup\$ – Denker Feb 22 '16 at 20:00
1
\$\begingroup\$

APL (Dyalog Unicode), 50 bytes

"The Objects' Solution"

While longer (29 chars) than @ngn's solution, it uses an entirely different approach: The input has the same overall structure as that solution, but all slots are represented as objects. Empty slots (including the non-existing center column) must be empty objects. while all black men must be references to the "black man" object, and all white men must be references to the "white man" object. All the objects may optionally have nice Display Forms for readability, and so the center column can optionally be made invisible.

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

Try it online!

+/ the sum of

1=() ones in

≢¨() the tallys of

  , the raveled (flattened)

  ∪/ unique sets across

  , concatenated to

  ∪⌿⍤2 unique sets down

,() concatenated to

  ⊢/ the rightmost column of

  4 2⍴ the, reshaped into four rows and two columns,

  ∪⌿ unique columnar sets

An atop operator, as supplied with AGL (ä), would bring the length down to 27 characters.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.