Performance of RegExp vs Rune Loop I was recently talking to someone about a function I wrote to mimic (very basically) the string interpolation function String.Format() found in the C# language. They mentioned that I would have performance concerns using RegExp, and that I should try to parse the string template rune by rune. So I wrote a loop the best I could to accomplish that very task. It looks alarmingly ugly (to me) and I wanted some input on the performance considerations with the loop version. As well, maybe some better suggestions on how to accomplish this function in a more sensible/clean fashion.

Here's the two different versions of the implementation:

void main() {
  String thestring = '{0} {1} {2} {3}!';
  assert(formatStringListRegExp([thestring, 'This', 'was', 'a', 'triumph']) == 'This was a triumph!');

  assert(formatStringListloop([thestring, 'This', 'was', 'a', 'triumph']) == 'This was a triumph!');
}

String formatStringListRegExp(List<String> args)
{
  if (args == null || args.length < 2) {
    throw new ArgumentError('expected at least two paramters.');
  }
  if (args[0] is !String) {
    throw new ArgumentError('expected a string for the first paramter.');
  }
  var str = args[0];
  var inserts = args.sublist(1);
  for (var i = 0; i < inserts.length; i++) {
    str = str.replaceAll('{$i}', inserts[i].toString());
  }
  return str;
}

String formatStringListLoop(List<String> args)
{
  if (args == null || args.length < 2) {
    throw new ArgumentError('expected at least two paramters.');
  }

  if (args[0] is !String) {
    throw new ArgumentError('expected a string for the first paramter.');
  }

  var str = args[0];
  var inserts = args.sublist(1);
  StringBuffer buffer = new StringBuffer();

  for (var i = 0; i < str.length; i++) {
    if (str[i] == '{' && i < str.length + 1) {
      var value = '';
      var count = 1;
      var number;

      while(true) {
        if (i + count < str.length - 1) {
          try {
            number = int.parse(str[i + count]);
          } catch (e) {
            break;
          }
        } else {
          break;
        }

        if (number is int) {
          value += number.toString();
          count++;
        } else {
          break;
        }
      }

      if (str[i + count] == '}') {
        if (value.isNotEmpty) {
          int index = int.parse(value);
          if (index < inserts.length) {
            buffer.write(inserts[index]);
            i += count;
          } else {
            buffer.write('{');
          }
        }
      }
    } else {
      buffer.write(str[i]);
    }
  }

  return buffer.toString();
}

I don't know Dart, but I haven't had any problems with Javascript regular expression speed, so I don't see why it would be a problem with Dart.

If you format strings are long -- which is probably unlikely -- then scanning the whole string once for each substitution string is not ideal. It's also buggy. Consider the calls:

formatStringListRegExp(['{0} {1}', '{1}', 'foo'])
formatStringListRegExp(['{0} {1}', 'foo', '{0}'])

So what I'd do is this (all error checking removed for brevity):

String formatStringListRegExp(List<String> args)
{
  return args[0].replaceAllMapped(new RegExp(r'{(\d+)}'),
                                  (Match m) => args[int.parse(m[1])+1])
}


Return timeframes relevant to just-elapsed time period (financial/trading context) I am writing trading software, and have written this utility function. Its purpose is to return a list of timeframes relevant to the just-elapsed time period. "Timeframe" here means bar or candle period.

E.g if time has just struck UTC 10:30am, the returned list will contain "1m", "3m", "5m", "m15" and "30m" strings, as those are the candles or bars that have just closed.

The first minute of a new day or week will add daily/weekly/monthly timeframe strings.

Timeframes in use are 1, 3, 5, 15 and 30 mins, 1, 2, 3, 4, 6, 8 and 12 hours, 1, 2 and 3 days, as well as weekly and monthly.

Is there a more elegant, less verbose way to achieve this?

Note: the output could also be integers instead of strings, where each timeframe is expressed as its total number of minutes.

def get_timeframes(self):
    timestamp = datetime.datetime.utcnow()
    timeframes = ["1m"]

    # 3 minute bars
    for x in range(0, 20):
        val = x * 3
        if timestamp.minute == val:
            timeframes.append("3m")

    # 5 minute bars
    for x in range(0, 12):
        val = x * 5
        if timestamp.minute == val:
            timeframes.append("5m")

    # 15 minute bars
    for x in range(0, 4):
        val = x * 15
        if timestamp.minute == val:
            timeframes.append("15m")

    # 30 minute bars
    for x in range(0, 2):
        val = x * 30
        if timestamp.minute == val:
            timeframes.append("30m")

    # 1 hour bars
    if timestamp.minute == 0:
        timeframes.append("1h")

    # 2 hour bars
    if timestamp.minute == 0 & timestamp.hour % 2 == 0:
        timeframes.append("2h")

    # 3 hour bars
    if timestamp.minute == 0 & timestamp.hour % 3 == 0:
        timeframes.append("3h")

    # 4 hour bars
    if timestamp.minute == 0 & timestamp.hour % 4 == 0:
        timeframes.append("4h")

    # 6 hour bars
    if timestamp.minute == 0 & timestamp.hour % 6 == 0:
        timeframes.append("6h")

    # 8 hour bars
    if timestamp.minute == 0 & timestamp.hour % 8 == 0:
        timeframes.append("8h")

    # 12 hour bars
    if timestamp.minute == 0 & timestamp.hour % 12 == 0:
        timeframes.append("12h")

    # 1 day bars
    if timestamp.minute == 0 & timestamp.hour == 0:
        timeframes.append("1d")

    # 2 day bars
    if (
        timestamp.minute == 0 & timestamp.hour == 0 &
            timestamp.day % 2 == 0):
                timeframes.append("2d")

    # 3 day bars
    if (
        timestamp.minute == 0 & timestamp.hour == 0 &
            timestamp.day % 3 == 0):
                timeframes.append("3d")

    # weekly bars
    if (
        timestamp.minute == 0 & timestamp.hour == 0 &
            calendar.day_name[date.today().weekday()] == "Monday"):
                timeframes.append("1w")

    return timeframes

I think you should separate the computation in three different functions, one for minutes, one for hours, and one for days. And generalize each of these functions, so they can be used for other time frames if you ever decide to change them.

Minutes

You can specify an extra parameter in range(), the step: how much is added every iteration. With this the method to check a minute time frame is quite simple:

def minute_timeframe(minutes, timestamp, timeframes):
    for x in range(0, 60, minutes):
        if timestamp.minute == x:
            timeframes.append(f"{minutes}m")

Since your tags say you use Python 3, I used formatted string literals.

Hours

Be careful! You are using the & operator, which in Python is the binary and operation. Since what you want is probably the logical and (i.e. this is true and the other is true), use the and keyword (same for or and not).

By looking at your implementation of hour timeframes, it's pretty easy to generalize:

def hour_timeframe(hours, timestamp, timeframes):
    if timestamp.minute == 0 and timestamp.hour % hours == 0:
        timeframes.append(f"{hours}h")

Days

The same happens for generalizing days. I must comment though, that your original does not seem to follow the PEP 8 Style for the indentations on that part of the code. You also do not need the parenthesis surrounding the if condition.

def day_timeframe(days, timestamp, timeframes):
    if timestamp.minute == 0 and timestamp.hour == 0 and timestamp.day % days == 0:
          timeframes.append(f"{days}d")

Final result

Now that our functions are generalized, in my opinion what would be best is to store a list of the different timeframes you want to use, that way adding new ones or changing them is simple. This is the final function:

# Constants go in ALL_CAPS
MINUTE_TIMEFRAMES = [3, 5, 15, 30]
HOUR_TIMEFRAMES = [1, 2, 3, 4, 6, 8]
DAY_TIMEFRAMES = [1, 2, 3]

def get_timeframes(self):
    timestamp = datetime.datetime.utcnow()
    timeframes = ["1m"]

    for x in MINUTE_TIMEFRAMES:
        minute_timeframe(x, timestamp, timeframes)

    for x in HOUR_TIMEFRAMES:
        hour_timeframe(x, timestamp, timeframes)

    for x in DAY_TIMEFRAMES:
        day_timeframe(x, timestamp, timeframes)

    # Format it correctly and use 'and'
    if (timestamp.minute == 0 and timestamp.hour == 0 and
        calendar.day_name[date.today().weekday()] == "Monday"):
        timeframes.append("1w")


Count distinct records in a JOINed SQL query I have two tables with a 1-many relationship, Device and TestResult.

My application has a filter builder front-end that allows a user to retrieve TestResults based on whatever filters they specify. This generates queries similar to this:

SELECT d.id,
       d.serialNumber,
       d.createdAt,
       r.id,
       r.testBlockId,
       r.deviceId,
       r.type,
       r.fieldResponses,
       r.stationName,
       r.summary,
       r.createdAt
FROM Device AS d
INNER JOIN TestResult AS r ON r.deviceId = d.id
WHERE d.id IN
    (SELECT id
     FROM Device
     WHERE serialNumber BETWEEN '000000001000' AND '000000002020'
     ORDER BY serialNumber ASC
     LIMIT 570, 10)
  AND r.createdAt BETWEEN '2020-03-27T11:54:43.100Z' AND '2020-04-01 09:21:02.362768'
ORDER BY serialNumber ASC;

This query limits the number of Devices returned, which handles paging on the front-end. I'm also generating a query that counts the total number of Devices that match the filters, without the OFFSET and LIMIT values. This is used to tell the front-end how many pages of records there are.

If I simply run the above query but change the SELECT statement to SELECT COUNT(DISTINCT d.id) as totalDevices and remove the LIMIT, it's very slow. So instead I'm generating this query to find the count:

SELECT COUNT(DISTINCT d.id) AS totalDevices
FROM Device AS d
INNER JOIN TestResult AS r ON r.deviceId = d.id
WHERE serialNumber BETWEEN '000000001000' AND '000000002020'
  AND r.createdAt BETWEEN '2020-03-27T11:54:43.100Z' AND '2020-04-01 09:21:02.362768';

This query runs faster, but it still isn't fast. I'm wondering if there is a better way to retrieve a count of the distinct Device records that would be returned from this query.

This query shows the following execution time with 1,000,000 records:

Run Time: real 8.090 user 1.562500 sys 6.500000

I've modified the query to use a GROUP BY instead of a COUNT DISTINCT, which has sped up the execution time.

SELECT COUNT(*) AS totalDevices
FROM (
  SELECT d.id
  FROM Device AS d
  INNER JOIN TestResult AS r ON r.deviceId = d.id
  WHERE serialNumber BETWEEN '000000001000' AND '000000002020'
    AND r.createdAt BETWEEN '2020-03-27T11:54:43.100Z' AND '2020-04-01 09:21:02.362768'
  GROUP BY d.id
);

This query shows the following execution time with 1,000,000 records:

Run Time: real 3.433 user 0.953125 sys 2.484375

The COUNT DISTINCT query shows the following execution time:

Run Time: real 8.090 user 1.562500 sys 6.500000

So the GROUP BY query takes just under half of the time of the COUNT DISTINCT query.


Haskell functions to extract and reverse integers hiding in strings There may not be a "right" way to do it, but I'm inexperienced in functional programming. I'd like some feedback on how the code can be written in a more idiomatic way.

Here it is:

import Data.Maybe (fromJust, isJust)

sepInt n = if n >= 10
            then  ( sepInt ( n `div` 10 ) ) ++ ((n `mod` 10):[])
            else n `mod` 10 : []

getStuff (x:xs) = if isJust x || null xs
                    then fromJust x
                    else getStuff xs

base10IntTOstring num =
                 let chars = [ (1, '1'), (2, '2'), (3, '3'), (4, '4'), (5, '5'), (6, '6'), (7, '7'), (8, '8'), (9, '9'), (0, '0') ]
                     numbahs = sepInt num in
                     map getStuff ( map (\a -> (map (\(x,y) -> if a == x then Just y else Nothing ) chars ) ) numbahs )

charTOBase10Int char =
                 let chars = [ ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9), ('0', 0) ] in
                     let charslist = ( map (\(a,x) -> if char == a then Just x else Nothing) chars ) in
                         getStuff charslist

stringTOBase10Int string =
    let integers = ( map charTOBase10Int string ) in
        let multByBase i (x:xs) = if null xs
                                   then (10^i)*x
                                   else (10^i)*x + multByBase ( i-1 ) xs
        in multByBase ( (length integers)-1 ) integers

It also reverses integers.

sepInt n = if n >= 10
            then  ( sepInt ( n `div` 10 ) ) ++ ((n `mod` 10):[])
            else n `mod` 10 : []

reverseInteger string =
    let integers = sepInt string in
        let multByBase i (x:xs) = if null xs
                                   then (10^i)*x
                                   else (10^i)*x + multByBase ( i-1 ) xs
        in multByBase ( (length integers) - 1 ) integers

Let's take one function at a time, until we're all done.

sepInt

sepInt n = if n >= 10
            then  ( sepInt ( n `div` 10 ) ) ++ ((n `mod` 10):[])
            else n `mod` 10 : []

First things first: you'll definitely want to learn a bit about precedence! Normally I'm in favor of adding some unnecessary parentheses if it helps disambiguate a strange situation or if the operators involved aren't often mixed, but too many of them can get in the way of readability. Also, take advantage of that sweet syntactic sugar for lists that the language provides! So iteration one of this function is

sepInt n = if n >= 10
            then sepInt (n `div` 10) ++ [n `mod` 10]
            else [n `mod` 10]

Now, as we all know, building up a linked list by repeatedly appending to the end is a bit inefficient. Probably for such small lists as you'll be using in test cases here it won't matter, but it's a good idea to get in the habit of paying attention to some of the easiest stuff, so let's try to improve this a bit. We have a choice here: either we can keep the interface of this function as-is, that is, always output a list in the right order, or we can choose to change the interface, and change all the call-sites of this function. I think for this case we can keep the interface. The idea we'll take is to build up the list backwards, then reverse it at the very end. The name go is traditional for local workers.

sepInt = reverse . go where
    go n = if n >= 10
            then [n `mod` 10] ++ go (n `div` 10)
            else [n `mod` 10]

There's something a bit funny about this base case to me. It seems like it's not the most basic one you could choose. If we let the "loop" run one more time...

sepInt = reverse . go where
    go n = if n > 0
            then [n `mod` 10] ++ go (n `div` 10)
            else []

There's a few things I find more satisfying about this: our base-case input is 0, a common base for Integers; our base-case output is [], a common base for []s; and there's no duplicated code in the two branches of the if. Finally, I think I'd choose to replace the if-then-else with a pattern match, noting however that this function has a slightly different behavior for negative numbers. Since we were never really doing the right thing for negative numbers, this doesn't bother me too much.

sepInt = reverse . go where
    go 0 = []
    go n = [n `mod` 10] ++ go (n `div` 10)

If we're feeling fancy, we can choose to use divMod instead of two separate calls to div and mod; and we can unroll the definition of (++); but I think neither of these is terribly important. Nevertheless, they're idiomatic, so:

sepInt = reverse . go where
    go 0 = []
    go n = let (d, m) = n `divMod` 10 in m : go d

Okay, let's check our work. We already know that the final thing works differently for negative numbers, so let's only check non-negative ones.

*Main Test.QuickCheck> quickCheck (\(NonNegative n) -> sepInt n == sepInt' n)
*** Failed! Falsifiable (after 2 tests):
NonNegative {getNonNegative = 0}

Whoa, whoops! Can you figure out which refactoring above was the culprit? =)

Now we have to decide whether we like the old behavior better or the new one. I think in this particular case we should like the old behavior better, since the goal is to show a number, and we'd like 0 to show up as "0" rather than as "". It's a bit ugly, but we can special-case it. Since we like our future selves, we'll leave ourselves a note about this, too.

-- special case for a human-readable 0
sepInt 0 = [0]
sepInt n = reverse . go $ n where
    go 0 = []
    go n = let (d, m) = n `divMod` 10 in m : go d

Now the test passes:

*Main Test.QuickCheck> quickCheck (\(NonNegative n) -> sepInt n == sepInt' n)
+++ OK, passed 100 tests.

getStuff

getStuff (x:xs) = if isJust x || null xs
                    then fromJust x
                    else getStuff xs

This name sure leaves something to be desired! And it leaves another important thing to be desired, too: there's lots of inputs where it just crashes. Nasty! It turns out that you never call it on inputs of that form later, but totality is another good habit that you should get yourself into. It's just another tool in the mature programmer's defensive programming toolbelt. In our case, we'll want to handle cases like [], or [Nothing], or [Nothing, Nothing], etc. where there's no good answer to return. What should we return if that happens?

One simple and quite common choice is to change our type from

getStuff :: [Maybe a] -> a

to

getStuff :: [Maybe a] -> Maybe a

but I think that's a bit short-sighted. Ignoring for the moment the inputs we know we're going to call this thing on, we've observed already that there's times when there's no good answer to return, and there's times when there is a good answer to return, so Maybe a seems like a good start, but there's also times when there are two good answers -- or more! So let's use a type that reflects this scenario instead:

getStuff :: [Maybe a] -> [a]

It's not too hard to fix up the code. First we'll just fix the type errors:

getStuff (x:xs) = if isJust x || null xs
                   then [fromJust x]
                   else getStuff xs

This isn't obviously better, since it still fails in all the same situations it used to fail, and it never returns multiple answers. So we should differentiate the two cases that lead us to the then branch:

getStuff (x:xs) = if isJust x
                   then fromJust x : if null xs
                         then []
                         else getStuff xs
                   else getStuff xs

Now, we have this if null xs branch primarily because getStuff still isn't total (it can't handle an empty input list). Instead of protecting ourselves from calling getStuff in this case, we should just let getStuff deal with empty lists correctly. So:

getStuff [] = []
getStuff (x:xs) = if isJust x
                   then fromJust x : getStuff xs
                   else getStuff xs

Actually, using isJust and fromJust is also a code smell, for the same reason as the rest of the changes so far: fromJust is partial. Instead of protecting ourselves from calling fromJust on inputs it can't handle, we should write our code in a way that avoids partial functions. Here's how:

getStuff [] = []
getStuff (Just x  : xs) = x : getStuff xs
getStuff (Nothing : xs) =     getStuff xs

