Asking 2 values, feet and inches, and it converts them to centimeters I was doing an exercise in PHP, and it works perfectly, no problems. But I think that maybe I coded it so long, and I think it can be shorter than it is now, but I don't know how to make it shorter and that works exactly the same way.

I will explain what this code is doing for you so it's faster if you are going to help (if you want a deeper explanation, you can translate the commented section because that's the wording of the exercise): first of all, I have a PHP file and a html file with a form. The form it's asking for 2 values (feet and inches), for converting them to centimeters. Feet value must be integer, greater than or equal 0. Inches must be integer or decimal, and greater than or equal 0.

<?php
    //Realice un formulario que introduzca dos valores (pies y pulgadas) y los convierta a
    //centímetros. Los pies deben ser un número entero mayor o igual que cero. Las pulgadas
    //son un número entero o decimal mayor o igual que cero. Un pie son doce pulgadas y una
    //pulgada son 2,54 cm.

    $converPC = 30.48;
    $converPlC = 2.54;
    $pies = trim(htmlspecialchars(strip_tags($_REQUEST["pies"]), ENT_QUOTES, "UTF-8"));
    $pulgadas = trim(htmlspecialchars(strip_tags($_REQUEST["pulgadas"]), ENT_QUOTES, "UTF-8"));
    if ( (!empty($pies)) && (!empty($pulgadas)) ) {
        if ( (is_numeric($pies)) && (is_numeric($pulgadas)) ) {
            //Apartado de los pies
            if ( (filter_var($pies, FILTER_VALIDATE_INT)) && ($pies >= 0) ) {
                $resultadoPI = $pies*$converPC;
                print "CONVERSIÓN PIES - CENTÍMETROS
";
                print "$pies pies son $resultadoPI centímetros

";
            } else {
                print "Error en pies
";
                print "Debe introducir un número entero mayor o igual que cero

";
            }
            //Apartado de las pulgadas
            if ($pulgadas >= 0) {
                $resultadoPU = $pulgadas*$converPlC;
                print "CONVERSIÓN PULGADAS - CENTÍMETROS
";
                print "$pulgadas pulgadas son $resultadoPU centímetros";
            } else {
                print "Error en pulgadas
";
                print "Debe introducir un número mayor o igual que cero";
            }
        } else {
            print "Error, ambos valores deben ser numéricos";
        }
    } else {
        print "Para que todo funcione, debe rellenar TODOS los campos del formulario";
    }

?>

This code is pretty compact already so there isn't much room to reduce the size of it. Typically separating the error handling, calculations, and output of content are separated so you may want to look into that for code improvements but that won't make the code any smaller.
Better data sanitation
It's great that you do your best to sanitize user input before you use it. But, there's better ways to go about it. Since
both inputs are expected to be floating point numbers you can use PHP's built in filter_var() with the
FILTER_VALIDATE_FLOAT flag to sanitize the value to a floating point number:
$pies     = filter_var($_REQUEST["pies"], FILTER_VALIDATE_FLOAT, FILTER_FLAG_ALLOW_THOUSAND);
$pulgadas = filter_var($_REQUEST["pulgadas"], FILTER_VALIDATE_FLOAT, FILTER_FLAG_ALLOW_THOUSAND);

Combine/remove your IF statements
When you see an IF statement followed by another IF statement that's usually a sign that you could combine the two into one as all of them must be true for the following code to be executed:
if ( !empty($pies) && !empty($pulgadas) && (s_numeric($pies) && is_numeric($pulgadas) ) {

The above line can then be shortened thanks to the better sanitation used above. The checks to is_numeric are no longer
needed since filter_var() will return a number or false which will be caught by the empty() checks. So you can now safely remove them:
if ( !empty($pies) && !empty($pulgadas) ) {

You can eliminate your check to see if $pies >= 0 by passing an extra flag to filter_var() to only allow positive numbers and zero.
if ( filter_var($pies, FILTER_VALIDATE_INT) && $pies >= 0 ) {

becomes
if ( filter_var($pies, FILTER_VALIDATE_INT, ['options' => ['min_range' => 0]]) ) {

You also forgot to add this check for $pulgadas.
Other notes
Use constants to store values that will remain the same and are unchangeable
Your variables containing the ratios for converting the measurements are better off set as constants than variables since they will remain the same and are unchangeable. (i.e. constant)
$converPC = 30.48;
$converPlC = 2.54;

becomes (notice the use of all capital letters as that is the expected format of constants in PHP)
define('CONVER_PC', 30.48);
define('CONVER_PLC', 2.54);

Omit closing PHP tag
When the closing tag is the last line of a PHP file you can safely omit and it is the standard practice as set forth by
the PSR-2 coding standard for PHP. There are lots of good reasons to do this.
Use echo over print()
print() is an alias of echo but there are minor differences between the two. Although they don't come into play here, it is the PHP convention to use echo for outputting content.
Unnecessary parenthesis
If your IF statements you have parenthesis around each conditional. That is not necessary. You only need to use them when you need to clarify scope. When there's only one condition there is nothing that needs clarification.
Outcome
This code is untested but should give you the idea of what the comments above mean.
define('CONVER_PC', 30.48);
define('CONVER_PLC', 2.54);
$pies     = filter_var($_REQUEST["pies"], FILTER_VALIDATE_FLOAT, FILTER_FLAG_ALLOW_THOUSAND);
$pulgadas = filter_var($_REQUEST["pulgadas"], FILTER_VALIDATE_FLOAT, FILTER_FLAG_ALLOW_THOUSAND);
if ( !empty($pies) && !empty($pulgadas) ) {
    //Apartado de los pies
    if ( filter_var($pies, FILTER_VALIDATE_INT, ['options' => ['min_range' => 0]]) ) {
        $resultadoPI = $pies*CONVER_PC;
        echo "CONVERSIÓN PIES - CENTÍMETROS
";
        echo "$pies pies son $resultadoPI centímetros

";
    } else {
        echo "Error en pies
";
        echo "Debe introducir un número entero mayor o igual que cero

";
    }
    //Apartado de las pulgadas
    if ( filter_var($pulgadas, FILTER_VALIDATE_INT, ['options' => ['min_range' => 0]]) ) {
        $resultadoPU = $pulgadas*CONVER_PLC;
        echo "CONVERSIÓN PULGADAS - CENTÍMETROS
";
        echo "$pulgadas pulgadas son $resultadoPU centímetros";
    } else {
        echo "Error en pulgadas
";
        echo "Debe introducir un número mayor o igual que cero";
    }
} else {
    print "Para que todo funcione, debe rellenar TODOS los campos del formulario";
}

Main issues with this code are

It doesn't meet the requirements (so doesn't the code in the other answer).
Its result is not very useful if you ever try to actually use it.
Nearly half of this code just duplicates itself or plain useless.

So here goes your homework

$converPlC = 2.54;
$converPC = $converPlC * 12;

$pies = $_REQUEST["pies"];
$pulgadas = $_REQUEST["pulgadas"];

if (ctype_digit($pies) && $pies >= 0) {
    $resultadoPI = $pies*$converPC;
    print "CONVERSIÓN PIES - CENTÍMETROS
\n";
    print "$pies pies son $resultadoPI centímetros

\n";
} else {
    print "Error en pies
\n";
    print "Debe introducir un número entero mayor o igual que cero

\n";
    $resultadoPI = 0;
}
if (is_numeric($pulgadas) && $pulgadas >= 0) {
    $resultadoPU = $pulgadas*$converPlC;
    print "CONVERSIÓN PULGADAS - CENTÍMETROS
\n";
    print "$pulgadas pulgadas son $resultadoPU centímetros\n";
} else {
    print "Error en pulgadas
\n";
    print "Debe introducir un número mayor o igual que cero\n";
    $resultadoPU = 0;
}

It makes your code fixed but it doesn't look good. To make it better, we will need a sensible output and also we definitely should separate the calculations from the output. So here goes the refactored version

$converPlC = 2.54;
$converPC = $converPlC * 12;

$pies = $_REQUEST["pies"];
$pulgadas = $_REQUEST["pulgadas"];

if (ctype_digit($pies) && $pies >= 0 && is_numeric($pulgadas) && $pulgadas >= 0) {
    $resultadoPI = $pies*$converPC;
    $resultadoPU = $pulgadas*$converPlC;
    $resultado   = $resultadoPU + $resultadoPI;
    if ($resultadoPU && $resultadoPI) {
        $title = "CONVERSIÓN PIES Y PULGADAS - CENTÍMETROS";
        $message = "$pies pies y $pulgadas pulgadas son $resultado centímetros";
    } elseif ($resultadoPI) {
        $title = "CONVERSIÓN PIES - CENTÍMETROS";
        $message = "$pies pies son $resultado centímetros";
   } elseif ($resultadoPU) {
        $title = "CONVERSIÓN PULGADAS - CENTÍMETROS";
        $message = "$pulgadas pulgadas son $resultado centímetros";
    } else {
        $title = "Invalid input data";
        $message = "Enter at least one value";
    }
} else {
    $title = "Invalid input data";
    $message = "Input must be a positive number or zero";
}
?>
<?=$title?>

<?=$message?>

Here you can see the immediate benefit of the separated output: when you will have to change the formatting, it would be done only once and without the hassle of escaping quotes and stuff.


Functional / Declarative FizzBuzz I spent some time today trying to write FizzBuzz in a functional/declarative style. I thought it would be a good chance to get some feedback on it since I've been doing functional programming for about a year now.

(I know there are some similar questions asked here before, but their approach to the code has been different to mine and it would be good to get feedback more specific to my code)

The main things I want to know are:

How consistent is this code with the best practices in functional and declarative programming?
Are there any bad practices in it that I should be aware of?

const isFizz = number => number % 5 === 0
const isBuzz = number => number % 3 === 0

const newArrayInRange = (min, max) => [...Array(max + 1).keys()].slice(min)

const fizzBuzz = (min, max) => newArrayInRange(min, max)
  .map(number => {
    if (isFizz(number) && isBuzz(number)) {
      return 'fizzbuzz'
    }
    if (isFizz(number)) {
      return 'fizz'
    }
    if (isBuzz(number)) {
      return 'buzz'
    }
    return number
  })
  .join('\n')

console.log(fizzBuzz(1, 100))

Maybe some changes

Removing the arrays needed to hold the counter, its a huge overhead just for a counter.
Avoiding excessive logic statements using (num % val) to return strings and using the empty string to add a number (see code marked /*A*/)
Putting everything into an array to join when done as you have done. It is the quickest way to build a long string in JavaScript.

Thus we end up with the following...

const fizz = num => num % 5 ? "" : "fizz";
const buzz = num => num % 3 ? "" : "buzz";
const fizzBuzz = num => fizz(num) + buzz(num);
const fizzBuzzer = (min, max) => {
    const res = [];
    do {
        const fb =  fizzBuzz(min);
        res.push(fb ? fb : min);       /*A*/
    } while (min++ < max);

    return res.join("\n");
}

Personally the function fizz, buzz, fizzBuzz are just adding code without good reason and would need to be closed over to avoid polluting what ever scope it is in.

Thus the 3 function become the expression right of const fb =

Also I am not a fan of arrow functions in an open scope so using a function declaration to ensure accessibility.

function fizzBuzzer(min, max) {
    const res = [];
    do {
        const fb =  (min % 5 ? "" : "fizz") + (min % 3 ? "" : "buzz");
        res.push(fb ? fb : min);
    } while (min++ < max);

    return res.join("\n");
}

You ask

  How consistent is this code with the best practices in functional and declarative programming?

Best practice, well that is subjective, contextual and would only have comparative meaning when compared to "bad" code?

Your code is not bad, it works , it would have been worse 3 years back due to the way JS engines handled arrays, but now most optimizers recognize the pattern and make it fly.

There is a zillion ways to write any bit of code. JS programmers can still not agree on the use of semicolons and whether or not automatic semicolon insertion was a good idea or not, so how is any bit of code ever going to be best practice.

  Are there any bad practices in it that I should be aware of?

OMDG Yes there is.... Semicolons, where are they?

// Example of bad
const fizzBuzzard = (min, max) => {
    const next = n => n <= max ? order[n % 15] : () => "";
    const txt = w => n => (w ? w : n + "\n") + next(++n)(n);
    const [n, b, f, fb] = [txt(), txt("buzzard\n"), txt("fizz\n"), txt("fizzBuzzard\n")];
    const order = [fb, n, n, b, n, f, b, n, n, b, f, n, b, n, n];
    return next(min)(min);
}
console.log(fizzBuzzard(1, 100));

First I would like to say that code can be functional to a degree, so I will point out what I like and what could be (even) more functional.

I like isFizz and isBuzz because they are declarative and pure functions (i.e. they have no obvious side effects and are deterministic). I also like that the map does not use intermediate variables, because that would be a more imperative approach.

A suggestion would be trying to reduce the potential number of evaluations in the map (for each number, both isFizz and isBuzz are potentially executed twice) without using intermediate variables. My suggestion can be found below in the toTerms function or the Ramdba pseudo code.

After taking the course Functional-Light JavaScript v3, I have attempted to write a declarative/functional FizzBuzz implementation too.

In this course, Kyle Simpson recommends gradually converting to declarative style, which I found helpful. Also it resulted in a way over-engineered implementation, but I think it does show parts of the code that I really had to think about before finding an appropriate declarative alternative.

The implementation is in this fiddle, with my intermediate progress too. It also contains suggestions for further refactoring. This is the state at time of writing:

const range = (function rangeInner(acc) {
 return (first, last) => {
    if(first > last) {
      return acc;
    }
    return rangeInner([...acc, first])(first + 1, last);
  }
})([]);

const isMod3 = n => n % 3 === 0;
const isMod5 = n => n % 5 === 0;

const predicatesAndTerms = [
    [isMod3, "Fizz"],
    [isMod5, "Buzz"]
]

const toTerms = n => predicatesAndTerms
 .reduce((acc, [predicateFn, term]) => acc += predicateFn(n) ? term : "", "");

const toFizzBuzz = n => toTerms(n) || n.toString();

console.log(range(1, 15).map(toFizzBuzz));

In an attempt to avoid potentially evaluating isMod3 (isFizz in the question) and isMod5 twice for each number, I refactored to a reduce over an array of "predicate" and "term" tuples, that is evaluated by a ternary operator that returns a value directly. I also tried to avoid intermediate variables as much as possible, forcing myself to create tiny cohesive functions instead.

In an earlier version, I had a similar implementation of range as in the question, but I refactored it to try out recursion combined with a closure for the acc parameter, with the option to refactor it using R.curry later, (where R refers to Ramda).

Pseudo-code for further refactoring toFizzBuzz with Ramda could be:

const orDefault = fn => n => fn(n) || n; // looks like R.defaultTo, but executes fn over n first.
const toTermsOrDefault = orDefault(toTerms);
const toString = n => n.toString();
const toFizzBuzz = compose(toString, toTermsOrDefault);

Good luck learning FP JavaScript! If you want to discuss FP JS, I'm always interested.


Graceful way to find combinations in JavaScript I'm looking for combinations, not permutations, and have found some really great examples ranging from using flatMap such as https://stackoverflow.com/a/54329187/669843

The result of ['a', 'b', 'c'] would be an array of arrays of 3 (a, b, and c). The result I'm looking for would also contain arrays of length 1 and 2.

Example:

['a']
['b']
['c']
['a', 'b']
['a', 'b', 'c']
['a', 'c']
...

I'm accomplishing the results with something like this but this seems extraordinarily awful and requires de-duplication.

for(let i = 0; tci < combo.length; tci++) {
  let newcombo = [allitems[item]].concat(combo.slice(tci, combo.length));
  ...
  push newcombo;

You can write this better.  The best way to explain it is to see the code example in Python's itertools module:

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

This generates the combinations of length 'r' efficiently using counting.  You can create all combinations by either adding length-1 'nulls' to the pool or just iterating over the lengths.

Combination generation is a bit hard to grok, and really you should step through this example until you get it.  It's a variation on the idea of manually counting used throughout many algorithms.

The base idea for combinations('ABCD', 2) is to start with 'AB' (first yield), increment the last letter 'AC' then 'AD' with the for j loop doing nothing, on the next loop i will be the index 0, so 'A' -> 'B' and the second resets to one more than the first character and you yield 'BC'.

Trace the code.  Keep hacking!  Keep notes.


Reversing a singly-linked List Is this the best way to reverse a singly-linked list? Can it be done with two, or fewer pointers? Any other comments?

public class ReverseLL {
    Node start;
    ReverseLL()
    {
        start=null;
    }
    class Node
    {
        Node next;
        int data;

        Node(int newData)
        {
            next=null;
            data=newData;
        }
        public void setData(int newData)
        {
            data=newData;
        }
        public int getData()
        {
            return data;
        }
        public void setNext(Node n)
        {
            next=n;
        }
        public Node getNext()
        {
            return next;
        }

    }
    public void insert(int newData)
    {
        Node p=new Node(newData);
        if(start==null)
        {
            start=p;
        }
        else
        {
            Node temp=start;
            while(temp.getNext()!=null)
            {
                temp=temp.getNext();
            }
            temp.setNext(p);
        }
    }

    public void reverse()
    {
        Node temp=start;
        Node previous=null;
        Node previous1=null;
        while(temp.getNext()!=null)
        {
            if(temp==start)
            {
                previous=temp;
                temp=temp.getNext();
                previous.setNext(null);
            }
            else
            {
                previous1=temp;
                temp=temp.getNext();
                previous1.setNext(previous);
                previous=previous1;
            }
        }
        temp.setNext(previous);
        start=temp;
    }
    public void display() {
        int count = 0;

        if(start == null) {
            System.out.println("\n List is empty !!");
        } else {
            Node temp = start;

            while(temp.getNext() != null) {
                System.out.println("count("+count+") , node value="+temp.getData());
                count++;
                temp = temp.getNext();
            }
            System.out.println("count("+count+") , node value="+temp.getData());
        }
    }
    public static void main(String args[])
    {
        ReverseLL ll=new ReverseLL();
        ll.insert(1);
        ll.insert(2);
        ll.insert(3);
        ll.insert(4);
        ll.insert(5);
        ll.insert(6);
        ll.insert(7);
        ll.insert(8);
        ll.display();
        System.out.println();
        ll.reverse();
        ll.display();
    }
}

This is a nice, clean implementation of a Linked list... Generally a good job.

You have a bug in your reverse method, a NullPointerException when the list is empty. There is an easy fix, but you should be aware.

I also had a look at your reverse method. I cannot see a way to do it with fewer than 3 variables, while still keeping the logic readable. I am not particularly fond of your implementation... The distinct if/else condition makes the internal logic cumbersome. It makes things easier if you consider the process to be closer to a swap... we want to swap the direction of the pointer between nodes.

So, the logic is, for three nodes A->B->C, we want to make B point to A, but, we have to remember that C comes after B before we reverse the pointer. Then we have to make C point to B, becoming A<-B<-C

But, we have a couple of loose ends (pun is intended)... we have the start pointer which points at A, and A is pointing at B still, So, we need to remove the now-redundant A->B pointer, and also move start to point at C..... All so complicated, but it boils down to a simple loop:

    public void reverse() {
        if (start == null) {
            return;
        }
        Node current = start;
        Node after = start.next;
        while (after != null) {
            Node tmp = after.next; // preserve what will come later.
            after.next = current;  // reverse the pointer
            current = after;       // advance the cursor
            after = tmp;           // the node after is the one preserved earlier.
        }
        start.next = null;         // null-out next on what was the start element
        start = current;           // move the start to what was the end.
    }

This, to me, is much more readable than the conditional logic you had. It does use three pointers in addition to the start.

If you want to, you can probably find a way to do it with one less pointer, but that is by hacking the start pointer and using it as a tracker in the loop (probably instead of current, but the readability, and simplicity will suffer if you do that.

Note also that Java coding convention puts the { open brace at the end of the line containing the conditional block.

Finally, at the risk of adding a little complexity to your code, most general-purpose Linked Lists in 'real' applications have an O (1) mechanism for getting the List size. If you have a custom purpose for the list where the size is not important, you can skip that, but, you should otherwise consider adding a size field so you can avoid doing a full iteration to get the size.

Another Finally, The Java Iterator concept is a very common idiom. It is surprisingly complicated though to get your implementation to match the specification. I strongly recommend that you take it upon yourself to make your List iterable, and to make sure your Iterator implementation conforms to the specification (especially the conditions under which the iterator throws exceptions).

I also extended your main method to do a few more tests than you have:

    public static void main(String args[]) {
        ReverseLL ll=new ReverseLL();
        ll.reverse();
        ll.display();
        System.out.println();

        ll.insert(1);
        ll.reverse();
        ll.display();
        System.out.println();

        ll.insert(2);

        ll.reverse();
        ll.display();
        System.out.println();

        ll.reverse();
        ll.display();
        System.out.println();

        ll.insert(3);
        ll.insert(4);
        ll.insert(5);
        ll.insert(6);
        ll.insert(7);
        ll.insert(8);
        ll.display();
        System.out.println();

        ll.reverse();
        ll.display();
        System.out.println();
    }

emphasized textWithout temp, this is not my code.  Please see:https://algorithms.tutorialhorizon.com/reverse-a-linked-list/

//https://algorithms.tutorialhorizon.com/reverse-a-linked-list/

public class ReverseLinkedList {

public static void main (String[] args) throws     java.lang.Exception
{
    LinkedListT a = new LinkedListT();
    a.addAtBegin(5);
    a.addAtBegin(10);
    a.addAtBegin(15);
    a.addAtBegin(20);
    a.addAtBegin(25);
    a.addAtBegin(30);
//  System.out.print("Original Link List 1 : ");
    a.display(a.head);
    a.reverseIterative(a.head);
    LinkedListT b = new LinkedListT();
    b.addAtBegin(31);
    b.addAtBegin(32);
    b.addAtBegin(33);
    b.addAtBegin(34);
    b.addAtBegin(35);
    b.addAtBegin(36);
    System.out.println("");
    System.out.println("___________________");
    System.out.print("Original Link List 2 : ");
    b.display(b.head);
    b.reverseRecursion(b.head,b.head.next,null);
    System.out.println("");
    //b.display(x);
   }
}
class Node{
public int data;
public Node next;
public Node(int data){
    this.data = data;
    this.next = null;
}
}
class LinkedListT{
public Node head;
public LinkedListT(){
    head=null;
}

public void addAtBegin(int data){
    Node n = new Node(data);
    n.next = head;
    head = n;
}
public void reverseIterative(Node head){
    Node currNode = head;
    Node nextNode = null;
    Node prevNode = null;

    while(currNode!=null){
        nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    head = prevNode;
    System.out.println("\n Reverse Through Iteration");
    display(head);
}

public void reverseRecursion(Node ptrOne,Node ptrTwo, Node prevNode){
    if(ptrTwo!=null){
            if(ptrTwo.next!=null){
                Node t1 = ptrTwo;
                Node t2 = ptrTwo.next;
                ptrOne.next = prevNode;
                prevNode = ptrOne;
                reverseRecursion(t1,t2, prevNode);
            }
            else{
                ptrTwo.next = ptrOne;
                ptrOne.next = prevNode;
                System.out.println("\n Reverse Through Recursion");
                display(ptrTwo);
            }
    }
    else if(ptrOne!=null){
        System.out.println("\n Reverse Through Recursion");
        display(ptrOne);
    }
    }

public void display(Node head){
    //
    Node currNode = head;
    while(currNode!=null){
        System.out.print("->" + currNode.data);
        currNode=currNode.next;
    }
    }
  }


Implementation of Counting Sort using C++ Please review my code. If any improvement needed please point out. I have used std::map. Is there any better alternative?

#include <bits/stdc++.h>

class count_sort
{
  std::map<int, int> m;
  std::map<int, int>::iterator it;

public:

  void counting_sort(std::vector<int>& a){
   for(int i=0; i<a.size(); i++)
   {
    m[a[i]]++;
   }
  }

  void display()
  {
    it = m.begin();
    while(it != m.end())
    {
      for(int i = 0; i < it->second; i++)
      {
        std::cout<<it->first<<" ";
      }
     it++;
   }
   std::cout<<"\n";
  }
};

int main()
{
    count_sort c1;
    std::vector<int>v {2,5,3,0,2,3,0,3};
    std::cout<<"The entered values are \n";
    for(int i = 0; i < v.size(); i++)
    {
      std::cout<<v[i]<<" ";
    }
    std::cout<<"\n";
    c1.counting_sort(v);
    std::cout<<"The sorted values \n";
    c1.display();
}

It says add more details. I don't know what to add.

#include <bits/stdc++.h>

You normally shouldn't use this. It includes every standard library header. If you compile without precompiled headers, this would make your compilation time much greater. The recommended practice is to #include just what you need, and if you want to use a precompiled header as well, that's just fine.

class count_sort
{

It is a bit strange to use a class for sorting. That your sort function is in a class implies that there's state, which is unexpected. You could use a namespace.

  std::map<int, int> m;
  std::map<int, int>::iterator it;

This state can easily be moved inside the functions, to the smallest scope possible.

  void counting_sort(std::vector<int>& a){

The name counting_sort is a bit redundant, seeing as it's a member function of a class called count_sort. You could use sort, or even operator(). Other than that, by taking std::vector<int>& as a parameter, you make this sort function not very general. The way the parameters are usually taken for a sort function (in C++) is as an iterator range:

template <typename Iter>
void counting_sort(Iter begin, Iter end) {

If you don't want to use templates, that's fine, but keep in mind that they make it more general.

One other thing to note is that you never change the vector in this function. That's a sign that it should be taken by const& rather than &. However, the expected semantics of a function called sort is that it modifies its parameter so that, after the function is called, the parameter is sorted. It's unusual and unexpected to have to call another function to obtain the output.

For the actual implementation, you can make use of C++11's range-based for loops (aka for-each loops). This:

for(int i=0; i<a.size(); i++)
{
 m[a[i]]++;
}

Becomes this:

// Read as "`for` each `int i` in `a`, ..."
for (int i : a) {
    m[i]++;
}

Putting together my suggestions, without templates, would look something like this:

namespace counting_sort {
    void sort(std::vector<int>& vec) {
        std::map<int, int> count;

        for (int i : vec) {
            ++count[i];
        }

        // modify the parameter; write the values back out
        auto begin = vec.begin();
        for (const auto& pair : count) {
            while (pair->second > 0) {
                *begin = pair->first;
                ++begin;
                --pair->second;
            }
        }
    }
}

Aside from what is said already:

Not sure by which coding style you go, but lower case class names are unusual.
Separate into several files. A class has a header file and a source file. Somebody who wants to use the class should only require the header. This also holds true for collections of functions. Keep your main source file small.
a is no proper variable name. Especially for an input. Neither is m. Use words. (i for the iteration variable is fine though, since it is short lived and everybody knows what it does)

That said, can only repeat from the other answer: This should not be a class. "This is a count sort" does not make sense as a sentence, this is why. Also, every object of it will be extremely short lived. If you want to extend the functionality of something that already exists, use functions.


Qt Custom Scatterplot I have  created a custom scatterplot in Qt and am wondering if there is a more efficient way to do it. Here is a sketch of the problem:

The layout of the plotting area consists of a rectangular structure starting at [0,0] in the top left corner and expands by 250 pixels to the bottom right corner [250,250]. So the y-coordinate grows downwards and the x-coordinate to the right.

The task consists of mapping two vectors (A[i],B[i]) holding numerical data onto this rectangular structure such that the lowest x,y coordinates are in the bottom left corner and the highest x,y coordinates are in the top right corner.

To solve this problem I choose the following approach (pseudo code):

calculate the min and max for (A and B);
calculate the spread (max - min) for (A and B);
transform A and B by:

 foreach (i in A) {
     (i - min(A) / spread(a))* 250
 }
 foreach(j in B) {
     (250 - ((j - min(B) / spread(B))*250
 }

and the implementation:

.h file

#include <QDialog>
#include <QtGui>
#include <QtCore>
#include <QGraphicsScene>
#include <cstdlib>
#include <cmath>
#include <QVector>
#include <QRectF>

namespace Ui {
class paintEr;
}

class paintEr : public QDialog
{
    Q_OBJECT

public:
    explicit paintEr(QWidget *parent = 0);
    ~paintEr();
private slots:
    void addPoint();

private:
    Ui::paintEr *ui;
    QGraphicsScene *scatter;

protected:
    void paintEvent(QPaintEvent *event);

};

.cpp

#include "painter.h"
#include "ui_painter.h"

paintEr::paintEr(QWidget *parent) :
    QDialog(parent),
    ui(new Ui::paintEr)
{
    ui->setupUi(this);
}

void paintEr::paintEvent(QPaintEvent *event){

    scatter = new QGraphicsScene(this);
    ui->graphicsView->setSceneRect(0,0,250,250);
    ui->graphicsView->setScene(scatter);

}
void paintEr::addPoint(){
    QPen greenPen(Qt::green);
    QBrush greenBrush(Qt::green);

    QVector<double> a,b,c,d;
    a << 2 << 5 << 7;
    b << 22 << 34 << 75;
    double min_a = *std::min_element(a.begin(), a.end());
    double max_a = *std::max_element(a.begin(), a.end());
    double min_b = *std::min_element(b.begin(), b.end());
    double max_b = *std::max_element(b.begin(), b.end());
    double spread_a = max_a - min_a;
    double spread_b = max_b - min_b;

    for(int i = 0; i < a.length(); ++i){
        c.push_back(((a[i]-min_a)/spread_a)*250);
        d.push_back(250-((b[i]-min_b)/spread_b)*250);
        scatter->addEllipse(c[i], d[i], 5, 5, greenPen, greenBrush);
    }
}
paintEr::~paintEr()
{
    delete ui;
}

main.cpp

#include "painter.h"
#include <QApplication>

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    paintEr w;
    w.show();

    return a.exec();
}

You should separate the actual data from the logic. Make your function capable of working on any QVectorq of QPairs (or pair of QVectors but that's not as normalized).

Variable names a,b,c,d don't make sense. Especially since a and b really ought to be input parameters.

You should be able to get both the min and max with one pass over the list. You'll probably have to write a custom mapreduce-style function.

For the circles in the QGraphicsScene: Are they supposed to have their center at the point in question, or the topleft of their bounding rect?

Here is a more detailed explanation to why I think the second approach is more efficient:

Before I come the my second approach let me explain the basic idea behind the first:

1. Approach:

Basic idea: express data of arrays A, B in percentages, with the min of A, B = 0 % and the max of A, B = 100 %;
Once the percentages are calculated, multiply each value in A, B with the respective length of the axis in pixels

2. Approach:

find the max of A, B by sorting both arrays and taking the last element as the max
divide the length of each axis by the max of A, B respectively and obtain the "multiplier" A_multip, B_multip
multiply each value of  A, B with their respective multiplier and plot

Pseudocode:

//initialise values
int lengthOfAxis_A;
int lengthofAxis_B;
double multiplier_A;
double multiplier_B;

//sort arrays
sort(A);
sort(B);

multiplier_A = lengthOfAxis_A / A.last;
multiplier_B = lengthofAxis_B / B.last;

foreach(i in A, B)
    plot(A[i]*multiplier_A, B[i]*multiplier_B)

Explanation:

I believe the second approach is faster because:

sorting once is less costly then finding the min and max respectivly (not 100% sure though)
no need for additional vectors (memory efficiency), instead two double values (multipliers)
(A[i] - min(A)) / spread(A) is replaced by: A[i] * A_multip (less computation)


Validate input of month/year, otherwise set it to current month/year Is there a cleaner way of doing this? I'm using filter_input to first check for valid input, then using it again to assign the variable. Also, my condition in if/else seems quite long.

$optionsMonth = array('options'=>array('min_range'=>1, 'max_range'=>12));
$optionsYear = array('options'=>array('min_range'=>1900, 'max_range'=>9999));

if ((filter_input(INPUT_GET, 'month', FILTER_VALIDATE_INT, $optionsMonth))&&(filter_input(INPUT_GET, 'year', FILTER_VALIDATE_INT, $optionsYear))){
    $month = filter_input(INPUT_GET, 'month', FILTER_VALIDATE_INT, $optionsMonth );
    $year = filter_input(INPUT_GET, 'year', FILTER_VALIDATE_INT, $optionsYear);
} else {
    $datetime = new Datetime('NOW');
    $month = $datetime->format('m');
    $year = $datetime->format('Y');
}

You may be over thinking it.  It's actually very simple.

The only ambiguous thing is if the year is two digits.  In most cases a two digit year can be fixed like this.  I believe in your use the month and year will be all be future and nothing from the 1900s.

if (intval($optionsYear) < 100){$optionsYear  = '20' . $optionsYear;}

Then to finish up:

$date = strtotime("$optionsYear-$optionsMonth-13"); // yyyy-mm-dd
if ($date){  // test validity, will be false if invalid
  $month = date('m',$date);  // invalid, use today's month and year.
  $year = date('Y',$date);
}
else{
  $month = date('m');  // valid numbers entered
  $year = date('Y');
}

Because the day of the month is no an issue I used 13.  Not that it would but in dates the month and day can cause problems.  By using a day of 13 it cannot be confused with a month.  If a date were entered as 13/4/2015, it would not be difficult to understand 13 is a day and 4 is a month. Oct, Nov, Dec would still be ambiguous if entered as 10, 11, or 12.

Your code is actually fine may be a suggestion to break it into multiple evaluations and functions for:

readability, clarity
structure
testability
code reuse

For example,

if ((filter_input(INPUT_GET, 'month', FILTER_VALIDATE_INT, $optionsMonth))
    &&(filter_input(INPUT_GET, 'year', FILTER_VALIDATE_INT, $optionsYear)))

can be written as a function call:

/**
 * This function validates the input against defined valid inputs.
 * It internally calls filter_input().
 * @param {Array} $optionsMonth - valid options
 * @param {int} $month - a user supplied input
 *
 * @return {boolan} - true if valid, false otherwise.
 */
function is_valid_input($optionsMonth, $month);

Then the implementation of the function is hidden, and the output of function is clear as it does one thing, so you may use use it like this:

if(!is_valid_input($optionsMonth, $month) ||
    !is_valid_input($optionsYear, $year) {
   // handle defaults
}

Therefore the suggested approach hides the implementation of the function, allows a clear structure flow and also allows it to be testable (ie. unit-test). Further readings on advantages of writing in functions here


Rounding JavaScript decimals JavaScript has some inaccurate rounding behavior so I've been looking for a reliable solution without success. There are many answers in this SO post but none cover all the edge cases as far as I can tell. I wrote the following which handles all the edge cases presented. Will it be reliable with edge cases I haven't tested?

If this is a viable solution, any enhancements to make it more efficient would be appreciated. It's not fast (time to run function 1000000 times: 778ms) but doesn't seem to be  terrible either. If there is a better solution, please post.

The edge cases that seemed to give the most problem were the first two:

console.log(round(1.005, 2)); // 1.01
console.log(round(1234.00000254495, 10)); //1234.000002545
console.log(round(1835.665, 2)); // 1835.67))
console.log(round(-1835.665, 2)); // -1835.67))
console.log(round(10.8034, 2)); // 10.8
console.log(round(1.275, 2)); // 1.28
console.log(round(1.27499, 2)); // 1.27
console.log(round(1.2345678e+2, 2)); // 123.46
console.log(round(1234.5678, -1)); // 1230
console.log(round(1235.5678, -1)); // 1240
console.log(round(1234.5678, -2)); // 1200
console.log(round(1254.5678, -2)); // 1300
console.log(round(1254, 2)); // 1254
console.log(round("123.45")); // 123
console.log(round("123.55")); // 124

function round(number, precision) {
  precision = precision ? precision : 0;

  var sNumber = "" + number;
  var a = sNumber.split(".");
  if (a.length == 1 || precision < 0) {
    // from MDN https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/round
    var factor = Math.pow(10, precision);
    var tempNumber = number * factor;
    var roundedTempNumber = Math.round(tempNumber);
    return roundedTempNumber / factor;
  }
  // use one decimal place beyond the precision
  var factor = Math.pow(10, precision + 1);
  // separate out decimals and trim or pad as necessary
  var sDec = a[1].substr(0, precision + 1);
  if (sDec.length < precision + 1) {
    for (var i = 0; i < (precision - sDec.length); i++)
      sDec = sDec.concat("0");
  }
  // put the number back together
  var sNumber = a[0] + "." + sDec;
  var number = parseFloat(sNumber);
  // test the last digit
  var last = sDec.substr(sDec.length - 1);
  if (last >= 5) {
    // round up by correcting float error
    // UPDATED - for negative numbers will round away from 0
    // e.g. round(-2.5, 0) == -3
    number += 1/(factor) * (+number < 0 ? -1 : 1);
  }
  number = +number.toFixed(precision);
  return number;
};

Here is a solution which is quick and handles all cases - negative number and negative precision. It was adapted from MDN - the main differences are

I pass positive numbers to specify decimal places where it is the opposite on MDN.
I took it out of the prototype and limited it to just the round function (removed ceil and floor)
it is significantly faster

function round(number, precision) {
  number = +number;
  precision = precision ? +precision : 0;
  if (precision == 0) {
    return Math.round(number);
  }
  var sign = 1;
  if (number < 0) {
    sign = -1;
    number = Math.abs(number);
  }

  // Shift
  number = number.toString().split('e');
  number = Math.round(+(number[0] + 'e' + (number[1] ? (+number[1] + precision) : precision)));
  // Shift back
  number = number.toString().split('e');
  return +(number[0] + 'e' + (number[1] ? (+number[1] - precision) : -precision)) * sign;
}

console.log(round(1.0e-5, 5)); // 0.00001
console.log(round(1.0e-20, 20)); // 1e-20
console.log(round(1.0e20, 2)); // 100000000000000000000
console.log(round(1.005, 2)); // 1.01
console.log(round(1234.00000254495, 10)); //1234.000002545
console.log(round(1835.665, 2)); // 1835.67))
console.log(round(-1835.665, 2)); // -1835.67))
console.log(round(1.27499, 2)); // 1.27
console.log(round(1.2345678e+2, 2)); // 123.46
console.log(round(1234.5678, -1)); // 1230
console.log(round(1234.5678, -2)); // 1200
console.log(round(1254.5678, -2)); // 1300
console.log(round(1254, 2)); // 1254
console.log(round("123.55")); // 124

Use this function to round the given number

Number((6.688689).toFixed(1));


Is there a better way to translate a string into methods? So I create 3D tree like structures using L-systems. Basically this means I generate a string like this:

 "FFFFFFFF-[[FFFF-[[FF-[[F-[[X]+X]+F[+FX]-X]+F]]]]]"

This string is then interpreted by a turtle performing certain actions for each character in the string. The problem is how to map characters to turtle actions in an elegant way in C++.

Right now I use a enum to specify the actions and performAction calls methods based on the action. Is there a better way of doing it?

The turtle code:

enum TurtleAction {
    MoveForward,
    TurnLeft,
    TurnRight,
    PitchDown,
    PitchUp,
    RollLeft,
    RollRight,
    TurnAround,
    PushState,
    PopState
};

struct TurtleState {
    Vec3f pos;

    Vec3f H;
    Vec3f L;
    Vec3f U;

    double width;
};

class Turtle {
    TurtleState m_currentState;
    stack<TurtleState> m_states;

    void(*m_drawFunc)(Vec3f,double); ///< Drawing callback

public:
    double alpha; ///< Turning angle

    Turtle(TurtleState startState,
           void(*drawFunc)(Vec3f,double));
    void performAction(TurtleAction action);

private:
    void move(double dist);
    void turn(double deg);
    void pitch(double deg);
    void roll(double deg);

    void push();
    void pop();

    void rotate(const Mat44f & R);
};

void
Turtle::performAction(TurtleAction action){
    switch (action) {
        case MoveForward:
            move(1.0f);
            break;

        case TurnLeft:
            turn(-alpha);

        case TurnRight:
            turn(+alpha);

        case PitchDown:
            pitch(-alpha);

        case PitchUp:
            pitch(+alpha);

        case RollLeft:
            roll(-alpha);

        case RollRight:
            roll(+alpha);

        case TurnAround:
            turn(180.0f);

        case PushState:
            push();

        case PopState:
            pop();

        default:
            break;
    }
}

The string parsing:

class LSystem {

    map<char,TurtleAction> m_actionRules;
    TurtleState m_start;

public:

    void draw(string & str,void(*drawFunc)(Vec3f,double));
    void computeString(string & axiom, int generations);

    LSystem();
    ~LSystem();

};

void
LSystem::draw(string &str, void (*drawFunc)(Vec3f, double))
{
    Turtle turtle(m_start,drawFunc);
    turtle.alpha = 25.0f;

    for (int s = 0; s < str.size(); s++) {
        char c = str[s];
        map<char,TurtleAction>::iterator it = m_actionRules.find(c);
        if (it != m_actionRules.end()) {
            turtle.performAction(it->second);
        }
    }
}

The design flaw would have been the use of this switch case with 11 entries. That's already a lot. By the way I warn you, you have forgotten 9 break out of 11 cases.

However, in your case, each case relates to a single action. I mean, there is not a lot new to understand while reading: for each case you define a single behaviour action, inside a single word function call. (You don't put multi line, multi code, with multi conditions behaviour that is complex inside your switch case... : this is the thing to avoid and you have avoided it)

So honestly speaking it's totally acceptable.

Only for your culture I am mentionning some ways to get rid of switch case. I repeat myself, you shouldn't apply them in your case right now.

However, the first thing you may notice in such design, maybe there are common behaviours that are dupplicated between all your function call inside the switch case.

Imagine, if in roll() and turn() you would first have to

Turn head to the right to see if nothing tries to cross my path
Turn head to the left to see if nothing is moving straight right on me

and then only to roll() or to turn()

Then you could start thinking about using the Strategy pattern instead of simple function calls. This way, the strategy object which contain the action to do, can share common behaviour in a mother class.

If you started to have really many Strategies, that should be tune and tweaked precisely, then you would think about implementing the Interpreter Pattern so as to map between the precise language in your entry and the Strategies to apply.

And if you start to have a big Interpreter object and you think you need a grammar to express all the possibilities, then no doubt you should think about a Domain Specific Language. ( with you how parser etc... ).

In your case the switch case is entirely sufficient ;-)


Shifting records in SQL Database while sorting with algorithm I have a table in a SQL Server database, which holds information of some images, and the relevant gallery of them. The columns are like:

ImageId, GalleryId, Order

I have a unique key on GalleryId-Order columns, that is, each image should have a unique order in its gallery.

A business requirement is to change the place (order) of an image, inside the gallery. For example, image at the order of 16, might be replaced at the new order 7. However, all the images should shift, if necessary, to provide space for this sorting operation. In this example, images with the order 7, 8, 9, ..., 15 should shift forward one level, so that the place 7 would become empty for the mentioned image.

I've written a procedure for this:

create procedure MoveImage(@imageId int, @newOrder int)
as
begin
    -- Finding the related gallery
    declare @galleryId int;
    select @galleryId = GalleryId
    from Images
    where ImageId = @imageId

    -- Finding the count of images inside this gallery
    declare @mediaCount int;
    select @mediaCount = COUNT(ImageId)
    from Images
    where GalleryId = @galleryId

    -- Finding the current order of the image
    declare @currentOrder int;
    select @currentOrder = [Order]
    from Images
    where ImageId = @imageId

    -- Temporary shifting the current media to one order above all, to bypass the 'Each Media Should Have a Unique Order in its Gallery' unique index
    update Images
    set [Order] = @mediaCount + 1
    where ImageId = @imageId

    -- Shifting all media of the gallery between the current order and the new order, one order forward, or backward
    if @newOrder < @currentOrder
    begin
        update Images
        set [Order] = [Order] + 1
        where GalleryId = @galleryId and [Order] >= @newOrder and [Order] <= @currentOrder
    end
    else
    begin
        update Images
        set [Order] = [Order] - 1
        where GalleryId = @galleryId and [Order] <= @newOrder and [Order] >= @currentOrder
    end

    -- Inserting the image at the specified order
    print @newOrder
    update Images
    set [Order] = @newOrder
    where ImageId = @imageId
end
go

It works, just fine (at least as much as I've tested it). However, I don't feel Okay with this procedure, I think it might become easier and more effective. Can anyone improve this T-SQL code?

PS: parameters are checked before being passed to this procedure, so presume that there is nothing wrong with parameters, like negative @newOrder, etc.

There is a much, much, much easier way to do this. You can use real values for order, so when you want to move the row from position 16 to position 7 you give it an order value which is the average between the order values of rows 6 and 7.

The precision of real numbers is huge, and I presume that the re-orderings of images in your database will be happening at human reaction speeds, so you probably won't run into precision problems during the remainder of the expected lifetime of the universe. But if you are really insecure about the possibility of precision problems, you can rectify your table every once in a while, by reading the rows sorted by their order, and writing them into a new table, re-assigning the order values by copying them from an integer identity field. Then you delete the old table and rename the new table to the old name.

I would consider changing the structure of your table to use a self-referencing foreign key that refers to the previous item.

This makes it trivial to change the position of an item within the sequence, or to insert/remove items.

In order to query the items in the correct order, you would need to use a recursive Common Table Expression.

Below is an example table structure along with a recursive CTE:

create table #Data
(
    DataID int not null primary key,
    Value varchar(50) not null,
    ParentDataID int references #Data (DataID) -- optionally put a unique constraint on this column in order to enforce only one child record
)

-- sorted order is 1, 4, 7, 9, 2, 5, 3, 8, 6
insert into #Data values
    (1, 'One', null),
    (2, 'Two', 9),
    (3, 'Three', 5),
    (4, 'Four', 1),
    (5, 'Five', 2),
    (6, 'Six', 8),
    (7, 'Seven', 4),
    (8, 'Eight', 3),
    (9, 'Nine', 7)
    ,(101, 'One Hundred One', null),
    (102, 'One Hundred Two', 109),
    (103, 'One Hundred Three', 105),
    (104, 'One Hundred Four', 101),
    (105, 'One Hundred Five', 102),
    (106, 'One Hundred Six', 108),
    (107, 'One Hundred Seven', 104),
    (108, 'One Hundred Eight', 103),
    (109, 'One Hundred Nine', 107)

;

with SortedData (DataID, Value, RootID, OrderNumber) as
(
    select
        DataID,
        Value,
        DataID,
        1
    from #Data
    where
        ParentDataID is null
        or ParentDataID = DataID

    union all

    select
        #Data.DataID,
        #Data.Value,
        SortedData.RootID,
        SortedData.OrderNumber + 1
    from #Data
    inner join SortedData on
        SortedData.DataID = #Data.ParentDataID
)
select *
from SortedData
order by RootID, OrderNumber

(EDIT: I've rearranged the content of my answer.  Code examples that used to be here are now at the bottom, because I feel that the easier approach is to use the trigger that I've written, shown below)

The code below is for an "instead of insert, update, delete" trigger on the table that will automatically perform the necessary "shifting" operations when records are inserted/updated/deleted.

Note that I've changed the name of the table in my example from #Data to SortableData, because triggers cannot be added to temporary tables.

EDIT: The original trigger code was unable to handle contiguous rows being added/moved/removed from the sequence.  I've now revised the trigger code to handle those scenarios

create trigger trig_SortableData on SortableData instead of insert, update, delete as begin

-- first, store a list of records that are to come after the records that are being added/moved
declare @ChildData table
(
    ChildDataID int,
    ParentDataID int
)
;

with DeletedSorted (DataID, ParentDataID, RootDataID) as
(
    select
        DataID,
        ParentDataID,
        ParentDataID
    from Deleted
    where
        not exists (
            select 1
            from Deleted d
            where
                d.DataID = Deleted.ParentDataID
        )

    union all

    select
        Deleted.DataID,
        Deleted.ParentDataID,
        DeletedSorted.RootDataID
    from Deleted
    inner join DeletedSorted on
        DeletedSorted.DataID = Deleted.ParentDataID
),
InsertedSorted (DataID, ParentDataID, LeafDataID) as
(
    select
        DataID,
        ParentDataID,
        DataID
    from Inserted
    where
        not exists (
            select 1
            from Inserted i
            where
                i.ParentDataID = Inserted.DataID
        )

    union all

    select
        Inserted.DataID,
        Inserted.ParentDataID,
        InsertedSorted.LeafDataID
    from Inserted
    inner join InsertedSorted on
        Inserted.DataID = InsertedSorted.ParentDataID
)
-- insert those records into the table variable along with the last DataID of the records being added/moved
insert into @ChildData
select
    SortableData.DataID,
    isnull(DeletedSorted.RootDataID, InsertedSorted.LeafDataID)
from SortableData
inner join InsertedSorted on
    InsertedSorted.ParentDataID = SortableData.ParentDataID
left outer join DeletedSorted on
    DeletedSorted.DataID = SortableData.ParentDataID
where
    not exists (
        select 1
        from Inserted
        where
            Inserted.DataID = SortableData.DataID
    )

-- and disengage those records from their current parent
-- Performing this update may be necessary if there is a unique constraint on ParentDataID
update d set
    d.ParentDataID = null
from SortableData d
inner join @ChildData c on
    c.ChildDataID = d.DataID

-- next, update any records that are being moved/deleted; put them after their new parent record
update d set
    d.ParentDataID = Inserted.ParentDataID
from SortableData d
inner join Deleted on
    Deleted.DataID = d.DataID
left outer join Inserted on
    Inserted.DataID = d.DataID
;

with DeletedSorted (DataID, ParentDataID, RootDataID) as
(
    select
        DataID,
        ParentDataID,
        ParentDataID
    from Deleted
    where
        not exists (
            select 1
            from Deleted d
            where
                d.DataID = Deleted.ParentDataID
        )

    union all

    select
        Deleted.DataID,
        Deleted.ParentDataID,
        DeletedSorted.RootDataID
    from Deleted
    inner join DeletedSorted on
        DeletedSorted.DataID = Deleted.ParentDataID
),
InsertedSorted (DataID, ParentDataID, LeafDataID) as
(
    select
        DataID,
        ParentDataID,
        DataID
    from Inserted
    where
        not exists (
            select 1
            from Inserted i
            where
                i.ParentDataID = Inserted.DataID
        )

    union all

    select
        Inserted.DataID,
        Inserted.ParentDataID,
        InsertedSorted.LeafDataID
    from Inserted
    inner join InsertedSorted on
        Inserted.DataID = InsertedSorted.ParentDataID
)
-- and revise those records that used to come after those records being moved in order to close the gap
update d set
    d.ParentDataID = isnull(InsertedSorted.LeafDataID, DeletedSorted.RootDataID)
from SortableData d
inner join DeletedSorted on
    DeletedSorted.DataID = d.ParentDataID
left outer join InsertedSorted on
    InsertedSorted.ParentDataID = DeletedSorted.RootDataID
where
    not exists (
        select 1
        from Deleted
        where
            Deleted.DataID = d.DataID
    )

-- and then actually remove those records that are being deleted
delete from SortableData
where
    exists (
        select 1
        from Deleted
        where
            Deleted.DataID = SortableData.DataID
    )
    and not exists (
        select 1
        from Inserted
        where
            Inserted.DataID = SortableData.DataID
    )

-- finally, insert any new records
insert into SortableData
select *
from Inserted
where
    not exists (
        select 1
        from Deleted
        where
            Deleted.DataID = Inserted.DataID
    )

-- and re-attach records to come after the added/moved records
update d set
    d.ParentDataID = c.ParentDataID
from SortableData d
inner join @ChildData c on
    c.ChildDataID = d.DataID

end

I've tested this trigger out with the following commands:

insert into SortableData values (10, 'Ten', 4)
update SortableData set ParentDataID = 1 where DataID = 5
delete from SortableData where DataID = 8
delete from SortableData where DataID = 6
insert into SortableData values (6, 'Six', 3)

I've also tested the following commands to add/move/remove multiple contiguous records in the sequence:

insert into SortableData values (10, 'Ten', 4), (11, 'Eleven', 10), (12, 'Twelve', 11)

delete from SortableData where DataID in (5,3)

update d set
    d.ParentDataID = u.ParentDataID
from SortableData d
inner join (
              select 9 as DataID,   1 as ParentDataID
    union all select 2,           8
    union all select 8,           9
) u on
    u.DataID = d.DataID

Also, below is a line to add a unique constraint on the ParentDataID column; this ensures that the non-null values are unique, but allows multiple nulls.  This allows you to store multiple sequences in the table; each record with a null ParentDataID field is a root.

create unique index uq_SortableData_ParentDataID on SortableData (ParentDataID) where ParentDataID is not null

The code examples below are from previous versions of my answer.  These demonstrate how to insert, move, and remove a single record in a sequence.  However, I would prefer to use the trigger shown above because it makes these complex operations unnecessary.

Below is some code that demonstrates inserting a new record into an arbitrary position.  Similar code would be needed in order to change the position of an existing record.  Alternatively, the code shown below could possibly be modified and implemented as an "instead of insert" trigger.

-- @DataID, @Value, and @ParentDataID should be parameters of the insert command
-- They are defined here as variables for the sake of testing
declare @DataID int
declare @Value varchar(50)
declare @ParentDataID int

-- These values will insert a new record, "Ten", after the record "Four"
set @DataID = 10
set @Value = 'Ten'
set @ParentDataID = 4

-- This code assumes that there is a unique constraint on ParentDataID
declare @ChildDataID int

-- first, update the current record that comes after "Four"
-- set ParentDataID to null so that we can put the new record in its place (the unique constraint makes this necessary)
-- also capture the DataID of this record in the @ChildDataID variable
-- The unique constraint on ParentDataID ensures that this update statement will only affect one record.
-- If there is not a unique constraint on ParentDataID, then this approach could corrupt the data.
update #Data set
    @ChildDataID = DataID,
    ParentDataID = null
where
    ParentDataID = @ParentDataID

-- insert the new record.
insert into #Data values (@DataID, @Value, @ParentDataID)

-- now update the previous record again; set the ParentDataID to the DataID of the newly inserted record
-- this ensures that the record that used to come after "Four" will now come after the newly inserted record
update #Data set
    ParentDataID = @DataID
where
    DataID = @ChildDataID

Below is an example of moving a record to a different position within the sequence.  In this case, it is moving record "Five" to come after record "One":

-- Move record "Five" to come after "One"

-- @DataID and @ParentDataID should be parameters of the update command
-- They are defined here as variables for the sake of testing
declare @DataID int
declare @ParentDataID int

-- These values will move the record "Five" to come after the record "One"
set @DataID = 5
set @ParentDataID = 1

-- This code assumes that there is a unique constraint on ParentDataID
declare @ChildDataID int

-- first, update the current record that comes after "One"
-- set ParentDataID to null so that we can put the new record in its place (the unique constraint makes this necessary)
-- also capture the DataID of this record in the @ChildDataID variable
-- The unique constraint on ParentDataID ensures that this update statement will only affect one record.
-- If there is not a unique constraint on ParentDataID, then this approach could corrupt the data.
update #Data set
    @ChildDataID = DataID,
    ParentDataID = null
where
    ParentDataID = @ParentDataID

declare @OriginalParentDataID int

update #Data set
    @OriginalParentDataID = ParentDataID,
    ParentDataID = @ParentDataID
where
    DataID = @DataID

-- update the record that comes after the record being moved
-- this record must now come after the record after which the record being moved originally came.
update #Data set
    ParentDataID = @OriginalParentDataID
where
    ParentDataID = @DataID

update #Data set
    ParentDataID = @DataID
where
    DataID = @ChildDataID

Finally, this last code example demonstrates removing a record from the sequence.  In this case, it is removing record "Eight":

-- Remove record "Eight"

-- @DataID should be a parameter of the delete command
-- It is defined here as a variable for the sake of testing
declare @DataID int

-- This value will remove the record "Eight"
set @DataID = 8

declare @OriginalParentDataID int

update #Data set
    @OriginalParentDataID = ParentDataID,
    ParentDataID = null
where
    DataID = @DataID

-- update the record that comes after the record being moved
-- this record must now come after the record after which the record being moved originally came.
update #Data set
    ParentDataID = @OriginalParentDataID
where
    ParentDataID = @DataID

delete from #Data where DataID = @DataID


Efficiently checking if a number is divisible by 3 I'm looking for code review, best practices and optimizations.

public final class DivThreeEfficiently {

    private DivThreeEfficiently() {}

    /**
     * Returns true if the input number is divisible by three.
     * Else returns false.
     *
     * @param n     the input number
     * @return      true if input number is divisible by three
     */
    public static boolean isMultipleOfThree(int n) {
        if(n < 0) n = -n;

        int evenCtr = 0;
        int oddCtr = 0;

        while (n != 0) {
            if ((n & 1) == 1) {
                oddCtr++;
            }
            n = n>>1;
            if ((n & 1) == 1) {
                evenCtr++;
            }
            n = n>>1;
        }

        return evenCtr == oddCtr;
    }
}

public class DivThreeEfficientlyTest {

    @Test
    public void testEvenNegative() {
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-3));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-6));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-12));
    }

    @Test
    public void testEvenPositive() {
        assertTrue(DivThreeEfficiently.isMultipleOfThree(0));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(3));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(6));
    }

    @Test
    public void testOddNegative() {
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-1));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-4));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-11));
    }

    @Test
    public void testOddPositive() {
        assertFalse(DivThreeEfficiently.isMultipleOfThree(1));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(4));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(11));
    }
}

