Random walker using Processing.JS on Khan Academy, with new walkers generated on mouse click I've created a project on Khan Academy as part of the Natural Simulations course on random walks.

This project is in JavaScript, using the Processing.JS library, slightly modified by Khan Academy.

(In the main, the inclusion of the Processing.JS library offers a few functions for drawing on a canvas. The majority of my project would be perfectly intelligible to someone who knew JavaScript but not about Processing.JS).

The code is as follows:

var Walker = function(colour, x, y) {
    this.radius = 10;
    this.x = x || width/2; // 'width' and 'height' refer to the size of the canvas
    this.y = y || height/2;
    this.r = (colour[0] === 0)? true: colour[0] || random(0, 255);
    this.g = (colour[1] === 0)? true: colour[1] || random(0, 255);
    this.b = (colour[2] === 0)? true: colour[2] || random(0, 255);
    return this;
};

// Randomly move up, down, left, right, or stay in one place
Walker.prototype.walk = function() {
    var choice = floor(random(0, 4));
    if (choice === 0 && this.x < width) {
        this.x += this.radius; // move right
    } else if (choice === 1 && this.x > 0) {
        this.x -= this.radius; // move left
    } else if (choice === 2 && this.y < height) {
        this.y += this.radius; // move down
    } else if (choice === 3 && this.y > 0) {
        this.y -= this.radius; // move up
    }
    return this;
};

Walker.prototype.display = function() { // Processing.JS drawing stuff
    noStroke(); // turn outline off
    fill(this.r, this.g, this.b, 20); // fill(r, g, b, transparency);
    ellipse(this.x, this.y, this.radius, this.radius); // ellipse(x-position, y-position, width, height);
    return this;
};

var walkers = [new Walker([255, 0, 0])];

draw = function() { // repeats 30 times/second. Like a for/while loop, but slower
    for(var i = 0; i < walkers.length; i++) {
        walkers[i].walk().display();
    }
};

mouseClicked = function() {
    walkers.push(
        new Walker([], round(mouseX / walkers[0].radius) * walkers[0].radius, round(mouseY / walkers[0].radius) * walkers[0].radius));
}; // ^ mouseX/mouseY refer to current position of mouse on canvas

View the project on Khan Academy.

I'm concerned about the performance of this code; specifically the for loop in the draw function. As the draw function repeats 30 times/second, will this mean that the loop will also repeat 30 times/second?

The program gets pretty slow when there's quite a few walkers initiated. How can I make this program perform better?

I would put noStroke in a different location.

You are trying to make this code more efficient. You call noStroke each time one of these guys is called. You really only need to call it once right? So change the state once in your draw function:

draw = function() {
    noStroke();
    for(var i = 0; i < walkers.length; i++) {
        walkers[i].walk().display();
    }
};

And remove it from your Walker.display function:

Walker.prototype.display = function() {
    fill(this.r, this.g, this.b, 20);
    ellipse(this.x, this.y, this.radius, this.radius);
    return this;
};


Encode strings as base64 I have this function I've written to encode strings of binary data as base64 strings. I'd like to see if there are areas where it could be improved, specifically:

Is the function correct? Are there edge cases I haven't accounted for? (Handling arbitrary UTF-8 correctly is a "nice-to-have" but not a "need-to-have" if it significantly increases complexity, but it should be able to handle arbitrary ASCII, treating control and whitespace characters as normal characters)
Can the performance of the algorithm I used be improved? Am I mistaken that its time and space complexities are both O(n), and can either be improved further? Can this problem be parallelized nicely?
Can it safely accept arbitrary/malicious input?
Am I using the right language features for the best performance? (The strings in this case would be generated at runtime, but it would be interesting if anyone wanted to show how to do it with template magic at compile-time, which is a few steps above my level).
Is it idiomatic, modern code that follows best practices? Am I relying on any nonstandard behavior? (Not necessarily a problem, but good to know).

#include "ToBase64.h" // string, experimental/string_view
#include <cinttypes>
#include <stdexcept>

using std::length_error; // stdexcept
using std::string; // string
using std::experimental::string_view; // experimental/string_view
using std::uint8_t; // cinttypes

string to_base64(const string_view input)
{
        static constexpr auto BASE64{
                "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
        };

        const auto len{ input.length() };
        string output;
        if (len > output.max_size() / 4 * 3 - 4) {
                throw length_error{ "Output too large to fit in std::string" };
        }
        output.reserve(len / 3 * 4 + 4);

        auto remainder{ 0 };
        uint8_t leftover{ 0 };

        for (uint8_t c : input) {
                switch ((remainder %= 3)++) {
                case 0:
                        output += BASE64[c >> 2];
                        leftover = c << 6;
                        break;
                case 1:
                        output += BASE64[(leftover >> 2) + (c >> 4)];
                        leftover = c << 4;
                        break;
                case 2:
                        output += BASE64[(leftover >> 2) + (c >> 6)];
                        output += BASE64[c & 0x3F];
                        break;
                }
        }

        switch (remainder) {
        case 1:
                output += BASE64[leftover >> 2];
                output += "==";
                break;
        case 2:
                output += BASE64[leftover >> 2];
                output += '=';
                break;
        }

        return output;
}

#include "ToBase64.h" // string, experimental/string_view

Best practice in C and C++ is to "#include what you use" in every file. Admittedly, in this case there is no possible way someone could refactor "ToBase64.h" to omit one of those headers, because both of those types are used in the signature of the single function that is the raison d'etre of the header. But still — I'd list #include <string> and #include <std/experimental/string_view> in "ToBase64.cc" as well as in "ToBase64.h".

using std::length_error; // stdexcept
using std::string; // string
using std::experimental::string_view; // experimental/string_view
using std::uint8_t; // cinttypes

In general, using declarations are frowned upon; although again in this case it's harmless. using declarations in header files are the really bad thing. In "ToBase64.cc", you could just as well get away with

using namespace std;

