Convert number into hours : minutes I wrote a simple extension to convert a number into a hours and minutes string in the ##:## format. This seems like a good way to do it, but let me know what you think.

Number.prototype.display_hours_minutes = function () {
  var remainder = this % 1;
  var remainderTime = new Date(remainder * 3600 * 1000);
  return ('0' + Math.floor(this)).slice(-2) + ':' + ( '0' + remainderTime.getMinutes()).slice(-2);
};

So this turns something like 53.34 into "53:20"

Extending built-in types always carries a risk that your code will interact poorly with other code.  Often, web page authors cobble together pages that use many JavaScript libraries.  Consider making it a regular function.

The function has a silent cap of "99:59".  That's an odd limit.  Either the number of hours should be unlimited, or it should be modulo 24.  Modulo 100 is totally unexpected.

The code would also fail to output the minutes correctly in some non-standard time zones, such as India, where the time zone offset relative to UTC is not an integral number of hours.

You don't need to compute remainder, as the Date object takes care of extracting the minutes portion in any case.

It took me a few seconds to figure out the significance of 3600 and 1000.  A comment would be helpful.

Here's my recommendation for a modulo 24 solution:

Number.prototype.display_hours_minutes = function () {
  var date = new Date(this * 3600 /* sec per hr */
                           * 1000 /* msec per sec */);
  return ('0' + date.getUTCHours()  ).slice(-2) + ':' +
         ('0' + date.getUTCMinutes()).slice(-2);
};


Max heap implementation I have implemented a max-Heap data structure backed by an array. I wanted to know whether this is an acceptable implementation or not.

