Possibly mixing prototype and module pattern I have either created something beautiful or something monstrous, and I'm not really sure which, and I don't know where else to turn but here. What I've done:

var MyObject = function(opts) {
    //init code, set vals, runs when 'new MyObject()' is called
}

MyObject.prototype = (function() {
    //private helper functions
    //scoping is a pain, but doable
    function myPrivateFunction() {}

    return {
        publicFunc1: function() { /* uses myPrivateFunction() */ }
        , publicFunc2: function() { /* uses myPrivateFunction() */ }
    };
})();

MyObject.prototype.publicFunc3 = function() {}
MyObject.prototype.publicFunc4 = function() {}
MyObject.prototype.publicFuncEtc = function() {}

To my surprise, this works, and takes care of a pretty significant problem of creating reusable private functions for various public functions. Of course, I have to do some scoping for the this object, but I feel it's a small price to pay for being able to use private reusable functions. I left the other functions on the outside to avoid having to deal with scoping.

My question is: is this a code smell? and as a corollary, is there a better way to do this?

The commenters pretty much said it all:

publicFunc3 can't see myPrivateFunction <- not good
I would declare function() { /* uses myPrivateFunction() */ } as a private function and then just return a pointer to it:

MyObject.prototype = (function() {
    //private helper functions
    //scoping is a pain, but doable
    function myPrivateFunction() {}
    function myPrivateFunction2() {/* uses myPrivateFunction() */ }
    function myPrivateFunction3() {/* uses myPrivateFunction() */ }

    return {
        publicFunc1: myPrivateFunction2
      , publicFunc2: myPrivateFunction3
    };
})();

I know there is a "comma first" movement out there, but it looks silly to me

Other than that, this code does not look monstrous to me, if it works for you, then why not.


Implementation of Luhn Algorithm I've implemented the well known Luhn Algorithm in Python. It's a simple one, so it's good for beginners.

import random
from math import ceil

def Luhn(digits):
    if digits >= 2:
        num = random.randrange(10**(digits-2),10**(digits-1))
        num_digits = list(str(num))

        for i in range(0,digits-1):
            num_digits[i] = int(num_digits[i])

        if digits % 2 == 0:
            range_start = 0
        else:
            range_start = 1

        for i in range(range_start,ceil((digits+range_start-1)/2)):
            if digits % 2 == 0:
                num_digits[2*i] *= 2
                if num_digits[2*i] > 9:
                    num_digits[2*i] -= 9
            else:
                num_digits[2*i-1] *= 2
                if num_digits[2*i-1] > 9:
                    num_digits[2*i-1] -= 9

        checksum = sum(num_digits)
        last_digit = checksum % 10

        if last_digit != 0:
            checknum = 10 - last_digit
        else:
            checknum = 0

        num = num*10+checknum
        return num
    else:
        return None

It's a function that takes 1 parameter (digits) and returns a valid number with a given number of digits.
The code is pretty straightforward, except for this part:

if digits % 2 == 0:
    range_start = 0
else:
    range_start = 1

for i in range(range_start,ceil((digits+range_start-1)/2)):
    if digits % 2 == 0:
        num_digits[2*i] *= 2
        if num_digits[2*i] > 9:
            num_digits[2*i] -= 9
    else:
        num_digits[2*i-1] *= 2
        if num_digits[2*i-1] > 9:
            num_digits[2*i-1] -= 9

Basically what it does is the 'multiplication by 2' part of the algorithm. This part was intentional, so don't take this in consideration. I just wanted to challenge myself.

I would like to get some feedback about the code and things that can be changed.

Some style notes:

In Python, function names are snake_case, not PascalCase.
You should always put spaces around operators, for example for i in range(0, digits - 1) instead. (That example could be tightened to for i in range(digits - 1), as ranges implicitly start from 0.)
I'm not a big fan of the variable names num or num_digits. At the very least spell out the word "number" – characters are cheap.

Some more substantial suggestions:

There should be a docstring on your function. Right now, it's not clear what it's doing, or how I should use it. (I think it creates a number which complies to the Luhn formula, but I'm guessing.) Also, there are no comments. You should make it clear why you've written this code – explain how it relates back to Luhn's algorithm.
To save yourself an indentation level, I'd turn the if statement into an early return:

def Luhn(digits):
    if digits < 2:
        return
    # do rest of function

At the start of the function, you create a large N-digit number, convert to a string, then list, and then turn each list element into an integer. You can simplify this slightly:

num = random.randrange(10 ** (digits - 2), 10 ** (digits - 1))
num_digits = [int(digit) for digit in str(num)]

Note that this implementation precludes the returned number starting with 0. I don't know if that was intentional, but if it was, you should have a comment explaining why.

(Luhn's algorithm is generally used with identification numbers, not just base-10 integers, so it's quite plausible it could encounter a number whose first digit is 0.)
You can tidy up the if statement as follows:

range_start = digits % 2

I would also create a variable range_stop, which makes the level of abstraction in the range limits more consistent:

range_start = digits % 2
range_stop = math.ceil(digits + range_start - 1) / 2)

for i in range(range_start, range_stop):
    # do some stuff

Within the for loop, you have very similar repeated code. I'd pull out the index into a separate variable, and then you can cut down on repetition.

for i in range(range_start, range_stop):
    idx = 2 * i + digits % 2
    num_digits[idx] = 2 * num_digits[idx] % 9


Greatest Common Factor I wrote this program to determine the Greatest Common Factor of any 2 given numbers, and would like to know of any improvements that can be made. I have tested it using a loop and 2 randomly generated numbers and it seems to work perfectly:

import java.util.ArrayList;
import java.util.Scanner;

public class GreatestCommonFactor
{
    public static void main(String[] args)
    {
        System.out.println("Please enter 2 numbers:");
        Scanner in = new Scanner(System.in);

        int a = Integer.parseInt(in.nextLine());
        int b = Integer.parseInt(in.nextLine());
        int greatestCommonFactor = gcf(a,b);

        System.out.println(greatestCommonFactor);
        in.close();
    }

    public static int gcf(int a, int b)
    {
        int result = 0;
        ArrayList<Integer> factorsA = factorise(a);
        ArrayList<Integer> factorsB = factorise(b);

        for (int i = 0; i < factorsA.size(); i++)
            if (factorsB.contains(factorsA.get(i)))
                result = factorsA.get(i);
        return result;
    }

    public static ArrayList<Integer> factorise(int num)
    {
        ArrayList<Integer> factors = new ArrayList<Integer>();
        int bounds = num/2;
        for (int i = 1; i <= bounds; i++)
            if (num % i == 0)
                factors.add(i);
        factors.add(num);
        return factors;
    }
}

Good job on closing your Scanner! I see a lot of people forget/miss that.

An alternative, just for your information, is using try with resources so you don't have to worry about closing/remembering to close it. As an aside, in general, you want to use more meaningful names than just 'a' and 'b' in your code (Though I'm totally going to be a hypocrite in a second, names are hard).

I would consider using Scanner's nextInt() method, you're using integers, using nextLine() isn't intuitive. As it is, despite your request for two numbers(should specify integers), if a user actually tries to input two space delimited numbers it'll throw an error.

Here's what the start of your code would look like with these suggestions:

        int first;
        int second;
        System.out.print("Please enter 2 integers: ");

        try(Scanner in = new Scanner(System.in)) {
            first = in.nextInt();
            second = in.nextInt();
        }

As for the actual logic of your code, You can use the Euclidean algorithm

// Greatest Common Denominator
public int computeGCD(int a, int b) {
    return b == 0 ? a : computeGCD(b, a % b);
}


Asks the user to input 10 integers, and then prints the largest odd number I have written a piece of python code in response to the following question and I need to know if it can be "tidied up" in any way. I am a beginner programmer and am starting a bachelor of computer science.

  Question: Write a piece of code that asks the user to input 10 integers, and then prints the largest odd number that was entered. if no odd number was entered, it should print a message to that effect.

My solution:

a = input('Enter a value: ')
b = input('Enter a value: ')
c = input('Enter a value: ')
d = input('Enter a value: ')
e = input('Enter a value: ')
f = input('Enter a value: ')
g = input('Enter a value: ')
h = input('Enter a value: ')
i = input('Enter a value: ')
j = input('Enter a value: ')

list1 = [a, b, c, d, e, f, g, h, i, j]
list2 = [] # used to sort the ODD values into
list3 = (a+b+c+d+e+f+g+h+i+j) # used this bc all 10 values could have used     value'3'
                          # and had the total value become an EVEN value

 if (list3 % 2 == 0): # does list 3 mod 2 have no remainder
    if (a % 2 == 0): # and if so then by checking if 'a' has an EVEN value     it rules out
                 # the possibility of all values having an ODD value entered
        print('All declared variables have even values')
    else:
        for odd in list1: # my FOR loop to loop through and pick out the     ODD values
            if (odd % 2 == 1):# if each value tested has a  remainder of one to mod 2
                list2.append(odd) # then append that value into list 2
        odd = str(max(list2)) # created the variable 'odd' for the highest ODD value   from list 2 so i can concatenate it with a string.
        print ('The largest ODD value is ' + odd)

Here are a couple of places you might make your code more concise:

First, lines 2-11 take a lot of space, and you repeat these values again below when you assign list1. You might instead consider trying to combine these lines into one step. A list comprehension might allow you to perform these two actions in one step:

>>> def my_solution():
    numbers = [input('Enter a value: ') for i in range(10)]

A second list comprehension might further narrow down your results by removing even values:

    odds = [y for y in numbers if y % 2 != 0]

You could then see if your list contains any values. If it does not, no odd values were in your list. Otherwise, you could find the max of the values that remain in your list, which should all be odd:

    if odds:
        return max(odds)
    else:
        return 'All declared variables have even values.'

In total, then, you might use the following as a starting point for refining your code:

>>> def my_solution():
        numbers = [input('Enter a value: ') for i in range(10)]
        odds = [y for y in numbers if y % 2 != 0]
        if odds:
            return max(odds)
        else:
            return 'All declared variables have even values.'

>>> my_solution()
Enter a value: 10
Enter a value: 101
Enter a value: 48
Enter a value: 589
Enter a value: 96
Enter a value: 74
Enter a value: 945
Enter a value: 6
Enter a value: 3
Enter a value: 96
945


Invert a dictionary to a dictionary of lists I have a dictionary whose keys are related to list of values, but any value may be related to many keys, hence be contained in various lists-attached-keys.

