Pseudo-random number generator & password generator I've started learning Rust and decided to implement something on my own from scratch. I've implemented a PRNG and I use it to generate random passwords.
Project tree:
|   .gitignore
|   Cargo.lock
|   Cargo.toml
|
+---src
|       main.rs
|       password.rs
|       xorshift.rs
|

main.rs :
use std::io;

mod xorshift;
mod password;

fn main() {

    let length : u32;

    loop{
        let mut pass_leng_str = String::new();

        println!("Enter the length of wannable password: ");

        io::stdin()
            .read_line(&mut pass_leng_str)
            .expect("Faild to read the line");

        let pass_leng_str = pass_leng_str.trim();

        match pass_leng_str.parse::<u32>(){
            Ok(i) => {
                length = i;
                break;
            },
            Err(..) => {
                println!("Not a valid integer!");
            },
        }
    }
    println!("Enter the characters you want to exclude: ");

    let mut exclude = String::new();

    io::stdin()
        .read_line(&mut exclude)
        .expect("Faild to read the line");

    let excluded : Vec<char> = exclude.chars().collect();

    println!("{}", password::rand_pass(length, excluded));

}

password.rs :
use super::xorshift;

pub static ASCII : [char; 69] = [
    'a', 'b', 'c', 'd', 'e',
    'f', 'g', 'h', 'i', 'j',
    'k', 'l', 'm', 'n', 'o',
    'p', 'q', 'r', 's', 't',
    'u', 'v', 'w', 'x', 'y',
    'z',
    'A', 'B', 'C', 'D', 'E',
    'F', 'G', 'H', 'I', 'J',
    'K', 'L', 'M', 'N', 'O',
    'P', 'Q', 'R', 'S', 'T',
    'U', 'V', 'W', 'X', 'Y',
    'Z',
    '1','2','3','4',
    '5','6','7','8',
    '9','0',
    '+','-','_','?','!','$','/',
];

pub fn rand_pass(pass_len : u32, excluded : Vec<char>)-> String{
    let mut  password = String::new();
    for _i in 0..pass_len{
        let c : char = loop{
            let c = ASCII[xorshift::get_rand(69) as usize];
            if !excluded.contains(&c){
                break c
            }
        };
        password.push(c);
    }

    password
}

xorshift.rs :
use std::time::UNIX_EPOCH;
use std::time::SystemTime;

pub fn get_rand(len : u128) -> u128{
    let now = SystemTime::now();
    let from_unix = now.duration_since(UNIX_EPOCH).expect("Congrats on time travel!");
    let seed = from_unix.as_nanos();
    let x = seed;
    let x = x ^ seed << 13;
    let x = x ^ x >>17;
    let x = x ^ x <<5;
    let x = x % len;
    x as u128
}

Welcome to Rust, and welcome to Code Review!
rustfmt & clippy
Always run cargo fmt and cargo clippy first.  cargo fmt
formats your code according to the official Rust Style Guide, and
cargo clippy detects common mistakes and provides feedback on
improving your code (none in this case).
main.rs
The biggest problem with the main function is its structure.
Logically, the job of main is to:

read the length of the password;

read the excluded characters; and

output the generated password.

You spent so much code on the first step that it is hard to recognize
at a glance without being familiar with input loops.  For readability,
it is preferable to extract all of this into a function:
fn input_length() -> usize {
    loop {
        eprintln!("Enter the length of password: ");

        let mut length = String::new();
        io::stdin()
            .read_line(&mut length)
            .expect("cannot read line");

        match length.trim().parse() {
            Ok(length) => return length,
            Err(_) => eprintln!("Error: invalid length\n"),
        }
    }
}

Lengths are usually represented by usize in Rust to avoid type
casts, instead of u32.
It is recommended to define variables as close to their usage as
possible.
Personally, I would change all occurrences of println! to
eprintln! expect the one that actually prints the password, so that
the program can be easily used in an automated script by reading
stdout.
Moving on, we see that there is no need to extract all characters in
exclude, a String, into excluded, a Vec<char> (the naming can
be improved, by the way).  A String encodes the characters in UTF-8,
which is variable-length, so ASCII characters take up only 1 byte
each, whereas a sequence of chars always stores each character as 4
bytes.  Moreover, UTF-8 is specially constructed so that searching
requires only a linear scan and no computation of character
boundaries, so there is no performance gain.
password.rs
It shouldn't be the job of the password module to expose a constant
array containing ASCII characters.  A better name for ASCII may be
ALLOWED_CHARS.
The function rand_pass will often be called with the password::
prefix, so it is not necessary to repeat this information.  I would
name it generate.
Since the function does not consume excluded, take a &[char], or
better, &str parameter.  See Why is it discouraged to accept a
reference to a String (&String), Vec (&Vec), or Box (&Box)
as a function argument?.
The function can be rewritten in a more logically straightforward
manner using iterators:
use std::iter;

pub fn generate(length: usize, excluded: &str) -> String {
    iter::repeat_with(generate_char)
        .filter(|c| !excluded.contains(&c))
        .take(length)
        .collect()
}

where generate_char is a function Fn() -> char that generates an
individual random character in the password, omitted for simplicity.
The intent is now clearer.
xorshift.rs
A better name for the module might be time_rng.
use declarations can be condensed:
use std::time::{SystemTime, UNIX_EPOCH};

A mutable variable is more readable to me here:
let mut x = seed;
x ^= (seed << 13);
x ^= (x >> 17);
x ^= (x << 5);
x % len

It is best to not count on the reader knowing the operator precedence
here.


Find array index with element equality in Python I was given this question during an interview. It is similar to binary search and I would like to ask for feedback for my solution.

  Array Index & Element Equality

  Given a sorted array arr of distinct integers, write a function
  indexEqualsValueSearch that returns the lowest index i for which
  arr[i] == i. Return -1 if there is no such index. Analyze the time and
  space complexities of your solution and explain its correctness.

  Examples:

  input: arr = [-8,0,2,5]
  output: 2 # since arr[2] == 2

  input: arr = [-1,0,3,6]
  output: -1 # since no index in arr satisfies
  arr[i] == i.

def index_equals_value_search(arr):
  left = 0
  right = len(arr) -1

  ind = 0
  output = -1

  while left <= right:
    ind = (left + right) // 2
    if arr[ind] - ind < 0:
      left = ind + 1
    elif arr[ind] == ind:
      output = ind
      break
    else:
      right = ind -1
  return output

Passing all of the basic tests

arr = [-8,0,2,5]
test1 = index_equals_value_search(arr)
arr2 = [-1,0,3,6]
test2 = index_equals_value_search(arr2)
print(test2) # return -1
arr3 = [0,1,2,3]
test3 = index_equals_value_search(arr3)
print(test3) # return 0
arr4 = [-6,-5,-4,-1,1,3,5,7]
test4 = index_equals_value_search(arr4)
print(test4) #return 7

Better tests

Before anything, let's improve the test suite so that we can feel more confident updating the code.

At the moment, the tests:

rely on meaningless values printed on standard output which have to be compared to values in the comments - we'll see quickly why this is something to avoid
have somes values "untested": value for test1 is not printed
have variables with names that does not convey much meaning (testXXX)

Let's see how we can improve this. We could:

get rid of the testXXX variables
rename all arrYYY variables as arr
use assert to checking everything is working properly. If we want to do things properly, we could use a unit test framework such as unittest.

At this stage, we have:

def test_index_equals_value_search():
    arr = [-8,0,2,5]
    assert index_equals_value_search(arr) == 2
    arr = [-1,0,3,6]
    assert index_equals_value_search(arr) == -1
    arr = [0,1,2,3]
    assert index_equals_value_search(arr) == 0
    arr = [-6,-5,-4,-1,1,3,5,7]
    assert index_equals_value_search(arr) == 7

which gives:

Traceback (most recent call last):
  File "review212877.py", line 32, in <module>
    test_index_equals_value_search()
  File "review212877.py", line 28, in test_index_equals_value_search
    assert index_equals_value_search(arr) == 0
AssertionError

My job pretty much stops at this point but I'll give additional comments anyway.

You see how important my first comment was.
This error also shows something which is missing in your code: documentation. Indeed, the value returned is correct if we stricly refer to the function name. However, there should be a piece of docstring mentionning we want "the lowest index".
Algorithms relying on indices and in particular binary search are very easy to get wrong and are not always easy to test. However, a function doing the same thing using linear search is very easy to write. If I were you, I'd write such a function and use it to write a pseudo-oracle:

def index_equals_value_search_linear(arr):
    for i, x in enumerate(arr):
        if i == x:
            return i
    return -1

More comments

Style

Python has a style guide called PEP 8 which is worth reading and trying to apply.

Among other things, it says:

  Use 4 spaces per indentation level.


Combining data from two AJAX requests I have two jQuery Ajax callbacks in succession, to fetch two sets of data from two different URLs, before combining them.

    $.ajax({
      type: "GET",
      url: numeratorUrl,
      error: function(request, status, error) {
        _this.showErrorMessage(request.status, error);
      },
      success: function(data) {
        parse(data,
             {columns: true },
             function(err, output){
                _this.globalOptions.data.numeratorData = output;
                $.ajax({
                  type: "GET",
                  url: denominatorUrl,
                  error: function(request, status, error) {
                    _this.showErrorMessage(request.status, error);
                  },
                  success: function(data) {
                    parse(data,
                         {columns: true },
                         function(err, newOutput){
                            _this.globalOptions.data.denominatorData = newOutput;
                            // combine the two datasets here
                         }
                    );
                  }
                });
             }
        );
      }
    });

It works fine, but I think it's unwieldy and hard to read. Is there a way to make it cleaner?

If the ajax operation is simple, you can use the shorthand $.get instead. I usually use $.ajax when I alter default AJAX settings.

In addition, your code looks unwieldy because you are encountering what they call "callback pyramid". The way to avoid that is use Promises. And you're in luck, jQuery AJAX operations return promises.

Here's a non-pyramid version.

$.get(numeratorUrl).then(function(data) {
  // When get resolves
  var parseDeferred = $.Deferred();
  parse(data, { columns: true }, function(err, output) {
    if (err) parseDeferred.reject(err);
    else parseDeferred.resolve(output);
  });
  return parseDeferred.promise()
}).then(function(output) {
  // When parse resolves
  _this.globalOptions.data.numeratorData = output;
  return $.get(denominatorUrl)
}).then(function(data) {
  // When second get resolves
  var parseDeferred = $.Deferred();
  parse(data, { columns: true }, function(err, output) {
    if (err) parseDeferred.reject(err);
    else parseDeferred.resolve(output);
  });
  return parseDeferred.promise()
}).then(function(newOutput) {
  // When second parse resolves
  _this.globalOptions.data.denominatorData = newOutput;
}, function(error) {
  // Catch-all for all errors
  _this.showErrorMessage(null, error)
});

Would have been better if parse returned a promise or a value (if it was synchronous). If so, then the code would look like this:

$.get(numeratorUrl).then(function(data) {
  // when get resolves
  return parse(data, { columns: true })
}).then(function(output) {
  // when parse resolves
  _this.globalOptions.data.numeratorData = output;
  return $.get(denominatorUrl)
}).then(function(data) {
  // when second get resolves
  return parse(data, { columns: true });
}).then(function(newOutput) {
  // when second parse resolves
  _this.globalOptions.data.denominatorData = newOutput;
}, function(error) {
  // catch-all for all errors
  _this.showErrorMessage(null, error)
});

Here's the same code, explained:

$.get(numeratorUrl).then(function(data){
  // Listen for $.get response,

  // Unless parse returns a promise, we can use Deferreds to manually
  // create promises, resolve and reject. This is handy especially for
  // async operations that don't operate on promises.

  var parseDeferred = $.Deferred();
  parse(data, { columns: true }, function(err, output){
    if(err) parseDeferred.reject(err);
    else parseDeferred.resolve(output);
  });

  // We return the deferred as a promise, a read-only version of the deferred.
  // This means we lose the resolve and reject interface from the deferred.
  return parseDeferred.promise();

}).then(function(output){
  // Since we returned a promise from the last then, this callback now listens
  // to that promise instead of the $.get()'s promise.

  _this.globalOptions.data.numeratorData = output;

  // Now we do another AJAX call. We return it's value (which is a promise) which
  // means the next chained then listens to this promise instead of the one from
  // parse. Since $.get() returns a promise, we don't need to manually use Deferreds.
  return $.get(denominatorUrl);

}).then(function(data){

  // Use the same pattern as above
  var parseDeferred = $.Deferred();
  parse(data, { columns: true }, function(err, output){
    if(err) parseDeferred.reject(err);
    else parseDeferred.resolve(output);
  });
  return parseDeferred.promise();

}).then(function(newOutput){

  _this.globalOptions.data.denominatorData = newOutput;

}, function(error){
  // Now the nice thing about promises is that errors propagate the
  // same way resolved values propagate. Unless you return a new promise,
  // the succeeding thens will always resolve/reject with the value from
  // the latest resolved/reject promise.
  //
  // If the first $.get() failed, this will catch the error. If the
  // first succeeded, and the parse after it failed, this catches it.
  //
  // In jQuery, I believe their rejection resolves with 3 values,
  // the xhr object, text status and another status - which is not
  // now native promises work. So you might want to look after it.

  _this.showErrorMessage(null, error);
});


Odd divisor summation Given an integer, k, we define its odd divisor sum to be the sum of all k's odd divisors. For example, if k = 20, then the odd divisor sum would be 1 + 5 = 6. Similarly, if given an array of values, we can find the odd divisor sum of the array by summing the odd divisor sums for each element in the array.
For example, if array K = [3, 4, 20], the odd divisor sum of the array would be oddDivisorSum(3) + oddDivisorSum(4) + oddDivisorSum(20) = (1 + 3) + (1) + (1 + 5) = 11.

This code works, but it does not pass all the cases due to time. I wanted to see if there was a more efficient way to write this. I heard that memoization could work, but I am not sure show how to implement it.
numbers = [3,21,11,7]

def  count(numbers):
    total = 0
    for k in numbers:
        for i in range(1,k+1,2):
            if k % i == 0:
                total+=i
    return total

First I would suggest to separate the code into two functions: One which computes the sum of odd divisors of a single number, and another which adds the odd divisors of all numbers in a list. Also, use better function names, and add at least a simple doc comment:

def oddDivisorSum(n):
    """Return the sum of odd divisors of n."""
    # ... to do ...

def totalOddDivisorSum(numbers):
    """Return the sum of all odd divisors of all numbers."""
    return sum(oddDivisorSum(n) for n in numbers)

This makes the code more clear, better reusable, and makes it easier to add test cases.

To make the computation faster, two observations help:

If \$k\$  is a divisor of \$n\$, then \$\frac{n}{k}\$ is also a divisor of  \$n\$.

This is what Oscar also said, and it allows to restrict the search for divisors to the interval  \$1\dots \sqrt n\$. The "problem" is that \$k\$ and \$\frac{n}{k}\$ can have different oddity.
If \$ k \$ is an odd divisor of an even number \$n\$ then \$k\$  is also an odd divisor of \$\frac{n}{2}\$.

Therefore, we can remove all even factors of \$n\$ first, and then find odd divisors in the reduced (odd) number. This makes the code simpler (because all divisors are odd) and faster for even numbers (a smaller \$n\$ means less trial divisions):

def oddDivisorSum(n):
    """Return the sum of odd divisors of n."""
    while n % 2 == 0:
        n //= 2
    sum = 0
    for k in range(1, int(n ** .5) + 1, 2):
        if n % k == 0:
            sum += k
            if n // k != k:
                sum += n // k
    return sum


Find the smallest number greater than "n" with the same digit sum as "n" Here is my code:

def func(n):
    sum_digits_n = 0
    for i in str(n):
        sum_digits_n+=int(i)

    num = n+1

    while True:
        s = 0
        for i in str(num):
            s+=int(i)
        if s==sum_digits_n:
            return num
            break
        else:
            num += 1

It works for small to moderate sized n. But it takes forever to run with big values of n. How can I optimize it?

For example, let's check the run times for different sized inputs:

import time
inputs = [7,70,700,7000,70000,700000,7000000,70000000]
for i in inputs:
    t = time.time()
    ans = func(i)
    print('Input: {}. Ans: {}. Time taken: {}s\n'.format(i, ans, time.time()-t))

As you can see, even with a not-so-huge input as 70 million, the code takes ~1.5 mins to run.

You have to come up with a trickier algorithm here rather than doing a brute force approach.

Let's try to think about a couple of cases here.

123, its sum of digits is 6. If we decrease 3 by 1, then we'll have to increase 2 by 1 (as you're trying to get the least larger element) -> 132
1293, sum of digits is 15. If we decrement 3 and increment 2 (9 is already a maximum digit so we cannot increment it) then we'll get 1392. But is it really the least greater value? Well, no, 1329 is. So, what we should do it increment 2, substitute 9 with 3 and decrement 3 (as 2 was just incremented). 9 must go to the end to minimise the value as much as possible.
129993 - here we have a similar case as #2. The only difference is that the full 999 must go to the end -> 132999.
12920 - another interesting case. But again, find the first non-zero digit from the left, then if 9s are its immediate neighbours move them to  the end, decrement 2 and put 0 before it -> 13019.

Hopefully, based on examples above it's clear which steps have to be implemented (we move from right to left):

Find the rightmost digit that can be decremented. So, 0 cannot be such a digit as it's minimal already. If such digit doesn't exist then there's no solution. Decrement it.
Find the closest digit to the left of the digit from step 1 that can be incremented. So, 9 cannot be such a digit as it's maximum already. If there's no such digit then just prepend 0 to the start of the current number. Increment the digit.
Now, sort all the digits after the digit from step 2 in ascending order.
You have a solution now!

UPDATE

As a bonus, a quick implementation of the approach in Python. I'll leave it up to you to improve this solution (if possible :) )

def solve(n):
    size = len(n)

    trailing_zeros = list()
    first_nines = list()

    i = size - 1
    while i >= 0:
        if int(n[i]) != 0:
            break
        trailing_zeros.append(n[i])
        i -= 1

    if i < 0:
        print ("No solution!")
        return

    first_non_zero_digit = int(n[i])
    i -= 1
    while i >= 0:
        if int(n[i]) != 9:
            break
        first_nines.append(n[i])
        i -= 1

    if i < 0:
        remaining = '1'
    else:
        increased_digit = int(n[i]) + 1
        remaining = ''.join(n[:i]) + str(increased_digit)

    print(remaining + ''.join(trailing_zeros) + str(first_non_zero_digit - 1) + ''.join(first_nines))


Cryptographically secure token generation in C# Is the following a cryptographically secure way to generate a random token? Does it have any of the predictability risks that are theoretically associated with using a GUID as a token?

using System;
using System.Security.Cryptography;

namespace myApp
{
    class Program
    {
        static void Main(string[] args)
        {
            byte[] bytes = new byte[32];
            using (var rng = new RNGCryptoServiceProvider()) {
                rng.GetBytes(bytes);
            }

            string hexToken = BitConverter.ToString(bytes).Replace("-", "").ToLower();
            Console.WriteLine(hexToken);
        }
    }
}

What is there to say about it?

The code generates 32 random bytes, fed by a good Cryptographically Secure Random Number Generator, seeded by the operating system. Then it converts to just lowercase hexadecimals.

There is only a very small chance that a CryptographicException is thrown by the random number generator, but if it happens it is currently not caught.


A multi-threaded Producer Consumer with C++11 I am trying to learn concurrent programming in C++11. I tried to write code for a classic producer consumer concurrency problem. Would you please review and make any comments about it?

#include <iostream>
#include <thread>
#include <deque>
#include <mutex>
#include <chrono>
#include <condition_variable>

using std::deque;
std::mutex mu,cout_mu;
std::condition_variable cond;

class Buffer
{
public:
    void add(int num) {
        while (true) {
            std::unique_lock<std::mutex> locker(mu);
            cond.wait(locker, [this](){return buffer_.size() < size_;});
            buffer_.push_back(num);
            locker.unlock();
            cond.notify_all();
            return;
        }
    }
    int remove() {
        while (true)
        {
            std::unique_lock<std::mutex> locker(mu);
            cond.wait(locker, [this](){return buffer_.size() > 0;});
            int back = buffer_.back();
            buffer_.pop_back();
            locker.unlock();
            cond.notify_all();
            return back;
        }
    }
    Buffer() {}
private:
    deque<int> buffer_;
    const unsigned int size_ = 10;
};

class Producer
{
public:
    Producer(Buffer* buffer)
    {
        this->buffer_ = buffer;
    }
    void run() {
        while (true) {
            int num = std::rand() % 100;
            buffer_->add(num);
            cout_mu.lock();
            std::cout << "Produced: " << num << std::endl;
            std::this_thread::sleep_for(std::chrono::milliseconds(50));
            cout_mu.unlock();
        }
    }
private:
    Buffer *buffer_;
};

class Consumer
{
public:
    Consumer(Buffer* buffer)
    {
        this->buffer_ = buffer;
    }
    void run() {
        while (true) {
            int num = buffer_->remove();
            cout_mu.lock();
            std::cout << "Consumed: " << num << std::endl;
            std::this_thread::sleep_for(std::chrono::milliseconds(50));
            cout_mu.unlock();
        }
    }
private:
    Buffer *buffer_;
};

int main() {
    Buffer b;
    Producer p(&b);
    Consumer c(&b);

    std::thread producer_thread(&Producer::run, &p);
    std::thread consumer_thread(&Consumer::run, &c);

    producer_thread.join();
    consumer_thread.join();
    getchar();
    return 0;
}

Prefer Reference over Pointer