(I've added a little creative whitespace to show parallels between the branches.) The only thing I'd change now is to pick a better name. For example, catMaybes might be an okay name for this. I'll mention one more thing, which is that this can also be implemented quite beautifully as a list comprehension:

catMaybes xs = [x | Just x <- xs]

By the way, this function is available from Data.Maybe.

base10IntTOstring

base10IntTOstring num =
                 let chars = [ (1, '1'), (2, '2'), (3, '3'), (4, '4'), (5, '5'), (6, '6'), (7, '7'), (8, '8'), (9, '9'), (0, '0') ]
                     numbahs = sepInt num in
                     map getStuff ( map (\a -> (map (\(x,y) -> if a == x then Just y else Nothing ) chars ) ) numbahs )

There are better ways to construct that lookup table! For example, I might choose

chars = zip [0..9] ['0'..'9']

(If you haven't seen zip before, I encourage you to try to code it up yourself! Then check the Report and compare answers.) Additionally, we're going to have to change things up a little, since we've changed how getStuff works and base10IntTOstring calls getStuff. Before, we had getStuff :: [Maybe a] -> a and hence map getStuff :: [[Maybe a]] -> [a]. Now, we have catMaybes :: [Maybe a] -> [a] and hence map catMaybes :: [[Maybe a]] -> [[a]]. Since we expect each of the lists in the output of that to be singleton lists, we can smash them all together with concat:

base10IntTOstring num =
                 let chars = zip [0..9] ['0'..'9']
                     numbahs = sepInt num in
                     concat (map catMaybes ( map (\a -> (map (\(x,y) -> if a == x then Just y else Nothing ) chars ) ) numbahs ))

Actually, this whole process at the very end is quite roundabout! If you squint, it looks like what we're really trying to implement here is a little function

lookupList :: Eq k => [(k, v)] -> k -> [v]

which we can use to index into our lookup table with the digits of our integer. So let's try to write this directly! Taking a cue from the final implementation of catMaybes above, we can write

lookupList table k = [v | (k', v) <- table, k == k']

Now our implementation can look like this:

base10IntTOstring num =
                 let chars = zip [0..9] ['0'..'9']
                     numbahs = sepInt num in
                     concat (map (lookupList chars) numbahs)

In fact, there's even a function concatMap that squashes those two things together. Veteran Haskellers will prefer to spell this function in its infix, polymorphic form as (>>=)

base10IntTOstring num =
                 let chars = zip [0..9] ['0'..'9']
                     numbahs = sepInt num in
                     numbahs >>= lookupList chars

though this spelling is optional. In fact, everything is short enough now that I would even feel comfortable inlining the definitions:

base10IntTOstring num = sepInt num >>= lookupList (zip [0..9] ['0'..'9'])

My only complaint now is the name, for two reasons. The first is that string isn't capitalized, which is inconsistent with the naming of the remainder of the file. The other one is more of a philosophical one: our input is an integer, not a base-ten integer. If anything, the base-ten-ness is being imposed on the output. So:

intTOBase10String num = sepInt num >>= lookupList (zip [0..9] ['0'..'9'])

Let's test it:

*Main Test.QuickCheck> quickCheck (\n -> base10IntTOstring n == intTOBase10String n)
+++ OK, passed 100 tests.

(By the way, a variant of lookupList that I have always felt has the wrong type, lookup, is available from Prelude.)

Finally, I would be remiss without pointing out that there are several good functions that already exist for doing conversions like this:

*Main Test.QuickCheck> let checkPosBase10 f = quickCheck (\(NonNegative n) -> f n == intTOBase10String n)
*Main Test.QuickCheck> checkPosBase10 show
+++ OK, passed 100 tests.
*Main Test.QuickCheck Numeric Data.Char> checkPosBase10 (\n -> showIntAtBase 10 intToDigit n "")
+++ OK, passed 100 tests.

The difference here is that showIntAtBase can be used for any base, and show is specific to base 10.

charTOBase10Int

charTOBase10Int char =
                 let chars = [ ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9), ('0', 0) ] in
                     let charslist = ( map (\(a,x) -> if char == a then Just x else Nothing) chars ) in
                         getStuff charslist

Actually, most of the changes we made to base10IntTOstring can be done here, as well. In the interest of totality, we'll change the type, too; it will return a [Char] (which we happen to know will be a singleton list, if anything) instead of a Char.

base10CharTOInt char = lookupList (zip ['0'..'9'] [0..9]) char

It's common in cases like this where the trailing arguments to the function you're defining are also trailing arguments to a function in the definition to omit the arguments entirely. The technical term for this is eta reduction, I think. Whether you choose to do this yourself is primarily a stylistic choice.

base10CharTOInt = lookupList (zip ['0'..'9'] [0..9])

The test for this one is a bit complicated; since the old implementation is partial, we have to restrict ourselves to those inputs that work.

*Main Test.QuickCheck> quickCheck (\n -> n >= '0' && n <= '9' ==> [charTOBase10Int n] == base10CharTOInt n)
*** Gave up! Passed only 67 tests.

The report here says that it passed the test, but that QuickCheck didn't run as many tests as it wanted to because most of the random inputs it generated weren't in the desired range. (In fact, perhaps it's questionable to use QuickCheck at all for this, since there's only ten inputs of interest anyway!)

By the way, this function (a partial version! boooo) exists also in Data.Char:

*Main Test.QuickCheck Data.Char> quickCheck (\n -> n >= '0' && n <= '9' ==> charTOBase10Int n == digitToInt n)
*** Gave up! Passed only 54 tests.

stringTOBase10Int

stringTOBase10Int string =
    let integers = ( map charTOBase10Int string ) in
        let multByBase i (x:xs) = if null xs
                                   then (10^i)*x
                                   else (10^i)*x + multByBase ( i-1 ) xs
        in multByBase ( (length integers)-1 ) integers

We first need to fix up some typing issues, since we've changed the interface to base10CharTOInt and this is a caller. As before, we can do that just by putting in a concat; as before, we'll spell the combination of concat and map as (>>=).

stringTOBase10Int string =
    let integers = string >>= base10CharTOInt in
        let multByBase i (x:xs) = if null xs
                                   then (10^i)*x
                                   else (10^i)*x + multByBase ( i-1 ) xs
        in multByBase ( (length integers)-1 ) integers

As with sepInt waaaay back at the beginning, I find the choice of base case a bit odd. Let's try the trick from before of letting the "loop" run one more iteration (and this time hopefully the refactoring isn't wrong!).

stringTOBase10Int string =
    let integers = string >>= base10CharTOInt in
        let multByBase i [] = 0
            multByBase i (x:xs) = (10^i)*x + multByBase ( i-1 ) xs
        in multByBase ( (length integers)-1 ) integers

Also, let's eliminate unnecessary parentheses.

stringTOBase10Int string =
    let integers = string >>= base10CharTOInt in
        let multByBase i [] = 0
            multByBase i (x:xs) = 10^i*x + multByBase (i-1) xs
        in multByBase (length integers-1) integers

Now, I wonder whether recomputing the power of ten each time is really the right thing to do. One thing we could do is to use 10^(length integers - 1) and divide by 10 in each recursion. But division is slow, so let's take another plan: instead of computing the length of the list explicitly, let's do it implicitly by having multByBase also compute the appropriate power of ten.

stringTOBase10Int string =
    let integers = string >>= base10CharTOInt in
        let multByBase [] = (1, 0)
            multByBase (x:xs) = let (pow, n) = multByBase xs in (pow*10, pow*x+n)
        in snd (multByBase integers)

This now has the magical special form of recursion that can be turned into a foldr. Let's do so! See if you can spot where each piece of code from the above ends up in the below.

stringTOBase10Int string =
    let integers = string >>= base10CharTOInt in
    snd (foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0) integers)

Personally, I often prefer where to let, and the foldr is complicated enough that I feel like it should be named, so I'd write it as follows. But this is an aesthetic choice that you may or may not agree with.

stringTOBase10Int string = snd (go integers) where
    integers = string >>= base10CharTOInt
    go = foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0)

And finally, fix up the name:

base10StringTOInt string = snd (go integers) where
    integers = string >>= base10CharTOInt
    go = foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0)

As usual, the tests. Since the old function was pretty partial, we'll arrange to have inputs it knows how to handle, though our new one tries to give an answer even when you feed it garbage.

*Main Test.QuickCheck> quickCheck (\(NonNegative n) -> base10StringTOInt (show n) == stringTOBase10Int (show n))
+++ OK, passed 100 tests.

By the way, there are functions for this available, too; take a look at reads from Prelude (base-10 specific) and readInt from Numeric (pick your favorite base). I won't try to write tests here, because the types of these functions are more informative (and more correct in many ways).

Final result

Barring the reuse of already-written functions, here's the final versions of all the functions.

sepInt 0 = [0]
sepInt n = reverse . go $ n where
    go 0 = []
    go n = let (d, m) = n `divMod` 10 in m : go d

lookupList table k = [v | (k', v) <- table, k == k']
intTOBase10String num = sepInt num >>= lookupList (zip [0..9] ['0'..'9'])

base10CharTOInt = lookupList (zip ['0'..'9'] [0..9])
base10StringTOInt string = snd (go integers) where
    integers = string >>= base10CharTOInt
    go = foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0)

Keep at it; I look forward to many more questions from you!


iOS SDK object to represent a place I am building an iOS SDK to be consumed by apps. I am building an object that represents a physical place. The interface looks like so:

@interface RDPlace : NSObject

@property (nonatomic, strong, readonly) NSString *city;

@property (nonatomic, strong, readonly) NSString *country;

@property (nonatomic, strong, readonly) NSString *address;

@property (nonatomic, strong, readonly) NSString *zip;

@end

This is all working fine, but now I am attempting to make this work outside of the US. I found out that some places (Hong Kong was the one that prompted this discovery) don't have a zip code. I'm wondering what the best value to put in this SDK is. I believe I have 3 options:

RDPlaces with no zip have the property set to nil
RDPlaces with no zip have the property set to NSNull
RDPlaces with no zip have the property set to @"" (empty string)

What is the most friendly for consumers of this object, and how would one annotate this for swift?

You're trying to solve a solved problem.

Just use CLPlacemark out of Core Location.  It has already solved all the problems you've brought up in your question: how to handle international addresses, what all the necessary fields are, how to handle missing fields, and how to interop with Swift.

Worse case scenario, if CLPlacemark isn't quite what you need, you can either subclass it or model your place object closely around this object.


How can I simplify the following code that calculates standard deviation Before I get started I have spent much time searching for the answer. It seems the most referenced way is here, http://www.developer.com/print.php/3794146. I am not quite understanding how to optimize. See below.

public void CalculateStdDev()
{
    arrayItemCount = 0; // integer
    average = 0; // double
    double itemsSum = 0;
    double[] values = new double[DS.Tables[0].Rows.Count];
    double[] deviations = new double[DS.Tables[0].Rows.Count];
    double[] squareDeviations = new double[DS.Tables[0].Rows.Count];
    double squareDeviationsSum = 0;
    double squareDeviationsAverage = 0;
    stdDeviation = 0; // double

    for (int i = 0; i < DS.Tables[0].Rows.Count; i++)
    {
        if (DS.Tables[0].Rows[i].ItemArray.GetValue(1).ToString() != "")
        {
            values[arrayItemCount] = Convert.ToDouble(DS.Tables[0].Rows[i].ItemArray.GetValue(1));
            itemsSum += Convert.ToDouble(DS.Tables[0].Rows[i].ItemArray.GetValue(1));
            arrayItemCount += 1;
        }
    }
    average = itemsSum / arrayItemCount;
    for (int i = 0; i < arrayItemCount; i++)
    {
        deviations[i] = Math.Abs(values[i] - average);
        squareDeviations[i] = deviations[i] * deviations[i];
        squareDeviationsSum += squareDeviations[i];
    }
    squareDeviationsAverage = squareDeviationsSum / Convert.ToDouble(arrayItemCount - 1);
    stdDeviation = Math.Round(Convert.ToDouble(Math.Sqrt(squareDeviationsAverage)), 3);
}

If the method calculate standard desviation, it should return the value, not assign a global variable or instance variable.

Regards,


Chaining three promises in Angular.JS I have demonstrated promise chaining where promise's p1,p2,p3 has to be resolved synchronously.

The code below is using angular.js 1, and here P3 is resolved then P2 and then P1.

<script type="text/javaScript">
            angular.module("myApp",[]);
            angular.module("myApp").controller("myCtrl",myCtrl);
            angular.module("myApp").factory("demoService",demoService);

            demoService.$inject = ["$q","$timeout"];
            myCtrl.$inject = ["$scope","demoService"];

            function myCtrl($scope,demoService){
                var vm = this;
                vm.init = init;

                vm.myList = [];

                function init(){
                    var p1 = demoService.get1000();
                    var p3 = demoService.get3000();
                    var p2 = demoService.get2000();

                    p3.then(function(obj){
                        vm.myList.push(obj.name);
                        console.log(obj.name);
                        return p2;
                    }).then(function(obj){
                        vm.myList.push(obj.name);
                        console.log(obj.name);
                        return p1;
                    }).then(function(obj){
                        vm.myList.push(obj.name);
                        console.log(obj.name);
                    });
                } // end of init
            } // end of myCtrl

            function demoService($q,$timeout){
                var obj = {};
                obj.get1000 = get1000;
                obj.get2000 = get2000;
                obj.get3000 = get3000;

                return obj;

                function get1000(){
                    var deferred = $q.defer();
                    var INTERVAL = 1000;
                    $timeout(function() {
                        deferred.resolve({ "name" : INTERVAL });
                    }, INTERVAL);
                    return deferred.promise;
                }

                function get2000(){
                    var deferred = $q.defer();
                    var INTERVAL = 2000;
                    $timeout(function() {
                        deferred.resolve({ "name" : INTERVAL });
                    }, INTERVAL);
                    return deferred.promise;
                }

                function get3000(){
                    var deferred = $q.defer();
                    var INTERVAL = 3000;
                    $timeout(function() {
                        deferred.resolve({ "name" : INTERVAL });
                    }, INTERVAL);
                    return deferred.promise;
                }

            } // end of demoService
