Table of Contents
Bowling Pins – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
const int Maxn = 305;
int nim[Maxn];
int t;
int n;
char str[Maxn];
int main() {
for (int i = 1; i < Maxn; i++) {
set <int> S;
for (int j = 0; j < i; j++)
S.insert(nim[j] ^ nim[i - 1 - j]);
for (int j = 0; j + 1 < i; j++)
S.insert(nim[j] ^ nim[i - 2 - j]);
while (S.find(nim[i]) != S.end()) nim[i]++;
}
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
scanf("%s", str);
int res = 0;
for (int i = 0; i < n; i++) if (str[i] == 'I') {
int j = i;
while (j < n && str[j] == 'I') j++;
res ^= nim[j - i];
i = j;
}
printf("%s\n", res? "WIN": "LOSE");
}
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int[] nim = new int[301];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while(t-- > 0) {
int n = in.nextInt();
String s = in.next();
List<Integer> list = new ArrayList<Integer>();
int count = 0;
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if(ch == 'I') {
count++;
} else {
if(count != 0)
list.add(count);
count = 0;
}
}
if(count > 0)
list.add(count);
int result = 0;
for(int i = 0; i < list.size(); i++) {
result ^= grundy(list.get(i));
}
if(result <= 0) {
System.out.println("LOSE");
} else {
System.out.println("WIN");
}
}
in.close();
}
private static int mex(List<Integer> arr) {
int mex = 0;
while(arr.contains(mex))
mex++;
return mex;
}
private static int grundy(int n) {
if(nim[n] != 0)
return nim[n];
if(n == 0) {
nim[0] = 0;
return 0;
}
if (n == 1) {
nim[1] = 1;
return (1);
}
if (n == 2) {
nim[2] = 2;
return (2);
}
List<Integer> list = new ArrayList<Integer>();
for(int i = 1, j = 0, k = 0; i <= n; i++) {
int x, y;
if(i <= n / 2) {
x = grundy(j);
y = grundy(n - j - 2);
j++;
} else {
x = grundy(k);
y = grundy(n - k - 1);
k++;
}
list.add(x ^ y);
}
nim[n] = mex(list);
return nim[n];
}
}
Python 3 rep HackerRank Solution
def get_or_update(key, f):
if key not in cache:
cache[key] = f()
return cache[key]
def replace_at_index(tup, ix, val):
return tup[:ix] + (val,) + tup[ix+1:]
def pin_to_nim(pins):
nim = []
curr_pile = 0
for i in range(len(pins)):
if pins[i]:
curr_pile += 1
else:
if curr_pile>0:
nim.append(curr_pile)
curr_pile = 0
if curr_pile > 0:
nim.append(curr_pile)
return tuple(nim)
def nim_to_pin(nim):
pin = []
for x in nim:
pin.extend([True]*x)
pin.append(False)
return tuple(pin[:-1])
def get_new_configs(pins, N):
new_configs = set()
for i in range(N):
if pins[i]:
new_config = replace_at_index(pins, i, False)
new_configs.add(new_config)
if (i<=N-2) and (pins[i+1]):
new_config = replace_at_index(new_config, i+1, False)
new_configs.add(new_config)
return new_configs
def get_winner(pins, N):
new_configs = get_new_configs(pins, N)
if not new_configs:
return 2
elif new_configs == {tuple([False]*5)}:
return 1
else:
next_winners = [get_or_update(config, lambda: get_winner(config, N)) for config in new_configs]
if any([nw==2 for nw in next_winners]):
return 1
else:
return 2
grundy_cache = {1: 1, 2: 2}
def get_or_update(key, f):
if key not in cache:
cache[key] = f()
return cache[key]
def get_grundy_number(nbr):
if nbr in grundy_cache:
return grundy_cache[nbr]
else:
pin_config = nim_to_pin((nbr,))
n = len(pin_config)
next_nim_configs = {pin_to_nim(x) for x in get_new_configs(pin_config, n)}
next_grundys = sorted([get_config_grundy(nnc) for nnc in next_nim_configs])
mex = 0
for ng in next_grundys:
mex = mex+1 if ng==mex else mex
grundy_cache[nbr] = mex
return mex
def get_config_grundy(nim_config):
rv = 0
for x in nim_config:
rv = rv^get_grundy_number(x)
return rv
T = int(input())
for _ in range(T):
N = int(input())
pins = tuple([x == 'I' for x in input()])
cache = dict()
if get_config_grundy(pin_to_nim(pins)):
print('WIN')
else:
print('LOSE')
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys,re
cache = {0:0, 1:1, 2:2}
def nimber_sum(a,b):
return a^b
def nimber(l):
if l in cache:
return cache[l]
heap = set()
for i in range(l):
heap.add(nimber_sum(nimber(i), nimber(l-1-i)))
#print ' sum',i,l-i-1,nimber_sum(i, l-1-i)
for i in range(l-1):
heap.add(nimber_sum(nimber(i), nimber(l-2-i)))
#print ' sum',i,l-i-2,nimber_sum(i, l-2-i)
n=0
while n in heap:
n += 1
cache[l] = n
#print 'nimber',l,n,heap
return cache[l]
def test_win(pins):
pins = pins.strip('X')
pins = re.sub(r'XX+', 'X', pins)
pins_list = pins.split('X')
n = 0
for p in pins_list:
n = nimber_sum(n, nimber(len(p)))
return (n != 0)
num_tests = int(sys.stdin.readline())
for num_test in range(num_tests):
num_pins = int(sys.stdin.readline())
pins = sys.stdin.readline().strip()
win = test_win(pins)
if win:
print 'WIN'
else:
print 'LOSE'
C rep HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int grundy[301];
void calcgrundy() {
grundy[0] = 0;
grundy[1] = 1;
grundy[2] = 2;
grundy[3] = 3;
int gset[512];
for (int i = 4; i <= 300; i++) {
memset(gset, 0, sizeof(gset));
int maxgset = gset[i-2];
gset[grundy[i-2]] = 1;
gset[grundy[i-1]] = 1;
if (maxgset < gset[i-1]) maxgset = gset[i-1];
for (int sp = 1; sp <= (i-1)/2; sp++) {
int gn = grundy[sp] ^ grundy[i - 1 - sp];
gset[gn] = 1;
if (maxgset < gn) maxgset = gn;
}
for (int sp = 1; sp < i/2; sp++) {
int gn = grundy[sp] ^ grundy[i - 2 - sp];
gset[gn] = 1;
if (maxgset < gn) maxgset = gn;
}
int j = 0;
while (j <= maxgset && gset[j]) j++;
grundy[i] = j;
fprintf(stderr, "grundy %d = %d\n", i, j);
}
}
int iwin2(int n, char *p) {
int nimber = 0;
int run = 0;
for (int i = 0; i < n; i++) {
if (p[i] == 'I') run++;
else {
nimber ^= grundy[run];
run = 0;
}
}
nimber ^= grundy[run];
return nimber != 0;
}
int main() {
int t;
calcgrundy();
scanf("%d\n", &t);
for (int tc = 0 ; tc < t; tc++) {
int n;
scanf("%d\n", &n);
char p[n+2];
memset(p,'X', sizeof(p));
fgets(p, n+1, stdin);
int result = iwin2(n,p);
if (result) {
printf("WIN\n");
} else {
printf("LOSE\n");
}
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
