Project Euler #7: 10001st prime This is my implementation of Project Euler #7.  Have I overdone it again?  Is there anything else I should or should not do?  It runs in 9 milliseconds on my computer.

  What is the 10001st prime number?

static int NPrimeGenerator(int nPrime)
{
    List<int> primes = new List<int>();

    primes.Add(2);
    int nPrimeVal = 3;

    while (primes.Count != nPrime)
    {
        int sqrtNPrimeVal = (int) Math.Sqrt(nPrimeVal);

        foreach (int i in primes)
        {
            if (nPrimeVal % i == 0) { break; }

            if (i >= sqrtNPrimeVal)
            {
                primes.Add(nPrimeVal);
                break;
            }
        }

        nPrimeVal += 2;
    }

    return primes[primes.Count - 1];
}

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int nPrime = NPrimeGenerator(10001);

    s.Stop();

    Console.WriteLine(nPrime);

    Console.WriteLine(s.ElapsedMilliseconds);
}

Have I overdone it again?

I think it's not bad at all. I don't think you overdid anything.

  Is there anything else I should or should not do?

Notice that the condition primes.Count != nPrime of the while loop is unnecessary evaluated many times:
when nothing was added to the list,
the re-evaluation is pointless.

You could improve this by changing it to an infinite loop with while (true),
and moving the original condition to the point right after adding a prime to the list. If the target count is reached, break out of both loops.

TOP: while (true)
{
    int sqrtNPrimeVal = (int) Math.Sqrt(nPrimeVal);

    foreach (int i in primes)
    {
        if (nPrimeVal % i == 0) { break; }

        if (i >= sqrtNPrimeVal)
        {
            primes.Add(nPrimeVal);
            if (primes.Count == nPrime)
            {
                break TOP;
            }
            break;
        }
    }

    nPrimeVal += 2;
}

But I think a bigger problem with this code is the poor naming,
especially of variables:

nPrimeVal implies a prime value, possibly the n-th prime. But that's not the case, making it very misleading. possiblePrime would be better.
nPrime implies.... I don't really know what. It's the target count, so I'd name it targetCount
NPrimeGenerator is not a great name. The method returns the n-th prime number, so GetNthPrime would seem more natural

It's good that you skip even numbers when searching for the next time.
What would be even better is to use a sieve,
a popular choice being the Sieve of Eratosthenes.

Lastly,
a little thing,
but note that in the condition i >= sqrtNPrimeVal you can drop the equality (making it i > sqrtNPrimeVal),
as in the case of equality the condition will not be reached,
thanks to the break right before it.


Extends Scala iterator's drop method to allow for drop(x: Long) I have a need to drop quantities of elements from an iterator beyond Int.MaxValue so I wrote a helper function that does just that. However, I can't help but feel like I'm doing this the dumb way - that there's got to be some built-in language construct or at least a more elegant way of tackling the problem.

/**
 * drops a Long's worth of elements from an Iterator[T] and returns the succeeding element.
 *
 * @param dropVal is the number of elements we want to drop
 * @param iteratorLong is the the iterator from which you want to drop lots-o-elements
 *
 * @return the value you need
 */
def dropLongAndGet[T](dropVal: Long, iteratorLong: Iterator[T]): T = {
    val dropCount = dropVal / Int.MaxValue
    val dropCountRemainder = (dropVal % Int.MaxValue).toInt

    var localIteratorReference = iteratorLong
    for (i <- 0L until dropCount) {
        localIteratorReference = iteratorLong.drop(Int.MaxValue)
    }

    return localIteratorReference.drop(dropCountRemainder)
                                 .next
}

Also, I am aware that the code will work w/o the return keyword - I use it because I'm used to seeing it from Java, it doesn't hurt anything to have it there, and I think it helps non-Scala programmers make sense of what's going on if/when they have to read my code.

You can use a (tail-)recursive method to achieve same result:

def drop[T](c: Long, i: Iterator[T]): Iterator[T] = {
  if (c > Int.MaxValue) drop(c - Int.MaxValue, i.drop(Int.MaxValue))
  else i.drop(c.toInt)
}

def dropLongAndGet[T](dropVal: Long, iteratorLong: Iterator[T]): T = {
  drop(dropVal, iteratorLong).next
}


python: generate a 'diff' dictionary out of two nested dictionaries I have written a function diff that takes two nested dictionaries and it computes a difference of their content (what is inside the list) returning a new dictionary. To better explain what I mean by difference here is an example of two input dictionaries:

dep={'cl1': {'to_do': ['bill', 'ann 46.0.1']},
     'cl2': {'to_do': ['ann 2.2.3']},
     'cl3': {'to_do': ['bill 2.4']}}

ins={'cl1': {'present': ['bill', 'ann 46.0.1', 'ann 2.2.3']},
     'cl2': {'present': ['ann 2.2.3','joy 6.9','matt 6.9']},
     'cl3': {'present': ['bill 2.4']}}

The diff function compares, for each key (cl1 with cl1,cl2 with cl2 and so on...), the present list of ins with the to_do list of dep. If an item of the present list does not appear in the to_do list for a specific key than this item will be added to a list in the output dictionary. If the item found in the present is already in to_do than None will be added to the list. The function returns a dictionary having the same structure as the input dictionaries. Only the names appearing in the list are taken, i.e. no numbers after the names.

For instance the diff function applied to the case above will give:

out = diff(ins,dep)
out = {'cl1': {'to_uninstall': ['ann']},
       'cl2': {'to_uninstall': ['joy', 'matt']},
       'cl3': {'to_uninstall': [None]}}

Below is the function I am using:

def diff(installed, deploy):
    answer = {}
    #ls_uninst=[]
    for ki,vi in installed.iteritems():
        for kd, vd in deploy.iteritems():
            if ki == kd:
                for ki1, vi1 in vi.iteritems():
                    for kd1, vd1 in vd.iteritems():
                        ls_uninst = []
                        # check if the list is empty
                        if not vi1 :
                            answer[ki] = {}
                            answer[ki]['to_uninstall'] = [None]
                        # non empty list
                        else:
                            for i in vi1:
                                if i not in vd1:
                                    # this gives only the name of the package (not the version)
                                    ls_uninst.append(i.split()[0]) # use i only to get the full name
                                elif i in vd1:
                                    ls_uninst.append(None)
                                # Check if lists contains only None
                                if all(x is None for x in ls_uninst):
                                    answer[ki] = {}
                                    answer[ki]['to_uninstall'] = [None]
                                else: # If at least one package is found
                                    ls_final = [x for x in ls_uninst if x is not None]
                                    answer[ki] = {}
                                    answer[ki]['to_uninstall'] = ls_final
    return answer

It works but I guess this could improved..how? Thanks

To start I'd change the way that you find vd. Instead of looping through the dictionary and checking the keys are the same, just do a lookup of the key.
This may raise a KeyError, and so you'll want to put a guard in for that.

However the rest of your code needs to change.
First if we have a look at your for i in vi1 loop.
You have the comment Check if lists contains only None, but you're making that list?
Don't do this. Ever.
And so I would move the if and else out of that loop:

for i in vi1:
    if i not in vd1:
        ls_uninst.append(i.split()[0])
    elif i in vd1:
        ls_uninst.append(None)

if all(x is None for x in ls_uninst):
    answer[ki] = {}
    answer[ki]['to_uninstall'] = [None]
else:
    ls_final = [x for x in ls_uninst if x is not None]
    answer[ki] = {}
    answer[ki]['to_uninstall'] = ls_final

From this we can see that the for loop should probably be a comprehension, and I'm saying this now [None] is horrible, so I'm removing that from here.
Which would result in:

ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]

After this, you should be able to see that if not vi1 is true not ls_uninst is true too, and so you can merge these ifs.
Resulting in something like:

for kd1, vd1 in vd.iteritems():
    ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
    answer[ki] = {}
    if ls_uninst:
        answer[ki]['to_uninstall'] = ls_uninst
    else:
        answer[ki]['to_uninstall'] = [None]

The if can then become either a ternary, or you can use or. I think or is quite nice here.
But to be honest, you should just remove this if.

You should now have something that looks like:

def diff(installed, deploy):
    answer = {}
    for ki, vi in installed.iteritems():
        try:
            vd = deploy[ki]
        except KeyError:
            continue
        for ki1, vi1 in vi.iteritems():
            for kd1, vd1 in vd.iteritems():
                ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
                answer[ki] = {}
                answer[ki]['to_uninstall'] = ls_uninst or [None]
    return answer

This only uses the last vi1 and vd1 to create this list.
So you should use itervalues instead.
Also I'd use all of the values, not just the last.
This can be done by flattening vi.itervalues,
I'd do this by using itertools.chain.from_iterable, but ultimately it's up to you.
I'd also change vd1 to a set.
And all of this results in:

from itertools import chain
flatten = chain.from_iterable

def diff(installed, deploy):
    answer = {}
    for ki, vi in installed.iteritems():
        try:
            vd = deploy[ki]
        except KeyError:
            continue
        vi1 = flatten(vi.itervalues())
        vd1 = set(flatten(vd.itervalues()))
        ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
        answer[ki] = {}
        answer[ki]['to_uninstall'] = ls_uninst or [None]
    return answer


3Sum 2 Different implementations complexity These are 2 implementations for the http://en.wikipedia.org/wiki/3SUM problem,
The first one is mine.
and in the second one I implemented Wiki's pseudo code.

Can someone please tell me if there is a difference between the two in complexity of runtime and memory space?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{

    //the 3SUM problem asks if a given set of n integers,
    //each with absolute value bounded by some polynomial in n, contains three elements that sum to zero
    public class ThreeSum
    {
        public ThreeSum()
        {
            List<int> array = new List<int> { 25, -10, -7, -3, 2, 4, 8, 10 };
            List<int> res = SolveThreeSum(array);
            res = SolveThreeSumWiki(array);
        }

        public List<int> SolveThreeSum(List<int> array)
        {
            for (int i = 0; i < array.Count - 2; i++ )
            {
                for (int j = i + 1; j < array.Count -1; j++)
                {
                    for (int k = i + 2; k < array.Count ; k++)
                    {
                        if ((array[i] + array[j] + array[k]) == 0)
                        {
                            return new List<int> { array[i], array[j], array[k] };
                        }
                    }
                }
            }
            return null;
        }

        public List<int> SolveThreeSumWiki(List<int> array)
        {
            array.Sort();
            for (int i = 0; i < array.Count - 3; i++)
            {
                int a = array[0];
                int start = i + 1;
                int end = array.Count - 1;
                while (start < end)
                {
                    int b = array[start];
                    int c = array[end];
                    if ((a + b + c) == 0)
                    {
                        return new List<int> { a, b, c };
                    }
                    else if (a+b+c > 0)
                    {
                        end = end - 1;
                    }
                    else
                    {
                         start = start + 1;
                    }
                }
            }
            return null;
        }
    }
}

