fftshift implementation for OpenCV I'm trying to implement fftshift from matlab for OpenCV. Can you please review the correctness of my algorithm? Have I missed something? Also, is there a better and faster way to do it?

cv::Mat ff;
cv::dft(distanceF, ff, cv::DFT_COMPLEX_OUTPUT);

//Make place for both the complex and the real values
cv::Mat planes[] = {cv::Mat::zeros(distanceF.size(),1, CV_32F), cv::Mat::zeros(distanceF.size(),1, CV_32F)};
cv::split(ff, planes);    // planes[0] = Re(DFT(I), planes[1] = Im(DFT(I))

cv::vector<float> im(planes[1].cols);
cv::vector<float> re(planes[0].cols);
int m = planes[0].cols;
int p = ceil(m/2);

for (int i = 0; i < p; i++)
{
    im[i] = planes[1].at<float>(p + i +1);
    im[p +i +1] = planes[1].at<float>(i +1);

    re[i] = planes[0].at<float>(p + i +1);
    re[p +i +1] = planes[0].at<float>(i +1);
}
im[p] = planes[1].at<float>(0);
re[p] = planes[0].at<float>(0);
cv::Mat input[] = {cv::Mat(im),cv::Mat(re)};
cv::merge(input,2,ff);

I think the best way to implement fftshift is like it is done in OpenCv itself:

//The body is inspired from OpenCV, the fct_fftshift is mine
void fct_fftshift(cv::Mat& src)
{
    int cx = src.cols/2;
    int cy = src.rows/2;

    cv::Mat q0(src, cv::Rect(0, 0, cx, cy));
    cv::Mat q1(src, cv::Rect(cx, 0, cx, cy));
    cv::Mat q2(src, cv::Rect(0, cy, cx, cy));
    cv::Mat q3(src, cv::Rect(cx, cy, cx, cy));

    cv::Mat tmp;
    q0.copyTo(tmp);
    q3.copyTo(q0);
    tmp.copyTo(q3);

    q1.copyTo(tmp);
    q2.copyTo(q1);
    tmp.copyTo(q2);
}

int main(int argc, char* argv[])
{
  cv::Mat src=cv::imread(argv[1], CV_8UC1);
  fct_fftshift(src); //it will change your original image
}


Basic slot machine game I have been learning PHP and wanted to see if I could make a very simple slot machine game.  Everything works, but I'm sure this is not the best way to do this. Please let me know how you would do this and what I can do to improve.

<?php

$num1 = rand(1, 5);
$num2 = rand(1, 5);
$num3 = rand(1, 5);

$result = $num1.' | '.$num2.' | '.$num3;

// Read points from file
$filename = 'points.txt';
$handle = fopen($filename, 'r');
$current = fread($handle, filesize($filename));
fclose($handle);

if ($num1 == $num2 && $num2 == $num3) {
$status = '<big>You are a winner!</big>';

$add_points = $current + 10;

// Add points to file
$handle = fopen($filename, 'w');
$current_points = fwrite($handle, $add_points);
fclose($handle);

} else {
$status = 'please try again!';
}

?>

<title>Slot Machine Game!</title>

<big><?php echo $result; ?></big>

<big><?php echo $status; ?></big>

<big><?php echo 'You have '.$current.' points!'; ?></big>

Looks good. Few initial things:

Indent inside control structures, so everything inside your if() statement would be prefixed by one tab. (You can use a fixed number of spaces, but that can cause problems if you share your code with people who use a different tab-spacing system).
It is a really good idea to split out your code into logic (or "controller") and template (or "view"). Your html would then go in a different file and be loaded by your PHP file - a good first step with this sort of thing is Smarty. From there you can progress to a proper PHP framework such as Symfony or Zend (but be aware the learning curve is steep).
Tags such as  and <big> tend to be discouraged - use CSS instead.
Keep your PHP statements in your view as small as possible. For example I'd rewrite your score thus:

    You have <?php echo $current ?> points!

You'll need to define a CSS class called 'points', of course.

Maybe you know but this game can only be played by one player at a time. Also there is no way for that player to restart there game.

As you are using this to learn exercise I would suggest your next step would be to use PHP sessions to store the players score. Then give the user the ability to start a new game.

It would also be nice to add a "Play Again" button and play again only if that button was click. If the user just refreshed try to have it not play again.

If you decide to go that way then you could have a new player welcome message for users who have not started to play yet.

Good luck.


Realizing a SQL ResultSet into a Map in Scala I am trying to realize a java.sql.ResultSet into a map, in Scala.

import java.sql.{ResultSet, ResultSetMetaData}

class DbRow extends java.util.HashMap[java.lang.String, Object] {
}

object freeFunctions {

  def realize(queryResult: ResultSet): Vector[DbRow] = {
    val md = queryResult.getMetaData
    val colNames = for (i <- 1 to md.getColumnCount) yield md.getColumnName(i)
    var rows: Vector[DbRow] = Vector.empty
    while (queryResult.next()) {
      val row = new DbRow
      for (n <- colNames) {
        row.put(n, queryResult.getObject(n))
      }
      rows = rows :+ row
    }
    rows
  }

}

I feel this could (should) be less verbose. If while/yield comprehensions existed, or some
comprehension for create a map. The client code needs a java map for now, but if an elegant
enough solution can produce a Scala map, I could convert it.

I don't have the time to test this, so I hope you can do that for me. I decided not to use HashMap straight away because type conversion makes things a bit more complicated than they should, but let me know if this is important for you and causes you trouble.

Here's option 1:

def realize(queryResult: ResultSet): Vector[Map[String, Object]] = {
    val md = queryResult.getMetaData
    val colNames = for (i <- 1 to md.getColumnCount) yield md.getColumnName(i)
    val buildMap = () => (for (n <- colNames) yield n -> queryResult.getObject(n)).toMap
    Iterator.continually(queryResult.next()).takeWhile(identity).map(_ => buildMap()).toVector
}

I don't like it much because some parts of the code rely on side effects of other parts of the code, so even if it works, it's still ugly.

Here's option 2, which I like more:

def buildMap(queryResult: ResultSet, colNames: Seq[String]): Option[Map[String, Object]] =
    if (queryResult.next())
        Some(colNames.map(n => n -> queryResult.getObject(n)).toMap)
    else
        None

def realize(queryResult: ResultSet): Vector[Map[String, Object]] = {
    val md = queryResult.getMetaData
    val colNames = (1 to md.getColumnCount) map md.getColumnName
    Iterator.continually(buildMap(queryResult, colNames)).takeWhile(!_.isEmpty).map(_.get).toVector
}

Nicer, IMHO, you can save some dots over there but I decided to keep them. Maybe something like this:

 (Iterator continually (buildMap(queryResult, colNames)) takeWhile (!_.isEmpty) map (_.get)).toVector

Again, I didn't test it, I don't know how to do it without a DB and I don't feel like setting one up now, sorry for that.

Finally, I'm not sure if you realized this, but "realize" is probably not the best name for this method (or for any method, unless you are programming some epistemic system, IMHO).

e.g. to get a map out of a resultset column ...

new Iterator[String] {
  def hasNext: Boolean = rs.next()
  def next(): String = rs.getString("xyz")
}.toMap


Password generator in Python 3.7 I am learning how to code in Python by myself and have never coded before, I just want to know if there is any way I can upgrade my PasswordGenerator.

#!/usr/bin/env python3
import random

def passwordgenerator():
    mypw = ""
    count = 0
    alphabet_number =    "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    symbols = "!?@%#$"
    running1 = True
    while running1:

        if len(symbols) == 1:

            #  Reset symbols
            symbols = "!?@%#$"

        if len(alphabet_number) == 1:

            #  Reset letters/numbers
            alphabet_number = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

        elif count == pw_length:

            if mypw.isupper() or mypw.islower():  # check if there is only upper     or only lower letter and rerun if True
                passwordgenerator()

            else:
                x = mypw
                y = list(x)  # creates a list and put the pw in to shuffle it
                random.shuffle(y)
                mypw = "".join(y)

                print(mypw)
                input("\nPress <Enter> to close the program")
                running1 = False

        elif count % 4 == 0:

            #  pick a random symbol every 3 loop and add it to the pw
            symbols_index = random.randrange(len(symbols))
            new_symbols = symbols[symbols_index]
            mypw = mypw + new_symbols

            # delete the symbols that is picked so there are no duplicate
            symbols_list_change = symbols.replace(new_symbols, "")
            symbols = symbols_list_change

        else:

            # pick a random number or letter and add it to the pw
            next_index = random.randrange(len(alphabet_number))
            new_alphabetnumber = alphabet_number[next_index]
            mypw = mypw + new_alphabetnumber

            # delete the symbols that is picked so there are no duplicate
            an_list_change = alphabet_number.replace(new_alphabetnumber, "")
            alphabet_number = an_list_change

        count += 1

if __name__ == '__main__':
    print("/!\ 12 Characters is a minimum for good security /!\ ")

    print("=" * 55)  # just to make it pretty

    running = True
    while running:
        pw_length = input("How many Characters do you want?\n")

        if pw_length.isdigit():  # verify if user input a number
            pw_length = int(pw_length)
            passwordgenerator()
            running = False
        else:
            print("A number is needed")

Not bad a all for a first Python program:

Good use of the line: if __name__ == '__main__': .
Good use of string methods (replace, isupper, islower etc...).
Good use of the random module methods.

But some things can be made better:

The function passwordgenerator could have pw_length as a parameter and return mypw. (The printing of the password moves to the main part in this case)
calling passwordgenerator from within passwordgenerator itself (a recursive call) can be tricky (what is the password accidentally is always lower...?)
The string constants "!?@%#$" and "abc...XYZ" occur both twice, they could be made constants on top of the program.
I think the line: elif count == pw_length should be different
a docstring could be added to passwordgenerator explaining the properties of the generated password.

Instead of writing out those long strings of characters, it might be better to use the predefined constants.  For example:

alphabet_number = string.ascii_lowercase +
                  string.ascii_digits +
                  string.ascii_uppercase

