working on it ...

Filters

Explore Public Snippets

Sort by

Found 890 snippets matching: hackerrank

    public by te777 modified Sep 24, 2016  3095  7  5  0

    Hackerrank Count Strings solution python

    Hackerrank Count Strings solution python
    '''
    Created on Aug 7, 2016
    
    AutomataTheory.py
    
    @author: Siddharthasahu @ https://github.com/siddharthasahu/automata-from-regex
    
    Automata build from from regex to DFA taken from there. Count Strings (Matrix class) added
    '''
    # You can test with input " 1 ((((ab)|a)*)|(((aa)|(bb))*)) 368046388 "
    
    #The result of the code executed in main should be 198110437 with the test input
    
    #import fileinput
    #from os import popen
    #import time
    #import sys, traceback
    
    class Automata:
        """class to represent an Automata"""
    
        def __init__(self, language = set(['a', 'b'])):
            self.states = set()
            self.startstate = None
            self.finalstates = []
            self.transitions = dict()
            self.language = language
    
        @staticmethod
        def epsilon():
            return ":e:"
    
        def setstartstate(self, state):
            self.startstate = state
            self.states.add(state)
    
        def addfinalstates(self, state):
            if isinstance(state, int):
                state = [state]
            for s in state:
                if s not in self.finalstates:
                    self.finalstates.append(s)
    
        def addtransition(self, fromstate, tostate, inp):
            if isinstance(inp, str):
                inp = set([inp])
            self.states.add(fromstate)
            self.states.add(tostate)
            if fromstate in self.transitions:
                if tostate in self.transitions[fromstate]:
                    self.transitions[fromstate][tostate] = self.transitions[fromstate][tostate].union(inp)
                else:
                    self.transitions[fromstate][tostate] = inp
            else:
                self.transitions[fromstate] = {tostate : inp}
    
        def addtransition_dict(self, transitions):
            for fromstate, tostates in transitions.items():
                for state in tostates:
                    self.addtransition(fromstate, state, tostates[state])
    
        def gettransitions(self, state, key):
            if isinstance(state, int):
                state = [state]
            trstates = set()
            for st in state:
                if st in self.transitions:
                    for tns in self.transitions[st]:
                        if key in self.transitions[st][tns]:
                            trstates.add(tns)
            return trstates
    
        def getEClose(self, findstate):
            allstates = set()
            states = set([findstate])
            while len(states)!= 0:
                state = states.pop()
                allstates.add(state)
                if state in self.transitions:
                    for tns in self.transitions[state]:
                        if Automata.epsilon() in self.transitions[state][tns] and tns not in allstates:
                            states.add(tns)
            return allstates
    
        def display(self):
            print ("states:", self.states)
            print ("start state: ", self.startstate)
            print ("final states:", self.finalstates)
            print ("transitions:")
            for fromstate, tostates in self.transitions.items():
                for state in tostates:
                    for char in tostates[state]:
                        print ("  ",fromstate, "->", state, "on '"+char+"'",)
                print
    
        def getPrintText(self):
            text = "language: {" + ", ".join(self.language) + "}\n"
            text += "states: {" + ", ".join(map(str,self.states)) + "}\n"
            text += "start state: " + str(self.startstate) + "\n"
            text += "final states: {" + ", ".join(map(str,self.finalstates)) + "}\n"
            text += "transitions:\n"
            linecount = 5
            for fromstate, tostates in self.transitions.items():
                for state in tostates:
                    for char in tostates[state]:
                        text += "    " + str(fromstate) + " -> " + str(state) + " on '" + char + "'\n"
                        linecount +=1
            return [text, linecount]
    
        def newBuildFromNumber(self, startnum):
            translations = {}
            for i in list(self.states):
                translations[i] = startnum
                startnum += 1
            rebuild = Automata(self.language)
            rebuild.setstartstate(translations[self.startstate])
            rebuild.addfinalstates(translations[self.finalstates[0]])
            for fromstate, tostates in self.transitions.items():
                for state in tostates:
                    rebuild.addtransition(translations[fromstate], translations[state], tostates[state])
            return [rebuild, startnum]
    
        def newBuildFromEquivalentStates(self, equivalent, pos):
            # Added "sorted" next line
            rebuild = Automata(sorted(self.language))
            for fromstate, tostates in self.transitions.items():
                for state in tostates:
                    rebuild.addtransition(pos[fromstate], pos[state], tostates[state])
            rebuild.setstartstate(pos[self.startstate])
            for s in self.finalstates:
                rebuild.addfinalstates(pos[s])
            return rebuild
    
        def getDotFile(self):
            dotFile = "digraph DFA {\nrankdir=LR\n"
            if len(self.states) != 0:
                dotFile += "root=s1\nstart [shape=point]\nstart->s%d\n" % self.startstate
                for state in self.states:
                    if state in self.finalstates:
                        dotFile += "s%d [shape=doublecircle]\n" % state
                    else:
                        dotFile += "s%d [shape=circle]\n" % state
                for fromstate, tostates in self.transitions.items():
                    for state in tostates:
                        for char in tostates[state]:
                            dotFile += 's%d->s%d [label="%s"]\n' % (fromstate, state, char)
            dotFile += "}"
            return dotFile
    
    class BuildAutomata:
        """class for building e-nfa basic structures"""
    
        @staticmethod
        def basicstruct(inp):
            state1 = 1
            state2 = 2
            basic = Automata()
            basic.setstartstate(state1)
            basic.addfinalstates(state2)
            basic.addtransition(1, 2, inp)
            return basic
    
        @staticmethod
        def plusstruct(a, b):
            [a, m1] = a.newBuildFromNumber(2)
            [b, m2] = b.newBuildFromNumber(m1)
            state1 = 1
            state2 = m2
            plus = Automata()
            plus.setstartstate(state1)
            plus.addfinalstates(state2)
            plus.addtransition(plus.startstate, a.startstate, Automata.epsilon())
            plus.addtransition(plus.startstate, b.startstate, Automata.epsilon())
            plus.addtransition(a.finalstates[0], plus.finalstates[0], Automata.epsilon())
            plus.addtransition(b.finalstates[0], plus.finalstates[0], Automata.epsilon())
            plus.addtransition_dict(a.transitions)
            plus.addtransition_dict(b.transitions)
            return plus
    
        @staticmethod
        def dotstruct(a, b):
            [a, m1] = a.newBuildFromNumber(1)
            [b, m2] = b.newBuildFromNumber(m1)
            state1 = 1
            state2 = m2-1
            dot = Automata()
            dot.setstartstate(state1)
            dot.addfinalstates(state2)
            dot.addtransition(a.finalstates[0], b.startstate, Automata.epsilon())
            dot.addtransition_dict(a.transitions)
            dot.addtransition_dict(b.transitions)
            return dot
    
        @staticmethod
        def starstruct(a):
            [a, m1] = a.newBuildFromNumber(2)
            state1 = 1
            state2 = m1
            star = Automata()
            star.setstartstate(state1)
            star.addfinalstates(state2)
            star.addtransition(star.startstate, a.startstate, Automata.epsilon())
            star.addtransition(star.startstate, star.finalstates[0], Automata.epsilon())
            star.addtransition(a.finalstates[0], star.finalstates[0], Automata.epsilon())
            star.addtransition(a.finalstates[0], a.startstate, Automata.epsilon())
            star.addtransition_dict(a.transitions)
            return star
    
    
    class DFAfromNFA:
        """class for building dfa from e-nfa and minimise it"""
    
        def __init__(self, nfa):
            self.buildDFA(nfa)
            self.minimise()
    
        def getDFA(self):
            return self.dfa
        
        def getAllStates(self):
            return self.allstates
        
        def getTransitions(self):
            return self.trstates
    
        def getMinimisedDFA(self):
            return self.minDFA
    
        def displayDFA(self):
            self.dfa.display()
    
        def displayMinimisedDFA(self):
            self.minDFA.display()
    
        def buildDFA(self, nfa):
            allstates = dict()
            eclose = dict()
            count = 1
            state1 = nfa.getEClose(nfa.startstate)
            eclose[nfa.startstate] = state1
            dfa = Automata(nfa.language)
            dfa.setstartstate(count)
            states = [[state1, count]]
            allstates[count] = state1
            count +=  1
            while len(states) != 0:
                [state, fromindex] = states.pop()
                # Next line was originally "for char in dfa.language:"
                # But returned "char" in random order, since dfa.language is a set,
                # so dfa.finalstates result was not consistent
                for char in sorted(dfa.language):
                    trstates = nfa.gettransitions(state, char)
                    for s in list(trstates)[:]:
                        if s not in eclose:
                            eclose[s] = nfa.getEClose(s)
                        trstates = trstates.union(eclose[s])
                    if len(trstates) != 0:
                        if trstates not in allstates.values():
                            states.append([trstates, count])
                            allstates[count] = trstates
                            toindex = count
                            count +=  1
                        else:
                            toindex = [k for k, v in allstates.items() if v  ==  trstates][0]
                        dfa.addtransition(fromindex, toindex, char)
       
            for value, state in allstates.items():
                if nfa.finalstates[0] in state:
                    dfa.addfinalstates(value)
     
            self.dfa = dfa
            self.allstates = allstates
            self.trstates = trstates 
    
        def acceptsString(self, string):
            currentstate = self.dfa.startstate
            for ch in string:
                if ch==":e:":
                    continue
                st = list(self.dfa.gettransitions(currentstate, ch))
                if len(st) == 0:
                    return False
                currentstate = st[0]
            if currentstate in self.dfa.finalstates:
                return True
            return False
    
        def minimise(self):
            states = list(self.dfa.states)
            n = len(states)
            unchecked = dict()
            count = 1
            distinguished = []
            equivalent = dict(zip(range(len(states)), [{s} for s in states]))
            pos = dict(zip(states,range(len(states))))
            for i in range(n-1):
                for j in range(i+1, n):
                    if not ([states[i], states[j]] in distinguished or [states[j], states[i]] in distinguished):
                        eq = 1
                        toappend = []
                        # Added "sorted" next line
                        for char in sorted(self.dfa.language):
                            s1 = self.dfa.gettransitions(states[i], char)
                            s2 = self.dfa.gettransitions(states[j], char)
                            if len(s1) != len(s2):
                                eq = 0
                                break
                            if len(s1) > 1:
                                raise BaseException("Multiple transitions detected in DFA")
                            elif len(s1) == 0:
                                continue
                            s1 = s1.pop()
                            s2 = s2.pop()
                            if s1 != s2:
                                if [s1, s2] in distinguished or [s2, s1] in distinguished:
                                    eq = 0
                                    break
                                else:
                                    toappend.append([s1, s2, char])
                                    eq = -1
                        if eq == 0:
                            distinguished.append([states[i], states[j]])
                        elif eq == -1:
                            s = [states[i], states[j]]
                            s.extend(toappend)
                            unchecked[count] = s
                            count += 1
                        else:
                            p1 = pos[states[i]]
                            p2 = pos[states[j]]
                            if p1 != p2:
                                st = equivalent.pop(p2)
                                for s in st:
                                    pos[s] = p1
                                equivalent[p1] = equivalent[p1].union(st)
            newFound = True
            while newFound and len(unchecked) > 0:
                newFound = False
                toremove = set()
                for p, pair in list(unchecked.items()):  #.items():
                    for tr in pair[2:]:
                        if [tr[0], tr[1]] in distinguished or [tr[1], tr[0]] in distinguished:
                            unchecked.pop(p)
                            distinguished.append([pair[0], pair[1]])
                            newFound = True
                            break
            for pair in unchecked.values():
                p1 = pos[pair[0]]
                p2 = pos[pair[1]]
                if p1 != p2:
                    st = equivalent.pop(p2)
                    for s in st:
                        pos[s] = p1
                    equivalent[p1] = equivalent[p1].union(st)
            if len(equivalent) == len(states):
                self.minDFA = self.dfa
            else:
                self.minDFA = self.dfa.newBuildFromEquivalentStates(equivalent, pos)
    
    class NFAfromRegex:
        """class for building e-nfa from regular expressions"""
    
        def __init__(self, regex):
            self.star = '*'
            # Next line was originally "self.plus = '+'
            # Changed to '|' to fit aplication of regex for program
            self.plus = '|'
            self.dot = '.'
            self.openingBracket = '('
            self.closingBracket = ')'
            self.operators = [self.plus, self.dot]
            self.regex = regex
            self.alphabet = [chr(i) for i in range(65,91)]
            self.alphabet.extend([chr(i) for i in range(97,123)])
            self.alphabet.extend([chr(i) for i in range(48,58)])
            self.buildNFA()
    
        def getNFA(self):
            return self.nfa
    
        def displayNFA(self):
            self.nfa.display()
    
        def buildNFA(self):
            language = set()
            self.stack = []
            self.automata = []
            previous = "::e::"
            for char in self.regex:
                if char in self.alphabet:
                    language.add(char)
                    if previous != self.dot and (previous in self.alphabet or previous in [self.closingBracket,self.star]):
                        self.addOperatorToStack(self.dot)
                    self.automata.append(BuildAutomata.basicstruct(char))
                elif char  ==  self.openingBracket:
                    if previous != self.dot and (previous in self.alphabet or previous in [self.closingBracket,self.star]):
                        self.addOperatorToStack(self.dot)
                    self.stack.append(char)
                elif char  ==  self.closingBracket:
                    if previous in self.operators:
                        raise BaseException("Error processing '%s' after '%s'" % (char, previous))
                    while(1):
                        if len(self.stack) == 0:
                            raise BaseException("Error processing '%s'. Empty stack" % char)
                        o = self.stack.pop()
                        if o == self.openingBracket:
                            break
                        elif o in self.operators:
                            self.processOperator(o)
                elif char == self.star:
                    if previous in self.operators or previous  == self.openingBracket or previous == self.star:
                        raise BaseException("Error processing '%s' after '%s'" % (char, previous))
                    self.processOperator(char)
                elif char in self.operators:
                    if previous in self.operators or previous  == self.openingBracket:
                        raise BaseException("Error processing '%s' after '%s'" % (char, previous))
                    else:
                        self.addOperatorToStack(char)
                else:
                    raise BaseException("Symbol '%s' is not allowed" % char)
                previous = char
            while len(self.stack) != 0:
                op = self.stack.pop()
                self.processOperator(op)
            if len(self.automata) > 1:
                print (self.automata)
                raise BaseException("Regex could not be parsed successfully")
            self.nfa = self.automata.pop()
            self.nfa.language = language
    
        def addOperatorToStack(self, char):
            while(1):
                if len(self.stack) == 0:
                    break
                top = self.stack[len(self.stack)-1]
                if top == self.openingBracket:
                    break
                if top == char or top == self.dot:
                    op = self.stack.pop()
                    self.processOperator(op)
                else:
                    break
            self.stack.append(char)
    
        def processOperator(self, operator):
            if len(self.automata) == 0:
                raise BaseException("Error processing operator '%s'. Stack is empty" % operator)
            if operator == self.star:
                a = self.automata.pop()
                self.automata.append(BuildAutomata.starstruct(a))
            elif operator in self.operators:
                if len(self.automata) < 2:
                    raise BaseException("Error processing operator '%s'. Inadequate operands" % operator)
                a = self.automata.pop()
                b = self.automata.pop()
                if operator == self.plus:
                    self.automata.append(BuildAutomata.plusstruct(b,a))
                elif operator == self.dot:
                    self.automata.append(BuildAutomata.dotstruct(b,a))
    
    """def drawGraph(automata, file = ""):
        From https://github.com/max99x/automata-editor/blob/master/util.py
        f = popen(r"dot -Tpng -o graph%s.png" % file, 'w')
        try:
            f.write(automata.getDotFile())
        except:
            raise BaseException("Error creating graph")
        finally:
            f.close()"""
    
    def isInstalled(program):
        """From http://stackoverflow.com/questions/377017/test-if-executable-exists-in-python"""
        import os
        def is_exe(fpath):
            return os.path.isfile(fpath) and os.access(fpath, os.X_OK)
        fpath, fname = os.path.split(program)
        if fpath:
            if is_exe(program) or is_exe(program+".exe"):
                return True
        else:
            for path in os.environ["PATH"].split(os.pathsep):
                exe_file = os.path.join(path, program)
                if is_exe(exe_file) or is_exe(exe_file+".exe"):
                    return True
        return False
    
    class Matrix:
        
        def __init__(self, DFA, allstates, transitions, length):
            self.length = length
            self.DFA = DFA
            self.allstates = allstates
            dim = 0
     
            for value, _state in allstates.items():
                if value != 0:
                    dim += 1
            dim += 1
            self.dim = dim
            self.matrix= self.createMatrix( self.DFA, self.allstates, transitions, self.dim)
            
        def getDim(self):
            return self.dim
            
        def createMatrix(self, DFA, allstates, transitions, dim):
     
            matrix = [[0]*(dim) for _ in range(dim)]
            for from_state, to_state in transitions.items():
                for to_state, _char in to_state.items():
                    matrix[from_state-1][to_state-1] = 1 
           
            return matrix   
            
        def count_paths(self, DFA, dim, length):
            modulo = 1000000007
            result = Matrix.pow2(self, length, self.matrix, dim, modulo)
            count = 0
                  
            for i in range(dim):
                for j in range(dim):
                    if i == 0:
                        for k in DFA.finalstates:
                            k -= 1
                            if j == k:
                                count += result[i][j]
                                
            return count % modulo
    
        def copy(self, dim):
            my_matrix = [[0]*(dim) for _ in range(dim)]
            for i in range(dim):
                for j in range(dim):
                    my_matrix[i][j] = self.matrix[i][j]
                    
            return my_matrix
    
        def printMatrix(self, matrix, dim):
            for i in range(dim):
                print(matrix[i])
    
        def pow2(self, power, matrix, dim, mod=None):
            
            result1 = [[0]*(dim) for _ in range(dim)]
            for i in range(dim):
                result1[i][i] = 1
            while power > 0:
                if power & 1:
                    result1 = Matrix.mat_square_mult(self, result1, matrix, dim, mod);
                power >>= 1;
                if power > 0:
                    matrix = Matrix.mat_square_mult(self, matrix, matrix, dim, mod);
            matrix = result1 
                   
            return matrix
    
        def mat_square_mult(self, matrix, other, dim, mod=None):
            result = [[0]*(dim) for _ in range(dim)]
            for i in range(dim):
                for j in range(dim):
                    index = 0
                    for k in range(dim):
                        index += (matrix[i][k] * other[k][j]) % mod
    
                        result[i][j] = index
            return result
    
    def count_strings(regex, length):
    
        nfaObj = NFAfromRegex(regex)
        nfa = nfaObj.getNFA()
        dfaObj = DFAfromNFA(nfa)
        dfa = dfaObj.getDFA()
        #minDFA = dfaObj.getMinimisedDFA()
        #print ("\nNFA: ")
        #nfaObj.displayNFA()
        #print ("\nDFA: ")
        #dfaObj.displayDFA()
        #print ("\nMinimised DFA: ")
        #dfaObj.displayMinimisedDFA()
        #result = None
        transitions = dfa.transitions
        allstates = dfaObj.getAllStates()
        resultObj = Matrix(dfa, allstates, transitions, length) 
        dim = resultObj.getDim()
        result = Matrix.count_paths(resultObj, dfa, dim, length)
        
        #The result should be 198110437 for the test input
    
        
        print (result)
        
        
        
    def main():
        
        cases = int(input().strip())
        for _i in range(cases):
            in_line = input().strip().split()
            regex = in_line[0]
            length = int(in_line[1])
            count_strings(regex, length)
        
    if __name__  ==  '__main__':
        main()

    external by EDFward modified Aug 30, 2015  1778847  196  4  1

    solved 'Breadth First Search: Shortest Reach' on hackerrank https://www.hackerrank.com/challenges/bfsshortreach

    solved 'Breadth First Search: Shortest Reach' on hackerrank https://www.hackerrank.com/challenges/bfsshortreach: bellman_ford.py
    from collections import namedtuple
    
    
    # A reasonable large number to represent infinity.
    INF = (1 << 31)
    UNIT_LENGTH = 6
    # Struct for edges.
    Edge = namedtuple('Edge', ['src', 'dest'])
    
    def calculate_shortest_distances(node_num, edges, src):
      """Bellman-Ford Algorithm.
         node_num: Number of nodes.
         edges: A list of edges.
         src: Source node."""
    
      # Index starts from 1.
      dist = [INF] * (node_num + 1)
      dist[src] = 0
      for _ in range(node_num):
        # A flag indicating whether update happens.
        updated = False
        for edge in edges:
          edge_src, edge_dest = edge
          if dist[edge_src] + UNIT_LENGTH < dist[edge_dest]:
            updated = True
            dist[edge_dest] = dist[edge_src] + UNIT_LENGTH
        
        if not updated:
          # Early exit since distances are now stable.
          break
      
      # Perform certain transformations on the output.
      del dist[src]
      del dist[0]
      return [(-1 if i == INF else i) for i in dist]
    
    if __name__ == '__main__':
      test_case_num = int(raw_input())
      for _ in range(test_case_num):
        edges = []
        node_num, edge_num = map(int, raw_input().split())
        for _ in range(edge_num):
          edge_src, edge_dest = map(int, raw_input().split())
          # Note this is an undirected graph.
          edges.append(Edge(edge_src, edge_dest))
          edges.append(Edge(edge_dest, edge_src))
        src = int(raw_input())
        dist = calculate_shortest_distances(node_num, edges, src)
        print ' '.join(map(str, dist))
    
    

    external by Vishnu Ashok modified Mar 18, 2015  525  0  3  0

    HackerRank Handshake

    HackerRank Handshake: Hackerrank-Handshake.py
    people = []
    
    for _ in range(int(raw_input())):
        people.append(int(raw_input()))
        
    for n in people:
        print ((n*(n-1))/2)    
    
    

    external by He Junjia modified Jan 18, 2015  17581  107  4  0

    solved 'Almost Sorted' on hackerrank https://www.hackerrank.com/challenges/almost-sorted

    solved 'Almost Sorted' on hackerrank https://www.hackerrank.com/challenges/almost-sorted: almost_sorted.cpp
    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    
    int main() {
        int n, nums[100000];
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> nums[i];
        
        // check anomolies, return early if there
        // are more than 2 non-contiguous anomolies
        vector<int> anomolies;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i-1]) {
                if (anomolies.size() < 2 ||
                    i-1-anomolies.back() == 1) {
                    anomolies.push_back(i-1);
                }
                else {
                    cout << "no" << endl;
                    return 0;
                }
            }
        }
        
        if (anomolies.empty()) {
            cout << "yes" << endl;
            return 0;
        }
        
        //anomolies should conform to a specific pattern
        int sz    = anomolies.size(),
            left  = anomolies[0], 
            right = anomolies.back() + 1;
        const char* keyword = (sz <= 2) ? "swap" : "reverse";
    
        if ((left == 0 || nums[right] >= nums[left-1]) &&
            (right == n - 1 || nums[left] <= nums[right+1]))
            printf("yes\n%s %d %d\n", keyword, left + 1, right + 1);
        else
            puts("no\n");
        return 0;
    }
    
    
    

    external by 1and1get2 modified Jul 4, 2014  91681  0  4  0

    hackerrank.md

    hackerrank.md: hackerrank.md
    hackerrank
    =============
    
    My own practice following:
    https://www.hackerrank.com/categories/algorithms/warmup
    
    started from Jun 14 2014, finished at, well, I don't know, just started.
    
    Basically, this is what I'll be doing when I got the pulse of playing dota. 
    Dota will always be the game of my life, best game ever, but I need a little break from it. 
    what changed my mind? 
    
    WHO CARES!
    
    
    | project name					| rate	|	link	|	others	|	
    | ----------------------------	|:-----:|:-------------------------------------------------------------	|:-----------------:|
    | [20140614-angry-children]		|	3	|	https://www.hackerrank.com/challenges/angry-children		|					|
    | [20140614-is-fibo]			|	2	|	https://www.hackerrank.com/challenges/is-fibo				|					|
    | [20140614-candies]			|	4	|	https://www.hackerrank.com/challenges/candies				|					|
    | [20140627-permutation-game]	|	4	|	https://www.hackerrank.com/challenges/permutation-game		|	not finished	|
    | [20140704-ncr-table]			|		|	https://www.hackerrank.com/challenges/ncr-table				|					|
    | [20140705-k-candy-store]		|		|	https://www.hackerrank.com/challenges/k-candy-store				|					|
    | []			|		|	https://www.hackerrank.com/challenges/ncr-table				|					|
    | []			|		|	https://www.hackerrank.com/challenges/ncr-table				|					|
    | []			|		|	https://www.hackerrank.com/challenges/ncr-table				|					|
    | []			|		|	https://www.hackerrank.com/challenges/ncr-table				|					|
    | []			|		|	https://www.hackerrank.com/challenges/ncr-table				|					|
    
    ```
    ##	about rate:
    *###	1	those question is so easy that I wish I haven't waste my time on this rather to play some game
    *###	2	well, it was okay question, might worth doing, might tought me something 
    *###	3	some good questions, might needed some thought but figured out 
    *###	4	hard questions, might solved after a big headache or not even solved but not too hard after reading the solution
    *###	5	really hard ones, couldn't figure out then and might even still confused even after reading the answer 
    ```
    
    

    external by Yong Wen Chua modified Feb 16, 2015  18796  167  5  0

    HackerRank Super Stack Solution

    HackerRank Super Stack Solution: SuperStack.cs
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    
    namespace Solution
    {
        class Solution
        {
            static void Main(string[] args)
            {
                var noCommands = Convert.ToInt32(System.Console.ReadLine());
    
                var stack = new LinkedList<int>();
                for (var i = 0; i < noCommands; ++i)
                {
                    var command = Console.ReadLine();
                    var split = command.Split(' ');
    
                    if (split[0] == "push")
                    {
                        var number = Convert.ToInt32(split[1]);
                        stack.AddFirst(number);
                    }
                    else if (split[0] == "pop" && stack.Count > 0)
                    {
                        stack.RemoveFirst();
                    }
                    else if (split[0] == "inc")
                    {
                        var count = Convert.ToInt32(split[1]);
                        var increment = Convert.ToInt32(split[2]);
                        count = Math.Min(stack.Count, count);
    
                        var node = stack.Last;
                        for (var j = 0; j < count; ++j)
                        {
                            node.Value += increment;
                            node = node.Previous;
                        }
                     }
    
                    PrintTop(stack);
                }
            }
    
            static void PrintTop(LinkedList<int> stack)
            {
                if (stack.Count == 0)
                {
                    System.Console.WriteLine("EMPTY");
                }
                else
                {
                    System.Console.WriteLine("{0}", stack.First.Value);
                }
            }
        }
    }
    
    

    external by p53ud0k0d3 modified Mar 19, 2015  343  2  3  0

    HackerRank The Love-Letter Mystery

    HackerRank The Love-Letter Mystery: the-love-letter-mystery.py
    words = []
    
    def evenPal(word):
        steps = 0
        l = len(word)
        w1 = word[:l/2]
        w2 = word[l/2:]
        w2 = w2[::-1]
        for i in xrange(0, len(w1)):
            steps += abs(ord(w1[i]) - ord(w2[i]))
        print steps
        
        
        
    def oddPal(word): #Different approach
        steps = 0
        l = len(word)
        mid = l/2
        j = -1
        for i in xrange(0, mid):
            steps += abs(ord(word[i]) - ord(word[j]))
            j -= 1
        print steps
            
            
    
    for _ in xrange(int(raw_input())):
        words.append(raw_input().strip())
        
    for word in words:
        if word == word[::-1]:
            print 0
        elif len(word) % 2 == 0:
            evenPal(word)
        else :
            oddPal(word)
    
    

    external by NeoZhangTCL modified Mar 3, 2016  834  4  3  0

    https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene/submissions/code/5410841

    https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene/submissions/code/5410841: Bear and Steady Gene
    import java.io.*;
    import java.util.*;
    
    public class Solution {
    
        public static void main(String[] args) throws FileNotFoundException {
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        	//uncomment it when doing in Eclipse
        	//System.setIn(new FileInputStream(args[0]));
        	Scanner in = new Scanner(System.in);
        	int length = in.nextInt();
        	int maxEach = length/4;
        	in.nextLine();
        	String gene = in.nextLine();
        	
        	int counterG = 0, counterA=0, counterC=0, counterT = 0;    	
        	Stack<Character> left = new Stack<Character>();
        	Stack<Character> right = new Stack<Character>();
        	List<Integer> lengths = new ArrayList<Integer>();
        	
        	int i;
        	for (i=0; i<length; i++){
        		if (gene.charAt(i)=='G'){
        			counterG++;
        			left.add('G');
        		}
        		if (gene.charAt(i)=='A'){
        			counterA++;
        			left.add('A');
        		}
        		if (gene.charAt(i)=='C'){
        			counterC++;
        			left.add('C');
        		}
        		if (gene.charAt(i)=='T'){
        			counterT++;
        			left.add('T');
        		}
        		if (counterG > maxEach|| counterA > maxEach|| counterC > maxEach|| counterT > maxEach){
        			lengths.add(left.size()-1);
        			char removed = left.pop();
            		if (removed=='G'){
            			counterG--;
            		}
            		if (removed=='A'){
            			counterA--;
            		}
            		if (removed=='C'){
            			counterC--;
            		}
            		if (removed=='T'){
            			counterT--;
            		}    
        			break;
        		}
        	}
        	
        	int j=length-1;
        	while(j>0 && !left.isEmpty()){
        		if (gene.charAt(j)=='G'){
        			counterG++;
        			right.add('G');
        		}
        		if (gene.charAt(j)=='A'){
        			counterA++;
        			right.add('A');
        		}
        		if (gene.charAt(j)=='C'){
        			counterC++;
        			right.add('C');
        		}
        		if (gene.charAt(j)=='T'){
        			counterT++;
        			right.add('T');
        		}
        		while((counterG > maxEach|| counterA > maxEach|| counterC > maxEach|| counterT > maxEach)&&!left.isEmpty()){
        			int len = left.size() + right.size() - 1;
        			lengths.add(len);
        			char removed = left.pop();
            		if (removed=='G'){
            			counterG--;
            		}
            		if (removed=='A'){
            			counterA--;
            		}
            		if (removed=='C'){
            			counterC--;
            		}
            		if (removed=='T'){
            			counterT--;
            		}    		
        		}
        		j--;
        	}
        	int result = length - Collections.max(lengths);
        	System.out.println(result);
        	
        }
    }
    
    
    

    external by cc2011 modified Mar 26, 2015  3878  73  5  0

    hackerrank [Greedy] https://www.hackerrank.com/challenges/largest-permutation

    hackerrank [Greedy] https://www.hackerrank.com/challenges/largest-permutation: gistfile1.txt
    //https://www.hackerrank.com/challenges/largest-permutation
    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
    
        public static void main(String[] args) {
            try {
                Scanner s = new Scanner(System.in);
                    String[] inputArr = s.nextLine().split(" ");
                    int n = Integer.parseInt(inputArr[0]) ;
                    int k = Integer.parseInt(inputArr[1]);
                    inputArr = s.nextLine().split(" ");
                    int[] input = new int[n];
                    for(int j=0; j < n;j++) {
                            input[j] = Integer.parseInt(inputArr[j]);
                    }
    
                    for(int j=0;j < n; j++) {
                            int swapIndex = existLargest(input[j],j,input);
                            if(swapIndex != j) {
                                    if(k!=0){
                                            int temp = input[j];
                                            input[j] = input[swapIndex];
                                            input[swapIndex]= temp;
                                            k--;
                                    } else {
                                            break;
                                    }
                            }
                    }
                    for(int j=0;j < n;j++) {
                            if(j >0)
                                    System.out.print(" ");
                            System.out.print(input[j]);
                    }
                    System.out.println();
            } catch(Exception e){
                e.printStackTrace();
            }
        }
        public static int existLargest(int curr,int index,int[] arr) {
            int output = curr;
            int outputIndex = index;
            for(int i=index+1; i < arr.length;i++){
                    if(output < arr[i]){
                            output = arr[i];
                            outputIndex = i;
                    }
            }
            return outputIndex;
        }
    }    
    
    

    external by cc2011 modified Mar 21, 2015  80  0  2  0

    hackerrank euler 69 : https://www.hackerrank.com/contests/projecteuler/challenges/euler069

    hackerrank euler 69 : https://www.hackerrank.com/contests/projecteuler/challenges/euler069: gistfile1.txt
    //hackerrank euler 69 : https://www.hackerrank.com/contests/projecteuler/challenges/euler069
     import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    class node {
        int max;
        int n;  
        double phiratio;
        public node(int max,int n,double phiratio){
          this.max = max;
          this.n = n;
          this.phiratio = phiratio;
        }
    }
    public class Solution {
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Map<Integer,node> map = new HashMap<Integer,node>();
            double max = 0;
            int ans = 0;
            int t = in.nextInt();
            for(int i=0; i < t; i++) {
                int total = in.nextInt();
                if( map.containsKey(total) ){                
                  node n = map.get(total);
                  ans = n.max;
                }          
                else{
                int start = map.size() > 2 ? map.size():2;
                  
                  for(int j=start ; j <= total ;j++) {
                       int n = j;
                       int temp = 2;
                       int count = n-1;
                       while( temp < n ){
                           if( isPrime(temp) && n%temp == 0 ){
                             //our logic is if temp is prime and is not prime to n 
                               count -= (n/temp)-1;
                           }
                           temp++;
                       }
                       double d= n/(double)count;
                       if( max < d ){
                          ans = n; 
                          max = d;
                       }  
                      node newN = new node(ans, j , d);          
                      map.put( j ,newN );
                  } 
                }
                System.out.println(ans);
           }
          
        }
        public static boolean isPrime( int n ){
        int temp = 2;
        while( temp*temp < n ){
          //sqrt of (n) is sufficient to find prime
            if( n%temp == 0 )
                return false;
            temp++;
        }
        return true;
    }
    
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    //output of n=8 : 1,3,5,7
    /*
    lets take n = 8. 
    temp = 2 , count = 8 
    8%2 == 0 , count = 8- (8/2-1) = 5
    
    temp = 3 count = 5
    8%3 != 0
    
    temp = 4 count = 5
    skip
    
    temp =5 count =4
    8%5 !=0
    
    temp = 6 count =5
    skip
    
    temp = 7 , skip
    
    
    ----------------------
    
    10    1,3,7,9 
    //for 10 
    10/2 = 5
    so 5-1 =4 are total multiples of 2
    
    for 2 :
    so all multiples of 2 that are less than 10 we'll substract from actual count
    so count = 10-4 
    
    for 3 :
    
    10%3 != 0
    skip
    
    for 4: 
    skip since we already take that into account.
    */
    
    
    
    
    
    • Public Snippets
    • Channels Snippets