Operator Search for Puzzle I was wondering if I could solve the problem here (mostly unrelated) using only simple binary operators since it is just mapping 100 different inputs to a boolean. For this I wrote this, but I have no real way to test, and I was also hoping it could be faster.

#include <iostream>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX_VAL 100

bool CODES[] = {1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1};

int op(int a, int b, int index) {
    switch (index) {
        case 0: return a + b; break;
        case 1: return a - b; break;
        case 2: return a * b; break;
        case 3: return a / b; break;
        case 4: return a & b; break;
        case 5: return a | b; break;
        case 6: return a ^ b; break;
        case 7: return a % b; break;
    }
}

int main(int argc, char const *argv[]) {
    for (int A=1; A < 2; A++) {
        std::cout << A << std::endl;
        for (int B=1; B < 2; B++) {
            std::cout << A << " " << B << std::endl;
            for (int C=1; C < 2; C++) {
                for (int D=1; D < MAX_VAL; D++) {
                    std::cout << A << " " << B << " " << C << " " << D << std::endl;
                    for (int E=1; E < MAX_VAL; E++) {
                        for (int opA = 0; opA < 8; opA++) {
                            for (int opB = 0; opB < 8; opB++) {
                                for (int opC = 0; opC < 8; opC++) {
                                    for (int opD = 0; opD < 8; opD++) {
                                        for (int opE = 0; opE < 8; opE++) {
                                            bool good = true;
                                            int index = 1;
                                            for (bool item : CODES) {
                                                int val = op(index, A, opA);
                                                val = op(val, B, opB);
                                                val = op(val, C, opC);
                                                val = op(val, D, opD);
                                                val = op(val, E, opE);
                                                val &= 1;
                                                if (val != item) {
                                                    good = false;
                                                    break;
                                                }
                                                index++;
                                            }
                                            if (good) {
                                                std::cout<<"GOOD "<<A<<" "<<opA<<" "<<B<<" "<<opB<<" "<<C<<" "<<opC<<" "<<D<<" "<<opD<<" "<<E<<" "<<opE<<std::endl;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

I am specifically looking for help for optimization, but of course style, correctness, or anything else is much appreciated.

Before we even get started into optimizations, I would like to point out a couple of things. First- many permutations of operands + operators are going to behave identically. There isn't a whole lot we can do to skip these, but in practice it seems that "similar" permutations are composed of "similar" components. That is, a handful of permutations of operands + operators that differ by 1 operand or operator will often have very similar input->output mappings. Some times you can take advantage of this to speedup your search. Sometimes the best solution is to do a completely random search of permutations to avoid the problem completely (at the cost of trying duplicate permutations). I won't explore either option below, but I wanted to mention them for completeness.

Secondly, you are trying to create a (int->bool) input->output mapping for 100 unique values. Even if we never tried two permutations of operands + operators that produce the same mapping, there's still 2^100 unique mappings to explore. That is not something that we can reasonably brute force. For 5 operands chosen (with replacement) from your 8 and 5 constants each in the range [0-99] inclusive, we have 8^5 * 100^5 == 3.27*10^14 == 2^48 permutations. Unless we are astronomically lucky, you're going to need to at least double your operand + argument count anyways. We need something smarter.

We need to try to prune the search space, but in order to do that we need to be able to determine early on whether a permutations is worth pursing. In the process of  restructuring your code to support such a heuristic, we're also going to gain a small performance boost. The following line of code is executed over and over for all 100 indices, and isn't going to change when you change opB, opC, and so on.

int val = op(index, A, opA);

This logic also applies to val = op(val, B, opB);, and the others. This isn't too bad- you're only losing a factor of 5 in performance, but it needs to be changed anyways to give our algorithm some foresight. We can reorder your loops to put the argument and operand together, and then compute the intermediate values immediately-

for (int A=1; A < 2; A++) {
    std::cout << A << std::endl;
    for (int opA = 0; opA < 8; opA++) {
        int valA[100];
        // compute val for all indices
        // Loop over B, C, D

This will allow us to compute the intermediate value of val exactly once- every time it is changed, rather than every time we change any operand / operator.

Now how does this help us prune the search space? Notice that for any mapping our operand constant is... constant. Together with the operator, they make a new (unary) operator. We can take this further as well- since all our new operators are "chained" together, they can be seen as one big (unary) operator.

input <operator> <operand_constant>  => output
input <new_operator> output
...
input <new_operator_A> <new_operator_B> => output
input <combined_operator> => output

The index itself is the only input and each index is unique, but each intermediate value/output might not be unique. Regardless of the index value, if two intermediate operations produce the same intermediate value, then both will produce the same output value. We can use this to prune the search space.

If two values in the array are identical, then their corresponding bits in the original array must both be the same. If they are not, immediately attempt the next operator / operand value. If you reduce your computations to unsigned chars spanning [0, 255] inclusive, the probability of having two equal intermediate values is roughly 0.999999999827. There will likely be many intermediate values with the same value, allowing you to quickly prune bad branches in the search tree.

To quickly determine if two values in the array cause a conflict, use an external array of size 256. When you compute an intermediate value v, check that array[v] is either uninitialized, or matches the desired output (map 0->1 and 1->2 maybe, and leave 0 to indicate uninitialized) and set the array element accordingly. If it doesn't match, then there's a conflict.

You could probably optimize this further by using a linked list to store the unique values of the array (every time array[v] is uninitialized), and then only check that those values are correct- avoiding redundant computations.

Even with this pruning, I suspect this will probably still be intractable. 2^100 is a huge number. You'll likely need to find a second way to check for "dead-end" branches, and/or an algorithmic breakthrough.


Variadic average function in C++ The following code was inspired from a tutorial I found online:

#include <cstdio>
#include <cstdarg>

double average_function(const int num_elements, ...)
{
    va_list elements;
    double sum = 0.0;

    va_start(elements, num_elements);
    for(int i = 0; i < num_elements; ++i) {
        sum += va_arg(elements, double);
    }
    va_end(elements);
    return sum / num_elements;
}

int main( int argc, char ** argv ) {

    printf("Average: %lf", average_function(5, 25.0, 35.7, 50.1, 127.6, 75.0));
    return 0;

}

I believe that the same can be done in many different ways.

Is there a better way to do the same without having as first arguments of the function the number of elements we want to sum? For example having instead a function to compute the average that have in its input only the set of elements we want to take into account without a their length?

One possibility would be to use an std::initializer_list:

#include <initializer_list>
#include <numeric>
#include <iostream>

double average(std::initializer_list<double> input) {
    double sum = std::accumulate(input.begin(), input.end(), 0.0);
    return sum / input.size();
}

int main() {
     std::cout << "Average: " << average({1, 2, 3, 4, 5, 6, 7, 8});
}

You could have the function take (for example) a vector instead, and it'd still work pretty much the same way (because vector already has a constructor that takes an initializer_list). Either way works out pretty much the same way though.

If you want to use just a list of numbers rather than having to add the {} around the list to force it into an initializer_list you can add var-args template function to wrap the call.

template<typename... Args>
double average(Args... args)
{
    return average({args...});
}

Looking at your code, a few things nearly jump out. First and foremost, you're using a C-style variable parameter list. This is mostly frowned upon in C++ for a number of reasons such as lack of type-safety. For example, if you'd accidentally passed your 25.0 as just 25, it'd be passed as an int instead of a double, and the whole thing would break.

The second is similar: using printf to print out the result has exactly the same problem for exactly the same reason (printf also uses a C-style variable parameter list).

Third, related to those but technically a separate issue (since it's about values, not types) is the problem you've apparently already noticed: it requires you to count the number of parameters. If you make a mistake, you get bad results (and if you tell it you're passing more parameters than you really do, undefined behavior).

Simply put, although your code won't compile as-is with a C compiler, it's still basically C-style code. It does nothing to fit with (or take advantage of) anything in C++ that wasn't a part of C 20+ years ago. If used correctly, it works, but it's all too easy to use it incorrectly.


Loading dictionary using trie in C very slow with large data set The code below works for very small dictionary files I used to test (two words).  However when I run this using a more typical dictionary file, my machine slows to the point of near crash.  I would like a review of what the potential bottleneck may be which I believe to be in the load() function. Of course, general comments are also welcomed if they may help with optimization and overall performance.

typedef struct node

{
    bool is_word;
    struct node* children[27];
}
node;

node* root;

int nwords = 0;

/**
* Returns true if word is in dictionary else false.
*/

bool check(const char* word)
{
    node* current = root;

    int i = 0;

    while(word[i] != '\0')
    {
        int letter = tolower(word[i]);

        if (letter == '\'')
        {
            return false;
        }

        if (current->children[letter-'a'] != NULL)
        {
            current = current->children[letter-'a'];
            i++;
        }

        else
        {
           return false;
        }
    }

    if (current->is_word == true)
    {
       return true;

    }

    return false;
 }

/**
 * Loads dictionary into memory.  Returns true if successful else false.
*/

bool load(const char* dictionary)
{

    FILE* dict = fopen(dictionary, "r");

    if(dict == false)
    {
       return false;
    }

    //initialize nodes

    root = calloc(27,sizeof(node));
    node* current = NULL;

    int c = 0;

    while(fgetc(dict) != EOF)
   {
       fseek(dict, -1, SEEK_CUR); //go back one byte to beginning of word
       current = root; //set index to root

       for(c = fgetc(dict); c != '\n'; c = fgetc(dict)) //iterate through word
       {
            if(current->children[c-'a'] == NULL)
            {
                current->children[c-'a'] = calloc(27,sizeof(node));
                current = current->children[c-'a'];
            }
            else
            {
                current = current->children[c-'a'];
            }
        }
        current->is_word = true; //once line break reached end the word
        nwords++;
    }

    fclose(dict);
    return true;
}

/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/

unsigned int size(void)
{
    return nwords;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */

void freeNode(node* current)
{
    for (int i = 0; i < 27; i++)
    {
        if(current->children[i] != NULL)
        {
            freeNode(current->children[i]);
        }
    }
    free(current);
}

bool unload(void)
{
    freeNode(root);
    return true;
}

A few notes:

typedef struct names are commonly written in PascalCase today.

Node* current = NULL;

Initialize your variables on the lowest scope as possible.  Therefore, declare your variables within your for loops. (C99)

for(int c = fgetc(dict); c != '\n'; c = fgetc(dict)) //iterate through word

Also, I feel as if you should be checking c for EOF, and then check for \n within the for loop.
The statements inside of your for loop look fishy to me:

if(current->children[c-'a'] == NULL)
{
    current->children[c-'a'] = calloc(27,sizeof(node))
    current = current->children[c-'a'];
}
else
{
    current = current->children[c-'a'];
}

No matter what, you are going to set children equal to current->children[c-'a'], so you can move that statement out of both branches of the conditional (DRY). Also, you should not be allocating 27 elements for every single Node.  Here is how I would write it:

if (!current->children[c-'a']) current->children[c-'a'] = calloc(1, sizeof(node));
current = current->children[c-'a'];

You can remove the != NULL part in your if conditional statements.
Avoid global variables: root and nwords.
Avoid magic numbers.

for (int i = 0; i < 27; i++)

Use a #define instead at the top of your code.

#define NUM_NODES 27

But where does the number 27 even come from?  Documentation would go a long way here to help developers understand what it is.
Set your Node values to NULL after you free them.  This is so that you do not try to access the data again after it has been freed.


Markov chain-based random text generator in Perl This is the first thing I've written in Perl besides one-liners. It just generates random text based on a text file. I was inspired by this. Any tips on making this better are welcome. I'd especially like to know if there are more idiomatic ways I could do certain things.

#!/usr/bin/env perl
use strict;
use warnings;
use File::Open qw(fopen);
use Data::Munge;

my $k = shift;                  # k-gram length
my $n = shift;                  # number of iterations
my $file = shift;
my $long_string = slurp fopen $file;

# loop through each k-gram; if no entry exists in %markov_chain,
# initialize it to an empty array. In either case, push the next
# k-gram into the array.

my %markov_chain;               # hash of arrays

for my $i (0 .. (length $long_string) - 1) {
  my $curr = substr $long_string, $i, $k;
  my $next = substr $long_string, $i + 1, $k;
  $markov_chain{$curr} //= [];
  push $markov_chain{$curr}, $next;
}

# Take the first k-gram from the original document. Draw a random
# k-gram from this k-gram's entry in %markov_chain. This will be the
# k-gram for the next iteration. Print the last character of the
# k-gram.

sub rand_elem { $_[rand @_] }

my $seed = substr $long_string, 0, $k;
print $seed;
for my $i (0 .. $n) {
  $seed = rand_elem @{$markov_chain{$seed}};
  print substr $seed, -1;
}

The only thing that comes to mind is the way you open the file.

You could do this instead:

open(my $file, "<", "$ARGV[0]") or die;
$data = do { local $/; <$file> };
close $file;

Which is a well known Perl idiom to read an entire file in one go.

For more info see these links

https://perlmaven.com/open-files-in-the-old-way

https://perlmaven.com/slurp

http://www.perlmonks.org/?node_id=20235


Summing sub arrays (maximal subarray) I have this piece of code, and I want to make if the way I'm calculating the time complexity is valid:

void traverse() {
    int currSum = 0;
    for(int i = 0; i < original.length; i++) {
        currSum = original[i];
        for(int j = i + 1; j < original.length; j++) {
            if(max <= currSum) {
                max = currSum;
            }
            currSum += original[j];
        }

        if(max <= currSum) {
            max = currSum;
        }
    }
}

I was thinking it'd be something along the lines of: (n - 1) + (n - 2) + (n - 3) ... etc but wasn't sure if that's correct.

The complexity of your void traverse () method is O(n^2).

The question is how many times if you have n-elements will currSum += original[j]; be performed.

To calculate that in this case you simply check how many times each loop will be executed.

The outer loop is n-times. Based on the length. Now the inner loop depends both directly and indirectly on the outer loop. As it will be performed n times based on the outer loop and (n/2)-1 times based on its condition.

So the total time is (n^2)/2-1 which is written O(n^2).

If this wasn't your question you should update it to make it more clear.

This is not a complete answer. If this satisifies as an answer then it should be moved to Stack Overflow. As it does not have anything to do with reviewing of code.

Some nitpick as well.

    if(max <= currSum) {
        max = currSum;
    }

Logically you would write it as

    if(currSum > max) {
        max = currSum;
    }

There is no real need to compare if they are equal and then give a new value (which will be equal to the old) if they are equal.

Now for the algorithm itself. If the problem is to find the maximum subarray I suggest you have a read over at Kadane's Algorithm, as it solves this in O(n) instead.

public int maxSubArray (int[] a) {
    int max = 0;
    int cur = 0;
    for (int i : a) {
        max = Math.max (i, max + i);
        cur = Math.max (cur, max);
    }
    return max;
}


ROT13 cipher challenge (HackerRank) I just started learning Ruby and thought that this relatively simple HackerRank challenge would be a good opportunity to try to write clean, tested and documented code without getting bogged down in very complex problems.

  In this challenge, your task is to write a method which takes an array of strings (containing secret enemy message bits!) and decodes its elements using ROT13 cipher system; returning an array containing the final messages.

I'd like to know if this follows the "Ruby Way" (I'm willing to bet it doesn't!) and I am open to improvements on all aspects of the code, including the documentation, which is meant to follow RDoc format.

I use Ruby v 2.4. Note that, coming from a mostly Python background, there may be some patterns that are very Python-like, if so please point out if there's a more Ruby way of doing it!

I am also planning to learn about TDD libraries with Ruby soon, for now using that short solution from Stack Overflow seemed sufficient for this exercise.

# AssertionError class & assert method copied from Stack Overflow
# https://stackoverflow.com/a/3264330/3626537
class AssertionError < RuntimeError
  # Extends RunTimeError
end

def assert &block
  # Evaluates whether the input block is true and raises AssertionError if not
  # +block+:: the block to evaluate
  raise AssertionError unless yield
end

def is_uppercase_letter? str
  # Evaluates whether a single is a single uppercase letter, i.e.: A-Z
  # +str+:: string to evaluate
  str.length == 1 && /[[:upper:]]/.match(str)
end

assert { is_uppercase_letter? "A" }
assert { !is_uppercase_letter? "a" }
assert { !is_uppercase_letter? "Hello" }

def is_lowercase_letter? str
  # Evaluates whether a string is a single lowercase letter, i.e.: a-z
  # +str+:: string to evaluate
  str.length == 1 && /[[:lower:]]/.match(str)
end

assert { is_lowercase_letter? "a" }
assert { !is_lowercase_letter? "A" }
assert { !is_lowercase_letter? "hello" }

def rot13_char ch
  # Apply ROT13 cipher to a single character
  # - Each letter is rotated by half of the alphabet, or 13 places
  # - Original case is preserved
  # - Non-letter characters remain unchanged
  # - https://en.wikipedia.org/wiki/ROT13
  # +ch+:: the character to apply ROT13 to
  rot_byt = ch.ord + 13
  if is_uppercase_letter? ch
    rot_byt <= "Z".ord ? rot_byt.chr : (rot_byt - 26).chr
  elsif is_lowercase_letter? ch
    rot_byt <= "z".ord ? rot_byt.chr : (rot_byt - 26).chr
  else
    ch
  end
end

assert { rot13_char("W") == "J" }
assert { rot13_char("J") == "W" }
assert { rot13_char("j") == "w" }
assert { rot13_char("w") == "j" }
assert { rot13_char("?") == "?" }

def rot13_string str
  # Apply ROT13 cipher to all characters in a string
  # +str+:: the string to apply ROT13 to
  chars = str.split('')
  results = []
  chars.each do |ch|
    results.push(rot13_char ch)
  end
  results.join("")
end

assert { rot13_string("Why did the chicken cross the road?") == "Jul qvq gur puvpxra pebff gur ebnq?" }
assert { rot13_string("Gb trg gb gur bgure fvqr!") == "To get to the other side!" }

# puts rot13_string "Why did the chicken cross the road?"
# puts rot13_string "To get to the other side!"
# puts rot13_string "Jul qvq gur puvpxra pebff gur ebnq?"
# puts rot13_string "Gb trg gb gur bgure fvqr!"

def rot13 messages
  # Apply ROT13 to an array of "messages" i.e. strings
  # +messages+:: the array of strings to apply ROT13 to
  rotated = []
  messages.each do |msg|
    rotated.push(rot13_string msg)
  end
  rotated
end

assert do
  input = ["Why did the chicken cross the road?", "To get to the other side!"]
  expected = ["Jul qvq gur puvpxra pebff gur ebnq?", "Gb trg gb gur bgure fvqr!"]
  actual = rot13 input
  expected == actual
end

assert do
  input = ["Jul qvq gur puvpxra pebff gur ebnq?", "Gb trg gb gur bgure fvqr!"]
  expected = ["Why did the chicken cross the road?", "To get to the other side!"]
  actual = rot13 input
  expected == actual
end

A Ruby string literal can be enclosed in single or double quotes. The
difference is that the latter does string interpolation.
Examples (from Double vs single quotes on Stack Overflow):

a = 2
puts "#{a}" # prints the value of a

puts 'a\nb' # just print a\nb
puts "a\nb" # print a, then b at newline

That may be wanted (e.g. to include newline characters), or not:

puts rot13_string "#{Wot?}"
// rot13.rb:100:in `<main>': undefined method `Wot?' for main:Object (NoMethodError)

so generally you should enclose the string literals in single-quotes.

The regular expression /[[:upper:]]/ matches all "uppercase alphabetical characters" (Unicode characters in the "Lu" general category, to be precise), and not just the ASCII uppercase letter A...Z.

Therefore your method can produce garbage, e.g. for German "umlauts",
or even crash, e.g. for Greek letters:

puts rot13_string "ÄÖÜ"
puts rot13_string "ΔΘΣ"

Output:

???
rot13.rb:42:in `chr': 903 out of char range (RangeError)
    from rot13.rb:42:in `rot13_char'
    from rot13.rb:62:in `block in rot13_string'
    from rot13.rb:61:in `each'
    from rot13.rb:61:in `rot13_string'
    from rot13.rb:86:in `'

That might not be relevant for this specific programming challenge (which
probably works with ASCII only).

But generally, to substitute only ASCII letters and ignore all other input, the patterns should be
/[A-Z]/ and /[a-z]/, respectively.

The rot13_string can be shortened to

def rot13_string str
  # Apply ROT13 cipher to all characters in a string
  #str+:: the string to apply ROT13 to
  str.each_char.map { |ch| rot13_char ch }.join("")
end

Instead of creating an array with all characters and appending each
mapped character to the result array, each_char
returns an enumerator for the characters, and map returns an
array with the transformed characters.

In the same way, the rot13 function becomes

def rot13 messages
  # Apply ROT13 to an array of "messages" i.e. strings
  # +messages+:: the array of strings to apply ROT13 to
  messages.map { |msg| rot13_string msg }
end

As an alternative, you can use the tr method which takes two string arguments
(with possible ranges) and transforms the given string by replacing
each character in the first argument by the corresponding character
in the second argument:

def rot13_string str
  # Apply ROT13 cipher to all characters in a string
  # +str+:: the string to apply ROT13 to
  str.tr('A-Za-z', 'N-ZA-Mn-za-m')
end

(From https://rosettacode.org/wiki/Rot-13#Ruby.)

This also works "Unicode-correct" in the sense that all other
Unicode characters are preserved. It is less flexible than your
approach however, since you cannot simply change the "offset" from
13 to any other number.


Merge sort algorithm implementation using C++ I'm trying to learn proper C++ and algorithms at the same time.

I particularly feel weird about my iterators usage in merge function. Is this a good way to handle it? I've modeled the signature after the STL std::merge method in <algorithm>.

I've tagged it as C++11 as well, because ideally I would've liked to make use of the new features like move semantics and rvalues, but it seems that I'm misunderstanding how they're supposed to work - no matter where I try to use them, my running time actually drops...

#include <vector>

typedef std::vector<int>::iterator vec_it;
void merge(vec_it left, vec_it left_end, vec_it right, vec_it right_end, vec_it numbers)
{
    while (left != left_end) {
        if (*left < *right || right == right_end) {
            *numbers = *left;
            ++left;
        } else {
            *numbers = *right;
            ++right;
        }

        ++numbers;
    }

    while (right != right_end) {
        *numbers = *right;
        ++right;
        ++numbers;
    }
}

void merge_sort(std::vector<int>& numbers)
{
    if (numbers.size() <= 1) {
        return;
    }

    std::vector<int>::size_type middle = numbers.size() / 2;
    std::vector<int> left(numbers.begin(), numbers.begin() + middle);
    std::vector<int> right(numbers.begin() + middle, numbers.end());

    merge_sort(left);
    merge_sort(right);

    merge(left.begin(), left.end(), right.begin(), right.end(), numbers.begin());
}

Looks good.

Couple of things I would do differently (not that your way is wrong).

Rather than pass references to the containers around I would pass iterators into the containers. This allows your sort algorithm to be container agnostic:

void merge_sort(std::vector<int>& numbers)
{}

// My version looks like this

template<typename I>                 // Notice the template
void merge_sort(I begin, I end)      // Just means I don't care what type
{}                                   // of iterator is used.

Same applies to merge().

Rather than creating sub arrays in merge_sort() I would do it inside merge(). With your current implementation you have a space complexity of \$O(N^2)\$. If you do it inside the merge you just need to allocate enough space to merge the current two ranges which is at most \$O(2N)\$ => \$O(N)\$.

Where you have:

std::vector<int>::size_type middle = numbers.size() / 2;
std::vector<int> left(numbers.begin(), numbers.begin() + middle);
std::vector<int> right(numbers.begin() + middle, numbers.end());

merge_sort(left);
merge_sort(right);

// My version looks like this:

std::size_t mid      = length/2;
I           midPoint = std::next(begin, mid);

// Merge in place.
mergeSort(begin, midPoint);
mergeSort(midPoint, end);

I could not work out how to merge without using a temporary (and I don;t have my copy of Knuth here). So my version of merge() merges the two sorted sub vectors into a temporary then copies back over the original.

Looking at your merge code it's slightly hard to follow (but I groked it). I personally prefer a simpler version.

// In this loop:
//    l:     current position in left  sub-array
//    r:     current position in right sub-array
//    i:     current position into merged array.
//    Note because we are merging in-place.
//    begin/midPoint/end are iterators to the input arrays that
//    split it into two parts.
while(l < midPoint && r < end)
{
    if (*l < *r)
    {    *i = *l;
         ++i;
         ++l;
    }
    else
    {    *i = *r;
         ++i;
         ++r;
    }
}
// One of the ranges is empty at this point.
// So only one of the loops will execute.
while(l < midPoint)
{   *i  = *l;
    ++i;
    ++l;
}
while(r < end)
{   *i  = *r;
    ++i;
    ++r;
}

A slight variation on this that I use; Where you use if () {} else {} I prefer to use the Condition Operator => Test ? <TrueWork> : <FalseWork>. I also have done this a few times and can safely compress ++ operations onto the same lines (Note I don't compress all of them; this is just personal preferences as I think it makes it easier to read this way). Which leaves me with:

while(l < midPoint && r < end)
{
    *i = std::move((*l < *r) ? *l++ : *r++);
    ++i;
}
while(l < midPoint)
{   *i  = std::move(*l++);
    ++i;
}
while(r < end)
{   *i  = std::move(*r++);
    ++i;
}

Notice: I use std::move() here. This is because my sort works on generic containers (not just integer containers). So I may be sorting an array of strings.

Final result is:

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

template<typename I>
void doMerge(I begin, I midPoint, I end)
{
    typename std::vector<typename std::iterator_traits<I>::value_type> TmpVec;

    TmpVec  tmp(std::make_move_iterator(begin), std::make_move_iterator(end));

    TmpVec::iterator   beginAlt   = std::begin(tmp);
    TmpVec::iterator   endAlt     = std::end(tmp);
    TmpVec::iterator   midAlt     = std::next(beginAlt, std::distance(begin, midPoint));

    TmpVec::iterator   l   = beginAlt
    TmpVec::iterator   r   = midAlt;
    I                  i   = begin;

    while(l < midAlt && r < endAlt)
    {
        *i = std::move((*l < *r) ? *l++ : *r++);
        ++i;
    }
    while(l < midAlt)
    {   *i  = std::move(*l++);
        ++i;
    }
    while(r < endAlt)
    {   *i  = std::move(*r++);
        ++i;
    }
}
template<typename I>
void mergeSort(I begin, I end)
{
    std::size_t length  = std::distance(begin, end);
    if (length <= 1)
    {   return;
    }

    std::size_t mid      = length/2;
    I           midPoint = std::next(begin, mid);

    mergeSort(begin, midPoint);
    mergeSort(midPoint, end);

    doMerge(begin, midPoint, end);
}

int main()
{
    std::vector<int>    data  {{ 5,12,45,2,67,8}};
    mergeSort(std::begin(data), std::end(data));

    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";
}


Prove that the graph is a valid tree in Python I recently solved this leetcode problem:

  Given n nodes labeled from 0 to n - 1 and a list of undirected edges
  (each edge is a pair of nodes), write a function to check whether
  these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

  Note: you can assume that no duplicate edges will appear in edges.
  Since all edges are undirected, [0, 1] is the same as [1, 0] and thus
  will not appear together in edges.

My code is correct, and runtime beats 80% of answers submitted, but the overall structure is not at all user friendly. Could anyone give some code review to improve readability?

Don't worry what alternative method or improving the solution since it is already in \$O(n)\$.

from collections import defaultdict

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        if not edges:
            if n == 1:
                return True
            elif n == 2:
                return False

        visited_nodes = defaultdict(list)
        count = True
        unvisited = []
        for key, value in edges:

            if key in visited_nodes and value in visited_nodes:
                return False

            if count:
                visited_nodes[key] = []
                visited_nodes[value] = []
                count = False
                continue
            if key in visited_nodes:
                visited_nodes[key].append(value)
                visited_nodes[value] = []
            elif value in visited_nodes:
                visited_nodes[value].append(key)
                visited_nodes[key] = []
            else:
                unvisited.append([key, value])

        for key, value in unvisited:

            if key in visited_nodes and value in visited_nodes:
                return False

            if key in visited_nodes:
                visited_nodes[key].append(value)
                visited_nodes[value] = []
            elif value in visited_nodes:
                visited_nodes[value].append(key)
                visited_nodes[key] = []
            else:
                return False

        return n == len(visited_nodes.keys())

print Solution().validTree(4, [[0, 1], [2, 3], [1, 2]])

Before going in depth of your algorithm, a few stylistics notes:

I assume that the class Solution(object) thing is required by leetcode, so it might not apply. But as a general note, your validTree method does not need to store/interact with any state. Thus there is no need for it to be a method and would benefit to be defined as a function. Also the naming should be snake_case as per PEP8: def valid_tree(n, edges):. is_valid_tree might also be a better name.
In Python 2, the keys method of dictionaries build and return a new list. It is generally recommended that your use iterkeys instead which return a proxy object to the actual keys of the dictionary. However, such object does not support the len protocol. But the dictionary support it without having to build anything new: len(visited_nodes).

Tidy up your special case

Your algorithm performs two checks:

Every node is reached through an edge;
Every node can reach each other through at most one path.

The only special case to that is, for only one node, to have no edges. The other cases will be handled by the for loops (which will do nothing if edges is empty) and the last check. Thus I would write:

def is_valid_tree(n, edges):
    if n == 1:
        # 1 node must not have edges
        return not edges
    ...

You can also remove all special cases by using default values in visited_nodes. More on that later.

Don't use stuff that you don't use

Sounds weird, doesn't it? But the same goes for your use of defaultdict: you use it without using the extra functionalities over dict. In fact, using visited_nodes = {} will not change anything in your program. So use that instead, it will remove a bit of overhead.

defaultdicts usage is to make use of default values instead of having to explicitly assign them, such as in:

d = defaultdict(list)
d['test'].append('something')
d['test'].append('something else')
d['other test'].append('a third thing')
print(d) # defaultdict(<class 'list'>, {'test': ['something', 'something else'], 'other test': ['a third thing']})

But instead, here you explicitly assign empty lists before assigning to them. This is because you explicitly want to define the key of the dictionary; and, in fact, you do not care about the value. Since you do not use values, why using a dictionary to start with? Use a set they are like dictionaries, but only for keys:

def is_valid_tree(n, edges):
    if n == 1:
        return not edges

    visited_nodes = set()
    count = True
    unvisited = []

    for key, value in edges:
        if key in visited_nodes and value in visited_nodes:
            return False

        if count:
            visited_nodes.add(key)
            visited_nodes.add(value)
            count = False
            continue
        if key in visited_nodes:
            visited_nodes.add(value)
        elif value in visited_nodes:
            visited_nodes.add(key)
        else:
            unvisited.append([key, value])

    for key, value in unvisited:
        if key in visited_nodes and value in visited_nodes:
            return False

        if key in visited_nodes:
            visited_nodes.add(value)
        elif value in visited_nodes:
            visited_nodes.add(key)
        else:
            return False

    return n == len(visited_nodes)

Remove "duplicated" checks

First of, the count variable is useless: it only store whether the dictionary (or the set) is empty. You can get the exact same information using not visited_nodes which is True when visited_node is empty and False otherwise.

Second, you want to add both key and value as key (so maybe they need to be renamed) of visited_nodes if either of them is already one. You can thus simplify the writing using a boolean or and retain the same functionality:

if key in visited_nodes or value in visited_nodes:
    visited_nodes.add(key)
    visited_nodes.add(value)

Using the set approach also help you write less verbose code: use the intersection & operator of sets:

for edge in edges:
    edge = set(edge)
    commons = visited_nodes & edge

    # If a path exist between the nodes in edge
    if commons == edge:
        # A cycle exist and thus it is not a tree
        return False

    # If a node has been visited or if it is the first edge
    if commons or not visited_nodes:
        # Add the path
        visited_nodes.update(edge)
    else:
        # Process later
        unvisited.append(edge)

Third, as stated earlier, you can get rid of all your special cases by initializing visited_nodes = {0}. This will allow you to remove the first check (if n == 1) since it is now handled by return n == len(visited_nodes). And it will also handle adding branches from the node 0 instead of any two first nodes.

Last, the body of both for loops is pretty similar. You may want to factorize it out. Unfortunately, I'm not able to come up with something elegant. It is possible to retry edges by appending them again at the end of edges instead of using unvisited, like so:

def is_valid_tree(n, edges):
    visited_nodes = {0}

    for edge in edges:
        branch = set(edge)
        commons = visited_nodes & branch

        # If a path exist between the nodes in edge
        if commons == branch:
            # A cycle exist and thus it is not a tree
            return False

        # If a node has been visited already
        if commons:
            # Add the branch
            visited_nodes.update(branch)
        else:
            # Process later
            edges.append(edge)

    return n == len(visited_nodes)

Unfortunately this can lead to infinite loops in cases where your code would have reached that return False in the second for loop. However, we can come up with some checks to prevent that. And it's still better than your solution because…

It appears that you have a bug

Calling Solution().validTree(5, [[0, 1], [3, 4], [2, 3], [1, 2]]) returns False. This is because you delay checking for [[3, 4], [2, 3]] but, when running the second checks, instead of delaying [3, 4] which would be integrated in a third pass, you return False. Same would be true for inputs such as Solution().validTree(n, [[0, 1], [n-2, n-1], [n-3, n-2], ..., [1, 2]]) which would need n-3 delayed passes to come to the answer True.

All in all, this doesn't sound like \$O(n)\$ worst case, and you need to fix that bug. Either you try something different, or you patch the previous simplification. I’d go with this one and use a Counter to track the number of time we delayed the treatment for a given edge. Special care has to be taken to provide hashable objects to the counter:

from collections import Counter

def is_valid_tree(n, edges):
    visited_nodes = {0}
    delays = Counter()

    for edge in edges:
        branch = set(edge)
        commons = visited_nodes & branch

        # If a path exist between the nodes in edge
        if commons == branch:
            # A cycle exist and thus it is not a tree
            return False

        # If a node has been visited already
        if commons:
            # Add the branch
            visited_nodes.update(branch)
        else:
            edge = tuple(edge)
            delays[edge] += 1
            if delays[edge] < n:
                # Process later
                edges.append(edge)
            else:
                # Too much delay, can't be processed
                return False

    return n == len(visited_nodes)


Gathering data from huge text files I have a text file composed of several subsequent tables. I need to get certain values from certain tables and save them in an output file. Every table has a header which contains a string that can be used to find specific tables. The size of these text files can vary from tenths of MB to some GB. I have written the following script to do the job:

string = 'str'
index = 20
n = 2

in_file = open('file.txt')
out_file = open("out.txt", 'w')
current_line = 0

for i in range(-index,index+1):
    for j in range(-index,index+1):
        for line in in_file:
            if string in line:
                En = line.split().pop(4)
                for line in in_file:
                    current_line += 1
                    if current_line == 2*(n+1)+2:
                        x = line.split().pop(10)
                    elif current_line == 3*(n+1)+2:
                        y = line.split().pop(10)
                    elif current_line == 4*(n+1)+2:
                        z = line.split().pop(10)
                        current_line = 0
                        break
                print i, j, En, x, y, z
                data = "%d %d %s %s %s %s\n" % (i,j,En,x,y,z)
                out_file.write(data)
                break
in_file.close()
out_file.close()

The script reads the file line by line searching for the specified string ('str' in this example). When found, it then extracts a value from the line containing the string and continue reading the lines that form the data table itself. Since all the tables in the file have the same number of lines and columns, I've used the variable current_line to keep track of which line is read and to specify which line contains the data I need. The first two for-loops are just there to generate a pair of indexes that I need to be printed in the output file (in this case they are between -20 and 20).

The script works fine. But since I've been learning python by myself for about one month, and the files I have to handle can be very big, I'm asking for advices on how to make the script more efficient, and overall, better.

Also, since the tables are regular, I can know beforehand which are the lines that contain the values I need. So I was wondering, instead of reading all the lines in the file, is it possible to specify which lines have to be read and then jump directly between them?

Sample input file

Here's a sample input file. I've included just some tables so you can have an idea how it's organized. This file is composed by two blocks with three tables each. In this sample file, the string "table   #" is what is used to find the data to be extracted.

Sample output file

And here's a sample output file. Keep in mind that these two files are not equivalent! This output was created by my script using an input file containing 1681 blocks of 16 tables. Each table had 13 lines just as in the sample input file.

All this nesting obfuscates your code pretty badly, so let's start by reducing it so it's easier to read. If you need to test something in your for loop, you should flip the test and use continue, like this:

    for line in in_file:
        if not string in line:
            continue
        En = line.split().pop(4)

This saves you one block of nesting at least. You could also combine your two range calls with itertools.product. product performs a nested loop based on the two iterables it's passed. It essentially creates the exact nested loop you have with just one line:

for i, j in itertools.product(range(-index,index+1), range(-index,index+1)):
    for line in in_file:
        if not string in line:
            continue
        En = line.split().pop(4)
        for line in in_file:
            current_line += 1
            if current_line == 2*(n+1)+2:
                x = line.split().pop(10)
            elif current_line == 3*(n+1)+2:
                y = line.split().pop(10)
            elif current_line == 4*(n+1)+2:
                z = line.split().pop(10)
                current_line = 0
                break
        print i, j, En, x, y, z
        data = "%d %d %s %s %s %s\n" % (i,j,En,x,y,z)
        out_file.write(data)
        break

It's certainly more readable now. Though still confusing, why are you looping over in_file within the in_file nested group? It seems redundant but also I think you have misunderstood how file reading works. When you have read the first ten lines of a file object and then start a new loop over that same object you wont re-read the first ten lines. This means there's no reason to nest your inner for loop like this. This will iterate over the same values:

for i, j in itertools.product(range(-index,index+1), range(-index,index+1)):
    for line in in_file:
        if not string in line:
            continue
        En = line.split().pop(4)
    for line in in_file:
        current_line += 1

Now about that current_line, you actually don't need to use that, you could use enumerate instead to automatically count the iteration you're on. enumerate takes an iterable and returns both the value, ie. line but also a number which you can use to replace current_line. enumerate usually starts counting from 0, but you can pass an optional starting parameter:

    for current_line, line in enumerate(in_file, 1):

I think current_line is a confusing name especially now that it's next to line. index or i are what I'd use, personally.

Also you're creating the same string twice, once to print and once to write. Just create data upfront so you can print the same value, this will avoid confusion with typo discrepancies between the two. You can manually add the newline in the write call instead. You should also use the new way of formatting, str.format, as it's type agnostic:

        data = "{} {} {} {} {}".format(i, j, En, x, y, z)
        print (data)
        out_file.write(data + '\n')

Now let's see how this looks with these changes:

for i, j in itertools.product(range(-index,index+1), range(-index,index+1)):
    for line in in_file:
        if not string in line:
            continue
        En = line.split().pop(4)
        break
    for idx, line in enumerate(in_file, 1):
        if idx == 2*(n+1)+2:
            x = line.split().pop(10)
        elif idx == 3*(n+1)+2:
            y = line.split().pop(10)
        elif idx == 4*(n+1)+2:
            z = line.split().pop(10)
            break

    data = "{} {} {} {} {}".format(i, j, En, x, y, z)
    print (data)
    out_file.write(data + '\n')

Now, a note about using open for your files. It's actually better to use with because it will always ensure your files are closed no matter what, even if error's occur during your script. It will unfortunately reintroduce nesting, but it it is worth it.

with open("file.txt") as in_file, open("out.txt", "w") as out_file:
    for i, j in itertools.product(range(-index,index+1), range(-index,index+1)):

Your names could definitely use work too. x, y and z don't mean anything to me. What is n? Is it a constant? Does it change? string is likewise vague, something like key would make more sense. index is confusing too, as it's only for specificying the range you loop over. Would boundary work perhaps? The problem is, your names are so vague I can't even suggest better ones because I don't know what these things do.

Also you should match Python naming conventions. You use snake_case for current_line which is good, but En looks like a class due to the capital. It should just be en, or better yet a descriptive name. Even i and j would benefit from descriptive names if it was possible.


Longest Collatz sequence using dynamic programming in Java I'm not getting where else should I optimize it. Is there any way to optimize this code any further? Just give me hints.

import java.io.*;
import java.util.*;

public class Solution {
    static int[] countarray = new int[5000000]; //for memoization
    static int count; //for calculating length
    public static void main(String[] args){
        countarray[0]=0;
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt(); //number of inputs
        while(t > 0){
            int num = scan.nextInt(); // number upto which we have to find maximum length of the sequence
            int max = 0;
            int result = 1;
            while(num >= 1){
                    count = 0;
                    if(countarray[num-1] != 0)
                        count = countarray[num-1];
                    else
                        counter(num);
                    if(count > max){
                        max = count;
                        result = num;
                    }
                    num--;
            }
            t--;
            System.out.println(result);
        }

    }
    public static int counter(int temp){
        if(temp <= 1)
            return count;
        if(temp < 5000000 && countarray[temp-1] != 0){
            count += countarray[temp-1];
            return count;
        }
        if(temp % 2 == 0)
            counter(temp/2);
        else
            counter((3 * temp) + 1);
        count++;
        if(temp < 5000000){
            countarray[temp-1] = count;
        }
        return count;
    }
}

You memoized once, but you needed to do it twice

Suppose you started with the entire countarray filled in for free.  Your program would still time out because you have \$10^4\$ test cases, and for each test case, you are searching up to \$5*10^6\$ array entries for a total of \$5*10^{10}\$ operations.  In other words, your program runs in \$O(T*N)\$ time, which is too slow.

Think about what happens when the first test case is 5000000 and the second test case is 4999999.  When you found the answer for the first test case, you should have also found the answer for the second test case.  But you
didn't memoize that anywhere.  If you just did a pass where you found the answer for each n once and saved the answers in a second memoization array, then each test case would take \$O(1)\$ time.  Then your total time would be \$O(T + N)\$, which is \$O(N)\$ to build the answer array and \$O(T)\$ to handle \$T\$ test cases.

Be careful of overflow

When computing the collatz sequence, it is easy to overflow a 32-bit integer.  I would recommend using a long instead of an int.  You might be overflowing and not knowing it because the if (temp <= 1) check may be cutting the sequence short.


Finding the largest prime factor As many people will undoubtedly recognise, this is a question in a well known series of problems that I won't name ;)

It's been a long time since I've written any F# and I'm not sure I've ever come across any canonical style guidelines so I'd like feedback on all aspects of the code.

let largestPrimeFactor (number:int64) =
    let rec inner n current =
        if (n * n) > current then
            current
        else if current % n <> 0L then
            let nextCandidate = if n = 2L then 3L else n + 2L
            inner nextCandidate current
        else
            inner n (current / n)
    inner 2L number

Usage is simply:

let largestFactor = largestPrimeFactor 999999866000004473L

// 999999937

I'm not really concerned with performance... I know about the various sieve options (Eratosthenes, Atkins) and decided that trial division for a single prime was adequate.

The names of the function and parameters inner n current don't mean anything; I suggest testFactor num factor instead.  I'd also swap the two parameters so that the one that varies more (the candidate factor) appears last — this is a convention to facilitate currying.

Switching the order of the cases lets you avoid nesting conditions.

let largestPrimeFactor (number:int64) =
    let rec testFactor num factor =
        if factor * factor > num then
            num
        else if num % factor = 0L then
            testFactor (num / factor) factor
        else if factor = 2L then
            testFactor num 3L
        else
            testFactor num (factor + 2L)
    testFactor number 2L


LeetCode 189 - Rotate Array I have a working solution for this problem that was accepted in LeetCode:

  Given an array, rotate the array to the right by k steps, where k is non-negative."

function rotate(nums, k) {
  for (let i = 1; i <= k; i += 1) {
    const poppedNum = nums.pop();
    nums.unshift(poppedNum);
  }

  return nums;
}

// rotate([1, 2, 3, 4, 5, 6, 7], 3) -> [5, 6, 7, 1, 2, 3, 4]

Questions:

Would the time complexity be \$O(k)\$ and space complexity be \$O(1)\$?
Is there a better way to solve this? The question asked to rotate the elements in-place if possible, but I am not sure how to accomplish this at the moment.

Review
Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.
Style
Some points on your code.

The names nums and k could be better, maybe array and rotateBy
Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line nums.unshift(nums.pop());
Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be for (let i = 0; i < k; i++) {

Complexity
Your complexity is \$O(n)\$ and storage \$O(1)\$ where \$n\$ is the number of rotations, the range \$n>0\$
However consider the next examples
rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0
rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1
rotate([1], 8e9); // Will spend a lot of time not changing anything

Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.
You can limit the complexity to \$O(k)\$ where \$0<k<=n/2\$
Rewrite
This is a slight improvement on your function to ensure you don't rotate more than needed.
function rotate(array, rotateBy) {
    rotateBy %= array.length;
    if (rotateBy < array.length - rotateBy) {
        while (rotateBy--) { array.unshift(array.pop()) }
    } else {
        rotateBy = array.length - rotateBy;
        while (rotateBy--) { array.push(array.shift()) }
    }
    return array;
}

Update
As vnp's answer points out the complexity of Array.unshift and Array.shift is not as simple as \$O(1)\$ and will depend on the array type. We can assume the best case for this problem, sparse array (effectively a hash table) and thus will grow/shrink down at \$O(1)\$
In that case the function above has a mean complexity of \$O(log(n))\$ of all possible values of \$k\$
Note that if the cost of grow/shrink operations is \$O(n)\$ (dense array) this will add \$n\$ operations for each \$k\$ making the above \$O(kn)\$ with \$0<=k<(n/2)\$ Expressed in terms of \$n\$ or \$k\$ only it remains \$O(log(n))\$  or \$O(k)\$

You could also use Array.splice
 array.unshift(...array.splice(-rotateBy,rotateBy));

However under the hood the complexity would be a little greater \$O(2n)\$ (which is still \$O(n)\$) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.
The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage \$O(n)\$
If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.


Registering a user and login I have these following controller functions for registering a user and login, in my app, and I want to make it more clean and maintainable.

Probably by using async/await and exec().  Also, the validations do not look not good. It would be great if you suggested me good practices to refactor this.

   registerUser: (req, res) => {
        const { username, email, password } = req.body
        User.create(req.body, (err, createdUser) => {
            if (err) {
                return res.status(500).json({ error: "Server error occurred" })
            } else if (!username || !email || !password) {
                return res.status(400).json({ message: "Username, email and password are must" })
            } else if (!validator.isEmail(email)) {
                return res.status(400).json({ message: "Invaid email" })
            } else if (password.length < 6) {
                return res.status(400).json({ message: "Password should be of at least 6 characters" })
            }
            else {
                return res.status(200).json({ user: createdUser })
            }
        })
    },

    loginUser: async (req, res, next) => {
        const { email, password } = req.body

        if (!email || !password) {
            return res.status(400).json({ message: "Email and password are must" })
        }

        await User.findOne({ email }, (err, user) => {
            if (err) {
                return next(err)
            } else if (!validator.isEmail(email)) {
                return res.status(400).json({ message: "Invalid email" })
            } else if (!user) {
                return res.status(402).json({ error: "User not found" })
            } else if (!user.confirmPassword(password)) {
                return res.status(402).json({ error: "incorrect password" })
            }

        })
    }
```

Regarding your validations - extract each of your validations in validation object.
You can do something like:

class Validator {

isValid(obj) {
//return false if obj is not valid
}

message(obj) {
//return error object if obj is not valid
}

status() {
//error status if validation fails
}

}

Then you can have like EmailValidator, Required, etc. implementation, which validates email strings, etc.
You then just iterate through all current validators and if any of them fails to validate, you use it's error message and status to return error object. That way you can easily configure this by editing current validator list and reuse them in different parts of code.


Setting the page number with a default Consider this code segment:

if (empty($_GET)) {
    $page_number = 1;
} else {
    $page_number = $_GET["page_number"];
}

I wonder if there is a better, more succinct way to express that idea. I thought about using a ternary operator, but the improvement over the original is not substantial:

$page_number = empty($_GET) ? 1 : $_GET["page_number"];

You have a surprise bug: what happens when I do page.php?Name=EBrown? Well $_GET is not empty but your page_number sure isn't set.

That said, you should be doing something like the following:

$page_number = 1;

if (isset($_GET["page_number"})) {
    $page_number = $_GET["page_number"];
}

or

$page_number = $_GET["page_number"];

if (!isset($page_number)) {
    $page_number = 1;
}

The first defaults and then checks for the parameter, the second checks if it's set then defaults. Take your pick.

But those still don't handle invalid (non-numeric) input, so we can do that as well:

$page_number = $_GET["page_number"];

if (isset($page_number) === FALSE || is_numeric($page_number) === FALSE) {
    $page_number = 1;
}

Now we safely default to 1 when page_number is not set, or when it's not numeric.

Of course, we still have another bug: what happens if page_number is 1.12? That's probably unintended. So, we'll check for that as well:

$page_number = $_GET["page_number"];

if (isset($page_number) === FALSE || strpos($page_number, '.') !== FALSE || is_numeric($page_number) === FALSE) {
    $page_number = 1;
}

And finally we'd extract that to a method:

function defaultInt($intValue, $default) {
    if (isset($intValue) === FALSE
        || strpos($intValue, '.') !== FALSE
        || is_numeric($intValue) === FALSE) {
        return $default;
    }

    return $intValue;
}

$page_number = defaultInt($_GET["page_number"], 1);

Easy to use in the future as well.


User-defined function to split a 1D array into 2D array The purpose of the UDF is to receive a 1D array and split it into a 2D array. The size of the new array should be dynamic.

Function SPLITARR(ByRef v() As Variant, MaxRow As Integer) As Variant
  Dim ArraySize As Integer
  Dim MaxCols As Integer
  Dim NewArray() As Variant
  Dim x As Integer, y As Integer, z As Integer

  ArraySize = (UBound(v(), 1) - LBound(v(), 1)) + 1
  MaxCols = ArraySize \ MaxRow

  If ArraySize Mod MaxRow > 0 Then MaxCols = MaxCols + 1
  ReDim NewArray(LBound(v(), 1) To MaxRow, 1 To MaxCols)
  For x = LBound(v(), 1) To UBound(v(), 1)
    y = x Mod MaxRow
    If y = 0 Then y = MaxRow
    z = x \ MaxRow
    If x Mod MaxRow = 0 Then z = z - 1
    NewArray(y, z + 1) = v(x, 1)
  Next
  SPLITARR = NewArray()
End Function

and should be called like;

Sub caller()
Dim a() As Variant
a() = Range("A4:A23")
a() = SPLITARR(a(), 5)
ActiveCell.Resize(UBound(a(), 1), UBound(a(), 2)).Value = a()
End Sub

Let range "A4:A23" have a value of (1,2,3,..20)
and this call will return

1,6,11,16
2,7,12,17
3,8,13,18
4,9,14,19
5,10,15,20

"receive a 1D array and split it into a 2D array" - it's not true, it receives a 2d array of which 2nd dimension is 1. It won't work receiving an 1D or transposed 2D array. (it probably serves your purpose, just be clear with the description to avoid confusion in the future.

If ArraySize Mod MaxRow > 0 Then MaxCols = MaxCols + 1

Although this is correct syntax it's generally a bad practice to write IF in one line.

You can simplify your calculations:

y = x Mod MaxRow
If y = 0 Then y = MaxRow

=> y = ( (x - 1) Mod MaxRow) + 1

z = x \ MaxRow
If x Mod MaxRow = 0 Then z = z - 1

=> z = (x-1) \ MaxRow

(These will not work correctly for 0 index, however in your case arrays copied from Range always have index starting from 1.


Get random direction based off of location and previous direction I've recently implemented a Wilson's Algorithm for maze generation. This problem however could also be extended to things such as snake, or some other simple AIs.

The problem is as follows:

  Blue Node -> Previous nodes

  Red Node -> Current node

  Black Line -> Wall

  In this case, we can analyze each of the 4 possible directions: up,
  right, down and left.

  Up - Not available, since the last move was down (reversing itself)
  Right - Not available, since there is a wall directly to the right
  Down - Available
  Left - Available

  From here we can see that should it move down, then the same
  availability will occur. If it should move left: up, left and down
  would then be available.

The way I have implemented this is as follows:

private int nextDirection(final int i, final int j, final int rowLimit, final int columnLimit, final int previous) {
    boolean up = true;
    boolean right = true;
    boolean down = true;
    boolean left = true;
    if (i == 0) {
        up = false;
    } else if (i == rowLimit) {
        down = false;
    }
    if (j == 0) {
        left = false;
    } else if (j == columnLimit) {
        right = false;
    }
    switch (previous) {
        case DIRECTION_UP:
            down = false;
            break;
        case DIRECTION_DOWN:
            up = false;
            break;
        case DIRECTION_RIGHT:
            left = false;
            break;
        case DIRECTION_LEFT:
            right = false;
    }
    final ArrayList<Integer> list = new ArrayList<>(4);
    if (left) {
        list.add(DIRECTION_LEFT);
    }
    if (right) {
        list.add(DIRECTION_RIGHT);
    }
    if (down) {
        list.add(DIRECTION_DOWN);
    }
    if (up) {
        list.add(DIRECTION_UP);
    }
    return list.get(random.nextInt(list.size()));
}

Where:

i           - row of current node
j           - column of current node
rowLimit    - row count minus one
columnLimit - column count minus one
previous    - previous direction
random      - java.util.Random instance

Now, I highly doubt this is the most efficient solution. However it is the least - well - troublesome. The others I have used are just a large amount of if statements considering every possible case.

However, neither of these solutions - at least how I see them - are efficient enough. Due to this and what Knuth once said, I went for readability. The main problem is, this has become a bottleneck in the calculation speeds.

Question:

Is there a way to better calculate the available directions? And therefore a better way to select a random direction.

Sides notes:

DIRECTION_UP    = 0x01;
DIRECTION_RIGHT = 0x02;
DIRECTION_DOWN  = 0x04;
DIRECTION_LEFT  = 0x08;

These can be changed to whatever value needed.

First of all, using i and j as variable names when dealing with 2D-arrays is just crazy in my personal opinion. Using x and y makes it so much clearer to know which is which.

Then, use an enum:

public enum Direction {
    LEFT, UP, RIGHT, BOTTOM;

    public Direction opposite() {
        switch (this) {
            case LEFT: return RIGHT;
            case RIGHT: return LEFT;
            case UP: return BOTTOM;
            case BOTTOM: return UP;
            default: throw new IllegalStateException();
        }
    }
}

This is probably the most useful enum there is. I don't know how many versions of it I have. Also note that you can add dx and dy values to this enum (UP for example is dx = 0 and dy = -1). This tends to reduce a lot of code duplication.

Now that we have an enum we can return that instead of those int things.

Also, we can use Java's EnumSet class to handle a collection of enums. This class is optimized to use a long (BitSet object for longer enums) and bitmasks, sort of like you seem to already be doing.

Once we have a nice EnumSet to use, then we can either create an array of it and grab a random item from the array, or we can use the iterator of it to iterate over random.nextInt(size) items (not the cleanest and fastest solution perhaps, but it should be faster than creating an array).

Random random = new Random();
private Direction nextDirection(final int y, final int x, final int rowLimit, final int columnLimit, final Direction previous) {
    EnumSet<Direction> directions = EnumSet.allOf(Direction.class);
    if (x == 0) {
        directions.remove(Direction.LEFT);
    }
    if (x == columnLimit) {
        directions.remove(Direction.RIGHT);
    }
    if (y == 0) {
        directions.remove(Direction.UP);
    }
    if (y == rowLimit) {
        directions.remove(Direction.BOTTOM);
    }
    directions.remove(previous.opposite());

    Iterator<Direction> it = directions.iterator();
    for (int i = 0; i < random.nextInt(directions.size()); i++) {
        it.next();
    }
    return it.next();
}

Or, if you would like the array approach:

Direction[] options = directions.toArray(new Direction[directions.size()]);
return options[random.nextInt(options.length)];


Extracting a specific substring in C I have a string like this:

char buffer[] = "blablabla$GPTXT->SOME CODES HERE<-\r\n$GPRMCblablabla";

It is sent from an external device and changes every 1 second.

The string length is over 1000 bytes and consisted of some standard sentences beginning with "$GPXXX" and ending with CRLF. I've written the following function to extract a specific sentence:

int findString(char *src, char *dst, int desLen, char *what2find, char termChar)
{
    char *temp;
    temp = strstr(src, what2find); ;
    if (temp == NULL)
        return 0;
    else
        temp += strlen(what2find);
    int j = 0;
    while (j<(desLen-1))
    {
        if (temp[j]==termChar)
            break;
        dst[j]= temp[j];
        j++;
    }
    dst[j] = '\0';
    return 1;
}

So:

 int main()
 {
  char buffer[] =
  "$GPGGA,123519,4807.038,N,01131.000,E,1,08,0.9,545.4,M,46.9,M,,*47\r\n
  $GPGSA,A,3,04,05,,09,12,,,24,,,,,2.5,1.3,2.1*39\r\n
  $GPGSV,2,1,08,01,40,083,46,02,17,308,41,12,07,344,39,14,22,228,45*75\r\n
  $GPRMC,123519,A,4807.038,N,01131.000,E,022.4,084.4,230394,003.1,W*6A\r\n
  $GPVTG,054.7,T,034.4,M,005.5,N,010.2,K*48\r\n";

  char dst[50];
  findString(buffer,dst,50,"$GPTXT",'$');
 }

finds and return the desired sentence.

But this code has the following problems:

It is very heuristic. I wonder if there exists some better solutions.
It depends on a character (i.e. '$') for termination. It may terminate after finding a '$' but not "$GPXXX". The optimal solution may find the characters between two strings, e.g. "$GPTXT" and "$GPRMC". I don't know if it is optimally achievable.

Note that the host processor is a 4Mhz ARM MCU!

P.S: The above-mentioned function works fine in my project. I just want to widen my C programming knowledge!

P.S. 2: Both answers from Lundin and David C. Rankin are nice. Unfortunately I can not accept both of them as answer!

As far as performance goes, there isn't much you can improve without doing manual optimization tricks. Such things are already implemented in the library functions though.

The main issue I see here is that you copy data into the destination before you know if the string actually contains a termination character. By doing so, you save a bit of time as you can copy and search at the same time. But you also end up copying data before the input has been verified.

What's best in your case, I don't know. It depends on how reliable your input is. If you have already verified it previously, then your copy+check in one might be the best choice. If it's some raw data from a serial bus (UART etc), it might be wisest to verify the data before you copy. I will show a version that does the verification first, it will be safer although possibly slightly slower than what you currently have.

General code review:

Style/best practices

Pointer parameters to data that isn't modified should be const qualified.
Using a plain int for error handling isn't ideal. You actually have several possible errors here: missing search string, missing terminator, potential buffer overflow. Even if your program doesn't need to know what went wrong, it might ease debugging and it costs you nothing extra to add.
The while loop could have been replaced with a for loop, for better readability:

for(size_t i=0; i<desLen-1; i++)
{
  if(temp[i]==termChar)
  {
    break;
  }
  dst[i]=temp[i];
}

Performance

The length of the search key could be determined at compile-time.
Consider dropping the terminating character parameter if what2find[0] could be said to always contain it.
Some micro-optimizations with C99 restrict are possible. I'll show an example below.

Here is a different version which contains more detailed error handling and checks for termination before copy:

#include <string.h>
#include <stdbool.h>

typedef enum
{
  STRFIND_OK,
  STRFIND_KEY_NOT_FOUND,
  STRFIND_TERMINATOR_NOT_FOUND,
  STRFIND_BUFFER_OVERFLOW,
} strfind_result_t;

strfind_result_t strfind_cpy (const char* str,
                              size_t      key_size,
                              const char  key[key_size],
                              char        terminator,
                              size_t      dst_size,
                              char        dst [dst_size])
{
  char* start = strstr(str, key);
  if(start == NULL)
  {
    return STRFIND_KEY_NOT_FOUND;
  }

  start += key_size-1;
  char* end = strchr(start, terminator);
  if(end == NULL)
  {
    return STRFIND_TERMINATOR_NOT_FOUND;
  }

  size_t length = (size_t)(end-start);
  if(length+1 > dst_size)
  {
    return STRFIND_BUFFER_OVERFLOW;
  }

  memcpy(dst, start, length);
  dst[length] = '\0';

  return STRFIND_OK;
}

C99 pointer-to-VLA are used to ensure data size integrity of the buffers. If the verification of data isn't needed, strchr could be replaced with a for loop like the one demonstrated above.

memcpy is the fastest possible copy. It will be faster than copy character-by-character, since the library implementation will work on 32 bit chunks that your ARM likes better than copying individual bytes. So my code might actually be faster (or it may be slower), you'll have to benchmark it.

Further micro-optimization is possible with C99 restrict:

strfind_result_t strfind_cpy (const char* restrict  str,
                              size_t                key_size,
                              const char* restrict  key,
                              char                  terminator,
                              size_t                dst_size,
                              char* restrict        dst);

This tells the compiler that none of the pointers passed point at the same buffer. This may improve performance ever so slightly, depending on how your compiler handles pointer aliasing internally. Check the disassembled code to see if restrict gave any benefits.

Example of use:

#include <stdio.h>

int main (void)
{
  const char data[] = "blablabla$GPTXT->SOME CODES HERE<-\r\n$GPRMCblablabla";
  char buf[50];
  strfind_result_t result;

  result = strfind_cpy(data,
                       sizeof "$GPTXT",
                       "$GPTXT",
                       '$',
                       sizeof buf,
                       buf);

  if(result == STRFIND_OK)
  {
    puts(buf);
  }
}


Improving performance of function to multiply vector with a matrix? I wrote this function to multiply vector with a matrix and I was wondering if someone experienced can spot something can improved its performance.
class matrix:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.m = [[0 for i in range(width)]for i in range(height)]

class vec2:
    def __init__(self, x, y):
        self.x, self.y = x, y
        self.vals = [x, y]

class vec3:
    def __init__(self, x, y, z):
        self.x, self.y, self.z = x, y, z
        self.vals = [x, y, z]

matrix = matrix(3, 3)
matrix.m[0][0] = 2
matrix.m[0][1] = 1
matrix.m[0][2] = 0.5
matrix.m[1][0] = 1
matrix.m[2][0] = 1
matrix.m[1][2] = 0.2

vector = vec3(1, 10, 10)

def multVecMat(vec, mat):
    canCarryOut = False
    if vec.__class__.__name__ == "vec3":
        if mat.width == 3 and mat.height == 3:
            canCarryOut = True
            newVec = vec3(0, 0, 0)
    else:
        if vec.__class__.__name__ == "vec2":
            if mat.width == 2 and mat.height == 2:
                canCarryOut = True
                newVec = vec2(0, 0)

    if canCarryOut:
        vecValues = []
        for v in range(mat.width):
            tempValues = []
            for m in range(mat.height):
                tempValues.append(vec.vals[v]*mat.m[v][m])
            vecValues.append(sum(tempValues))
        if vec.__class__.__name__ == "vec3":
            newVec.x, newVec.y, newVec.z = vecValues[0], vecValues[1], vecValues[2]
        else:
             newVec.x, newVec.y = vecValues[0], vecValues[1]

        return newVec
    raise ValueError

v = multVecMat(vector, matrix)
print(v.x, v.y, v.z)

Throw out the works and use Numpy. Seriously. Rolling your own matrix multiplication is fun and educational, but pretty much immediately reaches its limit if you care about performance. There is no universe in which a native Python implementation of low-level matrix operations will out-perform a well-written C library that has FFI to Python.


Exporting test results to PDF tables I have an asp.net web application and I want to export to a PDF tables in a particular way.

Tables will have data of type Test. tests have a type(by type i mean an int to tell them apart) and for every type i'm creating a TestTable and for every Test a column in each TestTable , there are 9 types. That's why there are 9 TestTables but in tests there might be for example only two different types.

Is there a better way to do this without creating two arrays that their might be useless

public IEnumerable<TestTable> TestHistoryItems(GetTestExportRequest request)
{

    IEnumerable<Test> tests = repository.FindBy(t => t.Visit.pid == request.PetId &&
                                                                t.Visit.dateofvisit >= request.Start && t.Visit.dateofvisit <= request.End).OrderByDescending(t => t.stamp);

    TestTable[] testTables = new TestTable[9] // all the TestTables are 9 but it might need less depending on tests
    {                                         //every TestTable needs tests, of type IEnumerable<Test>.
        new TestTable(),
        new TestTable(),
        new TestTable(),
        new TestTable(),
        new TestTable(),
        new TestTable(),
        new TestTable(),
        new TestTable(),
        new TestTable()
    };

    List<Test>[] testTypes = new List<Test>[9]
    {
        new List<Test>(),
        new List<Test>(),
        new List<Test>(),
        new List<Test>(),
        new List<Test>(),
        new List<Test>(),
        new List<Test>(),
        new List<Test>(),
        new List<Test>()
    };

    foreach (Test test in tests)
    {
        switch (test.type)
        {
            case 3: GetTable(test, ref testTables[0], 3); testTypes[0].Add(test); break;
            case 4: GetTable(test, ref testTables[1], 4); testTypes[1].Add(test); break;
            case 5: GetTable(test, ref testTables[2], 5); testTypes[2].Add(test); break;
            case 6: GetTable(test, ref testTables[3], 6); testTypes[3].Add(test); break;
            case 7: GetTable(test, ref testTables[4], 7); testTypes[4].Add(test); break;
            case 8: GetTable(test, ref testTables[5], 8); testTypes[5].Add(test); break;
            case 9: GetTable(test, ref testTables[6], 9); testTypes[6].Add(test); break;
            case 10: GetTable(test, ref testTables[7], 10); testTypes[7].Add(test); break;
            case 16: GetTable(test, ref testTables[8], 16); testTypes[8].Add(test); break;
         }
    }
    int i = 0;
    foreach (TestTable test in testTables)
    {
        testTables[i].Tests = testTypes[i]; //add tests in testTables
        i++;
    }

    return testTables;
}

public void GetTable(Test test, ref TestTable table, int index)
{
    if (table.Type != index)
    {
        table.TestName = test.TestTypeName; //One Time for every TestTable
        table.Type = index; //One Time for every TestTable
        table.Rows = test.TestDatas.Count(); //One Time for every TestTable; Rows of the table
    }
    table.Columns++; // columns are the number of tests in every TestTable
}

Here is the Class TestTable.

public class TestTable
{
    public string TestName { get; set; }
    public int Type { get; set; }
    public IEnumerable<Test> Tests { get; set; }
    public int Rows { get; set; }
    public int Columns { get; set; }
}

The program works as expected but I think this is wrong. Can't think of a better way to do this, I'm new to coding.

How can I make this code better?

Some quick remarks:

pid, dateofvisit, stamp, type are all properties and thus should follow Microsoft's naming guidelines. Moreover "pid" is fairly meaningless, why not call this "PetId" as well?
testTypes does not convey its actual contents.
Using an int to indicate a type is meaningless. I don't know what a test of type "1" is, or a "2". You should translate this into an enum with meaningful values.
WRT // columns are the number of tests in every TestTable: why do you need this? Can't you just count the entries in the property Tests?
Why is GetTable(Test test, ref TestTable table, int index) a public method? I doubt this is re-used elsewhere. Please apply the correct access modifier to a method, class, property, field etc.

I find your logic hard to understand. I've tried to rewrite it, based on what I think is happening, and this is what I came up with:

    public IEnumerable<TestTable> TestHistoryItems()
    {
        IEnumerable<Test> tests = // get data

        var testTables = new List<TestTable>();

        foreach (var testType in new int[] { 3, 4, 5, 6, 7, 8, 9, 10, 16 })
        {
            var relevantTests = tests.Where(x => x.Type == testType).ToList();

            if (!relevantTests.Any())
            {
                continue;
            }

            testTables.Add(GetTestTable(relevantTests));
        }

        return testTables;
    }

    private TestTable GetTestTable(IReadOnlyCollection<Test> tests)
    {
        var sampleTest = tests.First();
        return new TestTable
        {
            TestName = sampleTest.TestTypeName,
            Type = sampleTest.Type,
            Rows = sampleTest.TestDatas.Count,
            Tests = tests
        };
    }

You could even reduce the first method even more:

    public IEnumerable<TestTable> TestHistoryItems()
    {
        IEnumerable<Test> tests = // get data

        return new[] { 3, 4, 5, 6, 7, 8, 9, 10, 16 }
            .Select(testType => tests.Where(x => x.Type == testType).ToList())
            .Where(relevantTests => relevantTests.Any())
            .Select(GetTestTable)
            .ToList();
    }

To me, this looks a lot clearer: I see there's a list of test types you filter on, and based on that you make a List of TestTables for each type that has actual tests.

Again: I'm not 100% sure this is what you're doing, and that's because of the convoluted way your code works. And that is a major problem: good code can almost be "read" as a story. When I need to spend time trying to figure out that index is actually a test type that you've re-purposed, etc., that's a waste of time and energy.


Decision tree node split by Gini coefficient (used in RandomFerns/RandomForest algorithm) I am implementing the Random Ferns Algorithm for Classification. For simplicity, let's imagine a single decision tree with only a single node. As input we have a feature and the label of each dataset.

The function should work properly for any number of classes (length of set(labels)). The output is a feature threshold which leads to the best split. I plan to further implement other impurity measures such as misclassification rate or entropy.

For those interested in the topic, here is a link to a short introduction presentation in pdf format for the topic: classification trees and node split.

My current implementation works fine, yet I am sure there is plenty of place for improvement. If you have question regarding functionality, please ask. I gave some comments which explain what is to be done.

Example input:

test_features = [1,2,3,3,4]
test_labels = [0,0,1,1,1]

Example output:

3

Code as follows:

def best_split(feature_values, labels):
# training for each node/feature determining the threshold
impurity = []
possible_thresholds = sorted(list(set(feature_values)))

# the only relevant possibilities for a threshold are the feature values themselves

for threshold in possible_thresholds:
    # split node content based on threshold
    # to do here: what happens if len(right) or len(left) is zero
    right = [label for value, label in zip(feature_values, labels) if value >= threshold]
    left = [label for value, label in zip(feature_values, labels) if value < threshold]

    # compute distribution of labels for each split
    right_distribution = [len(list(group)) for key, group in groupby(right)]
    left_distribution = [len(list(group)) for key, group in groupby(left)]

    # compute impurity of split based on the distribution
    gini_right = 1 - np.sum((right_distribution / np.sum(right_distribution)) ** 2)
    gini_left = 1 - np.sum((left_distribution / np.sum(left_distribution)) ** 2)

    # compute weighted total impurity of the split
    gini_split = (len(right) * gini_right + len(left) * gini_left) / len(labels)

    impurity.append(gini_split)

# returns the threshold with the highest associated impurity value --> best split threshold
return possible_thresholds[impurity.index(min(impurity))]

This function is used for training of the Random Ferns class such as:

 def train(self, patches, labels):

        self.classes = list(set(labels))

        # here uniform distribution for each leaf is assumed
        # for each fern - for each feature combination - for each class - there is a posterior probability
        # these are all stored in a list of lists of lists named 'posterior'
        initial_distribution = [1 / len(self.classes)] * len(self.classes)
        self.posterior = [[initial_distribution] * (2 ** self.fernsize)] * self.number_of_ferns

        #determining the best threshold for each feature using best_split function
        all_thresholds = []

        for fern in self.ferns:
            fern_thresholds = []

            for feature_params in fern:
            # the function feature() extracts the feature values of a
            # specific feature (determined by feature_params) from each patch in patches
                feature_values = feature(patches, feature_params)

                fern_thresholds.append(best_split(feature_values, labels))

            all_thresholds.append(fern_thresholds)

        self.threshold = all_thresholds

Assuming that the groupby function comes from the itertools library, the list should be sorted before this function is called. For instance,
[len(list(group)) for key, group in groupby(right)] should be
[len(list(group)) for key, group in groupby(sorted(right))]. It doesn't work properly if the input is not sorted according to the documentation.
After you make the split, you compute exactly the same function for the left and the right part. It might be a good idea to create a separate function for it (something like get_gini_index(values), that takes a list of labels and return the gini index).
# to do here: what happens if len(right) or len(left) is zero. This one looks sort of weird to me. I'd recommend to figure out whether it's actually a special case. If it is, it should be handled properly (namely, this split should be ignored). If it's possible to prove that it's not a special case, this comment needs to be removed to prevent confusion. I would agree that sometimes todo's can be left in the code, but in this case it looks important and easy to fix.


Dagger 2 test application I have a complicated Dagger 2 use case on Android, where I have a lot of dependencies, but some of them are really slow to construct. Like 2-3 seconds slow.

My solution was to create an RX Observable that will be provided through Dagger's injection mechanism to other components, instead of waiting for the slow component to construct on the main thread.

The app's Application object would create the Observable, and provide access to it via one public getter I place on it. Application instance is a singleton by default, so I thought I could hold the reference there.

Another Observable would be the one constructing the slow component and pushing it into the publicly-accessible stream.

My code for demonstrating that scenario:

public class Dagger2TestApplication extends Application {

    private Subject<SlowComponent> mSlowComponent;

    @Override
    public void onCreate() {
        super.onCreate();

        // behavior subject saves the last value inside (great for singleton access)
        mSlowComponent = BehaviorSubject.create();

        // async slow component loading
        Completable
            .create(emitter -> {
                // prepare an artificial blocking delay
                final long delay = 2000L + Math.round(Math.random() * 4000d);
                final long start = System.currentTimeMillis();

                // noinspection StatementWithEmptyBody - just actively wait here
                do {} while (System.currentTimeMillis() - start < delay);

                // now create the instance
                final SlowComponent instance = DaggerSlowComponent.builder().contextModule(new ContextModule(this)).build();

                // finally send the item to all observers, finalize this stream
                mSlowComponent.onNext(instance);
                emitter.onComplete();
            })
            .subscribeOn(Schedulers.io())
            .subscribe();
    }

    public Observable<SlowComponent> getSlowComponentObservable() {
        return mSlowComponent;
    }

}

I decided to use a BehaviorSubject because it would immediately emit anything that was previously pushed into the stream, making it a holder/wrapper around my singleton dependency graph.

Basically, main main conundrum is - do you think this is the way to go for my use case? Or do you have any other ideas on how to achieve this type of behavior?

Not sure why you complicated it, a simple set of operators could do the same:

Observable<SlowComponent> mSlowComponent;

SerialDisposable mDisposable;

@Override
public void onCreate() {
    super.onCreate();

    mDisposable = new SerialDisposable();

    mSlowComponent = Observable.fromCallable(() ->
        DaggerSlowComponent.builder()
        .contextModule(new ContextModule(this))
        .build()
    )
    .subscribeOn(Schedulers.io())
    .replay(1)
    .autoConnect(0, mDisposable::set);
}

@Override
public void onDestroy() {
    super.onDestroy();
    mDisposable.dispose();
    mSlowComponent = null;
}

Main points:

Use fromCallable for a single element result
replay(1) will keep replaying a that single result
autoConnect(0) will start the sequence immediately, even without subscribers yet
mDisposable will allow the sequence to be cancelled if the activity gets disposed while the slow component is still being created.

Edit:

I almost forgot, SequentialDisposable is internal to RxJava, the public version is SerialDisposable.


Fetching configuration or default value I have two code snippets, doing exactly the same thing and both get the job done:

use defaults
use from config

Which is cleaner to use in golang and why?

first option:

package main

import (
    "fmt"
    "strings"
)

func main() {
    fmt.Println(getShCfg(Cfg{}), "\n================")
    fmt.Println(getShCfg(Cfg{"8MB", "4MB"}), "\n================")
    fmt.Println(getShCfg(Cfg{"8MB", ""}), "\n================")
    fmt.Println(getShCfg(Cfg{"", "4MB"}), "\n================")
}

type Cfg struct { A, B string }

func getShCfg(c Cfg) string {
    var out []string

    la := "l_sh_dit conf_data 7MB"
    lb := "l_sh_dit cert_data 3MB"

    if len(c.A) > 0 {
        out = append(out, "l_sh_dit conf_data " + c.A)
    } else {
        out = append(out, la)
    }
    if len(c.B) > 0 {
        out = append(out, "l_sh_dit cert_data "+c.B)

    } else {
        out = append(out, lb)
    }

    return strings.Join(out, ";\n\r") + ";"

}

second option:

package main

import (
    "fmt"
    "strings"
)

func main() {
    fmt.Println(getShCfg(Cfg{}), "\n================")
    fmt.Println(getShCfg(Cfg{"8MB", "4MB"}), "\n================")
    fmt.Println(getShCfg(Cfg{"8MB", ""}), "\n================")
    fmt.Println(getShCfg(Cfg{"", "4MB"}), "\n================")
}

type Cfg struct { A, B string }

func getShCfg(c Cfg) string {
    out := []string{
        getCfgProp("l_sh_dit conf_data", c.A, "7MB"),
        getCfgProp("l_sh_dit cert_data", c.B, "3MB"),
    }
    return strings.Join(out, ";\n\r") + ";"

}

func getCfgProp(key, val, def string) string {
    if len(val) > 0 {
        return key + " " + val
    }
    return key + " " + def
}

I would prefer the second option as it is more scalable i.e. if there are more than 2 parameters (two if else)  so in this case I'm skipping on another if-else in the code …

But in case there are only 2 parameters, is it worth to create a helper function?

Also if there is a better/cleaner approach to achieve it with Golang please let me know

None of the above. Rewrite the first option in readable form. For example,

package main

import (
    "fmt"
    "strings"
)

type Cfg struct{ A, B string }

func getShCfg(c Cfg) string {
    var out []string

    msg := "l_sh_dit conf_data "
    if len(c.A) > 0 {
        msg += c.A
    } else {
        msg += "7MB"
    }
    out = append(out, msg)

    msg = "l_sh_dit cert_data "
    if len(c.B) > 0 {
        msg += c.B
    } else {
        msg += "3MB"
    }
    out = append(out, msg)

    return strings.Join(out, ";\n\r") + ";"
}

func main() {
    sep := "\n================"
    for _, cfg := range []Cfg{
        {},
        {"8MB", "4MB"},
        {"8MB", ""},
        {"", "4MB"},
    } {
        fmt.Println(getShCfg(cfg), sep)
    }
}

Output:

l_sh_dit conf_data 7MB;
l_sh_dit cert_data 3MB;
================
l_sh_dit conf_data 8MB;
l_sh_dit cert_data 4MB;
================
l_sh_dit conf_data 8MB;
l_sh_dit cert_data 3MB;
================
l_sh_dit conf_data 7MB;
l_sh_dit cert_data 4MB;
================

Factoring out common code and data simplifies and highlights the structure of the problem.

To generalize we typically need three to seven cases. We have two. Configuration parameters usually contain a wide range of information and data types and structures. Idle speculation is not useful.

We have safely encapsulated the problem. As we learn more, we can easily revise the code.