Find first bad version (part 2) This is new code based on some new ideas to reduce calls to is_bad_version. Refer to the previous version of the code discussion from here.

Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated. My major idea is divide and conquer like a binary search/quick select.

Problem:

  You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Source code:

def is_bad_version(number):
    if number == 0:
        return False
    else:
        return True

def find_first_bad_index(numbers):
    start = 0
    end = len(numbers) - 1
    if start == end:
        if is_bad_version(numbers[start]):
            return start
        else:
            raise Exception('all good!')
    while start < end:
        mid = start + (end - start) / 2
        if is_bad_version(numbers[mid]):
            end = mid
        else:
            start = mid + 1
    if start == end:
        if is_bad_version(numbers[start]):
            return start
        else:
            raise Exception('all good!')

if __name__ == "__main__":
    print find_first_bad_index([0,0,0,1,1,1,1,1])
    print find_first_bad_index([0,0,0,0,0,0,0,1])

Document your code in the code. If trying to stick to all pertaining PEPs gets too much, have a look at Code Documentation Advice.

If you don't want to go with bisect
(noteworthy simplifications/improvements (esp. over/of VersionWrap), anyone? Please edit.)

from bisect import bisect
from functools import total_ordering

class NoBadVersion(Exception):
    """Home brewed exception to diferentiate from other
    kind of exceptions and avoid too generic except clauses.
    """

@total_ordering
class VersionWrap:
    """Support version designator comparison"""
    __slots__ = 'version', 'bad'
    def __init__(self, v, b = None):
        self.version = v
        self.bad = b
    def is_bad(self):
        if self.bad is None:
            self.bad = is_bad_version(self.version)
        return self.bad
    def __eq__(self, other):
        return other.is_bad() == self.is_bad()
    def __lt__(self, other):
        return not self.is_bad() and other.is_bad()

def find_first_bad_index(numbers):
    """Find the first bad version

    Assumes is_bad_version(numbers[i]) implies
     is_bad_version(numbers[i+n]) for every natural number n.
    numbers is a sequence of version designators,
    suitable as parameters to is_bad_version().

    Returns the lowest b such that is_bad_version(numbers[b])
    """
    firstNonGood = bisect([VersionWrap(vd) for vd in numbers],
                          VersionWrap(None, False))
    if firstNonGood == len(numbers):
        raise NoBadVersion('none bad!')

    return firstNonGood

, stay with

"""Find the first bad version

Keep number of calls to is_bad_version() at minimum.
"""

class NoBadVersion(Exception):
    """Home brewed exception to diferentiate from other
    kind of exceptions and avoid too generic except clauses.
    """

def is_bad_version(number):
    """dummy for an external predicate costly to evaluate"""
    return number

def find_first_bad_index(numbers):
    """Find the index of the first bad version

    Assumes is_bad_version(numbers[i]) implies
    is_bad_version(numbers[i+n]) for every natural number n.
    numbers is a sequence of version designators,
    suitable as parameters to is_bad_version().

    Returns the lowest b such that is_bad_version(numbers[b])
    """
    start = 0
    end = len(numbers)

    while start < end:
        mid = start + (end - start) // 2
        if is_bad_version(numbers[mid]):
            end = mid
        else:
            start = mid + 1

    if start == len(numbers):
        raise NoBadVersion('none bad!')
    return start

if __name__ == "__main__":
    numbers = [1] * 7
    for good in range(len(numbers)+1):
        print(find_first_bad_index(numbers))
        numbers[good] = 0


SIMD memcpy assembler implementation I am fairly rusty with assembler, let alone the AT&T syntax. I would appreciate it if someone with more experience could please review the following memcpy implementation. Note that this will only ever be called with aligned data.

inline static void alignedMemcpySSE(void *dst, const void * src, size_t length)
{
#if defined(__x86_64__) || defined(__i386__)
  size_t rem = (7 - ((length & 0x7F) >> 4)) * 10;
  void * end = dst + (length & ~0x7F);

  __asm__ __volatile__ (
   // save the registers we intend to alter, failure to do so causes problems
   // when gcc -O3 is used
   "push        %[dst]\n\t"
   "push        %[src]\n\t"
   "push        %[end]\n\t"

   "cmp         %[dst],%[end] \n\t"
   "je          remain_%= \n\t"

   // perform 128 byte SIMD block copy
   "loop_%=: \n\t"
   "vmovaps     0x00(%[src]),%%xmm0 \n\t"
   "vmovaps     0x10(%[src]),%%xmm1 \n\t"
   "vmovaps     0x20(%[src]),%%xmm2 \n\t"
   "vmovaps     0x30(%[src]),%%xmm3 \n\t"
   "vmovaps     0x40(%[src]),%%xmm4 \n\t"
   "vmovaps     0x50(%[src]),%%xmm5 \n\t"
   "vmovaps     0x60(%[src]),%%xmm6 \n\t"
   "vmovaps     0x70(%[src]),%%xmm7 \n\t"
   "vmovntdq    %%xmm0,0x00(%[dst]) \n\t"
   "vmovntdq    %%xmm1,0x10(%[dst]) \n\t"
   "vmovntdq    %%xmm2,0x20(%[dst]) \n\t"
   "vmovntdq    %%xmm3,0x30(%[dst]) \n\t"
   "vmovntdq    %%xmm4,0x40(%[dst]) \n\t"
   "vmovntdq    %%xmm5,0x50(%[dst]) \n\t"
   "vmovntdq    %%xmm6,0x60(%[dst]) \n\t"
   "vmovntdq    %%xmm7,0x70(%[dst]) \n\t"
   "add         $0x80,%[dst] \n\t"
   "add         $0x80,%[src] \n\t"
   "cmp         %[dst],%[end] \n\t"
   "jne         loop_%= \n\t"

   "remain_%=: \n\t"

   // copy any remaining 16 byte blocks
#ifdef __x86_64__
   "leaq        (%%rip), %[end]\n\t"
   "add         $10,%[end] \n\t"
#else
   "call        .+5 \n\t"
   "pop         %[end] \n\t"
   "add         $8,%[end] \n\t"
#endif
   "add         %[rem],%[end] \n\t"
   "jmp         *%[end] \n\t"

   // jump table
   "vmovaps     0x60(%[src]),%%xmm0 \n\t"
   "vmovntdq    %%xmm0,0x60(%[dst]) \n\t"
   "vmovaps     0x50(%[src]),%%xmm1 \n\t"
   "vmovntdq    %%xmm1,0x50(%[dst]) \n\t"
   "vmovaps     0x40(%[src]),%%xmm2 \n\t"
   "vmovntdq    %%xmm2,0x40(%[dst]) \n\t"
   "vmovaps     0x30(%[src]),%%xmm3 \n\t"
   "vmovntdq    %%xmm3,0x30(%[dst]) \n\t"
   "vmovaps     0x20(%[src]),%%xmm4 \n\t"
   "vmovntdq    %%xmm4,0x20(%[dst]) \n\t"
   "vmovaps     0x10(%[src]),%%xmm5 \n\t"
   "vmovntdq    %%xmm5,0x10(%[dst]) \n\t"
   "vmovaps     0x00(%[src]),%%xmm6 \n\t"
   "vmovntdq    %%xmm6,0x00(%[dst]) \n\t"

   // alignment as the previous two instructions are only 4 bytes
   "nop\n\t"
   "nop\n\t"

   // restore the registers
   "pop         %[end]\n\t"
   "pop         %[src]\n\t"
   "pop         %[dst]\n\t"
   :
   : [dst]"r" (dst),
     [src]"r" (src),
     [end]"c" (end),
     [rem]"d" (rem)
   : "xmm0",
     "xmm1",
     "xmm2",
     "xmm3",
     "xmm4",
     "xmm5",
     "xmm6",
     "xmm7",
     "memory"
  );

  //copy any remaining bytes
  for(size_t i = (length & 0xF); i; --i)
    ((uint8_t *)dst)[length - i] =
      ((uint8_t *)src)[length - i];
#else
  memcpy(dst, src, length);
#endif
}

save the registers we intend to alter, failure to do so causes problems when gcc -O3 is used

It should be possible to avoid the pushes and pops.  If you are changing the values of the constraints, you cannot have them as just "inputs" (which is where this code currently has them).  Quoting the docs:

  Do not modify the contents of input-only operands (except for inputs tied to outputs). The compiler assumes that on exit from the asm statement these operands contain the same values as they had before executing the statement.

There are a variety of ways to deal with this.  Simply moving the ones you actually change to the "outputs" section and changing them to "+r" might be sufficient.  Note that this will indeed change the values, which might affect your "remaining bytes" code.

  [rem]"d" (rem)

Is there some reason you need this value in that specific register?  Letting the optimizers pick the registers tends to be a better plan.

  let alone the AT&T syntax

