Approximate String Matching Interview Question I was working on the challenge Save Humanity from Interviewstreet for a while then gave up, solved a few other challenges, and have come back to it again.

The code below generates the correct answers but the time complexity  O(text * pattern) is not sufficient for the auto-grader. Could anyone perhaps give me a hint or a pointer on how to improve my algorithm?

final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
final StringBuilder builder = new StringBuilder();
final int number_trials = Integer.valueOf(input.readLine());

for(int trial = 0; trial < number_trials; trial++)
{
    final int allowed_mismatches = 1;
    final char[] text = input.readLine().toCharArray();
    final char[] pattern = input.readLine().toCharArray();
    input.readLine();

    for(int text_index = 0; text_index < text.length - pattern.length + 1; text_index++)
    {
        int pattern_index = 0;
        int missed = 0;

        while(pattern_index < pattern.length && missed <= allowed_mismatches)
        {
            if(text[text_index + pattern_index] != pattern[pattern_index])
            {
                missed++;
            }

            pattern_index++;
        }

        if(missed <= allowed_mismatches)
        {
            builder.append(text_index);
            builder.append(" ");
        }
    }

    if(builder.length() > 0 && builder.charAt(builder.length() - 1) == ' ')
    {
        builder.deleteCharAt(builder.length() - 1);
    }

    if(trial + 1 < number_trials)
    {
        builder.append("\n");
    }
}

System.out.println(builder.toString());

1.I would use something like "APPROXIMATE BOYER-MOORE STRING MATCHING" described here:

http://www.cs.hut.fi/~tarhio/papers/abm.pdf

2.The second option is the Suffix Tree Solution:

http://homepage.usask.ca/~ctl271/810/approximate_matching.shtml

The Suffix Tree approach to the k-mismatch problem is essentially the same as the approach taken when matching with wild-cards; though in this case k is the number of allowable mismatches rather than the number of wildcards. The algorithm proceeds by executing up to k constant-time lce queries for each position i in the text. If the the lce queries span the end of P, then P occurs starting at position i of the text.

for i = 1; i < m-n+1; i++
  1. j = 1, i′ = i, count = 0
  2. l = lce (P[j], T[i′])
  3. if j+l = n+1, P occurs in T at i with only count mismatches; continue next i;
  4. if count ≤ k, count++, j = j+l+1, i′=i′+l+1, go to 2
  5. if count = k+1, then a k mismatch of P does not occur at i; continue next i;

An alternate approach, when both k and the alphabet size are relatively small is to generate all permutations of P with up to k changes and then search for each of these permutations in the tree. This would run in time O(P′ + m), where P′ is the combined length of the permissible permutations of P.


English Translator - follow up Awhile ago I posted a Translator app that I have been in the process of making. I edited some features in it and I've decided to post it again.

My questions:

Is there anything I should add to this?
Is there any better (more easily readable) syntax for what I'm trying to do?
Say I wanted to make a GUI for this app. What language goes well with Ruby?

Here's the source code of the app:

require 'yaml'
require 'base64'
require 'digest'

def welcome_list
    puts """
    Welcome to Translation Center! Below you will find a list of available(so far) features, more feautures are being added as we speak! Have fun and enjoy!

    As of now Translation Center is able to translate from:

    1: Russian
    2: Spanish
    3: Arabic
    4: Pashto
    5: French

    Translation Center is also able to translate into:

    6: Base64
    7: Binary
    8: MD5

    Please choose from the list above by typing in the number in front of the language:
    """
    input = gets.chomp!
    case input.to_i
    when 1
        translate
    when 2
        translate
    when 3
        translate
    when 4
        translate
    when 5
        translate
    when 6
        base64
    when 7
        binary
    when 8
        md5
    else
        puts "Invalid input, redirecting..."
        return
    end
end

def translate
    translations = YAML.load_file 'words.yml'
    puts "Enter word or phrase to be translated to English, press 'Q' to quit:"
    input = gets.chomp
    if translations[input]
        puts "The translation of '#{input}' to English is: '#{translations[input]}'"
    elsif input =~ /q/i
        list
    else
        puts "Invalid word or phrase redirecting..."
        translate
    end
end

def binary
    puts "Enter your text you wanted translated to binary:"
    text = gets.chomp
    puts "#{text} in binary is: #{text.unpack('b*')}"
    binary if restart
end

def base64
    puts "Enter the text you want translated to Base64:"
    input = gets.chomp!.to_s
    new_string = "#{input}"
    puts "'#{input}' in Base64 is: #{Base64.encode64(new_string)}"
    base64 if restart
end

def md5
    puts "Enter text you want translated to MD5:"
    input = gets.chomp!.to_s
    input_string = Digest::MD5.new
    input_string.update(input)
    puts "'#{input}' translated to MD5: '#{input_string}'"
    md5 if restart
end

def restart
    puts "Would you like to [1]translate another, go back to the [2]main menu, or [3]quit?"
    input = gets.chomp!
     if input == "1"
        return true
    elsif input == "2"
        puts "Redirecting to Menu..."
        welcome_list
    else
        puts "Exiting system..."
        exit
    end
end
welcome_list

Sample words.yml file:

spanish:
a: to
abajo: down

arabic:
salam: Hi
ana min: I'm from...

russian:
А: A
В: V

french:
oui: Yes
non: No

pashto:
khe chare: Hello

japanese:
yaa: Hi
Yaa: Hi
Konbanw: Good evening

A few dozen teensy little things before I get to the meat of my review:

""" does not a multiline string make. It makes an empty string, a multiline string, and another empty string, all joined with newlines. Replace that with a heredoc -- this blog post goes into a good bit of detail about them.
I can't find a source for it, but console windows are typically 80 characters wide. Anything more and you get wrapping, which may look fine on *nix but on Windows it looks awful, because it's character-based wrapping, not word-based.
You made a bunch of grammar errors. I fixed 'em. Of course, most of the text could be reworked -- from the menu, you'd never guess that you can't translate to Russian, Spanish, Arabic, Pashto, or French, and you can't translate from base 64, binary, or MD5 hash. Well, maybe the last, but the rest it's not clear.
In a case statement, you can see if a number is within a range by doing when lower_bound..upper_bound. Standard range syntax applies.
You load the YAML file every time someone wants to translate something. Load it once, then either make it a $global variable or pass it in through translate's arguments.
When you say "redirecting", you probably mean "please try again", since there isn't a program in the world that "redirects" to the same menu when you mess up the input. You also don't want to use recursion to do that, since at some apparently random point they'll get a SystemStackError for recursing too deeply. There's a reason that Ruby has iterative loops.
On that note, why is it that when you enter invalid input anywhere else, you can try again, but in welcome_list, the program says the same thing but then exits? Just remove the text and have it end, or drop a loop in like everything else.
In md5, why is the hash called input_string? It's very obviously not what they inputted. That should really be called something like hash or result.
Some of your English is inconsistent -- personally, I like it all to look the same, because it gives it a more clean feel if you see 'Enter the text you want translated to [language]:' and 'abc' translated to [language] is: 'def' every time, instead of different text for each "language".
What on Earth is with this bit:

elsif input =~ /q/i
  list

Why does anything containing Q -- no, not something that's just that letter, read the documentation -- run a method, list, that doesn't exist? See, little teensy break-your-whole-program-no-matter-what bugs like that are why you have to test your code. I have no idea what you're trying to do here (i.e. go back to the welcome list or exit the program) so I assumed you wanted to exit the program. It's easier on me.
You use gets.chomp!.to_s, which makes no sense, because chomp! already returns a string, and the bang version (chomp! instead of chomp) affects nothing in this case. You use it right elsewhere, so I'm confused.

  NOTE: In refactoring the whole program according to my description below, some of these things become invalid. However, they're still worth mentioning.

Right, on to the fun stuff. Namely, why your program is absolutely terrible in one teeny tiny edge case that you should have seen a mile away: Two languages that have the same word will seriously screw each other up. See, you divide your YAML file into human-readable pieces by doing a little header with the language, but YAML doesn't see it like that. What it sees is a key, language_name, that's mapped to nothing at all. If you wanna say "These are all the words in Russian" and have YAML associate "russian" with those words, you have to indent1. For example:

russian:
    А: A
    В: V

instead of

russian:
А: A
В: V

Now, fixing this is gonna cause a few problems, because you were relying on your bad way of doing things. First off, translate is depending on everything being in the bottom level. Instead, what you're gonna have to do is change it like this:

  Add a parameter, all_words, and translations = all_words[language] before the first line.

Whew! That was an awful lot of effort. Now, that just broke all your code, because you're calling translate with only one argument, up above. What you're gonna wanna do is one of two things:

Hardcode your list into the case, sort of like it was before. I recommend against this.
Make it all super easy to change by having it sense what languages are available, update the list automatically, and put the appropriate options in the case.

Since the way I did it is pretty complicated, and involved an annoying amount of refactoring, I'm not gonna describe it in great detail. See the code if you want to know how. It's not that hard, just a different way of thinking.

There are a few remaining problems that I'm not going to fix, because I'm a lazy son of a you should practice. They are:

You mix input with calculation -- the calculation should ideally be separated from the input as much as is feasible. That is, if you're using puts and gets in the same method as the one where you perform a calculation, separate them. Note that this isn't always true -- if the calculation is solely for the purpose of dynamic text, for example, you shouldn't separate that out. Probably. It depends.
You made it almost impossible to easily loop the whole program, instead of just bits, because you focused on using recursion.

  Note: As a side effect of this, I couldn't easily figure out how to make restart work without recursion, so I left it alone.

In translate, if the word happens to be Q or q (which is unlikely but possible), you won't give the translation. You need to listen for CTRL+C (i.e. InterruptError if memory serves) and quit on that, then say that you're quitting on that.
If they enter the text in anything but all lowercase, it doesn't give them the translation, unless you put the uppercase versions in the YAML manually.
binary prints out the result as ["100001101000011010000110"] instead of 100001101000011010000110 (for the string aaa).

(mostly) Fixed code:

require 'yaml'
require 'base64'
require 'digest'

def welcome_list
  word_bank = YAML.load_file 'words.yml'
  languages = word_bank.keys
  non_language_options = 3
  i = non_language_options
  puts <<-END.gsub(/^\s*>/, '')
    >Welcome to Translation Center! Below you will find a list of as yet available features.
    >More features are being added as we speak! Have fun and enjoy!
    >
    >Translation Center can translate to:
    >
    >1: Base64
    >2: Binary
    >3: MD5
    >
    >Translation Center can translate from:
    >
    >#{languages.map { |item| "#{i+=1}: #{item}" }.join "\n"}
    >
    >Please choose from the list above by typing in the number in front of the option:
  END
  input = gets.chomp
  case choice = input.to_i
    when 1
      base64
    when 2
      binary
    when 3
      md5
    when (non_language_options+1)..(languages.length+non_language_options+1)
      translate(word_bank, languages[choice-non_language_options-1])
    else
      puts 'Invalid input.'
      return
  end

end

def translate(all_words, language)
  translations = all_words[language]
  while true
    puts "Enter word or phrase to be translated from #{language} to English, press 'Q' to quit:"
    input = gets.chomp
    if translations[input]
      puts "The translation of '#{input}' to English is: '#{translations[input]}'"
      next
    elsif input.upcase == 'Q'
      exit
    else
      puts 'Invalid word or phrase. Please try again.'
      next
    end
    break
  end
end

def binary
  while true
    puts 'Enter the text you want translated to binary:'
    text = gets.chomp
    puts "#{text} in binary is: #{text.unpack('b*')}"
    break unless restart
  end
end

def base64
  while true
    puts 'Enter the text you want translated to Base64:'
    input = gets.chomp
    new_string = "#{input}"
    puts "'#{input}' in Base64 is: #{Base64.encode64(new_string)}"
    break unless restart
  end
end

def md5
  while true
    puts 'Enter the text you want translated to MD5:'
    input = gets.chomp
    result = Digest::MD5.new
    result.update(input)
    puts "'#{input}' translated to MD5 is: '#{result}'"
    break unless restart
  end
end

def restart
  puts <<-END.gsub(/^\s*>/, '')
    >Would you like to:
    >1. Translate another
    >2. Go back to the main menu
    >3. Quit
  END
  input = gets.chomp!
  if input == '1'
    true
  elsif input == '2'
    puts 'Redirecting to menu...'
    welcome_list
  else
    puts 'Exiting...'
    exit
  end
end

welcome_list

Fixed words.yml:

spanish:
    a: to
    abajo: down

arabic:
    salam: Hi
    ana min: I'm from...

russian:
    А: A
    В: V

french:
    oui: Yes
    non: No

pashto:
    khe chare: Hello

japanese:
    yaa: Hi
    Yaa: Hi
    Konbanw: Good evening

As for a GUI, I suggest Shoes!, because it's conveniently already in Ruby.

1: Little teensy things like this are why you always, always, always, always read the documentation for everything you're using. ALWAYS.


Move friendly merge sort - follow-up This is a follow up to this question. I'm only interested to see if this is implemented correctly for move-only types.

#include <vector>
#include <iterator>
#include <algorithm>
#include <utility>

namespace sorting {
  namespace detail {
    template<typename RandomIt>
    RandomIt middle_iterator(RandomIt begin, RandomIt end) {
      return std::next(begin, (end - begin) / 2);
    }

    template<typename RandomIt1, typename RandomIt2, typename OutIt>
    OutIt merge(RandomIt1 left, RandomIt1 left_end, RandomIt2 right, RandomIt2 right_end, OutIt out) {
      while(left < left_end && right < right_end) {
        if (*left < *right) {
          *out++ = std::move(*left++);
        } else {
          *out++ = std::move(*right++);
        }
      }

      std::move(left, left_end, out);
      std::move(right, right_end, out);
      return out;
    }
  }

  template<typename RandomIt1, typename RandomIt2>
  void merge_sort(RandomIt1 begin, RandomIt2 end, RandomIt2 scratch_begin, RandomIt2 scratch_end) {
    if (end - begin > 1) {
      const auto mid = detail::middle_iterator(begin, end);
      const auto scratch_mid = detail::middle_iterator(scratch_begin, scratch_end);
      merge_sort(scratch_begin, scratch_mid, begin, mid);
      merge_sort(scratch_mid, scratch_end, mid, end);
      detail::merge(scratch_begin, scratch_mid, scratch_mid, scratch_end, begin);
    }
  }

  template<typename RandomIt>
  void merge_sort(RandomIt begin, RandomIt end) {
    using value_type = typename std::iterator_traits<RandomIt>::value_type;
    auto scratch_buffer = std::vector<value_type>(std::make_move_iterator(begin), std::make_move_iterator(end));
    merge_sort(begin, end, scratch_buffer.begin(), scratch_buffer.end());
  }
}

It certainly looks clean and well-written.
Just one thing, I really hate horizontal scrolling. I acknowlege this site is very restrictive there though.

Make sure your use of move-semantics is type-appropriate:

Move if it's a move-only type.
Move if moveing is noexcept.
Otherwise, don't move it.

The standard-library already has to do that in many places, and thankfully it is available to the public as std::move_if_noexcept() analogous to std::move.

I suggest adding your own helper which does that for iterators.
You know, it's itching in my fingers to modify merge() to use the conditional operator. Especially after applying the above point, which makes the common part even bigger.
One of the advantages moveing is that it allows for guaranteed success in more cases. Yes, writing flexible and comprehensive noexcept-specifications can be a pain, but your callers will thank you.

Without doing that work, a good part of the advantage of the two-range version is lost.
I would suggest renaming your iterator-ranges source and target respectively, neither is properly scratch. Also, I would use the more common temp as a name in merge_sort(begin, end).
Are you aware of the sordid tale that is std::vector<bool>?
I'm not saying it won't work in this case, though slowly.
You do know that C++17 has class template argument deduction?
It's nice to see that you only use < for comparisons, just like the standard-library. That should enable you to easily modify your code to allow for a custom comparison-object.
But there is a problem in how you do the comparisons, as your merge() is needlessly not stable: If both are equal, you should take from the left range instead.
Consider asserting that the two iterator-types fit together in the function, or testing it for SFINAE outside.


Project Euler 21: Sum of Amicable Numbers Problem 21:

  Let \$d(n)\$ be defined as the sum of proper divisors of \$n\$ (numbers less than \$n\$ which divide evenly into \$n\$).
  If \$d(a) = b\$ and \$d(b) = a\$, where \$a ≠ b\$, then \$a\$ and \$b\$ are an amicable pair and each of \$a\$ and \$b\$ are called amicable numbers.

  For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore \$d(220) = 284\$. The proper divisors of 284 are 1, 2, 4, 71 and 142; so \$d(284) = 220\$.

  Evaluate the sum of all the amicable numbers under 10000.

Am I abusing reduce or itertools here? I'm concerned this solution could be more readable. Also, is there a more efficient solution rather than calculating everything up front?

from itertools import chain, count
from operator import mul

def factorize(n):
    for factor in chain((2,), count(start=3,step=2)):
        if factor*factor > n:
            break

        exp = 0
        while n % factor == 0:
            exp += 1
            n //= factor
        if exp > 0:
            yield factor, exp

    if n > 1:
        yield n, 1

def sum_of_factors(n):
    """
    >>> sum_of_factors(220)
    284
    >>> sum_of_factors(284)
    220
    """
    total = reduce(mul,
        ((fac**(exp+1)-1)/(fac-1) for fac,exp in factorize(n)),
        1)
    return total - n

if __name__ == '__main__':
    cache = {k: sum_of_factors(k)
        for k in xrange(1, 10000)
    }

    print sum(k for k, v in cache.iteritems()
        if cache.get(v, None) == k
        and v != k)

Your code looks nice but I have a few suggestions to make it easier to understand according to my personal preferences.

It might be worth defining a function to encapsulate your call to reduce and mul (if you go forward in Project Euler problems, you'll reuse it many times) :

def mult(iterable, start=1):
    """Returns the product of an iterable - like the sum builtin."""
    return functools.reduce(operator.mul, iterable, start)

That you can easily use :

def sum_of_factors(n):
    """
    >>> sum_of_factors(220)
    284
    >>> sum_of_factors(284)
    220
    """
    total = mult((fac**(exp+1)-1)/(fac-1) for fac,exp in factorize(n))
    return total - n

Your function factorize generates tuples of the form (prime factor, power) which is probably worth documenting (either in the doc or in the function name).

I think it'd be easier to generate prime factors without grouping them as this can be delegated to a different function.

You'd have something like :

def factorize(n):
    """Generate prime factors (potentially repeated) in order."""
    for factor in chain((2,), count(start=3,step=2)):
        if factor*factor > n:
            break

        while n % factor == 0:
            n //= factor
            yield factor
    if n > 1:
        yield n

This function does one thing (and does it well) and can be easily tested :

for i in range(1, 1000):
    fact = list(factorize(i))
    assert mult(fact) == i  # see, i've reused mult already :-)
    assert sorted(fact) == fact  # there was a time where I needed that property but it's not really important now

Grouping and counting can be delected to a collection.Counter.

def sum_of_factors(n):
    """
    >>> sum_of_factors(220)
    284
    >>> sum_of_factors(284)
    220
    """
    total = mult((fac**(exp+1)-1)/(fac-1) for fac,exp in collections.Counter(factorize(n)).items())
    return total - n

The function sum_of_factors probably deserves some additional explanation (especially because the name says sum while the code says mult). Maybe a link to some reference would be enough.

You can avoid a few cache lookups. Indeed, at the moment, you consider all pairs (a, b) with a != b and add a whenever you find one. You could limit yourself to pairs (a, b) with a < b and add a+b when you find it. Also, by doing so, you know for sure that the value you are looking for will be in the cache.

sum_facts = {k: sum_of_factors(k) if k else 0 for k in range(10000) }
print(sum(k + v for k, v in sum_facts.items() if v < k and sum_facts[v] == k))


Find k-th smallest index in an MCMC procedure I am repeatedly (100,000+ times) running the following function to find the kth order statistic. I ran a profiler and noticed this function was most expensive. I am looking for a way to optimize this code for speed. The reason I think it can be done faster is because I do not want find the kth largest value, but the index of the kth largest value. However, now I'm effectively looping twice through the vector x, which seems inefficient to me.
The code below is an example, in practice I use R and Rcpp to run the code. Any ideas?

#include <iostream>
#include "C:\c++\armadillo-7.950.1\include\armadillo"

using namespace std;
using namespace arma;

int qSelectIdxC(arma::vec& x, const int k) {

    // ARGUMENTS
    // x: vector to find k-th largest element in
    // k: k-th statistic to look up

    // safety copy since nth_element modifies in place
    arma::vec y(x.memptr(), x.n_elem);

    // partially sorts y.
    std::nth_element(y.begin(), y.begin() + k, y.end());

    // the k-th largest value
    const double kthValue = y(k);

    // find and return the index of the k-th largest value;
    int idxK = std::find(x.begin(), x.end(), kthValue) - x.begin();
    return idxK;

}

int main() {

    vec test0 = regspace<vec>(0, 10); // 0, 1, ..., 10
    int ans0 = qSelectIdxC(test0, 5); // returns 5

    vec test1(100, fill::randu);
    int ans1 = qSelectIdxC(test1, 50);

    cout << "ans0" << ans0;
    cout << "ans1" << ans1;

    return 0;
}

To find the kth smallest/largest value you do not need to sort all values! Simply keep track of the k smallest/largest encountered values in a (sorted) buffer. This will take your run time from O(nlog(n)) to O(nlog(k)). And will also avoid the unnecessary copy and iteration, simply keep the index with k.

The following pseudocode illustrates the algorithm

template<typename It>
It min_k(It first, It last, int k){
   auto cmp_it_values = [](It lt, It rt){ return *lt < *rt;};
   auto max_copy = std::min<long>(k, std::distance(first, last));
   auto start_it = first;
   std::advance(start_it, max_copy);

    k++; // k == 0 has to return smallest one element.
    std::vector<It> k_smallest;
    k_smallest.reserve(k+1);
    for(auto it = first; it != start_it; ++it){
        k_smallest.push_back(it);
    }
    std::sort(k_smallest.begin(), k_smallest.end(), cmp_it_values);

    for(auto it = start_it; it != last; ++it){
        if(k_smallest.empty() || *it < *k_smallest.back()){
            auto insertion_point = std::lower_bound(k_smallest.begin(), k_smallest.end(),
                                                    it, cmp_it_values);
            k_smallest.insert(insertion_point, it);
            if(k_smallest.size() > k){
                k_smallest.pop_back(); // Remove the largest value
            }
        }
    }
    return k_smallest.back(); // The iterator to the min(k, n) smallest value
}

The above has O(nklog(k)) worst case and O(n + log(k)) best case behaviour. You can improve the worst case by using a max heap for k_smallest instead of a vector. This would have the promised O(nlog(k)) run time. I leave that as an exercise to the reader ;)

And you should read this using namespace std; is bad practice.

You can see from the benchmark here: https://ideone.com/B81Hs4 that the code above is twice as fast as your original code for the given values (you need to test with typical values for your application to verify) and the heap version is even faster.


Adding genres and themes from work Codacy is telling me this method has a complexity of 13. I need some tips on how to reduce it, more specifically inside the forEach loop.

I've already changed it from an if/else` if hell, but it seems it wasn't enough.

function addGenresAndThemesFromWork(work){
    let workDetails = {workId: work.$.id, genres: [], themes: []};
    let workInfo = work.info;

    if (typeof workInfo === 'object') {
        Object.keys(workInfo).forEach(function (key) {
            let workfInfoType = workInfo[key].$.type;
            let workInfoValue = workInfo[key]._;

            switch (workfInfoType.toLowerCase()) {
                case 'genres':
                    workDetails.genres.push(workInfoValue);
                    if (Genres.findOne({name: workInfoValue}) === undefined) {
                        Genres.insert({
                            name: workInfoValue
                        });
                    }
                    break;
                case 'themes':
                    workDetails.themes.push(workInfoValue);
                    if (Themes.findOne({name: workInfoValue.toLowerCase()}) === undefined) {
                        Themes.insert({
                            name: workInfoValue.toLowerCase()
                        });
                    }
                    break;
                case 'main title':
                    workDetails.name = workInfoValue;
                    break;
                case 'plot summary':
                    workDetails.plot = workInfoValue;
                    break;
                case 'objectionable content':
                    if (workInfoValue.toLowerCase() === 'ma') {
                        workDetails.mature = true;
                    }
                    break;
                case 'picture':
                    let workImg = workInfo[key].img[1];
                    if (workImg !== undefined) {
                        workDetails.picture = workImg.$;
                    } else {
                        if (workInfo[key].img[0] !== undefined) {
                            workDetails.picture = workInfo[key].img[0].$;
                        }
                    }
                    break;
                case 'alternative title':
                    if (workInfo[key].$.lang.toLowerCase() === 'ja') {
                        workDetails.alternativeTitle = workInfoValue;
                    }
                    break;
            }
        });
    }

    if (!_.has(workDetails, 'picture')) {
        workDetails.picture = {src: '/default.jpg', temporary: true};
    }

    persistWorkDetails(workDetails);
    }

I don't have a tool here to count, so I don't know how the numbers will
play out.  That said, I agree with the interpretation since there's a
lot of things going on here and it makes sense to detangle the function
into smaller bits.

The big if block immediately suggests that some kind of
short-circuiting or decomposing into functions would be useful.  E.g. if
workInfo is not an object, call persistWOrkDetails and just return;
the other branch will continue afterwards and also persists the object.

Then again, I'd rather split a function off in this case, though I have
no idea what to call it.

function addGenresAndThemesFromWork(work) {
    let workDetails = {workId: work.$.id, genres: [], themes: []};

    if (typeof work.info === 'object') {
        fillInWorkDetails(work.info, workDetails);
    }

    if (!_.has(workDetails, 'picture')) {
        workDetails.picture = {src: '/default.jpg', temporary: true};
    }

    persistWorkDetails(workDetails);
}

Next up are the genres and themes, which exhibit a common pattern, so
again, move that into a separate function.  Sounds like that is a
function that might already exist in a library anyway.

function pushNew(thing, name) {
    let value = {name: name};

    if (thing.findOne(value) === undefined) {
        thing.insert({name: name});
    }
}

...

case 'genres':
    workDetails.genres.push(workInfoValue);
    pushNew(Genres, workInfoValue);
    break;
case 'themes':
    workDetails.themes.push(workInfoValue);
    pushNew(Themes, workInfoValue.toLowerCase());
    break;

For "objectionable content" (I wonder) the if can be replaced with an
or, that is:

workDetails.mature = workDetails.mature || workInfoValue.toLowerCase() === 'ma';

The syntax is a bit longer, but a temporary variable could be used to
deal with that.

Is there a particular reason to use Object.keys instead of for
... in on the workInfo object?
The nested else { if ... } can just be written as else if in this
case.
workInfo[key] appears way too often, just assign it to a shorter
name.
Since you create workDetails yourself, you probably don't have to
use _.has, but just plain in.
The picture default value can be moved into the workDetails
initialisation since the loop will always overwrite the existing
value.  That also takes care of any possible issues with undefined.
If a function (like findOne) only returns a false value if couldn't
find something, then the comparison can also simply be if
(!findOne(...)) - I'm assuming that that's done for a reason though.

With all that in mind I'm arriving at the following, which, depending on
the exact format and semantics of the objects could be further
distilled, but I think this is good enough for now and for you to
continue on it later.

I'd also suggest that the workDetails object is filled in with more
defaults so it's actually clear that e.g. a missing mature field
actually means the same as mature: false in the initialisation (or
not, in which case the code below is slightly wrong).

function pushNew(thing, name) {
    let value = {name: name};

    if (thing.findOne(value) === undefined) {
        thing.insert(value);
    }
}

function pictureValue(img) {
    if (img[1] !== undefined) {
        return img[1].$;
    } else if (img[0] !== undefined) {
        return img[0].$;
    }
    return undefined;
}

function fillInWorkDetails(workInfo, workDetails) {
    for (let key in workInfo) {
        let value = workInfo[key];
        let workInfoValue = workInfo[key]._;

        switch (value.$.type.toLowerCase()) {
            case 'genres':
                workDetails.genres.push(workInfoValue);
                pushNew(Genres, workInfoValue);
                break;
            case 'themes':
                workDetails.themes.push(workInfoValue);
                pushNew(Themes, workInfoValue.toLowerCase());
                break;
            case 'main title':
                workDetails.name = workInfoValue;
                break;
            case 'plot summary':
                workDetails.plot = workInfoValue;
                break;
            case 'objectionable content':
                workDetails.mature = workDetails.mature || workInfoValue.toLowerCase() === 'ma';
                break;
            case 'picture':
                workDetails.picture = pictureValue(value.img) || workDetails.picture;
                break;
            case 'alternative title':
                if (value.$.lang.toLowerCase() === 'ja') {
                    workDetails.alternativeTitle = workInfoValue;
                }
                break;
        }
    }

    return workDetails;
}

function addGenresAndThemesFromWork(work) {
    let workDetails = {
        workId: work.$.id,
        genres: [],
        themes: [],
        picture: {src: '/default.jpg', temporary: true}
    };

    if (typeof work.info === 'object') {
        fillInWorkDetails(work.info, workDetails);
    }

    persistWorkDetails(workDetails);
}


Properly storing error messages and displaying them with OOP I have a class that I am using to initialize a form for editing. Once the form is submitted, data validation is done through the setters of my class. Good or bad input will be set in order to re-display them in the form (is this bad?). Everything works fine, but I am not too happy with how I am storing and displaying the error messages.

Any suggestions on how I can improve?

Course.class.php

<?php
class Course {
    protected $_code;
    protected $_name;
    protected $_errors = array();

    public function __constructor($id) {
        if (is_int($id)) {
            $this->_load($id);
        }
    }

    public function getCode() { return $this->_code; }

    public function setCode($value) {
        $this->_code = $value;
        if (empty($value)) {
            $this->setError('code', 'Enter a code.');
        } else if (strlen($value) > 10) {
            $this->setError('code', 'The code you provided must be less than 10 characters.');
        }
    }

    public function getName() { return $this->_name; }

    public function setName($value) {
        $this->_name = $value;
        if (empty($value)) {
            $this->setError('name', 'Enter a name.');
        } else if (strlen($value) > 50) {
            $this->setError('name', 'The name you provided must be less than 50 characters.');
        }
    }

    public function getError($name) {
        return isset($this->_errors[$name]) ? $this->_errors[$name] : '';
    }

    public function setError($name, $value) {
        $this->_errors[$name] = $value;
    }

    public function hasErrors() {
        return !empty($this->_errors);
    }

    public function _load($id) {
        // load record from database
    }

    public function save() {
        if (!this->hasErrors()) {
            // save record to database
        }
    }
}
?>

I have looked around and many have suggest to use exceptions. However, I don't quite get how I can use them because wouldn't throwing an exception in one setter cause the subsequent setters from not being called.

OOP Design Question - Validating properties
Validate on entry or before saving?

Here is how I am currently using my class:

edit_course.php

<?php
$filter = array(
    'hidSubmit' => FILTER_VALIDATE_BOOLEAN,
    'code' => FILTER_SANITIZE_STRING,
    'name' => FILTER_SANITIZE_STRING
);

$c = filter_input(INPUT_GET, 'c', FILTER_VALIDATE_INT);
$course = new Course($c);

$inputs = filter_input_array(INPUT_POST, $filter);
if ($inputs['hidSubmit']) {
    $course->setName($inputs['name']);
    $course->setDescription($inputs['description']);
    $course->save();
    refreshPage();
}

require_once 'header_admin.php';
?>

<form id="editForm" name="editForm" action="" method="post">
<fieldset>
<legend>Edit Course</legend>
    Code
    <input type="text" name="code" value="<?php echo $course->getCode(); ?>" maxlength="10" size="8" />
    <?php echo $course->getError('code'); ?>
    Name
    <input type="text" name="name" value="<?php echo $course->getName(); ?>" maxlength="45" size="25" />
    <?php echo $course->getError('name'); ?>
    <input type="submit" value="Save" />
    <input type="hidden" name="hidSubmit" value="1" />
</fieldset>
</form>

<?php
require_once 'footer_admin.php';
?>

The big disadvantage of putting the validation to the setter is that you are never able to set invalid values. In most cases this is fine, but in some scenarios a valid user input differs from a more general valid field content. In addition the validation is also executed to internal setter uses where know that they are valid.

That said, I recommend setters to be only setters and not more.

The validation itself can be placed in a separate method or even in a separate class (depending on the complexity).

If you only want to display one error message, throwing an exception within the validation should be fine.

If you want to collect multiple error messages, you might want to build a generic validation class:

$valid=new Validation();
$valid->assertNotEmpty($name,"name","Insert a name please");
$valid->assertLength($name,3,50,"name","...");
...
if ($valid->hasErrors()) ...

You could extend this to a CourseValidation if you need it at multiple locations.

$valid=new CourseValidation($code,$name);
...


Finding elements inside ExpandoObject Is it possible to simplify the code below?

dynamic model = GetExpandoObject(); //model type of ExpandoObject

var result = model.FirstOrDefault(x => x.Key == "node").Value;

if (result != null)
{
    result = ((ExpandoObject)result).FirstOrDefault(x => x.Key == "children");

    if (result != null)
    {
        result = ((IList<object>)((KeyValuePair<string, object>)result).Value).FirstOrDefault();

        if (result != null)
        {
            if (result != null)
            {
                result = ((ExpandoObject)result).FirstOrDefault(x => x.Key == "node").Value;

                if (result != null)
                {
                    result = ((ExpandoObject)result).FirstOrDefault(x => x.Key == "stuff");
                }
            }
        }
    }
}

Maybe it is possible to implement similar logic with Linq?  Any thoughts?

In your code, the variable result is just of type object because the compiler doesn't know what the result of FirstOrDefault is going to be.

Below I've used explicit typing using T for clarity and so that var doesn't evaluate to object

I created this extension method so that you wouldn't have to cast the object everytime you wanted to use it... this takes care of that before it returns

public static class ExtensionMethods
{
    public static T FirstOrDefault<T>(this ExpandoObject eo, string key)
    {
        object r = eo.FirstOrDefault(x => x.Key == key).Value;
        return (r is T) ? (T)r : default(T);
    }
}

What follows is a re-implementation of the original post's code using the above method

ExpandoObject model = GetExpandoObject();

var someExpandoObject = model.FirstOrDefault<ExpandoObject>("node");
if (someExpandoObject == null) return;

var kvp = someExpandoObject.FirstOrDefault<KeyValuePair<string, object>>("children");
if (kvp.Equals(default(KeyValuePair<string, object>))) return;

var ilo = kvp.Value as IList<object>;
if (ilo == null) return;

someExpandoObject = ilo.FirstOrDefault() as ExpandoObject;
if (someExpandoObject == null) return;

someExpandoObject = someExpandoObject.FirstOrDefault<ExpandoObject>("node");
if (someExpandoObject == null) return;

object finalResult = someExpandoObject.FirstOrDefault<object>("stuff");

What follows is another possible implementation using nested if statements instead of multiple return statements.

ExpandoObject model = GetExpandoObject();

ExpandoObject someExpandoObject;
KeyValuePair<string, object> kvp;
IList<object> ilo;
object finalResult;

if ((someExpandoObject = model.FirstOrDefault<ExpandoObject>("node")) != null)
{
    if (!(kvp = someExpandoObject.FirstOrDefault<KeyValuePair<string, object>>("children")).Equals(default(KeyValuePair<string, object>)))
    {
        if ((ilo = kvp.Value as IList<object>) != null)
        {
            if ((someExpandoObject = ilo.FirstOrDefault() as ExpandoObject) != null)
            {
                if ((someExpandoObject = someExpandoObject.FirstOrDefault<ExpandoObject>("node")) != null)
                    finalResult = someExpandoObject.FirstOrDefault<object>("stuff");
            }
        }
    }
}

Update:
Using a newer feature of C# null-propagation, we can string all these calls together. Now we no longer need to save each object down the chain (unless we want to).

Here is an implementation using null-propagation.

object finalResult = ((model.FirstOrDefault<ExpandoObject>("node")
    ?.FirstOrDefault<KeyValuePair<string, object>>("children").Value as IList<object>)
    ?.FirstOrDefault() as ExpandoObject)
    ?.FirstOrDefault<object>("stuff");


Nested loops - Random Forest, multiple parameters I'm writing a code which task is to grow Random Forest trees based on multiple parameters. In short:

Firstly, I declare a data frame in which model parameters and some stats will be saved.
Secondly, I declare model parameters and the loop iterator (it will be showed after every loop iteration).
Next, I have a nested loops with the model and prediction function.
Furthermore, parameters and some stats from the confusion matrix are saved to the dataframe.
Additionally, the number of iterations is printed and counted.
Last but not least, garbage collector is called.

The code looks like this:

## data frame in which model parameters and some stats will be saved

model_eff <- data.frame("ntrees" = numeric(0),
                        "zeros" = numeric(0),
                        "mvars"= numeric(0),
                        "eff" = numeric(0),
                        "0_0" = numeric(0),
                        "0_1" = numeric(0),
                        "1_0" = numeric(0),
                        "1_1" = numeric(0),
                        "predict_sum" = numeric(0),
                        "triangle" = numeric(0))

## parameteres

ntrees <- c(300, 500)
zeros <- sum(train.target) * c(1, 2, 3, 4, 5)
mvars <- c(30, 50, 70, 90, 110, 130)

## loop counter

i = 1

## loop with model, prediction etc.

for (j in 1:length(ntrees)){
  for (k in 1:length(zeros)){
    for (l in 1:length(mvars)){

      ## i-th model

      model <- randomForest(train,
                            y = as.factor(train.target),
                            ntree = ntrees[j],
                            do.trace = T,
                            sampsize = c('0' = zeros[k], '1' = sum(train.target)),
                            mtry = mvars[l])

      ## prediction - my function, apart from a regular prediction
      ##              outputs additional info

      predict.model(model, val, val.target)

      ## inserting model parameters and stats to a data frame for further comparisons

      model_eff <- rbind(model_eff,
                         c("ntrees" = ntrees[j],
                           "zeros" = zeros[k],
                           "mvars"= mvars[l],
                           "eff" = eff_measures$eff,
                           "0_0" = eff_measures$c.m[1, 1],
                           "0_1" = eff_measures$c.m[1, 2],
                           "1_0" = eff_measures$c.m[2, 1],
                           "1_1" = eff_measures$c.m[2, 2],
                           "predict_sum" = sum(TARGET3),
                           "triangle" = eff_measures$triangle))

      ## printing the number of iteration

      cat("iteration =", i)
      i <- i+1

      ## calling garbage collector to assure free space in RAM

      gc()
    }
  }
}

I have already split the train/validation data sets and their target variables, knowing that Random Forest deals with such data mor efficiently. I also tried to use the "foreach" package for parallelizing computations, however, the growing time for only one tree was 10-15% longer than without using all the cores.

I would like to know if I can shorten the time of execution of this code, especially if there is a way to avoid multiple loops since I heard that they are not the best way of programming in R.

Reproducible Example

Unfortunately, the code snippet that you gave does not lend itself to being reproducible. So, the advice being given is constrained.

Caches are nice

There are certain times where you should be caching a summation if the value is known to be constant through different iterations. In this particular case, we have: sum(train.target) and sum(TARGET3) that should be cached. Say:

stt = sum(train.target)
st3 = sum(TARGET3)

Knowledge (of size) is Power!

Immediately, one of the key issue you will face is the fact that you are rbind 60 items since you avoid giving stable numerical entries in the data.frame

## parameteres

ntrees <- c(300, 500)
zeros <- sum(train.target) * c(1, 2, 3, 4, 5)
mvars <- c(30, 50, 70, 90, 110, 130)

nitr = length(ntrees)*length(zeros)*length(mvars)

model_eff <- data.frame("ntrees" = numeric(nitr),
                        "zeros"  = numeric(nitr),
                        "mvars"  = numeric(nitr),
                        "eff"    = numeric(nitr),
                        "0_0"    = numeric(nitr),
                        "0_1"    = numeric(nitr),
                        "1_0"    = numeric(nitr),
                        "1_1"    = numeric(nitr),
                        "predict_sum" = numeric(nitr),
                        "triangle"    = numeric(nitr),
                        stringsAsFactors = F)

Declare count = 1 before the 3x for loops. Then save results using:

model_eff[count,] = c("ntrees" = ntrees[j],
                      "zeros" = zeros[k],
                      "mvars"= mvars[l],
                      "eff" = eff_measures$eff,
                      "0_0" = eff_measures$c.m[1, 1],
                      "0_1" = eff_measures$c.m[1, 2],
                      "1_0" = eff_measures$c.m[2, 1],
                      "1_1" = eff_measures$c.m[2, 2],
                      "predict_sum" = st3 ,
                      "triangle" = eff_measures$triangle))
count = count + 1

Parallel RandomForest via caret

The only other suggestion I have it to parallelize the build of the random forest via:

# caret modeling framework
library(caret)

# Parallel backend
library(doParallel)

# Register a cluster
registerDoParallel(cores = 5)

rf_model = train(train.target~.,data=train,method="rf",
                 prox=TRUE,allowParallel=TRUE)


Simple implementation of HashMap I have implemented a HashMap which supports insertions of integer key value pairs. The approach uses an array for simplicity and uses a standard hash function. Please give a review on the coding approach used in the program.

import junit.framework.Assert;
import org.junit.Test;

public class HashMapImpl {
class HashMap {
    int SIZE_OF_TABLE = 128;
    HashEntry[] table;
    HashMap() {
        table = new HashEntry[SIZE_OF_TABLE];
        for (int i = 0; i < SIZE_OF_TABLE; i++) {
            table[i] = null;
        }
    }

    public void put(int key, int value) {
        int index = hashCodeNew(key);
        System.out.println(index);
        HashEntry hashEntry = new HashEntry(key, value);
        if (table[index] == null) {
            table[index] = hashEntry;
        } else {
            HashEntry runner = table[index];
            while (runner.next != null) {
                if (runner.key == hashEntry.key) {
                    runner.value = hashEntry.value;
                    break;
                } else {
                    runner = runner.next;
                }
            }
            if (runner.next == null) {
                if (runner.key == hashEntry.key) {
                    runner.value = hashEntry.value;
                } else {
                    runner.next = hashEntry;
                }
            }
        }

    }

    public int get(int key) {
        int index = hashCodeNew(key);
        if (table[index] == null) {
            return -1;
        } else {
            HashEntry runner = table[index];
            if (runner.key == key) {
                return runner.value;
            }
            while (runner.next != null) {
                if (runner.key == key) {
                    return runner.value;
                }
            }
            return -1;
        }
    }

    public int hashCodeNew(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        int hashCode = h ^ (h >>> 7) ^ (h >>> 4);
        return hashCode % SIZE_OF_TABLE;
    }
}

class HashEntry {
    int key;
    int value;
    HashEntry next = null;

    HashEntry() {
    }

    public HashEntry(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return this.key;
    }

    public int getValue() {
        return this.value;
    }
}

@Test
public void testBasic() {
    HashMap hashMap = new HashMap();
    hashMap.put(10, 20);
    hashMap.put(20, 11);
    hashMap.put(21, 1);
    hashMap.put(20, 10);

    int value = hashMap.get(20);
    Assert.assertEquals(10, value);

}
}

Besides what has already been mentioned:

public class HashMapImpl {
class HashMap {

What's going on here? HashMapImpl is never used. This should be just simply

public class HashMap {

Don't have your unit tests inside of the class implementation, unit tests should be in a separate folder structure that mirrors your source structure. That way you don't have to ship the unit tests with your program when you release it.

Also this:

public int hashCodeNew(int h) {

should be private.

You're implementing the hash chaining as a linked list which has poor cache locality. You might just be better of having:

List<List<HashEntry>> table = new ArrayList<>(SIZE_OF_TABLE);

and let HashEntry be like this:

private class HashEntry {
    int key;
    int value;

    public HashEntry(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

As HashEntry is a class only used inside of HashMap it should be private or protected. Because it is protected or private and it is pretty much just a POD structure, you can just drop the accessors (get/set methods) which you weren't using anyway. Rule of thumb, if you're not using some parts of the code, remove them. The less code you have the better (generally). But don't skimp on the white space :)

Your put method allows the use of -1 as a key, but your get method uses -1 to signal a 'no such element' condition. Either you need to throw a IllegalArgumentException from put or you need to use another way of signaling that there is no such entry. I would suggest throwing NoSuchElementException like this:

public int get(int key) {
    int index = hashCodeNew(key);
    if (table[index] == null || table[index].size() < 1) {
        throw new NoSuchElementException("The key: \"" + key + "\" was not found in the map!");
    } else {
        ...
        throw new NoSuchElementException("The key: \"" + key + "\" was not found in the map!");
    }
}

While we're at it, notice that we have two code paths that result in the same action if an error occurs, we can rearrange this as:

public int get(int key) {
    int index = hashCodeNew(key);
    if (table[index] != null) {
        for(HashEntry entry : table[index]){
            if(entry.key == key)
                return entry.value;
        }
    }
    throw new NoSuchElementException("The key: \"" + key + "\" was not found in the map!");
}

Lets take a look at the put() function too, adapting it to use a list of lists for chaining and cleaning it up a bit:

public void put(int key, int value) {
    int index = hashCodeNew(key);
    HashEntry hashEntry = new HashEntry(key, value);

    List<HashEntry> chain = table[index];
    if (chain == null) {
        chain = new ArrayList<>();
    }

    Iterator<HashEntry> it = chain.iterator();
    while(it.hasNext()){
        if(it.next().key == key){
            it.remove();
            break;
        }
    }
    chain.add(hashEntry);
    table[index] = chain;
}

Your hash function is terrible:

public int hashCodeNew(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    int hashCode = h ^ (h >>> 7) ^ (h >>> 4);
    return hashCode % SIZE_OF_TABLE;
}

It doesn't handle negative h. You're basically just changing the lower bits, the high bits are mostly unaffected. A better (and faster) way is to simply multiply by a sizeable prime number:

private final static long BIG_PRIME = 175365371; // The 9,786,124th prime number
public int hashCodeNew(int h) {
    if( h >= 0) // 0 always at index 0.
        return (int)(h*BIG_PRIME) % SIZE_OF_TABLE;
    else
        return (int)((Integer.MAX_VALUE-h)*BIG_PRIME) % SIZE_OF_TABLE;
}

Why big? So that more of the available bits in the hash code are used.

Edit I just looked up Integer.hashCode() and it returns the value of the integer. Which implies that that is good enough as a hash and why wouldn't it be? All hash values are unique and evenly distributed. So:

public int hashCodeNew(int h) {
    return (h & Integer.MAX_VALUE) % hash.size();
}

First use Integer.MAX_VALUE which is \$2^{31} -1\$ to mask out the sign bit and then just take modulo. Handles negative values without a branch and is as fast as it gets without assuming the hash table is a power of two size (in which case simply use h & (hash.size() - 1)).


Generic methods for serializing and deserialzing xml files using streams followup Recently I asked this question: Generic methods for serializing and deserialzing xml files using streams

However it has come to my attention that this gives me an (harmless) exception when trying to deserialize.

System.IO.FileNotFoundException occurred
  Message="Could not load file or assembly '[Containing Assembly of MyType].XmlSerializers, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null' or one of its dependencies. The system cannot find the file specified."
  Source="mscorlib"
  FileName="[Containing Assembly of MyType].XmlSerializers, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null"
  FusionLog=""
  StackTrace:
   at System.Reflection.Assembly._nLoad(AssemblyName fileName, String codeBase, Evidence assemblySecurity, Assembly locationHint, StackCrawlMark& stackMark, Boolean throwOnFileNotFound, Boolean forIntrospection)
   at System.Reflection.Assembly.nLoad(AssemblyName fileName, String codeBase, Evidence assemblySecurity, Assembly locationHint, StackCrawlMark& stackMark, Boolean throwOnFileNotFound, Boolean forIntrospection)

It is a well known problem and most people would fix it by adding this to their csproj:

<Target Name="AfterBuild" DependsOnTargets="AssignTargetPaths;Compile;ResolveKeySource" Inputs="$(MSBuildAllProjects);@(IntermediateAssembly)" Outputs="$(OutputPath)$(_SGenDllName)">
   <!-- Delete the file because I can't figure out how to force the SGen task. -->
   <Delete
     Files="$(TargetDir)$(TargetName).XmlSerializers.dll"
     ContinueOnError="true" />
   <SGen
     BuildAssemblyName="$(TargetFileName)"
     BuildAssemblyPath="$(OutputPath)"
     References="@(ReferencePath)"
     ShouldGenerateSerializer="true"
     UseProxyTypes="false"
     KeyContainer="$(KeyContainerName)"
     KeyFile="$(KeyOriginatorFile)"
     DelaySign="$(DelaySign)"
     ToolPath="$(TargetFrameworkSDKToolsDirectory)"
     Platform="$(Platform)">
      <Output
       TaskParameter="SerializationAssembly"
       ItemName="SerializationAssembly" />
   </SGen>
</Target>

However I've tried something different namely:

public static T DeserializeObject<T>(this Stream stream) where T : IXmlSerializable
{
    Parameters.RequireNotNull(stream, "stream");

    using (var xmlTextReader = XmlReader.Create(stream))
    {
        var importer = new XmlReflectionImporter()
        var mapping = importer.ImportTypeMapping(typeof(T));
        var serializer = new XmlSerializer(mapping);

        T result = (T)serializer.Deserialize(xmlTextReader);
        stream.Close();
        return result;
    }
}

So my question, is this good code? is this a proper work around?

So my question, is this good code? is this a proper work around?

I would ask different questions:

Does the code work?
Could you avoid editing the csproj file?

If both answers are yes, the I'd say it's a good workaround... but not a perfect one.

stream.Close();

This line shouldn't be there. The caller should take care of disposing the stream. Every method should keep track only of its own resources. The ones that come from the outside world should be taken care of by their respective owner.

I'd be really surprised if I called this method and wanted to work with the stream later but get an exception that it has already been closed.


XML file parsing in Go Below is a piece of code that is responsible for serializing files.
ZL_LIST and PERS_LIST are XML file structs, I have not shown them here to save space.

Please check my code.

package parser

import (
    "encoding/xml"
    "fmt"
    "golang.org/x/text/encoding/charmap"
    "io"
    "io/ioutil"
    "os"
    "path/filepath"
    "sync"
)

type Files struct {
   Name          string
   PathZipFile   string
   PathUnzipFile string
}

type nameMap map[string]bool

func (ZL_LIST) Parse(FilesName []*Files) {
    unzipPath, err := filepath.Abs("tmp")

    files, err := ioutil.ReadDir(unzipPath)
    f := make([]*Files, 0)
    for _, file := range files {
        fileZip := new(Files)
        if !file.IsDir() && file.Name()[:1] != "." {
            fileZip.Name = file.Name()
            fileZip.PathUnzipFile = filepath.Join(unzipPath, file.Name())
            f = append(f, fileZip)
        }
    }

    if err != nil {
        fmt.Printf("[ERROR] Error retrieving files %v", err)
    }

    names := make(nameMap, 1)
    var wg sync.WaitGroup
    var countHmLmFiles int = -1
    var countHmFiles int = 0
    var countLmFiles int = 0
    var file *Files
    for countHmLmFiles, file = range f {
        wg.Add(1)
        go func(filename *Files) {
            parseHmLm(filename, &countHmFiles, &countLmFiles, &names)
            wg.Done()
        }(file)
    }
    wg.Wait()

    fmt.Printf("[INFO] Read %d files from them  HM files %d and LM files %d ", countHmLmFiles+1, countHmFiles, countLmFiles)
}

func parseHmLm(filename *Files, countHmFiles *int, countLmFiles *int, names *nameMap) {
    fmt.Println("[INFO] считывается файл ", filename.Name, " с заголовком ", filename.Name[:2])
    xmlFile, err := os.Open(filepath.Join(filename.PathUnzipFile))
    if err != nil {
        fmt.Printf("[ERROR] Cannot open file %e \n", err)
    }

    defer xmlFile.Close()

    switch filename.Name[:2] {
    case "HM":
        (*names)[filename.Name] = true
        (*countHmFiles) += 1
        var hFile ZL_LIST
        decoder := xml.NewDecoder(xmlFile)
        decoder.CharsetReader =  charset
        err := decoder.Decode(&hFile)
        if err != nil {
            fmt.Errorf("[ERROR] Cannot decode file %e", err)
        }
    case "LM":
        (*countLmFiles) += 1
        var lFile PERS_LIST
        decoder := xml.NewDecoder(xmlFile)
        decoder.CharsetReader = charset
        err := decoder.Decode(&lFile)
        if err != nil {
            fmt.Errorf("[ERROR] Cannot decode file %e", err)
        }
    }

}

func charset(charset string, input io.Reader) (io.Reader, error) {
    switch charset {
    case "windows-1251":
        return charmap.Windows1251.NewDecoder().Reader(input), nil
    default:
        return nil, fmt.Errorf("unknown charset: %s", charset)
    }
}

Calling function

package api
    import (
    "net/http"
    "github.com/go-chi/render"
    "../../store/parser"
    "fmt"
    "path/filepath"
)
    func (s *Rest) parse(w http.ResponseWriter, r *http.Request) {
        uploadPath, err := filepath.Abs("./upload/")
        if err != nil {
            fmt.Printf("[ERROR] can not find the specified path %e", err)
        }
        unzipPath, err := filepath.Abs("./tmp")
        if err != nil {
            fmt.Printf("[ERROR] can not find the specified path %e", err)
        }
        p := parser.Files{}
        filesName := p.GetFileName(uploadPath, unzipPath)
            p.UnzipFiles(filesName, unzipPath)
        ...
        ...

Variables

Go has two ways of declaring new variables: a var notation and a short one. It's preferable to use the short one:

wg := sync.WaitGroup{}
countHmLmFiles := -1
countHmFiles := 0
countLmFiles := 0

Also when declaring lots of global variables in the package block you may use block notation:

var (
    a int = 1
    b string = "foo"
)

You can declare variables directly in the for loop:

for countHmLmFiles, file := range f {
    // countHmLmFiles and file will be visible only here
}

This way their scope will be limited to for body.

Maps in Go

You've created a map with make:

names := make(nameMap, 1)

I don't see a point in creating a map for a single element. Also when you don't need the size argument in make you may simply write names := nameMap{}.

No need pass maps with pointer. Maps and slices are already a reference type and may be passed directly by value. It won't issue a full copy.

Error handling

You've missed lots of error checks. Ideally every error must be handled in place. Otherwise use _ to ignore it and make a comment to be specific on this as it looks like a broken code.

The switch lacks the default case. It worth adding it to catch other possible values of filename.Name[:2].

Also don't forget to add terminating \n to fmt.Printf to separate log messages.


Performing machine learning I've written the code below to do some work on machine learning in R. I'm not overly happy with some bits of it, and I suspect I could improve it quite a bit. Bits I'm specifically interested in looking at are how to deal with appending to vectors in the loop, and whether I can combine all of the functions kf.knn, kf.svm etc into one function with various arguments.

library(class)
library(nnet)
library(epibasix)
library(CVThresh)
library(e1071)

df <- read.table("semeion.data.data")
df$digit <- replicate(nrow(df), 42)

df$digit[which(as.logical(df$V266), arr.ind=TRUE)] = 9
df$digit[which(as.logical(df$V265), arr.ind=TRUE)] = 8
df$digit[which(as.logical(df$V264), arr.ind=TRUE)] = 7
df$digit[which(as.logical(df$V263), arr.ind=TRUE)] = 6
df$digit[which(as.logical(df$V262), arr.ind=TRUE)] = 5
df$digit[which(as.logical(df$V261), arr.ind=TRUE)] = 4
df$digit[which(as.logical(df$V260), arr.ind=TRUE)] = 3
df$digit[which(as.logical(df$V259), arr.ind=TRUE)] = 2
df$digit[which(as.logical(df$V258), arr.ind=TRUE)] = 1
df$digit[which(as.logical(df$V257), arr.ind=TRUE)] = 0

data <- df[,c(0:256,267)]

squareTable <- function(x,y) {
    x <- factor(x)
    y <- factor(y)

    commonLevels <- sort(unique(c(levels(x), levels(y))))

    x <- factor(x, levels = commonLevels)
    y <- factor(y, levels = commonLevels)

    table(x,y)

}

kf.knn <- function(data, k, nearest)
{
  N <- nrow(data)
  data <- data[sample(1:N),]

  folds.index <- cvtype(N, cv.bsize=1, cv.kfold=k, FALSE)$cv.index

  total = 0

  for (i in 1:k)
  {
    test <- data[folds.index[i,], 0:256]
    test.labels <- data[as.array(folds.index[i,]), 257]

    rest <- as.array(folds.index[-i,])

    train <- data[rest, 0:256]
    train.labels <- data[rest, 257]

    knnpredict <- knn(train, test, train.labels, nearest)
    t <- table(as.factor(test.labels), as.factor(knnpredict))

    kap <- epiKappa(t)
    total <- total + kap$kappa
  }

return(total / k)
}

kf.nnet <- function(data, k, hidden)
{
  N <- nrow(data)
  data <- data[sample(1:N),]

  folds.index <- cvtype(N, cv.bsize=1, cv.kfold=k, FALSE)$cv.index

  total = 0

  for (i in 2:k)
  {
    test <- data[folds.index[i,], 0:256]
    test.labels <- data[as.array(folds.index[i,]), 257]

    rest <- as.array(folds.index[-i,])

    train <- data[rest, 0:256]
    train.labels <- data[rest, 257]

    train$label <- as.factor(train.labels)

    nnetwork <- nnet(label ~ ., data=train, size=hidden, MaxNWts = 10000, maxit=200, linout=TRUE)
    nnetpredict <- predict(nnetwork, test, "class")

    table <- squareTable(as.factor(test.labels), as.factor(nnetpredict))

    print(table)
    kap <- epiKappa(table)
    total <- total + kap$kappa
  }

return(total / k)
}

kf.svm <- function(data, k)
{
  N <- nrow(data)
  data <- data[sample(1:N),]

  folds.index <- cvtype(N, cv.bsize=1, cv.kfold=k, FALSE)$cv.index

  total = 0

  for (i in 2:k)
  {
    test <- data[folds.index[i,], 0:256]
    test.labels <- data[as.array(folds.index[i,]), 257]

    rest <- as.array(folds.index[-i,])

    train <- data[rest, 0:256]
    train.labels <- data[rest, 257]

    train$label <- as.factor(train.labels)

    svmmodel <- svm(label ~ ., data=train, cost=8, gamma=0.001, cross=2)
    svmpredict <- predict(svmmodel, test)

    t <- table(as.factor(test.labels), as.factor(svmpredict))
    print(t)
    kap <- epiKappa(t)
    total <- total + kap$kappa
  }

return(total / k)
}

result <- vector("numeric", 1)
n <- vector("numeric", 1)

for (i in 2:10)
{
  avg <- kf.nnet(data, 5, i)
  result <- append(result, avg)
  n <- append(n, i)
  cat("!!!!!!!", i, avg, "\n")
}

result <- result[2:length(result)]
n <- n[2:length(n)]

df <- data.frame(kappa = result, n=n)
plot(df$n, df$res)

print(df)

You can avoid appending to vectors (which can cause re-allocation of space and can considerably slow things down in principle; though in your case of only a length 10 vector that shouldn't be noticeable) if you allocate them to the needed size initially and then assign within them.

result <- vector("numeric", 10)
# or even: result <- numeric(10)
n <- vector("numeric", 10)

for (i in 2:10)
{
  avg <- kf.nnet(data, 5, i)
  result[i] <- avg
  n[i] <- i
  cat("!!!!!!!", i, avg, "\n")
}

I'm not clear what you are asking about combing function; you can add an additional argument which is a character vector which then the code just has a series of if/elseif's checking that parameter to see which algorithm to use, if that is what you mean.


Select box to highlight choice deviation I have a select box that in default state looks as default (white, etc)
but when I select a different value, I want the entire table row to highlight in yellow.

I did this, but I want to make it better and more concise and more efficient.  Can you help?

Also I will have several such boxes, not just one.  Feel free to change/add/remove identifiers, I am looking for a better solution overall.

$(document).ready(function() {

  $("#closedRow").on('change', function() {
    if ($("#closedRow").val() != 0)
      $("#trRow").css('background-color', 'yellow');
    else
      $("#trRow").css('background-color', 'white');
  })

    $("#serviceRow").on('change', function() {
    if ($("#serviceRow").val() != 0)
      $("#trRow2").css('background-color', 'yellow');
    else
      $("#trRow2").css('background-color', 'white');

  })
})

    Closed:
    <select name="closed" id="closedRow">
            <option value="0">Show All</option>
            <option value="1">Hide Closed</option>
        </select>

    Service:
    <select name="service" id="serviceRow">
            <option value="0">Show All</option>
            <option value="1">Hide Service</option>
            <option value="2">Another Service</option>
        </select>

Maybe use a generic function to set the css on change if you don't have anything other than colors. It also helps with dry.

function evt_highlightRow() {
    row = $(this).parent().parent()
    if ($(this).val() != 0)
      row.css('background-color', 'yellow');
    else
      row.css('background-color', 'white');
}

Then use it like so:

$(some_target_nested_2_deep).on('change', evt_highlightRow);

// such as your select
$('select').on('change', evt_highlightRow);
// or a generic class applied to inputs in the same general location
$('.highlightRowTarget').on('change', evt_highlightRow);

I created the example here: https://codepen.io/anon/pen/bWraNB


Project Euler 3: Largest prime factor How can I improve my code, make it more efficient, and are there any tips you have?

Project Euler 3:

  The prime factors of 13195 are 5, 7, 13 and 29.

  What is the largest prime factor of the number 600851475143 ?

public class LargestPrimeFactor {

    public static void main(String[] args) {

        long num = 600851475143L;
        boolean isPrime = true;

        // this is to see if num is factorable
        for (int i = 2; i < num; i++) {

            //if i is a factor, check if its prime
            if (num % i == 0) {

                for (int j = 2; j < i; j++) {

                    if (i % j == 0) {

                        isPrime = false;

                    }

                }

                if (isPrime) {

                    System.out.println(i);

                }

            }

        }

    }

}

A small note first, please do not double-space all lines in code, it just makes it harder to read, rather than easier.

Integer overflow

Using an int primitive type for i and j is causing the number to go through integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$),  once it exceeds the maximum value 2,147,483,647 (or \$2^{31}-1\$), then finally all the way back from there to \$0\$, resulting in a java.lang.ArithmeticException: divide by zero. To correct this, use a long type for the iterators instead:

    // this is to see if num is factorable
    for (long i = 2; i < num; i++) {
        //if i is a factor, check if its prime
        if (num % i == 0) {
            for (long j = 2; j < i; j++) {

Algorithm

With the above problem fixed, we can now see that the algorithm you use has a few problems. Given the number \$n = 600851475143\$

It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.
For each \$i\$, it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.
It returns each number that matches both criteria, e.g., 71, 839, 1471 and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\$, which takes a very long time.

The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo as well.

class LargestPrimeFactor  {

    public static void main(String[] args) {

        long N = 600851475143L;

        // First, start from the maximum number and divide by 2
        // until you can no longer divide evenly by 2, i.e., the number is odd
        while (N % 2 == 0) {

            // in the case of 600851475143 this will be skipped entirely since it is an odd number,
            // but for the sake of generality we will keep it so it can be used on any number
            N /= 2;
        }

        // the next prime number is 3, and all prime numbers from there are odd numbers,
        // so we can safely just add 2 to the factor each time and only test for odd numbers
        // note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
        // like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
        for (long factor = 3; factor < N; factor += 2) {

            // if N is evenly divisible by the factor, then we just divide it, and we keep going
            // until N can no longer be divided by a number smaller than itself,
            // in other words, until N is a prime number
            while (N % factor == 0 && factor < N) {
                N /= factor;
            }
        }
        System.out.println("The answer is " + N);
    }
}


Interplanetary weight calculator I have been using this site for a couple of years for great answers and a ton of help. I wrote this program for my class project due 1/23. I am just wondering what you would recommend me changing or improving. I think I have some repetitive code, but I have not learned about defs in Java yet.

package project2;

import java.util.Scanner;

/**
 * @author Sartaj Singh
*/
public class Project2 {

    public static void main(String[] args) {

        int choice = 0;
        double weight;
        double earth = 9.81;
        double moon = 1.622;
        double mercury = 3.7;
        double venus = 8.87;
        double jupiter = 24.79;

        System.out.println("Welcome to Planetary Weight Calculator: ");
        Scanner input = new Scanner(System.in);
        System.out.print("Enter your weight in pounds (lb): ");
        weight = input.nextDouble();
        while (weight <= 0) {
            System.out.println("Invalid Input - Plase enter a value higher than 0 ");
            System.out.print("Enter your weight in pounds (lb): ");
            weight = input.nextDouble();
        }
        System.out.println("/////MENU/////");
        System.out.println("1 - Moon");
        System.out.println("2 - Mercury");
        System.out.println("3 - Venus");
        System.out.println("4 - Jupiter");
        System.out.print("Pick a number 1-4: ");
        choice = input.nextInt();
        while (choice <= 0 || choice >= 5) {
            System.out.println("/////MENU/////");
            System.out.println("1 - Moon");
            System.out.println("2 - Mercury");
            System.out.println("3 - Venus");
            System.out.println("4 - Jupiter");
            System.out.print("Pick a number 1-4: ");
            choice = input.nextInt();
        }
        switch (choice) {
            case 1:
                System.out.println("You selected Moon, your weight on Moon is: ");
                System.out.println(weight * (moon / earth) + " Lbs");
                break;
            case 2:
                System.out.println("You selected Mercury, your weight on Mercury is: ");
                System.out.println(weight * (mercury / earth) + " Lbs");
                break;
            case 3:
                System.out.println("You selected Venus, your weight on Venus is: ");
                System.out.println(weight * (venus / earth) + " Lbs");
                break;
            case 4:
                System.out.println("You selected Jupiter, your weight on Jupiter is: ");
                System.out.println(weight * (jupiter / earth) + " Lbs");
                break;
        }

        System.out.println("Thank you for using the Planetary Weight Calculator");
        System.out.println("Hope you will use it again! ");

    }

}

I would create a class for the Planets for a more scalable and Object Oriented design, as detailed below

The class would store Earth's G in a constant, because it does not change in any planet's calculation.
The constructor should require the planet's own G value and it's name (for the Print statements, discussed further below).
You can also add a method to calculate the resultant weight based on a given weight value, to follow along with the Object Oriented approach.

public class Planet {

final double earthG = 9.81;
double myG;
public String planetName;

public Planet(String planetName, double myG){
    this.myG = myG;
    this.planetName = planetName;
}

public double calculateWeight(double weight){
    return weight * myG/earthG;
}
}

In the main method I would create an array of Planets for readability,

Planet[] planets = new Planet[]{new Planet("Moon", 1.622),
                                new Planet("Mercury", 3.7),
                                new Planet("Venus", 8.87),
                                new Planet("Jupiter", 24.79)};

And use a Do-While loop to populate the loop instead of the While loop. The Do-While checks for the condition at the end, so the first print doesn't requires an input.

do{
   ...
  } while(expression);

You can also use the array to populate the menu itself using for loop. This is especially helpful if you have a large number of planets/items in the array.

do {
    System.out.println("/////MENU/////");
    for(int i=0;i<planets.length;i++){
        System.out.println(i + " - " + planets[i].planetName);
       }
    System.out.print("Pick a number 0 - " + planets.length + ": ");
    choice = input.nextInt();
    } while (choice <= 0 || choice >= 5);

Using the array has a massive advantage here for the output statement. Since the choice corresponds to the planet's position in the array, you can simply call the appropriate planet's method as planets[choice].calculateWeight(weight). Following two lines will suffice the purpose of the previous Switch-Case.

System.out.println("You selected " + planets[choice].planetName + ", your weight on " + planets[choice].planetName + " is: ");
System.out.println(planets[choice].calculateWeight(weight) + " Lbs");


C++ operator overloading for rationalNumber I have created a rationalnumber class and used operator overloading function of C++.

My questions are:

Have I implemented the class and < operator correctly?
Objects of class can now inserted in map and set. Is that part done correctly?

#include <bits/stdc++.h>
using namespace std;

class RationalNumber {
    int num;
    int den;
    bool negative;
    int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
public:
    RationalNumber() {
        num = den = 1;
        negative = 0;
    }
    RationalNumber(int a, int b) {
        if ((a < 0) ^ (b < 0))
            negative = 1;
        else
            negative = 0;
        num = abs(a);
        den = abs(b);
        int h = gcd(a, b);
        num /= h;
        den /= h;
    }
    RationalNumber operator+(const RationalNumber &r) {
        RationalNumber added;
        added = RationalNumber(num * r.den + r.num * den, den * r.den);
        return added;
    }
    bool operator<(const RationalNumber &r) const {
        return num * r.den < r.num * den;
    }

    void toString() {
        cout << num << "/" << den << endl;
    }
};
int main(int argc, char **argv) {
    RationalNumber r1(3, 5);
    RationalNumber r2(1, 3);
    RationalNumber r3 = r1 + r2;
    RationalNumber r4(9, 13);
    vector<RationalNumber> v;
    map<RationalNumber, string> S;
    map<RationalNumber, string>::iterator it;
    S[r1] = "1";
    S.insert(S.begin(), pair<RationalNumber, string>(r2, "2"));
    S.insert(S.begin(), pair<RationalNumber, string>(r2, "2"));
    S.insert(S.begin(), pair<RationalNumber, string>(r3, "3"));
    S.insert(S.begin(), pair<RationalNumber, string>(r4, "4"));
    for (it = S.begin(); it != S.end(); ++it) {
        RationalNumber r = it->first;
        r.toString();
        cout << it->second << endl;
    }
    return 0;
}

Style:

Use an initialiser list for constructors, with meaningful parameter names. example at the end.
Please use the right type for negative - true/false makes it a lot easier to read and understand inline what type negative is.
Naming: The toString() is easier expressed by returning a std::string - that can be used as-is or forwarded to std::cout or other logs. If you want to use a log output, (e.g. std::cout) it can be trivially implemented using a template operator<< with a generic ostream input - in this case it is not required (see below)
The operator+ can be expressed in a single line, without the temporary added variable.
it is desirable to make gcd an non-member file-local static function (static gcd(int a, int b)) the rationale being that the logic:

doesn't depend on the state (or const-ness) of the Rational object (so non-member)
doesn't need to access the (private/protected) innards of Rational(so non-static, non-friend)

In main, the for loop can be shortened (in general, if a function call chain helps avoid a temp variable, do so). example at the end.

The same logic (avoiding a temp variable) holds for defining r3 and r4 inlined when adding them to the map.

vector v is unused.
Include what you use: vector, map, iostream, cmath (and iterator if you decide to use ostream_iterator.
maps don't require an input iterator during insertion. Use std::make_pair(a, b) to cut down on the verbose template boilerplate.

Logical Issues:

Translation into abs and negative is done in the ctor and not followed up well in other places. This will fail for negative test cases. hint: why is negative required as a member?
adding 1/4 and 1/2 results in 6/8 - while this isn't incorrect, this defeats the purpose. Invoke gcd there.
Depending on how you want your object to behave, handle the case of (den == 0), either by explicity asserting against its occurence, or by adding special handling for arithmetic operators. You don't want a 1/0 + 5/2 == 2/0 comparison.

Constructor style preferred:

RationalNumber() : num(1), den(1), negative(false) {}
RationalNumber(int numerator, int denominator)
: num(abs(numerator))
, den(abs(denominator))
, negative((numerator < 0) == (denominator < 0))
{
    //use gcd here
}

Terser loop style suggestions:

for (map<RationalNumber, string>::iterator it = S.begin(); it != S.end();++it)
{
    std::cout << "comparing:" << itr->first.toString() << itr->second << std::endl;
}

or the even terser lambda:

transform(S.begin(), S.end(), ostream_iterator<string>(cout, '\n'),
    [] (const pair<RationalNumber, string>& p) { return p.first.toString() + " " + p.second; });

edits:
Moved code examples to the end - as code indents don't work in between bulleted points.


Luhn algorithm in Ruby I'm learning Ruby 2.3 and I've tried to implement a function which performs the Luhn credit card verification algorithm on an input string, returning true if it matches and false if it doesn't.

def luhn(card_no)
    card_no.split("")  # Break into individual digits
           .reverse  # Start from the end
           .each_with_index
           .map {|x, i| i.odd? and x.to_i * 2 or x.to_i}  # Double every other digit
           .map {|x| if x.to_s.length > 1; x.to_s.split("").map(&:to_i).inject(:+); else x end}  # If any numbers are now 2-digit, add their digits
           .inject(:+) % 10 == 0  # Check if multiple of 10
end

p luhn("4070590981311") # => true
p luhn("3103138183910") # => false

Is there any way to make this code shorter or more "Ruby-like"? I'm sure there  must be a better way to perform the second map operation.

Don't flip back and forth between string manipulation and arithmetic. When is a number 2 digits? When it's greater than 9. Yes, you can convert to a string, and check the string length, but why bother? Just convert everything to a number immediately and stick to it.
Don't bother with adding digits when a number is greater than 9; just subtract 9. The result is the same.
Don't use split("") when there's the String#chars method.
Don't chain off of #each_with_index, when you can use the Enumerator#with_index "modifier" on #map, i.e. .map.with_index { ... }
Don't do this i.odd? and x.to_i * 2 or x.to_i when you have ternary branching: [condition] ? [true branch] : [else branch]
A slightly more descriptive method name would help too. Right now it's hard to tell if the method calculates the check digits, or checks the credit card number. Something like #valid_credit_card_number? is an option. That it's a Luhn algorithm is an implementation detail; external code just want to know if it's valid or not.

That said there are many, many ways to implement the Luhn algorithm. A simple refactoring could be

def luhn(card_no)
  card_no
    .chars       # Break into individual digits
    .map(&:to_i) # map each character by calling #to_i on it
    .reverse     # Start from the end
    .map.with_index { |x, i| i.odd? ? x * 2 : x } # Double every other digit
    .map { |x| x > 9 ? x - 9 : x }  # If > 9, subtract 9 (same as adding the digits)
    .inject(0, :+) % 10 == 0        # Check if multiple of 10
end

A different approach could be:

def luhn(card_no)
  card_no
    .chars
    .reverse
    .each_slice(2)
    .inject(0) do |sum, (a, b)|
      double = b.to_i * 2
      sum + a.to_i + (double > 9 ? double - 9 : double)
    end % 10 == 0
end

Oh and remember to also check the length of the card number, and that it is, in fact, all-numeric.


Separate numbers with commas How should I approach refactoring this code?

def separate_comma(number)
  a = number.to_s.split('')
  b = a.size/3.0
  if a.size < 4
    p number.to_s
  elsif a.size%3 == 0
    n = -4
    (b.to_i-1).times do |i|
      a.insert(n, ',')
      n -= 4
    end
    p a.join("")
  else
      n = -4
    b.to_i.times do |i|
      a.insert(n, ',')
      n -= 4
    end
  p a.join("")
  end
end

separate_comma(97425)    # => "97,425"
separate_comma(89552600) # => "895,926,600"
separate_comma(0)       # => "0"
separate_comma(100)     # => "100"

I am not sure how hard may be for a newbie to take on functional programming, but if you are interested in new ways of programming, check it out. A more specific article on Ruby: FP with Ruby. If you think in terms of expressions (what things are) instead of statements (update, insert, delete, ...), code is more declarative (and usually shorter). I'll use no regexps to show an alternative approach to the existing answer:
def separate_comma(number)
  reverse_digits = number.to_s.chars.reverse
  reverse_digits.each_slice(3).map(&:join).join(",").reverse
end

If you want to support decimals:
def separate_comma(number)
  whole, decimal = number.to_s.split(".")
  whole_with_commas = whole.chars.to_a.reverse.each_slice(3).map(&:join).join(",").reverse
  [whole_with_commas, decimal].compact.join(".")
end


PHP strpos() as a way to implement an swear word filter I wrote a short function that should check if user input does contain any bad words that I predefined inside $bad_words array. I don't even care to replace them - I just want to ban if there are any. The code seems to work as it should - in the example below will detect the quoted string badword and the function does return true.
My question: Is this a good way to use foreach and strpos()? Perhaps there is better way to check if $input contains one of the $bad_words array elements? Or is it just fine as I wrote it?
function checkswearing($input)
{
    $input = preg_replace('/[^0-9^A-Z^a-z^-^ ]/', '', $input);//clean, temporary $input that just contains pure text and numbers

    $bad_words = array('badword', 'reallybadword', 'some other bad words');//bad words array

    foreach($bad_words as $bad_word)
    {//so here I'm using a foreach loop with strpos() to check if $input contains one of the bad words or not
        if (strpos($input, $bad_word) !== false)
            return true;//if there is one - no reason to check further bad words
    }
    return false;//$input is clean!
}

$input = 'some input text, might contain a "badword" and I\'d like to check if it does or not';

if (checkswearing($input))
    echo 'Oh dear, my ears!';
else
{
    echo 'You are so polite, so let\'s proceed with the rest of the code!';
    (...)
}

Two things I have noticed:

You remove all non-alpha-numeric characters, apart from the dash and space characters. I don't see what this adds to your filter? Clearly all the other characters are never part of your swear words, so why bother to remove them? It could, in theory, have unpredictable consequences, because formerly separated characters might form new words. Instead of removing you could replace the characters with a space, but my suggestion is to just don't do this step at all.

strpos() is case sensitive, that would mean your function won't find "BadWord" or "BADWORD" unless you add all these variants to your array. Better use stripos() which is case-insensitive.


Bounded Queue with multiple consumers and multiple producers It was an interview question:

Should implement a class - BlockingQueue with those constraints:

2 Methods - Adding an item and Take an item from the queue.
The class should support multiple consumers and multiple producers.
The class will getting a bounded size of queue and a maximum of producers and consumers at constructor:

public BlockingQueue(int boundedCapacity, int producers, int consumers)

At method Take - if the queue is empty - should to wait till have least one item in the queue.
At the method Insert - if the queue is full - should to wait till the queue was dequeued least one item.

I've written a queue class for supporting multiple producers and multiple consumers threads.

the class is getting bounded size and number of producers and consumers.

as following:

class BlockingQueue<T>
{
    readonly ConcurrentQueue<T> _queue = new ConcurrentQueue<T>();
    readonly int _boundedCapacity;

    readonly SemaphoreSlim _semaphoreSlimProducer;
    readonly SemaphoreSlim _semaphoreSlimConsumer;

    public BlockingQueue(int boundedCapacity, int producers, int consumers)
    {
        _boundedCapacity = boundedCapacity;
        _semaphoreSlimProducer = new SemaphoreSlim(0, producers);
        _semaphoreSlimConsumer = new SemaphoreSlim(consumers);
    }

    public void Insert(T item)
    {
        if(item == null) throw new ArgumentNullException("item");
        while(Count >= _boundedCapacity)
        {
            _semaphoreSlimProducer.Wait(1000);
            _semaphoreSlimConsumer.Release();
        }

        _semaphoreSlimProducer.Wait();
        _queue.Enqueue(item);
        _semaphoreSlimConsumer.Release();
    }

    public T Take()
    {
        while(Count == 0)
        {
            _semaphoreSlimConsumer.Wait(1000);
            _semaphoreSlimProducer.Release();
        }
        _semaphoreSlimConsumer.Wait();
        T retval = default(T);

        _queue.TryDequeue(out retval);

        _semaphoreSlimProducer.Release();
        return retval;
    }

    public int Count
    {
        get
        {
            return _queue.Count;
        }
    }
}

Testing:

private static void TestBlockingQueue()
{
    BlockingQueue<string> b = new BlockingQueue<string>(3, 3, 3);

    ConcurrentBag<Task> tasks = new ConcurrentBag<Task>();
    for(int i = 0; i < 10; i++)
    {
        var t = Task.Factory.StartNew(() => {
            string item = "Threadid:Thread.CurrentThread.ManagedThreadId_" + Thread.CurrentThread.ManagedThreadId + "_Count_";
            int count = 0;
            while(true)
            {
                item += count++;
                b.Insert(item);
                Console.WriteLine("insert item: " + item);
            }
        });
        tasks.Add(t);
    }

    for(int i = 0; i < 10; i++)
    {
        var t = Task.Factory.StartNew(() => {
            while(true)
            {
                var item = b.Take();
                Console.WriteLine("taked item: " + item);
            }
        });
        tasks.Add(t);
    }

    Task.WaitAll(tasks.ToArray());
}

I will be glad for getting a code review for this implementation.

The implementation clearly has a race condition:

Let's assume Count == _boundedCapacity - 1
Now have 2 producers call Insert simultaneously
Both simultaneously check that the current size is less than the upper bound and move beyond the while loop
Both insert an item.
Now you've exceeded the bounded capacity by 1

While it might be ok to be able to exceed the upper bound by up to the maximum number of producers - 1 the same race occurs in Take. Except on the consumer side it has the nasty side-effect of potentially trying to remove an object from an empty collection. In this case default(T) gets returned which the caller might not expect since Insert doesn't accept null objects.

Based on the null check in Insert I would infer that you never expect this to be instantiated on a value type but only reference types. I don't see any reason for it but if this should really not be allowed then add the type restriction where T: class to the implementation to make it clear.

In the end the bounded capacity really doesn't mean all that much since it's randomly exceeded and one can dequeue randomly from an empty queue.

Overall you should use BlockingCollection<T> to wrap the ConcurrentQueue<T> which implements the bounding capacity correctly. Just make sure to use the Add and Take methods accepting a CancellationToken so blocked operations can get interrupted nicely when you want to shutdown the application.


Creating and storing binary arrays I recently created a library in C, which creates and stores binary arrays. My library uses the standard fixed data types and allocates no more than 8 bytes for a binary array (8 bytes = 64-bit unsigned long long number). It also sets the binary equivalent at the bit level using the setBitsAt() method to make it quite efficient.

I want to know if there is a more efficient way of creating and storing binary arrays in C.

BinaryLibrary4C

Code snippet to create/store a binary array:

uint8_t* getBinaryArray(uint64_t num)
{
    int8_t encodeBitIndex = 0,byteIndex = -1;
    int8_t encodeBits = getEncodingBits(num);

    binaryArrayLen = getBytes4mBits(encodeBits);
    binaryArrayLen = (binaryArrayLen <= 0 || binaryArrayLen > BYTE) ? 0x1 : binaryArrayLen; /*Sanity check for size > 64bits*/

    int8_t bitIndex = 0,binValue;
    uint8_t *binaryArray = (uint8_t*)malloc(binaryArrayLen); /*Dynamic Array to store binary equivalent*/

    memset(binaryArray,0x0,binaryArrayLen); /*Set 0 as initial value to Array*/

    /*Storing binary equivalent in 1-bit each of binaryArray*/
    for (encodeBitIndex = 0; encodeBitIndex < encodeBits; encodeBitIndex++,bitIndex++)
    {

        if(isNextByte(encodeBitIndex))
        {
            byteIndex += 1;
            bitIndex = 0; /*-_- reset bitIndex for every byte*/
        }

        binValue = ((num >> encodeBitIndex) & 1) ?  1 : 0;
        setBitsAt((binaryArray + byteIndex),binValue,bitIndex,encodeBits);
    }
    return binaryArray;
}

void setBitsAt(uint8_t *dest,uint64_t bits,uint8_t at,uint8_t nBits)
{
    uint64_t mask = ((~0ULL) >> (sizeof(uint64_t) * BYTE - nBits)) << at;
    *dest = (*dest & ~mask)|((bits<<at) & mask);
}

const int8_t getEncodingBits(uint64_t num)
{
    return getRoundedBits((int8_t)fabs(floor(negLog2(num) - 1) + 1));
}

long double negLog2(uint64_t num)
{
    long double negLogVal = 0.0f;
    negLogVal = (num < 0) ? (sizeof(num) * BYTE) : (log2l(1.0L) - log2l(num));
    return isNumInMaxRange(num) ?  fabs(negLogVal) + 1 : negLogVal;
}

bool isNumInMaxRange(uint64_t num)
{
    return ((num == (UINT8_MAX  + 1U) || num == (UINT16_MAX  + 1U) || num == (UINT32_MAX  + 1ULL))) ?  true : false;
}

const int8_t getRoundedBits(int8_t bits)
{
    int8_t roundedBits;
    for(roundedBits = BYTE; roundedBits <= QWORD; roundedBits+=BYTE)
    {
        if(bits >= 0 && bits <= roundedBits)
            return roundedBits;
    }
    return -1;
}

I see a number of things that may help you improve your program.

Understand const

In a number of places in the code we have function declarations like this:

const int8_t getRoundedBits(int8_t bits)

The const is ignored by the compiler in this case, so it's merely confusing to the reader.  One can't have type qualifiers (such as const) on a return type, which makes sense if one thinks about it.  It makes no sense to return an int8_t value that can't be altered.  It's like going to the market and buying an egg, and being told, "You may have this egg, but you are not allowed to alter it."

Think carefully about data types

The code currently contains this function:

long double negLog2(uint64_t num)
{
    long double negLogVal = 0.0f;
    negLogVal = (num < 0) ? (sizeof(num) * BYTE) : (log2l(1.0L) - log2l(num));
    return isNumInMaxRange(num) ?  fabs(negLogVal) + 1 : negLogVal;
}

Since num is an unsigned type, the test for num < 0 will never return true, so this, too is useless code that the compiler easily ignores, but is confusing to a human reader of the code.

Simplify your code

The code contains this peculiar function:

bool isNumInMaxRange(uint64_t num)
{
    return ((num == (UINT8_MAX  + 1U) || num == (UINT16_MAX  + 1U) || num == (UINT32_MAX  + 1ULL))) ?  true : false;
}

First, the function uses the trinary operator (?:) where it isn't needed and simply clutters the code.  Second, there are a number of parentheses that aren't needed.

Avoid global variables

By the context, it appears that the binaryArrayLen variable is global.  It's generally better to explicitly pass variables into and out of your functions rather than using the vague implicit linkage of a global variable.  Not least, the current implementation would seem to preclude the possibility of ever having more than one BinaryArray.  In this case, it seems to me that a BinaryArray should be a struct containing both the data and the length.

Avoid conversions to and from floating point

We have a function getEncodingBits() which appears to be intending to return the number of bits required to encode the given number.  It looks like this:

int8_t getEncodingBits(uint64_t num)
{
    return getRoundedBits((int8_t)fabs(floor(negLog2(num) - 1) + 1));
}

The other functions have still more floating point mathematics in them, none of which is not really needed and will slow down your program.  Here's an alternative approach that is much simpler and uses no floating point:

int8_t getEncodingBits(uint64_t num)
{
    int8_t bits = 8;
    for (num >>= 8; num; num >>= 8) {
        bits += 8;
    }
    return bits;
}

Understand the standard library

The code currently includes these lines:

uint8_t *binaryArray = (uint8_t *)malloc(binaryArrayLen);
memset(binaryArray,0x0,binaryArrayLen);

First, memory allocation can fail, so the value of binaryArray must be checked before using it.  Second, if you really need the memory cleared, simply use calloc instead.

General comments

Handling this one bit at a time in the manner that this program does is a very inefficient mechanism.  For speed, it's better to handle as much data at one time as possible.  So instead of extracting and writing one bit at a time, it would make more sense to write the data in uint64_t sized chunks where possible.  Allocating memory in small chunks is also time-consuming.  In this case, the maximum data size is apparently uint64_t, so it would make sense to me to simply use uint64_t everywhere that you're currently using a BinaryArray.  Example:

#include <stdio.h>
#include <stdint.h>

typedef uint64_t BitArray;

int printBitArray(BitArray n) {
    const int len = sizeof(BitArray) * 8;
    char string[len + 1];
    char *ptr = &string[len];
    *ptr-- = ‘\0’;
    if (n == 0) {
        *ptr-- = '0';
    } else {
        for (*ptr = '0'; n; n >>= 1) {
            *ptr-- = '0' + (n & 1);
        }
    }
    return printf("%s\n", ptr+1);
}
BitArray setBit(BitArray n, int bitnum) {
    const BitArray mask = 1 << bitnum;
    return n | mask;
}
BitArray clrBit(BitArray n, int bitnum) {
    const BitArray mask = 1 << bitnum;
    return n & ~mask;
}

int main() {
    // set to 10101101 binary
    BitArray bits = 173u;
    printBitArray(bits);
    bits = setBit(bits, 14);
    printBitArray(bits);
    bits = clrBit(bits, 14);
    printBitArray(bits);
    bits = clrBit(bits, 0);
    printBitArray(bits);
}