Computers aren't humans.  A human might find it easiest to apply a divisibility rule.  A computer, though, doesn't care.

The simplest code would be to check n % 3 == 0.  The modulo operator uses the JVM opcode irem, which is about as efficient as you can get.

On an Intel CPU, irem is probably implemented using the IDIV (signed divide) instruction.  On most modern x86-compatible processors, IDIV with a 32-bit operand uses 10 to 30 micro-operations and has a latency of 20 to 61 clock cycles.  More importantly, the trend on newer and more powerful hardware is for IDIV to take fewer clock cycles.  In other words, writing the program as if it were a RISC processor is a counterproductive "optimization" — it would be better to let the hardware perform the division operation to its full potential.

For comparison…

javap -c DivThreeEfficiently

public final class DivThreeEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0
       1: ifge          7
       4: iload_0
       5: ineg
       6: istore_0
       7: iconst_0
       8: istore_1
       9: iconst_0
      10: istore_2
      11: iload_0
      12: ifeq          46
      15: iload_0
      16: iconst_1
      17: iand
      18: iconst_1
      19: if_icmpne     25
      22: iinc          2, 1
      25: iload_0
      26: iconst_1
      27: ishr
      28: istore_0
      29: iload_0
      30: iconst_1
      31: iand
      32: iconst_1
      33: if_icmpne     39
      36: iinc          1, 1
      39: iload_0
      40: iconst_1
      41: ishr
      42: istore_0
      43: goto          11
      46: iload_1
      47: iload_2
      48: if_icmpne     55
      51: iconst_1
      52: goto          56
      55: iconst_0
      56: ireturn
}