If you prefer the intel format for writing asm (and what rational person doesn't?), gcc has the -masm=intel option.

And lastly, have you tried writing this in C using intrinsics?  There are a couple of places in your code where I wonder if a different arrangement of instructions might give better results, but I can't say without trying it or running an analysis tool.

It's hard for humans to optimally arrange assembler instructions for modern processors.


Password expiry notification script I've just solve one problem that notifies users if their password is going to expire in 14 days.  The script is working fine. I just want to improve my code and desire some suggestions.

#!/usr/bin/env python
# Author :- Rahul Patil<linuxian.com>
#

import sys
import os

#-----------------------------------------------------------------
# Provide Ldap DN Details to Perform Ldap Search using anonymouse
#-----------------------------------------------------------------
Domain = 'linuxian.com'
EmailDomain = 'abc.om' # if your mail domain is different this will becom user@abc.com
ConnectDC = 'ldap://localhost:389'
# if 14 days remains to expire password then it will send email to that user
# until user update the new password
PwdWarnDays = 14
pwdMaxAge = 45 # default password expire in 45 days as per ldap ppolicy

Subject = "Ldap Password Expiry Details"

MsgBody = """
Dear %s,
    Your Password Will be Expire in %s, we request you to please
change your password, your last password change date is %s

Best Regards,
Linux Admin
"""

def GetUserDetails():
        """ This Function Will save all details in file
        it will use ldap search query for the same."""
        # Create bind dn eg. dc=example,dc=com
        BindDN = ','.join([ 'dc=' + d for d in Domain.split('.') ])
        #
        import ldap
        l = ldap.initialize(ConnectDC)
        # Perform Ldap Search
        return  l.search_s(
                BindDN,
                ldap.SCOPE_SUBTREE,
                '(uid=*)',['uid','pwdChangedTime']
            )

def CheckExpiry():
        """
        This Function will Check each user ExpiryWarning
        if it more thans WarningDays then it will send Emails
        to that particuler user
        """
         import datetime
         for k,v in Users:
                    uid = ''.join(v['uid'])
                    if 'pwdChangedTime' not in v:
                            pass
                            #print "User " + uid + "  not Updated Password"
                    try:
                          l = ''.join(v['pwdChangedTime'])
                    except:
                            pass

                    if 'pwdChangedTime' in v:
                        # To extrace year month day
                        d1 = datetime.date.today()
                        d2 = datetime.date(int(l[0:4]),int(l[4:6]),int(l[6:8]))
                        DaysOfPasswordChange = (d1 - d2).days
                        d2 = d2.strftime('%d, %b %Y')

                        ExpireIn = pwdMaxAge - DaysOfPasswordChange

                        # if password not changed before 14 days
                        if ExpireIn <= PwdWarnDays:
                            SendMail = "echo '" + MsgBody % (uid,ExpireIn,d2) + "' \
                                      mail -s " + '"' + Subject + '"' + ' ' + \
                                      uid + '@' + EmailDomain
                            #os.system(SendMail)
                            print SendMail

if __name__ == '__main__':
        Users = GetUserDetails()
        CheckExpiry()

I'm just going to comment on these three lines:

SendMail = "echo '" + MsgBody % (uid,ExpireIn,d2) + "' \
          mail -s " + '"' + Subject + '"' + ' ' + \
          uid + '@' + EmailDomain
#os.system(SendMail)
print SendMail

This doesn't work! You've commented out the line that sends the e-mail. Now, I understand that you did this so that you can test the script without spamming your users with these messages, and that you intend to uncomment the line when you deploy the script. But this isn't the best approach.

The first problem is that the need to test the script will come up again after you deploy it — you'll need to revise the text of the messages or change some other aspect the way it works, and then you'll want to test it again. So it would be worth your while to build in a permanent testing mechanism that's better than commenting out a line.

The second problem is that just printing the mail command doesn't actually constitute a test. You have to read the output in order to check that it's correct, and you could easily miss a problem.

What I suggest is that you have a setting that can be turned on and off to indicate whether the script is in testing or deployment:

deployed = False           # Is script deployed?
test_uid = 'rahul.patil'   # Send e-mail to this user if not deployed.

and that you send the e-mail to the test user when testing:

if not deployed:
    uid = test_uid
SendMail = "echo '" + MsgBody % (uid,ExpireIn,d2) + "' \
          mail -s " + '"' + Subject + '"' + ' ' + \
          uid + '@' + EmailDomain
os.system(SendMail)

Ideally you would provide a way to set the deployed flag (and the test_uid) through the script's command-line interface — see the argparse module for one approach to doing this.
When you run a command using os.system, the command gets interpreted by the shell. This is risky, because the shell has complicated quoting and evaluation rules that you may not understand. For example, suppose that you edited MsgBody like this:

MsgBody = """
Dear %s,
     Your password will expire in %s day(s). We're sorry for the
inconvenience, but we need you to change your password by %s.
"""

Looks good, right? But if you actually try this, you'll find that the call to os.system fails with an error like this:

sh: line 3: inconvenience,: command not found
sh: -c: line 4: unexpected EOF while looking for matching `''
sh: -c: line 5: syntax error: unexpected end of file

That's because the single quote in We're was interpreted by the shell as terminating the argument to echo.

In order to avoid problems like this (where data gets wrongly interpreted as code by the shell), you should avoid passing the arguments to the shell. Instead of os.system, you should use the functions in the subprocess module. For example, like this:

import subprocess

p = subprocess.Popen(['mail', '-s', Subject, uid + '@' + EmailDomain],
                     stdin=subprocess.PIPE)
p.communicate(MsgBody % (uid, ExpireIn, d2))


Generate every possible single word of three letters I was asked to generate every possible single word of three letters, so I wrote this script. How good is my code? Would it be better doing it using recursion or would that be over-engineering?

const getAllPossibleThreeLetterWords = () => {
      const chars = 'abcdefghijklmnopqrstuvwxyz'
      const arr = [];
      let text = '';
      for (let i = 0; i < chars.length; i++) {
            for (let x = 0; x < chars.length; x++) {
                  for (let j = 0; j < chars.length; j++) {
                        text += chars[i]
                        text += chars[x]
                        text += chars[j]
                        arr.push(text)
                        text = ''
                  }
            }
      }
      return arr
}
console.log(getAllPossibleThreeLetterWords());

It is very clear both what your code does and how it does it, this is a good thing. However, right now it is incredibly rigid. If requirements change more code will need to be changed than if you spent a bit more time on making it more generic (more on this later).

You can avoid doing multiple assignments to text by combining the lines with text = chars[i] + chars[x] + chars[j]. This also removes the need to reset text to the empty string after adding the word.
The variables i, x, and j seem to be randomly chosen. Not a big deal for loops this small, but it would be fairly easy to accidentally swap the order around. You might want to consider using a, b, and c instead.

What would you do if you were told to modify this method so that it generates 4 letter words? How about 20 letter words? Or just n letter words? While you could write a ton of for loops, it would be better to handle a more generic case. Whether you use recursion or not is entirely up to you.

To help you decide, here is a comparison.

Recursive, handling n letters.

let flatten = arr => arr.reduce((carry, item) => carry.concat(item), [])

let getAllWords = wordLength => {
    if (typeof wordLength != 'number') throw Error('wordLength must be a number')
    if (wordLength < 0) throw Error('wordLength must be greater than or equal to zero')
    if (wordLength == 0) return []

    let alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')
    let lengthen = word => alphabet.map(letter => word + letter)
    let addLetters = words => flatten(words.map(lengthen))
    let _getAllWords = (letters, words = alphabet, current = 1) => {
        return letters == current ? words :
            _getAllWords(letters, addLetters(words), current + 1)
    }

    return _getAllWords(wordLength)
}

console.log(getAllWords(2))

Iterative, handling n letters.

let getAllWords = wordLength => {
    if (typeof wordLength != 'number') throw Error('wordLength must be a number.')
    if (wordLength < 0) throw Error('wordLength must be greater than or equal to zero.')

    let alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')
    let words = []
    if (wordLength != 0) words = alphabet

    for (let i = 1; i < wordLength; i++) {
        let temp = []
        words.forEach(word => {
            alphabet.forEach(letter => temp.push(word + letter))
        })
        words = temp
    }

    return words
}

console.log(getAllWords(2))

It really is somewhat of a matter of opinion which is more clean. I personally would likely use the recursive version with the helper functions pulled out of the function itself to improve readability.


Validating user input I've written the below code to validate user input but I feel it's quite excessive for what seems to be a simple operation. I want to only accept non-negative integers or doubles as an input. This block of code is required three times in my program so I will need to put it into a method or something but in the mean time is there a simpler way to validate user input?

    Scanner input = new Scanner(System.in);

    boolean validWidth = false;
    double width = 0.0;;

    do // do while runs until the input is validated
    {
        System.out.print("Enter width: ");
        if (input.hasNextInt()) // we accept an int
        {
            width = input.nextInt();
            if (width > 0) // we accept a non-negative
            {
                validWidth = true;
            }
            else // refuse a negative
            {
                System.out.println("Input error. Try again.");
                validWidth = false;
            }
        }
        else if (input.hasNextDouble())// accept a double
        {
            width = input.nextDouble();
            if (width > 0) // we accept a non-negative
            {
                validWidth = true;
            }
            else // and refuse a negative
            {
                System.out.println("Input error. Try again.");
                validWidth = false;
            }
        }
        else
        {
            System.out.println("Input error. Try again.");
            validInput = false;
            input.next();
        }
    } while (!(validWidth));

You are distinguishing between hasNextInt() and hasNextDouble() in the input stream, but treating them identically afterwards.  hasNextDouble() will return true if the next token is an integer, because integers can be successfully parsed as a double too.

So your loop could be simplified into:

double width = 0.0;

for(;;) {
    System.out.print("Enter width: ");
    if (input.hasNextDouble()) {
        width = input.nextDouble();
        if (width > 0)
            break;
    }
    System.out.println("Input error. Try again.");
    input.nextLine();
}

A few notes:

The unnecessary validWidth variable has been removed.  A break statement exits the infinite for(;;) loop, skipping over the "cleanup, try again" code.
.nextLine() is used to cleanup after invalid input. This is important, because if the user enters "one fish two fish red fish blue fish" instead of say -12, your current approach will print out "Input error. Try again" 8 times.  Using .nextLine() discards everything up to and including the new line character.  Which brings us to zero and negative numbers.  If the user enters a valid integer/double, but not a positive one, your code didn't skip any tokens, where as my code (as mentioned above) will skip the remaining input up to and including the new line character.  Assuming the next character was a new line (as in the user entered -12 and pressed the return key) the following .hasNextDouble() will skip over the new line (and any other blank space) looking for the next token, so the effect is approximately the same.
But my code performs differently if the user enters red 5.  You original code will print "Invalid input.  Try again.", and then immediately consume the 5 as valid input, where as my code will discard the remainder of the line, and wait for the user to enter another line.

Since you are using the code multiple places, putting it into a method is prudent.  Here is one using a DoublePredicate functional interface in order to validate the input according to the caller's requirements:

double getDouble(Scanner input, String prompt, DoublePredicate validate) {
    double value = 0.0;

    for(;;) {
        System.out.print(prompt);
        if (input.hasNextDouble()) {
            value = input.nextDouble();
            if (validate.test(value))
                return value;
        }
        System.out.println("Input error. Try again.");
        input.nextLine();
    }
}

Which you could use with a lambda function like:

    double width = getDouble(input, "Enter width: ", x -> x > 0);


Capturing the positions of "start" and "end" markers in a multi-line string Is there any better (and shorter) way to get index of a regex match in Python?

import re
sstring = """
this is dummy text
which starts with nothing
and ends with something
"""

starts = re.finditer('start[s]?', sstring)
ends = re.finditer('end[s]?', sstring)

for m in starts:
    print (m.start())

for m in ends:
    print (m.end())

For me, there is only one starts and endsmatch in the string.

If you are certain that there is exactly one match, then you don't need to iterate.  You could write:

start, end = re.search('start.*ends?', sstring, re.DOTALL).span()

To note:

Take advantage of re.DOTALL so that the regex can span multiple lines.
Use match.span() and destructuring assignment to get both the start and end in one statement.
The [s]? after start is, from a mechanical viewpoint, useless.  You might want to keep it just for symmetry.

The spacing in print (something) is kind of weird; print(something) would be more conventional.


Handling create, update, and destroy for sync I'm pretty sure there's a way to make this "3 times" duplicated code into only one. Any idea how to do this?

if (typeof sync.create!='undefined') {
    for (var i = 0; i <sync.create.length; i++) {
        sync.create[i].modified.id_partenaire=false;
    };
}
if (typeof sync.update!='undefined') {
    for (var i = 0; i <sync.update.length; i++) {
        sync.update[i].modified.id_partenaire=false;
    };
}
if (typeof sync.destroy!='undefined') {
    for (var i = 0; i <sync.destroy.length; i++) {
        sync.destroy[i].modified.id_partenaire=false;
    };
}

If this should be executed on all properties of sync in general, i'd go with a for..in loop.

for(var prop in sync){
  if(sync.hasOwnProperty(prop) && typeof sync[prop] !== 'undefined'){
    var i=0, l = sync[prop].length;
    for (i; i < l; i+=1) {
        sync[prop][i].modified.id_partenaire=false;
    };
  }
}

Otherwise, if there are more properties and this should only be applied to these 3, Esailija's answer works better.


Did I overuse / underuse threading locks in my custom list class? I am writing a Python module in which two threads access one list. One thread adds 500 items to the list per second, and the other thread reads the list at an irregular interval. I want to make a thread-safe "list" class to avoid having to use locks every time I read or write to the list (suggested by this answer to a previous question on SO).

Here is my first go at a thread-safe list class (with help from these previous SO answers: 1 and 2). Are there any methods that should be locked that are not currently locked, or any methods that do not require a lock that are currently locked?

import collections
import threading

class ThreadSafeList(collections.MutableSequence):
    """Thread-safe list class."""
    def __init__(self, iterable=None):
        if iterable is None:
            self._list = list()
        else:
            self._list = list(iterable)
        self.rlock = threading.RLock()

    def __len__(self): return len(self._list)

    def __str__(self): return self.__repr__()

    def __repr__(self): return "{}".format(self._list)

    def __getitem__(self, i): return self._list[i]

    def __setitem__(self, index, value):
        with self.rlock:
            self._list[index] = value

    def __delitem__(self, i):
        with self.rlock:
            del self._list[i]

    def __iter__(self):
        with self.rlock:
            for elem in self._list:
                yield elem

    def insert(self, index, value):
        with self.rlock:
            self._list.insert(index, value)

While it looked like at first glance that you were missing quite a few from the normal list methods:

>>> dir(list)
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__delslice__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__setslice__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

Inheriting from collections.MutableSequence takes care of most of them (by using internally the re-implemented methods instead of the C methods).

>>> l = ThreadSafeList([3, 2, 1, 1])

A few are still missing, though:

>>> l.sort()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'ThreadSafeList' object has no attribute 'sort'

>>> l = l + [1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'ThreadSafeList' and 'list'

>>> l = l + l
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'ThreadSafeList' and 'ThreadSafeList'

>>> l = l * 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for *: 'ThreadSafeList' and 'int'

Although, there seem to be work-arounds for all of them, if changing mutating and non-mutating is fine:

>>> l = ThreadSafeList(sorted(l))
>>> l.extend([1])
>>> l.extend(l)
>>> l = ThreadSafeList(list(l) * 3)

Note that there is no way to add these lists without mutating them.

Otherwise, I see only one style-issue:

The output of repr should ideally include the class, so that eval(repr(obj)) returns a copy of the instance. You can define it like this:

def __str__(self):
    return str(self._list)

def __repr__(self):
    return "{self.__class__.__name__}({self._list})".format(self=self)

The latter can be slightly simplified in Python 3.6, using f-strings:

def __repr__(self):
    return f"{self.__class__.__name__}({self._list})"


Build a Person class, delegate don't duplicate I am currently learning javascript and I attempted to make a Person class (note - this was part of a practice exercise, so some of the design decisions may have been due to the requirements).

Specifically, I am looking for feedback on:

Usage of prototypes (i.e. from my understanding, prototype should be used when the particular behaviour/property is shared with all objects. This means there is only 1 instance of the function (e.g.) getFullName() which is shared across all objects, whereas the properties fullName, firstName and lastName which are declared directly in the Person function, thus a new unique copy will be created in every instance.
Usage of undefined (i.e. exercise required us to initially have obj.firstName to be equal to undefined. But does it make more sense to have these properties equal to undefined, or to have it equal to null, or to equal an empty string (like "").
Usage of this (am I generally correct in the usage of this? Particularly when prototypes are used)

var Person = function(firstAndLast) {
    this.fullName = firstAndLast;
    this.firstName = undefined;
    this.lastName = undefined;
};

Person.prototype.setFullName = function(firstAndLast){
    this.fullName = firstAndLast;
};
Person.prototype.setFirstName = function(first){
    this.firstName = first;
};
Person.prototype.setLastName = function(last){
    this.lastName = last;
};
Person.prototype.getFullName = function(){
    return this.fullName;
};
Person.prototype.getFirstName = function(){
    //exercise required a default firstName to be set, only if this function was called
    if(this.firstName === undefined){
        this.firstName = this.defaultFirst();
    }
    return this.firstName;
};
Person.prototype.getLastName = function(){
    //exercise required a default lastName to be set, only if this function was called
    if(this.lastName === undefined){
        this.lastName = this.defaultLast();
    }
    return this.lastName;
};

Person.prototype.defaultFirst = function(){
    var first = "";
    for(var i=0;i<this.fullName.length; i++){
        if(this.fullName[i] !== " "){
            first += this.fullName[i];
        }else{
            break;
        }
     }
    return first;
};

Person.prototype.defaultLast = function(){
    var last = "";
    for(var i=this.fullName.length-1; i>0; i--){
        if(this.fullName[i] !== " "){
            last += this.fullName[i];
        }else{
            break;
        }
    }
    return last.split("").reverse().join("");
};

Just so you know, undefined in JS is mutable. It's value can be changed. You could resort to using void 0 instead of undefined.
In JS, assignment operations are as good as values, equivalent to the value assigned. Also, the || acts like a "default" operation, where if the left-side value is falsy (ie, blank string, undefined, null, false, 0), the right-side value is used. And so, getFirstName (and similarly, getLastName) can be simplified into:

return this.firstName = this.firstName || this.defaultFirst();

For defaultFirst and defaultLast, essentially you're splitting by space and getting the first and last contiguous word, respectively. And so, it can be simplified using split and shift or pop:

// For first name:
return this.fullName.split(' ').shift();

// For last name:
return this.fullName.split(' ').pop();


Finding heaviest path through triangle I am doing Project Euler problem 67 which involves finding the heaviest path through a triangle of integers like this one (this is a smaller version from an earlier problem)

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

This is my code:

import Control.Monad (liftM)

addRows :: Integral a => [a] -> [a] -> [a]
addRows xs@(x:_) (y:ys) = x + y : addMid xs ys ++ [last xs + last ys]
    where addMid (a:b:bs) (c:cs) = c + max a b : addMid (b:bs) cs
          addMid _         _     = []

parse :: (Integral a, Read a) => String -> [[a]]
parse = map ((read <$>) . words) . lines

main = do
    tri <- liftM parse $ readFile "Triangles.txt"
    return $ maximum . foldl1 addRows $ tri

The above code works, however it seems inefficient in some respects. It seems like I'm not being as lazy as I should be with regards to my concatenation and use of last.

The last element...

  It seems like I'm not being as lazy as I should be with regards to my concatenation and use of last.

Yes. Let's have a look at an example and check addRow's behaviour:

       6
     1   4
   3   5   2
 9   1   2   6

addRows [6] [1, 4] = (6 + 1) : addMid [6] [4] ++ [6 + 4]            (1)
                   = 7       : []             ++ [10]
                   = [7, 10]

addRows [7, 10] [3, 5, 2] = (7 + 3) : [5 + max 7 10] ++ [10 + 2]    (2)
                          = [10, 15, 12]

Let's check how often you actually use each number. In (1), you use 6 twice, and both 1 and 4 once. In (2), you use 7 twice, 10 twice, and all of the other numbers once. Hm. Does this hold for a fourth line?

addRows [10, 15, 12] [9, 1, 2, 6]
     = (10 + 9) : addMid [10, 15, 12] [1, 2, 6] ++ [12 + 6]
     = (10 + 9) : 1 + (max 10 15) : 2 + (max 15 12) : [] ++ [12 + 6]

Using a function that "does things right"

This pattern seems to hold. You always use the elements in the first list twice, and the once in the second list only, well, once. This sound like it should be possible to zipWith the first elements with themselves somehow. If we were able to pattern match on the last element, this would be

(x:xs:[y]) -> x : zipWith max (x:xs:[y]) (xs:[y]) ++ [y]

However, the dreaded last element makes this hard. We could write our own zip function:

transformLine :: (Ord a) => [a] -> [a]
transformLine xs@(x:_) = x : go xs
  where
    go [y]           = y
    go (a: ys@(b:_)) = max a b : go ys

It's important that we only use cons to gain a maximum of laziness. This function will transform a line into another that's exactly one number longer:

transformLine [6]   == [6, 6]
transformLine [1,4] == [1, 4, 4]

It is therefore a list that can simply get summed onto the next line:

    [6,  6]   |->   [ 7, 10, 10]    | ->  [10, 15, 15, 12]
 +  [1,  4]   |   + [ 3,  5,  2]    |   + [ 9,  1,  2,  6]
 =  [7, 10] ->|   = [10, 15, 12] -> |   = [19, 16, 17, 18]

That way, addRows is simply

addRows xs ys = zipWith (+) (transformLine xs) ys

Turn your world upside down

However, we can also turn the triangle upside down and start with the longer lines:

 9   1   2   6
   3   5   2
     1   4
       6

Which makes this a lot easier, because we're now reducing the information instead of gaining additional:

     / 9 1 2   (init first line)  \
 max                               \
     \ 1 2 6   (tail first line)    (+)
                                   /
       3 5 2   (second line       /

Or, in actual code:

addRows :: (Num a, Ord a) => [a] -> [a] -> [a]
addRows xs ys = zipWith (+) ys $ zipWith max xs (tail xs)

However, now it's necessary to reverse the triangle beforehand or flip the arguments of addRows:

head . foldr1 addRows . reverse $ tri

head . foldr1 (flip addRows) $ tri

Note that head is fine here, since addRows always decreases the number of elements in the accumulating list, therefore you end up with a singleton. Also note that foldr is usually lazier on lists.

... and the oddities

While the previous section was concerned with laziness and last, this one contains general remarks:

import Control.Monad (liftM)

This isn't necessary, since IO is also an instance of Functor. And since the Applicative-Monad-Proposal every Monad is also an Applicative and therefore a Functor.

parse = map ((read <$>) . words) . lines

The <$> here is quite hard to read, especially since there are two operators next to each other (<$> and (.)). A simple fmap is easier to the eye:

parse = map (fmap read . words) . lines

Alternatively use map, since you're working with lists.

main =
    ...
    return $ maximum ...

main should have the type IO (). If you want to print the number, use print instead of return.

Summary

Other than the few oddities, well done. The last issue isn't that easy to solve unless you write another function or change your point of view. However, if you manage to actually reduce the amount of available information in your fold*, your usually on the right track.


Sieve of Erathosthenes speedup While reading HackerNews, I learned about a data set of the first 50 million primes.  This would be a lot, but his website has disclaimer:

  n this directory I have the first fifty million primes in blocks of one million.  Usually it is faster to run a program on your own computer than to download them, but by popular demand, here they are!

N = 10000

n = np.arange(N)+2
P = []

for M in range(3):

    n = np.arange(N)+2 + M*N
    for p in P:
        n =  n[np.where(n% p != 0)]

    while(len(n) > np.sqrt(N)):
        P += [n[0]]
        n = n[np.where(n% P[-1] != 0)]
        #print len(n),

print len(P), M*N/np.log(M*N), M

When I posted this on HackerNews, someone mentioned this was sub-optimal.

  I like this way of using NumPy. This resembles the sieve of Eratosthenes, so you'd think it was fast.
  However n%p[-1] isn't fast to do, your inner loop ends up taking nearly linear time. At least linear in the final number of primes, which is larger than \$N \log N\$. Hence your algorithm runs in \$N^{3/2}\$ whereas Eratosthenes is \$N \log \log N\$.

How do I fix it? For large values, say N=10**6 it's a bit slow.  What is wrong with n%p[-1]?

Sieving in the sense of the old Greek is about eliminating composites by crossing out all multiples of primes (striding additively), and the original SoE does not divide, ever. Trial division is something completely different, and for numbers approaching 2^64 it takes several million times as long as a segmented Sieve of Eratosthenes, even if you trial-divide only by primes.

The memory footprint can be reduced by sieving only the odd numbers, since the only even prime can be pulled out of thin air if need be.

Sieves are usually represented as packed bitmaps rather than one number per array cell, because otherwise memory consumption would be huge and things would be exceedingly slow. More compact forms of representations exist, which extend the 'odds-only' idea to dropping multiples of more small primes. They are called 'wheels', and one of the regulars here has written a brilliant explanation of them.

The famous mod 30 wheel drops 2, 3, and 5, and thus effectively stuffs 30 integers into a single byte. Packed odds-only bitmaps are much less complicated than such wheels though and good enough for many practical purposes.

The biggest speedup - almost an order of magnitude - comes from sieving in small blocks that fit into the L1 cache of the CPU, 32 KBytes or thereabouts. However, this makes division creep back into the code, because it is necessary for computing the start offset for each prime when processing a segment.

The division for recomputing the striding position for a prime for every new segment can be eliminated by remembering the last offsets for each prime from segment to segment (or rather the next offsets). That results in a further speedup.

The last optimisation is called 'presieving', which in practical terms means blasting the bit pattern for the composites of a bunch of small primes all over a bitmap before commencing normal operation at the first prime not in that bunch.

There are two variations: the general one blasts a segment immediately before commencing work on it, thus also warming the caches. The special one blasts the whole sieve in one go, and it is slightly faster overall given certain conditions. Perfect for initialising an auxiliary small factors sieve (up to 2^32) for a sieve that operates up to 2^64.

My pastebin has several standalone .cpp programs demonstrating these optimisations and their effects, so that you can gauge what each optimisation can buy you in terms of speed. Presieving might be slightly more difficult to do in python but all the other optimisations apply directly.

As a rough guide, sieving the full 32-bit range using the plain odds-only Eratosthenes takes 20 to 30 seconds on modern CPUs (single-threaded). If you apply all the optimisations then you can cut that to 2 seconds. The segmented sieve logic is also a precondition for parallel sieving.

EDIT: if you are interested in primes in general and large lists - or fast bulk generation - in particular then have a peek at my topic
Checksumming large swathes of prime numbers? (for verification). It mentions quite a few sources, up to 2^64 - 10 * 2^32 in fast bulk, from then on at a rate of about 1 million primes per minute (by having gp/PARI dump forprime()). primos.mat.br has lists up to 10^12, by the way.

EDIT: some resources on how to do Sieve of Eratosthenes in python and who to apply some of the optimisations:

Gareth Rees covers the basics in his excellent post under Sieve of Eratosthenes - Python
the python SoE examples on RosettaCode show many variants and some optimisations in action
the numpy/scipy docs have the lowdown on fancy indexing and dtype (to force arrays to specific data types like unsigned 32-bit integers a.k.a. uint32)
LiterateProgramming explains the basics of SoE in python at a gentler pace

The keys to speedy sieving in languages like python are two:

efficient, compact representation of the sieve (sets, bool arrays, uint32/uintp arrays)
pushing processing into the engine/runtime without incurring gratuitous inefficiencies (e.g. instead of division filter where(n % p != 0), use additive striding like is_composite[p*p::p] = True for a bool array)

Things like presieving pretty much require using uintp arrays to be really effective but sets and boolean arrays are more interesting for exploring the logic of the Sieve vs. the capabilities of python, numpy and scipy.

Note: your use of the division filter turns your code into 100% bona fide trial division, and it would make the old Greek turn in his grave... ;-)


Tic Tac Toe in Python practice I'm quite novice here so apologies for any silly mistake in advance
I've been writing a simple tic tac toe game which is a part of my course in udemy
Since this is my first project, I want to do my best in order to learn new things besides learning how to code better. Generally, I want to optimize my code as much as possible.
Can anyone help me with this?
# Tic Tac Toe
# 17 July 2020

import os

test_board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
player_input_num = 0    # numbers of inputs entered by player
player_num = 0
won = False
marker = 'X'

def clear_screen():
    os.system("clear")

def display_board(board_cords):
    '''
    display the board
    board_cords = list(left to right from top to bottom)
    '''
    line = '-'*40
    for counter in range(0, len(board_cords), 3):
        print("\t|\t\t|")
        print(
            f"{board_cords[counter]}\t|\t{board_cords[counter+1]}\t|\t{board_cords[counter+2]}")
        print(line)
        counter += 3    # go to next row

def check_player_input(number):
    if number < 10 and number >= 0:  # checking the range
        return True
    else:
        print('Sorry the input is not in range [0-9] .')
        return False

def player_input(player_in):
    '''
    Executing codes on the previously checked input
    '''
    global player_input_num  # access to player_input_num
    if player_input_num >= 2:
        # check if the position is free to use
        if check_capacity(test_board, player_in):
            result = place_marker(test_board, 'X', player_in)
            clear_screen()
            display_board(result)

            if check_win(test_board, marker):
                print("You Won!")
                global won
                won = True
        else:
            print("The current position is occupied.")
    else:
        if check_capacity(test_board, player_in):
            result = place_marker(test_board, 'X', player_in)
            clear_screen()
            display_board(result)
            player_input_num += 1
        else:
            print("The current position is occupied.")

def check_capacity(board, position):
    '''
    Check if the current position is free to use.
    '''
    return board[position] == ' '

def place_marker(board, marker, position):
    '''
    Replace the position with a marker
    '''
    board[position] = marker
    return board

def check_win(board, marker):
    '''
    Check if the current game is finished
    '''
    if board[0] == board[1] == board[2] == marker:
        return True
    if board[0] == board[3] == board[6] == marker:
        return True
    if board[0] == board[4] == board[8] == marker:
        return True
    if board[2] == board[5] == board[8] == marker:
        return True
    if board[6] == board[7] == board[8] == marker:
        return True
    if board[2] == board[4] == board[6] == marker:
        return True
    return False

def wanna_play():
    '''
    Check whether the players wanna play again or not.
    '''
    answer = input("Wanna play again? (Y or N)")
    return answer

# Main
display_board(test_board)
while True:
    while won == False:
        try:  # checking if input is int
            player_num = int(input("Enter a position: "))   # casting into int
        except:
            print("Input is not a number")
            continue

        if check_player_input(player_num):
            player_input(player_num)

    if wanna_play() in ['y', 'Y', 'n', 'N']:
        print("something")
    else:
        print("Invalid input.")
        # print("Thanks for playing :)")

Edited.

First thing, I assume that you don't like to use Object Oriented concepts and we will continue by the function approach.
One thing that I should say to you about the comments is always to use them but in a meaningful way. Adding # Variables comment above of the variables will not add any additional value to your code. It only wastes space.
The second thing is about naming. You should always follow your chosen naming rules.
So it's better to use player_input_num or player_in_num instead of the playerin_num. That's more snake_case.
So the beginning of your program will be like this after doing the above things:
import os

test_board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
player_input_num = 0

Acording to the comment rule we said above, you can remove the clear_screen docstring:
def clear_screen():
    os.system("clear")

Now we can take a look at the display_board function. You've used the while loop heare. But in the Python and for this case, using the for loop is more convient and readable. First, let's see the code:
def display_board(board_cords):
    '''
    display the board
    board_cords = list(left to right from top to bottom)
    '''
    line = '-'*40
    for i in range(0, len(board_cords), 3):
        print("\t|\t\t|")
        print(f"{board_cords[i]}\t|\t{board_cords[i + 1]}\t|\t{board_cords[i + 2]}")
        print(line)

The i is the loop counter variable. We said that the loop should start counting from the zero until reaching the len(board_cords). And also we told that after each iteration, it should increase the i value by 3.
The next function is check_player_input. In this function, we can remove the syntax variable. Also, we can use a more pythonic way of checking the user input range.
def check_player_input():
    """
    Gets an integer between 0 and 10 and calls `player_input` by that
    """
    while True:
        try:
            temp = int(input("Enter a position: "))
            if 0 <= temp < 10:
                break
            else:
                print('Sorry the input is not in range [0-9].')
        except:
            print("Input is not a number")
    player_input(temp)

Why removing the syntax variable is better? Because it's a variable with no real use. The original code is an infinite loop with a redundant variable.
Now we can go to the player_input function. The function that has an unnecessary global value.
One of the most famous **Not To Do` rules of software development is to avoid global values as possible. How we can avoid using that global value? The best way for doing that is to get the global value as an input parameter. But here I don't do that (Stay tuned for knowing why. For now, we just remove it and keeping its place).
The second problem here is the documentation of this function is not sufficient. I mean, what are the "codes"? You should add an extra description here for helping people understanding what is going on.
def player_input(player_in):
    if player_input_num >= 2:
        while check_win(test_board) == False:
            result = place_marker(test_board, 'X', player_in)
            clear_screen()
            display_board(result)
            check_player_input()

        print("You Won!")
    else:
        while player_input_num <= 2:
            result = place_marker(test_board, 'X', player_in)
            clear_screen()
            display_board(result)
            player_input_num += 1
            check_player_input()

In the next function, you did a very good thing. Inputting the board instead of using global values. I don't do it in your code in this post, but I strongly recommend doing that in other places of your code.
Doing that makes your code cleaner, more readable, more testable, and less buggy.
In the check_win there is a big problem. The login is too long and unreadable. It's better to break the logic down.
def check_win(board):
    if board[0] == board[1] == board[2]:
        return True
    if board[0] == board[3] == board[6]:
        return True
    if board[0] == board[4] == board[8]:
        return True
    if board[2] == board[5] == board[8]:
        return True
    if board[6] == board[7] == board[8]:
        return True
    if board[2] == board[4] == board[6]:
        return True
    return False

Why we did that? There are 6 different conditions for winning. So it's better to divide them from each other. So the person who reads your code can understand them more quickly.
All the things I've said until now are good, but there is a problem here. The code doesn't work.
The first problem is the player_input_num  value. In the original code, we only allow the user for inputting 3 values. So, What if the game will not finish after 3 moves? We should continue getting the inputs from the user until he/she wins the game.
We can change the player_input function like this:
def player_input(player_in):
    result = place_marker(test_board, 'X', player_in)
    clear_screen()
    display_board(result)
    if check_win(test_board, 'X'):
        print("You won")
    else:
        check_player_input()

We should change the check_win function too. Additional to the previous conditions, we should check that all 3 cell values are equal to the marker.
def check_win(board, marker):
    if board[0] == board[1] == board[2] == marker:
        return True
    if board[0] == board[3] == board[6] == marker:
        return True
    if board[0] == board[4] == board[8] == marker:
        return True
    if board[2] == board[5] == board[8] == marker:
        return True
    if board[6] == board[7] == board[8] == marker:
        return True
    if board[2] == board[4] == board[6] == marker:
        return True
    return False

Here it is. But still, we had a problem. What if the all cells of the board has been filled? We can add a new function for checking if the game has finished or not. But we can do it now because for doing that, you should have two players with two different markers. And I think you can do that by yourself.
For avoiding mistakes, I leave all the codes we seen above here. I hope this help you (Don't forget that it's not the best program for doing what you wanted, but I think, for now, it is a acceptable one).
import os

test_board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']

def clear_screen():
    '''
    clearing the screen
    '''
    os.system("clear")

def display_board(board_cords):
    '''
    display the board
    board_cords = list(left to right from top to bottom)
    '''
    line = '-'*40
    for i in range(0, len(board_cords), 3):
        print("\t|\t\t|")
        print(f"{board_cords[i]}\t|\t{board_cords[i + 1]}\t|\t{board_cords[i + 2]}")
        print(line)

def check_player_input():
    """
    Gets an integer between 0 and 10 and calls `player_input` by that
    """
    while True:
        try:
            temp = int(input("Enter a position: "))
            if 0 <= temp < 10:
                break
            else:
                print('Sorry the input is not in range [0-9].')
        except:
            print("Input is not a number")
    player_input(temp)

def player_input(player_in):
        result = place_marker(test_board, 'X', player_in)
        clear_screen()
        display_board(result)
        if check_win(test_board, 'X'):
            print("You won")
        else:
            check_player_input()

def place_marker(board, marker, position):
    board[position] = marker
    return board

def check_win(board, marker):
    if board[0] == board[1] == board[2] == marker:
        return True
    if board[0] == board[3] == board[6] == marker:
        return True
    if board[0] == board[4] == board[8] == marker:
        return True
    if board[2] == board[5] == board[8] == marker:
        return True
    if board[6] == board[7] == board[8] == marker:
        return True
    if board[2] == board[4] == board[6] == marker:
        return True
    return False

if __name__ == "__main__":
    display_board(test_board)
    check_player_input()

Two other things: 1. your logic for winning is not complete. 2. search about the if __name__ == "__main__":, it's better to use that.


Group duplicate files (part 3) This is a continued discussion (from here => Group duplicate files (part 2)) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a new post.

Here is my source code which group duplicate files together, written in Python 2.7. Any advice on smarter ideas to group duplicate files together more efficient, it will be great. Any general advice on code bugs and code style are also appreciated.

Problem statement:

I am given a list of files e.g. ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"]. I want to group all files which have the exact same content. Suppose in this example, file "1.txt", "2.txt", "3.txt" are the same, file "4.txt", "5.txt", "6.txt" have common header, but "4.txt", "6.txt" are exactly the same whole content. Then, the output should be two groups "1.txt", "2.txt", "3.txt" and "4.txt", "6.txt".

My major idea:

To avoid reading full content for each file, I generate a hash code for a piece of a file (in my example, I define the piece of file to be the 10 bytes of a file)
Each time after reading the next 10 bytes, I will hash the content of the next 10 bytes, and combine the hash value (of the next 10 bytes) with existing hash value of a file
Each time I see there is no common hash value for a file, I will stop reading this file from next piece (del file_handle_map[f])
The whole algorithm complete when all files are read

Special question

In method hash_next_n_bytes, I will return -1 if file already reached end (EOF), but sure if there is any better way to represent it, since I think -1 may conflict with some valid hash value -1?

Source code in Python 2.7

from collections import defaultdict
def group_duplicate_files(files):
    # open all filee
    file_handle_map = defaultdict(file)
    file_hash_map = defaultdict(int)
    for f in files:
        file_handle_map[f] = open(f, "r")
    while True:
        terminate = True
        group_map = defaultdict(list)
        for file_name, file_handle in file_handle_map.items():
            h = hash_next_n_bytes(file_handle, 10)
            if h != -1:
                terminate = False
                file_hash_map[file_name] = hash(file_hash_map[file_name]+h)
            group_map[file_hash_map[file_name]].append(file_name)
        remove_list = []
        for h, file_list in group_map.items():
            if len(file_list) == 1:
                remove_list.append(file_list[0])
        for f in remove_list:
            del file_handle_map[f]
        if terminate:
            break
    for h in file_handle_map.values():
        h.close()
    return group_map

def hash_next_n_bytes(f,n):
    x = f.read(n)
    if x:
        return hash(x)
    else:
        return -1

if __name__ == "__main__":
    files = ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"]
    print group_duplicate_files(files)

hash_next_n_bytes can return None in case of EOF
You close the remaining files at the end of group_duplicate_files, but you just del file_handle_map[f] in the while loop. You don't have to close the files, their __del__ method will take care of it when the function returns.
Instead of

while True:
    terminate = True
    ...
    if terminate:
        break

you can do

terminate = False
while not terminate:
    terminate = True
    ...

No need to make file_handle_map a defaultdict, it can be just dict.

Some optimization suggestions:

You can initialize the hash with sizes of files. That way, you will avoid comparing large files with many common leading bytes.
It might just be faster to calculate some simple checksum (MD5 or so) of a larger portion of the file. Alternately reading 10 bytes from many different files and calling hash on each result will likely be inefficient.


Very simple implementation of observer pattern in C++ I'm reading on design patterns for a software engineering class. I am doing small implementations of some I find the most interesting / applicable to better understand them.

I'd like a code review on my design, more particularly on the degree of coupling between my Observer and Publisher classes. I feel that the add_observer() function may be coupled too strongly with the Observer object and that there may be a way to do this with looser coupling.

Observer.h

#ifndef OBSERVER_H_INCLUDED
#define OBSERVER_H_INCLUDED

#include <string>

class Publisher;

class Observer {
public:
    virtual void eventOnProperty(Publisher* source,
         std::string event_name, std::string value) = 0;
};

#endif

Publisher.h

#ifndef PUBLISHER_H_INCLUDED
#define PUBLISHER_H_INCLUDED

#include "Observer.h"
#include <list>
#include <string>

class Publisher {
public:
    void notify_observers(std::string, std::string);
    void add_observer(Observer*);
protected:
    std::list<Observer*> my_observers;
};

#endif

Publisher.cpp

#include "Publisher.h"
#include "Observer.h"
#include <string>
#include <list>

void Publisher::notify_observers(std::string event_name, std::string value) {
    std::list<Observer*>::iterator it;
    for(it = my_observers.begin(); it != my_observers.end(); it++) {
        (*it)->eventOnProperty(this, event_name, value);
    }
}

void Publisher::add_observer(Observer* obs) {
    my_observers.push_back(obs);
}

Don't pass by pointer. There is no ownership associated with it (and it can be NULL and thus you need to test for that).

class Publisher {

    // Is the publisher taking ownership of the observer?
    void add_observer(Observer*);

Is your class taking ownership?

If the answer is yes (you take ownership and thus control lifespan). Then you should pass the object using a smart pointer that allows transfer of ownership.

    void add_observer(std::unique_ptr<Observer> obs);

If the answer is sort of. We are taking shared ownership (ie there might be other objects that are also using it). Then you pass using a smart pointer indicating shared ownership.

    void add_observer(std::shared_ptr<Observer> obs);

If the answer is NO then you pass a reference (as a reference can not be NULL) and also indicates that you don't have onership.

    void add_observer(Observer& obs);

If you do take ownership you need to do some work in the destructor of your publisher to make sure that you correctly relinquish ownership when the publisher dies.

If you don't have an ownership claim. This also means that the lifespan of the object may not live as longer as the publisher so you also need a way for the object to remove itself if it dies first and for the publisher to notify the observer that it has dies so it does not de-register itself from a dead object.

   void del_observer(Observer& obs);


A push style parser combinator in Haskell Usually, parser combinators in Haskell based on the parser type like

newtype Parser t r = Parser ([t] -> [(r,[t])])

This allows back tracking and multiple results. However I think it would be good to have it in "push" style, means the parser will have a set of result when no more input given, and have a transition function that for a given token, results in a new state of the parser. This results in the defintion

newtype PushParser t r = PushParser ([r], Maybe (t -> PushParser t r))

(We could have a data constructor that have two fields, however I prefer to use the more efficient newtype keyword so have to have only one field as a tuple)

To parse a list of tokens, we define the parse function as following:

parse :: PushParser t r -> [t] -> [r]
--No input, rs is the result
parse ~(PushParser (rs, _)) [] = rs
--No parsing function, this is an error state. No result
parse (PushParser (_,Nothing)) _ = []
--Otherwise, drop the results, apply the pasing function with the input and continue
parse (PushParser (_,Just f)) (t:ts) = parse (f t) ts

We can then define a fmap to make it a Functor like the following:

instance Functor (PushParser t) where
    fmap f ~(PushParser (r,mg)) = PushParser ((map f r), do {g<-mg; return (fmap f.g)})

Instance of Applicative is more tricky, but the easiest way is to make it depend on the not yet implemented instance of Monad.

instance Applicative (PushParser t) where
    pure x = PushParser ([x],Nothing)
    pf <*> pv = do
        f <- pf
        v <- pv
        return (f v)

But before giving the definition of Monad I want to introduce the definition of Alternative:

instance Alternative (PushParser t) where
    empty = PushParser ([],Nothing)
    (PushParser (r1,Nothing)) <|> (PushParser (r2,f)) = PushParser ((r1++r2), f)
    (PushParser (r1,f)) <|> (PushParser (r2,Nothing)) = PushParser ((r1++r2), f)
    (PushParser (r1,Just f1)) <|> (PushParser (r2,Just f2)) =
        PushParser ((r1 ++ r2), Just (\t -> f1 t <|> f2 t))

I have tried out different ways for the instance of Monad, but finally I believe the best way to give definition of (>>=) is to define unwrap (or join in the monad library) first.

instance Monad (PushParser t) where
    p >>= f = unwrap (fmap f p) where
        unwrap ~(PushParser (prs, mf)) =
            foldr (<|>) (PushParser ([], do { f<-mf; return (unwrap.f)})) prs

The above works perfectally fine, and although it does not make sense to make it an instance of Parser (in Text.Parser.Combinators) as we don't allow trace back, the other combinators that only requires Alternative worked perfectally fine.

However, the performance seems to be too bad. It is possibly as it keeps all possible parsing path and so consumes too much memory. For example, a simple parse (many (some (char '.'))) "...." will return 8 results, with all combinations of dots.

But I think there should be some way to improve the performance. Please advise me how to improve on this.

It'll lazily take no more memory than it takes time to find the first result if you do not try to enumerate all possible results.

For many/some to only try one option, you want Maybe's Alternative/MonadPlus behavior, not []'s. You could parametrize your Parser type in the Alternative used so the user can change it on the fly.

yoctoparsec uses this "push" style.

parseString (hoistFreeT maybeToList $ many $ some $ mfilter (=='.') token) "...."


AsyncCommand using MVVM and WPF Goals

I want to be able to call async code using the MVVM pattern
I want to
be able to add loading animations/screens without having to add
properties for each command on my viewmodels
I may want to be able to cancel these operations

This is what I came up with

public abstract class CommandBase : ICommand
{
    private readonly Func<bool> _canExecute;

    public CommandBase()
    {

    }

    public CommandBase(Func<bool> canExecute)
    {
        if (canExecute == null) throw new ArgumentNullException(nameof(canExecute));
        _canExecute = canExecute;
    }

    public bool CanExecute(object parameter)
    {
        return _canExecute == null || _canExecute();
    }

    public abstract void Execute(object parameter);

    public void RaiseCanExecuteChanged()
    {
        CanExecuteChanged?.Invoke(this, EventArgs.Empty);
    }

    public event EventHandler CanExecuteChanged;
}

public class AsyncCommand : CommandBase, INotifyPropertyChanged
{
    private readonly Func<CancellationToken, Task> _action;

    private CancellationTokenSource _cancellationTokenSource;

    private bool _isRunning;
    public bool IsRunning
    {
        get { return _isRunning; }
        set
        {
            _isRunning = value;
            OnPropertyChanged();
        }
    }

    private ICommand _cancelCommand;
    public ICommand CancelCommand => _cancelCommand ?? (_cancelCommand = new RelayCommand(Cancel));

    public AsyncCommand(Func<CancellationToken, Task> action)
    {
        if (action == null) throw new ArgumentNullException(nameof(action));
        _action = action;
    }

    public AsyncCommand(Func<CancellationToken, Task> action, Func<bool> canExecute) : base(canExecute)
    {
        if (action == null) throw new ArgumentNullException(nameof(action));
        _action = action;
    }

    private void Cancel()
    {
        _cancellationTokenSource?.Cancel();
    }

    public override async void Execute(object parameter)
    {
        IsRunning = true;
        try
        {
            using (var tokenSource = new CancellationTokenSource())
            {
                _cancellationTokenSource = tokenSource;

                await ExecuteAsync(tokenSource.Token);
            }
        }
        finally
        {
            _cancellationTokenSource = null;
            IsRunning = false;
        }
    }

    private Task ExecuteAsync(CancellationToken cancellationToken)
    {
        return _action(cancellationToken);
    }

    public event PropertyChangedEventHandler PropertyChanged;

    [NotifyPropertyChangedInvocator]
    protected virtual void OnPropertyChanged([CallerMemberName] string propertyName = null)
    {
        PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(propertyName));
    }
}

It can be used like this:

<Button Content="Start" Command="{Binding UpdateDisplayTextCommand}"/>
<Button Content="Cancel" Command="{Binding UpdateDisplayTextCommand.CancelCommand}"/>
<ProgressBar IsIndeterminate="{Binding UpdateDisplayTextCommand.IsRunning}" />

Any faults on this implementation? I'm also open to ideas on features which could be added to this class.

You should avoid code duplication in constructors. For larger objects this practice can quickly spin out of control. Re-use existing constructors instead:

public AsyncCommand(Func<CancellationToken, Task> action) : this(action, () => true) {}

or use default parameters:

public AsyncCommand(Func<CancellationToken, Task> action, Func<bool> canExecute = null) : base(canExecute)
{
    if (action == null) throw new ArgumentNullException(nameof(action));
    _action = action;
}

public CommandBase(Func<bool> canExecute = null)
{
    //this also allows you to remove "_canExecute == null" check
    _canExecute = canExecute ?? () => true;
}

Also, public constructors in abstract class look weird. You should make those protected.

Another minor thing: you have public and private members mixed together in a way, that does not make much sense. Personally, I find code easier to follow, if it has members of the same access level grouped together. But you can use any other scheme (some people like to group ICommand property with related delegate, for example), as long as it does not look random and chaotic.

P.S. If I were to use this class, I would also want to have an overloaded constructor, which takes Action<CancellationToken>. I don't want to manually create tasks, I want you to do it for me. I'm lazy like that. :) I would also want the command to either implement IDisposable or have a public Cancel method, so I can stop async operation programmatically. I mean I could call AsyncCommand.CancelCommand.Execute(...) but it looks ugly.


