Rotate an N × N matrix 90 degrees clockwise Given the problem from "Cracking the coding interview"

  Given an image represented by an NxN matrix, where each pixel in the
  image is 4 bytes, write a method to rotate the image by 90 degrees clockwise.

For simplicity I assumed a matrix of strings for my example so

[["a", "a", "a", "a"],
["b", "b", "b", "b"],
["c", "c", "c", "c"],
["d", "d", "d", "d"]]

becomes

[["d", "c", "b", "a"],
["d", "c", "b", "a"],
["d", "c", "b", "a"],
["d", "c", "b", "a"]]

Here's my JavaScript solution

var rotate = function(matrix) {
    // Copy the original matrix
    var origMatrix = matrix.slice();
    for(var i=0; i < matrix.length; i++) {
        // Map each row entry to its rotated value
        var row = matrix[i].map(function(x, j) {
            var k = (matrix.length - 1) - j;
            return origMatrix[k][i];
        });
        matrix[i] = row;
    }
    return matrix;
};

Are you up to date?

There is really not much to the problem and there are a variety of solutions.

It is also hard to know what the interviews are looking for. For some it is knowledge of latest language features, for others it may be judged on efficiency.

These very simple tests are generally just to see if you can actually write code. You would be amazed at how many people apply for jobs they are not able to do.

Assessing the code.

Looking at your code as a conservative HR interested in your code writing style, and up to date language knowledge.

It is a pass, you can code, you have the job but will have you in supervision for a while..You also need to catch up on the language as you are not using ES6 to the full.

General points

You need to use const for constants, and let for block scope variables.
You have not used any arrow functions.
I would question why you created the function using an expression, rather than a function statement, to make sure that you know the difference. (You should play it safe an use function statements)
Also maybe a little to much code, but not really an issue.
Code logic.. i would ask why you chose to duplicate the array rather than just create a new one as you went.

A quick rewrite

I am assuming the rotate is in place (original array) with new rows

function rotate(matrix) {          // function statement
    const N = matrix.length - 1;   // use a constant
    // use arrow functions and nested map;
    const result = matrix.map((row, i) =>
         row.map((val, j) => matrix[N - j][i])
    );
    matrix.length = 0;       // hold original array reference
    matrix.push(...result);  // Spread operator
    return matrix;
}

Some extras

The problem states "image" and "pixel" which give a hint that this may be judged on performance. They would tell you if it was. But if you get  a similar challenge and performance is important then its best to use good old for loops, avoiding any iterators that use callbacks.

Also a performance oriented function would swap in place rather than create new arrays. If you had to do that realtime with images for modern displays your code would be making big GC hits (Garbage Collection).

An alternative

Another way it can be done by rotating 4 pixels at a time can reduce memory overheads and processing time. Destructing lets you swap 4 corners in one go without the need to create temp variables.

I would never recommend you submit the following unless there was a clear directive for performance, and thinking outside the box.

// Commented version

// N*N is square
// pixels are rotated inplace
// 4 by 4 rotated in 4 iterations
// 5 by 5 rotated in 7 iterations
function rotatePixels(image) {
    var x, y, x1, y1, edge;
    // Solve by swapping 4 at a time in rings from the outside in
    const N = image.length;  // size of array
    const N1 = N - 1;        // position of end item
    const N2 = N / 2;        // Half way position

    // x,y hold the a cell coordinate
    x = y = 0;

    // x,y hold the diagonally opposite cell
    x1 = y1 = N1;

    // length of current edge
    edge =  N1;

    // while not at the center
    while (y < N2) {
        // for each item on the current edge
        while (x < edge) { // rotate points at outer edge
            // swap 4 corner items
            // using array destructed assignment
            [
                image[x ][y1],
                image[y1][x1],
                image[x1][N1 - y1],
                image[y ][x ]
            ] = [
                image[y ][x ],
                image[x ][y1],
                image[y1][x1],
                image[x1][N1 - y1]
            ];
            x += 1;     // move top pos forward one
            x1 -= 1;    // move bottom pos back one
        }
        y += 1;         // diagonally into array
        x  = y;         // x same as y
        y1 = x1 = N1-x; // and diagonal opposite
        edge -= 1;      // shorten the end
    }
    return image;
}

// How I would present it

function rotatePixels(image) {
    var x, y, x1, y1, edge;
    const N = image.length;
    const N1 = N - 1;
    const N2 = N / 2;
    x = y = 0;
    edge = x1 = y1 = N1;
    while (y < N2) {
        while (x < edge) {
            [image[x][y1], image[y1][x1], image[x1][N1-y1], image[y][x]] =
            [image[y][x] , image[x ][y1], image[y1][x1]   , image[x1][N1-y1]];
            x += 1;
            x1 -= 1;
        }
        x  = y += 1;
        y1 = x1 = N1-x;
        edge -= 1;
    }
    return image;
}

// At time of writing I was unsure as to the performance of the swap using destructuring
// Turns out it is very bad
// The next version is a more conventional swap and runs 3 time faster than the above version
// and 8 times faster than the conventional solution at top of answer

function rotatePixels(image) {
    var x, y, x1, y1, edge;
    const N = image.length;
    const N1 = N - 1;
    const N2 = N / 2;
    x = y = 0;
    edge = x1 = y1 = N1;
    while (y < N2) {
        while (x < edge) {
            const a = image[y][x];
            image[y][x]      = image[x1][N1-y1];
            image[x1][N1-y1] = image[y1][x1];
            image[y1][x1]    = image[x][y1];
            image[x][y1]     = a;
            x += 1;
            x1 -= 1;
        }
        x  = y += 1;
        y1 = x1 = N1-x;
        edge -= 1;
    }
    return image;
}


Javascript array-matching beginner As a beginner coder in js, I'd like to hear about further improvements of the following code, but nothing too advanced, please.
The program is meant to work the following way:

A user inputs a color array like this one: ["blue", "green"]
The code checks if those words are valid inputs (they should be found in a reference array of COLORS). This is done with catchInvalid function
If they are valid inputs, and so they are found in COLORS array, it gets the index of it. This is done in the decodedValue function

Example1:
COLORS= ["blue", "yellow", "red"]
User input: userColors=["yellow"]
returns index of yellow in COLORS i.e 1.

Example2:
COLORS= ["blue", "yellow", "red"]
User input: userColors=["yellow", "red"]
returns index 12 (index of yellow in colors*10 + index of red in colors (2)).

That's all. It's now working fine, but I wonder if you'd give any suggestions for improving the code.
    const COLORS = ["black", "brown", "red", "orange", "yellow", "green", "blue", "violet", "grey", "white"];
 //this will be the reference array
    const catchInvalid = (color, COLORS) =>{
    //checks if color is in COLORS (which is COLORS)
            if(COLORS.indexOf(color)==-1){
                    return `not a ${color} in ${COLORS}`
            }
            else { }
    }

    const decodedValue = (colorArray) => {
            //if previous 'color' is in the reference array, get the index of the color in COLORS.
    let CODES=[];

    if (colorArray.length==0){
            return "Input a color value"
            }
    else if (colorArray.length==1){
            catchInvalid(colorArray[0], COLORS)
            return COLORS.indexOf(colorArray[0])
            }
    else {
    for(let i=0; i<2;i++){
            //only for the first 2 items in the array.
            catchInvalid(colorArray[i], COLORS)
            CODES.push(COLORS.indexOf(colorArray[i]))
            }
                                                                                return CODES[0]*10 + CODES[1];
        }
}

console.log(decodedValue(["blue"]), decodedValue(["nothing"]), decodedValue(["blue", "green"]))

From a short review, considering you are a beginner;

keep your variables in lowerCamelCase so

COLORS -> colors
CODES -> codes

on the whole, avoid to have data type in the variable name

colorArray -> colors

your commenting is quite good
Your indenting is inconsistent, it easier to read your code when code is properly indented
catchInvalid probably should return a boolean
I would have called catchInvalid -> isInvalidColor it gives more detail
catchInvalid should either use the global, or know the colors locally
I would use COLORS.includes() over COLORS.indexOf
There is way to calculate the return code without making a distinction between 1 or 2 elements

Per the comment, a bit more explicit
    function decodeColorValues(colors){
      //These are all the possible colors
      const knownColors = ["black", "brown", "red", "orange", "yellow", "green", "blue", "violet", "grey", "white"];

      //Functions should return a consistent datatypes, so I return -1 instead of a message
      //If the caller did not provide an aray but say "orange", then this will return -1 as well
      if(!colors.length){
        return -1;
      }

      //Filter out unknown colors
      colors = colors.filter(color => knownColors.includes(color));

      //If all colors were unknown then return -1
      //You could change this so that if 1 color is unknown it returns -1
      if(!colors.length){
        return -1;
      }

      //We only deal with the first 2 entries (why?)
      colors = colors.slice(0,2);
      let value=0;

      //Abuse the fact that 10 times zero is still zero
      for(const color of colors){
        value = value * 10 + knownColors.indexOf(color);
      }

      return value;
    }

    console.log(decodeColorValues(["blue"]),
                decodeColorValues(["nothing"]),
                decodeColorValues(["blue", "green"]),
                decodeColorValues(["blue", "nothing"])
           );


Arbitrary Dice with Probability I wrote a script that gives a "generalized" function of an arbitrary dice. Is this any good? How can it improve so to make it cleaner?

import random
def roll(die):
    number = random.randint(0,len(die)-1)
    b = die[number]
    return b

Die1 = [1,2,3,4]
Die2 = [1,2,3,4,5,6] #num lists

def inptchacc():
    ending_conditions = ['stop','Stop','quit','Quit']
    end = False
    inpu = input('what number would you like to add to the new face of the Die? (to end the die please type "stop or Stop or quit or Quit to finish the DIE" )')
    while end == False:
        if not(inpu in ending_conditions):
            try:
                retr = int(inpu)
                return retr
            except:
                string = 'invalid input please try again'
                inpu = input('invalid input please try again ')
        else:
            stop = 'stop'
            return stop

def deeper(IDie):
    list = []
    Adding = True
    while Adding:
        print('The Die ' + IDie + ' is currently ' + str(list) )
        toadd = inptchacc()
        if toadd != 'stop':
            list.append(toadd)
        else:
            Adding = False
    return list

def chance_overlap(Die1,Die2):
    highnumber = 1000
    counter = 0
    for n in range(highnumber):
        x = roll(Die1)
        y = roll(Die2)
        if x == y:
            counter += 1
    chance = counter/highnumber
    return chance

chance = chance_overlap(Die1,Die2)

print(chance)
Doing = True
while Doing:
    try:
        IDie1 = deeper('IDie1')
        IDie2 = deeper('IDie1')
        chance2 = chance_overlap(IDie1,IDie2)
        Doing = False
    except:
        print ('incompatible options selected returning....... ')

print(chance2)

Since you need to roll many times in the chance_overlap function, you might want to optimize making n rolls, using random.choices (Python 3.6+):

from itertools import groupby

def roll(die, n=1):
    if n == 1:
        return random.choice(die)
    return random.choices(die, k=n)

def all_equal(iterable):
    "Returns True if all the elements are equal to each other"
    g = groupby(iterable)
    return next(g, True) and not next(g, False)

