Ontario Health Card mod 10 validation An example of the business rules are here.

Does this code implement those rules correctly?  Note that you will have to derive the rules from the example.

/*
test number from url
9876543217

other valid numbers
5322369835
7089771195
8108876957
4395667779
6983806917

not valid numbers
2790412845

5762696912
*/

declare @inputString as varchar(10) = '2790412845'
, @mathResult as tinyint
, @digitNumber as tinyint = 1
, @isValid as bit = 1
, @checkDigitPosition as tinyint
, @tenthDigit as tinyint;

declare @digits as table (
DigitNumber tinyint
, Digit tinyint
, NewDigit tinyint
);

while @digitNumber <= 10
begin
insert into @digits (
DigitNumber
, Digit
)
select @digitNumber
, cast(substring(@inputString, @digitNumber, 1) as tinyint) digit;

set @digitNumber = @digitNumber + 1;
end
/*
Double 1st, 3rd, 5th, 7th and 9th Digits and take the sum of their digits
*/
-- even numbered digits
update @digits
set NewDigit = Digit
where DigitNumber % 2 = 0;

-- odd numbered digits
update @digits
set NewDigit = cast(left(cast((Digit * 2) as char(2)), 1) as tinyint)
         + cast(right(cast((Digit * 2) as char(2)), 1) as tinyint)
where DigitNumber % 2 = 1;

--add the 1st nine new digits together and take 2nd digit (mod 10)
select @mathResult = result
from
(select sum(NewDigit) % 10 result
from @digits
where DigitNumber <= 9) temp;

select @mathResult w;
select * from @digits;
-- Subtract The Unit Position From Ten

set @checkDigitPosition = 10 - @mathResult;
-- compare this number to the 10th digit
select @tenthDigit = Digit
from
(select Digit
from @digits
where DigitNumber = 10) temp;

select @checkDigitPosition p
, @tenthDigit t
, case when @tenthDigit = @checkDigitPosition then 1 else 0 end isValid;

This is based on the Luhn-algorithm, see this answer.

Those solutions are generic, i.e. for any input length, but for a specific length string I prefer a brute-force approach, no variables/loops/etc., just cut&paste&modify:

select -- luhn check digit
   (10-
     ( -- sum of all digits after doubling the odd digits
        Substring(inputString, 1,1)*2 % 10
      + Substring(inputString, 1,1)*2 / 10
      + Substring(inputString, 2,1)
      + Substring(inputString, 3,1)*2 % 10
      + Substring(inputString, 3,1)*2 / 10
      + Substring(inputString, 4,1)
      + Substring(inputString, 5,1)*2 % 10
      + Substring(inputString, 5,1)*2 / 10
      + Substring(inputString, 6,1)
      + Substring(inputString, 7,1)*2 % 10
      + Substring(inputString, 7,1)*2 / 10
      + Substring(inputString, 8,1)
      + Substring(inputString, 9,1)*2 % 10
      + Substring(inputString, 9,1)*2 / 10
     ) % 10 -- subtract the last digit
   ) % 10   -- in case last digit is a zero: 10 -> 0

Put it in a CASE to get 0/1:

case when previous calculation = Substring(inputString, 10,1)
     then 1
     else 0
end


Refactoring random number generation As I'm learning Ruby I wrote this little program to generate a "nice" number randomly (like 4747, 6969, etc.).
As I'm currently breaking the "do not repeat yourself" rule, how would you refactor the following?

def nice_numbers
    a = rand(9)
    b = rand(9)
    c = rand(9)
    d = rand(9)
    while a != c || b != d
        a = rand(9)
        b = rand(9)
        c = rand(9)
        d = rand(9)
    end
    nice = [a,b,c,d].join
end

puts nice_numbers

The code:

def nice_numbers
  ([rand(9),rand(9)]*2).join
end

generates the same output as your function. It is also faster, as it does not test then regenerate anything.

If you want to DRY this up for rand(9):

def nice_numbers
  (Array.new(2) {rand(9)} * 2).join
end

Ruby language features used in this last example:

Array constructor takes a size param and a block to fill the Array
Multiplying an array by an integer repeats the array


Competition - Qualifications - E - Matrix distance 2 types of query:

add value to x y
output the sum of \$value*(|a - x|+|b-y|)\$ for every pair(a, b, v).

In the start you are given \$n\$ (number of querys), \$m\$ (maximal dimension for square matrix).

In the next \$n\$ lines you are given either:

1 x y v, you should add value v to x y coordinate, or
2 x y calculate the \$distance * value\$ between every \$a\$ and \$b\$ that have some values (distance is being calculated: \$|a- x| + |b - y|\$). So the formula for one spot in matrix would be \$v * (|a - x| + |b - y|)\$ for a given \$a\$ and \$b\$.

My code works, but it is too slow.

Constraints:
\$n <= 250'000\$
\$m <= 10^9\$
\$X_i\$ and \$Y_i <= m\$
\$V_i\$ <= \$10^4\$

time limit: 2.5s

My code:

for (int i = 0; i < n; ++i){

    int el;
    cin >> el;

    if (el == 1){
        int a, b, c;
        cin >> a >> b >> c;

        x.push_back(a);
        y.push_back(b);
        v.push_back(c);
    }

    if (el == 2){
        int a, b;
        cin >> a >> b;

        ll sol = 0;
        for (int j = 0; j < x.size(); ++j){
            sol += v[j] * (abs(a - x[j]) + abs(b - y[j]));
        }
        cout << sol << "\n";

    }

}

Your explanation is difficult to follow, but your code explains it. It's simple and clear.
The main thing I want to advise is to not use using namespace std. See this Stack Overflow question for reasons.
You don't show what ll is, I presume it's a long long int type?
For a newline, use '\n' rather than "\n". There's not a huge difference, but it's slightly faster to output a single character than a string containing a single character.
In terms of improving performance, you might want to keep a single vector with a struct:
struct Data {
   int x, y, v;
}
std::vector<Data> data;
// ...
data.emplace_back(a, b, c);

This gives you at least two advantages:

You call malloc/realloc (on push_back) three times as frequently if you have three vectors. If you have only one vector on the stack, there is a good possibility that realloc will simply add space to the end of your block, rather than creating a new block and copying the data over. If you have three vectors, trying to expand one will invariably have another be in the way, forcing the copy.
Of course you could do data.reserve(n) and be sure you'll never call realloc.

Data locality: In your second case, where you iterate over the data, you would read the three values from consecutive locations in memory, rather than from disjoint locations. This will allow a better use of cache. Since you iterate over these frequently, it could make a big difference.

Finally, you can improve your distance computation and do away with one of the calls to std::abs. Note that, for the L-1 norm that you use, distance(p1,p2) == abs(distance(0,p1)-distance(0,p2)). And, given your text "m (maximal dimension for square matrix)", I presume that the coordinates indicate a location within this matrix, and therefore are always larger or equal to 0. If so, computing the distance to the origin requires no std::abs. then your distance
abs(a - x[j]) + abs(b - y[j]) // distance(p1,p2)

can be rewritten as
abs(a + b - (x[j] + y[j])) // abs(distance(0,p1)-distance(0,p2))

The thing that still bothers me is that you are given m, but you don't need it. Maybe we're missing another possibility for optimization there?

(EDIT) Reducing complexity from O(n²) to O(n log n)
It is possible to reduce the complexity of step 2 by adding some (a lot of) complexity to step 1. Both steps (adding a point and computing the weighted distance of a point to all previous points) should turn into operations of logarithmic complexity w.r.t. the number of points seen so far.
We start with the observation that the core distance computation
sum( v[j] * ( abs(a - x[j]) + abs(b - y[j]) ) )

can we rewritten as
sum(v[j] * abs(a - x[j])) + sum(v[j] * abs(b - y[j]))

That is, the two dimensions can be tackled independently. From here on we'll look only at the x-coordinate, and presume we repeat the same operations for the y-coordinate.
Next, we note that we can write
sum(v[j] * abs(a - x[j])) == sum(v[j] * (a - x[j])) // for x[j]<=a
                          == sum(v[j] * (x[j]) - a) // for x[j]>=a

Thus, we need to separate incoming points in step 1 into those that are to the left of a future query point, and those to the right. (Note that if x[j]==a, the distance will be 0, and the point can be ignored or used twice without affecting the output.
So how do we separate incoming points around a coordinate we don't know yet? Use a tree. R-trees are the tool for spatial indexing like this. We need a simplified version, since we don't need to store bounding boxes, only split locations. Maybe it's more similar to a quadree.
Because
sum(v[j] * (a - x[j])) == sum(v[j])*a - sum(v[j]*x[j])

it seems that we need to accumulate sum(v) and sum(v*x) for all points to the left of x (and also for those to the right). Thus our tree needs to store these values. The tree further needs to indicate what the coordinate is that splits its left and right branches. Thus, we can easily find in the tree the nodes that are to the left or to the right when computing a distance in step 2.
I think the tree should have each input point as a leaf node. Each non-leaf node (can I call those branch nodes?) would contain the sum of v and v*x for its two children, as well as the x-coordinate half-way between the two children's x-coordinates. Something like this:
struct Node {
  Node* left;
  Node* right;
  std::uint64 sumV;
  std::uint64 sumXV;
  std::uint32 x;
}

During step 1, it's simply a matter of inserting nodes:
void Node::insert(std::uint32 x, std::uint32 v) {
  if (isLeaf()) {
    // turn this leaf node into a branch node
    // create a new leaf node with {sumV,sumXV,x}
    // create a new leaf node with {v,x*v,x}
    sumV = left->sumV + right->sumV;
    sumXV = left->sumXV + right->sumXV;
    x = (left->x + right->x) / 2;
  }
  if (x <= node->x) {
    left->insert(x,v);
  } else {
    right->insert(x,v);
  }
}

During step 2, find the position of a in the tree, and obtain sumV and sumXV for all nodes to the left, and all those to the right:
std::uint64 Node::sum(std::uint32 a) {
  if (isLeaf()) {
    return std::abs(sumV*a - sumVX);
  }
  if (a>=x) {
    return left->sumV*a - left->sumXV + right->sum(a);
  } else {
    return right->sumXV - right->sumV*a + left->sum(a);
  }
}

I don't have time to write a full implementation and test it, but it was to think about this problem!


Hovering over images to show another image whilst fading in & out I'm trying to figure out how to correctly hover over an image to fade in another image and when you move your mouse out, it would go fade back to the normal image.

$(document).ready(function(){

$('img').hover(
    function(){
        $(this).stop().fadeOut(function(){
        var $temp = $(this).attr('src');
        $(this).attr('src', $(this).attr('data-alt-src'));
        $(this).attr('data-alt-src', $temp);
        });

        $(this).fadeIn();
    },
    function(){
        $(this).stop().fadeOut(function(){
        var $temp = $(this).attr('data-alt-src');
        $(this).attr('data-alt-src', $(this).attr('src'));
        $(this).attr('src', $temp);
        });

        $(this).fadeIn();

    }
);
});
#main-wrapper {
width: 970px;
margin: 0 auto;
text-align: center;
}

