Disjoint-set data structure I'm trying to speed up my union-find disjoint set data structure. The idea is that initially n sets of single element sets are made, and put into a vector nodes. Each node has a parent node, and the highest parent of any particular index in the vector is the highest ranking member of set. Two concepts, union by rank and path compression, are used to achieve faster merging and finding times.

There are two querying types: Union of two values (and thus their sets), and checking if 2 members are in the same set.

Nevertheless, when using very large values for n (such as 100,000,000) and and m (such as 1,000,000), the program takes a bit of time to run. Generally around 30 seconds for my machine.

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>

using namespace std;

int n; //number of total elements
int q; //number of queries

struct node
{
    int data;
    node* parent;
    int rank;
    node(int d);
};

node::node(int d)
{
    data = d;
    rank = 0;
    parent = nullptr;
}

node* find(node* root)
{
    if (root != root->parent)
        root->parent = find(root->parent);
    return root->parent;
}

void merge(node* one, node* two)
{
    node* i = find(one);
    node* j = find(two);
    if (i->rank > j->rank)
        j->parent = i;
    else
        i->parent = j;

    if (i->rank == j->rank)
    {
        i->parent = j;
        j->rank++;
    }
}

int sameSet(int i, int j, vector<node*> v)
{
    if (find(v.at(i - 1))->data == find(v.at(j - 1))->data)
        return 1;
    return 0;
}

int main(int argc, char** argv) {

    cin >> n >> q;

    vector<node*> v (n); //vector holding all pointers to sets of nodes

    for (int i = 0; i < n; i++) //make n sets of 1 element each
    {
        node* n = new node(i);
        n->parent = n;
        v[i] = n;
    }
}

Would using a map instead of a vector, for example, be faster? Am I not compressing the path correctly (so that every member of a sets immediate parent is the highest ranking member) or unionizing by rank? As far as I'm aware, both merge and find should take O(log n) if implemented in the most efficient way, making me think this should be faster than it is.

Copying a huge vector by mistake
The reason your program is so slow is because of this line:

int sameSet(int i, int j, vector<node*> v)

This function makes a copy of the vector every time you want to do a simple check on two nodes.  If you simply change that line to this:
int sameSet(int i, int j, vector<node*> &v)

then your program will avoid the copy.  In my testing, the program ran in 1-2 seconds instead of over a minute with a large n.
Also, that function could be simplified from this:

int sameSet(int i, int j, vector<node*> &v)
{
    if (find(v.at(i - 1))->data == find(v.at(j - 1))->data)
        return 1;
    return 0;
}

to this:
bool sameSet(int i, int j, vector<node*> &v)
{
    return find(v[i-1]) == find(v[j-1]);
}


Get Validation result by group There is Three Validation Group A,B and No Group.

How to get validation result of only the specific validation group.

If Group A and No Group is not valid but all of group B is valid, i would like to get result as valid.

I have read the article validation in depth but don't find the straightforward solution.
http://msdn.microsoft.com/en-us/library/aa479045.aspx

Is there any simpler solution than this

    protected bool IsGroupB_Valid()
    {
        var validators = Page.GetValidators("B");

        foreach (IValidator item in validators)
        {
            if(item.IsValid == false)
            return false;
        }
        return true;
    }

Linq will make it look better:

protected bool IsGroupB_Valid()
{
    return Page.GetValidators("B").All(v => v.IsValid);
}

But probably you should look for something really different


Approximate integral in one line of code This is what I came up with:

Version 1:

static double Integrate(Func<double, double> f, double low, double high, double delta)
{
    return Enumerable.Sum(Enumerable.Select(Enumerable.Range((int)(low / delta), (int)((high / delta) - (low / delta))), c => f(c * delta) * delta));
}

If I'm allowed to use a helper-method it becomes slightly shorter:

Version 2:

static double Integrate(Func<double, double> f, double low, double high, double delta)
{
    return Enumerable.Sum(Enumerable.Select(DoubleRange(low, high, delta), c => f(c) * delta));
}

public static IEnumerable<double> DoubleRange(double min, double max, double step)
{
    for (double value = min; value <= max; value += step)
    {
        yield return value;
    }
}

Are there any better ways to do this? It's unfortunate LINQ doesn't have an overload for Enumerable.Range that takes floating point values. Are there ways of doing this with either more efficient or less characters of code?

Version 1.
It gives incorrect results for some delta values.
Example: Integrate(x => x * x, 0, 1, 0.1) gives 0.285 whenever other methods give 0.385.

Version 2.
Since the delta is a scalar that is a constant value for the Enumerable.Sum, it could be moved outside of the Enumerable.Sum.
Then we can replace the c => f(c) * delta with a method group f.
And also we can use Enumerable's extension methods as extension methods:

static double Integrate(Func<double, double> f, double low, double high, double delta)
{
    return delta * DoubleRange(low, high, delta).Sum(f);
}

public static IEnumerable<double> DoubleRange(double min, double max, double step)
{
    for (double value = min; value <= max; value += step)
    {
        yield return value;
    }
}

EDIT
The .Select(f).Sum() was replaced with the .Sum(f) as @mjolka advised.


ASP.net Identity admin reset user password I have an application which uses ASP.net Identity as for its user authentication.

I do not wish for users to reset their own password (for reasons which are not relevant here), so I have developed the following back end system to allow system administrators to reset the users password.

I have the following implementation:

Password Reset View:

@using (Html.BeginForm())
{
    @Html.AntiForgeryToken()

ResetPasswordViewModel

        @Html.ValidationSummary(true, "", new { @class = "text-danger" })
        @Html.HiddenFor(model => model.Id)

            @Html.LabelFor(model => model.NewPassword, htmlAttributes: new { @class = "control-label col-md-2" })

                @Html.EditorFor(model => model.NewPassword, new { htmlAttributes = new { @class = "form-control" } })
                @Html.ValidationMessageFor(model => model.NewPassword, "", new { @class = "text-danger" })

            @Html.LabelFor(model => model.ConfirmPassword, htmlAttributes: new { @class = "control-label col-md-2" })

                @Html.EditorFor(model => model.ConfirmPassword, new { htmlAttributes = new { @class = "form-control" } })
                @Html.ValidationMessageFor(model => model.ConfirmPassword, "", new { @class = "text-danger" })

                <input type="submit" value="Reset Password" class="btn btn-default" />

}

AccountAdmin Controller

    // GET: /AccountAdmin/ResetPassword
    public ActionResult ResetPassword(string id)
    {
        if (id == null)
        {
            return new HttpStatusCodeResult(HttpStatusCode.BadRequest);
        }
        ResetPasswordViewModel model = new ResetPasswordViewModel() { Id = id };
        return View(model);
    }

    //
    // POST: /AccountAdmin/ResetPassword
    [HttpPost]
    [ValidateAntiForgeryToken]
    public ActionResult ResetPassword(ResetPasswordViewModel model)
    {
        if (!ModelState.IsValid)
        {
            return View(model);
        }

        var removePassword = UserManager.RemovePassword(model.Id);
        if (removePassword.Succeeded)
        {
            //Removed Password Success
            var AddPassword = UserManager.AddPassword(model.Id, model.NewPassword);
            if (AddPassword.Succeeded)
            {
                return View("PasswordResetConfirm");
            }
        }

        return new HttpStatusCodeResult(HttpStatusCode.BadRequest);
    }

ResetPassword View Model

public class ResetPasswordViewModel
{
    public string Id { get; set; }

    [Required]
    [StringLength(100, ErrorMessage = "The {0} must be at least {2} characters long.", MinimumLength = 6)]
    [DataType(DataType.Password)]
    [Display(Name = "New password")]
    public string NewPassword { get; set; }

    [DataType(DataType.Password)]
    [Display(Name = "Confirm new password")]
    [Compare("NewPassword", ErrorMessage = "The new password and confirmation password do not match.")]
    public string ConfirmPassword { get; set; }
}

One thing you should keep in mind is that when the Add fails, your user is left without a password as it's already been removed. When will this fail? Usually when your password does not pass the validation.

Of course, seeing how an admin is doing it, there's probably not so much of a problem as they can simply add a different one - as long as the message is clear enough to show there actually is a problem with adding the new password.

The way Microsoft wants you to tackle this is by using a PasswordResetToken.

var code = await _userManager.GeneratePasswordResetTokenAsync(user);
await _userManager.ResetPasswordAsync(user, code, newPassword);

For this you'll have to fiddle around a bit with the token generators that Identity provides.


Creating a user via social auth, merging and modifying appropriately I'm using Sequelise with node.js, and I have a feeling the paradigm I'm using to modify objects is not working well, as my code is getting messy rather quickly.

The function User.createOrMerge is designed to be called after a successful social auth (Google, Facebook etc.), with kwargs being the social auth token to check against the user (e.g. { googleId: "some-oauth-token" }).

I seem to be writing a lot of code to deal with the overhead of using promises. Is there a way to do this more elegantly or is this my life now?

User.findByUsername = function(username, success, error){
  User.findOne({
    where: {
      username: username
    }
  }).then(function(user){
    success && success(user);
  }, function(){
    error && error();
  });
};

User.findByEmail = function(email, success, error){
  User.findOne({
    where: {
      email: email
    }
  }).then(function(user){
    success && success(user);
  }, function(){
    error && error()
  });
}

User.createOrMerge = function(username, email, kwargs, success, failure){
  // if user with kwargs exists, return that
  User.findOne({
    where: kwargs
  }).then(function (user) {
      if(user){
        success && success(user);
      }else{
        // if email address exists, merge user
        User.findByEmail(email, function(user){
          if(user){
            user.updateAttributes(kwargs).then(function(){
              success && success(user);
            });
          }else{
            // if username exists, modify this one
            User.findByUsername(username, function(user){
              if(user){
                username += UUID();
              }
              // finally create a new user
              kwargs['username'] = username;
              kwargs['email'] = email;
              User.create(kwargs).then(function(user){
                success && success(user);
              }, function(){
                failure && failure();
              });
            }, function(){
              failure && failure();
            });
          }
        }, function(){
          failure && failure();
        });
      }
  }, function(){
    failure && failure();
  });
}

You can organize better your asynchronous code.

Turn something like this:

Promisse.then(function() {
    Promisse.then(function() {
        promisse.then(function()) {
        }, function() { error })
    }, function() { error })
}, function() { error })

Into something like:

Promisse.then(function() {
}).then(function() {
}).then(function(){
}).catch(function () { failure && failure(); })

Another tip would be creating a function User.create and other called User.merge (this will make debugging easier; read about the Single-responsiblity principle to know more in depth why).


DDD modeling for a User Voice-like system I've taken on the challenge of modeling a simple User Voice-like system. High-level description:

It's a portal for some SaaS users;
They come and leave feature requests, suggestions, etc.;
They should be able to vote/unvote for any suggestions;
They can leave as many comments as they like on suggestions;
Comments may be removed by the owner, but may not be edited.

I've modeled the domain as follows, using a DDD approach. Please advise about mistakes, warnings, improvements, etc.

I've also applied the advices from these posts:

Don't create aggregate roots
Creating new aggregates in DDD
Link to an aggregate: reference or Id?

public abstract class Entity
{
    public Guid Id { get; protected set; } = Guid.NewGuid();
}

public class User : Entity // Aggregate Root
{
    public string Key => $"{Email}:{MarketplaceUrl}";

    public string Name { get; }

    public string Email { get; }

    public string MarketplaceName { get; }

    public Uri MarketplaceUrl { get; }

    internal User(string name, string email, string marketplaceName, Uri marketplaceUrl)
    {
        Name = name;
        Email = email;
        MarketplaceName = marketplaceName;
        MarketplaceUrl = marketplaceUrl;
    }

    public Suggestion MakeSuggestion(string text)
    {
        return new Suggestion(this, text);
    }
}

public class Suggestion : Entity // Aggregate Root
{
    public string Text { get; /* a suggestion cannot be altered */ }

    public User ByUser { get; }

    public DateTime SuggestedAt { get; }

    public ICollection<Comment> Comments { get; } = new List<Comment>();

    public ICollection<Vote> Votes { get; } = new List<Vote>();

    internal Suggestion(User byUser, string text)
    {
        ByUser = byUser;
        Text = text;
        SuggestedAt = DateTime.UtcNow;
    }

    public Comment AddComment(User byUser, string text)
    {
        var comment = new Comment(byUser, text);
        Comments.Add(comment);
        return comment;
    }

    public void RemoveComment(Comment comment, User userRemovingComment)
    {
        Comments.Remove(comment);
    }

    public void Unvote(User byUser)
    {
        var vote = Votes.SingleOrDefault(v => v.ByUser == byUser));

        if (vote != null)
            Votes.Remove(vote);
    }

    public Vote Vote(User byUser)
    {
        if (Votes.Any(v => v.ByUser == byUser))
            throw new CannotVoteTwiceOnSameSuggestionException();

        var vote = new Vote(byUser);
        Votes.Add(vote);
        return vote;
    }
}

public class Comment : Entity
{
    public string Text { get; /* a comment cannot be changed */ }

    public User ByUser { get; }

    public DateTime CommentedAt { get; }

    internal Comment(User byUser, string text)
    {
        ByUser = byUser;
        Text = text;
        CommentedAt = DateTime.UtcNow;
    }
}

public class Vote : Entity
{
    public User ByUser { get; }

    public DateTime VotedAt { get; }

    internal Vote(User byUser)
    {
        ByUser = byUser;
        VotedAt = DateTime.UtcNow;
    }
}

public interface IUserVoiceStore
{
    Task AddUserAsync(User user);

    Task AddSuggestionAsync(Suggestion suggestion);

    Task<Suggestion> GetSuggestionAsync(Guid id);

    Task<User> GetUserAsync(Guid id);

    // For when comments and votes are added/removed to/from a suggestion.
    Task UpdateSuggestionAsync(Suggestion suggestion);
}

public class UserVoiceService
{
    private readonly IUserVoiceStore store;

    public UserVoiceService(IUserVoiceStore store)
    {
        this.store = store;
    }

    public async Task<User> RegisterUserAsync(string name, string email, string marketplaceName, Uri marketplaceUrl)
    {
        var user = new User(name, email, marketplaceName, marketplaceUrl);
        await store.AddUserAsync(user);
        return user;
    }
}

public class CannotVoteTwiceOnSameSuggestionException : Exception { }

public class CannotRemoveCommentFromAnotherUserExcetion : Exception { }

The design looks solid, a few thoughts though:

I would split IUserVoiceStore into more granular UserRepository and SuggestionRepository. Also, UpdateSuggestionAsync() seems to indicate you can only update a suggestion and nothing else at a time, which can be limiting. It also IMO goes out of a repository's jurisdiction to flush a specific object to persistent storage. Using some kind of separate unit of work class where you can put multiple objects to be updated as part of a business transaction might be a better idea.
Not always feasible, but maybe change the type of link between Suggestion and User from a full reference to just an ID to avoid the temptation of manipulating 2 aggregate roots at the same time. (I don't agree with the article you linked to in that regard)
Keep an eye on suggestions with a large number of comments - depending on concurrent access, they can clog up your system and cause locking problems, especially if comments become more sophisticated, with images and so on.


Project Euler problem 3: Largest prime factor in JavaScript I have created a soloution for Project Euler: Problem 3 - Largest Prime Factor in JavaScript:

function isPrime(value) {
    for (var i = 2; i < value; i++) {
        if (value % i == 0) {
            return false;
        }
    }
    return true;
}

function findFactors(value) {
    var array = [];
    for (var i = 2; i < value; i++) {
        if (value % i == 0) {
            array.push(i);
        }
    }
    return array;
}

function findPrimeFactors(value) {
    var array = [];
    for (var i = 0; i < findFactors(value).length; i++) {
        if (isPrime(findFactors(value)[i])) {
            array.push(findFactors(value)[i]);
        }
    }
    return array;
}

document.write("Answer: " + Math.max(...findPrimeFactors(600851475143)));

I would like to know if my code even works, as it is so slow, that even when I left it for 20 minutes it still didn't finish, and if so, I would like to know a quick way of doing it (If my code would actually give it) so I can mark it as completed.

Your code looks pretty, and it is a very literal naïve implementation of the requirements. Unfortunately, the algorithm you are using is extremely inefficient.

Factoring large numbers is hard work! The difficulty of factoring large numbers is, in fact, what keeps cryptographic algorithms like RSA safe.  In your findFactors() function, just counting up to 600 billion will take a while; having to check for divisibility within the loop is even slower!

For a quick algorithm that will give the answer in about one second, see this answer.


Returning a viewmodel In my ASP.NET MVC code, I like to use controller service classes for my controllers. These service classes contain methods for retrieving viewmodel objects.

Here is an example controller snippet:

public SubscriptionsController(ISubscriptionsControllerService service)
{
    _service = service;
}

public ActionResult Index(Guid id)
{
    return View("Subscriptions", _service.GetSubscriptionsViewModelOnGet(id));
}

[HttpPost]
public ActionResult Index(SubscriptionsViewModel viewModel)
{
    _service.SaveSubscriptions(viewModel);

    return View("Subscriptions", _service.GetSubscriptionsViewModelOnPost(viewModel));
}

As you can see, I have a method for retrieving the subscriptions viewmodel on a GET request, as well as the equivalent for a POST request.

The POST method takes in an existing viewmodel object and updates any relevant data e.g. a list of subscription items, that need to be refreshed before passing back to the view.

My question is whether the naming of the methods (GetSubscriptionsViewModelOnGet() and GetSubscriptionsViewModelOnPost()) makes sense. They seem OK to me, but I'm interested in other people's views.

Why not name them both the same? The difference is the type of parameter you're passing. This leaves you free to do some method overloading:

public SubscriptionsViewModel GetSubscriptionsViewModel(Guid id)
{
    //GET Logic here...
}

public SubscriptionsViewModel GetSubscriptionsViewModel(SubscriptionsViewModel viewModel)
{
    //POST Logic here...
}

Why call them the same? They both do the same: return a SubscriptionsViewModel.


How to use smart pointers with SDL2 (SDL_RWops)? I want to write read savefile function with smart pointers and SDL2. I have little expirience with smart pointers and just want to ask is my code good, correct and no memory leaks.
this is my code:
std::shared_ptr<SDL_RWops> saveFile;

--
int GameEngine::ReadSave() {

        int Highlevel;

        //Open file for reading in binary
        saveFile = std::shared_ptr<SDL_RWops>(SDL_RWFromFile( "data/save.txt", "r" ), SDL_RWclose);

        //File does not exist
        if( saveFile.get()  == NULL ){
                printf( "Warning: Unable to open file! SDL Error: %s\n", SDL_GetError() );

                Highlevel = 0;

                //Create file for writing
                saveFile = std::shared_ptr<SDL_RWops>(SDL_RWFromFile( "data/save.txt", "w+" ), SDL_RWclose);

                if( saveFile.get() != NULL ){
                        printf( "New save file created!\n" );

                        //Initialize data
                        SDL_RWwrite( saveFile.get(), &Highlevel, sizeof(int), 1 );
                }
                else {
                        printf( "Error: Unable to create savefile! SDL Error: %s\n", SDL_GetError() );
                }
        }
        else{
                //Load data
                printf( "Reading save file...!\n" );

                SDL_RWread( saveFile.get(), &Highlevel, sizeof(int), 1 );
        }

        return Highlevel;
}

Your idea to wrap the result of SDL_RWFromFile in a smart pointer is a good idea. I recommend a few improvements:

Factor out the opening-and-wrapping operations into a named function. For example:
auto OpenFile(const char *fname, const char *mode) {
    return std::shared_ptr<SDL_RWops>(SDL_RWFromFile(fname, mode), SDL_RWclose);
}

if( saveFile.get()  == NULL ){

Your whitespace is all messed up here; and also, you should generally treat smart pointers the same way you'd treat regular pointers. Avoid using .get() and .reset() and so on, unless you have a specific reason you need to emphasize the "object-ness" of the smart pointer. Keep it simple by writing:
saveFile = OpenFile("data/save.txt", "r");
if (saveFile == nullptr) {
    printf("Warning: Unable to open savefile! SDL Error: %s\n", SDL_GetError());
    Highlevel = 0;
    saveFile = OpenFile("data/save.txt", "w+");
    if (saveFile == nullptr) {
        printf("Error: Unable to create savefile! SDL Error: %s\n", SDL_GetError());
    } else {
        printf("New save file created!\n");
        SDL_RWwrite(saveFile.get(), &Highlevel, sizeof(Highlevel), 1);
    }
} else {
    printf("Reading save file...!\n");
    SDL_RWread(saveFile.get(), &Highlevel, sizeof(Highlevel), 1);
}

I notice that you are not checking the return value of SDL_RWread for errors. That's not great.
Have you considered throwing an exception on failure, instead of using printf to report directly to the user? This would certainly streamline your code:
if (auto f = OpenFile("data/save.txt", "r")) {
    printf("Reading save file...\n");
    if (SDL_RWread(f.get(), &Highlevel, sizeof(Highlevel), 1) != 1) {
        throw std::runtime_error(std::string("Save file format error: ") + SDL_GetError());
    }
} else if (auto f = OpenFile("data/save.txt", "w+")) {
    printf("Writing new save file...\n");
    Highlevel = 0;
    SDL_RWwrite(f.get(), &Highlevel, sizeof(Highlevel), 1);
} else {
    throw std::runtime_error(std::string("Unable to create save file: ") + SDL_GetError());
}

Finally, shared_ptr is overkill here because you never have more than one "owner" of the open file. You should certainly rewrite OpenFile to return a unique_ptr — a type which you can still implicitly convert to shared_ptr if you do ever need shared ownership of the file. See "OpenSSL client and server from scratch, part 1"; it's basically this:
struct RWCloser { void operator()(SDL_RWops *p) const { SDL_RWclose(p); } };

using UniqueRWops = std::unique_ptr<SDL_RWops, RWCloser>;

UniqueRWops OpenFile(const char *fname, const char *mode) {
    return UniqueRWops(SDL_RWFromFile(fname, mode));
}


Smoothing Function in Python def smoothen(heightProfile, travelTime):
    newHeightProfile = []

    # Berechne einen gleitenden Mittelwert
    smoothingInterval = 30 * travelTime

    for i in xrange(smoothingInterval):
        heightProfile.append(heightProfile[-1])

    for i in xrange(len(heightProfile) - smoothingInterval):
        mean = 0
        for j in xrange(i, i + smoothingInterval):
            mean += heightProfile[j]
        newHeightProfile.append(mean/smoothingInterval)

    return newHeightProfile

Input:

heightProfile: an array of the size travelTime * 60
travelTime: an integer

travelTime can be, for example, 500. heightProfile contains an array of random numbers of the size travelTime * 60. The height profile should describe the height of a random landscape. The function is used to smoothen the values.

However, this code is very slow and expensive, even when using xrange:

Tests for travel time: 500
CPython: 38.3s
Pypy: 0.98s

Questions:

Is there a construct in this code which is very inefficient?
Would this be faster if I were to implement this function in C?

Any other recommendations for improvement are welcome.

Currently you are calculating the mean each time in the loop, so that's slice + sum for each of the len(heightProfile) - smoothingInterval iterations. We can remove this by calculating the mean of first smoothingInterval items and then inside of the loop simply subtract current ith item from the sum of the previous mean and add (i + smoothingInterval)th item to the sum and calculate the mean for the current window. With this approach we can do this in almost linear time.

Also as you're using Python 2 don't forget to add this line at the top of the file, otherwise normal division will result in integer division.

from __future__ import division

You can replace:

for i in range(smoothingInterval):
        heightProfile.append(heightProfile[-1])

with:

heightProfile.extend([heightProfile[-1]]*smoothingInterval)

If smoothingInterval is very huge then consider passing a generator expression to list.extend, but in most cases [heightProfile[-1]]*smoothingInterval is as fast as you can get:

last_val = heightProfile[-1]
heightProfile.extend(last_val for _ in xrange(smoothingInterval))

Full Code:

from __future__ import division

def smoothen_fast(heightProfile, travelTime):

    smoothingInterval = 30 * travelTime

    heightProfile.extend([heightProfile[-1]]*smoothingInterval)
    # Get the mean of first `smoothingInterval` items
    first_mean = sum(heightProfile[:smoothingInterval]) / smoothingInterval
    newHeightProfile = [first_mean]

    for i in xrange(len(heightProfile)-smoothingInterval-1):
        prev = heightProfile[i]  # the item to be subtracted from the sum
        new = heightProfile[i+smoothingInterval] # item to be added
        # Calculate the sum of previous items by multiplying
        # last mean with smoothingInterval
        prev_sum = newHeightProfile[-1] * smoothingInterval
        new_sum = prev_sum - prev + new
        mean = new_sum / smoothingInterval
        newHeightProfile.append(mean)

    return newHeightProfile

Timing comparisons:

>>> from random import sample
>>> heightProfile = sample(xrange(1, 10**5), 10**4)
>>> travelTime = 1000
>>> %timeit smoothen(heightProfile[:], travelTime)
1 loops, best of 3: 11.3 s per loop
>>> %timeit smoothen_fast(heightProfile[:], travelTime)
100 loops, best of 3: 2.69 ms per loop

Note that in my function call I am passing a slice of the list because we are modifying the passed list object using its .extend method, which is usually a not a good idea unless the caller expects such modifications.


ServiceBus QueueClient and TopicClient object resue I'm writing an Azure function using Visual Studio (multi-layers project), where I'm managing all Azure ServiceBus related code in one class.

(follow-up)

public class MessageBroker : IMessageBroker, IDisposable
{
    private readonly IAppConfiguration appConfiguration;
    private TopicClient topicClient;
    private QueueClient queueClient;

    public MessageBroker(IAppConfiguration appConfiguration)
    {
        this.appConfiguration = appConfiguration;
    }

    public async Task SendMessageToQueueAsync(string queueName, string message)
    {
        this.queueClient = QueueClient.CreateFromConnectionString(appConfiguration.BrokerConnectionString, queueName);
        BrokeredMessage brokeredMessage = new BrokeredMessage(message);
        await queueClient.SendAsync(brokeredMessage);
    }

    public async Task SendMessageToTopicAsync(string topicName, string message)
    {
        this.topicClient = TopicClient.CreateFromConnectionString(appConfiguration.BrokerConnectionString, topicName);
        BrokeredMessage brokeredMessage = new BrokeredMessage(message);
        await topicClient.SendAsync(brokeredMessage);
    }

    public void Dispose()
    {
        this.queueClient.Close();
        this.topicClient.Close();
    }
}

I use the [Inject] attribute to use DI in the Azure function. Whenever I need to send any message into a queue or topic, I inject IMessageBroker and call thr SendMessageToQueueAsync method. I see a Microsoft recommendation here to reuse QueueClient and TopicClient.

IMessageBroker is Singleton in my DI configuration.

Will the QueueClient.CreateFromConnectionString method create a new object every time or reuse a connection internally based on the same ConnectionString or queuename?

Is there anything I can do better on this code?

Having topicClient and queueClient as class fields is unnecessary here, and potentially leads to exception scenarios.

For example, if you were to create a new MessageBroker and immediately call Dispose() without first calling both the other methods then a NullReferenceException will be thrown as topicClient and queueClient are only defined within these methods.

An alternative could be to make use of the using syntax to instantiate a client and dispose of it when done. e.g.

using(var topicClient = TopicClient.CreateFromConnectionString(appConfiguration.BrokerConnectionString, topicName))
{
    BrokeredMessage brokeredMessage = new BrokeredMessage(message);
    await topicClient.SendAsync(brokeredMessage);
}

Using this approach would allow you to remove the IDisposable implementation.

If you want to be able to re-use the same topicClient and queueClient then you could have a MessageBroker for a specific queueName and/or topicName, and define the clients from the constructor.
(Creating new MessageBrokers as necessary for new queue and topic names.)

public class MessageBroker : IMessageBroker, IDisposable
{
    private readonly TopicClient topicClient;
    private readonly QueueClient queueClient;

    public MessageBroker(IAppConfiguration appConfiguration, string queueName, string topicName)
    {
        this.queueClient = QueueClient.CreateFromConnectionString(appConfiguration.BrokerConnectionString, queueName);
        this.topicClient = TopicClient.CreateFromConnectionString(appConfiguration.BrokerConnectionString, topicName);
    }

    public async Task SendMessageToQueueAsync(string message)
    {
        BrokeredMessage brokeredMessage = new BrokeredMessage(message);
        await queueClient.SendAsync(brokeredMessage);
    }

    public async Task SendMessageToTopicAsync(string message)
    {
        BrokeredMessage brokeredMessage = new BrokeredMessage(message);
        await topicClient.SendAsync(brokeredMessage);
    }

    public void Dispose()
    {
        this.queueClient.Close();
        this.topicClient.Close();
    }
}

If you have need of only one MessageBroker (i.e. one topicName and queueName) then this will be sufficient, and an instance of this can be registered within your DI.

Otherwise, you will need some sort of MessageBrokerFactory which can be used to create a MessageBroker for a given queue/topic name, that can then be re-used.

public MessageBrokerFactory {
    private readonly IAppConfiguration appConfiguration;

    public MessageBrokerFactory(IAppConfiguration appConfiguration)
    {
        this.appConfiguration = appConfiguration;
    }

    public IMessageBroker Create(string queueName, string topicName)
    {
        return new MessageBroker(
            this.appConfiguration,
            queueName,
            topicName);
    }
}


Array-based deque in Java Are the conditions which I have included for insertion and deletion from front and rear sufficient and necessary? Have I missed some condition check? Or have I included some redundant condition?

import java.io.*;
class Dequeue
{
int arr[];
int lim;
int front;
int rear;
public Dequeue(int l)
{
    lim=l;
    front=rear=0;
    arr=new int[(l+1)];
}
void addrear(int val)
{
   if(front==0 && rear ==0)
   {
    front=1;
    rear=1;
    arr[1]=val;
   }
   else if(rear==lim)
   {
   System.out.println("Overflow");
   }
   else
   {
   arr[++rear]=val;
   }
}
void addfront(int val)
{
    if(front==0 && rear ==0)
    {
    front=1;
    rear=1;
    arr[1]=val;
    }
    else if(front==1)
    {
        System.out.println("Overflow");
    }
    else
    {
    arr[--front]=val;
    }
}
void poprear()
{
    if(front==rear)
    {
        System.out.println(arr[front]);
        front=0;
        rear=0;

    }
    else if(front==0 && rear==0)
    {
       System.out.println("Underflow");
    }
    else
    {
        System.out.println(arr[rear]);
        rear--;

    }

}
void popfront()
{
    if(front==rear)
    {
        System.out.println(arr[front]);
        front=0;
        rear=0;

    }
    else if(front==0 && rear==0)
    {
       System.out.println("Underflow");
    }
    else
    {
        System.out.println(arr[front]);
        front++;

         }
      }
void display()
{
if(front!=0 || rear!=0)
{
    for(int i=front;i<=rear;i++)
   {
        System.out.print(arr[i]);
   }
   System.out.println();
}

else
System.out.println("Empty");
}
public static void main(String args[])throws IOException
{
int flag=0;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter size of array");
Dequeue obj=new Dequeue(Integer.parseInt(br.readLine()));
while(flag==0)
{
System.out.println("1 for addrear");
System.out.println("2 for addfront");
System.out.println("3 for poprear");
System.out.println("4 for popfront");
System.out.println("5 for exit");
int ch=Integer.parseInt(br.readLine());
switch(ch)
{
    case 1:
           System.out.println("Enter element");
           obj.addrear(Integer.parseInt(br.readLine()));
           obj.display();
           break;
    case 2:System.out.println("Enter element");
           obj.addfront(Integer.parseInt(br.readLine()));
           obj.display();
           break;
    case 3:obj.poprear();
           obj.display();
           break;
    case 4:obj.popfront();
           obj.display();
           break;
    case 5:flag=1;
           break;

}
}

}
}

Formatting:

First of all, indent your code properly; each level of identation should include four spaces. So instead of

class Dequeue
{
int arr[];
...

Rewrite it as

class Dequeue
{
    int arr[];
    ...

What comes to braces, according to Java coding conventions, you should have the opening curly brace on the same line with the token it belongs to; also, you should have one space between the relevant token and the opening brace:

class Dequeue {
    int arr[];
    ...

Naming:

Dequeue is not what you think it is called; it's Deque (double-ended queue). And in a FIFO queue data structure, the operation popping the first element is actually (and conventionally) called dequeue; don't mix the terminology.

What comes to method names, please stick to camel-case. For example,

addRear instead of addrear

Visibility:

Declare your fields (arr, lim, front, rear) private:

class Dequeue {
    private final int arr[];
    private int lim;
    ...

You can make arr final, since you do not reassign to it.

Also, you might consider declaring your class both public and final:

public final class Deque {
    private final int[] arr;
    ...

lim:

You don't need this field, as you can always rely on arr.length.

Algorithm:

Consider removing rear and replace it by a field, say, size. That way you always know the size of your deque, and you don't have to allocate additional array component in order handle the logic gracefully.

Proposal:

After working a bit on your code, I got this implementation. Hope that helps.

import java.util.NoSuchElementException;
import java.util.Random;

public class Deque {

    private final int arr[];
    private int head;
    private int size;

    public Deque(int capacity) {
        arr = new int[capacity];
    }

    public void addLast(int element) {
        checkCapacity();
        arr[(head + size++) % arr.length] = element;
    }

    public void addFirst(int element) {
        checkCapacity();

        if (head == 0) {
            arr[(head = arr.length - 1)] = element;
        } else {
            arr[(--head) % arr.length] = element;
        }

        size++;
    }

    public int removeFirst() {
        checkNotEmpty();

        int ret = arr[head];
        head = (head + 1) % arr.length;
        size--;
        return ret;
    }

    public int removeLast() {
        checkNotEmpty();

        int ret = arr[(head + size - 1) % arr.length];
        size--;
        return ret;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");

        for (int i = 0; i < size; ++i) {
            sb.append(arr[(head + i) % arr.length]);

            if (i < size - 1) {
                sb.append(", ");
            }
        }

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

    public int size() {
        return size;
    }

    private void checkCapacity() {
        if (arr.length == size) {
            throw new IllegalStateException("No more space is available.");
        }
    }

    private void checkNotEmpty() {
        if (size == 0) {
            throw new NoSuchElementException("Trying to pop an empty deque.");
        }
    }

    public static void main(String args[]) {
        Deque deque = new Deque(10);
        Random random = new Random();

        for (int op = 0; op < 30; ++op) {
            if (deque.size() == 0) {
                int num = random.nextInt(100);
                System.out.print("Adding " + num + " to front: ");
                deque.addLast(num);
                System.out.println(deque);
            } else {
                boolean add = random.nextBoolean();

                if (add) {
                    boolean front = random.nextBoolean();
                    int num = random.nextInt(100);

                    if (front) {
                        System.out.print("Adding " + num + " to front: ");
                        deque.addFirst(num);
                        System.out.println(deque);
                    } else {
                        System.out.print("Adding " + num + " to back:  ");
                        deque.addLast(num);
                        System.out.println(deque);
                    }
                } else {
                    boolean front = random.nextBoolean();

                    if (front) {
                        System.out.print("Removing from front: ");
                        deque.removeFirst();
                        System.out.println(deque);
                    } else {
                        System.out.print("Removing from back:  ");
                        deque.removeLast();
                        System.out.println(deque);
                    }
                }
            }
        }
    }
}


Checking whether a bullet has hit a Space Invader I just (almost) finished a Space-Invaders game in Javascript.
I have a few bugs to clear out of the way but meanwhile I wanted to ask how I can improve the method I use to test if one of my 'Bullets' has killed an 'Invader'.

I have a feeling I used too many loops and there must be a more elegant way.

The whole program may be found here.

The exact function is:

function testForInvaders(bullet){
    var score = document.getElementById('score');
    var bulletX = bullet.getLocation()[0],
        bulletY = bullet.getLocation()[1];

    for(var i = 0; i < Invaders.length; i++){
        var invaderX = Invaders[i].getLocation()[0],
            invaderY = Invaders[i].getLocation()[1];

        if(Invaders[i].isVisible()){
            // if bullet is in the invaders radius...
            if(bulletX >= (invaderX - 15) && bulletX <= (invaderX + 15) &&
            bulletY >= (invaderY - 15) && bulletY <= (invaderY + 15)){
                Invaders[i].removeVisibility();
                game.incrementScore();
                game.updateScore(score);
                return false;
            }
        }
    }
    return true;
}

This function is called from within my 'loop' function which is the interval the draws all elements to the canvas.
The logic is as follows:

move all invaders (loop through them)
move all bullets (loop through them)
for each bullet I call the above function and test against all Invaders.
then I loop through everything once more to draw it to the canvas.

How can I improve this?
General feedback would be welcome as well :)

Welcome to CodeReview!

I'm not really working with javascript, but I noticed some things I'd like to mention:

You can safely move the first two initialisations of invaderX an invaderY one condition deeper into the Invaders[i].isVisible() block - if the invader isn't visible there is no need to know the invaders position.
Same with the score variable. Initialise the variable immediately before using it (game.updateScore(score)).
Don't use magic numbers like 15 for the radius of an invader. Use a static class constant or instance property of an Invader instance. This would even allow you to create invaders of different size.
I would also put the isInInvadersRadius condition into a separate function. This function could look something like this:

function areInRadius(location1, location2, radius) {
    var x1 = location1[0],
        y1 = location1[1],
        x2 = location2[0],
        y2 = location2[1];

    return x1 >= x2 - radius && x1 <= x2 + radius &&
           y1 >= y2 - radius && y1 <= y2 + radius;
}

Using this function you wouldn't even need the temporaries bulletX and bulletY, just calling areInRadius(bullet.location(), Invaders[i].location(), Invader[i].radius).

Your function would look like this:

function testForInvaders(bullet) {
    for(var i = 0; i < Invaders.length; i++) {
        if(Invaders[i].isVisible() && areInRadius(bullet.location(), Invaders[i].location, Invaders[i].radius) {
            Invaders[i].removeVisibility();

            var score = document.getElementById('score');
            game.incrementScore();
            game.updateScore(score);
            return false;
        }
    }

    return true;
}

testForInvaders gets called quite often as you already mentioned and I'm honestly not sure if the overhead of the function call above will screw with the performance. You should consider to measure the impact.

Since I'm not into javascript I can't say anything special about hit detection (maybe there is a builtin or an standard way of doing so), but I'm sure other users will remind you of those (if existent).

Nice piece of code you delivered here for your first review. Keep it up!


Method that remove duplicates from a list of words in Java Today, I took a coding challenge with this question:

Given a List of Strings, write a method removeDuplicates that removes duplicate words from the List and returns an ArrayList of all the unique words. The returned ArrayList should be lexically alphabetically.

One thing that I learned while doing this problem is a TreeSet. From my understanding it works like a set but adds elements in order.

From the code, I concluded that my time complexity would be O(n).
Can anyone offer suggestions or corrections?

public static ArrayList<String> removeDuplicates(List<String> input) {

    ArrayList<String> array = new ArrayList<String>();
    Set<String> noDups = new TreeSet<String>();

    if(input.isEmpty()){
        return array;
    }

    if(input.size() == 1){
        array.add(input.get(0));
        return array;
    }

    for(int i = 0; i < input.size(); i++){
            noDups.add(input.get(i));
    }

    return new ArrayList<String>(noDups);
}

General advice

Prefer to declare variables by interfaces and not implementations. You don't need to specify that you use and return an ArrayList, specifying List is enough. So the first lines would be:

public static List<String> removeDuplicates(List<String> input) {
    List<String> array = new ArrayList<String>();
    Set<String> noDups = new TreeSet<String>();

Complexity

Javadoc for TreeSet says:

  This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Since you are performing a log(n) operation \$n\$ times, this becomes n * log(n).

Unnecessary edge cases

This is your main code:

for(int i = 0; i < input.size(); i++){
        noDups.add(input.get(i));
}

Now let's take a look at your special cases:

if(input.isEmpty()){
    return array;
}

We can see that this would be handled correctly by your main code.

Your other special case:

if(input.size() == 1){
    array.add(input.get(0));
    return array;
}

This too would be handled correctly by your main code.

Shortened code

With the above advice this would shorten your code to:

public static List<String> removeDuplicates(List<String> input) {
    List<String> array = new ArrayList<String>();
    Set<String> noDups = new TreeSet<String>();
    for(int i = 0; i < input.size(); i++){
        noDups.add(input.get(i));
    }
    return new ArrayList<String>(noDups);
}

There is however one more thing we can do, and that is to use a specific constructor of TreeSet:

public static List<String> removeDuplicates(List<String> input) {
    return new ArrayList<String>(new TreeSet<String>(input));
}


Project Euler #4 - Largest Palindrome Project - Python I solved the HackerRank version of the Largest palindrome problem (similar to Project Euler 4) in Python:

  Find the largest palindrome made from the product of two 3-digit numbers which is less than N, where 101101 < N < 1000000.

How can I make this more efficient? My solution keeps timing out.

Here is the Code:

# Find the Largest palindrome made from two three digit numbers which are less than N

# Get the input and store it in an array
def get_input():
    limit = int(input())
    limits = []

    for _ in range(limit):
        limits.append(int(input().strip()))

    return limits

# Check if palindrome or not
def is_palindrome(num):
    if str(num) == str(num)[::-1]:
        return True
    else:
        return False

# Find the Largest Palindrome
def largest_palindrome(num):
    largest = 0

    for i in range(2,999+1):
        for j in range(i+1 , 999+1):
            prod = i * j
            if is_palindrome(prod) and prod > largest and prod < num:
                largest = prod

    return largest

# Get the Limits
limits = get_input()

for limit in limits:
    print(largest_palindrome(int(limit)))

Look at my previous answer

palindrome is divisible by 11
i and j can be only odd
reverse loops 999 -> 1 and 999 -> i - 1 - first found palindrome less than n is our palindrome

Simplify code

str(num) is expensive, do it once

def is_palindrome(num):
    snum = str(num)
    return if snum == snum[::-1]

Instead of prod > largest and prod < num You can write num > prod > largest

Use list comprehension

limits = [int(input().strip()) for _ in range(limit)]


Simple string hashing algorithm implementation I thought of a simple way to hash a string. By taking the ASCII decimal value of each character, multiplying it by 10, and adding all of the values computed together for each character in a string. Is there a name for this algorithm? I highly doubt I was the first one to think of this.

Compiled with gcc -Wall -Wextra -Werror -std=c99 string.c -o string

#include <stdio.h>
#include <stddef.h>

size_t stringLength(const char* source)
{
    if(source == NULL) { return 0; }

    size_t length = 0;
    while(*source != '\0') {
        length++;
        source++;
    }
    return length;
}

static size_t getHash(const char* source)
{
    size_t length = stringLength(source);
    size_t hash = 0;
    for(size_t i = 0; i < length; i++) {
        char c = source[i];
        int a = c - '0';
        hash = (hash * 10) + a;
    }

    return hash;
}

static const char *const testCases[] = {
    "this",
    "is",
    "a",
    "test",
    "but",
    "i",
    "should",
    "use",
    "real",
    "dictonary"
};

#define TABLE_SIZE (16)

int main()
{
    size_t name = getHash("Ryan McCullagh");
    printf("%zu\n", name);

    for(size_t i = 0; i < (sizeof(testCases) / sizeof(testCases[0])); i++) {
        const char* source = testCases[i];
        size_t hash = getHash(source);
        printf("%s <==> %zu\n", source, (hash % TABLE_SIZE));

    }

    return 0;
}

Don't check for NULL pointer argument. The function should expect a valid null-terminated string, it's responsibility of the caller to ensure correct argument.
You don't need to know the string length. Check for null-terminator right in the hash loop.
It's possible to write it shorter and cleaner.

static size_t getHash(const char* cp)
{
    size_t hash = 0;
    while (*cp)
        hash = (hash * 10) + *cp++ - '0';
    return hash;
}

It's not quite clear what do you mean by "ASCII decimal value". Are you referring to this expression in your code: c - '0'? Well, suppose at some moment c == 'Z', so this expression amounts to 'Z' - '0'. If we substitute ASCII codes for these characters, then we get 90 - 48, this is equal to 42 which is ASCII code for '*' character. So you have transformed 'Z' into '*'. Is this somehow supposed to improve the quality of your hash function? I'm in doubt.
Are you aware that for the same expression c - '0' for a number of possible c values (e.g. ' ', '!', and anything with ASCII value less than 48) you will get a negative result and when you add it to the hash it will be sign-extended and converted to a huge unsigned value, something like 0xffffffffffffffxx?
If you are looking for a short and simple hash function then perhaps either of these might work for you.

/* D. J. Bernstein hash function */
static size_t djb_hash(const char* cp)
{
    size_t hash = 5381;
    while (*cp)
        hash = 33 * hash ^ (unsigned char) *cp++;
    return hash;
}

/* Fowler/Noll/Vo (FNV) hash function, variant 1a */
static size_t fnv1a_hash(const char* cp)
{
    size_t hash = 0x811c9dc5;
    while (*cp) {
        hash ^= (unsigned char) *cp++;
        hash *= 0x01000193;
    }
    return hash;
}


Remove unwanted characters from specified column in all Worksheets I need to remove some unwanted characters from a given column in all Worksheets from my Workbook. The code below works perfectly, but I'd like to know if there is a better/cleaner/faster way of doing this.

What exactly am I doing?
I am storing all unwanted/forbidden characters in an Array, after that I'm walking through all worksheets and replacing those characters with ""(empty) in each cell in column "J". In this case it will Always be in column J, but for maintainability (in case the template changes in future), I'm declaring it as a constant.

Why do I need to do this?
The data in this Workbook is uploaded to ALM, which does not allow any of those characters in the "Test Subject" field, hence I'm removing them. I chose this approach because I think it is easier, but if you have a better way of doing this (e.g. preventing the user from typing them in the first place, or any other approach that doesn't even require coding) it will be very welcome.

Code:

Sub replaceAll()

    Const FIRST_ROW As Integer = 2, TEST_COLUMN As String = "J"
    Dim arrForbidden() As String: arrForbidden = Split("\,/,:,%,',*,?,<,>,|,"",.", ",")

    Dim ws As Worksheet
    Dim lastRow As Long
    Dim rngCells As Range
    Dim cell, character

    For Each ws In ThisWorkbook.Worksheets

        lastRow = ws.Cells(ws.Rows.Count, TEST_COLUMN).End(xlUp).Row
        Set rngCells = ws.Range(TEST_COLUMN & FIRST_ROW).Resize(lastRow - FIRST_ROW + 1, 1)

        For Each cell In rngCells
            For Each character In arrForbidden
                cell.Value = Replace(cell.Value, character, "")
            Next
        Next
    Next

End Sub

First of all, let me note that your code looks good already. There are only a few things I would change:

It might be a good idea to turn the (Public) Sub into a Private Sub parameterized by FIRST_ROW, TEST_COLUMN, and arrForbidden, which then is called by a new Public Sub passing in your special values. This would separate the configuration from the actual algorithm.
The name of the sub and its parameters could be improved by replacing them with something more expressive, like RemoveAllForbiddenCharacters instead of ReplaceAll, and removalColumn instead of TEST_COLUMN. (Well, the last one is not very good, but nothing better came to my mind immediately.)
I am personally not a fan of declaring multiple variables on one line or initializing on the same line because it often hurts readability. However, here it does not really hurt.

Now, I would like to present a number of different approaches to your problem. Some of these can even be combined for better results.

Using an Array to Query and Write Data

Instead of directly iterating over the cells in the collumn and updating every cell, you can read in the entire range into a two-dimensional (Variant) array using the Value property of the range, or even better the Value2 property, which is faster and usually safer. (See this blog post.)
Then, you can iterate over the array and finally paste it back by assigning to the Value property of the range.

This approach is faster then updating each cell because accessing the cells in a worksheet is rather slow.

Using Regular Expressions

Instead of looping over your array, you could use a regular expression. The VBA support for these is in the library 'Microsoft VBScript Regular Expressions 5.5'. An extensive description on how to use them can be found in the answer to this question on Stack Overflow.

Basically, what you would do is set up the regex matcher with a pattern string—in your case, "[\\/:%'*?<>|"".]". Next, you would use the Replace function of the regex object to replace all occurrences of the forbidden characters in one go.

I do not know whether this is really much faster than the simple loop in your case. That pretty much depends on how well optimized the regex Replace procedure is. But either way, it is a little more expressive and you could reuse the code to do all sorts of more elaborate substitutions.

Using User-Defined Functions

Instead of using a sub, you could write a function just for replacing all forbidden characters in a cell. Then, you could use this in some new column in the worksheets to automatically produce the cleaned-up version of your column in that new column. However, this would probably require you to actually reformat the worksheets before uploading to ALM (assuming ALM requires a fixed sheet layout for the import).

Personally, I do not really like this approach as it pollutes the worksheets with helper columns. However, if the need arises to remove the forbidden characters in more places, writing such a function might be the way to go.

Using Excel Functions

If you do not want to use VBA at all, you can modify the previous approach to use a suitable Excel workbook function. The base function for this approach is SUBSTITUTE, which replaces occurrences of one string in another by a specified value.

A simple approach would be to nest calls to SUBSTITUTE, one for each character to replace. However, this very easily becomes completely unreadable. Moreover, there is an upper limit on how long a formula is allowed to be. (OK, this Microsoft page says the limit is now over 8000 characters, so this should not really be a problem.)

There might be a nicer way to reduce the nested formulas into one array formula, but I personally don't know how to do it.


A C++ implementation of LinkedHashMap This is my attempt at a C++ version of Java's LinkedHashMap. Any criticism is welcome.

I implemented important methods. Big thing still to do would be an iterator. First I wanted to get feedback on this thus far:

#include <unordered_map>
#include <list>
#include <utility>
#include <algorithm>
#include <set>

using namespace std;

template <class K, class V>
class linked_hash_map {
private:
    typedef typename list<K>::iterator list_iterator;
    unordered_map< K, pair<V, list_iterator > > hash;
    list<K> ls;
public:
    int size() { return hash.size(); }
    bool empty() { return hash.empty(); }
    void insert(pair<K,V> kv) {
        if (hash.count(kv.first) == 1) {
            auto p = hash[kv.first];
            hash[kv.first] = make_pair(kv.second, p.second);
        } else {
            ls.push_back(kv.first);
            auto it = ls.end(); --it;
            hash.insert( make_pair(kv.first, make_pair(kv.second, it)));
        }
    }
    void erase(K key) {
        if (hash.count(key) == 1) {
            auto p = hash[key];
            hash.erase(key);
            ls.erase(p.second);
        }
    }
    void eraseEldest() {
        if(!hash.empty()) {
            K key = ls.front();
            ls.pop_front();
            hash.erase(key);
        }
    }
    void eraseNewest() {
        if(!hash.empty()) {
            K key = ls.back();
            ls.pop_back();
            hash.erase(key);
        }
    }
    V at(K key) {
        auto p = hash.at(key);
        return p.first;
    }
    V operator[](K key) {
        auto p = hash[key];
        return p.first;
    }
    list<K>& keyList() {
        return ls;
    }
};

#include <algorithm>
#include <set>

I don't see anything from <algorithm> or <set> in the code.

using namespace std;

Never do this. Just never do this. But especially never do this in a header.

unordered_map< K, pair<V, list_iterator > > hash;
list<K> ls;

It seems a little inefficient to store the key twice - once in the map and once in the list. If the key is an int, no problem, but what if the key is an expensive type?

One possible solution is to store pointers to the keys in the list. So you have:

std::unordered_map< K, pair<V, list_iterator > > hash;
std::list<K const*> ls;

But that's only one alternative.

int size() { return hash.size(); }
bool empty() { return hash.empty(); }

Both of these functions should be const, and probably both noexcept as well.

void insert(pair<K,V> kv) {
    if (hash.count(kv.first) == 1) {
        auto p = hash[kv.first];
        hash[kv.first] = make_pair(kv.second, p.second);
    } else {
        ls.push_back(kv.first);
        auto it = ls.end(); --it;
        hash.insert( make_pair(kv.first, make_pair(kv.second, it)));
    }
}

There are a lot of inefficiencies in this function, and a lot of problems with exception safety.

Let's start with the inefficiencies, focusing on the case where the key is already in the map. You start by searching the map for the key (to count). And then you search the map for the key again to get the list iterator (using operator[]). And then you search it AGAIN to actually set the value.

Instead, what if you searched it just one time, and used the result from then on. For example:

void insert(std::pair<K,V> kv) {
    auto const p = hash.find(kv.first);
    if (p != hash.end()) {
        p->second.first = std::move(kv.second);
    } else {
        // ...

Now let's look at the exception issues in the second half of the function. First you create the key in the list, which can succeed or fail - if it fails, that's bad, but at least your class's invariants are still valid. Next you create the key, value, iterator set in the map. If that fails, then your class is now in the state where there is a key in the list that is not in the hash table.

Unfortunately, there is no easy fix for this. You are updating two different data structures; either one can fail, so no matter what you do you need to handle the case where the first one succeeds and the second one fails.

You could do something like this:

void insert(std::pair<K,V> kv) {
    auto const p = hash.find(kv.first);
    if (p != hash.end()) {
        p->second.first = std::move(kv.second);
    } else {
        ls.push_back(kv.first);
        try {
            auto it = ls.end(); --it;
            hash.insert( make_pair(kv.first, make_pair(kv.second, it)));
        }
        catch (...) {
            ls.pop_back();
            throw;
        }
    }
}

Or, a little more efficiently:

void insert(std::pair<K,V> kv) {
    auto const p = hash.find(kv.first);
    if (p != hash.end()) {
        p->second.first = std::move(kv.second);
    } else {
        auto const it = ls.insert(ls.end(), kv.first);
        try {
            hash.insert( make_pair(std::move(kv.first), make_pair(std::move(kv.second), it)));
        }
        catch (...) {
            ls.erase(it);
            throw;
        }
    }
}

It might also be worthwhile to create two insert() functions, one that takes std::pair<K, V> const& and doesn't use std::move(), and one that takes std::pair<K, V>&& and uses std::move().

On to erase():

void erase(K key) {
    if (hash.count(key) == 1) {
        auto p = hash[key];
        hash.erase(key);
        ls.erase(p.second);
    }
}

Once again, you are searching the hash map multiple times (once for count(), once for operator[], and once again for erase()). Also, you are taking the key by value, which is unnecessary. You're only reading its value, so you should take it by const&.

A more efficient version of the function might look like this:

void erase(K const& key) {
    auto const p = hash.find(key):
    if (p != hash.end()) {
        ls.erase(p->second.second);
        hash.erase(p);
    }
}

The next two functions have basically the same problems:

void eraseEldest() {
    if(!hash.empty()) {
        K key = ls.front();
        ls.pop_front();
        hash.erase(key);
    }
}

There is no need to copy the key into a variable, then remove it from the list, then use the variable to remove it from the hash table. Do it the other way around, and you avoid copies:

void eraseEldest() {
    if(!hash.empty()) {
        hash.erase(ls.front());
        ls.pop_front();
    }
}

Once again, the next two functions have basically the same problems:

V at(K key) {
    auto p = hash.at(key);
    return p.first;
}

There are loads of unnecessary copies here. First, the key is copied into the function argument, because you don't take it by const&. Then both the key and the value (and a list iterator) are copied into p. Then the value is copied again into the return value.

Let's start at the top.

The key doesn't need to be copied here, because you're just inspecting it's value. You can take it by const&:

V at(K const& key) {

The return value probably doesn't need to be copied either, and if you want to use it like lhm.at(key) = new_value;, it must be a reference. So:

V& at(K const& key) {

Now, in the function, you don't need to copy the result of hash.at(key) - in fact you really shouldn't. You should just take a reference to it:

auto& p = hash.at(key);
return p.first;

But there's really no need for p:

return hash.at(key).first;

Putting it all together:

V& at(K const& key) {
    return hash.at(key).first;
}

For const correctness, you'll need two of these functions, one const and one not:

V& at(K const& key) {
    return hash.at(key).first;
}

V const& at(K const& key) const {
    return hash.at(key).first;
}

And of course, all of the same for operator[].

list<K>& keyList() {
    return ls;
}

This is exceptionally dangerous. You are returning a non-const reference to the key list in your class. You are giving users the freedom to completely break your class's invariants. I can do:

auto& key_list = lhm.keyList();
key_list.clear();
// now lhm.hash is full of dangling list iterators

If you want to return the key list, you should not return it as a non-const reference. Either return it as a const reference or - better - by value. Don't give outsiders access to the guts of your class.


Secure password hashing I have found a password hashing article and an implementation.

Is this code secure if I increase the salt to 64 bytes, hash key size to 128 bytes and the iterations to 10000? Are there vulnerabilities or incorrectly implemented sections in this code?

I know that Rfc2898DeriveBytes is making use of HMAC-SHA1, but with a high salt bit count, the SHA1 risk is lowered (if my googling can be trusted).

Any advice or words of caution or ways to secure or correct this code would be welcome.

// The following constants may be changed without breaking existing hashes.
public const int SALT_BYTE_SIZE = 24;
public const int HASH_BYTE_SIZE = 24;
public const int PBKDF2_ITERATIONS = 1000;

public const int ITERATION_INDEX = 0;
public const int SALT_INDEX = 1;
public const int PBKDF2_INDEX = 2;

/// <summary>
/// Creates a salted PBKDF2 hash of the password.
/// </summary>
/// <param name="password">The password to hash.</param>
/// <returns>The hash of the password.</returns>
public static string CreateHash(string password)
{
    // Generate a random salt
    RNGCryptoServiceProvider csprng = new RNGCryptoServiceProvider();
    byte[] salt = new byte[SALT_BYTE_SIZE];
    csprng.GetBytes(salt);

    // Hash the password and encode the parameters
    byte[] hash = PBKDF2(password, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);
    return PBKDF2_ITERATIONS + ":" +
        Convert.ToBase64String(salt) + ":" +
        Convert.ToBase64String(hash);
}

/// <summary>
/// Validates a password given a hash of the correct one.
/// </summary>
/// <param name="password">The password to check.</param>
/// <param name="correctHash">A hash of the correct password.</param>
/// <returns>True if the password is correct. False otherwise.</returns>
public static bool ValidatePassword(string password, string correctHash)
{
    // Extract the parameters from the hash
    char[] delimiter = { ':' };
    string[] split = correctHash.Split(delimiter);
    int iterations = Int32.Parse(split[ITERATION_INDEX]);
    byte[] salt = Convert.FromBase64String(split[SALT_INDEX]);
    byte[] hash = Convert.FromBase64String(split[PBKDF2_INDEX]);

    byte[] testHash = PBKDF2(password, salt, iterations, hash.Length);
    return SlowEquals(hash, testHash);
}

/// <summary>
/// Compares two byte arrays in length-constant time. This comparison
/// method is used so that password hashes cannot be extracted from
/// on-line systems using a timing attack and then attacked off-line.
/// </summary>
/// <param name="a">The first byte array.</param>
/// <param name="b">The second byte array.</param>
/// <returns>True if both byte arrays are equal. False otherwise.</returns>
private static bool SlowEquals(byte[] a, byte[] b)
{
    uint diff = (uint)a.Length ^ (uint)b.Length;
    for (int i = 0; i < a.Length && i < b.Length; i++)
        diff |= (uint)(a[i] ^ b[i]);
    return diff == 0;
}

/// <summary>
/// Computes the PBKDF2-SHA1 hash of a password.
/// </summary>
/// <param name="password">The password to hash.</param>
/// <param name="salt">The salt.</param>
/// <param name="iterations">The PBKDF2 iteration count.</param>
/// <param name="outputBytes">The length of the hash to generate, in bytes.</param>
/// <returns>A hash of the password.</returns>
private static byte[] PBKDF2(string password, byte[] salt, int iterations, int outputBytes)
{
    Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(password, salt);
    pbkdf2.IterationCount = iterations;
    return pbkdf2.GetBytes(outputBytes);
}

Number of iterations is pretty low. Since .NET's PBKDF2 implementation is very slow, you can't afford a good number of iterations. But even with it, 20000 should be affordable for server side hashing. For client side hashing you can go much higher.
You're outputting more than the natural size (20 bytes for SHA-1), which decreases performance twofold without a security gain. At the same cost you could double the number of iteration, which improves security.

=> Increasing the output size beyond 20 bytes decreases security for a given hashing cost.
SlowEquals is a bad name. I'd call it ConstantTimeEquals.
No point in having large salts. Salts should be globally unique. 16 bytes is enough for that, so going beyond that doesn't increase security.
There are no known weaknesses in SHA-1 (or even MD5!) that apply to password hashing. Collision attacks are no threat in this context. The most important distinction between different hashes is the relative software (CPU) vs. hardware (GPU, FPGA, ASIC) performance. So on a 64 bit CPU, SHA-512 is probably a decent choice since it relies on 64 bit arithmetic.


Queue for distributing tasks between threads I implemented the following class to dispatch std::function<void(void)> objects to a thread pool. Multiple threads will block on the pop call until a task is available.

I am using the C++14 standard.

#pragma once

#include<memory>
#include<queue>
#include<mutex>
#include<condition_variable>

namespace alpha {

    template<typename T>
    class AsyncQueue {
        private:
            std::shared_ptr<std::queue<T>> queue;
            std::shared_ptr<std::mutex> mutex;
            std::shared_ptr<std::condition_variable> cond;

        public:
            /* Big 5 */
            AsyncQueue(const AsyncQueue& other) = default;
            AsyncQueue(AsyncQueue&& other) = default;
            AsyncQueue& operator=(const AsyncQueue& other) = default;
            AsyncQueue& operator=(AsyncQueue&& other) = default;
            virtual ~AsyncQueue() = default;

            /**
             * @brief Default constructor
             */
            AsyncQueue() :
                queue(new std::queue<T>()),
                mutex(new std::mutex),
                cond(new std::condition_variable()) {
            }

            /**
             * @brief Push a value to the async queue
             */
            void push(const T& object) {
                {
                    std::lock_guard<std::mutex> lock(*mutex);
                    queue->push(object);
                }
                cond->notify_one();
            }

            /**
             * @brief Push a value to the async queue (move variant)
             */
            void push(T&& object) {
                {
                    std::lock_guard<std::mutex> lock(*mutex);
                    queue->push(object);
                }
                cond->notify_one();
            }

            /**
             * @brief Pop a value from the queue
             */
            T&& pop() {
                std::unique_lock<std::mutex> lock(*mutex);
                while(queue->empty()) {
                    cond->wait(lock);
                }
                T object = std::move(queue->front());
                queue->pop();
                return std::move(object);
            }
    };
}

Specific questions:

Is there a way to keep both implementations of push DRY? The only difference is the type of the argument.
Is this safe? I tested it multiple times with true; while [[ $? == 0 ]]; do ./test; done, but i'd feel a lot better if someone told me that my idea of thread-safety is correct.
pop returns a rvalue-reference, which seems to cause problems when passing it directly to a function with the argument type const T&. Assigning it to a local variable first solves that, but is there a way to make push return a rvalue-reference only when it is needed? I am asking because i know C++ compilers implicitly move a lot.

EDIT:
The version that has the suggestions included can be found here. I applied the BSD 3-clause license to it.

Separation of concerns
You have the members of your class as shared_ptrs this indicates that you want shallow copy assignment and construction. This is not something that you should concern yourself when designing the class.
I would recommend that you design your queue as non-copyable and non-assignable. Because assigning a queue makes no sense. If the user needs to pass a queue around, it is their responsibility to make a shared_ptr<AsyncQueue>. This has the benefit of making your implementation cleaner, but also performing better as your member variables will now get a better cache locality.
The big 5
Following the above the big 5 should now be:
        AsyncQueue(const AsyncQueue& other) = delete;
        AsyncQueue(AsyncQueue&& other) = delete;
        AsyncQueue& operator=(const AsyncQueue& other) = delete;
        AsyncQueue& operator=(AsyncQueue&& other) = delete;
        virtual ~AsyncQueue() = default;

(note delete instead of default). The move assignment and construction cannot be implemented as moving a mutex is not supported (for good reason).
Use make_shared
If you still insist on using shared_ptr, you should use make_shared to construct them because this will co-allocate the reference count with the object data. This saves some memory but more importantly it improves data locality.
Forwarding references
You're better off using forwarding references (also known as universal reference but forwarding reference is the new preferred name) for the push method. In fact I would go as far as to not provide push but instead provide emplace that constructs the object in place like this:
template<typename... Args>
void emplace(Args&&... args){
    {
        std::lock_guard<std::mutex> lock(*mutex);
        queue->emplace(std::forward<Args>(args)...);
    }
    cond->notify_one();
}

emplace() will construct the queued object in place using the arguments passed to emplace() as constructor arguments to avoid a copy. This way you leave the decision whether or not to move to your user.
Obj o;
asyncqueue.emplace(o); // Will copy construct.
asyncqueue.emplace(std::move(o)); // Will move construct.

// Will evaluate o*3 into a temporary and move from it.
// Possibly eliding the copy.
asyncqueue.emplace( o * 3);
asyncqueue.emplace("whatevz"); // Will call constructor taking c-string.

Returning by move in pop
The reason you're crashing is that the local value you moved out of is destroyed when you leave the function scope. So you're moving from rubbish. Returning by r-value reference: Just don't. The compiler will likely perform (N)RVO and the copy will be optimized out if it is possible.
Condtional wait
You have an infinite conditional wait. It may be useful to have a functionality to "sever" the queue and release all threads waiting on jobs.
Typically you would have:
std::atomic<bool> still_running{true};

void stop(){ still_running = false; cond->notify_all();}

void push(T&&){
   if(!still_running) throw error("severed pipe");
   ...
}

void pop(){
   ...
   while(queue->empty() && still_running) {
       cond->wait(lock);
   }
   if(queue->empty(){
       // Check for queue empty here, as still_running could
       // have been changed after we returned but we could still
       // return useful data.
       throw error("severed pipe");
   }
   ...
}

Also prefer the more concise way of waiting on a condition variable:
while(queue->empty()) {
    cond->wait(lock);
}

could be:
cond->wait(lock, [this](){ return !queue->empty();});

For reference, you might be interested in: my implementation of a similar class


Extract data from a DBMS, create a CSV dump and transfer it to an FTP server First of all, my code does work as expected at least to some extent. The intention of the program is to extract data from a DBMS in order to create a CSV dump and transfer it to an FTP server.

My two issues:

The functions of the class seem to be bloated with self.-references. How can that be optimized? Or is that the way it ought to be? It looks overloaded to me.
The population of the plist-variable (first call of if __name__ == '__main__':) has been done very ineptly. The main function does not exit the program if the number of arguments does not equal 2. How can this be achieved respectively or be done better?

import cx_Oracle
import re
import os
import csv
import sys
import getopt
import ftplib
import ntpath

#os.environ['NLS_LANG'] = "en_US.ISO8859-1"
#os.environ['NLS_LANG'] = ".UTF8"

def main(argv):
    inputfile = ''
    outputfile = ''
    usage = 'test.py -i <inputfile> -o <outputfile>'
    flist = []
    try:
        opts, args = getopt.getopt(argv,"hi:o:",["ifile=","ofile="])
    except getopt.GetoptError:
        print usage
        sys.exit(2)
    for opt, arg in opts:
        if opt == '-h':
            print 'test.py -i <inputfile> -o <outputfile>'
            sys.exit()
        elif opt in ("-i", "--ifile"):
            inputfile = arg
        elif opt in ("-o", "--ofile"):
            outputfile = arg
        elif len(sys.argv) != 2:
            print usage
            sys.exit(2)
    flist.append(inputfile)
    flist.append(outputfile)
    return flist

class Extractor(object):

    def __init__(self, iput, oput):
        self.oracle_server = "my_oracle_server"
        self.oracle_password = "my_oracle_password"
        self.oracle_port = "1521"
        self.oracle_sid = "MYSID"
        self.oracle_user = "MYUSER"
        self.ftp_server = 'my_ftp_psw'
        self.ftp_user = 'my_ftp_user'
        self.ftp_passwort = 'my_ftp_passwort'
        self.sql_file = os.path.join(os.getcwd(),iput)
        self.csv_file = os.path.join(os.getcwd(),oput)
        self.dsnStr = cx_Oracle.makedsn(self.oracle_server, self.oracle_port, self.oracle_sid)
        self.connection = cx_Oracle.connect(user=self.oracle_user, password=self.oracle_password, dsn=self.dsnStr)
        self.cursor = self.connection.cursor()

    def execute_sql(self, file):
        self.f = open(file)
        self.sql_statement = self.f.read()
        self.cursor.execute(self.sql_statement)

    def extract_from_db(self):
        self.column_list = [i[0] for i in self.cursor.description]
        self.columns = ';'.join(self.column_list)
        with open(self.csv_file,'w') as outfile:
            outfile.write(self.columns+"\n")
            writer = csv.writer(outfile, delimiter =";")
            for row in self.cursor:
                writer.writerow(row)

    def transfer_file(self):
        print "Transferring " + self.csv_file + " ..."
        self.session = ftplib.FTP(self.ftp_server, self.ftp_user, self.ftp_passwort )
        self.file = open(self.csv_file,'rb')
        self.session.storlines('STOR ' + ntpath.basename(self.csv_file), self.file)     # send the file
        self.file.close()
        self.session.quit()
        print "Complete."

if __name__ == '__main__':
    plist=main(sys.argv[1:]) # very inept, doesn't not exit as intended when number of arguments does not equal 2
    ext = Extractor(plist[0], plist[1])
    ext.execute_sql(ext.sql_file)
    ext.extract_from_db()
    ext.cursor.close()
    ext.connection.close()
    ext.transfer_file()

Class members

Don't use class members if local variables are enough. For example here:

def execute_sql(self, file):
    self.f = open(file)
    self.sql_statement = self.f.read()
    self.cursor.execute(self.sql_statement)

The variables f and sql_statement are used only in this function, so they should be local variables (drop the .self).

As a general rule, it's good to limit the scope of variables, to minimize the chance of accidental modification somewhere else. This is good encapsulation and information hiding.

Review the other functions too, similarly.

Use context managers whenever possible

The function in the previous example should be rewritten using a context manager:

def execute_sql(self, file):
    with open(file) as fh:
        self.cursor.execute(fh.read())

Encapsulation

Looking at this sequence of statements:

ext = Extractor(plist[0], plist[1])
ext.execute_sql(ext.sql_file)
ext.extract_from_db()
ext.cursor.close()
ext.connection.close()
ext.transfer_file()

This code knows too much about the implementation of Extractor: it knows that the class has a cursor member and a connection member. It also knows that these members need to be closed after using, and in a specific order. That's really too intimate knowledge about the implementation. It's also hard to remember these steps, every time you might use this class.

The purpose of encapsulation and information hiding is to free users from knowing too much details. The problem with "knowing" is that it means that if you change the implementation later, all callers must change too. I suggest to reorganize the code, so that the usage looks more like this:

ext = Extractor(plist[0], plist[1])
ext.execute_sql_from_file()
ext.extract_from_db_to_file()
ext.transfer_file()

Inside the implementation of these functions, feel free to do whatever is necessary, such as opening database connection, running query, closing cursor and connection. Users don't need to know these details. This way, you will be able to change the implantation details later, and users of the class don't have to notice anything.


One program using three functions to compare two double-precision numbers I am currently learning C++ though Bjarne Stroustrup book Programming Principles and Practices using C++.

Going through the drills, I am trying to purposefully write efficient and readable code (good coding practices. However, I think I may be overdoing it with my use of functions for tasks within my program.

//Function to check if the entered numbers are similar in value
double similarValues(double valueBigger, double valueSmaller)
{
    if ((valueBigger - valueSmaller) < 0.01) {
        return 1;   //Return 1 if the values are similar
    }
    else {
        return 0;
    }
}

//Function checks which value is larger
double valueLarger(double value01, double value02)
{
    if (value01 > value02) {
        return value01;
    }
    else if (value01 < value02) {
        return value02;
    }
    else {
        return 0;       //Return 0 if the values are equal!
    }
}

//Function checks which value is smaller
double valueSmaller(double value01, double value02)
{
    if (value01 > value02) {
        return value02;
    }
    else if (value01 < value02) {
        return value01;
    }
    else {
        return 0;       //Return 0 if the values are equal!
    }
}

int main()
{

    // Reads two integers on each loop and prints them//
    double value02;
    double value01;

    while (cin >> value01 >> value02) {

        // Checks if the functions valueSmaller & valueLarger have not retuned 0
        if (valueSmaller(value01, value02) != 0 || valueLarger(value01, value02) != 0) {
            cout << "The smaller value is: " << valueSmaller(value01, value02) << " , the larger value is: " << valueLarger(value01, value02) << "\n";

            //Checks if the values are at least similar, returns 1 if true
            if (similarValues(valueLarger(value01, value02), valueSmaller(value01, value02)) == 1) {
                cout<<"The numbers are almost equal. \n";
            }
        }
        // If functions valueSmaller & valueLarger have returned 0 then do the below instuction
        else if (value01 == value02) {
            cout << "Both of these numbers are equal!" << "\n";
        }
        // If the values entered cannot be processed then output an error message
        else {
            cout << "Not a value I know! Incorrect input" << "\n";
        }

    }
}

Please critically (I do not mind if it is harsh) state what programming practices I am not following or following correctly. Also, whether my coding is on par with what you would deem as following great coding conventions.

Am I overdoing the functions?
Am I using return values differently then they should be used?
Is my code readable?
Are my comments accurate and to the point or are they vague?

Your functions and their use are very curious:

A function to determine if two values are similar should be symmetric in its arguments, and return a bool.
A function determining the truth of a property should be called is@. similarValue is a bit of a puzzler, which is actually good as the functions behavior is very surprising.
A conditional expression returns a bool, which can be implicitly converted to an integer of value 0 (false) or 1 (true).
I'm not sure what I should do with valueSmaller and valueLarger, but I am sure that I don't want to see anything like them ever again.

Other points:

Seems you also don't know the conditional-operator (expr ? value-if-true : value-if-false). It can be used to write things better, but beware of getting carried away with it.
You are using using namespace std;.
That's a bad idea, read "Why is “using namespace std;” considered bad practice?".
When you output string- and char-literals consecutively, just concatenate them together. Also, if you have a length-1-string-literal, a char-literal can serve the same purpose more efficiently.
Your comments are, I'm sorry to say, useless, as they just rephrase some of the more obvious code.
When you use descriptive names, most other comments for describing what code does also become superfluous (exception: doc-comments which will be extracted for bare-bones documentation).
Comments are for giving non-obvious reasons for doing things you do, reasons for doing them the way you do them, or describing how you do something.
See this good answer by rolfl about how to properly comment.


Iterating through a range using lodash/AngularJS and saving data The code below doesn't seem right to me. The scenario is:

User enters in a "quantity" into a form field.
If the user enters in 5, the loop below should iterate 5 times.
There should now be 5 new entries in the database with the container.product and container.status.

Any advice on making this cleaner?

var container = new Container($scope.batchFields);

container.product = $scope.item.originalObject._id;
container.status = 'active';

_.each($scope.batchFields, function(batch) {
  _.each(_.range(batch.batchesQuantity, 0, -1), function (val,i) {

    // This $save code smells a little with it
    // being inside the _.each.
    container.$save(function(response) {
      $notify.success('purchase.order.edit.created');
      if ($scope.$close) {
        $scope.$close();
      }
    }, function(errorResponse) {
      $scope.errors = errorResponse.data.message;
    });
  });

});

Please do not make separate calls (Http requests) for saving each container,as this will affect the web application performance. Instead batch the calls ( 5 calls at one time). Store them in an array and make a single call

_.each($scope.batchFields, function(batch) {
  var containersList = [];
  _.each(_.range(batch.batchesQuantity, 0, -1), function(val, i) {

    // store them in the array
    containersList.push(new Container($scope.batchFields));
  });

  $http.post('saveContainers', containersList).then(function(response) {
    $notify.success('purchase.order.edit.created');
    if ($scope.$close) {
      $scope.$close();
    }
  }, function(errorResponse) {
    $scope.errors = errorResponse.data.message;
  });

});


Partitioning a list in F# based on whole group characteristics I only started programming in F# yesterday, so I've not yet discovered what idiomatic F# actually looks like.

The first task I set myself required partitioning a list into smaller lists but where the partitioning is based on the characteristics of the whole group, rather than just being able to find split points based on the current element.

For example, given the list [1;2;3;4;5], I might want to group into sub-lists when the sum of the sub-list has reached at least 5. This would result in the output [[1;2;3]; [4;5]].

Any remaining elements that don't meet the criteria would be in a final sub-list.

My first attempt is below:

module Test

let rec partitionOn groupComplete list =
    let take list n = Seq.take n list

    // Take items from the front of the list until they form a complete group
    // or there are no more items
    let firstGroupAndRemainder itemsList =
        let firstGroup =
            [0 .. List.length itemsList]
            |> Seq.map (take itemsList)
            |> Seq.tryFind groupComplete
        match firstGroup with
        | Some g ->
            let groupList = g |> Seq.toList
            let remainingList = Seq.skip (List.length groupList) itemsList |> Seq.toList
            (groupList, remainingList)
        | None -> (itemsList, [])

    match list with
    | [] -> []
    | _ ->
        let group, rest = firstGroupAndRemainder list
        [group] @ partitionOn groupComplete rest

[<EntryPoint>]
let main argv =
    // Groups with sum greater than 5 (plus remaining elements)
    let result1 = partitionOn (fun l -> Seq.sum l > 5) [1;5;2;6;2]
    printfn "result1: %A" result1 // [[1;5]; [2;6]; [2]]

    // Groups with length 3 (plus remaining elements)
    let result2 = partitionOn (fun l -> Seq.length l = 3) [1;5;2;6;2]
    printfn "result2: %A" result2  // [[1;5;2]; [6;2]]

    0

It feels like there should be a simpler way to achieve this but I haven't yet thought of it.

Update

I've discovered the defaultArg function, so the firstGroupAndRemainder function might be slightly tidier as:

let firstGroupAndRemainder itemsList =
    let firstGroup =
        [0 .. List.length itemsList]
        |> Seq.map (take itemsList)
        |> Seq.tryFind groupComplete
    let groupList = (defaultArg firstGroup (List.toSeq itemsList)) |> Seq.toList
    let remainingList = Seq.skip (List.length groupList) itemsList |> Seq.toList
    (groupList, remainingList)

Based on this answer from the Haskell version of this question, it looks like we can do something as simple as:

let partitionOn groupComplete list =
    let rec inner currentGroup remainingList =
        match (currentGroup, remainingList) with
        | (group, []) -> [group]
        | (group, remaining) when groupComplete group -> [group] @ (inner [] remaining)
        | (group, head::tail) -> inner (group @ [head]) tail
    inner [] list

This simply recursively handles the three cases of: running out of elements; having a complete group; and building a group.

Update

Henrik Hansen pointed out that it is preferable to have a tail-recursive function. One possible way of achieving this is:

let partitionOn groupComplete list =
    let rec inner currentGroup remainingList =
        match remainingList with
        | [] -> [currentGroup]
        | head::tail ->
            let complete = groupComplete currentGroup
            let additionalGroup = if complete then [currentGroup] else []
            let newCurrentGroup = if complete then [] else currentGroup @ [head]
            let newRemaining = if complete then remainingList else tail
            additionalGroup @ (inner newCurrentGroup newRemaining)
    inner [] list

This merges together the last two cases of the match and gives a single call to inner at the end.

Update 2

If we look at the IL for this version, we can see that it is tail recursive:

    ...
    IL_0069: tail.
    IL_006b: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0> [FSharp.Core]Microsoft.FSharp.Core.Operators::op_Append<class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!a>>(class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0>)
    IL_0070: ret
    IL_0071: ldarg.1
    IL_0072: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!0> class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!a>>::get_Empty()
    IL_0077: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!0> class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!a>>::Cons(!0, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!0>)
    IL_007c: ret
} // end of method _::'inner@2-5'

Update 3

Nice idea to use a fold, from TheQuickBrownFox. This can be done more simply using the built-in fold function, keeping the same API:

let partitionOn groupComplete list =
    let folder acc x =
        match List.rev acc with
        | [] -> [[x]]
        | current::rest when groupComplete current -> acc @ [[x]]
        | current::rest -> (List.rev rest) @ [current @ [x]]
    List.fold folder [] list

However, @ is O(n), whereas :: is O(1), so it should really be:

let partitionOn groupComplete list =
    let folder acc x =
        match acc with
        | [] -> [[x]]
        | current::rest when groupComplete current -> [x]::acc
        | current::rest -> (x::current)::rest
    List.fold folder [] list |> List.map List.rev |> List.rev

Update 4

Based on TheQuickBrownFox comment the fold could be modified as follows:

let partitionOn initialGroupValue groupUpdate groupComplete list =
    let folder acc x =
        match acc with
        | ([], score) -> ([[x]], groupUpdate score x)
        | (a, score) when groupComplete score -> ([x]::a, groupUpdate initialGroupValue x)
        | (current::rest, score) -> ((x::current)::rest, groupUpdate score x)
    List.fold folder ([], initialGroupValue) list |> fst |> List.map List.rev |> List.rev

This version separates the current group evaluation into an update and a test, so that the minimum change is made for each iteration of the fold and the whole group doesn't need to be recalculated each time.


Convert a list of dictionaries to a dictionary of dictionaries I need to convert a list of dictionaries to a dictionary of dictionaries, with a particular item as the new key.

This is the way I'm currently doing it:

>>> a
[{'bar': 'baz', 'id': 'foo'}, {'bar': 'baz', 'id': 'qux'}]
>>> {
    item['id']:{
        sub_item:item[sub_item] for sub_item in item if sub_item != 'id'
    } for item in a}

{'qux': {'bar': 'baz'}, 'foo': {'bar': 'baz'}}

However, this looks really ugly to me.  Is there a more elegant way to do this?

While using methods with side effects in list- or dict-comprehensions is generally frowned upon, in this case you could make use of dict.pop to get the id and at the same time remove it from the dictionary.

>>> a = [{'bar': 'baz', 'id': 'foo'}, {'bar': 'baz', 'id': 'qux'}]
>>> {d.pop("id"): d for d in a}
{'qux': {'bar': 'baz'}, 'foo': {'bar': 'baz'}}

Keep in mind, though, that this will alter the dictionary in-place, i.e. afterwards:

>>> a
[{'bar': 'baz'}, {'bar': 'baz'}]

If you do not want to alter the original dictionaries, use map(dict, a) to create copies before poping elements from those, leaving the original dicts in a as they were.

>>> {d.pop("id"): d for d in map(dict, a)}
{'qux': {'bar': 'baz'}, 'foo': {'bar': 'baz'}}


Caesar Cipher [The Odin Project-Javascript Exercise] Very new to coding, so please don't bully me.

Implement the legendary caesar cipher:

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

Question: Write a function that takes a string to be encoded and a shift factor and then returns the encoded string:

caesar('A', 1) // simply shifts the letter by 1: returns 'B' the cipher should retain capitalization:

caesar('Hey', 5) // returns 'Mjd; should not shift punctuation:

caesar('Hello, World!', 5) //returns 'Mjqqt, Btwqi!' the shift should wrap around the alphabet:

caesar('Z', 1) // returns 'A' negative numbers should work as well:

caesar('Mjqqt, Btwqi!', -5) // returns 'Hello, World!'

My Solution:

function caesar(string, num) {
let arr = [];
for(let i=0;i<string.length;i++)
  {if(!(/[a-zA-Z]/.test(string[i])))
    {arr[i]=string[i]; continue;}
  let n = string.charCodeAt(i) + num;
  if (string[i] == string[i].toLowerCase())
    {if(n>122)
      {while(n>122)
        {n-=26;}}
     else
      {while(n<97)
        {n+=26;}
      }
    }
  else
    {if(n>90)
      {while(n>90)
        {n-=26;}
      }
     else
      {while(n<65)
        {n+=26;}
      }
    }
  arr[i]=String.fromCharCode(n);
  }
console.log(arr.join(''));
}
caesar("Hello, World!", 2);
caesar("Hello, World!", 75);

The code is working perfectly as per requirement, but please help me with a better solution if possible.

And if you do, please use comments to extensively explain the working process, as I'm quite the noob.

Welcome to Code Review, some considerations that can help you to simplify your code:

you have an alphabet of 26 letters, so if the shifting operation is
limited to a 26 characters range you can use the mod operation %26
to determine the final position.
you can have a shift negative operation num (ex. -5), for a 26
set of elements shift this is equal to a positive shift of  Math.abs(26 - Math.abs(num)) , so for 5 the positive shift is 21.

So if you have a c character and you want to obtain the ascii code of the corresponding shifted char of num positions you can obtain it in the following way:

const start = c === c.toLowerCase() ? 'a'.charCodeAt(0) : 'A'.charCodeAt(0);
const diff = c.charCodeAt(0) - start;
const sh = num >= 0 ? diff + num : diff + Math.abs(26 - Math.abs(num));
const code = sh % 26 + start;

The first line returns the ascii code of 'a' or 'A' depending if the char c is lowercase or uppercase called start, the second gives you the difference between c and start, the last two lines calculate the code of the shifted corresponding character.

After your function can be rewritten in the following way:

'use strict';

function caesar(str, num) {
    const arr = [];
    const re = /[a-zA-Z]/;
    for (const c of str) {
        if (re.test(c)) {
            const start = c === c.toLowerCase() ? 'a'.charCodeAt(0) : 'A'.charCodeAt(0);
            const diff = c.charCodeAt(0) - start;
            const sh = num >= 0 ? diff + num : diff + Math.abs(26 - Math.abs(num));
            const code = sh % 26 + start;
            arr.push(String.fromCharCode(code));
        } else {
            arr.push(c);
        }
    }

    return arr.join('');
}

I set arr and regex as const and instead of iterate over string using the index, I preferred the for ... of construct.

Note: I'm a javascript beginner too, so every suggestion to improve my code as for the original question is highly appreciated.