Memoizing decorator with retries, part 2 A while ago I asked this question Memoizing decorator that can retry and then promptly forgot about it. I more recently saw Python decorator for retrying w/exponential backoff and wanted to add backoff, but figured I should improve what I already have first. I have taken some of the suggestions of the original, but really I've just completely reimagined it (and if I do say so myself, rather cleverly too). My biggest issue with this is that I'm not sure that my current distinction between "exceptions that get suppressed but not remembered" and "exceptions that get remembered" seems like it might be a bit confusing - is there a friendlier interface here?

import functools
from types import MappingProxyType as FrozenDict

class Memoizer:

    def __init__(self, retry_times=0, suppressed_exceptions=tuple(), capture_exceptions=False):
        self.retry = retry
        self.retry_times = retry_times
        self.suppressed_exceptions = suppressed_exceptions
        self.capture_exceptions = capture_exceptions

    def __call__(self, function):
        d = {}

        @functools.wraps(function)
        def wrapper(*args, **kwargs, __forget=False):
            key = (args, FrozenDict(kwargs))
            if key not in d or __forget:
                i = self.retry_times
                while i > 1:
                    try:
                        d[key] = function(*args, **kwargs)
                    except self.suppressed_exceptions:
                        continue
                    except Exception as e:
                        if self.capture_exceptions:
                            d[key] = e
                            break
                        raise
                    else:
                        break
                    i -= 1
                else:
                    # If we didn't already break out, the last attempt shouldn't suppress exceptions
                    d[key] = function(*args, **kwargs)

            return d[key]

        return wrapper

Your code is broken:

__forget=False needs to be before **kwargs.
retry is undefined. (But is not used)
MappingProxyType is not hashable, and so you can't memoize it.

To fix the problem with MappingProxyType you can create a hashable dict, which seems kinda hacky, but is better than nothing. The other two are easy fixes.

I don't see why you're using a class,
the only benefit that you get from it is that you can hide implementation details in it.
However self. is an annoyance in your current implementation, in my opinion.

Design wise, I still don't get the name retry_times, let's actually retry that amount rather than try that amount of times.

And I'd split the memoizer away from the retry decorator.
Being able to use say functools.lru_cache would be nice.

And so I'd make the retry aspect a function,
removing where it currently adds to the cache.
changing the while loop to a for loop,
and will removing the cache.
This should get you:

def retry(retry_times=0, suppressed_exceptions=tuple(), capture_exceptions=False):
    def inner(function):
        @functools.wraps(function)
        def wrapper(*args, **kwargs):
            for _ in range(retry_times):
                try:
                    return function(*args, **kwargs)
                except suppressed_exceptions:
                    continue
                except Exception as e:
                    if capture_exceptions:
                        return e
                    raise
            else:
                return function(*args, **kwargs)
        return wrapper
    return inner

And now you can use the retry part without the memoizing part!
After this, I'd just make a generic memoizer, without caching the **kwargs.
Say:

def memoize(fn):
    cache = {}
    @functools.wraps(fn)
    def wrapper(*args, _forget=False):
        key = (args)
        if key not in cache or _forget:
            cache[key] = fn(*args)
        return cache[key]
    return wrapper


Finding the number of times the code will generate an alert depending upon whether the transaction is fraudulent Please refer to this problem from Hackerrank

  HackerLand National Bank has a simple policy for warning clients about
  possible fraudulent account activity. If the amount spent by a client
  on a particular day is greater than or equal to the client's median
  spending for a trailing number of days, they send the client a
  notification about potential fraud. The bank doesn't send the client
  any notifications until they have at least that trailing number of
  prior days' transaction data.

I have written the following code. However, the code is working for some of the test cases and is getting 'terminated due to timeout' for some. Can anyone please tell how can I improve the code?

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the activityNotifications function below.
    static int activityNotifications(int[] expenditure, int d)     {
        //Delaring Variables

        int iterations,itr,length,median,midDummy,midL,midR,               midDummy2,i,i1,temp,count;
        float mid,p,q;
        length = expenditure.length;
        iterations = length-d;
        i=0;
        i1=0;
        itr=0;
        count = 0;

        int[] exSub = new int[d];

        while(iterations>0)
        {

            // Enter the elements in the subarray
            while(i1<d)
            {
                exSub[i1]=expenditure[i+i1];
                //System.out.println(exSub[i1]);
                i1++;
            }

            //Sort the exSub array
            for(int k=0; k<(d-1); k++)
            {
                for(int j=k+1; j<d; j++)
                {
                    if(exSub[j]<exSub[k])
                    {
                        temp = exSub[j];
                        exSub[j] = exSub[k];
                        exSub[k] = temp;
                    }
                }
            }

            //Printing the exSub array in each iteration

            for(int l = 0 ; l<d ; l++)
            {
                System.out.println(exSub[l]);
            }

            i1=0;

            //For each iteration claculate the median

            if(d%2 == 0) // even
            {
                midDummy = d/2;
                p= (float)exSub[midDummy];
                q= (float)exSub[midDummy-1];
                mid = (p+q)/2;
                //mid = (exSub[midDummy]+exSub                                   [midDummy-1])/2;
                //System.out.println(midDummy);
            }
            else // odd
            {

                midDummy2 =d/2;
                mid=exSub[midDummy2];
                //System.out.println(midDummy2);
            }

            if(expenditure[itr+d]>=2*mid)
            {
                count++;
            }
            itr++;
            i++;
            iterations--;

            System.out.println("Mid:"+mid);
            System.out.println("---------");

        }

        System.out.println("Count:"+count);
        return count;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nd = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

        int[] expenditure = new int[n];

        String[] expenditureItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int expenditureItem = Integer.parseInt(expenditureItems[i]);
            expenditure[i] = expenditureItem;
        }

        int result = activityNotifications(expenditure, d);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

close

You had an opportunity to acquire (and then close) this resource
using try-with-resource

private static final Scanner scanner = new Scanner(System.in);

Similarly for this one:

new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

streaming input

You're reading 200,000 numbers here:

    String[] expenditureItems = scanner.nextLine().split(" ");

They won't fit in the lower levels of the cache hierarchy, they are spilling to RAM.
Consider reading as you compute.
You never need much more than d numbers to be resident at once.

no-op

This doesn't appear to do anything for you. Consider deleting it.

    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

temp var

The compiler optimizes it away,
but needlessly introducing a temp variable makes your code harder to read:

        int expenditureItem = Integer.parseInt(expenditureItems[i]);
        expenditure[i] = expenditureItem;

Just phrase it as:

        expenditure[i] = Integer.parseInt(expenditureItems[i]);

Not sure why you wanted to allocate 200,000 strings and then 200,000 ints,
when you could have streamed through them one string at a time.

Integer.toString

In addition to needless temp var,
it seems you chose to define an inconvenient API:

    int result = activityNotifications(expenditure, d);
    bufferedWriter.write(String.valueOf(result));

You might find it slightly more convenient to write the result
if activityNotifications returned Integer.

API

You might have found it convenient to pass in two separate arrays,
one containing d entries and the other containing the n - d
entries that you have to make decisions on.

Ok, it appears you spend almost no time in main,
relative to what activityNotifications consumes.

sort

The pair of nested loops headed by

        //Sort the exSub array

is quite insane.
You know d shall be "large".

You have an opportunity to use Arrays.sort() with cost O(d log d),
yet you went for the quadratic solution, O(d**2).

printing

I don't understand the comment "Printing the exSub array in each iteration".
Why would you want to spend time doing that?
Only the return value count is relevant for evaluating your submission.
Similarly for your debug print of mid.

algorithm - heap

You (re-)sort d elements every single time.
Even though only a single value entered the d-day window,
and a single value left.
Maintain a heap, at cost of O(log d) for each operation.

algorithm - counting values

Go back and read the problem.

Are expenditures floats of arbitrary precision? No, they are integers.

Can expenditures have arbitrary magnitudes as large as the U.S. debt?
No, only two hundred and one distinct values are allowed.

Recall that a median value separates the low half from the high half of the values.
Maintain 201 counts,
and a circular FIFO list of daily expenditures
(or continue using the giant n-entry input array,
indexing it d behind today).
Increment a count corresponding to today's expenditure,
and decrement a count for the day exiting the d-day window.
Identify the point at which the sum of the low counts
matches the sum of the high counts, that's your median.
You can do it in time proportional to 201 (much less than d),
or you can choose to do it faster than that
by maintaining cumulative sums
and remembering what yesterday's median was.
Good luck!


binary tree to binary search tree Today I had an interview where I was asked to solve "Given an binary tree, convert it to binary search tree in minimum time, space complexity".

I wrote this code, but got the feedback that complexity could be improved without using sort and without using external storage.

How to do it?

##code goes below##:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(root,arr):
    if root is None:
        return
    inorder(root.left, arr)
    arr.append(root.data)
    inorder(root.right, arr)

def binary_to_bst(root, arr):
    if root is None:
        return
    binary_to_bst(root.left, arr)
    root.data = arr.pop(0)
    binary_to_bst(root.right, arr)

root = Node(4)
root.left = Node(2)
root.right = Node(1)
root.left.left = Node(5)
root.left.right  = Node(7)
root.right.left = Node(12)
arr = []
inorder(root,arr)
arr.sort()
binary_to_bst(root, arr)

I don't think that time complexity could be improved. An in-place approach is to flatten the tree into a list (the key is to reuse child pointers), and recreate the tree as BST. To flatten,

    def flatten(root):
        rightmost = get_rightmost(root)
        while root:
            rightmost.right = root.left
            rightmost = get_rightmost(root.left)
            root.left = None
            root = root.right

The time complexity of flattening is linear.

To recreate,

    def list_to_bst(root):
        cursor = root
        while cursor:
            next = cursor.right
            cursor.right = None
            root = insert(root, cursor)
            cursor = next

insert is a standard (or balanced, if you want to go fancy) BST insertion. get_rightmost is trivial.

There is no recursion, so the space complexity is constant. The time complexity is bounded by insertion, that is in a \$O(n\log n)\$ ballpark.


"Picking Cards" challenge I recently tried my hand at CodeSprint2 through Interview Street.  Having not coded in quite some time, I wasn't surprised that I had difficulty writing optimized code, but on one problem in particular I can't find where I've gone wrong.  I've compared my code to successful algorithms used by other programmers, and I don't see much difference.  I tried in both Java and Ruby and hit a wall at the 4th test case with both (I'm just learning Ruby so thought it would be a fun exercise to try it - I tweaked my algorithm a little in the process).

The problem is Picking Cards and the description is here.

Code in Java:

import java.io.*;
import java.util.*;
import java.math.*;

public class Cards3 {

    public Cards3()
    {
    }

