Items also occurs in a set The task

  You're given strings J representing the types of stones that are
  jewels, and S representing the stones you have.  Each character in S
  is a type of stone you have.  You want to know how many of the stones
  you have are also jewels.

  The letters in J are guaranteed distinct, and all characters in J and
  S are letters. Letters are case sensitive, so "a" is considered a
  different type of stone from "A".

  Example 1:

  Input: J = "aA", S = "aAAbbbb" Output: 3

  Example 2:

  Input: J = "z", S = "ZZ" Output: 0

  Note:

  S and J will consist of letters and have length at most 50. The
  characters in J are distinct.

My functional solution

const findNumberOfJewels = (j,s) =>  [...s].reduce((num, x) => [...j].includes(x) ? num + 1 : num , 0);

console.log(findNumberOfJewels("aA", "aAAbbbb"));

My imperative solution

function findNumberOfJewels2(j,s) {
  let res = 0;
  const set = new Set(j);
  for (const x of s) {
    if (set.has(x)) { ++res; }
  }
  return res;
};

console.log(findNumberOfJewels2("aA", "aAAbbbb"));

The functional approach is almost certainly faster despite having worse big-O — \$O(j \cdot s)\$ functional vs \$O(j + s)\$ imperative — because linear searches of small arrays are very fast.

You don't need to destructure j and adding a boolean to a number coerces the boolean to 0 or 1.

sum is a better name than num and c is a good name for a character iterator.

const findNumberOfJewels = (j,s) => [...s].reduce( (sum, c) => sum + j.includes(c),  0 );


UserScript that summarizes Stack Exchange flag counts I am working on a UserScript that displays total flag counts and other information on the Flag Summary page.

Example:

Everything is working correctly but this bit of code seems rather repetitive and I'm sure it could be improved upon.

The following code pulls the total count of each flag type from the flag summary page.

Is there anything I can do to improve or shorten this code?

var helpful = 0,
    declined = 0,
    disputed = 0,
    aged = 0,
    total = 0;

$("td > a:contains('helpful')").parent().prev().each(function () {
    helpful += parseInt($(this).text().replace(",",""));
});

$("td > a:contains('declined')").parent().prev().each(function () {
    declined += parseInt($(this).text().replace(",",""));
});

$("td > a:contains('disputed')").parent().prev().each(function () {
    disputed += parseInt($(this).text().replace(",",""));
});

$("td > a:contains('aged')").parent().prev().each(function () {
    aged += parseInt($(this).text().replace(",",""));
});

$("td > a:contains('flags')").parent().prev().each(function () {
    total += parseInt($(this).text().replace(",",""));
});

Here is an example of what the markup looks like:

            441
            post flags

            41
            waiting for review

            310
            helpful

            5
            declined

            36
            disputed

            49
            aged away

            412
            comment flags

            6
            waiting for review

            406
            helpful

            5
            spam flags

            5
            helpful

            &nbsp;

            Clear all filters

            &nbsp;

            Filter your flag history by selecting a category above.

Note: I've only included the relevant part as I didn't want to add a bunch of noise to this post.

I don't particularly have an issue with your HTML, however your JavaScript could be improved.

Currently, you have a lot of duplicate logic. You should move it to a function that each case can call.

Like the following:

function flagCount(selector){
    var count = 0;
    $(selector).parent().prev().each(function () {
        count += parseInt($(this).text().replace(",", ""));
    });
    return count;
}

If I pass 0 into parseInt without the second parameter, it will return a hex number...

Using Number is better, and more readable.

Leaving you totally with:

function flagCount(selector){
    var count = 0;
    $(selector).parent().prev().each(function () {
        count += Number($(this).text().replace(",", ""));
    });
    return count;
}
var helpful = flagCount("td > a:contains('helpful')");
var declined = flagCount("td > a:contains('declined')");
var disputed = flagCount("td > a:contains('disputed')");
var aged = flagCount("td > a:contains('aged')");
var total = flagCount("td > a:contains('flags')");

Note, you could string concatenate the selector inside the function, but that limits the use case that you select another DOM element.


Computing the sum of squared differences About Data: 3D data (100x100x20).

Computation/Formula and Method: I am trying to compute the sum of squared differences along rows, columns and angles for various time differences.

%% Grid and time paramters

%# Grid parameters
nRows=100;
nCol=100;
InitLag_Row=0;
InitLag_Col=0;
InitLag_Ang=0;
LessLags=20;
nLags_Row=nRows-LessLags;
nLags_Col=nCol-LessLags;
nLags_Ang=min(nRows,nCol)-LessLags;

%# Time parameters
T=1:1:20;
nT=numel(T);

%# Load concentrations data file with 100x100x20 dimensions
load('c.mat')

%% Shift values along rows for all columns and all time steps
for hRow=InitLag_Row:nLags_Row
    c_ShiftedRow(:,:,:,hRow+1)=circshift(c(:,:,:),[-hRow 0]);
end

%% Shift values along columns for all rows and all time steps
for hCol=InitLag_Col:nLags_Col
    c_ShiftedCol(:,:,:,hCol+1)=circshift(c(:,:,:),[0 -hCol]);
end

%% Shift values along NW-SE and NE-SW directions for all time steps
for hAng=InitLag_Ang:nLags_Ang
    c_ShiftedNWSE(:,:,:,hAng+1)=circshift(c(:,:,:),[-hAng -hAng]);
    c_ShiftedNESW(:,:,:,hAng+1)=circshift(c(:,:,:),[-hAng hAng]);
end

idel_t=1; % initialize index for zero time lag
for del_t=0:nT-1 % time lag
    for nLags_t=1:nT-del_t; % number of time lags formed with del_t lag value
        for hRow=InitLag_Row:nLags_Row
            variogramTemp_hRow3D=(cumsum(((c(1:end-hRow,:,nLags_t)-...
                c_ShiftedRow(1:end-hRow,:,nLags_t+del_t,hRow+1)).^2),1))./...
                (2*size(c(1:end-hRow,:,nLags_t),1));

            variogram_hRow3D(hRow+1,:,nLags_t,idel_t)=variogramTemp_hRow3D(end,:)./...
                mean(var(c(1:end-hRow,:,[nLags_t,nLags_t+del_t]),0,1),3);
        end
        %% Variogram along columns for all images
        for hCol=InitLag_Col:nLags_Col
            variogramTemp_hCol3D=(cumsum(((c(:,1:end-hCol,nLags_t)-...
                c_ShiftedCol(:,1:end-hCol,nLags_t+del_t,hCol+1)).^2),2))./...
                (2*size(c(:,1:end-hCol,nLags_t),2));

            %# normalized variogram values at all times for different lags at all 'nRows'
            variogram_hCol3D(:,hCol+1,nLags_t,idel_t)=variogramTemp_hCol3D(:,end)./...
                mean(var(c(:,1:end-hCol,[nLags_t,nLags_t+del_t]),0,2),3);
        end
        %% Variogram along NW-SE and NE-SW directions for all images
        for hAng=InitLag_Ang:nLags_Ang
            variogramTemp_h3DNWSE=(cumsum(((c(1:end-hAng,1:end-hAng,nLags_t)-...
                c_ShiftedNWSE(1:end-hAng,1:end-hAng,nLags_t+del_t,hAng+1)).^2),1))./...
                (2*size(c(1:end-hAng,1:end-hAng,nLags_t),1));
            variogramTemp_h3DNESW=(cumsum(((c(1:end-hAng,end:-1:1+hAng,nLags_t)-...
                c_ShiftedNESW(1:end-hAng,end:-1:1+hAng,nLags_t+del_t,hAng+1)).^2),1))./...
                (2*size(c(1:end-hAng,end:-1:1+hAng,nLags_t),1));

            %# normalized variogram values/cumulative sum at all times for different lags along NW-SE and NE-SW directions
            variogram_h3DNWSE(hAng+1,1:nCol-hAng,nLags_t,idel_t)=variogramTemp_h3DNWSE(end,:)./...
                mean(var(c(1:end-hAng,1:end-hAng,[nLags_t,nLags_t+del_t]),0,1),3);
            variogram_h3DNESW(hAng+1,1:nCol-hAng,nLags_t,idel_t)=variogramTemp_h3DNESW(end,:)./...
                mean(var(c(1:end-hAng,end:-1:1+hAng,[nLags_t,nLags_t+del_t]),0,1),3);
        end
    end
    %# Change the zero matrices after nT-del_t to NaN
    variogram_hRow3D(:,:,nT-del_t+1:end,idel_t)=nan;
    variogram_hCol3D(:,:,nT-del_t+1:end,idel_t)=nan;
    variogram_h3DNWSE(:,:,nT-del_t+1:end,idel_t)=nan;
    variogram_h3DNESW(:,:,nT-del_t+1:end,idel_t)=nan;

    %# change to next time lag index
    idel_t=idel_t+1;
end

I would appreciate any help on ways to make this code faster and more efficient.

Here's a way to do it using pdist to generate both the differences in value, plus logical indices that you can use to select which distances you wish to look at/use further.

D1 = [1 2 3;4 5 6;7 8 9];
D2 = [9 8 7;6 5 4;3 2 1];
D = cat(3,D1,D2);

D(:,:,1) =

 1     2     3
 4     5     6
 7     8     9

D(:,:,2) =

 9     8     7
 6     5     4
 3     2     1

Y = repmat([1 2 3]', [1 3 2]); %# (' in comment to fix SO highlighting)
X = repmat([1 2 3],[3 1 2]);
T = repmat(cat(3,1,2),[3 3 1]);
D_diffsqrd = pdist(D(:),'euclidean').^2;
X_dist = pdist(X(:),'euclidean');
Y_dist = pdist(Y(:),'euclidean');
T_dist = pdist(T(:),'euclidean');
Angle_dist = pdist([X(:) Y(:)],'euclidean');

D_diffsqrd(X_dist==2 & T_dist==0 & Y_dist==0)
    4     4     4     4     4     4

D_diffsqrd(X_dist==0 & T_dist==0 & Y_dist==2)
    36    36    36    36    36    36

D_diffsqrd(X_dist==0 & T_dist==1 & Y_dist==0)
    64     4    16    36     0    36    16     4    64


Is this the right approach for Controller-Service-Dao implementation? I am a bit confused with Controller Service Dao implementation . I created a dummy User servlet along with Model controller dao and a service , though it will work , but is it the right approach. I am still confused about the purpose of service class

//user registration Service
//add user , delete user
@WebServlet("/useraction")
class UserController
{
    UserService userService = new userService();
    int id = request.getParameter("id");

    userService.userAction(int id,String action);
    //minimum code for sake of question
}

class UserService
{
    UserDao userDao = UserDaoImpl.getInstance();

    void userAction(int id,String action)
      switch(action){
       case "add" :
         userDao.addUser(id);
         break;
       case "delete" :
         userDao.deleteUser(id);
         break;
       default :
         throw IllegalArgumentException();
      }
    }
}

interface UserDao
{
    void deleteUser(int id);
    void addUser(int id);
}

class UserDaoImpl implements UserDao
{
    private static UserDaoImpl userDaoImpl = new UserDaoImpl();

    public static UserDaoImpl getInstance(){
        if(userDaoImpl == null)
            userDaoImpl = new UserDaoImpl();
        return userDaoImpl;
    }

    void deleteUser(int id){
        //some validations and db activity
    }

    void addUser(int id){
        //some validations and db activity
    }

}

//Model
class User
{
    private int id;
    private String name;
    private String email;
    //a lot more parameters
}

