Sales report for an invoicing system I am creating a sort of Sales Report for an Invoicing System.

I have an extremely complex MySQL Query that takes a very long time to execute (usually about 10 - 15 seconds). It involves multiple tables (containing hundreds or even thousands of rows) in a database that an even more complex system is built upon.

At this stage in development, it doesn't seem to me that it would be beneficial to change the structure of the database tables for this one query since everything else is working very fast.

If you care to review my query and give me advice on how to optimize my code to achieve the quickest possible time in terms of speed, I would be more than grateful.

I am using PHP with MySQLi.

SELECT `u`.`first`, `u`.`last`,
    `i`.`id`, IFNULL(`i`.`vendor`, `d`.`unattached_vendor`) AS `vendor`, IFNULL(`i`.`originalskunumber`, `d`.`skunumber`) AS `skunumber`,
    `d`.`date_sent`, `d`.`document_type`, `d`.`document_id`, `d`.`description`, `d`.`qty`, `d`.`triage_notes`, `d`.`status`, `d`.`arrival_date`, `d`.`id` AS `document_row`
    FROM `documents` AS `d`
        LEFT JOIN `inventory` AS `i`
            ON (CASE
                WHEN `d`.`document_type` = 'Invoice'
                    THEN `i`.`skunumber` = `d`.`skunumber`
                WHEN `d`.`document_type` = 'Purchase Order'
                    THEN `i`.`originalskunumber` = `d`.`skunumber`
            END)
        INNER JOIN `users` AS `u`
            ON `u`.`uid` = `d`.`customer_id`
        WHERE `d`.`document_type` <> 'Quote'
            AND `d`.`header_item` = '0'
            AND `d`.`active_document` = '1'
            AND `d`.`active_item` = '1'
            AND (CASE
                WHEN `d`.`document_type` = 'Invoice' AND `d`.`skunumber` IS NOT NULL
                    THEN (`d`.`document_id`, LEFT(`d`.`skunumber`, 3)) NOT IN (SELECT `trailing_doc`, LPAD(`vendor_code`, 3, '0') AS `vendor_code` FROM `documents` WHERE `active_document` = '1' AND `active_item` = '1' AND `trailing_doc` IS NOT NULL AND `vendor_code` IS NOT NULL)
                WHEN `d`.`document_type` = 'Purchase Order'
                    THEN 1
                ELSE 1
            END)
            AND (CASE
                WHEN `d`.`document_type` = 'Invoice'
                    THEN `d`.`document_id` IN (SELECT DISTINCT `document_id` FROM `payments` WHERE `active_payment` = '1' AND `payment_amount` > 0)
                WHEN `d`.`document_type` = 'Purchase Order'
                    THEN 1
            END)
            AND (CASE
                WHEN `i`.`id` IS NULL AND `document_id` IN (SELECT DISTINCT `trailing_doc` FROM `documents` WHERE `document_type` = 'Purchase Order' AND `active_document` = '1' AND `active_item` = '1' AND `trailing_doc` > '')
                    THEN 0
                ELSE 1
            END)
    GROUP BY `d`.`document_id`, `i`.`originalskunumber`

As requested, here's my EXPLAIN:

id  select_type         table       type    possible_keys   key     key_len     ref                     rows    Extra
1   PRIMARY             d           ALL     NULL            NULL    NULL        NULL                    2298    Using where; Using temporary; Using filesort
1   PRIMARY             u           eq_ref  PRIMARY         PRIMARY 4           example.d.customer_id   1       Using where
1   PRIMARY             i           ALL     NULL            NULL    NULL        NULL                    77418   Using where
4   DEPENDENT SUBQUERY  documents   ALL     NULL            NULL    NULL        NULL                    2298    Using where; Using temporary
3   DEPENDENT SUBQUERY  payments    ALL     NULL            NULL    NULL        NULL                    14      Using where; Using temporary
2   DEPENDENT SUBQUERY  documents   ALL     NULL            NULL    NULL        NULL                    2298    Using where

There are some formatting and code clarity points I will mention a bit further down, but for now there are some places I think the performance could be improved, at a glance. You should definitively consider posting your EXPLAIN and table definitions, as was suggested in a comment, for this and future SQL questions, as those can make a huge difference, often more so than the queries themselves.

Bottlenecks

This JOIN is perplexing:

FROM documents AS d
    LEFT JOIN inventory AS i
        ON (CASE
            WHEN d.document_type = 'Invoice'
                THEN i.skunumber = d.skunumber
            WHEN d.document_type = 'Purchase Order'
                THEN i.originalskunumber = d.skunumber
        END)

There is a fundamental problem if you are using a case expression like this as a joining condition. Why are your Invoice and Purchase Order documents not normalized into their own tables? I would suggest to take another look at the architecture there, especially if you find yourself having to do this kind of join often.
Parsing strings in SQL is expensive. At the very least, I hope your document_type column is indexed. If it isn't, then that's a choke point, because it has to scan the documents table (instead of an index) just to be able to join. If you find yourself making joins on non-index columns more than just very seldom, you need to look to do some serious indexing, and consider normalizing.
You are using a LEFT JOIN so I am assuming you are expecting null values... but the way you wrote the expression does not make that clear. Consider at the very least adding a comment to explain where you are expecting nulls and how it handles it.

I had to notice further down what the left join is actually for, with this bit...

WHEN d.document_type = 'Invoice' AND d.skunumber IS NOT NULL

How many other kinds of documents are stored like this? I see at least one more, Quote. Good question to ask yourself, I think. It's much easier to re-architect databases earlier on, if you have that luxury, than after you've written all your application around a sub-par architecture.

This is a bit weird:

WHERE d.document_type <> 'Quote'
    AND d.header_item = '0'
    AND d.active_document = '1'
    AND d.active_item = '1'

What are those '0' and '1'supposed to mean? Why are they characters instead of say, a BIT if they are meant to be true/false, or a TINYINT or INT if that is just a key that represents some value?

This part (and the 2 after it) in your where clause is formatted in such a way that as a one-liner you don't really see what is going on. Once you format it like the rest of your query is, it becomes clear that it's a very inefficient operation:

WHERE ...
...
AND (CASE
    WHEN d.document_type = 'Invoice' AND d.skunumber IS NOT NULL
        THEN (d.document_id, LEFT(d.skunumber, 3)) NOT IN (
            SELECT
                trailing_doc,
                LPAD(vendor_code, 3, '0') AS vendor_code
            FROM documents
            WHERE active_document = '1'
                AND active_item = '1'
                AND trailing_doc IS NOT NULL
                AND vendor_code IS NOT NULL
        )
    WHEN d.document_type = 'Purchase Order'
        THEN 1
    ELSE 1
END)

Wow, this is complex.

This condition is redundant: WHEN d.document_type = 'Purchase Order' THEN 1 ELSE 1. If a value doesn't fall in your first case, it will be 1 either way, so just keep the ELSE 1 by itself.
Again, I hope this document_type column is indexed, otherwise here we go again parsing those strings!
Now at first glance, this subquery seems really odd. You are verifying that your document_id (primary key, I'm assuming) is not contained in trailing_doc column (why?) and, perhaps even more strangely to an outsider, that the left-most 3 characters of your skunumber (why is it called a number if it has characters?) are not the same as the vendor_code padded to 3 characters with 0s to the left. So presumably, a skunumber could look something like 011999999 where 011 is the vendor code, and 999999 is the actual unit number. Did I guess right? That, to me, would be deserving of at the very least a small explanation as code comment, so the next maintainer doesn't have to do this kind of mental gymnastics as well.
Again, if performance is a concern, I really hope you have indexes on skunumber, vendor_code and trailing_doc. If you don't, then there's another bottleneck.

All the same points apply on your other subqueries to payments table. (except maybe point 3 that's pretty specific to this one).

Split into multiple, more specialized queries?

Consider splitting this logic into at least 2 queries, one for invoices and one for purchase orders, since they are really not the same thing. If need be, you could always bring them together using UNION, or combine them some other way (maybe in your application?), or altogether just keep them separated.

Code style

A few things:

All those back-ticks are really distracting, and really not needed. I realize they are added there by a PHP tool, but a quick find & delete in a text editor, or using a regex, is all that's needed to remove them.
Some line breaks make the first part of a SELECT easier to read, like

SELECT
    u.first,
    u.last,
    i.id,
    IFNULL(i.vendor, d.unattached_vendor) AS vendor,
    IFNULL(i.originalskunumber, d.skunumber) AS skunumber,
    ....
It's tempting to use 1-letter aliases for tables, but in bigger queries it can make things very hard to follow, once you start joining in 6, 9, 12 tables, to keep track of all those d, u and i names. Naming things is hard, but reading unclear code is harder.

I made a pastebin of how I reformatted your query here.


Code Chef problem COOKMACH Firstly, I got the solution for this question in CodeChef, but I noticed one thing which still confuses me. This was the code which was accepted as correct.

#include<iostream>
using namespace std;
int main(){
    int testCases,count=0;
    cin>>testCases;
    unsigned long int a,b;
    while(testCases--){
            count=0;
            cin>>a>>b;
            while(a&(a-1)){
                    a>>=1;
                    count++;
            }
            while(a>b){
                    a>>=1;
                    count++;
            }
            while(a != b){
                    a<<=1;
                    count++;
            }

            cout<<count<<"\n";
    }
   return 0;
}

And this is the solution which was getting TLE:

 #include<iostream>
 using namespace std;
 int main(){
    int testCases,count=0;
    cin>>testCases;
    unsigned long int a,b;
    while(testCases--){
            count=0;
            cin>>a>>b;
            while(a&(a-1) != 0 || a>b){
                    a>>=1;
                    count++;
            }
            while(a != b){
                    a<<=1;
                    count++;
            }

            cout<<count<<"\n";
    }
 return 0;
}

Both the solutions are almost same. What I have just modified in the first is that I have put a separate while loop

for checking if a is the power of 2
for making value of a less than b

Now what I understood was that keeping separate while loop saves me time by NOT having to do two conditions check for each iteration.

Am I correct with this understanding, or I am missing something. If I am correct, is it good practice (as per optimization) to write separate loops.

I would like to know how I can write this code in a better way or what other good practice I can follow.

is it good practice (as per optimization) to write separate loops.

That depends on the logic you need to implement. For example, if you have two loops iterating over the same range and having the same body, then it would be good to combine them to eliminate the code duplication. But that's not the case here, as the two loops can have distinct ranges. By combining the loops, you extend the range, and evaluate some condition more than necessary.

Take for example the input 256 and target 1. There's no need to evaluate the first condition more than once. After one check, it's enough to evaluate the second condition repeatedly until you reach the target number.

It's very often not possible to separate the conditions like this, effectively serializing the operations. For example if you have an unordered collection of users and you want to filter out those under age 20 and above 60, you have no choice but iterate over the entire collection, and to avoid two loops with identical bodies, it will be good to combine the conditions. You cannot just iterate while users are under 20 and then continue while users are above 60, since the collection is not known to be ordered that way. If it was, you would benefit from splitting the loop, reducing the number of evaluated conditions.

By the way, a funny thing about the challenge in question is that you could even flip the order of those two loops, for example this will work too:

while(a>b){
        a>>=1;
        count++;
}
while(a&(a-1)){
        a>>=1;
        count++;
}

The point is,
in this example the loops don't operate on the same range.
They each reduce the range,
and they can do that independently to get the same result.

Code review

Keep in mind that using namespace std is considered bad practice. A practical alternative:

using std::cin;
using std::cout;

Some other minor improvements:

It's better to declare variables where you use them, in the smallest scope
The code would be more readable if you put spaces around operators
The indentation is inconsistent
It's recommended to have one statement per line
No need for return 0 at the end of the main method, the compiler adds it automatically

Like this:

#include <iostream>

using std::cin;
using std::cout;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        unsigned long int a, b;
        cin >> a >> b;

        int count = 0;
        while (a & (a - 1)) {
            a >>= 1;
            count++;
        }
        while (a > b) {
            a >>= 1;
            count++;
        }
        while (a != b) {
            a <<= 1;
            count++;
        }

        cout << count << "\n";
    }
}