Any improvements or suggestions are welcome.

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MaxHeapDemo {

  int heap[],heapSize=0;

public MaxHeapDemo() {
    // TODO Auto-generated constructor stub
    heapSize=0;
}

/**
 * Function to build the max-heap
 * @param inputData
 */
private  void maxHeapify(int[] inputData) {

    heap= new int [inputData.length+1];
    //fill the heap from 1 index to make life easier

    //if a parent node is at ith index the the left child is at 2*i and right child is at
    //2*i+1
    //  System.out.println("data ="+Arrays.toString(data));
    //insert from the back to the front

    for (int i = 0; i < inputData.length; i++) {
        heap[heapSize+1]=inputData[i];

        heapify(inputData[i]);
        ++heapSize;
    }
}

/**
 * This method will balance the heap according to the properties of the heap
 * @param value
 * @param data
 */
private  void heapify( int value/*, int[] data*/) {

    //int index = data.length-1;
    int index = heapSize+1;
    //System.out.println("index "+index+" heap[index/2]"+heap[index/2]);
    while (index > 1 && heap[index/2] < value ){
        //swap parent with child
        int temp= heap[index/2];
        heap[index/2]= heap[index];
        heap[index]=temp;

        index/=2;
    }

}

/**
 * THis method remove the maximum element from the heap and re-balances the heap according
 * to the Max heap property
 * @return
 */
public  int removeMax() {

if(heapSize == 0)
    throw new NoSuchElementException("The heap is empty");

    int result=-1;

    result = heap[1];
    heap[1]=heap[heapSize];
    --heapSize;

    //now balance the heap according to the max heap property

    for (int i=1;i < heapSize ; i*=2){
        if (i*2 < heapSize && heap[i]< heap[i*2] && heap [i*2] > heap[i*2+1]){
            //swap the two elements
            int max= heap[i*2];
            heap[i*2]=heap[i];
            heap[i]= max;
        }else if (i*2+1 < heapSize && heap[i]< heap[i*2+1]){
            int max= heap[i*2+1];
            heap[i*2+1]=heap[i];
            heap[i]= max;
        }
    }
    System.out.println(Arrays.toString(heap));
    return result;
}
public void add(int value){
    int index = heapSize+1;
    if(index >= heap.length) heap = Arrays.copyOf(heap, heapSize + 16);
    heap[index] = value;

    while (index > 1 && heap[index/2] < heap[index]){
        //swap parent with child
        int temp= heap[index/2];
        heap[index/2]= heap[index];
        heap[index]=temp;

        index/=2;
}
}

/**
 * Main method to test the program
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    MaxHeapDemo heapDemo = new MaxHeapDemo();
    heapDemo.maxHeapify(new int []{3,2,6,7,9});
    System.out.println(Arrays.toString(heapDemo.heap));
    System.out.println("the maximum element is ="+heapDemo.heap[1]);
    System.out.println("remmoved max ele is = "+heapDemo.removeMax());
}
}

in the constructor it's better to allocate an empty array to avoid an unexpected null pointer.

In maxHeapify you should just at least initialize heapSize to 0 before the loop.

You have no other way to add a element to the heap. This would be something like this:

public void add(int value){
    int index = heapSize+1;
    if(index >= heap.length) heap = Arrays.copyOf(heap, heapSize + 16);
    heap[index] = value;

    while (index > 1 && heap[index/2] < heap[index]){
        //swap parent with child
        int temp= heap[index/2];
        heap[index/2]= heap[index];
        heap[index]=temp;

        index/=2;
    }
}

heapify depends on value being the same as the value at heap[heapSize+1] instead you can use the add above.

removeMax should throw a better exception than either returning -1 or throwing NullPointerException if the heap is empty (from being emptied or never being filled).

public  int removeMax() {
    if(heapSize == 0)
        throw new NoSuchElementException("The heap is empty");

    //...
}


Execute a function n times, where n is known at compile time Motivation

In this question, a user asked whether it is possible to inline the following function:

-- simplified version
{-# INLINE nTimes #-}
nTimes :: Int -> (a -> a) -> a -> a
nTimes 0 f x = x
nTimes n f x = nTimes (n-1) f (f x)

Unfortunately, the answer seems no, since GHC sees a recursive function and gives up. Even if you use a compile-time constant, e.g. nTimes 1 (+1) x, you don't end up with x + 1, but with nTimes 1 (+1) x.

While it's of course fine to refuse inlining if the number of loops is unknown, it's also a hassle if it is known.

Code

As you can see in the question above, I've proposed the following solution:

{-# LANGUAGE TemplateHaskell #-}
module Times where

import Control.Monad (when)
import Language.Haskell.TH

-- > item under review begins here

nTimesTH :: Int -> Q Exp
nTimesTH n = do
  f <- newName "f"
  x <- newName "x"

  when (n <= 0)    (reportWarning "nTimesTH: argument non-positive")
  when (n >= 1000) (reportWarning "nTimesTH: argument large, can lead to memory exhaustion")

  let go k | k <= 0 = VarE x
      go k          = AppE (VarE f) (go (k - 1))
  return $ LamE [VarP f,VarP x] (go n)

-- < item under review ends here

This should, for any n, create a function with patterns named f and x, and apply f to x with AppE n times:

$(nTimesTH 0) = \f x -> x
$(nTimesTH 1) = \f x -> f x
$(nTimesTH 2) = \f x -> f (f x)
$(nTimesTH 3) = \f x -> f (f (f x))

I can verify that the created function has the correct type:

$ ghci -XTemplateHaskell Times.sh
ghci> :t $(nTimesTH 0)
$(nTimesTH 0) :: r -> r1 -> r1

ghci> :t $(nTimesTH 1)
$(nTimesTH 1) :: (r1 -> r) -> r1 -> r

ghci> :t $(nTimesTH 2)
$(nTimesTH 2) :: (r -> r) -> r -> r

ghci> :t $(nTimesTH 3)
$(nTimesTH 3) :: (r -> r) -> r -> r

To all my knowledge, nTimesTH works exactly as expected.

Given that this is my first time dabbling with Template Haskell, does this follow best practices? Also, I'm using VarE, AppE and so on. Language.Haskell.TH also provides some combinators, so that one can write

  let go k | k <= 0 = varE x
      go k          = appE (varE f) (go (k - 1))
  lamE (map varP [f,x]) (go n)

Is this just personal preference, or is lamE preferred? As far as I can see, the expression combinators use the canonic implementation, e.g. varE = return . VarE, appE f x = liftA2 AppE f x and so on.

Tests

Just for completeness the QuickCheck tests. Those aren't really part of the review, but here fore completeness:

module Times where
import Test.QuickCheck

-- .. rest of module as above

genTestSingle :: Int -> Q Exp
genTestSingle n = do
  f <- newName "gTSf"
  x <- newName "gTSx"

  lamE [varP f, varP x] $
    appsE [ [| (==) |], appsE [nTimesTH n,           varE f, varE x]
                      , appsE [ [| nTimesFoldr n |], varE f, varE x]]

genAllTest :: Int -> Q Exp
genAllTest n = do
  f <- newName "gATf"
  x <- newName "gATv"

  lamE [varP f, varP x] $ doE $ (flip map) [1..n] $ \i ->
    noBindS $ appE [| quickCheck |] $ appsE [genTestSingle i, varE f, varE x]

module Main where

main = $(genAllTest 100) sin 40

Your implementation is fine. But it is a little bit ironic: In your SO answer, you start of with "you can use better functions", yet you rewrite nTimes via go. If this was a real module, you would probably want to export both functions nTimesTH and nTimes, and implement the former via the latter:

{-# LANGUAGE TemplateHaskell #-}
module Times (nTimes, nTimesTH) where

import Control.Monad (when)
import Language.Haskell.TH

-- example implementation
nTimes :: Int -> (a -> a) -> a -> a
nTimes n f x = iterate f x !! max 0 n

nTimesTH :: Int -> Q Exp
nTimesTH n = do
  when (n <= 0)    (reportWarning "nTimesTH: argument non-positive")
  when (n >= 1000) (reportWarning "nTimesTH: argument large, can lead to memory exhaustion")

  f <- newName "f"
  x <- newName "x"

  lamE (map varP [f,x]) $ nTimes n (appE (varE f)) (varE x)

This removes the need for code duplication, and any future optimization you find for nTimes gets automatically applied in nTimesTH, although that only matter during the compile time. After all $(nTimesTH n) is completely evaluated during compilation.

Other than that, I moved the warnings on top of the function, since this brings the names f and x closer to their actual use. I also replaced the data constructors with their respective functions.

Note that for a real module you still want to add documentation:

-- | @'nTimes' n f x@ applies @f@ @n@ times over @x@.
-- It does not apply @f@ if @n@ is negative. In this case @x@ is returned.
--
-- prop> nTimes n f x == iterate f x !! max 0
nTimes :: Int -> (a -> a) -> a -> a

-- | @'nTimesTH' n@ returns a function that applies the first
--   argument @n@ times to the second argument.
--   @n@ must be known at compile time. Needs @-XTemplateHaskell@.
--
-- prop> $(nTimesTH n) f x == nTimes n f x
nTimesTH :: Int -> Q Exp


Simple MPG calculator in Python I am a self taught coder taking a Programming Fundamentals class to work towards a degree. It's based on Python, which I'm not as familiar with as other languages. I added error handling like I would in javascript or php to be an overachiever. Professor gave online feedback (online course) not to use try-except, that it is ahead of where we are in the semester, that even when we do get there, she doesn't want it in our code, and that this code is "not well formed" because I used try-except. She gave no feedback as to what she meant and I don't think that sounds right but don't now enough to stand my ground. Googling "well formed python" just give me a bunch of xml.

# main function
def main():

    # @input dist : distance traveled in miles

    # @input guse : gas used traveling dist

    # @output mpg : dist/guse

    # set dist from input "Enter miles traveled: "
    dist = input('Enter distance traveled(in miles): ')
    # make sure dist is a number, and if not print error and restart
    try:
        dist = float(dist)
    except ValueError:
        print('Distance traveled must be a number! You did not travel "' + \
              dist + '" miles!')
        main()
    else:
        # if dist is 0.0, print error and restart
        try:
            x = 1 / dist
        except ZeroDivisionError:
            print('Miles traveled cannot be 0!')
            main()
        else:
            # set guse from input "Enter gas used in gallons: "
            gcon = input('Enter gas consumed traveling(in gallons): ')

            # make sure guse is a number, and if not print error and restart
            try:
                gcon = float(gcon)
            except ValueError:
                print('Gas consumed must be a number. You did not use "' + \
                          gcon + '"" gallons of gas!')
                main()
            else:

                # set mpg to dist divided by guse
                # if guse is 0.0, print error and restart
                try:
                    mpg = dist / gcon
                except ZeroDivisionError:
                    print('Gas consumed can not be 0!')
                    main()
                else:

                    # return(print) mpg
                    print('Average miles per gallon(mpg):', format(mpg, '5.2f'))

                    # print request for enter keypress to end
                    input('press enter to continue')

# Call main function
main()

I have three main remarks:

Recursion is not really an appropriate retry mechanism.

Try this: hold down Enter for a dozen responses, then hit ControlC.  As you see, the stack trace is quite deep.  It would be better for the call stack to be the same regardless of how the user arrived at a certain point in the code, because invariants make software easier to test and debug.  You're using recursion as a GOTO, except it's worse because it leaves a trace.  Instead, the validation should be done in a loop, which you break out of when valid input is obtained.
The code structure is a bit repetitive.

The routines to input the distance and gas consumption are actually quite similar, and could be written using shared code.
Trial division is a poor way to test for a zero value.

You test whether dist is zero with

# if dist is 0.0, print error and restart
try:
    x = 1 / dist
except ZeroDivisionError:
    print('Miles traveled cannot be 0!')
    main()

There are more straightforward ways to test for a zero value!  You end up discarding x, so the trial division isn't even useful work.

On further thought, your validation is not quite right.  If you're going to validate your input, you might as well prohibit negative numbers.  It is possible for the distance to be zero, when the car has been idling.  (The zero-distance case would only be problematic when displaying efficiency in "metric" units of L / 100km.)

In conclusion, your use of exceptions for validation is partly inappropriate (catching ZeroDivisionError to test for zero, especially for dist, from a logical viewpoint as well as a code expression viewpoint) and partly appropriate (catching ValueError to test for strings that cannot be interpreted as numbers).  I don't see any alternative to catching ValueError, except perhaps checking the input string against a regular expression \d+(?:\.(?:\d*))?, and I would consider ValueError to be the superior approach.  I think it would be fair to challenge your professor to propose a better alternative — in my opinion, the ball is in her court.

A minor note: your comments are inconsistent with your code.  Your code has a variable named gcon; the comments mention guse.

Suggested solution:

def ask(prompt, typeconv, typeconv_err, validation=None, validation_err=None):
    """
    Displays the prompt and asks for user input.  The result is passed through
    the typeconv function, then possibly a validation function as well.  If
    either the type conversion fails (with a ValueError) or the validation
    fails (by being false value), then the respective error message is
    displayed, and the prompt is displayed anew.
    """
    while True:
        val = input(prompt)
        try:
            val = typeconf(val)
        except ValueError:
            print(typeconv_err % (val))
        else:
            if validation is not None and not validation(val):
                print(validation_err % (val))
            else:
                return val

def main():
    dist = ask('Enter distance traveled(in miles): ',
               float,
               'Distance traveled must be a number! You did not travel "%s" miles!',
               lambda dist: dist >= 0.0,
               'Miles traveled cannot be negative!')

    gcon = ask('Enter gas consumed traveling(in gallons): ',
               float,
               'Gas consumed must be a number. You did not use "%s" gallons of gas!',
               lambda gcon: gcon > 0.0,
               'Gas consumed cannot be 0 or negative!')

    # print mpg
    mpg = dist / gcon
    print('Average miles per gallon(mpg):', format(mpg, '5.2f'))

    # print request for enter keypress to end
    input('press enter to continue')

# Call main function
main()


Removing any duplicate characters in a string I have piece of code in C which removes any duplicate characters in a string.  But I am doing it in two loops and would like it to optimize it to one loop.

void removeDuplicates(char* ptr)
{
    int end = 1;
    int length = strlen(ptr);
    int current;
    int i;
    current = 1;

    for(end=1; end<length; end++)
    {
        for(i=0; i<end; i++)
        {
            if(ptr[end] == ptr[i])
            break;
        }

        if(i == end)
        {
            ptr[current] = ptr[i];
            current++;
        }
    }

    ptr[current] = 0;
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    gets(str);
    removeDuplicates(str);
    printf("%s\n", str);
    return 1;
}

Remove Duplicates:  (Re-Write Ant's code so it is readable).

#include <stdio.h>

void removeDuplicates(char* ptr);

void removeDuplicates(char* ptr)
{
    char seen[UCHAR_MAX+1] = {0};

                              //
                              // Smallest data type is a char (unless you want to bit
                              // twiddle, and that has been shown to be not worth it
                              // see the complaints about std::vector<bool> in C++).
                              // 256 bytes is not much.
                              //
                              // By using char as they type it prevents all the complex
                              // multiplication/division an bit twiddling that Ant was doing.

    unsigned char* source = (unsigned char*)ptr;
    unsigned char* dest   = (unsigned char*)ptr;
    unsigned char  next;

    do
    {
        next  = *source;       // Get next character.
        if (!seen[next])       // Only enter the `if block` if we have not seen it.
        {
            seen[next] = 1;    // Mark it as seen
            *dest = next;      // Move it to destination.
                               // Note: source will change faster than dest when we
                               //       start seeing dupes, this acts as the copy back
                               //       over the duplicates.
            ++dest;
        }
        ++source;
    }
    while (next != '\0');      // Once we have copied the null terminator quit.
}


Date ranges from a given start date I'm trying to get a certain number of date ranges given a start date. Here's my code:

var startDate = new DateTime(2014, 1, 1);
var dates = new List<DateBlock>();
int counter = 0;
while(counter < 6)
{
    if (startDate >= DateTime.UtcNow)
    {
        dates.Add(new DateBlock
        {
            StartDate = startDate,
            EndDate = startDate.AddDays(30)
        });

        counter++;
    }

    startDate = startDate.AddDays(30);
}

var first =  dates.First();
dates.Insert(0, new DateBlock
{
    StartDate = first.StartDate.AddDays(-30),
    EndDate = first.StartDate
});

I'm wondering if there is a better way of doing this?

EDIT:
If the start date is 1/1/1 it should loop through and increment by 30 days and only add to the list if the current date is greater than or equal to UtcNow. Also it should keep going into the future until 6 more DateBlock's are added to the list.

The loop to find the starting date is clearly not needed.  This can be done with library object TimeSpan -- like this:

void Main()
{
  var startDate = new DateTime(2014, 1, 1);
  var dates = new List<DateBlock>();

  int priorPeriods = ((DateTime.UtcNow-startDate).Days) / 30;

  DateTime dateIndex = startDate.AddDays(priorPeriods*30);
  for(int index = 0; index < 6; index++)
  {
     dates.Add(new DateBlock { StartDate = dateIndex, EndDate = dateIndex.AddDays(30) });
     dateIndex = dateIndex.AddDays(30);
  }
}

public class DateBlock
{
   public DateTime StartDate { get; set;}
   public DateTime EndDate { get; set; }
}

You might have to check the edge case (today is exactly divisible by 30) to see it matches requirements.

Here is how you do it with linq (looks cooler, but slower)

void Main()
{
  var startDate = new DateTime(2014, 1, 1);
  var dates = new List<DateBlock>();

  int priorPeriods = ((DateTime.UtcNow-startDate).Days) / 30;

  dates = Enumerable.Range(0,6)
                .Select(index => new DateBlock {
                                   StartDate = startDate.AddDays((priorPeriods+index)*30),
                                   EndDate =startDate.AddDays((priorPeriods+index+1)*30)
                }).ToList();
 }

public class DateBlock
{
   public DateTime StartDate { get; set;}
   public DateTime EndDate { get; set; }
}


Minimum number of swaps required to sort the array in ascending order Here is my problem statement. An excerpt:

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.
For example, given the array arr = [7, 1, 3, 2, 4, 5, 6] we perform the following steps:

i   arr                     swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

The code:
int minimumSwaps(int arr_count, int* arr) {

long long int i,count=0,j,temp,min,min_index;
for(i=0;i<arr_count;i++)
{
    min=arr[i];
    min_index=i;
    for(j=i+1;j<arr_count;j++)
    {
        if(arr[j]<min)
        {
            min=arr[j];
            min_index=j;
        }
    }
    if(min_index!=i)
    {
        count++;
    temp=arr[min_index];
    arr[min_index]=arr[i];
    arr[i]=temp;
    }
    }
return count;
}

5 out of 15 test-cases are failing. Here is one of the test cases. It is failing with a message as "Terminated due to timeout".
I used selection sort approach as selection sort makes minimum swap operation.
My time complexity is O(n^2). Can I reduce it?

Analyzing the problem, finding clues

  I used selection sort approach as selection sort makes minimum swap operation.

Really? (I don't know.) More importantly, are you sure sorting is needed here?

  My time complexity is \$O(n^2)\$. Can I reduce it?

When the time limit is exceeded,
and the program appears to work correctly for non-large inputs,
the typical cause of slowness is the algorithm.
It can be hard to find an efficient algorithm.
To figure out the trick, look for clues.
For example, look details in the question that are not used in the current algorithm.

  You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n] without any duplicates.

Take a closer look. What's in there that your solution is not using?

There's nothing in your implementation that benefits from integers being consecutive, without any duplicates.
That is, it's not benefitting from this constraint on the input:

$$
1 \leq arr[i] \leq n
$$

In other words, the input consists of the numbers \$1, 2, 3, ..., n\$, shuffled.
Given such input,
you can produce a correct ordering in \$O(n)\$.
And as such, maybe sorting is not needed here after all.

This is still just a hint, without directly answering how to compute the minimum number of swaps.
But this observation must surely be part of the implementation.

(I suggest to stop reading here and try to come up with an algorithm that uses the above observation and implement a passing solution. Continue reading only if you need hints.)

Alternative algorithm

Consider this algorithm:

Build an array of indexes of the values in the input: indexes[arr[i] - 1] = i;.
Iterate over the input array, and when arr[i] != i + 1, then swap arr[i] with  arr[indexes[i]], and update the index of the original value of arr[i].

For example, for [7, 1, 3, 2, 4, 5, 6], the content of indexes would be [1, 3, 2, 4, 5, 6, 0] (indexes[7 - 1] = 0; indexes[1 - 1] = 1; indexes[3 - 1] = 2; ....

Then, the content of arr and indexes will go through these changes:

i       = 0; 7 != 1 so swap it with 1 (the element that belongs here)
arr     = [7, 1, 3, 2, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 0]

i       = 1; 7 != 2 so swap it with 2 (the element that belongs here)
arr     = [1, 7, 3, 2, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 1]

i       = 2; 3 == 3 so no swap
arr     = [1, 2, 3, 7, 4, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 3]

i       = 3; 7 != 4 so swap it with 4 (the element that belongs here)
arr     = [1, 2, 3, 4, 7, 5, 6]
indexes = [1, 3, 2, 4, 5, 6, 4]

And so on, two more swaps (total 5) and 7 reaches the end.

Bugs in questions

I don't recall ever finding a bug in an online puzzle (and that should always be the very last thought on your mind),
but this puzzle has one.
The 3rd sample input [1, 3, 5, 2, 4, 6, 8] (Testcase 14) violates the constraint \$1 \leq arr[i] \leq n\$. The 8 should be replaced with 7.
I worked around that by doing this when building indexes:

if (arr[i] > N) arr[i] = N;


Generating an array of school grades I have a catalogue of activities that are marked based on the age group that they are relevant to. There are 14 checkboxes for checking what grades. K, 1 - 12, and Adult. I have a switch statement to change the K and Adult to a numeric representation.

The following PHP code grabs the grades checked and displays them in consecutive groups.
Aka. K, 1, 2, 3, 5, 6, 7, 10, 11, Adult will display as K - 3, 5 - 7, 10 - Adult.

What I would like to ask is, is this a clumsy solution for my problem? Can I learn to make this more efficient or less prone to issues?

// generated through database, but set manually here for testing
$new_grades_array = array(K, 1, 2, 3, 5, 6, 7, 10, 11, Adult)

// grades related variables
$last = ""; // records previous grade in loop for checking consecutiveness
$display = ""; // concatenated display of results
$conseq = FALSE; // records if previous grade was consecutive

for ($i = 0; $i < count($new_grades_array); $i++):

     // set grade digit for K and Adult
     switch ($new_grades_array[$i]):
           case "K":
               $currentgrade_dig = 0;
               break;
           case "Adult":
               $currentgrade_dig = 13;
               break;
           default:
               $currentgrade_dig = $new_grades_array[$i];
     endswitch;

     // concatenates string to display variable based on situation
     if ($i == 0): // if the first grade listed

          $display = $new_grades_array[$i];

     elseif ($i +1 == count($new_grades_array)): //if the last grade listed

          if ($conseq != FALSE):
               $display .= " - " . $last . ", " . $new_grades_array[$i];
          else:
               $display .= ", " . $new_grades_array[$i];
          endif;

         $conseq = FALSE;

     elseif ($currentgrade_dig - $last ==1): // if consecutive number from previous
          $conseq = TRUE;

     else: // if not a consecutive number

          if ($conseq != FALSE):
               $display .= " - " . $last . ", " . $new_grades_array[$i];
               $conseq = FALSE;
          else:
               $display .= ", " . $new_grades_array[$i];
          endif;
     endif;

     $last = $new_grades_array[$i];

endfor;

print $display;

Here are some tips.

1) Have a function that returns the grade value.

This helps avoid duplicated code and increases readablilty.

Code:

function getGradeValue($val){
  switch ($val) {
  case "K":
    $val = 0;
    break;
  case "Adult":
    $val = 13;
    break;
  default:
  }
  return $val;
}

2) Create a function to retrieve the final output.

This allow for an easier way to test the overall functionality and helps to eliminate global variables.

3) Create unit tests to speed up testing

Simple Testcases:

function println( $str ){
  print( $str . "<br/>\n" );
}
function testThis( $arr, $expect ){
  $result = getGroupedGradesAsString( $arr );
  if( $result == $expect ){
    println( "Passed:" );
  }else{
    println( "Fail:" . $result . " != " . $expect );
  }
}
testThis( array("K", 1, 2, 3, 5, 6, 7, 10, 11, "Adult"), "K - 3, 5 - 7, 10 - 11, Adult" );
testThis( array("K"),  "K" );
testThis( array("K", "Adult"),  "K, Adult" );
testThis( array("K", 1, 2, 7, 11, 12), "K - 2, 7, 11 - 12" );
testThis( array( 6, 7, 8), "6 - 8" );
testThis( array("K", 2, 4, 6, 8, 10, 12), "K, 2, 4, 6, 8, 10, 12" );
testThis( array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, "Adult"),  "1 - Adult" );

4) Use a loop to find the last consistent number.

Refer to getGroupedGradesAsString() in the final code for more information.

Final Code:

<?php
// By Larry Battle [http://bateru.com/news/]
function getGradeValue($val){
  switch ($val) {
  case "K":
    $val = 0;
    break;
  case "Adult":
    $val = 13;
    break;
  default:
  }
  return $val;
}
function getGroupedGradesAsString($arr) {
  $output = "";
  for ($i = 0, $len = count($arr); $i < $len; $i++) {
    $output .= (($i) ? ", " : "" ) . $arr[$i];
    if( getGradeValue($arr[$i]) == getGradeValue($arr[$i+1])-1 ){
      do{
        $i++;
      }while( getGradeValue($arr[$i]) == getGradeValue($arr[$i+1])-1);
      $output .= " - " . $arr[$i];
    }
  }
  return $output;
}
?>

Demo here: http://codepad.org/zi8oavlv

Here's a shorter version but might be a litter bit harder to understand.

<?php
    // By Larry Battle [http://bateru.com/news/]
function getGradeValue($val){
    return ( $val == "K" || $val == "Adult" ) ? (($val == "K") ? 0 : 13 ) : $val;
}
function getGroupedGradesAsString($arr) {
  $output = "";
  for ($i = 0, $len = count($arr); $i < $len; $i++) {
    $output .= (($i) ? ", " : "" ) . $arr[$i];
    if( getGradeValue($arr[$i]) !== getGradeValue($arr[$i+1])-1 ){
        continue;
    }
    while( getGradeValue($arr[++$i]) === getGradeValue($arr[$i+1])-1);
    $output .= " - " . $arr[$i];
  }
  return $output;
}
?>


Exception Handling Design I am trying to design an exception hierarchy for logging errors.
These logs will be used only by developers and not by users.
This is a base class that I came up with.

#ifndef TSTRING_TYPEDEF
#define TSTRING_TYPEDEF
    typedef std::basic_string <TCHAR> tstring ;
#endif
struct BaseException // Derive from some standard exception
{
BaseException () ;
BaseException (const tstring &strWhat) ;
BaseException (const tstring &strWhat, const unsigned long ulErrorcode) ;

// ...Omitted functions here

void AddDetail (const tstring &strWhat) ;
void AddDetail (const tstring &strWhat, const unsigned long ulErrorcode) ;
tstring GetErrorString () const ;

private:
bool m_bValidErrorCode ;
std::vector <tstring> m_vecDetails ;
unsigned long m_ulErrorCode ;
};

The idea is that an inner function will not always have all the necessary details needed to give useful debugging information, so an inner function will load up an exception with whatever details it can and then throw the exception. The exception will be caught where it can be handled and more information may be added.

The error code will usually just be whatever ::GetLastError() returns (if applicable).

Please note that I won't be catching/wrapping bad alloc calls with this, so I'm not worried about making heap allocations with string and vector.

My questions:

I've been searching online for exception class design, and haven't found anything like this. This worries me. Is there something wrong with designing exceptions this way?
Are there any considerations to think about when deriving from one of the standard exceptions? Or should I just derive from std::exception and not worry about?
One problem with this design is that the format of the string is dependent on this class. Is there any good way to decouple this?

For example, let's a say we have files like this:

MainProcess.h

class MainProcess
{
public:
    // ctors, dtor, functions, etc...
private:
    Config m_config ;
    // ...
};

Config.h

class Config
{
public:
    // ctors, dtor, etc...
std::string ReadValue (const tstring &strFile, const tstring &strSection,
    const tstring &strKey, const bool bRequired = true,
    const tstring &strDefault = _T ("")) const ;

void WriteValue (const tstring &strFile, const tstring &strSection,
    const tstring &strKey, const tstring &strValue) const ;
};

class ConfigReadException // Derive from something
{
// ctors, dtor, etc...
private:
tstring strFile ;
tstring strSection ;
tstring strKey ;
tstring strDefault ;
};

class ConfigWriteException // Derive from something
{
// ctors, dtor, etc...
private:
tstring strFile ;
tstring strSection ;
tstring strKey ;
tstring strValue ;
};

In this case, these ConfigExceptions provide only relevant data and no specific format. But if we do this, then we may end up having to catch many different kinds of exceptions that would clutter our code.

Is it a better practice to have exception classes similar to BaseException or is it better to have exception classes to similar to ConfigReadException and ConfigWriteException, or is there a middle ground?

1) I've been searching online for exception class design, and haven't found anything like this. This worries me. Is there something wrong with designing exceptions this way?

Here is my opinion: What is a 'good number' of exceptions to implement for my library?

  2) Are there any considerations to think about when deriving from one of the standard exceptions? Or should I just derive from std::exception and not worry about?

You should probably derive from std::runtime_error.

  3) One problem with this design is that the format of the string is dependent on this class. Is there any good way to decouple this?

Use the string in the exception solely for logging (not for generating a user error message). The exception will generally carry technical information that is not relevant to the user.

But when displaying information to the user you should generate a formatted string at the catch point (not the throw point). This is because you can not tell what the output device is going to be used at the throw point.


Assigning entire column of data to specific column of an array in VBA The below code I have written is to allow me to Sum the results data for every year from 1 to 1000 over a range of 5000 locations. although a 1000 years seems extreme, for the application I am using this makes sense. Column K in the Class Calculation Sheet calculates the Data size for every year for a specific class. I have created the classArray so that the value in D1, which is where the class is defined, can be updated without having to switch back to the original results sheet where the classes are initially defined.

The Script as it stands works, but takes a very long time to run. I am dealing  with 1000 rows and roughly 5000 columns. I have defined the array "arr" which contains the Data size for every year for every class. This 2D array is basically every iteration of column K in the "Class Calculation Sheet" next to each other. At the moment it adds them together row by row as can be seen in the part of code that reads

'creates array of column of Data sizes

 arr(i, r) = ws1.Cells(6 + i, 11)

I was wondering if it is possible to assign the entire column "K" to a specific column within the pre defined array of pre defined size? This would mean that the code does not need to iterate through the 1000 rows, only the 5000 columns.

I realise this is a long winded explanation so please let me know if further clarification is required.

Sub UpdateData()

'Speed
Application.ScreenUpdating = False
Application.DisplayStatusBar = False
Application.EnableEvents = False
ActiveSheet.DisplayPageBreaks = False

Dim ws1 As Worksheet
Dim ws2 As Worksheet
Dim ws3 As Worksheet
Dim lastcol3 As Integer
Dim classArray As Variant
Dim numRows As Integer
Dim i As Long
Dim r As Long
Dim j As Long
Dim k As Long
Dim arr

Set wb = ThisWorkbook

Set ws1 = wb.Worksheets("Class Calculation Sheet")
Set ws2 = wb.Worksheets("Data")
Set ws3 = wb.Worksheets("Results")

'MANUAL
Application.Calculation = xlCalculationManual

'Number of Rows of data to be entered
numRows = 1000

'Gives value for number of columns of data to be entered
lastcol3 = ws3.Cells(4, ws3.Columns.Count).End(xlToLeft).Column - 1

'Defines 2 dimensional array
ReDim arr(1 To numRows, 1 To lastcol3)

'creates array from list of classes
classArray = ws3.Range(ws3.Cells(4, 2), ws3.Cells(4, lastcol3 + 1))

'AUTO
Application.Calculation = xlCalculationAutomatic

    For r = 1 To lastcol3

    'Makes value in D1 in Class calculation sheet equal to the Class name
    ws1.Range("D1") = classArray(1, r)

    'MANUAL
    Application.Calculation = xlCalculationManual

        For i = 1 To numRows

        'creates array of column of Data sizes
        arr(i, r) = ws1.Cells(6 + i, 11)

        Next

    'AUTO
    Application.Calculation = xlCalculationAutomatic

    Next

    'MANUAL
    Application.Calculation = xlCalculationManual

    For k = 1 To lastcol3

        For j = 1 To numRows

        If arr(j, k) = 15 Then
        ws2.Cells(6 + j, 4) = 1 + ws2.Cells(6 + j, 4)
        ElseIf arr(j, k) = 28 Then
        ws2.Cells(6 + j, 5) = 1 + ws2.Cells(6 + j, 5)
        ElseIf arr(j, k) = 50 Then
        ws2.Cells(6 + j, 6) = 1 + ws2.Cells(6 + j, 6)
        End If

        Next

    Next

    'AUTO
    Application.Calculation = xlCalculationAutomatic

'Speed
Application.ScreenUpdating = True
Application.DisplayStatusBar = True
ApplicationEnableEvents = True
ActiveSheet.DisplayPageBreaks = True

End Sub

First things first, your variables. The names aren't great. For the ws1 to ws3 you're using numbers, which should tell you it's not specific enough or you aren't being effective with your variables.

Worksheets have a CodeName property - View Properties window (F4) and the (Name) field can be used as the worksheet name. This way you can avoid Sheets("Data") and instead just use Data.

Also lastcol3 - what's that? lastColumn? Why the 3, also you missed camelCase on that one. Standard VBA naming conventions have camelCase for local variables and PascalCase for other variables and names. You could just call it resultsLastColumn instead.

i,r,j,k - these are counters right?

r - currentColumn. i,j,k are acceptable, but personal preference I like to avoid those.

Dim arr - When you don't define your variable, VBA will declare it as a Variant, which are objects:

Performance. A variable you declare with the Object type is flexible enough to contain a reference to any object. However, when you invoke a method or property on such a variable, you always incur late binding (at run time). To force early binding (at compile time) and better performance, declare the variable with a specific class name, or cast it to the specific data type.

By not declaring variables, you could possibly be paying a penalty.

In this case, it is a variant, but it's good to note for the future. It should have a more descriptive name, though.

lastColumn and numRows are integers - Integers - integers are obsolete. According to msdn VBA silently converts all integers to long.

Additionally, your numRows is set to 1000 and never changed. Why not

Const NUMBER_OF_ROWS As Long = 1000

Your indenting is non-existent.
It's good practice to indent all of your code that way Labels will stick out as obvious.

Always turn on Option Explicit. You can have it automatically by going to Tools -> Options in the VBE and checking the Require Variable Declaration option. This way if you have any variables not defined, the compiler will let you know. In this case your variable wb isn't defined.

You use Application.Calculation a lot. You set it to Manual and do some stuff, then set it to Automatic. Then you loop up to 5000 times in your r loop turning it manual and back to automatic. None of that is needed. The calculations you're doing in VBA aren't affected by the worksheet calculation. I don't know what kind of resources that's using, but I can't imagine it's helping.

Comments - "code tell you how, comments tell you why". The code should speak for itself, if it needs a comment, it might need to be made more clear. If not, the comment should describe why you're doing something rather than how you're doing it. Here are a few reasons to avoid comments all together.

ActiveSheet.DisplayPageBreaks = False - this will only work on the active sheet, what if the sheet isn't active. Why not tell it which sheet to do it on?

Also your last Application.EnableEvents is missing the ..

I don't quite understand this line

ws1.Range("D1") = classArray(1, r)

Does this need to move down column D with the class names?

With your arr array

ReDim arr(1 To NUMBER_OF_ROWS, 1 To resultsLastColumn)
For r = 1 To resultsLastColumn
    ws1.Range("D1") = classArray(1, r)
    For i = 1 To NUMBER_OF_ROWS
        arr(i, r) = ws1.Cells(6 + i, 11)
    Next
Next
For k = 1 To resultsLastColumn
    For j = 1 To NUMBER_OF_ROWS
        If arr(j, k) = 15 Then
            ThisWorkbook.Data.Cells(6 + j, 4) = 1 + ThisWorkbook.Data.Cells(6 + j, 4)
        ElseIf arr(j, k) = 28 Then
            ThisWorkbook.Data.Cells(6 + j, 5) = 1 + ThisWorkbook.Data.Cells(6 + j, 5)
        ElseIf arr(j, k) = 50 Then
            ThisWorkbook.Data.Cells(6 + j, 6) = 1 + ThisWorkbook.Data.Cells(6 + j, 6)
        End If
    Next
Next

This is pretty inefficient. Why not just pull everything into the array and do the sorting in it, rather than on the sheet. That will be quicker.

arr = Data.Range(Cells(1, 6), Cells(NUMBER_OF_ROWS, resultsLastColumn))

Now you can loop with your j and k in the arr or just eliminate k and reuse i.

So at the very least, you'll have this

Option Explicit
Private Sub UpdateData()

    Application.ScreenUpdating = False
    Application.DisplayStatusBar = False
    Application.EnableEvents = False
    ActiveSheet.DisplayPageBreaks = False
    Application.Calculation = xlCalculationManual

    Const NUMBER_OF_ROWS As Long = 1000
    Dim resultsLastColumn As Integer
    Dim classArray As Variant
    Dim i As Long
    Dim j As Long
    Dim k As Long
    Dim arr As Variant

    resultsLastColumn = Results.Cells(4, Results.Columns.Count).End(xlToLeft).Column - 1
    ReDim arr(1 To NUMBER_OF_ROWS, 1 To resultsLastColumn)
    classArray = Results.Range(Results.Cells(4, 2), Results.Cells(4, resultsLastColumn + 1))

    ClassCalculationSheet.Range("D1:D" & resultsLastColumn) = classArray()

    arr = Data.Range(Cells(1, 6), Cells(NUMBER_OF_ROWS, resultsLastColumn))
    For j = 1 To resultsLastColumn
        For i = 1 To NUMBER_OF_ROWS
            If arr(i, j) = 15 Then
                Data.Cells(6 + j, 4) = 1 + Data.Cells(6 + i, 4)
            ElseIf arr(i, j) = 28 Then
                Data.Cells(6 + j, 5) = 1 + Data.Cells(6 + i, 5)
            ElseIf arr(i, j) = 50 Then
                Data.Cells(6 + j, 6) = 1 + Data.Cells(6 + i, 6)
            End If
        Next
    Next

    Application.Calculation = xlCalculationAutomatic
    Application.ScreenUpdating = True
    Application.DisplayStatusBar = True
    Application.EnableEvents = True
    ActiveSheet.DisplayPageBreaks = True

End Sub

Some tweaking might be needed as I can't run the macro to see what needs adjusting.


Largest substring which starts and ends with some substring This code is meant to find the length of the largest substring within a string that starts and ends with a given non-empty substring. Here are some examples:

strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9

This is based off this question.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def strDist(string, sub):
    if len(string) < len(sub):
        return 0
    elif string[0:len(sub)] == sub and string[-len(sub):] == sub:
        return len(string)
    elif string[0:len(sub)] == sub and string[-len(sub):] != sub:
        return strDist(string[:-1], sub)
    elif string[0:len(sub)] != sub and string[-len(sub):] == sub:
        return strDist(string[1:], sub)
    elif string[0:len(sub)] != sub and string[-len(sub):] != sub:
        return strDist(string[1:-1], sub)

While the original question said that this should be done recursively, I would also be interested to see if there are any nice non-recursive ways of doing this. Also, let me know if a recursive or non-recursive approach would be preferable in an interview (assuming the question wasn't restricted to doing it recursively).

I think this algorithm is O(n) time complexity but O(n^2) space complexity. Correct me if I'm wrong. Also, any suggestions about how to improve complexities are welcome.

You should use str.startswith and str.endswith and avoid reinventing them with list slicing.

The conditions can be simplified: if the string does not start with the substring remove the first char if it does not end with the substring remove the last.

Space complexity can be reduced by passing indexes to the recursive invocations instead of copies of the string.


Use of pointers with file-reading program I'm working on a school assignment, and it's working fine, but I have a feeling I'm over-using pointers, and I just can't think of a way to not pass a triple pointer to the function readFile.

I'd be more than grateful for your suggestions, and if you have any other suggestions on how to improve my code I'd be glad to hear those too!

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

#define handle_error(message) \
    do { perror(message); exit(EXIT_FAILURE); } while(0)
int readFile(char ***names, FILE *file, int *size);
void *_realloc(void *ptr, size_t size);

int main(void) {
    char **names;
    int names_size;
    FILE *file;
    int chars_read;
    int i;

    names = NULL;
    file = NULL;
    names_size = 0;
    chars_read = 0;

    file = fopen("names", "r");
    readFile(&names, file, &names_size);
    printf("%s\n", names[0]);
    fclose(file);
    return EXIT_SUCCESS;
}

int readFile(char ***names_p, FILE *file, int *size) {
    int chars_read;
    int line;
    int chunk_size;
    int name_size;
    int name_length;
    char cur_char;
    char **names;
    char *name;

    name = NULL;
    names = NULL;
    line = 0;
    name_length = 0;
    name_size = 0;
    chunk_size = 2;
    chars_read = 0;
    while((cur_char = fgetc(file)) != EOF && cur_char != '\r'){
        if(cur_char == '\n') {
            if(name_size > 0) {
                names = _realloc(names, sizeof(char*) * (line+1));
                names[line] = _realloc(name, name_length + 1);
                names[line][name_length] = '\0';
                name_size = 0;
                name_length = 0;
                name = NULL;
                line++;
        }
    } else {
            if(name_size < name_length + 1) {
                name = _realloc(name,
                    sizeof(char) * (name_size =
                    (name_size + 1) * chunk_size));
            }
            name[name_length] = cur_char;
            name_length++;
        }
        chars_read++;
    }
    *names_p = names;
    *size = line;
    return chars_read;
}

void *_realloc(void *ptr, size_t size) {
    void *temp = realloc(ptr, size);
    if(temp == NULL) {
        int error = errno;
        if(error == ENOMEM) printf("size: %d\n", error);
        handle_error("realloc");
    }
    return temp;
}

1. Introduction

You'll see that I made a lot of comments below, but if you're just starting to learn C, then your code is not at all bad. C is a tough language to write robust code in: it provides many many ways to go wrong, and even the most expert and experienced programmers don't always succeed in avoiding the traps and pitfalls.

I like your attention to error handling, that you check the result of realloc, that you remember to close your file handle, and that you use the symbols EXIT_SUCCESS and EXIT_FAILURE to make it clear what you mean.

2. Bugs

You don't check whether there were in fact any names in the file before printing the first of them. If the file was empty then this would result in undefined behaviour:

$ clang cr27281.c
$ cat /dev/null > names
$ ./a.out
Segmentation fault: 11

You don't check the result of fopen. If this call failed then you'd end up trying to read from the file handle NULL:

$ rm names
$ ./a.out
Segmentation fault: 11

3. Other comments on your code

If you need to return multiple values from a function, then why not use a structure? You could declare a structure like this:

typedef struct name_array_s {
    char **names;         /* Array of names, allocated with malloc. */
    size_t count;         /* Count of names in the 'name' array. */
} *name_array_t;

