Split cells vertically on comma This takes a field delimited by commas, and splits on the comma.  The newly divided information is put in another field (created at the start of the program) called lob.  Each part of the split is put in the lob field in a duplicate record of the original record from before the split.  The primary key is ID which is automatically generated.

Here is a concise example of desired behavior (many fields omitted for visual clarity):

Before running the module:

 +--------------------------------------------+
 |  ID   | App Code  |   Lines Of Business    |
 +-------+-----------+------------------------+
 |   1   |    AB23   | Value1, Value 2,Value3 |
 +------ +-----------+------------------------+
 |   2   |    XY45   |         Value 2        |
 +--------------------------------------------+

After running the module:

 +-------------------------------------------------------+
 |  ID   | App Code  |   Lines Of Business    |   lob    |
 +-------+-----------+------------------------+----------+
 |   1   |    AB23   | Value1, Value 2,Value3 |  Value1  |
 +-------+-----------+------------------------+----------+
 |   2   |    XY45   |         Value 2        |  Value 2 |
 +-------+-----------+------------------------+----------+
 |   3   |    AB23   | Value1, Value 2,Value3 |  Value 2 |
 +-------+-----------+------------------------+----------+
 |   4   |    AB23   | Value1, Value 2,Value3 |  Value3  |
 +-------------------------------------------------------+

Is there a way to accomplish this task in a more elegant or accurate way?  Efficiency is also good, but this program already runs quick enough on my data-set.

Option Explicit

Public Sub ReformatTable()

    Dim db                       As DAO.Database
    Dim rs                       As DAO.Recordset
    Dim rsADD                    As DAO.Recordset
    Dim fld                      As DAO.Field

    Dim strSQL                   As String
    Dim varData                  As Variant
    Dim i                        As Integer

    Set db = CurrentDb

    ' Add a field into the existing IIPM table called lob.
    ' Values created during the Line Of Business split will be stored here.
    Dim strDdl As String
    strDdl = "ALTER TABLE IIPM ADD COLUMN lob TEXT(255);"
    CurrentProject.Connection.Execute strDdl

    ' Select all fields that have a Line of Business and are unprocessed (lob is Null)
    strSQL = "SELECT *, lob FROM IIPM WHERE ([Lines Of Business] Is Not Null) AND ([lob] Is Null)"

    Set rsADD = db.OpenRecordset("IIPM", dbOpenDynaset, dbAppendOnly)

    Set rs = db.OpenRecordset(strSQL, dbOpenDynaset)

    With rs
        While Not .EOF
            varData = Split(rs![Lines Of Business], ",") ' Get all comma delimited fields

            'Update First Record
            .Edit
            !lob = Trim(varData(0)) ' remove spaces before writing new fields
            .Update

            ' Add records with same first field
            ' and new fields for remaining data at end of string
            For i = 1 To UBound(varData)
                rsADD.AddNew
                For Each fld In rsADD.Fields
                    If fld.Name <> "lob" And fld.Name <> "ID" Then
                        ' Copy all fields except "lob" and "ID"
                        rsADD(fld.Name) = rs(fld.Name)
                    End If
                Next fld
                ' lob is set separately, ID is set automatically
                rsADD!lob = Trim(varData(i)) ' remove spaces before writing new fields
                rsADD.Update
            Next i

            .MoveNext
        Wend

        .Close
        rsADD.Close

    End With

    Set rsADD = Nothing
    Set rs = Nothing

    ' Remove empty rows which only contain an ID.
    CurrentProject.Connection.Execute "DELETE FROM IIPM WHERE lob IS NULL AND [App Code] IS NULL AND [Lines Of Business] IS NULL;"

    db.Close
    Set db = Nothing

End Sub

I would not put the results in the same table.  I would make a new table and put the results in the new table.  The new table can use the same surrogate keys as the original.  It is a basic principle in database design that you never work on live data when doing development.  I also like inputs and outputs to be separate.  Sometimes you can damage the data subtly and if you have changed the input data rather than create a separate output table, these changes can be harder to detect and remedy.

Other than that the code looks fine.


Universal memoization decorator I've just written a simple caching / memoization python decorator. It's purpose is to cache what the function returns for all the arguments combinations it's been ever invoked with.

So, if, say, we had a function my_function(a, b=2, c=3) invoked once with my_function(1, 2, c=3), the results should be then cached whenever I call it with my_function(1, 2, 3) or my_function(1, c=3, b=2) or my_function(c=3, b=2, a=1).

Is what's below a good approach and could it be somehow improved?

import functools
import pickle

def memoize_all(func):
    """
    This is a caching decorator. It caches the function results for
    all the arguments combinations, so use it with care. It does not matter      whether the arguments
    are passed as keywords or not.
    """
    cache = {}

    @functools.wraps(func)
    def cached(*args, **kwargs):
        arg_names = func.func_code.co_varnames
        arg_dict = {}
        for i, arg in enumerate(args):
            arg_dict[arg_names[i]] = args[i]
        arg_dict.update(**kwargs)
        key = pickle.dumps(arg_dict)
        if key not in cache:
            cache[key] = func(*args, **kwargs)
        return cache[key]
    return cached

I don't know what's up with the spacing in the docstring, but fix it.

Your memoize_all doesn't work with everything:

memoize_all(int)(1)
#>>> Traceback (most recent call last):
#>>>   ...
#>>> AttributeError: type object 'int' has no attribute 'func_code'

I suppose this doesn't bother you much, but it irks me ;).

Consider

for i, arg in enumerate(args):
    arg_dict[arg_names[i]] = args[i]

There's no point doing args[i]; it's just arg. Further, one should do

for i, (name, arg) in enumerate(zip(arg_names, args)):
    arg_dict[name] = arg

But then one can just do

arg_dict = dict(zip(arg_names, args))

You could even use

arg_dict = dict(zip(arg_names, args), **kwargs)

You try and save this with

key = pickle.dumps(arg_dict)

I'm not at all fond of this method. pickle is a bit fragile and more complicated than I would expect. I would personally do something like

key = frozenset(arg_dict.items())

If you skip generating arg_dict, this is

key = frozenset(kwargs.items()) | frozenset(zip(arg_names, args))

This does prevent accepting mutable arguments, but it's normally best to enforce purity before caching arguments anyway.

You then have just

def cached(*args, **kwargs):
    arg_names = func.func_code.co_varnames
    key = frozenset(kwargs.items()) | frozenset(zip(arg_names, args))

    if key not in cache:
        cache[key] = func(*args, **kwargs)
    return cache[key]

Note that in Python 3, this would be better with a signature object:

import functools
from inspect import signature

def memoize_all(func):
    """
    This is a caching decorator. It caches the function results for
    all the arguments combinations, so use it with care. It does not
    matter whether the arguments are passed as keywords or not.
    """
    cache = {}
    func_sig = signature(func)

    @functools.wraps(func)
    def cached(*args, **kwargs):
        bound = func_sig.bind(*args, **kwargs)
        key = frozenset(bound.arguments.items())

        if key not in cache:
            cache[key] = func(*args, **kwargs)
        return cache[key]
    return cached


Use PreparedStatement to insert into H2 database This question is related to my question on Stack Overflow earlier today. After getting suggestions on using the PreparedStatement from Java I changed my code a little.

  EDIT: In my original question on Stack Overflow I attempted to process
  the query in a very messy way, see this short excerpt:

String sqlQuerry = "INSERT INTO TASKS " + "VALUES ("
        + table.getValueAt(i, 0) + ", "
        + table.getValueAt(i, 1) + ", "
        + table.getValueAt(i, 2) + ", "
        + table.getValueAt(i, 3) + ", "

  Even though this might have worked, it would have been harder to
  understand and I ran into issues when the table.getValueAt(X,Y)
  returned "null".

As I am completely new to SQL in Java I want to know if the code below is "good" or at least "okayish" and can be maintained later on. If you got any tips on how to make this cleaner, let me know.

String sqlInsert = "INSERT INTO TASKS " + "VALUES" + "(?,?,?,?,?,?,?,?,?,?,?,?,?)";

for (int i = 0; i < table.getModel().getRowCount(); i++) {

    PreparedStatement sqlState = conn.prepareStatement(sqlInsert);

    int j = 1;

    sqlState.setInt(j++, Integer.parseInt(table.getValueAt(i, 0).toString()));
    sqlState.setInt(j++, Integer.parseInt(table.getValueAt(i, 1).toString()));
    sqlState.setInt(j++, Integer.parseInt(table.getValueAt(i, 2).toString()));
    sqlState.setInt(j++, Integer.parseInt(table.getValueAt(i, 3).toString()));

    sqlState.setString(j++, table.getValueAt(i, 4).toString());
    sqlState.setString(j++, table.getValueAt(i, 5).toString());
    sqlState.setString(j++, table.getValueAt(i, 6).toString());
    sqlState.setString(j++, table.getValueAt(i, 7).toString());

    sqlState.setInt(j++, Integer.parseInt(table.getValueAt(i, 8).toString()));

    sqlState.setString(j++, table.getValueAt(i, 9).toString());
    sqlState.setString(j++, table.getValueAt(i, 10).toString());
    sqlState.setString(j++, table.getValueAt(i, 11).toString());
    sqlState.setBoolean(j++, (boolean) table.getValueAt(i, 12));

    sqlState.executeUpdate();
}

There are some things to improve in this code. Especially when it's underlined that "if it can be maintained later on".

SQL query

