Simplifying conditional statements for transaction code I have below code in one function:

public void func()
{
    if (!string.IsNullOrEmpty(customerpay) && !string.IsNullOrEmpty(warrantypay) && !string.IsNullOrEmpty(maintanceplan))
    {
        if (customerpay == "Include" && warrantypay == "Include" && maintanceplan == "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[C^W^I]";
        }
        else if (customerpay == "Include" && warrantypay == "Include" && maintanceplan != "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[C^W]";
        }
        else if (customerpay == "Include" && warrantypay != "Include" && maintanceplan != "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[C]";
        }
        else if (customerpay != "Include" && warrantypay == "Include" && maintanceplan == "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[W^I]";
        }
        else if (customerpay != "Include" && warrantypay != "Include" && maintanceplan == "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[I]";
        }
        else if (customerpay != "Include" && warrantypay == "Include" && maintanceplan != "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[W]";
        }
        else if (customerpay == "Include" && warrantypay != "Include" && maintanceplan == "Include")
        {
            transactiontype = "," + "[Population].[Transaction Type Code].&[C^I]";
        }
    }
}

I need to simplify the above if-else C# code. Is there a way to do this?

You could do it like this:

public void func()
{
    if (string.IsNullOrEmpty(customerpay) || string.IsNullOrEmpty(warrantypay) || string.IsNullOrEmpty(maintanceplan))
        return;

    if (customerpay != "Include" && warrantypay != "Include" && maintanceplan != "Include")
        return;

    List<char> parts = new List<char>();
    if (customerpay == "Include")
        parts.Add("C");
    if (warrantypay == "Include")
        parts.Add("W");
    if (maintanceplan == "Include")
        parts.Add("I");

    transactiontype = ",[Population].[Transaction Type Code].&[" + string.Join("^", parts) + "]";
}

First, we simply return if any of the strings is empty; by inverting the logic, we can reduce one indentation level that makes the code unecessarily complicated. We also return for the single case that isn’t handled in your original code: If all three strings are not "Include".

After that, it’s easy once you find out the pattern of your string. The only changing part of your result string is in the brackets at the end. There are three possible characters: C, W, and I. They appear if the corresponding string equals to "Include". The characters are separated by a ^. So we just check each condition alone, and collect the characters in a list. Then we join with the separation character and build the final result string.


Negation detection in sentiment analysis This basic function to detect negation while performing sentiment analysis. So that not good kind of words can be considered a negative.

This code is working fine. Can someone help to improve it or find if any bug present?

def negate_sequence(self,text):
    """
    Detects negations and transforms negated words into "not_" form.
    """
    negation = False
    delims = "?.,!:;"
    result = []
#Here rather then applying split, we can directly feed our extracted symptoms list
    words = text.split()
    prev = None
    pprev = None
    for word in words:
        # stripped = word.strip(delchars)
        stripped = word.strip(delims).lower()
        negated = "not_" + stripped if negation else stripped
        result.append(negated)
        if prev:
            bigram = prev + " " + negated
            result.append(bigram)
            if pprev:
                trigram = pprev + " " + bigram
                result.append(trigram)
            pprev = prev
        prev = negated

        if any(neg in word for neg in ["not", "n't", "no"]):
            negation = not negation

        if any(c in word for c in delims):
            negation = False

    return result

Here are a few suggestions on how to improve the code:
State the intent
What is the purpose of the function? What is the input, what is the output? In human words, what does the algorithm do? A docstring answering those basic questions would be helpful. A series of concise unit tests would be great.
I ran the function to have a look at the output:
>>> text = "The weather is not good."
>>> result = negate_sequence(self=None, text=text)
>>> print(result)

['the', 'weather', 'the weather', 'is', 'weather is', 'the weather is', 'not', 'is not',
'weather is not', 'not_good', 'not not_good', 'is not not_good']

This doesn't ring a bell with me, so I stopped trying to understand the purpose.
Avoid stateful loops
Iteration i is coupled to iteration i-1 by the negation variable, this makes the logic hard to understand and error prone. If you work on bigrams/trigrams, I'd create a list of bigrams/trigrams and iterate over the tuples. This decouples the iterations.
Breakup long functions
This has almost endless benefits, as a starting point see this article. Some possibilities:

Have the text broken up into all lowercase and without punctuation by extract_words(text)
Have the list of trigrams created by make_trigrams(words)
Inspect the trigrams by process(trigrams)
If needed, have some kind of aggregate(results)

Once this is done, I guess we are much better to prepared to identify bugs and to further improve functionality.


Enable and disabled multiple inputs I have to enable/disable multiple inputs when a select change. It works but I want to do it better. How can I improve my code?

$("#street_type").on("change", function(event){
    if( $(this).val() == 1){
        $("#clase_via").prop('disabled', true);
        $("#nombre_via").prop('disabled', true);
        $("#numero_via").prop('disabled', true);
        ...
        $("#indicaciones").prop('disabled', true);
    }
    if( $(this).val() == 2){
        $("#clase_via").prop('disabled', false);
        $("#nombre_via").prop('disabled', false);
        $("#numero_via").prop('disabled', false);
        ...
        $("#indicaciones").prop('disabled', false);
    }
});

Create array with id's of needled input's:

var inputs = ["clase_via", ...], i, count;
for (i = 0, count = inputs.length; i < count; i += 1){
    $(inputs[i]).prop("disabled", true);
}

Add "data" attribute for needled input's:

<input type='text' data-lockable="true"/>
$("input [data-lockable='true']).prop("disabled", true);

Place all input's into one block and call jQuery as:

$("#maindiv > input").prop("disabled", true);


Retrieving a substring from an exponentially growing string For integer A, the base level of 1 is "XYZ"
For subsequent levels, the levels become "X" + Level (A - 1) + "Y" + Level (A - 1) + "Z".
So for level 2, the string would be "XXYZYXYZZ"
The objective is to return the substring from the Level string using the Start and End Index.
Example: If entering 2 3 7, it would Level 2, 3rd character to the 7th character and the result would be "YZYXY" from "XXYZYXYZZ"
The following constraints are given:

1 ≦ Level K ≦ 50,
1 ≦ start ≦ end ≦ length of Level K String,
1 ≦ end - start + 1 ≦ 100.

I have written a brute force approach for this problem in Python as follows
def my_substring():
    level = int(input())
    start_index = int(input()) - 1
    end_index = int(input())
    strings_list = [None] * level
    strings_list[0] = "XYZ"

    for i in range(1, level):
        strings_list[i] = "X" + strings_list[i - 1] + "Y" + strings_list[i - 1] + "Z"

    return "".join(strings_list[-1])[start_index:end_index]

if __name__ == '__main__':
    print(my_substring())

As shown, the length of the string will increase by (base string * 2) + 3 for each iteration.  Past the 20th iteration, my program starts running into issues from having to deal with the enormous final string.  I would like to learn how I can reduce my complexity from what I think is O(N^2).
What alternative approaches are there for me to handle/concatenate very long strings in Python?  Is there a way for me to reduce the loading time/resources for doubling my strings?
Or is my current approach flawed and should I be approaching this issue from a different angle (one that I am so far unable to come up with an alternative for).
Edit: I have been told that this problem can be solved in O(1) - O(logn) time.

The length of the string at level \$ K \$ is \$ 3 (2^K -1) \$, which means that for \$ K = 50 \$ a string with \$ 3377699720527869 \$ characters is (recursively) built. That is about 3 petabyte (if you count one byte per character) and won't fit into the memory of your computer.
On the other hand, only a small portion of that complete string is actually needed, because of the constraint \$ 1 \le end - start + 1 \le 100 \$. And in many cases, that substring is already contained in the string given by a previous, smaller level.
Therefore I would prefer a recursive algorithm: Check the given start and end indices for the positions of "X", "Y" and "Z" from the current level, and recurse to the preceding level for the portions between those positions.
Here is a possible implementation:
def substring(level, start_index, end_index):
    # Indices of "X", "Z", "Y" at the current level:
    low = 1
    high = 3 * (2 ** level - 1)
    mid = (low + high) // 2

    result = ""
    while start_index <= end_index:
        if start_index == low:
            result += "X"
            start_index += 1
        elif start_index < mid:
            e = min(end_index, mid - 1)
            result += substring(level - 1, start_index - low, e - low)
            start_index += e - start_index + 1
        elif start_index == mid:
            result += "Y"
            start_index += 1
        elif start_index < high:
            e = min(end_index, high - 1)
            result += substring(level - 1, start_index - mid, e - mid)
            start_index += e - start_index + 1
        else:
            result += "Z"
            start_index += 1

    return result

It computes
substring(50, 3377699720527869-200, 3377699720527869-100)

within fractions of a second.
Further improvements are possible, e.g. by noting that the string on level K starts with K "X" characters and ends with K "Z" characters, or by handling the first level separately.


Get individual item count get_item_count calls to an API and gets a count.  There are several pages to get this count from until there are no more results.

How do I improve this code to remove all of the extra variables and make it easier to read?

final_count = 0
page = 1
final_count = individual_count = get_item_count(config, page)
while individual_count > 20
  page = page + 1
  individual_count = get_item_count(config,page)
  final_count = individual_count + final_count
end

Use a do-while loop, so the loop body gets always executed at least once:

final_count = 0
page = 1
begin
  individual_count = get_item_count(config, page)
  final_count += individual_count
  page += 1
end while individual_count > 20


Find the third largest element in the array in linear time Find Third largest element in an array

  Input  : arr[] = {1, 14, 2, 16, 10, 20}

  Output : 14

Its a simple program, but would be great to know how it can be improved for better readability or any feedback regarding styling, etc.

public static int findThirdLargest(int[] numbers) {
    if (numbers.length < 3) {
        throw new IllegalArgumentException("there should be at least three numbers");
    }

    int largest, secondLargest, thirdLargest;
    largest = secondLargest = thirdLargest = Integer.MIN_VALUE;

    for (int number : numbers) {

        if (number > largest) {
            thirdLargest = secondLargest;
            secondLargest = largest;
            largest = number;
        } else if (number > secondLargest) {
            thirdLargest = secondLargest;
            secondLargest = number;
        } else if (number > thirdLargest) {
            thirdLargest = number;
        }
    }

    return thirdLargest;
}

@Test
public void findThirdLargest() throws Exception {

    // with positive numbers
    Assert.assertEquals(1, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, 3}));
    Assert.assertEquals(2, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, 3, 4}));
    Assert.assertEquals(2, ThirdLargestNumber.findThirdLargest(new int[]{1, 4, 3, 2}));
    Assert.assertEquals(14, ThirdLargestNumber.findThirdLargest(new int[]{1, 14, 2, 16, 10, 20}));
    Assert.assertEquals(16, ThirdLargestNumber.findThirdLargest(new int[]{19, -10, 20, 14, 2, 16, 10}));

    // with negative numbers
    Assert.assertEquals(-100, ThirdLargestNumber.findThirdLargest(new int[]{-100, -2, -3}));
    Assert.assertEquals(-3, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, -3, -1000}));
    Assert.assertEquals(-3000, ThirdLargestNumber.findThirdLargest(new int[]{-1000, -2000, -3000, -4000, -5000}));

    // what happens when all the numbers are same
    Assert.assertEquals(1, ThirdLargestNumber.findThirdLargest(new int[]{1, 1, 1, 1}));
}

Code: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/ThirdLargestNumber.java#5

I think overall it is well done, it is clear and readable. Some general tips:

You can make the parameter a varargs, which makes it easier to call:

public static int findThirdLargest(int... numbers)
...
int thirdLargest = findThirdLargest(1, 2, 3);

Since you check for the size of the array, you could perhaps also check if it is not null.
This is somewhat personal, but I would always declare and initialise each variable on a separate line, e.g.:

int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
int thirdLargest= Integer.MIN_VALUE;

To me it helps readability and potentially refactoring later on.

I'd remove the newline after the for loop opener. It decreases readability for me.

Nice that you added tests! You covered some good cases. You could take a look at Hamcrest matchers, you can create some nice declarative tests with it. They can also show quite decent messages in case a test fails.

Some extra tips about the current tests:

I'd split up the tests in a couple of different methods
Personally, I like to use static imports, so you can write:

assertEquals(1, findThirdLargest(1, 2, 3))

Also do not forget to test for failing cases. Test that when you pass less than 3 numbers, you expect an exception.

And what should the output of findThirdLargest(1, 1, 2, 2, 3, 3) be?

Lastly, a follow up exercise: how would you implement it if the user wants to find the k-th largest element?


Is there a simple way to use Underscorejs to achieve this? I have an object, having key and values.  I'd like to pick the object and call the appropriate function from the key:

var requireViews = {
            "breadCrumbView": true,
            "headerView": false,
            "footerView": false
        };

var that = this;

    _.each(requireViews, function(value, key){
                    if(value){ //if true?
                        if(_.functions(that, key)) that[key](); //checking is that function, and calling the function
                    }
                })

Is it ok or can we minimize it further?

To be honest, I'd skip underscore for this, and just do

for(var func in requireViews) {
  if(requireViews[func] && typeof this[func] === 'function') {
    this[func]();
  }
}

Otherwise, there are many different ways to go about it.

Here's a needlessly complex one, for instance:

var target = this;
_.chain(requireViews)
  .keys()
  .filter(function (func) { return requireViews[func] })
  .intersection(_.functions(this))
  .each(function (func) { target[func]() });


Displaying nested arithmetic expressions as a string using Scala pattern matching I am learning the concepts of pattern matching in Scala. Following is an exercise for the same. The task is to define a show function that outputs an expression as a String. Following are the definitions involved:

object Test {
  trait Expr
  case class Number(n: Int) extends Expr
  case class Sum(e1: Expr, e2: Expr) extends Expr
  case class Prod(e1: Expr, e2: Expr) extends Expr
  case class Var(name: String) extends Expr

  def nestOperations(e1: Expr, e2: Expr): String = {
    val l = e1 match {
      case Number(n) => n.toString
      case Prod(x, y) => nestOperations(x, y)
      case Var(s) => s
      case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
    }
    val r = e2 match {
      case Number(n) => n.toString
      case Prod(x, y) => nestOperations(x, y)
      case Var(s) => s
      case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
    }
    l + " * " + r
  }

  def show(e: Expr): String = e match {
    case Number(n) => n.toString
    case Sum(e1, e2) => show(e1) + " + " + show(e2)`
    case Prod(e1, e2) => nestOperations(e1, e2)
    case Var(s) => s
  }
  show(Sum(Number(1), Number(2)))
  show(Sum(Prod(Number(2), Var("x")), Var("y")))
  show(Prod(Sum(Number(2), Var("x")), Var("y")))
}

The expectation is that:
show(Sum(Number(1), Number(2))) outputs 1 + 2
show(Sum(Prod(Number(2), Var("x")), Var("y"))) outputs 2 * x + y
show(Prod(Sum(Number(2), Var("x")), Var("y"))) outputs (2 + x) * y

The program achieves all of the above. I want to know if the nestOperations method can be simplified? Looks like a lot of repetitive code in there.

You're right.  That repeated code in nestOperations() can be eliminated.

def nestOperations(es: Expr*): String =
  es.map {
    case Number(n) => n.toString
    case Prod(x, y) => nestOperations(x, y)
    case Var(s) => s
    case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
  }.mkString(" * ")

But why stop there?  You can pull much the same stunt with show() and eliminate nestOperations() altogether.

def show(es: Expr*): String = es.map{
  case Number(n) => n.toString
  case Sum(e1, e2) => if (es.length > 1) "(" + show(e1) + " + " + show(e2) + ")"
                      else show(e1) + " + " + show(e2)
  case Prod(e1, e2) => show(e1, e2)
  case Var(s) => s
}.mkString(" * ")


Subarray Sum Equals K I've written a solution to the following leetcode problem:

  Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

  Example 1:
  Input: nums = [1,1,1], k = 2
  Output: 2

  Note:
  The length of the array is in range [1, 20,000].
  The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution:

class Solution:
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        T = ['inf' for _ in range(len(nums))]
        count = 0
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                if j == i:
                    T[i] = nums[i]
                    if T[i] == k:
                        count +=1
                else:
                    currSum = T[j-1] + nums[j]
                    T[j] = currSum
                    if currSum == k:
                        count +=1
        return count

The solution passes 58/80 test cases, but for some reason, the solution is returning a Time Limit Exceeded exception on an input array with hundreds of elements. I implemented a dynamic programming solution using a 1d array to memoize previous sums so the algorithm should be efficient. Is there any way to optimize this?

These nested loops

    for i in range(len(nums)):
        for j in range(i,len(nums)):

undoubtedly make the time complexity quadratic. This is the reason for TLE. There is no point to optimize this code; you need to rethink the approach. I don't want to spell out the linear algorithm, and deprive you the fun of finding it. Hint: think of the sliding window.

A condition j == i inside the inner loop happens exactly once, and we perfectly know when. Lift it out:

    for i in range(len(nums)):
        T[i] = nums[i]
        if T[i] == k:
            count +=1
        for j in range(i + 1, len(nums)):
            currSum = T[j-1] + nums[j]
            T[j] = currSum
            if currSum == k:
                count +=1


Finding a word that represents an image This is an app wherein you have to find the word that represents the image. It's the same concept as the course app but I did this one myself.

How can I improve this code (put more commentary, put more space, you can add that, etc.)? I finished the second part of app development with Swift. Please explain why I should do the modification. Commentary are in French but I can translate them.

Game Struct

import Foundation
import UIKit
struct Game
{
    var correctWord: String
    var image: UIImage
    var guessedLetter: [Character]
    // création du bon mot par le joueur
    var formatedWord: String
    {
        var formateWord = ""
        let word = correctWord.lowercased()

        for letter in word
        {
            if guessedLetter.contains(letter)
            {
                formateWord += "\(letter)"
            }
            else
            {
                formateWord += "_"
            }
        }

        return formateWord
    }
    // Quand le joueur
    mutating func playerGuessed(_ letter: Character)
    {
        guessedLetter.append(letter)
    }
}

View Controller

import UIKit
//liste de mot et image
var imageAndWord = ["Maison": #imageLiteral(resourceName: "image 1"),"Bateau": #imageLiteral(resourceName: "image2") ,"Train": #imageLiteral(resourceName: "image 3"),"Vase": #imageLiteral(resourceName: "image 4")]
//récupération des clées
var theKey = Array(imageAndWord.keys)
// Nombre de clé
let totalKey = theKey.count + 1
//récupération des valeurs
var theValue = Array(imageAndWord.values)
// comptage d'image trouvé
var imageFindNumber = 0
class ViewController: UIViewController {
    // initialisation des vues
    @IBOutlet var lettersButtons: [UIButton]!
    @IBOutlet weak var imageView: UIImageView!
    @IBOutlet weak var wordLabel: UILabel!
    @IBOutlet weak var scoreLabel: UILabel!
    //Quand une lettre est pressée
    @IBAction func lettersButtonsPressed(_ sender: UIButton)
    {
        sender.isEnabled = false
        let letter = sender.title(for: .normal)!
        let lowCasedLetter = Character(letter.lowercased())
        currentGame.playerGuessed(lowCasedLetter)
        if currentGame.correctWord == currentGame.formatedWord
        {
            newRound()

        }
        updateUI()
    }
    // Actualisation de l'interface
    func updateUI()
    {
        let word = currentGame.formatedWord.map{String($0)}
        let spacingWord = word.joined(separator: " ")
        wordLabel.text = spacingWord
        imageView.image = currentGame.image
        scoreLabel.text = "Image: \(imageFindNumber)/\(totalKey)"

    }
    var currentGame: Game!
    // Initialisation de l'image et du mot
    func newRound()
    {
        if !theKey.isEmpty && !theValue.isEmpty
        {
        enableOrNotButton(true)
        let word = theKey.removeFirst().lowercased()
        let value = theValue.removeFirst()
        currentGame = Game(correctWord:word, image:value, guessedLetter: [])
        imageFindNumber += 1
        updateUI()
        }
        else
        {
            enableOrNotButton(false)
        }
    }
    //Activation ou désactivation de tout les bouttons
    func enableOrNotButton(_ enable: Bool)
    {
            for button in lettersButtons
            {
                button.isEnabled = enable
            }
    }
    override func viewDidLoad() {
        super.viewDidLoad()
        newRound()
        print(currentGame.correctWord)
        // Do any additional setup after loading the view, typically from a nib.
    }

    override func didReceiveMemoryWarning() {
        super.didReceiveMemoryWarning()
        // Dispose of any resources that can be recreated.
    }

}

I would begin with the imports.  When importing UIKit you will not need to import Foundation because the contents of UIKit will also include Foundation.

Now to recommend a few things with regards to the Game struct. Now the way the struct is instantiated means that one image is equivalent to a "Game," so you would be able to set the correctWord, and image to constants with let.

Secondly, we can also provide a more descriptive names for the variables to eliminate any confusion later on down the line, like using guessedLetters instead of guessedLetter (plural indicates that this is likely an array), correctAnswer instead of correctWord, and guessedWord instead of formatedWord as these are more clear and descriptive of their purposes.

import UIKit

struct Game
{
    let correctAnswer: String
    let image: UIImage
    var guessedLetters: [Character]
    // création du bon mot par le joueur
    var guessedAnswer: String
    {
        var guessedAnswer = ""
        let answer = correctAnswer.lowercased()

        for letter in answer
        {
            if guessedLetters.contains(letter)
            {
                guessedAnswer += "\(letter)"
            }
            else
            {
                guessedAnswer += "_"
            }
        }

        return guessedAnswer
    }
    // Quand le joueur
    mutating func playerGuessed(_ letter: Character)
    {
        guessedLetters.append(letter)
    }
}

Now with regards to the View Controller. I would begin by dealing with the variables at the top of the controller.  These should either be included in the controller or refactored into their own file. For simplicity sake, I'll just move these to be part of the ViewController.

Next we would want to rename some of the variables to make their purposes more clear.  This will help with understanding of what everything does in a way that is more identifiable than comments. I've opted to use names like imageDictionary and currentGameIndex over imageAndWord and imageFindNumber, for example.

Next, there are a couple values that are unnecessary.  Particularly theKey, theValue, and totalKey. These are not needed because we already have a mutable dictionary that we can perform actions against, so we do not need to create extra versions of these values.  When we are setting the new game parameters, I've updated those references to use the following logic, which will do the same thing without needing additional arrays.

imageDictionary.removeValue(forKey: currentGame.correctAnswer)
let word = imageDictionary.first?.key.lowercased()
let value = imageDictionary.first?.value

I've introduced a guard statement in the newRound method. This statement is useful for when you have a dependency that you need to continue executing.  In this case, you need to have an image available in order to proceed, so the guard case will verify if there is one, and then continue through or terminate early.  This is not necessary, but in cases where there are dependencies that are required, it can be useful and easier to read than nested if statements.

Another change I would recommend is renaming the enableOrNotButton: method. In my example, I've updated it to setButtonStatus enabled: as it helps you understand at a glance what the intent is.  setButtonStatus(enabled:true) shows you that you are intending that the button will be updated to enable = true.

Finally I've removed the redundant comments, as those don't really help much of anything. If the method is named appropriately, as is the case for updateUI(), then you don't really need a comment that says "updateUI() will update the UI".  Comments are more helpful when they explain something that isn't understood.  A good comment should be able to answer a question or provide information that isn't immediately obvious.

import UIKit

class ViewController: UIViewController {

    var imageDictionary = ["Maison": #imageLiteral(resourceName: "image 1"),"Bateau": #imageLiteral(resourceName: "image2") ,"Train": #imageLiteral(resourceName: "image 3"),"Vase": #imageLiteral(resourceName: "image 4")]
    var currentGameIndex = 0
    var currentGame: Game!

    @IBOutlet var letterButtons: [UIButton]!
    @IBOutlet weak var imageView: UIImageView!
    @IBOutlet weak var wordLabel: UILabel!
    @IBOutlet weak var scoreLabel: UILabel!

    @IBAction func letterButtonsPressed(_ sender: UIButton)
    {
        // Disable the button so the user cannot select the letter again.
        sender.isEnabled = false
        let guessedLetter = sender.title(for: .normal)!
        let lowercasedLetter = Character(guessedLetter.lowercased())
        currentGame.playerGuessed(lowercasedLetter)

        if currentGame.correctAnswer == currentGame.guessedAnswer
        {
            beginNewRound()
        }

        updateUI()
    }

    func updateUI()
    {
        let word = currentGame.guessedAnswer.map{String($0)}
        let spacingWord = word.joined(separator: " ")
        wordLabel.text = spacingWord
        imageView.image = currentGame.image
        scoreLabel.text = "Image: \(currentGameIndex)/\(totalKeys)"

    }

    func beginNewRound()
    {
        guard imageDictionary.isEmpty else {
            setButtonStatus(enabled:false)
            return
        }

        setButtonStatus(enabled:true)
        let word = imageDictionary.first?.key.lowercased()
        let value = imageDictionary.first?.value
        currentGame = Game(correctWord:word, image:value, guessedLetter: [])
        currentGameIndex += 1
        imageDictionary.removeValue(forKey: currentGame.correctAnswer)
        updateUI()
    }

    func setButtonStatus(enabled status: Bool)
    {
            for button in lettersButtons
            {
                button.isEnabled = status
            }
    }

    override func viewDidLoad() {
        super.viewDidLoad()
        beginNewRound()
        print(currentGame.correctAnswer)
        // Do any additional setup after loading the view, typically from a nib.
    }

    override func didReceiveMemoryWarning() {
        super.didReceiveMemoryWarning()
        // Dispose of any resources that can be recreated.
    }

}


HackerRank: Electronics Shop Challenge from Hacker Rank -

Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the items, given her budget.
Given the price lists for the store's keyboards and USB drives, and Monica's budget, find and print the amount of money Monica will spend. If she doesn't have enough money to both a keyboard and a USB drive, print -1 instead. She will buy only the two required items.

For example - with a budget of 10, two keyboards costing 3,1 & finally three drives available costing 5,2,8, the answer should be 9 as she is only able to purchase the keyboard for 3 and a drive for 5.
I've attempted to solve this logically and with good performance in mind. I'm not sure if I should be happy with my solution. I would appreciate any feedback.
My solution (which works) or my GitHub repo -
using System;
using System.Collections.Generic;
using System.Linq;

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

            Console.WriteLine(GetMoneySpent(new int[] { 3, 1 }, new int[] { 5, 2, 8 }, 10));
            Console.WriteLine(GetMoneySpent(new int[] { 5}, new int[] { 4 }, 5));
            Console.ReadLine();
        }

        static int GetMoneySpent(int[] keyboards, int[] drives, int budget)
        {
            if (budget == 0)
                return -1;

            // sort the two arrays so the highest values are at the front
            keyboards = SortArrayDescending(keyboards);
            drives = SortArrayDescending(drives);

            // delete any that are over our budget
            var affordableKeyboards = GetAffordableItems(keyboards, budget);
            var affordableDrives = GetAffordableItems(drives, budget);

            // make a list to contain the combined totals
            var combinedTotals = new List<int>();

            foreach (var keyboard in keyboards)
            {
                foreach (var drive in drives)
                {
                    combinedTotals.Add(keyboard + drive);
                }
            }

            // sort the list & delete anything over budget
            combinedTotals.Sort();
            combinedTotals.Reverse();
            combinedTotals.RemoveAll(n => n > budget);

            return combinedTotals.Count == 0 ? -1 : combinedTotals[0];
        }

        static int[] SortArrayDescending(int[] array)
        {
            Array.Sort(array);
            Array.Reverse(array);

            return array;
        }

        static int[] GetAffordableItems(int[] array, int budget)
        {
            return array.Where(n => n < budget).ToArray();
        }
    }
}

early pruning
This is very nice:
        // delete any that are over our budget

Doing it before sorting can slightly speed the sorting operation.
I say slightly because "items over budget" is determined by the input,
and it will be some fraction f of an input item category,
so the savings is O(f * n * log n).
early discard
This is a bigger deal.
        // sort the list & delete anything over budget

For k keyboards and d drives, the sort does O(k * d * log k * d) work.
Discarding within this loop would be an even bigger win.
consistent idiom
It was a little odd that you used
        combinedTotals.RemoveAll(n => n > budget);

and
        array.Where(n => n < budget).ToArray();

to accomplish the same thing.
There's no speed difference but consider phrasing the same thing in the same way.
reversing
If you pass into Sort something that implements the IComparer interface,
you can change the comparison order and thus skip the Reverse step entirely.
arithmetic
Arbitrarily choose one of the categories as the driving category, perhaps keyboard.
Sort the drive prices, while leaving the keyboards in arbitrary order.
Note the min drive price, and use that along with budget for immediately pruning infeasible keyboards.
Loop over all surviving keyboards.
Target price is budget - kb_price.
Do binary search over drives for the target,
finding largest feasible drive,
and use that to update "best combo so far".
No need to sort them, you need only retain the "best" one.


Correct usage of alignas in std::ostringstream wrapper Please take a look at this code:

class error_stream: boost::noncopyable
{
public:
    template<typename T>
    std::ostream& operator<<(T&& arg)
    {
        return strm() << std::forward<T>(arg);
    }
    std::string str() { return strm().str(); }
    bool empty() const { return !holder_.valid(); }
private:
    std::ostringstream& strm() { return holder_; }
    struct alignas(std::ostringstream) holder
    {
        holder(): ptr_{} {}
        ~holder()
        {
            if(valid())
                ptr_->~basic_ostringstream();
        }
        operator std::ostringstream&()
        {
            if(!valid())
                ptr_ = new (memory_) std::ostringstream{};
            return *ptr_;
        }
        bool valid() const { return ptr_; }
    private:
        char memory_[sizeof(std::ostringstream)];
        std::ostringstream* ptr_;
    } holder_;
};

Here I want to avoid creating std::ostringstream if there was no output made into it:

error_stream strm;
//strm << "...";
if(!strm.empty())
{
    //...get strm.str();
}

I use placement new/delete when a client outputs something into the stream. Do I need to use alingas for block of memory that will hold instance of std::ostringstream?

UPDATE: To give more context - this is part of THROW wrapper:

...
#define THROW_EX_WITH_LOCATION(EXCEPTION, LOCATION)                \
    for(error_stream strm;;                                        \
        strm.empty()?                                              \
            throw_exception<EXCEPTION>(LOCATION):                  \
            throw_exception<EXCEPTION>(LOCATION, strm.str()))      \
        strm
...

I don't want to create any stream if ther is no error message but solution should work with minumum overhead over version with just std::ostringstream.

Consider the following cases:

THROW();

and

THROW() << "some error";

I agree this looks like nitpicking.

This seems overcomplicated to me. Lazy-loading something doesn't require placement-new trickery and mucking around with alignments. Why not simply store a pointer to the stream which is only initialised when the user performs some kind of operation? This is the general way to do lazy-loading:

struct error_stream
{
private:
    std::unique_ptr<std::ostringstream> stream;

    // This should use make_unique, which you can find
    // or write yourself without too much hassle.
    void construct()
    {
        stream = std::unique_ptr<std::ostringstream>(
            new std::ostringstream);
    }

public:

    template <typename T>
    std::ostream& operator<<(T&& arg)
    {
        if(!stream) {
            construct();
        }
        (*stream) << std::forward<T>(arg);
        return *stream;
    }

    bool empty() const
    {
        return stream ? false : true;
    }

    std::string str()
    {
        if(empty()) {
             construct();
        }
        return stream->str();
    }
};

This seems to have the semantics you want (including being non-copyable due to using a std::unique_ptr) with much less hassle. You don't have to worry about placement new or any alignment requirements, which is going to make the code a -lot- harder to maintain.

Edit: If you really what to avoid the heap, I suppose you can use placement new. You allocate the memory for the stream when you create an error_stream, so I'm curious as to what problem you're trying to solve exactly. That being said, what you want to align is the storage for the ostringstream.

char memory_[sizeof(std::stringstream)];

Hence I'd use:

struct holder
{
....
private:
    alignas(std::ostringstream) char memory_[sizeof(std::stringstream)];
    ...
};


A simple web-app code - user registration. Is the layering ok? So knowing the little pieces is something different and putting them together is something different.

Here is the code where I try to follow good oop practices and 3 - layered structure.

Any review is greatly appreciated:

The form is located at registirationform.jsp.

The view layer:

public class RegistirationServlet extends HttpServlet {

    @Override
    protected void doPost(HttpServletRequest httpServletRequest, HttpServletResponse httpServletResponse)
            throws ServletException, IOException {

        httpServletRequest.setCharacterEncoding("utf-8");
        httpServletResponse.setContentType("text/html;charset=utf-8");

        try {
            UserRegistirationService userRegistirationService
                    = new UserRegistirationService(new AppUserAccessObject(new DatabaseConnectionImpl()));

            String username = httpServletRequest.getParameter("username");
            String password = httpServletRequest.getParameter("password");
            String email = httpServletRequest.getParameter("email");

            if(username.equals("")
                    || password.equals("")
                        || email.equals("")){
                List<String> errors = new ArrayList<String>();
                errors.add("Can you make sure you fill all the fields?");
                httpServletRequest.setAttribute("errors",errors);

                if(!username.equals("")){
                    httpServletRequest.setAttribute("username",username);
                }

                if(!email.equals("")){
                    httpServletRequest.setAttribute("email",email);
                }

                httpServletRequest.getRequestDispatcher("/registirationform.jsp").forward(httpServletRequest, httpServletResponse);
            }

            else {
                userRegistirationService.registerAppUser(username, password, email);
            }

        } catch (SQLException e) {
            e.printStackTrace();
            List<String> errors = new ArrayList<String>();
            errors.add("Registiration was not successful. Maybe username/email was already taken?");
            httpServletRequest.setAttribute("errors",errors);
            httpServletRequest.getRequestDispatcher("/registirationform.jsp").forward(httpServletRequest, httpServletResponse);
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }

    }
}

and the service layer:

public class UserRegistirationService {

    private AppUserAccessObject appUserAccessObject;

    public UserRegistirationService(AppUserAccessObject appUserAccessObject) {
        this.appUserAccessObject = appUserAccessObject;
    }

    public void registerAppUser(String username, String password, String email) throws SQLException {
        appUserAccessObject.insertUser(username, password, email);
    }
}

and the db layer:

public class AppUserAccessObject extends DataAccessObjectImpl implements DataAccessObject {

    public AppUserAccessObject(DatabaseConnectionImpl databaseConnection)
            throws IOException, SQLException, ClassNotFoundException {
        super(databaseConnection);
        setTableName("app_user");
    }

    public void insertUser(String username, String email, String password) throws SQLException {
        PreparedStatement preparedStatement = connection.prepareStatement("INSERT INTO " + tableName + "(username,email,password) VALUES(?,?,?)");
        preparedStatement.setString(1, username);
        preparedStatement.setString(2, email);
        preparedStatement.setString(3, password);
        preparedStatement.execute();
    }

}

Is all the code at correct layers?

I know you're asking strictly for feedback about the layers (which look fine to me), but in case you're looking for other feedback too:

if(username.equals("")
        || password.equals("")
            || email.equals("")){

You need to null check these values. getParameter can return null so you will get a NullPointerException if they don't exist.

List<String> errors = new ArrayList<String>();
errors.add("Registiration was not successful. Maybe username/email was already taken?");
httpServletRequest.setAttribute("errors",errors);

Can be done in one line if you want:

errors.add(Arrays.asList("Registiration was not successful. Maybe username/email was already taken?"));


How to find the common factors of 2 numbers Print the number of common factors of a and b.

input  > 10, 15

Output > 2

The common factors of 10, 15 are 1 and 5

My code

def print_factors(x,y):
    l = []
    for i in range(1, x + 1):
        if x % i == 0:
            l.append(i)
    m = []
    for i in range(1, y + 1):
        if y % i == 0:
            m.append(i)
    print (list(set(l).intersection(m)))
    #len(print (list(set(l).intersection(m))))

num1 = int(input("Enter a number: "))
num2 = int(input("Enter a number: "))

print_factors(num1,num2)

Is there any better way to optimize, like list comprehension. or using zip module

Indentation & style
One of the most distinctive features of Python is its use of indentation to mark blocks of code. Your code is not properly indented (each level of indentation should be equivalent to 4 spaces not like this:
def print_factors(x,y):
 l = []

like this:
def print_factors(x,y):
    l = []

Check pep8 https://www.python.org/dev/peps/pep-0008/ the official Python style guide, you'll find it helpful when learning the basics of Python code style and naming conventions.
Return
a function should not print anything, it should return
print (list(set(l).intersection(m)))
#len(print (list(set(l).intersection(m))))

and print is a function in Python 3.x, so it's very obvious it has no length
len(the commented line).
len
len() is used to get the length of sequences:
my_list = [1, 2, 3, 4]
print(len(my_list))

output: 4
Docstrings
Python documentation strings (or docstrings) provide a convenient way of associating documentation with Python modules, functions, classes, and methods. An object's docsting is defined by including a string constant as the first statement in the object's definition.
it is generally a good practice to use docstrings in your functions explaining what the function does that are usually enclosed within triple quotes:
def print_factors(number1, number2):
    """Return factors of number1 and number2."""
    # do things
    # return something

Descriptive variable names
l = []
for i in range(1, x + 1):
    if x % i == 0:
        l.append(i)
m = []
for i in range(1, y + 1):
    if y % i == 0:
        m.append(i)
print (list(set(l).intersection(m)))

what is l, what is i what is x ... names should be descriptive to improve the readability of your code (whether people that are reading your code and trying to understand or you reading your own code in the future) and here's an example:
factors_1 = []
factors_2 = []
for divisor in range(1, number1):
    if number1 % divisor == 0:
        factors1.append(divisor)
for divisor in range(1, number2):
if number2 % divisor == 0:
    factors2.append(divisor)

The code

Your function is not even doing what it should be doing (returning
the number of common factors not the factors themselves.
You don't have to iterate over the whole range of the number, you iterate up to the square root of the number is sufficient to find all factors.

This is how the code might look like:
def get_factors(number):
    """Generate factors of number."""
    yield 1
    for divisor in range(2, int(number ** 0.5) + 1):
        if number % divisor == 0:
            if number // divisor != divisor:
                yield divisor
                yield number // divisor
            if number // divisor == divisor:
                yield divisor

if __name__ == '__main__':
    number1 = int(input('Enter first number: '))
    number2 = int(input('Enter second number: '))
    number_1_factors = set(get_factors(number1))
    print(f'Factors of {number1}: {number_1_factors}')
    number_2_factors = set(get_factors(number2))
    print(f'Factors of {number2}: {number_2_factors}')
    common_factors = number_1_factors & number_2_factors
    print(f'Number of common factors of {number1} and {number2}: {len(common_factors)} factors.')


Do I need to close my FileOutputStreams? I have inlined temporary FileOutputStream that I am not able to explicitly close.

Is that a problem?

File raw = new File(uri.getPath());
Bitmap myBitmap = BitmapFactory.decodeFile(uri.getPath());

File compressedPicture = MEUtils.createTemporaryFile(getPackageName());
// see here
myBitmap.compress(Bitmap.CompressFormat.JPEG,
                  mObjectiveDefinitionForTakingPictureResult.getQuality(),
                  new FileOutputStream(compressedPicture));

JpegImageMetadata jpegMetadata = (JpegImageMetadata) Sanselan.getMetadata(raw);
TiffImageMetadata exif = jpegMetadata.getExif();
TiffOutputSet outputSet = exif.getOutputSet();
outputSet.setGPSInDegrees(app.locationListener.getLongitude(),
                          app.locationListener.getLatitude());

File compressedPictureWithMetadata = MEUtils.createTemporaryFile(getPackageName());
// see here
OutputStream compressedPictureWithMetadataOutputStream = new BufferedOutputStream(new FileOutputStream(compressedPictureWithMetadata));
new ExifRewriter().updateExifMetadataLossless(compressedPicture,
                                              compressedPictureWithMetadataOutputStream,
                                              outputSet);

EDIT

It seems that BufferedOutputStream can conveniently wrap a FileOutputStream, directly by inline it in the constructor: http://developer.android.com/reference/java/io/BufferedOutputStream.html

Yes, you do.

While the garbage collector does close your FileOutputStream (by calling finalize), it is not a good idea to rely on it because it runs unpredictably.

This means that if you do not close your streams explicitly, you may run into a limit on the number of simultaneously open files or into inability to open a file until you close the previous stream to it (on Windows) or into unpredictable file content if you open several streams to the same file (on Unix).


Updating positions of enemies every frame I am making a game for Android using Java and libGdx. I have an ArrayList of enemies that are updated each frame. The update method for the enemy looks like this:

public void update(float delta){

    if (waypointIndex < waypointCount){
        waypoint = path.getPoints().get(waypointIndex);

        distanceToWaypointX = waypoint.getX() - getCenterX();
        distanceToWaypointY = waypoint.getY() - getCenterY();

        directionToWaypoint = (float) Math.atan2(distanceToWaypointY, distanceToWaypointX);
        setRotation((float) Math.toDegrees(directionToWaypoint) - 180);

        translationX = (float) (Math.cos(directionToWaypoint) * getMovementSpeed() * delta);
        translationY = (float) (Math.sin(directionToWaypoint) * getMovementSpeed() * delta);

        distanceToWaypoint = (float) Math.hypot(distanceToWaypointX, distanceToWaypointY);

        if (distanceToWaypoint <= 5){
            waypointIndex++;
        }

        distanceTraveled += Math.sqrt(Math.pow(translationX, 2) + Math.pow(translationY, 2));

        translate(translationX, translationY);

    }
}

This works OK, but with 100 enemies the FPS starts to dip into the low 50's. I would like to keep a consistent 60 FPS and I plan to have more than 100 enemies on the screen at a time. How can i improve this code to make it more efficient?

Some things you could try:

Unless the waypoints change position, the objects will continue in the same direction each frame. This means

you don't have to recalculate directionToWaypoint (unless you have imperfect rotation). This includes cos(directionToWaypoint) and sin(directionTpWaypoint)
translationX and translationY become simple multiplication
distanceTravelled seems too complicated. Why isn't it just getMovementSpeed() * delta?


Updateable Priority Queue I've implemented an updateable priority queue as a part of implementing some single-source-shortest-path algorithms (Dijkstra, BF). I'm relatively new to Python.

class UpdateableQueue:
    def __init__(self,iterable=None):
        self._heap = []
        self._entry_finder = {}
        if iterable:
            for item in iterable:
                self._entry_finder[item[0]] = item[1]
                heapq.heappush(self._heap,(item[1],item[0]))

    def __getitem__(self, key):
        if key in self._entry_finder:
            return self._entry_finder[key]
        else:
            raise KeyError('Item not found in the priority queue')

    def __len__(self):
        return len(self._entry_finder)

    def __contains__(self, key):
        return key in self._entry_finder

    def push(self, key,priority):
        self._entry_finder[key] = priority
        heapq.heappush(self._heap, (priority, key))

    def pop(self):
        if not self._heap:
            raise IndexError("The heap is empty")

        value,key = self._heap[0]
        while key not in self or self._entry_finder[key] != value:
            heapq.heappop(self._heap)
            if not self._heap:
                raise IndexError("The heap is empty")
            value,key = self._heap[0]

        value, key = heapq.heappop(self._heap)
        del self._entry_finder[key]
        return key,value

Edit: a simple test case example of the UpdateableQueue

from UpdateableQueue.UpdateableQueue import UpdateableQueue

if __name__ == "__main__":
    # Initalizing empty queue
    queue = UpdateableQueue()
    # Inserting key=1,priority=4 element to the queue the heap is now of size 1, and the dict size 1
    queue.push(1,4)
    # editing key=1,priority=1 element to the queue the heap is now of size 2, and the dict size 1
    queue.push(1,1)
    # editing key=1,priority=2 element to the queue the heap is now of size 3, and the dict size 1
    queue.push(1,2)
    assert len(queue) == 1 # True
    assert 1 in queue # True
    # on pop we remove (key=1,value=1) from the heap and then pop out that value of (1,2), followed by
    # removing that key from the dict
    key, value = queue.pop()
    assert 1 not in queue #True
    assert key == 1 # True
    assert value == 2 # True
    # Inserting key=2,priority=5 element to the queue the heap is now of size 2, and the dict size 1
    queue.push(2,5)
    assert len(queue) == 1
    # We "clean" the remaining (1,4) element from the heap and return pop (2,5) as expected.
    key, value = queue.pop()
    assert key == 2  # True
    assert value == 5  # True

Your code looks good, there's not much for me to review, but here are a couple improvements/changes I would make.

Improvements

Docstrings: You should include a docstring at the beginning of every method/class/module you write. This will help any documentation catch what your code is supposed to accomplish.
If/Else: If you return a value in the if, then you don't need an else. You should just put the else code after the if, instead of inside an else, like so:

if key in self._entry_finder:
    return self._entry_finder[key]
else:
    raise KeyError('Item not found in the priority queue')

to

if key in self._entry_finder:
    return self._entry_finder[key]
raise KeyError('Item not found in the priority queue')

Updated Code

class UpdateableQueue:
    """ An updateable priority queue class """
    def __init__(self, iterable=None):
        self._heap = []
        self._entry_finder = {}
        if iterable:
            for item in iterable:
                self._entry_finder[item[0]] = item[1]
                heapq.heappush(self._heap, (item[1], item[0]))

    def __getitem__(self, key):
        """
        Returns the item with the specified key, if exists. Else,
        it raises a `KeyError` exception
        """
        if key in self._entry_finder:
            return self._entry_finder[key]
        raise KeyError('Item not found in the priority queue')

    def __len__(self):
        """ Returns the length of the queue """
        return len(self._entry_finder)

    def __contains__(self, key):
        """ Returns a boolean based on if the key is in the queue """
        return key in self._entry_finder

    def push(self, key, priority):
        """ Pushses a priority into the queue """
        self._entry_finder[key] = priority
        heapq.heappush(self._heap, (priority, key))

    def pop(self):
        """ Removes a priority from the queue """
        if not self._heap:
            raise IndexError("The heap is empty")

        value, key = self._heap[0]
        while key not in self or self._entry_finder[key] != value:
            heapq.heappop(self._heap)
            if not self._heap:
                raise IndexError("The heap is empty")
            value, key = self._heap[0]

        value, key = heapq.heappop(self._heap)
        del self._entry_finder[key]
        return key, value


Time complexity of Max counters As per the instructions are given in MaxCounters-Codility,

  You are given N counters, initially set to 0, and you have two possible operations on them:

  increase(X) − counter X is increased by 1,
  max counter − all counters are set to the maximum value of any counter.

  A non-empty array A of M integers is given. This array represents consecutive operations:

  if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
  if A[K] = N + 1 then operation K is max counter.

I have written this code

public int[] maxCount(int[]A,int N) {
    int[] I = new int[N];
    for (int i = 0; i < A.length; i++) {
        try {
            I[A[i] - 1]++;
        } catch (Exception e) {
            Arrays.sort(I);
            Arrays.fill(I, I[I.length - 1]);
        }
    }
    return I;
}

It gives correct answers for all test cases. Any Idea to do this with time complexity O(N). Its currently on O(N*M).

Lets start with the time complexity of your current algorithm:

for (int i = 0; i < A.length; i++) has a time complexity of O(M) (Length of array 'A' is 'M')
Arrays.sort(I) has a time complexity of O(N*log(N))1
Arrays.fill(I, I[I.length - 1]) has a time complexity of O(N) (The number of counters)

That means the complexity of your current algorithm is O(N^2 * log(N) * M).

You can replace the sorting by keeping track of the maximum value for all counters like this:

public int[] maxCount(int[] A, int N)
{
    int[] I = new int[N];
    //Initialize the max value to 0
    int max = 0;

    for (int i = 0; i < A.length; i++)
    {
        if (A[i] == N + 1)
        {
            Arrays.fill(I, max);
        }
        else
        {
            I[A[i] - 1]++;

            if (I[A[i] - 1] > max)
            {
                //Update the max value
                max = I[A[i] - 1];
            }
        }
    }
    return I;
}

The time complexity of this version is now O(M * N). This version is also using if statements to control the flow of the program as opposed to exceptions which is an anti-pattern2.

UPDATE: I've used the suggestion of Mees de Vries from his comment to implement a data structure for the problem. The complexity of the function reading the instruction incrementCounters() is O(n).

public class SynchronizedCounters
{
    private int[] counters;
    private int size;
    private int base = 0;
    private int max = 0;
    private final int INSTRUCTION_OFFSET = 1;

    public SynchronizedCounters(int size)
    {
        this.size = size;
        this.counters = new int[size];
    }

    public void incrementCounters(int[] instructions)
    {
        for (int instruction : instructions)
        {
            int instruct = instruction - INSTRUCTION_OFFSET;

            if (instruct >= size)
            {
                base = max;
            }
            else
            {
                normalizeCounter(instruct);

                counters[instruct]++;

                if (counters[instruct] > max)
                {
                    max = counters[instruct];
                }
            }
        }
    }

    public Integer getCounterValue(int counter)
    {
        normalizeCounter(counter);
        return counters[counter];
    }

    private void normalizeCounter(int index)
    {
        counters[index] = java.lang.Math.max(counters[index],base);
    }
}

Example using the class:

public static void main(String[] args)
    {
        SynchronizedCounters synchronizedCounters = new SynchronizedCounters(5);
        synchronizedCounters.incrementCounters(new int[]{1, 1, 1, 3, 2, 1, 1, 6, 2, 3});
        System.out.println("Value of first counter: " + synchronizedCounters.getCounterValue(0));
    }

Output:

Value of first counter: 5

1 https://stackoverflow.com/questions/21219777/the-running-time-for-arrays-sort-method-in-java

2 https://web.archive.org/web/20140430044213/http://c2.com/cgi-bin/wiki?DontUseExceptionsForFlowControl


Python XML parsing, extraction and renaming files I've written some code to:

Parse an XML file.
Extract some strings.
Make copies of the original XML whose names are suffixed with the extracted strings.

Please review this.

from lxml import etree as ET
import re

def create_paramsuffix_copies(xmlfile):

    NSMAP = {"c": "http://www.copasi.org/static/schema"}

    parsed = ET.parse(xmlfile)

    list_of_params = []

    for a in parsed.xpath("//c:Reaction", namespaces=NSMAP):
        for b in a.xpath(".//c:Constant", namespaces=NSMAP):
            list_of_params.append((a.attrib['name'])+'_'+(b.attrib['name']))

    return list_of_params

def add_suffix(xmlfile, name_suffix):

    parsed = ET.parse(xmlfile) #parse xml

    xmlfile = re.sub('.cps', '', xmlfile) #remove suffix

    parsed.write(xmlfile+'_'+name_suffix+'.cps',
                 xml_declaration = True,
                 encoding = 'utf-8',
                 method = 'xml')

modelfile = 'ct.cps'

for a in create_paramsuffix_copies(modelfile):
    add_suffix(modelfile,a)

Some style changes can happen, most are described here.

Using single letter variable names can be hard to understand, and don't explain what the data is well. It is good not to use them.
str.format is the best way to put variables into strings. E.G. '{}_{}.cps'.format(xmlfile, name_suffix)
CONSTANTS should be all caps. MODEL_FILE = 'ct.cps'
When passing 'kwargs' don't put spaces around the = operator. E.G. encoding='utf-8'
Use new-lines sparingly.
In-line comments are harder to read then comments before the code.
Comments should have a space between the '#' and the comment.

It may be good to change create_paramsuffix_copies to a generator, in this case it should be faster than making a list.

def create_paramsuffix_copies(xmlfile):
    NSMAP = {"c": "http://www.copasi.org/static/schema"}
    parsed = ET.parse(xmlfile)
    for a in parsed.xpath("//c:Reaction", namespaces=NSMAP):
        for b in a.xpath(".//c:Constant", namespaces=NSMAP):
            yield '{}_{}'.format(a.attrib['name'], b.attrib['name'])

You could add docstrings to your program so people know what the functions do at a later date.

But it looks really good!


Fun crypto problem: Exploiting a vulnerable encryption scheme with Python I came across a question asked here and here on the Crypto Stack Exchange site, and decided to analyze it as a kind of case study. To demonstrate the concept, I wrote a short python script depicting the proposed encryption scheme. It's mostly list comprehensions or generator expressions and bitwise operations.

$$C=E_k(m)$$
$$C_\alpha = C\oplus m$$
$$C_\beta = \overline{C}$$
$$C_\Omega = C_\alpha\ ^\frown\ C_\beta$$

#!/usr/bin/env python3

from Crypto.Cipher import DES

m = b'secret!!'
k = b'qwerty!!'
E = DES.new(k, DES.MODE_ECB)
C = E.encrypt(m)

C_alpha = int('0b'+''.join([f"{x:08b}" for x in C]), 2) ^ \
          int('0b'+''.join([f"{x:08b}" for x in m]), 2)

C_beta  = int('0b'+''.join([f"{x:08b}" for x in C]), 2) ^ \
          int('0b' + '1' * len(''.join([f"{x:08b}" for x in C])), 2)

C_omega = f"{C_alpha:064b}" + f"{C_beta:064b}"

if __name__ == '__main__':
    print(C_omega)

Then I ended up with this alternative version. If you want to try it out, save it as bad_scheme.py so it can work properly with the next script:

#!/usr/bin/env python3

from Crypto.Cipher import DES

m = b'secret!!'
k = b'qwerty!!'
E = DES.new(k, DES.MODE_ECB)
C = E.encrypt(m)

def bitwise_xor(bits_a, bits_b):
    bits_out = ''.join([str(int(x)^int(y)) for x, y in zip(bits_a, bits_b)])
    return(bits_out)

def bitwise_complement(bits_in):
    bits_out = ''.join([str(~int(x)+2) for x in bits_in])
    return(bits_out)

def C_alpha():
    bits_out = bitwise_xor(''.join([f"{x:08b}" for x in C]),
                           ''.join([f"{x:08b}" for x in m]))
    return(bits_out)

def C_beta():
    bits_out = bitwise_complement(''.join([f"{x:08b}" for x in C]))
    return(bits_out)

def C_omega():
    bits_out = C_alpha() + C_beta()
    return(bits_out)

if __name__ == '__main__':
    print(C_omega())

And here's what is essentially a working exploit of the (hypothetical) proposed encryption scheme's vulnerability; demonstrating the plaintext can be revealed without the key. It imports the final ciphertext and the bitwise functions from the first script, and works backwards, and complements \$C_\beta\$ to get \$C\$ (because \$C_\beta\$ is essentially just \$\overline{C}\$), then \$C \oplus C_\alpha\$ to reveal \$m\$ without requiring \$k\$. So:

$$\overline{C_\beta}=C$$
$$C_\alpha \oplus C=m$$

#!/usr/bin/env python3

from bad_scheme import C_omega, bitwise_xor, bitwise_complement

def C_alpha():
    bits_out = C_omega()[:int(len(C_omega())/2)]
    return(bits_out)

def C_beta:
    bits_out = C_omega()[int(len(C_omega())/2):]
    return(bits_out)

def C():
    bits_out = bitwise_complement(C_beta())
    return(bits_out)

def m():
    bits_out = bitwise_xor(C_alpha(), C_beta())
    return(bits_out)

if __name__ == '__main__':
    print(''.join([chr(int(m()[i:i+8],2)) for i in range(0,len(m()),8)]))

So, there it is. Just thought I'd put it out there and see what everyone thinks, which style is better, what's good about it, what's bad about it, and what I can do to improve it. It's not a real encryption scheme or anything, I'm mainly interested in feedback regarding design and execution, the handling of bitwise operations, and the general layout and structure of the code. I tried implementing a class and a few things to make it more robust and useful, but I couldn't pull it off. Also, is it better organized as functions? Or doing the same thing in fewer lines, just defining and operating on variables, and declaring no functions at all.

The conversions to bit-strings, then ints and back to strings are unnecessary.  m and k are bytes, so the elements (e.g., m[0] or k[i]) are already integers in the range 0-255;  bitwise operators can be applied to the elements directly.

I think routines in the Crypto library return strings, so the encrypt() return value might need to be encoded before using it.

from Crypto.Cipher import DES

m = b'secret!!'
k = b'qwerty!!'
E = DES.new(k, DES.MODE_ECB)
C = E.encrypt(m)

C = C.encode()  # <- needed if encrypt() returns a string (i.e., not bytes)

C_alpha = bytes(x^y for x,y in zip(C, m))

C_beta  = bytes(x^0xff for x in C)

C_omega = C_alpha + C_beta


Counting pairs of integers whose sum is less than a given threshold Recently I was going through this codechef problem while practicing for the upcoming zoc.

The problem asks to calculate number of combinations of the given numbers where the sum is less than another given number.

Previously I had a bruteforce algorithm which gave the correct answer but took a lot of time, in some cases even more than a second which raised a TLE error in codechef.

I changed my whole algorithm to get rid of that TLE error and also almost got that but for the last test it still gets stuck.

#include <iostream>
#include <vector>
#include <algorithm>
int main(){
    std::vector<long long> tstCases;
    std::vector<long long> okset;
    std::vector<long long> testset;
    for(int i =0;i<2;i++){
        long long cases;
        std::cin >> cases;
        tstCases.push_back(cases);
    }
    long long n = tstCases.at(0);
    long long k = tstCases.at(1);
    for(long long i =0;i<n;i++){
        long long cases;
        std::cin >> cases;
        if(cases<=k){
            if(cases < k/2){
                okset.push_back(cases);
            }else{
                testset.push_back(cases);
            }
        }
    }
    long long l = okset.size();
    long long p1 = (l*(l-1))/2;
    long long p2 = 0;
    sort(testset.begin(),testset.end());
    for(long long itr1 : okset){
        for(long long itr2 : testset){
            if(itr1+itr2 >= k){
                break;
            }else{
                p2++;
            }
        }
    }
    long long p = p1+p2;
    std::cout << p << std::endl;
    return 0;
}

Note : I am using long long because the problem instructed me to do so and I am lazy enough to do it by myself so I used replace all. Sorry for that.

A better algorithm

Your current algorithm has a worst case time of \$O(n^2)\$, when the list is half filled with zeroes, and half filled with k/2.  You can solve the problem in \$O(n \log n)\$ time by doing the following:

Sort the input.
Use two indices, one starting at the low end and one starting at the high end.  Call these indices i and j.
For each i, walk j down until a[i] + a[j] < k.  When this happens, add j-i to the solution count, and increment i.  Do not reset j.
Stop when i >= j.

Steps 2-4 solve the problem in \$O(n)\$ time, but the sort in step 1 takes \$O(n \log n)\$ time.  Here is a code snippet to illustrate the key part:

for (int i=0, j=len-1; i < j; i++) {
    while (j > i && a[i]+a[j] >= k)
        j--;
    count += j - i;
}


Showing links to Contributor Breakdown on Stackoverflow Docs So Stackoverflow Documentation has added "Contributor Breakdown". For any given topic (and example) people can display who contributed in which way.

That page is only available if you know the link though. And it's not linked publicly in any way. Since I like these hidden pages, but I keep forgetting the correct URLs to use, I wrote a short userscript to insert these links where relevant:

// ==UserScript==
// @name         Documentation contributor links
// @namespace    http://github.com/Vogel612/mini-se-userscripts/documentation-contributor-breakdown
// @version      0.1
// @description  Add links to the contributor breakdown for topics and examples on stackoverflow documentation.
// @author       Vogel612
// @include      /https?:\/\/stackoverflow\.com\/documentation\/.*
// @grant        none
// @run-at       document-end
// ==/UserScript==

(function() {
    // these are in here for debugging purposes
    document.addLinks = addLinks;
    document.addContributorLink = addContributorLink;
})();
// because the page is modified on SE side after loading. 2 secs should be enough to wait
setTimeout(addLinks, 2000);

function addLinks() {
    'use strict';
    let topicLink = document.querySelectorAll("a.doc-topic-link")[0];
    let topicMenuContainer = document.querySelector("div.docs-menu.topic-menu");
    addContributorLink("topic", topicLink.href.split('/')[5], topicMenuContainer);

    let exampleLinks = document.querySelectorAll(".example-link a.doc-example-link");
    let exampleMenus = document.querySelectorAll(".example-link div.example-menu.docs-menu");
    for (var i = 0; i < exampleLinks.length; i++) {
        let currentLink = exampleLinks[i];
        let currentMenuContainer = exampleMenus[i];
        addContributorLink("example", currentLink.href.split('/')[7], currentMenuContainer);
    }
}

function addContributorLink(section, linkId, menu) {
    'use strict';
    let href = `/documentation/contributors/${section}/${linkId}`;
    let elem = document.createElement("A");
    elem.href = href;
    elem.innerHTML = "CB";
    elem.title = "Contributor Breakdown";
    menu.insertBefore(elem, menu.children[0]);
}

Note that the documentation pages are modified by StackOverflow after loading and that removes the link, if I add it before the page is completely built. That's why I run addLinks() with a 2 second delay.

Any and all aspects are up for critique, as always :)

You're using 'use strict'; in all functions except the top one. Why not declare it at the top of your file?

You seem to have thought about readability. You're declaring variables for just that purpose here:

    let currentLink = exampleLinks[i];
    let currentMenuContainer = exampleMenus[i];

So why oh why do I see magic numbers in your code?

setTimeout(addLinks, 2000);
let topicLink = document.querySelectorAll("a.doc-topic-link")[0];
topicLink.href.split('/')[5]
currentLink.href.split('/')[7]
menu.insertBefore(elem, menu.children[0]);

Of those 5, arguably the first and latter are acceptable. The 3rd and 4th are the most magical of the lot. You explained the first in a comment, but I'd personally move it to a variable.


Does this C binary search tree have memory leaks? I am new to C, so I have been trying to get practice doing some coding.

Usually I use languages like Java, python, ruby, etc: Garbage collected languages. So manually cleaning up is new to me and I would appreciate any advice on whether there are major flaws in my approach.

Also any other comments on the overall idomatic-ness of this code, and things that I need to watch out for as I try to learn more C. (If it matters, I am compiling this to the c99 standards)

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

/* a reference counted BST node... */
typedef struct _node node;
struct _node {
    char *word;
    unsigned int refs;
    node *left;
    node *right;
};

/* allocate a node onto the heap.
 * copy word into a new array so that it can free it when it wants to
 * later without fear of clobbering another node's string.
 *
 * TODO: Maybe implement word counting so that if someone else adds a
 *       word that's already in the tree, I don't need to store two
 *       instances.
 */
node* node_new(char *word) {
    node *n = malloc(sizeof(node));

    char *nword = malloc(strlen(word) + 1);
    memcpy(nword, word, sizeof(nword));
    n->word = nword;

    n->refs = 0;
    n->left = NULL;
    n->right = NULL;

    return n;
}

/* Decrement the references and if it is determined that no one holds
 * a ref to this object, then free it and check its children.
 *
 * Return the number of nodes freed in this manner. If this node has
 * referents, then return 0 since no nodes were freed.
 */
int node_del(node *n) {
    n->refs -= 1;

    if (n->refs > 0) return 0;

    int removed = 1;

    if (n->left != NULL)
        removed += node_del(n->left);

    if (n->right != NULL)
        removed += node_del(n->right);

    free(n->word);
    free(n);

    return removed;
}

/* replace link with n.
 * Cleans up link if needed.
 */
void node_setlink(node **link, node *n) {
    if (*link != NULL) {
        node_del(*link);
    }

    n->refs += 1;
    *link = n;
}

/* Add a node to the BST.
 */
void node_additem(node *root, node *n) {
    int comp = strcmp(root->word, n->word);

    node **target = (comp > 0) ? &(root->left) : &(root->right);

    if (*target == NULL)
        node_setlink(target, n);
    else
        node_additem(*target, n);
}

/* Traverse the BST in order, dumping the words to standard out.
 * No side effects.
 */
void node_traverse(node *root) {
    if (root->left != NULL)
        node_traverse(root->left);

    printf("%s\n", root->word);

    if (root->right != NULL)
        node_traverse(root->right);
}

/* Go through each argument, adding it to the tree. Then traverse the tree. Then
 * free the tree.
 */
int main(int argc, char **argv) {
    if (argc < 3) {
        printf("Please give me two arguments, or there won't be anything to sort!");
        return 1;
    }

    node *n;

    node_setlink(&n, node_new(argv[1]));

    for (int i = 2; i < argc; i++) {
        node_additem(n, node_new(argv[i]));
    }

    node_traverse(n);
    printf("n is %s %d\n", n->word, n->refs);
    printf("%d removed when n freed.\n", node_del(n));

    return 0;
}

The code looks nice.  Just a few comments:

In new_node, your word-copying is wrong as you use sizeof(nword) where
nword is a pointer.  Using sizeof on a pointer gives only the size of the
pointer itself, not the size of what it points to.  try it with some long
words.  Your word copying could either use strdup or if you don't have that,
write your own.

In main, set n to NULL before using it.

There are no checks for malloc failure.  It is good practice to check, but the
only thing one can do is often to exit.

It is best to avoid leading underscore on identifiers (they are reserved).  And it is generally better to use explicit braces around statements even when strictly unnecessary.


Make utility using LINQ Make() takes projects with a list of tuples representing project references in the form of (Dependency, Dependent) and returns projects in the order to be build:

static void Main(string[] args)
{
    var projects = new[] { "a", "b", "c", "d", "e", "f" };
    var dependencies = new[] { ("a", "b"), ("a", "c"), ("e", "f"), ("c", "f"), ("f", "d") };
    Console.WriteLine(
        string.Join(", ", Make(projects, dependencies))); // a, e, b, c, f, d
}

Where:

static IEnumerable<string> Make(
    IEnumerable<string> projects,
    IEnumerable<(string Dependency, string Dependent)> references)
{
    var dependents = new HashSet<string>(references.Select(d => d.Dependent));
    var build = new HashSet<string>(projects.Except(dependents));
    return
        !projects.Any() ? Enumerable.Empty<string>() :
        !build.Any() ? throw new Exception("Circled references detected.") :
        build.Concat(Make(
            projects.Except(build).ToArray(),
            references.Where(r => !build.Contains(r.Dependency)).ToArray()));
}

What about run-time complexity of this one? Could it be optimized?

Exit early

Instead of stuffing everything in one return statements, return as early as possible.

if (!projects.Any()) return Enumerable.Empty<string>();

can be the first statement of your method. It saves recreating the hashset objects and it makes the flow of your method with its recursion more clear. I think sacrificing a bit of "conciseness" for readability is worth it.

ToArray

Are unnecessary and cause additional loops over your sets.

Except and HashSet

Enumerable.Except is already implemented using sets. The second argument is added to a set and the first is streamed through it. Creating the HashSet manually is a wasted effort. See the reference source.

So dependents can just be:

var dependents = references.Select(d => d.Dependent);

Contains and HashSet

Contains on the other hand benefits from the HashSet overload, since the Enumerable.Contains implementation just loops over the sequence. So build should be a HashSet to cope with larger inputs. While we're at it, we're using Linq, so ToHashSet().

static IEnumerable<string> Make(
    IEnumerable<string> projects,
    IEnumerable<(string Dependency, string Dependent)> references)
{
    if (!projects.Any())
    {
        return Enumerable.Empty<string>();
    }
    var dependents = references.Select(d => d.Dependent);
    var build = projects.Except(dependents).ToHashSet();
    if (!build.Any())
    {
        throw new Exception("Circled references detected.");
    }
    else
    {
        return build.Concat(Make(
              projects.Except(build),
              references.Where(r => !build.Contains(r.Dependency))));
    }
}


BFS implementation that walks a tile-based field I wrote a BFS implementation that walks a tile-based field. It takes a function that should return true for walkable tiles and false for walls. It also takes the start and end points. It currently takes about 5 seconds to find the shortest path from (0, 0) to (1000, 1000) which isn't bad, but it really isn't great.

import qualified Data.HashSet as H
import Data.Maybe (mapMaybe, isNothing)
import Data.List (foldl')

bfs ::
    (Int -> Int -> Bool) -> -- The field function. Returns True if tile is empty, False if it's a wall
    (Int, Int) -> -- Starting position
    (Int, Int) -> -- Final position
    Int -- Minimal steps
bfs field start end = minSteps H.empty [start] 0
    where
        minSteps visited queue steps
            |end `elem` queue = steps + 1
            |otherwise = minSteps newVisited newQueue (steps + 1)
            where
                (newVisited, newQueue) = foldl' aggr (visited, []) queue
                aggr (vis, q) node = if H.member node vis
                    then (H.insert node vis, neighbors node ++ q)
                    else (vis, q)
                neighbors (nx, ny) = filter (uncurry field) $ map (\(x, y) -> (nx + x, ny + y)) [(1, 0), (0, -1), (-1, 0), (0, 1)]

hugeField x y = x >= 0 && x <= 1000 && y >= 0 && y <= 1000

main = print $ bfs hugeField (0, 0) (1000, 1000)

I managed to make it five times faster but my solution uses some ad-hoc hacks.

First, I replaced queue with a set. This makes checking for solution faster and allows to update visited with single set-union operation.

bfs field start end = minSteps H.empty (H.singleton start) 0
    where
        minSteps visited queue steps
            |end `H.member` queue = steps + 1
            |otherwise = minSteps newVisited newQueue (steps + 1)
            where
                -- add whole frontier to visited set
                newVisited = queue `H.union` visited
                -- make next frontier from non-visited neighbors
                newQueue
                  = H.fromList (concatMap neighbors $ H.toList queue)
                  `H.difference` newVisited

This change makes the program slightly slower but it allows further optimizations.

Now to the ugly hack. Assuming you are on 64-bit machine and coordinates of empty tiles are in the range [0..2^31), it is possible to pack pair of coordinates into single Int. This will reduce memory footprint, improve cache locality and simplify hash calculation.

Here are two functions to pack/unpack coordinates:

enc :: (Int,Int) -> Int
enc (x,y) = shiftL (x .&. 0xFFFFFFFF) 32 .|. (y .&. 0xFFFFFFFF)

dec :: Int -> (Int, Int)
dec z = (shiftR z 32, z .&. 0xFFFFFFFF)

Use them to store packed coordinates in visited and queue and this will give you small improvement over the original code.

So, we made some ugly changes but gained very small speedup. Now it's time for magic. Changing single line of code will make the code 5 times faster.

Just import Data.IntSet instead of Data.HashSet.
Here is full code:

import qualified Data.IntSet as H
import Data.Bits

bfs field start end = minSteps H.empty (H.singleton $ enc start) 0
    where
        minSteps visited queue steps
            |enc end `H.member` queue = steps + 1
            |otherwise = minSteps newVisited newQueue (steps + 1)
            where
                newVisited = queue `H.union` visited
                newQueue
                  = H.fromList (concatMap (map enc.neighbors.dec) $ H.toList queue)
                  `H.difference` newVisited

                neighbors (nx, ny)
                  = filter (uncurry field)
                  $ map (\(x, y) -> (nx + x, ny + y))
                    [(1, 0), (0, -1), (-1, 0), (0, 1)]

enc :: (Int,Int) -> Int
enc (x,y) = shiftL (x .&. 0xFFFFFFFF) 32 .|. (y .&. 0xFFFFFFFF)

dec :: Int -> (Int, Int)
dec z = (shiftR z 32, z .&. 0xFFFFFFFF)

hugeField x y = x >= 0 && x <= 1000 && y >= 0 && y <= 1000

main = print $ bfs hugeField (0, 0) (1000, 1000)

The reason of such a speedup is that IntSet represents dense sets in much more compact form than HashSet. And this makes union and difference faster.


Bubble sort implementation with tests For practice I tried implementing a bubble sort algorithm in Ruby. I'm especially interested in creating clean DRY and KISS code and keeping things readable, but efficient. Any hints to improve things would be very much appreciated. The code looks like this:

class Sorter
  def initialize
  end

  def sort(stack)
    if stack.length == 0
      return stack
    else
      checkArguments(stack)
      if stack.length == 1
        return stack
      else
        newstack = []
        stackIsSorted = false
        while !stackIsSorted
          newstack = iterateThroughStack(stack)
          if  newstack == stack
            stackIsSorted = true
          else
            stack = newstack
          end
        end
        return newstack
      end
    end
  end

  def checkArguments(stack)
    stack.each do
      |element|
      if element.class != Float && element.class != Fixnum
        raise ArgumentError, "element detected in stack that is not an integer or double"
      end
    end
  end

  def iterateThroughStack(stack)
    newstack = []
    currentElement = stack[0]
    for i in (1...stack.length)
      if  currentElement < stack[i]
        newstack.push(currentElement)
        currentElement = stack[i]
      else
    newstack.push(stack[i])
      end
    end
    newstack.push(currentElement)
  end
end

Then, after reading about Test Driven Development, I started using this practice and since then, I think code makes more sense with unit tests. So below are the unit test I wrote:

require 'test/unit'
require 'lib/Sorter'

class Test_Sorter < Test::Unit::TestCase
  def setup
    @sorter = Sorter.new
  end

  def test_emptyStack
    stack = []
    assert_equal(stack, @sorter.sort(stack), "sorting empty stack failed")
  end

  def test_StackWithOneElement
    stack = [1]
    assert_equal(stack, @sorter.sort(stack), "sorting stack with one element: 1 failed")
    stack = ["a"]
    assert_raise (ArgumentError) { @sorter.sort(stack) }
  end

  def test_StackWithTwoElements
    stack = [2, 1]
    sorted_stack = [1, 2]
    assert_equal(sorted_stack, @sorter.sort(stack), "sorting stack with two elements: 1, 2 failed")
    stack = [2, "a"]
    assert_raise (ArgumentError) { @sorter.sort(stack) }
  end

  def test_StackWithThreeElements
    stack = [2, 3, 1]
    sorted_stack = [1, 2, 3]
    assert_equal(sorted_stack, @sorter.sort(stack), "sorting stack with three elements: 1, 2, 3 failed")
  end

  def test_StackWithFourElements
    stack = [4, 2, 3, 1]
    sorted_stack = [1, 2, 3, 4]
    assert_equal(sorted_stack, @sorter.sort(stack), "sorting stack with four elements: 1, 2, 3, 4 failed")
  end

end

Just a note about the tests: I'd create a test method for every assert call. For example,

  def test_StackWithTwoElements
    stack = [2, 1]
    sorted_stack = [1, 2]
    assert_equal(sorted_stack, @sorter.sort(stack), "sorting stack with two elements: 1, 2 failed")
    stack = [2, "a"]
    assert_raise (ArgumentError) { @sorter.sort(stack) }
  end

would be

  def test_StackWithTwoElements
    stack = [2, 1]
    sorted_stack = [1, 2]
    assert_equal(sorted_stack, @sorter.sort(stack), "sorting stack with two elements: 1, 2 failed")
  end

  def test_StackWithInvalidElement
    stack = [2, "a"]
    assert_raise (ArgumentError) { @sorter.sort(stack) }
  end

Too many asserts in one test is a bad smell. It's Assertion Roulette and you lost Defect Localization. If the first  assert_equal throws an exception you don't know anything about the results of the other assert calls which could be important because they could help debugging and defect localization.


Matrix of constrained sums using R In this post, I asked a question regarding how to create a matrix of integers where elements in each row satisfy a particular property.

The notation in the original post is a bit cumbersome so I will try to explain the question in a nutshell. I have a vector of integers cvec, which has length l-1, and I enumerate all the possibilities in a matrix such that every integer in each of the l columns is less than or equal to cvec[1] (first three lines of code). Then I iteratively reduce that large set possibilities into a smaller matrix, such that for a given row:

Consecutive elements taken 2,3,...l-1 at a time must be no larger than cvec[2], cvec[3], ..., cvec[l-1], respectively
The total sum of the l elements is equal to x.

By first subsetting mat to only those rows with sum x, and then running the nested for loops, I've been able to reduce the runtime by over 1/10th. For the above example, it now runs 7.8 seconds. However, I still think this could be faster if I somehow eliminate the nested loops. Any suggestions?

valid.counts2 <- function(x,l,cvec){
  #l>1
  vec = seq(from=0,to=cvec[1])
  lst = lapply(numeric(l), function(i) vec)
  mat = as.matrix(expand.grid(lst))
  mat = mat[which(rowSums(mat)==x),]

  if(l>2){
    #k=1 is redundant since all must be less than or equal to cvec[1]
    for (k in seq(from=2, to=l-1)){
      row.indx = NULL
      for (r in seq(l-k+1)){
        #pick out the index of the row(s) that satisfy constraint
        row.indx = which(rowSums(mat[,r:(r+k-1),drop=FALSE])<=cvec[k])
        #filter rows of mat
        mat = mat[unique(row.indx),]
      }
    }
  }
  return(mat)
}

Instead of a top-down (very memory intensive) approach, I would recommend a somewhat bottom-up approach, where you add one column at a time then do the reductions, add another column, etc. Try this:

expand.mat <- function(mat, vec) {
   out <- matrix(0L, nrow = nrow(mat) * length(vec),
                     ncol = ncol(mat) + 1)
   for (i in 1:ncol(mat)) out[, i] <- mat[, i]
   out[, ncol(mat) + 1] <- rep(vec, each = nrow(mat))
   return(out)
}

valid.counts3 <- function(x, cvec) {
   l   <-  length(cvec) + 1
   vec <- seq(from = 0, to = cvec[1])
   mat <- matrix(vec, ncol = 1)

   for (j in 2:l) {

      mat  <- expand.mat(mat, vec)
      rsum <- rowSums(mat)
      mat  <- mat[rsum <= x & rsum + cvec[1] * (l - j) >= x, ]

      for (i in 1:(j-1)) {
         k <- j - i + 1
         if (k == l) next
         rsum <- rowSums(mat[, i:j])
         mat  <- mat[rsum <= cvec[k], ]
      }
   }

   return(mat)
}

system.time({
   res <- valid.counts3(x = 148, cvec = c(36, 67, 92, 119))
})
#    user  system elapsed
#   0.279   0.036   0.319

Edit: And to handle a vector of x as input, make these slight changes. It will return a list of matrices.

valid.counts3 <- function(x, cvec) {
   l   <-  length(cvec) + 1
   vec <- seq(from = 0, to = cvec[1])
   mat <- matrix(vec, ncol = 1)

   for (j in 2:l) {

      mat  <- expand.mat(mat, vec)
      rsum <- rowSums(mat)
      mat  <- mat[rsum <= max(x) & rsum + cvec[1] * (l - j) >= min(x), ]

      for (i in 1:(j-1)) {
         k <- j - i + 1
         if (k == l) next
         rsum <- rowSums(mat[, i:j])
         mat  <- mat[rsum <= cvec[k], ]
      }
   }

   mat <- mat[rowSums(mat) %in% x, ]
   idx <- split(seq(nrow(mat)), rowSums(mat))
   return(lapply(idx, function(i, x) x[i, ], mat))
}

system.time({
   res <- valid.counts3(x = seq(from = 148, to = 155), cvec = c(36, 67, 92, 119))
})
#    user  system elapsed
#   0.333   0.048   0.381

sapply(res, nrow)
#  148  149  150  151  152  153  154  155
# 8649 5776 3600 2025 1024  441  144   25


Finds a position to break a string that is not part of a I have a 'read more' angular directive copied from:
https://github.com/doukasd/AngularJS-Components/blob/master/dd-text-collapse/dd-text-collapse.js

Some of my text can already have
 tags in it (I ONLY allow just
) so I just needed to handle that...below is only the extra code I wrote for this purpose.

Does it seems long for something seemingly trivial?

    //---All this to not break upon
 --
    if (text.includes('
')) {
        var charAtMaxLength = text.charAt(maxLength).toLowerCase();
        //console.log(charAtMaxLength);
        switch (charAtMaxLength) {
            case '<':
                if (text.charAt(maxLength + 3).toLowerCase() === '>') {
                    //console.log('Decrease maxLength by 1');
                    maxLength -= 1;
                }
                break;
            case 'b':
                if (text.charAt(maxLength - 1).toLowerCase() === '<') {
                    //console.log('Decrease maxLength by 2');
                    maxLength -= 2;
                }
                break;
            case 'r':
                if (text.charAt(maxLength - 2).toLowerCase() === '<') {
                    //console.log('Decrease maxLength by 3');
                    maxLength -= 3;
                }
                break;
            case '>':
                if (text.charAt(maxLength - 3).toLowerCase() === '<') {
                    //console.log('Increase maxLength by 1');
                    maxLength += 1;
                }
                break;
            default:
                //Do nothing.
                break;
        }
        //console.log(charAtMaxLength);
    }
    //--------------------------------------

You want to check if the letter that you have matched is part of a
.
But you're doing a strange check. That has bugs.

Lets say we test:

a<bc>d

we say that maxLength is 1.
You'll not break the <bc>.
For a dry test of this:

text.includes('
') # true
text.charAt(maxLength).toLowerCase() # '<'
switch ('<')
case '<':
text.charAt(maxLength + 3).toLowerCase() === '>' # true
maxLength -= 1 # maxLength = 0

Instead you can use, indexOf, slice and length to check if the text is not allowed.
This allows for you to easily change what you want to remove, and to expand on it.
Whilst being much smaller than what you have.

Get the, lowercase, charAt.
Find the indexof it in the remove string.
Set the start as maxLength minus the index.
Check if the index is in the remove string, and check if the slice of text from start to start plus the remove strings length is the remove string.
If it is change the maxLength to start - 1.

Or in JavaScript:

var text = 'a
d
';
var remove = '
';
var maxLength = 4;

var char = text.charAt(maxLength).toLowerCase();
var index = remove.indexOf(char);
var start = maxLength - index;
if (index != -1 && text.slice(start, start + remove.length).toLowerCase() == remove) {
    maxLength = start - 1;
}


Simple web form in PHP This is a simple web form handler in PHP that sends a completely filled web form to a email.

I see lots of repeating code. What is the best way to reduce repetition?
Is my way of checking for fields being empty good? The "empty()" method seems to also treat "0", "0.0" and similar values as empty.
Am I doing something that is unneccesary?

Any other criticism is appreciated.

<?php

if ( $_SERVER['REQUEST_METHOD'] !== 'POST' ) {
        die( 'Please use a form to send a message!' );
}

if ( !isset( $_POST['name'] ) || trim( $_POST['name'] ) === '' ) {
        die( 'Please enter your name!' );
}

if ( !isset( $_POST['phone'] ) || trim( $_POST['phone'] ) === '' ) {
        die( 'Please enter your phone number!' );
}

if ( !isset( $_POST['city'] ) || trim( $_POST['city'] ) === '' ) {
        die( 'Please enter your city!' );
}

$name = trim( $_POST['name'] );
$phone = trim( $_POST['phone'] );
$city = trim( $_POST['city'] );

$contents = '';

$contents .= "New order!\r\n";
$contents .= "\r\n";
$contents .= "Name: {$name}\r\n";
$contents .= "Phone number: {$phone}\r\n";
$contents .= "City: {$city}\r\n";

if ( mail( '<email removed>', 'New order!', htmlspecialchars($contents), 'From: <email removed>' ) ) {
    die( 'Thanks! We will contact you very soon!' );
} else {
    die( 'Unfortunately an error occurred. Please try again later.' );
}

To add to Quill's answer, use heredoc whenever you want to use multiline strings.

$contents = <<<CON
New order!

Name: {$name}
Phone number: {$phone}
City: {$city}
CON;

$content = htmlspecialchars($contents);

EDIT

Why & how it improves your code,

Much cleaners and improves readability
When you need double quotes inside the string you don't need to escape them
You don't have to worry about which characters to use when you need a line break.

A common use of this is when you write SQL queries, HTML or Email message bodies in your application. Basically multiline strings.