Algorithm to compute the n-th derivative of a polynomial in Python As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ordered list where the i-th index corresponds (though is not equivalent) to the coefficient of x to the n-th power.

Example:
Take the derivative of: \$3x^3 + 5x^2 + 2x + 2\$ -> [3,5,2,2]

1st derivative: \$9x^2 + 10x + 2\$
2nd derivative: \$18x + 10\$
3rd derivative: \$18\$
4th...n-th derivative: \$0\$

Implementation in Python:

def poly_dev(poly, dev):
    """
    :param poly: a polynomial
    :param dev: derivative desired, e.g., 2nd
    """

    c = 0                                # correction
    r = dev                              # to remove
    while dev > 0:
        for i in range(1, len(poly)-c):
            poly[i-1] = (len(poly)-(i+c))*poly[i-1]
        dev -= 1                                    # I suspect this
        c += 1                                      # this can be simplified
    return poly[:-r]

E.g., print(poly_dev(poly = [3,5,2,2], dev = 2))

I have a math background, but I'm only starting to learn about computer science concepts like Complexity Theory.

I've intentionally tried to avoid reversing a list, as I know that can be expensive. What other steps can I change to decrease this procedure's run time?

You are going one by one derivative, when you could easily do them all at once. With a little multiply-and-divide trick, you could save on complexity.