img {
width: 200px;
}
<!DOCTYPE html>

    <title>Hover In/Out</title>
    <meta charset="UTF-8">
    <link rel="stylesheet" href="styles.css">

So far, it works as it should with one minor defect. If I were to quickly hover my mouse over the image and out, it would stay in the second image. I initially wanted to hover over the image to show the other image and then when I hover out from the image it would go back to its initial image.

You need to fix your indentation.

Code inside blocks gets one more level of indentation.

Here is what your indented JavaScript would look like:

$(document).ready(function () {

    $('img').hover(
    function () {
        $(this).stop().fadeOut(function () {
            var $temp = $(this).attr('src');
            $(this).attr('src', $(this).attr('data-alt-src'));
            $(this).attr('data-alt-src', $temp);
        });

        $(this).fadeIn();
    },

    function () {
        $(this).stop().fadeOut(function () {
            var $temp = $(this).attr('data-alt-src');
            $(this).attr('data-alt-src', $(this).attr('src'));
            $(this).attr('src', $temp);
        });

        $(this).fadeIn();

    });
});

Your CSS also has poor indentation.

Here is your indented CSS:

#main-wrapper {
    width: 970px;
    margin: 0 auto;
    text-align: center;
}

img {
    width: 200px;
}

In the two functions that you are passing to $('img').hover, you are doing pretty much the same thing. I recommend creating a separate function that takes two parameters for the data to swap.

Here is what I came up with:

/*
    Sets the .stop().fadeOut of an element to swap two properties of that element
    @param(jQuery Object) elem -- the element
    @param(string) oldSrc -- one element to swap
    @param(string) newSrc -- another element to swap
*/
function fadeSwapSrc(elem, oldSrc, newSrc) {
    elem.stop().fadeOut(function() {
        var $temp = elem.attr(oldSrc);
        elem.attr('src', elem.attr(newSrc));
        elem.attr(newSrc, $temp);
    }
}

Now, your code simply becomes:

$(document).ready(function () {

    $('img').hover(
    function () {
        fadeSwapSrc('src', 'data-alt-src');
        $(this).fadeIn();
    },

    function () {
        fadeSwapSrc('data-alt-src', 'src');
        $(this).fadeIn();
    });
});


Counting first letter of title and printing letters from a to z I am trying to count the titles according to the first letter and filter it by the tag.

I tried for ages and I am not sure if I can write this query in a better way.
Can you please advise me.

Here is the sqlfiddle link:
http://sqlfiddle.com/#!9/3155cd/2

My query:

SELECT letter.letter as firstLetter, COUNT(item_tag.id) AS itemCount
        FROM letter
        left outer join item
             on left(item.title, 1) = letter.letter
        left outer join item_tag
            ON item_tag.item_id = item.id
        AND item_tag.tag_id = 1
        GROUP BY letter.letter

Here is my tables:

Item:

+----+-----------------+
| id |      title      |
+----+-----------------+
|  1 | title goes here |
+----+-----------------+

tag:

+----+----------+
| id |   name   |
+----+----------+
|  1 | tag name |
+----+----------+

item_tag

+----+--------+---------+
| id | tag_id | item_id |
+----+--------+---------+
|  1 |      1 |       1 |
+----+--------+---------+

letter:

+----+--------+
| id | letter |
+----+--------+
| 1  | A      |
| 2  | B      |
| .  | .      |
+----+--------+

Fiddle is currently broken again, but you should do the count as early as possible  -> Inner instead of more expensive Outer join and less rows to join.

SELECT l.letter AS firstLetter
  -- return 0 for missing letters
  ,Coalesce(lc.cnt,0) AS itemCount
FROM letter AS l
LEFT OUTER JOIN
 ( -- count letters before join
   SELECT Left(i.Title,1) AS letter
     ,Count(*) AS cnt
   FROM item AS i -- no Outer Join needed
   JOIN item_tag AS it
     ON it.item_id = i.id
    AND it.tag_id = 1
   GROUP BY Left(i.Title,1)
 ) AS lc
ON lc.letter = l.letter


Better jQuery function argument with if-statement? function check_itv(key) {

if (key.length){

    if(key=="left"){
        left_itv = setInterval(left,100);
        check_left= false;
        check_right=true;
        check_up=true;
        check_down=true;
        clearInterval(right_itv);
        clearInterval(down_itv);
        clearInterval(up_itv);
    }

    if(key=="right"){
        right_itv = setInterval(right,100);
        check_left= true;
        check_right=false;
        check_up=true;
        check_down=true;
        clearInterval(left_itv);
        clearInterval(down_itv);
        clearInterval(up_itv);
    }

    if(key=="up"){
        up_itv = setInterval(up,100);
        check_left= true;
        check_right=true;
        check_up=false;
        check_down=true;
        clearInterval(left_itv);
        clearInterval(right_itv);
        clearInterval(down_itv);
    }

    if(key=="down"){
        down_itv = setInterval(down,100);
        check_left= true;
        check_right=true;
        check_up=true;
        check_down=false;
        clearInterval(left_itv);
        clearInterval(right_itv);
        clearInterval(up_itv);
    }

}

}

check_left = true;
check_right = true;
check_up = true;
check_down = true;
left_itv = "";
right_itv = "";
up_itv = "";
down_itv = "";

Try to do shorter and better, Any idea ?

Thanks

Without changing too much, here are some tips on improving your code.
Assumptions:

You're working in modern web browser.
left, up, down, right are defined else where.

1)
Define all the variables at the top. I'm not sure where the fucntions left, up, down, right are.
2)
Use a switch instead of multiple if else.
3)
Perform an operation to collection if multiple elements share the same functionality. Refer to resetValues()
4)
Try to make all the if conditions as small as possible. Refer to !key.length
Here's what I came up with.
Array.prototype.forEach = Array.prototype.forEach || function(fn, scope) {
    for(var i = 0, len = this.length; i < len; ++i) {
        fn.call(scope || this, this[i], i, this);
    }
};

var self = this,
    check_left, check_right, check_up, check_down,
    left_itv, right_itv, up_itv, down_itv;

var resetValues = function(){
    ["left_itv", "right_itv", "up_itv", "down_itv"].forEach(function(el){
        clearInterval( self[el] );
    });
    ["check_left", "check_right", "check_up", "check_down"].forEach(function(el){
        self[el] = true;
    });
};

resetValues();

function check_itv(key) {
    if (!key.length) {
        return;
    }
    resetValues();
    switch( key ){
        case "left":
            left_itv = setInterval(left, 100);
            check_left = false;
            break;
        case "right":
            right_itv = setInterval(right, 100);
            check_right = false;
            break;
        case "up":
            up_itv = setInterval(up, 100);
            check_up = false;
            break;
        case "down":
            down_itv = setInterval(down, 100);
            check_down = false;
    }
}

Alternatively, you could swap the global variables inside a singleton(namespace) that has a reset functions. But that add a bit of complexity.


Python siren control Below is some code I've put together to contol a siren for a fire service.

It works by webscraping a paging feed and looks for set triggers.

Is there a better way of doing my code or is this "pythonic" enough or can it be improved?

Im python self taught.

"""PYTHON SCRIPT TO CONTROL SIREN

This script will webscape a paging feed and
in turn activate a siren on set incidents

siren should only sound for 30secconds between 0800 -2000 hrs

this has been made so the siren only goes off for some incidents not all

by s.rees (c) 2016
"""
from scraper import Scraper
import sys
import requests
from clint.textui import puts, colored
import RPi.GPIO as GPIO
from time import sleep
import time

time = datetime.datetime.now()

print "Starting"
print "Monitoring"

#Set GPIO siren is attached too
GPIO.setmode(GPIO.BOARD)
GPIO.setup(7, GPIO.OUT)

def siren ():
 GPIO.output(7, GPIO.HIGH)
 sleep(30)
 GPIO.output(7, GPIO.LOW)

if __name__ == "__main__":
# Load webscraper module
    scraper = Scraper(5, recent_messages=True)
    @scraper.register_handler
    def handler(msg):
# get msg from scraper and make it readable
        puts(colored.yellow(msg.channel), newline=False)
        puts(" [", newline=False)
        puts(colored.green(msg.datetime), newline=False)
        puts("] ", newline=False)
        if msg.response:
            puts(colored.red(msg.text))
        else:
            puts(msg.text)
# set agency
        if 'MFS' in msg.channel:
#set unit
         if 'Station' in msg.channel:
          print "Brigade Found"
#set response type
                 if 'RESPOND RUBBISH OR WASTE' in msg.text:
                  print "Trigger found"
                  if (time > datetime.time(8) and time < datetime.time(20)):
                    print "Activate Siren"
                    siren ()
                    print 'done'
                    return
                  else:
                    print "out of time restrictions"
                    return
                if 'RESPOND GRASS FIRE' in msg.text:
                  print "Trigger found"
                  if (time > datetime.time(8) and time < datetime.time(20)):
                    print "Activate Siren"
                    siren ()
                    print 'done'
                    return
                  else:
                    print "out of time restrictions"
                    return
            else:
                    print "Brigade found but no trigger"
                    return
            else:
                return
 scraper.run()
 GPIO.cleanup()

Here are some code style and organization notes:

remove unused imports (sys, requests)
import time is also not needed since you are immediately shadowing it after by defining the variable time
missing datetime import
organize imports per PEP8
use consistent 4-space indents
no need for extra space after the function and before the opening parenthesis - e.g. siren() vs siren ()
let's avoid hardcoding the constant values, like the number 7 and define it in a, say, GPIO_PIN "constant"
let's move all the initial setup code to under the "main" block of the program
use print() as a function as opposed to a statement (for Python 3.x compatibility)

Here is the improved initial part of the code without the "scraping" part:

from datetime import datetime
from time import sleep

import RPi.GPIO as GPIO
from clint.textui import puts, colored
from scraper import Scraper

GPIO_PIN = 7

def setup_gpio():
    """Sets GPIO siren is attached too."""
    GPIO.setmode(GPIO.BOARD)
    GPIO.setup(GPIO_PIN, GPIO.OUT)

def siren():
    """Make a siren (flash) on a desired output pin."""
    GPIO.output(GPIO_PIN, GPIO.HIGH)
    sleep(30)
    GPIO.output(GPIO_PIN, GPIO.LOW)

if __name__ == "__main__":
    print("Starting")
    print("Monitoring")

    now = datetime.now()

    setup_gpio()

Note that I've renamed time variable to a more readable now.

As far as the rest of the code in the "main" block of the program:

please see if there is a better way to register a handler for the scraper - instead of defining a decorator, define the handler function before the "main" block and call register_handler() passing in the function:

scraper.register_handler(handler)

the time comparisons can be improved by using the .hour attribute of a datetime and short-circuiting:

if 8 < now.hour < 20:

you can omit the last "else" + "return" branch
the prints around the siren() call should probably be put into the siren() function itself to avoid the code duplication


Cached empty collections I often need to return empty collections.
One of those days I wrote the following to return a cached instance:

public static class Array<T>
{
    // As a static field, it gets created only once for every type.
    public static readonly T[] Empty = new T[0];
}

I didn't know about Enumerable<T>.Empty() maybe it didn't exist back then. Although I know now, I still use this one.

There are still many functions in BCL that need an array instead of IEnumerable<T>, IList<T> or IReadOnlyList<T>. And array implements all of these so it can be used anywhere.

// All these variables share the same array's reference.
string[]            empty1 = Array<string>.Empty;
IEnumerable         empty2 = Array<string>.Empty;
IEnumerable<string> empty3 = Array<string>.Empty;

What do you think about this class?
Can you see any other advantages/disadvantages of it over Enumerable<T>.Empty()?

And about implementation:
Do you think making the caching using a static field would cause any problem?

Edit: Array class now has a static, generic Empty method, essentially deprecating this implementation.

Your solution is absolutely correct and practical.

In fact Enumerable.Empty<T> also returns empty array under the hood, just slightly in a different way (they have a separate instance holder class that is lazily initialized).


Query to compare execution performance metrics for the three most recent months I've been working on a semi-awkward query in that it uses a very high number of functions given its relatively small size and scope. I was hoping to get some feedback on any ways I could format or re-factor this better?

select  Name ,
        avg(TimeProcessing / 1000 + TimeRendering / 1000 + TimeDataRetrieval / 1000) as 'Current Month' ,
        isnull(count(TimeProcessing), 0) as 'Sample' ,
        min(l2.[Avg Exec Previous Month]) as 'Previous Month' ,
        isnull(min(l2.[Sample Previous Month]), 0) as 'Sample' ,
        min(l3.[Avg Exec Two Months Ago]) as 'Two Months ago' ,
        isnull(min(l3.[Sample Two Months Ago]), 0) as 'Sample'
from    marlin.report_execution_log l
        inner join      marlin.report_catalog c on l.ReportID = c.ItemID
        left outer join ( select    l2.ReportID ,
                                    avg(TimeProcessing / 1000 + TimeRendering
                                        / 1000 + TimeDataRetrieval / 1000) as 'Avg Exec Previous Month' ,
                                    count(TimeProcessing) as 'Sample Previous Month'
                          from      marlin.report_execution_log l2
                          where     TimeEnd between dateadd(MONTH, -2,
                                                            getdate())
                                            and     dateadd(MONTH, -1,
                                                            getdate())
                          group by  l2.ReportID
                        ) l2 on l.ReportID = l2.ReportID
        left outer join ( select    l3.ReportID ,
                                    avg(TimeProcessing / 1000 + TimeRendering
                                        / 1000 + TimeDataRetrieval / 1000) as 'Avg Exec Two Months Ago' ,
                                    count(TimeProcessing) as 'Sample Two Months Ago'
                          from      marlin.report_execution_log l3
                          where     TimeEnd between dateadd(MONTH, -3,
                                                            getdate())
                                            and     dateadd(MONTH, -2,
                                                            getdate())
                          group by  l3.ReportID
                        ) l3 on l.ReportID = l3.ReportID
group by l.ReportID, Name
order by Name

You might want to use Common Table Expression or Should use meaningful table alias in Join.

You might also want to use indexes on your date column with <= and >= operator instead of between.

Surround your column names in [] instead of single quotes.


Click n times on image to match with random number n Challenge

Create a page with

An element for number,
An image
An unordered list tag for list of images
A 'Check result' button
A text element to show result

Generate random number and put it in (i)
On click the image it add an li with the image inside UL tag
On click check result button, compare random with number of images inside UL, if both are same show Correct answer else wrong answer in result box.

Codepen URL

Random number and Image

HTML

Select  s

      <button id="btnResult" class="btn btn-primary">Check Result</button>

jQuery

