Header Ad

HackerRank Hamming Distance problem solution

In this HackerRank Hamming Distance problem solution, we have given a string S that consists of N small Latin letters 'a' and 'b'. we also have given M queries to process. we need to find the hamming distance between the consecutive substrings that starts at L1 and L2 respectively and have the length of len.

HackerRank Hamming Distance problem solution


Problem solution in Java.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Solution {
    private static final char LINE_END = '\n';
    private final InputStream input;
    private final OutputStream output;
    private final CommandFactory commandFactory;
    private final CommandExecutor commandExecutor;
    private final ByteArrayOutputStream outputBuffer;
    private char[] string;

    public static void main(String[] args) {
        Solution solutionHammingDistance = new Solution(System.in, System.out);
        try {
            solutionHammingDistance.process();
        } catch (IOException e) {
            throw new IllegalArgumentException(e);
        }
    }

    public Solution(InputStream input, OutputStream output) {
        this.input = input;
        this.output = output;
        commandFactory = new CommandFactory();
        commandExecutor = new CommandExecutor();
        outputBuffer = new ByteArrayOutputStream();
    }

    public void process() throws IOException  {
        readInt();
        string = readLine().toCharArray();
        readInt();
        Queue<Command> commands = processCommands();

        while (!commands.isEmpty()) {
            commandExecutor.execute(commands.remove());
        }

        output.write(outputBuffer.toByteArray());
    }

    private Queue<Command> processCommands() {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(input));
        return bufferedReader.lines().map(commandFactory::create).collect(Collectors.toCollection(LinkedList::new));
    }

    private int readInt() throws IOException {
        String line = readLine();
        return Integer.valueOf(line);
    }

    private String readLine() throws IOException {
        StringBuilder line = new StringBuilder();
        int readByte = input.read();
        while (readByte != -1) {
            line.append((char) readByte);
            readByte = input.read();
            if (readByte == LINE_END) {
                return line.toString();
            }
        }
        return line.toString();
    }

    private class CommandFactory {
        private Command create(String commandString) {
            char commandType = commandString.charAt(0);
            String[] commandArguments = commandString.split(" ");
            Command commandToReturn;
            switch (commandType) {
                case 'H': {
                    HammingDistance command = new HammingDistance();
                    command.firstStart = createIndex(commandArguments[1]);
                    command.secondStart = createIndex(commandArguments[2]);
                    command.length = Integer.valueOf(commandArguments[3]);
                    commandToReturn = command;
                    break;
                }
                case 'C': {
                    Change command = new Change();
                    command.left = createIndex(commandArguments[1]);
                    command.right = createIndex(commandArguments[2]);
                    command.ch = commandArguments[3].charAt(0);
                    commandToReturn = command;
                    break;
                }
                case 'S': {
                    Swap command = new Swap();
                    command.left1 = createIndex(commandArguments[1]);
                    command.right1 = createIndex(commandArguments[2]);
                    command.left2 = createIndex(commandArguments[3]);
                    command.right2 = createIndex(commandArguments[4]);
                    commandToReturn = command;
                    break;
                }
                case 'R': {
                    Reverse command = new Reverse();
                    command.left = createIndex(commandArguments[1]);
                    command.right = createIndex(commandArguments[2]);
                    commandToReturn = command;
                    break;
                }
                case 'W': {
                    Wipe command = new Wipe();
                    command.left = createIndex(commandArguments[1]);
                    command.right = createIndex(commandArguments[2]);
                    commandToReturn = command;
                    break;
                }
                default:
                    throw new IllegalArgumentException("Cannot found command! String: " + commandString);
            }
            return commandToReturn;
        }

        private int createIndex(String index) {
            return Integer.valueOf(index) - 1;
        }
    }

    private class CommandExecutor {
        private void execute(Command command) throws IOException {
            if (command instanceof MutingCommand) {
                string = command.execute(string);
            } else if (command instanceof OutputCommand) {
                String result = new String(command.execute(string));
                result += LINE_END;
                outputBuffer.write(result.getBytes());
            }
        }
    }

    private interface MutingCommand extends Command {
    }

    private interface OutputCommand extends Command {
    }

    private interface Command {
        char[] execute(char[] string);
    }

    private class HammingDistance implements OutputCommand {
        int firstStart;
        int secondStart;
        int length;

        @Override
        public char[] execute(char[] string) {
            long sum = 0L;
            for (int i = 0; i < length; i++) {
                if (string[firstStart + i] != string[secondStart + i]) {
                    sum++;
                }
            }
            return Long.toString(sum).toCharArray();
        }
    }

    private class Change implements MutingCommand {
        int left;
        int right;
        char ch;


        @Override
        public char[] execute(char[] string) {
            for (int i = left; i <= right; i++) {
                string[i] = ch;
            }
            return string;
        }
    }

    private class Swap implements MutingCommand {
        int left1;
        int right1;
        int left2;
        int right2;

        @Override
        public char[] execute(char[] string) {
            char[] newString = Arrays.copyOf(string, string.length);
            int i = left1;
            int rightSize = right2 - left2 + 1;
            int leftSize = right1 - left1 + 1;
            int restSize = left2 - right1 - 1;
            for (int j = 0; i < left1 + rightSize; i++, j++) {
                newString[i] = string[left2 + j];
            }
            for (int j = 0; i < left1 + rightSize + restSize; i++, j++) {
                newString[i] = string[left1 + leftSize + j];
            }
            for (int j = 0; i < left1 + rightSize + restSize + leftSize; i++, j++) {
                newString[i] = string[left1 + j];
            }
            return newString;

        }
    }

    private class Reverse implements MutingCommand {
        int left;
        int right;

        @Override
        public char[] execute(char[] string) {
            char[] chars = Arrays.copyOf(string, string.length);
            for (int i = 0; i <= right - left; i++) {
                chars[right - i] = string[left + i];
            }
            return chars;
        }
    }

    private class Wipe implements OutputCommand {
        private int left;
        private int right;

        @Override
        public char[] execute(char[] string) {
            return new String(string).substring(left, right + 1).toCharArray();
        }
    }

}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;


