CLP(FD) labeling on possibly infinite domains As a follow-up to this SO question, I implemented, for my Prolog-based language Brachylog, my own labeling predicate brachylog_equals/2 which is not guaranteed to terminate but works for infinite domains:

brachylog_equals(Z,Z) :-
    brachylog_equals_('init',10,Z).

brachylog_equals_(I,J,'integer':Z) :-
    fd_inf(Z,'inf'),
    fd_sup(Z,'sup')
    -> (
        (
            I = 'init'
            ;
            I \= 'init',
            abs(Z) #>= I
        ),
        abs(Z) #< J,
        label([Z])
        ;
        I2 is J,
        J2 is J*10,
        brachylog_equals_(I2,J2,'integer':Z)
    )
    ;
    fd_inf(Z,'inf')
    -> (
        (
            I = 'init'
            ;
            I \= 'init',
            Z #=< -I
        ),
        Z #> -J,
        label([Z])
        ;
        I2 is J,
        J2 is J*10,
        brachylog_equals_(I2,J2,'integer':Z)
    )
    ;
    fd_sup(Z,'sup')
    -> (
        (
            I = 'init'
            ;
            I \= 'init',
            Z #>= I
        ),
        Z #< J,
        label([Z])
        ;
        I2 is J,
        J2 is J*10,
        brachylog_equals_(I2,J2,'integer':Z)
    )
    ;
    label([Z]).

A few notes about this code:

This predicate is supposed to be used in automatically generated Prolog code, therefore its name does not describe its function but rather follows a convention.
'integer':Z rather than simply Z is simply here to comply with the rest of the project (it is used to check easily the type of arguments in some other predicates)

Here are my worries:

Is this the most idiomatic solution? (i.e. impose a finite bound on the variable where it has an infinite bound, and increase it recursively if backtracking occurs?)
Is this actually correct in all cases? (From what I tested it is, but I'm wondering if I missed some odd domains where it would break)
Is this computationally efficient?

Of course comments on code style (which I know does not respect usual conventions) or code simplication are also welcome.

Before discussing correctness, efficiency and alternative approaches, I first have three smaller suggestions to simplify the predicate a bit:

Its seems I2 is nowhere really needed, you can always simply use J instead.
for  J2, I would stick to CLP(FD) constraints like: J2 #= J*10.
instead of (\=)/2, I recommend to use dif/2.

These changes make the code a bit easier to read and more uniform, and put us into a better position to discuss the remaining issues.


Extension methods to get direct reports from user I have created a few extension methods to get the direct reports of a UserPrincipal as UserPrincipals themselves. This saves the user of the API quite a bit of typing.

public static IEnumerable<UserPrincipal> GetDirectReportUserPrincipals(
    this UserPrincipal userPrincipal)
{
    var directReportDistinguishedNames =
        userPrincipal.GetDirectReportDistinguishedNames();
    var directReportDistinguishedNamesArray =
        directReportDistinguishedNames as string[] ??
        directReportDistinguishedNames.ToArray();
    if (directReportDistinguishedNamesArray.IsNullOrEmpty())
        return null;
    return userPrincipal.Context.FindUsersByDistinguishedNames(
            directReportDistinguishedNamesArray);
}

public static IEnumerable<string> GetDirectReportDistinguishedNames(
    this UserPrincipal userPrincipal)
{
    return userPrincipal.GetProperty(DirectReports).Cast<string>()
        .Where(
            directReportDistinguishedName =>
                !directReportDistinguishedName.IsNullOrWhiteSpace())
        .ToList();
}

public static PropertyValueCollection GetProperty(
    this Principal principal, string propertyName)
{
    return principal.GetAsDirectoryEntry().Properties[propertyName];
}

public static DirectoryEntry GetAsDirectoryEntry(
    this Principal principal)
{
    return principal.GetUnderlyingObject() as DirectoryEntry;
}

public static UserPrincipal FindUserByDistinguishedName(
    this PrincipalContext principalContext, string distinguishedName)
{
    return UserPrincipal.FindByIdentity(
        principalContext,
        IdentityType.DistinguishedName,
        distinguishedName);
}

public static IEnumerable<UserPrincipal> FindUsersByDistinguishedNames(
    this PrincipalContext principalContext,
    IEnumerable<string> distinguishedNames)
{
    return distinguishedNames.Select(
            principalContext.FindUserByDistinguishedName).ToList();
}

Yes, it does take all of those to do this one task, but the task itself can be called with

userPrincipal.GetDirectReportUserPrincipals();

instead of

Converting user principal to dictionary entry.
Getting direct reports property of dictionary entry.
Casting property to string enumerable.
Using each string (distinguished name) to search for a user principal.

Some of these do feel odd, like they are too Linq-heavy or just unnatural ways of accomplishing the goal. The top method GetDirectReportUserPrincipals has an array cast to avoid "multiple enumeration" as ReSharper says. Is that really necessary?

Why are you ToListing your collections when you are returning IEnumerable<T>? Unless you have a good reason (rare) then leave them as IEnumerable

GetAsDirectoryEntry seems redundant - and in fact hides the fact that it could be null, whereas somebody calling as directly will know that null is possible. I note when you call it you do not test for null.

In general I prefer the lamba inputs as short names escpecially when the scope is so small, so do

   .Where( dn=>!dn.IsNullOrWhiteSpace())

instead of

   .Where(
        directReportDistinguishedName =>
            !directReportDistinguishedName.IsNullOrWhiteSpace())


How to improve my list's speed I'm wondering how I could improve my list's element-adding speed or just the whole list implementation.

The adding function first checks if the object is unique. If not, it will just check if the new data is better (the lower the value, the better) than the old one, then swap the values or just skip adding an element.

I have no idea how to make it work faster, but I know that something here is probably done terribly wrong. I need to use that list to add about 3 million elements in less than 4 seconds.

Note: Using std::string in my project is unfortunately forbidden.

#include <iostream>
struct node
{
    long shortestRoute;
    char* name;
    node *next;
    node()
    {
        next = 0;
    }
};
class List  {
public:
    node *first;
    List() { first = 0 ;}
    void add(long shortestRoute, char* name)
    {
        node *node = new node;
        node->name = name;
        node->shortestRoute = shortestRoute;
        if(first == 0)
            first = node;
        else
        {
            node *temp = first;
            while(temp)
            {
                if(!strcmp(temp->name, name) && temp->shortestRoute > shortestRoute)
                {
                    temp->shortestRoute = shortestRoute;
                    return;
                }
                else if (!strcmp(temp->name, name))
                    return;
                else if(temp->next)
                    temp = temp->next;
                else
                    break;
            }
            temp->next = node;
            node->next = 0;
        }
    }
    int size()
    {
        node *temp = first;
        int size;
        if(!first)
            size = 0;
        else
            size = 1;
        while(temp->next)
        {
            ++size;
            temp = temp->next;
        }
        return size;
    }
};
struct City
{
    City() { fastConnection = true; }
    int shortestRoute;
    char* name;
    Vector<char*> citiesSoFar;
    bool fastConnection;

};

If I understand correctly, you wish to maintain a list of places, and record only the shortest route to each place. This means that each time you need to find any duplicate entry, and choose which to keep.

For this task, an unordered list is pretty much the worst choice you could use. Your algorithm is O(n2) (that is, O(n) for adding each of n elements), and while that isn't important for 10 destinations, it's pretty critical for 3 million!

Given that ordering is not critical here, a hash table is really the correct implementation to use. This will get you O(1) insert and lookup, and the added programming complexity and memory use is appropriate for that number of elements. If that's not possible somehow, then second best would be some kind of self-balancing tree.

Finally, it makes no sense to count the length of a large list by iterating the elements. Just increment a counter every time you add an element. A reduction from O(n) to O(1). (In theory, if you add and destroy a lot of elements very frequently, but only query the size once in a blue moon, then my statement is untrue, but I doubt that's the case here.)

As far as your existing implementation goes, it's a bad plan to create the new node and then not use it. Maybe in your implementation a garbage collector will sort it out, but otherwise it'll be a huge memory leak, not to mention wasted effort.


ChocolatesByNumbers- Find the number of N chocolates in a circle Recently, i have been indulging in a lot of codility challenges to improve my coding performance. For each of this exercise, I always aim for simple solutions as opposed to complicated ones that arrive at the same answer . The question is

  Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N − 1.

  You start to eat the chocolates. After eating a chocolate you leave only a wrapper.

  You begin with eating chocolate number 0. Then you omit the next M − 1 chocolates or wrappers on the circle, and eat the following one.

  More precisely, if you ate chocolate number X, then you will next eat the chocolate with number (X + M) modulo N (remainder of division).

  You stop eating when you encounter an empty wrapper.

  For example, given integers N = 10 and M = 4. You will eat the following chocolates: 0, 4, 8, 2, 6.

  The goal is to count the number of chocolates that you will eat, following the above rules.

Write a function:

class Solution { public int solution(int N, int M); }

  that, given two positive integers N and M, returns the number of chocolates that you will eat.

  For example, given integers N = 10 and M = 4. the function should return 5, as explained above.

  Assume that:

  N and M are integers within the range [1..1,000,000,000].
  Complexity:

  expected worst-case time complexity is O(log(N+M));
  expected worst-case space complexity is O(log(N+M))

I am  aware  a similar questions has been asked in java ChocolatesByNumbers
but my question is more directed to C#

public static int PrintNChocolatesInaCircle(int N, int M)
{
    int counter = 1;
    int start = 0;
    int value;
    while ((start + M) % N != 0)
    {
        value = (start + M) % N;
        start = value;
        counter++;
    }
    return counter;
}

Codility scored my code in terms of Correctness 100% but in terms of performance, it takes longer time to process large elements e.g N = (3^9)(2^14), M=(2^14)(2^14) for a large element and going a bit higher the performance declines.

I think to brute force this kind of question is the wrong path to take to begin with.
Quoting the wikipedia on Brute Force Search :

While a brute-force search is simple to implement, and will always find a solution if it exists, its cost is proportional to the number of candidate solutions – which in many practical problems tends to grow very quickly as the size of the problem increases. Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed.

As @WinstonEwert has pointed out, the number of chocolates that you can eat, is related to the least common multiplier. And, here is one fast way of computing it making use of the Euclidean Algorithm :
static int gcf(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

static int lcm(int a, int b)
{
    return (a / gcf(a, b)) * b;
}

Credit to @AffluentOwl's answer
However, LCM is not the final answer, but it is the number of chocolate that we care, we have to divide lcm by M. And, we can simplify all this :
public static int PrintNChocolatesInaCircle(int N, int M)
{
    // these already have a known answer
    if (M == 1) return N;
    if (M == N) return 1;

    int a = N, b = M;
    while (b != 0)
    {
        var temp = b;
        b = a % b;
        a = temp;
    }

    return N / a;
}

Lastly, make sure you respect the requirements :

Write a function:
class Solution { public int solution(int N, int M); }


A non-recursive tuple_element implementation This is basically a non-recursive std::tuple_element implementation.

Note

To make this non-recursive, you must replace std::make_index_sequence with a non-recursive implementation. I left it with std::make_index_sequence in order to reduce the amount of unrelated code.

How it works

deduct has a specialization of deduct_impl that is generated from the index sequence template argument it receives. It is used in order to deduce the type at index in a variadic type template or tuple. It uses the itp_base and itp types.

itp<std::size_t> and itp<std::size_t, T> is an index-type-pair used to expand the variadic indices template with a type variadic template in order to match the generated specialization.

deducer puts it all together by specializing deduct and deduct_impl by using std::conditional_t to generate the correct specialization.

Basically, for std::tuple<void, int, char>, in order to get the type at index 1, it creates itp_base<0>, itp<1, int>, itp_base<2> and passes it to deduct and deduct_impl.

Source code

#include <utility>
#include <tuple>

template <std::size_t index>
struct itp_base {};

template <std::size_t index, typename T>
struct itp : itp_base<index> {};

template <std::size_t index, typename IndexSequence>
struct deduct;

template <std::size_t index, std::size_t... indices>
struct deduct<index, std::index_sequence<indices...>>
{
    template <typename Tuple>
    struct deduct_impl;

    template <typename T, typename... R>
    struct deduct_impl<std::tuple<itp_base<indices>..., itp<index, T>, R...>>
    {
        using type = T;
    };
};

template <std::size_t index, typename... Types>
class deducer
{
private:
    static_assert( index < sizeof...( Types ), "deducer::index out of bounds" );

    template <typename IndexSequence>
    struct deducer_impl;

    template <std::size_t... indices>
    struct deducer_impl<std::index_sequence<indices...>>
    {
        using type = typename deduct<index, std::make_index_sequence<index>
        >::template deduct_impl
        <
            std::tuple
            <
                std::conditional_t
                <
                    std::is_base_of<itp_base<indices>, itp<index, Types>>::value,
                    itp<index, Types>,
                    itp_base<indices>
                >...
            >
        >::type;
    };

public:
    using type = typename deducer_impl<
        std::make_index_sequence<sizeof...( Types )>>::type;
};

Convenience aliases

template <std::size_t index, typename Tuple>
struct tuple_element;

template <std::size_t index, typename... Types>
struct tuple_element<index, std::tuple<Types...>> : deducer<index, Types...> {};

template <std::size_t index, typename... Types>
using tuple_element_t = typename tuple_element<index, Types...>::type;

Test case

#include <iostream>
#include <string>

int main()
{
    using tuple_t = std::tuple<int, void, std::string>;
    static_assert( std::is_same<tuple_element_t<2, tuple_t>, std::string>::value, "!" );
}

Demo

http://coliru.stacked-crooked.com/a/16805356d2578d6d

Your approach on finding the nth element relies on being able to construct a tuple with the first n-1 types being some predictable thing that you can match against. But the types you chose for std::tuple<void, int, char> were, for index 1, std::tuple<itp_base<0>, itp<1, int>, itp_base<2>>.

But we don't actually need to introduce this itp thing to do this, we can simply turn it into std::tuple<void, int, void>. That way, deduct_impl's specialization instead of taking a std::tuple<itp_base<indices>..., itp<index, T>, R...>, we can simplify to:

template <std::size_t>
using make_void = void;

template <typename T, typename... R>
struct deduct_impl<std::tuple<make_void<indices>..., T, R...>>
{
    using type = T;
};

And on the other side, we pass in:

std::tuple<std::conditional_t<(indices == index), Types, void>...>

Same idea, just more direct.

For that matter, we don't even need the tuple! std::tuple is an expensive type to construct at compile-time, so it's best to avoid it entirely. Just pass in the types as a pack (though the following doesn't compile on gcc - though even there you don't need tuple, just use a light wrapper like template <class...> struct typelist;)

template <typename... Ts>
struct deduct_impl;

template <std::size_t>
using make_void = void;

template <typename T, typename... R>
struct deduct_impl<make_void<indices>..., T, R...>
{
    using type = T;
};

and:

using type = typename deduct<index, std::make_index_sequence<index>
>::template deduct_impl
<
    std::conditional_t<(indices == index), Types, void>...
>::type;

A different approach

Another non-recursive way to do this would be through an inheritance tree. We basically take std::tuple<void, int, char> and turn it into a type that inherits from indexed<0, void>, indexed<1, int>, and indexed<2, char>:

template <std::size_t I, typename T>
struct indexed {
    using type = T;
};

template <typename Is, typename ...Ts>
struct indexer;

template <std::size_t ...Is, typename ...Ts>
struct indexer<std::index_sequence<Is...>, Ts...>
: indexed<Is, Ts>...
{};

Then, given a function template constrained on an index, we can pull out the correct type:

template <std::size_t I, typename ...Ts>
struct at_index {
private:
    template <typename T>
    static indexed<I, T> select(indexed<I, T>);

    using impl = indexer<std::index_sequence_for<Ts...>, Ts...>;
public:
    using type = typename decltype(select(impl{}))::type;
};

I don't know which solution is better, but this one is certainly shorter.


Calculator - C++ operator-overloading I am new to object-oriented concepts. The following is my attempt at creating a basic calculator using class and operator overloading concepts. Please review it for improvements. Also, how do I make it more intuitive? I want to display: +,-,*,/ as options and use switch on them.

#include <iostream>
#include <conio.h>

using namespace std;

class calculator
{
    private:
        float val;

    public:
        calculator(): val(0)
        {}

        void getdata()
        {
            cout << "enter number: ";
            cin >> val;
        }

        void showdata()
        {
            cout << "value: " << val << endl;
        }

        calculator operator + (calculator) const;
        calculator operator - (calculator) const;
        calculator operator * (calculator) const;
        calculator operator / (calculator) const;
};

calculator calculator::operator + (calculator arg2) const
{
    calculator temp;
    temp.val = val + arg2.val;
    return temp;
}

calculator calculator::operator - (calculator arg2) const
{
    calculator temp;
    temp.val = val - arg2.val;
    return temp;
}

calculator calculator::operator * (calculator arg2) const
{
    calculator temp;
    temp.val = val * arg2.val;
    return temp;
}

calculator calculator::operator / (calculator arg2) const
{
    calculator temp;
    temp.val = val / arg2.val;
    return temp;
}

void main()
{
    calculator obj1, obj2, obj3;
    char ch;
    int choice;

    obj1.getdata();
    cout << "1st value entered: ";
    obj1.showdata();
    cout << endl;

    obj2.getdata();
    cout << "2nd value entered: ";
    obj2.showdata();
    cout << endl;

    cout << "Input choice as integer: 1: +,   2: -,   3: *,   4:/     ";
    cin >> choice;
    cout << endl;

    switch (choice)
    {
        case 1:
            obj3 = obj1 + obj2;
            break;
        case 2:
            obj3 = obj1 - obj2;
            break;
        case 3:
            obj3 = obj1 * obj2;
            break;
        case 4:
            obj3 = obj1 / obj2;
            break;
        default:
            cout << "Invalid choice! " << endl;
    }

    cout << "Result ";
    obj3.showdata();
    cout << endl;

}

You can also overload operator>> instead of using getdata():

std::istream& operator>>(std::istream& in, calculator& obj)
{
    return in >> obj.val;
}

Similar approach with showdata(), using operator<<:

std::ostream& operator<<(std::ostream& out, calculator const& obj)
{
    return out << "value: " << obj.val;
}

As for your existing overloads, you shouldn't need to return a calculator.  You appear to treat each calculator object as a single value.  This makes each one to appear to be single-use, and the more values you wish to enter, the more objects thus the more code you'll need to have.

What you should do is maintain one object and have val maintained as you enter data.  However, this will also mean that your arithmetic operators aren't needed.  If you wish to keep them, then you'll have to approach this differently.  For instance, you can calculate (not merely input) a final value for different calculators and use those operators to get a new value.  This may look like a needless approach for a simple calculator, but at least you're still able to utilize these arithmetic operators.

Some miscellaneous notes:

Be aware of the issues of using using namespace std.
You don't appear to be using <conio.h>, so just remove it.
You don't need to use std::endl in so many places.  A simple "\n" for outputting a newline should be sufficient.  More info about that here.


Rotating a character upside down and vice versa I have a pretty straightforward task, but I find it hard to figure out how to improve it. The code is pretty straightforward, but rather bad. There are some clarifications / extra details at the bottom. Let's assume the direction of the positive Z axis is (from the screen) towards you, the reader. Let's say I have this character:

Its angle / rotation along the Z axis is 0 initially. What I want it to do is rotate (say anticlockwise) around the Z axis with a particular speed (adjusted by RotationRate). When it reaches a (cumulated/total) rotation of 180, the rotation should stop. At this point the character will be upside down. If I now tap the screen again, the rotation should start again, but in the opposite direction, until it reaches an angle of 0. Now the character will look again like in the original photo above.

private bool Rotating = false;
private bool IsNormalPosition = true;
private float CharacterTargetAngle = 0;
private float RotationRate = 180 * 5;
private float Threshold = 30;

private IEnumerator Rotate()
{
    while (Rotating)
    {
        var angle = transform.eulerAngles;

        if (Mathf.Abs(CharacterTargetAngle - angle.z) < Threshold)
        {
            angle.z = CharacterTargetAngle;
            Rotating = false;

            transform.eulerAngles = angle;
        }
        else
        {
            transform.Rotate(0, 0, RotationRate * Time.deltaTime);
        }

        yield return new WaitForFixedUpdate();
    }
}

// called when user taps screen
public void OnTap()
{
    if (IsNormalPosition)
    {
        CharacterTargetAngle = 180;
    }
    else
    {
        CharacterTargetAngle = 0;
    }

    IsNormalPosition = !IsNormalPosition;
    RotationRate *= -1;

    if (!Rotating)
    {
        Rotating = true;

        StartCoroutine("Rotate");
    }
    else
    {
        StopCoroutine("Rotate");
        StartCoroutine("Rotate");
    }
}

Other details / clarifications:

Note that if the character is still rotating and I tap the screen again, I want its current rotation to stop and change direction immediately. For this I am setting a Rotating flag. If this is false, then it means the character is either upside down or sitting normally, so I only have to start the Rotate() coroutine. If, however, Rotating is true, I need to stop the previously started coroutine before starting the new rotation coroutine.

CharacterTargetAngle represents the angle I am aiming at: either 0 or 180.

IsNormalPosition represents whether the character has an angle of 0 (true) or 180 (false).

RotationRate represents the speed of rotation. Currently the character can rotate at a speed of 180 * 5 degrees per second. I reached this value after trying many others.

Your code seems to be quite clear to me. The only thing I can offer as a suggestion is as follows:

if (IsNormalPosition)
{
    CharacterTargetAngle = 180;
}
else
{
    CharacterTargetAngle = 0;
}

This is a little more concise.

CharacterTargetAngle = IsNormalPosition ? 180 : 0;


Find the min and max elements of a collection, and check whether it is sorted The function I propose allows to find the minimum and maximum values of a collection and to check that it is sorted up to a certain element. Basically it is a combination of std::minmax_element and std::is_sorted_until in a single pass function, without any significant overhead compared to a call to std::minmax_element.

template<typename ForwardIterator, typename Compare = std::less<>>
auto minmax_element_and_is_sorted_until(ForwardIterator first, ForwardIterator last,
                                        Compare compare={})
    -> decltype(auto)
{
    // Function-local result type, only the names of the
    // data members matter
    struct result_type
    {
        ForwardIterator min;
        ForwardIterator max;
        ForwardIterator sorted_until;
    } result = { first, first, last };

    // 0 or 1 elements
    if (first == last) return result;
    auto next = std::next(first);
    if (next == last) return result;

    // While it is sorted, the min and max are obvious
    auto current = first;
    while (not compare(*next, *current)) {
        ++current;
        ++next;

        // The range is fully sorted
        if (next == last) {
            result.max = current;
            return result;
        }
    }

    // The range is not sorted, use a regular minmax_element algorithm
    result.min = first;
    result.max = current;
    result.sorted_until = next;

    auto tmp = std::minmax_element(next, last, compare);
    if (compare(*tmp.first, *result.min)) {
        result.min = tmp.first;
    }
    if (not compare(*tmp.second, *result.max)) {
        result.max = tmp.second;
    }
    return result;
}

The algorithm minmax_element was introduced in Boost a long time ago before making its way into C++11. Its principal advantage is that finding both the min and max element of a collection only costs at most \$max(\lfloor \frac{3}{2}(N−1) \rfloor, 0)\$ comparisons vs. approximately \$2N\$ comparisons with separate calls to std::min_element and std::max_element.

The algorithm minmax_element_and_is_sorted_until takes the optimization logic one step further and allows to also find until which element a collection is sorted with virtually no additional comparison, while a separate call to std::is_sorted_until would have added another \$O(n)\$ comparisons.

While a bit obscure, this algorithm notably helps to optimize counting sort: some flavours of this sorting algorithm first need to know the minimal and maximal values of the collection to sort. In such a case, checking for free whether the collection is sorted allows to return early when the collection is already sorted, which is always something nice to have since it's free.

Do you think anything could be improved with this algorithm, be it a matter of correctness, style or performance?

The quick exit seems a bit clunky.

// 0 or 1 elements
if (first == last) return result;
auto next = std::next(first);
if (next == last) return result;

I also don't like the return on the same line as the if (test) it makes it harder to read (subjective).

I think I would simplify like this:

auto next = first;
if ((next == last) || (++next == last)) {
    return {first, first, last};
}

This also removed the need to declare result so far before it is actually needed.

Thus this:

// The range is not sorted, use a regular minmax_element algorithm
result.min = first;
result.max = current;
result.sorted_until = next;

can now be replaced with:

result_type result = { first, current, next };

Lets also use the std library to convey meaning for the min and max. So this:

if (compare(*tmp.first, *result.min)) {
    result.min = tmp.first;
}
if (not compare(*tmp.second, *result.max)) {
    result.max = tmp.second;
}

Can be replaced by:

auto iterCompare = [&compare](ForwardIterator lhs, ForwardIterator rhs){return compare(*lhs, *rhs);};
result.min = std::min(tmp.first,  result.min, iterCompare);
result.max = std::max(tmp.second, result.max, iterCompare);


Navigation bar using PHP I would like to know what you think:

<?php
 $nav_normal = array("1. Home","2. Read Me","3. License Agreement","4. General Information","5. Database Installer","6. Create an Account","7. Create Config","8. Successfully installed"
    );

$last_normal = array_pop(array_keys($nav_normal));

foreach($nav_normal as $name){

    if($Nav_ID == $name){
            $Nav_Type = "Selected";
    }else{
            $Nav_Type = "Unselected";
    }

    ?><li class="<?php echo($Nav_Type); ?>"><?php echo($name); ?>
<?php
            //this part is only for the (google chrome) view-source:\\
            //this will not be shown into the normal layout/output\\
            if($name != $last_normal){
                    echo("\n                                        ");
            }else{
                    echo("\n");
            }

}

On each page I write at the place of the navigation bar:

<?php
 $Nav_ID = "1. Home"; //etc. etc.\\
 include_once("navigation.php");
?>

I hope you can give me a review on what you think is either good or bad.  Just give your opinion.

<?php

// first up i have removed the numbers, those numbers can be automatically added using an ordered list,
// then if you add a menu option later you don't have to renumber everything and look through every file to check the $Nav_ID matches
$nav_normal = array("Home","Read Me","License Agreement","General Information","Database Installer","Create an Account","Create Config","Successfully installed");

// removed as documented below
// $last_normal = array_pop(array_keys($nav_normal));

// we need to start the list somewhere?, using an ordered list will automatically number the menu options
echo "
";

foreach($nav_normal as $name){

    if($Nav_ID == $name){
        // $Nav_Type is not very descriptive
        // $Nav_Type = "Selected";
        $Nav_Selected = "Selected";
    } else {
        $Nav_Selected = '';
        // it is not necessary to have a state for unselected
//        $Nav_Type = "Unselected";
    }

    // the last if/else block could be replaced by this single line
    $Nav_Selected = ($Nav_ID == $name) ? "Selected" : '';

    // it is not worth escaping php for a single, line, it is easier just to embed the html and echo it
    // make sure we call htmlspecialchars or characters like >< & " etc will stuff up your html
    echo "
".htmlspecialchars($name)."
";

    // this makes no visible difference, multiple spaces are rendered as one in html
//    if($name != $last_normal){
//        echo("\n                                        ");
//    }else{
        echo "\n";
//    }

}

// if we want extra spaces after the last item in the loop, just echo them after the loop has finished
echo "                                        ";

// don't forget to close the ordered list too
echo "
";


Updating NamedTuple members based on a function and previous value I'm using a NamedTuple to represent the state of my game while it's running. The user can alter these settings using key presses, so in my PyGame key handler, I'm writing things like:

if key_code == 273:  # Up arrow
    return game_settings._replace(fps=game_settings.fps + 5)

Each key press transforms the settings state by using the old value and _replace.

I decided to try and emulate Clojure's update function as an exercise, and because it may actually make more code more readable. It takes a function and a key, and updates the value at that key using the function. Example usage:

>>> sett = GameSettings(fps=30, is_running=True)

>>> sett.update(lambda x: not x, "is_running")
GameSettings(fps=30, is_running=False)

>>> sett.update2(lambda x: not x, is_running=None)
GameSettings(fps=30, is_running=False)

I created two different versions that each behave similarly but are slightly different. Version one accepts a string key. Version two accepts kwargs with a dummy value. I'm not super happy with either though. Having to pass a String to Version one fells messy any error prone. If I typo the String, I'll get an AttributeError at runtime. Version two accepting a dummy value also feels off and is also error prone; although I do think it reads nicer without the quotes. The code for each is also quite ugly and dense.

The methods don't actually need to accept more than one key (I'll probably never pass more than one at a time), but I figured it barely changes the algorithm and it mirrors _replace, so I decided why not.

I'd appreciate any thoughts here on how to set this up better or make the code cleaner.

from __future__ import annotations
from typing import NamedTuple, Callable, TypeVar
from functools import reduce

T = TypeVar("T")

class GameSettings(NamedTuple):
    fps: int
    is_running: bool = True

    def update(self, f: Callable[[T], T], *keys) -> GameSettings:
        return reduce(lambda acc, k: acc._replace(**{k: f(getattr(acc, k))}), keys, self)

    def update2(self, f: Callable[[T], T], **kwargs) -> GameSettings:
        return self._replace(**{k: f(getattr(self, k)) for k, _ in kwargs.items()})

I decided that since I'll likely never need to associate the same function with multiple keys, I might as well just associate the keys with a function directly:

def update3(self, **kwargs: Callable[[T], T]) -> GameSettings:
    return self._replace(**{k: f(getattr(self, k)) for k, f in kwargs.items()})

>>> sett = GameSettings(fps=30, is_running=True)

>>> sett.update3(is_running=lambda x: not x)
GameSettings(fps=30, is_running=False)

The code still isn't beautiful, but it makes a lot more sense when calling now.


SortedStack implementation in Java This is a data structure that supports the push(), pop() and isEmpty() operations and returns the least element on every pop(). In a sense, this works like a PriorityQueue, only in \$O(n)\$ runtime against the \$O(log n)\$ runtime of a PriorityQueue.

My implementation:

public class SortedStack<T extends Comparable<T>> {

    private int size;
    private  Stack<T> s1;
    private Stack<T> s2;

    public SortedStack(){

        s1 = new Stack<>();
        s2 = new Stack<>();
        size = 0;
    }
    public int compareTo(T other){
        return compareTo(other);
    }
    public void push(T item){

        size++;
        if(s1.getHead() == null){
            s1.push(item);
            return;
        }

        while(!s1.isEmpty()){
            if(s1.peek().compareTo(item) < 0){
                s2.push(s1.pop());
            }else if((s1.peek().compareTo(item) > 0) || (s1.peek().compareTo(item) == 0)){
                s1.push(item);
                break;
            }
        }
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }

    }

    public T pop(){
        size--;
        return s1.pop();

    }

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

}

The Stack implementation that it uses is as follows:

public class Stack<T>{
    private Node head;

    private class Node<T>{
        private T data;
        private Node next;

        public Node(T data){
            this.data = data;
            next = null;
        }
    }
    public Node getHead(){
        return head;
    }

    public void push(T item){
        Node p = new Node((Comparable) item);
        if(head == null){
            head = p;
            return;
        }
        p.next = head;
        head = p;

    }
    public T pop(){
        if(head == null){
            System.out.println("Popping off an empty stack!!!");
            System.exit(-1);
        }
        T item = (T) head.data;
        head = head.next;
        return item;

    }

    public T peek(){
        if(head == null){
            System.out.println("Empty Stack!!");
            System.exit(-1);
        }
        return (T) head.data;
    }

    public boolean isEmpty(){
        return head == null;
    }
}

First up, let's both simplify your low level Stack class, and correct the Generics at the same time.

Stack

The issues with the generics are "obvious" by the numerous times you cast values that should be generically correct anyway.

You also have overly complicated logic in your push method:

public void push(T item){
    Node p = new Node((Comparable) item);
    if(head == null){
        head = p;
        return;
    }
    p.next = head;
    head = p;

}

That can be simply (note, this requires a change to Node that I describe in a moment):

public void push(T item){
    head = new Node(item, head);
}

Right, the change to Node is to add the next to the constructor:

private class Node{
    private final T data;
    private final Node next;

    public Node(T data, Node next){
        this.data = data;
        this.next = next;
    }
}

The System.exit(-1) error handling is also really horrible.... use exceptions!

Finally, why do you have a getHead() method on the Stack? It returns a value that is a private-context Node, so nobody can actually call that method.... right? I am half-surprised that Java lets that compile.

The "final" Stack class could look like:

public class Stack<T>{

    private class Node{
        private final T data;
        private final Node next;

        public Node(T data, Node next){
            this.data = data;
            this.next = next;
        }
    }

    private Node head;

    public void push(T item){
        head = new Node(item, head);
    }

    public T pop(){
        if(head == null){
            throw new IllegalStateException("Cannot pop an empty Stack");
        }

        T item = head.data;
        head = head.next;
        return item;

    }

    public T peek(){
        if(head == null){
            throw new IllegalStateException("Cannot peek an empty Stack");
        }
        return head.data;
    }

    public boolean isEmpty(){
        return head == null;
    }
}

SortedStack

This class has some simpler problems - naming, and style. It also has some algorithmic problems that may be improved.

s1 and s2 are horrible, horrible names. stack and temp would be better. But, really, there's no reason to have temp at all, you can create it for the duration of the push method only - it does not need to hang around when empty.

You also have the following, very baffling method. This is a "WTF" thing:

public int compareTo(T other){
    return compareTo(other);
}

Please explain that to me? ;-)

