4
\$\begingroup\$

EDITS:

  • Added link to the plain-text (multiple strings) test data
  • Added BLANK,EDGE and TIE2 test cases (see Test Data section) (11/25)
  • Updated the JSON test cases (some lines were ill-formatted) (11/24)

Renju match gone bad !

Renju match gone bad ! (well, technically these guys are playing Go, but who cares) Wikisource

TL;DR

Take a 15x15 grid of characters (made of '.', '0' and '*'), as an input, replace one of '.' s with '*', in such a way that an unbroken horizontal, vertical or diagonal line of exactly five '*' chars is formed.

           *        *    * 
           *       *      *
 ******    *      *        *
           *     *          *
           *    *            *

Output the coordinates of your '*', or string - 'T' if there is no solution.

Creating a line of more than 5 '*' long (directly or indirectly) is not allowed, this is called an "overline".

Some examples of overlines:

 ****.** - replacing . with * will result in a horizontal overline


 *.***  - replacing . with * will result in a diagonal overline 
   *
    *
     *
      *
       *

Full Version

Abstract

Renju - is an abstract strategy board game (a simpler version of it is also known as Gomoku).

The game is played with black and white stones on a 15×15 gridded Go board.

Black plays first if white did not just win, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five stones horizontally, vertically, or diagonally.

Computer search by L. Victor Allis has shown that on a 15×15 board, black wins with perfect play. This applies regardless of whether overlines are considered as wins.

Renju eliminates the "Perfect Win" situation in Gomoku by adding special conditions for the first player (Black).

(c) Wikipedia

Objective

Consider you are a part of a Renju match, you are playing black, and there is just one turn left for you to win.

Take the current board position as an input, identify one of the winning moves (if there is one), and output it (see below for the data formats and restrictions).

Sample input board:

    A B C D E F G H J K L M N O P       . - vacant spot (intersection) 
 15 . . . . . . . . . . . . . . . 15    0 - white stone
 14 . . . . . . . . . . . . . . . 14    * - black stone
 13 . . . . . . . . . . . . . . . 13    X - the winning move
 12 . . . . . . . . . . . . . . . 12    
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . 0 . . . . . . . 10
  9 . . . . . . . * . . . . . . .  9
  8 . . . . . . . * . . . . . . .  8
  7 . . . 0 . . . * . . . . . . .  7
  6 . . . 0 0 . . * . . . . . . .  6
  5 . . . . . . . X . . . . . . .  5
  4 . . . . . . . . . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

(axis labels are for illustration purposes only and are not part of the input)

Sample output:

H5

Rules

For the purpose of this challenge, only the following subset of Renju rules apply:

  • You can place your stone on any vacant intersection (spot);

  • Player who achieved an unbroken row of five stones horizontally, vertically, or diagonally, wins;

  • Black (you) may not make a move which will result (directly or indirectly) in creation of an "overline" i.e. six or more black stones in a row.

Data Formats

Input data is a 15x15 grid of characters (".","*","0"]), ASCII-encoded, in any acceptable format, e.g. a two-dimensional character array or a newline separated set of strings e.t.c.

You may not however modify the input alphabet in any way.

Output data is a string, denoting the alpha-numeric board position, as illustrated by the sample board above.

Note that original horizontal axis numeration (A..P), does not include 'I', you MAY use 'A..O' instead, w/o penalty.

If there is no winning move available, output "T" instead.

Scoring

This is , so the shortest answer in bytes wins !

Some Tests Cases

Tie

Input:

    A B C D E F G H J K L M N O P
 15 . . . . . . . . . . . . . . . 15
 14 . . . . . . . . . . . . . . . 14
 13 . . . . . . . . . . . . . . . 13
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . 0 . . . . . . . 10
  9 . . . . . . . * . . . . . . .  9
  8 . . . . . . . * . . . . . . .  8
  7 . . . 0 . . . * . . . . . . .  7
  6 . . . 0 0 . . * . . . . . . .  6
  5 . . . . . . . Z . . . . . . .  5
  4 . . . . . . . * . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

Output:

 "T", the only "winning move" is H5 (denoted with "Z"), but that would create an overline H4-H9

Overline

