Calculating a unique count within a rolling time window I have a Pandas DataFrame that contains a row per member per day, expressing member interaction with a website. Members interact only on some days, each member is identified with an ID. Here is a simulated example:
import pandas as pd
import numpy as np

# Generate data.

ids = np.repeat(np.arange(100), np.random.randint(100, size = 100))

test = (
    pd.Series(
        ids,
        index = pd.Series(pd.date_range('2020-01-01', '2020-02-01').values).sample(ids.shape[0], replace = True)
    )
    .sort_index()
)

print(test.head())

Gives:
2020-01-01     4
2020-01-01    65
2020-01-01    95
2020-01-01    40
2020-01-01    88
dtype: int32

I'd like to calculate a unique count of members within a 7 day rolling window. After some experimentation and research on Stack Overflow (including Pandas rolling / groupby function), I arrived at an explicit loop and slicing.
# Calculate rolling 7 day unique count.

unique_count = {}

for k in test.index.unique():

    unique_count[k] = test.loc[k - pd.Timedelta('7 days'):k].nunique()

# Store as a dataframe and truncate to a minimum period.

unique_count = pd.DataFrame.from_dict(unique_count, orient = 'index', columns = ['7_day_unique_count']).iloc[7:]

print(unique_count.tail())

Gives:
            7_day_unique_count
2020-01-28                  98
2020-01-29                  98
2020-01-30                  98
2020-01-31                  97
2020-02-01                  97

This seems to work correctly and performs OK. But is it possible to do this without the explicit loop, such as with resample / groupby / rolling functions? If so, is that more efficient?

How about something like this:
test.rolling('7d').apply(lambda s:s.nunique()).groupby(level=0).max()

rolling('7d') is the rolling window. The window is determined for each row. So the first window starts from the row "2020-01-01     4" and extends 7 days in the past. The second window starts from the row "2020-01-01    65" and extends 7 days in the past.
.apply(lambda s:s.nunique()) determines the number of unique items in the window. But, because of the way rolling works, we get multiple results for the same day.
.groupby(level=0) groups the results by the date.
.max() takes the maximum nunique value for that date.
The above approach seemed rather slow, so here's a different approach. Basically use a Counter as a multiset and use a deque as a FIFO queue.  For each day update the Counter with the id's for that day and subtract the ones for the day at the beginning of the window.  The len of the Counter is then the number of unique ids.
from collections import Counter, deque

WINDOW = 7

fifo = deque(maxlen=WINDOW)
uniq = Counter()

def unique_in_window(x):
    if len(fifo) == WINDOW:
        uniq.subtract(fifo.popleft())

    uniq.update(x)
    fifo.append(x)

    return len(uniq)

test.groupby(level=0).apply(unique_in_window)


Migrating data from multiple spreadsheets to multiple text files This is like the reverse functionality of Text file to spreadsheet.

One or multiple .xlsx files in the path of the script get opened and the content is split into multiple .txt files.

For example, say you have two excel files in the folder:

file1.xlsx

file2.xlsx

The output created:

spreadsheet_to_text.py

"""
Reads in .xlsx files from path were the script is located.
Then the data of each column is split into a .txt file
"""

import glob
import openpyxl
from openpyxl.utils import get_column_letter

def get_text_filename(filename: str, column: int)->str:
    """
    Creates a text filename based on .xlsx file filename and column
    """
    return (filename.rstrip(".xlsx")
            + "_" + get_column_letter(column) + '.txt')

def xlsx_to_txt(filename: str):
    """
    Extract data from a .xlsx file in the script folder into
    multiple .txt files
    """
    workbook = openpyxl.load_workbook(filename)
    sheet_names = workbook.sheetnames
    sheet = workbook[sheet_names[0]]

    for column in range(1, sheet.max_column + 1):
        if sheet.cell(row=1, column=column).value:
            text_filename = get_text_filename(filename, column)
            with open(text_filename, mode='w') as textfile:
                for row in range(1, sheet.max_row + 1):
                    if sheet.cell(column=column, row=row).value:
                        textfile.writelines(
                            sheet.cell(column=column, row=row).value + '\n')

def spreadsheet_into_text():
    """main logic for split spreadsheet data into multiple text files"""
    for filename in glob.iglob("*.xlsx"):
        xlsx_to_txt(filename)

if __name__ == "__main__":
    spreadsheet_into_text()

I already incorporated some improvements from Text file to spreadsheet. I wonder how the code can get further improved.

This looks quite clean in general. May I suggest a few minor improvements:

I think you could just use workbook.active to get the sheet
instead of doing the rstrip(".xlsx") which would also right-strip out .sslsx or sl.xs.ss and even grab a part of the actual filename:

In [1]: "christmas.xlsx".rstrip(".xlsx")
Out[1]: 'christma'

use os module or the beautiful pathlib to properly extract a filename without an extension:

In [1]: from pathlib import Path

In [2]: Path("christmas.xlsx").resolve().stem
Out[2]: 'christmas'

calculate what you can before the loop instead of inside it. For instance, sheet.max_row is something you could just remember in a variable at the top of your function and re-use inside. It's not a lot of savings, but attribute access still has its cost in Python:

max_row = sheet.max_row

something similar is happening when you get the value of a cell twice, instead:

cell_value = sheet.cell(column=column, row=row).value

if cell_value:
    textfile.writelines(cell_value + '\n')

it may be a good idea to keep the nestedness at a minimum ("Flat is better than nested.") and would rather check for a reverse condition and use continue to move to the next iteration:

for column in range(1, sheet.max_column + 1):
    if not sheet.cell(row=1, column=column).value:
        continue

    text_filename = get_text_filename(filename, column)

Some out-of-the-box ideas:

feels like if you do it with pandas.read_excel() it may just become way more easier and beautiful


Select text with just one click I wrote this JS code with some jQuery and got a one-click-text-selection. Maybe someone can improve this code, because I think it's not "clean" and short engough ;) But I don't want to use an input field. Let me know if you have some ideas!

function SelectText(element) {
    var doc = document,
        text = doc.getElementById(element),
        range,
        selection;
    if (doc.body.createTextRange) {
        range = document.body.createTextRange();
        range.moveToElementText(text);
        range.select();
    } else if (window.getSelection) {
        selection = window.getSelection();
        range = document.createRange();
        range.selectNodeContents(text);
        selection.removeAllRanges();
        selection.addRange(range);
    }
}
$(function() {
    $('p').click(function () {
        SelectText('autoselect');
    });
});

And this is the HTML part:

Some cool text!

Here's the code in a fiddle.

You can further improve this by making it a jQuery plugin instead to make it reusable across any element.

non-IE browsers, combined, account for ~60% of users at the time of writing. This means 60% of the time, the two conditions are evaluated since you check for IE first. Instead, reverse the conditions to get it right on the first check 60% of the time.

$.fn.OneClickSelect = function () {
  return $(this).on('click', function () {

    // In here, "this" is the element

    var range, selection;

    if (window.getSelection) {
      selection = window.getSelection();
      range = document.createRange();
      range.selectNodeContents(this);
      selection.removeAllRanges();
      selection.addRange(range);
    } else if (document.body.createTextRange) {
      range = document.body.createTextRange();
      range.moveToElementText(this);
      range.select();
    }
  });
};

// Apply to these elements
$('p, #all-select').OneClickSelect();


Loading items into array from SQL Server The program we are working at has the following function:

function loadItem(arrayValues,arrayNames) {
    var j=document.getElementById('itemSelect').options.length;
    for(var i=0;i<arrayValues.length;i++) {
        if(!existsElement(document.getElementById('itemSelect'),arrayValues[i])) {
            document.getElementById('itemSelect').options[j]=new Option(arrayValues[i]+" - "+arrayNames[i],arrayValues[i],null);
            j++;
        }
    }
}

This fills a list that is later used to filter a search.

It was originally designed for small arrays (up to 25 elements) and it worked perfectly.

Now, I'm trying to use it to fill with the whole contents of a SQL table (about 9500 elements), I take the data from the DB with Java, transfer it to Javascript via AJAX and parse that List into two arrays that can be used with this function. That takes about a second, but then this function takes about 20 seconds to complete.

Why is it that slow, and what can I do to improve it?

Main issues

Access

DOM operations take time. You're selecting the element N^2 + 1 times. This can be reduced to 1: document.getElementById('itemSelect')
You're constantly getting arrayValues[i], which only needs to be done once.

Style

You should put spaces after commas: arg, arg2
You should put spaces before and after operations, for readability: var name = value
Spaces after semicolons: i < length; i++

Rewrite

function loadItem(arrayValues, arrayNames) {
    var itemSelect = document.getElementById('itemSelect'),
        j = itemSelect.options.length;
    for(var i = 0, length = arrayValues.length; i < length; i++) {
        let val = arrayValues[i];
        if(!existsElement(itemSelect, val)) {
            itemSelect.options[j] = new Option(val + " - " + arrayNames[i], val, null);
            j++;
        }
    }
}


Basic Java dice game public class diceGame {
    public static void main(String[] args) {
        int dice1;
        int dice2;
        int count = 0;
        int theSum = 0;
        int lowest = Integer.MAX_VALUE;
        int finalSum = 0;
        int diceSum;
        int totalSum=0;
        while (count < Integer.parseInt(args[0])) {
            count = count + 1;
            diceSum=0;
            theSum=0;
            while (diceSum!=7) {
                diceSum = 0;
                dice1 = 1 + (int) ((Math.random() * (6 - 1)) + 1);
                dice2 = 1 + (int) ((Math.random() * (6 - 1)) + 1);
                diceSum = dice1 + dice2;
                if (diceSum != 7) {
                    theSum = theSum + diceSum;
                }
                //System.out.println("the sum is "+theSum);
            }
            if (theSum > finalSum) {
                finalSum = theSum;
            }
            if (theSum < lowest) {
                lowest = theSum;
            }
            totalSum=totalSum+theSum;
        }
        double average=(double)totalSum/(Double.parseDouble(args[0]));
        System.out.println("After " + args[0] + " simulations: ");
        System.out.println("Biggest sum: " + finalSum);
        System.out.println("Smallest sum: " + lowest);
        System.out.println("The average is: "+average);

    }
}

I would like to execute this with much less code and want to learn other/better ways to do some of things I did, such as a random ints.

Your main() function desperately needs to be busted up, for multiple reasons:

You use a lot of variables, all of them declared at the top of main().  A human mind is only good at keeping track of about 7 things at a time, so this code is hard to follow.
It violates the Single Responsibility Principle, by parsing the command line, throwing the dice, keeping the statistics, and printing the report.  That's a lot of work for one function!
Object-oriented code is preferred in Java.  A static function avoids object-oriented thinking.
It's unclear what you're simulating: what constitutes a trial, and what you mean by biggest/smallest sum.