so I'm not sure why you're spending four lines to say basically the same thing. (And the comments aren't adding anything. Kill them.)

string to_base64(const string_view input)

I'm not sure what the best practice is with string_view: take it by value or by const reference? I'll assume by value is fine, since the whole point of string_view is that it's cheap to copy. But in general, taking things by const value is weird. It doesn't change the function's signature — i.e.

string to_base64(const string_view input);
string to_base64(string_view input);

redeclare the same function — so generally we'd like to omit the redundant const.

Man, so far I've commented on every single line of the code "well, this line is weird, but I guess it's harmless in this context..." ;p  Don't worry, the line after this one looks great!

static constexpr smells redundant; is it actually any different from constexpr?

The expression len > output.max_size() / 4 * 3 - 4 has too many operators in too unfamiliar an order for my puny brain. I guess you're saying "suppose I base64-decoded a 0xffffffff-character string... how many characters would the decoding have? If the given plaintext has more characters than that, then let's report that the encoding failed. Except minus four for some reason."

In practice, std::string::max_size() will be on the order of 2^63 or 2^64 — so astronomically large that your algebraic expression is physically incapable of ever being false. (Logically capable, yes. Physically capable, no; no computer in the world will ever have that much memory, or enough time to initialize it if it did.) So I'd say it's better to keep the code simple and omit that check. As a bonus, this lets you kill off the temporary variable len.

If your machine is actually running out of memory, the output.reserve on the next line will throw bad_alloc anyway.

Just kidding — it'll return successfully and then you'll get oomkilled at random, later.

auto remainder{ 0 };
uint8_t leftover{ 0 };

This seems fine to me, but I'm surprised that you're following neither the "Almost Always Auto zealot" pattern of

auto remainder = 0;
auto leftover = uint8_t(0);

nor the "I'm a normal person" pattern of

int remainder = 0;
uint8_t leftover = 0;

I guess your pattern is the one that allows the most use of Uniform Initialization, though.

switch ((remainder %= 3)++)

Please don't.

output += "==";
// ...
output += '=';

This is correct, but strikes me as a refactoring typo waiting to happen. In Python, Javascript, Perl, Bash, etc., string literals can be delimited with either ' or "; but in C++, "==" is a string and '==' is a multi-character character constant with implementation-defined value (15677 on all sane platforms).

output += "==\n";
// ...
output += '=\n';  // oops

Admittedly the above code generates two warnings on both GCC and Clang, and it's a hugely unlikely refactoring anyway; but still, if this were my code, I'd use "double quotes" in both cases.

Other than all these nitpicks, it looks very clean and certainly correct!


Node.js equivalent of cat -n or nl To add line numbers to a file (via stdin to stdout) we can use cat -n or nl.

Given the file test.txt with:

hello
hello
bye

We can do:

$ cat -n < test.txt
     1  hello
     2  hello
     3  bye

In languages like AWK, Perl, and Ruby, we often get built-in constructs to process files line-by-line, making this program trivial to write. Here is what I have in Ruby:

line_number = 0;
ARGF.each {|line| printf("%6d\t%s", line_number += 1, line)}

and granted, in AWK, it is much simpler since the line number is already present.

I've just tried to write this same script in node.js but found myself having to import the built-in fs module and then import three separate third-party modules.  My solution is:

var fs = require('fs');
var through = require('through');
var split = require('split');
var sprintf = require('sprintf').sprintf;

var linenum = 0;

var number = through(function (line) {
  this.queue(sprintf('%6d\t%s\n', ++linenum, line));
});

process.stdin.pipe(split()).pipe(number).pipe(process.stdout);

This is not intended to be a code-golfing problem, but rather a question of whether I have missed some built-in support for doing this kind of thing in node.  I like the separation of concerns, but what I thought would be a simple script in node turned out rather long.  Can it be improved?

It seems you need through and split to do the piping right. You do not need sprintf as you could build the number formatting yourself. You also do not need fs, you do not use it anywhere.

Something like

var through = require('through');
var split = require('split');

var linenum = 0;

function alignRight( s, n )
{
  s = s + "";
  return s.length > n ? s : new Array( n - s.length + 1 ).join(" ") + s;
}

var number = through(function (line) {
  this.queue( alignRight( ++linenum, 6 ) + "\t" + line + "\n"  );
});

process.stdin.pipe(split()).pipe(number).pipe(process.stdout);

Does the trick for me. While it seems overkill, the nice thing is that you can pipe data between functions yourself, not needing to rely on the OS shell.


More Pythonic Context Manager Wrapper I wanted to ask this here because what I wanted to originally do felt like a really Pythonic method. I want to be able to use the syntax:

d = {'apple':{'cranberry':{'banana':{'chocolate':[1,2,3,4,5,6]}}},'b':2}
with d['apple']['cranberry']['banana']['chocolate'] as item:
    for i in item:
        print(i)

    item.append('k')

but found that Python doesn't allow for using lists, dicts, etc. as context managers.

So I implemented my own:

def context_wrap(target):
    class ContextWrap:
        def __init__(self, tgt):
            self._tgt = tgt

        def __enter__(self):
            return self._tgt

        def __exit__(self, type, value, traceback):
            pass

    return ContextWrap(target)

if __name__ == '__main__':
    with context_wrap({'a':1}) as item:
        print(item['a'])

    with context_wrap([1,2,3,4,5]) as item:
        print(item[1])

    with context_wrap(3) as item:
        print (item)

In the above code, you can take any random object and wrap it inside an object that acts as a context manager controlling the underlying object. This means that inside any with clause, you can simply use the object with it's alias. I feel like it looks a lot cleaner and clearer than something like:

alias = d['apple']['cranberry']['banana']['chocolate']
for i in alias:
    print(i)

alias.append('k')

I wanted to know if there was a more "Pythonic" way to do it. So the improvement that I'm looking for is in terms of better reliance on the standard Python library and/or in terms of my syntax.

I think what you are doing is crazy, but yes, you can use Python’s library functions to clean it up.

from contextlib import contextmanager

@contextmanager
def context_wrap(target):
    yield target

Again, this is busy work.

alias = thing

is clearer, shorter and faster than

with context_wrap(thing) as alias:


Immutable binary search tree using Scala I have written a sample immutable binary search tree using Scala. However, I am not sure whether or not I was doing it the proper way since I am not an expert at functional programming. Is there a better or more efficient way of, say, traversing the tree or adding an item to it using a purely functional approach?

The add (+) method:

def +(data: T): Bst = {
  def insert(optTree: OptBst): Bst = optTree match {
    case None => BST(data)(comparison)
    case Some(tree) => comparison(data, tree.data) match {
      case cmp if cmp < 0 => tree(left = Some(insert(tree.left)))
      case cmp if cmp > 0 => tree(right = Some(insert(tree.right)))
      case _ => tree
    }
  }
  insert(Some(this))
}

Delete (-) method:

def -(data: T): OptBst = {
  def remove(optTree: OptBst): OptBst = optTree match {
    case None => None
    case Some(tree) => comparison(data, tree.data) match {
      case cmp if cmp > 0 => Some(tree(right = remove(tree.right)))
      case cmp if cmp < 0 => Some(tree(left = remove(tree.left)))
      case _ => (tree.hasLeft, tree.hasRight) match {
        case (false, false) => None
        case (true, false) => tree.left
        case (false, true) => tree.right
        case (true, true) =>
          val rightMinData = tree.rightMin.get.data
          Some(tree(data = rightMinData, right = tree.right.get - rightMinData))
      }
    }
  }
  remove(Option(this))
}

Search method:

  def search(data: T) = {
    @tailrec
    def search(optTree: OptBst): OptBst = optTree match {
      case None => None
      case Some(tree) => comparison(data, tree.data) match {
        case cmp if cmp < 0 => search(tree.left)
        case cmp if cmp > 0 => search(tree.right)
        case _ => optTree
      }
    }
    search(Some(this))
  }

I think it would be an improvement to define an empty element. Currently you have no way to represent an empty collection. But that is required if you would want to integrate your data structure with scala collections.

(In scala collections, you usually build up an immutable data structure like a Set or Map by starting with the empty element and adding elements. The apply methods defined in the companion objects are just convenience methods)

Defining an empty element will also simplify your code a lot. For example: you won't have to use Option for left and right, but can just use the empty value if e.g. left does not contain elements. For iteration for example you don't have to check whether left or right is empty by checking for None, but just call the method on the child.

In the simplest case this will look something like this:

object BST {
  def empty[T](implicit c:(T,T) => Int) : BST[T] = new EmptyBST(c)
}

sealed abstract class BST[T] {
  // abstract: whatever methods you want to support
}

case class EmptyBST[T](c:(T,T) => Int) extends BST[T] {
  // trivial implementation of all methods for an empty BST
}

case class NonEmptyBST[T](left:BST[T], right:BST[T], value:T, c:(T,T) => Int) extends BST {
  // non-trivial implementation of all methods for the non-empty case
}

Another thing: using (T,T) => Int is perfectly fine for educational purposes. But if you want this to match the style of other scala collections, you should use scala.math.Ordering. There are already predefined orderings and some utility methods to create orderings for composite objects like tuples.

For the traversal, I would not return a List[T] of all elements but instead just implement the Traversable[T] trait by defining a foreach method for each traversal order. That is much more efficient in case the user is not interested in everything but just the first few elements. And if the user wants a List[T] he can always make one by calling .toList. Traversal using foreach uses side effects internally, but for the end user these are not observable, so it's OK.


Read file contents to string safely I've just started to teach myself Rust. I've written the following code to read a text file and store the contents in a String. Is this the typical way of doing this? Can anyone suggest any improvements to this?

use std::fs::File;
use std::io::Read;
use std::io;

fn main() {

    let file_name = "test.txt";

    let mut file_contents = String::new();

    match get_file_contents(file_name, &mut file_contents) {
        Ok(()) => (),
        Err(err) => panic!("{}", err)
    };

    println!("{}", file_contents);

}

fn get_file_contents(name: &str, mut contents: &mut String) -> Result<(), io::Error> {

    let mut f = try!(File::open(name));

    try!(f.read_to_string(&mut contents));

    Ok(())

}

You could return the string directly:

fn main() {
    let file_name = "test.txt";
    let file_contents = match get_file_contents(file_name) {
        Ok(s) => s,
        Err(err) => panic!("{}", err)
    };

    println!("{}", file_contents);
}

fn get_file_contents(name: &str) -> Result<String, io::Error> {
    let mut f = try!(File::open(name));
    let mut contents = String::new();

    try!(f.read_to_string(&mut contents));

    Ok(contents)
}

and unwrap if you don’t intend to handle the error usefully:

let file_contents = get_file_contents(file_name).unwrap();


Karatsuba C++ implementation I've written an algorithm for integer multiplication using the Karatsuba method in C++. This implementation is far from ideal, so any comments are welcome.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cstring>

const int MAX_LENGTH = 50000 * 2 + 1;

void add_leading_zeros(char* a, int n) {
  int lena = strlen(a);
  for (int i = lena - 1 + n; i >= n; --i) {
    a[i] = a[i - n];
  }
  a[lena + n] = 0;
  for (int i = 0; i < n; ++i) {
    a[i] = '0';
  }
}

void remove_leading_zeros(char* a) {
  int lena = strlen(a);
  int ind = 0;
  while (ind < lena && a[ind] == '0') {
    ++ind;
  }

  for (int i = ind; i < lena; ++i) {
    a[i - ind] = a[i];
  }
  a[lena - ind] = 0;
}

void sum(char* a, char* b, char* res) {
  int lena = strlen(a);
  int lenb = strlen(b);

  if (lena < lenb) {
    std::swap(a, b);
    std::swap(lena, lenb);
  }

  int toAdd = 0;
  for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {
    int x = a[inda] - '0';
    int y = indb >= 0 ? b[indb] - '0' : 0;

    int cur = x + y + toAdd;

    if (cur >= 10) {
      toAdd = 1;
      cur -= 10;
    } else {
      toAdd = 0;
    }

    res[inda] = cur + '0';
  }

  if (toAdd == 1) {
    add_leading_zeros(res, 1);
    res[0] = '1';
  }
}

// assume that a > b
void sub(char* a, char* b, char* res) {
  int lena = strlen(a);
  int lenb = strlen(b);

  //assert(lena >= lenb);

  int toSub = 0;
  for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {
    int x = a[inda] - '0';
    int y = indb >= 0 ? b[indb] - '0' : 0;

    if (toSub == 1) {
      x--;
    }
    int cur;
    if (x < y) {
      cur = x + 10 - y;
      toSub = 1;
    } else {
      cur = x - y;
      toSub = 0;
    }

    res[inda] = cur + '0';
  }
}

// returns a * 10^n
void mult10(char* a, int n) {
  int lena = strlen(a);

  if (lena == 1 && a[0] == '0') {
    return;
  }

  for (int i = lena; i < lena + n; ++i) {
    a[i] = '0';
  }
  a[lena + n] = 0;
}

char* CreateArray(int len) {
  char* res = new char[len];
  memset(res, 0, len);
  return res;
}

// add leading zeros if needed
void make_equal_length(char* a, char* b) {
  int lena = strlen(a);
  int lenb = strlen(b);

  int n = std::max(lena, lenb);

  add_leading_zeros(a, n - lena);
  add_leading_zeros(b, n - lenb);
}

void karatsuba(char* x, char* y, char* res) {
  make_equal_length(x, y);

  int len = strlen(x);
  if (len == 1) {
    int val = (x[0] - '0') * (y[0] - '0');
    if (val < 10) {
      res[0] = val + '0';
    } else {
      res[0] = (val / 10) + '0';
      res[1] = (val % 10) + '0';
    }
  } else {
    char* xl = CreateArray(len);
    char* xr = CreateArray(len);
    char* yl = CreateArray(len);
    char* yr = CreateArray(len);

    int rightSize = len / 2;
    int leftSize = len - rightSize;

    strncpy(xl, x, leftSize);
    strcpy(xr, x + leftSize);
    strncpy(yl, y, leftSize);
    strcpy(yr, y + leftSize);

    int maxl = 3 * len;
    char* P1 = CreateArray(maxl);
    char* P2 = CreateArray(maxl);
    char* P3 = CreateArray(maxl);

    karatsuba(xl, yl, P1);
    karatsuba(xr, yr, P2);

    char* tmp1 = CreateArray(maxl);
    char* tmp2 = CreateArray(maxl);

    sum(xl, xr, tmp1);
    sum(yl, yr, tmp2);
    karatsuba(tmp1, tmp2, P3);

    sub(P3, P1, P3);
    sub(P3, P2, P3);
    mult10(P3, rightSize);

    mult10(P1, 2 * rightSize);

    sum(P1, P2, res);
    sum(res, P3, res);

    remove_leading_zeros(res);

    delete[] xl;
    delete[] xr;
    delete[] yl;
    delete[] yr;
    delete[] tmp1;
    delete[] tmp2;
    delete[] P1;
    delete[] P2;
    delete[] P3;
  }
}

int main() {
  char a[MAX_LENGTH], b[MAX_LENGTH];
  scanf("%s\n%s", a, b);

  char* res = CreateArray(MAX_LENGTH);
  karatsuba(a, b, res);

  printf("%s\n", res);

  scanf("%d", 1);

  return 0;
}

If you prefer programming in C-style, I suggest to use C.
If you want to use any part of C++, I suggest to embrace it fully.

I'll review only the main method for now,
I'm sure a lot more reviews will come from others.

You don't need the \n here. You can just drop it, it will work the same way:

  scanf("%s\n%s", a, b);

The C++ equivalent:

std::cin >> a >> b;

This generates a compiler warning, for good reason:
the arguments of scanf should be pointers, but it's an int.
Why is this line there at all? I suggest to remove it.

  scanf("%d", 1);


Constant time string comparision in PHP to prevent timing attacks I've been advised that when checking the password hash for a user I should use a string comparison function that always takes the same amount of time, to avoid timing attacks.

So I wrote this:

//this is a constant time string compare,
//it does not exit early even if the strings don't match
//it is case sensitve
//the time to compare is the time needed for the shorter string
//(if they are not the same length)
function time_strcmp($str1, $str2)
{
  $res = $str1 ^ $str2;
  $ret = strlen($str1) ^ strlen($str2); //not the same length, then fail ($ret != 0)
  for($i = strlen($res) - 1; $i >= 0; $i--) $ret += ord($res[$i]);
  return !$ret;
}

(I do it this way instead of checking equality in a loop just in case of optimization. Not sure if PHP does any, but it might in the future.)

Anyway, since this is such a critical part of the code, returning true when it shouldn't would completely defeat security.

Can anyone give me a code review? Or a better way?

Disclaimer

I have no formal education in security or cryptography, nor any kind of meaningful experience with either.

This post is basically me rambling, hopefully correctly :-).

