Simple multiple choice quiz Just wondering if there's anything I can improve on, I just started with Python recently and this is one of my first programs.

# Defining Score variables
x = 0
score = x

# Question One
print("What is 1 + 1")
answer_1 = input("a)1\nb)2\nc)3\nd)4\n:")
if answer_1.lower() == "b" or answer_1.lower() == "2":
    print("Correct")
    x = x + 1
else:
    print("Incorrect, 1 + 1 is 2")

# Question Two
print("Who is the 45th president of the United States?")
answer_2 = input("a)Barack Obama\nb)Hillary Clinton\nc)Donald      Trump\nd)Tom Brady\n:")
if answer_2.lower() == "c" or answer_2.lower() == "donald trump":
    print("Correct")
    x = x + 1
else:
    print("Incorrect, The 45th president is Donald Trump")

# Question Three
print("True or False... The Toronto Maple Leafs have won 13 Stanley   Cups?")
answer_3 = input(":")
if answer_3.lower() == "true" or answer_3.lower() == "t":
    print("Correct")
    x = x + 1
else:
    print("Incorrect")

# Question Four
print("What was the last year the Toronto Maple Leafs won the Stanley   Cup?")
answer_4 = input("a)1967\nb)1955\nc)1987\nd)1994\n:")
if answer_4.lower() == "a" or answer_4 == "1967":
    print("Correct")
    x = x + 1
else:
    print("Incorrect, The last time the Toronto Maple Leafs won the Stanley Cup was 1967")

# Question Five
print("True or False... The current Prime Minister of Canada is Pierre Elliot Tredeau?")
answer_5 = input(":")
if answer_5.lower() == "false" or answer_5.lower() == "f":
    print("Correct")
    x = x + 1
else:
    print("Incorrect, The current Prime Minster of Canada is Justin Tredeau")

#Total Score
score = float(x / 5) * 100
print(x,"out of 5, that is",score, "%")

