working on it ...

Filters

Explore Public Snippets

Sort by

Found 814 snippets matching: hackerrank

    public by te777 modified Sep 24, 2016  248  0  4  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 He Junjia modified Jan 18, 2015  1674  214  3  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 EDFward modified Aug 30, 2015  1727  128  3  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 cc2011 modified Mar 26, 2015  508  47  4  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 He Junjia modified Aug 29, 2015  294  5  3  0

    solved 'Bricks Game' on hackerrank https://www.hackerrank.com/challenges/play-game

    solved 'Bricks Game' on hackerrank https://www.hackerrank.com/challenges/play-game: play_bricks_dp.py
    def max_score(bricks):
        """bricks: A list of bricks."""
        sz = len(bricks)
        # DP algorithm. See the editorial.
        # https://www.hackerrank.com/challenges/play-game/editorial
        max_score_from = [0] * sz
        max_score_from[-1] = bricks[-1]
        max_score_from[-2] = max_score_from[-1] + bricks[-2]
        max_score_from[-3] = max_score_from[-2] + bricks[-3]
    
        backward_sum = max_score_from[:]
        for i in range(sz - 4, -1, -1):
            # Calculate scores with different actions: take 1, 2 or 3 bricks.
            score_take_one = bricks[i] + \
                backward_sum[i + 1] - max_score_from[i + 1]
            score_take_two = bricks[i] + bricks[i + 1] + \
                backward_sum[i + 2] - max_score_from[i + 2]
            score_take_three = bricks[i] + bricks[i + 1] + bricks[i + 2] + \
                backward_sum[i + 3] - max_score_from[i + 3]
    
            max_score_from[i] = max(
                score_take_one, score_take_two, score_take_three)
            backward_sum[i] = backward_sum[i + 1] + bricks[i]
    
        return max_score_from[0]
    
    
    test_case_num = int(raw_input())
    for _ in range(test_case_num):
        raw_input()
        bricks = map(int, raw_input().split())
        print max_score(bricks)
    
    
    

    external by smithzvk modified Jan 6, 2014  511  0  3  0

    HackerRank submission code for Common Lisp. This will grab source from quicklisp, create a monolithic source file that is suitable for upload to HackerRank. Also a bunch of comments and poorly edited thoughts.

    HackerRank submission code for Common Lisp. This will grab source from quicklisp, create a monolithic source file that is suitable for upload to HackerRank. Also a bunch of comments and poorly edited thoughts.: hacker-rank-submission.lisp
    ;; This file contains tools that can be used to package solutions to submit to
    ;; the hacker-rank even if they use programs from Quicklisp.  This is done by
    ;; using Quicklisp to grab the source (to be done), then using ASDF to track
    ;; down dependencies, then grabbing the entire source file and inserting it into
    ;; a single file for submission.  Your code is placed at the end of the file and
    ;; is read and evaluated from a string in a situation where the desired
    ;; libraries are instantiated.
    
    ;; This can be used with any ASDF reachable library (or this is at least the
    ;; goal), so you can use your own utility libraries as well so long as you don't
    ;; mind uploading them to a website.
    
    ;; To use it, merely place any systems that you would like loaded in a
    ;; ql:quickload form.  This is really sloppily done.  These forms are found by
    ;; searching your source for quickload forms with nothing but whitespace between
    ;; the form and the beginning of the line.  These libraries are then hunted down
    ;; and inserted at the beginning of the file irregardless of where you had the
    ;; quickload form.  Then use the function process-for-submission which will
    ;; produce a new file with the string "-submission" appended to the
    ;; pathname-name of the file.  This can be compiled using sbcl --noinform --eval
    ;; '(compile-file #p"<<filename>>")' --eval '(exit)' which is, I believe how the
    ;; HackerRank people do it, and it can be run via sbcl --noinform --load
    ;; '<<filename.fasl>>' which is, again, I believe how they do it on the server.
    
    ;; I know this is not very robust or clean, but it works for most purposes.  If
    ;; you know a better way of doing this, let me know.
    
    (ql:quickload '(:cl-fad
                    :cl-plumbing
                    :naive-reader))
    
    (defpackage :hacker-rank-submission
      (:use :cl :iterate)
      (:export
       #:create-submission-file))
    
    (in-package :hacker-rank-submission)
    
    
    ;; (defvar *files* nil)
    
    ;; (defclass gather-op (asdf:operation)
    ;;   ((files :initform nil :accessor files-of)))
    
    ;; (defmethod asdf:perform ((o gather-op) (c asdf:source-file))
    ;;   (map () (lambda (file) (push file *files*))
    ;;        #-(or ecl mkcl)
    ;;        (asdf:input-files o c)
    ;;        #+(or ecl mkcl)
    ;;        (loop :for i :in (asdf:input-files o c)
    ;; 	     :unless (string= (pathname-type i) "fas")
    ;; 	     :collect (compile-file-pathname (asdf::lispize-pathname i)))))
    
    ;; (defmethod asdf:perform ((operation gather-op) (c asdf:static-file))
    ;;   (declare (ignorable operation c))
    ;;   nil)
    
    ;; (defmethod asdf:operation-done-p ((operation gather-op) (c asdf:static-file))
    ;;   (declare (ignorable operation c))
    ;;   nil)
    
    ;; (defmethod asdf:output-files ((operation gather-op) (c asdf:component))
    ;;   (declare (ignorable operation c))
    ;;   nil)
    
    ;; (defmethod asdf:component-depends-on ((o gather-op) (c asdf:component))
    ;;   (declare (ignorable o))
    ;;   (list (cons 'gather-op
    ;;               (rest (first (asdf:component-depends-on
    ;;                             'asdf:compile-op c))))))
    
    ;; We then go through the files and process each apparent toplevel form by
    ;; wrapping it in a <eval-when> form.  By apparent toplevel form I mean the
    ;; forms that you get as you read a file.  This is actually a semantically
    ;; important unit in that a reader macro defined in one apparent toplevel form
    ;; can effect the later apparent toplevel forms, but not necessarily all of the
    ;; later toplevel forms as some of those may have been read at the same time as
    ;; the form with the reader macro definition.
    
    (defun wrap-form (form)
      (format nil "~%(eval-when (:compile-toplevel :load-toplevel :execute)~%~A~%)"
              form))
    
    (defun wrap-toplevel-forms (file)
      (with-output-to-string (out)
        (with-open-file (in file)
          (iter (for string = (handler-case
                                  (naive-reader:read-form-string in)
                                (end-of-file () nil)))
            (while (and string (not (eql string ""))))
            (princ (wrap-form string) out)))))
    
    ;; With asdf:monolithic-concatenate-source-op
    (defun gather-package-dependencies
        (component &key (output-file (make-pathname
                                      :name (concatenate
                                             'string
                                             (string-downcase (symbol-name component))
                                             "-processed")
                                      :type "lisp"
                                      :defaults *default-pathname-defaults*))
                        (if-exists :supersede))
      (asdf:oos 'asdf:monolithic-concatenate-source-op component :force t)
      (let* ((file (print (asdf:output-file 'asdf:monolithic-concatenate-source-op component)))
             (output (wrap-toplevel-forms file)))
        (if (eql output-file :string)
            output
            (with-open-file (out output-file :direction :output :if-exists if-exists)
              (princ output out)
              nil))))
    
    ;; This builds the system as necessary as a temporary file, then builds the
    ;; equivalent source file.
    (defun concat-source-files (file output-file)
      (let* ((dependencies (with-open-file (in file)
                             (let ((loads (read in)))
                               (cond ((or (atom loads)
                                          (not (eql 'ql:quickload)
                                               (first loads)))
                                      ;; No dependencies
                                      nil)
                                     ((atom (second loads))
                                      ;; only one dependency
                                      (list (second loads)))
                                     (t
                                      ;; Many dependencies
                                      (second (second loads)))))))
             (cl-fad:*default-template* "TEMPORARY-FILES:%")
             (system-name (concatenate 'string (format nil "~A" (random 10000))
                                       "-submission"))
             (system
               (intern (string-upcase system-name) :keyword))
             (asd-file
               (cl-fad:with-output-to-temporary-file
                   (out :generate-random-string
                        (lambda () (concatenate 'string system-name ".asd")))
                 (print `(asdf:defsystem ,system :depends-on ,dependencies) out))))
        (let ((asdf:*central-registry*
                (cons (make-pathname :directory (pathname-directory asd-file))
                      asdf:*central-registry*)))
          (with-open-file (in file)
            (read in)
            (let ((concat (make-concatenated-stream
                           (make-string-input-stream
                            (gather-package-dependencies
                             system
                             :output-file :string))
                           in)))
              (with-open-file (out output-file :direction :output
                                               :if-exists :supersede)
                (cl-plumbing:connect-streams concat out
                                             :background nil :read-fn 'read-line)))))))
    
    (defun create-submission-file (file &key output)
      (concat-source-files file output))
    
    (defun submit-solution (file challenge)
      (declare (ignore file challenge))
      (lambda () (print 'test))
      (error
       "This is not implemented yet and won't be until there is some kind of public API."))
    
    ;; The other way.
    
    ;; By HackerRank rules, you can write files to the local directory.  This means
    ;; that we could simply include the code to write the files out and compile them
    ;; along with the code to load them and compile your code.  This is probably the
    ;; cleanest way to work within the constraints (in fact if I had known that this
    ;; was a weak point on the constraints, I would have done this to begin with).
    
    ;; Actually this hinges on the ability to write at compile time, which isn't
    ;; necessarily something that we are allowed to do, and the presence of those
    ;; written files at run time, something that we are not explicitly guaranteed.
    
    ;; (eval-when (:compile-toplevel :load-toplevel :execute)
    ;;   (let ((num 0))
    ;;     (defun make-file-name ()
    ;;       (format nil "~D.lisp" num)))
    
    ;;   (defun write-file (source)
    ;;     (with-open-file (out (make-file-name) :direction :output)
    ;;       (format out "~A~%" source))))
    
    ;; (write-file "(defun test () t)")
    
    
    ;; There are some other tools that are extremely useful if you are using
    ;; hackerrank.  HackerRank problems typically involve repeated invocation of
    ;; your program from the shell, which is then given some partial input and an
    ;; output is expected for your next move.  This is pretty darned annoying as
    ;; this seems to indicate that your submission has to be state free.  This is
    ;; not actually the case, as the HackerRank rules clearly indicate that you can
    ;; write a file which will be present on the next invocation of you program.  Is
    ;; this true?
    
    ;; What we need is a way to serialize all the state of the system and then
    ;; restart the system on the next invocation.
    
    ;; One interesting way to do this would be to dump a core and then find a way to
    ;; reload it on the next invocation.
    
    ;; The other obvious way to do this is to print out data and then read it in,
    ;; perhaps using something as sophisticated as a serialization library.
    
    ;; We could also use a problem to probe properties about the system.  See if we
    ;; can use Clommand.
    
    
    
    ;; What would be neat is if I used slime-calls-who to perform tree shaking.
    ;; This is not implemented in sbcl, but it can be faked by using
    ;; slime-who-calls, which is implemented.  This works for both functions and
    ;; macros.
    
    ;; To fake it, just search all symbols that are defined in a package (and that
    ;; belong to that package) and use slime-who-calls to figure out who calls them
    ;; and then, for each of those, record the symbol in question into it's
    ;; calls-who entry (in a hash).  After that, you have an inverted call.
    
    ;; Note that this only works within for within the same imp/version, though the
    ;; coding can (usually) be made to not use special functions for different imps,
    ;; which would make the call tree work.
    
    ;; This could really be the start of a bigger shake and bake (macro-expansion)
    ;; project.
    
    
    

    external by He Junjia modified Sep 4, 2015  78  1  2  0

    learning golang in hackerrank AI domain https://www.hackerrank.com/domains/ai

    learning golang in hackerrank AI domain https://www.hackerrank.com/domains/ai: bot.go
    Go
    // Solved 'Bot saves princess' on hackerrank
    // https://www.hackerrank.com/challenges/saveprincess
    package main
    
    import (
    	"bufio"
    	"fmt"
    	"os"
    	"strconv"
    	"strings"
    )
    
    func main() {
    	var princessX, princessY int
    	var botX, botY int
    	var line string
    
    	// Read matrix size.
    	fmt.Scanln(&line)
    	n, _ := strconv.Atoi(line)
    
    	scanner := bufio.NewScanner(os.Stdin)
    	for i := 0; i < n; i++ {
    		scanner.Scan()
    		line = scanner.Text()
    		// Find the princess.
    		if i == 0 || i == n-1 {
    			if idx := strings.Index(line, "p"); idx != -1 {
    				princessX, princessY = idx, i
    			}
    		}
    		// Find the bot.
    		if idx := strings.Index(line, "m"); idx != -1 {
    			botX, botY = idx, i
    		}
    	}
    
    	// Move the bot.
    	horMove, horDist := "LEFT", botX-princessX
    	if horDist < 0 {
    		horMove = "RIGHT"
    		horDist = -horDist
    	}
    	for ; horDist > 0; horDist-- {
    		fmt.Println(horMove)
    	}
    
    	vertMove, vertDist := "UP", botY-princessY
    	if vertDist < 0 {
    		vertMove = "DOWN"
    		vertDist = -vertDist
    	}
    	for ; vertDist > 0; vertDist-- {
    		fmt.Println(vertMove)
    	}
    }
    
    
    

    external by cc2011 modified Apr 1, 2015  67  1  3  0

    hackerrank [combinatorics]https://www.hackerrank.com/challenges/picking-cards

    hackerrank [combinatorics]https://www.hackerrank.com/challenges/picking-cards: gistfile1.txt
    //https://www.hackerrank.com/challenges/picking-cards
    //http://www.programminglogic.com/codesprint-2-problem-picking-cards/(time out)
    //binary search solution : https://github.com/havelessbemore/hackerrank/blob/master/algorithms/math/picking-cards.java
    
    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
        private static final int MOD = 1000000007;
        public static void main(String[] args) {
            try {
                Scanner s = new Scanner(System.in);
                int t = Integer.parseInt(s.nextLine());
                while(t >0) {
                    int n = Integer.parseInt(s.nextLine());
                    String[] inputArr = s.nextLine().split(" ");
                    int[] arr = new int[n];
                    long ways = 1L;
                    for(int i=0; i < n; i++) {
                            arr[i] = Integer.parseInt(inputArr[i]);
                    }
                    for(int i=0; i < n;i++) {
                            ways *= (count(i,arr)-i);
                            ways = ways %MOD;
                    }
                    System.out.println(ways);
                    t--;
                }
            } catch(Exception e){
                e.printStackTrace();
            }
        }
        public static int count(int curr,int[] arr){
            int count = 0;
            for(int i=0; i < arr.length;i++) {//why starting from 0? because say you have 3 3 3 (3) 3 3 (you can use any 3 before(3) )
                    if(arr[i] <= curr)
                            count++;
            }
            return count;
        }
    }
    
    

    external by somzee modified Feb 3, 2016  33  1  1  0

    HackerRank - My solution for https://www.hackerrank.com/contests/worldcodesprint/challenges/two-pluses

    HackerRank - My solution for https://www.hackerrank.com/contests/worldcodesprint/challenges/two-pluses: two-pluses.rb
    ## Solution for https://www.hackerrank.com/contests/worldcodesprint/challenges/two-pluses
    
    # Read input from STDIN
    n, m = gets.strip.split(' ').map{|x| x.to_i}
    matrix = []
    n.times do |row|
    	matrix << gets.strip.split('')
    end
    
    # Calculate best area
    def find_best_area(matrix)
    	best_area = 1
    	all_pluses = find_all_pluses(matrix).sort.reverse
    	all_pluses.each do |plus|
    		return best_area if (plus.area ** 2) <= best_area
    		second_plus = find_second_plus(matrix, plus)
    		best_area = [best_area, (plus.area * second_plus.area)].max
    	end
    	best_area
    end
    
    # Given a matrix, find all valid pluses
    def find_all_pluses(matrix)
    	all_pluses = []
    	m, n = matrix.size, matrix[0].size
    	max_plus_size = [n, m].min
    	for j in 0..(m-1) do
    		for i in 0..(n-1) do
    			for plus_size in (1..max_plus_size).step(2)
    				new_plus = Plus.new(j, i, plus_size)
    				if new_plus.valid_on_matrix?(matrix)
    					all_pluses << new_plus
    				end
    			end
    		end
    	end
    	all_pluses
    end
    
    # Given a matrix and a plus, find a second valid plus
    def find_second_plus(matrix, plus)
    	blacken!(matrix, plus)
    	second_plus = find_all_pluses(matrix).sort.last
    	whiten!(matrix,plus)
    	second_plus
    end
    
    # Change color of used cells to Bad
    def blacken!(matrix, plus)
    	colorize(matrix, plus, 'B')
    end
    
    # Revert Blacken on matrix
    def whiten!(matrix, plus)
    	colorize(matrix, plus, 'G')
    end
    
    # Change a color of particular element in matrix
    def colorize(matrix, plus, color)
    	plus.coords.each do |j, i|
    		matrix[j][i] = color
    	end
    end
    
    # Define object class for Plus
    class Plus
    	attr_reader :y, :x, :n
    	def initialize(y, x, n)
    		@x, @y, @n = x, y, n
    	end
    
    	def area
    		(2 * n) - 1
    	end
    
    	def <=> (plus)
    		n <=> plus.n
    	end
    
    	def half_length
    		(n / 2).floor
    	end
    
    	def coords
    		coords = ((y - half_length)..(y + half_length)).map{|j| [j, x]}
    		coords += ((x - half_length)..(x + half_length)).map{|i| [y, i]}
    	end
    	
    	def valid_on_matrix?(matrix)
    		coords.each do |j, i|
    			return false if (j < 0) || (i < 0) || matrix[j].nil? || matrix[j][i].nil?
    			return false if matrix[j][i] == 'B'
    		end	
    		true
    	end
    end
    
    puts find_best_area(matrix)
    
    

    external by Github modified Nov 25, 2015  22  1  1  0

    solution for problem on hackerrank (https://www.hackerrank.com/challenges/plus-minus), It passes any of the testcases I give it including ones that the site says it fails when checking for solutions. I'm not sure what the problem is, I'm assuming it's...

    solution for problem on hackerrank (https://www.hackerrank.com/challenges/plus-minus), It passes any of the testcases I give it including ones that the site says it fails when checking for solutions. I'm not sure what the problem is, I'm assuming it's a float precision problem: plusminus.c
    /*solution for problem on hackerrank (https://www.hackerrank.com/challenges/plus-minus), It passes any of the
    testcases I give it including ones that the site says it fails when checking for solutions.
    I'm not sure what the problem is, but I'm assuming it's a float precision problem
    
    is supposed to take scan in an array of numbers of length given by the first number and then print the ratio of positive/ negative
    and zero numbers to the third decimal place*/
    
    #include <math.h>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <limits.h>
    #include <stdbool.h>
    
    int main(){
    	int n, pos, neg, arr_i; 
    	scanf("%d",&n);
    	int arr[n];
    	pos = 0;
    	neg = 0;
    
    	for(arr_i = 0; arr_i < n; arr_i++){
    		scanf("%d",&arr[arr_i]);
    		if (arr[arr_i] != 0){
    			if (arr[arr_i] > 0){
    				pos +=1;
    			}
    			else{
    				neg +=1;
    			}
    		}
    	}
    	
    	printf("%.3f\n", ((pos*1.0)/n));
    	printf("%.3f\n", ((neg*1.0)/n));
    	printf("%.3f", ((1.0*(6-(neg+pos)))/n));
    	return 0;
    }
    
    
    
    • Public Snippets
    • Channels Snippets