Correctness

This is a very informal (and rough) analysis, but hopefully it will assure you that your function is indeed correct.

function time_strcmp($str1, $str2)
{
    $res = $str1 ^ $str2;
    $ret = strlen($str1) ^ strlen($str2); //not the same length, then fail ($ret != 0)
    for($i = strlen($res) - 1; $i >= 0; $i--) $ret += ord($res[$i]);
    return !$ret;
}

Assume that $str1 and $str2 are arrays of bytes, each n1 and n2 bytes long, respectively.

In PHP, the ^ operator is defined for strings such that:

$s1 ^ $s2 == chr(ord($s1[0]) ^ ord($s2[0])) . chr(ord($s1[1]) ^ ord($s2[1])) . ... chr(ord($s1[L]) ^ $s2[L])
with L = min(strlen($s1), strlen($s2))

You've used this to your advantage in that any matching characters bytes mask to 0, and any non-matching bytes will mask to a value that is greater than 0.

So $res will be filled with 0s only if $s1 === $s2 with:

$l = min(strlen($str1), strlen($str2));
$s1 = substr($str1, 0, $l);
$s2 = substr($str2, 0, $l);

(1) So basically $res will be 0-filled only if the strings exactly match or if one of strings in its entirety is a prefix of the other.

$ret = strlen($str1) ^ strlen($str2);

(2) $ret will be 0 only if $str1 and $str2 are of the same length.

(For later, let this be denoted $ret0)

for($i = strlen($res) - 1; $i >= 0; $i--) {
    $ret += ord($res[$i]);
}

(3) $ret will now be equal to the sum of the value of all of the bytes of $res.

Let the amount added to $ret in this loop be denoted $ret1.

(4) From (1), we can conclude that $ret1 will be 0 only if the strings exactly match or one of the strings is a prefix of the other.

Recall:

$ret = $ret0 + $ret1;

From (2) and (4) we can conclude that $ret will be 0 only if strings are of the same length and no bytes differ in them.  This means that $ret will be 0 iff $str1 === $str2.

So yes, your function is functionally correct.

Timing

I can't comment much on this.  You will of course want to make sure that the length of the shortest string is always the same, otherwise there will be a difference in timing.

Also, I believe strlen() is O(1) in PHP, but you may want to verify that.

Minor suggestion #1

There's a very unlikely problem with adding the values of the bytes.  If there exist a sufficient number of unequal bytes, their values may exceed the maximum of an integer.  Bitwise operators are undefined (I believe) for floating types in PHP.  What you could do instead of adding is use bitwise OR.

(I realized the overflow when seeing it, but the bitwise OR, I lifted from: here)

Ponderings

Typically hashing algorithms output hashes of the same length for all inputs.  This means that a difference in values is likely your concern.

For example, with a short circuited comparison:

'abcd' === 'abce'
'abcd' === 'bbcd'

The first one will take more time to execute than the second since the second will bail out on the first letter.

Consider now what this timing attack would allow you to determine.  It would allow you to determine part of the hash, not the password (though if you could actually determine the hash in full, you would have already found a collision and thus have gotten into the system).

This seems fairly harmless to me just because of the cascading changes in hashing algorithms.

Just because I know that A is more of the hash than B is does not mean that I'm any closer to finding the hash unless I know how to change A in a manner such that the first N bytes of hash(A) do not change.  Being able to figure that out would be a major security problem for any cryptographic hash.

I feel like there's something I'm missing here, so if I've completely missed the point in this section, please tell me.


Computing quantity-based discounts I'm a CS professor and provided this code as a small piece of a refactoring assignment:
private double getTotalPrice(int quantity, double itemPrice) {
    if (quantity == 13) {
        return itemPrice * 12; // Baker's dozen
    }
    else if (quantity >= 6) {
        return itemPrice * quantity * .95;
    } else {
        return itemPrice * quantity;
    }
}

Students are supposed to remove inappropriate magic numbers, but, when discussing the above code with them, I realized I don't know the best way to improve the above code. I'm not interested in improving performance, just teaching how to write clean and maintainable code.
Updates
I realize there are other problems with the code, some intentional. What I am most interested in is how to name the magic numbers.
The purpose of the code is to determine the total price for an order of up to 13 items (limit in place to prevent hoarding). My priorities are readability and maintainability.

Refactoring
The first thing I'd do is remove the redundant else statements.  If you return from every branch, then there's really no need for the else clauses, they're just adding noise.
Constants?
It seems like there's some scope for constants / or lookups since there's some numbers floating around that seem to have meaning (discount amount, discount trigger threshold) etc.  If you're labelling a number with a comment (baker's dozen), it's a good indication that it could be replaced with a constant to 'name' the value.
What are you really be looking for?
However, for me, I think the code actually serves more to prompt questions about whether or not it is performing as desired.  If it is performing as expected, then it's the type of pricing system I hate (because it relies on the customer to optimize their own purchases).
If I buy 12 items, I'm charged for 12 at the discounted rate.
If I buy 13, I'm charged for 12 items at the standard rate.
If I buy 14, I'm charged for 14 at the discounted rate.  This is more expensive than me buying 13, then buying a single item as a separate transaction.
Is this correct? Are you hitting me with the postage?  Why don't I get 26 for the price of 24?
etc...
Constants Revisited
I think some of the above contribute to your difficulty coming up with constants... I'd go with something like this:
private static double getTotalPrice(int quantity, double itemPrice) {
    if (quantity == SPECIAL_ONE_OFF_DISCOUNT_QUANTITY) {
        return itemPrice * (SPECIAL_ONE_OFF_DISCOUNT_QUANTITY - 1);
    }
    if (quantity >= TRIGGER_DISCOUNT_QUANTITY) {
        return itemPrice * quantity * DISCOUNT_MULTIPLIER;
    }
    return itemPrice * quantity;
}

I'm using 'SPECIAL_ONE_OFF_DISCOUNT_QUANTITY', because it really is a special one off amount, with the current logic.  It doesn't duplicate at 26 etc.  I've got rid of the '12' constant, because really it's just 1 less than the trigger amount.  Having a 'ONE_OFF_DISCOUNTTED_QUANTITY' constant might make sense if you could see the need to pay for 10 when you bought 13 for example, however this seems a it unnecessary.
As I said, I'd prefer to rework the logic so that you always pay the lowest amount + so that discounts are additive.  This changes the output prices, so obviously wouldn't be possible if it didn't actually make sense to the client.  It does allow some of the constants to have different names though:
private static double getTotalPrice(int quantity, double itemPrice) {
    var chargeableQuantity = quantity - quantity / BUY_X_GET_ONE_FREE_QUANTITY;
    var valueMultiplier = chargeableQuantity >= TRIGGER_DISCOUNT_QUANTITY ? DISCOUNT_MULTIPLIER : 1;

    return itemPrice * chargeableQuantity * valueMultiplier;
}

I think 'BUY_X_GET_ONE_FREE_QUANTITY' is a better name than 'SPECIAL_ONE_OFF_DISCOUNT_QUANTITY', but it only really makes sense if buying twice the amount results in twice the discount...


Printing a sequence of numbers using two alternating threads I have written a program which creates a 2 new thread and shares a common lock object to print numbers alternatively. Wanted to know if the approach for using wait() and notify() is correct?

Main Class

public class MyMain {
public static void main(String[] args) {
MyThread1 obj = new MyThread1();
Thread thread1 = new Thread(obj);
Thread thread2 = new Thread(obj);

thread1.setName("t1");
thread2.setName("t2");

thread1.start();
thread2.start();

}
}

Thread Class

public class MyThread1 implements Runnable{
int i = 0;
@Override
public synchronized void run() {
    while(i<10)
    {
        if(i%2==0)
        {
try{
                notify();
                System.out.println(Thread.currentThread().getName()+" prints "+i);
                i++;
                wait();

             }catch(Exception e){ e.printStackTrace(); }
        }else
        {
            try{
                notify();
                System.out.println(Thread.currentThread().getName()+" prints "+i);
                i++;
                wait();
            }catch(Exception e){ e.printStackTrace(); }
        }
    }
}
}

Can there be a better usage of wait() and notify() instead of using it in both the if conditions?

I'm not sure what you expect from writing an if-else construct where both the if and the else block contain exactly the same code. Your run() method is effectively equivalent to the following:

public synchronized void run() {
    while (i < 10) {
        try {
            notify();
            System.out.println(Thread.currentThread().getName() + " prints " + i);
            i++;
            wait();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Other than that, your usage of notify() and wait() looks fine. However, there is a phenomenon called a "spurious wakeup", which means that a thread can be awakened for no apparent reason at all. This is very unlikely, but theoretically, it is possible that one of your two threads is spuriously woken up after it enters the waiting state but before the other thread acquires the lock on obj, which could result in one thread printing two consecutive numbers if the thread that was spuriously woken up re-acquires the lock. You might take a look at this.

Also, your program never terminates. You can rectify this by calling notify() or notifyAll() after the while loop.


Simple calculator using eval The following code is for a calculator made in ruby, I find that this way saves much time than having to build this calculator from scratch, especially that I want it to support BEMDAS operations. However, I'm feeling that it is inefficient because I'm using eval, and I think this could be dangerous.
Is it a good idea to use this in a real life application?

include Math
puts "enter an expression:"
input =  gets.chomp
begin
    result = eval(input)
    if (result.is_a? Numeric)
        puts result
    else
        puts "syntax error"
    end
rescue Exception
end

I do not know Ruby, but from my Python knowledge, it is not good to use eval in a real program.  When you use eval, it executes the code directly, so accidental/experimental input can have unwanted results, or even destroy the system.  Also, this has the potential for a hacker who has limited access to the system to run this program and do whatever they want as long as they have access to it, instead of cracking in deeper and doing whatever they are trying to do.

See this question for a detail discussion about eval in Ruby.

This question is about python, but also has good points.


Program to display a matrix in a spiral form I found an interview question which requires us to print the elements of the matrix in a spiral order starting from the top left. I need some pointers on how to improve my code:

#include <stdio.h>

//function that prints a row from startx,starty to endy
void printRow(int arr[][4],int startx,int starty,int endy)
{
    int yCtr;
    for(yCtr = starty; yCtr <= endy ; yCtr ++)
       printf("%d ",arr[startx][yCtr]);
}

//function that prints a row from startx,starty to endy (decreasing columns)
void printRowBackward(int arr[][4],int startx,int starty,int endy)
{
    int yCtr;
    for(yCtr = starty; yCtr >= endy ; yCtr --)
       printf("%d ",arr[startx][yCtr]);
}

//function that prints a column from startx,starty to endx
void printColumnBackward(int arr[][4],int startx,int starty,int endx)
{
   int xCtr;
    for(xCtr = startx; xCtr >= endx; xCtr --)
       printf("%d ",arr[xCtr][starty]);
}

// column backwards
void printColumn(int arr[][4],int startx,int starty,int endx)
{
    int xCtr;
    for(xCtr = startx; xCtr <= endx; xCtr ++)
       printf(" %d ",arr[xCtr][starty]);
}

// prints a section of the spiral
void printSpiralSection(int arr[][4],int startx,int starty,int size)
{
   printRow(arr,startx,starty,size - 1);
   printColumn(arr,startx + 1 ,size - 1 ,size -1);
   printRowBackward(arr,size - 1,size - 2,starty);
   printColumnBackward(arr,size - 2,starty,startx + 1);
}

int main()
{
    int array[4][4] = { 22 ,323,2342,222,
                          2,234,243,333,
                          21,13,23,444,
                          223,234,231,234};

    int startx =0, starty = 0, size = 4;
    // prints each section of the spiral ...
    while(size >=1) {
       printSpiralSection(array,startx,starty,size);
       size --;
       startx++;
       starty++;
    }
    getchar();
    return 0;
}

I would test it with a bigger array.  Since I created one to test it, I might as well post it here.  I put the numbers in the order I expected them to be printed, which makes checking easier.

const int array[][ARR_SIZE] = {
    { 1,   2,  3,  4,  5,  6,  7,  8,  9 },
    { 32, 33, 34, 35, 36, 37, 38, 39, 10 },
    { 31, 56, 57, 58, 59, 60, 61, 40, 11 },
    { 30, 55, 72, 73, 74, 75, 62, 41, 12 },
    { 29, 54, 71, 80, 81, 76, 63, 42, 13 },
    { 28, 53, 70, 79, 78, 77, 64, 43, 14 },
    { 27, 52, 69, 68, 67, 66, 65, 44, 15 },
    { 26, 51, 50, 49, 48, 47, 46, 45, 16 },
    { 25, 24, 23, 22, 21, 20, 19, 18, 17 },
};

Define ARR_SIZE at the top to 9 and replace each explicit 4 (apart from those in the array of course) with ARR_SIZE. Make each function static and each array parameter const.

Having done this I found that it really does work :-)

Each of your for-loops would be better written:

for (int y = starty; y <= endy; y ++) {
   printf("%d ", arr[startx][y]);
}

Notice that I defind the loop variable within the loop and called it y
instead of yCtr (the Ctr was just noise) and added some spaces. Note that it is normal to put a space after a comma (applies everywhere in your code - your use of spaces is occasionally inconsistent).  I prefer start_x to startx and print_row to printRow,  but that it just personal preference.

Also, a minor point, as the functions are named printRow and printColumn etc, it might be more natural to express the parameters in terms of rows and columns instead of x and y:

static void printRow(const int arr[][ARR_SIZE], int row, int col, int end_col)
{
    for (; col <= end_col ; ++col) {
       printf("%d ", arr[row][col]);
    }
}

The main loop would normally be expressed as a for-loop

int startx = 0;
int starty = 0;
for (int size = ARR_SIZE; size >= 1; --size) {...

Note that I defined the two start variables on separate line - again this is considered best practice.

Final point, your comments are mostly noise.


Robustness of this first difference function Here is a first difference function I threw together for a quick check in another program:

use std::ops::Sub;

fn first_difference<T>(input: &Vec<T>) -> Vec<T::Output>
    where T: Sub<Output = T> + Clone {

    let vec_len = input.len();

    input.iter().take(vec_len-1).enumerate().map(|(ind, val)| {
            val.clone() - input[ind+1].clone()
    }).collect()
}

Some things that I'm not happy with are:

Indexing the input while iterating over itself (I could use .chunks(2) but I need to visit each non-first non-last item twice)
Cloning each value inside the map (I couldn't make the trait annotation work for &T)

I also don't know if the function needs more machinery to protect against unexpected inputs (I'm not very experienced with strongly typed languages).

What can or should be done with this function?

Rustfmt is a tool for automatically formatting Rust code to the community-accepted style. Specifically, the { after the where should come on the next line.
Accept a &[T] instead of a &Vec<T>.

use std::ops::Sub;

fn first_difference<T>(input: &[T]) -> Vec<T::Output>
    where T: Sub<Output = T> + Clone
{
    let vec_len = input.len();

    input.iter()
        .take(vec_len - 1)
        .enumerate()
        .map(|(ind, val)| val.clone() - input[ind + 1].clone())
        .collect()
}

fn main() {
    println!("{:?}", first_difference(&[1, 3, 1]));
}

However, this code will panic if presented with an empty input slice because it tries to subtract 1 from 0. This can be addressed by using some iterator adapters:

fn first_difference<T>(input: &[T]) -> Vec<T::Output>
    where T: Sub<Output = T> + Clone
{
    let a = input.iter();
    let b = input.iter().skip(1);

    a.zip(b).map(|(a, b)| a.clone() - b.clone()).collect()
}

The Clone requirement is a little sad to have. You could adjust the bounds to work directly on references. This uses higher-ranked trait bounds (for <'a>):

fn first_difference<T>(input: &[T]) -> Vec<T>
    where for <'a> &'a T: Sub<Output = T>
{
    let a = input.iter();
    let b = input.iter().skip(1);

    a.zip(b).map(|(a, b)| a - b).collect()
}

I think the biggest "weakness" to the function is not one of its own. In Rust, subtraction may panic in certain cases. Specifically, when you exceed the range of the type, the compiler may abort the program. This can be controlled by the programmer, depending on the constraints of the problem at hand .

  Why doesn't the compiler complain about that lifetime specifier being
  undefined? The Rustonomicon says

    for<'a> can be read as "for all choices of 'a", and basically produces an infinite list of trait bounds that F must satisfy.
    Intense.

  which I agree is intense, but doesn't seem to tell me what the
  lifetime is. Is it the lifetime of F, or is it bounded in some other
  way externally?

for <'a> declares a new generic lifetime, that's why there's no compilation error. The quote from the Nomicon is fairly literal (as far as it can be) — the restriction in the where clause here is "any possible reference to a T needs to be able to be subtracted from another reference to a T. Those two references will share a unified lifetime 'a and the result of the subtraction will produce a T".

It's certainly a mouthful, but it's not impossible to understand once you've seen it a few times.

Specifically, the concrete lifetime will be the same as the incoming slice. This means I was probably being a over-clever, and the code could have been written as:

fn first_difference<'a, T>(input: &'a [T]) -> Vec<T>
    where &'a T: Sub<Output = T>
{
    let a = input.iter();
    let b = input.iter().skip(1);

    a.zip(b).map(|(a, b)| a - b).collect()
}


Verifying private class members in Unit Testing This code is an academic example. I was trying to write something easy because the domain is not important but the principles and best practices.

In this code, I have a class - Table. It has a private array (of objects Cell), which is used by many public functions in the code but there is no function that will return a particular cell. So the problem I have, is how can I test the Reset function? I can call this function but I can't review its result especially with the Option 2 where I don't have any references to this array.

That got me thinking if the design is correct.. and that lead me here.

My questions are:

Do I violate any SOLID principle?
Is the option 2 better way to go? (although in that case, there's no way to test it

Here's the code:

public class Cell
{
    public int X { get; set; }
    public int Y { get; set; }
    public string Value { get; set; }
}

public class Table
{
    private Cell[,] Cells { get; }
    public Table(Cell[,] cells)
    {
        Cells = cells;
    }

    public void SetCell(int x, int y, string value)
    {
        Cells[x, y].Value = value;
    }

    public void Reset()
    {
        for (int i = 0; i < Cells.GetLength(0); i++)
        {
            for (int j = 0; j < Cells.GetLength(1); j++)
            {
                Cells[i, j].Value = "";
            }
        }
    }

    public bool AreNeighborCellsSet(int x, int y)
    {
        bool areNeighborCellsSet = false;

        // checking...

        return areNeighborCellsSet;
    }
}

Option 2:

public class Table
{
    private Cell[,] Cells { get; }

    public Table(int height, int width, ICellFactory cellFactory)
    {
        Cells = new ICell[height, width];
        for (int i = 0; i < Cells.GetLength(0); i++)
        {
            for (int j = 0; j < Cells.GetLength(1); j++)
            {
                Cells[i, j].Value = cellFactory.Create(i, j);
            }
        }
    }

    // Rest is the same
}

how can I test Reset function? I can call this function, but I can't review its result. Specially with the Option 2 where I don't have any references to this Array.

You always test only public APIs so you need to verify the results of the many public functions whether they behave they way you expect them after resetting the table.

They are your contract and their expected results you need to verify.

  Is the option 2 better way to go? (although in that case, there's no way to test it

There is, the public APIs. If the initialization didn't work correctly you will get invalid results from them.

  I don't have any references to this Array

This is an internal detail that could change at any time. You don't test it. You test the public contract that you usually must not change.


Unique_Ptr Implementation I have Implemented Unique_Ptr with move semantics for the sake of Learning. Any suggestions, feed backs are highly appreciated.

// author @asad_nitp
#pragma once

namespace Smart_Pointers {
template<typename T>

class Unique_Ptr {
    T* m_ptr;
public:
    explicit Unique_Ptr(T* ptr = nullptr) noexcept
        : m_ptr(ptr)
    {}

    ~Unique_Ptr() noexcept {
        if (m_ptr != nullptr) {
            delete m_ptr;
        }
        m_ptr = nullptr;
    }

    Unique_Ptr(const Unique_Ptr&) = delete;
    Unique_Ptr& operator = (const Unique_Ptr&) = delete;

    Unique_Ptr(Unique_Ptr&& ob) noexcept {
        m_ptr = ob.m_ptr;
        ob.m_ptr = nullptr;
    }
    Unique_Ptr& operator = (Unique_Ptr&& ob) noexcept {
        if (this != &ob) {
            m_ptr = ob.m_ptr;
            ob.m_ptr = nullptr;
        }
        return *this;
    }

    T* operator -> () const noexcept {
        return m_ptr;
    }

    T& operator * () const {
        return *m_ptr;
    }

    T* get() const noexcept{
        return m_ptr;
    }

    T* release() noexcept {
        T* ans = m_ptr;
        m_ptr = nullptr;
        return ans;
    }

    void reset(T* ptr = nullptr) noexcept {
        T* old = m_ptr;
        m_ptr = ptr;
        if (old != nullptr)
            delete old;
    }

    void swap(Unique_Ptr& ob) noexcept {
        using std::swap;
        swap(m_ptr,ob.m_ptr);
    }

 };
}
  //Examples
  int main() {
     Smart_Pointers::Unique_Ptr<int> up1(new int(5));
     Smart_Pointers::Unique_Ptr<int> up2(new int(6));
     up1 = up2; // Error
     up1 = std::move(up2); //fine

     return 0;
   }

As mentioned in the original comment you leak on assignment:

Unique_Ptr<int>   a = new int(1);
Unique_Ptr<int>   b;

a = b;  // You leak the original a pointer.

Looking at the assignment operator:

Unique_Ptr& operator = (Unique_Ptr&& ob) noexcept {
    if (this != &ob) {
        m_ptr = ob.m_ptr;     // Here you overwrite the current value.
                              // and thus leak its original value.
        ob.m_ptr = nullptr;
    }
    return *this;
}

As mentioned in the comments the standard way of implementing move semantics is:

Unique_Ptr(Unique_Ptr&& ob) noexcept
    : m_ptr(nullptr)
{
    swap(ob);
}
Unique_Ptr& operator = (Unique_Ptr&& ob) noexcept
{
    swap(ob);
    return *this;
}

This has a couple of benefits. Calling the destructor is not required. You are moving the actual data to the other object. Thus means the destructor of the other object will correctly handle destruction.

This also potentially allows for re-use. If the ob is in some other context and you the object could be re-used this can help in optimizations. If it can not be-reused it will correctly be deleted.

You remove the pesimizing check for self assignment.

You don't have a conversion too bool.

if (a) {
    // A is holding a value you can do stuff with it.
}

// Now you can do
if (a.get()) {
    // A is holding a value you can do stuff with it.
}
// But its not as neat. And the context changes.

This is simply fixed with:

// Note the explicit (added in C++11) to replace the safe-bool idiom
explicit operator bool() {
    return m_ptr;
}

Can you guarantee that the destructor of type T does not throw?

void reset(T* ptr = nullptr) noexcept;

I think not. I agree it should be but that is not something you can guarantee and thus your code should not guarantee that it does not. So this should probably be:

void reset(T* ptr = nullptr);

You can probably do some meta-programming to determine if the destructor is noexcept but I don't have that in my head.

Don't mark your destructor as noexcept.

~Unique_Ptr() noexcept; // this is not needed.
                        // Destructors are automatically noexcept

Your destructor is automatically noexcept unless specific conditions are met so the compiler will work it out correctly for you.


Parallel class for javascript promises I created a class to run a certain number of tasks in parallel in the browser.  The constructor takes an array of inputs, a function that takes a single input and returns a promise, and a count of the number of tasks to run in parallel.  This is for doing some web scraping so I don't want to create a hundred ajax requests and wait for them to all complete with Promise.all, besides worrying about a timeout or failure I don't want to thrash the connections to a server (jsfiddle):

// run 5 at a time, calling func on each element of delays array
let par = new Parallel(delays, func, 5);
par.run().then(results => { ... });

It runs all the items and resolves if there were no errors, or rejects if there were any errors.  The results array contains each result or error from a reject.  Is there a better way?

class Parallel {

  constructor(inputs, func, count) {
    this.inputs = inputs;
    this.func = func;
    this.count = count;
    this.index = 0;
    this.active = 0;
    this.enabled = true;
    this.hadError = false;
  }

  cancel() {
    this.enabled = false;
  }

  run() {
    this.start = performance.now();

    return new Promise( (resolve, reject) => {
      this.results = [];

      let checkDone = () => {
        if (this.active === 0 && (this.index >= this.inputs.length || (!this.enabled))) {
          this.end = performance.now();
          if (this.hadError)
            reject(this.results);
          else
            resolve(this.results);
          return true;
        }
      }

      let setAndCheck = (index, result) => {
        this.active--;
        this.results[index] = result;
        queue();
      }

      let handleOne = (index, input) => {
        this.active++;
        this.func(input)
        .then(result => setAndCheck(index, result))
        .catch(err => {
          this.hadError = true;
          console.log('Error with input:', input);
          console.error(err);
          setAndCheck(index, err);
        });
      }

      let queue = () => {
        if (checkDone()) return;
        while (this.enabled && (this.active < this.count) && this.index < this.inputs.length) {
          let index = this.index;
          let input = this.inputs[index];
          this.index = this.index + 1;
          handleOne(index, input);
        }
      }

      queue();
    });
  }
}

let totalDelay = 0;
let func = (delay) => new Promise(resolve => setTimeout(() => resolve(delay), delay));
let delays = [];
for (var i = 0; i < 20; i++) {
 let d = Math.random() * 1000 + 500;
 delays.push(d);
  totalDelay += d;
}

let start = performance.now();
let par = new Parallel(delays, func, 5);
par.run().then(results => {
 var total = results.reduce((acc, val) => acc + val, 0);
  var actual = performance.now() - start;
  document.body.innerHTML = `

totalDelay: ${totalDelay.toFixed(2)}

actual: ${actual.toFixed(2)}

`;
});

I created a class to run a certain number of tasks in parallel in the browser.

Unless you're using web workers, in JS, nothing actually runs in parallel. The external processes (file reads, network requests, etc) may be running in parallel after spawning them, but JS still launches and completes in some sequence, asynchronously.

  It runs all the items and resolves if there were no errors, or rejects if there were any errors.

Sounds like you're looking for Promise.all. It takes an array of promises, and resolves if all of them resolve or rejects if any one of them rejects.

Now I've seen code that's eerily similar to this one, and I tell you it's a pain to debug. You have a bunch of functions depending on counters "flag properties" that alter how the functions work. Since async doesn't guarantee order, the values aren't guaranteed, therefore how the function runs is also not guaranteed. This then makes your queue hard to test and you end up doing "hope-driven development" - a project devoid of unit tests.

Hopefully I've scared you, since I don't ever want to see queueing done this way. Makes you lose hair. What I suggest you do is just take in an array of inputs, recursively work on them by chunks, concatenate the results and hand it over. No counters, no flags.

Here's a simple, no-cancel version of the queue. It launches the queue chunkSize at a time. Then it launches the rest of the array, up until the array is exhausted. Then the chunks are concatenated. All you need for inputs are functions that return promises. How you construct them or feed them input is up to you, not the queue. Below shows how to use closures. Alternatively, you can use bind.

const launchQueue = (q, chunkSize) => {
  // No more items, resolve with an empty array
  if (!q.length) return Promise.resolve([]);

  // Slice the array
  const chunk = q.slice(0, chunkSize);
  const remain = q.slice(chunkSize);

  // Call each function and store the promises returned to an array.
  // Promise.all fails fast. Catch errors and resolve with those.
  const chunkPromises = chunk.map(f => f.call().then(r => r, e => e));

  // Wait for all to resolve
  return Promise.all(chunkPromises).then(r => {

    // Run the remaining items
    return launchQueue(remain, chunkSize).then(s => {

      // Concat results.
      return r.concat(s);
    });
  });
}

// For each input, create a function that returns a promise that
// that resolves when the operation completes.
const queue = [9000, 7000, 4000, 5000, 8000, 1000, 3000, 2000, 4000, 6000].map(n => {
  return () => new Promise(r => {
    console.log(`fn with ${n} requested`);
    setTimeout(() => {
      console.log(`fn with ${n} resolved`);

      // Prove that whatever we resolve here ends up in the
      // call below.
      r(-n);
    }, n);
  });
});

// Hand over the functions to the queueing function and wait for
// the results.
launchQueue(queue, 2).then(r => console.log(r));

An async-await version is much more readable:

const launchQueue = async (q, chunkSize) => {
  if (!q.length) return [];

  const chunk = q.slice(0, chunkSize);
  const remain = q.slice(chunkSize);
  // The then is much more concise than a try-catch.
  const chunkPromises = chunk.map(f => f.call().then(r => r, e => e));
  const chunkResults = await Promise.all(chunkPromises);
  const remainResults = await launchQueue(remain, chunkSize);
  return chunkResults.concat(remainResults);
}

// For each input, create a function that returns a promise that
// that resolves when the operation completes.
const queue = [9000, 7000, 4000, 5000, 8000, 1000, 3000, 2000, 4000, 6000].map(n => {
  return () => new Promise(r => {
    console.log(`fn with ${n} requested`);
    setTimeout(() => {
      console.log(`fn with ${n} resolved`);

      // Prove that whatever we resolve here ends up in the
      // call below.
      r(-n);
    }, n);
  });
});

// Hand over the functions to the queueing function and wait for
// the results.
launchQueue(queue, 2).then(r => console.log(r));


Using delegates to avoid duplicate creation of resources I'm writing a PCL that uses an HttpClient to go visit a few sites and extract data from them. My initial code looked like this:

public static class Download
{
    public async static Task<byte[]> FromYouTubeAsync(string videoUri)
    {
        using (var client = new HttpClient())
        {
            string source = await client
                .GetStringAsync(videoUri);

            // get links...

            return await client
                .GetByteArrayAsync(links.First());
        }
    }
}

I realized, however, that this would be a waste of resources if the user of my library already had a HttpClient in hand. For example:

// Caller code
using (var client = new HttpClient())
{
    // Do some work with client

    byte[] bytes = await Download.FromYouTubeAsync("some://uri"); // A second HttpClient is created here, wasting resources and time...

    // Do some work with client and bytes
}

One solution could be to add an overload taking an HttpClient as a parameter, but what if the user wanted to use a WebClient instead? Or an HttpWebRequest? Or some other kind of client that wasn't availsble in the PCL?

My solution

I decided to take delegate parameters to get the page source and to download the file based on the URI. My code now looks like this:

public static class Download
{
    public async static Task<byte[]> FromYouTubeAsync(string videoUri)
    {
        using (var client = new HttpClient())
        {
            return await FromYouTubeAsync(
                () => client
                .GetStringAsync(videoUri),
                uri => client
                .GetByteArrayAsync(uri));
        }
    }

    public async static Task<byte[]> FromYouTubeAsync(
        Func<Task<string>> sourceFactory, Func<string, Task<byte[]>> downloadFactory)
    {
        string source = await sourceFactory();

        // get links...

        return await downloadFactory(links.First());
    }
}

The problem

Hm. Wait, what if the caller is using a client that doesn't support async, like HttpWebRequest? Better add another overload taking a Func<string> and a Func<string, byte[]>. What if s/he wants to make the first call synchronous, but the second call async? Or vice versa? OK, just add 2 more overloads. Wait, what if the caller wants the whole operation to be synchronous? Let's go add 4 Download.FromYouTube overloads wrapping each of the async methods. Whoops, it turns out we need to visit another page of YouTube in case the video's signature is encrypted! Sure, let's go add 8 mor-

I think you can see where this is going. How do I maintain this flexibility without scaring the user away when Visual Studio says that there are 17 different overloads for this method?

The problem here is that you want to be able to use a large number of unrelated objects (i.e. not implementing a common interface).  One solution would be to define a usable interface and define wrapper implementations for each of these objects.  Something like:

public interface IDataSource
{
    byte[] DownloadUrl(String url);
}

Your download class would use implementations of this interface, and you could provide implementations for HttpClient, WebClient, etc. like:

public class HttpClientDataSource : IDataSource
{
    public HttpClientDataSource(HttpClient client){}
}

All that said, this doesn't seem to really matter in your case.  I'm not convinced that allocating an HttpClient for internal use is exactly wasteful of resources.  Also, by forcing this decision onto the users of your library you've made it more complicated to use.  You'll have to explain to your users how to choose between different HTTP implementations.  Part of designing a good library is trading off flexibility and simplicity, and I would say the simpler interface is better.


How Long Will Your Smartphone Distract You From Family Dinner? I wrote a program to simulate this week's 538 Riddler, reproduced below:

  You’ve just finished unwrapping your holiday presents. You and your
  sister got brand-new smartphones, opening them at the same moment. You
  immediately both start doing important tasks on the Internet, and each
  task you do takes one to five minutes. (All tasks take exactly one,
  two, three, four or five minutes, with an equal probability of each).

  After each task, you have a brief moment of clarity. During these, you
  remember that you and your sister are supposed to join the rest of the
  family for dinner and that you promised each other you’d arrive
  together. You ask if your sister is ready to eat, but if she is still
  in the middle of a task, she asks for time to finish it. In that case,
  you now have time to kill, so you start a new task (again, it will
  take one, two, three, four or five minutes, exactly, with an equal
  probability of each). If she asks you if it’s time for dinner while
  you’re still busy, you ask for time to finish up and she starts a new
  task and so on.

  From the moment you first open your gifts, how long on
  average does it take for both of you to be between tasks at the same
  time so you can finally eat? (You can assume the “moments of clarity”
  are so brief as to take no measurable time at all.)

And the program itself:

private static int numberOfSimulations = 100000;
static void Main(string[] args)
{
    var rand = new Random();
    var simulationTimes = new List<int>();
    for (int i = 0; i < numberOfSimulations; i++)
    {
        var totalTime = 0;
        var myTaskTime = rand.Next(1, 6);
        var herTaskTime = rand.Next(1, 6);

        do
        {
            if (herTaskTime > myTaskTime)
            {
                totalTime += myTaskTime;
                herTaskTime -= myTaskTime;
                myTaskTime = rand.Next(1, 6);
            }
            else if (herTaskTime < myTaskTime)
            {
                totalTime += herTaskTime;
                myTaskTime -= herTaskTime;
                herTaskTime = rand.Next(1, 6);
            }
            else
            {
                totalTime += myTaskTime;
            }
        } while (myTaskTime - herTaskTime != 0);

        simulationTimes.Add(totalTime);
    }
    Console.WriteLine(simulationTimes.Average());
    Console.ReadLine();
}

Anecdotally, I'm consistently getting ~7.5 minutes.

I'm just looking for a general code review - does this look correct? Am I doing anything dumb? Should I have done it differently?

There's definitely an issue that will occur when a new task comes up with the same amount of time as what is left on the other person's task. Take for example the times.

MyTime | HerTime
----------------
3      | 5

Now the first loop occurs, HerTime gets reduced to 2, TotalTime gets set to 3, then MyTime gets rerolled to 2. Now, your while condition hits as MyTime = HerTime and it breaks out, but those 2 minutes were never accounted for.

An easy fix would be to add a guard condition to your while that gets set in the Else part of your If.

(Warning, the below changes are untested air code)

private static int numberOfSimulations = 100000;
static void Main(string[] args)
{
    var rand = new Random();
    var simulationTimes = new List<int>();
    for (int i = 0; i < numberOfSimulations; i++)
    {
        var totalTime = 0;
        var myTaskTime = rand.Next(1, 6);
        var herTaskTime = rand.Next(1, 6);
        var equal = false;

        do
        {
            if (herTaskTime > myTaskTime)
            {
                totalTime += myTaskTime;
                herTaskTime -= myTaskTime;
                myTaskTime = rand.Next(1, 6);
            }
            else if (herTaskTime < myTaskTime)
            {
                totalTime += herTaskTime;
                myTaskTime -= herTaskTime;
                herTaskTime = rand.Next(1, 6);
            }
            else
            {
                totalTime += myTaskTime;
                equal = true;
            }
        } while (!equal);

        simulationTimes.Add(totalTime);
    }
    Console.WriteLine(simulationTimes.Average());
    Console.ReadLine();
}


Beginner Coin Flip project I think I finally finished a small coin flip project I found online. However, I'm pretty confident this is far from the optimal solution and would really appreciate any feedback on how this could be improved. Since I'm studying by myself using Head First and Code Academy any feedback would be very very helpful!

The goals of the challenge are:

As a user I want to be able to guess the outcome of a random coin flip (heads/tails).
As a user I want to clearly see the result of the coin flip.
As a user I want to clearly see whether or not I guessed correctly.
As a user I want to clearly see the updated guess history (correct count/total count).
As a user I want to be able to quit the game or go again after each cycle.

This is my first time really using GitHub, but I included the .py file which hopefully you can access here.

import random

def random_flip(): #function to generate random Heads or Tails output

    random_choice = random.choice(["Heads","Tails"])
    return random_choice

def user_choice(): #function to ensure a valid input from the user, and returns that input.

    user_input = ""
    valid_guesses = ["Heads", "Tails"]

    while user_input not in valid_guesses:
        user_input = input("Heads or Tails?")

    return user_input

def coin_flip_game(): #function that plays the coin flip game.

    guess_count = 1  #guesses set to 1 so that program considers 1st guess.
    guesses = []     #list of guesses made by user
    winner = False
    first_try = True      #Variable to determine whether first try of user or not
    cancel_game = False   #Variable to determine whether game was cancelled

    print("Lets start! Begin by choosing:")

    while winner == False:
        if first_try == True:
            user_input = user_choice()

            if user_input != random_flip():
                guess_count += 1
                guesses.append(user_input)
                first_try = False
            else:
                winner = True
        else:
            decision = input("You guessed wrong, do you want to continue? Yes or No ")

            if decision == "Yes":
                user_input = user_choice()

                if user_input != random_flip():
                    guess_count += 1
                    guesses.append(user_input)
                    first_try = False
                else:
                    winner = True
            else:
                winner = True
                cancel_game = True
                break

    if cancel_game == True:
        print("Game over")
    elif guess_count == 1:
        print("Congratulations, you guessed correctly on your first try!")
    else:
        print("Congratulations! After ", guess_count, "you guessed correctly!")
        print("Your previous guesses were: ", guesses)

coin_flip_game()

After getting user input, you check it by doing decision == "Yes". This is pretty exact text to expect from the user. I'd at least upper-case their input, and unless you really needed them to be specific, only keep the first letter:

decision = input("You guessed wrong, do you want to continue? Yes or No ")
std_decision = decision[:1].upper()  # [:1] discards all but the first letter

if std_decision == "Y":
   . . .

In coin_flip_game you have

guess_count = 1  #guesses set to 1 so that program considers 1st guess

Then later:

if user_input != random_flip():
    guess_count += 1
    guesses.append(user_input)
    first_try = False
else:
    winner = True

You're only increasing guess_count if the guess was wrong. Regardless of if they were right or wrong though, they still made a guess. I think it makes more sense to add to the guess_count regardless, and start it at 0.

But then you're also only adding to guesses on wrong answers too. If you change it to append to guesses on both right and wrong answers, you'll have this:

guess_count = 0

. . .

guess_count += 1
guesses.append(user_input)

if user_input != random_flip():
    first_try = False

else:
    winner = True

Notice now though that guess_count will always be equal to the length of guesses, so it isn't needed. If you need to find out how many guesses were made, you can just do len(guesses). first_try also isn't necessary. To check if it was their first guess or not, you can do:

if len(guesses) == 0:
    . . .

Or, more idiomatically:

if not guesses:  # "If no(t) guesses (have been made)"
    . . .

I think that whole game loop part should be taken out into it's own function though; beyond what you've already done. I'd have a function that returns a list of guesses made until a correct guess was made. With how you have it set up now, I'm going to disregard cancelling since that will require some broader changes to accommodate, and it's highly unlikely that the user will have to guess more than a few times.

def guess_loop() -> List[str]:
    guesses = []

    while True:  # We're just going to return, so we don't need a condition
        user_input = user_choice()
        guesses.append(user_input)

        if user_input == random_flip():
            return guesses  # Returning guesses means we won

        else:
            print("You guessed wrong. Try again.")

def coin_flip_game():
    print("Lets start! Begin by choosing:")
    guesses = guess_loop()

    if len(guesses) == 1:
        print("Congratulations, you guessed correctly on your first try!")

    else:
        print("Congratulations! After", len(guesses), "you guessed correctly!")
        print("Your guesses were: ", guesses)

The bulky bit was taken out so it can be dealt with as an isolated bit of code. To know the outcome of the game, all I care about (besides cancelling, which could be handled by returning None) is the list of guesses they made until they won. I can get all the information I need from just that. Needing to mix in winner, and cancel flags can suggest that that code should be moved out. By the time you're managing two or three flags to control execution in one block of code, it can become hard to follow.

user_choice can be cleaned up too. Again, you're using a condition to control a loop when I think returning directly from the loop leads to cleaner looking code:

def user_choice():
    while True:
        user_input = input("Heads or Tails?").capitalize()  # Capitalize to give the user some leeway

        if user_input in {"Heads", "Tails"}:
            return user_input

        else:
            print("Invalid input.")

After the above and some small formatting touchups, I'm left with:

import random
from typing import List

def random_flip() -> str:
    return random.choice(["Heads", "Tails"])

def user_choice() -> str:
    while True:
        user_input = input("Heads or Tails?").capitalize()  # Capitalize to give the user some leeway

        if user_input in {"Heads", "Tails"}:
            return user_input

        else:
            print("Invalid input.")

def guess_loop() -> List[str]:
    guesses = []

    while True:  # We're just going to return, so we don't need a condition
        user_input = user_choice()
        guesses.append(user_input)

        if user_input == random_flip():
            return guesses  # Returning guesses means we won

        else:
            print("You guessed wrong. Try again.")

def coin_flip_game() -> None:
    print("Lets start! Begin by choosing:")
    guesses = guess_loop()

    if len(guesses) == 1:
        print("Congratulations, you guessed correctly on your first try!")

    else:
        print("Congratulations! After", len(guesses), "you guessed correctly!")
        print("Your guesses were: ", guesses)

coin_flip_game()

The -> bits are type hints for the return type of the function. I think they're handy to have to make it clearer what type of data is being dealt with.


Find items in a table that match a set of conditions in another table I have two tables. Table 1 has sets of EXPORT conditions: e.g., SET 1 has FOOD, GARMENT, and TECHNOLOGY, and SET 2 contains GARMENT and TECHNOLOGY.

TABLE 1
SETID       EXPORT
-----------------------
1           FOOD
1           GARMENT
1           TECHNOLOGY
-----------------------
2           GARMENT
2           TECHNOLOGY
-----------------------
3           GARMENT
3           FOOD
-----------------------
4           TECHNOLOGY
(more sets of conditions) ...

Table 2 has a list of countries with different types of exports.

TABLE 2
COUNTRY     EXPORT
-----------------------
GERMANY     AUTO
GERMANY     TECHNOLOGY
-----------------------
ITALY       FOOD
ITALY       GARMENT
-----------------------
CHINA       FOOD
CHINA       GARMENT
CHINA       TECHNOLOGY
CHINA       STEEL
-----------------------
FRANCE      FOOD
FRANCE      GARMENT
-----------------------
(more countries)...

I would like to find countries that satisfy each set of the conditions. A country satisfies a set of conditions if it meets all the conditions in a set (even if it may meet additional conditions) -- For example, CHINA satisfies SET 1 even though it also meets the additional condition STEEL.

The expected output is something like:

SET          Country
--------------------------
1            CHINA
2            CHINA
3            ITALY
3            CHINA
3            FRANCE
4            GERMANY
4            CHINA
...

Here's the query I have. It does the job, but I wonder if there is a way to make it perform better. Currently, when Table 1 has 5000 rows (approx. 600 sets of conditions), and Table 2 has 6 million rows, it takes 15 minutes to get the output.

WITH TEMP AS (  SELECT   SETID, COUNTRY, COUNT(*) AS TOTALCOUNT
                  FROM   #TABLE1 AS T1
                  JOIN   #TABLE2 AS T2 ON T2.EXPORT = T1.EXPORT
              GROUP BY   SETID, COUNTRY
              )
      SELECT  TEMP.SETID, COUNTRY
        FROM  TEMP
        JOIN  (  SELECT  COUNT(*) AS TOTALCOUNT, SETID
                   FROM  #TABLE1
               GROUP BY  SETID
              ) AS TEMP2 ON  TEMP.TOTALCOUNT = TEMP2.TOTALCOUNT AND TEMP.SETID = TEMP2.SETID
    ORDER BY  TEMP.SETID

Code for generating sample tables:

CREATE TABLE #TABLE1 (SETID INT, EXPORT NVARCHAR(MAX))
INSERT INTO #TABLE1(SETID, EXPORT)
VALUES (1, 'FOOD'), (1, 'GARMENT'), (1, 'TECHNOLOGY'), (2, 'GARMENT'),
       (2, 'TECHNOLOGY'), (3, 'GARMENT'), (3, 'FOOD'), (4, 'TECHNOLOGY');

CREATE TABLE #TABLE2 (COUNTRY NVARCHAR(MAX), EXPORT NVARCHAR(MAX))
INSERT INTO #TABLE2(COUNTRY, EXPORT)
VALUES ('GERMANY', 'AUTO'), ('GERMANY', 'TECHNOLOGY'), ('ITALY', 'FOOD'),
       ('ITALY', 'GARMENT'), ('CHINA', 'FOOD'), ('CHINA', 'GARMENT'),
       ('CHINA', 'TECHNOLOGY'), ('CHINA', 'STEEL'), ('FRANCE', 'FOOD'),
       ('FRANCE', 'GARMENT');

This is the standard logic to find subsets, but 15 minutes for two not really big tables is really a lot.

The join might return a huge result intermediate set (it's a m-n-join), you can check it using:

SELECT COUNT(*)
FROM   #TABLE1 AS T1
JOIN   #TABLE2 AS T2 ON T2.EXPORT = T1.EXPORT

Your query can be simplified a bit using a Group Count before the join:

WITH cte AS
 (
   SELECT *,
      COUNT(*) OVER (PARTITION BY SETID) AS cnt
   FROM #TABLE1
 )
SELECT SETID, COUNTRY
FROM cte
JOIN #TABLE2 AS T2
  ON T2.EXPORT = cte.EXPORT
GROUP BY SETID, COUNTRY
HAVING COUNT(*) = MAX(cte.cnt)
ORDER BY SETID

But I don't expect this to improve runtime (unless the optimizer did a very stupid plan before)

Edit:

As expected, most of the runtime is caused by the huge number (1,500,000,000) of rows in the intermediate result set. For a similar problem (exactly matching two sets) I used a solution based on joining comma-delimited strings of all values in a group (which was very efficient on a Teradata system). This logic can be modified for subsets, but I don't really know about efficiency.

This is the algorithm:

For each country create a comma-delimited list like this:

,FOOD,,GARMENT,,STEEL,,TECHNOLOGY,

For each set create a comma-delimited list like this:

%,GARMENT,%,TECHNOLOGY,%

And then simply join using a LIKE (the additional commas are needed to prevent matching partial values, e.g. 'TECHNO' matching 'TECHNOLOGY'):

WITH cte1 AS
 (
   SELECT SETID,
      STUFF((SELECT ',%,' + EXPORT
             FROM  #TABLE1 AS t2
             WHERE t.SETID = t2.SETID
             ORDER BY EXPORT
             FOR XML PATH('')) + ',%', 1, 1, '') AS x
   FROM #TABLE1 AS t
   GROUP BY setid
 )
,cte2 AS
 (
   SELECT COUNTRY,
      (SELECT ',' + EXPORT  + ','
       FROM  #TABLE2 AS t2
       WHERE t.COUNTRY = t2.COUNTRY
       ORDER BY EXPORT
       FOR XML PATH('')) AS x
   FROM #TABLE2 AS t
   GROUP BY COUNTRY
 )
SELECT cte1.SETID, cte2.COUNTRY
FROM cte1 JOIN cte2
ON cte2.x LIKE cte1.x
;


Recursive Fibonacci in Rust with memoization I'm trying to come up with an "elegant" way of calculating Fibonacci for number in Rust, using recursion and memoization (self-imposed requirements).

This is what I have so far:

fn fib(n: usize, memo: &mut [Option<usize>]) -> usize {
    memo[n].map(|v| v).unwrap_or_else(|| {
        let result = {
            if n > 1 {
                fib(n - 1, memo) + fib(n - 2, memo)
            } else {
                1
            }
        };
        memo[n] = Some(result);
        result
    })
}

fn main() {
    let number = 46;
    let mut memo: Vec<Option<usize>> = vec![None; number + 1];
    println!("{}", fib(number, &mut memo));
}

My cache in this implementation is just a slice of optional values, if the position contains Some(x) that's a cache hit, otherwise, in a closure, compute the value, passing the cache along, and just before returning the value save it as a Some(v) in the cache.

I figured that setting up a cache this way would make writes faster, since the memory is already allocated.

Can it be made faster? Or cleaner/more readable?

There's no reason to ascribe a type to memo.
Don't expose the memoization logic outside the call. Instead, create a shim function that creates the memoization vector for you.
You can then define the memoized function inside the shim function, preventing people from accidentally calling it.
Since the memo variable isn't used after the top-most recursive call, you can just pass in the reference directly, without creating a variable.
As mentioned in the comments, the map(|x| x) call is not needed here.
Write some kind of automated tests.

fn fib(number: usize) -> usize {
    fn fib_memo(n: usize, memo: &mut [Option<usize>]) -> usize {
        memo[n].unwrap_or_else(|| {
            let result = {
                if n > 1 {
                    fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
                } else {
                    1
                }
            };
            memo[n] = Some(result);
            result
        })
    }

    fib_memo(number, &mut vec![None; number + 1])
}

fn main() {
    let number = 46;
    let r = fib(number);
    println!("{}", r);
    assert_eq!(2971215073, r);
}

That being said, I'd point out that this memoized version of Fibonacci is not the most efficient — you don't need to keep every previous value forever. Instead, check out numerous ways of being more efficient:

Implement a generic Fibonacci sequence in Rust without using Copy trait
How to swap two variables?
How to avoid excessive cloning in Rust?
Is it possible to use a fold with a Vec?

One possible implementation of that:

fn fib(n: usize) -> usize {
    fn fib_memo(n: usize, memo: &mut [usize; 2]) -> usize {
        let [a, b] = *memo;
        let c = a + b;
        if n == 0 {
            c
        } else {
            *memo = [b, c];
            fib_memo(n - 1, memo)
        }
    }

    if n < 2 {
        1
    } else {
        fib_memo(n - 2, &mut [1, 1])
    }
}

Or a non-recursive variant:

fn fib(n: usize) -> usize {
    if n < 2 {
        1
    } else {
        let mut memo = [1, 1];
        let mut n = n - 2;

        loop {
            let [a, b] = memo;
            let c = a + b;

            if n == 0 {
                return c;
            }

            memo = [b, c];
            n -= 1;
        }
    }
}


Sieving for prime numbers I wanted to implement the Sieve of Erathosthenes up to int.MaxValue in C#. No object is allowed to exceed 2Gb so you can't allocate a bool[int.MaxValue] array. In order to solve the problem, I created a class that packs the bits into an array of bytes instead.

I know that it's possible to use a segmented sieve: this was just for 'fun'.

public class SieveOfEratosthenes
{
    private readonly int highestNumber;

    // Flags for each number are stored packed in a byte array.
    // Least significant bit is flag for 1 - by starting at 1 and not 0 we can seive to int.MaxValue
    //                             8 7 6 5 4 3 2 1
    // e.g. for highestNumber = 8: 1 0 1 0 1 0 0 1 => 1, 4, 6 and 8 have been marked non-prime.
    private readonly byte[] data;

    private SieveOfEratosthenes(int highestNumber)
    {
        if (highestNumber < 1)
        {
            throw new ArgumentOutOfRangeException(nameof(highestNumber));
        }
        this.highestNumber = highestNumber;
        var sizeRequired = (int)Math.Ceiling(highestNumber/8.0);
        data = new byte[sizeRequired];
    }

    public static SieveOfEratosthenes CreateSeive(int highestNumber)
    {
        var result = new SieveOfEratosthenes(highestNumber);
        result.Populate();
        return result;
    }

    public bool IsPrime(int number)
    {
        if (number < 0 || number > highestNumber)
        {
            throw new ArgumentOutOfRangeException(nameof(number));
        }
        // 0 not stored in byte array so we have to test separately.
        if (number == 0)
        {
            return false;
        }
        return ((data[(number-1)/8] >> (number-1)%8) & 1) == 0;
    }

    private void Populate()
    {
        for (var i = 2; i < Math.Sqrt(highestNumber); i++)
        {
            if (!IsPrime(i))
            {
                continue;
            }
            // j += i can overflow so need to guard against that in for loop.
            for (var j = i * i; j <= highestNumber && j > 0; j += i)
            {
                data[(j-1) / 8] = (byte)(data[(j-1) / 8] | (1 << ((j-1) % 8)));
            }
        }
        data[0] = (byte)(data[0] | 1); // Mark 1 as not prime.
    }
}

The algorithm for the Populate method is just from the wikipedia article with true and false the other way around, see: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode

The reason I'm using a static factory method is that I don't like constructors that do non-trivial work.

Here's a simple test harness that prints the primes under 100:

class Program
{
    static void Main(string[] args)
    {
        var sw = Stopwatch.StartNew();
        var sieve = SieveOfEratosthenes.CreateSeive(100);
        sw.Stop();
        Console.WriteLine(string.Join(", ", Enumerable.Range(0, 100).Where(sieve.IsPrime)));
        Console.WriteLine("Took {0}ms", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }
}

On my machine it takes about 20 seconds to seive to int.MaxValue which takes just over 250mb of memory (roughly int.MaxValue/8 bytes).

Any room for improvement, bugs or style issues?

For some kind of fun I've replaced your byte array with the buildin BitArray (as mentioned by Dmitry) in you class just to see the effect (it seems to be slightly faster). Further I've tried to implement the sieve algorithm as linq based. It all goes like this:

    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;

    namespace PrimesAndSieve
    {
      public class SieveOfEratosthenes
      {
        private readonly int highestNumber;

        private readonly BitArray data;

        private SieveOfEratosthenes(int highestNumber)
        {
          if (highestNumber < 1)
          {
            throw new ArgumentOutOfRangeException(nameof(highestNumber));
          }
          this.highestNumber = highestNumber;
          data = new BitArray(highestNumber);
        }

        public static SieveOfEratosthenes CreateSeive(int highestNumber)
        {
          var result = new SieveOfEratosthenes(highestNumber);
          result.Populate();
          return result;
        }

        public bool IsPrime(int number)
        {
          if (number < 0 || number > highestNumber)
          {
            throw new ArgumentOutOfRangeException(nameof(number));
          }
          // 0 not stored in byte array so we have to test separately.
          //if (number == 0) ... as noted by Heslacher
          //{
          //  return false;
          //}
          return !data[number];
        }

        private void Populate()
        {
          var sqrt = Math.Sqrt(highestNumber);

          for (var i = 2; i < sqrt; i++)
          {
            if (data[i]) // not a prime
            {
              continue;
            }
            // j += i can overflow so need to guard against that in for loop.
            for (var j = i * i; j < highestNumber && j > 0; j += i)
            {
              data[j] = true;
            }
          }
          data[0] = true; // Mark 0 as not prime.
          data[1] = true; // Mark 1 as not prime.
        }
      }

  class PrimesBySieveAndLinq
  {
    public IEnumerable<long> GetPrimes(long max)
    {
      yield return 2;

      BitArray bits = new BitArray((int)max);

      foreach (var n in EnumOddNumbers(max).Skip(1))
      {
        if (!bits[(int)n])
        {
          yield return n;
          for (long j = n * n; j < max && j > 0; j += n)
          {
            bits[(int)j] = true;
          }
        }
      }
    }

    IEnumerable<long> EnumOddNumbers(long max)
    {
      for (long i = 1; i < max; i += 2)
      {
        yield return i;
      }
    }
  }

      class Program
      {
        static void Main(string[] args)
        {
          int max = 10000; // 000000; // int.MaxValue;
          var sw = Stopwatch.StartNew();
          var sieve = SieveOfEratosthenes.CreateSeive(max);

          for (int i = 1; i < max; i++)
          {
            if (sieve.IsPrime(i))
            {
              Console.WriteLine(i);
            }
          }
          sw.Stop();
          var firstDuration = sw.ElapsedMilliseconds;

          Console.ReadLine();

          sw = Stopwatch.StartNew();
          PrimesBySieveAndLinq pbsl = new PrimesBySieveAndLinq();
          foreach (var prime in pbsl.GetPrimes(max))
          {
            Console.WriteLine(prime);
          }
          sw.Stop();
          Console.WriteLine();
          Console.WriteLine("Took {0}ms", firstDuration);
          Console.WriteLine($"Duration: {sw.ElapsedMilliseconds}");
          Console.WriteLine("END");
          Console.ReadLine();
        }
      }
    }

Note: If you try PrimesBySieveAndLinq.GetPrimes(int.MaxValue) it is very slow at the beginning, but speeds up after some 1000 of primes.


How to name a method that sets some values in a javabean? Often I find myself setting various fields in a Javabean and then passing that Javabean to some method.

customerEntity.setName("Foo");
customerEntity.setAge(45);
customerEntity.setAddress(address);

em.merge(customerEntity);

Or

requestPayload.setCustomerId(2343);
requestPayload.setCustomerPreference("green");
//lots more
sendRequest(requestPayload)

Not liking so much of data-population cluttering, I'd move those to a separate method..

public void doSomeOperation(Customer customer)
    {
          em.merge(prepareCustomerEntity(customer));
    }

private Customer prepareCustomerEntity(Customer customer)
   { customer.setName("Foo");
    customer.setAge(45);
    customer.setAddress(address);
    return customer;
   }

What would be a good name for such a method ? Maybe something like prepareXXX() or populateXXX()? Naming it as prepareXXX() makes it sound like a void method.. populateXXX() sounds better? Or should I just name it as setCustomerValues(). But setXXX() name makes it sound like a typical Javabean setter, which this is not.

I agree you should not use setXXX() as this sounds like a classic setter. I would say go with what you think sounds nice and conveys the meaning well. prepareXXX() sound nice to me. If it is default values you are setting, you could use something along populateWithDefaultValues().

Just make sure you use the same naming strategy throughout your application.


Performing an ID check on a person and saving the result I'm just trying to understand and use unit tests, which from what I can tell is exposing the issues with my code.  A lot of what I do is MVC/WebAPI.  One of the big issues I come across is that my methods end up too long, doing too much, which makes it very difficult to test them.

Description of what the code is for:

The code is taking a request to ID check a person, firstly I try to do this locally, reusing internal data (cheaper!). But if we don't have the information, we have to use an external web service.  I then return the result of whether the person is verified.

I create a log entry in a database, save that.  Then do a check, which is set against that previous entry.  Then return the result to the calling WebAPIController.

What I want:

Here's is the current block I'm looking at, how could I improve it, what should I do differently?  I am a pragmatic man, but I know this can be a lot cleaner, however I'm unsure where to break it up.  Typically using a repository style.

I want to make it more testable and cleaner.  I hear about keeping to a few lines per method.  Also making sure it only does one thing.  But then I think about my code below and they are a series of conditions which are evaluated.  So I could break them up, but it wouldn't be for re-use at this point, they would only be called once.  Which at the moment doesn't make sense for me to do, but it leaves me with long methods.

public interface IInvestigationManager
{
    Task<idResponseVM> LogAndDoCheck(idRequestVM requestVM);
}

public class InvestigationManager : IInvestigationManager
{
    private readonly IIdentityAuthenticationRepository _identityAuthenticationRepository;

    public async Task<idResponseVM> LogAndDoCheck(idRequestVM requestVM)
    {
        // Initialise the identity check, log the request and get Id
        var newIdCheck = CreateIdentityCheckDM_FromRequestVM(requestVM);

        //Log the Request in the database; Marking it pending result
        _identityAuthenticationRepository.Add(newIdCheck);

        IdentityCheck latestLocalCheck = null;
        idResponseVM responseVM = new idResponseVM();

        try //database interactions.
        {
            await _identityAuthenticationRepository.SaveChangesAsync();

            // Check for existing local authentication
            latestLocalCheck = _identityAuthenticationRepository.LatestPreviousCheckWithinThreshold(newIdCheck);
        }
        catch (SqlException ex)
        {
            latestLocalCheck = null;
            responseVM.Errors.Add("SQL Server error", ex);
            // Divert to try external check
        }
        catch (Exception ex)
        {
            throw ex;
        }

        if (latestLocalCheck != null)
        {
            // Local check
            newIdCheck.IdentityServiceUsed = IdentityServiceUsed.Local;
            newIdCheck.ResultMatchIsValid = latestLocalCheck.ResultMatchIsValid;

            responseVM.ResultIsValidMatch = latestLocalCheck.ResultMatchIsValid;
            responseVM.Results = null;
        }
        else
        {
            try
            {
                // External Id Check
                var idResult = GetExternalCheckResponse(requestVM);
                var isMatch = idResult.matchlevel == enReportType.IndividualReport;

                newIdCheck.IdentityServiceUsed = IdentityServiceUsed.External;
                newIdCheck.ResultMatchIsValid = isMatch;

                newIdCheck.ResultMatchType = idResult.matchlevel.ToString();
                newIdCheck.ExternalSearchId = idResult.searchid;

                responseVM.ResultIsValidMatch = isMatch;
                responseVM.Results = idResult;

            }
            catch (WebException ex)
            {
                // Do other stuff as a backup plan
            }
            catch (Exception ex)
            {
                // Log
                throw ex;
            }
        }

        await _identityAuthenticationRepository.SaveChangesAsync();

        return responseVM;
    }
}

You can use a mocking library, like MOQ, to "intercept" calls to _identityAuthenticationRepository, thus removing the physical database from the equation. And you want to do this because you do not want to be testing the Web Service. All you care about is what this code does with a given returned response.

It is troubling that you have catch (SqlException ex) at this level. Why is this not done in the repository? Besides separation of concerns, it blows the whole idea of an abstract repository out of the water.

Your concerns about "too long" methods seems arbitrary to me. LogAndDoCheck() may be "too long", but why? It's not so much "too long" as it is not understandable. Not without reading all the code carefully. It needs to be structured to express what's happening "at this level of abstraction". In other words, Your "Description of..." suggests what the method should look like:

 public ... LogAndDoCheck() {
     var identityThingy = VerifyLocally();

     if(!identityThing.Verified)
         identityThingy = VerifyRemotely();

     if(!identityThingy.Verified)
         throw new InvalidUserException(identityThingy.ToString());
 }

The method is not arbitrary made short. It's short because of the layering of abstract functional details.

It is also shorter because we got the repository out of the way. Of course you gotta call the repository eventually, but that method is now shorter too. And put the SqlException catching there too. That obviously is the best place to capture any available details like parameter values.

And exception handling might better be done by try { LogAndDoCheck(); } catch ....

P.S.

Instead of setting the IdentityCheck to null, have a property or other way of asking the object if the identity is invalid. That way you have the properties it was built with - user entry stuff I imagine - at hand and that can be included in Exception.Data.


Passing $_POST from view to model in MVC I am building my own MVC structured project to learn the concepts of MVC and I need to pass $_POST variables from my view (which is a login form) to the model. Down below is my approach but I wonder if it is the correct way to do it or there is a better one for example passing it into the construct or maybe putting $_POST inside an array.. What do you think?

The login method is to generate a token for my login form in the view which is for the cookie

class Users
{

    protected $db;

    public function __construct()
    {
        $this->db = Database::instance();
    }

    public function login()
    {
        return self::genToken();
    }

    public function loginAction()
    {
        $username   = $_POST['username'];
        $password   = $_POST['password'];
        $rememberMe = $_POST['remember_me'];
        $token      = $_POST['token'];
        $redirect   = null;
        ...

    }
    public function genToken()
    {
       return md5(uniqid());
    }

Here is my view. (http://localhost/MVC/public/user/login)

<form id="login" method="post" action="http://localhost/MVC/public/user/loginAction" class="well">

        Username
        <input type="text" name="username" class="form-control" placeholder="">

        Password
        <input type="password" name="password" class="form-control" placeholder="Password">
        <input type="hidden" name="token" value="<?= $data['token'] ?>" />

Forget the password?

        <input type="checkbox" name="remember_me" value="1" checked /> Remember Me

    <button type="submit" class="btn btn-default btn-block" name="signin">Login</button>
</form>

Superglobals

I cloned your repo and it looks like you've already taken my advice about passing in the superglobals instead of using them directly from your methods.

Formatting

I would have also commented on the formatting but you've also significantly improved that since posting the question. Cheers!

Commenting

The next good habit to get into is commenting, which s just as important as formatting and entirely lacking in this project. You should always put a short comment above every method explaining what it does, what parameters it takes and what it returns so you (and people maintaining the code in
 the future) don't have to read the code to figure out what it does.

I see you're using NetBeans. I Like NB too. NB makes documenting your PHP and JS classes and functions very easy. I looked and I could not find any good documentation because I cannot remember what it's called, so I'll just explain the features as best I can.

Auto-commenting Pro Tip

Netbeans will actually do most of the work for you - place the cursor on the empty line just above the start of the function and type /** and hit the enter key. Netbeans will create the rest of the comment including the parameters and the return type (if there is one).

This is what Netbeans generated for your loginAction method.

/**
 *
 * @param type $username
 * @param type $password
 * @param type $rememberMe
 * @param type $token
 * @param type $redirect
 */
public function loginAction($username, $password, $rememberMe, $token, $redirect = null)

Now you just need to write a short description on the first blankk line and fill in the types (if NB wasn't able to guess them already). eg..

/**
 * Authenticate a user and start a session
 * @param String $username - The username of the user
 * @param String $password - The user's password
 * @param Boolean $rememberMe - Set a cookie?
 * @param String $token - Login token
 * @param String|Null $redirect - URL to redirect to
 */
public function loginAction($username, $password, $rememberMe, $token, $redirect = null)

Now, not only will this be easy to read and maintain, but NetBeans will actually parse these comments and show you what parameters are required when you start to type the method name: