Tic-Tac-Toe and Chess, with fewest [distinct] characters

9

1

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.

Ypnypn

Posted 2014-11-09T19:02:49.160

Reputation: 10 485

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. – trichoplax – 2015-01-26T15:42:43.880

So oOo code is going to win?

– kennytm – 2014-11-09T19:07:53.970

@KennyTM No char may appear more than X times will render oOo useless – Optimizer – 2014-11-09T19:09:22.863

@Optimizer OK sorry misread the rules. – kennytm – 2014-11-09T19:43:51.780

2Could 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. – Tally – 2014-11-09T19:44:12.777

Is whitespace allowed? – None – 2014-11-09T20:53:56.530

Are you OK with things like exec(encode(len(s))) where s is a ginormous string of spaces, more than there are atoms in the universe? – xnor – 2014-11-09T21:15:12.617

@xnor Sure, but that won't win, since "no character may appear more than X times" – Ypnypn – 2014-11-09T22:03:38.250

@MartinBüttner I've allowed using letters instead of Unicode symbols. – Ypnypn – 2014-11-09T22:09:13.427

@Tally See above comment. – Ypnypn – 2014-11-09T22:10:05.867

@ciuak Wwhitespace characters are treated like any other kind of character. – Ypnypn – 2014-11-09T22:10:31.760

I've made some 4×4 boards based on the examples given. If they need to be changed, you can edit the markup here and paste into the Wikipedia sandbox to see the results. – r3mainer – 2014-11-10T02:56:03.600

@squeamish Thanks. The K stands for knight, not king. And the fourth example has the queen and bishop in the center columns, not the rightmost ones. – Ypnypn – 2014-11-10T02:59:05.107

Answers

3

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 << "`, ";
}

Toby Speight

Posted 2014-11-09T19:02:49.160

Reputation: 5 058