We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Digits Square Board
  5. Discussions

Digits Square Board

Sort by

recency

|

13 Discussions

|

  • mtammy779
     + 0 comments

    Explore Volcon is a fascinating concept car designed to revolutionize electric mobility with its innovative technology and sustainability focus. The Digits Square Board, on the other hand, is a unique mathematical puzzle that challenges logic and problem-solving skills, making it a delightful mental exercise for enthusiasts of all ages.

  • thecodingsoluti2
     + 0 comments

    Here is Digits Square Board problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-digits-square-board-problem-solution.html

  • cafelatte
     + 1 comment

    First full score Python 3 solution for this problem:
    According to the leaderboard no other Python3 solution was fast enough for all test cases (test case 3 with 10 boards of size 30x30 IS tough).
    After some tests and optimization I finally succeeded with it and now take the liberty of throwing that code at you ;-) 

    # document globals
N = None    # board size 
B = None    # board in 0/1 (is prime?)
G = None    # grundy
RINT = None # rows in B as Int
CINT = None # columns in B as Int

#
# Complete the 'squareBoard' function below.
#
# The function is expected to return a STRING.
# The function accepts 2D_INTEGER_ARRAY board as parameter.
#
def squareBoard(board):
    analyze(board)
    return 'First' if G[0][N-1][0][N-1] else 'Second'

def analyze(board):
    global N, B, G, RINT, CINT
    N = len(board)
    primes = {2,3,5,7}
    B = [[int(n not in primes) for n in row] for row in board]
    RINT = [ int(''.join(str(d) for d in reversed(row)),2) for row in B]
    CINT = [ int(''.join(str(d) for d in reversed(row)),2) for row in zip(*B)]
    G = [[[[0] * N for i2 in range(N)] for i3 in range(N)] for i4 in range(N)]
    GT = [[[[0] * N for i2 in range(N)] for i3 in range(N)] for i4 in range(N)]
    if not any(rint for rint in RINT):
        G[0][N-1][0][N-1] = 0
        return
    # fill in grundy numbers for all rectangles [rlo,rhi] x [clo,chi]
    # grundy is ...
    #   0 if rectangle is size 1 or doesn't contain any nonprime,
    #   else mex of all (cut into two pieces and xor them)
    for rsize in range(1,N +1):
        for csize in range(1,N +1):
            if rsize==1==csize: continue
            for rlo in range(N-rsize +1):
                rhi = rlo + rsize -1
                for clo in range(N-csize +1):
                    chi = clo + csize -1
                    # look for nonprime
                    if rsize < csize:
                        mask = get_mask(clo,chi)
                        if not any(RINT[ri] & mask for ri in range(rlo,rhi+1)):
                            continue
                    else:
                        mask = get_mask(rlo,rhi)
                        if not any(CINT[ci] & mask for ci in range(clo,chi+1)):
                            continue
                    # okay, there is some nonprime, so must do cuts ...
                    grundy = [0] * 40
                    #   ... by row [rlo,rcut] + [rcut+1,rhi]
                    GT_slice = GT[clo][chi]
                    for rcut in range(rlo,rhi):
                        grundy[GT_slice[rlo][rcut] ^ GT_slice[rcut+1][rhi]] = 1
                    #   ... by col [clo,ccut] + [ccut+1,chi]
                    G_slice = G[rlo][rhi]
                    for ccut in range(clo,chi):
                        grundy[G_slice[clo][ccut] ^ G_slice[ccut+1][chi]] = 1
                    mex = grundy.index(0)
                    G_slice[clo][chi] = mex
                    GT_slice[rlo][rhi] = mex
                    
    
def get_mask(i,j):
    return (1<<j+1) - (1<<i)

  • bahaa_lashin
     + 0 comments

    How can i return the result ? after I have fixed it I'm trying to return the result but every time it's show me an issue I tryed to return as a list like ['Second','First'] or string like 'Second\nFirst' but nothing happen.

  • arsegorov
     + 1 comment

    I wonder what the time limit/estimate for a single 30x30 matrix in Python 3 is.

    I used a single bytes sequence to store the matrix' bits (rows first), so I would only need to split it once to make a horizontal cut. For the vertical cuts I transposed the matrix first, so that would only need to be cut once.

    I cached the already found Grundy numbers in a dict, so I wouldn't need to traverse them again.

    So far, I got it down to a consistent 7.3 s on a random matrix on my machine, but that still fails tests 3 and 4. I ran out of ideas.

    Should I be using a different data structure? I tried the same algorithm, but storing data as an integer, setting the individual bits, but that turned out to be way slower.