Functional-style list in C++ I've implemented a functional-style list structure in C++. It seems okay so far, and doing custom allocation for list nodes improves performance greatly. I omitted that part here for simplicity.

The mutability of the list is intentional, as the application I'm thinking of requires a lot of state updates. I wrote this code instead of using std::forward_list because

I need to instantiate the list with incomplete types.
The algorithm is recursive (some kind of tree search), so the code will look better with a functional data structure.

Any advice is welcome.

#include <cstdlib>
#include <iostream>
#include <memory>

template<typename T>
struct List
{
    T head;
    std::unique_ptr<List<T>> tail;
};

template<typename T>
std::unique_ptr<List<T>> add(const T &t, std::unique_ptr<List<T>> &&l)
{
    return std::unique_ptr<List<T>>(new List<T>{t, std::move(l)});
}

template<typename T>
std::unique_ptr<List<T>> list()
{
    return std::unique_ptr<List<T>>();
}

template<typename T, typename ...Ts>
std::unique_ptr<List<T>> list(const T &t, const Ts &...ts)
{
    return add(t, list<T>(ts...));
}

template<typename T>
std::unique_ptr<List<T>> copy(const std::unique_ptr<List<T>> &l)
{
    if (l == list<T>())
    {
        return list<T>();
    }
    else
    {
        return add(l->head, copy(l->tail));
    }
}

template<typename T>
std::unique_ptr<List<T>> merge(const std::unique_ptr<List<T>> &a, const std::unique_ptr<List<T>> &b)
{
    if (a == list<T>())
    {
        return copy(b);
    }
    else
    {
        return add(a->head, merge(a->tail, b));
    }
}

template<typename T, typename Filter>
std::unique_ptr<List<T>> filter(const std::unique_ptr<List<T>> &l, Filter f)
{
    if (l == list<T>())
    {
        return list<T>();
    }
    else if (f(l->head))
    {
        return add(l->head, filter(l->tail, f));
    }
    else
    {
        return filter(l->tail, f);
    }
}

template<typename T>
std::unique_ptr<List<T>> sort(const std::unique_ptr<List<T>> &l)
{
    if (l == list<T>())
    {
        return list<T>();
    }
    else
    {
        return merge(sort(filter(l->tail, [&](const T &t){return t < l->head;})), add(l->head, sort(filter(l->tail, [&](const T &t){return t >= l->head;}))));
    }
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::unique_ptr<List<T>> &l)
{
    if (l == list<T>())
    {
        return os;
    }
    else
    {
        return os << l->head << ' ' << l->tail;
    }
}

std::unique_ptr<List<int>> randomList(int n)
{
    if (n == 0)
    {
        return list<int>();
    }
    else
    {
        return add(std::rand() % 100, randomList(n - 1));
    }
}

int main()
{
    auto r = randomList(100);
    std::cout << r << '\n' << sort(r) << '\n';
}

This looks pretty solid. I don't have any major comments. Just lots of minor ones.

Unique or Shared

Why unique_ptr as a design choice over shared_ptr? The latter would let you be able to take shallow copies to your lists without having to have references everywhere. I'm not saying that shared_ptr is strictly better, more than it's something worth considering if you have not already. Either way, both are strictly better than raw pointers, so you're already on the right track.

std::unique_ptr<List<T>>

That is a huge mouthful to type every time. And it is the only type that matters. So let's just alias it:

template <typename T>
using FList = std::unique_ptr<List<T>>;

Alternatively, rename List<> to Cons or Node so that the alias can be named List. To avoid confusion, I will use FList throughout the rest of this review.

cons()

The standard name for a list structure that is a value and a list is a "cons" cell. As in construct. Just for consistency, you should rename your add() to cons():

template<typename T>
FList<T> cons(const T& t, FList<T>&& xs)
{
    return {new List<T>{t, std::move(xs)}};
}

Now, this is less usable than it could be, simply because you can't do something like:

FList<long> x = ...;
cons(4, std::move(x)); // error

For that, let's loosen the restrictions:

template <typename T,
          typename U,
          typename = std::enable_if_t<std::is_constructible<T, U&&>::value>
          >
FList<T> cons(U&& u, FList<T>&& xs)
{
    return {new List<T>{std::forward<U>(u), std::move(xs)}};
}

You'll note that I changed your variable from l to xs. 1 is a terrible variable name as it's very easy to mistake for l. So easy to mistake that you probably didn't notice that I wrote one the first time and el the second time.

list()

Going on the theme of loosening restrictions, let's do that here too:

template<typename T>
FList<T> list()
{
    return {}; // shorter
}

template<typename T, typename U, typename...Us>
FList<T> list(U&& u, Us&&... us)
{
    return cons(std::forward<U>(u),
                list<T>(std::forward<Us>(us)...)
                );
}

That will let you write:

auto nums = list<int>(1, '4', 5ull);

Checking for empty list

In your functions, you tend to start with:

if (l == list<T>())

But std::unique_ptr is usable in a boolean context as-is. So all of those checks you can write much simpler:

template<typename T>
FList<T> copy(const FList<T>& xs)
{
    if (!xs)
    {
        return {};
    }
    else
    {
        return cons(xs->head, copy(xs->tail));
    }
}

Note that in the interest of being functional, we also probably want:

template <typename T>
T const& car(FList<T> const& xs) { // or T& if you want mutability
    return xs->head;
}

template <typename T>
FList<T> const& cdr(FList<T> const& xs) {
    return xs->tail;
}

So that this becomes:

return cons(car(xs), copy(cdr(xs)));

filter()

Could avoid some code duplication here:

template<typename T, typename Filter>
FList<T> filter(const FList<T>& xs, Filter f)
{
    if (!xs) {
        return {};
    }

    auto tail = filter(cdr(xs), f);
    return f(car(xs))
           ? cons(car(xs), std::move(tail))
           : tail;
}

sort()

This function deserves a comment solely for:

    return merge(sort(filter(l->tail, [&](const T &t){return t < l->head;})), add(l->head, sort(filter(l->tail, [&](const T &t){return t >= l->head;}))));

It's like you never want anybody to read your code. So you're basically trying to do a sort of quicksort based on partitioning the head. Let's just write that in more than one line of code (and rename it to sorted to mimic python and make it sound less like you're sorting in place):

template<typename T>
FList<T> sorted(const FList<T>& xs)
{
    if (!xs) return {};

    auto left = filter(cdr(xs), [&](const T& val){ return val < car(xs); });
    auto right = filter(cdr(xs), [&](const T& val){ return !(val < car(xs)); });

    return merge(sorted(left),
                 cons(car(xs), sorted(right)));
}

I find that a ton easier to read. The reason I wrote the second filter with ! is that it naturally lends itself to adding a custom comparator:

template <typename T, typename Comp = std::less<T>>
FList<T> sorted(const FList<T>& xs, Cmp cmp = {})
{
    if (!xs) return {};

    auto left = filter(cdr(xs), [&](const T& val){ return cmp(val, car(xs)); });
    auto right = filter(cdr(xs), [&](const T& val){ return !cmp(val, car(xs)); });

    return merge(sorted(left, cmp),
                 cons(car(xs), sorted(right, cmp)));
}


Sort array of objects with hierarchy by hierarchy and name I have an array of nested objects:

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},
    {_id:8, parent:2, name:'G'},
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

I need to sort them in the way for nodes at same level will be sorted by alphabetic order (asc/desc configurable) and all child nodes should be after their parent and before their parent's sibling node also sorted by alphabetic order.

For example, if sorted by asc, the output should be

[
    { _id: 4, parent: 0, name: 'A' },
    { _id: 5, parent: 4, name: 'M' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 3, parent: 1, name: 'Z' }
]

In the output, 4 is before 1 because A < Z. 5 and 6 are sorted alphabetically under 4 and before 1. Similar case for 8 and 7 under 2 and before 3.

and if desc, the output should be:

[
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 3, parent: 1, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 4, parent: 0, name: 'A' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 5, parent: 4, name: 'M' }
]

I tried to implement a function as below.

function sortByHierarchyAndName(arr, sort) {
    var i = 0;
        j = 0;
        t = 0;
        parentFound = false;
        x = arr.length;
        arr2 = [];

    //Sort by parent asc first
    arr = arr.sort(function(a, b) {
        if(a.parent < b.parent) return -1;
        if(a.parent > b.parent) return 1;
        return 0;
    });

    for(; i < x; i += 1) {
        t = arr2.length;
        if(t === 0)  arr2.push(arr[i]);
        else if(arr[i].parent === 0) {
            for(j = 0; j < t; j += 1) {
                if(sort === -1) {
                    if(arr[i].name >= arr2[j].name) arr2.splice(j, 0, arr[i]);
                } else {
                    if(arr[i].name <= arr2[j].name) arr2.splice(j, 0, arr[i]);
                }
            }
            if(arr2.length === t) arr2.push(arr[i]);
        }
        else {
            parentFound = false;
            for(j = 0; j < t; j += 1) {
                if(arr[i].parent === arr2[j]._id) {
                    if(j === t - 1) {
                        arr2.push(arr[i]);
                    }
                    parentFound = true;
                } else if(arr[i].parent === arr2[j].parent) {
                    if(sort === -1) {
                        if(j === t - 1) arr2.push(arr[i]);
                        else if(arr[i].name >= arr2[j].name) {
                            arr2.splice(j, 0, arr[i]);
                            j = t;
                        }
                    } else {
                        if(j === t - 1) arr2.push(arr[i]);
                        else if(arr[i].name <= arr2[j].name) {
                            arr2.splice(j, 0, arr[i]);
                            j = t;
                        }
                    }
                } else if(arr[i].parent > arr2[j].parent && parentFound) {
                    arr2.splice(j, 0, arr[i]);
                    j = t;
                }
            }
        }
    }
    return arr2;
}

Assuming array.sort() take f(n) amount of time when sorting by parent asc for an array of length n, I'm doing some performance analysis for the implementation as below.

  Best case: \$f(n) + x \times n + y \times \sum (\frac{1...n}{2})\times n\$

  Worst case: \$f(n) + x \times n + y \times \sum (1...n)\times n\$

  x - factor in processing any given element in arr.

  y - factor in processing any given element in arr against any element in arr2.

As you can see, in both case, the duration of execution will grow exponentially as n grows, so I'm wondering if I can do something to improve this.

Since you have a representation of a tree i suggest using it,
then traverse it in pre-order