</script>

So, my question is, Is there any better way of doing the above operation ? Also please review my code.

First of all, unrelated to your query, you can just inline the dependencies and the body of your factory and controller. It's bulky, but less visual noise. Also allows you to write them in separate files easily.

angular.module("myApp").controller("myCtrl",['$scope', 'demoService'], function($scope, demoService){
  // body
}])

// A more concise version. You'll need ng-annotate if you minify this
angular.module('myApp').controller('myCtrl', function($scope, demoService){
  // body
})

Also, semi-colons are optional in JS. Suggesting your remove them, they're just visual noise. Also convert double-quotes to single-quotes. They both mean the same thing, but the latter is is less visually annoying.

As for your query, first issue with your code is it's not doing what you think it's doing. The moment you call get1000, get2000, and get3000, your timers are already running. The only thing synchronous that's happening in that chain is when they get pushed into the array. In this case, your code can easily just use Promise.all().

function init(){
  var p1 = demoService.get1000()
  var p2 = demoService.get2000()
  var p3 = demoService.get3000()

  Promise.all([p3, p2, p1]).then(results => {
    vm.myList.push(...results.map(obj => obj.name))
  })
}

If you really want to make them synchronous (i.e. call get3000 then push, call get2000 then push, call get1000 then push), you will have to do the following:

function init(){
  demoService.get3000().then(obj => {
    vm.myList.push(obj.name)

    // Only call get2000 if get3000 resolves.
    return demoService.get2000()
  }).then(obj => {
    vm.myList.push(obj.name)

    // Only call get1000 if get2000 resolves.
    return demoService.get1000()
  }).then(obj => {
    vm.myList.push(obj.name)

    // get1000 completed
  })
}

If you're stuck with an environment that does not support async/await, the above syntax (which you're already doing) is pretty much all you've got. You can use arrow functions to make it less noisy. If you can do async/await, then it could be rewritten like so:

async function init(){
  const p1 = await demoService.get1000()
  vm.myList.push(p1)
  const p3 = await demoService.get3000()
  vm.myList.push(p2)
  const p2 = await demoService.get2000()
  vm.myList.push(p3)
}


Sock merchant from hackerrank - idiomatic typescript? Sock Merchant

  John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

  For example, there are \$ n = 7\$ socks with colors \$ar = [1,2,1,2,1,3,2]\$. There is one pair of color \$1\$ and one of color \$2\$. There are three odd socks left, one of each color. The number of pairs is \$2\$.

  Function Description

  Complete the sockMerchant function in the editor below. It must return an integer representing the number of matching pairs of socks that are available.

  sockMerchant has the following parameter(s):

  n: the number of socks in the pile
  ar: the colors of each sock

  Input Format

  The first line contains an integer \$n\$, the number of socks represented in \$ar\$.
  The second line contains \$n\$ space-separated integers describing the colors \$ar[i]\$ of the socks in the pile.

I just started learning typescript, and I don't know if this is good style:

import * as fs from 'fs';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputStringTemp = '';
let inputString: string[] = [];
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputStringTemp += inputStdin;
});

process.stdin.on('end', () => {
    inputString = inputStringTemp.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function sockMerchant(n: number, ar: number[]): number {
    // https://stackoverflow.com/questions/21070401/how-does-the-hash-variable-syntax-work-in-typescript/21071089#21071089
    // https://www.typescriptlang.org/docs/handbook/interfaces.html#indexable-types
    // https://stackoverflow.com/questions/44337856/check-if-specific-object-is-empty-in-typescript/44338054
    interface NumberMap {
        [index: number]: number;
    }

    // https://stackoverflow.com/questions/45571161/typescript-typing-map-object-and-instantiate-with-empty-object/45571346#45571346
    // https://stackoverflow.com/questions/29043279/how-to-use-string-indexed-interface-of-typescript/29043535#29043535
    let obj: NumberMap = {} as NumberMap;
    for (let key of ar) {
        // https://stackoverflow.com/questions/39590858/how-to-increment-a-value-in-a-javascript-object/39591127#39591127
        typeof obj[key] === 'undefined' ? obj[key] = 1 : obj[key]++;
    }
    let count = 0;
    // https://stackoverflow.com/questions/37699320/iterating-over-typescript-map/50232058#50232058
    for (const [key, value] of Object.entries(obj)) {
        // https://stackoverflow.com/questions/4228356/integer-division-with-remainder-in-javascript/4228376#4228376
        count += Math.floor(value / 2);
    }
    return count;
}

function main() {
    // https://stackoverflow.com/questions/45194964/how-to-assign-string-undefined-to-string-in-typescript/47553970#47553970
    // https://stackoverflow.com/questions/23314806/setting-default-value-for-typescript-object-passed-as-argument/44937766#44937766
    // const ws = fs.createWriteStream(process.env.OUTPUT_PATH!);
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH || "output.txt");

    const n = parseInt(readLine(), 10);
    const ar = readLine().split(' ').map(arTemp => parseInt(arTemp, 10));
    let result = sockMerchant(n, ar);
    ws.write(result + "\n");

    ws.end();
}

https://www.hackerrank.com/challenges/sock-merchant/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Let's make it pure function:

function readLine() {
    return inputString[currentLine++];
}

IMHO both for loop should be transform to reduce, or at least the second one where you use only addition, it would be still simple and readable as a reduce().

Personally, I don't like those shorts like ws - sounds like websocket, ar and means nothing, obj and count are too generic.

result could be declared as const, as well obj and count.

And lastly, too much links as comments, why do you assume reviewer don't know TS, JS... or google? :)
Not to mention, the links could be dead soon.


Simulate Pascal's/Delphi's Insert in C In Pascal/Delphi, there's a built-in function for inserting a substring into a main string.

procedure Insert ( const InsertStr : string; var TargetStr : string; Position : Integer ) ;

I'm used to this function, so I'd like to simulate it in C.

Because the main string will generally become longer after an insertion, the way to proceed is:

To have some extra space in a char array allocated in stack, or
To use dynamically allocated strings.

I've chosen the second option. At the moment my code looks like this. It uses the standard C string.h library.

#include "stdlib.h"
#include "string.h"

void myStrInsert(const char *pWord, char **pStr, int pos)
{
    // Only dynamically allocated strings are allowed.
    if (pos < 0)
        return;
    int lenStr = strlen(*pStr);
    if (pos > lenStr)
        pos = lenStr;
    int lenWord = strlen(pWord);

    char *pResult = (char *)malloc(lenStr + lenWord + 1);
    if (pResult != NULL) {
        memcpy(pResult, *pStr, pos);
        memcpy(pResult + pos, pWord, lenWord);
        memcpy(pResult + pos + lenWord, *pStr + pos, lenStr - pos + 1);
        free(*pStr);
        *pStr = pResult;
    }
}

Can this function be simplified/optimized?

There are a number of things that I see that may help you improve your code.

Use the appropriate form for #includes

The code has the appropriate #include files but they should be in angle brackets and not quotes.  When you write #include "math.h" it is different from #include <math.h>.  For standard headers, you should use the <> form.  If you're not sure about the difference, see this question for more detail.

Don't use Hungarian notation

Prefixing every variable with an abbreviation of its type (e.g. pStr) is usually called "Hungarian notation" and it was once popular.  Even then it was a bad idea.  Don't clutter up your source code with that; instead, concentrate on defining meaningful names for each variable and choose types appropriately.

Return an error code

The myStrInsert function can detect errors, but gives no indication to the calling program that anything went wrong.  A more robust design would return an error code.

Avoid memory fragmentation

The code allocates new space even if the original space would have had room.  This is somewhat wasteful and can lead to memory fragmentation.  Better would be to use realloc.

Do more error checking

It's good that pos is checked for a negative number, but it might be good to also check to assure that the pointers are not NULL before dereferencing them.

A possible rewrite

Using all of these suggestions, one might rewrite to something like this:

int myStrInsert(const char *inserted, char **target, int pos)
{
    if (inserted == NULL || target == NULL || *target == NULL || pos < 0) {
        return -2;
    }
    size_t wordlen = strlen(inserted);
    size_t origlen = strlen(*target);
    char *orig = realloc(*target, origlen+wordlen+1);
    if (orig == NULL) {
        return -1;
    }
    if (pos > origlen) {
        pos = origlen;
    } else {
        memmove(&orig[pos+wordlen], &orig[pos], origlen-pos);
    }
    memmove(&orig[pos], inserted, wordlen);
    orig[origlen+wordlen] = '\0';
    *target = orig;
    return 0;
}

Limitations

One thing I think I should mention is that, unlike the original code, this code is not robust if we attempt to splice a string into itself.  That is, if we try to insert "fox" into the string "the fox" by passing in the first parameter as a pointer into the same string we're modifying, it's not necessarily well-behaved.  It's something that isn't hard to fix, but I wanted to make sure that readers were aware of the limitation before attempting to use this code.


Accessing View from ViewModel Having a view (grid control) that provides some functionallity via methods (primary SerializeView / DeserializeView) that should be called from the view model which is bound to the view.

One point to consinder is, that the view model may not be bound to the view during the deserialization process. Therefore, the serialization state of the view must be buffered in the view model and applied when the view model will be bound to the view.

The following solution can handle such use cases in general:

Implementation

IViewAwareViewModel interface that must be implemented by the view model:

public interface IViewAwareViewModel<TView> where TView : class
{
    ViewConnection<TView> ViewConnection { get; }
}

ViewConection that encapsulates the view and provides "delayed access".

public class ViewConnection<TView> where TView : class
{
    private TaskCompletionSource<TView> taskCompletionSource = new TaskCompletionSource<TView>();

    public Task<TView> View => this.taskCompletionSource.Task;

    public bool IsConnected => this.taskCompletionSource.Task.IsCompleted;

    public void Release()
    {
        this.taskCompletionSource = new TaskCompletionSource<TView>();
    }

    public void RunOnView(Action<TView> action)
    {
        this.View.ContinueWith(task => action(task.Result));
    }

    internal void SetView(TView view)
    {
        if (this.IsConnected)
        {
            throw new InvalidOperationException("Unable to connect to a view twice.");
        }
        this.taskCompletionSource.SetResult(view);
    }
}

ViewConnector that provides a helper method for connecting the view with the view model.

public static class ViewConnector<TView> where TView : class
{
    public static void Register(FrameworkElement target)
    {
        if (target == null)
        {
            throw new ArgumentNullException(nameof(target));
        }

        if (!typeof(TView).IsInstanceOfType(target))
        {
            throw new InvalidOperationException($"Object of type '{target.GetType()}' is not compatible to type '{typeof(TView)}'.");
        }

        target.DataContextChanged += TargetDataContextChanged;
    }

    private static void TargetDataContextChanged(object sender, DependencyPropertyChangedEventArgs e)
    {
        var oldViewModel = e.OldValue as IViewAwareViewModel<TView>;
        var newViewModel = e.NewValue as IViewAwareViewModel<TView>;

        if (oldViewModel != null)
        {
            oldViewModel.ViewConnection?.Release();
        }

        if (newViewModel != null)
        {
            newViewModel.ViewConnection.SetView(sender as TView);
        }
    }
}

Usage

View Registration

var dataGrid = new MyDataGrid(); // implements: IDataGridAbstractionForViewModel
ViewConnector<IDataGridAbstractionForViewModel>.Register(dataGrid);

ViewModel Implementaion

public class DataGridViewModel : ViewModelBase, IViewAwareViewModel<IDataGridAbstractionForViewModel>
{
    public ViewConnection<IDataGridAbstractionForViewModel> ViewConnection { get; } = new ViewConnection<IDataGridAbstractionForViewModel>();

    protected override string SerializeState()
    {
        if (this.ViewConnector.IsConnected)
        {
            var view = this.ViewConnection.View.Result;
            return view.SaveLayout();
        }

        return string.Empty;
    }

    protected override void DeserializeState(string state)
    {
        base.DeserializeState(state);

        if (string.IsNullOrEmpty(state))
        {
            return;
        }

        this.ViewConnection.RunOnView(view => view.RestoreLayout(state));

    }

    protected override void OnRemoved()
    {
        base.OnRemoved();

        this.ViewConnection.Release();
    }
}

Questions

Are there other cleaner solutions / approaches?
Do you see any risk of memory leaks?
General feedback? :)