Div3MoreEfficiently.java

public class Div3MoreEfficiently {
    private Div3MoreEfficiently() {}

    public static boolean isMultipleOfThree(int n) {
        return n % 3 == 0;
    }
}

javap -c Div3MoreEfficiently

public class Div3MoreEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0
       1: iconst_3
       2: irem
       3: ifne          10
       6: iconst_1
       7: goto          11
      10: iconst_0
      11: ireturn
}

Did you make sure that the division is your bottleneck? In most cases a smart compiler/JITer will optimize that to a multiplication and won't take much cycles of your program.

In case that really slows your program down, you can use the solution here. It uses the fact that if the sum of all digits of a number in base N divides a divisor M of N-1 then that number is divisible by M. The original version deals with unsigned numbers so we need a little change

private static int reduce(int i) {
    if (i >= 6)
        return reduce((i >> 2) + (i & 0x03));
    else
        return i; // Done.
}

public static boolean isMultipleOfThree(int i) {
    if (i < 0) i = -i;
    // Sum of digits in base 4
    i = (i >> 16) + (i & 0xFFFF);
    i = (i >> 8) + (i & 0xFF);
    i = (i >> 4) + (i & 0xF);
    i = reduce(i);
    return i == 0 || i == 3;
}

You can also do it in base 16 but it'll take more comparisons and maybe not faster than this version.