Also, your function will return wrong results for negative dev (it should raise an exception instead).

Further, your function will mess up the original list:

>>> poly = [3, 5, 2, 2]
>>> print(poly_dev(poly, 2))
[18, 10]
>>> print(poly)
[18, 10, 2, 2]

Here is my take on it:

def poly_dev(poly, dev):
    if dev == 0:
        return poly[:]
    if dev > len(poly):
        return list()
    if dev < 0:
        raise ValueError("negative derivative")
    p = 1
    for k in range(2, dev+1):
        p *= k
    poly = poly[:-dev]
    n = len(poly)-1
    for i in range(len(poly)):
        poly[n-i] *= p
        p = p * (i+dev+1) // (i+1)
    return poly

So, the first thing I do after handling trivial cases is computing the multiplication factor for the first coefficient and take only a copy of the part of the list that I need (to avoid messing up the original).

Then I multiply each coefficient with the multiplication factor p, followed by computing the next one, meaning "divide by the smallest member of the product that defines p and multiply by the one bigger then the biggest one".

Notice that the division is //, which is integer division. That way you don't lose precision (and I think it's a bit quicker than the floating point one, but I'm not sure right now).

It may look redundant to multiply and later divide by the same number, but it's less work than multiplying dev numbers in each go.

Also, it would be more Pythonic to have enumerate(reversed(poly)) instead of range(len(poly)) in the for loop, but then we'd still need n-i somewhere, so this seemed cleaner to me for this particular case. Maybe I'm missing something obvious here.