ViewConnection class looks cool, I think that's a clever use of tasks. But frankly I don't see why you can't have a

public string State { get {...} set {...}}

property on both view and viewmodel and solve your problem with two-way databinding. You can set this property on your viewmodel when you load your layout. If view is there - fine, it will be notified that the property has changed and you can handle this change on the view side (i.e. update datagrid with new state). If the view is not there - also fine, it will fetch the property from viewmodel as soon as you set its DataContext. In similar fashion you can save datagrid state on view side, set View.State and handle the new state in ViewModel.State property (i.e save it to file). You do not show your view class, but I don't see any problems with this approach off the bat, and I think that's how those things should be done normally.


Simple Async Google Maps initializer with AngularJS Here is a simple reusable AngularJS factory I came up with to initialize Google Maps Asynchronously, which somehow does not seem to be supported by major libraries (see below):

Following Google's guidelines I am using global callback function (which seems to be unavoidable harm), that resolves a dummy promise, which is the only API returned.

Then maps can be loaded anywhere by simply calling

Initializer.mapsInitialized.
    .then(function(){
        map = new google.maps.Map(element, options);
    });

Below is the code. Any critics, potential flaws, drawbacks, violation of best practices is welcome!

// Google async initializer needs global function, so we use $window
angular.module('GoogleMapsInitializer')
    .factory('Initializer', function($window, $q){

        // maps loader deferred object
        var mapsDefer = $q.defer();

        // Google's url for async maps initialization accepting callback function
        var asyncUrl = 'https://maps.googleapis.com/maps/api/js?callback=';

        // async loader
        var asyncLoad = function(asyncUrl, callbackName) {
          var script = document.createElement('script');
          //script.type = 'text/javascript';
          script.src = asyncUrl + callbackName;
          document.body.appendChild(script);
        };

        // callback function - resolving promise after maps successfully loaded
        $window.googleMapsInitialized = function () {
            mapsDefer.resolve();
        };

        // loading google maps
        asyncLoad(asyncUrl, 'googleMapsInitialized');

        return {

            // usage: Initializer.mapsInitialized.then(callback)
            mapsInitialized : mapsDefer.promise
        };
    })

Most major libraries built for Google Maps seem to use the standard script tag

<script src='//maps.googleapis.com/maps/api/js'></script>

which is, however, blocking, may result in delays, and makes the page unsuitable for offline testing.

On another note, library such as script.js async loader, does not seem to work with this particular script.

I like it,

you could clean up the commented out code and possibly replace

    $window.googleMapsInitialized = function () {
        mapsDefer.resolve();
    };

with

    $window.googleMapsInitialized = mapsDefer.resolve;

Personally, I would re-arrange the code a tiny bit, keep the URL completely on top,
keep asyncLoad and the call closer together. Keep the declaration of mapsDefer and the resolving function closer.

// Google async initializer needs global function, so we use $window
angular.module('GoogleMapsInitializer')
.factory('Initializer', function($window, $q){

    //Google's url for async maps initialization accepting callback function
    var asyncUrl = 'https://maps.googleapis.com/maps/api/js?callback=',
        mapsDefer = $q.defer();

    //Callback function - resolving promise after maps successfully loaded
    $window.googleMapsInitialized = mapsDefer.resolve; // removed ()

    //Async loader
    var asyncLoad = function(asyncUrl, callbackName) {
      var script = document.createElement('script');
      //script.type = 'text/javascript';
      script.src = asyncUrl + callbackName;
      document.body.appendChild(script);
    };
    //Start loading google maps
    asyncLoad(asyncUrl, 'googleMapsInitialized');

    //Usage: Initializer.mapsInitialized.then(callback)
    return {
        mapsInitialized : mapsDefer.promise
    };
})


Segmented Sieve of Eratosthenes I implemented this for the Prime Generator problem on SPOJ, but I am only getting 0.01s run-time, and would like to be able to match the run-times of the top submissions, which are all 0.00s.
What are some suggestions for optimizations that I can do to improve the efficiency of this algorithm?

Input: The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output: For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef vector<bool> VB;
typedef vector<int> VI;

