Selection sort implementation in Java Here's an implementation of selection sort, that sorts an array in ascending order.

Please let me know of any improvements/optimisations that can be done.

import java.util.List;

public class SelectionSort {

    public static void start(List<Integer> arrayToSort){
        for(int i = 0; i < arrayToSort.size(); i++) {   // i = leftmost index of unsorted part of the array
            int minimumValue = i;
            for(int j = i; j < arrayToSort.size(); j++){
                if(arrayToSort.get(j) < arrayToSort.get(minimumValue)){
                    minimumValue = j;
                }
            }
            swap(i, minimumValue, arrayToSort);
        }
    }

    private static void swap(int a, int b, List<Integer> arrayToSort){
        int temp = arrayToSort.get(a);
        arrayToSort.set(a, arrayToSort.get(b));
        arrayToSort.set(b, temp);
    }
}

I suggest you format

for(int i = 0; i < arrayToSort.size(); i++) {   // i = leftmost index of unsorted part of the array

as

// i = leftmost index of unsorted part of the array
for(int i = 0; i < arrayToSort.size(); i++) {

swap takes arguments a, b and arrayToSort. These arguments could be more explanatory: swap doesn't sort anything and it doesn't take an array, and a and b don't say much.

It's canonical to use i and j as indices, so that would be more appropriate - although longer names wouldn't hurt either. The List argument would be better as items or similar. items is this-like, so put it first.

private static void swap(List<Integer> items, int i, int j) {
    int temp = items.get(i);
    items.set(i, items.get(j));
    items.set(j, temp);
}

You can also make this more like the OpenJDK implementation by using the return value from set:

private static void swap(List<Integer> items, int i, int j) {
    int temp = items.set(i, items.get(j));
    items.set(j, temp);
}

or even

private static void swap(List<Integer> items, int i, int j) {
    items.set(j, items.set(i, items.get(j)));
}

You could also make it generic.

private static <T> void swap(List<T> items, int i, int j) {
    items.set(j, items.set(i, items.get(j)));
}

Your sort is of course inefficient; you're using selection sort. However, you can at least make it a little faster. First neaten it up - including changing the name to something more descriptive. Note that minimumValue is not a value but an index - this should be fixed.

public static void sortInPlace(List<Integer> toSort){
    // i = leftmost index of unsorted part of the array
    for(int i = 0; i < toSort.size(); i++) {
        int minimumValue = i;
        for(int j = i; j < toSort.size(); j++) {
            if(toSort.get(j) < toSort.get(minimumValue)) {
                minimumValue = j;
            }
        }
        swap(toSort, i, minimumValue);
    }
}

You can change the inner loop to start at i + 1. You can also cache the value to halve the number of toSort.gets you make.

public static void sortInPlace(List<Integer> toSort){
    // i = leftmost index of unsorted part of the array
    for(int i = 0; i < toSort.size(); i++) {
        int minimumIndex = i;
        int minimumValue = toSort.get(i);
        for(int j = i + 1; j < toSort.size(); j++) {
            if(toSort.get(j) < minimumValue) {
                minimumIndex = j;
                minimumValue = toSort.get(j);
            }
        }

        swap(toSort, i, minimumIndex);
    }
}

This gives a noticeable speed improvement.

Frankly, though, if you want a reasonably fast integer selection sort, use an array. int[] is unboxed, which means that it's some 4x the speed. It's actually faster to copy into a temporary int[], sort and copy it back than to sort in a boxed List.


SPOJ - POWFIB (Fibo and non fibo) Time Limit Exceeds Problem

  Find (a^b)%M, where

  a = Nth non-fibonacci number

  b = Nth fibonacci number modulo M

  M = 1000000007

  Consider fibonacci series 1,1,2,3,.....

  INPUT

  First line contains T , the number of test cases.

  Each next T lines contains a  number N.

  OUTPUT

  Print T lines of output where each line corresponds to the required answer.

  EXAMPLE

  Input:

  3

  3

  2

  1

  Output:

  49

  6

  4

  Constraints

  1<=T<=100000

  1<=N<=10^7

Here is my code for the problem link

#include <cstdio>
#include <unordered_map>
using namespace std;

typedef long long int ll;

ll M = 1000000007;

ll mulmod(ll a, ll b)       //modular multiplication
{
    ll x = 0;
    ll y = a%M;
    while(b>0)
    {
        if(b%2)
            x = (x+y)%M;
        y = (y+y)%M;
        b/=2;
    }
    return x%M;
}

ll modulo(ll a, ll b)       //modular exponentiation
{
    ll x = 1;
    ll y = a;
    while(b)
    {
        if(b%2)
            x = mulmod(x,y);
        y = mulmod(y,y);
        b/=2;
    }
    return x%M;
}

unordered_map<ll,ll> Fib;

ll fibo(ll n)       //n+1 th fibonacci number
{
    if(n<2)
        return 1;
    if(Fib.find(n) != Fib.end())
        return Fib[n];
    Fib[n] = (fibo((n+1) / 2)*fibo(n/2) + fibo((n-1) / 2)*fibo((n-2) / 2)) % M;
    return Fib[n];
}

ll nonfibo(ll n)        //nth non-fibonacci number
{
    ll a = 1, b = 2, c = 3;
    while(n>0)
    {
        a = b;
        b = c;
        c = a+b;
        n-=(c-b-1);
    }
    n+=(c-b-1);
    return n + b;
}

int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        scanf("%lld",&n);
        printf("%lld\n",modulo(nonfibo(n),fibo(n-1)));
    }
    return 0;
}

It exceeds the time limit, how do I improve the code?

Here, you are using modular exponentiation and modular multiplication, which are fast enough.
Your nonfibo function is also taking only O(lg(n)) time.
But your method for computing nth fibonacci number is not much efficient. Try using this Linear Recurrence Solving Method.


Function which will fire off a specific template depending on which element is selected I have this function which will fire off a specific template depending on which element is selected. However, with the way it is, I'd have to update the JavaScript and the HTML when a new element is added. What I'd like is to have the function scale up to as many HTML elements one would add.

So far I have figured out if I do this:

 function templateLoader(e) {
        var doc = document,
            body = doc.getElementsByTagName('body'),
            event = EventUtility.getEvent(e),
            target = EventUtility.getTarget(event),
            overlay = $('#overlay');

        console.dir(event.currentTarget);

        if (target !== event.currentTarget) {

            switch(target.id){
                case '1':
               $.get('../../../templates/index.html',function(template) {
                 modal.append(Mustache.render($(template).filter('#templateID').html()))
                 modal.listview("refresh");
                 });
                break;

                case '2':
                alert(target.title);
                break;

                case '3':
                alert(target.title);
                break;

                case '4':
                alert(target.title);
                break;

                case '5':
                alert(target.title);
                break;
            }
        }

        EventUtility.stopPropagation(event);

    }

    EventUtility.addHandler(flimFlam, 'click', templateLoader);

});

HTML:

But of course that depends on me going int there and adding newer case conditions when needed. I know I'll have to go into the files anyway when the HTML is added. But I wanted a way to have the JS ready for any amount of cases.

I began with something like this:

 for (var i = 0, l = event.target.length; i < l; i++) {
                console.log(target.id[i]);
            };

body = doc.getElementsByTagName('body'),

There's a shorter document.body. But then, body isn't even being used in the function. So you probably have to remove it.

console.dir(event.currentTarget);
alert(target.title);

I suggest you don't pepper your code with console.* and alert to view values. Take advantage of the browser's debugger, and use breakpoints. Not only can you view the variable, you can also view surrounding variables, enclosing scopes and more.

