Bidirectional BFS on a matrix in Python 2.7 This code is a bidirectional BFS search. Given any two points in a matrix having 0's and 1's, I would like to find if there exists a path between them. Also note that it is forbidden to enter a cell that has a value of 0.

One note I would like to make about the code is that I have maintained a duplicate matrix to check if a particular cell has been visited by the source/destination.

Can someone please let me know if there are any discrepancies in what I have implemented and how I can improve the time efficiency of this? I am new to Python.

import copy

def path_exists(grid, queries):
    #iterate through queries.
    result=[]
    for (x1,y1,x2,y2) in queries:
        print "query",x1,y1,x2,y2
        if isValidIndex((x1,y1),(x2,y2),grid) != 0:
            result.append(findPath(x1,y1,x2,y2,grid))
        else:
            result.append(0)

    return result

def isValidIndex(startIndex,endIndex,grid):
    if startIndex[0] >= len(grid) or startIndex[0] < 0 or startIndex[1] >= len(grid[0]) or startIndex[1] < 0 or endIndex[0] >= len(grid) or endIndex[0] < 0 or endIndex[1] >= len(grid[0]) or endIndex[1] < 0 :
        return 0
    return 1

def findPath(x1,y1,x2,y2,grid):
    queue1=[[x1,y1]]
    queue2=[[x2,y2]]

    bool_grid = copy.deepcopy(grid)

    source_path = 0
    dest_path = 0

    while(1):
       if len(queue1) > 0:
           if find_path_from_source(queue1,grid,bool_grid,3) == 1:
               return 1

       if len(queue2) > 0:
           if find_path_from_source(queue2,grid,bool_grid,4) == 1:
               return 1

       if len(queue1) == 0 and len(queue2) == 0:
           return 0

def find_path_from_source(queue,grid,bool_grid,val):
    x=queue[0][0]
    y=queue[0][1]
    other_val = val

    if val == 3:
        other_val = 4
    else:
        other_val = 3

    if x + 1 < len(grid):
        if bool_grid[x+1][y] == other_val:
            return 1
        elif bool_grid[x+1][y] == 1:
            bool_grid[x+1][y] = val
            queue.append([x+1,y])

    if y + 1 < len(grid[0]):
        if bool_grid[x][y+1] == other_val:
            return 1
        elif bool_grid[x][y+1] == 1:
            bool_grid[x][y+1] = val
            queue.append([x,y+1])

    if x - 1 >= 0:
        if bool_grid[x - 1][y] == other_val:
            return 1
        elif bool_grid[x - 1][y] == 1:
            bool_grid[x - 1][y] = val
            queue.append([x - 1 , y])

    if y - 1 >= 0:
        if bool_grid[x][y - 1] == other_val:
            return 1
        elif bool_grid[x][y - 1] == 1:
            bool_grid[x][y - 1] = val
            queue.append([x, y - 1])

    queue.pop(0)

grid =  [[1,0,0,1,1],
         [0,1,1,1,1],
         [1,1,0,1,1],
         [0,1,1,0,1],
         [1,1,1,0,1]]

queries=((1,2,2,3),(0,0,1,1),(2,0,0,4),(5,0,2,5),(4,4,0,0),(0,4,4,4))

x = path_exists(grid,queries)

print x

isValidIndex handling two "indices" seems wrong. At least the condition you spell becomes too long. Besides, the condition looks somewhat inside-out. Consider

def isValidIndex(index, grid):
    return 0 <= index[0] < len(grid) and 0 <= index[1] < len(grid[0])

That said, AFNP principle tells that you don't really need this function at all:

    for (x1,y1,x2,y2) in queries:
        try:
            result.append(findPath(x1,y1,x2,y2,grid))
        except IndexError:
            results.append(0)

find_path_from_source has an execution path which returns nothing. Here you can get away with it, but the practice is in generally dangerous and indicates sloppy coding.
The repetitive code in find_path_from_source should be wrapped in the loop:

    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        try:
            if bool_grid[x + dx][y + dy] == other_val:
                return 1
            if bool_grid[x + dx][y + dy] == 1:
                bool_grid[x + dx][y + dy] = val
                queue.append([x + dx, y + dy])
        except IndexError:
                pass

The bool_grid name is misleading. What is bool about it?
Copying a large grid may hurt the performance. An alternative is to compare visited cells: once they have a common element, the path is found. Implementing them as sets may make it quite fast. Of course, when in doubt, profile.


Longest Absolute File Path in Leetcode I solved the Longest Absolute File Path challenge from Leetcode.

The question is

  Suppose we abstract our file system by a string in the following
  manner:

  The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

 dir
     subdir1
     subdir2
         file.ext

  The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

  The string
  "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
  represents:

dir
     subdir1
         file1.ext
         subsubdir1
     subdir2
         subsubdir2
             file2.ext

  The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty
  second-level sub-directory subsubdir1. subdir2 contains a second-level
  sub-directory subsubdir2 containing a file file2.ext.

  We are interested in finding the longest (number of characters)
  absolute path to a file within our file system. For example, in the
  second example above, the longest absolute path is
  "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not
  including the double quotes).

  Given a string representing the file system in the above format,
  return the length of the longest absolute path to file in the
  abstracted file system. If there is no file in the system, return 0.

  Note: The name of a file contains at least a . and an extension. The
  name of a directory or sub-directory will not contain a .. Time
  complexity required: O(n) where n is the size of the input string.

  Notice that a/aa/aaa/file1.txt is not the longest file path, if there
  is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

The approach used is very similar to the way one would do this by hand. This solution looks like it has a lot of if/else statements.

Could you please suggest a cleaner way to write this solution.

public static int LengthLongestPath(string input) {
  var prefixLength = new Dictionary < int,int > ();
  int countT = 0, lengthSoFar = 0, maxLength = 0;
  bool isFile = false;
  for (int i = 0; i < input.Length; i++) {
   if (input[i] == '\n') {
    if (prefixLength.ContainsKey(countT - 1)) {
     prefixLength[countT] = lengthSoFar + prefixLength[countT - 1] + 1;
    } else {
     prefixLength[countT] = lengthSoFar;
    }

    if (isFile == true) {
     maxLength = Math.Max(maxLength, prefixLength[countT]);
     isFile = false;
    }
    lengthSoFar = 0;
    ++i;
    countT = 0;
    while (input[i] == '\t') {
     ++countT;
     ++i;
    }
    --i;
   } else {
    ++lengthSoFar;
    if (input[i] == '.') {
     isFile = true;
    }
   }
  }
  // To handle cases where file occours in the end of the string.
  if (isFile == true) {
   if (prefixLength.ContainsKey(countT - 1)) {
    maxLength = Math.Max(maxLength, prefixLength[countT - 1] + lengthSoFar + 1);
   } else {
    maxLength = Math.Max(maxLength, lengthSoFar);
   }
   isFile = false;
  }
  return maxLength;
 }

Well, it is a little bit late to answer this question but I will do it nevertheless, because it's winterbash!
I had a hard time to read your code because of the level of indentation. I would suggest using the default of 4 spaces instead of 1 space.
Another problem with the code had been at first glance the countT variable but just because of the name. Abbreviations makes the code so much harder to read and understand. If the variable would have been named countedTabs its purpose would have been cristal clear.
One should use var if the type is easy to see by the right hand side of the assignment.
Manipulating a loop variable (i) if one can avoid is a bad habit and can lead to hard to find bugs. A simple else if (input[i] == '\t') { ++countedTabs; } would have been the way to avoid this.
If one need to know if a key exists in a Dictionary<TKey, TValue> ContainsKey() is the way to go, but only if the possible value isn't needed. If one needs the value one should use Dictionary<TKey, TValue>.TryGetValue(TKey, out TValue) because accessing the value later by calling Dictionary<TKey, TValue>[TKey] will internal call the ContainsKey() as well.
Instead of doing if (booleanVariable == true) one should use if (booleanVariable). One doesn't need to compare a boolean to true because the result of the comparison is just a boolean value as well. That beeing said, you can safely remove the isFile = false; at the end of that if block because it won't be used anymore. A last word about this if: The comment you placed above the if is a good comment because it describes why you have the if in place.
One last point to make, don't declare multiple variables in one line. This just hurts the readability of the code.
Summing up leads to
public static int LengthLongestPath(string input)
{

    var prefixLength = new Dictionary<int, int>();
    var countedTabs = 0;
    var lengthSoFar = 0;
    var maxLength = 0;
    var isFile = false;

    for (var i = 0; i < input.Length; i++)
    {
        if (input[i] == '\n')
        {
            if (prefixLength.TryGetValue(countedTabs - 1, out int value))
            {
                prefixLength[countedTabs] = lengthSoFar + value + 1;
            }
            else
            {
                prefixLength[countedTabs] = lengthSoFar;
            }

            if (isFile == true)
            {
                maxLength = Math.Max(maxLength, prefixLength[countedTabs]);
                isFile = false;
            }
            lengthSoFar = 0;
            countedTabs = 0;

        }
        else if (input[i] == '\t')
        {
            ++countedTabs;
        }
        else
        {
            ++lengthSoFar;
            if (input[i] == '.')
            {
                isFile = true;
            }
        }
    }
    // To handle cases where file occours in the end of the string.
    if (isFile)
    {
        if (prefixLength.TryGetValue(countedTabs - 1, out int value))
        {
            maxLength = Math.Max(maxLength, value + lengthSoFar + 1);
        }
        else
        {
            maxLength = Math.Max(maxLength, lengthSoFar);
        }
    }
    return maxLength;
}


Family tree in Prolog I tried to write a program in Prolog and describe a family tree:

parents(uranus, gaia, rhea).
parents(uranus, gaia, cronus).
parents(cronus, rhea, zeus).
parents(cronus, rhea, hera).
parents(cronus, rhea, demeter).
parents(zeus, leto, artemis).
parents(zeus, leto, apollo).
parents(zeus, demeter, persephone).

man(uranus).
man(cronus).
man(zeus).
man(apollo).
man(artemis).

woman(gaia).
woman(rhea).
woman(leto).
woman(demeter).
woman(persephone).
woman(hera).

father(X,Y) :- parents(X,_,Y).
mother(X,Y) :- parents(_,X,Y).

parent(X,Y) :- father(X,Y); mother(X,Y).

son(S,P) :- man(S), father(P,S).
daughter(D,P) :- woman(D), mother(P, D).

siblings(A,B) :- (parents(P,_,A), parents(P,_,B), A\=B) ; (parents(_,P,A), parents(_,P,B), A\=B).

