HackerRank Mixing proteins problem solution

In this HackerRank Mixing proteins problem solution Some scientists are working on protein recombination, and during their research, they have found a remarkable fact: there are 4 proteins in the protein ring that mutate after every second according to a fixed pattern. For simplicity, proteins are called A, B, C, D (you know, protein names can be very complicated). A protein mutates into another one depending on itself and the protein right after it. Scientists determined that the mutation table goes like this:

    A   B   C   D

    _   _   _   _

A|  A   B   C   D

B|  B   A   D   C

C|  C   D   A   B

D|  D   C   B   A

Here rows denote the protein at the current position, while columns denote the protein at the next position. And the corresponding value in the table denotes the new protein that will emerge. So for example, if protein i is A, and protein I + 1 is B, protein I will change to B. All mutations take place simultaneously. The protein ring is seen as a circular list, so the last protein of the list mutates depending on the first protein.

Using this data, they have written a small simulation software to get mutations second by second. The problem is that the protein rings can be very long (up to 1 million proteins in a single ring) and they want to know the state of the ring after up to 10 to power 9 seconds. Thus their software takes too long to report the results. They ask you for your help.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys


import sys

c2i = {'A': 0, 'B': 1, 'C': 2, 'D': 3}
i2c = ['A', 'B', 'C', 'D']

n, k = [int(x) for x in input().strip().split()]

s = [c2i[x] for x in input().strip()]
s = [s, [0] * len(s)]

a, b = 1, 0

while k > 0:
    a ^= b
    b ^= a
    a ^= b
    
    cp2 = 1
    for i in range(29, 0, -1):
        if k - (1 << i) >= 0:
            cp2 = 1 << i
            break
            
    k -= cp2
    
    for i in range(n):
        s[b][i] = s[a][i] ^ s[a][(i + cp2) % n]
        

for i in s[b]:
    sys.stdout.write(i2c[i])
    
sys.stdout.flush()

Problem solution in Java.

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

public class Solution {

    static String pmix(String s, int k) {
       
        int n = s.length();
        int[]  arrCode = new int[n];
        for (int i=0; i<n;i++){
            switch(s.charAt(i)){
                case 'A': arrCode[i] = 0; break;
                case 'B': arrCode[i] = 1; break;
                case 'C': arrCode[i] = 2; break;
                case 'D': arrCode[i] = 3; break;
            }
        }
        int[][] modify = {{0,1,2,3},{1,0,3,2},{2,3,0,1},{3,2,1,0}};
        
        for (int j = Integer.highestOneBit(k); k>0; k-=j, j=Integer.highestOneBit(k)){
            int[]  arrCode2 = new int[n];
            for (int l=0,shift2 = j%n; l<n; l++, shift2++){
                if (shift2>=n)shift2 = 0;
                arrCode2[l]=modify[arrCode[l]][arrCode[shift2]];  
            } 
            arrCode = arrCode2;
        }
        
        String[] maping = {"A","B","C","D"};
        String[] resChar = new String[n];
        for (int i =0;i<n;i++) {
            resChar[i]=maping[arrCode[i]];
        }
        String res= String.join("",resChar);
       
        return res;

    }
    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")));

        String[] nk = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nk[0].trim());

        int k = Integer.parseInt(nk[1].trim());

        String s = scanner.nextLine();

        String result = pmix(s, k);

        bufferedWriter.write(result);
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define MAXN 1000050

int N, K;
string S;
int A[MAXN];
int B[MAXN];

int main() {

	cin.sync_with_stdio(false);
	
	cin >> N >> K >> S;
	
	for (int i = 0; i < N; i++) {
		A[i] = S[i] - 'A';
	}
	for (int j = 30; j >= 0; j--) {
		if (K & (1 << j)) {
  			for (int i = 0; i < N; i++) {
				int o = (i - (1 << j)) % N;
				if (o < 0) {
					o += N;
				}
 				B[o] = A[i] ^ A[o];
			}
			memcpy(A, B, sizeof(A));
		}
	}
	
  	for (int i = 0; i < N; i++) {
		S[i] = A[i] + 'A';
	}
	cout << S << endl;
	
	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int i, j, n, k, c, *prot, *protnew, p2;
    scanf("%d %d",&n,&k);
    prot = malloc(n * sizeof(int));
    protnew = malloc(n * sizeof(int));
    for (i=0; i<n; i++) {
        while (c=getchar()-'A') if (c>=0 && c<=3) break;
        prot[i] = c;
    }
    p2 = 1;
    while (p2<k) p2 <<= 1;
    while (p2 >>= 1) {
        if (p2 & k) {
            for (i=0; i<n; i++) protnew[i] = prot[i] ^ prot[(i+p2) % n];
            for (i=0; i<n; i++) prot[i] = protnew[i];
        }
    }
    for (i=0; i<n; i++) putchar('A' + prot[i]);
    putchar('\n');
    return 0;
}