Code Golf Asked by Ypnypn on January 21, 2021
In this form of the game Tic-Tac-Chec, the goal is to move chess pieces to get four-in-a-row. Your goal here is to figure out if a position has a winning move.
The rules are similar, but not identical, to those of Tic-Tac-Chec.
The board is 4 by 4 squares. Each player has a rook, bishop, knight, and queen. On your turn, you have two options. You can move one of your pieces already on the board, following standard chess rules. Or you can place a piece not already on the board, on any unoccupied place.
If you move an existing piece onto an opponent’s piece, their piece is taken off the board and returned to them. However, you may not place a new piece on top of an opponent’s piece.
As soon as one player has all of their pieces in a row (or column, or diagonal), they win.
Write a full program that accepts a board from STDIN, and outputs whether the white player can win on the next turn.
Four strings of 4 characters each. Each character is either a space or a chess piece. Only rooks, bishops, knights, and queens are used, and at most one of each (per color) may appear. Neither player already has a four-in-a-row.
You can choose whether to accept as input the Unicode symbols for the chess pieces, or letters. If you choose letters, RBKQ
represents white pieces, and rbkq
represents black pieces.
If the white player can win on the next turn, output true
or 1
. Otherwise, output false
or 0
.
Choose a number X. Your program may contain at most X distinct characters, and no character may appear more than X times.
Lowest X wins. In case of a tie, fewest characters wins.
These examples assume the input uses letters to represent the pieces.
rkb
RB Q
true - the white player can place the knight to complete the bottom row.
-----------------------------------
rk
RBbQ
false - the black bishop prevents the white knight from completing the row.
-----------------------------------
rk
K
RBbQ
true - the white knight can capture the black bishop and complete the row.
-----------------------------------
rkRB
Qb
K
true - the white rook can move down one to complete the diagonal.
{Q←(QQ←⍴⍵)[1]
R←∨/¨⍵=⊂'RBQK'
B←({⍵(⍵[↑(⍳Q),¨¨⊂1--Q-⍳Q])}↑(⍳Q)=⊂⍳Q),{⍵,{⍵[{⍵[(1--1)1]}¨⍳QQ]}¨⍵}(⊂QQ)⍴¨(⍳Q)=⊂⍳Q
K←(Q-1)={∨/1↑⍴{(,⍵)/,⍳⍴⍵}⍵}¨B×⊂R
1-∨/K:1-1
K←↑∨/K/B
BB←{(,⍵)/,⍳⍴⍵}K×1-R
R←↑∨/BB-B←{(,⍵)/,⍳⍴⍵}R×1-K
1-⍴B:⍵[BB]=1↑''
BB←(1-∨/¨'RBQK'=⊂⍵[(,K)/,⍳⍴K])/'RBQK'
'K'=BB:×/∨/¨(⍳1--1)=⊂R∨-R
1-∨/(1-(⍳1--1)='RB'⍳BB)×(=/,{∨/1-×⍵})R∨-R:1-1
×/(1↑'')=⍵[B--(×⊂R)×⍳-1-∨/R]}↑⍞⍞⍞⍞
Character statistics:
- 1 B ) ( ⍵ / Q ⍳ R ' ∨ LF K , = ← } { ⊂ × ¨ ⍴ ↑ ] [ ⍞ :
27 26 22 20 20 19 19 18 15 15 14 12 12 12 12 11 10 10 10 9 9 9 8 8 7 7 4 4
chars 28
Decisions made during optimizing the score:
:
is needed for early returns from a dfn {}
. Either LF (n
) or a statement separator character ⋄
cannot be removed as a side effect.RBQK
as avoiding it requires at least ⎕A
and the code would get messy.∘
, reflex/flip ⍨
, and self ⊢
in favor of dfns and explicitly writing down arguments with parentheses.≢
(tally) in favor of ⍴
(shape/reshape), as tally = first element of shape, and reshape is unavoidable.⍉
(transpose) and ⌽
(reverse/rotate) in favor of explicit indexing []
combined with index generator ⍳
. Although there are one-char functions to do the indexing (⌷
, ⊃
), none is suitable for transpose operation.⊃
(first/pick) in favor of ↑
(mix/take), as take is unavoidable and indexing+mix can simulate both uses of ⊃
.∧
(logical and) in favor of ×
(times), and |
(abs/mod) by using the workaround x∨-x
for |x
(abs) and explicit membership ∊
(which was removed later) for x|y
(mod). ⊤
was also removed that way.∘.f
in favor of f⊂
or f¨⊂
. Similar trick was used to simulate ∊
(membership) and ~
(set minus): x∊y → ∨/¨x=⊂y
, x~y → (1-∨/¨x=⊂y)/x
⍸
(extract indices of ones) with the workaround (,x)/,⍳⍴x
.1-1
, four by extracting from ⍴⍵
, and +
with --
.' '
. I avoided it with 1↑''
, which "overtakes" length 1 from an empty string and gives a single blank. (It is a slightly different thing from the literal ' '
, but they are compatible in most cases.){
⍝ 4×4 boolean matrix where 1 means a white piece
whites←⍵∊'RBKQ'
⍝ one matrix per a winning position; roughly looks like
⍝ 1 0 0 0 ... 1 1 1 1 ... 1 0 0 0
⍝ 1 0 0 0 0 0 0 0 0 1 0 0
⍝ 1 0 0 0 0 0 0 0 0 0 1 0
⍝ 1 0 0 0 0 0 0 0 0 0 0 1
masks←((⊂,⊂∘⌽)∘.=⍨⍳4),(⊢,⍉¨)(⍳4)⌽¨⊂4 4⍴4↑1
⍝ 1 if the white is about to win in that specific winning position
filter←3=masks{≢⍸⍺∧⍵}¨⊂whites
⍝ No three-in-a-row: return false
~∨/filter:0
⍝ fetch the mask closest to white's winning
mask←(⍸filter)⊃masks
⍝ coordinates of misplaced piece (from) and empty position (to)
from←⍸whites>mask
to←⍸whites<mask
⍝ No from: the remaining place must be empty
~≢from:' '=⍵[to]
⍝ get the type of the piece to move
type←'RBKQ'~⍵[⍸mask]
⍝ Knight: true if 1×2 steps away, ignoring any obstacles
'K'=type:∧/1 2∊|⊃from-to
⍝ two booleans indicating if it can move in diagonals (BQ) or
⍝ cardinal directions (RQ)
diag cross←0 2⊤⊃'RB'⍳type
⍝ two booleans indicating if the direction to move is actually
⍝ diagonal or cardinal
isdiag←=/|⊃from-to
iscross←0∊|⊃from-to
⍝ Not aligned with the piece to move: return false
diag cross⍱.∧isdiag iscross:0
⍝ If aligned, true if all cells between from and to are blanks
∧/' '=¯1↓⍵[from+(×v)×⍳⌈/⊃|v←to-from]
}↑{⍞}¨⍳4 ⍝ Take 4 lines of input, format as matrix and pass to function
Answered by Bubbler on January 21, 2021
This uses "#%&()*+,-./01234569;<=>BKQR[]acdefghilmnoprstu{|}
, space and newline, distributed as follows: 24×n
, 33×, 20×
"
, 2×#
, 3×%
, 16×&
, 46×(
, 46×)
, 13×*
, 12×+
, 35×,
, 10×-
, 2×.
, 2×/
, 18×0
, 9×1
, 4×2
, 4×3
, 4×4
, 4×5
, 3×6
, 3×9
, 34×;
, 6×<
, 46×=
, 2×>
, 2×B
, 2×K
, 3×Q
, 2×R
, 8×[
, 1×, 8×
]
, 39×a
, 23×c
, 5×d
, 19×e
, 15×f
, 1×g
, 22×h
, 36×i
, 5×l
, 1×m
, 35×n
, 9×o
, 33×p
, 44×r
, 20×s
, 43×t
, 15×u
, 8×{
, 14×|
, 8×}
.
#include <stdio.h>
#include <string.h>
int n(char*a,char*e,int i)
{int c=0;for(;a<e;)c+=*a++=="n"[0];return c==i;}
int p(char *t, int r, int u)
{char h[]=" RBQK";char*p=t+r;char*a;int c=0;
for(int i=0;i<=3;++i,p+=u){char*s=strchr(h,*p);if(s&&s==h==0){++c;*s=" "[0];}else{a=p;}}
if(c-3)return 0;
char o=h[strspn(h, " ")];
p=strchr(t, o);
if(p==0)return*a==" "[0];
if(p<a){char*s=p;p=a;a=s;}
if(o=="K"[0])return(p-a)==3&&n(a,p,1)||(p-a)==2+5&&n(a,p,1)||(p-a)==9&&n(a,p,2)||(p-a)==11&&n(a,p,2);
if((p-a)%5==0||n(a,p,0))return (int)strchr("RQ", o);
return((p-a)%4==0&&n(a,p,(p-a)/4)||(p-a)%6==0&&n(a,p,(p-a)/6))&&strchr("BQ",o);}
int f(char *t)
{for(int i=0;i<4;++i)if(p(t,i,5)||p(t,i*5,1))return 1;
return p(t,0,6)||p(t,3,4);}
int main()
{char t[20];fread(t,19,1,stdin);t[19]=0;
if(f(t))puts("true");else puts("false");}
#include <stdio.h>
#include <string.h>
/* count newlines */
int n(char *a, char *e)
{
int c = 0;
for (;a<e;) c += *a++=='n';
return c;
}
/* check a single row, column or diagonal */
int p(char *t, int start, int stride)
{
char h[] = " RBQK"; /* pieces not in line */
char *p = t+start;
char *a;
int c = 0;
for (int i = 0; i <= 3; ++i, p+=stride) {
char *s = strchr(h, *p);
if (s && s == h == 0) {
/* a white piece */
++c;
*s = " "[0];
} else {
/* candidate target square */
a = p;
}
}
/* did we find three white pieces in this line? */
if (c != 3)
return 0;
char o = h[strspn(h, " ")];
p = strchr(t, o);
if (p==0)
return *a == " "[0];
/* ensure a < p */
if (p < a) {
char *s = p;
p = a;
a = s;
}
/* knight moves */
if (o == 'K')
return (p-a)==3 && n(a,p)==1
|| (p-a)==7 && n(a,p)==1
|| (p-a)==9 && n(a,p)==2
|| (p-a)==11 && n(a,p)==2;
/* rook moves */
if ((p-a)%5 == 0 || n(a,p)==0)
return 0==strchr("RQ", o)==0;
/* bishop moves */
return
((p-a)%4==0 && n(a,p)==(p-a)/4 ||
(p-a)%6==0 && n(a,p)==(p-a)/6)
&& strchr("BQ", o);
}
/* main predicate function */
int f(char *t)
{
/* try rows and columns */
for (int i = 0; i < 4; ++i)
if (p(t, i, 5) || p(t, i*5, 1))
return 1;
/* try diagonals */
return p(t, 0, 6) || p(t, 3, 4);
}
int main()
{
char t[20];
fread(t, 19, 1, stdin);
t[19]=0;
if (f(t)) puts("true"); else puts("false");
}
It works by looking for a row, column or diagonal containing three of the white pieces; a
points to the target position (not already containing a white piece). Then the missing piece (o
) is identified - it's the one we didn't remove from string h
as we saw it.
If the piece is not on the board, it must be in the hand, and it can only be played into a space. Otherwise (if we found it on the board), it must be in a position where it can move into the target square. Since moves are reversible, we swap if necessary, so that a < p
.
We test knight moves first - there are four legal downwards moves, and we avoid wrapping around the left/right edges of the board by verifying the number of newlines we pass.
After that, we test rook moves, and then bishop moves, using a similar algorithm (and a queen can use either of these moves).
int expect_true(char *board)
{
if (strlen(board) != 19) {
fprintf(stderr, "Wrong length board:n%snn", board);
return 1;
}
if (!f(board)) {
fprintf(stderr, "Expected true, but got false, forn%snn", board);
return 1;
}
return 0;
}
int expect_false(char *board)
{
if (strlen(board) != 19) {
fprintf(stderr, "Wrong length board:n%snn", board);
return 1;
}
if (f(board)) {
fprintf(stderr, "Expected false, but got true, forn%snn", board);
return 1;
}
return 0;
}
int main()
{
return
+ expect_true("rkb n"
" n"
" n"
"RB Q")
+ expect_false("rk n"
" n"
" n"
"RBbQ")
+ expect_true("rk n"
" K n"
" n"
"RBbQ")
+ expect_true("rk n"
" n"
"K n"
"RBbQ")
+ expect_true("rkRBn"
" n"
" Qb n"
"K ")
+ expect_true("rk n"
" n"
"K n"
"RBbQ");
}
#include<algorithm>
#include<iostream>
#include<map>
int main()
{
std::map<char,int> m;
for (int c; (c = getchar()) != EOF; )
++m[c];
for (auto e: m)
std::cout << e.first;
std::cout << "n distributed as follows: ";
for (auto e: m)
std::cout << e.second << "×`" << e.first << "`, ";
}
Answered by Toby Speight on January 21, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP