Stochastic simulation event timing So I'm learning bits and pieces of python.  Here's some code that just doesn't seem pythonic, and I'd like to improve it.  I'm doing stochastic simulations with a Gillespie style approach, but if that doesn't mean anything to you, no worries.  I'm trying to avoid some iterations and replace them with something like a list comprehension.  The code will work, only I'm looking for a better way to do the same thing.

First I calculate a stopping time (maxTime).  Then I calculate the time of an event (and store it if it's less than maxTime).  Then the time of the next event (and store again).  I repeat until I finally get an event happening after maxTime.

import random
maxTime = random.expovariate(1)

L = []
eventTime = random.expovariate(10)

while eventTime<maxTime:
    L.append(eventTime)
    eventTime += random.expovariate(10)

Any cleaner way to write this code?

If you're writing a simulation, it's probably worthwhile to add some abstractions to your code so that you can free your mind to think at a more abstract level.  Ideally, I would like to see

L = list(until_total(stop_time, poisson_process(10)))

(Consider not calling list() if you just need an iterable and not a list.)

Here is one way to get there:

from itertools import takewhile
from random import expovariate

def poisson_process(rate):
    while True:
        yield expovariate(rate)

def until_total(limit, iterable):
    total = [0]                 # http://stackoverflow.com/q/2009402
    def under_total(i):
        total[0] += i
        return total[0] < limit
    return takewhile(under_total, iterable)

stop_time = next(poisson_process(1))
L = until_total(stop_time, poisson_process(10))

Also, consider using more meaningful identifiers:

customer_arrivals = poisson_process(10)
cashier_yawns = poisson_process(1)
customer_interarrival_times = until_total(next(cashier_yawns), customer_arrivals)


Calculating average grades I'm a C# developer looking to learn more about Python and how to think in a more functional programming manner.

I have the following which takes a series of grades and returns the average:

grades = [100, 100, 90, 40, 80, 100, 85, 70, 90, 65, 90, 85, 50.5]

def grades_sum(scores):
    total = 0
    for score in scores:
        total += score
    return total

def grades_average(grades):
    return grades_sum(grades) / float(len(grades))

print(grades_average(grades))

What are some better functional programming / pythonic ways of approaching this problem?

In Python, there is a predefined function sum.  This completely negates your need for grades_sum(scores).

def grades_average(grades):
    return sum(grades) / float(len(grades))

Also, you do not need to cast len(grades) to float if you are using Python 3.


Keep reading user keyboard input if available, while echoing back the latest available On StackOverflow I have asked a question a few minutes ago, but then by trying a bit more, I found the answer myself, and I'm posting the resulting working code here for review.
What the code does, is waiting for, and repeatedly prompting the user to enter a character; when the user enters one, the program echoes it back and goes back to the previous mode, waiting for further input. The program assumes an initial implicit input of 'A'.
{-# language LambdaCase #-}

import Control.Concurrent
import Data.Maybe
import System.IO

main :: IO ()
main = do
  hSetBuffering stdin NoBuffering
  future_input <- newEmptyMVar
  work future_input 'l'

work :: MVar Char -> Char -> IO ()
work future_input latest_input = do
  forkIO $ putMVar future_input =<< getChar
  wait future_input latest_input
    where
      wait :: MVar Char -> Char -> IO ()
      wait future_input latest_input =
        tryTakeMVar future_input >>=
          \case Just input -> putStrLn ("new input " ++ return input)
                              >> work future_input input
                Nothing    -> putStrLn ("old input " ++ return latest_input)
                              >> threadDelay 100000
                              >> wait future_input latest_input

Some thoughts on about the code:

I've tried to use applicative/monadic style wherever I could, without compromising readability too much;
as regards the concurrentcy-handling part, basically the wait function, I preferred using the do sugar because I could hardly get something working this way.

With a bit of suggestion/help on Haskell's IRC channels, I came up with this, which doesn't forkIO at every recursion.
{-# language LambdaCase #-}

import Control.Concurrent
import Data.Maybe
import System.IO

main :: IO ()
main = do
  hSetBuffering stdin NoBuffering
  future_input <- newEmptyMVar
  forkIO $ pollInput future_input
  processInput future_input 'l'

pollInput :: MVar Char -> IO ()
pollInput future_input = (putMVar future_input =<< getChar) >> pollInput future_input

processInput :: MVar Char -> Char -> IO ()
processInput future_input latest_input = tryTakeMVar future_input >>=
    \case Just input -> putStrLn ("direction change " ++ return input)
                        >> processInput future_input input
          Nothing    -> putStrLn ("keep direction " ++ return latest_input)
                        >> threadDelay 100000
                        >> processInput future_input latest_input


Chat Viewer working with files I am writing a textual chat app for exercise purposes. All Chatters using my program have access to a network directory, and there my program is stored. This chat app consists of three programs. The user management program allows you to create and delete users. The messaging program allows you to write messages. The viewer program shows all messages.

Now I am about to find a strategy that is good for my viewer program. The code is not ordered yet, I just want to ask if the logic that is behind my code is suitable for a chat viewing program, or if there is a more sophisticated way to create such programs.

import java.io.FileInputStream;
import java.io.ObjectInputStream;
import java.io.IOException;
import java.io.File;

public class MessageViewerProgram {
    public static void main(String[] args) throws Exception {
        String saveDir = ".save/messages/";
        int fileName = 1;
        File file = new File(saveDir + fileName);
        while (true) {
            Thread.sleep(50);
            if (file.exists()) {
                Thread.sleep(20);
                try (FileInputStream fis = new FileInputStream(file);
                     ObjectInputStream ois = new ObjectInputStream(fis)) {
                    Message message = (Message) ois.readObject();
                    System.out.println(message.getSenderName() + ": " + message.getMessage());
                    fileName++;
                    file = new File(saveDir + fileName);
                } catch (IOException e) {
                    e.printStackTrace();
                } catch (ClassNotFoundException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

And this here is my "MessageWriterProgram". It is not finished yet, but it works already. I just post it because maybe it is needed to understand the problem, but you dont have to review the following class:

import java.util.Scanner;
import java.io.File;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.io.IOException;

public class MessageWriterProgram {
    public static void main(String[] args) {
        MessageWriterProgram mwp = new MessageWriterProgram();
        mwp.mainLoop();
    }

    private static final String SAVE_DIR_NAME = ".save/messages/";

    private Scanner scanner = new Scanner(System.in);
    private UserManager userManager;
    private User identity;

    public MessageWriterProgram() {
        scanner = new Scanner(System.in);
        userManager = new UserManager();
    }

    public void mainLoop() {
        if (!login()) {
            System.out.println("Login was not successful.");
            return;
        }
        System.out.println(identity.getName());

        while (true) {
            System.out.print("> ");
            String input = scanner.nextLine();
            if (!input.isEmpty()) {
                Message message = new Message(identity.getName(), input);
                saveMessage(message);
            }
        }
    }

    public void saveMessage(Message message) {
        // create file name that isn't used
        int filename = 1;
        while (true) {
            File file = new File(SAVE_DIR_NAME + filename);
            if (file.exists()) {
                filename++;
            } else {
                break;
            }
        }
        File file = new File(SAVE_DIR_NAME + filename);

        // store message
        try (FileOutputStream fos = new FileOutputStream(file);
             ObjectOutputStream oos = new ObjectOutputStream(fos)) {
            oos.writeObject(message);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    // returns if login was successful
    public boolean login() {
        System.out.print("Name: ");
        String name = scanner.nextLine();
        System.out.print("Password: ");
        String password = scanner.nextLine();
        identity = userManager.retainUserIdentity(name, password);
        return identity != null;
    }
}

I have some suggestions.
MessageViewerProgram

Instead of brute forcing all the messages in the directory, I suggest that you list them and iterate on them instead. You can use the method java.io.File#listFiles() for this.

File file = new File(saveDir);
File[] files = file.listFiles();

This will give you an array of the files in the message folder, and you can iterate.
File saveDir = new File(".save/messages/");

for (File currentMessageFile : saveDir.listFiles()) {
   try (FileInputStream fis = new FileInputStream(currentMessageFile);
            ObjectInputStream ois = new ObjectInputStream(fis)) {

      Message message = (Message) ois.readObject();
      System.out.println(message.getSenderName() + ": " + message.getMessage());
   } catch (IOException e) {
      e.printStackTrace();
   } catch (ClassNotFoundException e) {
      e.printStackTrace();
   }
}

MessageWriterProgram

The initialization of the MessageWriterProgram#scanner variable outside the constructor is useless, it's created  inside the constructor already.

private Scanner scanner;

public MessageWriterProgram() {
   scanner = new Scanner(System.in);
}

I suggest that you rename the method mainLoop in start or run or even execute.

MessageWriterProgram#saveMessage method

Rename the variable filename into fileName

I suggest that you extract the logic of counting the next file name in a method.

public void saveMessage(Message message) {
   // create file name that isn't used
   int fileName = getNextFilename();
   //[...]
}

private int getNextFilename() {
   int fileName = getNextFilename();

   while (true) {
      File file = new File(SAVE_DIR_NAME + fileName);
      if (file.exists()) {
         fileName++;
      } else {
         break;
      }
   }

   return fileName;
}

Instead of counting the messages in the loop, you can use the java.io.File#listFiles() and check the number of files in the folder.

private int getNextFilename() {
   File messageDirectory = new File(SAVE_DIR_NAME);
   File[] files = messageDirectory.listFiles();

   if (files != null) {
      return files.length + 1;
   } else {
      return 1;
   }
}

MessageWriterProgram#login method
In my opinion, this method is a bit useless and add confusion, since it does more than one thing.

Check if the User is present.
Update the identity variable.

If you inline it, it will be more readable and you can convert the identity variable to a local variable.
System.out.print("Name: ");
String name = scanner.nextLine();
System.out.print("Password: ");
String password = scanner.nextLine();

User identity = userManager.retainUserIdentity(name, password);

if (identity == null) {
   System.out.println("Login was not successful.");
   return;
}

Refactored MessageWriterProgram class
public class MessageWriterProgram {
   public static void main(String[] args) {
      MessageWriterProgram mwp = new MessageWriterProgram();
      mwp.mainLoop();
   }

   private static final String SAVE_DIR_NAME = ".save/messages/";

   private Scanner scanner;
   private UserManager userManager;

   public MessageWriterProgram() {
      scanner = new Scanner(System.in);
      userManager = new UserManager();
   }

   public void mainLoop() {
      System.out.print("Name: ");
      String name = scanner.nextLine();
      System.out.print("Password: ");
      String password = scanner.nextLine();

      User identity = userManager.retainUserIdentity(name, password);

      if (identity == null) {
         System.out.println("Login was not successful.");
         return;
      }

      System.out.println(identity.getName());

      while (true) {
         System.out.print("> ");
         String input = scanner.nextLine();

         if (!input.isEmpty()) {
            Message message = new Message(identity.getName(), input);
            saveMessage(message);
         }
      }
   }

   public void saveMessage(Message message) {
      // create file name that isn't used
      int fileName = getNextFilename();

      File file = new File(SAVE_DIR_NAME + fileName);

      // store message
      try (FileOutputStream fos = new FileOutputStream(file);
               ObjectOutputStream oos = new ObjectOutputStream(fos)) {
         oos.writeObject(message);
      } catch (IOException e) {
         e.printStackTrace();
      }
   }

   private int getNextFilename() {
      File messageDirectory = new File(SAVE_DIR_NAME);
      File[] files = messageDirectory.listFiles();

      if (files != null) {
         return files.length + 1;
      } else {
         return 1;
      }
   }
}


My own expandable list I wondered how an expandable list could be implemented. My first thought: You could create a class that has an array and you can create a new array each time the user wants to append an element and than you can copy the old array plus the new element into the new array. But this seems very inefficient to me. Then I read something about so called linked lists. The idea is very simple. Such a list has nodes. Nodes contain an object and another node. The nodes can be linked as required. I had my thoughts about that and I tried to write a class that follows this thought.

LinkedList.java

package linkedList;

public class LinkedList<T> {
    private Node<T> startNode;

    public LinkedList() {
        startNode = new Node<T>();
    }

    private Node<T> getEmptyNode() {
        Node<T> currentNode = this.startNode;
        while (currentNode.hasObject()) {
            currentNode = currentNode.getNextNode();
        }
        return currentNode;
    }

    public void insert(T object) {
        Node<T> emptyNode = getEmptyNode();
        emptyNode.setObject(object);
        emptyNode.setNextNode(new Node<T>());
    }

    public int getNumberOfElements() {
        Node<T> currentNode = startNode;
        int numberOfElements = 0;
        while (currentNode.hasObject()) {
            numberOfElements++;
            currentNode = currentNode.getNextNode();
        }
        return numberOfElements;
    }

    private Node<T> getNodeByIndex(int index) {
        Node<T> currentNode = startNode;
        for (int i = 0; i < index; i++) {
            currentNode = currentNode.getNextNode();
        }
        return currentNode;
    }

    public T get(int index) {
        return getNodeByIndex(index).getObject();
    }

    public void delete(int index) {
        if (index == 0) {
            startNode = getNodeByIndex(1);
            return;
        }

        // if index equals last available index
        if (index == (getNumberOfElements() - 1)) {
            Node<T> nodeBefore = getNodeByIndex(index - 1);
            nodeBefore.setNextNode(null);
            return;
        }

        Node<T> nodeBefore = getNodeByIndex(index - 1);
        Node<T> nodeBehind = getNodeByIndex(index + 1);
        nodeBefore.setNextNode(nodeBehind);
    }
}

Node.java

package linkedList;

public class Node<T> {
    private T object;
    private Node<T> nextNode;

    public Node() {
        this.object = null;
        this.nextNode = null;
    }

    public boolean hasObject() {
        return object != null;
    }

    public boolean hasNextNode() {
        return nextNode != null;
    }

    public T getObject() {
        return object;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    public void setObject(T object) {
        this.object = object;
    }
}

Main.java

package linkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.insert("Hallo");
        linkedList.insert("Test");
        linkedList.insert("Wie gehts?");
        linkedList.insert("Freuen sie sich?");
        System.out.println("Anzahl der Elemente: " + linkedList.getNumberOfElements());
        System.out.println("Drittes Element: " + linkedList.get(2));
        System.out.println("Alle Elemente:");
        for (int i = 0; i < linkedList.getNumberOfElements(); i++) {
            System.out.println(linkedList.get(i));
        }

        linkedList.delete(2);
        System.out.println("Alle Elemente:");
        for (int i = 0; i < linkedList.getNumberOfElements(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
}

Because this is my first attempt to do such stuff I am wondering what things can be improved. Is there a way to make this more efficient? Is the code clean and readable enough?

You are on the right track, and I think you would benefit by having your class implement the Java List<T> interface like so:

public class LinkedList<T> implements List<T> {

You would then have to change your methods so that their names and signatures conform to the interface. You can read about the details here for Java 7 or here for Java 8. If you do this then you could pass instances of your class into already implemented functions like Collections.sort.


Computing and Populating Excel Table With VBA I am trying to populate a table like this in Excel. I came up with a bunch
of loops to do this. I feel like this is a brute-force approach and may not work well when populating bigger tables.

Any other ways to populate values in Excel?

Sub Fill_SLA_priority()

    Dim SLAbyPrior      As Worksheet
    Dim wsAssignedTix   As Worksheet

    Dim ctP1            As Integer
    Dim ctP1RespSLA     As Integer
    Dim ctP1PlanSLA     As Integer
    Dim ctP1ResSLA     As Integer
    Dim ctP1All3SLA    As Integer

    Dim d              As Range

    Set SLAbyPrior = Worksheets("SLA by Priority")
    Set wsAssignedTix = Worksheets("AssignedTickets")

    For Each d In wsAssignedTix.Range(wsAssignedTix.Range("H1").End(xlDown), wsAssignedTix.Range("H" & Rows.count).End(xlUp))

            '' Loop through entire list to count number of P1 - P4, Request.
            '' P1
            '' Count number of Responded, Planned, Resolved, Overall SLA

            If d.Value = "Priority 1 Incident - Critical" _
                And (d.Offset(0, -1) = "Closed" Or d.Offset(0, -1) = "Resolved") Then

                    ctP1 = ctP1 + 1

                    If d.Offset(0, 2) = 1 Then ctP1RespSLA = ctP1RespSLA + 1
                    If d.Offset(0, 4) = 1 Then ctP1PlanSLA = ctP1PlanSLA + 1
                    If d.Offset(0, 6) = 1 Then ctP1ResSLA = ctP1ResSLA + 1
                    If d.Offset(0, 2) = 1 And d.Offset(0, 4) = 1 And d.Offset(0, 6) = 1 Then
                            ctP1All3SLA = ctP1All3SLA + 1
                    End If

            End If
    Next d

    '' Populating the cells in SLA_by_Priority
    With SLAbyPrior

            '' P1 - Resp SLA %
            .Range("B5") = ctP1RespSLA / ctP1

            '' P1 - Plan SLA %
            .Range("C5") = ctP1PlanSLA / ctP1

            '' P1 - Resl SLA %
            .Range("D5") = ctP1ResSLA / ctP1

            '' P1 - All 3 SLA %
            .Range("E5") = ctP1All3SLA / ctP1

    End With

End Sub

First things first - variable naming - help me. I look at your variables and have no idea what they are, what they are meant to do or how they should be used.

Dim SLAbyPrior      As Worksheet
Dim wsAssignedTix   As Worksheet

Dim ctP1            As Integer
Dim ctP1RespSLA     As Integer
Dim ctP1PlanSLA     As Integer
Dim ctP1ResSLA     As Integer
Dim ctP1All3SLA    As Integer
Dim d              As Range

Worksheets have a CodeName property - View Properties window (F4) and the (Name) field (the one at the top) can be used as the worksheet name. This way you can avoid set wsAssignedTix = Sheets("AssignedTickets") and instead just use AssignedTickets.
Integers - integers are obsolete. According to msdn VBA silently converts all integers to long.

Let's try to decipher what your variables are and give them meaningful names

d = priorityValue
ctP1 = countOfCritical?
ctP1RespSLA - countOfCriticalResponseServiceLevelAgreement?

Actually, I can't decipher them. Sorry.

For Each d In wsAssignedTix.Range(wsAssignedTix.Range("H1").End(xlDown), wsAssignedTix.Range("H" & Rows.Count).End(xlUp))

This could be done differently:

Dim lastRow As Long
lastRow = wsAssignedTix.Cells(Rows.Count, 8).End(xlUp).Row
Dim i As Long
For i = 1 To lastRow

Now change your if

Const CRITICAL_PRIORITY As String = "Priority 1 Incident - Critical"
Const CLOSED_OR_RESOLVED As String = "Closed Resolved"
If Cells(i, 8) = CRITICAL_PRIORITY And InStr(1, CLOSED_OR_RESOLVED, Cells(i, 7).Value) > 0 Then

Now do whatever all that adding is, but you can avoid the offset by just using the column number with the current row.

I'd also avoid doing the calculation in the With block by using a variable, personally.

Without really understanding what you're calculating, and assuming your values are either 1 or 0 you can probably just sum as you go rather than testing each offset cell for 1.

And, most likely, you'd benefit from loading the tickets sheet into an array and calculating on the array rather than the sheet.

Actually, what you could probably do is sort the tickets by critical and then just sum the columns for each status based on the count of critical tickets. That would be simpler.


Simple function to generate a list of letters I would like get some suggestions for improvement of this function, and alert me about any dodgy practices that you find.
I have been trying to learn python for a short time now and I would like to get some pointers on writing more pythonic code before I develop bad habits.

from string import ascii_uppercase, ascii_lowercase
from random import choice

def get_letters(case, n, random = False):
    """
    A function to generate a list of letters

    PARAMETERS
    ----------------------
    case (str) - type of case, 'u' for uppercase, 'l' for lowercase
    n (int) - number of letters to return
    random (bool) - specify if letters should be in random order

    RETURNS
    ----------------------
    if case is 'u', returns a list of uppercase letters
    if case is 'l', returns a list of lowercase letters
    if random = True a list of random letters will be returned (default is false)
    """

    case = case.lower()

    if random:
            if case == 'u':
                letters = [choice(ascii_uppercase) for i in range(n)]
            else:
                if case == 'l':
                    letters= [choice(ascii_lowercase) for i in range(n)]
    else:
        if case == 'u':
            letters = [ascii_uppercase[i] for i in range(n)]
        else:
            if case == 'l':
                letters= [ascii_lowercase[i] for i in range(n)]

    return letters

Some notes on your code:

def f(arg = False) -> def f(arg=False) (PEP8)
case = case.lower() Usually it's not a good idea to reuse variables: new values, new variable names.
else + indent + if = elif
Use (true_value if condition else false_value) for short conditional expressions.
ascii_uppercase[i] for i in range(n). This will fail if n is greater than the size of letters.
[choice(alphabet) for i in range(n)]. This repeats characters, is that ok? It seems more fitting to use random.sample(alphabet, n), which does not repeat elements.
case: It's not idiomatic to send strings this way. Use a boolean argument instead (as @oliverpool proposed).

I'd write:

from random import sample
from string import ascii_uppercase, ascii_lowercase

def get_letters(n, random=False, uppercase=False):
    """Return n letters of the alphabet."""
    letters = (ascii_uppercase if uppercase else ascii_lowercase)
    return (sample(letters, n) if random else list(letters[:n]))


Multilingual website with a database I created a multilingual site in MVC and I reached the current results, but I'm not sure it's the right way.

I have created a class named changeLanguage to change the language:

public ActionResult ChangeLanguage(String LanguageAbbrevation)
        {
            if (LanguageAbbrevation != null)
            {
                Thread.CurrentThread.CurrentCulture = CultureInfo.CreateSpecificCulture(LanguageAbbrevation);
                Thread.CurrentThread.CurrentUICulture = new CultureInfo(LanguageAbbrevation);

            }
            HttpCookie cookie = new HttpCookie("Language");
            cookie.Value = LanguageAbbrevation;
            Response.Cookies.Add(cookie);
            return RedirectToAction("Index","Home");

        }

Global.asax:

 protected void Application_BeginRequest(object sender, EventArgs e)
        {
            LanguageTB context = new LanguageTB();
            HttpCookie cookie = HttpContext.Current.Request.Cookies["Language"];
            if (cookie != null && cookie.Value != null)
            {
                System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo(cookie.Value);
                System.Threading.Thread.CurrentThread.CurrentUICulture = new System.Globalization.CultureInfo(cookie.Value);

            }

            else
            {
                System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en");
                System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en");

            }
        }

Controller:

 public ActionResult AboutUs()
 {
        HttpCookie cookie = HttpContext.Request.Cookies["Language"];
        var categoryList = context.SiteContents.Where(x => x.LanguageTB.CultureCode==cookie.Value)).ToList();
        return View(categoryList);
    }

I'm doing this again and again for every view:

 public ActionResult AllAttorney()
{
    HttpCookie cookie = HttpContext.Request.Cookies["Language"];
    var employeelist = context.Employees.Where(x => x.LanguageTB.CultureCode== mainLanguage.lb).ToList();
    return View(employeelist);
}

View:

 en

 az

 ru

         @RHome.MAttorney

         @RHome.MAboutUs

         @RHome.MNews

Language table:

  [Table("LanguageTB")]
public partial class LanguageTB
{
    public LanguageTB()
    {
        Articles = new HashSet
();
        Employees = new HashSet<Employee>();
        SiteContents = new HashSet<SiteContent>();
    }

    [Key]
    public int LanguageId { get; set; }

    [StringLength(50)]
    public string CultureCode { get; set; }

    [StringLength(100)]
    public string CultureName { get; set; }

    public virtual ICollection
 Articles { get; set; }
    public virtual ICollection<Employee> Employees { get; set; }
    public virtual ICollection<SiteContent> SiteContents { get; set; }
}

Too many Language Repetitions

You use the "Language" key a lot. What if you decide to rename it sometime? You'll need to search everywhere for this string. It'd be better if you encapsulated it or used a constant. I prefer extensions so it might look like this where you try to get the cookie and if it is not null ? then you get the value.

public static class HttpCookieCollectionExtensions
{
    public static string Language(this HttpCookieCollection cookies)
    {
        return cookies["Language"]?.Value
    }
}

Later in your application you can reuse it everywhere which would result in a nice short and clear code ba also getting rid of this ugly condition:

 if (cookie != null && cookie.Value != null)

Bug 1

else
{
    System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en");
    System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en");

}

There is a bug in this else. Both lines are the same. Did you copy/paste them?

Setting culture

Another case for encapsulation are the four lines where you set the culture. Just write a new method and put two of them there:

public static void SetCulture(string name)
{
    System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo(name);
    System.Threading.Thread.CurrentThread.CurrentUICulture = new System.Globalization.CultureInfo(name);
}

Default culture

Later you should also add a constant for the default cutlure

const string DefaultCulture = "en";

New event handler

Now put everything together and be happy with this pretty nice two-liner event handler:

protected void Application_BeginRequest(object sender, EventArgs e)
{
    var language = HttpContext.Current.Request.Cookies.Language() ?? DefaultCulture;
    SetCulture(language);
}

Object initializer

You can also shorten the ChangeLanguage method by using an object initializer. This means that you replace this three lines

HttpCookie cookie = new HttpCookie("Language");
cookie.Value = LanguageAbbrevation;
Response.Cookies.Add(cookie);

with simply this

Response.Cookies.Add(new HttpCookie("Language")
{
    Value = LanguageAbbrevation
});

Bug 2

There is one more bug in your application. When you check for the LanguageAbbrevation here you don't set it to any default value if it's null. Consequently setting the cookie to nothing. Why don't you use en here or skip setting the cookie by putting it inside the if?

public ActionResult ChangeLanguage(String LanguageAbbrevation)
{
  if (LanguageAbbrevation != null)
  {
      Thread.CurrentThread.CurrentCulture = CultureInfo.CreateSpecificCulture(LanguageAbbrevation);
      Thread.CurrentThread.CurrentUICulture = new CultureInfo(LanguageAbbrevation);

  }
  Response.Cookies.Add(new HttpCookie("Language")
  {
      Value = LanguageAbbrevation
  });
  return RedirectToAction("Index", "Home");

}


Service Locator with Lazy Loading in Swift I am experimenting with the ServiceLocator pattern. I'd like to support lazy loading of items.

protocol Resolver {
  func resolve<T> () -> T
}

protocol Register {
  func register<T>(instance: T)
  func register<T>(reference: @escaping () -> T)
}

final class LazyServiceLocator {

  enum ObjectRegistry {
    case instance(Any)
    case reference(() -> Any)

    func unwrap() -> Any {
      switch self {
      case let .instance(instance): return instance
      case let .reference(reference): return reference()
      }
    }
  }

  private lazy var store: Dictionary<ObjectIdentifier, ObjectRegistry> = [:]
}

extension LazyServiceLocator: Resolver {
  func resolve<T>() -> T {
    let key = ObjectIdentifier(type(of: T.self))
    if let item = store[key], let instance = item.unwrap() as? T {
      switch item {
      case .reference: register(instance: instance)
      default: break
      }
      return instance
    } else {
      preconditionFailure("Could not resolve service for \(type(of: T.self))")
    }
  }
}

extension LazyServiceLocator: Register {

  func register<T>(instance: T) {
    let key = ObjectIdentifier(type(of: T.self))
    store[key] = .instance(instance)
  }

  func register<T>(reference: @escaping () -> T) {
    let key = ObjectIdentifier(type(of: T.self))
    store[key] = .reference(reference)
  }
}

This can run with the following in a playground

let foo = LazyServiceLocator()

class Test {
  init() {
    print("Test")
  }
}

class OtherTest {
  init(foo: Test) {
    print("OtherTest")
  }
}

foo.register(instance: Test())
foo.register(reference: {
  return OtherTest(foo: foo.resolve())
})

let bar: Test = foo.resolve()
let boo: OtherTest = foo.resolve()

Commenting out let bar: Test = foo.resolve() still runs the print statement in it's init method, so I can see that works.

Commenting out let boo: OtherTest = foo.resolve() does not run the print statement, so I believe this also works.

I am very new to the pattern and Swift, so would appreciate some feedback on where this can be improved or what I have missed, being new to the language.

This is mostly good, but it can be improved.
You might want to constrain the Resolver and Register protocols to classes. Since you want to share instances this won’t work with structs.
protocol Register: class { ... }

Your store property doesn’t have to be lazy. Initializing an empty dictionary is cheap, so you can do that directly when your LazyServiceLocator is initialized.
The biggest issue I found is the ObjectIdentifier you use as the dictionary key. You don’t store the type of T (which would be T.self) but the type of the type of T - it’s metatype. I’m not quite sure if this can lead to problems, but it is unnecessary. Just use ObjectIdentifier(T.self).
The other thing you might want to consider is renaming your register(reference:) method to register(factory:). Calling something that creates an object reference is rather uncommon.
And finally you might want to consider adding an overload for resolve that takes the requested type as a parameter:
extension Resolver {
    func resolve<T>(_ type: T.Type) -> T {
        return resolve()
    }
}

With that you can write let x = resolve(Foo.self) instead of let x: Foo = resolve(). IMHO this is a bit more readable.


Scraping reviews from Google Play using JavaScript What I'm trying to do:

Get user input for Google Play App page.

e.g. https://play.google.com/store/apps/details?id=jp.scn.android
Scrape 100 reviews from Google Play App and organize them into an array.

My JavaScript function:

function test() {
    var urlAdd = document.getElementById('input').value;
    var urlEnglish = urlAdd + '&hl=en';

    var query = {
    url: urlEnglish,
    type: 'html',
    selector: '[class=review-body]',
    extract: 'text'
    },
    request;

    request = 'http://example.noodlejs.com/?q=' +
    encodeURIComponent(JSON.stringify(query)) +
    '&callback=?';

    jQuery.getJSON(request, function (data) {
    document.getElementById('output').innerHTML = '<pre>' +
    JSON.stringify(data, null, 4) + '</pre>';
    })
};

Problems:

This function feels bulky.
It only returns 20 results. My guess is that this has something to do with how the Google Play DOM retrieves reviews.

Questions:

How do I streamline/improve my scraper function?
How do I get 100 results or more?

Comments:

My apologies if this is a simple solution. I just started learning JavaScript piecemeal in February.

Use scraping as last resort. I suggest you find available APIs for that. It's more robust, and  easy to work with. One issue with scraping is that it fetches the static HTML generated by the url. You can't fetch what is loaded via JS. Although there are ways to do it, it's just adds too much complexity.

In terms of hacking the code, you could check out how Google Play loads the rest of the comments. It should be an AJAX call, check the network tab of your browser. You checkout that url, the response and modify it to your needs.

As for your script: You're using jQuery, use it all the way!

// Cache as well as put configurables here
var input = $('#input');
var output = $('#output');
var noodleUrl = 'http://example.noodlejs.com/?';

var query = {
    // You should check if the url ends with parameters. Otherwise, this fails.
    url: input.val() + '&hl=en',
    type: 'html',
    selector: '[class=review-body]',
    extract: 'text'
};

// $.param
var request = noodleUrl + $.param({
  q : JSON.stringify(query),
  callback : '?'
});

$.getJSON(request, function (data) {
    output.html('<pre>' + JSON.stringify(data, null, 4) + '</pre>');
}


Settings dialog, using information from its parent window My MainWindow popups a SettingsDialog. The setting dialog need to hide certain fields if the connected device is certain type.

void MainWindow::on_actionSettings_triggered()
{
    SettingsDialog * settings = new SettingsDialog(this);

    settings->exec();
}

Now in SettingsDialog:

SettingsDialog::SettingsDialog(QWidget *parent) :
    QDialog(parent),
    ui(new Ui::SettingsDialog)
{
    ui->setupUi(this);

    QSettings settings;

    MainWindow * mainWindow = (MainWindow *) parent;

    if ( mainWindow->deviceType == DEVICE_TYPE_B )
    {
        ui->comboBoxIP->setVisible( false );
    }
}

It works fine but is it a good way to access the info which is present in the parent window? or should the parent window pass in the device type in the constructor so it only knows the device type and work with it?

If the SettingsDialog can only take a MainWindow as a parent in the constructor then declare it to be so:

SettingsDialog::SettingsDialog(MainWindow *parent) :
    QDialog(parent),
    ui(new Ui::SettingsDialog)
{

As for getting the type indeed passing it in explicitly is better.

void MainWindow::on_actionSettings_triggered()
{
    SettingsDialog * settings = new SettingsDialog(this, deviceType);

    settings->exec();
}

My MainWindow popups a SettingsDialog. The setting dialog need to hide certain fields if the connected device is certain type.

void MainWindow::on_actionSettings_triggered()
{
    SettingsDialog * settings = new SettingsDialog(this);

    settings->exec();
}

Now in SettingsDialog:

SettingsDialog::SettingsDialog(MainWindow *parent, DeviceType deviceType) :
    QDialog(parent),
    ui(new Ui::SettingsDialog)
{
    ui->setupUi(this);

    QSettings settings;

    if (deviceType == DEVICE_TYPE_B )
    {
        ui->comboBoxIP->setVisible( false );
    }
}


Spring: Creating a Mutable Common Command Object or Controller Interceptor I'm integrating with a 3rd party vendor that has Users and Organizations in it. My tool is a user administration tool that allows us to store information in our local database about the Users and Organizations that we manage in the 3rd party vendor. So the Users and Organizations are stored in the 3rd party vendor as well as our database (we act as the middle man sort of). I'm at a crossroads with some ideas and would like to hear what others thought of the following problem and my solution.

Before I dive in, we're using Grails 2.4.4

One use case for the tool is creating a User. We create the user in the 3rd party vendor via an API call, and then we store information about that user in our database. There are many uses cases like this and there are 3 fields that are always in common between them, an API Token a Data Center ID and an Organization ID. These 3 fields are required for just about every API call we make to our 3rd party vendor and most of the Controller Actions result in an API call being made. For this reason, I had the idea to make a "Common" Command Object with these 3 fields on it that can be extended by another Command Object.

@Validateable
class CommonRequestCommand {

    String apiToken
    String dataCenterId
    String orgId

    static constraints = {

        apiToken nullable: true
        dataCenterId nullable: true
    }
}

@Validateable
class UserCreateCommand extends CommonRequestCommand {

    String email
    String firstName
    String lastName

}

There is one catch to this idea. The apiToken and dataCenterId are mutable (which I believe immutability is strongly suggested by Spring). It's possible that the apiToken and/or dataCenterId fields are supplied by the client/UI, or they might not be (orgId will always be supplied from the UI form). If they are not supplied, we query our database for them. If they do not exist in our database, then we throw an error. They almost always will NOT be supplied. To do that, I change the CommonRequestCommand to override the Getter methods and look up the API Token or Data Center ID if they are not provided

@Validateable
class CommonRequestCommand {

    private String apiToken
    private String dataCenterId
    String orgId

    public String getApiToken() {

        if(apiToken == null){
            Organization org = Organization.findById(orgId)
            if(org == null){
                throw new OrganizationException("Organization not found")
            }
            apiToken =  org.apiToken
        }
        return apiToken
    }

    public void setApiToken(String apiToken){
        this.apiToken = apiToken
    }

    public String getDatacenterId(){

        if(this.dataCenterId == null){
            Organization org = Organization.findById(orgId)
            if(org == null){
                throw new OrganizationException("Organization not found")
            }
            dataCenterId = org.dataCenterId
        }

        return dataCenterId
    }

    public void setDatacenterId(String dataCenterId){
        this.dataCenterId = dataCenterId
    }
}

My Question:
Do you think this is an appropriate design? I believe the biggest drawback to this is that the CommonRequestCommand is mutable.

Brainstorming a few other ways:

Drop the CommonRequestCommand and inheritance of command objects and instead create an Interceptor that creates a POGO CommonRequestObject and stores it in the request scope. Then in the controller, I pass both the UserCreateCommand object and the CommonRequestObject to the service layer.
Just pass the 3 fields through the params scope and don't worry about creating the CommonRequestCommand or an interceptor. Instead, every method in the service layer would have an additional 3 arguments for these fields.

I don't like the idea of modeling a common set of properties (or as you say "... for just about every API call..." probably a mostly common set of properties) as a superclass. IMO inheritance should be used to capture common business aspects, not common technical aspects. Or in other words, this feels somewhat like identifying a set of real world objects which have a lock, and then creating a HavingLock superclass with subclasses House, Car, Desk, ... - this simply does not sound right.

Then, the CommonRequestCommand has the ring of something that is a pure data holder. It has a set of parameters and maybe even a specific execution logic that is tied to the service you call. Tying this this to the lookup logic in your own application will make this a hard-to-test mess.

Thus, I agree that an immutable class will probably be the best, and furthermore recommend that you make that immutable class just a field in your commands. For the mutablility, you can always create a copy.

All in all:

put your parameters in a RequestParameters class, which is immutable and which does not contain business logic
for a request coming from the UI, check whether you have all parametes, look up the ones missing, and create such a RequestParametes object. This should be done in a business class in you application
After you created the RequestParameters object, create the concrete Command, passing the RequestParametes in.
Continue processing the command.


Trying to understand appropriate routing in MVC I am learning MVC, and trying to understand routing.

I understand that if I want to show an individual blog post for site.com/54, my route would be something like

//index.php
$controller = new Controller();
if ( preg_match("#/(0-9.)#", $uri, $matches) ) {
    $controller->showAction($matches[1]);
}

which would lead to my controller

//controllers.php
class Controller
{
    private function showAction($id) {
        $post = getPostById($id);
        $view = new View('views/show.php');
    }
}

And, on the other hand, a sensible thing to do for different static pages is perhaps

//index.php
...
} elseif ($uri == '/about') {
    $controller->aboutAction();
} elseif ($uri == '/contact') {
    $controller->contactAction();
} elseif ($uri == '/') {
    $controller->indexAction();
} else {
    $controller->missingAction();
}

My question is, what about the in-between? For example, apple.com/ipad/overview/ and apple.com/ipad/features/. They are different pages, so it seems like the latter is sensible (i.e. unique controller method for each page). But then, when you're on /overview, you still need to know you're a sub-page of /ipad (so you can highlight the iPad button in the navigation). If you did the first method (regex parsing), you'd know that (i.e. you could use $matches[1] when constructing your navigation). If you use the second method, it seems like in your view you'd have to do something like $current_product = 'ipad' so your nav would know about it. But this could get cumbersome.

What's the appropriate method?

Have you thought about calling the overview only when the URI ends in "overview" and preceded by a product slug?

$controller = new Controller();
if ( preg_match("#^/([a-zA-Z0-9_-]+)/overview/?$#", $uri, $matches) ) {
    $controller->showOverview($matches[1]);
}

This way, you define your routes with the following assumption:

/:product
/:product/specs
/:product/comments
/about

You should check out the Slim Framework: http://www.slimframework.com/

I've used it just for routing when performance was a crucial requirement.


Polling loop - Always a bad decision? I had a need to isolate some long-running blocking calls in a background thread of my app. I also needed to keep this thread running indefinitely, because COM would complain if some object I created in that thread were accessed from another thread. I then needed to control what these objects did from my main UI thread, in a guaranteed-FIFO manner.

The solution I came up with was kind of ActiveObject-reminiscent; a polling loop running as the DoWork handler of a BackgroundWorker, which accepted encapsulated Command objects representing the work to perform from a thread-safe ConcurrentQueue. Here's the vitals:

//basic implementation of the Command pattern; no serialization/persistence needed,
//just need to be able to encapsulate some work and defer it.
internal class Command
{
    private Action action;

    public Command(Action action)
    {
        this.action = action;
    }

    protected Command()
    {
    }

    public virtual void Execute()
    {
        action();
    }
}

//Generic variation accepts a single parameter
internal class Command<T>:Command
{
    private T param;

    private Action<T> action;

    public Command(Action<T> action, T param)
    {
        this.action = action;
        this.param = param;
    }

    public override void Execute()
    {
        action(param);
    }
}

...

//event handlers run in the UI thread will Enqueue() Command objects
//containing the delegates that should be run in the background thread
ConcurrentQueue<Command> queuedCommands = new ConcurrentQueue<Command>();

//The BGW DoWork handler; runs indefinitely until the UI that needs it is Dispose()d
private void MainBackgroundLoop(object sender, System.ComponentModel.DoWorkEventArgs e)
    {
        Command command;
        bool commandAvailable;

        do
        {
            commandAvailable = queuedCommands.TryDequeue(out command);
            if (commandAvailable)
                command.Execute();
            else
                Thread.Sleep(100); //<-- Here's your code smell
        } while (!e.Cancel);
    }

Now, this functions beautifully. But, the use of Thread.Sleep() in any SO/CR post usually gets called out as a code smell. I get why; this loop requires CPU to try to pull commands out of the queue at least 10 times a second, which will eat CPU for an "idle" thread. But, given there are other reasons why the thread has to keep running, this seems acceptable.

Thoughts?

You're right, most of the time, you shouldn't use polling like this. You should instead block the thread indefinitely if there is no work and wake it up when it's needed.

Fortunately, the same namespace that contains the ConcurrentQueue<T> you use also has the solution you need: BlockingCollection<T>. The collection has methods that will always return an item, and block if none are available, which is exactly what you need. Using that class, I would rewrite your code like this:

BlockingCollection<Command> queuedCommands = new BlockingCollection<Command>();

private void MainBackgroundLoop(object sender, DoWorkEventArgs e)
{
    do
    {
        Command command;
        bool commandAvailable = queuedCommands.TryTake(out command, Timeout.Infinite);
        if (commandAvailable)
            command.Execute();
    } while (commandAvailable);
}

Because the collection doesn't know about your DoWorkEventArgs, you have take care of ending the loop in some other way. In the code above, if you call queuedCommands.CompleteAdding(), it will make sure remaining items are processed and then it will shut down, because TryTake() will return false. Another option for cancellation is to use an overload of TryTake() that takes a CancellationToken and use that to cancel the operation.


Print all permutations with repetition of characters Given a string of length n, print all permutation of the given string.
  Repetition of characters is allowed. Print these permutations in
  lexicographically sorted order

Examples:

Input: AB

Ouput: All permutations of AB with repetition are:

  AA
  AB
  BA
  BB

Input: ABC

Output: All permutations of ABC with repetition are:

   AAA
   AAB
   AAC
   ABA
   ...
   ...
   CCB
   CCC

The following is my code:

void permutate(const string& s, int* index, int depth, int len, int& count)
{
    if(depth == len)
    {
        ++count;
        for(int i = 0; i < len; ++i)
        {
            cout << s[index[i]];
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < len; ++i)
    {
        index[depth] = i;
        permutate(s, index, depth+1, len, count);
    }
}

int main()
{
    string s("CBA");
    sort(s.begin(), s.end());
    cout << s << endl;
    cout << "**********" << endl;
    int len = s.size();
    int* index = new int[len];
    int count = 0;
    permutate(s, index, 0, len, count);
    cout << count << endl;

    system("pause");
    return 0;
}

In case you ever want to just display the string (if you have something like "AAA"):

// if a different character from the first is not found
// std::string::npos corresponds to "not found" (or -1)

if (s.find_first_not_of(s.front()) == std::string::npos)
{
    // inform user that only one permutation exists
}

This is a potential loss of data:

int len = s.size();

size() returns std::size_type, not int.  Do not use int for std::string or other STL container sizes.  They have their own size types that prevents this very issue.  This would be the proper initialization of len:

std::string::size_type len = s.size();

This is needless and potentially dangerous:

int* index = new int[len];

The "dangerous" part refers to the fact that delete is never used to free the allocated memory.  Always use delete with new where appropriate.

In order to free the memory properly, you would use delete in this way:

delete [] index;

But since you're utilizing the STL, instead consider an std::vector:

std::vector<int> index(s.size());

As the memory management is already properly done in std::vector's implementation, new/delete is not needed here at all.  Always try to avoid doing this manually in C++.
No need to pass the string's size; it's already part of the implementation.  Just use s.size().
With the utilization of the aforementioned std::vector and size(), you should now make depth and the loop counters of std::size_t.  This will avoid type-mismatch warnings from comparing size() with an int.  Make sure your compiler's warning flags are high.
Avoid using system("PAUSE") as it is platform-specific and can be imitated by better alternatives such as std::cin.get().  This will ask the user for a console input instead of a keystroke, but that difference shouldn't matter if it means maintaining portability.

Final code with applied changes (also tested on Ideone):

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

void permutate(const std::string& s, std::vector<int>& index, std::size_t depth, int& count)
{
    if (depth == s.size())
    {
        ++count;
        for (std::size_t i = 0; i < s.size(); ++i)
        {
            std::cout << s[index[i]];
        }
        std::cout << "\n";
        return;
    }

    for (std::size_t i = 0; i < s.size(); ++i)
    {
        index[depth] = i;
        permutate(s, index, depth+1, count);
    }
}

int main()
{
    std::string s("CBA");

    if (s.find_first_not_of(s.front()) == std::string::npos)
    {
        std::cout << "Only 1 permutation exists";
        return 0;
    }

    std::sort(s.begin(), s.end());

    std::cout << s << "\n**********\n";

    std::vector<int> index(s.size());
    int count = 0;

    permutate(s, index, 0, count);

    std::cout << "\nTotal permutations with repetitions: " << count;
}


Count how many times values has appeared in list so far I have a list of non-unique values. I want to output a list of the same length where each value corresponds to how many times that value has appeared so far.

The code I have written to do this seems over-complicated, so I think there has to be a better way.

x = [1,1,2,3,1,3]

def times_so_far(ls):

    out = [0]*len(x)
    counted = {}
    for i,v in enumerate(x):
        if v in counted:
            counted[v] += 1
        else:
            counted[v] = 0

        out[i] = counted[v]
    return out

times_so_far(x)
#[0, 1, 0, 0, 2, 1]

You can use a defaultdict, to remove the if v else.
To achieve this, you can do:

from collections import defaultdict
counted = defaultdict(int)
for i,v in enumerate(x):
    counted[v] += 1

To remove the need for out and enumerate you can yield on each iteration.
This would make your code very small and readable.

from collections import defaultdict

def times_so_far(list_):
    counted = defaultdict(int)
    for v in list_:
        counted[v] += 1
        yield counted[v]

print(list(times_so_far([1,1,2,3,1,3])))
#[0, 1, 0, 0, 2, 1]

It will return a generator object, hence why I use list.
If this is a problem then you can change yield to out.append() and re-add out.

This has \$O(n)\$ runtime, with a min \$O(n)\$ and maximum \$O(2n)\$ memory usage.


Count how many times a value is greater than or equal to the median of previous D elements I am self-studying algorithms and data structures. So, bear with me if the code I've written isn't stellar or interpretation is accurate.

Essentially, the problem (which I took from HackerRank) requires counting the number of times an element in an array is greater than or equal to two times the median of the subarray containing the past D elements.

For instance, suppose you have an array of [2,3,4,2,3,6,8,4,5]. And, the window is D = 5.

Starting value to compare against the median of the subarray is 6. So, you
look at the median of the subarray, [2,3,4,2,3], which is 3. Then, you multiply the median by 2, which is 6, and since the 2 x median value satisfies the condition, you would increment a counter by 1. You continue this procedure all the way to the last element of the array.

So, here's the code I have written thus far:

import sys

def activityNotifications(expenditure, d):
    """ Worst-case: O( n^2 * logn ) """
    num_of_trans = len(expenditure) - 1
    count = 0
    for i in range(d,num_of_trans):
        prev_trans = sorted(expenditure[i-d:i])
        if d % 2 == 0:
            left_i = (d - 1) // 2
            right_i = left_i + 1
            median = prev_trans[left_i] + prev_trans[right_i]
        else:
            median = prev_trans[d - 1]
        if expenditure[i] >= median:
            count += 1
    return count

if __name__ == "__main__":

    expenditures = [[2,3,4,2,3,6,8,4,5],[1,2,3,4,4]]
    d = 4

    for record in expenditures:
        result = activityNotifications(record, d)
        print(result)

The approach works, but I am afraid that the code is poorly optimized. If my understanding of asymptotic complexity of this algorithm is correct, I believe it's \$O(n ^ 2 * log(n))\$. Is there any way I can reduce the complexity down to \$O(n)\$ or even better \$O(log(n))\$?

** Update (01/11/18) **

Based on Austin Hasting's suggestion, I revised my code to utilize bisect functions to avoid sorting at every new window. Essentially, the first window is sorted. Then, after the median of the sorted array is computed, bisect finds the position of the leftmost element of the window in the sorted array. Based on the position, the element within the sorted array is deleted. Finally, the next element is added onto the sorted array using bisect once again. Based on the procedure I have outlined, here's my new code:

def median(a, d):
    if (d % 2) != 0:
        return a[d // 2]
    else:
        half = d // 2
        return (a[half] + a[half - 1]) / 2

def activityNotifications_bisect(expenditure, d):
    """ Worst-case: O( n ) """

    frauds = 0
    window = sorted(expenditure[:d])
    for p, i in enumerate(expenditure[d:]):
        if i >= median(window, d) * 2:
            frauds += 1
        del window[bisect_left(window, expenditure[p])]
        insort_left(window, i)
    return frauds

Theoretically speaking, the code appears to be an improvement. However, when I tested the performance of my old code versus the new using timeit with 1 million executions, I was surprised to see that the old code completing at 5.35 seconds beats the new one by 2.1 seconds. I am perplexed about what's preventing my new code from performing better than the old one. Any additional tips would be incredibly helpful!

You are almost correct.

I believe you are interpreting the performance as \$O(n²*logn)\$ because you are looping over (most of) the items in the input array (length = n) and you are using a sort to compute your median.

However, sorted's performance is actually determined by the size of the window parameter, D, which is a constant, and its log is a constant, too! So your performance is technically \$O(n*DlogD)\$, which is \$O(n × C)\$ which is \$O(n)\$.

But you can do better!

Assume for a moment that you have the window sorted. You now receive a sequence of pairs (a, z) where value a is to be removed from the window and value z inserted. Once this is done, you will need to recompute the median.

Also, you have two cases: one where the window size D is an odd number and thus the median is one of the values in the window; and the other case where the window size is an even number and the median must be computed as the mean of the central values.

I think that if you separate your code into two functions at the top level - one for even windows, one for odd windows, you can write code that updates the sorted window without having to invoke the sorted function each time through. Thus, instead of D log D you can perform one removal and one insert in a single pass, having time proportional to D.

You'll still pass over nearly all the items in the list, so your time will still be \$O(n)\$, but it won't be times quite so large a constant.

Edit for @hjpotter92:

You are traversing an unsorted sequence of numbers, using a sliding window:

 D = 4
 [a, b, c, d,] e, f, g, h
 a, [b, c, d, e,] f, g, h
 a, b, [c, d, e, f,] g, h

Each time you advance, your window adds one number (I called it z) on the right side, and loses one number (I called it a) from the left side. So instead of pretending that each window is a whole new bunch of numbers that have to be put into order, using sort, you can write your code to remove one number, insert one number, and then recompute the median.

In some cases (D is odd), the median is just window[D//2]. In other cases (D is even), the median is (window[D//2-1] + window[D//2]) / 2. This is because of how the median is computed. You can see OP doing this computation in the original code. However, there's no reason to keep checking D for odd/even, since it never changes in the function. Instead, it's better to split the function at the top level, and proceed from there:

def func(sequence, d):
    if d % 2 == 0:  # D is even
        # code for scanning with even window size
    else:  # D is odd
        # code for scanning with odd window size

Edit 2: Comprehensive performance test

I made some changes to your code to test various performance enhancements. Here is one set of results run on my 2011 MacBook Pro (numbers are seconds, lower is better):

$ python -V
Python 3.5.4

$ python test.py

With n=10 inputs, d=4
    replsort             0.925
    replsort2            1.063
    linsert              1.549
    insbisect            1.102
    noparity             0.965
    orig                 1.129

With n=1000 inputs, d=4
    replsort             3.945
    replsort2            4.268
    linsert              5.210
    insbisect            4.280
    noparity             4.431
    orig                 5.324

With n=1000 inputs, d=50
    replsort             7.384
    replsort2            7.156
    linsert              8.763
    insbisect            4.736
    noparity             10.172
    orig                 10.854

With n=1000 inputs, d=500
    replsort             10.447
    replsort2            10.590
    linsert              8.184
    insbisect            6.641
    noparity             50.901
    orig                 49.458

The orig function is your code. The noparity function is your code with the parity check hoisted to the top. The replsort functions maintain the window by replacing the a value with the z value (as discussed above) and then sorting the window. The linsert and insbisect functions work by doing a linear scan of the window, or by calling bisect.insort_left, respectively, to get the z value in place.

Important: your example is bad. You've got a short list of input numbers, with a small window size. That means the "fixed costs" will tend to dominate your performance.

What does that mean? It means that things like calling the function, initializing count = 0, setting up and tearing down the for loop, and executing the return statement will make a difference.

It also means that the difference between \$O(n)\$ and \$O(log\ n)\$ and \$O(n\ log\ n)\$ don't seem to matter.

But when I switched to generating 1000 random numbers, instead of 10 fixed numbers, things changed! Notice the linsert function goes from being 50% slower, to being something like 25% slower when n=1000. Also, notice that all the other functions beat noparity. I believe this is because noparity always recomputes the entire slice before sorting it. That computation got added in 990 more times (for d=4) and it started to be a drag on the performance.

Finally, I started increasing the window size. This is where the magic really happens, because this affects the performance of the sort, the bisect, the window search and removes. Essentially, this is the number that really determines the differences in performance. For a small window size, again the upfront costs of calling sorted or remove or bisect are dominating. But when the window size goes up, suddenly the differences in algorithmic efficiency start to matter.

And look what happens with d=500. First, realize that setting d=500 means the code only does half the work! Because the input of 1000 minus a 500 window size leaves 500 checks to run, rather than 996 (d=4) or 950 (d=50). But when that change is made, suddenly linsert (which is \$O(d)\$) and insbisect (which is \$O(log\ d)\$) outperform everybody. Because "setup costs" and "written in C" no longer cover up \$O(d\ log\ d)\$!

# test.py
import bisect

def orig(expenditure, d):
    """ Worst-case: O( n^2 * logn ) """
    num_of_trans = len(expenditure) - 1
    count = 0
    for i in range(d, num_of_trans):
        prev_trans = sorted(expenditure[i - d:i])
        if d % 2 == 0:
            left_i = (d - 1) // 2
            right_i = left_i + 1
            median = prev_trans[left_i] + prev_trans[right_i]
        else:
            median = prev_trans[d - 1]
        if expenditure[i] >= median:
            count += 1

    return count

def noparity(expenditure, d):
    """Hoist parity check out of loop"""

    num_of_trans = len(expenditure) - 1
    count = 0
    left_i = (d - 1) // 2
    right_i = left_i + 1

    if d % 2 == 0:
        for i in range(d, num_of_trans):
            prev_trans = sorted(expenditure[i - d:i])
            median_x2 = prev_trans[left_i] + prev_trans[right_i]
            if expenditure[i] >= median_x2:
                count += 1
    else:
        for i in range(d, num_of_trans):
            prev_trans = sorted(expenditure[i - d:i])
            median_x2 = prev_trans[d // 2] * 2
            if expenditure[i] >= median_x2:
                count += 1

    return count

def linsert(expenditure, d):
    """Hoisted median, using linear insertion instead of sort"""

    count = 0
    len_exp = len(expenditure)
    window = sorted(expenditure[:d])
    winremove = window.remove
    winsert = window.insert
    winappend = window.append

    if d % 2 == 0:
        m1 = d // 2
        m0 = m1 - 1
        ai = 0
        for zi in range(d, len_exp):
            median_x2 = window[m0] + window[m1]
            a, z = expenditure[ai], expenditure[zi]
            ai += 1

            if z >= median_x2:
                count += 1

            winremove(a)
            for i in range(d-1):    # d-1 because .remove
                if window[i] <= z:
                    winsert(i, z)
                    break
            else:
                winappend(z)

    else:
        raise NotImplementedError("I haven't written this code.")

    return count

def insbisect(expenditure, d):
    """Hoisted median, using bisect for insertion."""

    count = 0
    len_exp = len(expenditure)
    window = sorted(expenditure[:d])
    winremove = window.remove

    if d % 2 == 0:
        m1 = d // 2
        m0 = m1 - 1
        ai = 0
        for zi in range(d, len_exp):
            median_x2 = window[m0] + window[m1]
            a, z = expenditure[ai], expenditure[zi]
            ai += 1

            if z >= median_x2:
                count += 1

            winremove(a)
            bisect.insort_left(window, z)

    else:
        raise NotImplementedError("I haven't written this code.")

    return count

def replsort(expenditure, d):
    """Hoisted median, using replacement via index, then sort."""

    count = 0

    window = sorted(expenditure[:d])
    windex = window.index
    winsort = window.sort

    if d % 2 == 0:
        m1 = d // 2
        m0 = m1 - 1

        for a, z in zip(expenditure, expenditure[d:]):
            median_x2 = window[m0] + window[m1]
            if z >= median_x2:
                count += 1

            # Note: do not write `window =` anywhere, or you invalidate
            # windex and winsort.
            window[windex(a)] = z
            winsort()
    else:
        raise NotImplementedError("I haven't written this code.")

    return count

def replsort2(expenditure, d):
    """Hoisted median, using replacement via index, then sort."""

    count = 0

    len_exp = len(expenditure)
    window = sorted(expenditure[:d])
    windex = window.index
    winsort = window.sort

    if d % 2 == 0:

        m1 = d // 2
        m0 = m1 - 1
        ai = 0

        for zi in range(d, len_exp):
            median_x2 = window[m0] + window[m1]
            a, z = expenditure[ai], expenditure[zi]
            ai += 1

            if z >= median_x2:
                count += 1

            # Note: do not write `window =` anywhere, or you invalidate
            # windex and winsort.
            window[windex(a)] = z
            winsort()
    else:
        raise NotImplementedError("I haven't written this code.")

    return count

if __name__ == "__main__":
    from timeit import timeit
    from random import randrange as rr

    results =[line.strip().split() for line in """
replsort   9.730
replsort2  11.538
linsert    17.954
insbisect  10.970
noparity   10.574
orig 11.801
""".splitlines() if line.strip()]

    print("\nWith n=10 inputs, d=4")
    for funcname, time_for_me in results:
        print("    {:20s} {:5.3f}".format(funcname,
            timeit('{}([2,3,4,2,3,6,8,4,5], 4)'.format(funcname),
                setup='from __main__ import {}'.format(funcname),
                number=100000)))

    print("\nWith n=1000 inputs, d=4")

    for funcname, time_for_me in results:
        print("    {:20s} {:5.3f}".format(funcname,
            timeit('{}([rr(1, 16) for _ in range(1000)], 4)'.format(funcname),
                setup='from __main__ import rr, {}'.format(funcname),
                number=1000)))

    print("\nWith n=1000 inputs, d=50")

    for funcname, time_for_me in results:
        print("    {:20s} {:5.3f}".format(funcname,
            timeit('{}([rr(1, 16) for _ in range(1000)], 50)'.format(funcname),
                setup='from __main__ import rr, {}'.format(funcname),
                number=1000)))


Letter combinations of phone dial pad number In preparation for interviews, I have written a solution to this question:

  Given a sequence of numbers (34128) and an input map such   as a dial
  pad on a phone (2->[a,b,c], 3->[d,e,f], 4->[g,h,i]) write an algorithm
  to return all possible words from the sequence. E.g. Input: 232
  Output: [ada, adb, adc, aea, aeb, aec, afa, afb, afc, bda, bdb, bdc,
  bea, beb, bec, bfa, bfb, bfc, cda, cdb, cdc, cea, ceb, cec, cfa, cfb,
  cfc]

  Also what will happen if this would have been a 12 digit international
  number? How would that effect your design.

Below is the solution I have:

public class DialPad {

    public static void main(String[] args) {
        System.out.println(letterCombinations("232"));
    }

    public static ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preres = new ArrayList<String>();
        res.add("");

        for (int i = 0; i < digits.length(); i++) {
            for (String str : res) {
                String letters = map.get(digits.charAt(i));
                for (int j = 0; j < letters.length(); j++)
                    preres.add(str + letters.charAt(j));
            }
            res = preres;
            preres = new ArrayList<String>();
        }
        return res;
    }

    static final HashMap<Character, String> map = new HashMap<Character, String>() {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };
}

Is there any improvement I can make here? It looks to me like complexity is high in this code. How can I simplify this code better?

Putting the members of this class in the reverse order (map, then letterCombinations(), then main()) would be more customary.  The map should be private unless you have a good reason to do otherwise.  I would also avoid creating an anonymous subclass of HashMap, and initialize it this way:

private static final HashMap<Character, String> map = new HashMap<>(8);
static {
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
};

It would be more obvious that preres is a temporary variable if you scoped it properly.  Both res and preres could be named better — I've chosen results and nextResults, respectively.

Whenever possible, you should specify the initial capacity of an ArrayList.  The penalty for underestimating can be rather severe, as it requires reallocating and copying existing results.

digits.charAt(i) is a loop invariant that can be moved from the middle loop into the outer one.

All loops should have braces.  Omitting them is bad practice and will cause maintenance-induced bugs.

public static List<String> letterCombinations(String digits) {
    List<String> results = new ArrayList<String>();
    results.add("");

    for (int i = 0; i < digits.length(); i++) {
        String letters = map.get(digits.charAt(i));
        List<String> nextResults = new ArrayList<>(letters.length() * results.size());
        for (String str : results) {
            for (int j = 0; j < letters.length(); j++) {
                nextResults.add(str + letters.charAt(j));
            }
        }
        results = nextResults;
    }
    return results;
}

It's generally better to return List<String> rather than ArrayList<String>, to give you flexibility to change the implementation.  For example, here is a solution that uses just one LinkedList.

public static List<String> letterCombinations(String digits) {
    LinkedList<String> results = new LinkedList<>();
    results.add("");

    for (int i = 0; i < digits.length(); i++) {
        String letters = map.get(digits.charAt(i));
        for (int j = results.size(); j > 0; j--) {
            String intermediateResult = results.poll();
            for (int k = 0; k < letters.length(); k++) {
                results.add(intermediateResult + letters.charAt(k));
            }
        }
    }
    return results;
}


Recursive Matrix Multiplication Algorithm Can I improve on this any further. Is there a prettier way of passing the array sizes?
#include <stdio.h>

void matrix_addition(size_t n, int A[n][n], int B[n][n], int C[2*n][2*n], size_t c_start, size_t c_end) {
    for(size_t i = 0; i < n; ++i) {
        for(size_t j = 0; j < n; ++j) {
            C[i+c_start][j+c_end] = A[i][j] + B[i][j];
        }
    }
}

void recursive_matrix_multiply(
        size_t l, size_t n, int A[l][l], int B[l][l], int C[n][n],
        size_t a_r_start, size_t a_r_end, size_t a_c_start, size_t a_c_end,
        size_t b_r_start, size_t b_r_end, size_t b_c_start, size_t b_c_end
    ) {
    if(n == 1) {
        C[0][0] = A[a_r_start][a_c_start]*B[b_r_start][b_c_start];
    } else {
        int m = n/2;
        int C1[m][m];
        int C2[m][m];

        recursive_matrix_multiply(l, m, A, B, C1, a_r_start, a_r_end-m, a_c_start, a_c_end-m, b_r_start, b_r_end-m, b_c_start, b_c_end-m);
        recursive_matrix_multiply(l, m, A, B, C2, a_r_start, a_r_end-m, a_c_start+m, a_c_end, b_r_start+m, b_r_end, b_c_start, b_c_end-m);

        matrix_addition(m, C1, C2, C, 0, 0);

        recursive_matrix_multiply(l, m, A, B, C1, a_r_start, a_r_end-m, a_c_start, a_c_end-m, b_r_start, b_r_end-m, b_c_start+m, b_c_end);
        recursive_matrix_multiply(l, m, A, B, C2, a_r_start, a_r_end-m, a_c_start+m, a_c_end, b_r_start+m, b_r_end, b_c_start+m, b_c_end);

        matrix_addition(m, C1, C2, C, 0, m);

        recursive_matrix_multiply(l, m, A, B, C1, a_r_start+m, a_r_end, a_c_start, a_c_end-m, b_r_start, b_r_end-m, b_c_start, b_c_end-m);
        recursive_matrix_multiply(l, m, A, B, C2, a_r_start+m, a_r_end, a_c_start+m, a_c_end, b_r_start+m, b_r_end, b_c_start, b_c_end-m);

        matrix_addition(m, C1, C2, C, m, 0);

        recursive_matrix_multiply(l, m, A, B, C1, a_r_start+m, a_r_end, a_c_start, a_c_end-m, b_r_start, b_r_end-m, b_c_start+m, b_c_end);
        recursive_matrix_multiply(l, m, A, B, C2, a_r_start+m, a_r_end, a_c_start+m, a_c_end, b_r_start+m, b_r_end, b_c_start+m, b_c_end);

        matrix_addition(m, C1, C2, C, m, m);
    }
}

int main()
{
    int A[4][4] = {{1, 2, 3, 4}, {4, 3, 2, 1}, { 0, 0, 1, 1 }, {1, 1, 0, 0}};
    int B[4][4] = {{2, 2, 4, 4}, {4, 1, 1, 4}, {1, 0, 1, 0}, {1, 0, 1, 0}};
    int C[4][4];

    recursive_matrix_multiply(4, 4, A, B, C, 0, 3, 0, 3, 0, 3, 0, 3);

    for(size_t i = 0; i < 4; ++i) {
        for(size_t j = 0; j < 4; ++j) {
            printf("C[%i][%i] = %i, ", i, j, C[i][j]);
        }
        printf("\n");
    }

    return 0;
}

It currently works as intended but I'm looking to beautify this a bit. Even an improvement on variable naming would be appreciated. I'm trying to build up a portfolio so if you saw this from a professional standpoint what would you think?

All of the endpoints are redundant. If anyone can add anything else I'd still appreciate it.
#include <stdio.h>

void matrix_addition_partition(size_t n, size_t m, int A[m][m], int B[m][m], int C[n][n], size_t start, size_t end) {
    for(size_t i = 0; i < m; ++i) {
        for(size_t j = 0; j < m; ++j) {
            C[i+start][j+end] = A[i][j] + B[i][j];
        }
    }
}

void recursive_matrix_multiply(
        size_t l, size_t n, int A[l][l], int B[l][l], int C[n][n],
        size_t ar, size_t ac, size_t br, size_t cb
    ) {
    if(n == 1) {
        C[0][0] = A[ar][ac]*B[br][cb];
    } else {
        int m = n>>1;
        int C1[m][m], C2[m][m];

        recursive_matrix_multiply(l, m, A, B, C1, ar, ac, br, cb);
        recursive_matrix_multiply(l, m, A, B, C2, ar, ac+m, br+m, cb);

        matrix_addition_partition(n, m, C1, C2, C, 0, 0);

        recursive_matrix_multiply(l, m, A, B, C1, ar, ac, br, cb+m);
        recursive_matrix_multiply(l, m, A, B, C2, ar, ac+m, br+m, cb+m);

        matrix_addition_partition(n, m, C1, C2, C, 0, m);

        recursive_matrix_multiply(l, m, A, B, C1, ar+m, ac, br, cb);
        recursive_matrix_multiply(l, m, A, B, C2, ar+m, ac+m, br+m, cb);

        matrix_addition_partition(n, m, C1, C2, C, m, 0);

        recursive_matrix_multiply(l, m, A, B, C1, ar+m, ac, br, cb+m);
        recursive_matrix_multiply(l, m, A, B, C2, ar+m, ac+m, br+m, cb+m);

        matrix_addition_partition(n, m, C1, C2, C, m, m);

    }
}

void matrix_multiply(size_t n, int A[n][n], int B[n][n], int C[n][n]) {
    recursive_matrix_multiply(n, n, A, B, C, 0, 0, 0, 0);
}

int main()
{
    int A[4][4] = {{1, 2, 3, 4}, {4, 3, 2, 1}, {0, 0, 1, 1}, {1, 1, 0, 0}};
    int B[4][4] = {{2, 2, 4, 4}, {4, 1, 1, 4}, {1, 0, 1, 0}, {1, 0, 1, 0}};
    int C[4][4];

    matrix_multiply(4, A, B, C);

    for(size_t i = 0; i < 4; ++i) {
        for(size_t j = 0; j < 4; ++j) {
            printf("C[%i][%i] = %i, ", i, j, C[i][j]);
        }
        printf("\n");
    }

    return 0;
}


Selection sort algorithm in Swift I have written selection sort in Swift.

Sort([2,4,23,268,9,0]).bySelection()

I am looking for ways to further improve this programme using Swift language features.

struct Sort {

        private var elements:[Int]

        init(_ unsortedElems: [Int]) {
            self.elements = unsortedElems
        }

        func bySelection() -> [Int] {
            return selectionSortAlgo(input: elements)
        }

      }

  typealias SelectionSort = Sort
  extension SelectionSort {

    fileprivate func selectionSortAlgo(input:[Int]) ->[Int] {
        var elements = input
        let size = input.count

        for (index, item) in elements.enumerated() {
            var minimumIndex = index

            for subindex in  (index+1)..<size {
                if elements[subindex] < elements[minimumIndex] {
                    minimumIndex = subindex
                }
            }

            if minimumIndex != index {
                elements[index] = elements[minimumIndex]
                elements[minimumIndex] = item
            }
        }
        return elements
    }
}

I'll review this in two steps: first the body of selectionSortAlgo and then the higher level structure/architecture.

The selection sort implementation

Swapping elements

First of all, there is a bug (the only one I could find) in the code that swaps two elements that sometimes loses elements while swapping them. The smallest example where I can reproduce this is by sorting [1, 0, 0] which results in [0, 0, 0], losing the 1.

Looking at this code:

if minimumIndex != index {
    elements[index] = elements[minimumIndex]
    elements[minimumIndex] = item
}

I see that you're reading the item from the array as you're enumerating it and writing that at the minimumIndex, presumably to avoid having to get a tempItem to swap the two elements:

if minimumIndex != index {
    let tempItem = elements[index]
    elements[index] = elements[minimumIndex]
    elements[minimumIndex] = tempItem
}

The problem is that — because of array's value semantics — this doesn't account for changes that happen to the array since you started enumerating it. In short, you're swapping in a stale value from before you started sorting the array.

Now, what you're really doing here is swapping the elements at two indices, and that is best done with swapAt(_:_:). It's also documented to have no effect if the two indices are the same, so you can get rid of the surrounding if-statment:

elements.swapAt(minimumIndex, index)

If you're following along step-by-step you'll notice that the item of the enumerated array is now unused, so you can change it to only loop over the indices:

for index in elements.indices { ... }

Finding the index of the smallest element

I'll make two small syntactical changes to the code that finds the minimumIndex, partly to leverage Swift features but also to prepare the code to be generic (which I'll discuss later).

First, I'd like to describe what this loop is doing as "iterating through the indices of the slice of elements starting from the current index". In code I'd translate that into:

for subIndex in elements[index...].indices { ... }

Other than the minor syntactical difference, this means that the type of subIndex is an associated type of the collection being enumerated. This has no benefit for arrays, but will be important if you want to be able to sort other collections.

Secondly, since the loop body is only executed when the element at that subIndex is smaller than the element at the current minimumIndex I would possibly move the inner if-statement to a where clause:

var minimumIndex = index
for subIndex in elements[index...].indices where elements[subIndex] < elements[minimumIndex] {
    minimumIndex = subIndex
}

This change is only syntactical.

Going even further

Realistically I would probably stop here, but I'm going to continue to show more of this process and other implementations.

Considering the goal of that loop, what it's really doing it "finding the index of the minimum element in the rest of the elements".

There is two ways we can approach this goal. The first approach is by first finding the minimum element, and then finding the index of that element:

// The slice will never be empty, so it will always have a smallest element
let minimumElement = elements[index...].min()!
// This is one of the elements, so it will always have an index
let minimumIndex = elements[index...].index(of: minimumElement)!

In both of these lines it's safe to force-unwrap the results because:

the array slice will never be empty, so there will always be "some" smallest element
the smallest element comes from elements, so it will always have an index.

This alternative works, if it's a style that you prefer. However, it's iterating the slice twice; once to find the element and once to find the index.

To address that I'll use a zip to iterate over both the elements and the indices at the same time and find the minimum element-index-pair by comparing the elements. Since only the minimum index is needed to swap the elements I'll use tuple destructuring to only reference the minimumIndex once it's found.

// The slice will never be empty, so it will always have a smallest element
let (_, minimumIndex) = zip(elements[index...], index...).min(by: { $0.0 < $1.0 })!

For the same reason as before, it's safe to force-unwrap here. The slice will never be empty.

Higher level structure/architecture

At a high level there are two limitations to the Sort struct and its underlying implementations:

It can only compare Int elements
It can only sort arrays.

The first is pretty straightforward to address, by making the struct generic over an Element type that is constrained to be Comparable and by using arrays of that Element type:

struct Sort<Element: Comparable> {
    private var elements : [Element]
    ...
}

The second one is a bit trickier and highlights some constraints in how Sort can be extended to support other sorting algorithms. To make Sort support any kind of collection, it would be natural to also make it generic over a Collection type that is a Swift collection:

struct Sort<Collection: Swift.Collection, Element: Comparable>
       where Collection.Element == Element {
    private var unsortedElements : Collection
}

However, with this change the selection sort algorithm can no longer be used because swapAt(_:_:) is a method of MutableCollection rather than Collection. It's possible to constrain the Sort Collection to be a mutable collection, but what if another algorithm has another requirement? With this strategy we would end up constraining Sort more and more to the sum of all the different algorithms requirements.

A better alternative is to keep Sort as broad as possible, but to supply no sorting algorithms by default. Instead each sorting algorithm would be added as an extension only where the generic placeholder types satisfy those requirements:

extension Sort where Collection: MutableCollection {
    func bySelection() -> Collection {
        var elements = unsortedElements
        for index in elements.indices {
            let slice = elements[index...]
            let (_, minIndex) = zip(slice, slice.indices)
                                .min(by: { $0.0 < $1.0 })! // The slice will never be empty, so it will always have a smallest element
            elements.swapAt(minIndex, index)
        }
        return elements
    }
}

This change was greatly simplified because I had already moved away from the assumption of Int indices and instead got the index type from the collections associated Index type (implicitly). In other words, here minIndex is of the type Collection.Index rather than Int.

With this strategy each sorting algorithm can be added separately with the type constraints it needs, and a user of this API would have access to only the sorting algorithms that are available for the type of collection they are using.

At this point I don't see any value in the wrapping Sort struct, since these algorithm could be added as extensions to the collection itself in the same way. This solutions also has a more convenient and more "swifty" call site syntax

[2, 4, 23, 268, 9, 0].selectionSorted()

In the end, this is probably the solution that I'd end up with (without the Sort struct):

extension MutableCollection where Element: Comparable {
    func selectionSorted() -> Self {
        var elements = self
        for index in indices {
            let slice = elements[index...]
            let (_, minIndex) = zip(slice, slice.indices)
                                .min(by: { $0.0 < $1.0 })! // The slice will never be empty, so it will always have a smallest element
            elements.swapAt(minIndex, index)
        }
        return elements
    }
}

It's flexible in that it works with any mutable collection of any comparable element type. It's convenient in that it will show up immediately on the collection types where it's supported. I also feel that it's "swifty" in its style and conventions – both in its implementation and at its call site.


Outputting the Manufacturer ID of a processor using CPUID with inline ASM This outputs the manufacturer string associated with your CPU using the CPUID instruction. I wrote this up for a homework assignment, then found out that I didn't need to.

When run on my (virtual) machine, I get the following output:

EAX: 16
EBX: 756e6547
ECX: 6c65746e
EDX: 49656e69

GenuineIntel

What I'd like commented on:

I'm not super-proficient yet in bit manipulation. Originally, print_register had a for loop that iterated the mask directly, like

for (int32_t mask = 0xFF;; mask <<= 8) {

This worked until I realized that I needed to right-shift the result of the bitwise AND, and couldn't figure out how to get the bits shifted from the mask. I ended up going for a less efficient solution of iterating bit-counts and creating the mask each iteration. This feels like a naïve approach though.
Anything else notable. I'm starting to venture into increasingly unknown territory here, so anything would help.

Note that although inline asm seems to be considered bad practice to use in many cases, using it was the point of the exercise here. I know wrapper macros exist that would clean this up a bit.

#include <stdio.h>
#include <stdint.h>

void print_register(int32_t reg_value) {
    for (int shifted = 0; shifted < 0x20; shifted += 8) {
        int32_t mask = 0xFF << shifted;
        int32_t matched = (reg_value & mask) >> shifted;
        printf("%c", matched);
    }
}

int main() {
    int32_t out_eax = -1;
    int32_t out_ebx = -1;
    int32_t out_ecx = -1;
    int32_t out_edx = -1;

    int32_t leaf = 0;

    asm volatile ("cpuid"
                  :  "=a"(out_eax),  // 0
                     "=b"(out_ebx),
                     "=c"(out_ecx),
                     "=d"(out_edx)
                  :  "0"(leaf));

    printf("EAX: %x\nEBX: %x\nECX: %x\nEDX: %x\n\n",
           out_eax, out_ebx, out_ecx, out_edx);

    print_register(out_ebx);
    print_register(out_edx);
    print_register(out_ecx);

    printf("\n");
}

Use uint32_t

You have to be careful with shift operations on signed integers. In particular, right shifts on signed integers have implementation-defined behaviour, so it is hard to write portable code for it. It might work out in this case, but it is better to treat the values as unsigned integers here.

Bit shifting

While you have written a correct function to print the individual bytes of a 32-bit integer, it is a bit overkill. You can write it like so:

void print_register(uint32_t value) {
    printf("%c%c%c%c",
           (int)value,
           (int)(value >> 8),
           (int)(value >> 16),
           (int)(value >> 24));
}

This uses the fact that when printing a character, the value will already by truncated to 8 bits as if you would have written value & 0xFF, (value >> 8) & 0xFF, and so on. The cast to int might be necessary because the %c conversion expects an int, but int32_t might have a different size than an int on some platforms (for example, on an Arduino with an AVR CPU, int will be 16 bits).


Optimizing regex alternation, ability to view which choice matched? So I've got a regular expression parsing tcp responses from a music daemon. In case responses pile up I've come up with an expression to separate full responses from the data, however I'd like to also reference which choice was matched. Using capturing groups results in different numbers for each group, so is there a way to reference which alternation choice was matched besides that?

var patt = /((volume):\s\d+\n(.+\n)+?OK\n|OK\s(MPD)\s\d+\.\d+\.\d+|(OK)|(ACK).+\n)/;

This will match it, but I want to do different things with the separated response based on which match it was. I'd like to just have a switch case reference a single variable, but the only way I can think of to is:

var mycase = null;
var result = patt.exec(data);
if (result[2] == "volume")
    mycase= "volume";
else if (result[4] == "MPD")
    mycase= "MPD";
else if (result[5] == "OK")
    mycase= "OK";
else if (result[6] == "ACK")
    mycase= "ACK";

Is there a better way to do this?

First of all you can use non capturing groups to simplify the indices

var patt = /(?:(volume):\s\d+\n(?:.+\n)+?OK\n|OK\s(MPD)\s\d+\.\d+\.\d+|(OK)|(ACK).+\n)/;

var mycase = null;
var result = patt.exec(data);
if (result[1] == "volume")
    mycase= "volume";
else if (result[2] == "MPD")
    mycase= "MPD";
else if (result[3] == "OK")
    mycase= "OK";
else if (result[4] == "ACK")
   mycase= "ACK";

With this the result of the regex will be one of these

[ "complete match",  "volume", undefined, undefined, undefined ]
[ "complete match", undefined,     "MPD", undefined, undefined ]
[ "complete match", undefined, undefined,      "OK", undefined ]
[ "complete match", undefined, undefined, undefined,     "ACK" ]

Now you can either use the OR operator to get the case

mycase = result[1] || result[2] || result[3] || result[4];

Or just use a loop (be sure to only use non capturing groups for anything else but your cases)

for(var i = 1; i < result.length; i++){
    mycase = mycase || result[i];
}


A thread that can be interrupted before starting As per the Java documentation:

  Interrupting a thread that is not alive need not have any effect.

Particularly, interrupting a thread between the call to start() and the invocation of run() has no effect.

So I wrote a Thread which can be interrupted even before it started, so that the interrupted state is communicated once it started:

/**
 * A thread that can be interrupted before actually starting (that is between the moment {@link
 * #start} is called and {@link #run} is invoked.
 */
public final class InterruptableThread extends Thread {
    private final AtomicBoolean mInterrupted = new AtomicBoolean(false);
    private final Object mLock = new Object();
    private final AtomicBoolean mStarted = new AtomicBoolean(false);

    public InterruptableThread(Runnable runnable) {
        super(runnable);
    }

    @Override
    public void run() {
        synchronized (mLock) {
            mStarted.set(true);
            if (mInterrupted.get()) {
                super.interrupt();
            }
        }

        super.run(); // Let the original runnable handle the interruption by itself.
    }

    @Override
    public void interrupt() {
        synchronized (mLock) {
            mInterrupted.set(true);
            if (mStarted.get()) {
                super.interrupt();
            }
        }
    }
}

It seems safe to me, although the AtomicBoolean are maybe not required. But because we're dealing with multithreading here, another point of view is welcome.

I need this in a library with start() and stop() methods which look like:

public void start() {
    synchronized (mStartStopLock) {
        myThread = new InterruptableThread(myRunnable);
        myThread.start();
    }
}

public void stop() {
    synchronized (mStartStopLock) {
        myThread.interrupt();
        myThread.join();
    }
}

As you can see, despite the lock, if start() and stop() are called immediately one after another, nothing guarantees that interrupt() will have effect on the thread if it's a regular Java Thread. That's important because the Runnable uses the interrupted status for stopping itself.

Review

A Java Thread's default behavior is:

  A thread interruption ignored because a thread was not alive at the
  time of the interrupt will be reflected by this method returning
  false.

Changing the default behavior of interruption in a thread's lifecycle seems a bit tricky to me. I don't think you should override exising methods to change their specification when dealing with such common and wellknown threading constructs.
Instead, I would create 2 new methods, requestRun() and requestInterruption() to clearly indicate different functionality from run() and interrupt().
If you do decide to override run() and interrupt() make sure to clearly state in the Javadoc that the specification of these methods has changed.
InterruptableThread is an unfortunate name, since Thread is also interruptible. A better name would be PreemptiveInterruptibleThread.
Since you have atomic booleans, perhaps you could check the value before taking the lock, in order to mitigate access to the locks. There is a possible race condition though. You can read more about Double-checked locking here. Is your question implementation Idempotent?
If the atomic booleans are only used inside this lock, they could be replaced with ordinary booleans.
I like the fact everything that could be made final, has been declared final.
I do believe there still is a race condition after releasing the lock in run() and before calling super.run().


An extension method to safely retrieve or add a dictionary value The extension method:

/// <summary>
/// Thread safe. May lock on the input dictionary.
/// </summary>
public static U GetOrAdd<T, U>(this Dictionary<T, U> dict, T key, Func<U> create) {
    U val;
    if (!dict.TryGetValue(key, out val)) {
        lock (dict) {
            if (!dict.ContainsKey(key)) {
                val = create();
                dict[key] = val;
            } else {
                val = dict[key];
            }
        }
    }
    return val;
}

Sample usage:

var idVals = new Dictionary<int, List<int>>();
List<int> vals = idVals.GetOrAdd(id, () => new List<int>());
vals.Add(3);

Explanation:

If the key exists, we quickly retrieve the value using the
TryGetValue() method
If the key doesn't exist we use the provided create delegate to make a new one
We are protected against the case of two threads simultaneously looking for a key that doesn't exist by locking on the input
dictionary and afterward re-checking to see if the key still doesn't exist

Questions:

Are there scenarios that will cause this fail?
I found this extension method to be useful, but is clear enough to be properly understood by others?
Are there easier ways to achieve the thread-safety I'm looking for?
I know it's considered dangerous and bad practice to lock on an input parameter, but can I rely on the fact that locking on a dictionary to safely add/remove elements is a common convention?

Are there easier ways to achieve the thread-safety I'm looking for?

Yes, use the ConcurrentDictionary Class which is avaible since NET 4.0