Throw it away!

While we are throwing things away, throw out the size as well, it's a distraction, and unnecessary.

Talking about throwing things out..... did you throw out the peek() method when it should actually be there?

One small comment on this code segment:

if((s1.peek().compareTo(item) > 0) || (s1.peek().compareTo(item) == 0)){

How about ( ;-) ):

if(s1.peek().compareTo(item) >= 0) {

Now, ignoring the push(T) method, the rest of the SortedStack class could simply be:

public class SortedStack<T extends Comparable<T>> {

    private final Stack<T> stack;

    public SortedStack(){
        stack = new Stack<>();
    }

    public T peek() {
        return stack.peek();
    }

    public T pop(){
        return stack.pop();
    }

    public boolean isEmpty(){
        return stack.isEmpty();
    }

    public void push(T item) {
        //TODO - fill this in ;-)
    }

}

Now, abut that push method.... how about:

public void push(T item) {
    Stack<T> temp = new Stack<>();

    // stash away all values less than the new item
    while (!stack.isEmpty() && stack.peek().compareTo(item) < 0) {
        temp.push(stack.pop());
    }

    // keep the item
    stack.push(item);

    // restore all the smaller items.
    while (!temp.isEmpty()) {
        stack.push(temp.peek());
    }
}


Garbage collection loop in Game of Life I'm working on a Game Of Life clone as my first project. I'm still relatively new to programming, so my code is probably not really optimised.

The biggest bottleneck is in my Start() method, but that contains a lot of Unity3D specific methods which most people here probably don't know about. That's why I'm leaving that out.

My second bottleneck is somewhere in my Update() method. In here, I'm looping through my array which is currently 100 by 100 large, 10.000 in total.

I've been checking with the built-in profiler of Unity3D, and this reports that the biggest bottleneck is the garbage collection.

I also tried to put half of the loop in another thread, but that didn't work out properly, because it needs to look up cells in the other half.

If you see any other ways to improve my code, and not just the performance, feel free to let me know. But please, keep it simple, as I'm still relatively new to programming.

The relevant code:

void Update()
{
    timeElapsed += Time.deltaTime;                  // this will add deltaTime to timeElapsed,
    if (timeElapsed >= timeBetween)                 // until timeElapsed exceeds timeBetween,
    {                                               // which allows a new generation to be calculated
        timeElapsed -= timeBetween;
        if (gameState == GameState.Game_Playing)
        {
            grid = CheckAdjacent(grid);             // draw new generation
            UpdateInformation();                    // update information variables
        }
    }
}

public static void DrawGeneration(bool[,] grid)
{
    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            cubeGrid[x,y].renderer.enabled = grid[x,y]; // enables the renderer for active cells.
        }
    }
}

