Sorting a list of phone numbers by teleconference provider and location I'm looking to order an array of phone numbers with a primary sorting criteria of whether the teleconference provider is correct and a secondary criteria of whether the the location of the phone number matches the location of the user.

Example:

If UserLocation = US, meetingProvider = AT&T, the order should be:

US AT&T Number
UK AT&T Number
US Unknown number
UK Unknown number
US Webex number
UK Webex number

I've made two solutions for this problem. The sort function used in my 2nd attempt appears to be the function to use but I find the long winded closures impact readability. Although filtering repeatedly seems somewhat inefficient. With readability in mind, how can I can improve this function and which attempt is the better way to go about this?

1st attempt

///Orders parsed numbers by correctProvider -> unknownProvider -> incorrectProvider. If the users location can be idenitified we then order these subsets so the numbers for the users location are on top.
private static func sortParsedNumbers(meeting: Meeting) -> [String] {
    let unknownProviderNumbers = meeting.phoneNumbers.filter { ConferenceNumberDirectory.findProvider(forNumber: $0) == .unknown }
    var correctProviderNumbers = meeting.phoneNumbers.filter { ConferenceNumberDirectory.findProvider(forNumber: $0) == meeting.conferenceProvider }
    let incorrectProviderNumbers = meeting.phoneNumbers.filter { !unknownProviderNumbers.contains($0) && !correctProviderNumbers.contains($0) }

    if let userCountry = getUserLocation() {
        let userAndNumberLocationMatch = {ConferenceNumberDirectory.findCountryISOCodes(forNumber: $0).contains(userCountry)}
        let matchingLocationNumbers = correctProviderNumbers.filter(userAndNumberLocationMatch)
        let nonMatchingLocationNumbers = correctProviderNumbers.filter {matchingLocationNumbers.contains($0)}
        correctProviderNumbers = matchingLocationNumbers + nonMatchingLocationNumbers
    }
    return correctProviderNumbers + unknownProviderNumbers + incorrectProviderNumbers

2nd attempt

///Orders parsed numbers by correctProvider -> unknownProvider -> incorrectProvider. If the users location can be idenitified we then order these subsets so the numbers for the users location are on top.
    private static func sortParsedNumbers(meeting: Meeting) -> [String] {

    guard let userCountry = getUserLocation() else {
        let numbersOrderedByProvider = meeting.phoneNumbers.sorted {element,_ in ConferenceNumberDirectory.findProvider(forNumber: element) == .unknown }
            .sorted {element,_ in ConferenceNumberDirectory.findProvider(forNumber: element) == meeting.conferenceProvider}
        return numbersOrderedByProvider
    }

    let numbersOrderedByLocation = meeting.phoneNumbers.sorted(by: {x,_ -> Bool in ConferenceNumberDirectory.findCountryISOCodes(forNumber: x).contains(userCountry)} )
    let numbersOrderedByLocationAndProvider = numbersOrderedByLocation.sorted {ConferenceNumberDirectory.findProvider(forNumber: $0) == .unknown && ConferenceNumberDirectory.findProvider(forNumber: $1) != .unknown }
        .sorted {ConferenceNumberDirectory.findProvider(forNumber: $0) == meeting.conferenceProvider && ConferenceNumberDirectory.findProvider(forNumber: $1) != meeting.conferenceProvider}
    return numbersOrderedByLocationAndProvider
}

Your first attempt

That seems to be a correct implementation, but the same array meeting.phoneNumbers
is filtered repeatedly, which is not very efficient. You could improve it by
traversing the array once and assign each phone number to one of the four arrays:

func sortParsedNumbers(meeting: Meeting) -> [String] {

    var unknownProviderNumbers: [String] = []
    var incorrectProviderNumbers: [String] = []
    var correctProviderNumbers: [String] = []
    var matchingLocationNumbers: [String] = []

    let userCountry = getUserLocation()
    for phoneNumber in meeting.phoneNumbers {
        // ... append `phoneNumber` to one of the four arrays ...
    }

    return matchingLocationNumbers + correctProviderNumbers + incorrectProviderNumbers + unknownProviderNumbers
}

But this does not scale well if more sorting criteria are added.
Which leads us to

Your second attempt

There are two problems. First, you sort the arrays with comparison functions like this:

meeting.phoneNumbers.sorted { element, _ in
    someBooleanPredicate(element)
}

But the sorted(by:)
method requires that the given predicate is a "strict weak ordering over the elements",
in particular that

areInIncreasingOrder(a, a) is always false. (Irreflexivity)

and that condition is violated in your code.

Second, you chain multiple sorted(by:) calls. But the sorted() method
is not stable, which means that the later sort can destroy the result of the
previous sorts.

For both reasons, your code may give correct results, but you cannot rely on it.

So (unless you have a stable sort method, which the Swift standard library does not
yet provide), a multi-level sort must be done with a single call to sorted(by:).

Let's start with an example: Assume that you have a Person type with firstName
and lastName properties, then

persons.sort(by: { (lhs, rhs) in
    if lhs.lastName != rhs.lastName {
        return lhs.lastName < rhs.lastName
    }
    return lhs.firstName < rhs.firstName
})

would be a correct way of sorting an array with respect to the last name first,
and with respect to the first name second. This can be simplified to

persons.sort(by: { (lhs, rhs) in
    return (lhs.firstName, lhs.lastName) < (rhs.firstName, rhs.lastName)
})

because the compiler automatically creates a < operator for tuples of
comparable elements, implementing the lexicographical order.

In your case we have two criteria as well: provider and location. First we need some
type to describe and compare the desired sorting order for both criteria.
That could be just an Int, but an integer-based enum describes the intention more clearly:

enum ProviderStatus: Int, Comparable {
    case known
    case unknown
    case correct

    static func <(lhs: ProviderStatus, rhs: ProviderStatus) -> Bool {
        return lhs.rawValue < rhs.rawValue
    }
}

enum LocationStatus: Int, Comparable {
    case notMatching
    case matching

    static func <(lhs: LocationStatus, rhs: LocationStatus) -> Bool {
        return lhs.rawValue < rhs.rawValue
    }
}

Then you can compute a tuple describing the sorting order for each phone
number, and sort the numbers accordingly:

func sortParsedNumbers(meeting: Meeting) -> [String] {

    let userCountry = getUserLocation()

    func sortOrder(phoneNumber: String) -> (ProviderStatus, LocationStatus) {
        let providerStatus = ...
        let locationStatus = ...
        return (providerStatus, locationStatus)
    }

    return meeting.phoneNumbers.sorted(by: { (lhs, rhs) in
        sortOrder(phoneNumber: lhs) < sortOrder(phoneNumber: rhs)
    })
}

Adding more sorting criteria is straightforward with this approach.

A possible disadvantage is that sortOrder() can be called multiple times for the
same phone number during the sorting process. That can be avoided at the expense
of additional storage:

    return meeting.phoneNumbers
     .map { ($0, sortOrder(phoneNumber: $0))}
     .sorted { $1.1 > $0.1 }
     .map { $0.0 }

The return expression maps each phone number to a (number, sortOrder) pair,
sorts the pairs according to the sort order, and finally extracts the phone number
again. This guarantees that the sortOrder() function is called only once
for each phone number.


API Gateway for blocking api calls I recently had a programming interview, where I had to create an Api Gateway. The description is as follows:

You need to create a gateway in which it only allows certain number of callers to call api and rest of them will be blocked within the given timeframe.
For eg : If the time window is 1 minute. You need to allow only 6 calls to be called within that 1 minute window and rest of them will be blocked and will be only allowed in the next window of 1 minute.
In short every window will only allow 6 api calls.

I was not able write a proper code during 30 min round, since my brain started rushing towards all kinds of solutions.
But I tried to do it once I was done with an interview and below is my solution. Please let me know if there is anyway that I can improve in the implementation, in terms of performance or any other aspects.
public class APIGateway {
    private Employee emp;
    private int count = 0;
    private Timer timer;

    public APIGateway(Employee emp) {
        this.emp = emp;
        this.timer = new Timer(this);
        Thread t = new Thread(timer);
        t.start();
    }

    public synchronized void create() {
        while (!isAccessible()){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        emp.create();
        count++;
    }

    private synchronized boolean isAccessible() {
        if(count<6){
            return true;
        }
        return System.currentTimeMillis()<=timer.getElapsetime();
    }

    private synchronized void unblock(){
        count = 0;
        notifyAll();
    }

    private class Timer implements Runnable {
        private long startTime;
        private APIGateway gateway;

        Timer(APIGateway gateway){
            startTime = System.currentTimeMillis();
            this.gateway = gateway;
        }

        private long getElapsetime() {
            return startTime + 6000;
        }

        @Override
        public void run() {
            while (true) {
                try {
                    Thread.sleep(60000);
                    startTime = System.currentTimeMillis();
                    gateway.unblock();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }

    }

    public void delete() {
        // same like create
    }

    public void update() {
        // same like create
    }
}

// Assume this is the api calls.
interface Employee {
    void create();
    void delete();
    void update();
}

My first point would be that if I want throttling for my API, I would put it in some kind of interceptor. However since this is an interview assignment and for the sake of simplicity I would recreate that as a function call:

public synchronized void create() {
    if(isAccessible()) {
        create(employer);
    }
}

Secondly, I don't think it is a good idea to block with the while-loop you have, when the quota of calls have been made. Instead return a meaningful message that explains why the request was denied.

With the current implementation you are using the InterruptedException as part of your control flow, which is usually considered an anti-pattern https://softwareengineering.stackexchange.com/questions/189222/are-exceptions-as-control-flow-considered-a-serious-antipattern-if-so-why.

I feel like a simpler solution would be to simply reset the counter every 60 seconds in the Timer class, similar to what you are already doing. Maybe I am missing something, but I don't understand why you are doing the check:

System.currentTimeMillis()<=timer.getElapsetime();

You are already resetting the counter every 60 seconds, so I would just return false in this method.

My last point would that generally the client would be passing Employee (or whatever data needed to create an employee) in the request, so it does not make sense to have Employee as a field. Rather it should be a parameter of the create function.

If this came as an interview question I would also see it as an opportunity to talk about throttling, and what alternatives there are. For example, maybe checking the rate of calls instead of having a fixed window of 60 seconds would make sense. However that's not that related to this code review.


Multi-replacement in a string, independently and prioritized I need a shorter way to do this.

input: an ordered list of string pairs L; and a string s

task: for each pair (a,b), replace each occurrence a in s by b

note 1: the replacements have to be independent. The result of one replacement can not be taken as a trigger for a subsequent replacement
Example: L=(("a","b"),("b","c")); s="ab"; desired output: "bc", and not "cc".

note 2: L is ordered; the beginning of the list has higher priority, so if L is (("xyz", "P"), ("xy", Q)) and s is "wxyzabc" then the result should be "wPabc". If the order of L were reversed, the result would be "wQzabc".

bonus: it's a great thing if it can also handle regex patterns as replacement pairs

My idea:

iterate over L, and replace each source to a sequence of joker characters of equal length (the joker does not appear anywhere in the string), while noting the position where we found it.
then split the string to a list of strings of length 1, replace the first joker of each sequence with the desired target replacement, join the list back together and remove jokers.

Here is my implementation in Python:
def multireplace(text, changes):
    # find a possible joker character
    for num in range(256):
        joker = chr(num)
        if text.find(joker) != -1:
            continue

        jokerUsable = True
        for old,new in changes:
            if old.find(joker) != -1 or new.find(joker) != -1:
                jokerUsable = False
                break

        if jokerUsable:
            break

    # list of lists, each list is about one replacement pair,
    # and its elements will be the indices where they have to be done
    index_lists=[]

    for old, new in changes:
        indices = []
        pattern = re.escape(old)
        for m in re.finditer(pattern, text):
            indices.append(m.start())

        text = text.replace(old, joker*len(old))
        index_lists.append(indices)

    character_list = list(text)
    for i in range(len(index_lists)):
        old, new = changes[i]
        for place in index_lists[i]:
            character_list[place] = new

    # remove jokers
    i=0
    while i < len(character_list):
        if character_list[i] == joker:
            del character_list[i]
        else:
            i+=1

    return "".join(character_list)

This is very cumbersome, and seems to be a standard problem, so I was wondering if there is a standard way of doing this.

Do it recursively. Split the string by the first "from" value, recurse with the rest of the changes for each resulting part, then join them back together with the "to" value.

def multireplace(text, changes):
    if not changes:
        return text

    from_, to = changes[0]
    parts = text.split(from_)
    return to.join((multireplace(part, changes[1:]) for part in parts))

Advantage: Short and clean code
Disadvantage: Uses linear stack with respect to the number of changes. Might lead to stack overflow in case of lots of replacement pairs.

(Note: this answer is based on an earlier answer that somehow got deleted)


Format capital letters at the start of a sentence I have a set of predefined templates for messages, where you can insert different arguments to make it more specific.

In order for the messages to be looking good I needed a way to capitalize the first letters of each sentence because you might pass the argument fully lower-cased while in some messages that argument happen to be the start of the sentence which would require a capital letter at the start.

This is my extension method:

public static class Extensions
{
    private static readonly char[] _punctuationMarks = {'.', '!', '?'};

    public static string FormatCapitalLetters(this string source)
    {
        StringBuilder result = new StringBuilder();
        result.Append(source.First().ToUpper());
        for (int i = 1; i < source.Length; i++)
        {
            result.Append(source[i]);
            if (IsPunctuationMark(source[i]))
            {
                int index = i + 1;
                if (index >= source.Length || IsPunctuationMark(source[index]))
                {
                    continue;
                }
                if (source[index] == ' ')
                {
                    index++;
                }
                result.Append(' ');
                result.Append(source[index].ToUpper());
                i += index - i;
            }
        }
        return result.ToString();
    }

    private static string ToUpper(this char input) => input.ToString().ToUpper();

    private static bool IsPunctuationMark(char input) => _punctuationMarks.Any(
        punctuationMark => punctuationMark == input);
}

I'm looking for any comments on how to improve the current code or fix any flaws I'm unaware of, any alternative solutions are welcome as well.

Multispace bug

There is one flaw in this solution. It assumes a perfectly formatted sentence. This means that if there are multiple spaces between sentences the formatting won't work. For example it turns this "foo.  bar!    baz?" into "Foo.  bar!    baz?"

To fix this you either need another extension fixing all multiple spaces with a single one or make this one aware of this problem.

if (source[index] == ' ')
{
  index++;
}

This if should contain a continue but even with it, it won't work yet because the first if won't pass the second time. The logic is more complex and it would require a flag to skip "" spaces.

Trim

result.Append(source.First().ToUpper());

You assume that the first char is the first letter but you don't trim the source in case it isn't.

Naming

if (IsPunctuationMark(source[i]))
{
    int index = i + 1;
    if (index >= source.Length || IsPunctuationMark(source[index]))
    {
        continue;
    }
    if (source[index] == ' ')
    {
        index++;
    }
    result.Append(' ');
    result.Append(source[index].ToUpper());
    i += index - i;
}

Here I find the index too general. It looks like it should be called e.g. firstLetterIndex.

Alternative? ;-)

You could use regex to clean-up the string.

public static string CapitalizeSentence(this string source)
{
    return
        Regex
            .Replace(
                source.Trim(),
                @"(^|(?<Punctuation>[.!?])\s*)(?<FirstLetter>[a-z])",
                m =>
                    $"{(m.Groups["Punctuation"].Success ? m.Groups["Punctuation"].Value + " " : string.Empty)}" +
                    $"{m.Groups["FirstLetter"].Value.ToUpper()}");
}


isType(obj) / getType(obj) - v0 By browser unknown, i mean i don't know how far back support goes for this.

Also, I'm wondering when I can delegate to typeof.

I've heard typeof is faster but the method below is more widely supported and also mentioned in ES5.

/*isType
**  dependencies - none
**  browser - unknwon
**
*/
NS.isType = function (type, o) {
    return (Object.prototype.toString.call(o).slice(8,1) === type);
};

/*getType
**  dependencies - none
**  browser - unknown
**
*/
NS.getType = function (o) {
    return (Object.prototype.toString.call(o).slice(8,1);
};

Clarification:

Not interested in detecting array like objects....just the language objects defined in ES 5.

How about:

NS.CheckType = function (o,test) {
    // implements both
    return test ? o.constructor.name === test : o.constructor.name;
};
// usage
NS.CheckType(false);       //=> 'Boolean'
NS.CheckType(false,Array); //=> false
NS.CheckType({},Object);   //=> true
NS.CheckType({},Array);    //=> false
NS.CheckType([],Object);   //=> false
NS.CheckType([],Array);    //=> true
NS.CheckType(/[a-z]/);     //=> 'RegExp'
NS.CheckType(0);           //=> 'Number'
// etc...

Because most js-things 'inherit' from Object you can also use:

Object.prototype.is = function (test) {
    return test ? this.constructor === test : this.constructor.name;
};
// usage
'string'.is();        //=> 'String'
'string'.is(Object);  //=> false
 (function(){}).is(); //=> Function
 var f = function(){};
 f.is(Function);      //=> true
 // also
 function Animal(name){this.name = name || 'some animal';}
 var dog = new Animal('Bello');
 dog.is(Animal); //=> true
 // etc...

[Edit] tested this in IE7-10:

Object.prototype.is = function (test) {
    return test
      ? this.constructor === test
      : (this.constructor.name ||
         String(this.constructor)
             .match ( /^function\s*([^\s(]+)/im)[1] );
};

for completeness: if the constructor function is anonymous the method will fail. Here's a solution for that:

Object.prototype.is = function (test) {
        return test
          ? this.constructor === test
          : (this.constructor.name ||
              ( String(this.constructor).match ( /^function\s*([^\s(]+)/im)
               || ['','ANONYMOUS_CONSTRUCTOR'] ) [1] );
};
// usage
var Some = function(){ /* ... */}
    some = new Some;
some.is(); //=> 'ANONYMOUS_CONSTRUCTOR'

And as bonus:

Object.prototype.is = function() {
        var test = arguments.length ? [].slice.call(arguments) : null
           ,self = this.constructor;
        return test ? !!(test.filter(function(a){return a === self}).length)
               : (this.constructor.name ||
                  (String(self).match ( /^function\s*([^\s(]+)/im)
                    || [0,'ANONYMOUS_CONSTRUCTOR']) [1] );
}
// usage
var Some = function(){ /* ... */}
   ,Other = function(){ /* ... */}
   ,some = new Some;
2..is(String,Function,RegExp);        //=> false
2..is(String,Function,Number,RegExp); //=> true
some.is();                            //=> 'ANONYMOUS_CONSTRUCTOR'
some.is(Other);                       //=> false
some.is(Some);                        //=> true
// note: you can't use this for NaN (NaN === Number)
(+'ab2').is(Number);                 //=> true


Is this non-recursive mergesort efficient and a good way to simulate the recursive version? My teacher assigned us to do the recursive version of mergesort, yet I heard that the non-recursive version (bottom up) is a bit tougher, so I decided to this one as well. My main concerns are:

Considering the way I coded it, does it still have the same efficiency?
Did I do this in an acceptable way? If not, why?

Main:

    Random rand = new Random();
    ArrayList<Integer> array = new ArrayList<Integer>();
    for (int i = 0; i < 100; i++){
        array.add(rand.nextInt(20));
    }
    System.out.println("Original:");
    for (int num: array){
        System.out.print(" " + num);
    }
    Algorithm algo = new Algorithm(array);
    algo.print();

Code:

ArrayList<Integer> ar = new ArrayList<Integer>();
int loBound = 0, hiBound = 1;
public Algorithm(ArrayList<Integer> initAr){
    ar = initAr;
    partition();
}
public void partition(){
    if (ar.size() > 1){
        int partitionSize = 1;
        int arraySize = ar.size();

        if (ar.size() % 2 != 0) // if the size is odd make it even so loop doesn't terminate early without sorting all values
            arraySize++;

        while (arraySize / 2 >= partitionSize){
            while (true){
                ArrayList<Integer> left = new ArrayList<Integer>();
                ArrayList<Integer> right = new ArrayList<Integer>();
                // Variables which will be sent to 'update' method as parameters. Tells method which indexes to update (in-between low and high)
                int loInd = loBound, hiInd;
                for (int i = loBound; i < hiBound; i++){
                    left.add(ar.get(i));
                }
                calcBounds(partitionSize);
                for (int j = loBound; j < hiBound; j++){
                    right.add(ar.get(j));
                }
                hiInd = hiBound;
                if (right.size() != partitionSize){
                    update(left, right, loInd, hiInd);
                    break;
                }
                update(left, right, loInd, hiInd);
                calcBounds(partitionSize);
            }
            partitionSize*=2;
            loBound = 0;
            hiBound = partitionSize;
        }
    }
}
// calculates the indexes from which I will extract from the original array
private void calcBounds(int partitionSize){
    if (ar.size() - hiBound > partitionSize){
        loBound = hiBound;
        hiBound = loBound + partitionSize;
    }else {
        loBound = hiBound;
        hiBound = ar.size();
    }
}
// updates original ArrayList after sorting 'left' and 'right'
private void update(ArrayList<Integer> left, ArrayList<Integer> right, int loInd, int hiInd){
    // sort
    ArrayList<Integer> result = new ArrayList<Integer>();
    int lIndex = 0, rIndex = 0, resIndex = 0;
    while (lIndex < left.size() || rIndex < right.size()){
        if (lIndex < left.size() && rIndex < right.size()){
            if (left.get(lIndex) <= right.get(rIndex)){
                result.add(resIndex, left.get(lIndex));
                resIndex++;
                lIndex++;
            }else {
                result.add(resIndex, right.get(rIndex));
                resIndex++;
                rIndex++;
            }
        }else if (lIndex < left.size()){
            result.add(resIndex, left.get(lIndex));
            resIndex++;
            lIndex++;
        }else if (rIndex < right.size()){
            result.add(resIndex, right.get(rIndex));
            resIndex++;
            rIndex++;
        }
    }
    // update original ArrayList using result ArrayList
    int count = 0;
    for (int i = loInd; i < hiInd; i ++){
        ar.set(i, result.get(count));
        count++;
    }
}

void print(){
    System.out.println();
    System.out.println("Sorted:");
    for (int num: ar){
        System.out.print(" " + num);
    }
}

I have not looked into it too deeply to be able to fully answer your first question. Althought for you to get a picture of efficiency I would suggest to take the normal recursive merge sort and time it using System.nanoTime() and compare it with this version on the same array to be sorted. That could give you a picture about time complexity and regarding memory you would have to use a profiler. Simply jconsole can be enough in this case to see the memory consumption - careful with the GC kicking in when you don't want it.

Second question:
I am not saying that it would be a bad looking code but I have difficulties to understand it. I would suggest few improvements that can help the readability. For example the first one in the method partition - instead of having the whole code block in if (ar.size() > 1) I would suggest having if (ar.size() <= 1) then do return. This gets rid of one level of curly braces for the rest of the code block.

Another suggestion would be to use instance variable as least as possible, in this case loBound = 0, hiBound = 1 and ar. There is a "Brook's law for methods" that says that method should be passed necessary variables as parameters if possible, if not then accessing instance variables and so on. Besides it is some statement it is also improves readability if the method changes only parameters it got passed and not instance variables. You can better track what is being changed and returned in and from the method.

From where I am sitting the main downside of this code would be to come to it half year later and figure out what it does and if it does it right. I would say even the author of the code would have to take some time to figure it out.

I am sorry I might not help you with your first question. Hope the comments on the second one regarding the code style could be of use for you.


Optimizing producer consumer using monitors I am trying to review concurrency concepts, i.e monitor, semaphores, etc. I've learned that Semaphores are natively not available in C++11 (presumably because it is very error prone) - which is why I am trying to review monitors.

The producer/consumer below already works correctly (to my knowledge), but I am wondering if it is possible/correct to make an optimization and explicitly release the unique_lock, instead of waiting for it to destroy itself.

std::mutex mutex;
std::condition_variable space_in_buffer;
std::condition_variable buffer_empty;
std::queue<int> buffer;
#define MAX_BUFFER_SIZE 10

void produce() {
    while (1) {
        std::unique_lock<std::mutex> lock(mutex);
        if (buffer.size() == MAX_BUFFER_SIZE) {
            space_in_buffer.wait(lock);
        } else {
            // produce
            int new_product = rand() % 30;
            buffer.push(new_product);
            printf("Produced [%d] | Item Count: %lu\n", new_product,
                    buffer.size());

            /*
             * Possible optimization to call lock.unlock() here, instead
             * of waiting for the unique lock to go out of scope ?
             */

            buffer_empty.notify_one();

            // potential for extra processing here
        }
    }
}

void consume() {
    while (1) {
        std::unique_lock<std::mutex> lock(mutex);
        if (buffer.size() == 0) {
            buffer_empty.wait(lock);
        } else {
            // consume
            int to_be_consumed = buffer.front();
            buffer.pop();

            printf("Consumed [%d] | Item Count: %lu\n", to_be_consumed,
                    buffer.size());

            /*
             * Possible optimization to call lock.unlock() here, instead
             * of waiting for the unique lock to go out of scope ?
             */

            space_in_buffer.notify_one();

            // potential for extra processing here
        }
    }
}

for(;;) is the more idiomatic infinite loop, read as "forever".
Avoid long conditional blocks, and unneccessary indentation. What you actually have is a loop followed by the else-block. Which would be best written as:

while (buffer.size() == MAX_BUFFER_SIZE)
    space_in_buffer.wait(lock);
rest-of-loop;

Unless you prefer using a lambda for the condition.

space_in_buffer.wait(lock, [&]{ return buffer.size() == MAX_BUFFER_SIZE; });
rest-of-loop;

You are using the std::queue as a ring-buffer. That's inefficient, especially as the queue still allocates and frees its nodes on .push() and .pop(). Use a dedicated ringbuffer like boost::circular_buffer, orsomething without any dynamic allocation at all.
The format for printing a std::size_t with std::printf is "%zu". Don't drop the length-marker.
Mutex, buffer, and condition-variables should be encapsulated in a class-template with the buffer-size as a parameter for reuse.
Yes, you should minimize the time you hold the lock to maximize concurrency. See whether you can do that with scoping or need to manually release the lock.


Instantaneous validation of form field length Since I have a function which can be done in few ways as usual, I was wondering which way is the best to achieve the form validation where I have only one input field, and I am showing a warning on keyup if the number of characters are in between 1 and 3 as well as enabling disabling submit button based on number of characters. Here is the fiddle. So I have two functions:

var myFunction = function () {
    var input = document.getElementById("input");
    var warning = document.getElementById("warning");
    var button = document.getElementById("button");

    if (input.value.length >= 1 && input.value.length <= 3){
        warning.style.display = 'block';
    }
    else {
        warning.style.display = 'none';
    }

    if(input.value.length > 3){
        button.disabled = false;
    }
    else {
        button.disabled = true;
    }
}

Here I have two if else statements, so I was wondering what would be the cleanest way to achieve the same thing? The only thing I could come up with was this function:

var alternative = function () {
    var input = document.getElementById("input");
    var warning = document.getElementById("warning");
    var button = document.getElementById("button");
    warning.style.display = 'none';
    button.disabled = true;

    if (input.value.length >= 1 && input.value.length <= 3)
        warning.style.display = 'block';

    if(input.value.length > 3)
        button.disabled = false;
}

But I am not sure what is the best approach performance wise, since in the second function I have states that will always be the same on calling the function and then changing them based on conditions and in the first one I first check the conditions and then manipulate the elements?

Ternary operator

You could use the ternary operator for your first if-else case:

warning.style.display = input.value.length >= 1 && input.value.length <= 3 ? 'block' : 'none';

Now, this is a bit lengthy so we might choose to store input.value.length inside another variable like so:

var length = input.value.length;
warning.style.display = length >= 1 && length <= 3 ? 'block' : 'none';

Note, that if you can use ES6 features you could benefit from using const and object matching and declare length as follows:

const { length } = input.value;

Direct assignment

As for your second scenario, you could store the conditional directly inside your variable since you just want the negated version of what you're checking:

button.disabled = length <= 3;

A more general code review

The comparison against 1 and 3 is very vague and they are considered magic numbers. What do these variables represent?

You could incorporate another self explaining variable, such as isWarning as follows:

// ES5
var length = input.value.length;
var isWarning = length >= 1 && length <= 3;

// ES6
const { length } = input.value;
const isWarning = length >= 1 && length <= 3;

warning.style.display = isWarning ? 'block' : 'none';
button.disabled = length <= 3;

This helps the structure, but still doesn't answer the question of what do the values 1 and 3 represent?

I'm assuming you aren't checking 0 since you don't want a warning to show on an empty input, so I'll provide an example of what could be done:

// For ES5 change const to var
const minLength = 4;

const isEmpty = length === 0;
const isValidLength = length >= minLength;
const isWarning = !isValidLength && !isEmpty;

warning.style.display = isWarning ? 'block' : 'none';
button.disabled = !isValidLength;

Note, that minLength would ideally have a more descriptive name related to what it is checking. minNameLength, minPostcodeLength, etc. This way the code reads relating to the logic it's checking, now how that logic is implemented each time.

Misc - ES6 deep object matching

If you are using ES6 you could use deep object matching to get length directly:

const { value: { length } } = document.getElementById('input');

This is useful since we are only concerned with the input's length, not the element itself.

Misc - Consistent use of quotes

Another small remark is your use of quotes. Either is fine but it's best to be consistent - you're using double quotes in getElementById but single quotes for setting display.

I'll continue to add things when I have time. If you have any questions/concerns please leave a comment.


Sidekiq worker to validate survey participants I have worker code that looks like this:

class VerificationWorker
  include Sidekiq::Worker

  def perform(panel_id)
    members = MembersAPI.members.fetch

    members.each do |member|
      survey = Survey.find_by(number: member.data_number)
      next if survey.nil?

      if survey.id != member.data['survey_id']
        survey.fail!('survey_id does not match')
        next
      end

      survey.recipient_id = member.id if survey.recipient_id.blank?
      survey.recipient_id == member.id ? survey.verify! : survey.fail_panel!('recipient_id does not match member id')
    end
  end
end

What do you think about this code? Is it good enough?

Your code looks pretty good to me. Just some minor notes:

next if survey.nil? -> next unless survey is enough.
The conditional operator ? is normally used for expressions, not for actions with side-effects. Also, it's a long line, a normal if-else would look better.
Argument panel_id is not used?

That said, I'd refactor it a little bit. In my experience, full-fledged conditionals (no inline conditionals) make code easier to read so the line count increase is worth it.

class VerificationWorker
  include Sidekiq::Worker

  def perform(panel_id)
    members = MembersAPI.members.fetch

    members.each do |member|
      if (survey = Survey.find_by(number: member.data_number))
        if survey.id != member.data['survey_id']
          survey.fail!('survey_id does not match')
        else
          survey.recipient_id = survey.recipient_id.presence || member.id

          if survey.recipient_id == member.id
            survey.verify!
          else
            survey.fail_panel!('recipient_id does not match member id')
          end
        end
      end
    end
  end
end


Codility's BinaryGap: Hardware-aware answer This is a well-known question, which some others have posted about on this site.

Here's my first shot following a state machine approach:

int solution(int N) {
    int longestSizeGap{};
    int sizeGap{};
    bool gapStarted{};
    while (N > 0) {
        int remainder{N%2};
        switch (remainder) {
            case 0: {
                if (gapStarted) {
                    sizeGap++;
                }
                break;
            }
            case 1: {
                if (!gapStarted) {
                    gapStarted = true;
                } else {
                    if (sizeGap > longestSizeGap) {
                        longestSizeGap = sizeGap;
                    }
                }
                sizeGap = 0;
                break;
            }
        }
        N /= 2;
    }
    return longestSizeGap;
}

How could I improve this solution to be more "hardware-aware", i.e. what about branch prediction and pipelining, cache misses and page faults, memory hierarchy and data locality? How could I improve my code to just run better?

Scoping the case body is unnecessary.
gapStarted flag is redundant (sizeGap has all the necessary information). Consider

while (N > 0) {
    int remainder{N%2};
    switch (remainder) {
        case 0:
            sizeGap++;
            break;
        case 1:
            if (sizeGap > longestSizeGap) {
                longestSizeGap = sizeGap;
            }
            sizeGap = 0;
            break;
        }
    }
    N /= 2;
}

To address your immediate concerns, there is too few variables to worry about cache, pages, or memory hierarchy. Everything will stay in registers. I don't think you can do anything about branch prediction; however, read the next bullet.
A nice to know approach is de Bruijn hashing:

find the length of trailing gap using a technique described in the answer
remember the length
shift the number left by that length
find the number of trailing ones (e.g. negate and find the number of trailing zeroes), and shift them off
keep going until the number becomes 0.

Such loop will do as many iterations as there are gaps, as opposed to the argument width in your code. Worst case is still the same. OTOH, notice that there is no branches at all.


Python Knapsack problem: greedy A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it and it will have to last the whole day. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.

I decided to solve the knapsack problem by a greedy algorithm. I am not sure of the need of the Item class, maybe another data structure is better?

from __future__ import division

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.convenience = value / weight

    def __repr__(self):
        return "Item({}, {})".format(self.weight, self.value)

class Knapsack:
    def __init__(self, capience, items_inside=[]):
        self.capience = capience
        self.items_inside = items_inside

    def current_weight(self):
        return sum(item.weight for item in self.items_inside)

    def is_full(self):
        return self.current_weight() == self.capience

    def can_incorporate(self, item):
        return self.current_weight() + item.weight <= self.capience

    def fill(self, items):
        while not self.is_full():
            self.items_inside.append(
                max((item for item in items if self.can_incorporate(item)),
                key= lambda item: item.convenience))

    def __repr__(self):
        return "Knapsack({}, {})".format(self.capience, self.items_inside)

def main():
    bag = Knapsack(54)
    bag.fill([
        Item(12, 8),
        Item(20, 13),
        Item(4, 2),
        Item(1, 0.1)])
    print(bag)

if __name__ == "__main__":
    main()

A couple of possible bugs:

It results in this:

Knapsack(54, [Item(12, 8), Item(12, 8), Item(12, 8), Item(12, 8), Item(4, 2), Item(1, 0.1), Item(1, 0.1)])

How can you put one item in the knapsack four times over? And if you could, would you want four shovels just because one shovel is very useful? You never take anything out of the list of items once you have incorporated it.
is_full and can_incorporate both do very similar things, and interact badly in the fill function - what happens if the knapsack is not full, but it cannot incorporate any of the remaining items? It will crash trying to return the max of an empty list - or if that didn't happen, it would loop forever testing whether it could incorporate the next best thing, but never being able to. You could stay with while self.can_incorporate(item) and get rid of is_full().
When you initialise the Knapsack() object, you can pass a long list of items, which go straight into the items_inside without any capience checks - you can bypass the capacity limit and overload it. Then when you fill() it, it will crash.
Nothing stops you from just adding things to the items_inside list regardless of whether the Knapsack can take it, and it can't test for that afterwards. I feel like adding something to a full knapsack should raise an exception, like removing something from an empty list raises an exception. (e.g. putting a vehicle into the knapsack is an exceptional condition - you don't do it deliberately).

I'm no design expert for sure; but I feel a bit like you're losing the heart of the problem code by squishing the algorithm into almost a one-liner and overwhelming it with surrounding methods that are only there to support the algorithm.

I know that's what support methods are for, and in a way it's neat and tidy. But in another way, it's noisy and unclear.

I don't know what I'd change, exactly, and I'm left bikeshedding at things like:

capience isn't a word I can find on Google, what about capacity? Maybe capience is a fine word, but capacity seems like volume, so maybe weight_limit?
What about contents instead of items_inside?
Why current_weight instead of weight?
What about making current_weight a property so you have the same calling style as capience, instead of one being a property and one being a function call
It seems a lot of effort to calculate the remaining list every time in the fill loop, and calculate the sum of weights every time. You could sort the list of items by convenience, pop() them from the list, or iterate through it only once.
You pass fill a list of items, but don't know which ones it fills and which ones it doesn't.

So I've ended up rewriting it myself, and it's no shorter, and probably no clearer. But it might address some of these points. The Knapsack manages its own contents as a "private" variable (_contents), so it can protect against overload, and that means loading an item has its own method. Fill() only runs through the list once. Initialising the Knapsack can't overload it.

from __future__ import division

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.convenience = value / weight

    def __repr__(self):
        return "Item(weight={}, value={})".format(self.weight, self.value)

class Knapsack:
    def __init__(self, weight_limit, initial_items=[]):
        self.weight_limit = weight_limit
        self._contents = []
        self.fill(initial_items)

    def weight(self):
        return sum(item.weight for item in self._contents)
    weight = property(fget=weight)

    def incorporate(self, item):
        if self.weight + item.weight > self.weight_limit:
            raise Exception("Knapsack Overload Exception: {} is too heavy".format(item))
        self._contents.append(item)

    def fill(self, items):
        items = sorted(items, key=lambda item: item.convenience, reverse=True)
        rejected_items = []
        for item in items:
            try:     self.incorporate(item)
            except:  rejected_items.append(item)

        return rejected_items

    def __repr__(self):
        return "Knapsack({}, {})".format(self.weight_limit, self._contents)

def main():
    bag = Knapsack(54)
    print bag.fill([
        Item(12, 8),
        Item(20, 13),
        Item(4, 2),
        Item(200,1),
        Item(1, 0.1)])
    print(bag)

if __name__ == "__main__":
    main()

(I notice that I haven't even considered your actual question about whether the Item class is necessary! I don't know, it seems useful. Although having an item name might be good).


Count the frequency of integers in an array I recently reviewed a question here on Code Review. The problem statement is

  Write a program that prompts the user to input ten values between 80 and 85 and stores them in an array. Your program must be able to count the frequency of each value appears in the array.

I coded my own solution for the problem statement. My questions are
  - Can this be optimized more?
  - Did I miss anything in C++14 or C++17 that might improve the code?
  - Is the code readable?
  - Are the variable and function names good or can they be improved?

My goals were to write the best C++ I could, remove any magic numbers and allow the solution to scale for different sets of numbers.

#include "pch.h"
#include <iostream>
#include <array>

const size_t INPUTSIZE = 10;
const size_t FREQUENCYSIZE = 6;
const int MINLEGALVALUE = 80;
const int MAXLEGALVALUE = 85;

std::array<int, INPUTSIZE> getUserInput()
{
    std::array<int, INPUTSIZE> inputValues;

    size_t i = 0;
    do
    {
        int inputValue = 0;
        std::cout << "Please enter a number between " << MINLEGALVALUE << " and " << MAXLEGALVALUE  << ":" ;
        std::cin >> inputValue;

        if (inputValue >= MINLEGALVALUE && inputValue <= MAXLEGALVALUE)
        {
            inputValues[i] = inputValue;
            i++;
        }
        else
        {
            std::cout << "The number must be between" << MINLEGALVALUE << " and " << MAXLEGALVALUE << "\n";
        }

    } while (i < INPUTSIZE);

    return inputValues;
}

std::array<unsigned, FREQUENCYSIZE> getFrequencyCounts(std::array<int, INPUTSIZE> inputValues)
{
    std::array<unsigned, FREQUENCYSIZE> freqs = { 0 };

    for (auto inputs : inputValues)
    {
        freqs[inputs - MINLEGALVALUE]++;
    }

    return freqs;
}

void printFrequencies(std::array<unsigned, FREQUENCYSIZE> freqs)
{
    unsigned rowLabel = MINLEGALVALUE;
    for (auto frequency : freqs)
    {
        std::cout << rowLabel << "      " << frequency << "\n";
        rowLabel++;
    }
}

int main()
{
    std::array<int, INPUTSIZE> inputValues = getUserInput();
    std::array<unsigned, FREQUENCYSIZE> freqs = getFrequencyCounts(inputValues);

    std::cout << "\n";

    printFrequencies(freqs);
}

Names

All-caps names are typically reserved for macros. They don't seem to me to make much sense for const variables. In fact, they only make minimal sense for object-like macros--they were originally used for function-like macros as kind of a warning that you should be cautious about passing an argument with side-effects, because they might happen more than once.

Minimize Magic

I'd typically try to keep the magic numbers to a minimum. For example, instead of defining FREQUENCYSIZE by itself, I'd probably do something like this:

const int lower_bound = 80;
count int upper_bound = 85;
const int frequency_size = upper_bound - lower_bound + 1;

Separation of Concerns

I'd at least consider separating validating data from reading the data. I'd prefer to have a function on the general order of:

bool valid(int val) {
    return val >= lower_bound && val < upper_bound;
}

Class Usage

We have a number of different things related to reading and working with numbers in a specified range. It might be worth considering wrapping those bits and pieces into a coherent class for dealing with a value in a range, and let the outside world create and use objects of that class.

template <class T, T lower_bound, T upper_bound>
class bounded {
public:
    static bool valid(T val) { return val >= lower_bound && val < upper_bound; }

    friend std::istream &operator>>(std::istream &is, bounded &b) {
        T val;
        is >> val;
        if (valid(val))
            b.val = val;
        else
            is.setstate(std::ios_base::failbit);
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, bounded const &b) {
        return os << b.val;
    }

    size_t index() { return size_t(val - lower_bound); }

    static constexpr size_t range() { return upper_bound - lower_bound + 1; }

private:
    T val;
};

That let's us simplify the rest of the code a bit, something on this general order:

int main() {
    using integer = bounded<int, 80, 85>;

    std::array<integer, 10> inputs;
    std::array<size_t, integer::range()> freqs {};

    for (integer &i : inputs) {
        std::cin >> i;
        ++freqs[i.index()];
    }

    for (auto freq : freqs)
        std::cout << freq << "\n";
}

Technically, this doesn't meet the requirements as-is (e.g., it doesn't print out a prompt to tell the user to enter data), but I think it gives at least some idea of a direction things could go.


Incrementing and decrementing 3 seperate input values by 1 using Javascript I have written the following Javascript code which increments and decrements 3 separate inputs by 1:

//INCREMENTS/DECREMENTS BEDROOMS BY 1

function plusOneBedrooms() {
    var addRoom = document.getElementById('rooms_amount_bedroom');
    value = parseInt(addRoom.getAttribute('value'), 10) + 1;
    addRoom.setAttribute('value', value);
    addRoom.innerHTML = value;

}

function minusOneBedrooms() {
    var subtractRoom = document.getElementById('rooms_amount_bedroom');
    value = parseInt(subtractRoom.getAttribute('value'), 10) - 1;
    subtractRoom.setAttribute('value', value);
    subtractRoom.innerHTML = value;

}

//INCREMENTS/DECREMENTS BATHROOMS BY 1
function plusOneBathrooms() {
    var addRoom = document.getElementById('rooms_amount_bathrooms');
    value = parseInt(addRoom.getAttribute('value'), 10) + 1;
    addRoom.setAttribute('value', value);
    addRoom.innerHTML = value;

}

function minusOneBathrooms() {
    var subtractRoom = document.getElementById('rooms_amount_bathrooms');
    value = parseInt(subtractRoom.getAttribute('value'), 10) - 1;
    subtractRoom.setAttribute('value', value);
    subtractRoom.innerHTML = value;

}
//INCREMENTS/DECREMENTS KITCHENS BY 1
function plusOneKitchens() {
    var addRoom = document.getElementById('rooms_amount_kitchens');
    value = parseInt(addRoom.getAttribute('value'), 10) + 1;
    addRoom.setAttribute('value', value);
    addRoom.innerHTML = value;

}

function minusOneKitchens() {
    var subtractRoom = document.getElementById('rooms_amount_kitchens');
    value = parseInt(subtractRoom.getAttribute('value'), 10) - 1;
    subtractRoom.setAttribute('value', value);
    subtractRoom.innerHTML = value;

}

        Bedrooms

            <input type="number" class="room_count" id="rooms_amount_bedroom" autocomplete="off" value="0">

        Bathrooms

            <input type="number" class="room_count" id="rooms_amount_bathrooms" autocomplete="off" value="0">

        Kitchens

            <input type="number" class="room_count" id="rooms_amount_kitchens" autocomplete="off" value="0">

I would like to be able to have the same functionality but feel I could have probably done this in a simpler way. I'm new to Javascript/JQuery so any suggestions will be appreciated. Thanks!

Some things could be said about the HTML (no need for hr, border will do; those imgs should be background images on buttons; this is obviously a list; those smalls should be labels; way to many divs; ...) but let me focus on te JS as you are asking.

First thing that jumps out is the repetition. Each function basically does the same thing, but for a different room and with a different amount. Not very DRY at all.

The easy solution would be to pass the room name and the change amount in the function as parameters, and now you only need one function. Something like this:

function changeValue(roomName, amount) { ...

You can them call your function from the onclick attribute like so:

You can now add more rooms without having to change the javascript, and if you decide to change something in your logic you only have to change it once.

Second thing that was already noticed in the comments, you are changing the innerHtml of your inputs, but there is no such thing on inputs (there is no opening and closing tag with 'innerhtml' between them). Changing the value will suffice.

Also, you mention and tag jQuery, but this is vanilla JS, not a line off jQuery in there (which is fine btw!)

Let me close by showing you how my code would look if I had to write it:

HTML:

    bathrooms
    <button data-amount="-1">-</button>
    <input type="number" id="bathroom_count" value="0" autocomplete="off"/>
    <button data-amount="1">+</button>

    bedrooms
    <button data-amount="-1">-</button>
    <input type="number" id="bedroom_count" value="0" autocomplete="off"/>
    <button data-amount="1">+</button>

    kitchens
    <button data-amount="-1">-</button>
    <input type="number" id="kitchen_count" value="0" autocomplete="off"/>
    <button data-amount="1">+</button>

jQuery:

  $('#rooms li').on('click', 'button', function(e) {
    e.preventDefault();
    var $button = $(e.currentTarget);
    var $input = $button.siblings('input');

    $input.val(parseInt($input.val(), 10) + parseInt($button.data('amount'), 10));
  });

I think the code should speak for itself, but feel free to ask if you want me to elaborate.

I hope you learned something from it and happy coding!


Printing the contents of a string array using pointers I'm currently studying C and I'm trying to just print the contents of a string array. I'm using pNames to point to the first char pointer and iterating from there.

A more proper approach would use this pointer, get a char* each time and use printf("%s", pNames[i]) to print a whole string. However, I thought I would try to print it character-by-character inside each string, as follows:

#include <stdio.h>

int main(int argc, char *argv[])
{

char *names[] = {
    "John", "Mona",
    "Lisa", "Frank"
};

char **pNames = names;
char *pArr;
int i = 0;
while(i < 4) {

    pArr = pNames[i];
    while(*pArr != '\0') {
        printf("%c\n", *(pArr++));
    }
    printf("\n");
    i++;
}
return 0;
}

This code kind of works (prints each letter and then new line). How would you make it better?

Given that the code is really simple, I see mostly coding style issues with it.

Instead of this:

char *names[] = {
    "John", "Mona",
    "Lisa", "Frank"
};

I would prefer either of these writing styles:

char *names[] = { "John", "Mona", "Lisa", "Frank" };

// or

char *names[] = {
    "John",
    "Mona",
    "Lisa",
    "Frank"
};

The pNames variable is pointless. You could just use names.

Instead of the while loop, a for loop would be more natural.

This maybe a matter of taste,
but I don't think the Hungarian notation like *pArr is great.
And in any case you are using this pointer to step over character by character,
so "Arr" is hardly a good name.
I'd for go for pos instead. Or even just p.

You should declare variables in the smallest scope where they are used.
For example *pos would be best declared inside the for loop.
In C99 and above, the loop variable can be declared directly in the for statement.

The last return statement is unnecessary.
The compiler will insert it automatically and make the main method return with 0 (= success).

Putting it together:

int main(int argc, char *argv[])
{
    char *names[] = { "John", "Mona", "Lisa", "Frank" };
    for (int i = 0; i < 4; ++i) {
        char *pos = names[i];
        while (*pos != '\0') {
            printf("%c\n", *(pos++));
        }
        printf("\n");
    }
}

Actually it would be more interesting to use argc and argv for something:

int main(int argc, char *argv[])
{
    for (int i = 1; i < argc; ++i) {
        char *pos = argv[i];
        while (*pos != '\0') {
            printf("%c\n", *(pos++));
        }
        printf("\n");
    }
}


Dynamic Array in java I am implementing a class to mimic dynamic array as a part of my learning process of data structures. I have written the following class which works as a dynamic array data structure.
I have gone through some video tutorials and also read some code from Java's ArrayList implementation to understand how to code it in a simple manner. I would like to get the code reviewed from the following perspective:

Is there any design pattern that I should be following
Improvements like removing compile time warning related to generics.
Any tips on including test cases that can expose hidden issues in the code
Any other tips that will make it a better code like improve its performance or make it more modular.

import java.util.Arrays;
import java.util.Iterator;

public class DynamicArray<T> implements Iterable<T> {
  private Object[] elements;
  private int length = 0;
  private int capacity = 0;

  public DynamicArray() {
    this(10);
  }

  public DynamicArray(int capacity) {
    this.capacity = capacity;
    this.length = 0;
    this.elements = new Object[capacity];
  }

  public int size() {
    return length;
  }

  public boolean isEmpty() {
    return size() > 0;
  }

  public T get(int index) {
    validateIndexValue(index);
    return (T)elements[index];
  }

  public void set(int index, T element) {
    validateIndexValue(index);
    elements[index] = element;
  }

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

  public boolean add(T element) {
    ensureCapacity(length + 1);
    elements[length++] = element;
    return true;
  }

  public T removeAt(int index) {
    validateIndexValue(index);
    T element = (T) elements[index];
    removeElement(index);
    return element;
  }

  public boolean remove(T element) {
    if(element == null) {
      for(int i = 0; i < length; i++) {
        if(elements[i] == null) {
          removeElement(i);
          return true;
        }
      }
    } else {
      for(int i = 0; i < length; i++) {
        if(element.equals(elements[i])) {
          removeElement(i);
          return false;
        }
      }
    }
    return false;
  }

  public int indexOf(T element) {
    if(element == null) return -1;
    for(int i = 0; i < length; i++) {
      if(element.equals(elements[i])) {
        return i;
      }
    }
    return -1;
  }

  public boolean contains(T element) {
    return indexOf(element) > -1;
  }

  public java.util.Iterator<T> iterator() {
    return new java.util.Iterator<T>() {
      int index = 0;
      public boolean hasNext() {
        return index < length;
      }

      public T next() {
        return (T) elements[index++];
      }
    };
  }

  private void removeElement(int index) {
    int elementsToMove = length - index - 1;
    if(elementsToMove > 0) {
      System.arraycopy(elements, index + 1, elements, index, elementsToMove);
    }
    elements[--length] = null;
  }

  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity *= 2;
      elements = Arrays.copyOf(elements, capacity);
    }
  }

  private void validateIndexValue(int index) {
    if(index >= length || index < 0) {
      throw new IllegalArgumentException("Bad index value passed : " + index);
    }
  }
}
```

Unit testing
Definitely write some test cases for your code.  JUnit would be one possibility, but there are many test frameworks to choose from.
With any test framework, and at least one test per public method, this goof would have been immediately apparent:
  public boolean isEmpty() {
    return size() > 0;
  }

As Timothy Truckle points out in a comment below, one test per public method is not enough.
Misleading method argument name/implementation
While the way that you used ensureCapacity(length + 1) will work, it hides a subtle bug.
  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity *= 2;
      elements = Arrays.copyOf(elements, capacity);
    }
  }

Consider if you exposed the method ensureCapacity(int minSize) as a public method, like the standard library's ArrayList#ensureCapacity method.  A caller might use:
  var container = new DynamicArray<Integer>();
  container.ensureCapacity(10000);
  // ...

The first statement creates the container, with an initial capacity of 10.  The next statement looks to resize the container to hold 10000 integers, but what actually happens is, since 10000 is larger than the current capacity, the capacity is doubled to 20.
Instead of capacity *= 2; perhaps you would want something more along the lines of:
  private void ensureCapacity(int minSize) {
    if(minSize >= capacity) {
      capacity = Math.max(capacity * 2, minSize);
      elements = Arrays.copyOf(elements, capacity);
    }
  }

Initial Capacity
Even without exposing ensureCapacity(int minSize) as a public function, the following test will cause the bug to appear in a different way, causing a ArrayIndexOutOfBounds exception:
  var container = new DynamicArray<Integer>(0);
  container.add(10);

The initial capacity is zero.  In attempting to add an item, the length + 1 will exceed the capacity of zero, so the capacity will be doubled from zero to ... zero!  Then, elements[length++] = element; will access the first element from an array of length 0.  Oops.
You could prevent this with validation in the constructor ...
    if(capacity <= 0)
      throw new IllegalArgumentException("Capacity must be positive");

With the capacity = Math.max(capacity * 2, minSize); fix, this could be relaxed to allow an initial capacity of zero:
    if(capacity < 0)
      throw new IllegalArgumentException("Capacity cannot be negative");

Iteration
You define an Iterator for your DynamicArray, but if the array is modified while your iterator is in flight over the list, odd things may happen.
For example: If you have a DynamicArray<String> containing "foo", "bar" and "baz", you might create the iterator and retrieve the first item: "foo".  If you then performed .removeElement(0), the next element returned by the iterator would be "baz", not "bar"!
The standard collections will raise a ConcurrentModificationException in these cases.  They achieve this by maintaining a modCount in the container.  Each .add() or .remove() operation would increment this by one.  When the iterator is created, it captures the current modCount value for the container.  On every iterator operation, it checks to see if the modCount has unexpectedly changed, and if so, raise the exception.
Compile time warnings related to generics
You can add @SuppressWarnings("unchecked") annotation to a statement, method, or an entire class.  Ideally, you should apply the annotations to the smallest possible scopes to avoid accidentally suppressing warnings you didn't intend to.
See this answer


Faster JavaScript fuzzy string matching function? I'm using the following function to fuzzy match strings:

function fuzzy_match(str,pattern){
    pattern = pattern.split("").reduce(function(a,b){ return a+".*"+b; });
    return (new RegExp(pattern)).test(str);
};

Example:

fuzzy_match("fogo","foo") //true
fuzzy_match("jquery.js","jqjs") //true
fuzzy_match("jquery.js","jr") //false

It's very slow, though. How can I optimize that function?

function fuzzy_match(str,pattern){
    pattern = pattern.split("").reduce(function(a,b){ return a+".*"+b; });
    return (new RegExp(pattern)).test(str);
};

String concatenation is slow. The reason is that you need to allocate new memory anytime you concatenate two strings. A smart compiler may optimise that,  but not too much. However, what you are trying to do with that reduce already exists, and it's called join:

pattern = pattern.split("").join(".*")

The regex itself can be optimised: .* initially grabs as much as possible, then retracts only if the rest doesn't match. This takes a larger than neccessary amount of backtracking to find out. Instead, you could use a reluctant quantifier: .*?. This attempts to match as little as possible. If a match is found, it is found without backtracking. However, it still does a lot of backtracking if there is no match. We can do better: a[^b]*b (at this point, it doesn't really matter if the quantifier is greedy). A possessive quantifier (a[^b]*+b) would be even better, but javascript doesn't support these. Using a character class deprives us of a join, but see the next point.

pattern = pattern.split("").reduce(function(a,b){ return a+'[^'+b+']*'+b; });

Since you are complaining about an operation that takes about 3000 ns (as noted in the comments), it can be assumed you are doing a lot of queries. If there are very few patterns, you can cache your regexes. Underscore.js has a handy function that I'll demonstrate, but you could easily build the cache yourself.

var cache = _.memoize(function(pattern){
  return new RegExp(pattern.split("").reduce(function(a,b){
    return a+'[^'+b+']*'+b;
  })
})
function fuzzy_match(str,pattern){
  return cache(pattern).test(str)
};

If there is a lot of repetition among the tested strings, you should use these as a pattern instead, and the pattern as the tested string. This is even easier. I will also demonstrate how to scope your variables using the export pattern. Also, a bugfix must be inserted here (we can't assume all characters in the string are alphanumeric), to properly escape non-alphanumeric characters:

var fuzzy_match = (function(){
  var cache = _.memoize(function(str){
    return new RexEgp("^"+str.replace(/./g, function(x){
      return /[\-\[\]\/\{\}\(\)\*\+\?\.\\\^\$\|]/.test(x) ? "\\"+x+"?" : x+"?";
    })+"$");
  })
  return function(str, pattern){
    return cache(str).test(pattern)
  })
})()

Concerning the last regex:

Given some pattern "ace", the regex you build (/a.*c.*e/) tests if the string contains the characters of the pattern in the string, in the correct order.

If you want to test if a given string "abcde" is matched some pattern: The pattern must only contain the characters of the string, in the correct order: /^a?b?c?d?e?$/. To do this, we regex-escape every regex special character (pattern source: CoolAj86), make every character optional (?), and flank the regex with string boundary anchors.


Picking random lines out of text files So I was doing something which creates an airplane with an actual airline code, number, airplane type and so on.
The airline code and airplane type are stored in a txt file so I can add more later to my leisure... but the code I came up with to get a random line is extremely messy. Is there a better way? I searched all over stackexchange but it all seemed quite complex for little files which will have only (if ever) a couple dozen lines of content.

public String generate() {

    int totalLines = 0;
    File file = new File("icaocodes.txt");

    BufferedReader br = null;

    try {
        br = new BufferedReader(new FileReader(file));

        while ((br.readLine()) != null) {
            totalLines++;
        }
        br.close();

        br = new BufferedReader(new FileReader(file));

        Random random = new Random();
        int randomInt = random.nextInt(totalLines);
        int count=0;
        String icaocode;
        while ( (icaocode = br.readLine()) != null) {
            if (count == randomInt) {
                br.close();
                return icaocode;
            }
            count++;
        }
         br.close();

    } catch (FileNotFoundException e) {
        System.out.println("File not found: " + file.toString());
    } catch (IOException e) {
        System.out.println("Unable to read file: " + file.toString());
    }

    return "Puppies";

}

Naive Solution

(I say naive because of the assumption that the file you are working with is small. From a general design standpoint, it is usually best to prepare for the worst case and assume you may have to read a super long file at some point in time.)

Read the file line by line into a List or a Map, then fetch a random entry from here. (Judging by the brief details of what you're working on, a Map of different objects might be a good choice if you'd like to parse a file into different objects for flights, etc.)

Probably Better Solution

There's a good discussion over here about Reservoir Sampling.

Side notes

Because you posted in Code Review...

Split the reading from the BufferedReaders into separate try-catch blocks. This is just good practice, as in some cases your program may be able to continue executing even if an exception is thrown.
Close your readers in a finally. Check out this post on closing readers
Make file final.
I'm assuming you just slapped the "Puppies" in the return statement, but if you post more complete code, you can get comments and suggestions on all of your code, not just your approach to finding a random line :)


Computational verification of Collatz conjecture using gmplib Prerequisites

The unsigned long type has a size of 64 bits.

The following macros are defined.

/* all 3^n for n < 41 fits into 64-bit unsigned long */
#define LUT_SIZE 41
/* any reasonably high number */
#define LUT_SIZEMPZ 512

The following array is defined and properly initialized with corresponding values.

/* lut[n] contains 3^n */
mpz_t lut[LUT_SIZEMPZ];

Additionally, the following auxiliary function is defined.

/* count trailing zeros */
mp_bitcnt_t mpz_ctz(const mpz_t n)
{
    return mpz_scan1(n, 0);
}

Problem

This code review request follows my previous request Computational verification of Collatz conjecture. The implementation in this request should handle the numbers which cannot be handled with the code in previous post.

In short: My program verifies the convergence of the Collatz problem, using this algorithm. The convergence for all values n ≤ 87 × 260 has already been proven.

The following function is called for n of the form \$4n+3\$, in order from the smallest one to the largest one, only if all preceding calls returned zero.

This function should either

return 0 if the problem for the n is convergent, or
loop infinitely if the trajectory for the n is cyclic.

Code

The 128-bit input n is split into two 64-bit parts nh and nl such that n = nh * 2^64 + nl.

int check_convergence(unsigned long nh, unsigned long nl)
{
    mpz_t n;
    mpz_t n0;
    mpz_t n_max;
    mp_bitcnt_t e;

    mpz_init_set_ui(n, nh);
    mpz_mul_2exp(n, n, (mp_bitcnt_t)64);
    mpz_add_ui(n, n, nl);

    mpz_init_set_ui(n_max, 87UL);
    mpz_mul_2exp(n_max, n_max, (mp_bitcnt_t)60);

    mpz_init_set(n0, n);

    do {
        if (mpz_cmp(n, n_max) <= 0) {
            mpz_clear(n);
            mpz_clear(n0);
            mpz_clear(n_max);
            return 0;
        }

        mpz_add_ui(n, n, 1UL);

        e = mpz_ctz(n);

        mpz_fdiv_q_2exp(n, n, e);

        assert( e < LUT_SIZEMPZ );

        mpz_mul(n, n, lut[e]);

        mpz_sub_ui(n, n, 1UL);

        mpz_fdiv_q_2exp(n, n, mpz_ctz(n));

        if (mpz_cmp(n, n0) < 0) {
            mpz_clear(n);
            mpz_clear(n0);
            mpz_clear(n_max);
            return 0;
        }
    } while (1);
}

If you need a type with exactly 64 bits, use uint64_t (from <stdint.h>).  That will give a clear compilation error if no such type is available.

Given that the function never returns anything other than zero, we can move the cleanup of n, n0 and n_max outside the loop, and simply break to reach them.

Is indefinite looping really a good output if a cycle is detected?  How is that distinguishable from an arbitrarily long (but finite) chain?  Look up the standard algorithms for cycle detection in your graph theory textbook.


Generating a not-the-same-as-last-time random number I have to generate random number which differs from the number generated last time.

Which of these two variants is better? Or maybe you can suggest better implementation.

int generateRandom() {
    int randomNumber;
    do {
        randomNumber = random.nextInt(UPPER_BOUND);
    } while (randomNumber == lastRandomNumber);
    lastRandomNumber = randomNumber;
    return randomNumber;
}

vs

int generateRandom() {
    while (true) {
        int randomNumber = random.nextInt(UPPER_BOUND);
        if (randomNumber != lastRandomNumber) {
            lastRandomNumber = randomNumber;
            return randomNumber;
        }
    }
}

Neither option is great. Looking at the second option first (because it is the worst, in my opinion):

int generateRandom() {
    while (true) {
        int randomNumber = random.nextInt(UPPER_BOUND);
        if (randomNumber != lastRandomNumber) {
            lastRandomNumber = randomNumber;
            return randomNumber;
        }
    }
}

This contains a seemingly infinite loop. while(true) is often an indication that there's a better way to do things (not necessarily always, but in this case, yes). The reason it is a problem here is because it gives the impression that the loop repeats often, when, in fact, it seldom repeats ever.

The first block is better:

int generateRandom() {
    int randomNumber;
    do {
        randomNumber = random.nextInt(UPPER_BOUND);
    } while (randomNumber == lastRandomNumber);
    lastRandomNumber = randomNumber;
    return randomNumber;
}

This is better because the loop-terminating condition is much cleaner, more visible. The logic-path through the method is traditional. Still, it's not great. I dislike the need to declare the randomNumber variable as a separate declaration.

The 'while loop' solution would be more readable (even though it duplicates the nextInt() call), as:

int generateRandom() {
    int randomNumber = random.nextInt(UPPER_BOUND);
    while (randomNumber == lastRandomNumber) {
        randomNumber = random.nextInt(UPPER_BOUND);
    }
    lastRandomNumber = randomNumber;
    return randomNumber;
}

Even with the code duplication, it makes it clear that the normal case is handled, and then the while loop is a recovery process.

@Pimgd suggested sending the lastRandomNumber in as a parameter, and @maartinus suggested a single if-block condition rather than a while loop solution. In principle these are both good ideas. There is a way to make it completely reentrant, and also a way to remove the while-loop and the id-conditionals. My solution would be:

int generateRandom(int lastRandomNumber) {

    // add-and-wrap another random number to produce a guaranteed
    // different result.
    // note the one-less-than UPPER_BOUND input
    int rotate = 1 + random.nextInt(UPPER_BOUND - 1);
    // 'rotate' the last number
    return (lastRandomNumber + rotate) % UPPER_BOUND;

}

@mjolka pointed out that if UPPER_BOUND is large, it is possible for the values to overflow in the sum, and that the better solution would be:

return ((lastRandomNumber + rotate) & Integer.MAX_VALUE) % UPPER_BOUND;


Recording loans of access cards to people in a company I'm fairly new to Python and currently building a small application to record loans of access cards to people in a company. I'm using wxPython for the GUI and SQLAlchemy for the CRUD. I'm loosely following Mike Driscoll's tutorial for a similar application but I want to add some extra things that he hasn't implemented (he has most controls in the same window, but I'm passing things a lot between dialogues and windows and it's starting to look messy).

Particularly concerned about the following method in dialogs.py:

def OnCardReturn(self, event):
    """
    Call the controller and get back a list of objects. If only one object
    return then set that loan as returned. If none returned then error, no
    loans currently on that card. If more than one returned something has
    gone wrong somewhere, but present a list of the loans against that card
    for the user to pick the correct one to return.
    """

    value = self.txtInputGenericNum.GetValue()
    loans = controller.getQueriedRecords(self.session, "card", value)    #returns a list of objects
    numLoans = len(loans)
    if numLoans == 1:
        controller.returnLoan(self.session, value)    #returns nothing
        successMsg = "Card " + str(value) + " has been marked as returned"
        showMessageDlg(successMsg, "Success!")
    elif numLoans == 0:
        failureMsg = "Card " + str(value) + " is not currently on loan"
        showMessageDlg(failureMsg, "Failed", flag="error")
    elif numLoans > 1:
        failureMsg = """
        More than one loan for " + str(value) + " exists. Please select
        the correct loan to return from the next screen.
        """
        showMessageDlg(failureMsg, "Failed", flag="error")
        selectReturnLoan = DisplayList(parent=self, loanResults=loans,
                                                        returnCard=True)
        selectReturnLoan.ShowModal()
        selectReturnLoan.Destroy()

The controller is still under construction, so no complete code yet, but I've commented in what is returned by the calls to it so it's still possible to see what the functionality is.

Inline comments should only be used sparingly, and definitely not on already long lines. Your #returns a list of objects is pretty unnecessary both because it's overly long, but also because it's inferrable and doesn't seem to matter. You only pass the loans on unchanged so the user doesn't care that they're a list of objects. You can infer that it's a collection of something because of the name loans and the len usage. And that's all you need to know in this function, so forget that comment.

You should also format your docstring so it contains just one line summarising the function, a blank line and then the further details. You just have one long block but it's hard to read from it what the function should do. Instead you detail the possible results.

Instead of using str and concatenation, just use str.format. It's a convenient way of formatting strings and coverting their type at the same time:

    successMsg = "Card {} has been marked as returned".format(value)

Also note that you haven't correctly inserted this value in the failureMsg of numLoans > 1. You just have the string literal " + str(value) + ". You'd need the extra quotation marks to do it your way:

    failureMsg = """
    More than one loan for """ + str(value) + """ exists. Please select
    the correct loan to return from the next screen.
    """

But instead I'd suggest using str.format again.


Given a set of random strings, write a function that returns a set that groups all the anagrams together in objective-c I would like to get feedback on the solution and a question regarding Big O.
I am first converting each character in the string into the array and that would be O(n) then i am sorting the array O(n log n) and then I join back the array.  Not sure if that is O(n).  After i get the sorted string I would retrieve the NSArray from NSDictionary if it is there and either add the word to the array or create a new array and then set it back into the NSDictionary.  I would those operations are O(1).  The total runtime complexity is O(N log N) because of sort. Is that the correct breakdown.

void printAllAnagrams(NSArray *words)
{
    NSMutableDictionary *anagramsDictionary = [[NSMutableDictionary alloc]init];
    NSMutableArray *wordArray = [[NSMutableArray alloc]init];

    for(NSString *word in words){

        //Loop through each word
        for(int i = 0;i < [word length]; i++){
            //create a character array
            [wordArray addObject:[NSString stringWithFormat:@"%c",[word characterAtIndex:i]]];
        }

        //sort character array
        [wordArray sortUsingSelector:@selector(localizedCompare:)];
        //convert character array back to string to use it as a key for in the dictionary
        NSString *sortedString = [wordArray componentsJoinedByString:@""];
        NSMutableArray *anagramStrings =[[anagramsDictionary objectForKey:sortedString] mutableCopy];

        if(anagramStrings){
            //if anagram(s) of the word is already in the dictionary then add this word to the array
            //and store it back into the dictionary
            [anagramStrings addObject:word];
            [anagramsDictionary setObject:anagramStrings forKey:sortedString];
        }else{
            //create an array with current word and store it in the dictionary
            //using the sorted characters string as the key
            [anagramsDictionary setObject:@[word] forKey:sortedString];
        }
        [wordArray removeAllObjects];
    }
    NSLog(@"%@",anagramsDictionary);
}

This would be a better way to do the final storage into the dictionary. Attempt to retrieve an existing list. If it does not exist, create it and add it to the dictionary. You can then unconditionally add the current word to the array.

NSString *sortedString = [wordArray componentsJoinedByString:@""];

// Attempt to retrieve existing list
NSMutableArray * anagramStrings = [anagramsDictionary objectForKey:sortedString];
if( !anagramStrings ){
    // If it does not exist, create it and put it into the dictionary
    anagramStrings = [NSMutableArray array];
    [anagramDictionary setObject:anagramStrings forKey:sortedString];
}

// Add to the list
[anagramStrings addObject:word];

[wordArray removeAllObjects];

This avoids doing a copy every time, which in your original code is unnecessary in all cases but one.

Also worth noting is the last line here:

if(anagramStrings){
    //if anagram(s) of the word is already in the dictionary then add this word to the array
    //and store it back into the dictionary
    [anagramStrings addObject:word];
    [anagramsDictionary setObject:anagramStrings forKey:sortedString];
}

There is no need to put the mutable array back into the dictionary after getting a pointer to it, as you're doing. The array is not removed from the dictionary; your anagramStrings points to that exact same array.


Pygame snake as first game After poking around in some areas of python, I've decided to try Pygame. After about two hours of coding, this is what I came up with:

import pygame
import time
import random
pygame.init()
pygame.font.init()

WINDOW = pygame.display.set_mode((500, 500))

pygame.display.set_caption('snake')

FOOD_COORS = []

TICK = 15

RUN = True
SNAKE_COMP = [[50, 50, 2], [40, 50, 2], [30, 50, 2], [20, 50, 2], [10, 50, 2]]
f = [random.randint(0, 50)*10, random.randint(0, 50)*10]
d = 2
CLOCK = pygame.time.Clock()

def hit():
    time.sleep(3)
    pygame.quit()

class snake():
    def __init__(self, SNAKE_COMP):
        self.x, self.y = SNAKE_COMP[0][0:2]
    def draw(self, SNAKE_COMP):
        self.SNAKE_COMP = SNAKE_COMP
        for i in range(0, len(SNAKE_COMP)):
            pygame.draw.rect(WINDOW, (255, 255, 255), (SNAKE_COMP[i][0], SNAKE_COMP[i][1], 10, 10))

    def hit_check(self, SNAKE_COMP):
        self.SNAKE_COMP = SNAKE_COMP
        if SNAKE_COMP[0][0] >= 500 or SNAKE_COMP[0][0] < 0:
            hit()
        if SNAKE_COMP[0][1] >= 500 or SNAKE_COMP[0][1] < 0:
            hit()
        test_l = [[]]
        for i in range(0, len(SNAKE_COMP)):
            test_l.append(tuple(SNAKE_COMP[i][0:2]))
        for i in range(0, len(test_l)):
            if test_l.count(test_l[i]) > 1:
                hit()

class food():
    global FOOD_COORS
    def draw(self):
        x, y = self.x, self.y
        pygame.draw.rect(WINDOW, (255, 255, 255), (x, y, 10, 10))
    def spawn(self, SNAKE_COMP):
        global FOOD_COORS
        self.SNAKE_COMP = SNAKE_COMP
        test_l = [[]]
        for i in range(0, len(SNAKE_COMP)):
            test_l.append(SNAKE_COMP[i][0:2])
        g = True
        while g:
            x = random.randint(0, 49)*10
            y = random.randint(0, 49)*10
            if [x, y] not in test_l:
                g = False
        FOOD_COORS = [x, y]
        self.x, self.y = x, y
snek = snake(SNAKE_COMP)
apple = food()
apple.spawn(SNAKE_COMP)
s = False
g = False
while RUN:
    CLOCK.tick(TICK)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            RUN = False

    keys = pygame.key.get_pressed()
    if keys[pygame.K_UP] and d != 3:
        d = 1
    elif keys[pygame.K_RIGHT] and d != 4:
        d = 2
    elif keys[pygame.K_DOWN] and d != 1:
        d = 3
    elif keys[pygame.K_LEFT] and d != 2:
        d = 4
    if g != True and SNAKE_COMP[0][0:2] != FOOD_COORS:
        last = len(SNAKE_COMP) - 1
        for i in range(1, len(SNAKE_COMP)):
            SNAKE_COMP[len(SNAKE_COMP)-i][2] = SNAKE_COMP[len(SNAKE_COMP)-i-1][2]
        SNAKE_COMP[0][2] = d
        for i in range(0, len(SNAKE_COMP)):
            if SNAKE_COMP[i][2] == 1:
                SNAKE_COMP[i][1] -= 10
            elif SNAKE_COMP[i][2] == 2:
                SNAKE_COMP[i][0] += 10
            elif SNAKE_COMP[i][2] == 3:
                SNAKE_COMP[i][1] += 10
            elif SNAKE_COMP[i][2] == 4:
                SNAKE_COMP[i][0] -= 10
    else:
        k = SNAKE_COMP[0][2]
        FOOD_COORS.append(k)
        if k == 1:
            FOOD_COORS[1] -= 10
        elif k == 2:
            FOOD_COORS[0] += 10
        elif k == 3:
            FOOD_COORS[1] += 10
        elif k == 4:
            FOOD_COORS[0] -= 10
        SNAKE_COMP.insert(0, FOOD_COORS)
        apple.spawn(SNAKE_COMP)
    snek.hit_check(SNAKE_COMP)
    apple.draw()
    snek.draw(SNAKE_COMP)
    pygame.display.update()
    WINDOW.fill((0, 0, 0))

pygame.quit()

I definitely thinks this can be improved, just not sure how.

This isn't really todo with the code, but, it's always a good idea to add comments to your code to make it more readable and understandable.


Dining Philosophers Problem in Clojure I have implemented the Dining Philosophers Problem in Clojure with refs, trying to emphasize readability. Please point out if parts of it are inefficient, not idiomatic, or improvable in any way. Full code on GitHub.

;;;;;;;;;;;;;;;;;;;;
;;     DINING     ;;
;;  PHILOSOPHERS  ;;
;;     PROBLEM    ;;
;;;;;;;;;;;;;;;;;;;;
(ns concurrency.dining-philosophers
  (:gen-class)
  (:require [clojure.core.async :refer [go chan >!! <!!]]))

(def n-philosophers 5)
(def max-eating-time 3000)
(def max-thinking-time 2000)
(def retry-time 5)
(def forks (for [_ (range 0 n-philosophers)]
             (ref false)))

;; We use a core async channel to implement a logger that writes
;;  to the terminal. It will run on the main thread
(def logger-chan (chan))

(defn log [& xs]
  (>!! logger-chan (apply str xs)))

(defn logger [channel]
  (println "Ready to log...")
  (while true
    (let [msg (<!! channel)]
      (println msg))))

;; The philosopher function contains the main logic of the application
(declare get-forks eat think wait-retry-time)
(defn philosopher
  "Given a philosopher's location n at the table, tries to pick up both
    forks simultaneously and eat. When he is finished eating he thinks
    for a while. If he cannot pick up both forks, he retries after a while.
   This function runs in a thread"
  [n]
  (log "Philosopher " n " just sat down")
  (while true
    (if (get-forks n)
      (do (log "Philosopher " n " picked up forks")
          (eat n)
          (think n))
      (wait-retry-time))))

(declare get-fork left-fork right-fork release-fork)
(defn get-forks
  "We try to get the left fork first, and then the right fork. If we succeed
    in getting the left fork but not the right, we drop the left fork.
   Returns true if we succeed in getting both forks and false otherwise."
  [n]
  (dosync
   (if (get-fork (left-fork n))
     (if (get-fork (right-fork n))
       true
       (release-fork (left-fork n)))
     false)))

(defn get-fork [fork]
  (if @fork
    nil
    (ref-set fork true)))

(defn left-fork [n]
  (nth forks (mod (dec n) n-philosophers)))

(defn right-fork [n]
  (nth forks n))

(defn release-fork [fork]
  (ref-set fork false))

(declare release-forks)
(defn eat [n]
  (log "Philosopher " n " is dining")
  (Thread/sleep (rand-int max-eating-time))
  (release-forks n)
  (log "Philosopher " n " dropped forks"))

(defn release-forks [n]
  (dosync
    (release-fork (left-fork n))
    (release-fork (right-fork n))))

(defn think [n]
  (log "Philosopher " n " is thinking")
  (Thread/sleep (rand-int max-thinking-time)))

(defn wait-retry-time []
  (Thread/sleep retry-time))

(defn -main []
  (println "Starting main")
  (dotimes [i n-philosophers]
    (.start (Thread. #(philosopher i))))
  (logger logger-chan))
(-main)

Idiosyncrasies

declareing your fns

It's pretty unusual to declare all of your functions before defining them.

It appears that you did it so that you could define your functions in the order you thought
most appropriate. That's common for newcomers, and it's certainly something many people are
used to. To be clear, there's nothing wrong with wanting that.

However, most clojure programs work within this constraint and just define things in the
order they are needed. After a while you become accustomed to seeing things in that order,
and you start to look at the bottom of the file for the program overview. This has the
minor benefit of calling out the places where circular references are actually needed.

Manually calling -main

This is a toy program, so calling -main in your namespace probably does what you want 100%
of the time. However, in a real codebase, doing that can pretty much make your namespace
unusable for other namespaces. If you're using lein you can call:

lein run -m concurrency.dining-philosophers

If you're running raw clojure use:

java -cp "clojure.jar:$OTHER_JAR_PATHS" clojure.main -m concurrency.dining-philosophers

Program Structure

Decouple Philosophers

Your philosophers are aware of a lot of implementation details. Really all they care
about is their name, their left fork, and their right fork. You transmit all of that information
in a single number, which is convenient, but it means you have to be concerned with how
forks are retrieved in the philosopher code as opposed to just using the forks you're assigned.

The consequence of this is it binds your functions together in an undesirable way.

Leverage Sequences

Your solution uses a lot of indices and math to manipulate those indices. It could be made
dramatically simpler by manipulating sequences instead. (Hint: Use the above advice and the
partition function.)

Microfunctions

This is a really common thing for newcomers to clojure, myself included.

When I did a lot of Java, I tended to like very small functions, and I would create arbitrary
functions (e.g. get-fork, release-fork and wait-retry-time) for no other reason than to cut
down on my line count. After working with clojure for a while, function length became less important
than overall comprehensibility. So what I try and do now is look for fundamental concepts in my
program as opposed to places where I can inject a random function.

For example, for this problem, I see get-forks, release-forks, eat, and think as primitives.
They are things that are inherent to the problem. You may or may not name them, but they are definitely
there.

You never really want to get a single fork at one time, so get-fork seems too small to be a standalone
concept. The same for release-fork. wait-retry-time is just a pseudonym for (Thread/sleep retry-time). The latter is going
to be more obvious to any newcomer to the codebase.

General Comments

Use of core.async

Just to let you know, since you pulled in core.async, it's possible to do a lot of the
mechanics around starting/stopping threads with core.async. This has a couple of advantages:

Removes the need to use Java constructs like Thread/sleep, .start, .wait. (As far as I know, this is really just an aesthetic advantage)
Allows you to easily interact with processes (i.e. start them and stop them) (Another potential option here is Java's Executor
infrastructure.)

So it's not a massive gain, but the option is there if you choose.

No cleanup mechanism

While we're on the topic of interacting with the processes, the current structure doesn't
leave any hooks for cleaning up your threads. This works fine for a toy program where you'll
let it run then ctrl-c, but any real-world system will need to handle that
cleanly. So it might be nice for you to use the opportunity to think about how to structure the
program so you can clean up on demand.

Unbuffered logger-chan

Since your logger-chan is an unbuffered chan you've introduced synchrony around your logging
when you probably want some asynchrony there. I can't see any harm in setting a buffer of ~100 or
~1000 on that channel. It'll almost certainly be way ahead of its workload, and in the event it gets
behind, it'll still give some backpressure so you won't lose any events.

Closing Thoughts

I really like that you chose clojure's STM system for this problem. It's not often used, but by
far the best fit. Also, despite my nitpicking, the big picture flow of philosopher is straightforward
in the best kind of way.

Please let me know if you have any questions about my comments. I'm more than happy to give further feedback!

Edit in response to OPs comments

go-block lockup

You only get lock up if you occupy the thread (e.g. with Thread/sleep, or by doing IO or doing a CPU-intensive process). If you "park" it with (<! (a/timeout msecs)) it doesn't block the state machine.

core.async vs future

I was referring to the thread macro. I don't think there's any substantial benefit to core.async over the futures with and Executor. I actually did a version with ExecutorService and Future, and it has the same feature set. FWIW I think it's also more concise than the version I did with core.async.

However, it is very beneficial to use one of those two over Thread/start and Thread/wait. Those are pretty rudimentary constructs. And they suck for most use cases.

Function Size

You pose a really good point regarding get-fork. You do indeed want to eliminate repetition where possible (though not at the expense of simplicity). I would agree that in the current implementation, get-fork needs to be its own function. However, I don't think getting a single fork is necessary for a solution to this problem.


Using bluepy to send and read serial data I am trying to use bluepy to write and read serial data to/from an HC-08 Bluetooth module. The HC-08 is connected to a device that returns a fixed number of bytes whenever it receives a message over the HC-08.
Below is my code so far. This seems to work—however, I kind of winged this code from examples and an a lot of trial and error. I am not entirely sure what I am doing. Therefore, any comments/feedback for potential improvements would be very welcome. The code is implemented as a class myhc08 that has a write method. This method writes a string to the hc08 and then reads out a set number of bytes.
import struct
import bluepy.btle as btle
from matplotlib import pyplot

class ReadDelegate(btle.DefaultDelegate):
    def __init__(self):
        self.data = b''

    def reset(self):
        self.data = b''

    def handleNotification(self, cHandle, data):
        self.data = self.data + data

    @property
    def data_length(self):
        return len(self.data)

class myHC08:
    def __init__(self):
        self.mac = '34:14:B5:50:34:77'
        self.write_service_id = 4
        self.write_service = None
        self.peripheral = btle.Peripheral(self.mac)
        self.delegate = ReadDelegate()
        self.peripheral.withDelegate(self.delegate)

    def connect(self):
        s = self.write_service_id
        services = self.peripheral.getServices()
        self.write_service = self.peripheral.getServiceByUUID(list(services)[s].uuid)

    def write(self, message, min_bytes, unpack_string=False):
        print('Writing:', message)
        self.delegate.reset()
        c = self.write_service.getCharacteristics()[0]
        c.write(bytes(message, "utf-8"))
        print('Receiving %i bytes' % min_bytes)
        while self.peripheral.waitForNotifications(1): pass
        while self.delegate.data_length < min_bytes: pass
        received = self.delegate.data
        if unpack_string: received = struct.unpack(unpack_string,received)
        return received

    def disconnect(self):
        self.peripheral.disconnect()

bt = myHC08()
bt.connect()
r = bt.write('1*', 1250*2, '1250H')
bt.disconnect()

In case this helps, my computer lists the following UUIDs for the HC-08 device:
00001800-0000-1000-8000-00805f9b34fb Generic Access
00001801-0000-1000-8000-00805f9b34fb Generic Attribute
0000180a-0000-1000-8000-00805f9b34fb Device Information
0000ffe0-0000-1000-8000-00805f9b34fb Unknown
0000fff0-0000-1000-8000-00805f9b34fb Unknown

Concatenation
In computer science terms, depending on a lot of things, this:
    self.data = self.data + data

can be worst-case O(n^2). This happens when the Python runtime needs to work reallocating everything in the existing buffer before it's able to add new data. One way around this is to use BytesIO instead.
Casting to a list
Based on the documentation:

getServices() / Returns a list of Service objects

Since it's already a list, there is no need to re-cast to a list here:
    self.write_service = self.peripheral.getServiceByUUID(list(services)[s].uuid)

Disconnection safety
Since myHC08 has a disconnect method, it should be made into a context manager, and used in a with statement; or at the least:
bt.connect()
try:
    r = bt.write('1*', 1250*2, '1250H')
finally:
    bt.disconnect()