Keypress function conditional How can I combine these if statements to make this a little cleaner and be less repetitive?

$(document).keydown(function(e){
    if (e.keyCode == 38) {
        if($html.hasClass('client-loading') || canAnim === false) {
            return false;
        }
        var $prevProj = $('.project-current').prev('.project');
        $prevProj.click();
    }

    if (e.keyCode == 40) {
        if($html.hasClass('client-loading') || canAnim === false) {
            return false;
        }
        var $nextProj = $('.project-current').next('.project');
        $nextProj.click();
    }

    // Prevent rapid clicking
    if ( e.keyCode == 38 || e.keycode == 40 ) {
        canAnim = false;

        setTimeout(function(){
            canAnim = true;
        },2000);
    }
});

Here's another one, just for the heck of it

$(document).keydown(function (e) {
  var current;

  // return early
  if( e.keyCode !== 38 && e.keyCode !== 40 ) {
    return false;
  }

  // again, return early
  if( $html.hasClass('client-loading') || canAnim === false ) {
    return false;
  }

  current = $('.project-current');

  if( e.keyCode === 38 ) {
    current.prev('.project').click();
  }

  if( e.keyCode === 40 ) {
    current.next('.project').click();
  }

  canAnim = false;
  setTimeout(function () { canAnim = true; }, 2000);
});

