Creating boilerplate for jQuery plugins I've been writing some smaller jQuery plugins lately, and I've been thinking of writing up some boilerplate that I can use when writing new ones. I have code that works (for now), but I want to share it and get feedback on things I may be missing as I move to larger plugins.

/**
*  jQuery Plugin Boilerplate
*  - find and replace the following variable names
*    - utilities   : namespace for shared utility functions
*    - PluginClass : class name for plugin object
*    - pluginName  : the name of your plugin function, e.g. $('.foo').myPlugin()
**/
(function($) {

    /**
    *  Utility function object
    *  - namespace wrapper for variables or functions shared between all plugin instances
    **/
    var utilities = {

        // example utility function
        getInt: function(i) {
            i = parseInt(i, 10);
            return isNaN(i) ? 0 : i;
        }

    },

    /**
    *  Main plugin class
    *  - encapsulate each instance of plugin as an object
    **/
    PluginClass = {

        // other instance-specific functions get defined here

        init: function(el,options) {
            var _t = this;  // for maintaining reference to plugin class in callbacks

            this.options = $.extend({}, $.fn.pluginName.defaults, options);
            this.el = el;
            this.$el = $(el);

            // do your plugin stuff
        },

        callFn: function(fn) {
            switch(fn) {
              // case statements matching allowable function aliases
              // which execute the appropriate plugin functions
            }
        }

    };

    /**
    *  Plugin function
    *  - for each element passed to the plugin, create a new class instance
    **/
    $.fn.pluginName = function () {
        var arg = arguments[0];
        var fn, options;

        // if the argument passed is a string, then the user
        // is calling a function. Otherwise, it's an options object
        if(typeof arg === 'string') {
            fn = arg;
        }
        else {
            options = arg;
        }

        if (this.length > 0) {
            return this.each(function(i) {
                var el = $(this), p;

                // if plugin instance already exists, use it
                if(el.data('pluginName')) {
                    p = el.data('pluginName');
                    if(fn) { p.callFn(fn); }
                    else { p.init(this,options); }
                } else {
                    p = Object.create(PluginClass);
                    el.data('pluginName', p);
                    p.init(this,options);
                }
            });
        }

    };

    /**
    *  Plugin default options
    *  - created outside of plugin function for easier overriding by user
    **/
    $.fn.pluginName.defaults = {
        some: thing,
        foo: 'bar'
    };

})(jQuery);

Here's an example I created using this boilerplate. It's nothing fancy, it simply takes the text of an element and paints each character with a different color.

jQuery Plugin Demo - $.paintText()

My main concern here is with the functionality of using $('#foo').paintText('fnAlias') to call a function on an existing plugin instance. My way seems to work, but part of me feels there may be a more efficient way.

Thanks for any help.

From a once over:

I like how you store both el and $el
I also like how you expose your defaults
Not sure about _t, I think generally self is considered to a better name for this
You should have a spot in your boilerplate to define the prototype of your plugin class
Lint finds nothing worth mentioning


Text parser implemented as a generator I often need to parse tab-separated text (usually from a huge file) into records. I wrote a  generator to do that for me; is there anything that could be improved in it, in terms of performance, extensibility or generality?

def table_parser(in_stream, types = None, sep = '\t', endl = '\n', comment = None):
  header = next(in_stream).rstrip(endl).split(sep)
  for lineno, line in enumerate(in_stream):
    if line == endl:
      continue # ignore blank lines
    if line[0] == comment:
      continue # ignore comments
    fields = line.rstrip(endl).split(sep)
    try:
      # could have done this outside the loop instead:
      # if types is None: types = {c : (lambda x : x) for c in headers}
      # but it nearly doubles the run-time if types actually is None
      if types is None:
        record = {col : fields[no] for no, col in enumerate(header)}
      else:
        record = {col : types[col](fields[no]) for no, col in enumerate(header)}
    except IndexError:
      print('Insufficient columns in line #{}:\n{}'.format(lineno, line))
      raise
    yield record

You also may use csv module to iterate over your file. Your code would be faster because of C implementation and cleaner without line.rstrip(endl).split(sep)


Function to show/hide a menu on hover How can I make this code snippet be improved to become more professional?

(function($){

  $.fn.showMenu = function(options){

    return this.each(function(){

      $this = $(this);
      var high         = $this.outerHeight(),
          scrollHeight = $this.get(0).scrollHeight;

      $this.bind('mouseenter',function(){
        $this.css({overflow:'visible'})
             .stop()
             .animate({height:scrollHeight},'fast');
      }).bind('mouseleave',function(){
        $this.animate({height:high}, function(){
          $this.css({overflow:'hidden'});
        });
      });
    });

  }//the end of $.fn.showMenu

  $('#theme_content').showMenu();

});

You could also use .hover, if you are going for shorter code.
Jquery Hover


Function to lock a file using memcache, Version 2 Based on suggested reviews for Function to lock a file using memcache, I have modified the code to

import os
import shutil
import memcache

def addToCart(filename, username):
    ableToLock = memcache.add(filename, username)
    if ableToLock:
        # "ableToLock" can happen if the file is still present
        # or if it was already processed.
        if os.file.ispath(filename):
            # I have a lock and file exists. Think of Cart as a
            # JS Object from where you can pick items to "process".
            return "Added To Cart"
        else:
            # I have a lock but looks like file was processed already.
            # So removing the residual "key" created.
            memcache.delete(filename)
            return "Processed by another user."
    else:
        # "add" can also fail if remote server is down,
        # but now we are not handling that now. It will
        # block the user's ability to process anything.
        user = memcache.get(filename)
        if user and os.file.ispath(filename):
           # I try my best to show the user processing it.
           print "Being processed by %s" % user
        else:
           # But lost the race to find that.
           print "Processed by another user."

def process(source):
    shutil.move(source, destination)
    filename = os.path.basename(source)
    memcache.delete(filename)

Directly calling process is not considered valid as it can only be done from user's Cart and by that user. If the logic is correct, Cart will only have valid files at any point of time and no two Carts would be having the same file ever. If a request from Cart comes to process a filename and it doesn't exist in the file-system then it is considered flawed.

Are there any race conditions or logical flaws that still exists?

logical flaw

If an exception happens, your key could remain locked.

You use

def addToCart(filename, username):
    ableToLock = memcache.add(filename, username)
    if ableToLock:
        # ableToLock can happen if the file is still present
        # or if it was already processed.
        if os.file.ispath(filename):
            # I have a lock and file exists. Think of Cart as a
            # JS Object from where you can pick items to "process".
            return "Added To Cart"
        else:
            # I have a lock but looks like file was processed already.
            # So removing the residual "key" created.
            memcache.delete(filename)
            return "Processed by another user."
    else:
        ...

def process(source):
    shutil.move(source, destination)
    # filename => source
    memcache.delete(filename)

What if shutil.move throws an exception? Or print?

Better would be

if ableToLock:
    try:
        # ableToLock can happen if the file is still present
        # or if it was already processed.
        if os.file.ispath(filename):
            # I have a lock and file exists. Think of Cart as a
            # JS Object from where you can pick items to "process".
            return "Added To Cart"
        else:
            return "Processed by another user."
    finally:
        memcache.delete(filename)


Number-guessing game in Python with a single level of abstraction I've read about keeping functions to the same level of abstraction, and it seems to make sense in all the examples. However, when translating to non-contrived programming, I'm still very unsure of my decisions. I'm especially unsure of where it applies. I wrote this guessing game to try to work on it, but it ended up feeling really clunky and redundant. How far should I go out of my way to flatten code? I read loops should ideally only be one function call, but that seems extreme. Is that really standard practice? If so, how would I refactor my main without needing a bunch of globals or really long parameter lists?

from random import randrange

DEFAULT_LO   = 1
DEFAULT_HI   = 100
HOT_DISTANCE = 10

def main():
    answer    = randrange(DEFAULT_LO, DEFAULT_HI+1)
    tries     = 1
    lastGuess = 0
    guess     = 0
    wasHot    = False

    won = False
    isFirstTry = True
    while (not won):
        lastGuess = guess
        guess = promptGuess()

        if validGuess(guess):
            if guess != answer:
                newDistance = abs(answer-guess)
                oldDistance = abs(answer-lastGuess)
                displayResult(newDistance, oldDistance, isFirstTry)

            else:
                displayWin(tries)
                won = True

            tries += 1
            isFirstTry = False

def promptGuess(lo=DEFAULT_LO, hi=DEFAULT_HI):
    guess = input('Enter a number ({}-{}): '.format(lo, hi))
    guess = int(guess)
    return guess

def validGuess(num, lo=DEFAULT_LO, hi=DEFAULT_HI):
    return (num >= lo and num <= hi)

def displayResult(newDistance, oldDistance, firstGuess):
    wasHot = (oldDistance <= HOT_DISTANCE)
    isHot = (newDistance <= HOT_DISTANCE)

    if firstGuess:
        displayHotCold(newDistance)

    elif newDistance is oldDistance: # Can happen with new answer if equally
        print('Same temperature!')   # far on opposite side of answer

    elif isHot:
        displayHotHotterCooler(newDistance, oldDistance, wasHot)

    else:
        displayColdWarmerColder(newDistance, oldDistance, wasHot)

def displayHotCold(newDistance):
    if newDistance <= HOT_DISTANCE:
        print('HOT!')

    else:
        print('Cold')

def displayHotHotterCooler(newDistance, oldDistance, wasHot):
    if not wasHot:
        print('HOT!!')

    elif newDistance < oldDistance:
        print('HOTTER!!!')

    else:
        print('COOLER')

def displayColdWarmerColder(newDistance, oldDistance, wasHot):
    if wasHot:
        print('COLD')

    elif newDistance < oldDistance:
        print('Warmer!')

    else:
        print('Colder')

def displayWin(tries):
    if tries is 1:
        print('WOW!! You got it on your first try!')
    else:
        print('GOOD JOB! You got it in {} tries.'.format(tries))

main()

When too many parameters are being passed around, object-oriented programming can help.  But I don't think that that is your problem here.  I think you have divided the work into functions suboptimally.  Some advice:

Document each function's purpose in a docstring.

If you can't write a good docstring, then perhaps the function is poorly conceived.  Can you tell me what the displayHotHotterCooler() function does?  If you had to write a docstring for it, it might say:

  Assuming that a guess is hot, and that it is not the player's first guess, print 'HOT!!', 'HOTTER!!!', or 'COOLER' depending on how it rates relative to the previous guess.

That's too complicated, I think.  The function already has two preconditions on its applicability.  Any attempt to describe it better would end up being more verbose than the code itself.  Furthermore, the name displayHotHotterCooler doesn't really summarize the function's purpose.  All these problems suggest that this is not a worthwhile function to define, because its purpose is not clear.

In contrast, my display_hint() function below does have a clear summarizable purpose:

  Print a message hinting at the player's progress towards guessing the target number.

Delegate, don't micromanage.

promptGuess() could be smarter.  It already knows what the valid range is, so why can't it perform the validation for you too?  That would relieve main() from having to call validGuess(), and would eliminate one level of indentation from main().

Part of not micromanaging is to let each function figure out what information it needs.  Instead of passing three parameters newDistance, oldDistance, and firstGuess, consider passing the entire history of guesses instead, as a list.  The called function can infer whether it's the first guess based on the length of the array.  It can easily extract the last two elements, as needed.  (Drawbacks are that you end up storing more state than is strictly necessary, and that you have to trust the called function not to mutate the list.  But I think it's a worthwhile tradeoff for simplicity.)

Suggested solution

from random import randrange

def user_guesses(lo, hi):
    """
    Yield prompted guesses from the user, all verified to be integers
    between lo and hi (inclusive).
    """
    while True:
        guess = int(input('Enter a number ({}-{}): '.format(lo, hi)))
        if lo <= guess <= hi:
            yield guess

def display_win(diffs):
    """
    Print a congratulatory message for winning.
    """
    if len(diffs) == 1:
        print('WOW!! You got it on your first try!')
    else:
        print('GOOD JOB! You got it in {} tries.'.format(len(diffs)))

def display_hint(diffs, hot_distance):
    """
    Print a message hinting at the player's progress towards guessing
    the target number.

    diffs is a sequence of absolute differences between the guesses
    and the target number.  hot_distance is the threshold distance
    for considering a guess to be "hot".
    """
    is_hot = diffs[-1] <= hot_distance
    was_hot = diffs[-2] <= hot_distance if len(diffs) > 1 else None
    if was_hot is None:
        print('HOT!' if is_hot else 'Cold')
    elif diffs[-1] == diffs[-2]:
        print('Same temperature!')
    elif is_hot:
        print('HOT!!' if not was_hot else
              'HOTTER!!!' if diffs[-1] < diffs[-2] else
              'COOLER')
    else:
        print('COLD' if was_hot else
              'Warmer!' if diffs[-1] < diffs[-2] else
              'Colder')

def main(lo=1, hi=100):
    """
    Pick a random number between lo and hi (inclusive), and let the
    player guess the number.  Temperature hints are printed until
    the player guesses correctly.
    """
    hot_distance = (hi - lo + 1) // 10      # 10% of the range
    answer = randrange(lo, hi + 1)
    diffs = []
    for guess in user_guesses(lo, hi):
        diffs.append(abs(guess - answer))
        if guess == answer:
            display_win(diffs)
            return
        display_hint(diffs, hot_distance)

main()

Other remarks:

Using the is operator to test for numeric equality is incorrect.  It only happens to work for some smaller numbers.

>>> 5 is -(-5)
True
>>> 1024 is -(-1024)
False
>>> 5 == -(-5)
True
>>> 1024 == -(-1024)
True

PEP 8, the official Python style guide, discourages extra spaces for the sake of aligning = signs.  It also recommends lower_case_with_underscores instead of interCaps naming.
Python support double-ended inequalities (lo <= num <= hi).
Instead of sprinkling references everywhere to hard-coded constants, I often prefer to define default parameters.
Flag variables, like won and isFirstTry, are almost always a sign that you can devise a better control structure.  Just eliminate them from your code.


Is this FizzBuzz code idiomatic Groovy? I'm new to Groovy but have some experience with Java, C and Python. I'd appreciate your feedback on Groovy style and features in this FizzBuzz code.

Review Checklist

Is it idiomatic Groovy code?
Can anything be taken away?
Can it be more functional?
Could I make use of any Groovy-specific features?

FizzBuzzTest.groovy

import org.fizzbuzz.FizzBuzz
import org.junit.Before
import org.junit.Test

class FizzBuzzTest {

    FizzBuzz fb

    @Before
    void setUp() {
        fb = new FizzBuzz()
    }

    @Test
    void testGiven1Returns1AsString() {
        assert '1' == fb.toString(1)
    }

    @Test
    void testGiven2Returns2AsString() {
        assert '2' == fb.toString(2)
    }

    @Test
    void testGiven3ReturnsFizz() {
        assert 'Fizz' == fb.toString(3)
    }

    @Test
    void testGiven5ReturnsBuzz() {
        assert 'Buzz' == fb.toString(5)
    }

    @Test
    void testGiven15ReturnsFizzBuzz() {
        assert 'FizzBuzz' == fb.toString(15)
    }
}

FizzBuzz.groovy

package org.fizzbuzz

class FizzBuzz {

    String toString(number) {
        if (isMultipleOf3(number) && isMultipleOf5(number))
            return 'FizzBuzz'
        if (isMultipleOf3(number))
            return 'Fizz'
        if (isMultipleOf5(number))
            return 'Buzz'
        number.toString()
    }

    private boolean isMultipleOf5(number) {
        isMultipleOf.curry(5)(number)
    }

    private boolean isMultipleOf3(number) {
        isMultipleOf.curry(3)(number)
    }

    private def isMultipleOf = { int multipleOf, number ->
        number % multipleOf == 0
    }

    static void main(String... args) {
        def fb = new FizzBuzz()
        for (num in 1..100) {
            println fb.toString(num)
        }
    }

}

Referring to 'Could I make use of any Groovy-specific features?':
You could use a Category to add a isMultipleOf() method to Integer. So you could write if (number.isMultipleOf3())
(see Groovy Goodness: Use Categories to Add Functionality to Classes)

class Multiple {
    static boolean isMultipleOf(Integer number, int multipleOf) {
        number % multipleOf == 0
    }
}

def foo = 5
use (Multiple) {
    if(foo.isMultipleOf(3))
        println "Fizz"
    else
        println "Buzz"
}


Java Stack Implementation I'm looking for a code review on my Stack Implementation in Java. Specifically I am looking for correctness, style, and efficiency. Thank you!

public class MyStack<T> {
    private int top;
    private T[] stackArray;
    private int size;

    public MyStack(int size) {
        this.size = size;
        this.stackArray = (T[]) new  Object[size];
        this.top = -1;
    }

    public void push(T element) {
        if(isFull()) {
            throw new IndexOutOfBoundsException();
        }
        this.stackArray[++top] = element;
    }

    public T pop() {
        if(isEmpty()) {
            throw new NullPointerException("Stack is empty");
        }
        return this.stackArray[top--];
    }

    public boolean isFull() {
        if(this.top==(size - 1)) {
            return true;
        }
        return false;
    }

    public boolean isEmpty() {
        if(this.top== -1) {
            return true;
        }
        return false;
    }

    public int getTop() {
        return top;
    }

    public T[] getStackArray() {
        return stackArray;
    }

    public void setStackArray(T[] stackArray) {
        this.stackArray = stackArray;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }
}

There's a potential bug here:

public T pop() {
    if(isEmpty()) {
        throw new NullPointerException("Stack is empty");
    }
    return this.stackArray[top--];
}

The problem with this code is that a reference to the object stays in the array.  You've decremented the index, but the array still has the reference sitting there.  This could result in an object not being garbage collected when the user expects it to be.  While technically this doesn't affect how your stack works, hanging on to references you don't need is generally considered poor practice.

Consider something like this (not tested):

public T pop() {
    if(isEmpty()) {
        throw new NullPointerException("Stack is empty");
    }
    T retVal = this.stackArray[top];
    this.stackArray[top--] = null;
    return retVal;
}


Project Euler Problem 5 I wrote up a small script to calculate the answer to Project Euler Problem 5:

  2520 is the smallest number that can be divided by each of the numbers
  from 1 to 10 without any remainder.

  What is the smallest positive number that is evenly divisible by all
  of the numbers from 1 to 20?

I'm wondering if this algorithm can be improved or made more efficient:

def divisible_by(num, den_set):
    if not den_set: return True
    elif not num % den_set.pop():
        return divisible_by(num, den_set)
    else: return False

def smallest(den_count):
    i = 1
    den_set = list(range(1, den_count))
    while not divisible_by(i, den_set):
        den_set = list(range(1, den_count))
        i += 1
    return i

print smallest(20)

The smallest number that can be divided by a set of numbers without any remainder is also known as the least common multiple, which can be calculated directly using the greatest common divisor (gcd).

The least common multiple of a, b:

lcm(a, b) = a * b / gcd(a, b)

The least common multiple of a, b, c:

lcm(a, b, c) = lcm(a, lcm(b, c))

You could generalize this to more numbers.


Javascript - varargs constructors, method chaining, and static methods I am wondering if the code beneath considered as the proper way to achieve the topics stated in the title of the post.

I wonder is the best practice for achieving it?

var Obj = function() {
    if (arguments.length) {
        //do something
        for (var i in arguments) //iterate over the arguments
            alert(arguments[i]);
    }
};

Obj.prototype.foo = function() {
    alert("foo");
    return this;
};

Obj.prototype.bar = function() {
    alert("bar");
    return this;
};

Obj.spam = function() {
    alert("spam");
};

//varargs constructor
var varargs = ["arg1", "arg2"];
new Obj();
new Obj(varargs);
new Obj("a", "b", 1, 2.5);

//method chaining
new Obj().foo().bar();

//static method
Obj.spam();

Answer: Yes, yes, and yes.

Honestly, I'm wondering how else you'd achieve it. The arguments object exists to let you access whatever was passed; return this is really the only way to allow chaining; and the "static" method is technically just an object property, and that's the way you define those.

Only things I'd add is that you can easily convert the arguments object - which is "array-like" but not actually an array - to a real array by saying [].slice.call(arguments, 0);. Useful for looping, slicing, etc.. And you should always use braces/curly brackets - even if the "block" is just 1 line - just good code hygiene. Oh, and when in doubt, use hasOwnProperty() in a for...in loops.


Regex to remove inline javascript from string I need to remove inline javascript for a given string. Examples:

If user typed:

I should need to convert into

I created this PHP code and it works(apparently without issues):

http://writecodeonline.com/php/

function test_input($input){
  //I have a list with all events but for this example I used two
  $html_events = 'onload|onclick';
  $pattern = "/(<[A-Z][A-Z0-9]*[^>]*)($html_events)([\s]*=[\s]*)('[^>]*'|\"[^>]*\")([^>]*>)/i";
  $replacement = '$1$5';
  while( preg_match($pattern, $input) ){
    $input = preg_replace($pattern, $replacement, $input);
  }
  return htmlentities($input);
}

