Getting rid of an inordinate use of the `instanceof` function I am working with a library that has a base class Base, and three class descending from it Destination, Amenity and Landmarks.
The Base class looks something like this

public class Base {
    public Integer id;
    public String externalId;

    public Base() {
    }

    public int getId() {
        return this.id;
    }

    public String getExternalId() {
        return this.externalId != null ? this.externalId : "";
    }
}

The children classes look like this

public class Destination extends Base implements Parcelable {
    private String name;
    private String description;
    private Point[] points

    public String getName() {
        return this.name;
    }

    public String getDescription() {
        return this.description;
    }

    public Point[] getPoints(){
        return this.points;
    }

}

The important thing to note here is that the three child classes have the points property and the getPoints getter for accessing it. If it was my implementation, I would bring the points field into the base class to avoid replicating multiple times in the child classes but like I said, it's a library and I cannot modify the source.
While working with the library I have ran into a situation where I have had to use the instanceof function multiple times and since this is considered a code smell, I'd like to know if there is a better way of going about it. The situation I'm describing happens when I try to get one of the child objects when a point item is specidied, the code looks like this right now

public static <T> T getCurrentMapObjectWithPoint(Point point, T [] bases){

        T base = null;
        for(T model: bases){
            Point[] points = getpointsArrayFromMapObject(model);
            for(Point currentpoint: points){
                if(currentpoint.id.equals(point.id)){
                   return base;
                }
            }
        }
        return base;
    }

    private static <T> point[] getpointsArrayFromMapObject(T base){
        if(base instanceof Amenity ){
            return ((Amenity) base).getpoints();
        } else if(base instanceof Destination){
            return ((Destination) base).getpoints();
        } else if (base instanceof LandMark){
            return ((LandMark) base).getpoints();
        }
        return new point[]{};
    }

So simply put, given a Point and list of map items(T[] base - which means and array of either Amenity, Destination or Landmark) I'm trying to figure out which Amenity, Destination or LandMark the point belongs to which means I have to go throgh the list of map items and for each item, go through the points for that item and whenever the point id is equal to the id of the point given at the start I break out of the loop and return the current map item. Is there a better way of doing this without using instanceof multiple times?

I will assume that you really, really want to use the classes defined in the library and not make your own. Presumably the library classes offer other benefits that were not otherwise relevant to the question.

One thought is that you could define an interface that offers a function with the same signature as getPoints, though with a different function name.

public interface PointListGettable {
    public Point[] getPointList();
}