Input:

    A B C D E F G H J K L M N O P
 15 . . . . . . . . . . . . . . . 15
 14 . . . . . . . . . . . . . . . 14
 13 . . . . . . . . . . . . . . . 13
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . . . . . . . . . 10
  9 . . . . . 0 . . . . 0 . . . .  9
  8 . . 0 . . . . . . * 0 0 . . .  8
  7 . . 0 . . . . . * . . 0 . . .  7
  6 . . 0 * . 0 . * . . 0 0 . . .  6
  5 . . 0 . * . * X * * * . . . .  5
  4 . . . . . Z . . . . . . . . .  4
  3 . . . . . . * . . . . . . . .  3
  2 . . . . . . . * . . . . . . .  2
  1 . . . . . . . . * . . . . . .  1
    A B C D E F G H J K L M N O P

Output:

 "H5", the other possible winning move is "F4", but that would result in J1-D6 diagonal overline.

Multiple winning moves

Input:

    A B C D E F G H J K L M N O P
 15 . * * * . . * * * . . . . . . 15
 14 . * . . . . . * . . * . . . . 14
 13 . * . . . . . . . . . . . * . 13
 12 . . . . . 0 0 0 0 0 0 0 . * . 12
 11 . . . . 0 . . X . . . 0 . * * 11
 10 . . . . 0 X * * * * X 0 . . * 10
  9 . . . . 0 . . * . . . 0 . * *  9
  8 . . . . 0 0 . * . . 0 0 . * .  8
  7 . . . . . 0 . * . . 0 . . * .  7
  6 . . . . . 0 . X . . 0 . . . .  6
  5 . . . . . 0 0 0 0 0 0 . . . *  5
  4 . . . . . . . . . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

Output:

"H6" or "H11" or "F10" or "L10" (one of)

Test Data

The test data in a bit more machine-friendly form (JSON) is available HERE

Added BLANK,EDGE and TIE2 test cases: UPDATED TEST SUITE

You can use the following JS snippet to convert it to multiline strings, if necessary:

for(B in RENJU) { console.log(B+"\n"+RENJU[B].map(l=>l.join``).join`\n`); }

or just download them here

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd recommend giving the test cases as they'd appear to the program, not in the form that's clearest for a human to see. That will make it much easier to test submissions. \$\endgroup\$ – user62131 Nov 23 '16 at 20:18
  • \$\begingroup\$ @ais523 - I've posted JSON-formatted input data for the test cases to the Pastebin (see my update) \$\endgroup\$ – zeppelin Nov 23 '16 at 21:07
  • \$\begingroup\$ Jesus George! Can we please have columns from A to O instead of A to H and J to P!?! \$\endgroup\$ – Titus Nov 25 '16 at 12:26
  • \$\begingroup\$ @Titus, sure, I'll update the rules now to allow for this \$\endgroup\$ – zeppelin Nov 25 '16 at 12:43
1
\$\begingroup\$

JavaScript (ES6), 161

Input as multiline string.

Note: could save 1 byte using A..O instead of A..P

s=>[...s].some((q,p)=>([1,15,16,17].map(d=>x=(q=((r=p=>s[p-d]=='*'?r(p-d):p)(a=p)-r(p,d=-d))/d)>x?q:x,x=q!='.'&&5),x==4))?'ABCDEFGHJKLMNOP'[a%16]+(15-(a>>4)):'T'

Less golfed

s=>
[...s].some( 
  (q, p) => // execute for each character q in position p, stop when true
  (
    [1, 15, 16, 17].map( // offset for 4 directions
      d => // for each direction d
      (
        // recursive function to find adjacent '*' in direction -d
        r = p => s[p-d] == '*' ? r(p-d) : p,
        // I need 4 adjacent '*' in at least 1 direction
        // but no more in any direction
        a = p, // current position in a, could be the answer
        q = r(p), // look back (reuse variable q)
        d = -d, q -= r(p), // then look forward
        q = q/d, // number of '*' in q
        x = q > x ? q : x // keep the max in any direction
      ),
      // init x to 0 if the current position is empty
      // else init x to 5, so it will be not valid in any case (too big)
      x = q !='.' && 5
    ),
    // if 4 '*' found, exit the loop
    x==4
  )
) // return true if solution found (solution in a)
? 'ABCDEFGHJKLMNOP'[a % 16] + (15 - ( a >> 4))
: 'T'

Test

F=
s=>[...s].some((q,p)=>([1,15,16,17].map(d=>x=(q=((r=p=>s[p-d]=='*'?r(p-d):p)(a=p)-r(p,d=-d))/d)>x?q:x,x=q!='.'&&5),x==4))?'ABCDEFGHJKLMNOP'[a%16]+(15-(a>>4)):'T'

out=x=>O.textContent+=x+'\n\n'

