Ensuring Sequence of Events in an Array The Problem

I'm asking to see if there are methodically better solutions to this problem. The situation is as follows, I am receiving an array of events, they are marked by timestamp and there is a designated order of events. That is, that after every event of type a, there should always be a corresponding event b.

Due to how the server batches events, there is a chance that other event types with the same timestamp can corrupt this sequence. I would like to restore it.

The data structure is as follows,

[ { type: string, timestamp: number }, ]

As mentioned beforehand, I would like to ensure that every event of type 'a' is followed immediately by a type 'b' event.

const events = [
  { type: 'a', timestamp: 1 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'b', timestamp: 2 },
];

The target sequence would be as follows:

const sortedEvents = [
  { type: 'a', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'c', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'c', timestamp: 2 },
];

My Solution

My immediate approach to this is the following:

// Check if the next event for this item is of correct type
const nextIsCorrect = (arr, idx) => (arr[idx].type === 'a') && (arr[idx+1] && arr[idx+1].type === 'b');

// Build list of partnered events
const indices = events.reduce((prev, event, idx, arr) => {
  if (nextIsCorrect(arr, idx)) {
    return prev;
  }

  if (event.type === 'a') {
    prev.push([() => arr.indexOf(event)]);
  }

  if (event.type === 'b') {
    const precedingEvent = prev.find(el => {
      return (el[0] && !el[1]);
    });

    precedingEvent && precedingEvent.push(() => arr.indexOf(event));
  }

  return prev;
}, []);

// Rearrange
indices.forEach(set => {
  const from = set[1]();
  const target = set[0]() + 1;

  events.splice(target, 0, events.splice(from, 1)[0]);
});

I think this is an okay solution, but I can't help feel there is a much better approach eluding me.

Hard coding

Is too easy...

The first problem I see is that the sorting has the event type hard coded into the function.

I feel that hard coding any type of data into code is bad practice. At minimum if hard coding values is unavoidable the values should be defined as a constant and placed in a common location in the source file.

The problem with hard coding is the inevitable need to change or add to the hard coded items. This is a difficult process when the values are scattered in the code, and usually not easy to find as they are not unique.

For a simple fix I would add

const eventTypes = { a : "a", b : "b" };  // at the top of the source file
                               // or in a common file, and as close
                               // to the required scope as possible
                               // as to not be in global

Then in the code

if(event.type === eventTypes.a){  ...
if(event.type === eventTypes.b){  ...

Thus if you want to change you do so where you define the const and if you need to change the code you can us refactor tools to locate the unique types in your code base.

Using data given.

Better yet is to avoid the constants all together and use the data in the array items. You can compare strings with "stringA" < "stringB" is true. Javascript uses the strings char codes to evaluate the condition, that means that "stringa" < "stringB" is false as lowercase characters have a higher character code than capitals.

So assuming that event types are all lowercase you can sort the events with a standard sort function.

Thus the steps would be

Sort all events by time.
Reduce the events array to event type, adding an array of times to each type.
Sort the reduced events by type.
Empty events array and reconstruct events using the following method.
From the lowest time search the reduced array for matching times. Add to the events array matching time and associated type. Removing time from type if more than one time, and or remove type if only one time for type, until reduced array is empty.

Testing

The data set you have given, is very limited and thus the problem is a little ambiguous. To ensure that the function works you should provide data with at least every combination of possible data combinations (Not all combinations "abc" is the same as "gef" but different than "aac" and "abca" ) that will affect the ordered result.

Sometimes testing can not test all possible input possibilities as the number of tests is so large to be impractical. The best way to deal with such is to create randomised data and do a statistical test. You can not prove the function will not fail, you can prove it will.

in other words...

You can then say your function has only a small statistical chance of failure if you don't get a fail. If you get any fail then your function is known to fail and should be fixed.

I used a random test (as I am can't be bothered doing a complete test, and i Imagine it most matches the expected input) to test the function. Your function failed on the very first random test with a typeError (I did not examine the details)

The other answer given by GerritO also failed incorrectly ordering most test inputs.

An example of test data that fails

const events = [
  { type: 'a', timestamp: 1 },
  { type: 'a', timestamp: 4 },
  { type: 'a', timestamp: 3 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'b', timestamp: 2 },
];

//or
  [{ type: 'a', timestamp: 1 },
  { type: 'g', timestamp: 4 },
  { type: 'a', timestamp: 3 },
  { type: 'b', timestamp: 2 },]

A more robust function.

The rewrite has made a few assumptions, and has been tested on a huge set of random inputs without failing (no fail in over 10 million random input tests). That does not mean it does what you want, it does what I guessed you want. Order events by time, in same time groups, order events in alphabetical groups

Rather than modify the existing array I have created a new array to hold the results.

// test data example
const events = [
  { type: 'a', timestamp: 1 },
  { type: 'g', timestamp: 4 },
  { type: 'a', timestamp: 3 },
  { type: 'h', timestamp: 5 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'g', timestamp: 3 },
  { type: 'b', timestamp: 2 },
  { type: 'e', timestamp: 3 },
  { type: 'f', timestamp: 1 },
  { type: 'f', timestamp: 3 },
  { type: 'h', timestamp: 5 },
  { type: 'f', timestamp: 3 },
  { type: 'f', timestamp: 3 },
];

/* Please note this uses compact style. Single block statements are followed
   by `{ code }` when under 80 chars (tab 2). No `;` is added to comply with
   JSLint rule Semicoloans must be followed by newline. */

function reorderEvents(events){
    /* global to this function variables */
    // timeClear is flag to indicate that there are no events at the current event time
    // eventTime is the current event time to add to result
    var timeClear, eventTime, eIdx = 0; // index into ev arrray

    /* Functions global to this function */
    const typeSort = (a, b) => a.type < b.type ? -1 : a.type > b.type ? 1 : 0;
    const getEvent = () => {                        // gets event matching eventTime from reduced events
        if (ev[eIdx].times[0] === eventTime){       // does the event match the event time
            timeClear = false;                      // flag that it is unknown if there are more times at eventTime
            if (ev[eIdx].times.length === 1) {      // is this the only time for event
                const event = ev.splice(eIdx,1)[0]; // remove from array
                return { type : event.type, timestamp : event.times[0] }; // return the event
            }
            return { type : ev[eIdx].type, timestamp : ev[eIdx++].times.shift() }; // remove the time
        } else { eIdx ++ } // skip the event as not at the event time
    }

    const orderedEvents = [];   // Will hold the results and is returned by this function
    const reduced = new Map();  // holds events type as key and array of event times per key

    // We dont want to mess with the original array and as sorts are in place we need to copy the array
    events = [...events];
    events.sort((a,b) => a.timestamp - b.timestamp );  // Order events by time

    // reduce events to type
    events.forEach((event) => {
        const existing = reduced.get(event.type);
        if (existing === undefined) {
            reduced.set( event.type, { type : event.type, times : [event.timestamp] });
        } else { existing.times.push(event.timestamp) }
    });

    // get the reduced events from the Map and sort by type
    const ev = [...reduced.values()].sort(typeSort);
    timeClear = true;    // first pass the abstract previouse pass is clear

    // remove all events in order of time
    while (ev.length > 0) {
        if (eIdx === 0) { // if this the first item
            if (timeClear) { eventTime = ev[0].times[0] }  // get next time
            else { timeClear = true }  // clear flag and do another pass
        }
        const event = getEvent();
        if (event !== undefined) { orderedEvents.push(event) }
        eIdx = eIdx === ev.length ? 0 : eIdx ; // goto start when past end
    }
    return orderedEvents;
}
// To avoid console log function
function log(data) {
    const d = document.createElement("div");
    d.textContent = data.toString();
    document.body.appendChild(d);
}
const ordered = reorderEvents(events);
ordered.forEach(i => log(i.type + " : " + i.timestamp));


Calculating Euclidean distance and performing unit-testing The method creates a link, an edge between two nodes, and calculates the Euclidean distance.

I'm testing that after linking, the link does indeed exist, and that the distance is correct.

I've used a variety of test cases, to check that it works for both horizontal and vertical links (just incase there's a divide by zero error), and as well as forward and backwards to check that it doesn't return a negative value.

import unittest
from graph import SpatialGraph

class TestSpatialGraph(unittest.TestCase):
    #cleardown any existing graph.
    def setUp(self):
        print "TestSpatialGraph Setup"

        g = None

    def testCreateLink_00_01(self):
        g = SpatialGraph(2,2)
        g.addNode(0, 0,0)
        g.addNode(1,0,1)
        g.createLink(0,1)

        self.assertTrue(g.link_matrix[0][1])
        self.assertTrue(g.link_matrix[1][0])

        self.assertEquals(g.distMatrix[0][1],1000)
        self.assertEquals(g.distMatrix[1][0],1000)

    def testCreateLink_00_11(self):
        g = SpatialGraph(2,2)
        g.addNode(0, 0,0)
        g.addNode(1,1,1)
        g.createLink(0,1)

        self.assertTrue(g.link_matrix[0][1])
        self.assertTrue(g.link_matrix[1][0])

        self.assertEquals(g.distMatrix[0][1],1414)
        self.assertEquals(g.distMatrix[1][0],1414)

    def testCreateLink_00_10(self):
        g = SpatialGraph(2,2)
        g.addNode(0, 0,0)
        g.addNode(1,1,0)
        g.createLink(0,1)

        self.assertTrue(g.link_matrix[0][1])
        self.assertTrue(g.link_matrix[1][0])

        self.assertEquals(g.distMatrix[0][1],1000)
        self.assertEquals(g.distMatrix[1][0],1000)

    def testCreateLink_10_00(self):
        g = SpatialGraph(2,2)
        g.addNode(0, 1,0)
        g.addNode(1,0,0)
        g.createLink(0,1)

        self.assertTrue(g.link_matrix[0][1])
        self.assertTrue(g.link_matrix[1][0])

        self.assertEquals(g.distMatrix[0][1],1000)
        self.assertEquals(g.distMatrix[1][0],1000)

    def testCreateLink_11_00(self):
        g = SpatialGraph(2,2)
        g.addNode(0, 1,1)
        g.addNode(1,0,0)
        g.createLink(0,1)

        self.assertTrue(g.link_matrix[0][1])
        self.assertTrue(g.link_matrix[1][0])

        self.assertEquals(g.distMatrix[0][1],1414)
        self.assertEquals(g.distMatrix[1][0],1414)

    def testCreateLink_01_00(self):
        g = SpatialGraph(2,2)
        g.addNode(0, 0,1)
        g.addNode(1,0,0)
        g.createLink(0,1)

        self.assertTrue(g.link_matrix[0][1])
        self.assertTrue(g.link_matrix[1][0])

        self.assertEquals(g.distMatrix[0][1],1000)
        self.assertEquals(g.distMatrix[1][0],1000)

Here's some questions I have:

Obviously the code is repetitive. But I'm told that for unit tests, you shouldn't genericise, and instead should repeat yourself. (But what if I change one of the methods use? Won't going through each of the tests and refactoring be a pain?).
It assumes that addNode is working correctly. But is this how unit tests work? I then also have tests to check that addNode is working correctly, and then assume after that that everywhere else it is indeed working correctly.
I'm not testing for more distances. This was perhaps laziness on my part. I check just the one diagonal, and it's indeed calculating that distance correctly.
What else am I meant to have in a setUp method?
Each test is in its own method. Should they perhaps be all just one test?

Since the tests are testing the same thing (calculate the distance between two nodes) and the only difference is the test data, I say refactor it so that you have one test that tests the same logic with different data. When you have tests that are there for different purposes (like validation checking, distance calculation, not calling createLink, etc) you will have code duplication.

There should be separate tests for addNode and separate tests for validation checks (what happens when you try to create a link when there are no nodes added). Also there should be different variations of the amount of nodes.

Setup is called before every testmethod, so if you always create the same SpatialGraph you can do that there.


Promisifying a third-party JS library with minimal code overhead Context and Existing Code

I am trying to "promisify" a third-party authentication library (auth0-js) written in JavaScript. Right now it uses callback functions and there are no plans to expose an async/await friendly API. So, I'm writing a wrapper, to avoid callback hell in my own code.

Here's a callback factory function cb which is actively used for creating Promises.

import * as a0 from "auth0-js";

export function cb<TResult>(
  resolve: (reason: TResult) => void,
  reject: (reason: a0.Auth0Error) => void,
): a0.Auth0Callback<TResult> {
  return (error, result) => error ? reject(error) : resolve(result);
}

And here's an example of a wrapper class.

import * as a0 from "auth0-js";
import { cb } from "./cb";

export class Authentication {

  /**
   * Wraps the Auth0-js' `Authentication` object and exposes Promise-based methods.
   * @param wa Wrapped `Authentication` object.
   */
  constructor(private wa: a0.Authentication) { }

  public get dbConnection(): DbConnection {
    return new DBConnection(this.wa.dbConnection);
  }

  public buildAuthorizeUrl(options: any): string {
    return this.wa.buildAuthorizeUrl(options);
  }

  public loginWithDefaultDirectory(options: a0.DefaultDirectoryLoginOptions): Promise<any> {
    return new Promise((resolve, reject) => this.wa.loginWithDefaultDirectory(options, cb(resolve, reject)));
  }

  public login(options: a0.DefaultLoginOptions): Promise<any> {
    return new Promise((resolve, reject) => this.wa.login(options, cb(resolve, reject)));
  }

  public oauthToken(options: any): Promise<any> {
    return new Promise((resolve, reject) => this.wa.oauthToken(options, cb(resolve, reject)));
  }

  public loginWithResourceOwner(options: a0.ResourceOwnerLoginOptions): Promise<any> {
    return new Promise((resolve, reject) => this.wa.loginWithResourceOwner(options, cb(resolve, reject)));
  }

  public getSSOData(withActiveDirectories: boolean, options: a0.DelegationOptions): Promise<any> {
    return new Promise((resolve, reject) => this.wa.getSSOData(withActiveDirectories, cb(resolve, reject)));
  }

  public userInfo(accessToken: string): Promise<a0.Auth0UserProfile> {
    return new Promise((resolve, reject) => this.wa.userInfo(accessToken, cb(resolve, reject)));
  }

  public delegation(options: a0.DelegationOptions): Promise<a0.Auth0DelegationToken> {
    return new Promise((resolve, reject) => this.wa.delegation(options, cb(resolve, reject)));
  }

  public getUserCountry(): Promise<{ countryCode: string; }> {
    return new Promise((resolve, reject) => this.wa.getUserCountry(cb<{ countryCode: string; }>(resolve, reject)));
  }
}

Question

While I'm always open to any constructive feedback, there are a few specific aspects I'll be particularly thankful for.

I'm a C# developer and still know too little about JavaScript/TypeScript. If you know how to make this code look more JS-idiomatic, I'm all ears. Or I can paraphrase the question as "am I going the right/common route?"
You can see that there is a lot of structural repetition in the code that creates Promises from callbacks (e.g. loginWithDefaultDirectory(...), login(...), oauthToken(...) functions). Not nice. Is there a way to apply functional programming ideas here? I have a feeling that functional composition may get handy here, but I don't know how to apply it (a sign, I haven't grasp the concept yet)
Resolved It's also easy to notice that buildAuthorizeUrl(...) is a pass-through. No callbacks here. There must be an easier way to bind one object's function to another object's function, which I don't know how to do. Very similarly, get dbConnection() accessor is a supposed to be a pass-through.

Update 1

I figured the pass-through members can be coded very easily (one line per member):

 public buildAuthorizeUrl = this.wa.buildAuthorizeUrl;

So, point 3 is now out of question.

You are correct that you can avoid a lot of the structure duplication in this class. A promisify function would help a lot. Node has a built in util.promisify. Alternatively, you could write a simple method to apply the arguments and resolve when called. In vanilla JS this is simple enough.

function callPromised(method, ...args) {
    return new Promise((resolve, reject) => {
        method(...args, (error, result) => error ? reject(error) : resolve(result))
    })
}

Unfortunately, this method is difficult to type correctly in TypeScript. There's a proposal here. The best we can do now is write several overloads which gets incredibly messy with only a few parameters.

function callPromised<TResult>(method: (cb: Auth0Callback<TResult>) => void): Promise<TResult>;
function callPromised<TResult, Arg1>(method: (arg1: Arg1, cb: Auth0Callback<TResult>) => void, arg1: Arg1): Promise<TResult>;
function callPromised<TResult, Arg1, Arg2>(method: (arg1: Arg1, arg2: Arg2, cb: Auth0Callback<TResult>) => void, arg1: Arg1, arg2: Arg2): Promise<TResult>;
function callPromised(method: Function, ...args: any[]): Promise<any> {
    return new Promise((resolve, reject) => {
        method(...args, (error, result) => error ? reject(error) : resolve(result))
    })
}

The downside of this function is that this will not be bound correctly. This could be rectified by passing in a self parameter and would be required for your usage.

function callPromised<TResult>(method: (cb: Auth0Callback<TResult>) => void, self: any): Promise<TResult>;
function callPromised<TResult, Arg1>(method: (arg1: Arg1, cb: Auth0Callback<TResult>) => void, self: any, arg1: Arg1): Promise<TResult>;
function callPromised<TResult, Arg1, Arg2>(method: (arg1: Arg1, arg2: Arg2, cb: Auth0Callback<TResult>) => void, self: any, arg1: Arg1, arg2: Arg2): Promise<TResult>;
function callPromised(method: Function, self: any, ...args: any[]): Promise<any> {
    return new Promise((resolve, reject) => {
        method.call(self, ...args, (error, result) => error ? reject(error) : resolve(result))
    })
}

// For example
public loginWithDefaultDirectory(options: a0.DefaultDirectoryLoginOptions): Promise<any> {
    return callPromised(this.wa.loginWithDefaultDirectory, this.wa, options)
}


Sort a linkedlist with 3 elements 0, 1 and 2 Given a linked list of 0s, 1s and 2s, sort it. Looking for code review, optimizations and best practices

public final class SortZeroesOnesTwos {

    private Node first;
    private Node last;
    private int size;

    public SortZeroesOnesTwos(List<Integer> items) {
        for (Integer item : items) {
            add(item);
        }
    }
    public void add(Integer item) {
        Node node = new Node(item);
        Node l = last;
        last = node;
        if (first == null) {
            first = node;
        } else {
            l.next = node;
        }
        size++;
    }

    private static class Node {
        private int item;
        private Node next;

        public Node(int item) {
            this.item = item;
        }
    }

    public void sortZeroesOnesAndTwos() {
        int[] a = new int[3];

        Node node = first;
        while (node != null) {
            a[node.item] = a[node.item] + 1;
            node = node.next;
        }

        node = first;
        int i = 0;
        while (node != null) {
            if (a[i] == 0) {
                i++;
            } else {
                node.item = i;
                node = node.next;
                a[i] = a[i] - 1;
            }
        }
    }

    public int[] toArray() {
        int[] result = new int[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
 }

public class SortZerosOnesTwosTest {

    @Test
    public void test1() {
        SortZeroesOnesTwos sortList = new SortZeroesOnesTwos(Arrays.asList(0, 1, 2, 1, 2, 0));
        sortList.sortZeroesOnesAndTwos();
        int[] expected = {0, 0, 1, 1, 2, 2};
        assertTrue(Arrays.equals(expected, sortList.toArray()));
    }

    @Test
    public void test2() {
        SortZeroesOnesTwos sortList2 = new SortZeroesOnesTwos(Arrays.asList(1, 2, 1, 2));
        sortList2.sortZeroesOnesAndTwos();
        int[] expected2 = {1, 1, 2, 2};
        assertTrue(Arrays.equals(expected2, sortList2.toArray()));
    }

    @Test
    public void test3() {
        SortZeroesOnesTwos sortList3 = new SortZeroesOnesTwos(Arrays.asList(0, 2, 0, 2));
        sortList3.sortZeroesOnesAndTwos();
        int[] expected3 = {0, 0, 2, 2};
        assertTrue(Arrays.equals(expected3, sortList3.toArray()));
    }

    @Test
    public void test4() {
        SortZeroesOnesTwos sortList4 = new SortZeroesOnesTwos(Arrays.asList(0, 1, 0, 1));
        sortList4.sortZeroesOnesAndTwos();
        int[] expected4 = {0, 0, 1, 1};
        assertTrue(Arrays.equals(expected4, sortList4.toArray()));
    }
}

The mash-up you continue to have with Objects and primitives is something that is easy to resolve, yet you don't. Is there some reason I am missing why it is important to convert your data to an Integer Object before converting it back to an int?

public void add(Integer item) {

Why can't that be:

public void add(int value) {

???? Your Node class stores it as an int, so there is no reason to do the multiple conversions.

The algorithm you have used for the 'sorting' is similar to what I would do. There are a few nitpicks though (one of them is not so small....):

Use Post-increment and Post-Decrement operators:

a[node.item] = a[node.item] + 1;

and

a[i] = a[i] - 1;

should be:

a[node.item]++;

and

a[i]--;

Why use a linked list at all? Seriously, what does the Node concept buy you? This problem could easily be solved with a primitive array (... or an ArrayList, or LinkedList if you were not using primitives .....). If your data was stored as an array, it would be as simple as:

public void sortZeroesOnesAndTwos() {
    int[] itemcount = new int[3];

    for (int item : data) {
        itemcount[item]++;
    }

    int pos = 0;
    for (int item = 0; item < a.length; item++) {
        while (itemcount[item]-- > 0) {
            data[pos++] = item;
        }
    }
}


Java implementation of the Factory Method pattern I am working on a very simple game and thought it would be a good opportunity to learn and use the Factory Method pattern for creating game objects. I studied the pattern but I'm a bit confused about the Java implementation so thought I would share what I have come up with and get some opinions.

Please keep in mind that I am basing this design on the example from "Design Patterns... by the GOF" so we will use the following pieces: Product, ConcreteProduct, Creator, and ConcreteCreator.

Product (Interface for Game Objects)

public interface GameObject {
   public abstract void doSomeStuff();
}

ConcreteProducts (Implements Product Interface, 1 for each Game Object)

public class PlayerImpl implements GameObject {
    @Override
    public void doSomeStuff() {
        System.out.println("I am a player object!");
    }
}

public class EnemyImpl implements GameObject {
    @Override
    public void doSomeStuff() {
        System.out.println("I am an Enemy, you better run!");
    }
}

Creator (Interface that defines how to create objects)

This is the one I'm most confused about, seems un-necessary unless instead of an Interface it was some Abstract class, but even then seems kind of pointless to use a Creator in this design pattern?

 public interface GameObjectFactory {
    public abstract GameObject createGameObject(GameObjectFactoryImpl.Type type);
}

ConcreteCreator (Implements Creator, creates objects)

The ConcreteCreator will have a nested enumeration to help the client decide which player types are available. We will throw an exception if for some reason there is a game object type in the enumeration that is not handled in the factory method.

public class GameObjectFactoryImpl implements GameObjectFactory{

    // A helper enum that clients will use to create game objects
    public enum Type {
        PLAYER, ENEMY;
    }

    public GameObject createGameObject(GameObjectFactoryImpl.Type type) {

        switch (type) {
        case PLAYER:
            return new PlayerImpl();
        case ENEMY:
            return new EnemyImpl();
        default:
            throw new RuntimeException("Unsupported object type!");
        }

    }
}

Client

public class Game {

    private static GameObjectFactory gameObjectFactory = new GameObjectFactoryImpl();

    public static void main(String args[]){

        GameObject player = gameObjectFactory.createGameObject(GameObjectFactoryImpl.Type.PLAYER);
        GameObject enemy = gameObjectFactory.createGameObject(GameObjectFactoryImpl.Type.ENEMY);

        player.doSomeStuff();
        enemy.doSomeStuff();
    }

}

This pattern can be difficult to understand outside of an application with many modes of operation. There are two advantages to using the factory patterns: you can swap in different implementations, and you can vary the construction parameters without changing client code.

Where do these advantages shine? Testing! In the case of a game, randomness is a good example. When playing the game for real, you want your monsters to vary their behavior randomly. But when testing, you need to be able to choose from their possible behaviors. The real factory will initialize each monster with a real random number generator, but tests must be able to specify the behavior choices.

Take this example monster action:

public void chooseCombatAction() {
    if (isAfraid()) {
        return Action.RUN;
    }
    else {
        return Action.ATTACK;
    }
}

private boolean isAfraid() {
    return random.nextInt(10) > 7;
}

To test chooseCombatAction, you need to provide a mock random number generator. But if the constructor creates it, you can't. Instead, have the factory provide it, and create an implementation that takes one with pre-configured values. Now you can give that factory to the root game object that uses the factory to create monsters.

  Style Note: Drop implied modifiers--such as public and abstract on interface members--wherever possible. Every modifier adds context that must be groked.


Producing recursive directory listings This produces recursive directory listings(it's intended to do other things, so there will be something else instead of echo, but it isn't important), yet it isn't very intuitive. How can I improve it?

#! /bin/bash
deploy ()
{
    for file in $(ls $1); do
        if [ ! -d "$2$file" ]; then
            echo ${2}${file}
        else
            deploy $2$file "$2$file/"
        fi
    done;
}

deploy .

Output example:

tmp/kdecache-z/http/ba9c27404980248a61dcdadd35f5f52395b8bdde
tmp/kdecache-z/http/scoreboard
tmp/kdecache-z/icon-cache.kcache
tmp/kdecache-z/ksycoca4
tmp/kdecache-z/ksycoca4stamp
tmp/kdecache-z/plasma-svgelements-.customized1
tmp/kdecache-z/plasma-svgelements-internal-system-colors
tmp/kdecache-z/plasma_theme_.customized1.kcache
tmp/kdecache-z/plasma_theme_internal-system-colors.kcache
tmp/kdecache-z/Активные
tmp/kdecache-z/напоминанияrc
tmp/kdecache-z/Устаревшие
tmp/kdecache-z/напоминанияrc
tmp/kdecache-z/Шаблоны
tmp/kdecache-z/напоминанийrc
tmp/kde-z/xauth-1000-_0
tmp/ksocket-z/kdeinit4__0
tmp/ksocket-z/kio_http_cache_cleaner
tmp/ksocket-z/klauncherhX2255.slave-socket
tmp/ksocket-z/KSMserver__0
tmp/pulse-PKdhtXMmr18n/native
tmp/pulse-PKdhtXMmr18n/pid
tmp/qtsingleapp-homezS-8560-3e8
tmp/qtsingleapp-homezS-8560-3e8-lockfile
tmp/skype-2664/DbTemp./temp-KXp68f252Xx0kBMtqNdj7NFo
tmp/skype-2664/DbTemp./temp-NAailvY24hLGYNrZiJ99QIgH
tmp/sni-qt_skype_2664-v6Xyna/icons/hicolor/24x24/apps/skype_2664_2d1ee5482260fd9cd180b32787792683.png
tmp/sni-qt_skype_2664-v6Xyna/icons/hicolor/24x24/apps/skype_2664_37e170fc54e7355d9d298917e74f9ea9.png
tmp/sni-qt_skype_2664-v6Xyna/icons/hicolor/24x24/apps/skype_2664_602c84fa0f4d61c64f770495a500279e.png
tmp/sni-qt_skype_2664-v6Xyna/icons/hicolor/24x24/apps/skype_2664_f2fc4a539a7b9553f5b35241d1154e84.png
tmp/z.socket

P.S. It is working perfectly for me so I just want to make it more beautiful.

In fairness, this task is relatively simple, and your solution is actually pretty good.

Shell scripts are often just a hack to solve a specific task, and, your script is much better than many that I see that do that.

There are two things to consider in your script. The first is whether it can be improved. The second is whether there's a better way.

Now, about improving it. I would:

remove the need for the second parameter
name the parameters,
include the / in a different place
use quotes around variables in specific places.
reverse the if-blocks to get rid of the 'negate' condition.

Consider the following:

deploy () {
    local dir="$1"
    for file in $(ls "$dir/" ); do
        # Fully qualified file
        fqfile="$dir/$file"
        if [ -d "$fqfile" ]; then
            deploy "$fqfile"
        else
            echo "$fqfile"
        fi
    done;
}

Introducing the fqfile allows the simplifcation of other variables too.

Now, having said all that, your command could easily be solved with the find command:

find . -type f -exec echo {} \;

The above command will recursively find all files below ., and echo them.


IMapDocument in a 10.1 SOE I am wondering if this code will work in 10.1.

This video at 1:02 says not to create mxd based services. I think that just means not using IMapServerObjects3, but seems like IMapDocument should be OK.

#region IServerObjectExtension Members

private IPageLayout m_Layout = null;
public void Init(IServerObjectHelper pSOH)
{
    serverObjectHelper = pSOH;
    // open an mxd and grab the layout
    IMapDocument mapDoc = new MapDocumentClass();
    mapDoc.Open(@"\\sharedFolder\Mymapdocument.mxd");
    m_Layout = mapDoc.PageLayout;
    mapDoc.Close();
}

public void Shutdown()
{
    System.Runtime.InteropServices.Marshal.FinalReleaseComObject(m_Layout);
}

#endregion

Edit: Here's a related question on GIS.stackexchange.

The reason why the video states that you should not create SOEs on top of MXD based map services is because in 10.1 you will not be able to start a service from an mxd. You will need to convert your map document into a service definition.

One of the issues you will find with MXD-based SOEs in 10 when you upgrade to 10.1, is that your code most likely will be accessing layers or layouts in the map service. This is pretty common in MXD-based SOEs because it is through layers that you get to the datasets you want to use in your code etc.  At 10.1, your SOE code will break, because layers, layouts etc are only available in MXD-based SOE map services. If you create an MSD-based map service and build an SOE on top of it, you will notice the same. With MSD-based SOEs you need to use IMapServerDataAccess to get to the data sources in your map.  And that code will just work in 10.1. So writting SOE's on top of MSD is a good way to understand what will be possible in 10.1

I suggest you look at this and this.

As for using IMapDocument... go for it. It will work fine in 10.1


Fahrenheit / Celsius temperature converter - follow-up This is an updated version of the script Fahrenheit / Celsius temperature converter. I have changed the script to be non-interactive, using positional parameters instead of asking for user input once the script is running. In my testing of the script, everything seems to work as it should. But I am quite new to using positional parameters and I'm wondering if this is the best way of using them or if there might be a more streamlined approach.

help shift says:

shift: shift [n]
    Shift positional parameters.

    Rename the positional parameters $N+1,$N+2 ... to $1,$2 ...  If N is
    not given, it is assumed to be 1.

    Exit Status:
    Returns success unless N is negative or greater than $#.

Which leaves me still uncertain as to what that means exactly or how to implement it correctly. The script seems to work but I'd like to know if I could / should do anything differently.

#!/bin/bash

usage() {
    echo -e "usage: temp [-f][-c]|[number]|[-h]\nExample:\n\ttemp -f 54\n\ttemp -c 24.5\n"
}
re='^-?[0-9]+([.][0-9]+)?$'
if [ "$1" = "" ]; then
    usage
    exit 1
elif [[ ! "$2" =~ $re ]]; then
    usage
    exit 1
elif [[ "$3" != "" ]]; then
    usage
    exit 1
fi
while [ "$1" != "" ]; do
    case $1 in
        -f )    shift
                RES="$(echo "scale=2; (${1}-32)*5/9" | bc -q -l; printf "\b˚C")"
                echo "${1}˚F = "${RES}
                exit
                ;;

        -c )    shift
                RES="$(echo "scale=2; ${1}*9/5+32" | bc -q -l; printf "\b˚F")"
                echo "${1}˚C = "${RES}
                exit
                ;;

        -h )    usage
                exit
                ;;

        * )     usage
                exit 1
    esac
done

shift shifts the command line argument list by n, or by 1 if n is unspecified.
For example, given -c 25, the value of $1 is -c.
After you call shift without parameters,
it shifts the parameters by 1, so $1 becomes 25.
You used it correctly.

Use here-documents

This is hard to read:

echo -e "usage: temp [-f][-c]|[number]|[-h]\nExample:\n\ttemp -f 54\n\ttemp -c 24.5\n"

Using a here-document, it becomes much easier to read:

usage() {
    cat << EOF
usage: temp [-f][-c]|[number]|[-h]
Example:
    temp -f 54
    temp -c 24.5
EOF
}

Simplify conditions

This can be written slightly simpler:

if [ "$1" = "" ]; then

Like this:

if [ ! "$1" ]; then

This can be written much simpler:

elif [[ "$3" != "" ]]; then
    usage
    exit 1
fi
while [ "$1" != "" ]; do

Like this:

elif [[ "$3" ]]; then
    usage
    exit 1
fi
while [ "$1" ]; do

Simplify the bc calls

These statements are unnecessarily complicated:

-f )    shift
        RES="$(echo "scale=2; (${1}-32)*5/9" | bc -q -l; printf "\b˚C")"
        echo "${1}˚F = "${RES}
        exit
        ;;

-c )    shift
        RES="$(echo "scale=2; ${1}*9/5+32" | bc -q -l; printf "\b˚F")"
        echo "${1}˚C = "${RES}
        exit
        ;;

That is:

Doing part of the output formatting when you create RES and the other part when you echo it is confusing, it would be better to separate
Printing a backspace character becomes unnecessary when you separate the calculation and display formatting of RES
The quoting around $(...) is unnecessary
Instead of echo-ing the command for bc, a here-string would be better

Like this:

RES=$(bc -q <<< "scale=2; ${1}*9/5+32")
echo "${1}˚C = ${RES}˚F"

Notice how the assignment of RES has only calculation logic, no display logic. All the display logic is on the next line.
The result is cleaner and shorter.


Counting single degree vertex removal rounds (from a graph) Problem:
In this problem I had to remove all vertices with degree one from a given graph in rounds and count how many rounds are required to remove all possible vertices with degree 1.
e.g. 1-2-3-4 Remove 1 and 4 in round 1. Remove 2 and 3 in round 2.
e.g. we can't Remove any vertex here. Total 0 rounds.
1---2
 \ /
  3

So here is how I solve:

Logic:

Create an adjaceny list adj.
Create a degree sets dl with dl[i] containing all vertices with degree i.
Remove all vertices of degree one and remove their adjacency list. I do not update the degree or adjacency list of it's neighbors upon removal but only after the round has completed. For this I use a map/dictionary dec such that dec[x][0] are the neighbors of the single degree vertex x whose adjacency list and degree needs to be updated while dec[x][1] is the amount of degree reduction.
If we have non-zero single degree vertices then I first pop() them and update values of their dec value.
Finally for each vertex who needs to be updated, I move it from one degree set to another and update it's adjacency list.
Finally I increase round count and then I print it.

Note: Sometimes the single degree vertices may appear in pair like 1-2 then while pop(ping) it has already been removed so no need to update in last.

Code:
Please see Codeforces 192B for input description which is basically n(number of nodes), m(number of edges) and next m lines the edges.
from collections import defaultdict

n, m = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(m)]
adj = defaultdict(set)
for e in E:
    adj[e[0]].add(e[1])
    adj[e[1]].add(e[0])
dl = defaultdict(set)
for v in adj:
    dl[len(adj[v])].add(v)
if len(dl[1]) == 0:
    print('0')
else:
    cnt = 0
    while len(dl[1]) > 0:
        dec = defaultdict(lambda: [list(), 0])
        while len(dl[1]) > 0:
            v = dl[1].pop()
            for v2 in adj[v]:
                dec[v2][0].append(v)
                dec[v2][1] += 1
            del adj[v]
        for v2 in dec:
            if v2 in dl[len(adj[v2])]:
                dl[len(adj[v2])].remove(v2)
                dl[len(adj[v2]) - dec[v2][1]].add(v2)
                for x in dec[v2][0]:
                    adj[v2].remove(x)
        cnt += 1
    print(cnt)

Questions:

I have switched from a different language so my methods may not be very 'Pythonic' or exploiting advantages of 'Python' over others. Can you help?
Other improvements, if any?

Naming

Explicit names can go a long way in conveying what a piece of code does. Combine that with unpacking and explicit assignments to name parts of sequences, you can get:

from collections import defaultdict

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
adjacents = defaultdict(set)
for node1, node2 in edges:
    adjacent[node1].add(node2)
    adjacent[node2].add(node1)

degrees = defaultdict(set)
for node, neighbours in adjacents.items():
    degrees[len(neighbours].add(node)

if len(degrees[1]) == 0:
    print('0')
else:
    count = 0
    while len(degrees[1]) > 0:
        dec = defaultdict(lambda: [list(), 0])  # Can't figure out a good name for that
        singles = degrees[1]
        while len(singles) > 0:
            single = singles.pop()
            for node in adjacent[single]:
                dec[node][0].append(single)
                dec[node][1] += 1
            del adjacent[single]
        for node, (neighbours, count_neighbours) in dec.items():
            node_degree = len(adjacent[node])
            if node in degrees[node_degree]:
                degrees[node_degree].remove(node)
                degrees[node_degree - count_neighbours].add(node)
                for neighbour in neighbours:
                    adjacent[node].remove(neighbour)
        count += 1
    print(count)

Quick simplifications

We can see from there that some parts are unnecessary complicated: for node in adjacent(single) does not need to be a loop as there must be only one node adjacent to a node with degree 1. You can use unpacking to exctract this value; it will also let you ensure that there was actually only one value there:

while len(singles) > 0:
    single = singles.pop()
    neighbour, = adjacent[single]  # Do not forget the comma here
    del adjacent[single]
    dec[neighbour][0].append(single)
    dec[neighbour][1] += 1

You also have if len(degrees[1]) == 0: ... else: while len(degrees[1]) > 0 which are pretty much the same thing. You can remove the if, if there is no node of degree 1, then the while won't execute and count will still be 0.

Pythonic constructs

Every containers (lists, dicts, strings, sets, …) are considered False in a boolean context if they are empty and True otherwise. Which mean you should write while degrees[1]: or if not degrees[1].

You may also have noticed the use of dict.items() to iterate over both the keys and the values of a dictionnary at the same time. It is more efficient than using the key to retrieve the values latter.

You also don't really need to build a list of edges before building the dictionnary of adjacent nodes:

from collections import defaultdict

_, m = map(int, input().split())

adjacents = defaultdict(set)
for _ in range(m):
    node1, node2 = map(int, input().split())
    adjacent[node1].add(node2)
    adjacent[node2].add(node1)

degrees = defaultdict(set)
for node, neighbours in adjacents.items():
    degrees[len(neighbours].add(node)

count = 0
while degrees[1]:
    dec = defaultdict(lambda: [list(), 0])  # Can't figure out a good name for that
    singles = degrees[1]
    while singles:
        single = singles.pop()
        for node in adjacent[single]:
            dec[node][0].append(single)
            dec[node][1] += 1
        del adjacent[single]
    for node, (neighbours, count_neighbours) in dec.items():
        node_degree = len(adjacent[node])
        if node in degrees[node_degree]:
            degrees[node_degree].remove(node)
            degrees[node_degree - count_neighbours].add(node)
            for neighbour in neighbours:
                adjacent[node].remove(neighbour)
    count += 1

print(count)

Adding and removing nodes

You spend quite a lot of time moving nodes around in various lists and dictionaries. You could simplify the whole thing by using a more straightforward approach:

you only need to keep track of the nodes with degree 1
for each of these nodes:

remove it from its neighbour list of neighbours
if this neighbour now has degree 1, keep track of if in a temporary set

when done, iterate with the new set of nodes with degree 1.

from collections import defaultdict

_, m = map(int, input().split())

adjacents = defaultdict(set)
for _ in range(m):
    node1, node2 = map(int, input().split())
    adjacent[node1].add(node2)
    adjacent[node2].add(node1)

singles = {node for node, neighbours in adjacents.items() if len(neighbours) == 1}
count = 0
while singles:
    new_singles = set()
    for single in singles:
        neighbour, = adjacents[single]
        adjacents[neighbour].remove(single)
        if len(adjacents[neighbour]) == 1:
            new_singles.add(neighbour)
        # del adjacents[single] if you whish but it has no added value here
    singles = new_singles
    count += 1

print(count)

Functions

Using can help make things faster as Python resolves local symbols faster than global ones. But mainly recommended to organise the flow of things better and reuse parts of code.

You should also wrap the top-level code that you don't want to put in a function under an if __name__ == '__main__' clause:

from collections import defaultdict

def remove_singles(adjacents):
    singles = {node for node, neighbours in adjacents.items()
               if len(neighbours) == 1}

    passes = 0
    while singles:
        new_singles = set()
        for single in singles:
            neighbour, = adjacents[single]
            adjacents[neighbour].remove(single)
            if len(adjacents[neighbour]) == 1:
                new_singles.add(neighbour)

        singles = new_singles
        passes += 1

    return passes

if __name__ == '__main__':
    _, m = map(int, input().split())

    graph = defaultdict(set)
    for _ in range(m):
        node1, node2 = map(int, input().split())
        graph[node1].add(node2)
        graph[node2].add(node1)

    print(remove_singles(graph))


Speed up highscore rank calculation I calculate a highscore and find the users current rank like shown here. This is the query:

SELECT * FROM (SELECT  q.*, @r := @r + 1 AS rank
FROM ( SELECT  @r := 0 ) vars,
(
    SELECT  p.*, MAX(punkte) AS max_points
    FROM olympia_punkte_alle p
    WHERE markt_id = 1
    GROUP BY fb_id
    ORDER BY max_points DESC
) q) AS q2 WHERE fb_id = '26950' ORDER BY max_points DESC LIMIT 1

Problem is that the table has many rows (~8,5 Mio) and so this query is very slow. I could cache the sub select but than the highscore is always kind of old.

Any thoughts on how to make this faster?

EXPLAIN:

id  select_type         table   type    possible_keys   key key_len ref rows    Extra
1   PRIMARY <derived2>  ALL     NULL    NULL    NULL    NULL    1352    Using where; Using filesort
2   DERIVED <derived3>  system  NULL    NULL    NULL    NULL    1
2   DERIVED <derived4>  ALL     NULL    NULL    NULL    NULL    1352
4   DERIVED             p       ref     markt_id 4              2055    Using where; Using temporary; Using filesort
3   DERIVED NULL        NULL    NULL    NULL    NULL    NULL    NULL    No tables used

What about this query:

SELECT COUNT(*) + 1 as user_rank
    FROM olympia_punkte_alle p
    WHERE markt_id = 1
    GROUP BY fb_id
    HAVING
        MAX(punkte) > (SELECT MAX(punkte)
            FROM olympia_punkte_alle
            WHERE markt_id = 1
            GROUP BY fb_id
            HAVING fb_id = 2950)

We are getting the count of users that have better score then users with id 2950.
The count of better users + 1 is rank of your user.


String reversing x times Inspired by CodeWars

  We have a string s

  Let's say you start with this: "String"
    The first thing you do is reverse it: "gnirtS"
    Then you will take the string from the 1st position and reverse it
    again: "gStrin"
    Then you will take the string from the 2nd position and reverse it
    again: "gSnirt"
    Then you will take the string from the 3rd position and reverse it
    again: "gSntri"

  Continue this pattern until you have done every single position, and
    then you will return the string you have created. For this particular
    string, you would return: "gSntir"

  The Task:
    In this kata, we also have a number x
    take the above reversal function, and apply it to the string x times.
    Return the result of the string after applying the reversal function to it x times.

  Note:
  String lengths may exceed 2 million and x may exceed a billion.
  Be ready to optimize.

My solution works but times out and I am having trouble optimizing much further. The code contains a lot of useful comments but here is a summary of what I have attempted to do.

Cycle Length Calculation
Because the above algorithm generates cycles, we can calculate a strings cycle length and perform x % cycleLength to determine exactly how many iterations we must perform to get our end result, instead of having to calculate all the duplicate cycles. More on cycle lengths can be found here and here.

This method is better than nothing but can still get quite demanding on high cycle lengths. Potentially there is a better way of calculating the cycle length without so many iterations?

public final class XIterations {
    public static String xReverse(String s, long x) {
        // Using the cycle length and modular arithmetic,
        // We can find the exact number of reverse operations we will need to perform.
        // This way we will only perform operations we need to complete.
        long iterationsRequired = x % calculateCycleLength(s.length());

        // TODO: There may exist an algorithm that allows a linear transformation given x
        while (iterationsRequired > 0) {
            s = reverse(s);
            iterationsRequired--;
        }

        return s;
    }

    // The xReverse algorithm produces cycles and therefore duplicates.
    // This helper method determines the length of the cycle using the number of characters a string contains.
    // More detail on the algorithm can be found at:
    // https://oeis.org/A003558
    // https://oeis.org/A216066
    // TODO: There may exist an algorithm that requires less iterations to find the cycle length
    private static int calculateCycleLength(int n) {
        // Cache these so we only calculate them once.
        final int a = 2 * n + 1;
        final int b = 2 * n;

        int cycleLength = 1;
        while (true) {
            double c = Math.pow(2, cycleLength);
            if (c % a == 1 || c % a == b) {
                return cycleLength;
            }
            cycleLength++;
        }
    }

    public static String reverse(String s) {
        StringBuilder sb = new StringBuilder();
        int front = 0;
        int back = s.length() - 1;
        // Does not account for odd length strings. Will not add the middle character.
        while (front < back) {
            sb.append(s.charAt(back--));
            sb.append(s.charAt(front++));
        }

        // Account for odd length strings. Add the middle character that was never added by loop.
        if (front == back) {
            sb.append(s.charAt(front));
        }
        return sb.toString();
    }
}

I am mostly interested in optimization tips but of course any feedback is welcome.

choice of language

Unfortunately Java is not the best choice for doing such tasks. Object creation, reference handling and alike simply takes time.

So to speed up we need to throw away some of the benefits provides by the JVMs standard lib and switch to procedural programming on arrays.

optimizations

The calculation of the cycle length is a clever trick. But there must be an algorithm without looping which would speed up this calculation too.

implementation

As mentioned a fast solution must avoid object creation at all and should work on an array of chars rather than on  Strings. It should basically look like this:

public final class XIterations {
    public static String xReverse(String input, long iterations) {
      long iterationsRequired =  iterations% calculateCycleLength(input.length());
      char[] chars = input.toCharArray();
      for(int i = 0 ; i < iterationsRequired ; i++)
        chars = reverse(chars);
      return new String(chars);
    }
}

In your code I cannot find how you handle the skipping of the start of the string. I would do this by using a recursive call like this:

private char[] reverse(char[] chars, int startIndex){
   if(chars.length == startIndex) {
        return chars;
   } else {
      // reverse chars in array starting at startIndex
      return reverse(chars, ++startIndex);
   }
}


Find number of horizontal brush strokes to paint a skyline Asked in interview today:

You want to paint a skyline on your wall using only horizontal brush strokes. You are given an array of numbers, each representing the size of the column/building in that position. E.g. [1,2,1] - you can use two (horizontal) brush strokes. The first will paint the entire first row, and the second will paint the middle of the 2nd column.

Write an efficient algorithm to do so.

Here's my solution - idea being you count each end of strokes, and wipe out a row (or go up a row) for every iteration:

def solution(A):
    strokes = 0
    copy = [a for a in A]
    while sum(copy) > 0:
        for i in range(len(copy)):
            if (copy[i] > 0) and ((i+1 == len(copy)) or (copy[i+1] == 0)):
                strokes += 1
            if copy[i] > 0:
                copy[i] -= 1
    return strokes

solution([1,0,5,8,0]) will output 9

With every height drop by 1 point, a line ends. So you just need to calculate the sum of height drops. Don't forget to account for the last height. You could also do the same thing from the other end (every height increase starts a line).

def skyline(heights):
  diffs = [e1 - e2 for e1, e2 in zip(heights, heights[1:])]
  return sum(diff for diff in diffs if diff > 0) + heights[-1]

Some remarks on your code:

copy = [a for a in A] can be rewritten as copy = A.copy()
some parentheses in (copy[i] > 0) and ((i+1 == len(copy)) or (copy[i+1] == 0)) can be omitted:

if copy[i] > 0 and (i+1 == len(copy) or copy[i+1] == 0):
you can use enumerate in the for loop:

for i, elem in enumerate(copy):
  if elem > 0 and (i+1 == len(copy) or copy[i+1] == 0):
    strokes += 1
  if elem > 0:
    copy[i] -= 1

the ifs can be merged:

for i, elem in enumerate(copy):
  if elem > 0:
    copy[i] -= 1
    if i+1 == len(copy) or copy[i+1] == 0:
      strokes += 1


C++ Queue Circular Array Implementation I'm trying to implement a queue data structure in C++ using a circular array.
Please give recommendations on how I can improve this code.
Also, is my array growth strategy good? I'm doubling the array when the buffer is full.
(Try to remain in C++ 11 because, well that's a restriction I have to follow atm).
Sorry for the lack of comments in advance LoL (this is a rushed implementation).
#include <iostream>
#include <utility>

template <typename T>
class Queue {
public:
    Queue() : data(nullptr), len(0), front(0), cap(0)
    {
    }

    ~Queue()
    {
        this->Clear();
    }

    Queue(const Queue& rhs) : Queue()
    {
        if (rhs.data) {
            this->data = new T[rhs.cap];
            this->cap = rhs.cap;
            this->len = rhs.len;
            this->front = rhs.front;

            for (size_t i = 0; i < len; ++i) {
                this->data[i] = rhs.data[i];
            }
        }
    }

    Queue(Queue&& rhs) : data(rhs.data), cap(rhs.cap), len(rhs.len), front(rhs.front)
    {
        rhs.data = nullptr;
    }

    Queue& operator=(Queue rhs)
    {
        swap(*this, rhs);
        return *this;
    }

    size_t GetLength() const { return len; }
    const T& GetFront() const { return data[front]; }

    void Enqueue(const T& val)
    {
        if (len == cap) {
            size_t oldCap = cap;

            if (cap == 0) cap = 1;
            cap *= 2;

            T* newBuff = new T[cap];

            for (size_t i = 0; i < len; ++i) {
                size_t idx = (front + i) % oldCap;
                newBuff[i] = data[idx];
            }

            front = 0;
            data = newBuff;
        }

        data[(front + len) % cap] = val;
        ++len;
    }

    T Dequeue()
    {
        T val = std::move(data[front]);

        front = (front + 1) % cap;
        --len;
        return val;
    }

    void Clear()
    {
        delete[] data;
        data = nullptr;
        this->cap = this->len = this->front = 0;
    }

    friend
    std::ostream& operator<< (std::ostream& out, const Queue& q)
    {
        out << "Queue{";
        for (size_t i = 0; i < q.len; ++i) {
            size_t idx = (q.front + i) % q.cap;
            out << q.data[idx];
            if (i < q.len - 1) out << ", ";
        }

        out << "}";

        return out;
    }

    friend
    void swap(Queue& lhs, Queue& rhs)
    {
        std::swap(lhs.data, rhs.data);
        std::swap(lhs.len, rhs.len);
        std::swap(lhs.cap, rhs.cap);
        std::swap(lhs.front, rhs.front);
    }

private:
    T* data;
    size_t len;
    size_t cap;
    size_t front;
};

int main()
{

    Queue < int > a;
    a.Enqueue( 5 ); // add 5
    a.Enqueue ( 6 ); // add 6
    std::cout << a; // prints Queue{5, 6}

    a.Clear(); // empties the Queue
    std::cout << a; // prints Queue{}
}
```

This is quite a decent implementation of a C++ container! Some minor improvements are possible though:
Prefer using default member initialization
Especially when you have multiple constructors, default member initialization saves typing and reduces the chance of accidentily not initializing a variable. So:
class Queue {
public:
    Queue() = default;

    Queue(const Queue &rhs)
    {
        ...
    }

    ...
private:
    T* data = nullptr; // or {} works as well
    size_t len = 0;
    size_t cap = 0;
    size_t front = 0;
};

Use bitwise AND instead of modulo operations
Calculating the modulus of an integer is very slow compared to doing a bitwise AND (tens of CPU cycles vs. a fraction of a cycle). Since your capacity is always a power of two, you can use bitwise AND, like so:
data[(front + len) & (cap - 1)] = val;

You can get rid of the - 1 if you really want, that means storing the capacity minus one in cap. This will speed up the common case where you don't need to reallocate a tiny bit.
Note that the compiler probably won't be able to optimize the modulo to a bitwise AND by itself, because cap is not a constant.
Consider following the naming conventions of the standard library
It would be nice if your container has the same interface as other STL containers. That makes it easier for a programmer to remember the names of the member functions, but also makes it more likely that your container can be used as a drop-in replacement for other STL containers, and that algorithms that work with a std::queue can also work with your container. So consider renaming these member functions:

GetLength() -> size()
GetFront() -> front()
Enqueue() -> push()
Dequeue() -> pop() (althought the STL's pop() doesn't return any value)
Clear() -> clear()

The reason the STL doesn't return a value for pop() is so that it doesn't require T to be movable, instead you use front() to read the value, then pop() to discard it.
Unnecessary use of this->
There are a few places where you use this-> where it isn't necessary. In the copy constructor it makes a bit of sense since this emphasizes the contrast with rhs., but in ~Queue() and Clear() you don't need it.


Parallel image segmentation Follow up question Image processing using Python OOP library
I want to use multiprocessing to analyze several images in parallel:
class SegmentationType(object):
    DISPLAY_NAME = "invalid"

    def __init__(self, filename, path):
        self.filename = filename
        self.path = path
        self.input_data = None
        self.output_data = None

    def read_image(self):
        self.input_data =  cv2.imread(self.path + self.filename)[1]

    def write_image(self):
        cv2.imwrite(self.path + self.filename.split('.')[0] + '_' + self.DISPLAY_NAME + '.png', self.output_data)

    def process(self):
        # override in derived classes to perform an actual segmentation
        pass

    def start_pipeline(self):
        self.read_image()
        self.process()
        self.write_image()

class HSV_Segmenter(SegmentationType):
    DISPLAY_NAME = 'HSV'

    def process(self):
        source = rgb_to_hsv(self.input_data)
        self.output_data = treshold_otsu(source)

class LabSegmenter(SegmentationType):
    DISPLAY_NAME = 'LAB'

    def process(self):
        source = rgb_to_lab(self.input_data)
        self.output_data = global_threshold(source)

segmenter_class = {
'hsv': HSV_Segmentation,
'lab': LAB_Segmenter
}.get(procedure)

if not segmenter_class:
    raise ArgumentError("Invalid segmentation method '{}'".format(procedure))

for img in images:
    os.chdir(img_dir)
    processor =  = segmenter_class(img, img_dir, procedure)
    processor.start_pipeline()

What I tried so far:
image_lst = os.listdir(my_image_path)

# We split the list into sublist with 5 elements because of 512 GB RAM limitation
if len(image_lst) > 4:
    nr_of_sublists = (int(len(image_lst)/2.5))
    image_sub_lst  =(np.array_split(image_lst, nr_of_sublists))
else:
    image_sub_lst = [image_lst]

# We do the analysis for each sublist
for sub_lst in image_sub_lst:
    print (sub_lst)
    pool = multiprocessing.Pool(8)

    # Call the processor
    processor =  = segmenter_class(img, img_dir, procedure)
    processor.start_pipeline()
    # How to call map???
    pool.map(?, sub_lst)
    pool.terminate()

A warning on version
Many of the following suggestions assume that you are using Python 3.
Bare inheritance
class SegmentationType(object):

can be
class SegmentationType:

Abstract statics
DISPLAY_NAME = "invalid"

should not really assign a value. Instead,
DISPLAY_NAME: str

Unpacking imread
The documentation is deeply unhelpful: it says that imread returns "retval". Given your usage it's obvious that reality is more complicated, because you're indexing into it. Try to unpack instead:
_, self.input_data = cv2.imread(self.path + self.filename)

Abstract methods
process should raise NotImplementedError in the base.
Factory
You have a factory dictionary that should be turned into a method, something like
def get_segmenter(name: str) -> Type[SegmentationType]:
    return {
        t.DISPLAY_NAME: t
        for t in (HSVSegmenter, LABSegmenter)
    }[name]

Outer parentheses
Neither of these:
nr_of_sublists = (int(len(image_lst)/2.5))
image_sub_lst  =(np.array_split(image_lst, nr_of_sublists))

needs outer parentheses.
Syntax
Surely this is a typo? This will not run:
processor =  = segmenter_class(img, img_dir, procedure)

nor will this:
pool.map(?, sub_lst)


Counting sort using STL I'm trying to learn to use the C++ Standard Library and some of the modern C++11 features. Can someone review my counting sort algorithm below and critique my style/algorithm/use of the STL? Thank you!

#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

const int kSize = 100000000;      // Size of container to sort
const int kRangeFrom = -1000000;  // first of range for random number generator
const int kRangeTo = 1000000;     // last of range for random number generator

// Linear time sorting algorithm for integers
template<typename InputIterator>
void counting_sort(InputIterator first, InputIterator last) {
  auto minmax_el = std::minmax_element(first, last);
  auto min = *minmax_el.first;
  auto max = *minmax_el.second;
  std::vector<std::size_t> counts(max - min + 1, 0);

  std::for_each(first, last, [&](auto x) {
    ++counts[x - min];  // Store value counts
  });

  for (auto it_c = counts.begin(); it_c != counts.end(); ++it_c) {
    auto idx = std::distance(counts.begin(), it_c);
    std::fill_n(first, *it_c, idx + min); // Store in sorted order
    std::advance(first, *it_c);
  }
}

int main() {
  std::random_device rd;
  std::mt19937 mt(rd());
  std::uniform_int_distribution<int> dist(kRangeFrom,kRangeTo);

  std::vector<int> v1(kSize);
  std::generate(v1.begin(), v1.end(), [&](){ return dist(mt); });

  std::vector<int> v2(kSize);
  std::copy(v1.begin(), v1.end(), v2.begin());

  auto first1 = std::chrono::steady_clock::now();
  counting_sort(v1.begin(), v1.end());
  auto last1 = std::chrono::steady_clock::now();

  auto first2 = std::chrono::steady_clock::now();
  std::sort(v2.begin(), v2.end());
  auto last2 = std::chrono::steady_clock::now();

  std::cout << "counting sort time: " << std::chrono::duration<double, std::milli>(last1 - first1).count() << " ms" << '\n';
  std::cout << "std::sort time: " << std::chrono::duration<double, std::milli>(last2 - first2).count() << " ms" << '\n';
  std::cout << "v1 == v2: " << std::equal(v1.begin(), v1.end(), v2.begin()) << '\n';

  return 0;
}

Associative container

Update: Because of the O(n.log(n)) nature of std::map we have concluded this is not a good idea (But it was worth the test).

Rather than using a vector to store the count you can use an associative container.

std::vector<std::size_t> counts(max - min + 1, 0);

// replace with

using ValueType = std::iterator_traits<InputIterator>::value_type;
std::map<ValueType, std::size_t>  counts;

This will limit the amount of memory you use otherwise the amount of space you use could potentially exceed memory.
Also iterating over a sparse array would be expensive (As there will be lots of zero counts). By using an associative container you only iterate over valid values.

Range based for

Use the new range based for.

for (auto it_c = counts.begin(); it_c != counts.end(); ++it_c) {

// replace with:

for(auto const& value: counts) {

Combine range based for and associative containers

void counting_sort(InputIterator first, InputIterator last)
{
    using ValueType = std::iterator_traits<InputIterator>::value_type;
    std::map<ValueType, std::size_t> counts;

    for(auto value: boost::make_iterator_range(first, last)) {
        ++counts[value];
    }

    for(auto count: counts) {
        ValueType&   value = count.first;
        std::size_t& size  = count.second;
        std::fill_n(first, size, value);
        std::advance(first, size);
    }
}


Template to determine most frequent entries within a collection The problem

Given an arbitrary collection of objects of some kind, count and report the top k most frequent, together with the associated count.  For example, if the input array is {'a', b', 'a', 'c', 'b', 'b'} and for k = 2, the template would return { {b, 3}, {'a', 2} }.  The idea for the template it to allow start and ending iterators for any kind of collection for which ::value_type is defined.

The inspiration

Writing this review reminded me that I had, at one point, written a template to solve exactly this kind of problem. So I searched the hard drive, found this, and thought I'd present it here to see if might be critiqued and improved.

Questions

In particular, I'd be interested in any scenario in which the template fails.  Additionally, are there any checks that could be made to make sure that only suitable iterators are passed?  If so, what might those be?

maxfreq.h

#ifndef MAXFREQ_H
#define MAXFREQ_H
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iterator>

/*
 * This template takes a start and ending iterator of a collection of
 * some kind.  It counts the number of occurences for each instance and
 * returns a vector of the top `k` instances each with their associated
 * count.
 */
template <class InputIt>
auto most_frequent_k(InputIt first, InputIt last, std::size_t k) -> std::vector<std::pair<typename InputIt::value_type, unsigned>> {
    typedef typename InputIt::value_type T;
    typedef typename std::pair<T, unsigned> Tcount;
    std::unordered_map<T, unsigned> count;
    for (; first != last; ++first) {
        ++count[*first];
    }
    std::vector<Tcount> pairs;
    auto m = count.size();
    pairs.reserve(m);
    k = std::min(k, m);
    std::copy(count.begin(), count.end(), std::back_inserter(pairs));
    std::partial_sort(pairs.begin(), pairs.begin()+k, pairs.end(), [](const Tcount &a, const Tcount &b) {
            return a.second > b.second;
            });
    pairs.erase(pairs.begin()+k, pairs.end());
    return pairs;
}

#endif // MAXFREQ_H

test.cpp

#include "maxfreq.h"
#include <iostream>
#include <sstream>

void test1()
{
    std::cout << "Test 1 {\n";
    std::vector<int> input{1,2,3,4,2,3,4,1,1,2,1,2,1,2,1,3,5};
    auto pairs = most_frequent_k(input.begin() , input.end(), 3);
    for (const auto &p : pairs) {
        std::cout << '\t' << p.first << ", " << p.second << '\n';
    }
    std::cout << "}\n";
}

void test2()
{
    std::cout << "Test 2 {\n";
    std::istringstream woodchuck{"how much wood would a woodchuck chuck if a woodchuck could chuck wood"};
    std::vector<std::string> input{};
    std::copy(std::istream_iterator<std::string>(woodchuck), std::istream_iterator<std::string>(), std::back_inserter(input) );
    auto pairs = most_frequent_k(input.begin() , input.end(), 3);
    for (const auto &p : pairs) {
        std::cout << '\t' << p.first << ", " << p.second << '\n';
    }
    std::cout << "}\n";
}

int main()
{
    test1();
    test2();
}

Output

Output from the test driver above looks like this:

Test 1 {
    1, 6
    2, 5
    3, 3
}
Test 2 {
    chuck, 2
    woodchuck, 2
    wood, 2
}

Well, nice to see you follow stdlib conventions for your algorithm and accept an iterator-range.
But you really should use std::iterator_traits<It> to query the iterators associated types, as-is you cannot handle pointers.

Let's hope the elements are efficiently copied, or the algorithm is staggeringly inefficient.

Next, the count of unique symbols is often much smaller than k, making first inserting all elements, then sorting and finally removing most quite inefficient.
Consider limiting the result-vector to never grow beyond k elements using a heap.
(The standard provides std::make_heap (and for sorted output alsostd::sort_heap), but not down_heap (a vastly more efficient combination of std::pop_heap and std::push_heap, building-block of make_heap).)


PHP framework building: initializer and object loader classes I am building a PHP framework and would like to get some feedback on a few different sections of the project. I consider myself still a neophyte in PHP so I would like to ask if I'm going about completing these different tasks in an efficient and or correct way.

I have create two classes,  initializer and Loader. The initializer class setup the autoload for the including of the class scripts and the loader instantiates the object using Singleton pattern. I have include the code below.

Initializer class

    class Initializer{
    private static $extention = array('.core.php','.class.php');
    private static $directories = array('core/','controller/','model/');

    public static function loadClassFiles(){
        spl_autoload_register(array(__CLASS__,'autoload'));
    }

    private static function autoload($class){
        set_include_path(get_include_path().PATH_SEPARATOR.implode(PATH_SEPARATOR,self::$directories));
        spl_autoload_extensions(implode(',',self::$extention));
        spl_autoload($class);
    }

}

Loader Class

class  ObjectLoader{
    public static $objectsArray = array();

    public static function loadClass($object){
        if (empty(self::$objectsArray[$object])) {
            self::$objectsArray[$object] = new $object();
        }
        return self::$objectsArray[$object];
    }
}

Example of the classes being used.
Please Note: That class files with the extensions .core.php or .class.php are being looked for in directories core/, controller/ or model/.

Initializer::loadClassFiles();
$objectOne = ObjectLoader::loadClass('objectone');
$objectTwo = ObjectLoader::loadCLass('objecttwo');

I would like to know if this is a good way to go about it.

As promised in the comments I would write a more extensive answer. So here it goes.

Before I start I would like to say that I think it is a perfect learning opportunity building your own framework. I have been in the process of creating my own the last year or so. I started from scratch with little knowledge of the different things, so the things I point out in this answer is a mixture of experience (from trial and error) and best practices I have learned as valuable over that year.

I think the code you have provided shows you have a basic (though bare minimum) idea of how the code should work, a good start. Everything mentioned below should be taken as my way of helping you and pointing out errors that I made and I wished somebody helped me correct sooner.

The Initializer class

First of, your Initializer class attempts to load classes by declaring the include path and extensions over and over and THEN load the class. This should only be done once. It happens because you have provided the name of the function autoload to the spl_autoloader_register. PHP then runs this function each time a class is loaded. You then make a call to spl_autoload() which is irrelevant. A call to spl_autoload_register() with no parameters is just a good, in fact it might be a little faster as it is written in highly optimized code by PHP.

I feel like the initializer class needs another name. All it is doing is setting up autoloading of classes. A more appropriate name could be Autoloader?

Now to the class itself. The class uses static methods. I think the use of static methods has it place, but it is misused here. The autoloader class should only be instantiated once, so the need for static properties is not required.

When declaring paths to directories in which your classes resides, consider using fully qualified paths as they are a little faster than their relative counterpart. When loading a lot of classes this little improvement can save you some resources. Fully qualified paths can be achieved by:

$directories = []; // An array of directories.

/*
 * Hard-coding the paths when all paths are known would be preferred.
 * The function realpath() requires executable rights on all directories used.
 */
foreach($directories as $key => $directory) {
    $directories[$key] = realpath($directory);
}

Another thing which caught my eye was the hardcoded properties. Part of the solid principle states that a class should be open for extension, but closed for modification. This can be easily achieved by providing the directories/paths and extensions used as arguments in a constructer of the class. This would allow you to easily add more directories without altering the code you have already written.

Below I have written an example of the things I have stated above. Feel free to use it, but remember this is bare minimum code.

class Autoloader {

    private $directories = [];
    private $extensions = [];

    public function __construct(array $directories, array $extensions) {
        $this->directories = $directories;
        $this->extensions = $extensions;

        $this->register();
    }

    private function register() {

        $directories = array_merge((array) get_include_path(), $this->directories);
        $extensions  = implode(',', $this->extensions);

        set_include_path(implode(PATH_SEPARATOR, $directories));

        spl_autoload_extensions($extensions);
        spl_autoload_register();

    }

}

The usage will now look like:

$directories = [
    'core/',
    'controller/',
    'model/'
];

$extensions  = [
    '.php', // Added for compatibility with other libraries.
    '.core.php',
    '.class.php'
];

/*
 * Storing the instance in a variable is
 * not required.
 */
$autoloader = new Autoloader($directories, $extensions);

The loader class

As I said in the comments one of the two biggest issues that caught my eye was the inability to instantiate a new instance. I made the same assumption that storing each instance in a static property would save a lot of resources. But the reality proved me wrong. Here is one of the issues I have encountered.

With the good intention of saving resources you store the instances, so they can be referenced. But then you have a problem when you want to delete an resource intensive instance entirely. You cannot use unset($instance), because the reference to the instance would remain in the loader and no resources would be freed.

I therefore think you should provide a way to indicate that the class SHOULD be a shared (singleton) and all classes by default are non-shared. But this would render the purpose of the class useless, as you would only wrap the way a class is instantiated and you might even limit yourself at the same time as you cannot pass arguments to the class. So what I would do is make the class able to store an array of class names that should be shared and let it keep track of them. You would then provide it with an array of shared class names once (during instantiation of the Loader itself) and when you create a new class and need it shared, you would update that array.

The second issue is that you are unable to provide arguments to the instantiated class through the loader as it is. You would have to use plain PHP which renders the loader useless. This can easily be changed, which I will show in my version/refactoring of your code.

Then there is a litte bug in your code, where you check if an instance exists. The empty keyword checks if an array or string is empty and not if an array key exists (check the documentation to see which values are considered empty). Use the isset() keyword or the more verbose (but more readable in my opinion) array_key_exists() function.

I also think the class should avoid using static methods. I know this will prevent you from using class inside other classes as easily, but the classes required by other classes (dependencies) should be provided as arguments. Read up on Dependency injection (Tutsplus). I will also provide you with some resources you can read at the end.

Now when we stitch all this together an example of the loader class could look like the following:

class Loader {

    private $instances = [];
    private $shared = [];

    /*
     * The $shared argument has a default value of an empty array. This
     * makes the argument optional. Use this if no classes should be shared.
     */
    public function __construct(array $shared = []) {
        $this->shared = $shared;
    }

    /**
     * Load an instance of the specified class.
     *
     * @param string $class
     * @param array  $arguments
     * @param bool   $singleton
     *
     * @return object
     */
    public function load($class, array $arguments = [], $singleton = false) {

        /*
         * Check if a shared instance exists.
         */
        if(array_key_exists($class, $this->instances)) {
            return $this->instances[$class];
        }

        /*
         * Create a new instance.
         * The use of the ReflectionClass gives us the ability to provide
         * an array as arguments.
         *
         * If no arguments was provided we skip the instantiation if the reflection class.
         */
        if(empty($arguments)) {
            $instance = new $class;
        }else{
            $instance = (new \ReflectionClass($class))->newInstanceArgs($arguments);
        }

        /*
         * Check if a singleton is requested or the class is marked as shared.
         */
        if($singleton === true || array_key_exists($class, $this->shared)) {
            $this->instances[$class] = $instance;
        }

        return $instance;
    }

    /**
     * Removes a class from the shared instances array.
     * Use this to free up resources used by intensive classes.
     *
     * @param string $class
     *
     * @return bool Returns TRUE of the class was removed. Returns FALSE of the class is not shared.
     */
    public function free($class) {
        if(array_key_exists($class, $this->instances)) {
            unset($this->instances[$class]);
            return true;
        }
        return false;
    }

}

Usage of this class would look like:

$shared = [
    'Foo',
    'Bar'
];

$loader = new Loader($shared);

$obj = $loader->load('Foo'); // Would be shared
$obj = $loader->load('Bar'); // Would be shared
$obj = $loader->load('BumbleBee'); // Would provide a new instance every time.
$obj = $loader->load('BumbleBee', [], true); // BumbleBee is now shared.

$loader->free('BumbleBee'); // Is not shared anymore.

Phew, that was quite a lot. I hope this isn't too overwhelming. All the things I have pointed out are issues that I have experienced as solved like shown. Every single change may not suit your framework, but they helped me.

As promised I have listed some resources you can look at. I learned a lot even though some of them isn't PHP they certainly do apply.

Most of the resources linked at the bottom of this epic answer.
Dependency injection
(Advanced) SOLID Design principle. Not all of the principles can be easily achieved, but having them in mind while coding will help you out later, I know it have for me.
Document your code . The code you have provided are relatively simple. But when you have grown into a PHP guru and others look up to your code (or yourself six months later), good documentation of the more complex code is good. Do not document every single little array look up or variable initialization, but when the code doesn't immediately reveal its purpose documentation is lovely.

Happy coding out there!


Refactoring a Delimiter Is there a more cleaner approach to this? I'm doing the String calculator Kata posted by Roy Osherove. I realized that my calculator has no way of clearing out a previous expression after calling add. How can I handle this, and also how can I cut down the number of methods?

Here's a valid string: calc.add("//+\n1+2")

Here's an invalid string: calc.add("//b\n1b2")

class StringCalculator
  attr_reader :numbers

  def initialize(numbers = '')
    @numbers = numbers
  end

  def add(expression)
    @numbers << expression
    return nil if @numbers.end_with("\n")
    @numbers.gsub!(/\n/, delimiter)
    @numbers.empty? ? 0 : solution
  end

  private

  def valid_delimiters
    [*(33..46), *(58..64)].map(&:chr).join
  end

  def solution
    numerics = @numbers.split(delimiter).map(&:to_i)
    find_negatives(numerics)
    numerics.reduce(:+)
  end

  def find_negatives(numerics)
    negatives = numerics.select { |n| n < 0 }
    fail "negatives not allowed: #{negatives.join(', ')}" if negatives.any?
  end

  def supports?
    valid_delimiters.include?(@numbers[2, 1])
  end

  def delimiter
    return ',' unless @numbers.match(%r{^//})
    supports? ? @numbers[2, 1] : fail('Unsupported delimiter')
  end
end

Some of the code seems to be missing - I can't see where you assign @numbers. I'm going to assume that it is set to "//+\n1+2" or the like.

DRY - twice in your code you calculate the delimiter (@numbers[2,1]), either pass it as an argument, or make it a method.

Btw, you seem to have a syntax error there, you might have meant to say supports? ? @numbers... instead.

Be clear, not clever you show good control in ranges, array, chars, etc., but still the following will be much clearer to future readers of your code (you included!)

ValidDelimiters = "!\"\\#$%&'()*+,-.:;<=>?@"

(if you don't like to see escaped sequences, you can use %{!"\#$%&'()*+,-.:;<=>?@} instead)

Be Ruby - when you need to return a boolean, which is returned on a condition, there is no need to explicitly say .. ? true : false, simply return the condition result

Harness the power of regular expressions - when matching strings, captures are set to $n variables - you can use this to check your delimiter more elegantly:

ValidDelimiters = "!\"\\#$%&'()*+,-.:;<=>?@"

def supports?(delim)
   ValidDelimiters.include? delim
end

def delimiter
  return ',' unless @numbers.match(%r{^//(.)})
  delim = $1
  supports?(delim) ? delim  : fail('Unsupported delimiter')
end

Edit - with the new code

Naming - choose names that convey the meaning of the member - @numbers implicitly say it is a group of numbers, although it is actually a string... better name might be input_expression or something like that.

Redundant code with side-effects - your constructor accepts a string as input, which you assign to @numbers. This is not part of the requirements, and you probably don't have tests for that, but it may have serious impact on your result!

Also, for each time you call add, the input is concatenated to the end of the previous result (also not part of the requirements), which will break your code.

Assume nothing - Ruby's to_i method is very liberal - anything that is not a number will be parsed to - 0, so an input like "1,2,goat,3" will give a valid result of 6...

When state is redundant - when assuming each add is supposed to be a separate calculation - no state is needed. You can simply pass the expression around to your helper methods, and return the result. You can even turn your class into a module, with all methods being class methods, and the usage will be `StringCalculator.add('//+\n1+2')


Getting display size compact class in Android I have written a common class for finding display sizes in pre-honeycomb and for the latest versions of Android. Could anyone review my code and suggest possible modifications for this code?

import android.annotation.TargetApi;
import android.content.Context;
import android.graphics.Point;
import android.os.Build;
import android.view.Display;
import android.view.WindowManager;

public class DisplayManager {

    private Display mDisplay;
    private WindowManager mWindowManager;

    public DisplayManager(Context mContext) {
        mWindowManager = (WindowManager) mContext.getSystemService(Context.WINDOW_SERVICE);
        mDisplay = mWindowManager.getDefaultDisplay();
    }

    @TargetApi(Build.VERSION_CODES.HONEYCOMB_MR2)
    public int getDisplayHeight() {
        if (Integer.valueOf(android.os.Build.VERSION.SDK_INT) < 13) {
            return mDisplay.getHeight();
        } else {
            Point size = new Point();
            mDisplay.getSize(size);
            return size.y;
        }
    }

    @TargetApi(Build.VERSION_CODES.HONEYCOMB_MR2)
    public int getDisplayWidth() {
        if (Integer.valueOf(android.os.Build.VERSION.SDK_INT) < 13) {
            return mDisplay.getWidth();
        } else {
            Point size = new Point();
            mDisplay.getSize(size);
            return size.x;
        }
    }
}

First of all, this line:

if (Integer.valueOf(android.os.Build.VERSION.SDK_INT) < 13) {

Should be replaced with this:

if (Build.VERSION.SDK_INT < Build.VERSION_CODES.HONEYCOMB_MR2) {

Because a) There's no need to use Integer.valueOf for something that is already an int. b) Build.VERSION_CODES.HONEYCOMB_MR2 is a constant (or as we call it in Java, public static final) with the value 13. Avoid using "magic numbers" in your code like that, instead refer to existing constants or create new constants when necessary.

Secondly, I really doubt that the size of your screen will change while your object exists. Which means that this code need only to be run once and can therefore be placed in the constructor:

Point size = new Point();
mDisplay.getSize(size);

Now to the last point I want to make. Your mWindowManager variable is only used within the constructor. I see no need at all for that to be a field in your class. Change that to a local variable instead.

It is also a good practice to make your class fields final when possible (which is both possible for the mDisplay and also your newly created Point size field). The final keyword makes sure that you get a compiler error if you try to change the value of the variable after it has been initialized. Note that mDisplay.getSize(size) doesn't change the variable itself, it changes the values within the variable, i.e. the object size remains the same.

Besides this, I have to say that your code looks excellent. You have good variable names. I don't even see any indentation problems (except those that StackExchange create, but they're not your fault).


Pigeon and grain problem: find time until all the grain is eaten Problem:

  There are \$n\$ pigeons and \$m\$ grains. Pigeon \$i\$ eats a single grain every \$x_i\$ seconds. Find the time until all the grain is eaten.

  Input:

  A line with the integer \$m\$ giving the number of grains, followed by a line with \$n\$ integers \$x_1, x_2, \ldots, x_n\$ giving the time taken by each pigeon to eat one grain.

Currently I am doing a loop over each second and finding how many grains in that seconds are eaten. This with numpy I am able to get a good performance but for large inputs (\$m=10^{25}\$ and \$n=300000\$) the program runs forever.

What can I do mathematically to solve this?

import numpy

def melt(grains,birdTimes):
    counter=0
    counts = numpy.zeros(len(birdTimes,),dtype=numpy.int)
    birdTimes = numpy.array(birdTimes)
    while (grains>0):
        counts=counts+1
        temp=birdTimes-counts
        zeroA = numpy.where(temp==0)[0]
        grains = grains - len(zeroA)
        counts[zeroA] =0
        counter+=1
    return counter

Basically we're looking for the smallest value of \$T\$ which satisfies the discrete equation

$$ \left\lfloor {T \over x_1} \right\rfloor + \left\lfloor {T \over x_2} \right\rfloor + \dots + \left\lfloor {T \over x_n} \right\rfloor \ge m $$

where \$\lfloor {x \over y} \rfloor\$ is the floor division operation (// in Python). So we know the regular division operation (/ in Python) will also be a valid solution to this, albeit not necessarily with the smallest possible \$T\$:

$$ {T \over x_1} + {T \over x_2} + \dots +  {T \over x_n}  \ge m $$

If we factor out the \$T\$ time value, we see this is just an inequality of the form:

$$ \mathrm{Time} × \mathrm{Rate\ of\ consumption} \ge \mathrm{Amount\ consumed} $$

and thus

$$ \mathrm{Time} \ge {\mathrm{Amount\ consumed} \over \mathrm{Rate\ of\ consumption}}$$

We know the rate of consumption and amount consumed, and so by refactoring the earlier inequality we get this:

$$ T\left( {1 \over x_1} + {1 \over x_2} + \dots +  {1 \over x_n} \right) \ge m $$

and thus

$$ T \ge {m \over \left( {1 \over x_1} + {1 \over x_2} + \dots +  {1 \over x_n} \right)} $$

You can use this as a heuristic which will get you close to your desired value of \$T\$, now your search space just needs to check values greater than the above result. Start by

T = int(M / ((1. / xs).sum()))

Then iterate upwards to the correct value using your method of choice. How about filling the smallest available remainder to the next multiple? Like so:

while True:
    v = (T // xs).sum()
    if v >= M:
        break
    T += (xs - T % xs).min()
return T

I'm sure there's a closer-to-closed-form solution to this.


Regex for nginx log parser I made the following regular expression for parsing ngnix log

log_1 = "1.169.137.128 -  - [29/jun/2017:07:10:50 +0300] "GET /api/v2/banner/1717161 http/1.1" 200 2116 "-" "Slotovod" "-" "1498709450-2118016444-4709-10027411" "712e90144abee9" 0.199"

My test cases (https://regex101.com/r/Eyhxod/1)

lineformat = re.compile(r"""(?P<ipaddress>\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}) -  - \[(?P<dateandtime>\d{2}\/[a-z]{3}\/\d{4}:\d{2}:\d{2}:\d{2} (\+|\-)\d{4})\] \"GET (?P<url>.+?(?=\ http\/1.1")) http\/1.1" \d{3} \d+ "-" (?P<http_user_agent>.+?(?=\ )) "-" "(?P<x_forwaded_for>(.+?))" "(?P<http_xb_user>(.+?))" (?P<request_time>[+-]?([0-9]*[.])?[0-9]+)""",re.IGNORECASE)

Output:

data = re.search(lineformat, log_1)
data.groupdict()

{'ipaddress': '1.169.137.128',
 'dateandtime': '29/jun/2017:07:10:50 +0300',
 'url': '/api/v2/banner/1717161',
 'http_user_agent': '"Slotovod"',
 'x_forwaded_for': '1498709450-2118016444-4709-10027411',
 'http_xb_user': '712e90144abee9',
 'request_time': '0.199'}

I believe I should make it more robust towards edge cases and broken logs. Also I consider splitting my long expression into a smaller one.
Any advices towards the best-practices are appreciated.

At the very least, use verbose mode so you can see the whole thing at once.  Remember to explicitly include whitespace.

lineformat = re.compile(r"""
   (?P<ipaddress>\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})\s+
   -\s+
   -\s+
   \[(?P<dateandtime>\d{2}\/[a-z]{3}\/\d{4}:\d{2}:\d{2}:\d{2} (\+|\-)\d{4})\]\s+
   \"GET (?P<url>.+?(?=\ http\/1.1")) http\/1.1"\s+
   \d{3}\s+
   \d+\s+
   "-"\s+
   (?P<http_user_agent>.+?(?=\ ))\s+
   "-"\s+
   "(?P<x_forwaded_for>(.+?))"\s+
   "(?P<http_xb_user>(.+?))"\s+
   (?P<request_time>[+-]?([0-9]*[.])?[0-9]+)
   """,
   re.IGNORECASE | re.VERBOSE)


A light/dark theme toggle react component I have a dark theme toggle switch for my React component that works well, but I know the code could use some work. First I am checking to see what the users' preferences are for light/dark. Then I am setting in local storage what the user has chosen as a preference and then also checking for that value. I'm still learning and would like some feedback.

My requirements:

Needs to check the users' system preference for light/dark
Needs to persistently keep users light/dark preference throughout the site
Add class dark to the body tag in order to active all the CSS changes

import React, { Component } from "react";

class LightDarkToggle extends React.Component {

  componentDidMount() {
    let bodyClassList = document.body.classList;
    let themeSwitch = document.getElementById('switch-style');

      //Here we are checking the USERS' device settings for dark theme
      if(window.matchMedia('(prefers-color-scheme: dark)').matches) {
        bodyClassList.add('dark');
        themeSwitch.checked = true;
      }
      else if(window.matchMedia('(prefers-color-scheme: light)').matches) {
        bodyClassList.remove('dark');
        themeSwitch.checked = false;
      }

      //Persisting USERS' theme preference by checking the local storage we set
      if(window.localStorage.getItem('theme') === 'dark') {
        bodyClassList.add('dark');
        themeSwitch.checked = true;
      }
      else if(window.localStorage.getItem('theme') === 'light') {
        bodyClassList.remove('dark');
        themeSwitch.checked = false;
      }

  }

  handleClick() {
    document.body.classList.toggle('dark');

    if(document.getElementById('switch-style').checked === true){
      window.localStorage.setItem('theme', 'dark');
    }
    else if (document.getElementById('switch-style').checked === false){
      window.localStorage.setItem('theme', 'light');
    }

  }

  render() {
    return (

          <input type="checkbox" id="switch-style" onClick={this.handleClick} />

    );
  }
}

export default LightDarkToggle;
```

Here are some suggestions:
handleClick method
Intead of calling document.getElementById and checking for .checked twice, you can store it's value into a constant like this:
const isDarkMode = document.getElementById("switch-style").checked;

then just do window.localStorage.setItem("theme", isDarkMode ? "dark" : "light");
After these changes, the method will look like this:
handleClick() {
    document.body.classList.toggle("dark");
    const isDarkMode = document.getElementById("switch-style").checked;
    window.localStorage.setItem("theme", isDarkMode ? "dark" : "light");
}

componentDidMount method
This code can be simplified
if (window.localStorage.getItem("theme") === "dark") {
    bodyClassList.add("dark");
    themeSwitch.checked = true;
} else if (window.localStorage.getItem("theme") === "light") {
    bodyClassList.remove("dark");
    themeSwitch.checked = false;
}

You could make use of toggle method's second parameter, which is a boolean value that forces the class to be added or removed, regardless of whether or not it already existed.
So that code could be changed to
const mustUseDarkMode = window.localStorage.getItem("theme") === "dark";
bodyClassList.toggle("dark", mustUseDarkMode);
themeSwitch.checked = mustUseDarkMode;


Binary string to decimal conversion Problem Statement:

  Write a program that will convert a binary number, represented as a
  string (e.g. '101010'), to its decimal equivalent using first
  principles

  Implement binary to decimal conversion. Given a binary input string,
  your program should produce a decimal output. The program should
  handle invalid inputs.

Code:

public class Binary {
  private final String binaryString;

  public Binary(String binaryString) {
    this.binaryString = binaryString;
  }

  public int getDecimal() {
    return toDecimal(binaryString);
  }

  public static int toDecimal(String str) {
    int decimal = 0;
    int base0 = (int)'0';
    char ch;
    for (int i = 0; i < str.length(); i++) {
      ch = str.charAt(i);
      if (charIsNotBinary(ch)) {
        return 0;
      }
      decimal = decimal * 2 + ((int)str.charAt(i) - base0);
    }
    return decimal;
  }

  private static boolean charIsNotBinary(char ch) {
    return '1' < ch || ch < '0';
  }
}

Test Suite:

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import java.util.Arrays;
import java.util.Collection;

import static org.junit.Assert.assertEquals;

@RunWith(Parameterized.class)
public class BinaryTest {

    private String input;
    private int expectedOutput;

    @Parameters
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][]{
                {"1", 1},
                {"10", 2},
                {"11", 3},
                {"100", 4},
                {"1001", 9},
                {"11010", 26},
                {"10001101000", 1128},
                {"2", 0},
                {"5", 0},
                {"9", 0},
                {"134678", 0},
                {"abc10z", 0},
                {"011", 3}
        });
    }

    public BinaryTest(String input, int expectedOutput) {
        this.input = input;
        this.expectedOutput = expectedOutput;
    }

    @Test
    public void test() {
        Binary binary = new Binary(input);

        assertEquals(expectedOutput, binary.getDecimal());
    }
}

Reference:

http://exercism.io/exercises/java/binary/readme

Usability

The Binary class has two kinds of usages:

Create an instance from a binary string, to get the decimal value later
A utility class with a utility method to convert a binary string to decimal value

Having two usages is confusing.
In general, an API that lets you accomplish the same thing in multiple ways raises questions like "which way is better",
which is not a very productive discussion.
Just provide one way, and there will be less questions asked, less confusion.

In this particular example,
it might make sense to move the converter logic to a BinaryUtils utility class.
If you still want a class that contains a binary string and decimal value,
then you can keep the Binary class for that purpose.

Pre-calculate when it makes sense

Getters should not calculation. When I see a method named "getSomething",
I assume it simply returns the value of a field (or sometimes a defensive copy).
But in this class, it calculates the decimal value.
Every time it's called, again and again.
Since the method always returns the same value,
it would be better to calculate that value once,
at construction time.
And that way, the getter will naturally really return just a simple field value.

Avoid negation in names

Negation as the "Not" in charIsNotBinary may lead to double-negation in code like if (!charIsNotBinary(...)) { ... }, which can be confusing.
It's better to rewrite as isBinary, and use ! where you need to negate it.

Using < and > operators is also slightly odd, feels kind of overkill for a range of size 2.
This way seems simpler and more natural:

  private static boolean isBinary(char ch) {
    return ch == '0' || ch == '1';
  }