and then readFile could take a name_array_t as its first argument.
There's no comment or documentation explaining the interface to readFile. What is this function supposed to do and how are you supposed to call it? Imagine coming back to this code in a couple of years' time when you have forgotten all about it. Do you really want to have to reverse-engineer it to figure out what it does?
The variable names_size is an int, but it counts the number of entries in the names array and it can never legitimately be negative. And there are common platforms where INT_MAX is 2147483647, but where you have enough memory to store many more objects than that. So why not make names_size a size_t?
Similarly for the result of the function readFile.
Consider using abort() in your error handler instead of exit(EXIT_FAILURE). When running under the debugger, abort() drops you straight into the debugger prompt with a good chance of being able to find useful information in the backtrace, but exit() just quits the program, leaving you none the wiser.
It's a bit restrictive that the file has to be named names. Why not take the name on the command line in argv[1]?
This line:

if(error == ENOMEM) printf("size: %d\n", error);

has four problems! First, error messages should go to standard error, not (as here) standard output, so you need fprintf(stderr, ...). Second, you want size instead of error in the call to printf. Third, size is a size_t but you are using a %d format specifier which takes an int, so this results in undefined behaviour. Fourth, by putting the if and the printf on the same line, you've made it impossible (in most debuggers) to set a breakpoint on the printf. I would write:

if(error == ENOMEM)
    fprintf(stderr, "size: %lu\n", (unsigned long)size);

The C language allows you to combine the declaration of a variable and its initialization, so instead of writing the repetitive

char **names;
int names_size;
FILE *file;
int chars_read;
int i;

names = NULL;
file = NULL;
names_size = 0;
chars_read = 0;

you can write

char **names = NULL;
int names_size = 0;
FILE *file = NULL;
int chars_read = 0;
int i;

After making the change above, it becomes obvious that the variable i is unused. But shouldn't your compiler have complained about that? When writing a new program it's well worth turning on as many error-detecting features as you can, for example if you're using GCC it's a good idea to use a comprehensive set of flags like -ansi -pedantic -std=c99 -Wall -Werror.
The variable chars_read is also unused.
Having an assignment buried inside an expression seems error-prone and hard to understand (especially when broken across lines like this):

name = _realloc(name,
    sizeof(char) * (name_size =
    (name_size + 1) * chunk_size));

I prefer to keep the code simple:

name_size = (name_size + 1) * chunk_size;
name = _realloc(name, sizeof(char) * name_size));

sizeof(char) is defined to be 1 by the C standard, so you don't need it here (it doesn't do any harm, though).

  §6.5.3.4.3 When [sizeof is] applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1.

