Controller method to manage SMS subscriptions I have a huge method in my controller that is not DRY and just could use some general TLC. I'm new to ruby and I have not refactored my own code before, only contrived code you find on tutorials. Below I will show my controller, just to be clear I'm not looking for a full answer just maybe where I should start and some helpful tips.

def process_message(message, subscriber)
  if message == "tulip" || message == "stem"
    # If the user has subscribed flip the bit
    # and let them know
    subscribed = message == "tulip"
    subscriber.update(subscribed: subscribed)

    # Respond appropriately
    output = "You are now subscribed for updates."
    unless subscriber.subscribed
      output = "You have unsubscribed from notifications. Test 'TULIP' to start receieving updates again"
    end

    subscriber.add_to_group("visitor")

  elsif message == "dancers"
    subscribed = message == "dancers"
    subscriber.update(subscribed: subscribed)

    subscriber.add_to_group("dancers")

    output = "You have been subscribed to the Dancers list"

  elsif message == "staff"
    subscribed = message == "staff"
    subscriber.update(subscribed: subscribed)

    subscriber.add_to_group("staff")

    output = "You have been subscribed to the Staff list"

  elsif message == "volunteer"
    subscribed = message == "volunteer"
    subscriber.update(subscribed: subscribed)

    subscriber.add_to_group("volunteer")

    output = "You have been subscribed to the Volunteer list"

  else
    # If we don't recognize the command, text back with the list of
    # available commands
    output = "Sorry, we don't recognize that command. Available commands are: 'TULIP' or 'STEM'."
  end

  output

What I noticed is that there are very few differences between what's happening within the sections that the 'dancers', 'staff', and 'volunteer' messages take you through. Because the only thing that really changed between the three was the word within the message itself, I decided to combine them and use the message variable.

def process_message(message, subscriber)
  if standard_groups.include?(message)
    subscriber.update(subscribed: true)
    subscriber.add_to_group(message)

    "You have been subscribed to the #{message.capitalize} list"
  elsif message == 'tulip' || message == 'stem'
    subscriber.update(subscribed: message == 'tulip')
    subscriber.add_to_group('visitor')

    return 'You are now subscribed for updates.' if subscriber.subscribed
    "You have unsubscribed from notifications. Test 'TULIP' to start receieving updates again"
  else
    "Sorry, we don't recognize that command. Available commands are: 'TULIP' or 'STEM'."
  end
end

def standard_groups
  %w(dancers staff volunteer)
end

I was able to remove the output variable by leaving the string that you want to return as the last line that will run within the method. The exception is the line 'returned' if subscriber.subscribed comes back true.

I moved the common messages to an array so that you can easily add more in the future.

I considered separating the conditional for 'tulip' and 'stem' into 2 individual conditionals, but to me it made more sense to keep the "exceptions" together, especially since they share the 'visitor' group. For increased legibility, you may choose to separate them.


Finding remainder of stepping by multiple beyond a limit Summary: Looking for more elegant version of Math.ceil(a/b)*b - a.

I'm writing code (QML Canvas) that draws a timeline, with tick marks every n pixels.

// Stepping across the width of the window, drawing tick marks
for (var x=0; x<windowWidth; x+=n) drawTickAndLabelAt(x);

The timeline can be scrolled such that time=0 moves off the left edge of the window. I need to figure out the correct x value to start at so that the ticks are still drawn at the same time. That value is the multiple of n that is just larger than the scroll offset, minus the scroll offset.

This is the naive representation of that formula:

var firstTickX = Math.ceil(scrollOffset/n)*n - scrollOffset;
for (var x=firstTickX; x<windowWidth; x+=n) drawTickAndLabelAt(x);

