Primality test program I am fairly new to programming and even newer to C++ but I am currently in a class for scientific computing, and our task from two weeks ago was to improve the speed of a primality test program. I regrettably do not have the original code because I wrote over it, but the long and short was that program selects 100,000 integers from 100,000 to 999,999 and checks all numbers from 2 to less than the number.

Needless to say, it took over 17 seconds to run. My code was able to get it down to ~74 milliseconds. I handed in my code last week but it's been bugging me that I don't know if I got it as fast as it could go.

(The area I made is at the bottom, at int CountPrimes)

#include "stdafx.h"

using namespace std;
using namespace chrono;

int CountPrimes(unique_ptr<vector<int>> const &samples);

seed_seq seed{ 2016 };
default_random_engine generator{ seed };
uniform_int_distribution<int> distribution(100000, 999999);

int main()
{
    const auto samples{ make_unique<vector<int>>(100000) };

    for (auto &sample : *samples)
        sample = distribution(generator);

    cout.imbue(std::locale(""));
    cout << "Searching vector of "
        << samples->size() << " integers..."
        << endl;

    auto startTime = system_clock::now();

    int numPrimes = CountPrimes(samples);

    auto stopTime = system_clock::now();

    auto totalTime = duration_cast<milliseconds>(stopTime - startTime);

    cout << "Number of Primes: " << numPrimes << endl;
    cout << "Total run time (ms): " << totalTime.count() << endl;

    system("pause");
    return 0;
}

int CountPrimes(unique_ptr<vector<int>> const &samples)
{
    int numPrimes{};
    for (const auto &sample : *samples) {
        bool isPrime = true;
        int n{ 2 };
        int m{ 3 };
        if (sample % n == 0)
        {
            isPrime = false;
        }
        while (m < sample && m < 990)
        {
            if (sample % m == 0)
            {
                isPrime = false;
                break;
            }
            m += 2;
        }

        if (isPrime)
            numPrimes++;
    }
    return numPrimes;
}

Your CountPrimes function wrongly returns 3 (instead of the correct answer 0) when given the input {982081, 988027, 994009}. Can you see why?

Once you get down into dozens-of-milliseconds time ranges, it makes sense to increase the size of your test case so that you can distinguish real algorithmic improvements from noise. I recommend using 10,000,000 integers in your vector instead of 100,000, so that your runtimes are back up in the whole numbers of seconds instead of faster-than-human-reaction-time. A change that takes your runtime from 3.5 seconds to 1.5 seconds is vastly more likely to be a real optimization than a change that takes your reported runtime from 75 milliseconds to 20 milliseconds.

seed_seq seed{ 2016 };
default_random_engine generator{ seed };
uniform_int_distribution<int> distribution(100000, 999999);

