Find how much reputation a user had on a given date I saw this question on MSE and went ahead and wrote a solution to it:
https://meta.stackexchange.com/questions/313561/determining-users-reputation-as-of-particular-date

This calculates the reputation a user should have had at a certain date. I attempt to factor in everything that SEDE allows me to see. So -1 events from downvoting posts and serial voting reversal as well as the documentation reputation aren't factored in.

I'm curious about what could be improved here

SELECT
-- Total Reputation
(
SUM(CASE WHEN r2d.ReputationFromVotes + r2d.ReputationFromSuggestedEdits > 200 THEN 200 ELSE r2d.ReputationFromVotes + r2d.ReputationFromSuggestedEdits END)
+ SUM(r2d.ReputationFromBounties)
+ COALESCE((SELECT SUM(v4.BountyAmount * -1) FROM Votes AS v4 WHERE v4.VoteTypeId = 8 AND v4.UserId = ##UserId## AND v4.CreationDate < ##UntilDate:string## ),0)
+ COALESCE((SELECT COUNT(*) * 2 FROM Posts AS p3 WHERE p3.OwnerUserId = ##UserId## AND p3.AcceptedAnswerId IS NOT NULL),0)
+ SUM(r2d.ReputationFromAccepts)
) AS TotalReputation,
-- Rep Capped Activities with the Cap Factored in
SUM(
CASE
WHEN r2d.ReputationFromVotes + r2d.ReputationFromSuggestedEdits > 200 THEN 200
ELSE r2d.ReputationFromVotes + r2d.ReputationFromSuggestedEdits
END) AS ReputationFromRepCap,
-- Total Bounties recieved
SUM(r2d.ReputationFromBounties) AS ReputationFromBounties,
-- Total Bounties given
COALESCE((SELECT SUM(v4.BountyAmount * -1) FROM Votes AS v4 WHERE v4.VoteTypeId = 8 AND v4.UserId = ##UserId## AND v4.CreationDate < ##UntilDate:string## ),0) AS ReputationGivenAsBounties,
-- Total Reputation from Accepting Answers
COALESCE((SELECT COUNT(*) * 2 FROM Posts AS p3 WHERE p3.OwnerUserId = ##UserId## AND p3.AcceptedAnswerId IS NOT NULL),0) AS ReputationFromAcceptingAnswers,
-- Total Reputation from Accepted Answers
SUM(r2d.ReputationFromAccepts) AS ReputationFromAcceptedAnswers

FROM

(

SELECT
v.CreationDate AS VoteDate,

-- Total Reputation from Post Upvotes
-- PostTypeId 1 = Question, 2 = Answer
-- VoteTypeId 2 = Upvote, 3 = Downvote
-- CommunityOwnedDate is when a post was made CW.
-- Votes before that count, after not.
-- Vote Date is truncated to full days only so grouping works
SUM((CASE
  WHEN (p.PostTypeId = 1 AND v.VoteTypeId = 2 AND (p.CommunityOwnedDate > v.CreationDate OR p.CommunityOwnedDate IS NULL)) THEN 5
  WHEN (p.PostTypeId = 2 AND v.VoteTypeId = 2 AND (p.CommunityOwnedDate > v.CreationDate OR p.CommunityOwnedDate IS NULL)) THEN 10
  WHEN (v.VoteTypeId = 3 AND (p.CommunityOwnedDate > v.CreationDate OR p.CommunityOwnedDate IS NULL)) THEN -2
  ELSE 0
END)) AS ReputationFromVotes,

-- Total Reputation from Answer Bounties
-- VoteTypeId 9 = Bounty Close (Bounty Awarded)
-- BountyAmount = Amount of Reputation awarded
SUM(CASE
  WHEN v.VoteTypeId = 9 THEN v.BountyAmount
  ELSE 0
END) AS ReputationFromBounties,

-- Total Reputation from Answer Accepts
-- VoteTypeId 1 = AcceptedByOriginator (Answer Accepted)
SUM(CASE
  WHEN (v.VoteTypeId = 1 AND (p.CommunityOwnedDate > v.CreationDate OR p.CommunityOwnedDate IS NULL)) THEN 15
  ELSE 0
END) AS ReputationFromAccepts,

-- Total Reputation from Suggested Edits
-- if ApprovalDate isn't NULL and RejectionDate is NULL it's been approved and not overriden
-- Group by the same Date as Votes for Rep-Cap evaluation (They count towards it)
COALESCE((SELECT
SUM(CASE WHEN (se.ApprovalDate IS NOT NULL AND se.RejectionDate IS NULL) THEN 2 ELSE 0 END)
FROM SuggestedEdits AS se
WHERE se.OwnerUserId = ##UserId##
AND YEAR(v.CreationDate) = YEAR(se.ApprovalDate)
AND MONTH(v.CreationDate) = MONTH(se.ApprovalDate)
AND DAY(v.CreationDate) = DAY(se.ApprovalDate) ),0) AS ReputationFromSuggestedEdits

FROM Posts AS p
INNER JOIN Votes AS v ON v.PostId = p.Id

WHERE p.OwnerUserId =  ##UserId:int##
AND v.CreationDate <= ##UntilDate:string##

GROUP BY v.CreationDate

) as r2d

The main improvements I would suggest are:

Minimize the number of accesses made to the large, minimally indexed, SEDE tables.
Break the query into multiple steps.
Reduce or eliminate code repetition.

Temporary tables are allowed on SEDE. Use these to fetch the minimal data needed from the large base tables to perform the calculations. Referring to these smaller data sets will be much more efficient than interrogating the base tables multiple times.

Properly used, temporary tables enable more accurate cardinality estimation, automatic statistics on intermediate results, and provide indexing opportunities - all of which can improve final plan quality and performance.

Breaking the query up also makes the logic easier to comprehend and debug (initially, and when maintaining it in future). Errors and redundancies are much easier to spot with smaller queries.

I have not attempted to improve the reputation calculation logic itself, except in a few minor ways, but the following illustrates a possible re-implementation of the provided code using temporary tables:

Initialization

DECLARE
    @UserId integer = 22656, -- Jon Skeet, why not
    @UntilDate datetime = CURRENT_TIMESTAMP;

DROP TABLE IF EXISTS
  #Posts, #Data, #Edits;

Posts data

Just the columns we are going to need from the Posts table:

CREATE TABLE #Posts
(
    Id integer NOT NULL,
    AcceptedAnswerId integer NULL,
    CommunityOwnedDate datetime NULL,
    PostTypeId tinyint NOT NULL
);

Load the minimal number of rows needed:

INSERT #Posts
(
    Id,
    AcceptedAnswerId,
    CommunityOwnedDate,
    PostTypeId
)
SELECT
    P.Id,
    P.AcceptedAnswerId,
    P.CommunityOwnedDate,
    P.PostTypeId
FROM dbo.Posts AS P
WHERE
    P.OwnerUserId = @UserId
    AND P.CreationDate <= @UntilDate
    AND
    (
        P.CommunityOwnedDate IS NULL
        OR P.CommunityOwnedDate <= @UntilDate
    );

This applies the common predicates in the original query as early as possible, including setting a boundary of the values of CommunityOwnedDate that might impact the reputation calculation up to the desired date. Other filtering could be added here, for example to restrict the PostTypeId values to just those of interest.

The execution plan (for Jon Skeet) is:

This plan is relatively efficient, being primarily based on a seek to the OwnerUserId specified. The Merge Interval subtree is concerned with finding the range of CommunityOwnedDate values used as a secondary seek predicate.

The Key Lookup is sadly unavoidable, given the SEDE view dbo.Posts wrapping the underlying table dbo.PostsWithDeleted (filtering on DeletionDate IS NULL without a supporting index). Nevertheless, it does mean we can filter CreationDate in the same lookup without adding significant cost.

Adding votes data

The next step adds the columns we need from the voting data associated with the qualifying posts. This is performed as a second step rather than joining all in one step because the #Posts table provides useful accurate cardinality and statistical information. A join query is quite likely to mis-estimate, resulting in an inappropriate plan selection or hash spill, for example.

CREATE TABLE #Data
(
    AcceptedAnswerId integer NULL,
    CommunityOwnedDate datetime NULL,
    PostTypeId tinyint NOT NULL,
    BountyAmount integer NULL,
    VoteTypeId tinyint NOT NULL,
    CreationDate datetime NOT NULL
)
WITH (DATA_COMPRESSION = ROW);

Row compression is not necessarily super-useful here, but it does illustrate the extra flexibility of using discrete result sets.

INSERT #Data WITH (TABLOCK)
(
    AcceptedAnswerId,
    CommunityOwnedDate,
    PostTypeId,
    BountyAmount,
    VoteTypeId,
    CreationDate
)
SELECT
    P.AcceptedAnswerId,
    P.CommunityOwnedDate,
    P.PostTypeId,
    V.BountyAmount,
    V.VoteTypeId,
    V.CreationDate
FROM #Posts AS P
JOIN dbo.Votes AS V
    ON V.PostId = P.Id
WHERE
    V.CreationDate <= @UntilDate
    AND
    (
        P.CommunityOwnedDate IS NULL
        OR P.CommunityOwnedDate > V.CreationDate
    );

The query above again applies predicates as early as possible, and gives us a combined view of the posts and votes that we can interrogate in multiple ways later on at low cost (certainly much cheaper than accessing the base tables again).

The execution plan features accurate cardinality estimates, appropriate use of parallelism, and a hashtable build-side bitmap filter used to perform semi-join reduction on the Votes table scan. This removes rows that cannot possibly join even before they are surfaced from the storage engine to the query processor (as indicated by the INROW attribute).

Suggested Edit Data

We only need the date (no time component) and total reputation earned for suggested edits:

CREATE TABLE #Edits
(
    ApprovalDate datetime PRIMARY KEY,
    Reputation integer NOT NULL
);

INSERT #Edits
(
    ApprovalDate,
    Reputation
)
SELECT
    G.ApprovalDate,
    EditRep = 2 * COUNT(*) -- 2 rep per approved suggested edit
FROM dbo.SuggestedEdits AS SE
CROSS APPLY
(
    VALUES (CONVERT(datetime, CONVERT(date, SE.ApprovalDate)))
) AS G (ApprovalDate)
WHERE
    SE.OwnerUserId = @UserId
    AND SE.ApprovalDate <= @UntilDate
    AND SE.RejectionDate IS NULL
GROUP BY
    G.ApprovalDate;

Using CROSS APPLY with VALUES allows us to avoid repeating the datetime to date conversion in the SELECT list and GROUP BY clause. The converted value is put back in a datetime type for consistency with the other SEDE-derived tables.

It is generally best practice to pay careful attention to data types, avoiding implicit conversions. This has myriad benefits, not least for cardinality estimation and join performance & optimizations.

A possible improvement to the code here would be to use the date type everywhere only the date portion is needed.

The parallel scan of the SuggestedEdits table is the best we can do here, without better indexing in SEDE.

Reputation Per Day

This table largely replaces the original r2d subquery, computing reputation totals per day:

CREATE TABLE #DayTotals
(
    CreationDate datetime PRIMARY KEY,
    ReputationFromVotes integer NOT NULL,
    ReputationFromBounties integer NOT NULL,
    ReputationFromAccepts integer NOT NULL,
    ReputationFromSuggestedEdits integer NOT NULL
);

INSERT #DayTotals WITH (TABLOCK)
(
    CreationDate,
    ReputationFromVotes,
    ReputationFromBounties,
    ReputationFromAccepts,
    ReputationFromSuggestedEdits
)
SELECT
    D.CreationDate,
    ReputationFromVotes =
        ISNULL
        (
            SUM
            (
                CASE
                    WHEN D.PostTypeId = 1 AND D.VoteTypeId = 2 THEN 5
                    WHEN D.PostTypeId = 2 AND D.VoteTypeId = 2 THEN 10
                    WHEN D.VoteTypeId = 3 THEN -2
                    ELSE 0
                END
            ), 0
        ),
    ReputationFromBounties =
        ISNULL(SUM(CASE WHEN D.VoteTypeId = 9 THEN D.BountyAmount ELSE 0 END), 0),
    ReputationFromAccepts =
        ISNULL(SUM(CASE WHEN D.VoteTypeId = 1 THEN 15 ELSE 0 END), 0),
    ReputationFromSuggestedEdits = ISNULL(SUM(E.Reputation), 0)
FROM #Data AS D
LEFT JOIN #Edits AS E
    ON E.ApprovalDate = D.CreationDate
GROUP BY
    D.CreationDate;

The execution plan shows efficient parallel processing using only the relatively small temporary tables:

Other reputation totals

These are single values, stored in variables for convenience:

DECLARE
    @RepBountiesGiven integer =
    (
        SELECT
            ISNULL(SUM(-D.BountyAmount), 0)
        FROM #Data AS D
        WHERE
            D.VoteTypeId = 8 -- BountyStart
    ),
    @RepFromAcceptingAnswers integer =
    (
        SELECT
            2 * COUNT(*) -- 2 rep per answer accepted
        FROM #Posts AS P
        WHERE
            P.PostTypeId = 1
            AND P.AcceptedAnswerId IS NOT NULL
    ),
    @ReputationFromRepCap integer =
    (
        SELECT
            SUM
            (
                CASE
                    WHEN ReputationFromVotes + ReputationFromSuggestedEdits <= 200
                    THEN ReputationFromVotes + ReputationFromSuggestedEdits
                    ELSE 200
                END
            )
        FROM #DayTotals
    );

Final query

Now we have all the elements we need to produce the final output:

SELECT
    TotalReputation =
        @ReputationFromRepCap +
        SUM(DT.ReputationFromBounties) +
        @RepBountiesGiven +
        @RepFromAcceptingAnswers +
        SUM(DT.ReputationFromAccepts),
    ReputationFromRepCap = @ReputationFromRepCap,
    ReputationFromBounties = SUM(DT.ReputationFromBounties),
    ReputationGivenAsBounties = @RepBountiesGiven,
    ReputationFromAcceptingAnswers = @RepFromAcceptingAnswers,
    ReputationFromAcceptedAnswers = SUM(DT.ReputationFromAccepts)
FROM #DayTotals AS DT;

Try the complete script at: SEDE Demo


Root to leaf path with given sum in binary tree For a given binary tree and a sum, I have written the following function to check whether there is a root to leaf path in that tree with the given sum.

/*
//A binary tree node
struct Node
{
    int data;
    struct Node* left, * right;
};
*/

bool hasPathSum(Node *node, int sum)
{
    if(!node)
        return sum==0;

    return ( hasPathSum(node->left,  sum-node->data) ||
             hasPathSum(node->right, sum-node->data) );
}

Are there any edge cases in which the code will break? Also, do comment on the code style.

Give your operators some breathing space.

    if (!node) {
        return sum == 0;
    }

    return hasPathSum(node->left,  sum - node->data) ||
           hasPathSum(node->right, sum - node->data);

Note that return expression needs no parenthesis.
sum - node->data seems more natural to be expressed once:

    sum -= node->data;
    return hasPathSum(node->left,  sum) ||
           hasPathSum(node->right, sum);

I see no edge cases except possible overflows.


Configuring Constructor Parameters and Unit Testing Currently working on writing out some test for an iOS enterprise application.  My concern is in this set up of my overloaded constructor.

- (id)init
{
    CRMHttpClient *client = [CRMHttpClient sharedClient];
    NSOperationQueue *queue = [NSOperationQueue new];
    UIApplication *application = [UIApplication sharedApplication];
    return [self initWithCRMHttpClient:client operationQueue:queue application:application];
}

- (id) initWithCRMHttpClient:(CRMHttpClient *)client operationQueue:(NSOperationQueue *)operationQueue application:(UIApplication *)application
{
    self = [super init];
    if(self)
    {
        self.client = client;
        self.queue = operationQueue;
        self.queue.name = [[NSBundle.mainBundle bundleIdentifier] stringByAppendingString:@".CRMDataProcessingQueue"];
        self.queue.maxConcurrentOperationCount = 2;
        self.application = application;
        self.backgroundTask = UIBackgroundTaskInvalid;
    }

    return self;
}

-(id)init is called by the other classes in the project. -(id)initWithCRMHttpClient:... is called in my test class so I can inject my mocks to unit test my class. (I know I could use partial mocks for the singleton classes, but I prefer to explicitly inject the class)
What bothers me about this approach is the few lines of code where I'm configuring my NSOperationQueue's name and operation count.  This requires me to write this up in my -(void)setup method of my testing class.

- (void)setUp
{
    [super setUp];
    self.mockCRMHttpClient = [OCMockObject mockForClass:[CRMHttpClient class]];
    self.mockOperationQueue = [OCMockObject mockForClass:[NSOperationQueue class]];
    [[self.mockOperationQueue stub] setName:OCMOCK_ANY];
    [[self.mockOperationQueue stub] setMaxConcurrentOperationCount:2];
    self.mockApplication = [OCMockObject mockForClass:[UIApplication class]];
}

I need to stub out the calls for those set up methods so that I don't get failed calls.  I my options are:

Leave it as is, stubbing in the -setup
Configure the operation queue in the -init method instead.
Create a nice mock for mockOperationQueue
Am I forgetting something?

I'm unsure of which approach to take.

Go with #3, "Create a nice mock for mockOperationQueue." The only reason you're having to do that stubbing is that OCMock creates "strict" mocks by default. Strict mocks used to be the standard, but mock object frameworks have evolved. The problem with strict mocking is that they make tests more brittle.

For example, let's say you find the need to add another "this needs to happen when I'm setting up the operation queue" call. Suddenly, your tests will break, because the strict mock will complain, "I don't know what this new call is." You've coded things well by setting up the mock operation queue in one place, so fixing it wouldn't be hard; you'd just add another stub in your -setUp. But the test failure isn't a failure; it's noise.

OCMock was originally written when strict mocks were the norm. It was also the norm then to state expectations first, call the method of interest, then ask the mock to verify itself:

[mockView expect] addTweet:[OCMArg any];

[controller displayTweets];

[mockView verify];

But mock object frameworks have evolved since then. People figured out that having non-strict mocks was almost never a problem. And new frameworks came along that state the expectation after calling the method of interest. Using OCMockito, the example above changes to:

[controller displayTweets];

[verify(mockView) addTweet:anything()];

This restores the standard order of unit tests: "Arrange - Act - Assert" (or if you prefer, "Given - When - Then"). The verification of expectations now happens in the Assert phase, rather than sitting up in the Arrange phase. So now the test code reads more naturally, like a DSL.

The author of OCMock recognizes the importance of this evolution, and has stated:

  The next major version of OCMock is planned to support nice-by-default
  and verification of specific calls after the fact.


Replacing "no-js" with “js” class in the body element properly I currently have a WP site and in the header, I've put this in:

...
<body <?php body_class('no-js');?>>
    <script>document.body.className = document.body.className.replace( 'no-js' , 'js' );</script>
...

It works flawlessly and I've got no complaints, as it accomplishes the following:

Does not rely on jQuery to load, which is placed at the bottom of the code after the body element along with other js files.
Runs before the visible elements are loaded and doesn't change the look of the site after the site has loaded, meaning the user sees exactly what is supposed to be seen.
Code is placed immediately after the body element is opened so it can find the body after the browser reads that it exists, meaning it's quick, small, and easy to spot.

I'm wondering if there's a more efficient way of doing this.

This comment adds it as a function. Why a function and not just drop it in like I did?
Here is where I think I originally got my code from.
Here's a performance comparison I found from an SO answer, but it doesn't help me much.

Solution doesn't have to be js; it can be anything, as long as it's the right way. Obviously I'm using the classes to distinguish when js is working or not for the corresponding CSS styling to apply.

It's a decent and pretty bullet-proof solution. Modern browsers also support the classList API, so you can do:

document.body.classList.remove('no-js');

It's a slightly safer solution, as the original could technically replace parts of a word (like abcno-jsfoo). Not really a concern here, but still.

To avoid that, and still use the original solution, you could use a regular expression to match word boundaries too:

document.body.className = document.body.className.replace(/\bno-js\b/, '');


Lazy prime number generator There are multiple Project Euler problems (e.g. 7, 10) that deal with prime numbers. I decided make a reusable solution that could be used for most of them.

I wrote a method to generate an infinite* prime number sequence, which would enumerate lazily (that is - computing only when requested), using yield return. At this point I can use the whole power of LINQ, MoreLINQ, and any other IEnumerable extension method.

It doesn't perform great though - finding prime numbers below 2 million takes over a second. I don't think I can use a sieve as I don't know the upper bound. What could be done to improve it? Any other non-performance improvements?

*The sequence isn't really infinite, only up to 263-1 or until an OutOfMemoryException.

The prime sequence generator:

class PrimeSequenceGenerator : ISequenceGenerator
{
    public IEnumerable<long> GetSequence()
    {
        var primeCache = new List<long>();
        long curentNumber = 2;
        while (true)
        {
            var isPrime = true;
            var currentRoot = Math.Sqrt(curentNumber);
            foreach (var cachedPrime in primeCache)
            {
                if (curentNumber % cachedPrime == 0)
                {
                    isPrime = false;
                    break;
                }
                if (cachedPrime > currentRoot)
                {
                    break;
                }
            }
            if (isPrime)
            {
                primeCache.Add(curentNumber);
                yield return curentNumber;
            }
            curentNumber++;
        }
    }
}

An interface for all my sequence generators:

interface ISequenceGenerator
{
    IEnumerable<long> GetSequence();
}

Usage:

var generator = new PrimeSequenceGenerator();

// Euler problem 7 - Find the 10001st prime.
var problem7Solution = generator.GetSequence().ElementAt(10001 - 1);

// Euler problem 10 - Find the sum of all primes below two million.
var problem10Solution = generator.GetSequence().TakeUntil(x => x > 2000000).SkipLast(1).Sum();

For small primes - i.e. up to 2^32 and maybe up to 2^40..2^50ish regions - you can improve speed by several orders of magnitude if you use a Sieve of Eratosthenes.

In order to get decent speed the factor primes - i.e. those up to sqrt(limit), whatever your limit might be - should be sieved up front and stored in an array, alongside with the current working offset for each prime (initialised to the square of the prime). The sieving of the small factor primes can also be done with a - simpler - Sieve of Eratosthenes.

The size of the sieve should be equal to the L1 cache size of the expected target machine (usually 32 KByte), and for maximum efficiency you should use a packed odds-only bitmap. BitArray is slow as molasses, so either use bool[1<<15], or byte[1<<15] with manual bit indexing (i.e. sieve[i>>3] |= 1<<(i&7) to set bit i). Using wheels like mod30 can improve efficiency further, but only in connection with major unrolling of loops and lots of other complications.

Another performance boost is offered by presieving. Instead of clearing the sieve prior to sieving a new window's worth of primes, you simply blast over the sieve a pre-computed bit pattern that corresponds to sieving by a certain number of (odd) small primes. Presieving up to 13 hits a sweet spot in a situation like this, but going up to 17 or 19 can realise further (tiny) speed gains at the cost of much increased size of the precomputed pattern.

In order to illustrate what the code would look like and how the various techniques connect, here's the actual sieving function from my SPOJ PRIME1 submission:

internal static byte[] presieve_pattern;
internal static int presieve_modulus;
internal static int first_sieve_prime_index;
internal static byte[] sieve;
internal static int[] result;
internal static int result_size;

// ...

internal static void sieve_primes_between_ (int m, int n)
{
    if (m > n)
        return;

    Trace.Assert(first_sieve_prime_index == 0 || m > small_odd_primes[first_sieve_prime_index - 1]);
    Trace.Assert((m & 1) != 0 && (n & 1) != 0);
    Trace.Assert(m > 1);

    int sqrt_n = (int)Math.Sqrt(n);
    int max_bit = (n - m) >> 1;         // (the +1 is redundant here since both are odd)

    Trace.Assert(max_bit < sieve.Length * 8);

    if (first_sieve_prime_index == 0)  // without presieving
        Array.Clear(sieve, 0, (max_bit >> 3) + 1);
    else
    {
        int base_bit = (m >> 1) % presieve_modulus;
        while ((base_bit & 7) != 0)
            base_bit += presieve_modulus;
        Buffer.BlockCopy(presieve_pattern, base_bit >> 3, sieve, 0, (max_bit >> 3) + 1);
    }

    for (int i = first_sieve_prime_index, e = small_odd_primes.Length; i < e; ++i)
    {
        int prime = small_odd_primes[i];

        if (prime > sqrt_n)
            break;

        int start = prime * prime, stride = prime << 1;

        if (start < m)
        {
            start = (stride - 1) - (m - start - 1) % stride;
        }
        else
            start -= m;

        for (int j = start >> 1; j <= max_bit; j += prime)
            sieve[j >> 3] |= (byte)(1 << (j & 7));
    }

    Trace.Assert(m > 3 && m % 3 != 0);

    for (int i = 0, d = 3 - m % 3, e = (n - m) >> 1; i <= e; i += d, d ^= 3)
        if ((sieve[i >> 3] & (1 << (i & 7))) == 0)
            result[result_size++] = m + (i << 1);  // m is odd already
}

The code should answer quite a few questions that I simply glossed over in the text. This version is geared towards experimentation with various aspects (like number of presieve primes and so on), and thus it lacks a lot of - uglifying and code-bloating - optimisations.

The wrapper function needs to take care of things like non-sieve primes and normalising arguments, which is why I'm showing it here as well:

internal static void sieve_primes_between (int m, int n)
{
    result_size = 0;

    if (m < small_odd_primes[first_sieve_prime_index])
    {
        for (int i = -1; i < first_sieve_prime_index; ++i)
        {
            int prime = i < 0 ? 2 : small_odd_primes[i];

            if (m <= prime && prime <= n)
            {
                result[result_size++] = prime;
            }
        }

        m = small_odd_primes[first_sieve_prime_index];
    }

    n -= 1 - (n & 1);           // make it odd
    m |= 1;                     // make it odd
    m += m % 3 == 0 ? 2 : 0;    // skip if multiple of 3

    sieve_primes_between_(m, n);
}

This illustrates the kind of complications that you have to deal with when certain optimisations are applied, like special handling for the wheel primes (in this case only the number 2) and the presieve primes.

What is not shown here - because it does not fit the profile of the PRIME1 task - is the remembering of offsets. I don't have working C# code that uses the technique at the moment, because I just started learning the language. Remembering the working offsets shouldn't be too difficult to implement, despite the peculiarities of C# like lack of reference types.

The code takes 3..4 milliseconds to sieve 10 x 100,000 numbers just below the PRIME1 limit (10^9). A version using bool[] could be marginally faster for the low PRIME1 limit but certain further optimisations require the use of byte[] or int[], especially as C# has major performance problems with indexing.

This type of sieve performs decently in the 32-bit range. It can be modified to operate beyond 32 bits but in higher regions of the 64-bit range it gets bogged down by the sheer number of potential factor primes (hundreds of millions, at the end of the range) each of which needs to be considered for sieving each window unless a technique like bucketing is used.


Reviewing my implementation of a stack using linked list I have been studying data structures, and I'm new to this.  Here is my code for the push and pop operations.

I considered using a node=top, so that I can avoid O(n) operations for the push (i.e. finding the last node every time).
I can't seem to find a better implementation for the pop operation.

Let me know if my code is good or bad.  You can be harsh.  I'll take it positively and learn from it.

typedef struct stack_ {
    int data;
    struct stack_ *next;
}stack;

stack *push(stack *head, stack **top, int val){
    //if stack is empty
    if(head == NULL){
        head = (stack *)malloc(sizeof(stack *));
        head -> data = val;
        head -> next = NULL;
        *top = head; //make current node the top of stack
        return head;
    }

    stack *newnode;
    newnode = (stack *)malloc(sizeof(stack *));
    (*top)->next = newnode; //append new node to what top points to
    newnode -> data = val;
    newnode -> next = NULL;
    *top = newnode; //make current node the top of stack
    return head;
}

stack *pop(stack *head, stack **top){
    if(head == NULL){
        printf("Stack is empty\n");
        return NULL;
    }

    stack *cur, *prev;
    cur = head;
    while(cur -> next){ //Traverse to the end
        prev = cur;
        cur = cur -> next;
    }

    prev -> next = NULL;
    *top = prev; //make this node the top of stack
    free(cur);
    return head;
}

Here's the main function:

int main ()
{
    stack *head, *top;
    head = top = NULL;

    while(1){
        int choice;
        printf("1.Push\n2.Pop\n3.Exit\n");
        scanf("%d", &choice);

        if(choice == 3)
            break;
        else if(choice == 2){
            head = pop(head, &top);
            showstack(head);

        }
        else if(choice == 1){
            int val;
            printf("Enter the value to be pushed\n");
            scanf("%d", &val);
            head = push(head, &top, val);
            showstack(head);
        }
        else
            printf("Enter the correct choice\n");

    }
    if(head)
        free(head);
    if(top)
        free(top);
    return 0;
}

Some minor comments to add to what others have said.

Adding an underscore to the end of struct stack is just noise. It achieves
nothing, so leave it out.
Omit the spaces around -> and add them after keywords (if, while etc)
you are allocating only enough memory to hold a pointer to a stack node
(stack*). Instead you should be allocating a node:

head = malloc(sizeof(stack));

or:

head = malloc(sizeof *head);

Note also that there is no cast (we are writing C, not C++)

The version suggested by @ChrisWue is elegant, but it does need
two structures.  You could achieve the same thing but with only a
single struct (your existing stack) like this:

stack* push(stack *head, int data, int *result)
{
    stack *s = malloc(sizeof *s);
    if (s) {
        s->data = data;
        s->next = head;
        *result = 1;
    }
    else *result = 0;
    return s;
}

stack* pop(stack *head, int *data, int *result)
{
    if (!head) {
        *result = 0;
        return head;
    }
    *result = 1;
    stack *next = head->next;
    *data = head->data;
    free(head);
    return next;
}

But note that you must then be careful always to assign the return value to
head in the caller:

    int data;
    int ok;
    stack *head = NULL;
    ...
    head = push(head, data, &ok);
    if (ok) {
        ...
    }
    head = pop(head, &data, &ok);
    if (ok) {
        ...
    }


Is this a good way for Controller to interact with Model ? (MVC) In my controller I had the idea to do something like the following:

// retrieve fields from form
$firstname = $form->getInput('firstname');
$lastname = $form->getInput('lastname');
[...]
// create Member object
$member = new Member($firstname, $lastname, [...]);
// save Member in DB
$this->_daoFactory->get('Member')->save($member);

In this example, the DAO factory would create an instance of the MemberDAO class, which (I guess) acts like a data mapper? And allows me to save the Member object in DB, to update a Member, get a Member from id, and other db requests probably.

What do you think about this code?

Thank you for your review!

A lot of MVC frameworks do the datamapping in the same class (usually with static methods).  I would also avoid creating hard links between controllers and models (like having each model property as a parameter in the class constructor).  Something like this is a little more elegant, IMO:

<?php

// Model
class Member
{
    public static function forge(array $data = array())
    {
        return new static($data);
    }

    public function __construct(array $data = array())
    {
        foreach ($data as $k => $v)
        {
            // consider checking here for expected properties,
            // sanitizing input, etc.
            $this->$k = $v;
        }
    }

    public function save()
    {
        // If primary key exists, run DB update query
        // Otherwise, run insert query

        // Return success/failure information (and/or throw exceptions)
    }
}

// Controller action
$member = Member::forge($form->get_sanitized_postdata());
$member->save();


Too many parentheses to format a percentage in SELECT This query seems to have way too many parentheses.

SELECT
CAST(ISNULL(ROUND(CAST((SUM(product1) + SUM(product2)) AS FLOAT) / CAST(salescalls.visits AS FLOAT) * 100, 2), 0) AS VARCHAR) + '%' AS avrg
FROM sales, salescalls
WHERE sales.salescallId = salescalls.id

There is something you can do about

CAST((SUM(product1) + SUM(product2)) AS FLOAT) / CAST(salescalls.visits AS FLOAT) * 100

To perform floating-point division rather than integer division, either the dividend or the divisor needs to be a float.  You don't need make both of operands floats.  Furthermore, you can make a the dividend a float by using floating-point multiplication.  That means that you don't need to cast anything to a float.  That simplifies it to

100.0 * (SUM(product1) + SUM(product2)) / salescalls.visits

Next, you can rewrite the sums as one aggregate by adding the two columns in each row before summing the rows:

100.0 * SUM(product1 + product2) / salescalls.visits

I don't think that there's not much that can be done about ROUND(), ISNULL(), and CAST(… AS VARCHAR), though.  Consider doing that formatting in your application-layer code instead of SQL.

You've written the query using an old-style join.  It would be better to write it using a JOIN keyword:

SELECT CAST(
           ISNULL(
               ROUND(
                   100.0 * SUM(product1 + product2) / salescalls.visits,
                   2
               ),
               0
           ) AS VARCHAR
       ) + '%' AS avrg
    FROM sales INNER JOIN salescalls ON sales.salescallId = salescalls.id


Project Euler # 95 in Haskell - kind-of finding longest cycle in a graph I am trying to solve Project Euler #95 in Haskell, though I have already solved it in Java (see). I found that writing imperatively, we can easily do the task this way:

Pseudocode

Define cache as an int array.
Find all perfect numbers and store them in a HashSet.
For each number create a new HashSet for terms (named terms) that have already occured while iterating.
If the number is prime or perfect skip it (and set cache value to -1)
Now iterate using sum of proper divisors, if we stumble upon a number that is out of bounds or has cache value -1 skip this too and set this number's cache value as -1 too. Iterate until we reach 1 or a perfect number or the number itself; keep adding to terms.
If we reach the number, get the size of terms, otherwise (1 or perfect number) set cache value to -1.
Keep record of number with maximum terms size.

Now thinking of functionally writing this solution I find it quite difficult to maintain something as cache, I have to iterate for each number. Also, my mind was quite stuck to this imperative solution so the Haskell equivalent was not quite different or unique. How can I improve it? (It is also quite slower - 32s)

95.hs

import           Control.Arrow
import qualified Data.IntSet   as Set
import           Data.List
import           Data.Ord
import           Divisors

lim :: Int
lim = 1000000

main :: IO ()
main = print . fst . maximumBy (comparing snd) . map (id &&& amicableChainLength) $ [2..lim]
    where
        amicableChainLength x
            | sumOfProperDivisors x == x = 1 -- perfect numbers
            | otherwise = (\((_, list), _) ->
                case elemIndices (last list) list of
                    -- Two occurences
                    (a:b:_) -> b - a
                    -- Cannot occur but anyways
                    _       -> 0
                )
                -- Take first element where include stopped
                . head . dropWhile snd . scanl (include x)
                -- ((Set of numbers observed, Ordered list of them), Continue?)
                ((Set.empty, []), True)
                $ iterate sumOfProperDivisors x
        -- tries to include number into set/list and also tell when to stop
        include x ((set, list),_) n
            -- number is member of observed numbers
            | Set.member n set =
                if x==n
                    -- chain should start at that number
                    then ((set, list ++ [n]), False)
                    -- otherwise no meaning
                    else ((Set.empty, []), False)
            -- Out of bounds or an number earlier encountered, this cannot be answer
            -- since we are required to find minimum element of that chain
            | n > lim || n < 2 || n < x = ((Set.empty, []), False)
            -- New number, add it & continue
            | otherwise = ((Set.insert n set, list ++ [n]), True)

Divisors.hs

module Divisors where

sumOfProperDivisors :: Int -> Int
sumOfProperDivisors n = subtract n . (\s -> if isPerfectSquare n then s - root else s)
    . sum . map (\x -> x + n `div` x) . filter (\x -> n `mod` x == 0)
    . takeWhile (\p -> p*p <= n) $ [1..]
    where
        root = round (sqrt . fromIntegral $ n :: Double)
        isPerfectSquare x = root * root == x

If something can't happen, put your money on it and make it crash if it does anyway instead of silently carrying on.

maximumOn deserves its own name to lift our burden of manual tuple juggling.

Adding elements to the end of a list smells. Let me reverse the list order to fix that.

The scanl with the booleans looks degenerated, there must be a better way - let me undo its introduction. The booleans can be replaced with conditional recursion. The set need not be returned in the cases that used to return True. The list entries that are to be later returned need not be passed deeper into the recursion - and then the list need not be passed down at all. Incidentally, this restores the original list order.

Let's look what I got so far:

maximumOn f = fst . maximumBy (comparing snd) . map (id &&& f)

main :: IO ()
main = print $ maximumOn amicableChainLength [2..lim] where
  amicableChainLength x
    | sumOfProperDivisors x == x = 1 -- perfect numbers
    | otherwise = (\list -> case elemIndices (last list) list of (a:b:_) -> b - a)
      $ include x Set.empty
      $ iterate sumOfProperDivisors x
  -- tries to include number into set/list and also tell when to stop
  include x set (n:ns)
    -- number is member of observed numbers
    | Set.member n set = if x==n
        then [n] -- chain should start at that number
        else error "otherwise no meaning"
    -- this cannot be answer since we are required to find minimum element of that chain
    | n > lim || n < 2 || n < x = error "out of bounds or an number earlier encountered"
    -- New number, add it & continue
    | otherwise = n : include x (Set.insert n set) ns

This code kinda looks like the error cases do happen regularly. Were your comments under the assumption that we are currently looking at the x that is going to win the maximumBy contest? Let me use list comprehension syntax to skip through erroring xs without hacking our way through the data we happen to be working with too much. (Sadly this requires pulling back of parts of maximumOn.) Also the perfect numbers case seems to be subsumed by the other. Also the last element of the list is x if we're interested in it. Also the two positions of x are always in the front and back so we can just compare lengths, and we need not even pass the list out of include.

main :: IO ()
main = print $ fst $ maximumBy (comparing snd)
  [ (x, l)
  | x <- [2..lim]
  , let Just l = include x Set.empty $ iterate sumOfProperDivisors x
  ] where
  -- tries to include number into set/list and also tell when to stop
  include x set (n:ns)
    -- number is member of observed numbers
    | Set.member n set = if x==n
        then Just 0
        else Nothing
    -- this cannot be answer since we are required to find minimum element of that chain
    | n > lim || n < 2 || n < x = Nothing
    -- New number, add it & continue
    | otherwise = (+1) <$> include x (Set.insert n set) ns

I now notice that list comprehensions don't actually use the Alternative instance of lists within let expressions. Ah well, since the Ord instance for Maybe happens to make Nothing smaller than Just anything, I can get rid of the list comprehension again, and restore maximumOn!

main :: IO ()
main = print $ maximumOn (\x -> include x Set.empty $ iterate sumOfProperDivisors x)
  [2..lim] where
  -- tries to include number into set/list and also tell when to stop
  include x set (n:ns)
    -- number is member of observed numbers
    | Set.member n set = if x==n
        then Just 0
        else Nothing
    -- this cannot be answer since we are required to find minimum element of that chain
    | n > lim || n < 2 || n < x = Nothing
    -- New number, add it & continue
    | otherwise = (+1) <$> include x (Set.insert n set) ns

n<2 is subsumed in n<x, the chain length is monotonous with the set size, and do notation feels like it might help with include.

main :: IO ()
main = print $ maximumOn (\x -> include x Set.empty x) [2..lim] where
  -- set keeps track of previously seen numbers
  include x set n = do
    guard $ n <= lim && n >= x
    if Set.member n set
      then guard (x == n) >> Just (Set.size set)
      else include x (Set.insert n set) (sumOfProperDivisors n)

I have a hunch there's a way to decompose include completely, but I don't see it.


Determining whether a task is active based on many conditions I wrote a Rails model instance method that checks many separate conditions, and returns a single boolean. It does not employ any nesting of branching structures. Each check has its own comments describing its reasoning. Every check is necessary for the method to return an accurate value, and none of the checks are likely to be reused independently of the other checks. The function is 34 lines long including comments. A colleague reviewing the code suggested that the method may be too long, and therefore would be more readable if broken out into multiple helper methods for greater readability.

def active?
  #Check columns on self first, so if those dont pass,
  #no other records will need to be loaded.
  return false if self[:active] == false && !ignore_column
  return false if self.suspended # here for thoroughness. tasks should never be marked active and suspended.
  return false if self.completed_at # here for thoroughness. tasks should never be marked active and completed.
  if failed_attempts >= MAX_FAILED_ATTEMPTS # here for thoroughness. tasks should never be marked active after the max failed attempts.
    if !suppress_error_emails
      SystemMailer.error message:"Too many failed attempts for task execution. #{failed_attempts}/#{MAX_FAILED_ATTEMPTS} failed attempts for Task #{id}."
    end
    return false
  end
  #If the origin is inactive and not because it is a withdrawn status, then the task should be inactive.
  return false if !evergreen && origin && !origin.active && origin.is_a?(Crm::Status) && !origin.indicates_closed # Status or Subscription

  return false if sequenceable.is_a?(Crm::Case) && sequenceable.sales_stage_id.to_i>Crm::SalesStage.id('Placed') #placed policies shouldn't fire tasks

  #Recruits are always marked inactive because they are users that can't log in.
  #If the person is inactive but not a recruit, the task should be inactive.
  is_a_recruit=person.try(:is_a?,Usage::User) && person.try(:role)==Usage::Role['recruit']
  return false if !person.try(:active) && !is_a_recruit

  if self.template
    template_purpose_id=self.template.template_purpose_id
    purposes=Marketing::Template::TEMPLATE_PURPOSE
    status_opted_out=self.person.status_unsubscribe && template_purpose_id==purposes["Status"][:id]
    con_mktg_opted_out=self.person.is_a?(Crm::Connection) && self.person.marketing_unsubscribe && template_purpose_id==purposes["Consumer Marketing"][:id]
    user_mktg_opted_out=self.person.is_a?(Usage::User) && self.person.marketing_unsubscribe && template_purpose_id==purposes["Agent Marketing"][:id]
    if status_opted_out || con_mktg_opted_out || user_mktg_opted_out
      return false
    end
  end

  return true
end

Is there a magic number of lines where a function or method becomes too long and should be broken out into multiple functions? If so, what is the magic number? Does it depend on the type of code (model/view/controller), or some other circumstance?

Some comments on your code:

Keep the line length below 80-100 or the code becomes unreadable.
self[:active] == false -> !self[:active]
Checks should be terser, encapsulate logic in methods.
A return at the end of a code block is neither necessary nor idiomatic.
[Subjective] I usually prefer full-fledge conditionals to guards, indentation helps a lot to see what's going on.

In a first refactor, I'd write a more readable case:

def active?
  case
  when (!self[:active] && !ignore_column) || suspended || completed_at
    false
  when failed_attempts >= MAX_FAILED_ATTEMPTS
    if suppress_error_emails
      false
    end
      message = "Too many failed attempts for task execution. " +
        "#{failed_attempts}/#{MAX_FAILED_ATTEMPTS} failed attempts for Task #{id}."
      SystemMailer.error(message: message)
    end
  # ...
  # more conditions here, you get the idea
  # ...
  when template &&
       (status_opted_out? || con_mktg_opted_out? || user_mktg_opted_out?)
    false
  else
    true
  end
end

On a second refactor, I'd probably move all logic to separate methods. Now you could write:

def active?
  condition1? && condition2? && ... && conditionN?
end


Histogram of a string I'm teaching myself Python and when a friend posted this sentence

  Only the fool would take trouble to verify that his sentence was
  composed of ten a's, three b's, four c's, four d's, forty-six e's,
  sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's,
  four m's, twenty-five n's, twenty-four o's, five p's, sixteen r's,
  forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four
  x's, eleven y's, twenty-seven commas, twenty-three apostrophes, seven
  hyphens and, last but not least, a single !

I thought, as a fool, I would try to verify it by plotting a histogram. This is my code:

import matplotlib.pyplot as plt
import numpy as np

sentence = "Only the fool would take trouble to verify that his sentence was composed of ten a's, three b's, four c's, four d's, forty-six e's, sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's, four m's, twenty-five n's, twenty-four o's, five p's, sixteen r's, forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four x's, eleven y's, twenty-seven commas, twenty-three apostrophes, seven hyphens and, last but not least, a single !".lower()

# Convert the string to an array of integers
numbers = np.array([ord(c) for c in sentence])
u = np.unique(numbers)
# Make the integers range from 0 to n so there are no gaps in the histogram
# [0][0] was a hack to make sure `np.where` returned an int instead of an array.
ind = [np.where(u==n)[0][0] for n in numbers]
bins = range(0,len(u)+1)
hist, bins = np.histogram(ind, bins)

plt.bar(bins[:-1], hist, align='center')
plt.xticks(np.unique(ind), [str(unichr(n)) for n in set(numbers)])
plt.grid()
plt.show()

Which generates

Please let me know how to improve my code. Also, please let me know what I did wrong with plt.xticks that resulted in the gaps at the beginning and the end (or is that just a case of incorrect axis limits?).

Your code is pretty good!  I have only one substantive and a few stylistic suggestion.

Style

Since sentence is a hard-coded variable, Python convention is that it should be in all-uppercase, i.e. SENTENCE is a better variable name.
What are u and n in your code?  It's hard to figure out what those variables mean.  Could you be more descriptive with your naming?
Your call to .lower() on sentence is hidden after the very long sentence.  For readability I wouldn't hide any function calls at the end of very long strings.
Python has multi-line string support using the """ delimiters.  Using it makes the sentence and the code more readable, although at the expense of introducing newline \n characters that would show up on the histogram if they are not removed.  In my code below I use the """ delimiter and remove the \n characters I introduced to break the string into screen-width-sized chunks.  PEP8 convention is that code lines shouldn't be more than about 80 characters long.
You should consider breaking this code up into two functions, one to make generate the data, and one to make the graph, but we can leave that for another time.

Substance

Since your sentence is a Python string (not a NumPy character array), you can generate the data for your histogram quite easily by using the Counter data type that is available in the collections module.  It's designed for exactly applications like this.  Doing so will let you avoid the complications of bin edges vs. bin centers that stem from using np.histogram entirely.

Putting all these ideas together:

import matplotlib.pyplot as plt
import numpy as np
from collections import Counter

SENTENCE = """Only the fool would take trouble to verify that his sentence was composed of ten a's, three b's, four c's,
four d's, forty-six e's, sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's, four m's, twenty-five n's,
twenty-four o's, five p's, sixteen r's, forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four x's,
eleven y's, twenty-seven commas, twenty-three apostrophes, seven hyphens and, last but not least, a single !"""

# generate histogram
letters_hist = Counter(SENTENCE.lower().replace('\n', ''))
counts = letters_hist.values()
letters = letters_hist.keys()

# graph data
bar_x_locations = np.arange(len(counts))
plt.bar(bar_x_locations, counts, align = 'center')
plt.xticks(bar_x_locations, letters)
plt.grid()
plt.show()

Other

It wasn't anything you did with plt.xticks that led to the gaps.  That's the matplotlib default.  If you want a "tight" border to the graph, try adding a plt.xlim(-0.5, len(counts) - 0.5) before the plt.show().


Changing color on button click I have an html button that when the user clicks the button it will change color from blue to red and back.  Is there a better way to do this in jQuery?

HTML/jQuery

<html>
<head>
    <title>Button Fun</title>
    <script src = 'bower_components/jquery/dist/jquery.js'></script>
    <script type="home.js"></script>
    <link rel="stylesheet" type="text/css" href="styles.css"/>
    <script type="text/javascript">
    clicked = true;
    $(document).ready(function(){
        $("button").click(function(){
            if(clicked){
                $(this).css('background-color', 'red');
                clicked  = false;
            } else {
                $(this).css('background-color', 'blue');
                clicked  = true;
            }
        });
    });
    </script>
</head>
<body>

    <button>Press</button>

</body>
</html>

CSS

button{
    background-color: blue;
    height:100px;
    width:150px;
}

$("button").click(function(){
    if(clicked){
        $(this).css('background-color', 'red');
        clicked  = false;
    } else {
        $(this).css('background-color', 'blue');
        clicked  = true;
    }
});

You could do it like this instead

$("button").click(function(){
    var color = clicked ? 'red' : 'blue';
    $(this).css('background-color', color);
    clicked = !clicked;
});

We move the color picking to a single variable choice using a ternary statement and then we only have to write out the change to the CSS of the element once. then we flip the boolean.

I don't like the name of the boolean variable, it doesn't accurately describe what it is keeping track of, based on the way the code is written it should be named isButtonBlue.

If the button is blue, turn it red. If the button is not blue, turn it blue.

After looking at this a little bit longer I was thinking that you could make it one line shorter by making another line longer by moving the ternary statement into the CSS change

$("button").click(
    $(this).css('background-color', isButtonBlue ? 'red' : 'blue');
    isButtonBlue = !isButtonBlue;
});


Find the best path amongst N random points For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points.
I wanted to use a dynamic programming approach as N will be limited to a maximum of 15 points.

The following program works for me running

python dp.py

with python 2.7.3.

I would appreciate any tips to improve the speed and the memory use of that program.

The content of dp.py is

import random
import math

# Container for the points
points = []

# Generate N random points
def create_random_points(size):
    global points
    for n in range(size):
        x = random.uniform(0, 500)
        y = random.uniform(0, 500)
        points.append([x, y])

# Find the path through those points
def order_points():
    global points

    # How many points do we have?
    L = len(points)

    # No points at all
    if L < 1:
        return []

    # A single point
    if L == 1:
        return [0]

    # Calculate all the different distances
    distances = [0 for n in range(L * L)]

    for n in range(L):
        for m in range(n):
            A = points[n]
            B = points[m]
            distances[n * L + m] = math.sqrt((B[0] - A[0]) ** 2 + (B[1] - A[1]) ** 2)
            distances[m * L + n] = distances[n * L + m]

    # Calculate the best path: dynamic programming
    # Initialise the distance and path variables
    sum_path = [0 for n in range(L - 1)]
    path = [[0] for n in range(L - 1)]

    # Calculate the first iteration
    for point_m in range(1, L):
        sum_path[point_m - 1] += distances[point_m]
        path[point_m - 1].append(point_m)

    # Calculate the following iterations
    for n in range(1, L - 1):
        for point_m in range(1, L):
            dist = -1
            prev = -1
            for point_n in range(1, L):
                if point_n == point_m:
                    continue
                if point_n in path[point_m - 1]:
                    continue

                d = distances[point_m * L + point_n]
                if dist == -1 or dist < d:
                    dist = d
                    prev = point_n
            sum_path[point_m - 1] += dist
            path[point_m - 1].append(prev)

    # Calculate the last iteration
    for point_m in range(1, L):
        sum_path[point_m - 1] += distances[point_m]
        path[point_m - 1].append(0)

    best_score = min(sum_path)
    for point_m in range(1, L):
        if sum_path[point_m - 1] == best_score:
            best_path = path[point_m - 1]

    return best_path

create_random_points(5)

print 'We have the following points:'
print points

print ''
print 'And the best path is:'
print order_points()

One minor way to improve speed would be not to calculate the square root of all of the distances before comparison, but instead only return the square root of the shortest distance squared because the square root function is costly.


Renaming file in C# on Server I am using the following code to rename the uploaded files for any future name clashes. Please tell if my approach is right or I should follow some other approach or approach which is better.

[HttpPost]
    public ActionResult Upload(HttpPostedFileBase fileData)
    {
        if (fileData != null && fileData.ContentLength > 0)
        {
            //var fileName = Server.MapPath("~/Content/Images/" + Path.GetFileName(fileData.FileName));
            int pictureCount = 800000;
            pictureCount += db.Pictures.Count();
            string extension = Path.GetExtension(fileData.FileName);
            string renamedImage = Server.MapPath("~/Content/Images/Categories/cat" + pictureCount + extension);
            fileData.SaveAs(renamedImage);
            return Json(Path.GetFileName(renamedImage));
        }
        return Json(false);
    }

If you have two simultaneous file uploads db.Pictures.Count(); will return same number. So you will get a name clash.

If db.Pictures is a database then you can create and auto increment identity field and use it to save the file.

If there is no option with database you can use two more approaches:
Use GUID instead of picture name

[HttpPost]
public ActionResult Upload(HttpPostedFileBase fileData)
{
    if (fileData != null && fileData.ContentLength > 0)
    {
        string extension = Path.GetExtension(fileData.FileName);

        string renamedImage = null;
        do
        {
            renamedImage = Server.MapPath("~/Content/Images/Categories/cat" + System.Guid.NewGuid().ToString("N") + extension);

        } while( /*verify that renamedImage file does not exist*/ );

        fileData.SaveAs(renamedImage);
        return Json(Path.GetFileName(renamedImage));
    }
    return Json(false);
}

The drawback of this approach is that it is possible to upload same pictures to the server.

To mitigate that you can try using hash of the image as a file name. Before writing file contents to the disk check if that file already exists. Note: the check and file save operation must be made in thread-safe manner.


Generating HTML for prerolled d20 RPG initiative tables A fairly simple program that I tried to write in Common Lisp in order to practice/learn. I'm sure this can be done more elegantly but Lisp's string handling seems to be very werd.

(defun d20 () (+ 1 (random 19)))

(defun initlist (specs)
  (let* ((ilist (map 'list #'(lambda (n) `(,(first n) ,(+ (second n) (d20)))) specs))
         (sortedilist (sort ilist #'> :key #'second)))
    sortedilist))

(defun htmlinitlist (specs)
  (apply #'uiop:strcat `("

&nbsp;	&nbsp;
"
   ,@(loop for (a b) in (initlist specs) collecting
        (format nil "
~A	~A

&nbsp;	&nbsp;
"
                a b))
   "
")))

(defun htmlinitlists (specs count)
  (format nil "~{ ~A~}" (loop for i from 0 to count collecting (htmlinitlist specs))))

Sample usage from REPL:

(htmlinitlists '(("Elvish" 5) ("Wizgit" 2) ("Alaric" 8) ("Pounder" 6)) 17)

I wouldn't use strings at all. I would write to a stream.

If wished, I would convert the stream to a string.

(defun d20 () (+ 1 (random 19)))

initlist can be written more compact:

(defun initlist (specs)
  (sort (loop for (a b) in specs collect (list a (+ b (d20))))
        #'> :key #'second))

Now we pass a stream to htmlinitlist and write the contents to the stream:

(defun htmlinitlist (specs stream)
  (write-string "

&nbsp;	&nbsp;
" stream)
  (loop for (a b) in (initlist specs) do
        (format stream
                "
~A	~A

&nbsp;	&nbsp;
"
                a b))
  (write-string "
" stream))

If we want to get a string from a stream, we can use with-output-to-string. This binds a stream variable, which we can use and pass around...

(defun htmlinitlists (specs count)
  (with-output-to-string (stream)
    (write-char #\space stream)
    (loop repeat (1+ count) do (htmlinitlist specs stream))))

Alternate version of htmlinitlist using only one FORMAT call:

(defun htmlinitlist (specs stream)
  (format stream
          "

&nbsp;	&nbsp;
~
           ~{
~A	~A

&nbsp;	&nbsp;
~}~

"
          (loop for (a b) in (initlist specs) collect a collect b)))

Benefit

All the various string operations (which are creating lots of intermediate strings which are immediately garbage) have been replaced with the usual output functions and a stream.


"Kinda" addition chain calculator I build an addition chain (more information about addition chains: Wikipedia) calculator that produces shorter chains than chains with the length equal to the number that's being tried to achieve.
It doesn't always produces the shortest chains (if were talking about a big number). However still gives a pretty short chain compared to the max sized chain the number would get.
It is faster than, brute-force calculating (but obv. less accurate in finding the shortest chain (like I said above)), since it relies on an algorithm (I'm not sure if an algorithm is the right word, but basically I just used logical steps to find a short chain). Basically it starts from the given number and goes backwards to 1.

It works as followed:

Check if the number is even or odd, if it's odd check if it's a prime number.
If it's an even number, just divide by 2. If it's odd find the biggest factor and divide the number by it, till the factor itself is reached. If it's a prime number, subtract it by 1 and follow the steps for an even number
Step 1 and 2 are always repeated, and before (before and after would duplicate the values, so only 'before') every action, the current state of the number is added to a list

(It is also checking if every number had (n+1)/2 length of chains, so there's a tiny step for that, but that's not very important. This was an extra thing I did, for my math class.)
So let's say we have 5, it's an odd number so we subtract by 1 to get an even number: 4. Now we divide it by 2 and get 2, since 2 is also an even number we divide again and we got to 1 and the program stops and prints the list which is: [5, 4, 2, 1] (which is the shortest possible addition chain (I know that this only works for tiny numbers btw, for big numbers it still shortens the chain (of max size) a lot which is cool for me))

I am learning programming by myself and haven't touched sort/search algorithms, what could I have done better in terms of the quality of my code or even the logical steps I use to calculate?

n = int(input())  # kan tot 8 cijfers snel(<1min), na 8 traag

BewijsN = (n + 1) / 2

List1 = []

def IsEven(n):
    if n % 2 == 0:
        return True

    else:
        return False

def IsPrime(n):
    for x in range(n - 2):
        x += 2

        if n % x == 0:
            return False

    return True

def BigFactorCheck(n):
    for x in range(n):
        x += 1

        if n % (n - x) == 0:
            return n - x

while n > 1:
    if IsEven(n) == False:

        if IsPrime(n):
            List1.append(n)
            n += -1  # Prim naar even

        else:  # Oneven
            List1.append(n)
            BigFactor = BigFactorCheck(n)

            for x in range((n // BigFactor) - 2):
                x += 1
                List1.append(n - BigFactor * x)

            n = n - BigFactor * (x + 1)  # lelijk, maar werkt

    while IsEven(n):
        List1.append(n)
        n = n // 2

        if n == 1:
            List1.append(n)

List1.sort()
print(len(List1), List1)
if len(List1) - 1 <= BewijsN:
    print(True, len(List1) - 1, "<=", BewijsN)

Code Organization
Code should be organized in such a way that someone reading the code doesn't have to scroll up and down in order to understand the code.  For instance, you should not have:
mainline code
function definitions
mainline code

Instead, the mainline code should all be together at the bottom:
function definitions
mainline code

Naming
The PEP 8 -- Style Guide for Python Code lists a number of rules guidelines that should be followed throughout Python code.  One such guideline is:

function and variable names should be in snake_case; MixedCase is reserved for class names.

So BewijsN and List1 should become bewijs_n and list_1.  Similarly, IsEven, IsPrime and BigFactorCheck should be is_even, is_prime, and big_factor_check.
List1 is especially ugly.  There is no List2, List3 and so on, so why is there a 1 in that name?  number_chain might make a better name.
Boolean Test
def IsEven(n):
    if n % 2 == 0:
        return True

    else:
        return False

The function body reads approximately:
    if something is True:
        return True
    else:
        return False

Since something will be True in the "then" clause, instead of returning the literal True, we could return something.  Similarly, when something is False, in the "else" clause, instead of returning the literal False, we could also return something:
    if something is True:
        return something
    else:
        return something

At this point, we can see the if ... else is irrelevant; in both cases, we return something.  So we can optimize this to:
    return something

specifically:
def is_even(n):
    return n % 2 == 0

Range
The IsPrime function has this code:
    for x in range(n - 2):
        x += 2

This is confusing and inefficient.  Confusing because the loop variable x starts at 0, and is modified inside the loop, increasing it to 2; what is it on the next iteration?  Of course, the modification inside the loop body is lost when the next iteration begins, but that will often confuse a newcomer to Python.
It is inefficient, since because adding 2 each time through the loop is an unnecessary operation, which takes time.  Numbers are objects, and every time a computation changes a number, the old number object is dereferenced (and possibly destroyed), and a new number object may be created.  It is far faster to simply loop over the correct range: range(2, n).
def is_prime(n):
    for x in range(2, n):
        if n % x == 0:
            return False
    return True

This loop can actually be simplified and sped up, using the all(...) function and a generator expression:
def is_prime(n):
    return all(n % x != 0 for x in range(2, n))

There are many things you can do to further speed up this is_prime function.  If the number would be divisible by an even number larger than 2, it would have already been divisible by 2, so you can call that out as a special case, and then only consider odd numbers 3 and up, using range(3, n, 2):
def is_prime(n):
    if n > 2 and n % 2 == 0:
        return False

    return all(n % x != 0 for x in range(3, n, 2))

Also, looking for factors larger than \$sqrt(n)\$ is inefficient, since if \$x > sqrt(n)\$ was a factor, then \$n / sqrt(n) < sqrt(n)\$ would also be a factor, and you would have already encountered it:
from math import isqrt

def is_prime(n):
    if n > 2 and n % 2 == 0:
        return False

    return all(n % x != 0 for x in range(3, isqrt(n) + 1, 2))

Due to isqrt(n), this will crash if called with a negative value.  Crashing is bad.  What did your function do?  IsPrime(-10) returned True, which is incorrect, which is arguably worse than crashing.  At least if you crash, you know something went wrong, and get a stack trace you can debug.  A wrong result is harder to debug, since you don't know where it went wrong.  While we're at it, neither 0 nor 1 should return True:
from math import isqrt

def is_prime(n):
    if n < 2 or (n > 2 and n % 2 == 0):
        return False

    return all(n % x != 0 for x in range(3, isqrt(n) + 1, 2))

This is faster and more correct.  You could improve it even further, with more advanced prime checking, such as the sieve-of-eratosthenes.
Big Factor Check
def BigFactorCheck(n):
    for x in range(n):
        x += 1

        if n % (n - x) == 0:
            return n - x

On the last iteration, x initially is n-1, but you add 1 to it, so x actually would be n.  Then n % (n - x) would be n % (n - n), or n % 0, which is a division by zero!  Eek.  Fortunately, you never reach the last iteration; the previous iteration would test n % 1 == 0, which should always be true.  Still, dangerous code.
Again, for x in range(n) and x += 1 could simply become for x in range(1, n+1).  But you don't simply want x; you want n - x.  Why not just loop starting a n-1, and go down until you reach n - (n-1)?  You don't even need to try the n % 1 == 0 iteration; you could stop before reaching 1, and simply return 1 if you get to the end of the for loop:
def big_factor_check(n):
    for x in range(n - 1, 1, -1):
        if n % x == 0:
            return x
    return 1

Main function
Your mainline code is complex enough to warrant its own function.  You could even add a main-guard, so you can import this function into other programs if you want to use it, without executing the mainline code.
def addition_chain(n):
    number_chain = []
    while n > 1:
        # your computations here

    number_chain.sort()
    return number_chain

if __name__ == '__main__':
    n = int(input())
    bewijs_n = (n + 1) / 2
    chain = addition_chain(n)
    print(len(chain), chain)
    if len(chain) - 1 <= bewijs_n:
        print(True, len(chain) - 1, "<=", bewijs_n)


My own Queue Implementation in Java Please review my Queue implementation and let me know if you have any suggestions. I am not returning an exception for any of the methods defined here. As we know the exception is thrown only for add and remove functions and not for poll or offer functions.

    public class QueueImplementation<T> {
    private QueueNode<T> first;
    private QueueNode<T> last;
    private int size;

    private static class QueueNode<T> {
        private T val;
        private QueueNode<T> next;

        public QueueNode(T val) {
            this.val = val;
            this.next = null;
        }

        public void setNext(QueueNode<T> nextNode) {
            next = nextNode;
        }

        public QueueNode<T> getNext() {
            return next;
        }

        public T getValue() {
            return val;
        }

        @Override
        public String toString() {
            if(val == null) {
                return "null";
            }
            return val.toString();
        }

    }

    public void offer(T val) {
        QueueNode<T> cur = new QueueNode(val);
        if(size == 0) {
            cur.setNext(first);
            first = cur;
            last = cur;
            size++;
            return;
        }

        last.setNext(cur);
        last = cur;
        size++;
    }

    public T peek() {
        if(!isEmpty()) {
            return first.getValue();
        }
        else {
            return null;
        }
    }

    public QueueNode<T> poll() {
        if(isEmpty()) {
            return null;
        }

        QueueNode<T> cur = first;
        first = first.getNext();
        size--;
        return cur;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        if(size == 0) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        QueueNode<T> cur = first;
        sb.append(cur.getValue() + "<-");

        while(cur.getNext() != null && !cur.equals(last)) {
            sb.append(cur.getNext().getValue() + "<-");
            cur = cur.getNext();
        }

        return sb.append("null").toString();
    }

    public static void main(String[] args) {
        QueueImplementation<Integer> q = new QueueImplementation<>();
        System.out.println(q.size());
        System.out.println(q.poll()); //returns null;
        System.out.println(q.peek()); //return null;
        q.offer(1);
        q.offer(10);
        q.offer(100);
        System.out.println(q.size());
        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.size());
        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.size());
        System.out.println(q.poll());
    }
}

@Override
public String toString() {
    if(size == 0) {
        return "[]";
    }

    StringBuilder sb = new StringBuilder();
    QueueNode<T> cur = first;
    sb.append(cur.getValue() + "<-");

    while(cur.getNext() != null && !cur.equals(last)) {
        sb.append(cur.getNext().getValue() + "<-");
        cur = cur.getNext();
    }

    return sb.append("null").toString();
}

Empty stack prints "[]", stack with one element prints 1<-null. Where are the surrounding brackets? Also, you can use a do-while loop here to prevent needing to specify how to print twice:

@Override
public String toString() {
    if(size == 0) {
        return "[]";
    }

    StringBuilder sb = new StringBuilder();
    QueueNode<T> cur = first;

    do {
        sb.append(cur.getValue() + "<-");
        cur = cur.getNext();
    } while(cur != null);

    return sb.append("null").toString();
}

It also vastly simplifies the iteration.

public void offer(T val) {
    QueueNode<T> cur = new QueueNode(val);
    if(size == 0) {
        cur.setNext(first);
        first = cur;
        last = cur;
        size++;
        return;
    }

    last.setNext(cur);
    last = cur;
    size++;
}

This could be simplified to reduce duplication - step 1, making the else case explicit...

public void offer(T val) {
    QueueNode<T> cur = new QueueNode(val);
    if(size == 0) {
        cur.setNext(first);
        first = cur;
        last = cur;
        size++;
    } else {
        last.setNext(cur);
        last = cur;
        size++;
    }
}

Step two, moving similar instructions into the shared area.

public void offer(T val) {
    QueueNode<T> cur = new QueueNode(val);
    if(size == 0) {
        cur.setNext(first);
        first = cur;
    } else {
        last.setNext(cur);
    }
    last = cur;
    size++;
}

Additionally, you can make use of isEmpty() here for increased clarity.

public QueueNode<T> poll() {
    if(isEmpty()) {
        return null;
    }

    QueueNode<T> cur = first;
    first = first.getNext();
    size--;
    return cur;
}

poll() is returning internal nodes. You want to return the value instead. Don't expose your internal nodes. Use exceptions for indicating pulling from an empty queue.


A script that uses placeholder attribute to show a typing effect An easy to use type feature that uses the placeholder attribute and setTimer to give the effect of a user typing. Helpful if you need to draw attention to the search box field.

I'm looking to know if this type of implementation would be a performance impact or cause browser lag. Help in making this more condensed would also be helpful. I was thinking about using $.extend, but leaned away. Any reason why I shouldn't make this a jquery plugin?

https://jsfiddle.net/googabeast/jsepy3ed/

obj = {
    searchTxt: [
        "Welcome. What are you searching for? ",
        "Something else to type out "
        "Note the space at the end -> "
    ],
    hasFocus:false
}

if(obj.searchTxt !== null && obj.searchTxt !== "undefined"){
    var i = 0, ct = 0; obj.typeIt;

    function type(){
        obj.typeIt = obj.searchTxt[ct].slice(0, ++i);
        if(obj.typeIt === obj.searchTxt[ct]){
            i = 0;
            if(ct === obj.searchTxt.length-1){
                ct = 0;
            }else{
                ++ct;
            }
            return;
        };
        $(".searchBox").attr("placeholder", obj.typeIt);
        setTimeout(type, 80);
    };
    type();

    $(window).on({
        focus: function(){ obj.hasFocus = true; },
        blur: function(){ obj.hasFocus = false; }
    }).trigger("focus");

    setInterval(function(){
        if(obj.hasFocus){
            type();
        };
    }, 10000);
};

Performance Considerations

As the code stands now, every time the type function is invoked (that is, every 80 milliseconds) the code will parse the DOM looking for any elements with the searchBox class.

You can improve the code's efficiency by moving that expensive operation outside the function.

var i = 0, ct = 0, searchBox = $(".searchBox"); obj.typeIt;

function type(){
    // ...
    searchBox.attr("placeholder", obj.typeIt);
    // ...
};

If you know there'll only be one element with the searchBox class, you could improve its efficiency a step further by using the native document.querySelector method.

var i = 0, ct = 0, searchBox = document.querySelector(".searchBox"); obj.typeIt;

function type(){
    // ...
    searchBox.setAttribute("placeholder", obj.typeIt);
    // ...
};

Timeout/Interval Overlap

This one's not a biggie, but it's good to be aware of when working with setTimeout and setInterval.

Your interval function is running every 10 seconds to invoke type, while within the type function a timeout is running every 80 milliseconds to invoke type again (until the end of the search text short circuits that behavior).

If the code happens to be in the middle of writing out some search text when the 10-interval kicks in, you'll see some unusual behavior: multiple characters will be written within 80 milliseconds.

For something like this, that's probably not a major issue (you'll only see it happen when the search text is abnormally long or the interval time is abnormally short), but if you want to account for it, you can eliminate setInterval altogether. Instead, you can put a 10-second timeout in the "dead end" branch of the type function (the if block that short-circuits the 80-ms timeout upon reaching the end of the search text), just before the return statement.

function type(){
    obj.typeIt = obj.searchTxt[ct].slice(0, ++i);
    if(obj.typeIt === obj.searchTxt[ct]){
        i = 0;
        if(ct === obj.searchTxt.length-1){
            ct = 0;
        }else{
            ++ct;
            /* This replaces the setInterval call later in your code: */
            setTimeout(function(){
                if(obj.hasFocus){
                    type();
                }
            },10000);
        }
        return;
    };
    $(".searchBox").attr("placeholder", obj.typeIt);
    setTimeout(type, 80);
};

This ensures that type is invoked every 80 milliseconds while typing out the search text, and then every 10-seconds between search texts.

Another option is to use the clearTimeout method to make sure you don't have duplicate timeouts for the same function call running in parallel.

// define a timeout variable
var i = 0, ct = 0, timeout; obj.typeIt;

function type(){
    // ...
     if(timeout){clearTimeout(timeout);} // eliminate duplicate timeouts
     timeout = setTimeout(type, 80);
}

This is useful if there are multiple entry points for the type function, such as if you were to invoke it from the window's onFocus event.


CancellationToken and Reactive Extensions I have a couple of calls that I need to cancel a subscription based on a CancellationToken.  I saw How to cancel an observable sequence but I needed a more generic way.  I created an extension method that seems to work.

public static IObservable<TSource> TakeUntil<TSource>(this IObservable<TSource> source, CancellationToken token)
{

    var cancelationObservable =
        Observable.Create<object>(observer => token.Register(() => observer.OnNext(null)));
    return source.TakeUntil(cancelationObservable);
}

Is there a built in way of Rx to cover this?  Is Observable.Create the best way to trigger the pulse?

This seems so basic that I feel I may be missing something.

I need to cancel a subscription

If you're actually subscribing to the source using Subscribe(), then that has overloads that accept a CancellationToken, you might want to consider using that.

Observable.Create<object>(observer => token.Register(() => observer.OnNext(null)));

It took me a while to figure out that this doesn't cause a memory leak. I thought that since you call Register(), but never use the returned IDisposable to unregister, the registrations will stay there even when they are no longer needed. But that's not true, because the IDisposable is actually returned to Create(), which will Dispose() it when it's no longer needed.

I think this is confusing enough that it warrants a comment explaining the situation.

Also, the common way to express the void type in generics in Rx is the Unit type, not object:

Observable.Create<Unit>(observer => token.Register(() => observer.OnNext(Unit.Default)));

This is longer than your code, but I think it's also clearer.


Find the sum of the digits of a given number I need to find the sum of the digits of the given number and repeat the process until the value lies between 1 to 9.

e.g
if the input is 72457 then,

7+2+4+5+7 = 25

2+5 = 7

so , the function should return 7.

Also, if the input is a negative number like -72457 the function should return -7.

Here's what i tried,

int digitSum(int input1){

int flag=0;

if(input1<0)
     flag=1;

 int rem,sum=0;
 int x=abs(input1);

 while(x>0){
    rem=x%10;
    sum+=rem;
    x=x/10;

    }

 int value = sum%9;

 if(value==0){

    if(flag==1)
     return -9;

    else
     return 9;
 }

 else{

  if(flag==1)
   return -value;

   else
    return value;

 }

}

A simplified pure numerical function may be:

int digitSum(int input) {
    int n,m,s = input<0 ? -1:1;
    for(n=input*s; n>9; ) {
        for(m=n, n=0; m>0; m/=10)
            n+=m%10;
    }
    return n*s;
}


Sorting and Searching Algorithm The searching algorithm that I created is dependent upon the sorting algorithm (which many of you have seen in my previous question). I believe that the sorting algorithm can't be better (for beginner-level programmers like me) but I would like to know what you think about my descriptions for the searching algorithm.
I would appreciate your insight on the commented sections of my code (again, for the searching algorithm).
And if there are any other changes I can make, please don't hesitate to let me know.
def sorting_algorithm(list):
    for index in range(1, len(list)):
        current = list[index]
        while index > 0 and list[index - 1] > current:
            list[index] = list[index - 1]
            index = index - 1
            list[index] = current
    return list

print("the sorted list is", (sorting_algorithm([45, 14, 1, 7, 98, 23, 102, 57])))

#SEARCHING ALGORITHM CODE:

def searching_algorithm(list, num):
    fir = 0                                        #the first number of the list.
    las = len(list)-1                              #the last number of the list.
    i = -1                                         #the index is at the last number of the list.
    while (fir <= las) and (i == -1):              #the first number is less than or equals to the last number and the
                                                   #index is at -1 (so the last number).
        mid = (fir + las) // 2                     #the middle number is equal to the first num divided by the last number
                                                   #but without the remainder part.
        if list[mid] == num:                       #if the middle number of the list equals the number
            i = mid                                #then the index is moved to the middle number of the list.
        else:                                      #if that isn't true then we move on to the following condition.
            if num<list[mid]:                      #if the number is less than the middle number of the list
                las = mid -1                       #then the index moves one to the right.
            else:                                  #if that isn't true either, then move on to the following condition.
                fir = mid +1                       #then the program will conclude that the number is the greater than
                                                   #the middle number.
    return i

print("your number is at index",searching_algorithm([1, 7, 14, 23, 45, 57, 98, 102], 23))

The code is overcommented. Most of the comments do not add any value. They explain what the code is doing, which is obvious; the good comment shall explain why and how the code is doing what it is doing. Some of them are outright wrong, e.g.
   #the middle number is equal to the first num divided by the last number

Say what? Nothing is divided by the last number!
In any case, try to avoid comments. A presence of an explanatory comment means the failure to express yourself in the code.

As mentioned in the comment (no pun intended), the code implements a binary search.
  (fir + las) // 2

is all right in Python with its arbitrarily long integers; in most other languages, which deal with the native integers, computing fir + (las - fir) / 2 is indeed preferable.

Testing for i == -1 looks smelly. Most of the times i remains -1, and it only gets the meaningful value when the target number is found. When the condition
  list[mid] == num

is satisfied, it is a time to break the loop, or even return i right away.

Detour.
Returning -1 when the target number is not there is not right. All the work your function have done is suddenly discarded. Don't be discouraged: you are in the good company. bsearch from the standard C library makes the same blunder.
It is very helpful to return an insertion point instead: where the target number would have been. See how bisect.bisect_left()  does it right (ditto for C++ std::lower_bound).


Leetcode 102: Binary tree level-order traversal in Swift 102. Binary Tree Level Order Traversal

  Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

  For example:

  Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

  return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

This is my solution in Swift:

func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else{
            return []
        }
        let nodes = recursiveVisit(root)
        let capacity = nodes.reduce([Int]()) {
            if $0.contains($1.0) == false {
                return $0 + [$1.0]
            }
            return $0
        }.count
        return nodes.reduce([[Int]](repeating: [], count: capacity), {
          var tmp = $0
            tmp[$1.0].append($1.1)
            return tmp
        })
    }

func recursiveVisit(_ node: TreeNode?) -> [(Int, Int)]{
        //  [(Int,  Int)]
        //  depth,      node.val

        guard let node = node else{
            return []
        }

        var nodes = [(Int, Int)]()
        nodes.append((0, node.val))

        let lhs = recursiveVisit(node.left).map {
            return ($0.0 + 1, $0.1)
        }

        let rhs = recursiveVisit(node.right).map {
            return ($0.0 + 1, $0.1)
        }
        nodes.append(contentsOf: lhs)
        nodes.append(contentsOf: rhs)
        return nodes
    }

The solution is very intuitive: collect the nodes' value and depth, then reduce to the answer.

It is not as well designed as the Java Solution, though.

My question is mainly on the Swift syntax.  Is there any other way to do it more lean? Combine the two reduce() calls to one, for example?

Simplifying your code

Let's start here:

let capacity = nodes.reduce([Int]()) {
    if $0.contains($1.0) == false {
        return $0 + [$1.0]
    }
    return $0
}.count

The test

if $0.contains($1.0) == false

is shorter (and – in my opinion – better) written as

if !$0.contains($1.0)

Each invocation of the closure creates a new array. In such cases it is more efficient to use reduce(into:) with a closure that updates the array:

let capacity = nodes.reduce(into: [Int]()) {
    if !$0.contains($1.0) {
        $0.append($1.0)
    }
}.count

But what this code actually does is to determine the number of distinct levels in the nodes array. That is simpler and more efficiently done with a set:

let capacity = Set(nodes.map { $0.0 }).count

Here

return nodes.reduce([[Int]](repeating: [], count: capacity), {
    var tmp = $0
    tmp[$1.0].append($1.1)
    return tmp
})

a new nested array is created with each invocation of the closure. Again, this can be improved with reduce(into:), so that the first function becomes

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else {
        return []
    }
    let nodes = recursiveVisit(root)
    let capacity = Set(nodes.map { $0.0 }).count
    return nodes.reduce(into: [[Int]](repeating: [], count: capacity), {
        $0[$1.0].append($1.1)
    })
}

I have only minor suggestions for the second function:

var nodes = [(Int, Int)]()
nodes.append((0, node.val))

can be combined to

var nodes = [(0, node.val)]

The results of the recursive calls can be appended to the nodes array directly:

nodes += recursiveVisit(node.left).map {
    return ($0.0 + 1, $0.1)
}
nodes += recursiveVisit(node.right).map {
    return ($0.0 + 1, $0.1)
}

And if you use tuple labels then the code becomes better readable (and almost self-documenting):

func recursiveVisit(_ node: TreeNode?) -> [(level: Int, value: Int)] {

    guard let node = node else {
        return []
    }
    var nodes = [(level: 0, value: node.val)]
    nodes += recursiveVisit(node.left).map {
        return (level: $0.level + 1, value: $0.value)
    }
    nodes += recursiveVisit(node.right).map {
        return (level: $0.level + 1, value: $0.value)
    }
    return nodes
}

This can be used in the first function as well. As an alternative, define a custom struct with “level” and “label” members.

Alternative #1 – A nested function

It is not necessary to create an array of (level, value) tuples first. You can add a value to the sublist on the current level, or append a new level while traversing the tree recursively. With a nested function you don't even have to pass the array around:

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    var levels: [[Int]] = []

    func recursiveVisit(_ node: TreeNode?, level: Int) {
        guard let node = node else {
            return
        }
        if level < levels.count {
            levels[level].append(node.val)
        } else {
            levels.append([node.val])
        }
        recursiveVisit(node.left, level: level + 1)
        recursiveVisit(node.right, level: level + 1)
    }

    recursiveVisit(root, level: 0)
    return levels
}

Alternative #2 – Iteration instead of recursion

The referenced Java solution solves the task with iteration, and a list containing all nodes on the current level. Of course that can be done in Swift as well. Here is an example of a quite compact implementation:

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else {
        return []
    }

    var wrapList: [[Int]] = []
    var queue = [root] // First level

    while !queue.isEmpty {
        // All values of nodes on the current level:
        wrapList.append(queue.map { $0.val })
        // Replace queue by list of all nodes on the next level:
        queue = queue.flatMap { [$0.left, $0.right ] }.compactMap { $0 }
    }

    return wrapList
}


How can I make my stack monad faster? I made a stack monad that lets one manipulate and control values on a stack.

I want to know if it's correct (it seems correct), how to make it faster, and how I could detect stack overflows without carrying around the stack size and checking against it (I've heard about guard pages but I have no idea how I'd use them with Haskell).

{-# LANGUAGE RankNTypes #-}
module Main where

import Data.IORef

import Foreign.Ptr
import Foreign.Storable
import Foreign.Marshal.Alloc

import Control.Exception ( bracket )

import System.IO.Unsafe

newtype StackRef s a = StackRef (Ptr a)

data Stack = Stack (Ptr ())
newtype StackMonad s a = StackMonad (Stack -> IO (Stack, a))

instance Monad (StackMonad s) where
 return x = ioToStackMonad (return x)
 (StackMonad m) >>= f = StackMonad $ \stack -> do
   (newStack, x) <- m stack
   let (StackMonad g) = f x
   g newStack

runStackWithSize :: Int -> (forall s. StackMonad s a) -> a
runStackWithSize stackSize (StackMonad f) = unsafePerformIO $
 bracket (mallocBytes stackSize) free $ \theStack -> do
  (_, a) <- f (Stack theStack)
  return a

-- | 1024 bytes is the usual size for a stack
runStack :: (forall s. StackMonad s a) -> a
runStack = runStackWithSize 1024

newStackRef :: Storable a => a -> StackMonad s (StackRef s a)
newStackRef value = StackMonad $ \(Stack topOfStack) -> do
 let ptr = castPtr (alignPtr topOfStack (alignment value))
 poke ptr value
 return (Stack (plusPtr ptr (sizeOf value)), StackRef ptr)

ioToStackMonad :: IO a -> StackMonad s a
ioToStackMonad action = StackMonad $ \ptr -> do
 a <- action
 return (ptr, a)

writeStackRef :: Storable a => StackRef s a -> a -> StackMonad s ()
writeStackRef (StackRef p) val = ioToStackMonad (poke p val)

readStackRef :: Storable a => StackRef s a -> StackMonad s a
readStackRef (StackRef p) = ioToStackMonad (peek p)

{- |
 The type hackery means that pointers to the old stuff isn't reachable,
 therefore it's okay to pop the stack pointer.
-}
stack :: (forall s. (forall b. StackRef t b -> StackRef s b) -> StackMonad s a) -> StackMonad t a
stack f = let (StackMonad s) = f (\(StackRef p) -> StackRef p) in StackMonad $ \old_ptr -> do
 (_, state) <- s old_ptr
 return (old_ptr, state)

stack_ :: (forall s. (forall b. StackRef t b -> StackRef s b) -> StackMonad s ()) -> StackMonad t ()
stack_ f = let (StackMonad s) = f (\(StackRef p) -> StackRef p) in StackMonad $ \old_ptr -> do
 _ <- s old_ptr
 return (old_ptr, ())

x :: Int
x = runStack $ do
 a <- newStackRef 5

 c <- stack $ \lift1 -> do
  b <- newStackRef 1

  let liftedA = lift1 a
  aValue <- readStackRef liftedA
  writeStackRef liftedA 6
  bValue <- readStackRef b
  return (aValue + bValue)
 newAValue <- readStackRef a
 return (c + newAValue)

main = print x

This code is simply incorrect. It is even not a stack (because it lacks
pop operation and it is impossible to implement it in a type-safe way).
Here is an example:

runStack $ do
  newStackRef (5:: Int)
  newStackRef False
  newStackRef 'x'

according to the definition of the newStackRef it just pokes Storable
representation of the value into the memory block and advances the pointer.
Any information about the type of that value is lost.

To pop a value from such a stack you need to specify correct type and
compiler (or RTS) is not able to warn you if the type is not correct.

To the monad part of the question. From the instance Monad
definition it is easy to see that it almost the same as the State monad (here is how it defined in
Control.Monad.State.Trans.State.Lazy)

instance (Monad m) => Monad (StateT s m) where
    return a = state $ \s -> (a, s)
    m >>= k  = StateT $ \s -> do
        ~(a, s') <- runStateT m s
        runStateT (k a) s'

The only difference is that it operates on top of IO an has fixed type of state. So it is actually StateT (Ptr ()) IO.

It is even not clear what it is for a stack to be an instance of Monad.
E.g. list monad allows nondeterministic computations (in prolog-like
style), Maybe monad allows computations that fail.

To enable computation to access and operate stack it is easier to use existing State monad with some stack implementation as a state. I see no reason to implement your own Stack monad.


Split a list using another list whose items are the split lengths I want to split a list using another list which contains the lengths of each split.

E.g:

>>> print list(split_by_lengths(list('abcdefg'), [2,1]))
... [['a', 'b'], ['c'], ['d', 'e', 'f', 'g']]
>>> print list(split_by_lengths(list('abcdefg'), [2,2]))
... [['a', 'b'], ['c', 'd'], ['e', 'f', 'g']]
>>> print list(split_by_lengths(list('abcdefg'), [2,2,6]))
... [['a', 'b'], ['c', 'd'], ['e', 'f', 'g']]
>>> print list(split_by_lengths(list('abcdefg'), [1,10]))
... [['a'], ['b', 'c', 'd', 'e', 'f', 'g']]
>>> print list(split_by_lengths(list('abcdefg'), [2,2,6,5]))
... [['a', 'b'], ['c', 'd'], ['e', 'f', 'g']]

As you can notice, if the lengths list does not cover all the list I append the remaining elements as an additional sublist. Also, I want to avoid empty lists at the end in the cases that the lengths list produces more elements that are in the list to split.

I already have a function that works as I want:

def take(n, iterable):
    "Return first n items of the iterable as a list"
    return list(islice(iterable, n))

def split_by_lengths(list_, lens):
    li = iter(list_)
    for l in lens:
        elems = take(l,li)
        if not elems:
            break
        yield elems
    else:
        remaining = list(li)
        if remaining:
           yield remaining

But I wonder if there is a more pythonic way to write a function such that one.

Note: I grabbed take(n, iterable) from Itertools Recipes

Note: This question is a repost from a stackoverflow question

This is my first answer that I gave on stackoverflow:

from itertools import islice

def split_by_lengths(seq, num):
    it = iter(seq)
    for n in num:
        out = list(islice(it, n))
        if out:
            yield out
        else:
            return   #StopIteration
    remain = list(it)
    if remain:
        yield remain

Here I am not using a for-else loop because we can end the generator by using a simple return statement. And IMO there's no need to define an extra take function just to slice an iterator.

Second answer:

This one is slightly different from the first one because this won't short-circuit as soon as one of the length exhausts the iterator. But it is more compact compared to my first answer.

def split_by_lengths(seq, num):
    it = iter(seq)
    out =  [x for x in (list(islice(it, n)) for n in num) if x]
    remain = list(it)
    return out if not remain else out + [remain]