HackerRank Time Conversion solution The challenge (PDF) is to convert a time from 12-hour format (hh:mm:ssAM or hh:mm:ssPM) to 24-hour format.

This is my solution, which worked for all test cases.

string timeConversion(string s) {
    int size = s.length();
    if(s[size-2]=='A'){
        string hh = s.substr(0,2);
        int h = stoi(hh);
        if(h==12){
            string newh = "00";
            string newTime = newh.append(s.substr(2,6));
            return newTime;
        }else{
            return s.substr(0,size-2);
        }
    }
    else{
        string hh = s.substr(0,2);
        int h = stoi(hh);
        if(h==12){
            return s.substr(0,size-2);
        }
        int inPM = h+12;
        string newh = to_string(inPM);
        string newTime = newh.append(s.substr(2,6));
        return newTime;
    }
}

Anything which I could have done in a different way in your opinion?

Since the question gives a couple of guarantees about the input, take advantage of them. If you want to communicate these preconditions, assert them. Something like

string timeConversion(string s) {
    // Assume input is in the format hh:mm:ssAM or hh:mm:ssPM
    assert(s.length() == 10);
    int size = s.length();
    ...

...
if(s[size-2]=='A'){
    string hh = s.substr(0,2);
    int h = stoi(hh);
    ...
else{
    string hh = s.substr(0,2);
    int h = stoi(hh);
    ...

You do the same thing no matter which branch is taken. You can hoist this in front of the if statement

string hh = s.substr(0, 2);
int h = stoi(hh);
if (s[8] == 'A') {
    ...
} else {
    ...
}

After the previous step, the logic left is fairly straight-forward.

If it is AM and the hours read 12, set hh = "00". Otherwise do nothing.
If it is PM add the hours read 12, do nothing. Otherwise add 12 to the hours.

This is good. One thing to note is that two paths lead to the same conclusion of do nothing or don't change the time. I would keep the exact same logic and restructure a little to avoid redoing work.

...
if (s[8] == 'A') {
    if (h == 12) {
        // 12:mm:ssAM -> 00:mm:ss
        hh = "00";
    }
} else if (h != 12) {
    // 12:mm:ssPM -> 12:mm:ss, otherwise add 12 hours.
    hh = to_string(h + 12);
}

return hh + s.substr(2, 6);


Calculating Fibonacci numbers The following problem is currently taking more than 8 seconds to execute. Please help me to modify the program, so that execution time will be reduced.

var yourself = {
fibonacci : function(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    else {
        return this.fibonacci(n - 1) +
            this.fibonacci(n - 2);
    }
}
};

This is one of the standard examples for algorithmic complexity.  This algorithm is very easy to understand since it matches the mathematical definition well, but performs miserably since it's trying to calculate a number that grows exponentially by adding 0s and 1s together.

The key observation is that to calculate, say, fibonacci(5), it has to recursively calculate fibonacci(4) and fibonacci(3).  Then to calculate fibonacci(4), it has to calculate fibonacci(3) again, which is completely wasteful.  There are several things we can do to go faster:

Build from the bottom up.  Start two variables a=0 and b=1, then run a loop where you set a=b and b=a+b (careful to not blast values as you're using them).  This is how you would do it by hand.
Use your recursive solution, but cache the results so that it doesn't repeat work.  This is called memoization.
Use the closed-form formula.


Concatenate unless note mails = []
mails.concat(@note.cc_emails) unless @note.cc_emails.nil?
mails.concat(@note.to_emails) unless @note.to_emails.nil?

Everything what I'm doing here is checking is @note.cc_emails is not nil then concatenating it in mails array.
How can I write it in more efficient way & also reduce the number of lines in the code (if possible)?

These things are very much a matter of preference but I would go for something like:

mails = [ @note.cc_emails,
          @note.to_emails ].compact.join('')

which tends to remain usable as you add more clauses


Haskell: rndFile and [Char] vs IO String error import System.Environment (getArgs)
import Random

main = do
  args <- getArgs
  let len = length args
  let n = if len < 1 then 10000 else  read (args !! 0) :: Int
  let fileName = if len < 2 then show n ++ "-output.txt"  else args !! 1
  str <- rndStr n
  writeFile fileName (str)
--  writeFile fileName (rndStr n)
-- Couldn't match expected type `[Char]' with actual type `IO String'

rndStr :: Int -> IO String
rndStr n  = sequence . replicate n . randomRIO $ (' ', '~')

This code works. It creates size n file of random chars. That's good.

I have 2 questions:
1. Is my argument sanitizing ok? If not, how to make it better?
2. Swapping writeFile str for writeFile (rndStr n) produces [Char] vs IO String error.
Why? Shouldn't it be the same?
I manage this to work by accident, not because I know what I did.

Congratulations on your progress, :) Welcome to monads

First thing you have to keep in mind is to restrict the time spent in imperative world. So take out as much stuff as you can from the do ..., and refactor them into smaller non-IO code.

import System.Environment (getArgs)
import System.Random
import Control.Monad

Another advice is to avoid magic numbers in your code. If there are any, they should be declared in a highly visible area along with their purpose rather than buried deep in the code.

minLen = 10000

main = do
    args <- getArgs
    writeFile (getFileName args) =<< rndStr (getFileSize args)
  where getFileSize [] = minLen
        getFileSize (x:xs) = read x :: Int
        getFileName [x] = x ++ "-output.txt"
        getFileName (x:y:[]) = y

As you can see, the reason you can't use rndStr directly is that rndStr uses IO. So it cannot be directly used as a function. You can think of it this way. rndStr returns some thing that is wrapped in a box. You need special constructs to unbox it, and the special construct is either <- . You might also notice that main has the same kind of signature.

That isn't a really good analogy, and I am not the best teacher :). So if you really want to understand what happens, it might be better to read any simple monad tutorial.

rndStr :: Int -> IO String
rndStr n  = sequence . replicate n . randomRIO $ (' ', '~')

Try this approach if it makes better sense to you. When you start ghci, use this flag

ghci -XImplicitParams

On the prompt after loading your program, try to execute writeFile which was not accepting (rndStr number) earlier, but this time, instead of that expression, replace it by ?check

> writeFile (getFileName ["5"] ) ?check

You will get back some thing like

<interactive>:0:32:
  Unbound implicit parameter (?check::String)
    arising from a use of implicit parameter `?check'
    In the second argument of `writeFile', namely `?check'
    In the expression: writeFile (getFileName ["5"]) ?check
    In an equation for `it': it = writeFile (getFileName ["5"]) ?check

Ignore every thing except the second line, the Unknown implict .. tells you that ghc expected any exprssion in place of ?check would be a string.

Now try finding the type of our expression (rndStr number)

> :t rndStr 5
rndStr 5 :: IO String

As you can see, rndStr number has a different type IO String than the expected String. This is the reason you cant use rndStr number there, and why we have to do all that above.

Note that my statement writeFile (getFileName args) =<< rndStr (getFileSize args) is really same as

do
str <- rndStr (getFileSize args)
writeFile (getFileName args) str

Try to work out how it is so.


Improving performance of Ruby socket programming Server:

require 'socket'
require 'time'
require 'ap'

server = TCPServer.open(1026)

def process_the_request req, client # not important, disk-related process
  sleep 2
  req.to_s + ' ' + client.peeraddr[3].to_s + ' ' + Time.now.to_s
end

loop do

  Thread.start(server.accept) do |client|

    request = ''
    ch = ''

    begin

      ch = client.getc
      print ch

      if (ch.nil? or ch.ord == 13 or ch.ord == 10)

        if request.length < 1
          break if client.eof?
          next
        end

        ap "request: " + request
        response = process_the_request request, client
        ap "response: " + response
        client.puts response
        request = ''
        break if client.eof?

      else
        request += ch
      end

    end while true

    #ap "thread closed"
    client.close

  end # Thread

end # loop

Client:

nn='nc 127.0.0.1 1026'
echo -n '1' | $nn &
echo '2' | $nn &
echo -n '3' | $nn &
echo '4
5
6
7' | $nn &

You shouldn't read from the client one byte at a time.  Call client.gets to take a line at a time.


Binding touch events and moving an element I have the following jQuery plugin that binds touch events and moves an element.

In the functions moveMe and snap, there is duplicate code doing the same thing because I couldn't figure out how to refactor the scope of the functions to only do this once.

$.fn.draggable = function(limit) {

  var offset = null;
  var start = function(e) {
    var orig = e.originalEvent;
    var pos = $(this).position();
    offset = {
      x: orig.changedTouches[0].pageX - pos.left,
      //y: orig.changedTouches[0].pageX - pos.top
    };
    $(this).stop(true,false);
  };

  var moveMe = function(e) {
    e.preventDefault();
    $('body').css('overflow-x','hidden');

    var orig    = e.originalEvent;
    var touchX  = orig.changedTouches[0].pageX;
    var difference = touchX - offset.x;
    var move;

    if (difference >= limit) {
        move = limit;
    } else if (difference <= 0) {
        move = 0;
    } else {
        move = difference;
    }

    $(this).css({
      left: move,
      //left: orig.changedTouches[0].pageX - offset.x
    });

  };

  var snap = function(e) {

    var orig    = e.originalEvent;
    var touchX  = orig.changedTouches[0].pageX;
    var difference = touchX - offset.x;
    var threshold = limit*0.75;

    if (difference >= limit) {
        move = limit;
    } else if (difference <= 0) {
        move = 0;
    } else {
        move = difference;
    }

    if (threshold > (limit-move)) {
        $(this).animate({
            left : limit
        });
    } else {
        $(this).animate({
            left : 0
        });
    }

    };

  this.bind("touchstart", start);
  this.bind("touchmove", moveMe);
  this.bind("touchend", snap);

};

$("#container").draggable(200);

Could you write something like this?

var limited = function( value, limit ){
    if (value >= limit) {
        return limit;
    } else if (value <= 0) {
        return 0;
    } else {
        return value;
    }
}

then, when you need to work out move, just write move = limited( difference, limit );


Google CodeJam 2016 - Python Counting Sheep I decided to try some google codejam problems to get some more experience coding. The problem is at http://code.google.com/codejam/contest/6254486/dashboard, my solution is below. It gets the correct solution but would appreciate any tips on coding.

Problem

  Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

  Bleatrix must start with N and must always name (i + 1) × N directly after i × N. For example, suppose that Bleatrix picks N = 1692. She would count as follows:

  N = 1692. Now she has seen the digits 1, 2, 6, and 9. 2N = 3384. Now she has seen the digits 1, 2, 3, 4, 6, 8, and 9. 3N = 5076. Now she has seen all ten digits, and falls asleep. What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA instead.

  Input

  The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a single integer N, the number Bleatrix has chosen.

  Output

  For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the last number that Bleatrix will name before falling asleep, according to the rules described in the statement.

Code

import os

def getnumber(number,numberoftries):
  N = number
  digitlist = []
  print "new case number = " + str(number)
  for j in range(1,numberoftries):
    N = str(N)
    N.rstrip()
    digits = []
    for l in range(0,len(N)):
      if N[l] not in digits:
        digits.append(N[l])
       # print digits
    for l in range(0,len(digits)):
      k = digits[l]
      #  Add digits to digitlist
      if k not in digitlist:
        digitlist.append(k)
        print digitlist
  # check if we have all digits
    count = 0
    for k in range (0,10):
      if str(k) in digitlist:
        count = count + 1
    if count == 10:
      print "count = 10"
      return str(N)
    else:
      N = number * (j+1)
      print "number = " + str(N)
  return "INSOMNIA"

numberoftries = 1000
path = '/home/username/GoogleCodeJam/'
inputfile = 'A-large-practice.in'
inputfilename = path + inputfile
outputfilename = path + 'largeoutput'
f = open(inputfilename, "r")
numberofcases = f.readline()
o = open(outputfilename,"w")
for i in range (1,int(numberofcases)+1):
  N = f.readline()
  N = int(N)
  result = getnumber(N,numberoftries)
  outputline = 'Case #' + str(i) + ': ' + str(result) + '\n'
  o.write(outputline)
o.close()

In general, it is difficult to follow the logic and the code is not readable.

First, here are some general things you can improve:

N.rstrip() does not modify a string in place and returns a new string instead. Since you are not assigning the result to anything, it does nothing
according to PEP8, you should put underscores between the words in variable and function names - number_of_tries vs numberoftries or digitlist vs digit_list, get_number() vs getnumber()
following the previous note - N is not a good variable name
remove unused import
count = count + 1 can be rewritten as count += 1
put the main logic of the program into if __name__ == '__main__':
use print() function instead of a statement for Python 3.x compatibility
use with context manager when opening file(s) - this will ensure it being properly and safely closed
use os.path.join() to join the path components (okay, you now need to get your import os back :)
define constants in upper case (PEP8 reference)
use list comprehensions
use .format() instead of string concatenation
use built-in sum() function to for counting
loop over the items directly instead of indexes

The code after applying the changes:

import os

NUMBER_OF_TRIES = 1000
BASE_DIRECTORY = '/home/username/GoogleCodeJam/'
INPUT_FILE_NAME = 'A-large-practice.in'
OUTPUT_FILE_NAME = 'largeoutput'

def get_number(number, number_of_tries):
    print("new case number = {number}".format(number=number))

    digit_list = []
    current_number = number
    for j in range(1, number_of_tries):
        number_as_string = str(current_number)

        digits = []
        for item in number_as_string:
            if item not in digits:
                digits.append(item)

        for digit in digits:
            if digit not in digit_list:
                digit_list.append(digit)

        count = sum(1 for k in range(0, 10) if str(k) in digit_list)
        if count == 10:
            print("count = 10")
            return number_as_string
        else:
            current_number = number * (j + 1)
            print("number = {number}".format(number=number))

    return "INSOMNIA"

if __name__ == '__main__':
    input_file_name = os.path.join(BASE_DIRECTORY, INPUT_FILE_NAME)
    output_file_name = os.path.join(BASE_DIRECTORY, OUTPUT_FILE_NAME)

    with open(input_file_name, "r") as input_file, open(output_file_name, "w") as output_file:
        number_of_cases = next(input_file)
        for case_number in range(1, int(number_of_cases) + 1):
            number = int(next(input_file))
            result = get_number(number, NUMBER_OF_TRIES)

            output_file.write('Case #{case_number}: {result}\n'.format(case_number=case_number, result=result))

Alternative Solution:

We can also improve on both the performance and readability if we would use sets - collecting the digits seen so far until the length of the set is 10 (collected all digits) or we reach the maximum number of tries:

def get_number(number, number_of_tries):
    digits = set([])  # keep track of all seen digits

    current_number = number
    for j in range(1, number_of_tries):
        digits |= set(str(current_number))  # add new digits to the seen set

        if len(digits) == 10:  # exit if collected all the digits
            return current_number
        else:
            current_number = number * (j + 1)

    return "INSOMNIA"


Simple Rock Paper Scissors in C++ I have made a Rock Paper Scissors game. It works fine but I would like to know how can I improve it further.

#include <iostream>
#include <algorithm>
#include <string>
#include <random>
#include <array>
#include <map>
#include <limits>

namespace
{
    enum Winner { Tie, Player, Computer, WinnerCount };
    enum Items { Rock, Paper, Scissors, ItemsCount };

    template<typename T, std::size_t N>
    using Matrix = std::array<std::array<T, N>, N>;
}

std::string ask_guess(const std::array<std::string, Items::ItemsCount>& data)
{
    std::string result;
    auto comp = [&result](const std::string& str){ return str == result;};
    bool is_good = false;

    while (!is_good)
    {
        std::cout << "Enter your choice, rock, paper, or scissors: ";
        std::getline(std::cin, result);

        if (std::cin.fail() || std::none_of(data.begin(), data.end(), comp))
        {
            std::cout << "Not valid input.\n";
            if (!result.empty()) result.clear();
            is_good = false;
        }
        else
        {
            is_good = true;
        }

        std::cin.clear();
        std::cin.ignore(std::cin.rdbuf()->in_avail());
    };

    return result;
}

bool play_again()
{
    char result;
    bool is_good = false;

    while (!is_good)
    {
        std::cout << "Do you want to play again? [y/n]: ";
        std::cin >> result;
        result = std::toupper(result);

        if (std::cin.fail() || (result != 'Y' && result != 'N'))
        {
            std::cout << "Not valid input.\n";;
            is_good = false;
        }
        else
        {
            is_good = true;
        }

        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    };

    return result == 'Y';
}

int main()
{
    // Set up game
    const Matrix<Winner, Winner::WinnerCount> table
    {
        {  // Rock      Paper      Scissors
            { Tie,      Computer,  Player   }, // Rock
            { Player,   Tie,       Computer }, // Paper
            { Computer, Player,    Tie      }, // Scissors
        }
    };

    const std::array<std::string, Items::ItemsCount> data
    {
        "rock",
        "paper",
        "scissors"
    };

    std::map<std::string, Items> bindingItems
    {
       { data[Items::Rock],      Items::Rock     },
       { data[Items::Paper],     Items::Paper    },
       { data[Items::Scissors],  Items::Scissors },
    };

    std::map<Winner, std::string> winnerResult
    {
       { Winner::Tie,        "It's a tie!\n\n"  },
       { Winner::Player,     "You win!\n\n"     },
       { Winner::Computer,   "You lose!\n\n"    },
    };

    std::mt19937 engine{ std::random_device()() };
    auto dist = std::uniform_int_distribution<>(0, Items::ItemsCount - 1);

    // Game loop
    do
    {
        std::cout << "\n\n\tRock Paper Scissors Game\n\n";

        const auto userChoice = ask_guess(data);
        const Items player = bindingItems[userChoice];

        const Items computer = static_cast<Items>(dist(engine));
        const auto computerChoice = data[computer];

        std::cout << "\n\nYou entered: " << userChoice << '\n';
        std::cout << "Computer chose: " << computerChoice << '\n';

        std::cout << winnerResult[table[player][computer]];
    }
    while(play_again());
}

Here are some things that may help you improve your code.

Simplify the code

This seems to be rather a lot of lines of code for a very simple game.  For example, the ask_guess and play_again both do essentially the same thing.  They show a prompt, wait for input and then check to assure the input is one of the valid choices.  Since it's done for two different things and has both associated data and functionality, that suggests an object.

Simplify winner detection

Each player has only three choices, and if we take them in the order of "rock, paper, scissors" then for any choice n, the choice n+1 wins, choice n-1 loses, and n means a tie (obviously this is all mod 3).  This allows for very simple mathematics to determine the winner.

Make all strings named constants

If you ever wanted to make, say, a German version of the game, it would be simple if all of the strings were in one location.  If they're all const, then it doesn't have much impact on the runtime speed and there really aren't that many strings.

A proposed alternative

Here's an alternative that incorporates all of these suggestions:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <cctype>

class Menu {
private:
    const std::string prompt;
    const std::vector<std::string> choices;
    const std::string error_msg;
public:
    Menu(const std::string &prompt_string, const std::vector<std::string>& items, const std::string &err_msg)
    : prompt{prompt_string},
      choices{items},
      error_msg{err_msg}
    {}
    size_t size() const { return choices.size(); }
    const std::string& operator[](int i) const { return choices[i]; }
    size_t get_choice(std::istream& in=std::cin, std::ostream& out=std::cout) const {
        bool first = true;
        auto it = choices.end();
        do {
            if (!first) {
                out << error_msg;
            }
            out << prompt;
            std::string result;
            std::getline(in, result);
            std::transform(result.begin(), result.end(), result.begin(), [](unsigned char ch){ return std::tolower(ch);});
            it = std::find(choices.begin(), choices.end(), result);
            first = false;
            in.clear();
            in.ignore(in.rdbuf()->in_avail());
        } while (it == choices.end());
        return std::distance(choices.begin(), it);
    }
};

int main() {
    const Menu rps{"Enter your choice, rock, paper, or scissors: ",
        { "rock", "paper", "scissors"}, "Not valid input.\n"};
    const Menu again{"Do you want to play again? [y/n]: ",
        {"y", "n"}, "Not valid input.\n"};
    const std::vector<std::string> results{
        "It's a tie!", "You win!", "You lose!"};
    const std::string title{"\n\n\tRock Paper Scissors Game\n\n"};
    const std::string youchose{"\n\nYou entered: "};
    const std::string computerchose{"\nComputer chose: "};
    std::mt19937 engine{ std::random_device()() };
    auto dist = std::uniform_int_distribution<>(0, rps.size()-1);
     // Game loop
    do {
        std::cout << title;
        const auto user = rps.get_choice();
        const auto computer = dist(engine);
        std::cout << youchose << rps[user]
            << computerchose << rps[computer] << '\n'
            << results[(user + rps.size() - computer) % rps.size()]
            << "\n\n";
    }
    while(!again.get_choice());
}


Long cache refresh with guaranteed response I am trying to ensure that (once a cache item is populated) even if it's refresh object takes a long time to retrieve, the original cache item can be requested.

using System;
using System.Runtime.Caching;

namespace LongCacheTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Cacher.Add("key", "object", Get);

            Console.ReadLine();
        }

        public static Object Get()
        {
            // load big file from disck
            return "stuff";
        }
    }

    public class Cacheable
    {
        public delegate Object CacheEntryGet();

        public Object Obj { get; set; }
        public CacheEntryGet Getter { get; set; }
    }

    public class Cacher
    {
        private static MemoryCache _cache = null;

        private static MemoryCache Cache => _cache = _cache ?? new MemoryCache("long");

        private static CacheItemPolicy Policy => new CacheItemPolicy
        {
            AbsoluteExpiration = new DateTimeOffset(DateTime.Now.AddHours(1)),
            Priority = CacheItemPriority.Default,
            RemovedCallback = DidRemove
        };

        public static void DidRemove(CacheEntryRemovedArguments args)
        {
            Cache.Add(args.CacheItem.Key, args.CacheItem.Value, Policy);

            var item = args.CacheItem.Value as Cacheable;

            item.Obj = item.Getter();

            Cache.Remove(args.CacheItem.Key);
            Cache.Add(args.CacheItem.Key, item, Policy);
        }

        public static void Add(string key, Object obj, Cacheable.CacheEntryGet getter)
        {
            var item = new Cacheable{
                Obj = obj,
                Getter = getter
            };

            Cache.Add(key, item, Policy);
        }
    }
}

The practice here is to provide a method Getter and cache it alongside the cached Object. When the cache item expires, it is reinserted and the Getter method is called to get the refresh object. Once the fresh object is retrieved it replaces the original cache item.

How do I use this?

I don't understand how to use this.  It took me some time to understand the reason for the getter, and I can't see how to retrieve anything from this cache.

Why do I need to Add the value when I have the delegate?

In the Add method, it doesn't make sense to add provide both a value and a method that calculates the value; it is very likely that someone will pass in inconsistent arguments and get unexpected results.  It should suffice to simply pass in the delegate, and let the value calculate itself.

Why is this static?

It is very dangerous to have one global cache holding every different type.  You should allow for multiple caches for different purposes, and then you can...

Make this cache generic

Nobody likes to cast from Object.  Your interface should be Cacheable<T>, so that we can check at compile time that the type to be returned is what we expect.

Your response is not guaranteed

Your callback is only called after the item has been removed from the cache.  Even if you add the previous value back straight away, a poorly-timed interrupt could have another thread searching for a key in that split-millisecond it's not there.


replacing characters in string one by one to create target string while doing a code clash on codingames, in which we had to replace a character in a string one by one to transform it into a target string, printing out every itteration of the new string, resulting in something like this:

"Turtle Ham"
"Hurtle Ham"
"Hartle Ham"
"Hamtle Ham"
"Ham le Ham"
"Ham Me Ham"
"Ham Ma Ham"
"Ham MakHam"
"Ham Makeam"
"Ham Makerm"
"Ham Maker!"

This is de code I came up with, in Javascript.

var source = "Turtle Ham";
var target = "Ham Maker!";
var safe = source;
String.prototype.replaceAt=function(index, character) {
    return this.substr(0, index) + character + this.substr(index+character.length);
}
console.log(source);
for(var i=0; i < source.length; i++) {
    source = source.replaceAt(i, target.charAt(i));
    if(source == safe) {

    } else {
     console.log(source);
     safe = source;
    }
}

would there be any more effective way of doing this in Javascript?

As Tyler Flynn pointed out in a comment, you should flip the conditional from "equals" to "not equals" to avoid the (current empty) if branch:

if(source != safe) {
  console.log(source);
  safe = source;
}

I'd avoid extending the String prototype. The method you're adding is pretty generic, and could be reusable, so it's not a terrible thing to add, but still. Extending prototypes is generally considered bad form - not because it'll instantly break anything, but rather because if everybody did it, they might defined replaceAt in some other way, and break your code. Or your extension would break their code. So extending prototypes, while often tempting, should be considered carefully.
In this case, it'd be just as simple to have a replaceAt(string, index, character) function that you call with the string, instead of calling it on the string.

Other than that, you code seems OK. There are a ton of other approaches you could take, of course, but without some external metric to judge by, yours is as good as any other.

However, there's one issue which irks me a little: source is mutated. With your current code, you can't print the original string after the loop has run, because you've "lost" it - source just becomes equal to target. I'd keep source and target unaltered, and generate a third "result" string for each step instead.

This also points to an alternative approach: Instead of replacing characters, create a new string by glueing parts of the two others together.

var source = "Turtle Ham";
var target = "Ham Maker!";

var lastResult = null;

for(var i = 0; i <= source.length ; i++) {
  var result = target.substr(0, i) + source.substr(i);

  if(result != lastResult) {
    console.log(result);
  }

  lastResult = result;
}

This code doesn't even need a separate function or prototype extension, and doesn't mutate the input (source and target) strings. It also doesn't need an extra console.log to show the original; everything happens in the loop, which runs from 0 characters replaced to source.length (inclusive) characters replaced.


Is indentation of #if & #endif directives an important readability convention? I'm sharing C# code with a fellow programmer who is more use to writing C++. He uses #if and #endif directives (which I do not tend to use) and when they occur they have no indentation, for example

        private void dumpToDisplay()
        {
#if false
            ushort[] ScanStatus = new ushort[6];
            for (int ch = 0; ch < 6; ch++)
                ScanStatus[ch] = mySteppers.GetStatus(ch);

            return;
#endif
            string dumpString = stepDump();

            Debug.Print(dumpString);
        }

It is interesting that the code sample in the #if C# documentation adopts the same convention and has no indentation for the #if and #endif directives. Is this important? It certainly makes them stand out, but is that good?

I think it makes sense this way, because the #if directives are pretty much outside of the normal syntax. For example, you can write something like:

#if DEBUG
    if (CheckConditionDebug())
    {
        DoADebug();
#else
    if (CheckCondition())
    {
        DoA();
#endif
        DoB();
    }

This is valid code in both states (DEBUG defined or not), but there is no good way to indent the directives.

Note: I'm not saying that this is a good use of #if, just that it is a possible use and that it makes sense to take this into account.


Enhancing search using Fuzzy Logic in NodeJS Brief Description:

In my NodeJS Application, I have a model called User.

User.js

module.exports = {

  attributes: {
    name: {
      type: 'string'
    }
  }
};

My application consists users searching functionality using name attribute. For that I used find users using exact name as below(I am using MongoDB as my Database). My User Controller as below.

UserController.js

 var name = req.param('name');

 User.find({ name: { 'contains': name } }).exec(function (err, results) {
     if (err) {
         return res.serverError(err);
     }
     return res.send(results);
 });

Now I need to enhance my searching functionality.

As an example if my DB contains record as Michael and if I searched as micel, Michael should be given as a search result.

For that I used Fuzzy Logic Algorithm and I used fuzzy npm package. Now my implementation is as below.

UserController.js

var fuzzy = require('fuzzy');

module.exports = {

    search: function (req, res) {

        var term = req.param('name');
        var thisCtrl = this;

        User.find().exec(function (err, users) {

            if (err) {
                return res.serverError(err);
            }
            thisCtrl.createSearchQuery(term, users, function (orQuery) {
                User.find({or: orQuery}).exec( function (err, finalResulst) {
                    if (err) {
                        return res.serverError(err);
                    }
                    return res.send(finalResulst)
                })
            })
        });
    },

    createSearchQuery: function (term, users, cb) {

        var userNamesArr = [];
        var or = [];

        for (var i = 0; i < users.length; i++) {
            userNamesArr.push(users[i].name)
        }

        var results = fuzzy.filter(term, userNamesArr);
        var matches = results.map(function(el) { return el.string; });

        for (var i = 0; i < matches.length; i++) {

            var tempTerm = { name: { 'contains' : matches[i] }};
            or.push(tempTerm)
        }
        cb(or);
    }
};

This is working as I needed.

But My Question is,

I am getting all the users in my DB and create search term using Fuzzy Logic and finding again in User collection. Now this is ok if I have only about 100 user records. But the time when User collection contains Millions of user records , Will this causes to performance issue to my application or is there a Better Approach than this I should follow.

Sorry for my bad English and Suggestions are highly appreciated.

Question

  "Will this causes to performance issue to my application or is there a Better Approach than this I should follow."

Well that will depend on a lot of factors.

1million clients.
fuzzy.js and its performance.
A single medium level server.

State of development

First a quick look at the link you provided to fuzzy and at the bottom of the page you find the ToDo list which contains 2 points of interest

  Async batch updates so the UI doesn't block for huge sets. Or maybe Web Workers?
  Performance performance performance!

Following through to the gitHub repository and we find that the last activity was 3 years ago. This suggests (not implies) that development has ended. That a key issue recognized by the developers (performance) will not be worked on in the near future.

Performance

To try and determine the performance per search entry I went to their demo and timed the search over several differently size lists of names, and search strings.

The performance test shows a slightly below linear complexity (in the range of 628 - 1,250,000 names), however its too close to call and the safe bet is its linear. It searched 1.25million names in ~1 +/- 0.2seconds

Tests method

The test was performed in the console running the following snippet many times

t = performance.now();
res = fuzzy.filter(searchStr, data);
totalTime += performance.now() - t;
count ++;

A complex regular expression, on the same data required 1/10th the time.

t = performance.now();
res = data.filter(name => regExpSearch.test(name));
totalTime += performance.now() - t;
count ++;

Conclusion

What Node.js does well is IO, and what is does not do well is processing.

Assuming one medium level server.

1 second for a search is a very long time.
Fuzzy.js performance is unlikely to change.
A response time over a second puts your site in the bottom 20% of services, and is unacceptable.
I estimate that at 30 thousand users performance will become a serious problem (see below)

If you are serving 1million active users, (using the 20/80 rule) with 20% of users visiting your site one day a year 20% of them once a month and 20% of them once a week (~600,000 searches a year) with users geographically clustered resulting in significant peak times.

It is highly likely that you will regularly have 30+ concurrent queries and a few times a year you can expect 300, in which case your server will be blocked for over 5 minutes.

(NOTE) these are very rough estimates based on one search per user per visit.

The answers

  "Will this causes to performance issue to my application or..."

Yes for a very heavy trafficked site this will present a serious performance issue.

No for a very small traffic loads nobody will notice.

  "...is there a Better Approach than this I should follow."

Yes of course there is, use a regExp, and there are many more. But I can not hand out advice on speculation. The information given above is already dubious as it is based on a single request rather than the site/service as a whole.

Refection

Well gee... any nerd knows this...

1+ million regular users is cash in the bank.

A service must start somewhere and that is with a few users, with growth being gradual and predictable (once moving). If you are monetizing the service then growth is great and not a problem (if managed well).

Start with the basics and work your way up. Replacing infrastructure (the search methods, upgrading the server/s) is part of the business. Performance is the least of your initial problems.

If you plan for viral growth then you are in the realm of highly speculative investment capital. Outsource a solution to people that have the experience or you will miss a lucrative opportunity.

If you plan to provide a free service for 1+ million users, good on you :), but you will need to have a fairly deep pocket.


Calculating the factorial of a number efficiently I was trying to calculate the factorial of a large number in a short time:

class TestClass {
    public static void main(String args[] ) throws Exception {
        BufferedReader keyboard=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(keyboard.readLine());
        while(n!=0){
            int uptoValue=Integer.parseInt(keyboard.readLine());
            calculateFactorial(uptoValue);
            n--;
        }
    }
    private static void calculateFactorial(int uptoValue) {
        // TODO Auto-generated method stub
        BigInteger answer=new BigInteger("1");
        for(int i=1;i<=uptoValue;i++){
            answer=answer.multiply(new BigInteger(String.valueOf(i)));
        }
        System.out.println(answer);
    }
}

Which gave me total sum of  running  time of 1.7618 against various inputs.

Now I tried to solve it using pattern decomposition to avoid the number of loops, and wrote the following code:

class TestClass {
    public static void main(String args[] ) throws Exception {
        BufferedReader keyboard=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(keyboard.readLine());
        while(n!=0){
            int uptoValue=Integer.parseInt(keyboard.readLine());
            calculateFactorial(uptoValue);
            n--;
        }
    }
    private static void calculateFactorial(int uptoValue) {
        // TODO Auto-generated method stub
        BigInteger answer=new BigInteger("1");
        boolean oddUptoValue=false;
        int tempUptoValue=0;
        if(uptoValue%2!=0){
            tempUptoValue=uptoValue-1;
            oddUptoValue=true;
        }else{
            tempUptoValue=uptoValue;
        }
        for(int i=1;i<=tempUptoValue/2;i++){
            int temp=(tempUptoValue-i+1)*i;
            answer=answer.multiply(new BigInteger(String.valueOf(temp)));
        }
        if(oddUptoValue){
            answer=answer.multiply(new BigInteger(String.valueOf(uptoValue)));
        }
        System.out.println(answer);
    }
}

Which gave me a total sum of running time of 1.6362 sec against various inputs.

How can I improve the runtime? What are more efficient algorithms to calculate the factorials of a large number?

How can I improve the runtime? What are more efficient algorithms to calculate the factorials of a large number?

If you really want to know it, then study BigIntegerMath.factorial from Guava. There are too many tricks there to be described here.

Review

// TODO Auto-generated method stub

Are you sure you need it?

    boolean oddUptoValue=false;
    int tempUptoValue=0;
    if(uptoValue%2!=0){
        tempUptoValue=uptoValue-1;
        oddUptoValue=true;
    }else{
        tempUptoValue=uptoValue;
    }

Too complicated. What about

boolean oddUptoValue = uptoValue % 2 != 0;

and leaving oddUptoValue alone, as the division by two rounds down anyway.

int temp=(tempUptoValue-i+1)*i;

This can overflow, use

long product = (tempUptoValue - i + 1L) * i;

Note the name, the formatting (spacing), and the use of 1L which enforces a cast to long of both multiplicands.

 answer=answer.multiply(new BigInteger(String.valueOf(temp)));

This should be

 answer = answer.multiply(BigInteger.valueOf(product));

Optimizations

Despite avoiding the conversion via string being much faster, my above changes won't help with speed. The vast majority of the time for big inputs get spend in the BigInteger multiplication.

The simplest trick is getting rid of powers of two. Use Integer.numberofTrailingZeros for removing them from each multiplicand, compute the product and finally shift it left. This way the numbers you deal with get smaller and all operations get faster.

Regrouping the operands is the second trick. For four about equally big numbers, computing

(a * b) * (c * d)

instead of

((a * b) * c) *d

gives you a nice speedup. You can regroup your operands to make use of this.


File stream functions Is this good or not?  Input arguments for OsFile_Open must be in UTF8 format.

#include <stdio.h>

#ifdef WIN32
    #include <Windows.h>
#endif

// Types declaration, originally they are located in header file
//
typedef int                 Bool_T;
typedef signed long long    Int64_T;

#define true    1
#define false   0

#define IN
#define OUT

Bool_T OsFile_Open( IN const char * name, IN const char * mode, OUT FILE ** file )
{
    FILE * handle;

#ifdef WIN32

    wchar_t unicodeMode[MAX_PATH];
    wchar_t unicodeName[MAX_PATH];

    int unicodeNameLen;
    int unicodeModeLen;

    unicodeNameLen = MultiByteToWideChar( CP_UTF8, 0, name, -1, unicodeName, 0 );

    if( unicodeNameLen != 0 )
    {
        if( MultiByteToWideChar( CP_UTF8, 0, name, -1, unicodeName, unicodeNameLen ) != 0 )
        {
            unicodeModeLen = MultiByteToWideChar( CP_UTF8, 0, mode, -1, unicodeMode, 0 );

            if( unicodeModeLen != 0 )
            {
                if( MultiByteToWideChar( CP_UTF8, 0, mode, -1, unicodeMode, unicodeModeLen ) != 0 )
                {
                    handle = _wfopen( unicodeName, unicodeMode );

                    if( handle != NULL )
                    {
                        *file = handle;
                        return true;

                    }else{

                        return false;
                    }

                }else{

                    return false;
                }

            }else{ // if( unicodeModeLen != 0 )

                return false;
            }

        }else{ // if( MultiByteToWideChar( CP_UTF8, 0, name, -1, unicodeName, unicodeNameLen ) != 0 )

            return false;
        }

    }else{ // if( unicodeNameLen != 0 )

        return false;
    }

#else

    handle = fopen64( name, mode );

    if( handle != NULL )
    {
        *file = handle;
        return true;

    }else{

        return false;
    }

#endif

}

Bool_T OsFile_Close( IN FILE * file )
{
    return ( fclose( file ) == 0 ) ? true : false;
}

Bool_T OsFile_Seek( IN FILE * file, IN Int64_T offset, IN int origin )
{
    int result;

#ifdef WIN32
    result = _fseeki64( file, offset, origin );
#else
    result =  fseeko64( file, offset, origin );
#endif

    return ( result == 0 ) ? true : false;
}

Bool_T OsFile_GetPos( IN FILE * file, OUT Int64_T * curPos )
{
#ifdef WIN32
    *curPos = _ftelli64( file );
#else
    *curPos =  ftello64( file );
#endif

    return ( *curPos != -1 ) ? true : false;
}

size_t OsFile_Read( IN FILE * file, IN int numOfBytes, OUT unsigned char * buffer )
{
    return fread( buffer, sizeof( unsigned char ), numOfBytes, file );
}

int OsFile_Eof( IN FILE * file )
{
    return feof( file );
}

I'd re-structure (the Win32 part of) the open function to something like this:

#ifdef WIN32

    wchar_t unicodeMode[MAX_PATH];
    wchar_t unicodeName[MAX_PATH];

    if (MultiByteToWideChar( CP_UTF8, 0, name, -1, unicodeName, MAX_PATH) &&
        MultiByteToWideChar( CP_UTF8, 0, mode, -1, unicodeMode, MAX_PATH) &&
        (handle = _wfopen( unicodeName, unicodeMode)) != NULL)
    {
        *file = handle;
        return true;
    }
    return false;

#else

You don't need to call MultiByteToWideChar twice for each conversion -- the first call not only returns the length, but does the conversion as well. As it stands, your code has potential buffer overruns as well -- it used the first call to MultiByteToWideChar to measure the length that would be needed for the result, but never checked that this was less than or equal to the buffer space you provided.

It can be legitimate to do the two consecutive calls, especially if (for example) you want to ensure you can handle any possible input by using the first call the measure the necessary length, then allocating the necessary space dynamically, and then doing the second call using the dynamically allocated space.

Several places, you have things like:

return ( fclose( file ) == 0 ) ? true : false;

These should be written as:

return fclose(file) == 0;

or just:

return !fclose(file);

There's no need to select and return a Boolean literal -- the Boolean values yielded by == and ! will work nicely as-is.

Edit: You also have a couple of things like:

#ifdef WIN32
    *curPos = _ftelli64( file );
#else
    *curPos =  ftello64( file );
#endif

spread throughout the code. Where you're just dealing with different function names like this, I think I'd have one block up-front to deal with the name differences, and then use a single name through the rest of the code:

#ifdef WIN32
    #define ftello64(x) _ftelli64(x)
    #define fseeko64(x) _fseeki64(x)
#endif

/* ... */

Bool_T OsFile_Seek( IN FILE * file, IN Int64_T offset, IN int origin )
{
    return !fseeko64(file, offset, origin);
}

You might want to read #ifdef considered harmful for more about what to do and what to avoid.


In-place reversal of a singly linked list As suggested in The 2nd Monitor, I'd like a review of this in-place reversal of a singly linked-list:

#include <iostream>

struct node {
    int data;
    node *next;
};

node *reverse(node *list) {
    node *prev = NULL;
    node *next;

    while (list) {
        next = list->next;
        list->next = prev;
        prev = list;
        list = next;
    }
    return prev;
}

void show_list(node *list) {
    while (list != NULL) {
        std::cout << list->data << ", ";
        list = list->next;
    }
}

int main() {
    node *list = NULL;

    for (int i=0; i<10; i++) {
        node *n = new node;
        n->next = list;
        n->data = i;
        list = n;
    }

    std::cout << "As built: ";
    show_list(list);

    list = reverse(list);

    std::cout << "Reversed: ";
    show_list(list);
    return 0;
}

You don't use delete after allocating nodes with new, resulting in a memory leak.  As a general rule, delete should be used in the same way new was used.

In this case, have an identical for loop and use delete on each node:

for (int i=0; i<10; i++) {
    delete n;
}

With these two loops, you might as well have a constant to hold the number of nodes to use, so that you can make sure the same number is used.
You don't need to have return 0 at the end of main().  Reaching the end implies successful completion, and the compiler will insert this return for you.


dynamic programming solution for a string ending with 0, 1 or 2 A string that contains only 0s, 1s, and 2s is called a ternary string. Find a total ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

I have defined a recurrence relation as dp[i][j] means the total number os trings ending with j where i is the length of the string and j is either 0, 1 or 2.

dp[i][0] = dp[i-1][1] + dp[i-1][2]

dp[i][1] = dp[i-1][0] + dp[i-1][2]

dp[i][2] = dp[i-1][1] + dp[i-1][2] + dp[i-1][1]

from collections import defaultdict

def end_with_x(n):
  dp = defaultdict(int)
  dp[1] = defaultdict(int)
  dp[1][0] = 1
  dp[1][1] = 1
  dp[1][2] = 1
  for i in range(2, n+1):
    dp[i] = defaultdict(int)
    dp[i][0] = dp[i-1][1] + dp[i-1][2]
    dp[i][1] = dp[i-1][0] + dp[i-1][2]
    dp[i][2] = dp[i-1][2] + dp[i-1][0] + dp[i-1][1]
  return dp[n][0] + dp[n][1] + dp[n][2]
print(end_with_x(2))

Your recurrence is very fine, so I've just minor adjustments to propose:

In this kind of bottom-up DP, you only need to access the previous row. No need to keep the whole history.
There is a copy/paste bug in dp[i][0] computation.
No need to use a dict, each level (row) is fully filled out.

I would thus write:

def total_with_length(n):
    if n <= 0:
        return 0
    n0, n1, n2 = 1, 1, 1
    for _ in range(n-1):
        n0, n1, n2 = n1+n2, n0+n2, n0+n1+n2
    return n0 + n1 + n2


Vending machine implementation How would one optimize this code?

import java.util.*;
public class VendingMachineAssignement {

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        double item1 = 1.25;
        double item2 = .75;
        double item3 = .90;
        double item4 = .75;
        double item5 = 1.50;
        double item6 = .75;

        System.out.print("Enter an item number: ");
        int item = keyboard.nextInt();

        System.out.print("Enter the amount paid: ");
        double paid = keyboard.nextDouble();

        if (item == 2 || item == 4 || item == 6)
        {
            if (paid >= item2)
            {
                System.out.println("Thank you for buying item " + item + ", your change is $" + (paid-item2) + ". Please come again!");
            }
            if (paid < item2)
            {
                System.out.println("Please insert another " + "$" + (item2-paid));
            }
        }

        else if (item == 1)
        {
            if (paid >= item1)
            {
                System.out.println("Thank you for buying item " + item + ", your change is $" + (paid-item1) + ". Please come again!");
            }
            if (paid < item1)
            {
                System.out.println("Please insert another " + "$" + (item1-paid));
            }
        }
        else if (item == 3)
        {
            if (paid >= item3)
            {
                System.out.println("Thank you for buying item " + item + ", your change is $" + (paid-item3) + ". Please come again!");
            }
            if (paid < item3)
            {
                System.out.println("Please insert another " + "$" + (item3-paid));
            }
        }
        else if (item == 5)
        {
            if (paid >= item5)
            {
                System.out.println("Thank you for buying item " + item + ", your change is $" + (paid-item5) + ". Please come again!");
            }
            if (paid < item5)
            {
                System.out.println("Please insert another " + "$" + (item5-paid));
            }
        }

    }

}

And also, for example, if I enter 5 for item and .10 for paid, then why does it say Please insert another $1.4 instead of 1.40? Even though 1.50 - 1.4 and 1.50 - 1.40 would be the same, how come it does not display 1.40?

Things I would fix:

All of your condition test statements do exactly the same thing.

else if (item == 1)
{
    if (paid >= item1)
    {
        System.out.println("Thank you for buying item " + item + ", your change is $" + (paid-item1) + ". Please come again!");
    }
    if (paid < item1)
    {
        System.out.println("Please insert another " + "$" + (item1-paid));
    }
}
else if (item == 3)
{
    if (paid >= item3)
    {
        System.out.println("Thank you for buying item " + item + ", your change is $" + (paid-item3) + ". Please come again!");
    }
    if (paid < item3)
    {
        System.out.println("Please insert another " + "$" + (item3-paid));
    }
}
...

You can use arrays to help solve this issue.

double[] prices = new double[] { 1.25, 0.75, 0.9, 0.75, 1.5, 0.75 };

Then you can access those specific values with prices[item - 1].  Remember that arrays start with the index 0, so without subtracting 1 you will end up with an off-by-one error.  The comparison is now simplified.

if (paid >= (prices[item - 1]))
{
    System.out.println("Thank you for buying item " + item + ", your change is " + (paid - prices[item - 1]) + ". Please come again!");
}

You ask the user to insert more money, but never actually allow him to.

if (paid < item2)
{
    System.out.println("Please insert another " + "$" + (item2-paid));
}

This can easily be solved with a while loop and another pair of input request statements.

You never close your Scanner when you are finished with it (a memory issue).

keyboard.close();

You never check if the item you buy is actually within the bounds of the array length.

if (!(item <= prices.length))
{
    System.out.println("Sorry, we don't have that item in stock.");
    keyboard.close();
    return;
}

When working with money, it is hard to work with doubles, they are too imprecise.  An example of this is that 0.42 - .21 is likely something like 0.209999999999999997 rather than 0.21 exactly.

We are going to use the NumberFormat class to make sure that the our double values will stay accurate.

NumberFormat.getCurrencyInstance().format(number)

Recommendations that are optional:

Don't do this:

import java.util.*;

It could be problematic for the compiler to import a bunch of packages at once. If two packages provide the same type, both are imported, and the type is used in the class, a compile-time error occurs. This is described in JLS 6.5.5.1:

  Otherwise, if a type of that name is declared by more than one type-import-on-demand declaration of the compilation unit, then the name is ambiguous as a type name; a compile-time error occurs.

In addition, it also saves a bit of memory.  And your IDE (if you use one), should have the ability to do this automatically.

You might note that this:

public static void main(String... args)

Is a bit different than your usual:

public static void main(String[] args)

They both do the same thing, but one uses variable arity parameters.

The Scanner.nextInt() method does not read the last newline character of your input, and thus a newline could be consumed if you call Scanner.nextLine.  I prefer to use Scanner.nextLine since you can input any valid String, and then just parse it into the type you need (as long as it's a valid type to parse it to).

Final code:

import java.text.NumberFormat;
import java.util.Scanner;

public class Test
{
    public static void main(String... args)
    {
        Scanner keyboard = new Scanner(System.in);
        double[] prices = new double[] { 1.25, 0.75, 0.9, 0.75, 1.5, 0.75 };
        int item = 0;

        System.out.print("Enter an item number: ");
        item = Integer.parseInt(keyboard.nextLine());
        if (!(item <= prices.length))
        {
            System.out.println("Sorry, we don't have that item in stock.");
            keyboard.close();
            return;
        }

        System.out.print("Enter the amount paid: ");
        double paid = Double.parseDouble(keyboard.nextLine());

        while (paid < (prices[item - 1]))
        {
            System.out.print("You need " + NumberFormat.getCurrencyInstance().format(Math.abs((paid - prices[item - 1]))) + " more for item " + item);
            paid += Double.parseDouble(keyboard.nextLine());
        }
        System.out.println("Thank you for buying item " + item + ", your change is " + NumberFormat.getCurrencyInstance().format((paid - prices[item - 1])) + ". Please come again!");

        keyboard.close();
    }
}


Central Delannoy numbers I am solving this problem on SPOJ Upper Right King (Hard):

  There is a king in the lower left corner of the \$ n \times n \$ chess board. The king can move one step right, one step up or one step up-right. How many ways are there for him to reach the upper right corner of the board? Give the answer modulo 1000003.

The numbers to be output are the central Delannoy numbers.

I've written a solution in Python with a time complexity of \$ O(n(\log m)^2) \$.  But it's showing "time limit exceeded".  Can anyone help me out with this?

import math
MAX = 10000002
MOD = 1000003

# Extended euclidean algorithm for modular inverse

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return 0
    else:
        return x % m

t = raw_input()
t = long(t)

fact = []

for i in range(0,MAX):
    fact.append(0)
fact[0]=1
fact[1]=1
for i in range(2,MAX):
    fact[i] = (i%MOD * fact[i-1]%MOD)%MOD

while t:
    n = raw_input()
    n = long(n)
    n = n-1
    Sum = 1
    prod = ((n+1)%MOD * (n)%MOD)%MOD
    increment = n+1
    decrement = n
    Sum = (Sum%MOD + prod%MOD)%MOD

    for k in range(0,n-1):
        temp_prod = (prod%MOD * (increment+1)%MOD * (decrement-1)%MOD)%MOD
        prod = temp_prod
        fct = fact[k+2]
        fat2 = (fct%MOD * fct%MOD)%MOD
     #   print fat2,modinv(fat2,MOD)
        result = (temp_prod%MOD * modinv(fat2,MOD))%MOD
        Sum = (Sum%MOD + result%MOD)%MOD
        increment = increment + 1
        decrement = decrement - 1

    print "%ld" %(Sum)
    t = t-1

How can I reduce the complexity of this problem in order to have it accepted?

Flatten your method body

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

can be re-written as:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

because returning halts the function.

Use in-line 'ternary' to reduce verbosity

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return 0
    else:
        return x % m

should become

def modinv(a, m):
    g, x, y = egcd(a, m)
    return 0 if g != 1 else x % m

Say something meaningful when asking for input

t = raw_input()

The user sees nothing, only an hanging interpreter.

Use a main function

Python code runs faster in functions
You can use an if name ... block to avoid execution when the module is imported.

Convert directly (minor)

Do not waste lines:

n = raw_input()
n = long(n)

should become

n = long(raw_input()) # <- also add a meaningful prompt

Follow naming conventions (minor)

You follow the naming conventions pretty well, just one imprecision:

Sum = 1

should be:

sum = 1

Use proper spacing (minor)

For example this line:

prod = ((n+1)%MOD * (n)%MOD)%MOD

is hard to read because all the symbols are squashed together.

Modularize more (important)

You defined two functions, that is very good, but you could do more to reduce the 35 lines of top level imperative code that is too much.

Usually each function (including main) should be no more than 10-15 lines of code.

Use doctests to for automatic testing

In Math code, automatically testing your functions each time you run the programme can be invaluable, just use something like:

import doctest

def egcd(a, b):
    """
    Meaningful description here...

    >>> egcd(4132, 434)
    (2, -48, 457)
    """

    if a == 0:
        return (b, 0, 1)

    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

doctest.testmod()

and the code will be tested automatically.

Tell why

I can see many calculations in your code, but why? Following which algorithm, please write this inside the docstrings of your functions.


"Compress" the entry set of Integers in a Map to values incrementing by 1 What I'm trying to achieve is the following:

Given a Map, where the values may contain duplicates, I want to change the values so that they are incrementing by 1, starting from 1.

Example:

{"One"=1, "Three"=3, "Another three"=3, "Seven"=7} should result in:
{"One"=1, "Three"=2, "Another three"=2, "Seven"=3}

I do this now by:

"Inverting" the map into a com.google.common.collect.Multimap
Build a sorted list of unique values from the original map values (via Java 8 Stream API)
Iterate with ++-increments from 0 until size of unique values, and in the process get(i) the unique value from the sorted list, then map the original string to the value of the incrementing integer into a new map.

I'd be happy to learn if there is a better a.k.a. more elegant or more performant way of doing this!

The relevant JUnit test looks as follows, and passes.

import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;

...

@Test
public void mappingTest() {
    Map<String, Integer> map = new HashMap<>();
    map.put("One", 1);
    map.put("Two", 2);
    map.put("AnotherTwo", 2);
    map.put("Three", 3);
    map.put("Seven", 7);
    map.put("AnotherSeven", 7);
    map.put("Ten", 10);

    // Build the "inverted" Multimap
    Multimap<Integer, String> mMap = HashMultimap.create();
    for (Entry<String, Integer> entry : map.entrySet()) {
        mMap.put(entry.getValue(), entry.getKey());
    }

    // Get a list of unique integers compiled from the original map's values
    List<Integer> uniques = map.values().stream().distinct().sorted().collect(Collectors.toList());

    // Map the original keys to the new incrementing values
    Map<String, Integer> fMap = new HashMap<>();
    for (int i = 0; i < uniques.size(); i++) {
        for (String string : mMap.get(uniques.get(i))) {
            fMap.put(string, i+1);
        }
    }

    // Asserts
    assertEquals(fMap.get("One"), Integer.valueOf(1));
    assertEquals(fMap.get("Two"), Integer.valueOf(2));
    assertEquals(fMap.get("AnotherTwo"), Integer.valueOf(2));
    assertEquals(fMap.get("Three"), Integer.valueOf(3));
    assertEquals(fMap.get("Seven"), Integer.valueOf(4));
    assertEquals(fMap.get("AnotherSeven"), Integer.valueOf(4));
    assertEquals(fMap.get("Ten"), Integer.valueOf(5));
}

When you are collecting the unique integer values to a sorted list from the values of the original Map<String, Integer>, you are doing work that has already been done, namely the elimination of duplicates by calling distinct() on the stream. You have already filtered out the duplicates when you populated the Multimap<Integer, String>, so instead of collecting the values of the Map<String, Integer>, you could instead collect the keys of the Multimap<Integer, String>.

Also, you are creating a HashMultimap, which stores its values in HashSets (so it's like a HashMap<Integer, HashSet<String>>). This creates unneeded overhead, because the HashSet<String>s containing the values of the multimap eliminate duplicates. But in this case, the multimap can never contain duplicate values in the first place, since its values are obtained from the key set of the original Map<String, Integer>. It would therefore suffice to configure the multimap to store its values in ArrayLists instead of HashSets. By the way, the documentation says that the create methods of the individual Multimap implementations will be deprecated in the future, and that MultimapBuilder should be used instead.

Apart from that, you can omit the List<Integer> entirely by configuring the multimap to behave like a TreeMap instead of a HashMap. This might also save a bit of performance, because you have two functionalities implemented in one data structure, as opposed to using a Multimap for associating each integer with one or more Strings, and an additional List for sorting the integers. Of course, a TreeMap does not index its keys, so you would have to maintain a counter yourself when you iterate over the keys of the multimap.

Finally, the overall structure of your code sample is strange. Unit tests are meant to test whether some code works correctly. But your method mappingTest() not only performs the tests, it also contains the code to be tested. Of course, there's nothing wrong with placing assertions in code to test it. But what you wrote is not a unit test, because it doesn't test any defined unit (for example a method). It just executes some code and then uses assertions to check whether the code did what you thought it would do.

Instead, I suggest that you first write a method that accepts a Map<K, Integer> (or any Map<K, V> where <V extends Comparable<? super V>>) as a parameter and returns a "compressed" version of this map:

public static <K, V extends Comparable<? super V>> Map<K, Integer> compress(Map<K, V> map) {
    //...
}

Then, you write a separate method that tests that method by constructing a map like you did in mappingTest(), passing this map to compress(Map) and then inspecting the returned Map. This would be a unit test, because you are testing the functionality of a unit, i.e. the method compress(Map).


PDO connection / prep and execute in their own functions I'm currently changing some legacy code over to PDO.  The below code works, but not 100%.  I would like to know if it's best practice or if anything can be done better.

//Database Array
$config['db'] = array(
    'host' => 'localhost',
    'username' => 'root',
    'password' => 'root',
    'dbname' => 'local');

//New PDO
$db = new PDO('mysql:host=' . $config['db']['host'] . ';dbname=' . $config['db']['dbname'], $config['db']['username'], $config['db']['password']);
$db->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
//Check connection is ok
try {
    $db->exec("SET CHARACTER SET utf8");
}
catch (PDOException $ex) {
    print "Error!: " . $ex->getMessage() . "
";
    die();
}

//Update users function
function update($db, $fn, $ln, $email, $offers, $vlue, $response)
{
    $stmt = $db->prepare("insert into local (fName_765, lName_765, email_765, signup_765) values (:fname, :lname, :email, :signup, NOW())");
    $stmt->bindParam(':fname', $fn, PDO::PARAM_STR);
    $stmt->bindParam(':lname', $ln, PDO::PARAM_STR);
    $stmt->bindParam(':email', $email, PDO::PARAM_STR);
    $stmt->bindParam(':signup', $offers, PDO::PARAM_STR);
    try {
        $stmt->execute();
        print $db->lastInsertId(); //show ID
        return true;
    }
    catch (PDOException $e) {
        print "Error!: " . $e->getMessage() . "
"; // show error
        return false;
    }
}

//Test Attributes
$fn = 'test';
$ln = 'test';
$email = 'tesst@test,com';
$offers = '1';

if (!update($db, $fn, $ln, $email, $offers, $vlue, $response)) {
    echo "no update there is a slight problem";
} else {
    echo "it seemed to work";
}

Midified version:

$functionError = array();

//Database Array
$config['db'] = array(
    'host' => 'localhost',
    'username' => 'root',
    'password' => 'root',
    'dbname' => 'root');

//Check connection is ok
try {
    $db = new PDO('mysql:host=' . $config['db']['host'] . ';dbname=' . $config['db']['dbname'], $config['db']['username'], $config['db']['password']);
    $db->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
}
catch (PDOException $e) {
    $functionError[] = "
{DB} - Error!: " . $e->getMessage() . "
";
    errorhandler ($functionError);
    die ();
}

//Error Handler
function errorhandler ($functionError) {
    print_r ($functionError);
    echo "Sorry we are experiencing issues we are aware of the problem";

}

//Update users function
function update($db, $fn, $ln, $email, $offers, $vlue, $response)
{
    $stmt = $db->prepare("insert into kkt (fName_765, lName_765, email_765, signup_765, kkt_resp_765, kkt_respSate_765, stamp_765) values (:fname, :lname, :email, :signup, :kkt_rsp, :kkt_respState, NOW())");

    $parameters = array(
        ':fname' => $fn,
        ':lname' => $ln,
        ':email' => $email,
        ':signup' => $offers,
        ':kkt_rsp' => $vlue,
        ':kkt_respState' => $response);

    try {
        $stmt->execute($parameters);
        return true;
    }
    catch (PDOException $ex) {
        $functionError[] = "
{INSERT} - Error!: " . $ex->getMessage() . "
";
        errorhandler ($functionError);
        return false;
    }
}

//Test Attributes
$fn = 'test';
$ln = 'test';
$email = 'tesst@test,com';
$offers = '1';
$vlue = 'value';
$response = 'resp';

if (update($db, $fn, $ln, $email, $offers, $vlue, $response)) {
    echo "it seemed to work";
    print $db->lastInsertId();
    header('Location: thank-you.php');
    exit;
}

Here are a few things I noticed.

If you are going to catch a possible exception when you connect to your MySQL DB you want to include the PDO instantiation in the try block.

try {
    $db = new PDO('mysql:host=' . $config['db']['host'] . ';dbname=' . $config['db'}['dbname'], $config['db']['username'], $config['db']['password']);
    $db->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
    $db->exec("SET CHARACTER SET utf8");
}  catch(PDOException $e) {
    print "Error!: " . $ex->getMessage() . "<br/>";
    die();
}

The arguments $vlue and $response don't do anything in your update function. You probably want to get rid of those.
You can use a quicker syntax for binding parameters by defining an array that holds the values and passing it to PDOStatement::execute(). This has the benefit of less function calls. Doing it this way will default all parameter value datatypes to be PDO::PARAM_STR, which matches what you are doing currently.

$parameters = array(
    ':fname'  => $fn,
    ':lname'  => $ln,
    ':email'  => $email,
    ':signup' => $offers
);
$stmt->execute($parameters);

The point of exceptions is to be able to handle, on your own terms, exceptional events. If a PDO exception occurs in your update function, more than likely it won't/shouldn't know how to handle it. It makes more sense for the code that calls update to take care of that situation. So I would suggest moving the try/catch block to wherever the update function is called.

   try {
       update($db, $fn, $ln, $email, $offers, $vlue, $response)
   } catch (PDOException $e) {
       echo "no update there is a slight problem " . $e->getMessage();
   }


Read table row with multiple options I developing an algorithm to read a row from a table (specifically, I'm reading from an Excel file).

I have three conditions about when to terminate the Read operation:

When an empty cell is found (recognized by an ElementNotFoundException
When a cell with errors is found (which corresponds to a null value)
Both the two previous conditions

This is the current algorithm:

public IEnumerable<string> ReadRow(string spreadsheet, int column, int row, ReadOptions readOptions = ReadOptions.ReadUntilEmpty)
{
    var values = new List<string>();

    if (readOptions.HasFlag(ReadOptions.ReadUntilEmpty) && readOptions.HasFlag(ReadOptions.ReadUntilCellError))
    {
        try
        {
            for (var currentColumn = column; ; currentColumn++)
            {
                var value = ReadCell(spreadsheet, currentColumn, row);

                // Cell has errors, so we exit from the loop
                if (value == null) break;

                values.Add(value);
            }
        }
        catch (ElementNotFoundException)
        {
            // The row is terminated
            // so we exit the loop withouth loggin any error
        }
    }
    else if (readOptions.HasFlag(ReadOptions.ReadUntilCellError))
    {
        for (var currentColumn = column; ; currentColumn++)
        {
            try
            {
                var value = ReadCell(spreadsheet, currentColumn, row);

                // Cell has errors, so we exit from the loop
                if (value == null) break;

                values.Add(value);
            }
            catch (ElementNotFoundException)
            {
                // The ReadOptions is not setted on ReadUntilEmpty
                // so we just ignore empty cells
            }
        }
    }
    else if (readOptions.HasFlag(ReadOptions.ReadUntilEmpty))
    {
        try
        {
            for (var currentColumn = column; ; currentColumn++)
            {
                var value = ReadCell(spreadsheet, currentColumn, row);

                values.Add(value);
            }
        }
        catch (ElementNotFoundException)
        {
            // The row is terminated
            // so we exit the loop withouth loggin any error
        }
    }

    return values;
}

And just for reference, the enumeration used:

[Flags]
public enum ReadOptions
{
    ReadUntilEmpty,
    ReadUntilCellError
}

How can I improve it?

Also, any idea on how I can reuse this code to read a column instead a row?

You always terminate the reading of the row if the element isn't found. This means you can have just one Try-Catch block that wraps your If statement.
Instead of checking for && in your first statement, use || (or instead of and). You don't really care if ReadUntilEmpty is set at that point; only ReadUntilCellError matters. This eliminates an entire block from the If statement.
You could go one step further and only check the flag just before, or with, the null value check.

public IEnumerable<string> ReadRow(string spreadsheet, int column, int row, ReadOptions readOptions = ReadOptions.ReadUntilEmpty)
{
    var values = new List<string>();

    try
    {
        for (var currentColumn = column; ; currentColumn++)
        {
            var value = ReadCell(spreadsheet, currentColumn, row);

            if readOptions.HasFlag(ReadOptions.ReadUntilCellError))
            {
                // Cell has errors, so we exit from the loop
                if (value == null) break;
            }

            values.Add(value);
        }
    }
    catch (ElementNotFoundException)
    {
        // The row is terminated
        // so we exit the loop withouth loggin any
    }

    return values;
}

Ultimately I realized there's never actually a need to check the ReadUntilEmpty flag, so you could probably just drop the Enum and change ReadUntilError to a Boolean with a default value of false.

Abstracting this to work on columns instead of rows is easy. The logic doesn't change at all. You just call it with the row number passed into the column argument and the column number passed into the row argument. So, really, naming the hard part and I'm drawing a blank on any actually useful names, but for the sake of giving an example...

public IEnumerable<string> ReadRow(string spreadsheet, int iteratorIndex, int secondaryIndex, ReadOptions readOptions = ReadOptions.ReadUntilEmpty)
{
    var values = new List<string>();

    try
    {
        for (var index = iteratorIndex; ; index++)
        {
            var value = ReadCell(spreadsheet, index, secondaryIndex);

            if readOptions.HasFlag(ReadOptions.ReadUntilCellError))
            {
                // Cell has errors, so we exit from the loop
                if (value == null) break;
            }

            values.Add(value);
        }
    }
    catch (ElementNotFoundException)
    {
        // The row is terminated
        // so we exit the loop withouth loggin any
    }

    return values;
}

One final note: I'm not entirely comfortable with the fact that the catch block doesn't actually contain any code. It feels a bit hacky.


Genetic algorithm in Python that plots its evolution After programming in Haskell for a while, I've gotten attached to a functional style.  This is clearly evident in the code for my genetic algorithm.

Could you provide me with some hints as to how I can make this code more pythonic?  By that, I mean provide some method of organisation rather than throwing a bunch of functions around.  Any other recommendations are also welcome.

import copy
import matplotlib.pyplot as pyplot
import random

def create_member(genes):
    return (sum(genes), genes)

def shuffle(pool):
    pool_shuffled = copy.deepcopy(pool)
    random.shuffle(pool_shuffled)
    return pool_shuffled

def calculate_pool_fitness(pool):
    return sum([member[0] for member in pool])

def calculate_member_fitness(member):
    return sum(member[1])

def recalculate_fitneses(pool):
    return [(calculate_member_fitness(member), member[1]) for member in pool]

def select_members_roulette(pool, count):
    selection = []
    while len(selection) < count:
        member = select_member_roulette(pool)
        selection.append(copy.deepcopy(pool[member]))
    return selection

def select_member_roulette(pool):
    drop = random.randint(0, calculate_pool_fitness(pool))
    total_fitness = 0
    for member in range(0, len(pool)):
        total_fitness += pool[member][0]
        if total_fitness >= drop:
            return member

def mutate_gene(gene, rate=1):
    return 1 - gene if random.random() <= rate else gene

def mutate_genes(genes, rate=1):
    return [mutate_gene(gene, rate) for gene in genes]

def mutate_member(member, rate=1):
    return member[0], mutate_genes(member[1], rate)

def mutate_pool(pool, rate=1):
    return [mutate_member(member, rate) for member in pool]

def create_random_gene():
    return random.choice([0, 1])

def create_random_genes(size):
    return [create_random_gene() for _ in range(size)]

def crossover_genes(mother, father, rate=1):
    if random.random() <= rate:
        split = random.randint(1, len(mother))
        daughter = mother[:split] + father[split:]
        son = father[:split] + mother[split:]
    else:
        daughter = copy.deepcopy(mother)
        son = copy.deepcopy(father)
    return daughter, son

def crossover_members(mother, father, rate=1):
    daughter_genes, son_genes = crossover_genes(mother[1], father[1])
    return [(mother[0], daughter_genes), (father[0], son_genes)]

def crossover_pool(pool, rate=1):
    children = []

    # select every two elements for crossover
    for mother, father in zip(pool[::2], pool[1::2]):
        children.extend(crossover_members(mother, father, rate))

    return children

def generate_pool(size, gene_size):
    pool = []
    for member in range(0, size):
        genes = create_random_genes(gene_size)
        pool.append(create_member(genes))
    return pool

def evolve(pool, rate_crossover=0.9, rate_mutation=0.01):
    successors = copy.deepcopy(pool)

    # perform roulette selection whilst keeping best member
    member_alpha = copy.deepcopy(max(successors, key=lambda member: member[0]))
    successors = select_members_roulette(pool, len(pool) - 1)
    successors.append(member_alpha)

    successors = shuffle(successors)
    successors = crossover_pool(successors, rate_crossover)
    successors = mutate_pool(successors, rate_mutation)
    successors = recalculate_fitneses(successors)
    return successors

def main():
    random.seed
    pyplot.figure(figsize=(14, 8), dpi=400)
    axgraph=pyplot.subplot(111)
    pool_size = 50
    gene_size = 50
    generations = 100
    pool = generate_pool(pool_size, gene_size)
    for generation in range(0, generations):
        pool = evolve(pool)
        axgraph.scatter(generation, sum([member[0] for member in pool]))
    pyplot.grid(True)
    pyplot.axis([0, generations, 0, pool_size * gene_size])
    pyplot.savefig('genetic_algorithms.png')

main()

if __name__ == '__main__':
    main()

random.seed is a bug: add parentheses to actually call the function.
Use collections.namedtuple so you can write member.fitness instead of the less readable member[0]
copy.deepcopy should not be necessary in a functional approach
Keeping the genes in a tuple instead of a list would make the member tuple fully immutable, in line with the functional approach. This eliminates the need to deep-copy objects as you can safely copy just references.

After these changes create_member becomes like this:

import collections
Member = collections.namedtuple("Member", "fitness genes")

def create_member(genes):
    genes = tuple(genes)
    return Member(sum(genes), genes)

In some places you create members without calling create_member. Be sure to change them, for example:

def mutate_member(member, rate=1):
    return create_member(mutate_genes(member.genes, rate))

With immutable members there is no need to recalculate fitnesses. You can delete such functions.


Mutex locker class in C++ What needs to be corrected, added, or subtracted here?

class mutexLocker
{
    private:
    /* Declaration of a Mutex variable `mutexA`. */
    pthread_mutex_t &mutexA;

    /* `mutexStatus` holds the return value of the function`pthread_mutex_lock `.
    This value has to be returned to the callee so we need to preserve it in a class
    variable. */
    int             mutexStatus;

    public:
    /* Constructor attempts to lock the desired mutex variable. */
    mutexLocker (pthread_mutex_t argMutexVariable)
    : mutexA (argMutexVariable)
    {
        /* Return value is needed in order to know whether the mutex has been
        successfully locked or not. */
        int mutexStatus = pthread_mutex_lock (&argMutexVariable);
    }

    /* Since the constructor can't return anything, we need to have a separate function
    which returns the status of the lock. */
    int getMutexLockStatus ()
    {
        return mutexStatus;
    }

    /* We may need this Mutex variable as an argument for `pthread_cond_wait()`*/
    pthread_mutex_t getLockedMutex ()
    {
        if (mutexStatus >= 0)
            return mutexA;
    }

    /* The destructor will get called automatically whereever the callee's scope ends, and
    will get the mutex unlocked. */
    ~mutexLocker ()
    {
        if (mutexStatus >= 0)
             pthread_mutex_unlock (&mutexA);
    }
};

If you are keeping a reference to an object you should pass that object to the constructor as a reference:

mutexLocker (pthread_mutex_t    argMutexVariable)
                    //     ^^^  Missing reference.

You return the state of the lock operation:

int getMutexLockStatus ()

But if the mutext failed to lock what are you going to do.
If the mutext fails to lock there is probably something fundamentally wrong so you should probably stop the current action by throwing an exception.

You can't conditionally return a value.
You must always return something from a function that expects to return value.

pthread_mutex_t getLockedMutex ()
{
    if (mutexStatus >= 0)
        return mutexA;

    // What happens if the code gets here?
    // Letting a function return without an explicit return (in a non void method)
    // is undefined behavior.
}

Also I see no point in testing the status.
If the lock failed to lock you should have exited the code much earlier than this. If the lock fails throw an exception.

Your test is also incorrect (here and the destructor)

if (mutexStatus >= 0)

If the mutex did lock then it returned 0 and thus the mutexStatus is zero.


Producing a nested data set from flat data I have this example data :

 var objects = [
                {
                    title: "Parent Area",
                    code: "P",
                    areas: "B,C",
                    child: [],
                    selected: 0,
                    remove: 0
                },
                {
                    title: "Child area one",
                    code: "B",
                    areas: "C",
                    child: [],
                    selected: 0,
                    remove: 0
                },
                {
                    title: "Child area two",
                    code: "C",
                    areas: undefined,
                    child: [],
                    selected: 0,
                    remove: 0
                }
            ];

I want to create this data set :

sortedSet = [
                {
                    title: "Parent Area",
                    code: "P",
                    areas: "B,C",
                    child: [
                        {
                            title: "Child area one",
                            code: "B",
                            areas: "C",
                            child: [
                                {
                                    title: "Child area two",
                                    code: "C",
                                    areas: undefined,
                                    child: [],
                                    selected: 0,
                                    remove: 0
                                }
                            ],
                            selected: 0,
                            remove: 0
                        },
                        {
                            title: "Child area two",
                            code: "C",
                            areas: undefined,
                            child: [],
                            selected: 0,
                            remove: 0
                        }

                    ],
                    selected: 0,
                    remove: 0
                }
            ];

Iv written the following code:

 /**
             * for each area get it's children
             */
            angular.forEach(objects, function (obj) {

                if (obj.areas) {

                    var subChildren = obj.areas.split(",");

                    /**
                     * assign the current child as child of the parent area
                     */
                    angular.forEach(subChildren, function (currentChild) {

                        angular.forEach(objects, function (currentObj) {

                            if (currentObj.code == currentChild) {

                                /**
                                 * mark this for removal from main array
                                 * @type {number}
                                 */
                                currentObj.remove = 1;
                                obj.child.push(currentObj);
                            }
                        })

                    })

                }

            })

            var sortedSet = [];
            /***
             * clean out main areas array
             */
            angular.forEach(objects, function (obj, index) {

                if (!obj.remove) {
                    /**
                     * copy the correct values to a secondary array
                     */
                    sortedSet.push(objects[index]);
                }
            })

My code works as required but I really wish I didn't need to do so many loops.

Any suggestion re-factors to optimise this code?

The number of nested loops can be reduced and doing so provides an opportunity to check your data for duplicate ids. This may not be necessary if you trust your source to provide good data.

var objectByCode={};

objects.forEach(function(o){
    // if( objectByCode[o.code] ) throw 'Duplicate codes';
    objectByCode[o.code]=o;
});

objects.forEach(function(o){
    if(o.areas){
        o.areas.split(",").forEach(function(c){
            if(objectByCode[c]){
                o.child.push(objectByCode[c]);
                objectByCode[c].remove=1;
            } // else { throw 'Code not found'; }
        });
    }
});

var sortedSet=objects.filter(function(o){ return !o.remove; });

Personally I would worry less about how many nested loops you have used and more about the potentially recursive data structure you are creating. This may prove difficult to work with if any of the children turn out to be their own ancestors. If for example the object with code C had area P then the resulting sortedSet would be empty. If B was a child of C then any naive attempt to list all descendants of B would result in a infinite loop.

If you are sure that your data will never contain this situation then you should be safe. If you are worried that this problem might occur a quick and dirty way to test for it is to use JSON.stringify which will throw an error when asked to produce the string equivalent of recursive objects.

try{
    JSON.stringify(sortedSet);
}catch(e){
    // how you decide to handle this is up to you
}

It might not be important to your application if this is the case, but be aware that your code may need to handle these situations.


Maximum sub-array sum My code finds the maximum subarray sum and the starting and ending index of that subarray.

int Max(int a,int b){return (a>b)?a:b;}
int Max(int a,int b,int c){return Max(Max(a,b),c);}
int MaxAcrossSubArray(int arr[],int l,int m,int r,int &Start,int &End)
{
    Start=m;//initialize start index
    int sum=arr[m];
    int sum_l=arr[m];
    for(int i=m-1;i>=l;--i)//include mid(---------|)
    {
        sum+=arr[i];
        if(sum>sum_l)
        {
            Start=i;
            sum_l=sum;
        }

    }
    End=m+1;//initialize end index
    sum=arr[m+1];
    int sum_r=arr[m+1];
    for(int i=m+2;i<=r;++i)//include mid(|-----------------)
    {
        sum+=arr[i];
        if(sum>sum_r){
            End=i;
            sum_r=sum;
        }
    }
    return sum_l+sum_r;//(-----------|---------------------)

}
int MaxSubArray(int arr[],int l,int r,int &Start,int &End)
{
    if(l==r)
    {
        Start=l;
        End=r;
        return arr[l];
    }

    else
    {
       int mid=(l+r)/2;
        int sA=-1,eA=-1,sB=-1,eB=-1,sC=-1,eC=-1;
        int a=MaxSubArray(arr,l,mid,sA,eA);
        int b=MaxSubArray(arr,mid+1,r,sB,eB);
        int c=MaxAcrossSubArray(arr,l,mid,r,sC,eC);
        int Maximum=Max(a,b,c);

        if(Maximum==a)
        {
            Start=sA;
            End=eA;
            return a;
        }

        else if(Maximum==b)
            {
                Start=sB;
                End=eB;
                return b;
            }
        else
            {
                Start=sC;
                End=eC;
                return c;
            }
    }
    }

}
int main()
{
    int arr[9]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int Start=-1;
    int End=-1;

    cout<<MaxSubArray(arr,0,8,Start,End)<<"\n";
    cout<<Start<<"\n";
    cout<<End<<"\n";
    for(int i=Start;i<=End;++i)
    {

        cout<<arr[i]<<"\t";
    }
    cout<<"\n";
    return 0;
}

Is there any way to optimize this?

Welcome to Code Review!

Algorithm

Since you specifically asked how to optimize the code, I'll put this part first.  You are using a divide-and-conquer algorithm.  This algorithm is \$\operatorname{\Theta}(n \log n)\$.  There's a better \$\Theta(n)\$ algorithm which works like this: go through the array, from index i = [0, n).  Keep track of two variables:

max_sum: maximum subarray sum so far.
max_end_sum: maximum subarray sum ending at index i.

Initially, both can be considered to be "negative infinity".  At each element, these variables can be updated in constant time with the following formulas:

new_max_sum     = max{max_sum, array[i], max_end_sum + array[i]}
new_max_end_sum = max{array[i], max_end_sum + array[i]}

Readability

Code is read more than written.  Here are some tips to improve readability:

Always put a space after a comma and around binary operators.  Instead of

int c=MaxAcrossSubArray(arr,l,mid,r,sC,eC);

Use

int c = MaxAcrossSubArray(arr, l, mid, r, sC, eC);

Always put the opening and closing braces of a function body on separate lines.  Instead of

int Max(int a,int b){return (a>b)?a:b;}

Use

int Max(int a, int b)
{
    return (a > b) ? a : b;
}

Put a space after control keywords like for or if.  This helps visually distinguish them from functions and operators (sizeof, typeid, etc.).
Be consistent with indentation.  Bad example:

if(Maximum==a)
{
    Start=sA;
    End=eA;
    return a;
}

else if(Maximum==b)
    {
        Start=sB;
        End=eB;
        return b;
    }

The standard library facilities

The function Max is already available in the standard library as std::max.  For example:

std::max(42, 420) == 420
std::max({42, 420, 4200}) == 4200

(You may noticed that you need to use braces if the number of arguments is not exactly two.)

The following loop:

for(int i=Start;i<=End;++i)
{

    cout<<arr[i]<<"\t";
}

can be replaced by a call to std::copy with std::ostream_iterator.

In C++, raw C arrays are not recommended.  You are advised to use standard library containers like std::array instead.  Indexes should be of type std::size_t or std::ptrdiff_t instead of int.

Here's how the code may look like in modern C++, with iterators and tuples: (just a rough idea, not particularly optimized)

template <
    typename ForwardIt,
    typename Value,
    typename BinaryOp = std::plus<>,
    typename Compare = std::less<>
    >
std::tuple<ForwardIt, ForwardIt, Value>
maximum_subarray(ForwardIt first, ForwardIt last, Value init,
                 BinaryOp combine = {}, Compare compare = {})
{
    auto max_sum = std::make_tuple(first, first, init);
    auto max_end_sum = std::make_tuple(first, init);

    for (; first != last; ++first) {
        auto& [it, value] = max_end_sum;
        value = combine(value, *first);
        if (compare(value, *first)) {
            it = first;
            value = *first;
        }
        if (compare(std::get<2>(max_sum), value)) {
            max_sum = {it, std::next(first), value};
        }
    }

    return max_sum;
}

template <typename ForwardIt>
auto maximum_subarray(ForwardIt first, ForwardIt last)
{
    using Value = typename std::iterator_traits<ForwardIt>::value_type;
    return maximum_subarray(first, last, Value());
}


Synchronous logging of asynchronous retrieved folder info I started learning functional programming with JavaScript and I have the basic idea of Functors, container types and etc. I was trying to experiment with arrays but I don't know how to solve the problem of a function call that iterates over a array and returns returns another array. So the first call ends up with an array with 4 elements which are nested nested arrays of promises.
const iterate = p =>
Promise.all(p
.map(f=>({localPath:f.localPath,RelativePathFromDistLibrary:f.RelativePathFromDistLibrary}))
.map(f=>getsubfolders(f.localPath)
  .map(async _f=>({
    RelativeDistLibraryUrlAfterDomain: env.spDistLibraryAbsoluteUrlArray.slice(1).join(''),
    RelativeDistFolder:`${env.spDistFolderAbsoluteUrlArray.slice(3).join('')}${f.RelativePathFromDistLibrary}${_f}`,
    ModifiedTimeInMs: (await readStat(`${f.localPath}${_f}`)).mtimeMs
  }))
))
.then(x=>Promise.all(x.flat(Infinity)))
.then(x=>x.map(z=>console.log(z.ModifiedTimeInMs)))

The first call for iterate we pass an array of four objects. The first map just transforms each object, the second one gets all subfolders for each directory.
Example:
iterate([{RelativePathFromDistLibrary: '/src', localPath: './src'}]))

Then we map over all the results (first nested map). We wrap all in a promise.all since it will return a array of promises. We flatten the resulting array and wrap in a promise all again, then we can access the props.
Any tips that can help me better understand FP or solve the issues from this code would be super helpful.

I decided to go with the solution below.
By using Tasks I don't need to put all the logic right there, I can just pass the Task anywhere and map/chain over it to add extra functionality. I can even just fork it after I have all the data and get the List inside which I can also map and more.
Also with the function "getsubfolders" from the questions I can use to get the array of the paths and just wrap it in a List as I am doing in readDir.
So what I mean is that, although the structure is different, this way is way more flexible and readable (I can still derive all the above objects from the result).
I am noew trying to convert the getsubfolders to async and functional as well, for the sake of learning.
/* eslint-disable import/extensions */
/*
taken from
https://mostly-adequate.gitbooks.io/mostly-adequate-guide/content/ch08.html#asynchronous-tasks
 */
import fs from 'fs'
import {Task, traverse,concat,compose,chain,map, prop, List, } from './shared/functional.js';

// readDir :: String -> Task Error (List String)
const readDir = path => new Task((reject, result) => {
  fs.readdir(path, (err, data) => (err ? reject(err) : result(new List(data))));
});

// readDir :: String -> Task Error (Stat)
const readStat = filename => new Task((reject, result) => {
  fs.stat(filename, (err, data) => (err ? reject(err) : result(data)));
});

const dirList = dir =>
chain(
  traverse(Task.of, compose(readStat, concat(dir))),
  readDir(dir),
);

dirList('./shared/').fork(console.error, map(compose(console.log, prop('mtimeMs'))));