Speed up Magic square program I have written a Java program to calculate magic squares with recursion and backtracking. A 3*3 Magic square is calculated in about 1 sec, but a 4*4 needs about 50 minutes on my laptop with Intel i5. How i can improve the performance?

import java.util.Scanner;

public class MagicSquare {

private byte[][] square;
private byte magicNumber;
private long tmp = 0;

public MagicSquare() {

    Scanner sc = new Scanner(System.in);
    byte size = sc.nextByte();
    square = new byte[size][size];
    sc.close();
    magicNumber = (byte) ((size * size * size + size) / 2);

    long start = System.currentTimeMillis();
    solve(0, 0);
    printSquare();
    long duration = System.currentTimeMillis() - start;
    System.out.println(tmp);
    System.out.println(duration);
}

private boolean solve(int x, int y) {
    tmp++;
    if (x == square.length && y == square.length - 1 && isMagic()) {
        return true;
    }

    if (x == square.length) {
        y++;
        x = 0;
    }

    for (byte i = 1; i <= square.length * square.length; i++) {

        if (containsNumber(i) == false) {

            if (isValidRow(x) && isValidCol(y)) {

                square[x][y] = i;

                if (solve(x + 1, y) == true) {
                    return true;
                }
            }

        }
    }

    if (x < square.length && y < square.length) {
        square[x][y] = 0;
    }

    return false;
}

private boolean isMagic() {

    int diagonal1 = 0;
    int diagonal2 = 0;
    int col = 0;
    int row = 0;

    for (int i = 0; i < square.length; i++) {

        for (int j = 0; j < square[0].length; j++) {

            col = col + square[j][i];
            row = row + square[i][j];

            if (i == 0) {
                diagonal1 = diagonal1 + square[j][j];
                diagonal2 = diagonal2 + square[j][square.length - j - 1];
            }

        }

        if (col != magicNumber || row != magicNumber || diagonal1 != magicNumber || diagonal2 != magicNumber) {
            return false;
        }

        row = 0;
        col = 0;
    }

    return true;
}

private boolean isValidRow(int row) {

    int sum = 0;

    for (byte i = 0; i < square.length; i++) {
        sum = sum + square[row][i];
    }

    if (sum <= magicNumber)
        return true;

    return false;
}

private boolean isValidCol(int col) {

    int sum = 0;

    for (byte i = 0; i < square.length; i++) {
        sum = sum + square[i][col];
    }

    if (sum <= magicNumber)
        return true;

    return false;
}

public boolean containsNumber(byte value) {

    for (int i = 0; i < square.length; i++) {
        for (int j = 0; j < square[0].length; j++) {

            if (square[i][j] == value) {
                return true;
            }

        }
    }
    return false;
}

private void printSquare() {

    for (int i = 0; i < square.length; i++) {
        for (int j = 0; j < square[0].length; j++) {

            System.out.print(square[i][j] + " ");

        }
        System.out.println();
    }
}

public static void main(String[] args) {

     MagicSquare m = new MagicSquare();

   }
}

Any help is really appreciated.

You should use try-with-resources when you create a Scanner, and should only ever open a Scanner on System.in in your main program.  If you do this, you can pass the required size as an argument to the MagicSquare constructor:

public static void main(String[] args) {
    try(Scanner sc = new Scanner(System.in)) {
        byte size = sc.nextByte();
        MagicSquare m = new MagicSquare(size);
        m.printSquare();
    }
}

I’ve left construction of the magic square in the constructor (seems appropriate), but moved printing of the square to the main program.  After all, you might not always want to print the magic square.

You have numerous inefficiencies in your implementation:

You use square.length and (worse!) square[0].length when you could simply use size if you stored the magic square’s size as a size member.

You are testing x < square.length && y < square.length before resetting square[x][y] = 0;.  The x and y values should always be valid if you reach this step of the solve() method.  But there is one small possibility of them becoming invalid.  After filling in the last square...:

if (x == square.length && y == square.length-1 && isMagic()) {
    return true;
}

If it turns out isMagic() returns false, the method continues, loops over all values looking for an unused one (there aren’t any), and exits the method, returning false, but only after resetting square[x][y] = 0; which is why the check for invalid coordinates is required.  If instead you used:

if (x == square.length && y == square.length-1) {
    return isMagic();
}

... then the method always returns immediately, whether or not the completely filled in square is magic or not.  Now, the if guarding square[x][y] = 0; becomes unnecessary.

But the real issue comes from your algorithm as a whole.  You loop over \$N^2\$ squares, and for each square try each of the \$N^2\$ values, and for each value check each of the \$N^2\$ squares to see if the value is already used.  This is an \$O(N^6)\$ algorithm!

The usage check can be reduced to \$O(1)\$ by storing a “used” flag for each number:

boolean used[] = new boolean[size*size+1];

or

BitSet used = new BitSet(size*size + 1);

Then, simply checking used[value] or used.get(value) will return whether the value has been used or not.  Set the flag for the value when you store it in the square[][], and clear it when you replace the value.  That one change will reduce your time complexity from \$O(N^6)\$ to \$O(N^4)\$.

The next speed up can come from the observation that, if you take a solved NxN magic square, and erased one row and one column, you could trivially recreate the erased values.  If you know N-1 values in a row or column, the remaining value must be the desired total less the sum of the filled in values.  1 + 8 + ? = 15 ... the missing value is 15-(1+8)=6!  Of course, since you are generating candidate values, you need to ensure the computed value is (a) possible, and (b) unused.

Adding up numbers takes time.  Why keep adding the values?  You could keep a running total for each row and column:

square[x][y] = value;
row_sum[x] += value;
col_sum[y] += value;

... of course, you need to subtract the value out when backtracking, or replacing with a different candidate value.

Magic Squares are horizontally, vertically, and rotationally symmetric.  In a 4x4 magic square, there are only 3 unique locations the number “1” may appear in.  The remaining 13 locations would all correspond to simple rotations or mirroring of the square.  This would reduce the possible 4x4 squares from 16! permutations down to 3*15! ... an 81% reduction.  However, you are not finding all permutations; you stop once the first magic square is found, so this reduction in search space likely won’t produce much savings, if any.

While an 8x8 magic square seems huge, it is still within the realm of possibility.  The magicNumber, however, would be 260 which is too large for a byte.   Limiting the values themselves to a byte restricts the square to 15x15, and may be reasonable, but the sum should probably be an int.