That way, you're saved from mistyping the list, and it's clearer to readers what's included.


Append nones to list if is too short Is it possible to improve this bit?

def append_nones(length, list_):
    """
    Appends Nones to list to get length of list equal to `length`.
    If list is too long raise AttributeError
    """
    if len(list_) < length:
        nones = length - len(list_)
        return list_ + [None] * nones
    elif len(list_) > length:
        raise AttributeError('Length error list is too long.')
    else:
        return list_

1. Comments on your code

The documentation does not match the implementation. The docstring says "append Nones to list" but it does not append: if the list does not have the required length, it returns a newly allocated list.
It seems wrong to return the original list if it was the right length, but return a newly allocated list if it was too short. For consistency, the function should either always return a new list, or always (update and) return the old list.
It's a loss of generality to support only the addition of None elements. Why not let the caller pass in their preferred placeholder element.
If you run help(AttributeError) you'll see that its description is "Attribute not found." This does not seem appropriate here. ValueError would be a better choice, or better still, create your own.
There's no need to name the variable list_: this avoids shadowing the built-in function list, but you don't use that function, so it doesn't matter if you shadow it.
You call len(list_) three times. Simpler to call it once and store the value.
The case len(list_) == length could be combined with the case len(list_) < length and so simplify the code.
The error message "Length error list is too long" makes no sense in English.
The error message would be more useful if it contained the actual numbers.
This kind of function is ideal for doctests.

2. Revised code

I've chosen to make the function always update its argument, and fixed all the problems noted above.

class TooLongError(ValueError):
    pass

def pad(seq, target_length, padding=None):
    """Extend the sequence seq with padding (default: None) so as to make
    its length up to target_length. Return seq. If seq is already
    longer than target_length, raise TooLongError.

    >>> pad([], 5, 1)
    [1, 1, 1, 1, 1]
    >>> pad([1, 2, 3], 7)
    [1, 2, 3, None, None, None, None]
    >>> pad([1, 2, 3], 2)
    ... # doctest: +IGNORE_EXCEPTION_DETAIL
    Traceback (most recent call last):
      ...
    TooLongError: sequence too long (3) for target length 2

    """
    length = len(seq)
    if length > target_length:
        raise TooLongError("sequence too long ({}) for target length {}"
                           .format(length, target_length))
    seq.extend([padding] * (target_length - length))
    return seq

def nones(length,mylist):
    if len(mylist) > length:
        raise AttributeError('Length error list is too long.')
    for i in range(length):
        try: yield mylist[i]
        except IndexError: yield None

print list(nones(20,[1,2,3]))

it doesnt exactly match what you described but this is the implementation I would probably use

I would also probably change

if len(mylist) > length:
    raise AttributeError('Length error list is too long.')

to

assert len(mylist) <= length,"list is too long"


Binary check code in pyspark I am trying to find out if a column is binary or not. If a column is only having 1 or 0 then I am flagging it as binary, else non binary. Since I have a database background, I tried to achieve it through a SQL like statement. But when the file is big, this code is not giving me good performance.

Could you please suggest how I can improve this code:

input_data=spark.read.csv("/tmp/sample.csv", inferSchema=True,header=True)
input_data.createOrReplaceTempView("input_data")
totcount=input_data.count()

from pyspark.sql.types import StructType,StructField,StringType
profSchema = StructType([ StructField("column_name", IntegerType(), True)\
                   ,StructField("binary_type", StringType(), True)])
fin_df=spark.createDataFrame([],schema=profSchema) ##create null df

for colname in input_data.columns:
    query="select {d_name} as column_name,case when sum(case when {f_name} in ( 1,0) then 1 else 0 end) == {tot_cnt} then 'binary' else 'nonbinary'\
    end as binary_stat from input_data".format(f_name=colname, d_name="'"+str(colname)+"'",tot_cnt=totcount)
    join_df=spark.sql(query)
    fin_df=fin_df.union(join_df)

Spark dataframes (and columns) have a distinct method, which you can use to get all values in that column. Getting the actual values out is a bit more complicated and taken from this answer to a similar question on StackOverflow:

from pyspark.sql import SparkSession

def get_distinct_values(data, column):
    return {x[column] for x in data.select(column).distinct().collect()}

spark = SparkSession \
    .builder \
    .appName("Python Spark SQL basic example") \
    .config("spark.some.config.option", "some-value") \
    .getOrCreate()

input_data = spark.read.csv("/tmp/sample.csv", inferSchema=True, header=True)
input_data.createOrReplaceTempView("input_data")

print({c: get_distinct_values(input_data, c) == {True, False}
       for c in input_data.columns})
# {'category': False, 'logged_in': True, 'gid': False, 'pol_id': False, 'subcategory': False}

I don't know enough about spark to know how you would cast this back into a spark dataframe, but this should get you at least halfway there and be a bit faster, since it can do the fastest implementation it can to reduce the values to sets.

# /tmp/sample.csv
pol_id,gid,category,subcategory,logged_in
1,1,A,a,1
2,1,A,b,0
1,2,B,b,1
2,2,B,a,0

In my earlier approach, I was taking the count of 1 and 0 of a column also the total record count. If there is a match then I was flagging it as binary else non binary. But as per this approach, I am limiting the distinct record to 3. Then checking if the number of record is 2 and it has 0 or 1

columns_isbinary = []
for column_name in input_data.columns:
    column = input_data.select(column_name)
    column_distinct_3 = column.distinct().limit(3).rdd.flatMap(lambda x: x).collect()
    column_distinct_3_str = [str(value) for value in column_distinct_3]
    column_isbinary = len(column_distinct_3) == 2 and\
     all(value in column_distinct_3_str for value in ('1', '0'))
    columns_isbinary.append((column_name, column_isbinary))

is_binarydf=spark.createDataFrame(columns_isbinary,("column_name","isbinary"))


Cloning Distinct XML structures without data in PHP I struggled for the last couple days on this question and finally came up with a solution. But it's got so many loops I get dizzy just looking at the code - from recursive functions with loops to loops within loops.

I really expected to find a canned function in a popular XML class to extract all the unique nodes without data, but I am surprised how non-trivial I've found this endeavor.

While this works for my piddly example data, I have performance and scalability concerns when trying to use this code in production. For example, this elegant answer uses XSLT to solve the problem, but it's limited by node depth. So is there anyway to improve efficiency by cutting out a loop, or using less objects, or even utilizing a different class or technology completely? Are there any glaring failing conditions that aren't represented in my example data?

<?php
$xml = '
<root>
  <node/>
  <node>
    more
  </node>
  <node>
    another
  </node>
  <node>value</node>
</root>
';
$doc = new DOMDocument();
$doc->loadXML($xml);

// clone without data
$empty_xml = new DOMDocument();
$empty_xml->appendChild($empty_xml->importNode($doc->documentElement));
function clone_without_data(&$orig, &$clone, &$clonedoc){
  foreach ($orig->childNodes as $child){
    if(get_class($child) === "DOMElement")
      $new_node = $clone->appendChild($clonedoc->importNode($child));
    if($child->hasChildNodes())
      clone_without_data($child,$new_node,$clonedoc);
  }
}
clone_without_data($doc->documentElement, $empty_xml->documentElement, $empty_xml);

// remove all duplicates
$distinct_structure = new DOMDocument();
$distinct_structure->appendChild($distinct_structure->importNode($doc->documentElement));
foreach ($empty_xml->documentElement->childNodes as $child){
  $match = false;
  foreach ($distinct_structure->documentElement->childNodes as $element){
    if ($distinct_structure->saveXML($element) === $empty_xml->saveXML($child)) {
      $match = true;
      break;
    }
  }
  if (!$match)
    $distinct_structure->documentElement->appendChild($distinct_structure->importNode($child,true));
}
$distinct_structure->formatOutput = true;
echo $distinct_structure->saveXML();

This results in the unique XML structures stripped of all data:

<?xml version="1.0"?>
<root>
  <node/>
  <node>

  </node>
</root>

I would consider getting all nodes using getElementsByTagName('*') (note wildcard usage).

I would also consider simply cloning the $doc object.

That could simplify to this:

$doc = new DOMDocument();
$doc->loadXML($xml);
$clone = cloneDOMDocument($doc, true);

function cloneDOMDocument(DOMDocument $source, $remove_values = false) {
    $clone = clone $source;
    if($remove_values === true) {
        // select all nodes in clone
        $all_nodes = $clone->getElementsByTagName('*');

        // iterate all nodes in clone, resetting leaf values to empty string
        foreach($all_nodes as $node) {
            if($node->hasChildNodes() === false) {
                $node->nodeValue = '';
            }
        }
    }
    return $clone;
}


Counting number of inversions This is a HackerEarth Challenge Problem.

  Question:
  Puchi hates to carry luggage, but unfortunately he got a job to carry
  the luggage of his N friends in office. Each day, one of his N
  friends, gives him the luggage of a particular weight to carry. You
  will be given the weight of luggage of each friend in the array
  Weight, where Weighti is the weight of luggage of ith friend carried
  by Puchi on ith day. It is given that all the luggages carried by
  Puchi are distinct in their weights. As Prateek assigned this job to
  Puchi, so for each day, he wants to know the number of days in future
  when Puchi will have to carry the luggage , having weight less than
  the weight of luggage of current day. Please help Prateek for the
  same.

  Input:
   The first line contains a single integer T, denoting the number of test cases. In each test case, the following input will be
  present: First line contains an integer N, where N represents the
  number of friends. Next N line contains N integers, where ith line
  contains ith integer, which represents Weighti.

  Output:
     Output exactly T lines. Each line contains N integer separated by a space, where ith integer represents the number of
  luggage of future, which are less than the weight of luggage of the
  current day.

  Constraints:

  Subtask 1:   1 <= T <= 30 1<= N <= 104 1<= Weighti <= 106

  Subtask 2:   1 <= T <= 10 1<= N <= 105 1<= Weighti <= 106

I have used merge sort to calculate the inversions:

public class Puchi_and_Luggage {
static long invfreq[]=new long[1000001];

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
          int N=Integer.parseInt(br.readLine().trim());
          StringBuilder ans=new StringBuilder();

          int arr[]=new int[N];
          int copy[]=new int[N];
          for(int i=0;i<N;i++)
          {
              arr[i]=Integer.parseInt(br.readLine().trim());
              copy[i]=arr[i];
              invfreq[arr[i]]=0l;
          }

          mergesort(arr,0,N-1);
          for(int i=0;i<N;i++)
          {
            ans.append(invfreq[copy[i]]+" ");
          }
          System.out.println(ans);
        }

    }

    private static void mergesort(int[] arr, int i, int j) {

        int mid=0;

        if(i<j)
        {
            mid=(i+j)/2;
            mergesort(arr,i,mid);
            mergesort(arr,mid+1,j);
            merge(arr,i,mid,j);

        }

    }

    private static void merge(int[] arr, int i, int mid, int j) {

        int temp[]=new int[arr.length];
        int l=i;
        int r=j;
        int m=mid+1;
        int k=l;
        long inv=0l;
        while(l<=mid && m<=r)
        {
            if(arr[l]<=arr[m])
            {
                temp[k]=arr[l];
                invfreq[temp[k]]+=inv;
                k++;
                l++;
            }
            else
            {
                temp[k]=arr[m];
                k++;
                m++;
                inv++;

            }

        }
        while(l<=mid){
            temp[k]=arr[l];
            invfreq[temp[k]]+=inv;
            k++;
            l++;
        }
        while(m<=r){
            temp[k]=arr[m];
            k++;
            m++;
        }

        for(int i1=i;i1<=j;i1++){
            arr[i1]=temp[i1];
            //System.out.print(arr[i1]+" ");
        }

    }

}

But my code is giving Time Limit Exceeded for test cases with large input files.

Short answer: creating - and garbage collecting - N arrays of size N takes some time, even if operator new[] has been tuned for exceptional performance (as is the case for Java and C#).

int temp[]=new int[arr.length];

Long answer: a detailed treatment of all the coding/performance sins inherent in the code offered for review would fill many pages. However, I'm leaving that for someone else and instead I'll focus only on the algorithmics, in a language-agnostic way.

Throwing needlessly complicated technology at a practice problem can be educational, if only to drive the lesson home that the technology in question is in fact not a good match for the problem and that other solutions require less effort. Hence, if a problem listed under ‘merge sort’ then one ought to also solve it via merge sorting, but the first call should always be the simplest solution that promises to do the job.

In this case, that simplest solution is using a Fenwick tree to count inversions. No fuss, no muss, solution (C#) accepted with 1.19 s combined time for all test files.

const int MAX_VALUE = 1000000;

for (int t = int.Parse(Console.ReadLine().Trim()); t-- > 0; )
{
    int n = int.Parse(Console.ReadLine().Trim());
    var a = new int[n];

    for (int i = 0; i < n; ++i)
        a[i] = int.Parse(Console.ReadLine().Trim());

    var fenwick = new int[1 + MAX_VALUE];
    var result = new int[n];

    for (int i = n - 1; i >= 0; --i)
    {
        int a_i = a[i], inversions = 0;

        for (int j = a_i; j > 0; j -= j & -j)
            inversions += fenwick[j];

        for (int j = a_i; j <= MAX_VALUE; j += j & -j)
            ++fenwick[j];

        result[i] = inversions;
    }

    Console.WriteLine(string.Join(" ", result));
}

Compare this to the reams of code necessary for the merge sorting approach.

According to the problem constraints, values can go ten times as high as indices (limit 10^6 instead of 10^5). This makes the Fenwick ten times as big as the biggest input array, increasing the average path lengths for the Fenwicking from not quite 9.5 to not quite 11.5. However, for small ranges such as these this inefficiency is negligible - the code is more than fast enough already.

For details on Fenwick trees see the Wikipedia article on Fenwicks and the related practice section on HackerEarth (which includes a tutorial; it's in the Data Structures section which you're supposed to work through before starting with Algorithms). As regards determining the average iteration counts for the Fenwick loops, I'd recommend doing a bit of Fenwicking with pen and paper (for a Fenwick of size 2^k it's k / 2 + 1).

As regards merge sorting: unlike Fenwicks, merge sorting does not give a flying meow about what the actual ranges of the input values are - all it does with the inputs is compare them. This makes the algorithm especially attractive when the value range diverges wildly from the value count. For example, Fenwicking 100000 longs would require sorting the inputs in order to ‘compress’ them to the range 1 to 100000, which requires O(N log N) of extra effort.

Merge sorting requires no such preprocessing, but since it destroys the original order of the values it requires extra effort for correlating the inversion counts thus found to the original inputs (e.g. the array copy[] in the original code). Also, it makes the code quite a bit more complicated than that using a Fenwick tree, and it would get hugely more complicated if the input values weren't guaranteed to be unique whereas the Fenwick couldn't care less about uniqueness.

Coding a top-down merge sort with recursive function calls - as opposed an iterative bottom-up version with nested loops - makes it more difficult to control certain aspects (e.g. optimal splitting instead of simple halving) and it makes it even more difficult to make sorted ranges end up precisely where they're needed, instead of resorting to redundant copying of values.

However, the recursive version has somewhat better cache locality and in any case it is more than fast enough for this problem, regardless of the redundant copying. In my benchmarks it took little more than twice as long as the simpler Fenwick and was only marginally slower than an iterative version (124 ms for 10^6 values recursive vs 110 ms iterative and 44 ms Fenwick). In a coding challenge it might pay to keep the differences in mind, but not for this simple practice problem.

Hence the only algorithmic fix required here is using a pre-allocated temp array large enough to hold the largest input. That's all.

import java.io.*;
import java.util.*;

class Puchi{

    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int count=0;
            int n=sc.nextInt();
            int a[]=new int[n];
            for(int j=0;j<n;j++){
                a[j]=sc.nextInt();
            }
            for(int k=0;k<n;k++){
                count=0;
                for(int m=k+1;m<n;m++){
                    if(a[k]>a[m]){
                        count++;

                    }
                }
                System.out.print(count+" ");

            }

        }
    }
}

output: 1 0 1 0

But when trying to submit it's getting partially accepted.


Hackerrank problem: Climbing the Leaderboard (Java) I am solving the following Hackerrank problem: Climbing the Leaderboard.
The problem statement:
Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

The player with the highest score is ranked number 1 on the leaderboard.
Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.

For example, the four players on the leaderboard have high scores of 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice's scores are 70, 80 and 105, her rankings after each game are 4th, 3rd and 1st.
Function Description
Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element res[j] represents Alice's rank after the jth game.
climbingLeaderboard has the following parameter(s):
scores: an array of integers that represent leaderboard scores
alice: an array of integers that represent Alice's scores
Input Format
The first line contains an integer n, the number of players on the leaderboard.
The next line contains n space-separated integers scores[i], the leaderboard scores in decreasing order.
The next line contains an integer, m, denoting the number games Alice plays.
The last line contains m space-separated integers alice[j], the game scores.
Constraints

1 <= n <= 2 * 10^5
1 <= m <= 2 * 10^5
0 <= scores[i] <= 10^9 for 0 <= i < n
0 <= alice[j] <= 10^9 for 0 <= j < m

The existing leaderboard, scores, is in descending order.
Alice's scores, alice, are in ascending order.
Subtask
For 60% of the maximum score:

1 <= n <= 200
1 <= m <= 200

Output Format
Print m integers. The jth integer should indicate Alice's rank after playing the jth  game.

My solution is failing to pass 4 test cases due to timeout. The code is as follows:
 import java.util.*;

    public class Main {
        public static void main(String[] args) {

            Scanner scanner = new Scanner(System.in);

            int totalPlayers = scanner.nextInt();
            ArrayList<Integer> playerScores = new ArrayList<>();
            for(int i = 0; i < totalPlayers; i++) {
                playerScores.add(scanner.nextInt());
            }

            int aliceTotalScores = scanner.nextInt();
            ArrayList<Integer> aliceScores = new ArrayList<>();
            for(int i = 0; i < aliceTotalScores; i++) {
                aliceScores.add(scanner.nextInt());
            }

            List<Integer> finalScores = new ArrayList<>(playerScores);
            for(int i = 0; i < aliceTotalScores; i++) {
                finalScores.add(aliceScores.get(i));
                finalScores.sort(Collections.reverseOrder());
                Set<Integer> set = new LinkedHashSet<>(finalScores);
                finalScores.clear();
                finalScores.addAll(set);
                System.out.println(finalScores.indexOf(aliceScores.get(i)) + 1);
            }
        }
    }

Any suggestions on how to improve the solution or some general direction as to where I am making a mistake would be appreciated. Thanks in advance.

I have some suggestions to make the code cleaner, not faster.
Always try to pass the size of the maximum size to the Collection / Map when known
The ArrayList has a default size of 10 elements, if you have more elements, the list will have to resize its internal pool. By setting the size, you can prevent the resize and make your code faster.
//[...]
int totalPlayers = scanner.nextInt();
ArrayList<Integer> playerScores = new ArrayList<>(totalPlayers);
//[...]
int aliceTotalScores = scanner.nextInt();
ArrayList<Integer> aliceScores = new ArrayList<>(aliceTotalScores);
//[...]

Always use the base class / interface in the left part of the variable when possible
By setting the java.util.List interface in the variable part, this could make the code more refactorable in the future, since you could easily change the list type without changing everything (inheritance).
Before
 ArrayList<Integer> playerScores = new ArrayList<>(totalPlayers);

After
 List<Integer> playerScores = new ArrayList<>(totalPlayers);

Replace the for loop with an enhanced 'for' loop
In your code, you don’t actually need the index provided by the loop, you can the enhanced version.
Before
for (int i = 0; i < aliceTotalScores; i++) {
   finalScores.add(aliceScores.get(i));
   finalScores.sort(Collections.reverseOrder());
   Set<Integer> set = new LinkedHashSet<>(finalScores);
   finalScores.clear();
   finalScores.addAll(set);
   System.out.println(finalScores.indexOf(aliceScores.get(i)) + 1);
}

After
for (Integer aliceScore : aliceScores) {
   finalScores.add(aliceScore);
   finalScores.sort(Collections.reverseOrder());
   Set<Integer> set = new LinkedHashSet<>(finalScores);
   finalScores.clear();
   finalScores.addAll(set);
   System.out.println(finalScores.indexOf(aliceScore) + 1);
}

Extract some of the logic to methods.
To remove some of the code of the main method, you could move both list instantiation (playerScores & aliceScores) to methods. Since the logic is similar, you could make only one method to read the inputs to a list and reuse the same for both cases.
public static void main(String[] args) {
   List<Integer> playerScores = getPlayerScores(scanner);
   List<Integer> aliceScores = getAliceScores(scanner);
}

private static List<Integer> getAliceScores(Scanner scanner) {
   return getIntegers(scanner);
}

private static List<Integer> getPlayerScores(Scanner scanner) {
   return getIntegers(scanner);
}

private static List<Integer> getIntegers(Scanner scanner) {
   int size = scanner.nextInt();
   List<Integer> integers = new ArrayList<>(size);
   for (int i = 0; i < size; i++) {
      integers.add(scanner.nextInt());
   }
   return integers;
}

or
public static void main(String[] args) {
   List<Integer> playerScores = getIntegers(scanner);
   List<Integer> aliceScores = getIntegers(scanner);
}

private static List<Integer> getIntegers(Scanner scanner) {
   int size = scanner.nextInt();
   List<Integer> integers = new ArrayList<>(size);
   for (int i = 0; i < size; i++) {
      integers.add(scanner.nextInt());
   }
   return integers;
}

Refactored code
public static void main(String[] args) {
   Scanner scanner = new Scanner(System.in);
   List<Integer> playerScores = getPlayerScores(scanner);
   List<Integer> aliceScores = getAliceScores(scanner);
   List<Integer> finalScores = new ArrayList<>(playerScores);

   for (Integer aliceScore : aliceScores) {
      finalScores.add(aliceScore);
      finalScores.sort(Collections.reverseOrder());
      Set<Integer> set = new LinkedHashSet<>(finalScores);
      finalScores.clear();
      finalScores.addAll(set);
      System.out.println(finalScores.indexOf(aliceScore) + 1);
   }
}

private static List<Integer> getAliceScores(Scanner scanner) {
   return getIntegers(scanner);
}

private static List<Integer> getPlayerScores(Scanner scanner) {
   return getIntegers(scanner);
}

private static List<Integer> getIntegers(Scanner scanner) {
   int size = scanner.nextInt();
   List<Integer> integers = new ArrayList<>(size);
   for (int i = 0; i < size; i++) {
      integers.add(scanner.nextInt());
   }
   return integers;
}

The below solution is simpler and it should pass all the test cases. You don't need the sorting techniques to solve this. Your code is quite complicated as you did a sort in each loop which is not needed at all. Here what we can do instead:
1- Use Set to remove duplicate scores
2- Use LinkedHashSet to keep the set in order state
3- Save the Set again to a List which helps us to get the index of each score
Refactor code
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    List<Integer> playerScores = getPlayerScores(scanner);
    List<Integer> aliceScores = getAliceScores(scanner);

    Set<Integer> uniqueScores = new LinkedHashSet<>(playerScores);
    playerScores = new ArrayList<>(uniqueScores);

    int i = playerScores.size() - 1;
    for (Integer oneScore : aliceScores) {
        while (i >= 0) {
            if (oneScore < playerScores.get(i)) {
                System.out.println(i + 2);
                break;
            }
            i--;
        }
        if (i < 0) {
            System.out.println(1);
        }
    }
}

private static List<Integer> getAliceScores(Scanner scanner) {
    return getIntegers(scanner);
}

private static List<Integer> getPlayerScores(Scanner scanner) {
    return getIntegers(scanner);
}

private static List<Integer> getIntegers(Scanner scanner) {
    int size = scanner.nextInt();
    List<Integer> integers = new ArrayList<>(size);
    for (int i = 0; i < size; i++) {
        integers.add(scanner.nextInt());
    }
    return integers;
}


Python REST API clients I am working on a project right now, where we need to search different APIs, then clean & persists data to database and finally pushing to Elasticsearch.

The high level code looks like this:

class BaseParser(object):

    def __init__(self, source):
        self.url = source.url
        self.api_key = source.api_key

    def _prepare_auth_header(self):
        headers = {
        "Authorization": "Basic {}".format(self.api_key)
        }
        return headers

    def get_response(self):
        raise NotImplementedError()

class UnitedexchangeParser(BaseParser):

    def get_response(self):
        headers = self._prepare_auth_header()
        response = requests.get(self.url, headers=headers)
        return response.json()

class DubaiParser(BaseParser):

    def get_response(self):
        headers = self._prepare_auth_header()
        response = requests.get(self.url, headers=headers)
        return response.json()["data"]

class ParserFactory(object):

    def parse(self, source):
        if source.name == "Unitedexchange":
            parser = Unitedexchange(source)

        elif source.name == "Dubai":
            parser = DubaiParser(source)

        return parser.get_response()

The application is working fine, but we are adding more and more new sources which leads to change ParserFactory with same block of code.

How can I improve the layout and design such a way so we do minimal change for adding new parser? Performance is also an issue, and right now we are loading lots of individual classes which basically doing the same thing. It would be great if you can give some hint on that, too.

A few small comments:

When not supplying any argument to an exception, the () can be skipped: raise NotImplementedError.
I'm assuming ParseFactory is actually longer, otherwise there would be no need for it to be a class. A parse function on its own would be perfectly fine.
It would be better to make a dictionary of parsers, especially if the number of parsers grows:

class ParserFactory(object):
    parsers = {"Unitedexchange": UnitedexchangeParser,
               "Dubai": DubaiParser}

    def parse(self, source):
        parser = ParserFactory.parsers[source.name]
        return parser.get_response()

This does not solve the problem of having to implement every parser.

If they are sufficiently similar, namely almost all have the same get_response, you could just put a standard implementation in BaseParser and use

class DubaiParser(BaseParser):
    pass

Or, you could use type to create those classes that do not need any modifications dynamically and put them in a dictionary:

parsers = {"DubaiParser": None, "OtherParser": None, ...}
for name in parsers:
    parser = type(name, (BaseParser,), {})
    parser.__module__ = __name__
    parsers[name] = parser

There is even the possibility to override some methods, but this only makes sense if there are two different implementations of get_response

def get_response_json(self):
    headers = self._prepare_auth_header()
    response = requests.get(self.url, headers=headers)
    return response.json()["data"]

other_methods = {"get_response": get_response_json}

parsers = {"DubaiParser": None, "OtherParser": None, ...}
different_get_response = {"OtherParser", ...}
for name in parsers:
    if name in different_get_response:
        parser = type(name, (BaseParser,), {}, lambda ns: ns.update(other_methods)
    else:
        parser = type(name, (BaseParser,), {})
    parser.__module__ = __name__
    parsers[name] = parser

The code you've posted does not look like some real code example so I don't see much of reasons to comment it.

To answer your question how to register parsers automatically you can use either metaclasses or decorators for it. I would not go for metaclass while I find it interesting to use, this makes you code hard to understand so I will show you how to do it using decorators.

PARSERS_MAP = {}

def register_parser(inner):
    PARSERS_MAP[inner.__name__] = inner
    return inner

@register_parser
class FooParser:
    pass

class ParserFactory(object):

    def parse(self, source):
        parser = PARSERS_MAP[source.name]
        return parser(source).get_response()

As for your second question about performance, to be  honest, I didn't get it. please show the code you are having problems with.


Testing whether a string contains valid JSON by calling json_decode() I had a code review and got told by the senior programmer that it was very bad programming practice to use the json_decode() function of php to determine if a string was not in JSON format.

My argument was that the json_decode function has a fail case (returning NULL) and this exists for reasons such as the purpose I was using it for.

I got sat down one on one and told to never pass data to a function that was not intended for the function (in this case referring to passing a hex string to the json_decode() function).

Is what I did bad coding practice? How should I have written the code?

Here is the php code of what I basically did:

//example JSON Data
/*
$ExampleData = '
{
    "test": "48656c6c6f20576f726c64"
}
';
*/

//the most common case is that a hex string sent to the php script
$ExampleData = "48656c6c6f20576f726c64";

$jsonData = json_decode($ExampleData);

//one in every 1000 responses is JSON data
if($jsonData)
{
    //extract varaibles from the json
    print ("JSON data recieved");
}
else
{
    //response is hex so carry out normal function
    print ("Hex Data recieved");
}

try it online

I strongly agree with comment by @Iwrestledabearonce.  When dealing with input, there are normally other means to understand content type (content type headers, additional input fields, or other means to express an explicit contract).  Having forked code paths like this probably means you have a bad design and you should make sure the contract with data source is clear around how to convey what type of data is being passed.  That doesn't mean that the data passed still doesn't need to be validated as hex or JSON input, just that you shouldn't have to rely on performing JSON decoding or regex matching to determine your input data type.

This is especially exacerbated by the fact you mention 1 in 1000 request may have JSON.  Do you really want to perform json_decode() step on all 999 other requests?

As I can only receive a string to this php file I ended up ended up using a packet.header decoded in to a php object from a string like so:

<?php
//example JSON Data
/*
$packet->header = "JSON";
$packet->data = '
{
    "test": "48656c6c6f20576f726c64"
}
';
*/

//the most common case is that a hex string sent to the php script
$packet->header = "HEX";
$packet->data = "48656c6c6f20576f726c64";

if ($packet->header == "HEX")
{
    //do validation and process data
    print ("HEX data recieved");
}
elseif ($packet->header == "JSON")
{
    //do validation and process data
    print ("JSON data recieved");
}
else
{
    //data is not expected data or data is corrupt
}

?>

What does everyone think of this solution?


Find max number you can create from an array of numbers Was asked this in an interview yesterday:

You are given an array of numbers (not digits, but numbers: e.g. 9, 23, 184, 102, etc.) - you need to construct the largest number from it. For example: you get 21, 2, 10 - the largest number is 22110.

This is my solution, I wonder if you can improve this?

def maximum_number(a):
    work_dict = {
        0: 0,
        1: 0,
        2: 0,
        3: 0,
        4: 0,
        5: 0,
        6: 0,
        7: 0,
        8: 0,
        9: 0
    }

    for ai in a:
        # if ai is a single digit number, just add it
        if ai in work_dict:
            work_dict[ai] += 1
            continue

        # otherwise, decompose it to it's digits
        while ai > 0:
            number = ai % 10
            work_dict[number] = work_dict[number] + 1
            ai = int(ai/10)

    max_num = int('9'*work_dict[9] + '8'*work_dict[8] + '7'*work_dict[7] + '6'*work_dict[6] +
                    '5'*work_dict[5] + '4'*work_dict[4] + '3'*work_dict[3] + '2'*work_dict[2] +
                    '1'* work_dict[1] + '0'*work_dict[0])

    return max_num

Your code

Your code as such seems to be functional, but not really elegant or concise.

First, the variable names don't speak for themselves. Nobody would be hurt if the function input was named numbers instead of a and number instead of ai. work_dict is also  not a particularly good name since it's very generic. How about digit_histogram?

Handling single digit numbers separately seems unnecessary. The algorithm you implemented can handle them without special treatment.

When constructing max_num, there is a lot of repeated code. You could simplify this using a list comprehension and join (more on that soon).

How I would have tackled this

Since we have the luxury that combination of these numbers should be maximized in base 10, we can get their digits simply by looking at their str representation (which coincidentally happens to be in base 10 ;-) )1.

If you include the other recommendations from above you end up with:

def maximum_number_str(arr):
    digit_histogram = {
        "0": 0, "1": 0, "2": 0, "3": 0, "4": 0,
        "5": 0, "6": 0, "7": 0, "8": 0, "9": 0
    }
    # or: digit_histogram = {str(i): 0 for i in range(10)}

    for number in arr:
        for digit in str(number):
            digit_histogram[digit] += 1

    max_num = "".join(str(i)*digit_histogram[str(i)] for i in reversed(range(10)))

    return int(max_num)

Depending on how familiar you are with Python and if other modules are allowed, you could come up with a solution using collections.Counter, or at least skip the dict initialization all-together if you use .get(...) instead of [...] when accessing the dictionary as presented by Pål GD in is answer.

Just for reference, this is how it could look like using a Counter:

from collections import Counter

def maximum_number_counter(arr):
    digit_histogram = Counter()

    for number in arr:
        digit_histogram.update(str(number))

    max_num = "".join(
        str(i) * digit_histogram[str(i)] for i in reversed(range(10)))

    return int(max_num)

Edit: The other way to think about that task

There seems to be a vivid discussion here if you understood the task correctly. If you follow the arguments that speak against your and my former interpretation, this actually leads to another interesting problem.

I came up with the solution below, though I highly doubt that I could have come up with this in an interview situation.

from functools import cmp_to_key

def maximize_joint_number(number1, number2):
    joined12 = int(str(number1)+str(number2))
    joined21 = int(str(number2)+str(number1))
    return joined21 - joined12

def maximum_number(numbers):
    """
    Generate the largest possible number that can be generated rearanging the
    *numbers*, not the digits of the input sequence
    """
    return int("".join(str(i) for i in sorted(numbers, key=cmp_to_key(maximize_joint_number))))

The idea to this is actually from this blog post that was given in a comment by Eric Duminil. The cmp_to_key trickery is needed because the cmp keyword was removed from sort in Python 3. You could also use cmp_to_key as a decorator, which makes it a little bit nicer:

from functools import cmp_to_key

@cmp_to_key
def maximize_joint_number(number1, number2):
    ...

def maximum_number(numbers):
    return int("".join(str(i) for i in sorted(numbers, key=maximize_joint_number)))

A quick test seems to fulfill all the presented example outputs:

if __name__ == "__main__":
    assert maximum_number([0, 12]) == 120
    assert maximum_number([2, 21, 10]) == 22110
    assert maximum_number([9, 2, 5, 51]) == 95512
    assert maximum_number([20, 210, 32]) == 3221020
    assert maximum_number([1, 19, 93, 44, 2885, 83, 379, 3928]) == 93834439283792885191

The second and third test case break implementations that would try to use something like sorted(numbers, key=str, reverse=True) (lexicographical sort) directly.

1 Thanks to Peter Cordes for pointing out the inaccurate wording here in earlier revisions.

Here's what I came up with. It runs in O(n) because of the for each loop, and seems to be a nice readable option to me.

numberList = [1, 19, 93, 44, 2885, 83, 379, 3928]

def largestNumber(value):
    string = ''
    for number in value:
        string = string + str(number)
    result = ''.join(sorted(string, reverse=True))
    return(int(result))

print(largestNumber(numberList))

Output: 99998888754433332211

Your solution works in the same time complexity, so they are both on the same page in that regard, but stringing the values together and using python's built in sorting function saves some space and complexity.


Generate random numbers without repetitions I want to generate a list of N different random numbers:

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>();

    for (int i=0; i<count; i++)
    {
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

But I feel there is a better way.  This do...while loop especially makes this ugly. Any suggestions on how to improve this?

Updated answer in response to bounty: See Is that your final answer? at the end, and other changes - basically answer is significantly rewritten.

To break your problem down in to requirements:

you need a set of random numbers
the numbers need to be unique
the order of the returned numbers needs to be random

Your current code indicates that the range of random numbers is specified by Random.Next(), which returns values in the [0 .. Int32.MaxValue) range (note, it excludes Int32.MaxValue). This is significant for the purpose of this question, because other answers have assumed that the range is configurable, and 'small'.

If the range should be configurable, then the recommended algorithm would potentially be much larger.

Based on those assumptions, let's do a code review...

Code Style

do ... while

The most glaring problems here are the un-braced do-while loop. You already knew it, but this code is ugly:

    do number = random.Next();
    while (randomNumbers.Contains(number));

It really should be braced:

    do
    {
        number = random.Next();
    } while (randomNumbers.Contains(number));

This makes the statement clear, and significantly reduces confusion. Always use braces for 1-liners.

List Construction

The List class allows an initial capacity to be used. Since the capacity needs to just be count, it makes sense to initialize the list with this capacity:

List<int> randomNumbers = new List<int>(count);

Current Algorithm

This is where the most interesting observations can be made. Let's analyze your current algorithm:

Create a container for the results
repeat until you have selected N values:

Select a random value
check if it has been previously selected
if it is 'new', then add it to the container

This algorithm will produce random values, in a random order, and with good random characteristics (no skews, biases, gaps, etc.).

In other words, your results are good.

The problem is with performance....

There are two performance concerns here, one small, the other large:

the do-while loop to avoid collisions
the List container

do-while performance

The do-while has a very low impact on performance... almost negligible. This is hotly debated, but, the reality is that you would need a very, very large count before this becomes a problem. The reasoning is as follows:

Collisions happen when the random value was previously selected. For the specified range of [0 .. Int32.MaxValue), you would need a very large count before collisions actually happened. For example, count would have to be about 65,000 before there was better than a 50% chance that there was even a single collision.

In a general sense, given a Range of \$N\$, select \$M\$ numbers. If \$M < \sqrt{N}\$ then the probability of a single collision is < 50%. Since the Range is very large, the probability is small.

Obviously, if the range was small, then the probabilities would be significantly affected. But the range is fixed at Int32.MaxValue, so that's OK.

Additionally, if the count was large, then the probabilities would also be affected. How large would be very large? Well, you would be running in to very large arrays before you run in to significant problems..... I would venture you are hitting close to \$\frac{Int32.MaxValue}{2}\$ before you run in to a significant issue with performance.

List performance

This is without doubt your largest concern. You use the randomNumbers.Contains(number) call to determine whether a value was previously selected. This requires a scan of all previously-selected values to determine. As mentioned, this will almost always return false, and will thus have to scan the entire list.

As the count value increases, the length of time to perform the Contains will increase at an quadratic rate, \$O(n^2)\$ where n is count.

This performance problem will become critical much sooner than the random-collision problem.

Putting it together

The problem you have in your code is that you are trying to do too much at once, you are using a List because that is your return value, when a HashSet would be better. If you break the problem down in to stages, you will be able to solve things more elegantly.

If you add a duplicate value to a HashSet, it does not grow, and the operation performance is not dependent on the amount of data in the HashSet (it is \$O(1)\$). You can use the Count of the HashSet to manage the data uniqueness.

Once you have a clean set of unique random numbers, you can dump them in to a List, then shuffle the list using an efficient shuffle.

Combining these data structures, in the right way, leads to an overall \$O(n)\$ solution, which will scale fairly well.

Here is some code, which works in Ideone too. Note, my C# is weak, so I have tried to make the logic clear.

using System;
using System.Collections.Generic;

public class Test
{
    static Random random = new Random();

    public static List<int> GenerateRandom(int count)
    {
        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();
        while (candidates.Count < count)
        {
            // May strike a duplicate.
            candidates.Add(random.Next());
        }

        // load them in to a list.
        List<int> result = new List<int>();
        result.AddRange(candidates);

        // shuffle the results:
        int i = result.Count;
        while (i > 1)
        {
            i--;
            int k = random.Next(i + 1);
            int value = result[k];
            result[k] = result[i];
            result[i] = value;
        }
        return result;
    }
    public static void Main()
    {
        List<int> vals = GenerateRandom(10);
        Console.WriteLine("Result: " + vals.Count);
        vals.ForEach(Console.WriteLine);
    }
}

The above code is my initial recommendation, and it will work well, and scale well for any reasonable number of values to return.

Second Alternate Algorithm

The problem with the above algorithm is threefold:

When count is very large, the probability of collision is increased, and performance may be affected
Data will need to be in both the HashSet and the List at some point, so the space usage is doubled.
The shuffle at the end is needed to keep the data in a random order (HashSet does not keep the data in any specific order, and the hashing algorithm will cause the order to become biased, and skewed).

These are only performance issues when the count is very large. Note that only the collisions at large count will impact the scalability of the solution (at large count it is no longer quite \$O(n)\$, and it will be come progressively worse when count approaches Int32.MaxValue. Note that in real life this will not likely ever happen.... and memory will become a problem before performance does.

@JerryCoffin pointed to an alternate algorithm  from Bob Floyd, where a trick is played to ensure that collisions never happen. This solves the problem of scalability at very large counts. It does not solve the need for both a HashSet and a List, and it does not solve the need for the shuffle.

The algorithm as presented:

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

assumes that RandInt(1, J) returns values inclusive of J.

To understand the above algorithm, you need to realize that you choose a random value from a range that is smaller than the full range, and then after each value, you extend that to include one more. In the event of a collision, you can safely insert the max because it was never possible to include it before.

The chances of a collision increase at the same rate that the number of values decreases, so the probability of any one number being in the result is not skewed, or biased.

Is this almost a final answer? No

So, using the above solution, in C#, would look like (in Ideone) (note, code is now different to Ideone):

public static List<int> GenerateRandom(int count)
{
    // generate count random values.
    HashSet<int> candidates = new HashSet<int>();
    for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++)
    {
        Console.WriteLine(top);
        // May strike a duplicate.
        if (!candidates.Add(random.Next(top + 1)))
        {
            candidates.Add(top);
        }
    }

    // load them in to a list.
    List<int> result = candidates.ToList();

    // shuffle the results:
    int i = result.Count;
    while (i > 1)
    {
        i--;
        int k = random.Next(i + 1);
        int value = result[k];
        result[k] = result[i];
        result[i] = value;
    }
    return result;
}

Note that you need to shuffle the results still, so that the HashSet issue is resolved. Also note the need to do the fancy loop-condition top > 0 because at overflow time, things get messy.

Can you avoid the shuffle?

So, this solves the need to do the collision loop, but, what about the shuffle. Can that be solved by maintaining the HashSet and the List at the same time. No! Consider this function(in Ideone too):

public static List<int> GenerateRandom(int count)
{
    List<int> result = new List<int>(count);

    // generate count random values.
    HashSet<int> candidates = new HashSet<int>();
    for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++)
    {
        // May strike a duplicate.
        int value = random.Next(top + 1);
        if (candidates.Add(value))
        {
            result.Add(value);
        }
        else
        {
            result.Add(top);
            candidates.Add(top);
        }
    }

    return result;
}

The above answer is never going to allow the first value in the result to have any of the Max - Count to Max values (because there will never be a collision on the first value, and the range is not complete at that point), and this is thus a broken random generator.

Even with this collision-avoiding algorithm, you still need to shuffle the results in order to ensure a clean bias on the numbers.

TL;DR

Is This Your Final Answer? Yes!

Having played with this code a lot, it is apparent that it is useful to have a range-based input, as well as a Int32.MaxValue system. Messing with large ranges leads to potential overflows in the 32-bit integer space as well.

Working with @mjolka, the following code would be the best of both worlds:

    static Random random = new Random();

    // Note, max is exclusive here!
    public static List<int> GenerateRandom(int count, int min, int max)
    {

        //  initialize set S to empty
        //  for J := N-M + 1 to N do
        //    T := RandInt(1, J)
        //    if T is not in S then
        //      insert T in S
        //    else
        //      insert J in S
        //
        // adapted for C# which does not have an inclusive Next(..)
        // and to make it from configurable range not just 1.

        if (max <= min || count < 0 ||
                // max - min > 0 required to avoid overflow
                (count > max - min && max - min > 0))
        {
            // need to use 64-bit to support big ranges (negative min, positive max)
            throw new ArgumentOutOfRangeException("Range " + min + " to " + max +
                    " (" + ((Int64)max - (Int64)min) + " values), or count " + count + " is illegal");
        }

        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();

        // start count values before max, and end at max
        for (int top = max - count; top < max; top++)
        {
            // May strike a duplicate.
            // Need to add +1 to make inclusive generator
            // +1 is safe even for MaxVal max value because top < max
            if (!candidates.Add(random.Next(min, top + 1))) {
                // collision, add inclusive max.
                // which could not possibly have been added before.
                candidates.Add(top);
            }
        }

        // load them in to a list, to sort
        List<int> result = candidates.ToList();

        // shuffle the results because HashSet has messed
        // with the order, and the algorithm does not produce
        // random-ordered results (e.g. max-1 will never be the first value)
        for (int i = result.Count - 1; i > 0; i--)
        {
            int k = random.Next(i + 1);
            int tmp = result[k];
            result[k] = result[i];
            result[i] = tmp;
        }
        return result;
    }

    public static List<int> GenerateRandom(int count)
    {
        return GenerateRandom(count, 0, Int32.MaxValue);
    }

List contains is \$O(n)\$. HashSet contains is \$O(1)\$.

private static Random rand = new Random();
public static IEnumerable<int> GetRandomNumbers(int count)
{
    HashSet<int> randomNumbers = new HashSet<int>();
    while(randomNumbers.Count < count)
    {
        int r = rand.Next();
        if (randomNumbers.Add(r))
            yield return r;
    }
}


Bottom up merge sort in Haskell Although this sort works on Int lists < length million, when the stack overflows, the last clause of the merge function definition looks odd to me, recursing in 2 places. Is there clearer way to define that definition and how can the stack limitation be avoided?

msort :: Ord a => [a] -> [a]
msort [] = []
msort xs = concat . merge . split $ xs

merge :: Ord a => [[a]] -> [[a]]
merge [] = []
merge [x] = [x]
merge (l1:l2:ls) = merge $ mpair l1 l2 : merge ls

mpair :: Ord a => [a] -> [a] -> [a]
mpair [] l2 = l2
mpair l1 [] = l1
mpair l1@(x:xs) l2@(y:ys) | x >= y     = x : mpair xs l2
                          | otherwise  = y : mpair l1 ys

split :: [a] -> [[a]]
split xs = [[x]| x<-xs]

You've spotted the problem. Your merge function is flawed.  For each pair it processes, it introduces an extra unnecessary call to merge.  That is, for a list like [1,2,3,4,5,6], instead of your first merge call expanding directly to:

merge [[1],[2],[3],[4],[5],[6]]
= merge $ mpair [1] [2] : mpair [3] [4] : mpair [5] [6] : []

it expands to:

merge [[1],[2],[3],[4],[5],[6]]
= merge $ mpair [1] [2] : merge $ mpair [3] [4]
  : merge $ mpair [5] [6] : merge []

As a result, your count of merge calls is O(n) and your count of mpair calls is O(n^2) (or similar -- I didn't check exactly). when they should be O(log n) and O(n log n) respectively.

Instead, you want to split merge up into two functions:

merge :: Ord a => [[a]] -> [[a]]
merge [] = []
merge [x] = [x]
merge ls = merge (mergePairs ls)

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs (l1:l2:ls) = mpair l1 l2 : mergePairs ls
mergePairs ls = ls

This will speed up the algorithm enormously, and it will now run on tens of millions of integers.

See mergeAll.

They insert a bang to adjust the evaluation order, and push the second recursion down into the next definition.

You could experiment with the mutant offspring of the two implementations to try and understand reasons for their difference.


Word Pattern challenge in LeetCode I solved this problem from LeetCode:

  Given a pattern and a string str, find if str follows the same
  pattern.

  Here follow means a full match, such that there is a bijection between
  a letter in pattern and a non-empty word in str

  Examples:

  pattern = "abba", str = "dog cat cat dog" should return true.

  pattern = "abba", str = "dog cat cat fish" should return false.

  pattern = "aaaa", str = "dog cat cat dog" should return false.

  pattern = "abba", str = "dog dog dog dog" should return false.

  Notes:

  You may assume pattern contains only lowercase letters, and str
  contains lowercase letters separated by a single space.

I was able to solve this problem by using a Dictionary to keep track of the relation between the pattern and the str:

public class Solution {
public bool WordPattern(string pattern, string str)
    {
        var result = str.Split(' ').ToList();
        var mapPattern = new Dictionary<char, string>();
        if (result.Count != pattern.Count())
        {
            return false;
        }
        string matchstr;
        int index = 0;
        foreach (var c in pattern)
        {
            if (mapPattern.TryGetValue(pattern[index], out matchstr))
            {
                if (matchstr != result[index])
                {
                    return false;
                }
            }
            else
            {
                if(mapPattern.ContainsValue(result[index]))
                {
                    return false;
                }
                mapPattern.Add(c, result[index]);
            }
            ++index;
        }
        return true;
    }
}

The approach I have currently looks up the Dictionary twice to see if it already exists as a key or as a value in the Dictionary, which I believe would be the reason for slowing this by a significant amount.

Can you determine if I can do away with looking up twice? This solution only runs better than around 36% of the other submissions for this current problem. So, I believe there must be a better and faster way.

Overall, this is a nice, clean solution, congratulations!

Performance

  Can you suggest If I can do away with looking up twice. Currently this solution only runs better that around 36% of the other submissions for this current problem. So, I believe there must be a better and faster way.

"Looking up twice" is not the appropriate term. You do one lookup by key, and another lookup by value. These are very different operations, and lumping them together as "two lookups" hides important details. Imagine a program that does one lookup in an array and one lookup with a Google search on the internet, and the author would wonder if slowness might be caused by doing "two lookups". It would hide a crucial detail that one of the "lookups" is clearly much slower than the other.

The lookup in the dictionary by key is very fast, an \$O(1)\$ operation.

The lookup by value in a typical dictionary (or hash map) implementation is much slower, \$O(n)\$, because dictionaries are indexed by key, not by value. They are designed for fast lookups by key, not by value.

To make the lookup by value faster, you can add a set for values.

Scope

It's good to limit the scope of variables to the minimum needed.

matchstr should be declared inside the loop, as it is not needed outside
mapPattern should be initialized after the early return, as it might not be needed

Not much but you could change index

foreach (int index = 0; index < pattern.Count; index++)
{

Use a HashSet to store current values

A related approach with no O(n) lookup

public static bool PatterMatch(string pattern, string match)
{
    Dictionary<char, int> dlPattern = new Dictionary<char, int>();
    Dictionary<string, int> dlMatch = new Dictionary<string, int>();
    List<int> lPattern = new List<int>();
    List<int> lMatch = new List<int>();
    int index = 0;
    int indexOut;
    foreach(char p in pattern.ToCharArray())
    {
        if (dlPattern.TryGetValue(p, out indexOut))
        {
            lPattern.Add(indexOut);
        }
        else
        {
            dlPattern.Add(p, index);
            lPattern.Add(index);
            index++;
        }
    }
    index = 0;
    foreach (string m in match.Split(' '))
    {
        if (dlMatch.TryGetValue(m, out indexOut))
        {
            lMatch.Add(indexOut);
        }
        else
        {
            dlMatch.Add(m, index);
            lMatch.Add(index);
            index++;
        }
    }
    return lPattern.SequenceEqual(lMatch);
}


Classify the urgency by comparing the current time to two timestamps I'm currently working on a typescript-class with this method:

  /**
   * Gets the state of a package. The state is determined based on two timestamps stored as fields in the {@link
    * Package}. As the current time equals or passes a timestamp, the state changes.
   *
   * @param currentTime The time to compare the timestamps with
   * @param sourcePackage The package containing the two timestamps to compare the currentTime with
   * @returns {CardState} The calculated state of the package
   */
  static determineStateOfPackage(currentTime: Date, sourcePackage: Package): CardState {
    if (sourcePackage.targetTime.getTime() <= currentTime.getTime()) {
      return CardState.URGENT;
    }
    if (sourcePackage.warningTime.getTime() <= currentTime.getTime()) {
      return CardState.WARNING;
    }
    return CardState.FRIENDLY;
  }

It bugs me that the two ifs are repetitive but I can't really figure out how to improve this. How can I improve this code especially to avoid calling the two ifs with nearly the same content twice?

A couple notes:

Is CardState an enum?  If not, this function doesn't return a CardState object, but rather what appears to be values described within CardState class constants.  Your signature should reflect this.
I honestly don't think it is that problematic to have multiple if conditions as you are doing, as your usage is not increasing cyclomatic complexity of the method.  Now, if you started introducing new states, then it may get unwieldy and be good reason for refactoring.  As your code is now, it is very straightforward and easy to understand.  Why over-complicate?
Is currentTime a good variable name?  This method does nothing to ensure the passed Date object represents a time that is "current". Why name this variable *Time when it holds a Date object?
Consider less verbose determinePackageState vs. determineStateOfPackage package vs. sourcePackage.
You could possibly set getTime() value to constant in order to remove redundant calls (though this is probably splitting hairs).

This might result in (slightly) easier to read code such as:

  static determinePackageState(date: Date, package: Package): CardState {
    const timestamp: number = date.getTime();
    if (package.targetTime.getTime() <= timestamp) {
      return CardState.URGENT;
    }
    if (package.warningTime.getTime() <= timestamp) {
      return CardState.WARNING;
    }
    return CardState.FRIENDLY;
  }

Step 1: method extractions

At the very minimum, you can always extract the reusable(repeated) part of the code into an independent method and give it a proper self-explanatory name. This will not necessarily reduce the number of lines of resulting code, however, it will isolate (encapsulate) the specific logic in a single place which is a good achievement on its own

export class CardStateSelector {
  static determineStateOfPackage(currentTime: Date, sourcePackage: Package): CardState {
    if (CardStateSelector.isTimeCritical(currentTime, sourcePackage.targetTime)) {
      return CardState.URGENT;
    }
    if (CardStateSelector.isTimeCritical(currentTime, sourcePackage.warningTime)) {
      return CardState.WARNING;
    }
    return CardState.FRIENDLY;
  }

  private static isTimeCritical(currentTime: Date, baseTime: Date): boolean {
    return baseTime.getTime() <= currentTime.getTime()
  }
}

Step 2: applying the Strategy pattern [optional]

In your particular case applying the Strategy design pattern would be an overkill. However, if your code had more branching, or had more complex branch selection logic, or had heavier logic in branch(es), or a combination of those, I'd consider using Strategy.

This answer may be a good illustration of the pattern application in a situation similar to yours.

Update 1

ifs are just very nasty code smell. They should be avoided when the things start being complicated. There's even a small anti-if movement.

P.S.

Let me know if you want to see some pseudo-code or more real code for the Step 2.


Change a string into a function/def activator import random

import string

# every def from 'def nothing()' to 'def wxyz()' Print out several lines of text, printing: keyword 1, call number, phone number and keyword 2
def nothing():
    print("keyword: (nothing)\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def abc():
    print("keyword: abc\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def deft():
    print("keyword: deft\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def ghi():
    print("keyword: ghi\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def jkl():
    print("keyword: jkl\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def mno():
    print("keyword: mno\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def pqrs():
    print("keyword: pqrs\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def tuv():
    print("keyword: tuv\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

def wxyz():
    print("keyword: wxyz\ncalls: 1\n" + str(random_number()) + "\nkeyword: exit\n")

# keywords that are accepted and not denied
accepted_keywords = {
    0: nothing,
    1: abc,
    2: deft,
    3: ghi,
    4: jkl,
    5: mno,
    6: pqrs,
    7: tuv,
    8: wxyz
}

# creates a random phone number
def random_number():
    string = []
    x = 0
    while x != 10:
        x += 1
        number = str(random.randrange(0, 10))
        string.append(number)
    return str('(' + string[0] + string[1] + string[2] + ')' + string[3] + string[4] + string[5] + '-' + string[6] + string[7] + string[8] + string[9])

# these two things pick a random value & key from the accepted_keywords() dictionary then calls that value & key
#tester = random.randrange(len(accepted_keywords))
#accepted_keywords[tester]()

# randomizes letter so it can be aproved or denied
def random_keyword():
    keyword = ''
    chrt_count = random.choice([3,4])
    for i in range(chrt_count):
        lowercase = string.ascii_lowercase #lowercase letters
        random_letter = random.randrange(len(lowercase)) # chooses random character from var lowercase which is converted to a number based on its place in alphabet
        keyword_letter = lowercase[random_letter] # grabs the letter from lower using the number from var random_letter to located the place value of a letter
        keyword += keyword_letter
    while True:
        if keyword in accepted_keywords.values():
            print("keyword: " + keyword + "\n*Approved*\n")
            break
        else:
            print("keyword: " + keyword + "\nDenied\n")
            break

random_keyword()

Here is the scenario, I am using python 3.x and I am supposed use cases but since Python does not use cases, I had to use a dictionary.
My problem is that I have a function named wxyz() and I created another function named random_keyword that picks random letters from the alphabet, one at a time, and adds it into a variable named keyword that is a blank string. So by the time random_keyword has ran its course, keyword will have 3 or 4 random letters in it. For now let’s say that those random letters are “wxyz”, which is a string. Then I go through if keyword in accepted_key: print .... The problem is that keyword is a string, therefore it does not match the wxyz in accepted_keywords. Is there a way to turn a string into a function/def activator?

There are quite a lot of things you should do differently.

Let's start with your function random_number. You should not overwrite the string module (even though it is only locally), which you imported. You should also use list comprehensions to build the string. To pretty print the number as a phone number, use str.format. Use the fact that random.randrange takes an implicit 0 as its first argument (just like range). And finally use tuple unpacking, instead of manually indexing the list.

def random_number():
    phone_number = [random.randrange(10) for _ in range(10)]
    return "({}{}{}){}{}{}-{}{}{}".format(*phone_number)

Next, your random_keyword function. You can vastly simplify the building of random_letter by using a list comprehension again, together with str.join, to avoid costly string addition.

Your while True loop also serves no purpose, since you break it in either case.

Also, what is the point of storing something in a dictionary (with \$\mathcal{O}(1)\$ lookup time if a key is in it) and then checking to see if something is in the values, which is a list and takes therefore \$\mathcal{O}(n)\$? At this point your dictionary is just a simple list. You can access its members with numbers from 0 to len(accepted_keywords). Instead have a list of your functions and have a dictionary with their names as keys (which you can build using a dictionary comprehension).

functions = [nothing, abc, deft, ghi, jkl, mno, pqrs, tuv, wxyz]
accepted_keywords = {f.__name__: f for f in functions}

def random_keyword():
    keyword = ''.join(random.choice(string.ascii_lowercase)
                      for _ in range(random.choice([3, 4])))
    print("keyword: {}".format(keyword))
    print("*Approved*\n" if keyword in accepted_keywords else "Denied\n")

Finally, Python has an official style-guide, PEP8. It recommends using ALL_CAPS for global constants (like accepted_keywords).

Python also has a docstring convention (written down in PEP257), which in its simplest form looks something like the following:

def random_number():
    """creates a random phone number"""
    ...

At this point you should also notice that that function name is not very descriptive, maybe something like random_phone_number instead?


String compression function in python code I need to create a function called compress that compresses a string by replacing any repeated letters with a letter and number. Can someone suggest a better way to do this?

s=input("Enter the string:")
temp={}
result=" "
for x in s:
    if x in temp:
        temp[x]=temp[x]+1
    else:
        temp[x]=1
for key,value in temp.items():
    result+=str(key)+str(value)
        print(result)

Encapsulate your code into functions

Your code is neither reusable nor testable, wrap it into a function and call it from under an if __name__ == '__main__' guard. This will allow you to test it more easily. You will also be able to return values instead of printing them, this will make the code more reusable:

def compress(string):
    temp={}
    result=" "
    for x in string:
        if x in temp:
            temp[x] = temp[x]+1
        else:
            temp[x] = 1
    for key, value in temp.items():
        result += str(key) + str(value)

    return result

if __name__ == '__main__':
    s = input("Enter the string:")
    print(compress(s))

You can then jump into an interactive shell and type:

>>> from your_file_name import compress
>>> compress('aaabbccccddefg')
 a3b2c4d2e1f1g1
>>> compress('b'*42)
 b42

Use existing data structures

collections.Counter offers simplified ways of counting elements of an iterable:

from collections import Counter

def compress(string):
    temp = Counter()
    result = " "
    for x in string:
        temp[x] += 1

    for key, value in temp.items():
        result += str(key) + str(value)
    return result

if __name__ == '__main__':
    s = input("Enter the string:")
    print(compress(s))

You can even simplify further as Counter can take any iterable in its constructor. You can also use str.join to simplify even further:

from collections import Counter

def compress(string):
    counts = Counter(string)
    return ''.join(letter+str(count) for letter, count in counts.items())

if __name__ == '__main__':
    print(compress(input("Enter the string: ")))

Possible bug

To me, compressing a string mean having a mean to decompress it back. Using a dictionnary keyed by each letter as you do, you lost an important information: which letter is next to which one. Also 'aabaabaabaa' will be compressed to 'a8b3' which, to me, doesn't make sense and would be better as 'a2b1a2b1a2b1a2'. But I might be wrong. In this case, itertools.groupby is much more usefull as it will keep the ordering and avoid aggregating separate groups of letters:

import itertools

def compress(string):
    return ''.join(
            letter + str(len(list(group)))
            for letter, group in itertools.groupby(string))

if __name__ == '__main__':
    print(compress(input("Enter the string: ")))

This could be one of the way to do it:

count = 1
for i in range(1, len(input) + 1):
    if i == len(input):
        print(input[i - 1] + str(count), end="")
        break
    else:
        if input[i - 1] == input[i]:
            count += 1
    else:
            print(input[i - 1] + str(count), end="")
            count = 1


Get the brightest rectangle within an image I wrote an extension method for bitmaps which finds the brightest rectangle (with specified width & height) within an image.

Hopefully my code comments eliminate any confusion. If not, please let me know what I need to elaborate on.

I would like some help reducing repetitive calls to the conjoined Bitmap.GetPixel & Color.GetBrightness methods during the scanning process. (subsequently improving performance tremendously)

Method:

    public static Rectangle GetBrightestRectangle(this Bitmap bitmap, int width, int height)
    {
        // Each rectangle's value is its average pixel color.
        var rectangles = new Dictionary<Rectangle, float>();

        // Iterate through all possible rectangle points.
        for (var x = 0; x < bitmap.Width - width; x++)
            for (var y = 0; y < bitmap.Height - height; y++)
            {
                var brightnesses = new List<float>();

                // Iterate through all rectangle pixels.
                for (var w = x; w < x + width; w++)
                    for (var h = y; h < y + height; h++)
                    {
                        brightnesses.Add(bitmap.GetPixel(w, h).GetBrightness());
                    }

                rectangles.Add(new Rectangle(x, y, width, height), brightnesses.Average());
            }

        // The brightness ranges from 0.0 through 1.0, where 0.0 represents black and 1.0 represents white.
        return rectangles.OrderByDescending(pair => pair.Value).First().Key;
    }

Demo:

        var bitmap = (Bitmap)Image.FromFile(@"C:\Steve.png");
        var stopwatch = Stopwatch.StartNew();
        var brightestRectangle = bitmap.GetBrightestRectangle(50, 25);
        stopwatch.Stop();
        using (var graphics = Graphics.FromImage(bitmap))
        {
            graphics.DrawRectangle(new Pen(Color.Lime, 5), brightestRectangle);
        }
        bitmap.Save(@"C:\Jobs.png");
        Console.WriteLine($"bitmap.Size: {bitmap.Size}");
        Console.WriteLine($"brightestRectangle: {brightestRectangle}");
        Console.WriteLine($"stopwatch.Elapsed.Seconds: {stopwatch.Elapsed.Seconds}");

Steve.png

Jobs.png

  bitmap.Size: {Width=500, Height=500}

  brightestRectangle: {X=194,Y=99,Width=50,Height=25}

  stopwatch.Elapsed.Seconds: 37

Performance

Here is one simple suggestion, which doesn't require any real thought, and is simple enough to implement. It will result in only calling GetPixel once per pixel, but obviously has some other costs.

Instead of convolving a whole w*h rectangle over the image, first compute the sum of each horizontal strip of length w and store it in a buffer (essentially the same size as the image). Then compute the average of each h tall vertical strip in this buffer, each of which represents a w*h rectangle in the original image.

My only hesitation with suggesting this, is that currently you seem to deliberately call Average on a collection of pixels, which could give you slightly different results owing to joys of float-point maths (assuming nothing about the implementation). Any such error would, however, be imperceptible, but we don't know what your application is, so it is not for us to say that this isn't an issue (but I would wager it isn't).

Because this is just as an example, and I don't know much about floating point maths, I'll follow suit with the OP and only ever perform additions: I'll keep a queue (e.g. ring buffer) of elements as we scan across and down. You could instead keep a running sum, instead of computing sums over a queue, which would make the algorithm complexity order 2 rather than order 3 (the code in the OP is order 4). This is probably the most sensible change if performance is a serious concern, but I'll let you work out the changes necessary.

I'll ignore the joys of considering the actual memory layout of bitmaps: it might be better to sum across the columns first, and then the width, but I can't remember.

int hSumWidth = bitmap.Width - rectWidth + 1;
int hSumHeight = bitmap.Height;
float[,] hSums = new float[hSumWidth, hSumHeight];

Queue<float> queue = new Queue<float>(rectWidth);

// I would never use `var` in a for-loop; makes it immediately obvious we are using ints and not floats
for (int y = 0; y < bitmap.Height; y++)
{
    for (int x = 0; x < bitmap.Width; x++)
    {
        // this is the only time we call bitmap.GetPixel(,)
        queue.Enqueue(bitmap.GetPixel(x, y).GetBrightness());

        if (x >= rectWidth)
        {
            hSums[x - rectWidth, y] = queue.Sum();
            // if the ring-buffer isn't fixed size, we may have to manually evict the old value at this point
            queue.Dequeue();
        }
    }

    queue.Clear(); // we don't need to do this, but it is much clearer if we do
}

Now we have our 2D buffer of sums of horizontal strips of width w. Now we perform a similar operation to scan down them, and find the 'brightest' rectangle.

I don't see any real reason to keep an actual record of all the rectangles; we can just remember the best as we go along. It will reduce the time complexity (from O(n^2 log(n)) to O(n^2)) and won't clutter the code too much.

queue = new Queue<float>(rectHeight);

float bestAverage = float.NegativeInfinity;
Rectangle bestRectangle = default(Rectangle);

for (int x = 0; x < hSumWidth; x++)
{
    for (int y = 0; y < bitmap.Height; y++)
    {
        queue.Enqueue(hSums[x, y]);

        if (y >= rectHeight)
        {
            float rectangleAverage = queue.Average();

            if (rectangleAverage > bestAverage)
            {
                bestRectangle = new Rectangle(x, y - rectHeight, rectWidth, rectHeight);
                bestAverage = rectangleAverage;
            }

            // if the ring-buffer isn't fixed size, we may have to manually evict the old value at this point
            queue.Dequeue();
        }
    }

    queue.Clear();
}

return bestRectangle;

I have tested this quickly against your test image, and it finds a rectangle in the same place (quick visual inspection, no promises). Your code has an order 4 time complexity; this only has order 3 time complexity, 2 if you replace the queues with a running count. There is really nothing clever going on, but I think it ought to work. A gist of the complete method is provided.

Other

I've changed width and height into rectWidth and rectHeight, so that there can be no confusion.

I think you have an off-by-one error:

for (var x = 0; x < bitmap.Width - width; x++)

Consider if you had a 1*1 image, looking for 1*1 rectangles. This loop would never run, no rectangle would be found, and .First() would crash on the last line.

You can improve your access to the bitmap by using the LockBits() method. This method locks the pixels in memory and returns a BitmapData structure that gives you access to the pixels via its Scan0 property. Once you have a pointer to the pixels, getting a pixel is just some pointer math and a deference. If you're scanning over a rectangle of the image, this can be much faster in an inner loop than a function call, as you just increment your pointer and read from memory. I'm not a C# developer, so instead of trying to cobble together some example code that will likely be filled with errors, I'll just recommend looking at the above link for an example.


BOOL×BOOL→ENUM mapping Does this part look clean enough? Any suggestions on how to make it cleaner?

if (isCheck)
{
    if (isStuck)
    {
        return GameState.Mate;
    }
    else
    {
        return GameState.Check;
    }
}
else
{
    if (isStuck)
    {
        return GameState.Stalemate;
    }
    else
    {
        return GameState.Ok;
    }
}

I'd use a decision table here:

GameState[,] decisionTable = new GameState[2,2];
decisionTable[0,0] = GameState.Ok;
decisionTable[0,1] = GameState.Stalemate;
decisionTable[1,0] = GameState.Check;
decisionTable[1,1] = GameState.Mate;
return decisionTable[Convert.ToInt32(isCheck), Convert.ToInt32(isStuck)];

From Code Complete 2nd Edition, Chapter 19: General Control Issues, page 431:

  Use decision tables to replace complicated conditions

  Sometimes you have a complicated test involving several variables. It can be helpful to use a decision table to perform the test rather than using ifs or cases. A decision-table lookup is easier to code initially, having only a couple of lines of code and no tricky control structures. This minimization of complexity minimizes the opportunity for mistakes. If your data changes, you can change a decision table without changing the code; you only need to update the contents of the data structure.

Not really recommending this, but you could use the fact that you are always using both variables to generate a string representaion of the four states, and then have either a dictionary or switch statement return the correct value.

string checkStuck = isCheck.ToString() + isStuck.ToString();
switch(checkStuck) {
   case "TrueFalse":
        return GameState.Mate;
   case "TrueTrue":
       return GameState.Check;
   case "FalseFalse":
        return GameState.Ok;
   case "FalseTrue":
        return GameState.Stalemate;
}

You could do the same with integers, but at that point you might as well go with Andy's answer.