DBSCAN "region query" too slow; implement a tree? My current DBSCAN in Python works...but its indexing is far too slow; its a linear scan:

def find(self, p):
    nearby = []
    for pt in self.data:
        # Haversine algorithm
        px, ptx, py, pty = map(math.radians, [p.x, pt.x, p.y, pt.y])
        dx = px - ptx
        dy = py - pty
        a = math.sin(dy/2)**2 + math.cos(py)*math.cos(pty)*math.sin(dx/2)**2
        c = 2*math.asin(math.sqrt(a))
        d = 6371.0*c
        if d < self.eps:
            nearby.append(pt)
    return nearby

self.eps: The defined radius in km (hence the Haversine implementation)

self.data: Python list object of my Point() objects:

class Point:
    def __init__(self, lon, lat):
        self.x = lon
        self.y = lat
        self.cluster = None
        self.neighbors = 0

When I run the DBSCAN with say 27,000 points, the find() has to iterate through each point (technically minus 1 each time, but that's moot) for at worst O(N2) (assumes no points in the 27,000 are noise (i.e. they have valid minimum points within self.eps).

I have heard maybe a tree would be better for this? Not sure which and I would prefer to not keep adding modules (if possible!).

You don't provide much information, which is unfortunate, since this kind of optimization problem relies on knowing how to "skew" the code in order to get better performance.

For example, are your points constant? If you are always searching the same set of 27k points - for example, cities or road termini or railroad stations or whatever - then you can pre-compute lots of data about those points to make the code faster.

Are the points accumulated gradually over time? Could you perform an expensive computation on each point safely, knowing that the various points are collected at some interval that allows for that?

Are the points close together or far apart, relative to the likely neighborhood distances? That is, can you estimate the number of points that will be in the likely neighborhood queries?

Is your program memory-constrained? Can we trade memory allocation for performance?

Are the eps values - the neighborhood distances - truly variable? Or is there a static list (1km, 10km, 25km, 50km) that the user chooses from?

All these questions, and more, could be used to tune the code for speed. When you're asking a speed question, there's no such thing as too much data!

Finally, what flavor of python are you using? PyPy? Cpython? Jython? Cython?

With that out of the way, let me make a few "low hanging fruit" suggestions. I'll assume you're using "the python that came with my system" - meaning Cpython 2.7 or 3.4+.

The cpython compiler isn't nearly as smart as you might like. Let's look at the generated code from your function (I put it in test.py in a class named C):

$ python2
Python 2.7.13 (default, Apr 23 2017, 16:50:35)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import test
>>> import dis
>>> dis.dis(test.C.find)
  3           0 BUILD_LIST               0
              3 STORE_FAST               2 (nearby)

  4           6 SETUP_LOOP             230 (to 239)
              9 LOAD_FAST                0 (self)
             12 LOAD_ATTR                0 (data)
             15 GET_ITER
        >>   16 FOR_ITER               219 (to 238)
             19 STORE_FAST               3 (pt)

  6          22 LOAD_GLOBAL              1 (map)
             25 LOAD_GLOBAL              2 (math)
             28 LOAD_ATTR                3 (radians)
             31 LOAD_FAST                1 (p)
             34 LOAD_ATTR                4 (x)
             37 LOAD_FAST                3 (pt)
             40 LOAD_ATTR                4 (x)
             43 LOAD_FAST                1 (p)
             46 LOAD_ATTR                5 (y)
             49 LOAD_FAST                3 (pt)
             52 LOAD_ATTR                5 (y)
             55 BUILD_LIST               4
             58 CALL_FUNCTION            2
             61 UNPACK_SEQUENCE          4
             64 STORE_FAST               4 (px)
             67 STORE_FAST               5 (ptx)
             70 STORE_FAST               6 (py)
             73 STORE_FAST               7 (pty)

  7          76 LOAD_FAST                4 (px)
             79 LOAD_FAST                5 (ptx)
             82 BINARY_SUBTRACT
             83 STORE_FAST               8 (dx)

  8          86 LOAD_FAST                6 (py)
             89 LOAD_FAST                7 (pty)
             92 BINARY_SUBTRACT
             93 STORE_FAST               9 (dy)

  9          96 LOAD_GLOBAL              2 (math)
             99 LOAD_ATTR                6 (sin)
            102 LOAD_FAST                9 (dy)
            105 LOAD_CONST               1 (2)
            108 BINARY_DIVIDE
            109 CALL_FUNCTION            1
            112 LOAD_CONST               1 (2)
            115 BINARY_POWER
            116 LOAD_GLOBAL              2 (math)
            119 LOAD_ATTR                7 (cos)
            122 LOAD_FAST                6 (py)
            125 CALL_FUNCTION            1
            128 LOAD_GLOBAL              2 (math)
            131 LOAD_ATTR                7 (cos)
            134 LOAD_FAST                7 (pty)
            137 CALL_FUNCTION            1
            140 BINARY_MULTIPLY
            141 LOAD_GLOBAL              2 (math)
            144 LOAD_ATTR                6 (sin)
            147 LOAD_FAST                8 (dx)
            150 LOAD_CONST               1 (2)
            153 BINARY_DIVIDE
            154 CALL_FUNCTION            1
            157 LOAD_CONST               1 (2)
            160 BINARY_POWER
            161 BINARY_MULTIPLY
            162 BINARY_ADD
            163 STORE_FAST              10 (a)

 10         166 LOAD_CONST               1 (2)
            169 LOAD_GLOBAL              2 (math)
            172 LOAD_ATTR                8 (asin)
            175 LOAD_GLOBAL              2 (math)
            178 LOAD_ATTR                9 (sqrt)
            181 LOAD_FAST               10 (a)
            184 CALL_FUNCTION            1
            187 CALL_FUNCTION            1
            190 BINARY_MULTIPLY
            191 STORE_FAST              11 (c)

 11         194 LOAD_CONST               2 (6371.0)
            197 LOAD_FAST               11 (c)
            200 BINARY_MULTIPLY
            201 STORE_FAST              12 (d)

 12         204 LOAD_FAST               12 (d)
            207 LOAD_FAST                0 (self)
            210 LOAD_ATTR               10 (eps)
            213 COMPARE_OP               0 (<)
            216 POP_JUMP_IF_FALSE       16

 13         219 LOAD_FAST                2 (nearby)
            222 LOAD_ATTR               11 (append)
            225 LOAD_FAST                3 (pt)
            228 CALL_FUNCTION            1
            231 POP_TOP
            232 JUMP_ABSOLUTE           16
            235 JUMP_ABSOLUTE           16
        >>  238 POP_BLOCK

 14     >>  239 LOAD_FAST                2 (nearby)
            242 RETURN_VALUE

First, have a look at "line 10" - the block of code that starts with a "10" in the left-most column. That code corresponds to this python:

    c = 2*math.asin(math.sqrt(a))

The Python VM is a stack machine, so every opcode either takes something off the stack, puts something on the stack, or both. For example, the various LOAD_ ops put things onto the stack. The CALL_FUNCTION op calls a function (which is stored on the stack) with a number of arguments. And BINARY_MULTIPLY takes two arguments off the stack, multiplies them, and pushes the result back onto the stack.

There's a couple of optimization opportunities here that are good "rules of thumb." You can take this knowledge and apply it to any Cpython code you need to speed up (note: Cpython).

First, there's that 2 * at the front of the expression. That's fairly harmless, except that on the very next line you multiply by 6371.0, and you never do anything else with the c variable - it's just a temp. So to squeeze out some performance, go ahead and move the 2* to the next line. It turns out that the compiler will go ahead and do constant math in the same expression, so you can say 6371.0 * 2 * c and it will collapse that to a single constant.

Second, note that there's this sequence of lookups all over the place:

            169 LOAD_GLOBAL              2 (math)
            172 LOAD_ATTR                8 (asin)

In general, Python believes that any operation might cause the result of a name lookup to change. Because you can return any type, and any type can overload pretty much any operation, so why shouldn't it be possible for 2 * math.asin(x) to change the function pointed to by math.sqrt?

Because of this, and because name lookups like this really can be expensive (remember property methods and descriptors), you generally want to cache dotted-name lookups in a local variable if you're going to be looping with them:

asin = math.asin
sqrt = math.sqrt

Please note: This is not the same as doing from math import asin because that will still create a "global" name, and require a LOAD_GLOBAL operation, instead of a LOAD_FAST. Notice the FAST in the opcode name. ;-)

The same thing is true for almost every dotted name - if you are going to use it more than once, put it in a local variable.

One thing that might not be obvious is that you can cache "bound methods" - that is, method lookups like nearby.append. So you can also do:

nearby_append = nearby.append

...

nearby_append(pt)

And squeeze out another lookup.

But wait, there's more!

Because before you start doing that "peephole" optimization stuff, you need to look at improving your code in some other ways. Take a look at this:

def find(self, p):
    nearby = []
    for pt in self.data:
        # Haversine algorithm
        px, ptx, py, pty = map(math.radians, [p.x, pt.x, p.y, pt.y])

For the purposes of this function, the p object is a constant. So why do you keep doing the same conversion on it? Remember that map just applies the given function to each argument in turn. So you're calling math.radians on p.x and p.y 27000 times. Guess what? The answer isn't going to change!

Of course, I suspect that none of your points are going to change. That is, I suspect that once you create a point object, it doesn't get updated. So I think you would benefit from performing this conversion in the class initializer and storing the radian values in the object:

class Point:
    def __init__(self, lon, lat):
        self.x = lon
        self.x_radians = math.radians(lon)   # <- HERE
        self.y = lat
        self.y_radians = math.radians(lat)   # <- HERE
        self.cluster = None
        self.neighbors = 0

If you do that, you can eliminate that entire map call, and just retrieve the values. Yes, you pay an up-front cost of 27000 extra function calls, but it beats doing it in your find loop. (If you can't pay that cost, you could certainly do it as a separate loop at the front of your find function. You're going to do it anyway, and this lets you store the result.)

Also of note: math.cos(py) and math.cos(pty). You can certainly compute the cosine of py once at the top of the function. And if you're going to call this function a lot, it's probably worth storing the cosine(y) for all the points in the initializer.

Heuristics, anyone?

Another suggestion is simply to guess what's a neighbor and what's not. You've got a nice calculation there, with lots of trigonometry. But keep in mind what it's doing: it's trying to compute distance on a sphere, which is basically distance along a circle. The key word is circle.

At θ = 45°, cosθ is √2/2 as is sinθ. The sum of the two is √2, which is the maximum sum for a circle of radius 1. Thus, you know that for whatever distance N defines your neighborhood, the sum of cosine and sine will be less than or equal to √2 * N.

If your points are widely separated - that is, if you're dealing with cities and not the entrances to buildings in the same town - you can implement a heuristic: change √2 into 2.5 to allow for spherical error, and compute the corners of a "square" centered at p with sides 2 * 2.5 * N. Then just compare pt.x and pt.y with the min/max x and y of this square. Only if the point is inside the square do you perform the "expensive" computations. This adds a set of 4 comparisons to your loop, but eliminates the trig calls for all the non-matching candidates. Hopefully, that's most of the points.