This code ordering seems reversed!

    if (isValidRow(x) && isValidCol(y)) {
            square[x][y] = i;

square[x][y] should be filled in before the isValid checks are done.  Otherwise, an invalid state will prevent updating the square to a valid value.

“Invalid”, in this case, only happens if the sum becomes too large, and subsequent values will only make matters worse, but if the code is relying on that, it should break out of the candidate values loop once an invalid state is reached, instead of continuing with the next value.


Board Rotation Problem - Best Practices Problem: You are given a board containing lower-case letters and a word that you have to form. You can only take the letters from the front or the back, hence you have to rotate the board left or right. You have to use the greedy approach (choose which rotation lets you take the letter the fastest on each turn) and get a list of rotations necessary to get the word.

Example:

Initial Condition: Board: a g t c f  word: cat
Rotate Right -> f a g t c
Take c -> f a g t
Rotate Left -> a g t f
Take a -> g t f
etc

Code:

        public static List<Move> SolveLetterBoard(List<char> board, string word)
        {
            List<Move> result = new List<Move>();

            for (int i = 0; i < word.Length; i++)
            {
                char curChar = word[i];

                int leftPosition = board.IndexOf(curChar);
                int rightPosition = board.LastIndexOf(curChar);

                int location = 0;
                int where = leftPosition;
                Direction howToSpin = Direction.Left;

                //Is it easier to spin to the right or to the left
                if (board.Count - rightPosition <= leftPosition)
                {
                    where = board.Count - rightPosition - 1;
                    location = board.Count - 1;
                    howToSpin = Direction.Right;
                }

                Move curMove = new Move(howToSpin);
                for (int j = 0; j < where; j++)
                {
                    result.Add(curMove);

                    //Spin the board
                    char temp = board[location];
                    board.RemoveAt(location);
                    board.Insert(board.Count - location, temp);
                }

                //Remove the letter
                curMove = new Move(howToSpin, curChar);
                board.RemoveAt(location);

                result.Add(curMove);
            }

            return result;
        }

The code works, but I was told by the interviewer that the code "Your final code showed some lack of best practices", without any elaboration.
Could someone please advise what I did wrong.

Overall I'd consider your approach to be "procedural" rather than object-oriented, which might have contributed to the feedback about "lack of best practices"

I agree with Shanif that it would be best to create a class with different methods and avoid static.

Below is an example of the object-oriented approach.

Under the principle of encapsulation I wondered, "Should the Board expose its inner workings of how it generates the moves?" I decided no, and kept the Board's "calculation" methods private.

When I first posted this answer I knew that the various moves had enough in common to be candidates for inheritance. And, I got around to implementing it. Now the Move family of classes all derive from an abstract base class.

I also added the Solution class to capture the steps and help output them at the end.

Admittedly, this object model might be "overkill" for an app of this size. But, I was more interested in modeling the domain than in outputting the results as tersely as possible.

Despite its verbosity in meeting the currently-modest requirements, this object model provides a foundation upon which the app could grow to any size.

Or, to put it another way... Object-oriented programming is useful for many things. Winning at code golf is not among them.

Here's the output:

And the code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class App_LetterBoard
{
    public void Run()
    {
        var board = new Board("agtcf");
        board.Solve("cat");
        board.OutputResult();

        Console.WriteLine();
        var board2 = new Board("agtcfqwerqweroqiweru");
        board2.Solve("cat");
        board2.OutputResult();
    }
}

public class Board
{
    private string initial;
    private string target;
    private string current;
    private string result;
    private char next;

    public Solution Solution { get; private set; } = new Solution();

    public Board(string initial) => this.initial = initial;

    public void Solve(string target)
    {
        this.target = target;
        result = string.Empty;
        current = initial;
        var index = 0;

        Solution.Add(new Start(initial));

        while (!result.Equals(target))
        {
            next = target[index++];
            var distanceLeft = current.IndexOf(next);
            var distanceRight = current.Length - current.LastIndexOf(next) - 1;
            if (distanceLeft <= distanceRight)
            {
                captureLeft(distanceLeft);
            }
            else
            {
                captureRight(distanceRight);
            };

            result = $"{result}{next}";
        }
    }

    public void OutputResult()
    {
        Console.WriteLine($"Find -> {target}");
        Console.WriteLine(Solution.ToString());
    }

    private void captureRight(int distance)
    {
        for (var i = 0; i < distance; i++)
        {
            var move = new RotateRight(current);
            Solution.Add(move);
            current = move.After;
        }

        var take = new TakeRight(current);
        Solution.Add(take);
        current = take.After;
    }

    private void captureLeft(int distance)
    {
        for (var i = 0; i < distance; i++)
        {
            var move = new RotateLeft(current);
            Solution.Add(move);
            current = move.After;
        }

        var take = new TakeLeft(current);
        Solution.Add(take);
        current = take.After;
    }
}

public class Solution
{
    public List<Move> Moves { get; private set; } = new List<Move>();

    public void Add(Move move) => Moves.Add(move);

    public override string ToString()
    {
        var sb = new StringBuilder();
        sb.AppendLine(string.Join("\n", Moves.Select(m => m.ToString())));
        return sb.ToString();
    }
}

public abstract class Move
{
    public abstract string Name { get; }

    public string Before { get; private set; }

    public string After => advance();

    public Move(string remaining) => Before = remaining;

    public override string ToString() => $"{Name} -> {spread(After)}";

    protected abstract string advance();

    protected string removeLeft() => Before.Substring(1);

    protected string removeRight() => Before.Substring(0, Before.Length - 1);

    private string spread(string s) => string.Join(" ", s.ToArray());
}

public class Start : Move
{
    public override string Name => "Start";

    public Start(string current) : base(current) {}

    protected override string advance() => Before;
}

public class RotateLeft : Move
{
    public override string Name => "Rotate Left";

    public RotateLeft(string current) : base(current) { }

    protected override string advance() => $"{removeLeft()}{Before.First()}";
}

public class RotateRight : Move
{
    public override string Name => "Rotate Right";

    public RotateRight(string current) : base(current) { }

    protected override string advance() => $"{Before.Last()}{removeRight()}";
}

public abstract class Take : Move
{
    public override string Name => "Take";
    public Take(string current) : base(current) { }
}

public class TakeLeft : Take
{
    public TakeLeft(string current) : base(current) { }

    protected override string advance() => removeLeft();
}

public class TakeRight : Take
{
    public TakeRight(string current) : base(current) { }

    protected override string advance() => removeRight();
}


Business Layer - UI communication Taking the following cases in consideration.
Witch one would you prefer and why?
Suggestions appreciated.

Using Delegates

private void cmdDelete_enterClick(object sender, EventArgs e)
    {
    var accountManager = new BLAccountManager();
    accountManager.OnAccountInUse = (msg) => MessageBox.Show(msg);

    accountManager.OnConfirmation = (msg) =>
    {
        var dialogResult = MessageBox.Show(msg);
        return (dialogResult == DialogResult.OK);
    };

    accountManager.DeleteAccount(selectedAccountId);
}

 public class BLAccountManager
 {

public Action<string> OnAccountInUse;
public Func<string, bool> OnConfirmation;

public void DeleteAccount(string accountId)
{
    var bookingsUsingAccount = GetBookingsUsingAccount(accountId);
    if (bookingsUsingAccount.Count > 0)
    {
        OnAccountInUse("msg");
        return;
    }
    BankAccount account = GetAccount(accountId);
    if (OnConfirmation("confirm"))
    {
        account.Delete(false);
    }
}
}

Using Interfaces

  public interface IUICallback
  {
     void SendMessage(string message,string caption);
         bool Confirmation(string message,string caption);
  }

public class WinFormsUICallback : IUICallback
{
  public void SendMessage(string message, string caption)
  {
    MessageBox.Show(message, caption, MessageBoxButtons.OK,
                    MessageBoxIcon.Exclamation);
  }

  public bool Confirmation(string message, string caption)
  {
    DialogResult result = MessageBox.Show(message);
    return result == DialogResult.OK;
  }
}

  private void cmdDelete_Click(object sender, EventArgs e)
  {
        IUICallback uiCallback = new WinFormsUICallback();
    var accountManager = new BLAccountManager(uiCallback);
    accountManager.Delete(selectedAccountId);
  }

  public void Delete(string accountId)
  {
    BookingList bookingsUsingAccount =     bookingManager.GetBookingsUsingAccount(accountId);
    if (bookingsUsingAccount.Count > 0)
    {
            _uiCallback.SendMessage(msg, caption);
            return;
    }

    if (_uiCallback.Confirmation(confirmationMessage, caption))
        {
           account.Delete(false);
    }
   }

A third option is to use continuations:

public void DeleteAccount(string accountId, Action<string> OnAccountInUse, Func<string,bool> OnConfirmation)
{
    var bookingsUsingAccount = GetBookingsUsingAccount(accountId);
    if (bookingsUsingAccount.Count > 0)
    {
        OnAccountInUse("msg");
        return;
    }
    BankAccount account = GetAccount(accountId);
    if (OnConfirmation("confirm"))
    {
        account.Delete(false);
    }
}

edit: adding the usage, similar to the cases in the question

private void cmdDelete_enterClick(object sender, EventArgs e)
{
    var accountManager = new BLAccountManager();

    Func<string,bool> OnConfirmation = (msg) =>
    {
        var dialogResult = MessageBox.Show(msg);
        return (dialogResult == DialogResult.OK);
    };

    accountManager.DeleteAccount(selectedAccountId,
                                 (msg) => MessageBox.Show(msg),
                                 OnConfirmation);
}


Simple and efficient data structure for standard deviation queries in Java I have this data structure to which the user can add number or remove them, both in constant time. Also, there is a \$O(1)\$ operation for querying the standard deviation of the current contents of the structure:

StandardDeviationNumberSet.java

package net.coderodde.stat;

import java.util.HashMap;
import java.util.Map;

public class StandardDeviationNumberSet {

    private double sum;
    private double squareSum;
    private int numberOfElements;
    private final Map<Double, Integer> countMap = new HashMap<>();

    public void add(Number number) {
        double numberValue = number.doubleValue();
        Integer count = countMap.get(numberValue);

        if (count != null) {
            countMap.put(numberValue, count + 1);
        } else {
            countMap.put(numberValue, 1);
        }

        sum += numberValue;
        squareSum += numberValue * numberValue;
        numberOfElements++;
    }

    public double remove(Number number) {
        double numberValue = number.doubleValue();
        Integer count = countMap.get(numberValue);

        if (count != null) {
            if (count > 1) {
                countMap.put(numberValue, count - 1);
            } else {
                countMap.remove(numberValue);
            }

            sum -= numberValue;
            squareSum -= numberValue * numberValue;
            numberOfElements--;
            return numberValue;
        } else {
            return Double.NaN;
        }
    }

    public double getStandardDeviation() {
        checkSetHasAtleastTwoElements();
        double step1 = squareSum - sum * sum / numberOfElements;
        double step2 = step1 / (numberOfElements - 1);
        return Math.sqrt(step2);
    }

    private void checkSetHasAtleastTwoElements() {
        if (numberOfElements < 2) {
            throw new IllegalStateException(
                    "Computing the standard deviation requires at least two " +
                    "elements.");
        }
    }

    public static void main(String[] args) {
        StandardDeviationNumberSet set = new StandardDeviationNumberSet();

        set.add(1);
        set.add(1);
        set.add(3);

        System.out.println(set.getStandardDeviation());

        set.remove(1);

        System.out.println(set.getStandardDeviation());
    }
}

As always, any critique is much appreciated.

Overall I don't see any major problems with the code. There are some things I would change though:

Write unit tests.

Whenever I deal with mathematical classes, I think that it is obligatory to provide unit tests to verify correct computation and computational precision.

Add JavaDoc

Please add a JavaDoc to clarify whether it computes sample or population statistics.

Add comments

The use numberValue instead of number in the look ups to countMap has a significant but subtle difference that is easy to miss if you're not an expert. I would add comments to clarify this (you are correctly avoiding Integer(3) and Double(3) getting different counts).

Use map.getOrDefault

Since Java 8, which we have to assume is wide spread by this point, you can replace:

    Integer count = countMap.get(numberValue);

    if (count != null) {
        countMap.put(numberValue, count + 1);
    } else {
        countMap.put(numberValue, 1);
    }

with

    countMap.put(numberValue, countMap.getOrDefault(numberValue, 0) + 1);

Consider handling NaN and Inf inputs

Currently your code will silently break if any of the inputs contain NaN or Infinity. I would consider testing for these inputs and throwing if they are encountered.

Return type of remove is weird

As far as I can tell remove will return the input value or NaN if the input value was not removed. To me this feels very strange, I would much rather it'd return true if the statistics changed and false otherwise.

Change API to use double instead of Number

Currently your methods like public void add(Number number) first unbox the number into a double then rebox it into a Double. So calling add with a Double causes unnecessary boxing and unboxing.

Further more calling add with any of the primitive types (int,long,float etc) causes first a boxing to Number, then an unboxing to double then a re-boxing to Double (to use in countMap.get). This is a lot of unnecessary boxing and unboxing and will also generate a compiler warning on many systems.

So I would change:

public void add(Number number) {
    double numberValue = number.doubleValue();
    Integer count = countMap.get(numberValue);

    if (count != null) {
        countMap.put(numberValue, count + 1);
    } else {
        countMap.put(numberValue, 1);
    }

    sum += numberValue;
    squareSum += numberValue * numberValue;
    numberOfElements++;
}

to:

public void add(double number) {
    // JIT will use CSE to consolidate the auto boxings of number.
    countMap.put(number, countMap.getOrDefault(number, 0) + 1);
    sum += number;
    squareSum += number* number;
    numberOfElements++;
}

public void add(Number number){
    add(number.doubleValue());
}

and similarily for remove.

I would prefer to use the primitive double in the API because more often than not the user will do some computations to end up with the input value and will thus have a primitive double that they want to pass in. Other primitive types will automatically be type promoted to double. In the odd case that the user actually has a Number of some sort, we add an overload to handle it.

Add methods for querying the count and mean as well

You have all the data to get the mean value and sample count as well and these are commonly used in conjunction with the standard deviation so to me it makes sense to provide these methods as well as they are trivial.

Edit/Addendum

I would consider leaving the validation of removed values to the user. By having the countMap you add \$O\left(n\right)\$ memory requirement even if the user doesn't need the remove ability. And in many cases where you do need a remove (like a sliding window) the removal is guaranteed to be valid by the definition of the window.


Extract entities from sentences I have a function that extracts basic parts-of-speech words (NN,NNP,JJ,VBS etc.) from about 2000 sentences. I want to understand if there is a way to optimize so I can bring down the execution time (from about 12 secs right now to single digits) if possible.

import re, nltk, html

def extract_entities(text_list):

    entities=set()

    for sentence in text_list:
        try:

            tokens = nltk.word_tokenize(sentence)
            tagged = nltk.pos_tag(tokens)
            [entities.add(word.lower()) for word,pos in tagged
                 if pos in ['NN','NNP','NNS','NNPS','JJ','VBS','VBN','VBG','VBD']]

        except Exception as e:
            print('stage 1',e)

    return entities

Here are a few possible improvements:

Use a set for the positions you want and make it a constant. (This will give you a small speed-boost, because in is O(n) for lists, but O(1) for sets.)
Don't use a list-comprehension with side-effects for a loop.
Follow Python's official style-guide, PEP8. Specifically:

a) Don't do multiple imports

b) Put spaces around your operators