sister(X, Y) :- woman(X), ((parents(F,_,X)), (parents(F,_,Y)); ((parents(_,M,X)), (parents(_,M,Y)).

uncle(U,N) :- man(U), (siblings(U,M); siblings(U,F)), parents(M, F, N).
aunt(U,N) :- woman(U), (siblings(U,M); siblings(U,F)), parents(M, F, N).

grandparent(G,N) :- (parents(G,_,X), parents(X,_,N)); (parents(_,G,X), parents(_,X,N)).

grandpa(G,N) :- (parents(G,_,X), parents(X,_,N)); (parents(_,G,X), parents(_,X,N)), man(G).
grandma(G,N) :- (parents(G,_,X), parents(X,_,N)); (parents(_,G,X), parents(_,X,N)), woman(G).

The question is, I don't know if I did it right - especially the siblings, uncle, aunt, grandpa and grandma relations. Could somebody say if it's good or not? Thank you.

I think you can simplify your code quite a bit if you drop the implicit restrictions you have on parent.

Consider the following:

parents(X,Y,Z) :- (father(X,Z), mother(Y,Z)); (father(Y,Z), mother(X,Z)).

father(X,Y) :- parent(X,Y), man(X).
mother(X,Y) :- parent(X,Y), woman(X).

This gets rid of the implicit genders in your definitions (see your parents declarations). It means you'll need a few more lines, but it allows you to define parentship as data.

It also makes the definition for siblings a tad easier:

siblings(A,B) :- father(F,A), father(F,B), mother(M,A), mother(M,B) A\=B.

this can will make half-siblings (and step-parentship) a lot cleaner, especially considering Zeus' significant number of illegitimate offspring in case you want to extend the family tree... Greek Gods have quite the messy family if you look closer.

It also makes uncle and aunt slightly easier to follow:

uncle(U,N) :- man(U), ((siblings(U,M), mother(M,N)) ; (siblings(U,F), father(F,N))).

it can be even easier if you go for a definition with parent:

uncle(U,N) :- man(U), siblings(U,P), parent(P,N).

making the rest of the family relationships cleaner and easier to follow from here should be rather obvious. It especially eases up the grandparent definitions...

On that note: grandparent has a "small" bug. Since you implicity gendered parents, your grandparent relationship only includes the father's father and the mother's mother. A similar bug has shown itself in son and daughter... The gender of the parent doesn't influence whether the child is a son or a daughter ... father and mother respectively should be replaced by parent in that definition.

As a closing note: You should strive to build your data in a "simplistic" way of atomic units with as little "implicit relation" as possible. This might seem more effort, it will drastically reduce the chance of such bugs to happen though.


Review my F# BubbleSort Program I have written this code for BubbleSort in F#. Can you review and let me know how I can do this in most functional way.

let rec getHighest list =
    match list with
    | [x] -> x
    | [x; y] when x > y -> x
    | [x; y] -> y
    | hd1 :: hd2 :: tl when hd1 > hd2 -> getHighest (hd1 :: tl)
    | hd1 :: tl -> getHighest tl
    | _ -> failwith "unknown pattern"

let bubbleSort list =
    let rec innerBubbleSort sorted = function
    | [] -> sorted
    | l ->
        let x = getHighest l
        let (a, b) = List.partition (fun i -> i = x) l
        innerBubbleSort (a @ sorted) b
    innerBubbleSort [] list

[<EntryPoint>]
let main args =
    let input = [10; 7; 1; 0; -1; 9; 33; 12; 6; 2; 3; 33; 34;]
    let output = bubbleSort input
    printfn "%s" (List.fold (fun acc x -> acc + " " + x.ToString()) "" output)
    0

The first part could be rewritten as

match list with
| hd1 :: hd2 :: tl when hd1 > hd2 -> getHighest (hd1 :: tl)
| hd1 :: hd2 :: tl -> getHighest (hd2::t1)
| hd1 :: [] -> hd1
| _ -> failwith "unknown pattern"

which is significantly simpler


Function to test if exactly one of three parameters is truthy, without using equality operators Given the following instructions I have created a function that achieves the requirements. I feel my function is a bit too complex, though it does what it's supposed to. The difficult part for myself was avoiding the equality operators. The only way I could think to solve this is with a bit of math and a comparison operator. How can I simplify this function and save some editing time?

  Write a function onlyOne that accepts three arguments of any type.

  onlyOne should return true only if exactly one of the three arguments are
  truthy. Otherwise, it should return false.

  Do not use the equality operators (== and ===) in your solution.

My function:

function onlyOne(input1, input2, input3){
output = false;
let truthy = 0;
let falsey = 0;
if (!!input1) {
    truthy++;
} else falsey++;
if  (!!input2) {
    truthy++;
} else falsey++;
if (!!input3) {
    truthy++;
} else falsey++;
if (falsey > truthy) {
    output = true;
}
if (falsey > 2) {
    output = false;
}
return output;
}

(originally asked on StackOverflow and was directed here.)

You don't need to count the falsy arguments.  The challenge only asks you to count the truthy ones.  Since true is treated as 1 by the + operator, you can use that to perform the count.

As for the prohibition on using equality operators, you can easily work around that using two inequalities.

You forgot to declare output, so that was treated as a global variable.

function onlyOne(a, b, c) {
    let truthyCount = !!a + !!b + !!c;
    // Workaround for the prohibited test truthyCount == 1
    return 0 < truthyCount && truthyCount < 2;
}

console.log("These should be true:");
console.log(onlyOne(true, null, undefined));
console.log(onlyOne(false, '', '0'));
console.log(onlyOne(false, 0, '0'));
console.log(onlyOne(false, [], null));
console.log(onlyOne(1/0 /* Infinity */));

console.log("These should be false:");
console.log(onlyOne(1, 'a', Infinity));
console.log(onlyOne(false, null, undefined));
console.log(onlyOne(false, NaN, null));
console.log(onlyOne(0));

Based on @Blindman67's suggestion, here's another solution, which involves fewer operations.  How it works is less obvious from inspection, though.  Basically, it tests whether the number of falsy parameters is 2.

function onlyOne(a, b, c) {
    return !((!a + !b + !c) - 2);
}

console.log("These should be true:");
console.log(onlyOne(true, null, undefined));
console.log(onlyOne(false, '', '0'));
console.log(onlyOne(false, 0, '0'));
console.log(onlyOne(false, [], null));
console.log(onlyOne(1/0 /* Infinity */));

console.log("These should be false:");
console.log(onlyOne(1, 'a', Infinity));
console.log(onlyOne(false, null, undefined));
console.log(onlyOne(false, NaN, null));
console.log(onlyOne(0));


Displaying recent buyers' feedback on games I have the following code made to output the following:

Is there an efficient way to simplify it and not have to repeat the same if(!empty($st[$i]['feedback'])) { code block 2 times just to seperate 2 feedback lines with a echo '

';?

<?php

//Get 4 Feedback from Database;
$st = fetch("SELECT username,feedback,feedback_type,feedback_date FROM purchases WHERE feedback IS NOT NULL AND game = :game AND platform = :platform ORDER BY feedback_date DESC LIMIT 4","unfed_payments",array(":game"=>$urlname,":platform"=>$platform));

echo '
';

//Output the first 2 Feedback on line 1;
for($i = 0; $i < 2; $i++) {

    if(!empty($st[$i]['feedback'])) {

        echo '

';
                    echo $st[$i]['feedback'].'

';

    }

}

echo '

';

//Output the last 2 Feedback on line 2;
for($i = 2; $i < 4; $i++) {

    if(!empty($st[$i]['feedback'])) {

        echo '

';
                    echo $st[$i]['feedback'].'

';

    }

}

echo '
';

?>

Simple Approach

The simplest thing to remove copy-pasted code is to extract the exact duplication to its own function. Any variables that are needed can be passed on:

function printFeedback($st, $i) {
    if(!empty($st[$i]['feedback'])) {

        echo '

';
                    echo $st[$i]['feedback'].'

';

    }
}

Then use it:

$st = fetch([...]);

echo '
';

//Output the first 2 Feedback on line 1;
for($i = 0; $i < 2; $i++) {
    printFeedback($st, $i);
}

echo '

';

//Output the last 2 Feedback on line 2;
for($i = 2; $i < 4; $i++) {
    printFeedback($st, $i);
}

echo '
';

Now the duplication is gone.

Further Improvements

Now, the simple approach did remove the direct duplication, but we still have two similar for loops, and we have a function that accepts arguments that do not have real meaning in that context.

Let's improve it further by adjusting our print feedback function:

// echoes the given feedback array inside HTML.
function printFeedback($feedback) {
    if($feedback['feedback'])) {

        echo '

';
                    echo $feedback['feedback'].'

';

    }
}

Personally, I would create a real feedback object, but for this example I have kept it as an array, which may be fine for your purposes.

Now we can use this function in a more generic function:

// echoes the feedbacks in the feedback starting at position "from" and going to position "to" (exclusive).
function printFeedbackFromTo(Array $feedbacks, $from, $to) {
    for($i = $from; $i < $to; $i++) {
        printFeedback($feedbacks[$i]);
    }
}

And then use that function:

$st = fetch([...]);

echo '
';

printFeedbackFromTo(0,2);

echo '

';

printFeedbackFromTo(2,4);

echo '
';

Misc

Feedback seems to be user-supplied, so you have to HTML encode it, to prevent XSS.
Your comments are not needed. Just extract code into properly named functions, possibly with proper function comments (ideally using PHPDoc). In-code comments should not be used to structure your code - use functions for that - but to point out possible unclarities, problems, etc that could not be resolved otherwise.
The functions you might want to consider would be getFeedbacks($connection, $amountOfFeedbacks) and echoFeedbacks($feedbacks).
Don't put your style info in a style attribute, but in an external CSS file


Efficiently calculating differences between file using diff file I'm using SVNKit to get diff information between two revisions. I'm using the diff utility to generate a diff file, however I still need to parse it into numbers.

I implemented a solution, but it is rather slow. JGit does something similar, however it actually parses the values itself and returns an object, rather than a output stream, and is much much faster. I was unable to determine how to leverage that for SVNKit, so attempted the following solution:

private Diff compareRevisions(final SVNRevision rev1, final SVNRevision rev2) throws SVNException {
            final Diff diff = new Diff();

            try (final ByteArrayOutputStream baos = new ByteArrayOutputStream()) {

                doDiff(rev1, rev2, baos);

                int filesChanged = 0;
                int additions = 0;
                int deletions = 0;

                final String[] lines = baos.toString().split("\n");

                for (final String line : lines) {

                    if (line.startsWith("---")) {
                        filesChanged++;
                    } else if (line.startsWith("+++")) {
                        // No action needed
                    } else if (line.startsWith("+")) {
                        additions++;
                    } else if (line.startsWith("-")) {
                        deletions++;
                    }

                }

                diff.additions = additions;
                diff.deletions = deletions;
                diff.changedFiles = filesChanged;

                return diff;

            } catch (final IOException e) {
                LOGGER.trace("Could not close stream", e);
                return diff;
    }
}

I've taken to caching the values in files to improve time, but optimally I'd like to speed this up. Perhaps I could use external programs?

You need to parse the patch file format correctly. Otherwise the next patch that deletes an SQL comment will confuse your program, as it looks like this:

--- old_file.sql
+++ new_file.sql
@@ -1,1 +1,1 @@
--- SQL comment
+SELECT * FROM table;

Your current code interprets the removed line as a removed file.

The file format is explained here: http://www.gnu.org/software/diffutils/manual/html_node/Detailed-Unified.html

Since there are other people who had the same problem, you could just build on their work instead of writing your own, e.g. https://github.com/thombergs/diffparser.


"Team formation" challenge I'm trying to solve this problem but am getting a timeout. Can someone help me to improve?

using namespace std;

typedef multimap<int,int> MMap;

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t;
    cin>>t;
    for(int tcase=0; tcase<t; tcase++) {
        // contains input for each test case
        vector<int> in_vec;
        // array of different teams
        vector<vector<int> > vec_teams;
        int size;
        cin>> size;
        int val;
        int min = size;
        for(int i=0;i<size;++i) {
            cin>>val;
            in_vec.push_back(val);
        }
        if(size==0) {
            cout<<"0"<<endl;
            continue;
        }
        sort(in_vec.begin(),in_vec.end());
        vec_teams.push_back(vector<int>());
        // maintains ordered, key value pair of size and its position(index) in vec_teams
        MMap mmap;
        mmap.clear();
        vec_teams[0].push_back(in_vec[0]);
        mmap.insert(pair<int,int>(vec_teams[0].size(),0));

        for(int id=1; id<in_vec.size(); ++id) {
            bool added = false;
            MMap::iterator it = mmap.begin();
            //inserts the skill level to correct team
            // if not possible to add to any
            // then new team is created after the loop
            for(int i=0; i<vec_teams.size(); ++i,++it) {
                int mpos = (*it).second;
                if (vec_teams[mpos][vec_teams[mpos].size() -1 ] + 1 == in_vec[id]) {
                    pair <MMap::iterator, MMap::iterator> pa= mmap.equal_range(vec_teams[mpos].size());
                    MMap::iterator mmit;
                    for (mmit=pa.first; (*mmit).second!=mpos; ++mmit);
                    mmap.erase(mmit);
                    vec_teams[mpos].push_back(in_vec[id]);
                    mmap.insert(pair<int,int>(vec_teams[mpos].size(),mpos));
                    added = true;
                    break;
                }
            }
            // Since not able to add to existing teams
            // new team is created and added to it
            if(!added) {
                vec_teams.push_back(vector<int>());
                vec_teams[vec_teams.size() -1].push_back(in_vec[id]);
                mmap.insert(pair<int,int>(1,vec_teams.size() -1));
            }
        }
        int ans = (*(mmap.begin())).second;
        cout<<vec_teams[ans].size()<<endl;
    }
    return 0;
}

Separation of concerns

At the moment, all your code is in a convoluted main function handling :

getting the input from stdin
solving the problem
printing the answer in stdout.

It would be better to separate the concerns. On top of making things clearer and easier to maintain, it would also make things easier to test.

Writing tests

Because you'll probably want to improve the algorithm, it can be a safe option to write tests to ensure you are aware if you break your code. Great thing is that you have test cases provided with the problem, you just need to write them as code, run them and be happy.

At this stage, my code looks like :

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <assert.h>

using namespace std;

typedef multimap<int,int> MMap;

vector<int> get_input_from_std()
{
    // contains input for each test case
    vector<int> in_vec;
    int size;
    cin>> size;
    int val;
    for(int i=0;i<size;++i) {
        cin>>val;
        in_vec.push_back(val);
    }
    return in_vec;
}

int get_min_team_size(vector<int> in_vec)
{
    if(in_vec.size()==0) {
        return 0;
    }
    sort(in_vec.begin(),in_vec.end());
    vector<vector<int> > vec_teams;
    vec_teams.push_back(vector<int>());
    // maintains ordered, key value pair of size and its position(index) in vec_teams
    MMap mmap;
    mmap.clear();
    vec_teams[0].push_back(in_vec[0]);
    mmap.insert(pair<int,int>(vec_teams[0].size(),0));

    for(int id=1; id<in_vec.size(); ++id) {
        bool added = false;
        MMap::iterator it = mmap.begin();
        //inserts the skill level to correct team
        // if not possible to add to any
        // then new team is created after the loop
        for(int i=0; i<vec_teams.size(); ++i,++it) {
            int mpos = (*it).second;
            if (vec_teams[mpos][vec_teams[mpos].size() -1 ] + 1 == in_vec[id]) {
                pair <MMap::iterator, MMap::iterator> pa= mmap.equal_range(vec_teams[mpos].size());
                MMap::iterator mmit;
                for (mmit=pa.first; (*mmit).second!=mpos; ++mmit);
                mmap.erase(mmit);
                vec_teams[mpos].push_back(in_vec[id]);
                mmap.insert(pair<int,int>(vec_teams[mpos].size(),mpos));
                added = true;
                break;
            }
        }
        // Since not able to add to existing teams
        // new team is created and added to it
        if(!added) {
            vec_teams.push_back(vector<int>());
            vec_teams[vec_teams.size() -1].push_back(in_vec[id]);
            mmap.insert(pair<int,int>(1,vec_teams.size() -1));
        }
    }
    int ans = (*(mmap.begin())).second;
    return vec_teams[ans].size();
}

/*
Using http://stackoverflow.com/questions/8906545/how-to-initialize-a-vector-in-c
*/

void unit_tests()
{
    {
        int vv[]{4, 5, 2, 3, -4, -3, -5};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 3);
    }
    {
        int vv[]{-4};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 1);
    }
    {
        int vv[]{3, 2, 3, 1};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 1);
    }
    {
        int vv[]{1, -2, -3, -4, 2, 0, -1};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 7);
    }
}

