Newton's method to solve cubic equations I have used the Newton-Raphson method to solve Cubic equations of the form $$ax^3+bx^2+cx+d=0$$ by first iteratively finding one solution, and then reducing the polynomial to a quadratic $$a1*x^2+b1*x+c=0$$ and solving for it using the quadratic formula. It also gives the imaginary roots.

def deg3(a,b,c,d,g):  #using newton raphson method, I designed this to solve degree3 equations
    y=a*g**3+b*g**2+c*g+d
    return y
def solvedeg3equation():
    '''solves for cubic equations of the form ax^3+bx^2+cx+d=0 with the rough estimate of error within e'''
    import math
    e=float(input("e= "))
    a=float(input("a= "))
    b=float(input("b= "))
    c=float(input("c= "))
    d=float(input("d= "))
    count=1
    g=0.01
    while abs(deg3(a,b,c,d,g))>e and count<=100 and not d==0:
        count=count+1
        if 3*a*g**2+2*b*g+c==0:
            g=g+0.001
        g=g-deg3(a,b,c,d,g)/(3*a*g**2+2*b*g+c)

   if count<=100:
        if d==0:
            a1=a
            b1=b
            c1=c
            g=0
        else:
            c1=-d/g                                 #This is generation 3, which provides all three solutions, including imaginary solutions, if any.
            a1=a
            b1=(c1-c)/g                             #imagg=imaginary part of root, realg=real part
        if b1**2-4*a1*c1<0:
            realg=-b1/(2*a1)
            imagg=math.sqrt(4*a1*c1-(b1**2))/(2*a1)
            if a1>0:
                g2=str(realg)+'+'+str(imagg)+'i'
                g3=str(realg)+'-'+str(imagg)+'i'
            if a1<0:
                g2=str(realg)+'+'+str(-imagg)+'i'
                g3=str(realg)+'-'+str(-imagg)+'i'
        if abs(b1**2-4*a1*c1)<e:
            g2=-b1/(2*a1)
            g3=None
        if b1**2-4*a1*c1>e:
            g2=(-b1+math.sqrt(b1**2-4*a1*c1))/2*a1
            g3=(-b1-math.sqrt(b1**2-4*a1*c1))/2*a1
        print("Solved. The best guess is:",g,'and',g2,'and',g3)
        print("Iterations required: ",count)
    else:
        print("Maximum iterations exceeded ")
        print("Iterations: ",count,"Current guess: ",g)

I would like to know how I can make this code more efficient, both mathematically and structurally. Some places which could do with a more efficient piece of code, according to me, are:

To avoid crashing of the program when the derivative equals zero, I have used the provision of g+0.001, to avoid the case. Is there a better way to solve this problem? Both mathematical optimizations or structural (code-related) are welcome.
Reducing the number of conditional statements and elementary operations (like comparisons, assignments and arithmetic operations) to reduce the computation time
Improve the Newton-Raphson algorithm mathematically to reduce the number of iterations required (since 3-4 digit numbers require more than 100 iterations currently). I'm incorporating the provision of better guesses.

I am a beginner to Python (this is my second program) and programming in general, so please try to suggest as simple modifications as possible. Also, I would appreciate any tips on the general nature of my writing style.

Handling of complex roots

When there are complex roots, you have two cases, for a1 > 0 and a1 < 0.  You could just collapse the two cases by using abs(a1) when defining imagg.

Better yet, Python has built-in support for a complex type.  Why not use it instead of building a string?  Then you don't even have to worry about the sign of the imaginary part for the sake of a pretty printout.

Separation of concerns

Your solvedeg3equation() function performs input, calculation, and output.  That may do the job for you, but it ensures that your code will never be reusable, other than by copying and pasting — or by piping the input to you and attempting to parse the output!  Furthermore, it makes your code just as difficult to unit test.  What you want is a function that accepts a polynomial (more on that shortly) and returns a 3-tuple of solutions.  The caller would be responsible for input and output.

Notation

Representing a third-degree polynomial as variables a, b, c, and d is unwieldy.  You can't pass it around easily as one entity.  The proliferation of variables imposes a mental load.  Most importantly, I think that it leads to poor notation in your code.

I propose the following notation:

x0, x1, x2: The first, second, and third roots (better than g, g2, g3)
Polynomial(a, b, c, d): An object representing the polynomial a x3 + b x2 + c x + d
f: The polynomial to be solved (better than a, b, c, d)
df_dx: The derivative of f (better than 3*a*g**2+2*b*g+c)
q: The quadratic polynomial remaining after x0 has been found (better than c1=-d/g; a1=a; b1=(c1-c)/g)
q.discriminant(): Shorthand for b1**2-4*a1*c1
tolerance: better than e (which unfortunately looks like it's related to a, b, c, d)

Furthermore, you shouldn't hard-code a 100-iteration limit, especially twice as a magic number in the code.

Polynomial class

As noted above, having a class for polynomials is extremely useful for your problem.  In addition to the polynomial to be solved, you need its derivative, and you also have a quadratic equation to solve.  A polynomial class lets you

pass the polynomial into the solver function conveniently
collapse several variables into one
evaluate the value of the polynomial easily
take its derivative

Here is an implementation:

class Polynomial(object):
    def __init__(self, *coeffs):
        """
        Polynomial(3, 5, 0, -2) represents f(x) = 3x^3 + 5x^2 - 2.
        """
        self.coeffs = list(coeffs)[::-1]
        while self.coeffs[-1] == 0:
            self.coeffs.pop()

    def __call__(self, x):
        """
        >>> f = Polynomial(3, 5, 0, -2)
        >>> f(2)
        42
        """
        return sum([self[n] * x ** n for n in range(len(self.coeffs))])

    def __getitem__(self, n):
        """
        Gets the coefficient for x^n
        >>> f = Polynomial(3, 5, 0, -2)
        >>> f[2]
        5
        """
        return self.coeffs[n] if n < len(self.coeffs) else 0

    def __str__(self):
        """
        >>> f = Polynomial(3, 5, 0, -2)
        >>> str(f)
        3 x^3 + 5 x^2 + 0 x^1 + -2
        """
        return ' + '.join(["%d x^%d" % (self[n], n) for n in range(len(self.coeffs))][::-1])

    def degree(self):
        """
        >>> f = Polynomial(3, 5, 0, -2)
        >>> f.degree()
        3
        """
        return len(self.coeffs) - 1

    def derivative(self):
        """
        >>> f = Polynomial(3, 5, 0, -2)
        >>> f.derivative()
        9 x^2 + 5 x^1 + 0 x^0
        """
        deriv = [n * self[n] for n in range(len(self.coeffs) - 1, 0, -1)]
        return Polynomial(*deriv)

    def discriminant(self):
        """
        For quadratic polynomial a x^2 + b x + c, returns b^2 - 4 * a * c

        >>> f = Polynomial(4, -1, 2)
        >>> f.discriminant()
        -31
        """
        if self.degree() != 2:
            raise ValueError, "Discriminant of polynomial of degree %d not supported" % (self.degree())
        return self[1] ** 2 - 4 * self[2] * self[0]

Error handling

If something goes wrong, don't just print something.  Raise an exception, which ensures that the caller will notice the problem!

class SolutionNotFound(ValueError):
    """
    Raised when a root of a polynomial cannot be found.
    """

Iteration limit

Python has a language feature for executing an else clause when a loop terminates naturally through exhaustion (i.e., when its condition becomes false, rather than by an early break).  You can use it like this:

for _ in range(max_iterations):
    if abs(f(x0)) <= tolerance:
        break
    # TODO: refine x0 here
else:
    # Loop exhaustion, i.e. max_iterations reached
    # TODO: raise an error
# TODO: Calculate x1 and x2 here

Pretty!

All of that setup lets your code look like mathematics, not like a C program.  Now you can clear your head of the minutiae and focus on things that matter, like your mathematical technique.

I've made a few remarks in the code comments as well.

from math import sqrt

def solve_degree_3_polynomial(f, tolerance=0.00000001, initial_guess=0.01, max_iterations=100):
    if f.degree() != 3:
        raise ValueError, "Input must be a polynomial of degree 3"

    # If 0 is a root, make x0 exactly 0 to trigger a special case for
    # the quadratic equation below.
    x0 = 0 if f(0) == 0 else initial_guess
    df_dx = f.derivative()
    for _ in range(max_iterations):
        if abs(f(x0)) <= tolerance:
            break
        if df_dx(x0) == 0:
            x0 += 0.001
        x0 = x0 - f(x0) / df_dx(x0)
    else:
        raise SolutionNotFound, "Exceeded %d iterations.  Current guess: f(%d) = %d" % (max_iterations, x0, f(x0))

    # q = Quadratic
    q = Polynomial(f[3], f[2], f[1]) if x0 == 0 else \
        Polynomial(f[3], (-f[0] / x0 - f[1]) / x0, -f[0] / x0)

    # These three cases are mutually exclusive, right?  Then write them that way.
    if abs(q.discriminant()) < tolerance:
        # I think that returning a double root is better than returning
        # None for one of the roots.  It's mathematically more correct,
        # and less likely to cause bugs involving NoneType.
        x1 = x2 = -q[1] / (2 * q[2])

    elif q.discriminant() < 0:
        # You could just let cmath.sqrt() take care of this for you instead,
        # in which case all three cases collapse down to one!
        x1 = complex(-q[1] / (2 * q[2]), +sqrt(-q.discriminant()) / (2 * q[2]))
        x2 = complex(-q[1] / (2 * q[2]), -sqrt(-q.discriminant()) / (2 * q[2]))

    else:
        # If you change
        #     from math import sqrt
        # to
        #     from cmath import sqrt
        # then the two lines below handle all three cases, regardless of
        # whether the discriminant is negative, 0, or positive.
        x1 = (-q[1] + sqrt(q.discriminant())) / (2 * q[2])
        x2 = (-q[1] - sqrt(q.discriminant())) / (2 * q[2])

    return x0, x1, x2

Example usage

f = Polynomial(3, -1, 6, -2)
(x0, x1, x2) = solve_degree_3_polynomial(f)

print "f(x) = %s" % (f)
print "f(%s) = %s" % (x0, f(x0))
print "f(%s) = %s" % (x1, f(x1))
print "f(%s) = %s" % (x2, f(x2))

… prints

f(x) = 3 x^3 + -1 x^2 + 6 x^1 + -2 x^0
f(0.333333333333) = 2.423339307e-13
f((3.44613226844e-13+1.41421356237j)) = (-4.36495284361e-12-1.7763568394e-15j)
f((3.44613226844e-13-1.41421356237j)) = (-4.36495284361e-12+1.7763568394e-15j)

Next steps

As noted in the comments, I would recommend using cmath.sqrt() to collapse the three cases for the discriminant into one.

It would also be a good idea to decompose the cubic equation solver into a generic Newton's method solver for any polynomial, followed by a quadratic equation solver.

def solve_degree_3_polynomial(f, ...):
   if f.degree() != 3:
       raise ValueError
   x0 = solve_polynomial_by_newton(f, ...)
   q = Polynomial(f[3], (-f[0] / x0 - f[1]) / x0, -f[0] / x0)
   x1, x2 = solve_degree_2_polynomial(q)
   return x0, x1, x2


Solution in R

In your last code snippet, you're mixing code from tidyverse and data.table packages. I don't consider this to be completely wrong, but I would rather avoid it to increase readability and consistency.

library(magrittr)
library(data.table)
library(bench)

# data copied from OP
dat <- structure(list(Name = structure(c(1L, 2L, 3L, 4L, 1L, 2L, 3L),
                                       .Label = c("A", "B", "C", "D"),
                                       class = "factor"),
                      Date = structure(c(1L, 1L, 1L, 2L, 2L, 2L, 2L),
                                       .Label = c("1/1/2018", "1/4/2018"),
                                       class = "factor"),
                      Val1 = 1:7,
                      Val2 = 2:8),
                 class = "data.frame", row.names = 1:7)

dat
#>   Name     Date Val1 Val2
#> 1    A 1/1/2018    1    2
#> 2    B 1/1/2018    2    3
#> 3    C 1/1/2018    3    4
#> 4    D 1/4/2018    4    5
#> 5    A 1/4/2018    5    6
#> 6    B 1/4/2018    6    7
#> 7    C 1/4/2018    7    8
str(dat)
#> 'data.frame':    7 obs. of  4 variables:
#>  $ Name: Factor w/ 4 levels "A","B","C","D": 1 2 3 4 1 2 3
#>  $ Date: Factor w/ 2 levels "1/1/2018","1/4/2018": 1 1 1 2 2 2 2
#>  $ Val1: int  1 2 3 4 5 6 7
#>  $ Val2: int  2 3 4 5 6 7 8

Tidyverse Solution

tidyr::gather(dat, key = "key", value = "value", -Date, -Name) %>%
    tidyr::unite("id", key, Date, sep = ".") %>%
    tidyr::spread(id, value)
#>   Name Val1.1/1/2018 Val1.1/4/2018 Val2.1/1/2018 Val2.1/4/2018
#> 1    A             1             5             2             6
#> 2    B             2             6             3             7
#> 3    C             3             7             4             8
#> 4    D            NA             4            NA             5

data.table Solution

dt <- data.table(dat)
dt_long <- melt(dt, id.vars = c("Name", "Date"))

dcast(dt_long, Name ~ variable + Date)
#>    Name Val1_1/1/2018 Val1_1/4/2018 Val2_1/1/2018 Val2_1/4/2018
#> 1:    A             1             5             2             6
#> 2:    B             2             6             3             7
#> 3:    C             3             7             4             8
#> 4:    D            NA             4            NA             5

Benchmark

As you can see, data.table is already much faster with 1,200 rows.

nrows <- 1.2e4
# nrows <- 1.2e6
dat2 <- expand.grid(Name = LETTERS[1:4],
                    Date = seq(as.Date("2018-01-01"), by = "days", length.out = nrows/4))
dat2$Val1 <- sample(1:8, nrow(dat2), TRUE)
dat2$Val2 <- sample(1:8, nrow(dat2), TRUE)

f1 <- function(dat) {
    tidyr::gather(dat, key = "key", value = "value", -Date, -Name) %>%
        tidyr::unite("id", key, Date, sep = ".") %>%
        tidyr::spread(id, value)
}

f2 <- function(dat) {
    dt <- data.table(dat)
    dt_long <- melt(dt, id.vars = c("Name", "Date"))
    dt_wide <- dcast(dt_long, Name ~ variable + Date)
}

mark(tidyverse = f1(dat2),
     datatable = f2(dat2),
     check = function(x, y) all.equal(x, y, check.attributes = FALSE))
#> Warning: Some expressions had a GC in every iteration; so filtering is
#> disabled.
#> # A tibble: 2 x 10
#>   expression     min    mean  median     max `itr/sec` mem_alloc  n_gc
#>   <chr>      <bch:t> <bch:t> <bch:t> <bch:t>     <dbl> <bch:byt> <dbl>
#> 1 tidyverse  184.4ms 189.7ms 187.9ms 196.7ms      5.27   15.73MB     5
#> 2 datatable   43.1ms  45.9ms  45.4ms  51.7ms     21.8     5.36MB     2
#> # ... with 2 more variables: n_itr <int>, total_time <bch:tm>

Created on 2019-02-26 by the reprex package (v0.2.1)


Insertion sort via recursion I'm learning about algorithms and have been recently experimenting with insertion sort via recursion in Python.

My code works fine, but I was wondering if there are any possible improvements that can be made. I am especially interested in ways to reduce the actual content of the code (i.e. make it shorter) or improve the speed.

def insertionsort(alist):
    i = len(alist)
    if i > 2:
        temp = alist[:i-1]
        insertionsort(temp)
        alist[:i-1] = temp[:i-1]

    k = len(alist) - 1
    m = len(alist)

    while k >= 1 and alist[k-1] > alist[k]:
        front = alist[k]
        back = alist[k - 1]
        alist[k] = back
        alist[k-1] = front

        k = k - 1

A = [4, 1, 6, 3, 9, 10]
insertionsort(A)

print(A)

Starting with the low-hanging fruit: A variable called 'temp' is a big sign that you can do better. If you were to set up your code so that it returned a new list rather than modifying it in place, you could do this:

alist[:i-1] = insertionsort(alist[:i-1])

The rest of your code assumes that we will be working on the original, but the easiest fix for that is to make a copy at the earliest opportunity. If you do that early (and with an appropriate comment), and you don't need the original list anymore (you don't), then you can reuse the name alist without losing clarity. Unfortunately, copying the list is bad for performance, but readability needs to come first. But way down the bottom, I will point out a bigger improvement that will mean we don't actually have to choose between performance and readability here.