echo test_input(''). '
';
echo test_input(''). '
';
echo test_input('
hello buddies
'). '
';

I'm just looking for improvements or use cases that I did not supporting or that break my regex. I would appreciate if you tell me:

This: test_input('something bad'); breaks your regex.

Or if found an improvement that in a benchmark demonstrate better performance I should be happy to apply it as long as it does not break use cases already supported.

Thank You!

Update
I finally used htmlpurifier

Parsing markup with regex is like building your house using lego... it's not the right tool for the job. HTML is not a regular language, therefore regular expressions don't cut the mustard. More than that: You're actively working to bring the world as we know it to an end, which drives people insane
What you need is a DOM parser, and as luck would have it, PHP has the DOMDocument object, which is just that:

$dom = new DOMDocument;
$dom->loadHTML('<img onload="alert(\'hello world\');" onclick="alert(\'hello world\');" />');
$nodes = $dom->getElementsByTagName('*');//just get all nodes,
//$dom->getElementsByTagName('img'); would work, too
foreach($nodes as $node)
{
    if ($node->hasAttribute('onload'))
    {
        $node->removeAttribute('onload');
    }
    if ($node->hasAttribute('onclick'))
    {
        $node->removeAttribute('onclick');
    }
}
echo $dom->saveHTML();//will include html, head, body tags and doctype

Tadaa... both onload and onclick have been removed from the markup, without the pain of writing a reliable and stable regex, that can deal with in-line JS... As an added bonus, this code will be far more maintainable (and expandable) in the future. I'd much prefer maintaining this code, than having to rework a regular expression somebody wrote a couple of months ago...

If you want, you can echo only the tags you've changed, like so:

$changed = array();
$attributesOfDeath = array('onload', 'onclick');
foreach($nodes as $node)
{
    $current = null;
    foreach($attributesOfDeath as $attr)
    {
        if ($node->hasAttribute($attr))
        {
            $node->removeAttribute($attr);
            $current = $node;
        }
    }
    if ($current)
    {
        $changed[] = $current;//add to changed array
    }
}
$changed = array_map(array($dom, 'saveXML'), $changed);
echo implode(PHP_EOL, $changed);

As Jan said, for maintainability it's best to use an array of "forbidden attributes". That's what the $attributesOfDeath array is for. If you want to, later on, check for a third or fourth attribute, you can simply add that to the array, and nothing else in your code need change. It'll just keep on working as before.


Beginning guessing game in Python I've just finished work on my guessing game. I'm still fairly new to Python, so I'm looking for feedback and criticism on the code.

def game():

    import random #imports the module 'random'

    yes={"Yes","Y","yes","y"} #set 'yes' to these 4 strings
    no={"No","N","no","n"} #set 'no' to these 4 strings

    name=input("What is your name? \n") #asks for a name

    secret=int(random.random()*10)+1 #randomly generate a number

    trynum=0 #sets the number of tries to 0

    print ("---------------------------------------------------------------------\n"
           "---- Welcome,",name+"!\n"
           "---- I am thinking of a number between 1 and 10.\n"
           "---- Lets see how many times it will take you to guess the number.\n"
           "---------------------------------------------------------------------\n")

    while True: #starts a loop

        trynum=trynum+1 #sets number of tries to itself + 1

        guess=int(input("What is guess #"+str(trynum)+"? \n")) #asks for a guess

        if guess<secret: #if guess is too low/less than(<)
            print ("Too Low. Try again!")

        elif guess>secret: #if guess is too high/greater than(>)
            print ("Oops!! Too high, better luck next try!")

        else:
            if trynum==1: #if number of tries is only 1
                print ("-------------------------------------------------\n"
                       "----",name+"! You got it in",trynum,"guess!\n"
                       "-------------------------------------------------\n")
            else: #if number of tries is anything else
                print ("-------------------------------------------------\n"
                       "----",name+"! You got it in",trynum,"guesses!\n"
                       "-------------------------------------------------\n")

            if trynum<3: #if guessed in less than 3 tries
                print ("Bravo!")

            elif trynum<5: #if guessed in less than 5 tries
                print ("Hmmmmpf... Better try again")

            elif trynum<7: #if guessed in less than 7 tries
                print ("Better find something else to do!")

            else: #if guessed in more than 7 tries
                print ("You should be embarssed! My dog could pick better.")

                choice=input("""Would you like to play again? ("yes" or "no")\n""") #asks if you want to play again
                if choice in yes: #if yes, then run game again
                    game()
                if choice in no: #if no, then quit the game
                    print ("Okay.. Goodbye :(")
                    quit
            break
game()

Good job for a first experience in Python! You can improve your code a little by looking at these recommendations:

To choose a random integer, you could simply use random.randrange(0,11)
You should probably not import at the function level either, try writing your import statements at the top of your file.
The game() function is called recursively; you shouldn't do that. You could have an infinite loop that fires game() back when exited.
Personally, I wouldn't use lists with "yes" and "no" values, try something like

if "y" in choice.lower():
    return True
else:
    return False

Last but not least, you should check if the number entered is an integer. If it is not, ask the user to enter a valid integer until they do so.


Deadbeef : finding all words made of hexadecimal digits Hexadecimal 0xdead, 0xbeef are the magic numbers because they're also English words.
I decided to find such words as many as possible. How to do it? We need large English text let's say Ulysses by James Joyce and a program which extracts all words consists of hexadecimal digits. For simplicity, I decided to drop leet-language support. It dramatically shrinks the range but keeps real words only.

The code below extract magic numbers from given text and prints them to stdout in lower case

#include <ctype.h>
#include <stdio.h>

#define MAX_LEN 256

int process_file(FILE* file);

int main(int argc, char* argv[]) {

  if (argc == 1) {
    process_file(stdin);
  } else {
    size_t i = 0;
    char* filename;
    FILE* file;
    int err;
    while ((filename = argv[++i]) != NULL) {
      file = fopen(filename, "r");
      if (!file) {
        perror("fopen() failed");
        return 1;
      }
      err = process_file(file);
      fclose(file);
      if (err) {
        return 2;
      }
    }
  }

  return 0;
}

int process_file(FILE* file) {
  char word[MAX_LEN];
  size_t p = 0;
  int c;
  while (1) {
    c = getc(file);
    if (isspace(c) || c == EOF) {
      /* end of word or end of emptiness */

      if (p > 0 && p < MAX_LEN && p % 2 == 0) {
        word[p] = 0;
        printf("%s\n", word);
      }

      if (c == EOF) {
        break;
      }

      p = 0;
      continue;
    }

    if (p > MAX_LEN - 1) {
      continue;
    }

    if ((c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f')) { /* abcdef ABCDEF */
      word[p++] = tolower(c);
    } else {
      /* skip this word */
      p = MAX_LEN;
    }
  }

  if (feof(file)) {
    return 0;
  }

  if (ferror(file)) {
    perror("i/o error occurred");
  }

  return 1;
}

Commands

echo "Dead of being fed with beef for a decade" | ./deadbeaf | sort | uniq

should give

beef
dead
decade

It is customary to put helper functions first and main() last, to avoid having to write forward declarations like int process_file(FILE* file);.

process_file() is a very generic name.  I suggest renaming it to print_hex_words().

The process_file() function returns an error code.  Therefore, the responsibility for printing any error message for I/O errors should lie with main().

You assume that words are delimited by whitespace, and have neglected to deal with punctuation.

Your algorithm is very tedious.  Instead of using getc() to read a byte at a time, use fscanf() to read a whitespace-delimited word at a time.  To skip to the end of a sequence consisting solely of A-F characters, use strspn(…, "ABCDEFabcdef").

#define xstr(s) str(s)
#define str(s) #s

int print_hex_words(FILE* file) {
    char word_buf[MAX_LEN + 1];
    while (1 == fscanf(file, "%" xstr(MAX_LEN) "s", word_buf)) {
        char *word, *end, *trail_punct;

        /* Skip leading punctuation */
        for (word = word_buf; ispunct(*word); word++);

        end = word + strspn(word, "ABCDEFabcdef");

        /* Skip trailing punctuation */
        for (trail_punct = end; ispunct(*trail_punct); trail_punct++);

        if (word != end && *trail_punct == '\0') {
            /* NUL-terminate the word and convert it to lowercase */
            *end = '\0';
            for (end = word; (*end = tolower(*end)); end++);

            printf("%s\n", word);
        }
    }
    return ferror(file);
}

Instead of … | sort | uniq, you can use … | sort -u.


Checking whether textboxes have data I always end up creating a quick return statement above a code block if the simple condition of textbox null fields are found. Naturally, these tend to build up the more controls are added. Now I'm staring at this mess of code, and I'm looking for advice as to avoid this very common mistake in the future.

This is the spaghetti code of a small winform C# project that I'm sure will trigger more than a few people:

   if (txtFirst.Text == "" || txtLast.Text == "" || txtGross.Text == "" ||
        txtLessTNT.Text == "" || txtTCI.Text == "" || txtADDTI.Text == "" || txtGTI.Text == "" ||
        txtLessTE.Text == "" || txtLessPPH.Text == "" || txtLessNTI.Text == "" || txtTD.Text == "" ||
        txtTWCE.Text == "" || txtTWPE.Text == "" || txtTATW.Text == "" ||
        txtFirst.Text == " " || txtLast.Text == " " || txtGross.Text == " " ||
        txtLessTNT.Text == " " || txtTCI.Text == " " || txtADDTI.Text == " " || txtGTI.Text == " " ||
        txtLessTE.Text == " " || txtLessPPH.Text == " " || txtLessNTI.Text == " " || txtTD.Text == " " ||
        txtTWCE.Text == " " || txtTWPE.Text == " " || txtTATW.Text == " " || txtID.Text == "" ||
        txtID.Text == " " || txtTIN.Text == "" || txtTIN.Text == " " || txtFrom.Text == " " || txtFrom.Text == "" || txtTo.Text == " " || txtTo.Text == "" || txtCTC.Text == " " || txtCTC.Text == "" || txtCTC.Text == " " || txtPOI.Text == "" || txtPOI.Text == " " || txtDOI.Text == "" || txtDOI.Text == " " || txtDOI.Text == "" || txtAMT.Text == " " || txtAMT.Text == ""
    )

    {
        MessageBox.Show("Cannot enter null values!");
        return;
    }

Surely, there is an easier way to do this that allows the code to be modular and concise that permits the addition of new textbox controls. This happens more often than I'd like to admit and I wish to get rid of this habit once and for all.

Note that, I do have another solution, it's a linq block that iterates through ALL textbox controls in a given form. But what I'm looking for is as I mentioned, code that allows for selection of the controls involved.

Why so complicated?

One possible approach is:

var f = new Form();
if (f.Controls.OfType<TextBox>().Any(x => string.IsNullOrWhiteSpace(x.Text)))
{
    /*your stuff*/
}

A second approach is:

var TextBox1 = new TextBox();
var TextBox2 = new TextBox();

var textboxes = new[] { TextBox1, TextBox2 };
if (textboxes.Any(x => string.IsNullOrWhiteSpace(x.Text)))
{
    /*your stuff*/
}


SASS mixin for a font-awesome before/after usage In my SASS I use font-awesome declarations all over the place. I'm in love with it. I've created a SASS mixin for the usage:

I started with the following:

@mixin font-awesome-icon($type, $unicode, $size, $margin, $color, $weight) {
  @if $type == 'after'{
    &:after {
      content:$unicode;
      font-family:"FontAwesome";
      font-size:$size;
      color:$color;
      font-weight:$weight;
      margin:$margin;
      @content;
    }
  }
  @if $type == 'before' {
    &:before {
      content:$unicode;
      font-family:"FontAwesome";
      font-size:$size;
      color:$color;
      font-weight:$weight;
      margin:$margin;
      @content;
    }
  }
}

I then scaled it down further to the following:

@mixin font-awesome-icon($type, $unicode, $size, $margin, $color, $weight) {
  $beforeOrAfter:'';

  @if $type == 'after' {
    $beforeOrAfter:'after';
  }
  @else if $type == 'before' {
    $beforeOrAfter:'before';
  }

  &:#{$beforeOrAfter} {
      content:$unicode;
      font-family:"FontAwesome";
      font-size:$size;
      color:$color;
      font-weight:$weight;
      margin:$margin;
      @content;
    }
}

The usage would something like:

.tater {
@include font-awesome-icon(before,'\f0de',2.1em,0 0 0 3em,orange,300);
}

But I feel I could make the before/after part cleaner. I basically need to determine if it is a 'before' or 'after'.

The $type can be passed in directly to the pseudo-class selector after you check its validity.

@if $type == 'after' or $type == 'before' {
  &:#{$type} {
    content:$unicode;
    font-family:"FontAwesome";
    font-size:$size;
    color:$color;
    font-weight:$weight;
    margin:$margin;
    @content;
  }
}