     public void run()
    {
        ArrayList<Integer> cards = new ArrayList<Integer>();
        try{
            /*
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String input = reader.readLine();

            StringTokenizer tokenizer = new StringTokenizer(input);
            int T = Integer.parseInt(tokenizer.nextToken());
            */

            DataInputStream reader = new DataInputStream(System.in);
            int T = reader.readInt();
            reader.readChar();
            System.out.println("T = " + T);
            //read in and test each subsequence
            for(int i = 0; i<T; i++)
            {
                /*
                input = reader.readLine();
                tokenizer = new StringTokenizer(input);
                int N = Integer.parseInt(tokenizer.nextToken());

                //read in and store cards
                String nextLine = reader.readLine();
                tokenizer = new StringTokenizer(nextLine);
                */

                int N = reader.readInt();
                reader.readChar();

                for(int j=0; j<N; j++)
                {
                    int next = reader.readInt();//Integer.parseInt(tokenizer.nextToken());
                    reader.readChar();
                    cards.add(next);
                }
                Collections.sort(cards);
                System.out.println(numWays(cards) % 1000000007);
                cards = new ArrayList<Integer>();
            }

            reader.close();
        }
        catch (IOException e)
        {
            System.out.println("Can not read input.");
        }
    }

    //computers the number of ways to pick up cards in currCards given that
    //numPicked cards have already been picked up
    public long numWays(ArrayList<Integer> cardsLeft)
    {
        int numPicked = 0;
        long numWays = 1;

        //calculate until all cards are picked up
        while(cardsLeft.size() >= 1)
        {
            //if we can't pick up the next card, we're at a dead end - no solutions
            if(cardsLeft.get(0) > numPicked)
                return 0;

            int numCanPick = 0;

            for(int i: cardsLeft)
            {
                if(i <= numPicked)
                {
                    numCanPick++;

                }
                else
                {
                    break;
                }
            }

            cardsLeft.remove(0);
            numWays *= numCanPick;
            numWays = numWays % 1000000007;
            numPicked++;
        }

        return numWays;
    }

     public static void main(String args[])
       {
            Cards3 d = new Cards3();
            d.run();
       }
}

Code in Ruby

def runProgram
  answers = []
  t = STDIN.gets.to_i
  t.times{
    n = STDIN.gets
    numWays = 1
    cards = STDIN.gets.split.map(&:to_i)
    numPicked = 0
    for i in 0...cards.length
      numCanPick = cards.count{|a| a<= i}
      numWays = numWays * (numCanPick-i)
      break if numCanPick==0
      numWays = numWays % 1000000007
    end
     answers << numWays
  }

  puts answers
end

if __FILE__ == $0
 runProgram
 end

The immediate thing that jumps out to me is your use of an ArrayList for this. By continuously removing the first element, you force the array list to shift everything left one space each time (an O(n) operation assuming no underlying optimizations!)

Instead of removing from the array list (incurring an expensive shift), I would recommend that you keep an index.

    while(cardsLeft.size() >= 1)
    {
        //if we can't pick up the next card, we're at a dead end - no solutions
        if(cardsLeft.get(0) > numPicked)
            return 0;

        // ...
        for(int i: cardsLeft)
        {
             // ...
        }

        // ...

        cardsLeft.remove(0);
        // ...
    }

becomes

    int cardIndex = 0;
    while(cardIndex < cardsLeft.length())
    {
        //if we can't pick up the next card, we're at a dead end - no solutions
        if(cardsLeft.get(cardIndex) > numPicked)
            return 0;
        // ...
        for(int i = cardIndex; i < cardsLeft.length(); ++i)
        {
             // ...
        }
        // ...

        //cardsLeft.remove(0);
        ++cardIndex
        // ...
    }


Model interval inclusiveness in C# This is my first attempt to model a day's time interval and the fact that the start and end are either inclusive or not:

public class UtcTimeOfDay
{
    public int HourOfDay { get; set; }
    public int MinuteOfDay { get; set; }
    public int SecondOfDay { get; set; }
}

public class UtcTimeInterval
{
    public UtcTimeOfDay StartUtcTimeOfDay { get; set; }
    public UtcTimeOfDay EndUtcTimeOfDay { get; set; }
    public bool StartInclusive { get; set; }
    public bool EndInclusive { get; set; }
}

Any suggestions for improvement?

Do you need UtcTimeOfDay at all? DateTime already has useful methods for working with paramterized times.

The disadvantage that using a raw DateTime has is that you have no compile-time guarantee that you won't get an invalid DateTime (e.g. one with a Day component above 0). However, you can get the best of both worlds by having your class wrap a DateTime:

public class UtcTimeOfDay
{
    public readonly DateTime Value;

    public UtcTimeOfDay(int hour, int minute, int second)
    {
        Value = new DateTime(0,0,0,hour,minute,second);
    }
}

Now you get all the advantages of the rich functionality of DateTime, along with the guarantees provided by your original class.

Regarding your original UtcTimeOfDay, the names aren't great. Shouldn't MinuteOfDay be MinuteOfHour, and likewise shouldn't SecondOfDay be SecondOfMinute?

This also reveals another problem: there's no guarantee that these values are valid (they could be negative, or above the maximum possible). This could be done with validation in a constructor, making the setters private.

The name UtcTimeInterval doesn't make any reference to the fact that it's specifically for a time interval within a day. Why not UtcTimeOfDayInterval?

While you can use StartInclusive and EndInclusive, a normal technique to deal with exclusive time spans is simply to add or subtract a tick to your time. So for example, if the inclusive start time was startTimeInclusive, then if you want an exclusive version, that would be startTimeExclusive = startTimeInclusive.AddTicks(1);

Being able to do this so simply is another benefit of using a DateTime rather than trying to roll your own structure to represent the same thing.

So what I would do is remove the StartInclusive and EndInclusive properties, and do one of the following:

Just let whoever sets the start and end UtcTimeOfDay take responsibility for adding or subtracting a tick if they need to.
Add a constructor with boolean startInclusive and endInclusive parameters, as well as the start and end UtcTimeOfDays which itself does the tick adding/subtracting when needed.

Update

As a couple of people have noted in comments, using a TimeSpan instead of a DateTime may be preferable, as it is more in fitting with the meaning of these structures. This makes the add/subtract tick logic slightly more verbose, but not prohibitively.


Global.asax singleton Please help me decide whether this should be good or bad idea to declare a Singleton variable in Global.asax file. (It is not actually singleton pattern, I just want to make sure that only one instance is created for this class.)

public class Global : System.Web.HttpApplication
{
    private HTML5Video dailyHtml5Video;

    public HTML5Video DailyHtml5Video
    {
        get
        {
            if (dailyHtml5Video==null)
            {
                dailyHtml5Video = new HTML5Video();
            }

            return dailyHtml5Video;
        }
    }

}

Will this cause any thread-related issues or other possible issues?

It is not thread safe. You can use Lazy type to create a variable of HTML5Video in a thread safe manner.

Lazy<HTML5Video> dailyHtml5Video = new Lazy<HTML5Video>(() => new HTML5Video());
public HTML5Video DailyHtml5Video
{
    get {return dailyHtml5Video.Value;}
}

You can read about different versions of Singleton pattern here http://csharpindepth.com/articles/general/singleton.aspx


Eratosthenes Sieve optimized in C I wrote yet another optimized single-threaded Eratosthenes Sieve implementation in C:

erato.c

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

#define N 1000000000
#define num_t unsigned long

int main() {
    register char *b = malloc(N * sizeof(char));
    for(num_t i = 0; i ^ N; ++i)
        b[i] = !(i & 1);

    // printf("2\n");
    for(num_t i = 3; i ^ 1 ^ N; i += 2) {
        if(!b[i - 2]) {
            // printf("%llu\n", i);
            const num_t increment = i << 1;
            num_t j = i;
            while(j < N) {
                b[j - 2] = 1;
                j += increment;
            }
        }
    }
    free(b);
    return 0;
}

The output is omitted because it takes most of the time to process.

Optional flags: -O3

Performance

The sieve covers first 1.000.000.000 numbers in

  11.14s user 0.32s system 99% cpu 11.465 total

Could you please help me to improve my programming/mathematical skills by reviewing this piece of code?

Bug

At the end of your program, the b array is all full of 1s, which means that you didn't find any primes.  The problem is here:

       num_t j = i;

Because you start your j loop at i, you will mark i (which is prime) as non-prime.  You should start your j loop at i*i instead (see below).

Don't get tricky

Why write this:

for(num_t i = 0; i ^ N; ++i)

when you can write this:

for(num_t i = 0; i < N; ++i)

I had to stare at your code for a long time just to figure out whether it was correct, for a simple loop!

Also, you did it here:

for(num_t i = 3; i ^ 1 ^ N; i += 2) {

which should be:

for(num_t i = 3; i < N; i += 2) {

You can afford to waste 2 bytes

Here, you use index-2 to save 2 bytes:

    if(!b[i - 2]) {
        // printf("%llu\n", i);
        const num_t increment = i << 1;
        num_t j = i;
        while(j < N) {
            b[j - 2] = 1;
            j += increment;
        }
    }

There's no need to save 2 bytes.  Just use b[index] instead of b[index-2].  You already allocated the full array anyways.

Speed improvements

There are three things I can see that could speed up your program:

In your j loop, you can start j at i*i instead of just i.  All non-primes less than i*i will already be marked.
You can stop the i loop at sqrt(N) instead of at N, because once you reach sqrt(N), the second loop won't mark any more entries.
Since you are finding primes up to 10^9, you are using 1GB of memory for the b array.  You should get better performance if you use less memory, because the processor cache will be utilized more effectively if your array is smaller.

a) You can only track odd numbers, which will reduce your memory usage to 1/2 of the original (512MB).

b) You can use 1 bit per number instead of 1 byte per number.  This will reduce your memory to 1/8 of the original.  Combined with (a), it will be 1/16 the original, or 64MB.  This is a much better than 1GB.

Example using 1 bit per odd number

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define N        1000000000

int main(void)
{
    int       arraySize = ((N + 63)/64 + 1) * sizeof(uint32_t);
    uint32_t *primes    = malloc(arraySize);

    // Each bit in primes is an odd number.
    // Bit 0 = 1, bit 1 = 3, bit 2 = 5, etc.
    memset(primes, 0xff, arraySize);

    // 1 is not a prime.
    primes[0] &= ~0x1;

    int sqrt_N = sqrt(N);
    for(int i = 3; i <= sqrt_N; i += 2) {
        int iIndex = i >> 6;
        int iBit   = (1 << ((i >> 1) & 31));
        if ((primes[iIndex] & iBit) != 0) {
            int increment = i+i;
            for (int j = i * i; j < N; j += increment) {
                int jIndex = j >> 6;
                int jBit   = (1 << ((j >> 1) & 31));
                primes[jIndex] &= ~jBit;
            }
        }
    }

    // Count the number of primes in order to verify that the above worked.
    // Start count at 1 to include 2 as the first prime, since we are only
    // going to count odd primes.
    int count = 1;
    for (int i = 3; i < N; i += 2) {
        int iIndex = i >> 6;
        int iBit   = (1 << ((i >> 1) & 31));
        if (primes[iIndex] & iBit)
            count++;
    }
    printf("%d\n", count);

    free(primes);
    return 0;
}