Since the producer and consumer must have a buffer you should pass it by reference (rather than pointer). This also makes sure there is no confusion over ownership of the buffer (the owner of a pointer is responsible for deleting it). By using a RAW pointer you can not tell the owner but by using a reference you are explicitly stating that you are not passing ownership.

class Producer
{
    Buffer&  buffer_;
public:
    Producer(Buffer& buffer)
        : buffer_(buffer)
    {}

Prefer to avoid this->

When you use this-> it means you have scoping issues with your variables (which is a code smell for bad design). Use accurate variable names so that there is no confusion on where the variables belongs.

Member variables over globals.

Looks like your encapsulation of the mu and cond is wrong.

std::mutex mu,cout_mu;

Because they are global, you use a single mutex/condition for all buffer objects. This looks like a design flaw. It seems like the mutex/condition belongs to the class so that you are just locking the buffer you are manipulating (so you can use multiple buffers in the same application).

Sleeping inside lock

        cout_mu.lock();
        std::cout << "Produced: " << num << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
        cout_mu.unlock();

@Morwenn already suggested using scoped lock to make sure the mutex were correctly locked and unlocked. But I would also move the sleep outside the lock. This causes the current thread to stall but the other thread can not continue as the lock is still held while it is sleeping.

        {
            std::unique_lock<std::mutex> locker(cout_mu);
            std::cout << "Produced: " << num << std::endl;
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(50));

Prefer '\n' over std::endl

std::cout << "Produced: " << num << std::endl;

The difference between the two is a flush. Usually you do not want to manually flush (the stream have good flushing techniques built in). So it is usually best to let the streams flush themselves when appropriate.

In answer to comments:

class Buffer
{
public:
    void add(int num) {
        while (true) {
            std::unique_lock<std::mutex> locker(mu);
            cond.wait(locker, [this](){return buffer_.size() < size_;});
            buffer_.push_back(num);
            locker.unlock();
            cond.notify_all();
            return;
        }
    }
    int remove() {
        while (true)
        {
            std::unique_lock<std::mutex> locker(mu);
            cond.wait(locker, [this](){return buffer_.size() > 0;});
            int back = buffer_.back();
            buffer_.pop_back();
            locker.unlock();
            cond.notify_all();
            return back;
        }
    }
    Buffer() {}
private:
   // Add them as member variables here
    std::mutex mu;
    std::condition_variable cond;

   // Your normal variables here
    deque<int> buffer_;
    const unsigned int size_ = 10;
};


Code in patched Cygwin for calculating path to command interpreter I'm working on a fork of Cygwin for native Windows development.

In this commit, I'm trying to improve the security of code that spawns cmd.exe, used by functions like system, popen.

What I would like to focus on is this:

static const char *cmd_exe_path = NULL;

static void init_cmd_exe_path(void)
{
  char sysdir[NT_MAX_PATH];
  char cmdname[] = "cmd.exe";
  unsigned int nchars;

  if ((nchars = GetSystemDirectoryA(sysdir, sizeof sysdir)) < sizeof sysdir) {
    unsigned int total = nchars + 1 + sizeof cmdname + 1;
    char *path = static_cast<char *>(cmalloc_abort(HEAP_STR, total));
    snprintf(path, total, "%s\\%s", sysdir, cmdname);
    cmd_exe_path = path;
  }
}

const char *get_cmd_exe_path()
{
  static pthread_once_t cmd_exe_once = PTHREAD_ONCE_INIT;
  pthread_once (&cmd_exe_once, init_cmd_exe_path);
  return cmd_exe_path;
}

The idea here is to avoid relying on a hard-coded path like C:\Windows\System32\cmd.exe, as well as to avoid the COMSPEC environment variable which could be commandeered by an attacker. Comment about anything are welcome: API usage, bugs, security concerns, correct use of Cygwin internals (I have no idea whether HEAP_STR is the best choice in cmalloc_abort).

Oops, I see I used (void), out of habit, on the static function, even though this is C++.

You're allocating too much memory:

unsigned int total = nchars + 1 + sizeof cmdname + 1;

You only need 1 terminating null at the end of the string.  This is already accounted for in the size of cmdname (since you declare it as a string initialized []).  You can simply allocate:

unsigned int total = nchars + 1 + sizeof cmdname;

Or, if you add the "\" onto cmdname you could do:

char cmdname[] = "\\cmd.exe";
unsigned int total = nchars + sizeof cmdname;


Traversing List of Integers and ending on the last index which should be 0 I have a method that checks if a List is solvable. Solvable in this context means 2 things:

The last index of the list is a 0.
Starting from the first index, each value indicates how many position you should go back or forth in the List. After walking the indexes you should end at the last index.

public class ListSolver {

  public boolean isSolvable(List<Integer> list) {
    if (list == null) {
      throw new IllegalArgumentException("List is null");
    }

    int listSize = list.size();
    int lastIndex = listSize - 1;
    int currentIndexValue;
    for (int i = 0, loopCounter = 0; i < listSize; i = i + currentIndexValue, loopCounter++) {
      try {
        currentIndexValue = list.get(i);
      } catch (IndexOutOfBoundsException e) {
        return false;
      }

      // if traversed to last index and last index is 0
      if (i == lastIndex && currentIndexValue == 0) {
        return true;
      }

      // if infinite loop
      if (loopCounter > listSize) {
        return false;
      }
    }

    return false;
  }

}

public class ListSolverTest {

  private ListSolver listSolver = new ListSolver();

  @Test(expected = IllegalArgumentException.class)
  public void isSolvableGivenNullExpectIllegalArgumentException() {
    listSolver.isSolvable(null);
  }

  @Test
  public void isSolvableGivenListContainingZeroAndZeroExpectFalse() {
    boolean isSolvable = listSolver.isSolvable(Arrays.asList(0, 0));

    assertFalse(isSolvable);
  }

  @Test
  public void isSolvableGivenListContainingOneAndNegOneExpectFalse() {
    boolean isSolvable = listSolver.isSolvable(Arrays.asList(1, -1));

    assertFalse(isSolvable);
  }

  @Test
  public void isSolvableGivenListContainingZeroExpectTrue() {
    boolean isSolvable = listSolver.isSolvable(Collections.singletonList(0));

    assertTrue(isSolvable);
  }

  @Test
  public void isSolvableGivenListContainingOneAndZeroExpectTrue() {
    boolean isSolvable = listSolver.isSolvable(Arrays.asList(1, 0));

    assertTrue(isSolvable);
  }

  @Test
  public void isSolvableGivenListContainingNegOneExpectFalse() {
    boolean isSolvable = listSolver.isSolvable(Collections.singletonList(-1));

    assertFalse(isSolvable);
  }

}

The method was written using TDD, but I'm stuck now.

  How  can I refactor and make it more readable without creating new methods that feel contrived?

This function relies on no object state, so I would make it static.

You don't need both listSize and lastIndex.  To reduce clutter, I would keep just lastIndex.

currentIndexValue is too cumbersome a name, in my opinion.  "Current" is superfluous, especially when there is no "previous" or "next" involved.  "Index" just adds confusion.  So, I'd simply call it value.

The for loop is trying to do too much.  Considering that currentIndexValue is defined elsewhere, you can't understand how the loop behaves just by looking at the loop header.  So, I would just make it count iterations.

If currentIndexValue is 0, but i is not lastIndex, then i is never going to move.  You might as well return false immediately in that case.

It would be better to avoid triggering IndexOutOfBoundsException when i is negative.

public static boolean isSolvable(List<Integer> list) {
    if (list == null) {
        throw new IllegalArgumentException("List is null");
    }

    int lastIndex = list.size() - 1;
    int i = 0;
    for (int loopCounter = 1; loopCounter <= lastIndex; loopCounter++) {
        if (i < 0 || i > lastIndex) {
            return false;
        }
        int value = list.get(i);
        if (value == 0) {
            return i == lastIndex;
        }
        i += value;
    }

    return false;
}


Euler problem c++ / std::library usage Euler problems (projecteuler.net) often invites to quick and dirty solutions.

While hurrying through Problem 32 I found myself in want of the std:: toolkit. Not sure what it is though.

The problem description is included in the first comment.

I would really appreciate any suggestions as for the usage of the tools provided by standard c++ (11 if need be, lambdas might make it more succinct/elegant).

/*
 * File:   main.cpp
 * Author: cpt_giraffe
 *
 *

 * We shall say that an n-digit number is pandigital if it makes use of all the
 * digits 1 to n exactly once; for example,
 * the 5-digit number, 15234, is 1 through 5 pandigital.

 * The product 7254 is unusual, as the identity, 39 × 186 = 7254,
 * containing multiplicand, multiplier, and product is 1 through 9 pandigital.

 * Find the sum of all products whose multiplicand/multiplier/product
 * identity can be written as a 1 through 9 pandigital.

 * HINT: Some products can be obtained in more than one way
 * so be sure to only include it once in your sum.

 * Created on November 27, 2013, 9:41 PM
 */

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <numeric>
#include <sstream>

using namespace std;

// store the products, a set is ideal because of the HINT:
set<unsigned> products;

/**
 * Insert to products if string arguments is a proper product
 */
void insert_if_product(string factor1, string factor2, string product) {
    stringstream values(factor1 + " " + factor2 + " " + product);

    // is this a valid product.  (Most cases says no)
    unsigned f1, f2, p;
    values >> f1 >> f2 >> p;
    if (f1 * f2 == p) {
        products.insert(p);
    }

}

/**
 * magnitudes needs to add up: I'm checking
 * 9 digits total
 * m1 * m3 = m5
 * m1 * m4 = m4
 * m2 * m3 = m4
 * Is this all?
 *
 * @param check this permutation
 */
void check_products(string perm) {
    // all permutations are coming from perm, so no need to perm stuff here.
    string factor1 = perm.substr(0, 1);
    string factor2 = perm.substr(1, 3);
    string product = perm.substr(4, 5);

    insert_if_product(factor1, factor2, product);

    factor1 = perm.substr(0, 1);
    factor2 = perm.substr(1, 4);
    product = perm.substr(5, 4);

    insert_if_product(factor1, factor2, product);

    factor1 = perm.substr(0, 2);
    factor2 = perm.substr(2, 3);
    product = perm.substr(5, 4);

    insert_if_product(factor1, factor2, product);

}

int main(int argc, char** argv) {
    string s = "123456789";
    do {
        check_products(s);

    } while (next_permutation(s.begin(), s.end()));

    // Test case
    if (products.find(7254) != products.end()) {
        cout << "found 7254" << endl;
    } else {
        cout << "did not find 7254" << endl;
    }
    unsigned sum = 0;

    sum = accumulate(products.begin(), products.end(), 0);
    cout << "Sum:" << sum << endl;
    return 0;
}

Your conversions are... pretty WTF :)

void insert_if_product(string const& factor1, string const& factor2, string const& product) {
    auto p = std::stoul(product);
    if (std::stoul(factor1, nullptr, 10) * std::stoul(factor2, nullptr, 10) == p) {
        products.insert(p);
    }
}

