Python combine two integers to a third We have three integers:

A, B, C where the first (i.e. the most significant) digit of C is the first digit of A, the second digit of C is the first digit of B, the third digit of C is the second digit of A, the fourth digit of C is the second digit of B etc.

If one of the integers A and B runs out of digits, the remaining digits of the other integer are appended to the result.

Examples:

A = 1 5 4 8
B =  3 6 9    =>
C = 1356498

A = 1 0
B =  6 58    =>
C = 16058.

Here is my function which has two arguments, the integers A and B and returns the third integer C:

def myfunction(numberA, numberB):
    numberAstr = str(numberA)
    numberBstr = str(numberB)
    lenght1 = len(numberAstr)
    lenght2 = len(numberBstr)
    lenght3 = lenght1 + lenght2

    cl = []
    c = 0
    al = list(map(int, str(numberA)))
    bl = list(map(int, str(numberB)))

    if lenght1 >= lenght2:
        for i in range(lenght1):
            cl.append(al[i])
            if i <= (lenght2 - 1):
                cl.append(bl[i])
            print("Loop No:", i)
            print(cl)
    elif lenght2 > lenght1:
            for i in range(lenght2):
                if i <= (lenght1 - 1):
                    cl.append(al[i])
                cl.append(bl[i])
            print("Loop No:", i)
            print(cl)
    for i in range(lenght3):
        c += cl[i] * (10 ** (lenght3 - i))
    c //= 10
    return c

numberA = int(input("Enter the first number: "))
numberB = int(input("Enter the second number: "))
print('Integer C:', myfunction(numberA, numberB))

This function works just fine, but I'm sure that there is a pythonic way to do this! So I'm asking for any ideas to improve code efficiency.

You can use more built-in characteristics of the strings.  This code grabs each pair of digits and builds a list, which it then joins with no separator.  Then it adds the remainder from each string.  The shorter string's remainder is the empty string.

def int_merge(a, b):
    str_a = str(a)
    str_b = str(b)
    min_len = min(len(str_a), len(str_b))

    # Grab pairs of numbers while the lengths of both strings allow.
    # After that, add the remainder -- the shorter string will have none.
    result = ''.join([str_a[i]+str_b[i] for i in range(min_len)]) + \
             str_a[min_len:] + str_b[min_len:]
    return result

test = [
    (1548, 369),
    (1356, 24),
    (13, 2456)
]
for case in test:
    print int_merge(case[0], case[1])


Deleting empty files and folders Tell me how to speed up the removal of empty folders / files ?

string[] dirs = Directory.EnumerateDirectories(str1, "*", SearchOption.AllDirectories).ToArray();
DirectoryInfo dirInfo = new DirectoryInfo(str1);
for (int i = dirs.Length - 1; i >= 0; i--)
{
   if (Directory.EnumerateFileSystemEntries(dirs[i]).Count() == 0)
       Directory.Delete(dirs[i], true);
}
foreach(string pathToFile in Directory.GetFiles(str1))
{
     if (new FileInfo(pathToFile).Length == 0)
     {
          try
          {
              File.Delete(pathToFile);
          }
          catch(Exception ex)
          {
             // error
          }
     }
}

Deletes files not from all folders.

Directory.EnumerateDirectories(str1, "*", SearchOption.AllDirectories).ToArray();

Calling ToArray on this is counterproductive because this method returns directory names one by one (in a deferred fasion) as you go and request them. By using ToArray you go over directory names twice. First creating the array and then in your for loop. The EnumerateDirectories is a perfect candidate to be used with Parallel.ForEach or with AsParallel.

For example this is on my machine with 20k empty directories faster by approx 3 sec then the normal loop:

var emptyDirectories = Directory
    .EnumerateDirectories(str1, "*", SearchOption.AllDirectories)
    .AsParallel()
    .Where(d => !Directory.EnumerateFileSystemEntries(d).Any())
    .ToList();

Here you not only take the advantage of the AsParallel but also of the Any that does not have to enumerate all entries but stops as soon as at least one is found.

To delete the empty directories you can use the ForAll extension o a parallel enumeration:

var emptyDirectories =
    from d in Directory.EnumerateDirectories(str1, "*", SearchOption.AllDirectories).AsParallel()
    where !Directory.EnumerateFileSystemEntries(d).Any()
    select d;

emptyDirectories.ForAll(d => { /* delete directory */ });

The above method will of course delete only the last directory. If you want to delete directories that are empty after deleting the last empty directory you need to repeat the process:

var deleted = false;
do
{
    deleted = false;
    emptyDirectories.ForAll(d => { Directory.Delete(d); deleted = true; });
}
while(deleted);

The counterpart of the EnumerateDirectories is the EnumerateFiles method that you can use same way and you can figure out this part yourself ;-)


Cut specific rows and paste to new workbook faster I'm quite new to trying to write my own macros and I've been able to piece this one together, but it takes quite some time to run. Here is the macro for one value (I have to create workbooks for ~20 different values). Are there any ways I can improve its speed?

Also, I am assuming I can just replicate my For/Next loop with new values and workbooks and not have to run this macro every time with a new value. So if not, please tell me I'm being naive.

Sub MakeRecruitCommLog()

    Application.ScreenUpdating = False

    old_workbook = ActiveWorkbook.Name
    old_sheet = ActiveSheet.Name
    Workbooks.Add
    new_workbook1 = ActiveWorkbook.Name

    Workbooks(old_workbook).Activate
    Rows("1:1").Select

    Selection.Copy

    Workbooks(new_workbook1).Activate
    Range("A1").Select
    ActiveSheet.Paste

    Dim transfer_row As Long
    new_transfer = 2

    Workbooks(old_workbook).Activate

    For transfer_row = 2 To 514000
        Do While Range("L" & transfer_row) = "value1"

            Workbooks(old_workbook).Worksheets(old_sheet).Range(transfer_row & ":" & transfer_row).Cut _
                Workbooks(new_workbook1).Worksheets("Sheet1").Range("A" & new_transfer)

            new_transfer = new_transfer + 1

            Workbooks(old_workbook).Worksheets(old_sheet).Activate
            Rows(transfer_row & ":" & transfer_row).Delete Shift:=x1Up

        Loop
        Next transfer_row

    Workbooks(new_workbook1).Activate

End Sub

For one thing, I think you should do all 20 values all at once, in a single loop. First, create the workbooks so you can access them:

Workbooks.Add
ActiveWorkbook.Name = "value1"
Workbooks.Add
ActiveWorkbook.Name = "value2"

Then you can just check the value against one of the workbook names instead:

transfer_row = 2
Dim Transfer_Value as String
Do Until Range("L" & transfer_row) = ""
    Transfer_Value = Range("L" & transfer_row)
    Select Case Transfer_Value
        Case "value1", "value2"
            Workbooks(old_workbook).Worksheets(old_sheet).Range(transfer_row & ":" & transfer_row).Cut _
                Workbooks(Transfer_Value).Worksheets("Sheet1").Range("A" & new_transfer)
            Workbooks(old_workbook).Worksheets(old_sheet).Rows(transfer_row).Delete Shift:=xlUp
        Case Else
            transfer_row = transfer_row + 1
    End Select
Loop

If you have an array or something with the different values in it, you could use that instead of a massive Case string.


Commute cost calculator I wrote a simple javascript program that takes a user's input and calculates the cost of their commute. I feel like I'm repeating a lot of stuff though.

How could I refactor this to make it cleaner and more concise?

function calcCost(costOfGas, vehicleMPG, numMiles) {
  var dailyCost = (costOfGas / vehicleMPG) * (numMiles * 2);
  var weeklyCost = dailyCost * 5;
  var monthlyCost = weeklyCost * 4;

  return {
    dailyCost: dailyCost,
    weeklyCost: weeklyCost,
    monthlyCost: monthlyCost
  };
}

var form = document.forms[0];

form.onsubmit = function(e) {
  e.preventDefault();

  if (form.costOfGas.value == '' ||
    form.vehicleMPG.value == '' ||
    form.numMiles.value == '')
  {
    return;
  }
  else
  {
    var userCostOfGas = +form.costOfGas.value;
    var userMPG = +form.vehicleMPG.value;
    var userNumMiles = +form.numMiles.value;

    form.costOfGas.value = '';
    form.vehicleMPG.value = '';
    form.numMiles.value = '';

    var costs = calcCost(userCostOfGas, userMPG, userNumMiles);

    var inputReturned = document.getElementById("inputReturned");
    inputReturned.innerHTML = "For a car that gets " + userMPG +
    " MPG, driving " + userNumMiles + " miles to work each day at $" +
    userCostOfGas.toFixed(2) + "/gal:";

    calculatedDailyCost.innerHTML = "You're spending $" + costs.dailyCost.toFixed(2) + " on gas every day.";
    calculatedWeeklyCost.innerHTML = "You're spending $" + costs.weeklyCost.toFixed(2) + " on gas every week.";
    calculatedMonthlyCost.innerHTML = "You're spending $" + costs.monthlyCost.toFixed(2) + " on gas each month.";
  }
};

You have inconsistent bracing style. For example, in your onsubmit function, you start the brace on the same line as the function signature:

