12
\$\begingroup\$

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.

Rules

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.

Challenge

Write a full program that accepts a board from STDIN, and outputs whether the white player can win on the next turn.

Input

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.

Output

If the white player can win on the next turn, output true or 1. Otherwise, output false or 0.

Program

Choose a number X. Your program may contain at most X distinct characters, and no character may appear more than X times.

Winning

Lowest X wins. In case of a tie, fewest characters wins.

Examples

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.
\$\endgroup\$
13
  • \$\begingroup\$ So oOo code is going to win? \$\endgroup\$
    – kennytm
    Nov 9 '14 at 19:07
  • \$\begingroup\$ @KennyTM No char may appear more than X times will render oOo useless \$\endgroup\$
    – Optimizer
    Nov 9 '14 at 19:09
  • \$\begingroup\$ @Optimizer OK sorry misread the rules. \$\endgroup\$
    – kennytm
    Nov 9 '14 at 19:43
  • 2
    \$\begingroup\$ Could the examples be put into a more legible format, it is quite difficult to see what the positions of the pieces are and to which colour they belong. \$\endgroup\$
    – Tally
    Nov 9 '14 at 19:44
  • 1
    \$\begingroup\$ The repeated confusion about the winning criterion is due to the misleading title. it sounds like you are scoring based on least duplication of characters, but the title still states fewest distinct characters. \$\endgroup\$
    – trichoplax
    Jan 26 '15 at 15:42
5
+200
\$\begingroup\$

APL (Dyalog Unicode), 369 characters, score 28

{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]}↑⍞⍞⍞⍞

Try it online!

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:

  • Boolean guard : is needed for early returns from a dfn {}. Either LF (\n) or a statement separator character cannot be removed as a side effect.
  • I didn't try to avoid four letters RBQK as avoiding it requires at least ⎕A and the code would get messy.
  • Removed composition , reflex/flip , and self in favor of dfns and explicitly writing down arguments with parentheses.
  • Removed (tally) in favor of (shape/reshape), as tally = first element of shape, and reshape is unavoidable.
  • Removed (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.
  • Removed (first/pick) in favor of (mix/take), as take is unavoidable and indexing+mix can simulate both uses of .
  • Removed (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.
  • Removed ∘.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
  • Removed (extract indices of ones) with the workaround (,x)/,⍳⍴x.
  • Removed zero with 1-1, four by extracting from ⍴⍵, and + with --.
  • Removing blanks in plain code is easy, but this code has ' '. 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.)

Ungolfed with comments

{
  ⍝ 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
\$\endgroup\$
4
\$\begingroup\$

C, 53 distinct chars

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");}

Explanation

#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).

Test program

int expect_true(char *board)
{
    if (strlen(board) != 19) {
        fprintf(stderr, "Wrong length board:\n%s\n\n", board);
        return 1;
    }
    if (!f(board)) {
        fprintf(stderr, "Expected true, but got false, for\n%s\n\n", board);
        return 1;
    }
    return 0;
}

int expect_false(char *board)
{
    if (strlen(board) != 19) {
        fprintf(stderr, "Wrong length board:\n%s\n\n", board);
        return 1;
    }
    if (f(board)) {
        fprintf(stderr, "Expected false, but got true, for\n%s\n\n", 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("rkRB\n"
                       "    \n"
                       " Qb \n"
                       "K   ")
        + expect_true("rk  \n"
                      "    \n"
                      "K   \n"
                      "RBbQ");
}

Counting program (in C++)

#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 << "`, ";
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Suggest 6+3 for 9 And 16+3 for 19 \$\endgroup\$
    – ceilingcat
    Mar 14 '20 at 23:55

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.