Project Euler #9 in Swift - Special Pythagorean triplet I just finished Project Euler #9 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.

  A Pythagorean triplet is a set of three natural numbers, a < b < c,
  for which,

  a^2 + b^2 = c^2 For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

  There exists exactly one Pythagorean triplet for which a + b + c =
  1000. Find the product abc.

import Foundation

func getSpecialPythagoreanTriplet(sum:Int) -> Int {

    for var c = 2; c < sum; c++ {

        for var b = 1;b < c; b++ {

            for var a = 0; a < b; a++ {

                if (sum % (a + b + c)) == 0 && a * a + b * b == c * c {
                    let minSum = a + b + c
                    a *= sum / minSum
                    b *= sum / minSum
                    c *= sum / minSum
                    return a * b * c
                }
            }
        }

    }
    return -1
}

func euler9() {
    let number = getSpecialPythagoreanTriplet(1_000)

    println(number)
}

func printTimeElapsedWhenRunningCode(operation:() -> ()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

printTimeElapsedWhenRunningCode(euler9)

The code executes in 0.000274002552032471 s

Your program is quite fast, but that is a bit of a lucky coincidence. The
Pythagorean triplet with sum 1000 is (200, 375, 425). This is not a primitive
Pythagorean triplet  but (8, 15, 17) multiplied by 25.

So your program finds (8, 15, 17) quickly and from there "jumps" to the solution.
That is fine and solves the Project Euler problem. But if you want a solution
for arbitrary sums then one can do better. On my computer, your program
needs

0.0004 seconds to find the solution for sum = 1000, but
0.014 seconds to find the solution for sum = 928, and
1.9 seconds to find that there is no solution for sum = 1001.

The key point is that your method uses three nested loops, which is not necessary
because only two of the variables a, b, c can be chosen freely and the last
is determined by \$ a+b+c = \text{sum} \$.

From the condition a < b < c one can also restrict the possible ranges.
If we start with a in the outermost loop then

$$
    \text{sum} = a + b + c \ge a + (a + 1) + (a + 2) = 3 \, a + 3 \implies a \le (\text{sum} - 3)/3
$$

and for b we have

$$
    \text{sum} = a + b + c \ge a + b + (b + 1) = a + 2 \, b + 1
    \implies b \le (\text{sum} - 1 - a)/2 \quad .
$$

So your function would be

func getSpecialPythagoreanTriplet(sum:Int) -> Int {

    for var a = 1; a <= (sum - 3)/3; a++ {
        for var b = a + 1; b <= (sum-1-a)/2; b++ {
            let c = sum - a - b
            if a*a + b*b == c*c {
                return a*b*c
            }
        }
    }
    return -1
}

This method needs about 0.0002 seconds to find the solution (or it's non-existence) in all three test cases (sum = 1000, 928, 1001).

One note regarding your function name: It might be unclear what is "special"
in getSpecialPythagoreanTriplet().
Also the "Coding Guidelines for Cocoa" recommend the "get" prefix only for functions
that return some value indirectly. A better name for your function would
be something like

func pythagoreanTripletWithSum(sum:Int) -> Int


Hasher class for PHP<5.3 I've constructed a simple class whose entire purpose is to hash passwords securely and simply.

The catch is the PHP version is probably going to be 5.2.x. This means:

No CRYPT_BLOWFISH
Obviously no password_hash().

The question is, is the following secure? Can it be improved?

/**
 * Class Hasher
 *
 * @package Dependencies\Hasher
 *
 * Defines hashing mechanism for password saving.
 */
class Hasher {

    /**
     * @param string $string String for hashing
     * @param string $salt   Unique salt. The salt is best kept as a very long, very random string.
     * @param int    $cost   Cost parameter. 2^$cost iterations over the hashing algorithm.
     *
     * @return string
     */
    public function algo($string, $salt, $cost) {
        $iterations = pow(2, $cost);
        $result     = "";

        for ($i = 0; $i < $iterations; $i++) {
            $result = sha1($result . $salt . $string);
        }

        return $result;
    }

    /**
     * Pass a password through the hashing algorithm. And return the result.
     *
     * @param string $password
     * @param string $salt
     * @param int    $cost
     *
     * @return string
     */
    public final function hash($password, $salt, $cost = 10) {
        return $this->algo($password, $salt, $cost);
    }

    /**
     * Match password through the hashing algorithm against an existing hash to make sure there's a match.
     *
     * @param string $hash
     * @param string $password
     * @param string $salt
     * @param int    $cost
     *
     * @return bool
     */
    public final function verify($hash, $password, $salt, $cost = 10) {
        return $this->algo($password, $salt, $cost) == $hash;
    }

}

There are several improvements to this that involve various algorithms that are more cryptographically secure than sha1 (such as sha256 or higher, blowfish, whirlpool, etc.), using strict comparison (to avoid that gotcha with very long hashes loosely comparing when not equal), and including a CSPRNG salting function in the class, that takes over when a user does not supply a salt.

However, CRYPT_BLOWFISH is still very usable in PHP < 5.3. In fact, It's usable in PHP 3.0.18 and over, with the use of PHPass, by the same security company who make John the Ripper (which you should be using to test your class. Try and get the UNIQPASS wordlist. It's really effective!). An alternative to JtR is hashcat. There are several defcon talks about correct usage of password crackers to test strength (by the feds), among other uses (by the non-feds).

If you really must roll your own, then consider implementing blowfish manually.


Compose in Javascript - Go ahead with this example? I'm trying to use the good parts of Javascript and dont follow the classical inheritance.
I studied and created this example of compose in Javascript, https://gist.github.com/fernandoperigolo/7789866.

My question is. You think this example have a good implementations of composition? Can i go ahead with it? If not, What you suggest?

(function(){
  // Adding compose to Function prototype
  Function.prototype.compose = function(argFn) {
    var fnToCall = this;
    return function() {
      // This line is really complex and i don't know exactly what this line do
      return fnToCall.call(this, argFn.apply(this,arguments));
    }
  }

  // Eletronic atributes and methods
  var asEletronic = function(){
    this.voltage = '220v';
    this.power = false;
    this.switchPower = function(){
      if (this.power === true) {
        this.power = false;
        console.info('Eletronic are off now.');
      }else{
        this.power = true;
        console.info('Eletronic are on now.');
      };
    }
    return this;
  };

  // Sound Reproducer atributes and methods
  var asSoundReproducer = function(){
    this.watts = 60;
    this.playSound = function(sound){
      console.info('Playing the sound: '+sound);
    };
    return this;
  };
  // All sound reproducer is a eletronic
  // Composing first level
  asSoundReproducer = asSoundReproducer.compose(asEletronic)

  // Micro System atributes and methods
  // Not used, just example
  var asMicroSystem = function(){
    this.cd = false;
    this.mp3 = true;
    return this;
  };

  // TV atributes and methods
  var TV = function(){
    this.pol = 42;
    this.hdmi = true;
    return this;
  };

  // Compose a TV with full resources
  // Compose second level, asSoundReproducer is a composed object
  // This line looks me strange...
  TV = TV.compose(asSoundReproducer);

  // Create a new TV
  var myTV = new TV();

  // Looking my TV
  console.log(myTV);

  // Call a Eletronic method
  myTV.switchPower();

  // Call a Sound Reproducer method
  myTV.playSound('guitar.mp3');
})();

Interesting question,

from your comments inside the code you seem to not have written the code or have heavily borrowed from somebody else's code..

From a high level I have only a  few misgivings:

Do not modify standard JS objects, so do not add compose to the prototype of Function,  I grant you that it looks cool but it will bite you at some point
myTV instanceof asSoundReproducer does not work, so figuring what kind of object you are dealing with can be painful ( this is a drawback from not using standard js OO )
You have some provision for passing parameters to functions with argFn.apply(this,arguments) but the function signatures might look ugly since you do not cut out argFn from arguments
When reading up on composing, I prefer much to be able to compose in one go like TV = compose( asSoundReproducer, asMicroSystem );
I am not sure what as stands for in your function names, I would drop anything that resembles Hungarian notation.

This counter proposal is more complicated, but handles multiple constructors in 1 go, amd  provides support for parameters and typeof.

function merge(object, boltOn) {
  //Simply merge the properties of boltOn into object, overriding existing properties
  for(var property in boltOn)
    if(boltOn.hasOwnProperty(property))
      object[property] = boltOn[property];
  return object;
}

function compose(/*Constructor1, Constructor2, ..*/) {
  //Keep a closure reference for later
  var constructorReferences = arguments;

  return function ComposedConstructor(/*parameter1, parameter2, ..*/) {

    //Clone the constructors, we will modify the clones
    var constructorClones = Array.prototype.slice.call(constructorReferences).map(function(Constructor) {
      return new Object(Constructor);
    });

    var constructor = constructorClones.pop();
    //Set up the prototype chain, without loosing the original prototypes thru `merge`
    while(constructorClones.length) {

      var nextConstructor = constructorClones.pop();
      nextConstructor.prototype = merge(new constructor(arguments), nextConstructor.prototype);
      constructor = nextConstructor;

    }
    //Call the first constructor with the arguments provided to the constructor
    constructor = constructor.bind.apply(constructor, [null].concat(Array.prototype.slice.call(arguments)));
    return new constructor();
  };
}

function A(name) {
  this.a = name;
  console.log(arguments);
}
A.prototype.sayA = function() {};

function B() {
  this.b = 2;
  console.log(arguments);
}
B.prototype.sayB = function() {};

function C() {
  this.c = 3;
  console.log(arguments);
}
C.prototype.sayC = function() {};

var O = compose(A, B, C);
var o = new O('Samsung');

// {[object Object] { a: "Samsung",b: 2,c: 3,sayA: function,sayB: function,sayC: function}
console.log(o);
console.log(o instanceof A); //true
console.log(o instanceof B); //true
console.log(o instanceof C); //true


Find GCD of two numbers without using multiplication, division or modulus operators If either a or b is 0 return the other number. If both even return gcd of a/2 and b/2. If either a or b is even divide it by 2 and return gcd of the pair. If a less than or equal to b, return the gcd of a, a-b else return gcd of b, a-b

private int gcd(int a, int b){
        if(a == 0) return b;
        if(b == 0) return a;
        boolean isAEven = (a & 1) == 0;
        boolean isBEven = (b & 1) == 0;
       // if a and b are divisible by 2
        if(isAEven && isBEven){
            return gcd( a >> 1,  b >> 1) << 1;
        }
        if(isAEven && !isBEven){
            return gcd( a >> 1, b);
        }
        if(!isAEven && isBEven){
            return gcd(a, b >> 1);
        }
        if(a <= b){
            return gcd(a, b-a);
        } else {
            return gcd(b, a-b);
        }
    }

The code in general looks decent. There are some minor things in coding style that could be improved.

I would rename isAEven to aIsEven or aEven. A variable is a state, not a question.

The method in itself doesn't rely on any state of some object. It's a utility function. It would make more sense if it were static instead. If you plan to provide other similar utility functions you could write a specific class to group those. Similar to the Math class already available in java.

In this block:

    if(isAEven && isBEven){
        return gcd( a >> 1,  b >> 1) << 1;
    }
    if(isAEven && !isBEven){
        return gcd( a >> 1, b);
    }
    if(!isAEven && isBEven){
        return gcd(a, b >> 1);
    }

the checks for !isXEven are redundant. After the first if, you know that not both are even. Whether or not to remove this is your choice on which is more readable. Alternatively you could write it as:

    if(isAEven && isBEven){
        return gcd( a >> 1,  b >> 1) << 1;
    } else if(isAEven){
        return gcd( a >> 1, b);
    } else if(isBEven){
        return gcd(a, b >> 1);
    }

I added the else to make it explicit that these 3 actually belong together. Changing the order isn't allowed anymore after removing the !... check.

About the actual algorithm. it looks slightly different from what I've seen before. Doing a little searching on the internet I found out it's almost the same as this Binary GCD algorithm.

You're only missing 2 optimisations.

The first one is the obvious if(a == b) return a. When both are equal you don't need to calculate anything else. The biggest difference can be seen if a = b = 1<<30 (the biggest integer power of 2) where your algorithm takes about 32 recursive steps.

The other optimisation is a bit less obvious. The last 2 recursive calls in the code can also use a bitshift:

if(a <= b){
    return gcd(a, (b-a) >>1);
} else {
    return gcd(b, (a-b)>>1);
}

Because at  that point we know a (or b) is odd and b-a (or a-b) is even. We can skip a cycle to bitshift the new b immediatly.

Side note: you don't really need all the bitshifting if you're not interested in micro-optimisations for speed. The simplified version also works fast as is:

private static int gcd(int a, int b) {
    if (a == b) return a;
    if (a == 0) return b;
    if (b == 0) return a;

    if (a <= b) {
        return gcd(a, b - a);
    } else {
        return gcd(b, a - b);
    }
}


Tic Tac Toe check for win/tie in Python In the below GameOutcome class I'm checking for wins/ties in Tic Tac Toe. I'm pretty set on breaking the checks into 5 different functions because I'm specifically practicing making functions short and single-purposed. But I'm not at all set on my 5 if statements in the find_winner_or_tie method. Does somebody know a more elegant solution for the find_winner_or_tie method so it doesn't have 5 if statements in it? I sort of which I could just call each of the "check functions" in a loop but I don't know how to do this without hardcoding the names of all 5 of the "check functions".

class GameOutcome:

    def __init__(self):
        self.letter_dict = {'X': -1, 'O': 1, ' ': 0}
        self.state_of_game = None
        self.row_index_of_move = None
        self.column_index_of_move = None
        self.game_outcome = None

    def find_winner_or_tie(self, state_of_game, row_index_of_move, column_index_of_move):

        self.set_board_and_move(state_of_game, row_index_of_move, column_index_of_move)

        if self.check_row_containing_move_for_win():
            return self.game_outcome
        if self.check_column_containing_move_for_win():
            return self.game_outcome
        if self.check_main_diagonal_for_win_iff_it_contains_move():
            return self.game_outcome
        if self.check_off_diagonal_for_win_iff_it_contains_move():
            return self.game_outcome
        if self.check_for_tie():
            return self.game_outcome

        return ''

    def set_board_and_move(self, state_of_game, row_index_of_move, column_index_of_move):
        self.state_of_game = state_of_game
        self.row_index_of_move = row_index_of_move
        self.column_index_of_move = column_index_of_move

    def check_row_containing_move_for_win(self):
        total = 0
        for column in range(3):
            total = total + int(self.letter_dict[self.state_of_game.board[self.row_index_of_move][column]])
            if abs(total) == 3:
                winning_letter = self.state_of_game.board[self.row_index_of_move][self.column_index_of_move]
                self.game_outcome = winning_letter
                return True
        return False

    def check_column_containing_move_for_win(self):
        total = 0
        for row in range(3):
            total = total + int(self.letter_dict[self.state_of_game.board[row][self.column_index_of_move]])
            if abs(total) == 3:
                winning_letter = self.state_of_game.board[self.row_index_of_move][self.column_index_of_move]
                self.game_outcome = winning_letter
                return True
        return False

    def check_main_diagonal_for_win_iff_it_contains_move(self):
        if self.row_index_of_move == self.column_index_of_move:
            total = 0
            for diagonal_indexing in range(3):
                total = total + int(self.letter_dict[self.state_of_game.board[diagonal_indexing][diagonal_indexing]])
                if abs(total) == 3:
                    winning_letter = self.state_of_game.board[self.row_index_of_move][self.column_index_of_move]
                    self.game_outcome = winning_letter
                    return True
        return False

    def check_off_diagonal_for_win_iff_it_contains_move(self):
        if self.row_index_of_move + self.column_index_of_move == 2:
            total = 0
            for off_diagonal_indexing in range(3):
                total = total + int(self.letter_dict[self.state_of_game.board[off_diagonal_indexing][2 - off_diagonal_indexing]])
                if abs(total) == 3:
                    winning_letter = self.state_of_game.board[self.row_index_of_move][self.column_index_of_move]
                    self.game_outcome = winning_letter
                    return True
        return False

    def check_for_tie(self):
        if len(self.state_of_game.available_squares) == 0:
            self.game_outcome = 'Tie'
            return True
        return False

(Note: no code in this post has been run- beware errors.)

I have a couple of issues with your design, and with your review request.

First, you say that you are committed to using five different functions for the checking. That's unfortunate, since this problem is very amenable to being solved with iteration.

Next, you have a class GameOutcome that is being asked to identify a winner or tie. I disagree with this- this is something the game itself should do. The game outcome, IMO, would be a data class just collecting results. The name GameOutcome suggest that this class would have no knowledge of the sequence of moves, or the state of the game board.

With those out of the way, let's talk about your code.

Those names!

I hate your naming style. You have fallen into the trap of making excessively long names for no good purpose. I strongly suggest you review code written by other people (either here on CodeReview or look through github or the pypi repositories) to get a sense of how names should be chosen.

Consider this line:

    if self.check_row_containing_move_for_win():

The method check_row_containing_move_for_win is an internal method. It is not intended for use by arbitrary external callers, it is only a method in order to package up its code behind a name.

For an internal function, why not just call it _check_row.

Similarly, you have an externally callable method named find_winner_or_tie. The declaration:

def find_winner_or_tie(self, state_of_game, row_index_of_move, column_index_of_move):

Here's a better approach:

def find_winner_or_tie(self, state, row, col):
    """ Check if either player has won, or if a tie has been forced. Return 'X' or 'O'
        for a win, 'Tie' for a tie, and None when the game is not over.

        Parameters:
          state:  state of the game
          row:    row of the last move
          col:    column of the last move
    """

Providing in-depth explanation is the function of comments, not names. Your names should be as long as they need to be, but no longer.

Builtins any() and all()

You are writing code that checks for various conditions. Python supplies the any() and all() built-ins for situations like this. The trick is to learn to construct iterables in line, and that means using generator expressions.

A generator expression is an inside-out for loop in parentheses, like:

(abs(x) for x in somelist)

They resemble, and are related to, list, dictionary, and set comprehensions. In all cases there is an iteration keyword (for ... in ...) and some kind of leading expression. With a generator expression, you are constructing a generator in-line and storing it, evaluating it, or passing it as parameters.

How does this help you? Well, suppose you have a group of functions you want to evaluate for success. Say ... five of them? You might decide that you were going to return if any of those conditions were true. Well ...

def find_winner_or_tie(self, state, row, column):
    """ ... """
    self.set_board_and_move(state, row, column)

    checks = (self.check_row, self.check_column, self.check_diag_lr, self.check_diag_rl, self.check_tie)

    if any(check() for check in checks):   # If any check is true, we know the outcome
        return self.game_outcome

    return None

Less code, more data!

The thing about most games is that they are based on lots of data. And if you write your code correctly, you will find more and more data, with less and less code. That's the case here. Let's take a look at one of your check-functions:

def check_row_containing_move_for_win(self):
    total = 0
    for column in range(3):
        total = total + int(self.letter_dict[self.state_of_game.board[self.row_index_of_move][column]])
        if abs(total) == 3:
            winning_letter = self.state_of_game.board[self.row_index_of_move][self.column_index_of_move]
            self.game_outcome = winning_letter
            return True
    return False

Honestly, that's so long that it's unreadable. So let's refactor out the names:

def check_row(self):
    """Check row containing latest move for a win."""
    bias = self.letter_dict
    board = self.state_of_game.board
    row = self.row_index_of_move

    total = 0
    for column in range(3):
        total = total + bias[board[row][column]]

    if abs(total) == 3:
        self.game_outcome = board[row][0]
        return True
    return False

I think some people have already pointed out sum and some other options. But let's actually spell out what the row and column choices are:

ROWS = [ ((0, 0), (0, 1), (0, 2)),
         ((1, 0), (1, 1), (1, 2)),
         ((2, 0), (2, 1), (2, 2)),
]

Now, you could write code to generate that. In one line, even! But that's not important. What's important is that we know that there's a ROWS variable that can be indexed by row-number and which has a sequence of (row, col) tuples identifying the cells to look at.

Now, how does that help? Well, it helps because you can write a helper function that does the checking for you given a sequence of cells. Like this:

def check_cells(self, indices):
    """ Return True if all gameboard[][] cells specified by indices have same value,
        else False.
    """
    board = self.state_of_game.board
    values = [board[row][col] for row,col in indices]
    v0 = values[0]
    return all(v == v0 for v in values)

Then you can write the check_ functions in terms of that:

def check_row(self):
    """Check row containing latest move for a win."""
    indices = ROWS[self.row_index_of_move]
    return self.check_cells(indices)

You'll have to put in some validation on the diagonals, so you only call the check_cells if the move really was on a diagonal. The key here is that this uses the check_ functions to provide more data to the underlying check_cells, and so the bottom level code where the work is getting done is mainly data-driven.

Extra credit: detect forced ties

Your tie-detector only triggers at the last minute. But there are plenty of circumstances where a tie is inevitable. Why not code your tie-checker to recognize them?


Optimizing unboxed array operations in Haskell Consider this simplified code which successively permutes array elements:

import Data.Word
import Data.Bits
import Data.Array.Unboxed
import Data.Array.Base
import Data.Array.ST

test3 :: UArray Int Word32 -> UArray Int Word32
test3 arr = arr `seq` runSTUArray (change arr) where
    change a' = do
        a <- thaw a'
        x0 <- unsafeRead a 0
        x1 <- unsafeRead a 1
        unsafeWrite a 0 (x1 + 1)
        unsafeWrite a 1 (x0 - 1)
        return a

test4 :: (Word32, Word32) -> (Word32, Word32)
test4 (x, y) = x `seq` y `seq` (y + 1, x - 1)

apply :: Int -> (Int -> a -> a) -> a -> a
apply n f v0 = n `seq` v0 `seq` applyLoop 0 v0 where
    applyLoop i v
        | i == n - 1 = res
        | otherwise = applyLoop (i + 1) res
        where res = f i v

main :: IO ()
main = let arr = listArray (0, 1) [0, 1] :: UArray Int Word32
    in print $ apply 10000000 (\_ x -> x `seq` test3 x) arr

On my machine, with ghc 7.4.2 and -O3 flag the version with test4 (plain tuples) shows ~10 times better performance then the version with UArray (also, according to the profiler, UArray version has total allocation of ~1.5 Gb). Are there any other optimizations I could do? I'd prefer to use the array version, because it will be more convenient in the real application.

Okay, first let's establish a baseline. I'm on a 32-bit system now, so the allocation figures and also the timings are somewhat different than on a 64-bit system, but the trends are mostly the same. To see what we deal with, let's not compile for profiling, but just plain with optimisations (-O2).

I have created a repository with all versions of the code I ran. I took the liberty and removed all superfluous seqs, and slightly changed applyLoop, to

applyLoop i v
    | i == n    = v
    | otherwise = applyLoop (i + 1) $ f i v

which changes the result if apply is initially called with a zero argument (the new one immediately returns the original argument, while the old looped until i reaches -1 after wrap-around of the counter), but for positive arguments the semantics remain unchanged. For very small positive n, the one extra comparison the new version does might make a measurable difference if f is inlined and trivial, but for nontrivial n or f, the extra comparison is negligible, and the new version avoids code duplication that happens with the old.

That gives

$ ./test3 +RTS -s
array (0,1) [(0,0),(1,1)]
    560,049,112 bytes allocated in the heap
        32,160 bytes copied during GC
        42,632 bytes maximum residency (2 sample(s))
        22,904 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0      1083 colls,     0 par    0.02s    0.02s     0.0000s    0.0001s
Gen  1         2 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    1.35s  (  1.35s elapsed)
GC      time    0.02s  (  0.02s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    1.37s  (  1.37s elapsed)

%GC     time       1.3%  (1.3% elapsed)

Alloc rate    415,944,041 bytes per MUT second

Productivity  98.6% of total user, 98.4% of total elapsed

in contrast to

$ ./test4 +RTS -s
(0,1)
        47,492 bytes allocated in the heap
        1,756 bytes copied during GC
        42,632 bytes maximum residency (1 sample(s))
        18,808 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0         0 colls,     0 par    0.00s    0.00s     0.0000s    0.0000s
Gen  1         1 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.04s  (  0.04s elapsed)
GC      time    0.00s  (  0.00s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.04s  (  0.04s elapsed)

%GC     time       0.5%  (0.6% elapsed)

Alloc rate    1,182,455 bytes per MUT second

Productivity  98.9% of total user, 103.1% of total elapsed

from test4. The difference is enormous. Well, let's look at the core to find out why, and how we can reduce it.

First, the core for using test4:

Rec {
Main.main_$s$wapplyLoop [Occ=LoopBreaker]
  :: GHC.Prim.Int#
     -> GHC.Prim.Word#
     -> GHC.Prim.Word#
     -> (# GHC.Word.Word32, GHC.Word.Word32 #)
[GblId, Arity=3, Caf=NoCafRefs, Str=DmdType LLL]
Main.main_$s$wapplyLoop =
  \ (sc :: GHC.Prim.Int#)
    (sc1 :: GHC.Prim.Word#)
    (sc2 :: GHC.Prim.Word#) ->
    case sc of wild {
      __DEFAULT ->
        Main.main_$s$wapplyLoop
          (GHC.Prim.+# wild 1)
          (GHC.Prim.plusWord# sc2 (__word 1))
          (GHC.Prim.minusWord# sc1 (__word 1));
      10000000 -> (# GHC.Word.W32# sc1, GHC.Word.W32# sc2 #)
    }
end Rec }

You can't beat that without short-cutting. You get a tight loop using only unboxed values in registers, it does no allocation. But note that seqing x and y in test4 is necessary here to aid the strictness analyser. Without it, you get a loop using boxed Word32s building up huge thunks. The seqs that originally were in apply resp. in the function (\_ x -> x `seq` testN x) passed to it make no difference whatsoever.

So, we have a lean and mean unboxed loop to aim for, and a sluggish alternative allocating tons. What is allocating so much, and taking so much time there?

The applyLoop worker in this case begins with

case GHC.ST.runSTRep
       @ (Data.Array.Base.UArray GHC.Types.Int GHC.Word.Word32)
       (\ (@ s) (s :: GHC.Prim.State# s) ->
          let {
            n# [Dmd=Just L] :: GHC.Prim.Int#
            [LclId, Str=DmdType]
            n# = GHC.Prim.sizeofByteArray# ww4 } in
          case GHC.Prim.newByteArray# @ s n# s of _ { (# ipv, ipv1 #) ->
          case {__pkg_ccall array-0.4.0.1 memcpy forall s.
                              GHC.Prim.MutableByteArray# s
                              -> GHC.Prim.ByteArray#
                              -> GHC.Prim.Word#
                              -> GHC.Prim.State# GHC.Prim.RealWorld
                              -> (# GHC.Prim.State# GHC.Prim.RealWorld, GHC.Prim.Addr# #)}

allocating a new ByteArray# - which is pretty fast, GHC's runtime is very good at such things, but nevertheless, 10 million allocations sum up to non-negligible time - and copying the contents of the old array over. The __pkg_ccall is a quite fast C call, but it is considerably slower than a Haskell call, and calling over to C for copying 8 bytes is wasteful (the call takes much longer than the copying). I think - though I can't verify at the moment - that on a 64-bit system that is done without calling out to C, which would be much faster. Replacing the thaw with a manual copying loop for an unsafeNewArray_ of the appropriate size (manual_copy.hs) brings down the time to 0.65 seconds - but increases the allocation figures:

$ ./manual_copy +RTS -s
array (0,1) [(0,0),(1,1)]
    760,049,112 bytes allocated in the heap
        41,424 bytes copied during GC
        42,632 bytes maximum residency (2 sample(s))
        22,904 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0      1469 colls,     0 par    0.02s    0.02s     0.0000s    0.0001s
Gen  1         2 colls,     0 par    0.00s    0.00s     0.0003s    0.0003s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.62s  (  0.63s elapsed)
GC      time    0.02s  (  0.02s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.64s  (  0.65s elapsed)

%GC     time       3.3%  (3.2% elapsed)

Alloc rate    1,226,997,169 bytes per MUT second

Productivity  96.6% of total user, 95.3% of total elapsed

Note that it would be different for a large array, then calling to memcpy of the C standard library would pay off.

Using unsafeThaw here (unsafeThaw.hs) avoids allocating new ByteArray#s (the underlying raw arrays that carry the payload of UArrays) each iteration, and the involved copying, so it unsurprisingly speeds up the program, and reduces allocation:

$ ./unsafeThaw +RTS -s
array (0,1) [(0,0),(1,1)]
    400,049,112 bytes allocated in the heap
        27,596 bytes copied during GC
        42,632 bytes maximum residency (2 sample(s))
        22,904 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0       764 colls,     0 par    0.01s    0.01s     0.0000s    0.0001s
Gen  1         2 colls,     0 par    0.00s    0.00s     0.0003s    0.0003s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.28s  (  0.28s elapsed)
GC      time    0.01s  (  0.01s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.29s  (  0.29s elapsed)

%GC     time       4.4%  (4.3% elapsed)

Alloc rate    1,448,146,787 bytes per MUT second

Productivity  95.5% of total user, 95.6% of total elapsed

So the speedup is about 4.5× compared to the original - not bad, but still a far cry from the test4 time - and the allocation is reduced by 160 million bytes (10 million times 8 bytes for the two Word32 plus 8 for bookkeeping [size] of the ByteArray#), but it is still huge.

That is because

of _ { (# ipv4, ipv5 #) ->
(# ipv4,
    Data.Array.Base.UArray
    @ GHC.Types.Int @ GHC.Word.Word32 ww1 ww2 ww3 ipv5 #)
}

in each iteration it creates a new UArray Int Word32. It allocates a new UArray constructor, and pointers to the components, lower bound, upper bound, number of elements and the ByteArray#. We can avoid that by returning the argument array - after we sneakily changed the contents of its ByteArray# (unsafeThaw2.hs):

test3 :: UArray Int Word32 -> UArray Int Word32
test3 arr = runST (change arr) where
    change a' = do
        a <- Data.Array.Unsafe.unsafeThaw a' :: ST s (STUArray s Int Word32)
        x0 <- unsafeRead a 0
        x1 <- unsafeRead a 1
        unsafeWrite a 0 (x1 + 1)
        unsafeWrite a 1 (x0 - 1)
        return a'

which results in

$ ./unsafeThaw2 +RTS -s
array (0,1) [(0,0),(1,1)]
    80,049,100 bytes allocated in the heap
        6,828 bytes copied during GC
        42,632 bytes maximum residency (2 sample(s))
        22,904 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0       151 colls,     0 par    0.00s    0.00s     0.0000s    0.0001s
Gen  1         2 colls,     0 par    0.00s    0.00s     0.0003s    0.0003s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.17s  (  0.17s elapsed)
GC      time    0.00s  (  0.00s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.17s  (  0.17s elapsed)

%GC     time       1.7%  (1.7% elapsed)

Alloc rate    480,150,792 bytes per MUT second

Productivity  98.1% of total user, 98.0% of total elapsed

another nearly twofold speedup and allocation figures reduced by 80%.

It takes so much longer and allocates so much more than the tight loop mostly because each iteration costs a GHC.ST.runSTRep, which is NOINLINE and inhibits a worker-wrapper transform of test3 that would allow cheaper access to the ByteArray#.

You can get much better performance if you change the type of apply to be monadic, and use a monadic version of test3, e.g. (cleanST.hs)

import Data.Word
import Data.Array.Unboxed
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST

test0 :: STUArray s Int Word32 -> ST s (STUArray s Int Word32)
test0 arr = do
    x0 <- unsafeRead arr 0
    x1 <- unsafeRead arr 1
    unsafeWrite arr 0 (x1+1)
    unsafeWrite arr 1 (x0 - 1)
    return arr

applyM :: Monad m => Int -> (Int -> a -> m a) -> a -> m a
applyM n f v0 = do
    let loop i v
            | i < n    = do
                v' <- f i v
                loop (i+1) v'
            | otherwise = return v
    loop 0 v0

main :: IO ()
main = let arr = listArray (0,1) [0,1] :: UArray Int Word32
       in print $ runSTUArray $ do
                    marr <- thaw arr
                    applyM 10000000 (\_ a -> test0 a) marr

that comes close to the tight loop:

$ ./cleanST +RTS -s
array (0,1) [(0,0),(1,1)]
        49,148 bytes allocated in the heap
        1,756 bytes copied during GC
        42,632 bytes maximum residency (1 sample(s))
        18,808 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0         0 colls,     0 par    0.00s    0.00s     0.0000s    0.0000s
Gen  1         1 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.05s  (  0.06s elapsed)
GC      time    0.00s  (  0.00s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.06s  (  0.06s elapsed)

%GC     time       0.4%  (0.4% elapsed)

Alloc rate    905,470 bytes per MUT second

Productivity  99.2% of total user, 97.3% of total elapsed

but is of course still slower because the array reads and writes go to the L1 cache, while test4 operated completely in registers.

If you don't want to change the type of apply, I know no clean way of coming close to the performance of the tight loop.

If you are prepared to get your hands really dirty, you can use low-level primitives (low_level.hs),

{-# LANGUAGE MagicHash, UnboxedTuples, BangPatterns #-}

import Data.Word
import Data.Array.Unboxed
import Data.Array.Base
import GHC.Base

test3 :: UArray Int Word32 -> UArray Int Word32
test3 arr = change arr where
    swp mbarr s =
        case readWord32Array# mbarr 0# s of
          (# s1, w0 #) ->
            case readWord32Array# mbarr 1# s1 of
              (# s2, w1 #) ->
                case writeWord32Array# mbarr 0# (w1 `plusWord#` 1##) s2 of
                  s3 -> writeWord32Array# mbarr 1# (w0 `minusWord#` 1##) s3
    change arr@(UArray _ _ _ ba)
        = case swp (unsafeCoerce# ba) realWorld# of
            !s -> arr

which gives more or less the same figures as cleanST,

$ ./low_level +RTS -s
array (0,1) [(0,0),(1,1)]
        49,112 bytes allocated in the heap
        1,756 bytes copied during GC
        42,632 bytes maximum residency (1 sample(s))
        18,808 bytes maximum slop
            1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
Gen  0         0 colls,     0 par    0.00s    0.00s     0.0000s    0.0000s
Gen  1         1 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    0.05s  (  0.06s elapsed)
GC      time    0.00s  (  0.00s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    0.06s  (  0.06s elapsed)

%GC     time       0.4%  (0.4% elapsed)

Alloc rate    928,001 bytes per MUT second

Productivity  99.0% of total user, 95.1% of total elapsed

and more-or-less equivalent core (cleanST's is cleaner), but is really as dirty as it looks. I cannot recommend going down that route except in extreme circumstances.

Note: new (better) timings, the machine was busier when the original runs were made


Trie data structure in Java I have implemented a trie data structure in my way, though it is very similar to what major implementations I found but would like to get it reviewed by experts.

I don't see the need to store character in TrieContainer class as position within the series reflects the character stored. Maybe I am missing something and am wrong in my understanding.

Trie container

package trie;

public class TrieContainer{
    public boolean isEnd;
    public TrieContainer[] series = new TrieContainer[26];
}

Operations class

package trie;

public class Trie {

    public static void main(String[] args) {
        TrieContainer start = new TrieContainer();

        storeWords(start, "abc");
        storeWords(start, "abcd");
        storeWords(start, "abcde");
        storeWords(start, "india");
        storeWords(start, "hello");
        storeWords(start, "hell");

        printWordStrings(start,"");

        System.out.println("\n"+isWordPresent(start, "abcd"));
    }

    private static void storeWords(TrieContainer start, String word){
        for (int j = 0; j < word.length(); j++) {
            char character = word.charAt(j);

            //In series, check the position of character,
            //if it is already filled then check the series of filled Trie object.
            //if it is not filled then create new TrieContainer object and place it at correct position, and check
            //if it is end of the word, then mark isEnd = true or else false;
            if(start.series[character-97]!=null){
                if(word.length()-1 == j){ //if word is found till last character, then mark the end as true.
                    start.series[character-97].isEnd = true;
                }
                start = start.series[character-97];
            }else{
                TrieContainer trie = new TrieContainer();
                trie.isEnd = (word.length()-1 == j ? true:false);
                start.series[character-97] = trie;
                start = start.series[character-97];
            }
        }
    }

    private static boolean isWordPresent(TrieContainer start, String word){
        boolean isFound = true;
        for (int i = 0; i < word.length(); i++) {
            char character = word.charAt(i);

            //if at character position TrieContainer object is present then character is found and
            //start looking for next character is word.
            if(start.series[character-97]!=null){
                if(word.length()-1 != i){
                    start = start.series[character-97];
                }else{
                    if(!start.series[character-97].isEnd){
                        isFound = false;
                    }
                }
            }else{
                isFound = false;
                break;
            }
        }
        return isFound;
    }

    private static void printWordStrings(TrieContainer start, String toPrint) {
        if(start==null){
            return;
        }
        if(start.isEnd){
            System.out.println(toPrint);
        }

        for (int i = 0; i < start.series.length; i++) {
            TrieContainer t = start.series[i];
            if(t!=null){
                printWordStrings(t, toPrint + (char)(97+i));
            }
        }
    }
}

TrieContainer[26] contains a magic number. Since we can calculate with char I'd write TrieContainer['Z' - 'A' + 1] to make it clear.

I'd use System.out.printf("\n%b", isWordPresent(start, "abcd")) rather than string concatenation System.out.println("\n"+isWordPresent(start, "abcd")).

I'd let if follow by a space to distinguish it from method invocations (as you do it with for). I'd also surround else with spaces.

You're inconsistent in surrounding operators with spaces or not. Do the former.

I'd rename isFound to isWordFound.

Since the variables character are just local to for I'd call them just ch.

character-97 can be replaced with ch - 'a' then.

Array indices can be char, too. So:

for (int i = 0; i < start.series.length; i++) {
    ...
    ... (char)(97+i));

... can be changed to:

for (char ch = 0; ch < start.series.length; ch++) {
    ...
    ... (ch + 'a'));

I think start isn't an ideal name. With this if(start.isEnd) looks somehow irritating.

Having just static methods in Trie and public variables in TrieContainer doesn't look well-designed.


Reducing verbosity of RomanNumeral class I point to my problem in the comments of my code.

I have a class RomanNumeral:

public class RomanNumeral {

    private String romaNumera;
    private String romans = "IVXLCDM";

    public RomanNumeral(String rn) {
        //sets rn to romaNumera and checks if rn is a valid roman numeral
    }

    public boolean equals(RomanNumeral rn) {
        //overrides .equals
    }

     public String toString() {
            //overrides toString();
    }

             public int getDecimalValue() {
        float[] valueOfNumeral = new float[romaNumera.length()];
        int result = 0;
        float calculatedRomanDecimal=.5f;
        for(int i = 0; i<romaNumera.length(); i++) {

            /* My attempt at shortening the code
            for(int j = 0; j<romans.length(); j++) {

                if ( romans.charAt(j)==( romaNumera.charAt(i) ) && (j)%2==0 ) {valueOfNumeral[i] = calculatedRomanDecimal*2f;}
                if ( romans.charAt(j)==( romaNumera.charAt(i) ) && (j)%2==1 ) {valueOfNumeral[i] = calculatedRomanDecimal*5f;}
            */
        //What I am trying to do above and what I did bellow was check which               Roman numeral was which, and assign a float value to the corresponding index in a float array. Say that I have a Roman numeral MCM. MCM is romaNumera of type string, and I compare each character in romaNumera to each character in romans. Since romaNumera.charAt(0)==romans.charAt(6), I assign valueOfNumeral[0] the value of 1000
                //The stuff bellow works, but I feel like there is a more efficient way

                if (romans.charAt(0)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 1;}
                if (romans.charAt(1)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 5;}
                if (romans.charAt(2)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 10;}
                if (romans.charAt(3)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 50;}
                if (romans.charAt(4)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 100;}
                if (romans.charAt(5)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 500;}
                if (romans.charAt(6)==(romaNumera.charAt(i))) {valueOfNumeral[i] = 1000;}

        }

        result = Math.round(valueOfNumeral[romaNumera.length()-1]);
        for (int j = valueOfNumeral.length-2; j>=0; j--){
            if (valueOfNumeral[j]<valueOfNumeral[j+1])
                result -= Math.round(valueOfNumeral[j]);
            else result += Math.round(valueOfNumeral[j]);
        }

        return result;
    }

} // class RomanNumerals

This compiles and does what I want it to do, however, I am trying to find a way to shorten the program so it doesn't require so many if statements.

First thing you can do is put them in else if statements. It doesn't reduce the code but it do at least reduce the number of case the program has to check each time.

Because right now if the first match is good, it'll still check all the other statements.

To remove the ifs:

The other thing you could do is a Map. Doing that would not really reduced the amount of code but would make the code more readable. See this topic to learn more about the load factor in the map and how to initialize it.

private static final Map<String, Integer> ROMAN_MAP;
static
{
    // Note1 : Since you know the number of items in the map, you can initialize
    // the map directly with 7 safe "spots".
    // Note2 : We initialize it at 10 which is Roughly (N / load) + 1
    Map<Character, Integer>tempMap = new HashMap<Character, Integer>(10);
    tempMap.put('I', 1);
    tempMap.put('V', 5);
    tempMap.put('X', 10);
    tempMap.put('L', 50);
    tempMap.put('C', 100);
    tempMap.put('D', 500);
    tempMap.put('M', 1000);
    romanMap= Collections.unmodifiableMap(tempMap);
}

Then you can access it just like that :

ROMAN_MAP.get(romaNumera.charAt(i));

Changes with the use of a map :

Also, as mentioned, get rid of the floats AND of the Math.round() calls they are useless since your function returns an int anyway an that there is no possibility of displaying floating points anyway.

Your function can then be reduced to the following :

public int getDecimalValue() {
    int result = 0;
    int length = romaNumera.length();

    for(int i = 0; i < length; i++){
        int current = ROMAN_MAP.get(romaNumera.chartAt(i));
        int j = i+1;

        // Check if there is a next element and if it's bigger than current
        if(j < length && current < ROMAN_MAP.get(romaNumera.chartAt(j)){
            result -= current;
        } else {
            result += current;
        }
    }
    return result;
}

I've put { everywhere since they don't slow the process running in anyway and to me they make the code more readable and reduce the possibilities of error when refactoring.


Curiously Recurring Template Pattern (CRTP) implementation I'm implementing Curiously Recurring Template Pattern(CRTP) in Java as follows.

The Interface:

/**
 * Reason for the generic Value<T extends Value>
 * Value<IntValue> x; // legal, IntValue implements Value interface so allowed
 * Value<Integer> x;  // illegal, does not implement Value interface
 */
@SuppressWarnings("rawtypes")
public interface Value<T extends Value> {
    T deepCopy();
}

Classes implementing it:

public class IntValue implements Value<IntValue> {
    Integer value;

    public IntValue(Integer value) {
        this.value = value;
    }

    public Integer getValue() {
        return value;
    }

    @Override
    public IntValue deepCopy() {
        return new IntValue(value);
    }
}
/**
* // Valid
* List<IntValue> ints = Arrays.asList(new IntValue(Integer.valueOf(5)));
* ArrayValue<IntValue> arr = new ArrayValue<>(ints);
*
* // Invalid
* List<Integer> ints = Arrays.asList(Integer.valueOf(5));
* ArrayValue<Integer> arr = new ArrayValue<>(ints);
*/
@SuppressWarnings("rawtypes")
public class ArrayValue<T extends Value> implements Value<ArrayValue<T>> {

    List<T> values;

    public ArrayValue() {
        this(new ArrayList<>());
    }

    public ArrayValue(List<T> values) {
        this.values = values;
    }

    @SuppressWarnings("unchecked")
    @Override
    public ArrayValue<T> deepCopy() {
        List<? super Value> copyValues = new ArrayList<>();
        values.forEach(value -> copyValues.add(value.deepCopy()));
        return new ArrayValue<T>((List<T>) copyValues);
    }
}

//Static Function using the interface
@SuppressWarnings("rawtypes")
public static Value sub(Value a, Value b)
{
    if(a instanceof IntValue && b instanceof IntValue)
    {
        return new IntValue( ((IntValue)a).getValue() - ((IntValue)b).getValue());
    }
    else
    {
        throw new TypeMismatchException("Operation not supported");
    }
    return NullValue.NULL_VALUE;
}

However I have to suppress warnings multiple times throughout the implementation.

Are the uses of suppress annotation justified?

As far I can tell this doesn't generate any warnings:

class IntValue implements Value<IntValue> {

    Integer value;

    public IntValue(Integer value) {
        this.value = value;
    }

    public Integer getValue() {
        return value;
    }

    @Override
    public IntValue deepCopy() {
        return new IntValue(value);
    }
}

class ArrayValue<T extends Value<T>> implements Value<ArrayValue<T>> {

    List<T> values;

    public ArrayValue() {
        this(new ArrayList<>());
    }

    public ArrayValue(List<T> values) {
        this.values = values;
    }

    @Override
    public ArrayValue<T> deepCopy() {
        List<T> copyValues = new ArrayList<>();
        values.forEach(value -> copyValues.add(value.deepCopy()));
        return new ArrayValue<>(copyValues);
    }
}

But it makes more sense to do it without CRTP:

public interface Value<T> {
    Value<T> deepCopy();
    T getValue();
}

class IntValue implements Value<Integer> {

    Integer value;

    public IntValue(Integer value) {
        this.value = value;
    }

    @Override
    public Integer getValue() {
        return value;
    }

    @Override
    public IntValue deepCopy() {
        return new IntValue(value);
    }
}

class ArrayValue<T> implements Value<List<Value<T>>> {

    List<Value<T>> values;

    public ArrayValue() {
        this(new ArrayList<>());
    }

    public ArrayValue(List<Value<T>> values) {
        this.values = values;
    }

    @Override
    public ArrayValue<T> deepCopy() {
        List<Value<T>> copyValues = new ArrayList<>();
        values.forEach(value -> copyValues.add(value.deepCopy()));
        return new ArrayValue<>(copyValues);
    }

    @Override
    public List<Value<T>> getValue() {
        return values;
    }
}

class X {

    public static Value sub(Value<Integer> a, Value<Integer> b) {
         return new IntValue(b.getValue() - b.getValue());
    }
}


Removing duplication in horizontal and vertical checks // Check horizontals
for (int y = 0; y < sGridHeight; y++)
{
    Shape* groupShape = nullptr;
    int groupSize = 0;
    for (int x = 0; x < sGridWidth; x++)
    {
        GridItem* gridItem = GetItem(x, y);
        Shape* shape = gridItem->GetShape();
        if (shape == groupShape)
        {
            groupSize++;
            if (groupSize == m_MatchSize)
            {
                g_Audio->PlaySound(m_GemDestroyedSound.c_str());
                m_Score += shape->GetScore();
                for (int tx = x - m_MatchSize + 1; tx <= x; tx++)
                {
                    RANDOMIZE(GetItem(tx, y))
                }
                return;
            }
        }
        else
        {
            groupSize = 1;
            groupShape = shape;
        }
    }
}

// Check verticals
for (int x = 0; x < sGridWidth; x++)
{
    Shape* groupShape = nullptr;
    int groupSize = 0;
    for (int y = 0; y < sGridHeight; y++)
    {
        GridItem* gridItem = GetItem(x, y);
        Shape* shape = gridItem->GetShape();
        if (shape == groupShape)
        {
            groupSize++;
            if (groupSize == m_MatchSize)
            {
                g_Audio->PlaySound(m_GemDestroyedSound.c_str());
                m_Score += shape->GetScore();
                for (int ty = y - m_MatchSize + 1; ty <= y; ty++)
                {
                    RANDOMIZE(GetItem(x, ty))
                }
                return;
            }
        }
        else
        {
            groupSize = 1;
            groupShape = shape;
        }
    }
}

Is there an easy way to clean this up? It seems like a lot of code duplication.

I have no qualms about using #defines, and I cannot use C++11.

The most straightforward way to do this is to introduce a new boolean variable horz that is true in the case that you wish to check horizontals.  With that simple addition, both routines now can be expressed as one:

// if (horz) is true, check horizontals, else check verticals
aLimit = horz ? sGridHeight : sGridWidth;
bLimit = horz ? sGridWidth : sGridHeight;
for (int a = 0; a < aLimit; a++)
{
    Shape* groupShape = nullptr;
    int groupSize = 0;
    for (int b = 0; b < bLimit; b++)
    {
        GridItem* gridItem = (horz ? GetItem(b, a) : GetItem(a, b));
        Shape* shape = gridItem->GetShape();
        if (shape == groupShape)
        {
            groupSize++;
            if (groupSize == m_MatchSize)
            {
                g_Audio->PlaySound(m_GemDestroyedSound.c_str());
                m_Score += shape->GetScore();
                for (int tb = b - m_MatchSize + 1; tb <= b; tb++)
                {
                    RANDOMIZE(horz ? GetItem(tb, a) : GetItem(a, tb));
                }
                return;
            }
        }
        else
        {
            groupSize = 1;
            groupShape = shape;
        }
    }
}

However, there are a number of things that suggest opportunities for further improvement.  In particular, the use of pointers is probably not a good idea.  For example, these two lines:

    GridItem* gridItem = (horz ? GetItem(b, a) : GetItem(a, b));
    Shape* shape = gridItem->GetShape();

Are the only place that the gridItem pointer is used, and it's not checked for nullptr before it's dereferenced.  So either that's a bug if GetItem() could possibly return a nullptr or it should instead be written as a reference.  Even better, it could be combined into a single line and the variable eliminated completely.

Using this modified code is OK, but it's still a little unwieldy, so I would suggest that the GetItem() function should take a third argument which is the bool horz.  That would make those same two lines of code look like this:

    Shape* shape = GetItem(a, b, horz).GetShape();

Much nicer, but again, I'd turn this pointer into a reference (or better yet, a const reference if possible).


Improving script performance for looping unparalleled arrays Ive written a script to loop through a couple of unparalleled arrays a loop within a loop, Now im trying to find out if using break is all that's needed to exit and then continue over again.

What eles can you see or know to improve this?

var arr_vals = ["74","f4e3","22","r31","17","hundernds"]; // could have 500+ items
var arr_items = ["r31","22","65","100"]; // could have 50 items

var c = arr_items.length;
var arr_vals_len = arr_vals.length;
 for ( var i = 0; i < c; i++ ) {
   var xid = arr_items[i];

     for (var j = 0; j < arr_vals_len; j++ ){
      if(arr_vals[j] === xid){
      // match !
      break;
}
 }

Instead of iterating through the inner array multiple times, it might be faster to create a map for the inner array beforehand and then test for a match within the map. (I think this will only work if they're arrays of strings, though.)

var arr_vals = ["74","f4e3","22","r31","17","hundernds"]; // could have 500+ items
var arr_items = ["r31","22","65","100"]; // could have 50 items

var vals_len = arr_vals.length;
var items_len = arr_items.length;

var map_items = {};
for(var j = 0; j < items_len; ++j) {
  map_items[arr_items[j]] = 1;
}

for( var i = 0; i < vals_len; ++i) {
  if(map_items[arr_vals[i]]) {
    // match!
  }
}

Perf test


Should I set a license in the constructor or a static constructor? We are using the Aspose PDF library to work with PDF files. Aspose requires the license to be set once per process. Accordingly, I have created the following common static method that sets the license. Any code that needs Aspose will call into this method.

public class ConfigurationService
{
    private static bool isAsposePdfLicenseSet = false;

    public static void SetAsposePdfLicense()
    {
        if (isAsposePdfLicenseSet)
        {
            return;
        }

        // Set the license... (Moderately expensive - accesses the file system)

        isAsposePdfLicenseSet = true;
    }
}

I need to make sure the license is set before using my class, PdfInspector, but I only need to set it once, so I gave that class a static constructor:

static PdfInspector()
{
    ConfigurationService.SetAsposePdfLicense();
}

However, when I run Code Analysis in Visual Studio, it tells me that static constructors should be avoided. The alternative is to set the license in the constructor:

internal PdfInspector()
{
    ConfigurationService.SetAsposePdfLicense();
}

While this would be called every time the class is instantiated, the SetAsposePdfLicense would short circuit before doing any real logic. Bottom line, which implementation is preferable or is there an alternative that I haven't considered?

This is what made me want to answer:

// Set the license... (Moderately expensive - accesses the file system)

You do not want any constructor, static or not, to do work like this. A constructor that accesses the file system is screaming "I CAN BLOW UP ANYTIME!", and can throw file system -related exceptions. You don't want that in a constructor, even less a static one:

  A static constructor is used to initialize any static data, or to perform a particular action that needs to be performed once only. It is called automatically before the first instance is created or any static members are referenced.

  http://msdn.microsoft.com/en-us/library/k9x6w0hc.aspx

Making your field static ensures that the type (not the instance) has the field value, and your logic ensures it's set only once in the lifetime of your application. If your application isn't starting any process (requirement is once per process, right?), it can probably work.

I don't like that you're assuming that your application will only ever call this method in the same process though - it's a fair assumption to make, but since the requirements say once per process, I think your code should account for System.Diagnostics.Process.GetCurrentProcess().Id, and call the SetAsposePdfLicense() method if the method wasn't called in the process your code is running in.

I'm thinking of a factory living in a Singleton scope (or just as a plain Singleton), that would maintain an ICollection<int> (a HashSet<int> would be ideal for this) where each item is a process ID for which SetAsposePdfLicense was called.

public class PdfInspectorFactory
{
    private readonly ICollection<int> _processes = new HashSet<int>();

    private void SetLicenseForCurrentProcess()
    {
        var currentProcessId = System.Diagnostics.Process.GetCurrentProcess().Id;
        if (_processes.Contains(currentProcessId))
        {
            return;
        }

        // set the license...

        _processes.Add(currentProcessId);
    }

    public PdfInspector Create()
    {
        SetLicenseForCurrentProcess();
        var inspector = new PdfInspector();

        // do whatever you need to do with your inspector before returning it

        return inspector;
    }
}

Then your client code can use this PdfInspectorFactory and call its Create method to get a PdfInspector without having to care about whether or not the license is set.

The client code will not call the factory method in its constructor, rather only when it needs it.

public class SomeClass
{
    private readonly PdfInspectorFactory _factory;

    public SomeClass(PdfInspectorFactory factory)
    {
        _factory = factory;
    }

    public void DoSomething()
    {
        try
        {
            var inspector = _factory.Create();
            // here you go, now do what you need to do with your inspector...

        }
        catch(Exception exception)
        {
            // todo: log or otherwise report exception
            throw;
        }
    }
}

The factory instance should only exist as a Singleton instance - if you're using an IoC container that is very easy to accomplish. Otherwise you need to implement the factory class itself, as a Singleton.


Checking for any character common to two strings — Go is 50× slower than Python I decided to learn Go, knowing Python. My approach is by solving easy problems like this one:

  You are given two strings, A and B. Find if there is a substring that
  appears in both A and B. Several test cases will be given to you in a
  single file. The first line of the input will contain a single integer
  T, the number of test cases.

  Then there will be T descriptions of the test cases. Each description
  contains two lines. The first line contains the string A and the
  second line contains the string B.
  For each test case, display YES (in a newline), if there is a common substring. Otherwise, display NO.

The problem is straightforward: check if two sets intersect.

The real problem is that for the biggest testcase (20 strings of length 105 each) my Go code takes 2.6 seconds, which is unacceptable, knowing that my Python code solves the problem in 0.08 seconds. Based on the fact that Go is claimed to be near C speed, I assume that I am doing something super inefficiently.

package main
import "fmt"

func subst(s1 string, s2 string) bool {
    m := map[uint8]bool{}

    for i := 0; i < len(s1); i++ {
        m[s1[i]] = true
    }

    for i := 0; i < len(s2); i++ {
        if m[s2[i]] {
            return true
        }
    }
    return false
}

func main() {
    var n int
    var s1, s2 string

    fmt.Scanf("%d", &n)
    for i := 0; i < n; i++ {
        fmt.Scanf("%s", &s1)
        fmt.Scanf("%s", &s2)
        if subst(s1, s2) {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
    }
}

Python implementation:

def twoStrings(a, b):
    if len(set(a) & set(b)):
        print 'YES'
    else:
        print 'NO'

for i in xrange(input()):
    twoStrings(raw_input(), raw_input())

Nonetheless, two snippets look really different, they are actually doing similar things. In go I create a hash-map and put boolean value for each character from the first string (this is how sets are implemented in a lot of languages) and then for each character from the second string I am checking whether it is in a map and if no - exiting. It's obvious in the Python code.

This entire answer refers to my rewrite of the asker's code on the Go Playground and is mostly a summary of our discussion on the chat.so Go/Golang room. For reference, I'm reproducing the code below:

package main

import (
    "bufio"
    "io"
    "os"
    "strconv"
)

// charSet is a limited bitset to contain all lowercase latin characters (a-z).
type charSet struct {
    bits uint32
}

// Set switches a bit to 1 for any given character i that is in the range 'a'
// to 'z'. Characters outside this range have undefined behavior.
func (c *charSet) Set(i uint8) {
    c.bits |= 1 << (i - 'a')
}

// Intersects returns whether two charSets intersect (i.e., share one or more
// on bits).
func (c charSet) Intersects(o charSet) bool {
    return c.bits&o.bits != 0
}

// set returns a charSet for all bytes in s. Bytes in s must be in the range of
// 'a' to 'z'. Anything outside that range is regarded as undefined behavior.
func set(s []byte) charSet {
    var c charSet
    for i := 0; i < len(s); i++ {
        c.Set(s[i])
    }
    return c
}

// subst returns whether two strings share any characters. l and r are assumed
// to only contain characters in the range of 'a' to 'z'.
func subst(l, r []byte) bool {
    return set(l).Intersects(set(r))
}

func main() {
    var n int
    r := bufio.NewReader(os.Stdin)

    if l, err := r.ReadString('\n'); err == nil && len(l) > 1 {
        if n, err = strconv.Atoi(l[:len(l)-1]); err != nil {
            panic(err)
        }
    } else if err != nil {
        panic(err)
    }

    for i := 0; i < n; i++ {
        var s1, s2 []byte
        var err error
        s1, err = r.ReadBytes('\n')
        if err == nil {
            s2, err = r.ReadBytes('\n')
        }
        if err != nil && err != io.EOF {
            panic(err)
        }
        if len(s1) > 0 && len(s2) > 0 && subst(s1[:len(s1)-1], s2[:len(s2)-1]) {
            io.WriteString(os.Stdout, "YES\n")
        } else {
            io.WriteString(os.Stdout, "NO\n")
        }
    }
}

There are two major changes here to get this to the point that it at least beats Python in my own test runs on HackerRank:

Replace fmt.Scanf with just reading and parsing where necessary. The only input that requires actual parsing is the first integer, so there's no need for fmt.Scanf beyond that. Even initially we don't need it, however, because we're really only interested in parsing the first line. As such, I just replaced the entire thing with a buffered reader and read up to a delimiter, assuming that all lines end with '\n' (they should for this case). After that, I just run the first line through strconv.Atoi.

This chops off a reasonable amount of time in reading because it avoids parsing a format string and then modifying the input read to conform to the format string, as well as possible time spent in reflection depending on the data. I don't think it'll actually hit the reflect package here, but I haven't looked at the fmt.Fscanf implementation, so take that with a grain of salt.
Use a limited bitset (i.e., just one integer) instead of map[uint8]bool. This is more obvious as to why it's faster: there's no need to allocate more than four bytes on the stack to use an integer, and because the problem constrains the input strings to lowercase characters in the range of 'a' to 'z', we know it'll fit in the bounds of a 32-bit integer.

The charSet type and set function (which is just me being lazy and sort of mimicking the Python code) covers the entire implementation of this. All it does is, given a byte, update the underlying bits integer and test for an intersection using a bitwise and. To get a complete bitset for a string, or byte slice, just iterate over its length and set those bits.

This results in pretty simple code, an acceptable interface for working with a bitset that makes changes to the implementation easier, and it's much faster than allocating memory for a map, creating new cells in the map, and lookups in the map. (I think it's likely that some improvement would be seen by giving the map enough initial capacity for the cardinality of its key, but I doubt if it'd be significant — haven't tested it, so that's something to look into.) These are all fast enough for day to day things, but if we're trying to beat the time on some program, data structures are low-hanging fruit.

With those changes, I get, at worst, 0.01s on HackerRank for test #4 and #5 (possibly both — I'm guessing it's rounding at this point) and 0s for all other tests. This is also fairly easy to benchmark using the testing package, but I don't have a way to compare those results with Python's, so I consider HackerRank's authoritative for now.


Opening and validating an XML file I have a section of code that repeats many lines and I am looking to refactor this code possibly so that a function can be used instead of the same lines of code each time. Below is the section of code and the repeating code occurs in each if statement

Traversal::Traversal(string source, bool isFileName)
 {
      using namespace XML_Parser;
      using std::endl;

      std::ostringstream ppd;
  if (isFileName)
  {
      string content, line;
      std::ifstream file(source);
      if (! file)
      {
          ppd << endl << "error opening file " << source;
          cRep = ppd.str();
          cSuc = false;
          return;
      }
      ppd << endl << " file " << source << " opened ";
      while (file.good())
      {
          getline(file, line);
          content += '\n';
          content += line;
      }
      ppd << endl << "file " << source << " read ";
      source = content;
  }
  if (! elementExists(source,"afcd"))
  {
      ppd << endl << "no afcd tag";
      cRep = ppd.str();
      cSuc = false;
      return;
  }
  if (! elementExists(source,"rteirl"))
  {
      ppd << endl << "no rteirl tag";
      cRep = ppd.str();
      cSuc = false;
      return;
  }

How would I go about making this cleaner?

The basic aim is to put repeating parts in the function, while passing as a parameter anything that's different:

if (elementMissing(source, "afcd")) {
    return;
}

if (elementMissing(source, "rteirl")) {
    return;
}

bool elementMissing(source, element) {
    if (! elementExists(source, element)) {
        ppd << endl << "no " << element << " tag";
        cRep = ppd.str();
        cSuc = false;
        return true;
    } else {
        return false;
    }
}

I'm not sure what cRep and cSuc are supposed to be doing, so I can't help you with that part.


Daily Add/Del Git Log Analysis I just finished writing this Python script to calculate daily additions and subtractions from my git log to use in making pretty graphs. This is a rewrite of something I wrote previously in Perl. I have made an attempt to clean it up, but I feel that some of my list comprehensions are messy to say the least, and I'm abusing certain Python features.

#!/usr/bin/env python
# get-pmstats.py
# Henry J Schmale
# November 25, 2017
#
# Calculates the additions and deletions per day within a git repository
# by parsing out the git log. It opens the log itself.
# Produces output as a CSV
#
# This segments out certain file wildcards

import subprocess
from datetime import datetime
from fnmatch import fnmatch

def chomp_int(val):
    try:
        return int(val)
    except ValueError:
        return 0

def make_fn_matcher(args):
    return lambda x: fnmatch(''.join(map(str, args[2:])), x)

def print_results(changes_by_date):
    print('date,ins,del')
    for key,vals in changes_by_date.items():
        print(','.join(map(str, [key, vals[0], vals[1]])))

EXCLUDED_WILDCARDS = ['*.eps', '*.CSV', '*jquery*']

changes_by_date = {}
git_log = subprocess.Popen(
    'git log --numstat --pretty="%at"',
    stdout=subprocess.PIPE,
    shell=True)

date = None
day_changes = [0, 0]
for line in git_log.stdout:
    args = line.decode('utf8').rstrip().split()
    if len(args) == 1:
        old_date = date
        date = datetime.fromtimestamp(int(args[0]))
        if day_changes != [0, 0] and date.date() != old_date.date():
            changes_by_date[str(date.date())] = day_changes
            day_changes = [0, 0]
    elif len(args) >= 3:
        # Don't count changesets for excluded file types
        if True in map(make_fn_matcher(args), EXCLUDED_WILDCARDS):
            continue
        day_changes = [sum(x) for x in zip(day_changes, map(chomp_int, args[0:2]))]
print_results(changes_by_date)

I would apply the following improvements:

use collections.defaultdict to count down the number of added and deleted lines separately. This would help to improve the counting logic and avoid having to check for the old date at all
use any() to check for the excluded wildcards
unpack args into added, deleted lines and a filename
switch to gitpython from subprocess

The new version of the code:

from collections import defaultdict
from datetime import datetime
from fnmatch import fnmatch

import git

EXCLUDED_WILDCARDS = ['*.eps', '*.CSV', '*jquery*']

def chomp_int(val):
    try:
        return int(val)
    except ValueError:
        return 0

repo = git.Repo(".")
git_log = repo.git.log(numstat=True, pretty="%at").encode("utf-8")

added, deleted = defaultdict(int), defaultdict(int)

for line in git_log.splitlines():
    args = line.decode('utf8').rstrip().split()

    if len(args) == 1:
        date = datetime.fromtimestamp(int(args[0])).date()
    elif len(args) >= 3:
        added_lines, deleted_lines, filename = args

        # Don't count changesets for excluded file types
        if any(fnmatch(filename, wildcard) for wildcard in EXCLUDED_WILDCARDS):
            continue

        added[date] += chomp_int(added_lines)
        deleted[date] += chomp_int(deleted_lines)

for date, added_lines in added.items():
    print(date, added_lines, deleted[date])


Join JSON objects on common property is there an easier/more efficient way to join two JSON objects on a common property than this? It's a GeoJSON file (basically an array of objects), and I want to pull in a property from another JSON file (array of objects) based on a common property, similar to a SQL SELECT a.*, b.* FROM a LEFT JOIN b ON a.id = b.a_id

$.when(
    $.getJSON('https://data.phila.gov/resource/bbgf-pidf.geojson'),
    $.getJSON('https://data.phila.gov/resource/r24g-zx3n.json?%24select=count(*)%20as%20value%2C%20%3A%40computed_region_bbgf_pidf%20as%20label&%24group=%3A%40computed_region_bbgf_pidf&%24order=value%20desc')
).done(function(responseGeojson, responseData) {
    var data = responseData[0]
    var geojson = responseGeojson[0]

    // Create hash table for easy reference
    var dataHash = {}
    data.forEach(function(item) {
        if(item.label) dataHash[item.label] = item.value
    })

    // Add value from hash table to geojson properties
    geojson.features.forEach(function(item) {
        item.properties.incidents = +dataHash[item.properties._feature_id] || null
    })

    console.log(geojson)
})

I notice a query on one of your urls. I suggest you use jQuery's $.param to construct the query cleanly.

For your first loop, you could use reduce instead of forEach to generate your hash. Additionally, you might want kill NaN early. You don't want to be carrying NaN in any data structure, otherwise you'll get some unexpected NaN in your code.

var dataHash = data.reduce(function(hash, item) {
  var value = +item.value
  hash[item.label] = isNaN(value) ? null : value;
  return hash;
}, {});

geojson.features.forEach(function(item) {
  item.properties.incidents = dataHash[item.properties._feature_id];
});

As for efficiency, I guess that's about it. You don't want to be nesting a lookup inside the other loop. Two separate loops is better then one nested inside another.


Twisting words! (boustrophedon formatting) I decided to implement properly the Code Golf challenge about twisting strings. I report the assignement verbatim for convenience:

  Twisting Words!

  Given a string and a positive integer. You must twist the string, back
  and forth.

  Example Input / Output

  Input

Programming Puzzles & Code Golf
4

  Output

Prog
mmar
ing
zzuP
les
oC &
de G
 flo

  Input

  The input can be taken in through STDIN, or function argument. The
  input will consist of a string and a positive integer, n. The
  integer will determine the length of each twisted line.

  The string is twisted back-and-forth. An input of HELLO, WORLD! and
  5 would look like:

  Output

  The output will be the twisted text. It may not any trailing
  whitespace. If the input string length is not divisible be the line
  length, add a space until the line is filled:

  An example of this:    Input

Hello, World!
5

  Output (Note the whitespace at the very end)

Hello
roW ,
ld!

My implementation

def twist(text, chunk_size)
   text
     .+(" " * ((text.length % chunk_size) - 1))
     .chars
     .each_slice(chunk_size)
     .each_with_index
     .map {|str, i| i.odd? ? str.reverse : str}
     .map(&:join)
     .join("\n")
end

puts twist("Hello, World!", 5)
puts
puts twist("foo bar baz", 7)

Looks fine to me. Only thing I'd change is the way the padding is done: You can use ljust instead, which seems a little more appropriate to me. Something like:

.ljust(text.length.fdiv(chunk_size).ceil * chunk_size, " ")

You can also use the with_index modifier on map instead of doing a separate each_with_index, i.e.:

.map.with_index { |chunk, index| index.odd? ? chunk.reverse : chunk }

Of course there are several approaches to this. For instance, you needn't necessarily use chars and then join. For instance:

def twist(text, chunk_size)
  text
    .ljust(text.length.fdiv(chunk_size).ceil * chunk_size, " ")
    .scan(%r/.{#{chunk_size}}/)
    .map.with_index { |chunk, index| index.odd? ? chunk.reverse : chunk }
    .join("\n")
end

I won't say it's a better solution, though. Fewer lines, sure, but the interpolated regex isn't pretty. But again, it's just to show an alternative approach.

You can also move the ljust, to avoid the long'ish bit of arithmetic:

def twist(text, chunk_size)
  text
    .scan(%r/.{1,#{chunk_size}}/)
    .map { |chunk| chunk.ljust(chunk_size, " ") }
    .map.with_index { |chunk, index| index.odd? ? chunk.reverse : chunk }
    .join("\n")
end

It's obviously it's kinda brute-force, since we know that it'd only be the last chunk that could require padding. But again: Just an alternative.


Managing a CSV of users and permissions I've got a CSV that contains users and permissions in the below format, where users can have as little as one or as many as eight different permissions:

USER,PERM1,PERM2,PERM3,PERM4,PERM5,PERM6,PERM7,PERM8
jdoe,perm1,perm2
tsmith,perm1,perm2,perm3,perm4,perm5,perm6,perm7,perm8

This is the desired format, with each unique user and permission pair on a new line:

USER,PERM
jdoe,perm1
jdoe,perm2
tsmith,perm1
tsmith,perm2
tsmith,perm3
tsmith,perm4
tsmith,perm5
tsmith,perm6
tsmith,perm7
tsmith,perm8

My script below accomplishes this, but it's ugly, repetitive and I know there's a more Pythonic way to do it. Even worse, I had to bring the output file into Excel afterwards to filter and delete the rows with blank PERM values. Any recommendations to shorten this code and cut down on repetition would be much appreciated.

import csv

def reformat_ul(original_ul, formated_ul):
    with open(original_ul) as user_list:
        dict_reader = csv.DictReader(user_list)
        ul = []
        for row in dict_reader:
            ul.append(row)

    with open(formated_ul, 'w') as output2:
        output2.write('USER,PERM\n')
        for uperm in ul:
            p1 = '{},{}\n'.format(uperm['USER'], uperm['PERM1'])
            p2 = '{},{}\n'.format(uperm['USER'], uperm['PERM2'])
            p3 = '{},{}\n'.format(uperm['USER'], uperm['PERM3'])
            p4 = '{},{}\n'.format(uperm['USER'], uperm['PERM4'])
            p5 = '{},{}\n'.format(uperm['USER'], uperm['PERM5'])
            p6 = '{},{}\n'.format(uperm['USER'], uperm['PERM6'])
            p7 = '{},{}\n'.format(uperm['USER'], uperm['PERM7'])
            p8 = '{},{}\n'.format(uperm['USER'], uperm['PERM8'])
            output2.write(p1)
            output2.write(p2)
            output2.write(p3)
            output2.write(p4)
            output2.write(p5)
            output2.write(p6)
            output2.write(p7)
            output2.write(p8)

reformat_ul('user_list.csv', 'output.txt')

This is shorter:

import csv

def reformat_ul(original_ul, formated_ul):
    with open(formated_ul, 'w') as output2:
        output2.write('USER,PERM\n')
        with open(original_ul) as user_list:
            dict_reader = csv.DictReader(user_list)
            for row in dict_reader:
                user = row['USER']
                for key in sorted(row)[:-1]:
                    if row[key]:
                        output2.write("%s,%s\n" % (user, row[key]))

reformat_ul('user_list.csv', 'output.txt')

The highlights:

It doesn't waste memory by storing the rows in a temporary list. Using the two nested with there, it outputs while reading the output, piping properly
In sorted(row)[:-1] I take advantage of the fact that I know the column names, and that USER will come after all the PERM1..PERM8. If you need a more flexible implementation then you can amend the deepest if there, for example if key.startswith('PERM') and row[key]


Simple rate limiting class in Ruby The idea of this class is I would be able to limit the use of an API/method by sending it a key which would be an IP address or username and it would tell me if they are under the rate limit.

require 'time'

class RateLimit
    def initialize(time, limit)
        @reset_on = Time.now + time
        @limit = limit
        @keys = {}
    end

    def increment(key)
        reset if Time.now >= @reset_on

        if @keys[key] == nil
            @keys[key] = 1
        else
            @keys[key] += 1
        end
        return @keys[key] >= @limit
    end

    def current_level(key)
        reset if Time.now >= @reset_on
        return @keys[key]
    end

    def is_limited?(key)
        reset if Time.now >= @reset_on
        return @keys[key] != nil && @keys[key] >= @limit
    end

    def reset
        @reset_on = Time.now + @limit
        @keys = {}
    end
end

To me this seems like some pretty clean code but are there any issues I have missed or things that could be done better?

So there is a flaw in this approach. It limits requests based on the current time, and not by how many requests happened in the last amount of time. Let me give you an example. We'll start at time 0 with a limit of 10 requests per every seconds.

Time | Requests (total)
--------------
0    |     0
1    |     0
2    |     0
3    |     0
4    |     0
5    |     0
6    |     0
7    |     1
8    |     3
9    |     10 # requests start getting limited
10   |     10
# your request tracking resets here and requests are no longer limited
11   |     15
12   |     18
13   |     20
14   |     20
...

Do you see the issue? Between seconds 9 to 13 (4 seconds), we had a total of 17 requests when only want to allow 10 requests per every 10 seconds.

This shows that the initial approach is flawed.

In terms of code quality, I see a few things that could be improved:

1) Variable and method names:

@keys = {} is not immediately clear what it holds. However, if it were called requests_per_ip_address I would know. Long variable names better if they describe what they're holding.

is_limited? could just be limited?

2) Working with nil you should use #nil?

For example: @keys[key] == nil could be @keys.nil?
and @keys[key] != nil could be !@keys[key].nil?

3) Don't return at the end of methods.
The last line or branch of a method is what gets returned. The explicit return is not necessary.

4) Use private. Anyone can call any method on your rate limiter, but we only want a couple of methods to be public.

5) Use a linter. Check out RuboCop. You will be surprised by all of the style rules you break!

Here is an example of how I might write this class:

class RateLimit
  def initialize(maximum_requests, time_limit)
    @maximum_requests = maximum_requests
    @time_limit = time_limit
    @user_requests = Hash.new { |h, k| h[k] = [] }
  end

  def increment(ip_address)
    return false unless user_under_limit? ip_address
    @user_requests[ip_address] << Time.now
    true
  end

  def user_under_limit?(ip_address)
    remove_first_expired_request ip_address
    @user_requests[ip_address].count < @maximum_requests
  end

  private

  def remove_first_expired_request(ip_address)
    # We can just remove the first request if it is expired
    # and that will make room for a new request
    if @user_requests[ip_address].first < Time.now - @time_limit }
      @user_requests[ip_address].shift
    end
  end
end