Project Euler # 19 Counting Sundays in Python You are given the following information, but you may prefer to do some research for yourself.
1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

day_names = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
month_names = ['January', 'February', 'March', 'April', 'May', 'June', 'July', 'August', 'September',
               'October', 'November', 'December']
month_days_common = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
month_to_days = dict(zip(month_names, month_days_common))

def is_leap(year):
    """return True if a year is leap. False otherwise."""
    if (year % 4) == 0:
        if (year % 100) == 0:
            if (year % 400) == 0:
                return True
            else:
                return False
        else:
            return True
    else:
        return False

def get_date_day_names(end_year):
    """return a list of tuples containing day name, day, month, year from 1900 to end_year(exclusive)."""
    start_year = 1900
    total = 0
    all_day_names = []
    all_months1 = []
    all_months2 = {}
    year_month_times_number_of_days = []
    final_dates = []
    for year in range(start_year, end_year):
        count = 0
        while count < 12:
            all_months1.append((year, month_names[count]))
            count += 1
    for year in range(start_year, end_year):
        if is_leap(year):
            total += 366
        else:
            total += 365
    for i in range(total):
        all_day_names.append(day_names[i % 7])
    for year, month in all_months1:
        if is_leap(year):
            if month == 'February':
                all_months2[(year, month)] = 29
            else:
                all_months2[(year, month)] = month_to_days[month]
        else:
            all_months2[(year, month)] = month_to_days[month]
    for date, number_of_days in all_months2.items():
        for i in range(number_of_days):
            year_month_times_number_of_days.append((date, i + 1))
    date_day_name = list(zip(all_day_names, year_month_times_number_of_days))
    for date_item in date_day_name:
        final_dates.append((date_item[0], date_item[1][1], date_item[1][0][1], date_item[1][0][0]))
    return final_dates

def count(day_name, day_of_the_month, end_year):
    """returns count of a given day from 1901 to end_year(exclusive)"""
    final_dates = []
    dates_1900_to_end_year = get_date_day_names(end_year)
    for date in dates_1900_to_end_year:
        if date[-1] != 1900 and date[0] == day_name and date[1] == day_of_the_month:
            final_dates.append(date)
    return len(final_dates)

if __name__ == '__main__':
    print(count('Sunday', 1, 2001))

whole algorithmic change => \$O(n)\$

Your existing algorithm is quite confusing. Perhaps instead you could try a simpler structure such as:

from datetime import date

def num_sundays_on_first_of_month(year1, year2):
  num_sundays = 0
  for i in range(year1, year2+1):
      for j in range(1, 13):
          if date(i, j, 1).weekday() == 6:
              num_sundays += 1
  return num_sundays

if __name__ == '__main__':
    print(num_sundays_on_first_of_month(1901,2000))

This code is much more readable and far briefer. It makes effective use of the datetime module and its date objects.  It works by looping through every month between year1 and year2 inclusive and counting if it is a Sunday.

This runs at \$O(n)\$ time where \$n = year2 - year1\$


Adding file name information to CSV file columns Is there a simple way to combine the functions of this Powershell script?  It would be nice to have it file to one output file instead of several output files.

    GET-DATE
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1000 -entrytype Information -message "START CBM_PARSE.ps1" -category 1
######################################################################
######################################################################
$SA_Location = "E:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3"
SET-LOCATION $SA_Location
$filenames = @(GET-CHILDITEM $SA_Location -recurse -include *.csv)
$regex = '^([^-]+-[^-]+)-([A-Z])-(\d{4})(\d\d)(\d\d).+'

# $PIPE = ","
$PIPE = "$([char]0x2C)"

# $SLASH = "\"
$SLASH = "$([char]0x5C)"

# $DSLASH = "\"
$DSLASH = "$([char]0x5C)$([char]0x5C)"

