Wrapper function to do polynomial fits with gsl I have two arrays of double, say x and y containing some physical data.
I would like to find the best-fitting polynomial function at a given order:

\$y=pol_n(x)=c_0 + c_1*x + c_2*x^2 + ... + c_n * x^n\$

and return the coefficients (\$c\$) in an std::vector. There are no constraints on the function interface. The GNU Scientific Library, gsl, contains some handy functions to properly do the maths, however those functions are in plain old C. I have encapsulated them in this piece of C++ code:

std::vector<double> gsl_polynomial_fit(const double * const data_x,
                                       const double * const data_y,
                                       const int n, const int order,
                                       double & chisq) {
  gsl_vector *y, *c;
  gsl_matrix *X, *cov;
  y = gsl_vector_alloc (n);
  c = gsl_vector_alloc (order+1);
  X   = gsl_matrix_alloc (n, order+1);
  cov = gsl_matrix_alloc (order+1, order+1);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < order+1; j++) {
      gsl_matrix_set (X, i, j, pow(data_x[i],j));
    }
    gsl_vector_set (y, i, data_y[i]);
  }

  gsl_multifit_linear_workspace * work = gsl_multifit_linear_alloc (n, order+1);
  gsl_multifit_linear (X, y, c, cov, &chisq, work);
  gsl_multifit_linear_free (work);

  std::vector<double> vc;
  for (int i = 0; i < order+1; i++) {
    vc.push_back(gsl_vector_get(c,i));
  }

  gsl_vector_free (y);
  gsl_vector_free (c);
  gsl_matrix_free (X);
  gsl_matrix_free (cov);

  return vc;
}

Although it is pretty much self-contained it doesn't look very safe. With speed and code clarity in mind, what could be done to improve it?

One issue is numerical stability. Although the GSL uses stable routines, the problem of fitting a polynomial in the monomial basis is so ill-conditioned (especially for large ranges in x and large (eg 50) degree), that you risk getting significant errors. Unless you really, really need the coefficients in this basis then I think you should use another basis, for example Legendre or Chebycheff polynomials. This will mean that any code that uses the coefficients will need to know how to do so, but the evaluation is in fact almost as efficient as evaluation in the polynomial basis.


Workaround for overloaded constructor in PHP I have a class whose purpose is to display a comment.  I'd like to be able to instantiate it by passing a Comment object if I happen to have it available, or just the values if that's what I have available at the time.  Unfortunately PHP doesn't allow overloaded constructors, so here's the workaround I came up with.

class CommentPanel extends Panel {
    //Private Constructor, called only from MakeFrom methods
    private function CommentPanel($text, $userName, $timestamp) {
        parent::Panel(0, $top, System::Auto, System::Auto);

        // Render comment
    }

    public static function MakeFromObject(Comment $comment) {
        return new CommentPanel($comment->text, $comment->User->nickname, $comment->last_updated_ts);
    }

    public static function MakeFromValues($text, $userName, $timestamp) {
        return new CommentPanel($text, $userName, $timestamp);
    }
}

So here's the two methods for instantiating a CommentPanel:

$cp = CommentPanel::MakeFromObject($comment);
// or...
$cp = CommentPanel::MakeFromValues($text, $user, $last_updated_ts);
// but not
$cp = new CommentPanel(); //Runtime error

I'm moderately satisfied, although it's not near as intuitive as an overloaded constructor.  Any thoughts on improving this?

Given that php allows optional parameters and doesn't require type checking of parameters that are passed in, you can sort of "fake" an overloaded constructor.

something like this:

class CommentPanel extends Panel {
    public function __construct($text_or_comment, $username=null, $timestamp=null) {
        if (is_string($text_or_comment) {
            $this->textConstructor($text_or_comment, $username, $timestamp);
        }
        else { // assume that it's a comment since it's not a string ... there are better ways to handle this though
            $this->commentConstructor($text_or_comment);
        }
    }

    private function textConstructor($text, username, $timestampe) { /* . . . */ }
    private function commentConstructor(Comment $comment) { /* . . . */ }
}

This method will allow for a more consistent API and one that is perhaps more familiar to Java and C++ developers.

Also, I'm not positive which version of PHP you're targeting, but I believe in the current version, uses __construct instead of the class name as the constructor. I'm not sure if this is preferred but the documentation does say that it checks for __construct first and then the class name style constructor, so I would guess that using __construct() instead of CommentPanel() would reduce runtime ever so slightly. I'm not 100% sure on that though, that's just my understanding. Please correct me if I'm wrong :)


Parse one table out of CSV with multiple titled tables with the Python CSV module I'm looking to parse CSV files containing multiple tables using Python 3's csv module.

These complex CSVs are not unlike the toy example below. My goal is to make an idiom for picking out any one table using a known header row.

Complex CSV file toy.csv:

lists, fruits, books, forks, rope, gum
4, 2, 3, 0, 2, 2

Manhattan Produce Market
id, fruit, color
1, orange, orange
2, apple, red

Books
id, book, pages
1, Webster’s Dictionary, 1000
2, Tony the Towtruck, 20
3, The Twelfth Night, 144

Rope
id, rope, length, diameter, color
1, hemp, 12-feet, .5, green
2, sisal, 50-feet, .125, brown

Kings County Candy
id, flavor, color, big-league
1, grape, purple, yes
2, mega mango, yellow-orange, no

Each table is preceded by a title (except for a garbage table at the start). I save the previous row, and when I match the correct table header, I add the title as a new column.

import csv, re
header = [] #doesn't need to be list, but I'm thinking ahead
table = []

with open('toy.csv', 'r') as blob:
    reader = csv.reader(blob)
    curr = reader.__next__()
    while True:
        prev = curr
        try:
            curr = reader.__next__()
        except StopIteration:
            break
        if not ['id', ' book', ' pages'] == curr:
            continue
        else:
            header.append(prev)
            table.append(['title'] + curr)
            while True:
                try:
                    curr = reader.__next__()
                    if curr == []:
                        break
                    else:
                        table.append(header[0] + curr)
                except StopIteration:
                    break

The first part is to make an idiom which I can simply repeat for each table I want to extract. Later, I will combine the tables into one super-table filling NANs where the table headers don't match.

[['title', 'id', ' book', ' pages'],
 ['Books', '1', ' Webster’s Dictionary', ' 1000'],
 ['Books', '2', ' Tony the Towtruck', ' 20'],
 ['Books', '3', ' The Twelfth Night', ' 144']]

The code is based on this Stack Overflow post.

Happy to hear your suggestions to make the code more compact, idiomatic, and fit for my goals.

In general this code look very nice and seems to follow style guidelines well. I found your code easy to follow.  You asked for:

  ... suggestions to make the code more compact, idiomatic, and fit for my goals.

I will start with a couple of points for compact and idiomatic, and then add something a bit bigger picture.

Only need one stop iteration:

Your main loop uses this construct twice:

try:
    ....
except StopIteration:
    break

But the net result of these is identical, and the inner one could simply be removed.

Acccessing Dunders is generally uneeded:

In several places your code has something like:

curr = reader.__next__()

The idiomatic way to do this is:

curr = next(reader)

The __next__ (dunder next) method is there because that is how an object publishes its interface for next().  And while you can access this, you probably shouldn't.

In addition your entire loop is using next().  I suggest that this likely indicates your iteration structure could use some reworking.  Looking for a more natural iteration element may allow the code to be simplified.

Use natural record breaks:

Now something a little more substantive.

The data structure has a natural break between records as an empty line.  By noting the presence of this empty line in the parsing logic, the parsing logic can get quite a bit simpler. In your code you need to have:

prev = curr

Which is needed to reach back a line to find the category name.  But that same category was already marked via a blank line before.

I started to recast your code as an example of how to take advantage of that blank line, and found it just as easy to read in the entire file. The example below does not preserve the logic of looking for category heads of:

 ['id', ' book', ' pages']

But is was not super clear why in your requirements this was important.  But adding that back into the code below, or taking the resulting data and then finding that record in said data, could also be done.

Recast Parsing Code:

def read_my_csv(filename):
    category = None
    header = None
    record_data = {}
    table = []

    def make_record():
        return [dict(zip(header, x)) for x in table]

    with open(filename, 'rU') as csv_data:
        reader = csv.reader(csv_data)

        for row in reader:
            if not row:
                if category:
                    record_data[category] = make_record()
                table = []
                category = next(reader)[0]
                header = tuple(x.strip() for x in next(reader))
            else:
                table.append([x.strip() for x in row])

    if category:
        record_data[category] = make_record()
    return record_data

Test Code:

import csv
data = read_my_csv('csvfile.csv')
for item in data.items():
    print(item[0])
    for records in item[1]:
        for record in records.items():
            print('   {}'.format(record))
        print()

Results from recast:

Manhattan Produce Market
   ('id', '1')
   ('fruit', 'orange')
   ('color', 'orange')

   ('id', '2')
   ('fruit', 'apple')
   ('color', 'red')

Books
   ('id', '1')
   ('book', 'Websterâ€™s Dictionary')
   ('pages', '1000')

   ('id', '2')
   ('book', 'Tony the Towtruck')
   ('pages', '20')

   ('id', '3')
   ('book', 'The Twelfth Night')
   ('pages', '144')

Rope
   ('id', '1')
   ('rope', 'hemp')
   ('length', '12-feet')
   ('diameter', '.5')
   ('color', 'green')

   ('id', '2')
   ('rope', 'sisal')
   ('length', '50-feet')
   ('diameter', '.125')
   ('color', 'brown')

Kings County Candy
   ('id', '1')
   ('flavor', 'grape')
   ('color', 'purple')
   ('bigleague', 'yes')

   ('id', '2')
   ('flavor', 'mega mango')
   ('color', 'yellow-orange')
   ('bigleague', 'no')


Writing a hiveserver2 query result to CSV with Python using pyhs2 I am trying to create a small application that will help me extract data from Hadoop via hiveserver2 by simply writing it to CSV. At the moment, it takes about 40 seconds to pull 10,000 records from a hs2 table consisting of 500k rows with 203 columns. I would like to think that there is a faster, more efficient way of doing this than the way I am doing it now. Ideally I would like to eventually be able to pull and write 1 million rows per minute. It doesn't necessarily have to be written to CSV. It probably isn't feasible with my current skill level, but I like to set goals for myself.

import pyhs2
import time
import csv

csv_out = open('data.csv', 'wb')
mywriter = csv.writer(csv_out)

def generic_user():
    gu = 'xxxxxx'
    return gu

def password():
    pw = 'xxxxxxx'
    return pw

with pyhs2.connect(host='xxxxxxxx',
               port=10000,
               authMechanism='PLAIN',
               user=generic_user(),
               password=password(),
               database='xxxxxxxxxx') as conn:

    with conn.cursor() as cur:

        q = raw_input('Enter query: ').replace('csc', 'CSC')
        print q

        #timer start
        start_time = time.time()

        #Execute query
        cur.execute(q)

        col = []

        for key in cur.getSchema():
            col.append(key['columnName'])

        header = []
        header.append(col)

        for rows in zip(header):
            mywriter.writerows(rows)

        records = cur.fetch()
        # print records

        for rows in zip(records):
            mywriter.writerows(rows)