Passing data from one promise to another using then I'm trying to get an object with ratings and titles properties:
{
  ratings: [3, 5],
  titles: ['Movie1', 'Movie2']
}

from the following two functions:
const getMovies = () => {
  return new Promise((resolve) => {
    resolve([
      {
        movieId: 1,
        rating: 3
      },
      {
        movieId: 2,
        rating: 5
      }
    ]);
  });
};

const getTitle = (movieId) => {
  return new Promise((resolve, reject) => {
    switch (movieId) {
      case 1:
        resolve({ title: "Movie1" });
        break;
      case 2:
        resolve({ title: "Movie2" });
        break;
      default:
        reject(new Error("404 - movie not found"));
    }
  });
};

I'm avoiding async/await, so trying to get that result using then.
Here is my approach:
const result = {}

getMovies()
  .then((movies) => {
    result.ratings = movies.map(({rating}) => rating)
    return Promise.all(movies.map(({ movieId }) => getTitle(movieId)));
  })
  .then((titles) => {
    result.titles = titles.map(({title}) => title)
    console.log(result)
  })
  .catch(console.log)

Can I do this in a better way withou having to nest then inside then? I don't like the use of a external variable to gather my result, but I don't like the nested thens in this other approach:
getMovies()
  .then((movies) => {
    Promise.all(movies.map(({ movieId }) => getTitle(movieId)))
      .then((titles) => {
        console.log({
          ratings: movies.map(({rating}) => rating),
          titles: titles.map(({title}) => title),
        })
      })
      .catch(console.log)
  })
  .catch(console.log)

