Combinatorics, C++ and optimization Note: I have a working solution, my question is about optimization and other approaches.
Problem Description
Hello, I'm re-writing an old program I made that solves nonograms.
As part of solving it, I generate (for some of the lines) an array of all possible ways to fit the numbers in.
I want to create a piece of code, that will iterate all the positions in which I can put the spaces, for example: if there's a line with size 5, and the numbers are 1, 1, there are multiple ways do order the numbers, like 1-1--, 1--1-, 1---1, --1-1, ... (- is a white box, while 1 will be black).
Problem Breakdown
So if we look at the example above, we can describe the options like this:

The total size is 5, and we have two 1, therefore we have 2 white boxes to play around with (1 must be between the numbers), I have another function that calculates that "free space".

We can index the possible places for the spaces this way: [0] 1 [1] 1 [2], meaning the spaces can go in each of the [indexes].

All the options of placing the spaces can be solved with nested loops, but since the "free space" and the possible indexes are dynamic, this is not an option.

For solution I try to create "dynamic" nested loops, with any range and depth, the question is:

Is there a more efficient way of doing so?
Possible Solution
The scope my question refers to is not related specifically to solving a nonorgram or even a specific language, but since I'm writing this in C++, I will post my attempt for a code that does so:
#include <vector>
#include <iostream>

using namespace std;

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.
    int move_index;

    vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";
        cout << endl;

        for (move_index = iterators_number - 1;
             (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1); move_index--);
        if (move_index < 0) break;
        int new_value = options_iteration[move_index] + 1;
        for (; move_index < iterators_number; move_index++) options_iteration[move_index] = new_value;
    }

    return 0;
}

Output:
0 0 0
0 0 1
0 0 2
0 0 3
0 1 1
0 1 2
0 1 3
0 2 2
0 2 3
0 3 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

If anyone is interested in the full implementation, once it's done and fully documented, I will upload it to my GitHub account.
Thanks in advance for the helpers and commentators.

Overall Observations
The more code you provide the better the reviews you will get. There are 2 statements, 1 in the question and 1 in the comments after the question that almost make it off-topic for the Code Review site:

... my real code does not print for each iteration, this is for easy testing.
I have another function that calculates that "free space".

As provided in the question the code is almost unreadable and therefore would be a problem for maintenance. If I were an teacher grading this code the best grade I can give it is a C (70%) because it compiles and runs. The variable names are meaningful. In a professional environment if I were your manager we would have a long talk in private about why it is important to make the code more readable.
In a professional environment you are very unlikely to be the only one maintaining the code for multiple reasons:

You may get promoted and not assigned to maintain the code anymore.
You may quit and get another job.
A bug may exist in the code that needs to be fixed and you are assigned to a higher priority project so someone else will be assigned to fix the code.

There are more reasons than just the 3 above. For all these reasons I will be addressing coding style here.
Possible Optimizations
The first rule of optimization is don't optimize, the second is find all the bottlenecks in the code (bottlenecks being functions that slow down the code). The primary way to optimize C++ code is to use the built in compiler optimization using the -O through -O3 compiler command lines. This will generally produce very fast code. It will be very difficult to provide optimizations for this code as currently presented, but if you are compiling for debug one possible optimization might be to use the C++ iterators provided for each of the container classes such as vector.
You might also want to make the variables iterators_number and iterators_range constants since they don't change.
    const int iterators_number = 3;
    const int iterators_range = 3;

Avoid using namespace std;
If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.
Declare Variable as Necessary
As far as I can tell the variable move_index does not need to maintain it's value between iterations of the while (true) loop so it should be declared within the loop, the declaration should include the initialization of the variable in almost all cases, but definitely in this case.
Don't Use One line for Loops or if Statements
The code contains this line:
        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";

On my first time through the code I missed the fact that the for loop had an action. This code should be on 2 lines at least but preferably 4. 2 lines:
        for (int i = 0; i < iterators_number; i++)
            cout << options_iteration[i] << " ";

Why 4 lines? One of the easiest mistakes to make when maintaining code is to add a statement to a for loop or if statement without adding the braces necessary to make it part of the loop. So when creating new code it is better to add the to begin with:
        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }

I didn't come up with this, it was forced on me by a company coding standard, however, I saw the value of it having made that kind of mistake a number of times.
This version of the code is slightly longer but muc more readable and easier to maintain:
#include <vector>
#include <iostream>

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.

    std::vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }
        std::cout << std::endl;

        int move_index = iterators_number - 1;
        for ( ;
            (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1);
            move_index--)
            ;
        if (move_index < 0)
            break;

        int new_value = options_iteration[move_index] + 1;
        for ( ; move_index < iterators_number; move_index++)
        {
            options_iteration[move_index] = new_value;
        }
    }

    return 0;
}


Rolling regressions in R I want to run rolling regressions over each group and store the coefficient. The following works, but it's slow, since I have too many series and I want to run too many regressions for each group.