This works, but the formula feels inelegant, referencing both variables twice. Can you think of a simpler code path (using modulus, I'm assuming) that I'm failing to think of?

Math.ceil(scrollOffset/n)*n - scrollOffset

gives you the difference between scrollOffset and the next multiple of n larger or equal to scrollOffset. This is equivalent to:

var firstTickX = (scrollOffset % n) ? n - (scrollOffset % n) : 0;


Embolden parts of auto-complete suggestions that don't match the query I made a function to embolden text that doesn't match a string, but it appears to be very performance-heavy. I am certain that there are much better ways to do this, but with what I tried, I ran into a lot of trouble.

As a side note, one of the ways I know this is performance-heavy, is that when I type a few characters, and backspace them all, Chrome starts taking up more and more memory until it crashes.

Yes! I know this is not StackOverflow, so I'm just asking for some pointers on what the issues are with the code.

function Bolden(value, query) {
    var arr = []
    if (!value) return;
    while (value !== "") { // While the value still has work to be done on it
        if (value.toLowerCase().startsWith(query.toLowerCase())) {
            arr.push("" + value.slice(0, query.length) + "")
            value = value.slice(query.length, value.length)
        }
        else {
            arr.push(value.slice(0, 1))
            value = value.slice(1, value.length)
        }
    }
    return arr.join('')
}

Based on the current context available, if your query is not to be treated as a regex/custom pattern, I think a simple string.split should be enough. I am not that familiar with conventions in the JS world, but the last time I had worked with it, function names used to be in camelCase.

Also note that I am using the template literals when returning from bolden function; which should actually be named unemphasize (or unbold or normaliser).

function bolden(value, query) {
  if (!value) return;
  let splt = value.split(query)
  return splt.join(`<span style="font-weight:normal">${query}</span>`)
}

let tests = new Map([
  ['some', 'e'],
  ['things', 'thi'],
  ['other', 'te'],
  ['looooooooong', 'o']
])

for (let [v, q] of tests)
  console.log(bolden(v, q))


Calculating number of variations I was practicing for the upcoming zco in CodeChef, where I came across this problem:

  Given some number \$K\$ and a list of \$N\$ numbers, count the number of pairs (\$i\$, \$j\$) such that \$1 \le i \lt j \le N\$ and \$|a_i − a_j | \ge K\$.

  \$1 \le N \le 65000\$
  \$1 \le K \le 10^8\$
  \$0 \le a_i \le 10^8\$

I got the algorithm correct for \$N \le 4000\$, but for \$N \le 65000\$, it failed to compute in the given time limit.

#include <iostream>
#include <vector>
#include <sstream>
#include <cmath>
#include <cstdio>

using namespace std;

vector<int>split(string s){
    stringstream ss(s);
    string item;
    vector<int> elems;
    while(getline(ss,item,' ')){
        elems.push_back(stoi(item));
    }
    return elems;
}

int main(){
    string one,two;
    getline(cin,one);
    getline(cin,two);

    vector<int> testCases = split(one);
    vector<int> nums = split(two);

    int args = testCases[0];
    int k = testCases[1];
    int cases = 0;

    for(int i=0;i<args-1;i++){
        for(int j=1;j<nums.size();j++){
            int temp = abs(nums[0]-nums[j]);
            if(temp >= k){
                cases++;
            }
        }
        nums.erase(nums.begin());
    }

    printf("%i\n",cases);
    return 0;
}

I tried to use the printf instead of std::cout, because I read somewhere that it is much faster than the latter, but the result was same. How can I overcome the TLE? I also tried some few more tricks but they somehow altered the algorithm as a result they were giving wrong outputs.

using namespace std;

See Why is using namespace std in C++ is considered bad practice on why you should avoid using directives at the global scope.

vector<int>split(string s){
    // ......
    while(getline(ss,item,' ')){
    // ......
}

Horizontal spacing helps readability by distinguishing language constructs.  Unless you are code golfing, you should write code for correctness and readability.

std::vector<int> split(const std::string& s){
    // ......
    while (std::getline(ss, item, ' ')) {
    // ......
}

Consider your function call that splits a sequence of digits.

    vector<int> nums = split(two);

How many allocations/reallocations are being made in split()?

Every time you call split(), you are passing the arguments in by value.  Prefer to pass by value when parameters are cheap to copy.  Otherwise, pass by reference (to const if immutable) when parameters are expensive to copy or have an unknown cost. Determining the cost is architecture dependent. For most systems today, anything more the two or three words (size of a double or reference) should be considered expensive.

When creating the sequence, elems.push_back() will do many reallocations.  The amount of reallocations is implementation dependant upon the std::vectors growth factor.  The sequence length is one of the input parameters of the problem.  Use that length to reserve the space before reading.

nums.erase(nums.begin());

Again, avoid unnecessary copies.  Every time nums.erase() is called, you are copying all the remaining elements in the sequence.  You could avoid the calls by just using i and j as the indices.

    for (int i = 0; i < args - 1; ++i) {
        for (int j = i + 1; j < args; ++j) {
            int temp = abs(nums[i] - nums[j]);
            if (temp >= k) {
                ++cases;
            }
        }
    }

  I tried to use the printf instead of std::cout, because I read somewhere that it is much faster than the latter, but the result was same. How can I overcome the TLE? I also tried some few more tricks but they somehow altered the algorithm as a result they were giving wrong outputs.

99% of problems on these code challenge sites will produce TLE's because of your algorithm and not the I/O method being employed.  In the case of scanf/printf vs std::cin/std::cout, I prefer the latter for these types of exercises.  If you really need the performance of C formatted I/O from C++ IOStreams, consider the following:

Disable synchronization

std::ios::sync_with_stdio(false);

Untie the streams.

std::cin.tie(nullptr);

Avoid unnecessary flushes (prefer '\n' to std::endl).

A better approach, avoid reading as a std::string and tokenizing.  Read the arguments as their intended type. Ensure you reserve space in your std::vector before reading values.

We can make improvements to the algorithm through sorting. The problem states as one of the preconditions that \$i < j\$.  With a sorted sequence (in ascending order), every element is guaranteed to be less than or equal to the elements that follow it.  When you find one element that meets the variation threshold, every element after that also meets the threshold.  To find the first element that meets that threshold, C++ provides both linear search (std::find_if()) and binary search (std::lower_bound()).  Since the sequence is sorted, binary search should be the faster search for any meaningful sized sequence.  Use std::distance to find the counts, use std::accumulate to sum those counts.  Just using the standard library produced a top-10 time on codechef for c++14.


Initializing a new user I have a method in my rails project that initializes a new user by copying some properties of another. The method should also retain entered parameters if saving the new user is rejected. Rubocop complains that Assignment Branch Condition Size for this method is 42.02/15. How can I improve this?

def setup_user_clone
    member_id = (params[:id] || params[:member_id])
    @membership = Membership.find(member_id)
    accounts = @membership.user.accounts.map(&:id) | [@account.id]
    cloned_user = User.new @membership.user.attributes.slice('permissions')
    cloned_user.game_plan_admin = @membership.user.game_plan_admin
    if user_edit_params
      cloned_user.email = invite_email
      cloned_user.permissions = user_edit_params[:permissions]
      cloned_user.accounts = Account.find(invite_app_access.map(&:to_i))
      cloned_user.level = user_edit_params[:user_level]
    end
    profile = SettingsProfile.new @account, cloned_user
    accounts |= [*cloned_user.accounts.map(&:id).to_set]
    @user_edit = UserEdit.new current_user, profile, @membership.user.admin?, accounts, @membership.user.shared_credentials.map(&:id)
    @method = :post
  end

Here's my notes

First don't use #map and use #pluck instead (for database calls), all over your code.

bad:

@membership.user.accounts.map(&:id)

better:

@membership.user.accounts.pluck(:id)

Use eager loading, to reduce queries

Bad:

Membership.find(member_id)

Better:

Membership.includes(user: :accounts).find(member_id)

Because you are using users and accounts in the loops after.
This whole block could be reduced to a single statement

if user_edit_params
  cloned_user.email = invite_email
  cloned_user.permissions = user_edit_params[:permissions]
  cloned_user.accounts = Account.find(invite_app_access.map(&:to_i))
  cloned_user.level = user_edit_params[:user_level]
end

To

if user_edit_params
  cloned_user.assign_attributes(
    email: invite_email
    permissions: user_edit_params[:permissions]
    accounts: Account.find(invite_app_access.map(&:to_i))
    level: user_edit_params[:user_level]
  )
end

No idea what this does

@membership.user.attributes.slice('permissions')

but wouldn't this do the same ?

@membership.user.permissions

Law of Demeter
And basically just group common stuff into single methods and call the methods inside this method, isntead of having one huge method like this


Counting pairs of elements in a circular ArrayList containing -1, 0, and 1 I have the following method:

public void test() {

    List<Integer> slopeChanges = new ArrayList<Integer>();
    slopeChanges.add(0);
    slopeChanges.add(0);
    slopeChanges.add(1);
    slopeChanges.add(0);
    slopeChanges.add(1);

    List<Double> sixProbabilites = new ArrayList<Double>();

    int count_neg10 = 0, count_neg11 = 0, count_10 = 0, count_1neg1 = 0, count_0neg1 = 0, count_01 = 0;

    for(int i=0; i<slopeChanges.size(); i++) {
        if(i+1 != slopeChanges.size()) {
            if((slopeChanges.get(i) == -1) && (slopeChanges.get(i+1) == 0)) {count_neg10++;}
            else if((slopeChanges.get(i) == -1) && (slopeChanges.get(i+1) == 1)) {count_neg11++;}
            else if((slopeChanges.get(i) == 1) && (slopeChanges.get(i+1) == 0)) {count_10++;}
            else if((slopeChanges.get(i) == 1) && (slopeChanges.get(i+1) == -1)) {count_1neg1++;}
            else if((slopeChanges.get(i) == 0) && (slopeChanges.get(i+1) == -1)) {count_0neg1++;}
            else if((slopeChanges.get(i) == 0) && (slopeChanges.get(i+1) == 1)) {count_01++;}
        }else {
            if((slopeChanges.get(i) == -1) && (slopeChanges.get(0) == 0)) {count_neg10++;}
            else if((slopeChanges.get(i) == -1) && (slopeChanges.get(0) == 1)) {count_neg11++;}
            else if((slopeChanges.get(i) == 1) && (slopeChanges.get(0) == 0)) {count_10++;}
            else if((slopeChanges.get(i) == 1) && (slopeChanges.get(0) == -1)) {count_1neg1++;}
            else if((slopeChanges.get(i) == 0) && (slopeChanges.get(0) == -1)) {count_0neg1++;}
            else if((slopeChanges.get(i) == 0) && (slopeChanges.get(0) == 1)) {count_01++;}
        }
    }

    System.out.println(slopeChanges);

    if(count_neg10 != 0) {System.out.println("count_neg10 = " + count_neg10);}
    if(count_neg11 != 0) {System.out.println("count_neg11 = " + count_neg11);}
    if(count_10 != 0)    {System.out.println("count_10 = " + count_10);}
    if(count_1neg1 != 0) {System.out.println("count_1neg1 = " + count_1neg1);}
    if(count_0neg1 != 0) {System.out.println("count_0neg1 = " + count_0neg1);}
    if(count_01 != 0)    {System.out.println("count_01 = " + count_01);}

    if(count_neg10 != 0) {sixProbabilites.add((double)count_neg10 / ((double)slopeChanges.size()));}
    if(count_neg11 != 0) {sixProbabilites.add((double)count_neg11 / ((double)slopeChanges.size()));}
    if(count_10 != 0) {sixProbabilites.add((double)count_10 / ((double)slopeChanges.size()));}
    if(count_1neg1 != 0) {sixProbabilites.add((double)count_1neg1 / ((double)slopeChanges.size()));}
    if(count_0neg1 != 0) {sixProbabilites.add((double)count_0neg1 / ((double)slopeChanges.size()));}
    if(count_01 != 0) {sixProbabilites.add((double)count_01 / ((double)slopeChanges.size()));}
}

The slopeChanges list contains symbols that are either 0, 1, or -1. I would like to count frequencies of sub-blocks that are either 01, 10, -11, 1-1, -10, 0-1. The method that I showed does what I want, for example, this block of symbols 00101 should result in count_10 = 2 which means 10 sub-block occurs twice while 01 (i.e., count_01 = 2) occurs twice. Please note that the we consider the first symbol is also last.

As you can see, there are lot of duplication in the code in order to perform what I want. Is there a better way to re-write this function in a very elegant style?

The 2nd way is to use the array with unique index calculated from current and next value:

public void test() {

    List<Integer> slopeChanges = new ArrayList<Integer>();
    slopeChanges.add(0);
    slopeChanges.add(0);
    slopeChanges.add(1);
    slopeChanges.add(0);
    slopeChanges.add(1);

    /*
    static final int count_neg10 = 2; // -1 + 3 * (0 + 1);
    static final int count_neg11 = 5; // -1  + 3 * (1 + 1);
    static final int count_10 = 4; // 1 + 3 * (0 + 1);
    static final int count_1neg1 = 1; // 1 + 3 * (-1 + 1);
    static final int count_0neg1 = 0; // 0  + 3 * (-1 + 1);
    static final int count_01 = 6; // 0  + 3 * (1 + 1);*/

    int[] count = {0, 0, 0, 0, 0, 0, 0};
    String[] count_names = {"count_0neg1", "count_1neg1", "count_neg10", "", "count_10", "count_neg11", "count_01"};

    List<Double> sixProbabilites = new ArrayList<Double>();

    for(int i = 0, j = slopeChanges.size() -1; i<slopeChanges.size(); i++) {
      if (slopeChanges.get(i) != slopeChanges.get(j)) {
        count[slopeChanges.get(i) + 3 * (slopeChanges.get(j) + 1) ]++;
      }
      j = i;
    }

    System.out.println(slopeChanges);

    for(int i = 0; i<7; i++) {
      if(count[i] != 0) {
        System.out.println(count_names[i] + " = " + count[i]);
        sixProbabilites.add((double)count[i] / ((double)slopeChanges.size()));
      }
    }
}


JavaScript circular linked list compatriot game I found this question in O'Reilly Data Structure and Algorithm in Javascript:

  According to legend, the first-century Jewish historian Flavius
  Josephus was about to be captured along with a band of 40 compatriots
  by Roman soldiers during the Jewish-Roman War. The Jewish soldiers
  decided that they preferred suicide to being captured and devised a
  plan for their demise. They were to form a circle and kill every third
  soldier until they were all dead. Josephus and one other decided they
  wanted no part of this and quickly calculated where they needed to
  place themselves so they would be the last survivors.

  Write a program that allows you to place n people in a circle and
  specify that every mth person will be killed. The program should
  determine the number of the last two people left in the circle. Use a
  circularly linked list to solve the problem.

This is my solution:

function Node(element) {
    this.element = element;
    this.next = null;
}

function LList() {
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.advance = advance;
    this.count = count;
}

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == this.head)) {
        prevNode.next = prevNode.next.next;
    }
}
function findPrevious(item) {
    var currNode = this.head;
    while (!(currNode.next == this.head) &&
        (currNode.next.element != item)) {
        currNode = currNode.next;
    }
    return currNode;
}
function display() {
    var currNode = this.head;
    while (!(currNode.next == this.head)) {
        print(currNode.next.element);
        currNode = currNode.next;
    }
}
function count() {
    var currNode = this.head;
    var count = 0;
    while (!(currNode.next == this.head)) {
        count++
        currNode = currNode.next;
    }
    return count;
}
function find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}
function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

function advance(item, n) {
    var currNode = this.find(item);
    for (let i = n; i > 0; i--) {
        currNode = currNode.next;
    }
    return currNode;
}

function survivor(number, position) {
    //40 compatriots
    //kill every third soldier. advance by 3
    //last two survivors

    //place n people in a circle
    var compatroits = new LList();
    var currNode = compatroits.head;

    for (let i = 1; i <= number; i++) {
        compatroits.insert(i, currNode.element);
        currNode = currNode.next;
    }

    //kill every mth person in the circle
    //start from head
    var currItem = compatroits.head.element;
    while (compatroits.count() > 2) {
        //advance mth person
        var killNode = compatroits.advance(currItem, position);

        //set new start point to m.next node
        currItem = killNode.next.element;

        //remove mth person
        compatroits.remove(killNode.element);
    }

    //determine the last two people in the circle
    return compatroits.display();
}

Does anyone have a more efficient way to solve this problem?

The Ouroboros

Your code is way too complex for the task

The most obvious improvement is to remove the functions find, findPreviouse, and count

Why

Rather than hold the data each list item has, hold the current link. This means you dont need to find the item each time you move along the list
You can know the remaining number of links by counting each link removed so there is no need for the function count.
If you remove the next link in the sequence rather than the current you don't need to find the previous link as you already have that, thus you dont need findPreviouse.

Some more points