So if

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},
    {_id:8, parent:2, name:'G'},
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

lets build a tree like this

   [
      {_id:1, parent:0, name:'Z', children:
         [
             {_id:2, parent:1, name:'H', children:
                [
                   {_id:8, parent:2, name:'G', children: []},
                   {_id:7, parent:2, name:'L', children: []}
                ]
             },
             {_id:3, parent:1, name:'Z', children: []}
         ]
      },
      {_id:4, parent:0, name:'A', children:
         [
             {_id:5, parent:4, name:'M', children: []},
             {_id:6, parent:4, name:'N', children: []}
         ]},
   ]

my suggestion is like this:

var nodes = [
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},
    {_id:8, parent:2, name:'G'},
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]
var tree = {_id:0};

var addChildrenToNode = function(node,cmp){
    var currentNodeId = node._id;
    node.children = [];
    nodes.forEach(function(e){
        if(e.parent === currentNodeId){
            e = addChildrenToNode(e);
            node.children.push(e);
        }
    });
    node.children = node.children.sort(cmp); // sort the children
    return node;
};

var cmp = function(a, b) {
    if(a.name < b.name) return -1;
    if(a.name > b.name) return 1;
    return 0;
};
tree = addChildrenToNode(tree,cmp);

Then you only have to do the pre-order traverse, like this:

var preOrderTraverse = function(node, fn){ // sends values of tree to fn in pre-order
    fn(node); //call at preorder
    if(node.children.length > 0){
        node.children.forEach(function(e){
            preOrderTraverse(e,fn);
        });
    }
}

preOrderTraverse(tree,
    function(node){ // do what you like with each node
        console.log(node);
    }
);


Removing folders from my rails app with rake I'm trying to remove the tmp/letter_opener folder. Everything works fine, just wondering if there's a better way to write it. My next step is to write some tests, to double check that I can only accept those inputs (currently failing)

#my_rake_task.rake

namespace :cleanup do

desc 'Deletes the emails inside tmp/letter_opener folder.'
task letter_opener_emails: :environment do

start_time = Time.current
Rails.logger.info "Task starting at #{start_time}."
puts "Task starting at #{start_time}."

print 'About to remove the tmp/letter_opener folder. Press [Nn] to abort. Press [Yy] to continue.'
option = STDIN.gets.strip

case option #[FIXME]: Not deleting the folders
  when /[^Nn]/ then FileUtils.rm_r(Dir.glob('tmp/letter_opener/*'))
    puts 'Directory contents removed'
  when /[^Yy]/ then 'Exiting the task now.'
    # abort_message
end
end

As mudasobwa's comment says, your using the case statement backwards. And wrongly.

You're checking if input contains letters that are not n or N, and if that's true, you delete stuff. So I could type foobar, and it'd delete files. Bad.

Even if I type exit or quit or whatever else to stop the task, it'll happily delete stuff. Even typing cancel would be interpreted as "yes, please delete stuff", since - though it contains an "n" - it contains lots of letters that are not "n".

You also have a (dead) branch for not typing y or Y, though that makes no sense. And you don't have an else branch - not that you need one, but it'd make more sense.

You have a fixme you haven't fixed. Your indentation is missing or wrong. Your message ("About to remove the tmp/letter_opener folder.") doesn't match what the code does.

In all, it's not great.

All you need is this:

namespace :cleanup do
  desc 'Deletes the emails inside tmp/letter_opener folder.'
  task letter_opener_emails: :environment do
    puts "Remove tmp/letter_opener? [yn]"
    if STDIN.gets.chomp =~ /^y$/i
      FileUtils.rm_r("tmp/letter_opener")
    else
      puts "Aborting"
    end
  end
end


Spelling a number in English My Implementation:

string NumberToEnglish(long n)
{
    StringBuilder builder = new StringBuilder();
    var trillion = 1000000000000;
    var billion = 1000000000;
    var million = 1000000;
    var thousand = 1000;
    var hundred = 100;
    while(n != 0){
        if(n >= trillion){
            builder.AppendFormat("{0} Trillion ",NumberToEnglish(n / trillion));
            n -= (n / trillion) * trillion;
        }
        else if(n >= billion){
            builder.AppendFormat("{0} Billion ",NumberToEnglish(n / billion));
            n -= (n / billion) * billion;
        }
        else if(n >= million){
            builder.AppendFormat("{0} Million ",NumberToEnglish(n / million));
            n -= (n / million) * million;
        }
        else if(n >= thousand){
            builder.AppendFormat("{0} Thousand ",NumberToEnglish(n / thousand));
            n -= (n / thousand) * thousand;
        }
        else if(n >= hundred){
            builder.AppendFormat("{0} Hundred ",NumberToEnglish(n / hundred));
            n -= (n / hundred) * hundred;
        }else if(n >= 20){
            builder.AppendFormat(numerals[(n / 10) * 10] + " ");
            n -= (n / 10) * 10;
        }else{
            builder.Append(numerals[n]);
            n -= n;
        }
    }
    return builder.ToString();
}

Dictionary<long,string> numerals = new Dictionary<long,string>(){
    {   1,          "One"   },
    {   2,          "Two"   },
    {   3,          "Three" },
    {   4,          "Four"},
    {   5,          "Five"},
    {   6,          "Six"}  ,
    {   7,          "Seven"},
    {   8,          "Eight"},
    {   9,          "Nine"},
    {   10,         "Ten"   },
    {   11,         "Eleven"},
    {   12,         "Twelve"},
    {   13,         "Thirteen"},
    {   14,         "Fourteen"},
    {   15,         "Fifteen"   },
    {   16,         "Sixteen"   },
    {   17,         "Seventeen"},
    {   18,         "Eighteen"},
    {   19,         "Nineteen"},
    {   20,         "Twenty"    },
    {   30,         "Thirty"    },
    {   40,         "Forty"}    ,
    {   50,         "Fifty" },
    {   60,         "Sixty" },
    {   70,         "Seventy"},
    {   80,         "Eighty"}   ,
    {   90,         "Ninety"}   ,
    {   100,        "Hundred"}  ,
    {   1000,       "Thousand"},
    {   1000000,    "Million"   },
    {   1000000000, "Billion" },
    {   1000000000000, "Trillion" }
};

Test Method:

void Main()
{
    Console.WriteLine(NumberToEnglish(2120)); // Two Thousand One Hundred Twenty
}

How can I improve this?

I took an object-oriented approach here, and below you can find what I ended up with. Why do I think it's better? Well, basically, because you should need the ability to control how each one of the number parts is processed: whether it's plural, whether it should be changed according to previous (or following) number parts. The latter one does not really apply to english, but it applies to some other languages. If you did all that in one function, you would end up with having a bunch of code, which performs different kinds of tasks (1. retrieve string value 2. apply plural/singular 3. apply gender 4. Apply "forth"/"four" formatting rules). But taking the object oriented approach you now have a standalone part which does thing 1. When you need to think about 2-4, you can integrate other parsers into your code.

// This is what your initial function looks like
public static string NumberToEnglish(long n) {
    StringBuilder builder = new StringBuilder();
    var steps = new INumberPart[] {
        new SimpleNumberPart{Step = 1000000000000}, //trillion
        new SimpleNumberPart{Step = 1000000000}, //billion
        new SimpleNumberPart{Step = 1000000}, //million
        new SimpleNumberPart{Step = 1000}, //thousand
        new SimpleNumberPart{Step = 100}, //hundred
        new DecimalNumberPart(),
        new TeenNumberPart()
    };
    while (n != 0) {
        var firstAvailable = steps.First(s => s.CanBeFormatted(n));
        n = firstAvailable.Format(n, builder);
    }
    return builder.ToString();
}

public interface INumberPart {
    bool CanBeFormatted(long n);
    long Format(long n, StringBuilder s);
}

public class SimpleNumberPart : INumberPart {
    public long Step { get; set; }

    public bool CanBeFormatted(long n) {
        return n >= Step;
    }

    public long Format(long n, StringBuilder s) {
        return ProcessNum(n, Step, s);
    }

    private static long ProcessNum(long n, long step, StringBuilder builder) {
        var stepValue = n / step;
        builder.AppendFormat("{0}", NumberToEnglish(stepValue));
        builder.AppendFormat("{0} ", numerals[step]);
        return n - stepValue * step;
    }
}

public class DecimalNumberPart : INumberPart {
    public bool CanBeFormatted(long n) {
        return n >= 20;
    }

    public long Format(long n, StringBuilder s) {
        s.AppendFormat("{0} ", numerals[(n / 10) * 10]);
        return n - (n/10)*10;
    }
}

public class TeenNumberPart : INumberPart {
    public bool CanBeFormatted(long n) {
        return 0 <= n && n < 20;
    }

    public long Format(long n, StringBuilder s) {
        s.AppendFormat("{0} ", numerals[n]);
        return 0;
    }
}


Converting an input audio file to a monophonic FLAC file I have the following method which basically converts an input audio file to a monophonic FLAC file.

Now I am getting Member has cyclomatic complexity of 21 (105%) message in Visual Studio, while I've taken care of improving it as in the beginning it was longer, now there's not much I can remove from it as it pretty much fulfills my needs.

Should I just ignore this warning ?