1. DRY (Don't Repeat Yourself)

You should define containers for your questions and answers. This way you can avoid having to repeat the whole logic for every question.

As a first step, I would advise to put all your question texts, answer texts, choice texts and correct answer texts in lists.

Then you can write a function that iterates over these lists (at the same time) and does the actual game. For this you can use zip.

questions = ["What is 1 + 1",
             "Who is the 45th president of the United States?",
             "True or False... The Toronto Maple Leafs have won 13 Stanley   Cups?",
             "What was the last year the Toronto Maple Leafs won the Stanley   Cup?",
             "True or False... The current Prime Minister of Canada is Pierre Elliot Tredeau?"]
answer_choices = ["a)1\nb)2\nc)3\nd)4\n:",
                  "a)Barack Obama\nb)Hillary Clinton\nc)Donald Trump\nd)Tom Brady\n:",
                  ":",
                  "a)1967\nb)1955\nc)1987\nd)1994\n:",
                  ":"]
correct_choices = [{"b", "2"},
                   {"c", "donald trump"},
                   {"true", "t"},
                   {"a", "1967"},
                   {"false", "f"}]
answers = ["1 + 1 is 2",
           "The 45th president is Donald Trump",
           "",
           "The last time the Toronto Maple Leafs won the Stanley Cup was 1967",
           "The current Prime Minster of Canada is Justin Tredeau"]

def quiz():
    score = 0
    for question, choices, correct_choice, answer in zip(questions, answer_choices, correct_choices, answers):
        print(question)
        user_answer = input(choices).lower()
        if user_answer in correct_choice:
            print("Correct")
            score += 1
        else:
            print("Incorrect", answer)
    print(score, "out of", len(questions), "that is", float(score / len(questions)) * 100, "%")

if __name__ == "__main__":
    quiz()

2. OOP (Object-Oriented Programming)

A second step could be trying to encapsulate this whole object of a question into an actual Python object. That is, a question is an object that has a question(text), an answer, answer choices and correct answer choices.

You could define a class like this:

class Question:
    def __init__(self, question, answer, choices, correct):
        self.question = question
        self.answer = answer
        self.choices = choices
        self.correct = correct

But this class would be nothing but a data storage for these strings. Whenever you have this, you can use a collections.namedtuple.

>>> from collections import namedtuple
>>> Question = namedtuple("Question", "question answer choices correct")
>>> q = Question("What is 1 + 1", "1 + 1 is 2", "a)1\nb)2\nc)3\nd)4\n:", {"b", "2"})
>>> q.question
'What is 1 + 1'
>>> q[3]
{'b', '2'}

So a Question is just a tuple with nice names, so that afterwards q.question = q[0] = 'What is 1 + 1', and so on.

from collections import namedtuple
Question = namedtuple("Question", "question answer choices correct")

questions = [Question("What is 1 + 1", "1 + 1 is 2", "a)1\nb)2\nc)3\nd)4\n:", {"b", "2"}),
             ...]

def quiz():
    score = 0
    for question in questions:
        print(question.question)
        user_answer = input(question.choices).lower()
        if user_answer in question.correct:
            print("Correct")
            score += 1
        else:
            print("Incorrect", question.answer)
    print(score, "out of", len(questions), "that is",
          float(score / len(questions)) * 100, "%")

if __name__ == "__main__":
    quiz()

3. The last push

Last, but not least, you could make enumerating the choices automatic, using string.ascii_lowercase (which is simply the lowercase alphabet) and str.joining it with newlines and the ")" used to separate a letter from the choice associated with that letter.

You could also pass a list of Questions directly to the function, allowing making different quizzes (by choosing randomly 5 questions out of a pool of 100 question, for example).

Finally, you could use str.format to make the print of the final score a bit nicer.

import string
from collections import namedtuple
Question = namedtuple("Question", "question answer choices correct")

questions = [Question("What is 1 + 1", "1 + 1 is 2",
                      ["1", "2", "3", "4"], {"b", "2"}), ...]

def quiz(questions):
    score = 0
    for question in questions:
        print(question.question)
        for line in zip(string.ascii_lowercase, question.choices):
            print(") ".join(line))
        user_answer = input().lower()
        if user_answer in question.correct:
            print("Correct")
            score += 1
        else:
            print("Incorrect", question.answer)
    print("{} out of {} that is {} %".format(score, len(questions), score / len(questions) * 100))

if __name__ == "__main__":
    # Use all questions but the first
    quiz(questions[1:])


Solving the game Set in F# I was playing the game Set online, and thought it would be a good exercise to write an F# script to find all of the sets for me.

The rules of set are as follows:
A SET is 3 cards for which each feature is either common across all 3 cards or is different on each card. The object is to find all the SETs among the cards.

I started learning F# four days ago, so what I'm looking for are obvious/easy/"no duh" improvements. I've started at a low bar of just writing a function to compare a group of three cards, and tell you if those three cards form a set. You can see my first attempt below. It feels a bit clunky, like I'm not really making use of all that F# has to offer.

// Create a record type to represent each card
type Card =
    { Color: string
      Shape: string
      Pattern: string
      Number: int
    }

// Create some functions for comparing elements of a collection
let allEqual l = l |> Seq.pairwise |> Seq.forall (fun (x, y) -> x = y)
let allDifferent l = (l |> Seq.distinct |> Seq.length) = (Seq.length l)

// Combine them
let isSet l = (allEqual l) || (allDifferent l)

// The meat of this script
let compare card1 card2 card3 =
    // Put the cards together for easy iteration
    let cardList = [card1; card2; card3]

    // Check each field of the record to see if it makes a set
    let colorSet   = cardList |> List.map (fun c -> c.Color  ) |> isSet
    let shapeSet   = cardList |> List.map (fun c -> c.Shape  ) |> isSet
    let patternSet = cardList |> List.map (fun c -> c.Pattern) |> isSet
    let numsSet    = cardList |> List.map (fun c -> c.Number ) |> isSet

    // Check that they all make a set
    colorSet && shapeSet && patternSet && numsSet

// Test the functions out
let c1 = {Color = "blue"; Shape = "oval"; Pattern = "stripes"; Number = 3}
let c2 = {Color = "red";  Shape = "diamond"; Pattern = "solid"; Number = 2}
let c3 = {Color = "green";  Shape = "squiggle"; Pattern = "empty"; Number = 2}

let areCardsSet = compare c1 c2 c3
printfn "The cards c1, c2, and c3 are a set? %b" areCardsSet

Well, you're off to a good start, I think. Only one major thing comes to mind, when I read your code.

Tuples

Instead of operating on seqs or similar, use a tuple. The size of a tuple is fixed and known at compile time. In this game, you know you'll always consider three cards at a time, so it fits the bill. This will also help simplify your allEqual and allDifferent functions. The isSet function still works, as the parameter l is now a tuple instead of a seq.

let allEqual (c1, c2, c3) = c1 = c2 && c2 = c3
let allDifferent (c1, c2, c3) = c1 <> c2 && c2 <> c3 && c1 <> c3

This affects the shape of your compare function as well. The line

let colorSet = cardList |> List.map (fun c -> c.Color  ) |> isSet

now becomes like

let colorSet = isSet (card1.Color, card2.Color, card3.Color)

and similar for shapeSet, patternSet and numsSet. Now the cardList variable may be removed, and the compare function is short and to the point.

Abstracting the isSet function

Suppose you think the way the colorSet, shapeSet, etc. variables are defined looks to clunky. You could abstract away the commonalities, by defining a function for getting the Color property and so on. These could then be supplied as arguments to the isSet, allEqual and allDifferent functions . Like this:

let color c = c.Color
// ...
let allEqual feature (c1, c2, c3) = feature(c1) = feature(c2) && feature(c2) = feature(c3)
// ...
let cards = (card1, card2, card3)
let colorSet = isSet color cards
// ...

I've only shown a couple of the required functions above, but I hope you get the point. In a small example like this, this might be overkill, but had you had many more features, I would probably go that way.

Discriminated unions

One last point is, that it would be obvious to use discriminated unions instead of string and int. I.e. you could define types for each feature, and use them in the Card definition

type Color = Green | Blue | Red
type Number = One | Two | Three
// ...
type Card = { Color: Color; Number: Number; ... }

This will help readability of your code. Furthermore, if this should interact with the outside would, where input comes in the shape of strings, it pushes parsing and validation to the boundary layer.


Copying a range from one file to another Since it has too many loop, loop inside loop, this works very slowly. How can we increase the speed of this program? I am trying to copy a range from one file to another file of same name in different folder. I have folders named "A","B","C"..."G" inside c:\Charts\1\ and c:\Charts\0\. Inside each folder "A","B","C"..."G" there are files named 1,2,3,4,..10.

dim vArr1 as array
Dim vArr as array
vArr1 = Array("A", "B", "C", "D", "E", "F", "G")
vArr = Array("A", "B", "C", "D", "E", "F", "G")
Dim fileName1, Pathname1 As String
Pathname1 = "c:\Charts\1\"
Pathname="c:\charts\0\"
For Each vFile1 In vArr1
    fileName1 = Dir(Pathname1 & vFile1 & "\" & "*.xlsx")
    Do While fileName1 <> ""
        For Each vFile In vArr
            filename = Dir(Pathname & vFile & "\" & "*.xlsx")
            Do While filename <> ""
                If filename = fileName1 Then
                Set WB1 = Workbooks.Open(Pathname1 & vFile & "\" & fileName1)
                    WB1.Application.ScreenUpdating = False
                    WB1.ActiveSheet.Range("M1:M30").Copy
                    WB1.Close (False)
                Set WBD1 = Workbooks.Open(Pathname & vFile & "\" & filename)
                WBD1.ActiveSheet.Range("C1").Select
                    WBD1.ActiveSheet.Paste
                    WBD1.ActiveSheet.Cells(1, 3).Value = "HSI Q4 2014-15"
                    WBD1.Close (True)
                    filename = Dir()
                Else

                End If
                fileName1 = filename
            Loop
        Next
    Loop
Next

I doubt this is how you've actually declared arrays:

dim vArr1 as array
Dim vArr as array

That would be

Dim vArr1() As String
Dim vArr() As String

But nevermind that: you need to use more meaningful names. If they're folder names, consider calling them something like folders or folderNames - and avoid arbitrary Hungarian-like prefixes such as v.

This is why multiple declarations in the same instruction should be avoided:

Dim fileName1, Pathname1 As String

Do you think fileName1 is a String? It's not. It's implicitly declared as Variant, because As String only applies to Pathname1!

Indentation is off here, and only looks the way it does because WB1 has 3 characters (and it's another bad name):

Set WB1 = Workbooks.Open(Pathname1 & vFile & "\" & fileName1)
    WB1.Application.ScreenUpdating = False
    WB1.ActiveSheet.Range("M1:M30").Copy
    WB1.Close (False)

Should be:

Set WB1 = Workbooks.Open(Pathname1 & vFile & "\" & fileName1)
WB1.Application.ScreenUpdating = False
WB1.ActiveSheet.Range("M1:M30").Copy
WB1.Close (False)

Note that your usage of parenthesis in method calls is going to cause a bug one day or another, when you pass an argument like that into a ByRef parameter.

How so? Well, the "normal" VBA syntax for passing arguments is like this:

WB1.Close False

By doing this:

WB1.Close (False)

You are forcing the argument to be passed ByVal, overriding the procedure's signature that might have said ByRef. Of course it doesn't really matter here for a Boolean literal..

Workbooks.Open(Pathname1 & vFile & "\" & fileName1)

...or even for a String literal. But one day you're going to want to pass an argument into a ByRef parameter, and learn the hard way that parentheses should be dropped when doing procedure calls. They're only needed for function calls.

The main reason why your code is slow is because you're opening and closing workbooks - there's not really anything to do to speed that up unfortunately.

Except perhaps...

WB1.Application.ScreenUpdating = False

Take that part out of the loop, and turn off screen updating all the while.

Application.ScreenUpdating = False

Now, whenever you turn off screen updating, you need to turn it back on when you're done, and you need to handle runtime errors and make sure you're turning it back on even when an error breaks you out of the code. You're accessing the file system here, so you have to handle runtime errors.

See this post for how to properly handle errors in VBA.


Project Euler #1: multiples of 3 and 5 Ruby Total newbie here and wouldn't mind learning from Rubyists to look at how I tried to solve this challenge.

I started with 2 variables n which starts at 0 and total which is an array where I intend to push n if it satisfy the condition set by the 2 modulo. Using the until loop with a max of 1000, my intention was to change total from an empty array with values divisible by 3 and 5.

With total now with array items, I defined a method to take in total as a parameter that I can iterate to add values to a new method variable - sum. The method then returns the new value of sum.

Here's my code.

n = 0
total = []

until n >=1000 do
  if n % 3 == 0 || n % 5 == 0
    total << n
  end
  n += 1
  total
end

def sumTotal(total)
  sum = 0
  total.each { |i| sum+= i.to_i}
  puts sum
end

sumTotal(total)

About your code, a first refactor would include:

n = 0 + until n >=1000 do -> 0.upto(999).each do |n| or (0...1000).each do |n|
total.each { |i| sum += i.to_i}. Why to_i? it's already an integer.

A second refactor would, well, throw away the entire code :) That's how you'd write it in a low-level language (C, for example) but it's not idiomatic Ruby. In Ruby, you use functional constructs with enumerables. It's more concise, more readable, more declarative:

result = (0...1000).select { |n| n % 3 == 0 || n % 5 == 0 }.reduce(0, :+)

That would be perfectly fine but, in the context of the euler project, where you will use the same abstractions over and over, you can do better. What could you abstract here? I'd say: Integer#divisible_by? and Enumerable#sum. Once you've added these methods, the solution can be read out loud (write 0.upto(999) if you want an even more human-readable solution, even though people tend to prefer ranges):

result = (0...1000).select { |n| n.divisible_by?(3) || n.divisible_by?(5) }.sum


JavaScript async functions queue approach I wrote this queue object to handle async functions in JavaScript.
I'm not sure if this is a correct approach.
Is this steady enough to run on nodeJS or it may fail/fault?

var queue = {
    callbacks: [],
    start: function(){
        this.returnVal = this.callbacks.shift()();
    },
    next: function(returnVal){
        try{
            queue.returnVal = queue.callbacks.shift()( returnVal );
        } catch(e) { console.error("oops, this function failed..:", e)}
    },
    add: function( newCallback ){ // adds new funcion to the end of the queue
        this.callbacks.push(newCallback);
    }
}

/* generic functions */

function f1(param1){
    console.log('running f1');
    console.log('param1 is:', param1);
    queue.next('this string was returned from f1'); // return
}
function f2(param1){
    console.log('running f2');
    console.log('param1 is:', param1);
    setTimeout(function(){ // simulate async
        console.log('adding f9 function to the queue');
        queue.add(f9);
        queue.next('this string was returned from f2 after adding f9 to the queue'); // f2 return
    }, 1000);
}
function f3(param1){
    console.log('running f3');
    console.log('param1 is:', param1);
    queue.next(); // f3 return
}

function f9(){
    console.log('running f9');
    queue.next('f9 returns');
}

queue.callbacks.push(f1, f2, f3);
queue.start();

the output is:

running f1
param1 is: undefined
running f2
param1 is: this string was returned from f1
adding f9 function to the queue
running f3
param1 is: this string was returned from f2 after adding f9 to the queue
running f9
oops, this function failed..: [TypeError: queue.callbacks.pop(...) is not a function]

Note that the last line error is due to queue is now empty.
Can the try catch there save nodeJS from crashing?

One thing I find problematic is that queue.next is visible and can openly be called. The problem arises if your async function is waiting, and something else suddenly shifts the queue. You would get an unexpected results. To remedy this, I would suggest hiding next so that only the callbacks are aware of it.

One way to do it is pass in next as an argument to the callback. next would be a function that simply calls the next callback. If I remember correctly, this is how express did middleware.

function callback(arg1, arg2, ..., next){
  // do stuff
  next(arg1, arg2, ...);
}

An alternative would be to return a Promise. An advantage with this approach is that you remove the complexity of having to wrap the next callback as the next argument and instead, just call the callback and expect a Promise.

function callback(resolvedValue){
  // do stuff
  return Promise.resolve(resolution);
}

For your error, you should not rely on try-catch. try-catch should only be used for unexpected errors or errors that are intentionally thrown (like from an API) and meant to be recovered. But in this case, you are aware that it will throw an error when the queue is empty. You should do the check if the queue is empty before proceeding instead of relying on try-catch.

You should consider hiding the queue array. The problem with it being in the open is that it can be modified freely. It might be altered unintentionally, causing odd results. Consider hiding it inside a closure.

Your queue should hold a flag indicating that it's running or paused. Your queue could be in the middle of an async operation when queue.start is called. You wouldn't want the queue to suddenly start running. Also, if your queue runs out of callbacks, what does it do? Does it pause? Does it pick up after receiving a callback? How does third-party code know if the queue is still processing? These are some things to consider, and it depends on how the queue is used.


All possible groups of combinations of array Let's assume I have a one-dimensional array of integers of size n. My problem is to generate all the combination of all possible groups of size 1 to n, such as each combination has exactly one occurrence of each element. The order does not count:

[[1,2]] == [[2,1]]
[[1],[2]] == [[2],[1]]
[[1,2],[3,4]] == [[2,1],[4,3]] == [[4,3],[2,1]]...

For example, for the input array [1,2], I would get:

[[1,2]]
[[1],[2]]

With [1,2,3], I would have:

[[1,2,3]]
[[1,2],[3]]
[[1,3],[2]]
[[2,3],[1]]
[[1],[2],[3]]

And with [1,2,3,4]:

[[1,2,3,4]]
[[1,2,3],[4]]
[[1,2,4],[3]]
[[1,3,4],[2]]
[[2,3,4],[1]]
[[1,2],[3,4]] <= Equivalent to [[3,4],[1,2]]
[[1,3],[2,4]] <= Equivalent to [[2,4],[1,3]]
[[1,4],[2,3]] <= Equivalent to [[2,3],[1,4]]
[[1,2],[3],[4]]
[[1,3],[2],[4]]
[[1,4],[2],[3]]
[[2,3],[1],[4]]
[[2,4],[1],[3]]
[[3,4],[1],[2]]
[[1],[2],[3],[4]]

My code below is working but is actually very slow when the list has more than 6 elements:

public Set<Set<Set<Integer>>> recurseGroups(List<Integer> initialArray, List<Set<Integer>> currentGroups, int i) {
    if (i == initialArray.size()) {
        // Deep copy current group to save its content
        Set<Set<Integer>> copy = currentGroups.stream()
                .map(HashSet::new)
                .collect(Collectors.toSet());

        return Collections.singleton(copy);
    }

    Set<Set<Set<Integer>>> result = new HashSet<>();

    for (int j = i; j < initialArray.size(); ++j) {
        // Add a singleton group with the i-th integer
        // And generate groups with the remaining elements
        Set<Integer> newGroup = new HashSet<>(Collections.singletonList(initialArray.get(i)));
        currentGroups.add(newGroup);
        result.addAll(recurseGroups(initialArray, currentGroups, i + 1));
        currentGroups.remove(newGroup);

        // Add the i-th integer to each previous existing groups
        // And generate groups with the remaining elements
        for (int k = 0; k < currentGroups.size(); ++k) {
            currentGroups.get(k).add(initialArray.get(i));
            result.addAll(recurseGroups(initialArray, currentGroups, i + 1));
            currentGroups.get(k).remove(initialArray.get(i));
        }
    }

    return result;
}

// Calling line
Set<Set<Set<Integer>>> groups = recurseGroups(Arrays.asList(1,2,3), new ArrayList<>(), 0)

By adding a log in the stop condition, I noticed the code actually adds many times the same group combinations. I suspect it would be possible to improve the stop condition or the loop, but I don't see how.

After spending more hours than I'd like to admit on trying to figure out your algorithm and why it is slow, and after multiple false epiphanies, thinking that I have finally discovered the weakness in your program, I believe that, now, I have really found out where the problem with your code lies. Considering all the drafts I've written for explaining where your algorithms wastes performances, trying to format it so that it is easy to read, and even trying out some LaTeX expressions, the emphasis on the word "painfully" becomes all the more justified when I say that the explanation for your algorithm's unsatisfactory performance is really painfully simple. So here goes … the reason your code is slow is:
$$...$$$$...$$$$j$$
Seriously, when the for loop that introduces int j is executed after the first time, it does nothing it hasn't already done the first time around. All local variables declared outside the loop except result (i.e. the method parameters) have the exact same values as they did during the first execution of the loop. I can't believe I didn't see this earlier.

But now that I'm writing an answer to this question, I will also tell you what I did to make the code a bit more read-/understandable (in my opinion). Since, inside the method body, only elements from initialArray with an index larger than or equal to i are queried, and i doesn't serve any other purpose than to mark this index, I've eliminated i altogether and adjusted the recursive calls so that they only pass a sublist of the array with the relevant elements:

public Set<Set<Set<Integer>>> recurseGroups(List<Integer> integerList, List<Set<Integer>> currentGroups) {
    if (integerList.isEmpty()) {
        // ...
    }

    for (int j = 0; j < integerList.size(); ++j) {
        // ...
        Set<Integer> newGroup = new HashSet<>(Collections.singletonList(integerList.get(0)));
        currentGroups.add(newGroup);
        result.addAll(recurseGroups(integerList.subList(1, integerList.size()), currentGroups));
        currentGroups.remove(newGroup);

        // ...
        for (int k = 0; k < currentGroups.size(); ++k) {
            currentGroups.get(k).add(integerList.get(0));
            result.addAll(recurseGroups(integerList.subList(1, integerList.size()), currentGroups));
            currentGroups.get(k).remove(integerList.get(0));
        }
    }

    // ...
}

That way, no information that isn't needed enters the method, which makes it easier to understand its workings.

Also, the following line is really unnecessarily complicated:

Set<Integer> newGroup = new HashSet<>(Collections.singletonList(integerList.get(0)));

This creates a List that is never used again and serves no other purpose than to save one line of code. You might as well do this:

Set<Integer> newGroup = new HashSet<>();
newGroup.add(integerList.get(0));

Even with two lines, it still takes up less characters than the above version, and it doesn't do more than it needs to do, hence easier to read.

That's it, now I really have to go to sleep. Happy coding!


List objects in a Amazon S3 folder without also listing objects in sub folders I'm using the Amazon S3 Java SDK to fetch a list of files in a (simulated) sub-folder.  This code is rather standard (AWSConfiguration is a class that contains a bunch of account specific values):

String prefix = "/images/cars/";
int prefix_size = prefix.length();
AmazonS3 s3 = new AmazonS3Client(new AWSConfiguration());
ObjectListing objectListing = s3.listObjects(new ListObjectsRequest().
    withBucketName(AWSConfiguration.BUCKET).
    withPrefix(prefix));

Now this list will include objects like /images/cars/default.png as well as /images/cars/ford/Default.png (because they both contain the same prefix). To list only the objects that are directly inside the /images/cars/ "folder" I have the following function (in a class called S3Asset)

public static boolean isInsideFolder(int root_size, String key) {
  return (key.substring(root_size).indexOf("/") == -1);
}

This looks at the full key for any / after the prefix as a clue that it is inside a sub-folder.  This lets me iterate over the objects with the following code (I'm trimming the prefix for clarity):

for(S3ObjectSummary objectSummary : objectListing.getObjectSummaries()) {
  if(S3Asset.isInsideFolder(prefix_size, objectSummary.getKey())) {
    System.out.println(objectSummary.getKey().substring(prefix_size));
  }
}

As near as I can tell this is the cleanest way to do this but it has one characteristic that I don't like. If I'm looking a root level folder I'm requesting the names of all files in all sub-folders only to iterate over them and learn that there is only one object in the actual root level folder.  I've considered associating a key with the value being the full path of the folder, which would allow me to request objects with a predictable key instead of the prefix, but the major downside to this is that the key would have to be generated in code and therefor assets uploaded directly in to the S3 Bucket (through the management console) would not have this key.  Anyone have a better idea?

In the ListObjectsRequest javadoc there is a method called withDelimiter(String delimiter).  Adding .withDelimiter("/") after the .withPrefix(prefix) call then you will receive only a list of objects at the same folder level as the prefix (avoiding the need to filter the returned ObjectListing after the list was sent over the wire).

Some notes about the code:

1, I'd extract out to a local variable for the ListObjectsRequest instance:

final ListObjectsRequest listObjectRequest = new ListObjectsRequest().
    withBucketName(AWSConfiguration.BUCKET).
    withPrefix(prefix);
final ObjectListing objectListing = s3.listObjects(listObjectRequest);

It's easier to read.

2, root_size should be rootSize. (Regarding to the Java Coding Conventions.)

3, I would use String.contains instead of indexOf. It's more meaningful, easier to read since you don't have to use the -1 magic number.

4, In the last snippet I'd create a local variable for the key:

for (final S3ObjectSummary objectSummary: objectListing.getObjectSummaries()) {
    final String key = objectSummary.getKey();
    if (S3Asset.isImmediateDescendant(prefix, key)) {
        final String relativePath = getRelativePath(prefix, key);
        System.out.println(relativePath);
    }
}

5, Furthermore, I'd move the length call inside the helper method:

public String getRelativePath(final String parent, final String child) {
    if (!child.startsWith(parent)) {
        throw new IllegalArgumentException("Invalid child '" + child
            + "' for parent '" + parent + "'");
    }
    // a String.replace() also would be fine here
    final int parentLen = parent.length();
    return child.substring(parentLen);
}

public boolean isImmediateDescendant(final String parent, final String child) {
    if (!child.startsWith(parent)) {
        // maybe we just should return false
        throw new IllegalArgumentException("Invalid child '" + child
            + "' for parent '" + parent + "'");
    }
    final int parentLen = parent.length();
    final String childWithoutParent = child.substring(parentLen);
    if (childWithoutParent.contains("/")) {
        return false;
    }
    return true;
}

Note the input check. (Effective Java, Second Edition, Item 38: Check parameters for validity)

The multiple calls of length could look redundant and slow but premature optimization is not a good thing (see Effective Java, Second Edition, Item 55: Optimize judiciously). If you check the source of java.lang.String, you will find this:

/** The count is the number of characters in the String. */
private final int count;

...

public int length() {
    return count;
}

String is immutable, so it's easy to cache its length and JDK does it for you.


Solving for the zero of an arbitrary function This methods solves for the zero of an arbitrary function using the Bisection Method. It works as desired, but I want to know if the code can be improved or made more readable and if I'm properly dealing with the various error conditions that might arise.

/// <summary>
/// Finds the input value of a function such that the output is zero within the range of min and max
/// </summary>
/// <param name="function">The function to zero</param>
/// <param name="min">The lower bound of the "zero search"</param>
/// <param name="max">The upper bound of the "zero search"</param>
/// <param name="counter">The amount of iterations to convergence</param>
/// <param name="eps">Desired precision</param>
/// <returns>An input value such that 'function' returns 0 zero within the desired precision eps</returns>
public static double Zero(this Func<double, double> function, double min, double max, out int counter, double eps = .001) {
    double lowerBound = min,
        upperBound = max;
    counter = 0;
    double range = double.MaxValue;
    double tryIndex = double.MinValue;
    double tryEval = double.MinValue;
    while (Math.Abs(tryEval) > eps && counter < 10000) {
        counter++;
        range = upperBound - lowerBound;
        double maxEval = function(upperBound);
        double minEval = function(lowerBound);
        bool signMax = (maxEval > 0);
        bool signMin = (minEval > 0);
        if (signMax == signMin) {
            throw new Exception("Failed to converge");
        }
        tryIndex = lowerBound + (range / 2);
        tryEval = function(tryIndex);
        bool trySign = tryEval > 0;
        if (trySign == signMax) {
            upperBound = tryIndex;
        } else lowerBound = tryIndex;
    }
    return tryIndex;
}

Wall of declarations

double lowerBound = min,
    upperBound = max;
counter = 0;
double range = double.MaxValue;
double tryIndex = double.MinValue;
double tryEval = double.MinValue;

Nobody likes being greeted by a wall of declarations like that.  Let's see what can be done to reduce them.

lowerBound and upperBound merely rename the parameters.  You could just use min and max directly everywhere.

counter is strongly related to the loop.  You could write the loop as

for (counter = 0; Math.Abs(tryEval) > eps && counter < 10000; counter++)
{
    …
}

range is also local to the loop, and should be declared inside the loop.  It's also annoying that it's initialized on the 4th line of the function, redefined on the 9th line, and used 17th line. In fact, I wouldn't bother making a variable for it at all:

tryIndex = lowerBound + (min - max) / 2;

In general, you have a lot of expressions that don't need to be assigned to variables.

Loop structure

Initializing tryIndex and tryEval to double.MinValue is a code smell.  First of all, you should probably prefer double.NaN.  Secondly, it raises the question, under what circumstances might double.MinValue "leak" out as a result?  It's worth restructuring the program to avoid having those special values at all.

Restructuring the program will also reveal that there are two possible error conditions: failure to converge because the two endpoints evaluate to the same sign, and failure to converge because it took too many iterations.

public static double Zero(this Func<double, double> function, double min, double max, out int counter, double eps = .001)
{
    for (counter = 0; counter < 10000; counter++)
    {
        bool signMax = (function(max) > 0);
        if ((function(min) > 0) == signMax)
        {
            // Same sign
            throw new Exception("Failed to converge (same sign)");
        }

        double tryIndex = min + (max - min) / 2;
        double tryEval = function(tryIndex);
        if (Math.Abs(tryEval) <= eps)
        {
            return tryIndex;
        }
        else if ((tryEval > 0) == signMax)
        {
            max = tryIndex;
        }
        else
        {
            min = tryIndex;
        }
    }
    throw new Exception("Failed to converge (too many iterations)");
}


express-validator and promise chains Is this the correct way of chaining promises when it comes to express-validator? I am using express node and this is the endpoint for a get request

Something about it seems a bit messy, but I can't think of a cleaner way to do it.

function exitChain() {
  return Promise.reject();
}

function getUserByID(req, res) {

  const id = req.query.id;
  req.checkQuery('id', 'ID is not a number').isInt();

  const q = 'select * from users where user_id=$1';
  const p = [id];

  req.getValidationResult()
    .then(function(vRes) {
      if (!vRes.isEmpty()) {
        exitChain();
        return res.status(400).send('Validation Fail: ' + util.inspect(vRes.array()));
      }
    })
    .then(function() {
      pg.connect(postgresConfig)
        .then(function(client) {
          return client.query(q, p).execute();
        })
        .then(function(result) {
          result.client.done();
          return res.status(200).send(res.json(result.rows));
        })
        .catch(function(err) {
          console.log(err);
          return res.status(400).send('Error: ' + err);
        });
    })
    .catch(function(err) {
      console.log(err);
      return res.status(400).send('Error: ' + err);
    });
}

Normally, I'd start of modelling promise chains following the "happy path". Following that, you will almost always find your logic (therefore your promise chain) in a straight line. Any fail condition in the chain should be broken by returning a rejected promise, which then skips to the nearest fail callback (which might redeem it) or catch if nothing caught it midway.

For rejections, it's also advised to reject with an error object because 1) it makes sense to, 2) error-handling mechanisms will almost always expect an error object not a string, and 3) works well with async-await, which uses the try-catch mechanism, where catch expects an error object. Lastly, you can key off of the error object's data to know what status code to return. This versus having multiple ends within the chain.

Avoid hoisting variables to outer scopes unless needed. I'm referring to q and p. It's only used in the callback that does return client.query(q, p).execute();. It makes sense to put it in the callback because it's only used there, and there's no unnecessary operation if ever that callback is never reached.

Also, exitChain() does not work the way you think it works.

function getUserByID(req, res) {
  const id = req.query.id
  req.checkQuery('id', 'ID is not a number').isInt()

  req.getValidationResult().then(vRes => {

    // Do next async operation or fail depending on condition
    return vRes.isEmpty() ? pg.connect(postgresConfig) : Promise.reject(new Error('...'))

  }).then(client => {

    return client.query('select * from users where user_id=$1', [id]).execute()

  }).then(result => {

    result.client.done();
    return res.status(200).send(res.json(result.rows))

  }).catch(error => {

    // If anything fails, it all ends up here. The 400 could be replaced
    // depending on the error object data.
    res.status(400).send('Error: ' + error.message)

  })
}


Adding two values in a map, if they exist My code looks like imperative style code. I want to make my code more functional. How I can rewrite my program so it become functional style code?

    val _map = getMap();
    if(_map.contains(x) && _map.contains(y)) Right(_map(x) + _map(y))
    else if(_map.contains(x + y)) Right(_map(x + y))
    else if(!_map.contains(x)) Left("%d or %d not found".format(x, x + y))
    else if(!_map.contains(y)) Left("%d or %d not found".format(y, x + y))
    else Left("What is it?")

OK, so I taught myself a little scala and here is something a bit more functional than your example:

val _map = Map(1 -> 2, 2 -> 8, 4 -> 13 )

def pickSum(x:Int, y:Int): Either[String,Int] = {

  /* If the map contains the key k, return Right(value)
   * else return Left(key)
   */
  def pick(k:Int): Either[Int,Int] = {
    _map.get(k) match {
      case Some(v) => Right(v)
      case _ => Left(k)
    }
  }

  List(x, y) map { pick } match {
    case List(Right(a), Right(b)) => Right(a + b) // Two matching values: return the sum
    case l:List[Either[Int,Int]] => pick(x + y) match { // At least one failure: try  x+y
      case Right(i) => Right(i)  // x+y is in the map.  Return the value
      // Otherwise, return the list of keys not found in the map
      case e:Left[_,_] => Left( e :: l collect { case Left(i) => i } mkString("Not found in map: ", ",", "") )
    }
  }
}

Testing this in the Scala repl...

scala>  pickSum(1,2)
res0: Either[String,Int] = Right(10)

scala> pickSum(2,4)
res1: Either[String,Int] = Right(21)

scala> pickSum(2,3)
res2: Either[String,Int] = Left(Not found in map: 5,3)

scala> pickSum(1,3)
res3: Either[String,Int] = Right(13)

scala> pickSum(3,7)
res4: Either[String,Int] = Left(Not found in map: 10,3,7)

This does more or less what your code does; it either returns a Right() with the desired Integer value or a Left() containing a string explaining which keys could not be found in the map.  Personally, in the case of failure I had rather just return a Left containing a list of the failed keys, to be handled as some other part of the code saw fit.

The core function, here, is to look for a key in the map and either return the matching value wrapped in a Right() or, if there is no such key, the rejected key wrapped in a Left().  I went straight for Map.get rather than checking with .contains() because the former returns an Option, which allows more concise and expressive code.

You should notice that nowhere in the code do I re-assign a value (hell, I don't even create any vals, let alone vars).  Instead, I return a series of immutable collections, each one derived from the previous one.  This is one aspect of functional programming.

So...

List(x, y) map { pick }

This makes a list out of the given keys and then creates from that a list of the corresponding values or the rejected keys.  I then do some pattern matching

case List(Right(a), Right(b)) => Right(a + b)

If this matches, we have successfully retrieved two values.  Return the sum.  And we're done here.  Otherwise...

case l:List[Either[Int,Int]] => pick(x + y)

So this matches a list but doesn't care what it contains, because we know there was at least one failure or the previous match would have succeeded.  Matching all the permutations of failure in one line is less fragile than listing them all, if there's only one action to take.  So now we look for _map(x + y) and match the result...

case Right(i) => Right(i)

If this matches, _map(x + y) exists so we return it and that's it.  Otherwise...

case e:Left[_,_] =>

OK, (x + y) is not a valid key.  So what the rest of that line does is

Adds Left(x + y) to the head of the list: e :: l
Collects all the invalid keys from the list: collect { case Left(i) => i }
Builds a string containing the invalid keys: mkString
Wraps the resulting string in a Left()

I'm sure this could be done better, since I only learned enough Scala to do this in the last 24 hours.  However, it is (like Yuushi's answer) more idiomatic while also using some functional programming techniques (however modestly).

To genuinely improve my example code, it would help to know why you're doing this slightly odd thing.

To summarise the differences between your example and mine:

All the else if statements make yours very fragile.
Each individual else if statement is almost the same (i.e. using _map.contains()), giving room for error with all that duplication.
You could easily miss a permutation.
You might (in fact you do) have code paths that can never be evaluated.
I avoid duplication almost entirely.
Pattern matching makes it almost certain I catch all the permutations.


Google Code jam puzzle - Welcome to Code Jam The problem is to count all possible sub-sequences of "welcome to code jam" in a given input string (and only return the last 4 digits of the count).  Here is the link to the problem for reference.

I've implemented a solution in Haskell that worked fine on the examples and small datasets but failed on the large data set. Here is the code:

I'm interested in correctness first. (Am I missing some corner case?) I guess performance can be improved by memoization; and I'd be happy get any other tips on that front too.

w_s is short for welcome_solve: This calculates the total number of sub-sequences.

w_s x [] = 0
w_s (x: []) str_xs = length ( filter (\z -> z==x) str_xs )
w_s (x:xs) (str_x:str_xs) = if x==str_x
                            then (w_s xs str_xs)  + (w_s (x:xs) str_xs)
                            else w_s (x:xs) str_xs

And here is the code to get the last 4 digits:

getLast4 (w:x:y:z: []) = [w,x,y,z]
getLast4 (x:xs) = getLast4 xs
format_solve problem
         | solution < 1000 = getLast4 $ show $ 10000 + solution
         | otherwise  = getLast4 $ show solution
         where solution = w_s "welcome to code jam" problem

Example usage:

λ> format_solve "format_solve welcome to codejam"
"0000"
λ> format_solve "wweellccoommee to code qps jam"
"0256"
λ> format_solve "elcomew elcome to code jam"
"0001"

w_s, short for "welcome_solve", is, frankly, a poor name.  You're writing a function that counts the number of subsequences.  It's not even restricted to operating on strings.  Why not call it countSubsequences?

countSubsequences :: Eq a => [a] -> [a] -> Int

Your base cases should be simpler.

countSubsequences [] _ = 1
countSubsequences _ [] = 0

The recursive case is correct, but could be written more clearly with a more idiomatic convention for parameter names, and using guard clauses.

countSubsequences needle@(n:ns) haystack@(h:hs)
  | n == h    = countSubsequences needle hs + countSubsequences ns hs
  | otherwise = countSubsequences needle hs


Formatting uptime as a human-friendly time interval # extend Time class for readable method
class Time
  def readable
    case uptime
    when 0 then 'just now'
    when 1 then 'uptime second ago'
    when 2..59 then uptime.to_s + ' seconds ago'
    when 60..119 then 'uptime minute ago' # 120 = 2 minutes
    when 120..3540 then (uptime / 60).to_i.to_s + ' minutes ago'
    when 3541..7100 then 'an hour ago' # 3600 = 1 hour
    when 7101..82_800 then ((uptime + 99) / 3600).to_i.to_s + ' hours ago'
    when 82_801..172_000 then 'uptime day ago' # 86400 = 1 day
    else ((uptime + 800) / 86_400).to_i.to_s + ' days ago'
    end
  end

  private

  def uptime
    (Time.now - self).to_i
  end
end

Linter raises the following warnings. How can this be fixed?

TooManyStatements: Time#readable has approx 10 statements [https://github.com/troessner/reek/blob/master/docs/Too-Many-Statements.md]
Assignment Branch Condition size for readable is too high. [22.47/15]
Cyclomatic complexity for readable is too high. [9/6]
Method has too many lines. [11/10]

Bearing in mind that a linter can only look at how the code is written and not at what it's actually doing, switch statements (or the equivalent case as with Ruby) that don't do much are completely fine.

A switch that tests many conditions is bound to be long-ish, there's not much you can do there. Every one of the warnings you get is a direct consequence of the fact that you're testing 8 values.

I would say this is one prime example of a situation in which you just don't waste your time in an attempt to make the linter happy. Extracting methods is going to clutter things up and look dumb.

The only viable option that I can think of right now is sticking those ranges along with their readable description in some kind of hash, and retrieving the value from there. But it's a compromise, really: if this method gets called often, you could be instantiating yet another object at each call.

I say you just ignore what the linter says in situations like this, or adjust its default settings to make it less bitchy.

Your method is fine, the intent is very clear to me, and it's not doing anything complicated. Don't get all caught up in an attempt to please a tool that doesn't understand your code to begin with.


Find numbers that are both Triangle numbers and Square numbers I've written a simple JavaScript function to find numbers that contain both the attributes of a Triangle (\$ n(n+1)/2 = x \$) and a Square (\$ n^2 = x \$) number.
The challenge was given in Matt Parker's Things to Make and Do in the Fourth Dimension.

function main() {
  for (var i = 1; i < 1000000; i++) {
    var triangled = ( i * ( i + 1 ) ) / 2;
        if(Math.sqrt(triangled) % 1 === 0) {
         // print
      }
  }
}

Here's the JSFiddle of the same.

The algorithm n = 1000000 takes about ~35ms but gets considerably slower with higher values

~300ms for n = 10000000

~3000ms for n = 100000000

The only priority is performance. Any tips?

First, I tried to be mathematically clever (by trying something with the odd and evenness of triangular and square numbers). That resulted in me making a mistake and getting a bogus result.

Then I took a good look at your code. You are calling Math.sqrt for every iteration. That's really slow, so if we could work around that, it'd be a huge performance boost. And we can work around it, by keeping track of the next target to hit.

Additionally, if we're gonna pass every integer anyway, why don't we add them as we go, rather than constantly recalculation triangle? A triangular number consists of all the whole positive integers at or below N, so by simply summing as we go, we can keep a calculated triangular number in memory without the need to recalculate every iteration.

The resulting code...

function main() {
var timer = Date.now();
  var triangleSum = 0;
  var productCounter = 1;
  var product = 1;
  for (var i = 1; i < 100000000; i++) {
    triangleSum += i;
    if(triangleSum === product)
    {
        document.getElementById('log').innerHTML += '
' + Math.sqrt(triangleSum)+ ' and ' + i + ': ' + triangleSum + '
';
    }
    if(triangleSum >= product)
    {
        productCounter++;
        product = productCounter * productCounter;
    }
  }
  document.getElementById('log').innerHTML += '
Time taken: ' + (Date.now() - timer) + ' milliseconds
';
}

Runs in 380 ms compared to the 5346 ms it was giving me before.


Ensuring array of worksheets are present I have a sub which should only continue running if 4 specific worksheets are present. From online reading, such as @Tim Williams's comment in Test or check if sheet exists, I know that using an error thrown, to determine a course of action, can be frowned upon, but I found similar usage to mine in both that question and here.

Here is a simplified version:

Private Sub Test()

 If AllSheetsPresent Then MsgBox "Doing something"

End Sub

Private Function AllSheetsPresent() As Boolean

  AllSheetsPresent = True

  Dim SheetsArr()

  On Error GoTo errhand
  SheetsArr = ThisWorkbook.Sheets(Array("Response Times", "Incidents", "Calls", "Resources", "NoC, CPR"))

  Exit Function

errhand:
  If Err.Number = 9 Then
      AllSheetsPresent = False
      MsgBox "Sheets are missing from..."
      End
  End If

End Function

Notes:

For the purposes of testing I am using ThisWorkbook. It would otherwise be a workbook variable passed to the function.

Questions:

Is there a better way to perform this validation?
Related to 1) are there any risks associated with this approach I should be aware of?
If AllSheetsPresent Then MsgBox "Doing something" feels in some way superfluous as if False the code has stopped anyway. Again, this feels like an extension of 1) can this be re-written in a better way?

As this is working code I have posted here in the hope it is the right place to ask.

There are no risks because you are trapping the errors.

A better way to write the code would be to pass the target Workbook and the array of Sheets into the function for testing.  In the Function itself use On Error Resume Next to turn off the Error notification, Err.Number <> 0 to test if an Error was thrown, and On Error Goto 0 to reset any Errors.  I would also log the missing Sheets to the Immediate Window.

If you need to this pattern often, consider saving it in your Personal Macro Workbook.

Private Sub Test()
    Dim SheetsArr As Variant
    SheetsArr = Array("Response Times", "Incidents", "Calls", "Resources", "NoC, CPR")
    If AllSheetsPresent(ThisWorkbook, SheetsArr) Then MsgBox "Doing something"
End Sub

Private Function AllSheetsPresent(WB As Workbook, SheetsArr As Variant) As Boolean
    Dim msg As String, sh As Variant
    For Each sh In SheetsArr
        On Error Resume Next
        Set sh = WB.Sheets(sh)
        If Err.Number <> 0 Then msg = msg & sh & vbCrLf
        On Error GoTo 0
    Next

    If Len(msg) > 0 Then
        msg = Left(msg, Len(msg) - 1) 'Remove the last line return vbCrLf
        Debug.Print "These Sheets are not in " & WB.Name & ": " & Replace(msg, vbCrLf, ", "); ""

        msg = "These Sheets are not in " & WB.Name & vbCrLf & msg
        MsgBox msg, vbCritical, "Missing Sheets"
    Else
        AllSheetsPresent = True
    End If
End Function


Graham Scan Algorithm in Haskell I have just begun learning functional programming and Haskell.

This is my attempt to implement a solution to Graham Scan Algorithm in Haskell. Note that I am not even sure if this is indeed Graham Scan Algorithm, since I implemented this solution with only a few hints of the actual Graham Scan Algorithm. But I believe it to be correct and to have a \$\mathcal O\left(n \log(n)\right)\$ time complexity. However, I am still not quite there yet when it comes to understanding Lazy Evaluation, so not sure if it is indeed \$\mathcal O\left(n \log(n)\right)\$.

data Direction = LeftTurn | RightTurn | Straight deriving (Show, Eq)

findDirBetter (x, y) (x1, y1) (x2, y2)
    | cros_product == 0 = Straight
    | cros_product > 0  = LeftTurn
    | cros_product < 0  = RightTurn
   where cros_product = (x1 - x) * (y2 - y1) - (y1 - y) * (x2 - x1)

convex_hull_find []           = []
convex_hull_find (x:[])       = x:[]
convex_hull_find (x:x1:[])    = x:x1:[]
convex_hull_find (x:x1:x2:[]) = x:x1:x2:[]
convex_hull_find a            = (find_half_hull (tail sorted_x) [head sorted_x]) ++ (find_half_hull (tail (reverse sorted_x)) [head (reverse sorted_x)])
        where sorted_x                    = sortBy predicate a
              predicate (x, y) (x1, y1)   = compare x x1
              find_half_hull ([]) hull    = tail hull
              find_half_hull l (x:[])     = find_half_hull (tail l) ((head l):x:[])
              find_half_hull l hull       = if findDirBetter (head (tail hull)) (head hull) (head l) /= RightTurn
                                            then find_half_hull (tail l) ((head l):hull)
                                            else find_half_hull l (tail hull)

Please critique everything from the algorithm to the code.

Is this Graham Scan Algorithm?
Is it \$\mathcal O\left(n \log(n)\right)\$?
Is this elegant, readable Haskell code?

Is this Graham Scan Algorithm? Is it O(n log n)?

Yes, it is.

  Is this elegant, readable Haskell code?

No. It's buggy and far from elegant. Let's start with the bugs in convex_hull_find:

          convex_hull_find []           = []
          convex_hull_find (x:[])       = x:[]
Bug 1:    convex_hull_find (x:x1:[])    = x:x1:[]
Bug 2:    convex_hull_find (x:x1:x2:[]) = x:x1:x2:[]
          convex_hull_find a            = (find_half_hull (tail sorted_x) [head sorted_x]) ++ (find_half_hull (tail (reverse sorted_x)) [head (reverse sorted_x)])
Bug 3:      where sorted_x                    = sortBy predicate a
                  predicate (x, y) (x1, y1)   = compare x x1
                  find_half_hull ([]) hull    = ...

The first bug is simple and obvious: for non-unique inputs like [(0,0),(0,0)], the convex hull should be [(0,0)], but the input is returned verbatim. Non-unique inputs of arbitrary length are also handled improperly. The second bug arises from reordering inputs of length three. Obviously, [p1, p2, p3] (counterclockwise triangle), [p3, p2, p1] (clockwise) and [p2, p3, p1] (different starting point) should all result in the exact same convex hull, namely the counterclockwise triangle [p1, p2, p3] that starts with the lowest-sorting point.

To fix the first bug, just ensure the input is sorted and unique before you do any processing, even in case of short-circuit evaluation. The second bug can be fixed by removing the special case for inputs of length three, there is no need for it anyway. Also, replace head and tail by last and init so the lowest-sorting point stays in the first position for arbitrary-length inputs.

The third bug is a bit more tricky: if two points have the same x-coordinate, sorting by x is insufficient to find the starting point. You need to brake ties by y. Luckily, that's how Haskell orders tuples by default, so just replace sortBy predicate a by sort a. The input [(1,1),(1,0),(2,0),(1,2),(0,0)] triggers the faulty behavior.

Below is a corrected version of the function, complete with type annotations and a docstring. I renamed find_half_hull to grahamScan and made it a first-order citizen to improve readability. Note that function names in Haskell are camelCase by convention, not snake_case.

convexHull :: (Num a, Ord a) => [(a,a)] -> [(a,a)]
-- ^ Convex hull in two dimensions.
convexHull points
  | length sorted <= 2 = sorted
  | otherwise = init (grahamScan sorted) ++ init (grahamScan $ reverse sorted)
  where sorted = map head $ group $ sort points

In addition to renaming find_half_hull to grahamScan, I split it in two separate, simple functions and slapped a docstring to each. They are defined as follows:

grahamScan :: (Num a, Ord a) => [(a,a)] -> [(a,a)]
-- ^ Performs a Graham scan on an ordered list of unique points.
grahamScan = foldr push []
  where push point stack = grahamEliminate (point:stack)

The first of those, grahamScan, simply pushes points onto a stack one by one (starting with the last) and calls grahamEliminate on each iteration. The latter tests if the top three point form a counterclockwise triangle and removes points as appropriate.

grahamEliminate :: (Num a, Ord a) => [(a,a)] -> [(a,a)]
-- ^ Pops second-to-top element from a stack if top three elements do
--   not form a counterclockwise triangle. Repeats if necessary.
grahamEliminate (p1:p2:p3:stack)
  | doubleArea p1 p2 p3 <= 0 = grahamEliminate (p1:p3:stack)
grahamEliminate stack = stack

Finally, the following code can be replaced by a one-liner. Just leave it to the caller to test the sign, it's easier than to test for your custom type.

data Direction = LeftTurn | RightTurn | Straight deriving (Show, Eq)

findDirBetter (x, y) (x1, y1) (x2, y2)
    | cros_product == 0 = Straight
    | cros_product > 0  = LeftTurn
    | cros_product < 0  = RightTurn
    where cros_product = (x1 - x) * (y2 - y1) - (y1 - y) * (x2 - x1)

The complete code is then:

import Data.List

convexHull :: (Num a, Ord a) => [(a,a)] -> [(a,a)]
-- ^ Convex hull in two dimensions.
convexHull points
  | length sorted <= 2 = sorted
  | otherwise = init (grahamScan sorted) ++ init (grahamScan $ reverse sorted)
  where sorted = map head $ group $ sort points

grahamScan :: (Num a, Ord a) => [(a,a)] -> [(a,a)]
-- ^ Performs a Graham scan on an ordered list of unique points.
grahamScan = foldr push []
  where push point stack = grahamEliminate (point:stack)

grahamEliminate :: (Num a, Ord a) => [(a,a)] -> [(a,a)]
-- ^ Pops second-to-top element from a stack if top three elements do
--   not form a counterclockwise triangle. Repeats if necessary.
grahamEliminate (p1:p2:p3:stack)
  | doubleArea p1 p2 p3 <= 0 = grahamEliminate (p1:p3:stack)
grahamEliminate stack = stack

doubleArea :: Num a => (a,a) -> (a,a) -> (a,a) -> a
-- ^ Twice the area of a counterclockwise triangle. Negative if clockwise.
doubleArea (x1,y1) (x2,y2) (x3,y3) = (x2-x1) * (y3-y1) - (y2-y1) * (x3-x1)


Triaging items according to a time threshold I'm having this part of code which I want to make smaller, more readable and easy to manage. Any thoughts? I tried linq but got lost.

foreach (var o in state.s)
        {
            TimeSpan timeDiff = (DateTime.Now - o.time);
            if (timeDiff.TotalSeconds < 300)
            {
                richTextBox.AppendColoredText(o.name + " ", Color.Green);
            }
            else
            {
                richTextBox.AppendColoredText(o.name + " ", Color.Red);
                if (f == false)
                {
                    listA.Add(o.name);
                    listA_clone.Add(o.name);
                }
                else
                {
                    listA.Add(o._name);
                }
            }
        }

I tried linq but got lost.

LINQ stands for Language-INtegrated Query - and querying objects (or data) is not something that should have side-effects... and the very purpose of that loop is to have side-effects. In other words, using LINQ here would be abusing the language.

Your usage of var is inconsistent, and the naming is... dangerous - I like var, a lot. So I like that you're having it in your loop declaration. You see, I can guess that timeDiff is a TimeSpan just by looking at its name - and its assignment makes it pretty obvious what the type is as well. But I have no clue whatsoever what an o is, and all I know about s is that it's probably an IEnumerable<whatever-the-type-of-o-is>. Readable code is code that one can... read.

o.time and o.name are confusing, because they don't follow the typical PascalCase naming convention for public members. If they're public property getters, they should be o.Time and o.Name.

o._name is confusing at best, and a clear violation of encapsulation at worst. _name looks very much like a name for a private field - which shouldn't be accessible from this code. And if it's a public field, then you've broken encapsulation (because fields should never be public). And if _name isn't the backing field for the name property, then you have another problem: you clearly aren't writing code as if the next maintainer were a violent psychopath that knows where you live:

listA.Add(o.name);
...
listA.Add(o._name);

Another thing to note, is that the Boolean expression in an if condition doesn't need to involve a comparison against a Boolean value here:

if (f == false)

if f is a bool, then if (!f) is a Boolean expression... that would be perfectly clear if f had a meaningful name. By convention bool variable names start with is, or has:

if (!isHairyCode)

or

if (!hasBugs)


C# Regex to extract bug ID from Bugzilla JSON response I have written a series of Regex.Replace() lines to take an input like {"id":36} and convert it to id 36 and I was wondering if it is possible to combine all the calls I am making into one.

Results = Regex.Replace(Results, @"\{", "");
Results = Regex.Replace(Results, @"\}", "");
Results = Regex.Replace(Results, @"\""", "");
Results = Regex.Replace(Results, @"\:", " ");

I have done some experimentation but because have not figured out how to tell it "Find the { then the } and drop only those but keep the text in between".

Here is my full code block:

[Route("test")]
public async Task<string> Test()
{
    Dictionary<string, string> BugData = new Dictionary<string, string>
    {
            { "Bugzilla_api_key", "Removed For Security" },
            { "product", "Test" },
            { "component", "Test Component" },
            { "version", "unspecified" },
            { "summary", "App API Test" },
            { "op_sys", "All" },
            { "platform", "Other" },
            { "description", "A basic API test" }
    };

    string Json = JsonConvert.SerializeObject(BugData, Formatting.None);
    var Client = new HttpClient();
    var Request = new HttpRequestMessage(HttpMethod.Post, "http://bugzilla-tools/rest/bug");
    Request.Content = new StringContent(Json, Encoding.UTF8, "application/json");
    Request.Headers.Add("Accept", "application/json");
    var Response = await Client.SendAsync(Request);
    var Results = await Response.Content.ReadAsStringAsync();
    Results = Regex.Replace(Results, @"\{", "");
    Results = Regex.Replace(Results, @"\}", "");
    Results = Regex.Replace(Results, @"\""", "");
    Results = Regex.Replace(Results, @"\:", " ");

    if (Response.StatusCode == HttpStatusCode.OK)
    {
        return Results;
    }
    else
    {
        return "Error Logging to Bugzilla";
    }
}

The overall goal for this (which is working now). Is to pass data to BugZilla to log exceptions from the app as bugs, get the new bug ID and pass that up to an error page which will read something like "An error was encountered processing you request. This error has been logged with the bug ID 36" (Where ID 36 would be what this task passes up to the error page).

I am using the Regexes to make the returned string more readable, as trying to deserialize it with NewtonSoft would produce the error:

  JsonSerializationException: Cannot deserialize the current JSON object (e.g. {"name":"value"}) into type 'System.Collections.Generic.List`1[System.String]' because the type requires a JSON array (e.g. [1,2,3]) to deserialize correctly.
   To fix this error either change the JSON to a JSON array (e.g. [1,2,3]) or change the deserialized type so that it is a normal .NET type (e.g. not a primitive type like integer, not a collection type like an array or List) that can be deserialized from a JSON object. JsonObjectAttribute can also be added to the type to force it to deserialize from a JSON object.
   Path 'Bugzilla_api_key', line 1, position 20

From the code:

var T = JsonConvert.DeserializeObject<List<string>>(Json);
Results = string.Concat(T[0], " ", T[1]);

You want to say "any of these characters", so what you want is a character class.

However, if your task is actually to extract a key and value out of JSON, the right tool to use is not a string replacement hack, but a JSON parser.

In this case, the problem with

JsonConvert.DeserializeObject<List<string>>(Json)

… is that you're telling it to parse a key-value pair as a list.  What you want to do is deserialize a dictionary:

JsonConvert.DeserializeObject<Dictionary<string, int>>(Json)

Note that you should check the HTTP status code before trying to process the body of the result.


Stripping out all /* */ comments from a paragraph I've written this code keeping the following cases in mind and I think I've covered them all. I'd really appreciate if someone could help me determine if I've covered all of them.

Cases I considered:

No comments at all
Text /* Text */ Text
Text /* Text */ Text /* Text */
Text /* /* Text */ */ Text
Text /* /* Text */ Text
Text /* Text
Text */ Text

private static String stripComments(final String input) {
    StringBuilder builder = new StringBuilder();
    boolean startSeen = false;

    for (int i = 0; i < input.length();) {
        int moveAheadBy = 1;

        if (startSeen) {
            if (input.charAt(i) == '*' && (i != input.length() - 1 && input.charAt(i + 1) == '/')) {
                startSeen = false;
                moveAheadBy = 2;
            }
        } else {
            if (input.charAt(i) == '/' && (i != input.length() - 1 && input.charAt(i + 1) == '*')) {
                startSeen = true;
                moveAheadBy = 2;
            } else {
                builder.append(input.charAt(i));
            }
        }
        i += moveAheadBy;
    }

    return builder.toString();
}

You didn't specify whether or not nested comments are allowed, but your code trims only the shorter comment. For example, case 4 would yield Text  Text with nesting but Text  */ Text without. It would be helpful to include some unit tests to demonstrate the intent.

Your solution is pretty straight-forward with only one real complication. I would remove the moveAheadBy incrementer and instead perform an extra increment where you're setting moveAheadBy to 2. It's minor, but it removes unnecessary state.

To help with the readability, introduce a variable for the length of the input since it's used in so many places.

Another solution would be to use indexOf to seek ahead to the next open/close. The algorithm will still be \$O(n)\$, but the fewer number of append calls could add up with very, very long strings. This is more to show an alternate method than to improve on yours.

public static String stripComments(final String input) {
    StringBuilder buf = new StringBuilder();
    int current = 0;
    int end = input.length();

    while (current < end) {
        int nextOpen = input.indexOf("/*", current);
        if (nextOpen == -1) {
            // no more comments
            buf.append(input.substring(current));
            break;
        }
        buf.append(input.substring(current, nextOpen));
        int nextClose = input.indexOf("*/", nextOpen + 2);
        if (nextClose == -1) {
            // final comment not closed
            break;
        }
        current = nextClose + 2;
    }

    return buf.toString();
}

Unit Tests

Now that the method is public, let's add some tests.

@Test
public void testNone() {
    assertThat(stripComments("No comments at all"), is("No comments at all"));
}

@Test
public void testSingle() {
    assertThat(stripComments("Single /* foo */ comment"), is("Single  comment"));
}

@Test
public void testDisjoint() {
    assertThat(stripComments("Two /* foo */ disjoint /* bar */ comments"), is("Two  disjoint  comments"));
}

@Test
public void testNested() {
    assertThat(stripComments("Two /* foo /* nested */ baz */ comments"), is("Two  baz */ comments"));
}

@Test
public void testUnclosed() {
    assertThat(stripComments("Unclosed /* foo comment"), is("Unclosed "));
}

@Test
public void testUnopened() {
    assertThat(stripComments("Unopened */ comment"), is("Unopened */ comment"));
}


Testing whether lambda expression returns true for any list element I have the following function defined in my .emacs to test if a given executable exists within my $PATH. I implemented it with cl-reduce and the code looks really unidiomatic (to me).

(defun executable-in-path-p (executable)
  "Test if EXECUTABLE exists in path."
  (eq t (cl-reduce
         (lambda (path exists)
           (or (file-exists-p (concat (file-name-as-directory path) executable))
               exists))
         exec-path)))

Is there a more concise way to test if a list, mapped with a predicate function, has at least one element equal to t than this?

(eq t
    (cl-reduce
     (lambda (element acc)
       (or (some-check-p element)
           acc))
     some-list))

In Ruby for example I would write:

some_list.any? { |element| some_check(element) }

If you already have Common Lisp-derived functions in there, use CL-SOME instead:

(defun executable-in-path-p (executable)
  "Test if EXECUTABLE exists in path."
  (cl-some (lambda (path) (file-exists-p (concat (file-name-as-directory path) executable))) exec-path))

That's of course a little bit different than explicitly checking for t, but you shouldn't be doing that anyway in most cases (everything but nil is already true).


Daily SQL job to delete records older than 24 hours Below is a delete job to delete 1M+ records daily and takes 13 hours to complete and sometimes more than that. I need to optimize this.

  The table tblcalldatastore is being inserted 24*7 through a stored
  procedure and is supposed to have no records older than 24 hours.

Execution plan is below.

https://www.brentozar.com/pastetheplan/?id=ryYi2Sv7B

BEGIN

SET NOCOUNT ON;

DECLARE @DELETECOUNT int
DECLARE @DELETEATATIME int

DECLARE @CutOffDate datetime
DECLARE @HourRetained smallint
set @HourRetained = 24
begin Try

set @CutOffDate = getutcdate()

select  @DELETECOUNT = count(*) from [tblcalldatastore]
where  istestcase=0
and datediff(hour,receiveddate,@CutOffDate)>@HourRetained

SET @DELETEATATIME = 20000

WHILE @DELETECOUNT > 0

BEGIN

DELETE TOP(@DELETEATATIME) FROM tblcalldatastore WITH (ROWLOCK)  WHERE IsTestCase=0 and datediff(hour,receiveddate,@CutOffDate)>@HourRetained

SET @DELETECOUNT = @DELETECOUNT - @DELETEATATIME

END

end try

BEGIN CATCH

SELECT 'FAILED - ' + ERROR_MESSAGE() AS ErrorMessage

END CATCH

END

From Comments

Have you tested performance of copying data of a single day to a temporary table, truncating the target table, and re-inserting the copied data back to the target table?

  Yes, it's not taking much time to copy or insert, it is taking time to delete and select. One of the column has huge XML string.

Proposed Solution

Since inserting and copying data does not seem to yield a performance penalty, I would suggest to:

copy to data of today to a staging table
truncate the existing table (much faster than delete, no transaction logs)
copy staged data back to existing table

Or alternatively, as Dannnno suggests:

Potentially faster than copying the data twice would be to copy data to a staging table, truncate the existing table, then rename them both to swap places. This minimizes latches required for DDL, and also only requires a single copy. Snapshot isolation would also help this be as non-invasive as possible for anyone hitting the database.

Links

Similar problem: non-clustered index bottleneck on delete
Enlists a couple of possible solutions


If/else produce code duplication I have the following class:
public class UpdateData {

    public static boolean updateHasMessage(Update update) {
        return update.hasMessage() && update.getMessage().hasText();
    }

    public static boolean updateHasCallbackQuery(Update update) {
        return update.hasCallbackQuery() && (update.getCallbackQuery().getData()!= null);
    }

    public static Long getChatId(Update update) {
        if (updateHasMessage(update)) {
            return update.getMessage().getChatId();
        }
        else if (updateHasCallbackQuery(update)) {
            return update.getCallbackQuery().getMessage().getChatId();
        }
        else {
            return null;
        }
    }

    public static String getUserName(Update update) {
        if (updateHasMessage(update)) {
            return update.getMessage().getFrom().getUserName();
        }
        else if (updateHasCallbackQuery(update)){
            return update.getCallbackQuery().getFrom().getUserName();
        }
        else {
            return null;
        }
    }

    public static String getInputUserData(Update update) {
        if (updateHasMessage(update)) {
            return update.getMessage().getText();
        }
        else if (updateHasCallbackQuery(update)){
            return update.getCallbackQuery().getData();
        }
        else {
            return null;
        }
    }

    public static String getCallBackId(Update update) {
        return update.getCallbackQuery().getId();
    }

    public static Integer getMessageId(Update update) {
        if (updateHasMessage(update)) {
            return update.getMessage().getMessageId();
        }
        else if (updateHasCallbackQuery(update)){
            return update.getCallbackQuery().getMessage().getMessageId();
        }
        else {
            return null;
        }
    }

    public static String getCallBackData(Update update) {
        return update.getCallbackQuery().getData();
    }
}

As you can see I have similar block code in most methods:
if (updateHasMessage(update)) {
    ...
}
else if (updateHasCallbackQuery(update)) {
    ...
}
else {}

They return unique information and have various stuff inside, but this is very similar to code duplication.
Do I need to rewrite this or just stay with it? If need to rewrite, then how?
UPDATE
Update is a Telegram API object.

Keep it like that. It is perfectly readable, easy to understand, everything is fine.
Naturally you could do some lambda trickery along the lines of:
public static String extractFromMessageOrQuery(
       Update update,
       Function<Update, String> messageExtractor,
       Function<Update, String> queryExtractor,
       String defaultValue) {
   if (updateHasMessage)
       return messageExtractor.apply(update);
   else if (updateHashCallbackQuery(update))
       return queryExtractor.apply(update);
   return defaultValue;
}

public static String getInputUserData(Update update) {
    return extractFromMessageOrQuery(
        upd -> upd.getMessage().getText(),
        upd -> upd.getCallbackQuery().getData(),
        null
    );
}

But: would that make the code

easier to understand? No
easier to extend? No
easier to maintain? No

Thus: take note that these possibilities exist, and keep the code as-is.


String Queue implementation Is the implementation clean enough & can be used in production?
I tried to write clean & bug-free code. It looks good to me.

I would appreciate any improvement suggestions.

One question I have is, what are the corner cases one might need to consider while implementing a Queue like this that might be part of a 3rd party library?

  I am aware of the build-in C# Queue type. In production obviously that's what I would use

using System;

internal class Queue
{
    private System.String[] _container;
    private System.Int32 _topHook = 0;
    private System.Int32 _downHook = 0;

    public Queue(System.Int32 capacity = 5)
    {
        _container = new System.String[capacity];
    }

    public bool IsEmpty() => Count == 0;

    public System.Int32 Count { get { return _topHook - _downHook; } }

    public void Enqueue(System.String item)
    {
        if(Count == _container.Length) ReSize(Count * 2);
        _container[_topHook++] = item;
    }

    public System.String Dequeue()
    {
        if(IsEmpty()) throw new Exception("No Element In Queue");
        if(Count == _container.Length / 4) ReSize(Count * 2);

        var dequeuedValue = _container[_downHook++];

        _container[_downHook - 1] = null;

        return dequeuedValue;
    }

    private void ReSize(System.Int32 capacity)
    {
        System.String[] container = new System.String[capacity];
        var j = 0;

        for(var i = 0; i < _container.Length; i++)
            if(_container[i] != null)
                container[j++] = _container[i];

        _container = container;
        _topHook = Count;//_topHook will point to the NEXT element
        _downHook = 0;
    }

}

using System;

If you're going to say using System then don't be putting lots of System.s in the file; the point of this is to eliminate those.

internal class Queue

Is the class intended to be subclassed? If not, seal it. You can always unseal it later if you need to design it for extension.

Why do you not implement IEnumerable<string> ? Surely one of the primary use cases of a collection is enumerating it.

There is nothing in here that is specific to strings; it would be just as easy to write Queue<T>.

private System.String[] _container

Using System.String, System.Int32 and so on is legal, but not idiomatic in C#. Use string, int, and so on.

public Queue(System.Int32 capacity = 5)

What led you to believe that 5 is the correct number here? The maintenance programmer in the future will want to know what the consequences are of changing it to 10 or 1 or a million. Document the things that are not obvious from the code, and avoid "magic numbers".

public bool IsEmpty() => Count == 0;

This could be a property.

    if(Count == _container.Length) ReSize(Count * 2);
    _container[_topHook++] = item;

You might consider making a private property Capacity:

private int Capacity => _container.Length;

And now your code reads better.

if(Count == Capacity) ReSize(Count * 2);

Remember, keep your code in the business domain as much as possible. The length of the container is a mechanism.

Use assertions to document your invariants. That way if you break them, you get informed in your tests:

    Debug.Assert(Count <= Capacity); // precondition of resize
    if(Count == Capacity)
      ReSize(Count * 2);
    Debug.Assert(Count < Capacity); // postcondition of resize

Do this throughout; any invariant you can think of, document it with an assertion. Like, the count goes up when you enqueue and down when you dequeue, and so on.

Now, of course, this code is still completely wrong.

Suppose the array length is 5, top is 0, bottom is 0.  We enqueue four strings, so top is 4, bottom is 0. Now we dequeue. Top is 4, bottom is 1.  Now we enqueue. Follow your logic:

count is 4 - 1 = 3
3 is not 5, so no resize
top increments to 5

Now we enqueue again

count is 5 - 1 = 4
4 is not 5, so no resize
and we dereference container[5], which is out of bounds.

Do you see your bug here?

The problem is that the condition you are attempting to avoid -- dereferencing out of bounds -- and the condition you are checking -- count vs capacity -- have nothing to do with each other. The code should be:

    Debug.Assert(_topHook <= _container.Length);
    Debug.Assert(Count <= Capacity);
    if (_topHook == _container.Length)
      ReSize(Count * 2);
    Debug.Assert(Count < Capacity);
    Debug.Assert(_topHook < _container.Length);
    _container[_topHook++] = item;

    _container[_topHook++] = item;

I understand that C programmers like this sort of thing. I don't. A line of code should have one effect, and this one has two, and requires that you correctly reason about the ordering of effects.  Write the code so that it is crystal clear:

    _container[_topHook] = item;
    _topHook += 1;
    Debug.Assert(_topHook <= _container.Length);
    Debug.Assert(Count <= Capacity);

if(IsEmpty()) throw new Exception("No Element In Queue");

Don't use Exception as anything but a base class in production code. This could be an invalid operation exception, or make your own exception.

    if(Count == _container.Length / 4) ReSize(Count * 2);

The logic here is correct, but is nowhere documented. The logic is: we wish to maintain two properties, first, that there is never more than a ratio of three to one for wasted space to used space, and second, that there is never a sequence of enqueue-dequeue or dequeue-enqueue operations that both cause an expensive resize. Give a justification here for why and how this logic maintains those invariants.

Consider also: who cares if we are "wasting" in a 4:1 ratio in the case where we have capacity 5 and count 1 ?  Resizing the array to size 2 in this case is a waste of time.  Consider taking a more sophisticated approach for small queues. Abstract the decision of whether to resize, and by how much, to a helper method that encapsulates that policy.

    var dequeuedValue = _container[_downHook++];
    _container[_downHook - 1] = null;

See what your obsession with putting the ++ in place has cost you? You do work in the decrement, and then you undo that work because you did it too soon! This is hard to reason about and a bug waiting to happen given any modification to this code.  If you find you are undoing work you just did, you are doing something wrong; write the code more clearly:

    var dequeuedValue = _container[_downHook];
    _container[_downHook] = null;
    _downHook -= 1;

"Resize" is a word; it's not "re size". So the method should be Resize, not ReSize.

As noted in the other answer the resize logic is wrong.  The correct logic is to copy all the elements from downhook to tophook-1 in the original array into 0 to count-1 in the new array.

Never just fix a bug. Ask yourself "how could I have better reasoned about this code so as to avoid the bug?" and "how could I have changed the design of the code so as to avoid the bug?"  For example:

Resizing a queue should not be affected in any way by the contents of the queue, and so if you are making a comparison against an element of the queue during a resize, you know immediately that you've done something wrong.

Also, resizing a queue should take as many operations as there are elements in the queue, but you do as many operations as there are in the array. So again, you could have known from first principles that the code was probably wrong.

Finally, this bug would have been never written in the first place had you made a generic Queue<T>, since there is no "null" T to use as a marker. Solving the more general problem is sometimes easier than solving a specific problem, because it forces you to not try to take advantages of specifics, like the nullability of strings.

Develop the ability to reason about these sorts of invariants, and you will find that you will write code that is more likely correct and better performing.

Also, there are already helper methods on Array to help you copy elements from one array to another, and added bonus, they are possibly faster than the code you're writing. Use them.

There's another bug in Resize. Suppose your user says that they expect the capacity to be 1000. Fine; we allocate a thousand items for the array. Then they do 250 enqueues and a dequeue. What happens? The capacity is reset to 500!

The user said that they had an expectation of how much storage they'd need, in order to cut down on the number of resizes on the way there. But you possibly give them a resize on the way to 1000 items.

Keep track of the user's capacity preference, and use that as the minimum array capacity; don't shrink to less than that. They said they're cool with using that much memory, so honour that request.

There is no logic in here that will help with debugging or testing. For example, it would be nice to see something like an implementation of ToString that dumps out a comma-separated list.

EXERCISE: Resizes are expensive; they are an O(n) operation, and so should be done as little as possible. Consider a queue where you enqueue a thousand items, then for the rest of the program you do enqueue-dequeue-enqueue-dequeue-enqueue-dequeue a few million times. How many resizes are there?

Plainly there could be zero resizes because the queue never grows in size beyond 1001 items in this scenario. And yet there are a great many resizes!  What can you do to eliminate resizes in this scenario?


Implementation of C Standard Library Function ntohl() This is an implementation of ntohl() that I wrote as an exercise. ntohl() takes a uint32_t value and returns it unchanged if the host architecture is network-byte-order (big-endian), otherwise the value is converted to host-byte-order.

My version converts to little-endian; is it always the case that host-byte-order is taken to mean little-endian? This appears to be the case, from what I have read, but what if the host architecture is middle-endian? Do real implementations of ntohl() detect other byte-orders, or strictly big- and little-endian?

I am also interested in any comments about the use of a union to detect endianness on the host machine, suggestions and comparison with other methods, and similarly, comments and suggestions relating to the use of bitwise operators to perform the conversion from big-endian to little-endian.

#ifndef _STDINT_H
#include <stdint.h>
#endif

uint32_t my_ntohl(uint32_t netlong)
{
    union {
        uint16_t num;
        uint8_t bytes[2];
    } endian_test = { .bytes = { 0x01, 0x00 }};

    if (endian_test.num == 0x0001) {
        netlong = (netlong << 24) | ((netlong & 0xFF00ul) << 8) |
            ((netlong & 0xFF0000ul) >> 8) | (netlong >> 24);
    }

    return netlong;
}

Unless you wish to optimize the code, with specialized swappers for various hosts orders, you are doing it wrong.

I invite you to check The Byte Order Fallacy by Rob Pike. The punch line: the byte order of the computer you are executing the code on doesn't matter, because the language abstracts it for you.

Thus, only the byte order of the network matters, and the network is big-endian:

#include <stdint.h>
#include <string.h>

uint32_t ntohl(uint32_t const net) {
    uint8_t data[4] = {};
    memcpy(&data, &net, sizeof(data));

    return ((uint32_t) data[3] << 0)
         | ((uint32_t) data[2] << 8)
         | ((uint32_t) data[1] << 16)
         | ((uint32_t) data[0] << 24);
}

This function will work no matter the endianness of the host, even on the crazy middle-endians ones.

Oh, and it optimizes well in general, in case you were wondering:

ntohl(unsigned int):
        mov     eax, edi
        bswap   eax
        ret

bswap being the native CPU instruction to swap bytes on x86.


Implementing RSA-AES encryption protocol I am trying to write a simple program that allows to encrypt a string of plaintext so that it can be transmitted via an "insecure channel" by which I mean a "regular chat"; be it Skype, Facebook, or even email or something similar. This is what I came up with:

At first, one user, Alice, will generate a cryptographically secure key for this "session" (which can - I think - be very long, so long as new IVs can be generated). It will be used for the AES algorithm.

byte[] sessionKey = GenerateNewKey();

I/You don't need to worry about GenerateNewKey().

This key needs to be transferred. RSA should be used as the asymmetric encryption algorithm. At first, Bob will extract a new private-public Key set RSAParameters from a RSACryptoServiceProvider . Furthermore, I will take the public key as MyPublicKey from that RSAParameters.

RSAParameters extractedParameters;
using (RSACryptoServiceProvider prov = new RSACryptoServiceProvider(
    RsaKeyLength /* const, >= 4096  */)
{
     try
     {
          extractedParameters = prov.ExportParameters(true);
     }
     finally
     {
          prov.PersistKeyInCsp = false;
     }
}
byte[] bobsPublicKey = extractedParameters.Modulus;

Now, this byte[] bobsPublicKey will be given to Alice, by writing it into the chat. She will encrypt the byte[] sessionKey as follows:

byte[] encryptedAES;
using (RSACryptoServiceProvider prov = new RSACryptoServiceProvider())
{
    try
    {
        prov.PersistKeyInCsp = false;
        RSAParameters param = prov.ExportParameters(false);
        param.Modulus = bobsPublicKey;
        prov.ImportParameters(param);
        prov.PersistKeyInCsp = false;
        encryptedAES = prov.Encrypt(sessionKey, true /* use OAEP */);
    }
    finally
    {
        prov.PersistKeyInCsp = false;
    }
}

Then, she will write encryptedAES into the chat, which will be received by Bob, who finally gets the AES key sessionKey back via:

byte[] sessionKey;
using (RSACryptoServiceProvider prov = new RSACryptoServiceProvider())
{
    try
    {
        prov.PersistKeyInCsp = false;
        prov.ImportParameters(extractedParameters);
        prov.PersistKeyInCsp = false;
        sessionKey = prov.Decrypt(encryptedAES, true /* use OAEP */);
    }
    finally
    {
        prov.PersistKeyInCsp = false;
    }
}

Now, lets say Alice wants to send a message to Bob. Assume that for example _aes = "AES, 256 key, CBC, PKCS7"

byte[] iv = GenerateIV(8 /*byte length*/);
byte[] encryptedMessage;
using (MemoryStream ms = new MemoryStream())
{
     ms.Write(iv, 0, iv.Length); // Prepend the IV to the Stream
     // Append the encrypted message
     using (ICryptoTransform trans = _aes.CreateEncryptor(sessionKey, iv))
     using (CryptoStream cs = new CryptoStream(ms, trans, CryptoStreamMode.Write)
     using (StreamWriter sw = new StreamWriter(cs))
     {
         sw.Write(message);
         sw.Flush();
         cs.FlushFinalBlock();
     }
     encryptedMessage = ms.ToArray();
}

encryptedMessage will be written to the chat. Bob decypts like:

// extract the IV
byte[] iv = GetIV(encryptedMessage);
// the rest will be the actual message
byte[] data = GetData(encryptedMessage); // Don't worry about those two

byte[] decryptedMessage;
using (MemoryStream ms = new MemoryStream(data, iv.Length, 0))
using (ICryptoTransform trans = _aes.CreateDecryptor(sessionKey, iv))
using (CryptoStream cs = new CryptoStream(ms, trans, CryptoStreamMode.Read)
using (StreamReader sr = new StreamReader(cs))
    decryptedMessage = sr.ReadToEnd();

And finally, decryptedMessage should contain the message Alice tried to send.

My request is, that this code should be reviewed regarding

whether this is a correct - that is secure - implementation of such an "algorithm pair" for transmitting messages via an unsafe and permanently visible channel
whether there are redundant calls to the .Net classes
(more things that can be improved regarding the first point)

whether this is a correct - that is secure - implementation of such an
  "algorithm pair" for transmitting messages via an unsafe and
  permanently visible channel

Your approach provides zero forward security. As soon as Bobs private key is compromised, all past communication with Bob is compromised as well.

You should use a Diffie-Hellman like handshake protocol for agreeing on a common secret for the actual communication.

You are not providing any form of authentication either.

Right now, Eva can perform a trivial man-in-the-middle attack. While Alice could in theory still verify Bobs identity by comparing the provided public key against a trusted database, Bob in return has no means to verify Alice's identity.

A simple band-aid would be to sign the chosen communication key with Alice's public RSA key, so that Bob has the confirmation that the key was in fact chosen by Alice, and not Eva.

For that, just apply a cryptographic hash function to the key, and encrypt the hash with Alice's private RSA key. Bob then uses Alice's known public RSA key to decrypt the signature and verifies that he can generate the same hash. Alternatively you can hash the encrypted shared secret instead of the plain text, if you don't wish to leak information on the plain text.

Be wary that this is still potentially subject to replay attacks. In order to protect against that, Bob should start the communication with a plaintext nonce which Alice needs to include in the signature. This may be an arbitrary string, but something as simple as the current time stamp suffices.

This is still only authentication though, and does not remove the need to agree on a new key via DH to provide forward security. You need to get rid of the temporary key as fast as possible.

The problem of replay attacks also applies to the actual messages themselves. As each message is only protected by the shared secret, you are unable to detect when Eve maliciously repeats a recorded message of the same session repeatedly.

A practical solution to that, is to append a fresh nonce to each sent message, which is expected to be repeated in the next message. Now you can tell for sure if the order of messages in one direction has been altered.

As for ensuring the coherence of a dialog, you might want to think about acknowledgment messages, which confirm receiving a content message.

byte[] bobsPublicKey = extractedParameters.Modulus;

That's not the public key. You need both the public exponent and the modulus.

using (MemoryStream ms = new MemoryStream(data, iv.Length, 0))
using (ICryptoTransform trans = _aes.CreateDecryptor(sessionKey, iv))
using (CryptoStream cs = new CryptoStream(ms, trans, CryptoStreamMode.Read)
using (StreamReader sr = new StreamReader(cs))
    decryptedMessage = sr.ReadToEnd();

More curly braces and indentation please. The syntax with multiple using directives on the same indentation level should IMHO only be used when the declared disposables are independent. If they are dependent, they can no longer have the same life time, and that should be reflected by the code structure:

using (MemoryStream ms = new MemoryStream(data, iv.Length, 0))
using (ICryptoTransform trans = _aes.CreateDecryptor(sessionKey, iv))
{
    using (CryptoStream cs = new CryptoStream(ms, trans, CryptoStreamMode.Read)
    {
        using (StreamReader sr = new StreamReader(cs))
        {
            decryptedMessage = sr.ReadToEnd();
        }
    }
}


Count combinations of positive and negative that sum to target number The problem I'm solving is given as follows:

  You are given a list of non-negative integers, a1, a2, ..., an, and a
  target, S. Now you have 2 symbols + and -. For each integer, you
  should choose one from + and - as its new symbol.

  Find out how many ways to assign symbols to make sum of integers equal
  to target S.

Here is my solution:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return findTargetSum(nums, 0, S, 0);
    }

    int findTargetSum(vector<int>& nums, int i , int S, int sumSoFar){
        if(i == nums.size()){
            return sumSoFar == S;
        }

        return findTargetSum(nums, i + 1, S, sumSoFar + nums[i]) + findTargetSum(nums, i + 1, S, sumSoFar - nums[i]);
    }
};

This solution however performs slower than the target. I suspect there may be some DP solution I am missing or maybe some optimization in my current solution might be to blame. Any advice on how to cut the run time would be appreciated.

The question as asked by OP left out one crucial piece of information: The constraints of the problem. Listed below:

  Note: The length of the given array is positive and will not exceed
  20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer.

And herein lies a big hint: The sum of all elements will not exceed 1000 (and all input values are positive). This is the creators of the problem telling you that you can trade fixed size memory for speed, which wouldn't be possible if this constraint was not present.

Note that that "The result will fit in a 32 bit integer" is redundant and over estimated, as there can be max 20 elements only 2^20 combinations of +- exist and thus only 20 bits are needed to store the result, incidentally this means that you only need to try 1 million combinations of +- to brute force the problem which shouldn't take much more than 20 numbers*1 million combinations*instructions per number, which would be at most a second or so on a modern machine unless you botch the implementation.

Because addition and subtraction commutes you can sort the array without affecting the result. The individual solutions may change but not the number of solutions. This together with bounding of the largest possible remaining sum can be used to prune some branches from the search to improve upon brute force.

In general, the constraints are such that the brute force solution implemented efficiently should be enough, but we can do better if we use some memory.

Imagine an array A which can be indexed by values -1000 to 1000 (just offset the index by +1000 in your code, mapping the range -1000...1000 to 0...2000).

Then, for each index I we store a value V which is how many ways we can compute a sum of I. So when we are done, the answer to the problem: "In how many ways can you assign +- to the input values so that their sum in S", will be A[S].

Pseudo-code:

Create two arrays A and B, indexable from -1000 to 1000 and set all elements to 0.
Take the first value from the input, call it: a
And set A[a] = 1 and A[-a] = 1
Take the next value from the input, call it: b
For every index i, where A[i] is non-zero do: B[i+b] += A[i], B[i-b] += A[i], A[i] = 0
Swap A and B
Repeat from 4 until no more input is available
Return A[S]

The above procedure will take 20 iterations of 4. to 7. with the maximum problem size. Step 5 requires a scan through A meaning 2000 loop iterations. So all in all for the max problem size 40k iterations of the inner most loop are needed. Lets estimate the inner loop body to be 10 instructions putting us at around 400k instructions which is around two orders of magnitude less than brute force.

The observant reader will note that there is a lot of wasted time in scanning through A in step 5 to find the non-zero entries. There is a way to avoid this by using an auxiliary array to store non-zero indexes for the next iteration to speed this up. The details of this are left as an exercise for the reader.

There is another optimisation that can be made to get rid of the cost of offsetting the indexes in the inner most loop, can you find it?