You can also eliminate that i: Python allows negative indices to all builtin sequences, which are defined to count from the back. So the above line is just:

alist[:-1] = insertionsort(alist[:-1])

and the condition above it can test against len(alist) explicitly.

In your second loop, you use four lines to swap two list elements. This can be more idiomatically done in one line using tuple assignment:

alist[k], alist[k-1] = alist[k-1], alist[k]

But we can do better even then this - we don't need to do all these swaps at all. Instead, find where the last element should go, and put it directly there. This is exactly the type of job the bisect module is good for:

candidate = alist.pop()
bisect.insort(alist, candidate)

And this replaces the whole second while loop.

So so far we have:

def insertionsort(alist):
    # work on a copy instead of the original
    alist = alist[:]

    if len(alist) > 2:
        alist[:-1] = insertionsort(alist[:-1])

    candidate = alist.pop()
    bisect.insort(alist, candidate)

    return alist

A = [4, 1, 6, 3, 9, 10]
A = insertionsort(A)

print(A)

I said before that copying is potentially bad for performance (each copy takes time). And we're doing a lot of it. This line:

alist[:-1] = insertionsort(alist[:-1])

makes a new list containing all but the last element, which the recursive call will promptly clone (in its entirety). So that's two copies for each element after the second. It would be better if we could tell the recursive call to only treat up to a certain point in the list, and everything after that. To do this, we put the bulk of the code into a helper function:

def insertionsort(alist):
    def sort_helper(alist, hi):
        if hi > 1:
            sort_helper(alist, hi-1)

        candidate = alist.pop(hi)
        bisect.insort(alist, candidate, hi=hi)

    alist = alist[:]
    sort_helper(alist, len(alist)-1)
    return alist

A = [4, 1, 6, 3, 9, 10]
A = insertionsort(A)

print(A)

Note that the first condition changed from testing a length to testing a position, and that the helper function works completely in-place. This makes one copy, in the outer function. You can also change it back to an in-place sort like your original code by deleting two lines, and it will make zero copies. This is probably the best a recursive insertion sort can be.


A 3-D vector class built on top of numpy.array I wanted a convenient class to easy access the parameters inside. I am using a lot of math in my game; that's why a wanted to access them through x, y and z (for readability). And this is my outcome.

It is a class which lies on top of numpy array. It basically means that I can control a numpy array trough my class. And using x, y and z for accessing the parameters instead of using indices ([0], [1] or [2]).

For that I overwrite the built in functions.

Example:

a = numpy.array([1,1,1], dtype = "float32")
b = a[0]

to

a = Vector3(1,1,1)
b = a.x

So what I want to know is if this is a good way (I wanted a fast written implementation). Are there any performance issues and is it well written?

import numpy as np
from numbers import Number

class Vector3(object):
    def __init__(self, x = 0, y = 0, z = 0, dtype = "float32"):
        self._data = np.array([x,y,z], dtype = dtype)
        self.x = self._data[0]
        self.y = self._data[1]
        self.z = self._data[2]

    def __str__(self):
        return str("Vector3({0.x},{0.y},{0.z})".format(self))

    def __mul__(self, value):
        if isinstance(value, type(self)):
            result = self._data * value._data
        elif isinstance(value, Number):
            result = self._data * value
        return type(self)(x = result[0], y = result[1], z = result[2])

    def __rmul__(self, value):
        return self.__mul__(value) # Kommutativgesetz/commutative

    def __add__(self, value):
        if isinstance(value, type(self)):
            result = self._data + value._data
        elif isinstance(value, Number):
            result = self._data + value
        return type(self)(x = result[0], y = result[1], z = result[2])

    def __radd__(self, value):
        return self.__add__(value) # Kommutativgesetz/commutative

    def __sub__(self, value):
        if isinstance(value, type(self)):
            result = self._data - value._data
        elif isinstance(value, Number):
            result = self._data - value
        return type(self)(x = result[0], y = result[1], z = result[2])

    def __rsub__(self, value):
        if isinstance(value, type(self)):
            result = value._data - self._data
        elif isinstance(value, Number):
            result = value - self._data
        return type(self)(x = result[0], y = result[1], z = result[2])

#Test
if __name__ == "__main__":
    a = Vector3(5,5,5)
    b = Vector3(2,4,3)
    c = a * b
    d = 2 * a
    e = a * 2
    f = a + b
    g = a + 2
    h = 2 + a
    i = a - b
    j = 2 - a
    k = a - 2
    print(c,d,e,f,g,h,i,j,k, sep = "\n")

Your code and text mismatch. You state that you want to use x, y and z, but you don't actually do it. You only use them in the initializer, and then you use them as named parameters when you recreate your object when returning the value. So your code kind of obfuscates that you are working on a numpy array.

Simplify overridden functions

You could also simplify your code some as almost all of the functions does the same:

OPERATIONS = {
    "add" : numpy.add,
    "mul" : numpy.multiply,
    "sub" : numpy.subtract,
    ...
}

def _apply_operation(self, value, operation):

    if isinstance(value, type(self)):
        result = OPERATIONS[operation](value._data, self._data)
    elif isinstance(value, Number):
        result = OPERATIONS[operation](value, self._data)
    return type(self)(*result)

And this could be called like:

def __add__(self, value):
    return self._apply_operation(value, "add")

Another question is why do you use if ... elif, without any else. This does leave for potentially cases where neither of them hit, and this could lead to the result being undefined when returning.

If however you actually mean else instead of elif you simplify the calculation to:

result = OPERATIONS[operation](value._data if isinstance(value, type(self))
                                           else value,
                               self._data)

Or possibly even loose the result and do:

return type(self)(*OPERATIONS[operation](value._data if isinstance(value, type(self))
                                                     else value,
                                         self._data)

Consider adding/changing __repr__ and __str__

In Python it's normal to add spaces after commas, something your __str__ doesn't do. I would change the __str__ and add a __repr__ method like the following:

def __str__(self):
    return str('!r'.format(self))

def __repr__(self):
    return 'Vector3({0}, {1}, {2})'.format(*self._data)

Implement a better test scheme

Your tests are executed but you only have a visual test of them. A much better option would be to use doctest. This would allow you to write tests in the header of each function, and you could be sure they all works as expected.

Something like the following:

def __add__(self, value):
    """Adds the value into self, and returns result as Vector3.

    >>> Vector3(1, 2, 3) + Vector3(2, 4, 6)
    Vector3(3.0, 6.0, 9.0)

    >>> Vector3(1, 2, 3) + 5
    Vector3(6.0, 7.0, 8.0)
    """

    return self._apply_operation(value, "add")

And then in your main code you could simply do:

doctest.testmod()

If all tests pass, you'll see nothing, and it they fail, you'll see why the fail and both the expected and actual results.

Properties

If you want to use x, y and z as aliases into self._data you could use properties which changes self._data like the following:

@property
def x(self):
    """Property x is first element of vector.

    >>> Vector3(10, 20, 30).x
    10.0
    """
    return self._data[0]

@x.setter
def x(self, value):
   self._data[0] = value

...

if __name__ == '__main__':
    doctest.testmod()

    a = Vector3(1, 2, 3)
    a.x = 10.0

    print('a = {}, a.z = {}'.format(a, a.x))

Which would output:

a = Vector3(10.0, 2.0, 3.0), a.z = 10.0

Do however remove the setting of self.x, self.y and self.z from __init__ so you don't have conflicting data variables.


Nginx configuration, with global defaults and support for a PHP site The following code is an Nginx default conf file. The conf file itself includes another server block which holds a site's configuration.
While this combination works and the sites appears fine on web, I have a feeling that my code doesn't follow the DRY standard.
server {
    server_name _;
    return 301 https://$host$request_uri;

    root /var/www/html;
    index index.php index.html index.htm;

    location ~ \.php$ {
        include snippets/fastcgi-php.conf;
        fastcgi_pass 127.0.0.1:9000;
    }

    location / {
        try_files $uri $uri/ =404;
    }

    location ~ /\.ht {
        deny all;
    }

    # notes {
        # 443 ssl http2;
        # [::]:443 ssl http2;
    # }
}

server {
    listen 80;
    listen [::]:80;
    server_name contfix.co.il www.contfix.co.il;

    ssl_certificate /etc/nginx/conf.d/ssl/contfix.co.il.crt;
    ssl_certificate_key /etc/nginx/conf.d/ssl/contfix.co.il.key;
    ssl_dhparam /etc/nginx/conf.d/ssl/dhparam.pem;

    root /var/www/html/contfix.co.il;

    location / {
        index index.php index.html index.htm;
        try_files $uri $uri/ /index.php?$args;
    }

    location ~ \.php$ {
        include snippets/fastcgi-php.conf;
        fastcgi_pass 127.0.0.1:9000;
    }

    location ~*  \.(jpg|jpeg|png|gif|ico|css|js|ttf|woff)$ {
        expires 365d;
    }

    location ~*  \.(pdf)$ {
        expires 30d;
    }
}

Given that my code seems to be a bit repetitive, I want to ask: Can it be made a bit less repetitive?

I compared the two server configurations and the only thing that appears to match between the two is the location ~ \.php$ directive, as well as the index directive, though in the latter configuration that is under the directive location /

Perhaps the common configurations could be put into the file included via include (i.e. fastcgi-php.conf).


java : jumping caterpillar program Looking for code review, suggestions for improvement, best practices etc.

  Given N leaves numbered from 1 to N . A caterpillar at leaf 1, jumps from leaf to leaf in multiples of Aj (Aj, 2Aj, 3Aj).
  j is specific to the caterpillar. Whenever a caterpillar reaches a leaf, it eats it a little bit.. You have to find out how many leaves, from 1 to N, are left uneaten after all K caterpillars have reached the end. Each caterpillar has its own jump factor denoted by Aj, and each caterpillar starts at leaf number 1.

  Input:
  The first line consists of a integer T denoting the number of testcases. T test cases follow. Each test case consists of two lines of input. The first line consists of two integers: N, which denotes the number of leaves; and K, which denotes the number of caterpillars. Second line of each test case consists of K space seperated integers denoting the jumping factor of caterpillars.

  Example:

Input:
1
10 3
2 3 5
Output: 2

  Explanation: Testcase1: The leaves eaten by the first caterpillar are
  (2, 4, 6, 8, 10). The leaves eaten by the second caterpilllar are (3,
  6, 9) The leaves eaten by the third caterpilllar are (5, 10)
  Ultimately, the uneaten leaves are 1, 7 and their number is 2

class CatterpillarDetails{
    int leaves;
    public int getLeaves() {
        return leaves;
    }

    ArrayList<Integer> caterpillarOrder;

    public void setCaterpillarOrder(int order) {
        caterpillarOrder.add(order);
    }

    public ArrayList<Integer> getcaterpillarOrder() {
        return caterpillarOrder;
    }

    int noOfCatterpillar;
    public int getNoOfCatterpillar() {
        return noOfCatterpillar;
    }

    int result;

    public int getResult() {
        return result;
    }

    public void setResult(int result) {
        this.result = result;
    }

    CatterpillarDetails(int leaves, int noOfCaterpillar)
    {
        this.leaves = leaves;
        this.noOfCatterpillar = noOfCaterpillar;
        this.caterpillarOrder = new ArrayList<Integer>(noOfCaterpillar);
    }
}

public class Catterpillar {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testcase = sc.nextInt();
        CatterpillarDetails[] detailsObj = new CatterpillarDetails[testcase];
        for(int i = 0 ; i < testcase ; i++)
        {
            int leaves = sc.nextInt();
            int noOfCatterpillar = sc.nextInt();
            detailsObj[i] = new CatterpillarDetails(leaves,noOfCatterpillar);

            boolean[] eaten = new boolean[leaves];
            for(int j = 0 ; j < noOfCatterpillar ; j++) {
                int catterpillarOrder = sc.nextInt();
                detailsObj[i].setCaterpillarOrder(catterpillarOrder);

                for(int k = 1 ; k <= leaves ; k++)
                {
                    if(catterpillarOrder*k > leaves)
                        break;
                    else
                    {
                        eaten[(catterpillarOrder*k)-1] = true;
                    }
                }
            }
            detailsObj[i].setResult(calculateNotEaten(eaten));
        }
        for(int i = 0 ; i < testcase ; i++)
        {
            System.out.println(detailsObj[i].getResult());
        }
    }

    private static int calculateNotEaten(boolean[] eaten) {
        int count = 0;
        for(Boolean i : eaten)
        {
            if(!i)
            {
                count++;
            }
        }
        return count;
    }
}

I'm going to assume this question is in the context of quality interview code, not quality production code. Websites like GeeksForGeeks (https://practice.geeksforgeeks.org/problems/jumping-caterpillars/0)
don't grade you based on production code quality.

Your failure to correctly spell the most important word in the problem domain (Caterpillar) would put me off to a sour start. To me, that suggests an inattention to detail. In software development, little details can make a big difference.

You're doing a lot more work than you need to. The basic algorithm here should be - for each leaf, if it can be evenly divided by any of the caterpillar numbers, it gets eaten and you should move on. If none of the caterpillars eat it, increment the uneaten count and continue.

In idiomatic Java,
whitespace is placed between a control flow keyword (if, else) and the open paren
there is no whitespace before a semicolon
binary operators, including -, == and -, should have whitespace on both sides.
opening curly braces belong on the same line, not a newline

You should use try-with-resources blocks to handle closeable resources such as Scanner.

testcase is not a good variable name because it doesn't correctly explain what it's pointing to. numberOfTestCases would be better. scanner is also better than sc, because I don't have to assume what it holds.

You can also look for more opportunities to break out methods. A method with as much nested code as you have is hard to read and understand. Maximize readability until you have a known performance bottleneck.

If you were to rewrite your code using all these suggestions, it might look more like the untested code below:

import java.util.Arrays;
import java.util.Scanner;

public class Caterpillar {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int numberOfTestCases = sc.nextInt();

            for (int testCase = 0; testCase < numberOfTestCases; testCase++) {
                int numberOfLeaves = sc.nextInt();
                int[] caterpillars = readCaterpillarsFrom(sc);
                int uneatenLeaves = 0;
                for (int leaf = 1; leaf <= numberOfLeaves; leaf++) {
                    if (isLeafUneaten(leaf, caterpillars)) {
                        uneatenLeaves++;
                    }
                }
                System.out.println(uneatenLeaves);
            }
        }
    }

    private static int[] readCaterpillarsFrom(Scanner scanner) {
        int[] caterpillars = new int[scanner.nextInt()];
        for (int j = 0; j < caterpillars.length; j++) {
            caterpillars[j] = scanner.nextInt();
        }

        /* You're more likely to get a hit on smaller numbers, so the sort helps you leave earlier in some cases.
         * This is arguably a premature optimization, and may be a performance loss if the there are many
         * caterpillars and few leaves.
         */
        Arrays.sort(caterpillars);

        return caterpillars;
    }

    private static boolean isLeafUneaten(int leaf, int[] caterpillars) {
        for (int caterpillar : caterpillars) {
            if (leaf % caterpillar == 0) {
                return false;
            }
        }
        return true;
    }

}


Custom String Formatter I've written my custom implementation of an f"" / .format(...). I started the project thinking it was going to be longer than three lines.

from typing import List, Union, AnyStr

def format_string(string: str, variables: List[Union[str, int, float, bool, complex]]) -> str:
    """
    Formats the passed string with the passed list of variables

    >>> format_string("Hello, [*]", ["Ben"])
    Hello, Ben

    :param string -> str: String to be formatted
    :param variables -> List[Union[str, int, float, bool, complex]]: List of variables to format into string

    :return str: Formatted string
    """
    for index, value in enumerate(variables):
        string = string.replace("[*]", str(value), 1)
    return string

My main question is if it's possible to make this a one-liner. It absolutely infuriates me that I have to use three. I spent a long time trying a mixture of * and ''.join to no avail. The code works, I would just like to shorten it up to one line. Of course, any and all feedback is appreciated and considered.

A secondary question is the method header. To represent variables, I have a List that can contain any types of variables. How would I go about representing this instead of having to list each type separately?

For the second point, since it's easier, typing has an Any:

from typing import List, Any
. . ., variables: List[Any], . . .

For the first, you're just doing a reduction over variables:

from typing import List, Any
from functools import reduce

def format_string(string: str, variables: List[Any]) -> str:
    return reduce(lambda s, val: s.replace("[*]", str(val), 1), variables, string)

Although really, in a real use case, I'd still split this over three lines for clarity:

def format_string(string: str, variables: List[Any]) -> str:
    return reduce(lambda s, val: s.replace("[*]", str(val), 1),
                  variables,
                  string)

And honestly, I might just make that function var-arg instead of grouping things in a list to make it consistent with other format functions:

def format_string(string: str, *variables: Any) -> str:
    return reduce(lambda s, val: s.replace("[*]", str(val), 1), variables, string)

>>> format_string("[*] Hello [*]", 1, 2)
'1 Hello 2'

Note that when annotating a a var-arg parameter, you annotate the type of each element and ignore the type of the wrapping container (a tuple iirc). That means it's *variables: Any, not *variables: Tuple[... Any].

Of course though, whether or not this is better is a matter of taste, but this is the ideal use-case for reduce. Whenever you want to constantly reassign one thing in a simple loop, reduce is likely a good tool to look at.