private static void Convert(string inputFile, string outputFile, IProgress<double> progress = null)
{
    if (inputFile == null) throw new ArgumentNullException("inputFile");
    if (outputFile == null) throw new ArgumentNullException("outputFile");
    int stream = 0;
    int mixer = 0;
    try
    {
        stream = Bass.BASS_StreamCreateFile(inputFile, 0, 0,
            BASSFlag.BASS_STREAM_DECODE | BASSFlag.BASS_SAMPLE_FLOAT | BASSFlag.BASS_STREAM_PRESCAN);
        if (stream == 0) throw new BassException("Could not create stream");
        var info = Bass.BASS_ChannelGetInfo(stream);
        if (info == null) throw new BassException("Could not retrieve stream info");
        var freq = info.freq;
        mixer = BassMix.BASS_Mixer_StreamCreate(freq, 1,
            BASSFlag.BASS_MIXER_END | BASSFlag.BASS_SAMPLE_FLOAT | BASSFlag.BASS_STREAM_DECODE);
        if (mixer == 0) throw new BassException("Could not create mixer");
        bool addChannel = BassMix.BASS_Mixer_StreamAddChannel(mixer, stream, BASSFlag.BASS_MIXER_NORAMPIN);
        if (!addChannel) throw new BassException("Could not add stream to mixer");
        long getLength = Bass.BASS_ChannelGetLength(stream);
        if (getLength == -1) throw new BassException("Could not get channel length");
        var encoder = new EncoderFLAC(mixer)
        {
            Force16Bit = true,
            FLAC_Verify = true,
            OutputFile = outputFile
        };
        if (!encoder.Start(null, IntPtr.Zero, false))
            throw new InvalidOperationException("Could not start encoder");
        const int samples = 65536;
        const int bytes = (samples * sizeof(float)) | (int)BASSData.BASS_DATA_FLOAT;
        var buffer = new float[samples];
        long bytesRead = 0;
        while (Bass.BASS_ChannelIsActive(mixer) == BASSActive.BASS_ACTIVE_PLAYING)
        {
            int getData = Bass.BASS_ChannelGetData(mixer, buffer, bytes);
            bytesRead += getData;
            if (progress != null) progress.Report(1.0d / getLength * bytesRead);
        }
        encoder.Stop();
        if (getLength / sizeof(short) != bytesRead)
            throw new InvalidOperationException("Output length not equal to input length");
    }
    catch (Exception ex)
    {
        throw new InvalidOperationException("Conversion failed", ex);
    }
    finally
    {
        if (stream != 0) Bass.BASS_StreamFree(stream);
        if (mixer != 0) Bass.BASS_StreamFree(mixer);
    }
}

I think your code would become much simpler and more readable if you encapsulated all the BASS-related functionality from into separate types.

Something like:

class Stream
{
    private readonly int handle;

    // add overload that supports setting offset and lenght, if you need that
    public Stream(string inputFile, BASSFlag flags)
    {
        handle = BASS_StreamCreateFile(inputFile, 0, 0, flags);

        if (handle == 0)
            throw new BassException("Could not create stream");
    }

    public ChannelInfo GetInfo()
    {
        var result = Bass.BASS_ChannelGetInfo(stream);

        if (result == null)
            throw new BassException("Could not retrieve stream info");

        return result;
    }

    // etc.
}

This would simplify the start of your code to just:

Stream stream = new Stream(inputFile,
    BASSFlag.BASS_STREAM_DECODE | BASSFlag.BASS_SAMPLE_FLOAT | BASSFlag.BASS_STREAM_PRESCAN);
var info = stream.GetInfo();


Find all pairs in an array that sum to a given number without using HashMap Find all pairs in an array that sum to a given number without using HashMap.
  Duplicate pairs are not allowed. Input array cannot be modified.

  input:   {-2, -1, -1, 5, 7, 7, 7, 7, 8}, target = 7

  output: (-1, 8)

As it is mentioned, using HashMap is not allowed, so I decided to use binary search.

GitHub

public class TwoSumProblemUsingBinarySearch {

    public static class Pair {

        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object other) {
            if (other instanceof Pair) {
                Pair o = (Pair) other;
                return this.x == o.x && this.y == o.y;
            }

            return false;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    public static Set<Pair> findAllParis(int input[], int target) {
        int numbers[] = Arrays.copyOf(input, input.length);
        Set<Pair> pairs = new HashSet<>();

        Arrays.sort(numbers);

        for (int low = 0, high = input.length - 1; low < high; ) {
            int sum = input[low] + input[high];

            if (sum > target) {
                high--;
            } else if (sum < target) {
                low++;
            } else {
                pairs.add(new Pair(input[low], input[high]));
                high--;
                low++;
            }
        }

        return pairs;
    }
}

@Test
public void findAllParis() throws Exception {

    System.out.println(TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7));
    assertEquals(1, TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7).size());
}

Typo in method name as pointed out by @Stingy. Should be findAllPairs.
Accessing wrong array: You are reading values from input instead of your sorted copy numbers. This is probably a typo. E.g. int sum = input[low] + input[high]; should be int sum = numbers[low] + numbers[high];
Your for loop has an empty update statement, this isn't wrong per-se but a bit unusual. Consider an alternative using while instead:

int low = 0, high = numbers.length-1;
while (low < high) {
    int sum = numbers[low] + numbers[high];
    //...
}

Insufficient test: As evidenced by its failure to catch the bug in 2. the test is too limited to be of much help. Consider checking more than one example (especially corner-cases like an empty input array) and checking against the expected output instead of just its size.


Replacing if validations with a better error handling I have this little piece of front-end code, and I had a little code smell about the handling of errors.

  request
   .post(('/api/comment/:id/upvote').replace(':id', this.comment.id))
      .end(function (err, res) {
      if (err) {
        log('Fetch error: %s', err);
        return classes(targetElement).remove('selected');
      }

      if (res.status == 401) {
        return errorContainer.innerHTML = t(res.body.error);
      }

      if (!res.ok) {
        log('Fetch error: %s', res.error);
        return classes(targetElement).remove('selected');
      }

      if (res.body && res.body.error) {
        log('Fetch response error: %s', res.body.error);
        return classes(targetElement).remove('selected');
      }

      log('successfull upvote %s', self.comment.id);
      });

In all error conditions, I should "rollback" an status of html element.

classes(targetElement).remove('selected');

I can chain all conditions in one if in order to handle errors, but there's still a code smell.

Does someone have some ideas on how to wrap this in a better error handling?

It looks as if you have two things going on: detecting the error, and reporting the error.  You have a lot of different error handling; is there a way to abstract this down into a message?  Maybe a pair of functions, one of which abstract all of these errors down to a single, page-side error code, and the other of which presents a textual version of that.  Or something that returns a tuple.

In the meantime, I've broken it down into "something went wrong" and "what kind of wrongness happened" blocks.

The one thing that stands out at me is you have two different return types: whatever is returned from the function classes(), and the undefined at the end of the function on success.  By putting the error handler's return on its own line, I've made sure that js-hint and js-lint won't complain about inconsistent return types.

(function (err, res) {
    if ((err) || (res.status == 401) || (!res.ok) || (res.body && res.body.error)) {
        classes(targetElement).remove('selected');
        if (err || (res.body && res.body.error) || (!res.ok)) {
            log("Fetch error: ", (err || res.error || (res.body && res.body.error)));
        }
        if (res.status == 401) {
            errorContainer.innerHTML = t(res.body.error);
        }
        return;
    }
    log('successfull upvote %s', self.comment.id);
});


Counting the proportion of vowels in substrings I'm looking for an algorithm to make my code faster and better for big strings.

Problem link

Let the simple prettiness of a string be the count of vowels (I, E, A, O, U, Y) divided by the length of the string.  Find the sum of the simple prettiness of all substrings of a given string (with precision within 1 part per million), where the input string may be up to 5∙105.

Let's say I have the following input:

IEAIAIO

The output should be like this:

28.000000

Second ex:

BYOB
5.833333

Third ex:

YISVOWEL
17.050000

My solution gives me Time Limited Exceeded on big strings.

#include <bits/stdc++.h>
using namespace std;
int main()
{

    string s;
    while (cin>>s)
    {

        long double sum=0.0;

        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i+1; j <= s.length(); j++)
            {
                string ss=s.substr(i,j-i);
                //<<ss<<endl;
                long double len=0.0;
                for (int r = 0; r < ss.length(); r++)
                {
                    if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y' )
                        len++;
                }
                //cout<<"len = "<<len<<"\tss= "<<ss<<endl;
                long double len_ss=ss.length();
                sum+=(len/len_ss);
            }
        }
        cout<<fixed;
        cout << std::setprecision(6) << sum<<endl;

    }
return 0;

}

Style

You probably don't care much about this but your style (spacing for instance) is not very consistent.

Making things easier to improve

You'll make your code much easier to improve if :

you have a way to measure performances
you have a way to ensure you don't screw it up.

You can do so by writing a few tests.

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

long double prettyness(const string & s)
{
    long double sum = 0.0;
    long double len_s = s.length();
    for (int i = 0; i < len_s; i++)
    {
        for (int j = i+1; j <= len_s; j++)
        {
            string ss = s.substr(i,j-i);
            long double len = 0.0;
            long double len_ss = ss.length();
            for (int r = 0; r < len_ss; r++)
            {
                if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y' )
                    len++;
            }
            sum += len/len_ss;
        }
    }
    return sum;
}

void stdio_tests()
{
    string s;
    while (cin>>s)
    {
        cout << fixed << std::setprecision(6) << prettyness(s) << endl;
    }
}

void unit_tests()
{
    long double res;
    res = prettyness("IEAIAIO");
    assert(res == 28);
    res = prettyness("BYOB");
    assert(5.83333 < res && res < 5.83334);
    res = prettyness("YISVOWEL");
    assert(17.04 < res && res < 17.06);
    res = prettyness("QWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNM");
    assert(79984 < res && res < 79985);
}

int main()
{
    unit_tests();
    return 0;
}

Improvements

I already got rid of the multiples calls to length() above. Let's try to make other improvements.

For a start, you don't need to use substr at all. You can simply try to be smart with string indices :

long double prettyness(const string & s)
{
    long double sum = 0.0;
    long double len_s = s.length();
    for (int i = 0; i < len_s; i++)
    {
        for (int j = i+1; j <= len_s; j++)
        {
            long double len = 0.0;
            for (int r = i; r < j; r++)
            {
                if(s[r]=='I' || s[r]=='E' || s[r]=='A' || s[r]=='O' || s[r]=='U' || s[r]=='Y' )
                    len++;
            }
            sum += len/(j-i);
        }
    }
    return sum;
}

Then, you can get rid of the multiple checks of the char value by storing the result in an array.

Also, you could make things much faster by storing cumulative sums of vowels so that you can get number of vowels in substring i..j by computing something like cum[j]-cum[i].

The code would be something like :

long double prettyness(const string & s)
{
    long double sum = 0.0;
    size_t len_s = s.length();
    long double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i < len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');
    for (int i = 0; i < len_s; i++)
        for (int j = i+1; j <= len_s; j++)
            sum += (cum[j]-cum[i])/(j-i);
    return sum;
}

This is much faster but I'm pretty sure there is a way to do better. For instance, substrings of same lengths could be considered together to perform a smaller number of divisions.

long double prettyness(const string & s)
{
    size_t len_s = s.length();
    double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i < len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');
    long double sum = 0.0;
    for (int l = 1; l <= len_s; l++)
    {
        long double tmp_sum = 0.0;
        for (int end = l; end <= len_s; end++)
        {
            tmp_sum += cum[end] - cum[end-l];
        }
        sum += tmp_sum/l;
    }
    return sum;
}