Edit: Even less memory usage

Pete Kirkham suggested using even less memory by using 2 out of every 6 numbers.  In other words, using 1 bit per every 3 numbers instead of 1 bit per every 2 numbers.  At first I was skeptical because this required using a division in the inner loop.  However, after coding it up, it turned out to be faster.  The code is quite a bit trickier however, because the inner loops need to avoid any multiples of 3, because all multiples of 3 are no longer in the primes array:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define N        1000000000

int main(void)
{
    int       arraySize = (N/24 + 1);
    uint32_t *primes    = malloc(arraySize);

    // The bits in primes follow this pattern:
    //
    // Bit 0 = 5, bit 1 = 7, bit 2 = 11, bit 3 = 13, bit 4 = 17, etc.
    //
    // For even bits, bit n represents 5 + 6*n
    // For odd  bits, bit n represents 1 + 6*n
    memset(primes , 0xff, arraySize);

    int sqrt_N = sqrt(N);
    for(int i = 5; i <= sqrt_N; i += 4) {
        int iBitNumber = i / 3 - 1;
        int iIndex = iBitNumber >> 5;
        int iBit   = 1 << (iBitNumber & 31);
        if ((primes[iIndex] & iBit) != 0) {
            int increment = i+i;
            for (int j = i * i; j < N; j += increment) {
                int jBitNumber = j / 3 - 1;
                int jIndex = jBitNumber >> 5;
                int jBit   = 1 << (jBitNumber & 31);

                primes[jIndex] &= ~jBit;

                j += increment;
                if (j >= N)
                    break;

                jBitNumber = j / 3 - 1;
                jIndex = jBitNumber >> 5;
                jBit   = 1 << (jBitNumber & 31);

                primes[jIndex] &= ~jBit;

                // Skip multiple of 3.
                j += increment;
            }
        }
        i += 2;
        iBit <<= 1;
        if ((primes[iIndex] & iBit) != 0) {
            int increment = i+i;
            for (int j = i * i; j < N; j += increment) {
                int jBitNumber = j / 3 - 1;
                int jIndex = jBitNumber >> 5;
                int jBit   = 1 << (jBitNumber & 31);

                primes[jIndex] &= ~jBit;

                // Skip multiple of 3.
                j += increment;

                j += increment;
                if (j >= N)
                    break;

                jBitNumber = j / 3 - 1;
                jIndex = jBitNumber >> 5;
                jBit   = 1 << (jBitNumber & 31);

                primes[jIndex] &= ~jBit;
            }
        }
    }

    // Initial count includes 2, 3.
    int count=2;
    for (int i=5;i<N;i+=6) {
        int iBitNumber = i / 3 - 1;
        int iIndex = iBitNumber >> 5;
        int iBit   = 1 << (iBitNumber & 31);
        if (primes[iIndex] & iBit) {
            count++;
        }
        iBit <<= 1;
        if (primes[iIndex] & iBit) {
            count++;
        }
    }
    printf("%d\n", count);

    free(primes);
    return 0;
}

I'm sure the variant that works on multiples of 30 would be even faster than this, although the code would be even more complicated.

Timings

Here are the speeds of the various programs I ran on my computer:

Original program        : 13.33 seconds
OP fixed (i*i, sqrt(n)) :  7.75 seconds
1 bit per odd number    :  3.90 seconds
1 bit per 3 numbers     :  2.77 seconds

Note that I did not include the time it took to count the primes to verify the result.   I modified each program to count the number of primes just to make sure that they all worked, which is how I discovered that the original program had a bug in it.


What would be the computationally faster way to implement this 2D numerical integration? I am interested in doing a 2D numerical integration. Right now I am using the scipy.integrate.dblquad but it is very slow. Please see the code below. My need is to evaluate this integral 100s of times with completely different parameters. Hence I want to make the processing as fast and efficient as possible. The code is:

import numpy as np
from scipy import integrate
from scipy.special import erf
from scipy.special import j0
import time

q = np.linspace(0.03, 1.0, 1000)

start = time.time()

def f(q, z, t):
    return t * 0.5 * (erf((t - z) / 3) - 1) * j0(q * t) * (1 / (np.sqrt(2 * np.pi) * 2)) * np.exp(
        -0.5 * ((z - 40) / 2) ** 2)

y = np.empty([len(q)])
for n in range(len(q)):
    y[n] = integrate.dblquad(lambda t, z: f(q[n], z, t), 0, 50, lambda z: 10, lambda z: 60)[0]

end = time.time()
print(end - start)

Time taken is

212.96751403808594

This is too much. Please suggest a better way to achieve what I want to do. I have read quadpy can do this job better and very faster but I have no idea how to implement the same. Also, I tried to use cython-prange but scipy doesn't work without gil. I tried numba but again it didn't work for scipy. Please help.

A very low hanging fruit, namely lifting the constant factor

0.5 * (1 / (np.sqrt(2 * np.pi) * 2))

out from the integral, reduces time by a quarter. On my system the original code took

294.532276869

while the fixed one took

224.198880911

Another fruit, a bit above, is to abandon dblquad whatsoever. It is just a wrong tool here.

Notice that the only dependency on q is in j0(q * t), and that it does not depend on z either. From the mathematical viewpoint it means that an integral of erf(...) * exp(...) over dz can be tabulated once as a function of t, say F(t) for the lack of better name, which then can be fed into the final integration as t * j0(q*t) * F(t).

Of course you'd need a lambda to interpolate tabulated values, and to manually take care of precision, and maybe do something else that dblquad does under the hood. Nevertheless, expect a thousand-fold speedup.


"Guess My Number", Alternative Edition This is an alternative edition of a game I modified the code for. See:

Guess My Number, Classic Edition

I seek advice on best practice. Tips, tricks, and suggestions, all welcome:

# Alex Grattan
# 9/10/14

# This is an alternative version of the "Guess My Number Game".
# The Computer now has the role of guessing a number chosen by the player.
# The Computer emulates the expected behaviour of a player -
# The Computer will not choose a number higher or lower than one already chosen.

import random

BOUNDS = (1, 100)
THE_NUMBER = int(input("\t\tPick a number between %r and %r:\n " % BOUNDS))
TRIES_ALLOWED = 7
PREVIOUS_GUESSES = {'Min': BOUNDS[0], 'Max': BOUNDS[1]}
TRIES = 0

print("""\n\t\tThe Computer will now attempt to guess your number in a minimum of attempts:\n
\t\tO.K. Computer, you have %d gusses. Proceed!\n""") % TRIES_ALLOWED

for x in range(TRIES_ALLOWED):

    GUESS = random.randint(PREVIOUS_GUESSES.get('Min'), PREVIOUS_GUESSES.get('Max'))
    print ("\t\t\t %d\n") % GUESS
    TRIES += 1

    if GUESS > THE_NUMBER:
        print("\t\tSorry Computer. Your guess of %d was too high.\n\t\tTake a lower guess:\n") % GUESS
        PREVIOUS_GUESSES['Max'] = GUESS - 1

    elif GUESS < THE_NUMBER:
        print("\t\tSorry Computer. Your guess of %d was too low.\n\t\tTake a higher guess:\n") % GUESS
        PREVIOUS_GUESSES['Min'] = GUESS + 1

    else:
        GUESS == THE_NUMBER
        print("""\tCongratulations Computer, you guessed it! The number was %d
        \t\tAnd it only took you %d tries!\n""") % (THE_NUMBER, TRIES)
        break
else:
    print("""Sorry Computer; you failed to guess the number!
    The number I chose was %d""") % THE_NUMBER

A common practice is to reserve all capital names for constants. As these variables change during the execution of the program, so they should be lowercased instead: PREVIOUS_GUESSES, TRIES, GUESS.

Inside this else, you have a pointless statement:

else:
    GUESS == THE_NUMBER  # <-- just delete this line... or at least comment it out

Using the .get method of dictionaries, for example in PREVIOUS_GUESSES.get('Min') and PREVIOUS_GUESSES.get('Max') can be useful when you're not sure if the keys (Min, Max in this example) exist,
and if they don't exist you don't want a KeyError raised.
In this script these keys are guaranteed to exist,
so you can safely (and consistently) use PREVIOUS_GUESSES['Min'] and PREVIOUS_GUESSES['Max'] everywhere.


Returning the common divisors of two integers I have written this function that returns the common divisors of two integers. When called recursively 10 times with big integers ranging in 100000000, it takes over 5 seconds. How can I improve it so that it is faster (less than 5 seconds)?

commonDivisors :: Int -> Int -> [Int]
commonDivisors x y = if x > y then divisors y x else divisors x y
    where divisors :: Int -> Int -> [Int]
          divisors z n = filter (\x -> n `mod` x == 0 && z `mod` x ==0) [1..n]

I don't know your application, but it seems rather uncommon to me that one would want a list of all common divisors.

To optimize your code, you could use Euclid's algorithm to find the greatest common divisor of the two numbers; this is much faster than iterating through all numbers less than your arguments.  Even more, the common divisors of your two numbers happen to be the divisors of the greatest common divisor.  Thus, the two-step process of finding the greatest common divisor and then finding all divisors of that greatest common divisor will be faster than your current method, since it does not usually have to consider all numbers up to the smaller factor.

An optimization for finding factors of a number \$n\$ would be only to iterate up to \$\sqrt n\$, adding to the list any factor \$k\$ you find as well as \$n / k\$.  A separate idea would be to compute the prime factorization of \$n\$ and finding the factors from that.


Parallel process interest in C# In web api controller:
I am a newer in parallel and Async&Task programming. Need someone help me code review.

public async Task<IHttpActionResult> DoWork()
{
    List<string> listTask = await Helper.GetBlockBlock();
    userIds = listTask;
    this.ParallelTaskWork();//step 1,must be finished,but I an not sure when..
    await this.Service.GetAllClientInterestInfoList();//executing after step 1
    return this.Ok();
}
public async void ParallelTaskWork()
{
    Task[] taskList = this.TaskMaker(totalNum);
}
public Task[] TaskMaker(int threadNum)
{
    Task[] taskList = new Task[threadNum];
    Parallel.For(0, taskList.Length, i => taskList[i] = new Task(this.ProcessDealTask));
    Parallel.ForEach(taskList, t => t.Start());
    return taskList;
}
private void ProcessDealTask()
{
    for (int i = 0; i < totalNum; i++)
    {
        List<string> users = this.GetPartitionOfList(userIds, i, totalNum);
        Task task = this.ParallelDealUserList(users);
        task.Wait();
    }
}
private List<T> GetPartitionOfList<T>(List<T> userList, int index, int total)
{
    int section = (userList.Count / total) + 1;
    int end = (index + 1) * section > userList.Count ? userList.Count - index * section : section;
    if (end < 0) end = 0;
        int start = index * section < userList.Count ? index * section : userList.Count - 1;
    if (start < 0) start = 0;
        return userList.GetRange(start, end);
}
private async Task ParallelDealUserList(IEnumerable<string> list)
{
    await Task.Run(() => Parallel.ForEach(list, async (id, loopState) =>
    {
        try
        {
            await GrainClient.GrainFactory.GetGrain<IUser>(id.ToGuid()).DoProcessInterestAsync(true);
        }
        catch (Exception e)
        {
        }
    }));
}

