Determine the index where two lists diverge Background

A class provides an API to determine the index where two string lists diverge.

import java.util.LinkedList;

import static java.lang.System.out;

/**
 * Provides the ability to determine the index whereat two lists begin
 * to differ in content. Both this list and the list to comapre against
 * must not contain null strings.
 */
public class DivergentList extends LinkedList<String> {
  /**
   * Answers the index at which the strings within this list differ from
   * the strings in the given list.
   *
   * @param list The list to compare against.
   *
   * @return -1 if the lists have no common strings.
   */
  public int diverges( DivergentList list ) {
    int index = -1;

    if( valid( list ) && valid( this ) ) {
      while( equals( list, ++index ) );
    }

    return index;
  }

  /**
   * Answers whether the element at the given index is the same in both
   * lists. This is not null-safe.
   *
   * @param list The list to compare against this list.
   * @return true The lists have the same string at the given index.
   */
  private boolean equals( DivergentList list, int index ) {
    return (index < size()) && (index < list.size()) &&
      get( index ).equals( list.get( index ) );
  }

  /**
   * Answers whether the given element path contains at least one
   * string.
   *
   * @param list The list that must have at least one string.
   * @return true The list has at least one element.
   */
  private boolean valid( DivergentList list ) {
    return list != null && list.size() > 0;
  }

  /**
   * Test the functionality.
   */
  public static void main( String args[] ) {
    DivergentList list1 = new DivergentList();
    list1.addLast( "name" );
    list1.addLast( "first" );
    list1.addLast( "middle" );
    list1.addLast( "last" );
    list1.addLast( "maiden" );

    DivergentList list2 = new DivergentList();
    list2.addLast( "name" );
    list2.addLast( "middle" );
    list2.addLast( "last" );

    // Prints 1
    out.println( list2.diverges( list1 ) );

    list1.clear();
    list1.addLast( "name" );
    list1.addLast( "middle" );
    list1.addLast( "last" );

    list2.clear();
    list2.addLast( "name" );
    list2.addLast( "middle" );
    list2.addLast( "last" );
    list2.addLast( "maiden" );
    list2.addLast( "honorific" );

    // Prints 3
    out.println( list2.diverges( list1 ) );

    list1.clear();
    list2.clear();

    // Prints -1
    out.println( list1.diverges( list2 ) );

    list1.add( "name" );
    list2.add( "address" );

    // Prints 0
    out.println( list1.diverges( list2 ) );

    list2.addFirst( "name" );

    // Prints 1
    out.println( list1.diverges( list2 ) );
  }
}

Questions

A few questions:

How can the code be simplified (e.g., use a different structure)?
How can the code be improved (e.g., use generics; change the name, etc.)?
How would you make the code null-safe (e.g., override all add methods)?
How would you optimize the code?

Some notes:

Use ArrayList. LinkedList is not random access list. LinkedList#get(index) has O(n), ArrayList#get(index) has O(1)
The second check valid(this) is not required
Use Iterator to avoid (index < size()) && (index < list.size())
Not sure it is really necessary to define a new Class. Simple static util method can also do the job
Avoiding “!= null” statements in Java?

Example:

static int firstMismatch(List<?> original, List<?> other) {

    int index      = -1;
    Iterator<?> it = other.iterator();

    for(Object el : original){

        ++index;

        if(!(it.hasNext() && el.equals(it.next()))){
            return index;
        }
    }

    // TODO: other.size() > original.size()
    return it.hasNext() ? (index + 1) : -1;
}

Prints:

Original: [name, first, middle, last, maiden]
Other:    [name, first, middle, last, maiden]
-1
---------
Original: [name, middle, last]
Other:    [name, first, middle, last, maiden]
1
---------
Original: [name, middle, last, maiden, honorific]
Other:    [name, middle, last]
3
---------
Original: []
Other:    []
-1
---------
Original: [name]
Other:    [address]
0
---------
Original: [name]
Other:    [name, address]
1 // TODO: original has only 1 element

For completeness, another approach is to determine the list with fewer items, then iterate against the larger of the two, and exit when no more matches are found:

public int diverges( DivergentList<E> list ) {
  int index = -1;

  // Determine the larger list for iterating.
  boolean smaller = list.size() < this.size();

  Iterator<E> iFew = (smaller ? list : this).iterator();

  // Iterate over the larger list.
  for( E e : (smaller ? this : list) ) {
    // Terminate when no more items exist in the smaller list.
    if( !(iFew.hasNext() && e.equals( iFew.next() )) ) {
      break;
    }

    index++;
  }

  return index;
}

This introduces a new variable, uses a single return statement, eliminates a final return calculation, and ensures list1.diverges( list2 ) == list2.diverges( list1 ) is always true.

The revised code prints:

Original: [name, first, middle, last, maiden]
Other:    [name, first, middle, last, maiden]
4
---------
Original: [name, middle, last]
Other:    [name, first, middle, last, maiden]
0
---------
Original: [name, middle, last, maiden, honorific]
Other:    [name, middle, last]
2
---------
Original: []
Other:    []
-1
---------
Original: [name]
Other:    [address]
-1
---------
Original: [name]
Other:    [name, address]
0

In this case, the return values indicate the last common index, which allows an empty list to be differentiated from an equal list.


Circle check algorithm optimization for directed graph Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly appreciated.

More specifically, I have two questions:

My v2 method (refer to check_circle_v2) is an optimization which traverse only from in-degree zero nodes, and after DFS all in-degree zero nodes, I will check if there are still remaining nodes unvisited -- if yes, there are circle. I learned this method from some forum, but I am not sure if this algorithm truly has no bugs or truly have performance improvements comparing to straightforward dfs implementation in the code (refer to check_circle)?
If there are no in-degree zero nodes, can I make a conclusion that the graph has circle? Is that always true?

from collections import defaultdict
class Graph:
    def __init__(self):
        self.out_neighbour = defaultdict(list) # key has edge to value
        self.in_neighbour = defaultdict(list) # value has edge to key
        self.visited = set()
        self.nodes = set()
        self.being_visited = set()
    def add_edge(self, from_node, to_node):
        self.out_neighbour[from_node].append(to_node)
        self.in_neighbour[to_node].append(from_node)
        self.nodes.add(from_node)
        self.nodes.add(to_node)
    def check_circle_v2(self):
        for root in self.nodes:
            if root not in self.in_neighbour:
                if self.dfs(root):
                    return True
        if len(self.visited) < len(self.nodes):
            return True
        return False
    def check_circle(self):
        for root in self.nodes:
            if root not in self.visited:
                if self.dfs(root):
                    return True
        return False
    def dfs(self, node):
        self.being_visited.add(node)
        for n in self.out_neighbour[node]:
            if n in self.being_visited:
                return True # has circle
            elif n not in self.visited:
                if self.dfs(n):
                    return True
        self.visited.add(node)
        self.being_visited.remove(node)
        return False
if __name__ == "__main__":
    g = Graph()
    edges = [(1,2),(2,3),(3,1),(3,4)] # true
    edges = [(1, 2), (2, 3), (1, 3), (3, 4)] # false
    edges = [(4,1),(1,2),(3,2),(3,1)] # false
    for e in edges:
        g.add_edge(e[0],e[1])
    print g.check_circle()
    print g.check_circle_v2()

Avoid data duplication

You have:

a dictionary self.out_neighbour
a dictionary self.in_neighbour
a set self.nodes

all of which store essentially the same data in slightly different formats. You can avoid duplicating the input data by doing the following:

Combine out_neighbour and in_neighbour into a doubly-linked list. This would have the form:

{
  "3":  {
            "in":  [2],
            "out": [1, 4]
        },
  "4":  {
            "in":  [3]
            "out": []
        },
   ...etc
}

All nodes in the input would appear as keys in a single dictionary (eg. nodes_dict). This also means you can:

Eliminate the self.nodes list.

self.nodes is really only referred to once in your check_circle (or check_circle_v2) method, where you have:

        for root in self.nodes:

An equivalent list can be generated from the dictionary using:

        for root in self.nodes_dict.keys()

Time complexity:

Depth-first search for cycle detection in directed graphs is supposed to scale according to \$\mathcal{O}(n)\$, where n is the number of vertices. Yours scales with \$\mathcal{O}(n^2)\$, because the list self.being.visited is itself read through by if n in self.being_visited every time you visit a node.

If speed is an issue, it may be better to use a dict for self.being.visited. The code to check it is exactly the same, but works in \$\mathcal{O}(1)\$.

Your question 1:

The efficiency improvment gained by using check_circle_v2 can be no more than a constant factor of the original implementation. This is because depth-first search is still being called, which has a runtime of \$\mathcal{O}(n)\$ in this case.

Also, what this constant factor is, exactly, depends on the ratio of no-in-degree nodes to nodes having ins.

The best case is a graph of size \$n\$, with \$n - 1\$ nodes each having an edge pointing to them (the only visual example I can think of is like a chaos flag from Warhammer40K).

The worst case is the reverse of the chaos flag graph, with all arrows pointing inward. Your check_circle_v2 will call dfs on every node except the center node. So, in terms of time complexity and worst case performance, check_circle_v2 is no better than the original.

Your question 2:

The statement is true. Requiring the graph to have no in-degree nodes means that:

No. of nodes with (in > 0) \$=\$ No. of nodes

For the case of a non-cycle, one of its nodes lacks an in-pointing edge. So, by definition, for a non-cycle:

No. of nodes with (in > 0) \$=\$ No. of nodes \$- 1\$

The only way to have a non-cycle in the graph given the first requirement is to create an in-degree node for it without adding a new node. And the only way to do that is to connect the non-cycle to the existing graph, with one or more edges pointing to it from the graph. Then, the problem  must be restated in terms of the whole graph, which cannot be a non-cycle while fulfilling the first condition.

(Terminology note: It's cycle, not circle. Also, vertice is commonly used instead of node.)


Bot for Spacewar PPCG KotH I wrote a bot for a Programming Puzzles & Code Gold King of the Hill type of challenge called "Spacewar!". The challenge was written by @El'endiaStarman. The bot is called "Spy".

The controller is hosted here, so take a look for the feel. The API is a bit long, so here's a link.

The bot's logic:

  It runs away from the other bot with a 70% chance of firing a missile and hyperspaces when it's close to the sun.

It's not online yet at a seperate bot; so you can copy-paste the code here into the KotH controller's text area at the bottom to test it out.

I sorta just monkey-patched this bot together without an IDE, so the code isn't that great. Seriously, there's even an extra function I didn't use.

The code

function Spy_setup(team) {
  // Typical setup. Nothing to see here. ;)
  var botVars = {};
  botVars["color"] = team;
  return botVars;
}

function Spy_getActions(gameInfo, botVars) {
    var actions = [];
    var us, them, red = {
            rotation: gameInfo.red_rot,
            x: gameInfo.red_x,
            y: gameInfo.red_y,
            alive: gameInfo.blue_alive
        },
        blue = {
            rotation: gameInfo.blue_rot,
            x: gameInfo.blue_x,
            y: gameInfo.blue_y,
            alive: gameInfo.blue_alive
        };
    if (botVars.color == "red") {
        us = red;
        them = blue;
    } else if (botVars.color == "blue") {
        us = blue;
        them = red;
    }

    function distance(x1, y1, x2, y2) {
        return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }

    // Get our ship's position
    var rotation, x, y, opponentAlive;
    if (botVars.color == "red") {
        rotation = gameInfo.red_rot;
        x = gameInfo.red_x;
        y = gameInfo.red_y;
        opponentAlive = gameInfo.blue_alive;
    } else if (botVars.color == "blue") {
        rotation = gameInfo.blue_rot;
        x = gameInfo.blue_x;
        y = gameInfo.blue_y;
        opponentAlive = gameInfo.red_alive;
    }

    // Calculate our rotation compared to the sun in degrees
    var sunX = gameInfo.sun_x,
        sunY = gameInfo.sun_y,
        angle = Math.atan2(sunY - y, sunX - x) * 180 / Math.PI,
        rotationToSun = (rotation - angle + 360) % 360;

    // Check if we need to hyperspace to avoid the sun
    var rX = x - sunX,
        rY = y - sunY,
        distanceFromSun = Math.sqrt(rX * rX + rY * rY) - gameInfo.sun_r;
    if (distanceFromSun < 30) {
        actions.push("hyperspace");
        console.log("Command Module is Hyperspacing.")
    }
    if (gameInfo[botVars["color"] + "_alive"]) {
        var angle = Math.degrees(Math.atan2(them.y - us.y, them.x - us.x)),
            rotationToOpponent = (us.rotation - angle + 360) % 360;
        if (rotationToOpponent > 90 && rotationToOpponent < 270) {
            actions.push("turn right");
        } else {
            actions.push("turn left");
        };
        actions.push("fire engine");
        if (Math.random() > 0.3) {
            actions.push("fire missile")
        }
    }
}

Bugs

var us, them, red = {
        rotation: gameInfo.red_rot,
        x: gameInfo.red_x,
        y: gameInfo.red_y,
        alive: gameInfo.blue_alive
    },
    blue = {
        rotation: gameInfo.blue_rot,
        x: gameInfo.blue_x,
        y: gameInfo.blue_y,
        alive: gameInfo.blue_alive
    };

Red and blue are using the same alive variable.

Also...

if (distanceFromSun < 30) {
    actions.push("hyperspace");
    console.log("Command Module is Hyperspacing.")
}
if (gameInfo[botVars["color"] + "_alive"]) {

I don't think dead ships are supposed to hyperspace.

Licensing

When you use code from StackExchange, like from this answer to the PPCG challenge, you should at the very least add a comment referencing the original source.

Duplication

Without looking at the code in detail, I spot this bit of duplication:

var rotation, x, y, opponentAlive;
if (botVars.color == "red") {
    rotation = gameInfo.red_rot;
    x = gameInfo.red_x;
    y = gameInfo.red_y;
    opponentAlive = gameInfo.blue_alive;
} else if (botVars.color == "blue") {
    rotation = gameInfo.blue_rot;
    x = gameInfo.blue_x;
    y = gameInfo.blue_y;
    opponentAlive = gameInfo.red_alive;
}

if (gameInfo[botVars["color"] + "_alive"]) {

You should pick one style and stick with it. I think you could get rid of a lot of the duplication by using the second style:

var rotation, x, y, opponentAlive;
rotation = gameInfo[botVars.color + "_rot"];
x = gameInfo[botVars.color + "_x"];
y = gameInfo[botVars.color + "_y"];

Leaves us with the opponentAlive variable, though.

For that, I'd just go with a function getOppositeColor:

function getOppositeColor(ownColor){
    return ownColor === "blue" ? "red" : "blue";
}

And then we can get opponentAlive via

opponentAlive = gameInfo[getOppositeColor(botVars.color) + "_alive"];

Other weird things in your code are that you explicitly declare a distance function... and then you don't use it. You make objects for red and blue, but you don't use them and then extract values from gameInfo a second time...

You should get the variables once. Then use them. Make a single flow like that.

var actions = [];
var us, them, red = {
        rotation: gameInfo.red_rot,
        x: gameInfo.red_x,
        y: gameInfo.red_y,
        alive: gameInfo.red_alive
    },
    blue = {
        rotation: gameInfo.blue_rot,
        x: gameInfo.blue_x,
        y: gameInfo.blue_y,
        alive: gameInfo.blue_alive
    };
if (botVars.color == "red") {
    us = red;
    them = blue;
} else if (botVars.color == "blue") {
    us = blue;
    them = red;
}

This part, in that regard, is perfectly fine.

var rotation, x, y, opponentAlive;
if (botVars.color == "red") {
    rotation = gameInfo.red_rot;
    x = gameInfo.red_x;
    y = gameInfo.red_y;
    opponentAlive = gameInfo.blue_alive;
} else if (botVars.color == "blue") {
    rotation = gameInfo.blue_rot;
    x = gameInfo.blue_x;
    y = gameInfo.blue_y;
    opponentAlive = gameInfo.red_alive;
}

This entire part can go. It's not needed. You already have all of these variables as us.rotation, us.x, us.y, and them.alive.

    if (rotationToOpponent > 90 && rotationToOpponent < 270) {
        actions.push("turn right");
    } else {
        actions.push("turn left");
    };

Also, you don't need a semicolon to end this if-statement here.


Addition/Deletion records based on method argument I have one method for addition and deletion of the account records. It has method argument based on which addition or deletion happens.

Below is method

char ADD = 'Y';
char DELETE = 'N';
private void updateAccountDtls(AccountDtlsDTO accountDtlsDTO, char addOrDeleteRecord){
    if (ADD == addOrDeleteRecord) {
        //account addition related processing
    }
    else if (DELETE == addOrDeleteRecord) {
        //account deletion related processing
    }
}

which is consumed in switch like below

switch (action) {
        case SET:
            updateAccountDtls(accountDtlsDTO,ADD);
            break;
        case RESET:
             updateAccountDtls(accountDtlsDTO,DELETE);
            break;
        }

from performace perspective is this good practice to use character instaed of string for Yes/No?

Performance wise you're not going to notice the difference.

There is a far better solution available to you though. That is to have 2 separate methods altogether.

You already have a switch statement before calling the method in which you know that it will be a delete or an add. This makes it really easy to just call the right method.

Having separate methods that each do a specific thing makes the code easier to read and maintain later on.


Python caching generator Is this the correct way to cache a generator in Python, without iterating over it right away (for example using list() over it)?

@property
def results(self):
    def caching_iterator(it, r):
        for t in it:
            yield t
            r.append(t)

    if self._results:  # _results is [] initially
        return self._results
    return caching_iterator(self.run(), self._results)

This is a property of a class, as you can see. Basically, the idea is that the first time the property is accessed, a generator is returned. So the results are actually computed as the need arises. All the other subsequent times, the results are already inside a list, so they are returned straight away.

Are there simpler ways to achieve the same result? I like mine quite a bit, but I have one argument against it. The second argument of caching_iterator is a mutable type, a list. Since that object gets modified inside the function, this is potentially dangerous. However, I don't see how that could happen. The first time _results is None and caching_iterator does its job. But all the other times, the if test passes and _results is directly returned.

Memoizing a generator is a good idea to save having to rerun it. There are a few ways to do it - one is to handle it the way you're handling it, by returning the cached result if it exists, otherwise returning and caching the new result.

The first way, is to the the tee() method from itertools. Such as follows:

from itertools import tee

def run():
    for i in range(1000):
        yield i

sequence, memoized_sequence = tee(run())

This returns a 32 byte object:

<itertools.tee object at 0x23a564>
<itertools.tee object at 0x23a58c>

which you can then iterate over as you normally would:

for x in memoized_sequence:
    print x

Another way to do it, if the generator consistently returns small sets of data, is to just use list(). This is especially true if, like aforementioned, the generator returns small sets of data and that data is not dependent on an action (ie, data is static) and that data is not kept in memory for a long time (such as in a child that is killed (and its memory freed) once its served its purpose). The way to do so, is:

def run():
    for i in range(1000):
        yield i

memoized_sequence = list(run())

However, this set of 1000 integers while have a size of 4.2KB in memory. So its not ideal, nor memory efficient, but its an option.

Now, the way that you did it, as follows:

_results = []

def run():
    for i in range(1000):
        yield i

def results():
    def caching_iterator(it, r):
        for t in it:
            yield t
            r.append(t)

    if _results:  # _results is [] initially
        return _results
    return caching_iterator(run(), _results)

Would result in a 36 byte object:

<generator object caching_iterator at 0x23f97c>

I would suggest using the system provided tee function over the custom memoization technique, so your code would look like

from itertools import tee

def results():
    _, memoized_sequence = tee(self.run())
    return memoized_sequence

Doing so shaves you 4 bytes from the returned iterator object, as well as all the variable assignments and the added function and compacts your code.

EDIT

Seems that tee() does not memoize as I thought - it just returns an iterator. However, list() does so, though statically:

import random
from itertools import tee

def run():
    for i in range(5):
        x = random.randint(0, 100) * i
        print "calculating"
        yield x

_, memoized = tee(run())

for x in memoized:
    print x

l = list(run())
print l
print l

Results in:

calculating
0
calculating
92
calculating
94
calculating
165
calculating
100
calculating
calculating
calculating
calculating
calculating
[0, 43, 106, 222, 8]
[0, 43, 106, 222, 8]


Subclassed Python Counter for a more visually user-friendly __str__() method, for anagrams I wrote a Counter subclass suitable for anagrams, with a more visually user-friendly __str__() method using alphabetic ordering and Unicode superscripts(/subscripts) for letter-counts, so you can compare at-a-glance if two phrases are anagrams or not:

c1 = LetterCounter("PRESIDENTTRUMP")
print(c1)
D¹ E² I¹ M¹ N¹ P² R² S¹ T² U¹

Code below. My questions:

translating integer to superscript(/subscript) is really clunky. Anything more compact?
Counter.items() actually returns a view. It would be more elegant if it was similarly possible to define sorted_items() as a view instead of taking sorted(list(self.items()))
leave the subscript code in even though it's not currently used
applying .format() to a variable-length list of tuples is a pain, can't just use *args.

'{0[0]}{0[1]}'.format(x for x in value_count) fails with 'generator' object is not subscriptable
'{0[0]}{0[1]} '.format([x for x in value_count]) is wrong, the format is outside the list comprehension.
[ '{0[0]}{0[1]} '.format(x) for x in value_count ] won't allow us  call LetterCounter.int_to_superscript() on only the second item of each tuple.
any more elegant approaches?

in general we're supposed to override __str__() not __repr__(), but if we don't care about pickling why not just override __repr__(), then we can directly see the object just by typing its name, don't need print?
after I independently wrote this I found Printing subscript in python
it seems more friendly for general use/reposting to enter Unicode literals in source as '\u2070' rather than '⁰'

Code:

import collections

class LetterCounter(collections.Counter):

    subscript_digits   = ''.join([chr(0x2080 + d) for d in range(10)])
    superscript_digits = ''.join(['\u2070','\u00b9','\u00b2','\u00b3','\u2074','\u2075','\u2076','\u2077','\u2078','\u2079'])
    trans_to_superscript = str.maketrans("0123456789", superscript_digits)
    trans_to_subscript   = str.maketrans("0123456789", subscript_digits)

    @classmethod
    def int_to_superscript(cls, n):
        return str(n).translate(cls.trans_to_superscript)
    @classmethod
    def int_to_subscript(cls, n):
        return str(n).translate(cls.trans_to_subscript)

    def __str__(self):
        value_count = sorted(list(self.items()))
        return ' '.join( '{}{}'.format(x[0], LetterCounter.int_to_superscript(x[1])) for x in value_count )

# Test code
c1, c2 = LetterCounter("PRESIDENTTRUMP") , LetterCounter("MRPUTINSREDPET")
print(c1)
D¹ E² I¹ M¹ N¹ P² R² S¹ T² U¹

1. Review

There is no docstring. What kind of object is a LetterCounter?
The Python style guide recommends restricting lines to 79 characters. If you did this, then we wouldn't have to scroll the code horizontally to read it.
The Python style guide recommends naming constants (like superscript_digits) using ALL_CAPITALS. It's not compulsory to follow this guide but it makes it easier to collaborate with other Python programmers.
Instead of:

superscript_digits = ''.join(['\u2070','\u00b9','\u00b2','\u00b3','\u2074','\u2075','\u2076','\u2077','\u2078','\u2079'])

add an encoding declaration to the start of the source code:

# -*- coding: utf-8 -*-

and write:

SUPERSCRIPT_DIGITS = "⁰¹²³⁴⁵⁶⁷⁸⁹"

The function int_to_superscript is short, and only called once, so it would make sense to inline it at its single point of use.
There is no need for the call to list in sorted(list(self.items())): sorted accepts an iterable.
Referring to tuple elements by index, for example x[0] and x[1], makes it hard for the reader to understand what the elements are. It is clearer to use tuple unpacking to assign meaningful names to the elements. So instead of:

value_count = sorted(list(self.items()))
return ' '.join( '{}{}'.format(x[0], LetterCounter.int_to_superscript(x[1])) for x in value_count )

write something like:

return " ".join("{}{}".format(key, str(count).translate(SUPERSCRIPT_TRANS))
                for key, count in sorted(self.items())

or, if you are happy to use formatted string literals:

return " ".join(f"{key}{str(count).translate(SUPERSCRIPT_TRANS)}"
                for key, count in sorted(self.items()))

2. Revised code

# -*- coding: utf-8 -*-

from collections import Counter

# Code point mapping from digits to superscript digits.
SUPERSCRIPT_TRANS = str.maketrans("0123456789", "⁰¹²³⁴⁵⁶⁷⁸⁹")

class LetterCounter(Counter):
    """Subclass of Counter with readable string conversion using sorted
    ordering of keys and superscript digits for counts.

    >>> print(LetterCounter("HELLOWORLD"))
    D¹ E¹ H¹ L³ O² R¹ W¹

    """
    def __str__(self):
        return " ".join(f"{key}{str(count).translate(SUPERSCRIPT_TRANS)}"
                        for key, count in sorted(self.items()))

3. Answers to questions

If you want a mapping with sorted views of its keys and items, then you need the sortedcontainers package, which has the SortedItemsView that you are looking for. (The package has no SortedCounter, but it is not difficult to write one by subclassing SortedDict.)
It is rarely a good idea to leave dead code (like the subscripts in your example). The problem is that dead code does not get tested, and so as the live code changes it is easy to forget to make corresponding changes to the dead code, so that when you come to try to resurrect the dead code you find that it is broken.
The pickling protocol uses its own special methods like __getstate__, not __repr__.
There are situations in which it's useful for eval(repr(o)) to return an object similar to o, but otherwise you are free to redefine __repr__ however you like.


Basic Trigonometry written in python3 Below is the code I wrote to perform basic Trigonometry without using the math module(except for 1 place) for the purpose of teaching myself basic trig and to improve my python. I have never taken a trig class, so please consider this fact when explaining some fallacies in my trig logic, and please help me correct it.
I would like feedback on

The architecture of the code. I find my use of dictionaries handling the return of data very restrictive and would like to know how better to handle output or returning of values.
The usage of **kargs, is this proper utilization? Is there a different way to write these functions where I can input large amounts of (undermined) data?
Lines 47-64, better ways to write the block of if/elif statements for readability and functionality.

#!/usr/bin/env python3

import math

def sin(*args, **kwargs):
    degrees = kwargs.get('degrees', None)
    opposite = kwargs.get('opposite', None)
    hypotenuse = kwargs.get('hypotenuse', None)

    if degrees:
        return math.sin(math.radians(degrees))
    elif opposite and hypotenuse:
        return(opposite / hypotenuse)

def cos(*args, **kwargs):
    degrees = kwargs.get('degrees', None)
    adjacent = kwargs.get('adjacent', None)
    hypotenuse = kwargs.get('hypotenuse', None)

    if degrees:
        return math.cos(math.radians(degrees))
    elif adjacent and hypotenuse:
        return(adjacent / hypotenuse)

def tan(*args, **kwargs):
    degrees = kwargs.get('degrees', None)
    adjacent = kwargs.get('adjacent', None)
    opposite = kwargs.get('opposite', None)

    if degrees:
        return math.tan(math.radians(degrees))
    elif opposite and adjacent:
        return(opposite / adjacent)

def find_missing_side(*args, **kwargs):
    sin = kwargs.get('sin', None)
    cos = kwargs.get('cos', None)
    tan = kwargs.get('tan', None)
    opposite = kwargs.get('opposite', None)
    hypotenuse = kwargs.get('hypotenuse', None)
    adjacent = kwargs.get('adjacent', None)

    if sin and hypotenuse:
        opposite = sin * hypotenuse
        return {'opposite': opposite}
    elif sin and opposite:
        hypotenuse = opposite / sin
        return {'hypotenuse': hypotenuse}
    elif cos and adjacent:
        hypotenuse = adjacent / cos
        return {'hypotenuse': hypotenuse}
    elif cos and hypotenuse:
        adjacent = cos * hypotenuse
        return {'adjacent': adjacent}
    elif tan and opposite:
        adjacent = opposite / tan
        return {'adjacent': adjacent}
    elif tan and adjacent:
        opposite = tan * adjacent
        return {'opposite': opposite}

def pythagorean(*args, **kwargs):
    opposite = kwargs.get('opposite', None)
    hypotenuse = kwargs.get('hypotenuse', None)
    adjacent = kwargs.get('adjacent', None)

    if hypotenuse and opposite:
        adjacent = math.sqrt(hypotenuse * hypotenuse - opposite * opposite)
    elif adjacent and opposite:
        hypotenuse = math.sqrt(adjacent * adjacent + opposite * opposite)
    elif hypotenuse and adjacent:
        opposite = math.sqrt(hypotenuse * hypotenuse - adjacent * adjacent)

    return {'hypotenuse': hypotenuse, 'adjacent': adjacent,
            'opposite': opposite}

if __name__ == "__main__":
    # Testing sin, cos, tan functions.
    print(sin(degrees=35))  # Answer is .57
    print(sin(opposite=2.8, hypotenuse=4.9))

    print(cos(degrees=35))  # Answer is .82
    print(cos(adjacent=4.0, hypotenuse=4.9))

    print(tan(degrees=35))  # Answer is .70
    print(tan(opposite=2.8, adjacent=4.0))

    # Testing find_missing_side function.
    print(find_missing_side(sin=sin(degrees=35), opposite=2.8))
    print(find_missing_side(cos=cos(degrees=35), hypotenuse=4.9))
    print(find_missing_side(tan=tan(degrees=35), adjacent=4.0))

    # Testing pythagorean function.
    hypotenuse = find_missing_side(sin=sin(degrees=35), opposite=2.8)
    print(pythagorean(opposite=2.8, hypotenuse=hypotenuse['hypotenuse']))

All of your arguments accept *args but don't use it. If someone calls your functions like sin(some_angle), it's going to return None which is confusing. You can simply leave it out, **kwargs still works.

This is more a situation that calls for keyword-only arguments, because each function only has a small fixed number of possible arguments. This leads to better errors if, say, you misspell one of the argument names in a call. If you want to use keyword-only arguments without *args, you can add a single *, before the arguments, like this:
def sin(*, degrees=None, opposite=None, hypotenuse=None):
    if degrees:
       return math.sin(math.radians(degrees))
    elif opposite and hypotenuse:
       return opposite / hypotenuse

Testing for possible arguments should be done with if x is not None instead of if x: getting sin(degrees=0) is totally valid but will return None if you test for degrees instead of degrees is not None!

You're sort of overloading each function based on arguments passed. This makes the functions error-prone to use and possibly confusing. You can call sin(degrees=60, opposite=1, hypotenuse=1) and your program won't complain. You can call sin() and get None.
A possible solution would be to split the first four functions out like this:
def sin_from_degrees(degrees)
def sin_from_edges(*, opposite, hypotenuse)
def cos_from_degrees(degrees)
def cos_from_edges(*, adjacent, hypotenuse)
def tan_from_degrees(degrees)
def tan_from_edges(*, opposite, adjacent)
def opposite_from_sin(*, sin, hypotenuse)
def opposite_from_tan(*, tan, adjacent)
def adjacent_from_cos(*, cos, hypotenuse)
def adjacent_from_tan(*, tan, opposite)
def hypotenuse_from_sin(*, sin, opposite)
def hypotenuse_from_cos(*, cos, adjacent)

Note how none of the arguments are optional any more, and if you try to use a function the wrong way, Python will give you a nice error message explaining exactly what went wrong. I also made degrees a regular argument, because I felt that sin_from_degrees(degrees=degrees) would be a bit redundant and there's no confusion about which argument means what if there's only one, although I can understand wanting the API to be more consistent.

Your last two function is interesting in that it is overloaded to an extent, but not as easy to extricate as the other functions. I would use a namedtuple instead of a dictionary, and definitely signal if pythagorean is called with the wrong arguments.
from typing import NamedTuple

class Triangle(NamedTuple):
    adjacent: float
    opposite: float
    hypotenuse: float

def pythagorean(*, adjacent=None, opposite=None, hypotenuse=None):
    if hypotenuse is not None and opposite is not None and adjacent is None:
        adjacent = math.sqrt(hypotenuse * hypotenuse - opposite * opposite)
    elif adjacent is not None and opposite is not None and hypotenuse is None:
        hypotenuse = math.sqrt(adjacent * adjacent + opposite * opposite)
    elif hypotenuse is not None and adjacent is not None and opposite is None:
        opposite = math.sqrt(hypotenuse * hypotenuse - adjacent * adjacent)
    else:
        raise TypeError("pythogorean() expects exactly two arguments from 'adjacent', 'opposite', and 'hypotenuse'")
    return Triangle(adjacent, opposite, hypotenuse)

There is still a bit of duplication (if a is not None and b is not None and c is None: c = math.sqrt(a * a ± b * b) occurs three times) but I'm not sure at the moment how to cleanly refactor that, especially due to the sign change when calculating the hypotenuse. You could make it a bit shorter by using comparator chaining (a is not None is not b) but honestly I think that would be hurt readability and maintainability more than it would help.

Maybe I've gone a bit overboard with suggesting changing things you didn't ask about, but I hope that at least answers your questions!


AsyncTask which allows to handle exceptions on UI The AsyncTask available in android, gives you the result from doInBackground on the UI thread so that you can update UI according to the result, but exceptions need to be handled inside doInBackground function.

So following is my generic solution to the problem, the main objective here is to allow user to handle exceptions exactly the same way he does when working with synchronous code.

public abstract class AsyncTaskWithThrowable<Params, Progress, Result>  {

    public class ResultHolder<Result> {

        private ResultHolder(Result result) {
            _result = result;
        }

        private ResultHolder(Throwable throwable) {
            _throwable = throwable;
        }

        private Throwable _throwable = null;

        private Result _result;

        public Result getResult() throws Throwable{
            if (_throwable != null) {
                throw _throwable;
            }

            return _result;
        }
    }

    private AsyncTask<Params, Progress, ResultHolder<Result>> _asyncTask = new AsyncTask<Params, Progress, ResultHolder<Result>>() {
        @Override
        protected ResultHolder<Result> doInBackground(Params... params)  {

            try {
                return new ResultHolder<Result>(AsyncTaskWithThrowable.this.doInBackground(params));
            }
            catch (Throwable e) {
                new ResultHolder<Result>(e);
                return null;
            }
        }

        @Override
        protected void onPreExecute() {
            AsyncTaskWithThrowable.this.onPreExecute();
        }

        @Override
        protected void onPostExecute(ResultHolder<Result> result) {
            AsyncTaskWithThrowable.this.onPostExecute(result);
        }

        @Override
        protected void onProgressUpdate(Progress... values) {
            AsyncTaskWithThrowable.this.onProgressUpdate(values);
        }
    };

    public abstract Result doInBackground(Params ... params) throws Throwable;

    protected void onPreExecute() {
    }

    @SuppressWarnings({"UnusedDeclaration"})
    protected void onPostExecute(ResultHolder<Result> resultHolder) {
    }

    @SuppressWarnings({"UnusedDeclaration"})
    protected void onProgressUpdate(Progress... values) {
    }

    public final AsyncTaskWithThrowable<Params, Progress, Result> execute(Params... params) {
         _asyncTask.execute(params);
        return this;
    }
}

And this is how you use it.

new AsyncTaskWithThrowable<Boolean, Void, String>(){

    @Override
    protected String doInBackground(Boolean ...params) {
        if (!params[0]) {
            throw new InvalidParameterException();
        }
        return "result";
    }

    @Override
    protected void onPostExecute(ResultHolder<String> resultHolder) {
        try{
            String result = resultHolder.getResult();
            // Change UI
        }
        catch (InvalidParameterException e) {
            // Change UI
        }
        catch (Throwable e) {
            // I don't like this catch block, but i couldn't find a way to avoid it.
        }
    }
}.execute(false);

The problem I see with it is user is forced to handle Throwable (also doInBackground can throw anything), but I cannot use typed parameter for exception here, as Java doesn't allow to catch it.

First of all, a few notes:

ResultHolder<Result> can be a public static class.
This just feels wrong:

catch (Throwable e) {
    new ResultHolder<Result>(e);
    return null;
}

You should probably return that ResultHolder, shouldn't you?
Avoid @SuppressWarnings({"UnusedDeclaration"}). If you have a warning there, then find out why it is there and solve it. Don't mark it as ignored. Sometimes, marking warnings ignored this way is fine, I would never do it with an UnusedDeclaration warning though.

As for your question about the Throwable, you are right that it is not a good idea to use that there. You can solve this by wrapping the exception in another.

public class AsyncException extends Exception {
    public AsyncException(String message, Throwable cause) {
        super(message, cause);
    }
}

And then:

public abstract Result doInBackground(Params ... params) throws AsyncException;

public Result getResult() throws AsyncException {

private ResultHolder(AsyncException throwable) {

@Override
protected ResultHolder<Result> doInBackground(Params... params)  {
    try {
        return new ResultHolder<Result>(AsyncTaskWithThrowable.this.doInBackground(params));
    }
    catch (Exception e) {
        return new ResultHolder<Result>(new AsyncException("Error while performing doInBackground", e));
    }
}

Problem solved! Note that I changed to catching Exception instead of Throwable as Errors (throwables that are not exceptions) shouldn't really be caught, they are much more serious so they are meant to crash everything.


rename .html file from  tag with python I have many html files saved to my computer.they have same  tags like this: Rpi-Cam-Web-Interface- Page 2 - forum
and the page number changes
I want to rename file to page number
I use this code:
import re
import os
pattern=re.compile('<title>RPi Cam Web Interface - Page \d*')
for i in os.listdir():
   parser=open(i,'r',encoding='utf-8')
   m=pattern.search(parser.read())
   parser.close()
   os.rename(i,m.group()[35:]+'html')

any better way?

Spacing For reasonably professional Python code (or for any Python code you or others may have to look at later - ideally, all code you ever write), it would be a good idea to follow the standard PEP 8 style guide, to improve readability. To start with, it recommends putting spaces between arguments and operators, and using 4 spaces for indentation:
pattern = re.compile('<title>RPi Cam Web Interface - Page \d*')
for i in os.listdir():
    parser = open(i, 'r', encoding='utf-8')
    m = pattern.search(parser.read())
    parser.close()
    os.rename(i, m.group()[35:] + 'html')

Raw string It's a good idea to use raw strings when creating Python patterns so that escape sequences aren't interpreted, and instead the backslashes are treated as regular characters inside the pattern. For this particular pattern you're using, it happens to not be necessary, but if you ever had to change it and match a newline \n or a word boundary \b etc, not having used a raw string would result in the script not running as expected.
In other words, you'd want to do something like:
pattern = re.compile(r'<title>RPi Cam Web Interface - Page \d*')
#                    ^

Pattern I see 2 issues with the pattern:

The page number is optional because you're matching with \d* instead of \d+. Using \d+ to match one or more digits would make the intent of the pattern clearer. (\d* matches "zero or more digits")
You're manually extracting the page number from the match with m.group()[35:]. Use a capturing group in the pattern instead of having to manually count up indicies:

pattern = re.compile(r'<title>RPi Cam Web Interface - Page( \d+)')
#                                                         ^^^^^^
# ...
    page_number = m.group(1)


Increase efficiency for an R simulator of the Monty Hall Puzzle The Monty Hall Problem is a simple puzzle involving probability that even stumps professionals in careers dealing with some heavy-duty math.  Here's the basic problem:

Suppose you're on a game show, and you're given the choice of three doors: Behind one      door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who      knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

You can find numerous explanations of the solution here:
http://en.wikipedia.org/wiki/Monty_Hall_problem
Goal of my simulation: Prove that a switching strategy will win you the car 2/3 of the time.

I got curious and wanted to write a little function that simulates the problem many times and returns the proportion of wins if you switched and the proportion of wins if you stayed with your first choice.  The function then plots the cumulative wins.

This function takes a long time to run once I get to about 10,000 simulations.  I know I don't need this many simulations to prove this but I'd love to hear some ideas on how to make it more efficient.  Thanks for your feedback!

Monty_Hall=function(repetitions){
doors=c('A','B','C')
stay_wins=0
switch_wins=0
series=data.frame(sim_num=seq(repetitions),cum_sum_stay=replicate(repetitions,0),cum_sum_switch=replicate(repetitions,0))
for(i in seq(repetitions)){
    winning_door=sample(doors,1)
    contestant_chooses=sample(doors,1)
    if(contestant_chooses==winning_door)
        stay_wins=stay_wins+1
    else
        switch_wins=switch_wins+1
    series[i,'cum_sum_stay']=stay_wins
    series[i,'cum_sum_switch']=switch_wins
}
plot(series$sim_num,series$cum_sum_switch,col=2,ylab='Cumulative # of wins',
xlab='Simulation #',main=sprintf('%d Simulations of the Monty Hall Paradox',repetitions),type='l')
lines(series$sim_num,series$cum_sum_stay,col=4)
legend('topleft',legend=c('Cumulative wins from switching',
'Cumulative wins from staying'),col=c(2,4),lty=1)
result=list(series=series,stay_wins=stay_wins,switch_wins=switch_wins,
proportion_stay_wins=stay_wins/repetitions,
proportion_switch_wins=switch_wins/repetitions)
return(result)
}
#Theory predicts that it is to the contestant's advantage if he
#switches his choice to the other door.  This function simulates the game
#many times, and shows you the proportion of games in which staying or
#switching would win the car.  It also plots the cumulative wins for each strategy.
Monty_Hall(100)

R has vectorized operators and using those is much more efficient in this case:

Monty_Hall2 <- function(repetitions){
    doors <- c('A','B','C')
    winning_door <- sample(doors, repetitions, replace=TRUE)
    contestant_choose <- sample(doors, repetitions, replace=TRUE)
    stay_wins <- winning_door == contestant_choose
    switch_wins <- winning_door != contestant_choose
    series <- data.frame(sim_num = seq_len(repetitions),
                         cum_sum_stay = cumsum(stay_wins),
                         cum_sum_switch = cumsum(switch_wins))
    plot(series$sim_num,series$cum_sum_switch,col=2,ylab='Cumulative # of wins',
         xlab='Simulation #',main=sprintf('%d Simulations of the Monty Hall Paradox',repetitions),type='l')
    lines(series$sim_num,series$cum_sum_stay,col=4)
    legend('topleft',legend=c('Cumulative wins from switching',
                              'Cumulative wins from staying'),col=c(2,4),lty=1)
    list(series = series,
         stay_wins = series[repetitions,"cum_stay_wins"],
         switch_wins = series[repetitions,"cum_switch_wins"],
         proportion_stay_wins = series[repetitions,"cum_stay_wins"]/repetitions,
         proportion_switch_wins = series[repetitions,"cum_switch_wins"]/repetitions)
}

That is, generate all the answers and guesses, check for each one (vectorized) which (staying or switching) would be a win, and then accumulate those results. The rest is just to put the data in the same format that your function already had.

> system.time(tmp <- Monty_Hall(10000))
   user  system elapsed
   6.04    0.00    6.04
> system.time(tmp <- Monty_Hall2(10000))
   user  system elapsed
   0.01    0.02    0.03

So approximately 1/600 of the time. Or, since I didn't do proper benchmarking, say between 2 and 3 orders of magnitude quicker.


Duplication of enum across two models In my Rails app, I have two classes each with the same enum for status. Code climate is complaining about duplication.

class Enrolment < ActiveRecord::Base
  has_many :enrolment_presentations
  has_many :presentations, through: :enrolment_presentations

  enum status: {
    'Pending' => 1,
    'Suspended' => 2,
    'Cancelled' => 3,
    'Pass' => 4,
    'Fail' => 5,
    'DPR' => 6,
    'Unknown' => 7,
    'Enrolled' => 8
  }
end

class EnrolmentPresentations < ActiveRecord::Base
  belongs_to :enrolment
  belongs_to :presentation

  enum status: {
    'Pending' => 1,
    'Suspended' => 2,
    'Cancelled' => 3,
    'Pass' => 4,
    'Fail' => 5,
    'DPR' => 6,
    'Unknown' => 7,
    'Enrolled' => 8
  }
end

How would you go about removing this duplication?

Forgive my ignorance, but isn't ActiveRecord::Base#enum just a method? Therefore, to help reduce duplication (but not eliminate it), you could do something like this:

STATUS_FLAGS = {
  'Pending' => 1,
  'Suspended' => 2,
  'Cancelled' => 3,
  'Pass' => 4,
  'Fail' => 5,
  'DPR' => 6,
  'Unknown' => 7,
  'Enrolled' => 8
}

class Enrolment < ActiveRecord::Base
  has_many :enrolment_presentations
  has_many :presentations, through: :enrolment_presentations

  enum status: STATUS_FLAGS
end

class EnrolmentPresentations < ActiveRecord::Base
  belongs_to :enrolment
  belongs_to :presentation

  enum status: STATUS_FLAGS
end

This, of course, doesn't eliminate duplication. One way around that might be to use a module as a mixin (though I'm not sure how that would work with ActiveRecord) or use singular inheritance to create a class that extends ActiveRecord::Base with the enum status, and then inherit from that - though I have to admit it feels hacky extending Active Records through inheritance.

As a stylistic note, it appears that the convention for #enum is to use lowercase names rather than PascalCase.


Multiple base numbers parser This code is a Parser that parses numbers according to R5RS.

#b1001 - binary
#o2127 - octal
#h02d  - hexadecimal
#d1231 - decimal
3923 - decimal

It is working at the moment, the only problem is the parseNumberBase. I am really new to haskell, but it does not look very good to me.

How could I improve it? (readability wise)
It would also be nice to see a more "idiomatic" approach

import Data.Char (digitToInt)
import Numeric (readInt, readOct, readHex)
import Data.Maybe (listToMaybe, fromJust)

parseNumber :: Parser LispVal
parseNumber = parseNumberBase 'd'
          <|> do char '#'
                 base <- oneOf "bdoh"
                 parseNumberBase base

-- | Parses a number at a specific base
parseNumberBase :: Char -> Parser LispVal
parseNumberBase 'b' =
    do digits <- many1 (oneOf "01")
       return $ (Number . fromJust . readBinary) digits
parseNumberBase 'o' =
    do digits <- many1 octDigit
       return $ Number (fst (readOct digits !! 0))
parseNumberBase 'd' =
    do digits <- many1 digit
       return $ (Number . read) digits
parseNumberBase 'h' =
    do digits <- many1 hexDigit
       return $ Number (fst (readHex digits !! 0))
parseNumberBase _ =
    error "Wrong number base"

readBinary :: String -> Maybe Integer
readBinary =
    fmap fst . listToMaybe . readInt 2 (`elem` "01") digitToInt

do
   digits <- someParser
   return $ someFunction digits

is just

someFunction <$> someParser

We can make parseNumberBase a lot shorter with that information:

-- | Parses a number at a specific base
parseNumberBase :: Char -> Parser LispVal
parseNumberBase 'b' = Number . fromJust . readBinary <$> many1 (oneOf "01")
parseNumberBase 'o' = Number . fst . head . readOct  <$> many1 octDigit     -- see below
parseNumberBase 'd' = Number . read                  <$> many1 digit
parseNumberBase 'h' = Number . fst . head . readHex  <$> many1 hexDigit     -- see below
parseNumberBase _   = error "Wrong number base"

readFunc digits !! 0 is head (readFunc digits), so we were able to get rid of !! too.

That being said, parseNumberBase has a lot of responsibility. Split it into multiple parsers, and it's suddenly a lot easier to grasp:

parseBinary :: Parser LispVal
parseBinary = Number . fromJust . readBinary <$> many1 (oneOf "01")

parseDecimal :: Parser LispVal
parseDecimal = Number . read <$> many1 digit

parseHexadecimal :: Parser LispVal
parseHexadecimal = Number . fst . head . readHex <$> many1 hexDigit

parseOct :: Parser LispVal
parseOct = Number . fst . head . readOct  <$> many1 octDigit

We can now test all those functions in isolation. We can now write parseNumberBase as another parser:

parseNumber :: Parser LispVal
parseNumber = parseDecimal <|> char '#' *> parseNumberBase

parseNumberBase :: Parser LispVal
parseNumberBase =  char 'h' *> parseHexadecimal
               <|> char 'd' *> parseDecimal
               <|> char 'o' *> parseOct
               <|> char 'b' *> parseBinary


Efficient Strip Special Characters I have a private function in PHP that takes a given URL string and just leave the Alpha or numeric and certain punctuation left. I need the stripping of string due to having it match against ElasticSearch and ElasticSearch doesn't take it too kindly for special characters when it comes to exact match.

The following function so far is working fine.

protected function stripSpecialCharater($string)
{
    $string = iconv("Windows-1252","UTF-8",urldecode($string));
    $string = preg_replace(array('/\s{2,}/', '/[\t\n]/'), ' ', $string);
    return preg_replace('/[^a-zA-Z0-9Ã§&-©‚Âƒâ€˜\s]/', '', $string);
}

Can it be better? is there a lib that does this better? I've used Laravel Validation service where you can specify alpha_dash but this is not for validation but rather I need the left over to see if there is a match to the Database Storage for a search.

Regex101.com seems to think you can simply combine \s{2,} and [\t\n] into \s{2,}[\t\n] and it should have the same effect:

$string = preg_replace(array('/\s{2,}/', '/[\t\n]/'), ' ', $string);

into:

$string = preg_replace('/\s{2,}[\t\n]/', ' ', $string);

You should add whitespace between your binary operators in this line:

$string = iconv("Windows-1252","UTF-8",urldecode($string));

into:

$string = iconv("Windows-1252", "UTF-8", urldecode($string));

(I'm not personally familiar with iconv, so I can't give too much of a review on your usage of the function.)

Your third regex could be slimmed down from a-zA-Z into a-z with an case insensitive search.

return preg_replace('/[^a-zA-Z0-9Ã§&-©‚Âƒâ€˜\s]/', '', $string);

return preg_replace('/[^a-z0-9Ã§&-©‚Âƒâ€˜\s]/i', '', $string);

In the same way you use a preg_replace with an array, you combine the first pair, with the secondary statement into one line if you like.


node.js architecture suggestions I have a small node.js app (MY FIRST)

I have models using mongoose, controllers for each and a seperate route, I feel like this is pretty good seperation but something about the number of route files i would have to create seems not route, basically every section of the restful api would have a route, model and controller, this keeps everything nice and tidy but I had a few question or wishes for recommendations

The complete code can be found here
https://github.com/ninjatalent/starternodejs

however i will detail out one specific area i have questions below

in my app.js i have

app.use('/api/issue', issueWebsiteRouter);
app.use('/api/project', projectRouter);

This is because i can specify a router to handle /issue or /project, but this means that I will create a router for each of this.  Is this fairly common?  Good architecture?  Let me show you an example of a router

var express = require('express');

var route = function(Issue){

var issueWebsiteController = require('../controllers/issueWebsiteController')(Issue)  // putting elements in controllers to make it easier for unit testing etc, inject mongoose Issue model
var appRouter = express.Router();
appRouter.route('/')
    .post(issueWebsiteController.post)
    .get(issueWebsiteController.get);

// this is some middleware we are injecting when we are looking at an id we see if there is a book, we add it to request and next moves us to the next method
appRouter.use('/:id', function(req,res,next){
    Issue.findById(req.params.id, function(error,issue){
        if(error)
        {
            res.status(500).send(error);
        }
        else if(issue)
        {
            req.issue = issue;
            next();

        }
        else
        {
            res.status(404).send('no book found');
        }
    });
});
appRouter.route('/:id')

    .get(function(req,res){

        res.json(req.issue);// we wont get here if there is a 404 from above

    })
    .put(function(req,res){

        req.issue.url = req.body.url;
        req.issue.reporter = req.body.reporter;
        req.issue.title = req.body.title;
        req.issue.description = req.body.description;
        req.issue.browser = req.body.browser;
        req.issue.device = req.body.device;
        req.issue.save(function(error){ // on saving if error display error otherwise send back saved element
            if(error)
            {
                res.status(500).send(error);
            }
            else
            {
                res.json(req.issue);
            }
        });

    })
    .patch(function(req,res){
        if(req.body._id)
        {
            delete req.body._id;
        }
        for(var p in req.body) // for every key in req.body
        {
            req.issue[p] = req.body[p]; // we are assigning everything in req.issue to req.body
        }
        req.issue.save(function(error){ // on saving if error display error otherwise send back saved element
            if(error){
                res.status(500).send(error);
            }
            else
            {
                res.json(req.issue);
            }
        });
    })
    .delete(function(req,res){
       req.issue.remove(function(error){
           if(error)
           {
               res.status(500).send(error);
           }
           else
           {
               res.status(204).send('Removed'); // 204 means removed
           }
       }); // take whatever is found in middleware and remove it
    });
return appRouter;
};

module.exports = route;

Since the put delete etc for each of these is potentially going to be different it feels like I have to have a seperate route, again suggestions please

Your code becomes spaghetti rather easily with this approach. I suggest you move out your logic into separate modules for each route. Even cleaner, put them in a single folder so you can easily look for them. Something like this:

// app.js
var animalsModule = require('routes/animals');
var goats = require('routes/goats');

animals.route(router.route('/animals'));
goats.route(router.route('/goats'));

// animals.js
exports.route(route){
  route.get(...);
  route.post(...);
  route.put(...);
};

req.issue = issue;

I'm not sure if you should be altering objects you don't own, especially the request object. Doing this, req becomes your "global", a universally accessible but easily pollutable object. Removing this middleware might cause potential breakage in the future.

    req.issue.url = req.body.url;
    req.issue.reporter = req.body.reporter;
    req.issue.title = req.body.title;
    req.issue.description = req.body.description;
    req.issue.browser = req.body.browser;
    req.issue.device = req.body.device;

This code will break if the issue middleware is removed. If you write this way everywhere, you will get something like "assigning property to undefined" errors. Additionally, from what I can tell, this middleware will always run, regardless if you actually need issue or not.

I suggest you fetch issue only when needed, not all the time, and only in the location where its actually needed, not in the very available req object.

delete req.body._id;

There's a saying "Don't modify objects you don't own". Unless body was yours to begin with, don't be deleting properties off objects that don't come from your code. You might have unintentionally removed something that some other part of the app, a third-party module even, that needs the property.


(de)serializing c++ object almost automagically Here's one way to solve the serialization problem in c++20, using a json library:
#include <functional>

#include <unordered_map>

#include "json.hpp"

namespace nlm = nlohmann;

class properties
{
  struct property_info
  {
    std::function<void(nlm::json const&)> deserializor;
    std::function<nlm::json()> serializor;
  };

  std::unordered_map<std::string_view, property_info> reg_;

public:
  //
  nlm::json state() const;
  void state(nlm::json const&);

  //
  template <typename U, typename ...A>
  auto register_property(std::string_view const& k, U& v, A&& ...a)
  {
    static_assert(!(sizeof...(a) % 2));
    static_assert(!(std::is_const_v<U>));

    reg_.try_emplace(k,
      [&v](nlm::json const& j){v = j.get<U>();},
      [&v]{return nlm::json(v);}
    );

    if constexpr (sizeof...(a))
    {
      register_property(std::forward<A>(a)...);
    }

    return [this](auto&& ...a)
      {
        return register_property(std::forward<decltype(a)>(a)...);
      };
  }

  auto get(std::string_view const& k)
  {
    return reg_.find(k)->second.serializor();
  }

  template <typename U>
  void set(std::string_view const& k, U&& v)
  {
    reg_.find(k)->second.deserializor(std::forward<U>(v));
  }
};

nlm::json properties::state() const
{
  nlm::json r(nlm::json::object());

  for (auto i(reg_.cbegin()), cend(reg_.cend()); cend != i; i = std::next(i))
  {
    r.emplace(i->first, i->second.serializor());
  }

  return r;
}

void properties::state(nlm::json const& e)
{
  assert(e.is_object());
  auto const cend(reg_.cend());

  for (auto i(e.cbegin()), ecend(e.cend()); ecend != i; i = std::next(i))
  {
    auto& key(i.key());

    if (auto const j(std::as_const(reg_).find(key)); cend != j)
    {
      j->second.deserializor(i.value());
    }
  }
}

Example:
int main()
{
  struct S: properties
  {
    bool b{};
    int i{};

    S()
    {
      register_property("b", b)("i", i);
    }
  } s;

  s.set("b", true);
  s.set("i", 11.1);

  std::cout << s.get("b") << std::endl;
  std::cout << s.state() << std::endl;
}

2 functors for (de)serializing are generated for each registered property. If state is requested or set, these are executed accordingly. Obvious improvements are certain checks, getters/setters, instead of references. I think this is a nice quick solution for simple cases.
https://wandbox.org/permlink/J0vdLOTp5x6xvF9s

Avoid creating namespace aliases in header files
I assume that at least the declaration of class properties would be put in a header file. In that case, consider that users of that header file might not expect namespace nlm to be declared, so I recommend just writing out nlohmann fully.
Spelling
A minor issue: it is serializer, not serializor.
Function names
Avoid overloading state() to mean either setting the state or getting the state. While related, these are different operations, and it is much better to make that explicit by giving them different function names. An obvious modification is to name them get_state() and set_state(), but that sounds quite generic. I would also make it explicit that you are converting to or from JSON, so consider naming them to_json() and from_json().
Overhead
Your serialization method introduces a huge overhead. Every instance of a serializable struct now has to contain a std::unordered_map, which is filled in in the constructor. So this costs time and memory. It would be much nicer if you could build this only once per type that derives from properties. Perhaps it can be done using static variables and CRTP, something like:
template<typename T>
struct properties
{
    struct registry
    {
        // keeps the actual mapping
        ...
    };

    template <typename U>
    void set(str::string_view const& k, U&& v) {
        // forward it to the registry object, along with a pointer to the object
        auto self = static_cast<T *>(this);
        self->registry.set(self, k, v);
    }

    ...
};

struct S: properties<S>
{
    bool b{};
    int i{};

    static properties::registry reg_;

public:
    ...
};

S::properties::registry S::reg_ = {{"b", &S::b}, {"i", &S::i}};

But I struggle myself with how to create a constructor for properties::registry that would allow the above code (especially the last line) to work.
Make get() const
You should make the get() member function const, as it should not modify the state, and this will allow that functions to be used on const instances of classes that inherit from properties.
Use range-for where possible
You can simplify the code in some places by using range-for. For example, in properties::state(), where you can also combine it with structured binding:
for (auto &[name, variable]: reg_)
{
    r.emplace(name, variable.serializer());
}

It is unfortunate that the iterator of nlm::json doesn't work the same way; you can only access the value in a range-for, not the key.
Crash at runtime when accessing a non-existing property
If in main(), you call s.get("x"), the program crashes with a segmentation fault. Even if you never expect this function to be called with a user-supplied name, it still makes it hard to debug programming errors. Check the return value of calls to find() before trying to dereference the result. You could throw a std::runtime_error if find() return nulltpr, or if you don't want to use exceptions or pay for the performance cost in production builds, at least use assert() to help with debug builds.


Searching and comparing a record I am still a beginner in C++ and I am always curious about good/best coding methods.

Let's say I have a program which allows a users to edit the salary of a employee.

The system will prompt the user which to key in a employee's name first.
The system will then check whether or not the username exist.
If the username existed, the system will then allow the user to change the employee's
salary.

The salary and the name of the person is stored in a text file.

employeeInfo.txt (formatted by name and salary)

john 1000
mary 2000
bob 3000

user.h

#ifndef user_user_h
#define user_user_h
#include <iostream>

class  user  {

public:

    user(std::string userName,std::string salary);

    std::string getUserName();
    std::string getSalary();

    void setUserName(std::string userName);
    void setSalary(std::string salary);

private:
    std::string userName,salary;

};
#endif

user.cpp

#include "user.h"
#include <iostream>
#include <string>
using namespace std;

user::user(string userName,string salary)  {

    setUserName(userName);
    setSalary(salary);

};

string user::getUserName()    {
    return userName;
}
string user::getSalary()  {
    return salary;
}

void user::setUserName(std::string userName) {
    this->userName = userName;
}

void user::setSalary(std::string salary) {
    this->salary = salary;
}

main.cpp

#include "user.h"
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;

int main(){
    vector<user> userDetails;
    string line;
    string userName;
    string salary;

    ifstream readFile("employeeInfo.txt");

    while(getline(readFile,line))   {
        stringstream iss(line);
        iss >> userName >> salary;

        //consturctor
        user employeeDetails(userName,
                             salary
                             );
        userDetails.push_back(employeeDetails);

    }
    readFile.close();

    string name;
    cout << "Please enter a user name\n";
    cin >> name;

    for (int i =0; i<userDetails.size(); i++) {
        //search if there's a match
        if (userDetails[i].getUserName() == name) {
            string newSalary;

            cout << "Please enter a new salary" << endl;
            cin >> newSalary;
            userDetails[i].setSalary(newSalary);
        }
    }
    //display to see if the salary gets updated
    for (int i=0; i<userDetails.size(); i++) {
        cout << userDetails[i].getSalary << "\n";
    }
}

I am not really sure if my code (shown below) is the worst method to search for a record in a vector and match it against the input of the user.  I would like to know is there any way to improve my code.  I'd also like to gather some tips and ideas from you all to determine if this is the worst method to search for a record in a vector.

//search for existing username
for (int i =0; i<userDetails.size(); i++) {
            if (userDetails[i].getUserName() == name) {
                //do stuff
            }
        }

Your question is surprisingly hard to answer, largely because you ask one question in your words, but a different question in your code. Your written question is whether looking up a value by sequentially scanning a vector is the best or worst way to do it. And the answer to that question is nuanced. I'll talk more about this in a bit.

However your code shows a full scenario in which you read a file, look up and edit your single user, and display the full vector's contents. In this fuller context, the performance questions of the sequential scan almost definitely do not matter, as reading and displaying the whole vector will cost more time than you could save by having a smarter look-up. A more typical program might let you perform multiple edits, and then the time it took to look up each person might be more important. So that's another improvement to consider.

Scanning a Vector

Scanning a vector with a hand-rolled for loop is not generally considered the best way to do things. It's often much better to find an algorithm that does what you want, and use it. In this case we don't know anything particularly useful about the contents of your vector, so the best bet is going to be find or find_if. To use find, you'll have to overload operator== in something, and pass it around; to use find_if you can instead create a helper function or overload operator(), or in C++11 you can pass a lambda function. Let's examine the middle option:

struct user_by_name {
    user_by_name(string name) : name(name) {}
    bool operator()(user& user) { return user.getUserName() == name; }
    string name;
};

: : :

vector<user>::iterator iterFound = std::find_if(userDetails.begin(), userDetails.end(), user_by_name(name));
if (iterFound != userDetails.end())
{
    : : :
}

The nice thing about this approach is you can create ways to find users by other criteria, such as a user_by_salary, and substitute it in with almost no code change. The downside is that without making other changes, you'll never get better than "linear" performance - on average you'll always have to look through half of the items in your vector to find the one you need.

Scanning faster

If there's a natural ordering for the items in your vector, you have two main options. Both of them require implementing an operator<, and thus do change your user struct's usage paterns. And both of them scan faster by being able to skip past some items while finding the one you want.

You can keep the items in the vector, but sort them by this ordering. This allows you to use an algorithm such as lower_bound to find them in a fraction of the time.
You can store the items in a different data structure such as a std::map which makes similar use of the ordering to give you the same performance assistance that lower_bound does on the sorted vector.

Choosing between these cases depends on how the data will be used. Again, with just a single edit in your main program, this is all overkill. But if you are going to have a long-running multi-edit scenario, especially one with thousands of employees being looked up by name and updated, it might be worth examining these options.

Other options

If you were storing a realistic amount of data about each employee, had a realistic number of employees, and had a lot of tasks you wanted to perform on them, chances are you'd find storing their information in a database would make a lot more sense. Databases solve a lot of problems for you; not only do they support fast look-ups, they handle persistence of the data (loading and saving it as necessary) and, for the right scenarios, save you a lot of time and effort. Obviously for learning how to do some of the C++ programming that you show here, using a database may help you less (although learning how to use a database isn't a bad skill either).

Other comments

Finally I wanted to end this review with a list of more generic comments about your actual code. A lot of these things are details you don't need to care about yet, or that may have occurred just in trying to post your code here, but they may help you form better habits as you advance your C++ programming skills.

using namespace std is frowned upon. It's utter anathema in a header file (which you didn't do), but it's also a risk in your cpp file. You're better off either adding the std:: prefixes, or adding using std::string; using std::vector; etc. However it's unlikely to matter in code like you show here.
Your use of whitespace is inconsistent. You don't always put spaces after commas, and sometimes use newlines instead. In some places you use more blank lines that I would consider helpful. Also not going to really matter in code this short.
Your property accessors (getUserName, getSalary) should be const as they should not visibly modify the object, and probably should return a const string& instead of a mutable copy.
Your header should include <string> instead of <iostream>, and user.cpp can similarly drop its incldue of <iostream>; you don't appear to use anything from iostream in there. Your main.cpp similarly has a lot of unused includes, but I would expect it's more of a testing file so won't harp on it.
Your search loop will find multiple matches. If you have multiple employees named bruce, your code will stop at each of them and ask for a new salary. If this is not intentional, you can use break; to avoid this. Note that most of my commentary above assumes you will want to only update a single employee at a time.
If there's no match, the program directly displays the output without any explanatory messages. That seems a little surprising to me, but perhaps it's intentional.

There's not a lot of self-documentation in your code. You'll note the last two bullets I talk about what's intentional, and in particular that I'm uncertain what you meant for your code to do. Finding the right balance between variable names, function names, and comments will help resolve that in the future. This can start as simply as adding the description you gave in your post as a comment in your main.cpp.

But all that said, I think you're starting off on the right foot. You show some solid understanding, and you also show interest in refining your skills. Congratulations on a good first post here!


Simple OOP currency converter I am learning about OOP so it would be great if you can give me feedback on how to improve my code and OOP design.

This is a currency converter. Firstly, it will call a method to add 2 currencies and commission information and then it converts to another currency whose input is source currency and amount:

import pytest

class Bank:

    def addRate(self,first, second, rate):
        self.first_currency = first
        self.second_currency = second
        self.rate = rate

    def addCommission(self,commision):
        self.commission = commision

    def convert(self, currency, amount):
        if currency == self.first_currency:
            return (amount / self.rate) * (1-self.commission)
        else:
            return (amount * self.rate) * (1-self.commission)

@pytest.fixture()
def bank():
    return Bank()

def test_Bank_addRate(bank):

    bank.addRate("USD","GBP",2)
    assert bank.first_currency == "USD"
    assert bank.second_currency == "GBP"
    assert bank.rate == 2

def test_Bank_addCommision(bank):
    bank.addCommission(0.015)
    assert bank.commission == 0.015

def test_Bank_convert(bank):
    bank.addRate("USD", "GBP", 2)
    bank.addCommission(0.015)
    assert bank.convert("USD", 100) == 49.25

First: welcome to CodeReview! I hope that you get good feedback.

About your code. Your usage of Python is not terrible; most of your problems are conceptual, about the decisions you've made about your class. Looking at the method signatures from the outside, one would guess that addRate() can be called multiple times per single Bank instance, and that convert would then allow for any currency to be converted. That isn't the case; instead, your "Bank" class is actually closer to an "ExchangeRate" class.

There are two ways to go, here. Either make your class an ExchangeRate, in which case

you need to rename the class
convert, rather than accepting the name of a currency, should perhaps accept a forward boolean. Or, if you want to keep passing the name of a currency, it's important to make the argument name more clear, i.e. dest_currency.
Rename your addCommission to setCommission. "add" implies having more than one.
Rename your addRate to setRate. "add" implies having more than one.

Or, keep a "Bank" class, in which case:

you need to change the way that you store your exchange rates, probably to a dictionary-based system instead of a single float member
convert would accept both a source and destination currency
addRate's signature would stay the same, but its contents would change to use your dict.


Session expiration handler using PHP and jQuery At this point i am interested to see other techniques on handling session timeouts.

What are some good improvements on this script to detect when a session is no longer valid?

Important definitions:

  session.gc_maxlifetime - (default 1440 seconds) defines how long an
  unused PHP session will be kept alive. For example: A user logs in,
  browses through your application or web site, for hours, for days. No
  problem. As long as the time between his clicks never exceed 1440
  seconds. It's a timeout value.

  session.cookie_lifetime - *This value (default 0, which means until the browser's next restart) defines how long (in seconds) a session
  cookie will live. Sounds similar to session.gc_maxlifetime, but
  it's a completely different approach. This value indirectly defines
  the "absolute" maximum lifetime of a session, whether the user is
  active or not. If this value is set to 1*60*60, every session ends after an
  hour.*

Problems to address:

Session timeout
Cookie timeout
Browser deleted cookies / cleared history

SESSION_handler.php

<?php
class SESSION_handler{
public static $gc_maxlifetime;
public static $cookie_lifetime;
function __construct(){
    self::$gc_maxlifetime = ini_get('session.gc_maxlifetime');
    self::$cookie_lifetime = ini_get('session.cookie_lifetime');
    if(session_status() == PHP_SESSION_NONE) {
        session_start();
    }
}
public function get($session_key){
    if(session_status() == PHP_SESSION_NONE) {
        if(!empty($_SESSION[$session_key])){
            $_SESSION['time_at_last_session'] = time();
            return $_SESSION[$session_key];
        }
    }
    return undefined;
}
public function set($session_key, $session_value){
    if(session_status() == PHP_SESSION_NONE) {
        $_SESSION[$session_key] = $session_value;
        $_SESSION['time_at_last_session'] = time();
        return $_SESSION[$session_key];
    }
    return undefined;
}
public function session_expired(){
    if(
        time() - ((!empty($_SESSION['time_at_last_session']))? $_SESSION['time_at_last_session'] : 0) >= self::$gc_maxlifetime ||
        session_status() == PHP_SESSION_NONE ||
        !isset($_COOKIE[session_name()])
        ){
        return true;
    }
    return false;
}
}
?>

is_session_expired.php

<?php
    $SESSION = new SESSION_handler();
    if($SESSION->session_expired()){
        echo "true";
    }else{
        echo "false";
    }
?>

AJAX

<script type="text/javascript">
    $(document).ready(function(){
        (function(){
            tmp_ = arguments.callee;
            window.setTimeout(function(){
                $.ajax({
                    url:'/php/is_session_expired.php',
                    success: function(session_expired){
                        if(session_expired == "true"){
                            alert("session has expired");
                        }else{
                            console.log('session has not expired');
                        }
                    }
                });
            });
        })();
    })
</script>

I don't believe the code works as expected.

One of us for sure made mistake with session_status() == PHP_SESSION_NONE. If is me, comment so I can fix the answer.

Code style

You will have better readability, if you indent everything inside the class.

You need to work on if statement in SESSION_handler::session_expired(). I can not read it at all. I personally would do it on single row, but then many people will not like it at all.

Constructor

self::$cookie_lifetime - I do not see where you need this?

You initializing the static fields every time.

self::$gc_maxlifetime = ini_get('session.gc_maxlifetime');
self::$cookie_lifetime = ini_get('session.cookie_lifetime');

I would suggest something like this:

if (self::$gc_maxlifetime = -1){
   self::$gc_maxlifetime = ini_get('session.gc_maxlifetime');
   self::$cookie_lifetime = ini_get('session.cookie_lifetime');
}

You also might decide to remove them and use ini_get directly. Or you can do static method SESSION_handler::gc_maxlifetime().

Here you create session as well:

if(session_status() == PHP_SESSION_NONE) {
    session_start();
}

Do you really need to check session_status()? My experience is you can use session_start() directly. If there is a session created, statement will do no harm.

I believe you need to initialize $_SESSION['time_at_last_session'], but only if is not set already.

Something like:

if (!isset($_SESSION['time_at_last_session']))
    $_SESSION['time_at_last_session'] = time();

SESSION_handler::get() and SESSION_handler::set()

Why you have this:

if(session_status() == PHP_SESSION_NONE) {
    // ...
}
return undefined;

You probably want to check if everything with the session is correct? to do so, use:

if(session_status() != PHP_SESSION_NONE) {
    // ...
}

You return undefined;. This is first time I see this line in PHP. Just remove the if statement. Session is already made in constructor. If is not undefined will not help at all.

Actually, in constructor, you can save the result of session_start(); into some class property and use it instead of session_status().

SESSION_handler::session_expired()

should be something like this?

public function session_expired(){
    $time = isset($_SESSION['time_at_last_session']) ?
             $_SESSION['time_at_last_session'] : 0;

    // same, but ugly:
    //$time = (int) @$_SESSION['time_at_last_session'];

    if (session_status() == PHP_SESSION_NONE)
        return true; // session problem

    if (time() - $time > self::$gc_maxlifetime)
        return true; // session expired

    // fix $_COOKIE[session_name() thing

    return false; // session is NOT expired
}

is_session_expired.php

All OK if you fix the constructor.


Authenticating an internal API with Flask I'm developing an internal API using Flask, although due to limitations with our platform the endpoints will be accessible over the public internet. It will only have a very small number of users and it's not likely that this will increase much in the future. They will query the service programatically from a backend.

As only a small number of users will be consuming the API I think it makes sense to have a single key that can be used to access it. This will keep the authentication process simple and as the API doesn't provide access to anything really sensitive I don't believe we need to go too extreme on security. I've written the following:

app_config.py

import yaml
config = yaml.safe_load(open('config.yml'))

auth.py

from functools import wraps
from flask import request
from app_config import config

def valid_auth(func):
    @wraps(func)
    def func_wrapper(*args, **kwargs):
        if 'x-api-key' not in request.headers:
            return("Credentials not present in request", 401)
        elif request.headers['x-api-key'] != config['api_key']:
            return ("Credentials not valid", 401)
        else:
            return func(*args, **kwargs)
    return func_wrapper

main.py

import api_module as api
from flask import Flask, request
from auth import valid_auth

app = Flask(__name__)

@app.route('/route1')
@valid_auth
def api_function():
    #do api stuff here

Essentially the process is:

API key is stored in config.yml on API server
(SSL) Request from backend includes the key in a header called x-api-key
A wrapper function checks that the key sent in this header matches the key in the configuration before executing any API functions. If not, the user gets an error.

Does this seem like a reasonable approach to authentication for an internal API that will be used by a small number of users and that doesn't provide access to any sensitive information? Any general suggestions for how this process might be improved?

Just because you don't have many people using this API now, this does not mean that this will always be the case.

In addition, you might want to discriminate between the users of the API for various reasons:

To know how many there actually are
To know which user/application is generating all those requests suddenly
To rate-throttle some of them if needed
To disallow access for someone who abused the API or just left the company or an obsolete application

I would at least set this up in a very barebone way to have different API keys. For now you can just hardcode them in a dictionary in the config file, but this allows you to easily extract them to a database at some future point (which may never come). You can manually add users when needed (if it is only a few), or write a page that adds a user (if the manual task becomes too much).

In your config just have something like this:

config.yml

api_keys:
    08zEk8IC0le3I0kPwSF1g4XU9R5WgbpUq2vZkZ0pkQU: User 1
    ZtRE7FXwZdtCLMfFHWPTom7_d-4XFbXEkHR5bIdG2TM: User 2
    Wg1vaDs8uqFbYtNDsJ8H3gKjl_oI0T_O6Jg8qNLWJcU: App 1
    ...

Your code needs to be only minimally changed:

auth.py

def valid_auth(func):
    @wraps(func)
    def func_wrapper(*args, **kwargs):
        if 'x-api-key' not in request.headers:
            return "Credentials not present in request", 401
        elif request.headers['x-api-key'] not in config['api_keys']:
            return "Credentials not valid", 401
        else:
            return func(*args, **kwargs)
    return func_wrapper

Note that () around tuples are not needed in return since it is an expression and not a function.

Returning a tuple of message, status code to raise in one case and the result of the function in another case can also be a potential source of bugs. If the using code expects the return value to be a single value, checking for there being two and those two being a string and an int is not very fool-proof. Even worse if the function actually also returns a string and int tuple.

Instead, raise exceptions, which you can then deal with in api_function. Use custom classes inheriting from Exception:

class NoCredentials(Exception):
    status_code = 401

class WrongCredentials(Exception):
    status_code = 401

...
if 'x-api-key' not in request.headers:
    raise NoCredentials("Credentials not present in request")

This page in the official documentation explains in more detail how to use custom exceptions correctly in flask.


Collision-checking optimizations If I'm working in a 2D environment and have hundreds of objects, brute force collision-checking would be out of the question, but would my method below work?

For example, let's say I have a

std::vector<GameObj*> objectsVector

to hold all objects and a

std::multimap<Point2D, GameObj*> objectsMap

(basically a map which takes a 2D point representing a GameObject's coordinate as a key and the object itself as a value)

to get any object associated with a point. If I want to do collision-checking for an object, I could use a function that looks like this:

void World::checkForCollisions()
{
    for (int i = 0; i < objectsVector; ++i) {
        GameObj* currObj = objectsVector[i];
        for (
                int x = (int)currObj->getX() - (int)currObject->getWidth();
                x < currObj->getX() + 2*currObj->getWidth();
                x++
            )
        {
            for (
                    int y = (int)currObj->getY() - (int)currObject->getHeight();
                    y < currObj->getY() + 2*currObj->getHeight();
                    y++
                )
            {
                pair< multimap<Point2D, GameObj*>::iterator, multimap<Point2D, GameObj*> > \
                  range = objectsMap.equal_range(Point2D(x, y));
                for (
                        multimap<Point2D, GameObj*>::iterator it=range.first;
                        it!=range.second;
                        ++it
                    )
                {
                    if (checkCollision(currObj, it->second))
                        currObj->handleCollision(it->second);
                }
            }
        }
    }
}

Is this even remotely efficient? Because it doesn't seem to be. It basically just scrolls through the vector and checks to see if it collides with nearby objects. Problem is, I have to use 2 containers AND when things move, I have to pretty much reinitialize the entire map, because the keys would be invalid! Is there any way to improve this collision-checking function, or should I scrap the whole thing altogether and use spatial hashes or a quad-tree? Any suggestions would be helpful.

If I'm understanding things correctly, (x,y) is an anchor point of your object (say, bottom left), and you're iterating over every single point that could be an anchor point for an object that it's in collision with, then checking if it's an actual anchor point of an existing object.

My suggestion (assuming that your shapes are small and circle/box-like) would be to check for exclusion rather than inclusion. If you consider that each obj has a bounding rectangle around it, then do the following checks:

curr-x > test-x + test-width
curr-x + curr-width <= test-x
curr-y > test-y + test-height
curr-y + curr-height <= test-y

If any of these are true, then you're no longer interested.

So your function then becomes something like:

typedef std::multimap<Point2D, GameObj*> ObjectSpace;
void World::checkForCollisions()
{
    for (int i = 0; i < objectsVector; ++i) {
        GameObj* currObj = objectsVector[i];
        for ( ObjectSpace::iterator ito = objectsmap.begin(); ito != objectsMap.end(); ito++ ) {
            const GameObj* test = it->second;
            if ( test == currObj ) continue;
            if ( outsideBoundingRectangle( currObj, test ) ) continue;
            if ( checkCollision( currObj, test ) ) {
                    currObj->handleCollision( test );
            }
        }
    }
}

This may be enough for a reasonable speed.


Python 3: Finding common patterns in pairs of strings I have written a piece of code that finds common patterns in two strings. These patterns have to be in the same order, so for example "I am a person" and "A person I am" would only match "person". The code is crude, all characters, including whitespace and punctuation marks, receive the same treatment. The longest patterns are matched first.

The main function then returns two lists (one per string) of tuples with two elements. The first element is 1 if a substring has been matched, else 0. The second element is the substring.

So the format of returned lists will be like this:

[(1, 'I '), (0, 'am a person\n')]
[(1, 'I '), (0, 'can see\n')]

Now to the question -- what do you think about my code? I somehow feel that it's not quite top-notch, and I'm not an experienced coder. Any suggestions on coding style or the algorithms? I hope the code is reasonably clear.

The find_raw_patterns function returns lists with alternating integers and strings, so the only thing find_common_patterns does in addition to calling find_raw_patterns, is to arrange the lists' elements in two-element-tuples.

The function longest_common_substring is copied directly from Wikibooks, and I'm not very concerned about that function.

Code:

def longest_common_substring(S1, S2):
    M = [[0]*(1+len(S2)) for i in range(1+len(S1))]
    longest, x_longest = 0, 0
    for x in range(1,1+len(S1)):
        for y in range(1,1+len(S2)):
            if S1[x-1] == S2[y-1]:
                M[x][y] = M[x-1][y-1] + 1
                if M[x][y]>longest:
                    longest = M[x][y]
                    x_longest  = x
            else:
                M[x][y] = 0
    return S1[x_longest-longest: x_longest]

def find_common_patterns(s1, s2):
    arranged1 = []
    arranged2 = []
    (ptr1, ptr2) = find_raw_patterns(s1, s2) #ptr - pattern
    for i in range(len(ptr1) - 1):
        if type(ptr1[i]) == int:
            arranged1.append((ptr1[i], ptr1[i+1]))
    for i in range(len(ptr2) - 1):
        if type(ptr2[i]) == int:
            arranged2.append((ptr2[i], ptr2[i+1]))
    return (arranged1, arranged2)

def find_raw_patterns(s1, s2): # used recursively
    one = [] # used to reassemble strings, but with patterns and integer showing whether it's been matched or not
    two = [] # same, but for the second string
    com = longest_common_substring(s1, s2)
    if len(com) < 2:
        return ((0, s1), (0, s2))
    elif len(com) >= 2:
        i1 = s1.index(com)
        i2 = s2.index(com)
        s1_bef = s1[:i1] #part of string before the matched pattern
        s1_aft = s1[i1 + len(com) : ] # -//- after matched pattern
        s2_bef = s2[:i2]
        s2_aft = s2[i2 + len(com) : ]
        if len(s1_bef) > 0 and len(s2_bef) > 0: # find patterns in first parts of strings
            res = find_raw_patterns(s1_bef, s2_bef)
            one.extend(res[0])
            two.extend(res[1])
        one.extend((1, com)) # add current pattern
        two.extend((1, com))
        if len(s1_aft) > 0 and len(s2_aft) > 0: # find patterns from second parts
            res = find_raw_patterns(s1_aft, s2_aft)
            one.extend(res[0])
            two.extend(res[1])
        return (one, two)

You can simplify the two functions quite a bit. For find_raw_patterns you can use partition instead of manually splitting the strings up, and simplify the formation of the list.

def find_raw_patterns(s1, s2): # used recursively
    if s1 == '' or s2 == '':
        return [], []
    com = longest_common_substring(s1, s2)
    if len(com) < 2:
        return ([0, s1], [0, s2])
    s1_bef, _, s1_aft = s1.partition(com)
    s2_bef, _, s2_aft = s2.partition(com)
    before = find_raw_patterns(s1_bef, s2_bef)
    after = find_raw_patterns(s1_aft, s2_aft)
    return (before[0] + [1, com] + after[0],
            before[1] + [1, com] + after[1])

For find_common_patterns, you can use list indices to get the even and odd values rather than checking the type of each value, and use zip to get a list of pair tuples.

def find_common_patterns(s1, s2):
    (ptr1, ptr2) = find_raw_patterns(s1, s2) #ptr - pattern
    return (zip(ptr1[::2], ptr1[1::2]),
            zip(ptr2[::2], ptr2[1::2]))

But I think you can also combine the two functions with a minor adjustment to put the found values into paired tuples.

def find_common_patterns(s1, s2): # used recursively
    if s1 == '' or s2 == '':
        return [], []
    com = longest_common_substring(s1, s2)
    if len(com) < 2:
        return ([(0, s1)], [(0, s2)])
    s1_bef, _, s1_aft = s1.partition(com)
    s2_bef, _, s2_aft = s2.partition(com)
    before = find_common_patterns(s1_bef, s2_bef)
    after = find_common_patterns(s1_aft, s2_aft)
    return (before[0] + [(1, com)] + after[0],
            before[1] + [(1, com)] + after[1])