int main() {
    int n, m;

    cin >> n;
    char* s = new char[n+1];
   
    char* tmp1 = new char[n+1];
    char* tmp2 = new char[n+1];
    cin.ignore();
    cin.getline(s, n+1);
    
    cin >> m;
    
    
    while(m--) {
        char type; cin >> type;
        if(type == 'C') {
            int left, right;
            char c;
            cin >> left >> right >> c;
            memset(s + left - 1, c, right - left + 1);
        } else if(type == 'S') {
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;
            
            int sl = r1 - l1 + 1;
            int sm = l2 - r1 - 1;
            int sr = r2 - l2 + 1;
            
            
            memcpy(tmp1, s + l1 - 1     , sl);
            memcpy(tmp2, s + l1 - 1 + sl, sm);
            
            memmove(s + l1 - 1         , s + l2 - 1, sr);
            memcpy(s + l1 - 1 + sr     , tmp2      , sm);
            memcpy(s + l1 - 1 + sr + sm, tmp1      , sl);
            
           
        } else if(type == 'R') {
            int left, right; cin >> left >> right;
            reverse(s + left - 1, s + right);
        } else if(type == 'W') {
            int left, right; cin >> left >> right;
            printf("%.*s\n", right - left + 1, s + left - 1);
        } else if(type == 'H') {
            int l1, l2, len; cin >> l1 >> l2 >> len;
            int sum = 0;
            int i = l1 - 1, j = l2 - 1;
            for( ; i + 7 < l1 - 1 + len; i+= 8, j+= 8) {
                sum += (s[i] != s[j]);
                sum += (s[i+1] != s[j+1]);
                sum += (s[i+2] != s[j+2]);
                sum += (s[i+3] != s[j+3]);
                sum += (s[i+4] != s[j+4]);
                sum += (s[i+5] != s[j+5]);
                sum += (s[i+6] != s[j+6]);
                sum += (s[i+7] != s[j+7]);           
            }
            for(; i < l1 - 1 + len; i++, j++) {
                sum += (s[i] != s[j]);
            }
            printf("%d\n", sum);
        }

    }

    return 0;
}