Then, some trick to compute the inside of the loop faster. Indeed, many indices cancel each other. At the end, you are down to some value that can be precomputed with another cumulative array :

long double prettyness(const string & s)
{
    size_t len_s = s.length();
    double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i < len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');

    double cum_cum[len_s + 2];
    cum_cum[0] = 0;
    for (int i = 0; i <= len_s; i++)
        cum_cum[i + 1] = cum_cum[i] + cum[i];

    long double sum = 0.0;
    for (int l = 1; l <= len_s; l++)
        sum += (cum_cum[len_s + 1] - cum_cum[l] - cum_cum[len_s - l + 1])/l;
    return sum;
}

You have a O(n) algorithm, that should be fast enough (and it is easy to see that better complexity cannot be achieved).


Do you like this kind of helper, which creates short lived helper objects through a delegate? Just curious if this is a reasonable idea.  I wouldn't do it all the time.  The example I'm in now is that of the data context and repository that uses it.

I kind of like this because, compared to calling new in AssignButtonClicked, it gives my code the same quality of feeling independent of resource allocation as when using constructor injection (which I can't do for short lived resources).

void AssignButtonClicked(object sender, EventArgs e)
{
    WithPaymentBatchRepository((context, repository) =>
    {
        foreach (var itemIDs in this.SelectedItemIdsAsInts)
        {
            repository.SetPaymentBatchId(itemIDs, this.SelectedPaymentBatchId);
        }

        context.SaveChanges();
    });

    Refill();
}

static void WithPaymentBatchRepository(Action<EomTool.Domain.Entities.EomEntities, EomTool.Domain.Concrete.PaymentBatchRepository> action)
{
    using (var context = new EomTool.Domain.Entities.EomEntities(EomAppCommon.EomAppSettings.ConnStr, false))
    {
        var repository = new EomTool.Domain.Concrete.PaymentBatchRepository(context);
        action(context, repository);
    }
}

it gives my code the same quality of feeling independent of resource allocation as when using constructor injection

But it's not. With constructor injection, the caller can easily use another implementation or create the resource with different parameters. With your helper method, that is gone. And you can use constructor injection with short lived resources: inject a factory for that resource (that could be a simple Func<Resource> delegate or an interface) instead of the resource itself.

All in all, your helper method might be useful to avoid repeating common code, but not much else. And even with that, it doesn't help much.


How to fill in this HashMap neatly without code duplication? I'm supplying a HashMap with data in the following way:

HashMap<String,MyClass> myHashMap = new HashMap<String,MyClass>();
myHashMap.put( "foo", new MyClass(2,4) );
myHashMap.put( "bar", new MyClass(0,10) );
myHashMap.put( "a",   new MyClass(0,0) );
myHashMap.put( "b",   new MyClass(0,1) );
myHashMap.put( "c",   new MyClass(0,0) );
myHashMap.put( "d",   new MyClass(0,42) );
// ...

There's around 20 lines, but a lot is duplicated text. The only interesting information in every line is foo,2,4, bar,0,10, a,0,0 and so on. How can I make this code neater?

If only the strings differed, I'd do it this way:

List<String> names = Arrays.aslist("foo","bar","a","b","c","d");
for ( String name : names )
    myHashMap.put( name, new MyClass(0,0) );

Then I would use a static method to put the entries in the map:

HashMap<String,MyClass> myHashMap = new HashMap<String,MyClass>();
addEntry(myHashMap, "foo",2,4);
addEntry(myHashMap, "bar", 0,10);
addEntry(myHashMap, "a", 0,0);
addEntry(myHashMap, "b", 0,1);
addEntry(myHashMap, "c", 0,0);
addEntry(myHashMap, "d", 0,42);
// ...

private static //
void addEntry(HashMap<String,MyClass> map, String name, int arg1, int arg2){
  map.put( name, new MyClass(arg1,arg2) );
}

I recommend reading the data from a file and call addEntry(myHashMap, ...); in a loop until end of file is reached.


Project Euler #1 - Revisited I'm learning Clojure and solved Project Euler #1, I'd like to have my code reviewed on all aspects. I'm marking this as follow-up of Project Euler #1 because I answered my own question and implemented it.

Task: Multiples of 3 and 5

  If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

  Find the sum of all the multiples of 3 or 5 below 1000.

My solution

 (ns euler)

 (defn divisible-by?
   [x divisor]
   (zero? (mod x divisor)))

(->> (range 1000)
     (filter #(some (partial divisible-by? %) '(3 5)))
     (reduce +)
     println)

While you have duplicated less code than your first example, I would argue that the using some and partial are a bit overkill for this very trivial example, where or is more clear and succinct.  I like your modification if you are writing a function (which you are not) that takes an arbitrary list of factors to test for divisibility, but you aren't do that.
In general, when running from an interactive REPL, it makes no sense to println your answer.  Though you're not writing a function, we usually think of the function producing a value, given some inputs, and the value returned from the function is sufficient.  Maybe it seems picky, but since you went to the trouble to factor out a divisible-by function, it seems odd that you would unnecessarily print something.  You will find very few printlns in clojure code, generally speaking.  It makes your code harder to test, as you have side-effecting output.
The ->> threading macro is, again, overkill here in my opinion. The goal here is to sum a list of numbers, and making (reduce + ... front and center makes that clear.  You have obfuscated the intent a bit by threading this, IMO.

The above points may seem a bit picky, but they stem from the fact that your goal here is very simple: get a list of numbers and add them.  By threading the code, using partial application, and factoring out a function, you've made the solution overwhelming, compared to what the problem calls for.  What you have done is very nice, but I don't think it fits the problem such that at a glance the reader can quickly see the intent of the code.  Below is my solution, for reference.  It's not fancy, but it tells you what it does rather quickly:

(reduce + (filter #(or (zero? (rem % 3))
                       (zero? (rem % 5)))
                  (range 1000)))

Another more verbose solution, but also clear:

(reduce + (for [x (range 1000)
                :when (or (zero? (rem x 3))
                          (zero? (rem x 5)))]
            x))

One final note: many of the Project Euler problems are math-heavy and as such, often have a more math-based solution (as opposed to an algorithmic solution), or at least can be optimized in such a way.  The wikipedia page has an example using this first problem, where a constant-time (O(1)) solution can be applied which you would certainly want to use for a data set of sufficiently large size (many millions or billions, perhaps).


Project Euler, Challenge #17 in Swift Number letter counts, Problem 17:

  If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

  If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

  NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Result:

  \$21124\$ (Correct according to Project Euler)

  Time: \$0.0172510147094727\$ seconds

Since this hasn't been solved in Swift, I'd like a code review of this challenge which talks about the efficiency of the code, and how to correct bad practices or violations of any concepts. Here is the code:

import Foundation

let unitNames:[String] = [
    "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"
]

let tensNames:[String] = [
    "", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety", "hundred"
]

func convertIntegerToWords(number:Int) -> String {
    var words:String = ""

    if number >= 0 && number <= 19 {

        words = words + unitNames[number]

    } else if number >= 20 && number <= 99  {

        var digits = number.array

        words = words + tensNames[digits[0]]
        words = words + unitNames[digits[1]]

    } else if number >= 100 && number <= 999 {

        var digits = number.array

        if number % 100 == 0 {
            words = words + unitNames[digits[0]] + "hundred";
        } else {
            words = words + unitNames[digits[0]] + "hundredand";
            var newNumber = number - digits[0] * 100;
            words = words + convertIntegerToWords(newNumber)
        }

    } else if number == 1000 {

        words = words + "onethousand"

    }

    return words
}

extension Int {
    var array: [Int] {
        return Array(description).map{String($0).toInt() ?? 0}
    }
}

func EulerSeventeen() -> Int {

    var length:Int = 0

    for iterator in 1...1000 {
        length = length + count(convertIntegerToWords(iterator))
    }
    let end = NSDate();

    return length
}

let start = NSDate();
var result = EulerSeventeen()
let end = NSDate();

let timeInterval: Double = end.timeIntervalSinceDate(start);

println("Result: \(result) found in \(timeInterval) seconds")

I find it confusing that you first assign an empty string and then append to it. I suggest returning directly, like

// var words:String = "" Delete this

if number >= 0 && number <= 19 {

    return unitNames[number]

And a return for each branch. When I see a return I can rest my mind that the function has ended, if I see a string appending, maybe it will grow more before being returned.

The line:

 let end = NSDate();

Inside Euler17 should be deleted as it is useless.

Euler17 can be simplified a lot.

return (1...1000).map{count(convertIntegerToWords($0)}.sum

Use functional programming where it is worth it.

 var digits = number.array

Should be at the start of the function as you repeat it in almost every branch.

About @jimbo 's comment:

  For speed, I'd put the >= 100 && number <= 999 as the first > if, because 899 times out of 999, that'll be the one that's hit, > > and you don't want that being the last one.

Do not do it. Readibility will decrease and the performance impact will likely be minimal (benchmark needed).


Am I over-reacting with my page SESSIONS security? In order to secure my page SESSIONS I have the following pages.

My questions are

Am I over-reacting with this?
Should I place the token in login.php instead of the loginForm.php ?
When a user logins, I save his IP in the DB. Should I make use of this in authentication ?

Thank you community.

Login form loginForm.php

$token = md5(uniqid(rand(),TRUE));
<input name="login" type="text" class="textfield" id="login" />
<input name="password" type="password" class="textfield" id="password" />
<input type="hidden" name="token" value="<?php echo $token; ?>" />
<input type="submit" name="Submit" value="Login" />

When the user logins login.php

$fingerprint = sha1('SECRET-SALT'.$_SERVER['HTTP_USER_AGENT'].$_SERVER['REMOTE_ADDR'].$_POST['token']);
    session_regenerate_id();
    $member = mysql_fetch_assoc($result);
$_SESSION['SESS_MEMBER_ID'] = $member['member_id'];
$_SESSION['SESS_TOKEN'] = $_POST['token'];
$_SESSION['SESS_FINGERPRINT'] = $fingerprint;
session_write_close();
    header("location: index.php");
    exit();

Authenticating on every page auth.php

    session_start();
    $fingerprint = sha1('SECRET-SALT'.$_SERVER['HTTP_USER_AGENT'].$_SERVER['REMOTE_ADDR'].$_SESSION['SESS_TOKEN']);
    if( !isset($_SESSION['SESS_MEMBER_ID']) || (trim($_SESSION['SESS_MEMBER_ID']) == '')  || ($_SESSION['SESS_FINGERPRINT'] != $fingerprint) || !isset($_SESSION['SESS_TOKEN']) || (trim($_SESSION['SESS_TOKEN']) == '') ) {
        header("location: denied.php");
        exit();
    }

1) Overreacting is a question of how valueable your protected information is. My personal oppinion is that by the nature of digital computers and of the internet there is no such thing as overreacting in security. You either want something to be public or you do not, and in the latter case there is quite a bit of work and knowledge involved to counter all the different attacks. On the other hand, a lot of other people will say that if your protected information is not really valueable enough to hackers, then probably no hardcore hacker will invest enough time so your protection might not worth your programming efforts.

2) In the code above you build your fingerprint by hashing a concatenation of different information about the remote user and the token is used as a kind of salt (in addition to 'SECRET-SALT') to make that hash unique. So the answer depends on how secure is your session storage.

If you are alone on the server or you have a secure session storage for $_SESSION (like a password-protected database), then you do not need to worry about someone reading the contents of your session variables. This also means that protecting your fingerprint by hashing it is absolutely useless, in which case you can just remove the token and hashing from your code completely. In this case you also do not need a fingerprint, you can just store the user variables separately and compare them separately.

If there is a way for your $_SESSION contents to leak, then you want to protect private information in it. In this case you will want to keep your token private and do not send it to the user, put it into login.php instead. Normally, you do not have to worry about protecting a salt because even if it is known it will increase the time considerably for a hacker to crack a password, not just because of the longer password string but also because precomputed rainbow tables become useless. But in your case you do not have a password, all you have is the user_agent and the IP, both of which are easily predictable or sniffable. This means that the concatenated information is basically no variable to the hacker, so the only thing keeping him from cracking your fingerprint are your salts. So if you reveal them, the hash becomes useless.

To sum it up: If you want maximum securty in all situations, keep fingerprinting and hashing, but since your protected string is easily guessable, keep your token private this time. Theoretically even if your token is compromised 'SECRET-SALT' will still provide protection, but only as long as your code is safe. If your filesystem is hacked or the sources for the website your are building are public you cannot rely on 'SECRET-SALT' alone. Do not depend on hiding it, 'security by obscurity' is a bad practice.

3) Generally you should not depend on the IP to stay consistent across a session. This is because for a lot of legitimate users the IP can keep changing constantly, this can be because they are behind corporate load balancing, they are using AOL or some other proxy network. A possible solution is to observe the IP of a session and if it is consistent for, say, 10 pages, then it is reasonable to assume that it will stay consistent in the future. So only then will you start making checks on it. However, storing it temporarily in a DB can still be of use, eg. for logging so that it can be analyzed what happened if there is an attack or so.


Extracting performance statistics from FTP session transcript I've borrowed and written the following code to output the disconnect time. All works well but I'm curious as to how I could tighten/ shorten the code. If anyone feels like having some fun then I'd love to see what can be done. Be a learning lesson for me.

Excerpt of input:

ftp> !:--- FTP commands below here ---
ftp> lcd C:\Utilities\Performance_Testing\
\Utilities\Performance_Testing\: File not found
Verbose mode On .
ftp> verbose
binary
200 Switching to Binary mode.
ftp> put "test_file_5M.bin"
200 PORT command successful.
150 Ok to send data.
226 File receive OK.
ftp: 5242880 bytes sent in Seconds Kbytes/sec.
ftp> 44.81117.00disconnect
221 Goodbye.
ftp> bye

Code:

#Obtain UT external put value.
ut1intput=$(awk '
  NR==70 {
    for(i=1;i<=NF;i++) {
      if($i=="ftp>") {
        sub(/disconnect/, "", $(i+1));
        print $(i+1)
      }
    }
  }' filename.txt)

utintputvalue=`echo $ut1intput | awk -F. '{print $2"."$3}'| sed  's/^..//'`

Output:

utintputvalue is 117.00

Assuming the "Output" section is stored in "filename.txt", and assuming you have GNU tools:

grep -oP '(?<=\.\d\d)\d+\.\d\d(?=disconnect)' filename.txt

That's a perl regex meaning: prececeded dot and two digits, find some digits, a dot and two digits, followed by "disconnect". grep's -o option means "output only the matched text".


Project Euler problem 11, finding adjacent numbers with the greatest sum The full description of the problem to solve can be found here. The code I have written works fine but seems extremely verbose for what it's doing, I'm not sure if list comprehensions are meant to be used in the way that I have (maybe some kind of other construct would be more suitable?). Would be great for there to be a way to make the numberPairs function to be more DRY.

Also get the sense that I don't use function composition enough . and instead use $ for most nested function calls. Is this bad practice? How could I rewrite some of the functions in this using composition?

I am fairly new to Haskell so am unaware of any typical coding practices.

gridOfNumbers evaluates to a string containing the grid numbers from the problem with each number in a row separated by spaces and each row separated by newlines. Didn't seem worth including here (although I may be mistaken).

-- | In the `gridOfNumbers` find the 4 adjacent numbers in the given
-- | direction that have the greatest sum.
problem_11 :: Direction -> Int
problem_11 dir =
    maximum $ map (\(x1,x2,x3,x4) -> product $ x1:x2:x3:x4:[]) $ numberPairs dir

data Direction = UpDown | SideWays | LeftStartDiagonal | RightStartDiagonal

numberPairs :: Direction -> [(Int,Int,Int,Int)]
numberPairs UpDown =
    [(x1,x2,x3,x4) |
     currentRow <- [0..16],
     currentCol <- [0..19],
     let x1 = (listifyGrid !! currentRow) !! currentCol,
     let x2 = (listifyGrid !! (currentRow + 1)) !! currentCol,
     let x3 = (listifyGrid !! (currentRow + 2)) !! currentCol,
     let x4 = (listifyGrid !! (currentRow + 3)) !! currentCol]
numberPairs SideWays =
    [(x1,x2,x3,x4) |
     currentRow <- [0..19],
     currentCol <- [0..16],
     let x1 = (listifyGrid !! currentRow) !! currentCol,
     let x2 = (listifyGrid !! currentRow) !! (currentCol + 1),
     let x3 = (listifyGrid !! currentRow) !! (currentCol + 2),
     let x4 = (listifyGrid !! currentRow) !! (currentCol + 3)]
numberPairs LeftStartDiagonal =
    [(x1,x2,x3,x4) |
     currentRow <- [0..16],
     currentCol <- [0..16],
     let x1 = (listifyGrid !! currentRow) !! currentCol,
     let x2 = (listifyGrid !! (currentRow + 1)) !! (currentCol + 1),
     let x3 = (listifyGrid !! (currentRow + 2)) !! (currentCol + 2),
     let x4 = (listifyGrid !! (currentRow + 3)) !! (currentCol + 3)]
numberPairs RightStartDiagonal =
    [(x1,x2,x3,x4) |
     currentRow <- [0..16],
     currentCol <- [3..19],
     let x1 = (listifyGrid !! currentRow) !! currentCol,
     let x2 = (listifyGrid !! (currentRow + 1)) !! (currentCol - 1),
     let x3 = (listifyGrid !! (currentRow + 2)) !! (currentCol - 2),
     let x4 = (listifyGrid !! (currentRow + 3)) !! (currentCol - 3)]

listifyGrid :: [[Int]]
listifyGrid = map (map read) doubleListOfStrings
    where doubleListOfStrings = map (S.split " ") $ lines gridOfNumbers

The code I have written works fine but seems extremely verbose for what it's doing ... Would be great for there to be a way to make the numberPairs function to be more DRY.

I agree that there's a fair bit of repetition happening. This makes things very explicit, but at the cost of more boilerplate, as you said.

I suggest that the movement patterns for each direction be separated from the actual functionality of extracting a "line" of adjacent numbers from the board. That way, it's easier to see the differences between each direction:

quads :: Direction -> [[Int]]
quads UpDown
    = getLines 4 [0..16] [0..19] succ id
quads SideWays
    = getLines 4 [0..19] [0..16] id succ
quads LeftStartDiagonal
    = getLines 4 [0..16] [0..16] succ succ
quads RightStartDiagonal
    = getLines 4 [0..16] [3..19] succ pred

I've renamed numberPairs to quads because "pair" usually refers to a 2-tuple. succ and pred are just equivalent to (+ 1) and (- 1).

Now you can define getLines more generally (albeit with an uglier signature), in terms of iterating the row and column position with the supplied rowFn and colFn:

getLines :: Int -> [Int] -> [Int] -> (Int -> Int) -> (Int -> Int) -> [[Int]]
getLines n rows cols rowFn colFn =
    [line |
     row <- rows,
     col <- cols,
     let coordPairs = zip (iterate rowFn row) (iterate colFn col),
     let line = take n $ map gridGet coordPairs]

gridGet :: (Int, Int) -> Int
gridGet (row, col) = listifyGrid !! row !! col

This is just rearranging your code, except that I've used [Int] instead of (Int,Int,Int,Int) as the type of each number line. I'm not an experienced Haskeller, but I think that, here, the list is considerably easier to deal with than the tuple, at the expense of giving up an explicit length guarantee.

Using a list also makes it easy to adapt to other lengths than 4, since it's just a take n. The tuple code, at least structured as you have it right now, would grow linearly.

  Also get the sense that I don't use function composition enough . and instead use $ for most nested function calls. Is this bad practice? How could I rewrite some of the functions in this using composition?

Again, keeping in mind that I haven't done a whole lot of Haskell: I don't see anywhere in your code where $ looks out of place.

One place where composition is nice, though, is with map and nested lists. This:

listifyGrid :: [[Int]]
listifyGrid = map (map read) doubleListOfStrings
    where doubleListOfStrings = map (S.split " ") $ lines gridOfNumbers

could use composition if you want, as well as the words function:

listifyGrid = (map . map) read $ map words $ lines gridOfNumbers

(map . map) is so elegant that the equivalent in Python, for example, just seems obtuse. Oh, Haskell, you charmer.

Anyway, the main problem_11 function:

problem_11 :: Direction -> Int
problem_11 dir =
    maximum $ map (\(x1,x2,x3,x4) -> product $ x1:x2:x3:x4:[]) $ numberPairs dir

can also be defined as a pointfree composition, if that's your style, especially now that we can use map directly without unwrapping the tuple:

problem_11 = maximum . (map product) . quads


Can casting to fragment be more efficient than using a variable? I'm new to using fragments in Android. I'm working on an app using a sliding panel layout and I just came up with an idea for changing my fragments. I decided to create the following method:

    private void changeFrag(Object newFrag){
        // Insert the fragment by replacing any existing fragment
        FragmentManager fragmentManager = getSupportFragmentManager();
        fragmentManager.beginTransaction()
        .replace(R.id.fragment_secondpane, (Fragment) newFrag).commit();
    }

I'm calling the method in the following way:

    changeFrag(new myFragment());

Could this cause problems for me in the long run? I was hoping that by writing it this way, I could avoid extra code and hopefully cut down on any extra processing power the device would need for something like this:

        Fragment frag;
        frag= new myFragment();

        // Insert the fragment by replacing any existing fragment
        FragmentManager fragmentManager = getSupportFragmentManager();
        fragmentManager.beginTransaction()
        .replace(R.id.fragment_secondpane, (Fragment) frag).commit();

You could make it more dynamic. Because this method adds the Fragment only to the R.id.fragment_secondpane layout. If this is all what you desire, it's ok. Otherwise add a parameter for the layout. This way you can use your method to add a Fragment to different layouts.

Because every type of Fragment like ListFragment, DialogFragment or even a SherlockFragment is using Fragment as super class, you can use Fragment as the parameter type. There's no need to use Object. Note that you should avoid to mix the Fragment types of different librarys.

With methods like this you can avoid extra code in this situation, replacing different Fragments of a specific layout.

The processing will be the same. The creation of the necessary objects have to be done. There will be no difference if this happens in e.g. onCreate or the method you wrote. The only thing you could avoid is to hold an extra reference of the FragmentManager.

To sum all up you would have something like this:

private void changeFrag(int layout, Fragment newFrag){

    getSupportFragmentManager() // gets the FragmentManager of the Activity, no need to hold a reference
         .beginTransaction()
         .replace(layout, newFrag) // use the layout and the fragment, no need for a cast
         .commit();

}

Note that this method will work and is straightforward. If you have an approach with adding some Fragments to the backstack and some not or using different kind of animations, your method will be more complex and lacks performance. That's why I would not use this in every situation.


Directory that lists employee information I'm working on a directory that lists employee information.  Each employee can belong to multiple departments and each employee can have multiple job titles.  I have 5 MySQL tables that I am pulling information out of, including:

employee
employee_has_department
department
employee_has_jobTitle
jobTitle

The employee table has a many-to-many relationship with department and jobTitle.  I currently have nested queries, as follows:

$stmt = $mysqli->prepare("SELECT employeeId, firstName, middleName, lastName, suffix, profilePhoto FROM employee");
$stmt->execute();
$stmt->store_result();
$stmt->bind_result($employeeId, $firstName, $middleName, $lastName, $suffix, $profilePhoto);
while($stmt->fetch()){

  echo "
$firstName
";

  $stmt2 = $mysqli->prepare("SELECT jobName FROM jobTitle INNER JOIN employee_has_jobTitle ON jobTitleId = jobTitle_jobTitleId WHERE employee_employeeId = ?");
  $stmt2->bind_param("i", $employeeId);
  $stmt2->execute();
  $stmt2->store_result();
  $stmt2->bind_result($jobName);
  while($stmt2->fetch()) {
    echo "$jobName
";
  }

  $stmt3 = $mysqli->prepare("SELECT departmentName, departmentURL FROM department INNER JOIN employee_has_department ON departmentId = department_departmentId WHERE employee_employeeId = ?");
  $stmt3->bind_param("i", $employeeId);
  $stmt3->execute();
  $stmt3->store_result();
  $stmt3->bind_result($deptName, $deptURL);
  while($stmt3->fetch()) {
      echo "$deptName";
  }
}

Clearly the output needs formatting, but it's getting the information and outputting as expected.  I know that this can probably be done in a single sql statement, but the complexity and ugliness of performing a join on 5 separate tables with multiple many-to-many relationships leaves me wondering.  Would taking the time to figure out such a query worth the hassle, or is this an "acceptable" way of handling the situation?

The answer is that there is a definite performance gain in having it all in a single join. Just the reduction in back and forth should greatly decrease the latency, and the database engine should be way more effective.

For a more general view on that topic :

Will the request be hard to understand later ? This is the most important question, as it will be the difference between maintainable code and code nobody will dare touch. In this particular case, I would say there is an obvious request to write, and that it will be fairly easy to understand. If you don't feel this is the case, then you probably should not go this way (premature optimization, etc.).
How complex will be the whole solution ? Displacing logic from PHP to SQL is often a good idea, but might have drawbacks :

hidden logic (triggers, or opaque stored procedures) that is hard to understand later
vendor lock-in (when using advanced features that are not standard).
poor performance : with complex queries, it becomes hard to evaluate the run-time performance

It seems to me that a straightforward 5 tables join is far from complex, and is a lot less ugly than the PHP code displayed here. You would get rid of all the content of the while loop ...
How much will the performance be impacted ? For a low-traffic web application, which is the most common case, this should be the last concern.


Rails preventing ajax view duplication I have a website where people can write articles and publish/unpublish them. This is done via single button on the page:

<a id="publish-button" href="#" class="btn btn-default <%= 'btn-success' if @article.published? %>">

As you can see, if an article is already published I'm adding additional btn-success class.

Now, this is the JavaScript code that handles Ajax clicks on that button:

var $editor = $('#editor'); // Article container, it contains update action url as data-url
var $publishButton = $('#publish-button');
var togglePublished = function () {
  var url = $editor.data('url');

  var postData = {
    article: {
      stage: $publishButton.hasClass('btn-success') ? 'unpublished' : 'published'
    },

    _method: 'PUT'
  };

  $.ajax({
    url: url,
    data: postData,
    method: 'POST',
    success: function (article) {
      $publishButton['published' == article.stage ? 'addClass' : 'removeClass']('btn-success');
    }
  });
};
$publishButton.click(function (e) {
  e.preventDefault();
  togglePublished();
});

My controller action just returns a JSON encoded article in this case:

def update
  if @article.update(article_params)
    render json: @article
  else
    render json: { errors: @article.errors.full_messages }, status: :unprocessable_entity
  end
end

There are few things I see wrong with this:

My post data depends on class, which can be changed and changing it would require me to change it on two places: in template and in JS.
If I add data-published attribute to the button I would still have to add/remove class after Ajax has finished resulting in duplicated view logic (in HTML file and JS file).

I can see two ways to avoid this and be DRY:

Add conditional class only in JavaScript and run check upon page load

This would be fairly easy to do but would result in a brief delay because conditional class would be added in JavaScript which runs after all HTML has already loaded.

Extract button to partial view and return it from controller in Ajax

This seems like a more solid approach but since my update action is used in other places too it has to return article as JSON. That's why I would have to create another controller action:

def toggle_published
  @article.toggle_published # Something like this
  render partial: '_publish_button'
end

This reduces "restfulness" of my controller and it seems kind of silly to extract only one HTML element into a partial view.

Is there any better way to do this? It seems like a minor and insignificant code duplication but it's not an isolated example and as website complexity grows these things can multiply a lot and cause a lot of headaches.

You could theoretically overload the show action to only return the partial if request.xhr?. So if it's an ajax request, only render that button partial. But that's inelegant.

Alternatively, you can simply keep the default show action, send the entire page back, and just pluck out the button element (similar to how Turbolinks work). It'll keep the controller RESTful and keep the update-magic in the JS only. The trade-off is that you'll be rendering stuff that you won't actually use for anything. However, you can avoid some of it by disabling layout rendering for XHR requests (which is somewhat less kludgy than just rendering a partial; at least you're still rendering the show template).

However, having the publish button's state just defined by its color doesn't sounds like a very clear UI to me. Does a (presumably) green button mean "not published; clicking will publish" or "already published; clicking will unpublish"? I'd much prefer the button actually having a verb on it like "Publish" or "Unpublish" (or whatever you'd call it), so it's clear what the button will do.