c) Put a space after a comma in an argument list
Limit the scope of your try..except

With these fixes, here is the final code, as I would write it:

import re
import nltk
import html

POSITIONS = {'NN','NNP','NNS','NNPS','JJ','VBS','VBN','VBG','VBD'}

def extract_entities(text_list):
    entities = set()
    for sentence in text_list:
        try:
            tokens = nltk.word_tokenize(sentence)
            tagged = nltk.pos_tag(tokens)
        except Exception as e:
            print('stage 1', e)
            continue
        for word, pos in tagged:
            if pos in POSITIONS:
                entities.add(word.lower())
    return entities


Finding the Intersection of Arrays I would like any advice on how to improve this code. To clarify what this code considers an intersection to be, the intersection of [3,3,4,6,7] and [3,3,3,6,7] is [3,6,7]. I would appreciate any improvements to make the code more readable or perform faster.

public ArrayList<Integer> findIt (int[] a, int[] b){
    ArrayList<Integer> result = new ArrayList<Integer>();
    Arrays.sort(a);
    Arrays.sort(b);
    int i = 0;
    int j = 0;
    while(i < a.length && j < b.length){
        if(a[i]<b[j])
            ++i;
        else if (a[i] > b[j])
            ++j;
        else{
            if (!result.contains(a[i]))
                result.add(a[i]);
            ++i;
            ++j;
        }
    }
    return result;
}

Algorithm

You're using a O(n log(n)) algorithm here, which could be O(n²) for difficult cases since contains() is O(n) and is called in a loop. Instead, use the property of HashSet: access is O(1), which means you can achieve this in O(n) time. My algorithm below simply keeps track of what it can add to the result. I can add everything that exists in the first list, but I should not add an item I already added.

See my tested code for my implementation:

public static List<Integer> intersection(List<Integer> a, List<Integer> b){
    Set<Integer> canAdd = new HashSet<Integer>(a);
    List<Integer> result = new ArrayList<Integer>();

    for (int n: b) {
        if(first.contains(n)) {
            result.add(n);
            // we wish to add only one n
            canAdd.remove(n);
        }
    }

    return result;
}

Comments on your code

You should return a List, not an ArrayList since it's an implementation detail. Using an ArrayList is OK here since adding at the end of it has O(1) amortized complexity. Otherwise, lists should be LinkedList (when adding to the beginning, not to the end, as @Landei points out).
Be careful about the names you choose. findIt doesn't seem to be appropriate, but removeDuplicates or intersection describes what the code does.


Computing a list from Graphite JSON I had a simple function.

def graphite_json(target):
    url = 'http://server/render/?format=json&amp;target={}&amp;from=-10days'.format(target)
    r = requests.get(url)
    return r.json()

This contacts  a (Graphite) server, uses the requests library to get JSON string and convert it to a native list. Simple.

Then I wanted to test it and made a complete mess. My thinking was: I'll soon need more Graphite functionality so best to create a class, also have the requests library as an external dependency so that I can test better. What I ended up with is this:

The Business Logic:

import json
import requests

class Graphite(object):

    def __init__(self, server_url = 'http://server', requests_module=requests):
        self.requests = requests_module
        self.server_url = server_url

    def get(self, metric):

        url = '{}/render/?format=json&amp;target={}'.format(
            self.server_url, metric)
        response = self.requests.get(url)
        return response.json()

The Test

import json
import os
import pytest
from api.graphite import Graphite

@pytest.fixture(scope="session")
def sample_response():
    dirpath = os.path.dirname(os.path.realpath(__file__))
    with open('{}/data/graphite_response.json'.format(dirpath), 'r') as content_file:
        content = content_file.read()
    return content

@pytest.fixture(scope="session")
def mock_graphite_requests(sample_response):
    class Requests(object):
        def get(self, url):
            if 'target' not in url:
                raise NotImplementedError('need a target for graphite stats')
            class Response(object):
                def __init__(self, data):
                    self.data = data
                def json(self):
                    return json.loads(self.data)
            return Response(sample_response)
    return Requests()

@pytest.fixture(scope="session")
def graphite(mock_graphite_requests):
    return Graphite(requests_module=mock_graphite_requests)

def test_graphite_metric(graphite, sample_response):
    data = graphite.get('summarize(stats.gauges.items,"12hour","avg")')
    assert data == json.loads(sample_response)

I see this as weak because:

The test is huge! I'll have to maintain it, probably.
What am I actually testing? I think I only test that this class converts the response from JSON.

How can I fix this mess?

You don't want to test the network, the requests or json libraries, you want to check that your method calls requests with a certain parameter (to check if your string interpolation worked and used the correct arguments) and that you return the return value of the JSON method of the response (to check whether you actually used and passed through the object).

At least those are things worthy of testing.  You can simplify your code with mocks if you like them, otherwise I'd say move the class definitions so that you have proper MockRequests and MockResponse classes, maybe the requests with a response constructor argument or so.

And the classes should be as simple as possible, the check for "target" isn't necessary, just check whether the incoming URL has the correct (pre-set) value.  The response shouldn't call anything, it should just return the (again pre-set) JSON object instead.


Python program to calculate GCD def gcd(a,b):
    if (a>b):
        r1=a
        r2=b
    else:
        r1=b
        r2=a
    if(r1%r2==0):
        print (r2)
    else:
        gcd(r2, r1%r2)
a= int(input("Enter a number"))
b= int(input("Enter a number"))
gcd(a,b)

This code is about finding the greatest common divisor of two numbers.
Are there any better methods?
How can I improve this code?

Bug:

When I input -6 and -3 I expect the result to be 3 but  I get a RecursionError exception instead:

RecursionError: maximum recursion depth exceeded in comparison

For the sake of UX:

Leave some space between the text you display and the data to input:

Enter a number6
Enter a number5

This would be the minimum better:

Enter a number: 6
Enter a number: 5

You know what your program does, but not the user, so your messages must be clear and precise. Ask the user not to input a number but an integer number. Otherwise this can mislead the user to input a real number, or input a character by mistake (or even try to break into your software):

Traceback (most recent call last):
  File "cr.py", line 12, in <module>
    a= int(input("Enter a number"))
ValueError: invalid literal for int() with base 10: 'g'

Your program does not give a choice for the user to exit. The minimum you can do for this purpose is to handle the KeyboardInterrupt exception corresponding to when the user presses Ctrl + c
The messages are intended to communicate with the user, so let him know what the programs does:

print('Computing the GCD of two numbers.\n')

Divide and conquer:

This is a consequence of the aformentioned: it is time to implement a function whose only purpose is care about the user's input:

def read_an_integer_user_input():
    a = None
    while type(a) != int:
        try:
            a = int(input('Enter an integer: '))
        except ValueError:
            print('I expect an integer value. Try again.')
        except KeyboardInterrupt:
            print('\nGoodbye!')
            break
    return a

Do not print, return:

We expect the function that computes something to return the result not to print it. Not only this is the function definition by essence, but this way you give more chance for your code to be reused and properly. So instead of coding print(r2) I would write return r2; by the way, do not leave space between  print and (.
Iterative version:

Given the recursion bug previsouly mentioned, I would opt for an iterative implementation of your code:

def compute_gcd(a,b):
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a%b
    return a

Full program:

Let us gather the elements above to build a small coherent program:

def compute_gcd(a,b):
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a%b
    return a

def read_an_integer_user_input():
   a = None
   while type(a) != int:
       try:
           a = int(input('Enter an integer: '))
       except ValueError:
           print('I expect an integer value. Try again.')
       except KeyboardInterrupt:
           print('\nGoodbye!')
           break
   return a

if __name__ == '__main__':
    print('Computing the GCD of two numbers.')
    a = read_an_integer_user_input()
    b = read_an_integer_user_input()
    if a and b:
       print('The GCD of {} and {} is: {}'.format(a, b, compute_gcd(a, b)))


Intro to Java - determine valid unique numbers This is an assignment for an intro to Java course.  It works with the test case given, but I would like to know if there is anything / a lot of things that should be different or could be better.

Specification:

  Write a Java application that accepts 5 “valid” numbers from the user.

  A valid number is between 50 and 100 inclusive.  If the user enters a
  number outside of the valid range, an error message should indicate
  this.  An invalid number is not counted as one of the 5.  The user
  might enter 50 invalid numbers, and the program will keep asking for
  numbers between 50 and 100.

  If the user enters a number that they have previously entered, this is
  counted as one of the 5.  A message appears that it is not unique.  A
  unique number is a valid number that has not been entered up to this
  point.  A non-unique number is a valid number that has already been
  entered.

  After each valid number  is entered, the count of the unique numbers
  entered so far is printed, and all of the unique numbers are printed
  on a single line.  (see example)

  When the user has entered 5 valid numbers, a message appears informing
  the user of how many unique, valid numbers were entered, and the
  unique numbers are printed again.

package partB;

import java.util.Scanner;

public class PartB {

    public static void main(String[] args) {

        int[] validNumber;
        int[] uniqueNumber;
        int input, numberOfUnique = 0;
        boolean validCheck, uniqueCheck;
        validNumber = new int[5];
        uniqueNumber = new int[5];

        Scanner userInput = new Scanner(System.in);

        for (int i = 0; i < validNumber.length; i++) {

            System.out.print("\nEnter an integer: \t");
            input = userInput.nextInt();

            validCheck = isValid(input);

            while (validCheck == false) {
                System.out.print("\nEnter an integer: \t");
                input = userInput.nextInt();
                validCheck = isValid(input);
            }

            if (validCheck == true) {

                uniqueCheck = isUnique(validNumber, input);
                validNumber[i] = input;
                if (uniqueCheck == true) {
                    numberOfUnique++;
                    uniqueNumber[i] = input;
                    System.out.println("Unique so far: \t\t" + numberOfUnique);
                    outputStatements(uniqueNumber);

                } else if (uniqueCheck == false) {
                    System.out.println(input + " is valid, but not unique");
                    System.out.println("Unique so far: \t\t" + numberOfUnique);
                    outputStatements(uniqueNumber);
                }
            }
        }
        System.out.println();
        System.out.println("You entered " + numberOfUnique
                + " unique valid numbers!");
        outputStatements(uniqueNumber);
    }

    public static boolean isValid(int validParameter) {
        boolean result;

        if (validParameter >= 50 && validParameter <= 100) {
            result = true;
        } else {
            result = false;
            System.out.println("The number " + validParameter
                    + " is out of the valid range.");
        }
        return result;
    }

    public static boolean isUnique(int[] array, int uniqueParamter) {
        boolean result = true;

        for (int i = 0; i < array.length; i++)
            if (array[i] != 0) {
                if (array[i] == uniqueParamter) {
                    result = false; // is NOT unique
                    break;
                } else {
                    result = true; // is unique

                }
            }
        return result;
    }

    public static void outputStatements(int[] array) {

        for (int i = 0; i < array.length; i++) {
            if (array[i] != 0) {
                System.out.print(array[i] + " ");
            }
        }
        System.out.println();
    }
}

It looks alright, but there are some improvements you can do. First of all, you can still split your program into smaller functions still, which really helps readability.

Also, something glaring to me is that your functions in "main" are acting as instance variables for the rest of the class, which should not be the case. You should choose where you declare your variables based on the necessity of their scope. If you only use the input int as a store from user input, it should only be declared in the method that gets input from the user.

For instance, you could omit the input int from main and declare it locally in the GetInputFromUser method.

In main:

for (int i = 0; i < validNumber.length; i++) {
     GetInputFromUser(validNumber, uniqueNumber);
}

The method:

public static void GetInputFromUser(int[] validNums, int[] uniqueNums) {
     int input = userInput.nextInt()
     while (!isValid(input)) {
          System.out.print("\nEnter an integer: \t");
          input = userInput.nextInt();
     }
     //Code ommitted

}

I didn't really have time to read all of the specifications carefully, but I hope this helped a bit! Also, you may want to declare the int arrays as instance variables to avoid passing them around all the time.


Back to Basics - Tic Tac Toe I've seen a few TTT related posts recently, and thought I might learn something or be reminded of certain techniques from attempting my own rendition. Here is that attempt! Hopefully any new coders can benefit from this as well. Any improvement suggestions are welcome, and numpy, scipy & bitwise operations are open to aid optimization.

ttt.py

import numpy as np
from random import randint

def print_board(board):
    print("""
  +---+---+---+
c | {}   {}   {} |
  +   +   +   +
b | {}   {}   {} |
  +   +   +   +
a | {}   {}   {} |
  +---+---+---+
    1   2   3
""".format(*list(x if x != '0' else ' ' for x in board)))

def check_for_win(board):
    def check_diagonal(dia):
        return '0' not in dia and len(set(dia)) == 1

    a = np.array(board).reshape(3, 3)

    # check lr diagonal
    if check_diagonal(a.diagonal()):
        return True

    # check rl diagonal
    if check_diagonal(np.fliplr(a).diagonal()):
        return True

    # check rows & cols
    for matr in [a, np.transpose(a)]:
        for row in matr:
            if '0' not in row and len(set(row)) == 1:
                return True

    return False

if __name__ == "__main__":
    board = ['0'] * 9
    codes = ('c1', 'c2', 'c3', 'b1', 'b2', 'b3', 'a1', 'a2', 'a3')
    turn, user = 1, 'X' if bool(randint(0, 1)) else 'O'
    print('Welcome! First to play is %s!' % user)
    print_board(board)

    while True:
        print('Player %s: ' % user)
        code = input().strip().lower()

        if code in codes:
            idx = codes.index(code)
            board[idx] = user
            print_board(board)

            if turn >= 5:
                if '0' not in board:
                    print("Aw, it's a draw!")
                    exit()
                elif check_for_win(board):
                    print('%s won in %d turns! Congratulations!' % (user, turn))
                    exit()

            user = 'X' if user == 'O' else 'O'
            turn = turn + 1
        else:
            print("Hmm, that's not a valid input.")

Input Validation

You aren’t completely validating input

X: a1
O: b2
X: a2
O: a3 (block)
X: a3 For the Win!?

Invalid Win/Draw Detection Logic:

X  O  X
O     O
X  O  X

Last move in centre: “Aw, it’s a draw!”???

exit()

This is a bad function to use.   It exits the Python interpreter.   Unconditionally.  Period.

When you want to change your code to play repeated games, run unit tests, etc., you won’t be able to.  Nothing will execute after exit().

Better would be to move the code into a function, and simply return to force an exit of the current local context, instead of an exit of the entire interpreter.

f-strings

You are using {} and .format() in print_board, and using %s and %d in "..." % (...) expressions.  Usually, you should try to avoid mixing formatting methods.  Both are awkward to use, as the value and the place the value goes are far apart in the code.  Avoid using the % style.

Additionally, instead of:

print('%s won in %d turns! Congratulations!' % (user, turn))

using an f-string moves the variables inside the format string:

print(f'{user} won in {turn} turns! Congratulations!')

(I’d leave the print_board function alone, but in other print formatting, f-strings are a win.  )


Getting the order of values so none are hidden if (parseInt(obj[0].actual) > parseInt(obj[0].projected) && parseInt(obj[0].projected) > parseInt(obj[0].le)) {
    biggesteClass = 'bar';
    biggestVal = obj[0].actual;
    secondClass ='bar2';
    secondVal = obj[0].projected;
    thirdClass ='bar3';
    thirdVal = obj[0].le;
} else if (parseInt(obj[0].actual) > parseInt(obj[0].le) && parseInt(obj[0].le) > parseInt(obj[0].projected)) {
    biggesteClass = 'bar';
    biggestVal = obj[0].actual;
    secondClass = 'bar3';
    secondVal = obj[0].le;
    thirdClass ='bar2';
    thirdVal = obj[0].projected;
} else if (parseInt(obj[0].projected) > parseInt(obj[0].actual) && parseInt(obj[0].actual) > parseInt(obj[0].le)) {
    biggesteClass = 'bar2';
    biggestVal = obj[0].projected;
    secondClass ='bar';
    secondVal = obj[0].actual;
    thirdClass ='bar3';
    thirdVal = obj[0].le;
}  else if (parseInt(obj[0].projected) > parseInt(obj[0].le) && parseInt(obj[0].le) > parseInt(obj[0].actual)) {
    biggesteClass = 'bar2';
    biggestVal = obj[0].projected;
    secondClass ='bar3';
    secondVal = obj[0].le;
    thirdClass ='bar';
    thirdVal = parseInt(obj[0].actual);
} else if (parseInt(obj[0].le) > parseInt(obj[0].actual) && parseInt(obj[0].actual) > parseInt(obj[0].projected)) {
    biggesteClass = 'bar3';
    biggestVal = obj[0].le;
    secondClass ='bar';
    secondVal = obj[0].actual;
    thirdClass ='bar2';
    thirdVal = obj[0].projected;
} else {
    biggesteClass = 'bar3';
    biggestVal = obj[0].le;
    secondClass ='bar2';
    secondVal = obj[0].projected;
    thirdClass ='bar';
    thirdVal = obj[0].actual;
}

What I am trying to do here is, I am setting the biggest, second, and third value to create an overlapped bar-chart for d3.js.

// Select, append to SVG, and add attributes to rectangles for bar chart
svg.selectAll("." + biggesteClass)
    .data(obj)
    .enter().append("rect")
        .attr("class", biggesteClass)
        .attr("height", function(d, i) {return (biggestVal * 10)})
        .attr("width","150")
        .attr("x", function(d, i) {return (i * 80) + 25})
        .attr("y", function(d, i) {return 280 - (biggestVal * 10)});
svg.selectAll("." + secondClass)
    .data(obj)
    .enter().append("rect")
        .attr("class", secondClass)
        .attr("height", function(d, i) {return (secondVal * 10)})
        .attr("width","150")
        .attr("x", function(d, i) {return (i * 80) + 25})
        .attr("y", function(d, i) {return 280 - (secondVal * 10)});
svg.selectAll("." + thirdClass)
    .data(obj)
    .enter().append("rect")
        .attr("class", thirdClass)
        .attr("height", function(d, i) {return (thirdVal * 10)})
        .attr("width","150")
        .attr("x", function(d, i) {return (i * 80) + 25})
        .attr("y", function(d, i) {return 280 - (thirdVal * 10)});

I needed to find the order of the values, since the smallest value has to go last not to get covered (hidden) by the bigger values.

The thing is, I think my first code snippet is messy and can be better, but not sure how to.

How can I refactor it not to look code-smelly?

As far as I can undestand the key point is that you need to have an order of the fields based on the fields value from the greater to the smaller.

I think you can solve it just sorting the fields like it is an array:

const firstElement = obj[0];
const sortedNamedValues = Object.keys(firstElement)
    .sort((a, b) => {
        return firstElement[b] - firstElement[a]
    });

So in sortedNamedValues are now the fields names sorted from the greater to the smaller.

Now I see the bar class is sticket to the field name: actual with bar, projected with bar2 and so on.

That could be done in a lookup table map:

const classesToValues = {
    actual: 'bar',
    projected: 'bar2',
    le: 'bar3'
};

So your assignment code will became:

const biggesteClass = classesToValues[sortedNamedValues[0]];
const biggestVal = firstElement[sortedNamedValues[0]];
const secondClass = classesToValues[sortedNamedValues[1]];
const secondVal = firstElement[sortedNamedValues[1]];
const thirdClass = classesToValues[sortedNamedValues[2]];
const thirdVal = firstElement[sortedNamedValues[2]];


Selecting a random student from a class list This selects a random student from a class list, stored in a .ss file:

from Tkinter import Tk,Button,StringVar,Entry,Label
import random, tkFileDialog, tkMessageBox
root= Tk()
root.wm_title("Random Student Selector")
current=StringVar()
kids=[]
addKidName=Entry(root)
def addkid():
    kids.append(addKidName.get())
addKid=Button(root, text="Add a student", command=addkid)
def choosekid():
    try:
        chosen=random.choice(kids)
    except IndexError:
        tkMessageBox.showinfo("Empty class", "You need to add a student")
    current.set(chosen)
chooseKid=Button(root,text="Pick random student", command=choosekid)
chosenKid=Label(root,textvariable=current)
def loadfile():
    global kids
    loadedfile=tkFileDialog.askopenfile(mode='r', filetypes=[("Text files","*.ss")])
    try:
        kids=loadedfile.read().split(",")
    except AttributeError:
        tkMessageBox.showinfo("No file selected", "You need to select a file")
loadFile=Button(root,text="Load a class",command=loadfile)
def savetofile():
    savefile=tkFileDialog.asksaveasfile()
    stringToSave=""
    for i in kids:
        stringToSave=stringToSave+i+","
    stringToSave=stringToSave[:-1]
    savefile.write(stringToSave)
saveToFile=Button(root,text="Save a file",command=savetofile)
 addKid.grid(row=0,column=1)
addKidName.grid(row=0,column=0)
chooseKid.grid(row=1,column=1)
chosenKid.grid(row=1,column=0)
loadFile.grid(row=2,column=0)
saveToFile.grid(row=2,column=1)
root.mainloop()

First off, things I like about this code:

you don't use StringVars for your Entry widgets. Lots of tutorials seem to use them, but they are largely unnecessary
I like that you grouped all of your grid commands together.

Now, the things I think need improving:

from Tkinter import Tk,Button,StringVar,Entry,Label

Best practices suggest you import the whole library with a shorthand name such as tk. You then can reference each of the widgets by the short name to make it absolutely clear where the code is coming from. Otherwise, if you were to use both Tkinter and ttk widgets at some point, it becomes  unclear if you're referencing a Tkinter widget or a ttk widget since they both export similar class names.

I suggest changing your import to this:

import Tkinter as tk

Then, change all references to Button to be tk.Button, etc. This extra little bit of typing will make your code much easier to read and maintain over time.

It's great that you grouped all of your grid statements together.  However, the rest of your code is oddly interleaved. You have functions intermixed with code.

Instead of doing this:

addKidName=Entry(...)
def addkid(): ...
addKid=Button(...)
def choosekid(): ...

group all of your functions together, and all your widgets together.

def addkid(): ...
def choosekid(): ...
def loadfile(): ...
def savetofile(): ...
...
addKidName=Entry(...)
addKid=Button(...)
...

If you use grid  you should always do three things:

1) explicitly declare a sticky attribute for each widget
 2) always use rowconfigure to give at least one row a positive, non-zero weight (even if it's an invisible row below all other rows)
 3) always use columnconfigure to give at least one column a positive, non-zero weight (even if it's an invisible column to the right of all other columns)


JavaScript architecture example on an HTML page I'd want an advise about the following idea that I have for organizing JavaScript when it comes to creating an HTML page. My group will be starting a new project and the approach that I'm trying to come up with will be large scale because every HTML page will be using it. Below I'll show a sample code and I'd like it to be reviewed and advised if you think that's a good approach. I did not find anywhere anything better it seems.

There are 4 files:

${root}/billing.html: contains an input box for the name on credit card
${root}/js/com/mycompany/common/common.js: initializes logging and error handling
${root}/js/com/mycompany/common/Url.js: class that is used to perform an AJAX call
${root}/js/com/mycompany/aproject/billing.js: initializes things on the billing page

common.js:

var com_mycompany_common_common = function() {

    function log(message) {
        console.log((new Date()) + ': ' + message);
    }

    function init() {
        window.onerror = function(message) {
            log('Unhandled error: ' + message);
        }
    }

    return {
        log: log,
        init: init
    }
} ();

$(document).ready(function() {
    try {
        com_mycompany_common_common.init();
    } catch (e) {
        console.log('Error during initialization: ' + e);
    }
});

Url.js:

function com_mycompany_common_Url(url) {
    this.url = url;
}

com_mycompany_common_Url.prototype.addParameter(name, value) {
    this.url += '?' + name + '=' + value;
}

com_mycompany_common_Url.prototype.ajax() {
    com_mycompany_common_common.log('Send ajax to: ' + this.url);
}

billing.js:

var com_mycompany_aproject_billing = function() {

    function init() {
        $('#submitButton').click(function() {
            Url url = new com_mycompany_common_Url('http://bla.com/process/billing');
            var creditCardName = $('#ccName').val();
            url.addParameter('name', creditCardName);
            url.ajax();
        }
    }

    return {init: init};
} ();

$(document).ready(function() {
      try {
           com_mycompany_aproject_billing.init();
      } catch (e) {
           com_mycompany_common_common.log('Error during initialization: ' + e);
      }
});

billing.html:

<!DOCTYPE html>

        <title>Billing</title>

        Enter name on credit card: <input type="text" id="ccName" />

        <button id="submitButton">Submit Payment</button>

You have globals everywhere. Your cross module communication strategy is "uniquely named globals everywhere". I assume you know globals are bad but modul8 has a good article about it

Use a module bundling strategy using tools like browserify or modul8

// common.js
function log(message) {
    console.log((new Date()) + ': ' + message);
}

window.onerror = function(message) {
    log('Unhandled error: ' + message);
}

module.exports = { log: log };

You just got rid of those ugly company names as your namespacing strategy. And you also removed that ugly boilerplate code. Here your common.js file exports an object with the log method

// Url.js
var log = require("common.js").log;

function Url(url) {
    this.url = url;
}

Url.prototype.addParameter = function(name, value) {
    this.url += '?' + name + '=' + value;
};

Url.prototype.ajax = function() {
    log('Send ajax to: ' + this.url);
};

module.exports = { Url: Url };

You Url module explicitly requires your common file. It now has the log method.

//billing.js
var Url = require("Url.js").Url,
    $ = require("jQuery");

$('#submitButton').click(function() {
    var url = new Url('http://bla.com/process/billing');
    var creditCardName = $('#ccName').val();
    url.addParameter('name', creditCardName);
    url.ajax();
}

And billing explicitly requires Url and jQuery.

// billing.html
<!DOCTYPE html>

        <title>Billing</title>

        Enter name on credit card: <input type="text" id="ccName" />

        <button id="submitButton">Submit Payment</button>

And your billing html file loads a single precompiled billing bundle.


Enumerate multi-subsets for a multiset in Python Given a multiset (i.e., allow repeated elements), enumerate all distinct multi-subsets without using itertools(order is not important).

Example: Let s = 'a,a,b' then print to the console,

a
a,a
b
a,b
a,a,b

I am wondering if my approach (presented below) is efficient, and would appreciate stylistic advice. For example, I am not used to using *args, and in places my approach feels kludgey.

My attempt:

Count items in s:

A = s.split(',')
A_counts = defaultdict(int)
for i in A:
    A_counts[i] += 1

In our example we have {'a':2, 'b':1}. Use this to enumerate all tuples of points in the product of sets range(3)xrange(2), i.e., [[0,0],[0,1],[1,0],[1,1],[2,0],[2,1]]. Each tuple corresponds to a unique multi-subset. For example, the tuple [2,1] corresponds to a,a,b and the tuple [2,0] corresponds to a,a.

Enumerate all tuples:

def enumerate_tuples(*args):
    res = [[i] for i in range(args[0])]
    for arg in args[1:]:
        tmp = [j + [i] for i in range(arg) for j in res]
        res = tmp
    return res

Now print the corresponding multi-subset to console:

ordered_alphabet = list(A_counts)
args = (A_counts[i] + 1 for i in ordered_alphabet)
tuples = enumerate_tuples(*args)

# cycle through tuples printing corresponding string
for tup in tuples:
    if sum(tup) == 0: continue
    group = [ordered_alphabet[i] for i in range(len(tup)) for _ in range(tup[i])]
    out = ','.join(group)
    print(out)

It's a good idea to divide code into functions — this makes it easier to document, test and reuse the code. Here it would make sense to have a function defined like this:

def sub_multisets(elements):
    "Generate the sub-multisets of the iterable elements."
    # code goes here

Then you could call sub_multisets(s.split(',')) or whatever in the main program.
The code in the post omits one of the sub-multisets, namely the empty sub-multiset.
Wherever you have code using defaultdict(int), consider using collections.Counter instead. This is a specialized data structure for counting things. Here you could write:

A_counts = Counter(s.split(','))

with no need for a loop.
To compute the Cartesian product of some collections, use itertools.product. Here we need something like:

product(*[range(n + 1) for n in A_count.values()])

For example:

>>> A_count = Counter('aab')
>>> list(product(*[range(n + 1) for n in A_count.values()])
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]

which are the sub-multiset counts required.
To build the sub-multiset, we can use the Counter.elements method, for example if we have the counts (1, 1) we can write:

>>> tuple(Counter(dict(zip(A_count.keys(), (1, 1)))).elements())
('a', 'b')

Another way to do this would be to use itertools.repeat and itertools.chain:

>>> tuple(chain.from_iterable(repeat(k, n) for k, n in zip(A_count.keys(), (2, 1))))
('a', 'a', 'b')

but I think the Counter.elements approach is slightly simpler.

Putting all this together:

from collections import Counter
from itertools import product

def sub_multisets(elements):
    """Generate the sub-multisets of the iterable elements.
    For example:

    >>> [''.join(s) for s in sub_multisets('aab')]
    ['', 'b', 'a', 'ab', 'aa', 'aab']

    """
    counts = Counter(elements)
    for sub_counts in product(*[range(n + 1) for n in counts.values()]):
        yield Counter(dict(zip(counts.keys(), sub_counts))).elements()


Runge-Kutta 2nd order of differential equations Could I improve this somehow (not numerically, just C-wise)?  Do I need to allocate the array since I am returning it and not just using it inside the function?

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

/* Approximates a solution to a differential equation on the form:
   y'(t) + ay(t) = x(t)
   y(0) = b
*/
double* runge_kutta_2nd_order(double stepSize, double a, double b, double (*x) (double), double upto)
{
    int resultSize = ((int) (upto / stepSize)) + 2;
    double yt = b;
    double time;
    double k1,k2,ystar1,ystar2;
    int index = 1;

    //double *results = (double*) malloc(resultSize * (sizeof(double)));
    double *results = malloc(resultSize * sizeof(*results));
    if(results == NULL)
    {
        printf("\nCould not allocate memory. Exiting program.");
        exit(0);
    }

    results[0] = b;

    for(time = 0; time < upto; time += stepSize) //<=
    {
        k1 = x(time) - a * yt;
        ystar1 = yt + stepSize * k1;
        k2 = x(time + stepSize) - a * ystar1;
        ystar2 = yt + (k1 + k2) / 2 * stepSize;
        yt = ystar2;
        results[index] = ystar2;
        index++;
    }
    return results;
}

void free_results(double **r)
{
    free(*r);
    *r = NULL;
}

double insignal(double t)
{
    return exp(t/2)*(sin(5*t) - 10*cos(5*t));
}

int main(void)
{
    int i;
    double *res = runge_kutta_2nd_order(0.01,-1,0,&insignal,10);

    printf("\nRunge Kutta 2nd order approximation of the differential equation:");
    printf("\ny'(t) - y(t) = e^(t/2) * (sin(5t) - 10cos(5t))");
    printf("\ny(0) = 0");
    printf("\n0 <= t <= 10");

    for(i=0; i<1001; i+=100){
        printf("\ni = %lf => y = ", 0.01*i);
        printf("%lf", res[i]);
    }
    printf("\n");

    free_results(&res);

    return 0;
}

It is more usual to take a pointer to an already-allocated array, rather than allocate an array within the function itself.  This allows the calling function to choose the best kind of allocation.

When doing this you'd likely also take the number of indexes to fill as an input, deriving the step size from that:

/* resultsize must be >= 2 */
void runge_kutta_2nd_order(double results[], size_t resultsize, double a, double b, double (*x) (double), double upto)
{
    const double stepSize = upto / (resultsize - 1);
    double yt = b;
    size_t index;

    results[0] = b;

    for (index = 1; index < resultsize; index++)
    {
        const double time = index * stepSize;
        const double k1 = x(time) - a * yt;
        const double ystar1 = yt + stepSize * k1;
        const double k2 = x(time + stepSize) - a * ystar1;
        const double ystar2 = yt + (k1 + k2) / 2 * stepSize;
        yt = ystar2;
        results[index] = ystar2;
    }
}

So, for example, in this case you could use automatic allocation in main():

int main(void)
{
    int i;
    double res[1001];

    runge_kutta_2nd_order(res, 1001, -1, 0, &insignal, 10);

    printf("\nRunge Kutta 2nd order approximation of the differential equation:");
    printf("\ny'(t) - y(t) = e^(t/2) * (sin(5t) - 10cos(5t))");
    printf("\ny(0) = 0");
    printf("\n0 <= t <= 10");

    for(i=0; i<1001; i+=100){
        printf("\ni = %f => y = ", 0.01*i);
        printf("%f", res[i]);
    }
    printf("\n");

    return 0;
}


Code Concision - String Capitalization I'm working on a few JavaScript functions for myself that I hope come in handy sometime.  The first I wrote was a Capitalization function (yeah i know, real original. whatever)
I was just wondering if

I'm doing anything incredibly stupid
There's anyway to make the code below more concise (like cool JS concision features i don't know about, tightening down on program flow, etc.)
There's anything else cool i can do

Code:

String.prototype.capitalize = function(everyWord) {
    var words = this.split(" ");
    if (everyWord == true) {
        for (i = 0; i < words.length; i++) {
            words[i] = cap(words[i]);
        }
    }
    else {
        words[0] = cap(words[0]);
    }
    return words.join(" ");

    function cap(word) {
        return word.charAt(0).toUpperCase() + word.slice(1);
    }
};
var x = "abraham lincoln yada yada";
x = x.capitalize();
alert(x);
x = x.capitalize(true);
alert(x);

Thanks!
http://jsfiddle.net/thomas4g/LpwRn/31/

Live example

String.capitalize = function(str, everyWord) {
    return _.map(_.words(str), function(val, key) {
        return key === 0 || everyWord ? _.capitalize(val) : val;
    }).join(" ");
};

Write to String not String.prototype. Extending native prototypes is not friendly.

Use underscore and underscore.string.

Basically don't re-invent the wheel ;)


Organizing a long string into a list of lists This code loads the data for Project Euler problem 18, but I feel that there must be a better way of writing it.  Maybe with a double list comprehension, but I couldn't figure out how I might do that.  It is a lot more difficult since the rows to split up are not uniform in length.

def organizeVar():
    triangle = "\
75,\
95 64,\
17 47 82,\
18 35 87 10,\
20 04 82 47 65,\
19 01 23 75 03 34,\
88 02 77 73 07 63 67,\
99 65 04 28 06 16 70 92,\
41 41 26 56 83 40 80 70 33,\
41 48 72 33 47 32 37 16 94 29,\
53 71 44 65 25 43 91 52 97 51 14,\
70 11 33 28 77 73 17 78 39 68 17 57,\
91 71 52 38 17 14 91 43 58 50 27 29 48,\
63 66 04 68 89 53 67 30 73 16 69 87 40 31,\
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
    triangle = [row for row in list(triangle.split(","))]
    adjTriangle = []
    for row in range(len(triangle)):
        adjTriangle.append([int(pos) for pos in triangle[row].split(" ")])
    return adjTriangle

The code converts this string into a list of lists of ints where the first list contains 75, the second list 95, 64, the third list 17, 47, 82, the fourth list 18, 35, 87, 10 and so on to the bottom row.


MySQL GROUP BY id, then show name I have a users table where some users have the same name:

+----+------+
| id | name |
+----+------+
|  1 | Joe  |
|  2 | Joey |
|  3 | Joe  |
+----+------+

... and a purchases table:

+---------+--------+
| user_id | amount |
+---------+--------+
|       1 |    400 |
|       1 |    200 |
|       2 |    700 |
|       3 |    100 |
+---------+--------+

Goal

I want to show for each user, their name and the sum of their purchases like this (yes there are two people named Joe, no worry):

+------+-------+
| name | total |
+------+-------+
| Joe  |   600 |
| Joey |   700 |
| Joe  |   100 |
+------+-------+

My code

SELECT name, totals.total
FROM
  (
    SELECT user_id, SUM(amount) total
    FROM purchases
    GROUP BY user_id
  ) AS totals
INNER JOIN users u
ON totals.user_id=u.id;

It works, producing the right output.

How can I improve this code, in particular by not using a subquery?

Table creation code:

CREATE TABLE users (id INT UNIQUE NOT NULL AUTO_INCREMENT PRIMARY KEY, name VARCHAR(20));
INSERT INTO users (name) VALUES ('Joe'), ('Joey'), ('Joe');
CREATE TABLE purchases (user_id INT NOT NULL, amount INT);
INSERT INTO purchases (user_id, amount) VALUES (1, 400), (1, 200), (2, 700), (3, 100);

If you don't want to use a subquery, you can include the second table with a join before the group by:
SQL Fiddle

SELECT max(name) name, SUM(amount) total
FROM purchases
INNER JOIN users on users.id = purchases.user_id
GROUP BY user_id
ORDER BY user_id

yielding

name    total
Joe       600
Joey      700
Joe       100


Generating a list of alternatively positioned odd and even number out of an array of unsorted integers I had an half an hour interview with Microsoft for an intern position.  I was asked to generate a list of alternatively positioned odd and even number out of an array of unsorted integers.  I guess it was below the interviewer expectations since I did not get the offer.  Can any one give me some hints on improving my code?

import java.util.ArrayList;

public class EvenOddArray {

private int min(int n, int m)
{
    int min;
    if (n > m){
        min = m;
    }
    else {
        min = n;
    }
    return min;
}

public ArrayList<Integer> generateEvenOddArray(int[] list)
{
    ArrayList<Integer> oddList = new ArrayList<Integer>();
    ArrayList<Integer> evenList = new ArrayList<Integer>();
    ArrayList<Integer> resultList = new ArrayList<Integer>();

    for (int number : list) {
        if (number%2 == 0){
            evenList.add(number);
        }
        else {
            oddList.add(number);
        }

    }

    int numberOfEvenNumbers = evenList.size();
    int numberOfOddNumbers = oddList.size();
    int minOfOddAndEven = min(numberOfEvenNumbers,numberOfOddNumbers);
    ArrayList<Integer> longestList = getLongestList(evenList,oddList);

    int i ;
    for (i = 0; i < minOfOddAndEven; i++) {
        resultList.add(2*i,oddList.get(i) );
        resultList.add(2*i+1,evenList.get(i));
    }
    if(longestList != null ){
        for (int j = i; j < longestList.size(); j++) {
            resultList.add(longestList.get(j));
        }
    }
    return resultList;

}
private ArrayList<Integer> getLongestList(ArrayList<Integer> listone,
        ArrayList<Integer> listTwo) {
    if (listone.size()<listTwo.size()){
        return listTwo;
    }
    else if (listone.size()>listTwo.size()){
        return listone;
    }
    return null;
}

You probably should have used Math.min(). Even if it was requested by the interviewer to not use anything else besides ArrayList, min can be written much more concise as

return n <= m ? n : m

(1 line of code vs. 8)
This loop is little bit ugly:

  for (i = 0; i < minOfOddAndEven; i++) {
    resultList.add(2*i,oddList.get(i) );
    resultList.add(2*i+1,evenList.get(i));
}

While I think it should work (don't have a Java compiler handy to try) it's a bit confusing to add the numbers at specified indices. I think it is legal to call add(index, item) where index == size() which should add an element to the end of the list. So your code happens to work but you need to look twice to make sure. It's totally unnecessary to do this. You could have simply done:

for (i = 0; i < minOfOddAndEven; i++) {
    resultList.add(oddList.get(i));
    resultList.add(evenList.get(i));
}

Same result but cleaner.
Copying the remainder of the list could have been done with subList:

if (longestList != null)
{
    resultList.addAll(longestList.subList(minOfOddAndEven, longestList.size());
}

Overall I think the interviewer might have wanted to see the use of iterators. You could have greatly simplified your code with this:

Iterator<Integer> odds = oddList.iterator();
Iterator<Integer> evens = evenList.iterator();

while (odds.hasNext() || evens.hasNext())
{
     if (odds.hasNext())
     {
         resultList.Add(odds.next());
     }
     if (evens.hasNext())
     {
         resultList.Add(evens.next());
     }
}

This way you iterate over both lists at once and don't have to implement the "which list is longer and then copy the remainder part"


Formatted output of a structure I've implemented a to_string function that takes a player_t instance and format it into a string.

Code:

#include <stdio.h>
#include <string.h>

typedef struct player {
  int id;
  float points;
  char display_name[256];
} player_t;

#define MAX_OUTPUT_SIZE sizeof(int) + sizeof(float) + 256

void to_string(player_t, char [MAX_OUTPUT_SIZE]);

int main()
{
  char stringified[MAX_OUTPUT_SIZE];

  player_t p1 = {.id = 1, .points = 17.4, .display_name = "Tester"};

  to_string(p1, stringified);

  printf("player: %s\n", stringified);

  return 0;
}

void to_string(player_t player, char output[MAX_OUTPUT_SIZE])
{
  char temp[MAX_OUTPUT_SIZE];

  snprintf(temp, sizeof(temp), "\n\tid: %d", player.id);
  strncat(output, temp, 6 + 1);

  snprintf(temp, sizeof(temp), "\n\tpoints: %f", player.points);
  strncat(output, temp, 10 + 9);

  snprintf(temp, sizeof(temp), "\n\tdisplay_name: %s", player.display_name);
  strncat(output, temp, 18 + 256);
}

Output:

player:
    id: 1
    points: 17.400000
    display_name: Tester

Questions:

Is there a better way to define MAX_OUTPUT_SIZE instead of manually adding the size of each element?
Is there a better way to implement to_string instead of using a temporary variable, the separate combination of strncat & snprintf and explicitly counting the characters for strncat?.
Am I over complicating my usage of snprintf & strncat?
(slightly out of topic) Do you recommend any C project to read it's code that implement similar functionalities and is following best practices?

Thanks in advance and I'm sorry if I've missed any obvious mistakes (still in the process of learning C with Ruby/JS background).

The MAX_OUTPUT_SIZE constant does not correctly account for how many characters might be generated, and it does not agree with the calculation made within to_string().  In particular, note that sizeof (int) and sizeof (float) indicate how much memory is required to store values of those types; that's not at all related to how many characters are required to print them.

The correct calculation is hard to get right: you need to add the longest int value (formatted as a decimal), the longest float value (as a float) and the longest display_name, as well as all your fixed text and the terminating NUL.

It's hard to do that portably.

It should also be noted that a function parameter of char[MAX_OUTPUT_SIZE] decays to a pointer, and you have no guarantee that it points to an array of the declared size.

The right way to output into a char array is to pass the length as a separate parameter, and for your output function to indicate the required length if it fails (either by the return value, or via an output parameter).  Consider a function interface similar to snprintf() - but be aware of the common ways of mis-calling snprintf() and make sure you avoid them.

Other comments:

Avoid passing your player by value - it's much cheaper to pass a pointer to a readonly struct.
With the code below, we can check the worst-case output by constructing a struct player with id of INT_MIN, points of -FLT_MAX and a maximum-length display_name, and a debug version will tell us how big a buffer is required.  You can then modify the constant to the value indicated.
If you later internationalize the program, the fixed portion of the strings are no longer fixed.  You might even have to resort to the technique of calling snprintf(NULL, 0, format, args...) to measure the size, then allocating sufficient memory with malloc().  That adds to your work, as you then need to ensure that the allocated memory is correctly freed.

#include <stdio.h>
#include <string.h>

typedef struct player {
  int id;
  float points;
  char display_name[256];
} player_t;

/* Will write no more than length characters, including the terminating NUL.
   The return value indicates the number of characters to be written, excluding the NUL.
   A return value of length or more indicates a truncated write */
size_t to_string(char *output, size_t length, const player_t *player)
{
    size_t required_len =
        snprintf(output, length,
                 "\n\tid: %d\n\tpoints: %f\n\tdisplay_name: %s",
                 player->id, player->points, player->display_name);
#ifndef NDEBUG
    if (required_len >= length)
        fprintf(stderr,
                "Buffer too small: needs %zd but %zd was supplied\n",
                required_len+1, length);
#endif
    return required_len;
}

static const size_t MAX_OUTPUT_SIZE = 5;

#include <limits.h>
#include <float.h>
int main()
{
  char stringified[MAX_OUTPUT_SIZE];

  player_t p1 = {.id = 1, .points = 17.4, .display_name = "Tester"};

  if (to_string(stringified, sizeof stringified, &p1) >= sizeof stringified) {
      fprintf(stderr, "Buffer too small!\n");
      return 1;
  }

  printf("player: %s\n", stringified);
  return 0;
}


Function to display an alert It's a user alert script. It worked in every browser I tested. But the function itself looks very messy/repetitive. Is there any way to make this cleaner?

function message(text) {
    var alert = document.createElement('div');
    var alertText = document.createTextNode(text);
    var alertCloseButton = document.createElement('i');
    var buttonText = document.createTextNode('close');
    var shadow = document.createElement('div');

    alert.className = 'alert-text';
    alertCloseButton.className = 'material-icons';
    alertCloseButton.id = 'close-alert';
    alertCloseButton.setAttribute('onclick', 'function() { var a = this.parentNode; var s = a.parentNode; s.parentNode.removeChild(s)}');
    alertCloseButton.onclick = function() { var a = this.parentNode; var s = a.parentNode; s.parentNode.removeChild(s) };
    alertCloseButton.appendChild(buttonText);
    alert.appendChild(alertCloseButton);
    alert.appendChild(alertText);
    shadow.className = 'shadow';
    shadow.appendChild(alert);

    document.body.appendChild(shadow);
}
var button = document.querySelector('button');
button.addEventListener('click', function(){
    message('Button clicked');
});

Here's the code working: https://jsfiddle.net/3aouyfz7/

Explanation:

It's true that using objects can become messy after a while. That's why Template Literals and innerHTML are so powerful in this situation.

I would highly advise to avoid using parentNode when attempting to remove HTML, you may unintentionally remove something in the future if you decide to make your alert HTML more complex.

To solve this, create a container element that is accessible by your onclose method.

Also, I would also advise to not overwrite existing objects. Why not name alert to something else?

Don't add onclick events directly in the HTML, it's messy.

Solution:

function message(text) {

  const container = document.createElement("div");

  const onClose = ()=>container.remove();

  container.innerHTML = `

        close
        ${text}

  `;

  document.body.appendChild(container);

  document
    .querySelector('i#close-alert')
    .addEventListener("click", onClose);
}

Working Example:

function message(text) {

  const container = document.createElement("div");

  const onClose = ()=>container.remove();

  container.innerHTML = `

        close
        ${text}

  `;

  document.body.appendChild(container);

  document
    .querySelector('i#close-alert')
    .addEventListener("click", onClose);
}

const button = document.querySelector('button');
button.addEventListener('click', function() {
  message('Button clicked');
});
* {
  box-sizing: border-box;
}

.shadow {
  width: 100%;
  height: 100%;
  background-color: rgba(0, 0, 0, .5);
  position: fixed;
  top: 0;
  left: 0;
  display: flex;
  align-items: center;
  justify-content: center;
  z-index: 98;
}

.alert-text {
  border: 1px solid #aaa;
  padding: 2.5em;
  min-height: 10%;
  width: auto;
  max-width: 80%;
  background: #fff;
  z-index: 99;
  position: relative;
  text-align: center;
}

.alert-text i {
  position: absolute;
  top: 0;
  right: 0;
  color: #777;
  cursor: pointer;
  padding: .5rem;
}

.alert-text i:hover {
  color: #444
}
<!DOCTYPE html>

  <title></title>

  <link rel="stylesheet" type="text/css" href="https://fonts.googleapis.com/icon?family=Material+Icons">

Page content

  <button>alert</button>


PHP and MySQLi login script - is it secure / am I doing something wrong? Below is the code for my login page. I haven't really used MySQL (especially OOP) before, so I'd like to know if I'm doing something inherently wrong. The code is working as expected, but I don't trust my knowledge of SQL so much that I'd use this code publicly before asking someone to review it.

So please, tell me any and all problems you find within.

$link = new mysqli('host', 'user', 'pass', 'database');

if($link->error)
    die('Couldn\'t connect to the database. Error: '.$link->error);

if(isset($_POST['username']))
{
    if(!$stmt = $link->prepare('SELECT password FROM accs WHERE username = ?'))
    {
        echo 'Couldn\'t prepare the database query.';
        if($link->error)
            die(' Error: '.$link->error);
    }

    if(!$stmt->bind_param('s', $_POST['username']))
    {
        echo 'Couldn\'t bind parameters to the query.';
        if($stmt->error)
            die(' Error: '.$stmt->error);
    }

    if(!$stmt->execute())
    {
        echo 'Couldn\'t execute the query.';
        if($stmt->error)
            die(' Error: '.$stmt->error);
    }

    if(!$stmt->bind_result($result))
    {
        echo 'Couldn\'t bind the query results.';
        if($stmt->error)
            die(' Error: '.$stmt->error);
    }

    switch($stmt->fetch())
    {
        case NULL:
            die('Username not found.');
            break;

        case FALSE:
            echo 'Couldn\'t fetch the results.';
            if($stmt->error)
                die(' Error: '.$stmt->error);

            break;

        case TRUE:
            // I don't actually store the password in plaintext.
            if($_POST['password'] === $result)
                echo 'Logged in';
            else
                echo 'Wrong password';

            break;
    }
    $stmt->close();
}
else
    die('Error, no username specified.');

$link->close();

The only thing I could think of myself is that I should make a function for the $link->prepare(), $stmt->bind_param(), $stmt->execute() and $stmt->bind_result() conditionals, but that's not too big of a problem, just a design-quirk.

Oh, and if in the future I want to get more than one result from a query (i.e. a whole table) how would I know how many arguments to put into $stmt->bind_result()?

Also, is the way I handled errordetection and -notification optimal from a security and user-friendliness standpoint?

So after reading through your question, I noticed that you seem very concerned about the "security" of your web application. I'll do my best to share what knowledge I can muster up!

However, there are a couple key things I think need to be cleared up before we touch on the safety of your data.

  I haven't really used MySQL (especially OOP)

Cool! Good to hear that you're expanding your horizons :)

But... Don't be mistaken and call your code object oriented. There's a lot more to the pattern than simple calling an object's methods.

Don't think that we can write up an entire website procedural style, and then make one call to $object->method() and have it all of a sudden be object oriented! Object orientation means a separation of concerns in different class/interfaces.

It's too hard to give you one or two links that will magically "show you the way". I'm afraid you'll just have to read and practice until you can compare your code to other OO code, and say, "Wow, my code really looks object oriented!"

  I don't trust my knowledge of SQL

That's good! Don't ever publish something without having a second pair of eyes check your work.

When was the last time you wrote an essay without spell check turned on?

Okay, so, how secure is your code?

Well, from the comments, I'm sure you already realize there's something wrong with giving the user $stmt->error.

But, why is this bad?

Well, there are two main issues with it:

It's not user friendly. Kind of cheesy, but the guys on UX.StackExchange wouldn't be disagreeing with me. When you visit any major website, have you ever seen an error complaining the database connection failed on host 8080 on line 482? Of course not! The user doesn't need to know that information.

All the user needs to know is: how can I fix the problem. Most of the time this will just be "Try again later", sometimes it can be your browser telling you that you don't have an internet connection! Does the user need to know that the application couldn't bind the parameters to the query? What the hell does that even mean to the average user!

So now that we know all this, what should you do? Throw out all those errors that say you can bind parameters or prepare the query. All you need to tell the user is something such as: "Sorry, we couldn't execute your command" or whatever. The exact message will depend on the users, and you may need to do some A/B testing.
It in fact does assist any attack. Oh, so when I inject this SQL into the POST, it breaks on that step, that must mean the code is vulnerable there!

Here's a good read on StackExchange's information security site. There are tons of questions relating to your issue already. I'm not joking, there's a lot of relevant information for you! Did you ask for another sweet Q&A to read, because this one might help.

A Google can tell you a lot more than I can summarize here. A synopsis though: how much error message you show does depend on your site, but in general, it's best not to show the attacker a better way to attack!

Congratulations on discovering the security / user experience trade off!

OK, is there anything else that's insecure about this code? Well, unfortunately, nothing else pops out at me. Don't think that that means your code is safe though!

Any other comments from me? Yep!

Avoid die(). It's really not user friendly to kill the page when things go wrong.
Use brackets {, }! The language has them for a reason, and it was ridiculous to implement the shorthand.
It's always weird to read lot's of logic inside a switch's case. I'd see about refactoring that so you're not doing such large operations inside the statement.
When you secure passwords, which you will... I recommend using PHP's password_hash() utilities. It's probably the safest option for password storage at this point in time.
Over all, I'd look at trying to implement a database access layer into your application. I'd say the most well respected is Doctrine, but of course, do what the project calls for.

Hopefully that helps :)


Class for catching error and logging I often write something like this in my code:

try {
    obj.doSomething();
} catch (Throwable exception) {
    // there is no need to interrupt application
    String exceptionMessage = String.valueOf(exception.getMessage());
    Log.e("Name of my app", exceptionMessage, exception);
    // and may be something else
}

So I wrote this simple class:

public class TryHelper {

    public static final TryHelper LOGGER = new TryHelper(new Handler<Throwable>() {
        @Override
        public void handle(Throwable exception) {
            LogUtils.exception(exception);
        }
    });

    private final Handler<Throwable> exceptionHandler;

    public TryHelper(Handler<Throwable> exceptionHandler) {
        this.exceptionHandler = exceptionHandler;
    }

    public void tryDoIt(Runnable runnable) {
        try {
            runnable.run();
        } catch (Throwable exception) {
            exceptionHandler.handle(exception);
        }
    }

    public void tryDoIt(RunnableAbleToThrowCheckedException runnable) {
        try {
            runnable.run();
        } catch (Throwable exception) {
            exceptionHandler.handle(exception);
        }
    }

}

And interfaces from my own util package:

public interface RunnableAbleToThrowCheckedException {
    void run() throws Exception;
}

public interface Handler<T> {
    void handle(T obj);
}

Using:

TryHelper.LOGGER.tryDoIt(new Runnable() {
    @Override
    public void run() {
        obj.doSomething();
    }
});

But I'm pretty bad at English. So I need your help in choosing proper names (instead of TryHelper, RunnableAbleToThrowCheckedException, tryDoIt(), etc.).

I'm a fan of Uncle Bob and his book "Clean Code":

  We want the code to read like a top-down narrative.

And what do you think about the need for this class? Maybe it was a bad idea?

You could use Callable instead of RunnableAbleToThrowCheckedException. Its call method could throw Exeptions and has a return value too. You can use  Void as a type parameter and return null if you don't need these features:

public class MyCallable implements Callable<Void> {

    @Override
    public Void call() throws Exception {
        ...
        return null;
    }
}

TryHelper seems like an Executor to me. I'd name it ErrorHandlerExecutor and rename its tryDoIt methods to submit (similar to ExecutorService). I guess most developers would find it familiar.
errorLoggerExecutor seems a fair name for an instance which logs the errors of the submitted tasks.
I would also rename Handler to ErrorHandler to be more descriptive.


Find sum of all the subarrays of an array I have an array. Now I want to find the total of, sum of the subarray multiplied by its last element, for all the possible subarrays. This is what I have right now:

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
total = 0
for i in range(1, n+1):
    for j in range(n+1-i):
        temp = a[j:j+i]
        total += sum(temp)*temp[-1]
print(total)

Example Input:

3
1
2
3

Output:

53

Explanation:

1*1 + 2*2 + 3*3 + (1+2)*2 + (2+3)*3 + (1+2+3)*3 = 53

My code works fine, but is quite slow. How can I optimise it?

First I would suggest to separate I/O from the computation,
and define a function to compute the subarray sum. That increases
the clarity of the program and allows to add test cases more easily:

def subarray_sum(a):
    """Compute sum of all subarrays of a, multiplied by its last element"""
    n = len(a)
    total = 0
    for i in range(1, n + 1):
        for j in range(n + 1 - i):
            temp = a[j:j + i]
            total += sum(temp) * temp[-1]
    return total

Using sum() with generator expressions this can be shortened to

def subarray_sum(a):
    n = len(a)
    total = sum(sum(sum(a[i:j + 1]) * a[j] for j in range(i, n))
                for i in range(n))
    return total

But the time complexity is still \$ O(n^3) \$ because of the three nested
loops.

In order to find a more efficient method, let's compute the sum for a 3-element
array \$ [a, b, c] \$ explicitly:

$$
 a \cdot a + b \cdot b + c \cdot c \\
 + (a+b)\cdot b + (b+c) \cdot c \\
 + (a+b+c) \cdot c
$$
Rearranging terms, this becomes
$$
 a \cdot a + (a + 2b) \cdot b + (a + 2b + 3c) \cdot c
$$
Can you spot the pattern? This can be computed with a single
traversal of the array, i.e.  in \$ O(n) \$ time.


Creating new string with only distinct letters Aim: To have only one of each character on the Return string:

Public Shared Function CheckForDuplicates(ByVal vCharCheck As String) As String

    Dim vDeDuplicated As String = ""
    Dim i As Integer

    For i = 1 To vCharCheck.Length ' Count length of string

        'vDeDuplicate is blank to start so will always capture first character
        'vDeDuplicate is then checked against each character in the incoming string to see if it contains this character already
        'thus deduplicting the string

        If vDeDuplicated.Contains(Mid(vCharCheck, i, 1)) Then
            'Check the new string to see if it exists, if it does it is not allowed
        Else
            'The character is not found so we add it
            vDeDuplicated += Mid(vCharCheck, i, 1)
        End If

    Next

    Return vDeDuplicated
End Function

Of course you can eliminate the loop by using the Distinct method of the string, which won't care if the string is empty or not.  Assuming vCharCheck is the input string, it would look something like this:

Return New String(vCharCheck.Distinct.ToArray)


Find all collection properties of an object and get their values I have a chunk of code that get's all of the ICollection properties of the passed in object and then takes all of their values and adds them to another ICollection.

  End goal is to see which properties have child objects in them and
  thus finding out how many dependents the object has.

The object is an EntityFramework entity so the children would be other entities. I'm not entirely convinced that I'm actually grabbing the correct properties (although in my tests so far it works) and I'm not convinced I'm parsing them efficiently either. Here's the code, and I welcome any recommendations:

public class DependencyValidator<TEntity> :
    IDependencyValidator<TEntity>
    where TEntity : class {
    private readonly Type IEnumerableType = typeof(IEnumerable);
    private readonly Type StringType = typeof(String);

    public IEnumerable<KeyValuePair<string, IEnumerable<string>>> Dependencies(
        TEntity entity) {
        if (entity == null) {
            return Enumerable.Empty<KeyValuePair<string, IEnumerable<string>>>();
        }

        ICollection<KeyValuePair<string, IEnumerable<string>>> dependents = new List<KeyValuePair<string, IEnumerable<string>>>();

        entity.GetType().GetProperties().Where(
            p =>
                this.IEnumerableType.IsAssignableFrom(p.PropertyType)
                && !this.StringType.IsAssignableFrom(p.PropertyType)).ForEach(
            p => {
                IEnumerable values = (p.GetValue(entity) as IEnumerable);
                ICollection<string> children = new List<string>();

                foreach (var value in values) {
                    children.Add(value.ToString());
                }

                dependents.Add(new KeyValuePair<string, IEnumerable<string>>(p.Name, children));
            });

        return dependents;
    }
}

First up, let's clean up the formatting a bit.

public class DependencyValidator<TEntity> :
    IDependencyValidator<TEntity>
    where TEntity : class
{
    private readonly Type IEnumerableType = typeof(IEnumerable);
    private readonly Type StringType = typeof(String);

    public IEnumerable<KeyValuePair<string, IEnumerable<string>>> Dependencies(TEntity entity)
    {
        if (entity == null)
        {
            return Enumerable.Empty<KeyValuePair<string, IEnumerable<string>>>();
        }

        ICollection<KeyValuePair<string, IEnumerable<string>>> dependents = new List<KeyValuePair<string, IEnumerable<string>>>();

        entity.GetType().GetProperties().Where(
            p =>
                this.IEnumerableType.IsAssignableFrom(p.PropertyType)
                && !this.StringType.IsAssignableFrom(p.PropertyType)).ForEach(
            p =>
            {
                IEnumerable values = (p.GetValue(entity) as IEnumerable);
                ICollection<string> children = new List<string>();

                foreach (var value in values)
                {
                    children.Add(value.ToString());
                }

                dependents.Add(new KeyValuePair<string, IEnumerable<string>>(p.Name, children));
            });

        return dependents;
    }
}

Now let's use the var keyword to make it less verbose.

public class DependencyValidator<TEntity> :
    IDependencyValidator<TEntity>
    where TEntity : class
{
    private readonly Type IEnumerableType = typeof(IEnumerable);
    private readonly Type StringType = typeof(String);

    public IEnumerable<KeyValuePair<string, IEnumerable<string>>> Dependencies(TEntity entity)
    {
        if (entity == null)
        {
            return Enumerable.Empty<KeyValuePair<string, IEnumerable<string>>>();
        }

        var dependents = new List<KeyValuePair<string, IEnumerable<string>>>();

        entity.GetType().GetProperties().Where(
            p =>
                this.IEnumerableType.IsAssignableFrom(p.PropertyType)
                && !this.StringType.IsAssignableFrom(p.PropertyType)).ForEach(
            p =>
            {
                var values = (p.GetValue(entity) as IEnumerable);
                var children = new List<string>();

                foreach (var value in values)
                {
                    children.Add(value.ToString());
                }

                dependents.Add(new KeyValuePair<string, IEnumerable<string>>(p.Name, children));
            });

        return dependents;
    }
}

Your ForEach method seems to be non-standard, so I'd like to get rid of that.

public class DependencyValidator<TEntity> :
    IDependencyValidator<TEntity>
    where TEntity : class
{
    private readonly Type IEnumerableType = typeof(IEnumerable);
    private readonly Type StringType = typeof(String);

    public IEnumerable<KeyValuePair<string, IEnumerable<string>>> Dependencies(TEntity entity)
    {
        if (entity == null)
        {
            return Enumerable.Empty<KeyValuePair<string, IEnumerable<string>>>();
        }

        var dependents = new List<KeyValuePair<string, IEnumerable<string>>>();

        var properties = entity.GetType()
            .GetProperties()
            .Where(p => this.IEnumerableType.IsAssignableFrom(p.PropertyType) && !this.StringType.IsAssignableFrom(p.PropertyType));

        foreach (var property in properties)
        {
            var values = property.GetValue(entity) as IEnumerable;
            var children = new List<string>();

            foreach (var value in values)
            {
                children.Add(value.ToString());
            }

            dependents.Add(new KeyValuePair<string, IEnumerable<string>>(property.Name, children));
        }

        return dependents;
    }
}

ReSharper suggests replacing the inner loop with a LINQ expression, which I think looks alright.

public class DependencyValidator<TEntity> :
    IDependencyValidator<TEntity>
    where TEntity : class
{
    private readonly Type IEnumerableType = typeof(IEnumerable);
    private readonly Type StringType = typeof(String);

    public IEnumerable<KeyValuePair<string, IEnumerable<string>>> Dependencies(TEntity entity)
    {
        if (entity == null)
        {
            return Enumerable.Empty<KeyValuePair<string, IEnumerable<string>>>();
        }

        var dependents = new List<KeyValuePair<string, IEnumerable<string>>>();

        var properties = entity.GetType()
            .GetProperties()
            .Where(p => this.IEnumerableType.IsAssignableFrom(p.PropertyType) && !this.StringType.IsAssignableFrom(p.PropertyType));

        foreach (var property in properties)
        {
            var values = property.GetValue(entity) as IEnumerable;
            var children = (from object value in values select value.ToString()).ToList();

            dependents.Add(new KeyValuePair<string, IEnumerable<string>>(property.Name, children));
        }

        return dependents;
    }
}

Finally, we can make the fields static. ReSharper warns about this, but I think it's fine in this case.

 public class DependencyValidator<TEntity> :
    IDependencyValidator<TEntity>
    where TEntity : class
{
    private static readonly Type IEnumerableType = typeof(IEnumerable);
    private static readonly Type StringType = typeof(string);

    public IEnumerable<KeyValuePair<string, IEnumerable<string>>> Dependencies(TEntity entity)
    {
        if (entity == null)
        {
            return Enumerable.Empty<KeyValuePair<string, IEnumerable<string>>>();
        }

        var dependents = new List<KeyValuePair<string, IEnumerable<string>>>();

        var properties = entity.GetType()
            .GetProperties()
            .Where(p => IEnumerableType.IsAssignableFrom(p.PropertyType) && !StringType.IsAssignableFrom(p.PropertyType));

        foreach (var property in properties)
        {
            var values = property.GetValue(entity) as IEnumerable;
            var children = (from object value in values select value.ToString()).ToList();

            dependents.Add(new KeyValuePair<string, IEnumerable<string>>(property.Name, children));
        }

        return dependents;
    }
}