مساله:
متدی بنویسید که فیلدی برای بازی رومیزی معروف “Battleship” به عنوان ورودی بگیرد و اگر وضعیت کشتی ها درست بود عبارت true و در غیر اینصورت false را برگرداند. ورودی تضمین داده می شود که یک آرایه دو بعدی 10×10 است. عناصر موجود در آرایه اعداد هستند، 0 اگر سلول آزاد باشد و 1 اگر در کشتی اشغال شده باشد.
Battleship (همچنین Battleships یا Sea Battle) یک بازی حدسی دو نفره است. هر بازیکن دارای یک شبکه 10×10 شامل چندین “کشتی” است و هدف از بین بردن نیروهای دشمن با هدف قرار دادن تک تک سلولها در زمین خود است. کشتی یک یا چند سلول را در شبکه اشغال می کند. اندازه و تعداد کشتی ها ممکن است در نسخه های مختلف متفاوت باشد. در این کاتا ما از نسخه شوروی/روسی بازی استفاده خواهیم کرد.
قبل از شروع بازی ، بازیکنان تخته را نصب کرده و کشتی ها را مطابق قوانین زیر قرار می دهند:
باید یک کشتی جنگی (اندازه 4 سلول) ، 2 رزمناو (اندازه 3) ، 3 ناوشکن (اندازه 2) و 4 زیردریایی (اندازه 1) وجود داشته باشد. هرگونه کشتی اضافی و همچنین کشتی های مفقود شده مجاز نیستند.
هر کشتی باید یک خط مستقیم باشد ، به جز زیردریایی ها که فقط تک سلولی هستند.
کشتی نمی تواند همپوشانی داشته باشد یا با هیچ کشتی دیگری در تماس باشد ، نه از لبه و نه از گوشه.
این همه چیزی است که شما برای حل این کاتا نیاز دارید. اگر به اطلاعات بیشتری درباره بازی علاقه دارید ، از این پیوند دیدن کنید.
Description:
Write a method that takes a field for well-known board game “Battleship” as an argument and returns true if it has a valid disposition of ships, false otherwise. Argument is guaranteed to be 10*10 two-dimension array. Elements in the array are numbers, 0 if the cell is free and 1 if occupied by ship.
Battleship (also Battleships or Sea Battle) is a guessing game for two players. Each player has a 10×10 grid containing several “ships” and objective is to destroy enemy’s forces by targetting individual cells on his field. The ship occupies one or more cells in the grid. Size and number of ships may differ from version to version. In this kata we will use Soviet/Russian version of the game.
Before the game begins, players set up the board and place the ships accordingly to the following rules:
There must be single battleship (size of 4 cells), 2 cruisers (size 3), 3 destroyers (size 2) and 4 submarines (size 1). Any additional ships are not allowed, as well as missing ships.
Each ship must be a straight line, except for submarines, which are just single cell.
The ship cannot overlap or be in contact with any other ship, neither by edge nor by corner.
This is all you need to solve this kata. If you’re interested in more information about the game, visit this link.
public class BattleField {
private static boolean at (int y, int x, int[][] field) {
return !(y < 0 || y > 9 || x < 0 || x > 9 || field[y][x] == 0);
}
public static boolean fieldValidator (int[][] field) {
int[] boats = new int[] {2, 4, 3, 2, 1};
for (int y = 0; y < 10; y++) for (int x = 0; x < 10; x++) {
if (field[y][x] != 1) continue;
field[y][x] = boats[0];
int l = 1;
if (at(y+1, x, field)) {
while(at(y+l, x, field)) field[y+(l++)][x] = boats[0];
for (int i = -1; i <= l; i++) if (at(y+i, x+1, field)) return false;
} else {
while(at(y, x+l, field)) field[y][x+(l++)] = boats[0];
for (int i = -1; i <= l; i++) if (at(y+1, x+i, field)) return false;
}
if (l > 4 || --boats[l] < 0) return false;
boats[0]++;
}
if (boats[0] < 12) return false;
return true;
}
}public class BattleField {
private static int xy(int[][] arr, int x, int y) {
return (x < 0 || x >= arr[0].length || y < 0 || y >= arr.length) ? 0 : arr[y][x];
}
public static boolean fieldValidator(int[][] f) {
// Validate the ship's surroundings
// --------------------------------
for (int y = 0; y < f.length; y++) {
for (int x = 0; x < f[y].length; x++) {
if (xy(f, x, y) == 1) {
// Cannot allow a mix of horizontal and vertical
final boolean v = xy(f, x, y-1) != 0 || xy(f, x, y+1) != 0; // look up/down
final boolean h = xy(f, x-1, y) != 0 || xy(f, x+1, y) != 0; // look left/right
if (h && v) return false;
if (v) f[y][x] = -1; // using -1 to represent "vertical" ships
// Cannot be anything diagonally adjacent this cell
if (xy(f, x-1, y-1) != 0 || xy(f, x+1, y-1) != 0 || xy(f, x+1, y+1) != 0 || xy(f, x-1, y+1) != 0) return false;
}
}
}
// Count ships of various expected lengths
// ---------------------------------------
final int[] shipCounts = {0, 4, 3, 2, 1};
// horizontal ships
for (int y = 0; y < f.length; y++) {
for (int x = 0; x < f[y].length; x++) {
if (xy(f, x, y) == 1) {
int len = 1;
while (xy(f, ++x, y) == 1) len++;
if (len > 4) return false; // ship too big
shipCounts[len]--;
}
}
}
// vertical ships
for (int x = 0; x < f[0].length; x++) {
for (int y = 0; y < f.length; y++) {
if (xy(f, x, y) == -1) {
int len = 1;
while (xy(f, x, ++y) == -1) len++;
if (len > 4) return false; // ship too big
shipCounts[len]--;
}
}
}
// Check expected ship counts
for (int count : shipCounts) if (count != 0) return false;
return true;
}
}public class BattleField {
public static boolean fieldValidator(int[][] field) {
return new FieldValidator(field).validate();
}
}
class FieldValidator {
private int[][] field;
private int[] ships = {0,4,3,2,1};
public FieldValidator(int[][] field) {this.field = field;}
public boolean validate() {
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
if(field[i][j] == 1)
if (!isShipValid(i,j)) return false;
return java.util.Arrays.equals(ships, new int[]{0,0,0,0,0});
}
private boolean isShipValid(int i, int j) {
boolean isHorisontal = j<9 && field[i][j+1]==1;
int length = getShipLength(i, j, isHorisontal);
if (length > 4) return false;
ships[length]--;
if (!isLineEmpty(i-1, true, j-1, isHorisontal ? length+1 : 2)) return false;
return isLineEmpty(j-1, false, i-1, isHorisontal ? 2 : length+1);
}
private int getShipLength(int i, int j, boolean isHorisontal) {
int n = 0;
while(i < 10 && j < 10 && field[i][j] == 1) {
n++;
field[i][j] = 2;
if (isHorisontal) j++; else i++;
}
return n;
}
private boolean isLineEmpty(int line, boolean isHorisontal, int start, int length){
if (line == -1) return true;
int end = (start + length) < 9 ? start + length : 9;
for (int i = (start > 0) ? start : 0; i <= end; i++)
if (field [isHorisontal ? line : i] [isHorisontal ? i : line] !=0) return false;
return true;
}
}public class BattleField {
public static boolean fieldValidator(int[][] field) {
int[] arr = {4, 3, 2, 1};
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
if(field[i][j] == 1) {
int l = 0;
if(i < 9 && j < 9 && i > 0 && (field[i + 1][j] == 1 || field[i - 1][j] == 1) && field[i][j + 1] == 1) return false;
while(i + l < 10 && field[i + l][j] == 1) {
field[i + l][j] = 0;
l++;
if(i + l < 10 && (j < 9 && field[i + l][j + 1] == 1 || j > 0 && field[i + l][j - 1] == 1)) return false;
}
if(l == 1) {
while(j + l < 10 && field[i][j + l] == 1){
field[i][j + l] = 0;
l++;
if(j + l < 10 && (i < 9 && field[i + 1][j + l] == 1 || i > 0 && field[i - 1][j + l] == 1)) return false;
}
}
if(l > 4) return false;
arr[l - 1]--;
}
}
}
return java.util.Arrays.stream(arr).allMatch(k -> k == 0);
}
}public class BattleField {
public static boolean fieldValidator(int[][] field) {
int[][] temp = new int[10][10];
for(int i=0;i<10;i++) {
for(int j=0;j<10;j++){
if(field[i][j]==0) continue;
temp[i][j] += field[i][j];
if(j!=0 )temp[i][j] += field[i][j-1];
if(i!=0 )temp[i][j] += field[i-1][j];
if(i!=9 )temp[i][j]+= field[i+1][j];
if(j!=9 )temp[i][j] += field[i][j+1];
if(i!=9 && j!=9 )temp[i][j] += field[i+1][j+1];
if(i!=0 && j!=0 )temp[i][j] += field[i-1][j-1];
if(i!=9 && j!=0 )temp[i][j] += field[i+1][j-1];
if(i!=0 && j!=9 )temp[i][j] += field[i-1][j+1];
}
}
int sum=0;
for(int i=0;i<10;i++) for(int j=0;j<10;j++) sum+=temp[i][j];
System.out.println(sum);
return (sum==40) ? true: false;
}
}import java.util.*;
public class BattleField {
public static boolean fieldValidator(int[][] field) {
int[] figures = {4, 3 ,2 ,1};
for(int i = 0; i< field.length; i++) {
for(int j = 0; j< field.length; j++) {
if(field[i][j] == 1) {
if((i+1 < field.length && field[i+1][j] == 1) && (j+1 < field.length && field[i][j+1] == 1 )) return false;
if(i+1 < field.length && field[i+1][j] == 1) {
int siz = 0;
int p = i;
while(p < field.length && field[p][j] ==1) {
siz++;
p++;
}
if(siz > 4) return false;
for(int i1 = i; i1 < i+siz; i1++) {
if(i1 == i+siz-1)
if(((i1+1 < field.length && j-1 > -1) && field[i1+1][j-1] == 1) || ( (i1+1 < field.length)&& field[i1+1][j] == 1) || ( (i1+1 < field.length && j+1 < field.length)&& field[i1+1][j+1] == 1)) return false;
if(( j+1 < field.length &&field[i1][j+1] == 1) || (j-1 > -1 && field[i1][j-1] == 1)) return false;
field[i1][j] = 0;
}
figures[siz-1]--;
}else if(j+1 < field.length && field[i][j+1] == 1) {
int siz = 0;
int p = j;
while(p < field.length && field[i][p] == 1) {
p++;
siz++;
}
if(siz > 4) return false;
for(int j1 = j; j1 < j+siz; j1++) {
if( i+1 < field.length &&field[i+1][j1] == 1 || ( ((j1 == j && j1-1 > -1 && i+1 < field.length) &&(field[i+1][j1-1] == 1)) || ( (j1 == (j+siz-1) && j1+1 < field.length && i+1 < field.length) && (field[i+1][j1+1] == 1))))
return false;
field[i][j1] = 0;
}
figures[siz-1]--;
}else {
figures[0]--;
field[i][j] = 0;
if(((i+1 < field.length && j+1 < field.length) && (field[i+1][j+1] ==1)) || ((i+1 < field.length && j-1 > -1) && (field[i+1][j-1] ==1))) return false;
}
}
}
}
return Arrays.equals(figures, new int[]{0, 0, 0, 0});
}
}import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class BattleField {
private static final int CROSSED_OUT = -1;
public static boolean fieldValidator(int[][] field) {
Map<String, Integer> shipQuantityMap = new HashMap<>();
shipQuantityMap.put("battleShip", 1);
shipQuantityMap.put("cruisers", 2);
shipQuantityMap.put("destroyers", 3);
shipQuantityMap.put("submarines", 4);
try {
checkBoardElementsSum(field);
validPlacementOfShips(field, shipQuantityMap);
} catch (InvalidBoardException e) {
return false;
}
return shipQuantityMap.get("submarines") == 0 && shipQuantityMap.get("destroyers") == 0
&& shipQuantityMap.get("cruisers") == 0 && shipQuantityMap.get("battleShip") == 0;
}
private static void checkBoardElementsSum(int[][] field) throws InvalidBoardException {
int fieldsSum = Arrays.stream(field)
.flatMapToInt(Arrays::stream)
.reduce(0, Integer::sum);
if (fieldsSum != 20) {
throw new InvalidBoardException();
}
}
private static void validPlacementOfShips(int[][] field, Map<String, Integer> shipQuantityMap) throws InvalidBoardException {
for (int row = 0; row < field.length; row++) {
for (int col = 0; col < field[row].length; col++) {
if (field[row][col] == 1) {
int numberOfShipParts = validShipArea(field, row, col);
crossShip(numberOfShipParts, shipQuantityMap);
}
}
}
}
private static int validShipArea(int[][] field, int row, int col) throws InvalidBoardException {
if (horizontalRightFieldBusy(row, col, field) && vertitalDownFieldBusy(row, col, field)) {
throw new InvalidBoardException();
}
validSlants(row, col, field);
field[row][col] = CROSSED_OUT;
//horizontalValidation
int shipFields = checkHorizontal(row, col, field);
//vertical validation
if (shipFields == 1) {
shipFields = checkVertical(row, col, field);
}
return shipFields;
}
private static void crossShip(int shipFields, Map<String, Integer> shipQuantityMap) throws InvalidBoardException {
switch (shipFields) {
case 1:
shipQuantityMap.put("submarines", shipQuantityMap.get("submarines") - 1);
break;
case 2:
shipQuantityMap.put("destroyers", shipQuantityMap.get("destroyers") - 1);
break;
case 3:
shipQuantityMap.put("cruisers", shipQuantityMap.get("cruisers") - 1);
break;
case 4:
shipQuantityMap.put("battleShip", shipQuantityMap.get("battleShip") - 1);
break;
default:
throw new InvalidBoardException();
}
}
private static int checkVertical(int row, int col, int[][] field) throws InvalidBoardException {
int shipParts = 1;
while (row < field.length) {
if (vertitalDownFieldBusy(row, col, field)) {
shipParts++;
if (horizontalRightFieldBusy(row, col, field)) {
throw new InvalidBoardException();
}
row++;
validSlants(row, col, field);
field[row][col] = CROSSED_OUT;
} else {
return shipParts;
}
}
return shipParts;
}
private static int checkHorizontal(int row, int col, int[][] field) throws InvalidBoardException {
int shipParts = 1;
while (col < field[row].length) {
if (horizontalRightFieldBusy(row, col, field)) {
shipParts++;
if (vertitalDownFieldBusy(row, col, field)) {
throw new InvalidBoardException();
}
col++;
validSlants(row, col, field);
field[row][col] = CROSSED_OUT;
} else {
return shipParts;
}
}
return shipParts;
}
private static boolean vertitalDownFieldBusy(int row, int col, int[][] field) {
return row == field.length - 1 ? false : field[row + 1][col] == 1;
}
private static boolean horizontalRightFieldBusy(int row, int col, int[][] field) {
return col == field[row].length - 1 ? false : field[row][col + 1] == 1;
}
private static void validSlants(int row, int column, int[][] field) throws InvalidBoardException {
if (row > 0 && column > 0) {
if (field[row - 1][column - 1] != 0) throw new InvalidBoardException();
}
if (row < field.length - 1 && column > 0) {
if (field[row + 1][column - 1] != 0) throw new InvalidBoardException();
}
if (column < field.length - 1 && row > 0) {
if (field[row - 1][column + 1] != 0) throw new InvalidBoardException();
}
if (row < field.length - 1 && column < field.length - 1) {
if (field[row + 1][column + 1] != 0) throw new InvalidBoardException();
}
}
private static class InvalidBoardException extends Exception {
}
}