pull_time = time.time() - start_time
print pull_time

Speed improvements

Using a for loop to build a list is quite slow, when Python has 'list comprehensions'. They're for loop like expressions that build lists. So your col could be changed from this:

for key in cur.getSchema():
    col.append(key['columnName'])

to this:

col = [key['columnName'] for key in cur.getSchema()]

As far as I can tell, your header is actually pointless. You're making it just a single item list that then gets iterated over to write to your file. This seems to be the same as just mywriter.writerows(col).

Your use of zip is confusing. zip is used to join two or more lists when iterating. It's not normally used for a single list like you have, and doesn't really do much for you unless I'm missing something. It's a redundant drain on your time.

Other notes

You use context managers (with x as y) for the connection which is great, but you should do the same for your csv_out.

with open('data.csv', 'wb') as csv_out:

It's extra safety for your file the same way you have with the connections.

I'd also recommending refactoring your code into discrete functions rather than just one long script. It's better for readability and debugging purposes. Plus it makes it easier to change or reuse this code later.


Find existing player to update or create new one I'm making a game in Java 7, and I have this block of logic when handling an update from the server.

public void handleNewPlayer(Player newPlayer, Player[] otherPlayers) {
    boolean done = false;
    for (Player otherPlayer : otherPlayers) {
        if (newPlayer.id == otherPlayer.id) {
            updatePlayer(otherPlayer);
            done = true;
            break;
        }
    }

    if (!done) {
        createPlayer(newPlayer);
    }
}

The client has a list of players, and gets a player object from the server. If the client already has that player (one with the same id), it updates that existing one, otherwise it creates a new one.

This code looks ugly though. The done flag is really getting under my skin. Is there a better way to organize this to avoid that? Are there any other problems with this code?

Sidenote: createPlayer() and updatePlayer() do very different things, and need to be seperate methods.

A very quick review for the code, and assuming Java < 8:

public void handleNewPlayer(Player newPlayer, Player[] otherPlayers) {
    for (Player otherPlayer : otherPlayers) {
        if (newPlayer.id == otherPlayer.id) {
            updatePlayer(otherPlayer);
            return;
        }
    }

    createPlayer(newPlayer);
}

