16
1
Bounties
No. 1 (awarded)
I'll throw in 50 rep for the first valid answer
No. 2 (awarded)
I'll throw in another 100 rep for the shortest valid answer.
No. 3 (open for submissions)
I'll throw in 200 rep for the first one with a significant shorter valid answer. Significant being at most 45% of currently shortest answer (564 bytes x 0.45 = max 254 bytes).
The Game
You remember the classic game "Nine Men's Morris" or simply "Mill"? There's a variation called Three Men's Morris which is a bit like a mutable tic-tac-toe.
Rules
This is the blank board of the game:
a b c
1 [ ]–[ ]–[ ]
| \ | / |
2 [ ]–[ ]–[ ]
| / | \ |
3 [ ]–[ ]–[ ]
[ ]
is a field and |–/\
represent routes between those fields.
The game is played by two players 1
and 2
who each place 3 tokens on the board. This actually happened already and we are in the game. The game is won if one player can form a mill
which is a vertical or horizontal row of the player's 3 tokens.
Tokens can be moved on the board along the connecting lines, according to this rule:
To any adjacent empty position (i.e. from an edge position to the center, or from the center to an edge position, or from an edge position to an adjacent edge position
A player must make a move unless there's no adjacent empty position, in which case the move is skipped.
The Challenge
You're player 1
and your move is next. Write a program or a function, that determines whether:
- you can force a win with 2 or less moves (definite win)
- you can win with 2 or less moves, if your opponent makes a mistake (possible win)
- you cannot win with 2 or less moves, because you'll need more moves or because forced moves lead your opponent to win (impossible to win)
Requirements
- Even though you definitely win when you bore your opponent to death, your program must finish in finite time.
- You can write a program or a function.
Input
The players are represented by 1
and 2
. 0
defines a free field. You can take input as a matrix or an array.
Definite
A B C D
2 1 0 | 2 1 0 | 1 0 1 | 1 2 2
2 1 2 | 0 1 0 | 1 0 2 | 2 1 O
0 0 1 | 2 2 1 | 0 2 2 | O O 1
A: [2,1,0,2,1,2,0,0,1]
B: [2,1,0,0,1,0,2,2,1]
C: [1,0,1,1,0,2,0,2,2]
D: [1,2,2,2,1,0,0,0,1]
Possible
A B C
1 0 1 | 1 0 1 | 1 2 2
1 2 2 | 1 2 0 | 0 0 1
2 0 0 | 2 0 2 | 2 1 0
A: [1,0,1,1,2,2,2,0,0]
B: [1,0,1,1,2,0,2,0,2]
C: [1,2,2,0,0,1,2,1,0]
Impossible
A B
1 0 0 | 1 2 0
1 2 2 | 2 1 0
2 0 1 | 1 2 0
A: [1,0,0,1,2,2,2,0,1]
B: [1,2,0,2,1,0,1,2,0]
Output
Your program should output/return a smiley:
- Definite win:
:)
- Possible win:
:|
- Impossible to win:
:(
Examples
Definite win in two moves:
[2][1][ ] 1. [2][1][ ]
[2][1][2] -> [2][1][2]
[ ][ ][1] [ ][1][ ]
[2][1][ ] 1. [2][1][ ] [ ][1][ ] 2. [ ][ ][1]
[ ][1][ ] -> [ ][ ][1] -> [2][ ][1] -> [2][ ][1]
[2][2][1] [2][2][1] [2][2][1] [2][2][1]
[1][ ][1] 1. [ ][1][1] [ ][1][1] 2. [1][1][1]
[1][ ][2] -> [1][ ][2] -> [1][ ][2] -> [ ][ ][2]
[ ][2][2] [ ][2][2] [2][ ][2] [2][ ][2]
Possible win in two moves:
[1][ ][1] 1. [ ][1][1] [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2] [2][ ][2] [2][ ][ ] [2][ ][ ]
[1][ ][1] 1. [ ][1][1] [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2] [2][ ][2] [2][ ][ ] [2][ ][ ]
[1][2][2] 1. [ ][2][2] [2][ ][2] 2. [1][2][2]
[ ][ ][1] -> [1][ ][1] -> [1][ ][1] -> [1][1][1]
[2][1][ ] [2][1][ ] [2][1][ ] [2][ ][ ]
Impossible to win in two moves:
[1][ ][ ]
[1][2][2]
[2][ ][1]
Bonus
In case a definite win is possible and your program outputs the moves of one way to success as well like a1:a2
(1 move) or a1:a2,a3:b2
(2 moves), you can withdraw 30% of your byte count.
This is code golf – so shortest answer in bytes wins. Standard loopholes are disallowed.
Thanks to Peter Taylor who fixed some flaws and improved wording in the Sandbox.
Related . – insertusernamehere – 2015-11-18T10:08:48.247
1I like those ascii tables/graphics=) – flawr – 2015-11-18T16:38:09.913
1What happens if a player is unable to move? e.g. in
[1,0,0,2,1,0,2,2,1]
, player 2 cannot move - is this a win for player 1? – VisualMelon – 2015-11-25T13:01:56.267@VisualMelon Good addition. I've edited it into the question: "A player must make a move unless there's no adjacent empty position, in which case the move is skipped.". – insertusernamehere – 2015-11-25T13:20:52.550
Impossible test case C looks like it's a definite win to me (6->4, 4->2) and Impossible B looks like a possible. – VisualMelon – 2015-11-25T13:46:33.767
@VisualMelon but cant you move diagonally? so it comes out to [1,2,0,0,1,0,2,2,1] ? – Eumel – 2015-11-25T13:58:22.313
@VisualMelon You're right, impossible C was a definite win. I removed it. I also updated impossible B. It's hard to find impossible variants. – insertusernamehere – 2015-11-25T14:02:40.880
@VisualMelon I believe the state you give is (modulo symmetries) the only in which a player can't move. But the other has already won! – Leif Willerts – 2015-11-25T14:10:21.000
1@LeifWillerts I might be misunderstanding what you mean, but in that case, no player is in a winning state - they only win by having a horizontal or vertical line (not diagonal). – VisualMelon – 2015-11-26T13:07:36.180
uhm actually thinking about it, there is no impossible win, considering player 2 is stupid enough there is always a possibility to win – Eumel – 2015-11-26T14:31:25.703
i take it back, i misread the rules – Eumel – 2015-11-26T14:41:54.880
3Well, there are only 1680 valid board positions, so hardcoding can give a little over 210 bytes. (fewer if symmetry is considered) – lirtosiast – 2015-12-01T23:06:16.403
Curious, how to go from 1680 to 210? – Leif Willerts – 2015-12-08T17:43:46.373