Chess puzzle improvement Is it possible to optimize this solution to the N-queens puzzle?

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 10
using namespace std;

/* print solution */
void printSolution(int board[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cout<<board[i][j]<<"  ";
        cout<<endl;
    }
}

/* check if a queen can be placed on board[row][col]*/
bool isSafe(int board[N][N], int row, int col)
{
    int i, j;
    for (i = 0; i < col; i++)
    {
        if (board[row][i])
            return false;
    }
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
            return false;
    }

    for (i = row, j = col; j >= 0 && i < N; i++, j--)
    {
        if (board[i][j])
            return false;
    }

    return true;
}

/*solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
    if (col >= N)
        return true;
    for (int i = 0; i < N; i++)
    {
        if ( isSafe(board, i, col) )
        {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1) == true)
                return true;
            board[i][col] = 0;
        }
    }
    return false;
}

/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
    int board[N][N] = {0};
    if (solveNQUtil(board, 0) == false)
    {
        cout<<"Solution does not exist"<<endl;
        return false;
    }
    printSolution(board);
    return true;
}

// Main
int main()
{
    solveNQ();
    return 0;
}

This can definitely be optimized. First, though, a few style points. Don't use #define N as Hosch250 says. Jamal points out to use std:array; this can make some later aspects nicer, too.

Sort your imports. Don't use using namespace std. I'm not sure why you imported cstdio or cstdlib... so don't. Space your operators, even <<. Use braces around all blocks.

This:

if (x == true)
if (x == false)

should be

if (x)
if (!x)

Be consistent with spacing (eg. don't add spacing inside brackets in only one place). Use const in printSolution.

Remove return 0 from main and the useless // Main comment. Similarly for the /* print solution */ comment. I'm personally not a fan of /* this comment style */ although I admit that's particularly subjective.

I'd rename printSolution to printBoard, since it doesn't require a solution.

Convert ints to bools where appropriate.

You should use ++i and --i over the postfix forms by convention.

Now the tiny things are out of the way, consider improving printSolution with range-based for loops:

void printSolution(const std::array<std::array<int, N>, N> &board)
{
    for (auto row : board)
    {
        for (auto val : row)
        {
            std::cout << val << "  ";
        }
        std::cout << std::endl;
    }
}

Consider giving a better description of isSafe and what it assumes:

// Check if a queen can be placed at (row, col)
// This assumes that there is exactly one queen in each column
// less than col and none in any other.

This can be simplified by compressing the array to a 1-dimensional array of integers, since we know that the positions are bounded to one-per-column. This speeds up isSafe, improving timings.

It looks like this:

#include <array>
#include <iostream>

const int N = 25;

void printBoard(const std::array<int, N> &board)
{
    for (int i = 0; i < board.size(); ++i)
    {
        for (auto val : board)
        {
            std::cout << (val == i) << "  ";
        }
        std::cout << std::endl;
    }
}

// Check if a queen can be placed at (row, col)
// This assumes that there is exactly one queen in each column
// less than col and none in any other.
bool isSafe(std::array<int, N> &board, int row, int col)
{
    for (int i = 1; i <= col; ++i)
    {
        if (board[col-i] == row)
        {
            return false;
        }

        // Up diagonal
        if (board[col-i] == row - i)
        {
            return false;
        }

        // Down diagonal
        if (board[col-i] == row + i)
        {
            return false;
        }
    }

    return true;
}

bool solveNQRecurse(std::array<int, N> &board, int col)
{
    if (col >= N)
    {
        return true;
    }
    for (int i = 0; i < N; ++i)
    {
        if (isSafe(board, i, col))
        {
            board[col] = i;
            if (solveNQRecurse(board, col + 1))
            {
                return true;
            }
        }
    }
    return false;
}

/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
    std::array<int, N> board{};
    if (!solveNQRecurse(board, 0))
    {
        std::cout << "Solution does not exist" << std::endl;
        return false;
    }
    printBoard(board);
    return true;
}

int main()
{
    solveNQ();
}

The next thing to do is optimize isSafe by converting it to a bitset. Since it will be useful later, I will use an uint64_t instead of an std::bitset; this is fine since a 65x65 grid won't be quickly solvable anyway. The idea is expressed in the Java version of this question; you keep track of three masks of which diagonals and rows are free. You then shift these and combine them with &. This makes isSafe just

bool isSafe(uint64_t rowsFree, uint64_t upDiagFree, uint64_t downDiagFree, uint64_t col) {
    return (rowsFree & upDiagFree & downDiagFree) & (1ULL << col);
}

However, there's a special trick to just enumerate the set bits in a value, making this unneeded. I'll just convert the code from the Java version, since it's what I'd get to anyway.

This optimization takes it from a good 23 seconds for N=30 to to just 0.36; or a speed improvement of almost 100x. This gives

#include <array>
#include <bitset>
#include <iostream>

uint64_t const N = 30;

void printBoard(std::array<uint64_t, N> const &board)
{
    for (uint64_t i = 0; i < N; ++i)
    {
        for (auto val : board)
        {
            std::cout << (val == (1 << i) ? "♛" : "·") << " ";
        }
        std::cout << std::endl;
    }
}

// Use bit hackery to extract lowest bit from spaces,
// mutating both.
void splitLowestBit(uint64_t &bits, uint64_t &bit) {
    // Copy all of the bits
    bit = bits;

    // Remove the lowest bit from the original
    bits &= bits - 1ULL;

    // Remove the rest of the bits from the copy
    bit ^= bits;
}

bool solveNQRecurse(
    std::array<uint64_t, N> &board,
    uint64_t const rowsFree,
    uint64_t const upDiagFree,
    uint64_t const downDiagFree,
    uint64_t const col
)
{
    if (!rowsFree) {
        return true;
    }

    uint64_t spaces = rowsFree & upDiagFree & downDiagFree;

    while (spaces)
    {
        uint64_t bit;
        splitLowestBit(spaces, bit);
        board[col] = bit;

        bool solvable = solveNQRecurse(
            board,
            (bit ^ rowsFree),
            ((bit ^ upDiagFree) >> 1ULL) | (1ULL << N),
            ((bit ^ downDiagFree) << 1ULL) | 1ULL,
            col + 1ULL
        );

        if (solvable) { return true; }
    }
    return false;
}

/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
    std::array<uint64_t, N> board{};
    uint64_t fullMask = (1ULL << N) - 1ULL;

    bool solvable = solveNQRecurse(
        board,      // board
        fullMask,   // rowsFree
        fullMask,   // upDiagFree
        fullMask,   // downDiagFree
        0           // col
    );

    if (solvable)
    {
        printBoard(board);
    }
    else
    {
        std::cout << "Solution does not exist" << std::endl;
    }

    return solvable;
}

int main()
{
    solveNQ();
}


Drawing concentric circles to console This prints out a triple layer circle with 12 points per circle and finds the points across a grid.

I had a really hard time with this and I'm planning to implement a lot more code but I don't want to spoil my end result.   I'm new so take it easy on me but feel free to criticize as I am looking to improve my coding and syntax.

#include <iostream>
#include <algorithm>
#include <cmath>

struct vec2{
double circ;
double x;
double y;
} v[36];

void circle(){
double pi = 3.141;
double r = 6.75;
for (int i = 0; i < 3; i++) {
    v[i].circ = (2*pi)*r;
    std::cout << "circ # " << i+1 << ": " << v[i].circ << std::endl;

    for (int j = 0; j < 12; j++)  {
         int w = 19;
         int h = 12;
         int comp = j*30;
        double rad = comp * (pi / 180);
        double x = w + (r * cos(rad)) * 5/3;
        double y = h + (r * sin(rad));
        int fact = i*12+j;
        v[fact].x=x;
        v[fact].y=y;
        }    r += 2;
    std::cout << std::endl;
    }}

bool vecfind(int row, int col){
for(int i = 0; i<36; i++){
    if(v[i].x >= col && v[i].x  < col+1 &&
                v[i].y >= row && v[i].y < row+1)
    { return true;}
    }
    return false;
    }

void square(){
for(int row = 0; row < 23; row++){
    for(int col = 0; col < 39;col++){
        if (vecfind(row, col)){std::cout << "x";}
        else{std::cout << " ";}}
std::cout << std::endl;}
return;}

int main() {
circle();
square();

return 0;}

output:

circ # 1: 42.4035

circ # 2: 54.9675

circ # 3: 67.5315

                  x
          x                x
                  x
           x              x
                  x
   x         x          x         x
      x                        x
         x                  x

 x  x  x                      x  x  x

         x                  x
      x                        x
   x         x          x         x
                   x
           x              x
                   x
          x                x
                   x

There's a lot that can be improved in your code, especially if you are using C++. The more advanced features of C++ actually help you organize your code better, help you write less code to do what you want, and remove a lot of tedium that you find in C-style code.

Use proper names for variables and functions

Names should accurately reflect what the purpose is of a variable or a function. Of course, names should be concise, but apart from some well established conventions such as using i for a loop index, or x and y for coordinates, don't abbreviate names.
Here are some suggestions for improvements in your code:

Instead of circle(), name the function draw_circles().
Instead of square(), name the function print_result().
Instead of comp, name the variable angle, or perhaps phi.

Use '\n' instead of std::endl

std::endl is in fact equivalent to '\n', but in addition it also forces a flush of the output stream, which will slow down the output if it is used a lot.

Don't store unnecessary data

You have added a member variable circ to struct vec2. First of all, it is rather strange to name something vec2 when it contains 3 elements. But it is also unnecessary to store the radius of the circle in that struct at all.

Avoid using global variables

As already mentioned in the comments, don't use global variables if you can easily avoid them. Keep the array v inside main(), and pass it as a parameter to the other functions. It does not seem like a big deal now, but once your code grows you will appreciate keeping the global namespace tidy, and by passing references/pointers to your data to functions, you make those functions more reusable.

Stick to radians when possible

All trigonometric functions in <cmath> use radians, and any calculations done involving angles are usually simpler when done in radians than in degrees. Instead of:

int comp = j*30;
double rad = comp * (pi / 180);

Write this:

double angle = j * (2 * pi / 12);

Use a proper value for π

If your <cmath> library provides it, use M_PI for the value of π, or if not, write double pi = std::acos(-1) (see this question). Just don't make unnecessary approximations; it costs you nothing to do it properly, and you never know when an approximation might actually cause you problems.

Store the image, not the coordinates of the X'es.

Building a list of coordinates of where the X'es are, and then checking for each position in the output whether it matches the coordinates of one of the X'es is not efficient. This algorithm scales with O(width * height * number_of_Xes). You either want to write the X'es directly to the screen at the right position, or keep an array of width * height characters in memory, write the X'es to that array, and then at the end print the contents of that character array. Let's use the latter method, which brings us to:

Use a class to represent the output image

You are using C++, so make use of its features! Make a class that manages an ASCII-art image for you, like so:

#include <cassert>
#include <iostream>
#include <vector>

class Image {
    std::vector<char> pixels;

    public:
    const unsigned int width;
    const unsigned int height;

    // Create a w * h image, fill it with spaces
    Image(unsigned int w, unsigned int h):
            width(w), height(h), pixels(w * h, ' ') {}

    // Return a reference to the character at coordinates x, y
    char &at(unsigned int x, unsigned int y) {
        assert(x < width && y < height);
        return pixels[y * width + x];
    }

    // Print the image
    void print(std::ostream &out) {
        for (unsigned int y = 0; y < height; y++) {
            for (unsigned int x = 0; x < width; x++)
                out << at(x, y);
            out << '\n';
        }
    }
};

This class will store the characters that make up the image in a std::vector, which acts mostly like an array, but it has the nice property that it also allocates and cleans up memory for you behind the scenes.

The function at() will return a reference to the character in the vector at the given coordinates. You can use this to both read and write to that character.

The function print() takes a std::ostream reference as an argument, so you can have it print to any stream you want.

Using this class you can create an ASCII-art image, draw to it, and then print it like so:

int main() {
    // Create a 10x10 character image
    Image image(10, 10);

    // Draw a diagonal line
    for (int i = 0; i < 10; ++i)
        image.at(i, i) = '\\';

    // Print the results to the standard output
    image.print(std::cout);
}

Now you can rewrite your circle() function to write to a class Image, like so:

void draw_circle(Image &image, double radius, int steps) {
    static const double pi = std::acos(-1);

    for (int i = 0; i < steps; ++i) {
        double phi = i * (2 * pi / steps);
        double x = image.width / 2 + radius * cos(phi);
        double y = image.height / 2 + radius * sin(phi);
        image.at(x, y) = 'X';
    }
}

And then you can draw 3 circles with increasing radii like so:

int main() {
    Image image(40, 40);

    for (auto radius: {8, 12, 16})
        draw_circle(image, radius, 12);

    image.print(std::cout);
}

Of course, this will look like an ellipse on the screen, so you will have to find some way to correct the aspect ratio. You could create a draw_ellipse() function which takes two parameters for the radius, one for the horizontal direction and another for the vertical.


TI-Basic Bouncing Ball Animation Anyone who has programmed in TI-Basic is likely to have written one of these programs. The concept for this program is simple.

The "ball" represented by a single point that originates from the upper left hand corner of the screen and bounces around the screen leaving a trail as it travels. The initial movement vector for the ball is (1,1), meaning one down, one right. During each pass through a loop, the "ball" is translated by the amount specified in the movement vector. When the ball would go of bounds, its movement vector is adjusted so that this does not happen. In short, it behaves like this:

except I increased the frame of the GIF.

I've reduced my code to a very short and clean snippet:

FnOff
PlotsOff
AxesOff
ClrDraw