Problem solution in C.

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

typedef enum {SET, SWAP, REVERSE, WRITE, HAMMING} tCmdCode;

typedef struct {
    tCmdCode cmd;
    int p[4];
} tCommand;

static inline int getInt() {
    int res = 0;
    char c = getchar();
    while (c >= '0' && c <= '9') {
        res = res*10 + (int)(c-'0');
        c = getchar();
    }
    return res;
}

static inline void processSet(char S[], int l, int r, char ch) {
    memset(S+l, ch, r-l+1);
}

static inline void processSwap(char S[], char tS[], int l1, int r1, int l2, int r2) {
    int i = l1;

    int n = 0;
    memcpy(tS+n, S+l2, r2-l2+1);
    n += r2-l2+1;
    if (r1+1 <= l2) {
        memcpy(tS+n, S+(r1+1), l2-r1-1);
        n += l2-r1-1;
    }
    memcpy(tS+n, S+l1, r1-l1+1);
    n += r1-l1+1;
    memcpy(S+l1, tS, n);
}

static inline void processReverse(char * S, int l, int r) {
    int i = l;
    int j = r;
    char tmp;

    while (i < j) {
        tmp = S[i];
        S[i] = S[j];
        S[j] = tmp;
        i++;
        j--;
    }
}

static inline void processWrite(char * S, int l, int r) {
    fwrite(S+l, 1, r-l+1, stdout);
    putchar('\n');
}

static inline void processHamming(char S[], int l1, int l2, int len) {
    int distance = 0;
    int i = len;
    int i1 = l1;
    int i2 = l2;
    unsigned long long ps = 0;
    int j = 0;
    while (i >= 8) {
        unsigned long long *p1 = S+i1;
        unsigned long long *p2 = S+i2;
        ps += ((*p1) ^ (*p2)) & (0x0101010101010101ull);
        j += 1;
        if (j == 255) {
            for (int k = 0; k<8; k++) {
                distance += ps & 0xFF;
                ps = ps >> 8;
            }
            j = 0;
        }
        i -= 8;
        i1 += 8;
        i2 += 8;
    }
    for (int k = 0; k < 8; k++) {
        distance += ps & 0xFF;
        ps = ps >> 8;
    }

    for (; i > 0; i--, i1++, i2++)
        distance += (int)(S[i1] != S[i2]);
    printf("%d\n", distance);
}

int main() {
    int N;
    scanf("%d", &N);
    getchar();
#ifdef DEBUG
    printf("N = %d\n", N);
#endif
    char * S = malloc(N);
    char * tS = malloc(N);
    fread(S, 1, N, stdin);
    getchar();
    int M;
    scanf("%d", &M);
    getchar();
#ifdef DEBUG
    printf("M = %d\n", M);
#endif
    tCommand cmd;
#ifdef DEBUG
    printf("before: ");
    processWrite(S, 0, N-1);
#endif
    for (int i = 0; i< M; i++) {
        char cmd = getchar();
        getchar(); // space
        int l, r, l1, l2, r1, r2, len;
        char c;
        switch (cmd) {
            case 'C':
                l = getInt()-1;
                r = getInt()-1;
                c = getchar();
                processSet(S, l, r, c);
                getchar();
                break;
            case 'S':
                l1 = getInt()-1;
                r1 = getInt()-1;
                l2 = getInt()-1;
                r2 = getInt()-1;
                processSwap(S, tS, l1, r1, l2, r2);
                break;
            case 'R':
                l = getInt()-1;
                r = getInt()-1;
                processReverse(S, l, r);
                break;
            case 'W':
                l = getInt()-1;
                r = getInt()-1;
                processWrite(S, l, r);
                break;
            case 'H':
                l1 = getInt()-1;
                l2 = getInt()-1;
                len = getInt();
                processHamming(S, l1, l2, len);
                break;
        }
#ifdef DEBUG
        printf("after: ");
        processWrite(S, 0, N-1);
#endif
    }

    free(S);
    free(tS);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    return 0;
}


Post a Comment

0 Comments