This is important! If your points are heavily clustered, there's no sense having a heuristic to guess if one point is a neighbor of another - because you know the answer is yes! In that case, it would make more sense to develop a reverse heuristic, that says "here's a square contained in the circle. If the point is inside this square you know it's a neighbor, otherwise do the computation."  The objective with heuristics it to produce a fast computation that handles 75% or more of cases. If your data is biased, make the heuristic align with the biases!

Finally, another simple optimization would be to take your self.eps value and divide it by the various factors you are presently using to multiply. This can be done outside the loop, once, and saves you some cycles.

Larger-scale changes

First, don't forget that if A is a neighbor of B, then B is a neighbor of A. Make sure you are only looping over the "higher" values in your N-squared neighbor search:

for i, p1 in enumerate(points):
    for p2 in points[i+1:]:
        # etc.

You just have to be sure and add A to B's neighborhood and B to A's neighborhood at the same time.

Depending on what you're doing, there are a couple of geospatial data structures that you might profitably use. Two obvious ones are a hash of some sort and a K-d tree. The hash approach will work if your points are clustered and if you can determine a key generation algorithm that will reflect this. For example, if you know that your points are GPS coordinates in major metropolitan areas (New York, Los Angeles, Dallas, Chicago) then a hash key that "rounded" the coordinates to the nearest city center might be adequate. (Or truncated the lat/lon to, say, the nearest 5 degrees.) In this case, you'd want to have a hash value with lots of collisions. The collisions would be the likely neighbors. So you would iterate over the hash keys (equal to, say, 10% of the points) and identify which buckets you would search in. On the other hand, if the points are more distributed, or the clustering isn't obvious, then go with the K-d tree.