Questions i want to ask :

Is this the right approach for Controller dao service pattern?
Purpose of service class , is it for redirection only to dao or for validations also
Do we need to use inheritance for Dao classes ?

Thanks in Advance

There are various implementations of MVC or MVC inspired patterns, there aren't hard and fast rules to follow, each implementation is often tweaked to suit certain needs.

Here are some old threads that explain the responsibility of each layer and may answer some of your questions:

  Is this the right approach for Controller dao service pattern?

MVCS - Model View Controller Service

Responsibilities and use of Service and DAO Layers

  Purpose of service class , is it for redirection only to dao or for validations also?

Service layer vs DAO — Why both?

In MVC , DAO should be called from Controller or Model

  Do we need to use inheritance for Dao classes ?

Most effective way to reflect inheritance relationship in DAOs?


An Angular service to provide window and document objects In some components and services I need the window and document. So I created a small service, that provides these two objects.

windowAndDocument.service.ts:

import { Inject, Injectable } from '@angular/core';

import { DOCUMENT } from '@angular/common';

function getWindow (): any {
  return window;
}

@Injectable({
  providedIn: 'root',
})

export class WindowAndDocumentService {
  public window = null;

  constructor(@Inject( DOCUMENT ) public document :HTMLDocument) {
    this.window = getWindow();
  }
}

This works fine and can be imported into other services.

some.service.ts:

import { Injectable } from '@angular/core';

import { WindowAndDocumentService } from './windowAndDocument.service';

@Injectable({
  providedIn: 'root',
})

export class SomeService {
  constructor(private wads: WindowAndDocumentService) {}

  soSomething() {
    console.log(this.wads.window);
    console.log(this.wads.document.doctype);
  }
}

My questions are:

Is this the optimal way to provide window and  document?
Can this be written more concisely? I find it kind of odd, that one variable is injected and the other is pulled from a function call.

It's a given that the app runs in the browser.

Assuming you want a SOLID code and keep the single responsibility principle, you would need to inject window and document separately.
A clean way is to provide each of them using the useValue property of your provider:

@NgModule({
  declarations: [...],
  imports: [...],
  providers: [
   { provide: "windowObject", useValue: window}
  ]
})

as already answered on SO:
same stuff for the document provider.


PHP OOP registration with User class and singleton Database class I created registration system with PHP. I have User class that will handle all the input and insert the user input into database, and i created Database class with Singleton pattern that will connect to database. After user submited his data, new User object is created.

This is my Database class with singleton patter:

class Database {
    private static $instance = null;
    private $conn;

    private function __construct() {
        $dsn = "mysql:host=" . DB_HOST . ";dbname=" . DB_NAME;
        $this->conn = new PDO($dsn, DB_USER, DB_PASS);
    }
    private function __clone() {
        return false;
    }
    private function __wakeup() {
        return false;
    }
    public static function getInstance() {
        if(!self::$instance) {
            self::$instance = new Database();
        }
        return self::$instance;
    }
    public function getConnection() {
        return $this->conn;
    }
}

And this is my User class:

class User {

    public $errors = array();
    protected $username;
    protected $pw1;
    protected $pw2;
    protected $mail;
    private $db;
    private $conn;

    public function __construct() {
        $this->db = Database::getInstance();
        $this->conn = $this->db->getConnection();
    }
    }

I didn't copied rest of the User class code, because my question is: Is this a good way to create singleton pattern for db connection, and a good way to use it in other classes?
I'm fairly new to PHP, and i understand good amount of writing the PHP code, but what i lack is practical knowledge, what are common practices and how to structure the code.

For reasons laid out in this stackoverflow question  the singleton design pattern is not good match for PHP!

Clone Prevention

The advice from the accepted answer to the above stackoverflow question gives is to stop callers from cloning your object by adding a magic method like so:

public function __clone() {
    throw new Exception("Can't clone a singleton");
}

Your code will return false. false can be ignored / overlooked by programmers quite easily so I would stick to throwing an exception which is more explicit!

The Database Class

According to the php manual

  The intended use of __wakeup() is to reestablish any database
  connections that may have been lost during serialization and perform
  other reinitialization tasks.

Seeing as your class doesn't do that I can't see the value in the __wakeup method at all. There is a quote that is something along the lines of "don't write code you don't need now, because you won't in the future".

Chaining methods

As your getInstance method just returns an instance of the Database class and the method getConnection is public you can chain the calls like so:

$this->db = Database::getInstance()->getConnection();

PDO Exceptions

Make sure when setting up your PDO error mode to throw exceptions; this will prevent instances of trying to chain functions based on objects that fail to setup correctly.

Conclusion

If its not impractical too I would recommend (based on personal biases) that you drop the singleton pattern and move towards dependency injection simply because its easier to test and easier to get your head around!


Calculate Work Week Hours by Shift (stored as dict) I am crazy about needing to calculate my work shifts for my part-time job while attending University.  This is because I cannot work more than 20 hours a week.

  Yes, this code is crap, I wrote it in 20 minutes... my brain operates kinda like a pachinko machine, and whatever it writes for stupidly annoying scripts like this it just writes, screw quality.  Don't ding me for that, please, I just haven't had enough coffee or sleep lately to write better code.

So, I wrote a Python script that lets me do one of two things:

Process my 'normal' work schedule, which is hardcoded as the 'default' schedule
Process the first argument (which should be a dict containing the name of the day of the week, and contain a list of lists which contain the start and end time for each shift, using 24hr time format), passed into the program at runtime as an argument.

Regardless of these cases, it will always return something like:

Total Weekly Hours: 15.0

(as an example, using the 'default' hardcoded schedule).

When executing as a shell command, or with the python executable, you have to put the "schedule" dict in quotes.  This is an example of execution of the file and passing in a schedule where I have to take on additional hours (on the command line, so this would be executed verbatim):

./workhours.py "{'Monday': [['09:00', '13:00']], 'Tuesday': [['09:00', '10:30'], ['17:00', '19:00']], 'Wednesday': [['09:00', '11:00']], 'Thursday': [['13:00', '15:00']], 'Friday': [['10:00', '17:00']]}"

As long as the first argument is an entire dict, as a string so it's parsed right by the application, it seems to work fine, and gives me correct values (for example, the last example would return a value of 18.5 hours which is accurate).

While this works, I'd like suggestions for how I could improve this.  It's a quickly-thrown-together script that does what I want, but suggestions for improvement are definitely accepted.

This is the code:

workhours.py:

#!/usr/bin/python
import sys
import os
from ast import literal_eval
from datetime import datetime, timedelta

_TIME_FORMAT = '%H:%M'

def set_timeformat(self, formatstr=_TIME_FORMAT):
    self._TIME_FORMAT = formatstr

_DEFAULT_SCHEDULE = {
    'Sunday': None,
    'Monday': [['09:00', '13:00']],
    'Tuesday': None,
    'Wednesday': [['09:00', '11:00']],
    'Thursday': [['13:00', '15:00']],
    'Friday': [['10:00', '17:00']],
    'Saturday': None
}

def _calc_shift_hours(shift):
    tdelta = datetime.strptime(shift[1], _TIME_FORMAT) - datetime.strptime(shift[0], _TIME_FORMAT)

    if tdelta.days < 0:
        tdelta = timedelta(days=0, seconds=tdelta.seconds, microseconds=tdelta.microseconds)

    return tdelta.seconds / 3600.0

def _calc_workhours(sched=_DEFAULT_SCHEDULE):
    hours = {
        'Sunday': 0,
        'Monday': 0,
        'Tuesday': 0,
        'Wednesday': 0,
        'Thursday': 0,
        'Friday': 0,
        'Saturday': 0
    }

    totalhours = 0

    for day in sched.iterkeys():
        if sched[day] is None:
            pass
        else:
            # noinspection PyTypeChecker
            for shift in sched[day]:
                hours[day] += _calc_shift_hours(shift)
            totalhours += hours[day]

    os.system('clear')
    print "Total Weekly Hours: %s" % totalhours

if __name__ == '__main__':
    try:
        dictarg = literal_eval(sys.argv[1])
        if isinstance(dictarg, dict):
            schedule = dictarg
        else:
            schedule = _DEFAULT_SCHEDULE
    except IndexError:
        schedule = _DEFAULT_SCHEDULE

    _calc_workhours(schedule)

I would improve the way you calculate total hours - you don't actually need to keep track of how much hours per day of a week you can work and do the calculations in one go on the "schedule" object with the sum() built-in function:

def _calc_workhours(sched=_DEFAULT_SCHEDULE):
    """Returns total work hours from a schedule."""
    return sum(_calc_shift_hours(shift)
               for shifts in sched.values() if shifts
               for shift in shifts)

Note that, to define the "scope" of a function more clearly and set the clear boundaries, it returns work hours instead of printing it and executing an os.system() call (which I consider a side effect). Then, to print the result, edit the main block of the program and replace:

_calc_workhours(schedule)

with:

total_hours = _calc_workhours(schedule)
os.system('cls||clear')
print("Total Weekly Hours: %s" % total_hours)

Other ideas:

use argparse module instead of reading from sys.argv directly - it will be cleaner overall, you would have a simple and clear way to define a "--help" mode for your command-line program. Would be easier to set the default value for the schedule
instead of parsing the schedule with literal_eval() from the command-line consider accepting a JSON file with your schedule object which you would load with json.load()
in any case, reading and parsing the schedule should also be extracted into a separate function
we can also refactor _calc_shift_hours() a bit and instead of accepting the shift list, accept two arguments, shift_start and shift_end, a bit more explicit and cleaner:

def _calc_shift_hours(shift_start, shift_end):
    """Returns a number of hours per shift."""
    tdelta = datetime.strptime(shift_end, _TIME_FORMAT) - datetime.strptime(shift_start, _TIME_FORMAT)
    # ...

def _calc_workhours(sched=_DEFAULT_SCHEDULE):
    """Returns total work hours from a schedule."""
    return sum(_calc_shift_hours(shift_start, shift_end)
               for shifts in sched.values() if shifts
               for shift_start, shift_end in shifts)

print() function vs print statement, .values() vs itervalues() for Python 3 compatibility
missing docstrings (I've added them in the snippets above - they still can/should be more detailed)
the way you set the default schedule at the moment can be improved so that, if a default schedule is used, you know about it, something like:

try:
    dictarg = literal_eval(sys.argv[1])
    if isinstance(dictarg, dict):
        schedule = dictarg
    else:
        print("Invalid schedule object provided. Using the default schedule.")
        schedule = _DEFAULT_SCHEDULE
except IndexError:
    print("No schedule provided. Using the default schedule.")
    schedule = _DEFAULT_SCHEDULE

if literal_eval() cannot evaluate a string - there will be ValueError thrown - currently it is not handled properly. This again, can be beautifully solved by argparse, or/and if you switch to having schedule in JSON


Implementation of the atof() function I am looking for feedback on coding style. I know this function already exists, and I would never use my version over a well tested one. I am just practicing.

double Clib_atof(char s[])
{
    double val, power, rtn;
    int i, sign;
    for (i = 0; isspace(s[i]); i++);
    sign = (s[i] == '-') ? -1 : 1;
    if (s[i] == '+' || s[i] == '-') ++i;
    for (val = 0.0; isdigit(s[i]); ++i) {
        val = 10.0 * val + (s[i] - '0');
    }
    if (s[i] == '.') {
        ++i;
    }
    for (power = 1.0; isdigit(s[i]); ++i) {
        val = 10.0 * val + (s[i] - '0');
        power *= 10.0;
    }
    rtn = (sign * val / (power));

    // Next work on exponent
    if (s[i] == 'e') {
        int j, esign;
        int eval = 0;
        fprintf(stdout, "e found\n");
        for (j = i + 1; isspace(s[j]); ++j);
        esign = (s[j] == '-') ? -1 : 1;
        if (s[j] == '+' || s[j] == '-') ++j;
        for (; isdigit(s[j]); ++j) {
            eval = 10 * eval + (s[j] - '0');
        }
        fprintf(stdout, "eval = %d\n", eval);
        int l;
        for (l = 0; l < eval; l++) {
            (esign >= 0) ? (rtn *= 10) : (rtn /= 10);
        }
    }

    // Finally return the solution
    return rtn;
}

double Clib_atof(char s[])
{
    double val, power, rtn;
    int i, sign;
    for (i = 0; isspace(s[i]); i++);

Looks too much like the ; was an accident. I suggest using {/\*empty\*/} instead to make it clear you did it on purpose. Or I might write it as a while loop.

    sign = (s[i] == '-') ? -1 : 1;
    if (s[i] == '+' || s[i] == '-') ++i;
    for (val = 0.0; isdigit(s[i]); ++i) {
        val = 10.0 * val + (s[i] - '0');
    }

I dislike the use of a for loop here. The initializer condition doesn't really have any to do with the loop control. Repeating the loop until some condition becomes true feels like a while loop. With a for loop I think of iterating or counting not testing.

    if (s[i] == '.') {
        ++i;
    }
    for (power = 1.0; isdigit(s[i]); ++i) {
        val = 10.0 * val + (s[i] - '0');
        power *= 10.0;
    }

    rtn = (sign * val / (power));

I wouldn't use abbreviations like rtn and val. They make the code harder to read. I don't think any of those parens are necessary.

    // Next work on exponent
    if (s[i] == 'e') {
        int j, esign;
        int eval = 0;

I look at this and think evaluate, but I don't think that is what you meant.

        fprintf(stdout, "e found\n");
        for (j = i + 1; isspace(s[j]); ++j);

Why would you allow space here? Why j?  Why didn't you stick with i?

        esign = (s[j] == '-') ? -1 : 1;
        if (s[j] == '+' || s[j] == '-') ++j;
        for (; isdigit(s[j]); ++j) {
            eval = 10 * eval + (s[j] - '0');
        }

I note that this is pretty much the same as a previous block of code. Consider extracting the common bits into a function:

        fprintf(stdout, "eval = %d\n", eval);
        int l;
        for (l = 0; l < eval; l++) {
            (esign >= 0) ? (rtn *= 10) : (rtn /= 10);
        }

I suspect using a pow() function would be more fruitful.

    }

    // Finally return the solution
    return rtn;
}


Maximum contiguous subarray with recursion I've implemented the algorithm below for the maximum contiguous subarray problem and would like a review on three specific things:

Making the code shorter
Making the code faster
Any other algorithms that can do the job with lower complexity

def crossingsubarray(A, low, mid, high):

    negetiveinfinity = -10000000000
    summ = 0
    for i in range(mid, low - 1, -1):
        summ = summ + A[i]
        if summ > negetiveinfinity:
            negetiveinfinity = summ
            leftindex = i
    left = negetiveinfinity

    negetiveinfinity = -10000000000
    summ = 0

    for j in range(mid+1, high+1):
        summ = summ + A[j]
        if summ > negetiveinfinity:
            negetiveinfinity = summ
            rightindex = j
    right = negetiveinfinity

    return(leftindex, rightindex, left + right)

def findmaxarray(alist, low, high):

    if high == low:
        return low, high, alist[low]

    else:

        mid = (low+high)/2

        leftlow, lefthigh, leftsum = findmaxarray(alist, low, mid)
        rightlow, righthigh, rightsum = findmaxarray(alist, mid + 1, high)
        crosslow, crosshigh, crosssum = crossingsubarray(alist, low, mid, high)

        if leftsum >= rightsum and leftsum >= crosssum:
            return leftlow, lefthigh, leftsum
        elif rightsum >= leftsum and rightsum >= crosssum:
            return rightlow, righthigh, rightsum
        else:
            return crosslow, crosshigh, crosssum

B = [-7, -2, 5, 4, -1, 100, 10]

L,H,maxi = findmaxarray(B, 0, 6)

print(L)
print(H)
print(maxi)

Just a quick explanation:

The first function, crossingsubarray, returns the maximum value of a subarray (along with its low and high indices with respect to A) such that the subarray crosses the provided midpoint.

The second function, findmaxarray, is a divide-and-conquer task which recursively calls the first function such that the maximum contiguous subarray sum is found.

Please let me know if I could make any improvements in the aforementioned areas.

In this loop:

negetiveinfinity = -10000000000
summ = 0
for i in range(mid, low - 1, -1):
    summ = summ + A[i]
    if summ > negetiveinfinity:
        negetiveinfinity = summ
        leftindex = i
left = negetiveinfinity

First, 'negetiveinfinity' isn't a good variable name - it should be 'negative', for a start. More importantly, it doesn't reflect how you're using it - it "negative infinity" would be a number that always tests lower than any other number, but you're using it as the highest contiguous sum you've found so far. Similarly, you're using summ (another misspelling, although presumably this one is to avoid shadowing the builtin sum) as a trial total that you test to see if it is better than the stored one. Better names might be max_sum and trial_sum.

Then once you've found that, you reset those variables and reuse them in almost exactly the same loop on the other half of the list. Both of these loops also have a possible logic error: you start the trial sum at a 'sufficiently small' value. That can be problematic if it isn't small enough. Instead, it would be more usual to start it at the 'mid' value.

But the ideal thing to do here is to fix that error both times by factoring out the repeated code. You can do this really easily with a bit of analytic clarity of what your problem is: you're looking for the the maximum cumulative sum of the elements in a sequence. That immediately suggests using itertools.accumulate, like this:

left_half = it.accumulate(A[low-1:mid:-1])
right_half = it.accumulate(A[mid:high+1])
left = max(left_half, key=lambda x: x[1])
right = max(right_half, key=lambda x: x[1])
return (mid - left[0], mid + right[0], left[1] + right[1])

And that whole function is now five lines.

You can use do something similar here:

leftlow, lefthigh, leftsum = findmaxarray(alist, low, mid)
rightlow, righthigh, rightsum = findmaxarray(alist, mid + 1, high)
crosslow, crosshigh, crosssum = crossingsubarray(alist, low, mid, high)

if leftsum >= rightsum and leftsum >= crosssum:
    return leftlow, lefthigh, leftsum
elif rightsum >= leftsum and rightsum >= crosssum:
    return rightlow, righthigh, rightsum
else:
    return crosslow, crosshigh, crosssum

You never use *low and *high separately, and you only use *sum to compare the three sets. So instead of using nine variables, use a single list of tuples and a single call to max:

candidates = [findmaxarray(alist, low, mid),
              findmaxarray(alist, mid + 1, high),
              crossingsubarray(alist, low, mid, high)]

return max(candidates, key=lambda x: x[2])

You appear to be using Python 2. In Python 3.x, this line:

mid = (low+high)/2

will actually cause an error further along your code. Division of two integers now returns a float, so that eg, 5/2 = 2.5 (instead of 2). Use floor division to guarantee an integer result:

mid = (low+high) // 2

If you can't upgrade to Python 3, I highly recommend at least putting yourself in as close-to-future proof environment as possible. Include this line:

from __future__ import division

at the top of your file to back port this particular behavior.

Slicing the array into left_half and right_half does start creating copies that you have otherwise avoided by passing low and high around. For the right half, you could not copy it by using it.islice. But that won't work for the left half, because islice doesn't support using a negative step. If this is a problem, you may want to consider using numpy - slicing numpy arrays doesn't create copies.

For mutual consistency, and to better describe what the 'crossing' one does, rename your two functions to max_crossing_subarray and max_subarray. The usual written rule seems to be that functions should be named with verb phrases, but in practice there are some exceptions to this - in my experience, for functions that would be named find_blah dropping the find_ seems to be preferred.

In terms of overall complexity, this previous question implements a C version of what appears to be the same algorithm as yours and claims to be O(n log n). The accepted answer points to Kadane's algorithm, a non-recursive O(n) solution. The Wikipedia page provides a Python implementation that only returns the actual sum, but claims that it can be modified to return the start and end indices as well.


Looking for a way to create a particular matrix in python in a less amount of time I want to create a matrix like this in Python:
$$
\begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3\\
0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}
$$

I have written a code that works, but takes a long time to execute:

row = 3000
col = 4000

row_1 = np.asarray((col)*[0])
for i in range(1,row):
    row_1 = np.append(row_1, np.asarray((col)*[i]))
row_2 = np.asarray(row*[x for x in range(0,col)])
row_3 = np.asarray(col*(row)*[1])

output = np.vstack([row_1,row_2,row_3])

It takes between 55 to 65 seconds to run this code. Is it possible to create the same matrix in a way that is more efficient?

The NumPy Reference should be the first place you look when you have a problem like this. The operations you need are nearly always in there somewhere. And functions that you find while browsing the reference are sure to come in useful later in your NumPy career.

For the first row, you could use numpy.arange and numpy.repeat:

>>> np.repeat(np.arange(4), 4)
array([0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3])

For the second row, you could use numpy.tile:

>>> np.tile(np.arange(4), 4)
array([0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3])

For the third row, you could use numpy.ones:

>>> np.ones(4 * 4, dtype=int)
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

Putting that together (using numpy.ones_like for row3 so that it has the same shape and data type as row2):

row1 = np.repeat(np.arange(row), col)
row2 = np.tile(np.arange(col), row)
row3 = np.ones_like(row2)
output = np.vstack([row1, row2, row3])

This is about 100 times as fast as the code in the post.

But you can do better than that! There is a hint in the documentation for numpy.tile:

  Note: Although tile may be used for broadcasting, it is strongly recommended to use numpy’s broadcasting operations and functions.

Broadcasting is the way that NumPy adapts the inputs to an operation so that they match in shape. Using this we can write the whole function using array indexing and reshaping operations, like this:

output = np.zeros((3, row, col), dtype=int)
output[0] = np.arange(row).reshape(-1, 1)
output[1] = np.arange(col).reshape(1, -1)
output[2] = 1
output = output.reshape(3, -1)

This is about 160 times as fast as that code in the post.

A slightly clearer way to write this is to use numpy.meshgrid to generate the coordinate arrays:

output = np.zeros((3, row, col), dtype=int)
i, j = np.meshgrid(np.arange(row), np.arange(col), indexing='ij', sparse=True)
output[0] = i
output[1] = j
output[2] = 1
output = output.reshape(3, -1)

This isn't any faster than the previous version but the use of numpy.meshgrid gives more of a clue to the reader as to what is happening.

(You might be able to do even better than that. Do you really need to construct the whole matrix? Could you combine broadcasting and numpy.meshgrid to get the results you want instead? I can't answer this since you didn't explain what you are going to use this code for. But maybe you can ask another question showing us more of your program.)


An iterator returning all possible permutations of a list in Java I have this class that iterates over all permutations of an input list:

PermutationIterable.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * This class implements an {@code Iterable} returning all possible permutations
 * of a list.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 14, 2016) :*
 */
public class PermutationIterable<T> implements Iterable<List<T>> {

    final List<T> allElements = new ArrayList<>();