Using foreach(), speeds things up (and also getting the coefficient with (X'X)^{-1}X'Y but is there a way to vectorize this operation? Also open for any and all improvements.

library(data.table)

run.rolling.regressions <- function(x) {
DT <- data.table(   Y = rnorm(10000),
                    X = rnorm(10000),
                    key.group = rep(LETTERS[1:10], each = 1000))

window.length <- 12
names.of.groups <- unique(DT$key.group)
number.of.groups <- length(names.of.groups)

X.coefficients <- list()

for(j in 1:length(names.of.groups)) {
regressed.DT <- DT[key.group == names.of.groups[j]]
nrows.of.group <- nrow(regressed.DT)
            print(paste0(j, ', key.group: ', names.of.groups[j]))
for (i in window.length:nrows.of.group) {
            if(i == window.length) {
            X.coefficients[[names.of.groups[j]]] <- c(rep(NA, nrows.of.group)) }
            X.coefficients[[names.of.groups[j]]][i] <-  lm(Y ~ 1 + X,
                    data = regressed.DT[(i - 11):i])$coefficients['X']

}
}
return(X.coefficients)
}
system.time(X.coef <- run.rolling.regressions())

For each group in your data table, your code computes the coefficient b1 from a linear regression y = b0 + b1*x + epsilon, and you want to run this regression and obtain b1 for observations 1-12, 2-13, 3-14, ..., 989-1000. Right now you are separately calling lm for each data subset, which is a non-vectorized approach.

Vectorization of prediction models across datasets is in general not straightforward, but for the special case you have here (simple linear regression) is it possible because there is a simple closed-form expression for b1, the coefficient of interest. In particular, for given vectors x and y we have b1 = (mean(x*y) - mean(x)*mean(y)) / (mean(x^2) - mean(x)^2). The rolling coefficient value can therefore be computed using the rolling means of x*y, x, y, and x^2 with the appropriate window width.

The end result is a fully vectorized version of the code (I use the RcppRoll package to obtain rolling means):

library(RcppRoll)
rolling2 <- function(DT, window.length) {
  setNames(lapply(unique(DT$key.group), function(g) {
    regressed.DT <- DT[key.group == g]
    xyBar = roll_mean(regressed.DT$X*regressed.DT$Y, window.length)
    xBar = roll_mean(regressed.DT$X, window.length)
    yBar = roll_mean(regressed.DT$Y, window.length)
    x2Bar = roll_mean(regressed.DT$X^2, window.length)
    c(rep(NA, window.length-1), (xyBar - xBar*yBar) / (x2Bar - xBar^2))
  }), unique(DT$key.group))
}

We can confirm that this yields identical results to the code from the original post about 3 orders of magnitude more quickly:

set.seed(144)
DT <- data.table(   Y = rnorm(10000),
                    X = rnorm(10000),
                    key.group = rep(LETTERS[1:10], each = 1000))
system.time(X.coef <- run.rolling.regressions(DT, 12))
#    user  system elapsed
#  13.321   0.098  13.504
system.time(X.coef2 <- rolling2(DT, 12))
#    user  system elapsed
#   0.010   0.000   0.011
all.equal(X.coef, X.coef2)
# [1] TRUE

Note that I slightly modified the provided run.rolling.regressions function to take DT and window.length as input and to not print progress updates; I think it makes sense to separate the generation of the dataset from the function that computes the rolling means, and down the road it might be useful to have the window length as an adjustable argument instead of a fixed value.


complicated pascal triangle using JavaScript I wrote a function to generate a complicated version of the pascal triangle. The generated triangle should look like that:

┌─────────┬───┬───┬────┬────┬────┬────┬────┬───┬───┐
│ (index) │ 0 │ 1 │ 2  │ 3  │ 4  │ 5  │ 6  │ 7 │ 8 │
├─────────┼───┼───┼────┼────┼────┼────┼────┼───┼───┤
│    0    │ 1 │   │    │    │    │    │    │   │   │
│    1    │ 1 │ 1 │ 1  │    │    │    │    │   │   │
│    2    │ 1 │ 2 │ 3  │ 2  │ 1  │    │    │   │   │
│    3    │ 1 │ 3 │ 6  │ 7  │ 6  │ 3  │ 1  │   │   │
│    4    │ 1 │ 4 │ 10 │ 16 │ 19 │ 13 │ 10 │ 4 │ 1 │
└─────────┴───┴───┴────┴────┴────┴────┴────┴───┴───┘

My implementation is like that

function createTriangle (n) {
// initialize the holding matrix
  let matrix = [];

// iterate over the matrix rows, and for each row construct a new array of row number + 1

  for (let row = 0; row < n; row++) {
    matrix[row] = new Array(row+1);
// iterate over each row and check conditions

    for (let col = 0; col <= 2*row; col++) {
      if ((col === 0 && row >= 0) || (col === 2 * row)) {
        matrix[row][col] = 1;
// first case
      } else if(col === row && col === 1){
                matrix[row][col] = 1;
// second case ;
            } else if(row > col && matrix[row][col-1]=== 1 ) {
            matrix[row][col] =
            1 + matrix[row-1][col];
// third case
            } else if(row > col && matrix[row][col-1]!== 1 ) {
            matrix[row][col] =
            matrix[row-1][col-2] + matrix[row-1][col-1] + matrix[row-1][col];
// fourth case
     } else if((row === col && (matrix[row][col-1] !== 1))) {
                matrix[row][col] =
                matrix[row-1][col-2] + matrix[row-1][col-1] + matrix[row-1][col];

// fifth case
       // if the col number is even, add only the previous 2 elements in the previous row
            } else if(row < col && col % 2 === 0){
                matrix[row][col] = matrix[row-1][col-2] + matrix[row-1][col-1] + matrix[row-1][col];
// sixth case

      // if the col number is odd add the previous 3 elements in the previous row
            } else if(row < col && col % 2 === 1){

            matrix[row][col] = matrix[row-1][col-2] + matrix[row-1][col-1];
            }
        }
    }
  return matrix;
}

console.table(createTriangle(5))

I feel that my code is a bit confusing. In addition, there is a bug on matrix[4, 5] it should be 16,but it is 13?? Could anyone advise if there is a more refactored elegant solution? Appreciate your time and help.

Edit
The algorithm should generate a matrix that have number of columns twice number of rows. The elements before the element at matrix[row][col] where col = row should be the same but reversed in a desc. order. for example, matrix[4,4] => [1,4,10,16,19,16,10,4,1]. element at matrix[4,4] 19 should be equal to 6+7+6

You are not properly calculating the pascal triangle. Here is my solution, in this code I take advantage of the function .splice() to modify the content of every row. You know that the outter elements of each row are 1s and in between you make the calculations of the sum of the top "root elements", and just like that you get the Pascal's Triangle.

function pascalTriangle(level) {
  let matrix = [[1]];

  for (let row = 1; row < level; row++) {
    matrix.push([1, 1]);
    for (let col = 1; col < row; col++) {
      matrix[row].splice(col, 0, matrix[row - 1][col - 1] + matrix[row - 1][col]);
    }
  }

  return matrix;
}

console.log(pascalTriangle(7));

┌─────────┬───┬───┬────┬────┬────┬───┬───┐
│ (index) │ 0 │ 1 │ 2  │ 3  │ 4  │ 5 │ 6 │
├─────────┼───┼───┼────┼────┼────┼───┼───┤
│    0    │ 1 │   │    │    │    │   │   │
│    1    │ 1 │ 1 │    │    │    │   │   │
│    2    │ 1 │ 2 │ 1  │    │    │   │   │
│    3    │ 1 │ 3 │ 3  │ 1  │    │   │   │
│    4    │ 1 │ 4 │ 6  │ 4  │ 1  │   │   │
│    5    │ 1 │ 5 │ 10 │ 10 │ 5  │ 1 │   │
│    6    │ 1 │ 6 │ 15 │ 20 │ 15 │ 6 │ 1 │
└─────────┴───┴───┴────┴────┴────┴───┴───┘


String.IsNullOrEmpty in JavaScript I am aware of it being frowned upon to do something like write C# in JavaScript. (see this if you don't know what I'm talking about)

But as a judgement call, I think we could stand to have a relatively simple check for values that are null or empty, so I'm looking for feedback on this implementation of String.isNullOrEmpty.

String.isNullOrEmpty = function (value) {
    return (!value || value == undefined || value == "" || value.length == 0);
}

Starting with:

return (!value || value == undefined || value == "" || value.length == 0);

Looking at the last condition, if value == "", it's length MUST be 0. Therefore drop it:

return (!value || value == undefined || value == "");

But wait! In JS, an empty string is false. Therefore, drop value == "":

return (!value || value == undefined);

And !undefined is true, so that check isn't needed. So we have:

return (!value);

And we don't need parentheses:

return !value

Q.E.D.


Using Alertify to show messages I use a JavaScript library called Alertify to show simple, pretty messages, like "note created", or whatever. Often I want to send the user to a new page and then show an Alertify message.

I'm trying to find a way to do this on the fly, without tons of configuration.

Currently I do this by creating an AlertifyMessages object:

public class AlertifyMessages
{
    public string LogMessage { get; set; }
    public string LogCallback { get; set; }

    public string SuccessMessage { get; set; }
    public string SuccessCallback { get; set; }

    public string ErrorMessage { get; set; }
    public string ErrorCallback { get; set; }

    public AlertifyMessages() { }

    public AlertifyMessages(string logMessage = null, string logCallback = null,
                            string successMessage = null, string successCallback = null,
                            string errorMessage = null, string errorCallback = null)
    {
        LogMessage = logMessage;
        LogCallback = logCallback;
        SuccessMessage = successMessage;
        SuccessCallback = successCallback;
        ErrorMessage = errorMessage;
        ErrorCallback = errorCallback;
    }
}

and passing it to an action method:

public ActionResult Test()
{
    // RedirectToAction([action], [controller], [routeValues])
    return RedirectToAction("Details", "Notes",
        new AlertifyMessages(logMessage: "Lorem ipsum"));
}

and in the destination action method:

public class NotesController : Controller
{
    // GET
    public ActionResult Details(AlertifyMessages alertify)
    {
        return View(new NoteDetailsViewModel(alertify));
    }
}

which, finally, displays the messages in the view:

@if (Model.Alertify.LogMessage != null)
{
    @:@Html.Alertify("log", Model.Alertify.LogMessage, Model.Alertify.LogCallback)
}
@if (Model.Alertify.SuccessMessage != null)
{
    @:@Html.Alertify("success", Model.Alertify.SuccessMessage, Model.Alertify.SuccessCallback)
}
@if (Model.Alertify.ErrorMessage != null)
{
    @:@Html.Alertify("error", Model.Alertify.ErrorMessage, Model.Alertify.ErrorCallback)
}

The helper method Alertify just adds the JavaScript to call alertify.js, but you can see it here

Besides being a nightmare in so many ways, this doesn't even work unless the AlertifyMessage is all I need to pass. I could make some kind of complicated ToString() override to resolve this, but otherwise attempting to pass, say, an ID as well as an AlertifyMessages like so

return RedirectToAction("Details", "Notes",
    new { id = 1, alertify = new AlertifyMessages(logMessage: "Lorem ipsum")});

yields a URL like

https://localhost/Notes/Details/1?alertify=Project.Namespace.AlertifyMessages

This is way too complicated. There must be a better way.

  Edit: I'd like a way to specify the message in the calling action method (the one performing the redirect), and nowhere else. Is there a way to do this other than adding code to every single method and view?

You may start making your model simpler:

public sealed class AlertifyMessageModel
{
    public string Message { get; set; }
    public string Callback { get; set; }
}

Note that you do not need all those ugly ctor parameters:

public ActionResult Test()
{
    return RedirectToAction("Details", "Notes",
        new AlertifyMessageModel { Message = "Lorem ipsum" });
}

You may also want to use nameof(Notes.Details) instead of hard-coded "Details" string. Usually I also have an helper method GetControllerName(nameof(NotesController)) or a static field NotesController.Name but it's verbose and not everyone likes it.

Now let's go to your View. We need to add a property to the model to hold the type of notification:

public sealed class AlertifyMessageModel
{
    public string Message { get; set; }
    public string Callback { get; set; }
    public string Type { get; set; } = "log"
}

Then we can simply write:

if (Model.Alertify.Message != null)
{
    @:@Html.Alertify(Model.Alertify.Type, Model.Alertify.Message, Model.Alertify.Callback)
}

Next step is to change Type to enum:

public NotificationType Type { get; set; } = NotificationType.Log;

For your URL problem you should change something more, you may serialize the whole object as JSON and post it in the request body instead of in the URL. I don't see code around that then I can't really suggest a nice method. Note that you may also override ToString() to return a parseable representation of AlertifyMessageModel (think about type converters).


Optimising Probabilistic Weighted Moving Average (PEWMA) df.iterrows loop in Pandas I'm implementing the Probabilistic Exponentially Weighted Mean for real time prediction of sensor data in pandas but have issues with optimising the pandas notebook for quick iterations.

Is there a more optimal way to completely remove the for loop as it currently runs longer than expected. How can I take advantage of apply() ; or vectorized operations etc. here?

import pandas as pd
import numpy as np
from datetime import datetime, timedelta
import datetime
import matplotlib.pyplot as plt
#plt.style.use('fivethirtyeight')
#%config InlineBackend.figure_format = 'retina'
#%matplotlib inline
from itertools import islice
from math import sqrt
from scipy.stats import norm

ts = pd.date_range(start ='1-1-2019',
         end ='1-10-2019', freq ='5T')

np.random.seed(seed=1111)
data = np.random.normal(2.012547, 1.557331,size=len(ts))
df = pd.DataFrame({'timestamp': ts, 'speed': data})
df.speed = df.speed.abs()
df = df.set_index('timestamp')
time_col = 'timestamp'
value_col = 'speed'

#pewna parameters
T = 30      # initialization period (in cycles)
beta = 0.5  # lower values make the algorithm behave more like regular EWMA
a = 0.99    # the maximum value of the EWMA a parameter, used for outliers
z = 3

#the PEWNA Model

# create a DataFrame for the run time variables we'll need to calculate
pewm = pd.DataFrame(index=df.index, columns=['Mean', 'Var', 'Std'], dtype=float)
pewm.iloc[0] = [df.iloc[0][value_col], 0, 0]

t = 0

for _, row in islice(df.iterrows(), 1, None):
    diff = row[value_col] - pewm.iloc[t].Mean # difference from moving average
    p = norm.pdf(diff / pewm.iloc[t].Std) if pewm.iloc[t].Std != 0 else 0 # Prob of observing diff
    a_t = a * (1 - beta * p) if t > T else 1 - 1/(t+1) # weight to give to this point
    incr = (1 - a_t) * diff

    # Update Mean, Var, Std
    pewm.iloc[t+1].Mean = pewm.iloc[t].Mean + incr
    pewm.iloc[t+1].Var = a_t * (pewm.iloc[t].Var + diff * incr)
    pewm.iloc[t+1].Std = sqrt(pewm.iloc[t+1].Var)
    t += 1

I think you can use just raw numpy arrays for speeding it up:

after #the PEWMA Model you can just use following code:

_x = df[value_col]
_mean, _std, _var = np.zeros(_x.shape), np.zeros(_x.shape), np.zeros(_x.shape)

for i in range(1, len(_x)):
    diff = _x[i] - _mean[i-1]

    p = norm.pdf(diff / _std[i-1]) if _std[i-1] != 0 else 0 # Prob of observing diff
    a_t = a * (1 - beta * p) if (i-1) > T else 1 - 1/i # weight to give to this point
    incr = (1 - a_t) * diff

    # Update Mean, Var, Std
    v = a_t * (_var[i-1] + diff * incr)
    _mean[i] = _mean[i-1] + incr
    _var[i] = v
    _std[i] = np.sqrt(v)

pewm = pd.DataFrame({'Mean': _mean, 'Var': _var, 'Std': _std}, index=df.index)

If you need to apply it to really big data you could make it even faster by using numba package:

from numba import njit

# numba has some issues with stats's norm.pdf so redefine it here as function
@njit
def norm_pdf(x):
    return np.exp(-x**2/2)/np.sqrt(2*np.pi)

@njit
def pwma(_x, a, beta, T):
    _mean, _std, _var = np.zeros(_x.shape), np.zeros(_x.shape), np.zeros(_x.shape)
    _mean[0] = _x[0]

    for i in range(1, len(_x)):
        diff = _x[i] - _mean[i-1]

        p = norm_pdf(diff / _std[i-1]) if _std[i-1] != 0 else 0 # Prob of observing diff
        a_t = a * (1 - beta * p) if (i-1) > T else 1 - 1/(i) # weight to give to this point
        incr = (1 - a_t) * diff

        # Update Mean, Var, Std
        v = a_t * (_var[i-1] + diff * incr)
        _mean[i] = _mean[i-1] + incr
        _var[i] = v
        _std[i] = np.sqrt(v)
    return _mean, _var, _std

# Using :
_mean, _var, _std = pwma(df[value_col].values, 0.99, 0.5, 30)
pewm = pd.DataFrame({'Mean': _mean, 'Var': _var, 'Std': _std}, index=df.index)


Usage of Interlocked.CompareExchange for deciding whether a property has been changed by another thread I'm developing a Windows Service that receives data from somewhere and saves it to DB one time per 5 minutes. The Service is multithreaded and I actually got problems when several threads saved data at same minute (no thread sync was implemented).

Now I've implemented it and am looking for code-review and optimizations.

class DataProccessor
{
    private int _lastMinutesUpdate;
    private readonly Timer _saveTimer = new Timer(TimerTick, null, _settingsProvider.SaveInterval, Timeout.Infinite);

    private void TimerTick(object state)
    {
        var watch = new Stopwatch();
        watch.Start();
        var initialLastMinutesUpdate = _lastMinutesUpdate;
        var currentDate = DateTime.UtcNow;
        var currentDateMinutes = currentDate.Minute;
        var fiveMinUpdate = currentDateMinutes % 5 == 0 &&
                            currentDateMinutes != initialLastMinutesUpdate &&
                            initialLastMinutesUpdate == Interlocked.CompareExchange(ref _lastMinutesUpdate, currentDateMinutes, initialLastMinutesUpdate);
        if(fiveMinUpdate)
        {
            // Insert values to DataBase
        }
        // TimerTick will be called in interval from settings minus time spent to TimerTick execution.
        _saveTimer.Change(Math.Max(0, _settingsProvider.SaveInterval- watch.ElapsedMilliseconds), Timeout.Infinite);
    }
}

In your code, the only way to have two threads update that value simultaneously is if TimeTick gets invoked twice in a very short amount of time.  Given a sane value for your time interval, this can't happen.  And if it can, you would typically use a Monitor and quickly exit the second handler.

It seems that you are invoking this timer at a much higher rate than necessary - every 200ms - because you want to do something else that frequently, so you have code to check if you should do your 5 minute job now.  There isn't a good reason to have one callback responsible for two totally different things.  You should be able to solve this by having a 5 minute timer for the database job and a 200 ms timer for the broadcast, and these would each call their own callback function.


Handling errors when using PDO to connect to a database instead of MySQLi What would be the preferred method for handling errors when using the PDO to connect to a MySQL database? I was using mysqli_error($this->pdo), but I heard this was bad practice. Any feedback would be much appreciated.

class Database
{
    /*
     * Database properties
     */
    private $server   = 'localhost';
    private $username = 'root';
    private $password = 'root';
    private $database = 'posts';
    public $pdo;
    public static $instance;

    /**
     * Static method used to instantiate singleton
     * @return [object] Database object
     */
    public static function getInstance()
    {
        if (!isset($instance)) {
            Database::$instance = new Database();
        }
        return Database::$instance;
    }

    /**
     * Connect to DB when class is instantiated
     */
    private function __construct()
    {
        $this->connect();
    }

    /**
     * Connects to the database
     */
    private function connect()
    {
        // Assign dsn string
        $dsn = 'mysql:host=' . $this->server . ';dbname=' . $this->database;

        // Assign connection to $pdo
        $pdo = new PDO($dsn, $this->username, $this->password);

        // $pdo inside the function is added to the objects parameter pdo
        else {
            $this->pdo = $pdo;
        }
    }

    /**
     * Queries database for the argument $sql
     * @param  string $sql
     * @return Sql Query $statement
     */
    public function query($sql)
    {
        // Prepare SQL query
        $statement = $this->pdo->prepare($sql);

        // return mysql query array
        else {
            return $statement;
        }
    }

    /**
     * Queries for post of id $id
     * @param  [$id] Post ID
     * @return [array]
     */
    public function getPost($id)
    {
        // Query
        $stmt = $this->query("SELECT * FROM posts WHERE id=(:id)");

        // Binds $id parameter to the PDO
        $stmt->bindParam(':id', $id);

        // Execute query
        $stmt->execute();

        // Create an empty array for the posts
        $posts = array();

        while($row = $stmt->fetch()) {
            // Data is fetched from the database as an array
            $posts[] = $row;
        }

        // Return post in an array
        return $posts;
    }

}

From a first pass over - all you are doing are if else without any throw or inspection as to what possible errors that the PDO might be tossing out.

Thats bad because on production servers - I would assume that you won't be turning on error/warning reporting but will be logging them.

Also as @Alex L mentioned - you are missing a IF statement that checks if $pdo == null then throw exception. However its better with a try/catch

try {
    $pdo = new PDO($dns, $username, $password, $options);
} catch (PDOException $e) {
    throw new pdoDbException($e);
}


URL decode a string but log an error after second exception I have a method which does URL decoding on the string value passed along with using Charset:

  public String decodeValue(String value, Charset charset) {
    if (!Strings.isNullOrEmpty(value)) {
      try {
        value = URLDecoder.decode(value, charset.name());
      } catch (UnsupportedEncodingException ex) {
        // log error
        return null;
      }
    }
    return value;
  }

Now if URLDecoder.decode throws UnsupportedEncodingException the first time, then I want to run the same value against these three lines:

value = value.replaceAll("%(?![0-9a-fA-F]{2})", "%25");
value = value.replaceAll("\\+", "%2B");
value = URLDecoder.decode(value, charset.name());

And if then again URLDecoder.decode line throws exception second time, then I will log the error but only second time and return null value otherwise return the value which is decoded so I came up with this:

  public String decodeValue(String value, Charset charset) {
    if (!Strings.isNullOrEmpty(value)) {
      try {
        value = URLDecoder.decode(value, charset.name());
      } catch (UnsupportedEncodingException ex) {
        try {
          value = value.replaceAll("%(?![0-9a-fA-F]{2})", "%25");
          value = value.replaceAll("\\+", "%2B");
          value = URLDecoder.decode(value, charset.name());
        } catch (UnsupportedEncodingException uex) {
          // log error
          return null;
        }
      }
    }
    return value;
  }

I'd like to see if there is any better way to write the above code. As of now, it duplicates the code.

First, let's  move the replacements into a separate fixErrors method for readability.

String fixErrors(String value) {
    return value
        .replaceAll("%(?![0-9a-fA-F]{2})", "%25")
        .replaceAll("\\+", "%2B");
}

Now, my solution would be to write a method that returns the result of URLDecoder.decode as an Optional. Then, instead of nesting try/catch statements, we can just use Optional::or. This should look something like

public String decodeValue(String value, Charset charset) {
    if (!Strings.isNullOrEmpty(value)) {
        return tryDecode(value, charset)
            .or(() -> tryDecode(fixErrors(value), charset))
            .orElse(null);
    }
    return value;
}

Optional<String> tryDecode(String value, Charset charset) {
    try {
        return Optional.of(URLDecoder.decode(value, charset.name()));
    } catch (UnsupportedEncodingException ex) {
        return Optional.empty();
    }
}

Unfortunately, this solution precludes logging details of only the second error. To do this effectively, we could add error handling to tryDecode by passing it a Consumer<UnsupportedEncodingException>. Then we would have:

public String decodeValue(String value, Charset charset) {
    if (!Strings.isNullOrEmpty(value)) {
        return tryDecode(value, charset, ex -> {})
        .or(() -> tryDecode(fixErrors(value), charset, ex -> {
                // log ex
            }))
        .orElse(null);
    }
    return value;
}

Optional<String> tryDecode(String value, Charset charset,
                   Consumer<UnsupportedEncodingException> exConsumer) {
    try {
        return Optional.of(URLDecoder.decode(value, charset.name()));
    } catch (UnsupportedEncodingException ex) {
        exConsumer.accept(ex);
        return Optional.empty();
    }
}

Hopefully this solution meets your requirements.


Personal HTML page for beginner CS lab I'm completely new at programming and have started to study computer science this fall. Our first lab is going to require us to make a very simple web page like the picture LAB attached. I was wondering if I could get some good critique on my HTML code and learn some best practices while I'm at it.

<!DOCTYPE html>

<title> EECS1012 – Lab 1 </title>

 About Alen Harriet

 Passionate self-learner. Taking a CS Degree to learn more formal materials like Operating Systems and Computer Architecture, and to have strong fundamentals. My dream is to hopefully work for Google someday.

 My IP address: 192.XXX.XX.XX

 Courses I'm taking this semester.

 EECS 1012

 EECS 1001

 FA VISA 2065

 AP GEOG 2060

 My weekly timetable

     Time
     Monday
     Tuesday
     Wednesday
     Thursday
     Friday

     9am

     10am

     11am

     noon

     1:30pm
        LE EECS 1012

     FA VISA 2065

     2:30pm
      LE EECS 1012

     FA VISA 2065

     3:30pm
      LE EECS 1012

     FA VISA 2065

     4:30pm
      LE EECS 1012  LE EECS 1001

     FA VISA 2065

     5:30pm
      LE EECS 1001  LE EECS 1012

     AP GEOG 2060

     6:30pm
      LE EECS 1012

     AP GEOG 2060

     7:30pm
      LE EECS 1012

     AP GEOG 2060

 My Two Favourite Foods - With Links

It's good to validate HTML code on https://validator.w3.org/,
it can spot interesting bugs, for example that  noon 	 is outside of a

 here:

     11am

     noon

     1:30pm
        LE EECS 1012

     FA VISA 2065

And that \ is not allowed as path separator in the src attribute of img tags, as it is here:

The other warnings are interesting too,
about the inconsistent number of columns in table rows.


Is this query-string parser bug-free? I tried to implement a definitive, reliable URL query string parser that handles every corner case:

it tries to be efficient by avoiding regex
it takes full URLs or just query strings (as long as the query string begins with a question mark)
it ignores the hash value
it handles multiple equal parameter names
it handles parameter names that equal built-in JavaScript methods and keywords

What do you think - did I miss something?

function parseURLParams(url) {
  if (url === null) return;

  var queryStart = url.indexOf("?") + 1,
      queryEnd   = url.indexOf("#") + 1 || url.length + 1,
      query      = url.slice(queryStart, queryEnd - 1);

  if (query === url || query === "") return;

  var params = {},
      nvPairs = query.replace(/\+/g, " ").split("&");

  for (var i=0; i<nvPairs.length; i++) {
    var nv = nvPairs[i],
        eq = nv.indexOf("=") + 1 || nv.length + 1,
        n  = decodeURIComponent( nv.slice(0, eq - 1) ),
        v  = decodeURIComponent( nv.slice(eq) );
    if ( n !== "" ) {
      if ( !Object.prototype.hasOwnProperty.call(params, n) ) {
        params[n] = [];
      }
      params[n].push(v);
    }
  }
  return params;
}

It returns an object of arrays for parsed URLs with query strings and undefined if a query string could not be identified.

I used this in an answer over at SO.

Is it bug free?  No.

These two corner-cases have been missed:

parameter values containing '=', i.e. 'example.com?foo==bar' (double equals) or '?foo=k=v'
cannot handle parameters called 'toString' and 'valueOf' (amongst others.)

The first may well count as malformed URL, but Chrome handles it and pass through == unencoded in location.search.  To handle this, go back to basic indexOf usage.

The second problem's just pedantic really.  You could try and work around it using !params.hasOwnProperty(n) instead of !(n in params), but you'll still get stuck if someone passes a parameter called hasOwnProperty.  The only way I see around this is to fall back to some dire array-based collection populated something like:

var keys = [], params = [];
for (...) {
    var n = ..., v = ...;
    var i = keys.indexOf(n);
    if (i >= 0) {
        if (!(params[i] instanceof Array)) {
            params[i] = [params[i]];
        }
        params.push(v);
    } else {
        params[i] = v;
        keys.push(n);
    }
}

I guess you'd then have to resort to returning an array of arrays rather than an object.  i.e. each element of the array returned would either be [key, value] or [key, [values]], although client might find it easier to work with if you returned something like [key, value1, value2, ...] (which caters nicely for properties without values.)


One time key for authentication In a recent project I was to create a web service that would be consumed by another application. One of the requirements was to have a key in the service that authenticated the request as valid. But this key must never be the same and the key should be invalid soon after its use.

This is the code I wrote to that purpose.

public static bool isKeyValid(long testKey)
{
    var k = GetKey();

    var allowedVariance = 0.00000000004;
    var variance = k * allowedVariance;

    return (k + variance >= testKey && k - variance <= testKey);
}

public static long GetKey()
{
    var i = (long)DateTime.UtcNow.Ticks * 5;
    var d = (long)Math.Sqrt(Math.Ceiling(400 - (DateTime.UtcNow.Day * Math.PI)));
    var k = (long)((Math.Round((Math.Sqrt(i) * Math.Pow(Math.PI + d, 3)) * Math.E - d)) * d) + DateTime.UtcNow.Minute;
    return k;
}

The point being that the caller generates a key and the receiver generates its own and then compares these two and says everything is ok if the difference is within a given variance.

Note that nothing in the message is really secret and this is just a simple check so that the request is probably from a valid source.

I have two questions for this.

How could I have done this better in terms of existing encryption
libraries (in .Net) or using other things such as certificates. This must work     cross platform (Windows, iOS, and Android devices)
How can the given code be modified or improved to make it better for
the intended purpose?

General coding style

avoid using var because it obscures the datatypes.
use meaningful variable names.
when comparing ranges, put the thing being tested in the middle and keep both comparison operators the same.
always use the same value for UtcNow, because the clock is ticking.
document every function you write (1 or 2 lines of comments above each function)

Example:

// Returns true if this key value came from GetKey(), false otherwise.
public static bool IsKeyValid(long testKey)
{
    long k = GetKey();

    double allowedVariance = 0.00000000004;   // say what this is ...

    // You use of 'var' obscured the differing datatypes: k and testKey are long.
    double variance = k * allowedVariance;

    return (k - variance <= testKey && testKey <= k + variance);
}

// Returns a key based on the current time.
public static long GetKey()
{
    DateTime now = DateTime.UtcNow;

    // Explanation is called for here...
    long i = now.Ticks * 5;
    long d = (long)Math.Sqrt(Math.Ceiling(400 - (now.Day * Math.PI)));
    long k = (long)((Math.Round((Math.Sqrt(i) * Math.Pow(Math.PI + d, 3)) * Math.E - d)) * d) + now.Minute;

    return k;
}

I know nothing about encryption so cannot say whether there are built-in .NET functions which perform the same task, but there probably are.


Bernstein polynomial type for quadratic clipping I would like to implement a Bernstein polynomial class in Julia for learning purposes. The goal in the end is to implement the quadratic clipping algorithm from this paper. I am completely new to Julia coming from Python + Numpy + Numba, so I want to make sure that I program in the canonical Julia way when using Julia.

The naming of variables follows the aforementioned paper.

using Polynomials

type Bernstein
    n::Integer
    i::Integer
    α::Real
    β::Real
end
Bernstein(n, i) = Bernstein(n, i, 0., 1.)

Base.string(B::Bernstein) = "Bernstein $(get_p(B))"
Base.show(io::IO, B::Bernstein) = print(io, string(B))
Base.display(io::IO, B::Bernstein) = print(io, string(B))

function get_p(n, i, α=0, β=1)
    @assert β >= α "Invalid interval"
    return (binomial(n, i)
            * poly([α for _ in 1:i])
            * poly([β for _ in 1:(n - i)])
            * (-1)^(n - i)
            / (β - α)^n)
end
get_p(B::Bernstein) = get_p(B.n, B.i, B.α, B.β)

function ∫(p::Poly, α=NaN, β=NaN)
    integrated = polyint(p)
    if isequal(α, NaN) || isequal(β, NaN)
        return integrated
    else
        return integrated(β) - integrated(α)
    end
end

function inner_product(p::Poly, q::Poly, α=0., β=1.)
    @assert β >= α "Invalid interval"
    ∫(p * q, α, β)
end

function inner_product(B::Bernstein, Q::Bernstein)
    @assert B.α >= Q.α "Invalid interval"
    @assert B.β >= Q.β "Invalid interval"
    m, i, n, j, α, β = B.n, B.i, Q.n, Q.i, B.α, B.β
    (β - α)binomial(m, i)binomial(n, j) / ((m + n + 1)binomial(m + n, i + j))
end

# QUESTION: Is it possible to automatically account for commutativity?
(inner_product(p::Poly, B::Bernstein)
 = inner_product(B::Bernstein, p::Poly)
 = inner_product(B.p, p::Poly))

function Base.LinAlg.norm(q::Poly, α=0., β=1.)
    @assert β >= α "Invalid interval"
    √inner_product(q, q) / (β - α)
end

function Base.LinAlg.norm(B::Bernstein)
    √inner_product(B, B) / (B.β - B.α)
end

B = Bernstein(3, 2)
Q = Bernstein(4, 3)

inner_product(B, Q)
norm(B)

The below code uses Julia 1.0.  Full code as a Pkg3 project is available here.

Preliminaries

There's enough code for it to get its own module.  This also makes testing easier.

module Bernstein

using Polynomials

import Base: convert, promote_rule, show
import LinearAlgebra: dot, norm
import Polynomials: poly

Since we're in a module, we must define the exported things.  Since most of the things is just
overloaded methods, only the type remains.

export BernsteinPoly

You do this check so often, we can factor it out.  Alternative: using a separate type
for intervals.

macro checkinterval(α, β)
    :(@assert $(esc(α)) <= $(esc(β)) "Invalid interval")
end

Parametrization by a constrained type is better than fields of an abstract type.  But in the case of n and i, concrete Ints make more sense, since they represent natural numbers
always (this makes conversions below easier).
And I'm calling it BernsteinPoly, since it is a variant of Poly.

struct BernsteinPoly{T<:Number}
    n::Int
    i::Int
    α::T
    β::T
end

BernsteinPoly(n, i) = BernsteinPoly(n, i, 0.0, 1.0)

Just implementing show using print is the recommended way for custom pretty-printing. Here, we can reuse Polynomials.printpoly for nicer and more consistent formatting:

function show(io::IO, b::BernsteinPoly)
    print(io, "BernsteinPoly(")
    Polynomials.printpoly(io, poly(b))
    print(io, ")")
end

Conversions

get_p was essentially the conversion from BernsteinPoly to Poly.  We can replace this
by the implementation of proper convert methods.  The default parameters are unnecessary,
since already occuring defaulted in the BernsteinPoly constructor.

function convert(::Type{Poly{S}}, b::BernsteinPoly) where {S<:Number}
    n, i, α, β = b.n, b.i, convert(S, b.α), convert(S, b.β)
    @checkinterval α β

    return (binomial(n, i)
            * poly(fill(α, i))     # `fill` instead of list comprehension
            * poly(fill(β, n - i))
            * (-1)^(n - i)
            / (β - α)^n)
end

This allows you to just say convert(Poly, b), automatically reusing the inner type of b

convert(::Type{Poly}, b::BernsteinPoly{T}) where {T<:Number} =
    convert(Poly{T}, b)

While we're at it: conversion between different BernsteinPoly values

convert(::Type{BernsteinPoly{S}}, b::BernsteinPoly) where {S<:Number} =
    BernsteinPoly(b.n, b.i, convert(S, b.α), convert(S, b.β))

If we're handling different representations, we sometimes need to determine the "most general"
form, which is called promotion:

promote_rule(a::Type{BernsteinPoly{S}}, b::Type{Poly{T}}) where {S<:Number, T<:Number} =
    Poly{promote_type(S, T)}

promote_rule(::Type{BernsteinPoly{S}}, ::Type{BernsteinPoly{T}}) where {S<:Number, T<:Number} =
    BernsteinPoly{promote_type(S, T)}

Also add a method to the poly smart constuctor, which is now trivial:

poly(b::BernsteinPoly) = convert(Poly, b)

Linear Algebra

Now to the linear algebra part.  We could add methods to dot and norm from LinearAlgebra:

function dot(p::Poly{T}, q::Poly{T}, α = zero(T), β = one(T)) where {T<:Number}
    @checkinterval α β
    polyint(p * q, α, β)
end

And the norm induced by that inner product:

function norm(q::Poly{T}, α = zero(T), β = one(T)) where {T<:Number}
    @checkinterval α β
    √dot(q, q, α, β) / (β - α)
end

But such "overloads from outside" are frowned upon.  As of writing this, there's a norm method
in Polynomials, but not dot.  There's an issue about that; basically, dot is not
unique, hence we need to specify the intervals each time here.

For Bernstein polynomials, on the other hand, the inner product is defined uniquely, if I
understood correctly.

function dot(b::BernsteinPoly{T}, q::BernsteinPoly{T}) where {T<:Number}
    @checkinterval b.α q.α
    @checkinterval b.β q.β
    m, i, n, j, α, β = b.n, b.i, q.n, q.i, b.α, b.β
    (β - α) * binomial(m, i) * binomial(n, j) / ((m + n + 1) * binomial(m + n, i + j))
end

And the induced norm, as before.

function norm(b::BernsteinPoly)
    √dot(b, b) / (b.β - b.α)
end

As the last remaining question, how to do cross-type inner products.  If dot is defined for
Poly as written above, we can use dot(promote(p, q)..., α, β).  But it's difficult to get
that working as a method.  I tried

dot(p::Union{Poly{T}, BernsteinPoly{T}}, q::Union{Poly{T}, BernsteinPoly{T}},
     α = zero(T), β = one(T)) where {T<:Number} =
     dot(promote(p, q)..., α, β)

but that doesn't work.  It's probably not recommended to do that anyway.  Use promote
explicitely where necessary.

Example output

julia> B = BernsteinPoly(3, 2)
BernsteinPoly(3.0*x^2 - 3.0*x^3)

julia> Q = BernsteinPoly(4, 3)
BernsteinPoly(4.0*x^3 - 4.0*x^4)

julia> using LinearAlgebra

julia> dot(B, Q)
0.07142857142857142

julia> norm(B)
0.29277002188455997

end # module


How clean is my snow? I just wrote a snow animation in Python. I think this is fairly clean but I have a few things that I don't like.

from random import randrange
import time

# Snow animation
# Snow is simply the `#` symbol here. Half of the snow moves at 1 char
# per frame, while the other half moves at 0.5 chars per frame. The
# program ends when all the snow reaches the bottom of the screen.
# The viewing area is 80x25. It puts 100 snow flakes to output, half
# fast, and half slow. Every frame it dispenses 4 flakes, 2 fast and
# 2 slow ones, at random locations at the top of the viewing area.

screen = {'x': 80, 'y': 20}
drops = []

def createRainDrop(x, y, speed):
    return {'x': x, 'y': y, 'speed': speed}

def createRandomDrops():
    dropCount = 4
    for i in range(dropCount):
        yield createRainDrop(randrange(0, screen['x']), 0, min((i % 2) + 0.5, 1))

def moveDrops():
    for drop in drops:
        speed = drop['speed']
        drop['y'] = drop['y']+speed

def drawDrops():
    out = [''] * screen['y']
    for y in range(screen['y']):
      for x in range(screen['x']):
        out[y] += '#' if any([drop['x'] == x and int(drop['y']) == y for drop in drops]) else ' '

    return '\n'.join(out)

def dropsOnScreen():
    return any([drop['y'] < screen['y'] for drop in drops])

drops += createRandomDrops()

while dropsOnScreen():
    if len(drops) < 100:
        drops += createRandomDrops()

    print(drawDrops())
    moveDrops()
    time.sleep(0.100)

For example, I don't know how to remove the duplicate line drops += createRandomDrops(), and drawDrops() feels a bit like a hack.

I confess! While writing this it was rain, not snow!

Let's look at the code.

from random import randrange
import time

Your imports are very minimal! Good.

# Snow animation
# Snow is simply the `#` symbol here. Half of the snow moves at 1 char
# per frame, while the other half moves at 0.5 chars per frame. The
# program ends when all the snow reaches the bottom of the screen.
# The viewing area is 80x25. It puts 100 snow flakes to output, half
# fast, and half slow. Every frame it dispenses 4 flakes, 2 fast and
# 2 slow ones, at random locations at the top of the viewing area.

This looks more like a docstring to me. It would be nice to render it as such. You can do this by dropping the # signs, and surrounding it in """ quotes.

screen = {'x': 80, 'y': 20}
drops = []

Global variables are not that nice. But this is a simple file, so maybe we can leave it like this for now? Let's.

def createRainDrop(x, y, speed):
    return {'x': x, 'y': y, 'speed': speed}

I think something like a class would be better for this. Let's try

class RainDrop(object):
    def __init__(self, x, y, speed):
        self.x = x
        self.y = y
        self.speed = speed

Of course, now we need to replace createRainDrop(...) with RainDrop(...), and drop['...'] with drop.....

def createRandomDrops():
    dropCount = 4
    for i in range(dropCount):
        yield RainDrop(randrange(0, screen['x']), 0, min((i % 2) + 0.5, 1))

That's better.

def moveDrops():
    for drop in drops:
        drop.y = drop.y + drop.speed

We're modifying drop here, instead of asking it to modify itself. We should be writing something like drop.moveDown() here, or maybe drop.tick() ('tick' is what's commonly used to notify an event about stepping forward in time).

def drawDrops():
    out = [''] * screen['y']
    for y in range(screen['y']):
      for x in range(screen['x']):
        out[y] += '#' if any([drop.x == x and drop.y == y for drop in drops]) else ' '

    return '\n'.join(out)

Here, for all the positions on the screen, you're looping over all the drops. Ideally we'd turn that around:

def drawDrops():
    out = [[' ' for _ in range(screen['x'])] for _ in range(screen['y'])]
    for drop in drops:
        if int(drop.y) < screen['y']:
            out[int(drop.y)][drop.x] = '#'

Now that's a bit faster and cleaner.

def dropsOnScreen():
    return any([drop.y < screen['y'] for drop in drops])

Makes sense. Except I'd suggest to not use the [...], which creates a list. Better to use

def dropsOnScreen():
     return any(drop.y < screen['y'] for drop in drops)

This behaves the same, but does not have to create an intermediate list.

drops += createRandomDrops()

while dropsOnScreen():
    if len(drops) < 100:
        drops += createRandomDrops()

    print(drawDrops())
    moveDrops()
    time.sleep(0.100)

You want to get rid of the duplicated call to drops += createRandomDrops().

while True:
    if len(drops) < 100:
        drops += createRandomDrops()

    if not dropsOnScreen():
        break

    print(drawDrops())
    moveDrops()
    time.sleep(0.100)

But in my opinion, the extra createRandomDrops is not that bad.


Combination generator in Java (See the next iteration.)

Given a positive \$N\$, the following class generates all possible non-empty sets \$A \in \mathcal{P}(\{0, 1, \dots, N - 1\})\$ in lexicographic order. Also, it provides a method that can be used to copy a combination to a list. I am seeking primarily guidance regarding the API design of the class.

CombinationGenerator.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class CombinationGenerator<T> {

    /**
     * The array holding indices to elements considered to be in a combination.
     * Only the first {@code k} indices are considered actually to encode an
     * item in a combination.
     */
    private final int[] indexArray;

    /**
     * The current number of items in a combination.
     */
    private int k;

    public CombinationGenerator(int totalNumberOfItems) {
        checkTotalNumberOfItems(totalNumberOfItems);
        this.indexArray = new int[totalNumberOfItems];
    }

    public boolean generateNextCombination() {
        if (k == 0) {
            k = 1;
            return true;
        }

        if (indexArray[k - 1] < indexArray.length - 1) {
            indexArray[k - 1]++;
            return true;
        }

        for (int i = k - 2; i >= 0; --i) {
            if (indexArray[i] < indexArray[i + 1] - 1) {
                indexArray[i]++;

                for (int j = i + 1; j < k; ++j) {
                    indexArray[j] = indexArray[j - 1] + 1;
                }

                return true;
            }
        }

        ++k;

        if (k > indexArray.length) {
            return false;
        }

        for (int i = 0; i < k; ++i) {
            indexArray[i] = i;
        }

        return true;
    }

    public void loadCombination(List<T> all, List<T> target) {
        Objects.requireNonNull(all, "The list being sampled is null.");
        Objects.requireNonNull(target,
                               "The list to hold the combination is null.");

        target.clear();

        for (int i = 0; i < k; ++i) {
            target.add(all.get(indexArray[i]));
        }
    }

    private void checkTotalNumberOfItems(int totalNumberOfItems) {
        if (totalNumberOfItems < 1) {
            throw new IllegalArgumentException(
                    "Total number of items is illegal: " +
                    totalNumberOfItems + ".");
        }
    }

    public static void main(final String... args) {
        List<String> all = new ArrayList<>();

        all.add("A");
        all.add("B");
        all.add("C");
        all.add("D");
        all.add("E");

        int row = 1;
        List<String> combinationHolder = new ArrayList<>();
        CombinationGenerator generator = new CombinationGenerator(all.size());

        while (generator.generateNextCombination()) {
            generator.loadCombination(all, combinationHolder);
            System.out.printf("%2d: %s\n", row++, combinationHolder);
        }
    }
}

CombinationGeneratorTest.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class CombinationGeneratorTest {

    private CombinationGenerator generator;

    @Test
    public void test() {
        List<String> all = new ArrayList<>();
        List<String> target = new ArrayList<>();

        all.add("A");
        all.add("B");
        all.add("C");
        all.add("D");
        all.add("E");

        for (int i = 1; i <= all.size(); ++i) {
            int combinations = pow2(i) - 1;
            int count = 0;

            generator = new CombinationGenerator(i);

            while (generator.generateNextCombination()) {
                count++;
            }

            assertEquals(combinations, count);
        }
    }

    private static int pow2(int exp) {
        return 1 << exp;
    }
}

Consider the iterator pattern with the methods hasNextCombination() and nextCombination(). Let your implementation follow the implications. Maybe you have to introduce a buffer. The loadCombination()-method inverts the responsibility and let you do strange things like clearing the given list if the client gives you messy data. The standard iterator pattern is the way to go. Pass your list of elements to the constructor of your Iterator. Make defensive copies to avoid side effects. Return the combination of the elements directly. The Client should be responsible to collect them in a list.
Even this suggestion will be obsolete (1.). Do not check for "null" values. If the client gives you "null" then he should expect that the program will not work properly. Giving up the responsibility of the client to not pass null values has serious consequences for your source code. You will end up checking everything for null because you cannot count on anything. There are some exceptions to that which should be known: The parent of the root of a hierarchy may be null, lazy initialization is dealing with null and son find()-methods may return null that has to be evaluated immediatly. In all other cases: Never pass null, never check null and never return null.
Break the generateNextCombination()-method into smaller pieces. If you experience problems then it surely has to do with the multiple return statements. Multiple return statements will hinder you to apply refactorings like "extract method". Furthermore: extending your code is much more predictable. Avoid multiple return statements in a method. Provide a proper control flow until the end of the method.
As a matter of common usage do not use ++k. Use k++ instead. You yourself are switching between suffix and prefix notation. Keep doing one thing consistently to have the least surprise. Do not forget to adapt your breaking conditions.
As it is used in the test, do not take my suggestion too serious here but: Avoid using bit shifting. I do not event know if there is a significant speed up. After all it doesn't matter until your application critical on this. And most of the applications aren't. The reason is you introduce low level language structures in a high level language.


Concatenate the square of all the digits of a number Task: given a number (positive or negative), square every digit of it and concatenate them, forming a resulting number.

For example:

9119 should become 811181 = 9^2*10^0 + 1*10^1 + 1*10^2 + 9^2*10^3
(-1) should become (-1)

My code:

-- convert a number to the list of digits
-- doesn't work with negative numbers
digs :: Integral x => x -> [x]
digs 0 = [0]
digs x = let
      helper :: Integral x => x -> [x]
      helper 0 = []
      helper n = helper (n `div` 10) ++ [n `mod` 10]
  in
      helper x

squareDigit :: Int -> Int
squareDigit n = let sign = signum n
                    digits = (digs (abs n))
                    digs_sq = map (^ 2) digits
                    -- we can't concat squares as they may have more then 1 digit
                    digs_sq_flat = map digs digs_sq >>= id
                in
                  sign * foldl (\acc x -> x + (acc * 10)) 0 digs_sq_flat

Basically, it works:

*SquareDigit> squareDigit 9119
811181
*SquareDigit> squareDigit (-9119)
-811181

But maybe, my solution can be made more elegant.

Separate out combinators that apply some perspective to your data.

squareDigit = overAbs $ overDigits $ concatMap $ digs . (^ 2) where
  overAbs f n = signum n * f (abs n)
  overDigits f = foldl (\acc x -> x + (acc * 10)) 0 . f . digs


Two string comparison I wrote a function that finds the difference between two strings. This only works given that the difference is continuous.

Beyond doubt this already exists, I am recreating this for educational purposes. I would like feedback about my performance and efficiency.

Examples of this method:

String difference = Difference("Hello", "Hello world!");
//difference would be " world!"

String difference = Difference("Removing text", "Removi");
//difference would be "ng text"

String difference = Difference("same size", "SAME size");
//difference would be "SAME"

public static String Difference(String string1, String string2)
{
    int size = string2.length() - string1.length();
    if(size < 0)
    {
        size *= -1;
        String swap = string1;
        string1 = string2;
        string2 = swap;
    }
    String difference = "";
    int start = DifferenceStartIndex(string1, string2);
    if(size > 0)
        for(int i = start; i < start + size; i++)
            difference += string2.charAt(i);
    else
    {
        if(start != -1)
        {
            int end = DifferenceEndIndex(string1, string2, start);
            for(int i = start; i < end; i++)
                difference += string2.charAt(i);
        }
        else
            return "";
    }
    return difference;
}

public static int DifferenceStartIndex(String string1, String string2)
{
    int maxSize = (string1.length() > string2.length()) ? string1.length() : string2.length();
    for(int i = 0; i < maxSize; i++)
        if(((i < string1.length()) ? string1.charAt(i) : '\0') != ((i < string2.length()) ? string2.charAt(i) : '\0'))
            return i;
    return -1;
}

public static int DifferenceEndIndex(String string1, String string2, int start)
{
    int maxSize = (string1.length() > string2.length()) ? string1.length() : string2.length();
    int end = maxSize;
    for(int i = start; i < maxSize; ++i)
        if(string1.charAt(i) != string2.charAt(i))
            end = i + 1;
    return end;
}

Conventions
In java, methods begin with a lowercase letter.
Design
Methods should be private unless they are required by clients. In this case, only the difference() method should be public.
Implementation
There are a few things to look at here. First, your code is made much more complex by swapping around the two inputs based on size. It would be neater if you did the size comparison once, then called a helper method with parameters shorterString and longerString.
Your two size methods are clunky because they don't return early when they find a (mis)match, and because they run off of the longer string rather than the shorter string.
There may be a slight performance gain to be made if the two strings are frequently equal. In that case only, it may be faster to check if the two strings are equals() and return -1 from differenceStartIndex() right away. In your particular case, I highly doubt this check would be anything more than clutter.
Applying these changes might make the code look something like:
public final class Difference {

    public static String difference(final String string1, final String string2) {
        if (string1.length() <= string2.length()) {
            return differenceHelper(string1, string2);
        }
        return differenceHelper(string2, string1);
    }

    private static String differenceHelper(final String shorterString, final String longerString) {
        final int start = differenceStartIndex(shorterString, longerString);
        if (start < 0) {
            return "";
        }
        final int end = differenceEndIndex(shorterString, longerString, start);
        return longerString.substring(start, end);
    }

    private static int differenceStartIndex(final String shorterString, final String longerString) {
        for (int i = 0; i < shorterString.length(); i++) {
            if (shorterString.charAt(i) != longerString.charAt(i)) {
                return i;
            }
        }

        if (shorterString.length() == longerString.length()) {
            return -1;
        }

        return shorterString.length();
    }

    private static int differenceEndIndex(final String shorterString, final String longerString, final int startIndex) {
        for (int i = startIndex; i < shorterString.length(); i++) {
            if (shorterString.charAt(i) == longerString.charAt(i)) {
                return i + 1;
            }
        }
        return longerString.length();
    }

    public static void main(final String[] argv) {
        System.out.println(Difference.difference("Hello", "Hello world!"));
        System.out.println(Difference.difference("Removing text", "Removi"));
        System.out.println(Difference.difference("same size", "SAME size"));

    }
}


Get the first positive value that does not exist in array function solution(A) {
    var len = A.length;
    if(len > 1){
        let max = Math.max.apply(null, A);
        let range = Array.from(Array(max).keys());
        for(let i = 0; i < range.length; i++){
            if(A.includes(range[i]) === false){
                if(range[i] > 0){
                    return range[i];
                }
                continue;
            }
            continue;
        }
        return max + 1;
    }else if(len == 1 && (A[0] < 1 || A[0] > 1)){
        return 1;
    }else if((len == 1) && (A[0] == 1)){
        return 2;
    }
    return 1;
}

This is mainly used to get the first positive value that does not exist in sequence of integers in an array.

There is a time complexity of O(N ** 2).

Can it be better than this?

If there is no better complexity, can we optimize the for loop better than that?

Review

There are 3 answers already, yet none have addressed the flaws or reviewed your code.

Thus I will give a detailed review and an alternative solution

Your solution has bugs that make a estimation of complexity impossible.

To help review your code I have numbered the lines. See Snippet (B) for line numbers

Flaws AKA bugs

There are many cases where your code can not run. 3 different errors the last is the worst type of error uncatchable.

solution([-1,-2]) will throw an error.
solution([1,2e100]) will throw an error.
solution([1,2**31]) will crash the page after a long hangup on all but the top end machines.

Your code is not \$\mathcal{O}(n^2)\$ but rather it is incomplete or if run on a perfect machine \$\mathcal{O}(\infty)\$ (and same storage) as that is the largest number that the function Math.max can return.

Or if you have a max value less than the array size max then the complexity is \$\mathcal{O}(2^{m+1})\$ where \$m\$ is the max value in the array.Thus the complexity for input [1,2**32-1] is a whopping \$\mathcal{O}(n^{33})\$ and storage of \$\mathcal{O}(n^{32})\$

By the lines

The following numbered items (bold numbers 1) refer to your source code by line number

1 A is a very poor name, arr, array, nums, numbers or many more. Even a would be better as we do not capitalize variable names unless they are instantiatable objects defined as functions or using the class syntax.
2 len should be a constant. eg const len as it  is not to be reassigned at any point in the code.
3, 16 and 17. The if statements can be rearranged to reduce complexity.
4 max should be a constant. Its almost 2019 and the spread operator ... has been available for 4 years, Use it!!! Line 4 becomes const max = Math.max(...A);
5 Use constant const range =. You create an array of indexes from 0 to max. Which is a major problem, (See intro above) The irony is that you can (and do) calculate all the values from 0 to max via the for loop on the next line making line 7.  A.include(range[i]) is identical to A.include(i)
6 range.length is the same as max so use the shorter form for (let i = 0; i < max; i ++) {
7 Use the shorter form for not true if (! A.includes(range[i])) {
8 Use the shorter form is truthy. All numbers  !== 0 are truthy true thus this line can be if (range[i]) {
9 Could be return i;
11 and line 13 the continue is not needed as you are at the bottom of the for loop at those lines already.
16 Use the strict equality operator len === 1. use the shorter not form of  val < value || val > value as val !== value, making the line } else if (len === 1 && A[0] !== 1) {
18 Use the strict equality operators, There is no need for the  () around each clause } else if (len === 1 && A[0] === 1) {

General points.

If you return inside a statement block, you should not include the else at the end as It will never be used. Thus lines 16 and 17 do not need the else and can be moved down one line (away from the closing })
Though not a must it is cleaner to put spaces after for, if, else etc, before else, between ){
When you find you are needing to search a set of values repeatedly it pays to consider using a Map or Set to find the matches as they use a hash to lookup values and have a complexity of \$\mathcal{O}(1)\$ for the search, however to create the lookups is \$\mathcal{O}(n)\$. Thus using a Map or Set you can easily reduce complexity from \$\mathcal{O}(n^2)\$ to \$\mathcal{O}(n)\$. There is a storage penalty meaning you can go from \$\mathcal{O}(1)\$ to \$\mathcal{O}(n)\$.

Rewriting you code

Using a Set to remove the \$\mathcal{O}(n)\$ overhead of each Array.includes

The Set positiveInts can be created as we iterate the array, saving a little complexity.

I assume array items are less than or equal to Number.MAX_SAFE_INTEGER

Snippet (A)

function solution(array) {
    var min = 1;
    if (array.length === 1) {
        min = array[0] === 1 ? 2 : min;
    } else if (array.length) {
        const positiveInts = new Set();
        for (const val of array) {
            if (val > 0) {
                positiveInts.add(val);
                if (val === min) {
                    while (positiveInts.has(min)) { min ++ }
                }
            }
        }
    }
    return min;
}

Snippet (B)

/*lines*/
/* 1*/function solution(A) {
/* 2*/    var len = A.length;
/* 3*/    if(len > 1){
/* 4*/        let max = Math.max.apply(null, A);
/* 5*/        let range = Array.from(Array(max).keys());
/* 6*/        for(let i = 0; i < range.length; i++){
/* 7*/            if(A.includes(range[i]) === false){
/* 8*/                if(range[i] > 0){
/* 9*/                    return range[i];
/*10*/                }
/*11*/                continue;
/*12*/            }
/*13*/            continue;
/*14*/        }
/*15*/        return max + 1;
/*16*/    }else if(len == 1 && (A[0] < 1 || A[0] > 1)){
/*17*/        return 1;
/*18*/    }else if((len == 1) && (A[0] == 1)){
/*19*/        return 2;
/*20*/    }
/*21*/    return 1;
/*22*/}


LSD radix sort (force avoid div or idiv compiler instruction) in C++ I was trying to optimize the Radix Sort code, just because. Nothing more, nothing less. Here it is!!! So tell me, how does it look?
Summary:

instead of a div or mod ,i use left shift and right shift to avoid div or idiv compiler instruction.

the dual instruction is for avoiding jumps and the usual stuff.

btw you can do arr pointer with same code just change obj_arr*&arr with obj_arr**&arr and add some function to the class obj_arr to get unsigned int
example: arr[i]->get_unsigned_int().
or operator if that you like.
postdata: take in mind you are using arr of obj class.
#pragma once
#define modpow2(num,div_pow2,mod_pow2)  (num>>div_pow2) - (num >> mod_pow2+div_pow2 << mod_pow2)

template<class obj_arr>
unsigned int getmax(obj_arr*& arr, size_t& size);

template<class obj_arr>
void countrad(obj_arr*& arr, obj_arr*& aux_arr, size_t& size, unsigned int*& count, const unsigned int& mod_pow2, const unsigned int& div_pow2);

template<class obj_arr>
void radix_sort_ftl(obj_arr* arr, size_t size, unsigned int mod_pow2 = 4);

template<class obj_arr>
unsigned int getmax(obj_arr*& arr, size_t& size) {

    size_t i = modpow2(size,0,1);
    unsigned int aux=arr[0];
    for (; i < size; i += 2) {
        aux = arr[i] * (aux < arr[i]) + aux * (aux >= arr[i]);
        aux = arr[i + 1] * (aux < arr[i + 1]) + aux * (aux >= arr[i + 1]);
    }
    return aux;
}

template<class obj_arr>
void radix_sort_ftl(obj_arr* arr, size_t size, unsigned int mod_pow2) {
    unsigned int max = getmax(arr, size) + 1;
    obj_arr* aux_arr = new obj_arr[size];
    unsigned int* count = new unsigned int[1<< mod_pow2 + 1];

    for (unsigned int divpow2 = 0; max > (1<< divpow2); divpow2 += mod_pow2){
        countrad(arr,aux_arr,size,count,mod_pow2, divpow2);
    }

    delete[] aux_arr;
    delete[] count;

}

template<class obj_arr>
void countrad(obj_arr*& arr, obj_arr*& aux_arr, size_t& size, unsigned int*& count, const unsigned int& mod_pow2, const unsigned int& div_pow2) {

    unsigned int i, move,max_mod=1<<mod_pow2;

    i = modpow2(max_mod + 1,0,1);
    count[0] = 0;
    for (; i < max_mod + 1; i += 2) {
        count[i] = 0;
        count[i + 1] = 0;
    }

    i = modpow2(size, 0, 1);
    count[modpow2(arr[0],div_pow2,mod_pow2)+ 1] += i;
    for (; i < size; i += 2) {
        count[modpow2(arr[i], div_pow2, mod_pow2) + 1]++;
        count[modpow2(arr[i+1], div_pow2, mod_pow2) + 1]++;
    }

    i = modpow2(max_mod + 2, 0, 1) + 1;
    for (; i < max_mod + 1; i += 2) {
        count[i] += count[i - 1];
        count[i + 1] += count[i];
    }

    i = modpow2(size, 0, 1);
    move = modpow2(arr[0], div_pow2, mod_pow2);
    aux_arr[count[move]] = arr[0];
    count[move] += i;
    for (; i < size; i += 2) {
        move = modpow2(arr[i], div_pow2, mod_pow2);
        aux_arr[count[move]] = arr[i];
        count[move]++;

        move = modpow2(arr[i+1], div_pow2, mod_pow2);
        aux_arr[count[move]] = arr[i + 1];
        count[move]++;
    }

    i = modpow2(size, 0, 1);
    arr[0] = aux_arr[0];
    for (; i < size; i += 2) {
        arr[i] = aux_arr[i];
        arr[i + 1] = aux_arr[i + 1];
    }
}

```

Avoid macros
There is no need to make modpow2 a macro. Make it a  function instead:
static constexpr size_t modpow2(size_t num, size_t div_pow2, size_t mod_pow2) {
    return (num >> div_pow2) - (num >> (mod_pow2 + div_pow2) << mod_pow2);
}

Avoid forward declarations
You should not need to write forward declarations, unless you have circular dependencies between functions. Otherwise, they are unnecessary code duplication, and there is a potential for mistakes that is better avoided.
Be consistent with the template type
You made your functions templates, so I assume you want to be able to run radix sort on arrays of various types. However, I see code like this:
unsigned int aux = arr[0];

What if I have an array of unsigned long instead? Or float? When you make a template, you want to avoid making assumptions about the type of the variables. So either use the template type name:
obj_arr aux = arr[0];

Or better yet, just use auto when possible:
auto aux = arr[0];

Also use this for the return type. So:
template<class obj_arr>
auto getmax(obj_arr*& arr, size_t& size) {
    auto aux = arr[0];
    ...
    return aux;
}

When to pass by reference
You should only pass large objects by reference. Small objects, like pointers and primitive types like int and size_t should be passed by value if possible. So:
template<class obj_arr>
auto getmax(obj_arr* arr, size_t size) {
    ...
}

If you always use references, you risk adding unnecessary pointer indirection to your code.
Use const where appropriate
You should mark pointers and references as const when possible, since that might allow the compiler to generate better code, and it will also give a compiler error if you accidentily do modify a value that should be constant. So:
template<class obj_arr>
auto getmax(const obj_arr* arr, size_t size) {
    ...
}

You can even be more strict and also make the parameter size_t size const, and even local variables like max_mod inside countrad().
Use size_t consistenly for counts and indices
Don't use unsigned int for counts, unless you are absolutely sure you will never have to deal with arrays with more elements than can be counted in whatever an unsigned int might be on all the platforms you want to support.
Use idiomatic for-loops
Why have you moved the initializer statement out of all your for-loops? In most cases this does not seem necessary at all. Just write for-loops like you normally do:
auto aux = arr[0];

for (i = modpow2(size, 0, 1); i < size; i += 2) {
    aux = arr[i] * (aux < arr[i]) + aux * (aux >= arr[i]);
    aux = arr[i + 1] * (aux < arr[i + 1]) + aux * (aux >= arr[i + 1]);
}

Avoid premature optimization
Your implementation of getmax() seems to be written to avoid conditional jumps. However, many architectures have conditional move instructions that will be able to perform a maximum operation without needing conditional jumps. And this is much cheaper than two multiplication operations. Instead of calling getmax(), I would just use std::max_element() like so:
auto max = *std::max_element(arr, arr + size) + 1;

Let the compiler worry about optimizing this. If you really want to be sure, measure the speed of your radix sorting function when using your getmax() vs. when using std::max_element().
Also, in general the compiler will be able to optimize multiplication and division by constants for you, and will convert them to shifts if it sees they are powers of two. However, there are a few places where you call modpow2() with variable divisors, so it does make sense to explicitly use shifts here.
Use std::unique_ptr to manage allocated memory
It's best to avoid calling new and delete manually, and use smart pointers that do this for you. This avoids potential mistakes such as leaking memory or deleting something twice. If you can use C++14, then use std::make_unique() to create an array for you, like so:
auto aux_arr = std::make_unique<obj_arr[]>(size);
auto count = std::make_unique<size_t[])(1 << mod_pow2 + 1);

If you are stuck with an older version, you still need to use new:
std::unqiue_ptr<obj_arr> aux_arr = new obj_arr[size];
std::unique_ptr<size_t> count = new size_t[1 << mod_pow2 + 1];

But at least you don't have to call delete anymore. You could also use std::vector for even cleaner looking code, but then you lose a bit of performance due to the initialization of the elements.
Naming things
The names of your variables and functions are inconsistent and sometimes misleading. For example, choose whether you want to use underscores to separate words (which I recommend) or not, and stick with that choice.
The name obj_arr suggests that the type is an array, but actually it's the type of the array elements. In any case, I would use the more idiomatic T for this:
template<typename T>
auto getmax(const T* arr, size_t size) {
    ...
}

The word count suggests it is a single value, but actually it is an array. I recommend you use the plural form of a noun for arrays, or append _arr like you do with aux_arr for example.


Random tone generator using Web Audio API This is a random frequency audio generator made with the Web Audio API by Mozilla. The end-goal is an audio frequency trainer: the website plays an audio frequency and the user tries to guess which frequency it is. The frequencies will be limited to those found on 31 band graphical equalisers, and I'll include multiple difficulties.

This is my first step: the generator for the 'easy' difficulty (4 frequencies).

// create web audio api context
var audioCtx = new AudioContext();

// create oscillator (tone) and gain (volume) node
var tone = audioCtx.createOscillator();
var volume = audioCtx.createGain();

// create array of frequency values
var frequencies = ["100", "400", "1600", "6300"];
// pick a random frequency
var frequency = frequencies[Math.floor(Math.random() * frequencies.length)];

// set oscillator type (sine, square, sawtooth or triangle)
tone.type = 'sine';
// set oscillator frequency in Hz
tone.frequency.value = frequency;
// set gain volume (above 1 will clip)
volume.gain.value = 0.5;

// set tone destination to go through volume
tone.connect(volume);
// set volume destination to output
volume.connect(audioCtx.destination);

// start oscillator x seconds after timestamp
tone.start(1);
// stop oscillator x seconds after timestamp
tone.stop(4);

Don't mind the excessive commentation, I've only just started using JavaScript and don't trust myself to remember what every line of code does after a few days.

Reusable code

You code is not very flexible, and the frequencies somewhat arbitrary and spanning a large 6 octaves.

You can encapsulate the code in a function that creates an object you use to play the random tone as needed, allowing you to add features as you need.

Note friendly

Consider using standard musical notes rather than random frequencies.

To get the frequency of a note you use the expression

freq = 2 ** (note / 12) * 440;

where note is the number of semi tones from A4 440Hz. So to find C4 which is 3 notes up  2 ** (3 / 12) * 440;

To get the closest note to a frequency you use

note = Math.round(Math.log2(freq / 440) * 12);

Basic example

The example creates that object randomNotes and plays musical notes rather than random tones.

const randomNotes= (() => {

    /* Create the objects needed to play a tone */
    const audio = new AudioContext();
    const volume = audio.createGain();
    volume.gain.value = 0.5;
    volume.connect(audio.destination);

    /* Function to calculate frequency of a note starting at A4 and stepping semi tones*/
    const freq = note => 2 ** (note / 12) * 440; // 440 is the frequency of A4
    const randomNote = () => notes[Math.random() * notes.length | 0]; // the bitwise Or does the same as Math.floor
    const notes = [-25, -2, 22, 46]; // Close to your 100, 400, 1600 and 6300

    /* Create and return the object that is the randomNote */
    return {
        play(startIn = 1, playFor = 4) { // startIn and playFor is time in seconds
            const now = audio.currentTime;
            const oscillator = audio.createOscillator();
            oscillator.type = "sine";
            oscillator.connect(volume);
            oscillator.frequency.value = freq(randomNote());
            oscillator.start(now + startIn);
            oscillator.stop(now + startIn + playFor);
        }
    };
})();

Then to play a random note just call

randomNotes.play();

or playing two tones

randomNotes.play();
setTimeout(randomNotes.play, 6000);

or overlapping tones

randomNotes.play();
setTimeout(randomNotes.play, 3000); // starts half way through the first

Reusing the code

The Advantages of using this approch is that it becomes very easy to extend the functionality. Say you want to add volume control, or be able to add notes to the random list, just add a setter to the object returned,

// from above snippet
/* Create and return the object that is the randomNote */
return {
    set volume(value) { volume.gain.value = value },
    set note(value) { notes.push(value) }

    // continue on from above snippet
    play(startIn = 1, playFor = 4) { ...

You can then set the volume in a more abstract way and add notes to the random set with ease.

randomNotes.note = 12; // Add note A5 to the random set
randomNotes.volume = 0.8; // Increase the volume

More sound.

You will notice that there is a new oscillator created each time, and that the audio context's current time continues to tick. It is much more efficient to create one oscillator and change its frequency as needed and using timers to change the volume to start stop the sound. An oscillator can not restart after it has been stopped.

But this is not the best either as the audio context can chew some serious power and CPU even when not playing sound (On some audio hardware). Ideally you suspend the audio context and resume it as needed, in conjunction to using the gain control to start and stop the oscillator, as the audio context can sometimes be a little slow when suspending .

Personally I would create this type of thing using an audio buffer and just write the waveform directly to the buffer then play it.


How to optimize bitwise get/set/clear of ranges of bits on 8-bit integers in JavaScript? I have been working for a few days on writing get, set, and clear bitwise functions in JavaScript to clear not individual bits from an integer n, but to clear entire ranges of bits in n.
For example, using the functions below, I would expect this behavior:
getNumBits(0b101) // 3
getNumBits(0b10100000) // 8

// getBitRange(integer, startIndex, size)
getBitRange(0b101110010001111, 1, 4) // 1110
getBitRange(0b101110010001111, 5, 7) // 1

// setBitRange(integer, startIndex, value)
setBitRange(0b101110010001111, 5, 0b1001) // 0b101111001001111

// clearBitRange(integer, startIndex, size)
clearBitRange(0b101110010001111, 5, 5) // 0b101110000001111
clearBitRange(0b101110010001111, 2, 3) // 0b100000000001111

How can I optimize these functions by removing or reordering any of the operations? Can we cut out any steps? I did my best to figure out how to just barely implement the function, but I am no master at bit operations yet. Wondering if one could rewrite these 4 functions to make them more optimal. Please keep each instruction on its own line so it's easier to see :)
function getNumBits(n) {
  let i = 0
  while (n) {
    i++
    n >>= 1
  }
  return i
}

function getBitRange(n, l, s) {
  let r = 8 - l - s
  let p = 1 << p
  let o = p - 1
  let ol = o << r
  let or = o >> l
  let om = or & ol
  let x = n & om
  return x >> r
}

function setBitRange(n, i, x) {
  let o = 0xff // 0b11111111
  let c = getNumBits(x)
  let j = 8 - i // right side start
  let k = j - c // right side remaining
  let h = c + i
  let a = x << k // set bits
  let b = a ^ o // set bits flip
  let d = o >> h // mask right
  let q = d ^ b //
  let m = o >> j // mask left
  let s = m << j
  let t = s ^ q // clear bits!
  let w = n | a // set the set bits
  let z = w & ~t // perform some magic https://stackoverflow.com/q/8965521/169992
  return z
}

function clearBitRange(n, i, c) {
  let s = i + c
  let r = 8 - s
  let p = 1 << 8
  let o = p - 1
  let j = o >> i
  let k = o << r
  let h = j & k
  let g = ~h
  let z = n & g
  return z
}

This is only concerned with 8-bit numbers.

For any of the following suggestions, please do profile them to test the performance difference. Performance is likely to vary across multiple browser implementations of the JavaScript interpretation engine.
Rather than a loop for getNumBits, try Math.floor(Math.log(n)/LN_2) - or maybe trunc instead of floor - where LN_2 is precomputed as Math.log(2).
Try to avoid single-letter variables. Your functions are very impenetrable and will be neither legible nor maintainable by anyone else, or by you in a few weeks. In other words, you should not be a human minifier.
Rewrite your code to assume that the index is zero-based starting from the least-significant bit and going left. This will greatly simplify your code and will obviate calls to getNumBits.

Example implementations:
const LN_2 = Math.log(2);

function getNumBits(n) {
    return Math.trunc(Math.log(n) / LN_2) + 1;
}

function getBitRange(n, startIndex, size) {
    return (n >> startIndex) & ((1 << size) - 1);
}

function setBitRange(n, startIndex, size, value) {
    const mask = (1 << size) - 1;
    return (
        n & ~(mask << startIndex)
    ) | ((value & mask) << startIndex);
}

function clearBitRange(n, startIndex, size) {
    const mask = (1 << size) - 1;
    return n & ~(mask << startIndex);
}

A comment about getNumBits and the alternate implementation offered by @potato. That one is indeed faster than calls to log; a local test of mine using Node and 10,000,000 iterations indicates by a factor of about 16. But that needs to be taken with a grain of salt.
If you're (for some reason) doing a massive amount of client-side data processing and needing to call this function many thousands of times, it might be justified (with HEAVY commenting) to use the bit-twiddle method. In all other cases, I don't recommend using something that's so obscure and difficult-to-understand.


PHP - Redirect based on OS optimization I'm new to PHP and I would like to redirect the visitors of my website based on their operating system.
Below is my solution. Is there anything that needs to be optimized?

<?php
    // MOBILE
    $android = strpos($_SERVER['HTTP_USER_AGENT'],"Android");
    $blackberry = strpos($_SERVER['HTTP_USER_AGENT'],"BB10");
    $ios = strpos($_SERVER['HTTP_USER_AGENT'],"iOS");
    // DESKTOP
    $windows = strpos($_SERVER['HTTP_USER_AGENT'],"Windows");
    $mac = strpos($_SERVER['HTTP_USER_AGENT'],"Mac");

    // REDIRECTS
    // MOBILE
    if ($android == true)
    {
    header('Location: http://www.example.com/android');
    }
    else if ($blackberry == true)
    {
    header('Location: http://www.example.com/blackberry');
    }
    else if ($ios == true)
    {
    header('Location: http://www.example.com/ios');
    }
    // DESKTOP
    else if ($windows == true)
    {
    header('Location: http://www.example.com/windows');
    }
    else if ($mac == true)
    {
    header('Location: http://www.example.com/mac');
    }
    ?>

Thanks. Patrick

Before anything, I'll let you search on the web why this might not be such a good idea and I'll just focus on the code.

You probably should retrieve $_SERVER['HTTP_USER_AGENT'] and store it in a variable in order to avoid repeated code. Also, you might want to check if the variable is set properly before accessing it to avoid warnings/errors.
You can rewrite if ($variable == true) as if ($variable)
You could avoid the boilerplate and repeated code if you were storing the interesting parts of your logic in an array and write the common parts only once :

    $ua = isset($_SERVER['HTTP_USER_AGENT']) ? $_SERVER['HTTP_USER_AGENT'] : '';
    $redir = array(
        "Android" => 'android',
        "BB10"    => 'blackberry',
        "iOS"     => 'ios',
        "Windows" => 'windows',
        "Mac"     => 'mac'
    );
    if (isset($redir[$ua]))
    {
        header('Location: http://www.example.com/' . $redir[$ua]);
    }

I hope this helps!


Is this the best way to print dynamic percent value? Is there any better way of printing it?

public class PercentPrinter {

/**
 * @param args
 */
public static void main(String[] args) {

    for (int i = 0; i < 100; i++) {
        if (i == 0)
            System.out.print("percent completed: " + i + " %");
        try {
            Thread.sleep(500);
        } catch (Exception e) {
            System.out.println(e);
        }
        if (i > 9 && i <= 99) {
            System.out.print('\b');
            System.out.print('\b');
            System.out.print('\b');
            System.out.print('\b');

            System.out.print(i + " %");
        } else {
            System.out.print('\b');
            System.out.print('\b');
            System.out.print('\b');

            System.out.print(i + " %");

        }
    }
}
}

Standing on the shoulders of @rolfl…

I would prefer to use a carriage return to return the cursor to the beginning of the line, as it's a bit less fragile than backspacing.

public static void main(String[] args) {
    // Java's Printwriter.format() doesn't tell you how many characters
    // it produced; 30 characters is an overestimate to ensure that
    // the entire "Percent completed: ***%" string gets overwritten.
    final String CLEARLINE_FMT = "\r%30s\r";

    try {
        for (int i = 0; i < 100; i++) {
            System.out.printf("\rPercent completed: %3d%%", i);
            Thread.sleep(500);
        }
        System.out.printf(CLEARLINE_FMT + "Done!\n", "");
    } catch (InterruptedException e) {
        System.out.printf(CLEARLINE_FMT + "Interrupted!\n", "");
    }
}

Or, if you want to print "100%" instead of "Done!":

public static void main(String[] args) {
    // Java's Printwriter.format() doesn't tell you how many characters
    // it produced; 30 characters is an overestimate to ensure that
    // the entire "Percent completed: ***%" string gets overwritten.
    final String CLEARLINE_FMT = "\r%30s\r";

    try {
        for (int i = 0; ; i++) {
            System.out.printf("\rPercent completed: %3d%%", i);
            if (i >= 100) {
                System.out.println();
                break;
            }
            Thread.sleep(500);
        }
    } catch (InterruptedException e) {
        System.out.printf(CLEARLINE_FMT + "Interrupted!\n", "");
    }
}


C++ Linked List Implementation I'm learning C++ and also about data structures, so I am trying to implement some. This is my linked list. I've included two different ways of getting the length of the list, with a length variable and also a function (getLength2) that goes through the list until it finds a NULL pointer. I suspect that there could be memory leaks in it, though I'm not sure.

    #include "stdafx.h"
    #include <iostream>
    using namespace std;

    template <class val>
    class linked_list{
        struct node{
            val value;
            node *next;
        };
        node *start;
        unsigned int length;
    public:
        linked_list() { length = 0; start = NULL; }
        unsigned int getLength() { return length; }
        val getFirst() { return (*start).value; }
        unsigned int getLength2();
        void add(val value);
        val getVal(unsigned int pos);
        val pop();
    };

    int _tmain(int argc, _TCHAR* argv[])
    {
        linked_list<int> gary;
        for (int i = 0; i < 10; ++i){
            gary.add(pow(2, i));
        }
        for (int k = 0; gary.getLength() > 0; ++k){
            cout << gary.pop() << ' ' << gary.getLength() << endl;
        }
        return 0;
    }

    template <class val>
    void linked_list<val>::add(val value){
        node *second = start;
        start = new node;
        (*start).value = value;
        (*start).next = second;
        length += 1;
    }

    template <class val>
    val linked_list<val>::getVal(unsigned int pos){
        node current = *start;
        for (unsigned int depth = 0; depth < pos; ++depth){
            current = *(current.next);
        }
        return current.value;
    }

    template <class val>
    val linked_list<val>::pop(){
        val ret = start->value;
        node *new_address = start->next;
        delete start;
        start = new_address;
        length -= 1;
        return ret;
    }

    template <class val>
    unsigned int linked_list<val>::getLength2() {
        if (start == NULL){
            return 0;
        }
        node current = *start;
        unsigned int len = 1;
        while (current.next != NULL){
            current = *(current.next);
            len += 1;
        }
        // should this have a 'delete current'?
        return len;
    }

Your "getters" should be const since they don't modify any data members.  This will also protect you against any accidental modifications in those functions.

unsigned int getLength() const { return length; }

The constructor can instead be an initializer list:

linked_list() : length(0), start(NULL) {}

Be aware of the issues regarding using namespace std.
If you have a C++11-compliant compiler, use nullptr instead of NULL.
Be aware that _tmain() and _TCHAR* are non-portable, so anyone using this code outside of Visual Studio will not be able to compile it.  In order to make this portable, change them to main() and char* respectively.
Since you're using std::pow(), you should include <cmath>.  Although <iostream> is already covering it, you should add this library anyway.
There's not really a need for getLength2().  You just need to increment or decrement length, depending on the list operation.  Your inline "getter" will, of course, return this updated length.

Regarding incrementing/decrementing, length += 1 and length -= 1 can respectively be length++ and length--.
The val argument for add() should be passed by const&, especially if it happens to be of a non-primitive type.
You should consider error-checking (empty list) in pop() if you'd still like it to return the popped value.  Otherwise, you can make it void and simply return if the list is already empty.
Instead of (*start).value, use the -> operator for readability: start->value.