Sum of nodes at a given depth of a binary tree (String representation) Given a binary tree of integers and a depth, the goal is to find the sum of all node values at the depth in the tree. The root is considered depth 0, and the tree is given as a string in the format: (<node-value>(<left subtree>)(<right subtree>)). For example, treeLevelSum("(5(42)(-37(28)()))", 1) should return 5.

int treeLevelSum(String tree, int k) {
    int sum   = 0;

    int depth = 0;
    int value = 0;
    int sign  = 1;
    for (int i = 1; i < tree.length(); i++) {
        if (tree.charAt(i) == '(') {
            depth += 1;
        } else if (tree.charAt(i) == ')') {
            sum   += value * sign;
            value  = 0;
            sign   = 1;
            depth -= 1;
        } else if (depth == k) {
            if (tree.charAt(i) == '-') {
                sign = -1;
            } else {
                value = value * 10 + (tree.charAt(i) - '0');
            }
        }
    }

    return sum;
}

I was just wondering if there was a better way of parsing this, or if there was any way of improving efficiency? Is there a known "best solution" for this kind of problem?

Most likely you can't improve too much on this approach, as you do need to scan the entire string, and you don't convert any unneeded values. So as I see it there are three things you could try changing, but most likely they either not make a difference, or possibly even increase running time.

Pre-calculate the length of the string – Not quite sure how Java handles this one, but in the end-condition of your for loop you do tree.length(). If this had been a costly function, then some languages would execute this function for each run through the loop, and would benefit from this being done in front of the for loop. The length of your string isn't going to change in this case, so it should be safe to just do it once before the loop.
Not using repeated calls to tree.charAt(i) – In your code, in the worst case, you call tree.charAt(i) 4 times (when calculating the value). This could possibly be done outside the if block just once. However, this function is \$O(1)\$, so the benefit wouldn't be large.
Change the value extraction – Another change which could be made, is to change the way you extract the value. An alternative approach could be that after detecting the opening paranthesis, you could scan the string for the entire value string, and then convert it.

This could be done by preserving the start index of the value string, search until you hit a new parenthesis, and then convert the substring directly into a number. However, this doesn't need to be a faster method.

I've given no code in this answer, but I think you're getting the ideas.

One comment though on chosen algorithm, is that you calculate the value when on the correct depth, but you don't actually use it before you've traversed all child trees and then hit the end parenthesis.This isn't a problem in the current specification, but if it changed to sum up all values on multiple depths, it would fail miserably.

My final comment, is that your code does look clean and tidy with good names. If I'd change anything I would possibly add a little more vertical space, and some comments as to what the method is doing.


How to improve method of opening file in python then writing to another? Very simple I want to edit a virtual host files and replace the tags I made with some actual data:

import os, re
with open('virt_host', 'r+') as virtual
    file = virtual.read()
    file = re.sub('{{dir}}', '/home/richard', file)
    file = re.sub('{{user}}', 'richard', file)
    file = re.sub('{{domain_name}}', 'richard.com', file)

with open('new_virt', 'w+') as new_file
    new_file.write(file)
    new_file.close()

Is this the best way?

import os, re

Here, make sure you put a colon after virtual

with open('virt_host', 'r+') as virtual:

Avoid using built-in Python keywords as variables (such as file here)

    f = virtual.read()

This part is explicit, which is a good thing. Depending on whether or not you have control over how your variables are defined, you could use string formatting to pass a dictionary containing your values into the read file, which would save a few function calls.

    f = re.sub('{{dir}}', '/home/richard', f)
    f = re.sub('{{user}}', 'richard', f)
    f = re.sub('{{domain_name}}', 'richard.com', f)

Same as above regarding the colon

with open('new_virt', 'w+') as new_file:
    new_file.write(f)

One of the main benefits of using a context manager (such as with) is that it handles things such as closing by itself. Therefore, you can remove the new_file.close() line.

Here is the full code with the adjustments noted. Hope it helps!

import os, re

with open('virt_host', 'r+') as virtual:
    f = virtual.read()
    f = re.sub('{{dir}}', '/home/richard', f)
    f = re.sub('{{user}}', 'richard', f)
    f = re.sub('{{domain_name}}', 'richard.com', f)

with open('new_virt', 'w+') as new_file:
    new_file.write(f)


Stack implementation in ES6 Finally happy to see that now we can have iterators and generators. I also need to try to have private properties too so that we have well encapsulated data structures and I see that there are Proxies and Symbols which could help me do that.

Utils:

export const isDefAndNotNull = object =>
  object !== undefined && object !== null;

export const isIterable = object =>
  isDefAndNotNull(object) && typeof object[Symbol.iterator] === 'function';

Code:

import {isDefAndNotNull, isIterable} from "./Utils";

function *reverseArrayGenerator(arr) {
  let i = arr.length;
  while(--i >= 0) {
    yield arr[i];
  }
}

const data = Symbol("data");

export default class {
  constructor(iterable) {
    this[data] = [];
    if (isIterable(iterable)) {
      for (let item of iterable) {
        this.push(item);
      }
    }
  }

  peek() {
    return this[data].slice(-1)[0];
  }

  push(item) {
    this[data].push(item);
  }

  pop() {
    return this[data].pop();
  }

  isEmpty() {
    return this[data].length === 0;
  }

  size() {
    return this[data].length;
  }

  toString() {
    let res = [];
    for (let item of this) {
      res.push(item);
    }
    return JSON.stringify(res.join(' '));
  }

  [Symbol.iterator]() {
    return reverseArrayGenerator(this[data]);
  }
}

Test:

import {strictEqual as equal} from "assert";
import Stack from "../src/Stack";

suite("Stack", () => {
  test("without iterator", () => {
    const s = new Stack();
    s.push(1);
    equal(s.size(), 1);
    equal(s.pop(), 1);
    equal(s.size(), 0);
  });

  test("with iterator", () => {
    let s = new Stack([1, 2, 3]);
    equal(s.size(), 3);
    s = new Stack('hello');
    equal(s.size(), 5);
    s = new Stack([{name: 'Foo'}, {name: 'Bar'}]);
    equal(s.size(), 2);
  });

  test("peek", () => {
    let s = new Stack([1, 2, 3]);
    equal(s.peek(), 3);
    s.pop();
    equal(s.peek(), 2);
  });

  test("iterator", () => {
    const s = new Stack([1, 2, 3]);
    let i = 3;
    for(let item of s) {
      equal(item, i);
      i--;
    }
  });
});

Reference: http://algs4.cs.princeton.edu/13stacks/Stack.java.html

Why are you using a symbol for the data? If you're hoping for private variables, you're out of luck.
return JSON.stringify(res.join(' ')); Why? Why not just return JSON.stringify([...this]) or something? Why both join into a string and JSON stringify?
return this[data].slice(-1)[0]; is inefficient as it needlessly copies the array for each call. return this[data][this.size()]; should be (if marginally) better.
Why is your reverseArrayGenerator generator function not in Utils?
isDefAndNotNull, while nice, can be shortened or completely dropped. Shortened to object != null which is exactly the same thing, or dropped altogether in favor of:   object && typeof object[Symbol.iterator] === 'function';

I won't repeat what the other answer says, but it's also correct.


Unit testing where you depend on implementation of another method I am implementing a gap buffer and am trying to write a test for the insert method, the test currently looks something like this:

gapBuffer.insert('a')
assertEquals(gapBuffer.getText(), "a")
gapBuffer.insert('c')
assertEquals(gapBuffer.getText(), "ac")
gapBuffer.insert('d')
assertEquals(gapBuffer.getText(), "acd")
gapBuffer.moveCursorTo(1)
gapBuffer.insert('d')
assertEquals(gapBuffer.getText(), "abcd")

Now the problem is that this method is not just testing the insert method because it depends on the correctness of the getText() and moveCursorTo() methods

Note: the getText() and moveCursorTo() methods are not trivial but do have tests of their own

It's usually hard to test a setter without a getter and vice versa. Back Door Manipulation in xUnit Test Patterns discuss this in detail.

Some smells from the same book/site:

Eager Test: A single test verifies too much functionality.
Missing Assertion Message: A test fails. Upon examining the output of the Test Runner, we cannot determine exactly which assertion had failed.

I'd create at least three tests from the one above:

@Test
public void testInsert() {
    gapBuffer.insert('a')
    assertEquals(gapBuffer.getText(), "a")
}

@Test
public void testInsertTwice() {
    gapBuffer.insert('a')
    gapBuffer.insert('c')
    assertEquals(gapBuffer.getText(), "ac")
}

@Test
public void testMoveCursorToAndInsert() {
    gapBuffer.insert("acd")
    gapBuffer.moveCursorTo(1)
    gapBuffer.insert('d')
    assertEquals(gapBuffer.getText(), "abcd")
}

It helps Defect Localization.


Checking if two byte arrays are the same I have a method to compare two byte arrays. The code is Java-style, and there are many if-elses.

def assertArray(b1: Array[Byte], b2: Array[Byte]) {
  if (b1 == null && b2 == null) return;
  else if (b1 != null && b2 != null) {
    if (b1.length != b2.length) throw new AssertionError("b1.length != b2.length")
    else {
      for (i <- b1.indices) {
        if (b1(i) != b2(i)) throw new AssertionError("b1(%d) != b2(%d)".format(i, i))
      }
    }
  } else {
    throw new AssertionError("b1 is null while b2 is not, vice versa")
  }
}

I have tried as following, but it's not simplified the code much:

(Option(b1), Option(b2)) match {
    case (Some(b1), Some(b2)) => if ( b1.length == b2.length ) {
       for (i <- b1.indices) {
        if (b1(i) != b2(i)) throw new AssertionError("b1(%d) != b2(%d)".format(i, i))
       }
    } else {
       throw new AssertionError("b1.length != b2.length")
    }
    case (None, None) => _
    case _ => throw new AssertionError("b1 is null while b2 is not, vice versa")
}

Part of the problem is all the exceptions. There are better ways of handling exceptions, such as Scalaz Validation or Lift's Box. Scala itself comes with Either, which isn't particularly flexible.

On the other hand, you are not returning anything, which actually turns the whole code into a reverse Option: you either have Some(exception) or None.

Now, the test itself, except for checking for nulls, has a name in Scala: sameElements. Only it will not tell you what the problem was.

I can think of two ways of handling it. The first is just a small improvement on your pattern matching:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = (Option(b1), Option(b2)) match {
  case (None, None) =>
  case (None, _) | (_, None) => throw new AssertionError("b1 is null while b2 is not, vice versa")
  case (Some(b1), Some(b2)) if b1.length == b2.length =>
    (b1, b2).zipped.map(_ == _)
    .zipWithIndex.find(!_._1)
    .foreach {
      case (_, i) => throw new AssertionError("b1(%d) != b2(%d)".format(i, i))
    }
  case _ => throw new AssertionError("b1.length != b2.length")
}

The other way would be to turn the problem around completely. It would be like this:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = {
  def isOneNull =
    if ((b1 eq null) ^ (b2 eq null)) Some("b1 is null while b2 is not, vice versa")
    else None

  def areSizesDifferent =
    if (b1.length != b2.length) Some("b1.length != b2.length")
    else None

  def haveDifferentElements =
    (b1, b2).zipped.map(_ == _)
    .zipWithIndex.find(!_._1)
    .map { case (_, i) => "b1(%d) != b2(%d)" format (i, i) }

  def areTheyDifferent =
    if ((b1 ne null) && (b2 ne null)) areSizesDifferent orElse haveDifferentElements
    else isOneNull

  areTheyDifferent foreach (msg => throw new AssertionError(msg))
}

This is longer, and handles nullness in two separate places, and doesn't protect against nullness, but I think it reads much better. To get more than this I need Scalaz:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = {
  def isOneNull =
    (b1 eq null) ^ (b2 eq null) option "b1 is null while b2 is not, vice versa"

  def areTheyDifferent =
    Option(b1) <|*|> Option(b2) flatMap {
      case (b1, b2) =>
        def areSizesDifferent = b1.length != b2.length option "b1.length != b2.length"

        def haveDifferentElements =
          (b1, b2).zipped.map(_ == _)
          .zipWithIndex.find(!_._1)
          .map { case (_, i) => "b1(%d) != b2(%d)" format (i, i) }

        areSizesDifferent orElse haveDifferentElements
    } orElse isOneNull

  areTheyDifferent foreach (msg => throw new AssertionError(msg))
}

Or, to go more full-blown with Scalaz:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = {
  type Params = (Array[Byte], Array[Byte])
  type Func = Params => Option[String]

  def isOneNull =
    (b1 eq null) ^ (b2 eq null) option "b1 is null while b2 is not, vice versa"

  def areSizesDifferent: Func = {
    case (b1, b2) => b1.length != b2.length option "b1.length != b2.length"
  }

  def haveDifferentElements: Func = {
    case (b1, b2) =>
      (b1, b2).zipped.map(_ == _)
      .zipWithIndex.find(!_._1)
      .map { case (_, i) => "b1(%d) != b2(%d)" format (i, i) }
  }

  def areTheyDifferent =
    Option(b1) <|*|> Option(b2) flatMap (
      areSizesDifferent |@| haveDifferentElements
      apply (_ orElse _)
    ) orElse isOneNull

  areTheyDifferent foreach (msg => throw new AssertionError(msg))
}

Scala has an unfortunate overhead compared to Haskell to do these things. Also, Scalaz will be able to do a bit more in the next version, but this works with 6.0.

The gain with Scalaz is not, however, legibility or conciseness (in this code, anyway), but of composition. For instance, in the current Scalaz we can abstract most of the body of areTheyDifferent like this:

def composeFM[M[_]:Plus, F[_]:Applicative, B](f: F[M[B]], g: F[M[B]]): F[M[B]] =
  (f |@| g)(_ <+> _)
type FAB[x] = Array[Byte] => x
def areTheyDifferent = (
    Option(b1) <|*|> Option(b2)
    flatMap composeFM[Option, FAB, Int](areSizesDifferent, haveDifferentElements)
    orElse isOneNull
)

Note that composeFM doesn't know a thing about Option or Function1 -- it applies to the pattern.

Well, anyway, take your pick. Sometimes a problem just isn't worth the trouble, but it is useful to know how to handle the trouble anyway.


Python GUI by QtWebkit and Flask I'm new to Python. For learning purposes, I want to create desktop application by using QtWebKit and Flask. You can find the source code here

Main idea is:

create a form including a QWebview widget
create a Flask app
run Flask app on QWebview

It works correctly but I want to know:

How can I improve my code?
is this good way to create desktop apps?

My code is:

main.py

from core.Core import *

app = Flask(__name__)

from routes import *

if __name__ == '__main__':
    main(app)

core module: core/Core.py

import sys
from flask import Flask , render_template
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4.QtWebKit import *
from threading import Thread

class FlaskThread(QThread):

    def __init__(self,app):
        QThread.__init__(self)
        self.app = app

    def __del__(self):
        self.wait()

    def run(self):
        self.app.run()

def main(app):
    th = FlaskThread(app)
    th.start()
    #qt init
    qtapp = QApplication(sys.argv)
    qtapp.aboutToQuit.connect(lambda : th.terminate())
    webview = QWebView()
    webview.load(QUrl('http://localhost:5000'))
    webview.show()
    sys.exit(qtapp.exec_())

and then routes.py

from main import *

@app.route('/')
def index():
    #return 'hi'
    return render_template('index.html')

Your imports and module structure seems like an incredible mess. Yet your application only contains 3 files. Let's try and improve that.
Value your namespaces
import this

Preferably in an interactive session, will give you an insight of how you should approach problems in Python. In your case, it is the last line Namespaces are one honking great idea -- let's do more of those! which is at issue.
The core idea is to control where symbols can be found without risk of overriding them (or doing so knowingly). As such, from <something> import * is a bad practice and should either be:
import <something>

or
from <something> import <required_name1>, ..., <required_nameN>

This also means that you should removed unnecessary imports.
Avoid circular imports
I'm talking about having from main import * in routes.py and from routes import * in main.py.
One of the major issue with circular import is that one of them might bring an half-loaded module, (mainly) leading to NameErrors.
Why do you need to import routes in the first place? Nothing is used from that in main.py, so you can remove it.
Why do you need to import main in the first place? To be able to use render_template and the app object? Well, you should import render_template in routes.py and create app in there instead.
Don't over-split your code
Modules are good since they allow you to differentiate purposes for pieces of codes. But too much modules makes the code unmanageable.
At this stage of development you could still have all your code in a single file without loosing readability. But I imagine that you'll want to make your application grow and I understand your need to split it into different modules.
You made a good job identifying purposes:

a module to manage your webapp (routes.py);
a module to manage your GUI (in case you'll want to get something better than a QWebView in the future).

But I think you made a mistake making your GUI module "secondary". The GUI is the entry point of the application for your users, I would have made it the main module.
Then you can put routes.py into its own webapp (or whatever name fits its purpose more) folder. This will allow you to keep everything related to the "Web" part of your application in a single place. Try to at least separate your routes from your utilities functions.
You should also try to name your modules relative to what they do overall. main.py is not a good name.
New layout
pyfladesk.py
import sys

from PyQt4.QtCore import QThread, QUrl
from PyQt4.QtGui import QApplication
from PyQt4.QtWebKit import QWebView

PORT = 5000
ROOT_URL = 'http://localhost:{}'.format(PORT)

class FlaskThread(QThread):
    def __init__(self, application):
        QThread.__init__(self)
        self.application = application

    def __del__(self):
        self.wait()

    def run(self):
        self.application.run(port=PORT)

def provide_GUI_for(application):
    qtapp = QApplication(sys.argv)

    webapp = FlaskThread(application)
    webapp.start()

    qtapp.aboutToQuit.connect(webapp.terminate)

    webview = QWebView()
    webview.load(QUrl(ROOT_URL))
    webview.show()

    return qtapp.exec_()

if __name__ == '__main__':
    from webapp.routes import app
    sys.exit(provide_GUI_for(app))

webapp/routes.py
from flask import Flask, render_template

app = Flask(__name__)

@app.route('/')
def index():
    return render_template('index.html')

The few more changes I made contains:

improved naming a bit (not so much, you might come up with better names too);
converting magic values to constants so they can easily be spotted and changed;
used the callable webapp.terminate directly instead of creating a lambda.


LISP - Modify string I have to write a program that changes a string's vowels, consonants and other symbols into C, V respectively 0. I've done this but I wonder if there is a more efficient and elegant way to do it. Would appreciate input.

(defun string-to-list (string)
(loop for char across string collect char))

(defun is-vowel (char) (find char "aeiou" :test #'char-equal))

(defun is-consonant (char) (find char "bcdfghjklmnpqrstvwxyz" :test #'char-equal))

(defun letter-type (char)
(if (is-vowel char) "V"
(if (is-consonant char) "C"
"0")))

(defun analyze-word (word-string)
(loop for char across word-string collect (letter-type char)))

Moreover, I would like to make it a string, how could I do that? Should I define a function that would iterate through the list and make it a string or is it an easier way to do it?

I've got it, for the ones interested, the code is below. Used map to do it.

(defun string-to-list (string)
(loop for char across string collect char))

(defun is-vowel (char) (find char "aeiou" :test #'char-equal))

(defun is-consonant (char) (find char "bcdfghjklmnpqrstvwxyz" :test #'char-equal))

(defun analyze_word (word-string)
(loop for char across word-string collect (letter-type char)))

(defun letter-type (char)
  (cond ((find char "aeiou" :test #'char-equal) #\V)
        ((alpha-char-p char) #\C)
        (t #\0)))

(defun change_string (string)
(map 'string #'letter-type "analyze-word")
)

First, proper indentation helps a lot. I do appreciate you not putting the closing parens on separate lines though. Thank you.

(defun string-to-list (string)
  (loop for char across string collect char))

(defun is-vowel (char) (find char "aeiou" :test #'char-equal))

(defun is-consonant (char) (find char "bcdfghjklmnpqrstvwxyz" :test #'char-equal))

(defun letter-type (char)
  (if (is-vowel char) "V"
      (if (is-consonant char) "C"
      "0")))

(defun analyze-word (word-string)
  (loop for char across word-string collect (letter-type char)))

We're talking about Common Lisp, so there's no call to go defining your own string-to-list, especially if you're doing it in terms of loop. You can do the same thing with a coerce call.

CL-USER> (coerce "an example" 'list)
(#\a #\n #\  #\e #\x #\a #\m #\p #\l #\e)

Though now that I look at it, you don't call string-to-list anywhere anyway, so we may as well just remove the definition.

(defun is-vowel (char) (find char "aeiou" :test #'char-equal))

(defun is-consonant (char) (find char "bcdfghjklmnpqrstvwxyz" :test #'char-equal))

(defun letter-type (char)
  (if (is-vowel char) "V"
      (if (is-consonant char) "C"
      "0")))

(defun analyze-word (word-string)
  (loop for char across word-string collect (letter-type char)))

Common Lisp convention is to use a suffix of p or -p for predicates, rather than an is prefix.

(defun vowel-p (char) (find char "aeiou" :test #'char-equal))

(defun consonant-p (char) (find char "bcdfghjklmnpqrstvwxyz" :test #'char-equal))

(defun letter-type (char)
  (if (vowel-p char) "V"
      (if (consonant-p char) "C"
      "0")))

You can use cond rather than chaining ifs. Typically, this makes the intent clearer.

(defun letter-type (char)
  (cond ((vowel-p char) "V")
        ((consonant-p char) "C")
        (t "O")))

If you want to make the result of analyze-word a string, you'll need to return a character rather than a string from letter-type

(defun letter-type (char)
  (cond ((vowel-p char) #\V)
        ((consonant-p char) #\C)
        (t #\O)))

At that point, you can coerce its result.

CL-USER> (coerce (analyze-word "supercalifragilistiwhateverthefuck") 'string)
"CVCVCCVCVCCVCVCVCCVCCVCVCVCCCVCVCC"

Since your function is taking a sequence of characters, and returning a sequence of characters in the same form, it's actually easier to define analyze-word in terms of map than in terms of loop (in my experience, this is atypical but still worth looking out for).

(defun analyze-word (word-string)
  (map 'string #'letter-type word-string))

That will take "the function named letter-type", apply it to each element of word-string and return the resulting string. This also saves you from having to coerce its result after the fact.

CL-USER> (analyze-word "supercalifragilistiwhateverthefuck")
"CVCVCCVCVCCVCVCVCCVCCVCVCVCCCVCVCC"

Take this last point with a grain of salt though, because if you ever need to re-write analyze-word to return something like (list :consonants 21 :vowels 13), you'll be right back to loop.


Convenience function wrapping C++17's std::sample for distance=1 case C++ has the function std::sample which randomly samples from a range and places the results via an output iterator. My goal is to create a utility that directly returns a single value in the event that we only want to sample a single random element from the container.
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <unordered_set>
#include <array>

template<class InputIt, class URBG>
auto singleRandomSample(InputIt t_begin, InputIt t_end, URBG&& rng)
{
    using value_type = typename std::iterator_traits<InputIt>::value_type;
    std::array<value_type, 1> out;
    std::sample(t_begin, t_end, out.begin(), 1, rng);
    return out.at(0);
}

int main()
{
    std::default_random_engine rng{ std::random_device{}() };
    std::unordered_set<char> vowels{ 'a', 'e', 'i', 'o', 'u', 'y' };
    for (std::size_t i = 0; i < 10; ++i)
    {
        auto randomVowel = singleRandomSample(vowels.begin(), vowels.end(), rng);
        std::cout << "Random vowel: " << randomVowel << '\n';
    }
}

This function creates a temporary container out to which a single element is added, then returns that element by value. It uses an std::array because I know I only need room for a single element, although if I decided it was important to be able to use this with non-default-constructible types I could switch to a std::vector and a std::back_inserter.
Is it correct to call std::sample using rng as an argument directly, or should I be using std::forward(rng)?
It feels slightly clunky to have an entire temporary container just to store a single value that's immediately returned. Is there another way this functionality could be implemented?

A pointer is an iterator.
template <typename InputIterator, typename URBG>
auto singleRandomSample(InputIterator first, InputIterator last, URBG&& rng)
{
    using value_type = typename std::iterator_traits<InputIterator>::value_type;

    auto result = value_type{};

    std::sample(first, last, &result, 1, std::forward<URBG>(rng));

    return result;
}

Or, with a better, C++20 interface:
template <std::input_iterator I, std::sentinel_for<I> S, typename URBG>
    requires std::uniform_random_bit_generator<std::remove_reference_t<URBG>>
auto singleRandomSample(I first, S last, URBG&& rng)
{
    auto result = std::iter_value_t<I>{};

    std::ranges::sample(first, last, &result, 1, std::forward<URBG>(rng));

    return result;
}

template <std::input_range R, typename URBG>
    requires std::uniform_random_bit_generator<std::remove_reference_t<URBG>>
auto singleRandomSample(R&& r, URBG&& rng)
{
    auto result = std::ranges::range_value_t<R>{};

    std::ranges::sample(r, &result, 1, std::forward<URBG>(rng));

    return result;
}

This requires the value type of the range to be default-constructible, but you were already counting on that with the array solution.
If you want a solution that does not require default construction, you could probably do something like using an optional type—like std::optional, or std::variant with std::monostate—and a custom output iterator that does an emplace into it.


Ruby BST code for insertion implementation After some help in understanding difference why direct assignment with setter methods don't work, here is my code for a simple BST in ruby. Would appreciate your reviews and suggestions to refactor the code.

class Node
  attr_accessor :value, :left_child, :right_child

  def initialize (value)
    @value = value
    @left_child = nil
    @right_child = nil
  end
end

class BST
  attr_accessor :root

  def initialize
    @root = nil
  end

  def insert(value, node)

    if self.root == nil
      self.root = Node.new(value)
      return self.root
    end

    return self.root if self.root.value == value

    if node.value > value
      p node
      if node.left_child == nil
        node.left_child = Node.new(value)
        return node
      else
        insert(value, node.left_child)
      end

    else

      if node.right_child == nil
        node.right_child = Node.new(value)
        return node
      else
        insert(value, node.right_child)
      end
    end
  end

end

I'll be writing this review assuming that BST stands for Binary Search Tree, and that you're only concerned with constructing the tree, not searching through it. With that in mind, let's start:

Node class

First, for the easy part: in your definition of Node#initialize, you've got a space between the method name and the parenthesis initialize (. While ruby read that fine (it'll even work if you take out the parenthesis all together), it's considered best practice to put the parenthesis right up against the method name, so def initialize(value).

Different methods of dealing with the children

Also, you do not need to initialize @left_child and @right_child to nil. Instance variables do not need to be initialized. If you try and manipulate an uninitialized instance variable, it will behave as if it is set to nil. So, you can simply exclude @left_child and @right_child from your Node#initialize method.

However, if you wanted to allow them to be passed in optionally, you can use arguments or parameters with default values. Here's an example of parameters with default values:

def initialize(value, left_child = nil, right_child = nil)
  @value = value
  @left_child = left_child
  @right_child = right_child
end

and here's and example with hash arguments with defaults:

def initialize(value, left_child: nil, right_child: nil)
  @value = value
  @left_child = left_child
  @right_child = right_child
end

I personally prefer the second, because in that case you could easily pass a right_child without the left_child and vise versa. Otherwise, to pass a right_child, you'd need to pass nil for left_child.

Also, you may want to validate that @left_child and @right_child are both Nodes. In that case, you would want to define attr_readers for those variables and not attr_accessors. You would manually define the accessors like so:

def left_child=(left_child)
  if left_child.is_a? Node
    @left_child = left_child
  else
    # Some handling for invalid left children, e.g.
    throw "Invalid left child: #{left_child}"
  end
end

and the same for @right_child. You could even do it for value too! Or, if you wanted to get fancier, you could define a private validate_node method to avoid duplication in left_node= and right_node=:

def left_child=(left_child)
  @left_child = validate_node(left_child)
end

def right_child=(right_child)
  @right_child = validate_node(right_child)
end

private

def validate_node(node)
  if node.is_a? Node
    node
  else
    throw "You've passed an invalid node: #{node}"
  end
end

In case you didn't know, private methods are methods that (without some ruby magic) cannot be called outside of that class. They are private to that class.

  Note: (Partially note to self) This probably isn't the fully best way to do this, the validation method should validate behavior rather than class. I should write more about that.

I think that's all for the Node class, so let's move onward!

BST Class

First off, I think that BST isn't that great of a name for this class. I'd go with Tree, because that is what it stores.

Anyways, first thing first: I'd make it possible to pass root to the initializer by making it an argument with a default value:

def initialize(root = nil)
  @root = root
end

Next thing's next: The #insert method!

I notice that you're checking if self.root is nil. In ruby, there's a slightly faster (IIRC) and much more ruby way of doing this: self.root.nil?. It's a neat, built-in nil check. In addition, there's no reason to modify @root using its accessor, you can actually just modify it directly.

Also, I noticed that wherever you return a value, you're either returning the root, or the node that was passed in. I also note that you're always setting the node that was passed in as the root. So, you're actually always comparing to root. With that in mind, here are some little bits of cleanup (incomplete, I'll come back and finish it):

def insert(value, node)
  # When this occurs, it will set @root.value == node.value
  @root = Node.new(value) if @root.nil?

  return @root if @root.value == value

  if node.value > value
    if node.left_child.nil?
      node.left_child = Node.new(value)
    else
      insert(value, node.left_child)
    end
  else
    if node.right_child.nil?
      node.right_child = Node.new(value)
    else
      insert(value, node.right_child)
    end
  end
  return node
end

Other notes

Here's an interesting example of how someone else implemented BSTs in ruby


Project Euler 6: Difference between sum of squares and square of sum I've created a (very) simple solution for Project Euler problem 6:

  Project Euler Problem 6: Sum square difference

  The sum of the squares of the first ten natural numbers is,

  $$ 1^2 + 2^2 + ... + 10^2 = 385 $$

  The square of the sum of the first ten natural numbers is,

  $$ (1 + 2 + ... + 10)^2 = 55^2 = 3025 $$

  Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is \$3025 − 385 = 2640\$.

  Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution:

   \$25164150\$

To solve this in F# was pretty simple: I simply declared a function square which would multiply an x by itself, then a function which would run through a list of numbers and add the square of the sum of them, and subtract the sum of the squares of each.

let square x =
    x * x

let calcDiffSquareSumFromSumSquares list =
    (list |> List.sum |> square) - (list |> List.sumBy square)

printfn "Solution to Project Euler 6: %i" (calcDiffSquareSumFromSumSquares [ 1 .. 100 ])

On this one, I'm particularly curious if there's a functional way to run through the list only once, calculate the total sum, and calculate the squares of sums so that I wouldn't need to use two sum methods.

Looks good to me.

Couple of things to consider though:

You could split out two functions, squareOfSum and sumOfSquares. I think that would make it a little easier to read.
You could make the functions more general by using Seq.sum/Sum.sumBy instead of List.sum/List.sumBy.
While you could use fold, as joranvar mentioned, I think this would make the program much less clear and I would not recommend it (except as an exercise for learning about folds).
There is another way to attack the problem, by using the two identities

\begin{align}
1 + 2 + 3 + \cdots + n &= \frac{n(n + 1)}{2}, \quad \text{and} \\
1^2 + 2^2 + 3^2 + \cdots + n^2 &= \frac{n(n+1)(2n+1)}{6}.
\end{align}


Find next consecutive prime and find nth prime Code review for best practices, optimizations, bug detection etc. Also please verify my complexity as mentioned within the function comments.

/**
 * Util class with 2 functions,
 * 1. find the next consecutive prime
 * 2. find the nth prime.
 */
public class PrimeUtil {

    private PrimeUtil() {}

    private static List<Integer> findAllPrimes(int upperBound) {
        assert upperBound > 0;

        final List<Integer> primeList = new ArrayList<Integer>();
        int squareRoot = (int) Math.sqrt(upperBound);

        boolean[] nonPrime = new boolean[upperBound + 1];

        for (int m = 2; m <= squareRoot; m++) {
            if (!nonPrime[m]) {
                primeList.add(m);
                for (int k = m * m; k <= upperBound; k += m)
                    nonPrime[k] = true;
            }
        }

        for (int m = squareRoot; m <= upperBound; m++) {
            if (!nonPrime[m]) {
                primeList.add(m);
            }
        }

        return primeList;
    }

    /**
     * Returns the next / consecutive prime number of input number.
     *
     * Complexity: O (m * n) where m is number of primes till the input number, n is the difference between (to be found prime - input number)
     *
     * @param number The number whose next prime should be returned
     * @return        The next / consecutive prime number of input prime.
     */
    public static int nextPrime (int number) {
        if (number <= 0) {
            throw new IllegalArgumentException("The value of n is " + number + ". It should be greater than 0");
        }

        int nextNum = number + 1;
        boolean notPrime = true;
        final List<Integer> primes = findAllPrimes(number);

        while (notPrime) {

            notPrime = false;
            for (int i : primes) {
                if (nextNum % i == 0) {
                    notPrime = true;
                }
            }
            if (notPrime) {
                nextNum++;
            }
        }

        return nextNum;
    }

    /**
     * Returns the nth prime number.
     *
     * Complexity: O(n * m) where n is the prime number, and m is number of primes till the n.
     *
     * @param n     the nth prime number to be found.
     * @return      the nth prime number
     */
    public static int nthPrime(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("The value of n is " + n + ". It should be greater than 0");
        }

        final List<Integer> primes = new ArrayList<Integer>();
        int number = 2;

        while (primes.size() < n) {
            boolean notPrime = false;
            for (int i : primes) {
                if (number % i == 0) {
                    notPrime = true;
                }
            }
            // if you are a prime.
            if (!notPrime) {
                primes.add(number);
            }
            number++;
        }

        return primes.get(primes.size() - 1);
    }

    public static void main(String[] args) {
        System.out.println("Expected 101, Actual: " + nextPrime(100));
        System.out.println("Expected 17, Actual: " + nextPrime(15));

        System.out.println("Expected 7, Actual: " + nthPrime(4));
        System.out.println("Expected 29, Actual: " + nthPrime(10));
    }
}

This question is very similar to the Project Euler #7 challenge. This was asked recently: Suggestions for improvement on Project Euler #7. I answered that question there, and a lot of my suggestions there will follow through here. I also suggested an object-oriented class that will significantly improve the performance of this problem....

Your solution is very different, but similar issues can be found...

Some basic 'hygiene':

double-negative logic is hard to read. if (!nonprime[m]) should be if (prime[m]). If you cannot get the booleab values to be right (Arrays.fill(prime, true)) then you should revert to constants (private static final boolean PRIME = false;) and == comparisons: if (primeflag[m] == PRIME)
you also do double-negative logic in the nextPrime() method: boolean notPrime = true; and if (notPrime). This should be something like if (!prime) ....

First though, you actually have two very different solutions for 'find nth prime' and 'find primes less than x'. Your find nth prime algorithm is very slow. It does not use the Sieve of Eratosthenes at all. It is a 'naive' and slow mechanism for checking every value against all primes. There is a way to estimate the value of the nth prime, and you should use that, combined with the mechanism for calculating primes less than the estimate. This is illustrated in that other answer (reference Wikipedia)

:

you have blindly followed the wikipedia recommended algorithm/suggestion of doing an incremental progression on a sieve of numbers.
if you make 2 a special case, then you only actually need to process every second value (m += 2 instead of m++).
you do not cache previously computed prime numbers, as a result, calling your methods multiple times will require many re-computations of prime values.
Integer.MAX_VALUE happens to be a prime.... what happens if you run: nextPrime(Integer.MAX_VALUE - 1); ?


Project Euler Q2 - Sum of even Fibonacci numbers I'm very new at F#, and am using Project Euler to help me learn. Question #2 kept me going for a while, as my initial attempt at an answer was very slow and inelegant. Then I learnt about Seq.unfold, and a whole new vista unfolded in front of me!

The problem statement is as follows (source):

  Each new term in the Fibonacci sequence is generated by adding the
  previous two terms. By starting with 1 and 2, the first 10 terms will
  be:

  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

  By considering the terms in the Fibonacci sequence whose values do not
  exceed four million, find the sum of the even-valued terms.

Please can you comment on this code. Bear in mind I'm very new at this, so I may be doing it completely wrong!

let fibEvenSum max =
  let rec fibEven n =
    match n with
    | 0 -> 0
    | 1 -> 2
    | n -> 4 * (fibEven (n - 1)) + (fibEven (n - 2))
  1 |> Seq.unfold (fun n -> Some(fibEven n, n+1))
    |> Seq.takeWhile (fun n -> n < max)
    |> Seq.sum

If I run it like this, I get the right answer:

sumOfEvenFibs 4000000I

Is there a better way to do it?

Daniel's solution to another question applies here equally.

On another question, I showed that the sum is equal to

$$
\frac{F_{3n+2} - 1}{2}
$$

where \$3n\$ is the largest multiple of \$3\$ not to exceed the maximum.

If you wish to use this for asymptotic improvements, note that since the Fibonacci sequence has a closed-form solution, you can use it to find an approximate bound for \$3n\$, and then use fast exact mechanisms to find the exact value of \$F_{3n+2}\$.

$$
F_{3n} \approx \phi^{3n}/\sqrt 5 \\
3n \approx \log_\phi \left(F_{3n} \sqrt 5 \right)
$$

Finding a lower bound for \$n\$ thus takes very little time.

Personally I'd stick with the simple, slower solution, but it's interesting to note how far you can get with a bit of mathematical analysis.


Rot13 app - How to tidy up code? I made a program that lets the user input text into a text box.
The user can choose a number to rotate each alphabetical character by that number,
and the output box will diplay the converted text.
Here is how it runs:

Among the code is
#            if event.key == pygame.K_RETURN:
#                print('\n'.join([''.join(row) for row in rot_box.text])+'\n--------------------')

If you remove the hashtags, the converted text will be printed whenever you press Enter.
Here is my entire code:
import pygame
pygame.font.init()

wn = pygame.display.set_mode((600, 600))
font = pygame.font.Font(None, 32)

class TextBox():
    def __init__(self, x, y, w, h, title='Text Box', color=(0, 0, 0), default=''):
        self.input_box = pygame.Rect(x, y, w, h)
        self.w = w
        self.h = h
        self.color_inactive = color
        self.color_active = pygame.Color('purple')
        self.color = self.color_inactive
        self.default = default
        self.text = ['']
        self.active = False
        self.title = title

    def draw(self):
        title = font.render(self.title, True, self.color)
        wn.blit(title, (self.input_box.x+5, self.input_box.y-self.h))
        txts = [font.render(''.join(t), True, self.color) for t in self.text]
        width = max(self.w, max(txts, key=lambda x:x.get_width()).get_width()+10)
        height = self.h * len(txts)
        self.input_box.w = width
        self.input_box.h = height
        if len(txts) == 1 and txts[0].get_width() == 1:
            wn.blit(font.render(self.default, True, self.color), (self.input_box.x+5, self.input_box.y+5))
        else:
            for i, txt in enumerate(txts):
                wn.blit(txt, (self.input_box.x+5, self.input_box.y+5+i*self.h))
        pygame.draw.rect(wn, self.color, self.input_box, 2)

    def check_status(self, pos):
        if self.input_box.collidepoint(pos):
            self.active = not self.active
        else:
            self.active = False
        self.color = self.color_active if self.active else self.color_inactive

    def type(self, event):
        if self.active:
            if event.key == pygame.K_RETURN:
                self.text.append('')
            elif event.key == pygame.K_BACKSPACE:
                if self.text[-1]:
                    self.text[-1] = self.text[-1][:-1]
                else:
                    if len(self.text) > 1:
                        self.text = self.text[:-1]
            else:
                self.text[-1] += event.unicode

def rot(alp, num):
    while num >= 26:
        num -= 26
    if alp in 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ':
        n = ord(alp) + num
        if n > 122 or 97 > n > 90:
            n -= 26
        alp = chr(n)
    return alp

box = TextBox(110, 60, 140, 32, 'Input Text')
rot_num = TextBox(10, 60, 50, 32, 'Rot', default='0')
rot_box = TextBox(110, 300, 140, 32, 'Output Text')

while True:
    rt = int(rot_num.text[0]) if rot_num.text[0] else 0
    rot_box.text = [[rot(char, rt) for char in row] for row in box.text]
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
        if event.type == pygame.MOUSEBUTTONDOWN:
            box.check_status(event.pos)
            rot_num.check_status(event.pos)
        if event.type == pygame.KEYDOWN:
            box.type(event)
            if (event.unicode.isdigit() or event.key == pygame.K_BACKSPACE) and len(rot_num.text[0]) < 6 or event.key == pygame.K_BACKSPACE:
                rot_num.type(event)
#            if event.key == pygame.K_RETURN:
#                print('\n'.join([''.join(row) for row in rot_box.text])+'\n--------------------')

    wn.fill((255, 255, 200))
    box.draw()
    rot_num.draw()
    rot_box.draw()
    pygame.display.flip()

Can you show me how to clean up my messy code?
Can also you point me at the parts of my code that should've been in a class or function, and the parts that shouldn't have been?

Your ROT algorithm is slightly wrong. The real ROT returns The alphabet rotated in the corresponding case. But in yours, even if you give Uppercase(TUVWXYZ), it returns lowercase for large rotations. That is not exact ROT.
This can be seen from this screenshot
This may be helpful:  https://www.geeksforgeeks.org/rot13-cipher/. Here instead of chr() and ord() Dictionaries are used which is very efficient and less error prone.


Simple JavaScript canvas game Here is a link to the code on JSFiddle.

This is my first attempt at playing with canvas.  Before I move on doing anything else, it would be nice to have insight from somebody who knows canvas and JavaScript better than me.

Things I am looking for:

Ways to optimize animation
Ways to optimize the lazer drawing (I know I need to clear the lazers from the array every once in awhile when they are no longer within the drawing area, just haven't gotten around to it yet.)
Ways to optimize the code in general and have good code re-use.

HTML:

<canvas id="world" style="height: 300px; width: 300px;" />

JavaScript:

console.log("Game starting...");

var ship = new Object();
ship.name = "Enterprise";
ship.x = 0;
ship.y = 0;
ship.width = 50;
ship.left = false;
ship.right = false;
ship.up = false;
ship.down = false;
ship.fire = false;
ship.firerate = 5;
ship.cfirerate = 0;
var lazers = new Array();

var world = document.getElementById('world');
var cxt = world.getContext("2d");

$(document).bind('keydown', function(e) {
    if(e.keyCode==37){
        ship.left = true;
    }
    if(e.keyCode==38){
        ship.up = true;
    }
    if(e.keyCode==39){
        ship.right = true;
    }
    if(e.keyCode==40){
        ship.down = true;
    }
    if(e.keyCode==90){ //Z
        console.log("pew pew");
        ship.fire = true;
    }
});
$(document).bind('keyup', function(e) {
    if(e.keyCode==37){
        ship.left = false;
    }
    if(e.keyCode==38){
        ship.up = false;
    }
    if(e.keyCode==39){
        ship.right = false;
    }
    if(e.keyCode==40){
        ship.down = false;
    }
    if(e.keyCode==90){ //Z
        ship.fire = false;
    }
});

function createLazer(type) {
if (type == 1) {//LEFT LAZER
    cxt.beginPath();
    cxt.moveTo(125+ship.x,140+ship.y);
    cxt.lineTo(125+ship.x,130+ship.y);
    var l = new Object();
    l.type = type;
    l.x = ship.x;
    l.y = ship.y;
    return l;
}
else if (type == 2) {//RIGHT LAZER
    cxt.beginPath();
    cxt.moveTo(125+ship.x+ship.width,140+ship.y);
    cxt.lineTo(125+ship.x+ship.width,130+ship.y);
    var l = new Object();
    l.type = type;
    l.x = ship.x;
    l.y = ship.y;
    return l;
}
}

function drawWorld() {
cxt.fillStyle="#808080";
cxt.fillRect(0,0,300,300);
}
function drawLazers() {
for (x = 0; x < lazers.length; x++)
{
    cxt.beginPath();
    cxt.strokeStyle="#FF0000";
    if (lazers[x].type == 1) {
        cxt.moveTo(125+lazers[x].x,140+lazers[x].y);
        cxt.lineTo(125+lazers[x].x,120+lazers[x].y);
    }
    else if (lazers[x].type == 2) {
        cxt.moveTo(125+lazers[x].x+ship.width,140+lazers[x].y);
        cxt.lineTo(125+lazers[x].x+ship.width,120+lazers[x].y);
    }
    cxt.stroke();
    lazers[x].y = lazers[x].y - 6;

    //console.log("drawing lazer" + lazers[x].x + lazers[x].y);
}
}
function drawShip() {
if (ship.left) { ship.x = ship.x -5; }
if (ship.right) { ship.x = ship.x +5; }
if (ship.up) { ship.y = ship.y -5; }
if (ship.down) { ship.y = ship.y +5; }
if (ship.fire) {
    if (ship.cfirerate == 0) {
        lazers.push(createLazer(1));
        lazers.push(createLazer(2));
        ship.cfirerate = ship.firerate;
    }
}
if (ship.cfirerate != 0) {
    ship.cfirerate = ship.cfirerate - 1;
}

cxt.beginPath();
cxt.strokeStyle="#000000";
cxt.moveTo(125+ship.x,140+ship.y);
cxt.lineTo(150+ship.x,120+ship.y);
cxt.lineTo(175+ship.x,140+ship.y);
cxt.stroke();
}
function clear() {
cxt.clearRect(0, 0, 300, 300);
}

function gameLoop() {
drawWorld();
drawShip();
drawLazers();
}

setInterval(function() {
clear();
gameLoop();
}, 30);

Cool program!

I have put my review of the code on JsFiddle.

A basic synopsis of what I thought to improve:

Everything constant about the map, ship, lasers, and keycodes is all in one place to improve scalability.
I used object literals and array literals instead of new Object() and new Array() because using them is shorter and and makes things easier to manipulate.
The keydown and keyup event handlers were refactored to eliminate duplicate code.
The createLaser and drawLasers methods were refactored. I removed some drawing code from createLaser because it didn't seem to do anything, and I removed calculations in drawLasers that were redundant with createLaser.
I added code in drawLasers to remove lasers from the array that are no longer on the map. I also removed or rearranged drawing code that didn't do anything or was being called too many times. I removed the clear() function because it didn't seem to do anything.
I changed statements of form x = x + y, x = x - y and x = x + 1 to x += y, x -= y, and x++, respectively.
I changed one instance of the form array.push(x); array.push(y); to array.push(x,y);
I renamed lazer to laser because I kept typing laser and it caused bugs that here hard to find. You can rename it back, if you are accustomed to typing lazer.

Here is a copy of the revised code:

console.log("Game starting...");

var ship = {
    name: "Enterprise",
    x: 125,
    y: 120,
    width: 50,
    height: 40,
    left: false,
    right: false,
    up: false,
    down: false,
    fire: false,
    firerate: 5,
    cfirerate: 0,
    moveInterval: 5,
    color: "#000000"
},
    map = {
        width: 300,
        height: 300,
        color: "#808080",
        drawInterval: 30
    },
    laser = {
        height: 20,
        moveInterval: 6,
        color: "#FF0000"
    },
    lasers = [],
    keys = {
        left: 37,
        up: 38,
        right: 39,
        down: 40,
        fire: 90 //Z
    },
    getKey = function(key) {
        for (var i in keys) {
            if (keys.hasOwnProperty(i)) {
                if (keys[i] === key) {
                    return i
                };
            }
        }
    },
    eventValues = {
        keyup: false,
        keydown: true
    },
    types = {
        right: 1,
        left: 2
    };

var world = document.getElementById('world');
var cxt = world.getContext("2d");

$(document).bind('keydown keyup', function(e) {
    var key = getKey(e.keyCode);
    ship[key] = eventValues[e.type];
});

function createLaser(type) {
    var x = ship.x;
    if (type === types.right) {
        x += ship.width;
    }
    var y = laser.height + ship.y;
    return {
        type: type,
        x: x,
        y: y,
    }
}

function drawWorld() {
    cxt.fillStyle = map.color;
    cxt.fillRect(0, 0, map.width, map.height);
}

function drawLasers() {
    cxt.beginPath();
    cxt.strokeStyle = laser.color;
    for (var i = 0; i < lasers.length; i++) {
        var lsr = lasers[i];
        if (lsr.y < -laser.height) {
            lasers.splice(i, 1);
            continue;
        }
        cxt.moveTo(lsr.x, lsr.y);
        cxt.lineTo(lsr.x, lsr.y - laser.height);
        cxt.stroke();
        lsr.y -= laser.moveInterval;
    }
}

function drawShip() {
    if (ship.left) {
        ship.x -= ship.moveInterval;
    }
    if (ship.right) {
        ship.x += ship.moveInterval;
    }
    if (ship.up) {
        ship.y -= ship.moveInterval;
    }
    if (ship.down) {
        ship.y += ship.moveInterval;
    }
    if (ship.fire) {
        if (ship.cfirerate === 0) {
            lasers.push(createLaser(types.left), createLaser(types.right));
            ship.cfirerate = ship.firerate;
        }
    }
    if (ship.cfirerate !== 0) {
        ship.cfirerate--;
    }

    cxt.beginPath();
    cxt.strokeStyle = ship.color;
    cxt.moveTo(ship.x, ship.y + (ship.height / 2));
    cxt.lineTo(ship.x + (ship.width / 2), ship.y);
    cxt.lineTo(ship.x + ship.width, ship.y + (ship.height / 2));
    cxt.stroke();
}

function gameLoop() {
    drawWorld();
    drawShip();
    drawLasers();
}

setInterval(gameLoop, map.drawInterval)

If you see anything that you think is weird, or have a question about what I did, just ask me about it.


Summing values in a vector using threads This is my very first program that using threads. I use C++11 standard threads and I run it on Linux.

The program creates two threads that sums all the elements in a vector together. The first created thread sums the left half of the vector and the other thread sums the right part of the vector.

The main thread runs until both are done, adds the two sums together and then print the sum.

#include <iostream>
#include <vector>
#include <thread>

void
adder( const std::vector<int> & v, int begin, int end, int & result)
{
  for( ; begin < end; ++begin )
    {
      result = result + v.at( begin );
    }
}

int
main()
{
  int sum_left  = 0;
  int sum_right = 0;

  std::vector<int> v( 100000000,1); //100 millions
  int v_size = v.size();

  std::thread t1( adder, v, 0,v_size/2 , std::ref(sum_left) );
  std::thread t2( adder, v, v_size/2, v_size, std::ref(sum_right) );

  t1.join();
  t2.join();

  int sum_total = sum_left + sum_right;

  std::cout << sum_total << '\n';

  return 0;
}

Firstly, it's a good first attempt at writing some threaded code. The major sticking point is that you're passing in an int & and returning void. Of course, std::thread will just run some code and won't return you a result. However, within the C++11 threading library, there are a number of things you can use that will allow you to return results, instead of having to use std::ref and reference parameters.

Before tackling that, let's look at the adder function itself. I'm going to go through a sequence of improvements that can be made to it. Firstly, you should try and use the correct type to index into a std::vector:

using size_type = std::vector<int>::size_type;

int adder( const std::vector<int> & v, size_type begin, size_type end)
{
    for( ; begin < end; ++begin )
    {
        result = result + v.at( begin );
    }
}

This is ok, but it could be a lot more generic: What if the values aren't stored in a std::vector? Instead, template this so that it can use anything that supports an iterator concept:

template <typename Iterator>
int adder(Iterator begin, Iterator end)
{
    int result = 0;
    for(auto it = begin; it != end; ++it) {
        result += *it;
    }
    return result;
}

Ok, getting there, but we can still improve this quite a bit: what if we want to sum any kind of numeric type? (Note this will require an #include <iterator>):

template <typename Iterator>
std::iterator_traits<Iterator>::value_type
adder(Iterator begin, Iterator end)
{
    std::iterator_traits<Iterator>::value_type result;
    for(auto it = begin; it != end; ++it) {
        result += *it;
    }
    return result;
}

Ok, so we're not locked into a vector or an int type anymore. However, this pattern of summing up a bunch of values is really common, and there is library functionality that takes care of it for us: std::accumulate (note that this needs an #include <algorithm>):

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type
adder(Iterator begin, Iterator end)
{
    using T = typename std::iterator_traits<Iterator>::value_type;
    return std::accumulate(begin, end, T());
}

Now for the threading part.

The C++11 threading library has a really handy function called std::async. This allows you to run some piece of code in a thread, and retrieve a result from it. It will give you back what is known as a std::future (note that this needs an #include <future>):

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type
parallel_sum(Iterator begin, Iterator end)
{
    using T = typename std::iterator_traits<Iterator>::value_type;
    auto midpoint = begin + std::distance(begin, end) / 2;
    std::future<T> f1 = std::async(std::launch::async, adder<Iterator>, begin, midpoint);
    std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint, end);
    return f1.get() + f2.get();
}

We then use this as follows:

int main()
{
    std::vector<int> v;
    for(int i = 0; i < 100000; ++i) {
        v.push_back(i);
    }
    int total = parallel_sum(v.begin(), v.end());
    std::cout << total << "\n";
}

There's probably too much to absorb here in one go, but I'll break down the main points:

Try and make your functions work with the facilities provided by the standard library. Iterators permeate the container/algorithm side of it - if you can, try and work with iterators instead of directly with containers.
Look for functionality in the standard library that can help you with common tasks, such as std::accumulate.
With threading, if you want to get results back, prefer to use std::async instead of passing parameters by reference to store results.


Adding ID to body tag from variable defined in URL I have written a small PHP script to get a variable from the URL and echo it in the body ID.

An example of the url:

http://www.example.com/?var=123

I have added this to the head of my HTML page:

<?php if (isset($_GET['var'])) {
    $var = $_GET['var'];
} else {
    $var = NULL;
} ?>

The body tag of the HTML page looks like this:

<body class="whatever" <?php if(isset($var)) {echo "id=\"$var\""; } ?>>

The result is a body tag like this when the ?var=123 is added to the URL:

<body class="whatever" id="123">

This is working but I am sure there is a better way to go about it.

One technique is to default the value to NULL:

$var = NULL;
if (isset($_GET['var'])) {
    $var = $_GET['var'];
} ?>

Then when setting the attribute on the tag, isset() doesn't need to be used.

<body class="whatever" <?php if($var) {echo "id=\"$var\""; } ?>>

For a demonstration of this, see this phpFiddle.

Note that it is recommended that PHP not be mixed in with HTML code. For a good explanation, refer to this answer to Should I Include PHP code in HTML or HTML in PHP? on the Software Engineering site.

  Mixing languages is not a good idea. You don't put JavaScript in HTML, or HTML in JavaScript, or JavaScript in PHP, or HTML in Python or Ruby in SQL.1

As is recommended by that post, consider the use of templates:

  What are you probably looking for is called templates. Depending on the framework you use, it may already be available, usually under a form of MVC, where the template is in the view, or you may have to use a third-party template engine, such as Smarty.

  In both cases, the idea remains the same. You have PHP code strictly separated from the template which contains the HTML and a bit of very simplistic logic: simple loops over entities, conditions for conditional displaying of information, etc. When the PHP code is ready, it calls the template engine, passing to it some information. The engine uses a specific template to build the final output (often HTML, but other formats are possible as well) which is then sent to the user.1

1https://softwareengineering.stackexchange.com/a/291839/244085


Object map() / transmute() method I'm somewhat curious on peoples opinion about such a method. I Actually didn't find anything similar in librarys I use on regular bases so far.

This is my implementation:

Object.map = function _map( obj, transform ) {
    if( typeof obj === 'object' && typeof transform === 'function' ) {
        Object.keys( obj ).forEach(function _forEach( key ) {
            (function _mapping( oldkey, transmuted ) {
                if( transmuted && transmuted.length ) {
                    obj[ transmuted[ 0 ] || oldkey ] = transmuted[ 1 ];

                    if( transmuted[ 0 ] && oldkey !== transmuted[ 0 ] ) {
                        delete obj[ oldkey ];
                    }
                }
            }( key, transform.apply( obj, [ key, obj[ key ]] ) ));
        });
    }
};

I normally put it on the Object object and not the prototype. However, usage is like this

var foo = {
    someProp: 5,
    bar: 10,
    moar: 20
};

Object.map( foo, function(key, value) {
    return [ key.toUpperCase(), value*2 ];
});

result:

Object { SOMEPROP=10, BAR=20, MOAR=40}

I most often use it to translate CSS properties (to vendor prefixes). But I don't see people use an approach like this often in ECMAscript. Any thoughts?

First comment, there is no need for the closure inside _forEach which makes the code unnecessarily difficult to read.  More importantly I would argue that the function would be much more useful if did not transform the original object and instead returned a new object.

Object.map = function (obj, mapping) {
    var mapped = {};

    if (typeof obj !== 'object') {
        return mapped;
    }

    if (typeof mapping !== 'function') {
        // We could just return obj but that wouldn't be
        // consistent with the rest of the interface which always returns
        // a new object.
        mapping = function (key, val) {
            return [ key, val ];
        };
    }

    Object.keys( obj ).forEach(function (key) {
        var transmuted = mapping.apply(obj, [ key, value ]);

        if (transmuted && transmuted.length) {
            mapped[ transmuted[0] || key ] = kv[ 1 ];
        }
    });

    return mapped;
};

This is not only less dangerous for widely available object but it also makes the function more flexible by allowing it to be chained or used within an expression:

Object.map(oldCss, function (key, value) {
    // ...
}).doSomethingElse();

At the very least I would have your original function return the passed in object to allow for chaining or use within an expression.


Scala app to transpose columns into rows This is the first application or really any Scala I have every written. So far it functions as I would hope it would. I just found this community and would love some peer review of possible improvements or just tell me flat out what I'm doing wrong.

This code is supposed to read a table of tables then take all of the values from that table transpose the columns into rows and write them all to a master table with three additional columns. So far it does everything except the looping which I just haven't gotten to yet. This question is not about how to do the looping and really only hoping to critique what I have here so far. I did change some variable names and a few things I had to mask.

//how to call
//spark-submit --verbose --deploy-mode cluster --master yarn --class App scala-maven-0.1-SNAPSHOT.jar
import org.apache.spark.sql.{ SQLContext, SparkSession }
import org.apache.spark.sql._
import org.apache.spark.sql.types._
import org.apache.spark.sql.functions._
import java.util.Calendar

//this will call createStuff function for each table_name value in table
//TODO: Add loop and call CreateStuff with values from list returned from stuff_to_run
object App {
  def main(args: Array[String]) {
    //do I have to create the SparkSession value twice or can I pass this into the function?
    val spark = SparkSession.builder().appName("App").enableHiveSupport().getOrCreate()
    val stuff_to_run = spark.sql("select table_name from schema.table").rdd.map(r => r(0)).collect.toList
    println(stuff_to_run)
    CreateStuff("stuff");
  }

  def CreateStuff(stuffName: String): Unit = {
    var tablename = stuffName
    var column_stack = ""
    val spark = SparkSession.builder().appName("App").enableHiveSupport().getOrCreate()
    //is there a better way to get year and month
    val Year = Calendar.getInstance.get(Calendar.YEAR)
    val Month = Calendar.getInstance.get(Calendar.MONTH) + 1
    val twodigitmonth = "%02d".format(Month)
    val yrmnth = Year.toString + twodigitmonth.toString
    //get all of the data from the base table
    val raw_table = spark.sql("select *, '" + tablename + "' as stuffname, '" + yrmnth + "' as yrmnth from schema." + tablename)
    //transpose all columns into rows
    val string_table = raw_table.select(raw_table.columns.map(c => col(c).cast(StringType)): _*)
    //get column besides 3 defined these are the only ones which are not dynamic
    val selectColumns2 = string_table.columns.toSeq.filter(x => (x != "val1" && x != "stuffname" && x != "yrmnth"))
    val columnCount = selectColumns2.size
    //comma and quote
    selectColumns2.foreach { e =>
      column_stack += "'" + e + "', " + e + ", "
    }

    val collist = column_stack.mkString("").dropRight(1)
    import spark.sqlContext.implicits._

    val unPivotDF = string_table.select($"val1", $"stuffname", $"yrmnth",
      expr("stack(" + selectColumns2.size + ", " + collist.dropRight(1) + ") as (fieldname, fieldvalue)"))
    //unPivotDF.show()
    //insert records into combined table
    unPivotDF.createOrReplaceTempView("stuff_temp")
    spark.sql("insert into schema.combined_stuff select * from stuff_temp")
  }
}

Immediately I'd ask if there's any specific style guide that allows
these vastly different names, otherwise I'd suggest following IDE hints
and/or a linter and rename the variables and methods to be more
consistent (e.g. [cC]amelCase for everything).

Also, "stuff" is not a great name for anything ... what stuff are we
talking about?  In fact the first line of CreateStuff already shows
that there's a better name, tableName for the parameter, probably
createTable for the method.  yrmnth is especially bad too, three
vowels saved from yearMonth and in the process made the name
unreadable for the casual observer.

Seems like the spark session is created twice and the comment even says
so - I'd suggest passing the variable into the method, that's fairly
straightforward by either passing it as a parameter, or extending App
with a member variable.

The SQL queries are created by concatenating strings and there's usually
better ways, here probably a query builder.

columnCount is unused, selectColumns2 has 2 as the suffix, even
though there's no 1, that can just be selectColumns.

The loop for columnStack could be in its own method so it's a little
small section that could be tested on its own too, returning what is now
collist, formatColumnsList(columns: Seq[String]): String perhaps.
Again, if a query builder could do all this it would be a bit cleaner
than concatenating strings.

The construction for yrmnth is pretty convoluted for what it does, I'd
suggest finding a more succinct approach, e.g.

val yearMonth = DateTimeFormatter.ofPattern("yyyyMM").format(LocalDateTime.now())

That would require a recent Java for java.time.LocalDateTime and
java.time.format.DateTimeFormatter.  But even without there should be
better ways.  If everything fails the whole section should at least be
in its own method, e.g. formatDate(calendar Calendar): String.

The bottom part of unPivotDF uses a temporary table - is that the best
way to go, or could the data be inserted directly?


Given an unsorted integer array, find the first missing positive integer Here is the problem, any advice about code improvement, more efficient implementation in terms of time complexity, functional bugs, etc. are appreciated.

  Given an unsorted integer array, find the first missing positive
  integer.

  For example,
  Given [1,2,0] return 3,
  and [3,4,-1,1] return 2.

  Your algorithm should run in O(n) time and use constant space.

def firstMissingPositive(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 1
    for i,v in enumerate(nums):
        if v > len(nums):
            nums[i]=-1
        elif v <= 0:
            nums[i]=-1
        else:
            while i+1 != nums[i] and 0<nums[i]<=len(nums):
                #print i, nums[i]-1, nums[i], nums[nums[i]-1]
                v = nums[i]
                nums[i] = nums[v-1]
                nums[v-1] = v
                #nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
            if nums[i] > len(nums) or nums[i] <=0:
                nums[i] = -1
    for i,v in enumerate(nums):
        if nums[i] != i+1:
            return i+1
    return len(nums)+1

if __name__ == "__main__":
    print firstMissingPositive([1,2,0])
    print firstMissingPositive([3,4,-1,1])

PEP8

Python uses underscore as naming separator in function and variable names, see PEP8

Naming

for i,v in enumerate(nums)

It's better to use some obvious names so instead of i,v you should use index, value

Improvements

You've got a right idea on how to solve this, but there are some minor things in your implementation that can be improved.

for i,v in enumerate(nums):
    if v > len(nums):
        nums[i]=-1
    elif v <= 0:
        nums[i]=-1
    else:

this part can be simplified to

if  0 >= value > len(nums):
    continue

Now your while loop can make infinite number of cycles on such list [3,4,3,-1] so you need to handle this, also you don't have to replace items that are <= 0 or items that are >= len(nums) with -1 you can just skip them.

So in the end your code should look like this:

def first_missing_positive(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 1
    for index, value in enumerate(nums):
        if len(nums) < value <= 0:
            continue
        while index + 1 != nums[index] and 0 < nums[index] <= len(nums):
            v = nums[index]
            nums[index], nums[v-1] = nums[v-1], nums[index]
            nums[v-1] = v

            # Don't create infinite loops
            if nums[index] == nums[v-1]:
                break

    for index, value in enumerate(nums, 1):
        if value != index:
            return index
    return len(nums) + 1


Algorithm for motion detection using ultrasonic sensor on Arduino I am using a ultrasonic sensor to detect motion by looking at the variance of the sensor readings, however my algorithm is very prone to give false positives thus erroneously rising a motion event.

Algorithm Background

What I do is send a ping 20 times a second and wait for a pulse to come back using the input capture on arduino. I have a limit of 2 metres because I don't need to detect motion beyond that. Using a modifed version of the NewPing library which has a method check_timer which returns a value greater than 1 if the pulse from the arduino took more than a corresponding wait time for 2 metres and returns 1 if no pulse has been measured yet or 0 if it successfully got a pulse.

The following conditions need to be met to rise a motion event:

If the last measured pulse was a valid pulse (i.e check_timer returns 0) it will save it in an array and wait for
another positive pulse and only then test for the variance of the two
pulses. However if it failed to measure a valid pulse after the first
success it will reset the array.
If a variance greater than or equal to 500 is measured within a time
frame it will rise a motion event.

The code for my algorithm is this:

#include <NewPing.h>

#define TRIGGER_PIN   10 // Arduino pin tied to trigger pin on ping sensor.
#define ECHO_PIN      9 // Arduino pin tied to echo pin on ping sensor.
#define MAX_DISTANCE 200 // Maximum distance we want to ping for (in centimeters). Maximum sensor distance is rated at 400-500cm.

NewPing sonar(TRIGGER_PIN, ECHO_PIN, MAX_DISTANCE); // NewPing setup of pins and maximum distance.

unsigned int pingSpeed = 50; // How frequently are we going to send out a ping (in milliseconds). 50ms would be 20 times a second.
unsigned long pingTimer;     // Holds the next ping time.

unsigned long last = 0;
unsigned int samples = 2;
unsigned int distances[2];
unsigned int sum = 0;

void setup() {
  Serial.begin(9600); // Open serial monitor at 9600 baud to see ping results.
  pingTimer = millis(); // Start now.
}

void loop() {
  // Notice how there's no delays in this sketch to allow you to do other processing in-line while doing distance pings.
  if (millis() >= pingTimer) {   // pingSpeed milliseconds since last ping, do another ping.
    pingTimer += pingSpeed;      // Set the next ping time.
    sonar.ping_timer(echoCheck); // Send out the ping, calls "echoCheck" function every 24uS where you can check the ping status.
  }
  // Do other stuff here, really. Think of it as multi-tasking.
}

void echoCheck() { // Timer2 interrupt calls this function every 24uS where you can check the ping status.
  uint8_t rc = sonar.check_timer();
  if(rc==0) { // This is how you check to see if the ping was received.
    sum = sum + sonar.ping_result;
    distances[--samples] = sonar.ping_result;
    if(samples == 0) {
      float avrg = (float)(sum) / 2.0f; // Get the average of the samples we recorded
      float sum1 = 0;
      for(int i=1;i>-1;--i) {
        sum1 = sum1 + pow((distances[i] - avrg),2);
      }
      if((sum1 / 2.0f) >= 500.0f) { // If the variance of the samples is greater than or equal to 500
        unsigned long now = millis();
        if(now-last <= 250) { // To filter out random false positives we want two positves within this time frame
          Serial.print("motion event, variance is ");
          Serial.println(sum1 / 2.0f);
        }
        last = now;
      }
      sum = 0;
      samples = 2;
    }
  }else if(rc>1) { // Was it a faulty reading (e.g it exceeded the maximum waiting time)?
    sum = 0;
    samples = 2;
  }
}

My code works but is very unreliable. How can I improve this algorithm?

(EDIT: FYI the sensor I am refering to is a cheap HC - SR04 Ultrasonic Ranging Module.)

Late or spurious echoes
One thing that can happen is that during one ping interval of 50ms you can get echoes from objects up to 8.5m away (0.05[s] *354[m/s] / 2 ). If the object is a little further than that, say 9m, you will get the echo early during the next ping period instead.
As you can guess, this would be bad, it would wrongly appear as being a close echo while it in fact is distant. I'm not familiar with the strength of the ultrasonic on your chip; 8.5m may be out of range in which case this isn't the problem. But if it isn't then your library should send each ping request with a different frequency and check the frequency of the echo to know if you got the right echo, it should also check the amplitude of the echo for feasibility. Again I don't know if your library does any of this but you should check. Otherwise this might be causing your troubles. If 8.5m is just on the edge of the range it is conceivable that some times you get the echo and some times you don't.
Filtering
If you can rule out the above and you're certain your implementation is not at fault, then you can simply assume that it's a transient at work. They happen when dealing with sensors, and sound is finicky that way with echoes and everything.
Best way to deal with transients is to use some kind of filtering. Median might work well for you and I see that NewPing has a "ping_median" function, try this with a filter size of maybe 5 or thereabouts see if that helps.
Variance
Using two samples to estimate any kind of variance is way too little, the result is not in any way reliable. You are also very sensitive to transients and errors are you are calculating the square of the values. I would suggest another approach.
Another approach
If you want to detect movement you want to detect changes in the echo delay. So what you do is setup your timer to consistently ping at a fixed rate then keep a low pass filtered running average of the echo delay and look at the differential of this (the rate of change).
Some pseudocode:
float g = 0.9f
float avg_time = max_time
float avg_dt = 0.0f
float dt_hysteresis = 0.01f
for each 50ms
   if no echo for 10 iterations
      avg_time = max_time
      continue

   float echo_time = sensor.read()

   if avg_time == max_time
       avg_time = echo_time
       avg_dt = 0.0f
   else
       float prev_avg_time = avg_time;
       avg_time = avg_time * g + (1.0f - g) * echo_time
       avg_dt = avg_dt * g + (1.0f - g) * (avg_echo_time - prev_avg_time);

   if avg_dt < -dt_hysteresis
       // Some one approaching
   else if avg_dt > +dt_hysteresis
       // Some one leaving
end for

Explanation
g is a filter coefficient between 0 and 1.0, the higher it is the more "inert" your filter will be. It will be slower to react but be highly resistant to noise. If g is low the filter will react quickly but also more susceptible to noise, to put it simply. You can think of it as a low-pass filter where g implicitly controls the cut-off frequency. Normal values are in the range 0.7 to 0.95.
Every 50 ms you send out a ping and look for the echo. If you don't get an echo for 10 iterations or so, simply reset the avg_time variable so that you can start fresh the next time you get an echo and not be affected by what happened to be stored there since the last echo.
If you get an echo you low pass filter it with avg_time = avg_time * g + (1.0f - g) * echo_time and then look at the lowpass filtered change in the lowpass filtered time value avg_dt = avg_dt * g + (1.0 - g) * (avg_echo_time - prev_avg_time). If this change is larger than +- the hysteresis threshold dt_hysteresis you then deduce that some one is approaching or moving away from the sensor. You can also consider looking directly at avg_echo_time - prev_avg_time the extra lowpass filtering is simply to get rid of noise which is always present when we differentiate a real signal.
Hope this was of some help :s


How thread safe is this class? So the way I understand this code I wrote, it is thread safe, as long as the retrievers and depositors are thread safe. The only bad state I could see occurring is that a thread is using a retriever as a method local while another thread calls RefreshDependencies(), which would mean the thread with it as a method local would continue to use it even though it wasn't one of the current depositors/retrievers, but that one should be cleaned up when the method local using it exited as there would be no root anymore.

also open to any other notes on the code.

public static class DependencyContainer
{
    private const string DEPENDENCIES_LOCATION_APP_SETTINGS_KEY = "DependenciesLocation";

    private static object _lockDependenciesManagement;
    private static string _dependenciesLocation;

    public static IEnumerable<IEntryRetriever> Retrievers { get; private set; }
    public static IEnumerable<IEntryDepositor> Depositors { get; private set; }

    static DependencyContainer()
    {
        _lockDependenciesManagement = new object();
        string dependenciesLocation = ConfigurationManager.AppSettings[DEPENDENCIES_LOCATION_APP_SETTINGS_KEY] ?? typeof(DependencyContainer).Assembly.CodeBase.Replace(@"file:///", "");
        SetDependenciesLocation(dependenciesLocation);
        RefreshDependencies();
    }

    public static string GetDependenciesLocation()
    {
        lock (_lockDependenciesManagement)
        {
            return _dependenciesLocation;
        }
    }

    public static void SetDependenciesLocation(string newDependenciesLocation)
    {
        lock (_lockDependenciesManagement)
        {
            _dependenciesLocation = newDependenciesLocation;
        }
    }

    public static void RefreshDependencies()
    {
        lock (_lockDependenciesManagement)
        {
            // compose/load dependencies in here for writing and retrieving blog entries
        }
    }
}

First item I see is:

private static object _lockDependenciesManagement;

...should be:

private static readonly object _lockDependenciesManagement;

I don't see any reason this should/would change.

With the possibility of having Retrievers overwritten while being used, you should return a copy of the collection instead:

//    fields that could be altered while in use if made public
static IEnumerable<IEntryRetriever> _retrievers { get; private set; }
static IEnumerable<IEntryDepositor> _depositors { get; private set; }

public static IEnumerable<IEntryRetriever> Retrievers
{
    get
    {
        //    return copy of _retrievers
        lock (_lockDependenciesManagement)
        { return _retrievers.ToList(); }
    }
}

Your consumers can now manipulate work from it's own copy of the _retrievers collection. Handle _depositors in the same manner ...I think these steps will make the collections safer to use.


Runtime compiler for getting/setting runtime property values I've been playing about with runtime compilation to allow me to get/set runtime property values in C#, and so far I have come up with a class.

This allows me to write code like the following which works well and is much faster than standard reflection:

TypeWrapper wrapper = new TypeWrapper(target);
wrapper.Set("Value", "abc");
return (string)wrapper.Get("Value");

What I'm wondering is whether there is a way to make this even faster. I could go into metaprogramming and use Reflection.Emit,  but that adds a vastly increased order of complexity for other developers to follow.

Is there something obvious you can see?

Here's the current benchmarks using Benchmark.NET:

Total time: 00:01:47 (107.64 sec)

// * Summary *

BenchmarkDotNet=v0.9.4.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz, ProcessorCount=12
Frequency=3117484 ticks, Resolution=320.7715 ns, Timer=TSC
HostCLR=MS.NET 4.0.30319.42000, Arch=32-bit RELEASE
JitModules=clrjit-v4.6.1063.1

                     Method |      Median |     StdDev | Scaled |
--------------------------- |------------ |----------- |------- |
               1. Static C# |   2.5401 ns |  0.6457 ns |   1.00 |
              2. Dynamic C# |  35.1664 ns |  0.4643 ns |  13.84 |
            3. PropertyInfo | 430.8785 ns |  6.4399 ns | 169.63 |
      4. PropertyDescriptor | 920.3483 ns | 59.1531 ns | 362.32 |
             5. TypeWrapper | 117.0505 ns |  1.6790 ns |  46.08 |

// ***** BenchmarkRunner: End *****

1. Static C#: 2.54 ns
2. Dynamic C#: 35.17 ns
3. PropertyInfo: 430.88 ns
4. PropertyDescriptor: 920.35 ns
5. TypeWrapper: 117.05 ns

And the class itself:

public class TypeWrapper
{
    private readonly dynamic dyn;
    private readonly Dictionary<string, CallSite<Action<CallSite, object, object>>> setters
        = new Dictionary<string, CallSite<Action<CallSite, object, object>>>();

    private readonly Dictionary<string, CallSite<Func<CallSite, object, object>>> getters
        = new Dictionary<string, CallSite<Func<CallSite, object, object>>>();

    public TypeWrapper(object d)
    {
        this.dyn = d;
        Type type = d.GetType();
        foreach (var p in type.GetProperties(BindingFlags.Instance | BindingFlags.Public))
        {
            string name = p.Name;
            CallSite<Action<CallSite, object, object>> set = CallSite<Action<CallSite, object, object>>.Create(
            Microsoft.CSharp.RuntimeBinder.Binder.SetMember(
                CSharpBinderFlags.None,
                name,
                type,
                new[] { CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null) ,
                        CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null) }));

            this.setters.Add(name, set);

            CallSite<Func<CallSite, object, object>> get = CallSite<Func<CallSite, object, object>>.Create(
            Microsoft.CSharp.RuntimeBinder.Binder.GetMember(
                CSharpBinderFlags.None,
                name,
                type,
                new[] { CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null) }));

            this.getters.Add(name, get);
        }
    }

    public void Set(string name, object value)
    {
        var set = this.setters[name];
        set.Target(set, this.dyn, value);
    }

    public object Get(string name)
    {
        var get = this.getters[name];
        return get.Target(get, this.dyn);
    }
}

First, a trivial optimization: there is no reason for dyn to be dynamic: all it does is to make the Target invocation dynamic, which here only makes it slower.

On my computer, this makes Get/Set about 25 % faster.

Another possibility is to use Expression instead of CallSite. Since Expression is not as dynamic as dynamic, it can compile to simpler code. For me, using this results in 50 % better speed than your code after applying the previous optimization.

The code:

public class TypeWrapper
{
    private readonly object dyn;
    private readonly Dictionary<string, Action<object, object>> setters
        = new Dictionary<string, Action<object, object>>();

    private readonly Dictionary<string, Func<object, object>> getters
        = new Dictionary<string, Func<object, object>>();

    public TypeWrapper(object d)
    {
        this.dyn = d;
        Type type = d.GetType();
        foreach (var p in type.GetProperties(BindingFlags.Instance | BindingFlags.Public))
        {
            string name = p.Name;

            var wrappedObjectParameter = Expression.Parameter(typeof(object));
            var valueParameter = Expression.Parameter(typeof(object));

            var setExpression = Expression.Lambda<Action<object, object>>(
                Expression.Assign(
                    Expression.Property(
                        Expression.Convert(wrappedObjectParameter, type), p),
                    Expression.Convert(valueParameter, p.PropertyType)),
                wrappedObjectParameter, valueParameter);

            this.setters.Add(name, setExpression.Compile());

            var getExpression = Expression.Lambda<Func<object, object>>(
                Expression.Convert(
                    Expression.Property(
                        Expression.Convert(wrappedObjectParameter, type), p),
                    typeof(object)),
                wrappedObjectParameter);

            this.getters.Add(name, getExpression.Compile());
        }
    }

    public void Set(string name, object value)
    {
        var set = this.setters[name];
        set(this.dyn, value);
    }

    public object Get(string name)
    {
        var get = this.getters[name];
        return get(this.dyn);
    }
}


Breaking after one of several string replaces occur I have a script that matches a string against ~20 different regexs for the purpose of changing it. They are ordered and formed that the string will only ever match against one. How can I avoid checking all the str.replaces after I match once?

My code here works, but I repeat myself a lot and it does not seem optimal.

The while loop exists so I could break, I don't actually need to loop through anything - and in fact I ensure I don't loop at the end of it. I'm merely looking for a way to stop performing replaces, when I know they will do nothing.

function format_number(input){
    var str = input.value;
    str.toString();
    var copy = str;
    var checked = false;
    while (!checked) {
        str = str.replace(/regex1/, 'replace1');
        if (copy != str) {break;}
        str = str.replace(/regex2/, 'replace2');
        if (copy != str) {break;}
        str = str.replace(/regex3/, 'replace3');
        if (copy != str) {break;}
        str = str.replace(/regex4/, 'replace4');
        if (copy != str) {break;}
        str = str.replace(/regex5/, 'replace5');
        if (copy != str) {break;}
        str = str.replace(/regex6/, 'replace6');
        if (copy != str) {break;}
        str = str.replace(/regex7/, 'replace7');
        if (copy != str) {break;}
        str = str.replace(/regex8/, 'replace8');
        if (copy != str) {break;}
        str = str.replace(/regex9/, 'replace9');
        if (copy != str) {break;}
        str = str.replace(/regex10/, 'replace10');
        if (copy != str) {break;}
        str = str.replace(/regex11/, 'replace11');
        if (copy != str) {break;}
        str = str.replace(/regex12/, 'replace12');
        if (copy != str) {break;}
        str = str.replace(/regex13/, 'replace13');
        if (copy != str) {break;}
        str = str.replace(/regex14/, 'replace14');
        if (copy != str) {break;}
        str = str.replace(/regex15/, 'replace15');
        if (copy != str) {break;}
        str = str.replace(/regex16/, 'replace16');
        if (copy != str) {break;}
        str = str.replace(/regex17/, 'replace17');
        if (copy != str) {break;}
        checked = true;
    }
    input.value=str;
}

This seems to be a fine case for a loop over the expressions:

function format_input(input) {
    // decouple DOM things from pure functionality!
    input.value = format_number(input.value);
}
function format_number(str) {
    var replacements = [
        [/regex1/, 'replace1'],
        [/regex2/, 'replace2'],
        [/regex3/, 'replace3'],
        [/regex4/, 'replace4'],
        [/regex5/, 'replace5'],
        [/regex6/, 'replace6'],
        [/regex7/, 'replace7'],
        [/regex8/, 'replace8'],
        [/regex9/, 'replace9'],
        [/regex10/, 'replace10'],
        [/regex11/, 'replace11'],
        [/regex12/, 'replace12'],
        [/regex13/, 'replace13'],
        [/regex14/, 'replace14'],
        [/regex15/, 'replace15'],
        [/regex16/, 'replace16'],
        [/regex17/, 'replace17']
    ];
    for (var i=0; i<replacements.length; i++) {
        var copy = str.replace(replacements[i][0], replacements[i][1]);
        if (str != copy)
            return copy;
    }
    return str;
}


Parsing JSON with JavaScript I need to write some JavaScript code that will take a JSON string, parse it, and return the names of the most-deeply nested properties. For example, for this input:

var json =
"{\
foo: {\
  bar: 'something',\
  baz: {\
    jack: 'other',\
  },\
  bob: {\
    bill: 'hello',\
    bilbo: 11,\
      baggins: {\
        fizz: 'buzz'\
        finger: 'bang'\
      }\
    }\
  }\
}";

it should return ['fizz', 'finger']. There are a couple of caveats:

the parsing must be done "manually"- i.e. I can't use eval or a JS library to parse the JSON
the JSON property values are guaranteed to be strings, numbers, or objects, i.e. no arrays

Here's what I've come up with so far. The main function is findDeepestLeaveNodes. At the moment the code is a bit inefficient as it has to iterate twice over the whole input String. I'd like to improve this if possible, and am also looking for suggestions for improving the code quality.

var constants = {
    BLOCK_START: '{',
    BLOCK_END: '}'
};

function findDeepestLeaveNodes(json) {

    var maxNesting = getMaxNesting(json);
    var currentNestLevel = 0;
    var results = [];
    var jsonLength = json.length;

    for (var currentCharIndex = 0; currentCharIndex < jsonLength; currentCharIndex++) {
        var currentChar = json.charAt(currentCharIndex);
        //console.log("Nesting level " + currentNestLevel + " at character '" + currentChar + "'");

        if (currentChar == constants.BLOCK_START) {

            // FIXME The following parsing is fairly fragile. It doesn't handle the possibility
            // that a '}' or ',' way occur inside a String and therefore do always close a block or
            // separate sibling JSON properties. To handle this we'd need to write a proper JSON parser.
            if (++currentNestLevel == maxNesting) {
                // read the content of the current block
                var blockEndIndex = json.indexOf(constants.BLOCK_END, currentCharIndex);
                var currentBlock = json.substring(currentCharIndex + 1, blockEndIndex);

                // Each position in the properties array will contain a property name and it's value
                var properties = currentBlock.split(',');

                for (var i = 0; i < properties.length; i++) {
                    // parse out the property name
                    var property = properties[i];
                    var separatorPosition = properties[i].indexOf(':');
                    var propertyName = property.substring(0, separatorPosition);

                    results.push(propertyName.trim());
                }
            }
        } else if (currentChar == constants.BLOCK_END) {
            --currentNestLevel;
        }
    }
    return results;
}

function getMaxNesting(json) {
    var jsonlength = json.length;
    var currentNestLevel = 0;
    var maxNestLevel = 0;

    for (var i = 0; i < jsonlength; i++) {
        var currentChar = json.charAt(i);

        if (currentChar == constants.BLOCK_START) {
            ++currentNestLevel;

        } else if (currentChar == constants.BLOCK_END) {
            // update maxNestLevel if necessary
            maxNestLevel = Math.max(currentNestLevel, maxNestLevel);
            --currentNestLevel;
        }
    }
    return maxNestLevel;
}

I'd write it as a recursive descent parser since this is quite simple:

http://en.wikipedia.org/wiki/Recursive_descent_parser

Actually I already did this a couple of years back, when I wanted to create something that simply formats and highlights JSON a bit. If you can understand it, then you can modify it to your needs:

        <textarea id="thetextarea" rows="25" cols="70" onKeyUp="go(this.value);">[{"Dies":"Ist ein Beispiel...","mit":["Arrays","und","so"]},{"alles":"sch&ouml;n verschachtelt..."},"tippt einfach json-zeugs in dem grossen Feld.","Die Anzeige aktualisiert sich sofort...","Die Formatierungen sind als &lt;style&gt; gespeichert. Ihr k&ouml;nnt sie so beliebig &auml;ndern.",{"Zahlen":1,"sind":[1,4,55.67],"auch":"sch&ouml;n"}]</textarea>


Alternating items in a collection Is there any better way how to mix items in list? In my example: I want to sort list items as male, female, male, ... My solution is probably very time and resource demanding. Can I do it somehow with LINQ?

private List<Child> MixGender(List<Child> children)
    {
        List<Child> male = new List<Child>() { };
        List<Child> female = new List<Child>() { };

        male = children.Where(c => c.Sex == "male").ToList();
        female = children.Where(c => c.Sex == "female").ToList();

        int childrenCount = children.Count;
        int indexMale = 0;
        int indexFemale = 0;

        children.Clear();

        for (int i = 0; i < childrenCount; i++)
        {
            if (i % 2 == 1)
            {
                if (indexMale < male.Count)
                {
                    children.Add(male[indexMale]);
                    indexMale++;
                }
                else
                {
                    children.Add(female[indexFemale]);
                    indexFemale++;
                }
            }
            else
            {
                if (indexFemale < female.Count)
                {
                    children.Add(female[indexFemale]);
                    indexFemale++;
                }
                else
                {
                    children.Add(male[indexMale]);
                    indexMale++;
                }
            }
        }

        return children;
    }

Not a fan of LINQ, yet? Then look here... You could start by grouping Child by Sex into a new lookup, this would replace the two Wheres. In the next step you Zip them together and take one item from each collection at a time. You create from then new tiny collections that you finally flatten with SelectMany. No calculation necessary.

var groups = items.ToLookup(i => i.Sex);
var alternating =
    groups["male"]
        .Zip(groups["female"], (x, y) => new[] { x, y })
        .SelectMany(t => t)
        .ToList();

This will however require that both collections have the same length because Zip will go only as far as the shorter collection.

Some nice improvement to you method would be to make it work for any group of items. When you pass it a custom comparer you can GroupBy the items and iterate over each group until there is nothing left to yield. Since enumerators are disposable you need to make sure to dispose them properly at the end thus the finally block.

public static IEnumerable<T> Interleave<T>(this IEnumerable<T> source, IEqualityComparer<T> comparer)
{
    var groups = source.GroupBy(x => x, comparer);
    var enumerators = groups.Select(g => g.GetEnumerator()).ToList();
    try
    {
        var any = false;
        do
        {
            any = false;
            foreach (var e in enumerators)
            {
                if (e.MoveNext())
                {
                    any = true;
                    yield return e.Current;
                }
            }
        } while (any);
    }
    finally
    {
        foreach (var e in enumerators)
        {
            e.Dispose();
        }
    }
}

An example usage could then look like this:

var innerComparer = StringComparer.OrdinalIgnoreCase;
var comparer = EqualityComparerFactory<Child>.Create
(
    (x, y) => innerComparer.Equals(x.Sex, y.Sex),
    obj => innerComparer.GetHashCode(obj.Sex)
);
var result = items.Interleave(comparer);