Any performance problem? The method ParallelDealUserList I refer to https://stackoverflow.com/questions/19102966/parallel-foreach-vs-task-run-and-task-whenall
somebody said

  there is a disadvantage to use Task.Run in a loop- With
  Parallel.ForEach, there is a Partitioner which gets created to avoid
  making more tasks than necessary

and  The method TaskMaker
https://stackoverflow.com/questions/22988630/parallel-for-w-action-that-creates-different-tasks-c-sharp

First thing is that you should limit the degree of parallelism, to ex: 4 threads

Parallel.ForEach(
    listOfWebpages,
    new ParallelOptions { MaxDegreeOfParallelism = 4 },
    webpage => { Download(webpage); }
);

Without this, you are going to DDoS your service or resource you are using.

You seem to be using Project Orleans and AFAIK a grain should be a single threaded container. You should be able to do just:

private void ParallelDealUserList(IEnumerable<string> list)
{
    foreach(var item in list)
        GrainClient
            .GrainFactory
            .GetGrain<IUser>(item.id.ToGuid())
            .DoProcessInterestAsync(true);
}

I am not all that familiar with Project Orleans. Most likely this can be used, but I would use microservices (aka SOA2) instead.


Review of three constructors for a String class I have the following declaration in my String.h file:

private:
    char* nstring;
    int nlength;
};

The following are three constructors I've implemented in String.cpp.  I would like these to be reviewed.

// Default constructor for this class. Initializes an empty string.
string::string() {
    nlength = 1; // for "\0" terminating character at the end of the char array
    nstring = new char[nlength];
    nstring[nlength - 1] = '\0';
}

// Constructor for String class. Initializes a string based on the given C string.
string::string(const char* input) {
    nlength = strlen(input) + 1;
    nstring = new char[nlength];
    for (int i = 0; i < (nlength - 1); i++) {
        nstring[i] = input[i];
    }
    nstring[(nlength - 1)] = '\0';
}

// Copy constructor for String class.
// Initializes a string from an already existing string.
// The contents of the existing string should be copied over to this string.
string::string(const string& S) {
    nlength = S.nlength;
    nstring = new char[nlength];
    for (int i = 0; i < (nlength - 1); i++) {
        nstring[i] = S.nstring[i];
    }
    nstring[(nlength - 1)] = '\0';
}

Your lengths are off by 1 everywhere. An empty string has length 0 not 1, "Hello" has length 5 not 6, etc.