Your version

You have a bug in your three-loop implementation. This sort of bug creeps in when you use copy/paste to code without being diligent about checking what's useful. In your 'k' loop you have:

for (int k = i + 2; k < array.Count ; k++)

But that should loop from j + 1 and not i + 1. You should have:

for (int k = j + 1; k < array.Count ; k++)

This will significantly improve your performance for large lists.

The performance of this option will scale in terms of \$O(n^3)\$ which means each time you double the input data size, you will take 8 times longer to compute a result.

Wiki Version

The second method uses the wiki algorithm, which is also the base of the algorithm I would recommend....

The Sort will take \$O(n \log{n})\$ time. For largeish lists the log(n) can be effectively ignored....

What's interesting here, is that you loop to the array size still in the i loop. You can actually limit the outer loop to valeus less than or equal to 0.

At least one of the values has to be 0 or less in order for there to be a zero-sum.

Similarly, once you have a second number, chosen from values after i, you should then be able to do a binary-search for the third number.


Add a car to a map based on its model I have a map of cars Map<String, Set<Car>> which can be returned by getCarsMap() method where key is model of car , and value is list of cars of same model.

I would like to improve Car addCar(Car car) function. For now I wrote this a bit ugly piece of code.

public Car addCar(Car car) {
if(getCarsMap().entrySet().stream().anyMatch(es -> es.getKey().equals(car.getModel()))){
    if(!getCarsMap().get(car.getModel()).contains(car)){
        getCarsMap().get(car.getModel()).add(car);
    }
}else{
    Set<Car> tmpSet = new HashSet<Car>();
    tmpList.add(car);
    getCarsMap().put(car.getModel(), tmpSet) ;
}
return car;}

Since purpose is to learn streams, lambdas etc. (java8) I would love to use as these things as much as possible.

There is not need to go to streams at all for a piece of functionality already implemented in the containsKey member function of Map.

if(getCarsMap().containsKey(car.getModel())){
    if(!getCarsMap().get(car.getModel()).contains(car)){
        getCarsMap().get(car.getModel()).add(car);
    }
}


Method and class method debugging decorator A little while ago in The 2nd Monitor, me and @Phrancis were talking about Python and debugging, and the topic of function decorators came up with this message:

  Ethan Bierlein: You could even build a debug decorator. Give me a sec.

So, I built a small, simple debugging decorator, which would just print out the arguments of any method it was applied to.

I decided to go a little further though, and build two separate decorators. One for regular methods, and one built specifically for class methods. Essentially, the regular method decorator takes a function, and will print out it's arguments, and keyword arguments if debug=True. The class method decorator does the same, except it also prints out the attributes of the class it's contained in as well.

I'm wondering a couple of things though:

Is this a "pythonic" way to debug the arguments of a function?
Is there any additional data that should be debugged, that I missed?
Is the extra ClassMethodDecorator really needed? Or is there a simpler way to support both with one decorator?
I've built this to be Python 3, and Python 2.7 compatible. Did I do this correctly?

debug.py

from pprint import pprint

class MethodDebug(object):
    """Debug a normal method.

    This decorator is used for debugging a normal method,
    with normal arguments, i.e, not printing out the data
    of the class it's contained in.

    Keyword arguments:
    debug -- Whether or not you want to debug the method.
    """
    def __init__(self, debug):
        self.debug = debug

    def __call__(self, function):
        def wrapper(*args, **kwargs):
            if self.debug:
                pprint(args)
                pprint(kwargs)
            return function(*args, **kwargs)
        return wrapper

class ClassMethodDebug(object):
    """Debug a class method.

    This decorator is used for debugging a class method,
    with normal arguments, and self. When using this
    decorator, the method will print out it's arguments
    and the attributes of the class it's contained in.

    Keyword arguments:
    debug -- Whether or not you want to debug the method.
    """
    def __init__(self, debug):
        self.debug = debug

    def __call__(self, function):
        def wrapper(function_self, *args, **kwargs):
            if self.debug:
                pprint(function_self.__dict__)
                pprint(args)
                pprint(kwargs)
            return function(function_self, *args, **kwargs)
        return wrapper

test.py

from debug import MethodDebug, ClassMethodDebug

@MethodDebug(debug=True)
def normal_method(a, b):
    return a * b

print(normal_method(10, 10))

class TestClass(object):
    def __init__(self, a, b):
        self.a = a
        self.b = b

    @ClassMethodDebug(debug=True)
    def class_method(self, c):
        return self.a * self.b * c

a = TestClass(10, 10)
print(a.class_method(10))

To address your specific questions:

Is it Pythonic enough? I think so.
Is there any additional data that should be debugged? If I was using this for my debugging, I’d want a bit more information:

The name of the function that’s been called – knowing which args/kwargs were supplied to an unknown function is not that useful
The return value of that function
A trace statement when the function returns

There should also be something to distinguish trace output from regular output. That makes it much easier for me to reconstruct the call flow afterwards. Here’s an example of the sort of output I mean:

[trace] enter my_function {
[trace]   args: (10, 10)
[trace]   kwargs: {}
hello world
[trace] return 100 } exit my_function

For extra brownie points, use the traceback module to indent a function and its arguments/return value to match their level in the call tree.
Do I need a separate function and method decorator? It seems like it would be possible to do. I haven’t tried it, but https://stackoverflow.com/q/19314405/1558022 seems like it might have a couple of approaches.

If applied to a method, your function decorator will always print the repr() of the object. That might be enough in most cases – perhaps rather than defining a second decorator, you add an argument debug_object to your function decorator which additionally prints the object dict on demand.
Is it compatible with Python 2.7 and Python 3? As far as I can tell, yes.

Two other (minor) comments:

I would rename the decorators. The first is misleading, because it’s described as “method debug”, but actually gets applied to functions. More generally, I’d be inclined to violate naming principles and make these lowercase instead, so they don’t look out of place next to the decorated functions. I’d probably call them something like @internaltrace.
The docstring for “debug” is not very useful. A better docstring would tell me exactly what debugging means in this context – here, something like “print the arguments supplied to the function” would be better.

I’d be inclined to rename this parameter to “trace”, but I think correcting the docstring is more important.

A couple of additional ideas that came to me this morning:

You might want to tie this into the logging library, and direct all trace output to a dedicated file (say inttrc.log). That isolates trace statements from regular prints without putting [trace] everywhere, and is easier to search through later.

This will get you timestamps, which are worth including, but I forgot about yesterday.
Although pprint is nice, I think a one-line string might be better. You can always unpack it later if you need to, but having all the associated parts of args/kwargs on the same line will be easy for parsing later.


Find the longest line in 2D (MxM) array (vertical, horizontal, or diagonal) Find the length of the longest line with given square (MxM) matrix. (vertical, horizontal, or diagonal allowed) (Length of the longest line = number of consecutive 1's)

i.e.)
input:

{
{0,0,0,0,0,0,0,0},
{0,0,1,0,1,0,0,0},
{0,1,0,1,0,0,0,0},
{1,1,1,1,1,1,1,0},
{0,1,0,0,0,1,0,0},
{1,1,0,0,0,0,1,0},
{0,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0}
}

output: 7 (The 4th horizontal row is the longest line in this case.)

My java code:

public class LongestLine {
    private int hmax = 0;
    private int vmax = 0;
    private int rdmax = 0; // right down direction
    private int ldmax = 0; // left down direction

    public int longestLine(int[][] grid) {

        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 1) update(grid, i, j);
            }
        }

        return Math.max(Math.max(hmax, vmax), Math.max(rdmax, ldmax));
    }

    private void update(int[][] grid, int i, int j) {
        int h = 1, v = 1, rd = 1, ld = 1;

        if(j < grid[i].length - 1 && grid[i][j+1] == 1) {
            if(j == 0 || grid[i][j-1] != 1) h = updateH(grid, i, j+1, h);
        }
        if(i < grid.length - 1 && grid[i+1][j] == 1) {
            if(i == 0 || grid[i-1][j] != 1) v = updateV(grid, i+1, j, v);
        }
        if(j < grid[i].length - 1 && i < grid.length - 1 && grid[i+1][j+1] == 1) {
            if(j == 0 || i == 0 || grid[i-1][j-1] != 1) rd = updateRD(grid, i+1, j+1, rd);
        }
        if(j > 0 && i < grid.length - 1 && grid[i+1][j-1] == 1) {
            if(j == grid[i].length - 1 || i == 0 || grid[i-1][j+1] != 1) ld = updateLD(grid, i+1, j-1, ld);
        }

        hmax = Math.max(h, hmax);
        vmax = Math.max(v, vmax);
        rdmax = Math.max(rd, rdmax);
        ldmax = Math.max(ld, ldmax);
    }

    private int updateH(int[][] grid, int i, int j, int h) {
        h++;
        if(j < grid[i].length - 1 && grid[i][j+1] == 1) h = updateH(grid, i, j+1, h);
        return h;
    }

    private int updateV(int[][] grid, int i, int j, int v) {
        v++;
        if(i < grid.length - 1 && grid[i+1][j] == 1) v = updateV(grid, i+1, j, v);
        return v;
    }

    private int updateRD(int[][] grid, int i, int j, int rd) {
        rd++;
        if(j < grid[i].length - 1 && i < grid.length - 1 && grid[i+1][j+1] == 1)
            rd = updateRD(grid, i+1, j+1, rd);
        return rd;
    }

    private int updateLD(int[][] grid, int i, int j, int ld) {
        ld++;
        if(j > 0 && i < grid.length - 1 && grid[i+1][j-1] == 1)
            ld = updateLD(grid, i+1, j-1, ld);
        return ld;
    }
}

My code seems to work, but I'm not sure if this is the most efficient code. Do you think this is OK? Or are there any faster/simpler implementation? (Answer in Java format preferred.)

In worst case (array that has only 1, no 0) you are doing M operations for each cell in MxM for a total of M^3 operations. You can reduce it to M^2 if you remember the results for previous row (for vertical, LD, RD) and current(horizontal). If the cell is 1 increment the counters, otherwise reset them to zero.


Peak finding algorithm This is my peak finding algorithm. I try to split the 2D array in half and find the maximum element in the middle column. After that, the algorithm will check whether there are any other element bigger than it on the left or the right side. If there is any, the matrix will slice in half depending on the position of the element and go into recursion. You can simply change the size or the elements of the matrix.

How can I improve my coding to make it more efficient or concise?

import numpy as np
matrix=np.array([[3,2,3],
    [100,55,7],
    [344,9,37]
   ])