switch(target.id){

First, I wouldn't use id. id is supposed to be unique in the page. Use it if you're absolutely sure that the element is the only one in the page with that id. This can get real messy when you discover that your HTML needs to be in multiple places, but contain the same structure and/or content.

But then, I notice you use data-* attributes. Use that instead of id. It's designed for that purpose, carry data in markup.

 case '1':
$.get('../../../templates/index.html',function(template) {
  modal.append(Mustache.render($(template).filter('#templateID').html()))
  modal.listview("refresh");
  });

 break;

 case '2':
 alert(target.title);
 break;

 case '3':
 alert(target.title);
 break;

 case '4':
 alert(target.title);
 break;

 case '5':
 alert(target.title);
 break;

It doesn't have a default. switch is also a bit clunky. And I usually avoid switch because failing to add a break where needed will cause your code to run down an unexpected path.

The following would be a better way to model it:

// An operations object, with key as the id, and function as value
var operations = {
  '1': function(){
    $.get('../../../templates/index.html',function(template) {
      modal.append(Mustache.render($(template).filter('#templateID').html()))
      modal.listview("refresh");
      });
  },
  '2': function(){
    alert(target.title);
  },
  // and so on
}

if(typeof operations[target.id] === 'function') operations[target.id].call(null);


ReentrantReadWriteLock lock upgrade method I have a question about lock upgrading.Specifically what bothers me is between readlock.unlock() and following writelock.lock()...
I am providing a nearly complete implementation for a sample cache.I just omitted actual loading of cached data from database.

I appreciate if you can review the code and share your thoughts. I tried to express my concern in the java comments . My question is how to correctly synchronize in order to avoid rechecking the cache in load cache.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

public class JavaRanchSampleCache {

    private ConcurrentHashMap<String, ReentrantReadWriteLock> refreshLocks = new ConcurrentHashMap<String, ReentrantReadWriteLock>();
    private ConcurrentHashMap<String, HashMap<String, String>> cacheData = new ConcurrentHashMap<String, HashMap<String, String>> ();

    public  HashMap<String, String> getCachedData(String cacheKey)
    {
        ReentrantReadWriteLock lock = refreshLocks.get(cacheKey);

        if(lock==null)
        {
            lock=new ReentrantReadWriteLock();
            ReentrantReadWriteLock previous=refreshLocks.putIfAbsent(cacheKey, lock);
            if(previous!=null)//null means no previous lock object,first time usage
                lock=previous;
        }

        //we have a safe lock at this point
        try
        {
            lock.readLock().lock();//read the cached item for correspoding cacheKey
            HashMap<String, String> cachedItem=cacheData.get(cacheKey);
            if(cachedItem==null)//it is not cached yet.Load to cache on first request
            {
                cachedItem=loadItemExpensive(cacheKey);
            }

            return cachedItem;//return the cached item.

        }
        finally
        {
            lock.readLock().unlock();
        }

    }

    private HashMap<String, String> loadItemExpensive(String cahceKey)
    {
        ReentrantReadWriteLock lock = this.refreshLocks.get(cahceKey);
        HashMap<String, String> cachedItem=null;
        try
        {
             /*these two lines are for lock upgrading
             * BUT what happens if another thread interacts between line1 and line2
             * I mean after the readlock is relased,some OTHER thread might gain the writelock
             * before this thread and perform loaddata and update cache operation.
             * So should I check the cache once more to see if some other thread
             * has updated the cache? I 'feel' that I should,but it is ugly,i need some clever way.
             */
            lock.readLock().unlock();//line1
            lock.writeLock().lock();//line2

            /*omitted load data from some expensive store such as database or remote server*/

            return  cachedItem;
        }
        finally
        {
            lock.readLock().lock();//writelock owner can grant readlock immediately.
            lock.writeLock().unlock();//lock released
        }
    }

}

Your fears are valid. Once you let go of the lock, all bets are off. When you get the write lock, you will need to check if another thread has mutated the cache. Don't think of it as "ugly"; think of it as "correct". Continue to use comments to explain what you're doing and why you're doing it.

In a nutshell, a read/write lock can't support both upgrading and downgrading. Multiple locks must always be acquired in the same order (in this case, write then read), otherwise a deadly embrace can occur. So when going the other way (read then write), you must let go of the lock, at which point any decisions you made based on current state must be reconsidered.

But there are other options, depending on the details of your situation.

One is to always a get a write lock in anticipation of needing to make a modification and downgrading to a read lock if the data's already there. This is probably not what you want, especially if the majority of operations are read-only, as it will lead to lock contention and poor response times under load.

Other options might involve allowing multiple threads to (redundantly) perform the expensive load, and acquiring the write lock just at the moment of insertion to the table. Or it might be appropriate to just blindly overwrite the existing entry (in this last case, all you would really need is ConcurrentHashMap) . It all depends on the scenario what you're willing to tolerate.

Hope this helps.


Isometric Chunk Game I'm trying to create an Isometric Game in JavaScript.  I think the code is pretty good, but I'd like to know if there is something to improve.

        var CameraX = 0,
            CameraY = 0;

        for(var yChunks = 0; yChunks < NumYChunks; yChunks++)
        {
            var ChunkY = yChunks * HalfChunk,
                ChunkCameraY = yChunks * 4294967296;

            for(var xChunks = 0; xChunks < NumXChunks; xChunks++)
            {

                var FinalyChunk = ChunkY + CameraY;

                var FinalxChunk = xChunks * SizeChunk,
                    ChunkCameraX = xChunks + NumXChunks + CameraX;

                var index = new Number(ChunkCameraY + ChunkCameraX);

                ctx.fillStyle = "black";
                ctx.font = "bold 13px Arial";
                ctx.fillText("ID: " + index, FinalxChunk + 10, FinalyChunk + 20);

                for(var CeldY = 0; CeldY < CeldsYChunk; CeldY++)
                {
                    var yCeld = CeldY * 40;
                    for(var CeldX = 0; CeldX < CeldsXChunk; CeldX++)
                    {
                        var NewCeldX = HalfChunk + FinalxChunk + (CeldX * 40) - yCeld - 40 ,
                            NewCeldY = (CeldX * 20) + (yCeld / 2) + (FinalyChunk) - 10 ;
                        ctx.beginPath();
                        ctx.rect(NewCeldX, NewCeldY, 80, 40);
                        ctx.stroke();
                        ctx.closePath();
                    }
                }
            }
        }

Someone posted an answer which had some great points, but they deleted it.  I am only going to mention a couple of points that they made as well as some new ones, but they should definitely put their answer back up!

I am no Javascript expert but I have used it before.  Despite this, I am having great difficulty understanding what your code does.  You say you think the code is pretty good, so I'll have to take your word for it that it does what you are expecting it to do.  It is very hard to understand, though!

I'll just go through and point out things as I see them.

    var CameraX = 0,
        CameraY = 0;

Personally for this I would just say var CameraX; and var CameraY; on separate lines.  I don't see what you are really gaining by omitting the second var.  I know that it is legal to do it your way in Javascript, so it's not that it's wrong, but in my opinion it just causes a potential reader of your code to have to pause and reread it to fully understand.

for(var yChunks = 0; yChunks < NumYChunks; yChunks++)

You are iterating based on yChunks, but the fact that you have it plural just makes it confusing.  I would suggest simply yChunk, but I will talk about that more in the next paragraph.  The name NumYChunks is also a bit confusing.  Is it the max number of y chunks?  If so, I would call it MaxYChunks instead.

To elaborate on my earlier point, your naming is all over the place and completely inconsistent.  You say things like ChunkY, Finalychunk, yChunks, NumYChunks, all in different places and they all mean different things.  This makes the logical flow of your program very hard to follow.  At the very least, all of these things need to have a similar format, so if you are going to have Y capitalized and at the end of the variable, always do that.  So for example FinalyChunk would be FinalChunkY.  But an even better approach is to minimize the number of similar names, so try to come up with better, more descriptive names whenever possible.

A related point, I would suggest that you follow the variable naming conventions in whatever language you are writing in, so for Javascript that would be camelCase.

You use many magic numbers in the code, such as

ChunkCameraY = yChunks * 4294967296;
ctx.fillText("ID: " + index, FinalxChunk + 10, FinalyChunk + 20);
ctx.rect(NewCeldX, NewCeldY, 80, 40);

What is 4294967296?  What do 10 and 20 represent?  What are 80 and 40?  By declaring these as variables somewhere in the code, such as rectangleXSize = 80; rectangleYSize = 40; you will be accomplishing two things.  First, it will be much easier to read and understand your code.  Second, you will have a much easier time trying to modify the code at a later time, because at the top of the function you will see those values declared.  Otherwise you will have to search through the code to find the numbers you want to change.

The main logic of the function is where things get the most confusing, at least for me.  You have a four level deep for-loop structure, which is a sign that the design needs to be reevaluated.  Any time you have to have that many for loops to accomplish something, there is usually a better approach.  Additionally, I would break as much as possible out of the for loops and into smaller functions.  This will improve the readability of your code and make the logic easier to follow and easier to change later.  If you use descriptive function names, it will also be self documenting.

Finally I will echo the other (now deleted) answer and say that you should have more comments in your code.  You might even be forgiven for a deeply nested for loop if you have comments that explain what is happening at each stage.  At the very least, it will be a lot easier for you to understand in the future if you ever try to look at the code again!


Try/catch block in PDO wrapper I have written a PDO wrapper and a class file like a model.  It's looking good so far, but I'm just confuseed on where I should put the try/catch block.  Would it be better to place it in the PDO wrapper (pdoDatabase.php), mobile.php (model) or test.php?

pdoDatabase.php

class pdoDatabase {

public $db;
private $sth;
private static $instance;
private $error;

private function __construct() {
    $dsn = "mysql:dbname=" . config::read("db.database") . ";host=localhost";
    $username = config::read("db.username");
    $password = config::read("db.password");
    $this->db = new PDO($dsn, $username, $password);
    $this->db->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
}

public static function getInstance() {
    if (!isset(self::$instance)) {
        self::$instance = new static();
    }
    return self::$instance;
}

public function fetchData($sql, $params = array(), $fetchMode = 'all') {
    // Should try...catch block be here?
    try {
        $this->sth = $this->db->prepare($sql);
        if (count($params) > 0)
            $this->setBind($params);

        $this->sth->execute();
        $fetch = ($fetchMode == 'single') ? "fetch" : "fetchAll";
        return $this->sth->$fetch();
    } catch (PDOException $e) {
        $this->error = array(
            'status' => 'error',
            'message' => $e->getMessage()
        );
        return false;
    }
}

public function setBind($params) {
    if (is_object($this->sth)) {
        foreach ($params as $key => $value) {
            $this->sth->bindValue(":$key", $value);
        }
    }
}

public function error() {
   return $this->error;
}
public function beginTransaction() { }
public function commit() { }
public function rollBack() { }

mobile.php

class Mobile {

    public $db;

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

    public function findPhoneAffiliate($phoneId = null, $affiliateId = null, $affiliatePhoneId = null) {
     // or should try...catch block be here?
        $bindAr = array();
        if ($phoneId !== null)
            $whereAr[] = "phone_id = " . $phoneId;

        if ($affiliateId !== null)
            $whereAr[] = 'affiliate_id = ' . $affiliateId;

        if ($affiliatePhoneId !== null) {
            $whereAr[] = 'affiliate_phone_id = :affiliate_phone_id';
            $bindAr['affiliate_phone_id'] = $affiliatePhoneId;
        }

        $where = count($whereAr) > 0 ? 'WHERE ' . implode(' AND ', $whereAr) : '';

        $sql = "SELECT * FROM phone_affiliate $where";
        return $this->db->fetchData($sql, $bindAr, 'single');
    }
}

test.php

$mobileResult = $mobile->findPhoneAffiliate(null, 'f', "ASEF33");
if ($mobileResult) {
    // Data Found!
    print_r($mobileResult);
} else {
    if ($mobile->db->error()) {
        print_r($mobile->db->error());
        exit();
    }
    if ($mobile->db->rowCount() == 0)
        echo "Data Not Found";
}

As you can see, it will need to check if there any error or no data found in the else statement. Is this how it should be done?  If now, what can be improved to reduce the code from the test.php sample?

I'll probably revisit this later, but for now:

The exception catching should be done at either the model or model-using layer.  I would probably let the exceptions bubble up through the model unless you want the model to be fairly high level.

For the sake of abstracting the DB layer away from the model layer, I might consider wrapping the PDOException in some kind of model exception(s).  Exception wrapping is typically an anti-pattern, but it would keep your consuming code from needing to know that the models are all dependent on PDO.  (Thus allowing you to change PDO to something else if you ever wanted to -- basically it's a weird instance of separation of concerns and hiding implementation details.)

I'm starting to ramble, but what I'm trying to convey is that your consuming code needs to know something went wrong.  If you handle the exception in your DB class, you model has no (pleasant) way to know that something went wrong.  If you handle the exception in your model, the level above the model has no (pleasant) way to know something went wrong.  Basically your consuming code needs to know something happened, and for that to be the case, you need exceptions to come out of the model.  (An alternative would of course be returning a Boolean or something along those lines.  That tends to not fit the OO paradigm very well though, and PDO sometimes uses Boolean false when something isn't an error.)

Your pdoDatabase class shouldn't be a singleton.

$this->db = pdoDatabase::getInstance(); you pass the pdoDatabase instance as a parameter instead of coupling your code to this static method.

Dependency Injection

There's a few other things that stuck out to me, but I'm out of time now ;(.  Will come back later.

Exception Catching

It should be extremely rare for an exception to actually happen with your Mobile.

Consider the sources of exceptions: connection drops, invalid syntax, unknown column/table/etc, so on.  Basically there's different layers of exceptions. There's the connection oriented ones, and the SQL oriented ones.  The SQL oriented ones should never happen.  By the time your code goes into production, you should be certain that none of your queries have invalid syntax, reference non-existing entities, so on.

This leaves connection problems as the only source of exceptions (or perhaps MySQL related hiccups, though those should be pretty rare).

Because of this rarity, I would be tempted to basically ignore any exceptions.

Even if you did handle the exceptions, what are you going to do with them?

try {
    $affs = $mobile->findPhoneAffiliate(5);
} catch (SomeExceptionClass $ex) {
    //There's not really a good way to recover from this, so you might as well
    //show some kind of "Oops, something broke." page.
    //You could then log the exception behind the scenes and make sure the end-user
    //sees nothing sensitive.
}

What I would do in this situation is just let the exception bubble up to the very top. I would have a giant try/catch at the top layer though that intercepts any uncaught exceptions and renders some kind of error page.

How you do this will highly depend on the structure of your website, but assuming you're doing something MVC-ish, it should be fairly simple.  In the catch block, just kill the current dispatch, and instead dispatch a request for the exception page.


Looping through nested arrays with creating new array from nested items I have written this function but I am not so proud on it. I could use some help refactoring it.

Would recursion improve my code?

Data sample.

{
  "Name":"test2",
  "DepartmentUnitId":"test",
  "ParentDepartmentUnitId":"test",
  "NestedDepartments":[
    {
      "Name":"test2",
      "DepartmentUnitId":"test",
      "ParentDepartmentUnitId":"test",
      "NestedDepartments":[]
    },
    {
      "Name":"test2",
      "DepartmentUnitId":"test",
      "ParentDepartmentUnitId":"test",
      "NestedDepartments":[]
    }
  ]
}

JS:

function indentDepartments(departments, model) {
    var indentedDepartments = [];

    _.each(departments, function (department) {
        indentedDepartments.push(buildDepartment(department, 0));
        _.each(department.NestedDepartments, function (lv1Department) {
            indentedDepartments.push(buildDepartment(lv1Department, 1));
            _.each(lv1Department.NestedDepartments, function (lv2Department) {
                indentedDepartments.push(buildDepartment(lv2Department, 2));
            });
        });
    });

    function buildDepartment(data, level) {
        department = _.pick(data, 'DepartmentUnitId', 'ParentDepartmentUnitId');
        name = _.times(level, function () { return '-'; }).join('') + data.Name;

        _.extend(department, { Name: name });
        return department;
    }
    model.parentDepartments(indentedDepartments);
}

Edit:
Nested array can go 2 levels deep, but I wouldn't mind making this function more scalable.

You could indeed create a recursive function to collect each level of departments, keeping going as long as there are nested departments:

function indentDepartments(departments, model) {

    model.parentDepartments(doIndentDepartments(departments, 0));

    // called recursively to indent each level of department
    function doIndentDepartments(departments, level) {
        // indent departments at current level
        var departments = _.map(departments, function(department) {
            return buildDepartment(department, level);
        });

        // indent nested departments
        if (typeof departments.NestedDepartments != 'undefined') {
            departments.push.apply(departments, doIndentDepartments(departments.NestedDepartments, level +1));
        }

        return departments;
    }

    function buildDepartment(data, level) {
        department = _.pick(data, 'DepartmentUnitId', 'ParentDepartmentUnitId');
        name = _.times(level, function () { return '-'; }).join('') + data.Name;

        _.extend(department, { Name: name });
        return department;
    }
}


Database-agnostic user model in Golang I'm trying to design a database model for an API. So far, here's my attempt to do so:

I have a package called models that contains all of the models. Here, User is the database model and UserStorer is an interface that should be implemented by any store (e.g. postgres, mongodb etc.)

package models

//User represents an application user
type User struct {
    ID         int64
    Email      string
    Password   string
    FirstName  string
    MiddleName string
    LastName   string
}

...

//UserStorer represents a user store
//this can be used to store user on different
//data store
type UserStorer interface {
    List(...UserFilter) ([]User, error)
    Get(...UserFilter) (User, error)
    Create(User) error
    Update(User) error
    Delete(...UserFilter) error
}

Then I have a package called store, which contains the implementations of model stores like UserStorer

package store

import (
    "github.com/jmoiron/sqlx"

    "github.com/steven-ferrer/go-db-models/models"
)

//UserStore implements models.UserStorer
type UserStore struct {
    db *sqlx.DB
}

func (cs *UserStore) List(filters ...models.UserFilter) ([]models.User, error) {
    return nil, nil
}

func (cs *UserStore) Get(filters ...models.UserFilter) (models.User, error) {
    return models.User{}, nil
}

func (cs *UserStore) Create(User models.User) error {
    return nil
}

func (cs *UserStore) Update(User models.User) error {
    return nil
}

func (cs *UserStore) Delete(filters ...models.UserFilter) error {
    return nil
}

func NewUserStore(db *sqlx.DB) models.UserStorer {
    return &UserStore{db}
}

The question is, am I doing it right? If not, how do I improve it?

Here is the repo of the example that I used: https://github.com/steven-ferrer/go-db-models

I like your approach:

First you've defined an interface on accepting side of application. So you can fix requirements to parts responsible for storage.
Realisation is not tied to interface. Today you may use PostgreSQL, later you may add some sharding on application side, or even migrate to another DB. Keeping db-related logic in one place helps you do it in future.
Next you can cover it with tests to ensure logics won't get broken in future impovements.


Proportional sorting of web scrape results If you have a given list of lists what's the best way to sort them proportionally? Is there a better way to do this?

The idea is that in a case of web scraping, you would want to avoid hitting google all the time and want to distribute calls so that they are as even as possible.

Is this a thing that can be done more efficiently than this terribad code that I wrote?

urls = [
        ['http://google.com/search','redirect.com', 0],
        ['http://duckduckgo.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0],
        ['http://bing.com/search','redirect.com', 0],
        ['http://yahoo.com/search','redirect.com', 0],
        ['http://yahoo.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0],
        ['http://bing.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0],
        ['http://yahoo.com/search','redirect.com', 0],
        ['http://altavista.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0],
        ['http://yahoo.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0],
        ['http://altavista.com/search','redirect.com', 0],
        ['http://google.com/search','redirect.com', 0]
    ]

def get_domain( url ):
    domain = ''
    parts = tldextract.extract( url )
    if parts.subdomain != '' and parts.subdomain != 'www':
        domain = parts.subdomain + '.' + parts.domain + '.' + parts.suffix
    else:
        domain = parts.domain + '.' + parts.suffix
    return domain

def proportional_sort( urls ):
    doms = [get_domain(url[0]) for url in urls]
    dom_set = set(doms)

    matrix = {}
    for domain in dom_set:
        sublist = [item for item in urls if get_domain(item[0]) == domain]
        # print sublist
        random.shuffle(sublist)
        if len(sublist) in matrix:
            matrix[len(sublist)][domain] = sublist
        else:
            matrix[len(sublist)] = {}
            matrix[len(sublist)][domain] = sublist

    # print matrix.keys()

    map_vector = []

    for key in matrix:
        map_vector += [key] * key * len(matrix[key])
        map_vector = sorted(map_vector, key=int)

    # print map_vector

    proportionally_sorted = []

    for pos in map_vector:
        if pos in matrix:
            rand_pos = [pos]
            for key in matrix.keys():
                if key % pos == 0:
                    rand_pos.append(key)
            for position in rand_pos:
                rand_keys = matrix[position].keys()
                random.shuffle(rand_keys)
                for key in rand_keys:
                    rand = rand_keys.pop()
                    if matrix[position][rand]:
                        proportionally_sorted.append(matrix[position][rand].pop())
                        break
                    else:
                        continue

    return proportionally_sorted

I don't really understand what your code is supposed to do but I can see some room for improvement so let's go!

Style

Your code looks good and PEP 8 seems to be respected. I find the spacing in the argument lists a bit unusual but he... Also, your functions probably deserves some documentation like docstrings for instance.

Improvements

domain = '' is not needed here.

In :

    random.shuffle(sublist)
    if len(sublist) in matrix:
        matrix[len(sublist)][domain] = sublist
    else:
        matrix[len(sublist)] = {}
        matrix[len(sublist)][domain] = sublist

You don't need to call len over and over again.

    random.shuffle(sublist)
    leng = len(sublist)
    if leng in matrix:
        matrix[leng][domain] = sublist
    else:
        matrix[leng] = {}
        matrix[leng][domain] = sublist

Then, you could remove the duplicated logic :

    random.shuffle(sublist)
    leng = len(sublist)
    if leng not in matrix:
        matrix[leng] = {}
    matrix[leng][domain] = sublist

But the part with the test and the empty dict could be done automatically with defaultdicts.

In :

def proportional_sort( urls ):
    doms = [get_domain(url[0]) for url in urls]
    dom_set = set(doms)

    matrix = {}
    for domain in dom_set:
        sublist = [item for item in urls if get_domain(item[0]) == domain]

it seems like you are using the wrong data structure. You want to iterate over domains only and only once and then process the corresponding urls. It would be better to define a dictionnary mapping domains to list of urls once so that you don't have to call get_domain many times in many places. You have different ways to do this, the best involves setdefault :

dom_dict = {}
for url in urls:
    dom_dict.setdefault(get_domain(url[0])).append(url)

Then, your code becomes (not tested):

matrix = {}
for domain, sublist in dom_dict.iteritems():
    random.shuffle(sublist)
    leng = len(sublist)
    if leng not in matrix:
        matrix[leng] = {}
    matrix[leng][domain] = sublist


Ping-pong game with JavaScript and Canvas I have created my first ping-pong game with JavaScript and Canvas. I will be glad if anybody can tell me how to optimize the code and functionality.

https://github.com/nikitalarionov/js-pong

First collision detection:

//Function to check collision between ball and one of
//the paddles
function collides(b, p) {

    if(b.x + ball.r >= p.x + p.w && b.x - ball.r <= p.x + p.w) {

        if (b.y + b.r >= p.y && b.y + b.r <= p.y + p.h && b.x - b.r <= p.x) {
            paddleHit = 1;
            if(b.x < W/ 2) {
                hit++;
            } else if (b.x > W / 2) {
                hit2++;
            }
            return true;
        }
        else if(b.y - b.r <= p.y && b.y - b.r >= p.y - p.h && b.x + b.r >= p.x) {
            paddleHit = 2;
            if(b.x < W/ 2) {
                hit++;
            } else if (b.x > W / 2) {
                hit2++;
            }
            return true;
        }
        else return false;

    }
}

I experience bad performance when the ball hits an angle of one of the paddles:

// Function that updates everything, score, positions, main game logic
function update(){
    // Move the padles
    for(var i = 0; i <= padles.length; i++) {
        var p = padles[i];
        if (i === 0 && players[0].moveUp) {
            if (p.y <= 0) {
                p.y = 0;
            }
            else {
                                    // is it how i move left paddle
                                    // it is doesn't work good like a mousemove
                                    // animations is slowly, i dont know how to fix it
                p.y -=25;
            }
        }
        if (i === 0 && players[0].moveDown) {
            if (p.y + p.h >= H) {
                p.y = H - p.h;
            }
            else {
                p.y += 25;
            }
        }
        if (mouse.y && i === 1) {
            if (p.y + p.h >= H && mouse.y > p.y) {
                p.y = H - p.h;
            }
            else {
                p.y = (mouse.y -50) - p.w / 10;
            }
        }
    }

            // ... some code

}

There I have very lazy animation and moving of the left paddle. I use keys for it outside of the animation cycle:

    // Add Global Event to handle keyboards buttons
window.addEventListener('keydown', function(e) {
    if (e.keyCode === 87) {
        players[0].moveUp = true;
    } else
    if (e.keyCode === 83) {
        players[0].moveDown = true;
    }
}, false);

window.addEventListener('keyup', function(e) {
    if (e.keyCode === 87) {
        players[0].moveUp = false;
    } else
    if (e.keyCode === 83) {
        players[0].moveDown = false;
    }
}, false);

From a once-over,

Short 1 letter variables are terrible ( except for x and y ), b, p and W are just terrible
Also please spellcheck your variables: padles -> paddles
You should only detect collision when the ball is going to the left and gets in the danger-zone or when it is going to the right and getting in the danger-zone. So instead of doing 8 accesses, 1 AND and 4 sums (if(b.x + ball.r >= p.x + p.w && b.x - ball.r <= p.x + p.w) {) you should rather do something like

if( deltaX < 0 && ball.x < someLimit ){
  testCollision( ball , leftPaddle );
} else if( ball.x > someOtherLimit  ) {
  testCollision( ball , rightPaddle );
}

Where deltaX is the amount of pixels the ball is moving over the X axis, this should make paddle collision a lot more efficient
Please don't use magical constants, in this case I see 25 all over the place
Same for the keycodes, you should use constants for those


Finding duplicates between n Sets I have n Objects,
Each Object has a Set of "nested" "Neighboring Objects".
I need to check if there are duplicates between the "Neighboring Objects" Sets (there are no duplicates inside a single Set of "Neighboring Objects", but there might be between Sets).

At the end I need a new List of shared "Neighboring Objects"

In order to qualify, an Object must be present in every "Neighboring Set"

public List<Object> getOverlapingNeighbors(Object... d) {

    Objects.requireNonNull(d);

    List<Object> overlapingNeighbores = new ArrayList<Object>();

    Set<Object> neighbores = d[0].getNeighboringObjects(); // returns the "Neighboring Objects" Set

    for (Object candidate : neighbores) {

        boolean flag1 = true;

        for (int i = 1; i < d.length; i++) {

            boolean flag2 = false;

            for (Object other : d[i].getNeighboringObjects()) {
                if (candidate.equals(other)) {
                    flag2 = true;
                    break;
                }
            }

            if (!flag2) {
                flag1 = false;
                break;
            }

        }

        if (flag1) {
            overlapingNeighbores.add(candidate);
        }

    }

    return overlapingNeighbores;
}

I don't feel comfortable with this approach...
I was hoping some one smarter has implemented a way of doing this better

First off, I'm assuming Object isn't java.lang.Object, but your own class. In that case you really should find a better name for it. Even if java.lang.Object didn't exist, "Object" is a terribly generic name giving absolutely no clue on what it represents.

The variable names flag1 and flag2 are beyond terrible, plus I believe you only need one boolean flag, if at all. Reading the algorithm gave me a headache, so I gave up after a while, so I can't say if it does what it should correctly.

Considering the method is working with sets it should return a Set and not a List.

Is the use of variable arguments really a valid usage pattern? That is usually only sensible if you call the method with separate arguments in code. This seems more like a situation where you have a Collection of objects to start with.

d is a bad variable name (again).

You should check if d actually contains at least one object (and return an empty list/set, if not), otherwise the user of the method will get an unhelpful IndexOutOfBoundsException.

In your method you only access the "neighboring objects" property of your Object and no other property. Instead of giving the method a list/array of your Objects, it would make sense to instead just give it a list/array of the sets of neighboring objects.

As @markspace says, the algorithm you are describing seems to simply be the intersection of all sets, which you can get using the method .retainAll() of Set.

Based on this the simplest attempt would be something like this (using Java 8 Streams):

// This first method is only needed if you really need the varargs:
public static Set<Object> getOverlapingNeighbors(Object... objects) {
   return getOverlapingNeighbors(Arrays.asList(d));
}

public static Set<Object> getOverlapingNeighbors(List<Object> objects) {
   return intersectionOf(objects.stream().map(Object::getNeighboringObjects).collect(Collectors.toList()));
}

// These are two generic methods that calculate the intersection of Sets of any (java.utils.)Objects.
// It could/should be placed in a general utility class.
public static <T> Set<T> intersectionOf(Collection<Set<T>> sets) {
    // It may be useful to first sort the list of sets by size, to optimize
    // runtime.
    // It is not the most optimal implementation, since it creates a new HashSet
    // in each call of intersectionOf(Set<T> a, Set<T> b)
    return sets.stream().reduce((r, s) -> intersectionOf(r, s)).orElse(Collections.emptySet());
}

public static <T> Set<T> intersectionOf(Set<T> a, Set<T> b) {
    Set<T> newA = new HashSet<>(a);
    newA.retainAll(b);
    return newA;
}


Higher lower game in Ruby I finished the Ruby chapter in Seven Languages in Seven Weeks. It tries to make you familiar with the core concepts of several languages rather quickly. Dutifully I did all exercises, but most likely they can be improved to be more Ruby-like. I'll post my code samples one by one, so I can apply things learned in previous questions to later questions.

Day 1

  Write a program that picks a random number. Let a player guess the
  number, telling the player whether the guess is too low or too high.

range = (0..10)
to_guess = range.min + rand(range.max - range.min)
guessed = false

while !guessed
    puts "Guess a number, between #{range.min} and #{range.max}"
    guess = gets
    int = guess.to_i
    if int == to_guess
        puts 'Correct!'
        guessed = true
    else
        puts int > to_guess ? 'Lower' : 'Higher'
    end
end

After sepp2k's comments:

class Range
  def size
    self.end - self.begin
  end
end

range = 0..10
to_guess = range.begin + rand(range.size)
guessed = false

until guessed
  puts "Guess a number, between #{range.begin} and #{range.end}"
  guess = gets
  int = guess.to_i
  if int == to_guess
    puts 'Correct!'
    guessed = true
  else
    puts int > to_guess ? 'Lower' : 'Higher'
  end
end

A couple of minor things:

First of all the convention in the ruby world is to use 2 spaces for indentation, not 4. It doesn't really matter much, but it's generally easier to use the style conventions that everyone uses unless you have a reason not to.

range = (0..10)

You don't actually need the parentheses here. Parentheses are not part of range syntax - the reason you usually see ranges wrapped in parentheses is that you can't call methods on ranges without them (because 0..10.foo would be interpreter as 0..(10.foo)).

to_guess = range.min + rand(range.max - range.min)

You should use begin and end or first and last instead of min and max. In ruby 1.8.7 min and max are inherited from Enumerable and will iterate the entire range in order to find the minimum/maximum, making them O(n). Only in 1.9 (in 1.9.2 at least) they're overridden to work in O(1) time. begin and end work in O(1) time in all ruby versions.

I would also consider putting this into its own method as it seems like it might come in handy more than once.

while !guessed

I would write that as until guessed as that reads a bit nicer to me.


1, 2, Fizz, 4, Buzz: FizzBuzz I just recently started working on python (interesting language, actually), and, as I always do when I learn a new language (with the exception of BrainFuck, that's too hard), I write a FizzBuzz program.

I notice there is no error-checking, so my program would have problems with incorrect input, but please ignore that as I haven't gotten to that part yet.

Code:

def getString(num, fizz, buzz):
    if num % (fizz * buzz) == 0:
        return "FizzBuzz"
    elif num % fizz == 0:
        return "Fizz"
    elif num % buzz == 0:
        return "Buzz"
    else:
        return num

def fizzbuzz(maxNum, fizz, buzz):
    num = 1;
    while num <= maxNum:
        print(getString(num, fizz, buzz))
        num += 1

fizz = int(input("Enter the number to Fizz: "))
buzz = int(input("Enter the number to Buzz: "))
maxNum = int(input("Enter the maximum number: "))
fizzbuzz(maxNum, fizz, buzz)

The code will take a fizz, buzz, and a maxNum as input, and will output, all the fizzing and buzzing the code is doing.

Concerns:

Does it follow Python conventions?

getString and maxNum should be get_string and max_num, by PEP 8 recommendation.
getString sometimes returns a number, and sometimes returns a string.  This violates the expectation set up by the function name.  Also, a function that is indecisive about its return type is harder to work with.
num = 1; ← No semicolons in Python, please.
The fizzbuzz loop is written idiomatically as for num in range(1, maxNum + 1): …


Speed Efficiency of Decompression Algorithm I've rewritten a piece of Javascript in Python 3.7 that decompresses a file compressed in a specific format. The project that I got this from is available here.
The code I've come up with is as close an analog as I could interpret (I'm not the best at Javascript).
def decompress_lz2(data):
    global loop_count
    lb_len = 0
    lb_dist = 0
    escape = 0x16

    off_input = 0

    output = b''

    while off_input < len(data):
        loop_count += 1
        if lb_len:
            off_output = len(output) - lb_dist

            repeat = max(0, off_output + lb_len - len(output))

            chunk = output[off_output:off_output + lb_len - repeat]
            output += chunk

            if repeat:
                repeat_chunk = bytes([chunk[-1]]) * repeat
                output += repeat_chunk

            lb_len = 0

        if escape:
            chunk = data[off_input:off_input + escape]
            output += chunk
            off_input += escape
            escape = 0

        flag = data[min(off_input, len(data) - 1)]
        off_input += 1

        lb_len = flag >> 5

        if lb_len:
            if lb_len == 7:
                while True:
                    next_ = data[off_input]
                    off_input += 1
                    lb_len += next_
                    if next_ != 0xff:
                        break

            lb_len += 2

            lb_dist = (flag & 0x1F) << 8
            lb_dist += (1 + data[off_input])
            off_input += 1

            if lb_dist == 0x2000:
                lb_dist += (data[off_input] << 8)
                off_input += 1
                lb_dist += data[off_input]
                off_input += 1

        else:
            escape = flag + 1

    return output

where data is a byte string read in from a file opened in binary mode. My code and the original code both produce the same output, but where the original code takes only a few seconds to execute, mine takes ~10 minutes on the same file. Testing with multiple files yields similar benchmarks. My specific efficiency question is: What can I do to increase the speed of execution of this script on the same system while maintaining output accuracy?
I'm open to the idea of multithreading/multiprocessing though I don't think it's possible due to the nature of this compression type.
Example file, though it's very small and runs quickly on both implementations. It must be fed to decompress_lz2 as bytes.

I can't test it at the moment, but I suspect that the culprit is
output += chunk

in a couple of places. This line potentially has O(n^2) complexity because of copying output to a new place in memory that has room to append chunk to it.  It would be more efficient to append chunk to a list and then use b''.join() at the end to concatenate all the chunks.
def decompress_lz2(data):
    global loop_count
    lb_len = 0
    lb_dist = 0
    escape = 0x16

    off_input = 0

    output = []               # <-- make output a list

    while off_input < len(data):
        loop_count += 1
        if lb_len:
            off_output = len(output) - lb_dist

            repeat = max(0, off_output + lb_len - len(output))

            chunk = output[off_output:off_output + lb_len - repeat]
            output.append(chunk)  # <-- changed '+=' to '.append()'

            if repeat:
                repeat_chunk = bytes([chunk[-1]]) * repeat

                output.append(repeat_chunk)  # <-- changed '+=' to '.append()'

            lb_len = 0

        if escape:
            chunk = data[off_input:off_input + escape]
            output.append(chunk)  # <-- changed '+=' to '.append()'
            off_input += escape
            escape = 0

        flag = data[min(off_input, len(data) - 1)]
        off_input += 1

        lb_len = flag >> 5

        if lb_len:
            if lb_len == 7:
                while True:
                    next_ = data[off_input]
                    off_input += 1
                    lb_len += next_
                    if next_ != 0xff:
                        break

            lb_len += 2

            lb_dist = (flag & 0x1F) << 8
            lb_dist += (1 + data[off_input])
            off_input += 1

            if lb_dist == 0x2000:
                lb_dist += (data[off_input] << 8)
                off_input += 1
                lb_dist += data[off_input]
                off_input += 1

        else:
            escape = flag + 1

    return b''.join(output)  # <-- concatenate the chunks


Evaluating algebra expression using an auxiliary VB class compiled on the fly and consumed in a C# project I want to create algebra evaluator but I don't want to write my own parser because it takes much time to learn.
I don't like algebra expression in C# because it does not look natural compared to VB counterpart. For example, "x^2+1" in VB must be written as "Math.Pow(x,2)+1" in C#.
I am still a newbie in the world of programming and always interested to learn the best practices. I am always not confident with my code.

Minimal Working Example

Based on the 3  constraint given above, I tried to implement it as follows.

First, I create a template named template.vb as follows:

Imports System
Imports System.Math
Namespace AnyNamespace
    Public Class AnyClass
        Public Function AnyMethod(ByVal x As Double) As Double
            Return expression-in-x
        End Function
    End Class
End Namespace

where expression-in-x is just a place holder that will be replaced. See the next code how I replace it.

Second, I create a class named Parser.cs as follows:

using Microsoft.VisualBasic;
using System;
using System.CodeDom.Compiler;
using System.IO;
using System.Reflection;
using System.Text;

namespace Mathematics
{
    public static class Parser
    {
        static string expression;
        static object obj;
        static MethodInfo mi;

        public static string Expression
        {
            get
            {
                return expression;
            }
            set
            {
                expression = value;

                string source;

                using (StreamReader sr = new StreamReader("template.vb"))
                {
                    source = sr.ReadToEnd().Replace("expression-in-x", expression);
                }

                CompilerParameters cps = new CompilerParameters();
                cps.GenerateExecutable = false;
                cps.GenerateInMemory = true;

                CompilerResults crs = (new VBCodeProvider()).CompileAssemblyFromSource(cps, source);

                if (crs.Errors.Count > 0)
                {
                    StringBuilder sb = new StringBuilder();
                    foreach (CompilerError ce in crs.Errors)
                    {
                        sb.Append(string.Format("Error Number : {0}, Line : {1}, Message : {2}.\n", ce.ErrorNumber, ce.Line, ce.ErrorText));
                    }
                    throw new Exception(sb.ToString());
                }
                else
                {
                    Assembly a = crs.CompiledAssembly;
                    obj = a.CreateInstance("AnyNamespace.AnyClass");
                    mi = obj.GetType().GetMethod("AnyMethod");
                }
            }
        }

        public static double Evaluate(double x)
        {
            if (expression == null)
                throw new Exception("Unitialized expression.");
            try
            {
                return (double)mi.Invoke(obj, new object[] { x });
            }
            catch (TargetInvocationException error)
            {
                throw error;
            }
            catch (Exception error)
            {
                throw error;
            }
        }
    }
}

Last, I test the code as follows:

using Mathematics;
using System;

namespace Tester
{
    class Program
    {
        static void Main(string[] args)
        {
            Parser.Expression = "x^2+1";
            for (int x = 0; x < 10; x++)
                Console.WriteLine(Parser.Evaluate(x));
            Console.ReadKey();
        }
    }
}

Questions

Is what I did above recommended? If not, could you give me a direction or suggestion what should I improve it or whatever to make it much better?

public static class Parser

Why is this class static? When you have a class with some state, you should almost never make that state static. For example, you might be very surprised when you try using this code from multiple threads.

using (StreamReader sr = new StreamReader("template.vb"))
{
    source = sr.ReadToEnd().Replace("expression-in-x", expression);
}

You could have used File.ReadAllText() to make this simpler.

CompilerParameters cps = new CompilerParameters();
cps.GenerateExecutable = false;
cps.GenerateInMemory = true;

Using var and object initializer, you can shorten this to:

var cps = new CompilerParameters { GenerateExecutable = false, GenerateInMemory = true };

Also, cps is not a great name, don't shorten names unnecessarily.

obj = a.CreateInstance("AnyNamespace.AnyClass");
mi = obj.GetType().GetMethod("AnyMethod");

Instead of object and MethodInfo, you could store the method as a delegate:

Func<double, double> compiledFunction;

…

var obj = a.CreateInstance("AnyNamespace.AnyClass");
var mi = obj.GetType().GetMethod("AnyMethod");
compiledFunction =
    (Func<double, double>)Delegate.CreateDelegate(typeof(Func<double, double>), obj, mi);

…

return compiledFunction(x);

As another advantage, this is likely going to be faster, since it's not using reflection for every invocation of Evaluate().


Creating lists of events (pitches, velocities, delta-times, durations) from a MIDI track I am trying to understand good design patterns in Python and I cannot think of a way to break this huge function into smaller parts without making the code cluttered, overly complex or plain ugly.

I didn't want to clutter my question by posting the whole file. This function itself is already very large, but the class has only two methods: parse_midi() and generate_midi(file_name, file_length).

pitches, velocities, deltas, durations, and intervals are all MarkovChain objects. MarkovChain is a simple class with methods: add_event(event), generate_markov_dictionary(), and get_next_event(previous_event). MarkovChain.src_events is a list of events to generate the Markov chain from. It is a simple implementation of first order Markov chains.

def parse_midi(self):
    # on_notes dictionary holds note_on events until corresponding note_of event is encountered
    on_notes = {}
    time = 0
    previous_pitch = -1
    tempos = []
    delta = 0
    for message in self.track_in:
        time += message.time
        delta += message.time
        # There are also MetaMessages in a midi file, such as comments, track names, etc.
        # We just ignore them
        if isinstance(message, mido.Message) and message.type in ["note_on", "note_off"]:
            # some midi files use note_on events with 0 velocity instead of note_oof events
            # so we check if velocity > 0
            if message.velocity > 0 and message.type == "note_on":
                on_notes[message.note] = time
                self.pitches.add_event(message.note)
                self.velocities.add_event(message.velocity)
                self.deltas.add_event(delta)
                delta = 0
                if previous_pitch == -1:
                    self.intervals.add_event(0)
                else:
                    self.intervals.add_event(message.note - previous_pitch)
            else:
                # KeyError means note_off came without a prior associated note_on event!"
                # Just ignore them
                with ignored(KeyError):
                    self.durations.add_event(time - on_notes[message.note])
                    del on_notes[message.note]

            previous_pitch = message.note
        # Tempo might be many tempo changes in a midi file, so we store them all to later calculate an average tempo
        elif message.type == "set_tempo":
            tempos.append(message.tempo)
        elif message.type == "time_signature":
            self.time_signature = self.TimeSignature(message.numerator, message.denominator,
                                                     message.clocks_per_click, message.notated_32nd_notes_per_beat)
    # some tracks might be aempty in a midi file. For example they might contain comments as track name, and no note events
    if len(self.pitches.src_events) == 0:
        print("There are no note events in track {}!\n"
              "The file has {} tracks. Please try another one.".format(self.selected_track, self.num_tracks))
        exit(1)
    # a midi file might not contain tempo information at all. if it does, we calculate the average
    # else we just assign a default tempo of 120 bpm
    try:
        self.average_tempo = int(sum(tempos) / len(tempos))
    except ZeroDivisionError:
        self.average_tempo = mido.bpm2tempo(120)

Your notion of average tempo makes little sense.  A track with four minutes of ♩=120 followed by a 12-second coda of ♩=60 would have a reported average tempo of 90.  A more reasonable average would be to divide the total number of beats by the elapsed time.

$$\frac{120 \frac{\textrm{beats}}{\textrm{min}} × 4\   \textrm{min} +
         60 \frac{\textrm{beats}}{\textrm{min}} × 0.2\ \textrm{min}}
       {4.2\ \textrm{min}} \approx 117 \frac{\textrm{beats}}{\textrm{min}}
$$


Prim's algorithm via Priority Queues to print the minimum spanning tree of an undirected graph Here's my attempt, I believe the runtime is O(V*(ElogE + log E)) since the while loop runs V times and it takes ElogE + log E to do the priority queue operations inside the loop.
class Edge implements Comparable<Edge> {
  T source;
  T destination;
  int weight;

  public Edge(T source, T destination, int weight) {
     this.source = source;
     this.destination = destination;
     this.weight = weight;
  }

  public int compareTo(Edge other) {
    return this.weight - other.weight;
    }
}

public void printMSTPrims(Map<T, List<Edge> > adjacencyList) {
        // Records all visited destinations.
        Set<T> visited = new HashSet<>();
        Queue<Edge> edges = new PriorityQueue<>();
        T currentNode = adjacencyList.entrySet().iterator().next().getKey();
        visited.add(currentNode);
        // Run until we've visited all vertices
        while (visited.size() < adjacencyList.size()) {

            // Take all edges from current node and add to the PQ.
            for (Edge edge: adjacencyList.get(currentNode)) {
                edges.add(edge);
            }

            // Pick the smallest edge to a destination node not already visited.
            Edge edge = edges.remove();
            while (!edges.isEmpty() && visited.contains(edge.destination)) {
                edge = edges.remove();
            }

            // Found an eligible edge, print its contents. This edge does not have to necessarily start from the currentNode.
            System.out.println(edge.source + "--" + edge.weight + "--" + edge.destination);
            // Go next to this destination vertex.
            currentNode = edge.destination;

            //Now that you've reached this edge as a destination, record it.
            visited.add(currentNode);
        }

}

PS. I assume the graph does not have self-loops and double-edges.

For who is not familiar with Prim's algorithm: it finds a minimum spanning tree for a weighted undirected graph.

My suggestions:

Generics: the class Edge should be declared as Edge<T> or it won't compile as is. Or is it an inner class? Also the generic is missing in Comparable and the method compareTo.
compareTo: typically, for primitive types is better to use <,>, and return -1,0 or 1. In your case, compareTo could overflow the integer with a negative weight. You can change it from:
public int compareTo(Edge other) {
  return this.weight - other.weight;
}

To:
public int compareTo(Edge other) {
  return Integer.compare(this.weight,other.weight);
}

addAll instead of for-loop: adding all edges to the queue can be done with addAll. From:
for (Edge edge: adjacencyList.get(currentNode)) {
    edges.add(edge);
}

To:
edges.addAll(adjacencyList.get(currentNode));

Testing: the method printMSTPrims is hard to test. Would be better to have a method mstPrims that returns a result and then print it with another method. In that case, would be easier to test mstPrims.
Naming: the name edges is a bit generic, an alternative can be edgeQueue or just queue.

Your final assumption:

PS. I assume the graph does not have loops and self-edges.

So a tree? A (connected) acyclic undirected graph is a tree. Anyway, looking at your method I don't think there should be problems even if there are cycles.


Validating that all open/close parentheses are correctly matched It returns true for:

a*(b+c)
()()
(())
((!!(123(x))))

and returns false for:

(a((b+c))
)()(
))((
(rsd+3)*(-3-a))

As you can see, the logic is simple. Can you confirm for me that it works for all-cases? I mean the logic isn't flawed.

It must be efficient and by that I mean not go over the linked list more than once.

public boolean parentheses()
{
    return parentheses(0,_head);
}

public boolean parentheses(int p, CharNode current)
{
    if (current == null)
    {
        if (p == 0)
         return true;
        else
         return false;
    }
    else
    {
        if(current.getData() == ')' && p == 0)
         return false;
        else if (current.getData() == '(')
         return parentheses(p+1,current.getNext());
        else if (current.getData() == ')')
         return parentheses(p-1,current.getNext());
        else
         return parentheses(p,current.getNext());
    }
}

Short Answer
Yes, I believe it will be functional....
Dubious Recursion
Calling this method recursive is a problem. It is not a recursive method. Just because it is calling itself does not mean it is a recursive function. What you have is a bad loop. From Wikipedia:

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself).

Your code does not have a base case and a recursive case..... unless you consider current==null to be the base case... but that is just the recursion-terminating statement.
What I mean, is that, consider this loop:
boolean checkParenthesis(CharNode current) {
    int p = 0;
    while (current != null) {
        if (current.getData() == '(') {
             p++;
        } else if (current.getData() == ')') {
             p--;
        }
        if (p < 0) {
            return false;
        }
        current = current.getNext();
    }
    return p == 0;
}

That is how you can write the code iteratively.
Now, if I change it just like this:
boolean checkParenthesis(CharNode current, int p) {
    if (current == null) {
        return p == 0;
    } else {
        if (current.getData() == '(') {
             p++;
        } else if (current.getData() == ')') {
             p--;
        }
        if (p < 0) {
            return false;
        }
        return checkParenthesis(current.getNext(), p);
    }
}

What I am trying to show here is that you essentially have a while-loop that uses the stack to check the end condition.
For a long input, your code will fail with a stack-overflow exception.
Iteration
When you have linked data like you do, the natural solution is to use iteration.
The example I have above shows how it can be done.
I am not sure why you are using recursion at all.
Actual Recursion
If you really want to use recursion, the right way to do it would be to recurse down when you encounter a ( value, and recurse up when you encounter a )
Each recursive level will make sure it has a matching parenthesis.... it will look something like:
// used if there is an error.
private static final CharNode ERRORNODE = new CharNode(....);
private static final CharNode ENDOFDATA = new CharNode(....);

boolean checkParenthesis(CharNode current) {
    current = matchParenthesis(current, true);
    if (current == ERRORNODE) {
        return false;
    }
    // current could be null if there was an unexpected ')' as the very last character.
    return current == ENDOFDATA;
}

CharNode matchParenthesis(CharNode current, boolean toplevel) {
    while (current != null && current != ENDOFDATA && current != ERRORNODE) {
        if (current.getData() == ')') {
            // found our matching brace
            return current.getNext();
        }
        if (current.getData() == '(') {
            // need to start a sub-level check for a matching brace.
            current = matchParenthesis(current.getNext(), false);
        } else {
            current = current.nextData();
        }
    }
    if (current == null) {
        return toplevel ? ENDOFDATA : ERRORNODE;
    }
    return current;
}


Randomly generate set of size M from array of size N The following algorithm attempts to randomly generate a set of size M from an array of size N. It is not based on Knuth Fisher Yates shuffle, but could someone verify its correctness?

import random

def random_m(arr, m):
    if len(arr) <= m:
        return arr

    for i in range(m):
        rand = random.randint(i, len(arr)-1)
        arr[i], arr[rand] = arr[rand], arr[i]

    return arr[:m]

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

The above runs in\$\ O(m)\$ where as the method based on Knuth Fisher Yates runs in \$\ O(n)\$.

Your understanding of Fisher-Yates is incorrect: this is precisely Fisher-Yates. It merely differs from some implementations in accumulating at the start of the array rather than the end. As such the main part of the body is correct (and uniform, modulo artefacts of the RNG).

The alternative way round, accumulating at the end, would be

    for i in range(m):
        j = len(arr)-1-i
        rand = random.randint(0, j)
        arr[j], arr[rand] = arr[rand], arr[j]

    return arr[-m:]

However, I find the special case a bit confusing. if len(arr) < m I would expect an exception, and since that isn't the case I think there should be a comment to document the behaviour.


Constraint Algorithm Optimization in C++ I'm especially interested in ways to further optimize a constraint algorithm. So far I've switched to SIMD sse4 vector operations which nearly doubled the performance. I'm hoping there is more performance to squeeze out that I simply don't see.

Here is the algorithm:

FVector4 rest(REST_DISTANCE); // Set the constant simd vector outside the loop
FVector4 stiffness(STIFFNESS);

for (int i = 0; i < TEST_SIZE; i++)
{
    const auto& constraint = Constraints[i];
    auto& position1 = Particle[constraint.first].Position;
    auto& position2 = Particle[constraint.second].Position;

    for (int j = 0; j < ITERATION_COUNT; j++)
    {
        auto delta = position2 - position1;
        auto distance = delta.norm();

        auto correctionDistance = (distance - rest) / distance;
        auto pCorrection = correctionDistance * delta * stiffness;

        position1 += pCorrection;
        position2 -= pCorrection;
    }
}

Constraints is an array of a simple struct that holds two unsigned int's, Particle is an array of FParticle structs which holds three FVector4 fields and a Fvector4 simply wraps a __m128 and provides operators and functions like norm() which utilize _mm_* intrinsic functions.

Currently the algorithm takes 55 cycles per Constraint per Iteration, this is with TEST_SIZE of 150,000 and ITERATION_COUNT at 16. I know there is performance to gain from making it parallel but I'm hoping to get more performance out of the single threaded version specifically.

I can post the actual structs if needed.

FVector4 code:

struct FVector4
{
    FVector4()
    {}
    explicit FVector4(const __m128& InitData) : Data(InitData)
    {
    }
    explicit FVector4(__m128&& InitData) : Data(InitData)
    {
    }
    explicit FVector4(float InitValue)
    {
        Data = _mm_set_ps1(InitValue);
    }
    explicit FVector4(float X, float Y, float Z, float W = 0.f)
    {
        Data = _mm_setr_ps(X, Y, Z, W);
    }

    __forceinline float& operator[](int index)
    {
        return Data.m128_f32[index];
    }
    __forceinline const float& operator[](int index) const
    {
        return Data.m128_f32[index];
    }
    __forceinline __m128 squaredNorm() const
    {
        return _mm_dp_ps(Data, Data, 0x7F);
    }
    __forceinline __m128 norm() const
    {
        auto sqNorm = squaredNorm();
        return _mm_mul_ps(sqNorm, _mm_rsqrt_ps(sqNorm));
    }
    __forceinline __m128 normalized() const
    {
        auto dp = _mm_dp_ps(Data, Data, 0x7F);
        dp = _mm_rsqrt_ps(dp);
        return _mm_mul_ps(Data, dp);
    }
    __forceinline void normalize()
    {
        Data = normalized();
    }
    __m128 Data;
};

Operators as used in the algorithm:

__forceinline FVector4 operator-(const FVector4& a, const FVector4& b)
{
    return FVector4(_mm_sub_ps(a.Data, b.Data));
}
__forceinline FVector4 operator*(const FVector4& a, const FVector4& b)
{
    return FVector4(_mm_mul_ps(a.Data, b.Data));
}
__forceinline FVector4 operator/(const FVector4& a, const FVector4& b)
{
    return FVector4(_mm_mul_ps(a.Data, _mm_rcp_ps(b.Data)));
}
__forceinline FVector4& operator+=(FVector4& a, const FVector4& b)
{
    a.Data = _mm_add_ps(a.Data, b.Data);
    return a;
}
__forceinline FVector4& operator-=(FVector4& a, const FVector4& b)
{
    a.Data = _mm_sub_ps(a.Data, b.Data);
    return a;
}

I don't know much about SSE and can't offer you any suggestions on performance right now, just a few suggestions to improve your code a little bit. Nevertheless, it looks well written and clean.

Since the default constructor does nothing, you can make it = default. That's the new syntax for such cases since C++11. It also conveys more meaning that you want a default no-op constructor.
The move constructor is pointless. An __m128 is a native type like an integer, so it fits in a CPU register. It will always be copied. You can remove this constructor overload.
The other constructor that takes a __m128 by const reference is probably less efficient that it could be. Again, __m128 can be passed via registers, so taking by reference will instead pass a pointer that has to be dereferenced. I bet you it is generating more code than if you'd just pass it by value.
The constructor that takes the four X,Y,Z,W floats doesn't have to be explicit. For any constructor taking more than one argument that has no default, explicit doesn't make sense. It is only meaningful when the constructor has a single required argument and you want to force writing something like func(FVector{42.0f}). If the constructor takes more than one argument, it can't be implicitly called.
const float& operator[](int index) const should instead return by value. Again you are forcing the compiler to generate indirection code when the value can be cheaply passed in a register.
I would also recommend asserting in the array subscript operators to ensure index in >= 0 && < 4.
If you decide to port this code in the future, __forceinline is going to be a problem. It is a Microsoft extension. I would #define a portable macro for it instead or just use standard inline. __forceinline is no guarantee of inlining, despite the misleading name. It just provides a slightly stronger hint to the compiler than inline.
__m128 is somewhat an ugly type to pass around, with those double underscores. In your place, I would declare some alias for it, perhaps simd_t or something. It might even be of value in the future if you decide to port FVector to some other SIMD set like AltiVec.


Cleaner method of doing IF Basically, I'm performing an if statement on an array based on the returned value

<?php
if($array[1]>10000 AND $array[1]<50000){
        $selling = $array[1] - 250;
    }
    elseif($array[1]>50000 AND $array[1]<100000){
        $selling = $array[1] - 500;
    }
    else{
        $selling = $array[1] - 100;
    }
    $buying = $array[1] - 1000;

    if($array[1]>=10000){
        $buying = $buying-1000;
        if($array[1]>=20000){
            $buying = $buying-1000;
            if($array[1]>=30000){
                $buying = $buying-1000;
            }
                if($array[1]>=40000){
                    $buying = $buying-1000;
                }
                    if($array[1]>=50000){
                        $buying = $buying-750;
                    }
                        if($array[1]>=60000){
                            $buying = $buying-500;
                        }
                            if($array[1]>=70000){
                                $buying = $buying-500;
                            }
        }
    }
?>

As you can see it's VERY messy, would anyone be able to point me in the correct direction for cleaning this up please?

I seem to get the feeling you are either not comfortable using maps as others have suggested here...so why not throw in a switch instead?

$volume = $array[1];

if($volume > 10000 && $volume < 50000){
    $selling = $volume - 250;
} else if($volume > 50000 && $volume < 100000){
    $selling = $volume - 500;
} else {
    $selling = $volume - 100;
}

$buying = $volume - 1000;

switch($volume){
    case 10000:
    case 20000:
    case 30000:
    case 40000:
        $buying = $buying - 1000; break;
    case 50000:
        $buying = $buying - 750; break;
    case 60000:
    case 70000:
        $buying = $buying - 500; break;
    default:
        $buying = $buying;
}

REVISIT 01/26/2015: Revisiting this to say that I would now rewrite this code as follows:

function bound_check($bounds, $bound_check, $default_value) {
    $return_data = NULL;
    foreach($bounds as $bound){
        if($bound_check >= $bound[0] && $bound_check <= $bound[1]){
            $return_data = $bound_check - $bound[2];
        }
    }
    return $return_data ?: $default_value;
}

$selling_bounds = [
    [10000, 50000, 250],
    [50000, 100000, 500],
];

$buying_bounds = [
    [10000, 40000, 1000],
    [50000, 50000, 750],
    [60000, 70000, 500]
]

$selling = bound_check($selling_bounds, $array[1], $volume - 100);
$buying = bound_check($selling_bounds, $array[1], $volume - 1000);


Pythagorean number decomposition I have a pretty interesting problem that I'm trying to solve, and I am kind of stuck.

I want to count the triplets of distinct combinations a, b, c, that are smaller than LIMIThave the following properties:

a >= b, a >= c, and let's note m = a + b (a, b are integer)
a and m are the smallest 2 numbers in a Pythagorean triplet (a^2 + m^2 = x^2). m can be bigger than a, but a has to be larger than b or c

Here is the code I have so far. First, I generate all Pythagorean tripplets (of which I only use the first 2). The smallest one should be under the limit, but the largest one can be above the limit.

LIMIT = 10
pyt = {}

for m in xrange(1, LIMIT):
    for n in xrange(m + 1, LIMIT):
        k = 1
        a = n ** 2 - m ** 2
        b = 2 * m * n
        if (m - n) % 2 == 0 or gcd(m, n) != 1:
            continue

        while True:
            temp_a = a * k
            temp_b = b * k
            max_pyt = max(temp_a, temp_b)
            min_pyt = min(temp_a, temp_b)
            # I only need the minimum to be smaller than the LIMIT
            # but the maximum can't be larger than 2*LIMIT (check below)
            if min_pyt > LIMIT:
                break
            pyt[min_pyt, max_pyt] = 1
            k += 1

Once I have them, I just loop through them, and count the possible combinations that can be generated.

For example:

# pythagorean numbers: 6, 8 => (6^2 + 8^2 = 10^2)
# we can generate the numbers:
# 1, 5, 8 | 2, 4, 8 | 3, 3, 8 (when decomposing 6)
# 6, 2, 6 | 6, 3, 5 | 6, 4, 4 (when decomposing 8, although 6, 1, 7 are not good, the largest of the 3 needs to be a member of the Pythagorean triplet )

counter = 0
print pyt
for a, b in pyt:
    # if half of b is bigger than the limit, just continue
    temp = b // 2
    if temp >= LIMIT:
        continue
    elif b < LIMIT:
        # a is smaller than b, so any unordered combination of numbers with the sum a
        # will be good (4 = 1 + 3 or 4 = 2 + 2, 5 = 1 + 4, 5 = 2 + 3 - ie // works)
        counter += (a // 2)

    # at this point we know that temp (half of b) is not higher than the limit
    # and if it's less than a, there are combinations to be counted
    if temp <= a:
        # with the limit 10, we can have the following situation:
        # a = 8, b = 15, so we can count the set (8, 8, 7)
        counter += (a - temp) #
        if (a - temp) % 2 == 0:
            counter += 1

I hope I explained it well enough. The script seems to be working with lower values, but when going to higher numbers, I'm starting to miss things in limit situations, but I can't figure out what.

For example, with LIMIT = 99 I should be getting 1975, but I get 1943. Any ideas what I could be missing ? Any hint is more than welcome.

Also, since I'm still learning python, I wouldn't mind some tips on how to improve my code, and follow python coding standards.

Edit: The gcd function is from the fractions module (from fractions import gcd)

1. Missing GCD

You didn't give the code for your gcd function, so I'll assume it's something like this:

def gcd(m, n):
   """Return the greatest common divisor of positive integers m and n."""
   while n:
       m, n = n, m % n
   return m

2. Decomposition: primitive Pythagorean triples

You're having trouble finding the error here because your program consists of a single block of code. You have to run all of it in order to run any of it. It would make your program easier to debug if you split it up into functions with straightforward inputs and outputs, that can be tested individually. This technique is known as functional decomposition.

The first bit of functionality to pull out is the computation of the primitive Pythagorean triples. It's convenient to write this kind of function in the form of a generator — a function that produces its results one by one using the yield statement.

So, we could start with a function like this:

def f(LIMIT):
    for m in xrange(1, LIMIT):
        for n in xrange(m + 1, LIMIT):
            a = n ** 2 - m ** 2
            b = 2 * m * n
            if (m - n) % 2 == 0 or gcd(m, n) != 1:
                continue
            yield a, b

There are some immediate improvements that can be made:

The function needs a descriptive name and a docstring.
It's conventional to use ALL_CAPITALS only for global constants (see the Python style guide, PEP 8, for this and other recommendations).
It would be make sense to generate all three sides of the triangle (you only use two of them here, but the third one is useful for testing, and it
will come in handy in other Project Euler problems).
The continue statement can be avoided by reversing the sense of the condition.
itertools.combinations can be used to reduce the two nested loops to one.

Here's the improved code:

from itertools import combinations

def primitive_pythagorean_triples(limit):
    """Generate the primitive Pythagorean triples whose shortest side is
    no longer than 2 * limit - 3, together possibly with some other
    primitive Pythagorean triples whose shortest side is longer than
    that.

    """
    for m, n in combinations(xrange(1, limit), 2):
        if (m - n) % 2 and gcd(m, n) == 1:
            a = n ** 2 - m ** 2
            b = 2 * m * n
            c = n ** 2 + m ** 2
            yield a, b, c

The hardest part of doing this was writing the docstring. (a might be as large as (limit - 1) ** 2 - (limit - 2) ** 2 which is 2 * limit - 3.) When it's hard to write a docstring, this is often a hint that the function is poorly specified. In this case, surely it would be more convenient to pass in the actual maximum shortest side?

Let's check that these are really Pythagorean triples:

>>> all(a ** 2 + b ** 2 == c ** 2 for a, b, c in primitive_pythagorean_triples(100))
True

and have a quick look at the output:

>>> list(primitive_pythagorean_triples(8))
[(3, 4, 5), (15, 8, 17), (35, 12, 37), (5, 12, 13), (21, 20, 29), (45, 28, 53),
 (7, 24, 25), (9, 40, 41), (33, 56, 65), (11, 60, 61), (13, 84, 85)]

Does that list include all the primitives triples with shortest side no more than 13? It's hard to tell. It would be easier to read the output if each triple were sorted by side length, so that (15, 8, 17) appears as (8, 15, 17). It would also be convenient to reject triples whose shortest side is too long.

Making these changes gives us a third version of the function:

def primitive_pythagorean_triples(max_side):
    """Generate the primitive Pythagorean triples whose shortest side is
    no longer than max_side.

    """
    for m, n in combinations(xrange(1, max_side // 2 + 3), 2):
        if (m - n) % 2 and gcd(m, n) == 1:
            a = n ** 2 - m ** 2
            b = 2 * m * n
            c = n ** 2 + m ** 2
            if a < b and a <= max_side:
                yield a, b, c
            elif b < a and b <= max_side:
                yield b, a, c

And now we can take the output:

>>> sorted(primitive_pythagorean_triples(13))
[(3, 4, 5), (5, 12, 13), (7, 24, 25), (8, 15, 17), (9, 40, 41), (11, 60, 61),
 (12, 35, 37), (13, 84, 85)]

and compare it to, say, OEIS sequence A020884. This looks good so far, but to be more certain that this is correct, let's write a naïve version of the function (one that would be far too slow to solve the Project Euler problem) and compare the output of the two functions.

from math import hypot

def primitive_pythagorean_triples_slow(max_side):
    for a in xrange(1, max_side + 1):
        for b in xrange(a + 1, (a ** 2 - 1) // 2 + 1):
            c = hypot(a, b)
            if gcd(a, b) == 1 and c == int(c):
                yield a, b, int(c)

>>> sorted(primitive_pythagorean_triples(300)) == sorted(primitive_pythagorean_triples_slow(300))
True

3. Decomposition: all Pythagorean pairs

The next bit of functionality to decompose is the computation of the Pythagorean pairs. Your code looks like this:

pyt = {}
k = 1
while True:
    temp_a = a * k
    temp_b = b * k
    max_pyt = max(temp_a, temp_b)
    min_pyt = min(temp_a, temp_b)
    # I only need the minimum to be smaller than the LIMIT
    # but the maximum can't be larger than 2*LIMIT (check below)
    if min_pyt > LIMIT:
        break
    pyt[min_pyt, max_pyt] = 1
    k += 1

There are lots of small improvements we can make here:

Make it into a function we can test separately.
Write a docstring.
Generate these pairs instead of storing them in a dictionary.
Use itertools.count to simplify the loop.
Choose better names for the variables. For example, what's temporary about temp_a and why is that important? I'd prefer a name like ka to remind us that this variable holds the value k * a.

Here's the improved code:

from itertools import count

def pythagorean_pairs(max_side):
    """Generate pairs of integers (a, b), where a is the short leg and b
    the long leg of a Pythagorean triangle, and where a <= max_side
    and b <= 2 * max_side.

    """
    for a, b, _ in primitive_pythagorean_triples(max_side):
        for k in count(1):
            ka, kb = k * a, k * b
            if ka > max_side or kb > 2 * max_side:
                break
            yield ka, kb

Again, at this point it is useful to have a naïve computation of the same set of pairs, to test the faster version of the code.

def pythagorean_pairs_slow(max_side):
    for a in xrange(1, max_side + 1):
        for b in xrange(a + 1, 2 * max_side + 1):
            c = hypot(a, b)
            if c == int(c):
                yield a, b

>>> sorted(pythagorean_pairs(1000)) == sorted(pythagorean_pairs_slow(1000))
True

4. Decomposition: counting cuboids

Your code for counting the cuboids contains a lot of comments, which is a sign that it's not very clearly written. Let's pull out the body of the loop into a function and see if we can make sense of it:

def count_cuboids(a, b, LIMIT):
    """Given a Pythagorean pair (a, b), return the number of cuboids (p, q, r)
    such that 1 <= p, q, r <= LIMIT and ????

    """
    counter = 0
    temp = b // 2
    if temp >= LIMIT:
        return 0
    elif b < LIMIT:
        counter += (a // 2)
    if temp <= a:
        counter += (a - temp)
        if (a - temp) % 2 == 0:
            counter += 1
    return counter

Now, the problem I have here is that I can't figure out exactly which cuboids this is supposed to count, so I don't know how to write the docstring.

Your comment at the top says:

# 1, 5, 8 | 2, 4, 8 | 3, 3, 8 (when decomposing 6)
# 6, 2, 6 | 6, 3, 5 | 6, 4, 4 (when decomposing 8, although 6, 1, 7 are not
# good, the largest of the 3 needs to be a member of the Pythagorean triplet)

and indeed:

>>> count_cuboids(6, 8, 100)
6

so this suggests that the docstring for count_cuboids might need to be:

"""Given a Pythagorean pair (a, b), return the number of cuboids (p, q, r)
such that 1 <= p, q, r <= LIMIT and
either: p <= q <= r and p + q == a and r == b
    or: p == a and q <= r <= p and q + r == b."""

but then I tried the simplest example:

>>> count_cuboids(3, 4, 100)
2

which doesn't match your specification. According to your specification, there ought to be three possible cuboids here, not two: (1, 2, 4), (3, 1, 3) and (3, 2, 2).

So your code for counting the cuboids does not match your specification. One or both of them is wrong.

5. Conclusion

I don't want to spoil the Project Euler problem, so I'll leave you to take it from here. I'll finish by repeating the key points:

Use functional decomposition to split your code up into parts that you can test separately.
Write docstrings explaining what each function does. If you are having trouble writing concise and clear docstrings, this is a sign that the way you  have decomposed your code was poorly chosen and needs to be reconsidered.
Make use of generators to produce and consume sequences of results without having to store them in intermediate data structures.
When you have a complicated, optimized function, also implement a naïve, straightforward version of the same function that you can use to test it.


Get users that are presidents and compute their name I have a user table like this

id | firstname | surname  | title
1  | Bob       | Batman   | Dr.
2  | Alice     | Grimley  | Prof.
3  | Clara     | Caprio   |

In the user model class I have a function that computes the name

class User extends Authenticatable
{
    //...

    public function computeName()
    {
      return  trim($this->title . ' ' . $this->firstname . ' ' . $this->surname);
    }

    //...
}

In addition I have a 1:n relation with a table sortUser2Pres where n can only be 0 or 1. The relation maps if a user is a president or vice-president in a country.

user_id | country | type
1       | DE      | vice-president
2       | DE      | president

Now I wish to compute a name list of all users who are president. I can achieve it as follows:

$presidents = DB::table('user')
               ->select('firstname','surname','title')
               ->join('sortUser2Pres s', 's.user_id','=','user.id')
               ->where('s.type','president')
               ->get();

$names =  [];
foreach ($presidents as $user) {
    $names[] = trim($->title . ' ' . $->firstname . ' ' . $user->surname);
}

However, I think its bad that I cannot make use of the functions from the user model like computeName and that I have to copy & paste this function. Isn't there a cleaner way of achieving such a name list in Laravel and making use of the existing functions in the user model?

why do you have a 1:n relation? you can just add a 1:1 or column to your user table which has a type column for example and it holds president or vice-president values and then you can have a function in your model to check if it's a president or vice-president.

You can add a function to your repository to get all user which they are president with a simple query.


Python factory method with easy registry My aim is to define a set of classes, each providing methods for comparing a particular type of file. My idea is to use some kind of factory method to instantiate the class based upon a string, which could allow new classes to be added easily. Then it would be simple to loop over a dictionary like:

files = {
    'csv': ('file1.csv', 'file2.csv'),
    'bin': ('file3.bin', 'file4.bin')
}

Here is what I have so far:

# results/__init__.py
class ResultDiffException(Exception):
    pass

class ResultDiff(object):
    """Base class that enables comparison of result files."""
    def __init__(self, path_test, path_ref):
        self.path_t = path_test
        self.path_r = path_ref

    def max(self):
        raise NotImplementedError('abstract method')

    def min(self):
        raise NotImplementedError('abstract method')

    def mean(self):
        raise NotImplementedError('abstract method')

# results/numeric.py
import numpy as np
from results import ResultDiff, ResultDiffException

class NumericArrayDiff(ResultDiff):

    def __init__(self, *args, **kwargs):
        super(NumericArrayDiff, self).__init__(*args, **kwargs)

        self.data_t = self._read_file(self.path_t)
        self.data_r = self._read_file(self.path_r)

        if self.data_t.shape != self.data_r.shape:
            raise ResultDiffException('Inconsistent array shape')

        np.seterr(divide='ignore', invalid='ignore')
        self.diff = (self.data_t - self.data_r) / self.data_r
        both_zero_ind = np.nonzero((self.data_t == 0) & (self.data_r == 0))
        self.diff[both_zero_ind] = 0

    def _read_file(self, path):
        return np.loadtxt(path, ndmin=1)

    def max(self):
        return np.amax(self.diff)

    def min(self):
        return np.amin(self.diff)

    def mean(self):
        return np.mean(self.diff)

class CsvDiff(NumericArrayDiff):

    def __init__(self, *args, **kwargs):
        super(CsvDiff, self).__init__(*args, **kwargs)

    def _read_file(self, path):
        return np.loadtxt(path, delimiter=',', ndmin=1)

class BinaryNumericArrayDiff(NumericArrayDiff):

    def __init__(self, *args, **kwargs):
        super(BinaryNumericArrayDiff, self).__init__(*args, **kwargs)

    def _read_file(self, path):
        return np.fromfile(path)

As you can see, the classes CsvDiff and BinaryNumericArrayDiff have only very minor changes with respect to NumericArrayDiff, which could potentially be refactored using constructor arguments. The problem is that different file types would then require different constructor syntax, which would complicate the factory pattern.

I did also consider providing @classmethods to NumericArrayDiff, which could be put in a dict in order to link to the file types. However, I'm hoping for a more natural way of registering these classes to the factory.

Any advice would be much appreciated.

1. Stop writing classes

The title for this section comes from Jack Diederich's PyCon 2012 talk.

A class represents a group of objects with similar behaviour, and an object represents some kind of persistent thing. So when deciding what classes a program is going to need, the first question to ask is, "what kind of persistent things does this program need to represent?"

In this case the program:

knows how to load NumPy arrays from different kinds of file format (CSV and plain text); and
knows how to compute the relative difference between two NumPy arrays (so long as they come from files with the same format).

The only persistent things here are files (represented by Python file objects) and NumPy arrays (represented by numpy.ndarray objects). So there's no need for any more classes.

2. Other review points

The code calls numpy.seterr to suppress the warning:

RuntimeWarning: invalid value encountered in true_divide

but it fails to restore the original error state, whatever it was. This might be an unpleasant surprise for the caller. It would be better to use the numpy.errstate context manager to ensure that the original error state is restored.
When dispatching to NumPy functions, it usually unncessary to check shapes for compatibility and raise your own error. Instead, just pass the arrays to NumPy. If they can't be combined, then NumPy will raise:

ValueError: operands could not be broadcast together ...

3. Revised code

Instead of classes, write a function!

import numpy as np

def relative_difference(t, r):
    """Return the relative difference between arrays t and r, that is:

    0              where t == 0 and r == 0
    (t - r) / r    otherwise

    """
    t, r = np.asarray(t), np.asarray(r)
    with np.errstate(divide='ignore', invalid='ignore'):
        return np.where((t == 0) & (r == 0), 0, (t - r) / r)

Note the following advantages over the original code:

It's much shorter, and so there's much less code to maintain.
It can find the difference between arrays that come from files with different formats:

relative_difference(np.loadtxt(path1), np.fromfile(path2))

It can find the difference between arrays that don't come from files at all:

relative_difference(np.random.randint(0, 10, (10,)), np.arange(1, 11))


Regex in combination with file compare I have made a funtion to compare text files line by line, where timestamps and jobnumbers are replaced for a identical string. By lack of experience I'm not sure if this is the best way to do this.

if (row < comparedFile.Count)
{
    var regexJobNumber = @"([0-9]{4})";
    var regexTimeStamp = @"([0-9]{8}_[0-9]{6})";
    var input = line;
    var removeTimestamp = Regex.Matches(input, regexTimeStamp).Cast<object>().Aggregate(input, (current, Match) => Regex.Replace(current, regexTimeStamp, "<TimeStamp>"));
    var removeJobnumber = Regex.Matches(removeTimestamp, regexJobNumber).Cast<object>().Aggregate(removeTimestamp, (current, Match) => Regex.Replace(current, regexJobNumber, "<JobNummer>"));

    var input2 = comparedFile[row];
    var removeTimestamp2 = Regex.Matches(input2, regexTimeStamp).Cast<object>().Aggregate(input2, (current, Match) => Regex.Replace(current, regexTimeStamp, "<TimeStamp>"));
    var removeJobnumber2 = Regex.Matches(removeTimestamp2, regexJobNumber).Cast<object>().Aggregate(removeTimestamp2, (current, Match) => Regex.Replace(current, regexJobNumber, "<JobNummer>"));

    if (!removeJobnumber.Equals(removeJobnumber2))
    {
       var rowcount = row + 1;
       differenceList.Add("Difference found on rownumber: " + rowcount);
    }
    row++;
}

This isn't complete code. We have no idea what's happening with row; it seems to be a loop index, but we have no idea what else is happening in the loop.

Anyway, here's my take on things:

Create compiled regexes and move their creation out of the loop, creating Regex instance variables instead of using the static methods. This gets you a speed boost and simplifies the code.
Do the .Replace()s unconditionally; there's no harm in doing so.
Extract the common code into a new function/method. Don't repeat yourself. If you decided you wanted to use the English spelling "Number" instead of Dutch "Nummer" you don't want to have to fix it in two places.

So here it is:

string Standardize(string input)
{
  static var regexJobNumber = new Regex(@"(\d{4})", RegexOptions.Compiled);
  static var regexTimeStamp = new Regex(@"(\d{8}_\d{6})", RegexOptions.Compiled);
  string intermediate = regexTimeStamp.Replace(input, "<TimeStamp>");
  return regexJobNumber.Replace(intermediate,"<JobNumber>");
}

//...

  if (row < comparedFile.Count)
  {
    if (Standardize(removeJobnumber) != Standardize(removeJobnumber2))
    {
       var rowcount = row + 1;
       differenceList.Add("Difference found on rownumber: " + rowcount);
    }
    row++;
  }

My suggestion is to go through the documentation for Regex and see how each method is used.