$(function() {
    var elements = {
        random: $("#randomNumber"),
        item: $("#item"),
        sourceImage: $("#actionImage"),
        targetImage: $(""),
        imageList: $("#imgList"),
        list: $("
"),
        btnResult: $("#btnResult"),
        output: $("#output")
    },
    data = {
        random: Math.floor(9 * Math.random() + 2),
        image: elements.sourceImage.attr("src"),
        item: elements.sourceImage.attr("alt")
    },
    events = {
        init: function() {
            elements.random.text(data.random), elements.item.text(data.item), elements.targetImage.attr({
                alt: "list image",
                src: data.image
            }),
            elements.list.append(elements.targetImage),
            elements.sourceImage.click(events.addImage),
            elements.btnResult.click(events.showResult);
        },
        addImage: function() {
            elements.imageList.append(elements.list.clone());
        },
        showResult: function() {
            var result = "Correct Answer";
            elements.imageList.children().length !== data.random &&
            (result = "Wrong Answer"), elements.output.text(result);
        }
    };
    events.init();
});

The code looks clean and well readable and with one exception I would say there is nothing wrong with it per se, however you are using several unusual approaches.

The task asks for

  A text element to show result

I'm not sure what a "text element" means here, but it could be an <input type="text">. However that would be wrong, since there are for input and not output. Your choice of a <b> element is better, but HTML 5 provides the <output> element, that would be even more suitable.

Your choice to collect your variables in objects (elements, data, events)  seems somewhat arbitrary. It's not wrong, and after getting used to it, it actually helped readability somewhat (except that now almost all lines begin with elements...., which seems a bit repetitive).

Just be aware that it's an unusual thing to do, because people usually expect objects like that to have sort of technical use, instead of just grouping variables.

The use of the comma operator to separate statements (or to be exact expressions) instead of semicolons (or just line breaks) is very unusual. Since the comma operator is very rarely used, it can be confusing for beginners and experts may try to find deeper meaning to it, even when there is none. Especially the first line of init() irritated me for a moment, because there is no line break after the commas, so that it looks like some special is happening, which isn't.

The only point that I consider wrong: The use of && instead of a regular if. This (and the use of the comma operator) looks like you are trying to emulate the kind of "optimizations" that code compressors do. Don't do this. It compromises readablily. If you want to serve compact code, then use a code compressor.


Project Euler #5 in Java Project Euler #5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Here is my solution:
class SmallestMultiple {

    private static final int MAX = 20;

    public static void main(String[] args) {
        long time = System.nanoTime();
        int result = 1;
        for(int i = 1; i <= MAX; i++) {
            result = smallestMultiple(result, i);
        }
        time = System.nanoTime() - time;
        System.out.println("Result: " + result + "\nTime used to calculate in nanoseconds: " + time);
    }

    private static int smallestMultiple(int i, int j) {
        for(int index = 2; index <= i && index <= j; index++) {
            if(i % index == 0 && j % index == 0) {
                i /= index;
            }
        }
        return i * j;
    }

}

Output:

Result: 232792560
Time used to calculate in nanoseconds: 11603

Questions:

Is is as efficient as it can be? If not, how can I improve it?
Does it smell?

Mathematically, the least common multiple of a range of numbers can be expressed as

$$LCM(1..1) = 1$$
$$LCM(1..n+1) = \frac{LCM(1..n) * (n+1)}{GCD(\;LCM(1..n), \;n+1)} $$

So you can start with 1 and work your way up

static long leastCommonMultiple(long n) {
    long multiple = 1;

    for ( long i = 1; i <= n; i++ ) {
        multiple *= i / gcd(multiple, i);
    }

    return multiple;
}

The optimal Greatest Common Divisor algorithm is

static long gcd(long a, long b) {
    return ( 0 == b ) ? a : gcd(b, a%b);
}

The iterative version is

static long gcd(long a, long b) {
    while ( 0 != b ) {
        long temp = a;
        a = b;
        b = temp % b;
    }

    return a;
}

Running with the iterative version takes about a third of the time that your solution does on my machine.

You can get an additional speedup by using the fact that you already know \$LCM(1..10) = 2520\$.

static long leastCommonMultiple(long n) {
    long multiple = 2520;

    for ( long i = 11; i <= n; i++ ) {
        multiple *= i / gcd(multiple, i);
    }

    return multiple;
}

That allows you to start at 11 rather than 1.  It's not much of a gain though.  And of course, it's unique to this particular problem.


Website menu with Flask I wrote some code in Flask for site menu:

def menu(parent_id=0, menutree=None):
    menutree = menutree or []
    cur = g.db.execute('select id, parent, alias, title, ord from static where parent="'+ str(parent_id) +'" and ord>0 order by ord')
    fetch = cur.fetchall()

    if not fetch:
        return None

    return [{'id':raw[0], 'parent':raw[1], 'alias':raw[2], 'title':raw[3], 'sub':menu(raw[0])} for raw in fetch]

The data is taken from the sqlite3 table:

create table static (
  id integer primary key autoincrement,
  parent integer,
  alias string not null,
  title string not null,
  text string not null,
  ord integer
);

Variable (menu_list) is transmitted to template in each route:

@app.route('/')
def index():
    menu_list = menu()
    [...]
    return render_template('index.tpl', **locals())

Despite the fact that the code is more or less normal (except for prepared statements in a query to the database), the template is not very good:

  {% for menu in menu_list %}

    {{ menu.title }}
    {% if menu.sub %}

      {% for sub in menu.sub %}

{{ sub.title }}
        {% if sub.sub %}

          {% for subsub in sub.sub %}

{{ subsub.title }}
          {% endfor %}

        {% endif %}

      {% endfor %}

    {% endif %}

  {% endfor %}

Is it possible to improve the existing code / output / logic?

In this code, at first I didn't see the "danger" until I scrolled to the right by accident:

def menu(parent_id=0, menutree=None):
    menutree = menutree or []
    cur = g.db.execute('select id, parent, alias, title, ord from static where parent="'+ str(parent_id) +'" and ord>0 order by ord')
    fetch = cur.fetchall()

    if not fetch:
        return None

    return [{'id':raw[0], 'parent':raw[1], 'alias':raw[2], 'title':raw[3], 'sub':menu(raw[0])} for raw in fetch]

In the g.db.execute statement you're embedding a parameter and we cannot know where the parameter comes from and if it was properly validated to prevent SQL injection. Two things to do here:

Make the line shorter, especially when it contains potentially dangerous stuff in the far right
Use prepared statements with ? placeholder

It's not clear what kind of database you're using, so you might need to edit, but it should be something like this, shorter and without embedded parameters:

cur = g.db.execute('select id, parent, alias, title, ord '
                   'from static where parent = ? and ord > 0 '
                   'order by ord', parent_id)

Another small tip here, if you reverse the checking logic of if not fetch to if fetch at the end, you don't need to return None, as that's the default anyway, and the method will be a bit shorter:

def menu(parent_id=0, menutree=None):
    menutree = menutree or []
    cur = g.db.execute('select id, parent, alias, title, ord '
                       'from static where parent = ? and ord > 0 '
                       'order by ord', parent_id)
    fetch = cur.fetchall()

    if fetch:
        return [{'id': raw[0], 'parent': raw[1], 'alias': raw[2],
                 'title': raw[3], 'sub': menu(raw[0])} for raw in fetch]

And a tiny thing, PEP8 dictates to put a space after the : in a key:value pair, like so: key: value.

In this code:

@app.route('/')
def index():
    menu_list = menu()
    [...]
    return render_template('index.tpl', **locals())

I recommend to NOT include all **locals(), but use the list of variables you want to pass explicitly. We're all humans, one day you might accidentally expose something.


Procedural generation of a general matrix representing a tile map The problem is to design an structure which generates "uniformly" the next one in an initially zero matrix. Taking an arbitrary index i in the range [0,m-1] for any j where a[i,j] == 0.
It is, for example:
\begin{gather}
\begin{bmatrix}
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \begin{bmatrix}
1 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \begin{bmatrix}
1 & 0 & 1\\
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix}\\
\to\begin{bmatrix}
1 & 0 & 1\\
1 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \begin{bmatrix}
1 & 1 & 1\\
1 & 1 & 0\\
0 & 0 & 0\\
0 & 0 & 0\\
\end{bmatrix}\\
\to\begin{bmatrix}
1 & 1 & 1\\
1 & 1 & 0\\
0 & 1 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \begin{bmatrix}
1 & 1 & 1\\
1 & 1 & 0\\
1 & 1 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \begin{bmatrix}
1 & 1 & 1\\
1 & 1 & 1\\
1 & 1 & 0\\
0 & 0 & 0\\
\end{bmatrix} \to \cdots \to \begin{bmatrix}
1 & 1 & 1\\
1 & 1 & 1\\
1 & 1 & 1\\
1 & 1 & 1\\
\end{bmatrix}
\end{gather}
Where is the utility? This algorithm can be used for procedural generation in any tile game. Now, I'm not a game programmer but I found really annoying the tile generation of Audiosurf 2 so, I want to perhaps provide a better solution.
(Note that the ones can be replaced by a number located by its input order.)
(I know the implications of the player when he doesn't "tap" some tile but there are other alternatives.)
My solution is:
import numpy as np
import numpy.random as rd

class RandomMatrixGenerator():

    def __init__(self, m: int, n: int):
        self.m = m
        self.n = n
        self.matrix = np.zeros(shape=(m,n), dtype='int8')
        self.ones = np.ones(shape=(m,n), dtype='int8')

    def __put_next(self):
        j: int = rd.randint(0, self.n, dtype='int8')

        if self.ones[:,j].all() == self.matrix[:,j].all():
            self.__put_next()

        for i in range(self.m):
            if self.matrix[i, j] == 0:
                self.matrix[i, j] = 1
                return

    def put_next(self):
        if self.ones.all() == self.matrix.all():
            return
        self.__put_next()

# Mini test
gen = RandomMatrixGenerator(4, 5)

for i in range(4 * 5):
    gen.put_next()
    if gen.matrix.all() == gen.ones.all():
        print(i + 1)

I'm learning Python for a class and I want to know if there is a way to optimize this code or reduce syntax, I greatly appreciate it.

You don't need to create a second m x n matrix to track where you've set. Since you're only interested in the index of the last one placed in each column you can use an one dimensional n-length array to track the row of the last one added and then use that directly when indexing the matrix.
Similarly, it also lets you randomly choose columns that still have space to add ones directly (that is, the nber of ones added is less than the length of the column) using np.less, np.where, and np.random.choice instead of picking a column, checking if it contains all ones, and resampling if it does. That's almost always a bad approach, especially when you start to have more columns full than not. If there are 5 full columns and 1 non-full one you have to keep sampling until you randomly select the one non-full column with only 1/6th odds which is going to be slow.
Combining all that you can write everything you need in about 8 lines with a 6-7x speed up
def matrix_generator(m, n):
    matrix = np.zeros((m,n), dtype="int")
    ones = np.zeros(n, dtype="int")

    while np.any(np.less(ones, m)):
        i = np.random.choice(np.where(np.less(ones, m))[0])

        matrix[ones[i],i] = 1
        ones[i] += 1

        yield matrix


Minimum Steps to One to find minimum operations to transform n to 1 I was solving this dynamic programming problem, and I was wondering if I can get any code review and feedback. You can find this problem online.

#  Coding Problem: Minimum Steps to One
#
#  Prompt:    Given a positive integer, you can perform any combination of these 3 steps:
#             1.) Subtract 1 from it.
#             2.) If its divisible by 2, divide by 2.
#             3.) If its divisible by 3, divide by 3.
#
#             Find the minimum number of steps that it takes get from N to1
#

def min_steps_to_one(n):
    work = [0, 0]

    for i in range(2, n+1):
        min_choice = work[i-1]

        if i % 3 == 0:
          divide_by_three = work[i//3]
          min_choice = min(min_choice, divide_by_three)

        if i % 2 == 0:
          divide_by_two = work[i//2]
          min_choice = min(min_choice, divide_by_two)

        work.append(min_choice + 1)

    return work[n]

I also include some test cases for Minimum Steps to One Tests

true: should return 3 for 10
true: should return 0 for 1
true: should work for large numbers PASSED: 3 / 3

def expect(count, name, test):
    if (count is None or not isinstance(count, list) or len(count) != 2):
        count = [0, 0]
    else:
        count[1] += 1

    result = 'false'
    error_msg = None
    try:
        if test():
            result = ' true'
            count[0] += 1
    except Exception as err:
        error_msg = str(err)

    print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)
    if error_msg is not None:
        print('       ' + error_msg + '\n')

print('Minimum Steps to One Tests')
test_count = [0, 0]

def test():
  example = min_steps_to_one(10)
  return example == 3
expect(test_count, 'should return 3 for 10', test)

def test():
  example = min_steps_to_one(1)
  return example == 0
expect(test_count, 'should return 0 for 1', test)

def test():
  example = min_steps_to_one(1334425)
  return example == 22
expect(test_count, 'should work for large numbers', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')

Overall this looks very good. It's even fits nicely with PEP 8 guidelines.

I would suggest preallocating your array, with something like work = [0] * (n + 1) to help slightly with speed and memory use. append is slightly wasteful in that regard because it keeps resizing the array and copying its contents elsewhere.

In terms of naming, i could perhaps helpfully be renamed something like candidate and work could do with being renamed too. Nothing is that unclear though.

It's good to see tests along with the code, and particularly good to see 1 tested. However, it's better to prefer standard testing libraries such as unittest to writing your own test routines. It's particularly hard to read code that redefines functions as you go, so if you must roll your own I'd strongly suggest redoing expect to take the input and expected output rather than some freshly defined test function. (But really, use a library!)

Finally, a comment on the underlying algorithm. The bottom up algorithm here is simple, thorough, and correct which are all good things. However, it is potentially wasteful because it has to check every number up to the target.

Consider that every number is either even or is 1 away from being even. Therefore you can always either divide or divide next time. That means that, even without the rule about 3s, you should expect the solution to take at worst \$ 2 log_2(n) \$ steps. That in turn indicates that at almost all of the second half of your work list for large numbers is guaranteed to be unused: you can't divide to it (because you can't divide by less than 2) and it's not worth stepping to it 1 element at a time because that would quickly overshoot the logarithmic lower bound. (Experimentally, if you check the value for say 10,000,000 then over 70% of entries in your cache have paths at least as long as your target path and so are useless to you.)

Therefore, consider instead using a top-down dynamic programming approach instead of a bottom up one to avoid storing results that you are never going to use. (Essentially, this works out as a breadth first search.)


Custom moment formats based on string length Just wanted to gage how solid this code is. With moment cracking down on lazy formatting I thought this was a good way to parse the string for what format to use.

var string = $this.attr("data-date");
var withoutTime = "YYMMDD";
var withTime = "YYMMDDHHmm";
var format = function(){
  if(string.length == withoutTime.length) return withoutTime;
  if(string.length == withTime.length) return withTime;
  return false;
}();
var date = moment(string, format);

How about this (based on the assumption that $ refers to jQuery):

var dateString = $('div').data('date');

function getDateFormat(dateString){

    if(!dateString) return false;

    var dateTimeFormats = ['YYMMDD' ,'YYMMDDHHmm'];

    return dateTimeFormats.filter(function(format){
        return format.length === dateString.length;
    })[0] || false;
}

console.log(getDateFormat(dateString));

jQuery's data() method is preferred over attr() since it's intended to be used with either html5 data attributes (like in your case) or for caching data in the jQuery $.cache.
Try to use more descriptive names and don't use reserved keywords as variable names (or a close call like string vs String in your case).
Check if the date string is defined before making use of it
I suggest that you always do equality checks using the identity operator, ===. Otherwise you might get results like 1 == true since the type is not taken in to consideration
If you want to use Array.prototype.filter in IE < 9, you can add a shim.

http://jsfiddle.net/zb4sfno3/


error handling logic in php I'm wondering if you see anything terribly wrong with this code, or if you see any areas for improvement. My objective is to make sure its simple enough for someone else taking over my job to be able to pick up fairly quickly.

My basic question has to do with the fact that in my model, I'm trying to distinguish between system errors that I want to show the end user, and ones that I don't want them to see.
Here's some code from my model:

 public function macaddresses($ip, $name)
 {
   try
     {
      //some code....
  if ( $obj->connect() )
  {
           //do something else
       return $macaddies
      }
  else
  {
      throw new Exception('Connection');
  } //end if
   }
   catch (Exception $e)
   {
   $this->error_handler($e->getMessage());
   return false;
    }//end catch
  }//end function

private function error_handler($emess)
{
    switch ($emess)
    {
        case 'Connection':
             $userfriendlyemess = "Unable to connect to device. Please contact administrator!";
             break;

       //handling unknown errors
       default:
            $userfriendlyemess = "Oops!  Something big just happened.";
            log_message('error', $emess); //write to ci logs
            break;
    }// end switch
    throw new Exception($userfriendlyemess);

} // end function

Finally, the logic in my controller is where I make the calls to show_error.
I know in CI i can use templates or something... but since I don't think there are going to be too many cases in my switch statement, i thought i'd try this approach.
any suggestions would be appreciated.

I don't really like the method of exception pseudo-typing you're doing, I'd use different objects to represent the type of exception rather than the content, like so:

function macaddresses($ip, $name)
{
    try
    {
        //some code....
        if($obj->connect())
        {
            //do something else
            return $macaddies;
        }
        else
        {
            throw new UserVisibleException("Unable to connect to device. Please contact administrator!");
        }
    }
    catch(Exception $e)
    {
        $this->processException($e);
    }
}

private function processException($exception)
{
    if($exception instanceof UserVisibleException)
    {
        throw $exception;
    }
    else
    {
        log_message('error', $exception->getTraceAsString());
        throw new UserVisibleException(null, $exception);
    }
}

class UserVisibleException extends Exception
{
    public function __construct($message = null, $cause = null, $code = 1)
    {
        parent::__construct
        (
            $message === null ? "Oops!  Something big just happened." : $message,
            $code, $cause
        );
    }
}

I put processException() as a method as it isn't clear whether you're using this design pattern elsewhere, but I assume so as you're connecting to something and there's usually other exceptions that can happen later. If you aren't, you can just stick it back into the catch block of macaddresses().

Additionally, if it isn't clear, the ternary is so you don't have to manually type in the message to attach a cause to an unknown exception being wrapped. And I took the liberty of replacing the generic message "connection" with the stack trace of the exception that caused it being passed to your logger, as this more detailed information will be useful should you wish to debug the cause of it.


addClass and removeClass in a switch case Since I'm still learning jQuery, I would like to have some feedback on my code:

var showImgage = function()
{
 var selection = $(this).val();

 switch(selection)
 {
  case 'Monica Bellud':
  $('#Belluci').removeClass().addClass('show');
  $('#Andres').removeClass().addClass('hide');
  $('#Seydoux').removeClass().addClass('hide');
  break

  case 'Lea Seydoux':
  $('#Seydoux').removeClass().addClass('show');
  $('#Belluci').removeClass().addClass('hide');
  $('#Andres').removeClass().addClass('hide');
  break

  case 'Ursula Andress':
  $('#Andres').removeClass().addClass('show');
  $('#Belluci').removeClass().addClass('hide');
  $('#Seydoux').removeClass().addClass('hide');
  break

  default:
  selection.removeClass();
 }
}

  Wie van de onderstaande dames is géén Bond Girl in de nieuwe film 'SPECTRE'?
  <input type="radio" value="Monica Bellud" name="girlchoice" id="choicemonica" checked />Monica Bellud
  <input type="radio" value="Lea Seydoux" name="girlchoice" id="choicelea" />Lea Seydoux
  <input type="radio" value="Ursula Andress" name="girlchoice" id="choiceursula" />Ursula Andress

I simply want to change the image (which is in my div of my HTML) for each radiobutton. It works, but it looks like I'm duplicating my code 3 times. How can I make this easier?

I would probably add a class/something to use as a selector (in this case I added girls) to make lookup easier. You can do this in other ways such as getting the values of the actors map so do it as you will.

Also your default case is calling removeClass on a string as selection is the current contents of whatever the event is hooked to.

// Actor name -> the corresponding element selector on the page
var actorsIdMap = {
    'Monica Bellud': '#Bellud',
    'Lea Seydoux': '#Seydoux',
    'Ursula Andress': '#Andres'
}

var showImage = function() {
    var selection = $(this).val();

    if (selection in actorsIdMap) {
        // Hide the other actors
        $('.girls').removeClass('hide show');
        $(actorsIdMap[selection]).addClass('show');
    } else {
       // Default case what do?
    }
}


Wrapping WinAPI FindNextVolume as std iterator This is my first attempt at creating an STL-style iterator. Is this code ok?

std::set<std::wstring> getVolumeNames()
{
    class FindVolumeWrapper : public std::iterator<std::input_iterator_tag, std::wstring>
    {
        WCHAR        m_curVolName[MAX_PATH];
        HANDLE       m_hFindVol;
        DWORD        m_dwError;
    public:
        // start iterator
        FindVolumeWrapper(bool)
            : m_hFindVol(::FindFirstVolumeW(m_curVolName, ARRAYSIZE(m_curVolName)))
            , m_dwError(::GetLastError())
        {
            if (m_hFindVol == INVALID_HANDLE_VALUE && m_dwError != ERROR_NO_MORE_FILES)
            {
                throw AutoWinError(m_dwError);
            }
            if (m_dwError == ERROR_MORE_DATA)
            {
                m_dwError = ERROR_SUCCESS;
            }
        }

        // end iterator
        FindVolumeWrapper()
            : m_hFindVol(INVALID_HANDLE_VALUE)
            , m_dwError(ERROR_NO_MORE_FILES)
        {
            m_curVolName[0] = L'\0';
        }

        FindVolumeWrapper& GetNextVolume()
        {
            BOOL bSuccess = ::FindNextVolumeW(m_hFindVol,
                                              m_curVolName,
                                              ARRAYSIZE(m_curVolName));
            if (!bSuccess)
            {
                m_dwError = ::GetLastError();
                ::FindVolumeClose(m_hFindVol);
                if (m_dwError != ERROR_NO_MORE_FILES)
                {
                    throw AutoWinError(m_dwError);
                }
            }
            return *this;
        }

        FindVolumeWrapper& operator ++ ()
        {
            return GetNextVolume();
        }

        std::wstring operator * ()
        {
            return m_curVolName;
        }

        // equal if either both good and point to same element, or both faulty
        bool operator == (FindVolumeWrapper const& other)
        {
            return (this->m_dwError == ERROR_SUCCESS
                    && other.m_dwError == ERROR_SUCCESS
                    && wcscmp(m_curVolName, other.m_curVolName) == 0)
                 || (this->m_dwError != ERROR_SUCCESS && other.m_dwError != ERROR_SUCCESS);
        }

        bool operator != (FindVolumeWrapper const& other)
        {
            return !operator == (other);
        }
    };

    std::set<std::wstring> volumeNames(FindVolumeWrapper(true), FindVolumeWrapper());

    return volumeNames;
}

This answer by another user to a similar question lists the whole set of features required by the Standard for a fully compatible iterator type. The list is quite long, and you probably won't need all those features, so this comment is mostly FYI.

You have chosen to make your class an Input Iterator, however, it is not fully compliant with the specification for such. It is missing the post-increment (it++) operator and the -> dereference operator, which are important and should at least be added.

The comparison operators are not const, which is a mistake, since they do not mutate member data. The proper signature would be, for instance with operator ==:

bool operator == (FindVolumeWrapper const& other) const;

Also, this calling syntax for operator == is not wrong, but it is unusual (though you've correctly reused it to implement !=):

 bool operator != (FindVolumeWrapper const& other)
 {
    return !operator == (other);
 }

I would expect this instead:

bool operator != (FindVolumeWrapper const& other) const
{
    return !(*this == other);
}

No special syntax, just a plain comparison.

This comparison is hard to read, too many conditions being checked at once:

bool operator == (FindVolumeWrapper const& other)
{
    return (this->m_dwError == ERROR_SUCCESS
            && other.m_dwError == ERROR_SUCCESS
            && wcscmp(m_curVolName, other.m_curVolName) == 0)
         || (this->m_dwError != ERROR_SUCCESS && other.m_dwError != ERROR_SUCCESS);
}

Some auxiliary variables would help:

bool operator == (FindVolumeWrapper const& other) const
{
    const bool bothGood = (this->m_dwError == ERROR_SUCCESS) &&
                          (other.m_dwError == ERROR_SUCCESS);
    const bool bothBad  = (this->m_dwError != ERROR_SUCCESS) &&
                          (other.m_dwError != ERROR_SUCCESS);
    const bool sameName = (wcscmp(m_curVolName, other.m_curVolName) == 0);

    return (bothGood && sameName) || bothBad;
}

Yes this will always evaluate all expressions, though the improvement in readability is still worth it in my book. The comparisons are negligible in any modern machine, so I wouldn't worry about that. The string comparison has the potential to be expensive, so if you really mind that, add an if to avoid wcscmp when the first condition is not met.

Instead of defining one constructor that takes a boolean and one that takes no parameters, with the objective of creating the start and end iterators, you could use a more descriptive method by defining two dummy types and using those instead. Example:

// These are empty, we just need the names
struct StartIteratorTag { };
struct EndIteratorTag   { };

class FindVolumeWrapper
{
public:
    FindVolumeWrapper(StartIteratorTag) { ... }
    FindVolumeWrapper(EndIteratorTag) { ... }
};

std::set<std::wstring> volumeNames(FindVolumeWrapper(StartIteratorTag()), FindVolumeWrapper(EndIteratorTag()));

Your current method is also not bad thought, this is just another alternative.

Finally, this SO question also discusses about iterator types, I recommend a look at it for further reference. And this one compares the Input/Forward Iterator types.


Getters and setters in a Person class I thought to do away with getters and setters behind the real world objects such as Person, Company or Address, i.e. getName and setName.

Each of these have public enum Attrib of states.

And the state is actually a pure Object mapped to a private HashMap.

package model;

import java.util.HashMap;
import java.util.Map;

public class Person {

    public enum Attrib {
        NAME, //String
        EMAIL, //String
        PHONE; //int

        @Override
        public String toString() {
            return name().toLowerCase();
        }
    }

    private final Map<Person.Attrib, Object> attribs;

    public Person(String name, String email, int phone) {
        attribs = new HashMap<>();
        attribs.put(Person.Attrib.NAME, name);
        attribs.put(Person.Attrib.EMAIL, email);
        attribs.put(Person.Attrib.PHONE, phone);
    }

    public Object getAttrib(Person.Attrib attribute) {
        return attribs.get(attribute);
    }

    public boolean setAttrib(Person.Attrib attribute, Object value) {
        if (attribute == Person.Attrib.PHONE && !(value instanceof Integer)) {
            return false;
        }
        attribs.put(attribute, value);
        return true;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Person) {
            Person person = (Person) o;
            String _this = (String) this.getAttrib(Person.Attrib.NAME);
            String _that = (String) person.getAttrib(Person.Attrib.NAME);
            return _this.equalsIgnoreCase(_that);
        }
        return false;
    }

    @Override
    public int hashCode() {
        return attribs.get(Person.Attrib.NAME).hashCode();
    }

    @Override
    public String toString() {
        return (String) attribs.get(Person.Attrib.NAME);
    }
}

I did saved some getters and setters but I guess it can't justify that all attributes are objects. To check what instanceof the getAttrib(Person.Attrib attribute) is, i.e. skim the class source to know whether you deal with a String or an Integer or Whatever, type cast it.

As you observed, casting within your implementation of setAttribute() is ugly.  Worse than that, returning Object from getAttribute() is horrible — you've given up all type safety.  In a loosely typed language, that would just be business as usual.  However, in Java, the caller would have to cast the result (cumbersome and a potential source of bugs) or just treat it as an opaque Object (spreading the nastiness throughout the program).

Are you sure that you want to represent phone numbers as integers?  You would only get 9 digits reliably.  That's not enough to hold, say, an American phone number including the area code, which would be 10 digits.  Not to mention, you may need country codes, extension numbers, and spaces or punctuation for readability.  A string may be more appropriate after all.

Now, suppose that you just store all three attributes as strings, which eliminates the type safety issue.  What if you want to implement validation within setAttribute()?  You would end up putting in a switch, which would defeat any code savings you have achieved by doing this instead of implementing a separate setter for each attribute.

In summary, this is a bad idea, unless you had a requirement to associate many obscure or arbitrary attributes with a person (e.g. pet, priest, etc.).  In that case, you would implement something more elaborate, such as

public abstract class ModelEntity {
    public String getAttribute(String attrname);
    public void setAttribute(String attrname, String value) throws ValidationException;
    public ModelEntity getRelationship(String relname);
    public void setRelationship(String relname, ModelEntity obj) throws ValidationException;
}

public class Person extends ModelEntity {
    ...
}

public class Pet extends ModelEntity {
    ...
}

… but you would be doing that out of necessity, not out of laziness.  If you really wanted to be sloppy and lazy, you might as well publicly expose the Person's instance variables (not that I'm recommending that at all!).

Returning false to indicate validation failure is poor design.  I would throw an exception to force the caller to deal with it.

Your hashCode() and equals() methods need to be consistent.  If your equals() compares names case insensitively, then your hashCode() should also squash the name to lowercase.


Check whether array is sorted recursively I'm trying to implement isSorted method checking whether given array is sorted recursively. I've written two types, one is similar to merge sort logic, the another is like loop. Can they be made more efficient? Is there any thing I overlooked?

class SortedRecursive {
    public static void main(String[] args) {
        List<Integer> test = new ArrayList<>(Arrays.asList(9, 9, 9));
        List<Integer> test2 = new ArrayList<>(Arrays.asList(9, 10, 11));
        List<Integer> test3 = new ArrayList<>(Arrays.asList(5, 5, 3, 7));
        List<Integer> test4 = new ArrayList<>(Arrays.asList(1,2,2,3,3,4));

        System.out.println("test(nlogn) -> " + isSorted(test));
        System.out.println("test(n) -> " + isSortedAnotherVersion(test, 0));
        System.out.println("test2(nlogn) -> " + isSorted(test2));
        System.out.println("test2(n) -> " + isSortedAnotherVersion(test2, 0));
        System.out.println("input(nlogn) -> " + isSorted(test3));
        System.out.println("input(n) -> " + isSortedAnotherVersion(test3, 0));
        System.out.println("output(nlogn) -> " + isSorted(test4));
        System.out.println("output(n) -> " + isSortedAnotherVersion(test4, 0));
    }

    public static boolean isSorted(List<Integer> arr) {
        if (arr == null || arr.size() == 0) {
            return false;
        }

        if (arr.size() == 1) {
            return true;
        }

        int middleIndex = arr.size() / 2 ;
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        for (int i = 0; i < middleIndex; i++) {
            left.add(arr.get(i));
        }

        for (int i = middleIndex; i < arr.size(); i++) {
            right.add(arr.get(i));
        }

        //System.out.println("left -> " + left + " right -> " + right);

        boolean result = left.get(middleIndex - 1) <= right.get(0);

        return isSorted(left) && result && isSorted(right);

    }

    public static boolean isSortedAnotherVersion(List<Integer> arr, int index) {
        if (arr.size() == 1 || index == arr.size() - 1)
            return true;
        if (arr.get(index) > arr.get(index + 1)) return false;
        return isSortedAnotherVersion(arr, index + 1);
    }

}

Version 1:

Basically OK, but the copying of elements to another list is unnecessary. Have a look at List.sublist on how to create lists from a given index range.

Additionally, you should change the return statement to result && isSorted(left) && isSorted(right) so that the recursion does not take place if result is already false. (Look up short-circuiting in logical statements.)

Version 2:

NO. It is much better not to copy the elements and use indexes into the unmodified structure, but here you recurse for every element in the list, i.e. the recursion depth equals the list size. This is a total no-go, as it will definitely blow your stack if we are talking about serious data sizes.

Nevertheless, explore the option of using indexes (maybe a start-index AND an end-index) into the given structure some more and combine it to a divide and conquer-approach as in your first solution.

Happy coding!


Bringing the average score up to 9.5 I've been trying my hand at some simple problems on the website topcoder.com. I've been able to solve most of the problems I've tried so far in the Easy/Medium section, but I'm scoring very low. The points are based on running time and the amount of memory used by the program AFAIK.

This is a quick piece of code that I submitted and scored around 75/200, I was just wondering what sort of things I should be avoiding or looking out for in order to write more efficient code?

Quick summary of the problem at hand:

  Start with an array of test scores, calculate average and add new test scores of 10/10 to the array until the average is 9.5 or higher.

public class AimToTen{
    public static int need( int[] marks ){
        double average = 0, total = 0;
        int extras = 0;

        for( int x : marks )
            total += x;

        average = total / marks.length;

        if( average >= 9.5 )
            return 0;

        while( average < 9.5 ){
            extras++;
            total += 10;

            average = total / ( marks.length + extras );
        }

        return extras;
    }
}

The trick is not to loop to determine how many extra elements there is to add but to calculate them. A little mathematical consideration can show that you need to add 19 * marks.length - 2 * total elements.

So a faster solution would be:

public static int need(int[] marks) {
    int total = 0;
    for (int x : marks)
        total += x;

    return Math.max(19 * marks.length - 2 * total, 0);
}

If the number of extra steps to add with the result of that calculation is negative, it means the input array already satisfied the condition and we can return 0.

Here are the result of a small JMH benchmark comparing the code in your question and the above code. The two codes are given a random array of integers between 0 and 10, with a size going from 100,000 to 100,000,000 (Windows 10, JDK 1.8.0_66, i5 3230M @ 2.60GHz).

Benchmark             (arraySize)  Mode  Cnt     Score    Error  Units
StreamTest.testNeed        100000  avgt   30     8,208 ±  0,218  ms/op
StreamTest.testNeed       1000000  avgt   30    78,823 ±  0,834  ms/op
StreamTest.testNeed      10000000  avgt   30   798,294 ±  7,651  ms/op
StreamTest.testNeed     100000000  avgt   30  8038,244 ± 77,131  ms/op
StreamTest.testNeed2       100000  avgt   30     0,037 ±  0,004  ms/op
StreamTest.testNeed2      1000000  avgt   30     0,621 ±  0,179  ms/op
StreamTest.testNeed2     10000000  avgt   30     4,143 ±  0,090  ms/op
StreamTest.testNeed2    100000000  avgt   30    41,597 ±  1,499  ms/op

This shows a tremendous improvement! The code is at least 100x faster.

@Warmup(iterations = 10, time = 1000, timeUnit = TimeUnit.NANOSECONDS)
@Measurement(iterations = 10, time = 1000, timeUnit = TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class StreamTest {

    private static final Random RANDOM = new Random();

    @State(Scope.Benchmark)
    public static class ArrayContainer {

        @Param({ "100000", "1000000", "10000000", "100000000"})
        private int arraySize;

        private int[] marks;

        @Setup(Level.Iteration)
        public void setUp() {
            marks = RANDOM.ints(arraySize, 0, 10).toArray();
        }

    }

    public static int need( int[] marks ){
        double average = 0, total = 0;
        int extras = 0;

        for( int x : marks )
            total += x;

        average = total / marks.length;

        if( average >= 9.5 )
            return 0;

        while( average < 9.5 ){
            extras++;
            total += 10;

            average = total / ( marks.length + extras );
        }

        return extras;
    }

    public static int need2(int[] marks) {
        int total = 0;
        for (int x : marks)
            total += x;

        return Math.max(19 * marks.length - 2 * total, 0);
    }

    @Benchmark
    public int testNeed(ArrayContainer c) {
        return need(c.marks);
    }

    @Benchmark
    public int testNeed2(ArrayContainer c) {
        return need2(c.marks);
    }

}


Generic Merge Sort in C++ I wanted to implement merge sort in a generic way. I was not sure whether I should use the iterator or the container for the template type. I did not find a way to infer the container type using iterator_traits, so I decided to use the templated type for the container. Please let me know what you think!

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
void printArray(const T& a) {
    for (auto i: a) {
        cout << i << " ";
    }
    cout << endl;
}

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n < 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort<T>(begin, begin + n/2);
    auto secondHalf = mergeSort<T>(begin + n/2, end);
    auto firstIt = firstHalf.begin();
    auto secondIt = secondHalf.begin();
    T merged;
    while (firstIt != firstHalf.end() && secondIt != secondHalf.end()) {
        if (*firstIt < *secondIt) {
            merged.push_back(*firstIt);
            ++firstIt;
        } else {
            merged.push_back(*secondIt);
            ++secondIt;
        }
    }
    while(firstIt != firstHalf.end()) {
        merged.push_back(*firstIt);
        ++firstIt;
    }
    while(secondIt != secondHalf.end()) {
        merged.push_back(*secondIt);
        ++secondIt;
    }
    return merged;
}

int main() {
    vector<int> a = {3, 0, 7, 5, 7, 8, 3, 1};
    printArray(mergeSort<vector<int>>(a.begin(), a.end()));
    return 0;
}

While your merge step in mergeSort works it should be put into its own function:

// Exercise: make `my_merge` even more generic
template <typename Iterator, typename OutputIterator>
void my_merge(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              OutputIterator out)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            *out++ = *first1++;
        } else {
            *out++ = *first2++;
        }
    }

    while(first1 != last1) {
        *out++ = *first1++;
    }
    while(first2 != last2) {
        *out++ = *first2++;
    }
}

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n < 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort<T>(begin, begin + n/2);
    auto secondHalf = mergeSort<T>(begin + n/2, end);

    T merged;

    my_merge(firstHalf.begin(), firstHalf.end(),
             secondHalf.begin(), secondHalf.end(),
             std::back_inserter(merged));
    return merged;
}