Regardless, using the btn-sucess class gives you the desired look, but it's semantically meaningless. The class name doesn't really describe the current state or the action the button will take.

Picking the "re-render the show template"-option above will give you a chance to re-render the entire post with a published class. Then you can have a CSS rule like:

#post.published #publish-button {
  // set color etc.
}

Not as simple as using the generic btn-success class, but to me it makes more sense to track the state for the post as a whole, rather than a single button.

I imagine something like this for the view

<article id="post_123" data-url="..." class="<%= 'published' if @article.published? %>">

...

    ...

That'll mean that the element with the update URL is the same element that should be replaced by whatever is being sent back from the ajax-request. The JS only really needs to know that rule: Update the element with the data-url attribute. It doesn't need to know the specifics of re-styling individual elements.

Even if you don't go that route, toggling a published class in both view and JS is at least more readable/straight-forward that toggling a semantically unrelated class like btn-success.


Merge Sort using vector c++ I'm learning c++ and I know some algorithms and data structures. I was wondering what is the best way to do merge sort for a vector in c++.
// will write a program for merge sort
/* steps:
 * have an array of size n call it A
 * divide A into left and right halves L and R
 * call merge sort on the two halves now L' and R'
 * now merge the two halves into B (the sorted version of A)
 */
/* the merging algorithm:
 * the merging algorithm is a "two finger algo"
 * where an element of L' is compared with each elt of R' until the elt in R' is less
 * we then take this element and put it into our sorted array, B
 */