private void UpdateInformation()
{
    generation++; //counts the generations
}

public static int GetAliveCells ()
{
    int i = 0;
    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            if (grid[x, y]) // counts the number of alive cells
                i++;
        }
    }
    return i;
}

bool IsCellAlive(int adjacentCount, bool isAlive)
{
    if (isAlive)
        return liveRule.Contains(adjacentCount);
    else
        return becomeAliveRule.Contains(adjacentCount);
}

private bool[,] CheckAdjacent(bool[,] grid)
{
    int adjacentSquares = 0;
    bool[,] newGrid = new bool[gridX, gridY];

    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            adjacentSquares = 0;

            if (grid[calcX(x - 1), calcY(y - 1)])
                adjacentSquares++;
            if (grid[calcX(x), calcY(y - 1)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y -1)])
                adjacentSquares++;

            if (grid[calcX(x - 1), calcY(y)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y)])
                adjacentSquares++;

            if (grid[calcX(x - 1), calcY(y + 1)])
                adjacentSquares++;
            if (grid[calcX(x), calcY(y + 1)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y + 1)])
                adjacentSquares++;

            newGrid[x,y] = IsCellAlive(adjacentSquares, grid[x,y]);
        }
    }
    return newGrid;
}

private int calcX(int x)
{
    x += gridX;
    return (x % gridX);
}

private int calcY(int y)
{
    y += gridY;
    return (y % gridY);
}

I would advise you to count neighbours from alive points, not for cells to be checked. Null a 100x100 int array Neighbours. For every alive cell add +1 into every neighbouring cell in Neighbours. After the pass you have number of neighbours for the every cell, but time used is about 1/4 at most, because you saved the time not counting neighbours for zero cells.
You are taking left neighbours for utmost left cells, for example. Out of boundaries! You are blocking this by taking a function and modulo and thus making the toroid out of plane, but thus you are counting much longer - division or modulo are slow, functions even more slow. Simply count neighbours normally for the field except boundaries, otherwards for the four sides and four corners. More to write, but less to count later.
If you want a shorter code, you could use a help arrays ( I have invented them for myself in 1978)

// neighbor-vectors in xy coordinates clockwise from algebraic x axis.
int [8] dx={1,1,0,-1,-1,-1,0,1};
int [8] dy={0,-1,-1,-1,0,1,1,1};

and in counting neighbours for a cell do:

if(cell[x,y]>0)
for(i=0;i<8;i++){
   x1=x+dx[i];
   y1=y+dy[i];
   if(x1>=0 & x1<100 & y1>=0 & y1<100){
       neighbours[x1,y1]++;
   }
}

Count the time spent for different activities, for not to waste time on optimizing part that takes 0.1% of time.

So you can throw off many objects, not to create them at all. Only hold 2 desk in 2x100x100 array - each time one will be active, the other will be old.  You can even count neighbours and later make living/dead cells on the same desk. No garbage collection.


Logging class in Qt library for foreign language calls I have a small C++/Qt library that interfaces with an application in another language (so interfacing must be performed using primitives, notably pointers to Handler objects). To implement debug logging, each Handler has its own debug file, managed by a Log object. These are both constructed in the initializeHandler function.

To make use of RAII, I didn't want Log objects to have a default constructor - they have a copy-constructor, and a constructor that takes a QString to open a QFile with. If the Log can't open the file, I want the initializeHandler function to fail, so I made it throw a LogExceptFailedOpen exception. To interact with the application using my library, I have to catch that exception and re-interpret it as a returned error code (I can't just let the exception propogate - the calling application can't catch it). But I want to use the Log object if construction succeeds. Which leads me to my problem.

If I declare and initialize the Log in the try block, I can't access it after the catch block. I can get around this by using a QSharedPointer<Log> with a scope larger than the try block, then using the Log copy-constructor to create another Log object afterwards (or I could just use the Log stored in logPtr, but that's not the point). However, this feels like a hack, and I feel that the code structure could instead be reworked somehow.

There's some discussion here around someone with a similar problem, which suggests that I should either

do all my work within the try block, or
abandon RAII for Log objects.

Neither option appeals to me very much. RAII is important for Log objects, as they get passed around and copied a lot and it would be a major hassle to look for all the places where they could go out of scope.

How can I improve my code to avoid this problem?

initializeHandler function:

typedef int ErrorCode;
#define ERROR_FILE_FAILED_OPEN   -12
#define ERROR_INVALID_ARGS       -1
#define ERROR_OK                 0

ErrorCode initializeHandler(Handler*& handler, const char * logFile, int x, int y)
{
    QSharedPointer<Log> logPtr;
    try {
        logPtr.reset(new Log(QString(logFile)));
    } catch (const LogExceptFailedOpen& e) {
        return ERROR_FILE_FAILED_OPEN;
    }
    Log logger(*logPtr);

    logger.log("Log started.");
    logger.log("Initializing handler...");

    Handler* temp;
    try {
        temp = new Handler(logger, x, y);
    } catch (const HandlerExceptInvalidArgs& e) {
        logger.log("Arguments invalid. x = " + QString::number(x)
                   + ", y = " + QString::number(y));
        return ERROR_INVALID_ARGS;
    }
    handler = temp;

    logger.log("Successfully initialized handler.");

    return ERROR_OK;
}

Log class:

class Log
{
private:
    QSharedPointer<QFile> file;
    QSharedPointer<QTextStream> stream;
public:
    void log(const QString& message)
    {
        (*stream) << (message + "\r\n");
    }

    // file constructor
    Log(const QString& fileName) : file(fileName)
    {
        if (!file->open(QFile::WriteOnly)) {
            throw LogExceptFailedOpen();
        }
        stream = QSharedPointer<QTextStream>(new QTextStream(file.data()));
    }

    // copy-constructor
    Log(const Log& other) : file(other.file), stream(other.stream) {}

}

It would be great to be able to discern what outside requirements and what are requirements that you are imposing because you are imagining a specific way to solve this problem. You don't post the Handler class. If you want a logger per Handler why not have the handler class create the logger ?