A quick win in readability can be obtained by defining a Die class: die.toss() reads like English, whereas 1 + (int) ((Math.random() * (6 - 1)) + 1) doesn't.

class Die {
    // Since "throw" is a Java keyword, we use "toss"
    int toss() {
        return 1 + (int)(6 * Math.random());
    }
}

A good start to taming the variables would be to declare each of them in the tightest scope possible.  For example, theSum, and diceSum are only relevant inside the loop.  count is a loop counter, and it's much easier to recognize if you rewrite the loop as a for-loop.  dice1 and dice2 are only relevant inside the inner loop, which is better expressed as a do-while loop.

for (int count = 0; count < Integer.parseInt(args[0]); count++) {
    int theSum = 0, diceSum;
    do {
        int dice1 = 1 + (int) ((Math.random() * (6 - 1)) + 1);
        int dice2 = 1 + (int) ((Math.random() * (6 - 1)) + 1);
        diceSum = dice1 + dice2;
        if (diceSum != 7) {
            theSum = theSum + diceSum;
        }
        //System.out.println("the sum is "+theSum);
    } while (diceSum != 7);
    …
}

Now a picture is beginning to emerge.  The inner loop is what you would call a simulation trial.  Based on that, I would define a DiceSimulation class with a runTrial() method.  Everything else just falls into place around that core function.  ☺

public class DiceSimulation {
    private int trials = 0,                 // Formerly count
                min = Integer.MAX_VALUE,    // Formerly lowest
                max = 0,                    // Formerly finalSum
                sum = 0;                    // Formerly totalSum

    private Die die1 = new Die(),
                die2 = new Die();

    /**
     * One trial consists of tossing a pair of dice until a sum of 7 is obtained.
     * The result of the trial is the sum of all tosses up to, but not including,
     * the toss that resulted in 7.
     */
    public int runTrial() {
        int trialSum = 0, pairSum;           // Formerly theSum and diceSum
        while (7 != (pairSum = die1.toss() + die2.toss())) {
            trialSum += pairSum;
        }

        if (trialSum > max) {
            max = trialSum;
        }
        if (trialSum < min) {
            min = trialSum;
        }
        sum += trialSum;
        trials++;
        return trialSum;
    }

    public void report() {
        System.out.println("After " + trials + " simulations: ");
        System.out.println("Biggest sum: " + max);
        System.out.println("Smallest sum: " + min);
        System.out.println("The average is: " + (double)sum / trials);
    }

    public static void main(String[] args) {
        int trials = Integer.parseInt(args[0]);

        DiceSimulation sim = new DiceSimulation();
        for (int count = 0; count < trials; count++) {
            sim.runTrial();
        }
        sim.report();
    }
}


Creating strings of desired length from a list of substrings I have a method that generates strings from a list of substrings, and the desired length of all these strings is passed as an argument of the method. Here is my code:

import itertools as it

print make_string(5)

def make_string(wanted_length):
    available_strings = ['AB', 'CDE', 'FGHIJK', 'LMN', 'OP', 'QR', 'ST', 'U']
    minimum_length = 0
    i=2
    while minimum_length < wanted_length:
        products = it.product(*[available_strings]*i)
        str_products = [''.join(map(str,x)) for x in products]
        valid_products = [x for x in str_products if len(x)==wanted_length]
        if valid_products:
            return valid_products
        minimum_length = len(min(str_products, key=len))
        i += 1
    return None

As one can expect, it is incredibly slow and feels overall wrong even if it works. Do you have any input to help me make it better ?

EDIT

As Graipher pointed out in his comment, the above code stops when a valid string of desired length is found but doesn't return all valid strings of desired length. Here is the fixed code, which is obviously even slower than the previous one :)

def make_string(wanted_length):
    all_valid_products = []
    available_strings = ['AB', 'CDE', 'FGHIJK', 'LMN', 'OP', 'QR', 'ST', 'U']
    minimum_length = 0
    i=2
    while minimum_length < wanted_length:
        products = it.product(*[available_strings]*i)
        str_products = [''.join(map(str,x)) for x in products]
        valid_products = [x for x in str_products if len(x)==wanted_length]
        if valid_products:
            all_valid_products.extend(valid_products)
        minimum_length = len(min(str_products, key=len))
        i += 1
    return all_valid_products

The trouble is that you are generating an array with all possible combinations of all possible strings and then whittling it down from there.  You end up doing a lot of work you don't have to do.  However, it makes for conceptually easy-to-understand code, so I certainly wouldn't call this solution "wrong" (unless it is simply too slow for your actual application).  There is often a trade off between "does the job very well" and "easy to understand", and sometimes the latter is the real winner.

In terms of alternate approaches, I just have a general outline of one I can suggest (if it is helpful).  Instead of doing this in "string" space you could imagine doing this in "length" space.  I.e. instead of thinking of the problem in terms of allowed substrings, think of it in terms of allowed lengths of substrings:

available_strings = ['AB', 'CDE', 'FGHIJK', 'LMN', 'OP', 'QR', 'ST', 'U']

becomes:

strings_by_length = { 1: [ 'U' ], 2: [ 'AB', 'OP', 'QR', 'ST' ], 3: [ 'CDE', 'LMN' ], 6: [ 'FGHIJK' ] }
substring_lengths = strings_by_length.keys()

You now know that you have substrings of length 1, 2, 3, and 6.  Then break down the length combinations that are actually applicable.  For instance, for a desired length of 5 you can combine substrings of length:

[ 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 3 ],
[ 1, 4 ],
[ 1, 2, 2 ],
[ 3, 2 ],
[ 5 ]

You can automatically rule out [1, 4] and [ 5 ] because you have no substrings that match those lengths.  You also rule out substring FGHIJK because it is too long for any of your allowed lengths.  Of course, generating this list of possibilities is a bit tricky, and then the next part is also tricky:

Take your list of allowed combinations and combine them with the substrings separated by length to get all allowed combinations.  I'm not familiar with the itertools library but it might help with that.  For instance you could imagine taking combination [ 1, 2, 2 ] and basically doing an iterative combination of:

build_all_combinations( strings_by_length[1], strings_by_length[2], strings_by_length[2] )

Overall, this makes sure you are only calculating combinations for values that you know are allowed, rather than calculating all combinations and then filtering.  It has the potential to be more efficient, but the devil is always in the details.  Not sure how it will work out in practice, or how easy it will be to write.

Edit to add notes about performance

In case you are new to it, welcome to the world of np-complete problem sets!  I think your problem is effectively a variation on the knapsack problem.  Reading up on that may give you some ideas of different (and more efficient) approaches to this problem.  The short of it is that this can be slow.  I'm pretty sure you are running on O(n^2) time, which is not terrible, all things considered.  Anyway, onto the steps to optimize:

1. Make your algorithm smarter!

This is basically what I was trying to do.  How much my particular algorithm will help will vary depending on the precise problem.  If you have a lot of sub strings that are not applicable (i.e. the 'FGHIJK' in your example), then a little intelligence can save you a lot of computation.  In the example you gave some the general algorithm I had suggested would have ruled out that one branch before doing any computations, which would have theoretically brought the minimum number of computations down from 8^2 = 64 to 7^2 = 49, a ~25% improvement.  However, If all of your substrings had been shorter than the max length, there would have been no improvement.

In practice though I'm comparing to the best-case scenario, and your current algorithm may not be anywhere near that.  Your current algorithm may be running in a time substantially slower than the best-case scenario.  That is what I meant by "the devil is in the details".  Do you know how itertools works?  External libraries can make things convenient, but depending on how they run they may actually make your algorithm slower.  To really speed things up, it can help to really think through your algorithm and make sure it is running as close to ideal as possible.

2. Run in compiled code

Regardless of how smart your algorithm is, you are still facing at least O(n^2) time.  For large n the answer isn't going to be smartness but rather raw computing power.  As an interpreted language python is relatively slow, so in cases like this that can be a big source of your problem.  This doesn't mean you have to rewrite in C or another language, as python has many built in tools that may delegate parts of your tasks to compiled code.  As a general example (which may or may not be helpful for you), in a lot of my computations I used numpy extensively and relied upon its built-in array operations, in particular seeking to avoid for loops.  Looping tends to be one of the slowest parts of interpreted languages, while all of numpy's array operations are actually running as compiled code.  Taking parts of algorithms and switching from for loops to array operations that execute as compiled code on the server frequently saw performance gains by a factor of 5-40.

3. Parallel processing!

Some problems are very amenable to parallel processing.  This can either mean taking advantage of multi-core CPUs, working in a distributed computing environment (aka hadoop) or even GPU processing.  Off the top of my head, I'm not sure how helpful any of those options will be to your program.  I'm going to guess that this isn't important enough to be worth the time it takes to re-write this algorithm for some advance parallel processing but hey, you never know.

Summary

These are the steps I would go through if I had code that I needed to run quickly that was simply too slow.  How much time you spend actually optimizing things always depends on how important the code is, of course.  But ultimately you have those three options: make the code faster, figure out how to get it to run compiled, or throw lots of computing power at the problem.  In your particular case your problem will likely allow for only some optimization via smarter algorithms, so if you really need this to go fast you may have to start looking at options 2 & 3.


Dynamic programming solution for cross river algorithm Working on below cross river problem, and post my code in Python 2.7 using dynamic programming. Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated.

More specifically, my idea is,

build a DP array to represent if we can reach a location by a certain speed;
when checking whether we are reach a certain location by a certain speed, we check if we can reach (1) location - speed with speed, (2) location - speed with speed + 1, (3) location - speed with speed - 1, if any (1), (2) or (3) is true, it means we can reach a certain location with such specific speed;
For the last location, if could be reached by any speed, return True

Problem,

Given a string representation of the rocks in the river e.g. "*****  *   * * *  *  *", determine whether the river is crossable. Where,

* = landable
  = cannot land there

Suppose Initial location: 0 and Initial speed: 0

in each step:
    1. choose a new speed from {speed, speed + 1, speed - 1} (but not negative)
    2. move speed spaces: loc += speed
    3. if I land on water, I fail
    4. if I land past end of river, I win
    5. otherwise, keep going

For example, below river could be crossed by the first method. So, it should return True.

X~~~~~~~~~~~~~~~~~~~~~_______($)
*****  *   * * *  *  *
011 2  3   4   4  3  3   4 (crossed)
01 2 2 (failed)
01111 2 (failed)

Source code in Python 2.7,

from collections import defaultdict
def can_cross_river(river):
    # key: (location, speed) tuple,
    # value: True or False for whether reachable at a specific location
    # with a specific speed
    dp = defaultdict(lambda : False)
    dp[(0,0)] = True
    for i in range(1, len(river)):
        if river[i] != '*':
            continue
        for speed in range(0,i+1):
            if dp[(i-speed, speed)] or dp[(i-speed, speed-1)] or dp[(i-speed, speed+1)]:
                dp[(i, speed)]= True
                if i == len(river) - 1: # reach end of river at any speed is fine
                    return True
    return False