void stdin_tests()
{
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t;
    cin>>t;
    for(int tcase=0; tcase<t; tcase++) {
        vector<int> in_vec = get_input_from_std();
        cout<< get_min_team_size(in_vec) <<endl;
    }
}

int main() {
    unit_tests();
    return 0;
}

Algorithms and performances

In the case of programming problems like the one you are trying to solve, the real issue is usually the complexity of your algorithm, how it behaves on large inputs.

In order to see how your code behaves on larges inputs, you have two main strategies (and you should try apply both):

pen, paper and mathematics
tests : great thing is that now, it is quite easy to define tests of any size you like. You just need to time your program.

For instance, you could add the following tests to your test suite :

int nb_elts = 100000;
{ // Single big team
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
        v.push_back(i);
    assert(get_min_team_size(v) == nb_elts);
}
{ // Double big team
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
    {
        v.push_back(i);
        v.push_back(i);
    }
    assert(get_min_team_size(v) == nb_elts);
}
{ // Multiple different one-player teams
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
        v.push_back(2 * i);
    assert(get_min_team_size(v) == 1);
}
{ // Multiple identical one-player teams
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
        v.push_back(0);
    assert(get_min_team_size(v) == 1);
}
{ // Overlapping three-player teams
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
    {
        v.push_back(2*i);
        v.push_back(2*i+1);
        v.push_back(2*i+2);
    }
    cout << get_min_team_size(v) << endl;
    assert(get_min_team_size(v) == 3);
}

A quick look at your code tells me is probably somewhere around O(n^2) which grows "very" fast.

I have designed an algorithm which seems to be faster on the various inputs I have tried but I might have forgotten edge-cases.

In any case, the principle is the following :

we sort the individuals by levels just like you did.
we count of many individuals we have for each levels
when considering a new group of individual :

if we have more people than the number of teams, we create as many new teams keeping track of the level of the smallest level
if we have more teams than the number of people, we end the formation of as many teams, starting with the longest ones (the one with the smallest starting levels).

I hope :

I managed to make this explanation clear
this actually works.

And here is the corresponding code :

int get_min_team_size(vector<int> levels)
{
    if (levels.size()==0)
        return 0;
    sort(levels.begin(),levels.end());

    int sol = levels.size(); // Solution will not be bigger that the size of the input
    queue<int> lowest_lvl; // Storing the (sorted) levels of the less skilled member of the teams being formed.
    int level = levels[0] - 2; // Level of the individuals being processed (the minus 2 is a trick not to have to handle the beginning in a special way).
    int nb_in_level = 0; // Number of individual being processed
    levels.push_back(levels.back() + 2); // trick not to have to handle the end in a special way
    for(int id=0; id<levels.size(); ++id)
    {
        int ind_lvl = levels[id];
        if (ind_lvl == level)
        {
            // Same level : just counting the new individual
            nb_in_level++;
        }
        else
        {
            bool lvl_gap = ind_lvl != level + 1;

            // Different level : processing what needs to be done for previous level :
            // 1) If we haven't started enough teams, let's start them from that level
            while (lowest_lvl.size() < nb_in_level)
                lowest_lvl.push(level);

            // 2) If we have too many teams started, let's end the one starting with the longest ones
            // (they correspond to the first teams as we have them sorted by the level of the smallest individual)
            // and check their length. If we have a gap of level, we want to end them all.
            if (lvl_gap)
                nb_in_level = 0;

            while (lowest_lvl.size() > nb_in_level)
            {
                // Theoritically, lowest_lvl is sorted so only the last element is relevant but we have to unpop them anyway
                sol = min(sol, 1 + level - lowest_lvl.front());
                lowest_lvl.pop();
            }

            // 3) If there is a gap of level, we add the new beginning of team.
            if (lvl_gap)
            {
                lowest_lvl.push(ind_lvl);
            }
            nb_in_level = 1;
            level = ind_lvl;
        }
    }
    assert(nb_in_level == 1);
    assert(lowest_lvl.size() == 1);
    cout << sol << endl;
    return sol;
}


URLIfy a character array using Python - follow-up This is a follow up to my last code review:

URLify a string using Python

This problem has been reviewed in other languages, but I tried to solve this without looking at those answers.

I am hoping that I achieved \$O(n)\$ time and \$O(1)\$ space as was explained in my last review.  I would also appreciate any tips on improving clarity and/or making the code more pythonic without sacrificing time/space complexity.

def count_spaces(in_char_array):
   num_spaces = sum(1 for char in in_char_array if char == ' ')
   return  num_spaces

def urlify(in_char_array, true_length):
   num_spaces = count_spaces(in_char_array[:true_length])
   urlified_length = true_length + 2*num_spaces

   urlified_pos = urlified_length - 1
   for in_char in reversed(in_char_array[:true_length]):
       if in_char == ' ':
           in_char_array[urlified_pos-2:urlified_pos+1] = '%20'
           urlified_pos -= 3
       else:
           in_char_array[urlified_pos] = in_char
           urlified_pos -= 1
    return in_char_array