Guessing Game (Heads or Tails) You guess heads or tails by clicking one of the buttons on easyGUI.  If it's right, you will get a "good job" message.  If it's wrong, you will get a "wrong" message! After that, there is an option to play again.

Please give me some feedback on how I can make my code better, if there is room for improvement.

import random
import time
import easygui
import sys
while True:
    rand = random.choice(["Heads", "Tails"])
    firstguess = easygui.buttonbox("Pick one", choices= ["Heads", "Tails"])
    if firstguess == rand:
        easygui.msgbox("Wow you win!")
    else:
    easygui.msgbox("Sorry you guessed wrong!")
    time.sleep(2)
    answer = easygui.buttonbox("Play again?", choices=["Yes","No"])
    if answer == "Yes":
        pass
    else:
        break

easygui.msgbox("Ok, see you later!")
sys.exit(0)

Your script isn't bad. But there is always room for improvement:

It's bad to mix tabs and spaces.  The fact that your code broke when you pasted it here shows why.  Good editors have a setting that will help you with this.  (It is recommended that you use spaces only.)
You don't need sys.exit(0) at the end of your script, since Python will exit automatically when it reaches the end.
Choose your variable names carefully. rand is not very descriptive and firstguess is plain incorrect (every guess, not just the first, gets assigned to this variable).
Don't repeat yourself.  Don't write ["Heads", "Tails"] twice, because if you have to change it for whatever reason, you have to remember to change it in two places.  Store it in a variable.
You can simplify this:

if answer == "Yes":
    pass
else:
    break

To this:

if answer != "Yes":
    break

I don't know easygui, but it seems you should use a
ynbox
when you're asking "yes or no?".  So you can change this:

answer = easygui.buttonbox("Play again?", choices=["Yes","No"])
if answer != "Yes":
    break

To this:

play_again = easygui.ynbox("Play again?")
if not play_again:
    break

Or simply:

if not easygui.ynbox("Play again?"):
    break

With all the changes made and after applying the rules from the the Python style guide PEP8, your code looks like this:

import random    # alphabetic order
import time

import easygui    # third-party modules after standard-library modules

CHOICES = ["Heads", "Tails"]    # ALL_CAPS for variables whose value never changes

while True:
    result = random.choice(CHOICES)
    guess = easygui.buttonbox("Pick one", choices=CHOICES)
    if guess == result:
        easygui.msgbox("Wow you win!")
    else:
        easygui.msgbox("Sorry you guessed wrong!")
    time.sleep(2)
    if not easygui.ynbox("Play again?"):
        break

easygui.msgbox("Ok, see you later!")


JavaScript filter() on JSON object? I'm building a web interface for a home monitoring sensor array, and fetching JSON from the backend framework. I want to start putting statistics together for monitoring different areas of the home, inside and outside.

Each thermal sensor provide the reading, in regular intervals, of temperature and time of day, so I end up with a JSON object looking like this:

{
"sensor_1" :    [
    {
    "location" : "garage_east",
    "temp_f" :  [{
                    "value" : "71.2",
                    "timestamp" : "2017-05-01T08:15:00"
                },
                {
                    "value" : "70.8",
                    "timestamp" : "2017-05-01T08:30:00"
                },
                {
                    "value" : "72.6",
                    "timestamp" : "2017-05-01T08:45:00"
                }
        ]}],

"sensor_2" : [{
    "location" : "kitchen",
    "temp_f" : [{
                    "value" : "78.2",
                    "timestamp" : "2017-05-01T08:15:00"
                },
                {
                    "value" : "78.8",
                    "timestamp" : "2017-05-01T08:30:00"
                },
                {
                    "value" : "78.6",
                    "timestamp" : "2017-05-01T08:45:00"
                }]
}]}

and so on, with multiple sensors each displaying pretty large JSON objects for the reporting periods.

I want to derive the highest and lowest temperatures around the house, and at what time they occurred, using JavaScript (with AngularJS). Currently, I'm looking to optimize this (which does work):

/* The entire array of data, within time frame set by the user
*   and for the sensors defined by the user
*   from the RESTful API (params)
*/

api.sensor_data.get(params, function(data){

  $scope.sensorStats = {
    "kitchen" : {},
    "garage" : {}
  }
  /* find the highest temperature for a single sensor */
  let hightemp_kitchen = Math.max.apply(Math, data.sensor_1.temp_f.map(function(t){
        return t.value;
  }));
  /* grab the associated timestamp and put them both into an object */
  $scope.sensorStats.kitchen.high = data.sensor_1.temp_f.find(function(obj){
      return obj.value == hightemp_kitchen;
  });
  /* Repeat for each sensor of concern (user defined in params) */
  etc...
 });
}, ...

and then I use the in the DOM the expression {{ sensorStats.kitchen.high }} to display the high temp and date/time to the user for the kitchen.

Like I say, this works, but I'm doing this for each of the 15+ sensors in the array around the property. This method not the easiest to read and maintain - I think it can be faster and more efficient to maintain, but I don't have the lexicon to know what to research.

Is this efficient? Is there a "better" or more efficient way to filter out the data and return the temp and time? I'm reading up on ES6, and discovered the filter() method, but it seems to be useful only on arrays and not objects.

It seems like you should not be hard-coding concepts such as "kitchen", "garage", etc. into your code at all. You need to design that out.

Also I question the JSON structure.  sensor_* are meaningless property names, giving you an unnecessary level of nesting, so if you have control over JSON generation, you might consider an array of object like:

[
    {
        "location": ...,
        "temp_f": [
            ...
        ]
    },
    {
        ...
    }
]

But let's assume you can't do that, and think of ways we can get you the information make this whole thing more dynamic. I am not sure what params is even used for, so I am discarding this.