if __name__ == "__main__":
    river = "*****  *   * * *  *  *" # should return True
    #river = "* *" # should return False
    print can_cross_river(river)

You have a small bug. Consider a river like ******.. such that the last spot is not landable. You can still cross the river by jumping beyond the end of the river from the last landable stone, but your code thinks that you cannot.

The solution to this is to do a top down DP. Define dp(position, speed) to be true if you can cross the river starting from position with given speed. You want to find dp(0,0), which you can do easily with memoised recursion.


Fisher-Yates Shuffle This is a cut-and-dried Fisher-Yates implementation. As not typically a JS developer, I've tried to incorporate as many best practices as I can. I would appreciate any input as to make it conform to more best practices and continue to be maintainable.

(function fisherYates () {

    "use strict";

    var shuffle = function shuffle (array) {

        var beginningIndex = 0,
            currentIndex = array.length,
            indexDecrement = 1,
            randomIndex = 0,
            temporaryValue = 0;

        // While elements remain to be shuffled...
        while (currentIndex !== beginningIndex) {

            // Pick an element from the remaining elements...
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex -= indexDecrement;

            // Swap it with the current element.
            temporaryValue = array[currentIndex];
            array[currentIndex] = array[randomIndex];
            array[randomIndex] = temporaryValue;

        }

        return array;

    };

    return shuffle;

}());