Storing JWT in client side and putting tokens in all the future request I have started using NodeJS with Express JS and PassportJS and JWT for User Authentication. I am able to authenticate the user and generate JWT Token. I am using Bootstrap for my front-end.

By using Postman I am able to get the token and put it in the next request header and it is working fine.

But how do I do this in HTML Pages using JavaScript?

JavaScript to get response body or response headers
JavaScript to set request header with JWT Token

Here is the snippet to store data in SessionStorage:

sessionStorage.setItem('token', 'token-abcd1234');
var token = sessionStorage.getItem('token');

I have a mechanism to invalidate the token on logout by putting them in a DB.

Let me know if I am missing any pattern or missing anything.

Note: I am using login.html which has a form with a username and password. AJAX is not used.

Login Page

Login

    <form class="form-horizontal" action="/login" method="POST">

      Email:

        <input type="email" class="form-control" id="email" placeholder="Enter email" name="email">

      Password:

        <input type="password" class="form-control" id="password" placeholder="Enter password" name="password">

        <button type="submit" class="btn btn-default">Submit</button>

    </form>

NodeJS Route

router.get('/login', function(req, res, next) {
  res.render('login');
});

router.post('/login', function(req, res, next) {
  passport.authenticate('local', function(err, user, info) {
    if (err) {
      return next(err);
    }

    if (!user) {
      return res.status(401).json({
        err: info
      });
    }

    req.logIn(user, function(err) {
      if (err) {
        console.log(err);
        return res.status(500).json({
          err: 'Could not log in user'
        });
      }

      var token = Verify.getToken(user);
      res.status(200).json({
        status: 'Login successful!',
        success: true,
        token: token
      });
    });
  })(req,res,next);
});

At the time of posting this question, I had no idea about Frontend Frameworks.
Later I choose Vue Js as my frontend framework, things are working great.

All I was missing a Frontend Framework.


How to flatten the nested for loops? The problem I am facing is:
I need to interate through a bunch of lists, and there are separated conditions which needs to be satisfied by the list. conditons are not independent.

I care about the situation when all the conditions are matched.

The solutions I come up is nested interations mixed with conditions on each level, but it is rather ugly and not easy to maintain.

Is there a way for me to improve this code?

[1, 2, 3].each do |n1|
  if n1 == 1
    [1, 2, 3].each do |n2|
      if n2 == 2
        [1, 2, 3].each do |n3|
          if n3 == 3
            [1, 2, 3].each do |n4|
              if n4 == n3 # conditions are dependent
                print n1, n2, n3, n4
              end
            end
          end
        end
      end
    end
  end
end

In your example you iterate over the same collection. In that case I'd write:

[1, 2, 3].repeated_permutation(4).each do |n1, n2, n3, n4|
  if n1 == 1 && n2 == 2 && n3 == 3 && n3 == n4
    p [n1, n2, n3, n4]
  end
end

If instead you need to iterate over different collections, check Enumerable#product.

Of course, any of these alternatives will perform worse than your original code, since you drop whole groups of permutations when some condition is not satisfied.

Note that you could create a compact abstraction as efficient as your original code (it would take collections to iterate and conditions -with procs?- over them), but this won't pay off if you are going to use it only once.


Calculate the percentage of sum of hash values Please review my code and help on How can I make it better calculation in method and class definition with SOLID ruby principles??

The application has a static JSON file which contains:

{
  "homes": {
    "person_a": "windows+tables",
    "person_b": "lights+tables",
    "person_c": "doors+curtains"
 }
}

The application should, for each user request, calculate quotes for the 3 insurers. The business requirement is as follows:

The quote is a 10% of the rate if 2 covers are matched or 20% if just 1 cover is matched and that is the biggest requested, 25% if it is the second biggest or 30% if is the third.

the request from user is as follow

{:curtains=>20, :tables=>30, :windows=>50}

The system should not return a quote if the value is zero(0)

For eg: the application will return  the result for the above user request