(You'd probably want to come up with a better name than PointListGettable, however.)

Extend the offending classes so they implement this interface. For example:

public MyDestination extends Destination implements PointListGettable {
    public Point[] getPointList() {
        return getPoints();
    }
}

Now you can implement a function with a signature like

public PointListGettable getCurrentMapObjectWithPoint(Point point, PointListGettable [] bases)

but rather than define a function like your getpointsArrayFromMapObject, within the body of the for(PointListGettable model: bases) loop you can just write model.getPointList().

If it's just a matter of getting around one perceived defect in the inheritance scheme without using instanceof, however, I'm not sure all this is worth it.


Tracks the number of calories consumed throughout the day Tracks the number of calories a person consumes in a given meal it has helper method to get the day's total. The check method Tries to find any duplicate meals within the given list. The assumption is that a day can only contain one of each type of meal.

public class Meal {
    public enum Type {
        BREAKFAST,
        LUNCH,
        DINER,
    }

    public Type type;
    double caloriesConsumed;

    public Meal(Type type, double caloriesConsumed) {
        this.type = type;
        this.caloriesConsumed = caloriesConsumed;
    }

    //Gets calories burned
    public double getCaloriesConsumed() {
        return caloriesConsumed;
    }

    //Sets calories burned
    public void setCaloriesConsumed(double caloriesConsumed) {
        this.caloriesConsumed = caloriesConsumed;
    }

    //Get type
    public Type getType() {
        return type;
    }

    //Set type
    public void setType(Type type) {
        this.type = type;
    }

    public boolean equals(Meal meal) {
        return meal.getType() == meal.getType() && meal.getCaloriesConsumed() == getCaloriesConsumed();
    }

    public static void check(Meal... meals) throws Exception {
        /**
         * Tries to find any duplicate meals within the given list.
         * The assumption is that a day can only contain one of each type of meal.
         */
        ArrayList<Type> types = new ArrayList<Type>();
        for (int i = 0; i < meals.length; i++) {
            if (types.contains(meals[i].type))
            {
                throw new Exception();
            }
            else
            {
                types.add(meals[i].type);
            }
        }
    }

    public static double getTodaysCalories(Meal... meals) throws Exception
    {
        check(meals);

        double total = 0;
        for (Meal meal : meals) {
            total += meal.caloriesConsumed; //Add calories to total
        }
        return total;
    }

    public static void main(String[] args) {
        Meal breakfast = new Meal(Type.BREAKFAST, 500.7);
        Meal lunch = new Meal(Type.LUNCH, 378.9);
        Meal dinner = new Meal(Type.DINER, 620.1);

        try {
            double caloriesConsumed = Meal.getTodaysCalories(breakfast, lunch, dinner);
            System.out.println("Today's Total Calories is " + caloriesConsumed);
        } catch (Exception e) {
            System.out.println("Unable to calculate today's calories");
        }
    }
}

First, a small note. Your fields are public. There's no need for getters and setters if the fields are public.

Second, the getTodaysCalories() and check() methods seems a bit out of place in this class. I think it would be a lot better to have a 2nd class called DailyMeals. That class would then have a List<Meal> inside of it. That class would be the one to check if a duplicate is being added and what the daily totals are. However the checking for duplicates should be done at the time a meal is added. This would give the code more clarity and put the methods where they should be. As it stands now there isn't really any indication that a list of meals is for a single day and/or that it can't contain duplicates.

In addition, it may be some sort of rule that you can't have 2 of the same meal, but perhaps that would be better done by (instead of throwing an exception) prompting the user asking if they are sure they want to add a second lunch/dinner/breakfast etc. What happens if the person actually ate 2 meals and they consider them both lunch?

The general code structure could look something like this:

public class Meal {
    public enum Type {
        BREAKFAST,
        LUNCH,
        DINER,
    }

    private Type type;
    private double caloriesConsumed;

    public Meal(Type type, double caloriesConsumed) {
        this.type = type;
        this.caloriesConsumed = caloriesConsumed;
    }

    //ommitted getters, setters and equals for brevity...
}

public class DailyMeals {
    List<Meal> meals;

    //ommitted constructors for brevity...

    public void addMeal(Meal meal) {
        if (checkForDuplicate(meal))
            //throw error (or prompt if they're sure they want to add a duplicate)

        //rest of method code...
    }

    private boolean checkForDuplicates(Meal meal) {
        //code to check if multiple meals have the same type...
    }

    public int getCaloriesForDay() {
        //code returning total number of calories for the day
    }
}


string manipulation, which version of those 2 functions is better? I wrote my own version of endswith just like in high-level programming languages in C which I would like reviews on.

There are 2 versions. One is my own and the other is from ccan. For some reason, I feel that ccan's version is better than mine until proven wrong.

ccan/str's version:

static inline bool strends(const char *str, const char *postfix)
{
    if (strlen(str) < strlen(postfix))
        return false;

    return strcmp(str + strlen(str) - strlen(postfix), postfix) == 0;
}

My version:

bool strends(const char *str, const char *postfix)
{
    register const char *end = str + strlen(str) - 1;
    register const char *epostfix = postfix + strlen(postfix) - 1;

    while (end > str && epostfix > postfix)
        if (*end-- != *epostfix--)
            return false;
    return true;
}

Update
This is the newer version of mine:

bool strends(const char *str, const char *postfix)
{
        register const char *end = str + strlen(str) - strlen(postfix);
        if (strlen(str) < strlen(postfix))
                return false;

        while (*end)
                if (*end++ != *postfix++)
                        return false;
        return true;
}

I wonder which one is better and why (in terms of readability, performance and so on).  Please be specific and provide your research if possible.

Thanks in advance.

I like the more the first, because it works at an higher level of abstraction and it makes it clear that you are interested in comparing a part of the string with the postfix.

I'd probably introduce another variable to clearly represent that you are comparing the postfix with the latest strlen(postfix) chars of the original string.


Password generator + storage console app This is my code to generate and store password localy hashed in txt file.
I would like to kindly ask you whether you could review my code. Btw it is coded as console app. I am currently working on making GUI. Thanks in advance.

import random
import hashlib

class randomPass():
    action = ''
    def __init__(self):
        # SETUP
        self.passdic = {}

        self.num_lines = sum(1 for line in open('passwords.txt'))
        with open('passwords.txt', 'r') as rf:
            for i in range(self.num_lines):
                self.content = rf.readline()
                self.content = list(self.content.split())
                self.passdic[self.content[0]] = self.content[1]

        self.leng = 14
        self.action = ''
        self.gPass = ''
        # work as i want to
        self.myPass = ''

        print('perform one of the actions')
        while self.action != 'break':
            print('new action please')
            self.action = input()
            if self.action == 'generate':
                print('determine your generated password length, We recommend above 14 characters')
                self.leng = int(input())
                self.gPass = self.generateRandomPassWord(self.leng)
                print('generated')
            elif self.action == 'read':
                self.passRead()
            elif self.action == 'save':
                    self.savePass(self.gPass)
            else:
                print(self.action + 'is not a valid action')

    def generateRandomPassWord(self, lengthOfPassword=14):
        znaky = ['"', "'", '!', '#', '$', '%', '&', '(', ')', '*', '+', ',', '-', '.', '/', '0', '1', '2', '3',
                 '4', '5', '6', '7', '8', '9', ':', ';', '<', '=', '>', '?', '@', 'A', 'B', 'C', 'D', 'E', 'F', 'G',
                 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '[',
                 ']', '^', '_', '`', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
                 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}', '~']

        pword = ''.join([znaky[random.randint(0, len(znaky) - 1)] for i in range(lengthOfPassword)])
        return pword

    def savePass(self, generatedPassword):
        print('to save the generated pass word type your key password')
        self.myPass = hashlib.md5((input().encode('utf-8'))).hexdigest()
        if self.myPass in self.passdic:
            print('your key password already exists!')
        else:
            with open('passwords.txt', 'a') as af:

                af.write(self.myPass + ' ' + generatedPassword + '\n')

            self.passdic[self.myPass] = generatedPassword
            print('password stored')

    def passRead(self):
        print('to read the generated pass word type your key password')
        self.myPass = hashlib.md5((input().encode('utf-8'))).hexdigest()
        if self.myPass in self.passdic:
            print(self.passdic[self.myPass])
        else:
            print('we are sorry your password is non existant')

a = randomPass()
print('fin')

There is no particular need for this to be a class. While the reading of the file and the writing of the file are coupled, IMO this is not yet enough to make it into a class.

What is especially confusing is that you use members even for local variables which are not needed in the other methods.

Now, first, your reading of the file can be greatly simplified:

def read_password_file(file_name="passwords.txt"):
    with open(file_name) as f:
        return {key: password for key, password in map(str.split, f)}

This also allows using a different file than the default. It uses a dictionary comprehension and the fact that files are iterable.

The generation of the random passwords should be separate from the CLI interface (in case you want to change one without the other). The generation itself can also be simplified by using the string module:

import random
from string import ascii_lowercase, ascii_uppercase, digits, punctuation

ALLOWED_CHARS = ascii_lowercase + ascii_uppercase + digits + punctuation

def generate_random_pass_word(length=14, allowed_chars=ALLOWED_CHARS):
    return "".join(random.choices(allowed_chars, k=length))

This uses the random.choices function introduced in Python 3.6.

Your saving and retrieving from the passwords dictionary can become this:

import hashlib

def get_key(name):
    return hashlib.md5(name.encode('utf-8')).hexdigest()

def save_password(passwords, password, file_name="passwords.txt"):
    if password is None:
        print('First generate a password')
        return
    print('to save the generated pass word give it a name')
    name = get_key(input())
    if name in passwords:
        print('your key password already exists!')
    else:
        with open(file_name, 'a') as f:
            f.write(f"{name} {password}\n")
        passwords[name] = password
        print('password stored')

def read_password(passwords):
    print('to read the generated pass word type its name')
    name = get_key(input())
    if names in passwords:
        print(passwords[name])
    else:
        print('we are sorry your password is non existent')

Note that I call your self.myPass what it is, a simple name. It is not really a password (you could look it up in the file and use a rainbow table to get the cleartext) and even the context of having to think of a good password to store your good password seems ridiculous (do you use this password generation function to generate this password? What password do you use to store that password?).

I also used the new f-string (Python 3.6+) to simplify the writing to the file.

And finally, your main function, which has the user interface:

def main():
    pass, action = None, None
    passwords = read_password_file()

    print('perform one of the actions')
    while action != 'break':
        action = input('new action please\n')
        if action == 'generate':
            print('determine your generated password length, We recommend above 14 characters')
            length = int(input())
            pass = generate_random_pass_word(length)
            print('generated:', pass)
        elif action == 'read':
            read_password(passwords)
        elif action == 'save':
            save_password(passwords, pass)
        else:
            print(action + 'is not a valid action')

if __name__ == "__main__":
    main()
    print('fin')

Note that I put the calling of main under a if __name__ == "__main__": guard to allow importing from this script from another script.


Refactor deeply nested if-else I found a code on my computer that i wrote a while ago. It is based on an exercise from O'Reilly book Programming the Semantic Web. There is a class, that stores RDF triples, that is data in the form subject-predicate-object:

class SimpleGraph:
    def __init__(self):
        self._spo = {}
        self._pos = {}
        self._osp = {}

    def add(self, (s, p, o)):
        # implementation details
        pass

    def remove(self, (s, p, o)):
        # implementation details
        pass

Variables _spo, _pos, _osp are different permutations of subject, predicate, object for performance reasons, and the underlying data structure is dictionary of dictionaries of sets like {'subject': {'predicate': set([object])}} or {'object': {'subject': set([predicate])}}. The class also has a method to yield triples that match the query in a form of a tuple. If one element of a tuple is None, it acts as a wildcard.

def triples(self, (s, p, o)):
    # check which terms are present
    try:
        if s != None:
            if p != None:
                # s p o
                if o != None:
                    if o in self._spo[s][p]:
                        yield (s, p, o)
                # s p _
                else:
                    for ro in self._spo[s][p]:
                        yield (s, p, ro)
            else:
                # s _ o
                if o != None:
                    for rp in self._osp[o][s]:
                        yield (s, rp, o)
                # s _ _
                else:
                    for rp, oset in self._spo[s].items():
                        for ro in oset:
                            yield (s, rp, ro)
        else:
            if p != None:
                # _ p o
                if o != None:
                    for rs in self._pos[p][o]:
                        yield (rs, p, o)
                # _ p _
                else:
                    for ro, sset in self._pos[p].items():
                        for rs in sset:
                            yield (rs, p, ro)
            else:
                # _ _ o
                if o != None:
                    for rs, pset in self._osp[o].items():
                        for rp in pset:
                            yield (rs, rp, o)
                # _ _ _
                else:
                    for rs, pset in self._spo.items():
                        for rp, oset in pset.items():
                            for ro in oset:
                                yield (rs, rp, ro)
    except KeyError:
        pass

You see, this code is huge, and i feel it could be more terse and elegant. I suspect the possible use of dicts here, where tuple (s, p, o) is matched with a certain key in this dict, and then the yield is done. But i have no idea how to implement it.

How can i simplify this huge if-else structure?

Set args = (int(s != None), int(p != None), int(o != None)) [or args = ''.join(map(str, (int(s != None), int(p != None), int(o != None))))]

Now args will be (1, 0, 1) [or '101'] if p is None and the other two aren't.
Also, instead of using for loops you can use generator expressions to make the code more concise.

def triples(self, (s, p, o)):
    try:
        args = (int(s != None), int(p != None), int(o != None))
        if args == (1, 1, 1):
            #if o in self._spo[s][p]: #See sindikat's comment below
            #   yield (s, p, o)
            return iter([(s, p, o)] if o in self._spo[s][p] else [])
        if args == (1, 1, 0):
            return ((s, p, ro) for ro in self._spo[s][p])
        if args == (1, 0, 1):
            return ((s, rp, o) for rp in self._osp[o][s])
        if args == (1, 0, 0):
            return ((s, rp, ro) for rp, oset in self._spo[s].items() for ro in oset)
        if args == (0, 1, 1):
            return ((rs, p, o) for rs in self._pos[p][o])
        if args == (0, 1, 0):
            return ((rs, p, ro) for ro, sset in self._pos[p].items() for rs in sset)
        if args == (0, 0, 1):
            return ((rs, rp, o) for rs, pset in self._osp[o].items() for rp in pset)
        if args == (0, 0, 0):
            return ((rs, rp, ro) for rs, pset in self._spo.items() for rp, oset in pset.items() for ro in oset)
    except KeyError:
        pass

Combining this with Winston's suggestion you get the following definition

def triples(self, (s, p, o)):
    try:
        args = (int(s != None), int(p != None), int(o != None))

        if args in [(1, 1, 1), (1, 1, 0), (1, 0, 0), (0, 0, 0)]:
            lookat  = self._spo
            a1 = s; a2 = p; a3 = o;
            invperm = [0, 1, 2]
        if args in [(0, 1, 1), (0, 1, 0)]:
            lookat = self._pos
            a1 = p; a2 = o; a3 = s;
            invperm = [2, 0, 1]
        if args in [(1, 0, 1), (0, 0, 1)]:
            lookat = self._osp
            a1 = o; a2 = s; a3 = p;
            invperm = [1, 2, 0]

        permute = lambda x, p: (x[p[0]], x[p[1]], x[p[2]])

        if sum(args) == 3:
            #if a3 in lookat[a1][a2]: #See sindikat's comment below
            #   yield permute((a1, a2, a3), invperm)
            return iter([permute((a1, a2, a3), invperm)] if a3 in lookat[a1][a2] else [])
        if sum(args) == 2:
            return (permute((a1, a2, ra3), invperm) for ra3 in lookat[a1][a2])
        if sum(args) == 1:
            return (permute((a1, ra2, ra3), invperm) for ra2, a3set in lookat[a1].items() for ra3 in a3set)
        if sum(args) == 0:
            return (permute((a1, a2, a3), invperm) for ra1, a2set in lookat.items() for ra2, a3set in a2set.items() for ra3 in a3set)
    except KeyError:
        pass

Although this is slightly longer, it is easier to maintain in the sense that if you feel that the dictionary to look at should be changed (for better performance) for some combination of input, then the modification is easily accomplished with the second definition.


C++ edit distance / string similarity function based on the Jaro-Winkler algorithm I wrote a short library function, based on an example from Rosetta, to compare two strings and determine similarity, using Jaro-Winkler.

A short copy-paste ready example:

main.cpp

#include <string>
#include <iostream>

#include "jaro_winkler.hpp"

int main() {
    std::string a { "DWAYNE" };
    std::string b { "DUANE" };

    std::cout << "Similarity for '" << a
              << "' and '" << b
              << "': " << edit_distance::jaro_winkler(a, b)
              << std::endl;

    std::cout << "Similarity for 'MARTHA' and 'MARHTA': "
              << edit_distance::jaro_winkler("MARTHA", "MARHTA")
              << std::endl;
    std::cout << "Similarity for 'DIXON' and 'DICKSONX': "
              << edit_distance::jaro_winkler("DIXON", "DICKSONX")
              << std::endl;
    std::cout << "Similarity for 'JELLYFISH' and 'SMELLYFISH': "
              << edit_distance::jaro_winkler("JELLYFISH", "SMELLYFISH")
              << std::endl;
}

jaro_winkler.hpp

#pragma once

#include <cstddef>
#include <cstdint>
#include <algorithm>
#include <string_view>

namespace edit_distance {
    template <typename T = float>
    inline T jaro(const std::string_view source,
                  const std::string_view target)
    {
        const unsigned sl = source.length();
        const unsigned tl = target.length();

        if (sl == 0 || tl == 0) return 0;

        const auto match_distance = (sl == 1 && tl == 1)
                                        ? 0
                                        : (std::max(sl, tl) / 2 - 1);
        auto source_matches = new bool[sl] {0};
        auto target_matches = new bool[tl] {0};
        unsigned matches = 0;
        for (unsigned i = 0; i < sl; ++i) {
            const auto end = std::min(i + match_distance + 1, tl);
            for (auto k = i > match_distance ? (i - match_distance) : 0u; k < end; ++k)
            {
                if (!target_matches[k] && source[i] == target[k]) {
                    source_matches[i] = true;
                    target_matches[k] = true;
                    ++matches;
                    break;
                }
            }
        }
        if (matches == 0) {
            delete[] source_matches;
            delete[] target_matches;
            return 0;
        }

        T t = 0.0;
        unsigned k = 0;
        for (unsigned i = 0; i < sl; ++i) {
            if (source_matches[i]) {
                while (!target_matches[k]) ++k;
                if (source[i] != target[k]) t += 0.5;
                ++k;
            }
        }

        const T m = matches;
        delete[] source_matches;
        delete[] target_matches;
        return (m / sl + m / tl + (m - t) / m) / 3.0;
    }

    template <typename T = float>
    inline T jaro_winkler(const std::string_view source,
                          const std::string_view target,
                          const unsigned prefix = 2,
                          const T boost_treshold = 0.7,
                          const T scaling_factor = 0.1)
    {
        const auto similarity = jaro<T>(source, target);

        if (similarity > boost_treshold) {
            int common_prefix = 0;
            const int l = std::min((unsigned)std::min(source.length(), target.length()), prefix);
            for (; common_prefix < l; ++common_prefix) {
                if (source[common_prefix] != target[common_prefix]) break;
            }
            return similarity + scaling_factor * common_prefix * (1 - similarity);
        } else {
            return similarity;
        }
    }
} // namespace edit_distance

I'd be happy to hear any comments or critiques.

Here are a few things that I immediately see in this code that have room for improvement:

template <typename T = float>

Assuming you only want floating point values passed as template parameters (Since you do floating point arithmetic later on), you could add:

static_assert(std::is_floating_point<T>::value,
              "jaro can only be used with floating point types");

const unsigned sl = source.length();
const unsigned tl = target.length();

While the above may work for your code, the type for the length of the std::string_view isn't always guaranteed to be a plain unsigned int. Consider using std::size_t as the variable type, or std::string_view::size_type.

auto source_matches = new bool[sl] {0};
auto target_matches = new bool[tl] {0};

The use of auto is confusing here. It is hard to tell at first glance that you are meaning to use a dynamic array. auto doesn't shorten the type much either, so you may want to remove it.
Raw dynamic arrays are a large source of error. Consider using std::vector instead. This will also allow you to remove the deletes later on in your code.

for (unsigned i = 0; i < sl; ++i)

You could use std::size_t here. Don't make assumptions about unsigned types.

delete[] source_matches;
delete[] target_matches;

Using a std::vector would allow you to remove this.

(unsigned)std::min(source.length(), target.length())

If you have to use a cast, prefer using static_cast, as it makes your intent clearer.


Can my code be made into one? I've the following code:

    protected Dictionary<NpInfoHelper, object> Informer;
    protected override void OnInit(EventArgs e)
    {
        if (Session.Keys.Count == 1)
        {
            Session.Abandon();
            Response.RedirectPermanent("~/Pages/Login?e=true", true);
        }
        else
        {
            Informer = (Dictionary<NpInfoHelper, object>)Session["Informer"];
        }
        base.OnInit(e);
    }

in every backend .cs file of the .aspx file.

I think this is repetitive. Note that I'll be using Informer in every .aspx.cs file.

The above code is repeated 19 times. Can I make it just one?

Per the comment, what you probably want is an abstract class MyAppPage:

abstract class MyAppPage : Page {
    protected Dictionary<NpInfoHelper, object> Informer;
    protected override void OnInit(EventArgs e)
    {
        if (Session.Keys.Count == 1)
        {
            Session.Abandon();
            Response.Redirect("~/Pages/Login?e=true", true);
        }
        else
        {
            Informer = (Dictionary<NpInfoHelper, object>)Session["Informer"];
        }
        base.OnInit(e);
    }
}

then your other pages would extend MyAppPage instead of Page.

Finally, you'll notice I took the liberty of changes Response.RedirectPermanent to Response.Redirect. Permanent redirections return the 301 response "Moved Permanently" and signify that the current page no longer exists at this position and has been moved elsewhere. Using it to redirect someone who hasn't logged in might confuse crawlers.


Implement LSD radix sort in python I'm trying to implement LSD radix sort in python, but my code used 4 loop, is there any way I can do it in three or less?

Here is the 4 loops:

First loop iterate through the input list, convert it to desired radix, and change each number to a reversed list, like so:

123 --> 173 --> [3, 7, 1] #radix == 8

Second loop iterate through the newly created list, make them have the same length by adding 0, add a pointer to the corresponding element in input list, then reverse the list.Like this:

input: [1234, 56, 7]
After first loop: [[4, 3, 2, 1], [6, 5], [7]]
After the second loop: [[0, 1, 2, 3, 4], [1, 0, 0, 5, 6], [2, 0, 0, 0, 7]]

Third loop sort element in LSD order using counting sort, code is below.

Fourth loop put every thing in a new list with sorted order using the pointers.

Here's the code for radix sort:

def radix_sort(collection, radix):

    new_collect = []
    max_len = 0

    #loop through collection, convert them to desired form and put in new_collect
    for i in collection:
        num = []
        while i >= radix:
            remain = i % radix
            num.append(remain)
            i = i // radix
        num.append(i)
        new_collect.append(num)

        if len(num) > max_len:
            max_len = len(num)

    #loop through new_collect, extend the each item to same length
    for i in range(0, len(new_collect)):
        space = max_len - len(new_collect[i])
        patch = [0 for j in range(space)]
        new_collect[i].extend(patch)

        #add a pointer to the corresponding element in collection
        new_collect[i].append(i)
        new_collect[i].reverse()

    #sort by digit with counting_sort
    for i in range(-1, -1 - max_len, -1):
        new_collect = counting_sort(new_collect, radix - 1, i)

    #create a new list with same length as collection
    return_list = list(range(len(collection)))

    #put elements in collection to return_list, using the pointer in new_collect
    for i in range(0, len(collection)):
        return_list[i] = collection[new_collect[i][0]]

    return return_list

And here is the code for counting sort:

def counting_sort(collection, d_range, digit = -1):

    d_range += 1

    B = list(range(len(collection) + 1))
    C = list(range(d_range))

    for i in range(d_range):
        C[i] = 0

    for j in collection:
        #C[j] = |{key = j}|
        C[j[digit]] += 1

    for i in range(1, d_range):
        #C[i] = |{key <= i}|
        C[i] = C[i] + C[i - 1]

    for i in range(len(collection) - 1, -1, -1):
        B[C[collection[i][digit]]] = collection[i]
        C[collection[i][digit]] -= 1

    return B[1:]

Reply to Gareth Rees 's answer.

Wow, thank you for the detailed answer!

1.I guess I'm pretty bad at naming and documenting.

2.Never even tought of using |{key < k}| that's pretty neat!

3.The second argument is not the number of keys, at least I don't have the intention to make it so, it should be the range for the input, and I add 1 so that it includes 0. So I guess it's all possible value of keys.
In your improved version of the code, the value of the seq could be greater than the length of the bound, which I think will cause a out of range error.

4.About what you said in 4.1, since my radix_sort function require a radix for sorting, and I use the range of value instead of number of keys, wouldn't it be quicker to just input radix-1 or radix instead of using max()?

5.About what you said in 4.2, in my radix sort function, i need to change the raidx of input to a given value, so I need to use a loop to change it, and since I don't want the letters get involved for radixs greater than 10, I need to separate each digit, that's why I used lists. So unless I'm missing something, I don't think I can use you method in this particular scenario.

6.Do you use timeit to calculate the runtime? Or some other modules?

Thanks again for the answer!

PS: Is there anything you can say about my radix sort function's general logic? Is there anyway I can improve it?

1. Introduction

In this answer I'm just going to look at the function counting_sort. You'll see that there's plenty here for one answer.

2. Review

There's no docstring. What does this function do? What arguments does it take? What does it return?
When a function returns a result, it's conventional to name it with a noun or noun phrase describing the result. Hence the built-in function is called sorted rather than sort.
The first argument is named collection but this needs to be a sequence, so a name like seq would be better.
If the second argument were the number of keys (rather than the maximum key) then there would be no need to increment it (and similarly no need to decrement this argument in the callers).
The variables B and C could have more descriptive names, for example result and count respectively.

3. Performance

The lists B and C can be initialized more quickly using the * operator:

B = [None] * (len(collection) + 1)
C = [0] * d_range

The main loop looks like this:

for i in range(len(collection) - 1, -1, -1):
    B[C[collection[i][digit]]] = collection[i]
    C[collection[i][digit]] -= 1

But this means that collection[i] has to be looked up three times on each iteration. It is faster to iterate over the items in the collection (using reversed to do so in reverse order), avoiding the lookups:

for item in reversed(collection):
    B[C[item[digit]]] = item
    C[item[digit]] -= 1

Now, item[digit] has to be looked up twice on each iteration. It is faster to cache this in a local variable:

for item in reversed(collection):
    k = item[digit] # the key for this item
    B[C[k]] = item
    C[k] -= 1

Now, item[digit] is looked up twice for each item, once when counting the number of occurrences of each key, and once in the main loop. This can be reduced to a single lookup by creating an array of keys at the start:

keys = [item[digit] for item in collection]

and then using this when counting keys and in the main loop.
If C[k] is changed so that it has the value \$\left|\{\mathrm{key}<k\}\right|\$ rather than \$\left|\{\mathrm{key}≤k\}\right|\$, then this has three benefits: (i) the main loop can iterate over the collection in forward order, avoiding the call to reversed; (ii) the slice B[1:] at the end is avoided; (iii) the initialization of B is simplified.

Applying all these changes results in the following code:

def counting_sorted(seq, nkeys, digit=-1):
    """Return a new list containing all the items from seq in ascending
    order of item[digit], which must be a non-negative integer less
    than the parameter nkeys.

    """
    keys = [item[digit] for item in seq]

    # count[k] = |{key = k}|
    count = [0] * nkeys
    for k in keys:
        count[k] += 1

    # index[k] = |{key < k}|
    index = [0] * nkeys
    for k in range(nkeys - 1):
        index[k + 1] = index[k] + count[k]

    result = [None] * len(seq)
    for k, item in zip(keys, seq):
        result[index[k]] = item
        index[k] += 1
    return result

I find that this reduces the runtime to about 60% of the original. On my test data this is a little faster than the built-in sorted.

4. Interface improvements

There are a couple of infelicities in the interface to counting_sorted, and I think that for ease of use and understandability of the code it would be worth fixing them, even at the expense of a few percent slowdown.

The function requires us to pass in the value of nkeys. This is fragile (it would be easy to pass in the wrong value) and redundant (it can be computed from the data). So I would remove this parameter and add the line:

nkeys = max(keys) + 1

after the computation of keys.
The function looks up the sort key for each item by indexing the item with digit. But this only works for some kinds of item. Other sorting functions (like the built-in sorted) take a general key-derivation function, and I think it would be better to do so here. In your radix sort function you can make the key functions you need using operator.itemgetter

Revised code:

def counting_sorted(seq, key=None):
    """Return a new list containing all the items from seq in ascending
    order. A custom key function can be supplied to customise the sort
    order. Sort keys must be non-negative integers.

    """
    if key is None:
        keys = seq
    else:
        keys = list(map(key, seq))
    nkeys = max(keys) + 1

    # count[k] = |{key = k}|
    count = [0] * nkeys
    for k in keys:
        count[k] += 1

    # index[k] = |{key < k}|
    index = [0] * nkeys
    for k in range(nkeys - 1):
        index[k + 1] = index[k] + count[k]

    result = [None] * len(seq)
    for k, item in zip(keys, seq):
        result[index[k]] = item
        index[k] += 1
    return result

5. Answers to questions

Naming is one of the hardest things about programming. Reading other peoples' code is good practice—you'll find yourself continually thinking, "what on earth did the programmer mean by foo?" and then you can apply the same thought process to your own code.
I wanted to avoid the slice on B, and this change followed straightforwardly.
I think you're right and nkeys was a poor choice of name. What I meant by this was "number of (possible) distinct key values" but the name nkeys doesn't make that clear. (Naming is hard!)
You're right in this particular case that passing radix would be faster than calling max. But you'll see in the introduction to §4 that I gave my reasons for making these changes as "ease of use and understandability". The point is that by generalizing the function (so that it works in the general case, and not just in one specific context) it is easier to re-use, and easier for other programmers to understand and maintain.

This is a theoretical concern—after all, maybe you'll never want to re-use this code and no other programmers will ever work on it. But considered as an exercise I think it's valuable: in a professional context it's a good idea to make code as clear and easy to maintain as possible.
It's easy to change radix_sort to use the revised interface. There are two sensible approaches. (i) Transform each item into a list as before, and then pass key=itemgetter(-1) on the first iteration, key=itemgetter(-2) on the second iteration, and so on. (ii) Leave the items unchanged, and pass key=lambda x: x % radix on the first iteration, key=lambda x: (x // radix) % radix on the second iteration, and so on.
I use timeit.
As I said in the introduction, this answer is quite long enough already. Maybe someone else can have a look at radix_sort?


Unit tests for a simple function thats part of a public API Given I have to write a simple function that essentially just does a http-fetch
 to the given URL but is part of a public API that will be used by thousands.

I have two main questions about the problem:

Since this is a public API Im not sure how to handle inproper input. Should I return undefined or throw an error? (I rather throw errors to make it most obvious what types are expected). I've seen other API's however just returning undefined, which to me seems pretty stupid, as surely you dont want to be handling undefined in high level code?

function at(_url, _options) {

    if (!_options)
        throw new ReferenceError("No options provided.")

    if (typeof _options !== "[Object object]")
        throw new TypeError("No options provided.")

    if (typeof _url !== "string")
        throw new TypeError("URL must be a string.")

    ...

Is it too much to actually test if each possible inproper input is at hand?
(I find myself writing the same test code for each function I write and after a while it seemed kind "wrong" to be doing typechecking in JS. Is there a standard for typechecking inside API's in JS?)

const expect = require("chai").expect
const fetchWithOptions = require("./../index")

describe("me()", () => {
    it("should throw error if no options are provided", () => {
        expect(() => fetchWithOptions.at("some-url")).to.throw(ReferenceError)
    })

    it("should throw an error if options are not an object", () => {
        expect(() => fetchWithOptions.at("some-url", "string options")).to.throw(TypeError)
    })

    it("should throw an error if the provided url is not a string", () => {
        expect(() => fetchWithOptions.at(123123, {someOption: "someOption"})).to.throw(TypeError)
    })

})

Assuming this function is async, neither. Provide a callback parameter or return a Promise (I'd favour Promises personally). This is a more common / understood pattern in JavaScript.
Unfortunately no there isn't, it's very much part of the downsides (and beauty) of using a loosely-typed language. If you're concerned about type-safety then you should really take a look at TypeScript or equivalents.

With regards to the tests, personally I think covering each error scenario is fine - I do it myself, they're minimal effort and will help catch any regressions.


Zip / merge two linked lists together The following code interweaves two linked lists together in three flavors: iterative, recursive top-down, and recursive bottom-up. My iterative solution feels like it can be optimized better and my bottom up recursive design skills are not necessarily the best (although this solution is a much smaller task than most recursive bottom up solutions e.g. pruning a binary search tree).

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct list List;
struct list {
    int item;
    List* next;
};

//setup functions
List* generateList(int len);
void freeList(List* list);
void printList(List* list);
void showcase();
//zip functions
List* zipLists_iter(List* a, List* b);
List* zipLists_rec_top(List* a, List* b);
List* zipLists_rec_bot(List* a, List* b);
List* reverseList_rec(List* list);
List* reverseList_rec_imp(List* list, List* prev);

int main() {
    showcase();
    return EXIT_SUCCESS;
}

void showcase() {
    List* a = generateList(5);
    List* b = generateList(5);
    b = reverseList_rec(b);
    printList(a); //These are here for simplicity
    printList(b);

    puts("Testing zipLists_iter");
    a = zipLists_iter(a, b);
    printList(a);
    freeList(a);

    a = generateList(5);
    b = generateList(5);
    b = reverseList_rec(b);
    puts("Testing zipLists_rec_top");
    a = zipLists_rec_top(a, b);
    printList(a);
    freeList(a);

    a = generateList(5);
    b = generateList(5);
    b = reverseList_rec(b);
    puts("Testing zipLists_rec_bot");
    a = zipLists_rec_bot(a, b);
    printList(a);
    freeList(a);
}

void freeList(List* list) {
    while ( list ) {
        List* tmp = list;
        list = list->next;
        free(tmp);
    }
}

List* generateList(int len) {
    List* head = NULL;
    List* tail = NULL;
    int i;
    for (i = 0; i < len; i++) {
        List* node = malloc(sizeof(*node));
        node->item = i;
        node->next = NULL;
        if ( !head ) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void printList(List* list) {
    while ( list ) {
        printf("%d ", list->item);
        list = list->next;
    }
    printf("\n");
}

List* reverseList_rec(List* list) {
    return reverseList_rec_imp(list, NULL);
}

List* reverseList_rec_imp(List* list, List* prev) {
    if (!list) return NULL; //mirror NULL input

    if ( !list->next ) {
        list->next = prev;
        return list;
    } else {
        List* next = list->next;
        list->next = prev;
        return reverseList_rec_imp(next, list);
    }
}

List* zipLists_iter(List* a, List* b) {
    List* root = a;
    while ( a && b ) {
        List* oldNextA = a->next;
        List* oldNextB = b->next;
        a->next = b;
        b->next = oldNextA;
        a = oldNextA;
        b = oldNextB;
    }
    return root;
}

List* zipLists_rec_top(List* a, List* b) {
    List* oldNext = a->next;
    a->next = b;
    if ( b )
        zipLists_rec_top(b, oldNext);
    return a;
}

List* zipLists_rec_bot(List* a, List* b) {
    if ( !a ) {
        return b;
    } else if ( !b ) {
        return a;
    } else {
        a->next = zipLists_rec_bot(b, a->next);
        return a;
    }
}

The iterative approach is likely the most efficient approach. It is sparing on memory allocation, it does not require stack manipulation (and frames), and it won't cause stack overflows for long lists.

The recursive options are really not worth considering for this problem.

Your iterative implementation is not as 'tight' as I would hope, though. Consider your code:

List* zipLists_iter(List* a, List* b) {
    List* root = a;
    while ( a && b ) {
        List* oldNextA = a->next;
        List* oldNextB = b->next;
        a->next = b;
        b->next = oldNextA;
        a = oldNextA;
        b = oldNextB;
    }
    return root;
}

Your code saves away the 'second' items. It cross links the current items, and then it advances both lists.

I would prefer a solution that does one item at a time (instead of 2), and then swaps the lists so that the second list becomes the first, and vice versa.

save away item 2 from listA
make item 1 on listB the new item 2 on listA
make the saved-away item 2 (now orphaned) the swapped list B
make what was the listB item 1 the new listA.

In code, it would look like:

List* zipLists_iter(List* a, List* b) {
    if (!a) {
        return b;
    }
    List* root = a;
    while ( b ) {
        List* tmp = a->next;
        a->next = b;
        a = b;
        b = tmp;
    }
    return root;
}

Note that I put a check in there for an empty List A. This allows it to work on unevenly sized lists, including an empty list A.

By thinking about the problem a little differently you can:

remove a temporary variable.
remove two assignments
remove a null-check (a is never null)
but, you loop more often.

The remainder of your code (excluding the recursion methods which I am not going to review) is really good in terms of neatness, and functionality. It was easy to follow, and it was great that I could compile and run your code without any issues, even when using -Wall, and compiling as C99 standard.

Nicely done.


Select array element by its weight/probability I coded a function that takes an array with numbers and randomly chooses one of these numbers (Returns the index of the chosen one).
The value of each number works as an weight which determines the probability to that number be chosen.

E.G.: A possible input for the function could be [1.5, 3.5, 2.0, 1.3] and the respective probabilities would be 18.07%, 42.16%, 24.09%, 15.66%. In other words, the probability to choose a number is proportional to that number.

The function:

function chooseIndex(weights){

    let weightSum = 0;
    weights.forEach(weight => {
        weightSum += weight;
    });

    let choice = Math.random()*weightSum; // [0 ~ weightSum[
    let retIndex;
    weights.some((weight, index) => {
        choice -= weight;
        if(choice < 0){
            retIndex = index;
            return true;
        }
    });
    return retIndex;
}

I don't know why, but I feel it could be better about performance.
Any suggestions will be very welcome ;D

More concise code
First, you can compute weightSum using a reduce() function instead. I am not sure if there is any particular performance benefit to this or not, but it does allow you to put everything on one line if you like that sort of thing.
const weightSum = weights.reduce((sum, weight) => sum + weight, 0);

Similarly, in newer versions of Javascript you can use weights.findIndex() instead of weights.some() to make your code more concise. However this will not work in Internet Explorer.
    const retIndex = weights.findIndex((weight) => {
        choice -= weight;
        return (choice < 0);
    });
    return retIndex;

Now, on to efficiency.
Efficiency - using input once
If you only plan to use each input once, then the algorithm you have is close to the best fit for the job. But the time to produce an output increases linearly with the size of the input (O(n)). We can improve that. (Thanks Roland Illig.)
Say that at the top, instead of simply taking the sum, we generate a new array with all the intermediate steps to get to the sum. E.g. for the input [1.5, 3.5, 2, 1.3] we create the array [1.5, 5, 7, 8.3]. This leads us to more or less the inverse of your current method; instead of subtracting weights from one side of the less-than comparison (i.e. from choice), we are adding them to the other side.
    const accumulatedWeights = weights.slice(0, 1);
    weights.slice(1).forEach((weight, i) => {
        accumulatedWeights[i] = weight + accumulatedWeights[i - 1];
    });
    weightSum = accumulatedWeights[accumulatedWeights.length - 1];

    let choice = Math.random() * weightSum; // [0 ~ weightSum]
    let retIndex;
    accumulatedWeights.some((accumulatedWeight, index) => {
        if(choice < accumulatedWeight){
            retIndex = index;
            return true;
        }
    });
    return retIndex;

Now, this is not yet an improvement on your current method. The key is that this new array accumulatedWeights has a useful property: we know it is sorted, ordered from least to most (assuming no negative weights, which would frankly break everything anyway). This means we can do a binary search on it. Instead of using .some() to go from one end of the array to the other, we can start by checking in the middle of the array, and then "zoom in" on the half that must contain the correct value, then repeat.
Think about if there are 100 values in the input, and the random number generated corresponds to the value at index 99. Without binary search, we have to go through the whole array and do 100 operations to find the correct index; with binary search we only have to do around 7. (All 100 -> top 50 -> top 25 -> top 12 or 13 -> top 6 or 7 -> top 3 or 4 -> top 1 or 2 -> definitely top 1.) This is O(log n) time efficiency, a big improvement over O(n).
Unfortunately I don't have time to write out a full binary search function, but see this StackOverflow post.
Efficiency - using input many times
But what if you wanted to use each input more than once? E.g. you want to select ten million randomized indexes in a row based on the same weighting scheme.
Well, in that case you could follow the advice of this other StackOverflow post:

First, build a big array where each number you want to select appears some number of times in proportion to its weight. E.g. for the weights [1.5, 3.5, 2, 1.3], you would generate an array with fifteen 0s, thirty-five 1s, twenty 2s, and thirteen 3s.
Then, pick a random element from the big array (i.e. compute an index via Math.floor(Math.random() * big_array.length) and return the element at that index) ten million times in a row.

You pay a certain cost up front to set up the big array, but once you have it set up, the time to find another result is constant (O(1)), no matter how long the original input was.
Whether or not this is more efficient in practice depends entirely on your use case.


Improving MVC 4 DropDownList I'm currently populating my drop downlists like this...

  public  List<NewLogin> GetRolesForDDL()
    {
        using (database db = new database())
        {
            return (from r in db.UserRole
                    select new NewLogin
                    {
                        UserRole = r.Role,
                        RoleID = r.RoleID
                    }).ToList();
        }
    }
    public  NewLogin RoleDDL()
    {
        NewLogin nl = new NewLogin();
        using (database db = new database())
        {                               // populates ddl
            nl.RoleList = new SelectList(GetRolesForDDL(), "RoleID", "UserRole");
        }
        return nl;
    }

The part I don't like in particular is where nl.RoleList = new SelectList(GetRolesForDDL()
Is there a better way I can do this, by keeping within the same style and bypassing that method and using a quick and easy lambda expression instead?

Also another quick question is...

@Html.DropDownListFor(u => u.RoleID, Model.RoleList)
When I pass this to the controller I get the RoleID value, but my RoleName(text of ddl)
get's passed as null. Can I access both RoleName and ID without fetching it in the backend?

I know this doesn't work, but I'm thinking it would have to be something like

DDLFor(u => u.RoleID, u.RoleName)

Can I access both RoleName and ID without fetching it in the backend?

Yes, I believe so if you want to write a bit of javascript.  You would need to create a
hidden field and on every select list change event set the value of that field.

Something like

$(body).on("change", "#selectbox", function() {
    $("#inputbox").val($(this).val());
});

I'm also unsure as to why you are creating the database connection twice but I would consider
passing that into the GetRoles method like so:

public  IEnumerable<NewLogin> GetRolesForDDL(database db)
{
    return (from r in db.UserRole
            select new NewLogin
            {
                UserRole = r.Role,
                RoleID = r.RoleID
            });
}
public  NewLogin RoleDDL()
{
    using (database db = new database())
    {
        var roles = GetRolesForDDL(db).ToList();
        // populates ddl
        return new NewLogin
        {
            RoleList = new SelectList(roles, "RoleID", "UserRole");
        }
    }
}

Or even if both of these methods are part of a class consider passing the database into the class constructor and using it as a private instance variable.


Shell sort seems inefficient I am testing various sorting algorithms. Right now I am testing shell sort, insertion sort and selection sort. I ran all three algorithms on a randomly-generated list of 1000 integers. The selection sort took 41 seconds, insertion sort took 34 seconds and shell sort sort took over 3 minutes. What can I do to improve my implementation?

  public class SortAlgorithm
{
    public void InsertionSort<T>(T[] a) where T : IComparable
    {
        for (int i = 0; i < a.Length; i++)
        { // Exchange a[i] with smallest entry in a[i+1...N).
            int min = i;  // index of minimal entr.
            for (int j = i + 1; j < a.Length; j++)
            {
                if (Less(a[j], a[min]))
                {
                    min = j;
                }
                else if (a.Length < j + 1)
                {

                    a[j + 1] = a[j];
                    a[j] = a[min];
                }
            }
            Show(a);
            Exch(a, i, min);
        }
    }

    public void ShellSort<T>(T[] a) where T : IComparable
    { // Sort a[] into increasing order.
        int N = a.Length;
        int h = 1;
        while (h < N / 3)
        {
            h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ..
        }
        while (h >= 1)
        { // h-sort the array.
            for (int i = h; i < N; i++)
            { // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
                for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                    Exch(a, j, j - h);
                Show(a);
            }

            h = h / 3;
        }
    }

    public void SelectionSort<T>(T[] a) where T : IComparable
    { // Sort a[] into increasing order.
        int n = a.Length;  // array length
        for (int i = 0; i < n; i++)
        { // Exchange a[i] with smallest entry in a[i+1...N).
            int min = i;  // index of minimal entr.
            for (int j = i + 1; j < n; j++)
                if (Less(a[j], a[min])) min = j;
            Exch(a, i, min);
            Show(a);
        }
    }

    private static void Exch<T>(T[] a, int i, int j) where T : IComparable
    {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public void Show<T>(T[] a) where T : IComparable
    {            // Print the array, on a single line.
        foreach (T t in a)
        {
            Console.Write(t + " ");
        }
        Console.WriteLine();
    }

    private static bool Less(IComparable v, IComparable w)
    {
        return v.CompareTo(w) < 0;
    }

    public bool IsSorted(IComparable[] a)
    { // Test whether the array entries are in order.
        for (int i = 1; i < a.Length; i++)
            if (Less(a[i], a[i - 1])) return false;
        return true;
    }
}

Show() is probably slowing it down. It transforms your implementation into \$O(n^3)\$ and even worse increases the algorithm's time by (n*[time taken to access and write to console stream]) in the last loop. Preparing your string and printing once to the console would increase the speed, even better, printing when the list is sorted. Requesting and using resources (e.g. streams) during an expensive operation will increase execution time. You are using Console.Write <-- probably accessing the raw stream would be even faster if needs be.


Simple AngularJS controller for REST API We record software builds from our build machine into a database and for practice purposes I'm building a little web dashboard for it.

The API is REST (WebApi) and provides access to query for Products, Branches, Profiles and specific Builds.

The controller queries all products (each product contains a list of branches and profiles it has been build for) as well as all branches and profiles anything was ever built for.

It then goes on to query the last 10 builds for each of the branches and profiles a product was built for.

This is my first attempt at anything related to web-programming so I thought I'll get someone to look at it. Here is the code:

(function (angular) {
    var app = angular.module("app", ["ngResource"]);

    app.factory("Product", ["$resource", function ($resource) {
        return $resource("/api/Product");
    }]);

    app.factory("Build", ["$resource", function ($resource) {
        return $resource("/api/Build");
    }]);

    app.factory("BasicResource", ["$q", "$http", function ($q, $http) {
        var resourceFactory = {
            async: function(type) {
                var d = $q.defer();
                var result = $http.get("/api/" + type).success(function() {
                    d.resolve(result);
                });
                return d.promise;
            }
        };
        return resourceFactory;
    }]);

    app.controller("MainCtrl", ["$rootScope", "$scope", "$q", "$http", "BasicResource", "Product", "Build", function ($rootScope, $scope, $q, $http, BasicResource, Product, Build) {
        $rootScope.title = "Build Dashboard";
        $scope.Builds = [];

        $q.all([
            Product.query().$promise,
            BasicResource.async("Branch"),
            BasicResource.async("Profile")
        ]).then(function(data) {
            $scope.Products = data[0];
            $scope.Branches = data[1].data;
            $scope.Profiles = data[2].data;
        }).then(function() {

            var allBuildQueries = [];
            $scope.Products.forEach(function (prod) {
                prod.branches.forEach(function(b) {
                    prod.profiles.forEach(function(prof) {
                        allBuildQueries.push(Build.query({ product: prod.name, branch: b, profile: prof, limit: 10 }).$promise);
                    });
                });
            });

            $q.all(allBuildQueries).then(function (allBuilds) {
                allBuilds.forEach(function(builds) {
                    builds.forEach(function(build) {
                        $scope.Builds.push(build);
                    });
                });
            });
        });
    }]);

})(angular);

There are a few things which I don't really like about it so far but don't know how to improve it:

The /api/Branch and /api/Profile resources return a list of strings. This causes the issue described in the SO question. The two basic workarounds are to use $http or transform the response. I have used $http because it seemed the easiest and I have not figured out how to use transformResponse properly so far (documentation on that is somewhat light). However it results in the factories (Branch and Profile vs Product and Build) having slightly different interfaces which bugs me.
The second issue is the async query of the builds. Currently it queries Number of Branches x Number of Profiles per product for all products. At the moment this results in about 90 queries and really is no problem. However I'm wondering how this should be done properly in case the number of queries can grow into the hundreds or thousands.
The way how I combine all the build query results seems somewhat inelegant to me. In C# I'd use a LINQ query like allBuilds.SelectMany(x => x.builds).ToList(). Would strike me as weird if there wouldn't be a more elegant javascript way of doing it.
Since asking the question I have started using linqjs so that solves this issue.

You can use this unexplodeWord function:

 var explodedWords = [{"0":"h","1":"e","2":"l","3":"l","4":"o"},
                       {"0":"w","1":"o","2":"r","3":"l","4":"d"}]

 var words = explodedWords.map(unexplodeWord);

 // Converts {"0":"h","1":"e"} to "he".
 function unexplodeWord(explodedWord) {
   var chars = [];
   angular.forEach(explodedWord, function(char) {
     chars.push(char);
   });
   return chars.join('');
 }

 words.forEach(function(item) { console.log("word: " + JSON.stringify(item)); });

You would call it as such:

    $scope.Products = data[0];
    $scope.Branches = data[1].map(unexplodeWord);
    $scope.Profiles = data[2].map(unexplodeWord);

You would still have some asymmetry relative to Products, but not as much.
If I understand correctly, you want some kind of advice about pagination.  If you really get too much data, maybe you could print only the branches and profiles for one product at a time.

If you have too many branches and profiles for a single product, you should probably only output either branches or profiles, and paginate those.


PDO - configuration, database connection & and using I'm currently reading a book and watching some tutorials about PHP with MySQL (PDO), but it is not clear where to put certain things - where to put some code, should I put the connection to the database within try-catch and so on.

So, I'll explain how I started my project and if you could tell me if this is wrong or is there a better way.

In the directory includes I have config.php:

<?php
defined('DB_DNS') ? null : define("DB_DNS", "mysql:host=localhost;dbname=photo_gallery");
defined('DB_USER')   ? null : define("DB_USER", "root");
defined('DB_PASS')   ? null : define("DB_PASS", "");

In the directory includes I have database.php:

 try {
   $connection= new PDO(DB_DNS, DB_USER, DB_PASS);
   $connection->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
 } catch(Exception $e) {
    echo "Error: ".$e->getMessage();
    die();
 }

In the directory includes I have user.php with a class named User:

 <?php

 require_once(__DIR__."/../includes/config.php");
 require_once(__DIR__."/../includes/database.php");

 class User
 {
   public function findAllUsers() {
      try {
        global $connection;
        $sql = $connection->prepare("SELECT * FROM users");
        $result = $sql->execute();
        return $result;
      } catch (Exception $e) {
         echo $e->getMessage();
         die();
      }
   }
   public function find_by_id($id = 0) {
      try {
        global $connection;
        $sql = $connection->prepare("SELECT * FROM users WHERE id = :id");
        $result = $sql->execute(array($id));
        return $result->fetch(PDO::FETCH_OBJ);
     } catch (Exception $e) {
        echo $e->getMessage();
        die();
    }
  }
}

Similar to this, some authors do tutorials and courses that I watch.

Ok there are three distinct parts I'll discuss, but the most important one is the last one (the User class).

Config constants:

defined('DB_DNS') ? null : define("DB_DNS", "mysql:host=localhost;dbname=photo_gallery");
defined('DB_USER')   ? null : define("DB_USER", "root");

Things like this are sadly quite common. The problem with this setup is that things like username, password and even the default DB name (owing to it being part of the DSN) are all hard-coded in your project. The chances of these credentials being tracked by a SVC system like git are really quite high. As are the chances that the credentials may vary depending on the environment the code runs on (local/develop/testing/production). These are configuration parameters that you really shouldn't keep hard-coded in the code base

All things aside, it's also a lot shorter to write:

defined('SOME_CONSTANT') || define('SOME_CONSTANT', 'define here');

You're using a ternary to set a given value to null. Now a DSN can't be null, nor can the DB username. You should error in those cases, instead of setting the values to null.

try-catch-die

Code like this:

try {
    $connection= new PDO(DB_DNS, DB_USER, DB_PASS);
    $connection->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
} catch(Exception $e) {
    echo "Error: ".$e->getMessage();
    die();
}

is again all too common. But it's smelly for a number of reasons:

Exception's indicate something Exceptional has happened, and requires special attention by a piece of code written especially for such an event, often this is an Exception-handler. A basic handler will check some parameters to see if it can/should output details about the error, or hide them from the client, and will almost always write the full stack trace to some log, so you can diagnose the problem later on. What you're doing here is squelching that information, echo an often cryptic error message and then die. That's not handling the exception, that's giving up
PDO never throws a "regular" Exception instance, it throws PDOExceptions, your catch block should reflect this. This becomes especially useful when you're working on larger projects where a single method call can throw any number of different exceptions, and your calling it from a place where you can handle some of these exceptions, but can't handle others. In that case, you'll write something like catch (ExceptionICanHandle $e) {} and let other exceptions propagate to code that can handle it
Your DSN string is missing the ;charset=utf8 bit at the end (required to protect against injection)
You're calling setAttribute after constructing the instance. You needn't do that, the PDO constructor takes a fourth argument (array of attributes).

In short, here's what I'd write:

//parse or "obtain" config in some way
$dsn .= ';charset=utf8';//in case the charset is still missing, fix the config. I'm adding it here as a reminder
$connection = new PDO($dsn, $user, $pass, [ PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION]);

No try-catch nonsense, no die and no setAttribute. Just 1 line that does it all.

The User class

Your class suffers from a number of issues. The short list:

global is code-smell, a sign of bad design. Don't use it unless you really have to. And you really never need to use it (I've not seen a valid use case in 10 years +)
Again: try-catch-die, I've explained what is wrong with this
echo in a method is code-smell: SRP (Single Responsability Principle) is one of the core principles to follow if you want to write good code: A class should have only one job. User is a data object, it represents a DB record that represents a user of sorts. That's its job, nothing more, nothing less. Taking care of output is the job of a template/view.
Coding standards are important. Your class does not conform to the most widely adopted standard: PHP-FIG (PSR)
This is perhaps personal, but for the same reasons (SRP), I don't like data models to have find or save methods defined. That's the job of a DB mapper, or in doctrine-speak, an entity manager. Still, it's not unheard of to have data models with DB connections, so this is just a matter of opinion

In short, and assuming you're to keep the find_by_id method, here's what I'd have the User class look like:

class User
{//next line <-- PSR
    /**
     * @var PDO
     */
    protected $connection = null;

    /**
     * @var array
     */
    protected $statments = [];

    /**
     * @param PDO $connection
     */
    public function __construct(PDO $connection)
    {
        $this->connection = $connection;
    }

    /**
     * @param int $id
     */
    public function findById($id)
    {
        if (!is_numeric($id) || $id < 1) {
            throw new InvalidArgumentException('ID must be positive integer');
        }
        $method = __METHOD__;
        if (!isset($this->statements[$method])) {
            $this->statements[$method] = $this->connection->prepare('SELECT * FROM user WHERE id = :id');
        }
        $stmt = $this->statements[$method];
        $stmt->execute([':id' => $id]);
        $data = $stmt->fetch(PDO::FETCH_ASSOC);
        $stmt->closeCursor();
        if (!$data) {
            return null;
        }
        $found = new User($this->connection);//pass connection
        //load data model
        $found->setId($data['id'])
            ->setName($data['name']);
        return $found;
    }
}

The other method, I'd write in the same way, but I'll leave that for you to write. I'll have a look to previous reviews I've posted here that do roughly the same thing (query the DB, setup a data model etc...), because this review was written in a hurry, the code is not tested, and I might have left some things out

related review - links to 4 other reviews


Unit testing extension method adding view location expander Introduction

I'm writing unit tests for an extension method I wrote. Its only purpose it is to wrap startup logic which extends ViewLocationExpanders list by an instance implementating IViewLocationExpander. ViewLocationExpanders is a property of RazorViewEngineOptions, which can be configured in application startup in ConfigureServices() method. I'm using XUnit 2.4.1.

Usage

Instead of:

services.Configure<RazorViewEngineOptions>(options =>
{
    options.ViewLocationExpanders.Add(new ViewLocationExpander());
});

I can use:

services.AddViewLocationExpander(new ViewLocationExpander());

ViewLocationExpander

public class ViewLocationExpander : IViewLocationExpander
{
    public IEnumerable<string> ExpandViewLocations(
        ViewLocationExpanderContext context,
        IEnumerable<string> viewLocations)
    {
        if (context == null)
        {
            throw new ArgumentNullException(nameof(context));
        }

        if (viewLocations == null)
        {
            throw new ArgumentNullException(nameof(viewLocations));
        }

        /*
            * Note:
            * {0} = action name
            * {1} = controller name
            * {2} = area name
            */

        var newViewLocations = new string[]
        {
            // Example: '/Views/Home/_Partials/FooBar.cshtml'
            "/Views/{1}/_Partials/{0}.cshtml",
        };

        // Add new locations *AFTER* MVC default locations.
        return viewLocations.Union(newViewLocations);
    }

    public void PopulateValues(ViewLocationExpanderContext context)
    {
        context.Values["customviewlocation"] = nameof(ViewLocationExpander);
    }
}

Extension method

public static IServiceCollection AddViewLocationExpander(
    this IServiceCollection services,
    IViewLocationExpander viewLocationExpander)
{
    if (services == null)
    {
        throw new ArgumentNullException(nameof(services));
    }

    if (viewLocationExpander == null)
    {
        throw new ArgumentNullException(nameof(viewLocationExpander));
    }

    return services.Configure<RazorViewEngineOptions>(options =>
    {
        options.ViewLocationExpanders.Add(viewLocationExpander);
    });
}

Unit tests

[Fact]
public void ExtensionMethodAddsNewViewLocationExpander()
{
    // Arrange
    var services = new ServiceCollection();
    services.AddMvc();

    // These two are required to active the RazorViewEngineOptions.
    services.AddSingleton<IHostingEnvironment, HostingEnvironment>();
    services.AddSingleton<ILoggerFactory, LoggerFactory>();

    // Act
    var serviceProvider = services.BuildServiceProvider();
    var oldOptions = serviceProvider.GetRequiredService<IOptions<RazorViewEngineOptions>>().Value;
    services.AddViewLocationExpander(new ViewLocationExpander());
    serviceProvider = services.BuildServiceProvider();
    var newOptions = serviceProvider.GetRequiredService<IOptions<RazorViewEngineOptions>>().Value;

    // Assert
    Assert.True(newOptions.ViewLocationExpanders.Count > oldOptions.ViewLocationExpanders.Count);
}

Questions

Am I going beyond the scope of what unit testing should include? I'm afraid that my code is actually testing the basic functions of generic collections and/or aspects of ASP.NET Core.
If my concern above is true, that should I write unit tests to this at all? How should it work?

I find your test is excelent (and I'll borrow it from you). I would, however, make it a litte bit more exact and not only test the counts of generated locations but also whether they have the expected values.

You are not testing basic functions of collections or ASP.NET-Core aspects because it doesn't matter how it's implemented. What you are testing is whether your application has all the view locations it needs to work correctly.

This is a very important (integration) test and you should not remove it but improve it by asserting the actual locations too. If this breaks then your app wont't work anymore so it's a real lifesaver.


Minimize max distance of Gas Station I'm working on this problem, and any advice on performance improvement, bugs or code style issues are appreciated.

Problem

  Description

  There are N gas stations on a straight, M kilo-meters long highway.
  The i-th gas station is Ai kilometers away from the beginning of the
  highway. (It is guaranteed that there is one gas station at each end
  of the highway.)

  Now the mayor can build K more gas stations. He wants to minimize the
  maximum distance between two adjacent gas station. Can you help him?

  Input:

  The first line contains 3 integer N, M, k. (2 <= N <= 1000, 1 <= M, K
  <= 100000)

  The second line contains N integer, A1, A2, ... AN. (0 = A1 <= A2 <=
  ... <= AN = M)

  Output:

  The minimized maximum distance rounded to one decimal place.

  Sample Input

3 10 2
0 2 10

  Sample Output

2.7

My major ideas are:

Calculate lower and upper bound of gas station distance (lower bound 1, higher bound is current max distance between two existing gas stations)
Do a binary search for lower bound and higher bound, to see if we can fit with k gas stations

If we can fit, then try to lower higher bound of binary search
If we cannot fit, then try to higher lower bound of binary search

At the end, the number is minimal of max distance between gas stations
Since it requires one decimal place, I +/- 0.1 other than +/- 1

def max_gas_distance(distances, k):
    max_distance = 0
    for i, v in enumerate(distances):
        if i > 0:
            max_distance = max(max_distance, v - distances[i-1])
    # final result between 1 and max_distance
    l = 1.0
    h = max_distance
    while l <= h:
        mid = l + (h-l)/2.0
        if valid(distances, mid, k):
            h = mid - 0.1
        else:
            l = mid + 0.1
    return l
def valid(distances, mid, k):
    additional_gas_station = 0
    for i,v in enumerate(distances):
        if i > 0 and v - distances[i-1] > mid:
            additional_gas_station += (v - distances[i-1]) / mid
            if additional_gas_station >= k+1:
                return False
    return True

if __name__ == "__main__":
    existing_gas_stations = [0,2,10]
    k = 2.0
    print max_gas_distance(existing_gas_stations, k)

Bugs/Correctness

In the binary search, when a good value (that is when valid returns true) is found, your code doesn't save it before trying to optimize it further.

if valid(distances, mid, k):
    h = mid - 0.1 # Now the best value is lost.

The best way is to save the best distance you found so far.

if valid(distances, mid, k):
    best_so_far = mid
    h = mid - 0.1
...
return best_so_far

(v - distances[i-1]) / mid, now if the distance between the stations is 6 and mid is 3, the result will be 2, while you really only need to add 1 gas station. What you really wanna do is to get the ceiling of distance / mid which will give you the number of pieces of length mid, then subtract one to get the number of gas stations in the middle. So math.ceil(distance / mid) - 1.

Code Style

Overall I think the code is really clean, with clear variable names and good modularity.

The part that gets the max distance between every 2 elements

max_distance = 0
for i, v in enumerate(distances):
  if i > 0:
    max_distance = max(max_distance, v - distances[i-1])

Could be written in a more pythonic way as:

max_distance = max(a + b for a, b in zip(distances, distances[1:]))

The method name valid is not really readable, also the variable names mid and k are not expressive. So I would rename it to something like.

is_solvable(distances, distance_required, additional_stations)


Displaying image for the selected year I have the following code and I'm trying to find a cleaner way to run the year functions. At the moment I have 5 years as divs with an onclick event to bring the appropriate year image into view. So if you click on 1950, the 1950 year image will appear. If you then click on 1960, the 1950 image will disappear and the 1960 image will appear and so on.

In order to make sure that only the year image I want to see appears I have coded each function to remove every other years' image but this is going to lead to massive bloat as I want to be able to increase my 5 years to 20 and up.

Is there a way such as using a loop to work something like:
"If I click on 1950 then hide anything other 1950 and just show 1950"
rather than what I have now which is
"If I click on 1950, then hide 1960 image, hide 1970 image, hide 1980 image... and show 1950 image"

<!doctype html>

<meta charset="utf-8">
<base href="http://dtwdev.co.uk/new/">
<title>Year test</title>

1950

1960

1970

1980

1990

Create a style for the classes hidden_year and visible_year. When you click a link use a selector that selects all with id containing "year_19" and set them all to hidden_year, then just set the link you clicked to visible_year.

You could use a loop to build up the id values 5-9 if you really wanted to. . . var curr_year = 'year_19' + i + '0' in a loop.

Here is an example:

<!doctype html>

<meta charset="utf-8">
<title>Year test</title>

1950

1960

1970

1980

1990


Recover flights from found tickets I just found a whole bunch of plane tickets that only have a start and destination on them. I also know the route started in a certain city. I would like to recover the (alphabetically) first possible route a person took using these tickets. I added some examples in the doctests.

from collections import OrderedDict, defaultdict

class OrderedDefaultDict(OrderedDict):
    def __missing__(self, key):
        self[key] = value = 0
        return value

class FlightStorage():
    amount = 0

    def __init__(self):
        self.storage = defaultdict(OrderedDefaultDict)

    def add(self, start, destination):
        self.storage[start][destination] += 1
        self.amount += 1

    def list(self, start):
        return (destination for destination, amount in self.storage[start].items() if amount > 0)

    def remove(self, start, destination):
        self.storage[start][destination] -= 1
        self.amount -= 1

    def __len__(self):
        return self.amount

def reassemble_flights(start, flights):
    '''Reassembles a series of flights.

    >>> reassemble_flights('YUL', [('YUL', 'SFO'), ('SFO', 'HKO')])
    ['YUL', 'SFO', 'HKO']
    >>> reassemble_flights('YUL', [('SFO', 'HKO'), ('YYZ', 'SFO'), ('YUL', 'YYZ'), ('HKO', 'ORD')])
    ['YUL', 'YYZ', 'SFO', 'HKO', 'ORD']

    Returns the first (alphabetically sorted) route:
    >>> reassemble_flights('A', [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')])
    ['A', 'B', 'C', 'A', 'C']

    If no solution is available, returns None:
    >>> reassemble_flights('COM', [('SFO', 'COM'), ('COM', 'YYZ')]) is None
    True
    '''
    storage = FlightStorage()
    for flight in sorted(flights):
        storage.add(*flight)
    return backtrack_flights(start, storage)

def backtrack_flights(start, storage):
    if len(storage) == 0:
        return [start]
    if not any(storage.list(start)):
        return
    for destination in storage.list(start):
        storage.remove(start, destination)
        result = backtrack_flights(destination, storage)
        if result is not None:
            return [start] + result
        storage.add(start, destination)

1. Review

The problem of putting the tickets in order is the same as that of constructing an Eulerian path on the directed graph whose edges correspond to the tickets. (An Eulerian path is a path in a graph that follows every edge exactly once.)

Since this is really a graph problem, it would make things clearer if the code used graph terminology rather than flight terminology. Thus: FlightStorage → Graph, start → vertex (or node), destination → neighbour, list → neighbours, flights → edges and so on.

The reason for using graph terminology (rather than flight ticket terminology) is that there is a body of computer science literature about graphs, and translating your problem into graph terminology helps you to see how your problem relates to this body of literature, and helps you discover and implement the best data structures and algorithms for your problem.
The classes OrderedDefaultDict and FlightStorage lack docstrings.
The list method returns an iterator (not a list) over the neighbours of a vertex. This means that in this code:

for destination in storage.list(start):
    storage.remove(start, destination)
    # ...

the loop is modifying the dictionary storage.storage at the same time as it is iterating over it. This is not guaranteed to work in Python (though it might happen to do so in some cases). For reliability you need to avoid this.
In the remove method there ought to be a check that self.storage[start][destination] is greater than zero, before decrementing it. This would catch attempts to remove non-existent edges from the graph.
The test not any(storage.list(start)) only works if the vertices of the graph are represented by objects that test as true. This prevents us from (say) representing vertices as integers starting at zero (because vertex zero will test as false).
In any case there is no need for the special case if not any(storage.list(start)) because that is already handled correctly — if start has no neighbours then there will be no iterations of the for loop.
Returning None when the graph has no Eulerian path is risky. It would be easy for caller to forget to check. It is better to raise an exception in an exceptional case like this.
When constructing the graph, it would be faster to sort the neighbours of each vertex, rather than sorting all the edges in one big list.
The examples can be written more tersely. Instead of:

[('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')]

write:

'AB AC BC CA'.split()

2. Algorithm

The problem of constructing an Eulerian path can be solved using Hierholzer's algorithm. This algorithm works by following edges until a dead end is reached. For example, if we are given this graph:

Then following edges starting at A reaches a dead end at F:

This initial step may leave some vertices which still have unused edges. We pick one of the vertices (for example, vertex E) and follow unused edges again until we reach a dead end. Necessarily this dead end must be where we started (otherwise there is no Eulerian path), and so we get a loop:

Continue to find loops until there are no more unused edges. In this example, if we pick vertex D then we get one more loop:

Now all the edges have been used, so we stitch together the result, by inserting each of the loops into the path we found at the first step, getting the Eulerian path:

In order to ensure that this procedure yields the lexicographically first path, we need to take some care about the order we choose edges and vertices. In particular, when following edges, we should choose the unused edge to the lexicographically earliest neighbour, and when choosing a vertex with unused edges, we should choose the last such vertex along the path constructed so far.

3. Implementation

This uses a linked list to maintain the path, so that we can efficiently insert new vertices into the middle of the path as we go along. The graph itself is represented as a defaultdict(list) mapping each vertex to a list of its neighbours. The neighbours for each vertex are sorted into reverse order, so that when we pop the list we get the lexicographically smallest neighbour.

from collections import defaultdict

class Link:
    "A link in a linked list."
    def __init__(self, vertex):
        self.vertex = vertex
        self.next = None

    def insert(self, link):
        "Insert link after self in the linked list and return link."
        link.next = self.next
        self.next = link
        return link

    def __repr__(self):
        return '{0.vertex!r}->{0.next!r}'.format(self)

def eulerian_path(start, edges):
    """Given an iterable of edges in a graph, return a list of the
    vertices in the lexicographically first Eulerian path in the graph
    starting at the start vertex. Edges must be represented as an
    iterables of two vertices, and a vertex may be any hashable
    object.

        >>> ''.join(eulerian_path('A', 'BC AB CD'.split()))
        'ABCD'

        >>> ''.join(eulerian_path('A', 'AB BC CA AC'.split()))
        'ABCAC'

    If the graph has no Eulerian path, raise ValueError.

        >>> ''.join(eulerian_path('A', 'AB CD'.split()))
        Traceback (most recent call last):
        ...
        ValueError: No Eulerian path

        >>> ''.join(eulerian_path('B', 'AB BC CA AC'.split()))
        Traceback (most recent call last):
        ...
        ValueError: No Eulerian path

    """
    # Build directed graph.
    graph = defaultdict(list)
    for v, w in edges:
        graph[v].append(w)

    # Sort neighbours of each vertex in reverse order.
    for neighbours in graph.values():
        neighbours.sort(reverse=True)

    start = Link(start)    # First vertex on the Eulerian path.
    unvisited = [start]    # Stack of vertices that might have unvisited edges.
    while unvisited:
        cur = loop = unvisited.pop()
        # Follow edges until a dead end is reached.
        neighbours = graph[cur.vertex]
        while neighbours:
            if len(neighbours) > 1:
                unvisited.append(cur)
            cur = cur.insert(Link(neighbours.pop()))
            neighbours = graph[cur.vertex]
        # Each dead end (except possibly the first) must complete a loop.
        if cur.vertex != loop.vertex and cur.next is not None:
            raise ValueError("No Eulerian path")

    # All edges must be traversed.
    if any(graph.values()):
        raise ValueError("No Eulerian path")

    # Reconstruct path from linked list.
    path = []
    while start is not None:
        path.append(start.vertex)
        start = start.next
    return path

4. Performance

Hierholzer's algorithm requires no backtracking, and solves the problem in time that's linear in the size of the graph. Whereas the code in the post potentially follows all simple paths in the graph, and in the worst cases takes time that's exponential in the size of the graph.

Here's one way to generate some test graphs that demonstrate the problem.

from itertools import product

def test_graph(n):
    "Generate edges in a test graph with n vertices."
    yield from product(range(2, n), repeat=2)
    yield 1, 2
    yield 1, n
    yield n, 1

The code in the post takes nearly 3 seconds to find an Eulerian path in the test graph with six vertices:

>>> from timeit import timeit
>>> timeit(lambda:reassemble_flights(1, test_graph(6)), number=1)
2.905132247833535

By comparison, eulerian_path is 30,000 times faster on the same graph:

>>> timeit(lambda:eulerian_path(1, test_graph(6)), number=1)
9.236903861165047e-05

(See this answer for an explanation of why following all simple paths in a graph leads to exponential runtime.)


Difference between API time and server time I'm using the openweathermap API to get weather forecast data. I want to make sure that the forecast values are at minimum 2 hours in the future. The API is providing the forecast in 3 hour steps, so I need to make sure that the weather data are in the future.

Here is an example response provided by openweathermap API:

{"city":{"id":1851632,"name":"Shuzenji",
"coord":{"lon":138.933334,"lat":34.966671},
"country":"JP",
"cod":"200",
"message":0.0045,
"cnt":38,
"list":[{
        "dt":1406106000,
        "main":{
            "temp":298.77,
            "temp_min":298.77,
            "temp_max":298.774,
            "pressure":1005.93,
            "sea_level":1018.18,
            "grnd_level":1005.93,
            "humidity":87
            "temp_kf":0.26},
        "weather":[{"id":804,"main":"Clouds","description":"overcast clouds","icon":"04d"}],
        "clouds":{"all":88},
        "wind":{"speed":5.71,"deg":229.501},
        "sys":{"pod":"d"},
        "dt_txt":"2014-07-23 09:00:00"}
        ]}

I'm using JSON. The list property has the value dt_txt in this format: year-month-day 09:00:00. Now I need to check if this DateTime is minimum 2 hours in the future and if not I simply take the item at index 1 of the list.

I wrote following code:

 // look for next prediction
var weatherList = parsed.list;

// Check which time is relevant
// Get only time without description or/and date
// 2017-03-17 21:00:00
// ~~~~~~~~~~~~~^
var columnIndex = weatherList[0]["dt_txt"].indexOf(":") - 2;
// 2017-03-17 21:00:00
// ~~~~~~~~~~~^
var apiHoursString  = weatherList[0]["dt_txt"].substring(columnIndex, columnIndex + 2);

// server time:
var hours = String((new Date()).getHours());
if(hours.length < 2){
    hours = "0" + hours;
}

var apiHoursInt = parseInt(apiHoursString);
var hoursInt = parseInt(hours);

if((apiHoursInt - hoursInt) < 2){
    indexToUse = 1
}

I know this code is bad - what is the proper way to do that on Node.js?

I would not parse the dt_txt field. You would have to make too many assumptions including the format of the date (Is it yyyy-mm-dd or the American mm-dd-yyyy) and the time zone. Instead create a date object from the dt field:

var apiHours = (new Date(weatherList[0].dt * 1000)).getHours();

All those operations to add 0 and do hours to string to integer conversions are redundant. The following should be sufficient:

let weatherList  = parsed.list;
let apiHours     = (new Date(weatherList[0].dt * 1000).getHours();
let serverHours  = (new Date()).getHours();
let indexToUse   = (apiHours - serverHours < 2) ? 1 : 0;

Update 1

David is right, I had missed that point. A better solution would be:

// All values in milliseconds
const oneHour   = 60 * 60 * 1000;
let  apiTime    = weatherList[0].dt * 1000;
let  serverTime = (new Date()).valueOf();
let  indexToUse = (apiTime - serverTime < 2 * oneHour) ? 1 : 0;


Reusing StringBuilder or creating a new one? Given that it is better to reuse objects than create new ones when developing with Android, is it worth while deleting the contents of a StringBuilder and reusing it?

StringBuilder b = new StringBuilder();
//build up a string
b.delete(0, b.length());
//reuse it

Compared to:

StringBuilder b1 = new StringBuilder();
//build up a string
StringBuilder b2 = new StringBuilder();
//create a new one

Reusing doesn't need memory allocation, so it could be faster as @Mike Nakis mentioned. On the other hand it leads to ugly code: you use the same variable for two (or more) different purposes which could confuse readers, make maintenance harder. Unless you have a good reason to do that avoid it. I mean, you have a good reason if a profiling shows that creating new StringBuilder instances is a bottleneck in the application.

If you really have to reuse StringBuilders, try accessing them with different names with a helper method:

public static StringBuilder reuseForBetterPerformance(final StringBuilder sb) {
    sb.delete(0, sb.length());
    return sb;
}

Client code:

final StringBuilder b = new StringBuilder();
//build up a string
final StringBuilder c = reuseForBetterPerformance(b);
//reuse it
c.append(...)

It makes the code a little bit more readable, since the method name says why you're reusing the StringBuilder.


Script for starting a rails app, with some peculiarities I wanted to write a script, which starts a rails app, and opens it in the browser.
I'm trying to implement this in a peculiar way though - I expect two things:

the script must wait until the server is started, then open the browser within a short time
when I stop the script (Ctrl+C), the server process must stop.

The script I've written actually works, but I was wondering if there is a simplerr/more standard/more correct way of writing it.

The script is written for linux, but it's not meant to be platform specific - or more precisely, anything except Windows.

PROJECT_DIR          = '/path/to/app'
POLLING_TIME         = 0.1
SERVER_STARTED_REGEX = /WEBrick::HTTPServer#start/
BROWSER_COMMAND      = 'browser http://localhost:3000 &'

Dir.chdir( PROJECT_DIR )

thread = Thread.new do
  IO.popen( 'script/rails server 2>&1' ) do | io |
    Thread.current[ :last_server_line ] = io.gets while true
  end
end

sleep POLLING_TIME while thread[ :last_server_line ] !~ SERVER_STARTED_REGEX

`#{ BROWSER_COMMAND }`

thread.join

This was an interesting one. Thank you :)

I dug around in the rails code and poked at webrick and rack for a while and this is what I came up with:

PROJECT_DIR     = ENV['PROJECT_DIR']     || '/path/to/app'
BROWSER_COMMAND = ENV['BROWSER_COMMAND'] || 'browser http://localhost:3000 &'
PORT            = ENV['PORT'].to_i       || 3000

require "#{PROJECT_DIR}/config/environment.rb"

thread = Thread.new do
  Rack::Handler::WEBrick.run Rails.application, Port: PORT
end

`#{ BROWSER_COMMAND }`

Rack::Handler::WEBrick.shutdown

thread.join

This approach is actually borrowed from rack's webrick handler.

I load the environment prior to actually starting the webrick server making any waits unnecessary for me. If that should be necessary for you, I'm sure you could add it.

Then I pretty much stuck to what you did, putting the actual server into a thread. The Handler already provides that neat shutdown method.

Oh, I also took the liberty of adding some ENV variables so you can put this script into a file and run it from where ever you want.

EDIT: In the comments Marcus pointed out, that in order to resolve the timing issue, one can set the closure (block variable) from WEBrick.run {|server|} to a thread-local variable that can be polled afterwards.

There might also be ways to exploit Celluloid for messaging between the different threads.


Rendering plain text with paragraphs and line breaks as HTML I have text inside a variable that I need to separate in paragraphs, and at the same time respect the manual breaklines.

This is my code:

    {description.split('\n\n').map(paragraph => (

            {paragraph.split('\n').map(
                (line, index) =>
                    index > 0 ? (

                            {line}

                    ) : (
                        line
                    )
            )}

    ))}

I am not specially happy with the code. It is not very readable. Any ideas how to improve it?

Two things that help in cases like this (IMHO):

Extract a function for more complex logic or a Array.map callback (e.g. to give a descriptive name and/or avoid nesting)
Provide descriptive names for non-obvious stuff (e.g. I'd prefer firstLine and remainingLines (or something similar) over using index)

I'd probably do something like this:

description.split('\n\n').map(renderParagraph)

// If you are in a class, this could be a method on the class
function renderParagraph(paragraph) {
  // With fancy ES6:
  const [firstLine, ...rest] = paragraph.split('\n')
  // Or ES5:
  const lines = paragraph.split('\n')
  const firstLine = lines[0]
  const rest = lines.slice(1)

  return (

      {firstLine}
      {rest.map(line => (
        // React.Fragment doesn’t create a wrapper element in the DOM.
        // If you don’t care about that, you can use div instead
        <React.Fragment>

          {line}
        </React.Fragment>
      )}

  )
}