working on it ...


Explore Public Snippets

Sort by

Found 789 snippets matching: hackerrank

    public by te777 modified Sep 24, 2016  209  0  4  0

    Hackerrank Count Strings solution python

    Hackerrank Count Strings solution python
    Created on Aug 7, 2016
    @author: Siddharthasahu @
    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
        def epsilon():
            return ":e:"
        def setstartstate(self, state):
            self.startstate = state
        def addfinalstates(self, state):
            if isinstance(state, int):
                state = [state]
            for s in state:
                if s not in self.finalstates:
        def addtransition(self, fromstate, tostate, inp):
            if isinstance(inp, str):
                inp = set([inp])
            if fromstate in self.transitions:
                if tostate in self.transitions[fromstate]:
                    self.transitions[fromstate][tostate] = self.transitions[fromstate][tostate].union(inp)
                    self.transitions[fromstate][tostate] = inp
                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]:
            return trstates
        def getEClose(self, findstate):
            allstates = set()
            states = set([findstate])
            while len(states)!= 0:
                state = states.pop()
                if state in self.transitions:
                    for tns in self.transitions[state]:
                        if Automata.epsilon() in self.transitions[state][tns] and tns not in allstates:
            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+"'",)
        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)
            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])
            for s in self.finalstates:
            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
                        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"""
        def basicstruct(inp):
            state1 = 1
            state2 = 2
            basic = Automata()
            basic.addtransition(1, 2, inp)
            return basic
        def plusstruct(a, b):
            [a, m1] = a.newBuildFromNumber(2)
            [b, m2] = b.newBuildFromNumber(m1)
            state1 = 1
            state2 = m2
            plus = Automata()
            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())
            return plus
        def dotstruct(a, b):
            [a, m1] = a.newBuildFromNumber(1)
            [b, m2] = b.newBuildFromNumber(m1)
            state1 = 1
            state2 = m2-1
            dot = Automata()
            dot.addtransition(a.finalstates[0], b.startstate, Automata.epsilon())
            return dot
        def starstruct(a):
            [a, m1] = a.newBuildFromNumber(2)
            state1 = 1
            state2 = m1
            star = Automata()
            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())
            return star
    class DFAfromNFA:
        """class for building dfa from e-nfa and minimise it"""
        def __init__(self, nfa):
        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):
        def displayMinimisedDFA(self):
        def buildDFA(self, nfa):
            allstates = dict()
            eclose = dict()
            count = 1
            state1 = nfa.getEClose(nfa.startstate)
            eclose[nfa.startstate] = state1
            dfa = Automata(nfa.language)
            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
                            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:
            self.dfa = dfa
            self.allstates = allstates
            self.trstates = trstates 
        def acceptsString(self, string):
            currentstate = self.dfa.startstate
            for ch in string:
                if ch==":e:":
                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
                            if len(s1) > 1:
                                raise BaseException("Multiple transitions detected in DFA")
                            elif len(s1) == 0:
                            s1 = s1.pop()
                            s2 = s2.pop()
                            if s1 != s2:
                                if [s1, s2] in distinguished or [s2, s1] in distinguished:
                                    eq = 0
                                    toappend.append([s1, s2, char])
                                    eq = -1
                        if eq == 0:
                            distinguished.append([states[i], states[j]])
                        elif eq == -1:
                            s = [states[i], states[j]]
                            unchecked[count] = s
                            count += 1
                            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:
                            distinguished.append([pair[0], pair[1]])
                            newFound = True
            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
                self.minDFA = self.dfa.newBuildFromEquivalentStates(equivalent, pos)
    class NFAfromRegex:
        """class for building e-nfa from regular expressions"""
        def __init__(self, regex):
   = '*'
            # Next line was originally " = '+'
            # Changed to '|' to fit aplication of regex for program
   = '|'
   = '.'
            self.openingBracket = '('
            self.closingBracket = ')'
            self.operators = [,]
            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)])
        def getNFA(self):
            return self.nfa
        def displayNFA(self):
        def buildNFA(self):
            language = set()
            self.stack = []
            self.automata = []
            previous = "::e::"
            for char in self.regex:
                if char in self.alphabet:
                    if previous != and (previous in self.alphabet or previous in [self.closingBracket,]):
                elif char  ==  self.openingBracket:
                    if previous != and (previous in self.alphabet or previous in [self.closingBracket,]):
                elif char  ==  self.closingBracket:
                    if previous in self.operators:
                        raise BaseException("Error processing '%s' after '%s'" % (char, previous))
                        if len(self.stack) == 0:
                            raise BaseException("Error processing '%s'. Empty stack" % char)
                        o = self.stack.pop()
                        if o == self.openingBracket:
                        elif o in self.operators:
                elif char ==
                    if previous in self.operators or previous  == self.openingBracket or previous ==
                        raise BaseException("Error processing '%s' after '%s'" % (char, previous))
                elif char in self.operators:
                    if previous in self.operators or previous  == self.openingBracket:
                        raise BaseException("Error processing '%s' after '%s'" % (char, previous))
                    raise BaseException("Symbol '%s' is not allowed" % char)
                previous = char
            while len(self.stack) != 0:
                op = self.stack.pop()
            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):
                if len(self.stack) == 0:
                top = self.stack[len(self.stack)-1]
                if top == self.openingBracket:
                if top == char or top ==
                    op = self.stack.pop()
        def processOperator(self, operator):
            if len(self.automata) == 0:
                raise BaseException("Error processing operator '%s'. Stack is empty" % operator)
            if operator ==
                a = self.automata.pop()
            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 ==
                elif operator ==
    """def drawGraph(automata, file = ""):
        f = popen(r"dot -Tpng -o graph%s.png" % file, 'w')
            raise BaseException("Error creating graph")
    def isInstalled(program):
        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
            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):
        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: ")
        #print ("\nDFA: ")
        #print ("\nMinimised DFA: ")
        #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__':

    external by He Junjia modified Jan 18, 2015  1626  213  3  0

    solved 'Almost Sorted' on hackerrank

    solved 'Almost Sorted' on hackerrank 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) {
                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);
        return 0;

    external by EDFward modified Aug 30, 2015  1685  125  3  1

    solved 'Breadth First Search: Shortest Reach' on hackerrank

    solved 'Breadth First Search: Shortest Reach' on hackerrank
    from collections import namedtuple
    # A reasonable large number to represent infinity.
    INF = (1 << 31)
    # 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.
      # 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  494  46  4  0

    hackerrank [Greedy]

    hackerrank [Greedy] gistfile1.txt
    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(;
                    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) {
                                            int temp = input[j];
                                            input[j] = input[swapIndex];
                                            input[swapIndex]= temp;
                                    } else {
                    for(int j=0;j < n;j++) {
                            if(j >0)
                                    System.out.print(" ");
            } catch(Exception e){
        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  292  5  3  0

    solved 'Bricks Game' on hackerrank

    solved 'Bricks Game' on hackerrank
    def max_score(bricks):
        """bricks: A list of bricks."""
        sz = len(bricks)
        # DP algorithm. See the 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):
        bricks = map(int, raw_input().split())
        print max_score(bricks)

    external by smithzvk modified Jan 6, 2014  504  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
    (defpackage :hacker-rank-submission
      (:use :cl :iterate)
    (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~%)"
    (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-downcase (symbol-name component))
                                      :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)
            (with-open-file (out output-file :direction :output :if-exists if-exists)
              (princ output out)
    ;; 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
                                     ((atom (second loads))
                                      ;; only one dependency
                                      (list (second loads)))
                                      ;; Many dependencies
                                      (second (second loads)))))))
             (cl-fad:*default-template* "TEMPORARY-FILES:%")
             (system-name (concatenate 'string (format nil "~A" (random 10000))
               (intern (string-upcase system-name) :keyword))
                   (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))
          (with-open-file (in file)
            (read in)
            (let ((concat (make-concatenated-stream
                             :output-file :string))
              (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))
       "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  66  1  2  0

    learning golang in hackerrank AI domain

    learning golang in hackerrank AI domain bot.go
    // Solved 'Bot saves princess' on hackerrank
    package main
    import (
    func main() {
    	var princessX, princessY int
    	var botX, botY int
    	var line string
    	// Read matrix size.
    	n, _ := strconv.Atoi(line)
    	scanner := bufio.NewScanner(os.Stdin)
    	for i := 0; i < n; i++ {
    		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-- {
    	vertMove, vertDist := "UP", botY-princessY
    	if vertDist < 0 {
    		vertMove = "DOWN"
    		vertDist = -vertDist
    	for ; vertDist > 0; vertDist-- {

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

    hackerrank [combinatorics]

    hackerrank [combinatorics] gistfile1.txt
    // out)
    //binary search solution :
    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(;
                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;
            } catch(Exception e){
        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)
            return count;

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

    HackerRank - My solution for

    HackerRank - My solution for two-pluses.rb
    ## Solution for
    # Read input from STDIN
    n, m = gets.strip.split(' ').map{|x| x.to_i}
    matrix = []
    n.times do |row|
    	matrix << gets.strip.split('')
    # 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
    # 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 =, i, plus_size)
    				if new_plus.valid_on_matrix?(matrix)
    					all_pluses << new_plus
    # 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
    # Change color of used cells to Bad
    def blacken!(matrix, plus)
    	colorize(matrix, plus, 'B')
    # Revert Blacken on matrix
    def whiten!(matrix, plus)
    	colorize(matrix, plus, 'G')
    # Change a color of particular element in matrix
    def colorize(matrix, plus, color)
    	plus.coords.each do |j, i|
    		matrix[j][i] = color
    # Define object class for Plus
    class Plus
    	attr_reader :y, :x, :n
    	def initialize(y, x, n)
    		@x, @y, @n = x, y, n
    	def area
    		(2 * n) - 1
    	def <=> (plus)
    		n <=> plus.n
    	def half_length
    		(n / 2).floor
    	def coords
    		coords = ((y - half_length)..(y + half_length)).map{|j| [j, x]}
    		coords += ((x - half_length)..(x + half_length)).map{|i| [y, i]}
    	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'
    puts find_best_area(matrix)

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

    solution for problem on hackerrank (, 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 (, 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 (, 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; 
    	int arr[n];
    	pos = 0;
    	neg = 0;
    	for(arr_i = 0; arr_i < n; arr_i++){
    		if (arr[arr_i] != 0){
    			if (arr[arr_i] > 0){
    				pos +=1;
    				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