{
    person_a: 8 (10% of 80 (two matches on windows and tables))
    person_b: 7.5 (25% of 30 (one match on tables, the 2nd biggest cover))
    insurer_c: 6 (30% of 20 (one match on curtains, the 3rd biggest cover)

}

This is my solution:

require_relative './rules'

module Coverage
  class CalculateQuotes
    def initialize(quotes)
      @quotes = quotes
    end

    def calculate_rates
      result = []
      @insurer = Coverage::Rules.parse_file ## which will give {
                                        #"insurer_rates": {
                                       #"person_a": "windows+tables",
                                       # "person_b": "lights+tables",
                                       #"person_c": "doors+curtains"
                                      # }}
      @insurer[:insurer_rates].each do |k, v|
        @match_covers = match_cover(v.split("+"))
        result << [k, calculate_rate ]
      end
    end

    def match_cover(covers)
      covers = covers.map { |x| x.to_sym }
      @quotes.select { |k,v| covers.include?(k) }
    end

    def calculate_rate
      premium    = 0.0
      persentage = get_percentage_by_match_covers
      @match_covers.values.each do |v|
        premium += v * persentage
      end
      premium == 0 ? nil : premium
    end

    def get_percentage_by_match_covers
      if @match_covers.size == 2
        0.1
      elsif @match_covers.size == 1
        only_1_match_covers
      else
        0
      end
    end

    def only_1_match_covers
      index = position_of_customer_request
      case index
      when 0
        0.2
      when 1
        0.25
      when 2
        0.3
      else
        raise StandardError
      end
    end

    def position_of_customer_request
      (@quotes.to_a.reverse).index(@match_covers.to_a.flatten)
    end
  end
end

request = {:windows=>50, :contents=>30, :engine=>20}

Coverage::CalculateQuotes.new(request).calculate_rates
````

Ruby Hash

Rather than using a verbose case statement:

 case index
      when 0
        0.2
      when 1
        0.25
      when 2
        0.3

You could use a Hash:

rates = {0 => 0.2, 1 => 0.25, 2 => 0.3}

And the case can be replaced with:

rates[index]

Rubocop Report

Use symbols as procs when possible.

covers = covers.map { |x| x.to_sym }

This is a compact alternative:

covers = covers.map(&:to_sym)

Identify unused block arguments.

@quotes.select { |k,v| covers.include?(k) }

Use an underscore to identify unused block arguments:

@quotes.select { |k, _v| covers.include?(k) }

Numeric predicates should use predicate methods instead of comparison operators if possible

premium == 0 ? nil : premium

Use the predicate method zero instead:

premium.zero? ? nil : premium


Proxy using socket, doubts on multithreading and connection closing I'm trying to make a simple proxy server in Python using the socket library, mostly to understand how it works.  I'm a noob both at programming and networking, so please be nice if my questions are totally dumb.

At the moment I've set up a proxy server which intercepts requests from the browser, prints them and sends back an "Hello" sample response. It seems to work, so next I'm going to complete it by adding a client which forwards the request to the web server, receives the response and sends it back to the browser.

However, I have two doubts about this first (seemingly working) part of the code:

import socket, threading
serv_port = 50007
server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server.bind(('', serv_port))
server.listen(5)
while True:
    #get conn to client
    conn, addr = server.accept()
    #span thread
     conn_thread = threading.Thread(target=cthread, args=(conn,))
    conn_thread.start()

 def cthread(conn):
    #set timeout
    conn.settimeout(1)
    #receive data until null data is received or socket times out
    req = b''
    while True:
        try:
              req_pack = conn.recv(4096)
            if not req_pack:
                break
            else:
                req += req_pack
        except socket.timeout:
                      break

   print req #print request to stdout

   #send a sample response
   conn.send(b'HTTP/1.1 200 OK\n\n
Hello</h1') #QUESTION 1

   conn.close() #QUESTION 2

My first question is about threading. Should I leave everything as it is, or should I, after receiving a request, span a different thread to deal with the response part?

Sample code of what I mean:

#in function cthread
print req
#span thread
resp_thread = threading.Thread(target=respthread, args=(conn, req))
resp_thread.start()

def respthread(conn, req):
    #do everything that's to be done to get response, send it to browser
    conn.send(b'HTTP/1.1 200 OK\n\n
Hello</h1') #sample response
    conn.close()

Another question: is it correct to close the connection to the browser (conn) after each response has been sent, or does it slow connections too much and it's possible to do without?

First off, you need to do some error catching with the socket functions. All of them can possibly fail, it's better to be safe and do some error catching.

Here is what I mean:

try:
    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.bind(('', serv_port))
    server.listen(5)
except socket.msg as error:
    print("Recieved error #%d: %s\n" % (error[0], error[1]))
    sys.exit(-1)

And, with socket.accept too:

try:
    conn, addr = server.accept()
except socket.error as error:
    print("Recieved error #%d: %s\n" % (error[0], error[1]))
    sys.exit(-1)

When there is an error with a socket call, a tuple is returned containing the error code (returned from the socket syscall) and an error message to go along with it.

I added a sys.exit to the code that will close the program with exit code -1, which usually means to external that there was an error while running the program. To use this, you will have to import sys.

In this part of a line

threading.Thread(target=cthread, args=(conn,))

I don't think there should be a comma after conn in the tuple for args.

According to the python docs on socket.settimeout,

  The value argument can be a nonnegative float expressing seconds, or
  None.

You aren't passing in a float value when you call settimeout.

Also, I believe that you should allow more time before a timeout. Reading in 4096 bytes of data might take more than 1 second.

Maybe 3 seconds would work.

Indentation isn't as strict in python 2 as it is in python 3, but you still want it to be perfect.

In your while loop of cthread, your indentation is messed up:

 def cthread(conn): # extra space
    #set timeout
    conn.settimeout(1)
    #receive data until null data is received or socket times out
    req = b''
    while True:
        try:
              req_pack = conn.recv(4096) # extra 2 spaces (1/2 tab)
            if not req_pack:
                break
            else:
                req += req_pack
        except socket.timeout:
                      break # extra 10 spaces (2 1/2 tabs)

   print req #print request to stdout # missing space

   #send a sample response
   conn.send(b'HTTP/1.1 200 OK\n\n<h1>Hello</h1') # missing space

   conn.close() # missing space

Either indent lines with 1 tab or 4 spaces.

Now for your questions.

I'm a little confused by this question. Right now in your code, when you recieve a connection, you do handle the recieving and the sending in a separate thread. This is fine, and is a good idea.
After you close a connection, there is no connection to slow down. And yes; this is fine. Since your server isn't going to do anything more after it has sent it's response, then there is no point in keeping the connection. It'll just bog your server down in the long-run.


Displaying completed and failed wuuks using one or two functions I have upgraded my code. In the old code I had two functions: display_maker_success() and display_maker_fail():

function display_maker_success($link, $userid){
    $status="closed";
    $result="completed";

    $html = '';
    $sql = "select start, name from wuuk where tasker_id ='$userid' and status ='$status' and result ='$result' order by id desc LIMIT 6;";

    $result = mysql_query($sql, $link);
    $isempty=mysql_num_rows($result);
    If ($isempty ==0) {
        $html .= "No Record";
    } else {
        $html .= "
";
        $html .= "
Date & Time	Name	Status
";
        while ($row = mysql_fetch_array($result, MYSQL_NUM)) {
            $html .= "
$row[0]	$row[1]	Completed
";
        };
        $html .= "
";
    };
    echo $html;
};

function display_maker_fail ($link, $userid) {
    $status="closed";
    $result="fail";

    $sql = "select start, name from wuuk where tasker_id ='$userid' and status ='$status' and result ='$result' order by id desc LIMIT 1;";
    $result = mysql_query($sql, $link);
    $isempty=mysql_num_rows($result);
    If($isempty ==0){
        $html .= "No Record";
    } else {
        $html .= "
";
        $html .= "
Date & Time	Name	Status
";
        while ($row = mysql_fetch_array($result, MYSQL_NUM)) {
            $html .= "
$row[0]	$row[1]	fail
";
        };
        $html .= "
";
    };
    echo $html;
};

But I realised I can combine those two functions into one display_maker_stat() by putting more arguments into the function. I like it very much!

function display_maker_stat($link, $userid, $reuslt = 'fail', $limit)
{
    $status = "closed";
    $html = '';
    $sql = "select start, name from wuuk where tasker_id ='$userid' and status ='$status' and result ='$result' order by id desc LIMIT 1;";
    $query = mysql_query($sql, $link);
    if (mysql_num_rows($query) != 0) {
        $html .= "
";
        $html .= "
Date & Time	Name	Status
";
        while ($row = mysql_fetch_array($query, MYSQL_NUM)) {
            $html.= "
$row[0]	$row[1]	$result
";
        }
        $html.= "
";

    }
    else {
        $html.= "No Record";
    }
    echo $html;
}

Is there a better way to do this? I want more code reuse.

I used to do this sort of "optimisation" 20 years ago.  I don't anymore.  Clarity of code is more important.  I would rather have fewer parameters and properly named functions.  This way, you can just read the code without worrying about how the function works.

If you do what you are proposing, then to understand the code, you have to look at the what the function is doing every time it is used !!!

EDIT
An example of what I have just finished doing at work.  The original procedure was called Launch_Client_Form with a whole bunch of parameters.  It had four functions and the parameters of all 4 functions had to be passed each time.  I created 4 procedures

View_Client
Create_Client
Edit_Client
Find_Client

Each one has only the parameters it requires.  Internally they all still call Launch_Client_Form.  Now, when you encounter Edit_Client in the code, it does not require a comment and you know what it is going to do.


Ungrouping of values into multiple lists Given is a list with (possibly) non-unique elements.

My goal is to split this list into multiple lists, in sum containing the same elements, but separated in a way that no sublist contains each element value more than once.

A few examples to show the supposed result:

[1, 2, 2] -> [[1, 2], [2]]

[1, 2, 2, 3, 3, 4, 4, 4] -> [[1, 2, 3, 4], [2, 3, 4], [4]]

[4, 4, 1, 1, 4, 1, 3, 2, 1, 2, 5, 1, 2, 4, 4, 2, 5] ->
[[4, 1, 3, 2, 5], [4, 1, 2, 5], [4, 1, 2], [4, 1, 2], [4, 1]]

The order of the elements is not important. The fact that is it preserved is just a side-effect of my current implementation, but not needed. So the following would also be valid:

[1, 2, 2] -> [[2, 1], [2]]

My current implementation looks as follows:

fun <T> ungroupDuplicateValues(values: List<T>): List<List<T>> {
    val result: MutableList<List<T>> = mutableListOf()
    var counts = values.groupingBy { it }.eachCount().toMutableMap()
    while (counts.isNotEmpty()) {
        val newCounts: MutableMap<T, Int> = mutableMapOf()
        val subResult: MutableList<T> = mutableListOf()
        for ((value, count) in counts) {
            subResult.add(value)
            if (count > 1) {
                newCounts[value] = counts.getValue(value) - 1
            }
        }
        result.add(subResult)
        counts = newCounts
    }
    return result
}

It works, but feels kind of clumsy. Is there a more elegant/idiomatic (maybe functional) solution?

Played a bit with it... how do you like the following?

fun <T> ungroupDuplicateValues(values: List<T>): List<List<T>> {
  val countPerValue = values.groupingBy { it }.eachCount()
  val maxCount = countPerValue.map { it.value }.max() ?: 0
  return (1..maxCount).map { index ->
    countPerValue.filterValues { it >= index }
        .map { it.key }
  }
}

Complexity (in regards to O-notation) should be similar to yours...

Or the following variant using tailrec:

fun <T> ungroupDuplicateValues(values: List<T>) = ungroupDuplicateValues(values.toMutableList())

private tailrec fun <T> ungroupDuplicateValues(remainingValues : MutableList<T>, newValues : MutableList<List<T>> = mutableListOf()) : List<List<T>> {
  val values = remainingValues.distinct()
  newValues.add(values)
  values.forEach { remainingValues.remove(it) }
  return if (remainingValues.isEmpty()) newValues
         else ungroupDuplicateValues(remainingValues, newValues)
}

But don't ask me about the O-notation here. tailrec should be optimized, but as I still use a forEach { remove } it will probably still be O(n²).

If you rather prefer a direct assigned function (of the first shown solution), maybe the following is also ok for you:

fun <T> ungroupDuplicateValues(values: List<T>) =
  values.groupingBy { it }.eachCount().let { countPerValue ->
    (countPerValue.map { it.value }.max() ?: 0).let { maxCount ->
      (1..maxCount).map { index ->
        countPerValue.filterValues { it >= index }
            .map { it.key }
      }
    }
  }


Scalable client server communication import socket,time
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind(('',0))
port=s.getsockname()[1]
s.setblocking(0)
lines=[]
while True:
    try:
        data, addr = s.recvfrom(1024)
        if addr not in clients:
            clients.append(addr)

        if not lines:
            for client in clients:
                s.sendto(lines, client)
    except:
        pass
s.close()

I have paint application, in which the server sends the co-ordinates to a set of clients. I use the above code for sending, launching on a separate thread. This sends data to each client sequentially. This will cause a delay to the clients at the end of the list. Launching a separate thread for each client has scalability issues. Is there is scalabe way to write the above code maybe using async.io?

You cannot use recvfrom with a TCP socket (SOCK_STREAM). You don't see the error, because of your wrong exception handling. Never ignore all exceptions! Don't write your own server, use the appropriate interface from asyncio.


Review implementation for Partial Ordering of Vectors Partial ordering may be useful in some scientific contexts. This is quick prototype in Python, which I believe works correctly.

Do you notice any flaws? Can you provide a counter-example of wrong results? Additional test cases will be also rewarded with +1.

#!/usr/bin/env python3

import unittest as ut

def leq (L1, L2):
    assert len(L1) == len(L2)
    l = g = 0
    for v1, v2 in zip(L1, L2):
        if v1 < v2:
            l += 1
        elif v1 > v2:
            g += 1
    return l >= 0 and g == 0

class Test (ut.TestCase):

    def test1 (self):
        V1 = [1, 2, 3]
        V2 = [1, 2, 2]
        self.assertFalse(leq(V1, V2))
        self.assertTrue(leq(V2, V1))

    def test2 (self):
        V1 = [1, 2, 3]
        V2 = [2, 2, 3]
        self.assertTrue(leq(V1, V2))
        self.assertFalse(leq(V2, V1))

    def test3 (self):
        V1 = [1, 2, 3]
        self.assertTrue(leq(V1, V1))

    def test4 (self):
        V1 = [1, 2, 3]
        V2 = [3, 2, 1]
        self.assertFalse(leq(V1, V2))
        self.assertFalse(leq(V2, V1))

Edit: redefining the leq function (thanks to Cary for the comment)

leq = lambda L1, L2: sum(v1 > v2 for v1, v2 in zip(L1, L2)) == 0

Proved to be working with the same unit test.

Same result, but using short-circuit logic and avoiding to scan both lists:

leq = lambda L1, L2: not any (v1 > v2 for v1, v2 in zip(L1, L2))

As suggested in comment, equivalent version, more natural:

leq = lambda L1, L2: all(v1 > v2 for v1, v2 in zip(L1, L2))

Not much to say about it, good job!

Documentation: explain the mathematical explanation of your partial ordering unless it's really that obvious for your intended readers
Names:

In Python, names starting with uppercase letters are for class names: of course you're free to use your own convention, but this one makes it easy to share code between Python developers
Explicit is better than implicit: less is better than l which could also mean left or leave or whatever.

Style: In Python (see PEP8), we usually don't but spaces before function definitions.
Test cases: always add a test case for degenerate cases, eg. the empty list and lists of different lengths: those are the ones which usually fail.

(And +1 to the comments who should become an answer.)


Real time HTML tester Here is a simple webpage that I wrote to test HTML code in real time as typed, what are some ways that I can Improve my code? part of the code is reused from a previous project, I believe that it may now be causing problems. I am still learning about CCS and in places i used both the HTML width tag and the CCS property to set the width of the item.

When searching stackoverflow I found Quite a few questions about how HTML code can be loaded into an iframe, this seems to be a common problem, Am I properly loading a HTML string into an iframe?

<!DOCTYPE html>
<title>Live HTML tester</title>

Live HTML tester

    <input id="browseOpen" type="file" accept=".html"/>
    <textarea
        rows="20"
        id="HTMLdata"
        placeholder="Enter HTML code"
        onKeyPress="edValueKeyPress()
        "onKeyUp="edValueKeyPress()">
    </textarea>

Here is where the page is being hosted LiveHTML.html

Try rewriting your script with an addEventListener instead of an onChange method.

However, keep in mind that an addEventListener is not compatible with IE lower then IE9. So don't use this yet in live sites.

https://developer.mozilla.org/en-US/docs/Web/API/EventTarget.addEventListener?redirectlocale=en-US&redirectslug=DOM%2FEventTarget.addEventListener
http://coding.smashingmagazine.com/2013/11/12/an-introduction-to-dom-events/


Binary search in Scala Another exercise in Scala in which the goal is to find the target position as fast as possible. The initial input provides the grid size and the initial position. Each turn, this code provide a new position using println and the direction to the target is given back as a string ("UR" up-right, "DL" down-left, etc). The exercise does not require to end the infinite loop.

import math._
import scala.util._

object Player extends App {
    def getDirection(input: String): (Int, Int) = {
        input match {
            case "U" => (0, -1)
            case "UR" => (1, -1)
            case "R" => (1, 0)
            case "DR" => (1, 1)
            case "D" => (0, 1)
            case "DL" => (-1, 1)
            case "L" => (-1, 0)
            case "UL" => (-1, -1)
        }
    }

    def findNewRelativePositionOnAxis(direction: Int, min : Int, max : Int, current : Int) : Int = {
        direction match {
            case 1 => (max - current + 1 ) / 2
            case -1 => if(current == 1) -1 else (min - current - 1 ) / 2    //edge case for when the goal is at position 0
            case _ => 0
        }
    }

    def loop(x: Int, y: Int, minX: Int, minY: Int, maxX: Int, maxY: Int): Nothing = {
        val goaldir = getDirection(readLine)

        //Update min and max values to narrow down the search
        val newMaxX = if(goaldir._1 == -1) x else maxX
        val newMaxY = if(goaldir._2 == -1) y else maxY
        val newMinX = if(goaldir._1 == 1) x else minX
        val newMinY = if(goaldir._2 == 1) y else minY

        //Compute the next position
        val newX = x + findNewRelativePositionOnAxis(goaldir._1, newMinX, newMaxX, x)
        val newY = y + findNewRelativePositionOnAxis(goaldir._2, newMinY, newMaxY, y)

        //Send the result
        println(newX + " " + newY)

        loop(newX, newY, newMinX, newMinY, newMaxX, newMaxY)
    }

    // w: width of the building.
    // h: height of the building.
    val Array(width, height) = for(i <- readLine split " ") yield i.toInt
    val Array(x0, y0) = for(i <- readLine split " ") yield i.toInt

    loop(x0, y0, 0, 0, width, height)
}

Your code can be much improved by adding a few data structures:

case class Point(x: Int, y: Int)
case class Interval(min: Int, max: Int)
case class Dimensions(horizontal: Interval, vertical: Interval)
case class Direction(relX: Int, relY: Int)

Further you should start to introduce functions everywhere you have a comment now, for instance:

def updateSearchSpace(space: Dimensions, pos: Position, dir: Direction): Dimensions

Since this is a function that receives Dimensions and returns Dimensions as well, it is an ideal candidate to make it a method of the Dimensions class.

In order to simplify the method it is helpful to add a convenience method to Interval first:

case class Interval(min: Int, max: Int) {
  def shrink(newBound: Int, dir: Int) = Interval(
    min = if (dir == 1) newBound else min,
    max = if (dir == -1) newBound else max
  )
}

This allows you to shrink Dimensions pretty elegantly.

case class Dimensions(horizontal: Interval, vertical: Interval) {
  def shrink(pos: Position, dir: Direction) = Dimensions(
    horizontal.shrink(pos.x, dir.relX),
    vertical.shrink(pos.y, dir.relY)
  )
}

Your new data structures also give you much nicer signatures for your methods in general.

def loop(x: Int, y: Int, minX: Int, minY: Int, maxX: Int, maxY: Int): Nothing

becomes

def loop(pos: Position, searchSpace: Dimensions): Nothing

Your function findNewRelativePositionOnAxis(...) looks like it wants to be a member of Interval. I'll leave this one for you as an exercise ;-)


JavaFX FXML/window switcher I would like to write simple application where I'm going to make a few views:

Login
Register
Main app

I think that my method is not the best way to do this. Can someone give me a tip?

Main.java

package application;

import javafx.application.Application;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.layout.BorderPane;
import javafx.fxml.FXMLLoader;

public class Main extends Application {
    @Override
    public void start(Stage primaryStage) {
        try {
            BorderPane root = (BorderPane)FXMLLoader.load(getClass().getResource("Login.fxml"));
            Scene scene = new Scene(root,400,400);
            scene.getStylesheets().add(getClass().getResource("application.css").toExternalForm());
            primaryStage.setScene(scene);
            primaryStage.show();
        } catch(Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        launch(args);
    }
}

Controller.java

package application;

import java.io.IOException;
import java.net.URL;
import java.util.ResourceBundle;

import javafx.fxml.FXML;
import javafx.fxml.FXMLLoader;
import javafx.fxml.Initializable;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.layout.BorderPane;
import javafx.stage.Stage;

public class Controller implements Initializable{

    @FXML
    Button openRegister;

    @FXML
    Button openLogin;

    private Stage stage;

    @Override
    public void initialize(URL location, ResourceBundle resources) {

    }

    @FXML
    private void openRegister() throws IOException{
        stage = (Stage) openRegister.getScene().getWindow();
        BorderPane root;
        root = (BorderPane) FXMLLoader.load(getClass().getResource("Register.fxml"));
        Scene scene = new Scene(root);
        scene.getStylesheets().add(getClass().getResource("application.css").toExternalForm());
        stage.setScene(scene);
        System.out.println("Register.fxml opened");
    }

    @FXML
    private void openLogin() throws IOException{
        stage = (Stage) openLogin.getScene().getWindow();
        BorderPane root;
        root = (BorderPane) FXMLLoader.load(getClass().getResource("Login.fxml"));
        Scene scene = new Scene(root);
        scene.getStylesheets().add(getClass().getResource("application.css").toExternalForm());
        stage.setScene(scene);

        System.out.println("Login.fxml opened");
    }

}

Login.fxml

    <?xml version="1.0" encoding="UTF-8"?>

    <?import java.lang.*?>
    <?import javafx.scene.control.*?>
    <?import javafx.scene.layout.*?>
    <?import javafx.scene.layout.BorderPane?>

    <BorderPane xmlns="http://javafx.com/javafx/8.0.40" xmlns:fx="http://javafx.com/fxml/1" fx:controller="application.Controller">

          <Button fx:id="openRegister" mnemonicParsing="false" onMouseClicked="#openRegister" text="Button" BorderPane.alignment="CENTER" />

    </BorderPane>

Register.fxml

<?xml version="1.0" encoding="UTF-8"?>

        <?import java.lang.*?>
        <?import javafx.scene.control.*?>
        <?import javafx.scene.layout.*?>
        <?import javafx.scene.layout.BorderPane?>

        <BorderPane xmlns="http://javafx.com/javafx/8.0.40" xmlns:fx="http://javafx.com/fxml/1" fx:controller="application.Controller">

              <Button fx:id="openLogin" mnemonicParsing="false" onMouseClicked="#openLogin" text="Button" BorderPane.alignment="CENTER" />

        </BorderPane>

I think you are on the right track, there are only a few things I would change.

I would create a static function in the controller which inflates and returns a root node to be added to the stage (or even launches a new stage).
I would make a separate controller for each window/fragment you want to create. So you would have a LoginController and a RegisterController, each inflating and binding to their respective fxml files.

Depending on how your app is going to to be structured, you'll likely want a MainController which provides a container to swap sub-controllers in and out of. In this way, each controller is a single entity that can be used ad-hoc; only the main controller will be aware of their existence and be responsible for displaying them. MainController would also provide the ideal place for global menus, titles, toolbar, tabs, etc.

UPDATE

public static LoginUiController initScene(Stage stage) throws IOException
{
    LoginUiController controller = new LoginUiController();

    // Inflate FXML
    FXMLLoader loader = new FXMLLoader(LoginUiController.class.getResource("controller/login/Login.fxml"));
    loader.setController(controller);
    controller.root = loader.load(); // Good to have a pointer to the root node so the controller can be nested

    // Create scene
    Scene scene = new Scene(controller.root);
    stage.setScene(scene);
    controller.onCreated(); // Method to let the controller know it has been inflated and added to a scene

    return controller;
}

I generally make use of an abstract base controller that exposes the different methods I use (inflateFxml, initScene, onCreate) as well as a property binder lookup table, so the controller can unbind all listeners when closed.


Node.js RethinkDB connection wrapper with built in retries I wrote connection logic for a wrapper around RethinkDB in node.js. While it works, I know it can be cleaned up, and done in a better manner. Essentially the logic is start at the first host in config.hosts, if _connect() fails, then try the next host in the array. This continues for three times, or until config.hosts is empty. If __connect() is successful just set rethinkdbConnection to the returned connection object.

var config.hosts = ['10.0.0.1', '10.0.0.2', '10.0.0.3'];
var rethinkdbConnection;

exports.connect = function(config, callback) {
    var rethinkdbConfig = clone(config);
    delete rethinkdbConfig.hosts;

    function _connect(callback) {
        rethinkdbConfig.host = config.hosts.shift();

        r.connect(rethinkdbConfig, function(error, connection) {
            if(error) {
                return callback(error);
            }

            return callback(null, connection);
        });
    }

    _connect(function(error, connection) {
        if(error) {
            if(!config.hosts.length) {
                return callback(error);
            }

            _connect(function(error, connection) {
                if(error) {
                    if(!config.hosts.length) {
                        return callback(error);
                    }

                    _connect(function(error, connection) {
                        if(error) {
                            return callback(error);
                        }
                    });
                }
            });
        } else {
            rethinkdbConnection = connection;
            return callback();
        }
    });
};

What is a better way to write this?

Also it would be great instead of arbitrarily trying _connet() 3 times, to try as many times as the length of config.hosts instead.

You can use recursive promises. If promises don't exist in your platform, you could use a third party library or a polyfill to do the same thing.

function tryConnecting(config, remainingHosts){

    // Make a copy of hosts that we can shift off stuff. Don't modify config.
    remainingHosts = config.hosts.slice(0);

    // Promises resolve or reject only when we call resolve and recject.
    // When we see that we can still retry, we don't call either.
    return new Promise(function(resolve, reject)){

        // Update host
        config.host = remainingHosts.shift();

        // Try connecting
        r.connect(config, function(error, connection) {

            // If it fails and we still have hosts remaining, call the function
            // again. This promise's resolve and reject will be called when that
            // call's promise resolves or rejects
            if(error && remainingHosts.length) tryConnecting(config, remainingHosts).then(resolve, reject);

            // If it's an error, and we have no more remaining hosts, we reject
            // the promise. If this call was not the first (ie. previous call
            // failed with remaining hosts), then that promise will be rejected
            // with the same values.
            else if(error && !remainingHosts.length) reject(error, null);

            // If no error, then we resolve with the connection. If this was
            // not the first call (ie. previous call failed with remaining
            // hosts) then, that promise will resolve with the same values.
            else resolve(null, connection);
        });
    });
}

exports.connect = function(config, callback) {
    tryConnecting(config, config.hosts).then(callback, callback);
};


Efficient image generation with nodejs I have an app written with node.js, I have a function which takes an image file name and generates a few variations of this image, code below. The issue I am having is that when I have to generate resized images from multiple original images(20+) it sucks up all of the resources on my developing machine, CPU bumps to 100% as well as RAM. While If I run this on the server the process is killed since it sucks up all resources. I am using gm npm module which works on top of GraphicsMagick and ImageMagick. The way I use them is pretty identical to the example on their page.

My developing machine is macbook air with 8gb ram and 1.7GHz i7 processor.
My server is 10$ droplet on digitalocean with 1 GB / 1 CPU

On both I have

Node v6.10.1
NPM v4.2.0
GraphicsMagick v1.3.25
ImageMagick v6.9.8-3

I know that generating images is not an effortless task, but I am sure this should not be taking so much resources and break the app each time I have to generate images from 20+ originals on the server. I tried other npm packages like jimp, node-imagemagick-native, imagemagick and lwip. But the outcome is the same, my question is there something I can do to optimize the resources usage of the machine it is running on?

'use strict';
const path = require('path');
const gm = require('gm');
const debug = require('debug');

module.exports = (imgName) => {

  let sizes = [{
    width: 150,
    height: 150
  }, {
    width: 150,
    height: 150,
    crop: true,
    shortName: 'thumb'
  }, {
    width: 300,
    height: 300
  }, {
    width: 300,
    height: 300,
    crop: true,
    shortName: 'grid-300'
  }, {
    width: 500,
    height: 500
  }, {
    width: 500,
    height: 500,
    crop: true,
    shortName: 'grid-500'
  }, {
    width: 900,
    height: 600
  }, {
    width: 1400,
    height: 900
  }];

  sizes.forEach((size) => {

    if (imgName === undefined) return;

    let w = size.width;
    let h = size.height ? size.height : size.width;
    let ext = path.extname(imgName);
    let name = path.basename(imgName, ext);
    let suffix = `${w}x${h}`;
    let readPath = path.join(__dirname, '../uploads/' + imgName);

    if (typeof size.shortName === 'string') suffix = size.shortName;

    let relativePath = `../public/img/place/${name}-${suffix}.jpg`;
    let newPath = path.join(__dirname, relativePath);

    if (size.crop === true) {

      gm(readPath)
        .resize(w, h, '^')
        .gravity('Center')
        .crop(w, h)
        .quality(90)
        .write(newPath, (err) => {
          if (err) debug(err);
          return;
        });

    } else {

      gm(readPath)
        .resize(w, h)
        .quality(90)
        .write(newPath, (err) => {
          if (err) debug(err);
          return;
        });

    }

  });

};

Update:

in the uploads folder I have 40 images from 500kb to 2mb with resolution around 2000x3000px. The sizes for generated images are listed in the array.

Rather than using timing intervals, you may want to consider using promises/deferreds to process your queue. By doing this, you don't have wasted time gaps where you are not doing work. You could also experiment with the number of items you process of the queue at a given time to find the right balance between execution time and resource consumption.


My attempt at Dijkstra's Algorithm in Python 3 I am practicing my coding at HackerRank. The exact problem statement can be found here, but to summarize, it is finding the distances of the shortest path from a starting node to every other node in a non-directional graph where every edge is weighted 6. If a node is unreachable, the distance is -1. The nodes are named 1 to n. If you want an example, please see the provided one in the link.

To solve this, I googled an explanation of Dijkstra's Algorithm and tried my best to implement it (I am new to graph problems). My program passes 6/7 of the test cases, but it times out on the 7th. I improved some small inefficiencies, but it wasn't enough. Please advise me on how I may make the following faster:

def shortest (start, nodes, adj):
    unique = [] #this part is pretty standard for this Algorithm I think
    distance = [float('inf')]*nodes
    for i in range(1, nodes+1):
        if (len(adj[i-1])>0):
            unique.append(i)
    distance [start-1] = 0
    while (len(unique)>0):
        minDist = float('inf')
        for i in unique:
            if (distance[i-1] <= minDist):
                minDist = distance[i-1]
                distIndex = i
        current = distIndex #sets the current node as the closest unvisited node
        unique.remove(current)
        for i in adj[current-1]: #updates the distance of each neighbour of the current node
                neigh = i
                temp = 6 + distance[current-1] #edges are 6
                if temp < distance[neigh-1]:
                    distance[neigh-1] = temp
    return distance

q = int(input()) #each test case contains multiple problems, so just consider one iteration

for i in range(q):
    a = [] #for input purposes
    b = [] #for output purposes
    node = 0
    edge = 0

    #start of input
    node, edge = list(map(int, input().strip().split())) #the input begins with the number of nodes and edges in the graph
    for j in range(edge):
        a.append(list(map(int, input().strip().split()))) #reading the edges, which are all inputted next
    starting = int(input()) #reading the starting node
    #end of input

    adj = [[] for x in range(node)] #the adjacency matrix
    for j in a: #making the adjacency matrix from the inputted edges
        adj[j[0]-1].append(j[1])
        adj[j[1]-1].append(j[0])
    for j in adj:
        j = list(set(j)) #someone warned that the problematic test case gives the same edge many times, so this is to remove duplicates

    b = shortest(starting, node, adj)

    #formatting the output to what the question required
    b.remove(0)
    for i in range(len(b)):
        if b[i] == float('inf'):
            b[i] = -1
    print (" ".join(str(e) for e in b))

If it helps, I 'purchased' the test case which is timing out.

Those comments are very difficult to read.

j = list(set(j)) #someone warned that the problematic test case gives the same edge many times, so this is to remove duplicates

Format this properly:

# The problematic test case gives the same edge many times,
# so this is to remove duplicates
j = list(set(j))

Then remove fluff:

# Remove duplicates. Helps some test cases.
j = list(set(j))

In this case just remove the first comment, because list(set(...)) is already known to mean deduplicate. And remove the second since it's implied by the fact you've written the code.

j = list(set(j))

Another pair is

a = [] # for input purposes
b = [] # for output purposes

Don't do this. Just call them

descriptive_name_1 = []
descriptive_name_2 = []

so you don't need the comment in the first place.

Then there's q = .... So I wrack my brain thinking about what word contains q. But it turns out you just meant to write num_test_cases. What does that have to do with the letter q?

Worse than that is when you outright lie. What would you expect the variable node to contain? A node, right? Nope - it contains the total number of nodes.

And you write

node = 0

so we expect the total number of nodes to be 0 at that point, right? Nope, you immediately change your mind and write

node, edge = list(map(int, input().strip().split()))

But OK, fine. At least we know what nodes contains, then: multiple nodes, so a list (or other collection) of lengths of nodes.

Nope, it actually means exactly the same thing as node.

A similar comment goes for edge, which should be num_edges.

Then there's adj, which you label "adjacency matrix". Why not just call it adjacency_matrix then? But it's not even a dense matrix like that would imply, it's actually a list of per-node adjacencies, so call it adjacencies.

Then there's starting and start, which are the same thing named differently. Call them start_node or at least be consistent.

Going back to b, you have

b = []

but again this is a lie, because actually

b = shortest(start_node, num_nodes, adjacencies)

So just write that.

distances = shortest(start_node, num_nodes, adjacencies)

For a, initialize it as close to usage as possible and call it edges.

If you write

for j in range(num_edges):

you're misleading me into thinking you're going to use the index. When you're not going to, write

for _ in range(num_edges):

And what's up with that, followed by

for j in edges:

followed by

for j in adjacencies:

Is j just your general "this is a thing" variable? Most people use x, elem and item for that. Instead, write

for _ in range(num_edges):
for edge in edges:
for adjacent in adjacencies:

The middle can be

for start, end in edges:

The comment

#edges are 6

Isn't coherent. Try

# Edges are length 6

Instead, though, don't put this information in shortest - use 1 and multiply out when using the results.

Don't call variables temp. It's a poor name.

You've double-indented the part where you update the neighbours.

Note that

num_nodes, num_edges = list(map(int, input().strip().split()))

is just

num_nodes, num_edges = map(int, input().strip().split())

Why do you do this?

for i in adjacencies[current-1]:
    neigh = i

Just write

for neighbour in adjacencies[current-1]:

And the content can be

for neighbour in adjacencies[current-1]:
    distance[neighbour-1] = min(distance[neighbour-1], distance[current-1] + 1)

Do you not think this whole -1 thing is getting a bit silly? When reading, just decrement the edge values and starting edge correctly:

edges = []
for _ in range(num_edges):
    start, end = map(int, input().strip().split())
    edges.append((start - 1, end - 1))

start_node = int(input()) - 1

while loops and if statements don't need their condition parenthesized, and operators should be spaced properly:

while (len(unique)>0):   # before
while len(unique) > 0:   # after

Then this is better as just while unique.

Don't put spaces before the parentheses in function calls or indexing.

minDist should be min_dist. You can also start with it set to num_nodes, and the same for distance's initialization.

unique is a horrible name, and has nothing to do with the variable's purpose. Try unvisited instead. It can be initialized as

unvisited = [i for i, adj in enumerate(adjacencies) if adj]

distance, unsurprisingly, does not mean distance but instead distances. Fix that.

This code:

min_dist = num_nodes
for i in unvisited:
    if distances[i] <= min_dist:
        min_dist = distances[i]
        distIndex = i
current = distIndex

is just

min_dist = num_nodes
for i in unvisited:
    if distances[i] <= min_dist:
        min_dist = distances[i]
        current = i

and current should be called closest. It is simplifiable to

closest = min(unvisited, key=lambda x: distances[x])

This is faster if you write

closest = min(unvisited, key=distances.__getitem__)

but the difference isn't vital.

One last thing with shortest - rename it to shortest_distances.

Put the rest of the code in a main function.

If you write

def read_pair(decrement):
    x, _, y = input().partition(" ")
    return int(x) - decrement, int(y) - decrement

then you can initialize num_nodes, num_edges and edges with

num_nodes, num_edges = read_pair(0)
edges = [read_pair(1) for i in range(num_edges)]

Note my use of partition instead of split as IMO it's a better description of the operation here.

Then

for adjacent in adjacencies:
    adjacent = list(set(adjacent))

doesn't actually work! adjacent = only affects the local scope! Instead, you want

adjacencies = [list(set(adj)) for adj in adjacencies]

which is even better as

adjacencies = [set() for _ in range(num_nodes)]
for start, end in edges:
    adjacencies[start].add(end)
    adjacencies[end].add(start)

as you never have the large intermediates then, and there's no real point converting back from a set.

This stuff:

distances.remove(0)
for i in range(len(distances)):
    if distances[i] == num_nodes:
        distances[i] = -1
    else:
        distances[i] *= 6
print(" ".join(str(e) for e in distances))

is just

print(*(-1 if i == num_nodes else i * 6 for i in distances if i))

Nice, that seems to have made it fast enough, but more important the code is more readable.

We can improve speed further by avoiding input, using sys.stdin directly to get buffering.

def main(lines):
    def read_pair(decrement):
        x, _, y = next(lines).partition(" ")
        return int(x) - decrement, int(y) - decrement

    ...

main(sys.stdin)

Note that this change is sufficient on its own to beat the time limit: you can apply it to your original code to pass the test. Note also that you shouldn't mix input with next; at least on Python 2 this throws an error saying

ValueError: Mixing iteration and read methods would lose data

Though this error is gone in Python 3, that doesn't leave me feeling good about it.

I'd finish off with

from __future__ import print_function

to make it Python 2 compatible.

from __future__ import print_function

import sys

def shortest_distances(start_node, num_nodes, adjacencies):
    distances = [num_nodes] * num_nodes
    unvisited = [i for i, adj in enumerate(adjacencies) if adj]

    distances[start_node] = 0
    while unvisited:
        closest = min(unvisited, key=distances.__getitem__)
        unvisited.remove(closest)

        # Update the distances of each neighbour
        for neighbour in adjacencies[closest]:
            distances[neighbour] = min(distances[neighbour], distances[closest] + 1)

    return distances

def main(lines):
    def read_pair(decrement):
        x, _, y = next(lines).partition(" ")
        return int(x) - decrement, int(y) - decrement

    num_test_cases = int(next(lines))
    for i in range(num_test_cases):
        num_nodes, num_edges = read_pair(0)
        edges = [read_pair(1) for i in range(num_edges)]
        start_node = int(next(lines)) - 1

        adjacencies = [set() for _ in range(num_nodes)]
        for start, end in edges:
            adjacencies[start].add(end)
            adjacencies[end].add(start)

        distances = shortest_distances(start_node, num_nodes, adjacencies)

        print(*(-1 if i == num_nodes else i * 6 for i in distances if i))

main(sys.stdin)


linq.Any() check on large database Is there a way to speed up the Linq.Any check or perform the check in another way to enhance performance.

I have a mastercodes table that records unique codes for a campaign.  The code below will create new codes for a campaign but checks the mastercode table to make sure that it doesn;t already exist. Once the codes have been created and added to the mastercodes table it creates an excel file for download.

The main issue is that a campaign can have 400k codes and we have several campaigns running at once. So the mastercode table can get into the millions of records. When I request 300 new codes and run the below process without the .Any() check it takes 1-2 seconds in production. However when i add the check the process times out with the "no response to user" timeout error.

I'm using the Z.EntityFrameworrk.Extensions and the post to the table happens pretty much instantly.  But is there a way to code the perform the mastercode check that doesn't have a huge performance issue.

The Model

public class MasterCode
{
    public int MasterCodeId { get; set; }
    public int CampaignId { get; set; }
    public string CampaignCode { get; set; }
    public string Code { get; set; }
    public bool Used { get; set; }
    public DateTime SubmittedOn { get; set; }
}

The code

public static void GenerateMasterCodes(GenerateMasterCode model)
{
    using (ApplicationDbContext _context = new ApplicationDbContext())
    {
        Campaign campaign = _context.Campaigns.Find(model.CampaignId);

        List<MasterCode> masterCodes = new List<MasterCode>();
        for (var i = 1; i <= model.Count; i++)
        {
            var masterCode = new MasterCode
            {
                CampaignId = campaign.CampaignId,
                CampaignCode = campaign.CampaignCode,
                Used = false,
                SubmittedOn = DateTime.Now
            };

            // Ensure that no code already exists for that campaign.
            var code = GenerateMasterCode(model.StartString, model.CodeLength);
            while (_context.MasterCodes.Any(m => m.Code == code && m.CampaignCode == campaign.CampaignCode))
            {
                code = GenerateMasterCode(model.StartString, model.CodeLength);
            }
            masterCode.Code = code;

            masterCodes.Add(masterCode);
        }

        try
        {
            _context.MasterCodes.AddRange(masterCodes);
            _context.BulkSaveChanges();
        }
        catch (Exception ex)
        {
            ...
        }
    }
}

The Code generator

public static string GenerateMasterCode(string startString, int mastercodeLength)
{
    string numericChars = "X123456789";

    char[] chars = new char[mastercodeLength];
    Random rd = new Random();

    for (int i = 0; i < mastercodeLength; i++)
    {
        if (!string.IsNullOrEmpty(startString) && i < startString.Length)
        {
            chars[i] = Char.Parse(startString.Substring(i, 1));
        }
        else
        {
            chars[i] = numericChars[rd.Next(0, numericChars.Length)];
        }
    }

    return new string(chars);
}

GenerateMasterCode
I would break the GenerateMasterCode() method into two methods and would declare the Random as a static field tof the class.
From the Random documentation:

The default seed value is derived from the system clock and has finite resolution. As a result, different Random objects that are created in close succession by a call to the default constructor will have identical default seed values and, therefore, will produce identical sets of random numbers. This problem can be avoided by using a single Random object to generate all random numbers.

Instead of using a char[] to generate the random characters I would use a StringBuilder.
public static string GenerateMasterCode(string startString, int mastercodeLength)
{

    if (startString.Length == masterCodeLength) { return startString; }
    if (startString.Length > masterCodeLength) { return startString.Substring(0, masterCodeLength); }

    return startString + GenerateRandomCharacters(masterCodeLength - startString.Length);
}

private static Random rd = new Random();
private static string GenerateRandomCharacters(int length)
{
    string numericChars = "X123456789";
    int length = numericChars.Length;
    StringBuilder builder = new StringBuilder(length);
    for (int i=0; i < length; i++)
    {
        builder.Append(numericChars[rd.Next(length)]);
    }
    return builder.ToString();
}

GenerateMasterCodes
Right now you query in the while loop all of the MasterCodes although you are only interested in the Campain related MasterCodes. So you should query the MasterCodes which belongs to the Campain before you start with the for loop.
Assigning false to Used can be omitted, because that is the default value of bool.
You can use the var type for the List<MasterCode> as well.
If you don't use that method outside of the class you should consider to make it private.
public static void GenerateMasterCodes(GenerateMasterCode model)
{
    using (ApplicationDbContext _context = new ApplicationDbContext())
    {
        Campaign campaign = _context.Campaigns.Find(model.CampaignId);
        var campainRelatedMasterCodes = _context.MasterCodes.Where(m.CampaignCode == campaign.CampaignCode);
        var masterCodes = new List<MasterCode>();
        for (var i = 1; i <= model.Count; i++)
        {
            var masterCode = new MasterCode
            {
                CampaignId = campaign.CampaignId,
                CampaignCode = campaign.CampaignCode,
                SubmittedOn = DateTime.Now
            };

            // Ensure that no code already exists for that campaign.
            var code = GenerateMasterCode(model.StartString, model.CodeLength);

            while (campainRelatedMasterCodes.Any(m => m.Code == code))
            {
                code = GenerateMasterCode(model.StartString, model.CodeLength);
            }
            masterCode.Code = code;

            masterCodes.Add(masterCode);
        }

        try
        {
            _context.MasterCodes.AddRange(masterCodes);
            _context.BulkSaveChanges();
        }
        catch (Exception ex)
        {
            ...
        }
    }
}


Copying files, renaming conflicts I wrote a script to copy a file, but this file already exists in the target directory. So, first I need to rename the original file.

The script works, but a colleague did not want to use it because it is too complex. I would like to know how can I improve the code of this script. In some sense it seems to be overkill for simple task. I would like to find an objective reason to that opinion.

###GLOBAL VARIABLES

$goodDir = "..."
$targetDir = "..."
$goodFile = "..."
$targetFile = "..."

$app = "..."
$logDir= "..."
$timestamp = Get-Date -Format "dd-MMM-yyyy HH:mm:ss.fff" | foreach {$_ -replace ":", "."}

$log_name = $app + "_pscp-" + $timestamp + ".log"
$log_file = $logDir + $log_name

########################
#FUNCTIONS
########################

Function WriteLog
{
  param(

    [Int]$ecode=0,
    [string]$msg="Error Message"
  )
  $now = Get-Date -format "dd-MMM-yyyy HH:mm:ss.fff"
  $messageToLog = $now + ":[exit code " + $ecode.ToString() + "] :`t" + $msg
  Add-Content $log_file -value $messageToLog
}

function rename-File {
    param(
        # file to copy
        [Parameter(Mandatory)]
        [string]$fname,
        [Parameter(Mandatory)]
        [string]$from
        )
        $now = Get-Date -format "dd-MMM-yyyy"
        $toNewName = $fname + "-Copy-" + $now
        try {
            Rename-Item -Path $from$fname $toNewName -ErrorAction Stop
        }
        catch {
            WriteLog -ecode 4 -msg "The item $_.Exception.ItemName failed with the following message $_.Exception.Message"
            Break
        }
        Finally {
            WriteLog -msg "Rename FILE $fName `r`n`t`t`t`t`t`tFROM $from `r`n`t`t`t`t`t`tTO $toNewName"
        }

    }

function copy-File {
    param(
        # file to copy
        [Parameter(Mandatory)]
        [string]$fname,
        [Parameter(Mandatory)]
        [string]$from,
        [Parameter(Mandatory)]
        [string]$to    )

        try {
            Copy-Item -Path $from$fname -Destination $to -ErrorAction Stop
        }
        catch {
        WriteLog -ecode 4 -msg "The item $_.Exception.ItemName failed with the following message $_.Exception.Message"
        Break}
        Finally {
        WriteLog -msg "Copy FILE $fName `r`n`t`t`t`t`t`tFROM $from `r`n`t`t`t`t`t`tTO $to"
    }

    }

### MAIN ###

rename-File -fname $targetFile -from $targetDir
copy-File -fname $goodFile -from $goodDir -to $targetDir$targetFile

Here are some tipps:

Try to avoid / minimize the amout of global variables.
Use approved verbs (see Get-Verb) for your functions (the first letter should be uppercase).
Use the Join-Path cmdlet to combine a path.
Use string interpolation

"${app}_pscp-$timestamp.log"

or the format operator

'{0}_pscp-{1:dd-MMM-yyyy HH.mm.ss.fff}.log' -f $app, (Get-Date)

instead of string concatenation.

Also, I would not create a Copy-File nor a Rename-File function. Just invoke Copy-Item and Rename-Item in the main…


Refactor Oxford Comma function (and other functions) I wrote a program that managed projects and created a set of SQL files for each project. In the logic, I have a few functions that, each time I look at them, I wonder if they could be written in a better way. They are pretty straight forward and compact, however I feel like there are better, more efficient ways of computing their results.

I would appreciate any comments on coding style or improvements (either in readability or performance) that you may have.

Oxford Comma

This function takes a list as input then passes an Oxford comma-separated string off to another function:

# >>> obj._format_missing_message(['a','b','c'])
# 'a, b, and c'
def _format_missing_message(self, missing):
        length = len(missing)

        # Show the message if needed
        if length > 0:
            and_clause = '{} and '.format('' if length <= 2 else ',')
            message = and_clause.join([', '.join(missing[:-1]), missing[-1]])
            self._tab_pane.currentWidget().update_status(
                                            "Configs not found for: {}.".format(message))

SQL 'LIKE' String Creator

This next function takes a list of string inputs then finds the SQL LIKE syntax that recognizes all of the list:

import difflib

# >>> create_sql_regex(['123','124','125'])
# '12%'
def create_sql_regex(ids):
    ''' Creates a SQL regex from a list of strings for use in LIKE statement '''
    longest_match = ''

    # Raise an error if there is only one item in the list as there needs to be at least two
    # items to create the regex.
    length = len(ids)
    if length <= 1:
        raise NotEnoughComparisonData(
                 'Not enough data to compare. Passed list length: {}'.format(length))

    # Create the SequenceMatcher and loop through each element in the list, comparing it and
    # the previous item.
    matcher = difflib.SequenceMatcher()
    for item, next_item in zip(ids[:-1], ids[1:]):
        matcher.set_seqs(item, next_item)
        long_match = matcher.find_longest_match(0, len(item), 0, len(next_item))

        # If the match is shorter than the previous longest match or if we have not found
        # a match yet, store the match
        if long_match.size < len(longest_match) or longest_match == '':
            longest_match = item[long_match.a:long_match.a + long_match.size]

    # If not match was found, raise an error
    if longest_match == '':
        raise NoMatchFound('A match could not be found in this list: {0}'.format(ids))

    return '{}%'.format(longest_match)

Count Duplicates

This function is the simplest of the three. It takes a list as input and returns a hash that holds the count of each unique item found in the list:

# >>> count_duplicates(['a','a','b'])
# {'a':2, 'b':1}
def count_duplicates(values):
    counts = {}

    for val in values:
        if val in counts:
            counts[val] += 1
        else:
            counts[val] = 1

    return counts

Oxford comma

Are these really your expected outcomes?

# for ['a']
Configs not found for:  and a.

# for ['a', 'b']
Configs not found for: a and b.

# for ['a', 'b', 'c']
Configs not found for: a,  b, and c.

In particular, the case of a single item looks like a bug, and in the case of 3 or more items the 2 spaces between a,  b looks a bit strange.

In any case, it would make sense to split the method, for example:

def _format_missing_message(self, missing):
    if missing:
        message = _oxford_comma(missing)
        self._tab_pane.currentWidget().update_status(
            "Configs not found for: {}.".format(message))

@staticmethod
def _oxford_comma(items):
    length = len(items)
    and_clause = '{} and '.format('' if length <= 2 else ',')
    return and_clause.join([',  '.join(items[:-1]), items[-1]])

This way it's easier to unit test the Oxford comma logic.

Finally, I think the method would be slightly easier to read like this:

def _oxford_comma(items):
    length = len(items)
    if length == 1:
        return items[0]
    if length == 2:
        return '{} and {}'.format(*items)
    return '{}, and {}'.format(', '.join(items[:-1]), items[-1])

Count Duplicates

My only objection is the method name, count_duplicates. You are counting elements, not necessarily duplicates, and returning a map of item => count pairs. So for example get_counts would be more natural.

That's all I can pick on ;-)