foreach ($file in $filenames) {$outfile = "$file" + ".out"
$ReplaceString = ($file | Split-Path -leaf) -replace $regex,'$1|$3-$4-$5|$2:'
((GET-CONTENT $file| Out-String).Substring(7))  | FOREACH-OBJECT -Verbose {
       $_ -replace "\\","\\" `
        -replace $PIPE,"|" `
        -replace "E:",$ReplaceString `
    } | SET-CONTENT  $outfile
}
GET-DATE
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1002 -entrytype Information -message "END Parsing" -category 1
ECHO "END PARSE"
######################################################################
######################################################################

GET-DATE
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1000 -entrytype Information -message "START CBM-FS3" -category 1
GET-CONTENT (GET-CHILDITEM "E:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3\*.out") | out-file -encoding "UTF8" "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3\CBM-FS3.txt"
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1002 -entrytype Information -message "END CBM-FS3" -category 1
ECHO "END CBM-FS3"
<#
GET-DATE
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1000 -entrytype Information -message "START CBM-FS56" -category 1
GET-CONTENT (GET-CHILDITEM "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS56\*.out") | out-file -encoding "UTF8" "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS04\CBM-FS04.txt"
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1002 -entrytype Information -message "END CBM-FS56" -category 1
ECHO "END CBM-FS56"
#>
GET-DATE
WRITE-EVENTLOG -logname Application -Source BLERG -EventID 1002 -entrytype Information -message "END CBM_PARSE.ps1" -category 1
ECHO "END END"
######################################################################
######################################################################

Assuming you commented out the second file generation of these two:

GET-CONTENT (GET-CHILDITEM "E:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3\*.out") | out-file -encoding "UTF8" "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3\CBM-FS3.txt"

GET-CONTENT (GET-CHILDITEM "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS56\*.out") | out-file -encoding "UTF8" "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS04\CBM-FS04.txt"

You can combine the above lines using the -LiteralPath parameter to Get-ChildItem, like so:

GET-CONTENT (GET-CHILDITEM -LiteralPath 'E:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3\*.out', 'C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS56\*.out') | out-file -encoding "UTF8" "C:\Users\jsweeton\Documents\SITES\CBM\Storage Analysis\CBM-FS3\CBM-FS3.txt"

If that's not what you're looking for or you need more input, just let me know and I'll update my answer accordingly.


Pythonic way of removing one word entries from compound list Assume a multi-line file (myInput.txt) with lines comprising one or more words.
echo -e "Foo\nFoo bar\nFoo baz\nFoo bar baz\nBar\nBaz\nBaz qux\nBaz qux quux\nQux quux" > myInput.txt

I wish to remove all one-word lines that are identical with the first word of any multi-word lines using Python.
echo -e "Foo bar\nFoo baz\nFoo bar baz\nBar\nBaz qux\nBaz qux quux\nQux quux" > myGoal.txt

The following code satisfies my goal but does not appear overtly Pythonic to me.
from itertools import compress

myList = list()
with open("myInput.txt", "r") as myInput:
    for line in [l.strip() for l in myInput.readlines()]:
        if not line.startswith("#"):
            myList.append(line)

# Get all lines with more than one word
more_than_one = list(compress(myList, [len(e.strip().split(" "))>1 for e in myList]))
# Get all lines with only one word
only_one_word = list(compress(myList, [len(e.strip().split(" "))==1 for e in myList]))
# Keep only unique set of initial words of more_than_one
unique_first_words = list(set([e.split(" ")[0] for e in more_than_one]))
# Remove all union set words from only_one_word
only_one_word_reduced = [e for e in only_one_word if e not in unique_first_words]
# Combine more_than_one and only_one_word_reduced
combined_list = only_one_word_reduced + more_than_one

Do you have any suggestions on making the Python code slimmer and more straightforward?

# Get all lines with more than one word
more_than_one = list(compress(myList, [len(e.strip().split(" "))>1 for e in myList]))

The function split splits by whitespaces by default, there is no need to pass the explicit argument
Lines have been stripped already when reading the file, using strip seems unnecessary
Using list comprehension should be enough, without the function compress and list

For example:
more_than_one = [line for line in myList if len(line.split()) > 1]

Or:
more_than_one = [line for line in myList if ' ' in line]

Same observations for Get all lines with only one word

# Keep only unique set of initial words of more_than_one
unique_first_words = list(set([e.split(" ")[0] for e in more_than_one]))

Not sure why the set is converted to a list. Checking for unique words in a set is much faster than in a list

Functions: would be better to include all the operations in a function, for easier testing and reuse
PEP 8: function and variable names should be lowercase, with words separated by underscores as necessary to improve readability. myList should be my_list. More info.

A function that does the same could be the following:
def remove_duplicates(lines):
    seen = set()
    for line in lines:
        first_word, *tail = line.split()
        if tail:
            seen.add(first_word)
    return [line for line in lines if line not in seen]

An use it like:
print(remove_duplicates(['a','a b','b','c','c d','z']))
# Output: ['a b', 'b', 'c d', 'z']


Dynamic call of module pattern function I started reading about JavaScript patterns, and I really liked module pattern.
So I created some module:

var App = (function (parent, $) {
    function myPrivateFunc () {
        // Some private stuff
    }

    return {
        myPubFunc: myPrivateFunc,
        publicFunction: function () {
            // Do some stuff
        }
    };
})(App || {}, jQuery);

Now I want to call some functions on page but only functions I need on that specific page. I got idea to add data-modules attribute to body, and then load modules I demanded on that attribute. I did that this way:

var modules = $('body').data('modules').split(" ");

for (var i = modules.length - 1; i >= 0; i--) {
    App[modules[i]]();
}

My question is: Is this a good way to achieve what I wanted? I tested, it's working fine, but I'm a little suspicious about this dynamic calling. Is there better solutions (preferably not libraries) out there? If this is not good, why it isn't?

Instead of adding data-properties to the body tag, and waiting for / relying on jQuery, just use an inline script:

<script type="text/javascript">
    var modules = /* echo the needed modules here */;
    for (var i=0; i<modules.length; i++)
        App[modules[i]]();
</script>


Tiny Curl C++ wrapper I have written this sample code to fetch a web page in C++ using libcurl. Please review it.

#include <iostream>
#include <iostream>
#include <string>
#include <exception>

extern "C"
{
#include <curl/curl.h>
#include <stdlib.h>
}

//Exception class for curl exception

class CurlException : std::exception
{
public:
   CurlException(std::string message):m_message(message) {  }
   CurlException(CURLcode error)
   {
      m_message = curl_easy_strerror(error);
   }
   const char* what() throw()
   {
      return m_message.c_str();
   }
   ~CurlException() throw() { }

private:
   std::string m_message;
};

//A tiny wrapper around Curl C Library

class CppCurl
{
public:
   CppCurl(std::string url) throw (CurlException)
   {
      m_handle = curl_easy_init();
      if ( m_handle == NULL )
         throw CurlException("Unable to initialize curl handler");
      if ( url.length() == 0 )
         throw CurlException("URL can't be of zero length");
      m_url = url;
   }

   std::string Fetch() throw (CurlException)
   {
      SetOptions();
      SendGetRequest();
      return m_data;
   }

   ~CppCurl() throw()
   {
      curl_easy_cleanup(m_handle);
   }

private:

   void SetOptions() throw (CurlException)
   {
      CURLcode res;

      //set the url
      res = curl_easy_setopt(m_handle, CURLOPT_URL, m_url.c_str());
      if ( res != CURLE_OK)
         throw CurlException(res);

      //progress bar is not require
      res = curl_easy_setopt(m_handle, CURLOPT_NOPROGRESS, 1L);
      if ( res != CURLE_OK )
         throw CurlException(res);

      //set the callback function
      res = curl_easy_setopt(m_handle, CURLOPT_WRITEFUNCTION,
                              CppCurl::WriteDataCallback);
      if ( res != CURLE_OK )
         throw CurlException(res);

      //set pointer in call back function
      res = curl_easy_setopt(m_handle, CURLOPT_WRITEDATA, this);
      if ( res != CURLE_OK )
         throw CurlException(res);

   }

   void SendGetRequest()
   {
      CURLcode res;
      res = curl_easy_perform(m_handle);
      if ( res != CURLE_OK )
         throw CurlException(res);
   }

   static size_t WriteDataCallback(void *ptr, size_t size,
                                    size_t nmemb, void* pInstance)
   {
      return (static_cast<CppCurl*>(pInstance))->write_data(ptr, size, nmemb);
   }

   size_t write_data(void* ptr, size_t size, size_t nmemb)
   {
      size_t numOfBytes = size * nmemb;

      char *iter = (char*)ptr;
      char *iterEnd = iter + numOfBytes;

      //while ( iter != iterEnd )
      //{
      //   cout<<*iter;
      //   iter ++;
      //}

      m_data += std::string(iter, iterEnd);

      return numOfBytes;
   }

   CURL *m_handle;
   std::string m_url;
   std::string m_data;

};

int main()
{
   try
   {
      CppCurl ob("http://kodeyard.blogspot.in/");
      std::cout<<ob.Fetch();
      std::cout<<std::endl;
   }
   catch ( CurlException e)
   {
      std::cerr<<"Exception thrown..."<<std::endl;
      std::cerr<<e.what()<<std::endl;
   }

   return 0;

}

This is also here in the blog.

You should probably derive from std::runtime_error.
It takes a string in the constructor as the message and stored it for use with what() in a way that is safe even in low memory situations:

Your exception class is then simplified too:

class CurlException : public std::runtime_error
{
public:
   CurlException(std::string const& message): std::runtime_error(message) {}
                         //  ^^^^^^^ pass message by const reference.
   CurlException(CURLcode error): std::runtime_error(curl_easy_strerror(error)) {}
};

The use of exception specifications in C++ was an experiment that ultimitely showed it was a bad idea. The only useful specification was the no throw specification (and then only when you made sure it really was no-throw).

void SetOptions() throw (CurlException)
              // ^^^^^^^^^^^^^^^^^^^^^ Get rid of this bit.

In C++11 exception specifications have been deprecated.

The curl library is a C library. It only knows about C calling conventions. Thus you can NOT pass it C++ functions. If it works it is pure luck and definately non portable.

  res = curl_easy_setopt(m_handle, CURLOPT_WRITEFUNCTION,
                          CppCurl::WriteDataCallback);

Even though CppCurl::WriteDataCallback is a static function there is no guarantee that static methods have the same calling convention as a C function. Future versions of the compiler may break your code.

You should do something like this:

 extern "C" size_t WriteDataCallback(void *ptr, size_t size, size_t nmemb, void* pInstance)
 {
      CppCurl*   obj = reinterpret_cast<CppCurl*>(pInstance);
      return obj->write_data(ptr, size, nmemb);
 }

Not a big deal but I would have used insert rather than +=.

      m_data += std::string(iter, iterEnd);

 // -- or.

      m_data.insert(m_data.begin(), iter, iterEnd);


Check if an entity exists in a Azure Table Storage I want to check as fast as possible if an entity, based on PartitionKey and RowKey, exists in an Azure Table Storage.

I can do a standard TableOperation.Retrieve and check the result, like:

TableOperation retrieveOperation = TableOperation.Retrieve<CustomerEntity>("Smith", "Ben");
TableResult retrievedResult = table.Execute(retrieveOperation);

but that would return the complete entity.

By using a DynamicTableEntity I reduce the amount of data that is returned.
More code, but I assume better...

public async Task<bool> EntityExists(string partitionKey, string rowKey)
{
    var tableQuery = new TableQuery<DynamicTableEntity>();
    tableQuery.FilterString = TableQuery.CombineFilters(
            TableQuery.GenerateFilterCondition("PartitionKey", QueryComparisons.Equal, paritionKey),
            TableOperators.And,
            TableQuery.GenerateFilterCondition("RowKey", QueryComparisons.Equal, rowKey));

    var dynamicTableEntities = await CloudTable.ExecuteQuerySegmentedAsync(tableQuery, null, TableRequestOptions, OperationContext);
    return dynamicTableEntities.Results.Any();
 }

Any suggestions/criticisms to my solution are welcome

If I remember correctly, accessing a row by PartitionKey and RowKey is built to be the fastest operation you can do on an Azure Table Storage. The performance drawback of using a DynamicTableEntity probably isn't worth it unless the returned entity is really big.

I feel like you should stick to the Retrieve, but there's no better way to be sure than to profile both your solutions for performance to see which is better with your data.

Because there's nothing else to say about your code, from what I know, you have the 2 existing solutions in your hand. Figure the best one now :)


'Broken Record' Coding Challenge I was asked to complete a coding challenge for an interview. The challenge being to write a test function to check whether or not a string was a broken record. A broken record is defined as a string that contains a sequential repeated substrings. For example:

# These are broken records
"This is is a broken record"
"This is a is a broken record"
"This is a broken record. This is a broken record."

# These are not broken records
"This is not is a broken record"
"This is a is This"
"This is a broken record. This is not a broken record."

This is the code that I was able to come up with (Python 2.7). Any criticisms, improvements, or suggestions are greatly appreciated.

# Author: Jeremiah Zucker
# brokenRecord.py
# A small module to test whether a substring is repeated
# immediately, like a broken record

def brokenRecord(sent):
   if sent == "": # Use defualt string if empty
      sent = "This is a a is This"
   print("Determining if broken record: %s" % sent)

   arr = sent.split(" ")

   # Create count array for the sentence
   carr = [0] * len(arr)
   for i in range(0,len(arr)):
      carr[i] = arr.count(arr[i])

   # For each element in the array, try to find the
   # repeat if one is possible
   for i in range(0,len(arr)):
      if carr[i] > 1 and findRepeat(arr, i):
         print("Is a broken record at %d!" % i)
         return
   print("Not a broken record.")

def findRepeat(arr, i):
   beg = arr[i]
   j = i

   # Find all other indices of 'beg'
   others = []
   while beg in arr[j+1:]:
      j = arr[j+1:].index(beg) + j + 1
      others.append(j)

   # For all other indices of 'beg'
   for j in others:
      # Get both substrings
      lenRep = j - i
      try:
         rep = arr[i:j]
         rep2 = arr[j:j+lenRep]
      except IndexError:
         continue

      # Are they equal?
      if rep == rep2:
         # print(rep)
         # print(rep2)
         return True

   # Nope
   return False

if __name__ == '__main__':
   # print usage
   print("brokenRecord.py")
   print("To use, type a string and hit ENTER.")
   print("If no string is provided, the default string will be used.")

   # do until ctrl+c
   while True:
      try:
         brokenRecord(raw_input("\nString: "))
      except KeyboardInterrupt:
         print("\nThanks for testing!")
         break

First impressions matter in interview coding situations.  My first thought is: There's a lot of code.  And interviewers usually don't like to wade through a lot of code.  For you, as a candidate, that may be a sign that you are taking the wrong approach.

Function names should be lower_case_with_underscores as specified in PEP 8 coding conventions.

There should be a function that accepts a string and returns either True or False.  Your brokenRecord() function…

def brokenRecord(sent):
   if sent == "": # Use defualt string if empty
      sent = "This is a a is This"
   print("Determining if broken record: %s" % sent)
   …
   print("Not a broken record.")

… incorporates all kinds of junk that make it not reusable:

A weird if sent == "": sent = "This is a a is This" special case.  Such
a special case should be moved out into your testing mechanism — the caller, or, better yet, a doctest.
Printing diagnostics.  Again, such code should be done by the caller.
Not returning any useful value, making it hard for the caller to know what happened.

Catching IndexError to recover from out-of-bounds array access is poor style.

In your main loop, you could eliminate the break by swapping the try and while.

# do until ctrl+c
try:
   while True:
      brokenRecord(raw_input("\nString: "))
except KeyboardInterrupt:
   print("\nThanks for testing!")

Suggested solution

If I, as an interviewer, had asked this question, I would be hoping for a completely different kind of answer.  String analysis is much more easily done using regular expressions.  In particular, you need this feature:

  Backreferences in a pattern allow you to specify that the contents of an earlier capturing group must also be found at the current location in the string. For example, \1 will succeed if the exact contents of group 1 can be found at the current position, and fails otherwise. Remember that Python’s string literals also use a backslash followed by numbers to allow including arbitrary characters in a string, so be sure to use a raw string when incorporating backreferences in a RE.

  For example, the following RE detects doubled words in a string.

>>>
>>> p = re.compile(r'(\b\w+)\s+\1')
>>> p.search('Paris in the the spring').group()
'the the'

import re

def is_broken_record(s):
    """
    Check whether a string contains sequential repeated substrings.

    >>> is_broken_record("This is is a broken record")
    True
    >>> is_broken_record("This is a is a broken record")
    True
    >>> is_broken_record("This is a broken record. This is a broken record.")
    True

    >>> is_broken_record("This is not is a broken record")
    False
    >>> is_broken_record("This is a is This")
    False
    >>> is_broken_record("This is a broken record. This is not a broken record.")
    False
    """
    return bool(re.search(r'\b(.+)\s+\1', s))


C# greedy algorithm to pick activities that do not clash with each other (corrected) My task is the greedy algorithm:

The activity selection problem is characteristic to this class of problems, where the goal is to pick the maximum number of activities that do not clash with each other.

Sample input (the first line indicates the number of intervals; each subsequent line contains a start time and end time):

5
2 4
1 7
6 9
9 11
5 8

Corresponding output (maximum number of non-overlapping activities, followed by the indexes of those activities):

3
1 5 4

The output above indicates that the activities at time intervals 2-4, 5-8, and 9-11 can all be chosen with no overlap.

The program works on small data, but it is too slow for really big input and I don't know how to improve it. Any ideas?

  class Program
{
    static void Main(string[] args)

    {
       int N;
       int[,] a;
        using (StreamReader sr = new StreamReader(@"prednasky.in"))
        {
            string line;
            line = sr.ReadLine();
            N = int.Parse(line);
            a = new int[N, 2];
            int[] indx = new int[N];
            int[] b = new int[N];
            for (int i = 0; i < N; i++)
            {
                line = sr.ReadLine();
                int[] nums = line.Trim().Split().Select(int.Parse).ToArray();
                //the beginning of the interval to a[i, 0], indexes to a[i, 1]
                a[i, 0] = nums[0];
                a[i, 1] = i + 1;
                //The end of the interval to b[i]
                b[i] = nums[1];
                //indx is array of indexes, i sort it instead of array a
                indx[i] = i;
            }

            //now sort array of the end of the interval and array of indexes by it
            Array.Sort(b, indx);
            //now in 1 cycle going through a[index, *] and b. And save "correct" intervals to the start of a(becouse we already don't need it

            int last = 0;
            int poc = 0;
            for (int i = 0; i < N; i++)
            {
                if (a[indx[i], 0] > last)
                {
                    a[indx[poc], 0] = a[indx[i], 1];
                    poc++;
                    last = b[i];
                }
            }
            using (StreamWriter sr1 = new StreamWriter(@"rozvrh.out"))
            {
                sr1.WriteLine(poc);
                for (int i = 0; i < poc; i++)
                {
                    sr1.Write(a[indx[i], 0]);
                    sr1.Write(" ");
                }
                }
        }
    }

}

One of the prevailing rules of C# code development is that your code should be readable by others.  That means the intent of what you are doing should be easily determined by someone else reading your code.

This is not the case with your post.

I can't even begin to comment upon your algorithm without taking lots of time to figure out what you are doing.  Therefore, my reply is about style and structure.

Don't put everything in Main().  Your app wants to do 3 overall things:

Read inputs
Run thru a calculation
Write outputs

Your Main() would be simplified along those division of duties.  Thus your new Main() would:

Call the method that reads and validates inputs
Call the method performing calculations based on the validated inputs
Call the method performing outputs

Choose better names for your objects. a, b, and indx tell me little and are hard to follow.  Especially with indx and this notion of pointing to an indx.  C# has wonderfully modern features like classes.  Something like:

public class Interval
{
    public int Start { get; set; }
    public int End { get; set; }
}

Ditch using pointers to another array.  I see no reason to use a[indx[i], 0].  In conjunction with using a class or struct, there's no reason to have a multi-dimensional array.

Imagine how easy it would be to follow your logic that instead of cryptically using:

last = b[i];

Where it's easy to get lost on b[i] and wonder what last means (e.g. does it mean last element in the array or last value you worked with), that you could instead have a List<Interval> (or if you insist Interval[]) in a variable named intervals and you could use:

largestEnd = intervals[i].End;

It's much easier for someone to follow what you mean.  And once they can follow that, they will be better positioned to comment on the algorithm.


Fast Stream Formatting Into String I am trying to find a way to convert printable data types into a string in the fastest way possible.

I originally read that a static variable of stringstream that does all of the formatting is one of the fastest ways, since constantly constructing temporary variables of stringstream is slow.

The problem with using stringstream.str() is because it creates a copy of the entire string, which may lead to performance issues, so I made this function to get rid of the need of stringstream.str().

#include <iostream>
#include <sstream>
#include <streambuf>
#include <vector>
#include <string>

#define ALL(c) (c).begin(), (c).end()

stringstream str_buffer;

string extract()
{
    streambuf& buffer = *str_buffer.rdbuf();
    vector<char> sequence(str_buffer.tellp());
    buffer.sgetn(sequence.data(), str_buffer.tellp());

    str_buffer.seekp(0);
    buffer.pubseekpos(0);
    return string(ALL(sequence));
}

To use this function, just do str_buffer << var; string as_str = extract(); to get var as a string.

However, I have not yet compared timing benchmark results of this function and simply using stringstream.str(), so I hope that my function is faster if it is in theory. Any suggestions to further improve?

Your function modifies the get/put position of the buffer.  I think this is a bug, and it makes benchmarks misleading.  Try calling extract twice in a row -- you'll get different results.  You set the put position after calling sgetn but you should have set the get position.  This should be intuitive.  After a read, you "undo" your reading.  Fix the bug with something like this:

string extract() {
    streambuf& buffer = *str_buffer.rdbuf();
    vector<char> sequence(str_buffer.tellp());
    auto g = str_buffer.tellg();
    buffer.sgetn(sequence.data(), str_buffer.tellp());
    str_buffer.seekg(g); // seekg to the original position
    // as far as I can work out, buffer.pubseekpos is not necessary here?
    return string(ALL(sequence));
}

Your function still does not compute the same thing as str.  str returns the entire buffer.  Your function returns from the input position to the output position.  These are different -- try calling str_buffer.seekg(3) before comparing the output of the two functions if you want to see for yourself.  You could seekg(0) before you call sgetn:

    auto g = str_buffer.tellg();
    str_buffer.seekg(0);
    buffer.sgetn(sequence.data(), str_buffer.tellp());
    str_buffer.seekg(g);

I think this implementation is now correct enough to benchmark.  I tried the updated version vs str on http://quick-bench.com.  I used clang-9 and libstdc++(GNU).  I tried a stringstream with 1000 characters and also 10,000 characters.

This implementation is about 130 times slower than str with no optimizations and with -O1/Clang, and it is and 3.5 times slower with -O2/Clang.

How can you speed up your function?  Well the easiest way is to use str!  But let's make some small improvements.  You copy the buffer into a vector<char> and then copy the vector into a string.  What if we only have one string?

string extractOneString() {
    std::string sequence;
    sequence.resize(str_buffer.tellp());
    auto g = str_buffer.tellg();
    str_buffer.seekg(0);
    str_buffer.rdbuf()->sgetn(sequence.data(), str_buffer.tellp());
    str_buffer.seekg(g);
    return sequence;
}

Now the unoptimized version is 3.5 times slower -- just like the optimized version before.  As it turns out, the Clang's -O2 was already making this change for you.

Still, 3 times slower is not good.

This is maybe not obvious, but if you look at the assembly (perhaps using http://godbolt.org), you'll notice that resize calls memset to set the new buffer to zero.  That's not necessary since you're about to overwrite the buffer anyway.  There's no easy way to get around this (unless you count using str).  I think this contributes to the 3x slowdown (not sure and I don't think it's worth confirming).

A few notes about your code:

Don't use using namespace std.  People have written about this in lots of places so I won't here.
The ALL macro is ugly and unnecessary.  If you cannot stand to write iterators, look into the new ranges library.

It's worth learning sooner rather than later not to spend time optimizing the wrong thing.  You wrote this code and then (I) measured it.  Next time, measure your code first and then decide whether it's worth changing.  This has the added advantage that you're already set up to measure the code post change.

I think it's also worth focusing on the basic semantics of your program before worrying too much about measured performance.  An experienced C++ dev would see right away that your extract function has a unnecessary copies and would most likely fix that before profiling.  Learning to avoid copies and other idioms will help you avoid having to measure every little thing.


User name and password validation in a MVP application In a WinForms application I'm doing the password validation as follows:

When the user presses the OK button after entering username and password, an event will be fired and the listener in the presenter will then do the validation with the help of the Encryption class. It will basically compare the two hash values.

User Model

class User
{
    string UserID { get; set; }
    string Name { get; set; }
    string NIC {get;set;}
    string Designation { get; set; }
    string PassWord { get; set; }
    List<string> Permission = new List<string>();
    bool status { get; set; }
    DateTime EnteredDate { get; set; }

}

Login form

public partial class frmLogin : Form , IView
{
    public event EventHandler OnValidatePassword;

    public string UserName
    {
        get { return txtUser.Text; }
    }

    public string Password
    {
        get { return txtPassword.Text; }
    }

    public bool Valid { get; set; }

    private void btnOK_Click(object sender, EventArgs e)
    {

        OnValidatePassword(sender, e);
        if (Valid)
        {
            frmMain Main = new frmMain();
            Main.ShowDialog();
        }
    }
}

Presenter

class LoginPresenter
{
    IView _View;
    User _Model;
    DataService _DataService;

    public LoginPresenter( IView view, User model, DataService dataService )
    {
        _View = view;
        _Model = model;
        _DataService = dataService;
        SetModelPropertiesFromView();
        WireUpEvents();
    }

    private void SetModelPropertiesFromView()
    {
        _Model.UserName = _View.UserName;
        _Model.Password = _View.Password;
    }

    private void WireUpEvents()
    {
        _View.OnValidatePassword += new EventHandler(_View_OnValidatePassword);
    }

    void _View_OnValidatePassword(object sender, EventArgs e)
    {
        ValidatePassword();
    }

    private void ValidatePassword()
    {
        var hash = Encryption.GetHash(_Model.UserName, _Model.Password);
        var hashInDB = _DataService.GetUserCredentials( _Model.UserName); //returns a hash value

        if (hash != hashInDB)
        {
            MessageBox.Show("Invalid username or password");
            _View.Valid = false;
        }
        else
        {
            _View.Valid = true;
        }
    }
}

Encryption

class Encryption
{
    public static string GetHash(string salt, string password)
    {
        MD5CryptoServiceProvider hash = new MD5CryptoServiceProvider();
        byte[] plainTextBytes = Encoding.UTF8.GetBytes(salt + password);
        byte[] hashBytes = hash.ComputeHash(plainTextBytes);

        string hashValue = Convert.ToBase64String(hashBytes);
        return hashValue;

    }
}

I'm unsure of the way I'm calling main form's ShowDialog() method in the login form.  In that case I'm not using a presenter for the main form as it is just a MDI form which is only holding links to other forms.

Would MD5 encryption would be enough in this level?

Could you please review this code and provide your feedback?

For the GetHash() function you could go with PBKDF2. It was specifically created to address password hashing. It requires at least 8 bytes of salt, so the code below builds a SHA1 hash to "stretch" your salt to that minimum length. The better approach would be to generate a cryptographically-strong random salt and store that along with the resulting hash. (c.f. RNGCryptoServiceProvider)

public static string GetHash(string salt, string password)
{
    if (string.IsNullOrEmpty(salt))
    {
        throw new ArgumentNullException("salt");
    }

    if (string.IsNullOrEmpty(password))
    {
        throw new ArgumentNullException("password");
    }

    byte[] passwordSaltBytes = System.Text.Encoding.UTF8.GetBytes(salt);

    if (passwordSaltBytes.Length < 8)
    {
        using (var saltStretcher = System.Security.Cryptography.SHA1.Create())
        {
            passwordSaltBytes = saltStretcher.ComputeHash(passwordSaltBytes);
        }
    }

    using (var pbkdf2 = new System.Security.Cryptography.Rfc2898DeriveBytes(password, passwordSaltBytes, 10000))
    {
        return Convert.ToBase64String(pbkdf2.GetBytes(20));
    }
}


Rounding and formatting hours, minutes, seconds as HH:MM AM/PM I have a program which is supposed to convert standard time to traditional time. (e.g: 15:24:31 = 3:25PM [rounded seconds])

I would like for someone to error check my code for me as well as give me ideas on how to condense it.

I'm not sure if I'm allowed to post a program here because of safety issues but here is the exe.

Here is the program. Excuse the spelling mistakes regarding "Standared".

  private void button1_Click(object sender, EventArgs e)
{
    double Hours = double.Parse(textBox1.Text);
    double Minutes = double.Parse(textBox2.Text);
    double Seconds = double.Parse(textBox3.Text);

    if (Hours > 24 || Minutes >= 60 || Seconds >= 60)
    {
        label1.Text = "Please type in proper values.";
    }
    else if (Hours == 0 && Minutes == 0 && Seconds == 0)
    {
        label1.Text = "The traditional time is 12:00 AM";
    }
    else if (Hours == 0 && Minutes < 10)
    {
        label1.Text = "The traditional time is 12:0" + Minutes + " AM";
    }
    else if (Hours == 23 && Minutes == 59 && Seconds >= 30)
    {
        label1.Text = "The traditional time is 12:00 AM";
    }
    else if (Hours == 12 && Minutes == 59 && Seconds >= 30)
    {
        label1.Text = "The traditional time is 1:00 PM";
    }
    else
    {
        label1.Text = "The traditional time is " + Converter(Hours);
    }
}
public string Converter(double Input)
{
    String Final;
    double H = double.Parse(textBox1.Text);
    double M = double.Parse(textBox2.Text);
    double S = double.Parse(textBox3.Text);
    string AMPM = "";
    if (M == 59 && S == 59)
    {
        H = H + 1;
        M = 0;
        S = 0;
    }
    if (H == 12)
    {
        AMPM = "PM";
    }
    else if (H == 24)
    {
        H = 12;
        AMPM = "AM";
    }
    else if (H > 12)
    {
        H = H - 12;
        AMPM = "PM";
    }
    else if (H < 12)
    {
        AMPM = "AM";
    }
    if (S >= 30)
    {
        S = 1;
        if (S==1)
        {
            M = S + M;
        }
    }
    else
    {
        S = 0;
    }

    if (M == 0)
    {
         Final = H.ToString() + ":" + M.ToString() + "0 " + AMPM;
    }
    else if (M == 1 || M == 2 || M == 3 || M == 4 || M == 5 || M == 6 || M == 7 || M == 8 || M == 9)
    {
        Final = H.ToString() + ":0" + M.ToString() + " " + AMPM;
    }
    else
    {
        Final = H.ToString() + ":" + M.ToString() + " " + AMPM;
    }

    return Final;
}
}
}

DateTime handling
It's possible that you're prohibited from using the DateTime struct in this method since this is apparently homework. But, in case you're not aware, problems which are as common as parsing and formatting dates and times generally already have very sophisticated and well-designed solutions. In this case, it's .NET's System.DateTime, in particular the overload of ToString which takes a format string, and TryParse. You can find these both documented on the msdn site. Using that, I believe you would be able to condense all your code down to just a few lines.
Naming
By convention, variables local to methods are named in camelCase- i.e. the first letter should be lower case. So Hours should be hours, etc. This also applies for method parameters- Input should be input.
You seem to be using the default naming for your controls- label1, button1, etc. These should be given descriptive names, like all other variables.
You change conventions inside Converter. Why is something which was Hours in a different method now H? Prefer the more descriptive name (hours, once the casing is fixed).
Another convention is that classes should be named as nouns, and methods as verbs. So instead of Converter, you should use Convert. Often, something in the form VerbNoun is the most descriptive: ConvertTime, for example.
Numeric types
Looking at your code, it seems like your hours, minutes and seconds are expected to be integers. So why are you parsing them into doubles? This is going to lead to all sorts of potential issues- rounding can cause unexpected results when doing equality comparisons for example. If you want a variable which only stores whole numbers, it's very important you use an integer type- generally int unless you have a good reason to pick another.
Cleaning up
Okay, here's the big one. It's pretty unpleasant how button1_Click handles a bunch of special cases, then if it's not any of those, hands over to Converter, which itself has a whole lot of complex logic. Let's work out how we can do this better.
As I said earlier, the best way to do this is to use DateTime, but that's not really saying much useful about the code you wrote, and for all I know you may have a requirement not to use those in-built methods. So I'll work on the assumption you have to do all the tricky time handling yourself.
Probably the first thing to notice is that the handling of seconds, minutes and hours are almost completely independent from each other. Here's our aim for each one:

Seconds: Decide whether we need to round up to the next minute
Minutes: Add one if we've rounded up the seconds. Check for the special case that we went from 59 minutes to 60, in which case we need to tick over to the next hour.
Hours: Add one if we rounded up a minute from 59. Decide whether it's AM or PM. If it's PM, subtract 12 from the number.

Let's address these one by one.
Seconds
As you can see from the description above. Seconds are really simple. We really only need to decide whether they're greater than or equal to 30, then we can forget about them. But look at how much complexity they have in the code:
if (M == 59 && S == 59)

and
if (S >= 30)
{
    S = 1;
    if (S==1)
    {
        M = S + M;
    }
}
else
{
    S = 0;
}

Plus the repeated individual checks in button1_click.
So forget all that, we want a super-simple way to ask "do I need to round up my minutes?":
private bool DoMinutesRequireRoundUp(int seconds)
{
    return seconds >= 30;
}

There we go, that's all we need for seconds!
Minutes
Now we get a bit more complex. We have two questions to ask here:
Will rounding up minutes put us into the next hour?
What will the minutes value be after we've done any necessary rounding of seconds?
In your code you've handled this with a bunch of special cases sprayed all over the place of minutes being 59. But again, there's no need for that!
Let's start with the first, again as its own method:
private bool DoMinutesRoundUpToNextHour(int minutes, bool roundUpMinutes)
{
    return roundUpMinutes && minutes==59;
}

Now we have that, we're better equipped to tackle the second
private int GetRoundedMinutes(int minutes, bool roundUpMinutes)
{
    if(DoMinutesRoundUpToNextHour(minutes, roundUpMinutes))
    {
        return 0;
    }
    if(roundUpMinutes)
    {
        minutes++;
    }
    return minutes;
}

See how we've separated out this question from any concern of what exactly the seconds are, or- even more irrelevant- what the hours are.
Hours
And finally, the hours! In your code, you try to do things in a very mixed-up way, in which AM and PM checking is all jumbled up with subtracting 12, rounding minutes, and so on. There are a few steps here, but actually we can address them quite separately as long as we do them in the right order.
Here's what we need to do, and note how each task may be dependent on tasks before it, but not after it:

Add one if the minutes were rounded up from 59 to 00
Subtract 24 if the hours are greater than 23
Decide whether we should display "AM" or "PM"
Subtract 12 if the hours are greater than 12

Not trivial, but taking them one at a time, they're not too bad either. First, numbers 1 and 2:
private int GetRoundedHours(int hours, bool incrementHours)
{
    if(incrementHours)
    {
        hours++;
    }
    return hours % 24;
}

Then 3:
private string GetPeriod(int hours)
{
    return hours < 12 ? "AM" : "PM";
}

And finally 4:
private int Get12HourTime(int hours)
{
    return hours <= 12 ? hours : hours - 12;
}

Gluing it together
So that's a bunch of methods! But now putting it all together is very easy. Let's look at how they'd work in Convert.
First, I'm going to fix the Input thing. This is pretty confusing, as it's never used. Instead I'm going to have the time elements actually passed in and used.
private string ConvertTime(int seconds, int minutes, int hours)
{
    var roundUpMinute = DoMinutesRequireRoundUp(seconds);
    var incrementHour = DoMinutesRoundUpToNextHour(minutes, roundUpMinute);
    var roundedHour = GetRoundedHours(hours, incrementHour);

    var displayMinutes = GetRoundedMinutes(minutes, roundUpMinute);
    var displayHours = Get12HourTime(roundedHour);
    var period = GetPeriod(roundedHour);

    return displayHours.ToString() + ":" + displayMinutes.ToString() + " " + period;
}

One thing this doesn't address is the leading zero for minutes < 10, but this can very easily be done in a few extra lines.
It's hard to do a line-by-line comparison of this to your version, because it's quite structurally different, but the key is to see how we've separated out each individual question we need answered into its own piece of code, and decoupled those questions from each other. We don't do a check like:
if (Hours == 23 && Minutes == 59 && Seconds >= 30)

Because that's conflating 3 different questions ("Do we need to round up to the next minute?", "Do we need to round up to the next hour?", "Do we need to round up to the next day"?) which we should answer separately.


Submit form additions or changes using AJAX, and display result I am submitting my form using ajax. Here is the actual code:

// generic ajax caller
function ajaxHandler(url, data, options)
{
    return $.ajax($.extend({
            type: 'POST',
            url: url,
            dataType: 'json',
            data: data,
            success: function (data) {
                return data;
            },
            error: function (xhr, textStatus, error) {
                return error;
            },
        }, options))

};

   // This code handles course submission form

     $('#add-course').on('submit', function (e) {
    e.preventDefault();

    var form = $(this);

    ajaxHandler(form.url, form.serialize()).then(function (result) {

        console.log('#############');

        $('.field-error, .success, .error').remove();
        if(result.errorType == "fieldErrors")
        {
            // handle field errors
            $.each(result.data, function (key, value) {
                console.log(key, value);
                $(' ' + value.msg + '').insertBefore('#' + value.param);
            });
        }

        else if(result.errorType == "formErrors")
        {
            // handle form errors
            $('
' + result.message + '
').insertBefore(form);
        }

        else
        {
            // success
            form[0].reset();
            $('
' + result.message + '
').insertBefore(form);
        }

    })
    .fail(function (error) {
        $('
Error connecting server
').insertBefore(form);
    });

});

// Here is code which handles update course form
$('#change-course').on('submit', function (e) {
    e.preventDefault();

    var form = $(this);

    ajaxHandler(form.url, form.serialize()).then(function (result) {

        $('.field-error, .success, .error').remove();
        if(result.errorType == "fieldError")
        {
            // handle field errors
            $.each(result.data, function (key, value) {
                console.log(key, value);
                $(' ' + value.msg + '').insertBefore('#' + value.param);
            });
        }

        else if(result.errorType == "formError")
        {
            // handle form errors
            $('
' + result.message + '
').insertBefore(form);
        }

        else
        {
            // success
            $('
' + result.message + '
').insertBefore(form);
        }

    })
        .fail(function (error) {
            $('
Error connecting server
').insertBefore(form);
        });
});

As you can see the structure of add/update form is almost the same. How can I refactor all this?

I think most of the code duplication can be taken care of by simply creating success and failure functions to handle the ajax response for both your forms. Additionally, if you're only sometimes going to pass a value to options in the ajaxHandler function, you should check if it's undefined.

// generic ajax caller
function ajaxHandler(url, data, options) {
  var ajaxOptions = {
    type: 'POST',
    url: url,
    dataType: 'json',
    data: data,
    success: function(data) {
      return data;
    },
    error: function(xhr, textStatus, error) {
      return error;
    }
  };
  return (options === undefined) ? $.ajax(ajaxOptions) : $.ajax($.extend(ajaxOptions, options));
};

function success(result, form, reset) {
  $('.field-error, .success, .error').remove();
  if (result.errorType == "fieldErrors") {
    // handle field errors
    $.each(result.data, function(key, value) {
      console.log(key, value);
      $(' ' + value.msg + '').insertBefore('#' + value.param);
    });
  } else if (result.errorType == "formErrors") {
    // handle form errors
    $('
' + result.message + '
').insertBefore(form);
  } else {
    // success
    if (reset) {
      form[0].reset();
    }
    $('
' + result.message + '
').insertBefore(form);
  }
}

function failure(form) {
  $('
Error connecting server
').insertBefore(form);
}

// This code handles course submission form
$('#add-course').on('submit', function(e) {
  e.preventDefault();
  var form = $(this);
  ajaxHandler(form.url, form.serialize())
    .then(function(result) {
      console.log('#############');
      success(result, form, false);
    })
    .fail(function(error) {
      failure(form);
    });
});

// Here is code which handles update course form
$('#change-course').on('submit', function(e) {
  e.preventDefault();
  var form = $(this);
  ajaxHandler(form.url, form.serialize())
    .then(function(result) {
      success(result, form, true);
    })
    .fail(function(error) {
      failure(form);
    });
});


Refactoring and condensing a Javascript function with many repeat conditions, strings, and variables I have this function which is pretty easy to read and works just fine. I'm looking to advance my coding abilities by writing more concise code, though.

Does anyone know of an elegant way to condense this down? Any pointers very much appreciated! Thank you!

var $_GET = {};

document.location.search.replace(/\??(?:([^=]+)=([^&]*)&?)/g, function () {
    function decode(s) {
        return decodeURIComponent(s.split("+").join(" "));
    }

    $_GET[decode(arguments[1])] = decode(arguments[2]);
});

function create_filter_input($name, $termname) {
    var $input = '<input class="query-input" type="hidden" value="' + $termname + '" name="' + $name + '" />';
    return $input;
}

area = $_GET["area"],
type = $_GET["property_type"],
style = $_GET["style"],
feature = $_GET["feature"],

if(area || type || style || feature) {
    if(area) {
        areainput = create_filter_input('area',area);
        $filterTerms.append(areainput);
    }

    if(type) {
        typeinput = create_filter_input('property_type',type);
        $filterTerms.append(typeinput);
    }

    if(style) {
        styleinput = create_filter_input('style',style);
        $filterTerms.append(styleinput);
    }

    if(feature) {
        featureinput = create_filter_input('feature',feature);
        $filterTerms.append(featureinput);
    }
}

This is my current solution based on your answers! I think it's pretty concise. Let me know what you think! thanks again.

function create_filter_input($name, $termname, $filterterms) {
    if($termname) {
        var $input = '<input class="query-input" type="hidden" value="' + $termname + '" name="' + $name + '" />';
        $filterterms.append($input);
    }
}

create_filter_input('area',area,$filterTerms);
create_filter_input('property_type',type,$filterTerms);
create_filter_input('style',style,$filterTerms);
create_filter_input('feature',feature,$filterTerms);

Try to avoid repetition.

var args, i, check, len, filtered;

function parseUrl() {
    var getArgs = {};

    function decode(s) { // declare this function only once, don't declare functions inside any kind of loop
        return decodeURIComponent(s.replace(/\+/g, ' '));

    document.location.search.replace(/\??(?:([^=]+)=([^&]*)&?)/g, function () {
        getArgs[decode(arguments[1])] = decode(arguments[2]);
    });

    return getArgs;
}

function create_filter_input($name, $termname) {
    var $input = '<input class="query-input" type="hidden" value="' + $termname + '" name="' + $name + '" />';
    return $input;
}

args = parseUrl();
check = ['area', 'property_type', 'style', 'feature'];
len=check.length;

for(var i=0; i<len; i++) {
    if (!args[check[i]]) {
        continue;
    }
    filtered = create_filter_input(check[i], args[check[i]]);
    $filterTerms.append(filtered);
}

Try to write code anticipating change and write it to make your life easy. For example this:

type = $_GET["property_type"],

creates a variable named type but you then effectively need a map to get back to "property_type":

create_filter_input('property_type',type);

Is the same as:

create_filter_input('property_type', $_GET["property_type"]);

(Which, incidentally is the same as: create_filter_input('property_type', $_GET.property_type); - use dot notation where possible.)

If you write it like that - seeing that you are passing (almost) the same argument in all use cases to your create_filter_input function - you can start to see/think that you don't need 2 local variables - just having "property_type" is enough.

As one of the other answers says - don't serially append to the dom. each write is relatively expensive. it's better to build a dom fragment and append it to the dom in one go.


Adding two numbers, each digit as a single element of array After failing to answer an interview question, I went back home and coded the answer for my own improvement.
The questions was: Given two arrays containing a number, but with each element of the array containing a digit of that number, calculate the sum and give it in the same format.There must be no leading zeros in the resulting array.

My main concern is that I am being redundant with my logic, or that my code is not clear.

 int *sumOfTwo(int *a1,int *a2, int lengthOfA1, int lengthOfA2, int *lengthDest) {

      //I assume there is error checking for null pointers, etc.
      int *answer;
      int maxSize, minSize, diff;
      int a1IsLongest = TRUE;
      if(lengthOfA1 > lengthOfA2) {
          maxSize = lengthOfA1;
          minSize = lengthOfA2;
          a1IsLongest = TRUE;
      }
      else {
          maxSize = lengthOfA2;
          minSize = lengthOfA1;
          a1IsLongest = FALSE;
      }
      diff = maxSize - minSize;
      answer = malloc(maxSize * sizeof(int));
      int i, extraTen, result;
      extraTen = 0;

      *lengthDest = maxSize;
      //printf("This is lengthDest: %d\n", *lengthDest);

      for (i = maxSize-1; i >= 0; i--) {

          //add numbers, check if bigger than 10
         //check if arrays are of different sizes we want to access
         //the end from each, so need to account for this.

          if(diff == 0) {
              //arrays are equal in size
              result = a1[i] + a2[i] + extraTen;
              extraTen = 0;
          }
          else{
              //arrays are different sizes
              if(! ((i - diff) < 0)) {
                  if(a1IsLongest) {
                      result = a1[i] + a2[i - diff] + extraTen;
                      extraTen = 0;
                  }
                  else {
                      result = a1[i - diff] + a2[i] + extraTen;
                      extraTen = 0;
                  }
              }
              else {
                  if(a1IsLongest) {
                  result = a1[i] + extraTen;
                  extraTen = 0;
              }
              else {
                  result = a2[i] + extraTen;
                  extraTen = 0;
              }
          }
      }

      //the new malloc can only happen here
      if (result >= 10) {
         //check if at beginning of array
         if(i == 0) {

              maxSize = maxSize + 1;
              *lengthDest = maxSize;
              //printf("This is lengthDest: %d\n", *lengthDest);

              //overflowing, need to realloc
              int *temp = malloc(maxSize * sizeof (int));
              int j;
              //copy old elements into new array
              for(j = 0; j < maxSize; j++) {
                  //printf("index: %d\n", j);
                  if(j == 0) {
                      temp[j] = 1;
                  }
                  else if(j == 1) {
                      temp[j] = result % 10;
                  }
                  else {
                      temp[j] = answer[j-1];
                  }
              }

              free(answer);
              answer = temp;
              return answer;
          }
          else{
              //printf("in the else of the i equals 0.\n");
              answer[i] = result % 10;
              extraTen = 1;
          }
      }
      else {
         //printf(" results is less than 10\n");
         answer[i] = result;
     }
 }
 return answer;
}

I see some things that may help you improve your code.

Use const where practical

The sumOfTwo() function doesn't (and probably shouldn't) modify the passed integer arrays, so they should be declared const.

Show all required headers

The code uses malloc and free but the code does not show a the required include file.  For code reviews (and job interviews!), it's best to list the required includes.  This code needs only:

#include <stdlib.h>

Use stdbool.h when needed

This code contains lines like this:

int a1IsLongest = TRUE;

However, there are already bool types and values supported in the stdbool.h header.  Prefer those to non-standard types and values.  The line above would then be:

bool a1IsLongest = true;

Fix formatting

The indentation is not consistent, and in one case, there's a space between else and the following { but in other case there's no space.  Which convention you use is less important than choosing one and following it consistently.

Simplify your code

There are a number of extra variables and comparisons to determine which array is larger.  Why not instead simply assume that a1 is longer than or equal in length to a2 and then make that true?  It would simplify the code a lot.  For example, one could start the code this way:

if (lengthOfA1 < lengthOfA2) {
    // swap the arguments to ensure a1 is not shorter than a2
    int *temp = a1;
    int templen = lengthOfA1;
    a1 = a2;
    lengthOfA1 = lengthOfA2;
    a2 = temp;
    lengthOfA2 = templen;
}

Assume a convenient data structure unless otherwise specified

It's not clear whether you were told that the data structure had the least significant or most significant digit first or whether either had leading zeroes.  The most convenient data structure would actually be to store the data with the least significant digit first, as I'll demonstrate in the next suggestion.

Allocate memory only once

The current code allocates some memory and then may allocate again if more is needed, copying the elements from the old to the new array.  There are several strategies that would allow you to allocate memory only once.

The first is to note that the maximum additional memory required would be exactly one int and to simply allocate enough space for that, with the understanding that there would be, potentially, a leading zero in the answer.

The second would be to determine if a carry will be required and allocate space accordingly.  One way to do that would be to make two passes through the data.

The other possibility is to adjust the allocated length after calculation.  This could be done very simply using the realloc function.

Prefer "less expensive" to "more expensive" operations

If the digits are decimal digits (not stated, but assumed), then the largest possible sum will be 9+9=18, so the largest possible carry value is 1.  If the resulting value is greater than 10, the current code uses this code:

answer[i] = result % 10;

The % operator typically does a division which is computationally expensive on many platforms.  Better is to simply use subtraction and the fact that the carry can only possibly be equal to 1 or 0.

if (result >= 10) {
    result -= 10;
    carry = 1;
}

Check for memory allocation failure

Calls to malloc can fail.  Robust code should check for that and handle the out-of-memory condition appropriately.

Putting it all together

Here's a version incorporating all of these suggestions:

int *sumOfTwo(const int *a1, const int *a2, int lengthOfA1, int lengthOfA2, int *lengthDest)
{
    if (lengthOfA1 < lengthOfA2) {
        // swap the arguments to ensure a1 is not shorter than a2
        const int *temp = a1;
        int templen = lengthOfA1;
        a1 = a2;
        lengthOfA1 = lengthOfA2;
        a2 = temp;
        lengthOfA2 = templen;
    }
    *lengthDest = lengthOfA1 + 1;
    int *result = malloc(*lengthDest*sizeof(a1[0]));
    if (result == NULL) {
        *lengthDest = 0;
        return NULL;
    }
    // copy a1 into result
    memcpy(result, a1, lengthOfA1*sizeof(a1[0]));
    result[lengthOfA1] = 0;
    int carry = 0;
    int *end = result + *lengthDest;
    int val;
    // add in place
    for (int *digit = result; digit != end; ++digit) {
        val = carry + *digit;
        if (lengthOfA2) {
            val += *a2++;
            --lengthOfA2;
        }
        if (val >= 10) {
            val -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
        *digit = val;
    }
    return result;
}

Test harness

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

// sumOfTwo() goes here

void printnum(const int *num, int len, int desiredlen)
{
    for (; desiredlen > len; --desiredlen) {
        printf(" ");
    }
    for (num += len - 1; len; --len, --num) {
        printf("%u", *num);
    }
    puts("");
}

struct number {
    int len;
    int digits[5];
};

struct test {
    struct number n1, n2, expected;
};

struct test tests[] = {
    { { 1, {9} }, { 1, {9} }, { 2, { 8, 1 } }},
    { { 3, {8, 9, 9}}, {2, {1, 9}}, { 4, { 9, 8, 0, 1}}},
    { { 3, {8, 9, 9}}, {3, {0, 0, 1}}, { 4, {8, 9, 0, 1}}},
};

bool doTest(const struct test* t) {
    int lengthDest;
    int *answer = sumOfTwo(t->n1.digits, t->n2.digits, t->n1.len, t->n2.len, &lengthDest);
    printnum(t->n1.digits, t->n1.len, 5);
    printnum(t->n2.digits, t->n2.len, 5);
    puts("-----");
    printnum(answer, lengthDest, 5);
    if (lengthDest != t->expected.len) {
        free(answer);
        return false;
    }
    for (int i = 0; i < lengthDest; ++i) {
        if (t->expected.digits[i] != answer[i]) {
            free(answer);
            return false;
        }
    }
    free(answer);
    return true;
}

int main()
{
    int testcount = sizeof(tests) / sizeof(tests[0]);
    for (int i=0; i < testcount; ++i) {
        printf("Test %d: %s\n\n", i+1, doTest(&tests[i]) ? "OK " : "BAD");
    }
}

Test result

Here is the output of the test program:

    9
    9
-----
   18
Test 1: OK

  998
   91
-----
 1089
Test 2: OK

  998
  100
-----
 1098
Test 3: OK


Diff comparison for List List<string> difference tool for two input List<string> listA and listB

Output List<string>

both - in both listA and listB
listAonly - in listA only
listBonly - in listB only

Looking for speed, space, and style

.

//test
List<string> both;
List<string> both;
List<string> listAonly;
List<string> listBonly;
ListDiff( new List<string>() { "AAA", "BBB", "CCC", "DDD", "GGG", "FFF", "BBB", "GGG" }
        , new List<string>() { "AAA", "BBB", "DDD", "FFF", "EEE", "FFF", "EEE" }
        , false, out both, out listAonly, out listBonly );
Debug.WriteLine("both");
foreach (string s in both)
    Debug.WriteLine($"  {s}");
Debug.WriteLine("listAonly");
foreach (string s in listAonly)
    Debug.WriteLine($"  {s}");
Debug.WriteLine("listBonly");
foreach (string s in listBonly)
    Debug.WriteLine($"  {s}");
//end test

public static void ListDiff(List<string> listA, List<string> listB, bool ignoreCase, out List<string> both, out List<string> listAonly, out List<string> listBonly)
{
    both = new List<string>();
    listAonly = new List<string>();
    listBonly = new List<string>();

    IEnumerable<string> listAsorted = listA.OrderBy(x => x).Distinct();
    IEnumerable<string> listBsorted = listB.OrderBy(x => x).Distinct();

    var listAenumerator = listAsorted.GetEnumerator();
    var listBenumerator = listBsorted.GetEnumerator();

    bool listAcanmove = listAenumerator.MoveNext();
    bool listBcanmove = listBenumerator.MoveNext();

    while (listAcanmove | listBcanmove)
    {
        string valueA = listAenumerator.Current;
        string valueB = listBenumerator.Current;

        //Debug.WriteLine($"valueA = {valueA}");
        //Debug.WriteLine($"valueB = {valueB}");

        if (!listAcanmove && listBcanmove)
        {
            //Debug.WriteLine($"{valueB} in B not in A");
            listBonly.Add(valueB);
            listBcanmove = listBenumerator.MoveNext();
        }
        if (listAcanmove && !listBcanmove)
        {
            //Debug.WriteLine($"{valueA} in A not in B");
            listAonly.Add(valueA);
            listAcanmove = listAenumerator.MoveNext();
        }
        else
        {
            int comp = string.Compare(valueA, valueB, ignoreCase);
            if (comp == -1)
            {
                //Debug.WriteLine($"{valueA} in A not in B");
                listAonly.Add(valueA);
                listAcanmove = listAenumerator.MoveNext();
            }
            else if (comp == 1)
            {
                //Debug.WriteLine($"{valueB} in B not in A");
                listBonly.Add(valueB);
                listBcanmove = listBenumerator.MoveNext();
            }
            else
            {
                //Debug.WriteLine($"{valueA} {valueB} in B and A");
                both.Add(valueA);
                listAcanmove = listAenumerator.MoveNext();

                listBcanmove = listBenumerator.MoveNext();
            }
        }
        //Debug.WriteLine("");
    }
    //Debug.WriteLine($"done");
}

I wouldn't want to maintain this code. Unless you have proven that this code is a performance problem, do the simple thing. Yes, the following solution will iterate over the lists 3 times. No, I don't care that it does.

var both = listA.Intersect(listB);
var listAOnly = listA.Except(listB);
var listBOnly = listB.Except(listA);

If you're worried about case insensitivity, pass in a StringComparer.


XML format for mp3 files I'm developing a desktop app that will scan a user's system for mp3 files and send their whole collection to a website. I'm assuming the best file format for sending this data to a server would be XML -- although correct me if I'm wrong.

Can someone kindly comment on whether the formatting of the sample XML file below looks okay? Thanks!

<?xml version="1.0" encoding="utf-8"?>
<collection>
    <artist name="Michael Jackson">
        <track>Beat It</track>
        <track>Thriller</track>
    </artist>
    <artist name="The Beatles">
        <track>Hey Jude</track>
        <track>Yellow Submarine</track>
    </artist>
    <artist name="Eminem">
        <track>Lose Yourself</track>
        <track>Without Me</track>
    </artist>
</collection>

You may run into a problem if a track has more than one artist.

You'd have to enter the track for each artist again, or you'd have to only use the first artist, or you'd have to create a new "combined" artist.

Why not omit the artist→track hierarchy?

<collection>
  <track>
    <title>Thriller</title>
    <artist>Michael Jackson</artist>
  </track>
  <track>
    <title>Hey Jude</title>
    <artist>The Beatles</artist>
  </track>
</collection>

Benefits:

You can add more metadata for tracks (composer, album, etc.)
You can add tracks without title and/or artist

If different artists may have the same name, you'd need a way to differentiate the artist elements; e.g. by using id with an ID of an artist database.


Simple shared resource in Python I want a 4-bit resource to share status between processes and to retain status after shutdown and reboot. If the system were a microprocessor, I'd use a 4-bit register in non-volatile memory.

Process interaction with the shared resource is typically minutes to hours between interactions, however processes may attempt to access it at exactly the same moment. So there is a simple file locking mechanism. A process that finds the resource locked, will back off for a short while and then try again.

There are only 4 or 5 processes that deal with the resource. The short while (timeout) is 15 milliseconds plus random between 0 to 9 milliseconds. This is to prevent race conditions, processes locking each other, etc.

Processes will be daemonised, and they will use the functions below to access the pickle.

To simulate different processes, I'm using a few command prompt windows, started at about the same time. See the code.

All of Python's multitasking libraries, threading, Queue and DMTCP seem way too elaborate for my tiny 4-bit register. Hence this solution. Please comment.

import cPickle as pickle
import math
from time import sleep
import sys

'''
    There are 4 switches, A to D. Each can be On or Off.
    Switches must retain state on shutdown and/or reboot.

    Switch state is stored in a pickle in switch_state.p
    Switch state is a 4-bit number, ie max 15 decimal (all On)
    Switch A is bit 0, switch B is bit 1, and so on.

    Several processes may interact with switches.
    So, also in the pickle is a boolean 'locked'.
    All processes, when switching, must load the pickle, and first check if it's locked.
    If it is, it should wait until it becomes unlocked.
    If it's not, it should lock it, do its thing, and then unlock it.
'''

def new_state(statefile='switch_state.p'):
    try:
        switch = pickle.load(open(statefile, 'rb'))
    except:
        switch = {'state':0, 'locked': False}
        pickle.dump(switch, open(statefile, 'wb'))

# functions to turn state on and off
#
# using bitwise operations, so no need to check current state
# i.e. if you turn on a switch that's already on, nothing will change

def turn_on(cur_state, switchID):
    ON_bits = pow(2, ord(switchID) - ord('A'))
    return cur_state | ON_bits

def turn_off(cur_state, switchID):
    OFF_bits = ~pow(2, ord(switchID) - ord('A'))
    return cur_state & OFF_bits

def update_state(switchID, state, statefile='switch_state.p'):
    switch = pickle.load(open(statefile, 'rb'))

    while switch['locked']:
        # some other process is switching, wait till it finishes
        sleep(0.015 + random.random()/100)
        switch = pickle.load(open(statefile, 'rb'))

    if not switch['locked']:
        new_switch = {'state': switch['state'], 'locked': True}
        pickle.dump(new_switch, open(statefile, 'wb'))
        if state == 'On':
            newstate = turn_on(switch['state'], switchID)
        elif state == 'Off':
            newstate = turn_off(switch['state'], switchID)
        else:
            #shouldn't ever get here
            print 'unknown state'
            exit()

        new_switch = {'state': newstate, 'locked': False}
        pickle.dump(new_switch, open(statefile, 'wb'))
        report = 'switch {} is now {}, switchstate {}'
        print report.format(switchID, state, newstate)

new_state()

# test the above in three or four command shells
# python switchreg.py [switchID] [delaytime]
# switchID may be A to D
# shorter delaytimes simulate race-conditions better

switchID = sys.argv[1]
delaytime = float(sys.argv[2])
endrange = int(30/delaytime) # so time taken up by iterations is about the same

for i in range(0, endrange):
    update_state(switchID, 'On')
    sleep(delaytime)
    update_state(switchID, 'Off')

The one major problem is the lack of synchronisation between processes,
even if you randomise the sleep interval, this is still an invitation
for race conditions (unless you can somehow proof that the randomisation
is good enough).

Using a library like
lockfile or directly
using e.g. fcntl.lock will take care of that.  If you are worried
about the performance, well you are using Python, with cPickle (good
point that).  Otherwise some IPC mechanism, maybe a shared semaphore
between processes, would suffice.

Next, I think you can leave the file simply open and rewind to the
start, the read again instead of constantly closing and opening.  I'm
also not sure, but you could investigate file (region) locking via
fcntl instead to provide the necessary synchronisation.

The turn_on/turn_off seems very complicated if you could just write
out a dict, sequence, whatever, instead of doing bit manipulation.
If, however, you really want that part, then be consistent and simply
write two bytes to the file instead of using pickle.  The mixture of
very high-level serialisation and low-level composition of four bits
doesn't seem necessary at all.

Otherwise looks fine.  Some common expressions could be shared and the
written data structure is mostly used without any abstraction (like you
did with new_state, a updated_state function to create the new
dict could be nice), but I guess for a small script that hardly
matters.


Bash CGI Upload File I'm using the following Bash CGI to upload a file:

#!/bin/bash
echo "Content-Type: text/plain"
echo

if [ "$REQUEST_METHOD" = "POST" ]; then
    TMPOUT=hello
    cat >$TMPOUT

    # Get the line count
    LINES=$(wc -l $TMPOUT | cut -d ' ' -f 1)

    # Remove the first four lines
    tail -$((LINES - 4)) $TMPOUT >$TMPOUT.1

    # Remove the last line
    head -$((LINES - 5)) $TMPOUT.1 >$TMPOUT

    # Copy everything but the new last line to a temporary file
    head -$((LINES - 6)) $TMPOUT >$TMPOUT.1

    # Copy the new last line but remove trailing \r\n
    tail -1 $TMPOUT | tr -d '\r\n' >> $TMPOUT.1
fi

This is for a uClinux/Busybox server. When a file is passed this way, the original $TMPOUT will contain a four line head and one line tail that need to be removed to end up with the same file. The resulting file's hash is identical to the original.

It works but it seems pretty ugly, creating two files and such. I'm by no means a pro in bash, can this be made prettier?

Keep in mind that the target is a little embedded device and has no Perl/Python or anything on it. It needs to be pure bash.

Since your script has no content to return, a status code of 204 No Content would be more desirable than 200 Success.  For that, you should echo "Status: 204 No Content" (RFC 3875 Sec 6.3.3).  Also consider returning using status code 405 Method Not Allowed for anything other than a POST request.

$TMPOUT is a misnomer.  The file is not temporary at all — $TMPOUT.1 contains the final output of your script.

If your goal is to redirect the input to a file, discarding the first four lines, the last line, and the trailing newline of the penultimate line, you don't need to execute any external commands.  Bash is fully capable of doing all of the work itself.  The script isn't pretty, but I still find it easier to understand than copying the data back and forth, extracting lines here and there each time.

#!/bin/bash

case "$REQUEST_METHOD" in
  POST)
    (
        # Discard first four lines
        read && read && read && read &&

        # Read and echo, buffering two lines
        read line1 &&
        read line2 &&
        while read nextline ; do
            echo "$line1"
            line1="$line2"
            line2="$nextline"
        done

        # Echo penultimate line with no trailing newline.
        echo -n "$line1"

        # Discard last line ($line2)
    ) > hello

    echo 'Status: 204 No Content'
    echo
    ;;

  *)
    echo 'Status: 405 Method Not Allowed'
    echo
esac


Python flask web app, simplification I am writing web application using flask framework + mongodb. I have an issue, should I use classes for my mongo entities or just use dictionaries for them.

class School:
    def __init__(self, num, addr, s_type):
        self.num = num
        self.addr = addr
        self.s_type = s_type

or just create dictionary for any entity like:

school = { "number" : request['number'] ,
           "address": request['address'],
           "type"   : request['type'] }

I'm not familiar with that framework, but if there is more than one school and you are going to use Python to access those values (such as the school's address), I'd use a class. Think of it this way: Classes are usually meant to be instantiated, or at least to be a group of functions for a specific purpose.

Instead of creating a dict for each school you simply instantiate the class:

MIT=School(1,'Cambridge','university')
Harvard=School(2,'Cambridge','university')
>>> MIT.address
'Cambridge'
>>> Harvard.s_type
'university'

Or whatever pattern you are using.

This way you can also add functions to it:

class School:
    def __init__(self, name, num, addr, s_type):
        self.num = num
        self.name = name
        self.addr = addr
        self.s_type = s_type
    def describe(self):
        print "%s is a %s located at %s." % (self.name, self.s_type, self.address)
    def request(self,arg):
        request[arg] # I'm not sure if that's what you want, I copied it from the dict you had there

>>> MIT.describe()
MIT is a university located at Cambridge.
>>> MIT.request('name')
# Whatever that thing does


Mapping .csv rows to a Dictionary I have a .csv file in which each row represents an association between a software application and a web server. My goal is to fetch a List<Server> by application, so I'm mapping the .csv to a Dictionary<string, List<Server>>. I'm using CsvHelper to read the .csv file and map it to objects.

.csv format:

Family | Environment | Name   | Application
01     | Dev         | WEBD01 | application1
01     | Production  | WEBP01 | application1
02     | Dev         | WEBD02 | application2

Server class:

public class Server
{
    public string Name { get; set; }
    public string Family { get; set; }
    public string Environment { get; set; }
}

Mapping:

protected override void RefreshData()
{
    // _serverDictionary is a class-level Dictionary<string, List<Server>>
    _serverDictionary.Clear();

    using (TextReader textReader = File.OpenText(_csvFile.FullName))
    using (CsvReader reader = new CsvReader(textReader))
    {
        while (reader.Read())
        {
            string applicationName = reader.GetField<string>("Application");
            Server server = reader.GetRecord<Server>();

            if (_serverDictionary.ContainsKey(applicationName))
                _serverDictionary[applicationName].Add(server);
            else
                _serverDictionary.Add(applicationName, new List<Server> { server });
        }
    }
}

Fetching:

public IEnumerable<Server> GetByApplication(string applicationName)
{
    List<Server> servers = new List<Server>();

    _appServers.Where(pair => pair.Key.EqualsIgnoreCase(applicationName))
        .ForEach(pair => servers.AddRange(pair.Value));

    return servers;
}

Concerns:

Is a Dictionary the best data structure to use in the first place?
I feel that both the mapping code and the fetch code could be more efficient by better utilizing LINQ projection.

I feel that both the mapping code and the fetch code could be more efficient by better utilizing LINQ projection.

more efficient yes but this time without linq.

if (serverDictionary.ContainsKey(applicationName))
    serverDictionary[applicationName].Add(server);
else
    serverDictionary.Add(applicationName, new List<Server> { server });

This is a very inconvenient way of adding new items to your dictionary because you are accessing it twice for each new item. With TryGetValue you can do the same with only one access to it. This means that if you could retrieve the value then you already have and it's ready to use, there's no need to use the indexer anymore. If however it's not there, then you just add it.

if (serverDictionary.TryGetValue(applicationName, out List<Server> servers))
{
    servers.Add(server);
}
else
{
    serverDictionary[applicationName] = new List<Server> { server };
}

_appServers.Where(pair => pair.Key.EqualsIgnoreCase(applicationName))
    .ForEach(pair => servers.AddRange(pair.Value));

This might be super inefficient. If you use a dictionary then don't use linq if you don't have to. For fetching you can use the TryGetValue method agian:

return
    serverDictionary.TryGetValue(applicationName, out List<Server> servers)
        ? servers
        : Enumerable.Empty<Server>();

Retrieving an item with TryGetValue means it's an O(1) operation whereas the same done with the original query means that the entire dictionary needs to be searched which means O(n). If you need to return a copy of the server list the you might use linq for it and call .ToList() on the servers.

There is one more thing about the linq query. You search for the key by ignoring the case. If you have multiple names but with different case then the resulting list will contain items of all those keys. Is this really what you want? The Where won't stop at the first match.

I don't know how you create the dictionary but if you want to ignore the case of the key you should initialize the dictionary appropriately by specifying the key comparer:

serverDictionary = new Dictionary<string, List<Server>>(StringComparer.OrdinalIgnoreCase);

Now the keys is case-insensitive also during adding.


DBSCAN c++ implementation For work I had to implement the DBSCAN algorithm in the 3D space for clusters finding. It works, now I wonder how is the quality of the code. I'm especially concerned about incrementing the size of the vector during the for loop in the expandCluster lambda. I followed the Wikipedia article

struct ivec3
{
    int x;
    int y;
    int z;
};

std::vector<std::vector<ivec3>> dbscan3D(std::vector<ivec3> &dataset, int eps, int min_pts)
{
    // https://en.wikipedia.org/wiki/DBSCAN

    std::vector<std::vector<ivec3>> clusters;
    int idx_current_cluster = 0;

    struct info_point
    {
        ivec3 position;
        int cluster;
    };

    std::unordered_map<int, info_point> map_info_dataset;

    auto getKey = [](ivec3 P)
    {
        return ((int64_t)P.z << 42) + ((int64_t)P.y << 21) + (int64_t)P.x;
    };

    for (auto&& P : dataset)
    {
        map_info_dataset[getKey(P)] = info_point{ P, -1 };
    }

    auto regionQuery = [&eps, &map_info_dataset, &getKey](const int key)
    {
        const auto& pos_P = map_info_dataset.at(key).position;

        std::vector<int> keys_neighborPts;

        for (int x = pos_P.x - eps; x <= pos_P.x + eps; ++x)
        {
            for (int y = pos_P.y - eps; y <= pos_P.y + eps; ++y)
            {
                for (int z = pos_P.z - eps; z <= pos_P.z + eps; ++z)
                {
                    int key = getKey({ x, y, z });

                    if (map_info_dataset.count(key))
                    {
                        keys_neighborPts.push_back(key);
                    }
                }
            }
        }
        return keys_neighborPts;
    };

    auto expandCluster = [&eps, &min_pts, &map_info_dataset, &clusters, &regionQuery]
    (const int key, std::vector<int> &keys_neighborPts, int idx_current_cluster)
    {
        clusters.at(idx_current_cluster).push_back(map_info_dataset.at(key).position);
        map_info_dataset.at(key).cluster = idx_current_cluster;

        for (int i = 0; i < keys_neighborPts.size(); ++i)
        {
            auto &local_key = keys_neighborPts[i];
            auto &local_point = map_info_dataset.at(local_key);

            if (local_point.cluster == -1)
            {
                auto keys_neighborPts_local_point = regionQuery(local_key);

                if (keys_neighborPts_local_point.size() >= min_pts)
                {
                    keys_neighborPts.insert(keys_neighborPts.end(), keys_neighborPts_local_point.begin(), keys_neighborPts_local_point.end());
                }

                clusters.at(idx_current_cluster).push_back(local_point.position);
                local_point.cluster = idx_current_cluster;
            }
        }
    };

    for (auto&& P : map_info_dataset)
    {
        const int& key_P = P.first;
        info_point& info_P = P.second;

        if (info_P.cluster != -1)
        {
            continue;
        }

        auto keys_neighborPts = regionQuery(key_P);

        if (keys_neighborPts.size() >= min_pts)
        {
            clusters.emplace_back();
            expandCluster(key_P, keys_neighborPts, idx_current_cluster);
            ++idx_current_cluster;
        }
    }

    return clusters;
}

What is generally less efficient is iterating over an unordered set. This is because the set is actually a hash table of the keys. So whenever you want to iterate over the key-value pairs, a std::map is generally better.

Also what i apparent is that there is one function to do everything. This makes the code rather hard to follow and oversee. You should rather create one function for every functionality you want to implement and build your algorithm from short but clear functions. In your case there are at least 4 natural subfunctions that occur on the first glance.


Handling duplicate keys in quicksort A naïve quicksort will take O(n^2) time to sort an array containing no unique keys, because all keys will be partitioned either before or after the pivot value. There are ways to handle duplicate keys (like one described in Quicksort is Optimal). The proposed solution only works for the Hoare partition, but I've implemented the Lomuto partition. To deal with duplicate keys, I alternated between moving duplicates to the left of the pivot and moving duplicates to the right of the pivot. Here's my quicksort (ignore the lack of generics):

public static void swap(Comparable[] sort, int a, int b){
    Comparable temp=sort[a];
    sort[a]=sort[b];
    sort[b]=temp;
}
public static void quicksort(Comparable[] sort, int start, int end){
    while(end-start>1){//normal case
        int pivot=gen.nextInt(end-start)+start;//random pivot
        swap(sort, pivot, start);
        int index=start;//walking index
        boolean dupHandler=false;//init to true works also
        for(int i=start+1; i<end; ++i){//Lomuto partition
            int val=sort[start].compareTo(sort[i]);
            if(val>0 || ( val==0 && (dupHandler=!dupHandler) ) )
                swap(sort, ++index, i);
        }
        swap(sort, start, index);
        if(index-start<end-index-1){//recurse into smaller partition
            quicksort(sort, start, index);
            start=index+1;//use iteration for other partition
        }
        else{
            quicksort(sort, index+1, end);
            end=index;
        }
    }
}

Is there a better (more efficient) way to handle duplicate keys? If not, is there any way to significantly improve my code?

Use a swap function rather then repeating the three lines required to swap elements three times
Put spaces around your operators
You avoid recursing for the second partition. I don't think the performance gain from this is sufficient for the extra complexity in your code.

Rather then swapping before/after for the element equal to the pivot, count the number of elements equal to the pivot. Then when you sort the subarray make the one subarray shorter so as not to sort the elements equal to the pivot.

Another issue as Rafe has noted is that there are other issues besides duplicate keys that can cause a O(n^2) behavior. Your code doesn't handle any of those.


C++ observer pattern via boost.signals2 I was looking for a thread safe implementation of the observer pattern. I read https://xinhuang.github.io/posts/2015-02-11-how-a-multi-threaded-implementation-of-the-observer-pattern-can-fail.html and was thinking about point 4 "Don't reinvent the wheel, use Boost.Signals2 instead". So I tried the following code and wanted to  ask if it is safe to be used in a multithreaded application? What happens if an Observer is destructed during notifyObservers?

#include <boost/signals2.hpp>
#include <iostream>
#include <string>

class AbstractObserver {
public:
    using SignalType = boost::signals2::signal<void()>;

    virtual ~AbstractObserver() = default;

    virtual void notify() = 0;

    void registerAtSubject(SignalType &sig)
    {
        connection_ = sig.connect([this]() { notify(); });
    }

private:
    boost::signals2::scoped_connection connection_;
};

class Subject {
    AbstractObserver::SignalType sig_;
public:
    void registerObserver(AbstractObserver &observer)
    {
        observer.registerAtSubject(sig_);
    }

    void notifyObservers() const
    {
        sig_();
    }
};

class Observer : public AbstractObserver {
    std::string id_;
public:
    explicit Observer(std::string id) : id_(std::move(id))
    {};

    void notify() override
    {
        std::cout << "Observer " << id_ << " got notified" << std::endl;
    }
};

int main()
{
    Subject c;
    {
        Observer o2("B");
        {
            Observer o1("A");
            c.registerObserver(o1);
            c.notifyObservers();
            c.registerObserver(o2);
            c.notifyObservers();
        }
        c.notifyObservers();
    }
    c.notifyObservers();
}

Boost.Signals2 is a thread-safe library. It uses mutex locking internally. There are some caveats, as explained in this article:

  Almost all classes provided by Boost.Signals2 are thread safe and can
  be used in multithreaded applications. For example, objects of type
  boost::signals2::signal and boost::signals2::connection can be
  accessed from different threads.

  On the other hand, boost::signals2::shared_connection_block is not
  thread safe. This limitation is not important because multiple objects
  of type boost::signals2::shared_connection_block can be created in
  different threads and can use the same connection object.

but in its simplest and default forms, Boost.Signals2 is multi-threading safe.

Your given example is, indeed, thread-safe.

  What happens if an Observer is destructed during notifyObservers?

The slot is disconnected preemptively.


Project Euler problem 50 I was just trying Project Euler problem 50.

  The prime 41, can be written as the sum of six consecutive primes: 41
  = 2 + 3 + 5 + 7 + 11 + 13

  This is the longest sum of consecutive primes that adds to a prime
  below one-hundred.

  The longest sum of consecutive primes below one-thousand that adds to
  a prime, contains 21 terms, and is equal to 953.

  Which prime, below one-million, can be written as the sum of the most
  consecutive primes?

Here's my code for the same in Python:

LIMIT = 1000000

x = [1] * (LIMIT + 1)
x[0] = x[1] = 0

primes = []
length = 0

for i in range(2, LIMIT):
    if x[i]:
        primes.append(i)
        length += 1

        for j in range(i * i, LIMIT + 1, i):
            x[j] = 0

s = 0
prev = -1
cnt = -1

for i in range(length):
    s = 0

    for j in range(i, length):
        s += primes[j]

        if s > LIMIT:
            break

        if x[s] and cnt < j - i + 1:
            cnt = j - i + 1
            prev = s

print(prev)

I just create a list of primes using Sieve of Eratosthenes. For each prime, I'm just finding all the consecutive primes and their sums to get the answer.

This currently takes about one second to run.

Is there a faster, better, and neater way to solve this?

Thank you for your help!

EDIT:

I see there are 2 votes to close my program as it Lacks concrete context. Can you please explain what I should do to add concrete context?

for i in range(2, LIMIT):
    if x[i]:
        primes.append(i)
        length += 1

        for j in range(i * i, LIMIT + 1, i):
            x[j] = 0

This is inconsistent: either i should range up to LIMIT inclusive, or there's no need for j to range up to LIMIT inclusive.

Also, updating length in the loop is overkill. len(primes) outside the loop works just as well and doesn't distract.

There are more advanced ways of doing the sieve with range updates, but that's already covered in dozens if not thousands of answers on this site, so I'll leave it as an exercise to search for one of them.

s = 0
prev = -1
cnt = -1

It's not immediately clear what any of those variable names mean.

        if x[s] and cnt < j - i + 1:
            cnt = j - i + 1
            prev = s

This could be done more elegantly by folding cnt and prev into a tuple:

width_sum = (-1, -1)

...
    if x[s]:
        width_sum = max(width_sum, (j - i + 1, s))

You want the longest, so the fastest approach will usually be to search in decreasing order of length. To keep the bookkeeping simple it may be worth aggregating partial sums:

primes = []
accum = [0]

for i in range(2, LIMIT):
    if x[i]:
        primes.append(i)
        accum.append(accum[-1] + i)

        for j in range(i * i, LIMIT + 1, i):
            x[j] = 0

primes = set(primes)
for width in range(len(primes), 0, -1):
    for off in range(width, len(accum)):
        partial_sum = accum[off] - accum[off - width]
        if partial_sum > LIMIT:
            break
        if partial_sum in primes:
            print(partial_sum)
            exit(0)