{1,1→L₁
Repeat getKey
Ans→L₂
Pxl-Change(L₁(1),L₁(2
Ans+L₁→L₁
L₂*(1-2not(Ans and Ans≠{62,94
End

FnOn
PlotsOn
AxesOn
ClrDraw

What I would like to hear in responses can be enumerated in four points:

How can I reduce the size of this program?
How can I increase the speed of this program?
How can I reduce the numbers of variables used in this program?
How can I increase the clarity of this program without sacrificing any of the goals stated above?

People responding to this post should also keep in mind that this code was written for and tested on a TI-83 Plus calculator.

This uses no variables other than Ans, but because real( and imag( are two-byte tokens, the code is larger. It is also faster than your code according to Timtech.

i+dim(identity(1                    //{1+i,1+i}
Repeat getKey
Pxl-Change(real(Ans(1)),real(Ans(2
Ans+imag(Ans)(1-2inot(real(Ans) and real(Ans)≠{62,94
End

In your original solution, you can thusly save a total of six bytes at the cost of a small amount of speed, and the use of named lists. Two bytes less than that is a program that starts at (2,2) instead of (1,1) because command order is switched:

dim(identity(1→A                    //{1,1
Repeat getKey
Ans→B
Ans+∟A→A
Pxl-Change(Ans(1),Ans(2
∟Bcos(πʳnot(Ans and Ans≠{62,94
End

Finally, if your calculator is in radian mode, you can save one more byte by removing the ʳ.


Open github via commandline I'm learning bash and my goal here is from any repository on my computer to be able to type github and it will open the remote in a browser for me.

This works but I feel like I over complicated the remote=$(..) logic and arguably the get_ext() method.

get_ext() allows you to type github issues and it will open the issues page for that repo on github. I know it could work better if there was a hash map equivalent in bash but from what I can find, there's not.

code:

#! /bin/bash

endpoint=$1

get_ext() {
  case $1 in
    *github*)
      case $endpoint in
        pr)
          echo "/pulls";;
        issues)
          echo "/issues";;
        *)
          echo "";;
      esac;;
    *bitbucket*)
      case $endpoint in
        pr)
          echo "/pull-requests";;
        issues)
          # issues doesn't exist for bitbucket
          echo "";;
        *)
          echo "";;
      esac;;
  esac
}

open_site() {
  # currently only works for SSH addresses
  if [[ $remote == *@* ]]; then
    name=$(echo $remote | sed  "s/^.*:\(.*\)\.git/\1/g")
    ext=$(get_ext $1)
    open "$1/${name}${ext}"
  fi
}
remote=$(grep -A 1 "remote \"origin\"" $(pwd)/.git/config | sed -n 2p)

case $remote in
  *github*)
    open_site "https://github.com";;
  *bitbucket*)
    open_site "https://bitbucket.org";;
esac

Getting the url of origin

This is a bit awkward:

remote=$(grep -A 1 "remote \"origin\"" $(pwd)/.git/config | sed -n 2p)

Because:

The grep + sed is a bit hacky
$(pwd) can be replaced with a simple .
It's awkward to rely on .git/config content instead of some git command

Try to look for native Git commands to extract this kind of information, for example:

git remote show -n origin | grep Fetch.URL

The output is not exactly same as the original, but it will work fine with the rest of your script.

Named parameters

In Bash there are no named parameters.
As a consequence, in this function it can be hard to remember what $1 refers to:

open_site() {
  # currently only works for SSH addresses
  if [[ $remote == *@* ]]; then
    name=$(echo $remote | sed  "s/^.*:\(.*\)\.git/\1/g")
    ext=$(get_ext $1)
    open "$1/${name}${ext}"
  fi
}

As a workaround, I recommend assigning the parameter to a well-named local variable, like this:

open_site() {
  local baseurl=$1
  # currently only works for SSH addresses
  if [[ $remote == *@* ]]; then
    name=$(echo $remote | sed  "s/^.*:\(.*\)\.git/\1/g")
    ext=$(get_ext $baseurl)
    open "$baseurl/${name}${ext}"
  fi
}

Pattern replacement

Instead of this:

name=$(echo $remote | sed  "s/^.*:\(.*\)\.git/\1/g")

I recommend simple pattern substitution:

# chop off the start until the last :
remote=${remote##*:}
# chop off .git at the end
remote=${remote%.git}

The benefit of this approach is that it doesn't run extra programs (no sed, no echo, no piping).

A minor note, the original sed didn't need the g flag.

Printing a blank line

You don't need "" to just echo a blank line:

echo ""

This is exactly the same:

echo


New to immediately-invoked function expression with JavaScript, curious about placement At the end of the immediately-invoked function expression, there is an if statement that checks the screen width and loads in some resources. I'm curious if it is best practice to include this logic inside my IIFE, or outside. Both seem to function the same as far as I can tell, though I'm curious if there is preferred/best way this should be done.

Also of interest to me, inside the IIFE I have a if/if else/else statement. I'm curious if the last else, with the return in it is necessary. Does it offer any benefits or should I remove it.

Feedback is much appreciated!

Below is the code I'm working with:

(function(w){
    w.loader = function(filetype, filename, mediaquery){

      var head = document.getElementsByTagName("head")[0],
          stylesheet = document.createElement('link'),
          script = document.createElement('script'),
          filetype = filetype.toLowerCase(); // normalize filetype data for use in conditions

      // If file type is set to CSS, create dynamic stylesheet link element
      if (filetype === 'css'){
        stylesheet.type = 'text/css';
        stylesheet.rel = 'stylesheet';
        stylesheet.href =  (filename + '.css');
        stylesheet.media = (mediaquery) ? mediaquery : 'screen'; // Use screen for media unless otherwise specified
        // If a file name has been specified, append dynamic stylesheet link element
        if (filename.length){
          head.appendChild(stylesheet);
        }
      }
      // If file type is set to JS, create dynamic script element link
      else if(filetype === 'js'){
        script.type = 'text/javascript';
        script.src = (filename + '.js');
        // If a file name has been specified, append dynamic script element
        if (filename.length){
          head.appendChild(script);
        }
      }
      else{
        return;
      }

    };

    if(Math.max(screen.width,window.outerWidth) > 600 ){
      alert("Large Screen");
      loader('CSS', 'large-screen');
      loader('JS', 'large-screen');
    }

  }(this));

  /*
  if(Math.max(screen.width,window.outerWidth) > 600 ){
    alert("Large Screen");
    loader('CSS', 'large-screen');
    loader('JS', 'large-screen');
  }
  */

In this case, it makes no difference at all.  This IIFE really has no reason for even being there because all it contains is a single function.  Your code does use any of the usual benefits of an IIFE (like a local and protected scope) or capturing the arguments in a closure.

So the additional code that doesn't have any local variables of its own and doesn't use the passed in argument does not benefit at all from being in the IIFE, but there is no harm in putting it in the IIFE either.


Testing Remedy-on-Demand REST API code I am writing a python module to interact to the ROD (remedy on demand) BMC ticketing product. So far I have only written the log in and log out methods and tests. Before I crack on with the more complex methods I hope someone can review the current test strategy and happy to hear any suggestions for improvements.
rodAPI.py
import requests

class RodApi:
    def __init__(self, fqdn, username, password, token_type="AR-JWT"):
        self.username = username
        self.password = password
        self.fqdn = fqdn
        self.token_type = token_type
        self.login_url = f"https://{fqdn}/api/jwt/login"
        self.logout_url = f"https://{fqdn}/api/jwt/logout"
        self.token = None

    def login(self) -> bool:
        data = {"username": self.username, "password": self.password}
        headers = {"content-type": "application/x-www-form-urlencoded"}
        response = requests.post(self.login_url, data=data, headers=headers)

        print(f"connecting to URL: {self.login_url}")
        print(f"https status code: {response.status_code}")
        self.token = response.text
        if response.status_code == 200:
            return True
        return False

    def logout(self) -> bool:
        headers = {"Authorization": f"{self.token_type} {self.token}"}
        response = requests.post(self.logout_url, headers=headers)

        print(f"connecting to URL: {self.logout_url}")
        print(f"https status code: {response.status_code}")
        if response.status_code == 204:
            print(f"Logged out with a status of: {response.status_code}")
            return True
        else:
            print(f"Error logging out: {response.text}")
            return False

test_rodAPI
import pytest

from rodAPI import RodApi

@pytest.fixture()
def rod_api_instance():
    rod_api = RodApi("example.com", "some_user", "some_password")
    return rod_api

@pytest.fixture()
def rod_api_logged_in_instance(responses, rod_api_instance):
    responses.add(responses.POST, rod_api_instance.login_url, body="some_token_string")
    rod_api_instance.login()
    return rod_api_instance

def test_login_success(responses, rod_api_instance: RodApi):
    responses.add(responses.POST, rod_api_instance.login_url, body="some_token_string")
    result = rod_api_instance.login()
    assert result is True
    assert rod_api_instance.token == "some_token_string"

def test_login_fail(responses, rod_api_instance: RodApi):
    responses.add(responses.POST, rod_api_instance.login_url, status=404)
    result = rod_api_instance.login()
    assert result is False

def test_logout_success(responses, rod_api_logged_in_instance: RodApi):
    responses.add(responses.POST, rod_api_logged_in_instance.logout_url, status=204)
    result = rod_api_logged_in_instance.logout()
    assert result is True

def test_logout_fail(responses, rod_api_logged_in_instance: RodApi):
    responses.add(responses.POST, rod_api_logged_in_instance.logout_url, status=404)
    result = rod_api_logged_in_instance.logout()
    assert result is False
```

Redundant headers
Read
https://github.com/psf/requests/blob/master/requests/models.py#L514 - your use of
    headers = {"content-type": "application/x-www-form-urlencoded"}

should not be needed.
Out-of-order progress
You print
    print(f"connecting to URL: {self.login_url}")

when this has already happened. Either say "connected to", or move this statement before your post.
Exception degradation
Resist the urge to sabotage the Python exception system. Rather than returning booleans from your methods, call response.raise_for_status, and optionally wrap that in a try/except/raise MyException() from e with your own exception type. raise_for_status will also obviate your status code checks.


The cascaded_union function can take more than one object, so you should be able to do:

from shapely.geometry import Polygon, MultiPolygon
from shapely.ops import cascaded_union

def get_region(vertices, triangles):
    regions = MultiPolygon([Polygon([vertices[i] for i in triangle])
                            for triangle in triangles])
    return list(cascaded_union(regions).exterior.coords)

When deleting triangle[72] from your example, which is not really a triangle and the reason for your try...except ValueError, this gives the same area for this function and yours, 1060307.0.

If you cannot delete those zero-size triangles manually, you can do it programmatically as well:

def get_region(vertices, triangles):
    polygons = (Polygon([vertices[i] for i in triangle])
                for triangle in triangles)
    regions = MultiPolygon([p for p in polygons if p.area > 0])
    return list(cascaded_union(regions).exterior.coords)

I would leave getting the points of the exterior to the caller, or another function, but I left it here in order to not change the interface.

Note that cascaded_union may be superseded by unary_union, depending on the version you are using.

I am not sure why you use the datastructure you have. It would be easier to directly store the vertices for each triangle as a three-tuple, so that you could just do:

def get_region(triangles):
    polygons = (Polygon(triangle) for triangle in triangles)
    regions = MultiPolygon([p for p in polygons if p.area > 0])
    return list(cascaded_union(regions).exterior.coords)


Finding the name of a given constant using reflection The code below comes from the Arm_const class of my Android disassembler project:

// ARM condition code

public static final int ARM_CC_INVALID = 0;
public static final int ARM_CC_EQ = 1;
public static final int ARM_CC_NE = 2;
public static final int ARM_CC_HS = 3;
public static final int ARM_CC_LO = 4;
public static final int ARM_CC_MI = 5;
public static final int ARM_CC_PL = 6;
public static final int ARM_CC_VS = 7;
public static final int ARM_CC_VC = 8;
public static final int ARM_CC_HI = 9;
public static final int ARM_CC_LS = 10;
public static final int ARM_CC_GE = 11;
public static final int ARM_CC_LT = 12;
public static final int ARM_CC_GT = 13;
public static final int ARM_CC_LE = 14;
public static final int ARM_CC_AL = 15;

public static String getCCName(int cc)
{
    Class clazz=Arm_const.class;
    Field[] fields=clazz.getFields();
    for(Field f:fields)
    {
        String s=f.getName();
        if(s.contains("ARM_CC_"))
        try
        {
            if (((int)f.get(null))==cc)
            {
                return s.replace("ARM_CC_","");
            }
        }
        catch (IllegalAccessException e)
        {
            Log.e("arm","",e);
        }
        catch (IllegalArgumentException e)
        {}
    }
    return "";
}

The method getCCName returns the name of a constant from the declared public static final ints.

Examples:

3 → "HS"
12 → "LT"

Any suggestions to improve its performance (speed) are appreciated!

If performance is your concern I would implement getCCName as a lookup in a map that's filled when the class is loaded, e.g. like

private static final Map<Integer, String> _int2string;

static
{
    final Map<Integer, String> int2string = new HashMap<>();

    try
    {
        for (Field field: Arm_const.class.getFields())
        {
            final int mod = field.getModifiers();

            if (!int.class.equals(field.getType()))
                continue;

            if (!Modifier.isStatic(mod) || !Modifier.isPublic(mod))
                continue;

            if (!field.getName().startsWith("ARM_CC_"))
                continue;

            int2string.put(field.getInt(null),
                           field.getName().substring("ARM_CC_".length()));
        }
    }
    catch (IllegalAccessException l_e)
    {
        throw new RuntimeException(l_e); // should not occur
    }

    _int2string = Collections.unmodifiableMap(int2string);
}

public static String getCCName(int cc)
{
    return _int2string.get(cc);
}


Calculating the determinants of data entered This program is supposed to calculate the determinants of the data entered. I believe it does. Within the guidelines of this exercise we were not to break this down to functions but all out of main. We will be breaking it down into functions in part a and b of this overall exercise.

However, I don't know enough about matrices and determinants yet to know if I am using the equation given to me correctly. I know this out puts the data given to the screen correctly and the formula given was:

determinant = (AEI) + (BFG) + (CDH) - (BDI) - (AFH) - (CEG)

which equates to the array elements:

00 * 11 * 22 + 01 * 12 * 20 + 02 * 10 * 21- 01 * 10 * 22 - 00 * 12 * 21 - 02 * 11 * 20

Given the 3x3 block where the first row is ABC, second row of DEF and third row of GHI.

I am asking that it be analyzed and critiqued.

# include <iostream>
# include <stdio.h>
# include <iomanip>

using namespace std;

int main()
{
    int x,y,z,;
    char ch;
    float  My3DMatrix[3][3];
    int mReader[9];
    for (x = 0 ; x <= 8 ; x++)//This array is for accessing the Matrix elements in
    {                     //the prescribed manner to calculate the determ.
        y = x;
        if( x == 3 || x == 8 )y = 1;
        if(x == 4 || x ==6 )y = 2;
        if(x == 5 || x == 7 )y = 0;
        mReader[x] = y;
    }
    do  //This initiates the main loop
    {
        cout<<"Calculation of  3 x 3 Determinant"<<endl<<endl;
        for(x = 0; x<=2 ;x++) // This loop querries the user for
        {                     //input and feeds the My3DMatrix
            cout<<"What is row "<<x+1<<" of the matrix? ";
            for (y = 0 ; y <=2 ; y++)
            {
                cin>>My3DMatrix[x][y];
            }   //The matrix is now fed
        }
        cout<<"\nThe 3 x 3 Matrix entered is: "<<endl; //Now the Raw
        cout<<setprecision(3)<<fixed; //Matrix data is displayed
        for(x = 0 ; x<=2 ; x++)
        {
            cout<<My3DMatrix[x][0]<<"\t"<<My3DMatrix[x][1]<<"\t"
                <<My3DMatrix[x][2]<<endl;
        }
        float Determinant[6]; //This array is for storing the 6
        y = -1 ; z = 0; //products from each row of the matrix
        for(x = 0 ; x <= 8 ; x++)// There are 9 indexes to create 3 products from
        {   //This loop pulls the correct indexes from My3DMatrix then  creates
            if (z>=3) z = 0; //and stores the products into Determinant[x] 0 - 2
            if ((x % 3) == 0 || x == 0)
            {
                y = y + 1;
                Determinant[y] = 1;
            }
            Determinant[y] =  Determinant[y] * My3DMatrix[z][mReader[x]];
            z = z + 1;
        }
        y = 2 ; z = 0;
        for(x = 9 ; x >= 1 ; x--)// There are 9 indexes to create 3 products from
        {       //This loop pulls the correct indexes from My3DMatrix then creates
            if (z>=3) z = 0;//and stores the products into Determinant[x] 3 - 5
            if ((x % 3) == 0 || x == 0)
            {
                y = y + 1;
                Determinant[y] = 1;
            }
            Determinant[y] =  Determinant[y] * My3DMatrix[z][mReader[x - 1]];
            z = z + 1;
        }
        float myAnswer;
        myAnswer = 0;//Here with Determinant[6] loaded with the correct index products:
        myAnswer = Determinant[0] + Determinant[1] + Determinant[2] ; //The deternm.
        myAnswer = myAnswer -  Determinant[3] - Determinant[4] - Determinant[5]; //and simple calculation is plain
            cout<<"The determinant of the above matrix is: "<< myAnswer<< endl;
        cout<<"Would you like to Do another Matrix (Y/N)? ";

        cin>>ch ;
    }while(ch == 'Y' || ch == 'y');

    cin.get();

    return 0;
}

General comments:

Use one line per variable.

int x,y,z,;

Prefer to use smaller than than smaller than or equal. This is a bit nit-picky but when working with array bounds you can then use the same number in the test as in the size of the array, which makes it slightly easier to read.

int mReader[9];
for (x = 0 ; x <= 8 ; x++)

// try
int mReader[9];
for (x = 0 ; x < 9 ; x++) // easy to see correlation between x and mReader

The variables x/y/z are not used to pass information between different loops. So rather than declare them at the top declare them as close to the point of use as possible. Your loops should look more like this:

for(int x = 0; x<=2 ;x++)
 // ^^^ x is local to the loop

Do not fall in to the mental trap of thinking that you are saving space for re-use. The compiler is quite capable of doing that all by itself.

This test seems a bit redundant:

if ((x % 3) == 0 || x == 0)
     //          ^^^^^^^^^  Why? if x == 0 then (x % 3) == 0 thus the second part of the
     //                          test will never be evaluated.

Are you sure this is correct?

for(x = 9 ; x >= 1 ; x--)

Seems like x never reaches 0. As it turns out it is correct even if it looks wrong. But you need to read the rest of the code to make sure it is being used correctly. Writing code were you need to scan ahead to determine correctness is not a good idea. I would loop the same way as all the other loops (using a different variable name) then adjust the usage.

for(int reverseX = 0 ; reverseX < 9 ; ++reverseX)
{
 .....
     Determinant[y] =  Determinant[y] * My3DMatrix[z][mReader[9 - 1 - reverseX]];

Does this work?

cin.get();

Looks like you are trying to pause the application before termination. But to me it looks like it will try and swallow the '\n' from the last time you hit enter, and thus do nothing.


Implement funcionality with handling errrors without throwing exceptions In usual code if something goes wrong you throw an exception. However in some cases you need so that exceptions were processed and reported. Form validation is a good example. Error handling in this is realy easy. However I faced a problem when error handling is different from the previous example and that code does not look very pretty. Here is an example:

public function create($bcId) {
        $this->reporter->title("BC product resource creating report");
        $resource = $this->get($bcId);
        if (!$resource) {
            $this->reporter->report();
            return;
        }
        $dto = EntityDto::fromBc($resource);
        if (!$this->validator->validate($dto)) {
            $this->reporter->report($this->validator->getErrors());
            return;
        }
        $entity = Entity::fromDto($dto);
        $this->entityRepo->create($entity);
    }

    public function get($bcId) {
        try {
            $resource = $this->bcRepo->get($bcId);
        } catch (\Exception $e) {
            $this->reporter->add($e);
            return false;
        }
        return $resource;
    }

Without error handling the code would look like this:

public function create() {
        $resource = $this->bcRepo->get($bcId);
        $dto = EntityDto::fromBc($resource);
        $entity = Entity::fromDto($dto);
        $this->entityRepo->create($entity);
    }

Much less code and more clear. However I need proper error handling. I can not go with throwing exceptions because it will exit the app. I could have the following code:

public function create() {
        if (
            ($resource = $this->bcRepo->get($bcId)) &&
            ($dto = EntityDto::fromBc($resource)) &&
            ($entity = Entity::fromDto($dto)) &&
            ($this->entityRepo->create($entity))
        ) ; else {
            $this->report();
        }
    }

But it still is difficult to understand. Are there any variants to change the code to by prettier without chaning its behaviour?

I can not go with throwing exceptions because it will exit the app.

That's but a grave delusion and misconception about exception. What you have to learn yet, there is an infinite number of different exceptions, and catch (\Exception $e) is not the only way to catch an exception.

So you have a solution in three easy steps

First, define your own kind of exception:

class MyFormHandlerErrorException extends Exception {}

then make your methods throw this certain exception

if (something goes wrong) {
    throw new \MyFormHandlerErrorException('Error message goes here');
}

and then simply catch this only one

public function create() {
    try{
        $resource = $this->bcRepo->get($bcId);
        $dto = EntityDto::fromBc($resource);
        $entity = Entity::fromDto($dto);
        $this->entityRepo->create($entity);
    } catch (\MyFormHandlerErrorException  $e) {
        $this->reporter->add($e);
        return false;
    }
}

bingo! now your specific exceptions will be caught whereas all other error will bubble up to error handler. As simple as that

If you want to define several different exceptions of the same kind, then just create one basic exception and then extend all others from this:

class MyFormHandlerErrorExceptionA extends MyFormHandlerErrorException {}
class MyFormHandlerErrorExceptionB extends MyFormHandlerErrorException {}
class MyFormHandlerErrorExceptionN extends MyFormHandlerErrorException {}

now you could either catch any of them specifically, or catch them all at once by catching the base exception


Preserve formatting for mail merge Excel & Word 2016 I inherited some code and have discovered that it seems incredibly inefficient. The code works by applying text formatting to the cells in an Excel file cell by cell, via this loop:

Public Sub RemoveNumberFormat(ByVal columnName As String, ByVal lastColumn As Integer)
    For i = 2 To lastColumn
        textval = Range(columnName & CStr(i)).Text
        Range(columnName & CStr(i)).NumberFormat = "@"
        Range(columnName & CStr(i)).Value = textval
    Next i
End Sub

This will preserve numbers such as 6120 as 6,120 and currency values such as 7568910 as $7,568,910. These numbers are brought in from the Excel workbook into mail merge fields in a Word document. Currently, this function is called on every column in the workbook like so:

    RemoveNumberFormat "AM", lastColumn
    RemoveNumberFormat "AU", lastColumn
    RemoveNumberFormat "AV", lastColumn
    RemoveNumberFormat "BA", lastColumn
    ... etc.

Now this does work, but there's 145 columns. The macro is called on open and it takes several seconds to run. This seems incredibly inefficient.

I had tried simply updating the NumberFormat of the UsedRange as so:

Sheets("MailMerge").UsedRange.NumberFormat = "@"

But that still removes the commas and currency formatting from the columns.

I had also tried copying the values, updating the NumberFormat, then pasting the values in (essentially re-creating that loop as a set operation rather than cell by cell) but that also did not result in the formatting being preserved.

Is there a better way to do this than loop through each cell?

You can't read the Text property from a multi-cell range the same way you can with (eg) Value, but you can change the number format and set the value for the whole block using only two single operations, so something like this is much faster:

Public Sub RemoveNumberFormat2(ByVal columnName As String, _
                               ByVal lastColumn As Integer)
    Dim d(), rng As Range, i As Long

    Set rng = Range(columnName & "2:" & columnName & lastColumn)

    ReDim d(1 To lastColumn - 1, 1 To 1)

    'read the text values: this you have to do in a loop...
    For i = 1 To rng.Cells.Count
        d(i, 1) = rng(i).Text
    Next i

    'these you can do as a block...
    With rng
        .NumberFormat = "@"
        .Value = d
    End With
End Sub

In my testing on a ~3000-row column this was about 10x faster.


Concat downloaded content by wget I want to get the latest release of certain package. In order to do so I did this:

wget https://chromedriver.storage.googleapis.com/LATEST_RELEASE -O /tmp/chromedriver_release
wget http://chromedriver.storage.googleapis.com/`cat /tmp/chromedriver_release`/chromedriver_linux64.zip -O /tmp/chromedriver_linux64.zip

There's not a direct link to the latest version (at least none that I could find)
This instructions are part of a provisioning script, I don't have curl installed and I don't want to install it

I checked wget arguments and I didn't find anything that allows me to redirect the downloaded content to stdout. Will this be my best option?

This is very hard to read like that.
The duplication of the same base url is also not great.

With the -O flag, you could specify - to make the output go to stdout.

Lastly, `...` is obsolete syntax, use the modern $(...) instead.

baseurl=https://chromedriver.storage.googleapis.com
filename=chromedriver_linux64.zip

version=$(wget "$baseurl"/LATEST_RELEASE -O-)
wget "$baseurl/$version/$filename" -O "/tmp/$filename"


PHP upload script might be vulnerable I have written a basic PHP upload script a few years ago and recently I discovered some phishing html pages in the website's root.

This website is located in /www/sitename, while I upload the files to /gstorage/sitename, which can't be accessed from the web.

I have found a lot of html files in /www/sitename and it seems like they somehow came through the upload.php file, as I've found a POST from a specific ip to this file in the logs before the files appeared and then that IP started sending post to those files.

Here's the code:

include('inc.php');
$disallowed = array('php', 'php5');

if(isset($_FILES['upl']) && $_FILES['upl']['error'] == 0){

    $extension = pathinfo($_FILES['upl']['name'], PATHINFO_EXTENSION);

    if(in_array(strtolower($extension), $disallowed)){
        echo '{"status":"error", "message":"no PHP"}';
        exit;
    }
    $url = findNewURL();
    $size = formatSizeUnits($_FILES['upl']['size']);
    if(move_uploaded_file($_FILES['upl']['tmp_name'], '/gstorage/edited/'.$url)){
        try {
            $stmt = $db->prepare("INSERT INTO files(url, filename, size, type) VALUES(:url,:filename,:size, :type)");
            $stmt->execute(array(":url" => $url, ":filename" => $_FILES['upl']['name'], ":size" => $size, ":type" => $_FILES['upl']['type']));
        } catch(PDOException $ex) {
            echo 'Error!';
            echo $ex->getMessage();
        }

        echo '{"status":"success", "link": "http://edited.org/'.$url.'"}';
        exit;
    }
}
echo '{"status":"error"}';
exit;

Where could the vulnerability be?

Your extension check is pretty much useless, as I can still upload a variety of files with extensions that can gain me code execution, such as php4 or .htaccess. If possible, use a whitelist approach instead.

But in your case, it doesn't really matter, as you are not using the extension anyways, the filename is just a random 5 character string without extension.

You should also always use prepared statements. Yes, $file is currently controlled by you, but who knows, that may change in the future.

Apart from this, I don't see any vulnerabilities in your script. My guess is that the vulnerability is somewhere else (seeing the logged request that you suspect would still be interesting).


Pure PHP array_diff_assoc_recursive function For my application, I was using array_diff_assoc, when I noticed it was returning the wrong value.  I was using multidimensional arrays, therefore I needed a array_diff_assoc_recursive method.

I Googled around and found a few, but they all only took 2 parameters.  The official array_diff_assoc can take an infinite number of params.  I wanted mine to, so I wrote my own array_diff_assoc_recursive function.

<?php
class Tools{
    /**
     * Recursive version of array_diff_assoc
     * Returns everything from $a that is not in $b or the other arguments
     *
     * @param $a The array to compare from
     * @param $b An array to compare against
     * @param ... More arrays to compare against
     *
     * @return An array with everything from $a that not in $b or the others
     */
    public static function array_diff_assoc_recursive($a, $b){
        // Get all of the "compare against" arrays
        $b = array_slice(func_get_args(), 1);
        // Initial return value
        $ret = array();

        // Loop over the "to" array and compare with the others
        foreach($a as $key=>$val){
            // We should compare type first
            $aType = gettype($val);
            // If it's an array, we recurse, otherwise we just compare with "==="
            $args = $aType === 'array' ? array($val) : true;

            // Let's see what we have to compare to
            foreach($b as $x){
                // If the key doesn't exist or the type is different,
                // then it's different, and our work here is done
                if(!array_key_exists($key, $x) || $aType !== gettype($x[$key])){
                    $ret[$key] = $val;
                    continue 2;
                }

                // If we are working with arrays, then we recurse
                if($aType === 'array'){
                    $args[] = $x[$key];
                }
                // Otherwise we just compare
                else{
                    $args = $args && $val === $x[$key];
                }
            }

            // This is where we call ourselves with all of the arrays we got passed
            if($aType === 'array'){
                $comp = call_user_func_array(array(get_called_class(), 'array_diff_assoc_recursive'), $args);
                // An empty array means we are equal :-)
                if(count($comp) > 0){
                    $ret[$key] = $comp;
                }
            }
            // If the values don't match, then we found a difference
            elseif(!$args){
                $ret[$key] = $val;
            }
        }
        return $ret;
    }
}

I was wondering what you thought of my attempt.  It seems to work ok for my application, and in the few tests I tried with it.

DEMO: http://ideone.com/5GZ8Tn

The logic looks good but I would like to suggest a few tips to enhance readability and maintainability of your code.

First off: name your variables accordingly $a doesn't say anything to any random person when reading the code. He will have to scroll up and down figuring out what is what.

Second: Split your function into multiple methods. This will enhance readability and will keep an overview of your code. Now you have one very large method which will take a random person at least half an hour to figure out what it all does exactly.

Third: Try to avoid things like continue 2;, break; and more. They don't mean anything when you read code and can be avoided in most cases.

Fourth: Comments rot very quickly! Try and make sure that your methods are selfexplanatory so that you dont need to put comments.


Using Token Bucket to rate limit function calls This program is my attempt at solving the below problem:
We have a function which is going to be called by multiple threads. The problem is to find a way to limit the number of times this function is executed per second given that we don't have a control over:
a) The number of threads calling this function.
b) The number of times per second this function will be called by any thread.
We need to somehow limit its rate of execution.
This program is my attempt at solving this kind of problem. I've tried to use the Token Bucket Algorithm for this.
The usage is simple. It consists of a header file "tokenBucket.hpp". You need to include this in your program. Suppose you want to limit the execution rate of the function given below:
void printHelloWorld();

You need to do 2 things:
You need to create a tokenBucket object constructed with the required rate you want your function to be executed per second. e.g. tokenBucket aBucket(500);
When calling your function, then instead of: printHelloWorld();
you have to do:
if(aBucket.areTokensAvailable()) {
printHelloWorld();
}

Given below is my header only program:
#ifndef __TOKEN_BUCKET_HPP__
#define __TOKEN_BUCKET_HPP__

#include <chrono>
#include <mutex>
#include <iostream>

class tokenBucket{

  public:

    /* Constructor */
    tokenBucket(uint64_t fa_tokenFillRatePerSec): m_tokenFillRatePerSecond(fa_tokenFillRatePerSec),m_bucketSize(fa_tokenFillRatePerSec),m_availableTokens(fa_tokenFillRatePerSec),m_lastRefillTime(std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now().time_since_epoch()).count()),m_timeIntervalPerRequestInMicroSeconds(NUMBER_OF_MICROSECONDS_IN_A_SECOND/fa_tokenFillRatePerSec){
      fprintf(stdout,"\nToken Bucket initialised with the following values\nm_bucketSize(%lu)\nm_tokenFillRatePerSecond(%lu)\nm_availableTokens(%lu)\nm_lastRefillTime(%lu)\nm_timeIntervalPerRequestInMicroSeconds(%lu)\n",m_bucketSize,m_tokenFillRatePerSecond,m_availableTokens,m_lastRefillTime,m_timeIntervalPerRequestInMicroSeconds);
    }

    /* always called to check if sufficient number of tokens are available to server the request*/
    bool areTokensAvailable(int fa_numberOfRequestedTokens = 1){
      std::lock_guard<std::mutex> lg(m_mu);
      uint64_t now = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
      refill_tokens(now);

      if(m_availableTokens < fa_numberOfRequestedTokens){
        return false;
      }
      else{
        m_availableTokens -= fa_numberOfRequestedTokens;
        return true;
      }
    }

  private:
    static constexpr int NUMBER_OF_MICROSECONDS_IN_A_SECOND = 1000000;
    std::mutex m_mu;
    uint64_t m_bucketSize; //Currently I'm taking Bucket Size = token fill rate per second.
    uint64_t m_tokenFillRatePerSecond;
    uint64_t m_availableTokens; //current number of tokens available in the bucket
    uint64_t m_lastRefillTime;
    uint64_t m_timeIntervalPerRequestInMicroSeconds; // = (pow(10,6)/m_tokenFillRatePerSecond)

    /* to refill the tokens as per time diff */
    void refill_tokens(const uint64_t& fa_currentRequestTime) {
      /*calculate tokens added in particular time difference */
      if (fa_currentRequestTime >= m_lastRefillTime + m_timeIntervalPerRequestInMicroSeconds) {

        uint64_t l_newTokens = (fa_currentRequestTime - m_lastRefillTime)/m_timeIntervalPerRequestInMicroSeconds;

        if(m_availableTokens + l_newTokens < m_bucketSize) {
          m_availableTokens += l_newTokens;
        }
        else {
          m_availableTokens = m_bucketSize;
        }
        m_lastRefillTime = fa_currentRequestTime;
      }
    }
};

#endif

Comments/Criticisms are welcome.

Avoid casting time too much
A lot of code is spent on converting time to integers. Avoid casting too early; store time as much as possible as std::chrono types.
In fact, intead of storing how much tokens there are in the bucket, you could instead store how much time there is in the bucket. Then only in areTokensAvailable() do you need to cast from the amount of time in the bucket to the number of tokens.
For example, the result of two calls to std::chrono::...::now() can be subtracted from each other, the result is a duration that can be added to another duration.
Consider using shorter function and variable names
Your function and variable names are very verbose, to the point that they make the code harder to read. Try to make them more concise, remove redundant information. I would also avoid using prefixes such as fa_. Does it stand for function argument? It's already clear from the function definition that it's an argument. The m_ prefx for private member variables is more commonly used, and sometimes helps avoid name clashes, so I would keep that.
Use a single type to store the number of tokens
In your code, you use both uint64_t and int for the number of tokens. Be consistent and stick with a single type. Use a type alias to make it more explicit.
Use std::chrono::steady_clock
Don't use std::chrono::system_clock for measuring the passage of time. It will give incorrect results when daylight savings time changes, when there are leap seconds and whenever the system clock gets changed (either by an administrator or by something like an NTP daemon). The std::chrono::steady_clock is guaranteed to be a monotonically increasiing clock. I would also create a type alias for it to reduce typing.
Example
Here's an example of how the code can be made to look:
class tokenBucket {
    using count_type = uint64_t;
    using clock = std::chrono::steady_clock;

public:
    tokenBucket(count_type rate): m_rate(rate) {}

    bool request(count_type count) {
        std::lock_guard<std::mutex> lock(m_mutex);
        refill();
        return try_remove(count);
    }

private:
    std::mutex m_mutex;

    count_type m_rate;
    clock::time_point m_last_refill{clock::now()};
    clock::duration m_available{};
    clock::duration m_capacity{std::chrono::seconds(1)};

    void refill() {
        auto now = clock::now();
        m_available += now - m_last_refill;
        m_available = std::min(m_available, m_capacity);
        m_last_refill = now;
    }

    bool try_remove(count_type count) {
        auto requested = count * clock::duration(std::chrono::seconds(1)) / m_rate;

        if (requested <= m_available) {
            m_available -= requested;
            return true;
        } else {
            return false;
        }
    }
};

Note: m_capacity here holds the size of the bucket as a time duration. If it is constant, you can make it a static constexpr variable.


Downloading files using Python-requests I wrote a Python script to download files using multiple (source) IP addresses -- kindly suggest any improvements.

import cgi
import os
import posixpath
import Queue
import threading
import urllib
import urlparse
import random
import re
import shutil
import time

import requests
import requests_toolbelt

def get_IPs():
    """Returns all available IP addresses in a list."""
    # TODO: Windows only. Other options?
    out = []
    for i in os.popen('ipconfig'):
        i = i.strip()
        if i.startswith('IP'):
            out.append(i.rsplit(' ', 1)[-1])

    return out

def get_info(url):
    """Returns name and size of file to be downloaded."""
    try:
        resp = requests.head(url, allow_redirects=True)
        name = cgi.parse_header(resp.headers['content-disposition'])[1]['filename']
    except KeyError:
        path = urlparse.urlsplit(url).path
        name = posixpath.basename(path)
    name = urllib.unquote_plus(name)
    size = int(resp.headers['content-length'])
    return name, size

def worker(url, session, ud, part, size):
    """Downloads a part of the file specified by 'part' parameter."""
    # TODO: optimal tries, timeout?
    for _ in xrange(2):
        try:
            open('%s/%04d' % (ud, part), 'wb').write(
                session.get(url, timeout=(2, 7), headers={'range': 'bytes=%s-%s' % (
                    part*chunk, min(size, part*chunk + chunk - 1))}).content)
            break
        except:
            pass
    else:
        worker(url, sessions_queue.get(), ud, part, size)

    sessions_queue.put(session)

def summary(name, size, elapsed):
    """Prints summary of the download after it is completed."""
    print (
        '--\n'
        '%s download completed.\n'
        'Time elapsed: %.2fs\n'
        'Average download speed: %.2f MB/s\n'
        '--' % (name, elapsed, size/elapsed/2**20))

def download(url):
    """Downloads the file pointed to by 'url' parameter."""
    start = time.clock()
    name, size = get_info(url)
    # random id of length 20
    ud = '%0x' % random.getrandbits(80)
    os.mkdir(ud)
    threads = []
    for i in xrange(size/chunk + (size%chunk != 0)):
        t = threading.Thread(target=worker, args=(url, sessions_queue.get(), ud, i, size))
        threads.append(t)
        t.start()

    # characters \/:*?"<>| not allowed in filenames in Windows
    name = re.sub(r'[\\/:*?"<>|]', '_', name)
    # TODO: check if a file is already present with same name
    out = open(name, 'ab')
    for i, t in enumerate(threads):
        t.join()
        out.write(open('%s/%04d' % (ud, i), 'rb').read())

    summary(name, size, time.clock() - start)
    shutil.rmtree(ud)

def main():
    IPs = get_IPs()
    print len(IPs), 'IPs available.'
    for ip in IPs:
        adapter = requests_toolbelt.adapters.SourceAddressAdapter(ip)
        session = requests.Session()
        session.mount('http://', adapter)
        session.mount('https://', adapter)
        sessions_queue.put(session)

    while True:
        threading.Thread(target=download, args=(raw_input(),)).start()

if __name__ == '__main__':
    sessions_queue = Queue.Queue()
    KB = 1024
    MB = 1024*KB
    # TODO: optimal size?
    chunk = 100*KB
    main()

I am using it with about 100 IP addresses on my Ethernet -- each with about 100 KB/s speed. What'd be optimal configuration? (numbers of threads, chunk size)

You could rewrite your get_IPs function to be a list comprehension instead:

return [i.rsplit(' ', 1)[-1] for i in map(str.strip, os.popen('ipconfig'))
        if i.startswith('IP')]

map will call strip on all of the results from 'ipconfig' and then you can iterate over that, ignoring any values that don't start with "IP".

In worker you're using a loop to retry after timeouts. But you're just using 2 arbitrarily. Use a constant here so it's clear what you're doing, and easy to change later:

You also multiple times open files, but you should always try to use with, known as the context manager. It automatically closes the file even in the event that an error is raised. It's the safest way to open a file.

with open(filepath) as filename:
    execute_code_with(filename)
print("Done with filename")

Once you leave that indented block, the file is automatically closed. No need to even call filename.close().


Determining cell direction in a 2D grid I am making a simple function that retrieves a 3x3 cells out of NxM grid and determines the direction of cells base on their previous and next neighbor. It will return either any of the following

HORIZONTAL
VERTICAL
TOP_LEFT
TOP_RIGHT
BOTTOM_LEFT
BOTTOM_RIGHT
or INDETERMINATE

Suppose I have this data:

0 1 0
0 1 0
0 1 0
// Direction: VERTICAL

0 0 0
1 1 1
0 0 0
// Direction: HORIZONTAL

0 1 0        0 1 0        0 0 0        0 0 0
1 1 0        0 1 1        1 1 0        0 1 1
0 0 0        0 0 0        0 1 0        0 1 0
//TOP_LEFT   TOP_RIGHT    BOTTOM_LEFT  BOTTOM_RIGHT

0 0 0
1 0 0
1 0 0
// Direction: INDETERMINATE

This function would run many times and would vary(increase) depending on some other factors.

My functioning code so far is this:

var SNAKE_BODY = 1;
var SNAKE_HEAD = 2;

function isSnake(cell) {
    return cell == SNAKE_BODY || cell == SNAKE_HEAD;
}

function getMatrixNeighbors(x, y, board) {
    var neighbors = [];

    for(var row = y - 1; row <= y + 1; ++row) {
        for(var col = x - 1; col <= x + 1; ++col) {
            if ( col >= 0 && col < board.width
              && row >= 0 && row < board.height) {
                var cell = board.at(row, col);
                neighbors.push(cell);
            } else {
                neighbors.push(EMPTY);
            }
        }
    }
    return neighbors;
}

function getBodyDir(x, y, board) {

    var cells = getMatrixNeighbors(x, y, board);

    var top     = cells[1];
    var bottom  = cells[7];
    var left    = cells[3];
    var right   = cells[5];

    if ( isSnake(top) && isSnake(bottom) ) {
        if ( isSnake(cells[0])
          || isSnake(cells[2])
          || isSnake(cells[6])
          || isSnake(cells[8]) ) {
            return BODY_DIR_NEGLECT;
        }
        return BODY_DIR_VERTICAL;
    }

    if ( isSnake(left) && isSnake(right) ) {
        if ( isSnake(cells[0])
          || isSnake(cells[2])
          || isSnake(cells[6])
          || isSnake(cells[8]) ) {
            return BODY_DIR_NEGLECT;
        }
        return BODY_DIR_HORIZONTAL;
    }

    if ( isSnake(top) && isSnake(left) ) {
        return BODY_DIR_TOP_LEFT;
    }

    if ( isSnake(top) && isSnake(right) ) {
        return BODY_DIR_TOP_RIGHT;
    }

    if ( isSnake(bottom) && isSnake(left) ) {
        return BODY_DIR_BOTTOM_LEFT;
    }

    if ( isSnake(bottom) && isSnake(right) ) {
        return BODY_DIR_BOTTOM_RIGHT;
    }

     // return BODY_DIR_VERTICAL;
     return BODY_DIR_UNKNOWN;
}

I think this is the bottleneck in my app so I would like to know if there's anything you could suggest to improve the processing speed of this. Dirty hack is welcomed also as this is scripting and soon to be release.

Because neither row nor board.height depend on col, you could save two comparisons and an and in your getMatrixNeighbors function:

for(var row = y - 1; row <= y + 1; ++row) {
    var isInBounds = (row >= 0 && row < board.height);
    for(var col = x - 1; col <= x + 1; ++col) {
        if ( col >= 0 && col < board.width
                      && isInBounds) {
            neighbors.push(board.at(row, col));
        }
        [...]
    }
}

Note also that I removed the unneeded cell variable. It will probably not increase performance, but the code is nicer, I think.

I don't know what values x and y could possibly have, but I would assume that you can somehow save checking col >= 0 (and possibly some of the other bounds checks) each time.

You could also try to save x + 1 and board.width in a local variable to save the computation/accessing, but I would assume that either the compiler optimizes this for you, or that the introduction of an additional variable offsets the performance gain.

I don't think that getBodyDir is the bottleneck (although it would be good if you would profile this), but here you could also save the result of isSnake(top) etc in a local variable, instead of saving top as you are currently doing (top is never used anywhere except as argument for isSnake, so this would actually make sense and should result in nicer code).


Statefull Strategy pattern I have a situation in a class tries to create a group of same type of components and if some component fails then it needs to decide whether it should continue or throw the exception. Now the behavior whether to continue or re-throw depends in the context in which that class is used.

So a obvious solution was to pass the behavior from outside in a constructor, which is effectively a strategy pattern.
For now I had two implementations:

ContinuePolicy
AbortPolicy

These both policies were stateless so I created a single instance for them. Now I needed a strategy called SingleSuccessPolicy ( which ignores exception if atleast one of the components is successfully created). Now the problem is that to know whether all are failing or there is at least one success, the strategy needs to store some state (possibly count of components to be created). The side effect of it is that it makes creating a single instance infeasible.

Java Code:

class GroupComponent {
   private final ComponentExceptionPolicy exceptionPolicy;
   public GroupComponent(ComponentExceptionPolicy policy, GroupData data) {
      this.exceptionPolicy = policy;
   }

   public void createComponents() throws Exception {
      for(ComponentData compData : data.getComponentsData()) {
         try {
           createComponent(compData)
         } catch (Exception e) {
           policy.apply(compData, e);
         }
      }
   }
}

Code for Strategies:

public interface ComponentExceptionPolicy {
    public void apply(ComponentData data, Exception e);
}

class ContinuePolicy extends ComponentExceptionPolicy {
    @Override
    public void apply(ComponentData data, Exception e) throws Exception {
      //just log it and continue
    }
}

class AbortPolicy extends ComponentExceptionPolicy {
    @Override
    public void apply(ComponentData data, Exception e) throws Exception {
       throw e;
    }
}

class MaximumFailuresPolicy extends ComponentExceptionPolicy {
   private int n; //the expected size of group component

   MaximumFailuresPolicy(int n) {
       this.n = n;
   }

   @Override
   public void apply(ComponentData data, Exception e) {
      //on each exception I decrement count
      if(--n == 0) { //check if exception threshold is reached
         //as soon as found that all have failed then exception is thrown,
         //if any of component succeeds, then n will not reach to 0 and it
         //will just continue
         throw e;
      } else {
         //just log
      }
   }
}

EDIT:

To clarify, MaximumFailuresPolicy is meant to check that atleast one of the component should be initialized successfully. Maybe I have named it incorrectly

Is it a proper way to achieve this? Any help is appreciated.

Policy Naming and Behaviour
Your SingleSuccessPolicy name is not a good one. What you actually have here is a MaximumFailuresPolicy.
To effectively create a "real" SingleSuccessPolicy, you'd need to evaluate the final result of your foreach loop. But that is simply impossible in the catch-block.
The problem I see with your code is, that your SingleSuccessPolicy is required to be correctly initialized with new SingleSuccessPolicy(compData.size()-1);. As soon as a differnt SingleSuccessPolicy is passed in, the behaviour is no more the desired one.
You might consider creating the policy inside the GroupComponent constructor. Then you can make sure that the MaximumFailuresPolicy will always behave as a SingleSuccessPolicy, but that would change a whole lot of your structure.
This assumes your compData are immutable after construction, which in turn would IMO warrant a factory / builder pattern instead of what you have here.
What you want to do is yours to decide, but the current way is IMO too unreliable, especially when the ExceptionPolicy depends on what data you are handling. That is not the point of an ExceptionPolicy.
Nitpicks:
Your indentation is not conform to java-standards. Oracle consistently uses an indentation of 4 spaces (or one tab) for blocks.
From method to for-loop, you have 3 spaces, from for-loop to try-catch the same, and from try-catch to statements, you have 2 spaces.
All three alternatives violate conventions, but above all, you're inconsistent!
Additionally I suggest you mark your arguments as final, whereever possible.


Create and back up files I have to develop a class that creates new files. If a file with the given name already exists, it should be renamed by addition of the timestamp to the file name. The file name should be human-readable, so I can use neither UUID nor createTempFile. The code works, but looks too bulky.

public class FileBackup {

    /**
     * Creates new file. If file with given name exists, then backups
     * it by renaming and adding time stamp to file name;
     *
     * @param filePath the fully qualified name of file

     * @return the file on success; otherwise returns null
     *
     * @throws IOException
     */
    public static File backupAndCreateFile(String filePath) throws IOException  {

        File fileToCreate = new File(filePath);

        boolean backupRequired =  fileToCreate.isFile();

        if (backupRequired && !backupFile(fileToCreate)) {
            return null;
        }

        File file = new File(filePath);
        return file.createNewFile() ? file : null;
    }

    private static final String pattern = "-dd_M_yyyy-hh_mm_ss";
    private static final DateFormat dateFormat = new SimpleDateFormat(pattern);
    private static String generateBackupName (String filePath) {
        String name = getFileName (filePath);
        String ext = getFileExtention (filePath);
        return name + dateFormat.format(new Date()) + ext;
    }

    private static String getFileName (String filePath) {
        int i = filePath.lastIndexOf('.');
        return i == -1 ? filePath : filePath.substring(0, i);
    }

    private static String getFileExtention (String filePath) {
        int i = filePath.lastIndexOf('.');
        return i == -1 ? "" : filePath.substring(i);
    }

    private static boolean backupFile (File file) {

        String filePath = file.getAbsolutePath();

        while (true) {

            String backupName = generateBackupName (filePath);
            File backup = new File(backupName);

            if (!backup.isFile()) return file.renameTo(backup);

            // File with generated name exists, so
            // sleep for 0.5 second and try another name
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {return false;}; // never should be here
        }
    }
}

In my opinion your code it's not so bulky but I would do something like below with few changes. I have not tested it too much but it should works.

I will use FilenameUtils for easy manipulation with files like getting basename or extension of file - it will save you some of the lines and also it is one of the most used library for file manipulation.

I would remove String getFileName and String getFileExtention and create self-described function and delete in code comments. I also removed return false for InterruptedException - I would like to get another draft of the name in the next iteration.

I dont like spaggetti code when some string is creating like (with +):

return name + dateFormat.format(new Date()) + ext;

so here I would use StringBuilder or String.format or something like that.

Below is what I have done in few minutes.

import org.apache.commons.io.FilenameUtils;

import java.io.File;
import java.io.IOException;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;

public class FileBackup {

    private static final String pattern = "-dd_M_yyyy-hh_mm_ss.";
    private static final DateFormat dateFormat = new SimpleDateFormat(pattern);

    /**
     * Creates new file. If file with given name exists, then backups
     * it by renaming and adding time stamp to file name;
     *
     * @param filePath the fully qualified name of file

     * @return the file on success; otherwise returns null
     *
     * @throws IOException
     */
    public static File backupAndCreateFile(String filePath) throws IOException {
        return failedBackuOfExistingFile(filePath) ? null : new File(filePath);
    }

    private static boolean failedBackuOfExistingFile(String filePath) {
        File fileOnPath = new File(filePath);
        return  fileOnPath.exists() && !successBackupFile(fileOnPath);
    }

    private static boolean successBackupFile(File fileToBackup) {

        while (true) {

            File backupDraft = new File(generateBackupName(fileToBackup.getAbsolutePath()));
            if (!backupDraft.exists()) {
                return fileToBackup.renameTo(backupDraft);
            }
            fileWithGeneratedNameExistsNowSleepForSomeTime();
        }
    }

    private static void fileWithGeneratedNameExistsNowSleepForSomeTime(){
        try {
            Thread.sleep(500);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    private static String generateBackupName (String filePath) {
        String fileName = FilenameUtils.getBaseName(filePath);
        String fileExtension = FilenameUtils.getExtension(filePath);
        return new StringBuilder().append(fileName)
                .append(dateFormat.format(new Date()))
                .append(fileExtension)
                .toString();
    }
}


Securely hash passwords Since hashing algorithms isn't something to mess around with as a beginner. Several howto's explain that one should use already made solutions.
Examples of such pages:

https://crackstation.net/hashing-security.htm
https://owasp.org/www-project-cheat-sheets/cheatsheets/Password_Storage_Cheat_Sheet.html#pbkdf2

So I opted for ready-made solutions from java.security and java.crypto library packages.
But I feel there is still room for messing up, especially with regard to the parameters in PBEKeySpec(password, salt, iterations, keyLength).

According to some HOWTOs, salt should be as long in bytes as the output from the hash function. So I chose 64, since SHA-512 outputs (64*8=512 bits) 64 bytes. (Although, it seems I can get larger output simply by increasing keyLength argument above 512, which makes me wonder).

So basically. Do you guys/girls find this code reasonable? Especially in regards to the arguments passed?
If not, please tell me what to change, how and why.

package my.application;

import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.security.spec.InvalidKeySpecException;
import java.util.Arrays;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.PBEKeySpec;
import org.apache.commons.codec.binary.Hex;

public class PasswordHasher {
    private int ammountOfBytes = 64;
    private int keyLength = 512;
    private int iterations = 100000;
    private byte[] salt;
    private byte[] hash;
    private char[] password;
    private String saltHex;
    private String hashHex;

    public void hash(String rawPassword) {
        makeSalt();
        password = rawPassword.toCharArray();
        PBEKeySpec spec = new PBEKeySpec(password, salt, iterations, keyLength);
        SecretKey key;
        try {
            SecretKeyFactory generator = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA512");
            key = generator.generateSecret(spec);
            hash = key.getEncoded();
            hashHex = Hex.encodeHexString(hash);
            spec.clearPassword();
            key = null;
        }
        catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        catch (InvalidKeySpecException e) {
            e.printStackTrace();
        }

    }

    public void destroy() {
        saltHex = null;
        hashHex = null;
        Arrays.fill(password, (char) 0);
        Arrays.fill(salt, (byte) 0);
        Arrays.fill(hash, (byte) 0);
    }

    private String makeSalt() {
        try {
            SecureRandom random = SecureRandom.getInstance("SHA1PRNG");
            salt = new byte[ammountOfBytes];
            random.nextBytes(salt);
            saltHex = Hex.encodeHexString(salt);
        }
        catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        return saltHex;

    }

    public String getSaltHex() {
        return saltHex;
    }

    public String getHashHex() {
        return hashHex;
    }

}

There are a few things wrong security wise before we even get to the parameters.

private char[] password;

Storing the plain text password in an instance field makes it discoverable from memory dumps for a considerably long time. There is no need for the field to be an instance field since it is only used in the hash method.

public void hash(String rawPassword) {

Passing plain text password as a String parameter makes it impossible to be securely disposed of. When being passed around, passwords need to be char arrays and they need to be cleared immediately when they are no longer needed.

public void destroy() {

You have the right idea that the class needs to be cleared from sensitive data, but here you have made the clearing the responsibility of the caller while the data needing to be cleared is completely irrelevant to the caller. You should avoid having to rely on other people when dealing with sensitive data. Someone will forget to call destroy() because it is not something that needs to be done in a garbage collected environment. At least you could make it Closeable so there is some common contractual indication about the class needing cleanup. Because the method also clears the actual payload it is guaranteed that the sensitive data will be in memory as long as the payload is needed, which is much longer than the sensitive data needs to exist. But it's better to write the class so that it doesn't need external cleanup at all.

private int ammountOfBytes = 64;
private int keyLength = 512;
private int iterations = 100000;

These should be static and final constants, since you don't have any means to change them.

private String saltHex;
private String hashHex;

These are the only fields that have a information that needs to be kept for a longer period. Instead of wrapping all the fields into a same PasswordHasher class, you should put these two fields into a dedicated data class called HashedPassword, have all the other code be static utilities and have the hash method return the data class.

If we look at the naming, PasswordHasher implies that the class is an actor that implements an algorithm. Your implementation uses it as both a data container and the algorithm. It is better to separate the responsibilities to two different classes (single responsibility principle)


Given some text and a word list, print the 7 most common correctly spelled words I've got a basic python function that I've been tasked with finishing in a class.

It's already fulfilling all the requirements for an A as it's an introductory course to Python, but I'd like to get some advice on it still as it's taking quite some time to execute.

I've got a few years of experience with general programming, but I'm still quite new to Python. As such any sort of advice on what might be taking up time would be appreciated.

As it stands at the moment, it takes about .5 seconds to run through the code and print all the data.

A bit of detail to the program:

It reads three files:

A part of Alice in the Wonderland's first chapter (alice-ch1.txt)
A list of common words (common-words.txt)
And a list of correctly spelt words.

Finally it prints the top 7 words that have passed through the filters.

def analyse():
    #import listdir
    from os import listdir
    #import counter
    from collections import Counter
    files = "*************************************\n"
    for file in listdir():
        if file.endswith('.txt'):
            files = files + file + "\n"
    choice = input("These are the files: \n" + files + "*************************************\nWhat file would you like to analyse?\n")

    if choice.strip() == "":
        choice = "alice-ch1.txt"
    elif choice.endswith(".txt"):
        print(choice)
    else:
        choice = choice + ".txt"
    print(choice)

    with open(choice) as readFile, open('common-words.txt') as common, open('words.txt') as correct:
        correct_words = correct.readlines()
        common_words = common.readlines()
        common_words = list(map(lambda s: s.strip(), common_words))
        correct_words = list(map(lambda s: s.strip(), correct_words))

        words = [word for line in readFile for word in line.split()]
        for word in list(words):
            if word in common_words or not word in correct_words:
                words.remove(word)
        print("There are " + str(len(words)))
        c = Counter(words)
        #for word, count in c.most_common():
        #    print (word, count)
        nNumbers = list(c.most_common(7))
        out = ""
        print("*************************************\nThese are the 7 most common:")
        for word, count in nNumbers:
                out = out + word + "," + str(count) + "\n"
        print(out + "\n*************************************")

    input("\nPress enter to continue...")

List Comprehension

I'm not at all sure it'll run much faster (though it might--it's a little faster under Python 2.7, anyway), but I think a more Pythonesque approach would be to replace your loop:

    for word in list(words):
        if word in common_words or not word in correct_words:
            words.remove(word)

... with a list comprehension, something like:

words = [word for word in words if not word in common_words and word in correct_words]

Algorithm

To gain substantial speed, you probably want to rearrange your operations. Right now you're looking at each word in the input separately (and looking at all of them). Then, after you've found all the words that aren't common and are spelled correctly, you choose the 7 most common.

I'd reverse that: start by creating a Counter of all the input words. Then print those filtering words that are common or aren't spelled correctly. When you've printed seven of them, stop:

    words = [ word for line in readFile for word in line.split() ]

    c = Counter(words)

    counter = 0

    for word, count in c.most_common():
        if not word in common_words and word in correct_words:
           print word + ", "  + str(count)
           counter = counter + 1
           if counter == 7:
               break;

You could simplify that inner loop a little by by doing a little preprocessing. Instead of testing against both the common and correctly spelled lists, you could start by removing all the common words from the correctly spelled list, to get a single list of the words that are acceptable. Then when you're printing out your results, you'd check only against that one list. Given the sizes of the lists, this would be a win primarily if you did it once and saved the result so you can re-use it. If you re-did the preprocessing every time you ran the program, you'd probably use more time on the preprocessing than you'd save on the output loop.

There's probably more than can be done to make this neater as well, but nothing occurs to me immediately. At least for me in a quick test, this seems to run around ten to fifteen (or so) times as fast as the code in the question. The exact difference in speed will probably depend (heavily) on the size of input file though. In particular, I believe this is changing from \$O(N^2)\$ complexity to an expected complexity around \$O(N)\$1.

As an aside, I did consider (and test with) using a set instead of a list for common_words and correct_words, but at least in my testing, with the updated algorithm this didn't seem to make a difference that I could replicate dependably. With the original algorithm, however, changing these from list to set can improve performance considerably.

Logic

As it stands right now, your if/then chain:

if choice.strip() == "":
    choice = "alice-ch1.txt"
elif choice.endswith(".txt"):
    print(choice)
else:
    choice = choice + ".txt"
print(choice)

... prints out choice twice if it starts out ending with .txt. I suspect you really want something closer to:

if choice.strip() == "":
    choice = "alice-ch1.txt"
elif not choice.endswith(".txt")
    choice = choice + ".txt"
print(choice)

Magic number

It would probably be better to use something on the order of:

mostCommonLimit = 7

# ...

if counter == mostCommonLimit
    break;

If you want to get technical, it probably is still \$O(N^2)\$. The Counter presumably uses a hash table, which is \$O(1)\$ expected complexity, but can be \$O(N)\$ in the worst case (where all keys produce equivalent hashes). This is, however, so rare that in practice it's often ignored.


Using a map of shared_ptr instead of single pointers as class members I'm working on a node.js bindings for libcurl. As libcurl accepts many callback functions as options (like CURLOPT_READFUNCTION for example), I had to store their respective javascript callbacks somewhere when those options were set.

Initially I had the following class members (Easy.h:71):

Nan::Callback *cbChunkBgn;
Nan::Callback *cbChunkEnd;
Nan::Callback *cbDebug;
Nan::Callback *cbHeader;
Nan::Callback *cbFnMatch;
Nan::Callback *cbOnSocketEvent;
Nan::Callback *cbProgress;
Nan::Callback *cbRead;
Nan::Callback *cbXferinfo;
Nan::Callback *cbWrite;

Initialization also was too much code (Easy.cc:58):

Easy::Easy() :
    cbChunkBgn( nullptr ), cbChunkEnd( nullptr ), cbDebug( nullptr ), cbHeader( nullptr ),
    cbFnMatch( nullptr ), cbOnSocketEvent( nullptr ), cbProgress( nullptr ), cbRead( nullptr ),
    cbXferinfo( nullptr ), cbWrite( nullptr ),
    pollHandle( nullptr ),
    isCbProgressAlreadyAborted( false ), isMonitoringSockets( false ),
    readDataFileDescriptor( -1 ), id( Easy::counter++ ), isInsideMultiHandle( false ), isOpen( true )

Also, since one easy handle can be duplicated, I had a copy constructor which took care of copying the other handle data to itself, this included the callbacks. Most of them looks like that (Easy.cc:120):

if ( orig->cbHeader != nullptr ) {
    this->cbHeader = new Nan::Callback( orig->cbHeader->GetFunction() );
}

Trying to improve this code, I thought on using a map (typedef std::map<CURLoption, std::shared_ptr<Nan::Callback>> CallbacksMap;) which would store all the callbacks being used (new_Easy.h:72).

Copying the callbacks from another handle (in the copy constructor) would look like the following (new_Easy.cc:90):

this->callbacks.insert( orig->callbacks.begin(), orig->callbacks.end() );

Setting/removing a new callback, would looks like the following (new_Easy.cc:1134):

obj->callbacks.erase( CURLOPT_CHUNK_BGN_FUNCTION );
// ...
obj->callbacks[CURLOPT_CHUNK_BGN_FUNCTION].reset( new Nan::Callback( callback ) );

Where obj is an instance of the Easy class.

Retrieving one callback so it can be called (new_Easy.cc:509):

CallbacksMap::iterator it = obj->callbacks.find( CURLOPT_CHUNK_BGN_FUNCTION );
// ...
it->second->Call( ... );

And I would remove all those delete's from the destructor.

Thoughts? Would that be an improvement or just some unnecessary modification? Any better alternatives?

Also I would love any other suggestions for other parts of the code that you feel that are wrong or that can be improved.

I'm not particularly familiar with libcurl, but using a std::map for storing the callbacks is a good thing. One of my rules when programming is; If I need to store more than 1 thing of the same type, use a container for it. Which you've done, and it's a good thing.

There are a couple of nitpicks, and I'm assuming you have the possibility to use C++11.

Variables in class can be initialized with a default value.

...
Nan::Callback *cbChunkBgn = nullptr;
Nan::Callback *cbChunkEnd = nullptr;
Nan::Callback *cbDebug = nullptr;
Nan::Callback *cbHeader = nullptr;
...

Your constructor initializer lists aren't readable.

Change this:

Easy::Easy( Easy *orig ) :
    callbacks(), cbOnSocketEvent( nullptr ), pollHandle( nullptr ),
    isCbProgressAlreadyAborted( false ), isMonitoringSockets( false ),
    readDataFileDescriptor( -1 ), id( Easy::counter++ ), isInsideMultiHandle( false ), isOpen( true )

Into this:

Easy::Easy( Easy *orig )
    : callbacks()
    , cbOnSocketEvent( nullptr )
    , pollHandle( nullptr )
    , isCbProgressAlreadyAborted( false )
    , isMonitoringSockets( false )
    , readDataFileDescriptor( -1 )
    , id( Easy::counter++ )
    , isInsideMultiHandle( false )
    , isOpen( true )

You may also benefit from using delegating constructors. I'm not sure how it will fit into your design.

Easy::Easy( Easy *orig )
    : Easy()

Maybe you can skip the long constructor initializer lists by using default arguments all together.

Use auto where necessary. Transform this;

CallbacksMap::iterator it = obj->callbacks.find( CURLOPT_FNMATCH_FUNCTION );

Into this;

auto it = obj->callbacks.find( CURLOPT_FNMATCH_FUNCTION );

There is probably more, but those are what I saw at the first glance of the code.


Printing out prime numbers from an array given a max number Is there a shorter or maybe a cleaner way of doing:

  Using your is_prime? method, write a new method, primes that takes a (non-negative, integer) number max and returns an array of all prime numbers less than max.

def is_prime?(max)
  i = 2
  while i < max
    is_divisible = ((max % i) == 0)
    if is_divisible
      # divisor found; stop and return false!
      return false
    end

    i += 1
  end

  # no divisors found
  true
end
def primes(max)
  primes_arr = []

  i = 2
  while i < max
    if is_prime?(i)
      # i is prime; add it to the array
      primes_arr << i
    end

    i += 1
  end

  # return primes_arr
  primes_arr
end

Here it is using Prime#prime?:

  Suppose I want to get all the prime numbers less than 9

require 'prime'

a = (1..12).to_a
p a.select{|e| e.prime? and e < 9 }
# >> [2, 3, 5, 7]

Here is a method

require 'prime'

def prime_below_max(a,max)
   a.select{|e| e.prime? and e < max }
end

ary = (1..12).to_a
p prime_below_max(ary,9)
# >> [2, 3, 5, 7]


Detecting if two given strings are isomorphic using Java data structures So I have written the following code and it works for various same length isomorphic strings I have tried. However I am not sure what are some time complexity improvements and coding tweaks that could be applied to the code:

/**
 * Created by mona on 5/26/16.
 */
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Collections;

public class IsomorphicStrings {
    //the words "abca" and "zbxz" are isomorphic
    //aabc a(2) b(1) c(1)
    //zzbx z(2) b(1) x(1)
    //my algorithm
    //create a sorted hashmap  on value
    //check to see if two hashmap are equal based on their value set
    //assuming two isomorphic strings are of the same length

    public static boolean areIsomorphic(String s1, String s2) {
        Map<Character, Integer> freqMap1 = new HashMap<>();
        Map<Character, Integer> freqMap2 = new HashMap<>();

        for (int i=0; i<s1.length(); i++) {
            if (freqMap1.containsKey(s1.charAt(i))) {
                int freq1 = freqMap1.get(s1.charAt(i));
                freqMap1.put(s1.charAt(i), freq1 + 1);
            } else {
                freqMap1.put(s1.charAt(i), 1);
            }

        }

        for (int i=0; i<s2.length(); i++) {
            if (freqMap2.containsKey(s2.charAt(i))) {
                int freq2 = freqMap2.get(s2.charAt(i));
                freqMap2.put(s2.charAt(i), freq2 + 1);
            }
            else {
                freqMap2.put(s2.charAt(i), 1);
            }

        }

        List<Integer> freqList1 = new ArrayList<>();
        List<Integer> freqList2 = new ArrayList<>();

        for (Map.Entry entry: freqMap1.entrySet()) {
            freqList1.add((Integer) entry.getValue());
        }

        for (Map.Entry entry: freqMap2.entrySet()) {
            freqList2.add((Integer) entry.getValue());
        }

        Collections.sort(freqList1);
        Collections.sort(freqList2);

        return freqList1.equals(freqList2);

    }

    public static void main(String[] args) {
        String s1="abca";
        String s2="zbxz";
        System.out.println(areIsomorphic(s1, s2));
    }
}

/* side note: can isomorphic strings be of different lengths? Then what algorithm do you suggest? */

Your build two HashMap<Character, Integer>, then two ArrayList<Integer>, then sort the lists, then compare the lists.  Your logic is too complicated, I think.  Furthermore, you aren't taking advantage of the symmetry in the problem — nearly every line of code appears in duplicate. Even worse, the code doesn't even do what you claim; rather, it tests whether the inputs are isomorphic anagrams of each other.

Going by the definition, we can just build a character-to-character map from one string to the other, and fail as soon as we encounter an unexpected character.  This should be O(n), and possibly faster if a mismatch is detected early.

The code works equally well on any pair of CharSequences, not just Strings, so we might as well generalize.

import java.util.HashMap;
import java.util.Map;

public class IsomorphicStrings {
    public static boolean areIsomorphic(CharSequence s1, CharSequence s2) {
        return isSurjective(s1, s2) && isSurjective(s2, s1);
    }

    private static boolean isSurjective(CharSequence s1, CharSequence s2) {
        if (s1.length() != s2.length()) return false;

        Map<Character, Character> surjection = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            Character prev = surjection.put(c1, c2);
            if (prev != null && prev != c2) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(areIsomorphic(args[0], args[1]));
    }
}