;renju = {
"BLANK":"...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............",
"EDGE":"...........****\n.0.............\n.0.............\n.0.............\n.00000.........\n.....0.........\n.....0.........\n.....0.........\n.....0.........\n...............\n...............\n.....*........*\n....*.........*\n...*..........*\n..*...........*",
"TIE":"...............\n...............\n...............\n...............\n...............\n.......0.......\n.......*.......\n.......*.......\n...0...*.......\n...00..*.......\n...............\n.......*.......\n...............\n...............\n...............",
"TIE2":"...............\n.....0****000..\n...............\n.*0............\n..*.0..........\n..0*...0.......\n.......*.......\n.......*.......\n.......*.00....\n.......*.......\n.......0.......\n...............\n...............\n...............\n...............",
"OVERLINE":"...............\n...............\n...............\n...............\n...............\n...............\n.....0....0....\n..0......*00...\n..0.....*..0...\n..0*.0.*..00...\n..0.*.*.***....\n...............\n......*........\n.......*.......\n........*......",
"MULTIPLE":"...............\n...............\n...............\n.....0000000...\n....0......0...\n....0.****.0...\n....0..*...0...\n....00.*..00...\n.....0.*..0....\n.....0....0....\n.....000000....\n...............\n...............\n...............\n..............."
};

for(k in renju) {
  var r=F(renju[k])
  out(k+' '+r+'\n   ABCDEFGHJKLMNOP\n'+renju[k].split`\n`.map((v,i)=>(115-i+' ').slice(1)+v).join`\n`)
}
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ So you need the parens around 15-(a>>4)? \$\endgroup\$ – Zacharý Dec 1 '16 at 23:02
  • \$\begingroup\$ @ZacharyT yes. String + number - number === NaN \$\endgroup\$ – edc65 Dec 2 '16 at 7:45
2
\$\begingroup\$

PHP, 205 203 201 246 257 238 bytes

requires PHP<7.1 (relies on empty negative string offsets)

third approach, finally really complete, and I think I have left nothing to golf.

for($p=240;(!$l|$o)&&$p--;)for($k=4,$l=$o=0;$k--;$l|=preg_match("#\*{5}#",$s),$o+=preg_match("#\*{6}#",$s))for($s="*",$i=0;"."==($g=$argv[1])[$p]&&$i++<5;)$s=$g[$p-$i*$d=!$k?:$k+14].$s.$g[$p+$d*$i];echo$p<0?T:chr(65+$p%16).(15-($p/16|0));

takes multiline string with Linux style linebreaks (1 character) from command line argument.
For 2 character linebreak: add one each to 14, 15 and 16 and replace 240 with 255.

Run with -r.

breakdown

for($p=240;(!$l|$o)&&$p--;)     // loop through positions while (no line or has overlines)
    for($k=4,$l=$o=0;$k--;          // loop through four directions
        $l|=preg_match("#\*{5}#",$s),   // post condition: set flag for line
        $o+=preg_match("#\*{6}#",$s)    // and count overlines
        )
        for($s="*",                     // assume asterisk at current position
            $i=0;
            "."==($g=$argv[1])[$p]      // if character is "."
            &&$i++<5;)                  // look 5 fields in +/- direction:
            $s=$g[$p-$i*
                $d=!$k?:$k+14               // map [3,2,1,0] to offset [17,16,15,1]
            ].$s.$g[$p+$d*$i];              // add characters
                                // output
echo$p<0?T:chr(65+$p%16).(15-($p/16|0));

uses columns A..O. For A..H+J..P, append +($p/8&1) to the chr parameter.

\$\endgroup\$
  • \$\begingroup\$ Nice, but does this work for "Tie" and "Overline" test cases ? (I can not recognize any overline detection code) \$\endgroup\$ – zeppelin Nov 24 '16 at 16:40
  • \$\begingroup\$ @zeppelin: At the top or bottom of the board, empty strings will be appended to $s and strlen will never hit 5. And if $s contains newline or 0, the preg_match will fail. \$\endgroup\$ – Titus Nov 24 '16 at 16:47
  • \$\begingroup\$ Well, I meant the "overline", as defined by the rules, i.e. a string 6 or more '*' long, within the board (take a look at "Tie" and "Overline" test case illustrations). \$\endgroup\$ – zeppelin Nov 24 '16 at 16:50
  • \$\begingroup\$ @zeppelin: Oh I missed that one. I guess that will require some editing. Probably easier with the other approach that I´m currently working on. \$\endgroup\$ – Titus Nov 24 '16 at 17:12

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.