Covering array scraper and sorter A covering array is an \$N \times k\$ array in which each element is a from a set of \$v\$ symbols, and for every \$t\$ columns, every possible set of \$v^t\$ choices of the symbols appears at least once. The covering array number \$\mathrm{CA}(t,k,v)\$ is the smallest \$N\$ for which a covering array exists, given \$t\$, \$k\$, and \$v\$. A list of known covering array numbers (CANs) is available here.

I want to parse all of the known CANs from these pages and to find how "efficient" they are—what I mean by this is the ratio of \$\mathrm{CA}(t,k,v)\$ compared to \$v^t\$.

I developed Python code that access every covering array page, and parses the tables. I then sort the list of covering arrays by this ratio, and plot it using matplotlib.pyplot (using a log-scale for the y axis).

from urllib.request import urlopen
from bs4 import BeautifulSoup
import matplotlib.pyplot as plt

# covering array object
class CAElement:
    def __init__(self, N, t, k, v):
        self.N = N
        self.t = t
        self.k = k
        self.v = v
    def set_ratio(self, ratio):
        self.ratio = ratio
    def __str__(self):
        return "CA(N=%d; t=%d, k=%d, v=%d) -> %f" % (self.N, self.t, self.k, self.v, self.ratio)

CAArray = []

# iterate over v, t in the known table ranges
for v in range(2, 26):
    for t in range(2, 7):
        # download the webpage and find the elements
        url = "http://www.public.asu.edu/~ccolbou/src/tabby/%d-%d-ca.html" % (t, v)
        response = urlopen(url)
        soup = BeautifulSoup(response)
        tables = soup.findChildren('table')
        table = tables[0]
        rows = table.findChildren('tr')

        # iterate over all rows in the one table
        for row in rows:
            cells = row.findChildren('td') # has all of the table's elements
            elements = []
            for cell in cells:
                value = cell.string
                if value is not None and value != "k" and value != "N" and value != "Source":
                        elements.append(value)
            if len(elements) >= 2:
                kParsed = int(elements[0])
                NParsed = int(elements[1])
                element = CAElement(NParsed, t, kParsed, v)
                ratio = element.N / pow(element.v, element.t)
                element.set_ratio(ratio)
                CAArray.append(element)

# sort by N/(v^t)
CAArray.sort(key=lambda x: (x.ratio, x.N, x.v, x.t, x.k), reverse=True)

# print each element (in sorted order)
for element in CAArray:
    print(element)

# plotting - using log scale for y axis
# each point is colored according to t (i.e., the "strength" of the CA)
xs = range(0, len(CAArray))
ys = [y.ratio for y in CAArray]
colors = {2:"red", 3:"blue", 4:"green", 5:"yellow", 6:"orange"}
plt.scatter(xs, ys, c=[colors[x.t] for x in CAArray])
plt.axis([min(xs), max(xs), min(ys), max(ys)])
plt.yscale('log')
plt.show()

This code does exactly what I want it to do. However, there are some problems:

Accessing the webpages is somewhat slow, and could be faster.
The code does not seem very Pythonic (and by making it so could make iterating over the array much faster).

Any suggestions are welcome!

Here are some of the quick performance wins you may get:

switch to using requests and reuse a Session instance which should provide a performance boost:

  if you're making several requests to the same host, the underlying TCP
  connection will be reused, which can result in a significant
  performance increase (see HTTP persistent connection).

import requests

session = requests.Session()

# iterate over v, t in the known table ranges
for v in range(2, 26):
    for t in range(2, 7):
        # download the webpage and find the elements
        url = "http://www.public.asu.edu/~ccolbou/src/tabby/%d-%d-ca.html" % (t, v)
        response = session.get(url)

use the fastest available underlying parser - lxml (requires to install lxml):

soup = BeautifulSoup(response, 'lxml')

parse only table elements from a page source via SoupStrainer:

parse_only = SoupStrainer('table')
soup = BeautifulSoup(response, 'lxml', parse_only=parse_only)

Requires importing SoupStrainer from bs4.

And, applying some bs4 related shortcuts, the HTML parsing part would transform into:

table = soup.table
for row in table('tr'):
    elements = []
    for cell in row('td'):
        value = cell.string
        if value is not None and value not in ("k", "N", "Source"):
            elements.append(value)


ChunkerTransformStream, a transform stream to take arbitrary chunk sizes and make them consistent I have some code to interface with a wire protocol that requires data to be inserted into a stream at regular byte intervals.  Every 8KB (or at some other definable interval), a small chunk will be inserted.  To make this easy, I decided to create a transform stream that would take a flowing stream and write fixed chunk sizes.  That is, this stream can be written to in any size (2KB here, 500KB there, 5 bytes next, etc.) and it will output chunks in 8KB of size every time.

var stream = require('stream');
function ChunkerTransformStream (chunkSize) {
    chunkSize = chunkSize || 8192;

    var buffer = new Buffer(0);

    var chunker = new stream.Transform({objectMode: true});
    chunker._transform = function (chunk, encoding, done) {
        buffer = Buffer.concat([buffer, chunk]);

        while (buffer.length >= chunkSize) {
            this.push(buffer.slice(0, chunkSize));
            buffer = buffer.slice(chunkSize);
        }

        done();
    }

    chunker._flush = function (done) {
        if (buffer.length) {
            this.push(buffer);
            done();
        }
    }

    return chunker;
}

module.exports = ChunkerTransformStream;

This transform stream will be used heavily in my code, having several megabit pushed through it per second.  Is this the most efficient way to achieve what I want?  I am most concerned about my buffer operations.  It's my understanding that Buffer.concat() is very expensive, as it allocates an entirely new buffer and copies the first two to it.

Any feedback, on performance or otherwise, is welcomed.

First of all, your code looks great. It brought me to study the internal workings of Node's stream API.

The piece that you're concerned with, and rightfully so, is:

buffer = Buffer.concat([buffer, chunk]);

That's the way to do it. There are no other ways to do what you want to do without using bufferjs, which likely handles things the same way, or less efficiently.

Now, there is one optimization you can make here. By adding the totalLength parameter of Buffer.concat Buffer.concat(list, [totalLength]) you can improve efficiency by avoiding an additional loop in the function, which would need to check the new length of the new buffer.

    Name         Description                                       Required?    Type
    list         List of Buffer objects to concat                  Required     array
    totalLength  Total length of the buffers when concatenated.    Optional     number

  If totalLength is not provided, it is read from the buffers in the
  list. However, this adds an additional loop to the function, so it is
  faster to provide the length explicitly. - See more at:
  http://www.w3resource.com/node.js/nodejs-buffer.php#sthash.qISHPlCO.dpuf

Not sure if this will help or not, but other than that, I don't see any possible optimizations.


Convert Lua UINT to hh:mm:ss I have found the convert_to function in the lua-user wiki, and I created the convert_to_time function which does what I want it to do. Which is, basically: Having a number, return its value in a Time format.

The values range is:  [0..863999] as we want the data in 0..24 hours format by step of 0.1 second.

The code from the lua-user-wiki, had a step of 1 second so I had to change the base to fit my specifications, but because of that I've had to create too many conditions to be able to always print out the value I want. I had issues with printing 01:00:00 for example.

If someone of you can give it a view and suggest me a simpler way to achieve what I want in ALL situations I would appreciate it.

intervals={
 {"seconds",1}, --the "1" should never really get used but
 {"minutes",60},
 {"hours",60},
 {"days",24},
}

positions={}
for i=1,4 do
 positions[intervals[i][1]]=i
end

function convert_to(value, sourceunits, targetunits)

local sourcei, targeti = positions[sourceunits], positions[targetunits]
assert(sourcei and targeti)

if sourcei<targeti then

  local base=10
  for i=sourcei+1,targeti do
    base=base*intervals[i][2]
  end

  return value/base

elseif sourcei>targeti then

  local base=10
  for i=targeti+1,sourcei do
    base=base*intervals[i][2]
  end

  return value*base
else return value end
end

function convert_to_time(value)
  local returnString = "", horas, minutos, segundos

  horas = tostring(convert_to(value,"seconds","hours")) -- return : 12.888888889
  if(tonumber(string.match(horas, "%.(%w+)"))==nil) then return (horas ..":00:00") end
  minutos = tostring(convert_to("0."..string.match(horas, "%.(%w+)"),"hours","minutes")/10) -- returns : 53.33333334
  if(tonumber(string.match(minutos, "%.(%w+)"))==nil) then return (string.match(horas, "(%w+)%.") .. minutos ..":00") end
  segundos = tostring(convert_to("0."..string.match(minutos, "%.(%w+)"),"minutes","seconds")/10) -- returns : 20.0000000004

  horasStr = string.match(horas, "(%w+)%.")
  minutosStr = string.match(minutos, "(%w+)%.")
  if string.match(segundos, "%.") then
    segundosStr = string.match(segundos, "(%w+)%.")
  else
  segundosStr = segundos
  end

  -- Ñapa para que los numeros se vean en formato hh:mm:ss
  if (tonumber(horasStr) < 10) then if (tonumber(horasStr)==nil) then horasStr = "00" end horasStr = "0"..horasStr end
  if (tonumber(minutosStr) < 10) then if (tonumber(minutosStr)==nil) then minutosStr = "00" end minutosStr = "0"..minutosStr end
  if (tonumber(segundosStr) < 10) then if (tonumber(segundosStr)==nil) then segundosStr = "00" end segundosStr = "0"..segundosStr end

  returnString = horasStr .. ":" .. minutosStr .. ":" .. segundosStr

  return returnString

 end

You can test the code for this example:

print(convert_to_time(36000))

A much simpler way is:

function convert_to_time(tenths)
  local hh = (tenths // (60 * 60 * 10)) % 24
  local mm = (tenths // (60 * 10)) % 60
  local ss = (tenths // 10) % 60
  local t = tenths % 10

  return string.format("%02d:%02d:%02d.%01d", hh, mm, ss, t)
end


Porting a web-based POS system to Android I'm currently porting a web-based POS system to Android. The Android version uses NavigationDrawer to navigate between menus.

What I need a code review on is my current approach in loading fragments upon selected an item from navigation drawer. I'm using reflection to achieve my case.

MainActivity.java

@Override
    public void onNavigationDrawerItemSelected(String menuItemText) {
        FragmentManager fragmentManager = getSupportFragmentManager();
        BaseFragment fragmentToOpen = null;
        Method newInstanceMethod = null;
        try {
            newInstanceMethod = AvailableMenuList.MENU_ITEM_TABLE.get(menuItemText).getMethod("newInstance", null);
            fragmentToOpen = (BaseFragment) newInstanceMethod.invoke(fragmentToOpen, null);
        } catch (Exception e) {
            e.printStackTrace();
        }

        fragmentManager.beginTransaction()
                .replace(R.id.container, fragmentToOpen, menuItemText)
                .addToBackStack(menuItemText)
                .commit();
    }

HashMap implementation of available POS functions in Android version:

    public class AvailableMenuList {
        private AvailableMenuList() {} //Disable object instantiation

            public static final HashMap<String, Class<BaseFragment>> MENU_ITEM_TABLE = new HashMap() {{
                put("Announcement", AnnouncementListFragment.class);
                put("Board", BoardListFragment.class);
                put("SalesRegistration", SalesRegFragment.class);
                put("SalesRecords", SalesRtvFragment.class);
                put("OrderRegistration", OrderRegFragment.class);
                put("OrderRecords", OrderRtvFragment.class);
            }};
        }
    }

Is there a better approach of instantiating a new Fragment (by calling newInstance) instead of using reflection? Currently, there's only 6 functionalities but there's going to be at least 30 more in the future.

You can use fragmentManager.findFragmentByTag() instead.

If the fragment is not found, initalize a new one.

fragment = new YourFragment();


TodoItem component type checking for optional prop I have a TodoItem component that looks like this:
type Todo = {
  id: string;
  text: string;
  isCompleted: boolean;
  createdAt: string;
};

type TodoProps = {
  todo: Todo;
  removeTodo: (id: string) => void;
  markCompletedTodo?: (id: string) => void;
};

const TodoItem = ({ todo, removeTodo, markCompletedTodo }: TodoProps) => {
  return (

{todo.text}

      <button type="button" onClick={() => removeTodo(todo.id)}>
        Remove
      </button>
      {typeof markCompletedTodo === 'undefined' ? null : (
        <button type="button" onClick={() => markCompletedTodo(todo.id)}>
          Mark completed
        </button>
      )}

  );
};

export default TodoItem;

As you can see, it gets a todo with a isCompleted property. I want to render the 'Mark completed' button only is the isCompleted property is false, but currently I'm checking for the optional markCompletedTodo prop. That works but I have the feeling this can be done in a better way.
I'm using it to create two lists of TODOS, one for incomplete TODOS and one for complete TODOS, so I'm using it like this in another component:
return (

Incomplete TODOS

  {incompleteTodos.map((todo) => (
    <TodoItem
    key={todo.text}
    todo={todo}
    removeTodo={removeTodoRequest}
    markCompletedTodo={markCompletedTodoRequest}
    />
  ))}

Complete TODOS

  {completeTodos.map((todo) => (
    <TodoItem
      key={todo.text}
      todo={todo}
      removeTodo={removeTodoRequest}
    />
  ))}
)

Is there a better approach to this regarding the type checking and the prop types in the TodoItem component, or any other aspect?

Make the shapes the same In my experience, TypeScript is easiest when similar data has the same shape (type). Rather than conditionally passing a markCompletedTodo, consider passing that prop unconditionally, and in the child component, check todo.isCompleted when you need to identify whether to add the button or not.
Duplicate key bug You use:
{incompleteTodos.map((todo) => (
  <TodoItem
  key={todo.text}

What if the todo text is the same? Maybe someone adds "Get groceries" Tuesday, then comes back to the app on Thursday and adds "Get groceries" again for the next week. This means that you'll have duplicate mapped keys, which should not be done and will confuse React, possibly creating rendering problems.
Since it looks like todos have IDs, use those IDs as keys instead.
&& instead of conditional To conditionally render in React, you can use && or || to test, and put the element to be rendered on the right-hand side - it's a bit more concise than the conditional operator.
You could do something like:
// You could rename the definition of removeTodoRequest to removeTodo
// and markCompletedTodoRequest to markCompletedTodo
// so that you can use shorthand property names below:
const makeTodoItem = (todo: Todo) => (
  <TodoItem
    key={todo.id}
    {...{ todo, removeTodo, markCompletedTodo }}
  />
);
return (

Incomplete TODOS

  {incompleteTodos.map(makeTodoItem)}

Complete TODOS

  {completeTodos.map(makeTodoItem)}
); // don't forget this semicolon

type TodoProps = {
  todo: Todo;
  removeTodo: (id: string) => void;
  markCompletedTodo: (id: string) => void;
};

const TodoItem = ({ todo, removeTodo, markCompletedTodo }: TodoProps) => {
  return (

{todo.text}

      <button type="button" onClick={() => removeTodo(todo.id)}>
        Remove
      </button>
      {!todo.isCompleted && (
        <button type="button" onClick={() => markCompletedTodo(todo.id)}>
          Mark completed
        </button>
      )}

  );
};


Welford's online variance calculation algorithm for vectors I'm developing a face recognizing application using the face_recognition Python library.

The faces are encoded as 128-dimension floating-point vectors. In addition to this, each named known person has a variance value, which is refined iteratively for each new shot of the face along with the mean vector. I took the refining formula from Wikipedia.

I'm getting some false positives with the recognized faces, which I presume is because the library was developed primarily for Western faces whereas my intended audience are primarily Southern-Eastern Asian. So my primary concern with my code, is about whether or not I had gotten the mathematics correct.

Here's my refining algorithm in Python

import sys
from functools import reduce
from math import hypot

# fake testing data.

# new reference face.
refenc = (0.2, 0.25, 0.4, 0.5) * 32

# previous face encoding and auxiliary info.
baseenc = (0.2, 0.3, 0.4, 0.5) * 32
v = 0.01         # variance
n = 3            # current iteration

n = min(n, 28)   # heuristically limited to 28.

vnorm = lambda v: reduce(hypot, v)
vdiff = lambda u, v: list(map(lambda s,t:s-t, u, v))

delta1 = vdiff(refenc, baseenc)
if( vnorm(delta1) > 0.4375 and n > 1 ):
    sys.exit() # possibly selected wrong face.
    pass
newenc = [ baseenc[i] + delta1[i] / n for i in range(128) ]

delta2 = vdiff(delta1, newenc)
v = v*(n-1)/n + vnorm(delta1)*vnorm(delta2)/n

print(repr((newenc, v, n)))

Irrelevant note
: I used struct.(un)pack to serialize in binary to save space, because the repr of the data is too big.

I can't say I understand exactly what your algorithm does. Even when looking at Wikipedia it is hard to see. So, why don't you just use the reference implementation from there? It has functions with nice names and everything (well, not quite PEP8 compatible, but that could be changed).
Alternatively, once you have vectors of numbers and want to perform fast calculations on them, you probably want to use numpy, which allows you to easily perform some operation on the whole vector, like taking the difference between two vectors, scaling a vector by a scalar, taking the sum, etc.
import numpy as np

MAGIC_CUTOFF = 0.4375

class WrongFaceException(Exception):
    pass

def norm(x):
    return np.sqrt((x**2).sum())

def update(base_encoding, new_face_encoding, v, n):
    delta1 = new_face_encoding - base_encoding
    if norm(delta1) > MAGIC_CUTOFF and n > 1:
        raise WrongFaceException(f"norm(delta1) = {norm(delta1)} > {MAGIC_CUTOFF}")
    new_encoding = base_encoding + delta1 / n
    delta2 = delta1 - new_encoding
    v = v * (n - 1) / n + norm(delta1) * norm(delta2) / n
    return new_encoding, v, n + 1

if __name__ == "__main__":
    new_face_encoding = np.array((0.2, 0.25, 0.4, 0.5) * 32)
    base_encoding = np.array((0.2, 0.3, 0.4, 0.5) * 32)
    v = 0.01
    n = 3

    updated_encoding, v, n = update(base_encoding, new_face_encoding, v, n)
    print(updated_encoding, v, n)

In addition to using numpy, I expanded some of the names so it is clearer what they are, I made the cutoff value a global constant (you should give it a meaningful name), added a custom exception instead of just dying (the pass after it was unneeded and unreachable BTW), which makes it more clear what happened, wrapped the calling code under a if __name__ == "__main__": guard to allow importing from this script without running it and followed Python's official style-guide, PEP8, by having operators surrounded by one space.
Instead of this norm function, you can also use scipy.linalg.norm, which might be even faster.

To answer if you used the math correctly, I would say partially yes. It looks like you implemented the explicit formula given for the sample variance:
\$\sigma^2_n = \frac{(n - 1)\sigma^2_{n-1} + (x_n - \bar{x}_{n-1})(x_n - \bar{x}_n)}{n}\$
However, note that Wikipedia also mentions that this formula suffers from numerical instabilities, since you "repeatedly subtract a small number from a big number which scales with \$n\$".
Instead you want to keep the sum of the squared differences \$M_{2,n} = \sum_{i=1}^n (x_i - \bar{x}_n)^2\$ around and update that:
\$M_{2,n} = M_{2,n-1} + (x_n - \bar{x}_{n-1})(x_n - \bar{x}_n)\$
with
\$\bar{x}_n = \bar{x}_{n -1} + \frac{x_n - \bar{x}_{n-1}}{n}\$
Then the new population variance is given simply by:
\$\sigma^2_n = \frac{M_{2,n}}{n - 1}\$
This is a bit tricky to implement, since your \$x_i\$ are actually vectors of numbers, so you would need to find out how to properly reduce it in dimension (in your previous formula you used the norm for that).


Free a binary tree without using recursion or allocating memory As the title says, the objective is to free a binary tree without using the stack or allocating memory.
This was required for a kernel module where resources were limited.

Result has a complexity of \$ O \left( n \right) \$.

template<typename T>
struct Node
{
    T     data;
    Node* left;
    Node* right;
};

// Utility function to find the bottom left
// Of the tree (because that has a NULL left
// pointer that we can use to store information.
Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

void freeTree(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.
    Node* bottomLeft    = findBottomLeft(t);

    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        delete old;
    }
}

function missing templates

I'm sure you're aware, but the functions need the same templating as the Node such that void freeTree(Node* t) becomes:

template<typename T>
void freeTree(Node<T>* t)

slight reduction in memory use

You could slightly reduce the stack used by essentially inlining the function call to findBottomLeft.  The rewritten function now looks like this:

template<typename T>
void freeTree(Node<T>* t)
{
    // bl points at the bottom left node.
    // Any right nodes from t are added to the bottom left as we go down.
    // This progressively flattens the tree into a list as we go.
    Node<T> *bl;
    for(bl=t ; bl != nullptr && bl->left != nullptr; bl=bl->left);

    while(t != nullptr)
    {
        // body of for loop deliberately empty
        for (bl->left = t->right; bl != nullptr && bl->left != nullptr; bl=bl->left);
        Node<T>*   old = t;
        // Now just free the curent node
        t = t->left;
        delete old;
    }
}

Note that I'm using nullptr rather than NULL here which is a C++11 feature.  If you're not using a C++11 compliant compiler, you can simply use NULL for each of those instances.

Also, I've eliminated the early return in the case that t was equal to NULL in the original because this case is handled correctly by the for loop and while loop.

It's also important to realize that the body of the for loop is deliberately empty.  Some people dislike having a for loop with just a semicolon at the end, but I think it's not a problem if there is a comment pointing it out.


Adding multiple rows in an HTML table using jQuery I have this function that allows the user to supply a number and that many rows are appended to the existing table:

$('#add-row').click(function() {
    if($('#insert-rows-amnt').val() < 1) {
        alert('Please enter number of rows to insert');
    } else {
        for(i = 1; i <= $('#insert-rows-amnt').val(); i++) {
            $('table tr:last').clone(true).appendTo("tbody");
        }
    }
});

Where #insert-rows-amnt is an input field and in this case contains the number 5000.

This currently takes 48 seconds on my machine to add 5,000 additional rows - is there a quicker way of doing this?

I'm not against putting a loading message somewhere if there isn't a way to significantly increase the speed. I'm just curious if this is the most efficient way.

I'd do it like this:

$('#add-row').click(function() {
  var $tbody, $row, additionalRows;
  var numNewRows = parseInt($('#insert-rows-amnt').val(), 10);

  if (isNaN(numNewRows) || numNewRows <= 0) {
    alert('Please enter number of rows to insert');
  } else {

    $tbody = $('table tbody');
    $row = $tbody.find('tr:last');

    additionalRows = new Array(numNewRows + 1).join($row[0].outerHTML);

    $tbody.append(additionalRows);
  }
});

    Col1
    Col2

      1
      2

<input type="number" id="insert-rows-amnt" />
<button id="add-row" type="button">Add Rows</button>

Firstly, don't trust user input, verify you actually have a number, try to parse it and be explicit. Always use the radix, parseInt() can try to be too clever for its own good. The result could be NaN or a number, so check for these:

var numNewRows = parseInt($('#insert-rows-amnt').val(), 10);

if (isNaN(numNewRows) || numNewRows <= 0) {

If you're using JQuery, cache found objects, finding them isn't free, a search is done every time you pass a string selector, so if you've already found it, use it. This ins't going to set the world on fire, but it's a good habit to get into.

Onto the meat of the method, there are two methods for inserting HTML quickly. HTML updates are like Excel Worksheet updates, no small amount of processing goes on when you change the dom. Most of the time this is negligible, but if you're inserting a huge amount of html it's something to be aware of.

You could create a document fragment and append nodes to it. This gives the benefit of working with objects rather than strings so is less error prone. The essence of it is you create the fragment in memory and insert it once.
You can create the html as a string and insert it, it's a single dom update, but more error prone as you're string building. This case is simple enough for it to be a good option though.

new Array(numNewRows + 1).join($row[0].outerHTML);

This replicates a string x number of times. It works by initialising an array of x dimensions and then joining it using a given string as the text between the elements.


This divides the class of game objects into material and immaterial The fact is that a material object must have a field that does not make sense to an immaterial object

Here is a class whose objects I want to divide into material and immaterial:

public class GameObject {
    protected boolean isHidden;
    protected Coordinate position;
    protected int pictureWidth, pictureHeight;
    public Object filling;

    protected GameObject(int pictureWidth, int pictureHeight, Coordinate position, boolean isHidden, Color filling){
        this.position = position;
        this.pictureWidth = pictureWidth;
        this.pictureHeight = pictureHeight;
        this.isHidden = isHidden;
        this.filling = filling;
    }

    protected GameObject(Coordinate position, boolean isHidden, BufferedImage filling){
        this.position = position;
        this.pictureWidth = filling.getWidth();
        this.pictureHeight = filling.getHeight();
        this.isHidden = isHidden;
        this.filling = filling;
    }

    protected GameObject(GameObject gameObject) throws IOException{
        this.position = new Coordinate(gameObject.getPosition());
        this.pictureWidth = gameObject.getPictureWidth();
        this.pictureHeight = gameObject.getPictureHeight();
        this.isHidden = gameObject.isHidden();
        this.filling = gameObject.getFilling(); // передается ссылка
    }

    private GameObject getGameObject() {
        return this;
    }
    public void paint(Graphics gr) throws IOException{
        if(filling instanceof BufferedImage) {
            gr.drawImage((Image) filling, position.getX(), position.getY(), null);
        }
        else if(filling instanceof Color) {
            gr.setColor((Color) filling);
            gr.fillRect(position.getX(), position.getY(), pictureWidth, pictureHeight);
        } else {
            System.err.println("programmer, you forgot to add a way to draw this object");
        }
    }
    Object getFilling() {
        return filling;
    }

    int getPictureWidth() {
        return pictureWidth;
    }
    int getPictureHeight() {
        return pictureHeight;
    }
    boolean isHidden() {
        return isHidden;
    }
    Coordinate getPosition() {
        return position;
    }
}

I suppose that you need to create 2 classes that inherit GameObject, and make the constructor of the GameObject class visible only for these two classes:

1) class MaterialGameObject:

 public class MaterialGameObject extends GameObject{
    final int materialHeight;

    public MaterialGameObject(int materialHeight, int pictureWidth, int pictureHeight, Coordinate position, boolean isHidden, Color filling){
        super(pictureWidth, pictureHeight, position, isHidden, filling);
        this.materialHeight = materialHeight;
    }

    public MaterialGameObject(int materialHeight, Coordinate position, boolean isHidden, BufferedImage filling){
        super(position, isHidden, filling);
        this.materialHeight = materialHeight;
    }

    public MaterialGameObject(MaterialGameObject materialGameObject) throws IOException{
        super(materialGameObject.getGameObject());
        this.materialHeight = materialGameObject.getMaterialHeight();
    }

    public int getMaterialHeight() {
        return materialHeight;
    }

}

class ImMaterialGameObject:

public class ImMaterialGameObject extends GameObject{

    public ImMaterialGameObject(int pictureWidth, int pictureHeight, int materialHeight, Coordinate position, boolean isHidden, Color filling){
        super(pictureWidth, pictureHeight, position, isHidden, filling);
    }

    public ImMaterialGameObject(Coordinate position, boolean isHidden, BufferedImage filling){
        super(position, isHidden, filling);
    }

    public ImMaterialGameObject(GameObject gameObject) throws IOException{
        super(gameObject);
    }

}

Do you know a better way to solve the problem?

getGameObject - Never used. You should remove it. You can always use this, no need to have a function. If you meant for this to be protected, still remove it. Again use the object, no need to have a function.

ImMaterialGameObject - Unless "Im" stands for something, Immaterial is one word.

public Object filling; - You've obviously noticed all classes in Java extend from Object. Taking advantage of this is hackey. Instead you could use 2 separate fields and check if one or the other is null.

Onto the question "Is there a better approach?"

Without knowing what you're using this for, I'd say there's nothing wrong with your approach. To make things more clear, set GameObject to abstract.


Printing a calendar for a month based on user input I have a long piece of code that has many repeating points. I am sure that it doesn't take this amount of code to create a simple calendar, but I do not know how to shorten this piece of code.

# Creating a calendar in proportion to the user defined starting date

n = int(input('Enter number of days: '))#days in a month
s = input('The first day of the week: ')#The date that user wants the month to start
s = s.capitalize()

lis1 = ['Sa','M','T','W','Th','F','Su']
print('{:>3}{:>4}{:>4}{:>4}{:>4}{:>4}{:>4}'.format('Sa','M','T','W','Th','F','Su'))

for i in range(1,n+1):#loop to generate the dates for a month
  if s==lis1[0] and i ==1:#this is to determine how much should the code indent to align to traditional calendar formatting
    print('{:>3}'.format(i),end =' ')
  elif s==lis1[1] and i ==1:
    print(' '*4+'{:>3}'.format(i),end =' ')
  elif s==lis1[2] and i ==1:
    print(' '*8+'{:>3}'.format(i),end =' ')
  elif s==lis1[3] and i ==1:
    print(' '*12+'{:>3}'.format(i),end =' ')
  elif s==lis1[4] and i ==1:
    print(' '*16+'{:>3}'.format(i),end =' ')
  elif s==lis1[5] and i ==1:
    print(' '*20+'{:>3}'.format(i),end =' ')
  elif s==lis1[6] and i ==1:
    print(' '*24+'{:>3}'.format(i),end =' ')
  else:
    print('{:>3}'.format(i),end =' ')#after the indent this is to print the remaining dates

  if s==lis1[0] and i%7==0:#this is to print a new line in proportion the choosen starting date so as to stay in check with the traditional calendar format
    print()
  elif s==lis1[1] and i%7==6:
    print()
  elif s==lis1[2] and i%7==5:
    print()
  elif s==lis1[3] and i%7==4:
    print()
  elif s==lis1[4] and i%7==3:
    print()
  elif s==lis1[5] and i%7==2:
    print()
  elif s==lis1[6] and i%7==1:
    print()

This is an example of the calendar I am outputting.

Please guide me on shortening code that is related to loops if possible.

First improvement

  don't repeat yourself,  the dry principle

You have many elif statements that can be easily rewritten using a dictionary.

My final program has none at all. I rewrote your lst (also badly named) into a dictionary like this:

weekdays = {'Su':0,'M':1,'T':2,'W':3,'Th':4,'F':5,'Sa':6}

Now weekdays is used on 2 different locations to replace the long elif structure.

First elif block. Notice they all increment by 4. So I can use the value of the dictionary like this: weekdays[first_weekday]*4

Second elif block. Here you can use the same dictionary. Notice how weekdays[first_weekday] + current_day becomes a multitude of 7.

Second Improvement

You should rename the variables in your program to understand what they do. For example n should be renamed to number_of_days

A good way to follow are the PEP8 guidelines

Final Program

As you can see, this program not only is shorter but also far more readable

# I omitted comments because the names speak for themselves
number_of_days = int(input('Enter number of days in month: '))
first_weekday = input('First weekday of the month: ')

# Using a dictionary over a list is the biggest improvement in my opinion
weekdays = {'Su': 0, 'M': 1, 'T': 2, 'W': 3, 'Th': 4, 'F': 5, 'Sa': 6}
print('{:>3}{:>4}{:>4}{:>4}{:>4}{:>4}{:>4}'
      .format('Su', 'M', 'T', 'W', 'Th', 'F', 'Sa'))

# First elif block
print (weekdays[first_weekday]*4*' ' + '{:>3}'.format(1), end=' ')
for current_day in range(1, number_of_days+1):
    # Second elif block
    if (weekdays[first_weekday] + current_day) % 7 == 0:
        print ()
    print ('{:>3}'.format(current_day ), end=' ')


Install a Python package based on active_gpu or version I have the following code, is there a way to optimize it/reduce the code?

  #!/bin/bash

  if [[ "${active_gpu}" == 'true' ]]; then
    if [[ "${version}" == 'dev-gpu' ]]; then
        pip install "${version}"
    else
        pip install package-gpu=="${version}"
    fi
  else
    if [[ "${version}" == 'nightly' ]]; then
        pip install "${version}"
    else
        pip install package=="${version}"
    fi
  fi

For this kind of problem you want to build a command line with variables, and run it only once.

You only have a few cases but the benefits of this approach become apparent as you add more cases: you don't need an exponential number of branches to keep up.

This code does not exactly follow the logic of your code but it's probably close enough.  I'm using an associative array to build the param variable, and bash regular expressions to test for multiple no-param cases.

#!/bin/bash
declare -A gpu_param=( [true]=-gpu )
[[ $version =~ nightly|dev-gpu ]] || param=package${gpu_param[$active_gpu]}==
pip install $param$version


Recamán Sequence (A005132) I'm going to screw around with visualizing Recamán's Sequence, but want to have a good sequence generator to generate the sequence before I start. I want to use a lazy generator for my actual application, but decided to make a strict version first since it will likely be simpler.

This is what I ended up with. It works (verified against the OEIS), but is quite verbose. I don't technically require seen, but doing constant linear searching over acc would likely be unacceptable. I'm just looking for broad suggestions on how this can be improved, because while it's fairly fast (it can find the first million numbers in ~2 seconds on my potato), it's rather ugly.

I know though that I can make use of transients here, but they're easy enough to add afterwards that that's not a big deal.

Any suggestions would be appreciated, because I feel like I'm missing something obvious.

(defn strict-recamans-sequence [max-n]
  (let [c-last #(get % (dec (count %)))]
    (loop [n 1
           seen #{}
           acc [0]]
      (if (> n max-n)
        acc

        (let [prev (c-last acc)
              back (- prev n)
              new-n (if (and (pos? back) (not (seen back)))
                      back
                      (+ prev n))]
          (recur (inc n) (conj seen new-n) (conj acc new-n)))))))

If you want a lazy sequence, this may be a good example of using Python-style generator functions.  An example:

(defn concat-gen    ; concat a list of collections
  [& collections]
  (lazy-gen
    (doseq [curr-coll collections]
      (doseq [item curr-coll]
        (yield item)))))

(defn concat-gen-pair
  [& collections]
  (lazy-gen
    (doseq [curr-coll collections]
      (doseq [item curr-coll]
        (yield-all [item item])))))

(def c1 [1 2 3])
(def c2 [4 5 6])
(def c3 [7 8 9])

(is= [1 2 3 4 5 6 7 8 9]                            (concat-gen       c1 c2 c3))
(is= [1 1  2 2  3 3  4 4  5 5  6 6  7 7  8 8  9 9]  (concat-gen-pair  c1 c2 c3))


Reading a config file outside of the publicly visible root directory To enable my PHP scripts to access my MySQL database, I have a configuration file containing the name of the MySQL database, usernames, etc.

In order to keep that information secure, I'm storing it outside of the web root on the server. I WAS setting an environment variable in httpd.conf to the file path of the .ini file so that PHP could access it and then parse the config file.

However, for the purposes of demonstration I'm deploying this database and front end on a shared server which will not give me access to httpd.conf. This is the alternative I worked out:

<?php
  if(!isset($GLOBALS['config'])){
    $nonPublic = explode("/",$_SERVER['DOCUMENT_ROOT']);
    array_pop($nonPublic);
    $nonPublic = implode("/",$nonPublic);
    $GLOBALS['config'] = parse_ini_file($nonPublic."/configs/JCDBconfig.ini");
  }
?>

The theory is that I make sure the 'configs' folder is just above DOCUMENT_ROOT, grab all but the last part of the DOCUMENT_ROOT path, and the PHP script should be able to find the config file stored there.

My question is: Is this a good idea, or sloppy? Is $_SERVER['DOCUMENT_ROOT'] reliable enough that, should I deploy this on a dedicated server in the future, it will still work?

I am assuming that you have a directory structure something like this, which can be common in shared hosting environments:

/path/to/your/directory => your customer directory on the host
/path/to/your/directory/public => the web server document root

Or, if you had full control over your environment it might look like:

/some/nonpublic/directory => non-public directory (possibly in include path)
/var/www => web server document root

So ideally, your application should be able to seamlessly handle both without custom code that changes based on where you deploy the application.

Typically, this is done by configuring constants for file paths in a config file, not by relying on values derived from $_SERVER['DOCUMENT_ROOT'] as this has absolutely no connection to where on a server you may have the ability to place your non-public application code. You may be able to count on this behavior for some specific shared host environment, but this gives you no guarantee that this same behavior would exist in another environment.

So an approach of defining path constants may look like:

define('WEB_ROOT', $_SERVER['DOCUMENT_ROOT']);
define('INCLUDE_DIR', {path to one of non-public directories shown above});
define('CONFIG_DIR', INCLUDE_DIR . '/config');

Then if you wanted to check if your config is set for JCDB, it might look more like:

if(!isset($GLOBALS['config'])){
    $GLOBALS['config'] = parse_ini_file(CONFIG_DIR . '/JCDBconfig.ini');
}

This reduces your problem to only having to figure out how to populate the value into INCLUDE_DIR, not trying to determine this directory when you are at the point of trying to conditionally load configurations for various components in the application.

This could be hard-coded (not ideal) which is quick and dirty, but you might consider an approach that allows you to conditionally determine the include path.

For example, if you control the environment, you could modify your Apache config to inject an environmental variable holding the include path or, if missing, perhaps looks into a file that you specifically deploy onto your shared host to determine how to get to that include path for the host you are on.

So perhaps something like this near the beginning of your application bootstrap process.

define('WEB_ROOT', $_SERVER['DOCUMENT_ROOT']);
if(!empty($_SERVER['APP_INCLUDE_PATH']) {
    define('INCLUDE_DIR', $_SERVER['APP_INCLUDE_PATH']);
} else {
    define('INCLUDE_DIR', require WEB_ROOT . '/appIncludeConfig.php');
}

Where in Apache you have

 SetEnv APP_INCLUDE_PATH /some/nonpublic/directory

Or for shared host,  appIncludeConfig.php has a single line of code like:

<?php
return '/path/to/your/directory';

I question why you would want to put a critical dependency like a config setting into a mutable variable in global scope vs. something immutable (like a constant).  So perhaps something like this is more appropriate:

if(!defined('JCDB_CONFIG')){
    define('JCDB_CONFIG', parse_ini_file(CONFIG_DIR . '/JCDBconfig.ini'));
}

Note I also changed the naming of the config setting to be something less generic than just config such that it is clear that this value is specific only to this particular configuration value.


Compare two tables and arrange the values in a new array I have t things working with this current setup:

Route::get('test', function(){
    $finished = \App\Progress::select('stack_id')->get();
    $unfinished = \App\Stack::select(['id as stack_id'])->get();

    foreach ($unfinished as $key => $value) {
        if(!isset($finished[$key])){
            break;
        }
        if($value->stack_id == $finished[$key]->stack_id){
            unset($unfinished[$key]);
        }
    }
    return response()->json(['finished' => $finished->flatten(), 'unfinished' => $unfinished->flatten()]);
});

Two current values in progresses table and three values in stacks table

Progresses

id user_id stack_id
6   1   1
9   1   2

Stacks

id
1
2
3

The response:

{
"finished": [
{
"stack_id": 1
},
{
"stack_id": 2
}
],
"unfinished": [
{
"stack_id": 3
}
]
}

Can this be done in another, more efficient way?

you can create an array of finished and unfinished which contain stack_id and then use array_diff method in PHP.


Finding the difference between the estimated value and the true value in a reward task I have this function called error, which estimates value based on previous value and rewards in trials. The difference between the estimated value and true value is then calculated, giving the error. I need to run this code 1000 times with different lists of trials, but currently it runs too slowly. How would I optimize this code?
Additional information: alpha is a parameter. Reward and true_value are lists. Value always starts at 0.5, but I remove this starting number before calculating error
def loopfunction(alpha, reward, true_value):
    difference = []
    value = [0.5]
    for index, lr in enumerate(reward):
        value.append(lever_update(alpha, value[-1], reward[index]))
    value.pop(0)
    zip_object = zip(value, true_value)
    for value_i, true_value_i in zip_object:
        difference.append(value_i-true_value)
    absdiff = [abs(number) for number in difference]

    return absdiff

The lever_update function, which calculates value is here:
def lever_update(alpha, value, reward):
   value += alpha * (reward - value)
return(value)

Using list comprehensions instead of numerous .append calls is
often times faster and more readable.

A list of rewards should be called rewards instead of reward. Same goes for values and true_values.

We don't need to enumerate rewards, since we don't need the index itself. We can simply iterate over rewards.
def loopfunction(alpha, rewards, true_values):

    values = [0.5]
    for reward in rewards:
        values.append(lever_update(alpha, values[-1], reward))

    values.pop(0)

    return [abs(value - true_value) for value, true_value in zip(values, true_values)]

I sadly can't test performance right now, but I would assume the first for loop takes up most of your runtime. This is what I'd focus on for further improvements. In general, making code more concise and readable also allows for easier refactoring / performance improvements in the future.

We can also make lever_update more concise:
def lever_update(alpha, value, reward):
   return value + alpha * (reward - value)


Watch log dir for new file, automatically tail to slack We have a process that outputs to log files in the format /var/log/xxx/YYYY_MM_DD.log - the file name is chosen programmatically and is not rotated using logrotate or anything like that. We want to automatically tail the latest file and pipe that to slackcat so that we can see the logs in a certain slack channel.

I came up with the following solution that works great, but I'm no bash expert so I am wondering if this could be simplified? The hardest part was avoiding zombie processes when something dies or gets killed, but I'd love to do this with one file instead of 2 also:

watchlogdir.sh

#!/bin/sh
trap "pkill -TERM -g $$; exit" INT TERM EXIT
    while true; do
      /root/tailtoslack.sh &
      PID=$!
      echo $PID
      echo $$
  inotifywait -e create /var/log/xxx/
  pkill -TERM -P $PID
  kill $PID
done

tailtoslack.sh

while true; do
    FILETOWATCH=`ls -t /var/log/xxx/*.log | head -1`
    tail $FILETOWATCH -f -n1 | grep -v "DEBUG:\|^$" --color=never --line-buffered | /root/slackcat &> /tmp/slackcat
    sleep 31
done

The core of watchlogdir.sh, besides the interruption handling stuff, is using inotifywait to watch for a new file created in the log directory, and when that happens, killing tailtoslack.sh and respawning it so it can find the new file

tailtoslack.sh just looks for the latest file, and pipes that to slackcat after filtering out DEBUG lines and empty lines. the while loop here is because some lines in the error logs cause slackcat to crash, so this way if that happens it'll sleep for a little while and retry.

Without changing the requirements of how the log files are written, can any of this be done better?

This seems quite fine. Given your circumstances, I don't see how this can be done simpler.

The script could use a bit of tidying up though. The indentation of watchlogdir.sh is haphazard, it would be more readable to make it consistent. Oh I see now. It's the $$ that messes things up, your formatting is fine.

In the other script, this line could be written better:

FILETOWATCH=`ls -t /var/log/xxx/*.log | head -1`

By using $(...) instead of `...` for command substitution, and using the canonical option -n1 instead of -1 with head:

FILETOWATCH=$(ls -t /var/log/xxx/*.log | head -n1)


Recreating binary counter for arbitrary length arrays After weeks of slaving over FIPS-197, I finally have my own working C/C# implementation of AES-128 which I'm quite happy about.

The next thing I'm looking to do is implement a nonce counter block of configurable length (either 8 or 16 bytes) to convert this block cipher into a stream cipher (CTR mode), according to NIST 800-38a recommendation.

So to do this, the idea I had was to create from scratch a sort of BigNumber implementation that basically reflects how we increment the bits in a byte, starting with the least significant bit:

0000
0001
0010
0011
0100
0101
0110
0111
1000
...

The concept is come up with the same counting system, incrementing each element in the array (starting with the last element), resetting the LSE ("least significant element") when it's at max and incrementing the previous element.

Here's what I came up with:

// Re-invent the byte using arbitrary length array (i.e. BigNumber)
// to increment 16-byte nonce

// Benchmark: 273,839 inc/s { 00, 04, 2D, AF } on ATmega328
void incBytes(byte *state, int i)
{
  if (state[i] < 0xff)
  {
    state[i]++;
    return;
  }

  state[i] = 0x00;

  if (i == 0)
    return;

  i--;
  incBytes(state, i);
}

void printBytes(byte *state, int len)
{
  int i;
  for (i = 0; i < len; i++)
  {
    printf("%02X ", state[i]);
  }

  printf("\n");
}

void test()
{
  long t, count;
  byte nonce[16];

  fillBytes(nonce, 0, sizeof(nonce));
  count = 0;
  t = millis();
  while (millis() - t < 1000)
  {
    // cipher(plaintext, expandedKey);
    // cipherCtr(plaintext, expandedKey, nonce);
    incBytes(nonce, sizeof(nonce) - 1);
    count++;
  }

  Serial.print(count);
  Serial.println(" inc/s (incBytes)");
  dumpBytes(nonce, sizeof(nonce));
}

And here is a link to it in action at Ideone.

So I'd just like to get some feedback, not so much on the purpose of all of this or other alternatives out there, but if there are ways to improve it or if this is pretty much it :)

It will then provide me with a way to ensure that the Nonce block for AES-128 in CTR mode gets incremented properly (hence unique) using any arbitrary length byte array.

Note: This is for an Atmega328 so I would like to avoid using long long (64-bit integers) altogether.

No check for end of array
incByte() doesn't check if i >= 0.  So if all bytes are 0xff, it will happily start reading/writing to state[-1].
Simplification
Actually, I would remove the recursion.  If byte is of size 1 byte, you could also simplify the check for overflow past 0xff:
void incByte(byte *state, int i)
{
    do {
        if (++state[i] != 0)
            return;
        i--;
    } while (i >= 0);
}


Sharing data with another thread using lock_guard I wrote a updater_thread() and a reader_thread(), and used lock_guard to protect a global instance.
Question

I've never used lock_guard. In this code, is lock_guard used properly?

Is this code thread-safe?

Code
#include <iostream>
#include <thread>
#include <mutex>
#include <iterator>
#include <algorithm>
#include <vector>
#include <initializer_list>
#include <unistd.h>

class C {
  std::vector<int> v;
  std::mutex mutex_;

public:
  C() {}
  void Update(const std::vector<int> &new_v) {
    std::lock_guard<std::mutex> lock(mutex_);
    v = new_v;
  }
  bool Check(const int x){
    std::lock_guard<std::mutex> lock(mutex_);
    return std::find(v.begin(), v.end(), x) != v.end();
  }
  /* dump() is not essential */
  void dump() {
    std::lock_guard<std::mutex> lock(mutex_);
    std::cout << "dump: ";
    std::copy(v.begin(), v.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
  }
};

// create an instance gloablly
C g_c;

void updater_thread() {
  std::cout << "start updater_thread\n";
  while (true) {
    std::vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(rand() % 10 + 1);
    }
    std::sort(v.begin(), v.end());
    g_c.Update(v);
    std::cout << "updated!!!\n";
    std::copy(v.begin(), v.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    sleep(5);
  }
}

void reader_thread() {
  std::vector<int> v {1,2,3,5};
  while (true) {
    std::cout << "check: non-exist item: ";
    for (int i = 0; i < v.size(); i++) {
        if (!g_c.Check(v[i])){
            std::cout <<  v[i] << " ";
        }
    }
    std::cout << "\n";
    sleep(1);
  }
}

int main() {
  std::thread t_up(updater_thread);
  std::thread t_r(reader_thread);
  t_up.join();
  t_r.join();
}

Yes, that all looks correct to me!

You don't use anything from <unistd.h> (non-standard) or <initializer_list> (obscure), so I recommend removing those includes.

You sigil the mutex_ data member with an underscore, but you don't sigil the v member. I recommend being consistent:

std::mutex mutex_;
std::vector<int> v_;

Personally I would spell the member's name mtx_, but that's just a personal habit; I don't know if that naming convention is widespread. (cv_ for a condition variable certainly is, though!)

Consider that your Check and dump methods don't need to mutate the object, so they should be declared const. This means that your mutex_ data member will need to be declared mutable so that you can still lock and unlock it inside your const member functions.

Also, consider picking a capitalization rule and sticking to it. Why Check and Update but dump (not Dump)?

Check's parameter x is marked const but that marking serves no purpose: eliminate it. (Const is a contract.)

for (int i = 0; i < v.size(); i++) {
    if (!g_c.Check(v[i])){
        std::cout <<  v[i] << " ";
    }
}

This could be rewritten more concisely as

for (int vi : v) {
    if (!g_c.Check(vi)) {
        std::cout << vi << " ";
    }
}

Your multithreading stuff all looks great!


Getting the distance between various classes of shapes Below I define a simple shape class with two derived classes: Point and Line which both implement the Distance interface that defines a getDistance(Shape) method.  This type of setup could be useful for calculating distances between shapes.  For this simple example, consider the distance to be in 1D space and don't consider the actual calculations.

package shape;

public interface Distance {
    public int getDistance(Shape other);
}

public abstract class Shape implements Distance {
    public abstract int getDistance(Shape shape);
    public abstract int getDistance(int num); //for point
    public abstract int getDistance(int start, int end); //for line
}

public class Line extends Shape {
    private int start;
    private int end;

    public Line(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int getDistance(Shape other) {
        return other.getDistance(start, end);
    }

    //never gets called
    public int getPoint(Point other) {
        return getDistance(other.num);
    }

    @Override
    public int getDistance(int num) {
        return Math.min(Math.abs(num - start), Math.abs(num - end));
    }

    @Override
    public int getDistance(int start, int end) {
        int delta1 = Math.min(Math.abs(this.start - start), Math.abs(this.start - end));
        int delta2 = Math.min(Math.abs(this.end - start), Math.abs(this.end - end));
        return Math.min(delta1, delta2);
    }
}

public class Point extends Shape {
    protected int num;

    public Point(int num) {
        this.num = num;
    }

    @Override
    public int getDistance(Shape other) {
        return other.getDistance(num);
    }

    @Override
    public int getDistance(int num) {
        return Math.abs(this.num - num);
    }

    @Override
    public int getDistance(int start, int end) {
        return Math.min(Math.abs(num - start), Math.abs(num - end));
    }
}

public class ShapeTest {
    public static void main(String[] args) {
        Shape line = new Line(1, 2);
        Shape point = new Point(0);
        System.out.println(line.getDistance(point));
    }
}

My question is with the implementation above, there's a lot of indirection.  For example, in the Line and Point classes, for the following method: public int getDistance(Shape other), it's not known at compile time what Shape actually is.  So to avoid doing instanceof on Shape and handling each case in that function, I call getDistance on other and pass in the relevant coordinates -- this is the indirection that's a bit ugly, but it's a more object-oriented / polymorphic approach than casting and instanceof.

Question is: is there a cleaner way to implement this?  I'd like to define the required function int getDistance(Shape), leave it empty, and then define getDistance(Line) and getDistance(Point).  With those functions defined, it would be nice if Java just always called the most specific function prototype (so that getDistance(Shape) is never actually called), but that doesn't seem to happen.

Any advice on how to clean up the code above?

Quick Comments

Your Distance Interface is weird. It does not represent a distance, but an object having the ability to provide the distance between it, and some other object sharing the same interface.

The Shape interface is weird. The distance(int) and distance(int, int) are hacky and should go. They rely on implementation details of Point and Line.

The Shape should be an interface. It is currently a void Abstract class with no added value, it just prevents proper inheritance.

It looks weird to me to return ints for distances, given the propension of most metrics to return doubles due to frequent square roots being applied. However, I don't know your metrics so I'll stick with it.

Implementation using double-dispatch

If the number of classes is rather low, you could implement double-dispatch. Make the Shape interface have a distance(Shape) and every distanceTo(Foo), distanceTo(Bar), distanceTo(Fuzz) etc. like so:

public interface Shape {
    int distance(Shape shape);
    int distanceTo(Foo foo);
    int distanceTo(Bar bar);
    int distanceTo(Fuzz fuzz);
}

This way all Shape implementations will look like the following:

public class Foo implements Shape {
    public int distanceTo(Shape shape) {
        // You can copy-paste this method body on all other classes
        return shape.distanceTo(this); // This will call the strongly-typed methods below
    }
    public int distanceTo(Foo foo){
        // Specific implementation
    }
    public int distanceTo(Bar bar){
        // Specific implementation
    }
    public int distanceTo(Fuzz fuzz){
        // Specific implementation
    }
}

Here's how to use it:

Foo foo = new Foo();
Bar bar = new Bar();
int foobar = foo.distance(bar);
int foofoo = foo.distance(foo);

Very simple with just 3 classes. Can become a nightmare with 10+ classes.

You have to realize, that for every pair of Shapes, you'll need a dedicated distance method implementation. This means the number of distance(T t, U u) methods will grow rapidly.

From here on I will assume your network of Shape objects is sufficiently complex to warrant a dedicated structure to handle this in an externalized way.

The Problem

Basically, this boils down to the following:

  Given miscelaneous Objects, how to make it possible for any pair of Objects to interact (the interaction depends on the nature & implementation of those objects, and is not known in advance) and return something.

Obviously the interaction between two entities cannot be entirely contained in the entities themselves.

If it was, each Entity would have to know its distance to any other entity type (including unknown & unforeseen future Shape implementations), which means it would know every other Entity existence, and implementation details, and would have a dedicated distance implementation for each. That would:

Break Encapsulation - one Entity would have to know the detailed implementation of the other to perform the calculation)
Break extensibility - Adding an Foo entity would require adding a distance(Foo)method to every other Object

All those sins were commited in the double-dispatch implementation above.
So now we know the interaction implementation has to be externalized.

How to build an extensible externalized interaction function

Let's have a centralized distance functor (I'll make it a Singleton using an Enum, I assume you only have one set of interacting Shape implementations):

public enum DistanceEvaluator {
    INSTANCE;
    public final int distance(Shape shape1, Shape shape2){
         // Do something magic here
    }
}

Is this usable enough? I think you could very easily add the following default method (thanks, Java 8) to your Shape Interface:

public interface Shape {
    default int distance (Shape other){
        return DistanceEvaluator.INSTANCE.distance(this, other);
    }
}

Now aShape can calculate its distance to an other... provided the DistanceEvaluator holds an implementation for that particular pair of classes.

Enriching the DistanceEvaluator with implementations

A) You could implement everything in the DistanceEvaluator.

Then you just distribute the implementation using ìnstanceof and casting.
Advantages: The class combines all implementations, so can make good reuse of helper intermediate functions.
Disadvantage: the class could become enormous.

This should be used if the number of pairs is rather small with synergies (points, lines, segments, polygons).

B) You could use instanceofand cast the first argument (of type Foo)

Then simply forward the second argument (type Bar) to a FooDistanceCalculator class that knows how to compute distance to any Bar class.
Advantage: Implementations are grouped in a package, yet distributed between several classes.
Disadvantage: how to tell if distance(Foo, Bar) or distance(Bar, Foo) exists?

This should be used if the number of pairs becomes important and requires a (simple) structure.

C) You could make a completely dynamic mapping of distance functions.

Such mapping could be enriched at runtime, as a bonus.

Use the following Evaluator :

import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;

public enum DistanceEvaluator {

    INSTANCE;

    /** Holds distance implementations */
    private final Map<Class<? extends  Shape>, Map<Class<? extends Shape>, BiFunction<? extends Shape, ? extends Shape, Integer>>> MAP = new HashMap<>();

    /** When a class has no matching map of distance functions */
    private final Map<Class<? extends Shape>, BiFunction<? extends  Shape, ? extends  Shape, Integer>> MISSING = new HashMap<>();

    /** When a pair has no matching distance function */
    private final BiFunction<? extends  Shape, ? extends  Shape, Integer> NO_FUNCTION = new BiFunction<Shape,Shape, Integer>() {
        @Override
        public Integer apply(Shape t, Shape u) {
            throw new IllegalArgumentException("Shapes " + t + " and " + u + " cannot calculate their respective distance");
        }
    };

    /**
     * Computes the distance between any pair of Shapes.
     * @param shape1 a shape
     * @param shape2 another shape
     * @throws IllegalArgumentException if the pair has no matching distance implementation
     * @return the distance between the two shapes
     */
    public <T extends Shape, U extends Shape> int distance(T shape1, U shape2) {
        @SuppressWarnings("unchecked")
        Class<T> shape1class = (Class<T>) shape1.getClass();
        @SuppressWarnings("unchecked")
        Class<U> shape2class = (Class<U>) shape2.getClass();
        @SuppressWarnings("unchecked")
        BiFunction<T,  U, Integer> func = (BiFunction<T, U, Integer>) MAP.getOrDefault(shape1class, MISSING).getOrDefault(shape2class, NO_FUNCTION);
        return func.apply(shape1, shape2);
    }

    /** Register a distance function for a pair of {@link Shape} sub-classes.
     * Note the function will be registered for both class pairs (a, b) and (b, a)
     * @param class1 first {@link Shape} Class
     * @param class2 second {@link Shape} Class
     * @param biFunction distance {@link BiFunction}
     */
    public <T extends Shape, U extends Shape> void register(Class<T> class1, Class<U> class2, BiFunction<T, U, Integer> biFunction) {
        Map<Class<? extends Shape>, BiFunction<? extends Shape, ? extends Shape, Integer>> intermediate1 = MAP.get(class1);
        if(intermediate1 == null){
            intermediate1 = new HashMap<>();
            MAP.put(class1, intermediate1);
        }
        intermediate1.put(class2, biFunction);

        // Symmetric
        Map<Class<? extends Shape>, BiFunction<? extends Shape, ? extends Shape, Integer>> intermediate2 = MAP.get(class2);
        if(intermediate2 == null){
            intermediate2 = new HashMap<>();
            MAP.put(class2, intermediate2);
        }
        intermediate2.put(class1, biFunction);
    }
}

Here are a few Shape implementations. Note those implementations inject their required distance evaluators when their classes are loaded.

A Point class:

public class Point implements Shape{
    static {
        DistanceEvaluator.INSTANCE.register(Point.class, Point.class, new BiFunction<Point, Point, Integer>() {
            @Override
            public Integer apply(Point t, Point u) {
                return 0; // Calculations here
            }
        });
        DistanceEvaluator.INSTANCE.register(Point.class, Line.class, new BiFunction<Point, Line, Integer>() {
            @Override
            public Integer apply(Point t, Line u) {
                return 0; // Calculations here
            }
        });
    }
    // Class implementation details, up to you
}

A Line class:

public class Line implements Shape {
    static {
        DistanceEvaluator.INSTANCE.register(Line.class, Line.class, new BiFunction<Line, Line, Integer>() {
            @Override
            public Integer apply(Line t, Line u) {
                return 0; // Calculations here
            }
        });
    }
    // Class implementation details, up to you
}

With this scheme, it becomes possible to not implement all distance functions. This might or might not be a good feature for you.


Generic Repository: Am I over-complicating? I have created a generic repository for my MVC 3 page. I am using interfaces and a UnitOfWork. But before I set out to do this? Is this the right way to separate my databaseaccess from my viewmodels and views?

WHY I DID IT:

I want to seperate my databaseaccess from my viewmodels and my views, I also want the option to have specific methods for inserting some of my data hence the UserRepository. I also want a controlled environment using the UnitOfWork.

FEARS:

Am I over-complicating everything using these interfaces? Should I ditch the generic repository, I will use it for "basic" inserts so it's not useless by any means. I do understand that I might save some time having the generic repository, only to be creating specific repositories for some of my inserts/update/deletes.

Summary:

It consists of 6 files at the moment of which 2 are:

IRepository
GenericRepository
IUnitOfWork
UnitOfWork
IUserRepository
UserRepository

Code

IRepository:

public interface IRepository<T> where T : class
{
        IEnumerable<T> BaseFetchAll();
        void BaseAdd(T entity);
        void BaseDelete(T Entity);
}

Repository:

public abstract class GenericRepository<T> : IRepository<T> where T : class
{
    private IObjectSet<T> _dbContext;
    private Entities _context;
    protected DbSet<T> dbSet;

    internal GenericRepository(Entities context)
    {
        this._context = context;
        dbSet = context.Set<T>();
    }

    public void BaseDelete(T entity)
    {
        dbSet.Remove(entity);
    }

    public IEnumerable<T> BaseFetchAll()
    {
        return (IEnumerable<T>)(from x in dbSet select x).ToList<T>();
    }

    public void BaseAdd(T entity)
    {
        dbSet.Add(entity);
    }
}

IUnitOfWork:
Before you kick my butt, I am to implement the save,rollback etc. methods this is just to show you what I'm doing.

public interface IUnitOfWork
{
    IUserRepository UserRepository { get; }
    IUserFileRepository UserFileRepository { get; }
}

UnitOfWork:

public class UnitOfWork : IUnitOfWork
{
    private IUserRepository _userRepository;
    private Entities context = new Entities();

    public IUserRepository UserRepository
    {
        get
        {
             if(this._userRepository == null)
               this._userRepository = new UserRepository(context);
             return this._userRepository;
        }
    }
}

IUserRepository:

public interface IUserRepository: IRepository<t_users>
{
    IEnumerable<t_users> FetchAllUsers();
    void InsertToUserTableWithSpecs();
}

UserRepository:

public class UserRepository : GenericRepository<t_users>, IUserRepository
{

    private Entities dbContext;
    public UserRepository(Entities context) : base(context)
    {
        this.dbContext = context;
    }

    public IEnumerable<t_users> FetchAllUsers()
    {
        return (IEnumerable<t_users>)(from x in dbContext.t_users select x);
    }

    public void InsertToUserTableWithSpecs()
    {

    }
}

Not a lot of code but hopefully something to give you an idea in which direction I'm going.

I think if you are going to have only one Repository, then yeah this is over complicated! But if you will have many Repositories and you will be adding more and more, then you are on the right track. But couple of points:

I am not sure how your are using your UoW. From my point of view UoW should look like something like:

interface IUnitOfWork
{
    Begin();
    End();
    Rollback();
}

And UoW should be passed to Repositories. So basically you have a UoW that couple of Repositories may use to get their job done (get/insert records for instance). From where I look at this a UoW is not specific to a single Repository and can span multiple Repositories.

Imagine for instance that your UoW involves creating an Order entity and updating the Customer entity together.

Also I would suggest to tighten IRepository definition to:

public interface IRepository<T> where T : IDomainObject

This basically is saying that repositories are not supposed to be created for any sort of class. Your Domain classes can then implement IDomainObject to satisfy this condition. IDomainObject can be empty or depending on your Domain it can have some Domain related properties.


Using quickCheck for "99 Haskell problems" - problem 1 I'm working on learning Haskell, and I've implemented a solution to the first of the 99 Haskell problems. Here is my code:

import Data.Int
import Test.QuickCheck

myLast :: [a] -> Either String a
myLast [] = Left "Empty lists have no last element."
myLast xs = Right ((reverse xs) !! 0)

testMyLast :: [Int] -> Bool
testMyLast xs =
    case myLast xs of
        Left err -> null xs
        Right x -> x == last xs

main = quickCheck testMyLast

Now, I realize that my implementation of myLast is not the most efficient one. I'm not particularly interested in that type of feedback. Rather, I'm more curious about whether or not I'm following reasonable Haskell code style practices (the naming of things, indentation, etc.), as well as how I'm dealing with errors.

It's my understanding that using Either (or Maybe) when an error occurs is, in general, to be preferred over error "...", since dealing with exceptions is really only cleanly done in an IO context. Is my understanding correct? If it is, why do basic library functions (like List's last, for example) use error instead?

Most important point: Your answer does not do what is asked.

Question:

Prelude> myLast [1,2,3,4]
4
Prelude> myLast ['x','y','z']
'z'

Your implementation:

*Main> myLast [1,2,3,4]
Right 4

You should quickCheck for the equivalence of the function you are asked to implement myLast xs == last xs (with appropriate type signatures),
or write a unit test suite comprising at least the cases given.

Other points:

import Data.Int is unused.
(xs !! 0) should be head xs
Nested parentheses should be used sparingly because trying to match them reduces readability. Composition using operators . and $ should be preferred:

-- instead of this
myLast xs = Right (head (reverse xs))
-- this reads better
myLast' xs = Right $ head $ reverse xs
-- this makes the composition of 3 steps more explicit
myLast'' = Right . head . reverse


Find the maximum value of | Ai - Aj | + | i - j |: hackerearth.com practice problem Can you solve it?:

  Given an array 'A' consisting of 'n' integers, find the maximum value of the following expression:
  \$\lvert A_i - A_j\rvert + \lvert i - j\rvert\$

where \$A_i\$ is the element of the array at the i-th position (0-indexed array)

My solution:

def solve(n,l):
    ans=0
    for i in range(n):
        for j in range(n):
            if ans < (abs(l[i]-l[j])+abs(i-j)):
                ans=(abs(l[i]-l[j])+abs(i-j))
                print(ans)

t=int(input())
for _ in range(t):
    n=int(input())
    l = list(map(int,input().split()))
solve(n,l)

This code passes all the sample test cases but when I finally submit the code
for two inputs it shows wrong and
for all the other inputs it shows time limit exceeded.

Kindly point out what is wrong and what can be done in order to get the correct output.

The minor problem is that you are printing the result in the wrong place.

The major problem is that n may be up to 100,000.  This means you need to run 10,000,000,000 of your inner test.  And you may have only 0.02 seconds to do that.

The trick to dealing with that is probably to determine the maximum possible score of a given i and l[i], and skip the inner loop if it isn't worth it.  As part of this, you might find it beneficial to determine the range of the l[] values.

As an example, if you determine that all l[i]<=5, then it isn't worth looking at i>6 and i<n-6 (or thereabouts... I'm not positive about the border condition).


JQGrid with dynamic columns and server-side functionality I have a requirement where I need to build a grid with dynamic columns. I am dealing with a large dataset so I would like to use server-side paging, sorting, filtering logic so that I render only a page-size. I think I got the basic functionality working but just wanted to get my approach reviewed.

An action route will be the JSON datasource for the jqgrid.

Reference

My approach:

First make an ajax call to get the dynamic col model and other grid params (rows, page etc.) except data.
Update grid params (url, datatype and mtype) to enable server-side paging, sorting etc.

I am using a flag in the query string to determine if I need the col model (or) the data.

Note: I set the async flag to false for the AJAX requests to make sure I do not run into timing issues.

As you can see, I need to make two requests to set up the grid. One to get the col model and another one to get data and to update it to enable server-side interaction for subsequent requests. Is this ok?

$.ajax({
    url: firstFetchURL, //will hit an asp.net mvc action on a controller that returns json
    dataType: "json",
    type: 'POST',
    async: false,
    success: function (result) {

        if (result) {

            if (!result.Error) {

                var colD = result.data;
                var colM = result.colModelList;
                var colN = result.columnNames;

                $("#myGrid").jqGrid('GridUnload');

                $("#myGrid").jqGrid({ datatype: 'local',
                    colModel: colM,
                    colNames: colN,
                    data: colD,
                    height: "auto",
                    rowNum: 10,
                    sortname: viewOptionText,
                    sortorder: "desc",
                    pager: '#myGridPager',
                    caption: "Side-by-Side View",
                    viewrecords: true,
                    gridview: true
                });

                //Update grid params so that subsequent interactions with the grid for sorting,paging etc. will be server-side

                $("#myGrid").jqGrid('setGridParam', { url: secondFetchURL, datatype: 'json', mtype: 'POST' }).trigger('reloadGrid');

            }
        }
    },
    error: function (xhr, ajaxOptions, thrownError) {
        if (xhr && thrownError) {
            alert('Status: ' + xhr.status + ' Error: ' + thrownError);
        }
    },
    complete: function () {
        $("#loadingDiv").hide();
    }
});

I saw a related post here, but I am looking for some direction from experienced JQGrid users.

Small recommendations:

It seems to me that you can remove async: false parameter for the $.ajax call.
You can remove result.data from the data returned by the ajax call. (After that you should and the line with var colD = result.data). The data will be not really used because you call trigger('reloadGrid'); immediately.
On the other side the values for sortname and sortorder parameters should be included in the data model (as the properties of result).
You can use url: secondFetchURL, datatype: 'json', mtype: 'POST' parameters directly in the jqGrid definition ( in $("#myGrid").jqGrid({/*here*/});. No trigger('reloadGrid') will be needed.

UPDATED: Look at this and this answers. Probably the approach is what you need from the dynamic columns.

You can take a look in the answer in case if you will need to use custom formatters.


Improve page-specific CSS for different color schemes For a website with four pages (blog, portfolio, profil and impressum) I have four different color schemes (for links, headings, code, etc.).  This results in bloated CSS which I want to reduce.

Here is a demo. You see the navigation items use the color scheme of the page it links to. In the demo we're on the blog page with a green theme. Styling the different pages works by adding a class to the root element (i.e. ).

How can I improve this approach of styling things page-dependant?

Also what kind of naming would be appropriate? I could use the titles of the pages (page--blog, link--blog, …) or the colors (page--green, link--green, …). Other ideas/suggestions?

HTML:

        BlogPortfolioProfilImpressum

Regular paragraph, containing a link. Crazy, huh?

CSS:

.site-nav {
    background-color: #444;

    a {
        color: white;
        display: inline-block;
        padding: 20px;
    }
}

.link--green {
    background-color: forestgreen;

    .page:not(.page--blog) &:hover {
        background-color: yellowgreen;
    }
}

.link--blue { /* ... */ }
.link--orange { /* ... */ }
.link--red { /* ... */ }

.page-content {
    a,
    h1, h2, h3, h4, h5, h6 {
        .page--blog & {
            color: forestgreen;
        }

        .page--profil & { /* ... */ }
        .page--portfolio & { /* ... */ }
        .page--impressum & { /* ... */ }
    }
}

possible solutions/ideas:

additional CSS file only used on these sites (extra HTTP request)
page-specific CSS in style tags inside the actual html document (hard to manage)
Using SASS mixins to generate the CSS for the four pages (won't reduce bloat)

Some days passed and I feel like I should share the changes I have made so far.

Naming

I started using page names instead of color names on classes and variables. This leaves me with the benefit of being able to change the color scheme of an entire page only by changing the value of the color variable.

.page--home       -> .page--blog
.nav__item--green -> .nav__item--blog
$green-color      -> $blog-color

Generating page-specific CSS with a mixin

I need to style certain elements depending on the class I assign to the root element (e.g. <html class=page--blog>)
The needed arguments I pass to the mixin are $element (a selector like .site-nav or h1) and $property (a CSS property like color)
There also is an optional argument which allows me to switch to light color variations

Mixin:

@mixin themify($element, $property, $light-colors: false) {
    $pages: null;
    @if $light-colors == true {
        $pages: blog      $green-color-light,
                portfolio $orange-color-light,
                profil    $blue-color-light,
                impressum $red-color-light;
    } @else {
        $pages: blog      $green-color,
                portfolio $orange-color,
                profil    $blue-color,
                impressum $red-color;
    }

    @each $page in $pages {
        .page--#{nth($page, 1)} #{$element} {
            #{$property}: nth($page, 2);
        }
    }
}

/* Call the mixin without optional argument */
@include themify(site-nav, background-color);

/* ...use the light colors instead of the normal ones */
@include themify(site-nav, background-color, $light-color: true);

Problems with the mixin:

I can't pass a list of selectors like a, h1, h2, h3, h4, h5, h6 – Didn't find a solution so far (probably going to involve multi-dimensional lists)
Still creates the bloated CSS, but eases my work

I still would love to hear some suggestions/improvements.


Sample table-driven finite-state machine We have interviewees write sample code, but now we want them to modify some simple working code. I came up with the following proposal, which is a syntax-directed interpreter implemented with a table-driven finite state machine. The interpreter simply accepts whitespace-delimited text and outputs "Hello" when it sees the case-insensitive command "HELLO". Any other input is an error.

This is a highly-simplified version of some C code converted to C# for the interview:

enum Lexeme
{
    Error,
    EOF,
    Whitespace,
    H, E, L, O
}

static Lexeme LexemeOfIntChar(int cIn)
{
    if (cIn < 0)
        return Lexeme.EOF;

    switch (Convert.ToChar(cIn))
    {
        case 'H':
        case 'h':
            return Lexeme.H;
        case 'E':
        case 'e':
            return Lexeme.E;
        case 'L':
        case 'l':
            return Lexeme.L;
        case 'O':
        case 'o':
            return Lexeme.O;
        case ' ':
        case '\t':
        case '\r':
        case '\n':
            return Lexeme.Whitespace;
        default:
            return Lexeme.Error;
    }
}

static void Main(string[] args)
{
    // Transition table.
    // Each row is a state, each column is the new state given the column lexeme.
    // State -1 is error. No need to define an Error row since we never transition from it.
    // State 7 is end. We never transition from this either.
    int[,] transition = {
      // Err,EOF, Ws,  H,  E,  L,  O       // Lexeme
        { -1,  7,  0,  1, -1, -1, -1 },    // 0 = Start
        { -1, -1, -1, -1,  2, -1, -1 },    // 1 = first H
        { -1, -1, -1, -1, -1,  3, -1 },    // 2 = first E
        { -1, -1, -1, -1, -1,  4, -1 },    // 3 = first L
        { -1, -1, -1, -1, -1, -1,  5 },    // 4 = second L
        { -1,  6,  6, -1, -1, -1, -1 },    // 5 = first O
        { -1,  7,  0,  1, -1, -1, -1 },    // 6 = 'HELLO'
    };

    int currentState = 0;   // 0 = Start
    while ((currentState >= 0) && (currentState != 7))
    {
        Lexeme t = LexemeOfIntChar(Console.Read());
        currentState = transition[currentState, (int)t];
        switch (currentState)
        {
            case -1: Console.WriteLine("Invalid character!"); break;
            case 6: Console.WriteLine("Hello"); break;  // 6 = saw 'HELLO' with terminal symbol
        }
    }
}

The proposed exercise is to extend this interpreter to accept a "HELP" command that will print out:

  "usage 'HelloScript <scriptfile'

This can be done in about a half-dozen changes.

A co-worker I asked this about was able to complete it in under 15 minutes, but wanted to argue about terminology, implementation, et al.

The intent is for it to be a simple exercise only to see if interviewees can understand and maintain existing code. How understandable and maintainable is it?

If I were a candidate, I'd judge what I think the quality of your code looks like based on this simple, and I'd have some concerns:

Your transition table depends on the values of the Lexeme enum not changing (say by inserting additional values). If this is the case I'd like there to be a comment on enum saying order is significant or having the values explicitly given orders. Otherwise I'd expect the actual numbers to not matter.
Your code contains a transition table. That's hard to read and hard to modify. Why would you do that?
You've two extra sets of parens here:

while ((currentState >= 0) && (currentState != 7))

Your states and done via magic numbers and not an enum.
The check for -1 feels like it's in the wrong place. It is handling an error condition. But the other element of the switch isn't an error condition.


Text cutting tools for Twitter A few days ago I wanted to build a tools to cut a long text into one hundred-letters strings with the number of the tweets and which part of the tweets the tweet belongs to.

  I tried to have a tweet with one-hundred characters long but I could not find anything relevant to [1/x]

This is my tool:

import tweepy

n = 100

with open('texte-tw.txt','r') as input_file:
    abc = []
    for lines in input_file:
        abc.extend([lines[i:i+n] for i in range(0,len(lines),n)])

abc = [i.replace('\n','') for i in abc]

abc = list(filter(bool, abc))

ckey = 'xxx'
csecret = 'yyy'
atoken = 'uuu'
asecret = 'zzz'

auth = tweepy.OAuthHandler(ckey,csecret)
auth.set_access_token(atoken,asecret)
api = tweepy.API(auth)

for i,val in enumerate(abc):
        api.update_status(status=(val+' ['+str(i+1)+'/'+str(len(abc))+']'))

This is an extract of my file:

While it should be clear that we need a means of representing and reasoningabout uncertainty, it is not immediately obvious that probability theory can provideall of the tools we want for artiﬁcial intelligence applications.

Probability theorywas originally developed to analyze the frequencies of events. It is easy to seehow probability theory can be used to study events like drawing a certain hand ofcards in a game of poker.

These kinds of events are often repeatable. When wesay that an outcome has a probabilitypof occurring, it means that if we repeatedthe experiment (e.g., draw a hand of cards) inﬁnitely many times, then proportionpof the repetitions would result in that outcome.

Questions are the following:

What can I do to improve my solution?
Is there a way to cut with words that will be around one-hundred characters (+/- 10 characters) long tweet?
Are there way to package everything and that the solution will run with just one click (using Tkinter or something similar)?

My feedback:

Separation of concerns

You have three main concerns on your program:

Retrieving the input data (the text)
Splitting the text into 100 character tweets
Outputting the data to twitter

Here, you can have three functions, one per concern. Once you separate those concerns, your final code will become more flexible. You'll be able to (for example) take data from a different place than a file (e.g. a text field on GUI), output to some place different than twitter (e.g. you may want to output to the console for debugging), test different splitting algorithms (e.g. you may try an algorithm that tries not to break any words).

def readFile(filename):
    """Returns a string with the file text"""

def splitText(text, size):
    """Splits text into chunks of length size"""

def tweetEverything(texts):
    """Tweet each text in texts, adding the index of text in texts"""

Descriptive variable names

abc can become splitted_text, val can become excerpt, n can become split_size.

Cleaner ways of doing the same

(val+' ['+str(i+1)+'/'+str(len(abc))+']'

can be done using the string method format

'{} [{}/{}]'.format(val, i+1, len(abc))

Note how by doing it this way you avoid casting to str, and you clearly put the output format on the left side and the variables you render using that format on the right side.

list(filter(bool, abc))

in this case, that is the same as:

filter(None, abc)

because the default filtering behaviour is filter out false values. Another option is to use a list comprehension:

[excerpt for excerpt in abc if excerpt]

Reference


Using separate functions for Project Euler 1 I started programming with Java and C++, so I'm used to having a 'main' function that calls other functions that do the actual work. At university I was always told that doing actual computation in the main function is bad practice. I'm currently playing around with Python, and I have trouble figuring out how to write a nice 'main' function, especially since I'm doing small stuff that doesn't need separate classes.

What do you think about the following code? Is the main function necessary, or would  you just write everything without functions? Is there a general consent on this in the Python world?

# Finds sum of all multiples of 3 and 5 from 0 to 999

def find_multiples():
    global numbers

    for i in range(0,1000):
       if i%3==0 or i%5==0:
           numbers.append(i);

numbers = []

if __name__ == '__main__':
    find_multiples()
    print sum(numbers)

Here's some superficial review. More for testing the site and some comment formatting than anything, but: do create main functions (helps us benchmarkers a lot) and do think that your module can be imported, so docstrings and local variables help.

# Finds...
###-^ Put this in a docstring

def find_multiples():
    """Finds sum of all multiples of 3 and 5 from 0 to 999 """
###-^ This allows you to "from x import find_multiples,  help(find_multiples)"
    numbers = []
###-^ Avoid globals
    for i in xrange(1000):
###-^ Use xrange if Python 2.x, no need to start at 0 (it's the default)
       if not (i % 3) or not (i % 5):
###-^ Add spaces around operators, simplify
###-^ the boolean/numeric checks
           numbers.append(i)
###-^ Remove trailing ;
    return numbers

###-^ Removed global

def main():
###-^ Allows calling main many times, e.g. for benchmarking
    numbers = find_multiples()
    print sum(numbers)

if __name__ == '__main__':
    main()


Building a dynamic dictionary mapper inside function I have one function attrmapper. The purpose for this function is to build a dictionary, information, as attribution for the object. Is there a better way for me to rewrite the obj.information.update( part? The part to update information attribution will be more clear? Because if we replace mapping to a long string, the function will be really hard to read.

mapping = {
'firstname': 'this is fisrt name: {} should be string',
'lastname': 'this is last name: {} should be string',
'address': 'this is address {} should be address1, address2, state, state and zipcode',
'phone_number': 'this is phone number {} should be 0 to 9',
'gender': 'this is gender {}: should be male or female',
'company': 'this is company {} should be start with G',
'position': 'this is position {} should be engineer, manager and level',
'aAbreu': 'Albert Abreu',
'cGreen': 'Chad Green',
'lCessa': 'Luis Cessa',
'aJudge': 'Aaron Judge',
'jEllsbury': 'Jacoby Ellsbury',
    }
def attrmapper(obj: object) -> object:
    information = {}
    for name in ['aAbreu', 'cGreen', 'lCessa', 'aJudge', 'jEllsbury']:
        obj.information.update(
            {'{}_firstname'.format(name): mapping.get('firstname').format(mapping.get(name)),
            '{}_lastname'.format(name): mapping.get('lastname').format(mapping.get(name)),
            '{}_address'.format(name): mapping.get('address').format(mapping.get(name)),
            '{}_phone_number'.format(name): mapping.get('phone_number').format(mapping.get(name)),
            '{}_company'.format(name): mapping.get('company').format(mapping.get(name)),
            '{}_position'.format(name): mapping.get('firstname').format(mapping.get(name))})
    return obj

We can do a dictionary comprehension and avoid code repetition:

NAMES = ['aAbreu', 'cGreen', 'lCessa', 'aJudge', 'jEllsbury']
ATTRIBUTES = ['firstname', 'lastname', 'address', 'phone_number', 'company', 'position']
for name in NAMES:
    full_name = mapping.get(name)
    obj.information.update({
        f'{name}_{attr}': mapping.get(attr).format(full_name)
        for attr in ATTRIBUTES
    })

Note the use of an f-string for the key definition.

And, aside from that, I think you can remove the information variable as it is unused.

And, both my and your versions of the code don't handle missing keys situation - what if there is no such key in mapping?


Depth First Search Implementation (iterative) Here is my code for Depth First Search and, as far as I know, it is working fine on most cases. It is not very efficient as I have implemented it for the very first time..

Warning: It is only for bi-directional Graphs or Trees.. And it is not searching anything, just traversing. I think searching should be easy if it is traversing correctly..

def DFS(matrix,x):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j]=="farigh" or matrix[i][j]=="hogya":
                matrix[i].pop()

    stack = [x]
    Matrix=matrix
    print(Matrix)
    dimen=len(Matrix)
    rslt = [x]
    while stack:
        current=Matrix[stack[-1]-1]
        for j in range(len(current)):

                if current[j]==1 :
                    a=False
                    if (j+1 not in stack) and (j+1 not in rslt):
                        stack.append(j+1)
                        rslt.append(j+1)
                        print("stack",stack)
                        a= True
                        break
                if j+1== len(current):
                    current.append("farigh")

        if len(Matrix[stack[-1]-1]) == dimen and a == True :
            b=0
            current2= Matrix[stack[-1]-1]

            for e in range(len(current2)):
                if current2[e]==1:
                    b=b+1
            if b==1:
                stack.pop()
                current2.append("Hogya")

        if current[-1]=="farigh":
            stack.pop()

        print(stack,"stack")
    return(rslt,"rslt")

Let me know if you find any bugs.

Advice 1 (Space around binary operators)

Matrix=matrix

PEP-8 requires one space before a binary operator and after it:

Matrix = matrix

Advice 2 (Variable names should start from a lowercase letter)

Once again, you have a variable called Matrix. This applies to the function name DFS as well; I suggest you rename it to depth_first_search.

Advice 3

You print intermediate progress in your algorithm. Never do this. Think about what happens when your friend reuses your implementation: he or she will get overwhelmed with all that output that has no value. Also, it might slow down the execution of your algorithm, since printing goes down the chain to the very kernel. If you need to print anything, modify your algorithm to return a data structure which can do that, but let it do its work silently.

Advice 4

Your implementation seems to run in \$\Theta(V^2)\$ time. I suggest you convert the adjacency matrix to an adjacency list and input that list to your depth first search; this will bring down complexity to \$\Theta(E + V)\$, which is more efficient on sparse graphs (where \$E = o(V^2)\$).

Alternative implementation

Putting all together, I had this in mind:

from collections import deque

def adjacency_matrix_to_adjacency_list(adjacency_matrix):
    map = dict()
    j = 0

    for i in range(len(adjacency_matrix)):
        map[i] = []

    for adjacency_matrix_row in adjacency_matrix:
        for i in range(len(adjacency_matrix_row)):
            current_entry = adjacency_matrix_row[i]

            if current_entry == 1:
                map[j].append(i)

        j += 1

    return map

def depth_first_search(adjacency_matrix, source_node):
    open = deque([source_node])
    parents = {source_node: None}

    while open:
        current_node = open.pop()

        for child_node in adjacency_matrix[current_node]:
            if child_node not in parents.keys():
                parents[child_node] = current_node
                open.append(child_node)

    return parents


Invert dict of sets in Python What is the most Pythonic way to take a dict of lists and produce a new dict with the list items as keys and the previous dict's keys as list items.

Here's a visual explanation:

favorite_fruits = {"alice": {"apple", "orange"}, "bob": {"apple"}, "carol": {"orange"}}
people_by_fruit = {"orange": {"carol", "alice"}, "apple": {"bob", "alice"}}

Here's the best I have at the moment:

from collections import defaultdict
favorite_fruits = {"alice": {"apple", "orange"}, "bob": {"apple"}, "carol": {"orange"}}
people_by_fruit = defaultdict(set)
for person, fruit in favorite_fruits.items():
    for fruit in fruit:
        people_by_fruit[fruit].add(person)

Actually, I do believe you are quite good as you are. The simple inversion listed in this similar question (from comments) does not work when you want to split up the set values of your first dict. You could try something like a dict comprehension with a double for loop, but that doesn't work either as the second time you get a fruit it will overwrite the first one.

The only thing I would like to change in your answer is to use the plural of fruit, fruits, so that you don't do the for fruit in fruit which looks kind of hairy, and has the potential for code breaking as you're overwriting a variable with the same variable. Not good. In other words:

people_by_fruit = defaultdict(set)
for person, fruits in favorite_fruits.items():
    for fruit in fruits:
        people_by_fruit[fruit].add(person)