With regard to RAII, all objects destructors will be called at the end of the program, unless you need to open and close these files for other reasons, is there really an upside to make things more complicated than they already are ?

But yes that solution with the pointer and the copy doesn't look good, it smells like you trying to enforce a specific way of dealing with things that just doesn't fit the semantics of the code. The copy constructor in the logger is only there because of the way you want to create the logger, there doesn't seem to be any outside requirement that says that copy constructor is needed.
If you need to detect two different error conditions from exceptions you can just throw two different exception types, when you create your handler.

Unless there is a specific reason for having the initializeHandler function you could as well handle most of the logic you have in that function in the constructor and do the errorhandling in various catch blocks.
if you throw the exceptions in the constructor you don't have to check in the constructor if the preceding operations succeeded, that is one of the advantages of throwing exceptions for error handling. Also think about how often you expect the file open function to fail, if you expect this to be a regular occurrence then the handling would be different than if this is an 'exceptional' occurrence.

Here is one option how handler initialization could be handled.

QPointer<Handler> handler;
try {
    handler = new Handler(x, y, "Handler.txt");
  }
  catch (FileOpenException e) {
    // Handle file Open Exception
  }
  catch (HandlerException e) {
    // Handle Handler failure
  }
}

if (! handler.isNull())
{
  doProcessing();
}

Unless there are other requirements that force you to copy the logger, get rid of the copy constructor, then you don't have to use the QSharedPointer in your logger class. Instead you can just use plain stack members.


Restricting types not related through inheritance without using instanceOf by creating own class hierarchy Restricting types not related through inheritance without using instanceOf by creating own class hierarchy. It needs to interact with a key value data store, will convert to object before putting, but needs to convert back to fields after getting from DB with Function<Object,Field>. Something about this with regards to inheritance doesn't seem right, although it works.

import lombok.EqualsAndHashCode;
import lombok.Getter;
import lombok.NonNull;

/**
 * Field, placeholder for a type that can be stored in db
 */
@EqualsAndHashCode
public class Field<T> {
    @Getter
    private T featureValue;

    Field(@NonNull T value) {
        this.featureValue = value;
    }

    public static class Factory {
    }
}
//convert object to feature value (since ddb returns Map<String, Object> on Item.asMap)
//convert particular type of object to feature value (say Integer, String)
//abstract Field from(T value);
//convert feature value to particular type, call from drvd (from base => obj)
//enum or getEnum for some type expressed as string factory

/**
 * Field for a boolean type
 */
public class BooleanField extends Field<Boolean> {
    public BooleanField(Boolean value) {
        super(value);
    }

    public static BooleanField fromObject(Object value) {
        return new BooleanField((Boolean) value);
    }
}

import java.util.List;

/**
 * Field for a list data type, holds a list of Field
 */
public class ListField extends Field<List<Field>> {
    public ListField(List<Field> value) {
        super(value);
    }

    public static ListField fromObject(Object value) {
        return new ListField((List<Field>) value);
    }
}

import java.util.Map;

/**
 * Field for a map type, holds a map of String to Field
 */
public class MapField extends Field<Map<String, Field>> {
    public MapField(Map<String, Field> value) {
        super(value);
    }

    public static MapField fromObject(Object value) {
        return new MapField((Map<String, Field>) value);
    }
}

/**
 * Field for a Numeric type
 */
public class NumericField extends Field<Number> {
    public NumericField(Number value) {
        super(value);
    }

    public static NumericField fromObject(Object value) {
        return new NumericField((Number) value);
    }
}

import java.util.Set;

/**
 * Field for a set data type
 */
public class SetField extends Field<Set<Field>> {
    public SetField(Set<Field> value) {
        super(value);
    }

    public static SetField fromObject(Object value) {
        return new SetField((Set<Field>) value);
    }
}

/**
 * Field for a string type
 */
public class StringField extends Field<String> {
    public StringField(String value) {
        super(value);
    }

    public static StringField fromObject(Object value) {
        return new StringField((String) value);
    }
}

You can create the same thing by not creating all those subclasses. I also see that you can't use the instanceOf method. My first intention was getting this test method to work:

System.out.println(Field.fromObject(new ArrayList()).getFeatureValue().getClass());
System.out.println(Field.fromObject(new Integer(6)).getFeatureValue());
System.out.println(Field.fromObject(new Integer(6)).getFeatureValue().getClass());
System.out.println(Field.fromObject(Boolean.TRUE)); // null or error

As you can see, I call Field and not an implementation of the Field class. But I also want the correct class back as what class I put in there, so the output should be:

class java.util.ArrayList
6
class java.lang.Integer
null

In order that Boolean is a type what can't be created. After searching on this topic you come always back to instanceOf or what you did. The thing what I wanted is something I can refactor really easy, so it needed to be on 1 place to refactor.

Enum could help me with that, but still having trouble with subclasses what also need to be valid. (ArrayList if List is allowed)

I refactored your code to this. If you need to create the subclasses, you could still look at the static method.

public class Field<T> {

    private T featureValue;

    Field(T value) {
        this.featureValue = value;
    }

    public T getFeatureValue() {
        return featureValue;
    }

    public static <T> Field<T> fromObject(T value) {
        for (Allowed allow : Allowed.values()) {
            if (allow.getClazz().isAssignableFrom(value.getClass())) {
                return new Field<>(value);
            }
        }
        return null;
    }

    private enum Allowed {

        INTEGER(Integer.class),
        STRING(String.class),
        LIST(List.class);

        private final Class clazz;

        private Allowed(Class clazz) {
            this.clazz = clazz;
        }

        public Class getClazz() {
            return clazz;
        }
    }
}

As you can see, we iterate the Enum values to check the restrictions. With this solution you can add also the following test:

List<String> list  = Field.fromObject(new ArrayList<String>()).getFeatureValue();

As you can see, no casting is required.

The next is broken code:

List<String> list  = Field.fromObject(new ArrayList<Boolean>()).getFeatureValue();

which is also good because these are 2 different types.


Find a substring count in an string This code is written to find substring count in a string in Python 3. The original problem description is here. Please suggest better ways of solving this.

string =input()
substring = input()
count = 0
i=0
while(i<(len(string)-len(substring))):
    if(string.find(substring,i,len(string))>=0):
        count+=1
        i=string.find(substring,i,len(string))+1
    else:
        break;
print(count)

KISS (Keep it simple, stupid)
You could've done this way simpler than that by just writing:
string.count(substring)

Wrapping this into a function for later use would look like:
def count_substrings(my_string, my_substring):
    return my_string.count(my_substring)

if __name__ == '__main__':
    print(count_substrings('dexter is dexter lala dext dexter', 'dexter'))

Which will print the desired result:

3

About your code:

You should always have a space around operators (i=0 should be i = 0).
Python is not C. You have way too many parentheses and you shouldn't use ;.

There's something called PEP8 which is the recommended style-guide for Python. I'd strongly recommend you read it.
Your code would look like this if we'd respect the above:
string = input()
substring = input()

count, i = 0, 0
while i < len(string) - len(substring):
    if string.find(substring, i, len(string)) >= 0:
        count += 1
        i = string.find(substring, i, len(string)) + 1
    else:
        break
print(count)

More, I'd let the user know what's about to be entered so I'd write:
my_string = input('Please enter the string: ')
my_substring = input('What substring are you looking for? ')

You should also wrap your code within a function for later use, and add the if __name__ == '__main__' construction, which will allow you you to have that code execute only when you want to run the module as a program, and not have it execute when someone just wants to import your module and call your functions themselves

Anyway, the first solution does not work for overlapping matches (which I saw it was a requirement after reading the challenge), so you might consider doing it like you did, but a bit different / simpler:
def count_substrings(my_string, my_substring):
    count = start = 0
    while True:
        start = my_string.find(my_substring, start) + 1
        if start > 0:
            count += 1
        else:
            return count

The above might be even faster since it does the comparing in C.

Bear with the fact that I've only commented on your actual code, and not the entire challenge. You might wanna add some constraints which are clearly specified there (e.g: 1 <= len(my_string) <= 200)


Count duplicate List Count duplicate List<int> in List<List<int>>.
A duplicate is not order-dependent. { 1, 2, 3 } is a duplicate of { 2, 1, 3 }

Looking for speed without getting silly.

public static void CountListTest()
{
    List<List<int>> testData = new List<List<int>>
    {
            new List<int> { 7, 3, 4 },
            new List<int> { 1, 2, 3 },
            new List<int> { 2, 1, 3 },
            new List<int> { 6, 8, 3 },
            new List<int> { 9, 2, 4 },
            new List<int> { 6, 3, 8 },
            new List<int> { 7, 3, 4 },
    };
    List<List<int>> countList = CountList(testData);
    Debug.WriteLine("");
    testData = new List<List<int>>
    {
            new List<int> { 1, 2, 3 },
            new List<int> { 2, 1, 3 },
            new List<int> { 6, 8, 3 },
            new List<int> { 2, 1, 3, 9 },
            new List<int> { 6, 8, 3, 9 },
            new List<int> { 2, 1, 3, 9 },
            new List<int> { 9, 2, 4 },
            new List<int> { 6, 3, 8 },
            new List<int> { 7, 3, 4 },
    };
    countList = CountList(testData);
}
public static List<List<int>> CountList(List<List<int>> input)
{
    List<List<int>> returnListList = new List<List<int>>();
    foreach (List<int> list in input)
        list.Sort();
    HashSet<int> alreadyMatched = new HashSet<int>();
    int count = 0;
    bool match = true;
    int lastEval = 0;
    for (int i = 0; i < input.Count - 1; i++)
    {
        if (alreadyMatched.Contains(i))
            continue;
        returnListList.Add(input[i]);
        count = 1;
        lastEval = 0;
        for (int j = i+1; j < input.Count; j++)
        {
            if (alreadyMatched.Contains(j))
                continue;
            lastEval = j;
            if (input[i].Count() != input[j].Count())
                continue;
            match = true;
            for (int k = 0; k < input[i].Count(); k++)
            {
                if(input[i][k] != input[j][k])
                {
                    match = false;
                    break;
                }
            }
            if(match)
            {
                count++;
                alreadyMatched.Add(j);
            }
        }
        Debug.WriteLine("Count = {0}  List {1}", count, string.Join(", ", input[i]));
    }
    if (count == 1 && lastEval > 0)
    {
        Debug.WriteLine("Count = {0}  List {1}", 1, string.Join(", ", input[lastEval]));
        returnListList.Add(input[lastEval]);
    }
    return returnListList;
}