I mean why use an intermediate stream? Why, if you're using a stream, build it using string concatenation? Also, why pass in copies of read-only strings?!
avoid unnecesary allocations:

string factor1 = perm.substr(0, 1);
string factor2 = perm.substr(1, 3);
string product = perm.substr(4, 5);

is gonna do a lot of allocations. Probably more than you'd think. At least, reuse factor1,factor2 and product capacities? (My sample below makes them static)

  Edit Squeezing a few more drops out:

avoiding strings in more places avoids the temps from perm.substr(). Now I just directly assign by indices:

    factor1.assign(perm.begin()+0, perm.begin()+1);
    factor2.assign(perm.begin()+1, perm.begin()+4);
    product.assign(perm.begin()+4, perm.begin()+9);

using unordered_set seems to shave off milliseconds on average :)

Quick performance comparison (g++ -std=c++11 -march=native -O3`) shows the time taken goes down from ~1.036s to ~0.116s.

So, roughly 8.9x speed effectively.

Full code:

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <sstream>

// store the products, a set is ideal because of the HINT:
std::unordered_set<unsigned> products;

/**
 * Insert to products if string arguments is a proper product
 */
void insert_if_product(std::string const& factor1, std::string const& factor2, std::string const& product) {
    auto p = std::stoul(product);
    if (std::stoul(factor1, nullptr, 10) * std::stoul(factor2, nullptr, 10) == p) {
        products.insert(p);
    }
}

/**
 * magnitudes needs to add up: I'm checking
 * 9 digits total
 * m1 * m3 = m5
 * m1 * m4 = m4
 * m2 * m3 = m4
 * Is this all?
 *
 * @param check this permutation
 */

void check_products(std::string const& perm)
{
    static std::string factor1, factor2, product;
    // all permutations are coming from perm, so no need to perm stuff here.
    factor1.assign(perm.begin()+0, perm.begin()+1);
    factor2.assign(perm.begin()+1, perm.begin()+4);
    product.assign(perm.begin()+4, perm.begin()+9);

    insert_if_product(factor1, factor2, product);

//  factor1.assign(perm.begin()+0, perm.begin()+1);
    factor2.assign(perm.begin()+1, perm.begin()+5);
    product.assign(perm.begin()+5, perm.begin()+9);

    insert_if_product(factor1, factor2, product);

    factor1.assign(perm.begin()+0, perm.begin()+2);
    factor2.assign(perm.begin()+2, perm.begin()+5);
//  product.assign(perm.begin()+5, perm.begin()+9);

    insert_if_product(factor1, factor2, product);
}

int main() {
    std::string s = "123456789";

    do {
        check_products(s);
    } while(std::next_permutation(std::begin(s), std::end(s)));

    std::cout << "Sum:" << std::accumulate(products.begin(), products.end(), 0u) << "\n";
}


Waiting for game server connection public boolean connectedOnGameServer = false;
public final Object conGameServerMonitor = new Object();

public void connectedToGameServer() {
    synchronized (conGameServerMonitor) {
        if (connectedOnGameServer != false)
            throw new RuntimeException("Player connected twice");
        connectedOnGameServer = true;
        conGameServerMonitor.notifyAll();
    }
}

public void waitForGameServerConnection() {
    synchronized (conGameServerMonitor) {
        try {
            long startTime = System.currentTimeMillis();
            long waited = 0;
            while (!connectedOnGameServer && waited < GAMESERVER_CONNECT_TIMEOUT) {
                conGameServerMonitor.wait(GAMESERVER_CONNECT_TIMEOUT - waited);
                waited = System.currentTimeMillis() - startTime;
            }
            if (waited > GAMESERVER_CONNECT_TIMEOUT && connectedOnGameServer) {
                throw new RuntimeException("Client didn't connect to game server in time (" + GAMESERVER_CONNECT_TIMEOUT + " ms)");
            }
        } catch (InterruptedException e) {
            throw new RuntimeException("Interrupted while waiting for client to connect to game server", e);
        }
    }
}

What I need is:

Thread A calls waitForGameServerConnection
Thread B calls connectedToGameServer
Thread A continues

My code examples are excerpts. Don't copy/paste them, they are suggestions you can incorporate into your code.

if (waited > GAMESERVER_CONNECT_TIMEOUT && connectedOnGameServer)
{
   throw new RuntimeException("Client didn't connect to game server in time (" + GAMESERVER_CONNECT_TIMEOUT + " ms)");
}

can be reduced to:

if (!connectedOnServer) {
   throw new RuntimeException("Client didn't connect to game server in time (" + GAMESERVER_CONNECT_TIMEOUT + " ms)");
}

Now, you can handle this without an exception. Connections fail quite regularly, and it's easy to handle that.

public boolean waitForConnection() {
   synchronized (conGameServerMonitor) {
      // loop, guard
      return connectedOnGameServer? true : false;
   }
}

With this you can ask the player if he wants to try again, or wait a bit and try again, etc without having to catch an exception.
But what if B calls connectedToGameServer() after the wait completes?

boolean connectionInProgress;

public void connectedToGame() {
   synchronized (conGameServerMonitor) {
      if (connectionInProgress) {
         connectedOnGameServer = true;
         conGameServerMonitor.notifyAll();
      }
   }
}

public boolean waitForConnection() {
   synchronized (conGameServerMonitor) {
      connectionInProgress = true;
      // wait
      connectionInProgress = false;
      return connectedOnGameServer? true : false;
   }
}

You handle the wakeups and interuptions correctly. Kudos for the waited part - I thought "Useless!" for a second, but I forgot that a thread could wake anytime, and it's the thread's responsibility to be sure that it's conditions are fulfilled.


Finding unreferenced documents I have a database containing at least 2 collections datagroup and data.
Each data document have a reference to the _id of one of the datagroup documents.

I want to find all datagroup documents that have no data pointing to, the fastest as possible.

For this, I use a javascript mongo shell script.

I have these options for now (if you have one more, feel free to suggest):

  Notes:

  data.vid is the same value as datagroup._id (like external key, of kind ObjectId)
  There is a large number of data (~100,000,000) and datagroup (~20,000)

Option 1: (123s)

/* 0s since beginning (experimented) */
// get id of all datagroups used in data
let withData = db.data.find({})           // get all data
                      .map(d=>d.vid)      // to array of ObjectId
/* 1m40s since beginning (experimented) */

withData = Array.from(new Set(withData)); // remove duplicates in array
/* 1m52s since beginning (experimented) */

// find datagroup that ids not in ObjectId array
let withoutData = db.datagroup.find({_id: {$nin: withData}})
                              .map(dg=>dg._id);  // get their ids
/* 2m03s since beginning (experimented) */

Option 2: (59s)

/* 0s since beginning (experimented) */
// get id of all datagroups used in data
let withData = db.data.aggregate([
    {$project:{vid:1, _id:0}},       // keep only references to datagroups
    {$group:{_id:"$vid"}}            // remove duplicates
]).map(d=>d.vid.str);                // to array of ObjectId strings
/* 37s since beginning (experimented) */

let withoutData = db.datagroup.find({})      // find all datagroups
                              .map(dg=>dg._id) // get theys ids
                                             // compare with array of ids
                              .filter(vid => withData.indexOf(vid.str) < 0);
/* 59s since beginning (experimented) */

Option 3: (109s)

/* 0s since beginning (experimented) */
let withoutData = db.datagroup.aggregate([
    {$project:{_id:1}},       // keep only ids
    {$lookup:{
        from: "data",         // grouping data with datagroups
        localField: "_id",
        foreignField: "vid",
        as: "dgs"
    }},
    {$match:{dgs:[]}}        // keep only datagroups without data
]).map(dg=>dg._id);
/* 1ms49 since beginning (experimented) */

Do you think there is a better way than doing this, or should I use the option 2 because it's just the best way to do this kind of request ? (Or maybe you have ideas in order to speed up my options ?)

There is a better way, but this assume that you have an index on vid field (for example, {"vid": 1} ). If you don't, you can create one using db.data.ensureIndex({"vid": 1}). This can take several minutes to end.

The fastest solution (option 2) use $group after a $project  Here the $project stage only add overhead and does not speed up the $group stage, so we can get rid of it.

Currently, the $group operator can't take advantage of index, so it can be quite slow for such big dataset. A better solution would be to use distinct() instead

  Index Use

  When possible, db.collection.distinct() operations can use indexes.

so we can fetch withData array simply using this:

let withData = db.data.distinct("vid")

Then, the datagroup collection is filtered using map() and filter(). On really big array, this can be really expensive as javascript is quite slow. Instead, we can let mongodb do this operation with a simple query using $nin:

let withoutData = db.datagroup.distinct("_id", {"_id": {$nin: withData}})

As distinct() returns an array, we get directly the result in proper format, so we can avoid js mapping and filtering.

so the final script is:

let withData = db.data.distinct("vid")
let withoutData = db.datagroup.distinct("_id", {"_id": {$nin: withData}})

Some results

on my machine (ubuntu16.04) , with a similar dataset ( 100 000 000 docs in data, 20000 in datagroup)

New script runs in less than 5s :

time mongo test < newOption.js
0,06s user 0,00s system 1% cpu 3,534 total


Semaphore skipping additional threads In this example I've a refresh method that might be called by multiple threads. Requirements are:

refresh() method must be processed by only one thread at a time (blocking)
If already a thread is waiting, skip any new thread tries to acquire the lock to avoid processing multiple times

The refresh() method not returning anything nor changing state for the calling thread (fire and forget). So it is not necessary that it's called for every thread, instead, if multiple thread ask for a refresh it should only be executed once.

I'm trying to use a Semaphore with 1 permit for this task. If the semaphore has any queued threads I'm just returning, otherwise the thread will acquire the lock.

class Scratch {

    private final Semaphore refreshLock = new Semaphore(1);

    public void refresh() {
        System.out.println("call refresh()");
        try {
            synchronized (refreshLock) {
                if (refreshLock.hasQueuedThreads()) {
                    System.out.println("skip this thread ... " + Thread.currentThread().getId());
                    return; // don't put one more to the queue
                }
            }

            // wait till release of lock
            System.out.println("wait for lock release, queue: " + refreshLock.getQueueLength());
            refreshLock.acquire();

            try {
                System.out.println("process ... " + Thread.currentThread().getId());
                Thread.sleep(5000);
                System.out.println("### DONE");
            } finally {
                refreshLock.release();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    static class Task implements Runnable {
        private int taskId;
        private Scratch scratch;

        Task(int id, Scratch scratch) {
            this.taskId = id;
            this.scratch = scratch;
        }

        @Override
        public void run() {
            System.out.println("Task ID : " + this.taskId + " performed by " + Thread.currentThread().getName());
            try {
                Thread.sleep(300 + taskId * 10);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            scratch.refresh();
        }
    }

    public static void main(String[] args) {
        Scratch scratch = new Scratch();
        ExecutorService service = Executors.newFixedThreadPool(10);
        IntStream.range(0, 12).forEach(i -> service.submit(new Task(i, scratch)));
        service.shutdown();
    }
}

refresh() method must be processed by only one thread at a time ...

private final Semaphore refreshLock = new Semaphore(1);

A mutex is arguably a better synchronization object choice when you only need one thread at a time. So I would advise you to use a ReentrantLock instead, for instance.

synchronized (refreshLock) {
    if (refreshLock.hasQueuedThreads()) {
        System.out.println("skip this thread ... " + Thread.currentThread().getId());
        return; // don't put one more to the queue
    }
}

So in fact you are using not one but two synchronization objects, a semaphore and a monitor. The reason why you are doing this is because of your second requirement. However you can implement both of your requirements using only one synchronization object which would make your code simpler (hopefully).

Thread.sleep(5000);

No! I know you are doing this to emulate a long running operation. However long running operations should never execute within concurrent control, specially if it's running one at a time.

What this means effectively is that all threads calling refresh will be blocked by at least a whopping 5 seconds.

So obviously you have to implement your refresh method as a process that runs on the background. Meaning that you will be returning a Future that may complete at any given moment. For a thread that will do the process this moment will be when the process has finished, for all others this will be almost immediately.

This is the resulting implementation:

private final ReentrantLock refreshLock = new ReentrantLock();
private boolean hasRefreshed = false;
ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(2);

public Future refresh() {
    System.out.println("call refresh()");
    try {
        refreshLock.lock();
        if(hasRefreshed) {
            System.out.println("already refreshed");
            return executor.submit(() -> {});
        }

        hasRefreshed = true;
        return executor.submit(() -> {
            System.out.println("process ... " + Thread.currentThread().getId());
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("### DONE");
        });

    }finally {
        refreshLock.unlock();
    }
}

Ideally the synchronization logic would be implemented in a generic class that would be able to handle any use case.

You will also have to change your main a bit, so your program doesn't exit immediately.

IntStream.range(0, 12)
    .mapToObj(i -> service.submit(new Task(i, scratch)))
    .forEach(f -> {
        try {
            f.get();
        } catch (InterruptedException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (ExecutionException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        }
    });


Returning the title of a record I want to return the title of a record if one exists or the word 'invalid' if not:

    @ID int ,
    @Title nvarchar(50) output
    ...
if exists(select * from MyTable where ID=@ID)
    select @Title = (select Title from MyTable where ID=@ID);
else select @Title = 'invalid';

but I don't have a good feeling with this query.

Just do:

// Default value
select @Title = "invalid";

// If a record is found, replace "invalid" by the Title value
select @Title = Title from MyTable where ID=@ID;


Simple rwlock implementation in c++11 For answering this question of stackoverflow I have written the code
https://stackoverflow.com/questions/12033188/how-would-you-implement-your-own-reader-writer-lock-in-c11

Can someone review it - so that I can understand the possible problems in the code.

#include <condition_variable>
#include <iostream>
#include <shared_mutex>
#include <thread>
#include <unistd.h>
#define NR_THREADS 10
#include <mutex>

class MySharedLock {
 public:
  void read_lock() {
    std::unique_lock<std::mutex> lk(rw_mutex);
    std::cout << "\nReader Lock Writers are  " << writers << std::flush;
    if (writers != 0) {
      rw_cv.wait(lk, [this]() { return (this->writers == 0); });
    }
    readers++;
    lk.unlock();
  }

  void write_lock() {
    std::unique_lock<std::mutex> lk(rw_mutex);

    std::cout << "\nWriter Lock Writers are  " << writers << " Readers are "
              << readers << std::flush;
    if (readers == 0 && writers == 0) {
      std::cout << "\nWriter Lock Writers are  " << writers << std::flush;
    } else {
      rw_cv.wait(
          lk, [this]() { return (this->writers == 0 && this->readers == 0); });
    }
    writers++;
    lk.unlock();

  }

  void write_unlock() {
    std::lock_guard<std::mutex> lk(rw_mutex);
    writers--;
    rw_cv.notify_all();
  }

  void read_unlock() {
    std::lock_guard<std::mutex> lk(rw_mutex);
    if (readers == 1) {  // I am the last one.
      rw_cv.notify_all();
    }
    readers--;
  }

  explicit MySharedLock() {}

 private:
  std::mutex rw_mutex;
  std::condition_variable rw_cv;
  uintmax_t readers = {0}, writers = {0};
};

First, I suppose it would be cheating to just use a std::shared_mutex, right? :)

Second, it seems a little weird to declare uintmax_t writers for a variable that can only ever hold the value 0 or 1. But, on the other hand, the symmetry between readers and writers is kind of nice.

uintmax_t readers = {0}, writers = {0};

Strongly prefer to declare one variable per line. Also, I know some people like to write int i{0};, and of course the natural thing to write is int i = 0;, but your belt-and-suspenders approach is relatively unusual. Prefer

uintmax_t readers = 0;
uintmax_t writers = 0;  // or, bool has_writer = false;

explicit MySharedLock() {}

I am a big fan of this explicit zero-argument constructor! However, you should probably be in the habit of =defaulting things instead of {}.

if (writers != 0) {
  rw_cv.wait(lk, [this]() { return (this->writers == 0); });
}

Nit: A lambda that doesn't escape should generally just capture [&]. And you needn't write out this-> if you don't want to. So:

if (writers != 0) {
  rw_cv.wait(lk, [&]() { return (writers == 0); });
}

However, this could be more cleanly expressed as simply

while (writers != 0) {
  rw_cv.wait(lk);
}

lk.unlock();

unique_lock is an RAII type; it unlocks the controlled mutex automatically in its destructor. You don't need to (and therefore shouldn't) write .unlock explicitly in your code.

This implementation has the potential problem that it delegates all of the "queueing" logic to the mutex/cv themselves. It is possible that if customers show up as "reader, writer, reader, writer, reader, writer...", then the readers could starve out the writers, or even vice versa. The only way to fix this, AFAIK, is to implement some kind of a "queue" of waiters, so that each waiter knows exactly when it's at the head of the queue. (Imagine the ticketing system in a deli: "Now serving number 47!")

Inside reader_unlock, you have rw_cv.notify_all() — but I think that this could safely be changed to rw_cv.notify_one(). We know that nobody is waiting to read; therefore all waiters are writers; therefore at most one of them will actually be able to do any work right now; therefore it is sufficient to wake up just one of them.

(And of course by the time that guy wakes up, somebody new may have come in and stolen the lock. So even that guy might not get to do any work.)

However, what notify_all does do is transfer over all the waiters from waiting on the rw_cv to waiting on the rw_mutex. If std::mutex implements some kind of fair queueing system, this ensures that no writer will get starved for longer than one epoch-of-readers, because as soon as the epoch ends, all the writers will get woken up and transferred over to the mutex, so that their respective epochs-of-writers will happen bam bam bam one after the other.

Yeah, I think I've convinced myself that notify_all is actually the most effective thing to do here. But it probably deserves a code comment explaining why you think it's the right thing to do!

Finally, it's worth mentioning that the standard names for your methods (according to the standard SharedMutex concept) are:

read_lock     ->  lock_shared
read_unlock   ->  unlock_shared
write_lock    ->  lock
write_unlock  ->  unlock

There's no standard C++ name for the promotion of a held reader lock to a writer lock (which is deceptively tricky), nor for the downgrading of a held writer lock to a reader lock (which is trivial). You might think about whether you want to provide these operations, and if so, what the interface to them should be.


99 Haskell problems, problem 9: Pack function Today I started to tackle the 99 Haskell problems (http://www.haskell.org/haskellwiki/99_questions). I had to struggle with problem 9 which requires to Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists..

For example the input:

pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
["aaaa","b","cc","aa","d","eeee"]

I managed to create a pack function. However, my solution feels kind of
overcomplicated:

pack :: [[Char]] -> [[Char]]
pack xs = foldl (\acc x -> if not(null acc) && x `Data.List.isPrefixOf` (last acc)
                           then (init acc) ++ [(last acc) ++ x]
                           else acc ++ [x]) [] xs

A test of my pack function:

pack ["a", "a", "b", "b", "b", "c", "a", "a", "c"]
["aa","bbb","c","aa","c"]

Can you give me a code review?
How can I simplify it? What could I improve to make this function more idiomatic?

Let's improve the function step by step, focusin on readability as well as on the algorithm itself.

I believe the type of the function is not what it should be. We get a list of characters, and we should produce a list of lists:

pack1 :: [Char] -> [[Char]]
pack1 xs = foldl (\acc x -> if not(null acc) && [x] `isPrefixOf` (last acc)
                            then (init acc) ++ [(last acc) ++ [x]]
                            else acc ++ [[x]]) [] xs

The function doesn't require that we compare Chars. In such a case, it's better to make its type as generic as possible. Not only it makes it usage more generic, it also helps us ensure that we restrict to the specific problem of packing, not introducing anything particular about Chars. So the generalized type would be (Eq a) => [a] -> [[a]].
The major problem is that the function has O(n^2) time complexity. This is because calling last on a list, or appending someting to its end using ++ is O(n), and doing it n-times gets us to O(n^2). This is definitely something we'd like to avoid. The solution is easy: Instead of appending to the list, let's just prepend, and reverse it at the end. Since reverse is O(n), the result will be O(n) as well. Let's apply this idea to both the "big" list as well as its sublists:

pack2 :: (Eq a) => [a] -> [[a]]
pack2 xs = reverse . map reverse $
           foldl (\acc x -> if not (null acc) && [x] `isPrefixOf` (head acc)
                            then (x : (head acc)) : (tail acc)
                            else [x] : acc) [] xs

Most likely we could also omit map reverse, as the sublists always contain equal elements. This assumes that if two elements are equal, they're indistinguishable, which is usually a reasonable assumption. But I kept it there for completeness, and it doesn't affect the asymptotic complexity.
In Haskell it's customary to avoid if/then/else in favor of pattern matching. Not only it's often shorter, but it provides stronger guarantees and/or less required reasoning about the code. In the if condition, the reader needs to infer that using last or head on acc is allowed because we checked it's non-empty. If we instead factor out the inner function and use patternmatching,

pack3 :: (Eq a) => [a] -> [[a]]
pack3  = reverse . map reverse . foldl f []
  where f acc@(as@(a:_):ass) x | a == x     = (x : as) : ass
        f acc                x              = [x] : acc

we don't need to use any potentially dangerous functions such as head/tail and do any checking.

Here we also introduced another small improvement called η-conversion (eta). The idea is that \x -> g x is equivalent to g.
We'd like to avoid calling reverse.

The problem is that we're using foldl to produce the final list. By its nature, if we use foldl for converting lists, it reverses the order of the elements (or causes O(n^2) time complexity). Although we want to consume the list from left to right, it's more appropriate to use foldr here. (I'd say that the only reason to use foldl is if the result needs the whole list - for example when summing a list.)

Let's start with implementing map using foldr. (I'll hide the example, if you want to try it yourself. If you don't, just hover the mouse over it.)

   map' f = foldr (\x r -> f x : r) []

 The idea is to express how to process a single element, knowing how the rest of the list is processed.

Let's apply the same principle to pack:

pack4 :: (Eq a) => [a] -> [[a]]
pack4  = foldr f []
  where f x acc@(as@(a:_):ass) | a == x     = (x : as) : ass
        f x acc                             = [x] : acc

This isn't very different from the previous example. The main difference is that we (seemingly!) consume elements from the right, so we have no problem with reversing the order.
And still ... we can ask for more. The problem is that the function isn't lazy enough (even though we're using foldr). We'd like for example that

head $ pack4 ('a' : 'c' : repeat 'b')

produced "a", instead of looping forever - the required information is available. The reason for this is that we inspect the accumulator (by matching it with the pattern acc@(as@(a:_):ass) which is not irrefutable) at each iteration, which means that in order to produce a single element we first force the processing of the rest of the list.

Instead, we can create the result structure first to hold the current element without forcing the results of processing the rest of input list, so that this structure will be filled with more values only when/if it is so demanded:

pack5 :: (Eq a) => [a] -> [[a]]
pack5  = foldr f []
  where
    f x r = (x:u):w
            where
              (u,w) = case r of
                        []                 -> ([],[])
                        (g:gs) | head g==x -> (g ,gs)
                        gs                 -> ([],gs)

See also the source code for group, which is also implemented with the lazy behavior.


Improving readability of 3d math in Java Doing graphics in Java, I find myself writing lines like these regularly:

Vector3f b = mid.add( a.mult(yOffset + length / 2) ).add( up.cross(a).mult(xOffset) );

It gets even worse when I'm reusing objects.

Vector3f vTemp = VarPool.getVector3f();
Vector3f b = VarPool.getVector3f();

b.set(mid).addMutable( a.multAndStore(yOffset + length / 2, vTemp) ).addMutable( up.crossAndStore(a, vTemp).multMutable(xOffset) );

//...do some useful computation...

VarPool.recycle(vTemp, b);

I've tried coping using a combination of these two methods:

1. Place 'translations' in comments above dense lines

//i.e. Vector3f b = ( mid + a * (yOffset + length / 2) + (up X a) * xOffset );
//this calculates such and such
b.set(mid).addMutable( a.multAndStore(yOffset + length / 2, vTemp) ).addMutable( up.crossAndStore(a, vTemp).multMutable(xOffset) );

Disadvantages: Extra noise. 'Translation' comments can look like actual code that's been commented out. There's no getting around the real code being hard to read.

2. Break dense chains into more readable lines

b
    .set(mid)
    .addMutable( a.multAndStore(yOffset + length / 2, vTemp) )
    .addMutable( ( vTemp = up.crossAndStore(a, vTemp)
                    .multMutable(xOffset) ) );

Disadvantages: Some calculations don't chain up quite as nicely. When different return types are involved (e.g. matrices, quaternions, scalars), chaining is not always logical or possible.

Any other suggestions? Switching language is not really viable.

@DaveNewton Not necessarily, sometimes it's Groovy :-)

Advantage

code/syntax compatible with java.
Operator overrides allow you to write your code so it looks more like your comment i.e. operators rather than methods

Disadvantage

Groovy is slower than java (but this can be reduced with Groovy++)


Check if two strings are anagrams - HackerEarth You are given two strings. You have to check if the strings are permutations of each other and output "YES" or "NO" accordingly without quotes.

  Input:
  2 lines of input each containing a string. (a to z and 0 to 9)

  Output:
  A single line containing YES or NO.

  Constraints:
  String would not contain any spaces. size of string < 100

Here is my code:

#include <stdio.h>
#include <string.h>

char sort(int n, char str[])
{
    int i,j,swap;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(str[j]>str[j+1])
            {
                swap=str[j];
                str[j]=str[j+1];
                str[j+1]=swap;
            }
        }
    }
}
int main()
{
    char str1[100],str2[100];
    scanf("%s %s",&str1,&str2);
    sort(strlen(str1),str1);
    sort(strlen(str2),str2);
    if(strcmp(str1,str2)==0)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

How do I make this code as small (shorter code) as possible?

How do I make this code as small (shorter code) as possible?

You could change this:

if(strcmp(str1,str2)==0)
    printf("YES\n");
else
    printf("NO\n");

Like this, using the ternary operator and puts:

puts(strcmp(str1, str2) ? "NO" : "YES");

Technically,
you could also get rid of much of the whitespace and concatenate all instructions on a single line with semicolons.
But that's probably not what you really want.

If your aim is simplicity, then I think this is about as simple and short as it gets.

For readability, it would be better to add spaces around operators, for example like this:

    if (str[j] > str[j+1])
    {
        swap = str[j];
        str[j] = str[j+1];
        str[j+1] = swap;
    }

Some minor final remarks:

bubble sort is a slow sorting algorithm, but with words of max 100 letters, it's probably good enough
uppercase and lowercase letters will be treated differently, but since the treatment of letter case is unspecified, that might be fine too


Finding words that rhyme Preface

I was trying to review this question on the same topic, but in the end many points I wanted to make were excellently explained by @ferada so I felt that posting my code and explaining the concepts around such changes would just be repetition.

Instead I am questioning whether my approach is over-engineered considering the simplicity of this task.

Specification

I consider two words to rhyme if they share a certain number of phonemes at the end.

The division of the words into phonemes is already given from input and must only be read into program data.

Data is fetched from the internet on the first run and stored in a local file for successive runs to save internet traffic and execution time.

Code

import doctest
import os
import re
import requests
from collections import namedtuple

URL = "http://svn.code.sf.net/p/cmusphinx/code/trunk/cmudict/cmudict-0.7b"
LIBRARY = "library.txt"
PHONEMES_TO_MATCH = 3

ReadingData = namedtuple("ReadingData", ["word", "phonemes"])

def first_and_others(xs):
    """
    >>> first_and_others([1, 2, 3])
    (1, [2, 3])
    """
    return xs[0], xs[1:]

def format_data(raw_data):
    '''
    Transforms a list of lines of the format
      WORD [SPACE] PHONEME1 [SPACE] PHONEME2 [SPACE] PHONEME3 ...
    into a list of `ReadingData` classes for easier further processing.

    >>> format_data(["ZURCHER Z ER1 K ER0", "ZUREK Z UH1 R EH0 K"])
    [ReadingData(word='ZURCHER', phonemes=['Z', 'ER1', 'K', 'ER0']), ReadingData(word='ZUREK', phonemes=['Z', 'UH1', 'R', 'EH0', 'K'])]
    '''
    return [ReadingData(*first_and_others(x.strip().replace('\n','').split()))\
             for x in raw_data \
              if not x.startswith(';;;')]

def write_url_to_filename(url, filename):
    response = requests.get(URL, stream=True)

    if not response.ok:
        raise Exception("Error writing {} to {}".format(url, filename))

    with open(filename, 'wb+') as f:
        for block in response.iter_content(4096):
            f.write(block)

def find(predicate, iterable):
    """
    >>> find(lambda x: x % 2 == 0, [1, 2, 3, 4])
    2
    """
    return next(i for i in iterable if predicate(i))

def last_items_match(a, b, how_many):
    """
    >>> last_items_match([1, 2, 3], [7, 2, 3], 2)
    True
    """
    return a[-how_many:] == b[-how_many:]

def find_rhymes(word, data, how_many_phonemes=2):
    """
    Finds all the words in `data` that rhyme with `word`, that is,
    all the words that end in the same `how_many_phonemes` phonemes.

    `word` itself is always included as each word rhymes with itself
    (except when it has less than `how_many_phonemes` phonemes).

    >>> find_rhymes("example", [ReadingData('EXAMPLE', ['IH0', 'G', 'Z', 'AE1', 'M', 'P', 'AH0', 'L']),
    ...                         ReadingData('AMPAL', ['AE1', 'M', 'P', 'AH0', 'L']),
    ...                         ReadingData('HAPPINESS', ['HH', 'AE1', 'P', 'IY0', 'N', 'AH0', 'S'])])
    [ReadingData(word='EXAMPLE', phonemes=['IH0', 'G', 'Z', 'AE1', 'M', 'P', 'AH0', 'L']), ReadingData(word='AMPAL', phonemes=['AE1', 'M', 'P', 'AH0', 'L'])]

    """
    this_phonemes = find(lambda line: line.word == word.upper(), data).phonemes
    return [candidate for candidate in data \
             if last_items_match(candidate.phonemes, this_phonemes, how_many_phonemes)]

def main():
    if not os.path.isfile(LIBRARY):
        write_url_to_filename(URL, LIBRARY)
    with open(LIBRARY) as f:
        data = format_data(f.readlines())
    print(find_rhymes("FORCE", data, PHONEMES_TO_MATCH)[:20])

if __name__ == "__main__":
    doctest.testmod()
    main()

Your use of constants is a bit buggy. First of, since you call write_url_to_filename(URL, LIBRARY), you should change

def write_url_to_filename(url, filename):
    response = requests.get(URL, stream=True)

into

def write_url_to_filename(url, filename):
    response = requests.get(url, stream=True)

i.e: use the parameter instead of the constant.

Secondly, since you only use your constants in main and pass them as parameters afterwards, I feel it would be best to have them as parameters with default value instead of constants:

def main(library='library.txt',
         url='http://svn.code.sf.net/p/cmusphinx/code/trunk/cmudict/cmudict-0.7b',
         phonemes=3):
    if not os.path.isfile(library):
        write_url_to_filename(url, library)
    with open(library) as f:
        data = format_data(f.readlines())
    print(find_rhymes("FORCE", data, phonemes)[:20])

I would also have named write_url_to_filename simply download_into but it's not guaranteed that it is a better name.

On a stylistic note, you make extensive use of \ in your list-comprehensions where implicit line continuation are at play. You can drop them, it won't change the meaning.

You also seem to indent them one extra space after each line, try to avoid that.

find is just applying a filter and taking the first element. Since you are using Python 2, you may be insterested in itertools.ifilter instead of filter. The former being an iterator whereas the latter returns a list.

Not that your approach is bad per se, but you might want to compare the two, performance wise:

from itertools import ifilter

def find(predicate, iterable):
    return next(ifilter(predicate, iterable))

When building your ReadingData, your x.strip().replace('\n','').split()) can be replaced by x.split() as split without arguments has extra logic to clean-up a string while performing the split.

I would also change your helper function into:

def clean_line(line):
    data = line.split()
    return ReadingData(data[0], data[1:])

so that:

you can simplify format_data:

def format_data(raw_data):
    return [clean_line(x) for x in raw_data if not x.startswith(';;;')]

you let the possibility to the writer of the question that led to this code to write, in Python 3:

def clean_line(line):
    word, *phonemes = line.split()
    return ReadingData(word, phonemes)

which is even more explicit
You can use it directly in your with block without having to read the whole file into memory first:

def main(library='library.txt',
         url='http://svn.code.sf.net/p/cmusphinx/code/trunk/cmudict/cmudict-0.7b',
         phonemes=3):
    if not os.path.isfile(library):
        write_url_to_filename(url, library)
    with open(library) as f:
        data = [clean_line(line) for line in f if not line.startswith(';;;')]
    print(find_rhymes("FORCE", data, phonemes)[:20])

Alternatively, you could just pass the file f to format_data instead of the list of lines. It will work without modifications and will also let you build the data as you read the file instead of reading the file first and then building data.


A PDO connection classto initiate multiple connection and easy access I've been looking for a way to make the database connection easy available directry from any script, and from inside other classes. And since I tend to have different connections based on what action to execute, I had to find a way to easily scale the amount of connection needed.

Here's the solution I come up with.

I created this class:

class database{
    protected static $details = array();  //  holds all connection(s) details
    protected static $con = array();  //  holds the actual PDO connection(s)

/**
 *  addConnection()
 *  Adds a new connection
 *  @param string $alias a unique identifier for the connection
 *  @param string $db the database name
 *  @param string $un username
 *  @param string $pw password for the user
 *  @param string $desc a short description for this connection
 */
    public static function addConnection($alias,$db,$un,$pw,$desc){
        self::$details[$alias]=array('alias'=>$alias,'db'=>$db,'un'=>$un,'pw'=>$pw, 'desc'=>$desc);
    }

/**
 *  getConnection()
 *  @return array of a specific connection if a valid alias is provided. Othervise return a multidimensional array of all connections.
 */
    public static function getConnections($alias=''){
        if(!empty($alias)) return self::$details[$alias];
        else return self::$details;
    }

/**
 *  setConnection()
 *  This function moves the connection to $con[] for easy access both inside and outside of this class
 *  @param string $alias a unique identifier for the connection
 *  @param string $connection the string of a new pdo connection
 */
    public static function setConnection($alias,$connection){
        self::$con[$alias] = $connection;
    }

/**
 *  useConnection()
 *  @param string $alias a unique identifier for the connection
 *  @return a specific PDO connection based on the given alias
 */
    public static function useConnection($alias){
        return self::$con[$alias];
    }
}

And this script to set/initiate multiple connections:

if(database::getConnections()){
    try{
        $dbh_options = array(
            PDO::ATTR_EMULATE_PREPARES=>false,
            PDO::ATTR_DEFAULT_FETCH_MODE=>PDO::FETCH_ASSOC,
            PDO::MYSQL_ATTR_INIT_COMMAND=>'SET NAMES utf8',
            PDO::ATTR_ERRMODE=>PDO::ERRMODE_SILENT,
        );
        foreach(database::getConnections() as $dbh){
        #   initiate connection
            database::setConnection($dbh['alias'],new PDO('mysql:host=localhost;dbname='.$dbh['db'].';charset=utf8',$dbh['un'],$dbh['pw'],$dbh_options));
        //
        #   put the connection to a an array for easy access when coding
            $con[$dbh['alias']]=database::useConnection($dbh['alias']);
        //
        }
    } catch(PDOException $e) {
        file_put_contents('PDOException.txt',$e->getMessage(), FILE_APPEND);
        die('OBS! Something went wrong connecting to your database.<br>Please see PDOException.log for more details.');
    }
}

Here's how I add new connections:

database::addConnection('alias','database','username','password','a optional short description');
database::addConnection('alias2','database','username','password',null);

Amd this is how I can use the connection from whitin another class:

$select = $con['alias']->prepare('SELECT...');
$insert = $con['alias2']->prepare('INSERT INTO...');

And from other classes, I just extends the database class.

class sql extends database {
    public static function query($id){
        $query = self::$con['alias']->prepare('SELECT column FROM table WHERE id = ?');
        $query->execute(array($id));
        return $query->fetchColumn();
    }
}

But I would really like your oppinion on this. If there's any security issues with this setup?

You have some issues in code design and codestyle:

All class names must be Capitalized
Never use self::$field if $field is protected, use static::$field instead. If you use self child classes won't have access to redefine field!
Never use die() you have exceptions for this!
Save process time use if ($con = database::getConnections())
Class containing only static fields is useless and fully procedural-style, create Singleton or Registry instead.


Fastest way for working with itertools.combinations I need to speed up the function below:

import numpy as np
import itertools

def combcol(myarr):
    ndims = myarr.shape[0]
    solutions = []
    for idx1, idx2, idx3, idx4, idx5, idx6 in itertools.combinations(np.arange(ndims), 6):
        c1, c2, c3, c4, c5, c6 = myarr[idx1,1], myarr[idx2,2], myarr[idx3,1], myarr[idx4,2], myarr[idx5,1], myarr[idx6,2]
        if c1-c2>0 and c2-c3<0 and c3-c4>0 and c4-c5<0 and c5-c6>0 :
            solutions.append(((idx1, idx2, idx3, idx4, idx5, idx6),(c1, c2, c3, c4, c5, c6)))
    return solutions

X = np.random.random((20, 10))
Y = np.random.random((40, 10))

if __name__=='__main__':
    from timeit import Timer
    t = Timer(lambda : combcol(X))
    t1 = Timer(lambda : combcol(Y))
    print('t : ',t.timeit(number=1),'t1 : ',t1.timeit(number=1))

Results:

t :  0.6165180211451455 t1 :  64.49216925614847

The algorithm is too slow for my standard use (myarr.shape[0] = 500).  Is there a NumPy way to decrease execution time of this function (without wasting too much memory)?  Is it possible to implement the problem in Cython?

Your algorithm is of time complexity O(n^6) in ndims. If your current code needs 65 s for ndims = 40, then one could estimate the time for ndims = 500 to be roughly 8 years. Even an improvement of the most inner block's execution time by a factor of 1000 would yield an execution time of about 3 days. I guess this is not good enough.

So you should better try to improve the algorithm itself. However I do not really understand the problem the function is trying to solve and I couldn't come up with a better solution on the spot.

Also I haven't looked at numpy approaches, because you seem to have no vectorizable calculations in there.

Nonetheless I tried to make improvements to the code as is. I came up with the following:

You use only the a small fraction of myarr, so extract these parts first

myarr1 = myarr[:,1]
myarr2 = myarr[:,2]

Since you do many index lookups on these arrays turn them into lists. Numpy is not good at single index lookups.

myarr1 = myarr[:,1].tolist()
myarr2 = myarr[:,2].tolist()

Instead of substracting and comparing to 0, compare the variables directly saving one operation:

if c1>c2 and c2<c3 and c3>c4 and c4<c5 and c5>c6:

Instead of using and, you can also connect the comparisons all together, potentially saving the double variable lookups:

 if c1 > c2 < c3 > c4 < c5 > c6:

Instead of assigning the array elements to c1, c2, etc., use them directly. Since later comparisons are not executed if earlier one already return False this might save array lookups:

if myarr1[idx1] > myarr2[idx2] < myarr1[idx3] > myarr2[idx4] < myarr1[idx5] > myarr2[idx6]:

All in all I get the following code:

import numpy as np
import itertools

def combcol(myarr):
    ndims = myarr.shape[0]
    solutions = []
    for idx1, idx2, idx3, idx4, idx5, idx6 in itertools.combinations(np.arange(ndims), 6):
        c1, c2, c3, c4, c5, c6 = myarr[idx1,1], myarr[idx2,2], myarr[idx3,1], myarr[idx4,2], myarr[idx5,1], myarr[idx6,2]
        if c1-c2>0 and c2-c3<0 and c3-c4>0 and c4-c5<0 and c5-c6>0 :
            solutions.append(((idx1, idx2, idx3, idx4, idx5, idx6),(c1, c2, c3, c4, c5, c6)))
    return solutions

def combcol2(myarr):
    ndims = myarr.shape[0]
    myarr1 = myarr[:,1].tolist()
    myarr2 = myarr[:,2].tolist()
    solutions = []
    for idx1, idx2, idx3, idx4, idx5, idx6 in itertools.combinations(range(ndims), 6):
        if myarr1[idx1] > myarr2[idx2] < myarr1[idx3] > myarr2[idx4] < myarr1[idx5] > myarr2[idx6]:
            solutions.append(((idx1, idx2, idx3, idx4, idx5, idx6),(myarr1[idx1], myarr2[idx2], myarr1[idx3], myarr2[idx4], myarr1[idx5], myarr2[idx6])))
    return solutions

X = np.random.random((40, 10))
Y = [np.random.random((10, 10)) for i in range(100)]

if __name__=='__main__':
    from timeit import Timer
    for test_case in Y: assert combcol(test_case) == combcol2(test_case)
    t = Timer(lambda : combcol(X))
    t1 = Timer(lambda : combcol2(X))
    print('t : ',t.timeit(number=1),'t1 : ',t1.timeit(number=1))

With results like these:

t :  12.221544027328491 t1 :  0.8104081153869629
t :  10.69440507888794 t1 :  0.6592199802398682
t :  12.91178011894226 t1 :  0.8727250099182129
t :  11.21804690361023 t1 :  0.6851639747619629

The improvement is not even close to what you need. Also I tried to run the algorithm with ndims = 80 and got memory problems. The reason is the number of solutions: There were 18679356 solutions taking up 5 GB of RAM. With other values for ndims I found that around 5% - 25% of all possible solutions are valid! So it seems you need to change the way you output your solutions if you want to get beyond ndims = 100 on any realistic machine.

Edit: I just notice that 5 GB is a bit too much for the number of solutions. However this was the memory allocated by the python process. A run with ndims = 100 was unsuccessful due to lack of available memory.

Edit2: There is actually something far more efficient you can do, by interweaving your solution checks with the combination generation (abandoning itertools.combinations). This doesn't look so nice however:

import numpy as np
import itertools

def combcol(myarr):
    ndims = myarr.shape[0]
    solutions = []
    for idx1, idx2, idx3, idx4, idx5, idx6 in itertools.combinations(np.arange(ndims), 6):
        c1, c2, c3, c4, c5, c6 = myarr[idx1,1], myarr[idx2,2], myarr[idx3,1], myarr[idx4,2], myarr[idx5,1], myarr[idx6,2]
        if c1-c2>0 and c2-c3<0 and c3-c4>0 and c4-c5<0 and c5-c6>0 :
            solutions.append(((idx1, idx2, idx3, idx4, idx5, idx6),(c1, c2, c3, c4, c5, c6)))
    return solutions

def combcol2(myarr):
    ndims = myarr.shape[0]
    myarr1 = myarr[:,1].tolist()
    myarr2 = myarr[:,2].tolist()
    solutions = []

    for idx1 in range(ndims):
        c1 = myarr1[idx1]
        for idx2 in range(idx1+1, ndims):
            c2 = myarr2[idx2]
            if c1 > c2:
                for idx3 in range(idx2+1, ndims):
                    c3 = myarr1[idx3]
                    if c2 < c3:
                        for idx4 in range(idx3+1, ndims):
                            c4 = myarr2[idx4]
                            if c3 > c4:
                                for idx5 in range(idx4+1, ndims):
                                    c5 = myarr1[idx5]
                                    if c4 < c5:
                                        for idx6 in range(idx5+1, ndims):
                                            c6 = myarr2[idx6]
                                            if c5 > c6:
                                                solutions.append(((idx1, idx2, idx3, idx4, idx5, idx6),(c1, c2, c3, c4, c5, c6)))
    return solutions

X = np.random.random((40, 10))
Y = [np.random.random((10, 10)) for i in range(100)]

if __name__=='__main__':
    from timeit import Timer
    for test_case in Y: assert combcol(test_case) == combcol2(test_case)
    t = Timer(lambda : combcol(X))
    t1 = Timer(lambda : combcol2(X))
    print('t : ',t.timeit(number=1),'t1 : ',t1.timeit(number=1))

The result:

t :  11.706523180007935 t1 :  0.15908312797546387
t :  12.531341075897217 t1 :  0.16385602951049805
t :  11.581043004989624 t1 :  0.14388418197631836

So with that we already have nearly a factor of 100x speed-up.


Non-recursive method for finding \$a^n\$ I am working on an interview question from Amazon Software. The particular question I am working on is "to write a program to find \$a^n\$."

Here is my recursive solution to this problem (in Java):

int pow(int a, int n) {
     if(n == 0) {
          return 1;
     } else {
          return a * pow(a, n -1 );
     }
}

I did some runtime analysis and found that this solution runs in \$O(n)\$ time - recurrence relation with \$T(n) = 3 + T(n-1)\$, \$T(0)=1\$, and \$O(n)\$ space - depth of memory stack is \$n\$, with two local variables at each call, \$2n\$ total.

We are always taught to optimize our code in terms of space complexity and time complexity, so here is another solution that I came up with:

int pow(int a, int n) {
     int result = 1;
     for(int count=0;count<n;count++) {
           result *= a;
     }
     return result;
}

Would this solution be more efficient than the first one? This one runs in \$O(n)\$ time-loop until \$n\$ and \$O(1)\$ space - four units of space - one for a, n, result, and count.

There is a more efficient method using squaring:

int result = 1;
while(n>0){
    if(n%2 == 1)result*=a;
    a *= a;
    n /= 2;
}

Or in recursive notation:

int pow(int base, int exponent) {
     if(exponent == 0) {
          return 1;
     } else if(exponent%2 == 1){
          return base * pow(base*base, exponent / 2 );
     } else {
          return pow(base*base, exponent / 2 );
     }
}

This works because

\$\$ a^n = \begin{cases}
(a^2)^{\frac{n}{2}} & \text{if $n$ is even} \\
a \cdot (a^2)^{\frac{n-1}{2}} & \text{if $n$ is odd}
\end{cases}\$\$


"Enter key pressed" event-handler I am writing an "Enter key pressed" event-handler, so when user presses the "enter" key in the input of type text, this code is called:

    var email = "";
    var subscriberInput = $("input[name='subscriber_email']")
    // Subscribe RSS
    subscriberInput.keyup(function(e){
        if(e.which == 13){ // Enter key was pressed
            email = subscriberInput.val();
            $.post("/en/subscriber/add", { email: email }).done(function(data){
                 if(data == "success"){

                       subscribeBox.find('div.row').remove();

                       if(isEnglish){
                           subscribeBox.find('h5').text("You're subscribed!").addClass('green-text');
                       } else {
                           subscribeBox.find('h5').text("Sunteti abonat cu success").addClass('green-text');
                       }

                       setTimeout(function(){
                           subscribeBox.fadeOut('slow');
                       }, 5000)
                 } else {
                     alert(data);
                 }
            });
            return false;
        }
    });

How can I improve this code?

A few things to note before I explain improvements

Never forget var when declaring variables. I saw this in the code.

email = subscriberInput.val();

Now, best case scenario is that you declared email somewhere in the higher scopes. However, if it wasn't then JS will declare it as a global, which may have unforseen negative effects.
If you run a site that has translation capabilities, I suggest you don't hard-code messages. Use translation libraries instead. That way, you can globally change language with just a flick of a switch.

Then here's the improved code, given what you have:

subscriberInput.keyup(function (event) {

  // If you intent to prevent the default action of the enter, then I
  // suggest preventDefault() instead of return false
  event.preventDefault();

  // I recommend the "return if fail" pattern rather than "run when true"
  // because it removes unnecessary indentation. It's a case to case basis.
  if (event.which !== 13) return;

  $.post("/en/subscriber/add", {
    // The context of the function is the input box. We can simply use
    // the value property instead of calling out val()
    email: this.value
  }).done(function (data) {

    // Similar to above, use strict comparison as much as possible
    if (data === "success") {

      // Avoid repeating code by factoring out common code. In this case,
      // what set the code apart was the message.
      var message = isEnglish ? "You're subscribed!" : "Sunteti abonat cu success";

      subscribeBox.find('div.row')
                  .remove();

      // jQuery actually has a delay() function which can delay animations.
      // Better than using timers manually.
      subscribeBox.find('h5')
                  .addClass('green-text')
                  .text(message)
                  .delay(5000)
                  .fadeOut('slow');

    } else {

      // Now I don't know why you are doing the alert. If you are debugging,
      // I suggest you use console.log() or a custom logging library.
      alert(data);
    }
  });

});


Abstract factory or inversion of control pattern? I have several generic methods that use the typeof operator to determine the type of mapper class to create.  Eventually this is going to get out of hand.

Can anyone suggest a better way to handle this?  I have been reading up a bit and it seems like an abstract factory pattern or IOC would be a good pattern to use.  I'm not familiar with IOC.  Can someone provide an opinion on which would be better in this scenario?

internal UpdateStudentDocumentRequest MapDocToUpdateDocumentRequest<T>(T doc)
{
    Type docType = typeof(T);

    //V1
    if
    (
        docType == typeof(IndV1201314Model) ||
        docType == typeof(IndV1201415Model) ||
        docType == typeof(DepV1201415Model)
    )
    { return new V1DocMapper<Models.Verification.V1Base>().MapV1ToUpdateStudentDocumentRequest(doc as Models.Verification.V1Base); }

    //V3
    if
    (
        docType == typeof(IndV3201314Model) ||
        docType == typeof(IndV3201415Model) ||
        docType == typeof(DepV3201415Model)
    )
    { return new V3DocMapper<Models.Verification.V3Base>().MapV3ToUpdateStudentDocumentRequest(doc as Models.Verification.V3Base); }

    //FASchol
    if (docType == typeof(FAScholModel))
    {return new FAScholMapper().MapFAScholToUpdateStudentDocumentRequest(doc as FAScholModel);}

    return new UpdateStudentDocumentRequest();
}

IOC vs Abstract factory is kind of an apples to oranges question.  Abstract factory assumes you have a collection of related classes for which you don't want to know any of details involved in creating instances of those classes.  IOC doesn't necessarily abstract you away from the creation, it just sort of moves it to another area of your code base. In your particular scenario, one way to simplify that code might be like this

public class DocumentMappingSelector
{
    private Dictionary<Type, Type> mappingRoutes = new Dictionary<Type,Type>();

    public void AddRoute(DocumentMappingRoute route)
    {
         if (this.mappingRoutes.ContainsKey(route.SourceType))
         {
                // you could throw an exception or replace the route here, for this
                // example i'll just replace it
                if (this.mappingRoutes[route.SourceType] != route.MapperType)
                {
                    this.mappingRoutes[route.SourceType] = route;
                }
                else
                {
                     this.mappingRoutes.Add(route.SourceType, route);
                }
         }
    }

    public DocumentMappingRoute SelectMappingRoute(Type sourceType)
    {
        DocumentMappingRoute result = null;
        if (this.mappingRoutes.ContainsKey(sourceType))
        {
            result = this.mappingRoutes[sourceType];
        }
        return result;
    }
}

public class DocumentMappingRoute
{
    public DocumentMappingRoute(Type sourceTypeToBeMapped, Type mappingStrategyType, Action<object,UpdateStudentDocumentRequest> mappingProcessAction)
    {
         this.SourceType = sourceTypeToBeMapped;
         this.MapperType = mappingStrategyType;
         this.MappingProcess = mappingProcessAction;

    }
    Type SourceType { get; private set; }
    Type MapperType  { get; private set; }
    Action<object,UpdateStudentDocumentRequest> PerformMapping { get; private set; }
}
internal UpdateStudentDocumentRequest MapDocToUpdateDocumentRequest<T>(T doc)
{
    Type sourceType = typeof(T);
     UpdateStudentDocumentRequest updateStudentDocumentRequestInstance = new UpdateStudentDocumentRequest ();
    return selectorInstance.SelectMappingRoute(sourceType).MappingProcess(doc, updateStudentDocumentRequestInstance);  // you might not need the updateStudentDocumentRequestIsntance paramter here
}

For give any errors, I didn't type this in visual studio I just typed it in this editor.

Create and Add Document mapping routes to the selector
Get the mapping from the selector

Sorry this doesn't show the full code.  I ran short on time, but this should give you a general direction that will keep your code tight.  Let me know if you have any questions.


Singly linked list backed stack I commented on a question and blindly asserted that a Stack based on a linked list was rather elegant (see here)

I haven't ever written a Stack in C# so I thought I should back up my claim:

public class Stack<T> : IEnumerable<T>
{
    protected class StorageNode
    {
        public T Value { get; set; }

        public StorageNode Next { get; set; }

        public StorageNode(T value)
        {
            Value = value;
        }
    }

    public int Count { get; private set; }

    private StorageNode head;

    public void Push(T value)
    {
        var newNode = new StorageNode(value);
        if (head != null)
        {
            newNode.Next = head;
        }
        head = newNode;
        ++Count;
    }

    public T Pop()
    {
        if (head == null)
        {
            throw new InvalidOperationException("Cannot pop an empty stack");
        }
        var result = head.Value;
        head = head.Next;
        --Count;
        return result;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var current = head;
        while (current != null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

I didn't use the .Net LinkedList because I thought it was a bit overkill for a singly linked list...

Is there anything I can improve in my code?

Personally I would change

public void Push(T value)
{
    var newNode = new StorageNode(value);
    if (head != null)
    {
        newNode.Next = head;
    }
    head = newNode;
    ++Count;
}

into

public void Push(T value)
{
    var newNode = new StorageNode(value);
    newNode.Next = head;
    head = newNode;
    ++Count;
}

because I find the control not really useful. I mean, if the head is null then nothing happens, newNode.Next remains null.

Better yet (in my opinion), if you add a constructor:

public StorageNode(T value, StorageNode next)
{
    Value = value;
    Next = next;
}

the Push method can be written as:

public void Push(T value)
{
    head = new StorageNode(value, head);
    ++Count;
}