Note that I had to call my_merge that way since std already contains std::merge, which we can use instead:

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    auto n = end - begin;
    if (n < 2) {
        return T(begin, end);
    }
    auto firstHalf  = mergeSort<T>(begin, begin + n/2);
    auto secondHalf = mergeSort<T>(begin + n/2, end);

    T merged;

    std::merge(firstHalf.begin(), firstHalf.end(),
               secondHalf.begin(), secondHalf.end(),
               std::back_inserter(merged));
    return merged;
}

The merge and the parameters begin and end are good examples why using namespace std has to be handled with care. All those names are already in std. Use using namespace std only if you know the risks.

That being said, your generic variant will only work with random access iterators. If you want to make it more generic, you have to use std::distance and std::next instead of end - begin and begin + n/2:

template<typename T>
T mergeSort(typename T::iterator begin, typename T::iterator end) {
    const auto n = std::distance(begin, end);

    if (n < 2) {
        return T(begin, end);
    }
    const auto midpoint = std::next(begin, n / 2);

    const auto firstHalf  = mergeSort<T>(begin, midpoint);
    const auto secondHalf = mergeSort<T>(midpoint, end);

    T merged;

    std::merge(firstHalf.begin(), firstHalf.end(),
               secondHalf.begin(), secondHalf.end(),
               std::back_inserter(merged));
    return merged;
}