chunk_size is poorly named: it's not a size, it's an exponent that controls the exponential growth of the name buffer.

4. Performance

Your algorithm for allocation involves reallocating the names array each time a new line is reached in the file. This is wasteful, because each time this array is reallocated, the contents may have to be copied across to the new region of memory, potentially making it O(n2).

If your files are short then you may prefer not to worry about this, but after I did a simple rewrite of your readFile function to do less reallocation, I was able to get a speedup of more than 3× in test cases with many lines, like this one:

$ yes '' | head -10000000 | nl -ba > names
$ time ./names-old > /dev/null
real    0m4.136s
user    0m3.777s
sys     0m0.333s
$ time ./names-new > /dev/null
real    0m1.248s
user    0m0.946s
sys     0m0.287s


Project Euler 407: Is there any more optimal way to solve this idempotent equation (modulo n ring)? Project Euler problem 407:

  If we calculate a2 mod 6 for 0 ≤ a ≤ 5 we get: 0, 1, 4, 3, 4, 1.

  The largest value of a such that a2 mod 6 = a is 4.
  Let's call M(n) the largest value of a < n such that a2 mod n = a.
  So M(6) = 4.

  Find ΣM(n) for 1 ≤ n ≤ 107.

So far, this is what I have:

import time
start = time.time()
from math import sqrt

def primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(sqrt(n))+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

tot=0

gor = primes1(10000000)

def factor1(n):
    '''Returns whether a number has more than 1 prime factor'''
    boo = False

    '''if n in gor:
        return True'''

    for e in xrange(0,len(gor)):

        z=gor[e]

        if n%z==0:

            if boo:
                return False
            boo = True
        elif z*2>n:
            break
    return True

for n in xrange(2,10000000):

    if factor1(n):

        tot+=1
    else:
        for a in xrange(int(sqrt(n))+1,n/2+1):
            if (a*a)%n==a:

                tot+=n+1-a
                break

print tot
print time.time()-start

I've tried this code for smaller cases and it works perfectly; however, it is way too slow to do 10^7 cases.

Currently, for n being less than 20000, it runs in about 8 seconds.
When n is less than 90000, it runs in about 150 seconds.

As far as I can tell, for n is less than 10^7, it will run for many hours if not days.

I'm already using the sieve to generate prime numbers so that part is as fast as it can be, is there anything I can do to speed up the rest of the code?

I've already tried using different compiler like psyco, pypy, and shedskin. Psyco provides a minimal increase, shedskin speeds it up about 7 times but creates errors when large numbers occur, pypy speeds it up the most (about 20-30x the speed). But even then, it's still not fast enough for the amount of cases it has to go through.

1. Introduction

The feature of Project Euler that makes it interesting is that solving the problems is rarely a matter of writing down a straightforward algorithm and then optimizing it piecewise until it runs in the available time.

Instead, the problems are deliberately designed with parameters large enough that the straightforward algorithm will take many hours or days, but if you can gain some insight into the mathematical structure of the problem, then you can find a better algorithm that radically improves the runtime.

So if you're still at the "hours or days" stage then it's no good trying to speed up the code you've got. You might be able to speed it up by a factor of five or ten by piecewise optimizations, but probably no more than that. No, I'm afraid we need to use ... math.

2. Getting started

But what if you've already applied all the math you know, and you're too impatient to read a number theory textbook? How do you figure out where to look?

First, it's worth working your way through the Project Euler problems at least approximately in order, rather than diving straight in to the latest problems. The earlier problems often introduce key concepts (for example, Euler's totient function and how to compute it simultaneously for many numbers by sieving) in straightforward contexts, so that when in later and harder problems these concepts are needed, you'll already be familiar with them.

Second, many Project Euler problems involve at their heart a sequence of numbers. You can very often get useful clues about this sequence by computing the first few numbers in the sequence and then searching for them in the On-Line Encyclopedia of Integer Sequences.

In the case of problem 407, the first few elements of the sequence are 0, 1, 1, 1, 1, 4, 1, 1, 1, 6, and this is sequence A182665, which contains a link to this answer by Robert Israel on math.stackexchange.com.

3. Computing the sequence

