Highlight a pattern found I made a small web application with a search box. I wanted to highlight the words found in the search.

foreach my $article (@{$search_articles}) {
    my @result;

    foreach my $word (split(' ', $article->{content})) {
        if ( $word =~ params->{search} ) {
            push(@result,
                '' . $word . '');
        }
        else {
            push(@result, $word);
        }
    }

    $article->{content} = join(' ', @result);
}

It's a little wordy.  It is certainly possible to make cleaner, and I'd like to have your opinion.

Assuming that your search input is plain characters (i.e., no <, >, and likes), this is still problematic as can ruin your HTML code. Let's say I search for "border" in a page that contains
, or "class" in virtually any page written in the past 5 years,... IMO, this stuff is better done using a DOM parser and then searching just plain text.

Now, to comment the search itself... Let us assume that the word from your search box is contained in the variable $search. I think this is better done like this:

foreach my $article (@{$search_articles}) {
    $article->{content} =~ s/\Q$word\E/$&<\/span>/g
}


Top users under age 30, sorted by age, with rank In the pursuit of SQL enlightenment, I wrote a quick SEDE query to display Rep, Age and Overall Rank.
Sorted by Age, then Rank (Which is generated by Rep).

SELECT TOP 150
ROW_NUMBER() OVER (ORDER BY Users.Reputation DESC) AS Rank,
  Users.Id as [User Link],
  Users.Age,
  Users.Reputation as Rep
FROM Users
WHERE Users.Age IS NOT NULL AND Users.Reputation > 150 AND Users.Age <= 30
ORDER BY Users.Age ASC, Rank ASC;

I attempted formatting, but it feels wrong, and my (possibly) overly long WHERE statement seems incorrectly formatted as well.

What is a more optimal way to write this, if one does exist?

I've had parameters mentioned as an idea on improvement (age range and selection limitation).

A few things, some nitpicks, some UX, some probably-bugs. What Lyle's Mug has already stated is also part of my answer, but first things first:

UX

This query is quite unwieldy to use, because all the things you might want to play with are hardcoded.
SEDE allows using parameters, with a rather simple syntax:

##name:type[?if optional, default value]##

replacing all your magic numbers gets us to:

SELECT TOP ##x:int?150##
 -- ...
WHERE User.Age IS NOT NULL AND Users.Reputation > ##minrep:int?150## AND User.Age <= ##age:int?30##

Nitpicks:

Note that this already stretches out that single-line WHERE quite much. I really like queries to state WHERE conditions on separate lines, because that makes it easier to process them.

Additionally I strongly recommend a lightly different comma-placement when listing columns, namely the comma before the declaration.
This has the advantage of allowing removals without running into syntax errors each time.

Probably-Bugs:

The ordering you Limit By is ... skewed? strange? ... well you select the youngest users and limit according to age, when the purpose of such a query is most probably reputation based stats.
Off-By-One: WHERE Rep > 150 excludes users with 150 rep!
Then again it seems that the where clause about rep is moot anyways...
If you remove it, there's a way to cut away large parts of "inactive" userbase depending on reputation. Usually when querying that table, I explicitly exclude users with 1 and 101 rep. These two values are a strong indicator for non-activity.

My final version:

SELECT TOP ##x:int?150##
  ROW_NUMBER() OVER (ORDER BY Users.Reputation DESC) AS Rank
  , Users.Id as [User Link]
  , Users.Age
  , Users.Reputation as Rep
FROM Users
WHERE Users.Age <= ##age:int?30##
ORDER BY Rank ASC;

(also available on SEDE)


Calculating Euclidean norm for each vector in a sparse matrix Below is a naive algorithm to find nearest neighbours for a point in some n-dimensional space.

import numpy as np
import scipy.sparse as ss

# brute force method to get k nearest neighbours to point p
def knn_naive(k, p, X):
    stacked_p = ss.vstack([p for n in range(X.get_shape()[0])])
    D = X - stacked_p
    D = np.sqrt(D.multiply(D).sum(1))
    result = sorted(D)[:k]
    return result

Types for arguments to knn_naive(...) are:

# type(k): int
# type(p): <class 'scipy.sparse.csr.csr_matrix'>
# type(X): <class 'scipy.sparse.csr.csr_matrix'>

An example of dimensions would be:

X.shape: (100, 3004)
p.shape: (1, 3004)

Are there techniques to improve the above implementation in terms of computational time and/or memory?

I wasn't aware that scipy's sparse matrices did not support broadcasting. What a shame that you can't simply do D = X - p! Your construction of stacked_p can be sped up quite a bit, but you need to access the internals of the CSR matrix directly. If you aren't aware of the details, the wikipedia article has a good description of the format.

In any case, you can construct stacked_p as follows:

rows, cols = X.shape
stacked_p = ss.csr_matrix((np.tile(p.data, rows), np.tile(p.indices, rows),
                           np.arange(0, rows*p.nnz + 1, p.nnz)), shape=X.shape)

With some dummy data:

import numpy as np
import scipy.sparse as sps

p = sps.rand(1, 1000, density=0.01, format='csr')

In [15]: %timeit sps.vstack([p for n in xrange(1000)]).tocsr()
10 loops, best of 3: 173 ms per loop

In [16]: %timeit sps.csr_matrix((np.tile(p.data, 1000), np.tile(p.indices, 1000),
                                 np.arange(0, 1000*p.nnz + 1, p.nnz)), (1000, 1000))
10000 loops, best of 3: 94.1 µs per loop

That is close to 2000x times faster...


Algorithm Improvement - element differences in list The task is, you have an array of n numbers called nums, and an array of m numbers called maxes.

For each element in maxes, find the number of elements for which m is bigger than or equal to n.

nums = [4, 2, 5, 10, 8]
maxes = [3, 1, 7, 8]

output = [1, 0, 3, 4]

Eg, The first element, 3, in maxes, is only higher than 2 in nums, hence the first element in output is 1

The initial solution I could think of was trivial, and its O(n^2)

def sol_naive(nums,maxes):
    output = []
    for entry in maxes:
        higher_numbers = len([x for x in nums if x <= entry])
        output.append(higher_numbers)
    return output

Wondering if there's a better approach to solve this problem?

One simple observation is that this problem gets much easier if you sort nums O(n log(n). Then you can use bisect_left which uses binary search to find where an element would go in a sorted list and is O(log(n)) for each element in m. This yields a total time of O((n+m) log(n))

from bisect import bisect_left

def sol_sorted(nums,maxes):
    output = []
    nums.sort()
    for m in maxes:
        ind = bisect_left(nums, m)
        output.append(len(nums) - ind)
    return output


Getting employee details according to the role Here is my issue.I have two classes:

public class Role
{
  public string RoleTitle { get; set; }
  public string Office { get; set; }
  public string Department { get; set; }
}

And

public class Employe
{
  public string Name { get; set; }
  public List<Role> Roles { get; set; }
}

As you can see, class Employee contains ListRoles as a property.I have one method that process some share point list and returns one Employee object with all of his roles, something like this:

John Johnson

Regular Office1 Department2
Regular Office2 Department1
Manager Office1 Department3
OfficeDirector Office1 Departmnet4 etc.

As you can see one employee can have lot of different roles and lot of same roles but for different office/department (OK, I know that this is not real life situation, I'm just using this as an example). Now I'm using this Role information to process another SP List to get more information that I need to display.Roles are very important, because queries are based on them, what employee can see or not.Also, office and department are crucial information because rules for roles are also based on them.

My current code looks like this, I'm going through foreach loop and for each role, which I determine on RoleTitle, I create query, which will be added to final query (using OR).

public void GetEmployeeInformation(Employee emp)
{
    query = string.Empty;
    List<string> queries = new List<string>();
    foreach (Role role in emp.Roles)
    {
        switch (role.RoleTitle)
        {
            case ("Regular"):
                {
                    query = CamlQuery(role.Office, role.Department, "Office", "Department", "Choice");
                    break;
                    }

                case ("Manager"):
                    {
                        query = CamlQuery("Department", role.Department);
                        break;
                    }
                case ("OfficeDirector"):
                    {
                        query = CamlQuery("Office", role.Offices);
                        break;
                    }
                case ("Admin"):
                    {
                        query = CamlQuery("some implementation")
                        break;
                    }
            }
            queries.Add(query);
        }
//further implementation of method

    }

Everything is working fine, I got right results, but I'm wondering is there any chance that I can optimize code, because, for example, if I have 5 regular roles for each one it will go through the loop.

Another idea I got is to make changes in Role class, and create ListOffices, and ListDepartments so when I query in first method, I will get, for each different role, something like this

Manager:

Office1 Department1
Office2 Department2
Office3 Department3

Now, I will have only one Role object for every role with all office/department information inside, and I can go through foreach and inside Camlquery use one recursive method that will process all offices/departments for that role and create final query.The recursive method I've created is based on indexes of elements inside the lists, because when I create query I know that for first Manager role office/department pair is on [0] position in the list.But I've been told that using indexes in situation like this are very bad practice, so I've been stucked with this idea.

Do you have any idea how can I optimize this code by avoiding going through foreach loop for every single role and not using this approach with Lists and indexes?

You can  use linq GroupBy and Select to reduce your list to distinct RoleTitle's in your foreach loop:

foreach(Role role in emp.Roles.GroupBy(r=> r.RoleTitle).Select(g => g.First()))
{
    //...
}


Biometric matching score calculator I'm working on a biometric matching system and I would like to have few suggestions regarding vectorizing the following code:

% tpol and ipol
% column 1: x co-ordinate of the feature
% column 2: y co-ordinate of the feature
% column 3: angle orientation
% column 4: type of feature

ref_points=size(tpol,1); %number of rows=number of reference image points
   in_points=size(ipol,1); %number of rows=number of input image points
   radsize=7*ones(ref_points,1); %Radius size
   angsize=11* ones(ref_points,1); %Angle size
   radlow=-radsize./2;  % Lower Radius
   radhigh=radsize./2; % Upper Radius
   anglow=-angsize./2;  % Lower Angle
   anghigh=angsize./2; % Upper Angle
   epsillon=10;
   mscore=0; % initializing the matching score

   for i=1:ref_points
      for j=1:in_points
        rdiff=tpol(i,1)-ipol(j,1);    % Difference between the x-coordinate
        ediff=tpol(i,2)-ipol(j,2);      % Difference between the y-coordinate
        thetadiff=tpol(i,3)-ipol(j,3);   %Difference between the orientation
        if ((radlow(i) < rdiff) && (rdiff < radhigh(i)) && (anglow(i) < ediff) && ...
            (ediff < anghigh(i)) && (abs(thetadiff) < epsillon) && ...
            (tpol(i,4)==ipol(j,4)))
            mscore=mscore+1;
            tpol(i,4)=3; %Change type of the feature to know that the line was used
        end
      end
    end
  end

ipol and tpol are the input image and reference image points respectively. They are both a matrix of size (A x 4) each, A being the number of features detected in each image.

I asked this question on Mathworks for which I received the following answer:

    r = [-3.5 3.5];  % Lower Radius and Upper Radius
    a = [-5.5 5.5];  % Lower Angle and Upper Angle
    epsillon=10;

    % Vectorized computation of rdiff,ediff,thetadiff i.e. x,y-co-ordinate
    % and orientation
    pol = bsxfun(@minus,tpol,permute(ipol,[3 2 1]));
    p = all([bsxfun(@gt,pol(:,1:2,:),[r(1),a(1)]) & bsxfun(@lt,pol(:,1:2,:),[r(2),a(2)]),...
     pol(:,3,:) < ep, pol(:,4,:) == 0],2);
    mscore = nnz(p);
    tpol(any(p,3),4) = 4;

I checked the mscore received from the original code and verified it with the solution provided by plugging in one "if condition" at a time. All the "if conditions" provided me the same mscore except for:

if ((tpol(i,4)==ipol(j,4))

  and

p= all ([pol(:,4,:) == 0],2);

It would be very helpful if someone could help me out with this. The for loop takes a long time when the points detected are many.

The input data can be downloaded from Google Drive

Regarding the vectorized code:

permute can be considered a "Zero-cost operation".
Logical operations are performed fastest using bsxfun.
Arithmetic operations are fastest using bsxfun.

Therefore, it's close to impossible to improve the performance of the vectorized code you've posted.

Now, the question is: Is it correct?

It's hard to tell without knowing the exact data, but just by reading the code and your comments, I would think it is.

The reason why I think it is correct, even though the if conditions didn't return the same result:

You're comparing floating point values using ==. Check out Is floating point math broken?

When checking for equality, you should always use some tolerance. Have a look at the example below, where we are comparing 0.3 with 0.1 + 0.2:

x = 0.1;
y = 0.2;
z = 0.3;
the_same = (z == (x + y))
the_same =
     0
the_same = abs(z - (x + y)) < eps
the_same =
     1


Convert string of hex into vector of bytes I want to write a function that gets a string of hex numbers (two hex numbers represent a u8 value) then returns a vector of u8 values, e.g. the string 1f 0a d1 should be converted into [31, 10, 209]. The input string may contains non hex characters, then the function must be able to filter these characters, such as:

1f\x0ad1
1f \x0a\xD1
\x1F \x0a \xd1
\x1f    \x0A\xd1
...

All of them lead to the output [31, 10, 209]. My solution is that following:

fn parse_hex(hex_asm: &str) -> Vec<u8> {
    let hex_chars: Vec<char> = hex_asm.as_bytes().iter().filter_map(|b| {
        let ch = char::from(*b);
        if ('0' <= ch && ch <= '9') || ('a' <= ch && ch <= 'f') || ('A' <= ch && ch <= 'F') {
            Some(ch)
        } else {
            None
        }
    }).collect();

    let mut index = 0usize;
    let (odd_chars, even_chars): (Vec<char>, Vec<char>) = hex_chars.into_iter().partition(|_| {
        index = index + 1;
        index % 2 == 1
    });

    odd_chars.into_iter().zip(even_chars.into_iter()).map(|(c0, c1)| {
        fn hexchar2int(ch: char) -> u8 {
            if '0' <= ch && ch <= '9' {
                ch as u8 - '0' as u8
            } else {
                0xa +
                if 'a' <= ch && ch <= 'f' {
                    ch as u8 - 'a' as u8
                } else if 'A' <= ch && ch <= 'F' {
                    ch as u8 - 'A' as u8
                } else {
                    unreachable!()
                }
            }
        }
        hexchar2int(c0) * 0x10 + hexchar2int(c1)
    }).collect::<Vec<u8>>()
}

But it does make me happy. There are several problems that I may think of:

It needs to create two sub-vectors, one for odd-index element, one for even-index
Because of performance, I wrote the function hexchar2int (which is ugly) to convert two hex number into a u8 value instead of using u8::from_str_radix

I wonder if there is a better method to do that.

Note that this code will not work on any non-ASCII strings. These are more and more common, especially considering the global community we are a part of (and don't forget emoji ).
Use Vec<_> to avoid redundantly specifying the inner type when collecting.
Use byte literals b'x' instead of casting characters to bytes.
You can match on ranges of characters. I find this aesthetically pleasing.
Don't collect an iterator into a Vec just to call into_iter on the Vec. Instead, use the original iterator with partition.
Don't convert from u8 to char and back. You only need to make a single transformation.
There's no need to use the turbofish with the final collect since it's being returned and the type can be inferred.
There's no need to call into_iter for zip's argument, it's implied because it takes an IntoIterator.
Instead of partitioning into vectors, just grab two values out of the iterator at a time. Using fuse allows calling next after it's already returned None.
Your code handles the check of a hex digit twice, leading to the unreachable. Instead, perform the conversion when performing the check.

fn parse_hex(hex_asm: &str) -> Vec<u8> {
    let mut hex_bytes = hex_asm.as_bytes().iter().filter_map(|b| {
        match b {
            b'0'...b'9' => Some(b - b'0'),
            b'a'...b'f' => Some(b - b'a' + 10),
            b'A'...b'F' => Some(b - b'A' + 10),
            _ => None,
        }
    }).fuse();

    let mut bytes = Vec::new();
    while let (Some(h), Some(l)) = (hex_bytes.next(), hex_bytes.next()) {
        bytes.push(h << 4 | l)
    }
    bytes
}


IDF Function with a list of list I wanted to build a Inverse Document Frequency function, because in my opinion was not easy to do with scikit and I wanted also to show how it works for educational reasons.
Also reading this question on stack.
So I build this function.
It works, not sure about the efficency of my solution.
Let me know what do you think.
def idf(corpora,term="None"):
  """A function for calculating IDF, it takes a list of list as corpora, a term "t"
  and returns the relative IDF"""

  occurences=sum([ 1 for sublist in test for x in sublist if term in x])
  tot_doc=len(corpora)
  if occurences==0:
    print("Error")
  else:
    idf=round(1+np.log(tot_doc/occurences),3)
    return idf

test=[['I like beer'],['I like craft beers'],['I like ALE craft beers'],
      ['If I have to choose a craft beer, I will take the IPA craft beer']]

beer=idf(corpora=test,term='beer')
craft_beer=idf(corpora=test,term='craft')
ipa=idf(corpora=test,term='IPA')
print(beer)
print(craft_beer)
print(ipa)

Output:
  1.0
  1.288
  2.386

Use of global variable
In your function, you use test from the global scope in the comprehension which can lead to nasty side effects.
Type hints and formatting
Type hints and proper formatting help future readers understand the code easier. Modern code editors and static code analysis tools can also use them.
Docstring
A function docstring also helps future users to understand the code.
Raise ValueError if no match
Printing Error is not a good way to notify users of this function that something went wrong. What is the problem? Also if you dont return anything in this case, the function returns None with no errors, which can lead to other, harder to find errors later.
Use generator in counting sum
You dont need to create a list to count the occurences, you can just use a generator expression inside the sum.
No need for list of lists
Maybe you have a reason for this, but you dont need the list of lists data structure for your example.
Use python builtins
You dont need numpy for this task, using python builtins is enough. This way, you dont have to install numpy if you only want to use this function.

Putting it all together, my reviewed version looks like this.
import math
from typing import List

def inverse_document_frequency(corpora: List[str], term: str) -> float:
   """
   Calculates Inverse Document Frequency.

   Arguments:
       corpora (List[str]): List of strings to check for term 'term'
       term (str): Term to count in 'corpora'

   Returns:
       float: Inverse document frequency, defined as
           1 + log(length of corpora / occurrences of term)
           Rounded to 3 decimal places.
   """

   occurences = sum(1 for string in corpora if term in string)
   if occurences == 0:
       raise ValueError(f"No occurrences of term '{term}' in 'corpora'.")
   else:
       return round(1 + math.log(len(corpora) / occurences), 3)

test = [
   "I like beer",
   "I like craft beers",
   "I like ALE craft beers",
   "If I have to choose a craft beer, I will take the IPA craft beer",
]

beer = inverse_document_frequency(corpora=test, term="beer")
craft_beer = inverse_document_frequency(corpora=test, term="craft")
ipa = inverse_document_frequency(corpora=test, term="IPA")
print(beer)
print(craft_beer)
print(ipa)
```


Non locking UI code in WP8 I've recently started to delve into the world of windows phone 8 dev, and as a learning experience I've decided to make a stopwatch application. Now, given I've been a web guy most of my career, I've never come across UI thread locking issues, so the solution I've come up with to ensure my stopwatch class is updating the UI thread 'correctly' is (in my opinion at least) in need of a review.

So my overall questions with the below code are;

Am I doing it "right"?  I realise that can be kind of broad; I just want to make sure I'm not committing any cardinal sins of UI development.
Are there simpler approaches to what I've done?
Are there any improvements to the code that someone would suggest? I'm not sure using thread.sleep is a good idea, but when I take it out, it ends up locking the UI thread again. Hence why I'm asking for input.

My StopWatch Class:

public class StopwatchClass : IDisposable
{
    DispatcherTimer _timer;

    public int Interval { get; set; }

    public int Seconds { get; set; }
    public int Minutes { get; set; }
    public int Hours { get; set; }

    public bool IsRunning { get { return _timer.IsEnabled; } }
    public TimeSpan Elapsed { get; set; }
    public List<TimeSpan> Splits { get; set; }

    public StopwatchClass(int interval)
    {
        this.Splits = new List<TimeSpan>();

        _timer = new DispatcherTimer();
        _timer.Interval = new TimeSpan(0, 0, interval);
        _timer.Tick += timer_Tick;
    }

    void timer_Tick(object sender, EventArgs e)
    {
        this.Seconds += 1;
        if (this.Seconds == 60)
        {
            this.Minutes += 1;
            this.Seconds = 0;
        }
        if (this.Minutes == 60)
        {
            this.Hours += 1;
            this.Minutes = 0;
        }
    }

    public void Start()
    {
        _timer.Start();
    }

    public void Stop()
    {
        _timer.Stop();

    }
    public void Reset()
    {
        _timer = new DispatcherTimer();
        this.Seconds = 0;
        this.Minutes = 0;
        this.Hours = 0;
        this.Splits.Clear();
    }

    public void Split()
    {
        var timeSpan = new TimeSpan(this.Hours, this.Minutes, this.Seconds);
        this.Splits.Add(timeSpan);
    }

    public void Dispose()
    {
        _timer.Tick -= timer_Tick;
    }
}

And the WP8 button code (secondsValue is a text block on the wp8 page).

private async void startStopwatch_Click(object sender, RoutedEventArgs e)
    {
        watch.Start();

        await Task.Factory.StartNew(() =>
        {
            while (watch.IsRunning)
            {
                Thread.Sleep(1000);
                Dispatcher.BeginInvoke(() => secondsValue.Text = watch.Seconds.ToString());
            }

        });
    }

Minor

You should get rid of the Class suffix. There is no value in attaching the type as a suffix to the name.
You don't need to write this everywhere to access members.
You have an Elapsed property which is not used.

Bugs/Major

Your Reset() method will break the stopwatch because you create a new timer but you do not re-attach the timer tick event handler.
You have a Reset() method which sets up the timer but you also do this in the constructor which is some code duplication and in fact has introduced a bug (see previous point). DRY - Don't Repeat Yourself. Make use of a common method which can get called in both places.
Instead of "polling" your stopwatch in a continuous loop your StopwatchClass should expose an event like TimeUpdated to which any interested party can hook up to.

In general this can pose problems when interacting with UI because if the callback happens on a different thread then you need to marshal UI access across to the UI thread. However you have used a DispatcherTimer which is evaluated at the top of every dispatcher loop - which means the callbacks are happening on the UI thread and it is safe to access UI elements from within the callback (see the MSDN example).

So basically you can expose an event which gets fired on the timer callback and whatever code hooks up to it can update the UI.
In general MVVM has established itself as a very useful pattern. Which means that rather than updating UI elements directly you would update an observable view model to which the UI is bound. This decouples the UI better from the data and decoupling is always good.
The timer is guaranteed to not fire before the interval has elapsed - but there is no guarantee about how long after the interval has elapsed it will fire. This means your stopwatch will start falling behind the real time as you assume each tick is 1 second while in fact it might be 1.01 sec or so. This means after 100 seconds you could be easily 1 sec off or more. A thread time slice in windows is typically around 10ms so I'd suspect the timer to be around that accuracy. Although on Windows Phone you might get better performance (couldn't find any documentation in that regards).

The way to overcome this is to take a timestamp at Start and compute the difference to the current time on each tick. While this will probably also give you an approx. 10ms accuracy it will be constant while your solution will accumulate an error on each tick.

This will also alleviate the need to compute the seconds, minutes and hours since passing as you can get that from the Timespan.

With the changes from above your code could look like this:

public class StopwatchClass : IDisposable
{
    DispatcherTimer _timer;

    public int Interval { get; set; }

    public int Seconds { get; set; }
    public int Minutes { get; set; }
    public int Hours { get; set; }

    public bool IsRunning { get { return _timer.IsEnabled; } }
    public TimeSpan Elapsed { get; set; }
    public List<TimeSpan> Splits { get; set; }

    private DateTime _StartTimestamp = DateTime.MaxValue;

    public event EventHandler TimeUpdated;
    private void OnTimeUpdated()
    {
        var handler = TimeUpdated;
        if (handler != null)
        {
            TimeUpdated(this, EventArgs.Empty);
        }
    }

    public StopwatchClass(int interval)
    {
        Reset();
    }

    void timer_Tick(object sender, EventArgs e)
    {
        var timeSinceStart = DateTime.Now - _StartTimestamp;
        Seconds = (int)timeSinceStart.Seconds;
        Minutes = (int).timeSinceStart.Minutes;
        Hours = (int)timeSinceStart.TotalHours;
        OnTimeUpdated();
    }

    public void Start()
    {
        _StartTimestamp = DateTime.Now;
        _timer.Start();
    }

    public void Stop()
    {
        _StartTimestamp = DateTime.MaxValue
        _timer.Stop();
    }

    public void Reset()
    {
        Seconds = 0;
        Minutes = 0;
        Hours = 0;
        Splits = new List<TimeSpan>();
        _timer = new DispatcherTimer();
        _timer.Interval = new TimeSpan(0, 0, interval);
        _timer.Tick += timer_Tick;
    }

    public void Split()
    {
        var timeSpan = new TimeSpan(Hours, Minutes, Seconds);
        Splits.Add(timeSpan);
    }

    public void Dispose()
    {
        _timer.Tick -= timer_Tick;
    }
}


Seed std::mt19937 from std::random_device Many people seed their Mersenne Twister engines like this:

std::mt19937 rng(std::random_device{}());

However, this only provides a single unsigned int, i.e. 32 bits on most systems, of seed randomness, which seems quite tiny when compared to the 19937 bit state space we want to seed. Indeed, if I find out the first number generated, my PC (Intel i7-4790K) only needs about 10 minutes to search through all 32 bit numbers and find the used seed. (I know that MT is not a cryptographic RNG, but I just did that to get a feel for how small 32 bit really is in these days.)

I am trying to build a function to properly seed a mt19937 and came up with this:

#include <algorithm>
#include <iostream>
#include <random>

auto RandomlySeededMersenneTwister () {
    // Magic number 624: The number of unsigned ints the MT uses as state
    std::vector<unsigned int> random_data(624);
    std::random_device source;
    std::generate(begin(random_data), end(random_data), [&](){return source();});
    std::seed_seq seeds(begin(random_data), end(random_data));
    std::mt19937 seededEngine (seeds);
    return seededEngine;
}

int main() {
    auto rng = RandomlySeededMersenneTwister();
    for (int i = 0; i < 10; ++i)
        std::cout << rng() << "\n";
}

This does look like a safe solution to me; however, I have learned that problems with RNG are often times quite subtle.

Provided std::random_device produces good, random data on my system, does the code give me a correctly seeded std::mt19937?

Well, first off, why do you use a std::vector for a comparatively small sequence of known length? A raw array or std::array suffice and avoids any dynamic allocation.

Next, avoid needless magic numbers. Use std::mt19937::state_size instead of manually specifying 624.

Why do you use a lambda? A simple std::ref(source) suffices.

The seeding itself looks perfectly fine and there's no actual error anywhere in your code.
template<class T = std::mt19937, std::size_t N = T::state_size * sizeof(typename T::result_type)>
auto ProperlySeededRandomEngine () -> typename std::enable_if<N, T>::type {
    std::random_device source;
    std::random_device::result_type random_data[(N - 1) / sizeof(source()) + 1];
    std::generate(std::begin(random_data), std::end(random_data), std::ref(source));
    std::seed_seq seeds(std::begin(random_data), std::end(random_data));
    return T(seeds);
}

You could avoid the need for random_data by using counting and transforming iterators as detailed in "Sequence iterator? Isn't there one in boost?".
This is not simpler, but maybe more efficient:
template<class T = std::mt19937, std::size_t N = T::state_size * sizeof(typename T::result_type)>
T ProperlySeededRandomEngine () {
    std::random_device source;
    auto make_iter = [&](std::size_t n) {
    return boost::make_transform_iterator(
        boost::counting_iterator<std::size_t>(n), [&](size_t){return source();});
    };
    std::seed_seq seeds(make_iter(0), make_iter((N - 1) / sizeof(source()) + 1));
    return T(seeds);
}

On coliru


Number of possible palindrome sequences Here is the problem description from hackerearth.com:

  Rohan loves Palindromes. Palindrome is a string that read same forward
  and backward. For example abba is a palindrome while abca is not.

  Rohan is forming a palindrome of length lesser than or equal to \$n\$,
  with first \$k\$ characters of lowercase English letters. He needs your
  help to find out the number of possible palindromes.

  Output the result modulo \$10^9 + 7\$

  Input Format: First line contains 2 space separated integers, \$n\$ and \$k\$

  Output Format: Output a single integer, which is answer to the problem

  Constraints: \$1 ≤ n ≤ 10^9\$        \$1 ≤ k ≤ 26\$

  Sample input:

3 2

  Sample Output:

8

I tried making it and it was working fine for some small input but in case of large input its saying time limit exceeded. I think my code running time is \$O(n^2)\$, but I am not sure.

My code:

a,b = raw_input().split()
a = int(a)
b = int(b)
sum = 0
z = b
for i in xrange(1,a+1,2):
    d = z*2
    sum +=d
    z = z*b

if (a+1) % 2 == 0:
    sum = sum - (d/2)
print sum%1000000007

I am interested in knowing that where I am doing wrong with my code and how can I fix this. Also what should I do at first when I face these kind of problem whenever I have to deal with long input because every time I see any time limit error I am not able to fix it.

1. Introduction

You asked:

  what should I do at first when I face this kind of problem?

This is a good question! When I studied computing at university I was taught the following general technique:

Analyze the program and work out its complexity — that is, how does its runtime depend on its input?
Measure its runtime on some small examples.
Combine the complexity from step (1) with the measurements from step (2) to estimate the runtime for the worst case.
If the worst case is unacceptable, try to find a better algorithm.

As you get better at carrying out these steps, some of them will become second nature to you and so you won't have to go through them all in such detail as I do below. But when you're starting out, or unsure about the approach to take it's good practice to be thorough.

2. Analysis

The way to analyze a program is to annotate each line with the time it takes and the number of times it is executed. Then all you have to do is multiply and add!

But that's easier said than done, because how on earth do we know how long each line takes to execute? If we really wanted an accurate answer we could estimate it by running lots of tests. But we don't actually need to compute an exact answer: we just want an idea of how the runtime varies as a function of the input size. So as a first approximation, we'll say that simple operations (assignment, calling xrange, etc) take constant time 1, and that arithmetic operations like addition and subtraction take time proportional to the number of digits in the numbers. (We'll see later that this is an over-simplification, but it will have to do for now.)

CODE                          TIME TAKEN  NUMBER OF EXECUTIONS
============================  ==========  ====================
sum = 0                       1           1
z = k                         1           1
for i in xrange(1, n+1, 2):   1           n / 2
    d = z * 2                 log z       n / 2
    sum += d                  log sum     n / 2
    z = z * k                 log z       n / 2
if (n + 1) % 2 == 0:          log n       1
    sum = sum - d // 2        log sum     0 or 1
r = sum % 1000000007          log sum     1

(Note that I've rewritten the code to use n and k instead of a and b, so that the code more closely matches the statement of the problem.)

Now, in order to turn this into a total runtime, we need to know how big sum and z become. Well, \$z\$ gets multiplied by \$k\$ on each iteration of the loop, so after the \$i\$th iteration, \$z = k^{i+1}\$, and so \$z\$ is no more than about \$k^{n\over 2}\$ and so \$\log z\$ is no more than about \$n \log k \over 2\$.

At each iteration we add \$2z\$ to sum, where \$z\$ is no more than \$k^{n\over 2}\$. And there are about \$n \over 2\$ loop iterations, so sum is no more than \$nk^{n\over 2}\$ and so \$\log{sum}\$ is no more than \${n\log k\over2} + \log n\$. So adding everything up, we get a total runtime bounded by $$1 + 1 + {n\over 2} + {n^2 \log k \over 4} + {n^2 \log k + n\log n \over 2} + {n^2 \log k \over 4} + \log n + 2{n \log k + \log n \over 2}$$ which we can reorganize in terms of \$n\$ to get $$ n^2 \log k + {n\log n\over 2} + (\log k + {1\over 2})n + 2\log n + 2.$$  Now, as \$n\$ gets large, the terms containing \$n^2\$ will dominate (all the other terms become small by comparison). So we expect that as \$n\$ becomes large the runtime will become roughly proportional to \$n^2\log k\$.

(If this looks kind of complicated, it's because I've written out all the steps in detail. When you get experienced with the method, then you can skip all the steps that you know aren't going to appear in the result and just concentrate on the "big guns". For example, I would say to myself, "hmmm, that's \$Θ(n)\$ loops, each of which is handling numbers of typical size \$Θ(n\log k)\$ so the total runtime is \$Θ(n^2\log k)\$.")
Measurement is easier if we organize the code into functions, like this:

def palindromes(n, k):
    """Return the number of palindromes up to n letters long, using an
    alphabet of k letters, modulo 1000000007.

    """
    sum = 0
    z = k
    for i in xrange(1, n + 1, 2):
        d = z * 2
        sum += d
        z = z * k
    if (n + 1) % 2 == 0:
        sum = sum - d // 2
    return sum % 1000000007

Now we can measure the time taken (using Python's built-in timeit module) for some small values of \$n\$:

from timeit import timeit

def t(n, k):
    """Return the time taken to compute palindromes(n, k)."""
    return timeit(lambda:palindromes(n, k), number=1)

>>> t(10**3, 26)
0.0003402099828235805
>>> t(10**4, 26)
0.01810335897607729
>>> t(10**5, 26)
1.3598145439755172
>>> t(10**6, 26)
137.12631450797198

Let's plot the measurements from step (2) and draw a line of best fit to the equation \$t=an^2\$ that we worked out in step (1):

The fit looks pretty good and the coefficient of proportionality is \$a = 1.37 × 10^{-10}\$.

The worst case from the problem description is \$n=10^9\$, so this would result in a runtime of \$1.37 × 10^8\$ seconds, which is more than 4 years.
Four years is likely to exceed the time limit, so we need a better algorithm. How do you come up with one? Well, there are basically two sensible approaches here.

The first is to look for existing algorithms that solve the problem (or similar enough problems). It helps here to be familiar with lots of different types of algorithm so that you have some idea of where to look. And the way to become familiar with lots of algorithms is to read algorithms textbooks and then do some of the exercises.

The second approach is to use mathematical analysis to find alternative ways of computing the same results. For example, if you had a function like this:

def nsum(n):
    """Return a sum that depends on n."""
    result = 0
    for i in xrange(n):
        result += 1
    return result

Then I'm sure you could find a mathematical expression for the result in terms of the input \$n\$, and that would allow you to simplify the body of this function to:

    return max(n, 0)

or even:

    return n

if you didn't care about negative values of \$n\$.

3. Improving the algorithm

In this problem the mathematical approach looks like the way to go. Take a look at the analysis in §2.1 above. You can see that I was able to get quick estimates for the size of z and sum. But with a bit more care, could we work out the exact values for these variables?

Let's try that. We know that at the start of the \$i\$th iteration, \$z = k^i\$, and so \$d = 2k^i\$. So after \$m\$ loop iterations, the sum is $$ \sum_{1 \le i \le m} 2k^i = 2\sum_{1 \le i \le m} k^i. $$ If \$k=1\$ then this is \$2m\$, otherwise using the formula for summation of a geometric series it's $$ 2\left({k^{m + 1} - 1 \over k - 1} - 1\right). $$ There are exactly \$m = \left\lfloor{n + 1 \over 2}\right\rfloor\$ loop iterations, and if \$n\$ is odd we have a final subtraction of \$- k^m \$. So this suggests the following code:

def palindromes2(n, k, p=1000000007):
    """Return the number of palindromes up to n letters long, using an
    alphabet of k letters, modulo p.

    """
    if k == 1:
        return n % p
    m = (n + 1) // 2
    r = 2 * ((k**(m + 1) - 1) // (k - 1) - 1)
    if n % 2:
        r -= k**m
    return r % p

But we're not done! The first thing to do is to check that this is right, as it would have been easy to make a mistake in the mathematics. So let's check this function against the original:

>>> all(palindromes(n, k) == palindromes2(n, k)
...     for n in range(1, 1000) for k in range(1, 27))
True

But is it fast enough? Measurements suggest that it is faster that the first version of the code, but not fast enough to get the answer for \$n=10^9\$ in reasonable time:

>>> t(10**4, 26)
0.00031872402178123593
>>> t(10**5, 26)
0.011414641980081797
>>> t(10**6, 26)
0.2926187649718486
>>> t(10**7, 26)
11.10361772798933

We had better go through the analysis again for the new program and estimate the runtime. This time I'll omit the detailed analysis and cut straight to the point: we have some arithmetic operations here, on numbers that get as big as \$k^{{n + 1 \over 2}+1}\$, that is, with roughly \$n \log k\$ digits. We expect additions and subtractions on numbers of this size to take time roughly proportional to \$n \log k\$, and similarly for multiplication and division by small numbers. But there are also two exponentations: how long do these take? Well, I don't know about you, but I'm not sure of the runtime complexity of Python's ** operator. So there are two ways to go here: we could dive into the details of Python's exponentiation algorithm (yuck), or we could just assume that computing \$k^m\$ takes time proportional to some power of \$n \log k\$, say \$1 + b\$, and work out the value of \$b\$ by fitting the measurements to the equation \$t = an^{1+b}\$. Here's the best fit:

with parameters \$a = 4 × 10^{-11}\$ and \$b=0.63\$. (The value for \$1+b\$ is close to the exponent in the Karatsuba multiplication algorithm, which is the algorithm that CPython uses for multiplication of big numbers — see the function k_mul in longobject.c.)

So in the worst case (\$n = 10^9\$) the new algorithm is going to take about 5 hours. This is better than the 4 years of the original algorithm but is still likely to be unacceptable!

4. Further improving the algorithm

So we have to find another improvement. This is looking tricky: where can that come from? Well, the key observation is that the final result has to be returned modulo \$10^9+7\$, and so it can never have more than ten digits. And yet the intermediate values that we are computing are huge: in the worst case, \$k^m\$ has hundreds of millions of digits. This is a terrible waste of computation if we are going to compute a number with at most ten digits. So is there a way that we can do all the arithmetic modulo \$10^9+7\$ and so keep the intermediate values small?

How is that going to work? Modular addition, subtraction and multiplication are easy — we just add, subtract or multiply normally and then take the modulus later. For efficient modular exponentiation we can use the built-in function pow.

But we need a modular division operation in order to divide by \$k - 1\$, and Python doesn't have one built-in. In fact, modular division doesn't always exist — we can only divide by \$x\$ modulo \$p\$ if there is a unique number \$y\$ such that \$xy ≡ 1 \pmod p\$. (In this case \$y\$ is called the "multiplicative inverse of \$x\$ modulo \$p\$".) Luckily the modulus \$p\$ is prime, and this means that the multiplicative inverse \$y\$ exists for every \$x ≠ 0\$, and we can use the extended Euclidean algorithm to compute it.

That leads to this implementation:

def modular_inverse(x, p):
    """Return the multiplicative inverse of x modulo the prime p."""
    y, z, a, b = 0, 1, p, x
    while b:
        a, (q, b) = b, divmod(a, b)
        y, z = z, y - q * z
    return y

def palindromes3(n, k, p=1000000007):
    """Return the number of palindromes up to n letters long, using an
    alphabet of k letters, modulo the prime p.

    """
    if k == 1:
        return n % p
    m = (n + 1) // 2
    r = 2 * ((pow(k, m + 1, p) - 1) * modular_inverse(k - 1, p) - 1)
    if n % 2:
        r -= pow(k, m, p)
    return r % p

Again, we must check that this is correct:

>>> all(palindromes(n, k) == palindromes3(n, k)
        for n in range(1, 1000) for k in range(1, 27))
True

and see how bad the worst case is:

>>> timeit(lambda:palindromes3(10**9, 26), number=1)
3.3604970667511225e-05

That's probably acceptable now.


Find largest binary gap of a number N improved This is a follow-up question based on the original one. Could you please see the updated and refactored version and point at things to be improved in term of logic or efficiency?

I have now know as I have been made aware about the Greedy Algorithm; Math.Max and binary shifting which deal more gracefully with the task, however, if I were in a position to be unaware of them and this is the code I managed to write, what's your thoughts on it?

    public static int FindGap(int number)
    {
        string toBinary = Convert.ToString(number, 2);
        char[] toChar = toBinary.ToCharArray();

        char previous = '0';
        char current = '0';
        int maxGap = 0;
        int answer = 0;

        for (int i = 0; i < toChar.Length; i++)
        {
            if (toChar[i] == '1')
            {
                current = toChar[i];

                // keep last/latest largest gap as an answer
                if (answer < maxGap)
                {
                    answer = maxGap;
                }

                // reset if 1 appeared and start counting next gap
                maxGap = 0;
            }
            if ((toChar[i] == '0' && current == '1') || (toChar[i] == '0' && previous == '0'))
            {
                current = '0';
                maxGap++;
                previous = current;
            }
        }

        if (answer != 0)
        {
            return answer;
        }
        else return 0;
    }

If I were in a position to be unaware of them and this is the code I
  managed to write, what's your thoughts on it?

No need to call ToCharArray() because you can iterate over the chars of a string as well
By using an else if instead of the second if you won't need to check for toChar[i] == '0' but basically you only need a else.
Using a foreach loop instead of a for loop seems more natural for this task.
The returning of the answer can be simply return answer;
Because ToString(int, 2) strips leading '0' you can remove both current and previous.

Summing up it could look like so

public static int FindGap(int number)
{
    int maxGap = 0;
    int answer = 0;

    foreach(var c in Convert.ToString(number, 2))
    {
        if (c == '1')
        {
            if (answer < maxGap)
            {
                answer = maxGap;
            }
            maxGap = 0;
        }
        else
        {
            maxGap++;
        }
    }
    return answer;
}


Python image art project This program takes in an image, and saves an "arrowed" version of that image to /tmp/image.png. Example input and output is below the code.

from PIL import Image, ImageDraw
import operator
from pprint import pprint
import sys

base_width = 10
arrow_base_height = 15
arrow_point_height = 15
margin = (20,20)
do_outline = True
outline = (0, 0, 0) # black
background_color  = (255, 255, 255) # white

arrow_width = base_width / 2
total_arrow_height = arrow_base_height + arrow_point_height
total_arrow_width = 2 * base_width

def drawArrow(coords, color):
    if do_outline:
        draw.polygon(coords, fill=color, outline=outline)
    else:
        draw.polygon(coords, fill=color)

def to_real_coordinates(coords):
    # translates the coords to pixels on the picture
    return translate(coords, margin)

def translate(coords, vector):
    # Translates a list of coordinate tuples over a vector tuple
    t_coords = []
    for cord in coords:
        t_coords.append(tuple(map(operator.add, cord, vector)))
    return t_coords

def mirror(coords):
    # Takes a list of coordinate tuples and mirrors it across the first element of
    #    the first tuple
    # Formula: 2 * base - original
    m_coords = []
    base = coords[0]
    double_base = tuple(map(operator.mul, base, len(base)* (2,) ))
    for cord in coords:
        m_coords.append(tuple(map(operator.sub, double_base, cord)))
    return m_coords

def get_arrow_coords():
    coords = [
        (0, 0),
        (arrow_base_height, 0),
        (arrow_base_height, arrow_width),
        (arrow_base_height + arrow_point_height, - arrow_width),
        (arrow_base_height, -3 * arrow_width),
        (arrow_base_height, - base_width),
        (0, - base_width)
    ]
    return coords

if __name__ == "__main__":
    orig = Image.open(sys.argv[1]).transpose(Image.ROTATE_90)
    pix = orig.load()
    new_size = (1024,1024)
    actual_size = (new_size[0] + 2 * margin[0], new_size[1] + 2*margin[1])
    im = Image.new("RGB", actual_size, background_color)
    draw = ImageDraw.Draw(im)
    arrow = get_arrow_coords()
    m_arrow = mirror(arrow)
    for i in range(new_size[0] / total_arrow_height):
        for j in range((new_size[1] / total_arrow_width)):
            color = pix[
                i * total_arrow_height * orig.size[0] / new_size[0],
                j * total_arrow_width * orig.size[1] / new_size[1]
            ]
            # calculate and draw arrow
            coords = translate(arrow, (i * total_arrow_height, j * total_arrow_width))
            real_coords = to_real_coordinates(coords)
            drawArrow(real_coords, color)
            # calculate and draw mirrored arrow
            coords = translate(m_arrow, (arrow_base_height + i * total_arrow_height, j * total_arrow_width))
            real_coords = to_real_coordinates(coords)
            drawArrow(real_coords, color)

    im = im.transpose(Image.ROTATE_270)
    im.show()
    im.save("/tmp/image.png")

Be consistent and pythonic in naming functions.

draw_arrow instead of drawArrow

Use comprehensions instead of creating empty list and appending to it in a for loop. It's both faster and easier to read.

def translate(coords, vector):
    # Translates a list of coordinate tuples over a vector tuple
    return tuple(tuple(map(operator.add, c, vector)) for c in coords)

def mirror(coords):
    # Takes a list of coordinate tuples and mirrors it across the first element of
    #    the first tuple
    # Formula: 2 * base - original
    base = coords[0]
    double_base = tuple(map(operator.mul, base, len(base) * (2,) ))
    return tuple(tuple(map(operator.sub, double_base, cord)) for c in coords)

Why have a function that returns a constant value. Why creating a variable when you can just return the value.

def get_arrow_coords():
    return [...]
# or if you worry about mutability - use tuples. They actually faster if you wouldn't try to modify them (creating new ones from old ones) a lot.

arrow_coords = ...

You can also use collections.namedtuple('Size', 'height width') instead of using plain tuples for sizes. This would improve readability a little.

And I'm not sure, but maybe you would benefit from using numpy as it seems that you're doing some matrices work.


Students Arrangement algorithm I'm working on this exercise:

There is a classroom which has M rows of benches in it. Also, N students will arrive one-by-one and take a seat.

Every student has a preferred row number(rows are numbered 1 to M and all rows have a maximum capacity K. Now, the students come one by one starting from 1 to
N and follow these rules for seating arrangements:

Every student will sit in his/her preferred row(if the row is not full).
If the preferred row is fully occupied, the student will sit in the next vacant row. (Next row for N will be 1)
If all the seats are occupied, the student will not be able to sit anywhere.

Monk wants to know the total number of students who didn't get to sit in their preferred row. (This includes the students that did not get a seat at all)

Input

First line contains 3 integers
N, M and K.
N - Number of students and
M - Number of rows and
K - maximum capacity of a row.

Next line contains N space separated integers Ai.
Ai - preferred row of ith student.

Output

Output the total number of students who didn't get to sit in their preferred row.

Constraints:

1≤N,M≤10^5

1≤K≤500

1≤Ai≤M

code:

public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int K = sc.nextInt();
    int[] a = new int[N+1];
    //int[] rows = new int[N+1];
    TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
    //put student preferences in a, ordered as they enter one by one
    for(int i=1;i<=N;i++){
        a[i] = sc.nextInt();
    }
    //put in the tree the available rows as key,value: key:row number, value: available capacity
    for(int i=1;i<=M;i++){
        tree.put(i, K);

    }
    //count of students that didn't get a seat
    int c=0;
    for (int i=1;i<=N;i++){
        //check if prefered row is availbe
        //available capacity
        //case1: preferred seat is available
        if(tree.get(a[i])>0){
            tree.put(a[i], tree.get(a[i])-1);
        }
        else{
            //case 2: preferred seat is full, check next vacant row.
            if(tree.higherKey(a[i])!=null && tree.get(tree.higherKey(a[i]))>0){
                int nextRow = tree.higherKey(a[i]);
                tree.put(nextRow, tree.get(nextRow)-1);
            }
            // if preferred row is M, then check row 1
            if(a[i]==M && tree.get(1)>0){
                tree.put(1, tree.get(1)-1);
            }
            //increment count of students who didn't get to sit in their preferred row
            //(included those who didn't get a seat at all)
            c++;
        }
    }

    System.out.println(c);

}

I took into account all cases that are stated in the exercise. I want to know if I have anticipated all cases or am I missing a possible corner case.

Thanks for sharing your code!
These are my thoughts on it:

Naming

Naming Conventions

Please read (and follow) the
Java Naming Conventions

E.g.: you have variables with upper case names like N, M K. In java identifiers with (all) upper case indicate constants. But in your code these are variables and should therefore be (starting with) lower case letters.

You may have chosen this names including the case because they came from the problem statement. Nevertheless you should always stick to good naming. I would add the abbreviation from the problem statement as a comment to the variable:

    int numberOfStudensExpected = sc.nextInt();  // N
    int numberOfRowsInRoom = sc.nextInt(); // M
    int numberOfSeatsInRow = sc.nextInt(); // K

Choose you names from the problem domain, not from the technical solution.

You have identifier names like tree which refers to the type of the variabe. You should give it a name from your problem domain. Since it hols the capacity per row you decrement during processing it might be better named remainingCapacityPerRow.

Avoid single character names / abbreviations

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable. And/or you have to "reuse" variable names in different contexts. Both makes your code hard to read and understand for other persons. (keep in mind that you are  that other person yourself if you look at your code in a few month!) The same is true for (uncommon) abbreviations. You might find them being obvious today, while you're actively dealing with the problem, but You might have to "relearn" them if you worked on something else for a while.

On the other hand in Java the length of identifier names names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

So your variable a should better be named preferedRowOfStudent. And
your variable c should be named studentsWithoutSeat.

Along with the previous suggestion your code:

 if (tree.get(a[i]) > 0) {
     tree.put(a[i], tree.get(a[i]) - 1);

would change to:

 if (remainingCapacityPerRow.get(preferedRowOfStudent[i]) > 0) {
     remainingCapacityPerRow.put(preferedRowOfStudent[i], remainingCapacityPerRow.get(preferedRowOfStudent[i]) - 1);

As usual there are some exceptions for this suggestion.
E.g. the running index of loops is usually held in a single letter named variable like i in:

for(int i =0; i<SOME_CONSTANT; i++)

But even there you should use more problem oriented names to support your readers, especially in nested loops like this:

for(int rowInRoom =0; rowInRoom <numberOfRowsInRoom; rowInRoom ++)
   for(int seatInRow =0; seatInRow<numberOfSeatsInRow; seatInRow++)

Use of language

Use temporary variable to simplify the code

within your for loop you access the same element of array a several times. You should assign this element to a temporary variable before the first use.
Some may say you should do this for performance, but at least for Java performance is not affected.

along with the Avoid single character names / abbreviations suggestion your code would change to this:

 int studentsPreferedRow = preferedRowOfStudent[i];
 // ...
 int rowsRemainigCapacity = remainingCapacityPerRow.get(studentsPreferedRow );
 if (rowsRemainigCapacity  > 0) {
     remainingCapacityPerRow.put(studentsPreferedRow , rowsRemainigCapacity--);

doesn't this read much better?

Avoid odd ball solutions

You store the list of students in an array while you store the list of banks and their capacities in a Collection object rather than in an array too. This is called an odd ball solution because you use different approaches for the same thing.

avoid comments

Your solution has some comments which somehow structure your method into "sections". You should better extract these "sections" into methods with names derived from your comments:

public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    // read NMK
    int[] a = initialiseStudentRowPreferences(sc);
    TreeMap<Integer, Integer> tree = initializeRoom(N,K);
    int c = countStudentThatDidNotGetASeat(tree, a)
    System.out.println(c);
}
// ...
private int countStudentThatDidNotGetASeat(TreeMap<Integer, Integer> tree,int[] a){
   // do method extraction at all levels:
    int c = 0;
    for (int i = 1; i <= N; i++) {
      int studentsPreferedRow =  a[i];
      if(isPreferedRowAvailable(tree, studentsPreferedRow ))
        reduceCapacity(tree, studentsPreferedRow);
      } else {
         c += placeStudentInOtherRow(tree, studentsPreferedRow ))
      }
    }
    return c;
}
// ...

However, Comments should explain why the code is like it is, not what the code does. When ever you feel you need to explain your code try to find better names for your identifiers (variables and methods).

OOP

Your code is a procedural approach to the problem.

There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.

OOP doesn't mean to "split up" code into random classes.

The ultimate goal of OOP is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (among others):

information hiding / encapsulation
single responsibility
separation of concerns
KISS (Keep it simple (and) stupid.)
DRY (Don't repeat yourself.)
"Tell! Don't ask."
Law of demeter ("Don't talk to strangers!")


Next different permutation in C This is a program which you can get the next "different", i.e. elements in A[] can be identical, permutation at each call. I've written a C++ program for the same purpose in 2018, but I found it unreadable, readability = NULL, so here is a new one.
Any critical comment and answer will be welcomed :)
next_different_permutation.c:
#include <stdbool.h>

void pswap(int *l, int *r) {
    int temp = *l;
    *l = *r;
    *r = temp;
}

void reverse(int A[], int l, int r) {
    int size = (r-l+1);
    for (int i = 0; i < size/2; ++i)
        pswap(&A[l+i], &A[r-i]);
}

bool next_different_permutation(int A[], int l, int r) {
    if (r-l+1 <= 1)
        return false;                           // return false when [l,r] is(or back to) an increasing interval.
    int j = -1;                           // j will point to the highest peak of the interval [i,r].
    for (struct{int i, j;}                           // this for will find the first increasing [i,j] from r to l.
        z = {r-1, r}; z.j != l; --z.i, j=--z.j)
        if (A[z.i] < A[z.j]) {                           // find the maximal decreasing interval [j,r].
            int k = r;                           // after swap (i, k), interval [j,r] remains decreasing.
            while (!(A[z.i] < A[k]))                           // find the first A[k] where A[k] > A[z.i].
                --k;
            pswap(&A[z.i], &A[k]);
            reverse(A, z.j, r);
            return true;                           // when success we go, the z.i, z.j will be initialized in next call.
        }
    reverse(A, j, r);                           // Recover the A[l]>=A[l+1]>=...>=A[r]-array back to the increasing order.
    return false;
}

Usage:
#define ARRAY_SIZE 3
int A[ARRAY_SIZE]

void next_different_permutation_test_distinct() {
    for (int i = 0; i < ARRAY_SIZE; ++i)
        A[i] = i+1;
    do {
        print_array(A, ARRAY_SIZE, PRINT_WIDTH);
    } while (next_different_permutation(A, 0, ARRAY_SIZE-1));
    // the order will back to A[l]<A[l+1]<...<A[r]
}

void next_different_permutation_test_some_identical() {
    for (int i = 0; i < ARRAY_SIZE; ++i)
        A[i] = rand()%RAND_MOD;
    do {
        print_array(A, ARRAY_SIZE, PRINT_WIDTH);
    } while (next_different_permutation(A, 0, ARRAY_SIZE-1));
}

size and i in reverse look superficial. Consider
void reverse(int A[], int l, int r) {
    while (l < r) {
        pswap(&A[l++], &A[r--]);
    }
}

The outer loop looks very strange. Its body is executed exactly once, when the longest decreasing interval is detected. Consider lifting the body out of the loop.
As a side point, I don't see the point of struct {int i; int j}. It is initialized to {r-1, r}, and at each iteration both members are decremented. z.i is always equal to  z.j - 1. Keeping just one int is enough. Consider
  int j = r; // j will point to the highest peak of the interval [i,r].
  // this loop will find the first increasing [i,j] from r to l.
  while (j > l) {
      if (A[j-1] < A[j]) {
          break;
      }
      --j;
  }

  if (j > l) {
      int k = r;
      // find the first A[k] where A[k] > A[j-1].
      while (!(A[j-1] < A[k])) {
          --k;
      }
      pswap(&A[j-1], &A[k]);
      reverse(A, j, r);
      return true;
  }

  reverse(A, j, r);
  return false;

It already looks cleaner, but let's get going. An obvious next step is to get rid of the duplicate calls to reverse:
  if (j > l) {
      ....
      pswap(....);
  }
  reverse (A, j, r);
  return j > l;

No naked loops please. If you felt compelled to put comments like
      // find the maximal decreasing interval [j,r]
      // find the first A[k] where A[k] > A[z.i].

you admit that you failed to express the intentions in the code. Consider refactoring these loops into functions. Consider
  int j = find_decreasing_interval(A, l, r);
  if (l < j) {
      int k = lower_bound(A, j, r, A[j-1]);
      pswap(&A[j-1], &A[k]);
  }
  reverse((A, j, r);
  return j > l;


R merge even/odd rows I need to merge eve/odd rows on a data set.

Example:

      match team count points
    1     1  ARG    11     21
    2     1  ENG     9     19
    3     2  CAN     8     15
    4     2  USA     8     17
    5     3  FRA     7      7
    6     3  NZL     8     36

To:

      match team1 t1p t1s team2 t2p t2s
    1     1   ARG  11  21   ENG   9  19
    2     2   CAN   8  15   USA   8  17
    3     3   FRA   7   7   NZL   8  36

This is my current solution:

odd <- all_scores[seq(1, nrow(all_scores), 2),]
colnames(odd) <- c("match", "team1", "t1p", "t1s")
even <- all_scores[seq(2, nrow(all_scores), 2),]
colnames(even) <- c("match", "team2", "t2p", "t2s")
new_scores <- merge(odd, even)

Is there an easier, more space efficienct, or more R-like way to do this?

Have a look at the reshape function. To use the jargon, your data is in "long" format and you want to turn it to a "wide" format. Before using reshape, you will need to add a column of 1, 2, 1, 2, etc. so it can be used as the "time" column. You can do that on the fly using the transform function. In all:

new_scores <- reshape(transform(all_scores, i = 1:2),
                      idvar = "match", timevar = "i", direction = "wide")

#   match team.1 count.1 points.1 team.2 count.2 points.2
# 1     1    ARG      11       21    ENG       9       19
# 3     2    CAN       8       15    USA       8       17
# 5     3    FRA       7        7    NZL       8       36


Cell division Solving algorithm problems When G cell divides, it is divided into two G + 1 cells.

In order for the G cell to divide, energy as much as G is required.

What is the minimum energy required to make the total number of cells x?

Input Example (G for each of 2 cells, total number of cells)

1 3 4

Output Example (minimum energy)

3

Input Description
Assuming that there is one cell of the first generation and one cell of the first generation in the beginning, the energy required to make a total of four cells is as follows.
1G 3G -> Generation 1 (Energy 1 required)
2G 2G 3G -> Generation 2 (energy 2 required)
2G 3G 3G 3G (total 4 completed final energy 3)

I've answered the question in C #.

Is there a better way or a way to speed it up?

ex) If Sum is 10 million

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

namespace ConsoleApplication1
{
  class Program
  {
     static void Main(string[] args)
     {
        StringBuilder m_strbuilder = new StringBuilder();

         List<int> Cells = new List<int>();
         int MinIndex = 0;
         int Sum = 0;
         int FirstCell = 0;
         int SecondCell = 0;

         bool etc = true;
         ulong Result = 0;

         string Inputdata = null;
         string[] Textdata = null;

         while (etc)
        {
           try
           {
             Cells.Clear();

             Inputdata = Console.ReadLine();

             Textdata = Inputdata.Split(' ');

             if (Textdata[0] != null && Textdata[1] != null && Textdata[2] != null)
             {
                int.TryParse(Textdata[0], out FirstCell);
                int.TryParse(Textdata[1], out SecondCell);
                int.TryParse(Textdata[2], out Sum);
              }

            else
                continue;

            if ( 0 < FirstCell && FirstCell <= 10000000)
            {
                if (0 < SecondCell && SecondCell <= 10000000)
                {
                    if (2 <= Sum && Sum <= 100000000)
                        etc = false;
                    else
                        continue;
                }
                else
                    continue;
             }
            else
                continue;
           }

        catch (ArgumentException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (NullReferenceException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (IndexOutOfRangeException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
       }

        Cells.Add(FirstCell);
        Cells.Add(SecondCell);

        if (Cells[0] > Cells[1])
        {
            int TempNum = Cells[1];
            Cells[1] = Cells[0];
            Cells[0] = TempNum;
        }

         for (int i = 2; i < Sum; i++)
        {
            Result += (ulong)Cells[MinIndex];

            Cells[MinIndex] += 1;

            Cells.Insert(MinIndex + 1, Cells[MinIndex]);

            if (MinIndex + 1 != Cells.Count - 1)
            {
                if (Cells[MinIndex + 2] < Cells[MinIndex])
                    MinIndex = MinIndex + 2;
                else
                    MinIndex = 0;
            }
            else
                MinIndex = 0;
        }

        m_strbuilder.Append(Result);
        Console.WriteLine(m_strbuilder);

      }
    }
 }

namespace ConsoleApplication1
{
  class Program

These names tell no-one anything useful about what the program does, and there's no comment either. If you find this file on your hard drive in a year's time, will you remember what it's for?

        StringBuilder m_strbuilder = new StringBuilder();

        ...

        m_strbuilder.Append(Result);
        Console.WriteLine(m_strbuilder);

m_strbuilder is a misleading name (m_ is one convention for naming fields, but I've never seen it used for local variables); and the StringBuilder is completely unnecessary. Console.WriteLine(object) can be used as well on one object as another, so this could be simplified to

        ...

        Console.WriteLine(Result);

The indentation is crazy. I suspect that it's due to mixed tabs and spaces being converted to all spaces by the StackExchange software. But consistent code formatting is a good thing in general: reformat your code before you commit / submit for review.

         while (etc)
        {
           try
           {
             Cells.Clear();

             Inputdata = Console.ReadLine();

             Textdata = Inputdata.Split(' ');

             if (Textdata[0] != null && Textdata[1] != null && Textdata[2] != null)
             {
                int.TryParse(Textdata[0], out FirstCell);
                int.TryParse(Textdata[1], out SecondCell);
                int.TryParse(Textdata[2], out Sum);
              }

            else
                continue;

            if ( 0 < FirstCell && FirstCell <= 10000000)
            {
                if (0 < SecondCell && SecondCell <= 10000000)
                {
                    if (2 <= Sum && Sum <= 100000000)
                        etc = false;
                    else
                        continue;
                }
                else
                    continue;
             }
            else
                continue;
           }

        catch (ArgumentException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (NullReferenceException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (IndexOutOfRangeException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
       }

Firstly, this is a complicated bunch of code with a narrowly defined purpose.  On that basis it should be pulled out into a method. This would also allow a more elegant escape from the infinite loop, using return.

Secondly, even if it isn't in a method, some of those variables have narrow scopes and should be defined in their real scope rather than outside it. E.g. Textdata is not used outside the loop, so should be defined inside it.

Thirdly, the convention in C# is that local variables start with a lowercase letter, not an uppercase one.

Fourthly, the error handling is wrong. I tested this without supplying input (because a previous version of the question hardcoded the input and didn't require it to be supplied), and got an infinite loop outputting Unable to add System.NullReferenceException.

Fifthly, the input specification is essentially missing from the spec posted in the question, but I find the assumption that there will be exactly two starting cells to be unnecessarily restrictive. IMO the code could be simpler without that assumption.

         for (int i = 2; i < Sum; i++)
        {
            Result += (ulong)Cells[MinIndex];

            Cells[MinIndex] += 1;

            Cells.Insert(MinIndex + 1, Cells[MinIndex]);

            if (MinIndex + 1 != Cells.Count - 1)
            {
                if (Cells[MinIndex + 2] < Cells[MinIndex])
                    MinIndex = MinIndex + 2;
                else
                    MinIndex = 0;
            }
            else
                MinIndex = 0;
        }

Inserting into the middle of a List usually means that you're using the wrong data structure for the task. The right data structure for this approach would surely be a priority queue of some kind.

However, the approach can be optimised a lot. Consider input 1 1 67108864. Initially you have two 1s. After two generations you will have four 2s. After six generations you will have eight 3s. In general, if you have n of the smallest value G, and you still need n or more generations, you can replace all of them with 2n copies of G+1 at cost 2nG. So if you track generation and multiplicity you can go from executing the outer loop Sum - 2 times to roughly log(Sum) times, again using a priority queue. Work through the maths a bit more and you can make it a constant time calculation with no loops (assuming that you only have two cells in the starting state - if you adapt for an arbitrary number of cells as I suggested above, you need one loop).


Reverse Polish Calculator in Go I'm very new to Go (this is my first real program), and I was hoping to see if there was anything I was missing about the language or any ways to make it more idiomatic.

calculator.go

package calculator

import (
    "../stack"
    "unicode"
    "strconv"
)

func Calculate(input string) int {
    stack := new(stack.Stack)

    for i := 0; i < len(input); i++{
        c := rune(input[i])

        if unicode.IsDigit(c) {
            stack.Push(parseNumber(input, &i))
        }
        switch c {
            case '+':
                b := stack.Pop()
                a := stack.Pop()
                stack.Push(a + b)
            case '-':
                b := stack.Pop()
                a := stack.Pop()
                stack.Push(a - b)
            case '*':
                b := stack.Pop()
                a := stack.Pop()
                stack.Push(a * b)
            case '/':
                b := stack.Pop()
                a := stack.Pop()
                stack.Push(a / b)
        }

    }

    if(stack.Size() > 1) {
        panic("Input did not fully simplify")
    }

    return stack.Pop()
}

func parseNumber(input string, i *int) int {
    initialIndex := *i

    for unicode.IsDigit(rune(input[*i])) {
        *i++
    }
    num, _ := strconv.Atoi(input[initialIndex : *i])
    return num
}

calculator_test.go

package calculator

import (
 "testing"
)

func TestCalculate(t *testing.T) {
    tests := map[string]int{
     "3 4 +":7,
     "3 4 -":-1,
     "3 4 *":12,
     "3 4 /":0,
     "1 1 + 2 -":0,
     "5 10 * 2 /":25,
    }
    for input, expected := range tests {
        result := Calculate(input)
        if(result != expected) {
            t.Log("Calculate failed. Expected ",expected, ", got ", result)
            t.Fail()
        }
    }
}

stack.go

package stack

type Stack struct {
    i int
    // fixed size
    data [100]int
}

func (s *Stack) Push(i int) {
    if(s.i + 1 >= len(s.data)){
        panic("Out of memory!")
    }

    s.data[s.i] = i
    s.i++
}
func (s *Stack) Pop() int {
    if(s.i - 1 < 0){
        panic("Can't pop when there is no data!")
    }

    s.i--
    return s.data[s.i]
}

func (s *Stack) Size() int {
    return s.i
}

stack_test.go
Not very proud of this. Is there any way I can reduce the duplicated code? Are there any built in assert methods?

package stack

import (
 "testing"
)

func TestStack(t *testing.T) {
    s := new(Stack)

    if(s.Size() != 0) {
        t.Fail()
    }

    s.Push(1)

    if(s.Size() != 1) {
        t.Fail()
    }

    s.Push(2)

    if(s.Size() != 2) {
        t.Fail()
    }

    s.Push(3)

    if(s.Size() != 3) {
        t.Fail()
    }

    if(s.Pop() != 3) {
        t.Log("Didn't pop in order!")
        t.Fail()
    }

    if(s.Size() != 2) {
        t.Fail()
    }
    if(s.Pop() != 2) {
        t.Log("Didn't pop in order!")
        t.Fail()
    }
    if(s.Size() != 1) {
        t.Fail()
    }

    if(s.Pop() != 1) {
        t.Log("Didn't pop in order!")
        t.Fail()
    }
    if(s.Size() != 0) {
        t.Fail()
    }
}

Don't use relative import paths.

Such as "../stack".
Instead, use full import paths like
(e.g.) "github.com/kyranstar/RPN/stack".
That would be a reasonable path to use if you put your source somewhere like
$GOPATH/github.com/kyranstar/some-repo-name/, since you're a GitHub user.
This is discussed in How to write Go code.

So for example:

$GOPATH/src/github.com
└── kyranstar
    └── RPN
        ├── calculator
        │   ├── calculator.go
        │   └── calculator_test.go
        └── stack
            ├── stack.go
            └── stack_test.go

Note that you can do this even if you never have any intention of making this available on github.
In that case you'd just be using "github.com/kyranstar" as a convient prefix
that won't conflict with anyone else
(e.g. I use "bitbucket.org/myname/…", "github.com/myname/…", and "myname-test/…" as Go import prefixes depending on what I'm doing).

You didn't include anything to build a run-able command.
If you're fine with just go testing your packages, you don't need to.
But if you want to build a standalone non-test program you could either
put a simple package main right in …/kyranstar/RPN/anyname.go
or if the repo might have multiple commands to build, in …/kyranstar/RPN/cmd/name-of-command/anyname.go.
In either case, go build and go install will use the base name of the containing directory as the executable name.

Run go fmt (or gofmt, or goimports) on all your Go source.

On your source the changes it makes includes removing extraneous parenthesizes,
it's idiomatic to use if x { rather than if(x) {.

Slices vs arrays and your stack package.

It's usually better to use slices rather than fixed sizes arrays (like you do in stack.go)
unless you actually have a fixed size (e.g. perhaps type CoordinateVector [3]float64).

Then stack can become just something like:

package stack

type Stack []int

func (s Stack) Len() int    { return len(s) }
func (s *Stack) Push(i int) { *s = append(*s, i) }
func (s *Stack) Pop() int {
        n := len(*s) - 1
        v := (*s)[n]
        *s = (*s)[:n]
        return v
}

Note, Len() is more common/idiomatic than Size()
(and gorename
can help rename such things for you including all references anywhere in your $GOPATH).
This doesn't have a fixed size like yours does at the slight expense
of re-allocations as it grows.

Note that naming a package stack with a single type Stack causes code using it to stutter,
e.g. s := new(stack.Stack).
There is a blog entry about Package names that addresses this.
For example, perhaps such a stack package could have several types like Int, Int64, Float64, etc
and then callers would use stack.Int, stack.Int64, stack.Float64, etc.

Alternatively, the changed package becomes so small that it is common to just stick it into a stack.go
file in the current (calculator in this case) package and use it as a non-exported package type.

Finally, where you use this you have stack := new(stack.Stack).
Note that you are creating a local variable which shadows the import name.
You've made it difficult/impossible to use anything from the stack package anywhere else in the function
(e.g. to make a second stack for any reason).
If for no other reason then to prevent confusion in people reading the code, it's usually best to avoid such
things.

Strings by byte or rune.

Again there is a blog entry that covers this:
Strings, bytes, runes and characters in Go.

You have:

    for i := 0; i < len(input); i++ {
            c := rune(input[i])

this loops by bytes instead of by Unicode code points (called runes in Go).
This should normally be:

    for i, c := range input {

But then it iterferes with your parseNumber usage.
Sadly, strconv doesn't appear to have a function that will parse
out a number from the start of a string and tell you how many bytes/runes
were parsed.
Since you're only handling digits (and not decimal, negatives, floating point, etc)
it'd be pretty use to just make parseNumber such a function.

Return error, don't panic!

You should never panic out of a package for anything other than
critical unrecoverable programming errors.
(For example, the above Stack.Pop will just panic if the caller
miss-uses the stack, it's up to the caller to check Len if they need to.)
You should instead do something like this:

func Calculate(input string) (int, error) {
        // …
        if stack.len() != 1 {
                return 0, errors.New("did not fully simplify")
        }
        return stack.Pop(), nil
}

Note that it's recomended that error strings should not be capitalized
or end in punctuation.
golint
can help catch such things.

Testing

Instead of:

        t.Log("something")
        t.Fail()

Use t.Error
and/or t.Errorf.

Use a slice instead of a map for testcase data.
A map isn't needed, and it's unordered.
You don't show what input caused the failure which makes it
harder than needed for someone fixing a problem down the road.
You don't test failure cases
(see Go's testing coverage to see what your tests are missing).

So something like this perhaps:

func TestCalculate(t *testing.T) {
        tests := []struct {
                in  string
                out int
        }{
                {"3 4 +", 7},
                {"3 4 -", -1},
                {"3 4 *", 12},
                {"3 4 /", 0},
                {"1 1 + 2 -", 0},
                {"5 10 * 2 /", 25},
        }
        for _, d := range tests {
                result, err := Calculate(d.in)
                if err != nil {
                        t.Errorf("Calculate(%q) failed: %v", d.in, err)
                }
                if result != d.out {
                        t.Errorf("Calculate(%q) gave %v, expected %v",
                                d.in, result, d.out)
                }
        }
}

You mention repeated code in stack_test.go and assert methods.
Although there are various third party testing/assert packages,
I don't recommend them.

Usings what I've just mentioned, if I wanted to test a few
series of operations on something
I'd likely do something like this:

func TestStack(t *testing.T) {
        const (
                doPush = iota
                doPop
        )
        tests := [][]struct {
                op  int
                val int
                l   int
        }{
                // Simple 3×Push then 3×Pop:
                {
                        {doPush, 1, 1},
                        {doPush, 2, 2},
                        {doPush, 3, 3},
                        {doPop, 3, 2},
                        {doPop, 2, 1},
                        {doPop, 1, 0},
                },
                // … other cases here …
        }
nextTest:
        for i, steps := range tests {
                s := new(Stack)
                for j, d := range steps {
                        // Could use t.Log/t.Logf to verbosely
                        // log something about the step/op being done.
                        switch d.op {
                        case doPush:
                                s.Push(d.val)
                        case doPop:
                                if g := s.Pop(); g != d.val {
                                        t.Errorf("%d:%d poped %v, expected %v",
                                                i, j, g, d.val)
                                        continue nextTest
                                }
                        }
                        if g := s.Len(); g != d.l {
                                t.Errorf("%d:%d end len %v, expected %v",
                                        i, j, g, d.l)
                                continue nextTest
                        }
                }
        }
}

Then it becomes easy for anyone to just add data to the struct
for more testcases or more steps.

One complication here is that I wanted it to stop a specific
test case on the first failure (since each remaining step
depends on the previous ones working).
Normally you'd just use t.Fatal in place of t.Error to signal
that your test function can't proceed.
Here I just continue on with the next test case so I need the
(some would call ugly) loop label.

In addition to the previously mentioned links,
Effictive Go
and the Go Author's Go Code Review Comments
should be considered required reading.


Implementing Sample Abstract Factory Pattern using Smart Pointers in C++ Was trying to implement and example code to smart pointer from link.
Is it a good practice? To go with all unique pointers or should we use shared pointers in this case? How can i improve this ?

#include <iostream>
#include <string>
#include<memory>

void LOG(std::string strText)
{
    std::cout << strText << std::endl;
}

class Widget {
public:
    virtual void draw() = 0;
};

class WindowsBtn : public Widget
{
public:
    void draw() {
        LOG("Windows Button");
    }
};

class WindowsMenu : public Widget
{
public:
    void draw() {
        LOG("Windows Menu");
    }
};

class LinuxBtn : public Widget
{
public:
    void draw() {
        LOG("Linux Button");
    }
};

class LinuxMenu : public Widget
{
public:
    void draw() {
        LOG("Linux Menu");
    }
};
/*
class WidgetFactory
{
public:
    virtual Widget* CreateButton() = 0;
    virtual Widget* CreateMenu() = 0;
};

class WindowsFactory : public WidgetFactory{
public:
    Widget* CreateButton() {
        return (new WindowsBtn);
    }

    Widget* CreateMenu() {
        return (new WindowsMenu);
    }

};

class LinuxFactory : public WidgetFactory{
public:
    Widget* CreateButton() {
        return (new LinuxBtn);
    }

    Widget* CreateMenu() {
        return (new LinuxMenu);
    }

};

class Client
{
    WidgetFactory * factory;
public:
    Client(WidgetFactory* factory) :factory(factory)
    {}

    void draw(){
        Widget * wd = factory->CreateButton();
        wd->draw();
        display1();
        display2();
    }
    void display1()
    {
        Widget * w[] = {
            factory->CreateButton(),
            factory->CreateMenu()
        };
        w[0]->draw();
        w[1]->draw();
    }
    void display2()
    {
        Widget * w[] = {
            factory->CreateMenu(),
            factory->CreateButton()
        };
        w[0]->draw();
        w[1]->draw();
    }

};
*/
class SmartWidgetFactory
{
public:
    virtual std::unique_ptr<Widget> CreateButton() = 0;
    virtual std::unique_ptr<Widget> CreateMenu() = 0;
};

class SmartWindowsFactory : public SmartWidgetFactory {
public:
    std::unique_ptr<Widget> CreateButton() {
        return std::make_unique<WindowsBtn>();
    }

    std::unique_ptr<Widget> CreateMenu() {
        return  std::make_unique<WindowsMenu>();
    }
};

class SmartLinuxFactory : public SmartWidgetFactory {
public:
    std::unique_ptr<Widget> CreateButton() {
        return  std::make_unique<LinuxBtn>();
    }

    std::unique_ptr<Widget> CreateMenu() {
        return std::make_unique<LinuxMenu>();
    }
};

class SmartClient
{
    std::unique_ptr<SmartWidgetFactory> factory;
public:
    SmartClient(std::unique_ptr<SmartWidgetFactory> oFactory)
    {
        factory = std::move(oFactory);
    }

    void draw() {
        std::unique_ptr<Widget> wd = factory->CreateButton();
        wd->draw();
        display1();
        display2();
    }
    void display1()
    {
        std::unique_ptr<Widget> w[] = {
            factory->CreateButton(),
            factory->CreateMenu()
        };
        w[0]->draw();
        w[1]->draw();
    }
    void display2()
    {
        std::unique_ptr<Widget> w[] = {
            factory->CreateMenu(),
            factory->CreateButton()
        };
        w[0]->draw();
        w[1]->draw();
    }
};

int _tmain(int argc, _TCHAR* argv[])
{

    /*WidgetFactory *factory;
    factory = new LinuxFactory;
    Client *c = new Client(factory);
    c->draw();*/

    std::unique_ptr< SmartWidgetFactory > oFactory = std::make_unique<SmartLinuxFactory>();
    std::unique_ptr<SmartClient> oClient = std::make_unique<SmartClient>( std::move(oFactory) );
    oClient->draw();

    return 0;
}

First, the big bug.  Your Widget class has no virtual destructor! This means that every time you return a unique_ptr<Widget>, you're losing the information about what kind of widget needs destroying.

Clang will actually diagnose this mistake for you. No matter what compiler you use, make sure you turn on warnings via -Wall -Wextra (or -W4 on MSVC).

int _tmain(int argc, _TCHAR* argv[])

This is a non-standard main routine. Maybe I'm a POSIX chauvinist, but at least for posting publicly, I'd think it would be more appropriate to use

int main(int, char **)

or even better,

int main()

(since you don't use either of those parameters for anything).

Also notice that I'm using char** instead of char*[], because in C and C++, a function parameter cannot be an array. It is pointless to deceive yourself and mean to deceive others.

SmartClient(std::unique_ptr<SmartWidgetFactory> oFactory)

This constructor should be marked explicit. In fact, every constructor you ever write (except for copy constructors and move constructors) should be explicit. If you leave off the explicit, then you're enabling people to write code like

std::unique_ptr<SmartWidgetFactory> pf = ...;
SmartClient sc = std::move(pf);

or even

SmartClient sc = nullptr;

and it'll compile, and they won't realize what they did wrong until runtime. It's better to catch this kind of thing at compile time. Mark all your constructors explicit.

std::unique_ptr<Widget> CreateButton()

If you intended this function to override the virtual function in the base class, you should have marked it override. (It may still override the virtual function in the base class, even without override, if you spelled everything correctly; but don't bet your workday on it. Mark all overriding functions override and catch your bugs at compile time.)

Also, consider whether it makes conceptual sense that "creating a button" is a non-const method of the factory. Maybe it does; I tend to think it doesn't. So I would write this as

std::unique_ptr<Widget> CreateButton() const override

std::unique_ptr<SmartClient> oClient = std::make_unique<SmartClient>( std::move(oFactory) );

Why does this need to be heap-allocated?

auto oClient = SmartClient(std::move(oFactory));

Even if you want to keep using make_unique for some reason, consider replacing the cumbersome type name std::unique_ptr<SmartClient> with auto:

auto oClient = std::make_unique<SmartClient>(std::move(oFactory));

Notice I've also normalized the whitespace while I'm at it.

void LOG(std::string strText)

Pass large expensive-to-copy objects, such as std::string, by const reference.

void LOG(const std::string& text)

If you are on C++17, consider replacing const std::string& parameters with std::string_view parameters:

void LOG(std::string_view text)

Be aware that you should use string_view only in places where it would make equal sense to use a reference type (so, parameters, and that's it).

Also be aware that when people see LOG("foo") in your code, they will assume that LOG is a macro, because it's ALL UPPER CASE. If you mean for people to assume it's a function, call it print_to_log or something like that.


A job sequencing solution I have written this code as a college assignment fot the famous job sequencing problem. Please tell me any improvements if possible. Oh, for algorithms.h header file, refer my github repo

The code:

#include "algorithms.h"

struct Job {
    int index = 0;
    int time_slot = 0;
    int profit = 0;
public:
    Job() = delete;
    explicit Job(int i, int time, int pr) {
        index = i;
        time_slot = time;
        profit = pr;
    }
    bool operator>=(Job j) {
        if ((this->time_slot == j.time_slot && this->profit >= j.profit) || (this->time_slot > j.time_slot)) {
            return true;
        }
        return false;
    }
    bool operator<=(Job j) {
        if ((this->time_slot == j.time_slot && this->profit <= j.profit) || (this->time_slot < j.time_slot)) {
            return true;
        }
        return false;
    }
    bool operator<(Job j) {
        if ((this->time_slot == j.time_slot && this->profit < j.profit) || (this->time_slot < j.time_slot)) {
            return true;
        }
        return false;
    }
    bool operator>(Job j) {
        if ((this->time_slot == j.time_slot && this->profit > j.profit) || (this->time_slot < j.time_slot)) {
            return true;
        }
        return false;
    }
    bool operator==(Job j) {
        if (this->time_slot == j.time_slot) {
            return true;
        }
        return false;
    }
    friend std::ostream& operator<<(std::ostream& out, Job job) {
        out << job.index;
        return out;
    }
};

int main() {
    Job j1(1, 1, 3);
    Job j2(2, 3, 5);
    Job j3(3, 4, 20);
    Job j4(4, 3, 18);
    Job j5(5, 2, 1);
    Job j6(6, 1, 6);
    Job j7(7, 2, 30);
    std::vector<Job> vect = { j1,j2,j3,j4,j5,j6,j7 };
    vect = Sorter<Job>::mergeSort(vect);
    auto order = [&]() {
        auto it = vect.begin();
        while (it + 1 != vect.end()) {
            if (*it == *(it + 1)) {
                it = vect.erase(it);
                continue;
            }
            it++;
        }
    };
    order();
    std::for_each(vect.begin(), vect.end(), [](Job i) {std::cout << i << " "; });
    return 0;
}

The Job class has public members, so it's simpler to make it an aggregate:

struct Job {
    int index;
    int time_slot;
    int profit;
};

Then, use std::tie to simplify the comparison operators: (operands to these operators should be marked as const, which you didn't)

bool operator<(const Job& lhs, const Job& rhs)
{
    return std::tie(lhs.time_slot, lhs.profit) < std::tie(rhs.time_slot, rhs.profit);
}

// implement other operators in terms of <

You == is not consistent with other comparison operators, which is confusing and likely to cause problems.

Also note that if (condition) { return true; } return false; should be changed to return condition; for clarity.

This is convoluted:

Job j1(1, 1, 3);
Job j2(2, 3, 5);
Job j3(3, 4, 20);
Job j4(4, 3, 18);
Job j5(5, 2, 1);
Job j6(6, 1, 6);
Job j7(7, 2, 30);
std::vector<Job> vect = { j1,j2,j3,j4,j5,j6,j7 };

It should be simplified to

std::vector<Job> vect {
    {1, 1, 3}, {2, 3, 5}, // ...
};

This:

auto order = [&]() {
    auto it = vect.begin();
    while (it + 1 != vect.end()) {
        if (*it == *(it + 1)) {
            it = vect.erase(it);
            continue;
        }
        it++;
    }
};
order();

should be

vect.erase(std::unique(vect.begin(), vect.end()), vect.end());

(provided that I understand the code correctly).

And this:

std::for_each(vect.begin(), vect.end(), [](Job i) {std::cout << i << " "; });

is a complicated way of writing

for (const auto& job : vect) {
    std::cout << job << ' ';
}

or

std::copy(vect.begin(), vect.end(),
          std::ostream_iterator<Job>{std::cout, ' '});


Two dialog boxes using Deferreds? I've two similar functions and I want to use one generic function with two params, dialog and buttons.  How do I do it?

My functions:

LanguageLogosView.showConfirmRemoveDialog = function () {
    var def = $.Deferred();
    var buttons = {
        buttons: {
            "Remove": function () {
                def.resolve(true);
                $(this).dialog("close");
            },
            Cancel: function () {
                def.resolve(false);
                $(this).dialog("close");
            }
        }
    };
    $('#dialog-confirm-remove').dialog($.extend(LanguageLogosView.dialogConfirmDefaultSettings, buttons));
    return def;
}

LanguageLogosView.showConfirmEmptyRowsDialog = function () {
    var def = $.Deferred();
    var buttons = {
        buttons: {
            "Save": function () {
                def.resolve(true);
                $(this).dialog("close");
            },
            Cancel: function () {
                def.resolve(false);
                $(this).dialog("close");
            }
        }
    };
    $("#dialog-confirm-save-with-empty-rows").dialog($.extend(LanguageLogosView.dialogConfirmDefaultSettings, buttons));
    return def;
}

First of all, always return def.promise() - not def itself. If you return the Deferred object itself, other code can call resolve/reject on it. So keep def to yourself, and only return its promise.

Also, why not use reject() for the Cancel buttons instead of resolve(false)? If you use reject, it'll probably make the rest of your code simpler, since you don't need to check the resolve arguments. Your "success" handler either gets called, or it doesn't.

Second, since you're building buttons in both cases, that'd probably be the part I'd extract. For instance

function makeDialogButtons(resolveTitle, rejectTitle) {
  var def = $.Deferred(),
      buttons = {};

  buttons[resolveTitle] = function () {
    def.resolve();
    $(this).dialog('close');
  };

  buttons[rejectTitle] = function () {
    def.reject();
    $(this).dialog('close');
  };

  return { buttons: buttons, promise: def.promise() };
}

And use it like so

LanguageLogosView.showConfirmEmptyRowsDialog = function () {
  var buttons = makeDialogButtons('Save', 'Cancel');
      options = $.extend(LanguageLogosView.dialogConfirmDefaultSettings, buttons.buttons);
  $("#dialog-confirm-save-with-empty-rows").dialog(options);
  return buttons.promise;
};

It's not great, but it should do the job.