Even if you don't want to use std::next re-use the midpoint.


Statistics about gaps in DNA sequences Noobie to Numba here, I'm trying to get faster code from existing function but the result is not faster. 10 times faster would be heaven, but I know nothing about optimization.
This is code about parsing gaps in DNA sequences pairwise alignment and doing statistics about it.
The code looks like this:

import re
import time
import numpy as np
from numba import autojit, int32, complex64
sstart = 10
send = 52
absoluteRoiStart = 19 #rank of the first nucleotide in the ROI
absoluteRoiStop = 27 #rank of the the first nucleotide after the ROI
#ROI is here  'TATCGA---CAG|TA-----TACTA-C|G--TTGAGAGAGAC-CCCA'
#between |    'T--CGACCAC--|-GATCGAG---ATC|GGCTT--------CTC--A'
source =      'TATCGA---CAGTA-----TACTA-CG--TTGAGAGAGAC-CCCA'
sequence =    'T--CGACCAC---GATCGAG---ATCGGCTT--------CTC--A'
realSource = 'AAGGTTCCAATATCGACAGTATACTACGTTGAGAGAGACCCCACATGACTGACTACGT'

tresholds = {
    "DEL" : {
        "other" : 2,
        "slippage": 2,
        "quantity" : 7
    },
    "INS" : {
         "other" : 3,
         "slippage": 3,
         "quantity" : 7
    },
    "MUT" : {
        "other" : 3,
        "slippage": 3,
        "quantity" : 7
    },
    "NA" : {
        "other" : 3,
        "slippage": 3,
        "quantity" : 7
    }
}