    public PermutationIterable(List<T> allElements) {
        this.allElements.addAll(allElements);
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new PermutationIterator<>(allElements);
    }

    private static final class PermutationIterator<T>
    implements Iterator<List<T>> {

        private List<T> nextPermutation;
        private final List<T> allElements = new ArrayList<>();
        private int[] indices;

        PermutationIterator(List<T> allElements) {
            if (allElements.isEmpty()) {
                nextPermutation = null;
                return;
            }

            this.allElements.addAll(allElements);
            this.indices = new int[allElements.size()];

            for (int i = 0; i < indices.length; ++i) {
                indices[i] = i;
            }

            nextPermutation = new ArrayList<>(this.allElements);
        }

        @Override
        public boolean hasNext() {
            return nextPermutation != null;
        }

        @Override
        public List<T> next() {
            if (nextPermutation == null) {
                throw new NoSuchElementException("No permutations left.");
            }

            List<T> ret = nextPermutation;
            generateNextPermutation();
            return ret;
        }

        private void generateNextPermutation() {
            int i = indices.length - 2;

            while (i >= 0 && indices[i] > indices[i + 1]) {
                --i;
            }

            if (i == -1) {
                // No more new permutations.
                nextPermutation = null;
                return;
            }

            int j = i + 1;
            int min = indices[j];
            int minIndex = j;

            while (j < indices.length) {
                if (indices[i] < indices[j] && indices[j] < min) {
                    min = indices[j];
                    minIndex = j;
                }

                ++j;
            }

            swap(indices, i, minIndex);

            ++i;
            j = indices.length - 1;

            while (i < j) {
                swap(indices, i++, j--);
            }

            loadPermutation();
        }

        private void loadPermutation() {
            List<T> newPermutation = new ArrayList<>(indices.length);

            for (int i : indices) {
                newPermutation.add(allElements.get(i));
            }

            this.nextPermutation = newPermutation;
        }
    }

    private static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    public static void main(final String... args) {
        List<String> alphabet = Arrays.asList("A", "B", "C", "D");
        int row = 1;

        for (List<String> permutation : new PermutationIterable<>(alphabet)) {
            System.out.printf("%2d: %s\n", row++, permutation);
        }
    }
}

What can I improve here? Please, tell me anything that comes to mind.

Your solution looks good. It's a really challenging task. This is because you have to "flatten" an algorithm with recursive nature. Furthermore you have to break it apart into single steps and to be able to resume at the last step made.

So there are little things that I would change:

I like separated classes instead of inner classes they are more handy in testing
I would have separated the algorithm in "generateNextPermutation()" in an additional class.
I would follow the recursive nature of the problem and build a recursive structure. This is a slightly different approach.
I do not exactly know how the algorithm should behave if you provide an empty list. I assume that you will have one permutation as result. So I adapted your algorithm to work with an empty array of indices.

You see that our solutions do not differ in structure. Only the algorithm to generate a new permutation is extracted in a class and reformulated.

I unpacked this riddle (I somehow liked this riddle) and I want to provide a solution that can use either your algorithm or mine. But finally they converged against the same interface. I expected that as I know there is only one structure that fits the problem best. We may not have found it but both solutions have a "meeting" where the structure is mostly the same AND the things that may be different can work under the same abstraction. Sure, most structure was provided by the interfaces "Iterable" and "Iterator" but I found it interesting how the algorithms are interchangeable.

So first of all the interface for our algorithms:

public interface PermutationResolver<T> {

    List<T> resolvePermutation(List<T> base);

    boolean nextStep();

}

Your algorithm:

public class IndicesWalker<T> implements PermutationResolver<T> {

    private int[] indices;

    public IndicesWalker(int elements) {
        indices = new int[elements];
        for (int i = 0; i < indices.length; ++i) {
            indices[i] = i;
        }
    }

    @Override
    public boolean nextStep() {

        if (indices.length == 0) return false;

        int i = indices.length - 2;

        while (i >= 0 && indices[i] > indices[i + 1]) {
            --i;
        }

        if (i == -1) {
            // No more new permutations.
            return false;
        }

        int j = i + 1;
        int min = indices[j];
        int minIndex = j;

        while (j < indices.length) {
            if (indices[i] < indices[j] && indices[j] < min) {
                min = indices[j];
                minIndex = j;
            }

            ++j;
        }

        swap(indices, i, minIndex);

        ++i;
        j = indices.length - 1;

        while (i < j) {
            swap(indices, i++, j--);
        }
        return true;
    }

    @Override
    public List<T> resolvePermutation(List<T> base) {

        List<T> newPermutation = new ArrayList<>(indices.length);

        for (int i : indices) {
            newPermutation.add(base.get(i));
        }

        return newPermutation;
    }

    private void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

}

Mine:

public class RecursiveCounter<T> implements PermutationResolver<T> {

    private int i;
    private int max;
    private RecursiveCounter<T> nextState;

    public RecursiveCounter(int max) {
        this.max = max;
        this.i = 0;
        if (this.max > 1) {
            nextState = new RecursiveCounter<T>(max - 1);
        }
    }

    @Override
    public boolean nextStep() {

        boolean wasIncremented = true;

        if (nextState != null) {
            if (!nextState.nextStep()) {
                if (this.i == this.max - 1) {
                    this.i = 0;
                    wasIncremented = false;
                } else {
                    i++;
                }
            }
        } else {
            wasIncremented = false;
        }

        return wasIncremented;
    }

    private int getI(int level) {
        if (level == 0) {
            return this.i;
        } else {
            return nextState.getI(level - 1);
        }
    }

    @Override
    public List<T> resolvePermutation(List<T> base) {
        List<T> result = new ArrayList<>();
        List<T> work = new ArrayList<>(base);
        for(int i = 0; i < base.size(); i++) {
            result.add(work.remove(getI(i)));
        }
        return result;
    }

}

The iterator:

public class PermutationIterator<T> implements Iterator<List<T>>  {

    private List<T> base;

    private PermutationResolver<T> permutationResolver;
    private List<T> next;

    public PermutationIterator(List<T> base, PermutationResolver<T> resolver) {
        this.base = base;
        this.next = new ArrayList<>(base);
        this.permutationResolver = resolver;
    }

    private List<T> generateNextPermutation(boolean isLast) {

        List<T> result = null;

        if (!isLast) {
            result = getPermutationResolver().resolvePermutation(base);
        }

        return result;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }

    @Override
    public List<T> next() {

        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        List<T> current = next;

        this.next = generateNextPermutation(!getPermutationResolver().nextStep());

        return current;
    }

    private PermutationResolver<T> getPermutationResolver() {
        return permutationResolver;
    }

}

The iterable:

public class PermutationIterable<T> implements Iterable<List<T>> {

    private List<T> base;
    private PermutationResolver<T> resolver;

    public PermutationIterable(List<T> base, PermutationResolver<T> resolver) {
        super();
        this.base = base;
        this.resolver = resolver;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new PermutationIterator<T>(base, resolver);
    }

}

Code in action with both algorithms:

public class Main {

    public static void main(String[] args) {

        List<String> base = Arrays.asList();

        PermutationIterable<String> permutationIterable1 = new PermutationIterable<String>(base, new IndicesWalker<String>(base.size()));

        for (List<String> permutation : permutationIterable1) {
            System.out.println(permutation);
        }

        PermutationIterable<String> permutationIterable2 = new PermutationIterable<String>(base, new RecursiveCounter<String>(base.size()));

        for (List<String> permutation : permutationIterable2) {
            System.out.println(permutation);
        }

    }

}


Javascript wrap text with conditions I have to wrap my text, when it's longer then 16 characters and when there is space " " or a dash "-". Can I write it with regex or a function that is easier to read than mine below?

wrapType(str) {
        if (str.length > 16) {
            var p = 16;
            while (p > 0 && (str[p] !== " " && str[p] !== "-")) {
                p--;
            }
            if (p > 0) {
                var left = (str.substring(p, p + 1) === "-") ? str.substring(0, p + 1) : str.substring(0, p);
                var right = str.substring(p + 1);
                return left + "\n" + this.wrapType(right);
            }
        }
        return str;
}

Some minor changes to improve readability:

It's generally considered better practice to use str.charAt(0) instead of str[0] (even though str[0] often outperforms .charAt()).
Simplify the while condition and have it only check if p > 0; the character checks can be done inside the loop. This also lets you eliminate the if (p > 0) check.
Add some comments.

You could also incorporate p-- into your while loop (so it would read while (p-- > 0) { but that wouldn't improve readability.

wrapType(str) {
        if (str.length > 16) {
            // if string is longer than 16 characters
            var p = 16;
            while (p > 0) {
                // loop through the string and check each char
                if ((str.charAt(p) === " " || str.charAt(p) === "-") {
                    // if a dash or space is found, wrap the string
                    var left = (str.charAt(p) === "-") ? str.substring(0, p + 1) : str.substring(0, p);
                    var right = str.substring(p + 1);
                    return left + "\n" + this.wrapType(right);    // return the wrapped string
                }
                p--;
            }
        }
        return str;    // return the original string
}

If you wanted to take it further, you could create a small function to do the character-checking called breakHere or something similar that would return true if it found a dash or space, and false otherwise.  Then for your if checks, instead of checking for both the dash and space, you could just do something like if (breakHere()) { ... } which would make for slightly longer code but might make it easier for someone new to follow what's going on.  You could even have that function return the value itself, so you could call newStr = breakHere(); and newStr would either be assigned the wrapped string (if a dash or space was found) or the original string (str).  That would allow you to combine your two separate return statements into one -- return newStr.


Implementing numerical integration I have this C++ code that implements a rectangular numerical integration.  It evaluates the \$K\$-dimensional integral

$$\int_{u_K = 0}^{\gamma}\int_{u_{K-1} = 0}^{\gamma-u_K}\cdots\int_{u_2}^{\gamma-u_K-\cdots-u_3}F_U(\gamma-\sum_{k=2}^Ku_k)f_U(u_2)\cdots f_U(u_K)\,du_2\cdots du_K$$
where \$F_U\$ is the cdf and \$f_U\$ is the pdf.

#include <iostream>
#include <cmath>
using namespace std;

float pdf(float u){
     return (1/(pow(1+u, 2)));
}

float cdf(float u){
      return (1 - 1/(u+1));
}
// The main function that implements the numerical integration,
//and it is a recursive function
float integ(float h, int k, float du){
      float res = 0;
      if (k == 1){
         res =  cdf(h);
      }else{
         float u = 0;
      while (u < h){
         res += integ(h - u, k - 1, du)*pdf(u)*du;
         u += du;
     }
}
     return res;
}

int main(){
    float du = 0.0001;
    int K = 3;
    float gamma[4] = {0.31622777, 0.79432823,
                1.99526231, 5.01187234};
    int G = 50;
    int Q = 2;
    for (int i = 0; i < 4; i++){
        if ((G-Q*(K-1)) > 0){
            float gammath = (gamma[i]/Q)*(G-Q*(K-1));
            cout<<1-integ(gammath, K, du)<< endl;
    }

 }

    return 0;
}

I am facing a speed problem, although I switched to C++ from Python and MATLAB, because C++ is faster. The problem is that I need a small step size du to get an  accurate evaluation of the integration.

Basically, I want to evaluate the integral at 4 different points defined by gammath, which is a function of other defined parameters.

Is there anyway I can speed up this program? I already have 25x+ speed factor over the same code in Python, but still the code takes too long (I ran it all night, and it wasn't finished in the morning). And this is only for K=3, and G=50. In other cases I want to test K = 10, and G = 100 or 300.

I see a few things that may help you improve your program.

Avoid pow for float

The use of pow converts the argument to a double and returns a double.  If you're casting the result to a float anyway, the use of std::powf would be more appropriate.  But see the next suggestion for an even better approach.

Prefer multiplication to pow with small, fixed integral powers

The content of the pdf function could be rewritten like this instead:

 return 1.0f/((u+1)*(u+1));

Usealittlemorewhitespace

With everything crowded together on the line, it's hard to read and understand some lines like this:

float gammath = (gamma[i]/Q)*(G-Q*(K-1));

I'd write it like this instead:

float gammath{gamma[i] / Q) * (G - Q * (K - 1)};

This also uses the C++11 uniform initialization syntax, which I prefer.

Use constexpr where appropriate

Any time you can make a numerical constant or expression constexpr is one more opportunity for compiler optimization.  In this case, virtually everything in main, including du, K, gamma, G, and Q can be made constexpr simply by adding that keyword in front of the declaration.  With that, the compiler is free to evaluate expressions like this:

G - Q * (K - 1)

once at compile-time rather than at runtime.  It can save quite a bit of time if you use it.

Move invariants out of the loop

The value of the expression listed above does not change within the loop (or within the program at all, as presented).  Smart compilers can usually optimize that by themselves, but doing it manually may give you insight.  For example, we can make a constant of that expression outside the loop:

constexpr auto m{G - Q * (K - 1)};

Now the inner if boils down to if (m > 0) but since it's invariant within the loop, move it outside.  Now we have the encapsulating if outside and the for loop inside which makes a lot more sense.

Use C++11 threading features

The calculations for each value of gamma are completely independent.  For that reason, they could easily be calculated in parallel.  Here's a way to do that:

int main() {
    constexpr float du = 0.0001;
    constexpr int K = 3;
    constexpr float gamma[4] = {0.31622777, 0.79432823, 1.99526231, 5.01187234};
    constexpr int G = 50;
    constexpr int Q = 2;
    constexpr auto m{G - Q * (K - 1)};
    std::vector<std::future<float>> chunks;
    if (m > 0) {
        for (int i = 0; i < 4; i++) {
            float gammath{gamma[i] / Q * m};
            chunks.push_back(std::async(integ, gammath, K, du));
        }
    }
    std::mutex cout_mutex;
    for (int i=0; i < 4; ++i) {
        std::lock_guard<std::mutex> lock(cout_mutex);
        std::cout << gamma[i] << '\t' << 1 - chunks[i].get() << '\n';
    }
}

This requires <future>, <mutex>, and <vector> as #includes.

Parallelize the recursive integrals

If there are 100,000 steps in the integral, why do that with a single core?  If you have a multicore machine like I do, you could divide that work among multiple cores by using the same kind of std::async technique shown above.  This would dramatically speed the results (and can be divided among as many cores as you have).  I did not implement that, but the code above should give a hint as to how to do such a thing generically.

Use static for functions which can have file scope

If the pdf, cdf and integ functions are never used outside the file in which they're defined, the compiler can get quite clever about inlining code and other optimizations.  For that reason, I'd recommend making those functions static if at all possible.

Results

I didn't have the patience to run this at the du value in the program (0.0001) so I ran it at 50 times that at 0.005 to speed up testing.  Obviously, that's an option if you can accept the lower resolution, but I just did it to speed up timing tests.

The original (with the modified value of du) took 1.06 seconds, while the modified version took 0.723s.  At full resolution (du = 0.0001) the results took 30 minutes and 3 seconds on the same 64-bit 8-core Linux machine.


Get total count of object's elements and all children objects` elements I have a table, Taxonomy, with data that looks something like the following:

TaxID | ParentID | Name
-----------------------------------
1     | NULL     | Animal
2     | 1        | Cat
3     | 1        | Dog
4     | 1        | Fish
5     | 3        | Poodle
6     | 3        | Golden Retriever
7     | 4        | Goldfish

I then have a second table, Table2, that has records that reference the TaxIDs in Taxonomy. I've labeled the foreign key column referencing Taxonomy, FK_TaxID.

FK_TaxID | Field2
------------------
1        | value
1        | value
1        | value
2        | value
2        | value
2        | value
3        | value

The resulting hierarchy looks something like the following:

- Parent (TaxID=1; #elements=15)
  - Child (TaxID=2; #elements=3)
  - Child (TaxID=3; #elements=8)
    - GrandChild (TaxID=6; #elements=2)
    - GrandChild (TaxID=5; #elements=0)
  - Child (TaxID=4; #elements=5)
    - GrandChild (TaxID=7; #elements=10)

The #elements is based on how many times the TaxID appears in Table2.

I have a method that takes in a Taxonomy ID, and returns the total element count for the record and its sub-children.

For example:

If ID = 1, count should = 43.
If ID = 3, count should = 10.
If ID = 5, count should = 0.

Here is the code I am currently using:

public int GetCount(int ID)
{
    List<int> childrenIDs = DbContext.Taxonomy
        .Where(x => x.ParentID == ID)
        .Select(x => x.TaxID)
        .ToList();

    List<int> grandchildrenIDs = DbContext.Taxonomy
        .Where(x => childrenIDs.Contains(x.ParentID))
        .Select(x => x.TaxID)
        .ToList();

    int count = DbContext.Table2.Count(x => x.FK_TaxID == ID
        || childrenIDs.Contains(x.FK_TaxID)
        || grandchildrenIDs.Contains(x.FK_TaxID));

    return count;
}

This code gets the count in three steps:

Sets childrenIDs to equal the list of records where the ParentID equals the given ID.
Sets grandchildrenIDs to equal the list of records where childrenIDs contains the ParentID.
Gets the count of Table2 records where the FK_TaxID equals the inputted ID, or childrenIDs contains the FK_TaxID or grandchildrenIDs contains the FK_TaxID.

This method returns the correct results, yet it is quite slow, and seems overly complicated.

How can I simplify this method? Can I somehow get rid or one of the lists and get all the IDs in one call? Is there a more efficient way of doing this than using Contains() twice?

Why do you need to make the .ToList() call instead of keeping the IEnumerable objects returned by Select methods?

    public int GetCount(int ID)
    {
        var childrenIDs = DbContext.Taxonomy
            .Where(x => x.ParentID == ID)
            .Select(x => x.TaxID);
        var grandchildrenIDs = DbContext.Taxonomy
            .Where(x => childrenIDs.Contains(x.ParentID))
            .Select(x => x.TaxID);
        var count = DbContext.Table2.Count(x =>
         x.FK_TaxID == ID ||
         childrenIDs.Contains(x.FK_TaxID) ||
        grandchildrenIDs.Contains(x.FK_TaxID));
        return count;
}

This way, the only call to database is the last one.


Hamiltonian Monte Carlo in Scala I'm writing a program in Scala to perform Hamiltonian Monte Carlo (HMC), coupled with Gibbs sampling of some variables. The algorithm, with the modifications such as perturbing epsilon and l and performing Gibbs updates on some variables may be found in the easily available book chapter "MCMC using Hamiltonian Dynamics" by R Neal. The program works by alternating an HMC update of a set of variables q via the hmcUpdate() method with Gibbs updates of the variables gibbsVar via some unspecified method, then putting the two sets together in a tuple. The hmcRunner() method generates these tuples and prepends them onto a list.

I'm very new to Scala (last Friday) so I would like some feedback on the idiomacity of the code, as well as advice in general on improving readability. I've tried to write this in the form of an abstract class so that myself and my other group members can use this in their own code by supplying the unspecified methods themselves - is this the most appropriate structure to use?

import breeze.linalg._
import breeze.stats.distributions.Uniform
import breeze.stats.distributions.Gaussian
import breeze.stats.distributions.Gamma
import math.log, math.sqrt
import scala.annotation.tailrec

abstract class HMC(ul: Int, ue: Double) {
  val uDev = new Uniform(0.0,1.0)
  val nDev = new Gaussian(0.0,1.0)
  val l = ul
  val ep = ue

  final def metCheck(ho: Double, hn: Double): Boolean = log(uDev.sample()) < ho - hn

  def calcU(q: DenseVector[Double], sigs: List[Double]): Double

  def calcUgrad(q: DenseVector[Double], sigs: List[Double]): DenseVector[Double]

  def gibbsUpdate(q: DenseVector[Double]): List[Double]

  final def hmcUpdate(qo: DenseVector[Double], sigs: List[Double], acc: Int): (DenseVector[Double], Int) = {
    val uep = ep * min(sigs) * min(sigs) * (0.9 + 0.2 * uDev.sample()) // perturb ep, l pm 10% to avoid cyclic orbits
    val ul = (l.toDouble * (0.9 + 0.2 * uDev.sample())).toInt
    val po = DenseVector(nDev.sample(qo.length).toArray)
    val ho = calcU(qo, sigs) + (po dot po) / 2.0
    @tailrec
    def leapFrog(qo: DenseVector[Double], po: DenseVector[Double], ll: Int): (DenseVector[Double], DenseVector[Double]) = {
      if (ll == 1) {
        val qn = qo + (po :* uep)
        val pn = po - (calcUgrad(qn, sigs) :* uep) / 2.0
        (qn, pn)
      }
      else {
        val qn = qo + (po :* uep)
        val pn = po - (calcUgrad(qn, sigs) :* uep)
        leapFrog(qn, pn, ll - 1)
      }
    }

    val (qn, pn) = leapFrog(qo, po - (calcUgrad(qo, sigs) :* uep) / 2.0, ul)
    val hn = calcU(qn, sigs) + (pn dot pn) / 2.0
    if (metCheck(ho,hn)) (qn, acc + 1) else (qo, acc)
  }

  final def stdDevSample(sqmis: Double, n: Int) = sqrt(
    sqmis / (2.0 * Gamma((n.toDouble + 3) / 2.0, 1.0).sample())
    )

  //Pass initial values to rl
  @tailrec
  final def hmcRunner(maxIt: Int, report: Int, iter: Int, acc: Int,
    rl: List[(DenseVector[Double], List[Double])]):
    List[(DenseVector[Double], List[Double])] = {
    if (iter == maxIt) {
      val (qn, accn) = hmcUpdate(rl(0)._1, rl(0)._2, acc)
      val gibbsVar = gibbsUpdate(qn)
      (qn, gibbsVar) :: rl
    }
    else {
      val (qn, accn) = hmcUpdate(rl(0)._1, rl(0)._2, acc)
      val gibbsVar = gibbsUpdate(qn)
      val currU = calcU(qn, gibbsVar)
      if (iter % report == 0) {
        print("\nIteration "); print(iter); print(" of "); println(maxIt)
        print("U: "); println(currU)
        print("Acceptance: "); println(acc.toDouble / iter.toDouble)
      }
      hmcRunner(maxIt, report, iter + 1, accn, (qn, gibbsVar) :: rl)
    }
  }
}

I rewrote parts of your code (see below).  I did not have enough time to complete the refactoring, so it is far from I would really want to see, but at least it is not Fortran anymore.

You can use trait instead of abstract class.  It is more flexible.
The names, pretty much all names, are very uninformative.  Why uDev for a distribution?
You should separate the printing of reports from the actual algorithm (separation of concerns).  This advice applies to all languages, not just Scala.
Avoid using recursion.  It is like the assembly language of functional programming.  Use reduce and such instead.
It looks like you don't know about "string" + " " + "concantetation" or, even better, interpolation: s"Hello, ${name}".
In an if expression, when the code at the start of both if and else is the same, you should pull that code out.
You call min(sigs) twice in a row.  You should set a variable with that value and use it twice.
You can shorten the imports: import math.{log, sqrt}.  You should also explicitly write out all imports instead of doing a bulk import (import breeze.linalg._).  I was confused by where min was coming from.
Terminating a recursive loop on l == 1 looks odd in Scala; it's usually on 0.
I'm usually a big fan of breaking everything in small functions, but metCheck is so important that I think the computation should be left as code where it is called.
Don't pass acc to hmcUpdate.  That function has no business dealing with that accumulator (separation of concern).
The OO/functional design was pretty much inexistent.  I did some, but it is currently very poor due to lack of time.  A good design greatly improves readability.  You should spend some time to properly break everything down in classes.  And then think some more about it and do it, etc.

After some partial refactoring:

  val unifDist = new Uniform(0.0, 1.0)
  val normDist = new Gaussian(0.0, 1.0)

  // Poor names.  I don't know what they are.
  val l = ul
  val ep = ue

  type Position = DenseVector[Double]
  type Momentum = DenseVector[Double]
  case class HamState(q: Position, p: Momentum)

  def leapFrogStep(potentialEnergy: PotentialEnergy, uep: Double)(hamState: HamState): HamState = {
    val q = hamState.q + (hamState.p :* uep)
    val p = hamState.p - (potentialEnergy.calcGradU(hamState.q) :* uep)
    HamState(q, p)
  }

  def leapFrogMomemtumHalfStep(potentialEnergy: PotentialEnergy, uep: Double)(hamState: HamState): HamState = {
    val p = hamState.p - (potentialEnergy.calcGradU(hamState.q) :* uep) / 2.0
    HamState(hamState.q, p)
  }

  trait PotentialEnergy {
    def calcU(q: Position): Double
    def calcGradU(q: Position): DenseVector[Double]
    def computeTotalEnergy(hamState: HamState) = calcU(hamState.q) + (hamState.p dot hamState.p) / 2.0
    // I don't have the slightest idea what uep is...
    // I put it in this class, but it certainly does not belong here.
    def uep(): Double
  }

  case class WhateverSigsIsPotentialEnergy(sigs: List[Double]) extends PotentialEnergy {
    override def calcU(q: Position) = calcU_(q, sigs)
    override def calcGradU(q: Position) = calcUgrad_(q, sigs)
    // uep does not belong here.  It should not access "global" ep or uDev.
    override def uep = ep * min(sigs) * min(sigs) * (0.9 + 0.2 * unifDist.sample()) // perturb ep, l pm 10% to avoid cyclic orbits
  }

  def hmcStep(potentialEnergy: PotentialEnergy)(q: Position): Option[Position] = {
    val uep = potentialEnergy.uep
    val nSteps = (l.toDouble * (0.9 + 0.2 * unifDist.sample())).toInt

    val p = DenseVector(normDist.sample(q.length).toArray)
    val h = potentialEnergy.calcU(q) + (p dot p) / 2.0
    val initState = HamState(q, p)

    def halfStepper = leapFrogMomemtumHalfStep(potentialEnergy, uep)(_)
    def fullStepper = leapFrogStep(potentialEnergy, uep)(_)
    def fullPathTransform = (halfStepper :: List.fill(nSteps - 1)(fullStepper)) :+ halfStepper
    val state = fullPathTransform.foldLeft(initState) { (state, stepper) => stepper(state) }

    val energyChange =
      potentialEnergy.computeTotalEnergy(state) - potentialEnergy.computeTotalEnergy(initState)
    if (unifDist.sample() < math.exp(-energyChange))
      Some(state.q)
    else
      None
  }

  type GibbsSomethings = List[Double]
  case class PositionAndGibbs(pos: Position, gibbs: GibbsSomethings)

  /**
   * @return Boolean true if the generated position is different than the previous one.
   */
  def hmcAndGibbsStep(potentialEnergy: PotentialEnergy)(positionAndGibbs: PositionAndGibbs): (PositionAndGibbs, Boolean) = {
    var posOption = hmcStep(potentialEnergy)(positionAndGibbs.pos)
    var pos = posOption.getOrElse(positionAndGibbs.pos)
    var gibbs = gibbsUpdate(pos)
    (PositionAndGibbs(pos, gibbs), (pos != None))
  }

  def hmcRunner(potentialEnergy: PotentialEnergy)(maxIt: Int, prevState: PositionAndGibbs): List[PositionAndGibbs] = {

    val infiniteStream: Stream[(PositionAndGibbs, Boolean)] = {
      def loop(stateAndBool: (PositionAndGibbs, Boolean)): Stream[(PositionAndGibbs, Boolean)] =
        stateAndBool #:: loop(hmcAndGibbsStep(potentialEnergy)(stateAndBool._1))
      loop((prevState, false))
    }

    val finiteStream = infiniteStream.take(maxIt)

    val visitedStates = finiteStream.foldLeft(List[PositionAndGibbs]()) {
      case (visitedStates, (posAndG, isNew)) =>
        posAndG :: visitedStates
    }
    visitedStates

    // To print some report every "iter" iterations:
    //  1) change the foldLeft above so it also counts the "isNew"
    //  2) instead of calling once ".take(maxIt)", write a function that
    //     only takes "iter" at a time an then prints out some report.
    //     Call that method until the total number of iterations reaches "maxIt".
  }


Avoiding "warning: Use of uninitialized value" when fetching an integer CGI parameter I was using this code to fetch a CGI parameter:

$page = int(param('page'));

This sometimes results in:

warning: Use of uninitialized value in int

Is this a good solution to resolve this warning, or is better and more succinct code available?

if (defined param('page')) {
    $param_page = int(param('page'));
} else {
    $param_page = 1;
}

Standard practice is to scope variables using my.

Since Perl 5.10, the preferred way to write this is to use the logical defined-or operator to provide a default value when undef is encountered.

my $param_page = int(param('page') // 1);


Archaeologist Progression One of the badges available on Stack Exchange is the Archaeologist badge. This is awarded for making 100 edits on posts that had been inactive (at the time of the edit) for 6 months.

There is no indication on your profile, or elsewhere, how close you are to this badge. Here's an SEDE query that can give you a good idea of how close you are to being awarded Archaeologist:

-- Title or text edits on someone else's post
-- that had been idle for 6 or more months prior

with CandidateEdits as (

    -- Edits the user has made to titles/body of some other user's posts.

    select min(ph.Id) as EditId,
           ph.PostId EditPost,
           IsNull(p.ParentId, p.Id) as EditQuestion,
           ph.RevisionGUID as EditGUID,
           ph.CreationDate as EditDate
    from PostHistory as ph
        inner join Posts as p on ph.PostId = p.Id and OwnerUserId != UserId
    where UserId = ##UserId:int##
      and PostHistoryTypeId in (4,5) --Title/Body edits.
      and PostTypeId in (1, 2) -- question/answer
    group by ph.PostId, p.Id, p.ParentId, ph.RevisionGUID, ph.CreationDate

), RelatedPosts as (

    -- Posts that cannot be modified in the 6-month window

    select EditId,
           EditDate,
           EditGUID,
           EditQuestion as RelatedPost
    from CandidateEdits

    UNION

    select EditId,
           EditDate,
           EditGUID,
           Id as RelatedPost
    from CandidateEdits
    inner join Posts on EditQuestion = ParentId
         and PostTypeId = 2

), Inactives as (

    -- Edits that have no activity related posts in the 6 month window.
    -- Use Left join, and have a count of 0

    select EditId,
           count(distinct RevisionGUID) as Invalidations
    from RelatedPosts Left Outer Join PostHistory on
             RelatedPost = PostId
         and CreationDate between DateAdd(mm, -6, EditDate) and EditDate
         and Id < EditId
         and RevisionGUID <> EditGUID
    group by EditId
    having count(distinct RevisionGUID) = 0

), FirstEdit as (

    -- Only one of multiple edits on the same post count toward the badge.

    select ce.EditPost,
           min(i.EditId) as EditId
    from CandidateEdits as ce
      inner join Inactives as i on ce.EditId = i.EditId
    group by ce.EditPost

), Revisions as (

    -- Identify which revision in the system relates to the edit you made.
    -- convert to NVarchar to make concatenation simpler in result.

    select EditID,
           Convert(NVarchar(10), EditPost) as RevPost,
           Convert(NVarchar(10), count(distinct RevisionGUID)) as Revision
    from CandidateEdits inner join PostHistory
      on  PostId = EditPost
      and Id <= EditId
      and PostHistoryTypeId < 10
    group by EditId, EditPost
)

select Rank() over (order by EditDate) as Dig,
       ce.EditPost as [Post Link],
       EditDate,
       'site://revisions/' + RevPost + '/' + Revision
             + '|Revision ' + Revision as Revision
from  CandidateEdits as ce
inner join FirstEdit as i on ce.EditId = i.EditId
inner join Revisions as r on ce.EditId = r.EditId
order by EditDate

The logic for the inactive posts is complicated: A new, or edited answer, or an edit to the question itself, resets the 'inactive' counter. The most recent change to any of the answers, or the question itself, is what is used regardless of whether you are editing the question, or one of its answers.

Edits to the tags do not count, only to the title, or body of the post.

Because you may make multiple edits to the post, we only want to display the one edit that counts, and the revision it belongs to.

All suggestions welcome

A thing of beauty
For such an odd/complicated logic, you certainly have made your code easy to follow along. Your comments are succinct and well used to label the CTEs.
Your CTE names are perfect for the code to read fluidly. The spacing and indentation is both useful and consistent. You certainly know how to write some SQL.

Small nitpick
I feel that the table aliases are not the best, and perhaps not even needed, since the table names on SEDE are not particularly long and they are quite descriptive. i especially gave me pause.
from  CandidateEdits as ce
inner join FirstEdit as i on ce.EditId = i.EditId
inner join Revisions as r on ce.EditId = r.EditId


SQL Data Fetcher for CMS I am creating a CMS for a website, so I've added most of the functions that will fetch data from the database to a separate class. The code doesn't seem to have any bugs(Since I've tested it) but I don't like the way how it's looking, I feel like it can be improved but I don't know how. The other concern I have is whether using object orientation will be in this case better (speed etc) than simple functional way.

    <?php

class getResources{

    private $rowId;
    private $tableName;
    private $rowRes;
    private $limInit, $limEnd;
    private $direction;

    private function sqlFetcher(){

        $selectPosts = "select * from {$this->tableName} where post_id='{$this->rowId}'";

        $run_posts = mysql_query($selectPosts);
        if(!$run){
           die('Could not retreive data: "'.mysql_error().'"');
       }
        $row = mysql_fetch_array($run_posts);

        return $row;
    }

    private function fetchAllData(){
       $query = "SELECT * FROM {$this->tableName} ORDER BY {$this->rowRes} {$this->direction} LIMIT {$this->limInit},{$this->limEnd}";
       $run = mysql_query($query);
       if(!$run){
           die('Could not retreive data: "'.mysql_error().'"');
       }

       return $run;
    }
    /**************sqlFetcher Getters****************/
    function getContent($rowId, $tableName){
        $this->rowId = $rowId;
        $this->tableName = $tableName;

        $post_content = $this->sqlFetcher();

        return $post_content['post_content'];
    }

    function getTitle($rowId, $tableName){
        $this->rowId = $rowId;
        $this->tableName = $tableName;

        $post_title = $this->sqlFetcher();

        return $post_title['post_title'];
    }

    function getAuthor($rowId, $tableName){
        $this->rowId = $rowId;
        $this->tableName = $tableName;

        $post_author = $this->sqlFetcher();

        return $post_author['post_author'];
    }

    function getKeywords($rowId, $tableName){
        $this->rowId = $rowId;
        $this->tableName = $tableName;

        $post_keywords = $this->sqlFetcher();

        return $post_keywords['post_keywords'];
    }

    function getPicture($rowId, $tableName){
        $this->rowId = $rowId;
        $this->tableName = $tableName;

        $post_picture = $this->sqlFetcher();

        return $post_picture['post_picture'];
    }

    function getDate($rowId, $tableName){
        $this->rowId = $rowId;
        $this->tableName = $tableName;

        $post_date = $this->sqlFetcher();

        return $post_date['post_date'];
    }

    /*****************fetchAllData Getter********************/

    function getFetchedData($tb, $rR, $lI, $lE, $direction="ASC"){
        $this->tableName = $tb;
        $this->rowRes = $rR;
        $this->limInit = $lI;
        $this->limEnd = $lE;
        $this->direction = $direction;

        $row1 = $this->fetchAllData();

        return $row1;
    }

}

?>

Naming

Variable names should make it very clear what a variable does. One or two letter variables generally don't do that. tb, rR, lI, `lE are all very unclear names.
Do not shorten words in variables if possible. eg limInit, limEnd, rowRes.
Be consistent with your variable names. Either use camelCase or under_score.
your function names are sometimes unclear. What does sqlFetcher fetch that isn't fetched by fetchAllData? Does fetchAllData actually fetch all data? etc.
getResources isn't a very good class name (What is a getResources? ResourceGetter would be semantically better, but still not express what it does very well). Also, what resources? It looks like posts, because post_id is hardcoded (which is odd, since the table name isn't).

SQL

is there a reason for the different getSomething functions? Because it doesn't seem likely that only the title or only the author is needed very often. And a user of this class might think that these are simple getter (as the name implies), while in reality they perform costly database accesses. I would get rid of all of these and return the complete row, ideally wrapped in an object.
Be consistent with your SQL statements. Either SQL keywords are all upper case or all lower case (I prefer upper case).
don't select *, but name the fields you want explicitly.
In sqlFetcher you check $run, which doesn't actually exist.

Your code looks wide open to SQL injection. It is unclear what data is user supplied, but for security reasons I would treat all variable data as user supplied (it doesn't hurt). Use prepared statements with mysqli or PDO everywhere, always.

OOP

Currently, it seems a bit unclear what your class should actually do. Should it be a model that temporarily stores data, as the getter imply? Or should it perform database interactions?

You could easily separate these concerns with a different structure:

class Post {

    private $author;
    private $title;
    // [...]

    public function __construct($author, $title) {
            $this->author = $author;
            $this->title = $title;
            // [...]
    }

    public function getAuthor() {
        return $this->author;
    }

    public function getTitle() {
        return $this->title;
    }
}

class PostDAO {

    function getById($id, $mysqli) {
        $selectById = $mysqli->prepare("SELECT author, title FROM <table_name> WHERE post_id = ?");
        $selectById->bind_param("i", $id);
        $selectById->execute();
        $selectById->bind_result($author, $title);
        $selectById->fetch();
        $post = new Post($author, $title);
        $selectById->close();
        return $post;
    }

    function getAll($mysqli, $amount, $offset = 0) {
        $selectAll = $mysqli->prepare("SELECT author, title FROM <table_name> LIMIT ?,?");
        $selectAll->bind_param("ii", $offset, $amount);
        $selectAll->execute();
        $selectAll->bind_result($author, $title);
        $posts = array();
        while ($selectAll->fetch()) {
            $posts[] = new Post($author, $title);
        }
        $selectAll->close();
        return $posts;
    }
}

You can use it like this:

$mysqli = new mysqli(credentials);
$post = PostDAO::getById($mysqli, 1);
echo $post->getAuthor();

$posts = PostDAO::getAll($mysqli, 5);
echo $posts[0]->getAuthor();

Now it's very clear that calling the getters does not cost very much (time-wise), and your model can be reused. For example, you might already know all the data without needing a database connection (because they are stored in the URL or session, or because you are performing tests and thus set them yourselves). If you only use the Post class in your other classes (such as the views), it can easily be separated from the database.


Get index of value in ObservableCollection I have an ObservableCollection<MyType> ItemList, and I need to know the index of a specific MyType in the collection.  However, when I hard-code the values like this:

ItemList.IndexOf(new MyType(val1, val2, val3));

it can't find the value because it is a different instance of MyType, even if all the values are the same.

So, I wrote this simple method:

private int IndexOfValInItemList(MenuItem val)
{
    for (int i = 0; i < ItemList.Count; i++)
    {
        if (ItemList[i].Title == val.Title && ItemList[i].Page == val.Page && ItemList[i].Menu == val.Menu) { return i; }
    }

    return -1;
}

This is in the same class as the value and directly accesses the value.  I know that I could expand it to take any ObservableCollection<MyType>, but I haven't because ItemList cannot be passed by reference:

private ObservableCollection<MenuItem> _itemList = new ObservableCollection<MenuItem>();
public ObservableCollection<MenuItem> ItemList
{
    get { return _itemList; }
    set
    {
        if (_itemList == value) return;
        _itemList = value;
        OnPropertyChanged();
    }
}

Is this a good way to implement this, or is there are different way?  Is there a way I could call ItemList.IndexOf(MyType(...)) and override the equality operator used to check it?  I already tried overriding the == operator, and that did not work.

I will have a second ObservableCollection<MyType> soon as I finish implementing my ViewModel, so I would like to know a generic solution, but if I have to write a second method to get the value from that collection, that is OK too.

The documentation for IndexOf() clearly states how it looks for a matching value.

  This method determines equality using the default equality comparer EqualityComparer<T>.Default for T, the type of values in the list.

Which brings you to the documentation for EqualityComparer<T>.Default

  The Default property checks whether type T implements the System.IEquatable<T> interface and, if so, returns an EqualityComparer<T>that uses that implementation. Otherwise, it returns an EqualityComparer<T> that uses the overrides of Object.Equals and Object.GetHashCode provided by T.

You need to be overriding Equals not the == operator. Changing the behavior of the == operator to something other than Object.ReferenceEquals() for reference types should only be considered in rare cases.


Simple Google ReCaptcha validation Linked:
Google reCAPTCHA Validator: Iteration II

I have also created a simple Google Recaptcha Validation class to handle verification.

I used some code from CodingFusion's post Google New reCaptcha I am not a robot using asp .net, but I have altered it so that it fit my use case, and to make it extendable and reusable.

Can I clean it up further?

public class ReCaptchaValidator
{
    private readonly string _ReCaptchaSecret;
    private readonly string _ReCaptchaSiteKey;
    public List<string> ErrorCodes { get; set; }

    public ReCaptchaValidator(string reCaptchaSecret)
    {
        _ReCaptchaSecret = reCaptchaSecret;
        this.ErrorCodes = new List<string>();
    }
    public ReCaptchaValidator(string reCaptchaSecret, string reCaptchaSiteKey)
    {
        _ReCaptchaSecret = reCaptchaSecret;
        _ReCaptchaSiteKey = reCaptchaSiteKey;
        this.ErrorCodes = new List<string>();
    }

    public bool ValidateCaptcha(HttpRequest request)
    {
        var sb = new StringBuilder();
        sb.Append("https://www.google.com/recaptcha/api/siteverify?secret=");
        sb.Append(_ReCaptchaSecret);
        sb.Append("&response=");
        sb.Append(request.Form["g-recaptcha-response"]);

        //client ip address
        sb.Append("&remoteip=");
        sb.Append(GetUserIp(request));

        //make the api call and determine validity
        using (var client = new WebClient())
        {
            var uri = sb.ToString();
            var json = client.DownloadString(uri);
            var serializer = new DataContractJsonSerializer(typeof(RecaptchaApiResponse));
            var ms = new MemoryStream(Encoding.Unicode.GetBytes(json));
            var result = serializer.ReadObject(ms) as RecaptchaApiResponse;

            if (result == null)
            {
                return false;
            }
            else if (result.ErrorCodes != null)
            {
                foreach(var code in result.ErrorCodes)
                {
                    this.ErrorCodes.Add(code.ToString());
                }
                return false;
            }
            else if (!result.Success)
            {
                return false;
            }
            else //-- If successfully verified.
            {
                return true;
            }
        }
    }

    //--- To get user IP(Optional)
    private string GetUserIp(HttpRequest request)
    {
        var visitorsIpAddr = string.Empty;

        if (request.ServerVariables["HTTP_X_FORWARDED_FOR"] != null)
        {
            visitorsIpAddr = request.ServerVariables["HTTP_X_FORWARDED_FOR"];
        }
        else if (!string.IsNullOrEmpty(request.UserHostAddress))
        {
            visitorsIpAddr = request.UserHostAddress;
        }
        return visitorsIpAddr;
    }

}
[DataContract]
public class RecaptchaApiResponse
{
    [DataMember(Name = "success")]
    public bool Success;

    [DataMember(Name = "error-codes")]
    public List<string> ErrorCodes;
}

private readonly string _ReCaptchaSecret;
private readonly string _ReCaptchaSiteKey;

private fields are either lowerCamelCase or _lowerCamelCase, both conventions are common.

public ReCaptchaValidator(string reCaptchaSecret)
{
    _ReCaptchaSecret = reCaptchaSecret;
    this.ErrorCodes = new List<string>();
}
public ReCaptchaValidator(string reCaptchaSecret, string reCaptchaSiteKey)
{
    _ReCaptchaSecret = reCaptchaSecret;
    _ReCaptchaSiteKey = reCaptchaSiteKey;
    this.ErrorCodes = new List<string>();
}

Don't repeat work in your constructors: use chaining instead.

public ReCaptchaValidator(string reCaptchaSecret)
{
    _ReCaptchaSecret = reCaptchaSecret;
    this.ErrorCodes = new List<string>();
}

public ReCaptchaValidator(string reCaptchaSecret, string reCaptchaSiteKey)
    : this (reCaptchaSecret)
{
    _ReCaptchaSiteKey = reCaptchaSiteKey;
}

With C# 6, you can also use a property initializer to.. initialize.. your property.

public List<string> ErrorCodes { get; set; }

public ReCaptchaValidator(string reCaptchaSecret)
{
    _ReCaptchaSecret = reCaptchaSecret;
    this.ErrorCodes = new List<string>();
}

becomes

public List<string> ErrorCodes { get; set; } = new List<string>();

public ReCaptchaValidator(string reCaptchaSecret)
{
    _ReCaptchaSecret = reCaptchaSecret;
}

I would also advise to use a private setter for your ErrorCodes like this:

public List<string> ErrorCodes { get; private set; } = new List<string>();

Likewise, with C# 6, you might as well make it a readonly property:

public List<string> ErrorCodes { get; } = new List<string>();

StringBuilders see their most use when you're concatenating strings in a loop. In this scenario I would use a formatted string which turns this:

var sb = new StringBuilder();
sb.Append("https://www.google.com/recaptcha/api/siteverify?secret=");
sb.Append(_ReCaptchaSecret);
sb.Append("&response=");
sb.Append(request.Form["g-recaptcha-response"]);
sb.Append("&remoteip=");
sb.Append(GetUserIp(request));

into this:

var uri = string.Format("https://www.google.com/recaptcha/api/siteverify?secret={0}&response={1}&remoteip={2}",
    _ReCaptchaSecret,
    request.Form["g-recaptcha-response"],
    GetUserIp(request));

Or with C# 6:

var uri = $"https://www.google.com/recaptcha/api/siteverify?secret={_ReCaptchaSecret}&response={(request.Form["g-recaptcha-response"])}&remoteip={GetUserIp(request)}";

else if (!string.IsNullOrEmpty(request.UserHostAddress))

I prefer string.IsNullOrWhiteSpace because only rarely whitespace characters are considered good input.


Find two distinct subsets of a list that add up to the same value This code should partition a list into two subsets of the given list that add up to the same number: for example [15, 5, 20, 10, 35, 25, 10] -> [15, 5, 10, 15, 10], [20, 35] would be a valid solution. I'm looking for any tips to improve code style (be more Pythonic) or performance (mainly improvements to the algorithm used, but Python-specific things are also welcome). Thanks!

from collections import Counter

def partition_into_equal_parts(l):
    '''Partitions s into two subsets of l that have the same sum.

    >>> problem = [15, 5, 20, 10, 35, 25, 10]
    >>> first, second = partition_into_equal_parts(problem)
    >>> valid_solution(first, second, problem)
    True
    '''
    total = sum(l)
    # If sum is odd, there is no way that total = sum(first) + sum(second) = 2 * sum(first)
    if total % 2:
        return
    first = subset_sum(total // 2, l)
    if first is None:
        return
    second = []
    # Fill second with items from counter
    second_counter = Counter(l) - Counter(first)
    for number, amount in second_counter.items():
        second.extend([number] * amount)
    return first, second

def valid_solution(first, second, problem):
    return sum(first) == sum(second) and Counter(first) + Counter(second) == Counter(problem)

def subset_sum(k, lst):
    '''Returns a subset of lst that has a sum of k.

    >>> sum(subset_sum(24, [12, 1, 61, 5, 9, 2]))
    24
    >>> subset_sum(53, [12, 13, 14])
    '''
    return recursive_calculate(k, sorted(lst, reverse=True), 0)

def recursive_calculate(k, lst, start):
    for idx in range(start, len(lst)):
        if lst[idx] == k:
            return [lst[idx]]
        elif lst[idx] < k:
            rest = recursive_calculate(k - lst[idx], lst, idx + 1)
            if rest is not None:
                rest.append(lst[idx])
                return rest

Some "more pythonic" suggestions which also improve performance:

use Counter.elements()

in partition_into_equal_parts this code:

second = []
# Fill second with items from counter
second_counter = Counter(l) - Counter(first)
for number, amount in second_counter.items():
    second.extend([number] * amount)

can be merely replaced by

second = list((Counter(l) - Counter(first)).elements()

As Counter.elements returns a chained iterable of the expanded elements according to their count. So no need to do that with a loop and an extra list.

Cache the indexed element

In recursive_calculate, you have to use the index in

for idx in range(start, len(lst)):

but why not storing lst[idx] in a local variable? It's repeated a lot of times, and accessing a list element is costly. Just cache this access since you're not writing in lst (well you're writing to the end of it, recursively, but lst[idx] isn't udpated because the index is low enough).

def recursive_calculate(k, lst, start):
    for idx in range(start, len(lst)):
        element = lst[idx]
        if element == k:
            return [element]
        elif element < k:
            rest = recursive_calculate(k - element, lst, idx + 1)
            if rest is not None:
                rest.append(element)
                return rest
    return None

Small note: python functions implicitly return None, but "Explicit is better than implicit" (The Zen Of Python) so it's better to actually return it.


Turning multiple PHP arrays into one array ready for conversion to Javascript I am creating a multiple choice quiz game with PHP and Javascript. Questions can have 2 to 6 answers. I have been using the PHP queries in the code below to get arrays of the questions of a quiz, and the answers for each questions.

I now want to use this data in Javascript, and want to make it so each time a user clicks next question, a question and corresponding answers are displayed.

I think (but am not sure) that the best way to do this is to combine the arrays into one where the question array contains the answers arrays before converting to a javascript array.

Is this really the way I should do this, and if so how do I do so?

$thisquizid = $_POST['quizidvalue'];
    for ($j = 0; $j < $questionrows; ++$j)
        {
            $questionresult = pg_fetch_array($questionquery);
            $answerquery = pg_query($db_handle, "SELECT * FROM answer WHERE questionid = '$questionresult[0]'");
            $answerrows = pg_num_rows($answerquery);

        for ($i = 0; $i < $answerrows; ++$i)
            {
                $answerresult = pg_fetch_array($answerquery);
            }

    }

Running a SQL statement in a loop is in general a bad idea. Depending on your $questionsrow you might send a lot of not needed requests.

In relation to MECUs hint you could use something like:

$questions=array();
//add constrains to select only some questions or sort the answers
$result=...query($db_handle, "SELECT * FROM answer");
while ($row=...fetch_array($result))
{
    $qid=$row['questionid'];
    if (!isset($questions[$qid])) =array(); //create subarray if new question
    $questions[$qid][]=$row //append a new element to the question array
}
$json=json_encode($questions);

I.e. $questions[1] will contain a array with all your answers to question 1. The sorting of the answers can be moved to SQL query, also if you don't need all fields you can restrict this in the SQL and don't need to take care of this in your PHP.


Algorithm to park cars with minimal moves I'm working on a car move problem. Suppose we have origin parking position for each car, [-1,1,2,3,7,6,4,5] (which means first position is empty, car with ID 1 parked at 2nd position, car with ID 2 parked at 3rd position), we want to find the minimal move to re-park car as specific desired positions. For example specific desired position [4,6,5,1,7,3,2,-1] means car with ID 4 parked at first position, car with ID 6 parked as 2nd position, etc. -1 means empty parking lot to utilize.

Here is my code, my major idea is to find a parking chain (cycle), and move the chain together, for example, in my above example,

Find a chain (cycle): car 1 move to position of car 3, car 3 move to position of car 6, car 6 move to position of car 1, etc.
Leverage empty slot to move the chain, in above example, I move car 6 to empty slot, then move car 3 to car 6 position, then move car 1 to car 3 position, finally move car 6 back from empty slot to car 1 position.

Have two questions on my code,

I use a dictionary car_new_position to facilitate look-up for car ID and new position, is it good or any smarter ideas to not using the dictionary and achieve the same algorithm time complexity?
I treat empty slot the same as car (with ID -1) in the algorithm, not sure if I treat this way correctly, or I should treat empty slot in some different way?

from collections import defaultdict

def carMove(original_positions, new_positions):

    car_new_position = defaultdict(int) # build a dictionary to map car to new position
    for i in range(len(new_positions)):
        car_new_position[new_positions[i]]=i
    result=[]
    flags=[False]*len(original_positions)
    for i in range(len(original_positions)):
        if not flags[i]:
            move_chain=set()
            move_chain.add(i)
            flags[i] = True
            new_pos = car_new_position[original_positions[i]]
            while new_pos not in move_chain:
                move_chain.add(new_pos)
                flags[new_pos] = True
                new_pos = car_new_position[original_positions[new_pos]]
            result.append(move_chain)

    print result

if __name__ == "__main__":
    carMove([-1,1,2,3,7,6,4,5], [4,6,5,1,7,3,2,-1])

Output,

[set([0, 2, 6, 7]), set([1, 3, 5]), set([4])]

Ways you can improve your current code:

Follow PEP8, it builds consistency. Your assignments have either a space either side or no spaces. Pick one style, preferably the one with a single space either side.
You can use enumerate if you need to loop through both indexes and values of a list.
You can remove one level of indentation by inverting your if check, if flags[i] and using continue.
You can move the move_chain.add(i) and car_new_position[original_positions[i]] into the while loop.
This is by using new_pos = i, without adding it to the move_chain.
If you don't follow (4), rather than using move_chain = set(); move_chain.add(i) use move_chain = {i}.
You can move the logic for setting flags to true out of the while loop.
I prefer this as it's not needed to make the while loop work,
and so makes the code less complex.
Don't print rather than return from a function.
Changing your flags to a set can remove some code. I prefer sets, but it's probably slower.

def car_move(original_positions, new_positions):
    car_new_position = defaultdict(int)
    for i, pos in enumerate(new_positions):
        car_new_position[pos] = i
    result = []
    flags = set()
    for i in range(len(original_positions)):
        if i in flags:
            continue
        move_chain, new_pos = set(), i
        while new_pos not in move_chain:
            move_chain.add(new_pos)
            new_pos = car_new_position[original_positions[new_pos]]
        flags |= move_chain
        result.append(move_chain)
    print result

But what does your output even mean?
Take:

>>> carMove([-1,1,2,3,-1,4,5,6,-1], [-1,2,3,1,-1,5,6,4,-1])
[set([0, 8]), set([1, 2, 3]), set([8, 4]), set([5, 6, 7])]

What does this mean?
Do I have to move the cars ten times?
Do I need to notice that the set([0, 8]) is two empty car slots?
Why does the cycle 1, 2, 3 not have any empty car slots?
The output is unintuitive.
Instead, using the same idea of moving cycles you can make intuitive output.
By actually moving the cars.

Take the following:

>>> car_move([-1,1,2,3,-1,4,5,6,-1], [-1,2,3,1,-1,5,6,4,-1])
1, 1 -> 8
2, 2 -> 1
3, 3 -> 2
1, 8 -> 3
4, 5 -> 8
5, 6 -> 5
6, 7 -> 6
4, 8 -> 7
8

Sure it prints the moves, rather than returning them. But it's much simpler to understand.
Car1 moves from the first index to the eighth one. Car2 second index to first.
And there is a total of eight moves.

To make this you can:

Remove move_chain and flags, as we'll use other things.
This should get you something like:

def car_move(input, output):
    position = dict()
    for i, pos in enumerate(output):
        position[pos] = i
    for i in range(len(input)):
        if i in ...:
            continue
        new_pos = i
        while new_pos not in ...:
            new_pos = position[input[new_pos]]
    print result

Fix the conditions:

If the input and output value are the same, we'll skip that position.
While the input and output of the index are not the same.

Add a previous index and a current index to the while loop.
Add a swap function and call it in the while loop.

This function will swap the inputs, update the positions and print the swap.
We'll add a check to see if i's value is empty, if not swap it with an empty one.
Otherwise we may be swapping cars, not moving them to empty spaces.

And so should get you:

def car_move(input, output, empty=0):
    swaps = 0
    def swap(a, b):
        nonlocal swaps
        swaps += 1
        input[a], input[b] = input[b], input[a]
        position[input[a]] = a
        position[input[b]] = b
        #print(input)
        print('{0}, {1} -> {2}'.format(input[b], a, b))
    position = {
        pos: index
        for index, pos in enumerate(input)
    }
    for start in range(len(input)):
        if input[start] == output[start]:
            continue
        if input[start] != empty:
            swap(start, position[empty])
        index = start
        while output[index] != input[index]:
            prev_index = index
            index = position[output[prev_index]]
            swap(index, prev_index)
    return swaps

This is better as it finds the swaps, and adds a blank swap if needed.
It can also be changed quite easily to return an array of swaps, rather than print swaps and output the amount.
The biggest down side to my code is it requires nonlocal, a Python 3 only keyword, to increase the amount of swaps in the swap function.
But if you change it to output the actual swaps, then this is not needed.
As you can mutate a list in another scope. And would work in both Python 2 and Python 3.