The docs on "use strict" are vague but I'm not entirely sure putting it inside a function makes it apply to the function definition.
var shuffle = function shuffle (array) { seems unnecessarily redundant. I would just use function shuffle (array) {
Use const and let instead of var (unless you're trying to support older browsers)
It doesn't make sense to initialize randomIndex or temporaryValue.
I would write while (currentIndex > beginningIndex) { especially if the indexDecrement could be something other than 1. Actually I would prefer a for loop though its arguable given the way your loop is structured.
I would use destructuring assignment to swap values:

[ array[currentIndex], array[randomIndex] ] = [ array[randomIndex], array[currentIndex] ];

If you use const or let you can move the definition of randomIndex and temporaryValue inside the loop block.
You return the shuffle function but your IIFE doesn't assign it anywhere. Apart from the fact that this seems unnecessarily complex I wonder if this even works?


Implement MyQueue using two stacks I am taking a helper stack, which is used during dequeue. Kindly suggest improvement or some solution with less complexity.

import java.util.ArrayDeque;
import java.util.Deque;

public class MyQueueUsingTwoStack {

    Deque<Integer> mainStack = new ArrayDeque<>();
    Deque<Integer> helperStack = new ArrayDeque<>();

    public void enqueue(int x) {
        mainStack.push(x);
    }

    //popping up all the object from mainStack to helper stack(except the last one) and then putting all object
    //from helper stack to mainStack
    public int dequeue() {
        while(!mainStack.isEmpty()) {
            helperStack.push(mainStack.pop());
        }

        int pop = helperStack.pop();

        while(!helperStack.isEmpty()) {
            mainStack.push(helperStack.poll());
        }

        return pop;

    }

    public boolean isEmpty() {
        return mainStack.isEmpty();
    }

}

In dequeue, you do this:

pop everything from main and push to helper
pop one from helper
pop everything from helper and push to main

Basically moving all elements, twice.

You can do better:

if helper is empty: pop everything from main and push to helper
pop one from helper

This will significantly reduce the number of times elements are moved.

Don't forget to adjust isEmpty accordingly.


Use of Model and View (MVC) I have an application using c# and MVC5, with RazorEngine.

My application manages requests (orders from clients) and I need to show them in tables. To achieve this I have a Controller (HistoryController), a View (Index) and a Model (MaterialRequestModel) which takes several parameters in the constructor:

 public MaterialRequestModel(MaterialRequest order, Employee aConcernedEmployee, Employee anOrderedbyEmployee, Office anOffice)

In my controller, HistoryController I have the followin Index method, which gets all requests completed or canceled:

public ActionResult Index()
        {
            IQueryable<MaterialRequest> query= DB.MaterialRequest
                .Where(m => m.MaterialStatusId == MatStatus.A9Cancelled || m.MaterialStatusId == MatStatus.A8Complete);

            List<MaterialRequestModel> model= new List<MaterialRequestModel>();
            foreach (MaterialRequest req in query)
            {
                model.Add(new MaterialRequestModel(req, DB.Employees.Find(req.ConcernedEmployeeId), DB.Employees.Find(req.OrderedByEmployeeId), DB.Offices.Find(req.OfficeId)));
            }
            return View(model);
        }

Now, I could simply pass the query to the the View, but that is not a good practice and the community (this one!) strongly suggests I use Models to avoid placing logic into the view.

However, I can't help to think that the way I am building my model sucks terribly bad, because I am iterating over a large set of results.

How can I improve this code and make it decent without the loop?

Additionally, should I pass everything as a parameter to my model, or should I just pass the DB object into the Models contructor and have it do the quereies there?

You can for sure replace this loop by using Select()

public ActionResult Index()
{
    IEnumerable<MaterialRequestModel> model= DB.MaterialRequest
        .Where(m => m.MaterialStatusId == MatStatus.A9Cancelled || m.MaterialStatusId == MatStatus.A8Complete)
        .Select(r => new MaterialRequestModel(r, DB.Employees.Find(r.ConcernedEmployeeId), DB.Employees.Find(r.OrderedByEmployeeId), DB.Offices.Find(r.OfficeId)));
    return View(query.ToList());
}

or much cleaner by a separate method

public ActionResult Index()
{
    IEnumerable<MaterialRequestModel> model= DB.MaterialRequest
        .Where(m => m.MaterialStatusId == MatStatus.A9Cancelled || m.MaterialStatusId == MatStatus.A8Complete)
        .Select(r => CreateMaterialRequestModel(r));
    return View(query.ToList());
}

private MaterialRequestModel CreateMaterialRequestModel(MaterialRequest materialRequest)
{
    return new MaterialRequestModel(r, DB.Employees.Find(r.ConcernedEmployeeId), DB.Employees.Find(r.OrderedByEmployeeId), DB.Offices.Find(r.OfficeId));
}

which can be improved further by caching the employee and office in a dictionary.

private Dictionary<int, Employee> cachedEmployees = Dictionary<int, Employee>();
private Employee GetEmployeeById(Int id)
{
    Employee employee;
    if cachedEmployees.TryGetValue(id, out employee)
    {
        return employee;
    }
    employee = DB.Employees.Find(id);
    if(employee != null)
    {
        cachedEmployees[id] = employee;
    }
    return employee;
}

in the same way the office cacheing can be done, which results CreateMaterialRequestModel()

private MaterialRequestModel CreateMaterialRequestModel(MaterialRequest materialRequest)
{
    return new MaterialRequestModel(r, GetEmployeeById(r.ConcernedEmployeeId), GetEmployeeById(r.OrderedByEmployeeId), GetOfficeById(r.OfficeId));
}

there is only a small problem. Any changes to an employee or an office won't be reflected in the dictionaries.


PDO connection via INI parser classes A few days ago I asked this question and I've got an answer to work with interfaces. I've tweaked around with this to get myself a INI parser class.

<?php

<?php

require "Parser.php";

class IniParser implements Parser
{

    private $data = [];

    /**
     * Parses the data from a configuration file and stores it into a array.
     *
     * @param $file string The file where the configuration / credentials / settings exist.
     * @param string $section The section within the configuration file, this is optional
     * @throws Exception
     */
    public function parse ($file, $section = "") {
        if (!$this->isValidated('file', $file)) {
            throw new Exception("File seems not to work..");
        }
        $credentials = parse_ini_file($file, true);
        foreach ($credentials as $key => $values) {
            if (!$this->isValidated('values', $credentials, $section)) {
                throw new Exception("Values or section doesn't exist");
            } elseif ($key !== $section) {
                continue;
            }
            $this->data = $values;
        }
    }

    /**
     * This function returns the value from a key inside a array.
     *
     * @param $key mixed Key of the array
     *
     * @throws Exception
     * @return mixed Value of the selected key by the parameter
     */
    public function get ($key) {
        if (!isset($this->data[$key])) {
            throw new Exception("Value doesn't exist in key: " . $key);
        }
        return $this->data[$key];
    }

    /**
     * @param $type
     * @param $data
     * @param string $section
     * @return bool
     *
     * note: when validating the values, were validating an array.
     */
    public function isValidated ($type, $data, $section = "") {
        switch ($type) {
            case "file":
                return file_exists($data) || is_file($data);
            case "values":
                //1. Check if $data is an array
                //2. Section is set
                return is_array($data) || isset($data[$section]);
        }
        return false;
    }
}

When calling the parse() method in this class you  get a specific .ini file (first argument) and parses the values within a specific section.

When calling the get() method in this class, you get the value of the chosen key.

This are the required methods for it:

<?php

interface Parser
{
    public function parse($file, $section);

    public function get($key);

}

For my connection, I use this class:

<?php
class Connection
{
    private $state;
    private $credentials;

    public function __construct(Parser $credentials) {
        $this->credentials = $credentials;
    }

    public function initialize() {
        if ($this->isInitialized()) {
            throw new PDOException("Database connection seems already to be open");
        }
        $this->state = new PDO($this->credentials->get('engine') . ":host=" . $this->credentials->get('host') . ";dbname=" . $this->credentials->get('dbname'), $this->credentials->get('username'), $this->credentials->get('password'));
    }

    public function terminate() {
        if (!$this->isInitialized()) {
            throw new PDOException("Connection doesn't seem to be open");
        }
        $this->state = null;
    }

    public function isInitialized() {
        return $this->state instanceof PDO;
    }
}

To create a new connection, I use this piece of code:

<?php
/**
 * User: Bas
 * Date: 6-10-2014
 * Time: 21:24
 */

require "INIParser.php";
require "Connection.php";

$credentials = new IniParser();
$credentials->parse("configuration.ini", "Connection");

try {
    $con = new Connection($credentials);
    $con->initialize();

} catch (Exception $e) {
    echo $e->getMessage();
}

Structure

Your IniParser should be the only part of your code that is aware of how the ini file looks internally. That's the whole point of the interface: With it, you can parse different kinds of files (or even retrieve the data from something else). If the file structure changes at some point, you should only ever have to change your IniParser class, nothing else.

But right now, that isn't the case. Your Connection also needs to know how your file looks. To fix this, I would add explicit getters instead of the generic getter you have right now. So you should add getEngine, getHost, etc to your class. This has the added benefit that you can validate them (see that they exist, etc) as soon as you parse the file, instead of when you are using the credentials.

Then of course your naming doesn't make that much sense anymore. So I would rename Parser to ICredentialsParser and IniParser to IniCredentialsParser.

You might also think about passing the names of keys to it as well instead of hardcoding them inside the parser.

If you do all this, your Connection class is decoupled from the ini file itself, and also, your IniParser gets more meaning (before, it was more or less only a wrapper for parse_ini_file).

parse and continue

If possible, I would avoid continue. In some cases it makes sense, but most of the time, it makes code harder to read. Your code could look like this:

        if (!$this->isValidated('values', $credentials, $section)) {
            throw new Exception("Values or section doesn't exist");
        } elseif ($key == $section) {
            $this->data = $values;
        }

Misc

your isValidated('values', $credentials, $section) call is inside a loop, but doesn't use the loop variables, so you should move it out of the loop.
I would create separate isValidated functions, as they don't share any common code (the way you do it just complicates things). You can name them isValidFile and hasSection.
naming: most of the time, I see open and close for the operations you are naming initialize and terminate. Your names are not bad, just unconventional. I would go with the general convention.
naming: isValidated would sound a bit better as isValid.
isValidated should probably be private.
in PHPDocs, it's always good to write why an exception is thrown.


SetOfStacks data structure The data structure question I was trying to solve is as follows:

  Stack of Plates:

  Imagine a (literal) stack of plates. If the stack gets too high, it
  might topple. Therefore, in real life, we would likely start a new
  stack when the previous stack exceeds some threshold. Implement a data
  structure SetOfStacks that mimics this. SetOfStacks should be
  composed of several stacks and should create a new stack once the
  previous one exceeds capacity. SetOfStacks.push() and
  SetOfStacks.pop() should behave identically to a single stack (that
  is, pop() should return the same values as it would if there were
  just a single stack).

I am trying to practice better data structure design, so I was looking for some feedback on my code as well as tips for going forward:

import java.util.*;

 public class StackOfPlates {

   public class StackNode {
     private int data;

     public StackNode(int d){
       data = d;
     }

     public int getData(){
       return data;
     }
   }

   List<ArrayList<StackNode>> setOfStacks;
   private int stackCapacity;

   public StackOfPlates(int c){
     setOfStacks = new ArrayList<ArrayList<StackNode>>();
     stackCapacity = c;
   }

   void push(int item){
     StackNode s = new StackNode(item);

     if(setOfStacks.isEmpty()){
       ArrayList<StackNode> st = new ArrayList<StackNode>();
       st.add(s);
       setOfStacks.add(st);
     }
     else{
       int index = setOfStacks.size() - 1;
       int currStackSize = setOfStacks.get(index).size();
       if(currStackSize == stackCapacity){
         ArrayList<StackNode> st = new ArrayList<StackNode>();
         st.add(s);
         setOfStacks.add(st);
         setOfStacks.get(index + 1).add(s);
       }
       else{
         setOfStacks.get(index).add(s);
       }
     }
   }

   StackNode pop(){
     int setOfStacksSize = setOfStacks.size();
     if(setOfStacksSize == 0) return null;

     ArrayList<StackNode> lastStack = setOfStacks.get(setOfStacksSize - 1);
     int lastElmtIndex = lastStack.size() - 1;
     StackNode end = lastStack.get(lastElmtIndex);
     lastStack.remove(lastElmtIndex);
     return end;
   }
 }

Good start! There are some things that can be simplified.

Reuse of Java classes

Java provides the very helpful class Deque which can behave like a stack. So you can reuse this for easier coding :). There is also a Stack class, but that one is synchronized.

StackNode

There is no real need for StackNode. Just use generics to store the specified item directly into the Stack/Deque. This also prevents pushing and int and popping a StackNode, which is inconsistent.

Split checking capacity, current stack to separate methods

For readability, I would try to split the handling of multiple stacks from popping and pushing, increasing readability. The push() only needs to know that there is room and pop() needs to clean up after getting the element from the stack.

Also, if there is a method of keeping track of the current stack, the logic for checking also becomes easier.

Something like this:

public void push( T item )
{
    //Make room if needed
    ensureRoom();

    //The current stack has enough room to push the item
    currentStack().push( item );
}

(note that this is not thread-safe)

Besides easier to read, it also becomes easier to refactor. For example, if you decide not to use Deque but Stack or your own implementation, it is easier to change.

Error handling

What happens when an empty SetOfStacks gets a pop()? You should throw a nice exception to make sure that both your SetOfStacks stays consistent and make use the caller gets a nice exception.

Variable names

int c and int d are not that great for passing on information about what the integer means. Is c capacity? And the initial capacity? Or the maximum capacity?

Access modifiers

Make sure to apply public, protected and private to make sure you only expose functionality that needs to be exposed, and keep private stuff private.

Proposed solution

public class StackOfPlates<T>
{
    private Deque<Deque<T>> setOfStacks;
    private int     maxStackCapacity;

    public StackOfPlates( int maxStackCapacity )
    {
        setOfStacks = new ArrayDeque<>();
        this.maxStackCapacity = maxStackCapacity;
    }

    public void push( T item )
    {
        //Make room if needed
        ensureRoom();

        //the current stack has enough room to push the item
        currentStack().push( item );
    }

    private void ensureRoom()
    {
        if( setOfStacks.isEmpty()  || currentStack().size() == maxStackCapacity);
        {
            Deque<T> newStack = new ArrayDeque<T>();
            setOfStacks.add( newStack );
        }
    }

    private Deque<T> currentStack()
    {
        return setOfStacks.peek();
    }

    public T pop()
    {
        if (setOfStacks.isEmpty())
        {
            throw new NoSuchElementException();
        }

        //Remove top element of last sack
        T elem = currentStack().pop();

        //And remove the last stack if it is emty
        maybeRemoveLastStack();

        return elem;
    }

    private void maybeRemoveLastStack()
    {
        if (currentStack().isEmpty())
        {
            //remove empty stack
            setOfStacks.pop();
        }
    }

}


Permutations of any given numbers I have solved one programming problem where we have to find all the permutations of given numbers.

For example, \$[1,2,3]\$ have the following permutations:

$$[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]$$

I have written the code for it and my code successfully cleared all the tests. But, I am not really sure about its complexity.

public List<List<Integer>> permute(int[] num) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    res.add(new ArrayList<Integer>()); // Add an empty list
    for(int number = 0; number < num.length; number++)
    {
        List<List<Integer>> curr = new ArrayList<List<Integer>>();
        for(List<Integer> nestedL : res)
        {
            for(int j = 0; j < nestedL.size() + 1 ;j++)
            {
                nestedL.add(j,num[number]);
                List<Integer> temp = new ArrayList(nestedL);
                curr.add(temp);
                nestedL.remove(j);
            }
        }
        res = new ArrayList<List<Integer>>(curr);
    }

   return res;
}

First, look at the algorithm, which suggests that it is a \$O(n^3)\$. But, I am not sure if it it correct. Would somebody like to throw more light on the complexity of this algorithm?

public List<List<Integer>> permute(int[] num) {

I'd call num, numbers.  In fact, I try to always name collections with a plural.  Also, I write names out rather than abbreviate them.  It will make things much easier if you ever have to read the code in the future.

List<List<Integer>> res=new ArrayList<List<Integer>>();

It would be helpful here to explain why res is a list of lists.  Why not just a single list?  Maybe this would be obvious to me if you came up with a more descriptive name.  I'm guessing that res is short for result.  I would have probably named it permutations.

res.add(new ArrayList<Integer>()); // Add an empty list

When commenting, try to say why you are doing things rather than what you are doing.  E.g.  // Add an empty list so that the middle for loop runs.

This seems odd though.  You pass in an int[].  Why not make a list of integer arrays then?  If that makes something not work, comment on it so that you don't regress it later.

    for(List<Integer> nestedL : res)
    {

Note that res can contain all the permutations (of which there are \$n!\$).  This is what gives you your \$O(n!)\$ time.  Note that it's actually \$O(n^3n!)\$ time, but the \$n!\$ eats the \$n^3\$.

        for(int j = 0; j < nestedL.size() + 1 ;j++)

This would be better if you pulled the nestedL.size() + 1 out of the comparison.

        for(int j = 0, n = nestedL.size() + 1; j < n ; j++)

It seems like you should be able to do a bit better here.  There's a lot of list creation and copying, which seems unnecessary.

            nestedL.add(j,num[number]);
            List<Integer> temp = new ArrayList(nestedL);
            curr.add(temp);
            nestedL.remove(j);

Ok, you add an element to a list; then you copy the list; save the copy; finally, you remove the added element from the original list.  Why not reorder things like so

            List<Integer> temp = new ArrayList(nestedL);
            temp.add(j, num[number]);
            curr.add(temp);

That saves a remove operation.

This also highlights a problem with the name number.  It's not a number from the num array.  It's an index to the array.  I'd name it either i or index.

public List<List<Integer>> permute(int[] numbers) {
    // we use a list of lists rather than a list of arrays
    // because lists support adding in the middle
    // and track current length
    List<List<Integer>> permutations = new ArrayList<List<Integer>>();
    // Add an empty list so that the middle for loop runs
    permutations.add(new ArrayList<Integer>());

    for ( int i = 0; i < numbers.length; i++ ) {
        // create a temporary container to hold the new permutations
        // while we iterate over the old ones
        List<List<Integer>> current = new ArrayList<List<Integer>>();
        for ( List<Integer> permutation : permutations ) {
            for ( int j = 0, n = permutation.size() + 1; j < n; j++ ) {
                List<Integer> temp = new ArrayList<Integer>(permutation);
                temp.add(j, numbers[i]);
                current.add(temp);
            }
        }
        permutations = new ArrayList<List<Integer>>(current);
    }

    return permutations;
}


Calculate the sum over a list of minima of two vectors I have the following metric:

def d(x, y):
    """The metric."""
    return 1 - sum(min(xi, yi) for xi, yi in zip(x, y))

where x and y are numpy arrays of equal length (~3000). I know that the elements of x and the elements of y each sum up to 1 and are non-negative.

Can this be calculated faster?

Minimum calculation could be vectorized:

import numpy as np

def f(x, y):
    return 1 - np.minimum(x, y).sum()


Null checking a generic type Assuming I have a method with this signature

public void DoStuffWith<T>(T foo)

and I want to allow both structs and classes to be passed as T, I was wondering about how to best do the null-checking in case T is a class.

I came up with following two approaches:

1. Checking whether T is a struct or a class at runtime:

public void DoStuffWith<T>(T foo)
{
    if(!typeof(T).IsValueType && foo == null)
    {
        throw new ArgumentNullException(nameof(foo));
    }

    ...
}

2. Having two overloads with generic type constraints:

public void DoStuffWithStruct<T>(T foo) where T : struct
{
    ...
}

public void DoStuffWithClass<T>(T foo) where T : class
{
    if(foo == null)
    {
        throw new ArgumentNullException(nameof(foo));
    }

    ...
}

However, I dislike both approaches. I don't like the runtime type-checking at #1 and I don't like having multiple, differently named overloads at #2.

Which of the approaches do you suggest or do you think I should maybe consider a totally different approach altogether?

I appreciate any feedback.

If you try the following :

class Program
{
    static void Main(string[] args)
    {
        Foo<string>(null);
        Foo<string>("asd");
        Foo<int>(1);
        Console.ReadKey();
    }

    public static void Foo<T>(T test)
    {
        if(test == null)
        {
            Console.WriteLine("ho ho it's null");
            return;
        }

        Console.WriteLine(test.GetType());
    }
}

You will realize that both the options are, excuse me, useless. The language already supports this behavior and if T is a struct, test == null will simply return false all the time.


Making a conditionally visible page-up button I wanted to make a button that goes to the top of the page but only appears when you're not at the top. There are probably libraries that already do this, but I wanted to make it myself and after some tinkering the following is what I came up with.

There is an occasional annoyance from quickly scrolling up & down with the mouse-wheel which causes jitters/unwanted permanence of the button @ top, but otherwise it works.

setInterval is throttled in consideration for performance. I really get the feeling this could be improved, so I wondered if there is a more idiomatic/better way. What do you think?

var scrollVisible = false;
var userScrolled = false;

window.addEventListener('load', init, false);

function init() {
 window.addEventListener('scroll', function() {
  userScrolled = true;
 }, false);

 setInterval(function() {
     if(userScrolled) {
      if (window.pageYOffset == 0 && scrollVisible) {
       document.getElementById("scrollbutton").style.visibility = 'hidden';
       scrollVisible = false;
      } else if (!scrollVisible) {
       document.getElementById("scrollbutton").style.visibility = 'visible';
       scrollVisible = true;
      }
         userScrolled = false;
     }
 }, 100);
}

function scrollUp() {
 scrollTo(0, 0);
}
body {
 background-color: #272822;
 color: #F3F3F3;
}

#scrollbutton {
 background-color: #666664;
 border-radius: 100%;
 position: fixed;
 visibility: hidden;
 font-size: 1.5em;
    bottom: 0;
    right: 0;
}
#scrollbutton:hover {
 color: #A6E22E;
}
<!DOCTYPE html>

 <link rel="stylesheet" type="text/css" href="test.css"/>

<input type="button" value="&#8679" id="scrollbutton" onclick="scrollUp();"/>

Lorem Ipsum is simply dummy text of the printing and typesetting industry.
Lorem Ipsum has been the industry's standard dummy text ever since the 1500s.

 Contrary to popular belief, Lorem Ipsum is not simply random text.
    It has roots in a piece of classical Latin literature.

I doubt that you need the throttling.  Modern browser make a lot of decisions in response to events; this code is rather insignificant.

If anything, having a continuously ticking timer is counterproductive, especially on mobile devices.  I'd rather have a flurry of activity during the brief periods when scrolling is happening, and no activity at all when idle.

I would recommend toggling the visibility of the button more indirectly, using CSS.  Add or remove an scrolled-down class on the body element depending on whether the document is scrolled down.  Let the cascading rules take care of the rest.

function noteScrollPosition() {
    if ((window.pageYOffset == 0) != (document.body.className.indexOf('scrolled-down') < 0)) {
        if (window.pageYOffset == 0) {
            document.body.className = document.body.className.replace(/ *scrolled-down/, '');
        } else {
            document.body.className += 'scrolled-down';
        }
    }
}
window.addEventListener('load', noteScrollPosition, false);
window.addEventListener('scroll', noteScrollPosition, false);

function scrollUp() {
    scrollTo(0, 0);
}
body {
 background-color: #272822;
 color: #F3F3F3;
}

#scrollbutton {
 background-color: #666664;
 border-radius: 100%;
 position: fixed;
 font-size: 1.5em;
 bottom: 0;
 right: 0;
 visibility: hidden;
}
body.scrolled-down #scrollbutton {
 visibility: visible;
}
#scrollbutton:hover {
 color: #A6E22E;
}
<!DOCTYPE html>

 <link rel="stylesheet" type="text/css" href="test.css"/>