When doing a simple countdown use a while loop. eg while (n--) { is much simpler than for (let i = n; i > 0; i--) {
Don't test for conditions if there is no need. In remove you have if (!(prevNode.next == this.head)) { which I can not work out why you have it there. Also it should have been written as if (prevNode.next !== this.head) {
You should use const when ever possible, only if the variable has to change should you use var or let
Always use === or !== never use == or !=
If you are defining a object use the prototype or define the properties as an object. Creating a list of unrelated function names and then adding them to the object at creation is a mess, a source of bugs from the inevitable naming conflicts.

eg

function LList() {
    this.head = new Node("head");
    this.head.next = this.head;
}
LList.prototype = {
    remove(item) {
        // function body
    },
    findPrevious(item) {
        // function body
    },
    display() {
        // function body
    },
    count() {
        // function body
    },
    // and so on...
};

Rewrite

I think that the LList and Node objects are overkill for this problem. A simple ad-hock object can hold the item position and link to the next. You only need to hold the current node, and to determine when you have two left just count off each item as they are removed.

function survivor(number, step) {
    var i = 0, current;
    const add = pos => {
        const link = {pos};
        if (current) {                 // check if not first item
            link.next = current.next;  // insert link to tail
            current.next = link;
        } else { link.next = link }    // first link points to self
        current = link;                // Hold current as head
    }
    const stepOverAndRemove = (link, n) => {
        while (--n) { link = link.next }   // do this n-1 times
        return link.next = link.next.next; // remove next link and return link after that
    }

    while (i < number) { add(i++) }  // create list
    current = current.next;          // move to the start

    // remove every `step` item until only two remain
    while (number-- > 2) { current = stepOverAndRemove(current, step) }

    // return the position of the remaining two
    return [current.pos, current.next.pos];
}


In-memory top ten solution Is there anything wrong with the following implementation of an in-memory top-ten bought products tracker?

public class Main {

    private static List<Integer> topTenItems = Collections.synchronizedList(new ArrayList<Integer>(Collections.nCopies(10, 0)));
    private static List<Integer> topTenScores = Collections.synchronizedList(new ArrayList<Integer>(Collections.nCopies(10, 0)));
    private static ConcurrentMap<Integer,Integer> itemsScores;

    public static void main(String[] args)
    {
        itemsScores = new ConcurrentHashMap<Integer,Integer>();

        for (int i = 0; i < 1000000; i++)
        {
            Integer boughtItem = new Integer((int)(Math.random() * 100) + 1);
            bought(boughtItem);
        }

        assert isSorted(topTenItems);
        assert isSorted(topTenScores);

        System.out.println("items: " + getTopTen());
        System.out.println("scores:" + topTenScores);

    }

    public static boolean isSorted(List<Integer> l)
    {
     for (int i = 1; i < l.size(); i++)
     {
         if (l.get(i - 1) < l.get(i))
             return false;
     }
     return true;
    }

    public static void bought(Integer itemId)
    {
        Integer oldScore = itemsScores.get(itemId);
        Integer newScore;
        if (oldScore == null)
            newScore = 1;
        else
            newScore = oldScore + 1;

        itemsScores.put(itemId,newScore);
        doTopTen(itemId,newScore);
    }

    private static void doTopTen(Integer itemId, Integer newScore)
    {
        if (topTenItems.contains(itemId))
        { // we have this already; up the score, check the position
            int itemIndex = topTenItems.indexOf(itemId);
            if (itemIndex > 0)
            { // not top already
                if (topTenScores.get(itemIndex - 1) < newScore)
                {
                    // move to one position above
                    Integer tempProd = topTenItems.get(itemIndex - 1);
                    Integer tempScore = topTenScores.get(itemIndex - 1);
                    topTenItems.set(itemIndex - 1, itemId);
                    topTenScores.set(itemIndex - 1, newScore);
                    topTenItems.set(itemIndex, tempProd);
                    topTenScores.set(itemIndex, tempScore);
                }
                else
                { // just update the score
                    topTenScores.set(itemIndex, newScore);
                }
            }
            else
            {
                topTenScores.set(0,newScore);
            }
        }
        else
        {
            for (int i = 0; i < 10; i++)
            {
                // left to right
                if (topTenScores.get(i) <= newScore)
                {
                    topTenItems.add(i, itemId);
                    topTenScores.add(i, newScore);
                    topTenItems.remove(10);
                    topTenScores.remove(10);
                    break;
                }
            }
        }

    }

    public static List<Integer> getTopTen()
    {
        return topTenItems;
    }
}

Yes.

Actually quite a lot. But it's all easily salvageable.

static. It's all static. Hard to test and impossible to use twice (imagine top-ten of two classes of products). Any mutable static field is a code smell. Just drop it everywhere. Rename main and add a new main creating an instance and calling the original main.
private static ConcurrentMap<Integer,Integer> itemsScores;

This can be initialized inline just like the lists.

public static void main(String[] args)
{

Proper Java style is
public static void main(String[] args) {

This applies to all blocks, not only to methods.

Integer boughtItem = new Integer((int)(Math.random() * 100) + 1);

Don't use Math.random() with some strange arithmetic when you can create a new Random() and write
random.nextInt(100)
Don't use new Integer when you don't need a new instance (you should never need a new instance). Use Integer.valueOf, or just leave it out (autoboxing).

    assert isSorted(topTenItems);

Asserts are fine, but not for this. Checking that the list is sorted is actually the only thing the code does, so it makes no sense to switch it off. So use
   if (!isSorted(topTenItems)) {
        throw new WhateverException("some message");
   }

or better: Write a proper test using JUnit or alike.

public static boolean isSorted(List<Integer> l)

This doesn't do what the name promises. I'd expect a sorted list not to change after I call Collections.sort. Your list is descending. Moreover, it must be strictly descending. So the method name should express it.
Checking for strictly descending is wrong, isn't it?

    Integer newScore;
    if (oldScore == null)
        newScore = 1;
    else
        newScore = oldScore + 1;

Always use braces. Or better, write
    Integer newScore = oldScore == null ? 1 : oldScore + 1;

It's much shorter and clearer.

    doTopTen(itemId,newScore);

Wouldn't updateTopTen be a better name?

private static void doTopTen(Integer itemId, Integer newScore) ...

This looks very complicated. What's worse:

You're using synchronizedList, so you're assuming concurrent access.
The method itself is not synchronized and it'' probably break.

Imagine you test topTenItems.contains(itemId) and in the meantime another thread(s) change the list. So you're doing something based on a wrong test outcome.
I'm a bit lost
Your items are Integers and you're assuming they're sorted, too. Why should they? What do you need them for?
I might go for something like
// start empty as initially there's nothing in top ten
private final List<Integer> topTenItems = new ArrayList<Integer>();
// no topTenScores

private final Object lock = new Object();

private void updateTopTen(Integer itemId, Integer newScore) {
    synchronized (lock) {
        int index = topTenItems.indexOf(itemId);
        if (index == -1) {
            index = topTenItems.size();
            topTenItems.add(itemId);
        }
        while (index > 0 && itemsScores.get(index) > itemsScores.get(index-1)) {
            swap(index, index-1);
            index--;
        }
        if (topTenItems.size() > TOP_TEN_SIZE) {
            topTenItems.remove(TOP_TEN_SIZE);
        }
    }
}


Generic Producer-Consumer in C++11 I wrote the following simple 1 producer - 1 consumer problem, in attempt to learn some C++11 threading / generics.

#include <iostream>
#include <mutex>
#include <condition_variable>
#include <deque>
#include <thread>

struct data {
    int x, y;
    std::string s;

    data() : s("test") {
        x = std::rand() % 1000000;
        y = std::rand() % 1000000;
    }

    friend std::ostream& operator<<(std::ostream& os, const struct data d) {
        os << d.x << ", " << d.y << ", " << d.s << "\n";
    }
};

typedef struct data elem_t;

template <typename T>
class Buffer
{
public:
    Buffer(): m_size(1) {}
    Buffer(int s): m_size(s) {}

    void add(T x) {
        while (true) {
            std::unique_lock<std::mutex> locker(m_mtx);
            m_cond.wait(locker, [this](){return m_buffer.size() < m_size;});

            m_buffer.push_back(x);

            locker.unlock();
            m_cond.notify_all();

            return;
        }
    }

    T remove() {
        while (true) {
            std::unique_lock<std::mutex> locker(m_mtx);
            m_cond.wait(locker, [this](){return m_buffer.size() > 0;});

            T x = m_buffer.back();
            m_buffer.pop_back();

            locker.unlock();
            m_cond.notify_all();

            return x;
        }
    }

private:
    std::mutex m_mtx;
    std::condition_variable m_cond;

    std::deque<T> m_buffer;
    unsigned int m_size;
};

template <typename T>
class Producer
{
public:
    Producer() : m_buf(nullptr) {}
    Producer(std::string&& id, Buffer<T> *buf) : m_id(id), m_buf(buf) {}

    void produce() {
        while (true) {
            T x = T();

            m_buf->add(x);
            std::cout << x;

            int sleep = std::rand() % 1000 + 10;
            std::this_thread::sleep_for(std::chrono::milliseconds(sleep));
        }
    }

private:
    Buffer<T> *m_buf;
    std::string m_id;
};

template <typename T = int>
class Consumer
{
public:
    Consumer() : m_buf(nullptr) {}
    Consumer(std::string&& id, Buffer<T> *buf) : m_id(id), m_buf(buf) {}

    void consume() {
        while(true) {
            T x = m_buf->remove();
            std::cout << x;

            int sleep = std::rand() % 1000 + 10;
            std::this_thread::sleep_for(std::chrono::milliseconds(sleep));
        }
    }

private:
    Buffer<T> *m_buf;
    std::string m_id;
};

int main(int argc, char const *argv[])
{
    std::srand(std::time(nullptr));

    Buffer<elem_t> *buffer = new Buffer<elem_t>(std::stoi(argv[1]));
    Producer<elem_t> *p = new Producer<elem_t>("prod", buffer);
    Consumer<elem_t> *c = new Consumer<elem_t>("cons", buffer);

    std::thread pt(&Producer<elem_t>::produce, p);
    std::thread ct(&Consumer<elem_t>::consume, c);

    pt.join();
    ct.join();

    return 0;
}

The main concern I am having with this code is regarding genericity.
I have a generic buffer Buffer<T> (which is basically a std::deque<T>) and the produced value: T x = T();

For now, T = struct data, and everything works because of data(), but if T = int, for example, things start to get ugly.

One idea I have is to define a struct data packing all the needed fields, and then remove templates from classes (i.e. std::deque<struct data> only).

So, are templates an overkill here, and if not what is the / a correct way of expressing this code with them?
Also, are there any other problems / code smells / things to improve?

Buffer<T>

This class seems fine for the most part. Some small issues:

The while(true) loops in insert(T) and remove() only ever run one iteration. Those loops can be replaced by their body.
add calls m_buffer.push_back(x), which might not compile for types without a copy constructor. Try m_buffer.push_back(std::move(x)) instead: That will move if possible, and fall back to copy if not.
m_buffer is treated like a stack (push_back and pop_back are used only), so newest insertions get removed first. Maybe a queue was intended (using e.g. push_front and pop_back)?
The constructors initialize Buffer<T>::m_size (an unsigned int) with a signed value (1 or int s, respectively).
notify_all() is called on the condition variable. This would wake up every thread waiting on it - but very likely only one would actually be able to do anything. notify_one() would likely be a better fit.
The notify_all calls on the condition variable aren't needed every time: remove only needs to notify if other threads might be waiting to add elements, which is only when m_buffer.size() == m_size - 1 after the call to pop_back. Similarly, add only needs to notify if m_buffer.size() == 1 after push_front.
Buffer<T>::m_size doesn't represent the current size of the buffer (= number of elements contained), but the maximum capacity. Maybe m_capacity would be a better name.
Buffer itself isn't very descriptive of what it actually does. ConcurrentQueue, MessageQueue or similar would better represent its behavior.
While add and remove by themselves are fine names, common expectation for queue-like types are push and pop.
This actually is a working queue for n producers and m consumers. It seems a bit overkill for a 1 producer + 1 consumer scenario.

Furthermore, some improvements could be made:

bool try_push(T&&)/bool try_push(const T&)/bool try_pop(T&) member functions could be added that return early if the operation would otherwise have to wait.
push could be overloaded for const T& and T&& to enable better performance for moveable types.

Producer<T>/Consumer<T>

Both of these don't really seem necessary. Generally, its unlikely that someone will ever need generic producers/consumers (other than maybe for testing purposes), so I won't go into too much detail

Default constructors initialize m_buf to nullptr, but this is never checked afterwards. Either add checks for nullptr in the other member functions, or simply remove the default constructor.
Similarly, the buf parameter of the other constructor can be nullptr. If m_buf should never be nullptr (as the member functions seem to assume), simply make buf a Buffer<T>& instead. m_buf could then be initialized to &buf - but it might be more reasonable to change m_buf to Buffer<T>&, too.
Access to std::cout isn't synchronized. In some cases, this means the consumer might print before the producer does.
There is no way to stop a producer/consumer (other than forcefully terminating the program).
The member m_id is never used.
The second constructor takes a std::string&& id parameter - but initializes m_id without moving - which creates a copy. Generally, it would be expected that the object id refers to would be moved from after construction.

General stuff

main never checks if argv[1] is actually valid.
Using struct data when referencing the type isn't necessary in C++, just data suffices. So typedef struct data elem_t; could be simplified to typedef data elem_t;, or with a more modern approach, using elem_t = data;. (The struct data would be necessary in C, but this code will never interact with C as C doesn't support templates anyways.)
Many places use parentheses to initialize objects, like std::unique_lock<std::mutex> locker(m_mtx);. Prefer braces {} instead: In the example, if m_mtx could be interpreted as a type, then the compiler would be forced to make locker a function declaration. Using braces would prevent that from happening.
Prefer the utilities in the <random> header for generating random numbers, as std::rand is kinda terrible.
There's no need to create buffer, p and c on the heap (inside main). Using local variables would be just fine. (Also, they never get deleted properly. If allocation on the heap is absolutely needed, prefer using smart pointers like std::unique_ptr or std::shared_ptr.)
I cannot think of a 1 producer/1 consumer scenario in which threads are necessary: Most could be simplified to this pseudocode:

int main() {
    while(keep_running()) {
        consume_one(produce_one());
    }
}


MVC4 Routes, using Default Should I leave the Default Route in if it's not adding any benefit?

I have a RouteConfig.cs file that looks like this:

public static void RegisterRoutes(RouteCollection routes)
{
    routes.IgnoreRoute("{resource}.axd/{*pathInfo}");

    routes.MapRoute(
        name: "Dashboard",
        url: "{controller}/{action}",
        defaults: new { controller = "JobDashboard", action = "Index" }
    );

    routes.MapRoute(
        name: "Default",
        url: "{controller}/{action}/{id}",
        defaults: new { controller = "JobDashboard", action = "Index", enumDigit = UrlParameter.Optional }
    );

    routes.MapRoute(
        name: "Login",
        url: "{controller}/{action}",
        defaults: new { controller = "Account", action = "Login" }
    );
}

If I only have the Default and Login Routes and the user goes to the root of the site (eg www.sitename.com), then the user always goes to the Login page. I don't want them going to the Login page after they've logged in, and after a little bit of digging I discovered that MVC4 always sorts Route Order Importance by Custom Route first, and then the Default Route.

I created the Dashboard route, and everything is working fine. I then took out the Default route because it didn't seem needed. Nothing seems to be affected by removing the Default Route, and that leads me to the question, should I leave the Default Route in there?

I seem to recall that having a Default Route is good practice, but if it's not adding anything to the solution, is there a good reason to keep it around?

I am thinking that you would want to keep that default route in there in the case that something happens to the other routes, then there is something to route to if your custom routes get hosed up for some reason.

Defaults are there for a reason, don't get rid of them


Finding travel distance between airports I have 2 nested for loops which i want to get rid of. Any thoughts?
I am calculating distance between cities based on their longitude and latitude. There is a custom function earth.dist() that i am using in the loop.

for (i in 1:nrow(dat)) {
  #for each other airport
  for (j in 1:nrow(dat)) {
    #if both airport are different
    if (dat[i,3]!=dat[j,3]){
      k=k+1
      #airport1
      airport1[k] <- dat[i,3]
      #airport2
      airport2[k] <- dat[j,3]
      #find travel distance
      travdist[k] <- earth.dist(dat[i,5],dat[i,4],dat[j,5],dat[j,4])

    }
  }
}

function for distance calculation

earth.dist <- function (lon1, lat1, lon2, lat2){
  rad <- pi/180
  a1 <- lat1 * rad
  a2 <- lon1 * rad
  b1 <- lat2 * rad
  b2 <- lon2 * rad
  dlon <- b2 - a2
  dlat <- b1 - a1
  a <- (sin(dlat/2))^2 + cos(a1) * cos(b1) * (sin(dlon/2))^2
  c <- 2 * atan2(sqrt(a), sqrt(1 - a))
  R <- 6378.145
  d <- R * c
  return(d)
}

First, let's download some data similar to yours (I assume). This csv available online has almost 7,000 airports:

url <- "https://commondatastorage.googleapis.com/ckannet-storage/2012-07-09T214020/global_airports.csv"
library(RCurl)
txt <- getURL(url)
data <- read.csv(textConnection(txt), stringsAsFactors = FALSE)

For illustration purposes, we will use a small sample: the six airports in Jamaica.

dat <- subset(data, country == "Jamaica",
              c("city", "country", "name", "latitude", "longitude"))
dat
#              city country               name latitude longitude
# 1745    Ocho Rios Jamaica           Boscobel 18.40425 -76.96902
# 1746     Kingston Jamaica Norman Manley Intl 17.93567 -76.78750
# 1747  Montego Bay Jamaica      Sangster Intl 18.50372 -77.91336
# 1748 Port Antonio Jamaica          Ken Jones 18.19881 -76.53453
# 1749     Kingston Jamaica         Tinson Pen 17.98856 -76.82376
# 5878       Negril Jamaica   Negril Aerodrome 18.34000 -78.33556

Now let's have a look at your code. I will not review the math in earth.dist, I'll assume it is correct. One beautiful thing about that function is that it is vectorized, i.e., you could give it n-long vectors as inputs and it will compute n distances in a single call. Unfortunately, the rest of your code does not take advantage of it. Instead, your double loop only calls earth.dist with scalars at each time...

Instead of a double loop, you should be using the outer function. Have a look at the doc (?outer) if you are not familiar with it. The typical usage is outer(X, Y, FUN) where X and Y are vectors and FUN is a vectorized function. The output is a matrix Z where Z[i, j] is the result of FUN(X[i], Y[j]). But what's brilliant about outer is that it does not call FUN as many times as there are entries in Z (length(X) * length(Y)). No, it calls is only once. How? Because FUN is vectorized (a requirement) and outer knows how to take advantage of it.

So, here is how we can massage your data a bit so we can use outer. First, remember that outer loops on the pairwise combinations from two vectors. In our case, we could use the names of the airports:

airport.names <- dat$name

so we will be calling outer(airport.names, airport.names, FUN = airport.dist). All that is left is to write airport.dist: a vectorized function that will take as inputs two vectors of airport names and return their distances. We could first put the important data in a matrix with airport names as row names for easy access:

dat.mat <- as.matrix(dat[, c("latitude", "longitude")])
rownames(dat.mat) <- airport.names

Then define:

airport.dist <- function(name1, name2, data = dat.mat) {
    lon1 <- data[name1, "longitude"]
    lat1 <- data[name1, "latitude"]
    lon2 <- data[name2, "longitude"]
    lat2 <- data[name2, "latitude"]
    return(earth.dist(lon1, lat1, lon2, lat2))
}

Then run outer:

dist.mat <- outer(airport.names, airport.names, FUN = airport.dist)

and attach names to the columns and rows:

dimnames(dist.mat) <- list(airport.names, airport.names)

#                     Boscobel Norman Manley Intl Sangster Intl Ken Jones Tinson Pen Negril Aerodrome
# Boscobel             0.00000           55.58311     100.33081  51.30027   48.75737        144.54554
# Norman Manley Intl  55.58311            0.00000     134.79830  39.68379    7.02926        169.83797
# Sangster Intl      100.33081          134.79830       0.00000 149.58621  128.67955         48.17112
# Ken Jones           51.30027           39.68379     149.58621   0.00000   38.52863        191.03056
# Tinson Pen          48.75737            7.02926     128.67955  38.52863    0.00000        164.62138
# Negril Aerodrome   144.54554          169.83797      48.17112 191.03056  164.62138          0.00000

If you need to convince yourself that earth.dist was called a single time, you could add a cat("HELLO\n") somewhere inside its body (I did!). earth.dist having been called only once, there is no need to say how fast the computation will be.

Finally, if you want to store the distances in a three column (airport1, airport2, distance) data.frame rather than a matrix, you can do:

d <- dist.mat
dist.df <- data.frame(airport1 = rownames(d)[row(d)],
                      airport2 = colnames(d)[col(d)],
                      distance = c(dist.mat))

I hope it helps! Don't hesitate to comment below if you have questions.


Data item prototype in a Javascript data structure where object instance functions see own data I'm working on a complex Javascript application which includes its own data structure. The previous version's data structure was rather chaotic, and I'm looking to replace it with something where:

Every data item is an object which is (effectively) an instance of a class, which imposes a common structure including default values
Where possible, functions which set or get the data in a data item are taken out of the controller logic and attached to the data item class prototype

The problem I'm trying to solve by introducing this structure is, lots of messy and inconsistent 'model' style logic buried deep in 'controller' style functions, which has led to inconsistency, type errors, missing data errors, duplicated logic, etc.

Here's an example which uses the exact same approach I'm taking to defining and accessing instances (but the contents of data structure itself is simplified, since my question is about the way it's defined and accessed). I know that Javascript doesn't exactly have object 'classes' the way other languages do, and I've read about approximating them using prototypes, but I may be doing it wrong. In particular:

Do I need an init() function? Seems fine without one.
Is this a robust approach to the instance object accessing its own data? Can I rely on this within the attached function always being the instance's own data each time the function is called? Or should I be prepared to use call() or wrap calls in an anonymous function, or set it as a variable like that or self?
Is this a good way to give a class of objects default values? Note that this application already uses jQuery for other non-negotiable reasons, hence $.extend, and namespacing is already covered
I put the defaults object in the prototype so it's not redefined each time a new instance is created. Am I right in thinking this is a better practice than defining it within the function?
My actual application isn't about currencies, so please don't comment on the business logic. The code for setting the class is taken straight from my actual application draft, but I did swap the actual parameters and functions with simpler examples (if I hadn't, the explanation of the parameters and purpose of the functions would be longer than the rest of this question combined, and I'd need tonnes of non-relevant code to give a working example)

var dataItem = function(values){
  // Initiate new instance
  $.extend(this,this.defaults,values);
};

dataItem.prototype.defaults = {
  // Structure & defaults for each data item
  value: 0.0,
  currency: 'USD'
};

dataItem.prototype.formatCurrency = function(){
  // Simple example of a 'getter' function
  var formatted = '';
  switch(this.currency) {
    case 'GBP':
      formatted = '£';
    break;
    case 'USD':
    case 'CAD':
    case 'AUD':
      formatted = '$';
    break;
  }
  return formatted+this.value.toFixed(2)+' '+this.currency;
};

// Some simple usage examples

var expenses = new dataItem({
  value: 199.5,
  currency: 'GBP'
});

var canadaIncome = new dataItem({
  currency: 'CAD'
})

var taxes = new dataItem({
  value: 60
})

document.write( expenses.formatCurrency() + ' : ' + canadaIncome.formatCurrency() + ' : ' + taxes.formatCurrency() );
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.4.4/jquery.min.js"></script>

Naming Things

The class name dataItem doesn't communicate what it is, or how it is meant to be used:

  There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors. - Martin Fowler

What is a dataItem? From the code, it is a number value and a currency symbol. Perhaps CurrencyFormat might be more appropriate because what you are doing is formatting a number as currency.

Furthermore, naming conventions in JavaScript require that constructor functions should begin with a capital letter (DataItem vs dataItem). This naming convention is reflected in the native JavaScript API as well (String, Number, XMLHttpRequest, ...).

Principle of Single Responsibility

Being that you could format multiple numbers as the same currency, you might want to limit the instances that are available and use them to format any number, rather than keeping track of the number as an instance variable. This is the principle of Single Responsibility (do one thing, and do it well).

You can then provide an instance for each supported currency type, and a factory function that returns the proper formatter based on the currency name (e.g. "USD"):

function CurrencyFormat(symbol, name) {
    this.symbol = currencySymbol;
    this.name = currencyName;
}

CurrencyFormat.prototype = {
    name: null,
    symbol: null,

    constructor: CurrencyFormat,

    format: function(n, decimalPlaces) {
        decimalPlaces = typeof decimalPlaces == "number" ? decimalPlaces : 2;

        return this.symbol + n.toFixed(decimalPlaces) + " " + this.name;
    }
}

CurrencyFormat.AUD = new CurrencyFormat("$", "AUD");
CurrencyFormat.CAD = new CurrencyFormat("$", "CAD");
CurrencyFormat.GBP = new CurrencyFormat("£", "GBP");
CurrencyFormat.USD = new CurrencyFormat("$", "USD");

CurrencyFormat.getFormatter = function(currencyName) {
    if (CurrencyFormat[currencyName] && CurrencyFormat[currencyName] instanceof CurrencyFormat) {
        return CurrencyFormat[currencyName];
    }

    throw new Error("Currency format not implemented: " + currencyName);
};

Given the values you posted, this is how you would use the class:

var taxes = 60;
var expenses = 199.5;
var canadaIncome = 0;

console.log(CurrencyFormat.GBP.format(expenses));
console.log(CurrencyFormat.CAD.format(canadaIncome));
console.log(CurrencyFormat.USD.format(taxes));

If you know the currency name, you can use CurrencyFormat.getFormatter(...) to get the proper object:

// Get a formatter object by name:
var formatter = CurrencyFormat.getFormatter("USD");

// Throws an error because the currency name is not implemented:
var formatter = CurrencyFormat.getFormatter("XYZ");

This allows you to inject a currency formatter into other objects:

function ShoppingCartItem(price, currencyFormatter) {
    this.price = price;
    this.currencyFormatter = currencyFormatter;
}

ShoppingCartItem.prototype.formatPrice = function() {
    return this.currencyFormatter.format(this.price);
}

var item1 = new ShoppingCartItem(105.95, CurrencyFormat.getFormatter("USD"));
var item2 = new ShoppingCartItem(105.95, CurrencyFormat.GBP);

console.log(item1.formatPrice());
console.log(item2.formatPrice());

Removing unnecessary dependencies

There is no need to use jQuery.extend for just a couple of properties. This is an unnecessary dependency. For something as simple as a currency symbol and name, just pass those values in as constructor arguments. Passing in an object of key-value pairs is like hitting a thumb tack with a sledge hammer in this case.

Even if you needed to set a dozen properties by passing in an object of key-value pairs, I still wouldn't use jQuery.extend. It's not magic. It's just a for-in loop. You are better off writing half a dozen lines of code in order to remove a dependency on a large JavaScript library when this one class uses a fraction of what jQuery offers.


Use Promise to wait until DOM element exists I need to create a JavaScript Promise that will not resolve until a specific HTML element is loaded on the page.

I don't have any way of knowing when this element will be loaded, other than to simply poll the DOM for it.

It seems there should be a more concise way to accomplish this task.  I don't want anything that's "clever" to the point of being difficult to understand, but I'm open to any feedback on this pattern.

The code must be ES5 compatible for the most part.  Polyfills are probably ok, but it has to run on IE10+.

function getContainer() {
    return new Promise(function (resolve, reject) {
        waitForContainerElement(resolve);
    });
}

function waitForContainerElement(resolve) {
    var $configElement = $("#container");
    if ($configElement.length === 0) {
        setTimeout(waitForContainerElement.bind(this, resolve), 30);
    } else {
        resolve($configElement);
    }
}

Usage:

getContainer.then(function($container){
    ...
});

I would normally implement a max poll time, but didn't want that to cloud the issue here.

One idea would be to put the script tags at the end of the document's body - not in the head at all. It's a common trick in itself, often used to speed up load time, because it means no time is spent parsing scripts before moving on to the page's actual content. It also means that the scripts will have everything that's "before" them in the DOM ready for use.

Alternatively: If you're unwilling to move all the scripts, but still willing to simply wait for the document to report ready, there's no need for polling. See MDN's documentation for more. You may want to check document.readyState first, since attaching an event listener too late (after the document has loaded), is pointless: The event only fires once.

But wait! It appears you're already using jQuery, in which case all you have to do is:

$(function () {
  // code to run on document ready
});

That code can resolve a promise, but usually you'd just put that in your various scripts to make sure they only run once the document's ready (e.g. $(initWidget); where initWidget is whatever function kicks something off). It's how most jQuery scripts are written.


Parameterized Verilog shift register code I am a beginner in FPGAs, and I am studying Verilog HDL. Could you please check the quality of my code (a shift register)? Any comments are welcome.
The shift register serializes parallel from wr_data_i data to serial_data_o and has two variations of first serialized bit. It may be most significant bit or least significant bit, which is defined in parameters as TRUE or FALSE.
`timescale 1ns / 1ps

module shift_reg #
(
  parameter integer DATA_WIDTH   = 16,
  parameter integer DO_MSB_FIRST = "TRUE"
)
(
  input  wire                      clk_i,
  input  wire                      s_rst_n_i,
  input  wire                      enable,
  input  wire                      wr_enable,

  input  wire [DATA_WIDTH - 1 : 0] wr_data_i,

  output wire                      serial_data_o
);
  localparam integer MSB = DATA_WIDTH - 1;
  localparam integer LSB = 0;
  localparam integer XSB = ("TRUE" == DO_MSB_FIRST) ? MSB : LSB;

  reg [DATA_WIDTH - 1 : 0] parallel_data;

  assign serial_data_o = (1'h1 == enable) ? parallel_data[XSB] : 1'hz;

  always @ (posedge clk_i)
    begin
      if (1'h0 == s_rst_n_i)
        begin
          parallel_data <= 'h0;
        end
      else if (1'h1 == wr_enable)
        begin
          parallel_data <= wr_data_i;
        end
      else if (1'h1 == enable)
        begin
          if ("TRUE" == DO_MSB_FIRST)
            begin
              parallel_data <= {parallel_data[MSB - 1 : 0], 1'h0};
            end
          else
            begin
              parallel_data <= {1'h0, parallel_data[MSB: 1]};
            end
        end
    end

endmodule

I don't see any problems with the code functionally, and the layout follows good practices for the most part.  You chose meaningful names for the signals and parameters, and the parameters make your design scalable to different data widths.  It also follows good practices using nonblocking assignments for the sequential logic.  This is excellent for a beginner.
You should use a sized constant for the data reset value ('h0) in order to avoid synthesis lint warnings from some tools.  I prefer the replicated concatenation style for this: {DATA_WIDTH{1'h0}}.
I think it is more conventional to omit the 1'h1 == in comparisons to 1 for 1-bit signals.  It makes the code a little cleaner, and all the tools do the right thing.  For example: (wr_enable).
Similarly for comparisons to 0, omit the 1'h0 ==, and use either ! or ~ (they are equivalent for 1-bit signals): (!s_rst_n_i)
You did a fantastic job of using a consistent layout style.  The following comments are my preferences, but you might consider using them as well.
I use 4-space indentation because I think it is easier to see the different levels of your code's logic.
I prefer to place the begin and end keywords on the same line as the if/else keywords in order to reduce vertical space and get more code on one screen.  It also makes the branches of your code more evident.
Here is the code with the above suggestions:
`timescale 1ns / 1ps

module shift_reg #
(
    parameter integer DATA_WIDTH   = 16,
    parameter integer DO_MSB_FIRST = "TRUE"
)
(
    input  wire                      clk_i,
    input  wire                      s_rst_n_i,
    input  wire                      enable,
    input  wire                      wr_enable,

    input  wire [DATA_WIDTH - 1 : 0] wr_data_i,

    output wire                      serial_data_o
);
    localparam integer MSB = DATA_WIDTH - 1;
    localparam integer LSB = 0;
    localparam integer XSB = ("TRUE" == DO_MSB_FIRST) ? MSB : LSB;

    reg [DATA_WIDTH - 1 : 0] parallel_data;

    assign serial_data_o = (enable) ? parallel_data[XSB] : 1'hz;

    always @ (posedge clk_i) begin
        if (!s_rst_n_i) begin
            parallel_data <= {DATA_WIDTH{1'h0}};
        end else if (wr_enable) begin
            parallel_data <= wr_data_i;
        end else if (enable) begin
            if ("TRUE" == DO_MSB_FIRST) begin
                parallel_data <= {parallel_data[MSB - 1 : 0], 1'h0};
            end else begin
                parallel_data <= {1'h0, parallel_data[MSB : 1]};
            end
        end
    end
endmodule


Deeply extract all used symbols from a hash of nested symbols in an array I have a nested hash of symbols like this:

{
  a: {
    b: :c,
    d: {
      e: :f
    }
  },
  g: :h
}

I want to build an array that contains all symbols used in the hash, both keys and values, in any order. For the example above:

[:a, :b, :c, :d, :e, :f, :g, :h]

Is there any simple, fast and ruby-friendly way to do this?

I'm doing this with a recursive function that sums hash.keys with hash.values, and finally applies flatten to the result.

def all_keys(hash)
  hash.keys + hash.values.map { |e| e.is_a?(Hash) ? all_keys(e) : e }
end

Some notes:

The flattening should be performed where the non-desired nesting is being introduced, not later. Use flat_map instead of map:
Why e for the value name instead of v?

I'd write:

def all_keys(hash)
  hash.keys + hash.values.flat_map { |v| v.is_a?(Hash) ? all_keys(v) : [v] }
end

Another way to do it, slightly shorter, is to iterate directly the pairs. Pick the one which is more declarative to you:

def all_keys(hash)
  hash.flat_map { |k, v| [k] + (v.is_a?(Hash) ? all_keys(v) : [v]) }
end


Averaging nearby points in an array The following code takes in an point array and removes all of the nearby points whilst averaging them based on the conditions past in.

The variable _nCornerTolerance is an int that is calculated prior in the class. Typically it is around 5;

private Point[] AverageNearbyPoints(Point[] points, bool averageLeft, bool averageHigh)
{
    List<Point> plAveragedPoints = new List<Point>();
    for (int pi = 0, pc = points.Length; pi < pc; ++pi)
    {
        Point[] paNearbyPoints = points.Where(p => (Math.Abs(p.X - points[pi].X) <= _nCornerTolerance)
                                                && (Math.Abs(p.Y - points[pi].Y) <= _nCornerTolerance))
                                        .ToArray();
        if (paNearbyPoints.Length > 1)
        {
            int nX = averageLeft ? (int)Math.Floor(paNearbyPoints.Sum(p => p.X) / (float)paNearbyPoints.Length)
                                    : (int)Math.Ceiling(paNearbyPoints.Sum(p => p.X) / (float)paNearbyPoints.Length);

            int nY = averageHigh ? (int)Math.Floor(paNearbyPoints.Sum(p => p.Y) / (float)paNearbyPoints.Length)
                                    : (int)Math.Ceiling(paNearbyPoints.Sum(p => p.Y) / (float)paNearbyPoints.Length);

            if (!plAveragedPoints.Any(p => p.X == nX && p.Y == nY))
            {
                plAveragedPoints.Add(new Point(nX, nY));
            }
        }
        else
        {
            if (!plAveragedPoints.Any(p => p.X == points[pi].X && p.Y == points[pi].Y))
            {
                plAveragedPoints.Add(points[pi]);
            }
        }
    }

    return plAveragedPoints.ToArray();
}

Is there anyway I can rewrite the int nX = ... and int nY = ... parts better so I don't need the conditional?

A full review of this code would also be helpful, although the main part I am asking about is the above.

Naming

plAveragedPoints
paNearbyPoints

this variables would be more obvious if you wouldn't use this strange kind of hungarian notation. I figured out the pl means point list and pa point array, but if you need to read this fast you just can't because your brain will try to decypher what pl and pa means.

Does it really matter wether it is a List or an Array ?

       if (!plAveragedPoints.Any(p => p.X == nX && p.Y == nY))
        {
            plAveragedPoints.Add(new Point(nX, nY));
        }

and

       if (!plAveragedPoints.Any(p => p.X == points[pi].X && p.Y == points[pi].Y))
        {
            plAveragedPoints.Add(points[pi]);
        }

made me think that maybe a HashSet<Point> would be the better datastructure instead of a List<Point. You could simply call the Add() method and forget about the result of it.

Instead of using the tenary expression, @Caridoc had shown a different implementation which was a good start.

I would suggest to add another method which takes two Func<double,double> which are determined before calling that overloaded method like so

    private Func<double, double> CreateDesiredFunc(bool useFloor)
    {
        if (useFloor)
        {
            return Math.Floor;
        }
        return Math.Ceiling;
    }

Edit: Like @RickDavin pointed out in the comments this can be cleaned a little bit more by using more idiomatic names for the looping index variable and for the coordinate variables. In addition you should/could use the var type where it is clear from the right hand side of an assignment what type it is.

This boils down to the following

    private Point[] AverageNearbyPoints(Point[] points, bool averageLeft, bool averageHigh)
    {
        return AverageNearbyPoints(points, CreateDesiredFunc(averageLeft), CreateDesiredFunc(averageHigh));
    }

    private Point[] AverageNearbyPoints(Point[] points, Func<double, double> averageLeft, Func<double, double> averageHigh)
    {
        var averagedPoints = new HashSet<Point>();
        int numberOfPoints = points.Length;
        for (int i = 0; i < numberOfPoints ; ++i)
        {
            var nearbyPoints = points.Where(p => (Math.Abs(p.X - points[i].X) <= _nCornerTolerance)
                                              && (Math.Abs(p.Y - points[i].Y) <= _nCornerTolerance))
                                            .ToArray();
            var point = points[pi];

            if (nearbyPoints.Length > 1)
            {
                int x = (int)averageLeft(nearbyPoints.Sum(p => p.X) / (float)nearbyPoints.Length);

                int y = (int)averageHigh(nearbyPoints.Sum(p => p.Y) / (float)nearbyPoints.Length);

                point = new Point(x, y);

            }

            averagedPoints.Add(point);
        }

        return averagedPoints.ToArray();
    }


Project Euler #1 Sum of all the multiples of 3 or 5 below 1000 If we list all the natural numbers below 10 that are multiples of 3 or
  5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

  Find the sum of all the multiples of 3 or 5 below 1000.

My solution:

#include <stdio.h>
#define TOP_LIMIT 1000

float sum_of_series(float start_from,float position,float difference)
{
    return (position/2) *
        ( 2 * start_from + (position-1) * difference);
}

int find_last_multiple(int limit,int multiplier){
    return limit - (limit % multiplier);
}

void main(void){

    float last_position_3 =
        find_last_multiple( TOP_LIMIT-1 , 3 ) / 3;

    float last_position_5 =
        find_last_multiple( TOP_LIMIT-1 , 5 ) / 5;

    float last_position_15 =
        find_last_multiple( TOP_LIMIT-1 , 15 ) / 15;

    float sum_of_series_3 = sum_of_series(3,last_position_3,3);
    float sum_of_series_5 = sum_of_series(5,last_position_5,5);
    float sum_of_series_15 = sum_of_series(15,last_position_15,15);

    float answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;

    printf("sum of all the multiples of 3 or 5 below 1000\n");
    printf("answer = %f\n",answer);

}

I compiled it with: gcc (GCC) 4.8.3 20140624 (Red Hat 4.8.3-1)

In general, your algorithm/solution is clever. It is an \$O(1)\$ solution which I like, when most other solutions would be an \$O(n)\$ and do a modulo on 3 and 5. The trick for subtracting the double-count is something that should have a clear comment, including the reason why.

The find_last_multiple is also a neat solution. No issues with that, and it is simple enough to not require a comment.

Unfortunately the sum_of_series has some problems.... it should be commented, for a start... the logic is far from obvious.... I have not figured it out... yet.

Also, at this point it becomes float based calculations, and that threw me for a second. I immediately started thinking int-based math because the code has int constants, and it does int values in the find_last_multiple but it then does implicit casts to float. Very confusing.

Finally, it makes the assumption that that the series starts from 3, 5, or 15, but the question description starts from somewhere else.... I suggest you discard the starts_from parameter, and simply use the difference instead.

So, using float-based logic, and returning a float based solution is unexpected.... and I would expect there to be some comment as to why the sum of integers in a series is a float.

Finally, your sum_of_series should represent the standard formula for the sum-of-a-series (see the alternate form in wikipedia):

$$
\frac{n}{2}(2a + (n - 1)d)
$$

where n is the number of terms in the series, a is the start value, and d is the difference.

That can be simplified by setting a to be 0 (eliminating the 2a term), and for int math by doing:

$$
\frac{n(n - 1)}{2}d
$$

Mathematically, any multiple of an even number is always going to be even. Now, either \$n\$ or \$n - 1\$ is even.... so, \$n(n-1)\$ will be even, and safe to divide by 2.

I would also start from 0. Using integer math, the problem is simpler:

int sum_of_series(int limit, int difference)
{
    // from: http://en.wikipedia.org/wiki/Arithmetic_progression
    // formula for calculating the sum of a progression from 0 to a 'limit'
    // in steps of 'difference'. e.g. limit 10, difference 2 adds 0, 2, 4, 6, 8, 10 = 30
    int n = 1 + limit / difference; // integer math gives number of terms including term 0
    return ((n * (n - 1)) / 2) * difference;
}

So, you can use the above safely as:

int sum = sum_of_series(999, 15);

which will give the result 15 * (67 * 66) / 2 or  33165

Note that the problem statement requires the sum of values less than 1000, and the sum_of_series formula calculates inclusive of the limit, so we use the limit of 999, not 1000

Additionally, using the int-based logic, there is no need for there to be the find-limit method at all. This reduces your main method to:

int main(void){

    int sum_of_series_3 = sum_of_series(999,3);
    int sum_of_series_5 = sum_of_series(999,5);
    int sum_of_series_15 = sum_of_series(999,15);

    int answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;

    printf("sum of all the multiples of 3 or 5 below 1000\n");
    printf("answer = %d\n",answer);

    return 0;

}

I put the above together in a working Ideone


CSES - Number Spiral - Java TLE My java code for CSES Introductory problem Number Spiral gives TLE for large inputs, like
Input :
100000
170550340 943050741
121998376 943430501
689913499 770079066
586095107 933655238 …
(First line/number being the number of inputs)
My code is as below:
import java.util.*;
public class numberSpiral {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long testN = scanner.nextLong();
        long r=0,c=0;
        while(testN-- > 0){
            r = scanner.nextLong();
            c = scanner.nextLong();
            if (c > r) {
                if (c % 2 == 0) {
                    System.out.println(((c - 1) * (c - 1)) + 1 + (r - 1));
                } else
                    System.out.println(((c) * (c)) - (r - 1));
            } else {
                if(r % 2 == 0){
                    System.out.println(((r) * (r)) - (c - 1));
                } else
                    System.out.println(((r - 1) * (r - 1)) + 1 + (c - 1));
            }
        }
    }
}

It works for small inputs. I can't figure out how to optimize it better to reduce time. Time limit is: 1.00 s

I assume you refer to https://cses.fi/problemset/task/1071/ .
Your Algorithm itself is fine as far is i can tell.
The Problem is the large amount of inputs that need to need to be read(Testcases=100000), which Scanner cant provide within the 1s time limit.
A BufferedReader should offer the performance needed for this.(See https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ for more information).
The same might apply to System.out.println in which case it would be better to use a BufferedWriter


Selecting names with two consecutive, same letters I've a list of names that I'd like to iterate over and extract from it those names that have two letters that are the same right next to each other (i.e. Bill, Terry, Debby, Aaron, etc.).

The below code I have accomplishes this task, however I was wondering if there was a more efficient or line-friendly method of approaching this problem.

I started thinking about a solution involving LINQ's Where<> method, but then I wasn't sure how to use both a string variable and an int index variable inside a lambda expression.

Also, does there exist a way to accomplish this task in faster than O(n^2) time?

public static List<string> DoubleLetters(string[] array)
{
    List<string> doubleLetter = new List<string>();
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array[i].Length - 1; j++)
        {
            if (char.ToLower(array[i][j]) == char.ToLower(array[i][j + 1]))
            {
                doubleLetter.Add(array[i]);
                break;
            }
        }
    }
    return doubleLetter;
}

The outer for loop can be replaced with a foreach loop: foreach (var name in names). It removes the need for two counter variables, and simplifies indexing of the array, making the code easier to read.
This method would be more flexible if it accepted a single string and returned a boolean: bool HasRepeatingLetters(string str). That allows you to use it for single names as well as for multiple names.
For multiple names, the above method can easily be combined with Linq: var matchingNames = names.Where(name => HasRepeatingLetters(name)).ToArray() (you can remove the ToArray (or ToList) call if you want lazy evaluation). In this case, you don't even need an anonymous function, because the signature of HasRepeatingLetters already matches what Where requires: names.Where(HasRepeatingLetters).
Keep in mind that ToLower is culture-dependent (not all languages use the same upper/lowercase conversion rules). You may want to give your function an extra (optional) CultureInfo argument to control its behavior.
Performance of your function should be O(n), not O(n^2). Passing in twice as many strings, or strings that are twice as long, requires twice as much work, not four times as much. It would only be O(n^2) if, for example, you compared each string against every other string.
Calling ToLower on the given string would simplify your code, and it should be a bit faster too for names without repeating characters. You could also keep your for loop, but store the previous lower-cased character as you go, so you don't need to convert it to lower-case twice. That would make the code a little more complicated, so it's probably not worth the hassle. Of course, if performance is important, you should actually measure it.


Ruby: possible Poker holds for a hand of length n Hello everyone and thanks in advance for taking the time to read my post!!
In the process of learning Ruby, I'm writing a video poker machine that analyzes hands represented by arrays of Cards, like so: [ card, card, card, card, card ]
You may know that in draw poker, one can hold certain cards and toss the rest to the dealer, to be replaced by drawing new cards from the deck in the hopes of improving one's hand (hence the name). It's natural to figure that holds would be represented by an array of boolean values. To wit: [ true, true, false, false, false ] would mean holding the first two cards in a five-card hand and discarding the rest. What I'm trying to write is a method that will give me an array of all possible holds (an array of arrays) for a given hand size.
I've found that Ruby is terrific (though a bit slow) for permutations and combinations, i.e., all possible unique hands from a 52-card deck. All I have to do for that is call deck.combination( hand_size ).to_a. But unfortunately neither .permutation nor .combination is really giving me what I need for a method to produce possible holds.
High school math (which I'm terrible at, by the way) tells me that when determining possible unique n-combinations of two possible values, the size of the universe of all possible n-combinations will be two to the power of n - meaning there are 32 possible holds for a five-card poker hand.
After slaughtering a snow-white bull for the gods at midnight under a full moon, I've come up with the following solution using binary numbers. This method loops through a range from 0...2 ** hand_size, turns each element of the range into a binary number string with a hand_size number of leading zeroes using .rjust, then .maps each character in the string to an array of hand_size elements using a conditional and ternary; if the character is "1" it maps a true to the array, otherwise the character is a "0" and it maps false to the array.
def possible_holds( hand_size )
   result = []
   for each_hold in 0...2 ** hand_size do
      as_binary = each_hold.to_s( 2 ).rjust( hand_size, "0" )
      result << ( 0...hand_size ).to_a.map{ | card | as_binary[ card ] == "1" ? true : false }
   end
   result
end

This clunky little method actually works very well, but... it just doesn't seem very rubinic. I would love to hear clever suggestions as to how to improve it. I have this nagging feeling that this can all be done with a neat, simple method/enumerable or two... but no matter how many virgins I sacrifice I just can't seem to come up with anything better.
Thanks in advance for your help and happy coding!!

Here's a demonstration of how you might solve this problem the Ruby way:
SUITS = %w[ H D C S ]
FACES = %w[ 2 3 4 5 6 7 8 9 T J Q K A ]

CARDS = SUITS.flat_map { |s| FACES.map { |f| "#{f}#{s}" } }

def holds(hand)
  hand.length.times.flat_map do |n|
    hand.combination(n).to_a
  end << hand
end

holds(CARDS.shuffle.take(5))

Where you get results like this:
[[],
 ["AD"],
 ["5H"],
 ["QS"],
 ["4H"],
 ["5D"],
 ["AD", "5H"],
 ["AD", "QS"],
 ["AD", "4H"],
 ["AD", "5D"],
 ["5H", "QS"],
 ["5H", "4H"],
 ["5H", "5D"],
 ["QS", "4H"],
 ["QS", "5D"],
 ["4H", "5D"],
 ["AD", "5H", "QS"],
 ["AD", "5H", "4H"],
 ["AD", "5H", "5D"],
 ["AD", "QS", "4H"],
 ["AD", "QS", "5D"],
 ["AD", "4H", "5D"],
 ["5H", "QS", "4H"],
 ["5H", "QS", "5D"],
 ["5H", "4H", "5D"],
 ["QS", "4H", "5D"],
 ["AD", "5H", "QS", "4H"],
 ["AD", "5H", "QS", "5D"],
 ["AD", "5H", "4H", "5D"],
 ["AD", "QS", "4H", "5D"],
 ["5H", "QS", "4H", "5D"],
 ["AD", "5H", "QS", "4H", "5D"]]

Personally I'd hold the pair of 5s and the Ace.
For educational purposes here's a more Ruby-esque form of your original code:
def possible_holds(hand_size)
  (2 ** hand_size).times.map do |n|
    n.to_s(2).rjust(hand_size, '0').chars.map { |c| c == '1' }
  end
end

It's kind of messy due to the binary string to boolean conversion.

Tip: Try to avoid "casting a boolean to a boolean" as in patterns like x ? true : false or if x; true; else; false like you had in your code. That reduces down to just x. The x == '1' test already returns a true or false value. There is no maybe or kind_of response.


Optimized Int Reader I am new in Golang, and decided to create a function that could cater to my needs of reading an integer from stdin. I need the function to be as efficient and fast as possible.

package main
import(
    "fmt"
    "bufio"
    "os"
    "strconv"
)

type NoIntRead int

func (err *NoIntRead) Error() string{
    return fmt.Sprintf("No integer was read!")
}

var(
    inputreader = bufio.NewReader(os.Stdin)
    mybyteslice []byte = make([]byte,11)
)
func ReadInt() (int,error){
    var mybyte byte
    var myint int
    var err error
    var size int = 0
    for{
        mybyte,err = inputreader.ReadByte()
        if mybyte == '\n' || mybyte == ' ' || err != nil{
            if size == 0{
                myerr := NoIntRead(1)
                return 0,&myerr
            }
            mystring := string(mybyteslice[:size])
            myint,err = strconv.Atoi(mystring)
            if err != nil{
                myerr := NoIntRead(1)
                return 0, &myerr
            }
            return myint,nil
        }
        mybyteslice[size] = mybyte
        size++
    }
}
func main(){
    var myint int
    var err error
    for{
        myint,err = ReadInt()
        if err != nil{
            fmt.Println(err)
            break;
        }
        fmt.Println(myint)
    }
}

Is there a more efficient way to read integers from stdin? If yes, I would be more than grateful if someone could point me into the right direction.

As suggested by rolfl you should do Benchmarks on different approaches. This is the only way to tell, if you actually improved on your function.

There are a few points you can improve (or check if they actually improve your case) that I can share from experience:

1) currently you are converting the bytes to string and then you are creating an integer from them. Since you already know there will be integers, use the binary package to do the transformation from bytes directly to integer:

order := binary.LittleEndian
myint := int(order.Uint64(mybyteslice))

Note: this is about 10 times faster than any string/scan operation you can do.

2) Have you checked ReadBytes function of the inputreader? That could probably eliminate your for loop and thus also eliminate the memory allocations you have each time you add an item to mybyteslice.

3) This probably should be the first point because it is the most important: check out the pprof tool to investigate your code. For this you definitly need to write Benchmarks or generate load for your code another way. Then check what takes time in your code and minimize your allocations. Good places to start with pprof are this video and the very good article Debugging performance issues in go making a lot of suggestions.


Is it a good style to run external commands in Python? I have lots of external shell commands to run.

So I gave every command a name and then run it.

tar_report_cmd = 'zip -r  {0} {1} '%(report_file, _export_dir)
exec_proc(tar_report_cmd)
mv_report_cmd = "mv {0} {1}".format(report_file,report_dir)
exec_proc(mv_report_cmd)

But it looks sort of redundant and not beautiful.

Is there any better practice to replace my way?

def exec_proc(cmd_str):
    results = os.popen(cmd_str).read()
    return results

No, it is a security risk, and furthermore, os.popen() has been deprecated since Python 2.6.  The replacement is to use the subprocess module.

The security risk is that os.popen() expects its command as a string.  That means that the command will be interpreted by a shell to split it up into the command and its arguments.  If report_file, report_dir, or _export_dir contain any spaces or characters with a special meaning to the shell, horrible unexpected things can happen, including arbitrary command execution.


Calculate probability of dice total I am working on a project to get dice probability that requires 4 decimals places. My code works great, until the dice become huge (as I use in the example below). I am wondering if there is a way to make the process less laborious.
I should specify that I do already know that the choices list ending up so large is the performance issue.  I am looking for ways to improve performance.
An explanation of my code is:

We have \$n\$ dice each with \$f\$ faces and a target \$t\$. I want to know all the combinations of these dice to total \$t\$.
When: \$n = 2\$, \$f = 6\$ and \$t = 10\$, the following are the possible combinations:

4, 6
5, 5
6, 4

meaning poss_combinations returns \$3\$.

from itertools import product

dice = 10
faces = 10
number = 50

def poss_combinations(dice, faces, number):
    choices = list(product(range(1, faces+1), repeat=dice))
    count = 0
    for i in choices:
        if sum(i) == number:
            count += 1
    return count

answer = poss_combinations(dice, faces, number) / float(faces**dice)

return round(answer,4)

import

why import product within your method, and not in the module scope?

instantiation

There is just no reason to instantiate the list in

choices = list(product(range(1, faces+1), repeat=dice))

when you just iterate over it.

As noted by @JordanSinger, this takes a huge toll on memory, while using it as an iterable suffices

numpy alternative

a = sum(
    np.meshgrid(
        *(np.arange(1, faces + 1, dtype="uint8") for _ in range(dice)),
        copy=False
    )
)
(a == number).sum()

but for larger number of dice and faces this runs into MemoryError too

alternative

The integer value of True is 1. So instead of keeping a counter, and incrementing it each time there is a match, you can do:

def poss_combinations(dice, faces, number):
    choices = product(range(1, faces+1), repeat=dice)
    return sum(sum(roll) == number for roll in choices)

But even this will take ages for 10**10 combinations. Better would be to use a analytical formula like this one

alternative 2

A first alternative, is instead of taking the product, using itertools.combination_with_replacement to get all the combinations of dice rolls. For 10 10-faced dice, this is sum(1 for _ in combinations_with_replacement(range(10), 10)) or 92378. This is a much better number to work with that 10**10

The next step is to check which combinations combine to numbers, and then calculate how much of these combinations are possible link

from collections import Counter
from functools import reduce
from math import factorial
from operator import mul

def product_math(iterable):
    return reduce(mul, iterable, 1)

def combination_permutations(combination):
    c = Counter(combination)
    return factorial(sum(c.values())) / product_math(
        factorial(i) for i in c.values()
    )

calculates the number of possible permutations of a combination

def poss_comb_permutations(dice, faces, numbers):
    return sum(
        combination_permutations(combination)
        for combination in combinations_with_replacement(
            range(1, faces + 1), dice
        )
        if sum(combination) == numbers
    )

Then uses this to calculate the number of matching dice rolls.

All 3 methods arrive at the same result for

dice = 7
faces = 7
number = 20


Bogosort vs bogobogosort A question on Stack Overflow had me look up the article on bogosort on Wikipedia.

There they describe the bogosort algorithm and the bogobogosort algorithm. They say, about this last algorithm, that:

  bogobogosort was designed not to succeed before the heat death of the universe on any sizable list.

I wrote a program to compare these 2 algorithms and got somewhat conflicting results: bogosort performs worse than bogobogosort for arrays up to 12 elements.

I am more inclined to believe my code is wrong than Wikipedia. Of course it can be that 12 is not a sizable enough list and the difference starts being noticeable with larger arrays.

#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quit(const char *msg) __attribute__((noreturn));
void datainit(int *data, size_t n);
void acopy(int *dst, const int *src, size_t n);
unsigned long bogosort(int *data, size_t n);
unsigned long bogobogosort(int *data, size_t n);
double timedelta(const struct timespec *b, const struct timespec *a);
void shuffle(int *data, size_t n);
int sorted(int *data, size_t n);
int randto(int n);

int main(int argc, char **argv) {
    int data[20], data2[20];
    unsigned long n;
    unsigned long s[2];
    struct timespec t[3];
    char *err;

    if (argc != 2) quit("Specify number of elements.");
    errno = 0;
    n = strtoul(argv[1], &err, 10);
    if (errno || n < 2 || n > 20) quit("number between 2 and 20");

    srand((unsigned)time(0));
    datainit(data2, n);

    clock_gettime(CLOCK_MONOTONIC, t + 0);
    acopy(data, data2, n);
    s[0] = bogosort(data, n);
    clock_gettime(CLOCK_MONOTONIC, t + 1);
    acopy(data, data2, n);
    s[1] = bogobogosort(data, n);
    clock_gettime(CLOCK_MONOTONIC, t + 2);

    printf("    bogosort shuffled %12lu cards in %f seconds.\n", s[0], timedelta(t + 1, t + 0));
    printf("bogobogosort shuffled %12lu cards in %f seconds.\n", s[1], timedelta(t + 2, t + 1));

    return 0;
}

void quit(const char *msg) {
    if (msg) fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

void datainit(int *data, size_t n) {
    for (size_t i = 0; i < n; i++) data[i] = (int)i;
    shuffle(data, n);
}

void acopy(int *dst, const int *src, size_t n) {
    for (size_t i = 0; i < n; i++) dst[i] = src[i];
}

unsigned long bogosort(int *data, size_t n) {
    unsigned long c = 0;
    while (!sorted(data, n)) {
        c += n;
        shuffle(data, n);
    }
    return c;
}

unsigned long bogobogosort(int *data, size_t n) {
    unsigned long c = 0;
    for (size_t b = 2; b <= n; b++) {
        while (!sorted(data, b)) {
            c += b;
            shuffle(data, b);
            b = 2;
        }
    }
    return c;
}

double timedelta(const struct timespec *b, const struct timespec *a) {
    double aa = a->tv_sec + (a->tv_nsec / 1000000000.0);
    double bb = b->tv_sec + (b->tv_nsec / 1000000000.0);
    return bb - aa;
}

void shuffle(int *data, size_t n) {
    if (n == 1) return;
    int p = randto((int)n);
    int tmp = data[p];
    data[p] = data[n - 1];
    data[n - 1] = tmp;
    shuffle(data, n - 1);
}

int sorted(int *data, size_t n) {
    int r = 1;
    for (size_t i = 1; i < n; i++) {
        if (data[i - 1] > data[i]) {
            r = 0;
            break;
        }
    }
    return r;
}

int randto(int n) {
    int mx = (RAND_MAX / n) * n;
    int p;
    do p = rand(); while (p >= mx);
    return p % n;
}

And this is a possible result for an array with 10 elements

% ./a.out 10
    bogosort shuffled     13816640 cards in 0.400548 seconds.
bogobogosort shuffled      1102233 cards in 0.027740 seconds.

So, unexpectedly bogosort shuffled more cards than bogobogosort and took more time doing it.

Is my bogosort() wrongly implemented?
Is my bogobogosort() wrongly implemented?
Is my shuffle() wrongly implemented? (but it would influence both functions)
Is my randto() wrongly implemented? I believe there's no bias.

Not bogobogosort
The way you implemented your bogobogosort, it is actually faster than bogosort because of a few reasons:

After you successfully bogosort k elements, you immediately check whether k+1 elements are sorted.  This means that if on a previous shuffle, you happened to shuffle m elements all in order, then after you sort the first two elements you will immediately reach m.
For example, suppose you reach 5 cards and then fail.  You shuffle 5 cards and then start over at 2.  If those 5 cards happen to be in sorted order, you will immediately reach 6 as soon as you put the first 2 cards in order.

Because of point #1, your bogobogosort is actually faster than the bogosort because it only needs to sort n-1 cards instead of n.  After it sorts n-1 cards, it checks the order of n cards and may fail.  But in failing, it reshuffles n cards so that each time it sorts n-1 cards it has a 1/n chance of eventually succeeding.  So the total number of cards shuffled is on the order of (n-1) * (n-1)! * n which simplifies to (n-1) * n!, compared to the bogosort which shuffles n * n! cards.
I believe that the same principle applies at each step, so the time is even less than (n-1) * n!.  I'm not sure of the exact math but from running your program it appears that the bogobogosort runs in approximately the same time as the bogosort with one fewer cards.  I.e. Your_bogobogosort(n) = bogosort(n-1).

A proper bogobogosort
I rewrote your bogobogosort function to be like this:
unsigned long bogobogosort(int *data, size_t n) {
    unsigned long c = 0;
    size_t b = 2;

    while (1) {
        if (sorted(data, b)) {
            if (b == n)
                break;
            b++;
        } else {
            b = 2;
        }
        c += b;
        shuffle(data, b);
    }
    return c;
}

The key difference here is that after each success where it increments b, it reshuffles the deck to prevent point #1 above from happening..  With this change, I get output like this:
% ./a.out 6
    bogosort shuffled         1044 cards in 0.000013 seconds.
bogobogosort shuffled     54464568 cards in 0.500339 seconds.


Shuffling a list of track indices This question has a follow-up: Follow up to Shuffling a list of track indices

I have a bunch of paths in an ArrayList<String> and when a user has activated the shuffle button, I want to have a random order to play all of them. This class should help me get every index once. The methods getNext() and getPrevious() should help me to get the last / next song when the user clicks on either the next or previous button.

public class ShuffleGenerator {

    private ArrayList<Integer> indexList;
    private int currentIndex;

    public ShuffleGenerator(){
        indexList = new ArrayList<Integer>();
        currentIndex = 0;
    }

    public void initalize( int seed, int size ){

        if( !indexList.isEmpty() ){
            indexList.clear();
        }

        if( size > 0 ){

            //fill it with indices
            ArrayList<Integer> indices = new ArrayList<Integer>();
            for( int i = 0; i < size; i++ ){
                indices.add(i);
            }

            Random rnd = new Random(seed);

            do{

                int index = rnd.nextInt(indices.size());
                indexList.add( indices.get(index) );
                indices.remove(index);

            }while( indices.size() > 0 );

        }

    }
    /**
     * Get the next index.
     * @return -1 if failed otherweise the index.
     */
    public int getNext(){

        //if currentIndex is invalid
        if( currentIndex+1 >= indexList.size() || indexList.isEmpty() ){
            return -1;
        }

        currentIndex++;
        return indexList.get(currentIndex);
    }

    /**
     * Get the previous index.
     * @return -1 if failed otherwise the index.
     */
    public int getPrevious(){

        //if currentIndex is invalid
        if( currentIndex-1 < 0 || indexList.isEmpty() ){
            return -1;
        }

        //decrement the current index so we can get the previous one
        currentIndex--;

        return indexList.get(currentIndex);
    }

}

I tested it twice and it seems like I get every index from 0 to size-1 in a random order. But is it really giving me every index? I might have made a mistake and just not noticed yet. And is there anything to improve?

I would remove the:

if( size > 0 )

and replace the

do {...} while

with a

while {...}

to simplify the structure of the code.

You can also redesign your algorithm to simplify it further. You can use an Array instead of ArrayList and use the following shuffle algorithm which avoids the use of a supplementary array. Here is the complete code:

import java.util.Random;

public class ShuffleGenerator {
    private int indices[];
    private int nextIndex;

    ShuffleGenerator(int size) {
        indices = new int[size];
        nextIndex = 0;
        for( int i = 0; i < size; i++ ){
            indices[i]=i;
        }
    }

    public void shuffle(Random rnd){
        for( int i = 0; i < indices.length; i++){
            // place a random element j>=i into position i
            int j = i + rnd.nextInt(indices.length-i);
            // swap i and j
            int c = indices[i];
            indices[i] = indices[j];
            indices[j] = c;
        }
    }

    /**
     * Get the next index.
     * @return -1 if at the end of the sequence.
     */
    public int getNext(){
        if( nextIndex >= indices.length){
            return -1;
        }
        return indices[nextIndex++];
    }

    /**
     * Get the previous index.
     * @return -1 if at the start of the sequence.
     */
    public int getPrevious(){
        if( nextIndex <= 0){
            return -1;
        }
        return indices[--nextIndex];
    }
}

BTW I think it makes more sense to pass a Random object instead of a seed. How do you choose the seed to pass to the function?

added thanks to @Pimgd I noticed that there was a problem in your code: the first call to getNext() should return the first element of the sequence not the second...

Actually the interface getNext,getPrevious is not very good in my opinion (image how you would use it). I think it would be best to have getCurrent, next, prev where next and prev return void. Or you could simply define length and at methods and remove the cursor from the class.