The K-d tree is a binary tree (or binary-search-tree if you're a child of the 21st century) that can be used for locating any point. To find neighboring points using your distance function, you would simply do the distance computation at each node of the tree. The special case would be when a node's key value is within the heuristic neighborhood of your target point, you'll have to traverse both children of the node, to find any other nodes in the other half of the tree that might be in the neighborhood. For example, if a node is a lat node, with lat=A, and your target point has lat=A-2km, then for neighborhood=5km you'll have to search on either side of that node.

Also, note that you'll need to develop a strategy for nodes with equal values. For example, if two points have the same longitude, would you store a list-of-points in the node, or make a rule that says "sort by lowest latitude and put the other points in the right hand subtree"? It's up to you, but you need to handle it. (I suggest the latter.)


Integer-to-ASCII algorithm (x86 assembly) This is my best effort at converting a 32 bit integer in EAX, to an 8 character ascii string (result in RDI).  It will work accurately up to 99,999,999.  Higher values could be done using an xmm register.  The byte order in RDI is correct (e.g. if copied directly to video ram, the most significant byte is displayed first)  No expensive DIV instructions or memory accesses required.  Can this be improved further?

    mov ebx, 0xCCCCCCCD
    xor rdi, rdi
.loop:
    mov ecx, eax                    ; save original number

    mul ebx                         ; divide by 10 using agner fog's 'magic number'
    shr edx, 3                      ;

    mov eax, edx                    ; store it back into eax

    lea edx, [edx*4 + edx]          ; multiply by 10
    lea edx, [edx*2 - '0']          ; and ascii it
    sub ecx, edx                    ; subtract from original number to get remainder

    shl rdi, 8                      ; shift in to least significant byte
    or rdi, rcx                     ;

    test eax, eax
    jnz .loop

There are all sorts of things that LOOK like they should perform better, but I can only get a tiny bit of improvement.  And that may disappear (or worsen) on other hardware:

    mov ebx, 0xCCCCCCCD
    xor rdi, rdi

.loop:
    mov ecx, eax                    ; save original number

    mul ebx                         ; divide by 10 using agner fog's 'magic number'
    shr edx, 3                      ;

    mov eax, edx                    ; store quotient for next loop

    lea edx, [edx*4 + edx]          ; multiply by 10
    shl rdi, 8                      ; make room for byte
    lea edx, [edx*2 - '0']          ; finish *10 and convert to ascii
    sub ecx, edx                    ; subtract from original number to get remainder

    lea rdi, [rdi + rcx]            ; store next byte

    test eax, eax
    jnz .loop

The 2 changes are:

Move shl rdi to a 'better' place
Use lea instead of or to set rdi


Checking which pypi packages are Py3k-only I looked at the pypi classifiers and some guide to help me write the following script, and here's me wondering if it can be improved:

import xmlrpc.client

# pypi language version classifiers
PY3 =  ["Programming Language :: Python :: 3"]
PY2 =  ["Programming Language :: Python :: 2"]
PY27 = ["Programming Language :: Python :: 2.7"]
PY26 = ["Programming Language :: Python :: 2.6"]
PY25 = ["Programming Language :: Python :: 2.5"]
PY24 = ["Programming Language :: Python :: 2.4"]
PY23 = ["Programming Language :: Python :: 2.3"]

def main():
    client = xmlrpc.client.ServerProxy('http://pypi.python.org/pypi')

    # get module metadata
    py3names = [name[0] for name in client.browse(PY3)]
    py2names = [name[0] for name in client.browse(PY2)]
    py27names = [name[0] for name in client.browse(PY27)]
    py26names = [name[0] for name in client.browse(PY26)]
    py25names = [name[0] for name in client.browse(PY25)]
    py24names = [name[0] for name in client.browse(PY24)]
    py23names = [name[0] for name in client.browse(PY23)]

    cnt = 0
    for py3name in py3names:
        if py3name not in py27names \
           and py3name not in py26names \
           and py3name not in py25names \
           and py3name not in py24names \
           and py3name not in py23names \
           and py3name not in py2names:
            cnt += 1

    print("Python3-only packages: {}".format(cnt))

main()

Sidenote:

$ time python3 py3k-only.py
Python3-only packages: 259

real    0m17.312s
user    0m0.324s
sys 0m0.012s

In addition, can you spot any functionality bugs in there?  Will it give accurate results, assuming that pypi has correct info?

import xmlrpc.client

# pypi language version classifiers
PY3 =  ["Programming Language :: Python :: 3"]

Why do you have a single string in a list?

PY2 =  ["Programming Language :: Python :: 2"]
PY27 = ["Programming Language :: Python :: 2.7"]
PY26 = ["Programming Language :: Python :: 2.6"]
PY25 = ["Programming Language :: Python :: 2.5"]
PY24 = ["Programming Language :: Python :: 2.4"]
PY23 = ["Programming Language :: Python :: 2.3"]

You should put all these strings in one list.

def main():
    client = xmlrpc.client.ServerProxy('http://pypi.python.org/pypi')

    # get module metadata
    py3names = [name[0] for name in client.browse(PY3)]
    py2names = [name[0] for name in client.browse(PY2)]
    py27names = [name[0] for name in client.browse(PY27)]
    py26names = [name[0] for name in client.browse(PY26)]
    py25names = [name[0] for name in client.browse(PY25)]
    py24names = [name[0] for name in client.browse(PY24)]
    py23names = [name[0] for name in client.browse(PY23)]

If you put the python 2.x versions in a one list, you should be able to fetch all this data
into one big list rather then all of these lists.

    cnt = 0

Don't uselessly abbreviate, spell out counter

    for py3name in py3names:
        if py3name not in py27names \
           and py3name not in py26names \
           and py3name not in py25names \
           and py3name not in py24names \
           and py3name not in py23names \
           and py3name not in py2names:
            cnt += 1

I'd do something like: python3_only = [name for name in py3name if py3name not in py2names]. Then I'd get the number of packages as a len of that.

    print("Python3-only packages: {}".format(cnt))

main()

Usually practice is to the call to main inside if __name__ == '__main__': so that it only gets run if this script is the main script.


Searching over more models rails I'm trying to implement search over two models. In this example Book and Article. Here are the attributes from both of these :

Article(id: integer, magazine: string, title: string, body: text, created_at: datetime, updated_at: datetime)
Book(id: integer, publisher: string, author: string, title: string, foreword: text, body: text, created_at: datetime, updated_at: datetime)

I'm trying to search over multiple attributes on both of these Models using the same search string and combining results. Because my next goal is to have a permlink to results.

Here is how I implemented search on these Models:

def self.search(q)
  Article.where('magazine like :value OR title like :value OR body like :value', value: "%#{q}%")
 end

def self.search(q)
  Book.where('publisher like :value OR author like :value OR title like :value OR foreword like :value OR body like :value', value: "%#{q}%")
end

Here is the controller :

class HomeController < ApplicationController
    def search
      articles = Article.search(params[:q])
      books = Book.search(params[:q])

      @results = articles + books
    end
end

I use haml so here is my searchresult page :

%div.main
  %div.pull.left
    =link_to 'Back to search', '/',:class => 'btn btn-primary btn-lg'
  %div.clearfix
  %table.table.table-condensed
    %thead
      %tr
        %th Id
        %th Title
        %th Type
    %tbody
      - @results.each do |item|
        %tr
          %td #{item.id}
          %td #{item.title}
          %td #{item.class.name}

Is there a more elegant way to actually do the search? I don't have that many experience with rails but I was reading trough this article :

http://blog.codeclimate.com/blog/2012/10/17/7-ways-to-decompose-fat-activerecord-models/

1. And I was thinking I could do this as 2. Extract Service Objects, but as two search methods search over different attributes I wasn't able to do this? I'd be glad to hear your take on this.

2. Regarding the permlink to my search. I'm wondering should I create another model named i.e SearchResult and then link the single search result to many Books and Articles?

Update

I'm not looking for solutions like Sunspot or Sphinx, as this is a small app in dev mode just for practising but still I want it to be as better as possible.

you want a separate model for search, i.e.

class SearchResult < AR::Base
  #columns: content, title, user
  belongs_to :searchable, polymorphic: true
end

class Book < AR::Base
  has_one :searchable, polymorphic: true, class_name: 'SearchResult'
  belongs_to :user

  after_create :autobuild_searchable
  after_commit :update_search

  private

  def autocreate_searchable
    self.create_searchable
  end

  def update_search_content
    searchable.update_attributes(content: "#{title} #{author}", title: title, user: user.username)
  end
end

class SearchController
  def search
    @result = SearchResult.where("content like ?", "%#{params[:q]}%")
    if params[:user]
      @result = @result.where(user: params[:user])
    end
  end
end

Finally in view you can render the actual results, i.e.

= render @result.map(&:searchable)

(rails will render correct partial for each element, whatever it's book, magazine or anything, it will look for views/magazines/_magazine, views/books/_book)

You can extend the search with extra columns to use them as additional filters (here i've added user) and you don't pollute your models with extra search logic.
How will you handle the searchable content is up to you (here is just a primitive example). You can split it into separate columns (ie. search_field1, search_field2, search_field3), you can tokenize the input or build a fulltext index.

you can store a permalink in SearchResult or you can generate in on the fly. You may have some issues with rails path helpers on polymorphic associations, but those are easy to overcome.

If you have postgres as database i advise you to take a look on pg_search, it's simple and brilliant solution: https://github.com/Casecommons/pg_search and should give you better understanding on this topic.

The above code may not work, I didn't check it against Ruby/Rails, just trying to show an idea.


Tridiagonal Lists in Scheme (define (tridiagonal n)
   (build-list n
               (lambda (x)
                 (build-list n
                           (lambda (x)
                             (cond
                               [(= x n) 2]
                               [(or (= x (- n 1))
                                    (= x (+ n 1))) 1]
                               [else 0]))))))

The above is my attempt at making a tridiagonal patterns of lists.
Restrictions:

Consumed integer n is greater than 2
At most 3 non-zero value occour in a list.

Examples:

(tridiagonal 3) => (list (list 2 1 0) (list 1 2 1) (list 0 1 2))
(tridiagonal 5) => (list (list 2 1 0 0 0) (list 1 2 1 0 0) (list 0 1 2 1 0) (list 0 0 1 2 1) (list 0 0 0 1 2))

Your code doesn't actually work, because your two lambdas both used x as the parameter name, and the inner one shadows the outer one. Here's a fixed version:

(define (tridiagonal n)
  (build-list n
              (lambda (x)
                (build-list n
                            (lambda (y)
                              (cond
                                [(= x y) 2]
                                [(or (= x (sub1 y))
                                     (= x (add1 y))) 1]
                                [else 0]))))))

This works, but in Racket, it's probably more idiomatic to use for/list for creating a list:

(define (tridiagonal n)
  (for/list ((i (in-range n)))
    (for/list ((j (in-range n)))
      (max 0 (- 2 (abs (- i j)))))))

As you can see, I've taken the liberty of simplifying your cond expression too, into a single (max 0 (- 2 (abs (- i j)))) expression.


Class for sorting pool balls I have written this code for fun. I'd like to hear your suggestions about how to make it more compact and pythonic.

from random import shuffle

class Pool(object):
    """
    Simple object that allows to sort
    """

    def __init__(self):
        """
        During initalization the final grid containing
        ordered balls is created
        1 is placeholder for Solid balls
        0 is placeholder for Striped balls
        """
        self.grid = [[1],[0,0],[1,0,1],[0,1,0,0],[1,0,1,0,1]]

    def create_ball_set(self):
        """
        This function returns a list containing
        a shuffled pool balls set
        """
        balls = []
        [balls.append([number]) for number in range(1, 16)]
        for ball in balls:
            if ball[0] < 9:
                ball.append("Solid")
            else:
                ball.append("Striped")
        shuffle(balls)
        return balls

    def sort_ball_set(self, unsorted_balls):
        """
        This function returns a
        list of sorted balls from a list of
        shuffled balls
        """
        # Ball 1 always goes in 1st place
        self.grid[0][0] = unsorted_balls.pop(unsorted_balls.index([1, 'Solid']))
        # Ball 8 always goes in the 2nd row, in the middle
        self.grid[2][1] = unsorted_balls.pop(unsorted_balls.index([8, 'Solid']))
        # Creating an empty list for solid balls
        unsorted_solid_balls = []
        # Same thing but for striped balls
        unsorted_striped_balls = []

        # Now it is time to divide solid balls from striped ones
        for ball in unsorted_balls:
            if ball[1] == 'Solid':
                unsorted_solid_balls.append(ball)
            elif ball[1] == 'Striped':
                unsorted_striped_balls.append(ball)

        # Once the balls are divided it is time to put them in the grid
        for grid_row_index, grid_row in enumerate(self.grid):
            for grid_col_index, grid_col_value in enumerate(grid_row):
                # In their corresponding placeholder spot
                if grid_col_value == 1:
                    # 1 is for solid balls
                    self.grid[grid_row_index][grid_col_index] = unsorted_solid_balls.pop()
                elif grid_col_value == 0:
                    # 0 is for striped balls
                    self.grid[grid_row_index][grid_col_index] = unsorted_striped_balls.pop()
        return self.grid

pool_table = Pool()
print "Getting new set of balls from the pool table:"
unsorted_balls = pool_table.create_ball_set()
print unsorted_balls
print "Sorted balls:"
sorted_balls = pool_table.sort_ball_set(unsorted_balls)
# Pretty printing sorted balls
for row in sorted_balls:
    print row

I think it is usually better to take advantage of the built-in functions. Python lists already have a sort function, so you would expect a list of pool balls to be sortable by the start arrangement (a list of tuples/lists is already sortable, Python compares them element wise).

One way to achieve that is with a custom key function:

order = [1, 13, 11, 7, 8, 6, 9, 5, 14, 15, 2, 12, 3, 10, 4]
# Simplified balls list, as the fill style is not really needed for this
balls = [[n] for n in range(1, 16)]
balls.sort(key=lambda ball: order.index(ball[0]))

This is very succinct, but you could also promote the lambda key function to a proper function:

def pool_start_order(ball):
    order = [1, 13, 11, 7, 8, 6, 9, 5, 14, 15, 2, 12, 3, 10, 4]
    return order.index(ball[0])

balls = [[n] for n in range(1, 16)]
balls.sort(key=pool_start_order)

Another alternative is to make a PoolBall class, that is sortable, something like this:

class PoolBall(object):
    order = [1, 13, 11, 7, 8, 6, 9, 5, 14, 15, 2, 12, 3, 10, 4]

    def __init__(self, number):
        assert 1 <= number <= 15
        self.number = number
        self.fill = 'Solid' if number <= 8 else 'Striped'
        self.order = PoolBall.order.index(number)

    def __lt__(self, other):
        return self.order < other.order

    def __eq__(self, other):
        return self.number == other.number

    def __str__(self):
        return "{self.number} {self.fill}".format(self=self)

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

    balls = [PoolBall(i) for i in range(1, 16)]
    balls.sort()

Here, the __str__ and __repr__ are just there for pretty printing.

Whichever way you go, once you have a correctly sorted list of balls, you can use a function that successively takes one more ball, something like:

def pyramid_arrangement(balls):
    """
    Given a list of balls, arranges them in a pyramid shape.
    Yields each row.

    Leaves the balls list empty.
    """
    take = 1
    while balls:
        yield [balls.pop() for _ in range(take)]
        take += 1

Which you can use like this:

if __name__ == "__main__":
    balls = [PoolBall(i) for i in range(1, 16)]
    balls.sort(reverse=True)
    for row in pyramid_arrangement(balls):
        print row


SELECTing percentage and count of votes I have the following tables structures:

CREATE TABLE IF NOT EXISTS `options` (
  `option_id` tinyint(4) unsigned NOT NULL,
  `poll_id` mediumint(8) unsigned NOT NULL,
  `option` tinytext NOT NULL,
  UNIQUE KEY `option_id_poll_id` (`option_id`,`poll_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COMMENT='Storing poll options/choices';

CREATE TABLE IF NOT EXISTS `questions` (
  `poll_id` mediumint(8) unsigned NOT NULL AUTO_INCREMENT,
  `deleted` bit(1) NOT NULL DEFAULT b'0',
  `question` tinytext NOT NULL,
  `nick` varchar(32) NOT NULL,
  `dated` datetime NOT NULL,
  PRIMARY KEY (`poll_id`),
  KEY `deleted` (`deleted`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COMMENT='Table to store poll questions/titles';

CREATE TABLE IF NOT EXISTS `votes` (
  `poll_id` mediumint(8) unsigned NOT NULL,
  `option_id` tinyint(4) unsigned NOT NULL,
  `nick` varchar(32) NOT NULL,
  `dated` datetime NOT NULL,
  UNIQUE KEY `poll_id_nick` (`poll_id`,`nick`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

I am displaying details for a particular poll_id using the following query:

SELECT
    o.option_id AS option_id,
    o.`option` AS `option`,
    COUNT(v.nick) AS total,
    FLOOR(
        ( COUNT(v.nick) / (SELECT COUNT(1) FROM votes WHERE poll_id = %d) ) * 100
    ) AS percentage
FROM options o
LEFT JOIN votes v
    ON o.poll_id = v.poll_id
    AND v.option_id = o.option_id
WHERE o.poll_id = %d
GROUP BY o.option_id
ORDER BY total DESC, o.option_id ASC;

I am not satisfied with the way that I am calculating the percentage votes on each of the available options! %d is place-holder for string.format function.

I'd like a review on the query/table structures above.

It took me a while to realize that you must be considering a poll to be a single question (posted on a web page) that allows people to pick from a series of options for that single question.

Some things to consider:

[options] Consider reversing the index field order. It would seem probable that you will want to query up the options for a poll without specifying the option_id.
[questions] There appears to be no real point to indexing the deleted bit. When pulling questions up for a poll you can certainly exclude those that are deleted without needing an index.
[votes] I'm guessing that 'nick' is the login name of the user choosing an option from a single question poll?
Look at an explain to see if MySQL has optimized your sub-query into a single lookup. If not, do your own explicit query or consider using group by modifiers to do a rollup when you pull up poll stats. Then, in either case, as you load records for a poll (as you'll have some code for web display purposes) do the percentage calculation as you generate the output table.

Finally, it is customary to "select count(*) from tab" when you don't care about the columns involved.


Putting rows of ascending digits and eliminate rows of other digits, leaving other symbols intact For example, sequence "aasdf123456785fg87" will be transformed into "aasdf12345678fg", using getchar and putchar and then using strings.

With getchar and putchar:

char c = 0, c_ = 0;
char flag = 0;
while ((c = getchar()) != '.')
{
    if (isdigit(c))
    {
        if (!isdigit(c_))
        {
            flag = 0;
            c_ = c;
            while (true)
            {
                c = getchar();
                if (!isdigit(c))
                {
                    if (flag)(putchar(c_));
                    putchar(c);
                    break;
                }

                if (c - c_ == 1)
                {
                    flag = 1;
                    putchar(c_);
                }
                c_ = c;
            }
        }
    }
    else putchar(c);

    c_ = c;
}

and using strings:

char str[100] = { 0 }, outstr[100] = { 0 };
int i = 1;
char flag = 0;
int c = 0;
gets(str);
while (true)
{
    if (isdigit(str[i]))
    {
        if (isdigit(str[i - 1]))
        {
            if (str[i] - str[i - 1] == 1)
            {
                outstr[c++] = str[i - 1];
                flag = 1;
            }
            else
            {
                if (flag)outstr[c++] = str[i - 1];
                flag = 0;
            }
        }
    }
    else
    {
        if (flag)
        {
            outstr[c++] = str[i - 1];
            flag = 0;
        }
        if (str[i] == '.')break;
        outstr[c++] = str[i];
    }
    i++;
}
puts(outstr);

This code is not great, and I ask you to make it easier to understand and more effective. The thing is that I need to show these programs to my teacher, and he's going to see them done as easier and smarter as possible. I just don't know if it's okay.

Review of the getchar and putchar: portion

Testing the "With getchar and putchar:" code would be easier if given a function declaration to see clearly what are inputs and outputs.  Example:

void UpdigitsFilter_IO(void) {
// or
int UpdigitsFilter_IO(void) {

Code uses '.' as a terminator, but that is not listed as a design criteria.  Was this to be '\0'?
Code uses char c, whereas getchar() returns an int.  This causes issues in 2 places, when EOF is encountered and char outside the 0 - SCHAR_MAX (typically 127).  Proper use of is...() functions require values in the 0 to UCHAR_MAX range or EOF.

// char c = 0;
int c = 0;

Exiting the loop on EOF should occur  (2x  places)

// while ((c = getchar()) != '.')
while ((c = getchar()) != '.' || c == EOF)

There is a discrepancy between "ascending digits" and if (c - c_ == 1).  The first implies "135" is acceptable as the digits are greater than previous, but code implies they need to be sequential.  Assume sequential.
The requirements are silent on single digits sequences.  Assume acceptable.
Check the return value of putchar().  Maybe make this the function's return when non-zero.

int retval = putchar(ch);
if (retval) {
  return retval;
}

Filtering will not stop if a '.' is encountered in the inner c = getchar();.  Add checks here for '.' and EOF.


Allowing messages to be passed to listeners I have written an implementation of the observer pattern that allows messages to be passed to listeners in what would normally be the notify() method. For example a subscriber sub-class might look like the pseudo-code below, where Message is a simple class that can be subclassed and made to contain value objects or other data.

class MySubscriber extends Subscriber
{
    @Override
    public void notify( Message m )
    {
        if( m.getClass == MyMessage )
        {
            MyMessage myMessage = ( MyMessage ) m;
            if( myMessage.name == MyMessage.START )
            {
                // -- Finally do something here
            }
        }

        if( m.getClass == MyOtherMessage )
        {
            MyOtherMessage myOtherMessage = ( MyOtherMessage ) m;
            if( myOtherMessage.name == MyOtherMessage.INIT_SOMETHING )
            {
                // -- Finally do something else here
            }
        }

    }
}

Using conditionals like this to determine the message type seems a bit redundant and can get tedious in cases where a subscriber is listening for many message types. However, it is pretty explicit, easy to read and the implementation is quite simple. Is there a cleaner approach to achieve a similar result?

Personally I prefer polymorphism instead of conditions in such cases, as it helps to keep big conditions in a clean fashion - each condition in it's own class. As an example, in .NET they have generic event-handlers (subscribers) and following class system takes place (or something along these lines):

abstract class EventArgs { ... } // your abstract data class, Message if you will
class MyEventArgs : EventArgs { } // and it's implementation

abstract class EventHandler<T> // an abstract Subscriber
{
    public abstract Notify(T args); // Subscriber::notify() in your example
}

class MyEventHandler : EventHandler<MyEventArgs>  // an implementation of a subscriber for one specific case, which would be MyEventArgs
{
    public Notify(MyEventArgs args) { ... }
}


Number of zeroes at the end of a factorial I was working with this problem, which is to find the number of zeros at the end of any factorial.

Here's my solution:

#include<bits/stdc++.h>
using namespace std;
int main(){

    int numCases,num,zeroCount=0,mulFive,temp,i=0;
    cout<<numeric_limits<int>::max()-1000000000<<endl;
    cin>>numCases;
    int solutionArray[numCases];
    temp=numCases;
    while(numCases--)
    {
         zeroCount=0;
         cin>>num;
         mulFive=5;
         while(num/mulFive!=0)
         {
             zeroCount=zeroCount+ (num/mulFive);
             mulFive=mulFive*5;
         }
         solutionArray[i]=zeroCount;
         i++;
         //cout<<zeroCount;
    }
    for(int k=0;k<temp;k++)
        cout<<solutionArray[k]<<endl;

    return 0;
}

This is the most basic code that I could come up with. How should I make it more efficient using the same logic?  Perhaps I should use different logic?

There is a problem with your solution for large numbers ( >= 5^13 to be exact) because mulFive=mulFive*5; will go negative as the int overflows.

To protect against this, you could do

 while(num/5!=0)
 {
     zeroCount=zeroCount+ (num/5);
     num = num/5;
 }

i.e. divide the number rather than multiply the divisor, then only the size of num is a limit (2^31-1)


Truncate String to target length using only whole words I've got a bit of code that I'm wanting to tidy up. The aim is to take a String that consists of multiple words connected by a separator (It's produced using Collectors.joining(SEPARATOR) as below, although the stream processing is not quite so trivial), and return a portion from the front of it.

This portion should never contain partial words, but should in most cases be less than the TARGET_LENGTH number of total characters. It is safe to assume that the words themselves do not contain the SEPARATOR character.

String SEPARATOR = "-";
int TARGET_LENGTH = 20;

//Expected output: "this-is-a-sample"
String s = Arrays.asList("this", "is", "a", "sample", "string")
            .stream()
            .collect(Collectors.joining(SEPARATOR));

if (s.length() > TARGET_LENGTH) {
    if (s.contains(SEPARATOR)) {
        if (s.substring(0, TARGET_LENGTH + 1).contains(SEPARATOR)) {
            return s.substring(0, s.substring(0, TARGET_LENGTH + 1).lastIndexOf(SEPARATOR));
        } else {
            return s.substring(0, s.indexOf(SEPARATOR));
        }
    }
}
return s;

Expected output is as follows:

s                                   ||  result
"easy"                              ||  "easy"
"simple-case"                       ||  "simple-case"
"very-long-input-will-be-truncated" ||  "very-long-input-will"
"countercountermeasures"            ||  "countercountermeasures" //Longer than 20 chars
"countercountermeasures-foo-bar-baz"||  "countercountermeasures" //Longer than 20 chars
"a-b-c-d-e-f-g-veryveryverylongword"||  "a-b-c-d-e-f-g"

The provided code works, but isn't very clear and I imagine it will be horrible to maintain if any requirements change in the future. I'm looking for suggestions as to how it could be improved. I've considered adding a filter to the Stream that generates the String, with a counter keeping track of the current output length declared outside of the string-generation, but this feels like an even worse thing to do (At a guess I'd have to do something silly like update the counter from within a call to Stream.map())

Style

if (s.length() > TARGET_LENGTH) {
    if (s.contains(SEPARATOR)) {
        if (s.substring(0, TARGET_LENGTH + 1).contains(SEPARATOR)) {
            return s.substring(0, s.substring(0, TARGET_LENGTH + 1).lastIndexOf(SEPARATOR));
        } else {
            return s.substring(0, s.indexOf(SEPARATOR));
        }
    }
}

The above code is cumbersome. When you have a return statement inside an if-condition, there is no reason to have an 'else' condition.

Additionally, when you are using early-returns anyway, there's no reason to have such nested code blocks....

Alternatives

I can see multiple options to this problem. I would recommend testing them to see which performs better for you. The Regex option may in fact be faster if the pattern is reused often.

On the fly

In your own answer, you suggest on-the-fly building of the string, and ending early. This is a good option, but I would do it differently:

public static String portion(final int length, final String separator, String...words) {
    if (words.length == 0) {
        return "";
    }

    StringBuilder sb = new StringBuilder(length);
    sb.append(words[0]);
    for (int i = 1; i < words.length; i++) {
        if (sb.length() + separator.length() + words[i].length() > length) {
            return sb.toString();
        }
        sb.append(separator).append(words[i]);
    }
    return sb.toString();
}

Regex

Yeah, yeah, the whole "use a regular expression, now you have two problems...." but, this concept is:

If the String is < 20 chars, or has a separator within the 20 chars, take the longest string.
If the string is >= 20 or there are no separators within 20, then take until the end of string, or the first separator, whichever is shorter.

If you have the separator - and the length 20, then this can be expressed in the regex:

^(.{0,20}(?=$|-)|.*?(?=$|-))

where:

.{0,20}(?=$|-)

is: find up to 20 chars followed either by the end-of-line, or a separator.

and:

.*?(?=$|-)

is: otherwise, if the previous test fails, take until the end-of-line, or the next separator, whichever happens first.

You can build this in to a reusable pattern (and being defensive about separators that may have special regex meaning....):

private static final Pattern buildPattern(int length, String separator) {
    String qpat = Pattern.quote(separator);
    return Pattern.compile(String.format("^(.{0,%d}(?=$|%s)|.*?(?=$|%s))", length, qpat, qpat));
}

Then, you can use this as follows:

public static String portion(Pattern pat, String s) {
    Matcher mat = pat.matcher(s);
    mat.find(); // patterns will always match, will never fail...
    return mat.group();
}

I imagine this can be used, in your code, like:

private static final Pattern TWENTY_DASH = buildPattern(TARGET_LENGTH, SEPARATOR);

and then in your remaining code:

String s = Arrays.asList("this", "is", "a", "sample", "string")
            .stream()
            .collect(Collectors.joining(SEPARATOR));

return portion(TWENTY_DASH, s);

Return-Early

Having suggested the RegEx option, I would also suggest a simplified lastIndexOf/indexOf using early-returns, instead of nested if-blocks:

public static String portion(final int length, final String separator, String text) {

    if (text.length() <= length) {
        return text;
    }

    int pos = text.lastIndexOf(separator, length);
    if (pos >= 0) {
        return text.substring(0, pos);
    }

    pos = text.indexOf(separator, length);
    if (pos >= 0) {
        return text.substring(0, pos);
    }

    return text;

}


Creating an 2D array using pointer/malloc, and then print it out I am trying to write 2 functions, one to read the matrix (2D array) and other one to print it out. So far I have:

/* Read a matrix: allocate space, read elements, return pointer. The
   number of rows and columns are given by the two arguments. */
double **read_matrix(int rows, int cols){

    double **mat = (double **) malloc(sizeof(double *)*rows);
    int i=0;
    for(i=0; i<rows; i++){
    /* Allocate array, store pointer  */
    mat[i] = (double *) malloc(sizeof(double)*cols);
   //what to do after??

     return mat;
}

then the print matrix function, not sure if it is correct

 void print_matrix(int rows, int cols, double **mat){
  for(i=0; i<rows; i++){    /* Iterate of each row */
    for(j=0; j<cols; j++){  /* In each row, go over each col element  */
    printf("%f ",mat[i][j]); /* Print each row element */
}
}}

and here is the main function I am using to run:

#include <stdio.h>
#include <stdlib.h>

double **read_matrix(int rows, int cols);
void print_matrix(int rows, int cols, double **mat);
void free_matrix(int rows, double **mat);

int main(){

  double **matrix;
  int rows, cols;
  /* First matrix */
  printf("Matrix 1\n");
  printf("Enter # of rows and cols: ");
  scanf("%d %d",&rows,&cols);
  printf("Matrix, enter %d reals: ",rows*cols);
  matrix = read_matrix(rows,cols);
  printf("Your Matrix\n");  /* Print the entered data */
  print_matrix(rows,cols,matrix);
  free_matrix(rows, matrix);   /* Free the matrix */

    return 0;}

It seems OK to me as far as it goes. A couple of suggestions though:

read_matrix may be better split up into two functions, one to create it and the other to read the contents from the source, even if the create_matrix function is called from read_matrix - and you need to be aware of the possibility that the allocation may fail.
On the other hand, you may wish to consider just allocating a single block of size rows*cols of memory, and indexing it via y*rows + x rather than allocating several smaller blocks.
For 'neatness', you should consider using calloc( number_of_elements, sizeof (double) ) instead of malloc, just to give a (possibly) sensible initial value.
print_matrix could do with some layout changes, such that each row is on a separate line, and the corresponding cells line up under each other, something like %10.3f (but would depend on the type of data expected).


Graph implementation in C++ using adjacency list there is my final code for implementing a Graph in C++ using adjacency list and Object-oriented. I got some help from StackOverflow and it was really helpful, but now I would ask about some advice for improving and a possible way of implementing two functions: isPath( v, w ) for finding if two nodes are connected and isConnected(graph) returning "yes" if the graph is strongly connected otherwise "no".

The code:

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int source;
    int target;
};

class Graph
{
private:
    int numOfNodes;
    vector<vector<int>> baseVec;

public:
    Graph(int numOfNodes) : numOfNodes(numOfNodes), baseVec(numOfNodes) {}

    void newEdge(Edge edge) {
        if (edge.source >= numOfNodes || edge.target >= numOfNodes
            || edge.source < 0 || edge.target < 0) {
            cout << "Invalid edge!\n";
            return;
        }
        baseVec[edge.source].emplace_back(edge.target);
        baseVec[edge.target].emplace_back(edge.source);
    }

    void display() {
        for (vector<vector<int>>::size_type i = 0; i < baseVec.size(); i++) {
            cout << "\n Adjacency list of vertex " << i << "\n head: ";
            for (vector<int>::size_type j = 0; j < baseVec[i].size(); j++)
                cout << baseVec[i][j] << " ";
            std::cout << std::endl;
        }
    }
};

int main() {
    int vertex;
    cout << "Enter number of nodes: ";
    cin >> vertex;

    Graph graph(vertex);

    while (true) {
        int source, target;
        cout << "Enter edge ex.1 2 (-1 -1 to exit): \n";
        cin >> source >> target;
        if ((source == -1) && (target == -1))
            break;
        graph.newEdge({ source, target });
    }
    graph.display();
    return 0;
}

I really can't find many things to change, so I wrote the isConnected() function. Maybe it has some weaknesses or errors. Hope it's useful and I'm still waiting for advice. Thank you!

Code inside the class:

    bool isConected(std::vector<int> nodeVec)
        {

            for (st

d::vector<std::vector<int>>::size_type i = 0; i < baseVec.size(); i++)
        {
            if (baseVec[i].empty())
            {
                return false;
            }
        }
        for (std::vector<std::vector<int>>::size_type i = 0; i < baseVec.size(); i++)
        {
            for (std::vector<int>::size_type j = 0; j < baseVec[i].size() + 1; j++)
            {
                if (baseVec[i][j] == nodeVec[j + 1])
                {
                    return true;
                }
            }
        }
    }

The line in main:

std::vector<int> nodeVec;
    for (int i = 0; i < vertex; i++)
    {
        nodeVec.emplace_back(i);
    }

And:

if (graph.isConected(nodeVec) == true)
{
    std::cout << "Yes\n";
}
else
{
    std::cout << "No\n";
}

Some comments -

cout << "Invalid edge" is not a sane error-relaying mechanism. The C++ way to do things is to throw an exception. The calling code could catch the exception and print an error, or could let the app exit if this is a serious-enough error.
void display() needs to be void display() const. It doesn't modify anything.
Don't iterate through an STL container using an integer index. Iterate using an iterator. If you don't know what I mean, google around or read https://www.geeksforgeeks.org/iterators-c-stl/


Given an array find any three numbers which sum to zero Looking for optimizations and cleaner, more pythonic ways of implementing the following code.

#Given an array find any three numbers which sum to zero.

import unittest

def sum_to_zero(a):
    a.sort(reverse=True)
    len_a = len(a)
    if  len_a < 3:
        return []
    for i in xrange(0, len_a):
        j = i + 1
        for k in xrange(j + 1, len_a):
            if a[j] + a[k] == -1 * a[i]:
                return [a[i], a[j], a[k]]
    return []

class SumToZeroTest(unittest.TestCase):

    def test_sum_to_zero_basic(self):
        a = [1, 2, 3, -1, -2, -3, -5, 1, 10, 100, -200]
        res = sum_to_zero(a)
        self.assertEqual([3, 2, -5], res, str(res))

    def test_sum_to_zero_no_res(self):
        a = [1, 1, 1, 1]
        res = sum_to_zero(a)
        self.assertEqual(res, [], str(res))

    def test_small_array(self):
        a = [1, 2, -3]
        res = sum_to_zero(a)
        self.assertEqual(res, [2, 1, -3], str(res))

    def test_invalid_array(self):
        a = [1, 2]
        res = sum_to_zero(a)
        self.assertEqual(res, [], str(res))

#nosetests sum_to_zero.py

Your code fails this test case:

def test_winston1(self):
    res = sum_to_zero([125, 124, -100, -25])
    self.assertEqual(res, [125,-100,-25])

As for the code

def sum_to_zero(a):
    a.sort(reverse=True)

Why sort?

    len_a = len(a)
    if  len_a < 3:
        return []
    for i in xrange(0, len_a):

You can just do xrange(len_a). I recommend doing for i, a_i in enumerate(a) to avoid having the index the array later.

        j = i + 1

Thar be your bug, you can't assumed that j will be i + 1.

        for k in xrange(j + 1, len_a):
            if a[j] + a[k] == -1 * a[i]:

Why this instead of a[j] + a[k] + a[i] == 0?

                return [a[i], a[j], a[k]]
    return []

Not a good a choice of return value. I'd return None. An empty list isn't a natural continuation of the other outputs.

Here is my implementation of it:

def sum_to_zero(a):
    a.sort(reverse = True)
    for triplet in itertools.combinations(a, 3):
        if sum(triplet) == 0:
            return list(triplet)
    return []


Custom date data type in C I've created a very basic date data type in C simply to practice writing my own data type. Please critique.

#include <stdio.h>
#include <stdlib.h>
enum DATE_FORMAT{DASHES,SLASHES};
typedef enum DATE_FORMAT DFORMAT;
typedef struct {
    unsigned char day;
    unsigned char month;
    unsigned short year;
} DATE;

/* Allocates new DATE with specified values and returns a ptr to it. User must NULL-check */
DATE *create_date(unsigned char month, unsigned char day, unsigned short year)
{
    if((month > 12) || (month < 1))
        return NULL;
    if((day > 31) || (day < 1))
        return NULL;
    if((year > 9999) || (year < 0))
        return NULL;
    DATE *the_date = malloc(sizeof(DATE));
    if(the_date == NULL)
        return NULL;
    the_date->day = day;
    the_date->month = month;
    the_date->year = year;
    return the_date;
}
void printf_date(DATE *input, DFORMAT format)
{
    if(input == NULL)
        printf("Invalid DATE.\n");
    if(format == DASHES)
        printf("%hhu-%hhu-%hu\n",input->month,input->day,input->year);
    if(format == SLASHES)
        printf("%hhu/%hhu/%hu\n",input->month,input->day,input->year);
    return;
}
void free_date(DATE *dtf)
{
    if(dtf == NULL)
    {
        printf("Date free failed.\n");
    }
    else
    {
        free(dtf);
        printf("Date freed successfully\n");
    }
    return;
}

int main()
{
    DATE *my_date = create_date(3,17,2017);
    if(my_date == NULL)
    {
        printf("Please provide a valid date next time... exiting.\n");
        return(EXIT_FAILURE);
    }
    printf_date(my_date, SLASHES);
    printf_date(my_date, DASHES);
    free_date(my_date);
    return(EXIT_SUCCESS);
}

DATE *create_date(unsigned char month, unsigned char day, unsigned short year)

What if I want to create a DATE on the stack?

    if((month > 12) || (month < 1))
        return NULL;
    if((day > 31) || (day < 1))
        return NULL;
    if((year > 9999) || (year < 0))
        return NULL;

There are many date libraries out there, and they're not consistent on their offsets for months. I would consider creating an enum for the months.

Also, either don't validate the values at all or validate them fully. If I can't create 2017-13-01 then why can I create 2017-02-31? If I can't create a date in 753 BC then why can I create a date in year 0 (whatever that means – 1 BC?)?

Obviously that comes with some caveats, particularly with respect to the transition from the Julian to the Gregorian calendar; the documentation should make it clear what the transition date is and what days don't exist in consequence.

void printf_date(DATE *input, DFORMAT format)

Wouldn't sprintf_date be more useful? You can print to stdout given sprintf, but you can't print to anything other than stdout given only printf.

        printf("%hhu-%hhu-%hu\n",input->month,input->day,input->year);

        printf("%hhu/%hhu/%hu\n",input->month,input->day,input->year);

No. Just no. ISO 8601 is the only date format that should be used unless a locale parameter is supported.


Clean way of passing parameters I have the following code:

public EmployeeProcessOutput  RetrieveEmployee(EmployeeProcessInput input)
{
    var employee = input.Employee;

    if (input.EmployeeId == null)
        employee= CreateEmployee(employee);

    return new EmployeeProcessOutput
    {
        Employee = employee,
        State = "Stored"
    };
}

private Employee CreateEmployee(employee)
{
    //Call a service to create an employee in the system using the employee info
    //such as name, address etc and will generate an id and other employee info.
    var output = Service(employee)
    var employee = output.Employee;
    return employee;
}

Is there a clean way and of passing the employee parameter to the CreateEmployee method?  I feel that this line could be cleaner:

employee = CreateEmployee(employee);

Any thoughts?

Have a look at this. I think the real question is pass by value vs pass by reference.

More info here.

Edit:
The line could be modified to following:

CreateEmployee(ref employee);

and the method name would be:

private void CreateEmployee(ref employee)


Finding number of divisors faster Here is my code:

triangle_numbers = []
number = 0
for i in range(0, 10000):
    number = number+i
    triangle_numbers.append(number)

for number in triangle_numbers:
    number_of_divisors = 1
    for i in range(1, int(number/2)+1):
        if number % i == 0:
            number_of_divisors = number_of_divisors + 1
            if number_of_divisors > 500:
                print("FOUND AT ", number)

It takes forever to return the answer. How do I make it faster? I'm a beginner, so if you could walk me through your answer that would be great!

The challenge that I am doing is Highly divisible triangular number -
Problem 12.

You are searching for a number with more than 500 divisors in the range 0 to 10000. But we are not sure whether a number less than 10000 will be the required number. So, instead of searching a number in a range, we can search for that number which satisfies the condition the in the set of positive real numbers.

num=1
tnum=0 #representing triangular number
nof=0
while nof<501:
      nof=2 #to include 1 and the number itself
      tnum+=num
      num+=1
      for i in range (2,int((tnum/2))+1):
          if tnum%i==0:
             nof+=1
      print (tnum," : ",nof) #printing the triangular number and its number of divisors
print ("Required number is ", tnum)

This code will also take a good amount of time to get you result.


A c++ classs for recording audio samples This question is a continuation of this.

Here, I modified the original code with the following changes.
1. Make a class Recorder() to store the information of audio data.

class Recorder {
    public:
        Recorder(uint32_t sample_rate, uint32_t rec_time);
        ~Recorder();
        uint32_t frame_step;
        uint32_t sample_rate;
        uint32_t step_buf_size;
        uint32_t num_sample;
        uint32_t sample_counter;
        uint32_t record_time;
        int16_t *total_buf;
        void append(int16_t *step_buf, uint32_t n);
    private:
};

Recorder::Recorder(uint32_t rate, uint32_t rec_time)
{
    sample_rate = rate;
    frame_step = sample_rate / 100;
    step_buf_size = sizeof(int16_t) * frame_step;
    num_sample = rec_time * sample_rate;
    record_time = rec_time;
    sample_counter = 0;
    total_buf = new int16_t[num_sample];
}

Recorder::~Recorder()
{
    delete[] total_buf;
}

void Recorder::append(int16_t *step_buf, uint32_t n)
{
    memcpy(&total_buf[sample_counter], step_buf, n);
    sample_counter += n;
}

2. Use the following code to save a *.wav file.

static int32_t DumpWav(char fname[], int16_t lpsSample[], uint32_t nNumSample, uint32_t nSampleRate)
{   // arrays passed to functions are converted to pointers.
    class WavFile wf;
    wf.Create(fname, 1, 16, nSampleRate);
    if (lpsSample != NULL && nNumSample > 0) {
        wf.Write((BYTE *)lpsSample, nNumSample * 2);
        wf.Flush();
    }
    return nNumSample;
}
void main(int argc, char *argv[])
{
    Recorder rec(44100, 10);
    class CWaveRecord oRecorder;

    // Here I have to use new, because It's not allow to use a variable to init array.
    // int16_t tmp_buf[sizeof(uint16_t) * rec.frame_step]; <-- this does not compile.
    int16_t *step_buf = new int16_t[sizeof(uint16_t) * rec.frame_step];

    // Do something to record audio
    oRecorder.Initialize(1, 16, rec.sample_rate, rec.step_buf_size, 300, NULL, 0); // 0.01 * 300 = 3s circular buffer
    char ch;
    while (1) {
        printf("Press any key to record , and press again to stop, 'q' to exit ...\nMaximum recording time is %d seconds.\n", rec.record_time);
        ch = _getch();
        if (ch == 'q' || ch == 'Q' || ch == 27)
            break;

        printf("Start Record ...\n");
        rec.sample_counter = 0;

        oRecorder.StartRecord();
        while (oRecorder.GetWave((unsigned char *)step_buf) == WR_ERROR_SUCCESS) {
            uint32_t n;
            n = oRecorder.GetSamplePerBuffer();
            if (rec.sample_counter < rec.num_sample) {
                //rec.append(step_buf, sizeof(uint16_t) * n); <-- This line doesn't work. Why?
                memcpy(&rec.total_buf[rec.sample_counter], step_buf, sizeof(uint16_t) * n);
                rec.sample_counter += n;
            } else {
                oRecorder.StopRecord();
                printf("Buffer is empty. Done\n");
                break;
            }

        }

        char lpszFileName[256];
        SYSTEMTIME time;
        GetLocalTime(&time);
        sprintf_s(lpszFileName, "cmd_%02d_%02d_%02d_%02d_%02d_%02d.wav", time.wMonth, time.wDay, time.wHour, time.wMinute, time.wSecond, 1);
        DumpWav(lpszFileName, rec.total_buf, rec.sample_counter, rec.sample_rate);
    }

    delete[] step_buf;
}

This block of code works on my PC, but I still have few questions.
1. Why is my Recorder::append not working?
2. I didn't use vector() to store my audio data. The reason is that I have to pass address of total_buf to memcpy() and DumpWav(). Is using vector possible here to replace array?
3. Do you see any other improvements of my code?
Thank you.

There are a lot of things here you should definitely improve on:

Where are your includes? Your first file is missing the includes for cstdint and cstring, your second file for cstdint, cstdio, whatever header WavFile belongs to, the header for CWaveRecorder, for SYSTEMTIME and so on and so forth. It's a miracle that your code even compiles successfully.
Everything from standard headers must be prefixed with std::. This applies to all the [u]int**_t types as well as to printf, memcpy, etc.
class WavFile wf; is superfluous; Wavfile wf; will do fine. This is not C.
Why do you bother with printf, _getch and the like? This is C++, and it has a standard library that offers a great range of very handy tools for such things, such as std::cout and std::cin. Don't reinvent the wheel. Again, this is not C.
Don't use NULL, use nullptr. This is not C.
Why does Recorder have a private: followed by nothing? Remove that.
Why are all of Recorder's member variables public? This violates data encapsulation. Instead, provide getters and setters for data that should be accessible to the public.
To answer the second question of yours: Yes, it is perfectly possible here to use std::vector and you should definitely opt to do so. First of all, std::vector provides a method named data() which allows access to the underlying array. Secondly, there is also std::copy, which you should prefer in almost all cases.

This answer is by far not comprehensive, but I suggest you go and rework your code, then come back for another review.

I am not going to sugarcoat it for you: Your code is horrible by C++ standards. You freely mix C legacy functions with code bearing only the slightest resemblance with what is called modern C++.

There is a middle ground between C and C++ which is called "C with classes" by most people. If you want to write code that's closer to C, you could consider sticking with that. Otherwise, I strongly recommend you to pick up a good book and learn how to write reasonably good C++ first.


Increasing the coefficients of two numbers to sum to a targeted value I've naively tried to gradually increase two values so eventually, they sum to a targeted value.

Since this code runs many times and eventually for very large values, I don't know how to optimize so that it doesn't take more than 0.5 seconds.

def coefTargetSum(R, X, Y):
    coefResult = []
    for x in range(R):
        for y in range(R):
            if x * X + y * Y == R:
                coefResult.extend([x, y])
                return coefResult
    return -1

Rearrange the equation to find one variable from another.

\$R = xX + yY\$
\$xX = R - yY\$
\$x = \frac{R - yY}{X}\$

And so, if you don't want negative values of \$x\$, then you need to limit the range to \$\lfloor \frac{R}{X} \rfloor + 1\$.

This also will return floats, which for the most part shouldn't make a difference as it's a subtype of int. However as we're limiting the results to integers then converting the number to an int could make sense.
I also wouldn't return -1, but would instead use None or an empty list. This is as -1 makes no logical sense.
And rather than extending a list with another list, just return the wanted list. Better you could return a tuple.

This allows for:

def coefTargetSum(R, X, Y):
    for y in range(R // X + 1):
        x = (R - y*Y) / X
        if x % 1 == 0:
            return int(x), y
    return None


Calculating the Collatz Conjecture Today I read this thing about the Collatz Conjecture and wanted to try and write a program that calculates all the numbers. If you have any idea how the code could be shortened, please tell me.

List<string> liste = new List<string>();
long num = 1;
        long z = num;

        while (num != 100000)
        {
            while (z != 1)
            {
                if (z % 2 == 0)
                {
                    z = z / 2;
                }
                else
                {
                    z = (z * 3) + 1;
                }
            }
            liste.Add(num + ": " + z);
            Console.WriteLine(num+": "+z);
            finalnumber = z;
            num++;
        }

            string path = @"N:\Desktop\test.txt";
            File.Delete(path);
            for (int i = 0; i < liste.Count; i++)
            {
                string appendText = ""+liste[i]+"" + Environment.NewLine;
                File.AppendAllText(path, appendText);
            }

Each time you call File.AppendAllText, you create a new files stream and close it afterwards. Therfore, you should not write the result into the file by calling File.AppendAllText n times. just use string.Join instead:

var content = string.Join(Environment.NewLine, list);
File.WriteAllText(content);

Your code seems not work correctly, because if z == 1 is reached (which is given as initial state), the inner while loop is not entered anymore. I suppose there is a z = num; missing at the end of the outer while loop.

And in the very unlikely event, that you find a start number where the collatz conjecture does not ends up with 1, your program remains in an endless loop and you will never find out which number it was ;).


Parsing a string to extract values I am writing some C# that will be running on Linux and will extract values from a kernel generated system file that represents readings from a sensor.

The file contains two lines of text, and I have a method which will extract two values from the file.

The file looks like this:

$ cat /sys/bus/w1/devices/28-00000*/w1_slave
c3 01 4b 46 7f ff 0d 10 2f : crc=2f YES
c3 01 4b 46 7f ff 0d 10 2f t=28187

The method only cares about the crc=2f and YES (can also be NO) fields. The method returns a Nullable<SensorResult> type to indicate the success of parsing the fields:

If parsing could not happen at all because the passed parameter (a string) was invalid then a null will be returned.
If parsing was successful but the CRC was invalid (set to NO) then return a SensorResult and set appropriate fields to indicate that the CRC value is invalid.
If parsing was successful then return a SensorResult and set fields to indicate that the CRC value is valid.
Set the CrcValue field in SensorResult to the value extracted from the string. (If the YES/NO field is set to NO then getting the CRC value is still required.)

Because I'm parsing the string and extracting fields from specific positions, I've made a couple of enums to store these positions instead of relying on magic numbers.

Can the code be improved? If so, how? Are there any best practices I'm not following?

Parser:

    // <summary>
    // Parses the given line from the sensor file and determines if the CRC value is valid.
    // </summary>
    // <param name="sensorFileLine">The sensor file line.</param>
    // <returns>A <see cref="Nullable<SensorCrcValue>" /> that is used to indicate whether parsing the sensor data was successful.</returns>
    public static SensorCrcValue? TryParseCrcValue(string sensorFileLine)
    {
        if (string.IsNullOrWhiteSpace(sensorFileLine))
        {
            return null;
        }

        string[] initialSplitString = sensorFileLine.Split(' ');
        if (initialSplitString.Count() != (int)ParserFieldCount.CrcLineFieldCount)
        {
            return null;
        }

        string crcValueField = initialSplitString[(int)ParserFieldPosition.CrcValue].Split('=')[1];
        string crcValidField = initialSplitString[(int)ParserFieldPosition.CrcIsValid];

        SensorCrcValue sensorCrcValue;

        sensorCrcValue.CrcValue = Convert.ToByte(crcValueField);
        sensorCrcValue.IsCrcValid = false;

        if (crcValidField.Equals("YES"))
        {
            sensorCrcValue.IsCrcValid = true;
        }
        else if (crcValueField.Equals("NO"))
        {
            sensorCrcValue.IsCrcValid = false;
        }

        return sensorCrcValue;
    }

SensorResult struct:

public struct SensorCrcValue
{
    public bool IsCrcValid;
    public byte CrcValue;
}

public static SensorCrcValue? TryParseCrcValue(string sensorFileLine)

A common design pattern for Try[Action] methods is to return a boolean value to indicate if the action were successful or not and let the result be passed back to the caller through a by reference argument.
public static bool TryParseCrcValue(string sensorFileLine, out SensorCrcValue result)

SensorCrcValue sensorCrcValue;

sensorCrcValue.CrcValue = Convert.ToByte(crcValueField);
sensorCrcValue.IsCrcValid = false;

if (crcValidField.Equals("YES"))
{
    sensorCrcValue.IsCrcValid = true;
}
else if (crcValueField.Equals("NO"))
{
    sensorCrcValue.IsCrcValid = false;
}

return sensorCrcValue;

The last part of your code can be shortened since IsCrcValid is not a nullable boolean.
return new SensorCrcValue
{
    CrcValue = Convert.ToByte(crcValueField),
    IsCrcValid = crcValidField.Equals("YES")
};


Dijkstra's algorithm in JavaScript I'm trying to implement Dijkstra's algorithm to find the shortest path. This is from a challenge on CodeWars.

In this scenario there is a map:

[
  [1,2,3],
  [4,8,2],
  [1,5,3],
]

We start at the position 0, 0 and we can only move right or down. Our goal is to reach the position x, y passed to the function and get the sum of the shortest path. In this case the result would be 1+2+3+2+3 = 11 (for x and y pointing to the end of the square.

I implemented this code as an attempt to solve the challenge, but it times out. (It is safe to run, the part that timeout is commented).

const minPath = (grid, x, y) => {
  const maxWidth = x;
  const maxHeight = y;

  let next = [{ x: 0, y: 0, weight: grid[0][0] }];
  let arr = next;

  do {
    arr = next;
    next = [];

    for (let i = 0; i < arr.length; ++i) {
      let node = arr[i];

      if (node.x < maxWidth) {
        next.push({
          x: node.x + 1,
          y: node.y,
          weight: node.weight + grid[node.y][node.x + 1]
        });
      }

      if (node.y < maxHeight) {
        next.push({
          x: node.x,
          y: node.y + 1,
          weight: node.weight + grid[node.y + 1][node.x]
        });
      }
    }
  } while (next.length);

  return Math.min(...arr.map(o => o.weight));
};

const smallSquare = [
  [1,2,3],
  [4,8,2],
  [1,5,3],
];

console.time('small');
console.log(minPath(smallSquare, smallSquare.length - 1, smallSquare.length - 1));
console.timeEnd('small');

// just an example, values can be generated at random
const bigSquare = [[29,24,84,67,8,9,52,47,68,58,33,58,69,80,26],[95,98,94,47,20,70,46,87,80,82,96,28,4,52,10],[9,70,31,22,87,71,46,33,79,28,26,56,26,7,73],[35,2,88,70,20,41,39,85,35,35,19,1,41,85,63],[59,87,27,33,60,65,12,5,17,60,10,26,11,10,8],[6,15,49,32,54,39,93,28,32,32,51,52,13,92,44],[6,58,26,88,78,73,71,60,77,20,49,43,35,27,38],[59,73,86,52,27,85,74,67,85,72,92,55,31,76,43],[25,60,14,92,49,23,51,93,8,21,94,35,63,33,33],[34,33,18,99,67,38,36,80,5,6,82,87,33,97,3],[54,88,53,82,31,36,69,83,73,92,89,0,19,48,12],[6,89,54,88,35,13,1,33,38,31,59,93,29,72,55],[3,94,94,6,41,19,19,4,31,71,0,64,76,12,85],[96,20,58,69,65,79,40,25,58,52,79,17,97,32,42],[12,86,40,49,63,98,65,8,14,90,15,8,53,57,65]];

// This will break the page if run here
// console.time('bigSquare');
// console.log(minPath(bigSquare, bigSquare.length - 1, bigSquare.length - 1));
// console.timeEnd('bigSquare');

It seems to work pretty well, however, my solution is timing out all the time (12s+).

The first big test passes the position 29,29 (see grid here)

I wonder if I'm implementing it right. Is there something wrong? Is there a way to improve performance so it can work for really big maps?

It would help if you format your solution so that it can be copy and pasted into demonstrable code and if you provide a case where it times out.

In general if you're trying to find the shortest path (for example in a GPS) you would prune paths as you go, i.e. if you are trying to find the shortest route from A to E, you might calculate A-B-D and A-C-D, if A-B-D is shorter then you would prune A-B-D from the set of paths under consideration and not bother to calculate A-C-D-E.

That said I would just iterate through each cell calculating the cheapest way there (either from above or the left):

const minPath = (grid, x, y) => {

  function makeArray(width, height) {
    let outputArray = new Array(height);
    let row         = new Array(width);
    for(let iy = 0; iy < height; iy++) {
        outputArray[iy] = row.slice();
    }
    return outputArray;
  }

  function initArrayBorders(outputArray, grid, width, height)  {
    outputArray[0][0] = grid[0][0];
    for (let ix = 1; ix < width; ix++) {
      outputArray[ix][0] = outputArray[ix-1][0] + grid[ix][0];
    }
    for (let iy = 1; iy < height; iy++) {
      outputArray[0][iy] = outputArray[0][iy-1] + grid[0][iy];
    }
  }

  function fillArray(outputArray, grid, width, height) {
    for (let ix = 1; ix < width; ix++) {
      for (let iy = 1; iy < height; iy++) {
        let minWeight = Math.min(outputArray[ix-1][iy],
                                 outputArray[ix][iy-1]);
        outputArray[ix][iy] = minWeight + grid[ix][iy];
      }
    }
  }

  let width = x + 1, height = y + 1;
  let outputArray = makeArray(width, height);
  initArrayBorders(outputArray, grid, width, height);
  fillArray(outputArray, grid, width, height)
  console.table(outputArray);

  return outputArray[x, y];
};

console.clear();
console.log( minPath( [
  [1,2,3],
  [4,8,2],
  [1,5,3],
], 2, 2) );

I'm sure Google would also provide some other solutions.


Generic WebRequest Method for .PCL I have created this method to do all my WebRequests.

Generally my question is, if this could be improved in any way.
As a side question, I would like to know if it be better to create methods for each type (PUT, POST, GET, UPDATE, DELETE) of a request separately?

    /// <summary>
    /// Test-Method
    /// </summary>
    /// <param name="method">Json Content String</param>
    /// <param name="postData"></param>
    public static T CreateRequest<T>(string url, ICredentials cred, string method, string postData = null) where T : class
    {
        string responseJson = string.Empty;
        try
        {
            //Do request:
            HttpWebRequest request = WebRequest.Create(url) as HttpWebRequest;
            request.Method = method.ToUpper();//Just in case ToUpper();
            request.ContentType = "application/json";

            if ((method == "PUT" || method == "POST") && postData != null)
            {
                using (var streamWriter = new StreamWriter(request.GetRequestStream()))
                {
                    streamWriter.Write(postData);
                    streamWriter.Flush();
                }
            }

            var httpResponse = (HttpWebResponse)request.GetResponse();
            using (StreamReader reader = new StreamReader(httpResponse.GetResponseStream()))
            {
                responseJson = reader.ReadToEnd();
            }
        }
        catch (Exception ex)
        {
            Debug.Fail($"WebRequest failed: {ex.Message}");
            return null;
        }

        try
        {
            return JsonConvert.DeserializeObject<T>(responseJson);
        }
        catch (Exception ex)
        {
            Debug.Fail($"Error parsing JSON: {ex.Message}");
            return null;
        }
    }

Note:

credentials excluded for this purpose
don't focus on exceptionhandling- I left that out too

Thing that makes me more perplex is error-handling.

First of all you're catching all exceptions, it may hide subtle bugs unrelated to web request itself (for example wrong parameters you supply in your own code, StackoverflowException, OutOfMemoryException and so on).
You're swallowing exceptions, you just log them and return null (which is little bit counter-sense because it nullify any benefit of exceptions itself).
You do not give any chance to caller to handle exceptions (you're not doing anything useful, they may do), for example retry after a short amount of time (in case network error is transitory) or even to have any meaningful information about error.

IMO if you're writing library reusable code you shouldn't, it may be acceptable if this is an helper method to avoid repetitive code (but in this case some decent error handling is mandatory). Take, at least, a look at System.Net.WebException: The remote name could not be resolved.

After that, starting from top, I have some perplexity about method argument. It's a string and it has two drawbacks:

User may pass any unknown method and you won't know. Server may respond with an error 501 (according to RFC 2616 section 5.1.1, superseded by RFC 5789) but you will even get 400, 404 or probably 405 out there in the big real world...
User has always to type an error-prone string, no compile-time checks: errors will be detected at run-time (what if she types OPTONS instead of OPTIONS?)

Moreover you're handling strings in the wrong way:

You have method.ToUpper() just in case but there should not be a just in case in production code! Throw an error if you want user to use uppercase text or smoothly handle case errors. According to RFC 2616 (again in section 5.1.1) HTTP method is case sensitive (even if some servers don't care).
If a Turkish user enters options your code will fail because ToUpper() (again it's culture aware) will convert it to OPTİONS (note dotted uppercase İ instead of I).
You're comparing strings with == and it's current culture aware (same as above, it's not safe) and it's not case-insensitive (then what's the point of previous ToUpper()?)

What I'd do? Simply avoid strings in favor of an enum:

public enum HttpMethod
{
    Get,
    Post,
    Put,
}

Then you can convert that to string:

request.Method = HttpMethodToString(method);
if ((method == HttpMethod.Put || method == HttpMethod.Post) && postData != null)

Where HttpMethodToString() may (unless you want to use different names and enum items decorated with attributes) simply be:

static string HttpMethodToString(HttpMethod method)
{
    return method.ToString().ToUpperInvariant();
}

Even better: use already existing System.Web.Http.HttpMethod class and directly use it as string:

request.Method = method.ToString();
if ((method == HttpMethod.Put || method == HttpMethod.Post) && postData != null)

Now let's go to request itself.

HttpWebResponse implements IDisposable then it must be properly disposed, enclose it inside an using statement.

You're assuming that HTTP response is encoded as UTF-8 (StreamReader default) but it's not always true (I don't see anywhere code to add Accept-Charset HTTP header) then your code will fail if server will respond with any other encoding but UTF-8 or - and you're lucky with ISO 8859-1).

Read HttpWebResponse.CharacterSet, create the right Encoding with Encoding.GetEncoding() and give it to StreamReader constructor.

Your function is now doing three things:

Prepares the request.
Gets the response.
Parses response.

It is doing those things inside just one function called CreateRequest, little bit too much (IMO) and with a misleading name! I'd split this function into two/three smaller functions:

public static T ReadJsonFrom<T>(string url, HttpMethod method, string payload) {
    var request = CreateRequest(url, method, payload);
    var response = ReadResponseAsString(request);

    return JsonConvert.DeserializeObject<T>(response);
}

To fill those function is a trivial exercise. Now to understand how it works you need to read just three lines of code and you can put your error-handling code in one specific point: you may, for example, apply a retry pattern to read the response in ReadResponseAsString() but CreateRequest() may fail immediately.


CodeChef Matrix Rotation I am new to C# and have tried to solve a problem statement from CodeChef:

Problem statement

  You are given an array A of N integers. You are to fulfill M queries.
  Each query has one of the following three types:

  C d : Rotate the array A clockwise by d units.
  A d : Rotate the array A anticlockwise by d units.
  R d : Query for the value of the element, currently being the d-th in the array A.

  Input

  The first line contains two numbers - N and M respectively.

  The next line contains N space separated Integers, denoting the array
  A.

  Each of the following M lines contains a query in the one of the forms
  described above.

  Output

  For each query of type R output the answer on a separate line.

  Constraints

  \$1 \le N \le 100000\$
  \$1 \le M \le 100000\$
  \$1 \le d \le N\$, in all the queries
  \$1 \le \$ elements of A \$ \le 1000000\$

  The array A and the queries of the type R are 1-based.

  Example

  Input:

5 5
5 4 3 3 9
R 1
C 4
R 5
A 3
R 2

  Output:

5
3
3

My Code:

using System;
using System.Collections;
using System.Text;

namespace RotationSeptChallenge
{

class Program
{
    public static void Main(string[] args)
    {

        string nm = Console.ReadLine();
        string n = nm.Split(' ')[0];
        string m = nm.Split(' ')[1];
        int loopvar = int.Parse(m);
        string[] arr = new string[int.Parse(n)];
        var temp = Console.ReadLine().Split(' ');
        for (int i = 0; i < temp.Length; i++)
        {
            arr[i] = temp[i];
        }
        for (int loop = 0; loop < loopvar; loop++)
        {
            var optionanddistance = Console.ReadLine();
            char option = char.Parse(optionanddistance.Split(' ')[0]);
            int distance = int.Parse(optionanddistance.Split(' ')[1]);

            if (option == 'C')
            {
                ArrayList tempAL = new ArrayList();
                tempAL.AddRange(arr);
                tempAL.CopyTo(distance, arr, 0, arr.Length - distance);
                tempAL.CopyTo(0, arr, arr.Length - distance, distance);
            }

            if (option == 'A')
            {
                ArrayList tempAL = new ArrayList();
                tempAL.AddRange(arr);
                tempAL.CopyTo(arr.Length - distance,arr,0,distance);
                tempAL.CopyTo(0,arr,distance,arr.Length - distance);
            }

            if (option == 'R')
            {
                Console.WriteLine(arr[distance - 1]);
            }

        }

    }
  }
}

My solution seems to be right when I tried with a few sample outputs. However, Time Limit Exceeded was the result of my Submission. The time Limit is set to 1 sec and my solution takes >1sec. What seems to be the problem? How can I optimize this code to perform better?

You don't need all that copying and rearranging, all you need is to keep a pointer to where array starts and adjust your index calculation based on that.
Suppose you have an array of integers: [0, 1, 2, 3, 4], current start index is 0. If you rotate 2 to the left, your start index becomes 3: [2, 3, 4, 0, 1]. If you rotate this to the right 4 times, your start index is changed to 2.
You can see a pattern here: moving n cells to the left decreases start index by n and moving right increases start index.

Here's a sample pseudo-code:

startIndex = 0;
foreach operation
   if operation is print
      transformedIndex = operation.index - startIndex
      if(transformedIndex < 0)
         transformedIndex += inputArray.length
      print inputArray[transformedIndex]

   else
      if operation is rotate left
         startIndex -= operation.index
      else
         startIndex += operation.index
      startIndex = startIndex mod inputArray.length
      if startIndex < 0
         startIndex += input.Length


Swap Elements in Array if first characters match but only once per first character This is my solution to CodingBat problem p150113.  My Java knowledge is from 2011 and I'd like to know if this is still the optimal way to approach such a problem. and if my code is clean and understandable.

  We'll say that 2 strings "match" if they are non-empty and their first chars are the same. Loop over and then return the given array of non-empty strings as follows: if a string matches an earlier string in the array, swap the 2 strings in the array. A particular first char can only cause 1 swap, so once a char has caused a swap, its later swaps are disabled. Using a map, this can be solved making just one pass over the array.

firstSwap(["ab", "ac"]) → ["ac", "ab"]
firstSwap(["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]) → ["ay", "by", "cy", "cx", "bx", "ax", "aaa", "azz"]
firstSwap(["ax", "bx", "ay", "by", "ai", "aj", "bx", "by"]) → ["ay", "by", "ax", "bx", "ai", "aj", "bx", "by"]

public String[] firstSwap(String[] strings) {
  HashMap<String,Integer> hashMap = new HashMap<>();
  int counter = 0;
  int index = 0;
  for (String s : strings){
    String firstChar = s.substring(0,1);
    if(hashMap.containsKey(firstChar)){
      // make the switch in the array
      if(hashMap.get(firstChar) > -1){
        index = hashMap.get(firstChar);
        String temp = strings[counter];
        strings[counter] = strings[index];
        strings[index] = temp;
        // make sure it doesn't get swapped again:
        hashMap.put(firstChar,-1);
      }
    } else {
      hashMap.put(firstChar,counter);
    }

    counter = counter + 1;
  }
  return strings;
}

Some thoughts:

Use Interfaces when the implementation type does not matter. In your code, the fact that your Map is a HashMap is irrelevant, so prefer the Map interface.

-1 is a magic number. Use a constant to document what it's doing.

Use whitespace consistently. Just like for statements, if statements should have a blank space between the if and the (. There should also be whitespace before a { and after a , for readability.

Your comments are not contributing enough to offset the visual distraction they provide.

Your map's key is a string of length 1. It should probably be a character. And you definitely shouldn't label it a character in your variable names unless it is one.

Use final on variables which will not be reassigned as a statement of intent.

A for loop would more tightly constrain your indexing variable, which you're confusingly referring to as a counter.

You can use a guard clause to handle the simple case and then continue, rather than having a large nested if statement.

You're looking up firstChar three times. I agree that containsKey is clearer to read than a null check, but there's no reason to duplicate the other call. And you can use another constant to make clear what case you're trying to handle there too.

Note that you're destructively modifying the incoming array. In toy problems that's not a big deal, but if you're writing real code this is a very bad practice. It would be preferable to make a copy of the array and modify that instead.

If you were to apply all these changes, your code might look more like:

private static final Integer ALREADY_SWAPPED = -1;
private static final Integer FIRST_OCCURRENCE = null;

public String[] firstSwap(final String[] strings) {
    final Map<Character, Integer> map = new HashMap<>();
    final String[] result = Arrays.copyOf(strings, strings.length);

    for (int i = 0; i < result.length; i++) {
        final char firstCharacter = result[i].charAt(0);
        final Integer priorIndex = map.get(firstCharacter);

        if (priorIndex == FIRST_OCCURRENCE) {
            map.put(firstCharacter, i);
            continue;
        }

        if (priorIndex == ALREADY_SWAPPED) {
            continue;
        }

        final String temp = result[i];
        result[i] = result[priorIndex];
        result[priorIndex] = temp;
        map.put(firstCharacter, ALREADY_SWAPPED);
    }

    return result;
}


Find Nth prime - Where N < 10000 public static List<Integer> storePrimes(){
        int limit = Integer.MAX_VALUE / 10;
        boolean primes[] = new boolean[limit];
        List<Integer> primeList = new ArrayList<Integer>();
        int i = 2;
        while(primeList.size() <= 10001){
            while(true){
                if(primes[i] == false){
                    primeList.add(i);
                    break;
                }
                i++;
            }

            for(int j = i; j < limit; j += i){
                primes[j] = true;
            }
            i++;
        }
        return primeList;
    }

I want to find Nth primes. I am using this function to store all N primes. Later I can easily get Nth prime from list instead of doing everytime. N here is 10000.

How could I improve this code? What is the best upperlimit of an array?

How many?

How many primes are there less than N?

The short answer is that you should have somewhere between 100,000 and 1,000,000 entries in the array.  There's a table that says that there are less than 10,000 primes before 100,000.

        int limit = Integer.MAX_VALUE / 10;

You can calculate this based on N.  So assuming you pass N as a parameter to the method:

        final int LIMIT = 2 * N * (int)Math.log(N);

Would contain the necessary number of primes consistently.  You could probably get away with a considerably smaller number than 2.  E.g. 1.1 would likely also work.

I made LIMIT final and capitalized it.  It's not going to change, so we may as well make note of that.

Match name to function

        boolean primes[] = new boolean[limit];

You call this primes, but the prime values are false.  I would change this to composites.  Then it makes more sense for false to mean that it is prime.  You may even want to call it something like compositeStatuses or factorableStatuses to make that meaning clearer.

Optimize

            for(int j = i; j < limit; j += i){

You can actually do fewer than this:

            for (int j = i * i; j < LIMIT; j += i) {

This works because the first i multiples will have already been marked false by previous primes.  For example, when i is 2, then this starts at 4.  For 3, this starts at 9.  The only multiple between 3 and 9 is 6 which was marked false when i was 2.  In general, if a multiple is less than i * i, it will have been seen previously because it must be a multiple of i and something smaller than i.  All primes smaller than i have already been found.  The i * i value is the first multiple that we've never seen previously.

I added some extra spaces for readability as well.

Readability

        while(primeList.size() <= 10001){
            while(true){
                if(primes[i] == false){
                    primeList.add(i);
                    break;
                }
                i++;
            }

            for(int j = i; j < limit; j += i){
                primes[j] = true;
            }
            i++;
        }

I would find this easier to read as

        for (int i = 2; i < LIMIT; i++) {
            if (composites[i] == false) {
                primeList.add(i);
                if (primeList.size() >= N) {
                    break;
                }

                for (int j = i * i; j < LIMIT; j += i) {
                    composites[j] = true;
                }
            }
        }

This also explicitly handles the case where you try to go past the end of the array.  And it returns just N primes.  The original code would return 10,002 primes when you only needed 10,000.

I find it easier to follow without the infinite loop.  Now we can see that we are iterating from 2 to LIMIT checking if each value is prime.  There's only one loop that changes i so it's easy to understand what happens on each iteration.