I tested this as follows -

urlified_string = urlify(list('Mr John Smith    '), 13)

print(urlified_string)
print(''.join(urlified_string))

The output was:

['M', 'r', '%', '2', '0', 'J', 'o', 'h', 'n', '%', '2', '0', 'S', 'm', 'i', 't', 'h']

Mr%20John%20Smith

\$O(n)\$ time with \$O(1)\$ space is a hard, and somewhat extreme requirement.
Sure the \$O(n)\$ can be achieved easily. But the \$O(1)\$ is not.

Using lists, to achieve \$O(1)\$ means you have to change the list in-place.
This means any slicing or helper methods are instantly not an option.
This was pointed out by 200_success.
Take:

>>> a = 'abc  '
>>> id(a)
51272544
>>> id(a.strip())
48713152
>>> id(a[:-2])
44833440
>>> del a[-2:]
TypeError: 'str' object does not support item deletion
>>> a = list('abc  ')
>>> id(a)
51232040
>>> id(a.strip())
AttributeError: 'list' object has no attribute 'strip'
>>> id(a[:-2])
51246424
>>> del a[-2:]
>>> a
['a', 'b', 'c']
>>> id(a)
51232040

So to achieve the requirements you need is hard.
And I'd say unreasonable in the real world.

I also agree with Phrancis that your functions input is bad.
To achieve what you want, we'd want to manually implement strip.
And we're only allowed to make in place changes to the array.
This means the function will be, using type hints, inplace_strip(data: list).

Since strip removes just spaces at the front and back of the list, it's easy to implement efficiently.
Just count the amount of places to remove from the front and back, and then delete them.

def inplace_strip(data: list):
    for i in range(len(data)):
        if data[i] != ' ':
            break
    else:
        del data[:]
        return None
    if i:
        del data[:i]

    for i in range(len(data)-1, -1, -1):
        if data[i] != ' ':
            break
    if i != len(data):
        del data[i+1:]

Is this still \$O(n)\$ time? Yes.
If we look at the time complexity of the list operations I used, then we should see that they are all \$O(n)\$ or smaller.
And so the function is \$O(n)\$.

After this we need to mutate the list so that we can change all ' ' to '%20'.
There are three ways we can do this:

Set Item, changes the return to ['a', 'b', '%20', 'c'].
Set Slice, has the time complexity of \$O(k+n)\$.
Generator, you're going to change the space complexity outside of this function to \$O(n)\$.

So it's really a hard choice.
I'd use a generator as the function 'has no problems', it's you who's changing the space complexity to \$O(n)\$.
And so when ever you get a ' ' you'll yield the '%20'.
But you'll split it up so that there's three yields.

This makes the function simply:

def urlify(data: list):
    inplace_strip(data)
    for char in data:
        if char == ' ':
            yield '%'
            yield '2'
            yield '0'
        else:
            yield char

A function which will always have the usage as, ''.join(urlify(data)).
And so wastes all that hard work.
Instead I'd say to use str.strip and str.translate, this makes the code much simpler, which allows you to change the function to:

def urlify(data: list):
    return data.strip().translate({ord(' '): '%20'})


Calculate electric field of a charged annulus This script calculates the shape of the electric field on a 2D grid perpendicular to a uniformly charged annulus using SciPy's dblquad (tutorial, documentation).

I've chosen a coarse grid and specified a very large relative error epsrel here so that this example will run in about 10 seconds, but I'll be using it on a much finer grid and with much lower specified error.

I'd like to know if there are ways this can be significantly sped up without loss of accuracy, which should be in the 1E-7 neighborhood.

I'll be avoiding pathological points manually, as I've done here by avoiding the z=0 plane. I've left out constants and units to reduce clutter.

def Excalc(r, th):
    x, y, z = r*np.cos(th), r*np.sin(th), 0.0
    return (x0-x) * ((x0-x)**2 + (y0-y)**2 + (z0-z)**2)**-1.5

def Eycalc(r, th):
    x, y, z = r*np.cos(th), r*np.sin(th), 0.0
    return (y0-y) * ((x0-x)**2 + (y0-y)**2 + (z0-z)**2)**-1.5

def Ezcalc(r, th):
    x, y, z = r*np.cos(th), r*np.sin(th), 0.0
    return (z0-z) * ((x0-x)**2 + (y0-y)**2 + (z0-z)**2)**-1.5

import numpy as np
import matplotlib.pyplot as plt
from scipy.integrate import dblquad

twopi = 2.*np.pi

# annulus of uniform, unit charge density
rmin, rmax   = 0.8, 1.2
thmin, thmax = 0,   twopi

x = np.arange(-2,    2.1, 0.1)
z = np.arange(-1.55, 1.6, 0.1) # avoid z=0 plane for integration.
X, Z = np.meshgrid(x, z)
s = X.shape

eps = 1E-4
y0  = 0