(This follows Robert Israel's presentation, but with the notation changed to match the Project Euler problem.)

If \$a^2 \bmod n = a\$, then \$a(a − 1) \bmod n = 0\$.

So if \$n\$ can be factored as \$p_1^{e_1} p_2^{e_2} \ldots\$ then each \$p_i^{e_i}\$ must divide either \$a\$ or \$a − 1\$ (because each \$p_i\$ can divide into at most one of \$a\$ and \$a − 1\$).

Therefore \$n = uv\$, where \$u\$ and \$v\$ are coprime and \$u\$ divides into \$a\$ and \$v\$ divides into \$a − 1\$.

Let \$a = uw\$. Since \$a < n\$ then \$w < v\$ and \$uw = 1 \pmod v\$ therefore \$w = u^{−1} \pmod v\$.

So our plan, in pseudocode, is:

Factorize all the integers up to \$10^7\$ by sieving.
For each integer \$n\$:
  if \$n\$ is a prime or prime power, then \$a = 1\$;
  otherwise \$n\$ is a product of two or more distinct primes, so:
    for each way to factorize \$n = uv\$ with \$u\$, \$v\$ coprime:
      find \$w = u^{−1} \bmod v\$.
    \$a\$ is the maximum of \$uw\$ for all such \$uv\$.

Which might just be doable in the time available.

Now at step 6 we have to find the multiplicative inverse of \$u\$ modulo \$v\$. There are a couple of algorithms for finding the modular multiplicative inverse: normally we would use the extended Euclidean algorithm, but here the method using Euler's theorem is attractive because we know that \$u\$ is coprime to \$v\$. So \$u^{−1} = u^{φ(v)−1} \pmod v\$ where \$φ\$ is Euler's totient function.

Since we are sieving for the factorizations, we can sieve for the totients at the same time.

4. Python code

This runs in about 2½ minutes on my computer under pypy, so I didn't manage to squeeze it inside Project Euler's one-minute time limit. But at this point we're within sight of the goal, so it might be possible to get there by carrying out piecewise optimizations.

from collections import defaultdict
from functools import reduce
from itertools import combinations
from operator import mul

def factorize(n):
    """Factorize the numbers up to n, returning a pair (factorization,
    totient).

    factorization is a dictionary mapping each composite i below n to
    a list of numbers p ** e where p is a prime and e is the exponent
    of p in the factorization of i.

    totient is a list whose i'th element is Euler's totient function
    applied to i (the count of numbers less than i which are coprime
    to i).

        >>> from pprint import pprint
        >>> f, t = factorize(10)
        >>> pprint((dict(f), t))
        ({4: [4], 6: [2, 3], 8: [8], 9: [9], 10: [2, 5]},
         [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4])

    """
    n = n + 1
    f = defaultdict(list)
    t = list(range(n))
    for p in range(2, n):
        if p not in f:
            t[p] = p - 1
            for i in range(p + p, n, p):
                j, k = i, 1
                while j % p == 0:
                    j //= p
                    k *= p
                f[i].append(k)
                t[i] = t[i] * (p - 1) // p
    return f, t

def problem407(n):
    """Generate a sequence whose i'th element is the largest a < i such
    that a**2 == a (mod i), where i runs from 1 to n (inclusive).

    """
    f, t = factorize(n + 1)
    yield 0 # i = 1
    for i in range(2, n + 1):
        if i not in f or len(f[i]) < 2:
            # prime or prime power
            yield 1
            continue
        def uw():
            for j in range(1, len(f[i])):
                for c in combinations(f[i], j):
                    u = reduce(mul, c)
                    v = i // u
                    w = pow(u, t[v] - 1, v)
                    yield u * w
        yield max(uw())


build multiple websites with yarn This is a Bash script that runs commands which builds code using the parameters given.
Code
The task:
I have multiple instances of websites which need to be build individually using individual yarn commands and then copied out of a build folder and placed into their own individual folder. I found this very repetitive and so I wanted to solve the problem using a script. I thought about using Python but I ended up using Bash.
Pseudocode:
Inputs: folder where the code is built, folder where the output code is stored, list of languages to run yarn build on.
For each language in input:
   Go to project/build
   Run "yarn build_language"
   Delete output/language folder
   Copy project/build to output/language folder

Here is my Bash implementation:
#!/bin/bash

# PROC Build and Copy:
#     Args:
#         1) Build directory
#         2) Output directory path (general)
#         3) List of language names

#     For each lang in list of language names:
#         Run appropriate build command
#         Delete output directory
#         Copy build directory to output directory/lang

if (( $# < 3 )); then
    echo "Please use at least 3 parameters"
    exit 2
fi

array=("$@")

readonly build_path=$1
readonly output_path=$2
languages=("${array[@]:2}")

build_command="yarn build_"

for lang in "${languages[@]}"
do
    cd "$build_path" || exit
    eval "${build_command}${lang}"
    cd ~- || exit
    output=${output_path}${lang}
    rm -rf "$output"
    mkdir -p "$output"
    cp -r "$build_path" "$output"
done

Sample usage: ./build_all.sh my_project/build/. environments/ python lua
Discussion
I found a style guide on Github and tried to follow it but this is my first Bash script so I am not sure if I followed a good style. I am a Python developer and I fear I may have written a Python-script in Bash. I am also not sure if Bash is the best way to implement this type of script. I wanted to make this re-usable by pulling the directories out into parameters, but I decided not to have the yarn command as a parameter as I thought it could be confusing having lots of parameters. Are my assumptions justified, or do they make the code confusing?

Language choice
A lot of your commentary on this code revolves around whether bash is a good choice for this project.  I would say, yes, it is a good choice.  You have shell commands, and you want to make a bit of a wrapper around them.  That's a perfect use case for shell, even with so many more recent choices available.
A related concern that you raised is

I am a Python developer and I fear I may have written a Python-script in Bash.

Yeah, maybe, a bit.  But that's life in coding.  Everything you do is going to be influenced by previous languages you've been exposed to.  Most shell programs don't involve arrays, but there's nothing wrong with you taking advantage of unpopular features.  I will talk about making this like native shell in the review below.
Code review

Your use of indentation and quoting is excellent.
Nice variables names.  Yay for copying the command line arguments into named variables.
Your style guide seems like a reasonable choice although I just skimmed it.  I've liked Google's style guide and shellcheck.  Shellcheck is a linter so it could be used in your CI pipeline.
I like that you exit after some commands that could fail.  It would be nice from the calling perspective if you used distinct exit codes.  It would also be a good idea to check that rm, mkdir and cp succeeded.
Did you try it without evaling the command?  I didn't try it, but I'm guessing you can skip the eval.
So, back to the arrays being unusual in a shell script... The shell will split a string into arguments if they are separated by spaces.  You could make languages be a long space-delimited string and not worry about turning it into an array.  The for loop would become for lang in $languages; do and the shell would give you one at a time.  It also works your way and it should be decipherable to folks who aren't used to arrays in the shell, so I wouldn't worry about it.
The if at the top would usually be expressed like if [[ "$*" < 3 ]].  Your way is fine.  The (( )) tells the shell to "do math in here" and that works here, but you might want to do string comparisons or check file existence.  Then you'll need the [[ ]].


Iteratively determine the diameter of a binary tree Can the performance of the iterative approach be improved? I find that this approach lags behind many recursive options. no recursive answers, please.

Baseline recursive approach: takes 52 steps for this sized tree O(N) for every nested input each object is only touched once.

function diameterOfBinaryTree(root) {
  return diameterInternal(root).diameter;
};

function diameterInternal(root) {
  if (root == null) {
    return {
      diameter: 0,
      depth: 0
    }
  }
  let left = diameterInternal(root.left);
  let right = diameterInternal(root.right);
  let diameter = left.depth + right.depth;
  return {
    diameter: Math.max(diameter, left.diameter, right.diameter),
    depth: Math.max(left.depth, right.depth) + 1
  };
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

Iterative approach: takes 85 steps. However, the number of steps will double as the branches become more nested. That's because as you walk the nodes, they are walked in trios. Counting the roots while unpacking the right and left side. Culminating the counts on every retrograde unpacking, while passing every root object more than once. time complexity is O(N^2) for every nested object added it will be touched twice, once on entering and a second time on exiting.

function diameterOfBinaryTree(root) {
  let stack = [
    [1, root]
  ];
  let d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let [indicator, node] = [...stack.pop()];
    if (indicator) {
      let place = 0,
        extend = [];
      extend[place++] = [0, node]
      if (node.right !== null) {
        extend[place++] = [1, node.right]
      }
      if (node.left !== null) {
        extend[place++] = [1, node.left]
      }
      stack.push.apply(stack, extend);
    } else {
      let left = d.get(node.left) + 1 || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

Tail calls
You have to be careful when evaluating recursive functions as there is a big difference between recursion that is tail called, and those that are not.
As the problem requires a traverse back up the tree after locating an end node the tail of the recursive function should count as an iteration.
The upward traverse
The solution to the problem requires you to traverse down the nodes until you find the end node, counting the depth as you go. When you find an end node you then traverse back until you find a node with an un-traversed node. Each step back you record the max depth from that node.
Because the non iterative version requires you to push the current node to the stack so you can travel back up the tree you are counting what the recursive function is doing after the recursion (the tail).
Basics of tail calls
A tail call is a call made at the end of a function.
Many languages allow proper tail calls, which means that a tail called function does not need to push its current state to the call stack when it makes the recursive call, and thus there is no need to pop from the call stack when returning.
Consider the following two recursive functions.
Proper tail call recursion

function recurse(sum, value){
    sum += value;
    if(value > 10) { return sum }   // Returns functions state.sum
    return recurse(sum, value + 1); // Returns function call result
    // the functions state is not required after the recurse call.
}

console.log(recurse(0,0));

Non tail call recursion

function recurse(sum, value){
    if(value > 10) { return sum + value }
    sum +=  recurse(value, value + 1); // Note that the function state
                                       // that holds sum must be retained
                                       // in order to complete the function
    return sum;  // Return function state variable
}

console.log(recurse(0,0));

The two functions return the same result, but the second function requires an additional 10 pops from the call stack.
Javaascript ES6 currently does support proper tail calls and optimization, however no engine has yet released support (too many pages rely on call stack overflow to save them from infinite recursion)
Do call stack pops count?
I do not know what the official stance is on the complexity of recursive tails. Having proper tail calls make a huge performance difference and some types of problems can not be implemented using proper tail calls so I would count them as iterations.
If you count the tail call (the pop from the call  stack) as an iteration then your recursive function has the same number of iterations as the non recursive function.
As far as i can tell the solution can not be implemented using proper tail call recursion and thus the complexity should include both sides of the recursion call to be counted as an iteration.

var count = 0;
const nullReturn = {diameter: 0, depth: 0};
function diameterOfBinaryTreeA(root) {
  count = 0;
  const diameter = diameterInternal(root).diameter;
  console.log("Iterations : " + count);
  return diameter;
};

function diameterInternal(node) {
  count += 1;
  const left = node.left ? diameterInternal(node.left) : nullReturn;
  const right = node.right ? diameterInternal(node.right) : nullReturn;
  count += 1;
  const diameter = left.depth + right.depth;
  return {
    diameter: Math.max(diameter, left.diameter, right.diameter),
    depth: Math.max(left.depth, right.depth) + 1
  };
}

function diameterOfBinaryTreeB(root) {
  count = 0;
  const stack = [[1, root]];
  const nodeDepth = new WeakMap();
  let diameter = 0;
  while (stack.length) {
    count += 1;
    const [indicator, node] = stack.pop();
    if (indicator) {
      stack.push([0, node]);
      if (node.right) { stack.push([1, node.right]) }
      if (node.left) { stack.push([1, node.left]) }
    } else {
      const left = nodeDepth.get(node.left) + 1 || 0;
      const right = nodeDepth.get(node.right) + 1 || 0;
      nodeDepth.set(node, Math.max(left, right));
      diameter = Math.max(diameter, left + right);
    }
  }
  console.log("Iterations : " + count);
  return diameter;
}

let tree = {
  val: 3,
  right: {
    val: 20,
    right: {
      val: 7,
      right: null,
      left: null
    },
    left: {
      val: 15,
      right: null,
      left: null
    }
  },
  left: {
    val: 9,
    right: null,
    left: null
  }
}

console.log("Using recursion");
console.log("Diameter : " + diameterOfBinaryTreeA(tree))
console.log("Using Stack");
console.log("Diameter : " + diameterOfBinaryTreeB(tree))

Additional notes.
See above snippet for fixes as to the points below.

Use const for constants. You had many variables that were not being changes as let
When using recursive functions terminate the recursion before that call. If you have a recursive function and the first thing you do is check for a immediate return you are wasting a whole stack push and pop.
Don't forget to put ; at the end of lines.
Only use strings for property names if they are not valid names.
Keeping the extend array and place are not needed, just push the nodes directly to the stack.
if (node.left !== null) { is noisy if you know foo is either an object or null use if (node.left) {
Try to avoid non descriptive names, or use common abbreviations. d is not a good name for the map.


Speeding up prime factorization I have written the following code for returning the list of prime factors.  Any speed-enhancing suggestions?

import math
def is_prime(num):
    for n in range(2,math.floor(math.sqrt(num)+1)):
        if num%n==0:
            return False
    return True

def find_prime_factors(num):
    primes=[]
    for n in range(2,math.floor(num/2)+2):#The maximum value of the factor could only be half of the number
        if is_prime(num):
            primes.append(math.floor(num))
            break
        if is_prime(n) and num %n==0:
            num=num/n
            primes.append(n)
            while num%n ==0:
                num=num/n
                primes.append(n)

    return(primes)

Correctness

1 is not a prime factor:

>>> find_prime_factors(25)
[5, 5, 1]

Performance

Primality testing is expensive.  You call is_prime() twice on every iteration of the main loop of find_prime_factors().  Furthermore, is_prime() performs trial division in much the same way that find_prime_factors() does, resulting in redundant work.


MySQL JOIN to JSON array I'm building a HTTP API and this part should return a JSON list of posts and their attached photos, like this:

[
    {
        "id": "788",
        "content": "Foo bar! Foo foo, bar bar.",
        "photos": [181, 282, 182]
    },
    ...
]

And this is my PHP code handling the request:

// get all the posts and their photos
$st = $db->prepare ('SELECT * FROM `posts` ' .
                    'LEFT JOIN `photos` ON `photo_post` = `post_id`');
$st->execute ();

// init our results array
$posts = array ();

// get the first post (plus it's JOINed photo)
$row = $st->fetch (PDO::FETCH_OBJ);
// if there's more left
while (false !== $row) {
    // init our post array
    $post = array (
        'id' => $row->id,
        'content' => $row->content,
        'photos' => array ()    // to fill with the photos
    );
    do {
        // don't add a `null` if there's no photos
        if (null !== $row->screenshot)
            $post ['photos'] [] = $row->photo_id;
    // get the row, repeat if it's another photo
    } while (false !== ($row = $st->fetch (PDO::FETCH_OBJ)) &&
             $row->id === $post ['id']);

    // add this post to the list
    $posts [] = $post;
}

// and send it back
echo json_encode ($posts);

Pretty simple JOIN parsing job, right?  But the code is anything but nice or simple!

How can I parse MySQL's JOIN results elegantly into the JSON heirarchy that I need?

This is not vastly different but you might think its a little easier to read and follow and probably therefore debug.

With this code everything can be done within a single loop rather than the more complex multiple loop while/do that you originally used.

This also makes use of the stdClass provided by PHP to generate an array of objects as per your requirement, where your code was creating an array of arrays.

// get all the posts and their photos
$st = $db->prepare ('SELECT * FROM `posts` ' .
                    'LEFT JOIN `photos` ON `photo_post` = `post_id`');
$st->execute ();

// init our results array
$posts = array ();

$lastPostId = NULL;

// get the first post (plus it's JOINed photo)
while ( $post = $st->fetch (PDO::FETCH_OBJ) ) {

    if ( $lastPostId != $post->id ) {
        if ( $lastPostId !== NULL ) {
            // add this obj to the post array
            $posts[] = $tPost;
        }
        // start a new temp object
        $tPost          = stdClass();
        $tPost->id      = $post->id;
        $tPost->content = $post->content;
        $tPost->photos  = array();
    }

    // Add photo_id to current tPost obj
    $tPost->photos[] = $post->photo_id;

    $lastPostId = $post->id;
}

// and send it back
echo json_encode($posts);


Functional programming FizzBuzz I tried to code the fizzbuzz program following the functional programming rules in javascript. Please check my code and give feedback. thank you.
const isDivisible = (number, fizz) => number % fizz === 0;
const getSubstitutes = (
  number,
  substitutes,
  { currentIndex = 0, result = "" } = {}
) => {
  if (currentIndex === substitutes.length) return result;
  const { divisor, substitute } = substitutes[currentIndex];
  const newResult = result + (isDivisible(number, divisor) ? substitute : "");
  return getSubstitutes(number, substitutes, {
        currentIndex: currentIndex + 1,
        result: newResult,
  });
};
const fizzBuzz = (number, substitutes, currentIndex = 1) => {
  if (number < currentIndex) return;
  console.log(getSubstitutes(currentIndex, substitutes) || currentIndex);
  fizzBuzz(number, substitutes, ++currentIndex);
};
const substitutes = [
  {
        divisor: 3,
        substitute: "fizz",
  },
  {
        divisor: 5,
        substitute: "buzz",
  },
];
fizzBuzz(100, substitutes);

Overall it looks like you're missing out on most of the benefits of a functional approach and over-complicating your code. First glance it's basically impossible to work out what it's all doing without following each variable through everything.
Per the previous answer you don't seem familiar with common functional techniques like using .map, pipelines, or avoiding side-effects
Below is less a review of your code but a different solution that highlights the  techniques you're missing so you can see them in action
const fizzOrBuzz = (a, b, aPhrase, bPhrase) => (
    (n) => (
        (n % (a*b) === 0) ? aPhrase + bPhrase :
        (n % a === 0) ? aPhrase :
        (n % b === 0) ? bPhrase :
        n
    )
)

const generateNLengthArray = (n) => [ ...Array(n).keys()].map(i => i + 1)

const mapArrayTo = (f) => (array) => array.map(i => f(i))

const joinArray = (array) => array.join('\n')

const pipe = (...fns) => (x) => fns.reduce((v, f) => f(v), x) // One-liner pipeline pattern

const fizzbuzz = pipe(
    generateNLengthArray,
    mapArrayTo(fizzOrBuzz(3, 5, 'fizz', 'buzz')),
    joinArray
)

console.log(fizzbuzz(100))

One of the benefits of functional programming is breaking everything down into discrete, easily understandable functions, and then composing them together so it's crystal clear what's happening.
In this case defining fizzbuzz as a pipeline of three separate functions makes it clear that you're 1. creating an array of a specific length. 2. mapping the values of that array to either fizz or buzz and 3. joining the results together


Sort, & find out duplicates and missing elements in an array this code is for return duplicates after sorted them, and also to
  return the missed value between the limits of the given array, it's
  executed correctly, but i need to optimize it so it excecute in less
  time than it execute can any one help?

function findDupsMiss(arr) {
    // your code here
    var noDuplicates = [];
    var missedNum;
    var duplicates = [];
    var sortedDuplicates =[]

arr.forEach((el, i) => {
 if(noDuplicates.includes(el) == false){
   noDuplicates.push(el)
 }
})
var sortedArr = noDuplicates.sort((a,b) => a-b);
for(var i=0 ; i<sortedArr.length -1 ; i++){
  if((sortedArr[i]+1) !== sortedArr[i+1]){
    missedNum = sortedArr[i] + 1
   }
}
arr.forEach( el => {
  if(arr.indexOf(el) != arr.lastIndexOf(el)){
    duplicates.push(el)
  }
})
duplicates.forEach(el => {
  if(sortedDuplicates.includes(el) == false){
   sortedDuplicates.push(el)
 }
})

var lastdup = sortedDuplicates.sort((a,b) => a-b);
return [missedNum , lastdup]

}
findDupsMiss([10,9,8,9,6,1,2,4,3,2,5,5,3])

On the small 13 element array your implementation appears to be fairly performant, but since you request a "faster" implementation I took a stab at one myself.

Implementation

In this implementation I wanted to remove the multiple loops and use a data structure that lent itself to faster lookups, so I used plain javascript objects as maps. I also defined each array function callback outside where it'd be used to only instantiate a single copy.

function findDupsMiss2(arr) {
  const processedNumbers = {};
  const duplicates = {};
  const noDuplicates = {};

  const checkDupOrNot = (el, i) => {
    if (processedNumbers[el]) {
      duplicates[el] = el;
      delete noDuplicates[el];
    } else {
      noDuplicates[el] = el;
    }
    processedNumbers[el] = el;
  };

  arr.forEach(checkDupOrNot);

  const missedReduceFn = (missed, el, i, arr) =>
    el + 1 !== arr[i + 1] ? el : missed;
  const missed = [
    ...Array(
      processedNumbers[Object.values(processedNumbers).length - 1]
    ).keys()
  ].reduce(missedReduceFn, null);

  return [missed, Object.values(duplicates)];
}

Testing

This is the function I defined to measure how performant a function is:

const measurePerf = (fn, data, runs = 1000000) =>
  [...Array(runs).keys()]
    .map(() => {
      const start = performance.now();
      fn(data);
      const end = performance.now();
      return end - start;
    })
    .reduce((total, current) => total + current) / runs;

This takes a function and measures how long it takes to execute, sums the total time then divides by the # of runs to get an average execution time.

Used as such

measurePerf(findDupsMiss, data); // uses default 1 million iterations
measurePerf(findDupsMiss, data, 1000);

Initial Results

Using the default 1-million iteration performance measure

findDupsMiss1
[7, Array[4]]
0: 7
1: Array[4]
0: 2
1: 3
2: 5
3: 9
0.0021040050006413367

findDupsMiss2
[7, Array[4]]
0: 7
1: Array[4]
0: 2
1: 3
2: 5
3: 9
0.0023690749967063313

At first this may seem like your code is already faster (or my implementation is slower), but this isn't the entire story.

If we analyze the Big-O complexity of your implementation we find it is O(n^2). Of the outer loops (3x O(n) forEach loops and 2x O(nLog_n) sorts) each of the forEach loops has an additional O(n) search loop to find either an index or if an element is already included, bumping the Big-O to O(n^2).

The other implementation has also 4x loops (1x forEach, 1x array spread, 1x array reduce, 1x object.values), but has no inner loops, each loop uses an O(1) lookup in a map, so has an O(n) complexity.

  But where is the sort?

When using an object as a map with number-like keys, they are inserted in numerical order, so we get "sorting" for free. (in reality there is probably some minimal search though).

Further Results & Extended Examination

  What does this Big-O O(n^2) vs O(n) mean?

This has to do with how much work there is to do based upon input size. When an algorithm's Big-O complexity is O(n) then when the input size doubles the output should roughly double, i.e. something like 2n (hand wavey), whereas when an algorithm's Big-O complexity is O(n^2) then the output size something more like 4n.

Here's a rough table of output. Because of performance I had to drop the test performance iterations to 100 (versus10^6), but figured 100 runs is still enough to gather enough data for decent comparisons.

TBH the average is less relevant here as this table is more to illustrate the ratio between the two algorithms, with a secondary comparison in parenthesis to highlight the ratio of output from the previous iteration

const measurePerf = (fn, data, runs = 1000000) =>
  [...Array(runs).keys()]
    .map(() => {
      const start = performance.now();
      fn(data);
      const end = performance.now();
      return end - start;
    })
    .reduce((total, current) => total + current) /runs;

function findDupsMiss1(arr) {
  // your code here
  var noDuplicates = [];
  var missedNum;
  var duplicates = [];
  var sortedDuplicates = [];

  arr.forEach((el, i) => {
    if (noDuplicates.includes(el) == false) {
      noDuplicates.push(el);
    }
  });
  var sortedArr = noDuplicates.sort((a, b) => a - b);
  for (var i = 0; i < sortedArr.length - 1; i++) {
    if (sortedArr[i] + 1 !== sortedArr[i + 1]) {
      missedNum = sortedArr[i] + 1;
    }
  }
  arr.forEach(el => {
    if (arr.indexOf(el) != arr.lastIndexOf(el)) {
      duplicates.push(el);
    }
  });
  duplicates.forEach(el => {
    if (sortedDuplicates.includes(el) == false) {
      sortedDuplicates.push(el);
    }
  });

  var lastdup = sortedDuplicates.sort((a, b) => a - b);

  return [missedNum, lastdup];
}

function findDupsMiss2(arr) {
  const processedNumbers = {};
  const duplicates = {};
  const noDuplicates = {};

  const checkDupOrNot = (el, i) => {
    if (processedNumbers[el]) {
      duplicates[el] = el;
      delete noDuplicates[el];
    } else {
      noDuplicates[el] = el;
    }
    processedNumbers[el] = el;
  };

  arr.forEach(checkDupOrNot);

  const missedReduceFn = (missed, el, i, arr) =>
    el + 1 !== arr[i + 1] ? el : missed;
  const missed = [
    ...Array(
      processedNumbers[Object.values(processedNumbers).length - 1]
    ).keys()
  ].reduce(missedReduceFn, null);

  return [missed, Object.values(duplicates)];
}

const data = [10, 9, 8, 9, 6, 1, 2, 4, 3, 2, 5, 5, 3];

const perf1 = measurePerf(findDupsMiss1, data);
console.log(findDupsMiss1(data), perf1);

const perf2 = measurePerf(findDupsMiss2, data);
console.log(findDupsMiss2(data), perf2);

const processIterations = async () => {
  const results = [];

  // # elements 1, 2, 4, 8, 16, 32, 64, ..., 262144, 524288
  for (let i = 0; i < 20; i++) {
    const dataLength = 1 << i;
    const randData = [...Array(dataLength).keys()].map(() =>
      Math.floor(Math.random)
    );

    const [t1, t2] = await Promise.all([
      // For your sanity, start skipping findDupsMiss1 here at 11.
      // Maybe don't go more than 15 unless you like creating space heaters.
      i < 11 ? measurePerf(findDupsMiss1, randData, 100) : "skipped",
      measurePerf(findDupsMiss2, randData, 100)
    ]);

    results.push({
      iteration: i,
      dataLength,
      t1: Number.isFinite(t1) ? Number(t1).toFixed(3) : t1,
      t2: Number.isFinite(t2) ? Number(t2).toFixed(3) : t2
    });
  }

  return results;
};

processIterations().then(results => {
  console.log(`\t# Elements\tt1\tt2\tt2:t1 ratio`);
  results.forEach(({ iteration, dataLength, t1, t2 }, i, arr) => {
    const prev = arr[i - 1] || {};
    const t2t1Ratio = Number(t2 / t1).toFixed(2);
    const t1Ratio = Number(t1 / prev.t1).toFixed(1);
    const t2Ratio = Number(t2 / prev.t2).toFixed(1);

    console.log(
      `${iteration}\t${dataLength}\t${t1}(${t1Ratio})\t${t2}(${t2Ratio})\t${t2t1Ratio}`
    );
  });
});

    # Elements  t1 avg          t2 avg          t2:t1 ratio
0   1           0.002(NaN)      0.003(NaN)      1.50
1   2           0.002(1.0)      0.004(1.3)      2.00
2   4           0.003(1.5)      0.005(1.3)      1.67
3   8           0.006(2.0)      0.006(1.2)      1.00
4   16          0.005(0.8)      0.012(2.0)      2.40
5   32          0.011(2.2)      0.016(1.3)      1.45
6   64          0.031(2.8)      0.029(1.8)      0.94
7   128         0.084(2.7)      0.048(1.7)      0.57
8   256         0.270(3.2)      0.094(2.0)      0.35
9   512         1.032(3.8)      0.186(2.0)      0.18
10  1024        4.696(4.6)      0.372(2.0)      0.08
11  2048        16.303(3.5)     0.749(2.0)      0.05
12  4096        67.092(4.1)     1.492(2.0)      0.02
13  8192        266.986(4.0)    3.018(2.0)      0.01
14  16384       1081.774(4.1)   6.785(2.2)      0.01
15  32768       skipped(NaN)    12.298(1.8)     NaN
16  65536       skipped(NaN)    25.941(2.1)     NaN
17  131072      skipped(NaN)    49.775(1.9)     NaN
18  262144      skipped(NaN)    99.556(2.0)     NaN
19  524288      skipped(NaN)    195.841(2.0)    NaN

Notes:

Average time is in milliseconds
Item in () is the ratio to the previous time (i.e. line above)
Each iteration 100 runs for performance measuring
Stopped measuring algorithm 1 after 15 iterations, it's just too slow

Conclusion

As can be seen, the table confirms your algorithm, after a certain point, appears to settle into roughly a 4x output size based upon 2x input, where the other algorithm appears to settle around 2x, as expected. Also, a tipping point appears to consistently be around iteration #6 / 64 elements when algorithm #2 overtakes algorithm #1 and is more performant.


Hash-consing: running slow I've isolated this function, cons, for hash-consing in C. It is where the bottleneck of my program is. How could its performance be improved?

var32 cons(var32 x, var32 y){
    var32 ptr;
    uid id, hashedId;
    map newMap, currentMap;
    u32 colls;

    #ifdef __DEBUG__
    ++consCount;
    colls = 0;
    #endif

    // Before anything, compute the unique id of that node.
    id = (((uid)(x.ptr))<<32) | (uid)y.ptr;

    // Try to find the node. If it already exists, return its ptr.
    hashedId = id % MAP_HASH_SIZE;
    currentMap = mapByHashedId[hashedId];
    if (currentMap) do {
        if (mapId[currentMap] == id)
            return mapPtr[currentMap];
        #ifdef __DEBUG__
        ++colls;
        #endif
    } while ((currentMap = mapNext[currentMap]));

    #ifdef __DEBUG__
    if (colls<16) ++collisionCount[colls];
    ++allocCount;
    #endif

    // If does not exist, then alloc a new ptr to it.
    ptr = nodeNewPtr[nodeNewPtrIndex--];

    // Add that new ptr to the map.
    newMap = mapNewPtr[mapNewPtrIndex--];
    if (mapByHashedId[hashedId])
        mapNext[newMap] = mapByHashedId[hashedId];
    mapId[newMap] = id;
    mapPtr[newMap] = ptr;
    mapByHashedId[hashedId] = newMap;

    // Fill that new ptr.
    nodeLeft[GETPTR(ptr)] = x;
    nodeRight[GETPTR(ptr)] = y;

    return ptr;
};

Here is a link for complete source with tests!

Your code here is hard to follow because your code style and format are inconvenient.

Structures like this:

currentMap = mapByHashedId[hashedId];
if (currentMap) do {
    if (mapId[currentMap] == id)
        return mapPtr[currentMap];
    #ifdef __DEBUG__
    ++colls;
    #endif
} while ((currentMap = mapNext[currentMap]));

are .... irregular. a better format would be:

currentMap = mapByHashedId[hashedId];
while (currentMap)
{
    if (mapId[currentMap] == id)
        return mapPtr[currentMap];

    #ifdef __DEBUG__
    ++colls;
    #endif

    currentMap = mapNext[currentMap]
}

Additionally, this is the only loop in your method. All the other code are simple array and pointer manipulations. This method can only be slow because of three reasons:

it is called many, many times
the while loop iterates many many times
there's something else you're not showing.

Assuming the number of calls are appropriate, and you're not missing anything, the only alternative is that the while loop loops often. This indicates there are many collisions. Collisions happen for two reasons:

your MAP_HASH_SIZE is too small
your hashing function is irregular

I am going to go with both of those. In fact, I am going to guess that MAP_HASH_SIZE is something like 8192, or some other power of 2. The reason this is my (educated) guess, is that your hash function is vulnerable to inconsistencies.

Consider how you build your function, using two 32-bit values with the x value shifted and or'd with the y value. Let's also use some test data:

  x      y
---    ---
0x1    0x1
0x2    0x1
0x3    0x1
0x4    0x1

Now, in your function you would produce the ID by shifting the X, and the hash, by the modulo of the table size. Let's assume the table size is 32768 (a nice big value that should eliminate collisions, right)?

  x      y          id   hashedId
---    ---  ----------   --------
0x1    0x1  0x10000001        0x1
0x2    0x1  0x20000001        0x1
0x3    0x1  0x30000001        0x1
0x4    0x1  0x40000001        0x1

Because your MAP_HASH_SIZE is likely a power-of-2, the % MAP_HASH_SIZE is essentially the same as a bitmask of the low-order bits (or 0x7fff for size 32768)

If all your y values are similar, you will end up with many collisions in just a few buckets in the hash table.

For the hash function I would consider guaranteeing a minimum size (say 16 bits, or 64K), and then having a function which at least shifts some of the x value in to the range, and does an Xor....

hashedId = ((x << 7) ^ (y * 31)) % MAP_HASH_SIZE;

The above function will give you better distribution (perhaps not perfect) even if the hash size is a power of 2 > about 16 bits.


Collecting 3 years of data and building a string I am collecting 3 years of data and building a string that will be used with an ASP Literal control. The method GetListOfMeetingBygroupId takes in a groupID and year and will return meeting for that group and year.

    MeetingService ms = new MeetingService();
    int groupId = 574;

    //Meeting

    int totalYearCount = 3;
    StringBuilder sbMeeting = new StringBuilder();
    DateTime aDate = DateTime.Now;
    for (int x = 1; x <= totalYearCount; x++)
    {

        var list = ms.GetListOfMeetingBygroupId(groupId, aDate.Year);

        sbMeeting.AppendFormat("
{0}
",aDate.ToString("yyyy"));

        foreach (var meeting in list)
        {
                sbMeeting.Append("
");

                DateTime meetingendDate = Convert.ToDateTime(meeting.MeetingDateList.Select(c => c.StartDate).Max());
                DateTime meetingstartDate = Convert.ToDateTime(meeting.MeetingDateList.Select(c => c.StartDate).Min());

                int totalMeetingPresentation = ms.GetListOfPresentationsBymeetingId(meeting.MeetingId).Count();

                sbMeeting.Append(meetingstartDate.ToString("dddd, MMMM dd  yyyy"));
                sbMeeting.Append("
");
                sbMeeting.Append(meeting.Type.Name);
                sbMeeting.Append("
");

                if (totalMeetingPresentation > 0)
                {
                    sbMeeting.AppendFormat("{1}", meeting.MeetingId, "Minutes and Presentations");
                }
                else
                {

                    var meetingMinFile = ms.GetMeetingFile(meeting.MeetingId);
                    sbMeeting.AppendFormat("{1}	", meetingMinFile.FileManagerId, "Minutes");

                }
                sbMeeting.Append("
");
                sbMeeting.Append("
");
                sbMeeting.Append("
");
       }
        aDate = aDate.AddYears(-1);
    }

I'll focus on the C# part of the code, but please run the output HTML through a validator because at first glance I count no fewer than five HTML tags that are mismatched, misplaced, or simply broken.

Outer loop

You're not using the loop variable x anywhere. This suggests that the loop should be refactored around the thing that you're actually iterating over, which seems to be a range of years.

Each year is just an integer; you can get a range of integers using Enumerable.Range. You want the most recent totalYearCount years (inclusive of this year), so start the range at nowYear - totalYearCount + 1. You want this year first, so reverse the sequence too.

foreach (var year in Enumerable
    .Range(aDate.Year - totalYearCount + 1, totalYearCount)
    .Reverse())
{
    var list = ms.GetListOfMeetingBygroupId(groupId, year);
    // ...
}

You can replace aDate.ToString("yyyy") accordingly.

Naming

When using camelCase and PascalCase, each distinct word should start with a capital letter. GetListOfMeetingByGroupId, GetListOfPresentationsByMeetingId, meetingStartDate, meetingEndDate, and so on.

Type prefixes like sb don't help much, especially when abbreviated. Rename that variable to better reflect what it actually is: it's a builder for the output, so maybe outputBuilder instead of sbMeeting.

list is a really generic name for something we know to be a collection of meetings, so call it meetings or meetingList.

Code we haven't seen

It's advised to post or link to all supporting code. It's at least relevant because of this here:

Convert.ToDateTime(meeting.MeetingDateList.Select(c => c.StartDate).Max());

What's the type of c.StartDate? You're converting it to a DateTime after getting the maximum date -- so it's probably not a DateTime already -- which begs the question how are you sorting the dates? I suspect you might've wanted the order switched:

meeting.MeetingDateList.Max(c => Convert.ToDateTime(c.StartDate));

Note that I've used the overload for Max that takes a selector so that I can avoid the unnecessary Select.

General readability

Your spacing is inconsistent. Consistent spacing would make for better readability, so I offer these suggestions:

Use exactly one indent per {} block -- your inner foreach loop is double-indented.
Avoid empty lines of padding within {} blocks -- see your for loop and the else block.
Parameters should be separated by a comma and one space -- see your first sbMeeting.AppendFormat(...).

All of those hard-coded HTML strings should be refactored out into some kind of template. They have no business being encoded inline in the method like that.