api.sensor_data.get(function(data){
    let sensorData = {};
    // loop through each sensoer object, ignore top level key value
    Object.values(data).forEach( (sensor) => {
        // reduce f_temp array to single entry with highest temp
        // and set to sensorData result object with location as key
        sensorData[sensor.location] = sensor.f_temp.reduce( (acc, metric) => {
            if(parseFloat(metric.value) > parseFloat(acc.value)) acc = metric;
            return acc;
        }, sensor.f_temp[0]);
    });

    $scope.sensorStats = sensorData;
}

Based on your comment regarding params, you might have something more like this:

    let sensorData = {};

    let sensors = Object.values(data);
    // filter by location
    if (location in params) {
        sensors = sensors.filter( (sensor) => sensor.location === params.location );
    }
    // loop through each sensor objects
    sensors.forEach( (sensor) => {
        let result = null;
        let metrics = sensor.f_temp;
        if(minTimestamp in params) {
            metrics = metrics.filter( metric => {
                return (Date.parse(metric.timestamp) >= params.minTimeStamp );
            });
        }
        if(maxTimestamp in params) {
            metrics = metrics.filter( metric => {
                return (Date.parse(metric.timestamp) =< params.maxTimeStamp );
            });
        }
        if(metrics.length > 0) {
        result = metrics.reduce( (acc, metric) => {
            if(parseFloat(metric.value) > parseFloat(acc.value)) acc = metric;
            return acc;
        }, metrics[0]);
       sensorData[sensor.location] = result;
    });

    $scope.sensorStats = sensorData;
}


Lookup GINI by year and country This takes a dataframe as an argument, looks at all pairs of two columns in that data frame (country and year) and returns a column value of that pair in another data frame (the gini number).

get_gini <- function(year, country){
    GINI = 0
    SUBSETTED_WITH_COUNTRY_NAME_NOW_WITH_YEAR <- inequality[inequality$Code== country & inequality$Year== year,]
    GINI <- mean(as.numeric(SUBSETTED_WITH_COUNTRY_NAME_NOW_WITH_YEAR$Gini))

    country_and_year<- totes_data[totes_data$totes_data == country & totes_data$year == year,]
    country_and_year$GiniState1<-GINI
    output<-country_and_year$GiniState1
    output<-output[1]
    if (is.na(output)){
      output=0
    }
    else {
      output = output
    }
    assign("ginilist",output, envir=globalenv())
    rbind(output,ginilist)
}

With the data.table package, you can do a quick join and get the gini coefficient much easier. This solution is also vectorized, so you can call it with something like gini(2000:2004, 'USA') to get the gini coefficients for the USA for years 2000-2004.

It is also good practice to include the data in your function call, so you don't use objects from the global environment within the function call. This function outputs the entire data.table, but you can also just use the gini coefficient as output, if you add [, GINI] at the end.

gini <- function(year, country, data = inequality){
  require(data.table)
  setkey(setDT(data), 'Code', 'Year')[J(Code = country, Year=year),
                                        list(GINI = mean(as.numeric(Gini))),
                                        by=list(Code, Year)]
}


Create and destroy object in Unit Test I have some doubt when I should create an object in an Unit Test when the object needs to be stopped cleanly.

Usecase:
I have a class ComplexClass which has 3 functions:

Start(): starts a Thread
Stop(): stops the thread
GetX(): which gets a value

When I test this class I want to check if GetX() returns 42, but first I have to start the thread, and after it I want to stop the Thread. (During testing I don't want many dangling threads running).

Are fixtures the way to do this?:

class TestComplexClass(object):
    @pytest.fixture()
    def complexclass(self, request):
        print ("[setup] ComplexClass")

        cc = ComplexClass()
        def fin():
            print ("[teardown] ComplexClass")
            cc.stop()
        request.addfinalizer(fin)
        return cc

    def test_GetX(self, complexclass):
        // do some stuff

        complexclass.start()
        assert complexclass.GetX() == 42, "GetX() should return 42"

Or should I create the object in the Unit Test?:

class TestComplexClass(object):
    def test_GetX(self, complexclass):
        // do some stuff

        cc = ComplexClass()
        try:
            cc.start()
            assert cc.GetX() == 42, "GetX() should return 42"
        except AssertionError:
            cc.stop
            raise

(Note I'm using Py.Test)

This somewhat depends on which principle you value higher. Small repetition:

F.I.R.S.T

F: Fast

Pretty self-explaining. Unit tests have to be as fast as possible for TDD to be viable.

I: Independent

Unit tests are not depending on anything else than the testing-framework and the class under test (cut). Not even on other tests. Unit tests prepare their own data and setup and clean up after themselves after evaluation. It must not matter in which order unit tests are executed!

R: Repeatable

Unit tests give the same result when they are repeatedly executed. Even on a new moon with low tide. They always look for the same results and perform the same operations.

S: Self-Validating

Unit tests validate the result of any operation themselves. They may not give any results to external classes for validation. Also they should be self-explaining as to why that result is expected.

T: Timely

Unit tests are to be written as close as possible before the implementation of a feature

principles freely adapted from Agile in a Flash

In this case you will have to evaluate the fast principle against the independent principle
It will definitely be faster to create the instance of ComplexClass only once (on fixture setup), but that will undermine the independency of unit tests and may will cause problems when you depend on execution order.


Using readonly input fields to persist data between views I'm building a multi-screen Ajax form in an ASP.NET MVC solution.  The first screen displays some user details.  If the user clicks 'edit', they are taken to the next screen where they can edit the fields.  The call to retrieve the user info is quite slow so I don't want to repeat it for every Ajax request, so I'm thinking of displaying the information on the first screen using @Html.TextBoxFor(m=>m.FieldName, new {@readonly="readonly"}) (styled so it doesn't look like an ordinary readonly input). Then simply posting this information back and re-using it when I show the edit screen.

My initial screen to show existing info (Index.cshtml) is something like this (note that there are more fields, I just showed one to demonstrate the idea):

@using(Ajax.BeginForm("StartEdit", "UserDetails", new AjaxOptions{...})
{

        @Html.LabelFor(m=>m.FirstName)
        @Html.TextBoxFor(m=>m.FirstName, new { @readonly = "readonly" })

    <input type="submit" value="Edit"/>
}

and the edit screen (Edit.cshtml) is something like this:

@using(Ajax.BeginForm("SubmitChanges", "UserDetails", new AjaxOptions{...})
{

        @Html.LabelFor(m=>m.FirstName)
        @Html.TextBoxFor(m=>m.FirstName)

}

The controller is as follows:

public class UserDetailsController
{
    public PartialViewResult Index()
    {
        var viewModel = new MyViewModel(); //populated from web service, slow operation
        return PartialView("Index", viewModel);
    }

    public PartialViewResult(MyViewModel viewModel)
    {
        return PartialView("Edit", viewModel); //returning posted viewModel back to next view
    }

}

Is there anything wrong with doing this, or should I just use hidden fields to persist the information and render that same information to the user using @Html.DisplayFor(m=>m.FieldName) etc?

On a functional level there is no problem with using readonly inputs to persist and display data in a preview screen.  When I tried this approach however I noticed that different browsers treat readonly inputs in different ways which cannot be addressed with CSS rules. For example in Chrome the inputs can be styled to look and behave like any other element, however in IE the caret will sit there blinking on readonly input fields which was not acceptable in my particular case.


Reducing a 2D array to its longest unique series that aren't contained within any other I have an array whose members are arrays containing strings. Each array has 5 elements, some of which may be empty but always at the end of the array. The order of the strings matters because their hierarchical labels—call them catLists. I need all the longest unique lists, ie. some of the shorter catLists are contained within longer ones, and for my purposes the shorter ones are redundant.

Here's a sample of the data:

// in fact my $catLists array is hundreds of elements long and changing weekly
$catLists = array(
                    0 => array('500ml', '750ml', '', '', '')
                    1 => array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                    2 => array('big', 'bigger', 'biggest', '', ''),
                    3 => array('sml', 'med', 'lrg', '', ''),
                    4 => array('big', '', '', '', ''),
                    5 => array('300ml', '500ml', '750ml', '1L', '')
                    6 => array('1L', '750ml', '', '', ''));

// but if this were the list, then my desired output would be
$reducedCatLists = array(
                      0 => array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                      1 => array('big', 'bigger', 'biggest'),
                      2 => array('300ml', '500ml', '750ml', '1L'),
                      3 => array('1L', '750ml'));

Although sequence matters, position doesn't, which is why, for my purposes, $catLists[0] would be considered contained within $catLists[5] but $catLists[6] wouldn't.

I've no idea how to do this efficiently; right now I'm reducing every array to a string and then comparing substrings, but it's not clear to me that this is a good way to do this (self-taught programmer who leans toward design rather than math—no CS here at all).

$catList_strings = array();
        $reduced_catLists = array();
        foreach ($catLists as $i => $catList) {
            $stringified = implode("",$catList);
            $contained = false;
            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) $contained = true;
            }
            if (!$contained) {
                $catList_strings[] = $stringified;
                $reduced_catLists[] = array_filter($catList);
            }
        }

When this goes live I'd really like it not to be a burden to the server.

Bug

Try the following input:

$catLists = array(
                    0 => array('sml', 'med', 'lrg', 'xlg', 'xxl'),
                    1 => array('smlmed', 'lrg', '', '', ''));

I think that this will produce just one row of output, although it should produce two (these arrays are distinct).  To avoid this, you should check the arrays after finding matching strings or use some character that would never appear in the strings to join them.  If you change the join character, note that you may have to trim out the empty portion before generating the string.

For example, the colon (:) would work in your example:

$stringified = ':' . implode(':', $catList) . ':';

but would produce strings like :big::::: when you probably just want :big:.

Avoid unnecessary variables

            $contained = false;
            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) $contained = true;
            }
            if (!$contained) {
                $catList_strings[] = $stringified;
                $reduced_catLists[] = array_filter($catList);
            }

You can just say

            foreach ($catList_strings as $cl_str) {
                if ( strpos($stringified, $cl_str) ) {
                    $catList_strings[] = $stringified;
                    $reduced_catLists[] = array_filter($catList);
                    break;
                }
            }

This is also more performant, as it stops as soon as it finds a match.  The original code tried to generate more.

Consider using an associative array

You can make this more direct.  Something like:

function array_contains($base, $candidate, $start = 0) {
    if (count($base) < count($candidate) - $start) {
        return false;
    }

    foreach ($base as $v) {
        if ($v != $candidate[$start]) {
            return false;
        }
    }

    return true;
}

$indexesOf = array();
foreach ($catLists as $i => $catList) {
    $trimmedList = array_filter($catList);
    foreach ($trimmedList as $j => $cat) {
        if (isset($indexesOf[$cat]) {
            if (0 == $j) {
                foreach ($indexesOf[$cat] as $index => $start ) {
                    if (array_contains($catList, $catLists[$index], $start)) {
                        break 2;
                    }
                }
            }
        } else {
            $indexesOf[$cat] = array();
        }

        $indexesOf[$cat][$i] = $j;
        $reducedCatLists[] = $trimmedList;
    }
}

This uses a dictionary lookup to search for arrays that could potentially contain the current one.

Bug 2

Perhaps this isn't an issue, but the array order matters here.  You only check arrays that you've already seen.  I do this as well.  Not sure how much it matters, but

$catLists = array(
                    0 => array('500ml', '750ml', '', '', ''),
                    1 => array('300ml', '500ml', '750ml', '1L', ''));

and

$catLists = array(
                    0 => array('300ml', '500ml', '750ml', '1L', ''),
                    1 => array('500ml', '750ml', '', '', ''));

will return different results.

If you want to get the same result from both inputs, then you have to loop through the array twice.  The first time, you build the lookup array.  The second time, you build the reduced list.

Test

If you have historically accurate values for $catList run a test where you time how long it takes to process either way.

Note that if it only changes weekly, it may be reasonable to save $reducedCatList when it first appears.  That would be unlikely to cause significant load to the server, as you can choose to do it at a time when most legitimate users don't use the server.  Something like 3 AM is great, but even a time like 3 PM might work.  I don't know what patterns your customers follow.


Finding the number of integers that are a square and a cube at the same time I have written some code that takes two integers and returns the numbers of numbers that are both a square and a cube. I would like to know if there is a more efficient way to write this. I have only just started learning Java so any feedback would be greatly appreciated.

Scanner input=new Scanner(System.in);
double a=input.nextInt();
double b=input.nextInt();
int coolnumbers=0; //counter for the # of numbers that are a square and cube
for(double i=a; i<=b; i++){
    for(double j=1; j<=b; j++){
       if(i==Math.pow(j,6)){
         coolnumbers++;
         break;
       }
    }
}
System.out.println(coolnumbers);

Let's say a = 1, b = 1,000,000. Your code is a nested loop, each loop iterating a million times, for a total of one trillion tests. And I tell, out of my head, that the result is 10 and the numbers are 1, 2^6, 3^6, 4^6, 5^6, 6^6, 7^6, 8^6, 9^6 and 10^6.

The numbers that are both 2nd and 3rd powers are exactly the sixth powers of integers. So you can just iterate for i = 0, 1, 2, 3 etc., calculate j = i^6, then if j >= a and j <= b increase the counter, and if j > b then exit the loop. The time needed is proportional to the sixth root of b.

Even faster, if b was extremely large, calculate A = sixth root of a, round up to the nearest integer, and B = sixth root of b, rounded down to the nearest integer. The numbers from a to b that are sixth powers are exactly the sixth powers of the numbers from A to B, and there are B - A + 1 of them.


Check if a string has 20 numbers in a row in it My code will check if the variable myString has 20 running numbers. I'm new to JavaScript and I'm wondering if there is a simpler way to do this. How can I shorten my code and possibly make it more efficient?

var myString = "tuxwuhkocx14789470019215498263ljmgwsxvne";
var runningNumbers = 0;

for (i = 0; i < myString.length; i++) {

    var character = myString.charAt(i);

    if (!isNaN(character)) {
        // If character is a number:
        runningNumbers = runningNumbers + 1;
    } else {
        // If character is NOT a number:
        runningNumbers = 0;
    }

    if (runningNumbers == 20) {
        console.log("myString has 20 running numbers.");
    }

}

Output:

  myString has 20 running numbers.

If you use a regular expression to look for 20 digit characters (\d) in a row, then the code would be compact and the goal would be visible at a glance:

var twentyDigits = /\d{20}/;
if (twentyDigits.test(myString)){
  console.log("My string has 20 running numbers");
}

You can shorten this further as just:

if (/\d{20}/.test(myString)) console.log("Yup. 20");


Interface programming with Data Access Layer I have several controls that are bound from database tables.  Putting my OOP thinking cap on I figured since all of the controls will have a SqlCommand name and an associated SqlDataReader object I decided to make the following interface to program to.

public interface IBoundControl
    {
         string GetCommandName();
         void ReadyReader(SqlDataReader rdr);
    }

For illustration's sake, consider the following to classes which implement IBoundControl interface

public class Hospital : IBoundControl
    {

        public int HospitalId { get; set; }
        public string HospitalName { get; set; }

        public string GetCommandName()
        {
            return "spGetHospitals";
        }
        public void ReadyReader(SqlDataReader rdr)
        {
            this.HospitalId = (int)rdr["HospitalId"];
            this.HospitalName = (string)rdr["HospitalName"];
        }

    }

public class Race : IBoundControl
    {
        public int RaceId { get; set; }
        public string RaceDescription { get; set; }
        public string GetCommandName()
        {
            return "spGetRaces";
        }

        public void ReadyReader(SqlDataReader rdr)
        {
            this.RaceId = (int)rdr["RaceId"];
            this.RaceDescription = (string)rdr["RaceDescription"];
        }
    }

The controls are bound to a webform by making a call to the DataAccess class's BindControl method shown below:

 public class DataAccess
    {
        private readonly string cs = ConfigurationManager.ConnectionStrings["dbcs"].ConnectionString;

        //takes in a parameter that will be bound to a web form
        public List<IBoundControl> BindControl(IBoundControl i)
        {
            //creates a list of objects which will be bound to drop down lists
            List<IBoundControl> controlList = new List<IBoundControl>();
            using (var con = new SqlConnection(cs))
            {
                //grabs the name of the sproc for whatever type 'i' is
                using (var cmd = new SqlCommand(i.GetCommandName(), con))
                {
                    con.Open();
                    cmd.CommandType = CommandType.StoredProcedure;
                    SqlDataReader rdr = cmd.ExecuteReader();
                    while (rdr.Read())
                    {
                        //the factory creates an object of whatever type 'i' is
                        ControlFactory factory = new ControlFactory();
                        IBoundControl ibound = factory.CreateControl(i);
                        ibound.ReadyReader(rdr);
                        controlList.Add(ibound);
                    }
                }
                return controlList;
            }
        }

        public class ControlFactory
        {
            public IBoundControl CreateControl(IBoundControl control)
            {
                if (control is Hospital)
                    return new Hospital();
                else if (control is Race)
                    return new Race();
                else
                    return null;
            }
        }
    }

To my surprise, this actually worked - the first time, too!  I was hoping to get some comments on how this might be improved upon, or if there's any general techniques that while this example might be too rudimentary to show, is bad practice down the road.

EDIT: When I first wrote this, the only controls that I had in mind were drop down controls(which is why both classes have two propeties, an ID and a description).

The IBoundControl is good. It isolates the specific data calls. It's refreshing to see another approach than falling back to the repository pattern.

IBoundControl implementation is on a class that also doubles as the DTO. This is breaking the SRP. One way to solve this is to create class that's only job is for lookup values. Call it Lookup. It has two fields: Id and Name.

The new interface looks like this:

public interface IBoundControl
    {
         string GetCommandName();
         List<Lookup> ReadyReader(IDataReader rdr);
    }

Now the IBoundControl implementation will only contain data layer specific code and will return a normalized resultset of lookup values. Also notice that IBoundControl.ReadyReader is taking a dependency on IDataReader instead of implementation specific SqlDataReader.


Optimizing List performance I have a List<string> being stored in my cache with about 600K members.  I want this to act as the backend for an Ajax autocomplete box.  It's accessible through my model:

public static List<string> GetProducts()
{
    var cached = HttpContext.Current.Cache["MyApp-Products"];
    if (cached == null)
    {
        UpdateCache();
        return GetProducts();
    }
    return ((List<string>)cached);
}

My ajax call uses this method to get it's data:

[HttpPost]
public JsonResult ProductSearch(string term)
{
    return Json(MyModel.GetProducts()
        .Where(s => s.ToUpper().StartsWith(term.ToUpper()))
        .OrderBy(s => s)
        .Take(5)
        .ToList<string>()
    );
}

The problem is, this Ajax call to ProductSearch() is waiting 2.09 seconds for a response. I'm doing the same with other objects in my model that have smaller list sizes and they respond in 35-125ms (which is acceptable).

So, I believe my performance issue is somewhere in accessing the list.  Is there a faster way to access this list besides the Linq code that I'm using, or just a better way to use Linq?

A starts-with should be easy enough to store in a pre-sorted list, ideally using a case-insensitive sort comparer rather than applying conversions each sort. Then: use binary search to find the first match, and keep moving forwards until it no longer matches. Should be pretty efficient.

If this needs to be edited in a shared multi-threaded context, be sure to use appropriate synchronization - presumably readers will be more common than writers, so a ReaderWriterLockSlim may be the best option.


Efficient communication across multiple processors for finite elements I am implementing finite element code using MPI. Obviously, when using MPI I will have to include communication between different nodes so that all processors have all relevant information. As this is my first time doing something like this, I have implemented a very naive algorithm to get updated volume information for each element as shown below:

!loop over all of the processors
do n=0,numProcs-1
    !for each iteration of the loop, one processor will hand out relevant information
    if( my_id .eq. n ) then
        do i=0,numProcs-1
            if( i .ne. my_id ) then
                currProc=i
                !get the number of volumes processor i needs from processor n
                call MPI_RECV( numNeeded,1,MPI_INTEGER,i,my_id, &
                               MPI_COMM_WORLD,status,ierr )

                !for each volume that processor i needs:
                do j=1,numNeeded
                    !get the element number
                    call MPI_RECV( currNeeded,1,MPI_INTEGER,i,j, &
                                   MPI_COMM_WORLD,status,ierr )
                    !return the volume of that element
                    call MPI_SEND( myElements(elementGlobalToLocal(currNeeded))%xsj,1, &
                                   MPI_REAL8,i,j,MPI_COMM_WORLD,status,ierr )
                enddo
            endif
        enddo
    else
        !tell processor n how many volumes are needed from it, calculated elsewhere
        call MPI_SEND( numElementsNeeded(n+1),1,MPI_INTEGER,n,n, &
                       MPI_COMM_WORLD,status,ierr )

        !for each volume needed
        do j=1,numElementsNeeded(n+1)
            !send the element number, calculated elsewhere
            call MPI_SEND( elementsNeeded(n+1, j),1,MPI_INTEGER,n,j, &
                           MPI_COMM_WORLD,status,ierr )
            !receive the appropriate volume
            call MPI_RECV( myExternalXsj(currReceived),1,MPI_REAL8,n,j, &
                           MPI_COMM_WORLD,status,ierr )
            !global element numbering is 1-numTotElems
            !local numbering is 1-numElemsPerProc
            !elementGlobalToLocal keeps track of conversion from local to global
            elementGlobalToLocal(elementsNeeded(n+1, j))=currReceived
            currReceived=currReceived+1
        enddo
    endif
enddo

While this code does give the right results (i.e., all of the processors have all the information they need, and the values passed are the correct values), the performance is abysmal. Even when using -np 2, roughly 50% of the total time spent on volume calculations is spent doing this communication; when using -np 8 that comes up to a startling 94%. The major issue I see with the code above is that it doesn't scale very well; when process 0 is communicating to process 1, processes 2 and 3 are just hanging, which will cause a significant slowdown.

What would be a good way to address this? Also, are there any other major issues with the code that I am not seeing?

The answer was staring me right in the face, I just wasn't paying attention, apparently. Instead of sending one integer and one real*8 at a time, I should have been sending all of them at once, as:

do n=0,numProcs-1
    if( my_id .eq. n ) then
        do i=0,numProcs-1
            if( i .ne. my_id ) then
                currProc=i
                call MPI_RECV( numNeeded,1,MPI_INTEGER,i,my_id*2, &
                               MPI_COMM_WORLD,status,ierr )

                allocate( currNeeded(numNeeded) )
                allocate( volsNeeded(numNeeded) )

                call MPI_RECV( currNeeded,numNeeded,MPI_INTEGER,currProc,my_id*2+1, &
                               MPI_COMM_WORLD,status,ierr )

                do j=1,numNeeded
                    volsNeeded(j)=myElements(elementGlobalToLocal(currNeeded(j)))%xsj
                enddo

                call MPI_SEND( volsNeeded,numNeeded,MPI_REAL8,currProc,my_id, &
                               MPI_COMM_WORLD,status,ierr )

                deallocate( currNeeded )
                deallocate( volsNeeded )
            endif
        enddo
    else
        call MPI_SEND( numElementsNeeded(n+1),1,MPI_INTEGER,n,n*2, &
                       MPI_COMM_WORLD,status,ierr )

        call MPI_SEND( elementsNeeded(n+1, 1:numElementsNeeded(n+1)), &
                       numElementsNeeded(n+1),MPI_INTEGER,n,n*2+1, &
                       MPI_COMM_WORLD,status,ierr )

        call MPI_RECV( myExternalXsj(currReceived:currReceived+numElementsNeeded(n+1)), &
                       numElementsNeeded(n+1),MPI_REAL8,n,n,MPI_COMM_WORLD,status,ierr )

        do j=1,numElementsNeeded(n+1)
            elementGlobalToLocal(elementsNeeded(n+1, j))=currReceived
            currReceived=currReceived+1
        enddo
    endif
enddo

Reducing the MPI call times drastically reduces the time spent in communication from (on 8 cores) roughly 269 seconds to roughly 13 seconds, a speedup by a factor of more than 20. This still doesn't change the problem of low scalability, though perhaps using non-blocking send/receive operations (with a barrier after the end of the loop to ensure all messages are received/sent) will do that.


JavaScript shuffle idea Based on the standard implementation of Array.sort in JavaScript, would the following be a reasonable way of shuffling the contents of an array? Is it moderately efficient and will it produce a fairly even spread of results?

Array.prototype.shuffle = function () {
    return this.sort(function(){ return Math.random() - 0.5;});
};

This article says that a test run on that algorithm showed a bias with items less likely to move farther away from their original location than near (a bias).

My own intuition says that it could cause issues because the .sort() algorithm expects that when a given two elements are compared they will always have the same comparison result and yet that is not true when using this function.  Therefore, I'm thinking that how well this work could also depend upon how the .sort() method was actually implemented internally.

This article shows what seems to me like a better algorithm for randomness, though I wouldn't expect it to be particularly efficient:

Array.prototype.shuffle = function() {
    var s = [];
    while (this.length) s.push(this.splice(Math.random() * this.length, 1));
    while (s.length) this.push(s.pop());
    return this;
}

EDIT: Also just found this same question here: https://stackoverflow.com/questions/962802/is-it-correct-to-use-javascript-array-sort-method-for-shuffling.  That answer suggests this which is based on the Fisher-Yates algorithm and would be a lot more efficient than the algorithm above:

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

And, here's a testpage that shows the results of your proposed method vs. the Fisher-Yates method in your browser: http://phrogz.net/JS/JavaScript_Random_Array_Sort.html.


Find the total number of ways W, in which a sum S can be reached in N throws of a dice I was solving this question:

Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws.

  Example:

  S = 1, N = 6 => W = 0

  S = 6, N = 6 => W = 1

  S = 7, N = 6 => W = 6

  S = 3, N = 2 => W = 2

How to improve its complexity and make it more readable?

def get_sum_dp(n,s):
    t = [[0 for i in xrange(1,s+2)] for j in xrange(1,n+2)]
    for j in xrange(1,7):
        t[1][j] = 1
    for i in range(2, n+1):
        for j in range(1, s+1):
            for k in range(1,7):
                if k < j:
                    t[i][j] += t[i-1][j-k]
    print t[n][s]

get_sum_dp(2,8)

1. Review

The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:

>>> get_sum_dp(0, 0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr161002.py", line 32, in get_sum_dp
    t[1][j] = 1
IndexError: list index out of range

The name get_sum_dp could be clearer (what does "dp" mean? dynamic programming?). I would use a name like dice_rolls.
A docstring would be helpful in understanding what the function does.
It's usually more convenient to return a result instead of printing it. This would allow the result to be used in other computations if needed.
Instead of

t = [[0 for i in xrange(1,s+2)] for j in xrange(1,n+2)]

you could write:

t = [[0] * (s + 1) for _ in xrange(n + 1)]

(It's conventional to use _ for a loop variable whose value is not used.)
The initial condition is:

for j in xrange(1,7):
    t[1][j] = 1

but it would be simpler to use the following initial condition:

t[0][0] = 1

and change:

for i in range(2, n+1):
    for j in range(1, s+1):
        if k < j:

to:

for i in range(1, n+1):
    for j in range(1, s+1):
        if k <= j:

(This also fixes the bug I noted in point 1 above.)
In the nested loops:

for i in range(2, n+1):
    for j in range(1, s+1):

the loop over j goes all the way from 1 to s. But some of this may be wasted, because the sum of i dice must be between i and i * 6. So you could reduce the amount of work by writing:

for i in range(2, n+1):
    for j in range(i, min(s, i * 6) + 1):

Similarly, instead of checking k on every loop iteration:

for k in range(1,7):
    if k < j:
        t[i][j] += t[i-1][j-k]

you could compute the loop bounds in advance:

for k in xrange(1, min(6, j) + 1):
     t[i][j] += t[i - 1][j - k]

2. Revised code

def dice_rolls(n, s):
    """Return the number of ways in which a sum s can be reached in n
    throws of a 6-sided die.
    """
    t = [[0] * (s + 1) for _ in xrange(n + 1)]
    t[0][0] = 1
    for i in xrange(1, n + 1):
        for j in xrange(i, min(s, i * 6) + 1):
            for k in xrange(1, min(6, j) + 1):
                t[i][j] += t[i - 1][j - k]
    return t[n][s]

3. Alternative approach

Dynamic programming builds up a table of solutions to sub-problems from the bottom up (starting with small problems and using those to solve larger problems). But an alternative approach works from the top down, using recursion to compute the sub-problems, and memoization to avoid duplicated work. This often results in clearer code and it is easier to compute only the table entries that you need.

In Python 3.2 or later, you can easily memoize a function using the @functools.lru_cache decorator, like this:

import functools

@functools.lru_cache(maxsize=None)
def dice_rolls(n, s):
    """Return the number of ways in which a sum s can be reached in n
    throws of a 6-sided die.
    """
    if s < n or s > n * 6:
        return 0
    elif n == s == 0:
        return 1
    else:
        return sum(dice_rolls(n - 1, s - i) for i in range(1, 7))

(Python 2.7 lacks functools.lru_cache, but there's a backport package.)


Alternating Direction Method of Multipliers This is a python implementation of the Alternating Direction Method of Multipliers - a method of constrained optimisation that is used widely in statistics (http://stanford.edu/~boyd/admm.html).

This is simplified version, specifically for the LASSO:

Given a sparse vector $$x \in R^n$$and matrix $$A \in R^{m \times n}$$ and noisy measurements $$y = Ax + e$$where $$e$$ is additive Gaussian white noise we can solve the following minimisation problem

$$
\hat{x} = \min_x ||y-Ax||_2^2 + \lambda||x||_1
$$

to recover an estimate of $$x$$

The algorithm proceeds iteratively by calculating

$$ x^{k+1} = (A^TA + \rho I )^{-1}(A^Ty + \rho (z - u))$$
$$ z^{k+1} = \mathrm{sign}(\hat{x})\mathrm{max}\left(0, |x| - \frac{\lambda}{\rho}\right) $$

until some convergence criteria is met.

The implementation of the algorithm is below:

import numpy as np
import matplotlib.pyplot as plt
from math import sqrt, log

def Sthresh(x, gamma):
    return np.sign(x)*np.maximum(0, np.absolute(x)-gamma/2.0)

def ADMM(A, y):

    m, n = A.shape
    w, v = np.linalg.eig(A.T.dot(A))
    MAX_ITER = 10000

    "Function to caluculate min 1/2(y - Ax) + l||x||"
    "via alternating direction methods"
    xhat = np.zeros([n, 1])
    zhat = np.zeros([n, 1])
    u = np.zeros([n, 1])

    "Calculate regression co-efficient and stepsize"
    l = sqrt(2*log(n, 10))
    rho = 1/(np.amax(np.absolute(w)))

    "Pre-compute to save some multiplications"
    AtA = A.T.dot(A)
    Aty = A.T.dot(y)
    Q = AtA + rho*np.identity(n)
    Q = np.linalg.inv(Q)

    i = 0

    while(i < MAX_ITER):

        "x minimisation step via posterier OLS"
        xhat = Q.dot(Aty + rho*(zhat - u))

        "z minimisation via soft-thresholding"
        zhat = Sthresh(xhat + u, l/rho)

        "mulitplier update"
        u = u + xhat - zhat

        i = i+1
    return zhat, rho, l

A = np.random.randn(50, 200)

num_non_zeros = 10
positions = np.random.randint(0, 200, num_non_zeros)
amplitudes = 100*np.random.randn(num_non_zeros, 1)
x = np.zeros((200, 1))
x[positions] = amplitudes

y = A.dot(x) + np.random.randn(50, 1)

xhat, rho, l = ADMM(A, y)

plt.plot(x, label='Original')
plt.plot(xhat, label = 'Estimate')

plt.legend(loc = 'upper right')

plt.show()

A string is not a comment

A comment in the code starts with #. Even thought the strings you write seems to have no effect in the code, they are evaluated and created in memory (and thrown away right after) each time. Especially in the while loop.

Do not confuse yourself between docstrings and comments.

l is a really bad variable name.

I truly thought l/rho was 1/rho at first and had a hard time mapping your code to the maths.

Given that:

You don't seem to use the returned value for rho and l;
You “only” need rho and the quotient l/rho;
You don't need to recompute l/rho at each iterations.

I suggest you precompute using:

#Calculate regression co-efficient and stepsize
r = np.amax(np.absolute(w))
l_over_rho = sqrt(2*log(n, 10)) * r
rho = 1/r

and call Sthresh(xhat + u, l_over_rho) latter on. You also only need to return zhat.

Besides, you are dividing l_over_rho by 2.0 in Sthresh; on top of not seeing that anywhere in the maths, you should also incorporate it in the precomputation for a faster loop.

A for loop is more pythonic

Since you don't need the value of i in your while loop, it is best to write:

for _ in xrange(MAX_ITER):
    #x minimisation step via posterier OLS
    xhat = Q.dot(Aty + rho*(zhat - u))
    #z minimisation via soft-thresholding
    zhat = Sthresh(xhat + u, l_over_rho)
    #mulitplier update
    u = u + xhat - zhat

to better emphasize the fact that you won't use the iteration value.

Separate computation and presentation

I'd recommend creating a function for plotting the results and a function for your tests. That way, it would be easier to jump into an interactive session and test your function with alternatives input values:

def test():
    A = np.random.randn(50, 200)

    num_non_zeros = 10
    positions = np.random.randint(0, 200, num_non_zeros)
    amplitudes = 100*np.random.randn(num_non_zeros, 1)
    x = np.zeros((200, 1))
    x[positions] = amplitudes

    y = A.dot(x) + np.random.randn(50, 1)

    plot(x, ADMM(A,y)) #given that ADMM only 'return zhat' now

def plot(original, computed):
    plt.plot(original, label='Original')
    plt.plot(computed, label = 'Estimate')

    plt.legend(loc = 'upper right')

    plt.show()

if __name__ == "__main__":
    test()

[Optimization] Method lookups are faster with local variables

The Sthresh call incur overheads that you can easily remove since it is a one liner. In the same vein Q.dot, np.sign, np.maximum, and np.absolute have to be resolved at each loop iteration. You will save some time using local variable as alias to these functions:

Q_dot = Q.dot
sign = np.sign
maximum = np.maximum
absolute = np.absolute

for _ in xrange(MAX_ITER):
    #x minimisation step via posterier OLS
    xhat = Q_dot(Aty + rho*(zhat - u))
    #z minimisation via soft-thresholding
    u = xhat + u
    zhat = sign(u)*maximum(0, absolute(u)-l_over_rho/2.0) # do we even need the '/2.0' part ? see comment on 'l'
    #mulitplier update
    u = u - zhat

Full modifications (with a tiny bit of variable renaming)

import numpy as np
import matplotlib.pyplot as plt
from math import sqrt, log

def ADMM(A, y):
    """Alternating Direction Method of Multipliers

    This is a python implementation of the Alternating Direction
    Method of Multipliers - a method of constrained optimisation
    that is used widely in statistics (http://stanford.edu/~boyd/admm.html).

    This is simplified version, specifically for the LASSO
    """

    m, n = A.shape
    A_t_A = A.T.dot(A)
    w, v = np.linalg.eig(A_t_A)
    MAX_ITER = 10000

    #Function to caluculate min 1/2(y - Ax) + l||x||
    #via alternating direction methods
    x_hat = np.zeros([n, 1])
    z_hat = np.zeros([n, 1])
    u = np.zeros([n, 1])

    #Calculate regression co-efficient and stepsize
    r = np.amax(np.absolute(w))
    l_over_rho = sqrt(2*log(n, 10)) * r / 2.0 # I might be wrong here
    rho = 1/r

    #Pre-compute to save some multiplications
    A_t_y = A.T.dot(y)
    Q = A_t_A + rho * np.identity(n)
    Q = np.linalg.inv(Q)
    Q_dot = Q.dot
    sign = np.sign
    maximum = np.maximum
    absolute = np.absolute

    for _ in xrange(MAX_ITER):
        #x minimisation step via posterier OLS
        x_hat = Q_dot(A_t_y + rho*(z_hat - u))
        #z minimisation via soft-thresholding
        u = x_hat + u
        z_hat = sign(u) * maximum(0, absolute(u)-l_over_rho)
        #mulitplier update
        u = u - z_hat

    return z_hat

def test(m=50, n=200):
    """Test the ADMM method with randomly generated matrices and vectors"""
    A = np.random.randn(m, n)

    num_non_zeros = 10
    positions = np.random.randint(0, n, num_non_zeros)
    amplitudes = 100*np.random.randn(num_non_zeros, 1)
    x = np.zeros((n, 1))
    x[positions] = amplitudes

    y = A.dot(x) + np.random.randn(m, 1)

    plot(x, ADMM(A,y))

def plot(original, computed):
    """Plot two vectors to compare their values"""
    plt.plot(original, label='Original')
    plt.plot(computed, label='Estimate')

    plt.legend(loc='upper right')

    plt.show()

if __name__ == "__main__":
    test()


A* pathfinding algorithm too slow I'm trying to make a pathfinding algorithm for my project. I need it for a simulation and I need it to be fast!!!

I watched a few videos explaining the algorithm online and came up with the code below.

However, the performance varies a lot considering the start/finish points.
My project should have grids that go upwards of 500x500

A very slow example is the following, with a very small grid:

I have no idea what's making the algorithm so slow

Dir_Map = {
    "1": (1, 0),
    "2": (0, 1),
    "3": (-1, 0),
    "4": (0, -1),
    "5": (1, 1),
    "6": (-1, -1),
    "7": (1, -1),
    "8": (-1, 1)
}

class Node():
    def __init__(self, pos):
        self.x = pos[0]
        self.y = pos[1]
        self.g = 0
        self.h = 0
        self.f = 0
        self.beggining = 1
        self.parent = None

    def update(self, final):
        self.h = manhattan(self, final)
        self.f = self.f +  self.g

class Child(Node):
    def __init__(self, x, y, parent):
        Node.__init__(self, (parent.x + x, parent.y + y))
        self.g = abs(x) + abs(y) + parent.g
        self.beggining = 0
        self.came_from = (parent.x, parent.y)
        self.parent = parent

def sortbyF(node):
    return node.f

def manhattan(current, final):
    return abs(current.x - final.x) + abs(current.y - final.y)

def check_List(list, successor):
    for ind, val in enumerate(list):
            if (val.x, val.y) == (successor.x, successor.y):
                if val.f < successor.f:
                    return 1
    return 0

openlist = []
closedlist = []

def recursion(node):
    if node.beggining is 0:
        closedlist.append(node.came_from)
        recursion(node.parent)

def pfind(grid, start, finish):

    start_node = Node((start[0], start[1]))
    finish_node = Node((finish[0], finish[1]))
    Stop = 0
    openlist.append(start_node)

    while len(openlist) is not 0:
        current = openlist.pop(0)

        for dirs in Dir_Map.values():
            suc = Child(dirs[0], dirs[1], current)

            if grid[suc.x][suc.y] is not 1 and suc.x <= len(grid[:][1]) and suc.y <= len(grid[1][:]):
                suc.update(finish_node)

                if (suc.x, suc.y) == finish:
                    #Added so it adds the last step.
                    #New suc.came_from = finish
                    suc = Child(dirs[0], dirs[1], suc)
                    #retrace the path.
                    recursion(suc)
                    closedlist.reverse()
                    return closedlist

                if check_List(openlist, suc):
                    continue

                openlist.append(suc)

            else:
                 continue

        openlist.sort(key=sortbyF)

    return None

grid = [[0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

print(pfind(grid, (0,0), (4,3)))

There is some reasonable general algorithmic and python-specific advice here.

The lesson that needs to precede everything is, until you know where you're spending your time, you can't work out how to speed things up. It's well worth learning to use python's cProfile or another profiling tool.

Here's a run with the profiler of your example.

C:\Users\Josiah\Desktop>python -m cProfile -s cumtime astar.py
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]
         6911416 function calls (6911411 primitive calls) in 8.103 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    8.103    8.103 {built-in method builtins.exec}
        1    0.000    0.000    8.103    8.103 astar.py:2(<module>)
        1    0.042    0.042    8.102    8.102 astar.py:59(pfind)
    15538    6.918    0.000    6.918    0.000 astar.py:43(check_List)
     2082    0.645    0.000    1.087    0.001 {method 'sort' of 'list' objects}
  6719169    0.442    0.000    0.442    0.000 astar.py:37(sortbyF)
    16658    0.019    0.000    0.031    0.000 astar.py:28(__init__)
    15539    0.008    0.000    0.018    0.000 astar.py:22(update)
    16660    0.010    0.000    0.010    0.000 astar.py:13(__init__)
    15539    0.008    0.000    0.010    0.000 astar.py:40(manhattan)
    64394    0.004    0.000    0.004    0.000 {built-in method builtins.abs}
    33161    0.003    0.000    0.003    0.000 {built-in method builtins.len}
     2083    0.002    0.000    0.002    0.000 {method 'pop' of 'list' objects}
     8494    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
     2083    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.__build_class__}
      6/1    0.000    0.000    0.000    0.000 astar.py:53(recursion)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 astar.py:12(Node)
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
        1    0.000    0.000    0.000    0.000 astar.py:27(Child)

cumtime is the amount of time spent in a function and all functions it calls.
tottime is the amount of time just spent in the function.

What you can see is that the whole run takes 8.1 seconds, and 6.9 of those are spent directly inside check_List. That's 85% of the whole program's runtime, and basically the only place that's worth optimising. After all, even if you got everything else to take no time at all, you'd only reduce your runtime by 15%. Your only options are call check_List less or make it faster.

The purpose of check_List is to determine whether successor is the fastest way seen thus far to get to wherever successor goes to. You've done that by looping over a list. It would be faster to maintain and check a dictionary of all the places you've seen thus far.

That is, change check_list to check_dict

def check_dict(openDict, successor):
    if (successor.x, successor.y) in openDict:
        return openDict[(successor.x, successor.y)].f < successor.f
    return False

and instead of

            if check_List(openlist, suc):
                continue

            openlist.append(suc)

You'd want

            if check_Dict(openDict, suc):
                continue

            openlist.append(suc)
            openDict[(suc.x, suc.y)] = suc

My variation, which changes nothing except replacing check_list with check_dict as above, runs in 0.025 seconds instead of 8.1.

You might notice that that is significantly better than an 85% speed up, which seems odd because 15% of the run time wasn't actually in check_list at all.

As it happens, my variation fixes a subtle bug that I didn't see initially. As above, check_list is meant to prevent you from revisiting nodes that you've already found a way to. It does that by exhaustively checking all the nodes that you are currently considering for a next step. However, that's not the same! Because of current = openlist.pop(0) there are some entries that you have found routes to, but are no longer part of openlist! Because you don't have any indicator to avoid going back to them, you bounce back and forth among your early nodes.

Patching that bug by separately storing each node you pop off into current and searching them as well in check_list gets almost as good performance as using the dictionary. Well, it doesn't. It takes 0.125 seconds on my machine, which is a whole five times slower than the dictionary, and liable to get worse as the graph gets bigger. But it's a good sight better than 8 seconds!


Codility MaxCounters peformance in Python capping out at 77% performance My problem is quite similar to the question found here, except I am attempting to answer the question in Python.

  Given an array of N counters, all initialized to 0, and an array A representing a series of operations, find the final state of the counters.  Each entry in A should be interpreted as follows:

  If 1 ≤ A[k] ≤ N, then increase the counter at A[k] by 1.
  If A[k] = N + 1, then set all counters to current maximum value.

def solution(N, A):
    # write your code in Python 2.7
    counters = [0] * N
    max_count = 0
    for x in A:
        if 1 <= x and x <= N:
            counters[x-1] += 1
            if counters[x-1] > max_count:
                max_count += 1
        else:
            counters = [max_count] * N
    return counters

Nothing I can come up with allows me to do this in \$O(N + M)\$ time. I get rid of any max() functions going through the list by keeping track of it, but for the life of me I don't know how one is supposed to update N different variables M times (worst case scenario) without it being \$O(N * M)\$.

I am asking this question because I am uncertain what this question even asks is possible without having N processors to bring the \$O(N)\$ by itself stage of updating the counter array down to \$O(1)\$ through parallelization. Since the other question hasn't been answered, I guess what I want to know is if there is a data structure or some other heuristic that will get this down to \$O(M + N)\$.

What hurts your performance is filling the array with max_count. So don't do it. Imply it. The trick is all there, and it makes this slightly different from trying to execute a literal transcription of the problem.

Spelling out the details would rob pundits of the enjoyment of puzzling...

I don't know about Codility, but elsewhere the tasks can often be solved with efficient coding of a naive algorithm (especially in C/C++) instead of solving the puzzle algorithmically. Sometimes I try the 'raw firepower' solution as well, if it promises an interesting challenge. But only after finding the real solution, since each puzzle is basically about finding a specific trick that goes beyond the naive algorithm.

Given that people do these challenges for the puzzle value I think it would defeat their purpose if we posted complete solutions.

P.S.: the sketched solution reduces runtime only to M * log(M) + N or M * C + N but that should be sufficient (and enough of a hint).