form.onsubmit = function(e) { // <=======

But, in this if/else conditional, you are starting the brace on the next line:

else
{ // <========

Choose one and stick with it: it makes your code a lot more clean. Personally, I like to use the first version.

Here, you are checking to make sure that the form is not blank:

if (form.costOfGas.value == '' ||
  form.vehicleMPG.value == '' ||
  form.numMiles.value == '')
{

However, there is a much, much easier way to do this: using the required HTML attribute (scroll down for the "required" section)

By adding a blank required attribute to each of the input elements of your form, you can safely remove this chunk of code from your JavaScript; the user will no longer be able to submit the form unless they have entered data in each field.

Here, you are using the + operator to convert a string to a number:

var userCostOfGas = +form.costOfGas.value;

While this is a neat little JavaScript trick, it looks like it's more for if you were creating this code for a code golf: it is very unclear as to what this is doing.

To make this more clear, use the parseInt function:

var userCostOfGas = parseInt(form.costOfGas.value, 10);

It looks to me that, since you are attempting to turn the form input fields from a string into a number, that you are using input fields of the type text.

By doing it this way, you are forcing yourself to take that extra step of converting the input to a number type. It would a lot easier if you set the type attribute of your input fields to "number".

That way, when you go to get the value of the input fields, they will already be of the correct type.

Good job using toFixed on the output: it makes the formatting of numbers very clean.

You have a few magic numbers in your code, especially in the calcCost function:

var dailyCost = (costOfGas / vehicleMPG) * (numMiles * 2);
var weeklyCost = dailyCost * 5;
var monthlyCost = weeklyCost * 4;

Where did the 2 come from? What about the 5? And the 4?

To make your code more readable and understandable, you should declare constants at the top of your code, and then use the constants in place of these mysterious numbers.

Here, I've created a few for you:

var DAYS_IN_WEEK = 5;
var WEEKS_IN_MONTH = 4;

I wasn't able to figure out where the 2 came from.

Then, going back to the code snippet, you would use these constant variables like this:

var weeklyCost = dailyCost * DAYS_IN_WEEK;
var monthlyCost = weeklyCost * WEEKS_IN_MONTH;


Implementing Haskell#break Learn You a Haskell demonstrates the break function:

  breaks it when the predicate is first true.

Example:

-- ghci> break (==4) [1,2,3,4,5,6,7]
-- ([1,2,3],[4,5,6,7])

Here's my code:

break' :: (a -> Bool) -> [a] -> ([a], [a])
break' _ [] = ([], [])
break' f ys = break'' f ys []
               where break'' _ [] acc = (reverse acc, [])
                     break'' g xxs@(x:xs) acc
                        | g x       = (reverse acc, xxs)
                        | otherwise = break'' g xs (x:acc)

I used the reverse rather than use the ++ function due to @Anonymous's helpful advice on my implementation of lines.

Please review it.

The first [] case is unnecessary, since break'' already handles empty lists.

g is unnecessary, since f is in scope.

break'' has two nearly identical base cases, which could be combined into one (you may need to use head and tail instead of pattern-matching). That's a line shorter but IMO no clearer.

My previous advice to reverse the accumulator contained a subtle flaw: it needs to find the boundary before it returns anything, so it's not lazy enough. (This is a subtlety of lazy data structures; if you don't understand it yet, don't worry about it.) This occasionally matters in cases like this:

let (a, b) = break (==' ') $ "abc" ++ undefined in head a

The actual implementation avoids this by simply adding x to the result of the recursive call, without using an accumulator:

break _ xs@[]           =  (xs, xs)
break p xs@(x:xs')
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)


Combining two sorted lists I'm just hoping if there's a way to simplify this recursive code that takes 2 sorted lists and combines the two together in a sorted manner (without actually having to re-sort them).

def merge (l1,l2):
    if len(l1) == 0 and len(l2) == 0:
        return []
    if len(l1) == 0:
        return l2
    if len(l2) == 0:
        return l1
    if l1[0] <= l2[0]:
        return [l1[0]] + merge(l1[1:], l2)
    if l2[0] <= l1[0]:
        return [l2[0]] + merge(l1, l2[1:])

Use the built-in heapq.merge:

heapq.merge(*iterables)
Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.


Simple timed event template class It's a simple timed event template class. It's used in a 3D multiplayer game!
template <class T>
class CTimeEventDecorator : public CBaseDecorator, public CPooledObject<CTimeEventDecorator<T>>
{
public:
    typedef CTimeEvent<T> TTimeEventType;
    typedef std::vector<TTimeEventType> TTimeEventContainerType;

    CTimeEventDecorator(const TTimeEventContainerType& TimeEventContainer, T* pValue = 0)
        : it_start(TimeEventContainer.begin())
        , it_cur(TimeEventContainer.begin())
        , it_next(TimeEventContainer.begin())
        , it_end(TimeEventContainer.end())
        , pData(pValue)
    {
        if (it_start == it_end)
            *pValue = T();
        else
            ++it_next;
    }

    void SetData(T* pValue)
    {
        pData = pValue;
    }

protected:
    CTimeEventDecorator(CTimeEventDecorator<T>& ted, CParticleInstance* pFirstInstance, CParticleInstance* pInstance)
        : it_start(ted.it_start)
        , it_end(ted.it_end)
        , it_cur(ted.it_cur)
        , it_next(ted.it_next)
        , pData((T*)((unsigned char*)ted.pData - (DWORD)pFirstInstance + (DWORD)pInstance))
    {
        if (it_start == it_end)
            *pData = T();
    }

    virtual CBaseDecorator* __Clone(CParticleInstance* pFirstInstance, CParticleInstance* pInstance)
    {
        return new CTimeEventDecorator(*this, pFirstInstance, pInstance);
    }

    virtual void __Execute(const CDecoratorData& d)
    {
        if (it_start == it_end)
            Remove();
        else if (it_cur->m_fTime > d.fTime)
            *pData = it_cur->m_Value;
        else
        {
            while (it_next != it_end && it_next->m_fTime <= d.fTime)
                ++it_cur, ++it_next;

            if (it_next == it_end)
            {
                *pData = it_cur->m_Value;
                Remove();
            }
            else
            {
                float length = it_next->m_fTime - it_cur->m_fTime;

                *pData = it_cur->m_Value * (1 - (d.fTime - it_cur->m_fTime) / length) ;
                *pData += it_next->m_Value * ((d.fTime - it_cur->m_fTime) / length);
            }
        }
    }

    typename TTimeEventContainerType::const_iterator it_start;
    typename TTimeEventContainerType::const_iterator it_end;
    typename TTimeEventContainerType::const_iterator it_cur;
    typename TTimeEventContainerType::const_iterator it_next;

    T* pData;
};

What optimizations, refactor I can do?

This answer may come across as harsh, but it is not supposed to be.
Your code looks good, BUT it lacks any comments so it’s quite difficult for other people to understand what it’s purpose is.  I have no doubt that today you know what your code does, but if you are working in a professional capacity in three months time when you have written another several thousand lines you won’t remember.
You have used base classes, but we can’t see them, this means we have even less understanding of the code.
Your coding styles are nice and clean, but you need to decide which one to use for instance you’ve got camel case and underscores in variable names.
It’s possible that things are being done in the base classes that I can’t see, but you seem to be dereferencing pointers without verifying they are not null.  See *pData, which isn’t initialised.
And a really minor thing length could be a const variable.
You say you want to optimise the code.  What problems are there with it?  Have you benchmarked it’s current performance, where is most of the time spent?


Leap year algorithm? I wrote two functions for determining leap years.
("Kabisat" means "leap year" in Indonesia.)

def kabisat? y
  return false if y%4!=0
  return true if y%100!=0
  y%400==0
end

def kabisat_2? y
  return true if y%400==0
  return false if y%100==0
  y%4==0
end

require 'date';

(1..Date.today.year).each { |y|
  puts y if kabisat?(y)!=kabisat_2?(y)
}

Is it correct? And it is possible to write a shorter one?

Some notes:

I assume that, for some reason, you want to write your own function/method instead of the existing Date#leap? that @Flambino linked above.
kabisat? We all love our mother tongue, but in computing English is the lingua franca, specially when you share your code with people around the world. It's a nice word to learn, though :-)
This is a personal advice, not all Ruby programmers agree: don't use inline returns. Use the good old full-fledged conditionals, it's much more clear. In general, use expressions instead of statements.

Let's see the standard algorithm. Ok, I'll just translate it to Ruby (if I felt fancy I'd even add Integer#divisible_by?(n) for a fully declarative code):

def is_leap_year?(year)
  if year % 400 == 0
    true
  elsif year % 100 == 0
    false
  elsif year % 4 == 0
    true
  else
    false
  end
end

Too verbose? use boolean logic:

def is_leap_year?(year)
  (year % 400 == 0) || (year % 100 != 0 && year % 4 == 0)
end


First calculator in c++, tips for optimisation So this is my first attempt at making a calculator in c++, and i'm looking for experienced people to pinpoint what i could do better to make my calculator run better! *please note that i had to translate some parts of the code to english from my native language, and had to change bunch of names so if i forgot something somewhere my bad :P

#include <cmath>
#include <iostream>
#include <stdio.h>

using namespace std;

int prompt(const char* name)
{
printf("%s", name);
int value;
scanf("%d", &value);
return value;
}

int main()
{
    int mod;
    cout << "U kojem modu kalkulatora zelis biti? " << mod << endl;
    cout << "Mod 1 je za zbrajanje" << endl;
    cout << "Mod 2 je za oduzimanje" << endl;
    cout << "Mod 3 je za mnozenje" << endl;
    cout << "Mod 4 je za dijeljenje" << endl;
    cin >> mod;

    switch (mod)
    {
        case 1:
            cout << "Odabrali ste zbrajanje!" << endl;
            int a, b, zbroj;
            a = prompt("a: ");
            b = prompt("b: ");
            zbroj = a + b;
            printf("%d + %d = %d", a, b, zbroj);
            break;
        case 2:
            cout << "Odabrali ste oduzimanje!" << endl;
            int razlika;
            a = prompt("a: ");
            b = prompt("b: ");
            razlika = a - b;
            printf("%d - %d = %d", a, b, razlika);
            break;
        case 3:
            cout << "Odabrali ste mnozenje!" << endl;
            int umnozak;
            a = prompt("a: ");
            b = prompt("b: ");
            umnozak = a * b;
            printf("%d * %d = %d", a, b, umnozak);
            break;
        case 4:
            cout << "Odabrali ste dijeljenje!" << endl;
            int kolicnik;
            a = prompt("a: ");
            b = prompt("b: ");
            kolicnik = a / b;
            printf("%d / %d = %d", a, b, kolicnik);
            break;

        default:
            cout << "Nemamo tu opciju trenutno, prcekajte za nadogradnju programa, ili se javite developeru!" << endl;
    }
    return 0;
}

I'm a newbie :P

You should avoid using namespace std.

The code in the prompt function is not indented.

You should avoid using endl unless absolutely necessary (use a \n instead).  endl will flush the output buffer which can be a big performance hit.

You don't have a break statement for the default case of your switch statement.  While not required here, it can lead to problems in the future if additional cases are added after the default and the break is not added.

Declaring uninitialized variables within a switch statement is legal, but can lead to confusion.  Usually when variables are declared under a case, the code of the case is enclosed within { curly brackets }.  For example, the a and b variables, which are used in most of the cases, could be declared before the switch.


Generating all permutations of a sequence import itertools

def permutation_lib(iterable):
    return itertools.permutations(iterable)

def permutation(iterable):
    if len(iterable) <= 1:
        yield tuple(iterable)
    else:
        for sequence in permutation(iterable[:-1]):
            for i in range(len(sequence)+1):
                yield insert_at(sequence, i, iterable[-1])

def insert_at(iterable, idx, value):
    if idx == 0:
        return (value,) + iterable[:]
    elif idx == len(iterable):
        return iterable[:] + (value,)
    else:
        return iterable[:idx] + (value,) + iterable[idx:]

import unittest

class TestPermutation(unittest.TestCase):
    def test_permutations(self):
        self.assertEqual(list(permutation([0])), list(permutation_lib([0])))
        self.assertEqual(sorted(list(permutation([0,1]))), list(permutation_lib([0, 1])))

if __name__ == '__main__':
    unittest.main()

Imports should always be at the top of the file. I would make an exception for those that are needed only if __name__ == '__main__', but in that case they should be within that block. So your code should look like:

import itertools

def permutation_lib(iterable):
   ...

def permutation(iterable):
    ...

def insert_at(iterable, idx, value):
    ...

if __name__ == '__main__':

    import unittest

    class TestPermutation(unittest.TestCase):
        ...

    unittest.main()

which also means that when you import from this script you don't get the test class, or have import unittest at the top with import itertools.

None of your functions/classes/methods have docstrings. Including these to explain what each one does, and even document the parameters, return values, etc. (I like the Google style for this) makes your code easier to follow.

You have one test method with two assertions covering three functions. Does this not seem odd to you? If that method fails, where do you look for the problem? I would suggest factoring out permutation_lib entirely (which also means you can move import itertools to the testing block) and testing insert_at on its own in a separate method.


Simple Function in python I was wondering if this code can be coded better in terms of semantics or design. Should I return the LOS as numbers? should I have the constants be read from the db in case the user or I want to change them in the future?

def get_LOS(headway = None, frequency = None, veh_per_hr = None):
  if frequency != None and headway = veh_per_hr == None:
    headway = 1 / frequency

  if headway!= None or veh_per_hr != None:
    if headway 10 < or veh_per_hr > 6:
      return 'A'
    elif 10 <= headway < 15 or 5 < veh_per_hr <= 6:
      return 'B'
    elif 15 <= headway < 20 or 3 < veh_per_hr <= 5:
      return 'C'
    elif 20 <= headway < 31 or 2 < veh_per_hr <= 3:
      return 'D'
    elif 31 <= headway < 60 or 1 <= veh_per_hr < 2:
      return 'E'
    elif headway >= 60 or veh_per_hr < 1:
      return 'F'
    else:
      return 'Error'

def get_LOS(headway = None, frequency = None, veh_per_hr = None):

You have no docstring. That would helpful in explaining what the parameters are doing.

  if frequency != None and headway = veh_per_hr == None:

When checking wheter something is none it is best to use  is None or is not None

    headway = 1 / frequency

The problem is that if someone passes frequency along with one of the other parameters, this function will go merrily onwards and probably not even produce an error. I recommend having a get_LOS_from_frequency function which takes the frequency and then calls this function.

  if headway!= None or veh_per_hr != None:
    if headway 10 < or veh_per_hr > 6:

I'm pretty sure that won't compile

       return 'A'
    elif 10 <= headway < 15 or 5 < veh_per_hr <= 6:
      return 'B'
    elif 15 <= headway < 20 or 3 < veh_per_hr <= 5:
      return 'C'
    elif 20 <= headway < 31 or 2 < veh_per_hr <= 3:
      return 'D'
    elif 31 <= headway < 60 or 1 <= veh_per_hr < 2:
      return 'E'
    elif headway >= 60 or veh_per_hr < 1:
      return 'F'

I'd store these values in a list which makes it easy to pull them from configuration at a later date if neccesary.

    else:
      return 'Error'

Don't report error by returning strings. Throw an exception, or at least assert False.

How I'd do this:

import bisect
def get_los_from_frequency(frequency):
    return get_los(1 / frequency)

HEADWAY_LIMITS = [10, 15, 20, 31, 60]
VEH_PER_HR_LIMITS = [1,2,3,5,6]
GRADES = "ABCDEF"

def get_los(headway = None, veh_per_hr = None):
    if headway is None:
        headway_score = len(GRADES)
    else:
        headway_score = bisect.bisect_left(HEADWAY_LIMITS, headway)

    if veh_pr_hr is None:
        veh_pr_hr_score = len(GRADES)
    else:
        veh_pr_hr_score = len(GRADES) - bisect.bisect_left(VEH_PR_HR_LIMITS, veh_pr_hr)

    return GRADES[min(headway_score, veh_pr_hr_score)]


Buy and Sell a Stock for maximum profit (given a day and a price) If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example one:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example two:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

My solution:

walked the array grabbing the initial price and continued to swap it with the smallest value. Between the current smallest value < and only the proceeding larger peaks. With the solution being the largest chasms (difference) between the lowest peak and highest summit in value within an interval.  TimeComplexity is O(n) space complexity is O(1) only using one object.

const perfectPrice = (prices, peak = {
  buy: null,
  buy_day: null,
  sell_day: null,
  sell: null,
  profit: 0,
  profitable: {}
}) => {
  const week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
  prices.forEach((price, day, all) => {
    if (peak['buy'] === null) {
      peak['buy_day'] = day
      peak['buy'] = price

    } else if (price < peak['buy']) {
      peak['buy'] = price
      peak['buy_day'] = day
    }
    if (peak['profit'] < (price - peak['buy'])) {
      peak.profitable = {
        buy: week[peak.buy_day],
        buy_at: peak['buy'],
        sell: week[day],
        sell_at: price,
        profit: price - peak['buy']
      }
      peak['profit'] = price - peak['buy']
    }
  });
  return ((peak || {}).profitable || {}).profit ? peak.profitable : 'not profitable to sell';
}

console.log("(test 1):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 2):", perfectPrice([7, 6, 4, 3, 1]))
console.log("(test 3):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 4):", perfectPrice([1, 2]))
console.log("(test 5):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 6):", perfectPrice([2, 9, 5, 3, 1, 4]))
.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

Readability

The way you've named your variables makes the code more difficult to read for example peak just doesn't make sense to me. Another consideration would be to rename buy_day to cheapest_day
Don't overcomplicate things: I found the return statement at the end of your forEach confusing

General syntax improvement that would make the code easier to read:

Use camelCase over snake_case
Use dot notation when accessing an objects properties where possible

Remove unnecessary/unused code

You have an if/elseif that does the same thing this can be simplified using an or statement if (this || that)
peak.sell and peak.sell_day are never used, same for all in your prices.forEach

Misc

There may be some reasoning you had which I'm missing but I did't see the point in accepting the second argument peak.

Rewrite

const perfectPrice = (prices) => {
    const week = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'];

    let profit = 0;
    let profitable;

    const cheapest = {
        day: null,
        price: null,
    };

    prices.forEach((price, day) => {
        if (day === 0 || price < cheapest.price) {
            cheapest.price = price;
            cheapest.day = day;
        }

        const potential = price - cheapest.price;

        if (!(potential > profit)) {
            return;
        }

        profit = potential;

        profitable = {
            buy: week[cheapest.day],
            buyAt: cheapest.price,
            sell: week[day],
            sellAt: price,
            profit,
        };
    });

    return profitable || 'not profitable to sell';
};

console.log("(test 1):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 2):", perfectPrice([7, 6, 4, 3, 1]))
console.log("(test 3):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 4):", perfectPrice([1, 2]))
console.log("(test 5):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 6):", perfectPrice([2, 9, 5, 3, 1, 4]))


Program to display array elements in the ascending order of number of factors each element has Input:

1000 23 100 26 32

Output:

23  26  32  100 1000

Since 23 has '2' factors and 26 has '4' factors and 32 has '6' factors, and so on.

Should I use a linked list for these types of problems?
Is my code efficient? Or how can it be optimized?

Code:

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

int facts(int);

int main(void) {
    int n,a[2][25],i,j;
    printf("Enter the no. of items\n");
    scanf("%d",&n);
    printf("Enter the items\n");
    for(j=0; j<n; j++)
    {
        scanf("%d",&a[0][j]);
    }
    for(j=0; j<n; j++)
    {
        a[1][j] = facts(a[i][j]);
    }

    for(int x=0; x<n; x++)
    {
        for(int y=0; y<n-1; y++)
        {
            if(a[1][y]>a[1][y+1])
            {
                int temp = a[1][y+1];
                int temp1 = a[0][y+1];
                a[1][y+1] = a[1][y];
                a[0][y+1] = a[0][y];
                a[1][y] = temp;
                a[0][y] = temp1;
            }
        }
    }

    for(j=0; j<n; j++)
        {
            printf("%d\t", a[0][j]);
        }

    return 0;
}

int facts(int h)
{
    int factors=0;
    for(int k=1; k<=h; k++)
    {
        if((h%k)==0)
        {
            factors++;
        }
    }
    return factors;
}

int main(void) {
    int n,a[2][25],i,j;
    printf("Enter the no. of items\n");
    scanf("%d",&n);
    printf("Enter the items\n");
    for(j=0; j<n; j++)
    {
        scanf("%d",&a[0][j]);
    }
    for(j=0; j<n; j++)
    {
        a[1][j] = facts(a[i][j]);         // here i is not set yet
    }

Your compiler should've warned you about this. Please make sure all variables have a set value before checking them.

The only reasons this works is because your compiler decided to initialize i at zero here. However, it is not required to do so by the specification. This means it will break on other systems.


Pulling information from XML to insert into Word Document inside 3rd party application This is code written for use inside a 3rd party application to pull information from an XML and insert into a word document,  I don't know all the mechanics of the fun process of inserting the information into the word document (inside the 3rd party application) so some questions you might have for me are going to be answered with an "I don't know."

I haven't tested the code yet because it is pretty simple and I want to get changes into it before I have to shoot it to production.

Dim oNode
Dim oNodes

Set oNodes = XmlDoc.SelectNodes("/Record/Case/CaseFormsLoad/PartyLoad/Party/PartyPhones/Phone")
If oNodes.Length > 0 Then
    For Each oNode In oNodes
        If oNode.GetAttribute("ConfidentialFlag") = "True" Then
            ReturnData = ReturnData & oNode.Getattribute("PhoneNum") & VbCrLf
        End If
        If ReturnData Is Nothing Then
            ReturnData = ""
        End If
    Next
Else
    ReturnData = ""
End If

and the XML that it is parsing is in the format

<PartyPhones CurrHomeIndex="-1" CurrWorkIndex="-1" CurrCellIndex="0" CurrFaxIndex="-1" Count="2">
    <Phone PhoneID="111111" PartyID="1111111" PhoneNum="111-111-1111" PhoneExt="" PhoneTyKy="CELL" fPhoneNS="0" InvalidPhone="0" UserIDCr="101" TSCreate="3/12/2014 2:30:32 PM" UserIDChg="001" TSChange="05/01/2014 08:57:26" ConfidentialFlag="False"/>
    <Phone PhoneID="111112" PartyID="1111111" PhoneNum="111-111-1112" PhoneExt="" PhoneTyKy="CELL" fPhoneNS="0" InvalidPhone="0" UserIDCr="102" TSCreate="3/19/2014 11:10:55 AM" UserIDChg="001" TSChange="05/01/2014 08:57:26" ConfidentialFlag="True"/>
</PartyPhones>

A few remarks:

Variables:

I personally like declaring my Variables with a Type (the little safety needs to be used..). And while we're at it, I don't like having lists named as items

Thus I personally(more emphasis) would rather do:

Dim oNode As Variant
Dim oNodeList As Variant

Conditionals

If ReturnData Is Nothing Then
    ReturnData = ""
EndIf

This if-statement evaluates to true only once. Instead you should initialize ReturnData before your For Each and then you can completely remove it:

Set oNodeList = 'shortcutting here
Dim ReturnData = "" As Variant/String
If oNodeList.Length > 0 Then
  ' carry on


Database report in PHP Just a small PHP exercise to write some simple reports, I thought I'd do it without a framework for fun and profit. I'm particularly concerned about the potential for SQL injection, since the user could pass their own values to $_GET['status'].

I also understand that mysql_connect() et. al are deprecated in PHP since 5.5, but I assume better equivalents work the same way.

<?php

$server = "deleted";
$username = "deleted";
$password = "deleted";
$database = "deleted";

$conn = mysql_connect($server, $username, $password);

if (!$conn)
{
        die('Could not connect: ' . mysql_error());
}

mysql_select_db($database, $conn);

// Get the status from the last form submission, otherwise use default.
$choice = isset($_GET['status']) ? $_GET['status'] : '7';

// Get all the current statuses to populate the drop down list.
$options = mysql_query("SELECT name, id FROM issue_statuses", $conn);

// Get all the results for issues matching the chosen status id.
$result = mysql_query("SELECT id, subject FROM issues WHERE status_id = " . $choice, $conn);

// Get the name of the chosen status.
$chosen_status = mysql_query("SELECT name FROM issue_statuses WHERE id = " . $choice, $conn);
$status_name = mysql_fetch_array($chosen_status, MYSQL_ASSOC);

if (!$options || !$result || !$chosen_status)
{
        echo("
Error performing query: " . mysql_error() . "
");
        exit();
}

mysql_close($conn);

?>

<!DOCTYPE html>

        <title>RM Rep</title>

        <form name="status_choice" action="index.php" method="get">
                <select name="status">
                <?php
                        // Load all the statuses into a select list.
                        while ($row = mysql_fetch_array($options, MYSQL_ASSOC))
                        {
                                echo('<option value="' . $row['id'] . '">' . $row['name'] . '</option>');
                        }
                ?>
                </select>
                <input type="submit" value="Submit">
        </form>

<?php echo($status_name['name']); ?>

        <?php echo(mysql_num_rows($result) . " results"); ?>

        <?php
                // Print results.
                while ($row = mysql_fetch_array($result, MYSQL_ASSOC))
                {
                        echo("
");
                        echo("" . $row['id'] . "	");
                        echo("" . $row['subject'] . "	");
                        echo("
");
                }
        ?>

I also understand that mysql_connect() et. al are deprecated in PHP since 5.5, but I assume better equivalents work the same way.

Sort of. MySQLi can work a lot like the the mysql extension, but personally I prefer PDO. Whereas MySQLi has both an OO and a procedural API, PDO has only an OO one.  PDO can interact with more than just MySQL though.

Due to differences in SQL dialects, it's rare for it to be possible to just change out the driver and have everything work. It is a lot closer to cross compatibility than a specific RDBMS's API.  Also, you can use your knowledge of the PDO API across multiple database systems.  Whether it's MySQL, sqlite, SQL Server, etc, the general API is the same.

Anyway, whether you choose MySQLi or PDO, you should definitely stop using ext/mysql.

As for SQL injection: your code is basically a poster child for it.

$choice = isset($_GET['status']) ? $_GET['status'] : '7';
$result = mysql_query("SELECT id, subject FROM issues WHERE status_id = " . $choice, $conn);

What if I go to page.php?status=0 OR 1=1?  The query becomes:

SELECT id, subject FROM issues WHERE status_id = 0 OR 1=1

This is a fairly benevolent example since all this will do is ignore the status filter. I've seen some very clever exploits though. Given enough time and determination, this small exploit could be ripped open into horrible, horrible things.

The easiest solution to SQL injection is to always stay aware that SQL is a language like any other (well, not on a technical level, but on a superficial level).

In particular, just remember to either escape content if it's being put into the query as a string, or cast it if it's being put in as something else.

For example:

$choice = isset($_GET['status']) ? (int) $_GET['status'] : 7;

$choice is now safe to put into an SQL statement.

This StackOverflow thread gives tons of options for properly handling SQL queries.

if (!$options || !$result || !$chosen_status)
{
    echo("
Error performing query: " . mysql_error() . "
");
    exit();
}

If more than one query fails, this will only output the error for the last one. Additionally, using exit for rendering errors is bad practice. In a file this simple, there's really not much of a better option without going way out of your way. What I tend to do in larger applications though is let uncaught exceptions (in other words, either the ones that I expect to never happen or the ones that are fatal) bubble up to the top at which point the request is transparently piped to an error controller (basically, I've copied the approach of most PHP MVC frameworks). If you wanted to use a similar approach, you could basically wrap exceptions over the MySQL API. That get's ugly fast though.

Oh, also, the mysql_error should be passed through htmlspecialchars.  I'll add more to this note in a minute.

I'm not sure if it's technically valid to close a MySQL connection and then read the result sets.  I suspect that this is not valid, and that if it works, it's just by luck.

Even when not going full-blown MVC, it can be very beneficial to separate logic or manipulation from the view.  In particular, all of the mysql calls in the HTML parts, I would put in the PHP parts.  If your view is only looping over an array, the source of the array can be changed without the view having to know about it.  (Side note: depending on how strictly we're using terminology, the HTML part is probably better not called a view.)

while ($row = mysql_fetch_array($options, MYSQL_ASSOC))

You might as well us mysql_fetch_assoc.

echo('<option value="' . $row['id'] . '">' . $row['name'] . '</option>');

Anything being put into HTML needs to be run through htmlspecialchars. This comes back to being aware of context. It's just the rules of HTML.  Certain things must be escaped in the same way that things in SQL or PHP must be escaped.

(I'm also not a fan of the echo() form of echo, but that's mostly opinion.)

echo '<option value="' . htmlspecialchars($row['id']) . '">' . htmlspecialchars($row['name']) . '</option>';

A lot of people will say that the htmlspecialchars on the id is pointless since it's going to be an int.  While that's true, that's only for now.  With a primary key column it's not likely to happen (in fact it probably shouldn't happen), but I've been in situations before where an int column has been changed to a varchar and we've had problems with the HTML escaping after that. Considering the overhead of htmlspecialchars is tiny, might as well call it on everything being put into HTML.

There's a few more comments and suggestions I have. I was originally going to add them as comments to the code, but I got a bit carried away and decided to rewrite it with PDO.

<?php

$db = new PDO('mysql:host=localhost;dbname=somedatabase', 'username', 'password', array(
    PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION
));

//The error mode being exception means that exceptions will be thrown if a query fails
//(or some other kind of error happens).  This tends to be more convenient since you don't
//have to explicitly check for unexpected errors -- either everything executes fine, or the script
//crashes and burns (which might not be desired behavior in a lot of cases).
//Anyway, there is one little catch.  PDOException instances will sometimes include with them
//the DSN (the 'mysql:host=...' string), the username, and the password. This means that you must be
//very careful about never letting an end user see a PDOException.  In particular, you can either have
//a just-in-case top level try {} catch {} that can catch any unexpected errors, log them, and render
//them in a pretty page (what I like to do in any kind of sizable application), or at the very least,
//you can ensure that display_errors of Off on production servers (which it should be anyway). That way
//the exception will still be logged, but it won't be displayed.

//$options is a bad name. What kind of options?
$issueStatusesStmt = $db->query("SELECT name, id FROM issue_statuses");

//This is done in a weird way, but it has a reason.
//In particular, you can now check if a provided status id exists (isset($issueStatuses[$idToCheck])).
//And, you no longer need your name query since you can pull the name with $issueStatuses[$id]['name'].
$issueStatuses = array();
while ($is = $issueStatusesStmt->fetch(PDO::FETCH_ASSOC)) {
    $issueStatuses[$is['id']] = $is;
}

//This handles the isset check and validates that the provided value is an integer.
//If the value fails the integer check, $statusId will be false.  If no status param is
//provided in the URL, $statusId will be null. There is of course a lot more
//information about this at http://php.net/filter_input
$statusId = filter_input(INPUT_GET, 'status', FILTER_VALIDATE_INT);

 if (!isset($issueStatuses[$statusId]) {
    //This is what's called a magic constant. They tend to lead to problems.
    //In particular, what is this magical status 7? Someone not intimately familiar
    //with your DB data will have no idea.
    $statusId = 7;
}

//This prepares a statement with a placeholder for status_id.
$issuesStmt = $db->prepare("SELECT id, subject FROM issues WHERE status_id = :statusId");
$issuesStmt->execute(array('statusId' => $statusId));
/*
 * You could also do it like:
    $issuesStmt = $db->prepare("SELECT id, subject FROM issues WHERE status_id = ?");
    $issuesStmt->execute(array($statusId));
 * I prefer to stick with named fillers though.  It's significantly less confusing if you have
 * to revisit a complicated query a month later.
*/

//You could make this an associative array like earlier, but really there's no reason to at this point.
$issues = $issuesStmt->fetchAll(PDO::FETCH_ASSOC);

//Note: if $statusId default to 7 and 7 somehow doesn't exist in the database,
//this will issue a notice and $statusName will be null.
$statusName = $issueStatuses[$statusId]['name'];

//PHP will only eat one new line.  The doctype is supposed to be the very top line (unless I've imagined that requirement).
//This means it need to be on the line directly after the closing tag.
?>
<!DOCTYPE html>

        <title>RM Rep</title>

        <form name="status_choice" action="index.php" method="get">
            <select name="status">
                <?php foreach ($issueStatuses as $is) { ?>
                <option value="<?php echo htmlspecialchars($is['id']); ?>"><?php echo htmlspecialchars($is['name']); ?></option>
                <?php } ?>
            </select>
            <input type="submit" value="Submit">
        </form>

<?php echo htmlspecialchars($statusName); ?>

        <?php echo count($issues) . ' results'; ?>

        <?php
        /*
         If no entries are found, you will emit broken HTML in your current code.
         (At least I think an empty table is invalid HTML -- can't remember.)
         (Oh and also, I'm abusing PHP comments right now...)
        */
        ?>

        <?php if (!empty($issues)) { ?>

            <?php foreach ($issues as $issue) { ?>

                <?php echo htmlspecialchars($row['id']); ?>
                <?php echo htmlspecialchars($row['subject']); ?>

            <?php } ?>

        <?php } else { ?>

            No entries matched the given status.

        <?php } ?>


Monte Carlo asset price simulation I'm trying to write a simplistic Monte Carlo simulator to predict asset prices. For example, if something has an initial value of 50 and an historic daily standard deviation of 2, what are the odds it will be 40, 40-50, 50-60 or greater than 60 in 25 days?

import random

start = 50
sd = 2
days = 25
bins = [40,50,60]

iterations = 1000
results = [0] * (len(bins) + 1)

GAUSS = True # distribution can be gaussian or lognormal

for _ in range(iterations):
    mc = start
    for _ in range(days):
        if GAUSS:
            mc += random.gauss(0, sd)
        else:
            if random.randint(0,1):
                mc += random.lognormvariate(0, sd)
            else:
                mc -= random.lognormvariate(0, sd)
        if mc <= 0: # prices can't go below 0
            mc = 0

    for n, bin in enumerate(bins): # bin the iteration
        if mc < bin:
            results[n] += 1
            break
    else:
        results[-1] += 1

final = [100 * r / float(iterations) for r in results]
print(final)

The values at the top of your script are constants so, per the style guide, should be UPPERCASE_WITH_UNDERSCORES:

BINS = [40, 50, 60]
DAYS = 25
GAUSS = True  # distribution can be gaussian or lognormal
ITERATIONS = 1000
START_PRICE = 50
STD_DEV = 2

Note that I've also made some of the names a little more meaningful, and added more Pythonic whitespace to the list. I've also ordered them alphabetically, although there may be a more sensible grouping.

It would be nice to add a comment explaining BINS - the rest are fairly obvious, but it took me a few reads to figure out that they're the top of each bin, and an additional higher bin will be automatically added. Consider adding a module docstring covering this.

Currently, all of the code is just in the body of the script. Instead (as it makes it easier to import and reuse this functionality elsewhere), it is conventional to define an "entry point" function (conventionally named main) and call that when the script is invoked directly:

# imports, constants, etc.

def main():
    # do your thing

if __name__ == '__main__':
    main()

Rather than specify two distributions within the body of the code, I would extract the distribution function as a parameter to the simulation. In this case the functions would be:

def gaussian(std_dev):
    """Apply the Gaussian distribution."""
    return random.gauss(0, std_dev)

def lognormal(std_dev):
    """Apply the log-normal distribution."""
    return random.choice((1, -1)) * random.lognormvariate(0, std_dev)

Now if you wrote a function to do one iteration, it would be very simple:

def simulate(days, start_price, std_dev, distribution):
    """Simulate the asset for the specified number of days."""
    price = start_price
    for _ in range(days):
        price = max(0, price + distribution(std_dev))
    return price

You can then create more distribution functions in the future, and pass whichever you want to simulate; all it requires is a function that takes a single argument and returns a number.

Note that I have made the constants explicit parameters to these functions - this, again, makes reuse of the code easier. main would now look like:

def main():
    results = [0] * (len(BINS) + 1)
    dist = gaussian if GAUSS else lognormal
    for _ in range(ITERATIONS):
        final_price = simulate(DAYS, START_PRICE, STD_DEV, dist)
        ...
    ...
    print(final_results)  # you could return final_results instead

You could also abstract the binning of results into a function. I would avoid using the identifier bin, as this shadows a built-in function


Functional, but not recursive, tree traversal To learn tree traversal i implemented os.walk, tail-recursive and stack-based. Unfortunately Python doesn't support tail call optimization. How do i rewrite my function so that it is maximally functional paradigm compliant? I want to keep side-effects to minimum yet not dive into deep recursions.

def walk_rec(path):
    def i(result, stack):
        if not stack:
            return result
        else:
            path = stack.pop()
            with cd(path):
                ds, fs = partition(isdir, listdir(path))
            stack.extend(join(path, d) for d in ds)
            result.append((path, ds, fs))
            return i(result, stack)
    return i([], [expanduser(path)])

def walk_iter(path):
    stack = [expanduser(path)]
    result = []
    while stack:
        path = stack.pop()
        with cd(path):
            ds, fs = partition(isdir, listdir(path))
        stack.extend(join(path, d) for d in ds)
        result.append((path, ds, fs))
    return result

See: cd, partition.

I could get rid of cd, but this is not critical.

with cd(path):
    ds, fs = partition(isdir, listdir(path))
# can be replaced with
ds, fs = partition(lambda d: isdir(join(path, d)),
                   listdir(path))

Does this help?  In your walk_iter, instead of using pop, grab the first element of the stack. Then do something like this ...

if first_element_has_sub_elements:
    new_stack = stack[0][1]
    new_stack.extend(stack[1:])
    stack = new_stack[:]
else:
    stack = stack[1:]

This was my experiment, in case it's helpful ...

TREE = [
 ("L1A", [("L1A2A",),
          ("L1A2B", [("L1A2B3A", )])]),
 ("L1B", [("L1B2A", [("L1B2A3A", )])]),
 ("L1C",),
 ("L1D", [("L1D2A",),
          ("L1D2B", [("L1D2B3A", ),
                     ("L1D2B3B",)])]),
 ]

EXPECTED = ["L1A", "L1A2A", "L1A2B", "L1A2B3A",
            "L1B", "L1B2A", "L1B2A3A", "L1C",
            "L1D", "L1D2A", "L1D2B", "L1D2B3A", "L1D2B3B"]

def traverse_tree(TREE):
    chopped_tree = TREE[:]
    results = []
    while chopped_tree:
        results.append(chopped_tree[0][0])
        if len(chopped_tree[0]) > 1:
            new_tree = chopped_tree[0][1]
            new_tree.extend(chopped_tree[1:])
            chopped_tree = new_tree[:]
        else:
            chopped_tree = chopped_tree[1:]

    return results

if __name__ == "__main__":
    results = traverse_tree(TREE)
    if results == EXPECTED:
        print "OK"
    else:
        print "MISMATCH"
    print "Expected: "
    print EXPECTED
    print "Results: "
    print results


Simple multithreaded FileLogger in C++ I'm new to C++ and am following up on: A simple multithreaded FileLogger in C++
I am curious to know if I implemented his ideas correctly, if there are further improvements to the code and whether it's (still) correct.
FileLoggerThread.h
#pragma once
#include <string>
#include <fstream>
#include <mutex>
#include <deque>
#include <condition_variable>
#include <filesystem>

class FileLoggerThread
{
public:
    explicit FileLoggerThread(std::filesystem::path filePath);
    ~FileLoggerThread();                            // makes code more easily unit testable (unit tests can otherwise be in an infinite loop)

    void log(const std::string &msg);

    FileLoggerThread(const FileLoggerThread&) = delete;
    FileLoggerThread& operator=(const FileLoggerThread&) = delete;

private:
    void writeToFile();

    std::deque<std::string> mMessages;              // accessed by log (any thread) and writeToFile (the writer thread)
    std::ofstream mOutputFile;                      // only accessible by writeToFile

    // thread internal resources
    std::mutex mMessagesMutex;                      // lock/unlock this each time messages is pushed or popped
    std::condition_variable mThreadScheduler;       // log needs to wake up writeToFile
    bool mIsRunning;                                // if set to false then the writer thread stops
};

FileLoggerThread.cpp
#include "FileLoggerThread.h"
#include <thread>

FileLoggerThread::FileLoggerThread(std::filesystem::path filePath) : mOutputFile {filePath}, mIsRunning {true} {
    std::thread t(&FileLoggerThread::writeToFile, this);
    t.detach();
}

void FileLoggerThread::writeToFile() {
    while (mIsRunning) {
        std::deque<std::string> localMessages;
        std::unique_lock<std::mutex> writerLock {mMessagesMutex};
        mThreadScheduler.wait(writerLock, [&]{ return !mMessages.empty() || !mIsRunning;});
        localMessages.swap(mMessages);
        writerLock.unlock();

        for (const auto& message : localMessages) {
            mOutputFile << message << std::endl;
        }
    }
}

void FileLoggerThread::log(const std::string &msg) {
    std::unique_lock loggerLock(mMessagesMutex);
    mMessages.emplace_back(msg);
    loggerLock.unlock();
    mThreadScheduler.notify_one(); // done for performance reasons, see: https://youtu.be/F6Ipn7gCOsY?t=2205
}

FileLoggerThread::~FileLoggerThread() {
    mIsRunning = false;
    mThreadScheduler.notify_one();
}

It is not a good idea to have a completely detached thread. When one detaches thread, they usually use some sort of notification system like future/promise to ensure that the thread finished using resources. Here you file logger might have finished working and got destroyed while the detached thread still accesses this leading to UB. Instead you should keep thread as a part of the logger and trigger join in the destructor.

You shouldn't use std::endl; for every message - the flushing is a slow operation. You surely don't have a good reason to trigger it more often than more than once a second . Just make sure that you do trigger it once a second or so. std::condition_variable::wait_for/wait_until could be used to ensure that.

Another bug in destructor is that you modify mIsRunning without locking the mutex. Technically, it is a UB. In practice, this bug results in some very rare cases with the wait missing the notification and lasting eternity.

With the scheme that you are running I don't see why you use a std::deque for holding messages. Why not just std::vector? It is more efficient and also you shouldn't create new localMessages each time - just keep one constantly existing and clear it after each use. It saves some unnecessary memory allocations.

Also, once mIsRunning is false you need to ensure that all messages were written instead of quitting. Moreover, you shouldn't access mIsRunning in the while-loop condition as it should be guarded by the mutex.

The log function void log(const std::string &msg); accepts a string and copies it into the queue. It is a waste. You'd better have two other overloads: void log(std::string&& msg); and void log(std::string_view msg); with the former moving the string and it's content for printing instead of unnecessarily copying it, while latter is just a more general form of const std::string&.

In general, logger should support features like verbosity filterting and identification (e.g., info, warning, error), timestamping, and similar stuff that should be inherent part of a logger. Here you just accept arbitrary messages.


Is this a good example of the composite pattern? I am studying the composite pattern and have created a very simple project that uses composite to introduce family members. I have decided to go with the 'fully transparent' implementation by defining all of my common functions in the interface class, I feel this is the neatest implementation and am considering throwing an exception in Leaf classes if client tries to call add / remove...

Below are the sample classes I have created. I would like to get some thoughts on how I implemented.

Am I implementing composite correctly?
Is this a good piece of sample code?
Thoughts on throwing an exception in leaf class for un-needed function implementations like add / remove Person?

Client class

public class Client {

public static void main(String args[]) {

    Person gretchen = new Parent("gretchen", 101);
    Person steve = new Parent("Steve", 57);
    Person mary = new Parent("Mary", 56);
    Person timmy = new Child("Timmy", 10);
    Person molly = new Child("Molly", 5);

    gretchen.add(steve);
    gretchen.add(mary);
    steve.add(timmy);
    steve.add(molly);
    mary.add(timmy);
    mary.add(molly);

    //introduces entire family
    gretchen.introduce();

}

}

Component Class

public interface Person {

  public String getName();

  public int getAge();

  public int getNumOfChildren();

  public void add(Person person);

  public void remove(Person person);

  public void introduce();
}

Composite class

public class Parent implements Person {

private String name;
private int age;
private List<Person> children = new ArrayList<Person>();

public Parent(String name, int age) {
    this.name = name;
    this.age = age;
}

public void introduce() {

    System.out.println("Hi, I am ".concat(getName()));
    System.out.println("I am ".concat(Integer.toString(getAge()).concat(
            " years old")));
    System.out.println("I have ".concat(Integer.toString(children.size()).concat(" kids.")));
    System.out.println("Children... introduce your selves!");

    for (Person person : children) {
        person.introduce();
    }

}

@Override
public String getName() {
    return this.name;
}

@Override
public int getAge() {
    return this.age;
}

@Override
public int getNumOfChildren() {
    return this.children.size();
}

@Override
public void add(Person person) {
    children.add(person);
}

@Override
public void remove(Person person) {
    children.remove(person);
}

}

Leaf class

public class Child implements Person {

private String name;
private int age;

public Child(String name, int age) {
    this.name = name;
    this.age = age;
}

@Override
public void introduce() {

    System.out.println("Hi, I am ".concat(getName()));
    System.out.println("I am ".concat(Integer.toString(getAge()).concat(
            " years old")));

}

@Override
public String getName() {
    return this.name;
}

@Override
public int getAge() {
    return this.age;
}

@Override
public int getNumOfChildren() {
    return 0;
}

@Override
public void add(Person person) {
    // no implementation here, throw exception maybe?

}

@Override
public void remove(Person person) {
    // no implementation here, throw exception maybe?

}

}

Am I implementing composite correctly.

Although you are doing it correctly, a part of me wonders if it was the correct solution for you problem. The reason I ask is because a interface usually means that each method that you define is going to need to be implemented differently for each sub class that implements it. In your case it doesn't matter what type of person you have they will always introduce themselves the same way, and they will always say their name the same way, and they will always tell their age the same way. That being said an abstract class would have been a better choice because the basics will be the same for both parent and child (and even if you decide to add another branch of a person) for things such as their name, and age. The introduction would possibly be the only exception if you added a culture to this mixture. Since different cultures introduce themselves differently in almost all scenarios that would be a good candidate for a interface.

  Is this a good piece of sample code?

The code appears to be in good order. It is easy to read and easy to understand. My only issue (and it is debatable) is having the age part of the constructor. In this context it makes sense, but when i first introduce my self to someone I don't say, "Hi my name is Robert Snyder, I'm 30 years old". Instead I just introduce my self as "Robert" but judging by the context of your code it might be fair to have the age (such as in the case of the entrance to a liquor store, they want your id which has your name and age)

  Thoughts on throwing an exception in leaf class for un-needed function implementations like add / remove Person?

No. Never. Only in the higher levels do you want that to happen. This forces the user to use child classes. If your child classes are "dangerous" then people will either make their own, or not use yours.


Evaluating a math expression given in string format I am currently working on building a calculator using Java and JavaFX to practice my coding skills. I wrote the following methods to evaluate a given expression.

What can I improve? Is there anything you would recommend me to change to optimize my program?

public static String evaluate(String expression) {
    char[] tokens = expression.toCharArray();
    List<String> list = new ArrayList<>();

    String s = "";

    String operator = "";
    String firstNum = "";
    String secondNum = "";

    boolean operationOnQueue = false;

    for (int i = 0; i < tokens.length; i++) {
        if (Character.isDigit(tokens[i])) {
            s += Character.toString(tokens[i]);
        } else {
            list.add(s);
            list.add(Character.toString(tokens[i]));

            if (operationOnQueue) {
                operationOnQueue = false;
                secondNum = s;

                list.set(list.lastIndexOf(firstNum), eval(firstNum, operator, secondNum));
                list.remove(list.lastIndexOf(operator));
                list.remove(list.lastIndexOf(secondNum));
            }

            if (tokens[i] == '*' || tokens[i] == '/') {
                operationOnQueue = true;

                operator = Character.toString(tokens[i]);
                firstNum = list.get(list.lastIndexOf(operator) - 1);
            }

            s = "";
        }

        if (i == tokens.length - 1 && s.length() > 0) {
            list.add(s);

            if (list.get(list.size() - 2).equals("*") || list.get(list.size() - 2).equals("/")) {
                firstNum = list.get(list.size() - 3);
                operator = list.get(list.size() - 2);
                secondNum = list.get(list.size() - 1);

                list.set(list.size() - 3, eval(firstNum, operator, secondNum));
                list.remove(list.size() - 2);
                list.remove(list.size() - 1);
            }
        }
    }

    while (list.size() > 1) {
        firstNum = list.get(0);
        operator = list.get(1);
        secondNum = list.get(2);

        list.set(0, eval(firstNum, operator, secondNum));
        list.remove(2);
        list.remove(1);
    }

    return list.get(0);
}

public static String eval(String a, String operator, String b) {
    double r = 0;

    switch (operator) {
        case "/":
            r += Double.parseDouble(a) / Double.parseDouble(b);
            break;
        case "*":
            r += Double.parseDouble(a) * Double.parseDouble(b);
            break;
        case "-":
            r += Double.parseDouble(a) - Double.parseDouble(b);
            break;
        case "+":
            r += Double.parseDouble(a) + Double.parseDouble(b);
            break;
    }

    return Double.toString(r);
}

These are the results of my tests. The first line is the string inputted, along with the answer to the expression. The second line is the output of the program.

8+4/2+10*3+5*10 = 90
90.0

60*60+8+384/7/4-44*26 = 2477.71
2477.714285714286

64/16*18-51*7+5 = -280
-280.0

64/16*18-5100*7+5 = -35623
-35623.0

7325+92+44/4+57-84 = 7401
7401.0

14+54/9+1 = 21
21.0

7*4/7+9+12*3 = 49
49.0

How does it work?

Seems to be working now. What I can't understand is how :)

Code should be readable and easily understandable by humans as well. You might even be one of the humans that have to work with code that you wrote a year or more ago..

There is a lot going on in the code that I cannot tell why it's there and what its use is.

For example:

 if (operationOnQueue) {
                    operationOnQueue = false;
                    secondNum = s;

                    list.set(list.lastIndexOf(firstNum), eval(firstNum, operator, secondNum));
                    list.remove(list.lastIndexOf(operator));
                    list.remove(list.lastIndexOf(secondNum));
                }

I can read the code and see what it will do, but why? I have no clue.

So either try to explain the why in comments, or re-write the code to be more self-explanatory.

(Btw your code looks a bit like https://en.wikipedia.org/wiki/Shunting-yard_algorithm.)

Try to break big methods into smaller ones

You evaluate does a few things. The while loop in the end seems like a good candidate for a separate method. The second if in the for loop as well.

Don't repeat yourself

There are a few Character.toString(tokens[i]) in the code. It's easier to read if you extract that to a variable, for example String currentToken = Character.toString(tokens[i])

Handling error cases

What if the input is not a correct expression?

For example: 14+54/9+

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 2
    at java.util.ArrayList.rangeCheck(ArrayList.java:657)
    at java.util.ArrayList.get(ArrayList.java:433)
    at Math.evaluate(Math.java:64)
    at Math.main(Math.java:96)

BTW: for more interesting links / implementations see here:
https://stackoverflow.com/a/114601/461499


Content management system for media I have a content management system for an iOS app built with Rails. Right now there are three different types of content. The first two are just strings uploaded into a textfield by the user. One is Twitter handles and hashtags, the other is URLs. The second type is photos.

The user can upload as many individual instances of these types content as he/she wants to given a feed which will is the then passed to the iOS app via an API call to display.

The current approach I am using is to have Feed, Picture, Twitter, and Webpage models. When the user creates a new Feed, they then associate the appropriate content with that feed via a one to many relationship between each Feed instance it's content instances.

When it comes time to display to content the user has uploaded, a GET request for a given stream is generated and the Feed model then does the following awful thing determine what type of content should be shown:

 def Feed.get_content_for_feed(feed_id)
    return self.map_type_to_class(feed_id).get_content_for_feed(feed_id)
  end

  private

  def Feed.map_type_to_class(feed_id)
    feed_type_id = Feed.find(feed_id).feed_type_id
    not_yet_implemented = nil
    case stream_type_id
      when 1
        return Webpages
      when 2
        return Pictures
      when 3
        return not_yet_implemented
      when 4
        return Twitter
      when 5
        return not_yet_implemented
      when 6
        return not_yet_implemented
      when 7
        return not_yet_implemented
      when 8
        return not_yet_implemented
      else
        return nil

    end
  end

Then each content class implements a get_content_for_feed method to return the content:

def Twitter.get_content_for_feed(feed_id)
    tweet_urls = self.where(:feed_id => feed_id.to_i)
    if tweet_urls.empty?
      return []
    else
      return tweet_urls
    end
  end

It just returns the appropriate class. This works, but I know that it is wrong, but I am not sure what I would be doing.

First a light review:

You've got a bug, I think. Your map_type_to_class sets a feed_type_id variable, but your case statement is looking at a stream_type_id variable that I don't see anywhere.

Second, don't use so many return statements. It's Ruby; returns are implicit. So this you don't need returns in if...else or case branches you have in your question. In idomatic Ruby, you only see return if someone specifically wants to exit a method early (and even that's rare with well-factored code).

Lastly, this bit is redundant

tweet_urls = self.where(:feed_id => feed_id.to_i)
if tweet_urls.empty?
  return []
else
  return tweet_urls
end

Which, to all intents and purposes is the same as simply:

self.where(:feed_id => feed_id.to_i)

It's implicitly returned, and it's array-like, so there's no need to do anything special. It's either empty or it's not. If you want something that's truly an Array instance (and not just duck-typed), you can append a .to_a.

Anyway, what you're looking for is the constantize method for strings. What you've got is a fairly simple has_many relationship, you just want something like a string item_type column on your Feed model that contains the class name (as a string) instead of your current numeric ID.

From there it's a matter of implementing a polymorphic has_many (Rails already has a polymorphic option for belongs_to but that's a to-one association).

You could simply do

def Feed
  def items
    klass = item_type.constantize
    klass.where(feed_id: id)
  end
end

(yes that could just be one line).

You won't have all the fancy collection methods, caching, and other nice stuff Rails provides for regular associations, but you can add that if you want or simply make do without it (I recommend the latter unless you find it to be bigger hassle).

So in your FeedsController (or wherever), you're looking at something like

def show
  feed = Feed.find(params[:id])
  render json: feed.items
end

That should work as a super-minimal implementation. The point is really just that you store the class name, which you can then turn from a string into a class name constant with constantize.

Alternatively, you could use Rails' built-in associations, but there's more setup involved and it's not as clean to look at. Again, you'll want an item_type string column.

def Feed
  has_many :webpages # the class name Webpage is implicit
  has_many :pictures
  has_many :twitters # yuck, not a good name, but it'll imply the Twitter class

  def items
    association = item_type.underscore.pluralize # convert a class name to an association name
    send(associtation) # call the association method (e.g. `webpages`)
  end
end

The main advantage is that the items method is just a shortcut that provides the correct association object, so you have all the usual convenience methods. So you can do something like this for a webpage-type feed

Feed.find(some_id).items.create(params[:url])

Of course, the major issue is that it's not clear what's going on. Is items a collection of Picture? Of Webpage? If you just blindly try to create a Picture record from params meant for a webpage, things get messy.

So I'd stick to the first version, where items isn't an opaque alias for an association, and instead work a bit harder when adding new records and such.


Stack Overflow Tag Usage I am trying to efficiently use the SEDE tool to get a list of tags a user has answered questions on, and their stats on each Tag.

My code works for my account in 3185 ms, but if I try to run it on @jon-skeet's, user ID (22656) then it times out.

Are there ways to make this more efficient / better code, and allow it to be used for any user ID?

Stack Explorer Link

-- The tags and scores of my posts
CREATE TABLE #MyPosts (
  _tags nvarchar(250) COLLATE SQL_Latin1_General_CP1_CS_AS,
  _score int
);

INSERT INTO #MyPosts
SELECT
  Question.Tags,
  Answers.Score
FROM
  Posts as Answers
INNER JOIN
  Posts AS Question
ON
  Question.Id = Answers.ParentId
WHERE
  Answers.PostTypeId = 2 AND
  Answers.OwnerUserId = ##UserId:int?8041461##;
--------------------------------------------------------------------------
-- All of the tags with the total score and the amount of times used
CREATE TABLE #TagCounts (
  _tagName nvarchar(35) COLLATE SQL_Latin1_General_CP1_CS_AS,
  _score int,
  _count int
);

INSERT INTO #TagCounts
SELECT
  Tags.TagName,
  sum(_score),
  count(*)
FROM
  #MyPosts
INNER JOIN Tags ON #MyPosts._tags LIKE '%<'+Tags.TagName +'>%'
GROUP BY Tags.Id,Tags.TagName;
--------------------------------------------------------------------------
-- Outputs the tags with links, total score, count and average score
SELECT
  _tagName as [TagName],
  _score as 'Total Score',
  _count as 'Answer Count',
  cast(_score as FLOAT) / _count as 'Average Score'
FROM
  #TagCounts
WHERE
  _score IS NOT NULL
ORDER BY
  _score DESC

This TagName column holding all the tags is denormalized and the non-equi-join ON #MyPosts._tags LIKE '%<'+Tags.TagName +'>%' kills performance. There's no efficient way for the optimizer to do this join, thus it's like a Cross-Join to the 50000+ rows in Tags.

But the base data model is normalized, there's an associative table PostTags between Posts and Tags and then it's simple equi-joins:

with MyPosts as
 (
-- The tags and scores of my posts
   SELECT
     Question.Id AS PostId,
     Answers.Score
   FROM
     Posts as Answers
   INNER JOIN
     Posts AS Question
   ON
     Question.Id = Answers.ParentId
   WHERE
     Answers.PostTypeId = 2 AND
     Answers.OwnerUserId = ##UserId:int?8041461##
 )
-- All of the tags with the total score and the amount of times used
SELECT
  t.TagName,
  sum(score) as "Total Score",
  count(*) as "Answer Count",
  cast(sum(score) as FLOAT) / count(*) as 'Average Score'
FROM
  MyPosts AS p
JOIN PostTags AS pt
  ON p.PostId = pt.PostId
JOIN Tags AS t
 ON pt.TagId = t.Id
GROUP BY t.Id,t.TagName
ORDER BY "Total Score" DESC;

Your HAVING sum(score) IS NULL is not needed, there's no NULL score.

See SEDE query which runs fine with John Skeet, too :-)


Solving Sudoku using backtracking This is a solver for Sudoku using backtracking.  How can I make it more optimized and clean?

#include <stdio.h>

int isAvailable(int sudoku[][9], int row, int col, int num)
{
    int i, j;
    for(i=0; i<9; ++i)
        if( (sudoku[row][i] == num) || ( sudoku[i][col] == num )  )//checking in row and col
            return 0;

     //checking in the grid
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;

    for(i=rowStart; i<(rowStart+3); ++i)
    {
        for(j=colStart; j<(colStart+3); ++j)
        {
            if( sudoku[i][j] == num )
                return 0;
        }
    }

    return 1;
}

int fillsudoku(int sudoku[][9], int row, int col)
{
    int i;
    if( row<9 && col<9 )
    {
        if( sudoku[row][col] != 0 )//pre filled
        {
            if( (col+1)<9 )
                return fillsudoku(sudoku, row, col+1);
            else if( (row+1)<9 )
                return fillsudoku(sudoku, row+1, 0);
            else
                return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if( isAvailable(sudoku, row, col, i+1) )
                {
                    sudoku[row][col] = i+1;

                    if( (col+1)<9 )
                    {
                       if( fillsudoku(sudoku, row, col +1) )
                           return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else if( (row+1)<9 )
                    {
                        if( fillsudoku(sudoku, row+1, 0) )
                            return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else
                        return 1;
                }
            }
        }
        return 0;
    }
    else
    {
        return 1;
    }
}

int main()
{
   int i, j;
    int sudoku[9][9]={{3, 0, 6, 5, 0, 8, 4, 0, 0},
                      {5, 2, 0, 0, 0, 0, 0, 0, 0},
                      {0, 8, 7, 0, 0, 0, 0, 3, 1},
                      {0, 0, 3, 0, 1, 0, 0, 8, 0},
                      {9, 0, 0, 8, 6, 3, 0, 0, 5},
                      {0, 5, 0, 0, 9, 0, 6, 0, 0},
                      {1, 3, 0, 0, 0, 0, 2, 5, 0},
                      {0, 0, 0, 0, 0, 0, 0, 7, 4},
                      {0, 0, 5, 2, 0, 6, 3, 0, 0}};

    if( fillsudoku(sudoku, 0, 0) )
    {

        for(i=0; i<9; ++i)
        {
            for(j=0; j<9; ++j)
                printf("%d ", sudoku[i][j]);
            printf("\n");
        }
    }
    else
    {
        printf("\n\nNO SOLUTION\n\n");
    }

    return 0;
}

Very nice:

Few minor changes I would make.

In isAvailable() I would check row/col/box all at the same time.

int isAvailable(int sudoku[][9], int row, int col, int num)
{
    //checking in the grid
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;

    int i, j;
    for(i=0; i<9; ++i)
    {
        if (sudoku[row][i] == num)                             return 0;
        if (sudoku[i][col] == num)                             return 0;
        if (sudoku[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
    }

    return 1;
}

Which brings my to my first comment:
I prefer to have sub statments of while/for/if inside block quotes.

if( sudoku[i][j] == num )
            return 0;

// I prefer this:
if( sudoku[i][j] == num )
{   return 0;
}

This way there is not chance of accidentally putting a macro that expands and is not all executed.

Your code for moving to the next square is in multiple places in the code:

        if( (col+1)<9 )
           STUFF(row, col+1);
        else if( (row+1)<9 )
            STUFF(row+1, 0);
        else
            WIN

Because it is multiple places you have redundancy. I would move this check to one location. The easiest way to do that is move it to the first few lines of code in the function. Then you always make a recursive call like this fillsudoku(sudoku, row, col+1).

int fillsudoku(int sudoku[][9], int row, int col)
{
    if (col >= 9)
    {
         col = 0;
         ++row;
         if (row >= 9)
         {
             return 1;
         }
    }

    // Original code.
    // When doing a recursive call use ` fillsudoku(sudoku, row, col+1)`
    // You know the start of the code will test it.

Next I would exit early rather than have nested code.
This is a debatable point on style but I don;t think having to scroll down a long way to see a one lineer for failure helps in readability. And since you already exit early that is not a problem.

        if( sudoku[row][col] != 0) //pre filled
        {
            return fillsudoku(sudoku, row, col+1);
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if( isAvailable(sudoku, row, col, i+1) )
                {
                    sudoku[row][col] = i+1;

                    int good = fillsudoku(sudoku, row, col +1);
                    if (good)
                    {   return 1;
                    }
                    sudoku[row][col] = 0;
                }
            }
        }
        return 0;
}


Dijkstra's Algorithm C++ This is a basic implementation of Dijkstra's Shortest Path Algorithm for Graphs. I am looking for any kind of improvement.

/*
    Author: Stevan Milic
    Date: 10.05.2018.
    Dijkstra's Shortest Path Algorithm
*/
#include <stdio.h>
#include <limits.h>
#include <iostream>

#define N 9 // Number of Nodes in the graph

int minDistance(int distance[], bool visitedSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < N; v++)
        if (visitedSet[v] == false && distance[v] <= min)
            min = distance[v], min_index = v;
    return min_index;
}

void displayPath(int parent[], int s)
{
    if (parent[s] == -1)
        return;
    displayPath(parent, parent[s]);

    printf("-> %d ", s);
}

void display(int distance[], int n, int parent[])
{
    int start = 0;
    printf("Node\t     Distance\t         Path");
    for (int i = 1; i < N; i++)
    {
        printf("\n%d -> %d\t\t%d\t\t%d ", start, i, distance[i], start);
        displayPath(parent, i);
    }
}

void dijkstra(int graph[N][N], int start)
{
    int distance[N];

    bool visitedSet[N];

    int parent[N]; // For storing the shortest path tree

    for (int i = 0; i < N; i++) // This will make all distances as infinite and all nodes as unvisited
    {
        parent[0] = -1;
        distance[i] = INT_MAX;
        visitedSet[i] = false;
    }
    distance[start] = 0;
    for (int count = 0; count < N - 1; count++) // Finding the shortest path for all nodes
    {
        int u = minDistance(distance, visitedSet);

        visitedSet[u] = true;

        for (int n = 0; n < N; n++)
            if (!visitedSet[n] && graph[u][n] && distance[u] + graph[u][n] < distance[n])
            {
                parent[n] = u;
                distance[n] = distance[u] + graph[u][n];
            }
    }
    display(distance, N, parent);
}

int main()
{
    printf("***** Dijkstra's Shortest Path Algorithm ***** \n\n");
    int graph[N][N] = { {0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        {4, 0, 8, 0, 0, 0, 0, 11, 0},
                        {0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        {0, 0, 7, 0, 9, 14, 0, 0, 0},
                        {0, 0, 0, 9, 0, 10, 0, 0, 0},
                        {0, 0, 4, 0, 10, 0, 2, 0, 0},
                        {0, 0, 0, 14, 0, 2, 0, 1, 6},
                        {8, 11, 0, 0, 0, 0, 1, 0, 7},
                        {0, 0, 2, 0, 0, 0, 6, 7, 0 }
                      };
    dijkstra(graph, 0);
    printf("\n\n");
    system("pause");
    return 0;
}

The <iostream> header is not used.

min_distance can theoretically return an uninitialized value if all elements of visited_set are nonzero.  This shouldn't happen here, but initializing min_index = 0 would remove a potential problem and compiler warning.

display assumes that node 0 is the start node, but that value is passed in to dijkstra.  It should be passed in as a parameter.

In dijkstra, the graph parameter could be const int graph[N][N], which would then allow the graph variable in main to also be const.  The parent[0] = -1 assignment seems to be a typo.  It should be parent[i] = -1; to initialize all elements of parent.  The for (int n = 0; n < N; n++) loop should have curly brackets around its body.  While not currently necessary, having them in can avoid future problems when the code is modified and makes it clearer what is in the loop body rather than looking like a line with bad indentation.


Locating the largest Collatz Sequence with memoization Inspired by this question I wrote a memoized form of the collatz sequence calculator.

The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (on my PC) get that value up to 1427500000, which is a large number.

I ran this particular calculator and it eventually crashed (because Java long isn't big enough) as follows:

New best: 4890328815 at 1131 chains in 342.77514018s.
Value from chain 8528817511 at length 205 is negative: -7694391518238975012
At 10000000000 of 10000000000 (100%) in 712.666022051s
Best: 4890328815 at 1131 chains.
Largest number in any chain: 7168235036980384402

That is expected and intended. I just wanted to see what the largest value it could get to was.

Feel free to comment on anything related to the code.

public class CR_150878 {
    public static void main(String[] args) {
        long maxTestValue = 10000000000l;

        int maxLength = 0;
        long maxNumber = 0;
        int chainSize = 0;

        int maxSequenceMapLength = 1427500000;
        int[] sequenceLengthMap = new int[maxSequenceMapLength];

        long largestNumberAnyChain = 0;

        long startTime = System.nanoTime();
        for (long i = 2; i < maxTestValue; i++) {
            chainSize = 0;
            long currentNumber = i;

            while (currentNumber != 1) {
                if (currentNumber > 1 && currentNumber < maxSequenceMapLength && sequenceLengthMap[(int)currentNumber] != 0) {
                    chainSize += sequenceLengthMap[(int)currentNumber];
                    currentNumber = 1;
                } else {
                    if (currentNumber % 2 == 0) {
                        currentNumber = currentNumber / 2;
                    } else {
                        currentNumber = 3 * currentNumber + 1;
                    }
                    chainSize++;

                    if (currentNumber < 0) {
                        System.out.println("Value from chain " + i + " at length " + chainSize + " is negative: " + currentNumber);
                        currentNumber = 1;
                        i = maxTestValue;
                    }
                }

                if (currentNumber > largestNumberAnyChain) {
                    largestNumberAnyChain = currentNumber;
                }
            }

            if (i > 1 && i < maxSequenceMapLength) {
                sequenceLengthMap[(int)i] = chainSize;
            }

            if (chainSize > maxLength) {
                maxLength = chainSize;
                maxNumber = i;
                System.out.println("New best: " + maxNumber + " at " + maxLength + " chains in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s.");
            }

            if (i % (maxTestValue / 100) == 0) {
                System.out.println("At " + i + " of " + maxTestValue + " (" + (i / (maxTestValue / 100)) + "%) in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s");
            }
        }

        System.out.println("Best: " + maxNumber + " at " + maxLength + " chains.");
        System.out.println("Largest number in any chain: " + largestNumberAnyChain);
        System.out.println("Took: " + ((double)(System.nanoTime() - startTime) / 1000000000) + " seconds.");
    }
}

The class name is intentional, it was a code rewrite to that particular Code Review question.

It's a slightly optimized algorithm, instead of doing \$3n+1\$ I did \$(3n+1)/2\$ to avoid having to do all sorts of math to the next number, but then I lost the accuracy of the "Largest number in any chain" and whatnot values, so I undid it. (Believe it or not a whole minute was trimmed off execution time.)

This also solves the Project Euler 14 challenge in 0.13s.

Heap size

  The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (on my PC) get that value up to 1427500000, which is a large number.

When I try it with the same value, I run out of heap space.  That may be fixable by changing my JVM settings.

Optimizing by combining steps

                    if (currentNumber % 2 == 0) {
                        currentNumber = currentNumber / 2;
                    } else {
                        currentNumber = 3 * currentNumber + 1;
                    }
                    chainSize++;

You say that you found that it was faster if you divided by 2 in the else as well, but it gives inaccurate chainSize values.  Have you considered

                    if (currentNumber % 2 == 0) {
                        currentNumber /= 2;
                        chainSize++;
                    } else {
                        currentNumber = (3 * currentNumber + 1) / 2;
                        chainSize += 2;
                    }

This should give an accurate chainSize value if I'm understanding the optimization properly.

Also, this uses the briefer /= notation where i /= 2; has the same value as i = i / 2;.

Or

                    if (currentNumber % 2 != 0) {
                        currentNumber = 3 * currentNumber + 1;
                        chainSize++;
                    }

                    currentNumber /= 2;
                    chainSize++;

I'll leave it up to you if these help with run time as well.

Don't do useless checks

You have

                if (currentNumber > largestNumberAnyChain) {
                    largestNumberAnyChain = currentNumber;
                }

separate from the currentNumber update.  However, in two of the three branches, you reduce the value of currentNumber.

Consider what happens if you move it into the previous code.

                    if (currentNumber % 2 != 0) {
                        currentNumber = 3 * currentNumber + 1;
                        chainSize++;

                        if (currentNumber > largestNumberAnyChain) {
                            largestNumberAnyChain = currentNumber;
                        }
                    }

                    currentNumber /= 2;
                    chainSize++;

This is the only branch where currentNumber increases, so it's the only one that needs checked.

You could also move the check for negative numbers here for the same reason.  Note further that the largest check and the negative check will never be true at the same time.

Avoid timing output

                System.out.println("New best: " + maxNumber + " at " + maxLength + " chains in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s.");
            }

            if (i % (maxTestValue / 100) == 0) {
                System.out.println("At " + i + " of " + maxTestValue + " (" + (i / (maxTestValue / 100)) + "%) in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s");
            }
        }

        System.out.println("Best: " + maxNumber + " at " + maxLength + " chains.");
        System.out.println("Largest number in any chain: " + largestNumberAnyChain);
        System.out.println("Took: " + ((double)(System.nanoTime() - startTime) / 1000000000) + " seconds.");

If you write this instead as

            }
        }

        double elapsed = (double)(System.nanoTime() - startTime) / 1000000000;
        System.out.println("Best: " + maxNumber + " at " + maxLength + " chains.");
        System.out.println("Largest number in any chain: " + largestNumberAnyChain);
        System.out.println("Took: " + elapsed + " seconds.");

You might find that it runs faster.

Same problem with

                        System.out.println("Value from chain " + i + " at length " + chainSize + " is negative: " + currentNumber);

Measuring the time it takes to do the output distorts the overall timing.  It may not matter here, but it can be a bad habit to develop.


Function to convert from const char * to char** I made an adapter function to convert a const char * to char ** splitting the words in the initial string at each white space (leading, consecutive and trailing white spaces should be ignored).

#include <iostream>
#include <vector>
#include <cctype>

void str2arg(const char * str, std::vector<char*> & arg, std::string & memory) {
  arg.clear();
  memory.clear();
  bool copied_first_char = false;
  for ( size_t i = 0; str[i]!='\0'; ++i) {
    if (isspace(str[i])) {
      if (copied_first_char) {
        if (!isspace(str[i+1])) {
          memory += '\0';
        }
      }
    } else {
      copied_first_char = true;
      memory += str[i];
    }
  }
  if (memory.back()!='\0') memory += '\0';
  //from now on, memory should't be touched!
  for ( size_t i = 0; i < memory.length(); ++i ) {
    if (i==0 or memory[i-1]=='\0') arg.push_back(&memory[i]);
  }
}

int main() {
  std::vector<char*> av;
  std::string m;
  str2arg("   this is  a test   string   ", av, m);

  std::cout << "argc=" << av.size() << "  argv=" << av.data() << std::endl;
  for (auto i: av) std::cout << i << ".\n";
  return 0;
}

Basically the function takes the original C-string, a std::vector that will hold the pointers to the words, and a std::string for automated memory management.

In the first part of str2arg() I copy the chars from the original string substituting white spaces with the termination char '\0'. Then I push the char* into the vector looking at the positions of '\0'.

Of course both the vector and the string passed to str2arg() must then be used as read-only variables.

This looks fair, but I'm not totally proud of it...

I basically reject your code for admittance into the master branch.
This is not C++ code but primarily C and duplicates functionality that exists in the standard library.

Let's look at your interface first:

void str2arg(const char * str, std::vector<char*> & arg, std::string & memory) {

The parameter memory is only used internally to the function. It is not used externally and provides no utility. So get rid of it as a parameter. Make it an internal member of the function.

The parameter arg is used as an out parameter. You don't need to do this. Return the vector by value. This makes it very clear what you are doing. The optimizer will elide the copy and with move semantics in C++11 it will use move if it can not elide the copy. Summary: it is not an issue to return big values from functions the compiler will optimize away any issues (if for some reason it can't and you notice during benchmarking then you can have a look at using out parameters).

std::vector<char*> str2arg(const char * str);

Next issues is you are using pointers (and dropping the constness). Pointers are horrible and should only be used at the lowest level of your code for creating containers. Normally you can use normal objects to represent stuff. Here use std::string.

std::vector<std::string> str2arg(std::string const& str);
                                             ^^^^^^  Allows you to pass a literal.
                                                     That can be converted to a string.

Why are pointers horrible:
They do not provide any semantic definition of ownership. Ownership is a very important concept in C++ as it defines who is responsible for deleting an object. Normally we use containers and smart pointers to define ownership of dynamic objects and we refer to other objects via references when we don't own them.

Const correctness is a big deal in C++ this is something you should take to heart very quickly. You drop the constness on your pointers thus leading to a possibility where people incorrectly use the pointer you return (by modifying the content of the string). This is a real problem if the string is actually const and will cause the program to crash.

Algorithm:

Much improvement can be done here.
Let us examine the utilities provided by the standard.

Note 1:

The stream operator>> when applied to a std::string will read one space separated word from the stream.

  std::string word;
  stream >> word;  // drops leading space and reads a single space delimited word.

Note 2:

The std::istream_iterator<X> are iterators that treat streams as forward containers. They read X from the stream using operator>> and you can then access the object of type X with the standard iterator methods. Use this in combination with std::string and you can read words from a stream.

 std::istream_iterator<std::string> loop(stream);
 std::istream_iterator<std::string> end;

 for(;loop != end;++loop)
 {    std::cout << *loop << ".\n";
 }

Since we now have an iterator to scan through a stream of words we can also apply the standard algorithms.

 // Assuming the loop above had not drained the stream.
 // The following alternative copies a stream into the vector one word at a time.
 std::vector<std::string>  data;
 std::copy(loop, end, std::back_inserter(data));

Also note that std::vector has a constructor that takes iterators so you can build it directly, rather than using an algorithm.

 std::vector<std::string>  data(loop, end);

So now that we have gone through all that we can re-code your function like this:

#include <vector>
#include <string>
#include <sstream>
#include <iterator>
std::vector<std::string> str2arg(std::string const& str)
{
    std::stringstream  stream(str);
    std::vector<std::string>  result((std::istream_iterator<std::string>(stream)),
                                     std::istream_iterator<std::string>());
    return result;
}

Side note.

Since we mention command line args in other answers.
I like to convert the command line args into string before proceeding.

int main(int argc, char* argv[])
{
    std::vector<std::string>  args(argv+1, argv + argc);
}

main

int main()
{
    std::vector<std::string>  data = str2arg("   this is  a test   string   ");
    std::vector<char*>        ptr;
    // Doing it like this because I don't feel inclined to go look
    // up the appropriate iterator adapter to convert a string into a pointer.
    std::for_each(args.begin(), args.end(),
                  [&ptr](std::string& a){ptr.push_back(&a[0]);});

    SomeCFunctionThatNeedsPointers(&ptr[0]);
}

Main with Boost

#include <boost/iterator/transform_iterator.hpp>

int main()
{
    typedef boost::transform_iterator<std::function<char*(std::string&)>,
                                      std::vector<std::string>::iterator
                                     >    ti;

    std::vector<std::string>  data = str2arg("   this is  a test   string   ");
    std::vector<char*>        ptr(ti(args.begin(), [](std::string& x){return &x[0];}), ti(args.end()));

    SomeCFunctionThatNeedsPointers(&ptr[0]);
}