The columns where the data will be inserted should always be defined, for example: INSERT INTO TASK(id_task, title, creation_time... etc) VALUES(... . It's the same problem as for SELECT *, that should never be used in serious queries. That's because the table definition evolves over time; tomorrow there may be new columns added, other removed or reordered. There is absolutely no warranty that the meaning of what is behind the question marks in the example will be valid after the next feature implemented into the software.
Another reason to define them is just to help yourself: it's very difficult to remember which is the natural order of columns in the table for the thirteen question marks.

PreparedStatement

There is no need to recreate the PreparedStatement instance on each loop. Indeed, one of the reasons they are made for is the possibility to be reused. And their creation is sometimes quite costly.
The third line should come just before the for loop.

Parameter Indices

From the point of view of maintenability, calculating/incrementing the parameter index (j variable) is not safe. It's just almost like the columns ordering issue above. If j is incremented, the order of the lines with parameters setting is crucial and prone to errors. To solve, some readable (local) constants may be introduced, for example:

final int COLUMN_ID = 1;
final int COLUMN_TITLE = 2;

...
sqlState.setInt(COLUMN_ID, id);

Parameters Mapping

There is absolutely no way to know the meaning of the values that are retrieved from the table. Since it looks like a JTable object, here is a way how an explicit mapping can be created.

Define a TableModel by extending, for example, the javax.swing.table.DefaultTableModel and map the values you need with their respective getters:

class TaskTableModel extends DefaultTableModel {
    ...
    public String getTitle(int rowIndex) {
        return getValueAt(rowIndex, 2);
    }
}

When the JTable object is created, set a TaskTableModel instance on it:

JTable table = new JTable(...);
table.setModel(new TaskTableModel());

When setting the parameter values of the PreparedStatement, use the TaskTableModel instance:

TaskTableModel tableModel = (TaskTableModel) table.getModel();
...
sqlState.setInt(COLUMN_TITLE, tableModel.getTitle(i));


Is this a good algorithm for 2D collision, or will it allocate too much memory? I have a Rectangle class, of which I have 5-6 vectors for each instance. The main vectors are the center and color of the object, while the secondary vectors represent more or less the north, south, east, and west directions of the rectangle itself. These vectors are used to detect collision by "pointing" outside of the sides of the rectangle to detect collision. I may end up creating more fields of the NW, SW, NE, SE, equivalents as well, but I'd like to know if this is actually a good implementation before I do this. The only Vec2f I have allocated as a pointer is the mWidthHeight vector, which of course is just a representation of the width and the height (x = width, y = height) of the rectangle.

Will this allocate too much memory if there are thousands of these on the screen, or is this an OK (at least) implementation?

Rect.h

Note - I'm debating with the idea of making the N, S, E, W vectors pointers to memory. Is that a good idea, or no?

#pragma once

#include <QGLWidget>
#include <GL/glext.h>
#include <cmath>
#include <QDebug>
#include "Shape.h"
#include "Vec3f.h"
#include "rand.h"

const int DEFAULT_SQUARE_WIDTH = 5;
const int DEFAULT_SQUARE_HEIGHT = 5;

typedef enum {

  V2D_NORTH,
  V2D_SOUTH,
  V2D_EAST,
  V2D_WEST

} V2D_DIRECTION;

class Rectangle : public Shape
{
public:

    Rectangle(
        Vec2f center = Vec2f(),
        Vec2f widthheight = Vec2f(DEFAULT_SQUARE_WIDTH, DEFAULT_SQUARE_HEIGHT),
        float radius = 0,
        Vec3f color = Vec3f()
    );

    ~Rectangle();

    inline Vec2f* getWidthHeight() const {
        return mWidthHeight;
    }

    inline Vec2f getDirection(V2D_DIRECTION dir) const {
        switch(dir) {
        case V2D_NORTH:
            return mNorth;

        case V2D_SOUTH:
            return mSouth;

        case V2D_EAST:
            return mEast;

        case V2D_WEST:
            return mWest;

        }
    }
    virtual void Collide( Shape &s );

    virtual void Collide( Rectangle &r );

    virtual void Collide ( Circle &c );

    virtual bool Intersects( const Shape& s ) const;

    virtual bool Intersects( const Rectangle& s ) const;

    virtual bool IsAlive( void ) const;

    virtual float Mass( void ) const;

protected:

   virtual void Draw( void ) const;
   Vec2f* mWidthHeight;
   Vec3f mColor;

private:
   Vec2f mNorth;
   Vec2f mSouth;
   Vec2f mEast;
   Vec2f mWest;
   void InitDirections();

};

Your constructor arguments and defaults are unusual.
What does radius mean for a Rectangle?
Should there be an argument for initializing mass?
I suggest:

    static const Vec2f& defaultCenter();
    static const Vec2f& defaultSquareDimensions();
    static const Vec3f& defaultColor();

    Rectangle(
        const Vec2f& center = defaultCenter(),
        const Vec2f& widthheight = defaultSquareDimensions(),
        // Assuming rotation angles are supported...
        const Vec2f orientation = defaultOrientation(),
        const Vec3f& color = defaultColor()
    );

and/or maybe:

    Rectangle(
        const Vec3f& color,
        const Vec2f& center = defaultCenter(),
        const Vec2f& widthheight = defaultSquareDimensions(),
        // Assuming rotation angles are supported...
        const Vec2f orientation = defaultOrientation()
    );

    inline const Vec2f& getWidthHeight() const {
        return mWidthHeight;
    }

The static methods can return "static objects" that are constructed once each instead of always constructing new temps.

I can't tell what the return value of the following function represents.
What is the north direction vector of a rectangle?
Can you give examples for different rectangles?
Can you explain how you would use the returned vector?

    inline Vec2f getDirection(V2D_DIRECTION dir) const {
        switch(dir) {
        case V2D_NORTH:
            return mNorth;

        case V2D_SOUTH:
            return mSouth;

        case V2D_EAST:
            return mEast;

        case V2D_WEST:
            return mWest;

        }
    }

This seemed missing?

    virtual bool Intersects( const Circle& s ) const;

There should be some good reason not to make these private:

   Vec2f mCenter;

There seems to be no reason to make this a pointer.
There might be an argument for making it const.

   Vec2f mWidthHeight;
   Vec2f mOrientation;

If rectangles tend to come in a small selection of colors,
you may be better off storing an index into a central
pallette vector or possibly a pointer into a pool of shared colors.

There might be an argument for making this const if they don't change color.

   Vec3f mColor;

The following seem expensive to store and maintain and they also seem like they may be at least partly redundant? If they are redundant (derivable from a smaller set of parameters)
you should probably run benchmarks on code that stores these values
and code that calculates them on the fly as needed.

private:
   Vec2f mNorth;
   Vec2f mSouth;
   Vec2f mEast;
   Vec2f mWest;
   void InitDirections();

It may be that there is a better way to express orientation and/or these other values that is more useful in finding intersections.
It seems strange to me to be considering even more of these vectors for NW, etc. but I'm not even sure yet what they mean.

To speed up intersection, I thought you MIGHT also want to store
an additional widthheight representing the bounding box -- the smallest x/y
aligned rectangle that contains this rectangle in its current orientation.

SO MUCH depends on how your actual intersect logic uses all of these values.
Storing them all and more MIGHT be worthwhile.

CPU vs. memory trade-offs can be very tricky to predict.


Singly Linked List implementation in Python I'm new to Python and thus learning it by implementing a set of commonly used data structures. Here's my implementation of a  LinkedList.
First the Node class.

class Node:

    def __init__(self, value = None, next = None):
        self.value = value;
        self.next = next;

Here's the LinkedList,

from node import Node

class LinkedList:

    def __init__(self):
        self.head = None;
        self.size = 0;

    def insert(self, item):
        curr = Node();
        curr.value = item
        self.size += 1
        if(self.head == None):
            self.head = curr
        else:
            curr.next = self.head
            self.head = curr

    def remove(self, item):
        if(self.head == None):
             raise Exception('Removing from an empty list')
        curr = self.head
        if(curr.value == item):
            self.head = curr.next
            return
        while(curr.next.value != item):
            curr = curr.next
        if(curr.next == None):
            raise Exception('Item not present in list')
        else:
            curr.next = curr.next.next

    def print_list(self):
        curr = self.head;
        while(curr):
            print(curr.value, end=' ')
            curr = curr.next

And finally the calling client,

from linked_list import LinkedList

list = LinkedList()
list.insert(2)
list.insert(5)
list.insert(7)
list.insert(12)
list.insert(13)
list.remove(13)
list.print_list()

My primary language is Java, so I'd invite comments on how pythonic is my implementation and best practices. TIA.

For the most part it looks good, I haven't tested performance, but nothing stands out as bad. You should probably rewrite remove, so that it takes an index rather than a value. Imagine

list = LinkedList()
list.insert(2)
list.insert(2)
list.remove(2)

Your current code works great as long as there aren't duplicate values, but once there are everything gets kind of messed up.

With regards to pythonicness, the only comment I have is that if(x): is harder to type and harder to parse than if x:.


Computing resilience of the network presented as an undirected graph in Python The idea is to compute resilience of the network presented as an undirected graph in form {node: (set of its neighbors)} for each node in the graph}. The function removes nodes from the graph in the specified order one by one and calculates the size of the largest remaining connected component. The function returns a list whose k+1th entry is the size of the largest connected component after the removal of the first k nodes. The helper function bfs_visited() returns the set of nodes that are still connected to the given node.

How can I improve the implementation of the algorithm (currently it is very slow)?

def bfs_visited(graph, node):
    """undirected graph {Vertex: {neighbors}}
    Returns the set of all nodes visited by the algrorithm"""
    queue = deque()
    queue.append(node)
    visited = set([node])
    while queue:
        current_node = queue.popleft()
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

def cc_visited(graph):
    """ undirected graph {Vertex: {neighbors}}
    Returns a list of sets of connected components"""
    remaining_nodes = set(graph.keys())
    connected_components = []
    for node in remaining_nodes:
        visited = bfs_visited(graph, node)
        if visited not in connected_components:
            connected_components.append(visited)
        remaining_nodes = remaining_nodes - visited
        #print(node, remaining_nodes)
    return connected_components

def largest_cc_size(ugraph):
    """returns the size (an integer) of the largest connected component in the ugraph."""
    if not ugraph:
        return 0
    res = [(len(ccc), ccc) for ccc in cc_visited(ugraph)]
    res.sort()
    return res[-1][0]

def compute_resilience(ugraph, attack_order):
    """
    input: a graph {V: N}

    returns a list whose k+1th entry is the size of the largest connected component after the removal of the first k nodes
    """
    res = [len(ugraph)]
    for node in attack_order:
        neighbors = ugraph[node]
        for neighbor in neighbors:
            ugraph[neighbor].remove(node)
        ugraph.pop(node)
        res.append(largest_cc_size(ugraph))
    return res

1. Review

The docstring for bfs_visited should explain the node argument.
The docstring for compute_resilience should explain that the ugraph argument gets modified. Alternatively, the function could take a copy of the graph so that the original is not modified.
In bfs_visited the lines:

queue = deque()
queue.append(node)

can be simplified to:

queue = deque([node])

The function largest_cc_size builds a list of pairs:

res = [(len(ccc), ccc) for ccc in cc_visited(ugraph)]
res.sort()
return res[-1][0]

But you can see that it only ever uses the first element of each pair (the size of the component). So you could simplify it by not building the pairs:

res = [len(ccc) for ccc in cc_visited(ugraph)]
res.sort()
return res[-1]

Since only the size of the largest component is needed, there is no need to build the whole list. Instead you could use max to find the largest:

if ugraph:
    return max(map(len, cc_visited(ugraph)))
else:
    return 0

If you are using Python 3.4 or later, this can be further simplified using the default argument to max:

return max(map(len, cc_visited(ugraph)), default=0)

This is now so simple that it probably doesn't need its own function.
This line:

remaining_nodes = set(graph.keys())

can be written more simply:

remaining_nodes = set(graph)

There is a loop over the set remaining_nodes where on each loop iteration you update remaining_nodes:

for node in remaining_nodes:
    visited = bfs_visited(graph, node)
    if visited not in connected_components:
        connected_components.append(visited)
    remaining_nodes = remaining_nodes - visited

It looks as if the intention of the code to avoid iterating over the nodes in visited by removing them from remaining_nodes, but this doesn't work! The problem is that the for statement:

for node in remaining_nodes:

only evaluates the expression remaining_nodes once, at the start of the loop. So when the code creates a new set and assigns it to remaining_nodes:

remaining_nodes = remaining_nodes - visited

this has no effect on the nodes being iterated over.
You might imagine trying to fix this by using the difference_update method to adjust the set being iterated over:

remaining_nodes.difference_update(visited)

but this would be a bad idea because then you would be iterating over a set and modifying it within the loop, which is not safe. Instead, you need to write the loop as follows:

while remaining_nodes:
    node = remaining_nodes.pop()
    visited = bfs_visited(graph, node)
    if visited not in connected_components:
        connected_components.append(visited)
    remaining_nodes.difference_update(visited)

Using while and pop is the standard idiom in Python for consuming a data structure while modifying it — you do something similar in bfs_visited.
There is now no need for the test:

if visited not in connected_components:

since each component is produced exactly once.
In compute_resilience the first line is:

res = [len(ugraph)]

but this only works if the graph is a single connected component to start with. To handle the general case, the first line should be:

res = [largest_cc_size(ugraph)]

For each node in attack order, compute_resilience calls:

res.append(largest_cc_size(ugraph))

But this doesn't take advantage of the work that was previously done. When we remove node from the graph, all connected components remain the same, except for the connected component containing node. So we can potentially save some work if we only do a breadth-first search over that component, and not over the whole graph. (Whether this actually saves any work depends on how resilient the graph is. For highly resilient graphs it won't make much difference.)

In order to do this we'll need to redesign the data structures so that we can efficiently find the component containing a node, and efficiently remove that component from the collection of components.

This answer is already quite long, so I won't explain in detail how to redesign the data structures, I'll just present the revised code and let you figure it out for yourself.

def connected_components(graph, nodes):
    """Given an undirected graph represented as a mapping from nodes to
    the set of their neighbours, and a set of nodes, find the
    connected components in the graph containing those nodes.

    Returns:
    - mapping from nodes to the canonical node of the connected
      component they belong to
    - mapping from canonical nodes to connected components

    """
    canonical = {}
    components = {}
    while nodes:
        node = nodes.pop()
        component = bfs_visited(graph, node)
        components[node] = component
        nodes.difference_update(component)
        for n in component:
            canonical[n] = node
    return canonical, components

def resilience(graph, attack_order):
    """Given an undirected graph represented as a mapping from nodes to
    an iterable of their neighbours, and an iterable of nodes, generate
    integers such that the the k-th result is the size of the largest
    connected component after the removal of the first k-1 nodes.

    """
    # Take a copy of the graph so that we can destructively modify it.
    graph = {node: set(neighbours) for node, neighbours in graph.items()}

    canonical, components = connected_components(graph, set(graph))
    largest = lambda: max(map(len, components.values()), default=0)
    yield largest()
    for node in attack_order:
        # Find connected component containing node.
        component = components.pop(canonical.pop(node))

        # Remove node from graph.
        for neighbor in graph[node]:
            graph[neighbor].remove(node)
        graph.pop(node)
        component.remove(node)

        # Component may have been split by removal of node, so search
        # it for new connected components and update data structures
        # accordingly.
        canon, comp = connected_components(graph, component)
        canonical.update(canon)
        components.update(comp)
        yield largest()

In the revised code, the max operation has to iterate over all the remaining connected components in order to find the largest one. It would be possible to improve the efficiency of this step by storing the connected components in a priority queue so that the largest one can be found in time that's logarithmic in the number of components.

I doubt that this part of the algorithm is a bottleneck in practice, so it's probably not worth the extra code, but if you need to do this, then there are some Priority Queue Implementation Notes in the Python documentation.

2. Performance comparison

Here's a useful function for making test cases:

from itertools import combinations
from random import random

def random_graph(n, p):
    """Return a random undirected graph with n nodes and each edge chosen
    independently with probability p.

    """
    assert 0 <= p <= 1
    graph = {i: set() for i in range(n)}
    for i, j in combinations(range(n), 2):
        if random() <= p:
            graph[i].add(j)
            graph[j].add(i)
    return graph

Now, a quick performance comparison between the revised and original code. Note that we have to run the revised code first, because the original code destructively modifies the graph, as noted in §1.2 above.

>>> from timeit import timeit
>>> G = random_graph(300, 0.2)
>>> timeit(lambda:list(resilience(G, list(G))), number=1) # revised
0.28782312001567334
>>> timeit(lambda:compute_resilience(G, list(G)), number=1) # original
59.46968446299434

So the revised code is about 200 times faster on this test case.


Mendelian inheritance I started out with the Rosalind problems a while back. Turns out it's a great way to learn a new language. I'm still trying to learn Ruby, and while I haven't managed to use regular expressions as much as I wanted to (learning those being one of the reasons I started learning Ruby in the first place), I put together a repository of whatever challenges I have solved so far.

I learned how easy it is to benchmark with Ruby, so I put that to the test as well. While the resulting solution is good, it's quite possible there's a better one out there.

Problem: IPRB

  Probability is the mathematical study of randomly occurring phenomena. We will model such a phenomenon with a random variable, which is simply a variable that can take a number of different distinct outcomes depending on the result of an underlying random process.

  For example, say that we have a bag containing 3 red balls and 2 blue balls. If we let \$X\$
  represent the random variable corresponding to the color of a drawn ball, then the probability of each of the two outcomes is given by \$Pr[X=red]=35\$ and \$Pr[X=blue]=25\$.

  Random variables can be combined to yield new random variables. Returning to the ball example, let \$Y\$
  model the color of a second ball drawn from the bag (without replacing the first ball). The probability of \$Y\$ being red depends on whether the first ball was red or blue. To represent all outcomes of \$X\$ and \$Y\$, we therefore use a probability tree diagram. This branching diagram represents all possible individual probabilities for \$X\$ and \$Y\$, with outcomes at the endpoints ("leaves") of the tree.

Given:

  Three positive integers \$k, m,\$ and \$n\$, representing a population containing \$k+m+n\$ organisms: \$k\$ individuals are homozygous dominant for a factor, \$m\$ are heterozygous, and \$n\$ are homozygous recessive.

Return:

  The probability that two randomly selected mating organisms will produce an individual possessing a dominant allele (and thus displaying the dominant phenotype). Assume that any two organisms can mate.

Sample dataset:

2 2 2

Sample output:

0.78333

My solution solves the sample dataset and the actual dataset given:

Dataset:

22 26 27

Solution:

0.71775

IPRB.rb:

def probability_dominant(k, m, n)
    (k * k + k * (2 * m + 2* n - 1) + m * (0.75 * m + n - 0.75)) / ((k + m + n - 1) * (k + m + n))
end

user_input = gets.chomp

split_input = user_input.split().map { |number| number.to_i() }
puts probability_dominant(split_input[0], split_input[1], split_input[2]).round(5)

The math involved appears to be the performance bottleneck.

IPRB_benchmark.rb:

def probability_dominant_1(k, m, n)
    ((k * k - k) + 2 * (k * m) + 2 * (k * n) + (0.75 * (m * m - m)) + 2 * (0.5 * m * n))/((k + m + n)*(k + m + n -1))
end

def probability_dominant_2(k, m, n)
    (k * k + k * (2 * m + 2* n - 1) + m * (0.75 * m + n - 0.75)) / ((k + m + n - 1) * (k + m + n))
end

def probability_dominant_3(k, m, n)
    (k * k + k * m + k + 0.25 * m * m + 0.75 * m)/(k + m + n) - (k * k + k * m - k + 0.25 * m * m - 0.25 * m) / (k + m + n - 1)
end

require 'benchmark'

n = 500000
Benchmark.bm(6) do |x|
  x.report("first:")   { for i in 1..n; probability_dominant_1(n, n, n); end }
  x.report("second:")   { for i in 1..n; probability_dominant_2(n, n, n); end }
  x.report("third:")   { for i in 1..n; probability_dominant_3(n, n, n); end }
end

Output:

             user     system      total        real
first:   0.594000   0.000000   0.594000 (  0.597825)
second:  0.328000   0.000000   0.328000 (  0.316578)
third:   0.500000   0.000000   0.500000 (  0.517067)

I optimized the math the best I could, but optimizing for a computer is a lot sketchier than optimizing for a human. It's quite hard to keep it fast for the machine and readable for a human at the same time. I foresee the upcoming challenges to be more and more mathematically inclined, so I better tackle this here and now.

Any and all advice about how to math in Ruby is appreciated. Nitpicks are welcome too.

Profiling and Benchmarking
Rather than benchmarking, which just does total time, you would be better off profiling, which is like recursive benchmarking.  I recommend you use the ruby-prof gem.
I profiled your code thusly:
require 'ruby-prof'

n = 500000
puts "========================DOM 1============================="
RubyProf.start
(1..n).each { |n| probability_dominant_1(n, n, n) }
result = RubyProf.stop
printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT)

puts "========================DOM 2============================="
RubyProf.start
(1..n).each { |n| probability_dominant_2(n, n, n) }
result = RubyProf.stop
printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT)

puts "========================DOM 3============================="
RubyProf.start
(1..n).each { |n| probability_dominant_3(n, n, n) }
result = RubyProf.stop
printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT)

And got the following results:
========================DOM 1=============================
Measure Mode: wall_time
Thread ID: 1975060
Fiber ID: 22475080
Total: 4.755476
Sort by: self_time

 %self      total      self      wait     child     calls  name
 55.06      4.501     2.618     0.000     1.883   500000   Object#probability_dominant_1
 11.69      0.556     0.556     0.000     0.000  1434466   Fixnum#*
 10.14      0.482     0.482     0.000     0.000  1433660   Bignum#+
  7.95      0.378     0.378     0.000     0.000  1500000   Float#*
  6.60      0.314     0.314     0.000     0.000   934466   Bignum#-
  5.34      4.755     0.254     0.000     4.501        1   Range#each
  3.13      0.149     0.149     0.000     0.000   500000   Float#/
  0.08      0.004     0.004     0.000     0.000    24252   Fixnum#+
  0.00      4.755     0.000     0.000     4.755        1   Global#[No method]

* indicates recursively called methods
========================DOM 2=============================
Measure Mode: wall_time
Thread ID: 1975060
Fiber ID: 22475080
Total: 2.474247
Sort by: self_time

 %self      total      self      wait     child     calls  name
 60.31      2.258     1.492     0.000     0.766   500000   Object#probability_dominant_2
 10.67      0.264     0.264     0.000     0.000   952579   Bignum#+
  8.73      2.474     0.216     0.000     2.258        1   Range#each
  5.38      0.133     0.133     0.000     0.000   500000   Fixnum#*
  5.17      0.128     0.128     0.000     0.000   500000   Float#/
  4.73      0.117     0.117     0.000     0.000   500000   Float#+
  4.73      0.117     0.117     0.000     0.000   500000   Float#*
  0.28      0.007     0.007     0.000     0.000    31037   Fixnum#+
  0.00      2.474     0.000     0.000     2.474        1   Global#[No method]

* indicates recursively called methods
========================DOM 3=============================
Measure Mode: wall_time
Thread ID: 1975060
Fiber ID: 22475080
Total: 4.334434
Sort by: self_time

 %self      total      self      wait     child     calls  name
 50.85      4.074     2.204     0.000     1.870   500000   Object#probability_dominant_3
 17.44      0.756     0.756     0.000     0.000  2364956   Bignum#+
 16.66      0.722     0.722     0.000     0.000  3000000   Float#*
  6.00      4.334     0.260     0.000     4.074        1   Range#each
  5.42      0.235     0.235     0.000     0.000  1000000   Float#/
  3.39      0.147     0.147     0.000     0.000   476830   Bignum#-
  0.23      0.010     0.010     0.000     0.000    46340   Fixnum#+
  0.00      4.334     0.000     0.000     4.334        1   Global#[No method]

* indicates recursively called methods

Foreach function, these tables show the number of calls and time spent on function call, recursively all the way down.  Some portions, like the "range#each" can be ignored as part of of our testing overhead.
Looking at the results, I can spot why dominant_2 is the fastest.  Integer operations (FixNum) on a processor will always be faster.  Floating point (Float) is slow and floating point divisiondividing is slow, and big integers (integer numbers bigger than that hardware can natively support, typically 2^32 or 2^64) will also be slower.

Dom1 has 2M Float, ~2.4M BigNum, and ~1.4M FixNum operations.
Dom2 has 1.5M Float, ~1M BigNum, and ~530K FixNum operations.
Dom3 has 4M Float, ~2.3M BigNum, and ~46K FixNum operations.

Dom2 was the fastest because it has the fewest number of operations by far.
As a weak rule of thumb, when optimizing math, try to avoid BigNum and Float when feasible.  Also try to avoid things like converting numbers to strings and then back to numbers.
Conclusion
Know that more often though, that your slowdown will usually come from lots of branching and flow control, and being inefficient (like calculating the same things over and over rather than caching them), and those are the places to optimize.  If this problem were part of a larger, more complicated task, I can practically guarantee that your bottleneck would not be ANY of these functions, but something else entirely.


Find the lengths of strongly connected components in a graph I wrote a code to calculate the lengths of strongly connected components in a graph. The results I get are correct but it scales horribly.

This is the code I have. I understand that the runtime complexity of a graph traversals should be O(V+E) and as far as I understand, I am not visiting any node twice. And yet it takes forever for bigger graphs (875714 nodes and 5105043 edges)

class Graph:
    def __init__(self):
        self.graph = {}
        self.rev_graph = {}
        self.num_vertices = 0
    def addEdge(self, tail, head):
        if tail in self.graph:
            self.graph[tail].append(head)
        else:
            self.graph[tail]=[head]
        if head in self.rev_graph:
            self.rev_graph[head].append(tail)
        else:
            self.rev_graph[head] = [tail]
    def dfs(self, visited, start_node, stack):
        visited[start_node] = True
        if start_node in self.graph:
            for i in self.graph[start_node]:
                if not visited[i]:
                    self.dfs(visited, i, stack)
            # del self.rev_graph[start_node]
        stack.append(start_node)
    def dfs_counter(self, visited, start_node, delim='  '):
        l1 = sum(visited)
        visited[start_node] = True
        if start_node in self.rev_graph:
            # print(delim, 'rev graph neighbors: ', start_node, self.rev_graph[start_node])
            for i in self.rev_graph[start_node]:
                if not visited[i]:
                    self.dfs_counter(visited, i, 2*delim)
        l2 = sum(visited)
        return l2 - l1
        # print(stack)
    def find_scc_lens(self):
        self.num_vertices = len(set(list(self.graph.keys()) + list(self.rev_graph.keys())))
        visited = [False]*self.num_vertices
        stack = []
        self.dfs(visited, 0, stack)
        # stack = stack[::-1]
        # print(stack)
        # del(self.graph)
        visited = [False] * self.num_vertices
        scc_lengths = []
        for k,i in enumerate(stack[::-1]):
            if not visited[i]:
                # print("rev graph node count", k, i)
                scc_lengths.append(self.dfs_counter(visited, i))
        return scc_lengths

This exercise is from an online course I am taking. I tried a few other solutions online I found elsewhere and they are really fast compared to my runtimes.

What parts of the code can I optimize to improve the runtimes?

Example:

g = Graph()
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
g.find_scc_lens()

class Graph:
    def __init__(self):
        self.graph = {}
        self.rev_graph = {}
        self.num_vertices = 0

This looks reasonable. Note that the PEP8 style guide wants you to add a blank line after each method.

    def addEdge(self, tail, head):
        if tail in self.graph:
            self.graph[tail].append(head)
        else:
            self.graph[tail]=[head]
        if head in self.rev_graph:
            self.rev_graph[head].append(tail)
        else:
            self.rev_graph[head] = [tail]

The failure to update self.num_vertices here does not look reasonable. I suspect that the reason is that num_vertices shouldn't be a property of the class.

    def dfs(self, visited, start_node, stack):
        visited[start_node] = True
        if start_node in self.graph:
            for i in self.graph[start_node]:
                if not visited[i]:
                    self.dfs(visited, i, stack)
            # del self.rev_graph[start_node]
        stack.append(start_node)

In future, please remove commented code before submitting the code for review.

I could use a comment to explain the purpose of stack, and why it adds in post-order rather than pre-order.

    def dfs_counter(self, visited, start_node, delim='  '):
        l1 = sum(visited)
        visited[start_node] = True
        if start_node in self.rev_graph:
            # print(delim, 'rev graph neighbors: ', start_node, self.rev_graph[start_node])
            for i in self.rev_graph[start_node]:
                if not visited[i]:
                    self.dfs_counter(visited, i, 2*delim)
        l2 = sum(visited)
        return l2 - l1
        # print(stack)

sum(visited) is expensive: too expensive to use in this method, which is called inside a loop. If you refactor to track the sum directly then I expect you'll see a notable speedup.

2*delim probably isn't really desirable: it should probably be delim + '  '.

    def find_scc_lens(self):
        self.num_vertices = len(set(list(self.graph.keys()) + list(self.rev_graph.keys())))

It should be possible to do this without using list.

        visited = [False]*self.num_vertices

This is buggy. num_vertices is the number of vertices, not the largest vertex. Consider the graph

g = Graph()
g.addEdge(2, 3)
g.addEdge(3, 2)

The output should be either [2] (vertices with no edges don't exist) or some permutation of [1, 1, 2] (with vertices 0 to 3).

        stack = []
        self.dfs(visited, 0, stack)
        # stack = stack[::-1]
        # print(stack)
        # del(self.graph)

This is also buggy. What about vertices which aren't reachable from 0? Even if you add documentation saying that this method only works for connected graphs, that doesn't rule out

g = Graph()
g.addEdge(1, 2)
g.addEdge(2, 1)
g.addEdge(1, 0)

        visited = [False] * self.num_vertices
        scc_lengths = []
        for k,i in enumerate(stack[::-1]):
            if not visited[i]:
                # print("rev graph node count", k, i)
                scc_lengths.append(self.dfs_counter(visited, i))
        return scc_lengths

In order to validate the correctness of this implementation, it would be immensely useful to have a comment which says which algorithm it implements (and ideally links to reference material).


Extracting values from a list I had already solved this problem, but in an unnecessarily convoluted way that seems too specific. Can this be done better?

From a list:

(8 "layer-name" 10 x1 20 y1   10 x2 20 y2  10 x3 20 y3)

8, 10 and 20 are the "key-words" for layer-name, x-coord and y-coord respectively. The actual values follow the "key-words".

Return values should be --> '(("layer-name" x1 y1 x2 y2) ("layer-name" x2 y2 x3 y3))

#lang racket

(require srfi/1)

(define test-list '("multiple-lines" 8 "layer-name" 10 30 20 30   10 40 20 40   10 50 20 50))

(define (get-values lst lst2)
  (cond ((eq? lst2 '())
         '())
        (else
         (cons (cadr (member (car lst2) lst))
               (get-values lst (cdr lst2))))))

(define (get-multiple-values lst key key2) ; key is single values. key2 is repeatable values
  (define (splitter lst keyword) ; (splitter '(10 x1 20 y1 10 x2 20 y2 10 x3 20 y3) 10 20)  --->  '((x1 y1 x2 y2 x3 y3) (x2 y2 x3 y3) (x3 y3))
    (cond ((not (member keyword lst)) '())
          (else (cons (member keyword lst) (splitter (cddr (member keyword lst)) keyword)))))
  (define (joiner lst lst-of-lsts) ; (joiner '(1 2) '((a b) (c d)))  --->  '((1 2 a b) (1 2 c d))
    (cond ((empty? lst-of-lsts) '())
          (else (cons (append lst (car lst-of-lsts))
                      (joiner lst (rest lst-of-lsts))))))
  (define (trimmer size lst-of-lsts) ; (trimmer  '((x1 y1 x2 y2 x3 y3) (x2 y2 x3 y3) (x3 y3)))
    (cond ((empty? lst-of-lsts) '())
          ((> size (length (car lst-of-lsts)))
           (trimmer size (rest lst-of-lsts)))
          (else (cons (take (car lst-of-lsts) size)
                (trimmer size (rest lst-of-lsts))))))
  (joiner (get-values lst key)
          (trimmer 4 (map
                      (lambda (lst) (remq* key2 lst))
                      (splitter lst (first key2))))))

> '(("layer-name" 30 30 40 40) ("layer-name" 40 40 50 50))

I have a strong suspicion that this is an XY Problem, or at the very least, that you're using the wrong abstraction and/or data structure for representing data, using numbers as keywords somehow doesn't seem right. Anyway, I think the requested functionality can be implemented in an alternate, simpler way:

; obtain all values for a given keyword
(define (key-values lst kwd)
  (cond ((null? lst) '())
        ((equal? (first lst) kwd)
         (cons (second lst) (key-values (cddr lst) kwd)))
        (else (key-values (cddr lst) kwd))))

; interleave elements from two lists
(define (interleave lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        (else (cons (first lst1) (interleave lst2 (rest lst1))))))

; create all layers according to the defined structure
(define (joiner name lst1 lst2)
  (let loop ((lst (interleave lst1 lst2)))
    (if (null? (cddr lst))
        '()
        (cons (list name (first lst) (second lst) (third lst) (fourth lst))
              (loop (cddr lst))))))

; main function, receives a list of values and a list of keywords
(define (get-values lst kwds)
  (let ((name (first (key-values lst (first kwds))))
        (xs   (key-values lst (second kwds)))
        (ys   (key-values lst (third kwds))))
    (joiner name xs ys)))

For example:

(define test-list '(8 "layer-name" 10 30 20 30 10 40 20 40 10 50 20 50))
(define keywords '(8 10 20))
(get-values test-list keywords)
=> '(("layer-name" 30 30 40 40) ("layer-name" 40 40 50 50))


Select records and fill hash I use ruby 1.8.7. I have method wich select records and fill hash. In my opinion the code is not dry. Could somebody help me to refactor it and make it shorter and more elegant?

def fill_attributes()
  if (!$array[:status_id])
            $array[:status_id] = @customer.status_id
             @status_name=Status.find($array[:status_id]).name rescue nil
            $array[:status]=@status_name if @status_name
      end

     if (!$array[:color_id])
            $array[:color_id] = @customer.color_id
            @color_name=Color.find($array[:color_id]).name rescue nil
            $array[:color]=@color_name if @color_name
      end
     .....

  end

My version is:

  map={'model1' => Model1, 'model2' => Model2,'model3' =>Model3}

  map.keys.each do |model|
       key="#{model}_id".to_sym
       value="#{model}.#{model}_id"
     if (!$array[key])
          $array[key] =  #instance_variable_set("@#{value}",eval(value, binding) )
          name=map[model].find($array[key]).name rescue nil
          $array[key]=name if name
      end
   end

But there's a problem, to use instance_variable_set I have to create a class? What is the  best way to refactor it?

I think you can optimize it like :

def fill_attributes()
  if (!$array[:status_id])
    $array[:status_id] = @customer.status_id
    $array[:status]= get_attribute_name('status',$array[:status_id] )
  end

  if (!$array[:color_id])
    $array[:color_id] = @customer.color_id
    $array[:color]= get_attribute_name('color',$array[:color_id] )
  end

end

Private

def get_attribute_name(relator, relator_id)
  relator = relator.classify.constantize.find(relator_id)
  !relator.nil? ? relator.name : nil
end

Hope this will help you .


Weapon class firing logic in JavaScript I'm making a program to compare Borderlands 3 weapon damage over time in a graphic. There's still some work to be done, like implementing elemental damage, but I'd like to know if I'm doing a good job for now regarding the main firing logic.

My biggest concerns are:

General readability.
WeaponReload and WeaponFire extend WeaponAction, a class containing the properties .startTime, .endTime and .duration (included after the Weapon class code) and both are being treated as if they're the same. I think some other languages can do something similar using structs and protocols to check conformity and I'm not sure if this is the right way to do it in JavaScript.
I don't know whether I'm doing a good use of the try {...} catch {...} statement in Weapon.fullAuto or if this logic could be improved upon using other methods.

class Weapon {
    constructor (damage, fireRate, reloadSpeed, magazineSize, elementalDamage, elementalChance) {
        this.damage = damage
        this.fireRate = fireRate
        this.reloadSpeed = reloadSpeed
        this.magazineSize = magazineSize
        this.elementalDamage = elementalDamage
        this.elementalChance = elementalChance

        this.bulletsLeftInMagazine = magazineSize
    }
    get timePerShot () {
        return 1 / this.fireRate
    }
    fire (startTime = 0) {
        if (this.bulletsLeftInMagazine < 1)
            throw new Error("Not enough bullets in the magazine")

        let whenCanFireAgain = startTime + this.timePerShot

        --this.bulletsLeftInMagazine

        return new WeaponShot(startTime, whenCanFireAgain, this.damage)
    }
    reload (startTime = 0) {
        let whenCanFireAgain = startTime + this.reloadSpeed

        this.bulletsLeftInMagazine = this.magazineSize

        return new WeaponReload(startTime, whenCanFireAgain)
    }
    fullAuto (duration, startTime = 0) {
        let localActionStartTime = 0,
            globalActionStartTime = startTime,
            actions = []

        while (duration > localActionStartTime) {

            let localActionEndTime,
                globalActionEndTime,
                action

            try {
                action = this.fire(globalActionStartTime)
            } catch {
                action = this.reload(globalActionStartTime)
            }

            actions.push(action)

            localActionStartTime += action.duration
            globalActionStartTime += action.duration

        }

        return actions
    }
}

class WeaponAction {
    constructor (startTime, endTime, damageDealt) {
        this.startTime = startTime
        this.endTime = endTime
        this.damageDealt = damageDealt
    }
    get duration () {
        return this.endTime - this.startTime
    }
}

I understand semicolons in JavaScript are optional, however I believe you should always use them. It's easy to have something break later on because you neglected a semi-colon and it lost the whitespace which saved it before in a compression/generation/eval parse.

You could declare the timePerShot as a variable, to ensure the amount is not being calculated on every call (Although I'm pretty sure the parser or cache already solves this).

Use exceptions / errors in exceptional cases only. An example being making an HTTP call; The target could not exist, the internet could be down, or other cases that are out of your control.

Catching exceptions is also going to be very slow. You can return a value such as false instead. And/or you could do the check outside of the function.


Showing data for a chat with another user I have a get route to show the data for a chat with another user. If an existing chat exists I want to return that, otherwise create a new chat and return it.

/chat/user/{contra_user_id}

Should my Service or my repository be adding chat members to the chat? Currently I have my service creating each member.

class ChatService
{
    private $chatRepository;

    public function __construct(ChatRepository $chatRepository)
    {
        $this->chatRepository = $chatRepository;
    }

    public function findByUsers(User $user, User $contraUser) : Collection
    {
        $chat = $this->chatRepository->findByUsers($user, $contraUser);
        if ($chat = $chat->first()) {
            return $chat;
        }

        $chat = $this->chatRepository->create();
        $member = $this->chatMemberRepository->create($chat, $user);
        $contraMember = $this->chatMemberRepository->create($chat, $user);
        $returnChat = $this->chatRepository->find($chat->id);

        return $returnChat;
    }
}

You can break the functionality in to 2 seperate methods to make it more reusable. Here, findChatByUsers could return a collection or null, so the type hint was removed.

public function findChatByUsers(User $user, User $contraUser)
{
    $chat = $this->chatRepository
        ->findByUsers($user, $contraUser)
        ->first();

    return $chat;
}

public function getChat(User $user, User $contraUser) : Collection
{
    $chat = $this->findChatByUsers($user, $contraUser);

    // If chat is not available, create new chat
    if (!$chat) {
        $chat = $this->chatRepository->create();
        $member = $this->chatMemberRepository->create($chat, $user);
        $contraMember = $this->chatMemberRepository->create($chat, $user);
        $chat = $this->chatRepository->find($chat->id);
    }

    return $chat;
}


Heap insertion and deletion Implementation using Python I have implemented basic max heap insertion and deletion functions without recursion
# insertion
arr: [6,5,4,3,2,1]

# insert 7
arr: [7,5,6,3,2,1,4]
tree:

        7
    5       6
  3   2   1    4

# delete 7
arr: [6,5,4,3,2,1]
tree:

        6
    5       4
  3   2  1

My implementation
def insert(arr,ele):
    # bottom up
    n = len(arr)
    # insert into the n+1 position
    new_arr = arr.append(ele)
    i = n # last position
    while True:
        p_index = int((i-1)/2)
        # compare with the parent index
        if (arr[i] > arr[p_index]):
            # swap the elements
            arr[p_index], arr[i] = arr[i], arr[p_index]
            i = p_index
        else:
            # correct
            break
    return arr

# deletion
def delete(arr):
    # top down
    if not arr:
        return None
    # swap the last elment to root
    arr[0], arr[len(arr)-1] = arr[len(arr)-1], arr[0]
    item = arr.pop()
    n = len(arr)
    i = 0
    # comparing the children
    while True:
        # left/right child index
        lc_index = 2*i + 1
        rc_index = 2*i + 2
        # no chilren
        if lc_index > n-1:
            break
        # only has left child
        if lc_index == (n-1) and rc_index > n-1:
            if arr[lc_index] > arr[i]:
                arr[i], arr[lc_index] = arr[lc_index], arr[i]
            break
        else:
            if arr[lc_index] > arr[rc_index]:
                arr[i], arr[lc_index] = arr[lc_index], arr[i]
                i = lc_index
            else:
                arr[i], arr[rc_index] = arr[rc_index], arr[i]
                i = rc_index
    return item

These two functions works fine, but looks pretty cumbersome especially the delete function, any suggestions how to improve the code?

Integer division
Are you using Python 3?  If so, there is the integer division operator: //.  Instead of:
    p_index = int((i-1)/2)

you can write:
    p_index = (i - 1) // 2

Unnecessary variable
In your insert function, where do you use n?
    n = len(arr)
    ...
    i = n # last position

Seems like you can get rid of the n variable, and just initialize i = len(arr)
Wrong variable
In delete, where do you use n?
You might say it is used in several places.  I'd disagree.  I'd say it is never used; you only use n-1.
What is n-1?  It is the last index of the array:
    last = len(arr) - 1

    ...

    if lc_index > last:
        ...
    if lc_index == last and rc_index > last:
        ...

Unnecessary test:
Consider:
    lc_index = 2*i + 1
    rc_index = 2*i + 2

Note that we could rewrite that last statement as
    rc_index = lc_index + 1

Now consider:
    if lc_index == last and rc_index > last:
        ...

Substitute for rc_index ...
    if lc_index == last and lc_index + 1 > last:
        ...

If the first part of that test is True, the second part will always be True; if the first part is false, the second part will never be evaluated.  So you just need:
    if lc_index == last:
        ...

Left or right?
The code for the left & right children look identical, save for the index being used.
Instead of:
        if arr[lc_index] > arr[rc_index]:
            arr[i], arr[lc_index] = arr[lc_index], arr[i]
            i = lc_index
        else:
            arr[i], arr[rc_index] = arr[rc_index], arr[i]
            i = rc_index

You could select the correct left or right index to use:
        child_index = lc_index if arr[lc_index] > arr[rc_index] else rc_index

Then you don't need two copies of the remaining code:
        arr[i], arr[child_index] = arr[child_index], arr[i]
        i = child_index

Last element
 arr[0], arr[len(arr)-1] = arr[len(arr)-1], arr[0]

The arr[len(arr)-1] references the last element of arr, by determining the length of the array, and subtracting one to compute the zero-based index.
Using arr[-1] also references the last element of the array, using Python's negative indexing feature.  This allows a much simpler statement:
 arr[0], arr[-1] = arr[-1], arr[0]


Java Rock/Paper/Scissors Game For my computer science class I am tasked with writing a rock/paper/scissors game. I understand how to write the game, but I was wondering if someone more experienced than I could give me some pointers on how to become a better programmer.

Is there anything I could do to reduce the size of the code, but without diminishing functionality?

public class RockPaperScissors
{
    static double wins = 0;
    static double losses = 0;
    static double draws = 0;
    static double games = 0;

    private static void lose() {
        System.out.println("YOU LOSE! :D");
        losses++;
        games++;
    }

    private static void win() {
        System.out.println("you win :D");
        wins++;
        games++;
    }

    // main method
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);

        // variables
        Integer answer1 = 0;
        boolean playing = true;

        // start of game
        do
        {
            // main menu
            System.out.println("Input R, P, S, or Q(to quit).");

            // player's move
            String answer = scan.next();
            answer = answer.toLowerCase();

            // converts player's move from str to int
            switch (answer.charAt(0))
            {
            case 'r':
                answer1 = 0;
                break;
            case 'p':
                answer1 = 1;
                break;
            case 's':
                answer1 = 2;
                break;
            case 'q':
                System.out.println("User exit.");
                double winP = wins/games*100;
                double loseP = losses/games*100;
                double drawP = draws/games*100;
                System.out.println("Wins: " + wins);
                System.out.printf("%.2f", winP);
                System.out.println(" Percent");
                System.out.println("Losses: " + losses);
                System.out.printf("%.2f", loseP);
                System.out.println(" Percent");
                System.out.println("Draws: " + draws);
                System.out.printf("%.2f", drawP);
                System.out.println(" Percent");
                playing = false;
                break;
            default:
                System.out.println("ERROR!!");
                playing = false;
                break;
            }

            // checks for conditions
            if (playing)
            {
                // computer's move
                Random random = new Random();
                Integer choice = random.nextInt(3); // (n-1) 0 = rock, 1 = paper, 2 = scissors
                String comp = choice.toString();
                switch (comp)
                {
                case "0":
                    System.out.println("computer chose rock");
                    break;
                case "1":
                    System.out.println("computer chose paper");
                    break;
                case "2":
                    System.out.println("computer chose scissors");
                    break;
                default:
                    System.out.println("ERROR!");
                    break;
                }
                // checks results
                if (answer1 == choice)
                {
                    System.out.println("Draw");
                    draws++;
                    games++;
                }
                else if ((answer1 + 1) % 3 == choice)
                    lose();
                else if ((choice + 1) % 3 == answer1)
                    win();
                else
                    System.out.println("ERROR! ERROR!");
            }
        } while (playing);
    }
}

What do you mean by "reduce the size"? Code or byte-code?
If it's code you can easily remove a few lines by merging your System.out.print*():

System.out.printf("Wins: %d %.2f%%\nLosses: %d %.2f%%\nDraws %d %.2f%%",
    wins, winP, losses, loseP, draws, drawP);

Also, what is the use of transforming Integer into a String for the switch()? switch() on String was introduced in Java 7. A better-optimized version would be to use int directly:

int choice = random.nextInt(3); // (n-1) 0 = rock, 1 = paper, 2 = scissors
switch (choice) {
    case 0:
        ...
}

You can also have a String[] to store what you want to display:

String[] rps = { "rock", "paper", "scissors" };
if (choice >= 0 && choice < rps.length)
    System.out.println("Computer chose "+rps[choice]);
else
    System.out.println("Wrong choice!");
// Or use ternary operator:
//System.out.println(choice >= 0 && choice < rps.length ? "Computer chose "+rps[choice] : "Wrong choice!");

For byte-code size you can use primitive int instead of class Integer. And also int for your wins, losses, draws and games variables: ++ incrementation is a lot faster on int than on double. You can convert them to double only when computing the percentage (and correct a potential percentage calculation bug when using integer arithmetics):

loseP = 100.0 * losses / games; // 100.0 is a double, so 100.0 * losses is a double and (100.0 * losses) / games is also a double
// loseP = losses/games*100 will always be an int: losses and games are int, losses/games is an int, 100 is an int and losses/games*100 is an int

I'll let you figure out the rest :)


Largest Prime factor (Project Euler in Rust) I've been working on my Rust a bit and want to know how idiomatic my rust code is for the following Project Euler problem:
What is the largest prime factor of the number 600851475143 ?
I'm not looking for ways to improve efficiency or how to improve the strategy, but purely what I can improve with my Rust technique. There's two files: src/prime/sieve.rs which has a function for generating a vector of prime numbers, and src/p003.rs which is where the problem is solved.
// src/prime/sieve.rs

pub fn sieve(ceil: usize) -> Vec<usize> {
    let mut is_prime = vec![true; ceil + 1];
    is_prime[0] = false;
    if ceil >= 1 {
        is_prime[1] = false
    }

    for num in 2..ceil + 1 {
        if is_prime[num] {
            let mut factor = num * num;
            while factor <= ceil {
                is_prime[factor] = false;
                factor += num;
            }
        }
    }

    is_prime
        .iter()
        .enumerate()
        .filter_map(|(p, &is_p)| if is_p { Some(p) } else { None })
        .collect()
}

// src/prime/mod.rs

pub mod sieve;

// src/p003.rs

// https://projecteuler.net/problem=3
mod prime;
use prime::sieve::sieve;

fn biggest_prime_factor(n: usize) -> usize {
    for p in sieve((600851475143_f32.sqrt()) as usize).iter().rev() {
        if n % *p == 0 {
            return *p;
        }
    }
    return 0;
}

fn main() {
    println!("{}", biggest_prime_factor(600851475143));
}

I think
    for p in sieve((600851475143_f32.sqrt()) as usize).iter().rev() {

should be
    for p in sieve(((n as f32).sqrt()) as usize).iter().rev() {

Alternative approach
You could chain an iterator in runtime:
#[test]
fn main_playground() {
    // Sieve iterator-style
    let number: u128 = 600851475143;
    let upper_limit: u128 = (number as f32).sqrt().floor() as _;

    let mut sieve: Box<dyn Iterator<Item = _>> = Box::new(2..=upper_limit);

    while let Some(prime_number) = sieve.next() {
        sieve = Box::new(sieve.filter(move |&x| x % prime_number != 0));
        if number % (prime_number as u128) == 0 {
            dbg!(prime_number);
        }
    }
}

The answer is still 6857. But output is
running 1 test
[src\problem_003.rs:12] prime_number = 71
[src\problem_003.rs:12] prime_number = 839
[src\problem_003.rs:12] prime_number = 1471
[src\problem_003.rs:12] prime_number = 6857

I can think of many more approaches to this. I'd actually build a Sieve iterator
if I were you.


Pair matching elements from two lists Here is a method that takes two lists (l1 and l2) and pairs up elements that "match". As you can see at the end of the code block these lists consist of matching elements but in different indexes. The method pairUp outputs matching elements paired up, and discards those without a pair.

I spent way too much time writing this method, and it feels clumsy and complex, not scala idiomatic.

How could I have done this simpler? and could I make it faster?

case class A(serial:Int) {
  def matches(b:B):Boolean = this.serial == b.serial
}
case class B(serial:Int)

import scala.annotation.tailrec
@tailrec def pairUp(
  list1:List[A],
  list2:List[B],
  i:Int=0,
  pairs:List[(A, B)]=List.empty[(A,B)]
):List[(A,B)] = {
  if (list1.isEmpty || list2.isEmpty) return pairs
  else {
    if (i == list2.length)  // this list1 element has no match
      return pairUp(
        list1.tail,         // so discard
        list2,
        0, // reset counter
        pairs)
    else {
      if (list1.head matches list2.head) // these elements match
        return pairUp(
          list1.tail,
          list2.tail,
          0,
          pairs :+ ((list1.head, list2.head)))
      else
        return pairUp(
          list1,
          list2.tail :+ list2.head, // list2 element to back
          i + 1,
          pairs)
    }
  }
}

val l1 = List(0, 1, 2, 3, 4, 5).map(A(_))
val l2 = List(1, 3, 0, 2, 4).map(B(_))

val pairs = pairUp(l1, l2)
// List((A(0),B(0)), (A(1),B(1)), (A(2),B(2)), (A(3),B(3)), (A(4),B(4)))
println(pairs)

I am not an expert at scala, but this works for me

def pairUp2( list1: List[A], list2: List[B]): List[(A, B)] = {
    (for{
     a <- list1
     b <- list2
     if a.serial == b.serial
   } yield (a,b))
 }

 val pairs = pairUp2(l1, l2)
 pairs: List[(A, B)] = List((A(0),B(0)), (A(1),B(1)), (A(2),B(2)), (A(3),B(3)), (A(4),B(4)))

The for comprehension, takes each element of list1 and an element of list2 and yields a tuple only if the serial values match.


Testing the Dutch national flag task I recently coded the Dutch national flag problem in Java and wrote some tests.
The array in zero-indexed.
Please take a look at how I verify that elements of the output array are in the right order. It's the method verifyDutch

The Dutch national flag problem

public static void dutchFlag(int[] input, int mid) {
    if (input == null || input.length < 2) {
        return;
    }
    int i = 0; // the end of the red region
    int j = 0; // the element under consideration
    int k = input.length - 1; // the start of the blue region
    while (j <= k) {
        if (input[j] < mid) {
            swap(input, i, j);
            i++;
            j++;
        } else if (input[j] == mid) {
            j++;
        } else {
            swap(input, j, k);
            k--;
        }
    }
}

Testing

public class FlagSortsTests {

    @Test
    public void testDutchWithRandom() {
        int[] input = new int[10];
        Random random = new Random();
        for (int i = 0; i < input.length; i++) {
            input[i] = random.nextInt(100);
        }
        int mid = input[random.nextInt(input.length - 1)];
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    @Test
    public void testDutchSmallestMid() {
        int[] input = { 12, 34, 781, -1 };
        int mid = -1;
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    @Test
    public void testDutchLargestMid() {
        int[] input = { 12, 34, 781, -1 };
        int mid = 781;
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    @Test
    public void testDutchWithoutMid() {
        int[] input = { 12, 34, 781, -1 };
        int mid = 90;
        FlagSorts.dutchFlag(input, mid);
        verifyDutch(input, mid);
    }

    private void verifyDutch(int[] input, int mid) {
        if (input == null || input.length < 2) {
            return;
        }
        for (int i = 1; i < input.length; i++) {
            if (input[i] < mid) {
                Assert.assertTrue(input[i - 1] < mid);
            } else if (input[i - 1] == mid) {
                Assert.assertTrue(input[i] >= mid);
            } else if (input[i - 1] > mid) {
                Assert.assertTrue(input[i] > mid);
            }
        }
    }

Update #1

The assert failure messages are wrong. Let me delete them until I write something more infomative

Black hole

If the input is invalid, then there's no feedback to the caller, you just swallow the problem.  This may be ok for your situation, but generally I'd try to make sure the caller has some way of knowing if the operation did anything.

if (input == null || input.length < 2) {
    return;
}

You also don't have any tests for these edge cases (which may be fine if you really don't care about them, but then why bother checking the input at all).

Naming

Rather than giving your variables a single character and a descriptive comment at the top, consider giving the variable a meaningful name endOfRed.  You don't need the comment and you're not going to forget what the variable refers to as you move through the code.

int i = 0; // the end of the red region

Random

From a human perspective, running a bunch of tests with random values can be very reassuring.  However you want your unit tests to be repeatable and reliable.  Having random numbers generated to seed your tests can result in intermittent failures which you want to avoid (consider the impact if this was part of a larger build process).  If you do want to use random, then it would be a good idea to make sure that on failure the input data set is logged / displayed.  The only thing worse than an intermittent failure is one that you can't reproduce.

assertTrue

I'm not a huge fan of assertTrue.  People will often use it to assert equality and the feedback you get from assertTrue (expected true, was false) is a lot worse than the feedback you get if you're asserting equality (expecting x,y,z but got x,y).  When stuff goes wrong you want to know what values were being asserted against and often assertTrue hides that.  From your comments, it looks like you may have had messages which might have been better...

The hole in your tests

You don't actually check that the flags you're producing are the flags for the input.  So, I could replace your code with the following:

public static void dutchFlag(int[] input, int mid) {
    for(int i = 0; i < input.length;i++) {
        input[i] = mid;
    }
}

Even though this code is clearly wrong (since it's essentially a whitewash), all of your tests would pass.  I think your tests would actually be more expressive (and more reliable) if instead, you had three utility functions... findRed, findWhite and findBlue.  These would take in the generated flag and return an array of the numbers to the left of mid, equal to mid, to the right of mid.  So, findRed might look something like this:

private int[] findRed(int[]flag, int mid) {
    for(int index = 0; index < flag.length; index++) {
        if(flag[index] >= mid) {
            return Arrays.copyOfRange(flag, 0, index);
        }
    }
    return flag;
}

A test using it, might then look like:

@Test
public void testDutchWithoutMids() {
    int[] input = {12, 34, 781, -1};
    int mid = 90;

    FlagSorts.dutchFlag(input, mid);

    assertThat(findRed(input, mid)).containsExactlyInAnyOrder(12, 34, -1);
    assertThat(findWhite(input, mid)).isEmpty();
    assertThat(findBlue(input, mid)).containsExactlyInAnyOrder(781);
}

This validates that the flag sections actually contain the numbers that you're expecting them to and if there's any errors you get told what the expected values were and what the actual values are.  Note, I'm using AssertJ for my assertions.


Avoid duplicated += -= operator code In C++ (and C++11), classes defining a + and += operators often define a - and -= operators that do nearly the same thing (except + is replaced with - in the function).

What is the best way to avoid duplicated code here (and still achieve good performance)? I am sure there is a good way to do it with functors:

Here's what I've tried:

#include <iostream>
#include <functional>

struct num {
  int val;

  const num & operator +=(const num & rhs) {
    return op_equals<std::plus<int> >(rhs);
  }
  const num & operator -=(const num & rhs) {
    return op_equals<std::minus<int> >(rhs);
  }

  template <typename op>
  const num & op_equals(const num & rhs) {
    op operation;
    val = operation(val, rhs.val);
    return *this;
  }
};

int main() {
  num x{1};
  num y{2};
  x += y;

  std::cout << x.val << std::endl;
  return 0;
}

Note that this is a simple example; in reality the code in the += and -= operators is more complex.

Also, I am not married to functors in the solution-- any suggestions or advice?

I actually quite like this pattern and use it relatively often. I'm not sure if there is something better than functors for this - if there is, I'm not really aware of it. That being said, with C++11, I'd write this in a slightly different way:

struct num {
  int val;

  const num& operator +=(const num & rhs) {
    return op_equals(rhs, std::plus<int>());
  }

  const num& operator -=(const num & rhs) {
    return op_equals(rhs, std::minus<int>());
  }

  template <typename op>
  const num & op_equals(const num & rhs, op&& o) {
    val = o(val, rhs.val);
    return *this;
  }
};

Note the rvalue reference (which is actually a "universal reference", so can bind to either an lvalue or rvalue reference), and the movement of op to a parameter - I don't really like having to specify it as a template parameter which then gets instantiated and called in the function. I think this way is slightly cleaner.


An integer is even subset of another integer An integer m is defined to be an even subset of another integer n if every even factor of m is also a factor of n.

18 is an even subset of 12 because the even factors of 18 are 2 and 6 and these are both factors of 12.
But 18 is not an even subset of 32 because 6 is not a factor of 32.

I wrote the following code to check for even subsets.

public class EvenSubset {
public static void main(String args[]) {
    System.out.println("The result is: " + isEvenSubset(18, 32));
}
public static boolean isEvenSubset(int m, int n) {
    boolean status = false;
    int firstNumber = 0;
    int secondNumber = 0;
    for(int i = 2; i < m ; i++) {
        if(( m % i == 0) && (i % 2 == 0)) {
            firstNumber = i;
            for(int j  = 2;  j < n ; j++) {
                if( (n % j == 0) && (j % 2 == 0)){
                    secondNumber = j;
                    if(firstNumber == secondNumber) {
                        status = true;
                        break;
                    } else {
                        status = false;

                    }
                }

        }
       if(!status){
           status = false;
       }

    }

}
    return status;
}
 }

I thought that this coding style looked familiar… and indeed it is.  As I previously remarked, flag variables suck.  You shouldn't need a variable like status.

You also don't need firstNumber and secondNumber.  They are just the same as i and j, respectively.

In fact, the whole algorithm can be implemented more simply, just translating the problem description directly into code.  Iterate through the possible even factors of m.  If you find a candidate that is a factor of m but isn't a factor of n, then you can conclude that m is not an even subset of n.

public static boolean isEvenSubset(int m, int n) {
    for (int evenFactor = 2; evenFactor < m; evenFactor += 2) {
        if ((m % evenFactor == 0) && (n % evenFactor != 0)) {
            return false;
        }
    }
    return true;
}

However, there is an optimization that we can do, since factors always occur in pairs.  There is also a quick test we can do to immediately detect an obvious result, if m is odd.

public static boolean isEvenSubset(int m, int n) {
    // Optional optimization: m has no even factors
    if (m % 2 != 0) return true;

    int sqrtM = (int)(Math.sqrt(m) + 1);
    for (int evenFactor = 2; evenFactor <= sqrtM; evenFactor += 2) {
        if (m % evenFactor == 0) {
            if (n % evenFactor != 0) {
                return false;
            }
            int otherFactor = m / evenFactor;
            if ((otherFactor % 2 == 0) && (n % otherFactor != 0)) {
                return false;
            }
        }
    }
    return true;
}


Send message with SignalR to client(s) from injected (IoC) method I am new with SignalR and still a newbie with IoC Container SimpleInjector and I am wondering if there are any side effects and/or if I'm save with my chosen approach.

In my web app I have a SetupHub that invokes a method on an object resolved with SimpleInjector. This method may do anything that I'm not aware about. Maybe it contains Tasks and it may consume x units of time.

During this Setup process I want to inform the client of the progress. This is my current implementation and it works fine:

public class SetupHub : Hub
{
    public void Start()
    {
        // My SimpleInjector resolve wrapper
        IocContainer.Instance.GetInstance<ISetup>().Start(UpdateProgress);
    }

    private void UpdateProgress(double percentage)
    {
        Clients.Caller.updateProgress(percentage);
    }
}

public class Setup : ISetup
{
    public void Start(Action<double> updateProgress)
    {
        Task.Factory.StartNew(() =>
                              {
                                  updateProgress(10); // Bogus progress
                                  Thread.Sleep(100);  // Simulate x units of time
                                  CreateRoles();
                                  updateProgress(25);
                                  Thread.Sleep(400);
                                  CreateUsers();
                                  updateProgress(60);
                                  Thread.Sleep(200);
                                  CreateRelations();
                                  updateProgress(100);
                                  //CreateRelationGroups();
                              });
    }
}

public interface ISetup
{
    void Start(Action<double> updateProgress);
}

Currently, your setup doesn't allow for any cancellation or error handling. The latter is an implementation detail, so I guess you've handled that in the actual code. I would consider the following:

Return the started task out of Start
Will you ever need to provide a result from the started task? If so, provide an overload for Func<double,T>
Provide cancellation support via a cancellation token (if business logic dictates this is acceptable)
Provide a Stop method that also that can stop the task created by Start


Docker script to set up a Python development environment with some Git projects I've create a Docker script momodock.script that does some installation for a set of tools that I'll need to install on multiple machines:

FROM ubuntu:latest
MAINTAINER Momo <mo@mo.com>
LABEL description="TL;DR instructions to install Moses with Docker."
RUN apt-get update
RUN apt-get install -y apt-utils debconf-utils
RUN echo 'debconf debconf/frontend select Noninteractive' | debconf-set-selections
RUN apt-get update
RUN apt-get -y upgrade
RUN apt-get install -y sudo nano
RUN apt-get install -y perl
RUN apt-get install -y python-dev python3-dev python-pip python3-pip
RUN apt-get install -y libboost-all-dev
RUN apt-get install -y build-essential git-core pkg-config automake libtool wget zlib1g-dev python-dev libbz2-dev
RUN apt-get install -y cmake
RUN useradd -m -p mosesdocker -s /bin/bash ubiwan
RUN usermod -aG sudo ubiwan  # add user to sudo list
USER ubiwan
ENV HOME /home/ubiwan
WORKDIR $HOME
CMD /bin/bash
RUN cd $HOME
RUN git clone https://github.com/moses-smt/mosesdecoder.git
WORKDIR $HOME/mosesdecoder
RUN make -f $HOME/mosesdecoder/contrib/Makefiles/install-dependencies.gmake
RUN ./compile.sh  --max-kenlm-order=20 --max-factors=1000
WORKDIR $HOME
RUN git clone https://github.com/moses-smt/mgiza.git
WORKDIR $HOME/mgiza/mgizapp
RUN cmake .
RUN make
RUN make install
RUN cp $HOME/mgiza/mgizapp/scripts/merge_alignment.py bin/
WORKDIR $HOME
RUN git clone https://github.com/jonsafari/clustercat.git
WORKDIR $HOME/clustercat
RUN make -j 4
WORKDIR $HOME
RUN mkdir moses-training-tools
RUN cp mgiza/mgizapp/bin/* moses-training-tools/
RUN cp clustercat/bin/clustercat moses-training-tools/
RUN cp clustercat/bin/mkcls moses-training-tools/mkcls-clustercat
RUN mv moses-training-tools/mkcls moses-training-tools/mkcls-original
RUN cp moses-training-tools/mkcls-clustercat moses-training-tools/mkcls

And building it works smoothly:

docker build -t momo-docker.image - < momodock.script

But I've written the script like how one would emulate a human in the interactive docker environment.

Are there ways to simplify how I'm installing the required dependencies and software?

First off, a little theory. Docker uses most of its RUN commands very similar to what git is doing with commits. That said it makes sense to put RUN commands together that change the state of the image.

By the way, just like in git you can also go back any step in Docker.

According to the Dockerfile reference on RUN the string after RUN is appended to /bin/sh -c on Linux. This means you can chain commands using the usual semicolon (;) and double ampersand (&&) operators. Example:
RUN cmake . && make && make install

Hint: The difference between the semicolon and double ampersand is that a semicolon only separates commands on one line whereas the
latter will run the righthand side command only if the lefthand side
is successful.

Additionally commands like apt-get install allow you to install multiple packages at once, which you actually used a few times already:
RUN apt-get install pkg1 pkg2 pkg3

If the lines get too long, you can use the backslash character (\) at the end of a line to mark a line break. Example:
RUN apt-get install pkg1 pkg2 \
pkg3 pkg4 pkg5

Another way to optimise the image is getting rid of the copy statements and use symlinks instead
Aside from that your Docker file looks good.
If you expect to have variations of the process anytime in the future, consider splitting it into a base image and specialized images that rely on the base.


Selecting control class in a document assembler I feel like there is a cleaner/simpler way of doing the following. Is there an existing software pattern that I should be using?

I have an Assembler class that I use to assemble/process content rules MS-Word documents.

There are many different types of Controls that are processed:

ClearCellIf
DeleteColumnIf
DeleteLineIf
DeleteRowIf
RepeatingControl

The controls fall into two categories:

Generic controls (used over and over)
Custom controls (only used in a specific solution)

Each control extends a base PrecedentControl class and has a Test and a Process method:

class DeleteRowIf : PrecedentControl
{
    public DeleteRowIf(Wd.ContentControl control) : base(control) { }

    public static bool Test(Wd.ContentControl control, PrecedentInstruction Instruction)
    {
        return Instruction != null && Instruction.Command == "DeleteRowIf";
    }

    public override void Process<T>(T data, ref bool Cancel)
    {
        var result = PrecedentExpression1.Resolve(control.GetPrecedentInstruction().Expression, data);
        if (result)
            control.DeleteRow();
    }
}

The bit that I hate, and would like to do better, is the logic that determines which type of control is in use:

public static PrecedentControl AsPrecedentControl(this Wd.ContentControl control)
{
    var instruction = control.GetPrecedentInstruction();
    if (FormatVariable.Test(control, instruction))
        return new FormatVariable(control);
    else if (Optional.Test(control, instruction))
        return new Optional(control);
    else if (DeleteControlIf.Test(control, instruction))
        return new DeleteControlIf(control);
    else if (DeleteControlIf_AndPreviousSpace.Test(control, instruction))
        return new DeleteControlIf_AndPreviousSpace(control);
    else if (DeleteControlIf_AndSurroundingPunctuation.Test(control, instruction))
        return new DeleteControlIf_AndSurroundingPunctuation(control);
    else if (DeleteLineIf.Test(control, instruction))
        return new DeleteLineIf(control);
    else if (DeleteLineIf_OrRemoveControl.Test(control, instruction))
        return new DeleteLineIf_OrRemoveControl(control);
    else if (DeleteLineIf_AndRepositionBulletEnding.Test(control, instruction))
        return new DeleteLineIf_AndRepositionBulletEnding(control);
    else if (DeleteRowIf.Test(control, instruction))
        return new DeleteRowIf(control);
    else if (DeleteRowIf_OrRemoveControl.Test(control, instruction))
        return new DeleteRowIf_OrRemoveControl(control);
    else if (DeleteColumnIf.Test(control, instruction))
        return new DeleteColumnIf(control);
    else if (ClearCellIf.Test(control, instruction))
        return new ClearCellIf(control);
    else if (RepeatingControl.Test(control, instruction))
        return new RepeatingControl(control);
    else if (RepeatingControl_RemoveLastAnd.Test(control, instruction))
        return new RepeatingControl_RemoveLastAnd(control);
    else if (RepeatingControl_SecondLastHasAnd.Test(control, instruction))
        return new RepeatingControl_SecondLastHasAnd(control);
    else if (RunMacro.Test(control, instruction))
        return new RunMacro(control);
    else if (ContactDelivery.Test(control, instruction))
        return new ContactDelivery(control);
    else if (ContactDelivery_DeleteControlAndPrecedingComma.Test(control, instruction))
        return new ContactDelivery_DeleteControlAndPrecedingComma(control);
    else if (ContactDelivery_MultilineAddress.Test(control, instruction))
        return new ContactDelivery_MultilineAddress(control);
    else
        return null;
}

If all the Test methods look like in the provided sample implementation then I see several approaches to make your factory method cleaner:

Use a switch:

public static class Instructions
{
    public static const string DeleteIf = "DeleteIf";
    public static const string Optional = "Optional";
    ...
}

public static PrecedentControl AsPrecedentControl(this Wd.ContentControl control)
{
    switch (instruction.Command)
    {
        case Instructions.DeleteIf: return new DeleteIf(control);
        case Instructions.Optional: return new Optional(control);
        ...
        default:
            throw new InvalidInstructionException(instruction);
    }
}

Use a data driven approach with a Dictionary:

Dictionary<string, Type> InstructionMap = new Dictionary<string, Type>
{
    { Instructions.DeleteIf, typeof(DeleteIf) },
    { Instructions.Optional, typeof(Optional) },
    ...
}

And your factory method being:

public static PrecedentControl AsPrecedentControl(this Wd.ContentControl control)
{
    Type instructionType = null;
    if (InstructionMap.TryGet(instruction.Command, out instructionType))
    {
        return Activator.CreateInstanceOf(instructionType, control);
    }
    throw new InvalidInstructionException(instruction);
}

If by convention the instruction commands are all named the exact same as the corresponding classes dealing with them you can build the dictionary dynamically once via reflection by finding all the types deriving from PrecedentControl. Something along these lines might work:

typeof(PrecedentControl).Assembly
                        .GetTypes()
                        .Where(t => !t.IsAbstract && typeof(PrecedentControl).IsAssignableFrom(t))
                        .ToDictionary(t => t.Name, t => t);


My own implementation of Linq SelectMany extension method What do you think of my own implementation of the extension method SelectMany?
Motivating criticism is always welcome.

public static IEnumerable<TResult> MySelectMany<T, TResult>(this IEnumerable<T> source, Func<T, IEnumerable<TResult>> selector)
{
    var theList = new List<TResult>();

    foreach (T item in source)
    {
        foreach (TResult inneritem in selector(item))
        {
            theList.Add(inneritem);
        }
    }

    return theList as IEnumerable<TResult>;
}

The as cast in the return statement is entirely redundant, it doesn’t serve a purpose.

Furthermore, The problem with this implementation is that it’s not lazy. You should use a yield generator instead.

public static IEnumerable<TResult> MySelectMany<T, TResult>(this IEnumerable<T> source, Func<T, IEnumerable<TResult>> selector)
{
    foreach (T item in source)
        foreach (TResult inneritem in selector(item))
            yield return inneritem;
}

If C# already had a yield from statement, this would be even shorter since you wouldn’t need to iterate the inner items explicitly.


Checking if a number is divisible by 2-11 I am writing a Python class which checks if a given number is divisible by numbers 2-11. I am not using the __init__ method which in my opinion is not necessary in this case.

Questions:

How can I convert a given number in to abs(x) without using the __init__ method in every method at once?
How can I check if a number is divisible by 7 without using a recursive solution?

class Divisibility:
    """
    Program checks if given number is divisible
    by any number from 2 to 11
    """

    # Divisibe by 2 if last digit is divisible by 2
    def divisible_by_2(self, number):
        number = abs(number)
        if (number % 10) % 2 == 0:
            return True
        else:
            return False

    # Divisible by 3 if sum of its digits is divisible by 3
    def divisible_by_3(self, number):
        number = abs(number)
        n = number

        s = 0
        while n:
            s, n = s + n % 10, n // 10

        if s % 3 == 0:
            return True
        else:
            return False

    # Divisible by 4 if last two digits is divisible by 4
    def divisible_by_4(self, number):
        number = abs(number)
        if (number % 100) % 4 == 0:
            return True
        else:
            return False

    # Divisible by 5 if last digit is either 5 or 0
    def divisible_by_5(self, number):
        number = abs(number)
        if number % 10 == 0 or number % 10 == 5:
            return True
        else:
            return False

    # Divisible by 6 if number is divisible by 2 and 3
    def divisible_by_6(self, number):
        number = abs(number)
        if self.divisible_by_2(number) and self.divisible_by_3(number):
            return True
        else:
            return False

    def divisible_by_7(self, number):
        number = abs(number)
        if number % 7 == 0:
            return True
        else:
            return False

    # Divisible by 8 if last three digits is divisible by 8
    def divisible_by_8(self, number):
        number = abs(number)
        if (number % 1000) % 8 == 0:
            return True
        else:
            return False

    # Divisible by 9 if the sum of its digits is divisible by 9
    def divisible_by_9(self, number):
        number = abs(number)
        s = 0
        while number:
            s, number = s + number % 10, number // 10

        if s % 3 == 0:
            return True
        else:
            return False

    # Divisible by 10 if last digit is 0
    def divisible_by_10(self, number):
        number = abs(number)
        if number % 10 == 0:
            return True
        else:
            return False

    # Divisible by 11 if the difference between
    # the sum of numbers at even possitions and odd
    # possitions is divisible by 11
    def divisible_by_11(self, number):
        number = abs(number)
        n = number
        nn = number // 10
        total = 0

        while n:
            total += n % 10
            n //= 100

        while nn:
            total -= nn % 10
            nn //= 100

        if abs(total) % 11 == 0:
            return True
        else:
            return False

if __name__ == '__main__':

    D = Divisibility()
    print(D.divisible_by_2(-6))
    print(D.divisible_by_3(6))
    print(D.divisible_by_4(6))
    print(D.divisible_by_5(60))
    print(D.divisible_by_6(6))
    print(D.divisible_by_7(616))
    print(D.divisible_by_8(82453))
    print(D.divisible_by_9(9512244))
    print(D.divisible_by_10(-571288441))
    print(D.divisible_by_11(121))

You do this quite alot

if s % 3 == 0:
    return True
else:
    return False

Instead you could return directly

return s % 3 == 0