To highlight such relation; I build (in Python 3.6.1) the reverse dictionary using this:

   from collections import defaultdict
   #defaultdict is a dict that you set up to output a datatype as default, instead of throwing a KeyError exception, when a key not contained into it is called, it outputs the default datatype and the corresponding key is created on the fly and kept.
   reversed_dict =defaultdict(list)
   primary_dict ={"abc":[1,2,3], "cde":[3,5,7],"efg":[4,2,1,7]}
   #in the call of default dict, you must input a callable
   [reversed_dict[term].append(key) for key, innerset in primary_dict.items() for term in innerset]
   #append should be used instead of extend, as keys are strings, and extend would result in their breakdown

   #desired output for reversed_dict:
   #defaultdict(list,
   #     {1: ['abc', 'efg'],
   #      2: ['abc', 'efg'],
   #      3: ['abc', 'cde'],
   #      4: ['efg'],
   #      5: ['cde'],
   #      7: ['cde', 'efg']})

The code is very simple, and efficient.
My question is more about using the list comprehension to get the loading of the dict done, while it is not assigned to anything. Can't this cause any sort of problem? Shouldn't I better assign the comprehension and then delete it?

I am not very much used to "leaving in the air" something in Python. So I wonder if it is not "ugly", or problematic. I feel like it is bad because the comprehension is not actually doing what it is intended to, aka creating a list, I am only using its related feature of mimicking a for loop for it, because it is more efficient and readable than such loop.

What do you think?
I have been using such pattern for a long time now, but I was never  completely satisfied with it, I only kept it because the other way I found were too convoluted to do this, or not using only one step.
About the context, it is difficult to say because I very often have to use such practice. I am in bioinformatics, so I often get associations between a key (say a gene or protein) and a list (of biological effects, related drugs and so on). Sometimes I use dataframes, but actually I find groupby not very convenient, as to get the related info you have to handle indexes (granted, you can set you keys as index and drop the column, but it is many operations, plus you have an index as output and this comes with its own kind of hassle.

You are right, you should not use a list comprehension just for its side-effects. It is not very readable and only confuses the reader of the code.

Instead, just make it for loops. And put it into a function, so it is re-usable:

from collections import defaultdict

def reverse_dict_of_lists(d):
    reversed_dict = defaultdict(list)
    for key, values in d.items():
        for value in values:
            reversed_dict[value].append(key)
    return reversed_dict

if __name__ == "__main__":
    d = {"abc": [1, 2, 3], "cde": [3, 5, 7], "efg": [4, 2, 1, 7]}
    print(reverse_dict_of_lists(d))
    # defaultdict(<type 'list'>, {1: ['abc', 'efg'], 2: ['abc', 'efg'], 3: ['cde', 'abc'], 4: ['efg'], 5: ['cde'], 7: ['cde', 'efg']})

This might take a very small performance hit (it doesn't, see below), but this should be negligible compared to actually being able to understand what the code does.

Here are some timings on my machine. First I generate a list of some randomly filled dictionaries:

import random

def generate_dicts(dict_length, step=1):
    return [{i: [random.randrange(1, 100) for _ in range(j)]
             for i, j in zip(
                 [random.randrange(1, n_keys) for _ in range(n_keys)],
                 [random.randrange(1, 100) for _ in range(n_keys)])}
            for n_keys in range(2, dict_length + 2, step)]

This will generate dictionaries of the form {i: [...]}, where there are an increasing number of keys in the dictionary and also the length of the lists increases (but is random).

Plotting the time it takes to reverse the dictionary for dict_length = 100000, step = 1000:

And, with a slightly more realistic sample dict, which does not overwrite the keys and therefore shows the quadratic behavior of the double loop:

import numpy as np

def generate_dicts(n_keys_values):
    return ({i: [random.randrange(1, 100) for _ in range(random.randrange(1, n_keys))] for i in range(n_keys)} for n_keys in n_keys_values)

n_keys_values = np.logspace(1, 4.5, num=20, dtype=int)

This is on Ubuntu 17.04, Python 3.6.3, IPython 6.2.1, Intel i7-4710MQ (8) @ 3.500GHz.

You can see that the loop based approach is actually slightly faster in both cases :). The reason being, as Eric Duminil put it succinctly in the comments:

  A list comprehension might be faster than creating a list with a for loop. In [this] case, the list comprehension creates a useless list full of Nones. And this list isn't created at all with the for loop.


Performance of dynamic Fibonacci generator and dead rabbits I would like to improve my code style and its efficiency.

I'm just moving beyond the standard recursive approach to a lot of simple algorithms.

This post has two code snippets with slightly different but related problems. They're both in Python.

The first snippet is just to produce Fibonacci numbers. I think I've done this with O(n) time complexity. Do you have suggestions on how to make my code more readable and more efficient?

# Using bottom-up dynamic programming approach, define all fibonacci numbers
def fib(num):

    # First and second generations are trivial
    if num == 1 or num == 2:
        return 1

    # If not trivial, keep going:

    # Set up array
    allGenerations = [None] * (num + 1)
    allGenerations[1] = 1
    allGenerations[2] = 1

    # Fill in the array until you reach the given generation
    for i in range(3, num+1):
        allGenerations[i] = allGenerations[i - 1] + allGenerations[i - 2]
    return allGenerations[num]

The second snippet tries to use what I learned from the first snippet to solve a related problem. The numbers represent living rabbits. If rabbits lived forever, their population sizes would follow a fibonacci sequence. In this alteration, rabbits live for a fixed amount of time (input m). Newborn rabbits keep living, adult rabbits produce themselves and one offspring, and rabbits that are about to die just produce one offspring (see http://rosalind.info/problems/fibd/).

I'm not sure how to analyze the time complexity of this problem, but it seems high? So questions are (1) What is the time complexity of my solution? and (2) How can I improve efficiency and readability?

def rabbit(n, m):
    # First two generations are trivial
    if n == 1 or n == 2:
        return 1

    # If not trivial, keep going:

    # Set up array
    allGenerations = [None] * (n + 1)

    # Each index in the generations will be another array whose indicies represent the ages of the rabbits in that generation
    allGenerations[1] = [1]
    allGenerations[2] = [0, 1]

    # Bottom-up filling of generations
    for i in range(3, n + 1):
        # Initalize answer as a list of number of rabbits at each age
        answer = [None] * (i)

        # Get the previous generation
        previous = allGenerations[i - 1]

        # Initalize the number of newborns
        newborns = 0

        # From age 1 (first reproductive age) to either age at death
        # or the oldest in the previous generation (whichever comes first), produce newborn rabbits
        for j in range(1, min(m, len(previous))):
            newborns += previous[j]

        # The 0-index of the answer represents newborn rabbits
        answer[0] = newborns

        # Move every element in the previous generation up one index into the new generation
        for k in range(0, len(previous)):
            answer[k + 1] = previous[k]

        # Put this answer into the list of all answers
        allGenerations[i] = answer

    # Return all living rabbits
    return sum(answer[:m])

# Some testcases

import unittest

class mainTest(unittest.TestCase):
    def test(self):
        self.assertEqual(rabbit(1, 3), 1)
        self.assertEqual(rabbit(2, 3), 1)
        self.assertEqual(rabbit(3, 3), 2)
        self.assertEqual(rabbit(4, 3), 2)
        self.assertEqual(rabbit(5, 3), 3)
        self.assertEqual(rabbit(6, 3), 4)
        self.assertEqual(rabbit(7, 3), 5)
        self.assertEqual(rabbit(25, 31), 75025)
        self.assertEqual(rabbit(30, 30), 832040)
        self.assertEqual(rabbit(35, 29), 9227437)
        self.assertEqual(rabbit(40, 28), 102333267)
        self.assertEqual(rabbit(45, 27), 1134880302)

if __name__ == '__main__':
    unittest.main(argv=[''], exit = False)

With regard to your time complexity:

With your calculation of the nth Fibonacci number, you could do it in \$O(1)\$ time by using the relation:

$$F_n = \left\lfloor \frac{\varphi^n}{\sqrt{5}} + \frac{1}{2} \right\rfloor$$

So the 484th Fibonacci number would be equal to:

$$\left\lfloor \frac{\varphi^{484}}{\sqrt{5}} + \frac{1}{2} \right\rfloor \approx 6.317 \times 10^{100}$$

If you do not want to use the floor function, you can achieve the exact same result by manipulating the equation and using the nearest-integer function: \$\left[\frac{\varphi^n}{\sqrt5}\right]\$

This will speed up your program if you intend on calculating very large Fibonacci numbers.

Note: when calculating \$\varphi^n\$, use math.pow(x,y) because it uses floating point exponentiation and is always \$O(1)\$, whereas pow(x,y) and x**y can vary. For calculating \$\varphi\$ itself, there are many methods, here is an example.


Finding duplicated entries Since the Esteemed Academia wants me to learn Haskell, and Haskell seems just weird for me, I thought that to train some basic Haskell skills I'd write a simple script I now need in Haskell.

This is what the script is supposed to do... I have a file that looks like this:

oo R
j
j ai            I'm a comment
kd oo
stack j
a

I needed to extract duplicated elements from this file with lines they appear on. The catch is that the tab character denotes comments; so I'm a comment should not be considered here and in particular, this a from I'm a comment should not match this a that appears as the last element from these sample lines.

If fed this particular sample file, my script should report finding duplicate elements: oo on lines 1 and 4 and j on lines 2, 3 and 5. I believe I wrote a script that does this correctly.

Here it is:

import qualified Data.Map as Map
import Data.List
import Data.Function

main = do
  input <- fmap preprocess getContents
  printDupes $ findDupes input

preprocess input = let
    untabbedLines = map (takeWhile (/= '\t')) $ lines input
    wordsedLines = map words untabbedLines
    numberedLines = zip wordsedLines [1..]
    numberedWords = concat $ map indexDown numberedLines where
      indexDown (words', index) = map (flip (,) $ index) words'
  in numberedWords

findDupes entries = let
    occurences = Map.fromListWith (flip (++)) $ map (fmap (:[])) entries
  in Map.filter ((>1).length) occurences

printDupes :: Map.Map String [Int] -> IO()
printDupes dupes = let
    showPositions positions = intercalate ", " $ map show positions
    printDupe (dupe, positions) = putStrLn $ "Duplicated element " ++ dupe ++ " found on positions: " ++ showPositions positions
  in let
    sortedDupes = sortBy (compare `on` snd) $ Map.assocs dupes
  in mapM_ printDupe sortedDupes

The task is simple, but I guess it's OK for learning how to code in Haskell...

So could you kindly review this self-imposed exercise? What could've been done better than I did? Simpler? Shorter? I'm sure much, but what precisely? Also how to improve readability?

It can be helpful to run hlint to see if it spots some improvements.  In this case, it notes that:

you can replace concat $ map with concatMap on line 13
you can replace flip (,) $ index with (,index) on line 14 if you enable the TupleSections extension, or at least drop the dollar sign if you don't

A few additional things it misses are:

you can drop the in let on line 25
you can replace sortBy (compare `on` snd) with sortOn snd in line 26

It's also generally accepted as good practice to put type signatures on top-level functions.  You may feel it looks cluttered, but it really helps others understand your programs.  For example, I had to add them before I started working on your program, just so I could figure out what was going on.

A larger stylistic issue is that idiomatic Haskell code typically doesn't create a lot of bindings for intermediate results that are only used once.  I suspect that you've gone this route (labelling untabbedLines and wordsedLines, etc.) for two reasons -- first, you're probably more used to an imperative programming style that lays out an algorithm as a series ordered steps, and all these bindings are helping you think through the process ("first, I remove the tabbed comments, second I make the lines into words, third I number them, etc., etc.); second, you may be using it as a kind of self-documenting coding style, but I think comments make better documentation than awkward camelcase pseudonouns like wordsedLines.

So, a more usual way of writing your preprocess would be:

preprocess input
  = concatMap indexDown
  $ flip zip [1..]
  $ map words
  $ map (takeWhile (/= '\t'))  -- comments start with tab
  $ lines input
  where
    -- number each word on the line with the index
    indexDown (words', index) = map (,index) words'

Howoever, it's also pretty standard replace the pattern foo x = f $ g $ h $ k x with the point-free form foo = f . g . h . k.  It's possible to get carried away with point-free code, but this particular transformation is pretty routine.  Some people might prefer to collapse the map over the lines, too:

preprocess
  = concatMap indexDown
  . flip zip [1..]
  . map (words . takeWhile (/= '\t'))
  . lines
  where
    -- number each word on the line with the index
    indexDown (words', index) = map (,index) words'

Also, in situations like this with maps at multiple levels (lines and words), it's worth considering if a list comprehension might not be easier to understand:

preprocess' :: String -> [(String, Int)]
preprocess' input =
  [ (w, i)
  -- get each numbered line of words
  | (i, ws) <- zip [1..]
               $ map (words . takeWhile (/= '\t'))
               $ lines input
  -- and process each word
  , w <- ws ]

A similar consideration applies to findDupes.  It would be more usual to collapse it into a single functional pipeline in point-free form:

findDupes :: [(String, Int)] -> Map.Map String [Int]
findDupes = Map.filter ((>1) . length)
          . Map.fromListWith (flip (++))
          . map (fmap (:[]))

However, I think map (fmap (:[])) is probably too clever by half.  At the very least, it would be clearer to import second from Data.Bifunctor and write map (second (:[])), though even better would be to just use a lambda which makes the intended transformation clear at a glance:

map (\(w,i) -> (w,[i]))

A rewrite of printDupes would probably look like:

printDupes :: Map.Map String [Int] -> IO ()
printDupes dupes =
  forM_ (sortOn snd $ Map.assocs dupes) $ \(w, idxs) ->
    putStrLn $ "Duplicated element " ++ w ++
               " found on positions: " ++
               (intercalate ", " $ map show idxs)

(Here, forM_ comes from Control.Monad and is just a flipped version of mapM_.)

One additional stylistic issue regards your handling of IO.  Here, the main function is responsible for actually performing input and then calls on a pure function to perform the processing.  When it comes time to generate output, though, it passes off that responsibility to another function.  Haskell programs are usually carefully organized around their IO, with a clear division of responsibility between the IO and the pure processing, and it's usual to have input and output all handled at the same "level".  I realize that sounds a little fuzzy and hand-wavy, but it boils down to this -- it would be more usual to localize input and output in main and have the remainder of the program (including printDupes) be pure.  So, printDupes would instead look something like:

printDupes :: Map.Map String [Int] -> String
printDupes =
  unlines . map render . sortOn snd . Map.assocs
  where render (w,idxs)
          = "Duplicated element " ++ w ++
            " found on positions: " ++
            intercalate ", " (map show idxs)

I also personally find it a little odd that findDups takes a list [(String,Int)] but then returns a Map String [Int].  The Map seems like an implementation detail, and it "feels" like the function ought to return a [(String,[Int])], and it might as well sort this list while it's at it.

Anyway, with all those changes and some renaming of functions, the final program might look like:

{-# OPTIONS_GHC -Wall #-}

import qualified Data.Map as Map
import Data.List

main :: IO ()
main = interact (renderDups . findDups . getWords)

getWords :: String -> [(String, Int)]
getWords input =
  [ (w, i)
  | (i, ws) <- zip [1..]
               $ map (words . takeWhile (/= '\t'))
               $ lines input
  , w <- ws ]

findDups :: [(String, Int)] -> [(String, [Int])]
findDups = sortOn snd . Map.assocs
         . Map.filter ((>1) . length)
         . Map.fromListWith (flip (++))
         . map (\(w,i) -> (w,[i]))

renderDups :: [(String, [Int])] -> String
renderDups = unlines . map render
  where render (w,idxs)
          = "Duplicated element " ++ w ++
            " found on positions: " ++
            intercalate ", " (map show idxs)


Calculating the interest on a series of loans I am a college student and started my first week of C++ and we were given an assignment to convert a Java program that calculate the interest on a series of loans given the amount of the principal, the annual interest rate, and the number of days in a sentinel loop into C++.

Here is what we were given:

import java.util.Scanner;
public class ex311
{
public static void main(String[] args)
{
    double principle, rate, interest;
    int days;
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter principle (-1 to end):  ");
    principle = sc.nextDouble();
    while (principle != -1)
    {
        System.out.print("Enter annual interest rate (as a decimal):  ");
        rate = sc.nextDouble();
        System.out.print("Enter number of days:  ");
        days = sc.nextInt();
        interest = principle * rate / 365 * days;
        System.out.printf("Interest is %.2f\n", interest);
        System.out.print("\nEnter principle (-1 to end):  ");
        principle = sc.nextDouble();
    }
}
}

This is what I have for the C++ converted code:

#include <iostream>

using namespace std;
void main()
{
    double principle, rate, interest;
int days;
cout << "Enter principle (-1 to end)";
cin >> principle;
while (principle != -1)
{
    cout << "Enter annual interest rate(as a decimal)";
    cin >> rate;

    cout << "Enter number of days";
    cin >> days;

    interest = principle * rate / 365 * days;
    cout << "Interest is "<< interest;
    cout << "Enter principle (-1 to end)";
    cin >> principle;
}
}

I would like to know if there is a better way to go about this, as in making my code more efficient. I am aware that I should not be using void main, but this is how we're being taught for the time being.

Do not represent monetary amounts as a decimal type; use an integer type instead.
Try to avoid the use of using namespace std.
You could still allow the user to enter an interest rate and have the program convert it to a decimal, especially if the user doesn't know how to do this.
You could just have days, rate, and interest declared or initialized within the loop.  It's usually best to have variables kept in as close scope as possible.

Moreover, if you're going to "list" variables, have each one on a separate line.  This is easier to read and avoids the possibility of needing to scroll horizontally.


Random name-picker with array I created a program that picks a champion for a role on the game League of Legends using arrays and random numbers.

Is there a quicker and more efficient way of doing this?

There is one form that contains this:

namespace Random_Champ_Picker_V2
{
public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    internal void button1_Click( object sender, EventArgs e )
    {

        arrays array = new arrays();
        if( radioButton1.Checked == true )
        {
            Random T = new Random();
            int t = T.Next( 0, 57 );
            string toop = (string) array.top.GetValue( t );
            textBox1.Text = toop;
        }
        else if( radioButton2.Checked == true )
        {
            Random T = new Random();
            int t = T.Next( 0, 38 );
            string toop = (string) array.jung.GetValue( t );
            textBox1.Text = toop;
        }
        else if( radioButton3.Checked == true )
        {
            Random T = new Random();
            int t = T.Next( 0, 41 );
            string toop = (string) array.mid.GetValue( t );
            textBox1.Text = toop;
        }
        else if( radioButton4.Checked == true )
        {
            Random T = new Random();
            int t = T.Next( 0, 15 );
            string toop = (string) array.marksmen.GetValue( t );
            textBox1.Text = toop;
        }
        else if( radioButton5.Checked == true )
        {
            Random T = new Random();
            int t = T.Next( 0, 18 );
            string toop = (string) array.supp.GetValue( t );
            textBox1.Text = toop;
        }

    }

Class that contains the arrays (I removed most champ names for this post not to be cluttered):

namespace Random_Champ_Picker_V2
{
internal class arrays
{
    internal string[] supp = new string[]    {"Taric","Thresh"};

    internal string[] marksmen = new string[]{"Ezreal","Ashe"};

    internal string[] top = new string[]{"Zac","Aatrox"};

    internal string[] jung = new string[]{"Amumu","Jarvan IV"};

    internal string[] mid = new string[]{"karma","ziggs"};
}
}

First of all, you do not need to create an instance of Random class every time.

Then, you may use the ternary operator (the ?: operator) to select the array from which you want to take the element.

And, assuming that you have to take a random element form the array, you may use just a[T.Next(a.Length).

Random T = new Random();
. . .
string[] a = radioButton1.Checked? array.top:
             radioButton2.Checked? array.jung:
             radioButton3.Checked? array.mid:
             radioButton4.Checked? array.marksmen:
             radioButton5.Checked? array.supp:
             null;
if (a != null)
    textBox1.Text = a[T.Next(a.Length)];


Find if an array is arithmetic or geometric This seems to be working fine. I am pretty sure there is a better way to do it. How can my code be improved performance-wise? The main thing bothering me is the nested for-loop.

function arithGeo (arr) {
    var isGeometric = false;
    var isArithmetic = false;
    var diff = arr[2] - arr[1];
    var ratio = arr[2] / arr[1];
    for (var i = 0; i < arr.length - 1; i++) {
        var j = i + 1;
        if (diff !== arr[j] - arr[i]) {
            for (var k = 0; k < arr.length - 1; k++) {
                var l = k + 1;
                if (ratio !== arr[l] / arr[k]) {
                    break;
                } else if (l === arr.length-1) {
                    isGeometric = true;
                    break;
                }
            }
        } else if (j === arr.length - 1) {
            isArithmetic = true;
        }
    }

    if (isGeometric === true) {
        return "geometric";
    } else if (isArithmetic === true) {
        return "arithmetic";
    }
    else {
        return -1;
    }
}

console.log(arithGeo([2,4,6,8]));
console.log(arithGeo([2,6,18,54]));
console.log(arithGeo([2,6,1,54]));

I agree with @janos that sometimes returning a string and sometimes returning -1 makes this function hard to use.  In addition, it's unclear what your function is supposed to return for input that is both an arithmetic and a geometric sequence (every element is the same).

I find it odd that you base the difference and ratio on elements at indexes 1 and 2 rather than 0 and 1.  Such an arbitrary choice seems like an unnecessary failure mode for short input arrays.

Note that if the ratio is 0 or infinite, you can immediately declare the sequence to be not geometric.

A better approach is to assume that a sequence is arithmetic or geometric until proven otherwise.

function arithGeo(arr) {
    var diff = arr[1] - arr[0];
    var ratio = arr[1] / arr[0];
    var isArithmetic = true, isGeometric = isFinite(ratio) && ratio != 0;

    for (var i = 1, j = 2; (isArithmetic || isGeometric) && j < arr.length; i++, j++) {
        if (isArithmetic && arr[j] - arr[i] != diff) {
            isArithmetic = false;
        }
        if (isGeometric && arr[j] / arr[i] != ratio) {
            isGeometric = false;
        }
    }
    return isArithmetic && isGeometric ? 'both' :
           isArithmetic                ? 'arithmetic' :
                           isGeometric ? 'geometric'  : '';
}

For clarity, you might as well write it as two independent loops, because the classification problems are independent of each other.  There would be more lines of code, but the complexity of the algorithm remains the same.  Except in degenerate cases, only one of the loops is going to see much action anyway.

function arithGeo(arr) {
    var i, j;

    var diff = arr[1] - arr[0];
    var isArithmetic = true;
    for (i = 1, j = 2; isArithmetic && j < arr.length; i++, j++) {
        if (isArithmetic && arr[j] - arr[i] != diff) {
            isArithmetic = false;
        }
    }

    var ratio = arr[1] / arr[0];
    var isGeometric = isFinite(ratio) && ratio != 0;
    for (i = 1, j = 2; isGeometric && j < arr.length; i++, j++) {
        if (isGeometric && arr[j] / arr[i] != ratio) {
            isGeometric = false;
        }
    }

    return isArithmetic && isGeometric ? 'both' :
           isArithmetic                ? 'arithmetic' :
                           isGeometric ? 'geometric'  : '';
}


Can this custom Test:Unit assert be replaced/refactored? Am I missing test cases? I have a unit test that needs to compare two arrays but it shouldn't care about the order of the arrays. I didn't see anything in the Test:Unit docs that provided this so I wrote my own. I really don't want to use this code if I don't have to (want to avoid Not Invented Here syndrome).

If you can give me some feedback on the following points it would be a huge help, thanks!

Should I even use this? Is there a built-in Test:Unit assertion I can use?
I've refactored this as much as I can but any further improvements are encouraged and welcome.
I've included my tests for this custom assertion, can you see any cases that I may be missing?

Here is the custom assertion:

def assert_have_same_items(expected, actual, message = nil)
  full_message = build_message(message, "<?> was expected to contain the same collection of items as \n<?> but did not.\n", actual, expected)

  test = expected | actual

  assert_equal expected.size, actual.size, full_message
  assert_equal expected.size, test.size, full_message
end

And the tests:

test "assert_have_same_items with two arrays with same items in same order reports success" do
  assert_have_same_items [1,2,3], [1,2,3]
end

test "assert_have_same_items with two arrays with same items in different order reports success" do
  assert_have_same_items [1,2,3], [2,1,3]
end

test "assert_have_same_items with actual missing an item, reports failure" do
  assert_should_fail do
    assert_have_same_items [1,2,3], [2,1]
  end
end

test "assert_have_same_items with actual having more items, reports failure" do
  assert_should_fail do
    assert_have_same_items [1,2,3], [2,1,3,4,5,6]
  end
end

test "assert_have_same_items with actual having duplicates, reports failure" do
  assert_should_fail do
    assert_have_same_items [1,2,3], [2,1,3,2,1,3]
  end
end

test "assert_have_same_items with actual having duplicates and expected having same number of items, reports failure" do
  assert_should_fail do
    assert_have_same_items [1,2,3,4,5,6], [2,1,3,2,1,3]
  end
end

protected
def assert_should_fail
  begin
    yield if block_given?
    flunk "Expected failure but assertion reported success"
  rescue Test::Unit::AssertionFailedError
    assert true
  end
end

You have adequate test coverage for integers, and probably this will extend to floating points as well (although you really should test those as well, IMO). However you should also test for objects. Also, try a couple combinations of objects, numbers, and strings to be really sure that your assertion is correct.

If you only need to test for integer arrays, you should make it clear that the assert only works for them and its behavior with other arrays is undefined. In that case maybe you should change the name to assert_same_items_integer or something similar for clarity.


Better filereading and print formating in R I am a beginner using R and I am trying to solve some simple statistics problems and print the output. The following code takes in two datasets, computes the mean, variance and standard deviation. Finally it computes a 95-confidence interval for the standard deviation.

This is just a sample and my real data consists of a couple of thousand values, the files below are just for illustration.

Currently I read in my data files as follows

list(as.numeric(unlist(read.table(filename)))

however, I strongly feel there must be a better method? My datafiles
usually consists of rows of data (anywhere from 3 to 10 columns) and about a 1000 rows.

Secondly I find myself doing the following a lot

cat(paste(c("Confidence Intervall for the standard variation: (",
            f(CI.sigma.low[1]),", ",#
            f(CI.sigma.high[1]),")\n"), collapse = ""))

I tried to create a function that does this, however, I ran into problems when dealing with
multiple values.

I am not looking for feedback on the mathematics. Only syntax, and tips on how to
improve the overall structure of the code

Code

data_01.txt

34.10
34.21
33.34
35.45
31.56
34.67
36.72
33.16
34.35
34.50

data_02.txt

38.82518 37.61011 39.70940 41.19950 37.91823 39.06883 41.86497 38.87179
39.72824 39.46657 36.42833 39.73950 38.15764 38.49400 37.96093 38.31201
41.23278 37.50835 39.25816 39.72357 37.11235 38.84875 37.88969 38.86277

Main.R

EXERCISE <- 1 # Global variable,

# Shorthand for printing without " or numbers
p <- function(text,value) {
  cat(paste(c(text,value,"\n"), collapse = ""))
}

# Rounds number to X decimal places
f <- function(num, decimals=3) {
  round(num*10^decimals)/10^decimals
}

# Fancy title for the problems
problem <- function(index=EXERCISE) {
  w <- strrep("=",80); w.small <- strrep(" ",35)

  cat("\n\n"); cat(w,"\n")
  p(c(w.small,"Problem 3",letters[index],w.small),"")
  cat(w,"\n\n")
  #double << increments out of current scope
  EXERCISE <<- EXERCISE + 1
}

problem() # Problem 3a

# A list makes it easy to change or add files
filenames = c("data_01.txt",
              "data_02.txt")
kvm <- list()
for (i in 1:length(filenames)) {
  kvm[i] = list(as.numeric(unlist(read.table(filenames[i]))))
}

# Applies the function "length" to each element of "kvm" u.z.w
N <- sapply(kvm, length, simplify = TRUE)
mu <- sapply(kvm, mean, simplify = TRUE)
sigma <- sapply(kvm, sd, simplify = TRUE)

p("Number of values: ",N[1])
p("  Expected value: ",f(mu[1]))
p("        Variance:  ",f(sigma[1]^2))

problem() # Problem 3b

I <- 0.95 # 95-confidence intervall
alpha <- 1 - I

# qchisq is the Chi-squared Distribution
# df= degrees of freedom (frihetsgrader)
# CI = confidence interval
CI.sigma.low = (N-1) * sigma^2 / qchisq(1-alpha/2, df=N-1)
CI.sigma.high = (N-1) * sigma^2 / qchisq(alpha/2, df=N-1)

cat(paste(c("Confidence Intervall for the standard variation: (",
            f(CI.sigma.low[1]),", ",#
            f(CI.sigma.high[1]),")\n"), collapse = ""))

problem() # Problem 3e (T-interval)

I <- 0.95; alpha <- 1 - I

d.f <- sum(N) - length(N)
sigma.p <- sqrt(sum(sigma^2*(N-1))/d.f)

p("Pooled variance: ",f(sigma.p^2))
p("Pooled standard deviation: ",f(sigma.p))

v.p <- qt(1-alpha/2, d.f) * sigma.p * sqrt(sum(1/N))

CI.diff.mu.low <- (mu[1] - mu[2])-v.p
CI.diff.mu.high <- (mu[1] - mu[2])+v.p

p1 <- "Confidence Intervall for difference "
p2 <- "between mean values (mu_1-mu_2):"

cat(paste(c("\n",p1,p2,"\n","  (",
            f(CI.diff.mu.low),", ",#
            f(CI.diff.mu.high),")\n"), collapse = ""))

This should not be a complete review, but the base R function round has an optional second argument digits. It works like this

> round(1.234567, digits=1)
[1] 1.2
> round(1.234567, digits=2)
[1] 1.23

Therefore there is no need for your function f.


T-SQL Hmac (Rfc2104 SHA2_256) Implementation I'm trying to implement an Hmac in T-SQL using this question as an guide. Please critique this:

create function dbo.Hmac (
    @key varbinary(8000)
  , @message varbinary(7936)
)
returns table
with schemabinding as
return (
    select HashBytes('SHA2_256', Pads.o + HashBytes('SHA2_256', Pads.i + @message)) as [Hash]
    from (values(
        Cast( -- keys longer than blocksize are shortened and keys shorter than blocksize are zero-padded
            case
                when DataLength(@key) > 64 then HashBytes('SHA2_256', @key)
                else @key
            end
        as binary(64))
      , Cast(0x3636363636363636 as bigint) -- Rfc2104 inner padding constant
      , Cast(0x5C5C5C5C5C5C5C5C as bigint) -- Rfc2104 outer padding constant
    )) as Vars ([key], innerPadding, outerPadding)
    cross apply (values(
      -- unrolled loop to XOR key and iPad
        Cast((Substring(Vars.[key], 1, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 9, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 17, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 25, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 33, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 41, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 49, 8) ^ Vars.innerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 57, 8) ^ Vars.innerPadding) as binary(8))
      -- unrolled loop to XOR key and oPad
      , Cast((Substring(Vars.[key], 1, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 9, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 17, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 25, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 33, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 41, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 49, 8) ^ Vars.outerPadding) as binary(8))
      + Cast((Substring(Vars.[key], 57, 8) ^ Vars.outerPadding) as binary(8))
    )) as Pads (i, o)
);

Looks OK to me, without knowing Transact SQL anyway. Some things to consider:

obviously this implements just HMAC-SHA256, so the function should be named that way;
the key parameters is 8000 varbinary max value. That seems largish to me (although it might not matter much as the size is variable anyway);
there is no way to perform a hash over multiple fields in the DB which might be a use case (no incremental update possibility);
similarly, often it is required to reuse the key for multiple calculations, in that case you can cache the Pads.i and Pads.o values.

I'm also missing some constants being introduced but that might be due to the nature of TSQL.

Don't forget to test against NIST test vectors, just to be sure.


Quicksort in JavaScript assuming an immutable array Update: further succinct versions below (inspired by Haskell)

Quick sort in JS assuming an immutable array:

    const reorder = (arr, pivot) => {
      let larger = []
      let smaller = []
      let equals = []
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] < arr[pivot]) {
          smaller.push(arr[i])
        } else if (arr[i] > arr[pivot]) {
          larger.push(arr[i])
        } else {
          equals.push(arr[i])
        }
      }
      return {
        smaller: smaller,
        equals: equals,
        larger: larger
      }
    }

    const sort = (arr) => {
      if (arr.length <= 1) {
        return arr
      }
      const pivot = Math.floor(arr.length / 2)
      const result = reorder(arr, pivot)
      return [...sort(result.smaller), ...result.equals, ...sort(result.larger)]
    }

    console.log(sort([3, 1, 1, 1, 2]))

PS: I deleted the question posted earlier, thinking the algo was wrong, but then I realized a small tweak corrected it. The present code is based on comments received on earlier question.

Update:
Inspired by Haskell, here is a more succinct version using ES6:

const qsort = (arr) => {
  if(arr.length == 0) {
    return []
  }
  let [x,...xs] = arr
  let smaller = xs.filter(v => v <=x)
  let larger = xs.filter(v => v > x)
  return [...qsort(smaller),x,...qsort(larger)]
}

OR simplified further:

const qsort = ([x,...xs]) => {
  return x == undefined ? [] :
  [...qsort(xs.filter(v => v <=x)),x,...qsort(xs.filter(v => v > x))]
}

qsort([3,3,8,1,23,4,5,6,9,9,1,0,45,5,10])

Your code looks quite good. It is easy to read and understand.

I don't know how efficient it is, though. The reorder function creates lots of objects (3 arrays, and a return object). I think there are more efficient ways to implement this. Since you got the algorithmic complexity correct, I would not worry about these performance issues too much. If the code is fast enough, it's good enough. And it's readable, which is often more important.

Instead of let larger = [], you can write const larger = [] since the variable larger is only ever assigned once. Sure, you later modify the contents of the array, but the variable still points to the same array as before.

Instead of the for (let i = 0 loop, you can use the simpler for (const elem of arr) loop, which will free your code from the many [i] brackets.

There are some more unnecessary brackets in that function, in the expression arr[pivot]. This expression is evaluated more often than necessary. I would change the pivot element to be the value itself instead of the array index.

The sort function returns the original array in some cases, and a new array in the other cases. That is inconsistent. The caller of the sort function might assume that they may modify the array afterwards, and depending on the array size, this may or may not affect the original array, which you defined as immutable. Therefore you should return a copy of the array in every case.

You should write lots of automated tests. Having just a single example is not enough to cover all cases. I have written a few test cases for you, feel free to add more.

After applying all these suggestions, the code looks like this:

const reorder = (arr, pivot) => {
    const larger = []
    const smaller = []
    const equals = []
    for (let elem of arr) {
        if (elem < pivot) {
            smaller.push(elem)
        } else if (elem > pivot) {
            larger.push(elem)
        } else {
            equals.push(elem)
        }
    }
    return {
        smaller: smaller,
        equals: equals,
        larger: larger
    }
}

const sort = (arr) => {
    if (arr.length <= 1) {
        return arr.slice()
    }
    const pivotIndex = Math.floor(arr.length / 2)
    const result = reorder(arr, arr[pivotIndex])
    return [...sort(result.smaller), ...result.equals, ...sort(result.larger)]
}

const testcase = (unsorted, expected) => {
    const actual = sort(unsorted)
    const actualStr = actual.join(', ')
    const expectedStr = expected.join(', ')
    if (actualStr !== expectedStr) {
        console.log('error:', 'input:', unsorted, 'expected:', expected, 'actual:', actual)
    }

    if (actual.length !== 0) {
        const beforeModification = unsorted.join(', ')
        actual[0] += 1
        const afterModification = unsorted.join(', ')
        if (beforeModification !== afterModification) {
            console.log('error:', 'unsorted:', unsorted, 'before:', beforeModification, 'after:', afterModification)
        }
    }
}

testcase([], [])
testcase([1], [1])
testcase([3, 1, 1, 1, 2], [1, 1, 1, 2, 3])
testcase([0, 5, 4, 8, 9, 3, 7, 1, 2, 6], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])


Find property and value pairs between two objects I have a function that looks through an array of objects and returns an array of all objects that have matching property and value pairs. This works fine but I always get the notification: "Don't make functions within a loop".

So is this a bad approach to use a function within a loop?

function where(collection, source) {
  var arr = [];
  var keys = Object.keys(source);
  // What's in a name?
  for(var i = 0; i < collection.length; i++){
     if(keys.every(function(x){return x in collection[i] && source[x] == collection[i][x];})){
       arr.push(collection[i]);
     }
  }

  return arr;
}

where([{ first: "Romeo", last: "Montague" }, { first: "Mercutio", last: null }, { first: "Tybalt", last: "Capulet" }], { last: "Capulet" });

As @Pimgd explained, it's not good to recreate an anonymous function in every iteration of a loop. Move the function outside of the loop:

function where(collection, source) {
  var arr = [];
  var keys = Object.keys(source);

  function match(x) {
    return x in collection[i] && source[x] == collection[i][x];
  }

  for (var i = 0; i < collection.length; i++) {
     if (keys.every(match)) {
       arr.push(collection[i]);
     }
  }

  return arr;
}

I suggest to go one step further.
Instead of creating an array and appending to it,
you can benefit from the Array.prototype.filter method:

function where(collection, search) {
  function filter(item) {
    function matchSearchValue(key) {
      return key in item && search[key] == item[key];
    }
    return Object.keys(search).every(matchSearchValue);
  }
  return collection.filter(filter);
}

Finally, notice how I renamed everything to better explain their purpose.


Find good numbers in a given range This is the Good Numbers problem at Code Chef:

  A number is called a square-free number if there does not exist a number greater than 1, whose square divides the number. For example, 8 is not a square-free number as 4 (the square of 2) divides 8. Similarly, 4 is not a square-free number. However, 1, 3, and 6 are all square-free numbers.

  A number \$n\$ is called a good number if the following properties hold:

  It is a square-free number.
  Let \$s\$ denote the sum of all divisors of \$n\$ (including the trivial divisors 1 and \$n\$). Let \$c\$ denote the number of prime numbers dividing \$s\$. Number \$c\$ should be a prime number.

  You are given two numbers \$L\$ and \$R\$, and you have to find the sum of divisors (including the trivial divisors) of all the good numbers in the range \$L\$ to \$R\$ inclusive.

  Input

  The first line of the input contains an integer \$T\$ denoting the number of test cases. The description of \$T\$ test cases follows.

  The only line of each test case contains two space separated integers \$L\$ and \$R\$ denoting the range for which you have to find sum of divisors of good numbers.

  Output

  For each test case, output a single line corresponding to answer of the test case.

  Example

  Input:

2
1 5
6 10

  Output:

6
30

  Explanation

  These numbers in the range 1 to 10 are square-free numbers: 1, 2, 3, 5, 6, 7, 10.
  The sum of their divisors is 1, 3, 4, 6, 12, 8, 18 respectively.
  The number of prime divisors of their sum of divisors is 0, 1, 1, 2, 2, 1, 2 respectively.
  So, the numbers 5, 6, and 10 are good numbers.

  Example case 1. The only good number in the range 1 to 5 is 5. The sum of divisors of 5 is 6.

  Example case 2. In the range 6 to 10, the numbers 6 and 10 are good. The sum of their divisors is 12 + 18 = 30.

How can I improve my code? It is taking too much time to execute (5–20 seconds). Where the time limit is 1 second.

My code:

finds square free integers,
gets the sum of the unique divisors of the number,
Finds the amount of prime divisors for (2).

import time
start_time = time.time()
n=int(input())

for t in range(n):
 v=[]
 a,b=[int (x) for x in input().strip().split(' ')]
 for u in range(a,b+1):
        if u==1:
            v.append(u)
        elif u>1:
            for k in range(2,u):               # to find the square free no's
                if(u%(k**2)==0 and u>=(k**2)):

                    break;
            else:

                    v.append(u)
 sd=[]
 pd=[]
 for j in v:
    s=0

    for k in range(1,j+1):
        if j%k==0:
            s=s+k   #gives the no. of divisor for each square free no
    sd.append(s)

 for k in sd:  #This part is for finding the no of prime divisors for each square free no.
  count=[]
  for x in range (1,k):
   for u in range(2,x):
      if x%u==0 :
          break
   else :

       if (x!=1 and k%x==0):
         count.append(x)

  pd.append(len(count))  #counts the no of prime divisor

 pos=0
 su=0
 for j in pd:

    if j<=1:
      pos=pos+1
    else:

      su=su+sd[pos]
      pos=pos+1
 print(su)      #prints the sum of divisor of good numbers
print("---%s seconds ---" % (time.time() - start_time))

for k in sd:
    count = []
    for x in range(1, k):
        for u in range(2, x):
            if x % u == 0:
                break
        else:
            if x != 1 and k % x == 0:
                count.append(x)
    pd.append(len(count))

This part of the code is very slow. You are finding prime numers u through trial division, which is a very naïve method.

Basically, any code that involves prime numbers is going to be extremely slow if you don’t use a “smart” algorithm. Sieves are a good place to look. If I replace your code with

from sympy.ntheory.factor_ import primefactors
for k in sd:
    pd.append(len(primefactors(k)))

it is fifty times faster for the test input

1
1 500

(0.02 sec instead of roughly a second).

A final note: profiling is a very useful technique for finding out which steps of your code take a long time. Your code is impossible to profile if you don’t split it up into smaller functions, so please do that.


Get initials from full name Going through a book, I encountered the following assignment:

  Write an application that asks for the user’s first, middle, and last names and
  replies with the user’s initials.

Are there any flaws you notice immediately? Is there any way this code can be improved? I'm not really interested in coding style (I guess someone is going to say that I should put those braces on the next line, but I like it this way).

import javax.swing.JOptionPane;

public class Program
{

private static String fullName;
private static String firstName;
private static String middleName;
private static String lastName;

private static char firstInitial;
private static char middleInitial;
private static char lastInitial;

public static void main(String[] args)
{
    start();
}

public static void start()
{
    greet();
    askInput();
    seperateFullName(fullName);
    getInitials(firstName, middleName, lastName);
    showResult();
}

// @formatter:off
private static void greet()
{
    int dialogResult = JOptionPane.showConfirmDialog(null,  "This program asks you for you first, middle and last name"
                            + " and gives back your initials.\nDo you want to continue?");

    if (dialogResult == JOptionPane.NO_OPTION)
    {
        JOptionPane.showMessageDialog(null, "Shutting down...", null, JOptionPane.WARNING_MESSAGE);
        System.exit(0);
    }

}

private static void askInput()
{
    fullName = JOptionPane.showInputDialog("Please enter your first, middle and last name.");
}

private static void seperateFullName(String fullName)
{
    try
    {
        int firstSpace = fullName.indexOf(" ");
        firstName = fullName.substring(0, firstSpace);
        int lastSpace = fullName.lastIndexOf(" ");
        middleName = fullName.substring(firstSpace + 1 , lastSpace);
        lastName = fullName.substring(lastSpace + 1, fullName.length());
    }
    catch (StringIndexOutOfBoundsException e)
    {
        JOptionPane.showMessageDialog(null, "Invalid input!", null,
                JOptionPane.WARNING_MESSAGE, null);
        start();
    }
}

private static void getInitials(String firstName, String middleName, String lastName)
{
    firstInitial = firstName.charAt(0);
    middleInitial = middleName.charAt(0);
    lastInitial = lastName.charAt(0);
}
// @formatter:on

private static void showResult()
{
    JOptionPane.showMessageDialog(null, "Your initials are: "
            + firstInitial + "." + middleInitial + "." + lastInitial + ".");
}
}

Other than the style (yeah, you mentioned it) I think that you can:

First a small change: replace this

    int firstSpace = fullName.indexOf(" ");
    firstName = fullName.substring(0, firstSpace);
    int lastSpace = fullName.lastIndexOf(" ");
    middleName = fullName.substring(firstSpace + 1 , lastSpace);
    lastName = fullName.substring(lastSpace + 1, fullName.length());

with this:

String[] parts = fullName.split(" ");

But the main change I would suggest is a design one: remove the need for instance variables, by making each function return the input for the next.

public static void start()
{
    greet();
    String fullName = askInput();
    String[] nameParts = seperateFullName(fullName);
    String[] initials = getInitials(nameParts);
    showResult(initials);
}

(and of course modifying each function to return the value they compute)

Why?

It decouples each different part of the program, keeping them independent, specific, and therefore less prone to errors introduced somewhere else in the code.
It helps also with testing, as you can easily test each function separately.
It also helps with reusability as you could re-use each different part in other places.

Other than that, check the spelling in functions' names (For example: in seperateFullName separate is misspelt)


Simple todo list VanillaJS - repository pattern I'm new in JavaScript, so I was looking for some reviews and advice for better code quality.

import Todo from './Todo.js';

export default class Repository {
  constructor(todos = []) {
    this.todos = todos;
    this.storage = localStorage;
  }

  addTodo(todo, save=true) {
    this.todos = [...this.todos.filter(item => item.uuid !== todo.uuid), todo];
    if (save) {
      this.saveTodos();
    }
  }

  removeTodo(todo) {
    this.todos = [...this.todos.filter(item => item.uuid !== todo.uuid)];
    this.saveTodos();
  }

  saveTodos() {
    this.storage.setItem('todos', JSON.stringify(this.todos));
  }

  loadTodos() {
    const storageTodos = JSON.parse(this.storage.getItem('todos'));
    if (storageTodos !== null) {
      storageTodos.map(todo => this.addTodo(Object.assign(new Todo(), todo)), false);
    }

    return this.todos;
  }
}

https://github.com/adbo/todo_list

General points

There is no need to add localStorage to the Repository object as it is part of the global this.
You can access localStorage values directly by the key name [.1].  Eg setting localStorage.myData = "Hi World", getting const message = localStorage.myData, to check if it exists localStorage.myData !== undefined, to empty a value localStorage.myData = undefined, and to delete delete localStorage.myData
LocalStorage should not be trusted. Calling JSON.parse on data from local storage should always be wrapped in a try catch in case the data has been modified by a 3rd party.
Using filter to remove items from an array is not as efficient as locating the item's index and splicing it. Even better would be to store the todo array as a Map indexed by uuid see second example.
You have some poor naming due to the repeated prefixing of todo to all the functions. I can imagine that the Repository is called todoList and thus is would be todoList.addTodo  todoList.removeTodo and so on.  Would be far more readable if you drop the todo . Eg todoList.add,  todoList.remove, ...
You are repeating code. Both add and remove functions filter (remove) a todo. I would be better for add to call remove

Good OO design

Javascripts class syntax is something you should avoid as it forces you to create objects with poor encapsulation (if you don't use the "abomination" that is # private  prefix) Javascript has several very robust object patterns that provide air tight encapsulation and should be used if you wish to follow good OO design.

The examples shows and immediately invoked function (IIF) pattern that defines the Object Repository as a function returning an ad hock Object that encapsulates via closure.

The todos array (or map) is isolated and not directly accessible. It uses a getter to return the array of todos as a shallow copy

Examples

Both examples use IIF pattern to encapsulate the object created from the named Repository

Note that it has slightly different behavior than your object.

You can instantiate the object with or without the new token. Eg todos = Repository() or todos = new Repository()

The first example store data in an array that it keeps private, copied on creation and copied when accessed via the getter todos.

IFF ad hock

export default Repository = (() => {
    const save = (todos) => localStorage.todos = JSON.stringify(todos);
    const load = () => {
        try { return localStorage.todos ? JSON.parse(localStorage.todos) : [] }
        catch(e) { return [] }
    }
    return function(todos = []) {
        todos = [...todos];
        return Object.freeze({
            get todos() { return [...todos] },
            remove(todo, saveChanges = true) {
                const idx = todos.findIndex(item => item.uuid !== todo.uuid);
                idx > -1 && todos.splice(idx, 1);
                saveChanges && save(todos);
            },
            add(todo, saveChanges = true) {
                this.remove(todo, false);
                todos.push(toDo);
                saveChanges && save(todos);
            },
            save() { save(todos) },
            load() {
                load().forEach(todo => this.add(Object.assign(new Todo(), todo), false));
                return this.todos;
            }
        });
    }
})();

IFF with Map

This example uses a map to improve the efficiency of removing items and reduces the source size. It behaves identically to the first example.

Also as using this does present a security concern (even in modules) thus example references self via the named constant API

export default Repository = (() => {
    const save = (todos) => localStorage.todos = JSON.stringify(todos);
    const load = () => {
        try { return localStorage.todos ? JSON.parse(localStorage.todos) : [] }
        catch(e) { return [] }
    }
    return function(todosInit = []) {
        const API = Object.freeze({
            get todos() { return [...todos.values()] },
            remove(todo, saveChanges = true) {
                todos.delete(todo.uuid);
                saveChanges && API.save();
            },
            add(todo, saveChanges = true) {
                API.remove(todo, false);
                todos.set(todo.uuid, todo);
                saveChanges && API.save();
            },
            save() { save(API.todos) },
            load() {
                load().forEach(todo => API.add(Object.assign(new Todo(), todo), false));
                return API.todos;
            }
        });
        return API;
    }
})();

Notes

[.1] Note that MDN localStorage page cites "The pitfalls of using objects as maps" as reason not to use direct key access. Why only warn on localStorage why not have the same warning on every Object? Get with it MDN!!


Idiomatic word counting in Rust My goal is to read from standard input, break up the input into words, case-insensitively, and produce a report to standard output, where each line is a word followed by a space followed by its count. The output should be sorted by words.

This is my code:

use std::collections::BTreeMap;
use std::io;
use std::io::BufRead;

fn main() {
    let mut counts: BTreeMap<String, isize> = BTreeMap::new();
    let stdin = io::stdin();
    for line_result in stdin.lock().lines() {
        match line_result {
            Ok(line) => {
                let lowercase_line = line.to_lowercase();
                let words = lowercase_line.split(|c: char| {
                     !(c.is_alphabetic() || c == '\'')
                 }).filter(|s| !s.is_empty());
                 for word in words {
                    *(counts.entry(word.to_string()).or_insert(0)) += 1;
                 }
            },
            Err(e) => {
                panic!("Error parsing stdin: {:?}", e);
            }
        }
    }
    for (key, value) in counts.iter() {
        println!("{} {}", key, value);
    }
}

My questions are:

Is BTree the proper dictionary?
I know that there is a regex crate, but I would like to stay with things in standard Rust. That said, splitting is a terrible way to break up lines because you have to filter empties. Is there a way to just match the words, rather than splitting on non-word sequences?
Is matching on the Err part of the result proper? Or should we let the script crash? Is panicking okay?
I noticed one is not allowed to say let words = line.to_lowercase().split(...) because of the infamous"borrowed reference does not live long enough"` but is there a cleaner way?
Is there a nicer way to count words in a map? I don't like the asterisk.
I wish I didn't have to do an explicit lock on stdin.

Rust has a lot of things going for it, but when I compare what I got to the much prettier Julia version of this script, namely...

counts = Dict{AbstractString, UInt64}()
for line in eachline(STDIN)
  for word in matchall(r"[a-z\']+", lowercase(line))
    counts[word] = get(counts, word, 0) + 1
  end
end
for (word, count) in sort(collect(counts))
  println("$word $count")
end

...I'm thinking I don't know Rust very well, or, that's just the way things are. I mean, I know as a systems language, it's really hard to make vectors and strings. And they tell me I will learn to love the borrow checker. :) Hopefully someone with expertise in idiomatic Rust can be of service here. I'm not expecting it to be as short as the Julia code but I do fear my Rust is not idiomatic enough.

There is no "proper" dictionary, there are just different trade-offs. In this case, we have that HashMap gives us better asymptotic random access whereas BTreeMap gives us sortedness.

Sorting the a HashMap after-the-fact is well and good, but BTreeMap is already sorted so it seems like the better choice.

Rust very heavily gives tasks out to crates. This is guided by RFC 1242, and you might notice regex is in rust-lang-nursery. This means it is official and it is "standard rust"; it's just not in the standard library.

Plus, it's as easy as adding regex = "0.1" to your Cargo.toml, so that's no reason to avoid it.

Ignoring that, that

let words = line.to_lowercase().split(...)

doesn't work is just a fact of life right now, although that will eventually get fixed with non-lexical lifetimes.

These imports

use std::io;
use std::io::BufRead;

are nicer as

use std::io::{self, BufRead};

The large match

match line_result {
    Ok(line) => {
        ...
    },
    Err(e) => {
        panic!("Error parsing stdin: {:?}", e);
    }
}

would be nicer as

let line = match line_result {
    Ok(line) => line,
    Err(e) => panic!("Error parsing stdin: {:?}", e),
};

...

or even

let line = line_result.unwrap_or_else(
    |e| panic!("Error parsing stdin: {:?}", e)
);

But in this case the error handling doesn't add anything, so I'd just unwrap. All of these examples panic; a method that doesn't would involve error handling by printing and then returning from the function. Printing is normally worse to debug (no tracebacks) but nicer for end-users.

Instead of

*(counts.entry(word.to_string()).or_insert(0)) += 1;

which always allocates a new String, one can index with a borrowed &str. Sadly this isn't supported by the entry API right now, but you can hack around it:

if let Some(count) = counts.get_mut(word) {
    *count += 1;
    continue;
}
counts.insert(word.into(), 1);

Note the use of if let/continue instead of match is because of lexical lifetimes.

Since this is currently pretty ugly and the speedup probably doesn't matter, I'll leave this as a hypothetical. You say you "don't like the asterisk", but that's kind'a how it's meant to be done. I guess you could go the Julia route (get + unwrap_or + insert), but that's not really better.

After a few miscellaneous changes, the code for me looks like

extern crate regex;

use std::collections::BTreeMap;
use std::io::{self, BufRead};

use regex::Regex;

fn main() {
    let word_re = Regex::new(r"[a-z']+").unwrap();

    let mut counts: BTreeMap<String, isize> = BTreeMap::new();

    let stdin = io::stdin();
    for line in stdin.lock().lines() {
        let line = line.unwrap().to_lowercase();
        let matches = word_re.find_iter(&line);
        let words = matches.map(|(x, y)| &line[x..y]);

        for word in words {
            *counts.entry(word.into()).or_insert(0) += 1;
        }
    }
    for (key, value) in counts.iter() {
        println!("{} {}", key, value);
    }
}

This isn't as nice as the Julia code, but it's giving you a lot of opportunities to be a lot more efficient, and it's catching a lot more errors. It's true that locking stdin feels like a chore on 50-line examples, but it fits Rust's macro-goals of faster, safer APIs.


Mortgage calculator for homework I needed to create a mortgage calculator for an intro to CS class. As part of the assignment, with an interest rate of 6% needs to change to 7% after 3 years hence that if statement. The char dummy line at the end is a requirement from my professor.

I'm mainly looking for ways to clean it up or if I missed anything. I'm required to use namespace std, and I know a lot of you don't care for it.

#include <iostream>
using namespace std;

int main()
{
    double monthlyPayment;
    double balance;
    double interestRate;
    double interestPaid;
    double initialBalance;
    double termOfLoan;
    double month = 1;

    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(2);

    cout << "Enter the current balance of your loan: $";
    cin >> balance;
    cout << "Enter the initial yearly interest rate : ";
    cin >> interestRate;
    cout << "Enter the desired monthly payment : $";
    cin >> monthlyPayment;

    initialBalance = balance;

    while (interestRate >= 1)       /*Converts the interest rate to a decimal if the user inputs
                                                      in percentage form*/
    {
        interestRate = interestRate / 100;
    }

    if(month >= 36);
    {
        if(interestRate=.06)
        {
            interestRate=.07;
        }
    }
    balance = balance * (1 + interestRate / 12) - monthlyPayment;

    cout << "After month 1 your balance is $" << balance << endl;

    while (balance > 0)
    {
        if (balance < monthlyPayment)
        {
            balance = balance - balance;
        }
        else
        {
            balance = balance * (1 + interestRate / 12) - monthlyPayment;
        }

        month = month++;
        month = month + 1;
        month += 1;

        cout << "After month " << month << ", your balance is : $" << balance << endl;
        }
        cout << "You have paid off the loan at this point. Congratulations!" << endl;

        termOfLoan = month;

interestPaid = (monthlyPayment * termOfLoan) - initialBalance;

/*I believe the formula above would work if only there was
 a way to calculate how many months it took to pay
off the loan, but since it varies, I don't know how to
calculate "termOfLoan". */

            cout << "You paid a total ammount of $" << interestPaid << " in intrest." << endl;
            cout << "Total number of months = " << month << "." << endl;

char dummy;
cout << "Enter any key to quit." << endl;
cin >> dummy;
}

You use double values for calculations. Especially for money, I would suggest to switch to int and handle it in cents. That way you can avoid problems with floating point precision.
You don't check if cin>> fails or succeeds. If the user doesn't enter a number you may have a problem here. A possible solution might be to let the user reenter the value as long as it isn't correct.

do
{
    cout << "Enter the current balance of your loan: $";
}
while (!(cin >> balance));

You have a wrong check in the line if (interestRate = .06). You probably meant if (interestRate == .06). Additionally, this check might also be a problem as you do some calculations on interestRate that may cause inprecision (again floating point precision problem).

As you obviously await the user to input the value as int your check should be against 6 before you divide the value with 100.
You have this piece of code:

if (balance < monthlyPayment)
{
    balance = balance - balance;
}

Which is the same as:

if (balance < monthlyPayment)
{
    balance = 0;
}

I think the second version is easier to understand.

I didn't check any more of the code yet. I especially didn't prove it for correctness in you calculations.


Finding Egyptian fractions with A* search I've written an A* search to find the optimal solution to the equation

$$ \dfrac{4}{n} = \dfrac{1}{x} + \dfrac{1}{y} + \dfrac{1}{z} $$

with \$n, x, y, z\$ positive integers, and \$n\$ given; the optimal solution being the one with smallest sum \$ x + y + z \$.

(The Erdős–Straus conjecture states that there are solutions to this equation for all \$n>2\$.)

My working version:

def evaluate(option):
    return sum(option)

def generate_options(option):
    def option_valid(o):
        prev = o[0]
        for el in o[1:]:
            if el < prev:
                return False
            prev = el
        return True

    x, y, z = option
    opt = (x + 1, y, z)
    if option_valid(opt): yield opt
    opt = (x, y + 1, z)
    if option_valid(opt): yield opt
    opt = (x, y, z + 1)
    if option_valid(opt): yield opt

def is_solution(current, n):
    x, y, z = current
    if (4 / n) == (1 / x + 1 / y + 1 / z):
        return True
    return False

def A(option, generate_options, evaluate, is_solution):
    done = set()
    paths = PriorityQueue()
    paths.put((evaluate(option), option))
    done.add(option)
    while not paths.empty():
        price, current = paths.get()
        if is_solution(current):
            return price, current
        for gp in generate_options(current):
            if gp not in done:
                done.add(gp)
                paths.put((evaluate(gp), gp))
    return None

def main():
    def solution(x):
        return is_solution(x, n=18)

    print(A(
        (1, 1, 1),
        generate_options=generate_options,
        evaluate=evaluate,
        is_solution=solution))

The problem I see with this code would be that since I store all the checked solutions into a set, I could potentially run out of memory for an \$n\$ that would require a large amount of checked options. In my mind, I could fix this by clearing the entire set every \$m\$ iterations, but that could lead back to some options being checked more than once.

I'm fairly new to Python, and I also wonder if there's a better way to write my generate_options function. I do know there was no need to make it into a generator, but I did it that way for the sake of seeing how they work.

There's a bug in is_solution:

>>> is_solution((2, 3, 6), 4)
False

even though $$ {1\over2} + {1\over3} + {1\over6} = 1 = {4\over4}. $$

This is because \${1\over3}\$ and \${1\over6}\$ can't be exactly represented as floating-point numbers:

>>> 1/2 + 1/3 + 1/6
0.9999999999999999

The way to solve this is to represent fractions using the fractions.Fraction class:

>>> Fraction(1, 2) + Fraction(1, 3) + Fraction(1, 6) == Fraction(4, 4)
True

The question claims the algorithm is "A*", but that's not true. The A* search algorithm tries to find the least-cost path to an identifiable goal in a directed graph. But here you can't identify the goal (because you're looking for a minimum, you won't know what it is until the search is complete), and you don't care about the cost of the path taken to get there.

It would be better to call the algorithm "best-first search".
You're basically searching over all triples of integers looking for one that happens to add up to your target. This is a waste of time, because after you've picked \$y\$ and \$z\$, say, then you can know that $$ x = {1 \over {4\over n} - {1\over y} - {1\over z}} $$ and all you have to do is compute this and check that it's an integer.

So a (slightly) better strategy looks like this:

from collections import namedtuple
from fractions import Fraction
from itertools import chain, count, takewhile
from math import floor

Triple = namedtuple('Triple', 'x y z')

def egyptian_triples(n):
    """All solutions to 1/x + 1/y + 1/z = 4/n in lexicographic order."""
    tz = Fraction(4, n)
    for z in count(floor(1 / tz) + 1):
        ty = tz - Fraction(1, z)
        for y in range(floor(1 / ty) + 1, z + 1):
            tx = ty - Fraction(1, y)
            if tx.numerator == 1 and tx.denominator <= y:
                yield Triple(tx.denominator, y, z)

def min_egyptian_triple(n):
    """Return the solution to 1/x + 1/y + 1/z = 4/n with minimum x + y + z."""
    triples = egyptian_triples(n)

    # First solution in lexicographic order.
    first = next(triples)
    max_z = sum(first) - 2

    # Return minimum solution.
    return min(chain((first,), takewhile(lambda t: t.z <= max_z, triples)),
               key=sum)

This is substantially faster:

>>> from timeit import timeit
>>> timeit(lambda:main(115), number=1)
(290, (60, 92, 138))
19.941934717004187
>>> timeit(lambda:print(min_egyptian_triple(115)), number=1)
Triple(x=60, y=92, z=138)
0.46365413605235517


Checking if a relationship exists I'm using a many-to-many relationship between users and roles with propel:

    <column name="id" type="integer" required="true" primaryKey="true" autoIncrement="true" />
    <column name="username" required="true" type="varchar" primaryKey="true" size="50" />

    <column name="id" type="integer" required="true" primaryKey="true" autoIncrement="true" />
    <column name="role" required="true" type="varchar" size="20" primaryString="true" />
    <column name="name" required="true" type="varchar" size="50" />

    <unique>
        <unique-column name="role" />
        <unique-column name="name" />
    </unique>

    <column name="user_id" type="integer" primaryKey="true"/>
    <column name="role_id" type="integer" primaryKey="true"/>
    <foreign-key foreignTable="user">
        <reference local="user_id" foreign="id"/>
    </foreign-key>
    <foreign-key foreignTable="role">
        <reference local="role_id" foreign="id"/>
    </foreign-key>

This is how I check if a user has a role:

class User extends BaseUser
{
    public function hasRole($checkRole)
    {
        foreach ($this->getRoles() as $role)
        {
            if ($role->getRole() == $checkRole)
            {
                return true;
            }
        }

        return false;
    }
}

This works, but I think it could be optimized. Any ideas?

You don't have to loop throught the collection since you can directly query the database or your object if it is already loaded:

class User extends BaseUser
{
    public function hasRole($checkRole)
    {
        $userWithRole = UserQuery::create()
            ->filterByRole($checkRole)
            ->findOne();

        return !is_null($userWithRole);
    }
}

You can either check that $userWithRole is not null like I did or if it is an instance of User.

If your objects are already hydrated you can avoid the query by querying the Roles collection:

class User extends BaseUser
{
    public function hasRole($checkRole)
    {
        return $this->getRoles()->contains($checkRole);
    }
}


Faster method to find data using search word? I need to search through a string array to find every occurrence of "Parameters Table", and between each "Parameters Table" and the next, get another string from a specified index (that remains constant). I have been doing this like so:

public List<string> findlistOfNames(string[] arrayToLookForNames)
{
    List<string> listOfNames = new List<string>();

    const string separator = "Parameters Table"; //This is the string I am searching for

    var cuttedWords = arrayToLookForNames.SkipWhile(x => x != separator).Skip(1);

    while (cuttedWords.Any())
    {
        var variable = cuttedWords.TakeWhile(x => x != separator).ToArray();
        cuttedWords = cuttedWords.Skip(variable.Length + 1);
        listOfNames.Add(variable[2]); //This (always index 2) needs to be added to the list
    }
    return listOfNames;
}

This works but too slowly. Is there a better way to do this?

Here is a snippet of string[] arrayToLookForNames:

  Parameters Table

  0

  41

  Baro Pressure

  hPa

  AFD2

  recorded

  Parameters Table

  0

  42

  Baro Setting

  in-hg

Perhaps the best way to solve this problem is to not have it in the first place. If you are in control of the code that produce this array of string, probably from a text file or a similar input, you could produce a tree of values instead right from the start. That way, instead of trying to find specific values through a text search, you could simply find the nodes in the tree that you need, for instance the "Parameters Table" node, and then dive into each parameters from there. This would look a little bit like this:

<root node>
    A
        B1
        C1
    A
        B2
        C2

If you are not in control of this code, then you have no other choice than to search through the entire list. Marcin Juraszek did propose a pretty good solution for this. Another way to do this search, which would also be a little bit faster would be this:

public static class EnumerableExtensions
{
    private class SearchResults
    {
        public List<String> Values = new List<string>();
        public int SkipCounter = -1;
    }

    public static List<string> FindAllSubItems(this IEnumerable<string> source, string keyword, int distance)
    {
        return source.Aggregate(
            new SearchResults(),
            (sr, v) =>
            {
                if (v.Equals(keyword))
                {
                    sr.SkipCounter = distance;
                }

                if (sr.SkipCounter == 0)
                {
                    sr.Values.Add(v);
                }

                --sr.SkipCounter;

                return sr;
            },
            sr => sr.Values
        );
    }
}

Which can be used like so:

var someList = new string[] {"A", "B1", "C1", "A", "B2", "C2" };
someList.FindAllSubItems("A", 1); // returns { "B1", "B2" }

The idea around this solution is to make sure that only one pass through the list will ever happen. This is an O(n) solution, as opposed to Juraszek's one which is an O(n + m) solution where n is the amount of inputs and m is the amount of matching keys. This solution also adds a safety around keys that does not have at least distance elements. For now, it simply skips it, but it is trivial to check for the value of SkipCounter before resting it if an exception needs to be thrown.

Once we find a match for our first parameter, we set a skip counter based on a distance parameter. We then proceed on decrementing the counter until it reaches zero. If the counter reaches zero, we have a found an item at distance items of the parameter so we save it. If it never reaches zero it means that we are looking for an item further than there is in the list. Providing a negative distance to this algorithm will never yield any results as it is a forward only algorithm. When the final value is returned, we simply trash the counter and only keep the values we saved in our temporary SearchResults object.

EDIT

As requested in the comment, the question author is wondering how to trigger updates to a progress bar in a solution like this. Since this code is using LINQ which works wonders with yield return, you can simply call it like this:

var items = someList
    .Select((x, i) => { UpdateMyProgressBarForIndex(i); return x; })
    .FindAllSubItems(...);

As you expect, the lambda specified in the select block will be called for each element in the list. But because of how LINQ methods are designed (using yield return), this will happen as the aggregate method process them. This is because the list of items that Select returns is built only as new items are requested by the bottom most foreach loop which runs inside the Aggregate method. Basically, you will see this behavior:

Initialize aggregate seed
foreach items in the list
Select's lambda for item (x)
Aggregate lambda for item(x)
when done
extract final values from the seed


Given a search string, fetch all movies results from the api Was told this code was 'weird' and didn't pass the coding test. I tried to split up to show the different levels of abstraction but maybe I went overboard? I told them this in the walk through of the code as things like console logging would be something more like save to database or something more complex so it's its own abstraction.

const https = require('https');
/*
 * Complete the function below.
 * Use console.log to print the result, you should not return from the function.
 * Base url: https://jsonmock.hackerrank.com/api/movies/search/?Title=
 */
async function getMovieTitles(substr) {

    // get first page results
    const results = await fetchMoviePage(substr, 1);
    let matches = results.data.map(extractMovieTitle);

    // base case - if we only have one page of results then we done here
    if (results.total_pages === 1) {
        return sortAndPrintResults(matches);
    }

    // fill an incremented integer array from page 2 to last page
    const pages = fillRange(2, results.total_pages);

    // for each page fetch data and add to results list
    for await (const page of pages) {
        const { data } = await fetchMoviePage(substr, page);
        matches = matches.concat( data.map(extractMovieTitle) );
    }

    sortAndPrintResults(matches);
}

/**
 * send sorted results to stdout
 */
function sortAndPrintResults(results){
    console.log(results.sort().join('\n'));
}

/**
 * fetches a page of movie results.
 */
async function fetchMoviePage(substr, page) {
    try {
        return await fetchMatchingMovies(substr, page);

    } catch (error) {
        console.log(`Error retrieving movies for ${substr} on page ${page}: ${error}`);
        return {data:[]};
    }
}

/**
 * Fills an array of incremented integers from start to end
 */
function fillRange(start, end) {
    return Array(end - start + 1).fill().map((item, index) => start + index);
};

/**
 * returns the movie title from a movie object
 */
function extractMovieTitle(movie) {
    return movie.Title;
}

/**
 * fetch a list of movies matching a search string
 */
function fetchMatchingMovies(searchString, page) {
    const queryString = `https://jsonmock.hackerrank.com/api/movies/search/?Title=${searchString}&page=${page}`;

    return new Promise((resolve, reject) => {

        https.get(queryString, res => {
            let data = '';
            res.on('data', chunk => data += chunk);
            res.on('end', () => resolve(JSON.parse(data)));

        }).on('error', e => reject(e));
    });
}

I think it's cool that you fetch the pages in parallel.

A minor miss of the spec

The description says to not return from getMovieTitles,
but the implementation does that.

I agree the early return makes sense when there is a single page of results.
I would have extracted to a function the code that fetches results.
Then the caller could simply call sortAndPrintResults on the returned array.

Things I find weird

return sortAndPrintResults(matches) is weird because sortAndPrintResults is void.

sortAndPrintResults joins the results before printing to console,
which doubles the memory used by the results.
It would have been better to call console.log in a loop.

I find the name fillRange misleading.
Basically it creates a sequence of numbers.
That's not what I would guess from the name.

It's a pity to construct an array of numbers just to loop over them.

These two issues could be fixed by implementing a range function as an async generator.

It's not 100% clear if the functions were given or only the first one.
Many of them would be better inlined.


Tree parent and child nodes I have this method that returns true if attribute is already used and false otherwise:

public boolean alreadyUsed(Node node, int attribute)
{
    if (node.parent == null)
    {
        return false;
    }

    if (node.children != null)
    {
        if (node.splitAttribute == attribute )
        {
            return true;
        }
    }
    return alreadyUsed(node.parent, attribute);
}

Can this be written in a more understandable way?

Well, following conventions helps making your code more understandable. One convention is, for methods that return a boolean, using a predicate as a name, or as said in this answer, using a question.

So to begin with, I'd name the method isAlreadyUsed.

A second improvement by following conventions would be using accessor methods:

node.getParent() instead of node.parent. But that depends on the scope of Node.

Item 14 in Joshua Bloch's Effective Java:

  In public classes, use accessor methods, not public fields


Merging predicted values into measured values I created the following function below to merge the real values with the predicted values (when real are absent) in a new column in data.frame. The function actually works, but I would like to optimize it, because with the dataset that I work with, the function takes about two hours to run.

The function seems to be slowed down by the loop.

p <-
  function(object, newdata = NULL, type = c("link", "response", "terms"),
           rse.fit = FALSE, dispersion = NULL, terms = NULL,
           na.action = na.pass, ...)
  {
{
    pred <- predict (object,newdata)

      }

    vetor1 <- (newdata$ALT)         # Creates a column vector from the actual heights of the data.frame
    vetor1[is.na(vetor1)] <- 0      # Replaces the NA's present in the vector created above the numeric value 0
    vetor2 <- c(pred)           # Creates a vector from the predicted data
    for(i in 1:length(vetor1)){     # The loop is executed until all values vector1 pass the following condition
      if(vetor1[i]==0.00){      # If a value of the first vector has the value 0, ie, if it is absent
        vetor1[i]=vetor2[i]     # Then the predicted value will replace the missing value
        newdata$ALTMISTA <- vetor1  # The vector1, already possessing the actual values and the predicted values merged into the same vector goes                   on to become a new column in data.frame, this column is called a ALTMISTA
      }
    }
    return (newdata)
  }

I am assuming that the call to predict is not what is taking most of the time, so I'm not including that in my analysis.

One thing that is slowing down your code is that you are assigning vetor1 to newdata$ALTMISTA every iteration of the loop (well, every iteration that is 0). That could be pulled out of the loop since it only needs to be done once.

vetor1 <- (newdata$ALT)         # Creates a column vector from the actual heights of the data.frame
vetor1[is.na(vetor1)] <- 0      # Replaces the NA's present in the vector created above the numeric value 0
vetor2 <- c(pred)           # Creates a vector from the predicted data
for(i in 1:length(vetor1)){     # The loop is executed until all values vector1 pass the following condition
    if(vetor1[i]==0.00){      # If a value of the first vector has the value 0, ie, if it is absent
        vetor1[i]=vetor2[i]     # Then the predicted value will replace the missing value
    }
}
newdata$ALTMISTA <- vetor1  # The vector1, already possessing the actual values and the predicted values merged into the same vector goes                   on to become a new column in data.frame, this column is called a ALTMISTA
return (newdata)

Second, you replace NA with 0, and then test against 0. That means you are replacing both NA's and any 0's in the data. If you only want to replace NA's, just replace those without recoding them.

vetor1 <- (newdata$ALT)         # Creates a column vector from the actual heights of the data.frame
vetor2 <- c(pred)           # Creates a vector from the predicted data
for(i in 1:length(vetor1)){     # The loop is executed until all values vector1 pass the following condition
    if(is.na(vetor1[i])){      # If a value of the first vector is NA, ie, if it is absent
        vetor1[i]=vetor2[i]     # Then the predicted value will replace the missing value
    }
}
newdata$ALTMISTA <- vetor1  # The vector1, already possessing the actual values and the predicted values merged into the same vector goes                   on to become a new column in data.frame, this column is called a ALTMISTA
return (newdata)

Now the explicit loop can be replaced by vectorized functions, in this case ifelse

vetor1 <- (newdata$ALT)         # Creates a column vector from the actual heights of the data.frame
vetor2 <- c(pred)           # Creates a vector from the predicted data
vetor1 <- ifelse(is.na(vetor1), vetor2, vetor1) # replace elements of vetor1 that are NA with corresponding elements of vetor2
newdata$ALTMISTA <- vetor1  # The vector1, already possessing the actual values and the predicted values merged into the same vector goes                   on to become a new column in data.frame, this column is called a ALTMISTA
return (newdata)

Finally you can eliminate some single use intermediate variables. This may not appreciably speed up the function, but it does make for cleaner code.

vetor1 <- (newdata$ALT)
newdata$ALTMISTA <- ifelse(is.na(vetor1), pred, vetor1)
return (newdata)

As you did not provide example data, I was not able to benchmark these alternatives (nor, for that matter, even run them).