HackerRank Digits Square Board problem solution

In this HackerRank Digits Square Board problem solution Two HackerRank staffers found a secret room with a mysterious N x N square board and decided to play a game with it. The game has the following rules:

At the beginning of the game, the players write a single digit (given as input) ranging from 1 to 9 in each 1 x 1 cell composing the N x N square board.
The players move in alternating turns. In each move, the current player performs the following actions:

Chooses a board that has at least one non-prime number written on it and has more than one cell (i.e., dimensions > 1 x 1).
Cuts the chosen board into 2 smaller boards by breaking it along any horizontal or vertical line at the edge of a cell.
Note: Although the game starts with one N x N board, that board is split in two during each move. At the beginning of the kth move, a player can choose any one of the pieces of the original board (as long as it can have a legal move performed on it).

The game ends when there are no more cuttable boards (i.e., there are N.(1×1) boards, or all boards have only prime numbers written on them). The first player who is unable to make a move loses.

Given the value of n and the respective numbers written in each (i,j) cell of the board, determine whether the person who wins the game is the first or second person to move. Assume both players move optimally.

HackerRank Digits Square Board problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class DigitsSquareBoard {
    static final int  max = 60;
    static final int  maxn = 30;
    static int[][]a;
    static int n;
    static int[][][][]g;
    
    public static void main(String[] args) throws IOException{
        new DigitsSquareBoard().run();
    }
    
    public void run() throws IOException{
        Scanner in = new Scanner(System.in);
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = in.nextInt();
        int i,j,k,l,m;
        a = new int[maxn][maxn];
        g = new int[max][max][max][max];

        for(int tt =0;tt < t;tt++){
            n = in.nextInt();
            for(i=0;i<n;i++){
                Arrays.fill(a[i],-1);
            }
            for(i=0;i<n;i++){
                for(j=0;j<n;j++){
                    m = in.nextInt();
                    a[i][j]=(m==2||m==3||m==5||m==7)?0:1;//0 == black primes
                }
            }

            for(i=0;i<max;i++){
                for(j=0;j<max;j++){
                    for(k=0;k<max;k++){
                        for(l=0;l<max;l++){
                            g[i][j][k][l]=-1;
                        }
                    }
                }
            }
            int nimsum = grundy(0,0,n-1,n-1);

            if(nimsum>0) log.write("Firstn");
            else log.write("Secondn");
        }
        log.flush();
    }
    
    public boolean prime(int x, int y, int z, int t){
        int i,j;
        for(i=x;i<=z;i++){
                for(j=y;j<=t;j++){
                    if(a[i][j]==1) return false;
                }
            }
        return true;
    }
              
    public int grundy(int x, int y, int z, int t){
        if (g[x][y][z][t]!=-1) return g[x][y][z][t];
        if (prime(x,y,z,t)) {
            g[x][y][z][t]=0;
            return 0;
        }

        ArrayList<Integer> min = new ArrayList<Integer>();
        int i,j,k;

        for(i=x+1;i<=z;i++){
            k = grundy(x,y,i-1,t)^grundy(i,y,z,t);
            if(!min.contains(k)) min.add(k);
        }

        for(i=y+1;i<=t;i++){
            k = grundy(x,y,z,i-1)^grundy(x,i,z,t);
            if(!min.contains(k)) min.add(k);
        }

        for(k=0;min.contains(k);k++);


        g[x][y][z][t]=k;
        return k;
    }
    
}

Digits Square Board problem solution in C++.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

const int M=60;

int a[M][M],gr[M][M][M][M];
int n,t;

int prime_check(int x, int y, int z,  int m)
{
  for (int i=x;i<=z;i++)
    for (int j=y;j<=m;j++)
    if (a[i][j]==1 || a[i][j]==4 || a[i][j]==6 || a[i][j]==8 || a[i][j]==9) return 0;

    return 1;
}

int grundy(int x, int y, int z,int m)
{
    int v[75];

   if (gr[x][y][z][m]!=-1) return gr[x][y][z][m];
   if (prime_check(x,y,z,m))
   {
     gr[x][y][z][m]=0;
     return 0;
   }

  for (int i=0;i<75;i++)
    v[i]=0;

  for (int i=x+1;i<=z;i++) v[grundy(x,y,i-1,m)^grundy(i,y,z,m)]=1;
  for (int i=y+1;i<=m;i++) v[grundy(x,y,z,i-1)^grundy(x,i,z,m)]=1;


     for (int i=0;i<75;i++)
        if (v[i]==0)
     {
         gr[x][y][z][m]=i;
         return gr[x][y][z][m];
     }
     return -1;
}

void solve()
{
    scanf("%d",&n);

    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
     scanf("%d",&a[i][j]);


      for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
          for (int k=1;k<=n;k++)
            for (int l=1;l<=n;l++)
              gr[i][j][k][l]=-1;

    grundy(1,1,n,n);

   if (gr[1][1][n][n]!=0) printf("Firstn"); else printf("Secondn");

   return;

}

int main()
{
    scanf("%d",&t);

    while(t--)
        solve();

    return 0;
}

Problem solution in C.

#include <stdio.h>
#define N 35

int b[N][N], SG[N][N][N][N], pl[N][N][N][N];

int isprime(int d) {
    return (d==2) || (d==3) || (d==5) || (d==7);
}

int getSG(int i, int j, int k, int l) {
    int x, SGT[2*N];    
    if(SG[i][j][k][l]!=-1) return SG[i][j][k][l];
    if(!pl[i][j][k][l]) {
        SG[i][j][k][l]=0;
        return 0;
    }
    for(x=0; x<2*N; x++) SGT[x]=0;
    for(x=i; x<k; x++) SGT[getSG(i,j,x,l)^getSG(x+1,j,k,l)]=1;
    for(x=j; x<l; x++) SGT[getSG(i,j,k,x)^getSG(i,x+1,k,l)]=1;
    for(x=0; SGT[x]!=0; x++);
    SG[i][j][k][l]=x;  
    return x;
}

int main() {
    int i, j, k, l, n, ncases;
    for(scanf("%d", &ncases); ncases>0; ncases--) {
        scanf("%d", &n);
        for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d", &b[i][j]);
        for(i=0; i<n; i++) for(j=0; j<n; j++)
            for(k=i; k<n; k++) for(l=j; l<n; l++) {
                pl[i][j][k][l]=0;
                if(k>i && pl[i][j][k-1][l]) pl[i][j][k][l]=1;
                if(l>j && pl[i][j][k][l-1]) pl[i][j][k][l]=1;
                if(!isprime(b[k][l])) pl[i][j][k][l]=1;
            }
        for(i=0; i<n; i++) for(j=0; j<n; j++)
            for(k=i; k<n; k++) for(l=j; l<n; l++) {
                 SG[i][j][k][l]=-1;
        }                 
        for(i=0; i<n; i++) for(j=0; j<n; j++)
            for(k=i; k<n; k++) for(l=j; l<n; l++) {
                 fflush(stdout);
                 SG[i][j][k][l]=getSG(i,j,k,l);
        }                 
        if(SG[0][0][n-1][n-1]==0) printf("Secondn");
        else printf("Firstn");
    }
    return 0;
}