The code itself is not so bad although it could use more {} and maybe more precise names then lastEval or match. Of course it shouldn't print to the console but return a usable result.

I can't tell how fast/slow it would be if it returned a result that can be printed outside the method. I compared it with another search algorithm and for 1.000.000 iterations mine is ~20ms faster.

I think the method could do better by returning a dictionary with the results.

Currently the original method runs twice over the item list. First by sorting them and then by searching for duplicates.

This could be improved by using a helper array to mark which item is already sorted and skip subsequent sortings thus run over the items only once.

The last optimization is to skip items that already have been checked. I think you are doing this with the alreadyMatched helper but I'm not sure about it.

Making the method generic and require T to be IComparable makes it possbile to reuse it for other collections with comparable items.

The value comparison takes place in a local function sequenceEqualFast.

Similarly it sorts the lists and keeps track of the sorting in the local sortList function.

public static Dictionary<List<T>, int> FindDuplicatesFast<T>(
    List<List<T>> values
) where T : IComparable
{
    var isDuplicate = new bool[values.Count];
    var isSorted = new bool[values.Count];

    // Key: first of duplicates
    // Value: count of duplicates
    var results = new Dictionary<List<T>, int>();

    var sequenceEqualFast = new Func<List<T>, List<T>, bool>((l1, l2) =>
    {
        if (l1.Count != l2.Count) { return false; }
        for (int k = 0; k < l1.Count(); k++)
        {
            if (l1[k].CompareTo(l2[k]) != 0)
            {
                return false;
            }
        }
        return true;
    });

    var sortList = new Action<int>(i =>
    {
        if (!isSorted[i])
        {
            values[i].Sort();
            isSorted[i] = true;
        }
    });

    for (int i = 0; i < values.Count - 1; i++)
    {
        if (isDuplicate[i]) { continue; }
        sortList(i);

        results[values[i]] = 1;
        isDuplicate[i] = true;

        for (int j = i + 1; j < values.Count; j++)
        {
            if (isDuplicate[j]) { continue; }
            sortList(j);

            if (sequenceEqualFast(values[i], values[j]))
            {
                isDuplicate[j] = true;
                results[values[i]] += 1;
            }
        }
    }
    return results;
}

I have run some more tests and these are the results.

Test collection

var rnd = new Random();

var itemCount = 100;
var testData = Enumerable.Range(0, itemCount).Select(e =>
{
    var count = rnd.Next(3, 5);
    return Enumerable.Range(0, count).Select(en => rnd.Next(0, 10)).ToList();
}).ToList();

var testCount = 10000;

Results

@Paparazzi
00:00:03.2791287

@t3chb0t
00:00:01.6763969


Retrieving data from SQL DB based on user input I wrote this to connect to a local DB using my local login credentials. It pulls back card information based on the user's input.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Data.SqlClient;

namespace SQL_Console{
public class Info
{

//SQL Sever connection

    public static string connstring = @"Data Source=localhost\MAYDAY;Initial Catalog=NV; Integrated Security=SSPI; Connection Timeout=5";

    public static string ConnectionString
    {
        get
        {
            return ConnectionString;
        }
        set
        {
            connstring = value;
        }
    }
}

public class Lookup
{

//SQL Query

        public static string squery = "Select Cardnumber, CardHolder, ExpireDate from CreditCardTransactionHistory where clientnumber = (select clientnumber from foliolink where folionumber = @fnumber)";

}

//Execution

    class Program
{
    static void Main(string[] args)
    {
        string sqlconn = Info.connstring;

        Console.WriteLine("Enter Folio Number:");
        int fnum = Convert.ToInt32(Console.ReadLine());

        Console.Clear();

        SqlConnection sqlcon1 = new SqlConnection(sqlconn);
        sqlcon1.Open();

        SqlCommand sql1 = new SqlCommand(Lookup.squery, (sqlcon1));

        sql1.Parameters.AddWithValue("@fnumber", fnum);
        SqlDataReader reader = sql1.ExecuteReader();

        while (reader.Read())
        {
            Console.Write("Card Number: {0}\nCard Holder: {1}\nExpiration: {2}\n\n", reader[0], reader[1], reader[2]);

        }
        Console.ReadLine();
        sqlcon1.Close();
    }

}
}

I don't get the point of the ConnectionString class. Just about any example WRT writing db access code will use a connection string taken from a .config class; why aren't you following that recommendation?

Items like SqlConnection, SqlCommand, SqlDataReader should always be used in a using block in order to properly dispose of their resources. Look at examples like this one, or check this question on SO.

If you're going to place your SQL code in a separate class, I'd prefer it to be an embedded .sql file which you can then retrieve via code like this:

public static string GetQuery(string scriptName, string namespacePrefix)
{
    var resourceName = namespacePrefix + scriptName;
    var assembly = Assembly.GetExecutingAssembly();

    using (var stream = assembly.GetManifestResourceStream(resourceName))
    {
        if (stream == null)
        {
            throw new Exception($"Missing template: {resourceName}");
        }

        using (var streamReader = new StreamReader(stream))
        {
            return streamReader.ReadToEnd();
        }
    }
}

That way you'd at least get some IntelliSense for the SQL code.

Don't use AddWithValue().

On a more general note: avoid writing ADO.NET code by hand. Avoid using SqlDataReader etc. that require you to translate its results into your own custom classes and instead use one of the many tools that handles that for you. These days the vast majority of professional code is written using an ORM like Entity Framework. Even using a Micro ORM like Dapper would be much preferred.


Modern, C++ compliant, quick sort This is a kind of follow up to my previous sort implementation review with specific questions to quick sort, and Modern C++ idioms.

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void partition(BidirIt first,
               BidirIt last,
               BidirIt & pivot,
               Comparator cmp = Comparator())
{
    // Last usually points to end, rather than the last element.
    last--;
    // Until both first and last point to the same element (always going to be the pivot).
    while (first != last)
    {
        auto pivot_val = *pivot;
        while (cmp(*first, pivot_val)) ++first;
        while (cmp(pivot_val, *last)) --last;
        if (first == pivot)
        {
            std::iter_swap(first, last);
            pivot = last;
        }
        else
        {
            if (last == pivot)
            {
                std::iter_swap(first, last);
                pivot = first;
            }
        }
    }
}

std::vector<int> vec{ 1, 4, 5, 3, 2 };

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_quick(BidirIt first,
                BidirIt last,
                Comparator cmp = Comparator())
{
    typedef std::iterator_traits<BidirIt>::difference_type dt;
    dt size = std::distance(first, last);

    // Arrays of 0 or 1 elements are considered sorted.
    if (size > dt(1))
    {
        auto pivot = first + size / dt(2);
        ::partition(first, last, pivot);
        // Recursive call on each partititon.
        sort_quick(first, pivot);
        sort_quick(std::next(pivot), last);
    }
}

I am looking for any performance optimizations I may have missed in the algorithm itself, as well as Modern C++ constructs I may not be abiding by for this example.

In particular having to pass pivot by reference to partition and having to update the pivot reference if it gets swapped is pretty ugly, If anyone can think of a way around this I would love to know.

Also just realized this doesn't work with duplicates :|

Correctness

Fix build errors

My compiler indicates that your typedef statement is missing typename before std::iterator_traits<BidirIt>::difference_type dt; Additionally, you can replace the typedef with a using statement, which is more modern:

using dt = typename std::iterator_traits<BidirIt>::difference_type;

Adhere to iterator operations

The line:

auto pivot = first + size / dt(2);

Uses the + operator, which bidirectional iterators do not support. Calling your sort on a std::list will fail to compile. You can make your code compliant with bidirectional iterators by changing the above line to:

const auto offset = size / dt(2);
auto pivot = std::next(first, offset);

Squash the bug!

I don't know the cause, but your program appears to loop forever when I give your algorithm the sequence: 1,8,4,6,5,2,0,3. This is almost certainly not desired behavior.

Code Simplicity

Return the new pivot

You can avoid taking the pivot by reference by changing partition() to return the pivot value. The new function signature would be:

template<typename BidirIt,
typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
BidirIt partition(BidirIt first,
                  BidirIt last,
                  BidirIt pivot,
                  Comparator cmp = Comparator())

And then simply return pivot; at the end of the function. But then this function signature looks familiar:

Use the standard library, Luke!

There already exists a partition() function in the standard library. You can replace your entire partition function with it, and simplify sort_quick():

    pivot = std::partition(first, last, [&] (auto value)
                           {
                               return cmp(value, *pivot);
                           });

The use of auto in the lambda is a C++14 feature, you will have to write out the correct type if you can only use C++11. Also, using std::partition fixes the loop-forever bug on my "bad" input, but still doesn't quite give correct results.

Minor Issues

Unused comparator

sort_quick() accepts a comparator function argument, but the comparator is never used inside the body of the function.

Restrict Iterator types

Currently you rely on convention that your iterator types are bidirectional. You could produce nicer error messages by using static_assert, possibly like this:

using category = typename std::iterator_traits<BidirIt>::iterator_category;
static_assert(std::is_base_of<std::bidirectional_iterator_tag, category>::value, "This algorithm requires bidirectional iterators.");


Different types of model validation So we have a RESTful webservice that implements CRUD operations for a model, like this one:

class MyModel {
    private long id;
    private String name;
    // other fields
    private boolean completed;
    private boolean active;
    // getter and setters
}

In this webservice there is also a path like /service/{id}/complete that updates just the field completed to true. This indicates a final step for the creation.

The save and the complete operation are pretty simple and similar (they both end up calling a saveOrUpdate ). Where they differ is the validation. The complete validation is stricter.

The one before me declared an interface:

interface Validator<T> {
    void validate(T t);
}

And then to check that all mandatory fields where there before setting the complete attribute to true we have something like (writing in pseudocode):

MandatoryFieldsValidator implements Validator<MyModel> {

    list = {'id', 'active'}

    public void validate(MyModel model) {
        foreach(element in list) {
            if(myModel.get(element) is null) throw ValidationException(element + " is mandatory");
        }
    }
}

So then I needed another type of validator and started doing something like this because I needed specific controls over the name field:

NameValidator implements Validator<MyModel> {
    public void validate(MyModel model) {
        if(model.name is null or empty)
        throw ValidationException(element + " is mandatory");
        if(model.name.startswith("something"))
            throw ValidationException("something not valid prefix");
        if(model.name.length > 10)
        throw ValidationException("too long");
    }
}

The controller had an attribute of type Validator that instantiated a MandatoryFieldsValidator so I added another attribute of the same type instantiating a NameValidator.

Now what I don't like about this:

The fact that I need to add a new attribute to the class as soon as I have a new validator to use;
The fact that I'm repeating checks in different validators because even if name is not included in the MandatoryFieldValidator I'm applying the same logic inside NameValidator (is null or empty);
I will also add a new type of model and a MandatoryFieldValidator<NewModel> with the same type of control logic is a non-sense.

Can you give me some advice? I'm looking into a general pattern to organize this kind of validation but I'm using Java so if you have some Java specific solution is ok.

You could use the composite pattern to create a tree of Validator instances. Each node would validate its with its own Validator before delegating to children (if any). This way children don't need to check again what was already validated in parent nodes

public class ValidatorTree<T> implements Validator<T> {

    private Validator<? super T> node;
    private List<Validator<? super T>> children;

    // constructor etc. snipped for brevity

    @Override
    public void validate(T t) {
        node.validate(t);
        for (Validator<? super T> child : children) {
            child.validate(t);
        }
    }
}

This way you can bundle several validators into one (so only one root validator needs to be referenced). And validation order is guaranteed, so no need to perform duplicate checks.

Edit (in response to comment)

A Validator for Model1 may very well be different from a Validator for Model2. If Validators are to be reused for different models you can define interfaces that define the common parts to be validated.

e.g.

public interface Named {

    String getName();
}

and a matching NameNotNullValidator :

public class NameNotNullValidator implements Validator<Named> {
    @Override
    public void validate(Named named) {
        if (named.getName() == null) {
            throw new ValidationException(/* appropriate message here */);
        }
    }
}

And this Validator can be reused in validator trees for all models that implement Named. Note that I adapted the generics in ValidatorTree for this.


Getting the top 10 stores within a category I have the following query. I know there's an easier way to do this without the sub queries, or at least optimizing how they're used. I've read about cross joins and using HAVING but cannot figure out how to make this better as I know it's pretty bad.

Basically what I'm trying to do is get the top 10 stores within a category. For this category it is category with an id of 9 as you can see in the where clause. I am categorizing each individual user based on the most occurring category of the products they have. And then reordering the results by most orders and getting the first 10 results.

EDIT:

c.id = 9, which should be c.id = '$categoryId' (edited) is representative of where a numeric value would be passed into the query to get the top stores specific to a category id.

SELECT u.id,
       u.avatar,
       u.storeName,
       (SELECT COUNT(o.id) FROM orders o WHERE o.storeId = u.id) AS orders
FROM users u
WHERE (SELECT c.id
       FROM categories c, products p
       WHERE c.id = p.categoryId
       AND p.userId = u.id
       GROUP BY p.categoryId
       ORDER BY COUNT(p.id) DESC
       LIMIT 1) = '$categoryId'
ORDER BY orders DESC
LIMIT 10

There are some things that you don't need here

SELECT u.id,
       u.avatar,
       u.storeName,
       (SELECT COUNT(o.id) FROM orders o WHERE o.storeId = u.id) AS orders
FROM users u
WHERE (SELECT c.id
       FROM categories c, products p
       WHERE c.id = p.categoryId
       AND p.userId = u.id
       GROUP BY p.categoryId
       ORDER BY COUNT(p.id) DESC
       LIMIT 1) = 9
ORDER BY orders DESC
LIMIT 10

like the ORDER BY and the LIMIT 1 and the GROUP BY in the Select statement that is nested in your where clause.

SELECT u.id,
       u.avatar,
       u.storeName,
       (SELECT COUNT(o.id) FROM orders o WHERE o.storeId = u.id) AS orders
FROM users u
WHERE (SELECT c.id
       FROM categories c, products p
       WHERE c.id = p.categoryId
       AND p.userId = u.id
       ) = 9
ORDER BY orders DESC
LIMIT 10

You should also rename your column orders to orderCount

one more thing that I would suggest is to take it all out of the WHERE clause, this is slow

do it like this

SELECT u.id,
       u.avatar,
       u.storeName,
       (SELECT COUNT(o.id) FROM orders o WHERE o.storeId = u.id) AS orderCount
FROM users u INNER JOIN products p ON u.id = p.userId
WHERE p.categoryID = 9
ORDER BY orderCount DESC
LIMIT 10


Speed up sorting algorithm in R: make one column "smaller" than the other Consider the following sorting algorithm:

df <- data.frame(food_1 = c("APPLE 1534", "PEAR 2525", "BANANA 3045", "WATERMELON 5000"),
                 food_2 = c("ORANGE 2035", "BROCCOLI 5000", "BLUEBERRY 2000", "TOMATO 3000"),
                 stringsAsFactors = FALSE)

# Sorting
for (i in 1:nrow(df)){
  foods <- sort(c(df$food_1[i], df$food_2[i]))
  df$food_1[i] <- foods[1]
  df$food_2[i] <- foods[2]
}

I have data frames which are of size 250,000+ rows that I've used the code above for, and I'm not sure how to make this more efficient.

You solution does the job, but it is often better to vectorise your code. See the following example. First get the ordering of all elements in column a and b and then use this to rearrange the elements in the data.frame.

library(tictoc) #to get the run time

df <- data.frame(a = runif(10000),
                 b = runif(10000))

# your solution
tic()
df.loop <- df
for (i in 1:nrow(df.loop)){
df.loop[i, ] <- sort(df.loop[i, ])
}
toc()

#sort (order) only once
tic()
index.a <- 1:nrow(df)
index.b <- (nrow(df) + 1) : (2*nrow(df))
a.b.ordered <- order(c(df[, 1], df[, 2]))
b.greater.a <- match(index.b, a.b.ordered) < match(index.a, a.b.ordered)
df.index <- df
df.index[b.greater.a, 1] <- df[b.greater.a, 2]
df.index[b.greater.a, 2] <- df[b.greater.a, 1]
toc()

identical(df.loop, df.index)


BFS' shortest path unweighted directed graph The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too see if anything could be changed or improved:

public int bfsshortestpath (V source, V target) {
    Map<V, Integer> dist = new TreeMap<V, Integer>();
    Map<V, V> prev = new TreeMap<V, V>();

    for(V v: adjlist.keySet()){
        dist.put(v, null);
        prev.put(v, null);
    }
    dist.put(source, 0);

    Queue<V> q = new LinkedList<V>();
    q.offer(source);
    while(!q.isEmpty()){
        V u = q.poll();
        if(u == target)
            break;
        q.remove(u);
        for(V neighbor: adjlist.get(u)){
            int a = dist.get(u);
            if(dist.get(neighbor) != null)
                continue;
            //BFS distance
            dist.put(neighbor, a + 1);
            prev.put(neighbor, u);
            q.offer(neighbor);
        }
    }

    List<V> s = new LinkedList<V>();
    V u = target;
    while(prev.get(u) != null){
        s.add(u);
        u = prev.get(u);
    }
    return s.size();
}

Advice 1

for(V v: adjlist.keySet()){
    dist.put(v, null);
    prev.put(v, null);
}

This is \$\Theta(N)\$ and you don't really need it (see below). Also, TreeMap orders the keys (nodes) in a balanced binary search tree, which runs insertion/search/removal in worst case \$\Theta(\log n)\$ time, and you don't need it either: just use a HashMap with \$\Theta(1)\$ access, reading and writing.

Advice 2

In order to get rid of the initialization for in the above advice, you can do:

public int shortestPathLength(V source, V target) {
    Map<V, Integer> dist = new HashMap<V, Integer>();
    Map<V, V> prev = new HashMap<V, V>();
    Queue<V> q = new LinkedList<>();

    dist.put(source, 0);
    prev.put(source, null);
    q.offer(source);

    while(!q.isEmpty()){
        V u = q.poll();
        if(u == target)
            return tracebackPath(u, prev);
        q.remove(u);
        for(V neighbor: adjlist.get(u)){
            if (!dist.containsKey(neighbor)) {
                dist.put(neighbor, dist.get(u) + 1);
                prev.put(neighbor, u);
                q.offer(neighbor);
            }
        }
    }

    return 0; // Target not reachable from source.
}

List<V> tracebackPath(V target, Map<V, V> prev) {
    List<V> s = new LinkedList<V>();
    V u = target;
    while(prev.get(u) != null){
        s.add(u);
        u = prev.get(u);
    }
    return s.size();
}

Advice 3

if(u == target)

Beware. I suggest you implement equals for whatever node type you use and change the above to

if (u.equals(target))

Advice 4

Since you need to map nodes to values in the HashMap s, you need to override a hashCode() as well in the graph node class.

Concluding

Suppose both target and source nodes are very close to each other. My implementation will return very fast because it does not have to run that nasty for loop.

Hope that helps.


Remove last word from string Any suggestions on better way to remove the last word from a string?

$words = str_word_count($text, 1);
$lastWord = array_pop($words);
$textWithoutLastWord = implode(" ", $words);

or

$lastSpacePosition = strrpos($text," ");
$textWithoutLastWord =substr($text,0,$lastSpacePosition);

My personal preference would be the second option:

$lastSpacePosition = strrpos($text, ' ');
$textWithoutLastWord = substr($text, 0, $lastSpacePosition);

It's more obvious what's happening. The fact that str_word_count returns an array because you feed it a 1, is not obvious.
The code is shorter, in this case I feel that makes it easier to read, rather than obfuscated.
It is by far the fastest. In my text of 110 words copied from a wikipedia article, with 1e6 iterations

str_word_count version took 17.952 milliseconds.
strrpos took 0.597 milliseconds.
preg_replace (By Oscar M) took 71.189 milliseconds.

In my test text the are letters outside of a-z. The str_word_count solution breaks these letters as if spaces. Whether this is, or is not, the intended behaviour of the function, I would stay away from such behaviour.


Reimplementing numpy.genfromtxt in Fortran for Python I've found that the function genfromtxt from numpy in Python is very slow.

Therefore I decided to wrap a subroutine with f2py to read my data. The data is a matrix.

subroutine genfromtxt(filename, nx, ny, a)
implicit none
    character(100):: filename
    real, dimension(ny,nx) :: a
    integer :: row, col, ny, nx
    !f2py character(100), intent(in) ::filename
    !f2py integer, intent(in) :: nx
    !f2py integer, intent(in) :: ny
    !f2py real, intent(out), dimension(nx,ny) :: a

    !Opening file
    open(5, file=filename)

    !read data again
    do row = 1, ny
        read(5,*) (a(row,col), col =1,nx) !reading line by line
    end do
    close (5)
end subroutine genfromtxt

The length of the filename is fixed to 100 because f2py can't deal with dynamic arrays. The code works for filenames shorter than 100, otherwise the code in Python crashes.

This is how I call the function in Python

import Fmodules as modules
w_map=modules.genfromtxt(filename,100, 50)

Any idea on how to do this dynamically without sending nx and ny as parameters?