<input type="button" value="&#8679" id="scrollbutton" onclick="scrollUp();"/>

Lorem Ipsum is simply dummy text of the printing and typesetting industry.
Lorem Ipsum has been the industry's standard dummy text ever since the 1500s.

 Contrary to popular belief, Lorem Ipsum is not simply random text.
    It has roots in a piece of classical Latin literature.


Most elegant variadic functor Question

  Suppose we have two sorts of classes

  an input class Input

  defines a type result_type
  defines set(result_type)

  an output class Output

  defines a type result_type
  defines result_type get() const
  has a number of Input classes as member variables, on which its output depends

  Given an output class and several input classes (arbitrary number),
  consider the following procedure:

  loop over each input class and call set() with an appropriate value (defined beforehand)
  call the get() on the ouput class and collect the result.

  This procedure can be seen as a call to a function taking the input's
  values as arguments an returning the output value.

  Write the functor that constructs such a variadic function in the general case.

  Constraints are: C++ (most likely C++11), arbitrary number of input
  classes of possibly different Input::result_types. Note that
  Input::result_type is not necessarily related to
  Output::result_type. Aim should first be efficiency, but there's a
  big bonus if the code is elegant and readable.

  Details: For those who wonder how Output is related to Input, one could imagine that Input has a result_type get() const method
  as well, which returns whatever you provided via set(). Output
  then has a constructor that takes various Inputs, and stores them
  (or their reference) as member variables. Output::get() then does
  some math by using the return values of its input's get() methods,
  and returns some result of type Output::result_type.

Proposed solution

#include <functional>

template <class Output, class... Inputs>
std::function<typename Output::result_type(typename Inputs::result_type...)>
make_function(const Output& output, Inputs&... inputs) {
  return[&](typename Inputs::result_type... input_vals) {
    int dummy[]{0, (inputs.set(input_vals),0)...};
    return output.get();
  };
}

The int dummy[] line is due to @ecatmur's answer.

Looks to me as if you've already got the most elegant solution in mind.

In C++14 you'd remove the dependency on std::function and simply return a naked lambda, like this:

template <class Output, class... Inputs>
auto make_function(const Output& output, Inputs&... inputs) {
  return [&](typename Inputs::result_type... input_vals) {
    int dummy[] { 0, ((void)inputs.set(input_vals),0)... };
    return output.get();
  };
}

but in C++11 you can't make a function-that-returns-a-naked-lambda without a ton of boilerplate — if it's even possible at all.

Also, a nitpick, with props to @stephan-t-lavavej's talk at CppCon 2014. You wrote

(inputs.set(input_vals),0)...

but what you should have written was

((void)inputs.set(input_vals),0)...

to avoid accidentally calling MaliciousUserCode::operator,(int).


Return the anti-diagonals Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details.

Example:

Input:

1 2 3
4 5 6
7 8 9

Return the following :

[
  [1],
  [2, 4],
  [3, 5, 7],
  [6, 8],
  [9]
]

This is my approach to this question:

public class Solution {
    public ArrayList<ArrayList<Integer>> diagonal(ArrayList<ArrayList<Integer>> A) {

        //The total number of internal rows in the final list will be 2*noofrows(A) - 1
        int size = 2*A.get(0).size() - 1;
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        int count = 0;

        //Count of the number of rows
        int r = A.size();

        //Time complexity: O(size*r^2)
        //Space complexity: O(size)
        while( count < size)
            {
                ArrayList<Integer> temp = new ArrayList<>();
                for( int i = 0; i < r; i++ )
                {
                    for( int j = 0; j < r; j++ )
                        {
                            if( ((i + j) == count))
                                temp.add(A.get(i).get(j));

                            //Continue when the indices sum up to be > count
                            if((i + j) > count )
                                continue;
                        }
                }
                ans.add(temp);
                count++;
            }
        return ans;
    }

I have the following questions regarding my code:

1) Is there any better approach to solve this problem?

2) How can I improve my time and space complexity?

3) Are there any redundant steps that can be removed?

Reference

I figured out a solution that improves on time complexity:
So here's the thing: the solution is actually a rearrangement of the matrix, meaning O(r^2) should be possible: visit each cell of the matrix once, determinig its location in the solution.

and it's straightforward: find the heads of the anti-diagonals, and for each one, find all its members.
finding the heads: iterate over the first row, then (when you reached end of row) iterate over the last column.
for each cell in above mentioned iteration, start gathering anti-diagonal members by advancing one row down, one column left, until either one goes beyond matrix' bounds.

few notes on the posted code:

define the variables with interface types: List<List<Integer>> ans = new ArrayList<>(); this includes method arguments and return value.  This will allow you to change concrete implementation with minimal changes.
use short form if (without braces) judiciously. it makes the code less clear and is prone to errors. Some ppl will say do not use this at all.  when I use it, I put the condition and action in the same line:
if( ((i + j) == count)) temp.add(A.get(i).get(j));
I think in these types of questions, where input is known and does not change, arrays are bettter suited then Collections, since they offer more concise syntax: A[i][j] is more clear then A.get(i).get(j)
naming conventions: variables start with lower case.


Circular linked list in C Let me know if it seems right to you and if anything can be optimized. My concern is that I'm unsure if circular linked lists are supposed to have a tail. I've implemented it just using a head. Is that wrong? If so, how would you change it to make it proper?

/*
 * Circular Linked List
 *
 */

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void insert_beg_of_list(Node *current, int data);
void delete(Node *current, int data);
void print_list(Node *current);
int find_in_a_list(Node *current, int data);

void insert_beg_of_list(Node *current, int data) {
    //keep track of first node
    Node *head = current;

    while(current->next != head) {
        current = current->next;
    }
    current->next = (Node*)malloc(sizeof(Node));
    current = current->next;
    current->data = data;
    current->next = head;

}

void delete_from_list(Node *current, int data) {

    Node *head = current;
    while(current->next != head && (current->next)->data != data) {
        current = current->next;
    }
    if(current->next == head) {
        printf("%d element is not found\n\n", data);
        return;
    }
    Node *tmp;
    tmp = current->next;
    current->next = tmp->next;
    free(tmp);
    return;
}

void print_list(Node *current) {

    Node *head = current;
    current = current->next;
    while(current != head){
        printf(" %d ", current->data);
        current = current->next;
    }

}

int find_in_a_list(Node *current, int data) {

    Node *head = current;
    current = current->next;
    while(current != head) {
        if(current->data == data) {
            // Key found
            return 1;
        }
        current = current->next;
    }
    // Key is not found
    return 0;
}