Your constructor from the const char* can just assign every character in the loop (since we know the nlengthth character of input will be \0, right? Even better would be to use memcpy:

nlength = strlen(input);
nstring = new char[nlength + 1];
memcpy(nstring, input, nlength + 1);

Also you have to be careful on the copy constructor. What happens in this code?

string hello("hello");
hello = hello;


Randomizing Civilization 5 team choice This macro is made to randomly draw specific number of civilization choices for a specific number of Civ V players. It is based on a list of 43 possibilities and the for loop in the while loop checks for already picked civilizations. Constant cell references point to values obtained with scroll-bars in the worksheet. The variable based cell references are made to structure the results in a two-column design.

Are there any smart ways to make my code better from both an aesthetic as well as functional view?

Sub CIV_draw()
Range("K2:M50").ClearContents
Dim x As Integer
x = Cells(3, 3).Value
For i = 1 To x
    Cells(3 + (Cells(3, 7).Value + 2) * (i - 1), 11).Value = "Player " & i
    For j = 1 To Cells(3, 7).Value
        Dim Rand_CIV As String
        Dim RandNum As Integer
        Dim checkVal As Boolean
        checkVal = False
        While checkVal = False
            RandNum = CInt(Int(43 * Rnd())) + 1
            Rand_CIV = Cells(RandNum, 16).Value & " (" & Cells(RandNum, 15).Value & ")"
            For Z = 1 To 50
                If Cells(Z, 12) = Rand_CIV Then
                    Exit For
                End If
                If Z = 50 Then
                    checkVal = True
                End If
            Next Z
        Wend

        Cells((Cells(3, 7).Value + 2) * (i - 1) + (j + 3), 12).Value = Rand_CIV
    Next j
Next i
End Sub

I know for example that my duplicate check isn't optimal, and I would like to get suggestions for alternative solutions.

Well, Rubberduck only indicates one issue.

  Rubberduck Code Inspections - 3/8/2015 12:56:11 PM
  1 issue found.
  Suggestion: Member 'CIV_draw' is implicitly Public - VBAProject.Module1, line 3

Implicit Public Member documentation

So, you're off to a good start. You can correct this by explicitly declaring the Subroutine's scope.

Public Sub CIV_draw()

Personally, I would also ditch the prefix and just call this routine Draw(). The underscore holds a special place in VBA. It typically denotes either an Event procedure or an Interface implementation, so I would avoid using underscores in procedure names elsewhere.

The next thing I notice is that you're calling the Range() and Cells() methods without specifying a worksheet. This means you're implicitly calling these methods on the ActiveSheet. This should be avoided because it leaves a small chance that the user will change the worksheet while the code is executing. You should instead create a worksheet variable that gets set at the very beginning, then work with that instead.

Dim ws As Worksheet
Set ws = ThisWorkbook.ActiveSheet

ws.Range("K2:M50").ClearContents
' ...

There are also a lot of magic numbers in your code, but I'll get back to that. First, let's talk about extracting some well named methods. The random number logic is a good one to extract out. When reading this method, we don't care really how the random number is generated, only that we are getting one.

RandNum = CInt(Int(43 * Rnd())) + 1

Private Function GetRandomNum() As Integer
    GetRandomNum = CInt(Int(43 * Rnd())) + 1
End Function

Next is the business of getting a random civilization string.

Private Function GetRandomCivilization(ByVal RandNum As Integer, ByVal ws As Worksheet) As String
    GetRandomCivilization = ws.Cells(RandNum, 16).Value & " (" & ws.Cells(RandNum, 15).Value & ")"
End Function

This is already making your code more readable at a high level. If anyone wants the details, they can dig into these private functions. We've also entirely eliminated a variable by doing this.

Dim RandCivilization As String
Dim checkVal As Boolean

checkVal = False
While checkVal = False
    RandCivilization = GetRandomCivilization(GetRandomNum(), ws)
    For Z = 1 To 50

Next let's clean up your While loop a bit.

Dim checkVal As Boolean

checkVal = False
While checkVal = False

Next, let's flip the logic to use a Not condition.

Dim checkVal As Boolean
checkVal = False

While Not checkVal

And finally, give it a better name.

Dim endOfRange As Boolean
endOfRange = False

While Not endOfRange

The next order of business is to extract this duplicated logic into its own method.

(ws.Cells(3, 7).Value + 2)

Private Function GetNumberOfCivilizations(ByVal ws As Worksheet)
    GetNumberOfCivilizations = ws.Cells(3, 7).Value
End Function

Which brings the current state of the code to this.

Public Sub Draw()
    Dim ws As Worksheet
    Set ws = ThisWorkbook.ActiveSheet

    ws.Range("K2:M50").ClearContents

    Dim x As Integer
    x = ws.Cells(3, 3).Value

    Dim numberOfCivs As Integer
    numberOfCivs = GetNumberOfCivilizations()

    Dim i As Long
    For i = 1 To x
        ws.Cells(3 + (numberOfCivs + 2) * (i - 1), 11).Value = "Player " & i

        Dim j As Long
        For j = 1 To numberOfCivs
            Dim RandCivilization As String
            Dim endOfRange As Boolean

            endOfRange = False
            While Not endOfRange
                RandCivilization = GetRandomCivilization(GetRandomNum(), ws)

                Dim z As Long
                For z = 1 To 50
                    If ws.Cells(z, 12) = RandCivilization Then
                        Exit For
                    End If
                    If z = 50 Then
                        endOfRange = True
                    End If
                Next z
            Wend

            ws.Cells((numberOfCivs + 2) * (i - 1) + (j + 3), 12).Value = RandCivilization
        Next j
    Next i
End Sub

Private Function GetNumberOfCivilizations(ByVal ws As Worksheet)
    GetNumberOfCivilizations = ws.Cells(3, 7).Value
End Function

Private Function GetRandomNum() As Integer
    GetRandomNum = CInt(Int(43 * Rnd())) + 1
End Function

Private Function GetRandomCivilization(ByVal RandNum As Integer, ByVal ws As Worksheet) As String
    GetRandomCivilization = ws.Cells(RandNum, 16).Value & " (" & ws.Cells(RandNum, 15).Value & ")"
End Function

That's an improvement, but we're still dealing with a lot of numbers that don't mean much to us until we reference back to the actual worksheet. Let's define constant values for them and some functions that are responsible for getting data from the worksheet.

Private Function GetNumberOfPlayers(ByVal ws As Worksheet) As Integer
    GetNumberOfPlayers = ws.Cells(3, 3).Value
End Function

And yet another function to get the range we're writing the results to.

Private Function GetResultsRange(ByVal ws As Worksheet) As Range
    Set GetResultsRange = ws.Range("K2:M50")
End Function

Now, note that we're referencing the column positions within the results range, instead of the position relative to the worksheet. This is easier for a person to comprehend while only looking at the code.

Public Sub Draw()
    Dim ws As Worksheet
    Set ws = ThisWorkbook.ActiveSheet

    Dim resultsRange As Range
    Set resultsRange = GetResultsRange(ws)
    resultsRange.ClearContents

    Dim numOfPlayers As Integer
    numberOfPlayers = GetNumberOfPlayers()

    Dim numberOfCivs As Integer
    numberOfCivs = GetNumberOfCivilizations()

    Dim i As Long
    For i = 1 To numberOfPlayers
        resultsRange.Cells(3 + (numberOfCivs + 2) * (i - 1), 1).Value = "Player " & i

        Dim j As Long
        For j = 1 To numberOfCivs
            Dim RandCivilization As String
            Dim endOfRange As Boolean

            endOfRange = False
            While Not endOfRange
                RandCivilization = GetRandomCivilization(GetRandomNum(), ws)

                Dim z As Long
                For z = 1 To resultsRange.Rows.Count
                    If resultsRange.Cells(z, 2) = RandCivilization Then
                        Exit For
                    End If
                    If z = resultsRange.Rows.Count Then
                        endOfRange = True
                    End If
                Next z
            Wend

            resultsRange.Cells((numberOfCivs + 2) * (i - 1) + (j + 3), 2).Value = RandCivilization
        Next j
    Next i
End Sub

At this point, you should be getting the idea. Keep extracting well named functions until there's no duplicated or obscure logic left in your main routine. This snippet would be my next target.

(numberOfCivs + 2) * (i - 1)

As well as a couple of subs that are responsible for writing the data into the results range.

The code as it was in my IDE when I stopped reviewing:

Option Explicit

Public Sub Draw()
    Dim ws As Worksheet
    Set ws = ThisWorkbook.ActiveSheet

    Dim resultsRange As Range
    Set resultsRange = GetResultsRange(ws)
    resultsRange.ClearContents

    Dim numOfPlayers As Integer
    numberOfPlayers = GetNumberOfPlayers()

    Dim numberOfCivs As Integer
    numberOfCivs = GetNumberOfCivilizations()

    Dim i As Long
    For i = 1 To numberOfPlayers
        resultsRange.Cells(3 + (numberOfCivs + 2) * (i - 1), 1).Value = "Player " & i

        Dim j As Long
        For j = 1 To numberOfCivs
            Dim RandCivilization As String
            Dim endOfRange As Boolean

            endOfRange = False
            While Not endOfRange
                RandCivilization = GetRandomCivilization(GetRandomNum(), ws)

                Dim z As Long
                For z = 1 To resultsRange.Rows.Count
                    If resultsRange.Cells(z, 2) = RandCivilization Then
                        Exit For
                    End If
                    If z = resultsRange.Rows.Count Then
                        endOfRange = True
                    End If
                Next z
            Wend

            resultsRange.Cells((numberOfCivs + 2) * (i - 1) + (j + 3), 2).Value = RandCivilization
        Next j
    Next i
End Sub

Private Function GetNumberOfCivilizations(ByVal ws As Worksheet)
    GetNumberOfCivilizations = ws.Cells(3, 7).Value
End Function

Private Function GetRandomNum() As Integer
    GetRandomNum = CInt(Int(43 * Rnd())) + 1
End Function

Private Function GetRandomCivilization(ByVal RandNum As Integer, ByVal ws As Worksheet) As String
    GetRandomCivilization = ws.Cells(RandNum, 16).Value & " (" & ws.Cells(RandNum, 15).Value & ")"
End Function

Private Function GetNumberOfPlayers(ByVal ws As Worksheet) As Integer
    GetNumberOfPlayers = ws.Cells(3, 3).Value
End Function

Private Function GetResultsRange(ByVal ws As Worksheet) As Range
    Set GetResultsRange = ws.Range("K2:M50")
End Function


C++ implementation of the observer design pattern Started learning design patterns using C++. Below is an implementation of the Observer Pattern. Two abstract class templates Observer and Subject define the required interfaces. Two specific implementation ConcreteObserver and ConcreteSubject are defined to test the interfaces (I have not found good generic real-life examples that I like for the Observer Pattern, and so decided to go with ConcreteWhatever).

In this implementation, the subject pushes the state change to the observers.

#include <iostream>
#include <set>

// interfaces

template <typename T>
class Observer {
public:
    virtual void update(T subjectState)=0;
};

template <typename T>
class Subject {
public:
    virtual void registerObserver(Observer<T>* ptr_observer) = 0;
    virtual void unregisterObserver(Observer<T>* ptr_observer) = 0;
    virtual void notifyObservers() = 0;
};

// implementations

template <typename T>
class ConcreteObserver : public Observer<T> {
    Subject<T>* ptr_subject;
    T subjectState;
public:
    ConcreteObserver(Subject<T>* ptr_subject) : ptr_subject(ptr_subject) {
        std::cout << "Concrete observer " << this << " created to observe " << ptr_subject << std::endl;
        ptr_subject->registerObserver(this);
    }

    void update(T subjectState) {
        this->subjectState = subjectState;
        std::cout << "Observer " << this << " notified of subject " << ptr_subject << " state change to " << subjectState << std::endl;
    }

    void currentSubject(Subject<T>* ptr_subject) {
        ptr_subject->registerObserver(this);
        this->ptr_subject = ptr_subject;
    }

    ~ConcreteObserver() {
        ptr_subject->unregisterObserver(this);
    }
};

template <typename T>
class ConcreteSubject : public Subject<T> {
    std::set<Observer<T>*> observers;
    T state;
public:
    ConcreteSubject(T state) : state(state) {
        std::cout << "Concrete subject " << this << " created with state " << state << std::endl;
    }

    void registerObserver(Observer<T>* ptr_observer) {
        observers.insert(ptr_observer);
        std::cout << "Subject " << this << " registered observer " << ptr_observer << std::endl;
    }

    void unregisterObserver(Observer<T>* ptr_observer) {
        observers.erase(ptr_observer);
        std::cout << "Subject " << this << " unregistered observer " << ptr_observer << std::endl;
    }

    void notifyObservers() {
        for (std::set<Observer<T>*>::iterator iter = observers.begin(); iter != observers.end(); iter++) {
            (*iter)->update(state);
        }
    }

    void stateChanged() {
        notifyObservers();
    }

    T getState() {
        return state;
    }

    void setState(T state) {
        this->state = state;
        std::cout << "State of subject " << this << " changed to " << state << std::endl;
        stateChanged();
    }
};

int main() {
    std::cout << "Testing Subject-Observer implementation:" << std::endl;

    ConcreteSubject<int>* ptr_subject = new ConcreteSubject<int>(42);

    ConcreteObserver<int>* ptr_observer_1 = new ConcreteObserver<int>(ptr_subject);
    ConcreteObserver<int>* ptr_observer_2 = new ConcreteObserver<int>(ptr_subject);
    ConcreteObserver<int>* ptr_observer_3 = new ConcreteObserver<int>(ptr_subject);

    ptr_subject->setState(19);

    ptr_subject->unregisterObserver(ptr_observer_3);

    ptr_subject->setState(13);

    delete ptr_subject;

    getchar();
}

Design Review

Ownership

One of the advances of C++ over is C is ownership semantics. We understand who owns an object (and thus who is responsible for destroying the object). We do this by using a set of helper classes that explicitly state ownership or pass by reference to indicate non ownership.

The trouble with pointers is that they have no ownership semantics. You can't tell from their usage who is supposed to own the pointer and thus you can not tell who is responsible for deleting the object. Thus in C++ it is highly discouraged to use RAW pointers in public interfaces (I am not saying are not used, I am saying is that their normally place is deep inside a class so their ownership is very obvious and not normally exposed in public interfaces).

In you interface you never transfer ownership and you have both a register and unregister method on the subject. So that interface can be easily changed to show the ownership is not part of the interface.

template <typename T>
class Subject {
public:
    virtual void registerObserver(Observer<T>& ptr_observer) = 0;
    virtual void unregisterObserver(Observer<T>& ptr_observer) = 0;
    virtual void notifyObservers() = 0;
};

Please note I changed the * to &. This shows you are not passing ownership but you will always pass an observer. The additional upside is that you can no longer pass nullptr as an observer (you forgot to check to see if the pointer was nullptr and thus had a potential for calling a method on a nullptr (not a good idea).

Passing by value:

Here you pass the subjectState by value.

class Observer {
public:
    virtual void update(T subjectState)=0;
};

If T is large or complex then this is probably not a good idea. Pass a reference to the object. If the subject wants a copy they can explicitly make a decision to copy the object when they receive it (they have enough context to make an intelligent choice). So pass by reference instead.

class Observer {
public:
    virtual void update(T const& subjectState)=0;
              //          ^^^^^^  Normally I would pass by const ref.
              //                  But there is a case for passing by ref
              //                  as this allows each subject to mutate the
              //                  state of the object that is detectable
              //                  by other observers.
};

Virtual Destructors

If a class has virtual methods then you should have a virtual destructor.

The compiler will warn you about this if you turn up the warning level.

Override

When you override virtual methods you should add override to the method declaration.

The compiler will warn you about this if you turn up the warning level.

Code Review

Prefer to use the range based for when looping over a container.

        for (std::set<Observer<T>*>::iterator iter = observers.begin(); iter != observers.end(); iter++) {
            (*iter)->update(state);
        }

One thing you should change is the increment. It is slightly more efficient to use prefix increment (though the compiler probably compensates automatically). But it also makes your code look more modern.

        for (std::set<Observer<T>*>::iterator iter = observers.begin(); iter != observers.end(); ++iter) {
            (*iter)->update(state);
        }

This works. But it is a bit verbose.
In C++11 we made this easier with auto which makes the compiler do the work of working out the type.

        for (auto iter = observers.begin(); iter != observers.end(); ++iter) {
            (*iter)->update(state);
        }

In C++14 we added std::begin() and std::end() functions to make the above more generic and work with arrays as well as standard containers.

        for (auto iter = std::begin(observers); iter != std::end(observers); ++iter) {
            (*iter)->update(state);
        }

Also in C++14 we added the range based for:
The below loop is basically syntactic sugar (though it only calls std::end() once in C++17) for the previous loop I wrote.

        for (auto const& item: observers) {
            item->update(state);
        }

Const correctness.

Const correctness is really hard to add in afterwords (believe me). So best to start with your classes with it already in place. So any method that does not mutate the state of the object should be marked const

    void stateChanged() const {  // I added the cost here.
        notifyObservers();
    }

This class should be const and return by reference.

    T const& getState() const { // Notice the 2 `const` on this.
        return state;
    }

Move semantics and efficiency.

Copy semantics are good for simple types. But move semantics allow you a very effecient way of adding an object to another object. So you should learn how to move or construct in place an object.

    // Your version forces two copies.
    // You have a copy when you call setState to put the object
    // into the parameter `state` then you have a second copy
    // when you assign to `this->state`
    void setState(T state) {      // Copy here
        this->state = state;      // Copy here
        stateChanged();
    }

If T was large thats a lot of extra copying.
You should replace this with three methods:

    void setState(T const& newState) {   // Pass by reference avoid copy.
        state = state;
        stateChanged();
    }

    void setState(T&& newState) {        // Pass by RValue-Ref avoid copy.
        state = std::move(newState);     // Then move over current state.
        stateChanged();
    }

    // Advanced technique
    template<typename... A>
    void setState(A&&... args) {             // Pass arguments to construct a T by ref
        state = T(std::forward<A>(args)...); // Build the state in place.
        stateChanged();
    }

Don't use this-> it hides errors.

        this->state = state;

The only reason to use this-> is to distinguish a member that has been shadowed by a local variable (like a parameter). The problem is that it is error prone.

You must always remember to use this-> to use the local member otherwise you will accidentally use the local variable. If you forget there is no compiler warning that will help you.

On the other hand the compiler will warn you when you have shadowed variables. So if you never have a shadowed variable you can never accidentally use the wrong one.

Thus it is discouraged to use this-> as you are just setting yourself up for a hidden error. Rather make the compiler warn you about shadowed variables and use an appropriate name so it does not shadow.

Prefer '\n' over std::endl

    std::cout << "Testing Subject-Observer implementation:" << std::endl;

The difference between the two is a flush of the stream (done by std::endl). Flushing done by the user is one of the main speed slow downs in C++ code over C. The streams will already flush themselves at the optimal time, so a manual flush will usually retard performance.

Prefer to use automatic variables.

    ConcreteSubject<int>* ptr_subject = new ConcreteSubject<int>(42);

This is not Java. You don't need to new objects to create them you can just declare them locally.

    // This creates a local object
    ConcreteSubject<int> ptr_subject(42);

Using pointers like this (RAW pointers) is also discouraged as it very dangerous. If an exception occurs you will leak the pointer. You also have to keep track of the object and remember to call delete on it, which is error prone (as shown by a decades worth of C code). So we usually use wrappers to make sure the delete is called automatically.

    std::unique_ptr<ConcreteSubject<int>> aPointer std::make_unique<ConcreteSubject<int>>(42);

This is a pointer held inside an object wrapper. When it goes out of scope it will automatically be destroyed, this calls the destructor, which calls delete on the contained pointer.

As an example:

    ConcreteObserver<int>* ptr_observer_1 = new ConcreteObserver<int>(ptr_subject);

I see no call to delete for this object. So you just leaked it.


Safe multiplication of two 64-bit signed integers The function below implements safe multiplication of two 64-bit signed integers, preventing overflow from occurring:

// Multiplies two 64-bit signed ints if possible.
// Returns 0 on success, and puts the product of x and y into the result.
// Returns 1 if there was an overflow.
int int64_mult(int64_t x, int64_t y, int64_t * result)
{
    *result = 0;
    if (x > 0 && y > 0 && x > INT64_MAX / y) return 1;
    if (x < 0 && y > 0 && x < INT64_MIN / y) return 1;
    if (x > 0 && y < 0 && y < INT64_MIN / x) return 1;
    if (x < 0 && y < 0 && (x <= INT64_MIN || y <= INT64_MIN || -x > INT64_MAX / -y))
        return 1;
    *result = x * y;
    return 0;
}

Did I get the logic for detecting overflows right?  I am most interested in making sure that no undefined behavior will occur, and that the function will always return the right results.

We can assume that int64_t will be a two's complement integer, because this is for GCC and GCC does not support any other type of integer.

For the convenience of the code reviewers (you), I made a complete, self-contained test suite that you can just run in your favorite C/C++ environment:

https://gist.github.com/DavidEGrayson/06cf7ea73f82a05490ba

I am not too interested in code style issues.  I am aware it might be nice to assert that the output pointer is not null, and it might be nice to add braces and parentheses.  But really I want to know if the code is actually correct.

I am somewhat interested in making the code simpler if you have a way to do that; maybe some of the cases could be combined.

I am also aware that the logic might be easier if I just used a 128-bit integer to store the multiplication result, but I would like to get it right without doing that.

The reason I am asking this is because I am working on adding intsafe.h to mingw-w64 (a GCC compiler for Windows), so I am implementing safe multiplication of signed and unsigned numbers.  This function is analogous to LongLongMult in intsafe.h.  Your contribution will help make this header safer.  You can see my progress here.

Given that you are writing for gcc, is there a reason you're not using the builtins?

bool __builtin_add_overflow (type1 a, type2 b, type3 *res)
bool __builtin_sub_overflow (type1 a, type2 b, type3 *res)
bool __builtin_mul_overflow (type1 a, type2 b, type3 *res)

But as to your question, it looks correct to me, modulo the answer by the other poster.


Formatting a list of strings as a comma-separated string I'm learning Haskell on my own and I'm following the material of a course.

I would like to know if this is idiomatic Haskell.

asList :: [String] -> String
asList ss = "[" ++ (concat $ intersperse "," ss) ++ "]"

It looks idiomatic to me.

There's one slight improvement to the code that I could come up with.  There is a function that does what you're doing in the middle, called intercalate.  Here's the definition, from Data.List:

intercalate :: [a] -> [[a]] -> [a]
intercalate xs xss = concat (intersperse xs xss)

Using that, your function becomes:

asList :: [String] -> String
asList ss = "[" ++ (intercalate "," ss) ++ "]"


Generate a find command with pruned directories based on a config file The idea is to perform indexing of filetrees while excluding certain directories. I want to give the user a simple conf file instead of having to edit the script itself.
This is what I came up with:
conf.file:
cache
home/files

program:
#!/usr/bin/env bash

function get_opts {
        while read opt
        do
        echo "-path /data/data/com.termux/$opt -prune -o \\" >> fn_temp
        done < conf.file
}

function build_search_fn {
        touch fn_temp
        echo "function do_search {" > fn_temp
        echo "find /data/data/com.termux \\" >> fn_temp
        get_opts
        echo "-print" >> fn_temp
        echo "}" >> fn_temp
}

build_search_fn
source fn_temp
do_search >> output

It does what I want, but I have a strong feeling that it's not the 'proper' way of doing it. Besides the obvious lack of putting the base path into variables and some errorhandling I'm eager to learn about other approaches to do this.

You can use subcommands in a command:
echo "This $(date) is a date calculated in the echo command"

When you don't need additional control statements, you can use combined code like:
find /data/data/com.termux \
   $(awk '{printf("-path %s%s -prune -o ", "/data/data/com.termux/", $0)}' conf.file) \
   -print >> output

The awk command might be new for you, it is a replacement for your loop over the conf file. The same result can be found with sed:
sed 's#.*#/data/data/com.termux/& -prune -o #' conf.file

I think awk is the best here.


UVa Challenge Problem 100: 3n+1 code I have written this code for UVa Challenge 100:

#include<iostream>
using namespace std;
int main(){
int i,j,a,b,k,tot,gtot;
while(cin>>i>>j){
gtot=0;
a=i<j?i:j;
b=i<j?j:i;
for(int l=a;l<=b;l++){
tot=1;k=l;
while(k!=1){
tot++;
if((k%2)==0)k=k/2;
else k=(3*k)+1;
}

if(tot>gtot) gtot=tot;
}
cout<<i<<" "<<j<<" "<<gtot<<endl;
}
return 0;
}

The challenge is about finding the length of the longest Collatz sequence in a given range. Each input row contains two numbers, the minimum and maximum sequence start number to check. After calculating the maximum length of all sequences starting with a number in this range, this lentgh must be printed together with the given inputs.

My code produces the correct output for the given examples so I think it is correct but the online judge disagrees.

Formatting/Indentation

Your code as posted here has a horrible formatting which makes it hard to read and understand. You add a level of indentation for each nesting level (each {} block).

Extracting functions

All your code is in the main function which increases dependencies and reduces readability. Consider extracting independent tasks into own functions like.

a function to get the next number in the collatz sequence from the current one
a function to measure the length from a number to 1 in the collatz sequence
a function to build the maximum of this length for a range of integers

Then your main function would only consist of the code for reading the input and printing the output (which might also be moved into own functions as well)

C vs C++

As you are using C++ you should take advantage of its features. For example in C++ you don't need to declare all variables up front. This allows you to declare them as late as possible (when they are needed).

C++ also does not require return 0; at the end of main. If execution reaches the end the return 0; will be automatically done by the compiler.

Use std algorithms

I don't think it is really necessary but your code stores the minimum and maximum of i and j in a and b (not necessary because the task seems to guarantee that i <= j). You are doing this calculation on your own which adds burden on the reader to understand what you are doing. There are std algorithms for this:

a = std::min(i, j);

Naming

All your variables have far too short and undescriptive naming. Ideally, a reader should know from the name of a variable what it is for. In your case this is not possible. I would suggest:

i -> first_input (or start_number if it is guaranteed to be less or equal the j)
j -> second_input (or stop_number)
a, b according to the suggestions above if you still use them
l -> current_sequence_start
tot -> current_sequence_length
gtot -> maximal_sequence_length
k -> current_sequence_number

Don't using namespace std;

This can become a problem later on so don't get used to it. Typing std:: is not that bad and if it becomes too bad you still can do using std::cout; to avoid the "lengthy" names.

Putting all this together I get the following code

#include <iostream>
#include <algorithm>
#include <cassert>

/**
 * @brief Get the next number in the collatz sequence from the current one
 */
int next_collatz(int current_collatz) {
  return current_collatz % 2 == 0 ? current_collatz / 2
                                  : 3 * current_collatz + 1;
}

/**
 * @brief Count the number of steps in the collatz sequence from current_number
 *        to 1
 */
int count_collatz_steps_until_1(int current_number) {
  int counter = 1;
  while (current_number != 1) {
    ++counter;
    current_number = next_collatz(current_number);
  }
  return counter;
}

/**
 * @brief Find the maximum of the lengths of the collatz sequence for each
 *        number bewteen start_number and end_number (inclusive)
 */
int maximal_collatz_sequence_length(int start_number, int end_number) {
  assert(start_number <= end_number);
  int maximum_sequence_length = 0;
  for (int current_number = start_number; current_number <= end_number;
       current_number++) {
    int current_sequence_length = count_collatz_steps_until_1(current_number);
    maximum_sequence_length =
        std::max(maximum_sequence_length, current_sequence_length);
  }
  return maximum_sequence_length;
}

int main() {
  int first_input, second_input;
  while (std::cin >> first_input >> second_input) {

    int start_number = std::min(first_input, second_input);
    int end_number = std::max(first_input, second_input);

    std::cout << first_input << " " << second_input << " "
              << maximal_collatz_sequence_length(start_number, end_number)
              << std::endl;
  }
}

This should be an improvement in clarity but not in speed as it is the same algorithm.


Using reduce twice in a row for Run Length Encoding First of all, I'm new to Lisp (I currently use CLISP and SBCL). There probably are huge mistakes in this code so any guidelines are welcome :)

I'm very confused about how to do this. It's just about a habit and I don't want my actual help to implement an algorithm, as the one I came up with is not the best one.

Is it okay to use reduce twice in a row on the same list? (it is not exactly the same list as it has been reduced, but I hope you get my point)

Here the algorithm is pretty much the same as the run-length encoding the only differences I see are:

when a letter occurs only once, it has no number indication
the number of occurrences of a letters is put on the right instead of the left

For example:

input: aabcbaaabbbcc

output: a2bcba3b3c2

The steps I have chosen to do are these:

Convert the string input to a char list (\#a \#a \#b etc.)
Use reduce to transform the char list to ((\#a \#a) (\#b) etc.)
Transform the new list to a string using reduce again (this is where I'm wondering if the previous step should not be a reduce but a map)

I have implemented the 2 first steps of this algorithm here:

(defun compress-reduce (prev curr)
  ;prev is always a 2d list -> ex: ((a) (b))
  ;curr is always a char
  (format t "prev: ~A | curr: ~A | " prev curr)
  (let ((last-seq (nth 0 (last prev)))
        (last-char (nth 0 (nth 0 (last prev)))))

    (format t "last-seq: ~A | last-char: ~A~%" last-seq last-char)

    (if
      (= (char-int last-char) (char-int curr))
      (and (push curr last-seq)
           (setf (nth (- (length prev) 1) prev) last-seq) prev)
      (append prev (list (list curr))))))

(defun compress ()
  (let ((l (coerce "abcccbbabaaa" 'list) ))

    ; reduce
    (format t "~A" (reduce #'compress-reduce l :initial-value (list (list (nth 0 l)))))))

(format t "~A" (compress))

This always outputs:

prev: ((a)) | curr: a | last-seq: (a) | last-char: a
prev: ((a a)) | curr: b | last-seq: (a a) | last-char: a
prev: ((a a) (b)) | curr: c | last-seq: (b) | last-char: b
prev: ((a a) (b) (c)) | curr: c | last-seq: (c) | last-char: c
prev: ((a a) (b) (c c)) | curr: c | last-seq: (c c) | last-char: c
prev: ((a a) (b) (c c c)) | curr: b | last-seq: (c c c) | last-char: c
prev: ((a a) (b) (c c c) (b)) | curr: b | last-seq: (b) | last-char: b
prev: ((a a) (b) (c c c) (b b)) | curr: a | last-seq: (b b) | last-char: b
prev: ((a a) (b) (c c c) (b b) (a)) | curr: b | last-seq: (a) | last-char: a
prev: ((a a) (b) (c c c) (b b) (a) (b)) | curr: a | last-seq: (b) | last-char: b
prev: ((a a) (b) (c c c) (b b) (a) (b) (a)) | curr: a | last-seq: (a) | last-char: a
prev: ((a a) (b) (c c c) (b b) (a) (b) (a a)) | curr: a | last-seq: (a a) | last-char: a
((a a) (b) (c c c) (b b) (a) (b) (a a a))NIL

Algorithm

Your algorith is quadratic for no good reason because last and length
are linear in list length.

I suggest that you add new elements to the beginning instead of the
end of the return value in compress-reduce and
nreverse
it in compress.

Style

Avoid nth 0 in favor of car.

(= (char-int last-char) (char-int curr)) is better written as (char= last-char curr).

Avoid mixing and and push: keep conditions in and and side-effects
(like push) in progn.

Repeated reduce and map

Each map
(and mapcar et al)
allocates a fresh list, so doing a repeated map can waste memory (and
garbage collection cycles), so either using
map-into
or an explicit function composition is a good idea: instead of

(mapcar #'foo (mapcar #'bar my-list))

use either

(let ((res (mapcar #'bar my-list)))
  (map-into res #'foo res))

or

(mapcar (lambda (x) (foo (bar x))) my-list)

However, no such allocation happens with reduce
so there is no reason to avoid nested reduces.

Note that the proverbial "sufficiently smart compiler" should be able to
handle these problems (but not necessarily the quadraticity above!), so
you should only worry about this if you discover it to be the
performance bottleneck.

Remember (SICP):

  ... a computer language is not just a way of getting a computer to
  perform operations, but rather ... it is a novel formal medium for
  expressing ideas about methodology


Can these unit tests be improved? I'm not the greatest at writing tests yet and I'm starting a new OSS project for learning and as part of it I want to tackle being more effective at writing tests, more specifically quality tests. I think I write a lot of tests that don't bring much value except maintenance pain sometimes.

Can I improve these tests?

using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using FakeItEasy;
using HaywireMQ.Server.Channel;
using HaywireMQ.Server.MessageStore;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Ploeh.AutoFixture;
using Ploeh.AutoFixture.AutoFakeItEasy;

namespace HaywireMQ.Server.Tests
{
    /// <summary>
    /// Tests for HaywireServer
    /// </summary>
    [TestClass]
    public class HaywireServerTests
    {
        private IFixture fixture;

        public HaywireServerTests()
        {
        }

        [TestInitialize]
        public void Initialize()
        {
            fixture = new Fixture().Customize(new AutoFakeItEasyCustomization());
        }

        [TestMethod]
        public void Should_use_defaults_without_ModuleCatalog()
        {
            // Given
            var target = new HaywireServer();

            // When
            target.Start();

            // Then
            Assert.AreEqual<Type>(target.MessageStore.GetType(), typeof(InMemoryMessageStore));
            Assert.AreEqual<Type>(target.MessageChannel.GetType(), typeof(InMemoryMessageChannel));
        }

        [TestMethod]
        public void Should_use_ModuleCatalog()
        {
            // Given
            var catalog = new ModuleCatalog();
            var messageStore = fixture.CreateAnonymous<IMessageStore>();
            var messageChannel = fixture.CreateAnonymous<IMessageChannel>();
            catalog.MessageStores.Add(messageStore);
            catalog.MessageChannels.Add(messageChannel);
            var target = new HaywireServer(catalog);

            // When
            target.Start();

            // Then
            Assert.AreEqual<Type>(target.MessageStore.GetType(), messageStore.GetType());
            Assert.AreEqual<Type>(target.MessageChannel.GetType(), messageChannel.GetType());
        }

        [TestMethod]
        public void Should_create_MessageQueue()
        {
            // Given
            var catalog = new ModuleCatalog();
            var messageStore = fixture.CreateAnonymous<IMessageStore>();
            var messageChannel = fixture.CreateAnonymous<IMessageChannel>();
            catalog.MessageStores.Add(messageStore);
            catalog.MessageChannels.Add(messageChannel);
            var target = new HaywireServer(catalog);

            List<string> ids = new List<string>() {"test"};

            A.CallTo(() => messageStore.GetQueues()).Returns(ids);

            // When
            target.Start();

            // Then
            A.CallTo(() => messageStore.GetQueues()).MustHaveHappened();
            Assert.AreEqual<int>(target.MessageQueues.Count, 1);
            Assert.AreEqual<string>(target.MessageQueues[0].Id, "test");
        }
    }
}

Assuming that I've correctly managed to extrapolate the SUT and friends from the question, I'd reduce the tests to the following. Please note that this focuses only on AutoFixture mechanics, and not on the general design of neither test nor SUT API.

AFAICT, the following tests state the same as the tests in the OP, but reduced to only the necessary statements. Still, I agree with Nikos Baxevanis that it would be possible to reduce these tests dramatically with xUnit.net instead of MSTest.

using System.Collections.Generic;
using System.Linq;
using FakeItEasy;
using FirstAutoFixtureReviewForKellySommers;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Ploeh.AutoFixture;
using Ploeh.AutoFixture.AutoFakeItEasy;
using Ploeh.AutoFixture.Kernel;

namespace HaywireMQ.Server.Tests
{
    /// <summary>
    /// Tests for HaywireServer
    /// </summary>
    [TestClass]
    public class HaywireServerTests
    {
        [TestMethod]
        public void Should_use_defaults_without_ModuleCatalog()
        {
            // Given
            var fixture = new Fixture().Customize(new TestConventions());

            // When
            var target = fixture.CreateAnonymous<HaywireServer>();

            // Then
            Assert.IsInstanceOfType(target.MessageStore, typeof(InMemoryMessageStore));
            Assert.IsInstanceOfType(target.MessageChannel, typeof(InMemoryMessageChannel));
        }

        [TestMethod]
        public void Should_use_ModuleCatalog()
        {
            // Given
            var fixture = new Fixture().Customize(new TestConventions());

            var catalog = fixture.Freeze<ModuleCatalog>();
            fixture.AddManyTo(catalog.MessageStores, 1);
            fixture.AddManyTo(catalog.MessageChannels, 1);

            // When
            var target = fixture.CreateAnonymous<HaywireServer>();

            // Then
            Assert.AreEqual(catalog.MessageStores.Single(), target.MessageStore);
            Assert.AreEqual(catalog.MessageChannels.Single(), target.MessageChannel);
        }

        [TestMethod]
        public void Should_create_MessageQueue()
        {
            // Given
            var fixture = new Fixture().Customize(new TestConventions());

            var catalog = fixture.Freeze<ModuleCatalog>();
            fixture.AddManyTo(catalog.MessageStores, 1);

            List<string> ids = fixture.CreateMany<string>(1).ToList();
            A.CallTo(() => catalog.MessageStores.Single().GetQueues()).Returns(ids);

            var target = fixture.CreateAnonymous<HaywireServer>();

            // When
            target.Start();

            // Then
            A.CallTo(() => catalog.MessageStores.Single().GetQueues()).MustHaveHappened();
            Assert.AreEqual(1, target.MessageQueues.Count);
            Assert.AreEqual(ids.First(), target.MessageQueues[0].Id);
        }

        private class TestConventions : CompositeCustomization
        {
            public TestConventions()
                : base(
                    new AutoFakeItEasyCustomization(),
                    new GreedyHaywireServerCustomization())
            {
            }
        }

        private class GreedyHaywireServerCustomization : ICustomization
        {
            public void Customize(IFixture fixture)
            {
                fixture.Customize<HaywireServer>(c =>
                    c.FromFactory(new MethodInvoker(new GreedyConstructorQuery())));
            }
        }
    }
}


Tips on my LIFO java code I've been trying to learn java recently and I finally finish my first code. Any suggestions on where I can improve? Also, is it possible to send an argument to a class using something like an init function in python and are there any good and bad habits that I should keep in mind?
class LIFO {

    //Create an empty list with the lenght of the given size
    //Initialize our top value as 0
    int my_list[] = new int[5];
    int top = 0;

    //Adds a value to the list
    //Add one to our top
    public void push(int data)
    {
        my_list[top] = data;
        top++;
    }

    //Removes the top value from the list
    //Substract one from our top
    public int pop()
    {
        int data;
        top--;
        data = my_list[top];
        my_list[top] = 0;
        return data;

    }

    //Prints our list
    public void show()
    {
        for(int n : my_list)
        {
            System.out.print(n + " ");
        }
    }
}

//Driver Class
class Main {
    public static void main(String args[])
    {
        LIFO s = new LIFO();
        s.push(1);
        s.push(2);
        s.push(3);
        s.show();
        System.out.println("\n" + s.pop() + " Popped from stack");
        s.show();

    }
}

@Ted Brownlow has answered your constructor question, but here's a few other points to consider going forward...
Consider your class interface
Your class needs to present an interface that is functional,usable and focused.  At the moment, your class is responsible for both implementing a LIFO and outputting them to the console.  These are really different concerns.  Consider if instead of writing to the console you wanted to write to a web page / different window.  Building the display logic straight into the class makes it less flexible.  A good exercise might be to remove the show method and decide what method(s) you would need to add to your class in order to allow it to be implemented from outside the class.
Bounds checking
At the moment your class has a fixed maximum size of 5.  However, other than by reading the class there's no way for the client to know (possibly missing a maxSize method or similar).  There's also no way for the client to know how many items are in the list, unless they keep track of it themselves (possibly missing a currentSize method or similar).
Without this size information, there's no way for the client to know if it's safe to call push or pop.  Consider what would happen if you already had 5 items when push was called.  What would happen if 0 items were present and pop was called?  At the moment, you're relying on the framework to handle these scenarios.  This can be ok, if it's a conscious decision, but you probably want to consider  adding some bounds checks and throwing exceptions that more explicitly help the user of your class know what they did wrong.


Blackjack game made in Python 3 This is a simple blackjack game I finished making using Python. I hope you like it and I'm open to any suggestions or critiques you would give me.

from random import shuffle
import sys

def deal(deck, player, dealer):
    shuffle(deck)

    for _ in range(2):
        player.append(deck.pop())
        dealer.append(deck.pop())

def score(hand):
    non_aces = [c for c in hand if c != 'A']
    aces = [c for c in hand if c == 'A']

    total = 0

    for card in non_aces:
        if card in 'JQK':
            total += 10
        else:
            total += int(card)

    for card in aces:
        if total <= 10:
            total += 11
        else:
            total += 1

    return total

def display_info(player, dealer, stand):
    print("Your cards: [{}] ({})".format(']['.join(player), score(player)))
    if stand:
        print("Dealer cards: [{}] ({})".format(']['.join(dealer), score(dealer)))
    else:
        print("Dealer cards: [{}] [?]".format(dealer[0]))

def results(player, dealer, hand, stand):
    if score(player) == 21 and hand:
        print("Blackjack! You won!")
        sys.exit()
    elif score(player) > 21:
        print("Busted. You lost!")
        sys.exit()
    if stand:
        if score(dealer) > 21:
            print("Dealer busted. You won!")
        elif score(player) > score(dealer):
            print("You beat the dealer! You won!")
        elif score(player) < score(dealer):
            print("You lost!")
        else:
            print("Push. Nobody wins or losses.")
        sys.exit()

def hit_stand(deck, player, dealer, hand, stand):
    print("What would you like to do")
    print("[1] - Hit\n[2] - Stand")
    choice = input("> ")
    hand = False
    if choice == '1':
        player.append(deck.pop())
    elif choice == '2':
        stand = True
        while score(dealer) <= 16:
            dealer.append(deck.pop())
        display_info(player, dealer, stand)
        results(player, dealer, hand, stand)

if __name__ == '__main__':
    deck = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']*4
    player = []
    dealer = []
    standing = False
    first_hand = True
    deal(deck, player, dealer)
    while True:
        display_info(player, dealer, standing)
        results(player, dealer, first_hand, standing)
        hit_stand(deck, player, dealer, first_hand, standing)

The follow-up is "Blackjack game - follow-up".

Welcome to CodeReview, and greetings! Your code looks nice: it is well indented, mostly PEP8-conformant, and has clear names. I suspect you may not have spent enough time in Atlantic City or Las Vegas, however. ;-)

Encapsulation

You correctly guard your "main routine" code with if __name__ == '__main__' but you didn't bother to put all that code into a function. Please do so. Call it main if you like, but take the chance to wrap it all up into something that can be invoked from outside, for testing.

def main():
    ''' Play one hand of blackjack. '''
    deck = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']*4
    player = []
    dealer = []
    standing = False
    first_hand = True
    deal(deck, player, dealer)
    while True:
        display_info(player, dealer, standing)
        results(player, dealer, first_hand, standing)
        hit_stand(deck, player, dealer, first_hand, standing)

if __name__ == '__main__':
    main()

Similarly, have a look at this:

if choice == '1':
    player.append(deck.pop())

And this:

while score(dealer) <= 16:
    dealer.append(deck.pop())

What are you doing there? That seems like another opportunity to use a name to describe what's happening:

if choice == '1':
    deal_card(shoe, player)

# ... and ...

while score(dealer) <= 16:
    deal_card(shoe, dealer)

Also, what's 16? Is that a magic number? Should it have a name? (Hint: yes!)

while score(dealer) <= DEALER_MINIMUM_SCORE:
    deal_card(shoe, dealer)

While we're looking at the hit_stand function, consider that it does two things:

def hit_stand(deck, player, dealer, hand, stand):
    print("What would you like to do")
    print("[1] - Hit\n[2] - Stand")
    choice = input("> ")

    ########## End of part 1, start of part 2 ##########

    hand = False
    if choice == '1':
        player.append(deck.pop())
    elif choice == '2':
        stand = True
        while score(dealer) <= 16:
            dealer.append(deck.pop())
        display_info(player, dealer, stand)
        results(player, dealer, hand, stand)

First, it asks for user input. Then it tries to update the game state based on that input. That's one thing too many!

Create separate functions for separate things. I know it may seem pointless when some of those functions are one line long. But it represents a chance for you to "write" an explanation of what you are doing, and it also provides a place to make changes to the behavior.

Also, consider that when you "grow" this blackjack game you will really want places to add behavior. There are many more possibilities than "hit or stand" at the table!

And always remember, user input is unreliable! You have to validate it. What if I type "hit" or "stand" instead of 1 or 2?

Control Flow

You don't actually have an exit condition for your while loop. Instead, you are relying on calls to sys.exit() from lower in your code. That's not going to work for very long as your code complexity grows. Instead, why not create a boolean variable still_playing = True and use while still_playing: as your loop condition. Then you can change that value when it's appropriate.

And your program structure doesn't really resemble the flow of a blackjack game. At a blackjack table, the dealer deals starting cards to all the players, then each player "plays" their entire game, then the dealer "plays" according to his rules, then the results are evaluated. You jammed your "dealer plays" element into the hit_stand function. Pry it loose! Make your flow look more like the real flow of the table, and it will be easier to understand and easier to extend.

Data Flow

In Pascal, a programming language we used in that last millennium by training dinosaurs to interpret the statements for us, there were two kinds of subroutines, procedures and functions. The difference was that a function could return a value, while a procedure just executed statements with no returned result. That discrimination doesn't exist in Python: you can do either thing, but it all starts with def. Regardless, you seem to write only subroutines that do not return values. I think you should change that.

Creating and shuffling the deck is a place where a function could be put to good use, especially if you grow your game. Just write:

shoe = new_shoe()

or later:

shuffle_shoe(shoe)

(If you can't tell, this is heading towards a Shoe class. That will come in a much later review. Also: a shoe is what the dealer takes the cards from.)

Speaking of data, have a look at this:

def hit_stand(deck, player, dealer, hand, stand):
    print("What would you like to do")
    print("[1] - Hit\n[2] - Stand")
    choice = input("> ")
    hand = False

Notice that you take a hand parameter, do nothing with it, and then set it to False? What's up with that? The only thing you use it for is to pass it down to results, but you could just as well write results(..., False, ...) and not bother with the hand parameter.

Also, have a look at the results subroutine. You call it in the middle of the loop, right after displaying the hands. But you've divided showing the hands and evaluating them, when that's kind of the same thing. And you're ignoring the distinction between "showing the current situation" and "wrapping up the end of the game." I'd suggest that your checking for blackjack and for busting should go near where you deal the cards, and should update the loop control variable.

Game Flow

There are a few aspects of blackjack that you are missing, even at this simple level. First, check for and announce blackjack, for both the dealer and the player! If a player gets blackjack, there's no Hit/Stand question, there's only the question of whether the dealer pushes. And if the dealer gets blackjack, the game is over before it began. So check that first.

The obvious extras, like assigning and displaying card suits as well as ranks, multiple players, support for splits, doubling down, insurance, surrendering, etc., would all take you away from a "simple" blackjack game. But your code should be organized in such a way that it is simple to add those features!

Update:

To answer your question from the comments,

  Also, how do I handle the choice variable in the second function if I split hit_stand() as you suggested? And how results() should look like after I make still_playing Boolean?

Let's say hit_or_stand becomes a separate function. You would write something like:

def hit_or_stand():
    while True:
        ans = input("Hit or stand? ").lower()
        if ans in ('hit', 'stand'):
            return ans

# In your main loop:

player_stands = False
while not player_stands:
    # stuff like before
    if hit_or_stand() == 'stand':
        player_stands = True

    if not player_stands:
        deal_one_card(shoe, player)
        if score(player) > 21:
            break

# After loop: dealer takes cards, etc.
results()

The results can stay mostly the same. But some of your passed in variables are not needed, since you can compute them from the other data. For example, if the len(player) is 2, that's the first_hand flag. What's key is that results is outside the loop, not inside. You print the results after breaking/exiting from the loop.


Can I use a header tag in footer inside section? I want to know if I can use a header tag in footer inside section.  I also want to know if this follows SEO.

For example, I made four section boxes in footer:

Box 1

Box 2

Box 3

It's not valid HTML5 to have a <header> element inside a <footer> element. You could have checked this yourself on this site:

http://validator.w3.org/check

For using <header>, <footer> and <section> correctly, see this page:

https://developer.mozilla.org/en-US/docs/Web/HTML/Element/footer

For even more technical details, see the HTML5 specification:

http://www.w3.org/TR/html5/sections.html#the-footer-element

Special thanks to @amon for the links!


Recursive Function to Produce Constrained List of Integer Partitions I have modified a recursive function designed to print all the integer partitions of a positive integer to create a function that returns all partitions of the "number" parameter if they include a number contained in the "interesting" parameter. I would like to use this for very large numbers (10-50 million), but am getting errors referring to the recursion depth. My question is whether there is a way to do this more efficiently by recursion, and if not, whether there is another way to do this.
def partition(number, interesting): # returns all the partitions of number that are included in the interesting list
    answer = set()
    if number in interesting:
        answer.add((number, ))

    for x in range(1, number):
        if x in interesting:
            for y in partition(number - x, interesting):
                answer.add(tuple(sorted((x, ) + y)))
    return answer

Python is not designed for recursion. To avoid stack overflows there is a limit
In [2]: import sys

In [3]: sys.getrecursionlimit()
Out[3]: 1000

So we can easily design a test that will fail
In [4]: partition(1000, {1})
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-4-884568e60acd> in <module>()
----> 1 partition(1000, {1})

<ipython-input-1-60a0eb582d3c> in partition(number, interesting)
      6     for x in range(1, number):
      7         if x in interesting:
----> 8             for y in partition(number - x, interesting):
      9                 answer.add(tuple(sorted((x, ) + y)))
     10     return answer

... last 1 frames repeated, from the frame below ...

<ipython-input-1-60a0eb582d3c> in partition(number, interesting)
      6     for x in range(1, number):
      7         if x in interesting:
----> 8             for y in partition(number - x, interesting):
      9                 answer.add(tuple(sorted((x, ) + y)))
     10     return answer

RecursionError: maximum recursion depth exceeded in comparison

You may increase the recursion limit
In [5]: sys.setrecursionlimit(1500)

In [6]: partition(1000, {1})
Out[6]:
{(1, ...

but that is only applicable if your numbers are guaranteed to be in a certain range. Most probably you should implement a non-recursive solution. For 10-50 million you have to.
If your problem e. g. guarantees 1 <= number <= 500 you should still do some assertions in your function
assert 1 <= number <= 500