Numpy's genfromtxt is indeed slow which is due to it's flexibility. It tries very hard to figure out what the layout of your data file is. So you will not get this flexibility by implementing it yourself in fortran.

Have you tried using loadtxt instead?

Depending on the conditions, for the same matrix genfromtxt may be more than 20 times slower than loadtxt.

BTW a simple implementation in python which is in my case faster than both loadtxt and genfromtxt:

with open("matrix.txt",'r') as f:
    a=array([fromstring(s,dtype=float,sep=' ') for line in f])

I guess the speed comes from the fact that I do not have to read in the whole file to check how many lines it has.

EDIT: I realise this does not really answer your question, but I believe that the speed-up that you may get from using fortran does not really warrant the loss of flexibility.


The rusty Sieve of Eratosthenes To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N.

I have created the following code that both prints the prime number and whether it is prime in tabular format and prints a vector consisting of the prime numbers.

As additional library I'm using the external library bit-vec.

extern crate bit_vec;

const MAXIMUM_PRIME: u32 = 1000;

use bit_vec::BitVec;

fn main() {
    let mut prime_bit_vector = BitVec::from_elem((MAXIMUM_PRIME + 1) as usize, true);
    let sqrt_prime = ((MAXIMUM_PRIME as f64).sqrt() as u32) + 1;

    for i in 2..(sqrt_prime+1) {
        if prime_bit_vector[i as usize] {
            let mut j = i * i;
            while j <= MAXIMUM_PRIME {
                prime_bit_vector.set(j as usize, false);
                j += i;
            }
        }
    }

    let maximum_prime_length = MAXIMUM_PRIME.to_string().len();
    for i in 0..(MAXIMUM_PRIME+1) {
        println!("{index:<width$} {is_prime}", index = i, is_prime = prime_bit_vector[i as usize], width = maximum_prime_length as usize);
    }

    let primes: Vec<_> = prime_bit_vector.iter().enumerate().filter(|t| t.1).map(|t| t.0).collect();
    println!("Primes: {:?}", primes);
}

To start, let me heartily compliment you on your code! You have clearly put effort into learning what idiomatic Rust code looks like. Spacing of operators seems to be accurate, and using code like Vec<_> is top-notch.

I actually took a long time to write a review because there didn't seem to be much to say! After a bit, there were some small things:

I agree that your code could be improved by splitting out some functions:

Separates the concerns of building the primes and printing them.
Allows parameterizing the maximum easier.
Cordons off the mutability of the BitVec to a smaller scope.
Gives names to what is being printed.

Instead of passing the maximum prime when printing, it can be based on the size of the BitVec. It's a little odd as you have to subtract one, so maybe you might want to create a type for the primes that abstracts that away...
Generally, I'd recommend avoiding array indexing due to performance concerns — indexing has slight overhead due to bounds checking. I'm not sure if that applies for a BitVec though. I still like the enumerate solution better.
From previous Sieves, I think that you may want to write ((MAXIMUM_PRIME as f64).sqrt() as u32) + 1 as (MAXIMUM_PRIME as f64).sqrt().ceil() as u32. I think that's more correct in more cases, and probably communicates intent better.

extern crate bit_vec;

const MAXIMUM_PRIME: u32 = 1000;

use bit_vec::BitVec;

fn primes_up_to(max: u32) -> BitVec {
    let mut prime_bit_vector = BitVec::from_elem((max + 1) as usize, true);
    let sqrt_prime = ((max as f64).sqrt() as u32) + 1;

    for i in 2..(sqrt_prime+1) {
        if prime_bit_vector[i as usize] {
            let mut j = i * i;
            while j <= max {
                prime_bit_vector.set(j as usize, false);
                j += i;
            }
        }
    }

    prime_bit_vector
}

fn print_table(prime_bit_vector: &BitVec) {
    let max = prime_bit_vector.len() - 1;
    let maximum_prime_length = max.to_string().len();

    for (i, is_prime) in prime_bit_vector.iter().enumerate() {
        println!("{index:<width$} {is_prime}", index = i, is_prime = is_prime, width = maximum_prime_length);
    }
}

fn print_primes(prime_bit_vector: &BitVec) {
    let primes: Vec<_> = prime_bit_vector.iter().enumerate().filter(|t| t.1).map(|t| t.0).collect();
    println!("Primes: {:?}", primes);
}

fn main() {
    let prime_bit_vector = primes_up_to(MAXIMUM_PRIME);
    print_table(&prime_bit_vector);
    print_primes(&prime_bit_vector);
}

In the future, two Rust enhancements will help the code look even better:

Someday we will have inclusive ranges, which would transform x..(y+1) into some nicer syntax (perhaps x...y?).
Someday the step_by range iterator adapter will exist, which would transform the j += i to something like ((i*i)...MAXIMUM).step_by(i)


Reinventing std::optional I decided to make my own version of C++17's std::optional

It's basically a class that can optionally hold a variable (as the name suggests), it avoids having to resort to std::pair<bool, T> to check whether a variable is set.

I'd like some feedback regarding the overall implementation

template<typename T>
class Optional {
 public:
  /**
   * The constructor
   */
  Optional() :
    is_set_(false) {}
  /**
   * The constructor
   * @param val The value to set it to
   */
  Optional(const T& val) :
    val_(val), is_set_(true) {}

  /**
   * Sets the value
   * @param val The value to set it to
   */
  void set(const T& val) { val_ = val; is_set_ = true; }

  /**
   * @return The value
   */
  T get() const { return val_; }

  /**
   * Clears the value
   */
  void clear() { val_ = T{}; is_set_ = false; }

  /**
   * @return Whether the value is set
   */
  bool empty() { return !is_set_; }

  /* Operators */

  Optional operator=(const T& val) {
    val_ = val;
    is_set_ = true;
    return *this;
  }

  operator T() const {
    return val_;
  }

  bool operator==(const bool& val) const {
    return (is_set_ == val);
  }

  explicit operator bool() const { return is_set_; }

 private:
  T val_{};
  bool is_set_ = false;
};

Prefer value type semantic

Try to make classes default constructible and equality comparable whenever this makes sense. Currently your Optional class doesn't fulfil neither. The following code will not compile

class A { int a; A() = delete; };

int main()
{
  Optional<A> i;
}

Even though it might make sense to have an optional. Also consider this example

struct B { B() { /* insert something super long */ } }:

int main()
{
  Optional<B> opt_b; // this line takes really long!
}

Here is an example of how to use std::aligned_storage to use uninitialised memory. I think this could help you as well.

Do not return by value if you can

The line

T get() const { return val_; }

Makes a copy of T while returning val_. Imagine val_ is a very big std::string. This could be very expensive in code which calls get() multiple times. If you want read-only access, prefer to use

const T& get() const& noexcept { return val_; }

instead.

Make use of move assignments

Currently you have to copy values into your optional. But what, if you just want to move something big that you want to return from a function? You
need to add constructors for rvalue-Ts.

Optional(T&& value)
 : val_{std::move(value)}
 , is_set_{true} {}


WinForm Logon Best Practices I have a working logon for a WinForms Project. I use the program.cs file to launch the login form. I am not so sure there isn't a better way of implementing this.
Here is my program.cs file:
    using System;
    using System.Windows.Forms;
    using WindowsFormsApp.Presenters;
    using WindowsFormsApp.Views;
    using Autofac;
    using DbContexts;
    using Serilog;

    namespace WindowsFormsApp
    {
        internal static class Program
        {
            public static IContainer Container { get; private set; }
            public static string UserName { get; set; }

            /// <summary>
            /// The main entry point for the application.
            /// </summary>
            [STAThread]
            private static void Main()
            {
                var builder = new ContainerBuilder();

                builder.Register(c => new MyContext());

                Container = builder.Build();

                Log.Logger = new LoggerConfiguration()
                    .MinimumLevel.Debug()
                    .WriteTo.Console()
                    .WriteTo.RollingFile("log-{Date}.txt")
                    .CreateLogger();
                Log.Information("Application Started");

                Application.EnableVisualStyles();
                Application.SetCompatibleTextRenderingDefault(false);

                var loginForm = new LoginForm();
                var results = loginForm.ShowDialog();

                if (results == DialogResult.Cancel)
                    System.Environment.Exit(1);

                while (results != DialogResult.OK)
                {
                    results = loginForm.ShowDialog();
                    if (results == DialogResult.Cancel)
                        System.Environment.Exit(1);
                }

                var mainFormView = new MainFormView();

                mainFormView.Tag = new MainFormPresenter(mainFormView);

                Application.Run(mainFormView);
            }
        }
    }

Any suggestions or comments are welcome.

You have a public static property UserName that can be set by anyone, anywhere in your code. You didn't detail the usage of this property.

If it's the logon form that should update it and it will never update again, have your Program class set this field.

If it's another class that updates this field, maybe this property doesn't belong here.

You have some code that is duplicated, so there must be a way to do better.

From my point view, you are doing many different things in your Main method, maybe you could put these operations in separate methods : Init, Login, Start.

Use using

You put the Presenter for MainForm in the Tag Property, which I think belongs to a specific property. That way the MainForm can control who has access to it, otherwise any object that has an access to the MainForm can recover the Tag and therefore the Presenter. Another problem is that the Tag property is an object, so you will have to convert it every time you want to use it.

So, all together that would become :
using System;
using System.Windows.Forms;
using WindowsFormsApp.Presenters;
using WindowsFormsApp.Views;
using Autofac;
using DbContexts;
using Serilog;

namespace WindowsFormsApp
{
    internal static class Program
    {
        public static IContainer Container { get; private set; }
        public static string UserName { get; private set; }

        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        private static void Main()
        {
            Init();
            Login();
            Start();
        }

        private void Init()
        {
            var builder = new ContainerBuilder();
            builder.Register(c => new MyContext());
            Container = builder.Build();

            Log.Logger = new LoggerConfiguration()
                .MinimumLevel.Debug()
                .WriteTo.Console()
                .WriteTo.RollingFile("log-{Date}.txt")
                .CreateLogger();
            Log.Information("Application Started");

            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
        }

        private void Login()
        {
            using (loginForm = new LoginForm())
            {
                var results DialogResult.None;
                do
                {
                    results = loginForm.ShowDialog();
                    if (results == DialogResult.Cancel)
                        System.Environment.Exit(1);
                } while (results != DialogResult.OK);
                //Since we logged on correctly, we can update UserName (I guess)
                UserName = loginForm.ValidatedUserName;
            }
        }

        private void Start()
        {
            using (var mainFormView = new MainFormView())
            {
                mainFormView.Presenter = new MainFormPresenter(mainFormView);
                Application.Run(mainFormView);
            }
        }
    }
}