int main() {

    Node *head = (Node *)malloc(sizeof(Node));
    head->next = head;

    int data = 0;
    int usr_input = 0;

    while(1){
        printf("0. Exit\n");
        printf("1. Insert\n");
        printf("2. Delete\n");
        printf("3. Print\n");
        printf("4. Find\n");

        scanf("%d", &usr_input);

        // can also use a switch instead
        if( usr_input == 0) {
            exit(0);

        } else if(usr_input == 1) {
            printf("\nEnter an element you want to insert: ");
            scanf("%d", &data);
            insert_beg_of_list(head, data);

        } else if(usr_input == 2) {
            printf("\nEnter an element you want to delete: ");
            scanf("%d", &data);
            delete_from_list(head, data);

        } else if( usr_input == 3) {
            printf("The list is ");
            print_list(head);
            printf("\n\n");

        } else if( usr_input == 4) {
            printf("\nEnter an element you want to find: ");
            scanf("%d", &data);
            int is_found = find_in_a_list(head, data);
            if (is_found) {
                printf("\nElement is found\n\n");
            } else {
                printf("\nElement is NOT found\n\n");
            }
        }
    }
    return 0;
}

When making a collection of routines to handle a type, strongly advise to create a create and destroy function.   Rather then the below, consider some initialization function.

// Replace this code
Node *head = (Node *)malloc(sizeof(Node));
head->next = head;

// with this
Node *new_list(void ) {
  Node *head = malloc(sizeof *head);
  if (head) {
    head->next = head;
  }
  return head;
}
...
Node *head = new_list();

The names on the functions benefit by having the leading text indicate the grouping.   Avoid function delete() - too generic.

void clist_insert_beg(Node *current, int data);
void clist_delete(Node *current, int data);
void clist_print(Node *current);
int clist_find(Node *current, int data);

Consider 4 operations: Add_Before_First(), Remove_First(), Append(), Remove_End().   A circular list means it is relatively easy (O(1)) to do something at both ends of the list.   This code's delete_from_list() is nothing more that a typical linked list would do and take O(n) time.  Sadly even the insert_beg_of_list() also takes O(n) time.  Recommend to re-work this code so at least 1 of 2 "head" functions and at least 1 of the "tail" functions can operate in O(1) time  (no while loops).
Having a circular list with only a single pointer is do-able and perform 3 of the above 4 in O(1) time.  Consider a list that points to the tail.  No need for a head pointer as tail->next is the head.
Recommend a simpler to code and maintain allocation style.  The cast is not needed and the sizeof works even is the type of *(current->next) changes.

// current->next = (Node*)malloc(sizeof(Node));
current->next = malloc(sizeof *(current->next));

Though posted as 1 file, better to post as a circular_list.c, circular_list.h, main_sample_usage.c files to clearly identify that which is public and private.
I have doubts delete_from_list() works when the last element is deleted.  I think that is because of the overall design.  IMO, when a list contains no data, it should consume minimal space.  IOW, a NULL pointer is an empty list.  When a list type is used heavily, there are often many empty lists.  So an empty list of a pointer to a node pointing to itself seems wasteful.
Functions that do not modify the list should use const.

// int find_in_a_list(Node *current, int data) {
int find_in_a_list(const Node *current, int data) {

// void print_list(Node *current) {
void print_list(const Node *current) {

Hoping to find functions like

unsigned count_list(const Node *current);
bool empty_list(const Node *current);

Minor Use int main(void) {


Alternative implementation of isType() Detecting types in JavaScript sucks

This answer discusses the standard way to check the type of a JavaScript object (specifically, an array):

  The method given in the ECMAScript standard to find the class of
  Object is to use the toString method from Object.prototype.

if( Object.prototype.toString.call( someVar ) === '[object Array]' ) {
    alert( 'Array!' ); }

Why abuse Object.prototype.toString? It turns out that objects created in different frames have different constructors.

typeof only works for objects which are (or have equivalent) primitives, like strings.

Another way?

The above code makes me feel funny inside, and doesn’t have a chance of working for custom types, so I wrote this [Gist]:

function isType(object, type){
     return object != null && type ? object.constructor.name === type.name : object === type;
}

You use it like this:

isType([1, 2, 3], Array);
isType(null, null);
isType('foo', String);

mauke on ##javascript points out that it fails for objects whose constructors have the same name as the type you're testing against:

isType(new (function String(){}), String);

I think I like this behavior more than calling every custom type an Object.

To take it one step further

jQuery has a 25-line isPlainObject to tell if something is a plain object ({ foo: 'bar' }).

In what cases does the jQuery version behave more-correctly than…

isType(thing, Object);

?

Disclaimer: I haven’t tested this code in a bunch of cases or in a bunch of browsers. The experience concentrated into the jQuery source could blow me back to preschool.

I could not find anything wrong with your code,
so per Meta I am going to tell you why it is awesome ;)

Checking .toString() is icky, toString() could easily be replaced/enhanced
Your solution works across frames
I was not able to break it.

On a final note, it seems to me that needing to verify the type of an object ( besides assertions ) means you are doing something odd and probably the code should be re-thought.

Still, I am favouriting this question.

UPDATE : Turns out that according to jsperf, your solution is much slower :\


Python implementation for contains pattern in text This is an implementation of contains, which returns a boolean indicating whether a pattern occurs in text.

I encountered this question while I was implementing find_all_index. For example, contains('abc', 'b') returns True and contains('abc', 'c') returns True.

I ran the following unit test cases, and it passed against all test cases, so the code seems to be working fine.

Implementation

Test

def contains(text, pattern):
    assert isinstance(text, str), 'text is not a string: {}'.format(text)
    assert isinstance(pattern, str), 'pattern is not a string: {}'.format(text)

    """create a pattern variable name """
    pattern = list(pattern)
    p_len = len(pattern)

    clean_text = list(filter(str.isalnum, text))
    t_len = len(clean_text)

    print("Searching contains")
    for i in range(t_len):
        # If the first letter matches, check the rest of string
        if clean_text[i] == pattern[0]:

            for j in range(p_len):
                if i+j >= t_len:
                    return False
                if pattern[j] != clean_text[i+j]:
                    break
                if j == p_len-1:
                    return True

    return False

def test_string_algorithms(text, pattern):
    found = contains(text, pattern)
    print('contains({!r}, {!r}) => {}'.format(text, pattern, found))

def main():
    test_string_algorithms(text, pattern)

if __name__ == '__main__':
    main()

PEP8 and readability

You have a few great docstrings, there is no need for block-comments and docstrings.
In contains you have this assert isinstance(text, str) but don't use it.

Code changes

Your contains(text, pattern) could be a lot more simplified. Because contains checks whether a pattern occurs in text and returns a boolean indicating .

def contains(text, pattern):
    """Return a boolean indicating whether pattern occurs in text."""
    # If our pattern index is equal to our pattern length
    # then we found a match and we can return True
    # If our current text character is not our pattern character
    # and if we were checking for a pattern
    # If we have not found our pattern then we return False

    text_index = 0
    pattern_index = 0

    text_length = len(text)
    pattern_length = len(pattern)

    while text_index < text_length:
        if text[text_index] == pattern[pattern_index]:
            pattern_index += 1
        elif pattern_index > 0:
            pattern_index = 0
            continue
        if pattern_index + 1 > pattern_length:
            return True
        text_index += 1
    return False


JavaScript multiple ajax calls but can either be one or two I'm writing a piece of JavaScript to make one or two ajax calls. There will always be one ajax call fired but it might be two based on cookie setting. If user is logged in then we call another service to get the data. I would want this to fire async that's why I didn't put the second ajax call in the callback of the first call. We don't use jQuery just vanilla JS.

'use strict';

import Cookie from 'js-cookie';
const _ = require('../helpers');

module.exports = function(cb) {
  let number_of_calls = 1;
  window._g = window._g || {};

  const uid = Cookie.get('uid');
  if (uid) {
    number_of_calls += 1;
  }

  function setG(fds) {
    --number_of_calls;
    const out = JSON.parse(fds);
    window._g.context = out;

    if (number_of_calls === 0) {
      cb({});
    }
  };

  function setUser(user) {
    --number_of_calls;
    const out = JSON.parse(user);
    window._g.user = out;
    if (number_of_calls === 0) {
      cb({});
    }
  }

  _.ajax({url: '//some_service/content?url=' + _.url}).done(setG);

  if (uid) {
    _.ajax({url: '//another_service/user?uid=' + uid}).done(setUser);
  }
};

As mentioned in the comments, JS uses camelCase. Even if your team suggests to use snake_case consistently, JavaScript APIs are all in camelCase making your code look weird and out of place.

'use strict';

import Cookie from 'js-cookie';
const _ = require('../helpers');

Be consistent and use one module system. Suggesting you stick to the ES6 syntax as it is the standard.

Also, ES6 modules are in strict mode by default. This means the 'use strict'; pragma is unnecessary. If you're using a bundler that follows standards, it should be putting the pragma for you so you don't have to. If it doesn't put it for you, use a better bundler.

import Cookie from 'js-cookie';
const _ = require('../helpers');
module.exports = function(cb) {...}

Since I recommend writing ES6, then this should now be

import Cookie from 'js-cookie';
import _ from '../helpers';

export default function(cb){...}

_ and cb are not good names. Give them a full name, like Helpers and callback, respectively. "Lesser keystrokes" is not a good excuse. It's not worth the hassle debugging and you'll only lose hair faster.

Also, I would suggest ditching the callback pattern in favor of returning Promises. It will still look like callbacks when used, but it provides better control flow than callbacks.

window._g = window._g || {};

If  windows._g is just a temporary storage for your function's results, then as mentioned earlier, use promises. With promises, you can retrieve and pass on results from async operations without ever needing a temporary variable to store the data. The promise holds the values for you.

  multiple ajax calls but can either be one or two

Assuming _.ajax is not jQuery.ajax and the fact that you're using a done and not then, then _.ajax might not be returning promise-like objects. I suggest you do return a promise for _.ajax because what you're essentially doing is what Promise.all is for. It accepts multiple promises, and resolves when all are in. Good for multiple, parallel AJAX calls.

In the case of your second call, which is dependent on uid, you either return the _.ajax call promise or return a pre-resolved promise using Promise.resolve.

If I were to rewrite this module, it would look like this:

// getSessionData.js

import Cookie from 'js-cookie';
import Helpers from '../helpers';

export default function(){

  // Execute both requests. However, if `uid` isn't present, `userDataRequest`
  // will immediately be a resolved promise instead of a promise of an ajax call.
  const contextRequest = Helpers.ajax({});
  const userDataRequest = Cookie.get('uid') ? Helpers.ajax({}) : Promise.resolve({});

  // Wait for both promises to resolve. If `userDataRequest` is the pre-resolved
  // promise, then we'll only be waiting for `contextRequest`.
  //
  // This will resolve to { context: {}, user: {} }
  return Promise.all([contextRequest, userDataRequest])
                .then(([context, user]) => { context, user });
}

// Usage

import getSessionData from './getSessionData';

const sessionData = getSessionData().then(sessionData => {
  // This serves as replacement to your "callback"

  const context = sessionData.context;

  // user can either be the result from the AJAX call or a blank object.
  const user = sessionData.user;

  // Do stuff with context and user
});


Proper way to cancel WebClient in BackgroundWorker I have a WPF application that needs to get a XML document using a web request. The request is based on an id that the user enters. If the user enters a second id, before the first returns, I would like to cancel the first request, and start over with the second id. The following works, but I'm not sure if there is an easier way, or if this is correct. I am basically passing a ManualResetEvent reset event to a BackgroundWorker so that I can signal the thread to cancel the web request.

Is this approach poor form? Is passing in a reset event better than having a loop within the function that tests the DoWorkEventArgs::Cancel property every tenth of a second? Also, is there a way to delay the call to RunWorkerAsync until the background worker isn't busy, without blocking the thread? Or should I just create a new background worker every time?

Any input is much appreciated.

This is what I have in my window.xaml.cs.

    BackgroundWorker itemBackgroundWorker = new BackgroundWorker();
ManualResetEvent itemCancel = new ManualResetEvent(false);
private void tbID_TextChanged(object sender, TextChangedEventArgs e)
{
    int id;
    if (!int.TryParse(textBoxID.Text, out id))
        return;

    while (itemBackgroundWorker.IsBusy)
    {
        itemCancel.Set();
    }

    itemCancel.Reset();
    itemBackgroundWorker.RunWorkerAsync(new object[] { id, itemCancel });

}
void baselineSessionBackgroundWorker_DoWork(object sender, System.ComponentModel.DoWorkEventArgs e)
{
    Object[] args = (Object[])e.Argument;

    int id = (int)args[0];
    ManualResetEvent cancel = (ManualResetEvent)args[1];
    try
    {
        currentItem = webFunctions.getItem(id, cancel);
    }
    catch (Exception exx)
    {
        System.Diagnostics.Debug.WriteLine("Find run {0} failed with {1}", id, exx.Message);
        currentItem = null;
    }
}
void baselineSessionBackgroundWorker_RunWorkerCompleted(object sender, System.ComponentModel.RunWorkerCompletedEventArgs e)
{
    currentItemContentControl.GetBindingExpression(ContentControl.ContentProperty).UpdateTarget();
}

This is what I have for the static getItem method.

static string detailXMLQuery = "http://....";
public static myItem getItem(int id, ManualResetEvent cancelEvent = null)
{
    ManualResetEvent readFinishedEvent = new ManualResetEvent(false);
    if (cancelEvent == null)
        cancelEvent = new ManualResetEvent(true);
    else
        cancelEvent.Reset();

    Stream result = null;
    WebClient client = new WebClient();
    client.OpenReadCompleted += delegate(object sender, OpenReadCompletedEventArgs e)
    {
        if (e.Error != null)
            System.Diagnostics.Debug.WriteLine("Error getting XML:" + e.Error.Message);
        else
            result = e.Result;

        System.Diagnostics.Debug.WriteLine("Set finished state");
        readFinishedEvent.Set();
    };
    client.OpenReadAsync(new Uri(string.Format(detailXMLQuery, id)));

    ManualResetEvent.WaitAny(new WaitHandle[] { cancelEvent, readFinishedEvent }, 10000);

    if (!readFinishedEvent.WaitOne(0))
    {
        client.CancelAsync();
        System.Diagnostics.Debug.WriteLine("Error getting XML: The request timed out or was canceled");
        throw new Exception("The request timed out or was canceled");
    }

    XmlDocument doc = new XmlDocument();
    doc.Load(result);

    //parse xml, test cancelEvent.Wait(0) to see if cancel has been signaled.

    return new myItem();
}

Is this approach poor form?

I think yes

  Is passing in a reset event better than having a loop within the function that tests the DoWorkEventArgs::Cancel property every tenth of a second?

Both are wrong. Event is a kernel object! Using a kernel object for this type task is wasteful. It would be better if you used something like this:

webClient.DownloadStringCompleted += new DownloadStringCompletedEventHandler(DownloadStringCallback2);
client.DownloadStringAsync (uri);

In this case, you don't need to block any thread with a loop. When your request completes, you will take the control in passed method (DownloadStringCallback2).

  Also, is there a way to delay the call to RunWorkerAsync until the background worker isn't busy, without blocking the thread?

At first glance - yes, you can pass in worker method CancellationToken. When the user inputs a new value, you simply cancel the token and start a new task. When the cancelled request takes the control in DownloadStringCallback2 it should check the token and return. If it wasn't cancelled, it may continue work. On each user request you should simply cancel the old token and create a new one, then start a new request.

  Or should I just create a new background worker every time?

I think it's OK at first glance. On each user request create a new BackgroundWorker and pass the cancellation token. The BackgroundWorker will use ThreadPool behind the scenes anyway.


Fibonacci in linear time by using an extra pointer I have a function to find the nth number in a Fibonacci sequence, in which I am recursively calling the function. The sum is stored in a class variable and I have an extra pointer I increment every time the function gets called.

This extra pointer is the gate keeper which dictates the base case of when to exit from the loop. The performance I get, using this algorithm is, \$O(n)\$ linear time and with \$O(1)\$space.

I get the expected answer but I am confused if this an acceptable solution from a coding interview stand point.

var x = 0
var sum = 0
func myFibonacci(of n: Int, a: Int, b:Int) -> Int {
  x+=1
  if (x == n) {
    return sum
  } else {
    sum = a+b
    return myFibonacci(of: n, a: b, b: sum)
  }
}

let finalAns = myFibonacci(of: 9, a: 0, b: 1)
print("The nth number in Fibonacci sequence is \(finalAns)")

Output: 34

Time complexity: \$O(n)\$ linear time

Space complexity \$O(1)\$

Is this an acceptable solution for a coding interview?

Your function uses global variables, which is bad for several reasons:

The variables must be reset before the function can be called again.
The variables can be modified from outside of your function, causing
wrong results.
The function is not thread-safe.

In addition,

The program logic is not immediately obvious (at least it wasn't to me).
Calling the function with n <= 0 causes an integer overflow.

Global variables are often problematic, and
here they can be easily avoided, making the code not only safer,
but also simpler.

First, the global sum variable is elimitated by making
it local:

var x = 0
func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    x += 1
    if (x == n) {
        return b
    } else {
        let sum = a + b
        return myFibonacci(of: n, a: b, b: sum)
    }
}

or eliminate it completely:

var x = 0
func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    x += 1
    if (x == n) {
        return b
    } else {
        return myFibonacci(of: n, a: b, b: a + b)
    }
}

Now get rid of the global variable x by decrementing n instead
in the recursive call:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    if n == 1 {
        return b // Recursion terminates here
    }
    return myFibonacci(of: n - 1, a: b, b: a + b)
}