The switch statement is made exactly for this kind of case.

$(document).keydown(function(e){
    var $proj;
    switch (e.keyCode) {
        case 38:
            if($html.hasClass('client-loading') || canAnim === false) {
                return false;
            }
            $proj = $('.project-current').prev('.project');
            break;

        case 40:
            if($html.hasClass('client-loading') || canAnim === false) {
                return false;
            }
            $proj = $('.project-current').next('.project');
            break;

        // Prevent rapid clicking
        case 38:
        case 40:
            canAnim = false;

            setTimeout(function(){
                canAnim = true;
            },2000);
            break;
    }

    $proj.click();
});

You can also notice the small refactoring I applied. Keeps some common stuff out of the switch, so that less code is in each case.


Find all subsets of an int array whose sums equal a given target I am trying to implement a function below:

  Given a target sum, populate all subsets, whose sum is equal to the target sum, from an int array.

For example:

Target sum is 15.

An int array is { 1, 3, 4, 5, 6, 15 }.

Then all satisfied subsets whose sum is 15 are as follows:

15 = 1+3+5+6
15 = 4+5+6
15 = 15

I am using java.util.Stack class to implement this function, along with recursion.

GetAllSubsetByStack class

import java.util.Stack;

public class GetAllSubsetByStack {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 15;

    private Stack<Integer> stack = new Stack<Integer>();

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;

    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        *
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                sumInStack -= (Integer) stack.pop();
            }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }
}

Main class

public class Main {

    private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
        14, 15 };

    public static void main(String[] args) {
        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}

Output in Console is as follows:

15 = 1+3+4+5+2
15 = 1+3+4+7
15 = 1+3+5+6
15 = 1+3+2+9
15 = 1+3+11
15 = 1+4+2+8
15 = 1+4+10
15 = 1+5+2+7
15 = 1+5+9
15 = 1+6+8
15 = 1+14
15 = 3+4+6+2
15 = 3+4+8
15 = 3+5+7
15 = 3+2+10
15 = 4+5+6
15 = 4+2+9
15 = 4+11
15 = 5+2+8
15 = 5+10
15 = 6+2+7
15 = 6+9
15 = 2+13
15 = 7+8
15 = 15

Please help me with the following 2 things:

How can I improve this code to reduce the times for recursion? Is sorting the int array (from high to low) before recursion a better way?
Is there a way to improve the code without using recursion?

There are three reasonable responses here:

yes, your recursion code can be improved for performance.
yes, part of that improvement can come from sorting the data.
yes, there's a way to refactor the code to not use recursion, and it may even be faster.

Bearing that in mind, this answer becomes 'complicated'.

Basic performance improvements for current code:

if (sumInStack == TARGET_SUM) {
    print(stack);
}

can easily be:

if (sumInStack >= TARGET_SUM) {
    if (sumInStack == TARGET_SUM) {
        print(stack);
    }
    // there is no need to continue when we have an answer
    // because nothing we add from here on in will make it
    // add to anything less than what we have...
    return;
}

I dislike any recursive function which rely on external (outside-the-method) values. In your case, the sumInStack is external. This makes the target hard to 'see'.

Additionally, if we do sort the data, there are some benefits we can have, and a way to restructure the recursion to make it do less work (since we can guarantee that all values after a point have certain properties...):

consider the method (assuming sorted data):

public void populateSubset(final int[] data, int fromIndex,
                           final int[] stack, final int stacklen,
                           final int target) {
    if (target == 0) {
        // exact match of our target. Success!
        printResult(Arrays.copyOf(stack, stacklen));
        return;
    }

    while (fromIndex < data.length && data[fromIndex] > target) {
        // take advantage of sorted data.
        // we can skip all values that are too large.
        fromIndex++;
    }

    while (fromIndex < data.length && data[fromIndex] <= target) {
        // stop looping when we run out of data, or when we overflow our target.
        stack[stacklen] = data[fromIndex];
        populateSubset(data, fromIndex + 1, stack, stacklen + 1, target - data[fromIndex]);
        fromIndex++;
    }
}

You would call this function with:

Arrays.sort(data);
populateSubSet(data, 0, new int[data.length], 0, 15);

So, that is 'can the code be improved?' and 'will sorting help'

As for the 'unrolled' (no recursion) version of the system, it can be done. It would require three int[] arrays:

int[] data = {....}
int[] sum = new int[data.length];
int[] indices = new int[data.length];
int depth = 0;
int lastindex = -1;

The sum gives and indices act like a stack, and the depth is how deep the stack is (again, assume sorted data):

Arrays.sort(data);
while (depth >= 0) {
    lastindex++;
    if (lastindex == data.length) {
        // we have run out of data.
        do {
            // walk up the stack till we find some data.
            depth--;
        while (depth >= 0 && (lastindex = indices[depth] + 1) < data.length);
    }
    if (depth >= 0) {
         .....
         you then add your code in here to check the target,
         keep it updated in your 'stack'.
         go down a level and move on....
    }

}

Another way to do problems like this — investigating properties of all subsets (that is, members of the "power set") — is to think of the main set as a list of cells, and each cell as a binary digit position. A member of the power set can therefore be described by a binary number, such that the subset contains only those elements of the set corresponding to a 1 in the binary value.

By doing that, you can generate the power set just by counting. Of course this gets a little complicated when the original set has more values in it that can be comfortably dealt with by the native integer type in a given programming language, but Java has BigInteger. (Enumerating a power set for any purpose is going to be a little painful for original sets that big anyway.)


Beauty salon site in HTML 5 First time working with html 5 so far. Am I using my markup correctly thus far?
Semantically correct that is?

    <!doctype html>

    <title>Salon Sociel | Hair-Nails-Unisex</title>
    <meta charset="utf-8">
    <link rel="stylesheet" href="style/main.css">

Salon Sociel

Hair-Nails-Unisex

Home

About

Services

Products

Portfolio

Contact

Friends

Welcome to Our Salon Sociel

featured

Keratin

footer

meta-charset should come before title

The meta-charset element would ideally be the first element in head (details about the order in head).

So it could be:

  <meta charset="utf-8">
  <title>Salon Sociel | Hair-Nails-Unisex</title>
  <link rel="stylesheet" href="style/main.css">

Wrong use of section and h3

You have:

Salon Sociel

Hair-Nails-Unisex

Neither is the section correct here (it only contains headings, and by using it the h1 is no longer the heading of the body), nor is it correct to use a heading element for a subheading (details).

So it should simply be:

Salon Sociel

Hair-Nails-Unisex

(Your structure would have been correct if using hgroup instead of section, but this element was removed from W3C’s HTML.)

The w3c html validator reports several issues with this HTML.
I suggest to start by clearing those.

Keep re-verifying using the validator until there are no more validations, and your HTML will be in much better shape.


Using `from select`-syntax to pass through elements from a collection unmodified While working on a project with a friend of mine, I noticed the following syntax:

public IObservable<X> GetXs()
{
    return from x in xs
           select x;
}

He said that while xs is an IObservable<X> field, this is the way it is supposed to be written in Linq, and everyone does it this way. It also allows one to add where-clauses later on easily.

On the other hand, Reflector shows that a new delegate is created that is passed to the Select() function on the observable, but that function always returns just this, so it seems to me it also has a slight overhead.

So I don't agree with him and would have written it as follows:

public IObservable<X> GetXs()
{
    return xs;
}

Are there any other reasons for using the from select-syntax without filtering, selecting or ordering that I might have missed? Which syntax is better and why?

I don't personally use RX, so my answer may be wrong, but he is it anyway:

I don't know whether “everyone does it this way”, but I doubt it. The code is translated into (after LINQ query transformation and by writing extension method invocation as if it was a normal method):

return Observable.Select(xs, x => x);

Observable.Select does exactly what you would expect it to, if you know LINQ to objects: it creates a new observable, which consumes each item from xs, processes it using the delegate you gave it (which in this case just returns the item unchanged) and then produces the result.

So, using that code does have some overhead, but it will be most likely negligible for you and you shouldn't worry about it much. But it does make the code longer and more confusing (it did confuse you). And “there is a chance it will save you some typing in the future” is not a good reason to sacrifice readability, I think.

Based on my understanding the first option is going to create a whole new enumerable object (as well as a linq iterator object) as well as the overhead of calling a function for each element.  I would definitely go with the second (your) option.  If you need where filtering later, then add it later on.

This next part definitely applies when returning a type of IEnumerable, I can't say 100% for an IObservable, but that LINQ syntax is lazily evaluated.  If the return value is NOT used right away but saved for later and the state of xs has changed when you go to use it you might get unexpected results if you don't force the evaluation right away after returning from the function.


Validating the model outside of the controller in ASP.NET I wasn't quite sure whether I should do it this way or create a validation service and inject it, but this works:
Controller:
[HttpPost]
public async Task<IActionResult> NewUser(NewUsertVm viewModel)
{
    if (UserValidator.NewUserIsValid(viewModel, ModelState) == false)
    {
        return View(nameof(NewUser), viewModel);
    }

// Code omitted for brevity
}

UserValidatorClass
public static bool NewUserIsValid(NewUserVm viewModel, ModelStateDictionary modelState)
{
    if (string.IsNullOrEmpty(viewModel.RefOne) && string.IsNullOrEmpty(viewModel.RefTwo) && string.IsNullOrEmpty(viewModel.RefThree))
    {
        var validationMessage =
            "At least one of either the first, second or third ref numbers must be entered to add a new user. Please enter one of these numbers and try again.";
        modelState.AddModelError(nameof(viewModel.RefOne), validationMessage);
    }

    var regEx = new Regex("(^\\d{10}$)");

    if (viewModel.RefOne != null)
    {
        if (!regEx.IsMatch(viewModel.RefOne))
        {
            var validationMessage =
                "Ref One must be 10 digits and contain only numbers.";
                modelState.AddModelError(nameof(viewModel.RefOne), validationMessage);
        }
    }

    return modelState.IsValid;
}

The idea behind the validator is that it needs to ensure at least one of the three properties are not null (RefOne, RefTwo & Ref Three. Property names have been changed for post). If RefOne is used, it needs to match the RegEx pattern.
This appears to work as intended but is there a better way of achieving the same result?

Validating the model outside of the controller in ASP.NET:
Model validation with Data Annotations, the MVC framework will usually automated to handle the performance of actual validation and results to the end-user.
To validate the model outside of controller,we can create a sample of console application into the same application or in other application also.
Here,We are using class named User model:

using System.ComponentModel.DataAnnotations;
namespace ValidateExample
{
    public class User
    {
        [Required]
        [StringLength(20)]
        public string FirstName { get; set; }

        [Required]
        [StringLength(25, MinimumLength = 3)]
        public string LastName { get; set; }

        [Required]
        [EmailAddress]
        public string EmailAddress { get; set; }
    }
}

I have created, within the same Solution, a Console App project.Here's our Console App:

using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using ValidateExample.Models;

namespace ValidateExample
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Starting validation:");

            User user = new User();
            user.FirstName = null;
            user.LastName = "aaa";
            user.Emailaddress = "eg@exam@example";

            var context = new ValidationContext(user, null, null);
            var results = new List<ValidationResult>();

            var isValid = Validator.TryValidateObject(user, context, results, true);

            if (!isValid)
            {
                Console.WriteLine("User is not valid! Errors are:");
                foreach (var validationResult in results)
                {
                    Console.WriteLine(validationResult.ErrorMessage);
                }
            }
            Console.WriteLine("Validation Complete...");
            Console.ReadKey();
        }
    }
}

We simply created a model named User and made some data-annotations in it.Then,In console class We putted some invalid values to test the application.
Here,We called the Validator.TryValidateObject() this function which validate the model according to the data-annotations.
Run the apllication :
The Console Output :-

Starting validation:
User is not valid! Errors are:
The FirstName field is required.    //(as We assigned null to FirstName field)
The EmailAddress field is not a valid email address.


Implement a function to check if a tree is balanced Yet another interview question:

  Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

First off, did I understand the question correctly? In other words, we are looking for a subtree in a tree (or rotation of it) that looks like:

     root
    /    \
 leaf_1  leaf_2
  /
leaf1_1

My initial idea was to count the depth of the tree and check if maxDepth - minDepth < 2 (which requires 2 traversal) . But I think I found a more efficient solution. The trade-off is that we should keep the ref to the root. I assume n-ary tree.

Is this correct?

import java.util.LinkedList;

public class Trees {

    Node threeRoot;
    private boolean isBalanced = true;

    Trees(Node threeRoot){
        this.threeRoot = threeRoot;
    }

    static class  Node{
        public Node root;
        public LinkedList<Node> children = new LinkedList<>();
    }

     boolean isBalanced(Node node){
       if (threeRoot == null) {
            isBalanced = true;
        }
        if (threeRoot.children == null || threeRoot.children.isEmpty()) {
            isBalanced = true;
        }

        isBalancedRed(node);
        return isBalanced;
    }

     void isBalancedRed(Node node) {
        if (node.children.isEmpty()) {
            if (node.root != null && node.root.children.size() == 1) {
                isBalanced = false;
            }
        }
        for(Node nodeEl : node.children)
        {
            isBalancedRed(nodeEl);
        }
    }

    public static void main(String[] args){
        Trees tree = new Trees(new Node());
        Node root = tree.threeRoot;
        Node leaf1 = new Node();
        Node leaf2 = new Node();
        Node leaf11 = new Node();

        root.children.add(leaf1);
        leaf1.root = root;
        root.children.add(leaf2);
        leaf2.root = root;

        leaf2.children.add(leaf11);
        leaf11.root = leaf2;

        System.out.println(tree.isBalanced(root));
    }
}

First off, I would use something other than a LinkedList to hold the children of an n-ary tree. A LinkedList requires you to enumerate the list in order to get the reference to any child other than the leftmost, which is going to slow you down.

Second, your code is basically returning false in any situation where the Node's parent has one child that itself doesn't have any children. In your example tree, that's the exact case (you have two children of the root, one of which has another child) but the tree is balanced according to the rules, so I would expect this algorithm to return a lot of false positives (and negatives).

Finding the depth of an n-ary tree is a linear-bound operation; you traverse each branch of the tree recursively, finding the depth at each leaf node. You can find both the maximum and minimum depth in one traversal; at each level, ask each branch for its maximum and minimum depth, passing the depth of the current node. The base case is that of a leaf node (no children); the min and max is the depth of that leaf. You can store this result in a Tuple or in a more specialized MinMax struct, as you please. With those results returned to the calling level, scan them to find the lowest Min and the greatest Max, and return that to the caller.

Here's a basic implementation:

public class MinMax<T>
{
    private T minVal;
    private T maxVal;

    public MinMax(T min, T max)
    {
       minVal = min;
       maxVal = max;
    }

    public T min() {return minVal;}
    public T max() {return maxVal;}
}

private MinMax<Integer> GetMinMaxDepth(Node node, int currDepth)
{
    //base case; no children. Max and min depth at this leaf is currDepth.
    if(node.children == null || node.children.size() == 0)
       return new MinMax<Integer>(currDepth, currDepth);

    //determine the maximum and minimum depth of all child branches,
    //and track the absolute max and min across all of them.
    int min = Integer.MAX_VALUE, max = -1;
    for(Node nextNode : node.children)
    {
        MinMax<Integer> childDepth = GetMinMaxDepth(nextNode, currDepth+1);
        if(childDepth.min() < min) min = childDepth.min();
        if(childDepth.max() > max) max = childDepth.max();
    }

    return new MinMax<Integer>(min, max);
}

boolean isBalanced()
{
    //easy cases; a tree with 0 or 1 elements.
    if(treeRoot == null || treeRoot.children == null || treeRoot.children.size() == 0)
       return true;
    //traverse the tree and find the minimum and maximum depth.
    MinMax<Integer> minMaxDepth = GetMinMaxDepth(treeRoot, 0);

    return minMaxDepth.max() - minMaxDepth.min() > 1;
}

This could probably be optimized in our case to return early if we discover that any node's child depths differ by more than 1. We could hack it by throwing an Exception, but the proper strategy is almost as easy to implement:

private MinMax<Integer> GetMinMaxDepth(Node node, int currDepth)
{
    //base case; no children. max and min depth at this leaf is currDepth.
    if(node.children == null || node.children.size() == 0)
       return new MinMax<Integer>(currDepth, currDepth);

    //determine the maximum and minimum depth of all child branches,
    //and track the absolute max and absolute minimum.
    int min = Integer.MIN_VALUE, max = -1;
    for(Node nextNode : node.children)
    {
        MinMax<Integer> childDepth = GetMinMaxDepth(nextNode, currDepth+1);
        //Exit now if child is unbalanced
        if(childDepth.max() - childDepth.min() > 1) return childDepth;
        if(childDepth.min() < min) min = childDepth.min();
        if(childDepth.max() > max) max = childDepth.max();
        //Exit now if current node is unbalanced
        if(max-min > 1) break;
    }

    return new MinMax<Integer>(min, max);
}

The upside is that we quit as soon as we know the answer to the question (is the tree unbalanced?), which will increase the average performance (but not the worst-case performance on a tree that is balanced or is unbalanced at its furthest extremities). The downside is that we no longer know how unbalanced the tree is; the MaxMin returned to the top level will always have a Max and Min that differ by the first detected difference greater than the threshold (probably 2), not the absolute difference in depth of leaf nodes in the tree.

The one case that is difficult to determine in an n-ary tree is that of a tree that never forks. This algorithm will find a depth difference between any two or more branches, but when there is only one branch, the maximum and minimum depths of the tree are the same and there's nothing to use for comparison. Technically, it would have only one "leaf" node (usually defined as a node with no children) and so by the given definition all (one) of the leaves are the same distance from the root, however if you looked at the map of an N-ary tree that was more like a linked list (or even a V or Y shape) and went deeper than two levels, you wouldn't call it balanced.

Perhaps a change in definition may be required; a node is a "leaf" node if it does not have N child nodes (where N is the order of the N-ary tree). So, in a quaternary tree (4 children per node), if any node has fewer than 4 children, then the depth of the current node is considered as a "minimum" depth and will almost certainly be the minimum depth at that level. That's another easy change:

private MinMax<Integer> GetMinMaxDepth(Node node, int currDepth)
{
    //base case; no children. max and min depth at this leaf is currDepth.
    if(node.children == null || node.children.size() == 0)
       return new MinMax<Integer>(currDepth, currDepth);

    //determine the maximum and minimum depth of all child branches,
    //and track the absolute max and absolute minimum.
    //Exit as soon as we know that this or any child node is unbalanced.
    int min = Integer.MIN_VALUE, max = -1;

    //If this node isn't "full", its depth is the minimum depth for this branch
    if(node.children.size < max_children) min = currDepth;

    for(Node nextNode : node.children)
    {
        MinMax<Integer> childDepth = GetMinMaxDepth(nextNode, currDepth+1);
        //check if child is already unbalanced
        if(childDepth.max() - childDepth.min() > 1) return childDepth;
        if(childDepth.min() < min) min = childDepth.min();
        if(childDepth.max() > max) max = childDepth.max();
        //check if current node is unbalanced
        if(max-min > 1) break;
    }

    return new MinMax<Integer>(min, max);
}

The return statement in isBalanced() should be:

return !( minMaxDepth.max() - minMaxDepth.min() > 1);


Convert Persian and Arabic digits to English I use the following utility method to convert Persian and Arabic digits to English using regex:

convertNumbers2English: function (string) {
    return string.replace(/[٠١٢٣٤٥٦٧٨٩]/g, function (c) {
        return c.charCodeAt(0) - 1632;
    }).replace(/[۰۱۲۳۴۵۶۷۸۹]/g, function (c) {
       return c.charCodeAt(0) - 1776;
   });
}

Be nice to the maintenance programmer, even (especially?) if you expect it to be you. If you're mixing characters which are visually indistinguishable but don't need to be literal self-representations, you can use Unicode escapes and hexadecimal offsets as so:

convertNumbers2English: function (string) {
    return string.replace(/[\u0660-\u0669]/g, function (c) {
        return c.charCodeAt(0) - 0x0660;
    }).replace(/[\u06f0-\u06f9]/g, function (c) {
       return c.charCodeAt(0) - 0x06f0;
   });
}

Just that small change accomplishes the following:

I can easily see that I haven't missed any digits without having to count;
I can easily see that I haven't accidentally mixed digits from the two styles;
I can easily see that the offset subtracted is correct in each case;
I can easily see that the values returned by the anonymous functions are integers from 0 to 9 and not strings or codepoints corresponding to '0' to '9', which is useful if I'm not primarily a JS developer;
If I care about squeezing every last byte out of my JS, I can see a way to combine the two into one:

convertNumbers2English: function (string) {
    return string.replace(/[\u0660-\u0669\u06f0-\u06f9]/g, function (c) {
        return c.charCodeAt(0) & 0xf;
    });
}

The minimiser should take care of unescaping the Unicode escapes.
It might be slightly easier for me to find which characters they are, because I can look up the hex values in a Unicode character table.

for convert Persian or Arabic number to English number:
const convertToEnglish = (elem) => {
  const p2e = (elem) => elem.replace(/[۰-۹]/g, (digit) => "۰۱۲۳۴۵۶۷۸۹".indexOf(digit));
  const a2e = (elem) => elem.replace(/[٠-٩]/g, (digit) => "٠١٢٣٤٥٦٧٨٩".indexOf(digit));
  return p2e(a2e(s));
};
convertToEnglish("۱۲۳qwe۵۶۷asd")