VI sieve(int n) {

  VB is_prime(n, true);
  int sqrtn = sqrt(n);

  for (int i = 2; i <= sqrtn; ++i) {
    if (is_prime[i]) {
      for (int j = i * 2; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }

  VI primes;
  int prime_size = is_prime.size();

  for (int i = 2; i <= prime_size; ++i) {
    if (is_prime[i]) {
      primes.push_back(i);
    }
  }
  return primes;
}

void segmented_sieve(int &m, int &n) {

  int range = n - m;
  VI primes = sieve(range + 1);
  VB is_prime(range + 1, true);

  for (const auto &prime : primes) {
    for (int i = (m / prime) * prime; i <= n; i += prime) {
      if (i >= m && i != prime) {
        is_prime[i - m] = false;
      }
    }
  }

  for (int k = 0; k <= range; ++k) {
    if (is_prime[k]) {
      printf("%d\n", m + k);
    }
  }
}

int main() {

  int t;
  scanf("%d", &t);

  while (t--) {
    int m, n;
    scanf("%d%d", &m, &n);
    if (m == 1) m++;
    segmented_sieve(m, n);
  }
  return 0;
}

Algorithm is incorrect

The algorithm you are using is incorrect because you do not find the proper range of primes to use for your segmented sieve.  You are currently finding and using primes in the range 0..(n-m+1).  But you actually need to be finding primes in the range 0..sqrt(n).  Here is a trivial test case that demonstrates the problem:

1
9 9

For this test case, you find primes in the range 0..1, which finds no primes, which leads to an incorrect result where you print 9 as a prime.  The correct range of primes should be 0..3 for this test case.

Find primes once

Given the maximum \$n\$ of \$10^9\$, you should do a single sieve to find all the primes under \$\sqrt {10^9}\$.  There should be 3401 primes under 31623.  In fact, you could even hardcode this list of primes into your program to avoid performing the sieve at runtime.  It should only take 14KB to hardcode that list (7KB if you store them as short).

Optimizing the segmented sieve

Let's take a look at your main loop:

  for (const auto &prime : primes) {
    for (int i = (m / prime) * prime; i <= n; i += prime) {
      if (i >= m && i != prime) {
        is_prime[i - m] = false;
      }
    }
  }

There are several things I notice that are suboptimal:

The loop increments by prime.  You could achieve 2x speeds if you only handled odd numbers and incremented by 2*prime instead.  The only even prime is 2 and you can check for that as a special case outside the sieve.
You have a if (i >= m) check which could be removed if you just started the loop from the right starting value.
You have a if (i != prime) check which could be removed if you just started the loop from the right starting value.
You do a subtraction i-m on every iteration.

So what is the correct starting value?  You were close in your (m / prime) * prime) expression.  The problem is that your expression could result in a value smaller than m.  You should just round up like this:

int start = ((m + prime - 1) / prime) * prime;

This gets rid of the i >= m check.  But also, start should be at least prime * prime, because any multiple of prime less than that will already have been handled by a lower prime.

start = max(start, prime * prime);

This gets rid of the case where you might reach i == prime.  Thirdly, start should be odd, because if you are doing #1 above, you should start at an odd index and increment by an even increment.

if ((start & 1) == 0)
    start += prime;

Lastly, by subtracting m from start and making your loop go until n-m, you can get rid of the subtraction inside the loop.

start -= m;

Rewrite

Here is a rewrite of your whole program using the above ideas:

#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

#define MAX        1000000000

typedef vector<bool> VB;
typedef vector<int> VI;

// This holds the primes from 3..sqrt(MAX)
VI primes;

// Finds the primes from 3..n and stores them in the global "primes".
static void findPrimes(int n)
{
    int i;
    int sqrtn = sqrt(n);
    VB  is_prime(n+1, true);

    for (i = 3; i <= sqrtn; i += 2) {
        if (is_prime[i]) {
            int increment = i+i;
            primes.push_back(i);
            for (int j = i * i; j <= n; j += increment) {
                is_prime[j] = false;
            }
        }
    }
    for (; i <= n; i += 2) {
        if (is_prime[i])
            primes.push_back(i);
    }
}

// Finds the primes in the range [m..n] and prints them.
void segmented_sieve(int m, int n)
{
    int range = n - m;
    VB is_prime(range + 1, true);

    for (int prime : primes) {
        int increment = prime + prime;
        // Start should be the first multiple of prime >= m, or prime^2,
        // whichever is larger.  Also make sure start is odd.
        int start = max(((m + prime - 1) / prime) * prime, prime * prime);
        if ((start & 1) == 0)
            start += prime;
        // Adjust to range so we don't have to subtract m in the loop.
        start -= m;
        for (int i = start; i <= range; i += increment) {
            is_prime[i] = false;
        }
    }

    if (m <= 2 && n >= 2)
        printf("2\n");
    for (int k = (m & 1) ? 0 : 1; k <= range; k += 2) {
        if (is_prime[k]) {
            printf("%d\n", m + k);
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);

    findPrimes(sqrt(MAX));
    while (t--) {
        int m, n;
        scanf("%d%d", &m, &n);
        if (m == 1) m++;
        segmented_sieve(m, n);
    }
    return 0;
}


Possible antipattern: looping until a search condition is met Whenever I write a loop, I always use closure if it's appropriate by way of a self-executing anonymous function. I will typically write my searching loops as follows:

var i = 0, length = myArr.length,
    fe = null;

for (; i < length; i++) {
    if ((function (el) {
            if (el.searchCondition) {
                fe = el;
                return true;
            }
        }(myArr[i])) === true) {
        break;
    }
}

return fe;

I thought it was minimal code and pretty clean. I know it's not the easiest to read - but is there any reason why I should not be doing it this way?

I know it's not the easiest to read - but is there any reason why I should not be doing it this way?

You answered your own question already. It's not easy to read, which is a very good reason not to do it this way.

In addition to the readability, your code will (probably, I didn't profile it) also perform worse than the simple solution (because of the extra function call).

So you have two points against this pattern. What are the advantages?

Two other points: if (exp === true) adds extra complexity. I would just write if (exp), and let the function return false. And you should assign i right were you need it, inside the loop.

If you consider all those points, your code might look like this:

var length = myArr.length,
    fe = null;

for (var i = 0; i < length; i++) {
    if (myArr[i].searchCondition) {
        fe = myArr[i];
        break;
    }
}

return fe;

If you don't like that the array is accessed twice, save the value in a temporary variable. Or just return directly like @dusky did:

var length = myArr.length;

for (var i = 0; i < length; i++) {
    if (myArr[i].searchCondition) {
        return myArr[i];
    }
}


Multiple dispatch with variant and multi visitation in C++ The following program is a demonstration of variant and double visitation used to obtain double dispatch between the elements of two inhomogeneous containers. Most of the work is done at compile time. What do you think about it compared to the dynamic version in explained in Wikipedia?

boost::variant does not employ variadic templates and has a hand coded limit to 20 different types which can be easily extended to 50 but not beyond. Is it a crazy idea to use this pattern (with an appropriate variant implementation) with more than 50 types, say 100 spaceships and 10 different asteroids or so?

#include <iostream>
#include <vector>
#include "boost/variant.hpp"
using std::cout;
using std::endl;

////////// some basic objects

class SpaceShip {};
class ApolloSpacecraft : public SpaceShip {};

class Asteroid {
public:
  void CollideWith(SpaceShip&)
       { cout << "Asteroid hit a SpaceShip" << endl; }
  void CollideWith(ApolloSpacecraft&)
       { cout << "Asteroid hit an ApolloSpacecraft" << endl; }
};

class ExplodingAsteroid : public Asteroid {
public:
  void CollideWith(SpaceShip&)
       { cout << "ExplodingAsteroid hit a SpaceShip" << endl; }
  void CollideWith(ApolloSpacecraft&)
       { cout << "ExplodingAsteroid hit an ApolloSpacecraft" << endl; }
};
////////// visitor

struct CollideVisitor : public boost::static_visitor<void> {
  template <typename A, typename S>
  void operator()( A & a, S & s) const { a.CollideWith(s);}
};

////////// demo

int main() {
  std::vector<boost::variant<Asteroid,ExplodingAsteroid>> asteroids;
  asteroids.emplace_back(Asteroid());
  asteroids.emplace_back(ExplodingAsteroid());

  std::vector<boost::variant<SpaceShip,ApolloSpacecraft>> spaceships;
  spaceships.emplace_back(SpaceShip());
  spaceships.emplace_back(ApolloSpacecraft());

  for (auto & a : asteroids) {
    for (auto & s : spaceships) {
      boost::apply_visitor(CollideVisitor(), a, s);
    }
  }

  return 0;
}

It's a good example of multimethods in C++. But you should be aware that variant takes at least as much space as the biggest of its argument. It's done so to minimize overhead of walking an additional pointer. Probably, you need a variant with another allocation policy, as asteroids and spaceships are quite numerous.

But, to be serious, there's an even bigger problem: extension. You would like to

define new functions that do something with asteroids, spaceships or tuples of them;
define new types of asteroids and spaceships;
modify code only locally.

Your solution needs to have variant<list, of, all, objects, of, the, kind> in several places of your code in addition to defining a new classes for new types of game objects. That's a non-local change.


Performing the Lychrel algorithm in Rust A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers.

In the code below I'm trying to calculate the palindrome that comes from the end of this algorithm up to some limit (as it is hypothesized to be infinite for some values).

extern crate num;
extern crate time;

use num::bigint::BigInt;
use num::FromPrimitive;
use time::PreciseTime;
use std::env;

// The limit for number of iterations to run.
static LIMIT: u64 = 5000;

// Return the "lychrel" number for a given input, or the number reached
// at iteration LIMIT, whichever comes first.
fn lychrel(number: u64) -> BigInt {
    let mut next = FromPrimitive::from_u64(number).unwrap();
    let mut iterations = 0;
    let mut rev;

    loop {
        // rev = reverse(&next, &zero);
        rev = reverse_str(&next);

        if &next == &rev {
            break;
        }

        next = &next + &rev;

        if iterations % 1000 == 0 { println!("{} iterations complete.", iterations) }
        if iterations == LIMIT { break; }

        iterations += 1;
    }

    next
}

// Integer function is nearly 4 (!) times slower.
// So this function has been removed, in favour of reverse_str()
// fn reverse(number: &BigInt, zero: &BigInt) -> BigInt {
//  let zero: BigInt = FromPrimitive::from_u64(0).unwrap();
//  let mut reverse = FromPrimitive::from_u64(0).unwrap();
//  let mut temp = number.clone();

//  while &temp > &zero {
//      reverse = reverse * 10 + &temp % 10;
//      temp = &temp / 10;
//  }

//  reverse
// }

// Transform a BigInt into a char array, reverse and parse back into a BigInt.
fn reverse_str(number: &BigInt) -> BigInt {
    let reverse_string: String = number.to_string().chars().rev().collect();
    let reverse_value: BigInt = reverse_string.parse().unwrap();
    number + reverse_value
}

fn main() {
    let args: Vec<_> = env::args().collect();
    let start = PreciseTime::now();

    let input = args[1].parse::<u64>().expect("Usage: ./lychrel <number>");

    lychrel(input);
    // println!("{}", lychrel(input));

    let end = PreciseTime::now();
    println!("Processed {} iterations in {} seconds.", LIMIT, start.to(end));
}

(Note that this requires the num and time crates to be installed)

This is my first time using Rust, so I'm finding the entire idea of "ownership" pretty new. Am I passing data by reference too much?  I seem to have a lot of ampersands.

Use const instead of static if you don't need to take the address of the global.
Use for over a range instead of mutating a counter.
It's a little strange to return a value when the iteration runs out. Perhaps an Option would be better?
There's no need to take references just to compare for equality; eq takes &self.
Don't need &next or &rev when adding to get next because we no longer need these values.
reverse_str does more than just reverse; perhaps a better name is in order?
No need to collect all the arguments to an array, just use the iterator directly.

extern crate num;
extern crate time;

use num::bigint::BigInt;
use num::FromPrimitive;
use time::PreciseTime;
use std::env;

const LIMIT: u64 = 5000;

fn lychrel(number: u64) -> BigInt {
    let mut next = FromPrimitive::from_u64(number).unwrap();
    let mut rev;

    for i in 0..LIMIT {
        rev = reverse_str(&next);

        if next == rev {
            break;
        }

        next = next + rev;

        if i % 1000 == 0 {
            println!("{} iterations complete.", i)
        }
    }

    next
}

fn reverse_str(number: &BigInt) -> BigInt {
    let reverse_string: String = number.to_string().chars().rev().collect();
    let reverse_value: BigInt = reverse_string.parse().unwrap();
    number + reverse_value
}

fn main() {
    let arg = env::args().nth(1).expect("Usage: ./lychrel <number>");

    let start = PreciseTime::now();
    let input = arg.parse::<u64>().expect("Argument must be a number");
    lychrel(input);
    let end = PreciseTime::now();

    println!("Processed {} iterations in {} seconds.", LIMIT, start.to(end));
}

I think it would be interesting to convert the iteration to an iterator.


Powershell script to iterate through folder and restore SQL backups I am working on a PowerShell script which will loop through a directory containing SQL Server database backup .bak files; move the files to a different location; restore each of those files to the local SQL instance using OSQL.exe; output the SQL output to a log file.

This works OK, but I am willing to improve it.

$sourceBackupDirectory = "C:\FTP"
$sqlDatabaseLocation = "C:\Program Files\Microsoft SQL Server\MSSQL11.MSSQLSERVER\MSSQL\DATA\"
$backupsLocation = "C:\DatabaseRestore\"

Get-ChildItem $sourceBackupDirectory -Filter "*.bak" -Recurse | Move-Item -Destination $backupsLocation #move files
$backupsLocationFiles = Get-ChildItem $backupsLocation -Filter "*.bak" #load files into array

$todayUK = Get-Date -format yyyyMMdd
$logsFolder = "LogFiles\"
$logFile = $backupsLocation + $logsFolder + $todayUK + ".txt"

foreach ($file in $backupsLocationFiles)
{
    $filePath = $backupsLocation + $file
    $file = [io.path]::GetFileNameWithoutExtension($file)
    #$filePath
    #$file

    RestoreDB $file $filePath
}

function global:RestoreDB ([string] $newDBName, [string] $backupFilePath)
{
    [string] $dbCommand = "RESTORE DATABASE [$newDBName] " +
    "FROM    DISK = N'$backupFilePath' " +
    "WITH    FILE = 1, " +
    "MOVE N'$newDBName' " +
    "TO N'$sqlDatabaseLocation" + "$newDBName.mdf', " +
    "MOVE N'$newDBName" + "_log' " +
    "TO N'$sqlDatabaseLocation" + "$newDBName" + "_log.ldf', " +
    "NOUNLOAD, REPLACE, STATS = 5"
    Write-Host $dbCommand

    OSQL.EXE -E -Q $dbCommand >> $logFile #this ouputs the SQL output into a logfile.
}

This is mostly style things, but:

You should store all your constants at the top (including $logsFolder)
#this ouputs the SQL output into a logfile: you misspelled outputs
You should use the string concatenation syntax:

"TO N'$($sqlDatabaseLocation)$($newDBName)_log.ldf',"

You only use $todayUK once, so you should include it directly as a string instead of declaring it.
Instead of concatenating each string component together, use a multi line string operator like @" or a trailing backtick `.

    [string] $dbCommand = @"RESTORE DATABASE [$newDBName]
FROM    DISK = N'$backupFilePath'
WITH    FILE = 1,
MOVE N'$newDBName'
TO N'$($sqlDatabaseLocation)$($newDBName).mdf',
MOVE N'$($newDBName)_log'
TO N'$($sqlDatabaseLocation)$($newDBName)_log.ldf',
NOUNLOAD, REPLACE, STATS = 5"

Now, you can just directly call that string instead of assigning it to $dbCommand:

    Write-Host @"RESTORE DATABASE [$newDBName]
FROM    DISK = N'$backupFilePath'
WITH    FILE = 1,
MOVE N'$newDBName' #more stuff here


Controller code using the koa framework I would like to gather ideas on how to refactor the JavaScript/NodeJS controller code below to be more aesthetic. The code is using the koa framework thus I use yield commands. I also use mongoose (I'm waiting for 3.9.2 which will support promises).

As a Ruby on Rails developer, I'm searching for a Rails-style way on writing NodeJS programs.

'use strict'

/*
 * Model dependencies
 */

var _ = require('lodash')
var parse = require('co-body')
var db = require('mongoose-glue')

/*
 * User controller.
 */

module.exports = {

  /*
   * Lists available users.
   */

  index: function*(id) {
    var skip, limit
    skip = Math.max(0, this.query.skip)
    limit = Math.min(10, this.query.limit)
    this.body = yield db.model('user').find().skip(skip).limit(limit).exec()
  },

  /*
   * Displays user with an id.
   */

  show: function*(id) {
    this.body = yield db.model('user').findById(id).exec()
    this.status = this.body ? 200 : 404
  },

  /*
   * Creates a new user.
   */

  create: function*() {
    var data
    try {
      data = yield formData(this, 'name')
      this.body = yield createUser(data)
      this.status = 201
    } catch(e) {
      this.body = e
      this.status = 403
    }
  },

  /*
   * Updates user with an id.
   */

  update: function*(id) {
    var data
    try {
      data = yield formData(this, 'name')
      this.body = yield updateUser(id, data)
    } catch(e) {
      this.body = e
      this.status = 403
    }
  },

  /*
   * Removes user with an id.
   */

  destroy: function*(id) {
    var item
    try {
      item = yield destroyUser(id)
      this.status = item ? 200 : 404
    } catch(e) {
      this.body = e
      this.status = 403
    }
  },

}

/*
 * Create user thunk
 */

function createUser(data) {
  return function(next) {
    db.model('user').create(data, next)
  }
}

/*
 * Update user thunk.
 */

function updateUser(id, data) {
  return function(next) {
    db.model('user').findByIdAndUpdate(id, data, next)
  }
}

/*
 * Create user thunk
 */

function destroyUser(id) {
  return function(next) {
    db.model('user').findByIdAndRemove(id, next)
  }
}

/*
 * Returns form data.
 */

function *formData(ctx) {
  var data
  data = yield parse.form(ctx)
  data = _.any(arguments) ? _.pick(data, arguments) : data
  return data
}

Interesting question,

I understand you search for a rails-style way on how to write nodejs programs. However from a CodeReview perspective, your code should be idiomatic (conforming to the mode of expression characteristic of a language) so that other developers can grok your code and even maintain it.

From that perspective your code is quite good, the only thing being that you really (really) should put those semi-colons. Just get over it, good JavaScript has semicolons at the end of each line.

Other than that:

I like the use of 'use strict', generator functions and yield
I like the amount of comments, not so much the style, I would go for less vertical real estate

/*
 * User controller.
 */

could just as well be

//User controller

It's a matter of taste but I find this more idiomatic

var skip = Math.max(0, this.query.skip),
    limit = Math.min(10, this.query.limit);

than

var skip, limit
skip = Math.max(0, this.query.skip)
limit = Math.min(10, this.query.limit)

I guess from a style perspective you want to split declaration from initialization, but I find this takes too much vertical real estate.
Logging/Handling errors, you should consider putting more effort in handling errors than simply throwing a 403 on the client side, you should do something on the server side as well
Magic constants (404, 200) etc. are known well enough that you don't have to create named constants.

All in all I like your code, I guess if I had to maintain I would run it thru a script to fix all the semicolons and comments and go from there ;)


Implementing simplified Jaipur board game I wanted to build a bot for playing Jaipur board game. I started by implementing a simplified version of the game without bot. Want to make sure I'm going in the right direction.
Few of the simplifications from the actual game:

Prices of commodities are fixed
No camels
Only one card is visible and can be picked from the market
Cards are not shuffled at the start

Code:

import random
import numpy as np

DIAMOND = 0
GOLD = 1
SILVER = 2
SILK = 3
SPICE = 4
LEATHER = 5
commodities = [DIAMOND, GOLD, SILVER, SILK, SPICE, LEATHER]

price = [7, 6, 5, 3, 3, 1] # DIAMOND, GOLD, SILVER, SILK, SPICE, LEATHER

TAKE = 0
SELL = 1
actions = [TAKE, SELL]

class Jaipur():
    def __init__(self, player1, player2):
        self.market = [DIAMOND] * 6 + [GOLD] * 6 + [SILVER] * 6 + [SILK] * 8 + [SPICE] * 8 + [LEATHER] * 10

        player1 = globals()[player1]
        player2 = globals()[player2]

        self.player1 = player1(tag='P1')
        self.player2 = player2(tag='P2')

        self.winner = None
        self.player_turn = self.player1

    def play_game(self):

        # while len(self.market != 0):
        while self.winner is None:
            self.state = self.play_move()
            self.game_winner()

            if self.winner is not None:
                print('P1 score: ', self.player1.score)
                print('P2 score: ', self.player2.score)

                print('Winner is ', self.winner)

    def play_move(self, learn=False):

        if self.player_turn == self.player1:
            self.print_game()
            new_market = self.player1.make_move(self.market, self.winner)
            self.player_turn = self.player2

        elif self.player_turn == self.player2:
            self.print_game()
            new_market = self.player2.make_move(self.market, self.winner)
            self.player_turn = self.player1

    def print_game(self):
        print(self.market)
        print('turn: ', self.player_turn.tag)
        print('market: ', self.market)
        print('player hand: ', self.player_turn.hand)
        print('player score: ', self.player_turn.score)

    def game_winner(self):

        if len(self.market) == 0:
            if self.player1.score > self.player2.score:
                self.winner = self.player1.tag
            else:
                self.winner = self.player2.tag
        return self.winner

class Player():
    def __init__(self, tag):
        self.tag = tag
        self.hand = [0] * len(commodities)
        self.score = 0

    def hand_size(self):
        return sum(self.hand)

    def take(self, market):
        print('taking..')
        if self.hand_size() == 7:
            return market

        if len(market) == 0:
            return market

        taken = market.pop()
        self.hand[taken] += 1

        return market

    def sell(self, market, commodity=None):
        print('selling..')
        if commodity is None:
            commodity = np.argmax(self.hand)

        if commodity in [DIAMOND, GOLD, SILVER] and self.hand[commodity] < 2:
            return market

        if self.hand[commodity] < 1:
            return market

        self.score += self.hand[commodity] * price[commodity]
        if self.hand[commodity] == 3:
            self.score += 2
        elif self.hand[commodity] == 4:
            self.score += 5
        elif self.hand[commodity] >= 5:
            self.score += 9

        self.hand[commodity] = 0

        return market

    def make_move(self, market, winner):
        # move = int(input('0: Take, 1: Sell. Choose move..'))
        move = random.randint(0, 1)
        new_market = market
        if move == 0:
            new_market = self.take(market)
        elif move == 1:
            new_market = self.sell(market)

        return new_market

def play():
    game = Jaipur('Player', 'Player')
    game.play_game()

play()

Here are a couple of first-glance observations:

Use enum. If you are going to have all-caps names with integers, you might as well import the module and get all the benefits.
Don't pass classes by name. Pass them by value. Change this: game = Jaipur('Player', 'Player') into something like game = Jaipur(Player, Player) (note: no quotes).

Classes are first-class objects in Python. You can pass them around just like any other object.
Use the game class to enforce the rules. You have code in your Player class to check on things like the minimum number of commodities to trade. Put that in the game class instead. Also, make the game class the keeper of records. If your Player class is supposed to be an AI, then let the game handle the record-keeping and have the player just tell the game what it wants.
(An example of the Single Responsibility Principle.)
Don't import numpy just to use argmax! Python defines a max() builtin.


Dining Philosopher's problem implementation with Java Locking Framework to avoid deadlock Dining philosopher problem is one of the classic problems in computer science. I intended to implement it using Java threads. I attempted using the locking framework that came with Java 5 and used the tryLock() method to avoid deadlock. My implementation is fairly simple. I implemented the runnable interface to represent a philosopher and used executor service to run all these runnable.

As a lock, I have used ReentrantLock. I know there are several implementations are already discussed here, but I would like to get some review on my implementation.

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;

public class Philosopher implements Runnable {
    private String name;
    private final Lock leftFork;
    private final Lock rightFork;

    public Philosopher(String name, Lock leftFork, Lock rightFork) {
        this.name = name;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    public void think() {
        log("thinking");
    }

    public void eat() {
        //assume, eating requires some time.
        //let's put a random number
        try {
            log("eating");
            int eatingTime = getRandomEatingTime();
            TimeUnit.NANOSECONDS.sleep(eatingTime);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    @Override
    public void run() {
        while (true) {
            keepThinkingAndEating();
        }
    }

    private void keepThinkingAndEating() {
        think();

        if (leftFork.tryLock()) {
            try {
                log("grabbed left fork");
                if (rightFork.tryLock()) {
                    try {
                        log("grabbed right fork");
                        eat();
                    } finally {
                        log("put down right fork");
                        rightFork.unlock();
                    }
                }
            } finally {
                log("put down left fork");
                leftFork.unlock();
            }
        }
    }

    private void log(String msg) {
        DateTimeFormatter formatter = DateTimeFormatter.ISO_LOCAL_TIME;
        String time = formatter.format(LocalDateTime.now());
        String thread = Thread.currentThread().getName();
        System.out.printf("%12s %s %s: %s%n", time, thread, name, msg);
        System.out.flush();
    }

    private int getRandomEatingTime() {
        Random random = new Random();
        return random.nextInt(500) + 50;
    }
}

And the main method to run this code:

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class PhilosopherMain {
    public static void main(String[] args) {
        Lock[] forks = new Lock[5];
        for (int i = 0; i < forks.length; i++) {
            forks[i] = new ReentrantLock();
        }

        Philosopher[] philosophers = new Philosopher[5];

        ExecutorService executorService = Executors.newFixedThreadPool(5);

        for (int i = 0; i < philosophers.length; i++) {
            Lock leftFork = forks[i];
            Lock rightFork = forks[(i + 1) % forks.length];
            philosophers[i] = new Philosopher("Philosopher " + (i + 1), leftFork, rightFork);
            executorService.execute(philosophers[i]);
        }

        executorService.shutdown();
    }
}

Your implementation is minimalistic but it does what it does and it does it good.

Your code consists basically of three elements:

Setup the place
Logging actions of the philosophers
Handling philosopher behaviour

1 and 2 are not that interesting as they may differ slightly from implementation to implementation. And in general you did not reach a code mass to address any modularization issues.

Number 3 is the part I want to address. You chose the egoistic variant of the dining philosophers. A philosopher may face starvation if other philosophers keep taking the forks in unfavorable point of times.

Another variant is cooperative. You have to introduce one more artefact to do so. Philosophers may give aquired forks directly to their neighbors if they registered for usage of a fork while the fork itself is currently unavailabe. This prevents a philosopher from releasing the fork and aquiring it again immediately so other philosophers have no chance to introduce themselves in the process.


String Calculator Kata in Scala This is my solution of string calulator kata in scala(i'm new of tdd).
I'd like a general review of this.

  String Calculator

  Create a simple String calculator with a method int Add(string
  numbers) The method can take 0, 1 or 2 numbers, and will return their
  sum (for an empty string it will return 0) for example “” or “1” or
  “1,2”

  -Allow the Add method to handle an unknown amount of numbers

  -Allow the Add method to handle new lines between numbers (instead of commas). the following input is ok:  “1\n2,3”  (will equal 6) the
  following input is NOT ok:  “1,\n” (not need to prove it - just
  clarifying)

  -Support different delimiters to change a delimiter, the beginning of the string will contain a separate line that looks like this:
  “//[delimiter]\n[numbers…]” for example “//;\n1;2” should return three
  where the default delimiter is ‘;’ .

  -Numbers bigger than 1000 should be ignored, so adding 2 + 1001  = 2

  -Delimiters can be of any length with the following format:  “//[delimiter]\n” for example: “//[***]\n1***2***3” should return 6

package stringcalculator

    import org.scalatest.{BeforeAndAfter, FunSuite}

    class StringCalculetor3 extends FunSuite with BeforeAndAfter {

    private val calculator = new Calculator(new InputParser())

    before {}

    test("sum of empty string is 0") {

      assert(0 === sum(""))

    }

    test("sum of one number  string is number") {

      assert(5 === sum("5"))
      assert(6 === sum("6"))

    }

    test("sum of two  numbers  separated with comma") {

      assert(3 === sum("1,2"))
      assert(5 === sum("1,4"))

    }

    test("sum of 3  numbers separated with comma") {

      assert(6 === sum("1,2,3"))

    }

    test("sum of 2  numbers  separated new line  separetor") {

      assert(3 === sum("1\n2"))
      assert(6 === sum("1\n2,3"))

    }

    test("sum of 2 numbers with another separator") {

      assert(3 === sum("//;\n1;2"))

    }

    test("sum of 2 numbers with multiple separator") {
      assert(3 === sum("//[;]\n1;2"))
      assert(3 === sum("//[--]\n1--2"))
    }

    test("numbers > 1000 do not fall in the sum") {
      assert(3 === sum("1,2,1001"))
    }

    private def sum(in: String): Int = {
      calculator.sum(in)
    }

The calculator

package stringcalculator

/**
 * Created by MarcopTo on 20/10/2015.
 */
class Calculator(inputParser: InputParser) {

  def sum(input: String): Int = {
    val (in, separetor) = inputParser.parse(input)
    val numbers = in.split(separetor).map(_.toInt).filter(_ < 1001)
    numbers.sum
  }

}

The parser

package stringcalculator

/**
 * Created by MarcopTo on 20/10/2015.
 */
class InputParser() {

  private val defaultSeparator: String = ",|\n"
  private val singleSeparatorPosition: Int = 2

  def parse(input: String): (String, String) =
    if (containsSeparator(input)) {
      val endOfHeader: Int = input.indexOf("\n")
      val separetor = extractSeparator(input,endOfHeader)
      val in = extractInput(input,endOfHeader)
      (in, separetor)
    }else
      (defaultInput(input), defaultSeparator)

  private def defaultInput(input: String): String = if (input.isEmpty) "0" else input

  private def containsSeparator(in: String): Boolean = in.contains("//")

  private def extractInput(input: String,endOfHeader: Int): String = input.substring(endOfHeader+1)

  private def extractSeparator(in: String,endOfHeader: Int): String = {
    val header = getHeader(in, endOfHeader)
    if (containsMultipleSeparator(header))
      in.substring(in.indexOf("[") + 1, in.indexOf("]"))
    else
      header.charAt(singleSeparatorPosition).toString
  }

  private def getHeader(in: String, endOfHeader: Int): String = in.substring(0, endOfHeader)
  private def containsMultipleSeparator(in: String): Boolean = in.contains("[")

}

It is nice that you have divided the parsing and the actual calculation over the InputParser and the Calculator.

I think your InputParser can be improved at some points :

Using a regular expression to extract the separator would reduce the size of your InputParser and the large number of methods needed to get the separator.
I would also include the splitting of the input in the parser, so you can return only the numbers. The user of the parser does not really need to know which separator was used.
toInt throws an exception if the string can not be converted to an Int, which you don't handle. More ideomatic Scala would be to return an Option, Try, ...
If you add more functionality to the InputParser, you probably should also create unit tests for the InputParser class.

My attempt to improve your InputParser :

class Parser {
  private val defaultSeparator: String = ",|\n"

  // parse now returns an Option[List[Int]]
  // -> invalid input now returns None (eg parse("foo"))
  def parse(input: String): Option[List[Int]] = {
    input match {
      case "" => Some(List(0))
      case SeparatorNumbers(sep, numbers) =>
        val separator = sep.map(escapeSeparator).getOrElse(defaultSeparator)
        val stringNumbers = numbers.split(separator).toList
        // stringNumbers.map(...) is of type List[Option[Int]]
        // the sequence function below turns this into Option[List[Int]]
        // (you could also use Scalaz for sequence (or traverse), but
        // that is probably overkill if you only use it here)
        sequence(stringNumbers.map(i => Try(i.toInt).toOption))
      case _ => None
    }
  }

  // not explicitly mentioned in the requirements
  // make multiple separators possible (eg "//[:|;|,]\n1:2;3.4")
  private def escapeSeparator(sep: String) =
    sep.split("""\|""").map(java.util.regex.Pattern.quote).mkString("|")

  // an extractor object which uses a regular expression
  // pattern matching with SeparatorNumbers gives an optional separator
  // and the numbers (still as one string)
  object SeparatorNumbers {
    // regular expression with two capture groups for separator and the rest
    private val Extract = """(?s)^(?://\[?(.+)\]?\n)?(.*)""".r

    def unapply(input: String): Option[(Option[String], String)] =
      input match {
        // if no separator is found, sep is null
        // Option(sep) will then be None
        case Extract(sep, numbers) => Some(Option(sep), numbers)
        case _ => None
      }
  }
}

// possible implementation to sequence List[Option[A]]
def sequence[A](listO: List[Option[A]]) : Option[List[A]] =
  listO.foldLeft(Option(List.empty[A])) {
    case (None, _) => None
    case (_, None) => None
    case (Some(list), Some(elem)) => Some(elem :: list)
  }.map(_.reverse)

Your Calculator class could pretty mutch stay the same, you only need to handle Option[List[Int]] instead of List[Int].

val p = new Parser

def add(input: String) = {
  p.parse(input).map(_.filter(_ < 1001).sum)
  // now Option[Int], depends how you want to handle invalid input
}


Array implementation of Java Stack As an exercise, I wanted to make an array implementation of Stack, including most of the methods from the native Java Stack.

I'd like to know the following:

Does the code follow good programming principles?
Is the code readable/understandable?
Are there any redundant fields/operations?
Is there a way to further improve the code?
Should I reduce the capacity of the stack at some point? Testing the native Java Stack, it doesn't seem to do any size reduction, except with trim().

Note: I know Javadoc is missing, but I am only just beginning to read into that.

import java.util.Arrays;
import java.util.EmptyStackException;
import java.util.Random;

@SuppressWarnings("unchecked")
public class ArrayStack<T> {
    private T[] data;
    private int numElements;
    private static final int INITIAL_CAPACITY = 10;

    public ArrayStack() {
        data = (T[]) new Object[INITIAL_CAPACITY];
    }

    private void enlarge() {
        T[] temp = Arrays.copyOf(data, data.length);
        data = (T[]) new Object[data.length * 2];

        for (int i = 0; i < temp.length; i++) {
            data[i] = temp[i];
        }
    }

    public void push(T element) {
        if (numElements == data.length) {
            enlarge();
        }

        data[numElements] = element;
        numElements++;
    }

    public T peek() {
        if (isEmpty()) throw new EmptyStackException();
        return data[numElements - 1];
    }

    public T pop() {
        if (isEmpty()) throw new EmptyStackException();
        T element = data[--numElements];
        data[numElements] = null;
        return element;
    }

    public boolean isEmpty() {
        return (numElements == 0);
    }

    public int capacity() {
        return data.length;
    }

    public int size() {
        return numElements;
    }

    public void clear() {
        for (int i = 0; i < numElements; i++) {
            data[i] = null;
        }

        numElements = 0;
    }
}

Suppressing warnings

It's hard to defend suppressing warnings at the class level.
The problematic lines in your code are these:

    data = (T[]) new Object[INITIAL_CAPACITY];

Which appears in two places.
I suggest to move the array allocation to one place,
and suppress the warning only for that line, like this:

public ArrayStack() {
    data = newArray(INITIAL_CAPACITY);
}

private final T[] newArray(int capacity) {
    @SuppressWarnings("unchecked")
    T[] tmp = (T[]) new Object[capacity];
    return tmp;
}

private void enlarge() {
    T[] temp = Arrays.copyOf(data, data.length);
    data = newArray(data.length * 2);

    System.arraycopy(temp, 0, data, 0, temp.length);
}

This hits two birds with one stone:

The ugly array creation is now at once place instead of two
Warnings are suppressed for the single problematic line, not for the entire class

In case you were wondering, the local tmp variable is necessary in newArray, otherwise Java doesn't allow suppressing the warning on a return statement or regular assignment. It has to be declaration + assignment.

Another important note here is the private final modifier of newArray.
The private modifier is necessary to prevent sub-classes from overriding the behavior and potentially breaking the constructor.
The final modifier is necessary to prevent sub-classes from shadowing the method by another method with the same name, causing confusion.

Manual array copy

Instead of this:

for (int i = 0; i < temp.length; i++) {
    data[i] = temp[i];
}

It's better to use System.arraycopy instead:

System.arraycopy(temp, 0, data, 0, temp.length);

(Also seen in the previous section.)

Other minor things

In clear, I'm wondering why you manually null out the elements,
rather than simply creating a fresh new array.
You could let the garbage collector take care of the stale array.

Random is unused, so remove the import.