With a slight modification it works for n = 0 as well.
Negative arguments should be caught instead of recursing
repeatedly until an integer overflow occurs:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    precondition(n >= 0, "`n` must be non-negative")
    if n == 0 {
        return a // Recursion terminates here
    }
    return myFibonacci(of: n - 1, a: b, b: a + b)
}

This is what I would expect as a recursive implementation in a coding interview (of course you can also implement it iteratively,
or use a closed-form expression such as Binet's formula).

As a bonus, you can implement it for negative arguments as well,
compare Generalizations of Fibonacci numbers:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    if n == 0 {
        return a // Recursion terminates here
    } else if n > 0 {
        return myFibonacci(of: n - 1, a: b, b: a + b)
    } else {
        return myFibonacci(of: n + 1, a: b - a, b: a)
    }
}


Faster way to parse file to array, compare to array in second file, write final file I currently have an MGF file containing MS2 spectral data (QE_2706_229_sequest_high_conf.mgf). The file template is here, as well as a snippet of example:

BEGIN IONS
TITLE=File3249 Spectrum10594 scans: 11084
PEPMASS=499.59366 927079.3
CHARGE=3+
RTINSECONDS=1710
SCANS=11084
104.053180 3866.360000
110.071530 178805.000000
111.068610 1869.210000
111.074780 10738.600000
112.087240 13117.900000
113.071150 7148.790000
114.102690 4146.490000
115.086840 11835.600000
116.070850 6230.980000
... ...
END IONS

This unannotated spectral file contains thousands of these entries, the total file size is ~150 MB.
I then have a series of text files which I need to parse. Each file is similar to the format above, with the first column being read into a NumPy array. Then the unannotated spectra file is parsed for each entry until a matching array is found from the annotated text files input.

(Filename GRPGPVAGHHQMPR)

       m/z              i matches
 104.05318        3866.4
 110.07153      178805.4
 111.06861        1869.2
 111.07478       10738.6
 112.08724       13117.9
 113.07115        7148.8
 114.10269        4146.5
 115.08684       11835.6
 116.07085        6231.0

Once a match is found, an MGF annotated file is written that then contains the full entry information in the unannotated file, but with a line that specifies the filename of the annotated text file that matched that particular entry. The output is below:

BEGIN IONS
SEQ=GRPGPVAGHHQMPR
TITLE=File3249 Spectrum10594 scans: 11084
PEPMASS=499.59366 927079.3
... ...
END IONS

There may be a much more computationally inexpensive way to parse. Given 2,000 annotated files to search through, with the above large unannotated file, parsing currently takes ~ 12 hrs on a 2.6 GHz quad-core Intel Haswell CPU.

import numpy as np
import subprocess as sp
import sys
from pyteomics import mgf, auxiliary

def main():
    pep_files = []

    if (len(sys.argv) > 0):
        spec_in = sys.argv[1]
    else:
        print 'Not enough Command Line Arguments!'

    path = '/DeNovo/QE_2706_229_sequest_high_conf.mgf'
    print spec_in
    pep_files.append(spec_in)

    for ann_spectra in pep_files:
        seq = ann_spectra[:ann_spectra.find('-') - 1]
        print seq
        a = np.genfromtxt(ann_spectra, dtype=float, invalid_raise=False, usemask=False, filling_values=0.0, usecols=(0))
        b = np.delete(a, 0)

        entries = []

        with mgf.read(path) as reader:
            for spectrum in reader:
                if np.array_equal(b, spectrum['m/z array']):
                    entries.append(spectrum)
                    file_name = 'DeNovo/good_training_seq/{}.mgf'.format(ann_spectra[:-4])
                    with open(file_name, 'wb') as mgf_out:
                        for entry in entries:
                            mgf_out.write('BEGIN IONS')
                            mgf_out.write('\nSEQ={}'.format(seq))
                            mgf_out.write('\nTITLE={}'.format(entry['params']['title']))
                            mgf_out.write('\nPEPMASS={} {}'.format(entry['params']['pepmass'][0], entry['params']['pepmass'][1]))
                            mgf_out.write('\nCHARGE={}'.format(entry['params']['charge']))
                            mgf_out.write('\nRTINSECONDS={}'.format(str(entry['params']['rtinseconds'])))
                            mgf_out.write('\nSCANS={}'.format(entry['params']['scans']))
                            mgf_out.write('\n')
                            p = np.vstack([entry['m/z array'], entry['intensity array']])
                            output = p.T
                            np.savetxt(mgf_out, output, delimiter=' ', fmt='%f')
                            mgf_out.write('END IONS')

