In this HackerRank Bowling Pins problem solution Complete the function iswinning that takes the number of pins and the configuration of the pins as input, and return WIN or LOSE based on whether or not you will win. Given the current configuration of the pins, if both of you play optimally, determine whether you will win this game or not.
Problem solution in Python.
#!/bin/python3 import os import sys g = {0:0,1:1,2:2} for i in range(3,301): found = set() for j in range(i-1): found.add(g[j]^g[i-j-1]) found.add(g[j]^g[i-j-2]) g[i] = min(set(range(max(found)+2))-found) def isWinning(n, config): tot = 0 L = 0 config += "X" for i in config: if i == "I": L+=1 else: tot = tot^g[L] L = 0 if tot != 0: return "WIN" return "LOSE" if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') t = int(input()) for t_itr in range(t): n = int(input()) config = input() result = isWinning(n, config) fptr.write(result + 'n') fptr.close()
Problem solution in Java.
import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { static int[] grundy; static String isWinning(int length, String config) { String[] tokens = config.split("X"); int p = 0; for(String token : tokens) { p ^= grundy[token.length()]; } return p > 0 ? "WIN" : "LOSE"; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int t = Integer.parseInt(scanner.nextLine().trim()); grundy = new int[301]; grundy[0] = 0; grundy[1] = 1; grundy[2] = 2; for(int n = 3; n < grundy.length; n++) { List<Integer> g2 = new ArrayList<>(); for(int p = 1; p <= 2; p++) { for(int s = 0; s < ((n - p) / 2) + 1; s++) { g2.add(grundy[s]^grundy[n - p - s]); } } int m = 0; boolean found = false; do { found = false; for(int i = 0; i < g2.size(); i++) { if(g2.get(i) == m) { found = true; m++; } } } while(found); grundy[n] = m; } System.out.print("Found grundy: "); for(int i = 0; i < 20; i++) { System.out.print(grundy[i] + " "); } System.out.println(); for (int tItr = 0; tItr < t; tItr++) { int n = Integer.parseInt(scanner.nextLine().trim()); String config = scanner.nextLine(); String result = isWinning(n, config); bufferedWriter.write(result); bufferedWriter.newLine(); } bufferedWriter.close(); } }
Problem solution in C++.
#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("%sn", res? "WIN": "LOSE"); } return 0; }
Problem solution in C.
#include <stdio.h> #include <stdlib.h> #include <string.h> char str[301]; int dp[301],a[4000]; int main(){ int T,N,c,i,j; for(dp[0]=0,i=1;i<301;i++){ memset(a,0,sizeof(a)); for(j=0;j<=i-1-j;j++) a[dp[j]^dp[i-1-j]]=1; for(j=0;j<=i-2-j;j++) a[dp[j]^dp[i-2-j]]=1; for(j=0;a[j];j++); dp[i]=j; } scanf("%d",&T); while(T--){ scanf("%d%s",&N,str); for(i=c=j=0;i<N;i++){ if(str[i]=='I') c++; else if(str[i]=='X' && i && str[i-1]=='I'){ j^=dp[c]; c=0; } } j^=dp[c]; if(j) printf("WINn"); else printf("LOSEn"); } return 0; }