fields, errors = [], []
for x0, z0 in zip(X.flatten(), Z.flatten()):
    # use of lambda in lieu of function calls https://stackoverflow.com/a/49441680/3904031
    Ex, Exerr  = dblquad(Excalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
    Ey, Eyerr  = dblquad(Eycalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
    Ez, Ezerr  = dblquad(Ezcalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
    fields.append([Ex, Ey, Ez])
    errors.append([Exerr, Eyerr, Ezerr])

Evec = np.stack([np.array(thing).reshape(s) for thing in zip(*fields)])
Emag = np.sqrt((Evec**2).sum(axis=0))

Evecerr = np.stack([np.array(thing).reshape(s) for thing in zip(*errors)])
Emagerr = np.sqrt((Evecerr**2).sum(axis=0))

if True:
    names = 'Ex', 'Ey', 'Ez', 'Emag'
    plt.figure()
    for i, (E, name) in enumerate(zip([e for e in Evec] + [Emag], names)):
        smalls = np.abs(E) < 1E-08
        E[smalls] = 0.     # fudge to keep Ey from showing 1E-14 fields
        plt.subplot(2, 2, i+1)
        plt.imshow(E, origin='lower')
        plt.colorbar()
        plt.title(name, fontsize=16)
    plt.show()

if True:
    names = 'Ex rel error', 'Ey rel error', 'Ez rel error', 'Emag rel error'
    plt.figure()
    for i, (err, name) in enumerate(zip([er for er in Evecerr] + [Emagerr], names)):
        plt.subplot(2, 2, i+1)
        plt.imshow(err/E, origin='lower')
        plt.colorbar()
        plt.title(name, fontsize=16)
    plt.show()

I think the main time consuming factor here is calculating the dbquad, that said there are some smaller improvements you can make

split into functions

lookup of local variables in a function is faster than a global lookup, so putthing each part in a function can speed up this process already. If you do this, beware that your E_calc functions use global state (x0, y0 and z0), so they should be defined in the function scope, so they can use the local variables

numpy

You can use numpy a bit more to assemble the final answers

Instead of  keeping 2 arrays fields and errors, you can  keep this in 1 array, and index the errors and values.

def calc2():
    twopi = 2.*np.pi

    # annulus of uniform, unit charge density
    rmin, rmax   = 0.8, 1.2
    thmin, thmax = 0,   twopi

    x = np.arange(-2,    2.1, 0.1)
    z = np.arange(-1.55, 1.6, 0.1) # avoid z=0 plane for integration.
    X, Z = np.meshgrid(x, z)
    s = X.shape

    eps = 1E-4
    y0  = 0
    def Excalc(r, th):
        x, y, z = r*np.cos(th), r*np.sin(th), 0.0
        return (x0-x) * ((x0-x)**2 + (y0-y)**2 + (z0-z)**2)**-1.5

    def Eycalc(r, th):
        x, y, z = r*np.cos(th), r*np.sin(th), 0.0
        return (y0-y) * ((x0-x)**2 + (y0-y)**2 + (z0-z)**2)**-1.5

    def Ezcalc(r, th):
        x, y, z = r*np.cos(th), r*np.sin(th), 0.0
        return (z0-z) * ((x0-x)**2 + (y0-y)**2 + (z0-z)**2)**-1.5
    values = []
    for x0, z0 in zip(X.flatten(), Z.flatten()):
        # use of lambda in lieu of function calls https://stackoverflow.com/a/49441680/3904031
        Ex, Exerr  = dblquad(Excalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
        Ey, Eyerr  = dblquad(Eycalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
        Ez, Ezerr  = dblquad(Ezcalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
        values.append([Ex, Ey, Ez, Exerr, Eyerr, Ezerr])
#         errors.append([Exerr, Eyerr, Ezerr])
    values = np.array(values).T.reshape(6, *X.shape)

    e_vec = values[:3]
    e_mag = np.linalg.norm(e_vec, axis=0)

    e_vec_err = values[3:]
    e_mag_err = np.linalg.norm(e_vec_err, axis=0)

    return Evec, Emag, Evecerr, Emagerr

This resulted in a very slight reduction in time, so will not save you heaps

lru_cache

refactoring the calc methods to reuse the most of the result actually slowed things down, this is how I tackled that

from functools import partial, lru_cache

@lru_cache(None)
def calc(r, th, coords_0):
    coords_0 = np.array(coords_0)
    diff = coords_0 - np.array((r*np.cos(th), r*np.sin(th), 0.0))
    return diff * ((diff)**2).sum()**-1.5

def calc3():
    rmin, rmax = 0.8, 1.2
    thmin, thmax = 0, 2.*np.pi

#     s = X.shape

    eps = 1E-4
    y0  = 0
    x = np.arange(-2,    2.1, 0.2)
    z = np.arange(-1.55, 1.6, 0.2) # avoid z=0 plane for integration.
    X, Z = np.meshgrid(x, z)

    calc_axis = lambda r, th, coords_0, axis: calc(r, th, coords_0)[axis]

    values = []
    for x0, z0 in zip(X.flatten(), Z.flatten()):
        coords_0 = (x0, y0, z0)
        Excalc, Eycalc, Ezcalc = (partial(calc_axis, coords_0=coords_0, axis=i) for i in range(3))
        # use of lambda in lieu of function calls https://stackoverflow.com/a/49441680/3904031
        Ex, Exerr  = dblquad(Excalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
        Ey, Eyerr  = dblquad(Eycalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
        Ez, Ezerr  = dblquad(Ezcalc, thmin, thmax, lambda t: rmin, lambda t: rmax, epsrel=eps)
        values.append((Ex, Ey, Ez, Exerr, Eyerr, Ezerr))
    print(calc.cache_info())
    values = np.array(values).T.reshape(6, *X.shape)

    e_vec = values[:3]
    e_mag = np.linalg.norm(e_vec, axis=0)

    e_vec_err = values[3:]
    e_mag_err = np.linalg.norm(e_vec_err, axis=0)
    return e_vec, e_mag, e_vec_err, e_mag_err, values

Apparently, about halve of the calls to calc were cached, but moving the calculation to this method resulted in a net slowdown.

numba

What did result in a speed increase was numba

just adding @jit before def calc(r, th, coords_0): made the calculation 3 times as fast


Split dictionary of lists into two dicts based on binary values I have a very large dictionary that contains key-value pairs where the key is a string and the value a list. All lists have the same lengths. I want to split up the dataset (dictionary) in two based on the values in one of the lists. One of the lists will contain binary values (i.e. 0 or 1). I want to split up the dictionaries so that one of them contains all those where the binary value is 0 and the other where it is 1.

(It is easier to understand this when you mentally transform the dataset in a table where each index of the lists is a row, and where the dictionary values are column names.)

I guess I could first convert the dict to a Pandas dataframe and then subset the dataframe, and convert the resulting dataframes back to dicts, but I only want to do this if it proves to be faster than doing it with dictionaries only.

The following code works (test it here), but as said I'm not sure about efficiency. I'm only interested in Python >= 3.6

from collections import defaultdict

def split_d(d, key):
  include = defaultdict(list)
  exclude = defaultdict(list)

  for i in range(0, len(d[key])):
    binary = d[key][i]
    for k, v in d.items():
      if k == key:
        continue

      if binary == 0:
        exclude[k].append(v[i])
      elif binary == 1:
        include[k].append(v[i])
      else:
        raise ValueError(f"Key {key} is not binary. Expected values 0 or 1")

  return include, exclude

d = {
  'prof': [1,0,0,1,1,1,1,1,0,1],
  'val': [45,12,36,48,48,59,5,4,32,7]
}

print(split_d(d, 'prof'))

You should indent with 4 spaces, as per PEP8.

You can move your if out of the inner loop, and use enumerate, leading to a ~9% speed up.

def split_d(d, key):
    include = defaultdict(list)
    exclude = defaultdict(list)
    for i, binary in enumerate(d[key]):
        if binary == 1:
            output = include
        elif binary == 0:
            output = exclude
        else:
            raise ValueError(f"Key {key} is not binary. Expected values 0 or 1")

        for k, v in d.items():
            if k == key:
                continue
            output[k].append(v[i])

    return include, exclude

You can also remove key from d and add it back when you've gone through both the loops. Leading to a further ~5% speed up.

def split_d(d, key):
    include = defaultdict(list)
    exclude = defaultdict(list)
    keys = d.pop(key)
    try:
        for i, binary in enumerate(keys):
            if binary == 1:
                output = include
            elif not binary:
                output = exclude
            else:
                raise ValueError(f"Key {key} is not binary. Expected values 0 or 1")

            for k, v in d.items():
                output[k].append(v[i])
    finally:
        d[key] = keys
    return include, exclude

Other than the above your code looks good and I don't think there is any way to increase the performance in vanilla Python. And so if this is not fast enough then looking into NumPy would be the best thing next.


Using T-SQL SEQUENCE with Entity Framework 6 After reading many posts about how to handle sequences in EF 6 (see below) I found a way that was working for me. I'm using Code First and want to include the sequence from scratch, so without using migrations (tell me if I'm getting this wrong).

Task was to get an unique and gapless incrementing extra ID for my entity Car, which is not being used as primary key.

Here is what I'm doing now:

Entity:

public class Car
{
    public int Id { get; set; }
    public int CarNr { get; set; }
    public string Name { get; set; }
}

Context:

public class Context : DbContext
{
    public Context() : base()
    {
        SetDefaultConfiguration();
    }

    public Context(string connectionString) : base(connectionString)
    {
        SetDefaultConfiguration();
    }

    public Context(DbConnection existingConnection) : base(existingConnection, true)
    {
        SetDefaultConfiguration();
    }

    public override int SaveChanges()
    {
        SetCarNr();
        return base.SaveChanges();
    }

    public override Task<int> SaveChangesAsync()
    {
        SetCarNr();
        return base.SaveChangesAsync();
    }

    public override Task<int> SaveChangesAsync(CancellationToken cancellationToken)
    {
        SetCarNr();
        return base.SaveChangesAsync(cancellationToken);
    }

    private void SetDefaultConfiguration()
    {
        Database.SetInitializer(new CreateSequenceInitializer());
    }

    public class CreateSequenceInitializer : DropCreateDatabaseIfModelChanges<Context>
    {
        protected override void Seed(Context context)
        {
            context.Database.ExecuteSqlCommand("CREATE SEQUENCE CarNrSequence AS INT START WITH 200000 NO CACHE;");
            base.Seed(context);
        }
    }

    private void SetCarNr()
    {
        var carsToSave = ChangeTracker.Entries().Select(e => e.Entity).OfType<Car>();
        foreach (var c in carsToSave)
        {
            c.CarNr = GetNextSequenceValue();
        }
    }

    public int GetNextSequenceValue()
    {
        var rawQuery = Database.SqlQuery<int>("SELECT NEXT VALUE FOR CarNrSequence;");
        var task = rawQuery.SingleAsync();
        int nextVal = task.Result;
        return nextVal;
    }

    public DbSet<Car> Cars { get; set; }
}

So I'm using a DatabaseInitializer to create the sequence for me and intercept the SaveChanges to insert the extra ID queried from the DB.

Question:
Is there a better way? Is this "save"? What problems do you see?

Thanks!

PS: Here are some links that helped me a lot

https://stackoverflow.com/questions/27077461/how-to-get-next-value-of-sql-server-sequence-in-entity-framework
https://stackoverflow.com/questions/24162895/entity-framework-6-and-sql-server-sequences
https://stackoverflow.com/a/34894274/226278
https://stackoverflow.com/questions/20136504/how-can-set-a-default-value-constraint-with-entity-framework-6-code-first

Your C# code looks fine, but using non-cached sequences instead of IDENTITY (which would be much easier to implement in Entity Framework) does not ensure a gapless incrementing identifier.

According to this Microsoft article, sequences can generate gaps in some scenarios:

  The sequence object generates numbers according to its definition, but
  the sequence object does not control how the numbers are used.
  Sequence numbers inserted into a table can have gaps when a
  transaction is rolled back, when a sequence object is shared by
  multiple tables, or when sequence numbers are allocated without using
  them in tables.

So, error on saving changes will have consumed the sequence numbers and thus you obtain gaps.

On the database side, this thread approaches the generation of gapless incrementing identifier, but I am also thinking about generating identifiers within the application layer and restoring the value on save failure:

private int PrevSequenceId;
private int SequenceId;

private void SetCarNr()
{
    var carsToSave = ChangeTracker.Entries().Select(e => e.Entity).OfType<Car>();
    foreach (var c in carsToSave)
    {
        c.CarNr = Interlocked.Increment(ref SequenceId);
    }
}

public override int SaveChanges()
{
    try
    {
        SetCarNr();
        return base.SaveChanges();
        // locking might be required here for thread safety
        PrevSequenceId = SequenceId;
    }
    catch (Exception exc)
    {
        // log stuff if needed

        // locking might be required here for thread safety
        SequenceId = PrevSequenceId;
    }
}

However, this solution may work only if identifiers are generated by the application layer only.


File names to database table I have files in subfolders on a network drive. I want to create a list of files, and insert that list into an Oracle table.

I can successfully iterate through the files in the subfolders and do the insert:

Loop through a user-defined list of subfolders called subfolder_list (I only want the files in specific subfolders; not all of the subfolders)
Loop through the files in each subfolder
Using an ArcSDESQLExecute class in the ArcPy site package, insert each file name into the records table

import arcpy
import os

db_conn_folder = r'C:\connection\folder\connection.sde'
conn = arcpy.ArcSDESQLExecute(db_conn_folder)

folder = r'\\my\network\folder'
subfolder_list = [r'\DRAWINGS', r'\DOCUMENTS', r'\VIDEOS']

#Delete all records in the table
db_exec = conn.execute('delete from records')

#Loop through the list of subfolders
for i in subfolder_list:
    #loop through the files in the subfolder
    for filename in os.listdir(folder + i):
        #insert the file names into the table
        db_exec = conn.execute('insert into records (file_name) values (' + filename + '\')')

#Commit the insert statements
db_exec = conn.execute('commit')

print "Complete."

The SQL is a little hard to read with all the python parsing and formatting. Plain-language SQL would look like this:

delete from records;
insert into records (file_name) values ('plan_profile_1.tif');
commit;

While the code works just fine, I'm wondering, can it be improved?

(I can count the number of Python scripts I've written on one hand.)

folder = r'\\my\network\folder'
subfolder_list = [r'\DRAWINGS', r'\DOCUMENTS', r'\VIDEOS']

Don't write the type into the variable name. The type should be able to change without the variable having to be renamed. subfolders already tells you that it is a collection of subfolders. subfolder_names might be better, to make clear that it contains the folders' names, not wrapper objects for the file system.

Removing the backslash from the beginning can prevent you from having to read up the code to make sure where the backslash is, at the beginning or the end. subfolder or subfolder_name implies just the name. So add the backslash wherever you concatenate the strings.

#Delete all records in the table
db_exec = conn.execute('delete from records')

That comment is obsolete, as it adds no information that is not already in the next line of code.

#Loop through the list of subfolders
for i in subfolder_list:
    #loop through the files in the subfolder
    for filename in os.listdir(folder + i):
        #insert the file names into the table
        db_exec = conn.execute('insert into records (file_name) values (' + filename + '\')')

Again, the comments are not needed, and instead impair readability. Instead of explaining with comments what the code does, improve the code to better explain itself. i can be acceptable as a loop variable, but whenever possible, use a more explicit name, like in this case subfolder_name. Then you get this more expressive code:

for subfolder_name in subfolder_names:
    for file_name in os.listdir(folder + r'\' + subfolder_name)
        db_exec = conn.execute('insert into records (file_name) values (' + file_name + '\')')

#Commit the insert statements
db_exec = conn.execute('commit')

Again the comment is not needed.

print "Complete."

What is complete? Give the user more info, e. g. `"42 file names inserted into database."


Knapsack 01 solution Solution to bounded knapsack 01 problem. Once again comprehensive description is difficult in this space, refer here. Looking for code review. optimizations and best practices.

final class Item {
    private final int value;
    private final int weight;

    public Item (int value, int weight) {
        if (value == 0) {
            throw new IllegalArgumentException("The value " + value + " should be positive.");
        }
        if (weight == 0) {
            throw new IllegalArgumentException("The weight " + weight + " should be positive.");
        }

        this.value = value;
        this.weight = weight;
    }

    public int getValue() {
        return value;
    }

    public int getWeight() {
        return weight;
    }
}

public final class Knapsack01 {

    private Knapsack01() {  }

    /**
     * Returns the maximum value, given set of items and maxweight
     *
     * @param items         the set of items.
     * @param maxWeight     the max weight
     * @return              the max value obeying the constraints
     */
    public static int getMaxValue (Item[] items, int maxWeight) {
        if (maxWeight <= 0) {
            throw new IllegalArgumentException("the maxweight: " + maxWeight + " should be positive");
        }

        int[][] knapsack = new int[items.length + 1][maxWeight + 1];

        for (int item = 0; item <=items.length; item++) {
            for (int weight = 0;  weight <= maxWeight; weight++) {

                if (item == 0 || weight == 0) {
                    continue;
                }

                int itemWeight = items[item - 1].getWeight();
                if (weight >= itemWeight) {
                    int remainingWeight = weight -  itemWeight;
                    // check the max value upto remainingWieght, the we might have computed before.
                    int valueUptoRemainingWeight = knapsack[item - 1][remainingWeight];
                    // how about trying currentItem + remainingItem ?
                    int tentativeValue = items[item - 1].getValue() + valueUptoRemainingWeight;
                    // compare this against previously calculated max-value
                    int previousMaxValue = knapsack[item - 1][weight];

                    knapsack[item][weight] = Math.max(tentativeValue, previousMaxValue);

                } else {
                    knapsack[item][weight] = knapsack[item - 1][weight];
                 }
            }
        }

        return knapsack[items.length][maxWeight];
    }

    public static void main(String[] args) {
        Item i1 = new Item( 60, 10);
        Item i2 = new Item(100, 20);
        Item i3 = new Item(120, 30);

        Item[] items = new Item[3];
        items[0] = i1;
        items[1] = i2;
        items[2] = i3;

        assertEquals(180, getMaxValue(items, 40));
        assertEquals(220, getMaxValue(items, 50));
        assertEquals(280, getMaxValue(items, 60));
        assertEquals(280, getMaxValue(items, 60));
    }
}

Just a few comments :

Your if (value == 0) and if (weight == 0) should probably be if (value <= 0) and if (weight <= 0).

Keep It Simple : because value and weight are final, you could probably make them public, removing the need for getters.

Also, you could make this an inner class/nested class if you don't plan to use it for anything else.

Purely personal but I'd rather avoid continue whenever it can be easily avoided. If your case, it's quite easy to put the whole block behind a if (item != 0 && weight != 0) (or even better : if (item > 0 && weight > 0)).

However, things could be even more straightforward : for (int item = 0; item <=items.length; item++) and for (int weight = 0;  weight <= maxWeight; weight++) could start at 1 because first iteration won't do anything anyway because condition if (item == 0 || weight == 0) will be true. Then, as far as I can tell, the guard is not needed anymore.


Smart pointer implementation I've decided to implement a simple smart pointer:

#pragma once
//simple and basic reference by Aldrigo Raffaele
#include "Common.h"
#include "Exceptions.h"

class MemWrp {
        private:
        uint numref;
        public:
        void* content;

        MemWrp(void* content) {
                this->content = content;
                numref = 1;
        }

        void AddRef() { numref++; }
        uint RemoveRef() { return --numref; }

        destructor MemWrp() { delete content; }
};

template< class T >
class Ref {
        private:
        MemWrp* wrp = NULL;
        public:
        Ref() {}
        Ref(T* ptr) {
                wrp = NULL;
                if (ptr != NULL) wrp = new MemWrp(ptr);
        }
        Ref(const Ref<T>& r) {
                wrp = r.wrp;
                if (wrp != NULL) wrp->AddRef();
        }
        Ref(MemWrp* w) {
                wrp = w;
                wrp->AddRef();
        }

        T* Get() const {
                if (wrp == NULL) return NULL;
                return (T*)wrp->content;
        }

        template<class F>
        bool is() { return dynamic_cast<F*>(Get()) != NULL; }

        template<class F>
        Ref<F> as() {
                if (!this->is<F>()) return Ref<F>::Ref();
                return Ref<F>::Ref(this->wrp);
        }

        Ref<T>& operator=(Ref<T>& rhs) {
                if (this == &rhs) return *this;
                if (rhs.wrp == NULL && wrp != NULL && wrp->RemoveRef() == 0) delete wrp;
                wrp = rhs.wrp;
                if (wrp != NULL) wrp->AddRef();
                return *this;
        }

        Ref<T>& operator=(T* rhs) {
                if (Get() == rhs) return *this;
                if (rhs == NULL && wrp != NULL && wrp->RemoveRef() == 0) delete wrp;
                else if (rhs != NULL) wrp = new MemWrp(rhs);
                return *this;
        }

        bool operator==(const Ref<T>& other) const {
                return (this->Get() == other.Get());
        }

        bool operator==(const int other) const {
                return (this->Get() == (void*)other);
        }

        bool operator!=(const Ref<T>& other) const {
                return !(*this == other);
        }

        bool operator!=(const int other) const {
                return !(*this == other);
        }

        T* operator->() {
                if (this->Get() == NULL) throw NullPointerException();
                return this->Get();
        }
        const T* operator->() const {
                if (this->Get() == NULL) throw NullPointerException();
                return this->Get();
        }

        destructor Ref() {
                if (wrp != NULL && wrp->RemoveRef() == 0) delete wrp;
        }
};

What do you think?  How can I subdivide it into .h and .cpp?

What do you think?

For learning RAII/resource management, it's a good idea to write your own smart pointer class. For production code, use std::shared_ptr, std::unique_ptr, or boost smart pointers (if you have to).

Here are some notes on the code itself:

The code only compiles if you add:

Code:

#define destructor ~

Don't do that! It simply increases the WTFPLOC ("what the fuck!"s per lines of code) ratio of your code and even if it seems like a nice idea now, you will (most probably) not consider it a good idea one year from now, looking at the code.

MemWrp should:

store the data in a strongly-typed pointer (that means, make it a template by pointer type); Otherwise, when you delete it will not invoke the right destructor type unless you use a cast.
be a private part of the Ref class; It's an implementation detail; you should not need to create instances of it outside of Ref implementation, and you should not pollute the global namespace with the class name.
Use a better name; While using shortened words for names (i.e. MemWrp instead of MemoryWrapped/MemoryWrapper/MemoryWrap etc), this is only a good idea if the shortened words are traditionally used for replacement (e.g. "ptr" for "pointer" is fine, "Mem" for "memory" is fine, "Wrp" can be expanded into about five words easily and leads to confusion).
protect it's managed resource (why is MemWrp::content public?)

Ref class should:

be renamed to _Something_Ptr or Ptr_Something_ ("Ref" traditionally represents a reference which has/should have reference semantics). See std::ref and std::cref for comparison. Examples: Shared_Ptr, CountedPtr, ManagedPtr, SmartPtr, etc. Just don't call it Ref.
Not allow construction from a pointer converted to int.

The interface of the class suggests that this code is perfectly legal:

class Qxb; // implementation is irrelevant
Ref<Qxb> ref(101); // good luck dereferencing this pointer

Ref class should (continued):

Not need C-style (or any other style) casts; They are not only unnecessary, they are a symptom of bad implementation or design.
Disallow construction of a Ref instance from a MemWrp instance, especially since the MemWrp class is not strongly-typed on the stored content.
not implement equality comparison with ints. Your class doesn't store ints, it should not have a value equal to them. This will (probably) lead to problems in client code.


Async task post method WebAPI controller I have a post method in an WebAPI2 controller. I just want to make sure that everything I have done is correct. I want to create a new task run the method asynchronously and return a message.

public async Task<IHttpActionResult> Post([FromBody]Menu m)
{
    using (MySqlConnection con = new MySqlConnection(""))
    using (MySqlCommand cmd = new MySqlCommand("Insert into Menu (Description,LanguageId,IsActive) values (@Description,@LanguageId,@IsActive) ", con))
    {
        try
        {
            if (con.State == ConnectionState.Closed)
            {
                await con.OpenAsync();
                cmd.Parameters.AddWithValue("@Description", m.Description);
                cmd.Parameters.AddWithValue("@LanguageId", m.LanguageId);
                cmd.Parameters.AddWithValue("@IsActive", m.IsActive);
                await cmd.ExecuteNonQueryAsync();
            }
        }
        catch (MySqlException ex)
        {
            return Content(HttpStatusCode.NotFound,ex);
        }
        finally
        {
           await  con.CloseAsync();
        }
        return Ok("Inserted Succesfully");
    }
}

Should I create a new async method to execute the query and then return the message into the post method of the controller, or is this the correct way?

You need to take care of Single Responsibility Principle here.
Your Post method should handle only HTTP request and then it passes to another handler for further operation and after receiving the result, revert back to User.

You can follow SRP and DRY principle in your code.


Merge intersecting sub-arrays What I'm trying to achieve is to group all sub-arrays, which are connected (sharing the same elements) into one array.
So here is an example:

Input: [[1, 17], [3, 5], [5], [1, 3], [7], [2], [9, 8], [7, 2]];

What I am expecting to get: [[ 1, 3, 5, 17 ], [ 2, 7 ], [ 8, 9 ]]

Indexes of arrays, that are related:

0, 1, 2, 3
4, 5, 7
6

My code does what's needed, but my gut tells me that performance, amount of iterations and readability of the code can be improved, especially because it will be run on pretty long arrays.

So here is what I have:

const input = [[1, 17], [3, 5], [5], [1, 3], [7], [2], [9, 8], [7, 2]];

let i = 0;

const mergeIntersections = (array) => {
  const arrayClone = [].concat(array);
  let intersectionFound;
  let currIntersections = [];

  arrayClone.forEach(() => {
    /**
     * Subarray, which elements we'll look for
     * Removing it from the source array so it does not disturb us
     */
    const wanted = arrayClone.shift().sort((a, b) => a - b);

    /*
     * Preserving the length of the source array
     */
    arrayClone.push([]);

    let intersections = [].concat(wanted);

    wanted.forEach((wantedElement) => {
      arrayClone.forEach((arr, arrIndex) => {
        if (~arr.indexOf(wantedElement)) {
          intersections = intersections.concat(arr);
          intersectionFound = true;
          arrayClone[arrIndex] = [];
        }
        i++;
      });
    });

    if (intersectionFound) {
      currIntersections.push(Array.from(new Set(intersections)));
    } else {
      currIntersections = array;
    }

    currIntersections = currIntersections.filter(item => item.length);
  });

  if (intersectionFound) {
    return mergeIntersections(currIntersections);
  }
  return currIntersections;
};

console.log('result: ', JSON.stringify(mergeIntersections(input)));
console.log('amount of iterations: ', i);

I went full performance here, so no forEach and such.
The idea is to use associative arrays and assume they cost O(1) for speed improvement. The steps of this algorithm:

For each number, store the index of the array it first appeared on.
For repeated numbers, we have intersections. As resolving the intersection right now is not performant (we might have more intersections later), we will just mark the current array and the array that number first appeared on as neighbors.
After all this preprocessing, we are ready to solve the problem. What we are left with is a graph, where a node is an array inside input. For that node, we have stored its inmediate neighbors, which represent the other arrays that also had a common number with it.
Now we do a standard DFS to iterate over all direct and indirect neighbors of a node, where we keep adding the numbers of each of those nodes to the group we are making.

The most expensive part of the algorithm is the sorting, which I´m not sure if you needed it. If you do not care about order, no need to sort them. The important part is that we only add each number to the result array once, and we process each number once, so except for the sorting, the complexity should be linear on the amount of numbers in input.

const input = [[1, 17], [3, 5], [5], [1, 3], [7], [2], [9, 8], [7, 2]];

function merge(input) {
    var numberGroup = {}
    var neighbors = new Array(input.length); // direct intersections
    var processed = new Array(input.length); // for the dfs

    for (var arrayIndex = 0; arrayIndex < input.length; arrayIndex++) {
        var array = input[arrayIndex];
        neighbors[arrayIndex] = {}; // we don´t use [] because we don´t want to keep repeated neighbors
        processed[arrayIndex] = false;

        for (var i = 0; i < array.length; i++) {
          var number = array[i];

          if (numberGroup.hasOwnProperty(number) == false) { // haven´t seen the number before
            numberGroup[number] = arrayIndex; // we mark its first apparition
          } else { // we connect the node with the one where this number appeared for the first time
            var neighbor = numberGroup[number];
            neighbors[arrayIndex][neighbor] = true;
            neighbors[neighbor][arrayIndex] = true;
          }
        }
    }

    //inline function, could be taken outside and pass input , processed and neighbors
    function makeGroup (index, group) { // dfs
      if (processed[index] == false) {
          processed[index] = true;

          for (var i = 0; i < input[index].length; i++) {
            group[input[index][i]] = true; // we only care about key, so we put value true but could be false
          }

          for (var neighbor in neighbors[index]) makeGroup(neighbor, group)
          return true; // this makes a new group
      }
      return false; // this does not make a new group
    }

    var result = [];

    for (var i = 0; i < input.length; i++) {
      var group = {};
      if(makeGroup(i, group)) {
        result.push(Object.keys(group).map(Number).sort((a, b) => a - b)); // pass the keys to an array and sort it
      }
    }

    return result;
}

console.log(merge(input));


Client for handlersocket server I wrote a simple client for handlersocket server, but I'm not a professional Java programmer and would like to know the opinion of Java developers on my code.

Well I have not yet decided how to implement a class HSResult.

My project is here

HSResult store initial query and answer as List of ChannelBuffers, where each ChannelBuffer it chunk of response according to the protocol.

package kom.handlersocket.result;

import org.jboss.netty.buffer.ChannelBuffer;
import kom.handlersocket.query.HSQuery;
import kom.handlersocket.core.SafeByteStream;

import java.nio.charset.Charset;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class HSResult {
    private final HashMap<HSQuery, List<ChannelBuffer>> resultSet =
        new LinkedHashMap<HSQuery, List<ChannelBuffer>>();
    private final Charset charset;

    public HSResult(Charset charset) {
        this.charset = charset;
    }

    public void add(HSQuery query, List<ChannelBuffer> result) {
        resultSet.put(query, result);
    }

    public void debug() {
        SafeByteStream output = new SafeByteStream(1024, 65536, charset);

        for (Map.Entry<HSQuery, List<ChannelBuffer>> entry: resultSet.entrySet()) {
            entry.getKey().encode(output);
            System.out.print(new String(output.toByteArray(), charset));
            output.reset();

            for (ChannelBuffer buffer : entry.getValue()) {
                System.out.print(buffer.toString(charset));
                System.out.print("-");
            }

            System.out.println();
        }
    }
}

The type of the resultSet reference could be simply Map<...>:

private final Map<HSQuery, List<ChannelBuffer>> resultSet

Reference: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces
Instead of the Map<HSQuery, List<ChannelBuffer>> I'd use Guava's Multimap. It was
designed for this case.
Constructors and methods should validate their input parameters.

public HSResult(Charset charset) {
    this.charset = charset;
}

Does it make sense to have a charset with null? If not, check it and throw an NullPointerException. (Effective Java, Second Edition, Item 38: Check parameters for validity)


A rename utility in Scala I made a commandline tool for renaming files, similar to the rename command in Ubuntu. Here is the code:

import scala.collection.mutable.Map

object Main extends App {
  val usage =
    """
      |A commandline tool for renaming files (written in Scala)
      |
      |Usage:
      |
      |  screname [-a] [-t] -s search_pattern -r replace_pattern filenames
      |
      |Type screname and return to print this message.
    """.stripMargin

  // Print usage and exit
  def printHelpExit() = {
    println(usage)
    System.exit(0)
  }

  if (args.length == 0) {
    printHelpExit()
  }
  val arglist = args.toList
  type OptionMap = Map[Symbol, Any]

  // Is the arg a switch?
  def isSwitch(s: String) = (s(0) == '-')

  // Function for parse args
  def nextOption(map: OptionMap, list: List[String]): OptionMap = {
    list match {
      // List is exhausted
      case Nil => map
      case "-a" :: tail => {
        nextOption(map ++ Map('replaceAll -> true), tail)
      }
      case "-t" :: tail => {
        nextOption(map ++ Map('testRun -> true), tail)
      }
      case "-s" :: searchPattern :: tail => {
        if (map.contains('searchPattern)) throw new IllegalArgumentException("Only one search pattern allowed.")
        nextOption(map ++ Map('searchPattern -> searchPattern), tail)
      }
      case "-r" :: replacePattern :: tail => {
        if (map.contains('replacePattern)) throw new IllegalArgumentException("Only one replace pattern allowed")
        nextOption(map ++ Map('replacePattern -> replacePattern), tail)
      }
      case filename :: tail => {
        map.update('files, filename :: (map.getOrElse('files, List())).asInstanceOf[List[String]])
        nextOption(map, tail)
      }
    }
  }

  val options = nextOption(Map(), arglist)
  // Validate options
  if (!options.contains('searchPattern)) throw new IllegalArgumentException("No search pattern provided")
  if (!options.contains('replacePattern)) throw new IllegalArgumentException("No replace pattern provided")
  if (options.getOrElse('files, List()).asInstanceOf[List[String]].size == 0) throw new IllegalArgumentException("No filenames provided")

  // Rename
  val fileRenamer = new FileRenameByPattern(options.getOrElse('files, List()).asInstanceOf[List[String]], options.getOrElse('searchPattern, "").asInstanceOf[String], options.getOrElse('replacePattern, "").asInstanceOf[String], options.getOrElse('replaceAll, false).asInstanceOf[Boolean])
  if (options.getOrElse('testRun, false).asInstanceOf[Boolean]) {
    fileRenamer.printFileNamePairs()
  } else {
    fileRenamer.rename();
  }
}

import java.io.File

/**
 * Created by IDEA on 17/08/15.
 */

class FileRenameByPattern(val oldFileNames: List[String], val searchPattern: String, val replacePattern: String, val replaceAll: Boolean) {
  val newFileNames = getNewFileNames()

  def getNewFileNames(): List[String] = {
    oldFileNames map {
      (x: String) =>
        if (replaceAll)
          x.replaceAll(searchPattern, replacePattern)
        else
          x.replaceFirst(searchPattern, replacePattern)
    }
  }

  def getFileNamePairs() = {
    oldFileNames zip newFileNames
  }

  def rename(): List[Boolean] = {
    rename(getFileNamePairs())
  }

  def rename(pairs: List[(String, String)]): List[Boolean] = {
    pairs map {
      case (o, n) => new File(o) renameTo new File(n)
    }
  }

  def printFileNamePairs() = {
    val w1 = oldFileNames.map(_.length).max
    val w2 = newFileNames.map(_.length).max
    getFileNamePairs() map {
      case (s1, s2) => println("%%%ds %%%ds".format(w1, w2).format(s1, s2))
    }
  }
}

The -t option is for a dry run.

I am thinking how to make it more extendable, like adding a sequence of numbers at the beginning, appending a date at the end, etc, but any suggestions on improvement are welcome.

Option Parsing

As mentioned in comments, your option passing raises some issues.

The parsing does nothing to enforce the sequence given in the usage
Any argument at any position that is not recognised as part of an option is treated as a filename.

This opens the risk of a range of silent errors, which worries me about a utility which I should trust to operate safely on a (potentially large) number of files.  There is a simple fix:

Move the filename match to the second slot, just after the Nil match.
Have it throw an exception if the Options map does not already contain 'searchPattern and 'replacePattern

That will eliminate all the worrying errors, leaving only the harmless possibility of multiple '-a' and '-t' options.  There are more functional ways to manage the options but that will do enough for this relatively simple requirement.

It seems you've found and adapted the code from the second-highest scoring answer from this SO question.  I'm surprised that was voted up so much.  It's simple, yes, but also

Fragile
Requires a lot of code repetition to do even simple things
Hard to extend without rewriting most or all of the code
Poor example of both style and good practice

(Not that the third point is so important.  But...  nextOption doesn't return the next option, it returns a map of options - it's badly named to reflect an internal implementation detail.  Using list, map and string as variable names is terrible practice, map in particular)

Which library to use

scopt, from the accepted answer in that link, is pretty good.  I know the example looks a mess, but it's been made deliberately overcomplicated to show off every single feature.  For your code, it would be small, much simpler and more expressive.  It groups all the information relevant to an option in one place, including the validation code (and it handles the validation for you, halting as soon as an invalid option is processed, rather than processing them all and then validating them).  It provides a clear way to distinguish between options and parameters.

The documentation could be a bit more detailed and it does assume you know which methods are automatically generated for case classes (e.g. copy, which is used everywhere in the example).  Note that your config class does not have to be a case class - it just saves you some typing.kj

class FileRanameByPattern

In both rename and printFileNamePairs, why use map?  One returns List[Boolean] while the other returns List((), ()) but since you use them both in an if expression, the result is List[Any].  The result is meaningless, so why not use foreach and just return Unit?


cache with least accessed items eviction I wrote this code, in order to implement a cache decorator which handles least accessed eviction.
The role of this decorator is to memoize decorated functions calls with args and kwargs and return the previously computed value if still in cache.
Warning, this handles only serializable args and kwargs, for the sake of simplicity.
Please review it and tell me if this makes sense.
The code:
import json
import hashlib
from collections import OrderedDict

class EvictionCache(OrderedDict):

    def __init__(self, *args, **kwargs):
        max_size = kwargs.pop('max_size', None)
        super(EvictionCache, self).__init__(*args, **kwargs)
        self._max_size = max_size

    @property
    def full(self):
        return len(self) >= self._max_size

    def set(self, hash, value):
        if self.full:
            self.evict()
        super(EvictionCache, self).__setitem__(hash, value)

    def get(self, hash):
        value = super(EvictionCache, self).pop(hash, None)
        if value:
            super(EvictionCache, self).__setitem__(hash, value)
        return value

    def evict(self):
        print 'evicting oldest cached item'
        super(EvictionCache, self).popitem(last=False)

def cache(max_size=None):

    def make_md5(args, kwargs):
        data = dict(args=args, kwargs=kwargs)
        md5 = hashlib.md5(json.dumps(data, sort_keys=True)).hexdigest()
        return md5

    def wrapper(f):
        # make this cache belong to the decorated function to prevent the cache
        # to be shared between different decorated functions
        f._cache = EvictionCache(max_size=max_size)

        def inner(*args, **kwargs):
            md5 = make_md5(args, kwargs)
            res = f._cache.get(md5)
            if res:
                print 'from cache'
                return res

            res = f(*args, **kwargs)
            print 'to cache'
            f._cache.set(md5, res)

            return res

        return inner
    return wrapper

@cache(max_size=2)
def func(x):
    return x * 2

if __name__ == '__main__':

    print func(1)
    print func(2)
    print func(2)
    print func(1)
    print func(2)
    print func(3)
    print func(4)
    print func(5)

output
to cache
2
to cache
4
from cache
4
from cache
2
from cache
4
to cache
evicting oldest cached item
6
to cache
evicting oldest cached item
8
to cache
evicting oldest cached item
10

I don't really feel subclassing a built-in data structure and defining your custom get() and set() methods is a good idea. One of the downsides of the current implementation is that if I would do self.cache[key] = value - this will not go through the cache's set() method and, hence, will not go through the "eviction" check at all. If you are subclassing a dictionary or an ordered dictionary, properly define the __getitem__() and __setitem__() magic methods instead of writing your custom get() and set() on top of it.

Also check this implementation that has a simpler wrapper, but uses a "proxy" "cached function" helper class.

And, here is the source code of the Python's functools.lru_cache for the reference.

Some other minor notes:

use print() as a function for Python-3.x compatibility


Pivot DataFrame with DateTimeIndex I have some data, which I've faked using:

def fake_disrete_data():
    in_li = []
    sample_points = 24 * 4

    for day, bias in zip((11, 12, 13), (.5, .7, 1.)):
        day_time = datetime(2016, 6, day, 0, 0, 0)
        for x in range(int(sample_points)):

            in_li.append((day_time + timedelta(minutes=15*x),
                          int(x / 4),
                          bias))

    return pd.DataFrame(in_li, columns=("time", "mag_sig", "bias")).set_index("time")

fake_disc = fake_disrete_data()

I can pivot each column individually using and then concatenate them using:

cols = list(fake_disc.columns.values)
dfs = []
for col in cols:
    dfs.append(pd.pivot_table(fake_disc,
                              index=fake_disc.index.date,
                              columns=fake_disc.index.hour,
                              values=col,
                              aggfunc=np.mean))

all_df = pd.concat(dfs, axis=1, keys=cols)

But is there a better way to do this?

I'm trying to follow the answers seen in Pandas pivot table for multiple columns at once and How to pivot multilabel table in pandas, but I'm having a difficult time translating their methods to the DateTimeIndex case.

Review

all in all, this code is rather clean. I would use a generator comprehension and itertools.chain in fake_disrete_data instead of the nested for-loop, but that is a matter of taste

linewraps

I prefer to wrap lines after the ( instead of the first argument. Here I follow the same rules as black. This leads to lesser indents, but slightly longer code, for example:

dfs.append(
    pd.pivot_table(
        fake_disc,
        index=fake_disc.index.date,
        columns=fake_disc.index.hour,
        values=col,
        aggfunc=np.mean,
    )
)

list comprehension

instead of the appending, you can do

dfs = [
    pd.pivot_table(
        fake_disc,
        index=fake_disc.index.date,
        columns=fake_disc.index.hour,
        values=col,
        aggfunc=np.mean,
    )
    for col in columns
]

or even better, feed a dict to pd.concat, so you don't have to specify the keys argument

dfs = {
    col: pd.pivot_table(
        fake_disc,
        index=fake_disc.index.date,
        columns=fake_disc.index.hour,
        values=col,
        aggfunc='mean',
    )
    for col in fake_disc.columns
}
pd.concat(dfs, axis=1)

I also changed the np.mean to 'mean', so you don't have to specifically import np for this, and avoided having to create the columns list

Alternative approach

pd.pivot is a wrapper around unstack, groupby and stack. If you want to do something more complicated, you can do those operations by hand

fake_disc = fake_disrete_data()
fake_disc.columns = fake_disc.columns.set_names('variable')
df = fake_disc.stack().to_frame().rename(columns={0: 'value'})
df['hour'] = df.index.get_level_values('time').hour

this creates an intermediary DataFrame

time                variable    value   hour
2016-06-11 00:00:00 mag_sig     0.0     0
2016-06-11 00:00:00 bias        0.5     0
2016-06-11 00:15:00 mag_sig     0.0     0
2016-06-11 00:15:00 bias        0.5     0
2016-06-11 00:30:00 mag_sig     0.0     0
...

This you can group. To group the time per hour, you can use pd.Grouper

pivot = (
    df.groupby([pd.Grouper(level="time", freq="d"), "hour", "variable"])
    .mean()
    .unstack(["variable", "hour"])
    .sort_index(axis="columns", level=["variable", "hour"])
)

  value
variable  bias    ...     mag_sig
hour  0   1   2   3   4   5   6   7   8   9   ...     14  15  16  17  18  19  20  21  22  23
time
2016-06-11    0.5     0.5     0.5     0.5     0.5     0.5     0.5     0.5     0.5     0.5     ...     14.0    15.0    16.0    17.0    18.0    19.0    20.0    21.0    22.0    23.0
2016-06-12    0.7     0.7     0.7     0.7     0.7     0.7     0.7     0.7     0.7     0.7     ...     14.0    15.0    16.0    17.0    18.0    19.0    20.0    21.0    22.0    23.0
2016-06-13    1.0     1.0     1.0     1.0     1.0     1.0     1.0     1.0     1.0     1.0     ...     14.0    15.0    16.0    17.0    18.0    19.0    20.0    21.0    22.0    23.0

performance

according to the %%timeit cell magic in Jupyterlab,
the first approach (with the dict and concat) takes about 23ms, the second approach about 10ms. Depending on your usecase, this difference might be important. If it is not, pick the method which is most readable to your future self


Find valid triples for a sorted list of integers I'm working on a problem in which I have an input array, sorted positive unique integers, and have to try to find all possible triples \$(x,y,z)\$ which satisfy \$x+y>z\$ and \$x<y<z\$. For example, \$(1,2,3)\$ is not a valid triple since \$1+2\$ is not \$> 3\$, and \$(3,4,5)\$ is a valid triple since \$3<4<5\$ and \$3+4>5\$.

This code leverages binary search, and I'm wondering if this can be improved in terms of time complexity. Please also help to point out any code issues/bugs or improvement areas.

Implementation

# find upper bound of value, including value itself
def findUpperBound(numbers, value, start):
    if not numbers:
        raise 'value eror'
    low = start
    high = len(numbers) - 1
    while low <= high:
        mid = (low + high) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] > value:
            high = mid - 1
        else:
            low = mid + 1
    # if reach here, means find an upper bound
    return low

if __name__ == "__main__":

    result = set()
    numbers=[1,2,4,5,6,7,8,10]
    for i in range(0, len(numbers)-2):
        for j in range(i+1, len(numbers)-1):
            k = findUpperBound(numbers, numbers[i] + numbers[j], j+1)
            for p in range(j+1, k):
                result.add((numbers[i], numbers[j], numbers[p]))

    print result

Output

set([(5, 7, 10), (4, 6, 8), (5, 7, 8), (4, 8, 10), (6, 8, 10), (2, 6, 7), (5, 6, 7), (4, 5, 6), (5, 6, 8), (2, 4, 5), (5, 6, 10), (2, 7, 8), (5, 8, 10), (4, 7, 8), (7, 8, 10), (6, 7, 8), (2, 5, 6), (6, 7, 10), (4, 5, 7), (4, 5, 8), (4, 6, 7), (4, 7, 10)])

1. Review

The code is not portable to Python 3 due to the use of the print statement.
The code is not fully organized into functions: most of it runs at the top level of the module. This makes it hard to understand and hard to test.
It's not allowed in Python to raise a string. If you try this you'll get the following:

>>> findUpperBound([], 0, 0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr143389.py", line 4, in findUpperBound
    raise 'value eror'
TypeError: exceptions must derive from BaseException

What you need is something like:

raise ValueError("no numbers")

But it isn't right to raise an exception when there are no numbers to search. The function is supposed to return an index into numbers that is greater than or equal to start and points after all entries less than or equal to value. So if numbers is empty then it should return start.
Functions for binary search of a sorted sequence are already built into Python: see the bisect module. In this case you'll want to use bisect.bisect_left.
The two nested loops for i and j can be combined into a single loop using itertools.combinations. This leads to the revised code:

from itertools import combinations, islice
from bisect import bisect_left

def triangles(seq):
    """Given a sorted sequence of unique numbers, generate triples a, b, c
    that satisfy the triangle inequality, that is, where a + b > c.

    """
    for i, j in combinations(range(len(seq) - 1), 2):
        a, b = seq[i], seq[j]
        for c in islice(seq, j + 1, bisect_left(seq, a + b, lo=j+1)):
            yield a, b, c

In the general case, the number of triples satisfying the conditions is \$O(n^3)\$. Consider as an extreme case the set of numbers \$\{n, n+1, \ldots, 2n\}\$: in this case every triple satisfies the conditions. So in general you don't lose any asymptotic efficiency by iterating over all the triples:

for triple in combinations(numbers, 3):
    a, b, c = triple
    if a + b > c:
        yield triple

2. Answers to questions

In comments, you wrote:

  I think time complexity is the same of your algorithm and my algorithm.

Yes, the algorithms are identical. The point of using itertools.combinations is to reduce the length of the code and make it clearer, not to change the behaviour.
You asked:

  Wondering if you are thinking of any better algorithm which could improve the time complexity even better?

See §1.7 above — in the worst case there are \$O(n^3)\$ triples satisfying the conditions, so no algorithm can have runtime \$o(n^3)\$ in the general case. Possibly for some distributions of inputs it would be possible to do better, but I don't know.
You asked:

  What do you think is the time complexity of current algorithm you are writing in general (I mean average)?

Before you can describe the average runtime of an algorithm, you have to specify the distribution of inputs. With knowing the distribution of inputs, it's impossible to say.