if __name__ == '__main__':
    main()

The Python script is used with command line arguments with the following bash script:

for f in *.txt ; do python2.7 mgf_parser.py "$f"; done

This was used to be able to only parse a given number of files at a time. Suggestions on any more efficient parsing methods?

Disclaimer : I have very limited skill/knowledge for anything related to np. Also, I haven't run your code to identify bottleneck which should be the very first thing to do before trying to perform optimisations.

Common ways to make things faster are :

not to do something if you don't need to.
not to do something multiple times if once is enough.

In the first category, your import subprocess as sp and from pyteomics import auxiliary are not required : you can get rid of this. This shouldn't change anything from a performance point of view but it's always good to make things easier.

In the second category, it seems like you could open filename once for each ann_spectra.
Also, for each entry, you could retrieve entry['params'] only once. Similarly, you could call mgf_out once.

This is the code I have at this stage :

def main():
    pep_files = []

    if (len(sys.argv) > 0):
        spec_in = sys.argv[1]
    else:
        print 'Not enough Command Line Arguments!'

    path = '/DeNovo/QE_2706_229_sequest_high_conf.mgf'
    print spec_in
    pep_files.append(spec_in)

    for ann_spectra in pep_files:
        seq = ann_spectra[:ann_spectra.find('-') - 1]
        print seq
        a = np.genfromtxt(ann_spectra, dtype=float, invalid_raise=False, usemask=False, filling_values=0.0, usecols=(0))
        b = np.delete(a, 0)

        entries = []
        file_name = 'DeNovo/good_training_seq/{}.mgf'.format(ann_spectra[:-4])
        with open(file_name, 'wb') as mgf_out, mgf.read(path) as reader:
            for spectrum in reader:
                if np.array_equal(b, spectrum['m/z array']):
                    entries.append(spectrum)
                    for entry in entries:
                        param = entry['params']
                        mgf_out.write('BEGIN IONS\nSEQ={}\nTITLE={}\nPEPMASS={} {}\nCHARGE={}\nRTINSECONDS={}\nSCANS={}\n').format(
                            seq,
                            param['title'],
                            param['pepmass'][0],
                            param['pepmass'][1],
                            param['charge'],
                            str(param['rtinseconds']),
                            param['scans'])
                        p = np.vstack([entry['m/z array'], entry['intensity array']])
                        output = p.T
                        np.savetxt(mgf_out, output, delimiter=' ', fmt='%f')
                        mgf_out.write('END IONS')

Now, I have realised something that I find quite confusing : you keep adding elements to entries and then you loop over it : it will loop once the first time, twice the second time, n times the n_th times. Is this something we really need/want to do ?

Finally, you are doing things in an un-usual way : you have pep_files = [], then pep_files.append(spec_in). This could easily be written pep_files = [spec_in]. Then, you do for ann_spectra in pep_files:, you might as well get rid of pep_files, ann_spectra and the loop and work directly with spec_in (and maybe you should exit when the argument is not provided).


Moving chips between cells Challenge:

  You are given a line of N cells with positive integers written in them. Initially a chip is placed on the leftmost cell. Each time it can be moved in any direction (to the left or to the right) on a neighboring cell or across the neighboring cell on the next one. The move is valid if the two numbers - the one the chip is standing on and the one the chip is going to be moved onto - have a common divisor greater than one. How far to the right is it possible to move a chip?

I have a working (I think) method of passing this challenge by recursively checking this method until it finds the optimum solution. I know this is probably the slowest way to do this (\$O(n!)\$?), and it seems that this isn't good enough, because the website I'm submitting my answer to says that I've exceeded my time limit.

Is there any way I can speed up this code?

int chipMoving(int[] a) {

   if(a.length == 1)return 0; //base case
   int b = a[0], c = a[1],d = b;
   while (c!=0){
     int f = c;
     c = b%c;
     b = f;
   }//b is now gcd of a[0] and a[1]

   if(a.length == 2)return b<=1?0:1; //if there are only two terms, return whether we can use the next number one or not
   int e = a[2];
   while (e!=0){
     int f = e;
     e = d%e;
     d = f;
   }//e is now the gcd of a[0] and a[2]

   int leftMax = chipMoving(Arrays.copyOfRange(a,1,a.length));
   int rightMax = chipMoving(Arrays.copyOfRange(a,2,a.length));

   //if only one is available, use that one
   if(b>1 && d<=1)return 1+leftMax;
   if(d>1 && b<=1)return 2+rightMax;

   //check which is better and return that
   if(leftMax > rightMax)return 1+leftMax;
   return 2+rightMax;
}

I am not convinced that your code works correctly. For example if I run it with the {5,3,15,1,1,3,1} input it will result in 6 what is definietly wrong. (Nothing can have a common divisor with 1 greater than 1).

My other concern is that you only move the chip forward, although it might be necesarry to move it backwards. For example:

{5, 3, 15, 9, 1, 3, 1}

You can get to the 3 on index 5, but only if you step back from the 15 to the 3. Here is the route:

0 -> 2 -> 1 -> 3 -> 5

Your approach is to simulate the optimal route of the chip and the return the result. A cleaner approach would be to calculate all visitable positions and then return the rightmost.

This problem can be naturally interpreted as a graph traversal. The nodes are the cells, and an edge is defined between two nodes if the difference of their indices are at most 2, and they have a common divisor greater then 1.

For this you need a function that finds the greates common divisor. For example:

int gcd(long a, long b) {

    if (b==0)
        return a;
    else
        return gcd(b, a % b);
}

One that tells you if an edge exists between two nodes:

boolean edge(int[] a, int i, int j){
    return gcd(a[i], a[j]) > 1;
}

You need to mark all visited cell using a breath first traversal:

private static boolean[] getVisited(int[] a) {
    boolean[] visited = new boolean[a.length];

    Queue<Integer> toVisit = new LinkedList<Integer>();
    toVisit.add(0);

    while (!toVisit.isEmpty()) {
        int i = toVisit.remove();
        if (visited[i])
            continue;
        visited[i] = true;
        if (i - 2 >= 0 && !visited[i - 2] && edge(a, i, i - 2))
            toVisit.add(i - 2);
        if (i - 1 >= 0 && !visited[i - 1] && edge(a, i, i - 1))
            toVisit.add(i - 1);
        if (i + 2 < a.length && !visited[i + 2] && edge(a, i, i + 2))
            toVisit.add(i + 2);
        if (i + 1 < a.length && !visited[i + 1] && edge(a, i, i + 1))
            toVisit.add(i + 1);
    }
    return visited;
}

And then find the rightmost visited cell:

int chipMoving(int[] a) {
    boolean[] visited = getVisited(a);

    for (int i = visited.length - 1; i >= 0; --i)
        if (visited[i])
            return i;

    return 0;
}

The runtime characteristics of finding the visited cells is \$O(N)\$, searching for the rightmost visited is also \$O(N)\$. That makes together \$O(N)\$.


Optimizing Diwali Lights problem in C I was trying to solve the Diwali Lights challenge on HackerRank.

  Problem Statement

  On the eve of Diwali, Hari is decorating his house with a serial light
  bulb set. The serial light bulb set has N bulbs placed sequentially on
  a string which is programmed to change patterns every second. If
  atleast one bulb in the set is on at any given instant of time, how
  many different patterns of light can the serial light bulb set
  produce?

  Note: Lighting two bulbs *-* is different from **-

  Input Format

  The first line contains the number of test cases T, T
  lines follow.  Each line contains an integer N, the number of bulbs in
  the serial light bulb set.

  Output Format

  Print the total number of patterns modulo 105

  Constraints

  1 <= T <= 1000
  0 < N < 104

  Sample Input

2
1
2

  Sample Output

1
3

The Code I had written is

#include<stdio.h>
# define MAX 10000 // assuming we need first 100 rows
unsigned long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // inietialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = (triangle[i - 1][j - 1] + triangle[i - 1][j]) %100000;
        }
    }
}

unsigned long long C(int n, int r) {
    return triangle[n][r];
}
/*long long C(int N, int R)
    {
        if(R > N/2) R = N - R;
        int i;
        unsigned long long ans = 1;
        for(i=1; i<=R; i++)
        {
            ans *= N-R+i;
            ans /=i;
        }
    //  printf("N=>%d R=>%d ANS=>%lld\n", N, R, ans);
        return ans;
    }
 */
int main()
{
    makeTriangle();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int N;
        scanf("%d", &N);
        //  int copy = N;
        int i;
        unsigned long long int answer =0;
        switch (N)
        {
        case 1:
            printf("1\n");
            break;
        case 2:
            printf("3\n");
            break;
        default:
        {
            int limit = N%2==0? (N /2) -1:(N/2);    // Caluculate nCr till N/2 and multiply by 2
            int n_even =0;
            if( N%2 ==0)            // calculate nC(n/2) only when N is Even
            {
                n_even = C(N,N/2);
            }
            for(i=1;i<=limit;i++)
            {
                answer +=(2*C(N,i));
                answer %= 100000;
            }
            printf("%lld\n", (answer+ 1+ n_even) % 100000); //+1 is for nCn which is 1 always
            break;
        }
        }
    }
    return 0;
}

The answer is pretty straightforward as it can be obtained by the summation of nCr. But there were a few hiccups when I tried to implement the same.

In my first attempt I had used the commented function C(N,R) to calculate the nCr each and every time for all the test cases. But this approach gave me a TLE error. So I decided I'd compute the values for nCr for all the values in with the makeTriangle() function and then whenever I called this function it would return me the computed value by looking up the array in O(1) time.

However, even this approach gave me a Time limit Exceeded error. Hence I was wondering if there could be any other optimizations that I could do with this code or a possible different approach to this problem :)

As @vnp has pointed out, each bulb can have two states, so the number of possibilities is \$2^N\$. However, the state where all bulbs are off is prohibited, so subtract one, and is the answer is simply \$(2^N -1) \mod 10^5\$.

The tricky part of the problem is that \$2^{{10}^4} -1\$ is a very large number to work with, so calculating \$(2^N -1) \mod 10^5\$ is a non-trivial problem.