Problems

Groups in grid

``````// 0 is empty, 1 is blocked, 2 is group1

package ai.jdd.prob;

import java.util.Arrays;
import java.util.Queue;

public class Grid {

private static int grid[][];

public static void main(String[] args) {
int rows = 5;
int cols = 5;
int numBlocks = (rows*cols)/2;

for (int i = 0; i < 10; i++) {
System.out.println("Is there more than one group? " + checkGrid(rows, cols, numBlocks));
}
}

static boolean checkGrid(int rows, int cols, int numBlocks) {
boolean oneGroup = false;
grid = new int[rows][cols];
for (int i=0; i<numBlocks; i++) {
grid[(int)(Math.random()*rows)][(int)(Math.random()*cols)] = 1; //add in blocked cells
}
for (int[] row : grid)
System.out.println(Arrays.toString(row));
for (int x=0; x<rows; x++) { // iterate through grid
for (int y=0; y<cols; y++) {
if (grid[x][y] == 1) { // if this cell is blocked
if (oneGroup) {
return true; // found second group
}
oneGroup = true; // found first group
combineGroup(x,y);
}
}
}
return false; // 0 or 1 group found
}

private static void combineGroup(int x, int y) { // This method sets connected cells to 2
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
Queue<Integer[]> q = new LinkedList<>();
Integer point[] = {x,y};
grid[x][y] = 2; // add it to group
q.add(point); // queue of next cells to check

while (!q.isEmpty()) {
point = q.poll(); // get next cell to check

for (int i = 0; i < 4; i++) { // check neighbors
point[0] = dx[i]+x;
point[1] = dy[i]+y;
// check if in range and blocked
if(point[0]>=0 && point[0]<grid.length && point[1]>=0 && point[1]<grid[0].length && grid[point[0]][point[1]] == 1) {
grid[point[0]][point[1]] = 2;
}
}
}
}
}``````

Boggle

``````package ai.jdd.prob;

import java.util.HashSet;
import java.util.Set;

public class Boggle {

/*
I chose DFS becuase I would have to store more state in memory if I had used BFS.

List<String> ans is the list of answers, could make it a set remove duplicates

solveBoggle's input is a matric of chars. For each char in the matrix, it will do a DFS for words

searchWord's input is the board, coordinates, and the word so far.
it adds the char to the word, and marks the coordinate in the board as 1

it adds the word to the answer list if it is a word

if the word is a prefix then it will run searchWord on its neighbors
*/

private Set<String> ans = new HashSet<>(); //List of answers, right now there could be duplicate words

Set<String> solveBoggle(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
searchWord(board, i, j, "");
}
}
return ans;
}

private void searchWord(char[][] board, int row, int col, String word) {
word += board[row][col];
board[row][col] = '1';

if(BoggleDict.isWord(word)) {
}

if(BoggleDict.isPrefix(word)) {
int[] dRow = {0,1,0,-1,-1,-1,1,1};
int[] dCol = {-1,0,1,0,-1,1,-1,1};
for (int i = 0; i < 8; i++) {
int rowNeighb = dRow[i]+row;
int colNeighb = dCol[i]+col;
if (rowNeighb != -1 && rowNeighb != board.length && colNeighb != -1
&& colNeighb != board[1].length && board[rowNeighb][colNeighb] != '1'){
searchWord(board, rowNeighb, colNeighb, word);
}
}
}
}

}``````