How can I improve this using then and not async/await?

You could do like so if you prefer, essentially just pass forward the data i the promises. You could write your own promiseAllObject if you want it to be slightly neater.
const result = getMovies()
  .then(movies => {
    return Promise.all([
      Promise.all(movies.map(({ movieId }) => getTitle(movieId))),
      movies.map(_ => _.rating)
    ]);
  })
  .then(([titlesObj, ratings]) => ({
    titles: titlesObj.map(_ => _.title),
    ratings
  }))
  .catch(console.log);

result.then(r => console.log(r));


Django search method I have done this small piece of code used to search for a given word across several fields of a Django model.

Goal was to have first entries equals to the word, then entries starting by the world and finally just entries containing it.

I would like to have feedback on it :

# -*- coding: utf-8 -*-
"""Module created to search a specific term in several fields of a model"""
from itertools import chain
import operator

from django.db.models import Q

__author__ = 'trnsnt'

def search_for_term(model, term, fields, number=10):
    """
    Generic method used to search term on list of fields.
    Return first fields equals to term, then fields starting by the term, and at the end fields containing term
    :param model: Django model class
    :param term: Searched term
    :param fields: Fields to look for
    :param number: Number of wanted response
    :return: List of objects
    """
    searcher = ['iexact', 'istartswith', 'icontains']
    objects = []
    for search in searcher:
        curr_filter = reduce(operator.or_, [Q(('%s__%s' % (field, search), term)) for field in fields])
        # Need to search for number to handle duplicate objects
        objects = uniquify(objects, model.objects.filter(curr_filter)[:number])[:number]
        if len(objects) == number:
            return objects
    return objects