def algo(problem):
    print('matrix =' + str(problem))
    Nrow=len(problem)
    print("row"+str(Nrow))
    for i in problem:
        Ncol=len(i)
        break
    if Nrow <=0 or Ncol<=0:
        return None
    print("col"+str(Ncol))
    mid=Ncol//2
    (substartR,subnrow)=(0,Nrow)
    (substartc1,subncol1)=(0,mid)
    (substartc2,subncol2)=(mid,Ncol-mid+1)
    subproblem=[]
    subproblem.append((substartR,substartc1,subnrow,subncol1))
    subproblem.append((substartR,substartc2,subnrow,subncol2))
    print(subproblem)

    loc=[]
    for i in range(Nrow):
        loc.append((i,mid))
    # bestloc is a tuple of location and biggest val
    bestloc=findmax(loc,problem)
    print("bestloc" + str(bestloc[0]))

    bestloc1=bestneighbour(bestloc,Nrow,Ncol,problem)
    print("bestloc1 =" + str(bestloc1))

    if bestloc[0] != bestloc1:
        print('sub problem')
        #print(problem)
        new_matrix=get_subproblem(subproblem,bestloc1,problem)
        return algo(new_matrix)
    else:
        (x,y)=bestloc1
        #print("the peak " +str( problem[x][y]))
        print( problem[x][y])

def findmax(loc,matrix):
    (bestloc,bestval)=(None,0)

    for i in loc:

      if bestloc == None or bestval < get_value(i,matrix) :
        #print(get_value(i))

          bestloc=i
          bestval= get_value(i,matrix)

    return (bestloc,bestval)

def get_value(i,matrix):

    y=i[1]
    x=i[0]

    return matrix[x][y]

def bestneighbour(i,Nrow,Ncol,matrix):

    y=i[0][1]
    x=i[0][0]
    bestval=i[1]

    inew=(x,y)
    if x-1>=0 and matrix[x-1][y]>bestval:
        inew=(x-1,y)
        bestval=matrix[x-1][y]
    if x+1<Nrow and matrix[x+1][y]>bestval:
        inew=(x+1,y)
        bestval=matrix[x+1][y]

    if y-1>=0 and matrix[x][y-1]>bestval:
        inew=(x,y-1)
        bestval=matrix[x][y-1]

    if y+1<Ncol and matrix[x][y+1]>bestval:
        inew=(x,y+1)
        bestval=matrix[x][y+1]

    return inew
def get_subproblem(sub,bestloc,matrix1):
    #global matrix
    (row,col)=bestloc
    #print(row)
    #print(col)
    for i in sub:
        print(i)
        (start_R,start_C,num_of_row,num_of_col)=i
        if start_R<=row and row<start_R+num_of_row:
            if start_C<=col and col<start_C+num_of_col:
                matrix1=matrix1[start_R:num_of_row,start_C:num_of_col+start_C]
                return matrix1

algo(matrix)

1. algo

I can see 3 areas of local improvements here:

for i in problem:
    Ncol=len(i)
    break

doing a loop to just set Ncol for the first element is really ugly. Since your list isn't empty just do:

Ncol = len(problem[0])

Now why 3 lines for this:

subproblem=[]
subproblem.append((substartR,substartc1,subnrow,subncol1))
subproblem.append((substartR,substartc2,subnrow,subncol2))

when you can create your list directly:

subproblem= [(substartR,substartc1,subnrow,subncol1),(substartR,substartc2,subnrow,subncol2)]

and last thing, learn about list comprehensions for things like this:

loc=[]
for i in range(Nrow):
    loc.append((i,mid))

that can be rewritten as

loc = [(i,mid) for i in range(Nrow)]

2. findmax / getvalue

As mentionned in comments, the indentation of return statement is off, but since the code works, I'm assuming that it's just a typo. Here:

for i in loc:
  if bestloc == None or bestval < get_value(i,matrix) :
      bestloc=i
      bestval= get_value(i,matrix)

return (bestloc,bestval)

get_value is a function created just for this method. It introduces a lot of overhead & doesn't improve readability either. Scrap it, "inline" & cache the value
set bestloc to the first value (and value is okay, but first one is the most logical choice) before the loop starts, so you don't have to test for None in the whole loop. For this we have to handle the "loc is empty" cornercase at start.

So rewrite function like:

def findmax(loc,matrix):
    if not loc:
        # get rid of the "loc is empty" case
        return (None,0)
    bestloc,bestval = loc[0]

    for i in loc:
       x,y = i  # unpack from i, no indice access
       mvalue = matrix[x][y]

       if bestval < mvalue:
          bestloc = i
          bestval = mvalue

    return (bestloc,bestval)

only one access to the matrix, no unnecessary test for None, no function calls, faster index access.

get_subproblem

Use chaining comparisons since row and col are tested twice (now you can group both conditions)
don't slice then return, return the slice

like this:

for i in sub:
    print(i)
    (start_R,start_C,num_of_row,num_of_col)=i
    if start_R <= row <start_R+num_of_row and start_C <= col <start_C+num_of_col:
        return matrix1[start_R:num_of_row,start_C:num_of_col+start_C]

if you don't care about the print you could unpack directly in loop:

for start_R,start_C,num_of_row,num_of_col in sub:


Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements.

Given 4 elements (1, 2, 3 and 4):

  |1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10

Here is my code in Java:

List<Integer> a = new ArrayList<Integer>(); //just for understanding , the Array List is already filled with numbers
public static int lsum(int N)
{
    int sum =0;

    for( int i=0;i<N;i++)
    {
        int w =a.get(i);
        for(int j =i;j<N;j++)
        {
            int z = a.get(j);
            sum =sum +(z-w);
        }

        }
    return(sum);

}

I'm looking for an efficient algorithm rather than the trivial one I am using (O(n2) complexity). This is a requirement for a bigger program which requires this function. The input (number of elements) can be as big as 105.

Let's see this mathematically. I am assuming that a is an ascendingly sorted array. I start with indexes from 1, to get better readability (by avoiding n-1 as often as possible).

We want the following sum:

$$\begin{array}{l@{}l@{}l@{}l}
\sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_j - a_i) = (a_2 - a_1) &+ (a_3 - a_1) &+ (a_4 - a_1) + & \dots + (a_n - a_1) +\\
                    &+ (a_3 - a_2) &+ (a_4 - a_2) + & \dots + (a_n - a_2) +\\
                                &&+ (a_4 - a_3) + & \dots + (a_n - a_3) +\\
                                            &&& \dots
\end{array}$$

So, we:

add a1 zero times, a2 once,... ak k-1 times, and
subtract a1 n-1 times, a2 n-2 times,... ak n-k times.

I'd say that your sum is

$$
\sum_{k=1}^n (k-1)a_k - \sum_{k=1}^n (n-k)a_k = \sum_{k=1}^n (2k-n-1)a_k
$$

Given your example (1,2,3,4), we get:

$$
\sum_{k=1}^4 (2k-4-1)a_k = -3 \cdot 1 + (-1 \cdot 2) + 1 \cdot 3 + 3 \cdot 4 = -3 - 2 + 3 + 12 = 10.
$$

This has a linear complexity, which is optimal, because you need to "visit" each member of the array at least once (which is linear).

I believe you can write your code by yourself. Just set indexes to go from zero, but be careful about the formula: 2k - n - 1 becomes 2k - n + 1 when k starts from zero.


Finding occurrence of a given character in a String? I came up with this simple solution:

public class Main {

  /**
   * How to count occurrence of a given character in a String?
   */

  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    if (!in.hasNextLine()) {
      System.out.println("You must enter a string!");
    }

    String givenString = in.nextLine();

    char givenChar = in.next().charAt(0);

    int occurance = occuranceOfChar(givenString, givenChar);

    System.out.println(givenChar + " occured " + occurance + " times!");
  }

  private static int occuranceOfChar(String givenString, char givenChar) {

    int sum = 0;

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

      char charAtI = givenString.charAt(i);

      if (charAtI == givenChar) sum++;
    }

    return sum;
  }
}

Are there any bad practices here?

Your program doesn't print a prompt to the user and I couldn't make it output the warning to enter a string. I have made a few basic changes. The actual counting is done in a very basic but robust way

public class Main {

    /**
     * How to count occurrence of a given character in a String?
     */

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        System.out.println("Please enter a string to search");

        String givenString = in.nextLine();

        System.out.println("Please enter the character to search for");
        char givenChar = in.next().charAt(0);

        int occurance = occuranceOfChar(givenString, givenChar);

        System.out.println(givenChar + " occured " + occurance + " times!");
    }

    private static int occuranceOfChar(String givenString, char givenChar){

        int sum = 0;

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

            char charAtI = givenString.charAt(i);

            if (charAtI == givenChar) sum++;
        }

        return sum;
    }
}


Extracting nodes from a graph database I'm new to Postgres and PostGIS, but not to geospatial applications.

I have a table loaded up with graph data in the form of links (edges). The link database has about 60,000,000 rows. I am trying to extract the nodes to allow for quicker searching. For some of my proof-of-concept work I was able to use the link table for the searches, but there will be lots of duplicates, and there's no guarantee that either the source column or the target column contains all nodes.

This is Postgres & PostGIS, so I am also using the table to cache a geometry->geography conversion. Yes I do need to use geography fields. I'm also copying the geometry information "just in case".

Table creation SQL:

-- Recreate table and index
DROP TABLE IF EXISTS nodes;

CREATE TABLE nodes (node integer PRIMARY KEY, geog geography(POINT,4326) );

CREATE INDEX geogIndex ON nodes USING GIST(geog);

SELECT AddGeometryColumn('nodes', 'geom', 4326, 'POINT', 2);

-- Insert all unique nodes from the source column
INSERT INTO nodes (node,geog,geom)
       SELECT DISTINCT ON (source) source,geography( ST_Transform(geom_source,4326)),geom_source
       FROM view_topo;

-- Insert any nodes in the target column that we don't have already
INSERT INTO nodes (node,geog,geom)
       SELECT DISTINCT ON (target) target,geography( ST_Transform(geom_target,4326)),geom_target
       FROM view_topo
       WHERE NOT EXISTS( SELECT 1 FROM nodes WHERE nodes.node = view_topo.target);

VACUUM ANALYZE;

I left the first INSERT running overnight and it took about 2-3hrs to run. This resulted in about 40,000,000 unique nodes being added.

I have just enabled the second INSERT and the VACUUM ANALYZE. I am expecting it to take until at least lunchtime.

Luckily this is only a batch job that has to be executed once after I've loaded a new link table, but is there a better way? Is there a faster way?

Check out PostgreSQL's tips on adding a lot of data into a table. In particular, are you sure that you need that index before INSERTing all that data? It might speed things up if you create the index after all the data has been added to the table.


Count contiguous sub-array whose sum is a perfect square I have to count the number of contiguous sub-arrays whose sum is a perfect square.

For instance, if we have an array:

number = [1,4,2,3,5]

Now the contiguous sub-arrays whose elements sum is a perfect square are:

[1] [4] [4,2,3]

Total count = 3

To solve this problem I took an array which stores the prefix sum and then I run two loops to get the answer:

int array[] = new int[n + 1];
int prefixSum[] = new int[n + 1];
int count = 0;
for (int index = 1; index <= n; index++) {
    array[index] = in.nextInt();
    prefixSum[index] = (prefixSum[index-1]+array[index]);
    count +=isPerfectSquare(prefixSum[index])?1:0;
}
for (int prev = 1; prev <= n; prev++) {
    for (int index = prev+1; index <= n; index++) {
        count += isPerfectSquare(prefixSum[index]-prefixSum[prev]) ? 1 : 0;
    }
}
System.out.println("count = " + count);

How can I improve this in terms of complexity?

You don't really use array[].  You store a value in array[index], and then immediately read the value back out, and then never use that value again.  This results in unnecessary memory cycles.

    array[index] = in.nextInt();
    prefixSum[index] = (prefixSum[index-1]+array[index]);

You could replace this with a temporary variable, and remove the array.

    int element = in.nextInt();
    prefixSum[index] = prefixSum[index-1] + element;

As a minor efficiency boost, instead of adding the element to the prefixSum[index-1], which involves an array lookup (another memory cycle), you could keep the running total in a local variable.

int running_total = 0;
for (int index = 1; index <= n; index++) {
    int element = in.nextInt();
    running_total += element;
    prefixSum[index] = running_total;
    ...

You have two different ways of counting the sub-arrays that sum to a perfect square:

count += isPerfectSquare(prefixSum[index]                ) ? 1 : 0;
count += isPerfectSquare(prefixSum[index]-prefixSum[prev]) ? 1 : 0;

The first is used when you are counting from the beginning of the list, the second when you start by excluding one or more elements from the beginning.

You could make the first method look more like the second, by adding a subtraction of 0:

count += isPerfectSquare(prefixSum[index]-      0        ) ? 1 : 0;

By design (or is it by coincidence?), prefixSum[0] actually contains the value 0.

count += isPerfectSquare(prefixSum[index]-prefixSum[ 0  ]) ? 1 : 0;

So if your second loop started with for (int prev = 0; instead of for (int prev = 1;, you could remove your first counting statement completely.

Your outer nested loop runs one more time that necessary.  It runs while prev <= n, where the inner loop starts at index = prev+1 and runs while index <= n.  On the last iteration of the outer loop, prev == n, so index starts at index = n+1 and of course index <= n is immediately false, so the inner loop doesn't run at all, which makes this last iteration of the outer loop pointless.  You could use prev < n as the loop condition.

The count += isPerfectSquare(...) ? 1 : 0; ternary operation isn't saving you much, and could be costing you some performance.  The ternary operation is an if ... then ... else ... statement, and the else part is count += 0, which is a no-op.  The following is clearer, and might even be faster.

        if (isPerfectSquare(...)) {
            count++;
        }

Improved code:

int prefixSum[] = new int[n + 1];
int count = 0;
int running_total = 0
for (int index = 1; index <= n; index++) {
    int element = in.nextInt();
    running_total += element;
    prefixSum[index] = running_total;
}
for (int prev = 0; prev < n; prev++) {
    for (int index = prev+1; index <= n; index++) {
        if (isPerfectSquare(prefixSum[index] - prefixSum[prev])) {
            count++;
        }
    }
}
System.out.println("count = " + count);


Character Sprint Spaghetti Code I finally managed to get the code to work properly. It makes the player object move faster if the user double taps the arrow key with a few 'ticks' (new frames) after the 1st stroke. - User presses and has a limited time to press again to sprint the object. If the time runs out the user has to try again.

However, It'd be better I believe to be working with time, miliseconds and not 'ticks', as what I intend involves lots of key combinations that have x seconds to be pressed.

I would like to know the redundancies in the code, what can be made into a class and something better then screen refresh to time things up (delays?).

package
{

import flash.display.Sprite;
import flash.display.Graphics;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.ui.Keyboard;
import flash.events.KeyboardEvent;

public class Main extends Sprite {
var keys:Array = [];
var player:Sprite = new Sprite();
var sprint, condition1, condition2, timerStart, keyUp, keyDown:Boolean;
var timer:int;

public function Main():void {

player.graphics.beginFill(0x000000);
player.graphics.drawCircle(0, 0, 25);
player.graphics.endFill;

addChild(player);
player.x = 100;
player.y = 250;

player.addEventListener(Event.ENTER_FRAME, update);
stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown);
stage.addEventListener(KeyboardEvent.KEY_UP, onKeyUp);
}

function update(e:Event):void {

  if ((timerStart)&&(timer>0)) {
    timer --;
    condition1 = true;
  }

  if (keyUp) {
    if ((condition1) && (timer > 0)) {
       condition2 = true;
    }

    if (sprint) {
      timerStart = false;
      condition1 = false;
      condition2 = false;
      sprint = false;
      timer = 7;
    }

    if (timer <= 0) {
      timerStart = false;
      condition1 = false;
      condition2 = false;
      sprint = false;
      timer = 7;
    }
}

if (keys[Keyboard.RIGHT]) {
timerStart = true;

if ((condition1) && (condition2)) {
sprint = true;
}

if (sprint) {
player.x += 7;
} else player.x += 2;
            }

function onKeyDown(e:KeyboardEvent):void {
keys[e.keyCode] = true;
keyUp = false;
keyDown = true;
}

function onKeyUp(e:KeyboardEvent):void {
keys[e.keyCode] = false;
keyUp = true;
keyDown = false;
}

} // class
} // package

From a once over

Indentation is terrible, consider using a tool like jsbeautifier.org, it works for ActionScript as well
Keep working with Event.ENTER_FRAME <- It is the better approach in my mind
Always be on the look out for copy pasted code, this:

if (sprint) {
  timerStart = false;
  condition1 = false;
  condition2 = false;
  sprint = false;
  timer = 7;
}

if (timer <= 0) {
  timerStart = false;
  condition1 = false;
  condition2 = false;
  sprint = false;
  timer = 7;
}

could be

    if (sprint || timer <= 0) {
      timerStart = false;
      condition1 = false;
      condition2 = false;
      sprint = false;
      timer = 7;
    }

Do not track keyDown, you do not use it, and it's value is always the opposite of keyUp
condition1 and condition2 are very unfortunate names, you should try to be more descriptive
This code could use some well named constants and indenting:

if (sprint) {
player.x += 7;
} else player.x += 2;

I would rather see

var FAST_SPEED = 7,
    NORMAL_SPEED = 2;
if (isSprinting) {
    player.x += FAST_SPEED;
} else {
    player.x += NORMAL_SPEED;
}

or if I wanted to be fancy

player.x += isSprinting ? FAST_SPEED : NORMAL_SPEED;


52-Line Logging System I wanted to make an extremely light-weight logging system. What are your thoughts on this and what can be done to improve it?
First, the usage:
int main( )
{
    logging::level = logging::fatal | logging::warning;
    mini_log( logging::fatal, "entry point", "nothing", " is ", "happening!" );
}

Now, the code:
#if defined( NDEBUG )
#define mini_log( ... ) static_cast< void >( 0 )
#else
namespace logging
{
    enum level_t
    {
        none = 0b00000,
        information = 0b00001,
        debug = 0b00010,
        warning = 0b00100,
        error = 0b01000,
        fatal = 0b10000,
        all = 0b11111
    } inline level = all; // level should only be used in the entry point
    inline std::mutex stream;
}
#define mini_log \
    [ ]( logging::level_t const level_message, \
         std::string_view const location, \
         auto &&... message ) -> void \
    { \
        std::lock_guard< std::mutex > lock_stream( logging::stream ); \
        struct tm buf; \
        auto time = [ & ]( ) \
        { \
            auto t = std::time( nullptr ); \
            localtime_s( &buf, \
                         &t ); \
            return std::put_time( &buf, \
                                  "[%H:%M:%S]" ); \
        }; \
        auto level = [ = ]( ) -> std::string \
        { \
            switch( level_message ) \
            { \
                case logging::information: \
                    return " [" __FILE__ "@" stringize_val( __LINE__ ) "] [Info] ["; \
                case logging::debug: \
                    return " [" __FILE__ "@" stringize_val( __LINE__ ) "] [Dbug] ["; \
                case logging::warning: \
                    return " [" __FILE__ "@" stringize_val( __LINE__ ) "] [Warn] ["; \
                case logging::error: \
                    return " [" __FILE__ "@" stringize_val( __LINE__ ) "] [Erro] ["; \
                case logging::fatal: \
                    return " [" __FILE__ "@" stringize_val( __LINE__ ) "] [Fatl] ["; \
            } \
        }; \
        if( level_message & logging::level ) \
            ( ( std::cout << time( ) << level( ) << location << "]: " << message ) << ... ) << '\n'; \
    }
#endif

Macros
Most of your code is in a macro. This makes it harder to write, read and debug.
Why not place the logic in normal functions and only use macros to pass __FILE__ and __LINE__?
That is until you can switch to C++20 which provides std::source_location
Naming
Why is the mutex called stream?


Generating random permutation with forced change of order (Secret Santa) I wrote this function to generate random permutation of input vector, while making sure every element has switched place (for a Secret Santa like purpose).
std::map<std::string, std::string> getPermutation(const std::vector<std::string>& participants)
{
  auto permuted = participants;
  std::random_device rd;
  std::mt19937 g(rd());
  bool correctlyPermuted = false;
  while(!correctlyPermuted)
  {
    std::shuffle(permuted.begin(), permuted.end(), g);
    auto res = std::mismatch(participants.begin(), participants.end(), permuted.begin(), std::not_equal_to{});
    if(res.first == participants.end())
    {
      correctlyPermuted = true;
    }
  }

  std::map<std::string, std::string> result;
  for(int i = 0; i < participants.size(); ++i)
  {
    result[participants[i]] = permuted[i];
  }
  return result;
}

You can run code here. Note that's still work in progress, I'm mostly concerned about the function above.
participants is guaranteed to contain no duplicate elements.
I'm not really concerned with speed - it's supposed to be executed by humans, they are unlikely to notice any performance improvement. Of course, you are welcome to point any obvious performance issues.
However, I'm concerned with the readability of the function, particularly with the use of std::mismatch to find actually matching elements. It feels too clever, but maybe it's just good use of functional programming and I'm overthinking? It also seems too long for a good function (22 lines), but I can't think of how it could be splitted/shortened logically.

I would suggest breaking the actual permutation algorithm out into its own function, since it’s useful on its own. That would pretty much solve the readability problem.
And then I would suggest doing the permutation with indices, rather than copying the whole input vector. (Indices would also work for other range types, especially if you limit the input range type to random-access, which is not unreasonable for a sorting algorithm.) Once you’re dealing with indices, detecting positions that are unchanged is trivial, and quick:
template <std::sized_range Rng, typename Gen>
requires std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
auto get_fully_permuted_indices(Rng const& rng, Gen&& gen)
{
    auto idxs = std::vector<std::size_t>(std::ranges::size(rng));
    std::iota(idxs.begin(), idxs.end(), std::size_t(0));

    auto permuted = false;
    do
    {
        std::ranges::shuffle(idxs, gen);

        permuted = true; // hope for the best!
        for (auto i = std::size_t(0); i < res.size(); ++i)
        {
            // if the value at i is the same as i, then this is not properly permuted
            if (i == idxs[i])
            {
                permuted = false;
                break;
            }
        }
    } while (not permuted);

    return idxs;
}

Once you have that, your main function is trivial:
std::map<std::string, std::string> getPermutation(const std::vector<std::string>& participants)
{
    auto const idxs = get_fully_permuted_indices(participants, std::mt19937{std::random_device(){}});

    auto res = std::map<std::string, std::string>{};
    for (auto i = std::size_t(0); i < std::ranges::size(participants); ++i)
        res.emplace(participants[i], participants[idxs[i]]);

    return res;
}

I would also suggest moving the creation of the RNG out of the function, and passing the RNG in as an argument:
template <typename Gen>
requires std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
auto getPermutation(const std::vector<std::string>& participants, Gen&& gen)
{
    auto const idxs = get_fully_permuted_indices(participants, std::forward<Gen>(gen));

    auto res = std::map<std::string, std::string>{};
    for (auto i = std::size_t(0); i < std::ranges::size(participants); ++i)
        res.emplace(participants[i], participants[idxs[i]]);

    return res;
}

This goes with the doctrine of “one function, one job”, and allows both reusing the RNG, and testing the function with a known RNG.
If you want to go even further, an “is-fully-permuted-indices” algorithm, to remove that for loop in get_fully_permuted_indices(), also seems useful:
template <std::input_range Rng>
requires std::equality_comparable_with<std::ranges::range_value_t<Rng>, std::size_t>
constexpr auto is_fully_permuted_indices(Rng const& rng)
{
    auto idx = std::size_t(0);
    for (auto&& item : rng)
    {
        if (item == idx++)
            return false;
    }

    return true;
}

template <std::sized_range Rng, typename Gen>
requires std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
auto get_fully_permuted_indices(Rng const& rng, Gen&& gen)
{
    auto idxs = std::vector<std::size_t>(std::ranges::size(rng));
    std::iota(idxs.begin(), idxs.end(), std::size_t(0));

    do
    {
        std::ranges::shuffle(idxs, gen);
    } while (not is_fully_permuted_indices(idxs));

    return idxs;
}


Serving static assets through wildcard rule I wrote this as a way to deliver static portion of the app.  I'm wondering if there is a better way to write this, as I am new to Express.

The goal is to let a single-page app to handle routing as needed. There is an API layer of this app that is defined under the /api/ route namespace.

I wanted to note that all assets are served from /app folder and are not public. I can adjust that, but as of now, that's the folder structure. /app is a compilation destination. root folder contains server.js where the below code resides and contains app/ and src/ folders, as well as server/ folder that contains API related stuff.

var express = require('express');
var http = require('http');
var path = require('path');
var app = express();

require('./express/api')(app);

app.get("/css/*",function(req,res){
  res.sendfile('app'+req.path);
});
app.get("/js/*",function(req,res){
  res.sendfile('app'+req.path);
});
app.get("/img/*",function(req,res){
  res.sendfile('app'+req.path);
});
app.get("/pages/*",function(req,res){
  res.sendfile('app'+req.path);
});
app.get('*',function(req,res){
  res.sendfile('app/index.html');
});

app.listen(3000);
console.log('Listening on port 3000');

There is a better way.

If you wish to serve static files with express - it comes bundled with static middleware. To use it, you simply add this line before your routes:

app.use(express.static(__dirname + '/public'));

This may require slight adjustment to your paths but it replaces all those manual routes and is more efficient (caching, expiration etc).

Check out this example.

I would, however, suggest that you use something like nginx for your static assets since it's typically more robust and it'll free resources from your node server.


"Rock Paper Scissors Game" Java What can make this code better?
And how could I improve this code?
Oh and what I would love is if someone has a project that is not that
challenging but I could learn a lot from it :)

import java.util.Scanner;

public class RockPaperScissors {
    final static int ROCK = 1;
    final static int PAPER = 2;
    final static int SCISSORS = 3;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Start By Entering A number");
        int human = input.nextInt();
        System.out.println("ROCK IS 1 :: PAPER IS 2 :: SCISSORS 3");
        int computerScore = 0, humanScore = 0, computer;
        while (human != -1) {
            human = input.nextInt();
            computer = (int) (Math.random() * 3 + 1);
            String h = human == 1 ? "ROCK" : human == 2 ? "PAPER" : "SCISSORS";
            String c = computer == 1 ? "ROCK" : computer == 2 ? "PAPER" : "SCISSORS";
            if ((human == ROCK && computer == SCISSORS) || (human == PAPER && computer == ROCK) || (human == SCISSORS && computer == PAPER)) {
                humanScore++;
                System.out.println("Human Won : " + humanScore);
                System.out.println("Human Chose " + h + " and Computer Chose " + c);
            } else if ((computer == ROCK && human == SCISSORS) || (computer == PAPER && human == ROCK) || (computer == SCISSORS && human == PAPER)) {
                computerScore++;
                System.out.println("Computer Won : " + computerScore);
                System.out.println("Human Chose " + h + " and Computer Chose " + c);
            } else if (human == computer) {
                System.out.println("HAH YOU BOTH THINK THE SAME! ");
                System.out.println("DRAW!");
            } else {
                System.out.println("Something Went Wrong Try Again:( ");
            }
        }
        System.out.println("\n\nThe Scores Are *DRUM NOISES* ");
        for (int i = 0; i < 4; i++) {
            System.out.println("------------------------------");
        }
        System.out.println("Human score : " + humanScore);
        System.out.println("Computer score : " + computerScore);
        if (humanScore > computerScore) {
            System.out.println("Human Race Is saved! We Won!");
        } else if (computerScore > humanScore) {
            System.out.println("Sadly We Lost. Better Luck Next Time:)");
        } else {
            System.out.println("Scores are Tied");
        }
    }
}

This is a reasonable first attempt but there are many ways to make it better:

public class RockPaperScissors {
    final static int ROCK = 1;
    final static int PAPER = 2;
    final static int SCISSORS = 3;

Consider using an enumerated type to hold related constants.

System.out.println("Start By Entering A number");

Your capitalization is not standard English.
Tell the user how to quit.

int human = input.nextInt();
System.out.println("ROCK IS 1 :: PAPER IS 2 :: SCISSORS 3");

Put the explanation before fetching input!
Why is there no "is" for the scissors case?

int computerScore = 0, humanScore = 0, computer;
while (human != -1) {

Consider refactoring the main method so that it more clearly reflects what is happening, and extracting state to an object.  I'd prefer to see your main look like this:

public static void main(String[] args) {
    initialize();
    Game g = new Game();
    g.printStartingText();
    while(!g.finished())
      g.playRound();
    g.printEndText();
}

Can you structure your program like that? It will be more clear if you do.

        String h = human == 1 ? "ROCK" : human == 2 ? "PAPER" : "SCISSORS";
        String c = computer == 1 ? "ROCK" : computer == 2 ? "PAPER" : "SCISSORS";

You've replicated some code here; it would be better to make a map from integer to the enumerated value and do two lookups in the map here.

    if ((human == ROCK && computer == SCISSORS) || (human == PAPER && computer == ROCK) || (human == SCISSORS && computer == PAPER)) {

Instead of doing this work twice, write a method that returns PLAYER_1, PLAYER_2 or TIE:

    Winner w = getWinner(human, computer);

That will let you simplify the logic that follows, and it will be easier to read.

            System.out.println("Something Went Wrong Try Again:( ");

This should never happen. A better choice would be to assert that the condition is impossible.

    System.out.println("Human Race Is saved! We Won!");

Why are the humans "we"? The message is being produced by a computer! It should be "The human race is saved; you won and we computers lost." :)


Kotlin Stack using an ArrayList to compare and remove elements Is this a performant strategy to implement a stack in Kotlin to compare and delete values?
Expect
Create a stack in order to compare an array of asteroids (ASTs) and handle collisions (deletions), returning the final array of ASTs after collisions.

Each AST moves at the same speed
Negative numbers move left, positive numbers move right
Smaller ASTs explode (are deleted), the same size both explode, and same direction ASTs do nothing

See: LeetCode
Example 1:
Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.

ArrayList Stack Strategy
Create a stack using an ArrayList to compare asteroid (AST) direction, values, and remove ASTs.
The solution performs as expected in terms of achieving the correct results. However, I'm looking to improve speed and memory performance.
See: GitHub repository

Build ArrayList used as a stack and add the AST values to the stack
Start curIndex at the top of the stack and check the stack until curIndex is at the second element of the stack, thus checking for all possible AST collisions.
Using the current cur and previous prev values, check whether a collision will occur. A collision occurs when prev is positive and cur is negative.
Given a collision with ASTs with equal value, remove both ASTs. If the curIndex is not at the end of the stack after removing ASTs, continue to check for right-most collisions by decrementing curIndex--. Otherwise, fully decrement curIndex-=2
Given a collision with one AST with a larger value, remove the smaller AST. Only decrement when curIndex is at the end of the stack.
If there are no collisions, decrement the stack curIndex--.

Implement
fun asteroidCollision(asteroids: IntArray): IntArray {
    val stack = ArrayList<Int>()
    for (a in asteroids) stack.add(a)
    var curIndex = stack.size - 1
    while (curIndex >= 1) {
        val cur = stack.get(curIndex)
        val prev = stack.get(curIndex - 1)
        if (prev.isRight() && cur.isLeft()) {
            if (Math.abs(cur) == Math.abs(prev)) {
                stack.removeAt(curIndex)
                stack.removeAt(curIndex - 1)
                if (curIndex - 2 == stack.size - 1)
                    curIndex -= 2
                else curIndex--
            } else if (Math.abs(prev) > Math.abs(cur)) {
                stack.removeAt(curIndex)
                if (curIndex - 1 == stack.size - 1)
                    curIndex--
            } else {
                stack.removeAt(curIndex - 1)
                curIndex--
            }
        } else curIndex--
    }
    return stack.toIntArray()
}

fun Int.isLeft() = this < 0
fun Int.isRight() = this > 0

Potential improvement
This seems like it could be a potential improvement. However, it still requires creating a new data structure vs. working with the original array and requires converting the data structure back into an array to return the results.

Build a double LinkedList class.
Pass in one element at a time.
Check the top/last element to see if it collides with the previous element.
Continue to check previous elements after all of the original elements are added.

An array to list can be done by the function toList().
list.size-1 is an existing property on a list called lastIndex.
'Math.abs' is from Java. Kotlin has its own abs, which isn't prefixed by a class.
List provides an operator function to access by index:
stack.get(curIndex) can be written as stack[curIndex]
fun asteroidCollision(asteroids: IntArray): IntArray {
    val stack = asteroids.toMutableList()
    var curIndex = stack.lastIndex
    while (curIndex >= 1) {
        val cur = stack[curIndex]
        val prev = stack[curIndex - 1]
        if (prev.isRight() && cur.isLeft()) {
            if (abs(cur) == abs(prev)) {
                stack.removeAt(curIndex)
                stack.removeAt(curIndex - 1)
                if (curIndex - 2 == stack.lastIndex)
                    curIndex -= 2
                else curIndex--
            } else if (abs(prev) > abs(cur)) {
                stack.removeAt(curIndex)
                if (curIndex - 1 == stack.lastIndex)
                    curIndex--
            } else {
                stack.removeAt(curIndex - 1)
                curIndex--
            }
        } else curIndex--
    }
    return stack.toIntArray()
}

flow
The if-else if-else chain can be reduced to two if-statements.
This is because the case where the absolute value of cur and prev are the same is just the other two cases combined.
As far as I know, you do need more variables, to make it possible.
Therefor, this is just another choice, with its own drawbacks:
fun asteroidCollision(asteroids: IntArray): IntArray {
    val stack = asteroids.toMutableList()
    var index = stack.lastIndex
    while (index >= 1) {
        val curIndex = index
        val cur = stack[curIndex]
        val prevIndex = index-1
        val prev = stack[prevIndex]
        if (prev.isRight() && cur.isLeft()) {
            if (abs(prev) >= abs(cur)){
                stack.removeAt(curIndex)
                if (index-1==stack.lastIndex)
                    index--
            }
            if (abs(cur) <= abs(prev)){
                stack.removeAt(prevIndex)
                index--
            }
        } else index--
    }
    return stack.toIntArray()
}


Min heap without recursion The code reads in integer array from user input and builds a minimum heap via an iterative scheme.
Are there any edge cases in which this approach would fail?
For the following test case/command sequence:
1 4 3 10 12 6 -1
remove
remove
print

My output is 4 6 10 12 instead of 4 10 6 12, is this an invalid implementation?
#include <iostream>
#include <string>
#include <sstream>
#include <stdexcept>
#include <cmath>

int readheap(int* theheap) {
    std::string num;
    int val = 0;
    int size = 0;
    std::cout << "Enter the elements of heap" << std::endl;
    std::getline(std::cin, num);
    std::istringstream iss(num);
    while (iss >> val) {
        if (val != ' ' && val > 0){
            theheap[size] = val;
            ++size;
        }
    }
    if(size <= 1) {
        throw std::runtime_error("Invalid user input");
    }

for (int k = 1; k < size; ++k) {

        if (theheap[k] > theheap[(k - 1) / 2])  {
            int j = k;

            while (theheap[j] > theheap[(j - 1) / 2])  {
                std::swap(theheap[j], theheap[(j - 1) / 2]);
                j = (j - 1) / 2;
            }
        }
    }
    for (int k = size - 1; k > 0; --k) {
        std::swap(theheap[0], theheap[k]);

        int j = 0, index;

        do {
            index = (2 * j + 1);

            if (theheap[index] < theheap[index + 1] && index < (k - 1))
                ++index;

            if (theheap[j] < theheap[index] && index < k)
                std::swap(theheap[j], theheap[index]);

            j = index;

        } while (index < k);
    }
    std::cout << "Size of heap is " << size << '\n';
    return size;
}

void heapRemove(int* theheap, int& size) {
    for(int i=0; i<size-1; ++i){
        theheap[i] = theheap[i+1];
    }
    int* x = theheap;
    x = nullptr;
    delete x;
    size--;
    for (int k = 1; k < size; ++k) {

        if (theheap[k] > theheap[(k - 1) / 2])  {
            int j = k;

            while (theheap[j] > theheap[(j - 1) / 2])  {
                std::swap(theheap[j], theheap[(j - 1) / 2]);
                j = (j - 1) / 2;
            }
        }
    }
    for (int k = size - 1; k > 0; --k) {
        std::swap(theheap[0], theheap[k]);

        int j = 0, index;

        do {
            index = (2 * j + 1);

            if (theheap[index] < theheap[index + 1] && index < (k - 1))
                ++index;

            if (theheap[j] < theheap[index] && index < k)
                std::swap(theheap[j], theheap[index]);

            j = index;

        } while (index < k);
    }
}

void heapPrint(int* theheap, int size) {
    for (int i = 0; i < size; ++i){
        std::cout << theheap[i] << ' ';
    }
    std::cout << '\n';
}

int main() {
    int* theheap = new int[10];
    int size = readheap(theheap);
    heapPrint(theheap, size);
    heapRemove(theheap, size);
    heapPrint(theheap, size);
    std::cout << size << std::endl;
    return 0;
}

Memory over-runs

readheap is non-size-aware, so it's wide open to an overrun error (or even a deliberate overrun attack). Pass in a size, or use a sized data structure like a vector.

Indentation

You should fix it up for this line:

for (int k = 1; k < size; ++k) {

Order-of-operations

Neither of these expressions need parentheses:

index = (2 * j + 1);

index < (k - 1)

Deleting a null?

x = nullptr;
delete x;

Does that actually run without crashing?

Const arguments

void heapPrint(int* theheap, int size) {

should be

void heapPrint(const int *theheap, int size) {


Two inputs, two buttons to set variables to input - with .each(); What it does is simple: the user inputs a from- and a to-value in a field, sets it with ok. With the go-button, the user makes the program count from f to t and adds it to the site. With delete, the user clears the added markup.

I feel I could simplify the two set-functions into one, but I'm quite stuck.

$(document).ready(function(){

    var f, t

    $("#setfrom").click(function(){

        f = parseInt($("#from").val());

        if (isNaN(f)) {
            $("#test").append("
You said you needed numbers, right
");
        } else {$("#test").append("
" + f + "
");
        }
    });

    $("#setto").click(function(){

        t = parseInt($("#to").val());

        if (isNaN(t)) {
            $("#test").append("
You said you needed numbers, right
");
        } else {
            $("#test").append("
" + t + "
");
        }
   });

    $("#count").click(function(){

        $("#num").append("
Okay, here they come:
");

        for (i=f; i<=t; i++) {

            $("#num").append("
" + i + "</div)");
        }
    });

    $("#delnum").click(function(){
    $("#num").empty();
    $("#test").empty();
});

});

Hi, need numbers?

Yes, from

    <input type="text" id="from"></input>
    <button id="setfrom" class="button">OK</button>

to

    <input type="text" id="to"></input>
    <button id="setto" class="button">OK</button>

    <button id="count" class="button">go!</button>
    <button id="delnum" class="button">delete!</button>

Just regarding your question of how to simplify the two set-functions to one, you can merge them in one function which reacts on clicks on both buttons and behaves different depending on the button which has been clicked.

This could look like this:

$("#setfrom, #setto").click(function(event){
    var value;
    if (event.target.id == "setfrom") {
        value = parseInt($('#from').val());
        f = value;
    } else {
        value = parseInt($('#to').val());
        t = value;
    }

    if (isNaN(value)) {
        $("#test").append("
You said you needed numbers, right
");
    } else {
        $("#test").append("
" + value + "
");
    }
});

To explain what has changed here, it is important to understand what is happening in the code.

$("#setfrom, #setto") selects all elements which have either "setfrom" or "setto" as the id (look for "id=" in your html code), those are the two buttons.

The next part .click(function(event) { says that the following code should be executed each time that one of these elements is clicked. event is automatically filled by jQuery to contain information about the click of the user. For example event.target contains the concrete element which has been clicked, in this case always one of the two buttons.

We use this to find out, which of the buttons was clicked by the user and read the value from the depending input field (again selected using the $("#something") syntax explained before).

We store the value in two variables:

value is used to check if the value is a number and to output either the error or the number
f or t (depending on which button was clicked) is (as in your code) stored for later counting from f to t

With broader changes you could avoid the need for the user to click the "OK" buttons by just reading the values whenever the "go!" button is clicked.

This will change the behavior of the formular, but I think it will help you to understand how you can further simplify your code.

To do so you can eliminiate the above function and put the relevant code inside the click handler for the "#count" button:

$("#count").click(function(){

    var from = parseInt($("#from").val());
    var to = parseInt($("#to").val());

    if (isNaN(from) || isNaN(to)) {
        $("#test").append("
You said you needed numbers, right
");
        return
    }

    $("#num").append("
Counting from " + from + " until " + to + "
");
    for (i=from; i<=to; i++) {

        $("#num").append("
" + i + "</div)");
    }
});

Whenever the button with the id "count" is clicked, the following happens:

The values of the two input fields are read and written to variables from and to. If one of these values is not a number, an error message is printed and the flow is aborted using the return statement.

Otherwise a message is printed showing the user the start and the end of the row to be printed. After that the count is done.

For sure the code and the functionality could be further improved, but I will leave that to you. Just some hints what could be your next steps to improve this code:

Not always appending the output, but replacing old output and thus avoiding the user to need to click the "delete!" button
Extracting the duplicate code of reading values from input fields using functions

For the style of your code, I would recommend a few points:

Make sure that every new command is on a new line. Putting multiple things in one line will make it a lot harder to find out what what is happening while reading your code. In most cases you will spend more time reading your code than writing it, thus readability is very important. This applies even for control structures and commands like this line in your code: } else {$("#test").append("
" + f + "
");
As already said in the comments (and afterwards heavily improved by you): Look for correct indentation of your code. The three lines following $("#delnum").click(function() { should each be indented one (more) level. This would make it even easier to see that those lines are somehow depending on this line.
Do give your variables a speaking name. E.g. f and t could be renamed to from and to. Even in a small program like this one that helps to understand what each variable means. Keep in mind that others might want/need to understand your code - including yourself in a later point of time, when you are not completely aware of what you did there anymore.


Weighted dice with n faces Here you find some code that returns the value of a multivariate Bernoulli density function - for a dice with n faces, where each face has its weight (weight must be positive reals, not necessarily sum = 1) it provides the result of the tossing.

function face = weighted_dice(faces, weight)
    % face = dice(faces, weight)
    % input: row vector. Faces and weight of the same dimension!
    % output: face is the discrete face after tossing a virtual dice with given
    % faces and weight.
    if size(faces, 2) ~= size(weight, 2) || size(weight, 2)<= 1
        error('Input of function dice not well defined. See help')
    end

    num_weight = size(weight, 2);
    % weight = [w1,w2,w3, .. ,w_n]
    % cumulative_weight = [0, w1, w1+w2, w1+w2+w3, ... , sum(weight)]

    cumulative_weight = zeros(1, num_weight + 1);
    for j=1:num_weight
       cumulative_weight(j+1) = sum(weight(1:j));
    end

    % pick a random value unif. distrib. betw. 0 and the sum of the weights.
    rand_w = unifrnd(0, cumulative_weight(end));
    % check in which interval of the cumulative_weight is this element
    for j=1:num_weight
       if rand_w >= cumulative_weight(j) && rand_w < cumulative_weight(j+1)
           break
       end
    end

    % assign the interval found to the value of the face
    face = faces(j);

E.g.

disp(weighted_dice(['a','b','c','d','e','f'], [0.1, 0.1, 0.5, 0.1, 0.1, 0.1]))

beans = zeros(1,6);
for i=1:1000
    val = weighted_dice(['a','b','c','d','e','f'], [0.1, 0.1, 0.5, 0.1, 0.1, 0.1]);
    if val == 'a'
        beans(1,1) = beans(1,1) + 1;
    elseif val == 'b'
        beans(1,2) = beans(1,2) + 1;
    elseif val == 'c'
        beans(1,3) = beans(1,3) + 1;
    elseif val == 'd'
        beans(1,4) = beans(1,4) + 1;
    elseif val == 'e'
        beans(1,5) = beans(1,5) + 1;
    elseif val == 'f'
        beans(1,6) = beans(1,6) + 1;
    end
end

disp(beans)

Any idea how to vectorise the two for-cycle in the function?

If you're trying to speed up the code, I would do a couple of things.  You have some redundant processing, such as this:

cumulative_weight = zeros(1, num_weight + 1);
for j=1:num_weight
   cumulative_weight(j+1) = sum(weight(1:j));
end

which is performed 1000 times inside weighted_dice, but you really only need to do it once.  I would also get rid of the face labels altogether, because you don't care what the 6 faces are called, you just care about the distribution of results.  Finally, you can use the MATLAB builtin histc to generate the results in a vectorized fashion.

function face_index = new_weighted_dice(cumulative_weight)
    % cumulative_weight = cumulative distribution function to draw against
    % output: face_index is the discrete face after tossing a virtual dice with given
    % faces and weight.

% pick a random value unif. distrib. betw. 0 and the sum of the weights.
rand_w = unifrnd(0, cumulative_weight(end));
% check in which interval of the cumulative_weight is this element
for j=1:num_weight
   if rand_w >= cumulative_weight(j) && rand_w < cumulative_weight(j+1)
       break
   end
end

% assign the interval found to the value of the face
face_index = j;
end

%%%--------------main script

cumulative_weight = zeros(1, num_weight + 1);
for j=1:num_weight
   cumulative_weight(j+1) = sum(weight(1:j));
end
val = zeros(1,1000);
for i=1:1000
    val(i) = new_weighted_dice(cumulative_weight)
end

beans = histc(val, cumulative_weight);

Short, clean, fast.


String sequence in Haskell Given a string sequence and a string, the function should output the next string of that sequence.

For example, for sequence "abc":

a
b
c
aa
ab
ac
ba
..
cc
aaa
aab

How can I improve my code while maintaining a balance between performance and readability?

data Sequence = Sequence {
    getSequence :: String,
    getFirst    :: Char,
    getLast     :: Char
} deriving (Show, Eq, Ord)

getNextChar :: Sequence -> Char -> Char
getNextChar s c
    | c == getLast s = getFirst s
    | otherwise      = findChar (getSequence s)
    where findChar (x:r@(y:xs))
            | x == c    = y
            | otherwise = findChar r

getNextStr :: Sequence -> String -> String
getNextStr s xs
    | l /= getLast s = init xs ++ [getNextChar s l]
    | otherwise      = nextAny
    where l       = last xs
          fstChar = getFirst s
          lstChar = getLast s
          (f, t)  = span (== lstChar) . reverse $ xs
          nextAny
            | length t == 0 = replicate (length f + 1) fstChar
            | otherwise     = reverse $ replicate (length f) fstChar ++ [getNextChar s (head t)] ++ tail t

The primary issue I see is that your code is focused on the wrong sort of state. What you have written would be used something like—

iterate (getNextStr (Sequence "abc" 'a' 'c')) "a"

But this is very slow, you can see from the repeated usage of last, (++), and reverse that the actual state that matters (which character is next in the sequence) is getting parsed out of the previous state anew with every iteration. You are relying on repeating many \$O(n)\$ operations, which ends up causing your code to have a terrible constant factor performance hit.

The key insight or trick is to take advantage of lazy evaluation to produce an infinite stream of values which can hide all of the messy state machinery you need away in some thunks.

stringSequence :: [Char] -> [String]

We start with a clean slate and a new type signature. In this case we have a function that takes a sequence of Char values, and returns a list (which we know will be infinite) of String values made by applying the sequence generating procedure to the Chars. The magic obviously happens in the sequence generating procedure, so let's concentrate on that.

stringSequence chars = map (:"") chars

Starting is easy, we simply make a String out of each Char in our given sequence. Next step is to generate the two character Strings.

stringSequence chars =
  let
    strings = map (:"") chars
    front   = strings
    next    = concatMap (\f -> map (f ++) strings) front
  in
    front ++ next

This is the biggest jump I'll make, so make sure you understand it. The two character strings are made by taking each string we've already generated and appending a Char from the sequence to it (for convenience, strings makes it easy to combine previous values generated by the sequence generating function and the next element of the given Chars).

stringSequence chars =
  let
    strings = map (:"") chars
    front   = strings
    next    = concatMap (\f -> map (f ++) strings) front
    after   = concatMap (\s -> map (s ++) strings) next
  in
    front ++ next ++ after

Now we add the three character strings, and notice a pattern. Strings of length \$n+1\$ are made by appending the sequence characters to the strings of length \$n\$. Leveraging this insight and a trick called Tying the Knot, we can write the final version of stringSequence that produces an infinite lazy list of sequenced values.

stringSequence chars =
  let
    strings = map (:"") chars
    sequence = strings ++ concatMap (\s -> map (s ++) strings) sequence
  in
    sequence

Compare this version to your original. The Sequence type you had is now replaced with a simple list. Instead of getNextChar we use the whole sequence in one go so we don't have to perform additional bookkeeping to maintain correct ordering. Rather than parsing the previous result value with getNextStr, we maintain our state hidden away from the user by providing them an infinite list, instead of out in the open where the user has to keep track of it and we have to keep parsing it.


Permutation of phone numbers starting at button x, ending at button y, and z numbers long I am trying find the total number of permutations possible with a given x, y, and z.
x is the initial number, y is the final number, and z is the total number of buttons pressed.
I am supposed to only move from number to number like the knight in chess, in an 'L' shape.
For example, if you just dialed a 1, the next number you dial has to be either a 6 or an 8. If you just dialed a 6, the next number must be a 1 or 7.
Currently, my implementation outputs the correct answer for all the numbers I have given it. However, it is god awful slow because compute time is exponential. What I want to know is how I can compute this in linear time, more or less. z will always be between 1 and 100, inclusive.

##Computes the number of phone numbers one
##can dial that start with the digit x, end
##in the digit y, and consist of z digits in
##total. Output this number as a
##string representing the number in base-10.
##Must follow "knights rule" moves, like chess
##########_________##########
##########|1||2||3|##########
##########|_||_||_|##########
##########|4||5||6|##########
##########|_||_||_|##########
##########|7||8||9|##########
##########|_||_||_|##########
##########|_||0||_|##########
##########^^^^^^^^^##########
dict = {0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
    4: [0, 3, 9], 5: [], 6: [0, 1, 7], 7: [2, 6], 8: [1, 3],
    9: [2, 4]}

def recAnswer(current, y, z, count, total):
    if count == z and current == y:
            total += 1
            return total
    count+=1
    if count > z:
            return total
    for i in dict.get(current):
            total = recAnswer(i, y, z, count, total)
    return total

def answer(x, y, z):
    if x == y:
            if z%2 == 0:
                    return '0'
    elif x == 5 or y == 5:
            if z == 1 and x == y:
                    return '1'
            else:
                    return '0'
    elif x%2 != 0 and y%2 == 0:
            if z%2 != 0:
                    return '0'
    elif x%2 == 0 and y%2 != 0:
            if z%2 != 0:
                    return '0'
    elif x%2 == 0 and y%2 ==0:
            if z%2 == 0:
                    return '0'
    elif x%2 != 0 and y%2 != 0:
            if z%2 == 0:
                    return '0'

    total = recAnswer(x,y,z,1,0)
    return str(total)

def test():
    for i in xrange(1,15,1):
            print i,":",answer(1,3,i)

    print answer(6, 2, 5)
    print answer(1, 6, 3)
    print answer(1, 1, 99)

test()

One probable solution could be to modify the code as this:

Have the code inside answer in another function, say, isNotTraversalCandidate which returns 0,1 if it the conditions confirm that no further traversal is required else it returns -1.
In recAnswer() use this function, isNotTraversalCandidate(), for the input x, y, z in every level. The recursive function should also verify the x, y, z with those conditions.


Sieve of Sundaram for Project Euler 7 This is a sequel to my previous question: Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and R

I am trying to implement the Sieve of Sundaram in various languages to solve Project Euler Problem #7.

I have written a solution in Haskell (to which I am still very new, but eager to learn) based loosely on the example available on this blog.

The approach is to find the upper bound for the value of the nth prime:
$$\mathrm{Bound}(n) = n \times (\log(n) + \log(\log(n))) $$

Then sieve all of the numbers up to the bound.

I would like some advice on improving my style (conciseness, clarity), and the performance of my code, which is about 30x slower than the C++ solution included in my previous question.

import Data.List

bound :: Int -> Int
bound n = floor (n' * ((log n') + log (log n')))
    where
        n' = fromIntegral n

marked :: Int -> [Int]
marked n = sort [ i + j + 2*i*j | i <- [1..iMax], j <- [i..jMax i]]
    where
        iMax = floor (sqrt (fromIntegral n))
        jMax i = quot (n - i) (2*i + 1)

removeComposites :: [Int] -> [Int] -> [Int]
removeComposites [] _          = []
removeComposites (s:ss) []     = 2*s + 1 : removeComposites ss []
removeComposites (s:ss) (c:cs)
    | s == c    = removeComposites ss cs
    | s > c     = removeComposites (s:ss) cs
    | otherwise = 2*s + 1 : removeComposites ss (c:cs)

sieveSundaram :: Int -> [Int]
sieveSundaram n = 2:(removeComposites [1..n'] (marked n'))
    where
        n' = quot (bound n) 2

pe_007 = last (take n (sieveSundaram n))
    where n = 10001

main :: IO ()
main = do
    print pe_007

Prime sieves are really not well suited for linked lists. While sorting or merging are clever way to handle the lists in a functional context, the easiest way to improve preformance is to simply use mutable arrays, so it's more similar to the C++ version.

Here I just replaced the sorting and removeComposites with an unboxed STArray and indexing. The benifit with using STArray is that you still get a pure function, even though the array is mutable while generating. The times are now comparable with the C++ version.

import Data.Array.ST
import Data.Array.Unboxed

bound :: Int -> Int
bound n = floor (n' * (log n' + log (log n')))
    where
        n' = fromIntegral n

marked :: Int -> [Int]
marked n =  [ i + j + 2*i*j | i <- [1..iMax], j <- [i..jMax i]]
    where
        iMax = floor (sqrt (fromIntegral n))
        jMax i = quot (n - i) (2*i + 1)

marked' :: Int -> UArray Int Bool
marked' n = runSTUArray $ do
    arr <- newArray (1,n) True
    mapM_ (\i -> writeArray arr i False) (marked n)
    return arr

sieveSundaram :: Int -> [Int]
sieveSundaram n = 2: [2*x+1 | x <- [1..n'], marked' n' ! x]
    where
        n' = quot (bound n) 2

pe_007 = last . take n $ sieveSundaram n
    where n = 100001

main :: IO ()
main = print pe_007

On my system, with n=200001, the times are:

Haskell, Original version: 5.930s
Haskell, Neil's version:   5.916s
Haskell, Data.IntSet:      2.853s
Haskell, Boxed STArray:    0.209s
Haskell, Unboxed STUArray: 0.055s
C++:                       0.019s

It is probably possible to improve the times even more, but this takes care of most of the difference.

Update

Continuing on the theme of using the right data structure for the job, I tried using IntSets for aditional comparison. It is about twice as fast as the list based solutions, but still a lot slower than using mutable arrays (see updated table). So if you want to stay with pure haskell98, this might be an alternative. Here is my (naive) translation. I just create the set of numbers [1,n] and the set of numbers to remove (from marked) and take the difference.

import qualified Data.IntSet as IS

bound :: Int -> Int
bound n = floor $ n' * (log n' + log (log n'))
    where
        n' = fromIntegral n

marked :: Int -> [Int]
marked n =  [ i + j + 2*i*j | i <- [1..iMax], j <- [i..jMax i]]
    where
        iMax = floor (sqrt (fromIntegral n))
        jMax i = quot (n - i) (2*i + 1)

marked' :: Int -> [Int]
marked' n = let
    l1 = IS.fromList [1..n]
    l2 = IS.fromList (marked n)
    in IS.toList $ l1 IS.\\ l2

sieveSundaram :: Int -> [Int]
sieveSundaram n = 2: [2*x+1 | x <- marked' n']
    where
        n' = quot (bound n) 2

pe_007 = last . take n $ sieveSundaram n
    where n = 200001

main :: IO ()
main = print pe_007

IntSets are a really good data structure if you need to repeatedly modify the sets in a pure context, but for this problem nothing can beat an unboxed mutable array.


Is this a right and effcient way of checking AND in a for loop Just saw this at work in a code review and was wondering if this style of coding - for loop, doing && like that, seems fine to you or is there a better way of doing the same?

for (int j = 1; j <= ETtop; j++)
{
    // Check everything.
    int k = ET[j].PriIdx;
    for (int z = 1; z <= ET[k].ArgTop; z++ )
    {
        // Check to make sure every Argument in the equation is valid.
        // If it's a calc this is only true if it's been evaluated.
        ready = ready && ET[k].Arg[z].Valid;
    }
}

Currently, once you get ready to be false, all other checks after that will fail (as false && condition2 will always be false).

Why not just break out of the inner for loop when ET[k].Arg[z].Valid is false?  If ready is needed, you may keep the assignment line, but break when it's false.


Insertion sort implementation adapted from the web I've found this implementation on the web:

void insertSort(int a[], int length)
{
    int i, j, value;
    int k=0;
    for(i = 1; i < length; i++)
    {
      value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
      {
            a[j + 1] = a[j];
            k++;
        }
        a[j+1] = value;
    }

    printf("k=%d", k);
}

I have written this:

#include <stdio.h>

#define SIZE 8

int array1[SIZE] = {77, 33, 44, 11, 88, 22, 66, 55};

void PrintArray()
{
    int i = 0;
    printf("\n");
    for(i=0 ; i<SIZE ; i++)
    {
        printf("%d, ", array1[i]);
    }
}

void Insert(int insertPosition, int insertElementIndex)
{
    int temp = array1[insertElementIndex];
    int i = 0;

    for(i=insertElementIndex ; i>=insertPosition ; i--)
    {
        array1[i] = array1[i-1];
    }

    array1[insertPosition] = temp;
}

void InsertionSort()
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0 ; i<SIZE ; i++)
    {
        for(j=0 ; j<=i ; j++)
        {
            if(array1[i] < array1[j])
            {
                Insert(j, i);
                PrintArray();
            }

            k++;
        }
    }
    printf("k=%d", k);
}

main()
{
    PrintArray();

    InsertionSort();
    //insertSort(array1, SIZE);

    PrintArray();

    getch();
}

Is there any problem with this implementation?

First of all, what you implemented is not insertion sort:

Insertion sort uses one loop to iterate over the array, and for each element uses another loop to move the element to its desired location. This makes its running time \$O(n^2)\$.

Your algorithm iterates over each pair of elements (using the two nested loops in InsertionSort()) and then for each pair, uses a third loop (the one in Insert) to move the one element to the position of the other if necessary. This makes its running time \$O(n^3)\$, which is significantly worse than \$O(n^2)\$.

So that's a problem.

In addition to that there's also a major usability problem with your function:

By making the array and its size a global variable and a constant instead of parameters, you make reuse of your function as good as impossible. If you want to use the function to sort multiple arrays, you have to copy each one into the global variable, call the sort function, and then copy it back from the global variable again. And this only works if all the arrays have the same size. If the arrays have different sizes it's plain impossible to use your InsertionSort function on them.

So passing the array and its size as parameters is clearly preferable.

Lastly, I realize that you're most probably aware of this and this is just a learning exercise, but just in case:

In most real-world applications, quick sort or merge sort are usually preferable to insertion sort, having much better performance characteristics than insertion sort in the majority of cases. So if you want to use this in real code, you should rethink whether you really want to use insertion sort.

Also the standard C library has a sort function built-in, so you don't even have to implement anything yourself.


Comparing two bubble sort algorithms I'm learning C and I've got to a point learning about different sorting algorithms.  Before seeing how it was done, I wanted to try doing it myself based on what I read on how it's working.

int temp;
    for(int i = 0; i < SIZE - 1; i++)
    {
        for(int j = 0; j < SIZE - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }

This is what the code from where I learn looks like:

for(int i = 0; i < SIZE; i++)
{
       if((i < SIZE - 1) && (arr[i] > arr[i+1]))
       {
                  int tmp = arr[i];
                  arr[i] = arr[i + 1];
                  arr[i + 1] = tmp;
                  i = -1;
       }
}

Now, obviously they're different, but is one more efficient in someway than the other?  Did I do something that is less efficient than their code?

Your implementation

Your implementation is mostly pretty good.  I'd just make a few minor changes:

int temp should be declared in the tightest scope possible — namely, inside the if block.  Localizing the variable further makes it harder to misuse and easier to understand.  I'd also rename temp to swap to make its purpose clearer.  (Naming a variable temp is usually a bad idea, in my opinion.)
int temp is at the wrong level of indentation.  Maybe you just made an error when pasting the code here?
There is a space after if, but not after for.  Be consistent.  I recommend putting the space there to distinguish those keywords from function calls.
The j < SIZE - 1 - i condition is a bit hard to follow.  You could apply the transformation ii = SIZE - 1 - i, and have the outer loop count backwards instead.

for (int ii = SIZE - 1; ii > 0; ii--)
{
    /* Let the largest element bubble up to the end */
    for (int j = 0; j < ii; j++)
    {
        if (arr[j] > arr[j + 1])
        {
            int swap = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = swap;
        }
    }
}


Two Python classes for a web crawler I am using the Python module urllib3. It occurs to me that there is a better way to design a good class when I rebuild my last site crawler.

class Global:
    host = 'http://xxx.org/'
    proxy=True
    proxyHost='http://127.0.0.1:8087/'
    opts=AttrDict(
        method='GET',
        headers={'Host':'xxxx.org',
              'User-Agent':'Mozilla/5.0 (Windows NT 6.1; rv:12.0) Gecko/20100101 Firefox/12.0',
              'Accept':'text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8',
              'Accept-Language':'en-us;q=0.5,en;q=0.3',
              'Accept-Encoding':'gzip, deflate',
              'Connection':'keep-alive',
              'Cookie':'xxxxxxx',
              'Cache-Control':'max-age=0'
              },
        assert_same_host=False
    )
    def getPool(self,proxy=None):
        if proxy is  None:
            proxy = self.proxy
        if(self.proxy):
            http_pool = urllib3.proxy_from_url(self.proxyHost)
        else:
            http_pool = urllib3.connection_from_url(self.host)
        return http_pool

class Conn:
    def __init__(self, proxy):
        self.proxy= proxy
        self.pool = Global().getPool(self.proxy)
    def swith(self):
        self.pool = Global().getPool(not self.proxy)
    def get(url, opts=Global.opts):
        try:
          self.pool.urlopen(
              method=opts.method,
              url= url,
              headers= opts.headers,
              assert_same_host=opts.assert_same_host
              )
        except TimeoutError, e:
            print()
        except MaxRetryError, e:
            # ..

I try to make class contains all global configs and data for others to call,
just like I do in JavaScript. But, are these classes too tightly coupled? Should I just merge them together?

Class design

A good class in general is one that corresponds to an Abstract Data Type,
which is a collection of data and operations that work on that data.
A good ADT should have a single, clear responsibility.

The Global class is not a good ADT:

It does two unrelated things:

Contain configuration information
Manage a proxy pool

Possibly as a consequence of the previous point, it is poorly named

It would be better to split this class into two:

Configuration or Config: contain configuration information
ProxyPoolManager: manage a proxy pool

Note that ProxyPoolManager should not reference Configuration directly:
it will be best to pass to it the proxyHost and proxy as constructor parameters.

As the poorly named Conn class already does half of the proxy pool management,
it would be better to rename it to ProxyPoolManager and move getPool method into it and rename Global to Configuration.

Coding style

You have several coding style violations, not conforming to PEP8:

Use spaces around = in variable assignments, for example:

proxy = True instead of proxy=True
opts = AttrDict(...) instead of opts=AttrDict(...)

No need to put parentheses in if(self.proxy):
There should be one blank line in front of method definitions of a class: put a blank line in front of get and switch methods in the Conn class
You mistyped switch as swith

Other issues

This code doesn't compile:

class Conn:
    def get(url, opts=Global.opts):
        try:
          self.pool.urlopen(...)

Because it makes a reference to self which was not passed in as method parameter.

This is a bit hard to understand,
because of reusing the name "proxy" both as method parameter and as attribute:

def getPool(self,proxy=None):
    if proxy is  None:
        proxy = self.proxy
    if(self.proxy):
        http_pool = urllib3.proxy_from_url(self.proxyHost)
    else:
        http_pool = urllib3.connection_from_url(self.host)
    return http_pool

The purpose of this method would be more clear if you used a different name for the method parameter.