def overlap_chance(*dice, n=1000):
    rolls = [roll(die, n) for die in dice]
    equal_rolls = sum(all_equal(roll) for roll in zip(*rolls))
    return equal_rolls / n

Here I chose to include it in your roll function, which is nice because you only have on function, but you do have different return types depending on the value of k, which is not so nice. If you want to you can make it into two separate functions instead.

I made chance_overlap take a variable number of dice so it even works for more than two (and also for one, which is a bit boring).

In addition, I followed Python's official style-guide, PEP8 for variable names (lower_case).

The all_equal function is directly taken from the itertools recipes.

Using a Monte-Carlo method to determine the chance for the dice to get the same values is fine, but you could just use plain old math.

Each distinct value \$j\$ on each die \$i\$ has probability \$p^i_j = n^i_j / k_i\$, where \$k_i\$ is the number of faces of die \$i\$ and \$n^i_j\$ the number of times the value \$j\$ appears on that die. Then the chance to have an overlap is simply given by

$$
P(overlap) = \sum\limits_j \prod\limits_i p^i_j = \sum\limits_j \prod\limits_i n^i_j / k_i,
$$

where \$i\$ goes over all dice and \$j\$ over all values present on any dice (with \$n^i_j = 0\$ if value \$j\$ does not appear on die \$i\$).

In other words dice rolls are independent events and e.g. the chance to get two heads or two tails with a fair coin (dice = [["H", "T"], ["H", "T"]]) are \$P(HH \vee TT) = P_1(H)\cdot P_2(H) + P_1(T) \cdot P_2(T) = 0.5\cdot0.5 + 0.5\cdot0.5 = 0.5\$.

from collections import Counter
from functools import reduce
from itertools import chain
from operator import mul

def overlap_chance_real(*dice):
    all_values = set(chain.from_iterable(dice))
    counters = [Counter(die) for die in dice]
    lengths = [len(die) for die in dice]
    return sum(reduce(mul, [counter[val] / length
                            for counter, length in zip(counters, lengths)])
               for val in all_values)

The nice thing about this is that we don't need to worry if not all dice have the same values, since Counter objects return a count of zero for non-existing keys.

For dice = [[1,2,3], [1,1,1]] it returns the correct (and precise) value of 0.3333333333333333. and 0.5 for dice = [["H", "T"], ["H", "T"]].

The execution time of the first function (overlap_chance)  increases linearly with the number of dice (all six sided) and it is in general slower than the second function (overlap_chance_real):

With two dice with increasing number of faces the first function is slower but basically constant in time while the second function is faster but the time increases with the number of faces. This plot also contains your function (since it can only deal with two dice it was not included in the previous plot), which is slower than both:


Throttling promise execution (API requests, etc) I was working on a client for a remote api and realized that I needed to throttle requests at a maximum rate of 4 Hertz (4 requests per second). I wrote a simple typescript class to do it and wanted to solicit code review. It basically should accept a () => Promise<R> and return a Promise<R> that resolves once executed by the queue.

My prototype solution is here, and I'd just like to solicit feedback for it. Original code here.

/**
 * Request throttle has an add() method which takes a () => Promise<string>
 * and queues the promise to be executed in order.
 * add() returns a promise that resolves with the original promise result.
 */
class RequestThrottle {
  stack = [];
  spacing = 1000;

  add: (req: () => Promise<string>) => Promise<string> = req => {
    let executor;
    const requestPromise: Promise<string> = new Promise((resolve, _reject) => {
      let localExecutor = () => {
        resolve(req());
      };
      executor = localExecutor;
    });

    this.stack.push(executor);
    return requestPromise;
  };

  pullAndExecute = () => {
    const op: () => Promise<string> = this.stack.shift();
    // if (op) console.log("throttle found:", op);
    if (op) op();
  };

  interval = setInterval(this.pullAndExecute, this.spacing);

  stop = () => clearInterval(this.interval);
}

const throttle = new RequestThrottle();

/**
 * Promise tester - to add a bit of extra async operations
 * (eg a network request to an api)
 * */
const addChild: (c: number | string) => Promise<string> = count => {
  const list = document.getElementById("list");
  const node = document.createElement("LI");
  node.innerHTML = count.toString();
  list.appendChild(node);
  const promise: Promise<string> = new Promise(resolve =>
    setTimeout(() => {
      log(`added "${count}"`);
    }, 500)
  );
  return promise;
};

const log = (s: string) => {
  const list = document.getElementById("log");
  const node = document.createElement("pre");
  node.innerHTML = s;
  list.appendChild(node);
};

addChild("Starting a List").then(console.log);

const enqueue: (i: number | string) => () => Promise<string> = i => {
  console.log("enqueueing " + i);
  return () => {
    return addChild(i);
  };
};

for (var i in [1, 2, 3, 4, 5, 6]) {
  throttle.add(enqueue(i)).then(console.log);
}

The most important advice I can offer is to turn on strictNullChecks and noImplicitAny. Without these settings, TypeScript's ability to warn you about problems in your code is severely limited.

Doing this first, TypeScript reveals several problems (Ignoring errors from your tests, you just need a ! assertion):

test.ts:19:21 - error TS2345: Argument of type 'undefined' is not assignable to parameter of type 'never'.

19     this.stack.push(executor);
                       ~~~~~~~~

test.ts:24:11 - error TS2322: Type 'undefined' is not assignable to type '() => Promise<string>'.

24     const op: () => Promise<string> = this.stack.shift();
             ~~

None of these errors are particularly difficult to fix. First, we need to define the type of stack. Right now, as it is assigned [], the inferred type is [] (an empty tuple). If we look at the type of functions added to it in add, we see that a function of type () => void is added, so declare that.

class RequestThrottle {
  stack: (() => void)[] = [];

This change will change the reported errors slightly, giving us more useful error messages.

test.ts:19:21 - error TS2345: Argument of type 'undefined' is not assignable to parameter of type '() => void'.

19     this.stack.push(executor);
                       ~~~~~~~~

test.ts:24:11 - error TS2322: Type '(() => void) | undefined' is not assignable to type '() => Promise<string>'.
  Type 'undefined' is not assignable to type '() => Promise<string>'.

24     const op: () => Promise<string> = this.stack.shift();
             ~~

The next problem is caused by let executor;. Since no type has been declared, TypeScript will implicitly type the variable as any. You could fix this by typing executor as (() => void) | undefined and then asserting that it has been set after executing the promise, but it is simpler to just add the function to stack within the promise.

At the same time, declaring the add function as a property instead of an arrow function on the class (like you did with pullAndExecute) is kind of weird. I'd prefer this style:

class RequestThrottle {
  stack: (() => void)[] = [];
  spacing = 1000;

  add = (req: () => Promise<string>): Promise<string> => {
    return new Promise<string>((resolve) => {
      this.stack.push(() => {
        resolve(req());
      });
    });
  };

This resolves the first issue, the second issue can be easily resolved by dropping the erroneous Promise<string> type on op in the pullAndExecute function.

class RequestThrottle {
  stack: (() => void)[] = [];
  spacing = 1000;

  add = (req: () => Promise<string>): Promise<string> => {
    return new Promise<string>((resolve) => {
      this.stack.push(() => {
        resolve(req());
      });
    });
  };

  pullAndExecute = () => {
    const op = this.stack.shift();
    if (op) op();
  };

  interval = setInterval(this.pullAndExecute, this.spacing);

  stop = () => clearInterval(this.interval);
}

Next we must consider the access level of each member. add should obviously be public. Similarly, it makes sense for stop to be public. But stack, spacing, interval and pullAndExecute are all implementation details. Users of this class shouldn't need to care (or even know) that they exist. They should all be marked as private.

Despite this... users might want to be able to specify spacing when using the class. There are two ways to meet this need. Either let the user specify it in the constructor, or add a start method that starts the interval. I prefer the start solution.

class RequestThrottle {
  private stack: (() => void)[] = [];
  private interval = 0;

  add = (req: () => Promise<string>): Promise<string> => {
    return new Promise<string>((resolve) => {
      this.stack.push(() => {
        resolve(req());
      });
    });
  };

  private pullAndExecute = () => {
    const op = this.stack.shift();
    if (op) op();
  };

  start = (spacing = 1000) => {
    this.stop();
    this.interval = setInterval(this.pullAndExecute, spacing);
  };

  stop = () => clearInterval(this.interval);
}

Note that in the start method I call stop first. This is to ensure that we don't have multiple queue consuming clocks running at once.

Now, you mentioned that you wanted this class to work with a Promise<R>. As written, it will only let you use Promise<string>. Thankfully, this is a trivial fix, we just need to make the add method generic.

  add = <R>(req: () => Promise<R>): Promise<R> => {
    return new Promise<R>((resolve) => {
      this.stack.push(() => {
        resolve(req());
      });
    });
  };

With all these changes together, the class becomes:

class RequestThrottle {
  private stack: (() => void)[] = [];
  private interval = 0;

  add = <R>(req: () => Promise<R>): Promise<R> => {
    return new Promise<R>((resolve) => {
      this.stack.push(() => {
        resolve(req());
      });
    });
  };

  start = (spacing = 1000) => {
    this.stop();
    this.interval = setInterval(this.pullAndExecute, spacing);
  };

  stop = () => clearInterval(this.interval);

  private pullAndExecute = () => {
    const op = this.stack.shift();
    if (op) op();
  };
}

A couple other notes:

Don't use for .. in to iterate over arrays. Use for .. of instead.

for (const i of [1, 2, 3, 4, 5, 6]) {
  throttle.add(enqueue(i)).then(console.log);
}

Don't make promises that can never be resolved or rejected. In addChild, the promise will never be resolved.
Should RequestThrottle throttle based on promise starts or promise resolves? Currently it throttles based on the initial call of a function... but if that function takes more than spacing to resolve, you could have multiple promises waiting at once. This might be desired, but it is something to consider.


Shortest possible way of printing a specific board I am trying to print a board exactly like this with the multidimensional array.

char score[10][10] = {' '};

   a b c d e f g h i j
  +-------------------+
 0|                   |
 1|                   |
 2|                   |
 3|                   |
 4|                   |
 5|                   |
 6|                   |
 7|                   |
 8|                   |
 9|                   |
  +-------------------+

This is my code:

#include <iostream>
using namespace std;
#include <vector>
#include <string.h>

int main(){

char score[10][10] = {' '};

cout<< "   a b c d e f g h i j"<< endl;
cout <<"  +-------------------+"<< endl;
    for (int i = 0; i < 10; i++) {
        cout<<" "<< i <<"|" ;
        for (int j = 0; j < 10; j++) {
           cout << score[i][j];
        }
            if(i == 0){
                cout << "                  |";

            }
            else{
                cout << "                   |";
                }
        cout<< endl;

    }
    cout <<"  +-------------------+"<< endl;

}

As you can see my code is inefficient and lengthy.

What would be the shortest possible way (or a shorter way) of printing the board as exactly shown above with the multidimensional score array?

Bugs

You say:

  I am trying to print a board exactly like this with the multidimensional array.

But, in reality, you are not... you only print the first item from the 2D array, and the rest of the board is printed from the constant string values. See this article describing C++ array initialization

char score[10][10] = {' '};

The above code only initializes the first position of the score 2D array, and the remaining cells in the array are left as null-characters.

When those null-characters are printed in the j loop:

    for (int j = 0; j < 10; j++) {
       cout << score[i][j];
    }

The all do nothing (except the very first cell at score[0][0]) because they become zero-length strings.

Thus, only the first line, and the first value get printed. To compensate for this, you are printing an constant-string value to complete the line, but, the first line is one character longer (because you printed score[0][0]) than the others, so the first line has to have a single-char shorter constant to complete it, and you need the if(i == 0){... condition.

I have made this obvious by initializing the array with an x (char score[10][10] = {'x'};) in this ideone which produces:

   a b c d e f g h i j
  +-------------------+
 0|x                  |
 1|                   |
 2|                   |
 3|                   |
 4|                   |
 5|                   |
 6|                   |
 7|                   |
 8|                   |
 9|                   |
  +-------------------+

You need to correctly initialize the array....

char score[10][10] = {};
for (int i = 0; i < 10; i ++) {
    for (int j = 0; j < 10; j++) {
        score[i][j] = ' ';
    }
}

Other

you are using the grid-size 10 as a magic number in a lot of places. You should probably make it a constant.....

Alternative.

C++ is not my primary language, and this is hardly a good example of a C++ program, but I have re-written your program as.... available on ideone as well ... This is the code that you should really be reviewed on ....

#include <iostream>
using namespace std;
#include <vector>
#include <string.h>

int main(){

    char score[10][10] = {};
    for (int i = 0; i < 10; i ++) {
        for (int j = 0; j < 10; j++) {
            score[i][j] = 'x';
        }
    }

    cout<< "   a b c d e f g h i j"<< endl;
    cout <<"  +-------------------+"<< endl;

    for (int i = 0; i < 10; i++) {
        // print the first character as part of the opener.
        cout << " " << i << "|" << score[i][0];
        for (int j = 1; j < 10; j++) {
           // only add spaces for subsequent characters.
           cout << " " << score[i][j];
        }
        cout << "|" << endl;
    }
    cout <<"  +-------------------+"<< endl;

}

because the above code initializes the 2D array with x, it prints the following grid:

   a b c d e f g h i j
  +-------------------+
 0|x x x x x x x x x x|
 1|x x x x x x x x x x|
 2|x x x x x x x x x x|
 3|x x x x x x x x x x|
 4|x x x x x x x x x x|
 5|x x x x x x x x x x|
 6|x x x x x x x x x x|
 7|x x x x x x x x x x|
 8|x x x x x x x x x x|
 9|x x x x x x x x x x|
  +-------------------+


Shutdown-Script for Don't Starve Together Dedicated Server I have written my first LUA-Script/Function to shut down the Dedicated Server for Don't Starve Together.
I wanted to shut down the server in 2 minutes and inform everyone on the server that the server is shutting down.
The function os.execute is nil in the dedicated server console, so I can't use os.execute("sleep " .. seconds).

Can I improve something on this script? Is it best practice?

function sleep(seconds)
    local t = os.time()
    local diff = 0
    while diff < seconds do
        diff = os.difftime(os.time(), t)
    end
end

local steps = {120,60,30,10,5,4,3,2,1}
local n = table.getn(steps)
for i=1,n-1,1 do
  TheNet:SystemMessage("The server shuts down in " .. steps[i] .. " seconds")
  sleep(steps[i] - steps[i+1])
end
TheNet:SystemMessage("The server shuts down in " .. steps[n] .. " seconds")
sleep(steps[n])
TheNet:SystemMessage("The server is shutting down now")
c_shutdown(true)

Link to the server command list for Don't Starve.

TheNet:SystemMessage prints the message into the chat
c_shutdown(true) shutdown the server and persist the world

table.getn has been deprecated for more than 2 years now.
Why iterate only until n-1?
I'd prefer using the string.format over plain concatenation. This is just a personal preference, as the strings are easier to read that way.
Although you do not need to pass true to the c_shutdown, do mention in a comment what it does. Maintaining comments is a nice way to recognise engine specific hard-bound parameters; without having to refer the docs again.
Iterate over the table using ipairs

Rewritten, the code would be:

local function sleep(seconds)
    local diff, t = 0, os.time()
    while diff < seconds do
        diff = os.difftime(os.time(), t)
    end
end

local steps = {
  120, 60, 30,
  10, 5, 4, 3,
  2, 1
}
local notice = "The server shuts down in %d seconds"

for _, secs in ipairs(steps) do
  TheNet:SystemMessage(notice:format(secs))
  sleep(secs)
end
TheNet:SystemMessage("The server is shutting down now")
c_shutdown(true)  -- true parameter implies that the game will be saved


Creating keyword records in a database This code is part of a data model used to create keyword records in a database.

if (_queue
    .OrderByDescending(record=>record.Primary)
    .GroupBy(record=>record.Term)
    .Select(record=>record.First())
    .Select(Create)
    .Any(result=>result <= 0))
{
    throw new ModelException("Failed to create keyword record.");
}

While I can understand this, I was also thinking it was a little obfuscated.

Is the intent of this code clearly readable?

Definitely readable although I would just combine your two select statements and add some whitespace:

if (_queue.OrderByDescending(record => record.Primary)
          .GroupBy(record => record.Term)
          .Select(record => Create(record.First()))
          .Any(result => result <= 0))
{
    throw new ModelException("Failed to create keyword record.");
}

As you see I also prefer to keep the first statement on the same line and indent the next statements to align with the linq statement.

One remark though: first you're ordering your records and then grouping them. Is this done deliberately? I would assume that you'd want to group first and then order, not in the least because you would have to order less elements. But then again: grouping might be more performant if you order it first so I'm not entirely sure.


Small Markov chain Monte Carlo implementation I've written a small markov chain monte carlo function that takes samples from a posterior distribution, based on a prior and a binomial (Bin(N, Z)) distribution.

I'd be happy to have it reviewed, especially perhaps, regarding how to properly pass functions as arguments to functions (as the function prior_dist() in my code). In this case, I'm passing the function uniform_prior_distribution() showed below, but it's quite likely I'd like to pass other functions, that accept slightly different arguments, in the future. This would require me to rewrite mcmc(), unless there's some smart way around it...

def mcmc(prior_dist, size=100000, burn=1000, thin=10, Z=3, N=10):
    import random
    from scipy.stats import binom
    #Make Markov chain (Monte Carlo)
    mc = [0] #Initialize markov chain
    while len(mc) < thin*size + burn:
        cand = random.gauss(mc[-1], 1) #Propose candidate
        ratio = (binom.pmf(Z, N, cand)*prior_dist(cand, size)) / (binom.pmf(Z, N, mc[-1])*prior_dist(mc[-1], size))
        if ratio > random.random(): #Acceptence criteria
        mc.append(cand)
    else:
        mc.append(mc[-1])
    #Take sample
    sample = []
    for i in range(len(mc)):
        if i >= burn and (i-burn)%thin == 0:
            sample.append(mc[i])
    sample = sorted(sample)
    #Estimate posterior probability
    post = []
    for p in sample:
        post.append(binom.pmf(Z, N, p) * prior_dist(p, size))
    return sample, post, mc

def uniform_prior_distribution(p, size):
    prior = 1.0/size
    return prior

def mcmc(prior_dist, size=100000, burn=1000, thin=10, Z=3, N=10):
    import random
    from scipy.stats import binom

Don't import inside functions. It goes against python convention and is inefficient

    #Make Markov chain (Monte Carlo)
    mc = [0] #Initialize markov chain
    while len(mc) < thin*size + burn:
        cand = random.gauss(mc[-1], 1) #Propose candidate
        ratio = (binom.pmf(Z, N, cand)*prior_dist(cand, size)) / (binom.pmf(Z, N, mc[-1])*prior_dist(mc[-1], size))
        if ratio > random.random(): #Acceptence criteria
            mc.append(cand)
    else:
        mc.append(mc[-1])

Why is this in else clause? It only make sense to use else clauses if you are using break.

    #Take sample
    sample = []
    for i in range(len(mc)):
        if i >= burn and (i-burn)%thin == 0:
            sample.append(mc[i])

Actually something like sample = mc[burn::thin] will have the same effect as this loop

    sample = sorted(sample)
    #Estimate posterior probability
    post = []
    for p in sample:
        post.append(binom.pmf(Z, N, p) * prior_dist(p, size))

I'd suggest post = [binom.pmf(Z, N, p) * prior_dist(p, size) for p in sample]

    return sample, post, mc

def uniform_prior_distribution(p, size):
    prior = 1.0/size
    return prior


Array offset without losing values After looking through PHP.net documentation for hours, is this the best way to offset an array from start to finish by using array_slice() with array_merge()?

For example: $array = array(1,2,3,4) to offset by 2 to get return $array = array(3,4,1,2).

Here's the code I'm using it in:

    $team = 2;
    $course = array(
    array('title'=>1,  'hole'=> 'h01', 'shot1'=>'value="-3"', 'shot2'=>'value="-2"', 'shot3'=>'value="-1"', 'shot4'=>'value="0"', 'shot5'=>'disabled="disabled"'),
    array('title'=>2,  'hole'=> 'h02', 'shot1'=>'value="-4"', 'shot2'=>'value="-3"', 'shot3'=>'value="-2"', 'shot4'=>'value="-1"', 'shot5'=>'value="0"'),
    array('title'=>3,  'hole'=> 'h03', 'shot1'=>'value="-3"', 'shot2'=>'value="-2"', 'shot3'=>'value="-1"', 'shot4'=>'value="0"', 'shot5'=>'disabled="disabled"'),
    array('title'=>4,  'hole'=> 'h04', 'shot1'=>'value="-2"', 'shot2'=>'value="-1"', 'shot3'=>'value="0"', 'shot4'=>'disabled="disabled"', 'shot5'=>'disabled="disabled"'),
    array('title'=>5,  'hole'=> 'h05', 'shot1'=>'value="-4"', 'shot2'=>'value="-3"', 'shot3'=>'value="-2"', 'shot4'=>'value="-1"', 'shot5'=>'value="0"')
    );

    $array1 = array_slice($course, $team);
   $array2 = array_slice($course, 0, $team);
   $merged = array_merge($array1, $array2);

}

If you don't mind modifying the original array, you can shorten the (perfectly adequate code you have) with this:

$head = array_splice($course, 0, $team);  // remove and return first $team elements
$merged = array_merge($course, $head);    // append them to the end

You should be able to omit the temporary $head array by inserting the array_splice call into the array_merge call at the cost of a little code clarity. Try it out to make sure the order of operations is correct.

$merged = array_merge($course, array_splice($course, 0, $team));

Edit: If you're doing this once per team you can use a loop with array_shift to remove the first element and array_push to place it at the end:

for ($team = 0; $team < $numTeams; $team++) {
    array_push($course, array_shift($course));
    // use $course...
}


Composing and executing a customer search I was wondering if someone could help me refactor this code. Although I know this looks bad, it works. Now I would like to refactor it so I would respect the open/closed principle in SOLID. Let's say the client wants a new search field to search data on, then I need to come to this method and add it in and this breaks the O/C principle. How would you guys change this?

public List<Customer> Search(Search searchData){
using(context)
{
    var query = context.Customers;

    if(!string.NullOrEmpty(searchData.FirstName)
        query.Where(c => c.FirstName == searchData.FirstName);

    if(!string.NullOrEmpty(searchData.LastName)
        query.Where(c => c.LastName == searchData.LastName);

    if(!string.NullOrEmpty(searchData.StreetName)
        query.Include(c => c.Address);
        query.Where(c => c.Address.StreetName == searchData.StreetName);

    if(!string.NullOrEmpty(searchData.PostCode)
        query.Include(c => c.City);
        query.Where(c => c.City.PostCode == searchData.PostCode);

    var customers = query.ToList();
    return customers;
}    }

Not sure if you know how dangerous omitting braces for if statements can be. Do you know what happens here :

if(!string.NullOrEmpty(searchData.StreetName)
    query.Include(c => c.Address);
    query.Where(c => c.Address.StreetName == searchData.StreetName);

no matter wether searchData.StreetName is null or not the query.Where(c => c.Address.StreetName == searchData.StreetName); will be executed nevertheless. I assume from the way you have formatted the code that you assume this will be only executed if the condition is true.

I would like to encourage you to always use braces {} although they might be optional. This helps you to structure your code which helps to make it more readable and by using them you make your code less error prone.


Unique letter counter for string in Python I'm trying to create a program that creates a record of how many times letters appear in a given string (ignoring blank spaces) using recursion.

s = "Hello there this is the string"

new_s = ""
for i in s:
    if i != " ":
        new_s += i
new_s = new_s.lower()
com_dict = {}
def merge_count(s):
    global com_dict
    if len(s) == 1:
        if s[0] in com_dict:
            com_dict[s[0]] += 1
        else:
            com_dict[s[0]] = 1
    else:
        merge_count(s[:int(len(s)/2)])
        merge_count(s[int(len(s)/2):])

merge_count(new_s)
for i in com_dict:
    print i, com_dict[i]

Is the global variable necessary? Should I be using a different data structure instead of a dictionary? I will need to rank the results based on the most frequently appearing letters. Is using recursion in this scenerio generally a bad idea? Would iterating be a better choice?

Is the global variable necessary?

No. Global variables are almost never necessary, and rarely the best solution. Consider this:

def merge_count(s, com_dict):
    if len(s) == 1:
        if s[0] in com_dict:
            com_dict[s[0]] += 1
        else:
            com_dict[s[0]] = 1
    else:
        merge_count(s[:int(len(s)/2)], com_dict)
        merge_count(s[int(len(s)/2):], com_dict)

def main():
    s = "Hello there this is the string"

    new_s = ""
    for i in s:
        if i != " ":
            new_s += i
    new_s = new_s.lower()

    com_dict = {}
    merge_count(new_s, com_dict)
    for i in com_dict:
        print i, com_dict[i]

main()

In this, you pass a dictionary to merge into into to the function.

You do

new_s = ""
for i in s:
    if i != " ":
        new_s += i

Addition of strings in loops is always almost bad, because it may reallocate the string on every addition. Instead, one should do a join:

new_s = "".join(i for i in s if i != " ")

However, in this case you might as well just do

new_s = s.replace(" ", "")

Recursively splitting in merge_count is pointless. Just do

def merge_count(s, com_dict):
    for i in s:
        if s in com_dict:
            com_dict[s[0]] += 1
        else:
            com_dict[s[0]] = 1

which affords the better interface of

def merge_count(s):
    com_dict = {}

    for i in s:
        if s in com_dict:
            com_dict[i] += 1
        else:
            com_dict[i] = 1

    return com_dict

One can simplify things with defaultdict:

from collections import defaultdict

def merge_count(s):
    com_dict = defaultdict(int)

    for i in s:
        com_dict[i] += 1

    return com_dict

Or even further with Counter:

from collections import Counter

def merge_count(s):
    return Counter(s)

Instead of

for i in com_dict:
    print i, com_dict[i]

One should do

for i, v in com_dict.iteritems():
    print i, v

Then one fixes up the naming

from collections import Counter

def main():
    string = "Hello there this is the string"

    lower_chars = string.replace(" ", "").lower()
    char_counts = Counter(lower_chars)

    for char, count in char_counts.items():
        print(char, count)

main()


Minimizing number of field lamps This program attempts to solve the following challenge:

  There is a 2D grid of cells containing N lamps. Each lamp illuminates its own cell as well as its eight neighbours.  How many lamps can you possibly remove such that each cell that was originally illuminated remains illuminated?

My code:

import java.util.*;

class test
{
    public static void main(String[] ar)
    {
        int use = 0;
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the dimensions: ");
        int a = sc.nextInt();
        int b = sc.nextInt();
        int[][] f = new int[a][b];
        System.out.print("Enter the no. of lamps: ");
        int n = sc.nextInt();
        int[][] l = new int[n][2];
        //System.out.print("Enter the coordinates : ");
        for(int i = 0; i < n; i++)
        {
            int t1,t2;
            do
            {
            t1 = l[i][0] = (int)(Math.random()*a);
            t2 = l[i][1] = (int)(Math.random()*b);
            f[t1][t2] = 1;
        }while(f[t1][t2] == 0);
        }
        print(f);
        light(f);
        for(int i = 0; i < l.length; i++)
        {
            int[][] f1 = new int[a][b];
            for(int j = 0; j < l.length; j++)
            {
                if(i == j)
                    continue;
                int x = l[j][0];
                int y = l[j][1];
                if(x < 0)
                    continue;
                f1[x][y] = 1;
            }
            light(f1);
            if(!same(f,f1))
                use++;
            else
            {
                l[i][0] = -1;
                l[i][1] = -1;
            }
        }
        System.out.println("Usefull : " + use);

    }

    public static boolean same(int[][] a, int[][] b)
    {
        for(int i = 0; i < a.length; i++)
        {
            for(int j = 0; j < a[i].length ; j++)
            {
                if(a[i][j] != b[i][j])
                    return false;
            }
        }
        return true;
    }

    public static void print(int[][] a)
    {
        for(int i = 0; i < a.length ; i++)
        {
            for(int j = 0; j < a[i].length; j++)
                System.out.print(a[i][j] + " ");
            System.out.println();
        }
        System.out.println();
    }

    public static void light(int[][] a)
    {
        for(int i = 0;i < a.length; i++)
        {
            for(int j = 0; j < a[i].length; j++)
            {
                if(a[i][j] == 1)
                    light(a,i,j);
            }
        }
        convert(a);
    }

    public static void light(int[][] a, int i, int j)
    {
        for(int p = i - 1; p <= i + 1; p++)
        {
            for(int q = j - 1; q <= j + 1; q++)
            {
                try
                {
                    if(a[p][q] != 1)
                        a[p][q] = 2;
                }catch(Exception e){}
            }
        }
    }

    public static void convert(int[][] a)
    {
        for(int i = 0; i < a.length; i++)
        {
            for(int j = 0; j < a[i].length; j++)
            {
                if(a[i][j] == 2)
                    a[i][j] = 1;
            }
        }
    }
}

Please help to improve my code.

Your algorithm is faulty, because it only tries to eliminate redundant lamps in the order in which they were installed.

Consider a 1 × 9 array with 7 initial lamps L0 … L6 at positions 2 … 8.

Your algorithm would first eliminate L0 at position 5, then L1 at position 4.  It would consider L2 and L3 essential.  Then it would eliminate L4 at position 7.  L5 and L6 would be essential.  Total lamps eliminated: three.

An optimal solution would eliminate four lamps at positions 3, 4, 6, 7.


Incrementing and displaying a field if not empty I've got this code to work, but being really new to PHP, I don't know if this is proper. This is my first time using PHP to increment.

I have 10 fields for YouTube videos (using Advanced Custom Fields in WordPress - I don't have the repeater fields and won't be getting them)
The video/html elements only show if the corresponding video field is not empty

Are the variables correctly placed?

Are there better ways to do this?

    <?php
         $vidnum = 'video_';
         for($n=0; $n<=9; $n++) {
         $next = $vidnum.($n +1 );
         $video = get_field('' . $next . '');
             if (!empty($video))
                    echo '
' . $video . '
';
                }

        ?>

$vidnum = 'video_';

Presumably $vidnum is short for $video_number, but this isn't a video number.  It's the prefix before the video number.

     $video_number_prefix = 'video_';

You can go ahead and call it what it is.

     for($n=0; $n<=9; $n++) {
     $next = $vidnum.($n +1 );

You say that you have ten fields but you write 9.  There are two ways to write it with 10.

     for ( $n = 0; $n < 10; $n++ ) {

But the second works better with your $next variable, which I'm going to rename to $video_identifier.

     for ( $i = 1; $i <= 10; $i++ ) {
         $video_identifier = 'video_' . $i;

You don't need to save the value of the string literal.  You only use it once, so you can just use it.

Starting with 1 instead of 0 means that you don't have to add 1 to the value before using it.

I switched from $n to $i, as $i is a more common loop iteration variable.

     $video = get_field('' . $next . '');

This seems more complicated than it needs to be.

         $video = get_field($video_identifier);

Adding the empty strings doesn't seem to accomplish anything.

         if (!empty($video))
             echo '
' . $video . '
';

The single statement version of an if is harder to read and maintain.

         if ( ! empty($video) ) {
             echo '
' . $video . '
' . "\n";
         }

I also added a line break at the end.  Functionally this won't matter, but it makes the HTML easier to read.

The whole thing:

<?php
     for ( $i = 1; $i <= 10; $i++ ) {
         $video_identifier = 'video_' . $i;
         $video = get_field($video_identifier);
         if ( ! empty($video) ) {
             echo '
' . $video . '
' . "\n";
         }
     }
?>

This also fixes your indentation issues.

Note that I'm not commenting on your use of get_field.  Looking at the documentation, it seems that get_field depends heavily on the configuration.  Without the configuration, that is off-topic for review.


Looping through selected cells to indent text I have written the following Google Spreadsheet script that attempts to loop through all selected cells and then update the value so that it adds an indent, by adding

=CONCAT(REPT( CHAR( 160 ), 5),"' + value[row] + '")

around the value.

Is there a better way to achieve this?

var ss = SpreadsheetApp.getActiveSpreadsheet();

function indentText() {
  var values = ss.getActiveRange().getValues();
  var newValues = new Array();

  for (i = 0; i < values.length; i++) {
    if (values[i][0] != '') {
      newValues.push(['=CONCAT(REPT( CHAR( 160 ), 5),"' + values[i][0] + '")']);
    } else {
      newValues.push(['']);
    }
  }

  ss.getActiveRange().setValues(newValues);

};

function onOpen() {
  var sheet = SpreadsheetApp.getActiveSpreadsheet();
  var entries = [{
    name : "Indent Text",
    functionName : "indentText"
  }];
  sheet.addMenu("Indent Text", entries);
};

Interesting question,

there is clearly a lack in the Google Script API to indent cells..

Still, I find the CONCAT approach ugly, if one wants to indent 2 times, the formula will be:

=CONCAT(REPT( CHAR( 160 ), 5),"=CONCAT(REPT( CHAR( 160 ), 5),"'Hello World'")")

Which is ugly, I would simply pre-calculate the prefix and concatenate in the script and not let the formula do the work. This will also make un-indenting much easier.


Replace all occurrences with the properties of an object The basic idea is to replace all special expressions, e.g., [%InvoiceNo%], [%DueDate%], in a string with the properties of an object, Invoice invoice.

string str = "Your invoice [%InvoiceNo%] will be due on [%DueDate%]";
Invoice invoice = new Invoice { InvoiceNo = "123456", DueDate = DateTime.Parse("2011.12.29") };
string result = GetNewValue(str, invoice);
//The expected result is: Your invoice 123456 will be due on 11/29/2011

I think the simplest way to implement GetNewValue() could be

private string GetNewValue(string str, Invoice invoice)
{
    str = str.Replace("[%InvoiceNo%]", invoice.InvoiceNo);
    str = str.Replace("[%DueDate%]", invoice.DueDate.ToString());
    return str;
}

However, in my case, Invoice has a hundred properties and the target string only contains one or two properties. I rewrite GetNewValue() in the way I think it should work more efficiently. Here is my code

private string GetNewValue(string str, Invoice invoice)
{
    List<string> expressions = new List<string>();
    List<string> fields = new List<string>();

    var startIndices = str.IndicesOf("[%");
    var endIndices = str.IndicesOf("%]");
    int startLen = "[%".Length;
    int endLen = "%]".Length;

    for (int i = 0; i < startIndices.Count; i++)
    {
        expressions.Add(str.Substring(startIndices[i],
                                      endIndices[i] - startIndices[i] + endLen));
        fields.Add(str.Substring(startIndices[i] + startLen,
                                 endIndices[i] - startIndices[i] - startLen));
    }

    for (int i = 0; i < expressions.Count; i++)
        str = str.Replace(expressions[i], invoice.GetValueByName(fields[i]).ToString());

    return str;
}

StringExtender IndicesOf()

public static List<int> IndicesOf(this string target, string search)
{
    List<int> indices = new List<int>();
    int startIndex = 0;
    int index;

    while ((index = target.IndexOf(search, startIndex)) > -1)
    {
        indices.Add(index);
        startIndex = index + 1;
    }

    return indices;
}

GetValueByName() using Reflection

public class Invoice
{
    // Properties
    ......

    public object GetValueByName(string name)
    {
        PropertyInfo myProperty = typeof(Invoice).GetProperty(name);
        return myProperty.GetValue(this, null);
    }
}

How can I improve this code? Fast, less memory usage, or one-liner
Don't tell me the first approach is better. Orz
Thanks :)

You can do it in one loop instead of getting all the indexes separately. Just off the top of my head:

        string str = "Your invoice [%InvoiceNo%] will be due on [%DueDate%]";

        int startIndex = 0;

        while ((startIndex = str.IndexOf("[%", startIndex)) > -1)
        {
            int endIndex = str.IndexOf("%]", startIndex);
            string exp = str.Substring(startIndex, endIndex - startIndex + 2);
            string field = str.Substring(startIndex + 2, endIndex - startIndex - 2);
            str = str.Replace(exp, invoice.GetValueByName(field).ToString());
            startIndex = 0;
        }

Some points to note here:

I assume you are guaranteed to see the %] if you find the [%
I didn't test for edge cases like what if str = "[%invoice%]"

This is a neat solution but the more I think about your problem the more I wonder if you can engineer it so you pass what fields you want to your invoice object and it just returns you the correct string so you don't need to mess around with placeholders... food for thought :)


Return n largest nonzero entries of an array For something I'm working on, I need a function that takes in a one-dimensional array vec of integers and returns a boolean array of the same shape indicating where the n largest entries of vec are located.
For example,

nlargest([0, 1, 3, 5], 2) should yield [0, 0, 1, 1].
nlargest([0, 0, 4, 0, 3, 6], 2) should yield [0, 0, 1, 0, 0, 1].
nlargest([2, 1, 4, 3], 1) should yield [0, 0, 1, 0].

I have decided it's worthwhile to write my own function to do this, because the input data in this case has a few "nice" properties:

n is always strictly smaller than the number of nonzero entries in vec and greater than zero
The nonzero entries are all positive integers and there are no ties among them

Here is a working Julia function that does this:
function nlargest(vec, n)
    # Boolean vector shaped like input indicating n largest entries
    inp = copy(vec)
    out = zeros(Bool, length(vec))
    for i in 1:n
        am = argmax(inp)
        out[am] = true
        inp[am] = -1
    end
    return out
end

I am more interested in the design of the algorithm itself than the specific Julia implementation, so here is equivalent pseudocode:

Initialize: out ← a array of boolean 0s shaped like vec
Repeat n times:

j ← argmax(vec)
Set the jth entry of out to 1
Set the jth entry of vec to -1 (*)

Return out

(*) is taking advantage of the fact that all the nonzero entries are positive, but it feels like a bit of a hack to me. An alternative idea I had for this step was to "pop" the jth entry out of vec so that argmax(vec) has shorter input on the next loop. But it seems to me that the time savings there are offset by then having to adjust subsequent j values based on the new length of vec. Is this reasoning sound, or is there something clever I can do here?
Have I taken full advantage of the structure of my input data? Can I do better than the default argmax() function?
Of course, feedback on the Julia implementation is also welcome.

The algorithm you described has complexity O(n * m), where m is the size of the input array, since you run a full argmax at every one of the n iterations.
You can achieve the same thing by collecting the indices of the n largest values once, and then set only those indices to 1 in the result array.  For finding of the n largest values, you could use a heap, but Julia makes this easier with partialsortperm:
function nlargest(v, n; rev=true)
    result = falses(size(v))
    result[partialsortperm(v, 1:n; rev=rev)] .= true
    return result
end

This uses a BitArray for storage; if n << m, even a sparse array might pay off.  It should have complexity O(m + n log n), unless I'm misjudging partialsortperm.  Note that sorting algorithms in Julia work ascending by default, so you have to use rev=true to get the equivalent of your code.


Enum Constants for Convert Units I have a few constants in a game that I'm doing for hobby. I need to store constants for the total size of the a Physical World and the size of the Screen.

I can position the world's objects to the screen or vice versa.

To position the images on the screen for example I get the position that the body occupies in the physical world and transform to the screen by doing:

(Full Screen Size / Total size of the World) * position of the object in the world.

I came up with an ingenious way to keep these constant while I do conversion operations using the enum below:

import com.badlogic.gdx.math.Vector2;
import static br.com.games.Test.Sizes.*;

public class Test {

    public static enum Sizes {
        WORLD(new Vector2(25.806f, 15.48f)), SCREEN(new Vector2(800f, 480f)), TRANSFORM(
                new Vector2(-1, -1));

        private Vector2 value;

        private Sizes(Vector2 value) {
            this.value = value;
        }

        private Vector2 inputValue;
        private Vector2 sourceValue;

        public Sizes value(Vector2 value) {
            inputValue = value;
            return this;
        }

        public Sizes from(Sizes size) {
            sourceValue = size.value;
            return this;
        }

        public Vector2 to(Sizes size) {
            float x = size.value.x / sourceValue.x * inputValue.x;
            float y = size.value.y / sourceValue.y * inputValue.y;
            return Vector2.Zero.set(x, y);
        }

        public Vector2 getValue() {
            return value;
        }
    }

}

I can use it this way:

    public static void main(String[] args) {
        TRANSFORM.value(new Vector2(10, 10)).from(WORLD)
                .to(SCREEN);
    }

Vector2 class is here.

What do you think of this way of using constants and operations? Do you see any problems? Could you point out some improvement?

I'm not at all sold on TRANSFORM being part of your enum. The API for this enum lets you make nonsense calls like WORLD.from(WORLD).to(TRANSFORM). Always try to prevent invalid use of your APIs. I'm not really sure why you wouldn't use a naive approach like two static methods Transformer.worldToScreen(Vector2) and Transformer.screenToWorld(Vector2). Are you anticipating needing additional conversions later?

If you're really hankering for a fluent API for some reason, you could do Transform.value(Vector2D).from(Sizes).to(Sizes). You can control the return types to prevent at least some of the possible errors, but there are still some invalid calls like Transform.value(...).from(WORLD).to(WORLD).

**** EDIT ****

Since you're interested in the fluent approach, here's something to get you started. Obviously it needs documentation and input checking. The DisplayType enum can either belong to Transform or it can be top-level, depending on your needs. Likewise, the two inner classes can easily be split out.

As far as not instantiating objects, you can't really do a fluent API correctly without new objects. Do you have a real, demonstrated performance issue with creating new objects? Many people wrongly assume that object creation and garbage collection will be a big issue without testing.

If you really need to do this without new object instances, then your only good option as I see it is static methods. Your Sizes enum is too easy to use incorrectly.

public final class Transform {

    public static enum DisplayType {
        SCREEN(new Vector2(800f, 480f)),
        WORLD(new Vector2(25.806f, 15.48f));

        private final Vector2 size;

        private DisplayType(final Vector2 size) {
            this.size = size;
        }
    }

    private Transform() {
        super();
    }

    public static From value(final Vector2 value) {
        return new From(value);
    }

    public static final class From {

        private final Vector2 value;

        From(final Vector2 value) {
            this.value = value;
        }

        public To from(final DisplayType sourceDisplayType) {
            return new To(this.value, sourceDisplayType);
        }
    }

    public static final class To {

        private final Vector2 value;
        private final DisplayType from;

        To(final Vector2 value, final DisplayType from) {
            this.value = value;
            this.from = from;
        }

        public Vector2 to(final DisplayType targetDisplayType) {
            /* TODO: Do math here */
            throw new UnsupportedOperationException();
        }
    }
}


Converting an image to black and white This code is a project that I am working on to eventually analyze some images but right now I am purely trying to read an image and convert it to black and white.  The input should be either white or something else which would end up as black so it is easy to check for this.

import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import numpy as np

img = mpimg.imread('./Training/Image1.png')

imgplot = plt.imshow(img)

width = img.shape[1]
height = img.shape[0]

def generateArray():
    arr = []
    for y in range(img.shape[0]):
        arr.append([])
        for x in range(img.shape[1]):
            if img[y][x][0] != 1:
                arr[y].append(1)
            else:
                arr[y].append(0)
    return arr

arr = generateArray()

plt.show()

To be clear, I desire to create an array arr that contains either a 0 if the corresponding pixel in the inputted image is white or 1 if it is anything other than white.

I am somewhat of a beginner with Python but I am confused as to why this code takes so long to run (>19 seconds on my older Mac).  Is there something that I am missing that would speed it up significantly?

Yes, there are a few things which can be done to speed up your code.

You create local variables width and height.  But then you don't use these variables.  Instead you use for x in range(img.shape[1]): which ends up evaluating img.shape[1] a total of height times.  Consider that img.shape retrieves the shape array from img, and then accesses the [1] member of that list.  Using for x in range(width): doesn't have that overhead.

Consider arr[y].append(_).  Again, this code is looking up in the arr list, the [y] element, and to that retrieved list appending a value.  That done once for every pixel.  If you kept a handle to the list that you are appending to, you wouldn't have to look it up each time.

def generateArray():
    arr = []
    for y in range(height):
        row = []
        for x in range(width):
            if img[y][x][0] != 1:
               row.append(1)
            else:
               row.append(0)
        arr.append(row)
    return arr

The above code should be a little faster.

Appending is a time-consuming operation.  If the list is stored as an array, rather than a linked-list, then appending an element will require frequent reallocation of the array capacity, and copying of all of the elements to the new storage area.  We can prevent this reallocating and copying by allocating storage for all of the data all at once:

def generateArray():
    arr = [None] * height          # Correctly sized array of rows
    for y in range(height):
        row = [0] * width          # Correctly sized row, filled with 0's
        for x in range(width):
            if img[y][x][0] != 1:
               row[x] = 1
        arr[y] = row
    return arr

Here, the row array starts off with [0, 0, 0, 0, ..., 0, 0, 0] so it is only necessary to set the elements to 1 where needed.

Looping and list lookup can be slow.  Consider:

        for x in range(width):
            if img[y][x][0] != 1:
                row[x] = 1

which loops over all the x values of a row, and for every x value, looks up the row img[y], and then the pixel in the row img[y][x], for each pixel in that row, and then accesses the [0] element of that pixel.  That's a lot of lookups.  If instead we used:

        for x, pixel in enumerate(img[y]):
            if pixel[0] != 1:
                row[x] = 1

we'd be iterating over the row of pixels, getting their values without the double list lookup.

We could also use list comprehension to build the list.  Since each row is of a fixed, known length, the list comprehension can allocate the correctly sized list, and fill in the elements one-at-a-time, without indexing or appending.

def generateArray():
    arr = [None] * height
    for y in range(height):
        arr[y] = [ 1 if pixel[0] != 1 else 0 for pixel in img[y] ]
    return arr

That also applies to building each row.

def generateArray():
    return [ [ 1 if pixel[0] != 1 else 0 for pixel in row ] for row in img ]

The function generateArray() uses a global variable img.  It would be better to pass img into the function.

def generateArray(img):
    # code which uses img

generateArray() is a terrible name for the function.  Maybe generateMaskFromImage()?

The output arr is not being used by your code.  If you omitted the line:

arr = generateArray()

your code would run much, much faster.   ;-)


Fibonacci sum with memoization Problem:

  Using the recursion approach, find a Fibonacci sum without repetition of computation.

def sum_fibonacci(n):
    """Compute the nth Fibonacci number.

    >>> sum_fibonacci(35)
    9227465
    >>> sum_fibonacci(10)
    55
    >>> sum_fibonacci(0)
    0
    >>> sum_fibonacci(1)
    1
    >>> sum_fibonacci(5)
    5
    """
    """Your code here"""

Solution:

fibcache = {}
def  sum_fibonacci(n):
    """Compute the nth Fibonacci number.

    >>> sum_fibonacci(35)
    9227465
    >>> sum_fibonacci(10)
    55
    >>> sum_fibonacci(0)
    0
    >>> sum_fibonacci(1)
    1
    >>> sum_fibonacci(5)
    5
    """
    if n == 0:
        fibcache[n] = 0
        return fibcache[n]
    elif n == 1:
        fibcache[n] = 1
        return fibcache[n]
    else:
        sum_left = 0
        sum_right = 0
        if n-2 in fibcache.keys():
            sum_left += fibcache[n-2]
        else:
            sum_left += sum_fibonacci(n-2)
            fibcache[n-2] = sum_left
        if n-1 in fibcache.keys():
            sum_right += fibcache[n-1]
        else:
            sum_right += sum_fibonacci(n-1)
            fibcache[n-1] = sum_right
        return sum_left + sum_right

This program uses dictionary data model amidst tree recursion.

Can it be more readable? Can it avoid global cache fibcache update? Because nonlocal is better than global.

Note: I'm currently aware of data models - class 'tuple', class 'list' and class 'dict'.

I think that caching should look the same on every function,

cached_f(args):
    if args not in cache:
        cache[args] = f(args)
    return cache[args]

So Fibonacci becomes:

cache = {}
def fib(n):
    if n not in cache.keys():
        cache[n] = _fib(n)
    return cache[n]

def _fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

I'm not sure why the cache should not be global (other than namespace pollution), you could end with duplication of the results and also missing a cached result making you compute again what you wanted to avoid computing.

Also, you may initialize the cache with the base cases and skip them when writing the recursion, but that is not so clean.


Probabilistic Matrix Inspection - Suggested by a paper, implemented by me I have read this paper and I actually found it interesting.

This is an attempt to implement the proposed algorithm. I would like to know:

Is my algorithm correct by what is discribed in the paper?
Is my algorithm easy to understand?

Here is my little program

// Based on http://www.ijcai.org/Proceedings/16/Papers/053.pdf
//
// The paper uses two matrices, but I decided to "join" them into 1 matrix of
// tuples. Things are easier this way (isn't it a valid reason?).
//
// A matrix is a list of lists, but...
//
// It is not like you would expect.
//
// Each inner list represents a column, not a row!
//
// A "standard" visualization of a matrix is:
//        column1  column2  column3
//  row1 (1,  90) (1,  10) (0,  90)
//  row2 (0,   0) (1, 100) (1,  40)
//  row3 (0,  10) (1,  80) (1, 100)
//
// In my program it is seen as:
//           row1        row2        row3
//  colum1 (1,  90)    (0,   0)    (0,  10)
//  colum2 (1,  10)    (1, 100)    (1,  80)
//  colum3 (0,  90)    (1,  40)    (1, 100)
//
// It is made this way because, in this specific case, it is easier to go
// recursively in a list of columns.

let exampleMatrix = [
    [1,  90;    0,   0;    0,  10]

    [1,  10;    1, 100;    1,  80]

    [0,  90;    1,  40;    1, 100]
]

let optimalColumnOrderOf matrix =
    let sumProbabilities column =
        column
        |> List.map (fun (_, q) -> q)
        |> List.reduce (+)

    let comparator column1 column2 =
        let sum1 = sumProbabilities column1
        let sum2 = sumProbabilities column2

        sum2 - sum1

    matrix
    |> List.sortWith comparator

let thereIsZeroProbabilityIn column =
    List.exists (fun (_, q) -> q = 0) column

let optimalRowOrderOf column =
    let comparator (_, q1) (_, q2) =
        q2 - q1

    column
    |> List.sortWith comparator

let isColumnFeaseble column =
    let thereIsZeroIn c =
        c
        |> optimalRowOrderOf
        |> List.exists (fun (n, _) -> n = 0)

    if thereIsZeroProbabilityIn column then false
    else
        column
        |> List.filter (fun (_, q) -> q < 100)
        |> thereIsZeroIn
        |> not

let isMatrixFeaseble matrix =
    matrix
    |> optimalColumnOrderOf
    |> List.exists isColumnFeaseble

[<EntryPoint>]
let main argv =
    printf "%O" (isMatrixFeaseble exampleMatrix)

    System.Console.ReadKey() |> ignore

    0

In F# we prefer match over if:

if thereIsZeroProbabilityIn column then false
else
    column
    |> List.filter (fun (_, q) -> q < 100)
    |> thereIsZeroIn
    |> not

Should, instead, be:

match thereIsZeroProbabilityIn column with
| true -> false
| false ->
    column
    |> List.filter (fun (_, q) -> q < 100)
    |> thereIsZeroIn
    |> not

In the case where you're only piping to one other function, you should stay consistent with whether you inline the pipe or not:

 System.Console.ReadKey() |> ignore

and

column
|> List.sortWith comparator

Are inconsistent, generally speaking I prefer to inline the pipe when there is only one pipe happening. (It seems to make be more readable that way.)

column |> List.sortWith comparator

You reduce LoC and make use of the horizontal spacing.

let comparator column1 column2 =
    let sum1 = sumProbabilities column1
    let sum2 = sumProbabilities column2

    sum2 - sum1

In that case you should not be using the local constants, they only create overhead on the stack, they're not used more than once, and they're not cached, so in reality they provide no additional value.

let comparator column1 column2 =
    (sumProbabilities column2) - (sumProbabilities column1)

Again, reduce vertical space a little.

Other than this, I have nothing else to say about the code except maybe to shorten some of the names. It's awful verbose. It's good F# already, my modifications are merely recommendations. Good work. :)


Check for iOS version Here's an approach i came up with for checking IOS versions.

#define __PROCESS_INFO  ([NSProcessInfo processInfo])
#define CURRENT_IOS     ([__PROCESS_INFO operatingSystemVersion])

#define IOS(x)          ((NSOperatingSystemVersion){[x integerValue], 0, 0})
#define IOS9            ((NSOperatingSystemVersion){9, 0, 0})
#define IOS10           ((NSOperatingSystemVersion){10, 0, 0})
#define IOS11           ((NSOperatingSystemVersion){11, 0, 0})

#define IS_IOS9         ([__PROCESS_INFO isOperatingSystemAtLeastVersion:IOS9] && \
                                ![__PROCESS_INFO isOperatingSystemAtLeastVersion:IOS10])
#define IS_IOS10        ([__PROCESS_INFO isOperatingSystemAtLeastVersion:IOS10] && \
                            ![__PROCESS_INFO isOperatingSystemAtLeastVersion:IOS11])

that way this type of code is more readable

if (IS_IOS9) {
    // [... openURL: ...];
}
else if (IS_IOS10) {
   // [... openURL:options:completionHandler: ...];
}

Let me know what you think ...

If you need to check if a certain method exists you can also check if the object supports it via respondsToSelector: like this:

if ([object respondsToSelector:@selector(openURL:options:completionHandler:)]) {
    [object openURL:...options:...completionHandler:...];
} else {
    [object openURL:...];
}

I think this approach is more flexible than checking the OS version. I've seen many people doing this.

This is similar to how JavaScript programmers check existence of certain JS features: if they checked the browser version instead, the code would be unmaintainable as there are a lot of browsers and they constantly evolve.


Increase performance of a method which finds the element removed from an array Imagine that you have a TreeSet of numbers, and you copy them into an array, but you remove one element of it. You want to know the element removed.

import java.util.Arrays;
import java.util.Set;

import com.google.common.collect.Sets;

public class Question {

    private static final Set<Integer> SET = Sets.newTreeSet(Arrays.asList(1, 3, 5, 7));

    public static void main(String[] args) {
        int[] unsorted = {1, 5, 3};

        int elementRemoved = checkElementRemoved(unsorted);
        System.out.println("Element removed " + elementRemoved);
}

private static int checkElementRemoved(final int[] unsorted) {
    Integer elementRemoved = null;
    for (Integer number : SET) {
        if (!arrayContains(unsorted, number)) {
            // O(n^2) complexity
            elementRemoved = number;
            break;
        }
    }
    return elementRemoved;
}

private static boolean arrayContains(final int[] unsorted, final int number) {
    for (Integer inArray : unsorted) {
        if (inArray == number) {
            return true;
        }
    }
    return false;
}

The problem is that this solution has \$O(n^2)\$ complexity and I would like to improve the performance.

I think that the best option would be to sort the array, am I right?

I think that the best option would be to sort the array, am I right?

Not exactly. You could sort it and reduce the complexity using a binary search to O(n log(n)). But you could much better by copying the array into a HashSet and getting O(n) assuming no perverted distribution (the worst case hash table access is O(n), but occurs very rarely).
The search itself could be even faster, when using two sorted arrays. As all the  data come from a Set, there are duplicates.  So whenever the element of the first array at a given position equals to the element of the other array at the same position, you know that you're before the removed element. Using a binary search you can get a complexity of O(log(n)). However, producing the the second array costs O(n), so you don't gain anything w.r.t. the O-notation.
Review
private static final Set<Integer> SET = Sets.newTreeSet(Arrays.asList(1, 3, 5, 7));

This is fine for the test data, but then you should define another constant for unsorted, too.
private static int checkElementRemoved(final int[] unsorted) {
    Integer elementRemoved = null;
    for (Integer number : SET) {
        if (!arrayContains(unsorted, number)) {
            // O(n^2) complexity
            elementRemoved = number;
            break;
        }
    }
    return elementRemoved;
}

You're not checking anything. Call it find... or alike. Don't use useless variables. It all can be reduced to
private static int checkElementRemoved(int[] unsorted, Iterable<Integer> set) {
    for (Integer number : set) {
        if (!arrayContains(unsorted, number)) {
            // O(n^2) complexity
            return number;
        }
    }
    throw new WhateverException();
}

Your code secretly throws a NullPointerException when unboxing elementRemoved. This is pretty bad. Throwing NPE explicitly would be much better, but NPE is not the right exception here. Letting your method return an Integer would be better, but only postpone the problem. Actually, IllegalArgumentException sounds right, as it's not allowed to pass an array missing no element.
In any case, you should pass SET as an argument, so that your method is more usable.
private static boolean arrayContains(final int[] unsorted, final int number) ...

This is no better than Arrays.asList(unsorted).contains(number). But as already said, create a HashSet and use it for speed.


Program for checking gaps in hierarchy? In my data I have few hierarchy values - example address

Name -> Street -> City -> County -> State -> Country

The validation I need is: if a value in the above hierarchy is present, then all the previous/higher order values should be present.
Below is a valid case

Name -> Street -> City -> State
This is valid even though there is no country - as it is last in the order

and below is an invalid case

Name -> Street -> State -> Country
This is invalid as there is no City Which is of higher order than state and country.

The below code helped me in doing the checks. Can this be simplified further? I want to get rid of the last dummy return statement. (To the best of my knowledge, it is difficult to get rid of it. But there are more people far more knowledgeable than me.)
 package com.example.demo;

public class SimplyfyHierarchyCheck {

    public static void main(String[] args) {

        String a="a", b="b", c="c", d="d";

        SimplyfyHierarchyCheck shc = new SimplyfyHierarchyCheck();
        System.out.println(shc.isGapLessHierarchy("a", b, "", "") );
    }

    //can this method be made even more concise.
    private boolean isGapLessHierarchy(String... args) { //Hierarchy
        boolean isGapLess=true;

        for(int i=args.length-1; i>=0; i--) {
            if(args[i].isBlank() )  //nothing to check
            {
                continue;
            }
            for(int j=i-1; j>=0; j--) {
                if(args[j].isBlank() )  //gap found i.e false
                {
                    return false;
                }
            }
        }
        return isGapLess; //dummy return // am required to return true or false // can i get rid of this
    }

}

As a long-term Java programmer, I know that most of my time will be spent in maintenance.
On that basis I prefer simple code that expresses its purpose clearly to clever, concise, unclear code.
With that context in place here's some basic comments.
 String a="a", b="b", c="c", d="d";

It's not the Java way to do multiple declarations together - I'd
split these.

They are constants not variables, so they should be "static final" (and UPPERCASE).

Three of them are not used, so delete them.
System.out.println(shc.isGapLessHierarchy("a", b, "", "") );

Why do you mix use of a constant and a literal? As a maintenance
programmer looking at your code I'm now wondering whether this has
some significance.

Now to your "isGapLessHierarchy()" method:

The method has no dependency on an object, so it should be "static"
Never call anything "args" (other than perhaps the arguments to a main method). Give your method parameters meaningful names. How about "hierarchyElements" in this case?
(Almost) Never use 'i' and 'j' as indexes. Use something meaningful.
Going forwards through a list is (IMHO) clearer than going backwards. Your condition can be expressed as "a gap should never be followed by a non-gap", which allows us to go forwards.

Here's my code using your pattern, with some cleanup and adding a more extensive set of tests (I couldn't be bothered with Junit in this case, but you probably should).
  public class HierarchyCheck {

  public static void main(String[] args) {
    String[][] testCases = new String[][]{
      new String[]{"Name", "Street", "City", "County", "State", "Country"},
      new String[]{"Name", "Street", "City", "County", "State", ""},
      new String[]{"Name", "Street", "City", "County", "", "Country"},
      new String[]{"Name", "Street", "", "County", "State", "Country"},
      new String[]{"Name", "", "City", "", "State", "Country"},
      new String[]{"Name", "", "", "", "", ""}
    };

    for (String[] testCase : testCases) {
      System.out.format("%s %s gapLess%n",
                        Arrays.toString(testCase),
                        isGapLessHierarchy(testCase) ? "is" : "is not");
    }
  }

  private static boolean isGapLessHierarchy(String... hierarchyElements) {

    // Find the first gap
    int firstGap = 0;
    for (firstGap = 0; firstGap < hierarchyElements.length; firstGap++) {
      if (isBlank(hierarchyElements[firstGap])) {
        break;
      }
    }

    // Is there a non-gap after the first gap?
    for (int nonGap = firstGap + 1; nonGap < hierarchyElements.length; nonGap++) {
      if (!isBlank(hierarchyElements[nonGap])) {
        // There is, so it's not gapless
        return false;
      }
    }

    // Definitely gapless
    return true;
  }

  // We don't have Java 11 for the String.isBlank() method, so fake it!
  private static boolean isBlank(String string) {
    return (string == null) || (string.trim().length() == 0);
  }
}

However, I'd probably have gone for a simpler, arguably cruder approach.
  private static boolean isGapLessHierarchy(String... hierarchyElements) {

    boolean seenGap = false;

    for (String hierarchyElement : hierarchyElements) {
      if (isBlank(hierarchyElement)) {
        seenGap = true;
      }
      else {
        if (seenGap) { // gap followed by non-gap
          return false;
        }
      }
    }

    // Definitely gapless
    return true;
  }


Extending SeqLike - move an element to the front of the sequence I wrote a method called bringToFront, which moves an element a to the first position of a sequence seq if it exists; otherwise, seq is returned.
If a appears in the sequence more than once, only the first occurrence is moved.

Sample input/output:

List(1, 2, 3, 4, 3).bringToFront(1)     // List(1, 2, 3, 4, 3)
List(1, 2, 3, 4, 3).bringToFront(2)     // List(2, 1, 3, 4, 3)
List(1, 2, 3, 4, 3).bringToFront(3)     // List(3, 1, 2, 4, 3)
List(1, 2, 3, 4, 3).bringToFront(4)     // List(4, 1, 2, 3, 3)
List(1, 2, 3, 4, 3).bringToFront(5)     // List(1, 2, 3, 4, 3)

I could have easily defined these as extensions on List[A] or Seq[A], but I wanted to try and define them for the most abstract type possible, SeqLike[A, Repr]. For this, a CanBuildFrom is needed (I think).

Code:

implicit class SeqLikeOps[A, Repr <: SeqLike[A, Repr]](seq: SeqLike[A, Repr]) {
  def bringToFront(a: A)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Repr = {
    seq.find(_ == a) match {
      case Some(_) => a +: seq.removeFirst(a)
      case _ => seq.repr
    }
  }

  def removeFirst(a: A)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Repr = {
    val b = cbf()

    @tailrec
    def go(xs: SeqLike[A, Repr]): Unit = xs match {
      case h +: t if h == a => b ++= t
      case h +: t => b += h; go(t)
      case _ => ()
    }

    go(seq)
    b.result()
  }
}

My concerns:

Is this the correct way of extending types like SeqLike or TraversableLike in general?
In SeqLike[A, Repr], A and Repr are covariant. In SeqLikeOps[A, Repr], they're not, because they appear in a contravariant position in the signatures of bringToFront and remoteFirst. Is there any downside to this? Could they, somehow, be made covariant?
Do I need the upper bound <: SeqLike[A, Repr]?
Are the names I chose for these methods good? Suggestions are welcome.
Is there a more efficient (in regards to memory and/or time complexity) and/or idiomatic way of implementing this?

Feel free to point out anything else I might have done wrong.

You might be overcomplicating a bit by reaching further than you need into builder mechanics.  If you rewrite the signature of SeqLikeOps to

import scala.language.higherKinds
implicit class SeqLikeOps[A, F[_]](seq: SeqLike[A, F[A]])
  (implicit cbf: CanBuildFrom[F[A], A, F[A]]) {

then bringToFront can basically look like this:

def bringToFront(a: A): F[A] = {
  val as = // Do some magic with seq
  as.to[F]
}

Using higher kinds makes the upper bound go away while leaving the messy details of building to .to[F]
Here's one way to do that using Iterators for efficient space usage and gc and for their laziness.

implicit class SeqLikeOps[A, F[_]](seq: SeqLike[A, F[A]])(implicit cbf: CanBuildFrom[F[A], A, F[A]]) {
  private sealed trait Step {
    def iter: Iterator[A]
    def run(x: A): Step
  }
  private case class Found(iter: Iterator[A]) extends Step {
    def run(x: A) = Found(iter ++ Iterator(x))
  }
  private case class NotFound(iter: Iterator[A], val a: A) extends Step {
    def run(x: A) =
      if (x == a)
        Found(Iterator(x) ++ iter)
      else
        NotFound(iter ++ Iterator(x), a)
  }
  def bringToFront(a: A): F[A] = {
    val result = seq.iterator.foldLeft(NotFound(Iterator[A](), a): Step) {
      (s, a) => s.run(a)
    }
    result.iter.to[F]
  }

}

Using Iterator this way does grow the heap in proportion to the size of seq, because of the lazy ++.  There are other ways to do this, still using the continuation-passing-style of Found/NotFound, which don't even do that.  If such a solution isn't clear to you, I can provide one on request.

That aside, using an Iterator to build the final collection is a win.

As to variance, I can see no use for it in SeqLikeOps.  Your aim here is to be returning the same collection type wherever possible and the same A always.  Any subtype of F[A] is going to be seqLike and you return F, so variance has no purpose.

Sticking with the direct use of the builder (which may give the best performance), you might want to consider indexOf rather than find.  Then if it returns -1 or 0, you just return the original. Otherwise you can build b using a, seq.take(index) and seq.drop(index + 1) with no recursion or other tricks needed.  Oh, and you forgot sizeHint...

def bTF(a: A)(implicit cbf: CanBuildFrom[F[A], A, F[A]]): F[A] = {
  seq.indexOf(a) match {
    case i if i > 1 => {
      val b = cbf()
      b.sizeHint(seq)
      b += a
      b ++= seq take i
      b ++= seq drop (i + 1)
      b.result
    }
    case _ => seq.repr
  }
}

Of course, what we both really want is a way to minimise traversal.  Scala just doesn't make that as easy as I'd like.   But indexOf does mean only 1 traversal, with no new build, both if the value isn't found or if it is already at the front.  It also means equality tests are only done on one traversal, not two.

After a little more thought, I came up with a variant of the above solution which really only iterates just once.  But it may not be future-proof.

def bTFi(a: A)(implicit cbf: CanBuildFrom[F[A], A, F[A]]): F[A] = {
  val iter = seq.iterator
  val pred = iter.takeWhile(_ != a)
  val b = cbf()
  b.sizeHint(seq)
  b += a
  b ++= pred
  if (iter.isEmpty)
    seq.repr
  else {
    b ++= iter
    b.result
  }
}

Using the iterator this way means only one traversal of the collection.  It works because, when forced by the assignment to the builder, takeWhile(_ != A) has to examine the first element which does equal a.  And any Iterator operation which fetches the next element discards it after use.  So this does work with the absolute minimum of traversal and good economy of space.

I just have a feeling this may rely on an implementation detail that might change.  I will ask around.

EDIT:

Using anything other than next and hasNext on an iterator is considered not safe as the state of the iterator after any other operation is considered an implementation detail.  But hey,  here's an even simpler version:

def bTFi2(a: A)(implicit cbf: CanBuildFrom[F[A], A, F[A]]): F[A] = {
  val iter = seq.iterator
  val pred = iter.takeWhile(_ != a)
  (Iterator(a) ++ pred ++ iter).to[F]
}

which does feel a bit dirty.


Reading a collection of strings from the user I was trying to write a program that will read a collection of strings from the user, and then end the moment it encounters a ".". So then I write a do-while loop.

I came across a something like this:

string temp;
vector<string> params;
do
{
    cin >> temp;
    if (temp == ".")
        break;

    params.push_back(temp);

} while (temp != ".");

I realized that no matter what, the loop will always end from within its body -- which is the exact result that want.

But there something about piece of code that smells fishy. Are there any better ways?

Another thing to note: I don't want the "." to be pushed onto the vector, hence that's why I added that little if (temp == ".") break; statement.

Don't forget to check the stream status for errors or EOF.

while (cin >> temp && temp != ".")
{
    params.push_back(temp);
}

EDIT: You do not necessarily need to invent your own break condition. There's one already — end of file. You can just read strings until you reach it. This way, your program will also work with non-interactive input nicely. To generate an end of file on a terminal, type Ctrl+D on Unix/Linux and Ctrl+Z on Windows.

while (cin >> temp)
{
    params.push_back(temp);
}


How to apply Python generators to finding min and max values? I'm solving yet another problem in HackerRank (https://www.hackerrank.com/challenges/determining-dna-health/problem). In short: you are given 2 arrays (genes and health), one of which have a 'gene' name, and the other - 'gene' weight (aka health). You then given a bunch of strings, each containing values m and n, which denote the start and end of the slice to be applied to the genes and health arrays, and the 'gene'-string, for which we need to determine healthiness. Then we need to return health-values for the most and the least healthy strings.

My solution is below, and it works, but it's not scalable, i.e. it fails testcases with a lot of values.

import re
if __name__ == '__main__':
    n = int(input())

    genes = input().rstrip().split()

    health = list(map(int, input().rstrip().split()))

    s = int(input())
    weights = []
    for s_itr in range(s):
        m,n,gn = input().split()
        weight = 0
        for i in range(int(m),int(n)+1):
            if genes[i] in gn:
                compilt = "r'(?=("+genes[i]+"))'"
                matches = len(re.findall(eval(compilt), gn))
                weight += health[i]*matches
        weights.append(weight)
    print(min(weights), max(weights))

Can you advise on how to apply generators here? I suspect that the solution fails because of the very big list that's being assembled. Is there a way to get min and max values here without collecting them all?

Example values:

genes = ['a', 'b', 'c', 'aa', 'd', 'b']
health = [1, 2, 3, 4, 5, 6]
gene1 = "1 5 caaab" (result = 19 = max)
gene2 = "0 4 xyz" (result = 0 = min)
gene3 = "2 4 bcdybc" (result = 11)

This case returns 0 19

UPD: Follow-up question on optimized (but still not working) solution here.

eval(...)

What is the purpose of:

compilt = "r'(?=(" + genes[i] + "))'"
... eval(compilt), ...

It takes a string like "aa", and forms a new string "r'(?=(aa))'", which is source code for the raw string r'(?=(aa))', which when evaluated yields the string "(?=(aa))".

There is no escaping being done, no obvious reason to do the raw string formation and subsequent evaluation, and no prevention of a syntax error due to a stray ' character in the genes[i] array.  So ... why not simply:

regex = "(?=(" + gene[i] + "))"

and no call to eval(...) at all?

Regex Capturing

The regex subexpression (...) is a "capturing group", which copies the matching characters into an internal buffer, for returning in the match group.

>>> re.findall('(?=(aa))', "caaab")
['aa', 'aa']

Without the capturing group, the matching characters do not have to be copied to the internal buffer, to be returned.

>>> re.findall('(?=aa)', "caaab")
['', '']

Given that you are only interested in the len(...) of the list returned from re.findall(), the capturing group seems like unnecessary overhead, which can be eliminated for faster execution.

Compiled Regex

As Python uses regular expressions, it maintains a cache of the most recently used regular expressions.  This cache has a limited size, to prevent an excessive memory load.

In this exercise, you are repeatedly using the same gene regular expressions for each "healthy string" test.  If the number of genes exceeds the cache size, Python will be tossing out compiled regular expressions, only to compile them again moments later.

You can preempt this by compiling and storing all the gene regular expressions ahead of time.  Leveraging Python 3.6's f-strings, and list comprehension:

    genes = input().rstrip().split()
    genes_rx = [re.compile(f"(?={gene})") for gene in genes]

Used as:

               matches = len(re.findall(genes_rx[i], gn))

Now the gene to regular expression string, to compiled regular expression is done once per gene, instead of once per "healthy string" test.

Computing min/max weight without creating a list

How about:

    min_weight = math.inf
    max_weight = -math.inf

    for ...:

        weight = ...

        if weight < min_weight:
            min_weight = weight
        if weight > max_weight:
            max_weight = weight

    print(min_weight, max_weight)


Looping through the ResultSet efficiently and the add the values for columns in List I am working on a multithreaded project in which each thread will randomly find columns for that table and I will be using those columns in my SELECT sql query and then I will be executing that SELECT sql query. AFter exectuing that query, I will be looping through the result set and will add the data for each columns into List<String>.

Here columnsList will contains columns delimited by comma. For example-

col1, col2, col3

Below is my code.

class ReadTask implements Runnable {

public ReadTask() {

}

@Override
public run() {
  ...

  while ( < 60 minutes) {

    .....

    final int id = generateRandomId(random);
    final String columnsList = getColumns(table.getColumns());
    final String selectSql = "SELECT " + columnsList + "  from " + table.getTableName() + " where id = ?";
    resultSet = preparedStatement.executeQuery();

    List<String> colData = new ArrayList<String>(columnsList.split(",").length);
    boolean foundData = false;

    if (id >= startValidRange && id <= endValidRange) {

        if (resultSet.next()) {
            foundData = true;
            for (String column : columnsList.split(",")) {
                colData.add(resultSet.getString(column.trim()));
            }
            resultSet.next();//do I need this here?
        }
    } else if (resultSet.next()) {
        addException("Data Present for Non Valid ID's", Read.flagTerminate);
    }

    ....
      }
   }

    private static void addException(String cause, boolean flagTerminate) {
        AtomicInteger count = exceptionMap.get(cause);
        if (count == null) {
            count = new AtomicInteger();
            AtomicInteger curCount = exceptionMap.putIfAbsent(cause, count);
            if (curCount != null) {
                count = curCount;
            }
        }
        count.incrementAndGet();

        if(flagTerminate) {
            System.exit(1);
        }
    }
}

Problem Statement:-

After executing the SELECT sql query. Below are my two scenarios-

I need to see whether the id is between the valid range. If it is between the Valid Range then check whether resultSet has any data or not. If it has data then loop around the resultSet using the columns from the columnsList and start adding it in coldData list of String.
else if id is not in the valid range then I need to check I am not getting any data back from the resultSet. But somehow if I am getting the data back and flag is true to stop the program, then exit the program. Else if I am getting the data back but flag is false to stop the program, then count how many of those happening. So for this, I have created addException method.

Can anyone help me out whether the way I am doing here for my above two scenarios is right or not? It looks like, I can improve the if/else loop code more I guess for my above two scenario.

I am not that familiar with JDBC, but I think the method you search for is: isBeforeFirst: "true if the cursor is before the first row; false if the cursor is at any other position or the result set contains no rows"

This does not modify the results cursor then.

if (id >= startValidRange && id <= endValidRange)

I would change it to:

if (startValidRange <= id && id <= endValidRange)

Only a small change, but increase readability a lot (at least for me)


Javascript filter class to hide and show content on data-attributes I'm a hacker, not a trained engineer.  I ask/answer specific questions on StackOverflow and am pretty confident in my ability to get the browser to do what I want, I thought I could benefit a great deal from a code review- hopefully I'm in the right place.

Please tear down my bright-eyed naivetie with cutting comments on code style, design, etc if I am and let me know if this isn't what this site is for.

This is a filter class that hides and shows long lists of content in container divs based on the content meta data.  A sample content div:

<div class="todd.packer StreamContent"
  data-username="todd.packer"
  data-topic_id="13"
  data-post_id="1394">
  ...
</div>

The class itself (relies on JQuery):

function StreamFilter(_containerId, _testAttribute, _targetStyleClass, _applyStyleClass, _testFor){
    return{
        active : false,
        filterHash : {},
        testFor : _testFor,
        CONTAINER_ID : _containerId,
        TEST_ATTRIBUTE : _testAttribute,
        TARGET_STYLE_CLASS : _targetStyleClass,
        APPLY_STYLE_CLASS : _applyStyleClass,

        on : function(){
            this.active = true;
            this.enforce();
        },

        off : function(){
            this.clear();
            this.active = false;
            this.unenforce();
        },

        clear : function(){
            this.filterHash = {};
        },

        add_key : function(_key){
        // messages with matching metadata will be displayed
            this.filterHash[_key] = true;
        },

        filter_only : function(_key){
            this.clear();
            this.add_key(_key);
            this.on();
        },

        test : function(_key){
            return(this.filterHash[_key]);
        },
        render : function(_$object){
            if(this.active && ((this.test(_$object.attr(this.TEST_ATTRIBUTE)) === true) === this.testFor)){
                _$object.addClass(this.APPLY_STYLE_CLASS);
            }
            return _$object;
        },

        enforce : function(){
            var i;
        // possible performance problems
            $("#" + this.CONTAINER_ID + " ." + this.TARGET_STYLE_CLASS).addClass(this.APPLY_STYLE_CLASS);
            //first hide everything...
            for(i in this.filterHash){
                    // For each attribute and value in add_key, remove the hidden class
                    $("[" + this.TEST_ATTRIBUTE + "='" + i + "']").removeClass(this.APPLY_STYLE_CLASS);
            }
        },

        unenforce : function(){
            $("#" + this.CONTAINER_ID + " ." + this.TARGET_STYLE_CLASS).removeClass(this.APPLY_STYLE_CLASS);
        }
    };
}

The usefulness of creating a class is that you can have private variables.

Simply placing every thing in an object defeats that point.  Instead you should define everything in the protected part of the function and simply expose an external API with the return.

http://codr.cc/s/9b31baa5/js