Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
I post my solution below:
import java.util.Random;
public class candyCrush {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] res = generateRandon(6);
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[0].length; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
}
public static int[][] generateRandon(int size) {
Random r = new Random();
int dp[][] = new int[size][size];
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
int rand = r.nextInt(4) + 1;
if (x > 1 && y > 1) {
int a = dp[x - 1][y];
int b = dp[x][y - 1];
int c = dp[x - 2][y];
int d = dp[x][y - 2];
int newRand = rand;
if (rand == a && rand == c && b!=d) {
newRand = a;
while (newRand == a) {
newRand = r.nextInt(4) + 1;
}
}else if (rand == b && rand == d && a!=c) {
newRand = b;
while (newRand == b) {
newRand = r.nextInt(4) + 1;
}
}else if(a==c && b==d){
while (newRand == a||newRand==b) {
newRand = r.nextInt(4) + 1;
}
}
dp[x][y] = newRand;
} else if (x <= 1 && y > 1) {
int a = dp[x][y - 1];
int b = dp[x][y - 2];
int newRand = rand;
if (rand == a && rand == b) {
newRand = a;
while (newRand == a) {
newRand = r.nextInt(4) + 1;
}
}
dp[x][y] = newRand;
} else if (y <= 1 && x > 1) {
int a = dp[x - 1][y];
int b = dp[x - 2][y];
int newRand = rand;
if (rand == a && rand == b) {
newRand = a;
while (newRand == a) {
newRand = r.nextInt(4) + 1;
}
}
dp[x][y] = newRand;
}else{
dp[x][y] = rand;
}
}
}
return dp;
}
}
wtcupup, mine is already too long and complex for the problem, yours is out of control.
struct seq
{
seq() {val = len = 0;}
int val, len;
};
int* MakeMatrix(int N)
{
int* pRVal = new int[N*N];
seq* pColSeqs = new seq[N];
for (int r = 0; r < N; r++)
{
seq rowSeq;
for (int c = 0; c < N; c++)
{
seq* pCurSeqs[2] = {&pColSeqs[c], &rowSeq};
int nextNum = 0;
while (nextNum == 0)
{
nextNum = rand()%4 + 1;
for (seq* pS: pCurSeqs)
if ((pS->len == 2) && (pS->val == nextNum))
nextNum = 0;
}
pRVal[r*N + c] = nextNum;
for (seq* pS : pCurSeqs)
{
pS->len = (nextNum == pS->val) ? pS->len+1 : 1;
pS->val = nextNum;
}
}
}
return pRVal;
}
int main(int argc, char* argv[])
{
srand((int)time(NULL));
const int N = 50;
int* pRVal = MakeMatrix(N);
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
printf("%d,", pRVal[r*N + c]);
printf("\n");
}
getch();
return 0;
}
how about this: ( simple without DP)
1) row0,col 0 starts with 1 followed by 2,3,4,3,2,1 ,2,3,4.. ( basically increasing and decreasing)
2) if we shift above row elements left once and place this element at the end of the row - then it would be 2,2,3,4,3,2,1 ,2,3,4,1
continue the process for all rows..
after u construct matrix u will observe that row0==col0 , row1==col1 and so on. Also same element cannot occur more than twice.
#include <iostream>
#include <stdlib.h>
using namespace std;
int get_random_num()
{
return rand() % 4 + 1;
}
int main()
{
int matrix[4][4];
int t = 1;
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
t = get_random_num();
matrix[i][j] = t;
//check row according to validity
if ((j == 2) && (matrix[i][0] == matrix[i][1] == matrix[i][2])){
(t > 1) ? t-- : t++;
matrix[i][j] = t;
}
//check column according to validity
if ((i == 2) && (matrix[0][j] == matrix[1][j] == matrix[2][j])){
(t > 1) ? t-- : t++;
matrix[i][j] = t;
}
cout << " " << matrix[i][j];
}
cout << endl;
}
return 0;
}
public static void main(String[] args) {
System.out.println();
System.out.println("Generating matrix");
int [][] matrix = generateMatrix(10);
for(int row = 0; row < matrix.length; ++row){
for(int col = 0; col < matrix.length; ++col){
System.out.print(" " + matrix[row][col]);
}
System.out.println();
}
}
public static int [][] generateMatrix(final int N){
int [][] result = new int[N][N];
for(int row = 0; row < N; ++row){
for(int col = 0; col < N; ++col){
setValidNum(row, col, result);
}
}
return result;
}
//idea is to fill the rows and cols up in ascending order so we only need
//to look backwards for problems, can have at most 2 invalid nums
private static void setValidNum(int row, int col, int [][] arr){
int invalidNum1 = 0;
int invalidNum2 = 0;
if(col-2 >= 0 ){
if(arr[row][col-1] == arr[row][col-2]){
invalidNum1 = arr[row][col-1];
}
}
if(row-2 >= 0){
if(arr[row-1][col] == arr[row-2][col]){
invalidNum2 = arr[row-1][col];
}
}
Random rand = new Random();
int result = rand.nextInt(4) + 1;
while(result == invalidNum1 || result == invalidNum2){
result = rand.nextInt(4) + 1;
}
arr[row][col] = result;
}
public class RandomGenerate1X1 {
static boolean find(int[][] a) {
int[] row = new int[a.length];
int[] col = new int[a.length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
if (!increment(a[i][j], row)) {
return false;
}
if (!increment(a[j][i], col)) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[][] a = { { 1, 2, 1, 1 }, { 2, 1, 4, 2 }, { 1, 2, 4, 1 }, { 3, 2, 2, 2 } };
System.out.println(find(a));
}
private static boolean increment(int m, int[] row) {
if (row[m - 1] == 2) {
return false;
} else {
row[m - 1] += 1;
for (int i = 0; i < row.length; i++) {
if (i != m - 1) {
row[i] = 0;
}
}
}
return true;
}
}
public static int[][] generateArray(int N) {
int[][] arr = new int[N][N];
Set<Integer> oneToFour = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Random rand = new Random();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int duplicateInCol = 1;
int duplicateInRow = 1;
if (i > 1 && arr[i - 1][j] == arr[i - 2][j]) { // Same nums in col
duplicateInCol = arr[i - 1][j];
oneToFour.remove(duplicateInCol);
}
if (j > 1 && arr[i][j - 1] == arr[i][j - 2]) { // Same nums in row
duplicateInRow = arr[i][j - 1];
oneToFour.remove(duplicateInRow);
}
arr[i][j] = new ArrayList<>(oneToFour).get(rand.nextInt(oneToFour.size()));
oneToFour.add(duplicateInCol);
oneToFour.add(duplicateInRow);
}
}
return arr;
}
from random import randint
def find_valid_number(a, i, j):
while True:
rand = randint(1, 4)
if j >= 2 and a[i][j-2] == a[i][j-1] \
and a[i][j-1] == rand:
continue
if i >= 2 and a[i-2][j] == a[i-1][j] \
and a[i-1][j] == rand:
continue
return rand
def generate_matrix(n):
a = []
for i in xrange(n):
for j in xrange(n):
if j == 0:
a.append([])
a[i].append(find_valid_number(a, i, j))
for row in a:
print " ".join(map(str, row))
generate_matrix(10)
Hi,
simplifying the methods might pay off in terms of understandability and clean code. Some of the solutions are too complicated. Bellow is my attempt, please let me know if you have any comments!
{{import java.util.HashSet;
public class RandomArray {
private int[] elements;
private int[][] result;
private int size;
public RandomArray(int size, int[] elements) {
this.elements = elements;
this.size = size;
result = new int[size][size];
}
private boolean isValidForRow(int row, int col, int pos) {
if (row < 2) {
return true;
}
if (result[row-1][col] != result[row-2][col]) {
return true;
}
if (result[row-1][col] != elements[pos]) {
return true;
}
return false;
}
private boolean isValidForCol(int row, int col, int pos) {
if (col < 2) {
return true;
}
if (result[row][col-1] != result[row][col-2]) {
return true;
}
if (result[row][col-1] != elements[pos]) {
return true;
}
return false;
}
public int[][] generate() {
int pos;
HashSet<Integer> invalidPos;
for (int i=0; i<size; ++i) {
for (int j=0; j<size; ++j) {
invalidPos = new HashSet<>();
pos = (int) (Math.random() * elements.length);
if (!isValidForRow(i, j, pos)) {
invalidPos.add(pos);
}
if (!isValidForCol(i, j, pos)) {
invalidPos.add(pos);
}
if (invalidPos.size() > 0) {
pos = (int) Math.random() * elements.length;
for (Integer invPos : invalidPos) {
if (pos >= invPos) {
pos++;
}
}
}
result[i][j] = elements[pos];
}
}
return result;
}
} }}
import java.util.concurrent.ThreadLocalRandom;
public class RandomMatrix {
public static void main(String[] args) {
final int n = 4;
// up to k elements consecutive allowed in rows or columns
final int k = 2;
// min (inclusive) for the values in the matrix
final int min = 1;
// max (inclusive) for the values in the matrix
final int max = 4;
int[][] a = generateMatrix(n, k, min, max);
print(a, n);
}
public static void print(int[][] a, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
System.out.print(a[i][j] + " ");
}
System.out.println("");
}
}
public static class Element {
private int previous;
private int count;
public Element(int previous, int count) {
this.previous = previous;
this.count = count;
}
public int getCount() {
return this.count;
}
public int getPrevious() {
return this.previous;
}
public void increaseCount() {
this.count++;
}
}
private static boolean isValid(Element item, int candidate, int k) {
return item == null || candidate != item.getPrevious() || item.getCount() < k;
}
private static Element processCandidate(Element item, int candidate) {
if (item == null || item.getPrevious() != candidate) {
return new Element(candidate, 1);
}
item.increaseCount();
return item;
}
private static int[][] generateMatrix(int n, int k, int min, int max) {
int[][] a = new int[n][n];
Element[] rows = new Element[n];
Element[] cols = new Element[n];
// next candidate
int c = 0;
for (int i = 0; i < n; ++i) {
Element row = null;
for (int j = 0; j < n; ++j) {
do {
c = generateCandidate(min, max);
} while (!isValid(cols[j], c, k) || !isValid(row, c, k));
cols[j] = processCandidate(cols[j], c);
row = processCandidate(row, c);
a[i][j] = c;
}
}
return a;
}
private static int generateCandidate(int min, int max) {
return ThreadLocalRandom.current().nextInt(min, max + 1);
}
import java.util.concurrent.ThreadLocalRandom;
public class RandomMatrix {
public static void main(String[] args) {
final int n = 4;
// up to k elements consecutive allowed in rows or columns
final int k = 2;
// min (inclusive) for the values in the matrix
final int min = 1;
// max (inclusive) for the values in the matrix
final int max = 4;
int[][] a = generateMatrix(n, k, min, max);
print(a, n);
}
public static void print(int[][] a, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
System.out.print(a[i][j] + " ");
}
System.out.println("");
}
}
public static class Element {
private int previous;
private int count;
public Element(int previous, int count) {
this.previous = previous;
this.count = count;
}
public int getCount() {
return this.count;
}
public int getPrevious() {
return this.previous;
}
public void increaseCount() {
this.count++;
}
}
private static boolean isValid(Element item, int candidate, int k) {
return item == null || candidate != item.getPrevious() || item.getCount() < k;
}
private static Element processCandidate(Element item, int candidate) {
if (item == null || item.getPrevious() != candidate) {
return new Element(candidate, 1);
}
item.increaseCount();
return item;
}
private static int[][] generateMatrix(int n, int k, int min, int max) {
int[][] a = new int[n][n];
Element[] rows = new Element[n];
Element[] cols = new Element[n];
// next candidate
int c = 0;
for (int i = 0; i < n; ++i) {
Element row = null;
for (int j = 0; j < n; ++j) {
do {
c = generateCandidate(min, max);
} while (!isValid(cols[j], c, k) || !isValid(row, c, k));
cols[j] = processCandidate(cols[j], c);
row = processCandidate(row, c);
a[i][j] = c;
}
}
return a;
}
private static int generateCandidate(int min, int max) {
return ThreadLocalRandom.current().nextInt(min, max + 1);
}
import java.util.concurrent.ThreadLocalRandom;
public class RandomMatrix {
public static void main(String[] args) {
final int n = 4;
// up to k elements consecutive allowed in rows or columns
final int k = 2;
// min (inclusive) for the values in the matrix
final int min = 1;
// max (inclusive) for the values in the matrix
final int max = 4;
int[][] a = generateMatrix(n, k, min, max);
print(a, n);
}
public static void print(int[][] a, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
System.out.print(a[i][j] + " ");
}
System.out.println("");
}
}
public static class Element {
private int previous;
private int count;
public Element(int previous, int count) {
this.previous = previous;
this.count = count;
}
public int getCount() {
return this.count;
}
public int getPrevious() {
return this.previous;
}
public void increaseCount() {
this.count++;
}
}
private static boolean isValid(Element item, int candidate, int k) {
return item == null || candidate != item.getPrevious() || item.getCount() < k;
}
private static Element processCandidate(Element item, int candidate) {
if (item == null || item.getPrevious() != candidate) {
return new Element(candidate, 1);
}
item.increaseCount();
return item;
}
private static int[][] generateMatrix(int n, int k, int min, int max) {
int[][] a = new int[n][n];
Element[] rows = new Element[n];
Element[] cols = new Element[n];
// next candidate
int c = 0;
for (int i = 0; i < n; ++i) {
Element row = null;
for (int j = 0; j < n; ++j) {
do {
c = generateCandidate(min, max);
} while (!isValid(cols[j], c, k) || !isValid(row, c, k));
cols[j] = processCandidate(cols[j], c);
row = processCandidate(row, c);
a[i][j] = c;
}
}
return a;
}
private static int generateCandidate(int min, int max) {
return ThreadLocalRandom.current().nextInt(min, max + 1);
}
var arr = [
[1,2,3,4],
[1,3,2,1],
[1,2,4,2],
[3,2,1,4]
];
function getValidArray(arr) {
var checkNum = 3;
var continousCounter = 0;
var savedNumber = 0;
for(var i in arr) {
if(i === 0) {
continousCounter++;
savedNumber = arr[i];
continue;
}
if(arr[i] !== savedNumber) {
continousCounter = 1;
savedNumber = arr[i];
continue;
}
if(arr[i] === savedNumber) {
continousCounter++;
if(continousCounter === checkNum) {
return false;
}
}
}
return true;
}
function isValidMatrix(matrix) {
if(matrix && matrix.hasOwnProperty('length')) {
var cols = {};
for(var i in matrix) {
if(!getValidArray(matrix[i])) {
return false;
}
for(var j in matrix[i]) {
if(!cols[''+j]) {
cols[''+j] = [];
}
cols[''+j].push(matrix[i][j]);
}
}
for(var idx in cols) {
if(!getValidArray(cols[idx])) {
return false;
}
}
}
return true;
}
var arr = [
[1,2,3,4],
[1,3,2,1],
[1,2,4,2],
[3,2,1,4]
];
function getValidArray(arr) {
var checkNum = 3;
var continousCounter = 0;
var savedNumber = 0;
for(var i in arr) {
if(i === 0) {
continousCounter++;
savedNumber = arr[i];
continue;
}
if(arr[i] !== savedNumber) {
continousCounter = 1;
savedNumber = arr[i];
continue;
}
if(arr[i] === savedNumber) {
continousCounter++;
if(continousCounter === checkNum) {
return false;
}
}
}
return true;
}
function isValidMatrix(matrix) {
if(matrix && matrix.hasOwnProperty('length')) {
var cols = {};
for(var i in matrix) {
if(!getValidArray(matrix[i])) {
return false;
}
for(var j in matrix[i]) {
if(!cols[''+j]) {
cols[''+j] = [];
}
cols[''+j].push(matrix[i][j]);
}
}
for(var idx in cols) {
if(!getValidArray(cols[idx])) {
return false;
}
}
}
return true;
}
Here is my solution. easy to understand.
public class GenerateMatrixWithNoSameTypeofElement {
public static void main(String[] args){
int a[][] = generateMatrix(4);
for(int i = 0; i<4; i++ ){
for(int j =0; j<4; j++){
System.out.print(a[i][j] + " ");
}
System.out.println();
}
// System.out.println(validMatrix(a));
}
private static int[][] generateMatrix(int p) {
int a[][] = new int[p][p];
int i=0,j;
while(i<p){
j=0;
while(j<p){
Random rand = new Random();
boolean lop = true;
int x = rand.nextInt(p);
while(lop && (j >=2 || i >=2)){
if(j>=2){
if(x == a[i][j-1] && x == a[i][j-2]){
x = rand.nextInt(p);
lop = true;
}
else
lop = false;
}
if(i>=2){
if(x == a[i-1][j] && x == a[i-2][j]){
x = rand.nextInt(p);
lop = true;
}
else{
lop = false;
}
}
}
a[i][j] = x;
j++;
}
i++;
}
return a;
}
Here is my solution.
public class GenerateMatrixWithNoSameTypeofElement {
public static void main(String[] args){
int a[][] = generateMatrix(4);
for(int i = 0; i<4; i++ ){
for(int j =0; j<4; j++){
System.out.print(a[i][j] + " ");
}
System.out.println();
}
// System.out.println(validMatrix(a));
}
private static int[][] generateMatrix(int p) {
int a[][] = new int[p][p];
int i=0,j;
while(i<p){
j=0;
while(j<p){
Random rand = new Random();
boolean lop = true;
int x = rand.nextInt(p);
while(lop && (j >=2 || i >=2)){
if(j>=2){
if(x == a[i][j-1] && x == a[i][j-2]){
x = rand.nextInt(p);
lop = true;
}
else
lop = false;
}
if(i>=2){
if(x == a[i-1][j] && x == a[i-2][j]){
x = rand.nextInt(p);
lop = true;
}
else{
lop = false;
}
}
}
a[i][j] = x;
j++;
}
i++;
}
return a;
}
}
public class GenerateMatrix {
private int[][] matrix;
private int rowCount;
private int colCount;
final List<Integer> alphabet;
public GenerateMatrix(int n, int m) {
rowCount = n;
colCount = m;
matrix = new int[n][];
for (int i = 0; i < m; ++i) {
matrix[i] = new int[m];
}
alphabet = new ArrayList<>();
alphabet.add(1);
alphabet.add(2);
alphabet.add(3);
alphabet.add(4);
}
public void generate() {
for (int i = 0; i < rowCount; ++i) {
for (int j = 0; j < colCount; ++j) {
matrix[i][j] = generate(i, j);
}
}
}
private int generate(int r, int c) {
Set<Integer> s = new HashSet<>();
s.addAll(alphabet);
int left = leftDisallowed(r, c);
int up = uptDisallowed(r, c);
if (left != -1) {
s.remove(left);
}
if (up != -1 && up != left) {
s.remove(up);
}
int rand = (new Random()).nextInt(s.size());
return (int) s.toArray()[rand];
}
private int leftDisallowed(int i, int j) {
if (i < 2) {
return -1;
}
if (matrix[i - 2][j] == matrix[i - 1][j]) {
return matrix[i - 2][j];
}
return -1;
}
private int uptDisallowed(int i, int j) {
if (j < 2) {
return -1;
}
if (matrix[i][j - 2] == matrix[i][j - 1]) {
return matrix[i][j - 1];
}
return -1;
}
}
private int getRand(int min, int max, int exclude){
int[] range= null;
if(exclude<min ||exclude>max){
range=new int[max-min+1];
}else{
range=new int[max-min];
}
int ptr=0;
for(int i=min; i<=max; i++){
if(i==exclude)
continue;
range[ptr++]=i;
}
int randomNum = ThreadLocalRandom.current().nextInt(range[0], range[range.length-1] + 1)-1;
return range[randomNum];
}
public int[][] randMat(int size, int min, int max){
int[][] retMat=new int[size][size];
for(int i=0;i<size;i++){
for(int j=i;j<size;j++){
int exclude=min-1;
if(j>=2 && retMat[i][j-1]==retMat[i][j-2]){
exclude=retMat[i][j-2];
}
retMat[i][j]=getRand(min, max, exclude);
exclude=min-1;
if(i>=2 && retMat[i-1][j]==retMat[i-2][j]){
exclude=retMat[i-1][j];
}
retMat[j][i]=getRand(min, max,exclude);
}
}
return retMat;
}
private int getRand(int min, int max, int exclude){
int[] range= null;
if(exclude<min ||exclude>max){
range=new int[max-min+1];
}else{
range=new int[max-min];
}
int ptr=0;
for(int i=min; i<=max; i++){
if(i==exclude)
continue;
range[ptr++]=i;
}
int randomNum = ThreadLocalRandom.current().nextInt(range[0], range[range.length-1] + 1)-1;
return range[randomNum];
}
public int[][] randMat(int size, int min, int max){
int[][] retMat=new int[size][size];
for(int i=0;i<size;i++){
for(int j=i;j<size;j++){
int exclude=min-1;
if(j>=2 && retMat[i][j-1]==retMat[i][j-2]){
exclude=retMat[i][j-2];
}
retMat[i][j]=getRand(min, max, exclude);
exclude=min-1;
if(i>=2 && retMat[i-1][j]==retMat[i-2][j]){
exclude=retMat[i-1][j];
}
retMat[j][i]=getRand(min, max,exclude);
}
}
return retMat;
}
private int getRand(int min, int max, int exclude){
int[] range= null;
if(exclude<min ||exclude>max){
range=new int[max-min+1];
}else{
range=new int[max-min];
}
int ptr=0;
for(int i=min; i<=max; i++){
if(i==exclude)
continue;
range[ptr++]=i;
}
int rand = ThreadLocalRandom.current().nextInt(1, (range.length) + 1)-1;
return range[randomNum];
}
void Run()
{
int m = 5;
int n = 5;
var matrix = GenerateMatrix(m, n, new int[4] {1,2,3,4 });
PrintMatrix(matrix, m, n);
}
private static void PrintMatrix(int[,] matrix, int m, int n)
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(matrix[i,j] + "\t");
}
Console.WriteLine();
}
}
private static int getRandomNumber(int[] numbers)
{
return numbers[new Random().Next(0, numbers.Length - 1)];
}
private static int[,] GenerateMatrix(int m, int n, int[] numbers)
{
var result = new int[m, n];
var rowPossibleOffender = -1;
var colPossibleOffender = new int[n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
int newNumber = default(int);
while ((newNumber = getRandomNumber(numbers)) == rowPossibleOffender
&& newNumber == colPossibleOffender[j]) ;
result[i, j] = newNumber;
//Set row offender
if (i > 0 && result[i, j] == result[i - 1, j])
{
rowPossibleOffender = result[i, j];
}
else
{
rowPossibleOffender = -1;
}
// set col offender
if (j > 0 && result[i, j] == result[i, j - 1])
{
colPossibleOffender[j] = result[i, j];
}
else
{
colPossibleOffender[j] = -1;
}
}
}
return result;
}
private static int[][] generate(int size) {
final ThreadLocalRandom random = ThreadLocalRandom.current();
final int[][] matrix = new int[size][size];
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix.length; col++) {
boolean assigned = false;
while (!assigned) {
int number = random.nextInt(4) + 1;
boolean rowCondition = row < 2 || matrix[row - 1][col] != matrix[row - 2][col] || matrix[row - 1][col] != number;
boolean colCondition = col < 2 || matrix[row][col - 1] != matrix[row][col - 2] || matrix[row][col - 1] != number;
if (rowCondition && colCondition) {
assigned = true;
matrix[row][col] = number;
}
}
}
}
return matrix;
}
All the solutions are too lengthy .. I have tested my solution and it works every time.. Comments are appreciated
private int[][] getRandomMatrix(int size){
int [] [] matrix = new int[size][size];
int random;
for (int i=0;i<size;i++){
for ( int j=0 ;j<size;j++){
random = getRandomNumber();
matrix[i][j]= random;
if((((i - 1) >= 0) && ((i-2)>=0)) ){
if( (matrix[i][j] == matrix[i-1][j] && matrix[i][j]== matrix[i-2][j] ) ){
random = getRandomNumber();
j--;
}
}
if(((j-1)>=0) && ((j-2)>=0)){
if((matrix[i][j]== matrix[i][j-1] && matrix[i][j]== matrix[i][j-2])){
random = getRandomNumber();
j--;
}
}
}
}
return matrix;
}
private int getRandomNumber() {
return new Random().nextInt(4)+1;
}
#include <iostream>
#include <algorithm> // std::random_shuffle
#include <vector> // std::vector
#include <ctime> // std::time
#include <cstdlib>
using namespace std;
bool isSafe(vector<vector<int>> &A,int i,int j,int val)
{
bool hor = true;
if(j>1)
{
if((A[i][j-1] == val) && A[i][j-2] == val)
return false;
}
if(i>1)
{
if((A[i-1][j] == val) && A[i-2][j] == val)
return false;
}
return true;
}
bool solve(vector<vector<int>> &A,int i,int j)
{
int N = A.size();
if(i==N-1 && j==N) return true;
if(j==N) return solve(A,i+1,0);
vector<int> nums(4,0);
for(int t=1;t<=4;t++) nums[t-1] = t;
random_shuffle(nums.begin(),nums.end());
for(int k=0;k<4;k++)
{
if(isSafe(A,i,j,nums[k]))
{
A[i][j] = nums[k];
bool b = solve(A,i,j+1);
if(b) return true;
}
}
}
int main()
{
cout<<"Hello\n";
int N = 4;
vector<vector<int>> A(N,vector<int>(N,0));
bool t = solve(A,0,0);
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout << A[i][j] << " ";
}
cout << "\n";
}
return 0;
}
How about just generate all the combinations of making an N length array using 1,2,3,4 and then randomly picking an index number from this collection for every row in the result matrix?
preprocess(N, (1234)) => { {1,1,2,1), (1,2,1,1), (2,1,1,1), {1,1,3,1)................} -> combList
GenerateMatrix(combList, N)
{
for(int i = 0; i < N; i++)
{
randIdx = generateIndex(0, combList.size());
solution[i] = combList.get(combList.get(randIdx));
}
}
your solution doesn't allow the case that two elements of same type are next to each other in a row or column, but actually it is allowed. Only three or above connected elements in the same row or column are prohibited.
- wtcupup2017 December 30, 2016