Global variables are evil. In this case, these variables are used only by main; so you should make them local to main. (If you still wanted them to be statically allocated instead of stack-allocated, you could qualify them with static; but protip: there's no reason to do that.)

int CountPrimes(unique_ptr<vector<int>> const &samples)

Stylistically, most C++ programmers would write this as

int CountPrimes(const std::unique_ptr<std::vector<int>>& samples)

(having internalized the advice that using namespace std; is a bad habit, and finding const X& easier to read than X const &). Your mileage may vary.

However, definitely you should not be using unique_ptr here. You have three indirections here where only one is needed:

The actual data is in a buffer on the heap...
which is pointed to by a pointer wrapped in a std::vector...
which is pointed to by a pointer wrapped in a std::unique_ptr...
which is pointed to by the reference argument to CountPrimes.

Instead of all this indirection, I recommend either the "standard" two levels of indirection:

int CountPrimes(const std::vector<int>& samples)

or if you can use the C++ Core Guidelines support library, you could dispense with one more level:

int CountPrimes(gsl::span<int> samples)

Anyway, get rid of that unique_ptr. It's not buying you anything. And as a good rule of thumb: passing any kind of smart pointer by reference is just as much of a code smell as passing a core-language pointer by reference. If you find yourself doing it, something is probably wrong with your design!

int numPrimes{};

is IMHO a needlessly convoluted way to write

int numPrimes = 0;

Likewise,

int n{ 2 };
if (sample % n == 0)
{
    isPrime = false;
}

is IMHO a needlessly complicated way to write

if (sample % 2 == 0) {
    continue;
}

When you know the input isn't prime, any further work you do after that point is wasted. Don't spend time looping on m if you're just going to throw that work away in the end.

If I were writing this code, I'd make a helper function bool IsPrime(int x) that just returns true if x is prime; and then my CountPrimes function could be

int CountPrimes(const std::vector<int>& v)
{
    int result = 0;
    for (auto&& x : v) {
        if (IsPrime(x)) ++result;
    }
    return result;
}

Notice the complete lack of goto, break, or continue in this program; that is, I'm enabling the use of structured programming by breaking my code down into subroutines.

The only reason not to arrange your program logically in this way is if you expect to get some benefit from logically arranging the computations a different way. For example, maybe we could exploit SSE vectorized instructions to do the computation four times faster, something like this:

int CountPrimes4x(const int *abcd)
{
    // use some _mm_... intrinsics or something
}

int CountPrimes(const std::vector<int>& v)
{
    int result = 0;
    assert(v.size() % 4 == 0);
    for (size_t i=0; i < v.size(); i += 4) {
        result += CountPrimes4x(&v[i]);
    }
    return result;
}

Problem is, there's no fast integer division instruction on x86, so we might not come up with anything better than the plain old (slow) (non-vectorized) integer division we started with.


Computing integer square roots in Java - follow-up (See the previous iteration.)

My two previous methods for computing the integer square root of a number \$N\$ ran in the \$\mathcal{O}(\sqrt{N})\$ worst case time. Now I have added a method (intSqrt3) that runs in \$\mathcal{O}(\log \sqrt{N})\$ time:

Main.java:

import java.util.Random;
import java.util.function.Function;

public class Main {

    public static long intSqrt1(long number) {
        long sqrt = 0L;

        while ((sqrt + 1) * (sqrt + 1) <= number) {
            sqrt++;
        }

        return sqrt;
    }

    public static long intSqrt2(long number) {
        if (number <= 0L) {
            return 0L;
        }

        long sqrt = 1L;

        while (4 * sqrt * sqrt <= number) {
            sqrt *= 2;
        }

        while ((sqrt + 1) * (sqrt + 1) <= number) {
            sqrt++;
        }

        return sqrt;
    }

    public static long intSqrt3(long number) {
        if (number <= 0L) {
            return 0L;
        }

        long sqrt = 1L;

        // Do the exponential search.
        while (4 * sqrt * sqrt <= number) {
            sqrt *= 2;
        }

        long left = sqrt;
        long right = 2 * sqrt;
        long middle = 0;

        // Do the binary search over the range that is guaranteed to contain
        // the integer square root.
        while (left < right) {
            middle = left + (right - left) / 2;

            if (middle * middle < number) {
                left = middle + 1;
            } else if (middle * middle > number) {
                right = middle - 1;
            } else {
                return middle;
            }
        }

        // Correct the binary search "noise". This iterates no more than 3
        // times.
        long ret = middle + 1;

        while (ret * ret > number) {
            --ret;
        }

        return ret;
    }

    public static long intSqrt4(long number) {
        return (long) Math.sqrt(number);
    }

    private static void profile(Function<Long, Long> function, Long number) {
        long result = 0L;
        long startTime = System.nanoTime();

        for (int i = 0; i < ITERATIONS; ++i) {
            result = function.apply(number);
        }

        long endTime = System.nanoTime();

        System.out.printf("Time: %.2f, result: %d.\n",
                          (endTime - startTime) / 1e6,
                          result);
    }

    private static final int ITERATIONS = 1_000;
    private static final long UPPER_BOUND = 1_000_000_000_000L;

    public static void main(String[] args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        long number = Math.abs(random.nextLong()) % UPPER_BOUND;

        System.out.println("Seed = " + seed);
        System.out.println("Number: " + number);

        profile(Main::intSqrt1, number);
        profile(Main::intSqrt2, number);
        profile(Main::intSqrt3, number);
        profile(Main::intSqrt4, number);
    }
}

The performance figures I get looks like this:

Seed = 19608492647714
Number: 54383384696
Time: 531.18, result: 233202.
Time: 218.41, result: 233202.
Time: 1.81, result: 233202.
Time: 0.43, result: 233202.

Above, intSqrt3 took 1.81 milliseconds.

Critique request

Is there something I could improve? Naming/coding conventions? Performance? API design?

When using function parameters, use the primitive types when available:

Function<Long, Long> function

is a red-flag, and should be LongUnaryOperator.

Your code will spin in to an infinite loop for 25% of all long values .... anything larger than Long.MAX_VALUE/4 will cause this loop to become infinite:

    // Do the exponential search.
    while (4 * sqrt * sqrt <= number) {
        sqrt *= 2;
    }

About that loop.... why do you have a magic number 4....? What does it do?

This code needs more testing... and magic numbers need to be removed.


recursive function improvement I am creating routes from an array of menuItems. I have written a recursive function, which works fine but I think the code can be improved. So, I need you guys to review my code and suggest me some changes.

Here is the code:

const accumulator = [];
const renderRoutes = (_menuItems) => {
  _menuItems.forEach((menuItem) => {
    accumulator.push(
      <Route
        exact
        path={menuItem.path}
        render={props => (
          <Scene
            {...props}
            menuItem={menuItem}
          />
        )}
      />,
    );
    if (menuItem.children) {
      renderRoutes(menuItem.children);
    }
  });
  return accumulator;
};

Avoid recursion, avoid putting the accumulator out of the function that fills it.

My favourite phrase: Every recursive algorithm can be rewritten without recursion. In worst case, using one (extra) stack.

function renderRoutes(menuItems) {
  let accumulator = [];
  let queue = [];
  queue.concat(menuItems);
  while (queue.length > 0) {
    const item = queue.shift();
    accumulator.push(route(item))
    queue.concat(item.children);
  }
  return accumulator;
}

The route(item) is the same as your <Route....


Initializing global object from one thread and waiting for it in other threads Is everything OK with this code?

I need this mechanism:

I want to initialize global object of type A (named 'gA'), which may take very long time
I don't want to wait for gA to be initialized, I want to start other threads at the same time (in order for the program to be responsive)
Other threads also take some time to initialize their own stuff, and when they are ready, they want to use the gA. It can happen at any moment, before or after gA is initialized. I must assume that other threads are ready before gA is initialized and must wait therefore wait for gA.

I came up with this simple solution using shared_future. The code works and does what I want. I only wonder if there are some dangers hidden within this approach. Maybe you can spot some bug in this code?

#include <iostream>
#include <chrono>
#include <memory>
#include <future>
#include <functional>

using namespace std;
using namespace chrono_literals;

struct A
{
    A() { cout << "ctor A" << endl; }
    ~A() { cout << "dtor A" << endl; }
    void talk(string name) { cout << "[" << this_thread::get_id() << "] A is talking from thread " << name << endl; }
};

// global A object which threads of type B want to use
unique_ptr<A> gA;

bool initA()
{
    int i = 0;
    while (i++ < 7)
    {
        this_thread::sleep_for(1s);
        cout << "[" << this_thread::get_id() << "] Initializing global object gA, it takes a lot of time... (" << i << ")" << endl;
    }
    gA.reset(new A());
    cout << "[" << this_thread::get_id() << "] gA is ready to use!" << endl;
    return true;
};

void funB(string name, shared_future<bool> futA)
{
    int i = 0;
    while (i++ < 3)
    {
        this_thread::sleep_for(1s);
        cout << "[" << this_thread::get_id() << "] Initializing thread " << name << "... (" << i << ")" << endl;
    }
    cout << "[" << this_thread::get_id() << "] Now thread " << name << " waits to use global gA" << endl;
    futA.wait();

    cout << "[" << this_thread::get_id() << "] Ok, now thread " << name << " can use global gA" << endl;
    gA->talk(name);
}

int main()
{
    cout << "[" << this_thread::get_id() << "] Starting main..." << endl;

    shared_future<bool> sharedFutA(async(launch::async, initA));

    thread tB1(funB, string("B1"), sharedFutA);
    thread tB2(funB, string("B2"), sharedFutA);
    thread tB3(funB, string("B3"), sharedFutA);

    tB1.join();
    tB2.join();
    tB3.join();

    cout << "Done" << endl;
}

Seems reasonable to me. Just a few nits first:

You should never using namespace std; in real code. Just write std::string, and so on. It'll save your readers some confusion, and it'll avoid subtle bugs related to ADL that you'll only learn about much later in life.
using namespace std::chrono_literals is presumably a type for using namespace std::literals or maybe using namespace std::literals::chrono_literals.
You've got some spurious semicolons: }; should be } in at least one place.

Unless the value of the bool being passed through the future — true or false — is meaningful, it shouldn't be part of your program. In this case you could (and therefore should) be using std::shared_future<void> instead of std::shared_future<bool>.

There is a simpler and therefore perhaps better thread-synchronization mechanism, if all your threads are launching from the same spot at the same time. Use a mutex which is locked when the threads spawn, and force each thread to "check in" by locking that mutex before it's allowed to continue. For example:

// global A object which threads of type B want to use
std::unique_ptr<A> gA;

void initA(std::unique_lock<std::mutex> lk)
{
    // do setup here

    gA = std::make_unique<A>();

    // now signal that it's okay for the B threads to start
    lk.unlock();
}

void funB(std::string name, std::mutex& checkpoint)
{
    // do initial setup here

    checkpoint.lock(); checkpoint.unlock();

    gA->talk(name);
}

int main() {
    std::mutex checkpoint;
    std::unique_lock<std::mutex> lk(checkpoint);
    auto tB1 = std::thread(funB, string("B1"), std::ref(checkpoint));
    auto tB2 = std::thread(funB, string("B2"), std::ref(checkpoint));
    auto tB3 = std::thread(funB, string("B3"), std::ref(checkpoint));
    initA(std::move(lk));
[...]

Notice that the lk.unlock() in initA isn't strictly needed, as written, because the destructor of lk was going to drop that lock anyway. But you could put more code after lk.unlock() if you had more things to do that didn't affect gA.

Also notice that I'm using make_unique instead of reset(new ...). Always prefer to use make_unique and make_shared instead of raw new and delete — again because it helps avoid subtle exception-related bugs which if you're lucky you'll never see in the wild; but also because if you get in the habit of never writing new or delete yourself, you'll be able to spot more easily when other people's code incorrectly uses new or delete. Ideally, you want to get in a situation where you can install a git commit hook that does a git grep \bnew\b and fails if it finds any!


Socket chat room in Python This is a Python chat room that I've been working on and it enables to you to chat to other people on the same network through Python.

Server.py:

import socket
import sys

s = socket.socket()
host = socket.gethostname()
print(" server will start on host : ", host)
port = 8080
s.bind((host,port))
name = input(str("Please enter your username: "))
print("")
print("Server is waiting for incoming connections")
print("")
s.listen(1)
conn, addr = s.accept()
print("Recieved connection")
print("")
s_name = conn.recv(1024)
s_name = s_name.decode()
print(s_name, "has joined the chat room")
conn.send(name.encode())

while 1:
    message = input(str("Please enter your message: "))
    conn.send(message.encode())
    print("Sent")
    print("")
    message = conn.recv(1024)
    message = message.decode()
    print(s_name, ":" ,message)
    print("")

Client.py:

import socket
import sys

s = socket.socket()
host = input(str("Please enter the hostname of the server : "))
port = 8080
s.connect((host,port))
name = input(str("Please enter your username : "))
print(" Connected to chat server")

s.send(name.encode())
s_name = s.recv(1024)
s_name = s_name.decode()
print("")
print(s_name, "has joined the chat room ")

while 1:
    message = s.recv(1024)
    message = message.decode()
    print(s_name, ":" ,message)
    print("")
    message = input(str("Please enter your message: "))
    message = message.encode()
    s.send(message)
    print("Sent")
    print("")

I just wanted suggestions on how I can to improve this chatroom to make it better and faster. All suggestions will be greatly appreciated.

host = input(str("Please enter the hostname of the server : "))
...
message = input(str("Please enter your message: "))

can be changed to simply:

message = input("Please enter your message: ")
...
host = input("Please enter the hostname of the server : ")

since there is no need to cast a string to a string.

while 1:

is fine, but is more readable as:

while True:

Having print statements like the following:

print("")

is redundant. If you want an extra newline after a print statement; Add "\n" to the end of the preceding print statements to remove a function call, and reduce code clutter. E.G:

print("Sent\n")

This is more of a personal preference, but fstring formatting is more readable  than the following:

print(s_name, ":" ,message)

should be:

print( f"{s_name}: {message}" )


Check if one string is a permutation of another using Python The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview."

I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the length of each string (they should be the same length since I am checking if there lengths are equal) and the space complexity is \$O(n)\$.

Is this correct?  In particular does checking the length of each string take \$O(1)\$ time?

def is_permutation(first_string, other_string):
    if len(first_string) != len(other_string):
        return False

    count_first = {}
    count_other = {}

    for char in first_string:
        if char in count_first.keys():
            count_first[char] += 1
        else:
            count_first[char] = 1

    for char in other_string:
        if char in count_other.keys():
            count_other[char] += 1
        else:
            count_other[char] = 1

    for char in count_first.keys():
        if char not in count_other.keys():
            return False
        elif count_first[char] != count_other[char]:
            return False

    return True

Yes, len(str) should be O(1) in Python.  (Good question!)  Each of your for loops is O(n), so your whole function is O(n).

Your counting loops could be written more compactly as

for char in first_string:
    count_first[char] = 1 + count_first.get(char, 0)

The epilogue could be simplified to

return count_first == count_other

It pays to get familiar with the standard Python library, though.  Your entire function could be more simply implemented as

from collections import Counter

def is_permutation(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

… where len(a) == len(b) is an optional optimization.  Writing less code simplifies maintenance and tends to create fewer opportunities for introducing bugs (as in Rev 2 of your question).


How to hide implementation of JDBC while processing large query in client's code? I have client's methods that processes a large SQL query. I wouldn't like to do that through getting whole query result to memory, but process it in batches. It entails with exposing JDBC API to client's code.  I think that this code could be refactored much better.

    //client's method
    m_jdbcManager = JdbcManagerUtil.getInstance();
    m_tupleManager = DbTupleManager.getInstance();
    Connection connection = null;
    PreparedStatement statement = null;
    ResultSet resultSet = null;
    try {
        connection = m_jdbcManager.getConnection();
        connection.setAutoCommit(false);
        statement = connection
                .prepareStatement(Statements.SELECT_RIGHT_TUPLES);
        statement.setInt(1, id);
        statement.setFetchSize(JdbcManagerUtil.FETCH_SIZE);
        resultSet = statement.executeQuery();
        while (resultSet.next()) {
            Tuple tuple = (Tuple) m_tupleManager
                    .readObject(resultSet);
            //process tuple, invokes methods from client class
        }
        connection.setAutoCommit(true);
        JdbcManagerUtil.closeEverything(connection, statement, resultSet);
    } catch (<exceptions>) {
    }

I tried to expose method that returns ResultSet, but after processing, there must be released resources Connection, PreparedStatement and ResultSet.
JDBC 4 and PostreSQL database.

Your assumption that the entire dataset is read in to memory is not necessarily accurate. The JDBC clients I have worked with (DB2, MS-SQLServer, Sybase, Oracle, etc.) each default to, or have an option to limit the size of the client-side buffer. You only have a small amount of data on the actual client, and the ResultSet process fetches more data when you iterate through it.

There is no need to add another level of buffering. Are you sure the data is all being returned? Have you inspected the configuration options for your JDBC Client?


Representing an adjacency list (graph) using a hash table of lists While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews.

I tried to implement the graph as follows:

template <typename T, typename K> struct graph {
    unordered_map< T, list< pair<T, K> > > adjList;
    bool directed = 1;
};

This allowed me to store a list of pairs (where first is the destination vertex, and second is the weight) for every vertex, and the adjacency list can be indexed by the vertex content.

So far, I was able to implement the basic operations successfully:

insertEdge()
removeEdge()
searchEdge()
printGraph() (prints all edges)

These operations behave correctly for both directed and undirected graphs.

template <typename T, typename K> struct graph {
    unordered_map< T, list< pair<T, K> > > adjList;
    bool directed = 1;
};

template <typename T, typename K> void reinit(graph<T, K>& g, bool directed)
{
    g.directed = directed;
    g.adjList.clear();
}

template <typename T, typename K> void insertEdge(graph<T, K>& g, T v1, T v2, K weight)
{
    g.adjList[v1].push_front(std::make_pair(v2, weight));
    if (!g.directed)
        g.adjList[v2].push_front(std::make_pair(v1, weight));
}

template <typename T, typename K> void printGraph(graph<T, K>& g)
{
    cout << "Graph is " << (g.directed ? "directed" : "undirected") << endl;
    for (const auto& v : g.adjList) //for every vertex
        for (const auto& e : v.second)
            cout << v.first << "---" << e.second << "---" << e.first << endl;
}

template <typename T, typename K> K searchEdge(graph<T, K>& g, T v1, T v2)
{   //test if edge(v1,v2) is graph
    auto l = g.adjList.find(v1);
    if (l != g.adjList.end())
        for (auto e : l->second)
            if (e.first == v2)
                return e.second;

    return numeric_limits<K>::min();
}

template <typename T, typename K> void removeEdge(graph<T, K>& g, T v1, T v2)
{
    if (GRAPH::searchEdge(g, v1, v2) != numeric_limits<K>::min())
    {
        auto l = g.adjList.find(v1);
        for (auto e = l->second.begin(); e != l->second.end(); e++)
            if (e->first == v2)
            {
                l->second.erase(e);
                return;
            }
    }
}

For the most part, I found trouble implementing breadth-first search and depth-first search algorithms. If the current structure is not that great, please suggest any changes/reformulations. If it's passable, please suggest how I can approach those mentioned algorithms.

General Comments

Write your code for readability.

You don't normally see templates written like this:

template <typename T, typename K> void printGraph(graph<T, K>& g)

It pushes the information you want all the way to the right. Normally, I would expect to see the template code on the first line, followed by the object it templates (looking like a normal bit of code):

template <typename T, typename K>
void printGraph(graph<T, K>& g)

The space between > when closing a template has not been needed in over 5 years. Let it be consigned to the big bit bucket in the sky.

 list<pair<T, K> > >

I notice your lack of using std:: when declaring your types.

 unordered_map< T, list

This not only means you have using namespace std; in your code, but that you have it in a header file (or you have a lot of using XXXX; but causes the same issues). The use of using namespace std; in normal code is considered bad practice. But the use of it in a header file is so bad that people will ban your code from projects. You are basically infecting any code that includes your header. This can lead to subtle, impossible-to-find errors. Don't do it.

I would also prefer if you would use an initial capital letter for type information. The most important part of C++ is the type system. Being able to identify types easily is essential. Thus, most people use an initial capital letter to identify user-defined types, while an initial lower-case letter identifies an object.

Build your types from smaller types. This will make it easier to maintain your code as it localizes changes. For example, rather than using std::pair<T, K> as your edge definition, prefer to use a named type Edge. That way, if you change the definition of the type, you only have to change it in a single location and not trawl through your code looking for all uses. Also, using a name like that provides context and meaning, which in turn makes your code easier to read.

template <typename T, typename K>
struct Graph
{
    using Edge        = std::pair<T, K>;
    using EdgeList    = std::list<Edge>;
    using AdjencyList = std::unordered_map<T, EdgeList>;

    AdjencyList adjList;
    bool        directed = true; // use real bool(s) not int.
};

Design Comments

You are completely ignoring encapsulation. Your functions may work, but because your data is completely exposed, there is no protection from a bad coder coming along and breaking your constraints. Your methods are supposed to be the only way to manipulate the state (so it can be controlled).

Because of this, your code would fail any competent code review and not be allowed into the code base.


Handling GetTickCount() overflow in timeouts This is code which must run on XP, so no GetTickCount64, and which should correctly handle the value wrapping around after 49 days. Can it be improved?

// DWORD timeoutMs is a given parameter.

DWORD beginMs = (timeoutMs == INFINITE ? 0 : ::GetTickCount());
DWORD endMs = beginMs + timeoutMs; // unsigned arithmethic is Mod(MAX+1)
DWORD currentMs;

// Create Process, omitted for brevity

while ((waitResult = ::WaitForSingleObject(pi.hProcess, DEFAULT_WAIT_MS)) == WAIT_TIMEOUT)
{
    if (timeoutMs != INFINITE)
    {
        bool timeoutReached = false;
        currentMs = ::GetTickCount();
        if (beginMs <= endMs) // normal case
        {
            if (currentMs > endMs)
            {
                timeoutReached = true;
            }
        }
        else // special case: tick count wrapped around after 49 days uptime
        {
            if (currentMs < beginMs && currentMs > endMs)
            {
                timeoutReached = true;
            }
        }

        if (timeoutReached)
        {
            ::TerminateProcess(pi.hProcess, 0);
            break;
        }
    }
}

Unsigned subtraction (and automatic mod 2^32) will always give currentMs - beginMs == elapsedMs, even when beginMs > currentMs, and as long as the actual elapsed time doesn't overflow the tick count (it isn't greater than 49 days).

So you could replace the original with the following code:

DWORD beginMs = GetTickCount();

// Create Process, omitted for brevity

while ((waitResult = WaitForSingleObject(pi.hProcess, DEFAULT_WAIT_MS)) == WAIT_TIMEOUT) {
    if (timeoutMs != INFINITE) {
        DWORD currentMs = GetTickCount();
        bool timeoutReached = currentMs - beginMs > timeoutMs;
        if (timeoutReached) {
            TerminateProcess(pi.hProcess, 0);
            break;
        }
    }
}

And you could even go a step further and eliminate the variables currentMs and timeoutReached: if (GetTickCount() - beginMs > timeoutMs) {...


Grid search parameter combinations in Python For a computation engineering model, I want to do a grid search for all feasible parameter combinations. Each parameter has a certain possibility range, e.g. (0 … 100) and the parameter combination must fulfil the condition a+b+c=100. An example:

ranges = {
    'a': (95, 99),
    'b': (1, 4),
    'c': (1, 2)}
increment = 1.0
target = 100.0

So the combinations that fulfil the condition a+b+c=100 are:

[(95, 4, 1), (95, 3, 2), (96, 2, 2),
 (96, 3, 1), (97, 1, 2), (97, 2, 1),
 (98, 1, 1)]

This algorithm should run with any number of parameters, range lengths, and increments.

The solutions I have come up with is brute-forcing the problem. That means calculating all combinations and then discarding the ones that do not fulfil the given condition. I have to use np.isclose(), because when using floats, the rounding error in Python's will not lead to an exact sum.

def solution(ranges, increment, target):
    combinations = []
    for parameter in ranges:
        combinations.append(list(np.arange(ranges[parameter][0], ranges[parameter][1], increment)))
        # np.arange() is exclusive of the upper bound, let's fix that
        if combinations[-1][-1] != ranges[parameter][1]:
            combinations[-1].append(ranges[parameter][1])
    result = []
    for combination in itertools.product(*combinations):
        # using np.isclose() so that the algorithm works for floats
        if np.isclose(sum(combination), target):
            result.append(combination)
    df = pd.DataFrame(result, columns=ranges.keys())
    return df

However, this quickly takes a few days to compute. Hence, both solutions are not viable for large number of parameters and ranges. For instance, one set that I am trying to solve is (already unpacked combinations variable):

[[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0],
 [22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0, 51.0, 52.0, 53.0, 54.0, 55.0, 56.0, 57.0, 58.0, 59.0, 60.0, 61.0, 62.0, 63.0, 64.0, 65.0, 66.0, 67.0, 68.0, 69.0, 70.0, 71.0, 72.0, 73.0, 74.0, 75.0, 76.0, 77.0, 78.0, 79.0, 80.0, 81.0, 82.0, 83.0, 84.0, 85.0, 86.0, 87.0, 88.0],
 [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0],
 [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0], [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0],
 [0.0, 1.0, 2.0],
 [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0],
 [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0],
 [0.0],
 [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0],
 [0.0]]

This results in memory use of >40 GB and calculation time >400 hours.
Do you see a solution that is either faster or more intelligent, i.e. not trying to brute-force the problem?

split
The method does a few things at the same time.

It expands the ranges
generates the combinations
takes the sums
compares to the target
assembles a DataFrame

better would be to split it up in a few logical units. This will not only help freeing memory in-between steps, but also help with debugging the intermediate values
looping
Check the talk "Looping like a pro"
You loop over the index, and end up with real long variables like ranges[parameter][0]. If you use tuple expansion, you can do this:
def expand(ranges, increment):
    for start, end in ranges.values():
        expansion= list(np.arange(start, end, increment))
        # np.arange() is exclusive of the upper bound, let's fix that
        if expansion[-1] != end:
            expansion.append(end)
        yield expansion

For me, this is a lot clearer. It also has the benefit of keeping the lines shorter.
Since it are more the expansions of the ranges you create instead of the combinations, I renamed the method and variables.
This also uses a generator instead of an intermediate list.
This alternative might even simpler:
def expand(ranges, increment):
    for start, end in ranges.values():
        yield  np.arange(start, end + increment/2, increment)

This can then be combined and summed like this:
def combine_naive(expansions, target):
    for combination in itertools.product(*expansions):
        # using np.isclose() so that the algorithm works for floats
        if np.isclose(sum(combination), target):
            yield combination

I like your comment there. It explains why you use np.isclose instead of ==
Alternative approaches
numpy
instead of having itertools.product assemble the combinations, you could use numpy.meshgrid
def combine_numpy(expansions, target):
    grid = np.meshgrid(*expansions)
    summary = np.array(grid).sum(axis=0)
    indices = np.where(np.isclose(summary, target))
    return (
        [row[i] for row, i in zip(expansions, idx)]
        for idx in zip(*indices)
    )

This is approximately the same, but staying in the numpy universe. You can reduce the memory footprint here with the correct choice of dtype and reducing the number of intermediary variables
sorted
or you could use the fact the expansions are sorted, and break when a sum is over the target. This uses recursion, tuple unpacking and the fact an empty sequence is Falsey.
def combine_sorted(expansions, target, previous=()):
    series, *rest = expansions

    sum_max = sum(item[-1] for item in rest)
    for item in series:
        current = previous + (item,)
        sum_current = sum(current)
        if rest:
            if sum_current + sum_max < target and not np.isclose(
                sum_current + sum_max, target
            ):
                continue
            yield from combine_sorted(rest, target, previous=current)
        else:
            if np.isclose(sum_current, target):
                yield current
            elif sum_current > target:
                return

The sum_max is to skip numbers where the total some will be less than target as soon as possible.
testing and timing with real data will show which option is more memory and CPU intensive.
if __name__ == "__main__":
    ranges = {"a": (95, 99), "b": (1, 4), "c": (1, 2)}
    increment = 1.0
    target = 100.0
    df = solution(ranges, increment, target)

    expansions = list(expand(ranges, increment))
    results = list(combine_naive(expansions, target))
    df1 = pd.DataFrame(results, columns=ranges.keys())
    print(df1)

    results_sorted = list(combine_sorted(expansions, target))
    print(results_sorted)
    df_sorted = pd.DataFrame(results_sorted, columns=ranges.keys())
    print(df_sorted)

    results_numpy = list(combine_numpy(expansions, target))
    print(results_numpy)
    df_sorted = pd.DataFrame(results_numpy, columns=ranges.keys())
    print(df_sorted)


JavaScript date format string to php date format string convert Please find the following scenario, I've dynamic JS date format string from API but I am looking for the best way to convert the format that accepts in PHP date format. For now, I wrote it my own way but I doubt there should be a standard solution.
JS time format: YYYY-MM-DD / YYYY/MM/DD
Need PHP format: Y-m-d / Y/m/d
I've written the solution this way, please let me know if you find something else in a better way than this.
function dateFormatStringConvert(string $format) : string
{
    foreach (['-', '/'] as $operator) {
        if (strpos($format, $operator) !== false) {
            return implode($operator, array_map(function ($piece){
                return $piece[0]=='M' || $piece[0]=='D' ? strtolower($piece[0]) : $piece[0];
            }, explode($operator, $format)));
        }
    }
    return 'm-d-Y';
}

I don't see the need to do so much dynamic work.  I would establish a lookup array to access.  This will be clean, direct, and easy to maintain.  If the incoming format is not found, just fallback to m-d-Y using the null coalescing operator.
private $formatLookup = [
    'YYYY-MM-DD' => 'Y-m-d',
    'YYYY/MM/DD' => 'Y/m/d',
];

public function dateFormatStringConvert(string $format) : string
{
    return $this->formatLookup[$format] ?? 'm-d-Y';
}

With this setup, you never need to touch the processing method, you only need to maintain the lookup array.


Complexity in multiple if-else algorithms I am learning Algorithms, Part I on coursera.org. I just watched the first lecture then tried to write some code in C#. The class basically stores list of connected numbers. You can add numbers that connected together by calling Union and check if they are connected by calling AreConnected. Code is as follows:

public class UnionFind
{
    private readonly List<HashSet<int>> source;

    public static UnionFind Create()
    {
        return new UnionFind();
    }

    private UnionFind()
    {
        this.source = new List<HashSet<int>>();
    }

    public void Union(int left, int right)
    {
        var isLeftExist = this.source.FirstOrDefault(o => o.Contains(left));
        var isRightExist = this.source.FirstOrDefault(o => o.Contains(right));

        if (isLeftExist == null &&
            isRightExist == null)
        {
            var hash = new HashSet<int>();
            hash.Add(left);
            hash.Add(right);

            this.source.Add(hash);
        }
        else if (isLeftExist != null &&
            isRightExist == null)
        {
            isLeftExist.Add(right);
        }
        else if (isRightExist != null &&
            isLeftExist == null)
        {
            isRightExist.Add(left);
        }
        else
        {
            // found left and right
            this.source.Remove(isRightExist);

            foreach (var item in isRightExist)
            {
                isLeftExist.Add(item);
            }
        }
    }

    public bool AreConnected(int left, int right)
    {
        return this.source
            .Any(o =>
                o.Contains(left) &&
                o.Contains(right));
    }

To make it easier to understand, this is unit test class.

[TestClass]
public class UnionFindTests
{
    [TestMethod]
    public void SimpleUnionTest()
    {
        int left = 10;
        int right = 20;

        var uf = UnionFind.Create();

        uf.Union(left, right);
        Assert.IsTrue(uf.AreConnected(left, right));
    }

    [TestMethod]
    public void DuplicateUnionTest()
    {
        int left = 10;
        int right = 10;

        var uf = UnionFind.Create();

        uf.Union(left, right);
        Assert.IsTrue(uf.AreConnected(left, right));
    }

    [TestMethod]
    public void MultipleLinksUnionTest()
    {
        int left1 = 10;
        int left2 = 20;
        int left3 = 30;

        int right1 = 15;
        int right2 = 25;
        int right3 = 35;

        var uf = UnionFind.Create();
        uf.Union(left1, right1);
        uf.Union(left2, right2);
        uf.Union(left3, right3);

        uf.Union(left1, right2);
        Assert.IsTrue(uf.AreConnected(left2, right1));
    }
}

UnionFind works find and pass all tests in unit test. The problem is I found method Union has many if-else and I want to get rid of it. Is there a simpler way of implementing Union method?

Building on @alzaimar's answer:

You can unfold the conditionals with early return. The linear flow makes it slightly easier to follow.

if (listContainingLeft == null && listContainingRight == null)
{
    AddBranch(left, right);
    return;
}

if (listContainingLeft != null && listContainingRight != null)
{
    Combine(listContainingLeft, listContainingRight);
    return;
}

if (listContainingLeft != null)
{
    listContainingLeft.Add(right);
    return;
}

if (listContainingRight != null)
{
    listContainingRight.Add(left);
    return;
}


Wrapping JS file in function, and assigning that function to a variable I've been reading about wrapping JS files in functions to call them on load, etc. I also was looking at namespaces and how to avoid collisions with functions/objects/variables of the same name. What improvements can be made? I know the code works, I'm more concerned with best practices for wrapping JS files and using namespaces.

// codereview.js:
var codeReview = (function() {
    // basically "private" function? Will there be a collision with jQuery here?
    function $(id) {
        return document.getElementById(id);
    }

    // "public" functions
    return {
        fizzbuzz: function() {
            var newhtml = '';
            var output = 0;
            for (var i = 1; i <= 100; i++) {
                if (i % 3 == 0 && i % 5 == 0) {
                    output = "FizzBuzz";
                } else if (i % 3 == 0) {
                    output = "Fizz";
                } else if (i % 5 == 0) {
                    output = "Buzz";
                } else {
                    output = i;
                }
                newhtml += output + "<br />";
            }
            $('fizzbuzz-output').innerHTML = newhtml;
        },
        email: function() {
            var first = "test@em";
            var last = "ail.com";
            var email = first + last;
            $('my_email').innerHTML = email;
        }
    }
})();

Both of the "public" functions would be called via codeReview.fizzbuzz() or codeReview.email()

Also, codeReview.email() is basically just to click and reveal my email address. I did it this way thinking it couldn't get scraped, is that accurate or did I just come up with a super complicated way to display an email address?

From a organizing perspective you are doing fine, in essence you used the Module Pattern. I would just advise you to consider placing 'use strict'; in the beginning of your function.

As you probably figured out, $ does not collide with jQuery. Though, for this piece of code I would not create a one line function if you are only going to call that function once.

For the email thing, I think it might fool a number of scrapers, I'd keep it.

For fizzbuzz, while your code is working, I think the goal is to use a minimum amount of modulo statements, your code could be written with fewer modulo statements..

My counter suggestion is very close to your code:

// codereview.js:
var codeReview = (function() {

    // "public" functions
    return {
        fizzbuzz: function() {
            var output, i;
            for (i = 1; i <= 100; i++) {
                output = '';
                if (i % 3 == 0) {
                    output = 'Fizz';
                }
                if (i % 5 == 0) {
                  output += 'Buzz';
                }
                output = output || i;
                console.log(output);
            }
        },
        email: function() {
            var first = 'test@em';
            var last = 'ail.com';
            var email = first + last;
            return document.getElementById('my_email').innerHTML = email;
        }
    }
})();

codeReview.fizzbuzz();

This was an interesting read, which provided an alternative inner loop which is more code review friendly:

            for (i = 1; i <= 100; i++) {
                if (i % 15 == 0) {
                    output = 'FizzBuzz';
                }
                else if (i % 3 == 0) {
                    output = 'Fizz';
                }
                else if (i % 5 == 0) {
                  output += 'Buzz';
                }
                else{
                  output = i;
                }
                console.log(output);
            }


More efficient loops to generate unpronounceable words I wanted to write a function to generate only unpronounceable words. I realised afterwards that the same thing could probably be achieved by just taking out the vowels. Regardless, I feel that there is probably a better way to iterate through the syllable checking.

function unpronouncable(length) {
    var twoLetters = ['aa','ae','ag','ai','ar','ao','as','aw','ay','ba','da','de','ed','ef','eh','ei','em','en','er','et','ex','fa','fe','fu','gi','go','hm','ho','so','id','ie','jo','ka','ki','ku','lo','mi','mm','mu','na','ne','nu','od','oe','oi','om','op','os','os','oy','pe','pi','qi','re','se','ta','ti','ut','wo','xi','xi','ya','yu','za','zo','co','my','qu','ge','ro','ra','xa','wa'];
    var threeLetters = ['thm','css','dvd','buh','bad','rue','cun','pub','puk','pul'];

    var letters = "abcdefghijklmnopqrstuvwxyz";
    var string = "";
    for (var i = 0; i < length; i += 1) {
        string += letters[Math.floor(Math.random() * letters.length)];
    }

    function generate() {
        for (var j = 0; j < string.length; j += 1) {
            var test = string.slice(j,j+2);
            for (var k = 0; k < twoLetters.length; k += 1) {
                if (twoLetters[k] === test) {
                    console.log('Has two letter syllable');
                    return unpronouncable(length);
                }
            }
        }
        for (var j = 0; j < string.length; j += 1) {
            var test = string.slice(j,j+3);
            for (var k = 0; k < twoLetters.length; k += 1) {
                if (threeLetters[k] === test) {
                    console.log('Has three letter syllable');
                    return unpronouncable(length);
                }
            }
        }

        return string;
    }
    return generate();
}

console.log(unpronouncable(8));

Copy Pasting

If you are copy-pasting code, it is a sign that you should write it differently (your two for loops are quite obviously copy pasted).

Bug

I'm pretty sure that here:

        for (var k = 0; k < twoLetters.length; k += 1) {
            if (threeLetters[k] === test) {

you meant to change it to k < threeLetters.length;.

Solution

Instead of copy-pasting the for loop code, extract it to a function:

function generateHelper(string, array, charCount) {
    for (var j = 0; j < string.length; j += 1) {
        var test = string.slice(j,j+charCount);
        for (var k = 0; k < array.length; k += 1) {
            if (array[k] === test) {
                console.log('Has ' + charCount + ' letter syllable');
                return unpronouncable(length);
            }
        }
    }
}

Coding Style

i++

It is customary to write j++ instead of j += 1 in loops.

loop variable

It is also customary to use i as primary loop variable and j as secondary variable in case the loop is nested inside another loop. As your j-loops in generate are not nested, I would use i for them, and then j instead of k for the nested loop.

Call of return generate();

return should generally be at the end of a function, but in this case, I would pull it up in front of the generate function definition. It is easier to overlook at the bottom.

But the whole generate method seems unnecessary. Couldn't you just remove these lines:

function generate() {
}
return generate();

I don't mean the code inside the function, just the function definition and the function call.

General Approach

You already mentioned that this is probably not the best approach, so I'm not going to say too much about it. Generally, I would probably go with an iterative solution as most of the time they are easier to understand and faster as well.

An example of an iterative approach might look like this:

function unpronouncable(length) {
    // filter these out
    var twoLetters = ['aa', 'ae', 'ag', 'ai', 'ar', 'ao', 'as', 'aw', 'ay', 'ba', 'da', 'de', 'ed', 'ef', 'eh', 'ei', 'em', 'en', 'er', 'et', 'ex', 'fa', 'fe', 'fu', 'gi', 'go', 'hm', 'ho', 'so', 'id', 'ie', 'jo', 'ka', 'ki', 'ku', 'lo', 'mi', 'mm', 'mu', 'na', 'ne', 'nu', 'od', 'oe', 'oi', 'om', 'op', 'os', 'os', 'oy', 'pe', 'pi', 'qi', 're', 'se', 'ta', 'ti', 'ut', 'wo', 'xi', 'xi', 'ya', 'yu', 'za', 'zo', 'co', 'my', 'qu', 'ge', 'ro', 'ra', 'xa', 'wa'];
    var threeLetters = ['thm', 'css', 'dvd', 'buh', 'bad', 'rue', 'cun', 'pub', 'puk', 'pul'];

    // generate a new string until one is found that does not contain the filters
    var generatedString = "";
    var done = false;
    while (!done) {
        generatedString = generate(length);
        done = !contains(generatedString, twoLetters, 2) && !contains(generatedString, threeLetters, 3);
    }
    return generatedString;

    // generates a random string with given length
    function generate(length) {
        var letters = "abcdefghijklmnopqrstuvwxyz";
        var string = "";
        for (var i = 0; i < length; i++) {
            string += letters[Math.floor(Math.random() * letters.length)];
        }
        return string;
    }

    // returns true if string contains any characters in the stringArray.
    function contains(string, stringArray, charCount) {
        for (var k = 0; k < stringArray.length; k++) {
            if (string.indexOf(stringArray[k]) > -1) {
                console.log('Has ' + charCount + ' letter syllable');
                return true;
            }
        }
        return false;
    }
}
console.log(unpronouncable(8));

You could also replace the done = [...] assignment with two if statements, which might be easier to read.

Also: your approach with iterating over the string and using splice is quite complicated. Just use string.indexOf(stringArray[k]) > -1; to check if a string contains another string.

And just out of curiosity: how would you pronounce css or dvd?


unit-testing / mocking a class which contains functionality which depends on itself Take the below code:

public interface ISettingsManager
{
    SettingData GetSettingByIdentifierOrCreateIfDoesNotExist(Enum identifier);
    T GetSetting<T>(Enum identifier);

}

[IocComponent]
public class SettingsManager : ISettingsManager
{
    private readonly ISettingGetItemByIdentifierService _settingGetItemByIdentifierService;

    public SettingsManager(
        ISettingGetItemByIdentifierService settingGetItemByIdentifierService)
    {
        _settingGetItemByIdentifierService = settingGetItemByIdentifierService;
    }

    public SettingData GetSettingByIdentifierOrCreateIfDoesNotExist(Enum identifier)
    {
        SettingData setting = //GetSetting from database;
        return setting;
    }

    #region ISettingsManager Members

    public T GetSetting<T>(Enum identifier)
    {
        var setting = GetSettingByIdentifierOrCreateIfDoesNotExist(identifier);
        return (T)setting.Value;
    }

    #endregion
}

The ISettingsManager is created to retrieve settings for an application.  The main logic is done in GetSettingByIdentifierOrCreateIfDoesNotExist.  The logic is not shown in the example, but this should try to get the setting from the database.

The method GetSetting is a convenience method which basically retrieves the setting from the other method, and casts it to the required value as setting.Value is of type object.

I am trying to follow the Test-Driven-Development guidelines, and hence I assume a unit-test should be created for this method as well.   As it is, one cannot just mock the GetSettingByIdentifierOrCreateIfDoesNotExist, as it is in the same class.

Does it make sense to split this out in another class, so one can mock it?  Personally, I think that these two go together.  Any ideas how one would approach this would be greatly appreciated :)

I'm not sure if you need GetSettingByIdentifierOrCreateIfDoesNotExist declaration in your interface... Do you have special use cases where GetSetting<T> is not enough?

If I'm right and all you need is just GetSetting<T> method then you can go ahead and make GetSettingByIdentifierOrCreateIfDoesNotExist method private, thus you'll make it an implementation specific that doesn't need to be tested separately, you'll test it by testing GetSetting<T>.

If you do need GetSettingByIdentifierOrCreateIfDoesNotExist method, then I would go with a different approach: since GetSetting<T> is just an additional feature on top of GetSettingByIdentifierOrCreateIfDoesNotExist, you can remove it from ISettingsManager interface and rewrite as an extension method like this:

public interface ISettingsManager
{
    SettingData GetSettingByIdentifierOrCreateIfDoesNotExist(Enum identifier);
}

public static class SettingsManagerExtensions
{
    public static T GetSetting<T>(this ISettingsManager manager, Enum identifier)
    {
        var setting = manager.GetSettingByIdentifierOrCreateIfDoesNotExist(identifier);
        return (T)setting.Value;
    }
}


Implementation of cp program that prints the number of bytes copied I have written the code for implementation of the cp program that prints the number of bytes copied when the user presses Ctrl-C. Could someone please review this code and provide feedback. Thanks a lot.

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<fcntl.h>
#include<error.h>
#include<signal.h>
#define buffer_size 512

void signal_handler(int num);
void write_buf(int des_fd, char *buffer, size_t rlen, int *bytes);
int flag = 0;

void signal_handler(int num)
{
    printf("The caught signal number is : %d\n", num);
    flag = 1;
}

void write_buf(int des_fd, char *buffer, size_t rlen, int *bytes)
{
    int wlen;

    while (1) {
        wlen = write(des_fd, buffer, rlen);
        if (wlen == -1)
            error(1, 0, "error in writing the file\n");
        *bytes = *bytes + wlen;
        buffer = buffer + wlen;
        rlen = rlen - wlen;
        if (rlen == 0)
            break;
    }
}

int main()
{
    int src_fd;
    int des_fd;
    int rlen;
    int bytes;
    char buffer[buffer_size];

    signal(SIGINT, signal_handler);
    src_fd = open("src_text", O_RDONLY);
    if (src_fd == -1)
        error(1, 0, "error in opening the source-file\n");
    des_fd = open("des_txt", O_WRONLY);
    while (1) {
        rlen = read(src_fd, buffer, sizeof(buffer));
        if (rlen == -1)
            error(1, 0, "error in reading the file\n");
        if (rlen == 0)
            break;
        write_buf(des_fd, buffer, rlen, &bytes);
        if (flag == 1)
            printf("The number of bytes copied is :%d\n", bytes);
        flag = 0;
    }
}
```

Do not call printf from the signal handler. It is not signal safe. man sigaction for details.
write_buf is somewhat convoluted. while (rlen > 0) seems more straightforward.

Also, it is forced to write the entire buffer. It means that your program only pays attention to the Ctrl-C in between of writes. You may get more crispy resolution by testing wlen < rlen and inspecting errno; if write was interrupted, it would be EINTR.

void function with an in-out parameter (bytes in your case) is strange to say the least. The void function is not supposed to return anything, and in-out parameters are generally unclean. Just return bytes.
error() is a GNU extension and should not be used in programs intended to be portable. In any case, the pass errno as a second parameter. The user is very interested what exactly was wrong.
If the program was not interrupted, it doesn't print number of bytes copied. Looks like a bug (or a very dubious design decision) to me.


It's OK to use max(), reimplementing it yourself won't save time, especially since the Python version is possibly faster if it's written in C. It's possible to be more concise and clearer though: max(hori + verti + dia + diarev).
You should use a list of list to represent a matrix, not a list of dictionaries. As cat_baxter points out, d = [map(int, row.split()) for row in open('20x20.txt').read().splitlines()] is enough to populate d. However if you're not familiar with list comprehensions and map, it's OK to use normal loops.
Python doesn't really have constants, but a convention is to do VERTI = "verti" and then use VERTI everywher, denoting that it is a constant ("verti" is not a good name, by the way, "vertical" is better. Use code completion.)
try: ... except: ... is bad practice, you need to catch specific exceptions (KeyError in this case). And you need to understand why those errors are thrown! This could be a bug in your code.


Script to remove .vb files from a directory I wrote a script to remove .vb code files when there are corresponding .cs files in a certain directory structure.  But I felt like there were some extra statements that I had to put in there that didn't feel natural.  Is there a better way to do this check and then action?

Specifically, having to do the foreach at the end didn't seem right to me.  I also didn't know if there was a more PowerShell-y way to do the change extension and test-path.

ls . -include *.vb -recurse
    | ? { $cs = [System.IO.Path]::ChangeExtension($_.FullName, ".cs"); Test-Path $cs }
    | % { rm $_ -force }

You could combine expression vs. command mode in PowerShell, process only files (!$_.PSIsContainer) and use regex instead of ChangeExtension:

gci -include *.vb -Recurse |
    ? { (!$_.PSIsContainer) -and (Test-Path ($_.FullName -replace "\.vb$", ".cs") } |
    % { rm $_ -force }


Convert a List of graph edges to a Map of neighboring nodes What would be best way achieving this? Is it possible to use Immutable map?

import scala.collection.mutable.Map

/* Convert List of Edges to mapping Node -> List of Nodes */
def create_graph(edges: Array[Array[Int]]): Map[Int, List[Int]]  = {
    val graph = Map[Int, List[Int]]();
    for (i <- 0 until edges.length) {
        val a = edges(i)(0)
        val b = edges(i)(1)
        if(graph contains a ) graph(a) = b::graph(a)
        else graph(a) = List(b)
    }
    return graph
}

It is possible to achieve the same result with a scala.collection.immutable.Map:

def create_graph2(edges: Array[Array[Int]]): Map[Int, List[Int]]  = {
       // group the tuples so that a -> Array((a, b1), (a, b2), (a, b3)...)
  edges.groupBy(edge => edge(0))
       // convert the array to target list of Ints, removing duplicates
       .map{ case(key, edges) => (key, edges.map(_(1)).toSet.toList)}
}

Using the following test case:

val test1 = Array(Array(1, 2), Array(2, 3), Array(3, 4), Array(1, 5))
val result1 = create_graph(test1)
val result2 = create_graph2(test1)

The results are:

result1 = Map(2 -> List(3), 1 -> List(5, 2), 3 -> List(4))
result2 = Map(2 -> List(3), 1 -> List(2, 5), 3 -> List(4))


Improving a JQuery Promise "Chain" I have a little chain of JQuery promises.  My problem is at each stage I want to notify my progress to the user, keep them in the loop (Perhaps using .notify somehow?)

What I've eneded up with is this bizarre mess of callbacks and promises.  It works but I'm quite certain there is a neater, more logical way to do this.

both fetchSomeData() and Parser() return a promise

    var parseData = function(json)
    {
        showMessage("Updating your data...");
        return new Parser(json);
    };

    var onParseDone = function()
    {
        hideMessage();
        updateView();
    };

    showMessage("Fetching a bit of data...");
    fetchSomeData().pipe(parseData).done(onParseDone);

Surely this is possible. Only the fetch and parse functions would need to call notify with the respective message on the Deferreds they return. The code then could look like this:

fetchSomeData().pipe(parser).progress(showMessage).done(hideMessage, updateView);


Count occurrences of date-time in large CSV My input file is a CSV of varying size, up to around 10GB. The file has several fields, however I'm only interested in the third column, a date-time field. The date-times are in UTC timezone, and they are not ordered.

Example of values in column:

2017-08-03T10:22:31.000Z
2017-08-03T10:22:32.000Z
2017-08-03T10:22:37.000Z
2017-08-03T10:22:40.000Z
...

My desired output is a CSV which counts the number of date-times by hour, which have been converted to a specified user timezone.

example output file:

2017-08-01 05:00:00,230
2017-08-01 06:00:00,3340
2017-08-01 07:00:00,4362
2017-08-01 08:00:00,1747
2017-08-01 09:00:00,5676
2017-08-01 10:00:00,6955
...

Below is the working code I have written:

dates = {}
with open(myInputFile) as file:
    reader = csv.reader(file)
    for row in reader:
        row_date = datetime.datetime.strptime(row[2],"%Y-%m-%dT%H:%M:%S.%fZ").replace(tzinfo=tz.gettz('UTC'))
        row_date = row_date.astimezone(tz.gettz(newTimezone)).replace(tzinfo=None)
        row_date = row_date.strftime("%Y-%m-%d %H:00:00") #Strips minute and below info

        if row_date in dates:
            dates[row_date] += 1
        else:  #If date not in dictionary add entry
            dates[row_date] = 1

rows = zip([k for k in sorted(dates)],[dates[k] for k in sorted(dates)]) #changes dict to date ordered zip
with open('WaypointCount.csv'),'w', newline='') as output: #saves to csv
    wr = csv.writer(output)
    for row in rows:
        wr.writerow(row)

Basically I use the csv module to read each entry line by line.

I convert the string into a datetime, and set it's timezone to UTC.

I then convert the datetime to the new Timezone. The reason I do that at this step rather than later is because some timezones are offset from UTC by 30 minutes, which would mess up my hourly grouping.

I then convert it back into a string, stripping away the minute, second and microsecond information, and add a count to my dictionary.

Once I have looped through every row I convert my dictionary into two lists ordered by the Date key, zip them together, and write to a new csv.

I feel like I've probably converted between too many datatypes. How can I improve this code so it follows best practices, and runs optimally?

Syntax

Your code does not have valid Python syntax.
The first closing parentheses in this line should not be there:

with open('WaypointCount.csv'),'w', newline='') as output: #saves to csv

Improvements

Use if __name__ == '__main__'

If you run script code, enclose it within an if block checking for __main__:

if __name__ == '__main__':
    <your_code_here>

LBYL vs. default dicts

The check statement

if row_date in dates:
    dates[row_date] += 1
else:  #If date not in dictionary add entry
    dates[row_date] = 1

can be optimzed using a collections.defaultdict:

from collections import defaultdict

dates = defaultdict(int)

dates[row_date] += 1

The defaultdict will automatically initialize a non-existant key's value with 0, by calling the provided factory int without parameters iff the requested key does not exist.

Dict key and value sorting

The line

rows = zip([k for k in sorted(dates)],[dates[k] for k in sorted(dates)])

seems quite cumbersome to me.
You iterate and sort the dict twice and then zip the keys and values.
I suggest changing that to:

with open('WaypointCount.csv','w', newline='') as output: #saves to csv
    wr = csv.writer(output)
    for row in sorted(dates.items()):
        wr.writerow(row)

Use fitting datatypes

In the line

row_date = row_date.strftime("%Y-%m-%d %H:00:00") #Strips minute and below info

You already convert the datetime back to a str although you later will sort by it.
While this should have the same beaviour iff the datetime string is in ISO format, you may want to store the actual datetime value instead of the string representation and later convert it into the desired output format.

with open('WaypointCount.csv','w', newline='') as output: #saves to csv
    wr = csv.writer(output)
    for timestamp, occurences in sorted(dict.items()):
        timestamp_str = timestamp.strftime("%Y-%m-%d %H:00:00")
        wr.writerow((timestamp_str, occurences))

PEP8

Last, but not least, consider PEP8.
Espacially your variable naming and line length.


Quadratic function solver + testing I wrote a simple quadratic function solver with unit tests. Can anyone check if this is okay?

Quadratic function class

public class QuadraticFunction {
    private Integer a,b,c;

    public QuadraticFunction(Integer a, Integer b, Integer c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public Result calculate() throws NullPointerException{
        if(calculateDelta()>0){
          return new DeltaBiggerThanZero(calculateX1(),calculateX2());
        }else if(calculateDelta() == 0){
            return new DeltaEqualsZero(calculateOneRoot());
        }else{
            return new NoSolution();
        }
    }

    private Double calculateDelta(){
        return Math.pow(b,2) - 4*a*c;
    }

    private Double rootOfDelta(){
        return Math.sqrt(calculateDelta());
    }

    private Double calculateX1(){
        return (-b-rootOfDelta())/2*a;
    }

    private Double calculateX2(){
        return (-b+rootOfDelta())/2*a;
    }

    private Double calculateOneRoot(){
        return Double.valueOf((-b)/2*a);
    }

Result class example

final public class DeltaBiggerThanZero implements Result{

    private Double x1, x2;

    public Double getX1() {
        return x1;
    }

    public Double getX2() {
        return x2;
    }

    public DeltaBiggerThanZero(Double x1, Double x2) {
        this.x1 = x1;
        this.x2 = x2;
    }
    public String printSimpleResult() {
        return "Rozwiązaniem równiania jest: x1="+x1+" x2="+x2;
    }
}

This is a test:

public class QuadraticFunctionTest {
    @Test
    public void testIfEquationHasTwoResults() throws Exception {
        QuadraticFunction quadraticFunction = new QuadraticFunction(1,-4,-5);
        Result result = new DeltaBiggerThanZero(-1.0,5.0);

        assertEquals(quadraticFunction.calculate().getX1(), result.getX1());
        assertEquals(quadraticFunction.calculate().getX2(), result.getX2());
    }

    @Test
    public void testIfEquationHasOneResult(){
        QuadraticFunction quadraticFunction = new QuadraticFunction(1,6,9);
        Result result = new DeltaEqualsZero(-3.0);

        assertEquals(result.getX1(), quadraticFunction.calculate().getX1());
    }

    @Test
    public void testIfTheresNoSolution() throws Exception {
        QuadraticFunction quadraticFunction = new QuadraticFunction(1,2,5);
        Result result = new NoSolution();
        assertEquals(quadraticFunction.calculate().getX1(), null);
        assertEquals(quadraticFunction.calculate().getX2(), null);
    }
}

Looks good, nice and clean. Nitpicks:

no need to introduce a method called printSimpleResult when you can simply override toString (either way, the "print" part is a lie as the method returns the string, doesn't print it)
missing @Override annotation in DeltaBiggerThanZero
naming a variable "result" in the tests is a bit ambiguous, especially since it seems that you don't know what order of params assertEquals takes in (it's "expected, actual", for the record)
why artificially limit input parameters a, b, c to integers only?
what's the purpose of throws NullPointerException in calculate's signature? I see no way in which this exception could be triggered, and you're not required to declare unchecked exceptions (and it's a matter of discussion whether you should)

You didn't include the code for NoSolution but apparently it's an implementation that returns null for most of the fields. This begs for using Java 8's Optional. Returning null and hoping the clients will know and remember how to interpret it is a bad idea.

On the other hand, creating a class hierarchy for different kinds of solutions is rather problematic for the client (arguably this is not the scenario that calls for inheritance, which should be used judiciously). Since calculate() returns an abstract Result, the client still needs to do "sniffing" on the returned object to figure out how many (if any) results there were. They could to this either by checking via instanceof or trying to see what x1 and x2 are (if x2 is null it must be the "delta-is-zero" case, if both x1 and x2 are null it must be the "delta-is-negative" case with no solutions). Neither of these options is elegant or clean. A better solution could be to return a List<Double> that has either zero, one or two elements in it. A simple implementation that would allow you to get rid of the Result type and its subclasses could be:

public List<Double> calculate() {
    Double delta = calculateDelta();
    if (delta > 0) {
        return new ArrayList<Double>(Arrays.asList(new Double[] { calculateX1(), calculateX2() }));
    } else if (delta == 0) {
        return new ArrayList<Double>(Arrays.asList(new Double[] { calculateOneRoot() }));
    } else {
        return Collections.<Double> emptyList();
    }
}

A List has a nice default implementation of toString() so the client calling the code above could just do:

QuadraticFunction qf = new QuadraticFunction(1, -4, -5);
List<Double> results = qf.calculate();
System.out.println("Rozwiązania to: " + results);

To get the output of:

  Rozwiązania to: [-1.0, 5.0]


Ruby & OOP: FizzBuzz Game I would like a more elegant solution for this problem, I think the FizzBuzzArrayBuilder class is not used properly. Also can those if statements be removed somehow?

Any suggestion on how to improve this by still using OOP is welcome.

Problem:

Given the array [1, 2, 3, 4, ... 100], print all the elements as follows:

if the element can be divided by 3 print: Fizz
if the element can be divided by 5 print: Buzz
if the element can be divided by both 3 and 5 print: FizzBuzz
else print the number

Output:
1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz ...

Solution:

class Fizz
  def output
    puts 'Fizz'
  end
end

class Buzz
  def output
    puts 'Buzz'
  end
end

class FizzBuzz
  def output
    puts 'FizzBuzz'
  end
end

class Element
  def initialize(value)
    @value = value
  end

  def output
    puts @value
  end
end

class FizzBuzzArrayBuilder
  def initialize(array)
    @array = array
  end

  def build
    result = []
    @array.each do |e|
      if e % 15 == 0
        result << FizzBuzz.new
      elsif e % 3 == 0
        result << Fizz.new
      elsif e % 5 == 0
        result << Buzz.new
      else
        result << Element.new(e)
      end
    end
    result
  end
end

class Counter
  def initialize(array)
    @fizz_buzz_array = FizzBuzzArrayBuilder.new(array).build
  end

  def output_array
    @fizz_buzz_array.map(&:output)
  end
end

array = (1..100).to_a
Counter.new(array).output_array

Wrong Objects

You've made objects, but you haven't really made the right ones.  Your Fizz, Buzz, FizzBuzz, and Element classes are really just wrappers for a string, which is already a class.

Object oriented programming is not always the best solution for a problem.  FizzBuzz itself is frankly very trivial and almost any object based approach is a needlessly complicated solution.  With that said, perhaps we can redefine the problem to make it a better fit for an object oriented solution.

New problem definition

Consider this modified problem: As input you will receive a list.  Each row (a rule) will have one or more numbers (divisors) and a text substitution.  After parsing the list, for every number 1..100 you will either print the number or a substitution for the number.  For each rule, if a number is divisible by all of the divisors, you will use the substitution.  In the event of a tie, use the substitution from the rule with the most divisors.  If there is still a ties use the substitution for the rule with the smallest individual divisor.  For example, given "3 6 apple" and "2 9 banana" and "18 candle", they all tie for an input of 18, but "2 9 banana" has the smallest divisor, 2.

Example Input:
3 fizz
5 buzz
3 5 fizzbuzz
3 6 apple
2 9 banana
18 candle
2 3 4 dog

New Classes

Now there is opportunity for new classes, perhaps Parser that reads the rules/substitutions, Rule which contains a list of divisors, the substitution, and perhaps it supports the comparison operation <=> so that the rules can automatically resolve ties.  There could also be an Engine class for iterating through 1..100 and applying the rules.  There are a couple of different ways you could define the classes or even the problem here. In general though, OO solutions to trivial problems aren't a good fit.


Validation default value I want to check if all items of a list meet a set of criteria:

bool AreValid(list<string> vals)
{
   bool allValid=true;

   foreach(string val in vals)
   {
       if(!condition1)
          ...
          allValid=false;
       else if(!condition2)
          ...
          allValid=false;
   }

   return allValid;

}

The reason I can't use LINQ All() is that for each failed condition I'm doing some job.

is it safe to set allValid as true by default?

It's safe. A few things to consider:

When the list is empty you might want to return false.
Consider using an abstract data type (instead of string) which stores your data (the string) and move the validation logic to there.
As Jeff Vanzella already suggested, you can return false immediately when you now that a value is not valid. It's faster and easier to read:

bool AreValid(list<string> vals)
{
   foreach(string val in vals)
   {
       if(!condition1)
          ...
          return false;
       if(!condition2)
          ...
          return false;
   }

   return true;

}

Note that you don't need the else keyword anymore.


Rendering data into a graph The output result is perfect to what I wanted, but takes a tad bit too long to pull data then render into a graph.  Is there a better way to rewrite this code to speed up the process?

CASE "TestGrid":
    $SnapArrayResult = array();
    $PlayArrayResult = array('A','B','C','D');
    echo "
\n";
    echo "
Data on Alliance
\n";

    $SnapResult = $db-> query("SELECT snap FROM scSVR WHERE hex(alliance) IN (hex('A'),hex('B'),hex('C'),hex('D')) GROUP BY snap ORDER BY snap ASC");
    while ($SnapRow = $db-> fetch_assoc($SnapResult)){ $SnapArrayResult[] = $SnapRow['snap']; }

    echo "

	\n";
    foreach($SnapArrayResult as $SAR){ echo "".DTConvS($SAR)."	\n"; }
    echo "

\n";
    echo "
";
    foreach($PlayArrayResult as $PAR){
        echo "
".$PAR."	";
        foreach($SnapArrayResult as $SAR){
            $PlayerResult = $db-> query("SELECT COALESCE(count(*),0) as pCnt FROM scSVR WHERE hex(alliance) = hex('".$PAR."') AND snap = ".$SAR);
            $PlayerRow = $db-> fetch_assoc($PlayerResult);
            echo "".$PlayerRow['pCnt']."	\n";
        }
        echo "
";
    }
    echo "

";
    break;

Look at the code below. I haven't tried it yet, but the idea is avoid iterating query that will take a long time. So, I just use one query.

CASE "TestGrid":
        $SnapArrayResult = array();
        $PlayArrayResult = array('A','B','C','D');
        echo "
\n";
        echo "
Data on Alliance
\n";
        echo "

	\n";
        $SnapResult = $db-> query("SELECT snap,COALESCE(count(*),0) as pCnt,hex(alliance) as alliance FROM scSVR WHERE hex(alliance) IN (hex('A'),hex('B'),hex('C'),hex('D')) GROUP BY snap,alliance ORDER BY snap ASC");
        $changeSnap = null;
        $PlayerRow = array();
        while ($SnapRow = $db-> fetch_assoc($SnapResult))
        {
            if($changeSnap!=$SnapRow['snap'])
            {
                $SnapArrayResult[] = $SnapRow['snap'];
                $changeSnap=$SnapRow['snap'];
                $PlayerRow[$changeSnap] = array();
                echo "".DTConvS($SAR)."	\n";
            }
            $PlayerRow[$changeSnap][$SnapRow['alliance']] = $SnapRow['pCnt'];
        }

        echo "

\n";
        echo "
";
        foreach($PlayArrayResult as $PAR){
            echo "
".$PAR."	";
            foreach($SnapArrayResult as $SAR){
                echo "".$PlayerRow[$SAR][$PAR]."	\n";
            }
            echo "
";
        }
        echo "

";
        break;


Returning an existing data frame with four new columns I'm trying to implement a function that given a data frame returns the same data frame with four columns added. These new four columns are: for each row, I get the maximum element and its index and put them as two new columns. I do the same with the second maximum element.  I don't care if they are repeated.

add_2max <- function(x)
{
  max1 = max(x, na.rm=TRUE)
  indmax1 = which.max(x)
  y=x[-c(indmax1)]
  max2 = max(y, na.rm=TRUE)
  indmax2 = which(x==max2)
  indmax2 = ifelse(max1==max2, indmax2[2], indmax2[1])
  x=c(x, max1, max2, indmax1, indmax2)
  return (x)
}

add_2max_df <- function(DF)
{
  NewDF=t(apply(DF, 1, add_2max))
  return(NewDF)
}

I'm sure this code can be improved.  What do you recommend in order to do that? Is it fast enough?

Here's a faster way:

add_2maxFaster <- function(x)
{
  imax1 <- which.max(x)
  imax2 <- which.max(x[-imax1])
  if (imax2 >= imax1) imax2 <- imax2 + 1L
  c(x, x[imax1], x[imax2], imax1, imax2)
}

set.seed(42)
m <- matrix(runif(1e6), 1e4)

# Compare speed:
system.time( a1<-apply(m, 1, add_2max) )        # 0.38 secs
system.time( a2<-apply(m, 1, add_2maxFaster) )  # 0.15 secs

# ...And compare results
all.equal(a1,a2) # TRUE


Huge Fibonacci modulo m optimization in Python 3 I'm doing some an Algorithm Design online course as a way of learning algorithms and Python as well. One of these challenges requires that I write code for finding a "Huge Fibonacci Number Modulo m". The code works, but for some inputs (such as 99999999999999999 100000), it exceeds the allocated time limit. However, I can't see a way of improving performance.

Here is the problem description:

  Problem Introduction

  The Fibonacci numbers are defined as follows:

  F(0) = 0, F(1) = 1, and F(i) = F(i−1) + F(i−2) for i ≥ 2.

  Problem Description

  Task: Given two integers n and m, output F(n) mod m (that is, the remainder of F(n) when divided by m).

  Input Format: The input consists of two integers n and m given on the same line (separated by a space).

  Constraints: 1 ≤ n ≤ 10^18 , 2 ≤ m ≤ 10^5 .

  Output Format: Output F(n) mod m

  Time Limits:C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3
  sec. Memory Limit: 512 Mb

  Sample:

Input:

    281621358815590 30524

Output:

    11963

Here is the code:

#!/usr/bin/python3

from sys import stdin

def get_fibonacci_huge(n, m):
    fibonacciNumbers = [0, 1, 1]
    pisanoNumbers = [0, 1, 1]
    pisanoPeriod = 3

    for i in range(2, n):
        if pisanoNumbers[i - 1] == 0 and pisanoNumbers[i] == 1:
            pisanoPeriod = i - 1
            break;

        nextFibonacci = fibonacciNumbers[i - 1] + fibonacciNumbers[i];

        fibonacciNumbers.append(nextFibonacci)
        pisanoNumbers.append(nextFibonacci % m)
    else:
        pisanoPeriod = None # If we exhausted all values up to n, then the pisano period could not be determined.

    if pisanoPeriod is None:
        return pisanoNumbers[n]
    else:
        return pisanoNumbers[n % pisanoPeriod]

if __name__ == '__main__':
    dataEntry = stdin.readline()
    n, m = map(int, dataEntry.split())
    print(get_fibonacci_huge(n, m))

For an input of 99999999999999999 100000, it takes around 5.10 seconds, and the maximum allowed time is 5.00 seconds.

As a complete Python and algorithms newbie, any input is appreciated.

Fibonacci numbers grow exponentially. It means that the number of bits representing them grows linearly, and so does the complexity of computing nextFibonacci. It results in the overall quadratic complexity of your loop.

Good news is that you don't need to compute Fibonacci numbers at all. You only need to compute Pisano numbers. They obey the similar recurrence,

    p[n+1] = (p[n] + p[n-1]) % m

and by virtue of the modulo they never exceed m. A complexity of an individual addition stays constant, and the overall complexity becomes linear.

(Tiny additional: \$ (a + b)\ \textrm{mod}\ c\equiv a\ \textrm{mod}\ c\ + a\ \textrm{mod}\ c\$)


Ascending Order Algorithm I wrote a simple function to sort an array of integers in ascending order. Here is the code -

void sort(int* begin, int* end) {

    int* it = begin;

    int num1 = 0, num2 = 0;

    while (it != end) {

        num1 = *it;
        num2 = *(it + 1);

        if (num1 > num2) {

            *it = num2;
            *(it + 1) = num1;
            it = begin;

         } else {

             it++;

         }

    }

}

Is there any way I can improve this code?

Reading and writing off the end!

When it points to the last element (one before end), you read one-past-the-end, and then potentially write to it. This is undefined behavior. You need to make sure that you stop before then. One way to ensure this is to iterate from begin+1 to end, and compare the element with the one before it.

Logic

The typical way to write bubble sort is to have a loop that goes the full list, and set a flag if you swapped anything, and loop until you didn't. This will make it easier to understand what's going on - rather than having your loop next step set in two separate places, which is error prone.

Unnecessary variables

You don't need num1 or num2. Simply rely on std::swap:

if (*(it-1) > *it) {
    std::swap(*(it-1), *it);
    swapped = true;
}

Or you could implement such a thing yourself:

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

Either way, avoiding unnecessary variables is a plus.

Spacing

Don't add so many blank statements between lines. Taking up too much vertical space makes it harder to read.

Proposed implementation

The following addresses all of my points:

void sort2(int* begin, int* end) {
    bool swapped = true;
    while (swapped) {
        swapped = false;
        for (int *it = begin+1; it != end; ++it) {
            if (*(it - 1) > *it) {
                std::swap(*(it - 1), *it);
                swapped = true;
            }
        }
    }
}

Minor optimization

Rewriting the way I did it above allows for a minor optimization. Every time through the for loop, we know that we just put the "largest" number at the end. It "bubbled" up! At that point, we don't need to do anything else with it, so we can decrement the end pointer:

while (swapped) {
    swapped = false;
    for (int *it = begin+1; it != end; ++it) {
       ...
    }

    --end; // <==
}

Future work

Bubble sort is \$O(n^2)\$. It gets the job done, but it's... not great. A strictly better algorithm to start with is insertion sort, which is still \$O(n^2)\$. From there, you can look at merge sort and quicksort, both \$O(n \lg n)\$.

Also consider what you'd need to do to be able to support (a) arbitrary types, not just ints and (b) in arbitrary order, not just increasing.


Shell POSIX OpenSSL file decryption script Tonight, I tried to write a Bash OpenSSL file decryption script. Encryption script will follow in highly similar manner, so I think it's not necessary now.

Let's suppose we have an encrypted large file using:

openssl enc -aes-256-cbc -salt -in somefile -out somefile.enc

You correctly noticed I always add .enc to the file name.

The meaning of the script is:

take one, and only one, argument as a file
ask user for password
decrypt that file with openssl with a shown progress
save it without the .enc extension, or if it didn't have that extension, give it .dec extension
not to overwrite existing files

Though I wrote it with maximum effort, a review is more than welcome.

The script follows:

#!/bin/bash

if [ "$#" -ne 1 ] || [ ! -f "$1" ]
then
    echo "A single existing file needs to be given as an argument. Exiting."
else
    input_filename="$1"
    filepath=$(dirname "$1")
    filename_extracted_from_path=$(basename "$1")
    filename_without_enc_extension="${filename_extracted_from_path%.enc}"

    if [[ "$filename_extracted_from_path" == "$filename_without_enc_extension" ]]
    then
        output_filename="$filepath/$filename_extracted_from_path".dec
    else
        output_filename="$filepath/$filename_without_enc_extension"
    fi

    if [ -f "$output_filename" ]
    then
        echo "Destination file exists. Exiting."
    else
        pv "$input_filename" | openssl enc -aes-256-cbc -d -salt -out "$output_filename"
    fi
fi

EDIT1:

I decided to put the script on GitHub (when done), therefore it must be POSIX compliant, so I have made minor changes.
I found out, the script lacks destination directory writable check, so I integrated it.
Also, it now checks if it is run as root (or with sudo).

But the structure remains and new version of the script follows:

#!/bin/sh

if [ "$#" -ne 1 ] || [ ! -f "$1" ]
then
    echo "A single existing file needs to be given as an argument. Exiting."
else
    input_filename="$1"
    filepath=$(dirname "$1")
    filename_extracted_from_path=$(basename "$1")
    filename_without_enc_extension="${filename_extracted_from_path%.enc}"

    if [ "$filename_extracted_from_path" = "$filename_without_enc_extension" ]
    then
        output_filename="$filepath/$filename_extracted_from_path".dec
    else
        output_filename="$filepath/$filename_without_enc_extension"
    fi

    if [ -f "$output_filename" ]
    then
        echo "Destination file exists. Exiting."
    else
        if [ ! -w "$filepath" ] && [ "$(id -u)" -ne 0 ]
        then
            echo "Destination directory is not writable. Exiting."
        else
            pv --wait "$input_filename" | openssl enc -aes-256-cbc -d -salt -out "$output_filename"
        fi
    fi
fi

Uploaded on GitHub: https://git.io/fxslm

Get rid of unnecessary nested and combined ifs

While here it goes to no extreme, it's advisable to check for errors first, and to do that one by one - if possible, which is exactly this case.

Do some extra checks

Only in case of 0 arguments, the script should output usage message.
This script does not support multiple arguments, so if given more than 1, inform the user.
The script only checks for existence of the file, but what if it's not readable by the user.

Use tput for handling text colors instead of escape sequences

Those escape sequences are non-portable and the fact it works in dash does not mean it would do the job in Cygwin for instance; tput is clearly more portable.

bold=$(tput bold)
red=$(tput setaf 1)
yellow=$(tput setaf 3)
nocolor=$(tput sgr0)

bold_red=${bold}${red}
bold_yellow=${bold}${yellow}

Write a function for handling errors

print_error_and_exit()
{
    echo "${bold_red}$1 Exit code = $2.${nocolor}"
    exit "$2"
}

Shorten test commands, since there are only if ... then

[ "$#" -eq 0 ] \
&& print_error_and_exit "One argument needs to be given. Both relative, and absolute file paths are supported." 1

Declare and initialize variables just before they're used

The following declarations:

input_filename="$1"
filepath=$(dirname "$1")
filename_extracted_from_path=$(basename "$1")
filename_without_enc_extension="${filename_extracted_from_path%.enc}"

Should be split in order not to declare / initialize variables the script may not use in event of a failure.

Use exit return codes

The script should give the system feedback for example for automated processing. And be sure to use different exit codes in every failure event.

Root account check is unnecessary

The following test:

[ "$(id -u)" -ne 0 ]

Does not serve the intended purpose and should be omitted.

Comment code, that is not self-explanatory

The following code:

if [ "$filename_extracted_from_path" = "$filename_without_enc_extension" ]
then
    output_filename="$filepath/$filename_extracted_from_path".dec
else
    output_filename="$filepath/$filename_without_enc_extension"
fi

May be a little unclear, so a short comment is advisable.

The script should give feedback to the user too

The core code:

pv --wait "$input_filename" | openssl enc -aes-256-cbc -d -salt -out "$output_filename"

Should say something like:

Decryption failed / successful.

Clean after failed decryption

In the event of failed decryption, there is an empty output file present.

(Optional) The decryption status message could use some colors

In the end, if the decryption fails, it shows something similar to:

bad decrypt
140673166227096:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:evp_enc.c:529:

Though it might suffice to say the above mentioned message, some users might prefer it in color.

Based on the above code, I would re-write it as follows:

#!/bin/sh

bold=$(tput bold)
red=$(tput setaf 1)
yellow=$(tput setaf 3)
nocolor=$(tput sgr0)

bold_red=${bold}${red}
bold_yellow=${bold}${yellow}

print_error_and_exit()
{
    echo "${bold_red}$1 Exit code = $2.${nocolor}"
    exit "$2"
}

[ "$#" -eq 0 ] \
&& print_error_and_exit "One argument needs to be given. Both relative, and absolute file paths are supported." 1

[ "$#" -gt 1 ] \
&& print_error_and_exit "Multiple arguments are not supported." 2

[ ! -f "$1" ] \
&& print_error_and_exit "The given argument is not an existing file." 3

input_filename="$1"

[ ! -r "$input_filename" ] \
&& print_error_and_exit "Input file is not readable by you." 4

input_filepath=$(dirname "$input_filename")

[ ! -w "$input_filepath" ] \
&& print_error_and_exit "Destination directory is not writable by you." 5

filename_extracted_from_path=$(basename "$input_filename")
filename_without_enc_extension="${filename_extracted_from_path%.enc}"

if [ "$filename_extracted_from_path" = "$filename_without_enc_extension" ]
then
    # the file has a different than .enc extension or no extension at all
    # what we do now, is that we append .dec extention to the file name
    output_filename="$input_filepath/$filename_extracted_from_path".dec
else
    # the file has the .enc extension
    # what we do now, is that we use the file name without .enc extension
    output_filename="$input_filepath/$filename_without_enc_extension"
fi

[ -f "$output_filename" ] \
&& print_error_and_exit "Destination file exists." 6

if ! pv -W "$input_filename" | openssl enc -aes-256-cbc -md sha256 -salt -out "$output_filename" -d 2> /dev/null
then
    [ -f "$output_filename" ] && rm "$output_filename"

    print_error_and_exit "Decryption failed." 7
else
    echo "${bold_yellow}Decryption successful.${nocolor}"

    exit 0
fi


find the index of subarray from a parent array Are there any improvements that can be made on the below code, especially in terms of memory and time? I feel bad about setting found = false in every iteration of the for loop.

public static void main(String[] args) {
    System.out.println(getSubArrayIndex(new int[]{2,3,4,2,2,3,5,5,4,2,3,4}, new int[]{2,3,4}));
}

static int getSubArrayIndex(int[] parentArr, int[] subArr) {
    boolean found = false;
    for (int i = 0; i <= parentArr.length - subArr.length; i++) {
        if(parentArr[i] == subArr[0]){
            for(int j = 1 ; j < subArr.length ; j++){
                if(!(parentArr[i+j] == subArr[j])){
                    found = false;
                    break;
                }
                else{
                    found = true;
                }
            }
        }
        if(found)
            return i;
    }
    return -1;
}

Advice 1

Your method is a little bit overdone. Consider this:

public static int getSubArrayIndexV2(int[] haystack, int[] needle) {
    outer:
    for (int i = 0; i <= haystack.length - needle.length; ++i) {
        for (int j = 0; j < needle.length; ++j) {
            if (haystack[i + j] != needle[j]) {
                continue outer;
            }
        }

        return i;
    }

    return -1;
}

Advice 2

This is actually pattern matching in "strings" consisting of integers instead of characters. As such, you can use, say, Knuth-Morris-Pratt algorithm that runs in time \$\mathcal{O}(n + m)\$ (where \$n\$ is the length of the integer array to search in, and \$m\$ is the length of the integer array to search for). The complexity of your solution is worst-case \$\mathcal{O}(nm)\$.

(Take a look at this program.)


Get all recipes from database with the cheapest ingredients I have the following query which tries to get all the cheapest products linked to my recipes and it takes 10 seconds to return from the database:

SELECT PRODUCTOS.id, PRODUCTOS.titulo, CONCAT (INGREDIENTES.titulo," ", CONCAT(RECETA_INGREDIENTE.cantidad * $pers, "", PRODUCTOS.medida)) as ingrediente , precio, precio_medio , RECETA_INGREDIENTE.cantidad as cantidad_receta, PRODUCTOS.Volumen as cantidad_producto, PRODUCTOS.imagen, RECETA_INGREDIENTE.id_ingrediente as idingrediente, PRODUCTOS.precio_medio as precio_medio, PRODUCTOS.medida
FROM PRODUCTOS
INNER JOIN INGREDIENTES ON INGREDIENTES.id = PRODUCTOS.ingrediente
INNER JOIN RECETA_INGREDIENTE ON INGREDIENTES.id = RECETA_INGREDIENTE.id_ingrediente
WHERE precio = (SELECT MIN(precio) FROM PRODUCTOS AS f WHERE f.ingrediente = PRODUCTOS.ingrediente) AND RECETA_INGREDIENTE.id_receta = $id;

I found the SELECT MIN(precio)... within the WHERE case is making the query take too long. I found out the price is a float column which I believe is not the most suitable data type for a price. This is taking products with the cheapest price in the PRODUCTS table and I was thinking about replace the FROM PRODUCTS part with something more like this:

select *,MIN(precio) from PRODUCTOS where ingrediente is not null group by titulo;

But I still couldn't get it working. Any advice?

The output is all the ingredients for a particular recipe with the cheapest products.

Table definition:

/*Table structure for table `INGREDIENTES` */

DROP TABLE IF EXISTS `INGREDIENTES`;

CREATE TABLE `INGREDIENTES` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `titulo` varchar(255) DEFAULT NULL,
  `slug` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=65 DEFAULT CHARSET=utf8;

/*Table structure for table `PRODUCTOS` */

DROP TABLE IF EXISTS `PRODUCTOS`;

CREATE TABLE `PRODUCTOS` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `titulo` varchar(255) DEFAULT NULL,
  `categoria` varchar(255) DEFAULT NULL,
  `precio` float DEFAULT NULL,
  `precio_medio` float DEFAULT NULL,
  `volumen` int(5) DEFAULT '0',
  `promo` varchar(255) DEFAULT NULL,
  `url` varchar(255) DEFAULT NULL,
  `ingrediente` int(11) DEFAULT NULL,
  `ref` int(11) DEFAULT NULL,
  `imagen` varchar(255) DEFAULT NULL,
  `medida` varchar(4) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=321 DEFAULT CHARSET=utf8;

/*Table structure for table `RECETAS` */

DROP TABLE IF EXISTS `RECETAS`;

CREATE TABLE `RECETAS` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `titulo` varchar(255) DEFAULT NULL,
  `cal` varchar(50) DEFAULT NULL,
  `descripcion` text,
  `imagen` varchar(255) DEFAULT NULL,
  `orden` int(11) DEFAULT NULL,
  `visible` tinyint(1) DEFAULT '0',
  `TYPE` varchar(255) DEFAULT NULL,
  `id_tipo` int(1) DEFAULT NULL,
  `id_dificultad` int(1) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=16 DEFAULT CHARSET=utf8;

/*Table structure for table `RECETA_INGREDIENTE` */

DROP TABLE IF EXISTS `RECETA_INGREDIENTE`;

CREATE TABLE `RECETA_INGREDIENTE` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `id_ingrediente` int(11) DEFAULT NULL,
  `cantidad` int(11) DEFAULT NULL,
  `orden` int(11) DEFAULT NULL,
  `id_receta` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=75 DEFAULT CHARSET=utf8;

I found two issues after some investigation

The first is that my "precio" column is float and that a bad idea to store currencies. I turn this into a double data type by using the following command:

ALTER TABLE PRODUCTOS MODIFY COLUMN precio double;

The second issue is the way I use the subquery to get the cheapest product price in every single product. Instead, I've changed my PRODUCTS table inside of my FROM case to a  minified version. Basically, what I've done is get all the products with the cheapest price by ingredient and removes the need of use subqueries. Please, see the fixed version:

SELECT ...
FROM (
    SELECT * FROM PRODUCTOS AS P WHERE ingrediente is not null and P.precio = (
    select MIN(precio) from PRODUCTOS where P.ingrediente=PRODUCTOS.ingrediente group by PRODUCTOS.ingrediente LIMIT 1)
) AS PRODUCTOS
INNER JOIN INGREDIENTES ...

The result returned is exactly the same and I've moved from 1.8 seconds to 0.15 which I think is a great improvement.