#include <iostream>
#include <vector> // will use the vector class  to make things like list slicing very easy

using namespace std;
void merge_sort(vector<int> &arr);
void merge(vector<int >&left, vector<int> &right, vector<int> &results);

int main() {
    vector<int> my_vector{10, 30, 50, 40};
    merge_sort(my_vector);

    for (int i: my_vector)
        cout << i << ',';
    return 0;
}

void merge_sort(vector<int> & arr) {
    if (arr.size() <= 1) return;

    int mid = arr.size() / 2;
    vector<int> left(arr.begin(), arr.end() - mid);
    vector<int> right(arr.begin() + mid, arr.end());

    merge_sort(left);
    merge_sort(right);
    merge(left, right, arr);
}
void merge(vector<int> &left, vector<int> &right, vector<int> &results)
{
    int L_size = left.size();
    int R_size = right.size();
    int i = 0, j = 0, k = 0;
    // two finger algorithm
    while (j < L_size && k < R_size)
    {
        if (left[j] < right[k]) {
            results[i] = left[j];
            j++;
        }
        else {
            results[i] = right[k];
            k++;
        }
        i++;
    }
    while (j < L_size) {
        results[i] = left[j];
        j++; i++;
    }
    while (k < R_size) {
        results[i] = right[k];
        k++; i++;
    }
}
```

Overall
Looks good overall.
The design works perfectly for sorting integers. But in C++ we can potentially sort anything. So why not allow your sorting algorithm to work with any sortable type.
To do this learn templates:
 void merge_sort(vector<int> &arr);

 // Change to:

 template<typename T>
 void merge_sort(vector<T>& arr);

The next thing to think about is that vector<> is not the only thing that can be sorted. There are lots of container types that can be sorted. Normally we don't care about the container type and we abstract the container away and specific what what we want to sort in terms of iterators.
So the next subject to learn are iterarators'. Then you can specify what you want to sort in terms of the beginning and end of a range.
template<typename I>
void merge_sort(I begin, I end);

The next thing you should think about is the memory requirements your algorithm uses. Currently your algorithm uses 2 times the current size of the array you want to sort (in addition the vector). You can change this so you only use 1 times the current size of the vector.
To achieve this you want to allocate the memory once outside the recursive sort function then pass in this temporary memory into the merge sort.
// The wrapper
template<typename I>
void merge_sort(I begin, I end)

    // Create a single buffer are to be be re-used.
    std::vector<int>  tmpData(std::distance(begin, end));

    merge_sort_with_buffer(begin, end, std::begin(tmpData) std::end(tmpData));
}

template<typename I1, template I2>
void merge_sort_with_buffer(I1 b , I1 e, I2 tb, I2 te)
{
    std::size_t s = std::distance(begin, end);

    if (s < 2) {
        return;
    }

    I1 m   = std::next(begin, s/2);
    I2 tm  = std::next(tBegin, s/2);

    merge_sort_with_buffer(b, m, tb, tm);
    merge_sort_with_buffer(m, e, tm, te);
    merge(tb, tm, te, b);
}

template<typename I2, template I1>
void merge(I2 tb, I2 tm, I2 te, I1 dst)
{
    // copy tb->tm
    // copy tm->te
    //
    // To the destination
}

Code Review
Not a fan of bad comments:
#include <vector> // will use the vector class  to make things like list slicing very easy

Do you use slicing?

Stop doing this:
using namespace std;

It might be useful in books where space is limited. But in real code it actually causes problems. I recomend you stop using it because it becomes a habit. This is a bad one. When you have a bad habit you will just use it without thinking and accidentally cause on f the problems.
See: Why is “using namespace std;” considered bad practice? Personally I find the second answer the best.

In C++ it is more normal to put the & with the type in the declaration.
void merge_sort(vector<int> &arr);

// Like this:

void merge_sort(vector<int>& arr);

Note: This is the opposite of what is common in C.

Please always add the curly craces '{}'
    for (int i: my_vector)
        cout << i << ',';

    // Like this:

    for (int i: my_vector) {
        cout << i << ',';
    }

The trouble is people still make silly macros that are multiple lines. Not using the braces can put you in funny situations where only part of your code is executed by the loop when you least expect it.
More importantly to me it makes it much simpler to read.

In C++ the last return in main() is not needed.
    return 0;

If you don't provide one the compiler automatically adds a return 0 at the end of main.
It has been common practice to not include a return 0 if main does not ever return anything else. So if I see a return 0 at the end I start looking for other error detection code that would return another value.

This is a subtle one:
        if (left[j] < right[k]) {

If you use the less here then if they are equal you will choose the one from the right. Keep that in mind.
There is an important mathematical principle around sorting called "Stability" (when sorting). If items that are equal retain there original relative order the sort is considered stable otherwise it is not.
If you choose from the right when the items are equal your algorithm is not stable. So by using <= you automatically make your algorithm stable.
        if (left[j] <= right[k]) {

Note this is a copy operation:
        results[i] = left[j];

Now for integers this makes absolutely no different. But when you make this work for other types this mean copying an object. This can be expensive so we would prefer to use move rather than copy.
        results[i] = std::move(left[j]);

Sure these work.
    while (j < L_size) {
        results[i] = left[j];
        j++; i++;
    }
    while (k < R_size) {
        results[i] = right[k];
        k++; i++;
    }

But much easier to use standard algorithms
    std::copy(&left[j],  &left[L_size],  &result[i]);
    std::copy(&right[k], &right[R_size], &result[i]);

But then we remember that we want to use move rather than copy.
    std::move(&left[j],  &left[L_size],  &result[i]);
    std::move(&right[k], &right[R_size], &result[i]);


How to shorten two methods with the same theme? I have this code:

private void numWidth_ValueChanged(object sender, EventArgs e)
{
    if (ignoreChange) return; // Sometimes I only want to change the value without the event firing (like when undo-ing)

    PushUndoStack();

    int width = (int)numWidth.Value;

    foreach (Layer layer in doc.TileLayers)
        layer.Width = width;

    hscDoc.Maximum = doc.WidthInPixels;
    ClampScrollbarValue(hscDoc);
}

private void numHeight_ValueChanged(object sender, EventArgs e)
{
    if (ignoreChange) return;

    PushUndoStack();

    int height = (int)numHeight.Value;

    foreach (Layer layer in doc.TileLayers)
        layer.Height = height;

    vscDoc.Maximum = doc.HeightInPixels;
    ClampScrollbarValue(vscDoc);
}

They are both very similar yet I can't really think of a good way to combine the two. This happens several times in my program and the lines of code are really adding up. I suppose I could use reflection but is it overkill? Can anyone think of a better way?

This is just an example. This happens quite a few times in my program where functions are very similar but cannot be easily refactored in to a generic method.

Something along these lines:

private void ValueChangedImp(object sender, EventArgs e, Func<int> get_value, Action<Layer, int> set_value, Func<int> get_pixels)
{
    if (ignoreChange) return; // Sometimes I only want to change the value without the event firing (like when undo-ing)

    PushUndoStack();

    int value = get_value();

    foreach (Layer layer in doc.TileLayers)
        set_value(laywe, value);

    hscDoc.Maximum = get_pixels();
    ClampScrollbarValue(hscDoc);
}

private void numWidth_ValueChanged(object sender, EventArgs e)
{
    ValueChangedImp(sender, e, () => (int)numWidth.Value, (layer, value) => layer.Width = value, () => doc.WidthInPixels);
}

private void numHeight_ValueChanged(object sender, EventArgs e)
{
    ValueChangedImp(sender, e, () => (int)numHeight.Value, (layer, value) => layer.Height = value, () => doc.HeightInPixels);
}


Optimizing this matrix shifter I need to optimize this piece of code I made because this will run in real-time mode.

It's a matrix shifter that pulls downward and will neglect any transparent element.

Code:

void shiftDown(int col)
{
    int x = 0;  //transparent element
    int N = 5;  //size
    int i,j,k,l;

    for ( i = N - 1;i >= 0; --i )
    {
        if( map[i][col] == x )
        {
            for( j = i;j >= 0; --j )
            {
                if ( map[j][col] != x )
                {
                    for ( l = i, k = j;l >= 0; --l, --k )
                    {
                        map[l][col] = map[k][col];
                    }
                }
            }
        }
    }
}

Data:

(before)

0 2 3 2 0
0 1 4 0 1
1 2 2 0 3
2 1 0 0 4
4 3 1 1 3

(after)

0 2 0 0 0
0 1 3 0 1
1 2 4 0 3
2 1 2 2 4
4 3 1 1 3
    ^ ^

Other code

int map[][5] =
{
  {0, 2, 3, 2, 0},
  {0, 1, 4, 0, 1},
  {1, 2, 2, 0, 3},
  {2, 1, 0, 0, 4},
  {4, 3, 1, 1, 3}
};

void printMap();
void shiftDown(int col);

int main()
{
    cout << "before\n";
    printMap();

    for (int i = 0;i < 5; ++i)
    {
        shiftDown(i);
    }
    cout << "after\n";
    printMap();

    cin.get();
    return 0;
}

void printMap()
{
    for (int row = 0;row < 5; ++row)
    {
        for (int col = 0;col < 5; ++col)
        {
            cout << map[row][col] << '\t';
        }
        cout << endl << endl << endl << endl;
    }
}

Note: Looked at my comment again and I need to correct my error. Its int map[N][N] again. This will not work for M x N matrix.

You can sort each column separately (only move the transparent value to the top of the column) with a fast sorting algorithm like merge sort:

void mergeSortBlock(int *a, int index1, int index2, int size, int transparent){
    int *result;
    int resultIndex = 0;
    int mergeIndex1 = index1;
    int mergeIndex2 = index2;

    result = new int [size*2];

    while (mergeIndex1 <= (index1 + size -1) && mergeIndex2 <= (index2 + size -1)){
        if (a[mergeIndex2] == transparent) {  // check the transparency
            result[resultIndex] = a[mergeIndex2];
            resultIndex++;
            mergeIndex2++;
        }
        else {
            result[resultIndex] = a[mergeIndex1];
            resultIndex++;
            mergeIndex1++;
        }
    }

    if (mergeIndex2 <= (index2 + size - 1)) {
        for (int i = mergeIndex2 ; i< (index2 + size); i++) {
            result[resultIndex] = a[mergeIndex2];
            resultIndex++;
            mergeIndex2++;
        }
    }
    else{
        for (int i = mergeIndex1 ; i< (index1 + size); i++) {
            result[resultIndex] = a[mergeIndex1];
            resultIndex++;
            mergeIndex1++;
        }
    }

    // copy the result back
    for (int i=0; i < size*2; i++) {
        a[index1+i] = result[i];
    }
    delete [] result;
}

void mergeSort(int *a, int indexFront,int indexEnd, int transparent){
    int size = (indexEnd - indexFront +1)/2;
    if (size > 1){
        mergeSort(a, indexFront, indexFront + size - 1, transparent);
        mergeSort(a, indexFront + size, indexEnd, transparent);
    }
    mergeSortBlock(a, indexFront, indexFront + size, size, transparent);
}

As you can see, in the mergeSortBlock function, instead of examining a[mergeIndex1]>a[mergeIndex2] you check the transparency condition.

the indexFront is the index of the first element of your array and indexEnd is the index of the last element.

Now in your main, first you need to transpose the matrix so that the ith row of the transposed matrix (called result in this example) represents the ith column of your map matrix. then call the mergeSort function for each row of the transposed matrix, Result .

int  main()
    int result[5][5];
    int map[][5] =
    {
        {0, 2, 3, 2, 0},
        {0, 1, 4, 0, 1},
        {1, 2, 2, 0, 3},
        {2, 1, 0, 0, 4},
        {4, 3, 1, 1, 3}
    };

    //transpose map => map's ith column = result's ith row
    for (int i = 0; i<5; i++)
        for (int j = 0; j<5; j++)
            result[j][i] = map[i][j];

    for (int i=0; i<5; i++)
        mergeSort(result[i],0,4,0);

    //transpose reuslt => result's ith row = map's ith column
    for (int i = 0; i<5; i++)
        for (int j = 0; j<5; j++)
            map[j][i] = result[i][j];

    return 0;
}

At the end again we need to transpose the matrix result.

Note: The complexity of merge sort is O(n.logn). You have n columns. This makes the complexity of the matrix shifter O(n^2.logn). Thanks to the nature of your problem, you can still improve this by parallel programming (of course if you have multiple processors). The complexity of transpose is O(n^2). The complexity of your own algorithm is O(n^3).

Note2: You can modify mergeSort and mergeSortBlock functions to work directly with the columns of your matrix.


Transactionally create something, if allowed I have been looking over this block of code for hours trying to simplify it. Would there be a better way to check all those conditions before creating a transaction object without using so many if-elses?

def create(self, validated_data):

    user = self.context['request'].user
    if user.role == 'super_admin':  # ref PR 25.1
        return Transaction.objects.create(**validated_data)
    elif user.role == 'user' or user.role == 'org_admin' or user.role == 'site_admin':  # ref PR 25.4
        if check_user_institution_exists(validated_data['user_institution'].id):
            if check_user_belongs_to_institution(validated_data['user_institution'].id, None, user.id) > 0:
                if check_upload_permission(validated_data['user_institution'].id):
                    return Transaction.objects.create(**validated_data)
                else:
                    raise serializers.ValidationError({'Error': 'You do not have upload permission for this '
                                                                'institution.'})
            else:
                raise serializers.ValidationError({'Error': 'You do not belong to this institution.'})
        else:
            raise serializers.ValidationError({'Error': 'This user institution does not exist.'})
    else:
        raise serializers.ValidationError({'Error': 'You are not assigned a role.'})

You don't need to use elif you can change that to just an if.
You can simplify code blocks by using guard clauses that have the following layout:

if a:
    ...
else:
    raise b

To:

if not a:
    raise b

...

You can use a in [b, c] rather than a == b or a == c.
As commented by Michel Billaud, "The code will be shorter with an auxiliary variable id = validated_data['user_institution'].id".

Employing the above would get the following which I find to be much easier to read.

def create(self, validated_data):
    user = self.context['request'].user
    if user.role == 'super_admin':  # ref PR 25.1
        return Transaction.objects.create(**validated_data)

    if user.role not in ['user', 'org_admin', 'site_admin']:  # ref PR 25.4
        raise serializers.ValidationError({'Error': 'You are not assigned a role.'})

    id_ = validated_data['user_institution'].id
    if not check_user_institution_exists(id_):
        raise serializers.ValidationError({'Error': 'This user institution does not exist.'})

    if check_user_belongs_to_institution(id_, None, user.id) <= 0:
        raise serializers.ValidationError({'Error': 'You do not belong to this institution.'})

    if not check_upload_permission(id_):
        raise serializers.ValidationError({'Error': 'You do not have upload permission for this '
                                                    'institution.'})

    return Transaction.objects.create(**validated_data)


Refactoring a collection of if statements that contain 2 arguments. At the moment I have seven if statements that resemble the following code:

if(hit.collider.gameObject.tag == "Colour1" && start_time > look_at_time)
        {
            new_colour1.ChangeObjectMaterialColour(hit.collider.gameObject.renderer.material.color);

            var colums = GameObject.FindGameObjectsWithTag("column");
            foreach( GameObject c in colums)
                c.GetComponent<MeshRenderer>().materials[1].color = new_colour1.orignalMaterial;
        }

        else if(hit.collider.gameObject.tag == "Colour2" && start_time > look_at_time)
        {

            new_colour2.ChangeObjectMaterialColour(hit.collider.gameObject.renderer.material.color);
            var colums = GameObject.FindGameObjectsWithTag("column");
            foreach( GameObject c in colums)
                c.GetComponent<MeshRenderer>().materials[1].color = new_colour2.orignalMaterial;
        }

Each statement is roughly 6 lines of code and takes up a lot of space and can be a little tricky to read. What I'm wanting to do is find a way to re factor this so that my code is little less clunky and doesn't take up too much space.

I had thought about changing my collection of if statements into a switch statement but I discovered that switch statements can't handle two arguments like I have above. If there any other way I can re factor my code but keep the same functionality or am I stuck with my collection of if statements?

We can start looking at what is duplicated.  For example, the only difference between the two blocks of code is the string "Color1" and "Color2" in the if statement, and the variable new_colour1 which is replaced with new_colour2.

From here I'd suggest something like the following:

//This should be declared once - e.g. class level not method level.
var colorDict = new Dictionary<string, NewColorType>
                    {
                        {"Colour1", new_colour1},
                        {"Colour2", new_colour2}
                    };
NewColorType newColor;
if(start_time > look_at_time && colorDict.TryGetValue(hit.collider.gameObject.tag, out newColor))
{
   newColor.ChangeObjectMaterialColour(hit.collider.gameObject.renderer.material.color);
   var colums = GameObject.FindGameObjectsWithTag("column");
   foreach( GameObject c in colums)
      c.GetComponent<MeshRenderer>().materials[1].color = newColor.orignalMaterial;
}


Permutations program in Python This code asks for letters and a number of letters per word and generates all possible permutations. Then compares those permutations with an English dictionary and creates a list with all the words that match with the dictionary. Finally, it prints the list on a new terminal. The problem is that when words are long (about 10 letters each) I run out of memory. Any suggestions to improve this code and to try to solve the memory problem?

EDIT: my aim is to get 'real' words after typing some letters (e.g input: wxtisneo; letters_per_word: 3; output: one, two, six...)

import os
import itertools
import string
import sys
from sets import Set

def check_files():
    if 'all_combinations_list.txt' in os.listdir('/tmp'):
        os.remove('/tmp/real_words.txt')

def factorial_formula(v):
    a = 1
    if v < 0:
        return 0
    elif v == 0:
        return 1
    else:
        for i in range(2, v+1):
            a = a*i
        return a

def combinations_formula():
    w = len(split_letters)
    x = factorial_formula(w)
    y = (w - number_input)
    z = factorial_formula(y)
    total = x / z
    return total

def possible_existing_words():
    dictionary = [i.strip() for i in open('/usr/share/dict/american-english').readlines()]
    raw_all_combinations = list(itertools.permutations(split_letters, number_input))
    all_combinations = [''.join(word) for word in raw_all_combinations]
    real = set(all_combinations).intersection(dictionary)
    real_2 = list(real)
    output_file = open('/tmp/real_words.txt', 'w')
    with open('/tmp/real_words.txt', 'w') as out:
        for e in real_2:
            separated_words = str(e)
            print >>out, separated_words
    os.system("gnome-terminal -e 'bash -c \"cat /tmp/real_words.txt; exec bash\"'")
    print ''' FINISHED
'''

if __name__ == "__main__":
    os.system('clear')
    check_files()
    letter_input = raw_input(' Type in letters: ')
    number_input = int(raw_input(' Letters per word: '))
    split_letters = list(letter_input)
    letter_input
    number_input
    if ' ' in split_letters:
        print '''
 ERROR: White space typed
 '''
        sys.exit()
    elif len(split_letters) < number_input:
        print '''
 ERROR: More letters in word than typed
 '''
        sys.exit()
    print '''

 Creating %s different combinations...''' % combinations_formula()
    print ' Detecting dictionary matches...'
    possible_existing_words()
    sys.exit()

You're first building a list of all permutations of the input word, and then using that to filter the dictionary. The problem with this approach is that the number of permutations is huge — for 10 distinct letters, there are 10! = 3628800 permutations. In comparison, /usr/share/dict/american-english is only about 100k words, and /usr/share/dict/american-english-huge is about 340k — less than 10 times the number of permutations. This kind of pretreatment can be useful, but only if the variable data to be processed afterwards is large or if the amount of computation per data pair is very large, neither of which are the case here.

There's cheap way to check if two words are a permutation of each other: sort their letters. Two words are permutations of one another if and only if sorting their letters returns identical results.

def is_a_permutation(word1, word2):
    return sorted(word1) == sorted(word2)

Here, you only want to see if each dictionary word consists of number_input elements of split_letters. This is the case if the length of the word is number_input and the word is a subsequence (not necessarily consecutive) of split_letters — after sorting both the word and split_letters.

I don't think the Python standard library has a subsequence test (only a substring test, i.e. where the elements must be consecutive). A cheap way to implement it for lists of characters is to build a regular expression and let the regular expression engine build an optimized automaton internally.

def subsequence_re(word):
    return re.compile('.*'.join([re.escape(letter) for letter in sorted(word)]))

That's a tiny precomputation, after which you get cheap processing on each dictionary word. You can then process the dictionary as a stream, so your program will use constant memory with respect to the dictionary size (and linear memory in the size of the target permutation, instead of factorial).

Here's a demo program where I don't copy the whole input logic, I just take the letters from the command line and the dictionary from standard input.

#! /usr/bin/env python
import re
import sys

def subsequence_re(word):
    return re.compile('.*'.join([re.escape(letter) for letter in sorted(word)]))

def filter_file(target_length, target_re, data_file):
    for line in data_file:
        word = line[:-1]
        if len(word) == target_length and \
           re.search(target_re, ''.join(sorted(word))):
            yield word

if __name__ == '__main__':
    target = sys.argv[1]
    for word in filter_file(len(target), subsequence_re(target), sys.stdin):
        print word

There are other ways to test if a word is a permutation of the number_input letters among split_letters. One way is to build a dictionary (in the sense of a Python dict) where the keys are the distinct letters in split_letters and the values are the number of occurrences of each letter. To see if a word matches, build a similar dictionary and check if the number is smaller (entries not in the reference dict count as an immediate failure); note that the word must also have the target length. As a follow-up exercise, implement and benchmark this method.