def getAllGaps(sequence1, sequence2):
    starts = []
    stops = []
    lengths = []
    types = []
    locations = []
    gap = '(\-)+'
    x = re.compile(gap)
    for m in x.finditer(sequence1):
        #Get Gap satrt, stop and length
        start,stop = m.span()
        #Test if Gap is slippage(compression or extension)
        if start > 1 and stop < len(sequence2):
            h = sequence2[start-1:stop+1].upper()
            i = sequence1[start-1:stop+1]
            repetitions = i.replace('-', h[0]).upper(), i.replace('-', h[-1]).upper()
            if h == repetitions[0] or h == repetitions[1]:
                slippage = True
            else:
                slippage = False
        else:
            slippage = False
        starts.append(start)
        stops.append(stop)
        lengths.append(stop-start)
        if slippage:
            types.append(2)
        else:
            types.append(1)
        locations += range(start, stop)
    d = [starts, stops, lengths, types]
    return {'locations': locations, 'bounds': d}

def getAlignmentData(source, sequence, sstart, tresholds):
    insertionData = getAllGaps(source, sequence)
    alignmentLength = len(source)
    oneArray = np.ones(alignmentLength)
    oneArray[insertionData['locations']] = 0
    absoluteIndex = oneArray.cumsum()-1+sstart
    relativeIndex = np.arange(alignmentLength)
    tf = (absoluteIndex >= absoluteRoiStart) & (absoluteIndex < absoluteRoiStop)
    absoluteBounds = absoluteIndex[tf]
    relativeBounds = relativeIndex[tf]
    relativeRoiStart = int(relativeBounds.min())
    relativeRoiStop = int(relativeBounds.max())
    events = np.array(insertionData['bounds'], dtype=np.int32)
    insertionStartingInRoi = events[:,(events[0] >= relativeRoiStart) & (events[1] <= relativeRoiStop)]
    print(insertionStartingInRoi)
    deletionData = getAllGaps(sequence, source)
    events = np.array(deletionData['bounds'], dtype=np.int32)
    deletionOverlappingRoiOrStartingInRoi = events[:,((events[0] <= relativeRoiStart) & (events[1] >= relativeRoiStart)) | ((events[0] >= relativeRoiStart) & (events[1] <= relativeRoiStop))]
    print(deletionOverlappingRoiOrStartingInRoi)

t0 = time.time()
getAlignmentData(source, sequence, sstart, tresholds)
t1 = time.time()
getAlignmentData(source, sequence, sstart, tresholds)
t2 = time.time()

print(str(t1-t0)+' to first try')
print(str(t2-t1)+' to second try')

When I add the @jit decorator on the two functions, I get slower code. Do I need to do something special, like signatures? Can Numba make this code faster or do I need to use Cython?

After profiling your code as:

import cProfile, pstats, StringIO
pr = cProfile.Profile()
pr.enable()
for it in range(0,10000):
    getAlignmentData(source, sequence, sstart, tresholds)

pr.disable()
s = StringIO.StringIO()
sortby = 'cumulative'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
print s.getvalue()

You will get:

1370129 function calls (1370122 primitive calls) in 3.249 seconds

   Ordered by: cumulative time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
10000    1.003    0.000    3.249    0.000 test.py:71(getAlignmentData)
20000    1.071    0.000    1.684    0.000 test.py:38(getAllGaps)
20000    0.171    0.000    0.171    0.000 {numpy.core.multiarray.array}
20000    0.160    0.000    0.160    0.000 {method 'reduce' of 'numpy.ufunc' objects}
10000    0.018    0.000    0.121    0.000 {method 'min' of 'numpy.ndarray' objects}
400022    0.119    0.000    0.119    0.000 {method 'append' of 'list' objects}
180000    0.107    0.000    0.107    0.000 {method 'replace' of 'str' objects}
100000    0.106    0.000    0.106    0.000 {range}

You can use Cython or f2py to optimise memory management starting with getAllGaps, which is simpler, and then go for getAlignmentData.

Keep in mind that you need to deactivate outputs and take long runs to measure real speedup.

If you compile your code using nuitka you can get 9x speedup.

     110128 function calls (110121 primitive calls) in 0.355 seconds

Ordered by: cumulative time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
20000    0.158    0.000    0.158    0.000 {method 'reduce' of 'numpy.ufunc' objects}
10000    0.011    0.000    0.101    0.000 /usr/local/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/numpy/core/_methods.py:28(_amin)
10000    0.022    0.000    0.096    0.000 /usr/local/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/numpy/core/numeric.py:141(ones)
20000    0.025    0.000    0.081    0.000 /usr/local/Frameworks/Python.framework/Versions/2.7/lib/python2.7/re.py:192(compile)
10000    0.008    0.000    0.076    0.000 /usr/local/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/numpy/core/_methods.py:25(_amax)
20000    0.056    0.000    0.056    0.000 /usr/local/Frameworks/Python.framework/Versions/2.7/lib/python2.7/re.py:230(_compile)
10000    0.037    0.000    0.037    0.000 {numpy.core.multiarray.copyto}
10000    0.037    0.000    0.037    0.000 {numpy.core.multiarray.empty}

All you need to do is install nuitka and run:

$ nuitka mycode.py

You also need a larger dataset to run a proper benchmark. Since it's easy to keep small data in cache, the profiler can provide misleading results.


Maxcounters in JavaScript I am trying to solve this question: MaxCounters.

Solving it is straightforward, but solving it fast enough is proving very difficult. How can I improve the performance of this code? At the moment it is too slow for the large_random_2 and extreme_large tests.

function solution(N, A) {
    const M = A.length;
    let max = 0;
    let counters = new Array(N);

    if (M <= 0) {
        return -1;
    }

    // set counters to 0
    for (let i = 0; i < N; i++) {
        counters[i] = 0;
    }

    for (let K = 0; K < M; K += 1) {
        if (A[K] === N + 1) {
            // set counters to last maximum
            for (let j = 0; j < N; j++) {
                counters[j] = max;
            }
        } else if (A[K] > 0 && A[K] <= N) {
            // add one to counter
            counters[A[K] - 1] = counters[A[K] - 1] + 1;
            // update maximum
            if (counters[A[K] - 1] > max) {
                max = counters[A[K] - 1];
            }
        }
    }

    return counters;
}

You can save some time by not running through every counter and setting them to the maximum each time max gets called. Since they are all equivalent at the start and after each time the max is called, you can just record the current maximum counter value (in between each call of max) and add it all together at the end, rather than updating every counter element each time max is called.

let currentTally = {};
let currentMax = 0;
let total = 0;
for (let K = 0; K < M; K += 1) {
        if (A[K] <= N) {
             if(currentTally[A[K]]){
                 currentTally[A[K]] += 1;
             }else {
                 currentTally[A[K]] = 1;
             }
             if( currentTally[A[K]] > currentMax) {
                  currentMax = currentTally[A[K]];
             }
        }

        if (A[K] === N + 1) {
            total += currentMax;
            currentTally = {};
            currentMax = 0;
        }
        }
    }
    for(let i = 0; i < counters.length; i++) {
         if(currentTally[i]){
             counters[i] = total + currentTally[i];
         }else{
             counters[i] = total;
         }
    }

Also, this way, no need to set all counters to zero in the first place.


My Python 3.6 script to detect stamp card redeem fraud and prepare a csv report I have a requirement to write a Python 3.6 script which should be able to detect following case within a time period and be able to create a text file report that lists the condition violated and transaction that caused the violation:

Redeeming over 3 time on same stamp card within 10 mins

The required table in database for storing user and stamp card details has following structure-

Here the 'to_sate' column with values 2,3 and 4 means a card is redeemed.

Now, I have written following script to fulfill above requirement and it is working as expected. In my local environment it is taking 2.7 minutes to complete the process for 36000 records-

def insert_data(csv_import_path, csv_export_path):
    import time
    from multiprocessing import Pool
    import multiprocessing
    import pandas as pd
    import pymysql
    # Connect to the database
    engine = pymysql.connect(host='localhost',
                             user='admin',
                             password='MY_PASSWORD',
                             db='MY_DB',
                             charset='utf8mb4',
                             cursorclass=pymysql.cursors.DictCursor)
    df = pd.read_sql(
        "SELECT stamps_record_id, user_id,  stamp_card_id, stamp_time, merchant_id, merchant_store_id FROM rmsdb.user_stamping_records where to_state in (2,3,4) order by stamp_card_id",
        engine)
    df.to_csv(csv_import_path)
    df = pd.read_csv(csv_import_path, index_col=["stamps_record_id"])
    unique_users = df.user_id.unique()
    df["stamp_time"] = pd.to_datetime(df["stamp_time"])
    num_processes = multiprocessing.cpu_count()
    s_time = time.time()
    with Pool(num_processes) as p:
        final_df = pd.DataFrame()
        for i in range(0, len(unique_users)):
            user = unique_users[i]
            new_df = df[df.user_id == user]
            sid = new_df.stamp_card_id.unique()
            for i in sid:
                fdf = new_df[new_df.stamp_card_id == i]
                # len(fdf) can be user given value
                if len(fdf) > 3:
                    for i in range(0, len(fdf)):
                        g = (fdf.iloc[i:i + 3])
                        if len(g) >= 3:
                            x = (g.tail(1).stamp_time.values - g.head(1).stamp_time.values).astype("timedelta64[s]")
                            if x[0].astype(int) < 600:
                                final_df = final_df.append(g)

    e_time = time.time() - s_time
    #     final_df.drop_duplicates(keep="first").to_csv("C:\\Users\\rahul.khanna\\Desktop\\user_stamping_records_frauds.csv", index=False)
    final_df.drop_duplicates(keep="first").to_csv(csv_export_path, index=False)

    print("Total Time taken is: " + str(e_time / 60) + " minutes.")

