Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Short / Functional / Binary Matrix - (with comments) solution in Clear category for [old] The Territory of Go by namle1412
"use strict";
/*
Main purpose of this code to transform original matrix to new matrix with easier
to count.
-- Orignal --
++B++++++
+BB++++++
BB+++++++
+++++++++
+++++++++
++WWW++++
++W+W++++
++WWW++++
+++++++++
-- Goal --
1, 1, 5, 3, 3, 3, 3, 3, 3
1, 5, 5, 3, 3, 3, 3, 3, 3
5, 5, 3, 3, 3, 3, 3, 3, 3
3, 3, 3, 3, 3, 3, 3, 3, 3
3, 3, 3, 3, 3, 3, 3, 3, 3
3, 3, 6, 6, 6, 3, 3, 3, 3
3, 3, 6, 2, 6, 3, 3, 3, 3
3, 3, 6, 6, 6, 3, 3, 3, 3
3, 3, 3, 3, 3, 3, 3, 3, 3
Other developer may use object to represent a cell, - something like
{
b: true|false
w: true|false
}
- but it will be lead on to use multi matrix as the sametime (orignal matrix,
result matrix, visited matrix, etc.) and bunch of object. Instead of we
can exploited binary flag (like cmod on unix).
With:
BLACK = 1, WHITE = 2, PLACED_CELL = 4
So:
NEUTRAL = 3 (1|2), PLACED_BLACK = 5 (1|4), PLACED_WHITE = 6 (2|4)
== Conclusion ==
I was not spend enough time to optimize main function (cordGen and fillBoard)
and I feel like it just good enough to pass all test case but not worl on real
game. I'm very appricate if you have time to help me improve main function.
Instead of use spread/infection methods (set value for 4 neighbors)) we can use
check neighbors methods with easy sum method. Example:
C1 C2 C3
C4 C0 C5
C6 C7 C8
let sum = C2 | C4 | C5 | C7;
if (isWhite(sum)) C0 |= WHITE;
if (isBlack(sum)) C0 |= BLACK;
pretty easier and less operations, but I love the zombie infection scheme more.
Another thing I was not sure was checking 4 neighbors is good enough or need to
check whole 8 neighbors cell cause I never play Go before.
*/
// directions to nei
const NEIGHBORS = [[1,0],[-1,0], [0,-1], [0,1]];
// flag
const PLACED_CELL = 4, WHITE = 2, BLACK = 1;
// convert orignal board to new board using binary flag
const trans = (j) => j == 'B' ? BLACK|PLACED_CELL : j == 'W' ? WHITE|PLACED_CELL : 0;
const makeMatrixBoard = (board) => board.map(i => i.split('').map(trans));
// binary check
const check = (bin) => (data) => (data & bin) == bin;
const isWhite = check(WHITE), isBlack = check(BLACK), isPlaced = check(PLACED_CELL);
// main function
// this generator generate list of coordinates we need to visit
// TODO: should improve logic to increase performance
function* cordGen(size) {
let a = Array(size).fill(0).map((_,i) => i);
let b = a.map(i => size - 1 - i);
// nw -> se
for (let i of a) for (let j of a) yield [i,j];
// se -> nw
for (let i of b) for (let j of b) yield [i,j];
// ne -> sw
for (let i of a) for (let j of b) yield [i,j];
// sw -> ne
for (let i of b) for (let j of a) yield [i,j];
}
// main function
// this function will spread/infection nearby cell
// can replace with check logic (look comment above)
const fillBoard = (neighbors) => (scoreBoard, [r, c]) => {
neighbors.forEach(([i,j]) => {
if( 0 <= r+i && r+i < scoreBoard.length && 0 <= c+j && c+j < scoreBoard.length ) {
if(isBlack(scoreBoard[r][c]) && !isPlaced(scoreBoard[r+i][c+j])) scoreBoard[r+i][c+j] |= BLACK;
if(isWhite(scoreBoard[r][c]) && !isPlaced(scoreBoard[r+i][c+j])) scoreBoard[r+i][c+j] |= WHITE;
}
});
return scoreBoard;
}
// helper function to build return data
const count = (data, value) => data.map(i => i.filter(x => x==value).length).reduce((a,b) => a+b, 0);
const bwCounter = (scoreBoard) => ({
'B': count(scoreBoard, BLACK),
'W': count(scoreBoard, WHITE),
});
// main interface
var territory = (board) => bwCounter(Array.from(cordGen(board.length)).reduce(fillBoard(NEIGHBORS), makeMatrixBoard(board)));
var assert = require('assert');
if (!global.is_checking) {
console.log('Example:')
console.log(territory(['++B++++++',
'+BB++++++',
'BB+++++++',
'+++++++++',
'+++++++++',
'++WWW++++',
'++W+W++++',
'++WWW++++',
'+++++++++']))
// These "asserts" are used for self-checking and not for an auto-testing
assert.deepEqual(territory(['++B++++++',
'+BB++++++',
'BB+++++++',
'+++++++++',
'+++++++++',
'++WWW++++',
'++W+W++++',
'++WWW++++',
'+++++++++']), {'B': 3, 'W': 1})
console.log("Coding complete? Click 'Check' to earn cool rewards!");
}
Aug. 29, 2018
Comments: