Hangman Game Efficiency To put it simply, I'm making a hangman game and it works as it is, it correctly outputs what I want it to, and I have no problem with submitting it now. I only wish to make it more efficient, and I doubt it's at max efficiency as it is. So here it is.
"""
This code runs a hangman game for the user.
"""
# This function gets the user's guess for the letter and determines if its correct
def get_guess():
    global user_guess
    while True:
        user_guess = input("Guess a letter: ")
        if user_guess.isnumeric():
            print("That is not a letter!")
        elif len(user_guess) > 1:
            print("You can only enter one letter!")
            continue
        elif user_guess.islower() == False:
            print("Remember to enter a lowercase letter, but I'll swap it for you this time :)")
            return user_guess.lower()
        else:
            return user_guess

# This function updates the dashes that the code outputs, this function displays the progress
# of the user's guess for the secret word
def update_dashes(secret_word, dashes, user_guess):
    for i in range(len(secret_word)):
        if secret_word[i] == user_guess:
            dashes  = dashes[:i] + user_guess + dashes[i + 1:]
            return dashes

# This imports the random function
import random
# This list defines what words the random.choice method can select from for hangman
words = ["jazz", "hello", "bird", "birds", "peanut", "butter", "cake", "hallway"]
# This secret_word defines a random word from the list for the user to guess
secret_word = random.choice(words)
# This variable defines the progress meter of dashes based on the length of the random word
dashes = "-" * len(secret_word)
# This variable defines the number of tries the user starts with and has left
tries = 10
# This while statement updates the user's progress for guessing the word
while tries > 0 and dashes != secret_word:
    print(dashes)
    guess = get_guess()
    dashes = update_dashes(secret_word, dashes, user_guess)
    if guess in secret_word:
        print("That letter is in the secret word!")
    else:
        print("That letter is not in the secret word.")
        tries = tries - 1
         print("You have " + str(tries) + " tries left.")

# This if statement determines if the user has won or lost based on their tries or if the
# progress meter is full
if tries == 0:
    print("You ran out of guesses, the word was " + secret_word + ".")
    print("--------------------------YOU LOSE----------------------------")
elif dashes == secret_word:
    print(dashes)
    print("You guessed correctly, the word was " + secret_word + "!")
    print("--------------------------YOU WIN!----------------------------")

Welcome to CodeReview! Your general structure is already pretty good and the comments made the code easy to read. Here are some key suggestions and explanations. The full code can be found at the bottom.

Comments
Comments should generally not (have to) explain every single line, especially really simple lines like an import:
# This imports the random function
import random

Any Python developer that reads this will know what the line does. Adding a comment here significantly increases the time needed to read and understand the code, so I'd advise against simple comments like this.

f-Strings
f-Strings offer a convenient and readable way to print text that includes variables:
print("You have " + tries + " tries left.")

becomes
print(f"You have {tries} tries left.")

dashes and update_dashes
Since you need to modify dashes multiple times I would suggest a mutable data type instead of a str, e.g. a list.
dashes = ["-"] * len(secret_word)

Since it's now a list, we would need to print it by calling "".join(dashes). We'll put that in its own seperate __str__ function in the next point.
This allows for a more concise definition of update_dashes(...):
def update_dashes(secret_word, dashes, user_guess):
    for index, letter in enumerate(secret_word):
        if letter == user_guess:
            dashes[index] = user_guess

Multiple things to notice here:

dashes is modified in-place, therefore we don't need to return it. Passing it to the function is enough.
Using enumerate will give us index and letter for all letters in secret_word. This approach is more pythonic than iterating over a range and accessing the elements by their index.
We do not immediately return once we find a matching letter. This is important because we can have multiple occurences of the same letter in secret_word.

class Dashes
I would say dashes combines enough unique logic, for it to make sense to make it a standalone-class. This comes down to some personal preference, but I find it improves the code structure here.
class Dashes:
    PLACEHOLDER = "-"

    def __init__(self, secret_word):
        self.secret_word = secret_word
        self.letters = [self.PLACEHOLDER] * len(secret_word)

    def update(self, guess):
        for index, letter in enumerate(self.secret_word):
            if letter == guess:
                self.letters[index] = guess

    def is_completed(self):
        return self.PLACEHOLDER not in self.letters

    def __str__(self):
        return "".join(self.letters)

As you can see, Dashes now handles a lot of useful logic for the rest of our program.

Complete code
Some other points worth mentioning:

You should avoid using global variables as far as possible. Global variables aren't good practice, as they can lead to some unexpected behaviour / confusing bugs.
Wrapping your program's main functionality into a main() function is generally good practice. Wrapping your call to main() into a if __name__ == '__main__': condition is also a good idea. You can read more about it here.
For if-conditions that break or continue a loop or return from a function, it often improves readability to move them into seperate conditions instead of an if ... elif ... elif ... else construct.
user_guess.islower() == False is equivalent to not user_guess.islower(), and even better user_guess.isupper().
When checking if user input is not a letter, you should use not user_guess.isalpha() instead of only checking for numbers with user_guess.isnumeric().
tries = tries - 1 is equivalent to tries -= 1.
Imports should usually be found at the top of your code file.
We only need to update dashes if the user_guess is in secret_word.
The length of secret_word will probably never be performance-critical. In general, if we need to perform multiple (performance-critical) membership tests (e.g. letter in word), sets provide lookups in constant instead of linear time.

Here's the full code without comments:
from random import choice

class Dashes:
    PLACEHOLDER = "-"

    def __init__(self, secret_word):
        self.secret_word = secret_word
        self.letters = [self.PLACEHOLDER] * len(secret_word)

    def update(self, guess):
        for index, letter in enumerate(self.secret_word):
            if letter == guess:
                self.letters[index] = guess

    def is_completed(self):
        return self.PLACEHOLDER not in self.letters

    def __str__(self):
        return "".join(self.letters)

def get_guess():
    while True:
        user_guess = input("Guess a letter: ")

        if not user_guess.isalpha():
            print("That is not a letter!")
            continue

        if len(user_guess) != 1:
            print("You can only enter one letter!")
            continue

        if user_guess.isupper():
            print("Remember to enter a lowercase letter, but I'll swap it for you this time :)")
            return user_guess.lower()

        return user_guess

def main():
    words = ["jazz", "hello", "bird", "birds", "peanut", "butter", "cake", "hallway"]
    secret_word = choice(words)

    dashes = Dashes(secret_word=secret_word)

    tries = 10

    while tries > 0 and not dashes.is_completed():
        print(dashes)
        user_guess = get_guess()

        if user_guess in secret_word:
            print("That letter is in the secret word!")
            dashes.update(user_guess)
        else:
            print("That letter is not in the secret word.")
            tries -= 1
            print(f"You have {tries} tries left.")

    if dashes.is_completed():
        print(dashes)
        print(f"You guessed correctly, the word was {secret_word}!")
        print("--------------------------YOU WIN!----------------------------")
    else:
        print(f"You ran out of guesses, the word was {secret_word}.")
        print("--------------------------YOU LOSE----------------------------")

if __name__ == "__main__":
    main()


Simple decision tree in Haskell I've been trying to get better at Haskell for a while, and have recently been working on a lot of small projects with it. This constructs a binary decision tree.

The command to run it is:

stack exec decision-tree-exe <threshold> <training file> <testing file>

where threshold is in the range (0,1].

I think I've gotten a lot better, but I'm still having problems, especially with performance and readability. For this project, I took a more top down approach, implementing functions after using them. src/DecisionTree.hs is where the bulk of the logic is, and the file is pretty much in order of writing. I would love to get some feedback from some more experienced people on where I might improve.

module DecisionTree where

import Data.List (genericLength, maximumBy, nub)
import Data.Map (elemAt, foldlWithKey', fromListWith)
import Data.Ord

data DecisionTree a b
  = Node ([a] -> Bool) (DecisionTree a b) (DecisionTree a b)
  | Leaf b

type Dataset cat attrs = [(cat, [attrs])]

type Threshold = Double

type Splitter c a = ([a] -> Bool, Dataset c a, Dataset c a)

apply :: DecisionTree a b -> [a] -> b
apply (Leaf b) _ = b
apply (Node f l r) a =
  case f a of
    False -> apply l a
    True -> apply r a

train ::
     (Ord c)
  => (Dataset c a -> Maybe (Splitter c a))
  -> Dataset c a
  -> DecisionTree a c
train splitter dataset =
  case splitter dataset of
    Just (partitioner, left, right) ->
      Node partitioner (train splitter left) (train splitter right)
    Nothing -> Leaf majority
  where
    classCounts = fromListWith (+) $ map (\k -> (fst k, 1)) dataset
    majority = fst $ foldlWithKey' max (elemAt 0 classCounts) classCounts
    max acc k v
      | v > snd acc = (k, v)
      | otherwise = acc

giniSplitter ::
     (Ord a, Ord c) => Threshold -> Dataset c a -> Maybe (Splitter c a)
giniSplitter threshold dataset =
  case fst maxDelta > threshold of
    True -> Just $ snd maxDelta
    False -> Nothing
  where
    attrs = nub . concat . snd . unzip $ dataset
    partitioner a = (a `elem`)
    delta a = giniDelta (partitioner a) dataset
    maxDelta = maximumBy (comparing fst) $ map delta attrs

giniDelta :: (Eq c) => ([a] -> Bool) -> Dataset c a -> (Double, Splitter c a)
giniDelta partitioner dataset =
  ( gini dataset - (d1 / d * gini left + d2 / d * gini right)
  , (partitioner, left, right))
  where
    left = filter (not . partitioner . snd) dataset
    right = filter (partitioner . snd) dataset
    d1 = genericLength left
    d2 = genericLength right
    d = genericLength dataset

gini :: (Eq c) => Dataset c a -> Double
gini d = 1 - sum [(pj c) ** 2 | c <- nub . fst . unzip $ d]
  where
    pj c = genericLength (filter ((== c) . fst) d) / genericLength d

Just a few random comments:

Both elemAt and maximumBy give hints that you're expecting to operate on non-empty structures. Maybe give Data.List.NonEmpty a try.
A few places could be more clear with more pattern matching. E.g. max (k1, v1) k2 v2 instead of max acc k v. Or (maxDelta, splitter) = maximumBy …
map snd is more conventional than snd . unzip. I suspect it would be more efficient too but I might be wrong.
In several places you're traversing the same list multiple times. In general, it's better to avoid this as it's likely to force the spine of the (potentially large) list in memory. You might be able to merge these multiple traversals into one (e.g. using the foldl package). More likely, you should simply use vector.
In giniDelta you could use Data.List.partition to construct left and right.
Apply top-down ordering in your where-clauses. E.g. in train, majority should come first as it is the declaration that is referenced from the main function body.

EDIT: All in all I think readability is actually pretty good!


Rails passing in params to association on create method I am currently using a belongs_to relationship in my Rails application to link a map and a group an object that way I can assign those maps to the user based on the group they are in.

I have this mapgroup model.

class Mapgroup < ApplicationRecord
  belongs_to :map, optional: true
  belongs_to :group, optional: true
end

I am getting the map from a dropdown menu in the form but I don't want a dropdown for the group because the use is already in that group.

I opted to assign the group_id in the url to the mapgroup in the create method.

def create
  @mapgroup = Mapgroup.create(mapgroup_params)
  @mapgroup.group_id = params[:group_id] <-- right here

  respond_to do |format|
    if @mapgroup.save
      format.html { redirect_to groups_path, notice: 'Mapgroup crated' }
    else
      format.html { render :new, notice: 'That shit failed' }
    end
  end
end

Is this a good practice? I have done this in previous apps but it seems a bit...smelly. Is there a more elegant way to do this?

You have two issues here:

need to find parent model first, and then build association (as group_id could be wrong)
create would try to save record, so you're trying to save twice. Use build/new instead.

    def create
      @group = Group.find(params[:group_id])
      @mapgroup = @group.mapgroups.build(mapgroup_params)

      respond_to do |format|
        if @mapgroup.save
          format.html { redirect_to groups_path, notice: 'Mapgroup crated' }
        else
          format.html { render :new, notice: 'That shit failed' }
        end
      end
    end


Making empty cells in Underscore template From the back-end, I am receiving 8 data. The client requires showing that the row per data is 7, so I have 1 data in balance. I have created empty data and made the empty cells, which works fine. But is it a correct approach to using Underscore templates?

Here is the live demo

Template:

JavaScript:

var obj = {
"schemeCodeDetails": [
    { "schemeCode": "AFN"},{"schemeCode": "BBT"},{"schemeCode": "BCH*"},
    {"schemeCode": "BCY*"},{"schemeCode": "BDP"},{"schemeCode": "BDQ"},{"schemeCode": "BDV"}, {"schemeCode": "BDW" } ]
}
for(i=0;i<  obj.schemeCodeDetails.length % 7; i++){
    obj.schemeCodeDetails.push({"schemeCode": ""});
}

    var temp = _.template($('#scheme').html());

    $('body').append(temp(obj));

For one thing, the
 is opened but never closed here:

<% _.each(schemeCodeDetails, function (item, index) { %>
    <%= index % 7 == 0 ? '
' : null %>

                <%= item.schemeCode %>

<% }) %>

For another, it would be better if the template didn't have knowledge about the number 7 at all, for two reasons:

Right now both the JavaScript and the template share this number. If you change it in one place, you must remember to change in the other too.
The template needs special handling for the empty cells, using % 7. Ideally templates should be kind of dumb, and have as little logic as possible.

I suggest organizing the data into rows in the JavaScript, for example in obj.rows, like this:

var obj = {
    "schemeCodeDetails": [
        {"schemeCode": "AFN"},
        {"schemeCode": "BBT"},
        {"schemeCode": "BCH*"},
        {"schemeCode": "BCY*"},
        {"schemeCode": "BDP"},
        {"schemeCode": "BDQ"},
        {"schemeCode": "BDV"},
        {"schemeCode": "BDW"}
    ],
    "rows": []
};

var maxItemsPerRow = 7;
var i;
for (i = 0; i < obj.schemeCodeDetails.length; i++) {
    if (i % maxItemsPerRow == 0) obj.rows.push([]);
    obj.rows[obj.rows.length - 1].push(obj.schemeCodeDetails[i]);
}

for (var j = i % maxItemsPerRow; j < maxItemsPerRow; j++) {
    obj.rows[obj.rows.length - 1].push({"schemeCode": ""});
}

var template = _.template($('#scheme').html());

$('body').append(template(obj));

Using the new field, you could rewrite the HTML like this:


Hierarchical data structure using classes My code implements the following structure :Module contains Submodule contains Ability contains Template. There is so much repetition that I'm sure there is a better way.

class Module:
    def __init__(self, name, lang):
        assert lang in ['fr', 'en']
        self.name = name
        self.lang = lang
        self.submodules = {}

    def add_submodule(self, submodule):
        assert isinstance(submodule, Submodule)
        assert submodule.name not in self.submodule
        self.submodules[submodule.name] = submodule

class Submodule:
    def __init__(self, name, module):
        self.name = name
        self.link_with(module)
        self.abilities = {}

    def add_ability(self, ability):
        assert isinstance(ability, Ability)
        assert ability.name not in self.abilities
        self.abilities[ability.name] = ability

    def link_with(self, module):
        assert isinstance(module, Module)
        self.module = module
        module.add_submodule(self)

class Ability:
    def __init__(self, name, submodule):
        self.name = name
        self.link_with(submodule)
        self.templates = {}

    def add_template(self, template):
        assert isinstance(template, Template)
        assert template.name not in self.templates
        self.templates[template.name] = template

    def link_with(self, submodule):
        assert isinstance(submodule, Submodule)
        self.submodule = submodule
        submodule.add_ability(self)

class Template:
    def __init__(self, name, ability):
        self.name = name
        self.link_with(ability)
        self.lang = ability.submodule.module.lang

    def link_with(self, ability):
        assert isinstance(ability, Ability)
        self.ability = ability
        ability.add_template(self)

I could have coded a global function "link_to_parent" and set 'childs' sets and 'parent' set but I prefer to be able to do : ability.submodule.module instead of doing ability.parent.parent which is not explicit enough.

YOU ARE IN A MAZE OF TWISTY LITTLE CLASSES, ALL ALIKE

So when seeing a bunch of classes that are all very similar, I start to think Metaclass!  So let's give that a whirl.

Below I will discuss a refactor of your implementation using a metaclass.  The metaclass will allow us to implement the parent/child relationships generically, but then also gives us ready access to the same infrastructure using names which are not parent/child

What are metaclasses?

Metaclasses are classes that create classes.  This in the same relationship wherein classes are used to create objects.  Take for instance this class declaration:

# Static class declaration
class AClass(int):

    a_class_attribute = 'twisty'

The above can be equivalently declared by calling type directly as:

# Dynamic (meta) declaration
AClass = type('AClass', (int,), {'a_class_attribute': 'twisty'}).

And in this case type is the metaclass of AClass, since it is called to make a class.

I won't go any farther in this explanation because it can go on for a while, and there are lot's of resources to read on this topic.

Removing Common Code

So the data structure under discussion consists of 4 classes that are hierarchical as

class Module: a container for instances of:
class Submodule: a container for instances of:
class Ability: a container for instances of:
class Template:

The code then consists of various boiler plate for the management of the tree.  Let's refactor the various boilerplate into a metaclass, and a base class, to remove the common code.

Metaclass as a class

Our metaclass inherits from type and has the same signature:

class ModuleMetaClass(type):

    def __init__(cls, name, bases, attrs):

This __init__ method will be called every time we declare one of our classes.  In this __init__, we do the bookkeeping necessary to relate the classes to one another.  Basic idea is that we will declare our classes in the order they appear in the hierarchy.  Thus the first declaration will be for Module, and the second for Submodule, etc.  Then in the ModuleMetaClass.__init__ we can relate the classes to each other as parent/child.

__init__ starts with:

if cls._metaclass_instances is None:
    # First instance is ModuleBaseClass
    cls._parent_class = None
    cls._metaclass_instances = [type(None)]

here, we initialize the list of classes that will be instantiated, and note that this class being at the top of the tree has no parent. Continuing...

else:
    # parent class is the previously declared class
    cls._parent_class = cls._metaclass_instances[-1]

    # if not at the top of the tree, then we are our parent's child
    if cls._parent_class != type(None):
        cls._parent_class._child_class = cls

    # store this class in the list of classes
    cls._metaclass_instances.append(cls)

will note that our parent class is at the end of the class list (ie: last added), then if we have a parent, register us as his child, and then add ourselves to the end of the class list.

And that is basically it for the metaclass.  There is a bit more bookkeeping, but see the full listing at the bottom of the post for that.

A Base Class to manage the tree relationships

The first instance of our metaclass (ModuleMetaClass) will be a base class for each of the node types. Class starts with:

class ModuleBaseClass(metaclass=ModuleMetaClass):
    """ Base class for each of the derived classes in our tree """

This indicates that our class will be built by instantiating a ModuleMetaClass.  ModuleBaseClass.__init__() contains the boilerplate from the original data structure and the meta bits to allow our named attributes.  The fun bits start with:

# child class variable plural is used to add a common name
plural = getattr(self._child_class, '_plural')
if plural is not None:
    setattr(self, plural, self._children)

This code uses the information stored in the class hierarchy from the metaclass to add an access attribute to this node's children.  Similarly:

# add an access attribute for each of the nodes above us in the tree
while parent is not None:
    setattr(self, type(parent).__name__.lower(), parent)
    parent = parent._parent

adds an access attribute to our parent node, and his parent and... all the way to the top of the tree.  The original implementation only had an accessor for the immediate parent.

Declaring our classes

So the remaining code contains the operative elements of the classes themselves, with all of the common boilerplate removed to ModuleBaseClass and ModuleMetaClass.

class Module(ModuleBaseClass):
    def __init__(self, name, lang):
        super().__init__(name, None)
        assert lang in ['fr', 'en']
        self.lang = lang

class Submodule(ModuleBaseClass):
    _plural = 'submodules'

class Ability(ModuleBaseClass):
    _plural = 'abilities'

class Template(ModuleBaseClass):
    _plural = 'templates'

    def __init__(self, name, ability):
        super().__init__(name, ability)
        self.lang = module.lang

Note the last line where Template was able to reach all the way up to Module.lang to retrieve the language.

Full Code Listing

class ModuleMetaClass(type):
    """ Metaclass that is instantiated once for each class """
    _metaclass_instances = None

    def __init__(cls, name, bases, attrs):

        if cls._metaclass_instances is None:
            # First instance is ModuleBaseClass
            cls._parent_class = None
            cls._metaclass_instances = [type(None)]
        else:
            # parent class is the previously declared class
            cls._parent_class = cls._metaclass_instances[-1]

            # if not at the top of the tree, then we are our parent's child
            if cls._parent_class != type(None):
                cls._parent_class._child_class = cls

            # store this class in the list of classes
            cls._metaclass_instances.append(cls)

        # no child class yet
        cls._child_class = None

        # call our base (meta) class init
        super().__init__(name, bases, attrs)

class ModuleBaseClass(metaclass=ModuleMetaClass):
    """ Base class for each of the derived classes in our tree """

    def __init__(self, name, parent):
        assert isinstance(parent, self._parent_class)
        self.name = name
        self._parent = parent

        if self._child_class is not None:
            self._children = {}

            # child class variable plural is used to add a common name
            plural = getattr(self._child_class, '_plural')
            if plural is not None:
                setattr(self, plural, self._children)

        # add self to our parents collection
        if parent is not None:
            parent._add_child(self)

        # add an access attribute for each of the nodes above us in the tree
        while parent is not None:
            setattr(self, type(parent).__name__.lower(), parent)
            parent = parent._parent

    def _add_child(self, child):
        assert isinstance(child, self._child_class)
        assert child.name not in self._children
        self._children[child.name] = child

# --------------------------------

class Module(ModuleBaseClass):
    def __init__(self, name, lang):
        super().__init__(name, None)
        assert lang in ['fr', 'en']
        self.lang = lang

class Submodule(ModuleBaseClass):
    _plural = 'submodules'

class Ability(ModuleBaseClass):
    _plural = 'abilities'

class Template(ModuleBaseClass):
    _plural = 'templates'

    def __init__(self, name, ability):
        super().__init__(name, ability)
        self.lang = module.lang

# --------------------------------

module = Module('module1', 'fr')
sub_module1 = Submodule('sub_module1', module)
sub_module2 = Submodule('sub_module2', module)
ability = Ability('ability1', sub_module1)
template = Template('template1', ability)
print(template.lang)


De-linearize a 2d linearized grid and calculate distance between 2 points In a simulation of mine, for which performance is paramount, I have the following bottleneck.

I have a huge 2D grid of dimensions width and height, whose dimensions are stored in linearized form, i.e. positions at x and y are stored as one integer x + y*width. Every iteration I have to get thousands of such linearized coordinates, de-linearize an calculate distance between 2d coordinates.

Currently, what I do is:

y1 = linPos1 / width; //int divided by int disregards remainders
x1 = linPos1 - width * y1;

y2 = linPos2 / width; //int divided by int disregards remainders
x2 = linPos2 - width * y2;

int xDiff = x2-x1;
int yDiff = y2-y1;
double distance = sqrt(xDiff*xDiff  + yDiff*yDiff);

How could I improve upon that? What is the most performant way to take two of such integer values, retrieve back x and y and then calculate the 2D distance between said points? I am open to all suggestions, including SIMD instructions.

What you are doing is packing the two integer coordinates into a single integer, then unpacking them.

Let us assume that \$\text{height} \leq \text{width}\$, let w = width. Translate the lattice so that \$ 0 \leq x,y\leq w-1\$.

Using these assumptions, the packing can be done by writing the coordinates in base w. For example, if w = 10, x=4, and y=7, then the representation is w*y + x = 7*10 + 4 = 74.

Using our assumptions this is an injective function, i.e. to one pair \$(x,y)\$ there exists at most one \$k\$ such that \$k=wy+x\$, and each such \$k\$ uniquely determine the \$(x,y)\$. This means that the packing-unpacking is well-defined, which is great: same points will have the same representations, and a representation corresponds to exactly one point.

Your code,

y = k / w;
x = k - w * y;

could be written a few different ways, e.g. using %,

y = k / w
x = k % w

or by using std::div.

Modern compilers will compile all of these to the same instruction: idivl, so you don't have to worry about this part, just don't forget to tell your compiler to optimize slightly. For example, g++ needs the -O1 flag.

So that's about as good as it gets, unless we can use some faster form of integer division(from now on, simply division).

If a number is in base \$b\$, then it's really easy to divide it by powers of \$b\$: just shift the numbers around; e.g. 1234/10^3 = 1, 1234 % 10^3 = 4.

That's all fine and well, but string operations aren't going to be faster than idivl. Luckily we don't need those, because by choosing \$w=2^n\$, we can leverage bit-shifts, and bitwise-and to do exactly the same for us, really fast.

Let's find the smallest \$n \in \mathbb N\$, such that \$w \leq 2^n\$. Let \$ w = 2^n\$. Perhaps you won't use a few coordinates, but that's not really a problem.
Now our division code will look like this.

y = k >> n
x = k & ((1 << n) - 1)

Here x will be the first nth bits of k, and y will be the rest. For example, if k = 1101, n=2, then x = 1101 & ((1 << 2) - 1) = 1101 & (0100 - 0001) = 1101 & 0011 = 0001 = 01, y = 1101 >> 2 = 0011 = 11.

Now let's see if the compilers are clever enough to do this for us automatically.

int func1(int a) {
    int x = a / 1024;
    int y = a % 1024;
    return x+y;
}

int func2(int a) {
    int x = a >> 10;
    int y = a & ((1 << 10) - 1);
    return x+y;
}

Let's see the assembly code generated from the code above, if we allow the compiler to optimize a bit.

_Z5func1i:
    leal    1023(%rdi), %eax
    testl   %edi, %edi
    movl    %edi, %edx
    cmovns  %edi, %eax
    sarl    $31, %edx
    shrl    $22, %edx
    sarl    $10, %eax
    addl    %edx, %edi
    andl    $1023, %edi
    subl    %edx, %edi
    addl    %edi, %eax
    ret

_Z5func2j:
    movl    %edi, %eax
    andl    $1023, %edi
    shrl    $10, %eax
    addl    %edi, %eax
    ret

As you can see, besides some sign-checking, the two codes are identical. In fact, after specifying that we are working with unsigned integers, we get the same output:

    movl    %edi, %eax
    andl    $1023, %edi
    shrl    $10, %eax
    addl    %edi, %eax
    ret

This means that we can keep our more readable operators: %, and /. Hurray!

Now let's look at the last part of your code, and let's change it to a more general formula.

double distance = metric(xDiff,yDiff);

Where metric is a function calculating a distance. In your case, metric corresponds to the Euclidean metric,

double metric(int dx, int dy) {
   return std::sqrt(dx*dx+dy*dy);
}

Depending on your needs, you could use other metrics; as you are working on an integer lattice, I'd suggest you take a look at the taxicab metric. Its calculation is faster, and there is less room for numerical errors.

double metric(int dx, int dy) {
   return std::abs(dx) + std::abs(dy);
}

Implementing these changes result in code, which is a constant time faster, than your
original one.

While it was fun figuring out, I doubt this is the kind of speed up you were hoping for. I think optimizing other parts of your code could have greater benefits. Perhaps consider posting them as a separate question.


Conditionally copying cells from other worksheets I wrote super redundant VBA code and it works and solve my problem. I am trying to simplify it but don't know where to start due to my limited knowledge in VBA.

Basically, this code works as a vlookup function and return all required data from other sheets in the same workbook. I have multiple columns to be filled so I repeat using the same codes. But I believe there is a much more neat version rather than mine.

Sub LoopTem()

Dim ws As Worksheet
Dim ws1 As Worksheet
Dim ws2 As Worksheet
Dim ws3 As Worksheet
Dim ws4 As Worksheet
Dim ws5 As Worksheet
Dim ws6 As Worksheet
Dim ws7 As Worksheet

Dim i As Integer
Dim r As Integer
Dim s As Integer
Dim t As Integer
Dim u As Integer
Dim v As Integer
Dim w As Integer

Dim lastRow As Integer
Dim lastRow2 As Integer
Dim lastRow3 As Integer
Dim lastRow4 As Integer
Dim lastRow5 As Integer
Dim lastRow6 As Integer
Dim lastRow7 As Integer

Set ws = Worksheets("Proactive Template")
Set ws2 = Worksheets("To")
Set ws3 = Worksheets("Copy")
Set ws4 = Worksheets("Comment")
Set ws5 = Worksheets("PAM Consolidation")
Set ws6 = Worksheets("PSS Contact")
Set ws7 = Worksheets("Mapping")

lastRow = ws.Range("Q" & Rows.Count).End(xlUp).Row
lastRow2 = ws2.Range("Q" & Rows.Count).End(xlUp).Row
lastRow3 = ws3.Range("Q" & Rows.Count).End(xlUp).Row
lastRow4 = ws4.Range("A" & Rows.Count).End(xlUp).Row
lastRow5 = ws5.Range("A" & Rows.Count).End(xlUp).Row
lastRow6 = ws6.Range("A" & Rows.Count).End(xlUp).Row
lastRow7 = ws7.Range("L" & Rows.Count).End(xlUp).Row

For i = 2 To lastRow
For r = 2 To lastRow2
    If ws.Cells(i, 18) = ws2.Cells(r, 17) Then
       ws.Cells(i, 20) = ws2.Cells(r, 19)
    Exit For
    End If
Next r
Next i

For i = 2 To lastRow
For s = 2 To lastRow3

    If ws.Cells(i, 18) = ws3.Cells(s, 17) Then
       ws.Cells(i, 21) = ws3.Cells(s, 19)
    Exit For
    End If
Next s
Next i

For i = 2 To lastRow
For t = 2 To lastRow4
    If ws.Cells(i, 14) = ws4.Cells(t, 1) Then
       ws.Cells(i, 19) = ws4.Cells(t, 2)
    Exit For
    End If
Next t
Next i

For i = 2 To lastRow
For u = 2 To lastRow5
    If ws.Cells(i, 11) = ws5.Cells(u, 1) Then
       ws.Cells(i, 22) = ws5.Cells(u, 2)
    Exit For
    End If
Next u
Next i

   For i = 2 To lastRow
For v = 2 To lastRow6
   If ws.Cells(i, 11) = ws6.Cells(v, 1) Then
      ws.Cells(i, 23) = ws6.Cells(v, 3)
      ws.Cells(i, 24) = ws6.Cells(v, 2)
      ws.Cells(i, 25) = ws6.Cells(v, 4)

      Exit For
   End If
Next v
Next i

For i = 2 To lastRow
For w = 2 To lastRow6
   If ws.Cells(i, 10) = ws7.Cells(w, 12) Then
      ws.Cells(i, 26) = ws7.Cells(w, 13)
      Exit For
   End If
Next w
Next i

ws.Cells.WrapText = False

End Sub

There are two different ways you could go about DRYing this up.
1) Create a subroutine that takes some parameters.
I want to show you this first, because it's very important to learn this concept. Anytime you see patterns like below, you should be extracting out new subroutines or functions.

For i = 2 To lastRow
For r = 2 To lastRow2
    If ws.Cells(i, 18) = ws2.Cells(r, 17) Then
       ws.Cells(i, 20) = ws2.Cells(r, 19)
    Exit For
   End If
Next r
Next i

For i = 2 To lastRow
For s = 2 To lastRow3

    If ws.Cells(i, 18) = ws3.Cells(s, 17) Then
       ws.Cells(i, 21) = ws3.Cells(s, 19)
    Exit For
    End If
Next s

If you look carefully at this, you'll notice that the only difference between these loops is the source column, the destination sheet, and the destination column.
Sub CopyData(souceWs As Worksheet, sourceCol As Long, destWs as Worksheet, destCol As Long)
    Dim lastRow As Long, destLastRow As Long
    lastRow = sourceWs.Range("Q" & Rows.Count).End(xlUp).Row
    destLastRow = destWs.Range("Q" & Rows.Count).End(xlUp).Row

    Dim i As Long, j As Long
    For i = 2 To lastRow
        For j = 2 To destLastRow
            If destWs.Cells(i, 18) = sourceWs.Cells(r, 17) Then
                destWs.Cells(i, destCol) = sourceWs.Cells(r, sourceCol)
                Exit For
            End If
        Next j
    Next i
End Sub

And then call this subroutine from your main routine once for each sheet that needs to be processed.
CopyData Worksheets("To"), 19, ws, 20
CopyData Worksheets("Copy"), 19, ws, 21
'etc

However, this would be terribly slow if there is a large amount of data to process. It would loop through the entire destination once for every call to CopyData.
2) Move everything inside of the outer loop.
There's no sense in looping from 2 To destLastRow over and over again. The code gets DRYed up a good bit and sees a performance boost by moving the logic inside.
For i = 2 To destLastRow

    sourceWs = Worksheets("To")
    lastRow = sourceWs.Range("Q" & Rows.Count).End(xlUp).Row

    For j = lastRow
        'do stuff
    Next j

    sourceWs = Worksheets("Blah")
    lastRow = sourceWs.Range("Q" & Rows.Count).End(xlUp).Row

    For j = lastRow
        'do stuff
    Next j

    'etc

Next i

At this point there's still some duplication, so you could use the concepts from #1 to extract the inner loop to its own subroutine.
Some other things you could do better:

The inside of each For block should be one indentation level (1 tab or four spaces) deeper. It's easier to follow.

I know a lot of people innocently recommend not reusing variable names, but sometimes it's cleaner to do so. Your inner loop counter was way up past r in the alphabet. Note how I reused j above once I was done with the previous loop. It just makes for less to remember. Just make sure that you're actually done with these generic variables before reusing them.

Don't number variables. If you catch yourself numbering variables, do exactly what you did =;)- Stop and look for a way to clean it up with a loop, subroutine, function, etc. If you just can't avoid it, give them meaningful names like sourceSheet and destSheet.


Implementing `Promise.all()` I took a stab at implementing Promise.all():

"use strict";

function all (...promises) {
   const promise = new Promise((resolve, reject) => {
      let counter = 0;
      const values = [];
      let rejected = false;
      promises.forEach(
         (promise, idx) => {
            promise.then(val => {
                  counter++;
                  values[idx] = val;
                  if (counter === promises.length)
                     resolve(values);
               },
               () => {
                  if (!rejected) {
                     reject(new Error(`${promise} was rejected!`));
                     rejected = true;
                  }
               }
            );
         }
      );
   });
   return promise;
};

Good job using const for values, as well as let for re-assignable values like counter and rejected.

Did you test this code? My presumption is that it didn't happen, because when I tried running it, I see the following error:

  error promise.then is not a function

This is because the promises are spread out:

function all (...promises) {

Without the spread operator it appears to run as I would expect, as long as each entry in promises is a promise.

I must admit I compared with another implementation of Promise.all(). In comparison with that function, yours tracks rejected, whereas the other one simply calls reject whenever a promise is rejected.

Another thing I noticed is that the variable name promise is reused - both for the outer promise to be returned by all() as well as the callback to promises.forEach(). It would be wise to use different names to improve readability. In fact there is little need to assign the outer promise - it can simply be returned without being assigned to a variable since it isn't modified after being instantiated.

Another aspect to consider is that Promise.all() can accept promises or non-promises - e.g. the MDN documentation gives an example like this:

const promise1 = Promise.resolve(3);
const promise2 = 42; // <- not really a promise
const promise3 = new Promise(function(resolve, reject) {
  setTimeout(resolve, 100, 'foo');
});

Promise.all([promise1, promise2, promise3]).then(function(values) {
  console.log(values);
}).catch(error => {
   console.log('error: ', error.message);
});
// expected output: Array [3, 42, "foo"]

With your code, it throws the error promise.then is not a function so it might be wise to check if each item is a promise before calling .then() on it.


CSES standard solution for range query problem giving TLE Problem statement is from CSES
This is a standard question where we are given a list of numbers and a number of queries. For each query, you have to give the sum of numbers in the given range.
My implementation in python:
def solve():
    n,q = [int(a) for a in input().split(' ')]
    arr = [int(a) for a in input().split(' ')]

    cumulativeArray = [0] # Initial entry added to make 1 based indexing
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]
        cumulativeArray.append(sum)

    for i in range(q):
        x,y = [int(a) for a in input().split(' ')]
        print(cumulativeArray[y] - cumulativeArray[x-1])

solve()

This gives the required answers correctly for all my custom test cases. But gives TLE for huge test cases.
I believe this is happening due to split() method in my code.
Any leads are welcome.

You are already using the optimal solution algorithm for the problem. A few things, which might speed-up the computations (.split should not be the limiting factor in most likeliness)
Variable naming
Use names which match the problem description, so that it becomes easier to follow your code. So, instead of x, y it'd be a, b. Also, in python, it is a good practice to name your variables in lower_snake_case.
sum is an builtin function. Do not override this.
Computing len
You do not need to iterate over indices as the index is not really being used anyway. Lists can be iterated over their values itself.
Lazy iterators
Instead of generating list inline, you can use generators so that the values are yielded when iterating, and not consuming memory.
.split
Not passing a parameter to .split is same as providing whitespace as parameter.

Rewrite:
def solve():
    n, q = map(int, input().split())
    arr = map(int, input().split())

    cumulative_summation = [0]
    running_sum = 0
    # Not calculating `len` of `arr`, also, you don't need to calculate it.
    # the length is known to be `n`.
    for value in arr:
        running_sum += value
        cumulative_summation.append(running_sum)

    for i in range(q):
        a, b = map(int, input().split())
        print(cumulative_summation[b] - cumulative_summation[a - 1])


C++ code to find distance between line and point So I made this simple program that allows users to construct points and lines and then return the smallest distance between a given point and a line. In doing so I have used some OOP concepts and operator overloading (both of which are fairly new territory for me). As such, I would really appreciate feedback. Furthermore, the code assumes that the user specifies a line by providing two distinct points and that this line is infinite.

#include <vector>
#include <algorithm>
#include <iostream>

class Point {
    public:
    int x;
    int y;
    Point (int x, int y) : x(x), y(y) {};
    Point() : x(0), y(0) {};
};

class Vector {
    public:
        int x;
        int y;
        Vector () : x(0), y(0) {};
        Vector (Point p1, Point p2) : x(p2.x - p1.x), y(p2.y - p1.y) {};
};

class Line {
    public:
    Point start;
    Point finish;
    Vector direction_vector;
    Line(Point st, Point fin) {
        direction_vector = Vector(st, fin);
        start = st;
        finish = fin;
    };
};

int operator^(const Vector& v1, const Vector& v2) {
    int ret = ((v1.x) * (v2.y)) - ((v1.y) * (v2.x));
    //cross product should return 3d vector but for convenience
    //return an int (for example by dotting result with unit z vector)
    return ret;
}

int operator*(const Vector& v1, const Vector& v2) {
    int ret = ((v1.x) * (v2.x)) + ((v1.y) * (v2.y));
    return ret;
}

double distance_line_point(Line l, Point p) {
    Vector AB = l.direction_vector;
    Vector AC(l.start, p);
    int abs = ((AB)*(AB));
    double norm = (double) std::sqrt(abs);
    //return distance by using area of triangle is base*height / 2
    //and then calculate area using cross product
    double dist = ((double) (AB^AC)) / ((double) norm);
    return std::abs(dist);
}

int main() {
    Point p1(1, 1);
    Point p2(2, 6);
    //construct two points to form line
    Point p3(3,3);
    //construct point to find distance to line
    Line l1(p1, p2);
    //make line from two points
    double res = distance_line_point(l1, p3);
    std::cout << res << std::endl;
    return 0;
}

Include all headers

Since you're using std::sqrt() and std::abs() you need to #include <cmath>.

Line objects can be put in an invalid state

You seem to understand that a line requires two distinct points because you say

  the code assumes that the user specifies a line by providing two distinct points

Still, it's probably better for your code to make sure start is not the same point as finish so that you can handle the error (e.g. by throwing an exception) as soon as you encounter it. This can make it easier to debug a program using your code -- as it is, I could construct a Line with the same two points and not notice later until the distance calculation returns a nonsensical result.

To make sure start != finish, make them private and provide getter and setter member functions. The setter functions should check that start and finish are not the same point. Both the setter functions and the constructor should check for this error condition.

Similarly, because all members of Line are public it's possible to break your distance calculation. Consider a slight modification to main():

int main() {
    Point p1(1, 1);
    Point p2(2, 6);
    //construct two points to form line
    Point p3(3,3);
    //construct point to find distance to line
    Line l1(p1, p2);

    // Evil
    l1.direction_vector = Vector(p2, p2);

    //make line from two points
    double res = distance_line_point(l1, p3);
    std::cout << res << std::endl;
    return 0;
}

The result is now -nan because distance_line_point() just uses Line::direction_vector without checking its validity. Not only do you need to check that Line::direction_vector uses the correct points defined by Line::start and Line::finish, you need to check that the Vector is non-zero.

The solution would be the same as before: make Line::direction_vector private and provide getter and setter functions for it (or perhaps just a getter, and re-calculate it when start or finish is modified). The setter functions for all three members of Line would need to ensure the validity of the other two.

That said...

Line should not have the member direction_vector

Two (distinct) points are all that is required for a line. You seem to be providing Line::direction_vector just so that distance_line_point() can determine the vector between the two points that define the Line. However, you can easily calculate that vector in distance_line_point(). With Line defined as you have it, you can replace

Vector AB = l.direction_vector;

with

Vector AB(l.start, l.finish);

Now you can remove Line::distance_vector.

Operator overloading

See C++ Operator overloading on Stack Overflow for general guidelines on how to overload operators. You seem to be following those guidelines pretty well for the operators you've overloaded.

However, consider adding some additional overloads that make sense. For example, these operators would come in handy if you modified Line to make sure that its two points are not the same:

inline bool operator==(const Point& lhs, const Point& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

inline bool operator!=(const Point& lhs, const Point& rhs) {
    return !operator==(lhs, rhs);
}

Also, since you've defined * for your Vector class it would make sense to define the other operators that make sense for vectors: *=, +, +=, etc. I would be surprised to be able to multiply two Vector objects but not add them.


getTweets in JavaScript I'm a JavaScript newbie who was first introduced to JavaScript by jQuery. I'm trying to switch over some of the small things I've written in jQuery to JavaScript as a way of learning. I was wondering how I could make my code cleaner and if there were any bad habits which I am guilty of doing.

function getTweets(user) {

    //Adds a little animation to the body when function is executed
    $('.container').html('

');
    var container = document.getElementsByClassName('container')[0];
    container.innerHTML = "

";

    $.getJSON("https://twitter.com/statuses/user_timeline.json?screen_name=" + user + "&callback=?&count=50", function(data) {

        var date = {
            Sun : 'Sunday, ',
            Sat : 'Saturday, ',
            Mon : 'Monday, ',
            Tue : 'Tuesday, ',
            Wed : 'Wednesday, ',
            Fri : 'Friday, ',
            Thu : 'Thursday, ',
        };
        // Creates a box and puts JSON data into it.
        for ( var i = 0 ; i < data.length; i++) {
            // Makes the dates readable and links work.
            data[i].text = data[i].text.replace(/(http[s]*:\/\/[\w/\.]+)/, '$1')
            day = date[ data[i].created_at.match(/\w+/)[0] ];
            data[i].created_at = data[i].created_at.replace(/(\+\d+)/g, '').replace(/\w+/, day);

            var art = document.createElement('article');

            art.innerHTML = "
" + data[i].user.name + "
" + data[i].created_at + "
" + data[i].text + "
";
            container.appendChild(art);

        };
        //Everything after this is to dynamically create a Pinterest type layout
        var width = Math.floor( ( $(window).width() - 200 )/225),
            col = [],
            small = 0,
            articleArray = document.getElementsByTagName('article');

        while ( col.length < width ) {
            col.push(0)
        };

        for (var o = 0; o < articleArray.length; o++) {

            articleArray[o].style.top = col[small] + "px";
            articleArray[o].style.left = small*225 + "px";

            col[small] += articleArray[o].clientHeight + 5;

            for ( var j = 0; j < width; j++ ) {

                if (col[j] < col[small]) {
                    small = j
                }

            };
        };

        container.style.height = col[small] + 'px';
        container.style.width = col.length * 225 - 5 + 'px';

        $('.container .loading').fadeOut();
        $('article').fadeIn();

    });

};

First step to making the code look good is proper indentation. JSBeautifier can do that for you.
Next is consistency. If you use jQuery, you can go all-out with jQuery to make it as neat and uniform. Of course, you can do vanilla JS if you want to for optimization.
Then remove duplicate code or code that does the same thing over and over again.
Watch out for missed vars. This can make variables to globals which isn't good.
When declaring, follow this order:

variables
functions
"prep code" like initializers, code to fill arrays, fetching values etc.
actual operation of the function

The rest are commented so keep a sharp eye. Can't really debug the code but the idea of what to do are there:

function getTweets(user) {

    //cache an object if it's to be used more than once
    var container = $('.container').html('

'),

        //put the url up here so it does not clutter the getJSON below
        //i prefer using single quotes than double quotes for a cleaner look
        url = 'https://twitter.com/statuses/user_timeline.json?screen_name=' + user + '&callback=?&count=50';

    $.getJSON(url, function (data) {

        //it's logical to only put things where they are needed
        //in this case, the following variables are only needed
        //when the callback completes
        var date = {
            Sun: 'Sunday, ',
            Sat: 'Saturday, ',
            Mon: 'Monday, ',
            Tue: 'Tuesday, ',
            Wed: 'Wednesday, ',
            Fri: 'Friday, ',
            Thu: 'Thursday, '
        },
            width = Math.floor(($(window).width() - 200) / 225),
            col = [],
            small = 0,
            articleArray = $('article');

        //prep codes after vars
        while(col.length < width) {
            col.push(0)
        };

        //consistency and ease, use jQuery instead.
        $.each(data, function (i, value) {
            //watch out for missed "vars"
            var day = date[value.created_at.match(/\w+/)[0]],
                //shorthand notation for creating a variable, appending it to the container directly
                //we can hand it over to a reference to do more on it
                art = $('
').appendTo(container);
            value.text = value.text.replace(/(http[s]*:\/\/[\w/\.]+)/, '$1')
            value.created_at = value.created_at.replace(/(\+\d+)/g, '').replace(/\w+/, day);
            art.html('
' + value.user.name + '
' + value.created_at + '
' + value.text + '
');
        });

        container.css({
            width : col.length * 225 - 5,
            height : col[small]
        })

        //using the built in each to loop through DOM
        articleArray.each(function (i, article) {
            $(article).css({
                'top': col[small],
                'left': small * 225
            });
            col[small] += article.clientHeight + 5;
            for(var j = 0; j < width; j++) {
                if(col[j] < col[small]) {
                    small = j
                }
            }
        }).fadeIn(); //chain whenever necessary

        //using context to limit the scope of the selector search
        $('.loading', container).fadeOut();
    });
}


Simple array usage demonstration I just finished this code for my own practice purpose.  This code works just fine but I understand there still a lot insidious problems.  Any advice for improvement would be appreciated.  So here it goes:

Package DS;

import java.util.*;

public class basic_Array {

public static void main(String[] args) {

    int option;

    System.out.println("Welcome to basic array test, please choose your testing subject: ");

    Scanner user_option = new Scanner(System.in);

    do{

        System.out.println("Option 1: Simple one dimensional array.");
        System.out.println("Option 2: Simple two dimensional array. (under construction)");
        System.out.println("Option 0: Exit program");

        option = user_option.nextInt();
        System.out.println("current option is: " + option);

        switch(option){

        case 1:
            //simple array input method
            simple_a1();
            break;
        case 2:
            simple_a2();
            break;
        }

    }while(option != 0);

    System.out.println("Program terminated...");
    user_option.close();

}

private static void simple_a1() {

    int[] a1 = new int[5];

    int in_num;                                                             //redundant but clear.

    Scanner user_input = new Scanner(System.in);

    for(int i = 0; i < 5; i++){

        System.out.println("Request input for item " + i);
        in_num = user_input.nextInt();
        a1[i] = in_num;
        System.out.println("Got it, next one ");
    }

    System.out.println("The numbers in a1 are: ");

    for(int i2: a1){
        System.out.print(i2 + " ");
    }

    System.out.println("\nEnd of testing 1, back to main menu...");

}

private static void simple_a2() {

    System.out.println("This function still under construction, back to main menu...");
}

}

Edit in 2/26/2017:

Thanks for EBrown and others input, I've modified my program structure and added a few new functions.

I also have a question on multiple scanners I've put in my program. I did some search on it and many people says this is also a bad practice that may confuse the programmer in long run.  I think it cause the error when I trying to close the scanner object in simple_a1 method, so I only close the user_option scanner (located in main method).  So my question is: will it still cause resource leak?

Let's talk about SRP for the moment (I'm not going to cover anything else but this). SRP (or Single-Responsibility Principle) dictates that each and every component of code should have exactly one responsibility.

So we're going to look at all your code top-to-bottom and determine what responsibilities we have in each method.

We'll start with main:

Output information regarding programme definition to user;
Accept and process user input;
Call appropriate method(s) based on user input;

So that's more than one, but that's fine, we need to finish our analysis to make appropriate decisions on what to do next. Let's look at simple_a1:

Process items in an array;
Accept and process user input;
Add user input to array;
Print array information;
Inform the caller we're going back to the main menu;

That's a lot, and even simple_a2 has more than one responsibility:

Inform the user the feature is not implemented;
Inform the user we are returning to the main menu;

What happens when we're not going back to the main menu again from either of those methods? Now you have multiple places that you have to modify, and in a larger, production application that would mean very possible breakages.

So we're going to eliminate responsibilities until each and every method only has one left.

Let's start with simple_a1:

We can take the following block and extract it to a new method:

System.out.println("Request input for item " + i);
in_num = user_input.nextInt();
a1[i] = in_num;
System.out.println("Got it, next one ");

This does exactly one thing: prompt the user for a number and store it in the array. We won't store it in the array in our sub-method, but we'll extract the prompting out. Let's create a new method:

private static int getNumber(Scanner input, int index) {
    System.out.println("Request input for item " + index);
    int result = input.nextInt();
    System.out.print("Got it");
    return result;
}

Perfect, so this has one responsibility. It's not the prettiest, but it will do. Next we have to implement this in our other method:

for (int i = 0; i < 5; i++) {
    a1[i] = getNumber(user_input, i);

    if (i + 1 < 5) {
        System.out.println(", next one");
    }
}

So now our input prompting is separated from our processing, that's good but we can do better.

The block is now something along the lines of:

int[] a1 = new int[5];
Scanner input = new Scanner(System.in);

for (int i = 0; i < 5; i++) {
    a1[i] = getNumber(input, i);

    if (i + 1 < 5) {
        System.out.println(", next one");
    }
}

Well this whole block has one responsibility: build an array. So we can extract that out further:

private static int[] buildArray(int size) {
    int[] result = new int[5];
    Scanner input = new Scanner(System.in);

    for (int i = 0; i < 5; i++) {
        result[i] = getNumber(input, i);

        if (i + 1 < 5) {
            System.out.println(", next one");
        }
    }

    input.close();

    return result;
}

Good, so now simple_a1 looks like:

private static void simple_a1() {
    int[] a1 = buildArray(5);

    System.out.println("The numbers in a1 are: ");

    for(int i2: a1){
        System.out.print(i2 + " ");
    }

    System.out.println("\nEnd of testing 1, back to main menu...");
}

But we still have three remaining responsibilities:

Build an array;
Print the array;
Inform the user we're going back to the main menu;

Well we can make a printArray method:

private static void printArray(int[] printArray) {
    for (int val : printArray) {
        System.out.print(val + " ");
    }
}

Then we finally finish simple_a1:

private static void simple_a1() {
    int[] a1 = buildArray(5);
    printArray(a1);
    System.out.print("\nEnd of testing 1");
}

So we're down to one responsibility: process an array. It's made up of steps, but the implementation for those steps is not part of simple_a1.

Next we'll fix simple_a2:

private static void simple_a2() {
    System.out.print("This function still under construction");
}

So we don't care where we return to, we only care that we're returning.

Finally, fixing main is easy:

public static void main(String[] args) {
    System.out.println("Welcome to basic array test, please choose your testing subject: ");
    Scanner input = new Scanner(System.in);

    mainMenu(input);

    System.out.println("Program terminated...");
    input.close();
}

private static void mainMenu(Scanner input) {
    int option = 0;

    do {
        System.out.println("Option 1: Simple one dimensional array.");
        System.out.println("Option 2: Simple two dimensional array. (under construction)");
        System.out.println("Option 0: Exit program");

        option = user_option.nextInt();
        System.out.println("current option is: " + option);

        switch(option) {
            case 1:
                //simple array input method
                simple_a1();
                break;
            case 2:
                simple_a2();
                break;
            case 0:
                return;
            // In C# the `case else` is `default`, not sure what Java's is
            default:
                System.out.print("Invalid option: " + option);
                break;
        }

        System.out.println(", back to main menu");
    } while (option != 0);
}

We've got all our major components separated, and we can clearly see what each section is supposed to do.

Overall, good start, I hope to see more from you here. :)


Stopwatch app using Dojo Here is the link to fiddle. This is my first app using Dojo. Any comments/feedback is highly appreciated.

dojoConfig = {parseOnLoad: true};

resetStopwatch();

require(["dijit/form/ToggleButton", "dijit/form/Button", "dojo/dom", "dojo/dom-attr", "dojo/domReady!"], function(ToggleButton, Button, dom, domAttr){

    var timeUpdate;

    var toggleButton = new ToggleButton({
        showLabel: true,
        checked: false,
        label: "Start",
        onChange: function() {
            if (this.get('label') == "Start") {
                this.set('label', 'Stop');

                var milliseconds = seconds = minutes = hours = 0;

                timeUpdate = updateTime(domAttr, 0, 0, 0, 0);
            }
            else if (this.get('label') == "Resume") {
                this.set('label', 'Stop');
                // fetch current time in the stopwatch
                prev_milliseconds = parseInt(domAttr.get("milliseconds", "innerHTML"));
                prev_seconds      = parseInt(domAttr.get("seconds", "innerHTML"));
                prev_minutes      = parseInt(domAttr.get("minutes", "innerHTML"));
                prev_hours        = parseInt(domAttr.get("hours", "innerHTML"));
                timeUpdate = updateTime(domAttr, prev_hours, prev_minutes, prev_seconds, prev_milliseconds);

            }
            else if (this.get('label') == "Stop"){
                this.set('label', 'Resume');
                clearInterval(timeUpdate);
            }
        }
    }, "start_stop_resume");

    var resetButton = new Button({
        label: "Reset",
        onClick: function(){
            toggleButton.set('label', "Start");
            clearInterval(timeUpdate);
            resetStopwatch();
            resumeFlag = false;
        }
    }, "reset");
});

function updateTime(domAttr, prev_hours, prev_minutes, prev_seconds, prev_milliseconds){
    var startTime = new Date();
    timeUpdate = setInterval(function(){
        var timeElapsed = new Date().getTime() - startTime.getTime();

        // calculate hours
        hours = parseInt(timeElapsed/1000/60/60) + prev_hours;
        hours = prependZero(hours);
        domAttr.set("hours", "innerHTML", hours + " : ");

        // calculate minutes
        minutes = parseInt(timeElapsed/1000/60) + prev_minutes;
        if(minutes > 60)
            minutes = minutes % 60;
        minutes = prependZero(minutes);
        domAttr.set("minutes", "innerHTML", minutes + " : ");

        // calculate seconds
        seconds = parseInt(timeElapsed/1000) + prev_seconds;
        if(seconds > 60)
            seconds = seconds % 60;
        seconds = prependZero(seconds);
        domAttr.set("seconds", "innerHTML", seconds + " :: ");

        // calculate milliseconds
        milliseconds = timeElapsed + prev_milliseconds;
        milliseconds = prependZero(milliseconds);
        if(milliseconds > 1000)
            milliseconds = milliseconds % 1000;
        if(milliseconds < 10)
            milliseconds = "00" + milliseconds.toString();
        else if(milliseconds < 100)
            milliseconds = "0" + milliseconds.toString();
        domAttr.set("milliseconds", "innerHTML", milliseconds);

    },25);  // update time in stopwatch after every 25ms

    return timeUpdate;

}

function resetStopwatch(){
    require(["dojo/dom-attr"], function(domAttr){
        domAttr.set("hours",        "innerHTML", "00 : ");
        domAttr.set("minutes",      "innerHTML", "00 : ");
        domAttr.set("seconds",      "innerHTML", "00 :: ");
        domAttr.set("milliseconds", "innerHTML", "000");
    });
}

function prependZero(time){
    if(time < 10){
        time = "0" + time.toString();
        return time;
    }
    else
        return time;
}

I tinkered a bit with the fiddle, I have the following observations:

If you were to place the colons in the HTML, then you would no longer need to concatenate the colons into the time fields:

  :
  :
  ::

You could generalize prependZero so that it works for both seconds and milliseconds by passing the requested length:

  function prependZero( time, length ){
      time = time + "";
      while( time.length < length ){
      time = '0' + time;
    }
    return time;
  }

or a more Golfic version which calculates the amount of zeroes that will be required:

function prependZero2( time, length ){
    time = time + "";
    return new Array( Math.max( length - time.length + 1 , 0 ) ).join("0") + time;
}

if(minutes > 60) minutes = minutes % 60; is the same as minutes = minutes % 60; is the same as minutes %= 60;.
Your code would be much cleaner if you split out time calculations from prettyfying the numbers.

You could have a function that is dedicated to time calculations:

function updateTime(domAttr, prev_hours, prev_minutes, prev_seconds, prev_milliseconds){
  var startTime = new Date();
  timeUpdate = setInterval(function(){
    var timeElapsed = new Date().getTime() - startTime.getTime();

    // calculate hours
    hours = parseInt(timeElapsed/1000/60/60) + prev_hours;

    // calculate minutes
    minutes = parseInt(timeElapsed/1000/60) + prev_minutes;
    minutes %= 60;

    // calculate seconds
    seconds = parseInt(timeElapsed/1000) + prev_seconds;
    seconds %= 60;

    // calculate milliseconds
    milliseconds = timeElapsed + prev_milliseconds;
    milliseconds %= 1000;

    setStopwatch( hours , minutes , seconds , milliseconds );

  },25);  // update time in stopwatch after every 25ms

  return timeUpdate;
}

and a function that just updates the DOM:

function setStopwatch( hours , minutes , seconds , milliseconds ){
    require(["dojo/dom-attr"], function(domAttr){
        domAttr.set("hours"       , "innerHTML", prependZero( hours, 2 ) );
        domAttr.set("minutes"     , "innerHTML", prependZero( minutes, 2 ) );
        domAttr.set("seconds"     , "innerHTML", prependZero( seconds, 2 ) );
        domAttr.set("milliseconds", "innerHTML", prependZero( milliseconds, 3 ) );
    });
}

resetStopwatch then becomes as simple as

function resetStopwatch(){
    setStopwatch( 0, 0, 0, 0 );
}

A very minor nitpicking, but the require array is hard to read, you should figure out how Dojo proposes you should indent that array.
Another nitpicking is that you trust the DOM as your data model (you retrieve the values from the labels when you hit Resume), that is a bad practice in general, but acceptable for a timer project.

You can check the end result here.


List comprehension for reading lists of integers As of reading the following input.txt file:

1 6 14
1 2 7
1 3 9
2 3 10
2 4 15
3 6 2
3 4 11
4 5 6
5 6 9

I wanted to make a list of lists containing each line as a list of integers

[[1, 6, 14],
 [1, 2, 7],
 [1, 3, 9],
 ...
 [5, 6, 9]]

I achieved that by doing the following

with open('input.txt', 'r') as f:
    # gets lines as list of strings [['1, 2, 3,', ...]]
    nodes_list = [n.split() for n in f.readlines()]
    # convert strings inside the lists to int's [[1, 2, 3], ...]
    nodes_list = [[int(y[0]), int(y[1]), int(y[2])] for y in nodes_list]

Is there any way that I can achieve the same with a single comprehension list, without the need of having two separated ones? If not, maybe some cleaner way of doing it?

You can use a map to give you what you want in a single line:

with open('input.txt', 'r') as f:
    nodes = [list(map(int, line.split())) for line in f]

An explanation of how it works:

f.readlines() iterates over the lines, with line endings removed

line.split() gives you an iterable over the space-separated characters

map(int, ...) does the conversion to int for every element

list(...) converts it to a list to give you a list of lists


Ruby Game of Life with matrices A little while ago I wrote this implementation of Conway's Game of Life in Ruby. It's based on this Game of Life in APL video, which I think is rather elegant, though a bit dense. Feel free to give feedback on any aspect of the program, but the parts I most care about are readability and the way I work with matrices.

Unlike most implementations, the neighbor count used to determine who's alive in the next generation includes self (the cell who's neighbors we are counting). This technique is used in the APL version as well and allows us to express the rules of the game in a more concise manner than normal: i.e. a cell in the next generation is alive if its neighbor count including self is three or if it was alive in the last generation and its neighbor count including self is four.

The program currently monkey-patches Matrix, which I'm not thrilled about. I'm pretty sure Matrix#translate can be removed in favor of some sort of matrix math that would do the equivalent, but I'm not familiar enough with the subject to know how to do this well.

It would also probably be nice to blank the screen without shelling out.

The program requires Ruby 1.9 or later.

#!/usr/bin/env ruby
# encoding: utf-8

require 'matrix'

class Matrix
  def translate(row_count, col_count)
    Matrix[
      *row_vectors.map do |row|
        row.to_a.rotate(row_count)
      end.rotate(col_count)
    ]
  end
end

class Board
  attr_reader :width, :height

  def self.random(size)
    board = Matrix.build(size) { rand(10) == 0 ? 1 : 0 }
    new(board)
  end

  def self.parse(board_string)
    new(Matrix[board_string.split("\n").map { |row| row.split.map(&:to_i) }])
  end

  def initialize(board)
    @width = board.column_size
    @height = board.row_size
    @board = board
  end

  def next
    board_state = neighbor_counts.map.with_index do |count, idx|
      count == 3 || count == 4 && @board[idx / width, idx % width] == 1 ? 1 : 0
    end

    Board.new(board_state)
  end

  def to_s
    @board.row_vectors.map do |row|
      row.map do |n|
        n == 1 ? "B" : "·"
      end.to_a.join(" ")
    end.join("\n")
  end

  def neighbor_counts
    [-1,0,1].product([-1,0,1]).map do |row, col|
      @board.translate(row, col)
    end.reduce(:+)
  end
end

if __FILE__ == $0
  b = Board.random(40)
  system("clear")

  loop do
    puts b
    sleep 0.2
    system("clear")
    b = b.next
  end
end

Instead of magic numbers, extract them to either explaining variables or constants.
For example, in neighbor_counts, what are -1, 0, and 1?
People who are familiar with the GoL might know what you're trying to do, but assume you're passing this off to someone who is new to the GoL and doesn't know what these constants represent.


Find a prefix of a query string in the values of a Map I have a hash map which maps to some strings which serve as prefixes and are of small length (max length is 6):

Map<String, String> map = new HashMap<>();
map.put("codeA", "100");
map.put("codeB", "7");
map.put("codeC", "0012");
etc

This is fine so far, but I also need when provided an input string to actually break it into 2 parts if the string has a prefix that matches one of the values in my map.

What I do is:

boolean found = false;

String [] result;
for(Entry<String, String> e: map.entrySet()) {
   String code = e.getKey();
   String value = e.getValue();
   if(value.length >= inputString.length) continue;
   if(inputString.startsWith(value)) {
       result = new String[2];
       result[0] = value;
       result[1] = inputString.substring(value.length + 1);
       found = true;
       break;
     }
}
return result;

Could this be improved? Could I have been using some additional datastructure/API for this?

I am interested in an approach in Java 7 without any extra libs. The HashMap has ~400 entries and the input string 8-11 characters.

I would need a way to get the prefix having the code (hence the HashMap) and break the input string into the prefix and the rest part.

Trie

A trie would solve this problem perfectly.  With a trie, you could search all your prefixes in \$O(n)\$ time, where \$n\$ is the length of the input string.  You current implementation requires \$O(m*n)\$ time, where \$m\$ in the number of prefixes and \$n\$ is the length of the input string.

Of course, the trie solution will be much more complex than your existing solution, so you will need to weigh the performance benefits of using a trie versus the simplicity of using a HashMap.


SQL injection safety check I was wondering if my code is safe for sql injection.
This code just checks if the username exists in my db or not.

$username = $_POST['username'];
$stmt = mysqli_stmt_init($con);
$query = "SELECT username FROM users WHERE username = ?" ;
mysqli_stmt_prepare($stmt, $query);
mysqli_stmt_bind_param($stmt, "s", $username);
mysqli_stmt_execute($stmt);
mysqli_stmt_bind_result($stmt, $user['username']);
mysqli_stmt_execute($stmt);
if (mysqli_stmt_fetch($stmt)){
    if ($user['username'] === $username){
    echo $username, ' exists';
    }
}
elseif (!mysqli_stmt_fetch($stmt)){
    echo $username, ' doesn\'t exists';
}

SQL Injection-wise, this is completely safe. You don't run any risk of SQL Injection.

However, some parts of your code is not optimal:

mysqli_stmt_execute($stmt);
mysqli_stmt_bind_result($stmt, $user['username']);
mysqli_stmt_execute($stmt);

Why are you executing the statement twice?

Now, imagine that you hade your if-else switched so that you wanted to check for non-existing user first:

if (!mysqli_stmt_fetch($stmt)) {
    echo $username, ' doesn\'t exists';
}
elseif (mysqli_stmt_fetch($stmt)) {
    if ($user['username'] === $username) {
        echo $username, ' exists';
    }
}

This code would not work, and you might not be aware of why exactly. You might be just lucky that you did not code it this way from the start.

The issue is that you are calling mysqli_stmt_fetch twice. You should not do that, there can only be a maximum of one result, which means that the second if will always be false.

Your original code should look like this:

if (mysqli_stmt_fetch($stmt)) {
    if ($user['username'] === $username){
        echo $username, ' exists';
    }
}
else {
    echo $username, ' doesn\'t exists';
}

In fact though, if the first if-statement is true, then the inner if will also be true because of your SQL WHERE condition. So your code could be just this:

if (mysqli_stmt_fetch($stmt)) {
    echo $username, ' exists';
}
else {
    echo $username, ' doesn\'t exists';
}


Comparing strings with contents of columns I wrote the following lines of code to compare some strings with contents of columns (string) in SQLite database:

void PaymentTransaction::setAttributesBySqliteStmt(sqlite3_stmt * statement)
{
    ZF_LOGD("setAttributesBySqliteStmt\n");
    int columnCnt = sqlite3_column_count(statement);
    for (int i = 0; i < columnCnt; i++) {
        if (strcmp("id", sqlite3_column_name(statement, i)) == 0)
            id = sqlite3_column_int(statement, i);
        else if (strcmp("gas_station_id", sqlite3_column_name(statement, i)) == 0)
            gas_station_id = sqlite3_column_int(statement, i);
        else if (strcmp("nozzle_id", sqlite3_column_name(statement, i)) == 0)
            nozzle_id = sqlite3_column_int(statement, i);
            ................
            //SAME CODES FOR OTHER COLUMNS
            ................
            else {
        ZF_LOGW("Invalid column name(%s) in table name Transaction",
                sqlite3_column_name(statement, i));
           }
      }
  }

   void PaymentTransaction::bindValueToSqliteStmt(sqlite3_stmt* statement)
   {
int paramCnt = sqlite3_bind_parameter_count(statement);
for (int i = 1; i <= paramCnt; i++) {
    if (i == sqlite3_bind_parameter_index(statement, "@id"))
        sqlite3_bind_int(statement, i, id);
    else if (i == sqlite3_bind_parameter_index(statement, "@gas_station_id"))
        sqlite3_bind_int(statement, i, gas_station_id);
    else if (i == sqlite3_bind_parameter_index(statement, "@nozzle_id"))
        sqlite3_bind_int(statement, i, nozzle_id);
    else if ............
     //SAME CODES FOR OTHER COLUMNS
     ..................
     else {
        ZF_LOGW("Invalid param name(%s) in table name Transaction",
                sqlite3_bind_parameter_name(statement, i));
     }
  }
}

Since there are 30 columns in total, there are lots of if else statements and I was wondering whether there is better/shorter way of writing these lines of code?

The obvious approach here would be to use a map or unordered_map to convert from a column name to a pointer (or reference) to the actual column. This will typically reduce the line count by about 2:1. More importantly, however, it makes most of that simple initialization, and the code that executes at run time is about 3 lines or so. An implementation would look something like this:

struct PaymentTransaction {
    int id;
    int gas_station_id;
    int nozzle_id;
    // more members here
public:
    void setAttributes(sqlite3_statement const *);
};
void PaymentTransaction::setAttributes(sqlite3_statement const *statement) {
    for (int i = 0; i < statement->sqlite3_column_count(); i++) {
        std::string name = sqlite3_column_name(statement, i);

        static const std::map<std::string, int &> int_members{
            { "id", id},
            {"gas_station_id", gas_station_id},
            {"nozzle_id", nozzle_id}
            // ...
        };

        auto pos = int_members.find(name);
        if (pos != int_members.end()) {
            pos->second = sqlite3_column_int(statement, i);
        }
    }
    // Possibly similar code for members of other types
}

Note that this requires a separate map for each type of column (integer vs. floating point vs. string) but can have a single map for all the columns of one type.

You could separate the map from the function, and make the function a template to avoid duplicating that code (but this may be more trouble than it's worth, depending on how many types you need to deal with--all you've shown are ints, but I don't know how accurately that reflects you real use.


Jasmine test involving a sequence of actions I am writing test cases in JavaScript and jQuery, the framework is Jasmine and Karma.

describe('When a user selects a multiple-response Hotspot response', function () {

    it('Then allow highlighting multiple responses', function (done) {
        utils.clickHotspotElementAtIndex(view, 1, function() {});
        utils.clickHotspotElementAtIndex(view, 0, function() {});
        utils.clickHotspotElementAtIndex(view, 2, function() {});
        setTimeout(function() {
            expect(utils.verifyHotSpotHasBeenHiglightedAtIndex(view, 0)).toBe('true');
            expect(utils.verifyHotSpotHasBeenHiglightedAtIndex(view, 1)).toBe('true');
            expect(utils.verifyHotSpotHasBeenHiglightedAtIndex(view, 2)).toBe('true');
            done();
        }), 2000});
    });

What it does is:

click on element 1, sync action
click on element 0, sync action
click on element 2. sync action
When the main thread is free, wait for 2 seconds and then
expect element 0 has been highlighted
expect element 1 has been highlighted
expect element 2 has been highlighted

Is there a more elegant way to do this?

The anonymous functions and hardcoded values can be abstracted. For example:

function click(value){
    utils.clickHotspotElementAtIndex(view, value, Function);
}

function tests(value){
    expect(utils.verifyHotSpotHasBeenHiglightedAtIndex(view, value)).toBe('true');
}

function test () {
    [0, 1, 2].map(tests);
}

Then the asynchronous code can be modernized via async/await:

async function sequencer() {
    const clicks = [1, 0, 2].map(click);
    await Promise.all(clicks);
}

function run() {
    beforeEach(sequencer);
    it('Then allow highlighting multiple responses', test);
}

And the call can simply be a one-liner:

describe('When a user selects a multiple-response Hotspot response', run);

References

Jasmine Tutorial: Asynchronous work
JavaScript loops - how to handle async/await


Is this really what has to be done to clear the selection of an ASP.NET TreeView? I have a TreeView called myTreeView. I want to be able to write a single statement after which myTreeView.SelectedNode is null, but TreeView.SelectedNode doesn't have a setter. I've looked at the decompiled source of TreeView, and there is a SetSelectedNode method (that can accept null), but it's internal.

So I made this extension method:

public static void ClearSelection(this TreeView treeView)
{
    var currentSelection = treeView.SelectedNode;
    if (currentSelection != null)
    {
        currentSelection.Selected = false;
    }
}

and now I can just say

myTreeView.ClearSelection();

But this seems insane. Am I missing something?

There's no in-built method to do this. Your extension method looks great.

Even if TreeView did have an obscurely-named method to clear its selected node, I can only imagine it doing exactly the same as what you've written anyway.


Directed graph similarity calculation -- optimizing Mathematica code I am looking to optimize the following computation.  First, some explanations:

Explanation

I have a directed graph whose adjacency matrix may only contain 1s and 0s.  The similarity of nodes i and j is defined as follows:

count how many nodes have an edge pointing to both i and j, and count how many nodes do both i and j point to
divide the sum of these two counts by the total number of nodes either i or j is connected to

I need to find the maximum similarity of each node in graph (its similarity with any other node except itself), and compute the average of these numbers.

The graphs I'm working with are not necessarily connected, but they don't have components of size 1 (i.e. nodes that are not connected to any other nodes).

The code

meanMaxSim[g_Graph] :=
 Module[{am, pList, similarityMatrix},
  am = AdjacencyMatrix[g];
  pList = Transpose@Join[am, Transpose[am]];
  similarityMatrix = Outer[Total[#1 #2]/Total[Sign[#1 + #2]] &, pList, pList, 1];
  Mean[Max /@ dropDiagonal[similarityMatrix]]
]

(Sign is used to keep 0s and convert anything larger to 1s.)

This function just removes the elements on the diagonal of an n by n matrix, ending up with an n by n - 1 matrix:

dropDiagonal[matrix_] :=
 MapThread[Drop[#1, {#2}] &, {matrix, Range@Length[matrix]}]

Graph[] is only available in Mathematica 8, but this is irrelevant here as most of the time is spent in Outer[] anyway.  If you have an earlier version, just assume that you have the adjacency matrix as a SparseArray as starting point.

I am looking for modifications that speed this up significantly (more than 3x), but any other comment on the code is most welcome.  Hopefully a speedup is possible without a significant increase in code complexity.

Notes

Doing the computations with machine-numbers is okay, but I didn't bother doing that since it doesn't provide a significant speedup.

A note about self-loops: they are allowed in the graph, and yes, they're double-counted in this implementation.

EDIT:

I was too quick to ask this question.  Here's a ~4x speedup using Compile.  I'm still interested in comments / further speedups.

simMatCompiled =
  Compile[{{p, _Real, 2}},
    Table[Total[a b]/Total@Sign[a + b], {a, p}, {b, p}]
  ];

mxSim[g_Graph] :=
  Module[{am, pList, similarityMatrix},
    am = N@AdjacencyMatrix[g];
    pList = Transpose@Join[am, Transpose[am]];
    similarityMatrix = simMatCompiled[Normal[pList]];
    Mean[Max /@ dropDiagonal[similarityMatrix]]
  ]

I needed to change Outer to Table in order for Compile to be able to do its job.

Minor improvements, but consider using:

pList = ArrayFlatten[{{am\[Transpose], am}}];

and

dropDiagonal = MapThread[Delete, {#, Range@Length@#}] &;

I also tried dropDiagonal = MapIndexed[Drop, #] & but this is slower, at least in v7.

Replace:

Total[#1 #2]/Total[Sign[#1 + #2]] &

With:

#.#2 / Tr@Unitize[#1 + #2] &

I believe this is an improvement to your compiled function:

Compile[{{p, _Real, 2}},
  With[{b = p\[Transpose]},
    #.b / Total@Sign[# + b] & /@ p
  ]
]


Initial Mass Function for young star clusters and disk field stars I hope you can help with improving my code. I am defining a function which draws out elements of a certain mass, one by one, from a distribution constrained by the function imf(), until I have used up all the mass given to the function. The code takes a very long time between 1 minute to 45 minutes depending on the input mass. I am wondering if there is any way to make this code more effective?
In the code there are certain parameters that give trivial answers such as log10(mnorm) this was done to ensure I could in the future alter the parameters. The focus of my problem is the while loop and how it draws from the distribution given by imf(), I have identified that this part is the root course of the long performance time for the code. Any help would be greatly appreciated.

class Mod_MyFunctions:

    def __init__(self):
        pass

    def imf(self, x, imf_type):

        # Chabrier (2003) IMF for young clusters plus disk stars: lognorm and power-law tail
        mnorm = 1.0
        A1 = 0.158
        mc = 0.079
        sigma = 0.69
        A2 = 4.43e-2
        x0 = -1.3

        if imf_type == 0:
            ml = numpy.asarray((x <= log10(mnorm)).nonzero())[0]
            mh = numpy.asarray((x > log10(mnorm)).nonzero())[0]
            y = numpy.zeros(len(x))
            for i in ml: y[i] = A1 * exp(-(x[i] - log10(mc))**2/2./sigma**2)
            for i in mh: y[i] = A2 * (10.**x[i])**(x0-1)
            return y

    def mass_dist(self,
        mmin=0.01,
        mmax=100,
        Mcm=10000,
        imf_type=0,
        SFE=0.03):

        result = []
        while sum(10**(np.array(result))) < SFE*Mcm:
            x=numpy.random.uniform(log10(mmin), log10(mmax),size=1)
            y=numpy.random.uniform(0, 1, size=1)
            result.extend(x[numpy.where(y < myf.imf(x, imf_type))])

        md=numpy.array(result)
        return 10**md, len(md)

Improvise means something different then you think :)

log10(mnorm) seems to be needed to compute only once. And you can do it in your head. It is 0.

Same for log10(mc) (well not in your head this one :)).

imf_type seems useless when not zero. I am not pythonist, so, what does imf() return if imf_type is nonzero?

sigma**2 can also be computed once.

log10(mmin) and log10(mmax) can be computed once per mass_dist call.

myf.imf(x, imf_type) can be computed once per call to extend (or mass_dist, im not sure what that statement means, but I am almost sure that imf call can be moved at least one level up). This one is probably the biggest performance killer.

And there're probably more instances of this (anti)pattern.

As for the algorithm itself, I leave that to others :)


Fibonacci generating algorithm I have written an algorithm that generates a Fibonacci series to the \$Nth\$ number. The code below works fine, but as a beginner I know I must be writing pretty ugly code.

For example I think it is probably not good practice to declare and initialize the variables where I have, but I am confused about what would be the best place.

All comments and advice on code style etc. are welcome.

package algorithms;

import java.util.Scanner;

/**
* This class will generate a list of fibonacci numbers
* @author Richard
*
*/
public class FibonacciGenerator {

/**
 * This method will generate a list of fibonacci numbers
 * @param args
 */
public static void main(String[] args) {
    //declare vars and set initial values
    int number = 0, previousNumber = 0, twoNumbersAgo = 1;
    Scanner input = new Scanner(System.in);

    //prompt user for nth number
    System.out.println("Enter the n'th number for your Fibonacci series: ");

    //set loop counter equal to given nth number
    int n = input.nextInt();

    //loop through as many times as n
    for (int counter=1;counter<=n;counter++){

        //setting each new number in list equal to the sum of the previous two
        number = (previousNumber) + (twoNumbersAgo);

        //print out number
        System.out.print(number+" ");

        //change vars to be next two numbers
        twoNumbersAgo = previousNumber;
        previousNumber = number;
    }
    //close resources
    input.close();
}
}

Advice 1

One very useful principle is that each method should solve only one problem and not more. In this context, I suggest that you roll a static method that simply computes a desired Fibonacci sequence and returns it as an array/list. Then, another method can call the previous and output the numbers.

Advice 2

Instead of closing a Scanner explicitly, you could use a try with resources. Any Autocloseable can do and will be closed implicitly.

try(Scanner scanner = new Scanner(System.in)) {
    // Use scanner here.
}
// Scanner automatically closed here.

The above will close Scanner when exiting the block, or in the case of exception.

Advice 3

Fibonacci sequence grows exponentially. For that reason you might want to use BigInteger.

Summa summarum

An alternative implementation may look like this:

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class FibonacciGenerator {

    public static BigInteger[] getFibonacciSequencePrefix(int n) {
        BigInteger[] result = new BigInteger[n];

        BigInteger a = BigInteger.ONE;
        BigInteger b = BigInteger.ONE;

        for (int i = 0; i < n; ++i) {
            result[i] = a;
            BigInteger tmp = a;
            a = b;
            b = b.add(tmp);
        }

        return result;
    }

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int n = scanner.nextInt();
            System.out.println(Arrays.toString(getFibonacciSequencePrefix(n)));
        }
    }
}


Project Euler Problem 52: Permuted multiples This is my solution to Project Euler
Problem 52 - Permuted Multiples. In the problem I'm searching for the smallest value of x such that x, 2x, 3x, 4x, 5x, and 6x use the same digits.

x = 125874
while True:
    x += 1
    if sorted(set(str(x))) == sorted(set(str(x * 2))) == \
        sorted(set(str(x * 3))) == sorted(set(str(x * 4))) == \
            sorted(set(str(x * 5))) == sorted(set(str(x * 6))):
        print x
        break

Is this bad Python? Is there a better way to write this instead of using a while True loop? I've tried adding the if condition to the while loop, but keep getting an infinite loop.

Python lacks C-style techniques like side-effect assignments (while (++x) { … }) and counting for-loops (for (int x = 125874; ; x++) { … }).  When you find yourself needing a counting loop in Python, a better formulation is nearly always available using either xrange(), itertools, or a generator.  In this case, I recommend itertools.count().

There's nothing in the problem statement that implies that the answer exceeds 125874.  The only logical limit I can see is that the answer needs to have at least six digits.  (The problem is probably designed to make you think about the decimal representation of \$\frac{1}{7}\$.)

Furthermore, manually writing all of the tests for 2, 3, 4, 5, and 6 is poor style.

There is no need to transform each set into a sorted list.  Skipping that transformation nearly doubles the speed of the code.

from itertools import count

for n in count(100000):
    digits = set(str(n))
    if all(set(str(mult * n)) == digits for mult in xrange(2, 7)):
        print n
        break


Python: pass "mutable integer" in recursion I'm working on some code to find the max depth/height in a tree. I came up with a recursive solution, and I find myself needing to pass an integer "by reference". Currently, I'm using a mutable container to achieve this, but is there a more Pythonic way?

class Node:
"""
Node in a tree, with children stored in a list.
"""
   def __init__(self, keyParam, childrenParam = None):
    self.key = keyParam #some id of the node; not strictly required, but often needed.

       if childrenParam is None:
           self.children = []
       else:
           self.children = childrenParam

def dfsWithDepth(node, currentDepth, currentMaxContainer):
    currentDepth += 1
    if currentDepth > currentMaxContainer[0]:
        currentMaxContainer[0] = currentDepth

    for child in node.children:
        if child is not None:
            dfsWithDepth(child, currentDepth, currentMaxContainer)

# %% Construct tree
rootNode = Node('n1')
rootNode.children = [Node('n2'), Node('n3')]
tempNode = rootNode.children[0]  # n2
tempNode.children = [Node('n3'), Node('n4')]
tempNode = tempNode.children[1]  # n4
tempNode.children = [None, Node('n5')]

currentMaxContainer = [0]
dfsWithDepth(rootNode, 0, currentMaxContainer)

print(currentMaxContainer)

Optimization and restructuring

Node class constructor (__init__ method)

the arguments keyParam, childrenParam introduce unneeded verbosity and better named as just key and children
the whole if ... else ... condition for ensuring children list is simply replaced with self.children = children or [] expression

The initial dfsWithDepth function should be renamed to say find_max_depth to follow PEP8 style guide naming conventions.

The former parameters currentDepth, currentMaxContainer become unneeded. Within the crucial recursive function it's worth to capture "empty" node and node with no children beforehand. That's achieved by the following condition:

if node is None or not node.children:
    return 1

The remaining recursive search relies on the crucial find_max_depth and builtin max functions calls and accumulates the final max depth through traversing all subsequent sub-trees (child nodes).

The final optimized version:

class Node:
    """
    Node in a tree, with children stored in a list.
    """

    def __init__(self, key, children=None):
        self.key = key  # some id of the node; not strictly required, but often needed.
        self.children = children or []

def find_max_depth(node):
    if node is None or not node.children:
        return 1
    return 1 + max(map(find_max_depth, node.children))

Testing (I've added additional 5th level for demonstration):

# Construct tree
rootNode = Node('n1')
rootNode.children = [Node('n2'), Node('n3')]
tempNode = rootNode.children[0]  # n2
tempNode.children = [Node('n3'), Node('n4')]
tempNode = tempNode.children[1]  # n4
tempNode.children = [None, Node('n5')]
tempNode = tempNode.children[1]  # n5
tempNode.children = [Node('name7')]

print(find_max_depth(rootNode))   # 5