if __name__ == '__main__':
    insert_data("C:\\Users\\hitman\\Desktop\\user_stamping_records_import.csv", "C:\\Users\\hitman\\Desktop\\user_stamping_records_frauds.csv")

I have converted the df to dictionary for a sample-

34198: '2018-10-13 16:48:03', 34199: '2018-10-13 16:48:03', 34200: '2018-10-13 16:48:03', 34201: '2018-10-13 16:48:03', 34202: '2018-10-13 16:48:03', 34203: '2018-10-13 16:48:03', 34204: '2018-10-13 16:48:03', 34205: '2018-10-13 16:48:03', 34206: '2018-10-13 16:48:03', 34207: '2018-10-13 16:48:03', 34208: '2018-10-13 16:48:03'

Before moving my script to production, I need your suggestion for any improvement in my code.

Can anyone please have a look on my code and let me know any improvement in it?

Let me know also if I forgot to include any required information here.

The description of the problem in the post says that the case to be detected is redeeming "over 3 time" but what the code actually detects is 3 times or more. Which is right?
The description of the problem in the post says that the case to be detected is redeeming:

  on same stamp card within 10 mins

But what the code actually detects is redeeming:

  on same stamp card by the same user within 10 mins

Which of these is right? It seems to me that the description in the post would be better, because otherwise someone could avoid detection by switching to a new user account after redeeming twice. (Maybe the software ensures that each stamp card is redeemable only by one user, but in that case why check the user at all?)
The code assumes that the database will return records for each same stamp card id in increasing stamp time order, otherwise this won't work:

g.tail(1).stamp_time.values - g.head(1).stamp_time.values

But the SQL query only orders them by stamp card id, not by stamp time. Perhaps it happens to be the case at the moment that records are added to the table in stamp time order. But it is a bad idea to depend on this, because a change to the way the database is updated could break this assumption. It would be more robust to be explicit and write:

ORDER BY stamp_card_id, stamp_time

Here's what I suspect is the main performance problem:

for i in range(0, len(unique_users)):
    user = unique_users[i]
    new_df = df[df.user_id == user]

The expression df[df.user_id == user] looks innocent, but actually it has to loop over all the records in the dataframe twice: once to test user_id == user, and a second time to select the matching records. And this has to be done for every user. So if there are 36,000 records and (say) 10,000 unique users, then the user_id == user test gets run 360,000,000 times!

Instead of iterating over the unique users and then finding the records for each user, use Panda's groupby method to efficiently group the records by user.

But looking at my point §2 above, is this step really necessary? Perhaps what we really need to do is to ignore the users altogether and go straight to the stamp card ids.
The same anti-pattern occurs in the stamp card processing code:

sid = new_df.stamp_card_id.unique()
for i in sid:
    fdf = new_df[new_df.stamp_card_id == i]

This needs to become:

for fdf in df.groupby(['stamp_card_id']):

If you really do care about the users as well as the stamp cards, then you should order the query results by both:

ORDER BY user_id, stamp_card_id, stamp_time

and group by both:

for fdf in df.groupby(['user_id', 'stamp_card_id']):

The code creates a multiprocessing pool, but does not use it! You have to call the pool's methods, for example multiprocessing.Pool.apply, to take advantage of the pool—it doesn't work by magic.

But actually I suspect that there's no need to use multiprocessing here. Once you have eliminated the quadratic runtime behaviour as discussed above, then it should run in an acceptable amount of time in a single process.


Please check out my code incrementer I recently developed code that can run as a function parameter but I'm not quite sure how vulnerable it is to hacks and/or cheats.
Also, is there anything I could improve?

const h1 = document.getElementById('hi')

world = "world";

function testCode(codeEntered) {
    var code = codeEntered;
  var run = code *= 1;
  return(run);
}
<button onclick="testCode(h1.textContent = world)">
Test
</button>

<h1 id="hi">
Hello
</h1>

Some thoughts:

Writing testCode(h1.textContent = world) is a bit unconventional, and might not do what you expect: this is the same as writing the two lines
h1.textContent = world;
testCode(world);

because the assignment (the first line) evaluates to the value of the right hand side.

Instead of writing var code = codeEntered;, you can save yourself a line and just use the variable codeEntered instead of making a new variable.

The line  var run = code *= 1; also is a bit unexpected. This is equivalent to writing
code = code * 1;
var run = code;

But code is a string, and multiplying it by 1 evaluates to NaN (try it!), so after that line, code == run == NaN.

Code style: return(run); would typically be written return run; instead (it's not a function).

In summary, testCode actually always returns NaN, but the value then gets thrown away because it isn't used anywhere. In effect, your code actually just runs h1.textContent = world when you click the button, then runs testCode whose value isn't used (but is always NaN anyway).

I hope this gives you some useful feedback.


ExactlyOne extension method I often find in codebases something on the order of if (sprockets.Count() > 0) which is easily replaced with LINQ's if (sprockets.Any()). This keeps the entirety of sprockets from having to be iterated over completely (to get the count) then comparing to zero. Further, the business logic often reads something like "if there are any sprockets, inform the user of the subtotal". I also often see similar logic for exactly one of something: if (sprockets.Count() == 1) which doesn't have an easy, low-cost LINQ alternative. So I've created one here:

public static bool ExactlyOne<TSource>(this IEnumerable<TSource> source)
{
    if (source is null)
    {
        throw new ArgumentNullException(nameof(source));
    }

    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
    {
        return enumerator.MoveNext() && !enumerator.MoveNext();
    }
}

Usage is if (sprockets.ExactlyOne()) Here are unit tests. There is one helper method called Infinite() which is a never-ending enumerable, which will baffle sprockets.Count(), but not sprockets.ExactlyOne():

[TestClass]
public sealed class ExactlyOneTests
{
    [TestMethod]
    [ExpectedException(typeof(ArgumentNullException))]
    public void TestNull()
    {
        int[] nullArray = null;

        Assert.IsFalse(nullArray.ExactlyOne());
    }

    [TestMethod]
    public void TestZero()
    {
        int[] zero = Array.Empty<int>();

        Assert.IsFalse(zero.ExactlyOne());
    }

    [TestMethod]
    public void TestOne()
    {
        int[] one = { 1 };

        Assert.IsTrue(one.ExactlyOne());
    }

    [TestMethod]
    public void TestTwo()
    {
        int[] two = { 1, 2 };

        Assert.IsFalse(two.ExactlyOne());
    }

    [TestMethod]
    public void TestInfinite()
    {
        IEnumerable<int> infinite = Infinite();

        Assert.IsFalse(infinite.ExactlyOne());
    }

    private static IEnumerable<int> Infinite()
    {
        while (true)
        {
            yield return 0;
        }
    }
}

Looking for overall review - is the code readable, maintainable, performant. Do the tests cover the expected cases or are there more to consider?

Q&A

  Is the code readable?

ExactlyOne states very clearly what the method is supposed to do.
source is null seems odd to me (does that even compile?). I'd prefer source == null. (Edit from comments: a topic about is null vs == null)
IEnumerator<TSource> enumerator = source.GetEnumerator() can be written as var enumerator = source.GetEnumerator().

  Is the code maintainable?

Since you are looking for a sibling function of Any<T>(), I would also include a ExactlyOne<T>(Func<T, bool> predicate).

  Is the code performant?

It does seem so, right? But notice that LINQ is optimized for IEnumerable<T> that is also ICollection<T>, in which case Count is used. Implementations should have an eager implementation of this property. Your method could also use this optimization Count == 1.
I actually noticed (in my eyes) unexpected behavior in LINQ: Count<T>() is optimized for ICollection<T> but Any<T() is not. This means you arguably could make a slightly faster implementation than LINQ.
An in-depth comparison is required to find the most optimized approach. As discussed in the comments, testing the different implementations against a variety of input sources should yield us which method perfoms best under which conditions.

  Do the tests cover the expected cases or are there more to consider?

You cover null, empty, 1, multiple, early exit on infinite.. but perhaps also test on ICollection<T> and custom IEnumerable<T> implementations with eager and/or lazy loading.

Reference Source: LINQ Any vs Count

// not optimized for ICollection<T> (why ??)
public static bool Any<TSource>(this IEnumerable<TSource> source) {
    if (source == null) throw Error.ArgumentNull("source");
    using (IEnumerator<TSource> e = source.GetEnumerator()) {
        if (e.MoveNext()) return true;
    }
    return false;
}

public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
    if (source == null) throw Error.ArgumentNull("source");
    if (predicate == null) throw Error.ArgumentNull("predicate");
    foreach (TSource element in source) {
        if (predicate(element)) return true;
    }
    return false;
}

// optimized for ICollection<T>
public static int Count<TSource>(this IEnumerable<TSource> source) {
    if (source == null) throw Error.ArgumentNull("source");
    ICollection<TSource> collectionoft = source as ICollection<TSource>;
    if (collectionoft != null) return collectionoft.Count;
    ICollection collection = source as ICollection;
    if (collection != null) return collection.Count;
    int count = 0;
    using (IEnumerator<TSource> e = source.GetEnumerator()) {
        checked {
            while (e.MoveNext()) count++;
        }
    }
    return count;
}


Removal of a character to make a string a palindrome This code determines which index for a given string if that character is removed will produce a palindrome string.

  For eg
    s = "baa"
    After removing b the string "aa" is palindrome.

Here this is what I have written until now. Due to time complexity problems, it exceeds 2ms. How this can be made faster?

#include <iostream>
#include <string>
using namespace std;

bool checkPalindrome(string s){
  bool found = true;
  int len = s.length();
  for(int i=0;i<len;i++){
    if(s[i] != s[len-i-1])
    {
      found = false;
      break;
    }
   }
  return found;
 }  // end of function

   int main() {

     int test;
     cin>>test;   // get the number of test case
     for(int i=0;i<test;i++){
       string s;
       cin>>s;    // get the string as input
       if(checkPalindrome(s)){
         cout<<-1<<endl;   //if already string is palindrome
       }
       else{
         int len = s.length();
         for(int i=0;i<len;i++){
           string aa = s.substr(0,i) + s.substr(i+1,len);
           if(checkPalindrome(aa)){
             cout<<i<<endl;
             break;
           }
       }
     }

   }
   return 0;
  }

Some Improvements:

Your checkPalindrome function is returning whether the string is a palindrome or not. What if it returns an index, at which it fails?
Try working with that. Right now, you are calling the checkPalindrome function O(string-length), and checkPalindrome in itself is O(string-length), making it a square time algorithm.

Wikipedia article on Big O notation
A minor improvement: do you need to iterate over the entire string to determine if it is a palindrome?