Dijkstra implementation for large graphs I am implementing the Dijkstra algorithm for a large graph (40k nodes, 100k arcs). For shorter paths the searchtime is under a second for larger ones (from one end to the other) it takes quite some minutes to do it. I am also drawing the path after the search, so I am using some Qt objects. How could I make it faster? I feel like I am losing time when I search the neighbors because of the map structure.

This is the class:

class PathFinder {
public:
   void findPath2(const Node & start, Node & finish);

   static PathFinder& getInstance();
   PathFinder();
   PathFinder(Gps gps);
   ~PathFinder();

   unsigned int* getPrev() const;
   void setPrev(unsigned int* prev);
   QVector<unsigned int> makePath(int target);

   GraphicNode* getTo();
   GraphicNode* getFrom();

   void setTo(GraphicNode* node);
   void setFrom(GraphicNode* node);

   class Compare
   {
   public:
      bool operator() (std::pair<Node*, int> a, std::pair<Node*, int> b)
      {
         return a.second > b.second;
      }
   };

private:
   static PathFinder* _pathfinder;
   Gps _gps;
   GraphicNode* _from;
   GraphicNode* _to;

   unsigned int* _prev;
   unsigned int* _dist;
   unsigned int _notVisited;

   bool selectedNode = false;

   Node* getMinNode();
   bool hasNotVisited();
};

This is the search function:

void PathFinder::findPath2(const Node& start, Node& finish)
{
   QVector<Node> nodes=_gps.graph().nodes();

   std::priority_queue<std::pair<Node*,int>,std::vector<std::pair<Node*, int>>,Compare> q;

   _dist[start.id()] = 0;
   for (int i = 0; i < nodes.size(); i++) {
      std::pair<Node*, int> p = std::make_pair(const_cast<Node*>(&nodes.at(i)), _dist[i]);
      q.push(p);
   }

   while (!q.empty()) {
      std::pair<Node*, int> top = q.top();
      q.pop();
      Node* minNode = top.first;
      QMap<Node*, unsigned short> nextNodes = minNode->nextNodes();

      if (*minNode == finish) {
         return;
      }
      int minNodeId = minNode->id();
      for (QMap<Node*, unsigned short>::iterator iterator=nextNodes.begin(); iterator != nextNodes.end(); iterator++) {
         Node* nextNode = iterator.key();
         int altDist = _dist[minNodeId] + nextNodes.value(nextNode);
         int nextNodeId = nextNode->id();
         if (altDist < _dist[nextNodeId]) {
            _dist[nextNodeId] = altDist;
            _prev[nextNodeId] = minNodeId;
            std::pair<Node*, int> p = std::make_pair(nextNode, _dist[nextNodeId]);
            q.push(p);
         }
      }
   }
}

This is the structure of the node, it contains a map to its neighbors with the weight as the value (x and y are coordinates for drawing it later on, don't mind those):

class Node {
private:
   unsigned short _id;
   double _y;
   double _x;
   QMap<Node*, unsigned short> _nextNodes;
   bool _visited = false;

public:
   Node();
   Node(unsigned short id, double longitude, double latitude);

   unsigned short id() const;
   double y() const;
   void setY(double y);
   double x() const;
   void setX(double x);

   bool operator==(const Node& other);
   void addNextNode(Node* node, unsigned short length);

   QMap<Node*, unsigned short> nextNodes() const;
};

Don't use QT objects when you are not working with QT constructs. There is no benefit to it.
Your node::_id is unsigned shirt, which for MSVS has a range of 0 to 65,535. Be aware of that when you graph grows.
Do not use a map. A std::vector is way faster/bettter for traversing than a std::map.
You do a lot of copying data around:

QMap<Node*, unsigned short> nextNodes = minNode->nextNodes();

That is a copy of all neighbors everytime you access a node during your search. If you really need the temporary, which you dont then at least make this a reference.


Invitation confirmation validator class InvitationConfirmationValidator < ActiveModel::Validator
  def validate(record)
    invitation = Invitation.find_by_url_suffix(record.id)
    if invitation
      if invitation.materialized?
        record.erros.clear
        record.errors[:base] << "Invitation already materialized"
      end
    else
      record.erros.clear
      record.errors[:base] << "Invitation does not exist"
    end
  end
end

The above is the code for a Validator. It first checks if an invitation with an ID exists. If it does, it checks whether it has already been used.

The code seems to me more complex than it should be to achieve this simple task. Can its complexity be reduced?

The first thing I would do is assign those strings to constants since they will never change throughout the life of the program.
Also, I'm not sure why you have to clear the errors out when you validate this part of the model. When I run valid? on a model, personally I would like to see ALL of the reasons that the model isn't valid.

class InvitationConfirmationValidator < ActiveModel::Validator
  def validate(record)
    invitation = Invitation.find_by_url_suffix(record.id)
    return record.errors[:base] << MISSING_INVITE_MESSAGE unless invitation
    return record.errors[:base] << MATERIALIZED_INVITE_MESSAGE if invitation.materialized?
  end
end


Find all words in a dictionary that can be made with a string of characters (Recursion/Binary Search) I'm working on an algorithm that could take in a string of 20 random characters, and display to the user every word in a dictionary that can be successfully made with those letters, regardless of length. If the string is "made", it would return "mad", "made", etc.

However, the execution time is extremely poor with my current method. I've been recommended to give the Trie structure a shot. But seeing how Java doesn't have it built in, I wanted to see if there's a better approach to this algorithm, or if I should look at implementing my own Trie structure.

I currently use a Binary Search implementation to check for prefixes, found through recursion, and see if a certain recursive path should be continued or not.

private ArrayList<String> dict = new ArrayList<>();
private Set<String> possibleWords = new HashSet<>();

private void getAllValidWords(String letterPool, String currWord) {
    //Add to possibleWords when valid word
    if (letterPool.equals("")) {
       // No action to be done.
    } else if(currWord.equals("")){
        //Will run only the initial time the method is called.
        for (int i = 0; i < letterPool.length(); i++) {
            //Get the individual letters that will become the first letter of a word
            String curr = letterPool.substring(i, i+1);
            //Delete the single letter from letterPool
            String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1));
            if(inDict(curr)){
                possibleWords.add(curr);
            }
            boolean prefixInDic = binarySearch(curr);
            if(prefixInDic){
                //If the prefix isn't found, don't continue this recursive path.
                getAllValidWords(newLetterPool, curr);
            }
        }
    } else {
        //Every time we add a letter to currWord, delete from letterPool
        for(int i=0; i<letterPool.length(); i++){
            String curr = currWord + letterPool.substring(i, i+1);
            String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1));
            if(inDict(curr)){
                possibleWords.add(curr);
            }
            boolean prefixInDic = binarySearch(curr);
            if(prefixInDic){
                //If the prefix isn't found, don't continue this recursive path.
                getAllValidWords(newLetterPool, curr);
            }
        }
    }
}

private boolean binarySearch(String word){
    int max = dict.size() - 1;
    int min = 0;
    int currIndex;
    boolean result = false;
    while(min <= max) {
        currIndex = (min + max) / 2;
        if (dict.get(currIndex).startsWith(word)) {
            result = true;
            break;
        } else if (dict.get(currIndex).compareTo(word) < 0) {
            min = currIndex + 1;
        } else if(dict.get(currIndex).compareTo(word) > 0){
            max = currIndex - 1;
        } else {
            result = true;
            break;
        }
    }
    return result;
}

Favor interfaces over implementations

private ArrayList<String> dict = new ArrayList<>();

This would more commonly be written as

private List<String> dict = new ArrayList<>();

Using the interface is more flexible and easier to change.

Dictionary types

That said, the more common type for a dictionary is

private Set<String> dictionary = new HashSet<>();

Then you can generate all the words and check them.

If you are committed to a binary search, consider using a NavigableSet.

private NavigableSet<String> dictionary = new TreeSet<>();

This would give you code like

    for (char letter : letterPool.toCharArray()) {
        String current = word + letter;

        String bound = word + (letter + 1);
        NavigableSet<String> prefixed = dictionary.subSet(current, true, bound, false);

        if (prefixed.isEmpty()) {
            // no need to keep looking if we didn't find anything
            continue;
        }

        // current will be the first element of the Set if present
        if (prefixed.first.equals(current)) {
            possibleWords.add(current);
            prefixed.pollFirst();
        }

        // if there's more than one letter left in the pool
        if (letterPool.size > 1) {
            // recurse with it out of the pool
            String remaining = letterPool.substring(0, i) + letterPool.substring(i + 1);
            getAllValidWords(remaining, current, prefixed);
        }
    }

I changed the names of currWord to word, newLetterPool to remaining, and curr to current, as I find that easier to read.  Your mileage may vary.

We don't need to check if letterPool or word are empty.  The code works for those cases.

I added prefixed to the recursive call.  The reason is that we don't need to search the whole tree.  We only need the subtree.

I moved generation of newLetterPool to the point where I know it will be used.  Prior to that we may never use it, so why waste time generating it?

Trie

This is the application for which a Trie is designed.  That said, my experience is that they tend to be slow and memory intensive.  It takes too long to build the structure to get the gains from fast prefix searches.

You might well find the brute force solution with a HashSet to be faster.  In that solution, you basically generate each possible permutation and then filter out just the ones that are words.  The downside is that you may check a lot of words like zxqjv.

A Trie works best in situations where it's prebuilt and easy to load into memory or where it stays as it is for long periods of time.  Also, you should not be memory constrained.

If you do attempt to use a Trie, consider using it only for the first few letters.  Then you can go back to something more like this.


My first ever calculator C# This is my first ever created program I've made. It's not very good but I'm pretty proud of it.
If you have any suggestions I could add into the calculator I would gladly do that.
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

namespace CSharp_Shell
{
    public static class Program
    {
        public static void Main()
        {
           try
           {
                Console.WriteLine("--------------------------------");
                Console.WriteLine("Operators:");
                Console.WriteLine("+ = Add");
                Console.WriteLine("- = Subtract");
                Console.WriteLine("* = Multiply");
                Console.WriteLine("/ = Divide");
                Console.WriteLine("^ = Power");
                Console.WriteLine("--------------------------------");

                Console.Write("Enter operator: ");

                string op = (Console.ReadLine());

                Console.Write("Enter First Number: ");
                double num1 = Convert.ToDouble(Console.ReadLine());

                Console.Write("Enter Second Number: ");
                double num2 = Convert.ToDouble(Console.ReadLine());
                Console.WriteLine("--------------------------------");

                if (op == "+")
                {
                   Console.WriteLine(num1 + num2);
                   Console.WriteLine("--------------------------------");
                }
                else if (op == "-")
                {
                   Console.WriteLine(num1 - num2);
                   Console.WriteLine("--------------------------------");
                }
                else if (op == "/")
                {
                   Console.WriteLine(num1 / num2);
                   Console.WriteLine("--------------------------------");
                }
                else if (op == "*")
                {
                   Console.WriteLine(num1 * num2);
                   Console.WriteLine("--------------------------------");
                }
                else if (op == "^")
                {
                   double value1 = Math.Pow(num1, num2);
                   Console.WriteLine("{0}", value1);
                   Console.WriteLine("--------------------------------");
                }
                else
                {
                   Console.ForegroundColor = ConsoleColor.Red;
                   Console.WriteLine("error");

                   Console.ForegroundColor = ConsoleColor.White;
                   Console.WriteLine("--------------------------------");
                }
           }
           catch
           {
            Console.ForegroundColor = ConsoleColor.White;
                Console.WriteLine("--------------------------------");

            Console.ForegroundColor = ConsoleColor.Red;
            Console.WriteLine("error");

            Console.ForegroundColor = ConsoleColor.White;
                Console.WriteLine("--------------------------------");
           }
           Console.ForegroundColor = ConsoleColor.Gray;
           Console.Write("Press any key to stop the program");
           Console.ReadKey();
        }
    }
}

Over all, if this is your first time coding, you've really done a stellar job. I'm having a hard time believing this was a first attempt without replicating someone else's code, just because of how cleanly you've approached it. Very well done.
The below suggestions are more further improvements than they are corrections on what you were doing. Some of the things I suggest may not make full sense now, but are good habits to breed early on, because when you start working on more complex applications, you'll significantly benefit from not having to learn every mistake the hard way.

Avoid repetition
How often do you see this code:
Console.ForegroundColor = /* some color */;
Console.WriteLine(/* some message */);

The answer is a lot. So to save yourself some repeated code, abstract it into a method:
public void WriteMessage(string message, ConsoleColor color = ConsoleColor.White)
{
    Console.ForegroundColor = color;
    Console.WriteLine(message);
}

It seems like a little thing, but it effectively halves amount of lines (revolving around printing logic) in your main method, since you can now just do:
WriteMessage("error", ConsoleColor.Red);

Note that I also made the color an optional parameter, so it can be omitted when no special color is needed:
WriteMessage("a message without special color");

Syntax improvements
This is just a little thing, but notice how every condition ends with drawing a line:
if (op == "+")
{
    Console.WriteLine(num1 + num2);
    Console.WriteLine("--------------------------------");
}
else if (op == "-")
{
    Console.WriteLine(num1 - num2);
    Console.WriteLine("--------------------------------");
}
// and so on...

If all of them end on the same instruction, it's easier to just put that instruction behind the if/else:
if (op == "+")
{
    Console.WriteLine(num1 + num2);
}
else if (op == "-")
{
    Console.WriteLine(num1 - num2);
}
// and so on...

Console.WriteLine("--------------------------------");

But you can go further. The same applies to printing the result. So you can also move that outside of the chain:
double result = 0;

if (op == "+")
{
    result = num1 + num2;
}
else if (op == "-")
{
    result = num1 - num2;
}
// and so on...

Console.WriteLine(result);
Console.WriteLine("--------------------------------");

Syntax improvements
You should avoid if else chains where you keep checking if the same variable matches a given value. That's precisely what a switch was made for:
switch(op)
{
    case "+":
        Console.WriteLine(num1 + num2);
        break;
    case "-":
        Console.WriteLine(num1 - num2);
        break;
    case "*":
        Console.WriteLine(num1 * num2);
        break;
    // and so on...
}

Break it up
The code you wrote is relatively neat for a beginner program. Good indentation, reasonable whitespace separation between lines.
But the next step is breaking your method down into smaller steps. If I were to sum up what this code does, I'd list it as follows:

Takes in a number (twice)
Takes in a mathematical operation
Writes messages to the console, sometimes in color.
Performs the selected operation on the selected numbers

You could add a lot more bullet points here if you wanted, e.g whether you consider drawing a horizontal separator as a different task from writing a message to the console. I'm sticking with these four as it's a basic example.
These four bullet points are a great (but not complete) guideline to how you need to break down your application. Anything you consider a separate task, is generally going to want to be in a method on its own. So in this case you'd be looking at methods like:

double GetNumber()
char GetOperation() - I'd consider using a custom enum here instead of a character, but let's keep it simple for now.
void WriteMessage(string message, ConsoleColor color = ConsoleColor.White) - see previous point section
Separate operator methods:

double Add(double a, double b)
double Subtract(double a, double b)
double Multiply(double a, double b)
double Divide(double a, double b)
double Power(double a, double b) - This mirrors Math.Pow and you could technically skip your own method and use Math.Pow directly. However, due to abstraction considerations, it's good practice to still define your own method. This is maybe beyond your current skill level, but the idea behind it is that if you suppose that you change your calculation logic in the future, it's easier to rewrite the content of your Power method once, than it is to go hunt for all references to Math.Pow and substitute them all individually.

There's definitely still room for improvement, but you're still a beginner and this is a good first step. Try to write the code in your Main method in a way that it relies on these methods I just listed, instead of having the Main menu do all the heavy lifting by itself.
Think of it this way: when you stop being a cook and instead become a chef (= better code), then you're no longer doing the small jobs yourself, e.g. peeling the potatoes and washing the dishes. Tasks get delegated. Chefs (the Main method) rely on the small things being done by others (the submethods).
Refactoring
I noticed this:
Console.WriteLine("{0}", value1);

It's needlessly complex. Just do:
Console.WriteLine(value1);

I suspect that this is a refactoring remnant. It used to do more than just print value1, but over time you changed the code, and never steered away from using the String.Format approach.
That's completely normal, but this is precisely why developers should always revisit code when it's "finished", to see if there are some remnants of past attempts that can be cleaned up or refactored into something better.
A better user experience
It helps to sometimes think like a user instead of like a developer. When adding 1 and 2 together, how do we write things?

+ 1 2
1 + 2
1 2 +

I hope you'll agree that the second bullet point is vastly preferred. Note that the first bullet point also exists (it's called Polish notation), but unless you have reason to believe that your users predominantly use Polish notation, the second bullet point is how users think.
But when you ask for user input, you are asking for + 1 2:
Console.Write("Enter operator: ");
string op = (Console.ReadLine());

Console.Write("Enter First Number: ");
double num1 = Convert.ToDouble(Console.ReadLine());

Console.Write("Enter Second Number: ");
double num2 = Convert.ToDouble(Console.ReadLine());

That doesn't match with how users think. It's a very simple improvement to just change the order of your code. It doesn't change how your code works, but it does improve the user experience.
An even better user experience
This is not as simple, but as a next challenge, you could see if you could move away from users having to input separate values and having to press enter inbetween.
See if you can figure out how to let users input the whole formula, e.g. "1+2" and take it from there. Or, alternatively, read every key the user presses and dynamically figure out what they mean.
If you think about a real-world calculator, it works without needing to press enter inbetween its data input. So try and make yours similar. It's a great user experience improvement, and a good exercise for someone who's new to coding.


Revealing module pattern modified for more class-like behavior I've recently been learning about the revealing module pattern, and it seems like a really good way to structure code in many cases. However, I find myself wanting to use it like a class, so I'm trying to modify it to behave in the following ways:

Instances get created from the module (doesn't just immediately return its own object)
The module can take arguments and use them like a constructor (I don't see this in many revealing module examples)
The module can be extended like a class; extending modules inherit its public properties/methods and can share arguments/parameters

I seem to have achieved this by using just a function expression instead of an IIFE, creating an instance of the parent within the extending module, and passing the extending module's arguments into the parent instance. Here is the full working pattern I've come up with:

var Module = function({text = 'no text given'} = {}) {
    var private = {};
    private.text = text;
    private.logText = function() {
        console.log(private.text);
    };

    var public = {};
    public.logText = private.logText;

    return public;
};

var Extended = function({extraText = 'no extra text given'} = {}) {
    var parent = Module(arguments[0]);
    // Note: I chose to use an object as a parameter in this snippet,
    // but you could also just use regular parameters and pass in
    // arguments instead of arguments[0]

    var private = {};
    private.extraText = extraText;
    private.alertText = function() {
        alert(private.extraText);
    }

    var public = {};
    public.logText = parent.logText;
    public.alertText = private.alertText;

    return public;
};

// TEST INSTANCES

var testModule = Module({ text: "I'm in the console." });
testModule.logText(); // "I'm in the console."

var testExt = Extended({ extraText: "I'm in an alert." });
testExt.logText(); // "no text given"
testExt.alertText(); // alerts "I'm in an alert."

var anotherExt = Extended({
  text: "I'm in the console.",
  extraText: "I'm in an alert."
});
anotherExt.logText(); // "I'm in the console."
anotherExt.alertText(); // alerts "I'm in an alert."

Now it basically behaves as a class like I was wanting - but I'm wondering what limitations/shortcomings there might be that I'm not seeing. Is the revealing module pattern ever used this way?

Review

This is a code review so I will point out some style problems first

Function expressions V statements

There are several ways to ways you can declare a named function.

As a statement.  function functionName() { }
As an expression. const functionName = function() { };  Note the semicolon

The most important difference between the two is that function statements are hoisted and available in all part of the scope they are declared in. Function expressions are not, even if you declare them as a var (which is hoisted) it remains undefined until it is assigned a value.

Function declared as statements are thus the safest form of function declaration and should be preferred over expression declarations.

testA(); // no error and calls testA
testB(); // throws an error ReferenceError: testB is not defined
testC(); // throws and error TypeError: testC is not a function

function testA(){};
const testB = function(){};
var testC = function(){};

const, var and let

When declaring variables use the appropriate type. const is the preferred type, unless you need to modify the value then use var. If you wish to use let in preference to var that is up to you, but be warned that let is not hoisted.

Avoid reserved words.

There is a set of words that are reserved and represent existing, or possible future tokens. Two of these are public, and private you should avoid using reserved words.

There are also many context specific words that you should try to avoid unless you are sure you are not overwriting an existing global property. For example parent, though you safely use it, I do not know if that is just luck or  knowledge that parent is a global scope object AKA window.parent and you are in function scope thus not overwriting the global.

Anti pattern

I consider this as an anti pattern

var Extended = function({extraText = 'no extra text given'} = {}) {
   var parent = Module(arguments[0]);

I am not sure if you are aware that if you call

 Extended(); // without an argument

Then arguments[0] is undefined, and arguments.length === 0 but the destructured argument named extraText has the value "no extra text given"

If you did this in purpose may I suggest that you use an alternative...

const Extended = function(info = {}) {
    const parent = Module(info);
    info = {extraText : "no extra text given", ...info};

...as it is much clearer what the intent is.

Use quotes not apostrophes

To avoid confusion with template string declarations delimited by Back Quote try to avoid using Apostrophes (AKA single quite)

Don't duplicate variables

The object Module creates the object private and assign the property text the value of the argument text. This is just a duplication as the only place you use text is in the function it is available as the argument

Design

You are on the correct path to using JavaScript to create private (protected) and public states. Though there is no need to create the private objects as you can use the function scope to hold the private state, including functions

Simple example of a object with both public and private states, using getters and setters to protect type (count as a Number), and access to private state from private and public scopes (eg function 'show')

function MyObj(text = "Nothing to see here."){

     if (typeof text !== "string") {  text = "Wrong type." }

     // private variables
     var count = 0;  // Type safe from outside

     // private functions declared here or in the API below
     function show(){
         console.log(text);
         count += 1;
     }

     // public API also accessible from private scope
     const API = {
         get count() { return count  },
         set count(c) {  // only set if a number to keep type safe state
             if (!isNaN(c)) { count = Number(c) }
         }
         show,  // public access to private function

        // OR add the function here
         show() {
            console.log(text);  // still have private access
            count += 1;
         }
     }

     // internal access
     setTimeout(show, 1000); // via private function

     // or via public API
     setTimeout(API.show, 2000);

     return API;
}

You can nest these objects creating additional levels of state security. You can also create several public objects that share a single private state,

A rewrite

As your code does nothing with its private states there was not much to go by. The Design section above would be more appropriate for what you may be after.

The following does the same as your code with considerably less noise.

function Module({text = 'no text given'} = {}) {
    function logText() { console.log(text) };  // private function
    return { logText };
}

function Extended(info = {}) {
    info = {extraText : "no extra text given", ...info};
    function alertText() { alert(info.extraText) }
    return { ...Module(info), alertText };
}


Extract data from one column of SQL Server table I have an SQL Server table from which I want to extract data from one column (DD) and return as multiple columns.

The data is in NVARCHAR and looks like:

  ;HF:GN;HM:GTN;HN:GN;PN:AN;PVD:GO;PVR:1.1;BN:AN;BVD:GO;BV:2.3;

There is less to be changed in the way this data is structured.

I have to extract all of the data in ... and between : and ; and have to return as individual columns. I tried with the following query:

SELECT DataID
    ,SUBSTRING(DD,CHARINDEX(';HF:',DD) + LEN(';HF:'),CHARINDEX(';HM:',DD) - (CHARINDEX(';HF:',DD) + LEN(';HF:'))) as HF
    ,SUBSTRING(DD,CHARINDEX(';HM:',DD) + LEN(';HM:'),CHARINDEX(';HN:',DD) - (CHARINDEX(';HM:',DD) + LEN(';HM:'))) as HM
    ,SUBSTRING(DD,CHARINDEX(';HN:',DD) + LEN(';HN:'),CHARINDEX(';PN:',DD) - (CHARINDEX(';HN:',DD) + LEN(';HN:'))) as HN
    ,SUBSTRING(DD,CHARINDEX(';PN:',DD) + LEN(';PN:'),CHARINDEX(';PVD:',DD) - (CHARINDEX(';PN:',DD) + LEN(';PN:'))) as PN
    ,SUBSTRING(DD,CHARINDEX(';PVD:',DD) + LEN(';PVD:'),CHARINDEX(';PVR:',DD) - (CHARINDEX(';PVD:',DD) + LEN(';PVD:'))) as PVD
    ,SUBSTRING(DD,CHARINDEX(';PVR:',DD) + LEN(';PVR:'),CHARINDEX(';BN:',DD) - (CHARINDEX(';PVR:',DD) + LEN(';PVR:'))) as PVR
    ,SUBSTRING(DD,CHARINDEX(';BN:',DD) + LEN(';BN:'),CHARINDEX(';BVD:',DD) - (CHARINDEX(';BN:',DD) + LEN(';BN:'))) as BN
    ,SUBSTRING(DD,CHARINDEX(';BVD:',DD) + LEN(';BVD:'),CHARINDEX(';BVR:',DD) - (CHARINDEX(';BVD:',DD) + LEN(';BVD:'))) as BVD
    ,SUBSTRING(DD,CHARINDEX(';BVR:',DD) + LEN(';BVR:'),LEN(DD) - (CHARINDEX(';BVR:',DD) + LEN(';BVR:'))) as BVR
FROM DataTable
WHERE DD is not null

I think I'll have to generate the query at run-time from a list of column names or may have hard-coded query as the structure of the data and the required columns is not likely to change.

Given that, is there a better approach to optimize this query? May be by using Regular Expressions or any other approach?

Edit:

Is there a better approach using C# Code-behind? This eventually is being used for an ASP.Net Web Application.

Basically, sql is not meant to parse text.  The database design is the issue here and it probably needs to be modified.  Another option is to return the string to the server and do the parsing there and then make another call to sql.

My answer is basically a copy of Andrew White's answer to this stackoverflow question.


A function which translates a sentence to title-case The task is to write a JavaScript-function which translates a given blank-separated sentence to title-case.

Means that all words shall start with a capital and then the rest of the word in lower-case. But: A certain, specified set of conjunctions, preposition as well as article shall be all lower-case.

Example: "The second of the four items." becomes "The Second of the Four Items.".

Here's my implementation of such a function:

function translateToTitleCase(str) {
  const translateWord = (sWord) => {
    return sWord.slice(0, 1).toUpperCase() + sWord.slice(1).toLowerCase();
  }

  const words = str.split(" ");

  words[0] = translateWord(words[0]);

  for (let i = 1; i < words.length; i++) {
    if (!["of", "and", "the", "to"].includes(words[i].toLowerCase())) {
      words[i] = translateWord(words[i]);
    } else {
      words[i] = words[i].toLowerCase(); // Make sure is's the correct case, when the sentence (or parts of it) is given in uppercase.
    }
  }

  return words.join(" ");
}

// -- Examples -------------------------------------------------------------------------------
console.log(translateToTitleCase("Into unmerciful the entreating stronger to of word guessing."));
console.log(translateToTitleCase("the OLD MAN aND THE sEa"));

I think my coding is still a bit "noisy" with the usage of all those brackets, chained methods and concatenation.

Any ideas about how to improve my implementation?

Perhaps some cool new ES6-feature I wasn't aware of.

What would you have done differently and why?

I find this code quite reasonable on the whole, but you might consider the following suggestions relating to consistency, succinctness and semantics.

Move and rename the inner helper function

translateWord is reusable as a general utility function and seems better-placed in the global scope and renamed to titleCase. This meshes with similarly-named Ruby, Python and PHP builtins (titlecase, title, ucfirst, respectively). When I see "translate", I think of linguistics or mathematics before I think of strings or casing.

Avoid excessive calls to toLowerCase

.toLowerCase() is more efficient called once on the entire sentence before splitting rather than incurring the overhead of calling it multiple times per word. With this in mind, you can skip calling the titleCase function described above if you wish.

Improve "ignore" list

if (!["of", "and", "the", "to"].includes(words[i].toLowerCase())) {

is problematic for a few reasons:

It creates a new array object for every word. Move initialization to the top of the function and create it once.
Hardcoding restricts your function's reusability. Making this ignore list a default parameter allows the client to adjust the list as needed.
Giving this array a variable name makes its purpose more obvious.
Although the array is small, it needs to be traversed linearly to perform a lookup; using a set improves semantics, readability and time complexity all at once and is the ideal structure for testing membership.

Avoid the loop

This task is a map operation: each word has a function applied to it. You can roll split, map (your for loop) and join into one call to replace, which takes a regular expression that splits on non-word characters and applies the titleCase function to each one that passes the ignore test.

Minor points

sWord.slice(0, 1) can be sWord[0].
sWord is an okay variable name, but str (matching your outer function) or word seems more consistent.
Unless there is a good hoisting or context reason, I'd make the outer function also use an arrow function for consistency with your inner function.

A rewrite

const titleCaseWords = (words, ignore=["of", "and", "the", "to"]) => {
  ignore = new Set(ignore);

  return words.replace(/\w+/g, (word, i) => {
    word = word.toLowerCase();

    if (i && ignore.has(word)) {
      return word;
    }

    return word[0].toUpperCase() + word.slice(1);
  });
};

[
  "Into unmerciful the entreating stronger to of word guessing.",
  "the OLD MAN aND THE sEa"
].forEach(test => console.log(titleCaseWords(test)));


Which solution is good to generate a list without None results from a function? I'm relatively new to Python and learned, that function cannot return nothing, not even None. In my application I want to iterate over a list and keep all non-None results of a complicated function:

def complicated_function(x):
    if x < 0:
        return "a"
    elif x == 3.6:
        return "b"
    elif x == 4:
        return None  # Idealy here nothing should be returned
    elif x > 10:
        return "c"
    else:
        return "d"

I have three soltuions and my question is which would you recommend me to use and are there better ones?

First solution

tmp = [complicated_function(x) for x in [-1, 2, 3.6, 4, 5, 20]]
ret = [x for x in tmp if x]

Second solution

ret = [complicated_function(x) for x in [-1, 2, 3.6, 4, 5, 20] if complicated_function(x)]

Third solution

ret = []
for x in [-1, 2, 3.6, 4, 5, 20]:
    tmp = complicated_function(x)
    if tmp:
        ret.append(tmp)

I think the first solution is slow, if the list to iterate over is very large. The second solution seems to be bad if the complated_function is really expensive (in rumtime). The third solution seems to be ok, but append is said to be significantly slower than list comprehension.

You can use an intermediate generator function:

[y for y in (complicated_function(x) for x in <my_iterable>) if y is not None]

An alternative is changing complicated_function to become a generator that accepts an iterable, instead of a pure function:

def complicated_function(iterable):
    for x in iterable:
        if x < 0:
            yield "a"
        elif x == 3.6:
            yield "b"
        elif x == 4:
            continue
        elif x > 10:
            yield "c"
        else:
            yield "d"

and then: list(complicated_function(<my_iterable>))


Refactoring from if-else-if to Dictionary I have come across the following piece of code

 if (Region.Current == Region.EU)
    {
      return RegionalPriceLN;
    }
    else if (Region.Current == Region.NY)
    {
      return RegionalPriceNY;
    }
    else if (Region.Current == Region.HK)
    {
      return RegionalPriceHK;
    }
    else if (Region.Current == Region.TK)
    {
      return RegionalPriceTK;
    }

    return null;

And want to refactor it to use a Dictionary. Was thinking of something like below:

return Map.TryGetValue(Region.Current, out func) ? func() : null;

And the dictionary being initialized like this:

 Map = new Dictionary<Region, Func<double?>>
                             {
                               {Region.EU, () => RegionalPriceLN},
                               {Region.NY, () => RegionalPriceNY},
                               {Region.HK, () => RegionalPriceHK},
                               {Region.TK, () => RegionalPriceTK}
                             };

Another approach, to optimize memory usage would be to hold a static dictionary instead of an instance one:

private static readonly Dictionary<Region, Func<TickingBasket, double?>> Map = new Dictionary<Region, Func<TickingBasket,double?>>
                             {
                               {Region.EU, t_ => t_.RegionalPriceLN},
                               {Region.NY, t_ => t_.RegionalPriceNY},
                               {Region.HK, t_ => t_.RegionalPriceHK},
                               {Region.TK, t_ => t_.RegionalPriceTK}
                             };

This would require for us to pass "this" to the delegate:

return Map.TryGetValue(Region.Current, out func) ? func(this) : null;

Can you think of a more elegant way to do this?

Regards.

UPDATE: Region is a reference type.

Second option is definitely a preferred way over first one. Also you may consider a switch statement.

UPDATE. Since Region is a class then the only good way to avoid long if...else is the mapping like in your second variant

First option that you proposed (Map = new Dictionary<Region, Func<double?>>) requires the construction of Dictionary each time the method is executed. It is a waste of resources and time, and for this case even the if..else..if..else statements don't look that ugly :).

Second option (static Dictionary with fixed mappings) is a traditional way to branch the logic for your case. Moreover in certain cases C# compiler will compile the switch statement into static Dictionary to run lookups.


TPL inside Windows Service I need to perform few tasks inside a Windows Service I am writing in parallel. I am using VS2013, .NET 4.5 and this post shows that TPL is the way to go.

I was wondering if anyone can tell me if I have done it correctly.

public partial class FtpLink : ServiceBase
{
    private readonly CancellationTokenSource _cancellationTokenSource = new CancellationTokenSource();
    private readonly ManualResetEvent _runCompleteEvent = new ManualResetEvent(false);

    public FtpLink()
    {
        InitializeComponent();

        // Load configuration
        WebEnvironment.Instance.Initialise();
    }

    protected override void OnStart(string[] args)
    {
        Trace.TraceInformation("DatabaseToFtp is running");

        try
        {
            RunAsync(_cancellationTokenSource.Token).Wait();
        }
        finally
        {
            _runCompleteEvent.Set();
        }
    }

    protected override void OnStop()
    {
        Trace.TraceInformation("DatabaseToFtp is stopping");

        _cancellationTokenSource.Cancel();
        _runCompleteEvent.WaitOne();

        Trace.TraceInformation("DatabaseToFtp has stopped");
    }

    private async Task RunAsync(CancellationToken cancellationToken)
    {
        while (!cancellationToken.IsCancellationRequested)
        {
            Trace.TraceInformation("Working");

            // Do the actual work
            var tasks = new List<Task>
            {
                Task.Factory.StartNew(() => new Processor().ProcessMessageFiles(), cancellationToken),
                Task.Factory.StartNew(() => new Processor().ProcessFirmware(), cancellationToken)
            };

            Task.WaitAll(tasks.ToArray(), cancellationToken);

            // Delay the loop for a certain time
            await Task.Delay(WebEnvironment.Instance.DatabasePollInterval, cancellationToken);
        }
    }
}

The general design of your example is correct, however there are some problems with how you have implemented the async code. Most notibly

Calling .Wait() on the Task returned by RunAsync() will block 'OnStart()'. Instead it should be done after cancellation in the OnStop() method. This would eliminate the need to use a ManualResetEvent
Task.WaitAll() should be replace with await Task.WhenAll()

More importantly you can achieve the desired behaviour much more simply by using a System.Threading.Timer. The TPL is needed only to perform parallel processing.

public partial class FtpLink : ServiceBase
{
    private Timer _timer;

    public FtpLink()
    {
        WebEnvironment.Instance.Initialise();
    }

    protected override void OnStart(string[] args)
    {
        Trace.TraceInformation("DatabaseToFtp service started.");
        _timer = new Timer(Process, null, 0, WebEnvironment.Instance.DatabasePollInterval);
    }

    protected override void OnStop()
    {
        _timer.Dispose();
        Trace.TraceInformation("DatabaseToFtp service stopped.");
    }

    private void Process(object state)
    {
        Trace.TraceInformation("Processing message files and firmware...");

        Parallel.Invoke(
            () => new Processor().ProcessMessageFiles(),
            () => new Processor().ProcessFirmware());

        Trace.TraceInformation("Processing complete.");
    }
}

If you want to ensure that the service waits for processing to complete before exiting, you can use a simple Monitor as shown in the answer to this question.


Link shortener application - return the "following" string I'm working on developing an application to shorten links. Part of that requires me to be able to get the "next" string based on an allowed character ranges, as if we were counting up. Characters go from A-Z to a-z to 0-9. Some samples:

"A" => "B"
"AA" => "AB"
"AZ" => "Aa"
"Az" => "A0"
"A9" => "BA"
"999" => "AAAA"

I've written a small class to accomplish this. My main concerns are the way I've hard-coded the ranges, and I'm not sure if doing this recursively made the most sense.

package proceduralstring;

/**
 * Char succession: A-Z a-z 0-9
 * @author User
 *
 */
public class ProceduralStringCreator {

    public static String getFirst(){
        return "A";
    }

    public static String getFirst(int minLength){
        StringBuilder result = new StringBuilder();
        for(int i=0; i<minLength; i++){
            result.append("A");
        }
        return result.toString();
    }

    public static String getNext(String current) throws BadFormatException{
        if(!current.matches("[a-zA-Z0-9]+")){
            throw new BadFormatException("String contains illegal characters.");
        }
        if(current.matches("9{"+current.length()+"}")){
            return getFirst(current.length()+1);
        }
        StringBuilder result = new StringBuilder(current);
        replaceWithNext(result, result.length()-1);
        return result.toString();
    }

    private static StringBuilder replaceWithNext(StringBuilder toReplace, int index){
        char currentChar = toReplace.charAt(index);
        if(currentChar != '9'){ //base case
            if(currentChar != 'z' && currentChar != 'Z'){
                toReplace.replace(index, index+1, ((char)(currentChar+1))+"");
            }else{
                if(currentChar == 'z'){
                    toReplace.replace(index, index+1, "0");
                }else if(currentChar == 'Z'){
                    toReplace.replace(index, index+1, "a");
                }
            }
            return toReplace;
        }else{ //recursive case
            toReplace.replace(index, index+1, "A");
            return replaceWithNext(toReplace, index-1);
        }
    }
}

The code is tested and works as intended (the exception is the desired behavior, as there is an invalid character):

package proceduralstring;

public class ProcStringTest {

    public static void main(String[] args) throws BadFormatException {
        System.out.println("getFirst: "+ProceduralStringCreator.getFirst());
        System.out.println("getFirst(5): "+ProceduralStringCreator.getFirst(5));
        System.out.println("Next of A: "+ProceduralStringCreator.getNext("A"));
        System.out.println("Next of AA: "+ProceduralStringCreator.getNext("AA"));
        System.out.println("Next of AAA: "+ProceduralStringCreator.getNext("AAA"));
        System.out.println("Next of A9: "+ProceduralStringCreator.getNext("A9"));
        System.out.println("Next of Adhs3hdfh9: "+ProceduralStringCreator.getNext("Adhs3hdfh9"));
        System.out.println("Next of 9: "+ProceduralStringCreator.getNext("9"));
        System.out.println("Next of 99: "+ProceduralStringCreator.getNext("99"));
        System.out.println("Next of Aas9s99: "+ProceduralStringCreator.getNext("Aas9s99"));
        System.out.println("Next of 9z9999: "+ProceduralStringCreator.getNext("9z9999"));
        System.out.println("Next of 9Z9999: "+ProceduralStringCreator.getNext("9Z9999"));
        System.out.println("Next of AUHR(#H: "+ProceduralStringCreator.getNext("AUHR(#H"));
    }

}

Output:

getFirst: A
getFirst(5): AAAAA
Next of A: B
Next of AA: AB
Next of AAA: AAB
Next of A9: BA
Next of Adhs3hdfh9: Adhs3hdfiA
Next of 9: AA
Next of 99: AAA
Next of Aas9s99: Aas9tAA
Next of 9z9999: 90AAAA
Next of 9Z9999: 9aAAAA
Exception in thread "main" proceduralstring.BadFormatException: String contains illegal characters.
    at proceduralstring.ProceduralStringCreator.getNext(ProceduralStringCreator.java:24)
    at proceduralstring.ProcStringTest.main(ProcStringTest.java:18)
Picked up JAVA_TOOL_OPTIONS: -Duser.language=en

Consider wrapping getFirst() into getNext(String) - just have it return "A" if it takes in a null or empty string. That might make it a little easier for the client to use.
getFirst(int) can leverage Arrays.fill(), which will make it a little easier to read. Consider throwing an exception if the minLength is less than zero - otherwise you get an empty string returned. Another option would be to return "A".
The core problem can be solved non-recursively. A helper method to return the next character would be, well, helpful, and easier to read than what you're doing now. The math gets done inside the loop, and you prepend an 'A' if appropriate.
You might want to make 'A' a constant, since it's special.

If you make the changes I suggest, your code might look something like:

import java.util.Arrays;
import java.util.regex.Pattern;

public class ProceduralStringCreator {

    private static final Pattern VALID = Pattern.compile("[a-zA-Z0-9]+");
    private static final char FIRST_CHARACTER = 'A';

    public static String next(final int size) {
        if (size < 0) {
            throw new IllegalArgumentException("Size must be greater than or equal to zero, was " + size);
        }
        final char[] value = new char[size];
        Arrays.fill(value, FIRST_CHARACTER);
        return new String(value);
    }

    public static String next(final String current) throws BadFormatException {
        if (current == null || current.isEmpty()) {
            return Character.toString(FIRST_CHARACTER);
        }

        if (!VALID.matcher(current).matches()) {
            throw new BadFormatException("String contains illegal characters.");
        }

        final StringBuilder stringBuilder = new StringBuilder(current);
        int index = stringBuilder.length();

        do {
            index--;
            stringBuilder.setCharAt(index, nextCharacter(stringBuilder.charAt(index)));
        } while ((index >= 1) && (stringBuilder.charAt(index) == FIRST_CHARACTER));

        if ((index == 0) && (stringBuilder.charAt(index) == FIRST_CHARACTER)) {
            stringBuilder.insert(0, FIRST_CHARACTER);
        }

        return stringBuilder.toString();
    }

    private static char nextCharacter(final char character) {
        switch (character) {
        case 'Z':
            return 'a';
        case 'z':
            return '0';
        case '9':
            return 'A';
        default :
            return (char) (character + 1);
        }
    }

}


An overloaded random number function template using modern C++ I don't mess around a lot with templates (or with GTK), but today I wrote something and would like to know how it can be improved, and hopefully clarify a few things in the process.

So, Randolfi() is a function template which returns a random number. A range can be specified as arguments.

It uses features new to C++11, based on these:

How to generate a random number in C++?
Random number generation in C++11 , how to generate , how do they work?

(The name "Randolfi" is a joke made by a few colleagues regarding my last name, Ranolfi.)

randolfi.hpp

#ifndef RANDOLFI_HPP
#define RANDOLFI_HPP

#include <random>

template <typename T>
T Randolfi()
{
    std::mt19937 rng;
    rng.seed( std::random_device()() );
    std::uniform_int_distribution<T> dist;
    return dist(rng);
}

template <typename T>
T Randolfi(T range_start, T range_end)
{
    std::mt19937 rng;
    rng.seed( std::random_device()() );
    std::uniform_int_distribution<T> dist(range_start, range_end);
    return dist(rng);
}

#endif //RANDOLFI_HPP

randolfi-test.cpp

#include <iostream>
#include <string>
#include <gtkmm.h>
#include "randolfi.hpp"

using namespace std;

int main()
{
    auto app = Gtk::Application::create();

    uint a_random_number = Randolfi<uint>();

    Gtk::MessageDialog dialog( to_string(a_random_number) );
    dialog.run();

    return 0;
}

Notes:

Somehow it doesn't feel right to have such a large proportion of redundant lines across the function overloads. I think there might be a template-related trick to help here, but searching for it proved useless since all the results I found (like this one) are concerned about type parameter overloading, which is not my case.
I though about declaring it as Randolfi(T range_start = NULL, T range_end = NULL) and then checking if (range_start != NULL && range_end != NULL), but that does not save me any lines, and also appears to be frowned upon.
As it is, the function can be called without type argument for the second overload, but not for the first one:

Randolfi(0, 100);  // type parameter ommited for template
Randolfi();  // Fails - compiler has no clue on know how to instantiate template

I have a feeling this inconsistency is bad practice.
I'm mostly concerned about the template header, but I did include my testing code (randolfi-test.cpp) to this question so maybe someone can let me know if I did something terribly wrong. From my part, I'd like to avoid calling Gtk::Application::create() but that doesn't seem to be possible.

Thanks!

The constructor of uniform_int_distribution has default arguments:
template<typename T>
explicit uniform_int_distribution(T a = 0,
                                  T b = std::numeric_limits<T>::max());

(I don't know why a defaults to 0 rather than to the minimum T, but there you go).
You can reduce your duplication by using the same default arguments, and passing them through to this constructor:
template <typename T>
T Randolfi(T range_start = 0,
           T range_end = std::numeric_limits<T>::max())
{
    std::uniform_int_distribution<T> dist(range_start, range_end);
    return dist(rng);
}

Or, we can use perfect forwarding to create the distribution with the same arguments as passed in:
template <typename T, typename... Args>
T Randolfi(Args&&... args)
{
    std::uniform_int_distribution<T> dist(std::forward<Args>(args)...);
    return dist(rng);
}

We'll need to do this if we want to support a variety of distributions, so it's probably the way to go.

Don't recreate a random generator every call.  You could make it static, which will reduce that to once per instantiation, but it's better to keep it outside of the function, so you only create and seed it once per process.
In the test program, you should exercise more than one type T, and test with implicit and explicit range.  Also, avoid using namespace std;, and prefer tests which don't require a GUI environment (so they can be more easily run on build servers).

Modified code
#include <limits>
#include <random>
#include <utility>

static auto rng = []{
    std::mt19937 rng;
    rng.seed(std::random_device()());
    return rng;
}();

template <typename T,
          template<typename> typename Distribution
                                      = std::uniform_int_distribution,
          typename... Args>
T Randolfi(Args&&... args)
{
    Distribution<T> dist(std::forward<Args>(args)...);
    return dist(rng);
}

#include <iostream>

int main()
{
    std::clog << Randolfi<int>(-100, +100) << '\n'
              << Randolfi<char>('a', 'z') << '\n'
              << Randolfi<double, std::normal_distribution>(100, 15) << '\n'
              << Randolfi<std::size_t>() << std::endl;
}


Find if a word with wildcard exists in dictionary This is a question from a phone interview I had.

The question was in 2 parts:

  a. find("cat") -> T/F suggest a data structure to find is if a word
  exists in a large dictionary, how will one node of that data structure
  will look like?

  b. Implement a bool Find(string str) function which returns true or
  false if the word exists or not, and also supports "?" wildcard which
  can occur more than once.

    O
a    b     c    d   e
  a      b
b   r  t
    r    e
    o     r
    t

This is the final answer I have arrived with the interviewer:

public class TreeNode {
    public HashSet<TreeNode> Nodes {get;set;} // 26 children
    public HashSet<char> Index {get;set;}
    public bool EndOfWord {get;set;}
}

public bool Find(string str, TreeNode root, int currentIndex)
{
    if (str.IsNullOrEmpty() || root == null || currentIndex < 0)
    {
        return false;
    }

    if( currentIndex == str.Length )
    {
        return root.EndOfWord;
    }

    if(str[currentIndex] == '?')
    {
        for(int i=0; i< root.Nodes.Count ; i++)
        {
            if(root.Nodes[i] == null)
            {
                continue;
            }
            if (Find(str, root.Nodes[str[currentIndex]], currentIndex+1))
            {
                return true;
            }
        }
        return false;
    }
    else
    {
        if (root.Index.Contains(str[currentIndex]))
        {
            return Find(str, root.Nodes[str[currentIndex]], currentIndex+1);
        }
        else
        {
            return false;
        }
    }
}

Please suggests any data structure you can think of. I thought of using a suffix tree and tried to implement it.

Please suggest any other implementation for the Find() function and let me know if this is an interview where are the mistakes in my code. Complexity, code checking, naming, style, ...and so on. I didn't pass the interview and I'm trying to learn from this.

At first: This is a really nice question for an interview. You can show off your knowledge of data structures and algorithms here, but you can also demonstrate how familiar you are with your programming language and concepts like test driven development for example.

So, what went wrong here? At the first sight, your solution looks "ok". If you look a little closer, there are some issues:

Data Structures

You were pretty spot on when choosing a tree here. You could have done a little better by calling it with its common name, Trie. That comes from retrieval and is described in detail over here.

This data structure in its simplest form (we don't need any more for solving your problem) consists of trie nodes that have 1.) children where each child is assigned a character and 2.) a marker if this node is the last character of a word (so that we can distinguish a prefix of a word and a complete word).

You tried printing a graph as an example, which unfortunately got lost in formatting. Here is one from Wikipedia:

In your solution, you have used two HashSets (of TreeNodes and chars). I don't understand what the Index set is for, as you didn't include your code for adding nodes. The bigger problem I see here is the type HashSet itself: They describe unordered lists of stuff ("sets"), and you are trying to access them using an indexer (e.g. root.Nodes[str[currentIndex]]). This will not only give unpredicted results, it won't even compile. There is no indexer on HashSet.

What you actually want to use here is a Dictionary. Looking at the graph above, we seem to be navigating along using characters. That means, in every node, having one character we can determine the next node to go to. A dictionary can do that for us.

The whole thing

Rather than trying to come up with some working code during the interview, I would have talked about the architectural and algorithmic features of the to-be-built solution. I guess, if you had written out some unit tests that specify the behavior of the system it would have come out better than writing code that obviously won't even compile.

Let's see how we can easily build the whole thing using TDD (Test Driven Development), writing tests first and then bringing them from red to green by developing and refactoring our Trie.

Please create an empty Unit Test Project and create a new file in there. Add the NuGet package "FluentAssertions". You can paste each method stepwise to see how the solution matures. If there is a [TestMethod] attribute above, add it to the TrieTests class. If there is no attribute, add or update the method in TrieNode.

We start with:

[TestClass]
public class TrieTests
{
    private readonly TrieNode trie = new TrieNode();

    [TestMethod]
    public void AddingDoesntThrow()
    {
        this.trie.Add("word");
    }
}

public class TrieNode
{
    public void Add(string blah)
    {
        throw new NotImplementedException();
    }
}

Ok. We need to add stuff to the trie, so we have an Add. Test will be red. Update Add method:

    public void Add(string blah)
    {
    }

Bam, test is green now. Next one! (Don't do more that you need to make your test green. Deleting the NotImplementedException is enough for now.)

    [TestMethod]
    public void FindEmptyString()
    {
        this.trie.Add("");
        this.trie.Find("").Should().BeTrue();
    }

    public bool Find(string query)
    {
        throw new NotImplementedException();
    }

Test is red.

    public bool Find(string query)
    {
        return true;
    }

Test is green! But wait. What if there is nothing in the trie?

    [TestMethod]
    public void FindInEmptyTrieReturnsFalse()
    {
        this.trie.Find("").Should().BeFalse();
    }

Test is red, because we have no logic at all. Let's add the isWord boolean field and use it:

public class TrieNode
{
    private bool isWord;

    public void Add(string s)
    {
        if (s.Length == 0)
        {
            this.isWord = true;
        }
    }

    public bool Find(string query)
    {
        if (query.Length == 0)
        {
            return this.isWord;
        }

        return false;
    }
}

Okay, our trie works with empty strings! What happens if somebody passes null?

    [TestMethod]
    public void FindWithNullQueryThrows()
    {
        Action find = () => this.trie.Find(null);
        find.ShouldThrow<ArgumentNullException>();
    }

Test is red. We need to check the argument and throw an exception:

    public bool Find(string query)
    {
        if (query == null)
        {
            throw new ArgumentNullException("query");
        }

        if (query.Length == 0)
        {
            return this.isWord;
        }

        return false;
    }

Let's add support for real words now:

    [TestMethod]
    public void FindWordReturnsTrue()
    {
        this.trie.Add("word");
        this.trie.Find("word").Should().BeTrue();
    }

This is the tricky part. To make this work, we have to add the aforementioned dictionary of child nodes. Adding "word" creates child nodes for each character; finding "word" checks if the next child node exists and recurses down the tree: A trie node finds "word" if it has a child node "w" and this child node finds "ord".

public class TrieNode
{
    private readonly Dictionary<char, TrieNode> children
        = new Dictionary<char, TrieNode>();

    private bool isWord;

    public void Add(string s)
    {
        if (s.Length == 0)
        {
            this.isWord = true;
            return;
        }

        var c = s[0];
        var child = GetOrCreateChild(c);

        child.Add(s.Substring(1));
    }

    private TrieNode GetOrCreateChild(char c)
    {
        TrieNode child;
        if (!children.TryGetValue(c, out child))
        {
            child = new TrieNode();
            children.Add(c, child);
        }

        return child;
    }

    public bool Find(string query)
    {
        if (query == null)
        {
            throw new ArgumentNullException("query");
        }

        if (query.Length == 0)
        {
            return this.isWord;
        }

        var c = query[0];
        var child = this.GetChild(c);

        return child != null && child.Find(s.Substring(1));
    }

    private TrieNode GetChild(char c)
    {
        TrieNode child;
        return this.children.TryGetValue(c, out child) ? child : null;
    }
}

We can even add further tests to check if everything works as expected:

    [TestMethod]
    public void FindLongerWordReturnsTrue()
    {
        this.trie.Add("word");
        this.trie.Add("wording");
        this.trie.Find("wording").Should().BeTrue();
    }

    [TestMethod]
    public void FindPrefixReturnsFalse()
    {
        this.trie.Add("word");
        this.trie.Find("wor").Should().BeFalse();
    }

Both green already! Now we still have something to do: We need the wildcard support.

    [TestMethod]
    public void FindWithWildcardReturnsTrue()
    {
        this.trie.Add("word");
        this.trie.Find("w??d").Should().BeTrue();
    }

Instead of looking for one child node, a "?" means looking in all child nodes. We can generalize that: GetChild(char) gets renamed to GetChildren(char) and returns an IEnumerable:

public class TrieNode
{
    private readonly Dictionary<char, TrieNode> children
        = new Dictionary<char, TrieNode>();

    private bool isWord;

    public void Add(string s)
    {
        if (s.Length == 0)
        {
            this.isWord = true;
            return;
        }

        var c = s[0];
        var child = GetOrCreateChild(c);

        child.Add(s.Substring(1));
    }

    private TrieNode GetOrCreateChild(char c)
    {
        TrieNode child;
        if (!children.TryGetValue(c, out child))
        {
            child = new TrieNode();
            children.Add(c, child);
        }

        return child;
    }

    public bool Find(string query)
    {
        if (query == null)
        {
            throw new ArgumentNullException("query");
        }

        if (query.Length == 0)
        {
            return this.isWord;
        }

        var c = query[0];
        var child = this.GetChildren(c);

        return child.Any(x => x.Find(query.Substring(1)));
    }

    private IEnumerable<TrieNode> GetChildren(char c)
    {
        if (c == '?')
            return this.children.Values;

        TrieNode child;
        return this.children.TryGetValue(c, out child)
            ? new[] { child }
            : Enumerable.Empty<TrieNode>();
    }
}

You could add additional features like a collection of values for each trie node or prefix search, but I guess this simple implementation would have solved your question.


Group collections by their elements property I have a Customer class:

public class Customer
{
    public Guid Id { get; set; }
    // Some other properties...}

And three transactions classes that have a reference to Customer:

public class Order
{
    public Guid CustomerId { get; set; }
    // Some other properties...}

public class Invoice
{
    public Guid CustomerId { get; set; }
    // Some other properties...}

public class Payment
{
    public Guid CustomerId { get; set; }
    // Some other properties...}

I have a collection for each of transaction type. And I want to get this collection to be "grouped" by their elements CustomerId properties. So, as a result I'd like to get a collection of such objects:

public class CustomerInfo
{
    public CustomerInfo(Guid customerId, IEnumerable<Order> orders,
        IEnumerable<Invoice> invoices, IEnumerable<Payment> payments){...}

    public Guid CustomerId { get; set; }
    public IEnumerable<Invoice> Invoices { get; set; }
    public IEnumerable<Order> Orders { get; set; }
    public IEnumerable<Payment> Payments { get; set; }
}

Right now I am doing so by this function:

private IEnumerable<CustomerInfo> _GetCustomerInfo(
    IEnumerable<Payment> payments, IEnumerable<Invoice> invoices,
    IEnumerable<Order> orders)
{
    var invoicesGroupdByCustomers = invoices.GroupBy(x => x.CustomerId);
    var ordersGroupdByCustomers = orders.GroupBy(x => x.CustomerId);
    var paymentsGroupdByCustomers = payments.GroupBy(x => x.CustomerId);

    var result = new List<CustomerInfo>();
    foreach (var group in invoicesGroupdByCustomers)
        result.Add(new CustomerInfo(group.Key,
            ordersGroupdByCustomers.FirstOrDefault(x => x.Key == group.Key),
            group,
            paymentsGroupdByCustomers.FirstOrDefault(x => x.Key == group.Key)));

    foreach (var group in ordersGroupdByCustomers)
        if (!result.Any(x => x.CustomerId == group.Key))
            result.Add(new CustomerInfo(group.Key,
                group,
                invoicesGroupdByCustomers.FirstOrDefault(x => x.Key == group.Key),
                paymentsGroupdByCustomers.FirstOrDefault(x => x.Key == group.Key)));

    foreach (var group in paymentsGroupdByCustomers)
        if (!result.Any(x => x.CustomerId == group.Key))
            result.Add(new CustomerInfo(group.Key,
                ordersGroupdByCustomers.FirstOrDefault(x => x.Key == group.Key),
                invoicesGroupdByCustomers.FirstOrDefault(x => x.Key == group.Key),
                group));

    return result;
}

Here is sample of calculations where I use these transactions collections:

private Dictionary<Guid, decimal> _CalculateSales(
    IEnumerable<CustomerInfo> customersSalesInfo)
{
    var result = new Dictionary<Guid, decimal>();

    foreach (var customerInfo in customersSalesInfo)
    {
        var sales = customerInfo.Invoices.Sum(x => x.Header.SubTotalAmt) +
            customerInfo.Orders.Sum(x => x.Header.SubTotalAmt) -
            customerInfo.Payments.Sum(x => x.Header.SubTotalAmt);
        result.Add(customerInfo.CustomerId, sales);
    }

    return result;
}

Is there a better approach?

If they all implemented a common interface then you could simplify it.

 public interface ICustomerItem
    {
        Guid CustomerId {get;}
     }

Concat the the items together

var items = invoices.Concat(payments).Concat(orders);

Then project them into your class

 items
.GroupBy(x => x.CustomerId)
.Select(g =>
          new CustomerInfo(g.Key,
                 g.OfType<Order>(),
                 g.OfType<Payment>(),
                 g.OfType<Invoice>())


PHP MVC controller code needs diet? This is the dashboard controller code in PHP Symfony 2. It collects some aggregate data and points for charts, but i don't like it very much. Do you think that this code belongs to what a controller should do in a MVC patter? How can i refactor it?

public function dashboardAction()
{
    $bag = array();

    // Helpers from service container
    $messaging = $this->get('messaging.helper');
    $charting  = $this->get('charting.helper');

    // Current logged user, subscription and message inhibitor
    $loggedUser   = $this->getSecurityContext()->getToken()->getUser();
    $subscription = $messaging->createSubscriptionFromUser($loggedUser);
    $usage        = $messaging->createUsageFromSubscription($subscription);

    $bag['subscription'] = $subscription;
    $bag['usage']        = $usage;
    $bag['inhibitor']    = $messaging->createInhibitor($usage, $subscription);

    // Get charts from usage raw data
    $rawData = $usage->getRawData();
    $start   = $usage->getStartDate();
    $end     = $usage->getEndDate();

    $bag['line_chart'] = $charting->createMessagesLineChart($rawData, $start, $end);
    $bag['pie_chart']  = $charting->createMessagesPieChart($rawData);

    // Customers and latest 5 added
    $customers = $loggedUser->getCustomers();

    $bag['customers_count']  = $customers->count();
    $bag['latest_customers'] = $customers->slice(0, 5);

    // Tags/keywords counts and latest 5 meta
    $metas       = $loggedUser->getMeta();
    $getTags     = function($m) { return $m instanceof Tag; };
    $getKeywords = function($m) { return $m instanceof Keyword; };

    $bag['tags_count']     = $metas->filter($getTags)->count();
    $bag['keywords_count'] = $metas->filter($getKeywords)->count();
    $bag['latest_meta']    = $metas->slice(0, 5);

    // SMS and newsletter counts
    $outgoingMessages = $loggedUser->getOutgoingMessages();
    $getSms           = function($m) { return $m instanceof SmallTextMessage; };
    $getNewsletters   = function($m) { return $m instanceof Newsletter; };

    $bag['sms_count']        = $outgoingMessages->filter($getSms)->count();
    $bag['newsletter_count'] = $outgoingMessages->filter($getNewsletters)->count();

    return $bag;
}

A controller? No. A model? Sure. Not sure if Symfony defines a controller differently, but this is not what I think of as a controller.

As for refactoring, the easiest way would be to break it up into smaller methods. For instance, right off the bat I see at least 6 different potential methods here. You could create a bunch of smaller methods that returns a part of the bag (messaging, charting, etc...) and then merge them all together. In fact, that's the only real improvement I can see. I feel bad leaving such a short answer, so here's an example of a couple of those smaller methods, which is actually about half that code.

private function getUsageCharts ( $usage ) {
    $rawData = $usage->getRawData();
    $start   = $usage->getStartDate();
    $end     = $usage->getEndDate();

    $line_chart = $charting->createMessagesLineChart($rawData, $start, $end);
    $pie_chart  = $charting->createMessagesPieChart($rawData);

    return compact( 'usage', 'line_chart', 'pie_chart' );
}

private function getMessagingFields( $loggedUser ) {
    $messaging = $this->get('messaging.helper');

    $subscription = $messaging->createSubscriptionFromUser($loggedUser);
    $usage = $messaging->createUsageFromSubscription($subscription);
    $inhibitor = $messaging->createInhibitor($usage, $subscription);

    extract( $this->getUsageCharts( $usage ) );//$line_chart, $pie_chart
    return compact( 'subscription', 'usage', 'inhibitor', 'line_chard', 'pie_chart' );
}

Hope this helps!


Randomly pick a first name from a file I have a very easy question for you guys out there. It's been a while since I took my programming courses (switched majors) but am trying to get my feet wet again.
Objective:
I will be creating a program that will output 10 random full names (and have it be different every time the program is run).  Before I complete it, I'd like some feedback on the first iteration, which just chooses random first names.
Info:
I have a file called firstnames.txt, containing a list of 10 first names.
Premise:
I'm a beginner and I/O really throws me.  I feel this is a basic enough program for me to learn from, and with your advice, I'll be able to copy/paste the same code to get a last name.
Thanks!
Here's what I have so far:
#include <windows.h>
#include <cstdlib>
#include <iostream>
#include <string> //random headers because it's been awhile :P
#include <fstream>
#include <time.h>

using namespace std;

int main()
{
//Variable declarations
int a = 0;
int randNum;

ifstream myFile;
myFile.open("firstnames.txt");
string names[10]; // holds the 10 names in the file.
string randomNames[10];// holds the randomly generated names FROM the file.

while (myFile.good())
{
    getline(myFile, names[a]); // reads the names from the text file, into an array named "names[]."
    a++;
}
for (int i = 0; i < 10; i++)  // makes this program iterate 10 times; giving you 10 random names.
{
    srand( time(NULL) ); // seed for the random number generator.
    randNum = rand() % 10 + 1; // gets a random number between 1, and 10.
    randomNames[i] = names[randNum];
}
for (int i = 0; i < 10; i++)
{
    cout << randomNames[i] << endl; // outputs all 10 names at once.
}

myFile.close();
return EXIT_SUCCESS;
}

My firstnames.txt looks like:
Ryan
John
Daniel
Gavin
Frank
Danielle
Lucy
Sarah
Katie
Nicole

My lastnames.txt will look similar:
Johnson
Lewis
Walker
Robinson
Wood
Thompson
White
Watson
Jackson
Wright

(Another question I guess would be is the way I formatted the names (each name on a new line) a bit over complicated in the text file? Like would it be better/shorter to just separate each name by a space or something?)
Thanks again!

Well, at least you know what's wrong here:

#include <string> //random headers because it's been awhile :P

You actually need: <iostream>, <string>, <ctime> and <cstdlib>.
You are using using namespace std;.
That's a bad idea, read "Why is “using namespace std;” considered bad practice?".
It's safer and more flexible to use a std::vector, though admittedly insignificantly less efficient.

std::vector<std::string> names;

There's no good reason why you first generate all the data and safe it in memory just to dump it all afterwards in one go.
There's a reason while(!found_end) {read_some_more; process_it;} doesn't work:
You only know you have reached the end after you tried to read beyond it.

for (std::string line; std::getline(myFile, line) && !line.empty(); )
    names.push_back(std::move(line));

If you extract the code to read names from a file into a function your code does not only get cleaner, you can also reuse it.
You are re-seeding the old toy-RNG repeatedly in a relatively tight loop. Can you see where that might not be all that great for randomness?

Anyway, C++11 provides far better RNGs in <random>. See "Seed std::mt19937 from std::random_device" for how to properly seed one.
Ending main with return EXIT_SUCCESS; is equivalent to ending it with return 0; which can be omitted (but only for main).

Following my suggestions lets you loose <ctime> and <cstdlib> but adds <vector>, <utility>, <functional>, <random> and <algorithm>.

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <random>
#include <algorithm>

static std::vector<std::string> read_names(const std::string& filename)
{
    std::vector<std::string> names;
    std::ifstream file(filename);
    for(std::string name; std::getline(file, name) && !name.empty(); )
        names.push_back(std::move(name));
    return names;
}

static const std::string& choose_any(
    std::mt19937& rng,
    const std::vector<std::string>& names
) {
    return names[std::uniform_int_distribution<size_t>(0, names.size() - 1)(rng)];
}

static std::mt19937 ProperlySeededRandomEngine()
{
    std::mt19937::result_type random_data[std::mt19937::state_size];
    std::random_device source;
    std::generate(std::begin(random_data), std::end(random_data), std::ref(source));
    std::seed_seq seeds(std::begin(random_data), std::end(random_data));
    std::mt19937 seededEngine (seeds);
    return seededEngine;
}

int main()
{
    auto firstnames = read_names("firstnames.txt");
    auto lastnames = read_names("lastnames.txt");
    auto rng = ProperlySeededRandomEngine();
    for(int i = 0; i < 10; ++i)
        std::cout << choose_any(rng, firstnames) << ' '
            << choose_any(rng, lastnames) << std::endl;
}


Merging sorted linked lists - C++ Problem from hackerrank:

You’re given the pointer to the head nodes of two sorted linked lists.
The data in both lists will be sorted in ascending order. Change the
next pointers to obtain a single, merged linked list which also has
data in ascending order. Either head pointer given may be null meaning
that the corresponding list is empty.
Input Format
You have to complete the Node* MergeLists(Node* headA,
Node* headB) method which takes two arguments - the heads of the two
sorted linked lists to merge. You should NOT read any input from
stdin/console.
Output Format
Change the next pointer of individual nodes so that
nodes from both lists are merged into a single list. Then return the
head of this merged list. Do NOT print anything to stdout/console.
Sample Input
1 -> 3 -> 5 -> 6 -> NULL
2 -> 4 -> 7 -> NULL

15 -> NULL
12 -> NULL

NULL
1 -> 2 -> NULL

Sample Output
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
12 -> 15 -> NULL
1 -> 2 -> NULL

/*
Merge two sorted lists A and B as one linked list
Node is defined as
struct Node
{
 int data;
 struct Node *next;
}
*/
Node* MergeLists(Node *headA, Node* headB)
{
// This is a "method-only" submission.
// You only need to complete this method
if(headA == NULL)
  return headB;
if(headB == NULL)
  return headA;

Node* temp1;
Node* temp2;
Node* originalHead;
Node* head = new Node;
head->data = 0;
head->next = 0;
//temp1 should always point to head with smaller value
if(headA->data <= headB->data)
{
  temp1 = headA;
  originalHead = headA;
  temp2 = headB;
}
else
{
  originalHead = headB;
  temp1 = headB;
  temp2 = headA;
}
while(temp1 != 0 && temp2 != 0)
{
    if(temp1->data <= temp2->data){
        head->next = temp1;
        head = temp1;
        if(temp1->next != NULL)
            temp1 = temp1->next;
        else{
            head->next = temp2;
            break;
        }
    }
    else{
        head->next = temp2;
        head = temp2;
        if(temp2->next != NULL)
            temp2 = temp2->next;
        else{
            head->next = temp1;
            break;
        }
    }
}
return originalHead;
}

Simplify

In this loop, the loop condition is practically useless:

while(temp1 != 0 && temp2 != 0)
{
    if(temp1->data <= temp2->data){
        head->next = temp1;
        head = temp1;
        if(temp1->next != NULL)
            temp1 = temp1->next;
        else{
            head->next = temp2;
            break;
        }
    }
    else{
        head->next = temp2;
        head = temp2;
        if(temp2->next != NULL)
            temp2 = temp2->next;
        else{
            head->next = temp1;
            break;
        }
    }
}

The statements before the loop have already checked that temp1 and temp2 are not null. So the condition will be true for the first time.
Then in each cycle, you check if the next value of temp1 or temp2 will be null and if yes then break out. So you could as well change the loop condition to while (true), and the program will still work.

But instead of doing that,
it would be simpler to move those checks out of the loop body,
and let the loop condition be useful:

do {
    if (temp1->data <= temp2->data) {
        head->next = temp1;
        head = temp1;
        temp1 = temp1->next;
    } else {
        head->next = temp2;
        head = temp2;
        temp2 = temp2->next;
    }
} while (temp1 != NULL && temp2 != NULL);

head->next = temp1 != NULL ? temp1 : temp2;

Taking it one step further, head can be updated outside of the if-else, like this:

do {
    if (temp1->data <= temp2->data) {
        head->next = temp1;
        temp1 = temp1->next;
    } else {
        head->next = temp2;
        temp2 = temp2->next;
    }
    head = head->next;
} while (temp1 != NULL && temp2 != NULL);

head->next = temp1 != NULL ? temp1 : temp2;

You have this comment:

//temp1 should always point to head with smaller value

Nope, not really! This would work just as well:

if(headA->data <= headB->data) {
  originalHead = headA;
} else {
  originalHead = headB;
}
temp1 = headA;
temp2 = headB;

Memory management

You created a new Node for head, but you forgot to delete it.

Suggested implementation

Some further simplifications and improvements are possible:

No need to check if one of the heads are null. It's possible to rewrite using a dummy a node to handle such cases naturally without special treatment
The variable names can be improved

Implementation:

Node* MergeLists(Node *headA, Node* headB)
{
    Node *dummy = new Node();
    Node *node = dummy;

    Node *nodeA = headA;
    Node *nodeB = headB;
    while (nodeA != NULL && nodeB != NULL) {
        if (nodeA->data <= nodeB->data) {
            node->next = nodeA;
            nodeA = nodeA->next;
        } else {
            node->next = nodeB;
            nodeB = nodeB->next;
        }
        node = node->next;
    }

    node->next = nodeA != NULL ? nodeA : nodeB;

    Node *head = dummy->next;
    delete dummy;
    return head;
}


Linked deque implementation in C I wrote a deque implementation in C for storing char *. It uses a doubly linked list, but I'm calling it a deque since it can only push/pop from the head and tail of the list.

I don't have much experience writing C (I'm more of a Python guy) so please let me know what can be improved! I am already aware of the following:

there are no comments (I've tried to use self-explanatory names)
the testing isn't particularly rigorous

linkedlist.h

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H
#include <stdlib.h>

struct ll_node {
    struct ll_node *prev;
    struct ll_node *next;
    char           *data;
};

struct linkedlist {
    struct ll_node *head;
    struct ll_node *tail;
    size_t         length;
};

void ll_node_init(struct ll_node *node, char *data);
void ll_init(struct linkedlist *ll);
void ll_destroy(struct linkedlist *ll);
void ll_push_head(struct linkedlist *ll, char *data);
void ll_push_tail(struct linkedlist *ll, char *data);
char *ll_pop_head(struct linkedlist *ll);
char *ll_pop_tail(struct linkedlist *ll);

#endif

linkedlist.c

#include <stdlib.h>
#include "linkedlist.h"

void ll_node_init(struct ll_node *node, char *data) {
    node->prev = NULL;
    node->next = NULL;
    node->data = data;
}

void ll_init(struct linkedlist *ll) {
    ll->head = NULL;
    ll->tail = NULL;
    ll->length = 0;
}

void ll_destroy(struct linkedlist *ll) {
    struct ll_node *node = ll->head;
    struct ll_node *next;

    while(node != NULL) {
        next = node->next;
        free(node);
        node = next;
    }
}

void ll_push_head(struct linkedlist *ll, char *data) {
    struct ll_node *node = malloc(sizeof(struct ll_node));
    ll_node_init(node, data);

    if(ll->head != NULL) {
        ll->head->prev = node;
    }

    if(ll->tail == NULL) {
        ll->tail = node;
    }

    node->next = ll->head;
    ll->head = node;
    ll->length++;
}

void ll_push_tail(struct linkedlist *ll, char *data) {
    struct ll_node *node = malloc(sizeof(struct ll_node));
    ll_node_init(node, data);

    if(ll->tail != NULL) {
        ll->tail->next = node;
    }

    if(ll->head == NULL) {
        ll->head = node;
    }

    node->prev = ll->tail;
    ll->tail = node;
    ll->length++;
}

char *ll_pop_head(struct linkedlist *ll) {
    struct ll_node *node = ll->head;
    char *data;

    if(node == NULL) {
        return NULL;
    }

    if(node == ll->tail) {
        ll->tail = NULL;
    }

    ll->head = node->next;
    ll->length--;

    data = node->data;
    free(node);

    return data;
}

char *ll_pop_tail(struct linkedlist *ll) {
    struct ll_node *node = ll->tail;
    char *data;

    if(node == NULL) {
        return NULL;
    }

    if(node == ll->head) {
        ll->head = NULL;
    }

    ll->tail = node->prev;
    ll->length--;

    data = node->data;
    free(node);

    return data;
}

ll_test.c

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "linkedlist.h"

int main(int argc, char *argv[]) {
    struct linkedlist ll;
    char *data;
    ll_init(&ll);

    ll_push_head(&ll, "Alice");
    ll_push_tail(&ll, "Bob");
    ll_push_tail(&ll, "Charlotte");
    ll_push_head(&ll, "Daniel");
    assert(ll.length == 4);

    assert(strcmp(ll_pop_head(&ll), "Daniel") == 0);
    assert(strcmp(ll_pop_tail(&ll), "Charlotte") == 0);
    assert(strcmp(ll_pop_tail(&ll), "Bob") == 0);
    assert(strcmp(ll_pop_tail(&ll), "Alice") == 0);
    assert(ll.length == 0);

    ll_destroy(&ll);
    return 0;
}

Looks good. Few notes:

There is no reason to #include <stdlib.h> in both linkedlist.h and linkedlist.c. Pick one (I recommend linkedlist.c).
Allocation of a struct llnode instance definitely belongs to ll_node_init, and its signature should be

static struct ll_node * ll_node_init(char * data);

Notice static: there is no reason to expose struct ll_node to the client.
Maintain your invariants. It is clear that if (ll_head != NULL) then ll_tail != NULL, and vice versa. For example, push_head should have

    if (ll->head != NULL) {
        assert(ll->tail != NULL);
        ll->head->prev = node;
    } else {
        assert(ll->tail == NULL);
        ll->tail = node;
    }

The code doesn't really care what kind of data it queues. You may consider making the structure more generic with void * data.


Write and control Perlin noise for 1D I'm reading this tutorial and it's the first time I try something this new.

Here is my attempt:

import sys
import math
import pygame
import random

pygame.init()
windowwidth, windowheight = 900, 500
windowsurface = pygame.display.set_mode((windowwidth, windowheight), 0, 32)
clock = pygame.time.Clock()
fps = 30
MAX_INT = (1<<31) - 1
grey = (128, 128, 128)

def linear_interpolate(a, b, x):
    return a*(1-x) + b*x

def int_noise(x):
    # I'm pretty sure I can use random.uniform(-1, 1) as I need a value in the range (-1, 1)
    # I just saw this function on SO that is said to be faster that the build-in.
    x = int(x)
    x = ((x << 13) & MAX_INT) ^ x
    x = ( x * (x * x * 15731 + 789221) + 1376312589 ) & MAX_INT
    return 1.0 - x / 1073741824.0

def smooth_noise(x):
    return int_noise(x)/2 + int_noise(x-1)/4 + int_noise(x+1)/4

def noise_interpolate(x):
    int_x = int(x)
    fractional_x = x - int_x

    v1 = smooth_noise(int_x)
    v2 = smooth_noise(int_x+1)

    return linear_interpolate(v1, v2, fractional_x)

def perlin_noise(x):
    total = 0
    persistence = 1/4
    octaves = 10

    for i in range(octaves):
        frequency = pow(2, i)
        amplitude = pow(persistence, i)

    total = total + noise_interpolate(x*frequency) * amplitude

    return total

#---------------------------------------------------------------------------

def mainloop():
    scale = 50
    points = [(i, perlin_noise(0.6*i) * scale)
              for i in range(0, windowwidth, 10)]
    points.append((900, perlin_noise(0.5)))

    while True:
        clock.tick(fps)
        pygame.display.set_caption('fps: %.2f' % clock.get_fps())

        # handle events
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()

        # update game state

        # draw
        for i in range(len(points) - 1):
            pygame.draw.line(windowsurface, grey,
                             (points[i][0], 350+points[i][1]),
                             (points[i+1][0], 350+points[i+1][1]), 1)
        pygame.display.update()

if __name__ == '__main__':
    mainloop()

I know the design is awful, but I'm more concerned if it is the correct way to write all this. From interpolating function, to the smoothing function, all the way to perlin.

I have the feeling that this Perlin noise function is completely wrong and very misleading, regardless the fact that I draw the wave onto the screen.

To begin with, you cannot use random.uniform() in your current design. The tutorial specifically emphasize that the  noise function shall be seeded, that is, for the same argument it shall always return the same result.

Second, the tutorial suggests that each octave must have its own noise generator. I believe it is essential (again, the noise it seeded, so you'd get literally the same noise for each octave).

You can get away with random.uniform() by calculating noise tables (one per octave), and use them as noise functions. In fact, I'd recommend this approach.


Generic dataloader for redux-thunk using axios I am developing an application where there are lots of async actions. I wanted to go with redux-saga but most have insisted to continue with redux-thunk. In redux-thunk, inside each action we have to work with async operation using then, dispatch, catch, etc. This makes looks actions so messy and lots of code will be repeated. I wanted to create a generic dataLoader for the use of redux-thunk and axios.

Here is my attempt:

export class Company {
/**
* Generic api data loader
*/
static dataLoader(apiUri, onSuccess, onError, data, ...actionArguments) {
  const requestURL = `${API_BASE}${apiuri}`;
  try {
    let options;
    if (data !== undefined) {
      // if we have data to post
      options = {
      method: 'POST',
      url: requestURL,
      body: JSON.stringify(data),
      headers: {
         'Content-Type': 'application/json',
         'X-Requested-With': 'XMLHttpRequest',
      },
      };
    }
  }
  return function(dispatch) {
    axios(options)
    .then(response => {
      dispatch({
        type: onSucess,
        payload: response.data
      });
    })
    .catch(error => {
      dispatch({ type: onError, payload: err});
    });
  }
}

static get(apiUri, onSuccess, onError, ...actionArguments) {
    return this.dataLoader(apiUri, onSuccess, onError, undefined, ...actionArguments);
  }

  /*
   * Shorthand POST function
   */
  static post(apiUri, onSuccess, onError, data, ...actionArguments) {
    return this.dataLoader(apiUri, onSuccess, onError, data, ...actionArguments);
  }

}

I want to convert the following code to further this one:

export function showResultofApartment() {
  return (dispatch) => {
    dispatch({ type: 'APARTMENT_FETCH_START' });
    const token = localStorage.getItem('token');
    return axios.get(`${API_URL}/newoffers/apartment/`)
    .then((response) => {
      console.log('response apart', response.data);
        dispatch({ type: 'APARTMENT_FETCH_SUCCESS', payload: response.data });
    })
    .catch((err) => {
      dispatch({ type: 'APARTMENT_FETCH_FAILURE', payload: err });
    });
  };
}

to such or more efficient than this:

export function showResultofApartment() {
  return(dispatch) => {
    dispatch({ type: APARTMENT_FETCH_START });
    const token = localStorage.getItem('token');
    return Company.get('/apartments', APARTMENT_FETCH_SUCCESS, APARTMENT_FETCH_ERROR);
    // if post then Company.post('/apartment', APARTMENT_POST_SUCCESS, APARTMENT_POST_ERROR, data)
  }
}

I have not tested this. I am just throwing my idea through code to get other experts idea on how I should handle such case for a more efficient technique without using other more external libraries.

This is one of the problems with async actions in redux-thunk. As you point out you have to create constants for "APARTMENT_FETCH_STATUS" and manually dispatch actions of this type before and after the request has been done.

The redux-promise-middleware library actually does all this for you. You simply create an action like so:

const foo = () => ({
  type: 'FOO',
  payload: new Promise()
});

and the library will take care of dispatching an action of type "FOO_PENDING", and then of type "FOO_FULFILLED" when the promise has resolved. With redux-promise-middleware your actions would become something like this:

const showResultOfApartment = () => ({
    type: "FETCH_APARTMENT",
    payload: axios.get("http://api.com/apartments").then(result => result.data)
})

In your reducer you would create handlers for "FETCH_APARTMENT_PENDING", "FETCH_APARTMENT_FULFILLED" and "FETCH_APARTMENT_REJECTED". In the case where the promise fulfills or rejects, you also get the result of the promise by accessing action.payload. An example of what it could look like:

function apartmentReducer(state, action){
    if(action.type === "FETCH_APARTMENT_PENDING"){
        return Object.assign({}, state, { loading: true })
    }
    else if(action.type === "FETCH_APARTMENT_FULFILLED"){
        return Object.assign({}, state, { loading: false, apartment: action.payload })
    }
    else if(action.type === "FETCH_APARTMENT_REJECTED"){
        return Object.assign({}, state, { loading: false, error: action.payload })
    }
    return state;
}

redux-promise-middleware

Introduction to redux-promise-middleware


Sort an array by value and index in C Your task is to sort an array of integer numbers by the product of the
  value and the index of the positions.

  For sorting the index starts at 1, NOT at 0! The sorting has to be
  ascending. The array will never be null and will always contain
  numbers.

My solution

int* sortByValueAndIndex(int* array, int arrayLength) {
  int* extraArray = malloc(arrayLength * sizeof(int));

  for (int index = 0; index < arrayLength; index++) {
    extraArray[index] = array[index] * (index + 1);
  }

  /* Bubble sort */
  for (int firstIndex = 0; firstIndex < arrayLength - 1; firstIndex++) {
    for (int secondIndex = 0; secondIndex < arrayLength - firstIndex - 1; secondIndex++) {
      if (extraArray[secondIndex] > extraArray[secondIndex + 1]) {

        int tmp = array[secondIndex];
        array[secondIndex] = array[secondIndex + 1];
        array[secondIndex + 1] = tmp;

        tmp = extraArray[secondIndex];
        extraArray[secondIndex] = extraArray[secondIndex + 1];
        extraArray[secondIndex + 1] = tmp;
      }
    }
  }

  free(extraArray);

  return array;
}

Well, your code works, though it needs \$O(n)\$ space and \$O(n^2)\$ time.

It's also quite cleanly implemented, so kudos.

Still, there's naturally something which can be improved:

If you need a generic loop-index, the natural name is i. If you need a second one, ask for j. Yes, they are short, but they are the standard names, so you cannot get more descriptive.
Your additional array's name should reflect its use: Call it keys.
You have a general tendency for long names. Try to keep it as brief as you can without sacrificing clarity.
Avoid using a type with sizeof. If the receiving variable ever changes its type, you have to keep it in sync manually, and its not idiomatic. Use:

int* keys = malloc(arrayLength * sizeof *keys);

You assume that malloc() won't fail. You know assume makes an ass out of u and me?
Do you know that signed integer-overflow is Undefined Behavior? I didn't find anywhere in the problem-description a guarantee that array[i] * (i + 1) won't overflow, so you might want to use a bigger type for the keys.
Should you really write your own sub-standard sorting-algorithm, or can you use the one in the standard-library?

The following trades more extra-space for using qsort(), which should have \$O(n * \log(n))\$ runtime:

typedef struct pair {
    long long key;
    int value;
} pair;

static int sortByValueAndIndex_comp(const void* pa, const void* pb) {
    long long a = ((pair*)pa)->key;
    long long b = ((pair*)pb)->key;
    return (a > b) - (a < b);
}

int* sortByValueAndIndex(int* arr, int n) {
    assert(arr || !n);
    assert(INT_MAX <= LLONG_MAX / INT_MAX);
    pair* kv = malloc(n * sizeof *kv);
    if (!kv)
        return 0;

    for (int i = n; i-- > 0;) {
        kv[i].key = arr[i] * (i + 1LL);
        kv[i].value = arr[i];
    }

    qsort(kv, n, sizeof *kv, sortByValueAndIndex_comp);

    for (int i = n; i-- > 0;)
        arr[i] = kv[i].value;

    free(kv);
    return arr;
}