def uniquify(*queryests):
    """Take several queryset and return list of unique object
    :param queryests: QuerySets we want to uniquify
    """
    seen = set()
    return [x for x in chain(*queryests) if not (x in seen or seen.add(x))]

Nice doc-strings. I enjoyed seeing your code. I have just a few comments.

Use built-in functions instead of rolling your own

My guess would be that you could improve the efficiency of uniquify and also make the code more expressive/easier to digest by returning the list version of a union of all the sets in querysets rather than rolling your own solution. Something like this should work (I didn't run it):

full_set = set().union(*query_sets)
return list(full_set)

Another option relying on built-in functionality would be to return a set out of the chaining you already do:

return set(chain(*queryests))

In fact coming back to this, I think you should return a set. It doesn't seem that you later need a list since you're just checking membership. I believe checking set membership is much faster than checking list membership.

Logic

I apologize if I am misunderstanding your logic, but it seems in search_for_term that you want to return early when you find at least number number of results. However, right now you only return early if you find exactly that number of results. Wouldn't you want to modify your early return as:

    if len(objects) >= number:
        return objects

If not it might be helpful to add a comment explaining the logic of returning when you have exactly a certain number of results.

Little nits

Notice you've got a typo in your parameter name queryests. I would recommend using snake_case as in my example above.

Since you're only using operator.or_, consider importing just that function.


Match users to their preferences by ID I am using Java, but coming from a JavaScript background. I have two objects:

a list of users
an Iterable of users preferences

I am joining them into a new users object that I call newUser, and then adding newUser to a List of User and returning that.
I need to match up users to their user preferences based on a shared id.  If I was using JS I would get the id of the user and filter the user preferences based on the same id.  I wasn't able to figure that out, so I used a for loop for users and then a foreach loop for users preferences and the used an if statement to find a match.
var users = service.getUsers();
List<User> value = new ArrayList<User>();
var usersPreferences = _userRepo.findAll();
for(int i =0; i < users.size(); i++){
    var user = users.get(i);
    boolean[] isFound = {false};
    usersPreferences.forEach(prefUser -> {
        if(prefUser.getId() == user.getId()){
            User newUser = new User(user, prefUser);
            value.add(newUser);
            isFound[0] = true;
        }
    });
    if(!isFound[0]){
        User newUser = new User(user);
            value.add(newUser);
    }
}
return value;

var users = service.getUsers();
        List<User> value = new ArrayList<User>();
        var usersPreferences = _userRepo.findAll();

Personally, I dislike var with a passion because of exactly such usage. I can't see half-the types, so I have to make a few assumptions here.

for(int i =0; i < users.size(); i++){

First, I'm against using single-letter variable names, with the only exception being dimensions. Having said that, you can most likely use a for-each loop here (I'm not seeing the type of users, but I assume that it is a List).
for (User user : users) {

List<User> value = new ArrayList<User>();

This variable name could be better, because it doesn't make much sense.

            boolean[] isFound = {false};
            usersPreferences.forEach(prefUser -> {
                if(prefUser.getId() == user.getId()){
                    User newUser = new User(user, prefUser);
                    value.add(newUser);
                    isFound[0] = true;
                }
            });
            if(!isFound[0]){
                User newUser = new User(user);
                    value.add(newUser);
            }

Instead of using a lambda, you could use a simple for-each loop:
            boolean isFound = false;
            for (UserPreference userPreference : userPreferences) {
                if(prefUser.getId() == user.getId()){
                    User newUser = new User(user, prefUser);
                    value.add(newUser);
                    isFound = true;
                }
            }
            if(!isFound){
                User newUser = new User(user);
                value.add(newUser);
            }

Even better would be if you would extract the second loop into its own function, as that would reduce the complexity of your logic:
private User createUserWithPreferences(User user, List<UserPreferences> userPreferences) {
    for (UserPreference userPreference : userPreferences) {
        if (userPreference.getUserId() == user.getId()) {
            return new User(user, userPreference);
        }
    }

    return new User(user);
}

List<User> createdUsers = new ArrayList<>();

for (User user : users) {
    createdUsers.add(createUserWithPreferences(user, userPreferences);
}


Spatial grid of objects I'm using this class so that objects can find other objects that are near them.  Each object has a position and radius. Objects are added to the Grid. If they move then they call update with their new position.  An object can call retrieve to find which objects are around it. How can I optimize it, specifically the retrieve function?

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Arrays;

public class Grid {

    private Map<Integer, Set<Obj>> objects = new HashMap<>();
    private Set<Obj> retrievedObjects = new HashSet<>();
    float size;
    int divisions;

    public Grid(float size, int divisions) {
        this.size = size;
        this.divisions = divisions;
    }

    public void update(Obj obj) {
        if (!obj.grids.equals(getGridsObjIsIn(obj.position, obj.radius))) {
            remove(obj);
            insert(obj);
        }
    }

    public void insert(Obj obj) {
        obj.grids = getGridsObjIsIn(obj.position, obj.radius);

        for (Integer grid : obj.grids) {
            if (objects.containsKey(grid)) {
                objects.get(grid).add(obj);
            } else {
                objects.put(grid, new HashSet<Obj>(Arrays.asList(obj)));
            }
        }
    }

    public void remove(Obj obj) {
        for (Integer grid : obj.grids) {
            objects.get(grid).remove(obj);
        }
        obj.grids.clear();
    }

    public Set<Obj> retrieve(Vector2 pos, float radius) {
        retrievedObjects.clear();
        Set<Integer> grids = getGridsObjIsIn(pos, radius);

        for (Integer grid : grids) {
            if (objects.containsKey(grid)) {
                retrievedObjects.addAll(objects.get(grid));
            }
        }

        return retrievedObjects;
    }

    private Set<Integer> getGridsObjIsIn(Vector2 pos, float radius) {
        Set<Integer> grids = new HashSet<>();

        int[] min = positionToGrid(pos.x - radius, pos.y - radius);
        int[] max = positionToGrid(pos.x + radius, pos.y + radius);

        for (int x = min[0]; x <= max[0]; x++) {
            for (int y = min[1]; y <= max[1]; y++) {
                grids.add(x + y * divisions * divisions);
            }
        }

        return grids;
    }

    private int[] positionToGrid(float x, float y) {
        return new int[]{Math.round(divisions / size * x), Math.round(divisions / size * y)};
    }
}

Comments

It is of course better to write self-documenting code that does not require comments.  However, sometimes we can't quite meet that goal.

    float size;
    int divisions;

What are these?  My first thought is that they are the size of a grid square in pixels or some other unit and the number of grid squares in a row or column.  I don't know what the unit is for the size.  And my length/width hypothesis gets confused when I see code like

                grids.add(x + y * divisions * divisions);

Why divisions * divisions?  If it were just divisions, I'd think that this was just a Cartesian plane.  Then y would represent a row, and x would be the place in the row.  So basically converting the two-dimensional grid into one-dimension.  So a value of divisions - 1 would be next to divisions in the single dimension but would represent the last element of the y = 0 row and the first element of the y = 1 row in two dimensions.

As is, this means something different, and I'm not sure what.  Comments could help clarify this, not just for me as a reviewer but for you in six months when you've forgotten why you did things this way.  You don't need to comment every line, but if you feel clever for the way you did something, comment that.  Because the next person who edits the code (which may be you) won't be nearly as clever as you are at that moment.

What's an Obj?

You don't include the code for Obj, so I'm not really sure what it is.  A less generic name might help.

Fields vs. local variables

    private Set<Obj> retrievedObjects = new HashSet<>();

Why is this an object field?  It's used in exactly one method, cannot be retrieved outside that method, and is reset in the method.  If you replaced it with a local variable, nothing else about this code would change.

The one difference is that if you call retrieve a second time, the values in the set might change.  That seems rather confusing.  You could be iterating over the set, trigger a retrieve, and your iterator is now pointing to an invalid location.  That seems more problematic than keeping up to date is helpful.  Particularly as retrieve takes different parameters.  So the set may change because the parameters are different rather than because what the set represents has changed.

Sparse

This grid is sparsely populated.  You use a Map to hold it, so you only need to remember the locations where it is populated.  This saves a lot of memory at the cost of some speed.  If you find yourself with plenty of memory and constrained by time, consider switching to a different data structure, e.g. a two dimensional array.

Another question is if the Map helps you at all.  You could simply iterate over the list of objects instead.  That might be faster, as you only need to know if the objects conflict.  You actually check each possible conflict and then merge the results.  So if an object is in a hundred squares and another is in fifty, you might do fifty merges.  Consider

for (Obj o : allObjects) {
    if (distance(o, obj) < o.radius + obj.radius) {
        retrievedObjects.add(o);
    }
}

That checks more objects but may do fewer merges.

A side effect of this is that the radius would become an actual radius.  I would expect a radius to be part of the definition of a circle, but in the current code, it defines a square.  If you really want a square, you can still simplify things.  Consider

    int objMinX = Math.max(0, obj.x - obj.radius);
    int objMinY = Math.max(0, obv.y - obj.radius);
    int objMaxX = Math.min(divisions - 1, obj.x + obj.radius);
    int objMaxY = Math.min(divisions - 1, obv.y + obj.radius);
    for (Obj o : allObjects) {
        if (hasOverlap(objMinX, objMaxX, o.x - o.radius, o.x + o.radius)
                && hasOverlap(objMinY, objMaxY, o.y - o.radius, o.y + o.radius)) {
            retrievedObjects.add(o);
        }
    }

and later

public static boolean hasOverlap(int minA, int maxA, int minB, int MaxB) {
    return maxA >= minB && minA <= maxB;
}

Another option would be to switch from Map<Obj> to NavigableMap<NavigableMap<Obj>>.  Then you could do the query more like a two dimensional array.

The important thing is to test these to see which performs best for you.  This is not a case of a one size fits all solution.  The best solution is going to be dependent on the exact characteristics of your data.  How sparsely filled is your grid?  How many objects are there?  Two large objects in a grid would suggest that iterating over all objects is best.  A grid where every square is covered but with small objects might suggest a different solution.


PHP MVC implementation without a framework I've been using PHP for years and in every project I've ever done I've included the HTML, PHP, SQL etc ... in the same page. Upon looking through Github at large projects like WordPress and MediaWiki it appears there are much better ways to lay out your code. I want to use MVC for my next project because I plan on making the code open source. I don't want to use a framework because I don't want lots of overhead and I don't want to have to learn a new framework to be honest.

I've started implementing what I think is a very simple MVC framework for my project. Can anyone who has experience with MVC tell me if I'm doing this correctly?

My project is called How, hence the class names.

The file structure of my project looks like this:

Root directory   -> index.php /includes/ .htaccess
In /includes/    -> /classes/ /controllers/ /routes/ /views/
In /classes/     -> _Globals.php How.php Route.php View.php
In /controllers/ -> Controller.php Root.php
In /Routes/      -> Route.php
In /views/       -> root.php

index.php

<?php
include_once( 'includes/classes/How.php' );

$how = new How();
$how->run();

/includes/classes/How.php

<?php
include_once( './includes/routes/Routes.php' );

class How {
    public function getRoute() {
    global $Routes;
    $uri = $_SERVER['REQUEST_URI'];

    if (!in_array($uri, $Routes)) {
        die("Invalid route.");
    }
    return $uri;
    }

    public function run() {
        try {
            $this->getRoute();
        } catch (Exception $e) {
            die("Failed to get route.");
        }
    }
}

/includes/classes/Route.php

<?php
include_once( '_Globals.php' );
class Route {

    private function registerRoute($route) {
        global $Routes;
        $Routes[] = BASEDIR.$route;
    }

    public static function set($route, $closure) {
        self::registerRoute($route);
        $closure->__invoke();
    }
}

/includes/classes/View.php

<?php
    class View {
        public static function make($view) {
            try {
                include( './includes/controllers/'.$view.'.php' );
                include('./includes/views/'.$view.'.php');
                return 1;
            } catch ( Exception $e ) {
                return 0;
            }
        }
    }

/includes/classes/_Globals.php

<?php
$Routes = array();
define( 'BASEDIR', '/how/' );

/includes/controllers/Root.php (Controller.php is currently blank)

<?php
class RootController {
    public static $username = "Francis";
}

/includes/Routes/Route.php

<?php
include_once( './includes/classes/Route.php' );
include_once( './includes/classes/View.php' );

Route::set('', function() {
    View::make('root');
});

Route::set("about-us", function() {
});

/includes/views/root.php

Welcome <?php echo RootController::$username; ?>!

.htaccess

RewriteEngine On
RewriteRule ^([^/]+)/? index.php?url=$1 [L,QSA]

It works like this:

The .htaccess redirects all requests to index.php.
Index.php calls how->run() which checks if the current route is valid.
Valid routes are stored in the global $Routes array, they are added to the $Routes array by the Route::set() method in the Routes/Route.php.
If the route is valid the View::make() method is called which loads the view from /includes/views/ and the ViewController is loaded from /includes/controllers/.

Before you consider any answer, always consider the rule that you should not write code which is not helpful and avoid code which is unused. When you are using an external framework there is a community which maintains it for you. Here its only you who is the expert.

Less code you write, less maintenance & faster development time.
More readable and maintainable code, easier it is.

Feedback on your code.

Routes.php is quite simplistic. It is not necessarily bad but you havent considered how you would pass on different types of values.
The framework considers only routing as the primary goal of the framework. But you havent considered other things like DB query, Caching, Templating, Security. etc
You are loosing a lot of flexibility in file management when with the current routes framework.

In addition to the above I suggest including two more pieces of code.

A general file (include_top.php) which gets included in top of all files. It might look something like the following

<?
session_start();
//do some global configurations
function __autoload($className) {
    // Put your own directory structure here //
    if(file_exists("../classes/$className.php"))
    include_once "../classes/$className.php";
}
?>

This helps you to easily structure your code into different folders without worry about certain import statements having right path and doing additional global configurations.
An ORM (Object-relational mapping) is a must for any scalable
framework. You can checkout existing frameworks already. I will put a plug for my own light weight ORM.


LeetCode 641: Design Circular Deque I'm posting a solution for LeetCode's "Design Circular Deque". If you'd like to review, please do so. Thank you!
Problem
Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

Example:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);            // return true
circularDeque.insertLast(2);            // return true
circularDeque.insertFront(3);           // return true
circularDeque.insertFront(4);           // return false, the queue is full
circularDeque.getRear();            // return 2
circularDeque.isFull();             // return true
circularDeque.deleteLast();         // return true
circularDeque.insertFront(4);           // return true
circularDeque.getFront();           // return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Deque library.

Code:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

struct MyCircularDeque {
        MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}

        const bool insertFront(
            const int value
        ) {
            if (isFull()) {
                return false;
            }

            stream[head] = value;
            --head;
            head += k;
            head %= k;
            ++counts;

            return true;
        }

        const bool insertLast(const int value) {
            if (isFull()) {
                return false;
            }

            stream[tail] = value;
            ++tail;
            tail %= k;
            ++counts;

            return true;
        }

        const bool deleteFront() {
            if (isEmpty()) {
                return false;
            }

            ++head;
            head %= k;
            --counts;

            return true;
        }

        const bool deleteLast() {
            if (isEmpty()) {
                return false;
            }

            --tail;
            tail += k;
            tail %= k;
            --counts;

            return true;
        }

        const int getFront() {
            return isEmpty() ? -1 : stream[(head + 1) % k];
        }

        const int getRear() {
            return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
        }

        const bool isEmpty() {
            return !counts;
        }

        const bool isFull() {
            return counts == k;
        }

    private:
        using ValueType = std::uint_fast16_t;
        std::vector<ValueType> stream;
        ValueType counts;
        ValueType k;
        ValueType head;
        ValueType tail;
};

Using the same type for the deque contents and the sizes/indices (k, count, head, tail) feels wrong. At least, k and count should be std::vector::size_type.

Since you are backing up the deque with std::vector, making head and tail the std::vector::iterator looks more idiomatic.

k is not the most descriptive name. Consider capacity.

I am not sure that std::vector is the best container to back up the fixed size deque. After all, the point of std::vector is to have a dynamic size. std::array, or even a plain old C-style array, looks more natural.