Some code styles prohibit this because you typically only want to have one return in a function (there's two here), but I typically overlook this for simple methods where the logic ends up clearer in my opinion.

And here's a Java 8 way (might not be optimal)

public void handleNewPlayer(Player newPlayer, Player[] otherPlayers) {
    final Optional<Player> otherPlayer = Arrays.stream(otherPlayers)
        .filter((Player p) -> newPlayer.id == p.id)
        .findFirst();

    if (otherPlayer.isPresent()) {
      updatePlayer(otherPlayer.get());
    }
    else {
      createPlayer(newPlayer);
    }
}

It doesn't do much on the LOC metric, but it has a much clearer semantic meaning.

A comment from Vogel612 brings up the Optional#orElse method. This sounds like a great method, but the only way I can see it used here is as follows:

public void handleNewPlayer(Player newPlayer, Player[] otherPlayers) {
    final Optional<Player> player = Arrays.stream(otherPlayers)
        .filter((Player p) -> newPlayer.id == p.id)
        .findFirst()
        .orElse(newPlayer);

    if (newPlayer == player) {
      createPlayer(newPlayer);
    }
    else {
      updatePlayer(player);
    }
}

I think this has even greater semantic meaning, but your mileage my vary. Additionally, I still feel like we're lacking the conciseness of the final version below.

Finally, you can now use Groovy for Android development. Here's how this can be done in Groovy:

def handleNewPlayer(Player newPlayer, Player[] otherPlayers) {
  def otherPlayer = otherPlayers.find() { newPlayer.id == otherPlayer.id }
  if (otherPlayer) {
    updatePlayer otherPlayer
  }
  else {
    createPlayer newPlayer
  }
}


Simplify series of string manipulations in Ruby I have a series of string manipulation, I realize this with the following code. I want it to be more elegant and readable such as str.sub_heading().sub_codeblock()..., how could I rewrite my code?

def sub_heading(str)
  str.gsub!(/^(#+)\w+/) {|m|  m.gsub("#", "=")}
  str.gsub!(/^(=+)(.+)/, '\1 \2 \1')
end

def sub_codeblock(str)
  str.gsub!(/```(.+\n)((.|\n)+)```/,  '{{{#!text_pygments \1\2}}}')
end

def sub_inlinecode(str)
  str.gsub!(/`(.+)`/, '{{{\1}}}')
end

def sub_bold(str)
  str.gsub!(/([^\w]|^)\*\*\w[\w\s\d\-_'"]*\*\*([^\w]|$)/) {|m|  m.gsub("**", "'''")}
end

def sub_italic(str)
  str.gsub!(/([^*]|^)\*\w[\w\s\d\-_'"]*\*([^*]|$)/) {|m|  m.gsub("*", "''")}
end

def sub_link(str)
  str.gsub!(/\[\[(.+)\|(.+)\]\]/, '[[\2|\1]]')
end

sub_heading(inputdata)
sub_codeblock(inputdata)
sub_inlinecode(inputdata)
sub_bold(inputdata)
sub_italic(inputdata)
sub_link(inputdata)

You may collect the replacements in a Hash and call them on after the other.

replacements = {
  /1/ => ' one ',
  /2/ => ' two ',
  /([34])/ => ' (\1 is three or four) ',
}

test = '123'
replacements.each{|regex, repl|
  test.gsub!(regex, repl)
}
p test

The gsub-version with blocks need a little trick:

replacements = {
  /1/ => ' one ',
  /2/ => ' two ',
  /3/ => Proc.new{|m| m*2},
}

test = '123'
replacements.each{|regex, repl|
  if repl.is_a?(Proc)
    test.gsub!(regex){|m| repl.call(m)}
  else
  test.gsub!(regex, repl)
  end
}
p test

In your case you may define your replacements with:

Replacements = {
  # sub_heading
  /^(#+)\w+/                                    => Proc.new{|m|  m.gsub("#", "=")},
  /^(=+)(.+)/                                   => '\1 \2 \1',
  # sub_codeblock
  /```(.+\n)((.|\n)+)```/                       => '{{{#!text_pygments \1\2}}}',
  # sub_inlinecode
   /`(.+)`/                                     => '{{{\1}}}',
  # sub_bold
  /([^\w]|^)\*\*\w[\w\s\d\-_'"]*\*\*([^\w]|$)/  => Proc.new{|m|  m.gsub("**", "'''")},
  # sub_italic
  /([^*]|^)\*\w[\w\s\d\-_'"]*\*([^*]|$)/        => Proc.new{|m|  m.gsub("*", "''")},
  # sub_link
  /\[\[(.+)\|(.+)\]\]/                          => '[[\2|\1]]',
}

def my_replace(inputstring)
  Replacements.each{|regex, repl|
    if repl.is_a?(Proc)
      inputstring.gsub!(regex){|m| repl.call(m)}
    else
    inputstring.gsub!(regex, repl)
    end
  }
end

my_replace(inputdata)


Finding the largest of a series of numbers being XORed I'm working on solving a problem involving finding the largest of a series of numbers being XORed.

This is the actual problem:

  Xorq has invented an encryption algorithm which uses bitwise XOR
  operations extensively. This encryption algorithm uses a sequence of
  non-negative integers \$x_1, x_2, ... x_n\$ as key. To implement this
  algorithm efficiently, Xorq needs to find maximum value for (\$a\$ xor \$x_j\$)
  for given integers \$a\$, \$p\$ and \$q\$ such that \$p<=j<=q\$. Help Xorq to implement
  this function.

  Input

  First line of input contains a single integer \$T\$ (\$1 <= T <= 6\$). T test
  cases follow.

  First line of each test case contains two integers \$N\$ and \$Q\$ separated
  by a single space (\$1 <= N <= 100,000\$; \$1 <= Q <= 50,000\$). Next line contains
  \$N\$ integers \$x_1, x_2, ... x_n\$ separated by a single space (\$0 <= x_i < 2^{15}\$).
  Each of next Q lines describe a query which consists of three integers
  \$a_i\$, \$p_i\$ and \$q_i\$ (\$0 <= a_i < 2^{15}\$, \$1 <= p_i <= q_i <= N\$).

  Output

  For each query, print the maximum value for (\$a_i\$ xor \$x_j\$) such that
  \$p_i <= j <= q_i\$ in a single line.

I keep failing because of a timeout.  What are some ways in which I could optimize my code to reduce time?

Is there a better way to do the bit manipulation?  Should I be using a different data structure than an array?  I've read a few articles on optimization and changed a few things, but nothing that made a real difference.  Maybe I need to attempt the problem in a different fashion?

#include <stdio.h>

int main (int argc, char * argv[]) {
    unsigned int T,N,Q,i,a,p,q,count,max,n[100000],res[100000];
    scanf ("%d\n%d %d", &T, &N, &Q);
    while (T--) {
        for (i = 0; i < N; i++) {
            scanf ("%d", &n[i]);
        }
        while (Q--) {
            count = 0;
            scanf ("%d %d %d", &a, &p, &q);
            p--;
            q--;
            for (i = p; i <= q; i++) {
                res[count++] = a ^ n[i];
            }
            max = res[0];
            for (i = count; i--;) {
                if (res[i] > max) {
                    max = res[i];
                }
            }
            printf ("%d\n", max);
        }
    }
    return 0;
}

I apologize for all the arbitrarily named variables.  All of these problems just use single character names as their variables.

Putting all variables of the same type onto a single line can be bad for readability and maintenance:

unsigned int T,N,Q,i,a,p,q,count,max,n[100000],res[100000];

Since the single-character variables are similar, they can still be together.  The rest of them, however, should be on separate lines.  Also, since i is a loop counter, it's best to declare it as close as possible to its for loop instead.

unsigned int T, N, Q, a, p, q;
unsigned int count;
unsigned int max;
unsigned int n[100000]
unsigned int res[100000];


First n primes optimization Pretty standard. Generates the first n primes, input via a scanner.

package main;

import java.util.Scanner;

public class Prime_Generator {
   public static void main(String args[]) {
      int n;
      int status = 1;
      int num = 3;

      Scanner scanner = new Scanner(System.in);
      System.out.print("First n primes: ");

      n = scanner.nextInt();
      if (n >= 1) {
         System.out.print("First "+n+" prime numbers are: \n");
         System.out.println(2);
      }

      for (int i = 2; i <=n;) {
         for (int j = 2; j <= Math.sqrt(num); j++) {
            if (num%j == 0) {
               status = 0;
               break;
            }
         }
         if (status != 0) {
            System.out.println(num);
            i++;
         }
         status = 1;
         num++;
      }
   }
}

My question:

How can I improve the efficiency of this code?

Two things:

First, you notice that if I entered "1" as an input, I will get "2," instead of "2".

Second, you check the divisibility of a number n against all numbers from 2 to sqrt(n). This is good, but you can improve it by keeping track of all prime numbers you produce. Whenever you find that p is a prime number, you add it to a list of prime numbers, call it primeList. Now whenever you want to check if n is prime, you can test n against all primes in primeList whose sqrt is less than or equal to n. This way to save on the number of primes to test.

There is a lot of advance theory on finding a prime, but for simple one this is sufficient.


All combinations of a string with special characters I have written a function which generates combinations of string by replacing 1 or more characters by the symbol "*".

The code is as follows:

/**
        this following code is responsible to generate all possible combiantions of letters from a
        word with *
        for eg. word = "fin",
        wordSet --> {fin, fi*, f**, f*n, **n, ***,*in}

*/
public static void generateCombinations(Set<String> words){

        Set<String> wordSet = new HashSet<>();

        for (String word : words){

            StringBuilder asterisk = new StringBuilder("*");

            while (asterisk.length() != word.length()){

                int startIndex = 0;
                while (startIndex + asterisk.length() < word.length()) {
                    String tempWord = word.substring(0, startIndex)
                            + asterisk.toString()
                            + word.substring(startIndex +  asterisk.length());
                    wordSet.add(tempWord);
                    startIndex ++;
                }
                wordSet.add(word.substring(0, Math.abs(startIndex - asterisk.length()+1 ))+ asterisk.toString() );

                //loop condition incrementor
                asterisk.append("*");
            }
            //all *'s
            wordSet.add(asterisk.toString());
            //no *
            wordSet.add(word);
        }
        //System.out.println(wordSet);

    }

However, I think this is a highly inefficient code as I need to do the same operation for all the words in the given Set of words(Set<String> words).

Is there any faster way to generate the same result? Any improvements in the current function to enhance speed and readability?

Well, you can simply find out where the * can be, e.g.:

___, __*, _**, _*_, **_, ***,*__

and then replace:

fin, fi*, f**, f*n, **n, ***,*in

Code:

public static String[] possibleCombinations(String s) {
    int length = s.length();
    char[][] strings = new char[length * (length + 1) / 2][length];
    for (int i = 0; i < strings.length; i++) {
        strings[i] = s.toCharArray();
    }
    strings[0][0] = '*';
    for (int i = 0, j = 0, counter = 0; i < length; i++, counter += length - i + 1, j = i) {
        for (; j < length; j++) {
            for (int k = j; k < length; k++) {
                strings[counter + k - i][j] = '*';
            }
        }
    }
    String[] result = new String[strings.length + 1];
    result[0] = s;
    for (int i = 0; i < strings.length; i++) {
        result[i + 1] = new String(strings[i]);
    }
    return result;
}

It's fairly fast:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
**aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
***aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa***
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa**
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*
length: 50
Time taken: 1064956 nanoseconds

Length: 500
Time taken: 733033361 nanoseconds


JQuery hover with multiple ID's I would like to see if the working code below can be written more elegantly. I am assuming there is a way to parse out the "r" and "h" to condense it down into a function. Any help is much appreciated for learning purposes. There are no parent/sibling relationships in the ID's.

    $('#r1_1').hoverIntent(function(){
        $('#h1_1').toggleClass('vis');
    });
    $('#r1_2').hoverIntent(function(){
        $('#h1_2').toggleClass('vis');
    });
    $('#r1_3').hoverIntent(function(){
        $('#h1_3').toggleClass('vis');
    });
    $('#r1_4').hoverIntent(function(){
        $('#h1_4').toggleClass('vis');
    });
    $('#r1_5').hoverIntent(function(){
        $('#h1_5').toggleClass('vis');
    });
    $('#r2_1').hoverIntent(function(){
        $('#h2_1').toggleClass('vis');
    });
    $('#r2_2').hoverIntent(function(){
        $('#h2_2').toggleClass('vis');
    });
    $('#r2_3').hoverIntent(function(){
        $('#h2_3').toggleClass('vis');
    });
    $('#r2_4').hoverIntent(function(){
        $('#h2_4').toggleClass('vis');
    });
    $('#r2_5').hoverIntent(function(){
        $('#h2_5').toggleClass('vis');
    });
    $('#r3_1').hoverIntent(function(){
        $('#h3_1').toggleClass('vis');
    });
    $('#r3_2').hoverIntent(function(){
        $('#h3_2').toggleClass('vis');
    });
    $('#r3_3').hoverIntent(function(){
        $('#h3_3').toggleClass('vis');
    });
    $('#r3_4').hoverIntent(function(){
        $('#h3_4').toggleClass('vis');
    });

Instead of using ids #r, let's include in the element the attribute data-something to differentiate the elements that must have the behavior setted by the function. Using a div, for instance:

We won't need the ids with #r anymore. Considering that you already have the elements #h* we just need to put the id number inside data-something of the corresponding element, so that the function can use it:

$("div[data-something]").hoverIntent(function() {
    var idNumber = $(this).data("something");
    $('#h' + idNumber).toggleClass('vis');
});

Now, you just need to use the data-something attribute.


Perl project review - Word counter I wrote this perl script that analizes a text and plot out a bar graph of the word occurrences during the text.

Since come mainly from Javascript and PHP, i would like to know how bad is this code and if there is room for improvement and how, any tip will be appreciated!

Thanks!

#!usr/bin/perl -w
use strict;
use warnings;
use GD::Graph::bars;
use GD::Graph::colour;

if (!$ARGV[0]) {
    die "Error:\nPlease supply a txt file and a database of words to exclude\n";
}

my $file = $ARGV[0];
my $dbfile = $ARGV[1];
my $cnt = 0;
my %wordlist = ();
my @db = ();
my $threshold = 18;

binmode STDOUT,"utf8";

open (HNDL,'<:utf8', $file) || die "wrong filename";

if ($dbfile){
    open (HDB,'<:utf8', $dbfile) || die "wrong filename";
    @db = <HDB>; # load file into array
    foreach my $db (@db) {
        # remove newlines
        #$db =~ s/\n\s*//;
        chomp($db);

    }
}

while (my $val = <HNDL>)
{
    my @val = split / /, $val; # split each space build words array

    foreach my $word (@val){
        # clean the word remove newlines
        #$word =~ s/\n\s*//;
        chomp($word);
        # clean the word remove everything until '
        $word =~ s/^.\'//;
        # clean the word remove any nonword characters
        # $word =~ s/[^a-zA-Z_0-9]//;
        # clean the word remove dots and commas
        $word =~ s/,|\.//;

        if (length($word) < 2){
            next;
        };

        # check if the word is to be excluded
        my $exclude = 0;
        if ($dbfile){
            foreach my $dbword (@db) {
            # check if the string contains dbword
            # ^ check for occurence at start
            # $ check for occurence at end
            # /i case insensitive
              if ($word =~ m/^$dbword$/i){
                $exclude = 1;
                #print "Escluso: $word";
              }
            }
        }

        if($exclude == 0) {
          # check word in the hash
            if (exists $wordlist{$word}) {
                #if present augment value by one
                $wordlist{$word}++;
            }else{
            #if not present add
                $wordlist{$word} = 1;
            }
        }else{
            # do nothing
        }

    }
}

# Export CSV

# Print header
print ("Word,Value\n");

# print hash elements for each sorted element
for my $key ( sort { $wordlist{$a} <=> $wordlist{$b} }  keys %wordlist){

        #print "$key ---> $wordlist{$key}\n\n";
        if ($wordlist{$key} >= $threshold){
            print "$key,$wordlist{$key}\n";
            }
    }

# Export Graph
my $graph = GD::Graph::bars->new(1024, 600);

# Build data arrays
my @xdata = ();
my @ydata = ();
my @data = ();
for my $key ( sort { $wordlist{$a} <=> $wordlist{$b} }  keys %wordlist){

        #print "$key ---> $wordlist{$key}\n\n";
        if ($wordlist{$key} >= $threshold){
            push(@xdata,$key);
            push(@ydata,$wordlist{$key});
            }
    }

push (@data,\@xdata);
push (@data,\@ydata);

$graph->set(
    x_label     => 'Words',
    x_label_position => '0.5',
    y_label     => 'Number of Hits',
    title       => 'Number of Hits for Each Word',
    bar_spacing => 5,
    bar_width => 25,
    transparent  => '0',
    bgclr  => 'white'
) or warn $graph->error;

my $image = $graph->plot(\@data) or die $graph->error;

# write file to output
$file =~ s/\.[*]$//;

open(PNGOUT,">","$file.png");

binmode PNGOUT;
print PNGOUT $image->png;

close(PNGOUT);

close (HDB);
close (HNDL);

Use lexical filehandles instead of typeglobs (read here for more about why; the biggest problem with typeglobs is that they are global in scope).

open (my $handle,'<:utf8', $file) || die "wrong filename";

You should close your filehandles sooner rather than waiting til the end of the program, if possible. For example, there's no reason to keep HDB open after its contents have been read into memory.
Consider changing @db to a hash, then using exists to check whether a word is in the exclude list. This should be faster than looping through the array (depending on how many words are in the exclude list and how often a word will be in the list). Since case is not important, you could call lc or uc before testing.

If you want to keep it as an array, then consider exiting the loop using last once the first match is found.
You sort the keys of %wordlist twice using the same criteria. Consider storing the sorted list in a new variable.


Encoding and decoding in Haskell -- 99 Problems exercise 13, 14 I've been working on these solutions to the Haskell 99 questions, encoding and decoding series for a while now, so I figured I ought to present them to see how I screwed up the implementation.

Problems:

  Encoding: Write a function which encodes a series of characters using
  run-length encoding and an algebraic data type such that the sequence
  "aaaabccaadeeee" outputs:

[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

  Decoding: Write a function which decodes a series of algebraic data types  representing run-length encoding as a series of characters such that the sequence

[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

  outputs "aaaabccaadeeee".

Here is the code I used for the problems:

import Data.List

main = do
    print $ decode (encode "Mississippi")

data Encoding = Multiple Int Char | Single Char deriving (Show)

encode :: [Char] -> [Encoding]

encode chars= map toEncoding ( (countChars . group) chars)

    where

    countChars :: [String] -> [(Int, Char)]
    countChars strings = map countCharsHelper strings

    countCharsHelper :: String -> (Int, Char)
    countCharsHelper chars = (length chars, head chars)

    toEncoding :: (Int, Char) -> Encoding
    toEncoding (1, a) = Single a
    toEncoding (num, a) = Multiple num a

decode :: [Encoding] -> [Char]

decode encodings = foldl (++) "" (map replicateChars (map fromEncoding encodings))
    where

    fromEncoding :: Encoding -> (Int, Char)
    fromEncoding (Multiple num char) = (num, char)
    fromEncoding (Single char) = (1, char)

    replicateChars :: (Int, Char) -> [Char]
    replicateChars (num, char) = replicate num char

And the output is the expected output "Mississippi", while decode and encode testing correctly via GHCi.

The general idea, which is to use group and Data.List.group and replicate, is right.  Your implementation is a bit verbose, though.

The top-level functions (encode, decode, and main) should have type signatures.  You didn't write one for main :: IO ().  The inner functions, though, don't need type signatures, since the compiler can infer their types.

Avoid nesting parentheses.  All of your nested parentheses could be written with $ instead.  For example:

print $ decode $ encode "Mississippi"

I don't think you need so many helper functions.

Both encode and decode could be written in point-free style.

Writing decode = foldl (++) "" (map replicateChars (map fromEncoding encodings)) is too complicated.  concatMap would do the trick.

import Data.List (group)

data Encoding = Multiple Int Char | Single Char deriving (Show)

encode :: String -> [Encoding]
encode = map toEncoding . group
  where
    toEncoding (c:[]) = Single c
    toEncoding group  = Multiple (length group) (head group)

decode :: [Encoding] -> String
decode = concatMap fromEncoding
  where
    fromEncoding (Single char)       = [char]
    fromEncoding (Multiple num char) = replicate num char

main :: IO ()
main = do
    print $ decode $ encode "Mississippi"


Max repeated word in a string I was trying to do a very common interview problem "Finding the max repeated word in a string " and could not find much resources in net for c/c++ implementation. So I coded it myself here. I have tried to do most of the coding from scratch for better understanding. Could you review my code and provide comments on my algorithm. Some people have suggested using hashtables for storing the count, but am not using hashtables here.

#include<stdafx.h>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;
string word[10];

//splitting string into words
int parsestr(string str)
{
    int index = 0;
    int i = 0;
    int maxlength = str.length();
    int wordcnt = 0;
    while(i < maxlength)
    {
        if(str[i] != ' ')
        {
            word[index] = word[index] + str[i];
        }
        else
        {
            index++; //new word
            wordcnt = index;
        }
        i++;
    }
    return wordcnt;
}

//find the max word count out of the array and return the word corresponding to that index.
string maxrepeatedWord(int wordcntArr[],int count)
{
    int max = 0;
    int index = 0;
    for(int i = 0; i <= count; i++)
    {
        if(wordcntArr[i] > max)
        {
            max = wordcntArr[i];
            index = i;
        }
    }

    return word[index];
}

void countwords(int count)
{
    int wordcnt = 0;
    int wordcntArr[10];
    string maxrepeatedword;
    for(int i = 0; i <= count; i++)
    {
        for(int j = 0; j <= count; j++)
        {
            if(word[i] == word[j])
            {
                wordcnt++;
                //word[j] = "";
            }
            else
            {}
        }
        cout << " word " << word[i] << " occurs " << wordcnt << " times " << endl;
        wordcntArr[i] = wordcnt;
        wordcnt = 0;
    }

    maxrepeatedword = maxrepeatedWord(wordcntArr,count);
    cout << " Max Repeated Word is " << maxrepeatedword;
}

int main()
{
    string str = "I am am am good good";
    int wordcount = 0;
    wordcount = parsestr(str);
    countwords(wordcount);
}

Here's a long list of feedback. Sorry for the blunt tone, but I'm trying to be brief:

parsestr mutates a global variable but returns a value that's relevant to
that variable (the count). That's inconsistent. Either have it return both
the count and the array (or make things easier on yourself and use a
vector that knows its size), or make the count global too.
You don't handle punctuation characters. Is that a requirement? Should
"a(b)" be one word? Should "a. a" be two unique words?
Do you need to split on characters other than space? What about \t or
\n? Other Unicode whitespace characters?
Your while(i < maxlength) loop could more simply be a for loop.
Building up the word by incrementally contatenating characters onto a
string is slow. It will periodically require dynamic allocation. A more
efficient solution would be to remember the start index of the word. When
you reach the end, create a string from the substring (start, end) in one
step.

Going further from there, there's no reason to even store those words
separately since that start, end pair is enough to reconstruct it as needed.
Your program will mysteriously crash if you pass a sentence with more than
ten words. :( Since you're using dynamic allocation everywhere else (string
does that under the hood) there's no reason to use a fixed array for words.
At the very least, you should have a constant for that size and check that
you don't overflow the array.
index isn't a helpful variable name. Call it wordIndex.
Likewise, wordcnt would be better as wordCount.
maxrepeatedWord is a mixture of camelCase and all lowercase. Be consistent
(and camelCase is generally better since it makes it easier for the reader
to split it into words).
wordcntArr would be better as wordCounts. The fact that it's an array is
self-evident.
i <= count should be just <. Arrays are zero-based, so
wordcntArr[count] is past the last valid element.
index -> indexOfMax.
You're passing count into countwords even though that count is relevant
to a global variable that it accesses directly. Why not just make the count
global too?
The else {} accomplishes nothing. Remove it.
If you declare wordcnt inside the for(int i... loop, you won't have to
reinitialize it each iteration.
int wordcntArr[10] again duplicates the magical literal 10. Use a
constant or, better, a dynamically-sized container.
You're redundantly recounting each word every time it occurs. With
"I am am am good good", you'll get a count array like 1 3 3 3 2 2.
If you had a collection of unique words instead, your \$O(n^2)\$ complexity
would go down to \$O(mn)\$ where \$m\$ is the number of unique words.

A hash table would be a good way to create the set of unique words.
Your test string assumes repeated words will be contiguous (as opposed to,
say "I am good am good am."). Is that intentional? Desirable?

At a high level, your algorithm is also not optimal. You've got \$O(n^2)\$ performance, ignoring the dynamic allocation as you incrementally build up those strings. With that, it gets worse.

I believe the canonical solution to this is (roughly):

create a map of words -> counts
set wordStart to 0
iterate through the string
    if the current character is a word delimiter
        set word to the substring from wordStart to here
        set wordStart to here
        if map contains word
            increment the count for that word
        else
            add the word to the map with a count of 1
        end
    end
end

set maxWord to null
set max to 0
iterate through the map
    if count for this word > max
        set maxWord to this word
        set max to count
    end
end

return maxWord

That gives you \$O(n)\$: you only walk the entire string once.


Returning a list of income for a month My current code takes 2.7-4.5 seconds to complete, is there any way to make it faster?

I need to return a list of the income in all days in a month.  My idea was to loop through the days of one month, but this takes so long should not be a hard task.

What can I improve?  I was thinking on GroupBy a date range.

    public IEnumerable<GetSellInfo> GetSellInvoices(int month, int year, int offset)
{
    DateTime startDate = new DateTime(year, month, 1, 0, 0, 0).AddMinutes(offset);
    DateTime endDate = new DateTime(year, month, DateTime.DaysInMonth(year, month) , 23, 59, 59, 999).AddMinutes(offset);
    DateTime utc = DateTime.UtcNow.AddMinutes(-offset);
    DateTime maxDate = new DateTime(utc.Year, utc.Month, utc.Day, 23, 59, 59, 999).AddMinutes(offset);

    if (endDate > maxDate) endDate = maxDate;

    var invoices =
        db.SellInvoices.Where(invoice => invoice.Date >= startDate && invoice.Date <= endDate);

    List<GetSellInfo> result = new List<GetSellInfo>();
    DateTime counterDate = startDate;

    while (counterDate <= endDate)
    {
        DateTime iDate = new DateTime(counterDate.Year, counterDate.Month, counterDate.Day, 0, 0, 0).AddMinutes(offset);
        DateTime jDate = new DateTime(counterDate.Year, counterDate.Month, counterDate.Day, 23, 59, 59, 99).AddMinutes(offset);
        var dayInvoices = invoices.Where(invoice => invoice.Date >= iDate && invoice.Date <= jDate);

        decimal cfCard = dayInvoices.Select(x => x.CardSettlementSum).DefaultIfEmpty(0).Sum();
        decimal cfCash = dayInvoices.Select(x => x.CashSettlementSum).DefaultIfEmpty(0).Sum();
        decimal depositsCard = dayInvoices.Select(x => x.CardDepositSum).DefaultIfEmpty(0).Sum();
        decimal depositsCash = dayInvoices.Select(x => x.CashDepositSum).DefaultIfEmpty(0).Sum();
        decimal notSyledsDecimal = dayInvoices.Select(x => x.NotStyledsSum).DefaultIfEmpty(0).Sum();
        decimal discountsDecimal = dayInvoices.Select(x => x.DiscountsSum).DefaultIfEmpty(0).Sum();

        result.Add(new GetSellInfo
        {
            Date = counterDate,
            TotalCard = cfCard + depositsCard,
            TotalCash = cfCash + depositsCash,
            DepositsInCard = depositsCard,
            DepositsInCash = depositsCash,
            NotStyleds = notSyledsDecimal,
            Discounts = discountsDecimal,
            Returns = cfCard - depositsCard + cfCash + depositsCash,
            Total = cfCard + depositsCard + cfCash + depositsCash,
        });
        counterDate = counterDate.AddDays(1);
    }

    return result;
}

I'm going to elaborate on what I mentioned in comments.

Assuming you're using LINQ to Entities, this line:

var invoices =
        db.SellInvoices
          .Where(invoice => invoice.Date >= startDate && invoice.Date <= endDate);

does not actually execute the query. It just builds the query, execution is deferred until you call one of the methods that force the materialization of the result set. One of those methods is Sum.

That means you're calling the database 6 times per loop.

If you add .ToList():

var invoices =
        db.SellInvoices
          .Where(invoice => invoice.Date >= startDate && invoice.Date <= endDate)
          .ToList();

You'll just hit the database once, grab the full result set and the rest of the processing will be done in-memory.

In case of not-too-big datasets, that is definitely a viable way to go. Otherwise, you'd have to write a stored procedure to do the processing.


Google Maps marker management for games Is there a better way to design this code? I have read that too many function parameters is a sign of poorly design code, and would love some feedback on this code.
The functions Google Maps markers and update the state.
Also any other feedback unrelated is welcome.
Functions:
// Initialising map and markers
export const handleApiLoaded = (
  games,
  map,
  setGameMarkers,
  setInfoWindow,
  handleMarkerClick
) => {
  const infoWindow = new google.maps.InfoWindow({});

  const gameMarkers = [];
  for (const game of games) {
    const newMarker = createGameMarker(
      map,
      game,
      infoWindow,
      gameMarkers,
      handleMarkerClick
    );

    newMarker ? gameMarkers.push(newMarker) : null;
  }

  // Update state
  setGameMarkers(gameMarkers);
  setInfoWindow(infoWindow);
};

// Create marker object for game
export const createGameMarker = (
  map,
  game,
  infoWindow,
  gameMarkers,
  handleMarkerClick
) => {
  const [lat, lng] = [parseFloat(game.latitude), parseFloat(game.longitude)];

  if (locationIsUnoccupied(lat, lng, gameMarkers)) {
    var icon = {
      url: GAME_ICON_URL,
      scaledSize: new google.maps.Size(30, 45),
    };

    var marker = new google.maps.Marker({
      position: {
        lat: lat,
        lng: lng,
      },
      icon: icon,
      map,
    });

    marker.addListener("click", () => {
      infoWindow.close();
      map.panTo(marker.getPosition());
      handleMarkerClick(marker, map);
      infoWindow.setContent(createGameInfoWindow(game));
      infoWindow.open(map, marker);
    });

    return marker;
  }
};

From a short review;

locationIsUnoccupied and createGameInfoWindow are mysterious, where are they defined?
newMarker ? gameMarkers.push(newMarker) : null; should trigger jshint, I would just go for the if statement
I would structure all the code and functions in to MVC (model view controller)

So GAME_ICON_URL becomes model.GAME_ICON_URL
So createGameInfoWindow becomes ui.createGameInfoWindow
So locationIsUnoccupied becomes model.locationIsUnoccupied

This could make your code look like;
// Initialising map and markers
export function handleApiLoaded(model, ui, controller){
  ui.infoWindow = new google.maps.InfoWindow({});

  model.gameMarkers = [];
  for (const game of games) {
    addGameMarker(game, model, ui, controller);
  }

  //Not sure the below would still make sense?
  model.setGameMarkers(gameMarkers);
  ui.setInfoWindow(ui.infoWindow);
};

// Create marker object for game
export function addGameMarker(game, model, ui, controller){

  const [lat, lng] = [parseFloat(game.latitude), parseFloat(game.longitude)];

  if (model.locationIsUnoccupied(lat, lng, model.gameMarkers)) {
    var icon = {
      url: model.GAME_ICON_URL,
      //Why 30 and 45, a comment would be good here
      scaledSize: new google.maps.Size(30, 45),
    };

    var marker = new google.maps.Marker({
      position: {
        lat: lat,
        lng: lng,
      },
      icon: icon,
      map: model.map,
    });

    marker.addListener("click", () => {
      ui.infoWindow.close();
      //Maybe `map` should be part of `ui`, deep thoughts to be had..
      model.map.panTo(marker.getPosition());
      ui.handleMarkerClick(marker, map);
      ui.infoWindow.setContent(createGameInfoWindow(game));
      ui.infoWindow.open(map, marker);
    });

    model.gameMarkers.push(marker);
  }
};


Efficient bookkeeping in heap I'm trying to implement a heap using list data structure. I'd also like to keep track of the position of elements in the list in order to enable easy deletion. My implementation involves looping through the entire list to update the positions after an insert/delete combo. I'm afraid this raises the time complexity from O(log n) to O(n). Is there a better way of keeping track of elements' position? Currently, update method is what takes care of the bookkeeping.

class heap():
    ''' Min-Heap'''
    def __init__(self,G):
        self.list=[0] #to ease dealing with indices, an arbitrary value at index 0
        self.pos={} #holds position of elements with respect to list
        self.G = G #Graph, contains the score for each element in G[element][2]
def update_pos(self):
    self.pos = {}
    for i in xrange(1,len(self.list)):
        self.pos[self.list[i]]=i

def percUp(self): #percolate up, called by insert method
    start = len(self.list)-1
    while start//2>0:
        if self.G[self.list[start/2]][2] > self.G[self.list[start]][2]:
            self.list[start/2],self.list[start] = self.list[start],self.list[start/2]
        start = start//2

def insert(self,element):
    self.list.append(element)
    self.percUp()
    self.update_pos()

def percDown(self,start=1): #percolate down, called by extract_min method
    while 2*start < len(self.list):
        min_ind = self.getMinInd(start)
        if self.G[self.list[start]][2] > self.G[self.list[min_ind]][2]:
            self.list[start],self.list[min_ind] = self.list[min_ind],self.list[start]
        start = min_ind

def extract_min(self):
    self.list[-1],self.list[1] = self.list[1],self.list[-1]
    small = self.list[-1]
    self.list = self.list[:-1]
    self.percDown()
    self.update_pos()
    return small

def delete(self,pos):
    self.list[-1],self.list[pos] = self.list[pos],self.list[-1]
    self.pos.pop(self.list[pos])
    self.list = self.list[:-1]
    self.percDown(pos)
    self.update_pos()

def getMinInd(self,start):
    if 2*start+1 > len(self.list)-1:
        return 2*start
    else:
        if self.G[self.list[2*start]][2]<self.G[self.list[2*start+1]][2]:
            return 2*start
        else:
            return 2*start+1

Instead of calling update_pos at the end of a heap operation, update it as you go along. For example, percUp becomes:

cur_pos = len(self.list) - 1
parent_pos = cur_pos // 2
while parent_pos:
    cur = self.list[cur_pos]
    parent = self.list[parent_pos]
    if self.G[parent][2] > self.G[cur][2]:
        self.list[parent_pos] = cur
        self.pos[cur] = parent_pos
        self.list[cur_pos] = parent
        self.pos[parent] = cur_pos
    cur_pos = parent_pos
    parent_pos //= 2

And similarly for percDown.
Having written that, a simpler approach to deletion from a heap is simply to leave the object in the heap but mark it somehow as deleted. Then when you extract the minimum you check to see if it was marked as deleted, and if it was, you throw it away and extract another one.
If you use the "mark object as deleted" method, then you would be able to use Python's built-in heapq module (see in particular the "Priority Queue Implementation Notes"). See this answer for an example implementation.
It looks (from the name "G" for the scores) as though you are using this to implement the priority queue of unvisited nodes in the A* search algorithm. But then it is not clear why you need to delete items from the middle of the heap—in the A* algorithm this never happens (an item is only deleted when it is popped as the minimum item). So you could just not implement deletion, and since the pos dictionary is only used by the deletion method, you wouldn't have to maintain it, and so you could just use Python's built-in heaps directly. See this answer for an example.


PHP 7.3.9: Check if uploaded file is an image (I don't care about the format) I just care if it's any of the common formats so that later when I list all files, for those that are images, I can generate previews based on mime type.

So PHP.NET suggest to use exif_imagetype function to check if file is an image. In case of success an integer will be returned indicating one of 18 constants.

The check I do is against an UploadedFile so my method is quite simple. As this is code review. Would you optimize my code to be even better? Thanks for any hints.

/**
 * @link https://www.php.net/manual/en/function.exif-imagetype.php
 *
 * @param UploadedFile $file
 * @return bool
 */
private function isFileImage(UploadedFile $file): bool
{
    $result = exif_imagetype($file->getRealPath());

    return is_int($result) && $result >= 1 && $result <= 18;
}

The method in question does not use $this therefore you might consider making it static.

Further it is a private method, i dont know of which class, but consider making it a public method of its own class.

The method accepts UploadedFile but it is only interested in the real path. As long as you keep it private it could be ok and simpler to call, but if you ever make it public (as suggested above), you should let it accept string path instead, that way it will be more flexible.

There are 18 constants for the image types, but you are using hardcoded numbers. What If another type is added in the future? Do you want to have to modify your code? Check the exif_ imagetype return value doc. It will never return int that is not one of the constants. return is_int($result); is absolutely enough.


Port-scanning with two IPs I am making a Python program with what I learned so far where the user enters two IPs that represents the start and end of the range of IPs to be scanned, then saves the wanted IP in a text file.

   #ip range and scanning
import socket
import sys
ok=[]
def ipscan(start2,port):
    s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.settimeout(2)
    try:
        s.connect((start2,port))
        print start2 ,'-->port %s is Open'%port
        ok.append(start2)
    except: print start2 ,'-->port %s is Closed ! '%port
def iprange(start,end):
    while end>start:
       start[3]+=1
       ipscan('.'.join(map(str,start)),p)
       for i in (3,2,1,0):
          if start[i]==255:
             start[i-1]+=1
             start[i]=0
 #--------------------------------------------#
sta=map(int,raw_input('From : ').split('.'))
fin=map(int,raw_input('to : ').split('.'))
p=input('Port to scan : ')
iprange(sta,fin)
print '-----------end--------------'
of=open('Output.txt','w')
for ip in ok:
    of.writelines(ip+'\n')
of.close()

It seems to be working but I need to be sure, and wanted to know if I can make it any faster, or if there is a better way.

Your naming convention doesnt aid legability. e.g, rename p to port.

Don't do carte blanche exception handling. Be more specific, e.g.:

try:
    ...
except (ValueError, KeyError)
    ...

You are also a miser with your spaces. White space is important for legibility.

explicit is better than implicit so replace ipscan('.'.join(map(str,start)),p) with ipscan(start2='.'.join(map(str,start)), port=p)

Consider replacing while end>start with while end >= start as it allows scanning of a single IP address..

I cans see how the ordering of 3,2,1,0 is important so replace

for i in (3,2,1,0):
     if start[i]==255:
         start[i-1]+=1 #what if
         start[i]=0

with

for i, val in enumerate(start):
    if val == 255:
        start[i] = 0
        start[i-1] += 1

Also, what if item at index 0 == 255? that will cause start[i-1] += 1 to raise an Index Error.

Also, it is not clear why that transformation is being done, so some documentation will be great. Future you will thank present you for it too. Just simply #this does x because of y can suffice.

replace

of=open('Output.txt','w')
for ip in ok:
    of.writelines(ip+'\n')
of.close()

with context and join

with open('Output.txt','w') as of:
    of.write('\n'.join(ok))


Finding common ancestor in a binary tree Following is a Python program I wrote to find the common ancestor in a binary tree (not BST) with no link to parent node. Please review.

def common_ancestor(N1, N2, head):
    if not head:
        return [None, 0, 0]

    left_status = common_ancestor(N1, N2, head.left)
    if left_status[0]:
        return left_status

    this_status = [None, 0, 0]
    if head == N1:
        this_status[1] = 1
    if head == N2:
        this_status[2] = 1

    right_status = common_ancestor(N1, N2, head.right)
    if right_status[0]:
        return right_status

    combined_status = [None, 0, 0]
    combined_status[1] = left_status[1] or this_status[1] or right_status[1]
    combined_status[2] = left_status[2] or this_status[2] or right_status[2]

    if combined_status[1] and combined_status[2]:
        print "Common Ancestor is %s" % head
        combined_status[0] = head

    return combined_status

if __name__ == "__main__":
    head = some_node
    print common_ancestor(5, 32, head)[0]

1. Review

You didn't give us the definition of the node objects, so I'm guessing you used something like this:

from collections import namedtuple
Node = namedtuple('Node', 'left right'.split())

There's no docstring. How do I call common_ancestor? What is the meaning of the arguments N1, N2, and head? (I'm guessing that N1 and N2 are the nodes to find the nearest common ancestor of, and that head had to be the root node of the tree.)
The function common_ancestor does two things: it finds a node and prints a message about it. It would be better to separate these responsibilities.
The print statement means that the code is not portable to Python 3.
The function allocates a new list of three status elements for each node in the tree. But as we'll see below, we only need a total of two status elements.
The test head == N2 is not quite right. Here we need the actual node N2, not just any node that happens to be equal to N2, so the test should use is rather than ==.

2. Simpler implementation

The function common_ancestor traverses the tree in depth-first order, keeping track of which of N1 and N2 have been visited so far. So let's start with a simple depth-first traversal implementation:

def traverse(node):
    """Visit all nodes in the tree starting at node, in depth order."""
    if node is None: return
    traverse(node.left)
    traverse(node.right)

Here's a binary tree with two shaded nodes that we want to find the common ancestor of. The thin line shows the order in which nodes are visited by a depth-first traversal.

Suppose that we augment this traversal function so that it keeps track of how many of n1 and n2 have been visited so far:

count = 0
def traverse(node):
    """Visit all nodes in the tree starting at node, in depth order."""
    if node is None: return
    print("Entering {}, count={}".format(node, count))
    if node is n1: count += 1
    if node is n2: count += 1
    traverse(node.left)
    traverse(node.right)
    print("Exiting {}, count={}".format(node, count))

This figure shows the value of count on entry to each node:

And this figure shows the value of count on exit from each node:

You'll see that all the common ancestors of the two nodes have count = 0 on entry and count = 2 on exit (and only common ancestors have this property). So that means that we can implement common_ancestor like this:

def common_ancestor(n1, n2, head):
    """Return the nearest common ancestor of nodes n1 and n2 in the tree
    rooted at head.

    """
    count = 0   # How many nodes in {n1, n2} have been visited so far?
    ancestor = None

    def traverse(node):
        nonlocal count, ancestor
        if node is None or ancestor is not None: return
        count_at_entry = count
        if node is n1: count += 1
        if node is n2: count += 1
        traverse(node.left)
        traverse(node.right)
        if count_at_entry == 0 and count == 2 and ancestor is None:
            ancestor = node

    traverse(head)
    return ancestor

The nonlocal statement was new in Python 3, so if you're stuck on Python 2 then you'll have to find a workaround, for example using a status object:

class Status(object): pass
status = Status()
status.count = 0
status.ancestor = None
# etc.

3. Efficient implementation?

The implementation discussed here has to traverse the whole tree and so takes time \$ O(n) \$. Whether this is important depends on how many common-ancestor queries you have. If there are many, then you'll probably want to change your tree data structure so that you can make efficient common-ancestor queries.

Adding parent pointers allows you to bring the query cost down to \$ O(\log n) \$ on balanced trees but if you have many common-ancester queries then you may prefer to preprocess the tree into a data structure that suppose \$O(1)\$ queries. See Bender and Colton (2000) for an approach based on range-minimum queries.


Find and replace String with a substring result I was asked this recently, and I couldn't figure out the best way. We are trying to replicate Google's search results where the search terms are bolded (using a b tag) in the results.

Input                       Terms               Output
The search is cool          {sea}               The search is cool

Originally, I thought this was pretty easy:

String results(String input, String[] terms)
{
   for(String term : terms)
   {
      input = input.replace(term, "" + term + "");
   }

   return input;
}

However, this isn't correct. For example:

Input                       Terms               Output
The search is cool          {sea, search}       The search is cool

I struggled to figure out the best way to approach this. Obviously we can no longer find and replace immediately. I played around with using a Map<Integer,String> where the key is the index returned by input.indexOf(term) and the value is the term, but this seemed potentially unnecessary. Any improvements?

public String results(String input, String[] terms)
{
   Map<Integer, String> map = new HashMap<Integer,String>();
   for(String term : terms)
   {
      int index = input.indexOf(term);
      if(index >= 0)//if found
      {
          String value = map.get(index);
          if(value == null || value.length() < term.length())//use the longer term
              map.put(index, term);
      }

   }

   for(String term: map.values())
   {
       input = input.replace(term, "" + term + "");
   }

   return input;
}

I would go with Regex for this, with greedy matches so that nested results like your example above would only match the outer string.

So with your example here:

Input                       Terms               Output
The search is cool          {sea, search}       The search is cool

A Regex pattern of search|sea could be derived from the search terms, and only 'search' would be matched. Note that the longest term will need to first for this to work as desired.

String results(String input)
{
 String retVal = input.replaceAll("search|sea", "$1")

 return input;
}

I think this should be close to what you need, but I havn't had time to test and check. Hope it helps.


JavaScript function to generate tree object from flat object The following function takes an object of items in the format of

{
  'complex-key': 'value',
  // Repeat
}

where complex-key is a key delimited by dots, and returns an object in the form of a tree, where you can access the value by traversing the parts of the complex keys as keys in the object (see examples below).

The function

function createMessages(items) {
    var result = {};
    Object.keys(items).forEach(function(key) {
        var keyParts = key.split('.');
        var currentObj = result;
        while (keyParts.length > 0) {
            var currentKey = keyParts.shift();
            if (keyParts.length === 0) {
                var currentItems = {};
                if (currentObj[currentKey]) {
                    currentItems = currentObj[currentKey];
                }
                currentObj[currentKey] = function() { return items[key]; };
                Object.keys(currentItems).forEach(function(currentItemKey) {
                    currentObj[currentKey][currentItemKey] = currentItems[currentItemKey];
                });
            }
            else if (!currentObj[currentKey]) { currentObj[currentKey] = {}; }
            currentObj = currentObj[currentKey];
        }
    });
    return result;
}

Examples

var message1 = createMessages({'a.b.c.d': 42});
console.log(message1.a.b.c.d() === 42); // true

var message2 = createMessages({'a.b.c.d': 42, 'a.b.c.e': 43});
console.log(message2.a.b.c.d() === 42); // true
console.log(message2.a.b.c.e() === 43); // true

var message3 = createMessages({'a.b.c.d': 42, 'a.b.c': 43});
console.log(message3.a.b.c() === 43); // true
console.log(message3.a.b.c.d() === 42); // true (properties on the functions)

The current function looks overly bloated and inefficient (with \$O(n\times m)\$ at best, and \$O(n\times m^2)\$ at worst). While this is going to be used for test code only, and to small objects only (no more than 10 keys), I would still want to find a way to make it prettier and more efficient. Would appreciate any and all help.

Here is what I'd do. I'd split it into two actions - adding a single property and assigning them all.

Adding a single property is just adding a function if it's something like "a", and it's adding a property to a sub-object if it's something like "a....". So let's use recursion and break it up into those two use cases:

If it's at length one , create the function (but keep all the keys for the third example).
If it's more, call it recursively and create a property.

This translates to the following JS:

function walkTheChain(arr, val, obj){
  if(arr.length === 1) return obj[arr[0]] = Object.assign(() => val, obj[arr[0]]);
  if(!(arr[0] in obj)) obj[arr[0]] = {};
  walkTheChain(arr.slice(1), val, obj[arr[0]]);
}

Now, creating the whole object is just a matter of applying it to all the keys passed in:

function createMessages(map){
  var obj = {};
  for(var key in map) walkTheChain(key.split("."), map[key], obj);
  return obj;
}


Percentage based drop prize on Mob entity kill I have created a simple percentage-based random prize drop for killing certain mobs.
A drop is basically what the player will get in return for killing a mob, as a reward.

So I have a large list of Mobs saved in an XML file which looks like this:

<?xml version="1.0" encoding="UTF-8"?>
<drops>
    <npc id="1">
        <drop item="175" amount="1" chance="0.001" />
        <drop item="174" amount="5" chance="0.013" />
        <drop item="173" amount="1" chance="0.158" />
        <drop item="172" amount="1" chance="0.098" />
    </npc>
</drops>

Basically each NPC has its own ID, so that way we can easily decide what drops does a certain NPC can drop.

So for NPC '1' we have 4 drops, the hardest to get drop is 0.001 (1/1000) and the easiest one is 0.158.

To make the drop system percentage based, I used SecureRandom and the nextFloat() method to generate the base drop rate for the NPC.

After I got the rate, I go through all of the drops that the NPC can drop, and find the drop with the closest drop chance rate to the generated random float rate.

I do this like that:

/**
 * Gets a random drop for NPC by random percentage
 * @param npc       The NPC id
 * @return  The drop details
 */
public Drop getRandomDrop(int npc) {
    List<Drop> drops = this.drops.get(npc);

    /**
     * The random drop rate
     */
    float rate = random.nextFloat();

    /**
     * The closest distance to rate
     */
    float bestDistance = Float.MAX_VALUE;

    // Closest's drop instance
    Drop closest = null;

    for (Drop d : drops) {
        float rt = d.getChance();
        if (rt == rate) {
            return d;
        }

        float distance = Math.abs(rt - rate);
        if (distance < bestDistance) {
            bestDistance = distance;
            closest = d;
        }
    }

    return closest;
}

But I feel that I can make the drops system more accurate, as in this approach is not accurate enough. I need some reviews and suggestions on my approach.

/**
 * Gets a random drop for NPC by random percentage
 * @param npc       The NPC id
 * @return  The drop details
 */
public Drop getRandomDrop(int npc) {
    List<Drop> drops = this.drops.get(npc);

    float roll = random.nextFloat();

    for ( Drop d : drops ) {
        float chance = d.getChance();
        if ( roll < chance ) {
            return d;
        }

        roll -= chance;
    }

    // if no drop was selected, return an empty drop
    return Drop::EMPTY_DROP;
}

This is how I would write it.  Note that I changed the random variable to be called roll like a roll of a die.  For each drop, it compares the roll to the chance of getting that drop.  If the roll is less than the drop rate, then that drop is the loot.  Otherwise, reduce the roll by the drop chance (which makes subsequent drops more likely).

This method assumes that the drop chances in the XML add up to 1 or that there is an implicit chance of an empty drop.  If you want to always drop and have drop chances that don't add up to 1, you can normalize the rate.

float totalChance = 0.0;
for ( Drop d : drops ) {
    totalChance += d.getChance();
}

and then in the current loop

        float chance = d.getChance() / totalChance;

You may still have to do some adjustment to get the rounding right in the case of a maximum random.nextFloat result.

You would set the EMPTY_DROP to be a static class constant representing no loot.  Note that this would also be the drop if the NPC's section was missing from the XML file.


Manage connection without 'using' statement I replace this common statement:

using (var connection = new MySqlConnection(connectionString))
{
     connection.Open();
     // Do work here; connection closed on following line.
}

With this connection manager class that I made:

public class ConnectionBase : IConnectionBase
{
    private static readonly string ConnString =
        ConfigurationManager.ConnectionStrings["ConnStr"].ConnectionString;

    private static readonly Lazy<MySqlConnection> ConnectionString =
        new Lazy<MySqlConnection>(() => new MySqlConnection(ConnString));

    private IDbConnection _db;

    public IDbConnection Db
    {
        get
        {
            if (_db != null) return _db;

            _db = ConnectionString.Value;
            if (_db.State == ConnectionState.Closed) _db.Open();
            return _db;
        }
    }

    public void Dispose()
    {
        if (_db != null)
            _db.Dispose();
    }
}

And wired up to my repository like this:

public abstract class BaseRepository
{
    protected readonly IDbConnection _repository;

    public BaseRepository(IConnectionBase connection)
    {
        _repository = connection.Db;
    }
}

Then I use it on top of the dapper method (since it contains connection.close() at the end of every method that it used).

public class MyTableRepository : BaseRepository
{
    public MyTableRepository(IConnectionBase connection) : base(connection) {}

    public List<MyTable> GetAllMyTable()
    {
        return _repository.Query("SELECT * FROM MyTable").ToList();
    }

}

It's been working great thus far for quite some time in production.

Are there any side effects for this implementation since it doesn't explicitly state to dispose the IDbConnection object?

I can understand why you want to remove the clutter from your code - but sharing the instance of MySqlConnection isn't a good idea. As soon as multiple threads are trying to use the connection at the same time, things are going to go wrong.

The connections are already pooled for you (See here) so you creating and disposing IDbConnections is cheap and easy.

I think you should create a connection factory:

public interface IConnectionFactory
{
    IDbConnection GetOpenConnection();
}

public class ConnectionFactory : IConnectionFactory
{
    private static readonly string connectionString =
        ConfigurationManager.ConnectionStrings["ConnStr"].ConnectionString;

    public IDbConnection GetOpenConnection()
    {
        // Is there an overload to automatically open the connection?
        var connection = new MySqlConnection(connectionString);
        connection.Open();
        return connection;
    }
}

Then your base repository can do:

public abstract class BaseRepository
{
    protected readonly IConnectionFactory connectionFactory;

    public BaseRepository(IConnectionFactory connectionFactory)
    {
        this.connectionFactory = connectionFactory;
    }
}

Then all of your actual repositories can do:

public class MyTableRepository : BaseRepository
{
    public MyTableRepository(IConnectionFactory connectionFactory) : base(connectionFactory) {}

    public List<MyTable> GetAllMyTable()
    {
        using (var connection = connectionFactory.GetOpenConnection())
        {
            return connection.Query("SELECT * FROM MyTable").ToList();
        }
    }
}

I realise it doesn't save you much over the original code other than centralising the connection string...

A more advanced idea would be add an Execute method to your base repo but I don't think it would add much...

protected T Execute<T>(Func<IDbConnection, T> query)
{
    using (var connection = connectionFactory.GetOpenConnection())
    {
        return query(connection);
    }
}


Mailmerge from Excel to premade template in Word I've written the following code to take data from the Excel file "Data" and use it for a mailmerge in a prepare Word template named "Template." I'm new to using VBA in word or Access, so any feedback in these areas is very welcome

Sub AccessTransfer()

Dim strPath As String
Dim objAccess As Access.Application
Dim strExcelPath As String
Dim lastRow As Long
lastRow = Sheets("Data").Cells(Rows.Count, 1).End(xlUp).row
Dim rng As Range
Set rng = Sheets("Data").Range("A" & lastRow, "M" & lastRow)
strPath = "L:\...\MailMergeTEMPDB.accdb"
Set objAccess = CreateObject("Access.Application")
Call objAccess.NewCurrentDatabase(strPath)
objAccess.Visible = False
strExcelPath = Application.ActiveWorkbook.FullName
Set objAccess = New Access.Application
Call objAccess.OpenCurrentDatabase(strPath, False)
objAccess.Visible = False
Call objAccess.DoCmd.TransferSpreadsheet(acImport, _
acSpreadsheetTypeExcel8, "MailMergeTable", strExcelPath, _
True, Range:="Data!")
Access.Application.CloseCurrentDatabase

Dim wdApp As Object, newDoc As Object
    Dim strFile As String
    strFile = "L:\...Template.docm"
    Set wdApp = CreateObject("Word.Application")
    wdApp.Documents.Open strFile, ReadOnly:=False
    wdApp.Visible = True
    wdApp.Run "Project.Module1.WordMailMerge"
    Kill "L:\....MailMergeTEMPDB.accdb"
End Sub

And then Macro called from within Word is:

Sub WordMailMerge()
Dim strFile As String
strFile = "L:\...MailMergeTEMPDB.accdb"
    ActiveDocument.MailMerge.OpenDataSource Name:= _
        strFile _
        , ConfirmConversions:=False, ReadOnly:=False, LinkToSource:=True, _
        AddToRecentFiles:=False, PasswordDocument:="", PasswordTemplate:="", _
        WritePasswordDocument:="", WritePasswordTemplate:="", Revert:=False, _
        Format:=wdOpenFormatAuto, Connection:= _
        "Provider=Microsoft.ACE.OLEDB.12.0;User ID=Admin;Data Source=strFile;Mode=Read;Extended Properties="""";Jet OLEDB:System database="""";Jet OLEDB:Registry Path=""""" _
        , SQLStatement:="SELECT * FROM `MailMergeTable`", SQLStatement1:="", _
        SubType:=wdMergeSubTypeAccess
    With ActiveDocument.MailMerge
        .Destination = wdSendToNewDocument
        .SuppressBlankLines = True
        With .DataSource
            .FirstRecord = wdDefaultFirstRecord
            .LastRecord = wdDefaultLastRecord
        End With
        .Execute Pause:=False
    End With
    Windows("AH_MacroMailMergeTemplate").Activate
    ActiveDocument.Close
End Sub

I'm also new to using VBA to navigate trough directories, so feedback in this aspect would be appreciated too.

There's no need to Call anything, it's obsolete. Instead just use Sub argument, argument.

What's this

Kill "L:\....MailMergeTEMPDB.accdb"

Is this closing the access object? Is this deleting the file? Be explicit - Kill isn't something you generally want to see in any code.

FSO.Deletefile strPath


Perl script to rename files in a directory tree I'm taking a scripting language course with no prior scripting language or Linux experience, though I've taken classes in VB, Java, and C++. Our first assignment is to write a script that will traverse the directory tree of the location the script is run from and rename the files according to some predetermined rules. In this case, directories are to have spaces, \", and any .hxx or .cxx extensions removed. Files get the same treatment except their extensions are changed to .h or .cpp respectively. Also, the script isn't supposed to actually change the file names, just produce a file with the commands to do so, mine are bash commands in the form of mv 'old file name' 'old_file_name'.

#!/usr/bin/perl -w

use Cwd;
use File::Find;
use strict;

my $file = "output.txt";
my $dir = getcwd;

# Creates file to print output to, Die with error message if we can't open it
open my $fh, '>>', $file
    or die "$file: $!\n";

# traverse the directory tree
find(\&process_files, $dir);

# creates a file of bash rename scripts
sub process_files
{
    my $s1 = $_;
    if (-f)
    {
        $s1 =~ s/\s/_/g;
        $s1 =~ s/\"//g;
        $s1 =~ s/\.cxx/\.cpp/g;
        $s1 =~ s/\.hxx/\.h/g;
        print $fh "mv '" , $_ , "' " ,  $s1 , "\n";
        print "mv '" , $_ , "' " ,  $s1 , "\n";
    }
    if (-d)
    {
        $s1 =~ s/\s/_/g;
        $s1 =~ s/\"//g;
        $s1 =~ s/\.(cxx|hxx)//g;
        print $fh "mv '" , $_ , "' " ,  $s1 , "\n";
        print "mv '" , $_ , "' " ,  $s1 , "\n";
    }
}
close $fh;

It seems correct to me except these lines:

$s1 =~ s/\.cxx/\.cpp/g;
$s1 =~ s/\.hxx/\.h/g;
$s1 =~ s/\.(cxx|hxx)//g;

There're no needs to do the substitution g lobal and also you need to anchor the regex at the end:

$s1 =~ s/\.cxx$/.cpp/;
$s1 =~ s/\.hxx$/.h/;
$s1 =~ s/\.(cxx|hxx)$//;


Sum of Squares/Square of Sum Difference I am doing Project Euler problem #6. This is the question it asks:

  The sum of the squares of the first ten natural numbers is,

  $$1^2 + 2^2 + \ldots + 10^2 = 385$$

  The square of the sum of the first ten natural numbers is,

  $$(1 + 2 + \ldots + 10)^2 = 55^2 = 3025$$

  Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

  Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

My implementation in Python is as follows:

def sum_of_squares(n):
    return sum([i**2 for i in range(1, n+1)])

def square_of_sum(n):
    return sum(range(1, n+1)) ** 2

print square_of_sum(100) - sum_of_squares(100)

It works but I was wondering if my implementation is good and fast enough?

Implementation is good indeed, but I have some reservations calling it fast. Its complexity is O(n). As usual (including, but not limited to, Project Euler), an ultimate optimizer is math. Recall that

  $$ 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$$

and

  $$ 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$$

so the result

  $$ \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(n-1)n(n+1)(3n+2)}{12}$$

can be achieved in O(1) time.


Largest Sum Contiguous Subarray - Kadene's algorithm I am looking forward to an answer to improve this code?
Thanks.
Test class
package test;

import main.algorithms.LargestSumContiguousSubarray;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class LargestSumContiguousSubarrayTest {

    LargestSumContiguousSubarray largestSumContiguousSubarray;

    @Before
    public void setUp(){
        largestSumContiguousSubarray = new LargestSumContiguousSubarray();
    }

    @Test
    public void testSumContiguousSubArray(){
        int[] a = {-2, -3, 4 - 1, -2, 1, 5, -3};
        int sum = 7;
        Assert.assertEquals(sum, largestSumContiguousSubarray.kadenesAlgo(a));
    }

}

LargestSumContiguousSubarray.java class
package main.algorithms;

public class LargestSumContiguousSubarray {

    // O(n)
    // Kadene's algorithm
    public int kadenesAlgo(int[] a) {

        // This is also works for negative numbers
        int max_so_far = a[0];
        int curr_max = a[0];

        for(int i=0;i<a.length; i++){
            curr_max = Math.max(a[i], curr_max+a[i]);
            max_so_far = Math.max(max_so_far, curr_max);
        }
        return max_so_far;
    }
}

I have some suggestions for your code.
Replace the for loop with an enhanced 'for' loop
In your code, you don’t actually need the index provided by the loop, you can use the enhanced version.
before
for (int i = 0; i < a.length; i++) {
//[...]
}

after
for (int current : a) {
//[...]
}

Variable and parameter name should be in camelCase style
The variables should be in camelCase.


Replace anchor tags and force create new tag with custom attributes I'm just use the add_filter('the_content', function($content){}); for filtering anchor tags in a post.

Basically, I want filter anchor tags to appropriate format. I want to add custom attributes like rel="nofollow noopener" and target="_blank" if the anchor tag linked to external of my WordPress site.

Instead checking and replace if rel or target is already exists in the anchor tag, I just need to retrieve the value of href and the value of the anchor tag itself (value). So I can force create an anchor tags with my preferred custom attributes.

Here's my current working function:

add_filter('the_content', function($content) {
    $internal = get_home_url();

    return preg_replace_callback('#([^>]*)#i', function($match) use ($internal) {
        if(stripos($match[1], $internal) || strpos($match[1], "#") == 0) {
            return "$match[2]";
        } else {
            return "$match[2]";
        }
    }, $content);
});

I'm worried about performance because this function run each user read a post. Any suggestions are welcome.

I must recommend that you favor accuracy over performance.  After all, what good is a fast loading site if it doesn't provide the correct/intended content.

When parsing valid html, please always leverage a good dom parser.  Regex is "dom-unaware" and therefore is more vulnerable to breakage.

Here is a demonstration of how to use DOMDocument and XPath to articulately replace hyperlinks in your document in a stable manner:

Code: (Demo)

$html = <<<HTML

hello FYI later
no quoted attributes
<A href="https://external.com"
title="some title"
data-key="{\'key\':\'adf0a8dfq<>*1$4%\'">a link with data attribute
and
this is not a hyperlink but simply an anchor tag
Jumper

HTML;

$internal = 'https://example.com';

$dom = new DOMDocument;
$dom->loadHTML($html, LIBXML_HTML_NOIMPLIED | LIBXML_HTML_NODEFDTD);
$xpath = new DOMXPath($dom);
foreach ($xpath->query("//a[@href]") as $node) {
    $replacementNode = $dom->createElement("a", $node->nodeValue);
    $href = $node->getAttribute('href');
    $replacementNode->setAttribute('href', $href);
    if($href[0] != "#" && stripos($href, $internal) === false) {
        $replacementNode->setAttribute('rel', 'nofollow noopener');
        $replacementNode->setAttribute('target', '_blank');
    }
    $node->parentNode->replaceChild($replacementNode, $node);
}
echo $dom->saveHTML();

Output:

hello FYI later
no quoted attributes
a link with data attribute
and
this is not a hyperlink but simply an anchor tag
Jumper

Will this be slow?  Well, I presume it will be slower than regex but then that is the cost of implementing a superior processing tool.  If you need to gain performance, investigate other avenues which will not spoil your content.  This is not a task where a shortcut is a good idea.


Digital persona fingerprint verification takes a lot of time I'm using Digital Persona U.are.U 4000b fingerprint reader and I have this function that verifies the fingerprint from SQL server

My problem is the loop because it takes a lot of time to compare the templates.

Please give me some advice on how can I optimize or revise my code.

CODE:

Protected Sub Process(ByVal Sample As DPFP.Sample)
    con = New SqlConnection

    con.ConnectionString = "Data Source=Test;Initial Catalog=TestDB;Persist Security Info=True;User ID=sa;Password=Passw0rd"

    Dim command As String = "SELECT * FROM Bio_Emplist"

    Dim da As New SqlDataAdapter(command, con)
    Dim dtb As New DataTable
    da.Fill(dtb)
    If dtb.Rows.Count > 0 Then
        rowCount = dtb.Rows.Count
        Try
            For Each dr As DataRow In dtb.Rows
                Dim fpt As Byte() = CType(dr("Fpt"), Byte())

                Dim ms As New MemoryStream(fpt)
                Dim tmpObj As DPFP.Template = New DPFP.Template
                Dim verify As DPFP.Verification.Verification = New DPFP.Verification.Verification

                Template = tmpObj
                tmpObj.DeSerialize(fpt)

                DrawPicture(ConvertSampleToBitmap(Sample))

                Dim features As DPFP.FeatureSet = ExtractFeatures(Sample, DPFP.Processing.DataPurpose.Verification)
                ' Check quality of the sample and start verification if it's good
                If Not features Is Nothing Then
                    ' Compare the feature set with our template
                    Dim result As DPFP.Verification.Verification.Result = New DPFP.Verification.Verification.Result()
                    verify.Verify(features, Template, result)
                    'UpdateStatus(result.FARAchieved)

                    If result.Verified Then
                        MakeReport("The fingerprint was VERIFIED.")

                        empID = dr("EmpID")
                        empFName = dr("FName")
                        empLName = dr("LName")
                        SetVerifyText(empID, empFName, empLName)
                        Exit Try
                    Else
                        FailedVerifyText()
                        If rowCount = 1 Then
                            MakeReport("The fingerprint was NOT VERIFIED.")
                        Else
                            rowCount = rowCount - 1
                            MakeReport("Finding Match...")
                        End If
                    End If
                End If
            Next
        Catch ex As Exception
            MsgBox(ex.ToString)
        End Try
    End If
End Sub

Remove everything that is repeated in the loop and return/do the same thing. Put them outside the loop. Example, this draw the same image every time, you only need it once.

DrawPicture(ConvertSampleToBitmap(Sample))

And this seems to get the same feature every time.

Dim features As DPFP.FeatureSet = ExtractFeatures(Sample, DPFP.Processing.DataPurpose.Verification)


List with object and index filtering out the object depends upon the index present at list I have a following list which indicates the indexes.

 List<Integer> integerList = Arrays.asList(1, 3, 5, 6); // index

I have the following collection of objects.

Collection<Test> testCollection = new ArrayList<>();

Test test01 = new Test(0, "A"); // 0
Test test02 = new Test(1, "B"); // 1
Test test03 = new Test(2, "C"); // 2
Test test04 = new Test(3, "D"); // 3
Test test05 = new Test(4, "E"); // 4
Test test06 = new Test(5, "F"); // 5

testCollection.add(test01);
testCollection.add(test02);
testCollection.add(test03);
testCollection.add(test04);
testCollection.add(test05);
testCollection.add(test06);

The integerList has indexes which are present on testCollection. I want to filter out the testCollection which will have object consisting the index 1, 3, 5. Index 6 is not present on object collection.

I wrote the code as below example. Is there any better as like Java 8 way?

List<Test> testList = new ArrayList<>(testCollection);
List<Test> newTestList = new ArrayList<>();

for (Integer integer : integerList) {

  for (int j = 0; j < testList.size(); j++) {

    if (integer == j) {
      newTestList.add(testList.get(j));
    }
  }
}
System.out.println(newTestList);

It will have the following output as result:

[Test{id=1, name='B'}, Test{id=3, name='D'}, Test{id=5, name='F'}]

The class Test has following information.

class Test {
  private int id;
  private String name;
}

It seems to me that your solution is basically O(n*m),the size of the unfiltered list times the number of filter indexes.  I think you can get O(n+mlogm),the size of the unfiltered list plus sorting the filtered indexes, by using a combination of indexes and iterators and iterating through both lists at the same time.  It could look something like this:

public static List<Test> getFilteredList(Collection<Test> unfilteredList, List<Integer> filterIndexes) {
    if(filterIndexes == null || filterIndexes.size() == 0){
        return new ArrayList<Test>(unfilteredList);
    }
    Collections.sort(filterIndexes);
    List<Test> newTestList = new ArrayList<>();
    Iterator uIterator = unfilteredList.iterator();
    Iterator fIterator = filterIndexes.iterator();
    Integer fIndex = (Integer)fIterator.next();
    for (Integer uIndex = 0;uIterator.hasNext();++uIndex) {
        Test nextTest = (Test)uIterator.next();
        if (uIndex == fIndex) {
            newTestList.add(nextTest);
            if(!fIterator.hasNext()){
               break;
            }else{
                fIndex = (Integer)fIterator.next();
                if(fIndex >= unfilteredList.size()){
                    break;
                }
            }
        }
    }
    return newTestList;
}


AES CTR mode using pycrypto I've implemented CTR mode by myself (only decryption for now), using only AES built-in functions from pycrypto. It means that I'm not supposed to use mode=AES.MODE_CTR. However, I know that using AES.MODE_CTR would be more simple, but I'm doing this as a learning experience.

Is it a safe AES CTR??

(non-parallel version)

from Crypto.Cipher import AES

from Crypto.Cipher import AES

ciphers = ["69dda8455c7dd4254bf353b773304eec0ec7702330098ce7f7520d1cbbb20fc3" + \
    "88d1b0adb5054dbd7370849dbf0b88d393f252e764f1f5f7ad97ef79d59ce29f5f51eeca32eabedd9afa9329",      \
    "770b80259ec33beb2561358a9f2dc617e46218c0a53cbeca695ae45faa8952aa" + \
    "0e311bde9d4e01726d3184c34451"]

key     = "36f18357be4dbd77f050515c73fcf9f2"

class IVCounter(object):
    def __init__(self, value):
    self.value = value

    def increment(self):
        # Add the counter value to IV
        newIV = hex(int(self.value.encode('hex'), 16) + 1)

        # Cut the negligible part of the string
        self.value = newIV[2:len(newIV) - 1].decode('hex') # for not L strings remove $ - 1 $
        return self.value

    def __repr__(self):
        self.increment()
        return self.value

    def string(self):
        return self.value

class CTR():
    def __init__(self, k):
        self.key = k.decode('hex')

    def __strxor(self, a, b):     # xor two strings of different lengths
        if len(a) > len(b):
            return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
        else:
            return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])

    def __split_len(self, seq, lenght):
        return [seq[i:i+lenght] for i in range(0, len(seq), lenght)]

    def __AESencryptor(self, cipher):
        encryptor = AES.new(self.key, AES.MODE_ECB)
        return encryptor.encrypt(cipher)

    def decrypt(self, cipher):
        # Split the CT into blocks of 16 bytes
        blocks = self.__split_len(cipher.decode('hex'), 16)

        # Takes the initiator vector
        self.IV = IVCounter(blocks[0])
        blocks.remove(blocks[0])

        # Message block
        msg = []

        # Decrypt
        for b in blocks:
            aes = self.__AESencryptor(self.IV.string())
            msg.append(self.__strxor(b, aes))

            self.IV.increment()

        return ''.join(msg)

def main():
    decryptor = CTR(key)
    for c in ciphers:
        print 'msg = ' + decryptor.decrypt(c)

if __name__ == '__main__':
    main()

This code was supposed to do the same that the code below:

import Crypto.Util.Counter
ctr_e = Crypto.Util.Counter.new(128, initial_value=long(IV.encode('hex'), 16))
decryptor = AES.new(key.decode('hex'), AES.MODE_CTR, counter=ctr_e)
print decryptor.decrypt(''.join(blocks))

I couldn't spot any problems with your implementations, but caveat lector: I'm not a cryptography expert, so take that with an appropriate pinch of salt.

I'm also concerned about the output:

$ python reinvent.py
msg = CTR mode lets yo▒B▒▒▒c▒?▒N▒▒w▒▒ap▒9▒uz▒▒▒3▒▒▒o▒V_M▒▒A
msg = Always avoid the▒?A▒▒r    ▒ά

It looks as if the first block has been decrypted correctly, and then it all falls over. Probably a bug, but I didn't dig into what's causing it.

Edit: Turns out this was an indentation problem – the code as posted had lost some indentation, and I guessed wrong when I tried to add it back.

The biggest problem with this code is the lack of docstrings and comments. Especially when you're dealing with cryptography – it's important to explain why you wrote the code you did, and how it relates to the original problem. This makes code easier to read, review and maintain – and would probably make it much easier to spot the bug above.

A variety of comments below.

IVCounter class

There should be a docstring explaining what this class represents, and what sort of values it expects as input.  I had lots of fun hassle trying different inputs and hitting a variety of errors before I got it working.
Your __repr__ method is mutating the internal state of the object – that seems like a really bad idea. The usual use case for repr() is as a debugging tool; changing the instance you're trying to debug will be a bundle of laughs.

Here's an alternative repr you could use:

def __repr__(self):
    return '%s(%r)' % (self.__class__.__name__, self.value)

This returns a string that could be eval'd to get something equivalent to the current object, which is a much more conventional use of this function.
I'm not sure why you have a string method. It would be better for callers to access self.value directly, and if you want a string representation of an object, you should define __str__ instead.
What happens when the counter overflows? You get a nasty TypeError:

>>> x = IVCounter('\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe')
>>> x.increment()
'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff'
>>> x.increment()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 8, in increment
  File "/usr/lib/python2.7/encodings/hex_codec.py", line 42, in hex_decode
    output = binascii.a2b_hex(input)
TypeError: Odd-length string

You should think about how you want to handle an overflow like this – at the very least, you should wrap the exception and provide a more intelligible error message.

CTR class.

Should subclass from object.
Avoid single letter variable names where possible; try to prefer descriptive and expressive names. For example, __init__(self, key) instead of __init__(self, key). Or for block in blocks.
In your __strxor method, you have repeated code – the only thing that changes is the arguments to zip(). Would be good to cut down that repetition.
The variable name lenght is misspelt in the definition of the __split_len method.
When I hear the word cipher, I think of things like AES, whereas you seem to be using it to describe a message text. That's a little confusing – docstrings would help.
In the decrypt() method, rather than:

self.IV = IVCounter(blocks[0])
blocks.remove(blocks[0])

you could just use:

self.IV = IVCounter(blocks.pop(0))

which will remove the item and extract it.

Misc

You appear to be importing Crypto.Cipher.AES twice. Why?