Mouseover effect for radio buttons I'm very much a beginner and have put together some JavaScript to control a pair of radio buttons which essentially behave as links.

I'm doing this as sort of a self-initiated project, or bit of fun. I know I don't have to use radio buttons, but it's something I just wanted to do.

It simply checks the radio button when you hover over it, and at the same time highlights the accompanying text. Or, highlights the text when hovered over, and also checks the accompanying radio button.

When the cursor moves out, no longer hovering over, the elements go back to their normal states.

I feel like there has to be a much cleaner way of implementing this.

Here is my mark up of the two radio buttons:

<form name=links>

        <input type="radio" name="fb" onMouseOut="out_event_01()" onMouseOver="over_event_01()" />

Button1

        <input type="radio" name="tw" onMouseOut="out_event_02()" onMouseOver="over_event_02()" />

Button2

</form>

As you can see I have a lot of onMouseOut and onMouseOver events.

This is the JavaScript I'm using:

function over_event_01()
{
var links = document.links.fb;
links.checked = true;
document.getElementById('fb_link').style.color = 'black';
}
function out_event_01()
{
var links = document.links.fb;
links.checked = false;
document.getElementById('fb_link').style.color = 'rgb(153,153,153)';
}
function over_event_02()
{
var links = document.links.tw;
links.checked = true;
document.getElementById('tw_link').style.color = 'black';
}
function out_event_02()
{
var links = document.links.tw;
links.checked = false;
document.getElementById('tw_link').style.color = 'rgb(153,153,153)';
}
function over_event_03()
{
var links = document.links.fb;
links.checked = true;
document.getElementById('fb_link').style.color = 'black';
}
function out_event_03()
{
var links = document.links.fb;
links.checked = false;
document.getElementById('fb_link').style.color = 'rgb(153,153,153)';
}
function over_event_04()
{
var links = document.links.tw;
links.checked = true;
document.getElementById('tw_link').style.color = 'black';
}
function out_event_04()
{
var links = document.links.tw;
links.checked = false;
document.getElementById('tw_link').style.color = 'rgb(153,153,153)';
}

Without re-writing all your code I do have a few suggestions for you:

Don't use inline javascript (onMouseeOut, onMouseOver) always use event listeners (I'll show you how the code example below).  The reason for this is twofold: first it separates your javascript from your HTML second it makes your code even more maintainable if you change a listener you have one place to look.
Use classes instead of inline styles (for the same reasons mentioned above)

this means replace the style=xxx with a css classname (again i'll have an example in the code below)

A lot of your code can be condensed into small reuseable functions since a lot of it is repetitive.

Since you are new to JavaScript I'll avoid some of of the intermediate patterns that I think may apply here such as wrapping this entire functionality in an instantly invoked function expression (IIFE) but you really should read this article by Ben Alman http://benalman.com/news/2010/11/immediately-invoked-function-expression/

So lets look at how it can be improved with some psudo code.  First Lets create one wrapper function that will encapsulate all your functionality.  First set some function variables to your links and radios.  Then we attach events for most browsers and older versions of IE, then we create two generic functions to handle your mouseenter and mouseleave. These functions will handle the duplicated logic of checking

function overOut(){
 //these variables will be accessable by all the inner functions so we only declare them once
  var fbLinks = document.links.fb,
      twLinks = document.links.tw
      fbLink = document.getElementById('fb_link'),
      twLink = document.getElementById('tw_link');

  //check for standard event listener
  if(fbLink.addEventListener){
    //here i'm assuming that fblinks are the links you want to highlight
    fbLink.addEventListener("mouseover",radioOverFunction(this,fbLinks));
  }
  //ie events
  else if(fbLink.attachEvent){
    //here i'm assuming that fblinks are the links you want to highlight
    fbLink.attachEvent("mouseover",radioOverFunction(this,fbLinks));
  }

  /***************************************************
  *  repeat the above code but for mouseout events   *
  ***************************************************/

  var radioOverFunction = function(radio,target){
      //in here you would set check the radio and set the classname on the target
      target.className = 'mouseOverClassName';
  };

  var radioLeaveFunction = function(radio,target){
      //in here you would set check the radio and set the classname on the target
      target.className = 'standardClassName';
  }

}


Django models: different methods on each instance? Imagine I have code like this in (it's about the concept; this is example code):

# models.py
from django.db import models

class Monster(models.Model):
    x = models.FloatField()
    y = models.FloatField()
    def use_unique_ability(self, target):
        ''' different monsters types will implement this differently '''
    def check_attack(self, player): # should I attack this player?
        ''' different monsters types will implement this differently '''
    class Meta:
        abstract = True

class SlimyMonster(Monster):
    def __init__(self):
        self.attack = 3
        self.hit_points = 10
    def use_unique_ability(self, target):
        target.hit_points -= 2 * target.attack
    def check_attack(self, player): # should I attack this player?
        return player.hit_points < self.hit_points

class CaerbannogRabbit(Monster):
    ''' well, you get the idea '''

# many more monsters

Each monster has the same attributes and method names, but different values and implementation. Monster would probably be an interface in Java. Each monster type will override only some of the many methods.

This technically works, but it has some significant downsides:

Each monster is a new database table with the same columns
Because of that, I need a lot of queries to check for all monsters
I need GenericForeignKey to reference individual monsters (instances of any of the model classes)

The other extreme isn't exactly pretty either. This is based on dynamically mixin a base class to an instance (+this) and how to import a module given the full path?:

# models.py
from django.db import models
from os.path import join
from inspect import isclass
from imp import load_source
from settings import PATH_TO_MONSTER_FILES

class InconsistentMonsterError(Exception): pass

class MonsterClass(models.Model):
    name = models.CharField(max_length = 32)
    attack = models.PositiveIntegerField(default = 1)
    defense = models.PositiveIntegerField(default = 10)
    method_file = models.CharField(max_length = 128) # it's a source file, not media file, so I'm using CharField
    def __init__(self, *args, **kwargs):
        super(MonsterClass, self).__init__(*args, **kwargs)
        try:
            modul = load_source(self.method_file, join(PATH_TO_MONSTER_FILES, self.method_file))
        except IOError:
            raise InconsistentMonsterError('no file named %s' % join(PATH_TO_MONSTER_FILES, self.method_file))
        classes = [cls for cls in [getattr(modul, x) for x in dir(modul)] if isclass(cls)]
        if not len(classes):
            raise InconsistentMonsterError('file %s doesn\'t contain classes' % join(PATH_TO_MONSTER_FILES, self.method_file))
        bases = self.__class__.__bases__ + (classes[-1], )
        self.__class__ = type('NewClassName', bases, {
            '__module__': MonsterClass.__module__,
        })

class MonsterInstance(models.Model):
    cls = models.ForeignKey(MonsterClass)
    x = models.FloatField()
    y = models.FloatField()

and for each monster a file like this:

# slimy_monster.py
class SlimyMonster(): # not a Model
    def use_unique_ability(self, target):
        ''' different monsters types will implement this differently '''
    def check_attack(self, player): # should I attack this player?
        ''' different monsters types will implement this differently '''

The code seems... inellegant. It's complex, and it's like using eval (execute code based on an 'external' string)
Every monster must be changed in two places: the database and a file (although I suppose I could define database values in the file)

Given these two options, should I use one of them, or something in between? I tend towards the second option, but I'm not quite satisfied.

What you want is inheritance as a proxy model.

In your subclasses, use the following Meta option:

class SlimyMonster(Monster):
    class Meta:
        proxy = True

    def some_method_to_override(self):
        ...

This way the subclassing has no effect on the database side, only on the Python side.


Partitions of an integer and filtering by number of elements I have Python code to get the partitions of an integer and then display those who have a certain number of elements. The problem is, the program is rather slow and takes a considerable amount of time to complete the partitions of numbers beyond 25. I am certain my algorithm is not optimal and would like to know how to improve it.

#Function to create a partition, receives the integer n
def particion(n):
    if n == 1:
        return [[1]]

#Add the number itself to the results
    res = [[n]]

#Go through all the numbers
    for i in range(1, n):
        a = n-i
        R = particion(i)
    #Add the results of the recursion
        for r in R:
            if r[0] <= a:
                res.append([a] + r)

    return res

#Only print the partitions of length x
resultado=particion(n)
for i in range(0,len(resultado)):
    if len(resultado[i])==x:
        print(resultado[i])

First a technical note.  In mathematics, 2+3 is the same partition as 3+2.  The right name for what you are looking for are combinations.

That said, you are spending most of your time coming up with answers that you will throw away.  Don't.  Spend it coming up with answers that you won't throw away.  Like this:

def compositions(n, size):
    if n == 0 and size == 0:
        yield []
    elif 0 < size:
        for i in range(1, n-size+2):
            for c in compositions(n-i, size-1):
                yield c + [i]

for c in compositions(25, 2):
    print(c)

Update

Since you actually do want partitions, here is an equivalent approach for partitions.

def partitions(n, size, limit=None):
    if limit is None:
        limit = n
    if n == 0 and size == 0:
        yield []
    elif size * limit < n:
        # No solutions possible.
        pass
    elif 0 < size:
        for i in range(1, min(limit, n-size+1)+1):
            for c in partitions(n-i, size-1, i):
                yield [i] + [c]


Convert unsigned Integer to ASCII in x86 assembly This is my best effort to code an x86 32 bits to get an unsigned int (4 bytes) and convert it into a string. My strategy was successively divide the number by ten and fulfill the remainder of the div according its position in the heap pre-allocated string. I am assuming the bigger value has 10 digits at most.

File i2a.s:

# convert integer to ASCII

.section .data

num:
    .long   123456789
str:
    #    0123456789A
    .string "          \n"
len:
    .long .-str

.section .text
    .globl _start

_start:
    # last index of str
    lea str+0xa, %edi
    # initialize eax
    mov num, %eax
loop:
    # divide
    xor %edx, %edx
    mov $0xa, %ecx
    div %ecx        # quocient: EAX / remainder: EDX

    # convert remainder to ASCII
    add $0x30, %edx
    # store it in str[i--]
    mov %dl, -1(%edi)
    dec %edi

    # if quocient is zero, we're done.
    cmp $0, %eax
    je  print

    # if i == 0, we're done.
    cmp     str, %edi
    je  print

    # repeat.
    jmp loop

print:
# print content of str
    mov $4, %eax
    mov $1, %ebx
    lea str, %ecx
# where the generated string starts?
#   str[%edi]
    sub $str, %edi
    add %edi, %ecx
# what is the final length of str?
#   len -= %edi
    mov len, %edx
    sub %edi, %edx
    int $0x80

exit:
    mov $1, %eax
    mov %edx, %ebx
    int $0x80

I know there are some criticism about div and its slow execution. Please, fell free to criticize it as well as to point out caveats, tips, and tricks.

Simple script I'm using to build it: (it will create bin directory in cwd)

#! /bin/bash

# binaries output directory (objects and executables are placed there)
OUTDIR=bin
[ -d $OUTDIR ] || mkdir $OUTDIR

as --32 $1.s -o $OUTDIR/$1.o \
    && ld -m elf_i386 $OUTDIR/$1.o -o $OUTDIR/$1 \
    && $OUTDIR/$1

Usase:

./build i2a

It’s been a good many years since I wrote significant code in x86 assembly language, but I’ll wade in here.

Yes, div is a fat pig of an instruction.  It not only takes a ridiculous number of clock cycles, but it uses many of the dispatch ports, clogging the CPU so it can’t do much else while waiting on the result.  See the links in this S.O. answer.

This is because division is difficult.  You could look up how to transform division by a constant (10 in this case) into multiplication and code that.

But, successive division/modulo by 10 is now I learned it.

The biggest speed benefit will be from allowing pipelining to work well and not stalling.  Sometimes you code two or three different copies of the loop and interweave them so that there is more independent calculations to work on at the same time.  To that end, you might start by dividing by 10000 once and then doing high digits and low digits separately in interwoven loops.

But, using the div instruction makes that difficult because it has pre-targeted registers that it uses, and worse, the instruction does not pipeline.

I think the fastest would be to use the div-less algorithm with vector SIMD instructions to compute multiple digits at the same time.

sketch of an idea

Avoid all division/modulo and instead build up the decimal representation using decimal arithmetic!

A 64-bit value can also be treated as 8 bytes; each byte is a digit (not packed as BCD nibbles, but one per byte).  You can add them by adding the 64-bit integers — each byte will add, and there can be no caries outside of the byte because the largest result is 18 and you can hold up to 255.

In particular, doubling such a value means adding it to itself.  The hard part, which I’ll explain later, is following that up with carry propagation.

So, start with a 8-digit unpacked decimal set to all zeros; call that Accumulator.

Loop while In != 0  :

Take your normal integer (called In) and mask off the lowest bit, getting a result that is either 0 or 1.  Add that to the least significant byte of Accumulator.  Note that you have no if here, no branching.  It will simply add zero accomplishing nothing, or add one.  You can do that add using a 32-bit or any other sized int aliased with the Accumulator, not just a byte, because you know the carry will not happen out of the byte.  I mention this because byte arithmetic is slightly slower than 32/64.

Then, shift In right one bit.

Add Accumulator to itself, using the aliasing trick I mentioned before.

Process the carries.

[end of loop]

Convert Accumulator to an ASCII representation by adding 0x30 to each byte.  This can be a constant of 64 bits, so you do this in one add.

So, how do you propagate the carries?  Use SSE instructions.

Load the Accumulator into an SSE register.  Use an instruction which compares each (byte) element against 10 and produces a packed bitmap of the results.  There will be 16 bits, indicating which bytes are too large for decimal.

Use that bitmap as a mask to subtract 10 from each enabled byte.  You can use the same SSE register loaded with all 10's for both steps.

Shift the bitmap left by one bit.  Now use that as a mask to add 1 to every enabled byte.

Now, saving the SSE register back to RAM and loading it again will slow it down.  So do the doubling (adding the register to itself) in SSE, also.  Adding the new In bit can be done with separate instructions, or rolled into the carry step by setting the least bit (or not) after shifting left.  Whichever is the least amount of jumping through hoops or avoiding a branch.


Iterating over JSON docs This Lua code runs in redis. It iterates over some JSON docs, and applies some logic based on the user (if any) making the request. I'm sure there's a lot I can improve here.

local function iterAll(limit)
  local start = 0
  local stop = limit-1
  local ids = redis.call('zrevrange', 'questions-by-latest', start, stop)
  local i = 0
  local function it()
    i = i+1
    if i <= #ids then
      return ids[i]
    elseif i > #ids then
      start = start+limit
      stop = stop+limit
      i = 1
      ids = redis.call('zrevrange', 'questions-by-latest', start, stop)
      if #ids > 0 then
        return ids[i]
      end
    end
  end
  return it
end

local function filter(qid, optUid)
  local q = cjson.decode(redis.call('hget', 'questions', qid))
  if not q['is-active'] then return false end

  if optUid then
    local u = cjson.decode(redis.call('hget', 'users', optUid))
    if #u['ignored-tags'] > 0 then
      for idx, itag in ipairs(u['ignored-tags']) do
        for jdx, qtag in ipairs(q['tags']) do
          if itag == qtag then return false end
        end
      end
    end
  end

  return true
end

local offset = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])

local optUid = false
if #ARGV == 3 then
  optUid = tonumber(ARGV[3])
end

local i = 0
local j = 0
local ids = {}
for qid in iterAll(limit) do
  if filter(qid, optUid) then
    i = i+1
    if i > (offset+limit) then break end
    if i > offset then
      j = j+1
      ids[j] = qid
    end
  end
end

return ids

Firstly, you've hard-coded all of your key names instead of using the KEYS table for passing them to the script - this is both hard to maintain as well as incompatible with clustering.

Next, consider using MessagePack (cmsgpack in Redis' Lua) instead of JSON when serialiazing/deserializing questions (q) and users (u) - it is leaner and faster.

Also, the jdx, qtag loop looks like a membership test, so it should be replaced with a check against an associative table instead.

Overall, the code appears to be quite complex with multiple nested loops. Without more information on the values' sizes, it is hard to make an educated guess whether this is a viable approach, but intuitively I'd be hesitant about this. Furthermore, it is hard to understand the logic's purpose - it is perfectly possible that there are more efficient ways to do/model what you want/need, but it would be better if you'd provide an overview of the context and requirements before.


Convert minute to time for display I am new to javaScript, I just coded a method where I can convert a minute to a time in hh:mm AP/PM. I was then displaying the time in a table.  I was wondering if there is a better approach to this? Because my code seems quite messy, with many if and else statement.

function convertMinsToHrsMin(minutes) {
                var str = '';
                var h = Math.floor(minutes / 60);
                var m = minutes - (h * 60);
                h = h < 10 ? '0' + h : h;
                m = m < 10 ? '0' + m : m;
                if (h >= 12) {
                    if (h == 12) {
                        str = "PM";
                    }
                    else if (h >= 22) {
                        h = (h - 12);
                        str = "PM";
                    }
                    else {
                        h = '0' + (h - 12);
                        str = "PM";
                    }
                }
                else {
                    if (h == 0) {
                        h = 12;
                        str = "AM";
                    }
                    else {
                        str = "AM";
                    }
                }
                return h + ":" + m + " " + str;
            }

            startTime = convertMinsToHrsMin(720);
            endTime = convertMinsToHrsMin(1080);

            alert(startTime);
            alert(endTime);

Here is a jsFiddle to work on: https://jsfiddle.net/Issaki1/txns3mhc/

I was wondering if there is a better approach to this?

Yes. Use a library. Using what's already done is always better than doing it yourself. ;)

The next best thing you could do is convert minutes into milliseconds and instantiate a Date object from it. From there, JS does most of the heavy lifting for you. Here's an example (not extensively tested, but you get the idea):

const pad = n => `0${n}`.slice(-2)

const convertMinsToHrsMin = mins => {
  const date = new Date(mins * 60 * 1000)

  // Need to be UTC since timestamps are universal
  // but normal time methods operate based on local time.
  const hours = date.getUTCHours()
  const minutes = date.getUTCMinutes()

  // If 0, as in 00:00 or 12:00, default to 12.
  const hours12 = hours % 12 || 12
  const period = hours >= 12 ? 'PM' : 'AM'

  return `${pad(hours12)}:${pad(minutes)}${period}`
}

startTime = convertMinsToHrsMin(720);
endTime = convertMinsToHrsMin(1080);

alert(startTime);
alert(endTime);

As for your code:

Use console.log instead of alert. I know alert is a quick way to visualize values, but getting the habit of using console.log will do wonders for your skin.
Avoid very deep and branchy conditionals. if statements don't do anything on its own and has to be mutating some variable. That means you define variables up top. There is a chance that you might miss a branch and leave that variable empty or contain an unwanted value.
Use a ternary for short conditionals, like determining AM and PM. It's short, and gets you into not mutating variables.
Use template literals to construct strings. This way, you don't need to break out strings and you always get a string (not a NaN should your expression fail you due to coercion).
And lastly, get familiar with the native APIs. They do lots of heavy lifting for you so you don't have to write it yourself.


Finding a route in maze matrix Maze puzzle

  A 1 in input matrix means "allowed"; 0 means "blocked". Given such a matrix, find the route from the 1st quadrant to the last (n-1, n-1).

I would like to get some feedback to optimize and make this code cleaner. Also let me know if O(n!) is the complexity, where n is the dimension of the maze.

final class Coordinate {
    private final int x;
    private final int y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Maze {

    private final int[][] maze;

    public Maze(int[][] maze) {
        if (maze == null) {
            throw new NullPointerException("The input maze cannot be null");
        }
        if (maze.length == 0) {
            throw new IllegalArgumentException("The size of maze should be greater than 0");
        }

        this.maze = maze;
    }

    public List<Coordinate> solve() {
        return getMazePath(0, 0, new Stack<Coordinate>());
    }

    private List<Coordinate> getMazePath(int row, int col, Stack<Coordinate> stack) {
        assert stack != null;

        stack.add(new Coordinate(row, col));

        if ((row == maze.length - 1) && (col == maze[0].length - 1)) {
            Coordinate[] coordinateArray = stack.toArray(new Coordinate[stack.size()]);
            return Arrays.asList(coordinateArray);
        }

        for (int j = col; j < maze[row].length; j++) {

            if ((j + 1) < maze[row].length && maze[row][j + 1] == 1) {
                return getMazePath(row, j + 1, stack);
            }

            if ((row + 1) < maze.length && maze[row + 1][col] == 1) {
                return getMazePath(row + 1, col, stack);
            }
        }

        return Collections.emptyList();
    }

    public static void main(String[] args) {
        int[][] m = {  {1, 0, 0},
                       {1, 1, 0},
                       {0, 1, 1} };

        Maze maze = new Maze(m);

        for (Coordinate coord :  maze.solve()) {
            System.out.println(coord.getX() + " : " + coord.getY());
        }
    }
}

First of all I don't think the time complexity is O(n!). You are doing DFS(unknowingly). So the time complexity would be O(n + m) and AFAIK you can't solve maze problem less than that unless you are using BFS. But nevertheless it will not make any difference.

Now your code has some bug, I think you didn't consider that way and it's ok if you are a beginner like me. Try to change the maze matrix to

int[][] m = {{1, 1, 1},
             {1, 0, 1},
             {1, 1, 0},
             {0, 1, 1}};

and you will get the picture. Maze can be solved but still it's not printing anything.
So what is the solution? BACK-TRACK.

Moreover you are only taking account of possibilities of going right and down, why not up and left?

You have hard-coded that the start point will be always (0,0) and end point will be (N-1, N-1)... yeah your puzzle says that but this will not be same for every puzzle right? So think of a general solving technique...

SPOILER ALERT

   Web resource

 My solution

Code Cleaning Tips

getMazePath method can be cleaned. In 1st if you are checking if you have reached the goal or not. Now move the checking condition to another method and return true if you have reached the goal.
In for loop(no need of this if you are using recursion) you are checking if you are in the maze and path exists or not... see how you are repeating yourself for every condition... think of a general solution.
No need for maintaining a Stack, since you are not using any of Stack's method but only add, which you can also use with a List.
Override toString method in Coordinate class. And get rid of long S.o.p s.

Good Luck!


Law of Demeter and data models? Inspired by this question, but hopefully not a duplicate.

I understand that the Law of Demeter is very useful in case of services interacting with other services, for example it's much easier to mock the other services in unit tests.
What about services interacting with data models, though?

Let's say I have a hierarchy of immutable classes:

public final class Document {
    private final List<Page> pages;
    // Constructor, getter, ...
}

public final class Page {
    private final List<Paragraph> paragraphs;
    // Constructor, getter, ...
}

public final class Paragraph {
    private final List<Line> lines;
    // Constructor, getter, ...
}

Let's say I want to do something with certain lines in a document doc:

public void doSomething(Document doc) {
    for (Page page : doc.getPages()) {
        for (Paragraph para : page.getParagraphs()) {
            for (Line line : para.getLines()) {
                if (someCondition(line)) {
                    someAction(line);
                }
            }
        }
    }

Now, as far as I understand, the above code doesn't obey the Law of Demeter.
However, I don't want to force the law at all cost and clutter the model (here, the Document class) with tens of methods like:

public List<Line> filterWrtSomeCondition();
public List<Line> filterWrtSomeOtherCondition();

Or maybe there's a third way?  I suspect that the Law of Demeter applies primarily to services interacting with other services.  Is it a valid interpretation?

For some perspective on the LoD, read "The Law of Demeter Is Not A Dot Counting Exercise".  In particular the part under the heading "I Fought The Law and The Law Won".

I think in this instance that pages, paragraphs and lines are very logical subcomponents of documents.  These each have different but related behaviour.  The each also serve different purposes.

Forcing the document to handle interactions with subcomponents will - as you say - lead to clutter (and more chance of introducing troublesome issues).

The big thing about the LoD is that it aims to reduce coupling.  However adding methods to Document doesn't really reduce coupling as you're still writing code that says "do x to line y" - you're just asking Document to do it for you.

Don't get me wrong, the LoD is useful.  But like all principles it has to be used correctly to stay useful.

(Funnily enough a similar question with a similar answer as been asked at SO.)

Conclusion

In short I don't see any benefit for you in talking to Document rather than it's contained Pages, Paras, & Lines.  Frankly I don't think there's any ROI for you.


Simplex number calculation (all dimensions) in python How can I calculate simplex numbers in all dimensions?
Example:

dimension:     2|      3|      4|
simpl(1)       1|      1|      1|
simpl(2)       3|      4|      5|
simpl(3)       6|     10|     15|
simpl(4)      10|     20|     35|
simpl(5)      15|     35|     70|

First I considered about a recursive implementation (in python):

def simplex(n, dim):
    if dim == 1:
        return n
    else:
        i = 1
        ret = 0
        while i <= n:
            ret += simplex(i, dim-1)
            i+=1
        return ret

The algorithm works, but because of the recursion its really slow, especially if your dimension number is 5 or higher.

You should use a for loop rather than a while loop to solve the problem.
This is as you're just re-writing a for loop.
Using a for loop you can change the loop to a comprehension, and take the sum of it.
This allows you to get the code:

def simplex(n, dim):
    if dim == 1:
        return n
    dim -= 1
    return sum(simplex(i, dim) for i in range(1, n + 1))

However this can be simplified.
When dim is the bullet point the function is:

\$n\$
\$\Sigma_{i = 1}^{n} i\$
\$= \frac{n(n + 1)}{2}\$
\$\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} j)\$
\$= \frac{n(n + 1)(n + 2)}{6}\$
\$\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} (\Sigma_{k = 1}^{j} k)))\$
\$= \frac{n(n + 1)(n + 2)(n + 3)}{24}\$
\$\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} (\Sigma_{k = 1}^{j} (\Sigma_{l = 1}^{k} l))))\$
\$= \frac{n(n + 1)(n + 2)(n + 3)(n + 4)}{120}\$

Since we're getting a pattern, we know that the top part of the fraction is:

\$\Pi_{i = 0}^{dim - 1} n + i\$

And if we use oeis to find the denominator it says it's probably the factorial sequence.
And so it's likely:

\$\frac{\Pi_{i = 0}^{dim - 1} n + i}{dim!}\$

This is actually really easy to write in Python.
And so you can get a significant speed up.

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

def simplex(n, dim):
    return reduce(mul, (n + i for i in range(dim))) // factorial(dim)


Cat program in x86 NASM I wrote cat program in x86 NASM and I would like to know if there is anything that can be improved.

This implementation of cat supports:

Reading from stdin.
Multiple arguments.

I checked few cases and program behaves exactly like original cat command.

I was thinking if I should add labels like write even if I wouldn't jmp to them, so code would be cleaner.

Code:

section .text
    global _start

_start:
    ;esi=1
    mov esi, 1

    ;if(argc==1)
    ;goto open
    cmp dword [esp], 1
    jnz open

    ;else
    ;fd=STDIN_FILENO
    mov dword [fd], 0
    jmp read

open:
    ;fd=open(path,oflag)
    mov eax, 5
    mov ebx, [esp+esi*4+4]
    mov ecx, 0
    int 0x80
    mov [fd], eax

read:
    ;bytes_read=read(fd,buf,BUFSIZE)
    mov eax, 3
    mov ebx, [fd]
    mov ecx, buf
    mov edx, BUFSIZE
    int 0x80

    ;write(STDOUT_FILENO,buf,bytes_read)
    mov edx, eax
    mov eax, 4
    mov ebx, 1
    mov ecx, buf
    int 0x80

    ;if(bytes_read!=0)
    ;goto read
    cmp edx, 0
    jnz read

    ;close(fd)
    mov eax, 6
    mov ebx, [fd]
    int 0x80

    ;esi++
    inc esi

    ;if(esi<argc)
    cmp dword esi, [esp]
    jl open

exit:
    mov eax, 1
    mov ebx, 0
    int 0x80

section .data
    BUFSIZE equ 1024

section .bss
    buf resb BUFSIZE
    fd resd 1

I was thinking if I should add labels like write even if I wouldn't jmp to them, so code would be cleaner.

Writing labels that aren't jumped to is fine. Provided they have meaningful names, it can help to understand the program.

My comments (not in a particular order)

;esi=1
mov esi, 1

This is a redundant comment! I already can see what the instruction does. What I can't know is what the ESI register will be used for.

;if(argc==1)
;goto open
cmp dword [esp], 1
jnz open

Here the comment does not correspond to the code. The code actually does if(argc!=1).

cmp edx, 0
jnz read

The more usual way to test for zero would be test edx, edx. It has a smaller encoding and is generally a bit faster.

mov ebx, 0

Similarly, zeroing a register is best done using the xor instruction (xor ebx, ebx). This is both faster and shorter.

mov dword [fd], 0

Your program would not need this instruction at all, if you would move the fd variable from the .bss section to the .data section using fd dd 0.

This in turn opens up an opportunity to shorter the code from:

    cmp dword [esp], 1
    jnz open
    mov dword [fd], 0
    jmp read
open:

to:

    cmp dword [esp], 1
    je  read
open:

Also note that in conjunction with the cmp instruction, it's better to use je and jne.
In conjunction with the test instruction, it's preferable to use jz and jnz.

je and jz have an identical encoding but choosing the right instruction mnemonic better expresses what the intention of the code is.

;if(esi<argc)
cmp dword esi, [esp]
jl open

The argc is by its very nature an unsigned number. After all it's just a count. You should use the conditional jumps that are provided to deal with the unsigned conditions. So better use jb open (JumpIfBelow).
Also there's no point in writing the dword size-tag. The mention of the dword register ESI already dictates the size.

mov edx, eax
mov eax, 4
mov ebx, 1
mov ecx, buf
int 0x80

I always prefer to write the function number directly above the int 0x80 instruction. That way it's immediately clear what function is getting invoked. And for perfection I even assign the registers in a sorted manner:

mov edx, eax
mov ecx, buf
mov ebx, 1
mov eax, 4
int 0x80

Putting it all together

not being afraid to write redundant labels
putting the comments in a separate column for readability
shaving off one more byte by using the fact that ESI==1 when cmp dword [esp], 1 is executed.

section .text
    global _start

_start:
    mov  esi, 1
    cmp  [esp], esi        ;if(argc==1) goto read
    je   read
open:
    xor  ecx, ecx          ;fd=open(path,oflag)
    mov  ebx, [esp+esi*4+4]
    mov  eax, 5
    int  0x80
    mov  [fd], eax
read:
    mov  edx, BUFSIZE      ;bytes_read=read(fd,buf,BUFSIZE)
    mov  ecx, buf
    mov  ebx, [fd]
    mov  eax, 3
    int  0x80
write:
    mov  edx, eax          ;write(STDOUT_FILENO,buf,bytes_read)
    mov  ecx, buf
    mov  ebx, 1
    mov  eax, 4
    int  0x80
more:
    test edx, edx          ;if(bytes_read!=0) goto read
    jnz  read
close:
    mov  ebx, [fd]         ;close(fd)
    mov  eax, 6
    int  0x80
next:
    inc  esi
    cmp  esi, [esp]        ;if(esi<argc)
    jb   open
exit:
    xor  ebx, ebx
    mov  eax, 1
    int  0x80

section .data
    fd   dd 0              ;fd=STDIN_FILENO

section .bss
    BUFSIZE equ 1024
    buf  resb BUFSIZE

Concern

Nowhere in your code do you check for any errors from api calls like open or read. Imagine what might happen in these cases?


Hackerrank "Strings: Making Anagrams" Javascript Solution This is the original problem :

  Input Format

  The first line contains a single string, a.  The second line contains a
  single string, b.

  Constraints

  1<= |a|,|b| <= 10^4

  It is guaranteed that  and  consist of lowercase English alphabetic
  letters (i.e.,  through ). Output Format

  Print a single integer denoting the number of characters you must
  delete to make the two strings anagrams of each other.

  Sample Input

  cde

  abc

  Sample Output

  4

  Explanation

  We delete the following characters from our two strings to turn them
  into anagrams of each other:

  Remove d and e from cde to get c. Remove a and b from abc to get c. We
  must delete  characters to make both strings anagrams, so we print  on
  a new line.

And this is the solution I've came up with using javascript. I've decided to use objects in order to avoid nested for loops which leads to O(M*N). I think my solution is O(M+N+O+P), however, I do believe there's a much better solution out there, and some more refactoring can be done to my code. Anyone?

There are some default I/O codes you may find in the original website

function main() {
  var a = readLine();
  var b = readLine();

  // Creating object with {"k": 5, "a": 2, "b": 1} for example
  var objA = countAlphabetFrequency(a);
  var objB = countAlphabetFrequency(b);

  var numOfDeletionsA = countNumberOfDeletions(objA,objB);
  var numOfDeletionsB = countNumberOfDeletions(objB,objA);

  console.log(numOfDeletionsA + numOfDeletionsB);
}

function countAlphabetFrequency (arrOfAlphabets){
    var resultObj = {}

    for (i = 0; i < arrOfAlphabets.length; i++) {
        if (resultObj[arrOfAlphabets[i]]) {
          resultObj[arrOfAlphabets[i]] += 1;
        } else {
          resultObj[arrOfAlphabets[i]] = 1;
        }
    }
    return resultObj;
}

function countNumberOfDeletions (mainObj, referenceObj){
    var numOfDeletions = 0;

    for (var k in mainObj) {
        if (mainObj.hasOwnProperty(k)) {
          if (mainObj[k] && referenceObj[k]) {
            // Alphabet k exists in both strings
            if (mainObj[k] > referenceObj[k]) {
              // Main string has more k than in reference string
              numOfDeletions += mainObj[k] - referenceObj[k];
              mainObj[k] = referenceObj[k];
            }
          } else {
            // Alphabet k only exists in Main string
            numOfDeletions += mainObj[k];
          }
        }
    }

    return numOfDeletions
}

I like your idea of counting character frequencies first. This allows you to count the required deletions in linear time.

Your code is readable, but readability can be improved by more semantic naming and leveraging modern JavaScript language features.

Naming:

Regarding the variable names a, objA, mainObj, resultObj, arrOfAlphabets: Those identifiers mainly include type information (obj, arrOf). But as a reader, I am more interested in the role of your variables instead of their type. So instead of objA I would prefer to read frequenciesA or even freqA. And instead of arrOfAlphabets I suggest the simpler characters.

For-loops:

First of all, you probably forgot to declare the local loop iterator in for (i = 0; ...). Unfortunately, those omissions can introduce very hard to trace bugs as you now access and potentially share a global variable i.

Also, JavaScript arrays and strings implement the iterable protocoll. This means you can iterate over them using a simpler for-of loop:

for (let char of characters) { ... }

This allows you to replace arrOfAlphabets[i] with the more readable char.

Default properties:

There is a pretty common technique used to handle default values of object properties. Replace

if (obj[arrOfAlphabets[i]]) {
  resultObj[char] += 1;
} else {
  resultObj[char] = 1;
}

with the shorter and idiomatic

resultObj[char] = (resultObj[char] || 0) + 1;

Enumerate object keys:

Instead of

for (var k in mainObj) {
    if (mainObj.hasOwnProperty(k)) { ... }
}

you can nowadays use Object.keys to write

for (let key of Object.keys(mainObj)) { ... }

Refactoring:

You probably noticed the redundancy in

var numOfDeletionsA = countNumberOfDeletions(objA,objB);
var numOfDeletionsB = countNumberOfDeletions(objB,objA);
console.log(numOfDeletionsA + numOfDeletionsB);

If you modify your countAlphabetFrequency function to increment frequencies for string a and decrement frequencies for string b, you can simply sum the absolute frequencies to get the number of required deletions.

If you combine that with a more descriptive approach by replacing for-loops with forEach and reduce, you get a simpler implementation:

// Count character deletions required to make 'a' and 'b' anagrams:
function count(a, b) {
  let freqs = {};
  a.split('').forEach(char => freqs[char] = (freqs[char] || 0) + 1); // increment
  b.split('').forEach(char => freqs[char] = (freqs[char] || 0) - 1); // decrement
  return Object.keys(freqs).reduce((sum, key) => sum + Math.abs(freqs[key]), 0);
}

// Example:
console.log(count('ilovea', 'challenge')); // 9


Simple multi-threaded Java server loop I'm new to sockets and servers in general and I would like to know if I'm doing something really wrong in the following server loop for spawning threads to process requests.

private static ServerSocket server;
private static final Object request_counter_lock = new Object();
private static int request_counter = 0;
private static boolean exit = false;

public static void main(String[] args) {
    try {
        server = new ServerSocket(8000,100);
        // Loop until one of the clients sends an exit request.
        while (!exit) {
            try {
                final Socket socket = server.accept();
                // When a connection is accepted we increment the request
                // counter so when the server starts to shut down it waits
                // until all requests are finished processing.
                synchronized(request_counter_lock) { request_counter++; }
                // Fire up a new thread to process requests.
                new Thread(new Runnable() {
                    @Override
                    public void run() {
                        try {
                            processConnection(socket);
                        } catch (IOException e) {
                            logger.error("unable to process request: " + e.getMessage());
                        } finally {
                            // Make sure we close the socket.
                            SocketCloser.close(socket);
                            // Also decrement the request counter because we just closed
                            // the request socket which means we are done with this client.
                            synchronized(request_counter_lock) { request_counter--; }
                        }
                    }
                }).start(); // Fire up the thread.
            } catch (IOException e) {
                logger.error("error accepting socket connection: " + e.getMessage());
            }
        }
    } catch (IOException e) {
        logger.fatal("unable to start server: " + e.getMessage());
    } finally {
        // If the while loop breaks that means we received an exit request from
        // one of the clients but it's possible that there are still some requests
        // in progress so we can't shut down the server right away. We have to wait
        // until the request counter drops down to 0.
        synchronized(request_counter_lock) {
            logger.info("acquired lock for request_counter");
            while(request_counter > 0) {
                logger.info("request counter is above 0 so waiting");
                try {
                    // Wait 1 second for ongoing clients to finish with their work.
                    request_counter_lock.wait(1000);
                } catch (InterruptedException e1) {
                    logger.error("error in request_counter synchronized block: " + e1.getMessage());
                }
            }
        }
        logger.info("request counter reached 0 so going to close server");
        try {
            server.close();
        } catch (IOException e1) {
            logger.error("unable to close server: " + e1.getMessage());
        }
    }
}

I wouldn't recommend creating new Threads on your own or using Threads without holding onto their references. It makes it too hard to shut down properly. In your example, I think that if SocketCloser.close(socket) throws, then the request_counter will be off by one.

I recommend starting with a thread pool.

ExecutorService pool = ExecutorService.newCachedThreadPool();

You can use a fixed size pool if an infinite pool causes you problems. Then you can submit Runnables to it in the same place you're creating Threads now. Finally, when you want to shut down, you can use the methods shutdownNow() and awaitTermination() on the pool.


Building array of 'truthy' rule conditions I'm running a lot of functions to build a mongoDb request. Based on their response (if not falsy) I'm appending the return values to an array ruleConditions[] which is used later.

Currently I'm doing it this way:

//building ruleConditions
var ruleConditions = {$and: []};

var fromConditions = mongoRequestsHelper.getFromConditions(rule.from);
if (fromConditions) ruleConditions.$and.push(fromConditions);

//and 4 similar blocks

Is there any way to avoid unneeded variables creation (carTypesConditions...)?

Calling functions twice like:

if (mongoRequestsHelper.getFromConditions(rule.moversFilter)) ruleConditions.push(mongoRequestsHelper.getFromConditions(rule.moversFilter))

is not a good idea obviously.

First up, you should really be using more modern variable definitions (using let and const instead of var).

As for your conditional processing for the mongoDB clauses, the simpler way to process the data would be to accumulate all the clauses in to a single temporary array, and then filter that array in to the actual query clause. For example, consider:

const clauses = [
    mongoRequestsHelper.getFromConditions(rule.A),
    mongoRequestsHelper.getFromConditions(rule.B),
    mongoRequestsHelper.getFromConditions(rule.C),
    mongoRequestsHelper.getFromConditions(rule.D),
    ......
];

const ruleConditions = {
    // filter out non-truthy clauses
    $and: clauses.filter(clause => clause)
};


Ask the user random questions from a multiple-choice test I'm quite new to programming and was hoping you wouldn't mind taking a look at my code and giving some points as to how I could clean it up.

Assignment guidelines:

  Create a program that reads multiple choice questions from 1 file and
  gives 10 random questions to the user. Do Not uses classes.

Example of how the questions are stored in the text document I created

Question (end of line)
Option1 (end of line)
Option2 (end of line)
Option3 (end of line)
Option4 (end of line)
Answer (end of line)
(intentionally left blank)
Question2...Question20 (rinse and repeat for remaining questions)

Code I used:

#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>

using namespace std;

struct questionFormat
{
    string question;
    string answersA;
    string answersB;
    string answersC;
    string answersD;
    string answerSheet;
    string space;
};

int main ()
{
    questionFormat q;
    string questions [20];
    string answersA [20];
    string answersB [20];
    string answersC [20];
    string answersD [20];
    string answerSheet [20];
    string space[20];
    int userAnswer [10];
    int testQuestions [10] = {99,99,99,99,99,99,99,99,99,99};
    int counter = 0, num = 0, userCorrect =0, correctAnswer = 0;
    fstream infile("testQuestions.txt", ios::in);
    srand(time(NULL));

    do
    {
        getline (infile, q.question);
        questions[counter] = q.question;

        getline (infile, q.answersA);
        answersA[counter] = q.answersA;

        getline (infile, q.answersB);
        answersB[counter] = q.answersB;

        getline (infile, q.answersC);
        answersC[counter] = q.answersC;

        getline (infile, q.answersD);
        answersD[counter] = q.answersD;

        getline (infile, q.answerSheet);
        answerSheet[counter] = q.answerSheet;

        getline (infile, q.space);
        space[counter] = q.space;

        counter++;
    } while (counter < 20);

    cout << "Welcome to my fantastic test.\nYou will randomly be given 10/20 questions." << endl;

    counter = 0;

    while (counter < 10)
    {
        num = rand()%20;
        cout << "Current random number: " << num << endl;
        cout << "Counter is: " << counter << endl;
        if (bool exists = find(begin(testQuestions), end(testQuestions), num) != end(testQuestions))
        {
            continue;
        }
        else
        {
            testQuestions[counter] = num;
            cout << "\nQuestion # " << counter +1 << endl;
            cout << questions [num] << endl;
            cout << answersA [num] << endl;
            cout << answersB [num] << endl;
            cout << answersC [num] << endl;
            cout << answersD [num] << endl;
            cin >> userAnswer[counter];

            correctAnswer = stoi(answerSheet[num]);
            if (userAnswer[counter] == correctAnswer)
            {
                userCorrect++;
            }
            counter++;
        }
    }
    cout << "You got a total of " << userCorrect << " out of 10 correct" << endl;

    return 0;
}

Cleanup questionFormat

You don't need the space variable.
The variables answersA, etc. should be answerA, etc.
The type of answerSheet can be int. I also think that correctAnswer is a better name for the member.

struct questionFormat
{
   string question;
   string answerA;
   string answerB;
   string answerC;
   string answerD;
   int correctAnswer;
};

Use an array of questionFormat instead of many arrays of strings

The lines

string questions [20];
string answersA [20];
string answersB [20];
string answersC [20];
string answersD [20];
string answerSheet [20];
string space[20];

can be replaced by

questionFormat questions[20];

Create function for reading data

Create function readData and move the code to read the data from main to readData.

int readData(std::string const& inputFile,
              questionFormat questions[],
              int maxQuestions)
{
   fstream infile("testQuestions.txt", ios::in);
   ...
}

Don't assume file IO succeeded

Always check status of file IO operations. It's never safe to assume that they succeeded.

Change the lines that read the input to:

for (counter = 0; counter < maxQuestions; ++counter )
{
   questionFormat& q = questions[counter];

   if ( !getline (infile, q.question) )
   {
      std::cout << "Failed to read a question.\n";
      return counter;
   }

   if ( !getline (infile, q.answerA) )
   {
      std::cout << "Failed to read answer A to a question.\n";
      return counter;
   }

   if ( !getline (infile, q.answerB)  )
   {
      std::cout << "Failed to read answer B to a question.\n";
      return counter;
   }

   if ( !getline (infile, q.answerC) )
   {
      std::cout << "Failed to read answer C to a question.\n";
      return counter;
   }

   if ( !getline (infile, q.answerD) )
   {
      std::cout << "Failed to read answer D to a question.\n";
      return counter;
   }

   if ( !(infile >> q.correctAnswer ) )
   {
      std::cout << "Failed to read the correct answer to a question.\n";
      return;
   }

   // Ignore two lines of text.
   // The first line corresponds to what's left in the stream
   // after reading the correct answer.
   // The second line is the intentionally left space.
   infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
   infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

Simplify the find line

The line

if (bool exists = find(begin(testQuestions), end(testQuestions), num) != end(testQuestions))

can be simplified to:

if (find(begin(testQuestions), end(testQuestions), num) != end(testQuestions))

Move the code to conduct the tests to a separate function

void conductTests(questionFormat questions[],
                  int maxQuestions)
{
   ...
}

The contents of conductTests will be different from your posted code due to use of an array of questionFormat to hold the data.

That will simplify main to:

int main ()
{
   questionFormat questions[20];

   srand(time(NULL));

   int numQuestions = readData("testQuestions.txt", questions, 20);

   conductTests(questions, numQuestions);

   return 0;
}

No need to use an array for userAnswer

The value is read and used inside every iteration of the loop. It can be a simple int. Not only that, it can be in the scope of the while loop instead of being in the function scope.

Here's the complete program:

#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <limits>
#include <algorithm>

using namespace std;

struct questionFormat
{
   string question;
   string answerA;
   string answerB;
   string answerC;
   string answerD;
   int correctAnswer;
};

int readData(std::string const& inputFile,
             questionFormat questions[],
             int maxQuestions)
{
   fstream infile("testQuestions.txt", ios::in);

   for (int counter = 0; counter < maxQuestions; ++counter )
   {
      questionFormat& q = questions[counter];

      if ( !getline (infile, q.question) )
      {
         std::cout << "Failed to read a question.\n";
         return counter;
      }

      if ( !getline (infile, q.answerA) )
      {
         std::cout << "Failed to read answer A to a question.\n";
         return counter;
      }

      if ( !getline (infile, q.answerB)  )
      {
         std::cout << "Failed to read answer B to a question.\n";
         return counter;
      }

      if ( !getline (infile, q.answerC) )
      {
         std::cout << "Failed to read answer C to a question.\n";
         return counter;
      }

      if ( !getline (infile, q.answerD) )
      {
         std::cout << "Failed to read answer D to a question.\n";
         return counter;
      }

      // Ignore two lines of text.
      // The first line corresponds to what's left in the stream
      // after reading the correct answer.
      // The second line is the intentionally left space.
      infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
      infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
   }

   return maxQuestions;
}

void conductTests(questionFormat questions[],
                  int maxQuestions)
{
   int testQuestions [10] = {99,99,99,99,99,99,99,99,99,99};
   int counter = 0;
   int userCorrect = 0;

   cout << "Welcome to my fantastic test.\nYou will randomly be given 10/20 questions." << endl;

   while (counter < 10)
   {
      int userAnswer;
      int num = rand()%maxQuestions;
      cout << "Current random number: " << num << endl;
      cout << "Counter is: " << counter << endl;
      if (find(begin(testQuestions), end(testQuestions), num) != end(testQuestions))
      {
         continue;
      }
      else
      {
         testQuestions[counter] = num;
         cout << "\nQuestion # " << counter +1 << endl;
         cout << questions [num].question << endl;
         cout << questions [num].answerA << endl;
         cout << questions [num].answerB << endl;
         cout << questions [num].answerC << endl;
         cout << questions [num].answerD << endl;
         cin >> userAnswer;

         if (userAnswer == questions[num].correctAnswer)
         {
            userCorrect++;
         }
         counter++;
      }
   }

   cout << "You got a total of " << userCorrect << " out of 10 correct" << endl;
}

int main ()
{
   questionFormat questions[20];

   srand(time(NULL));

   int numQuestions readData("testQuestions.txt", questions, 20);

   conductTests(questions, numQuestions);

   return 0;
}


Number of inversions on a segment I was trying to do this question and I get TLE on one the test cases (the actual link to the question  will ask you to login).
What is an inversion?

An inversion of an element is the number of elements to the left which
are greater. Sum of number of numbers throughout a segment is the
answer.

It is based on Segment Trees.
My attempt is this:
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct segtree {

    int size;
    vector<int> sums;

    void init(int n){
        size=1;
        while(size<n)
            size*=2;
        sums.assign(2*size,0);
    }

    void change(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){sums[x]+=v;return;}
        int m=(lx+rx)/2;
        if(i<m)
            change(i,v,2*x+1,lx,m);
        else
            change(i,v,2*x+2,m,rx);
        sums[x]= sums[2*x+1] + sums[2*x+2];
    }
    void change(int i,int v){
        change(i,v,0,0,size);
    }

    int calc(int l,int r,int x,int lx, int rx){
        if(lx>=l&&rx<=r) return sums[x];
        if(rx<=l||lx>=r) return 0;
        int m =(lx+rx)/2;
        return calc(l,r,2*x+1,lx,m) + calc(l,r,2*x+2,m,rx);
    }
    int calc(int l){
        return calc(l,size,0,0,size);
    }
};

int main(){

    int n, m;
    cin >> n >> m;

    vector<int> a(n);

    for(int i=0;i<n;++i)
        cin >> a[i];

    while(m--) {
        int op;
        cin >> op;

        if(op == 1){

            int x, y;
            cin >> x >> y;

            x-=1;

            segtree st;
            st.init(40);

            int sum = 0;

            for(int i=x;i<y;++i){
                int val = a[i];
                sum += st.calc(val);
                st.change(val-1, 1);
            }

            cout << sum << "\n";

        } else {
            int x, y;
            cin >> x >> y;
            a[x-1]=y;
        }
    }

    return 0;
}

I wanna know a better time complexity version of the program.

Overall Observations
The function main() is too complex and should be broken up into multiple functions, if you do this you might notice that you are recreating your segtree struct for every query when it only needs to be created once and then each query should be applied to that structure.
Recursion is expensive in terms of resources it might be better to find iterative solutions.
The code is difficult to read and that may be why I am the first person answering.
Avoid using #include <bits/stdc++.h>
The header bits/stdc++.h is not part of the C++ programming standard and includes the whole world, this program needs only 2 C++ headers
#include <iostream>
#include <vector>

I realize that the programming challenge probably provided this for you, but that doesn't mean you should keep it if you know the proper includes.
Avoid using namespace std;
If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.
Variable Names
While you are using the variable names from the programming challenge, these variables names are not very descriptive and could cause you or someone who might be maintaining this code in a professional environment to make errors in the code.
Horizontal Spacing
One of the standard conventions in programming is to leave a space between an operator and an operand in any statement, this makes the code easier to read, examples:
        if(rx-lx==1){sums[x]+=v;return;}

versus
        if (rx - lx == 1) { sums[x] += v; return; }

        int m=(lx+rx)/2;

versus
        int m = (lx + rx) / 2;

Vertical Spacing
        if(rx-lx==1){sums[x]+=v;return;}
        int m=(lx+rx)/2;

versus
        if (rx - lx == 1)
        {
            sums[x] += v;
            return;
        }

        int m = (lx + rx) / 2;

As mentioned above, it isn't really clear what the variables m, rx and lx are, especially m.
Unused #define
The code contains:
#define ll long long

This is unused in the scope of the program and should be removed. There are at least 2 ways in C++ that don't require #define, one is a typedef and another is a using statement. While macros will continue to be supported in C++ to remain backwards compatible with C, the trend is to not use macros when possible.
##Magic Numbers
There are Magic Numbers throughout the program function (40, 2, 1), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.
Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.
An enum could be used for the query type.


Python program that draws the Mandelbrot set fractal I wrote a Python program that draws the Mandelbrot set fractal. However, the program is very slow. I would appreciate any feedback on the program, but I would especially appreciate feedback on how to improve the performance of my program.

from PIL import Image, ImageDraw
import numpy as np

def FractalFunc(x, c):
    return (x * x) + c

def IterateFractal(c, iterateMax=100):
    z = 0
    last = np.nan
    for i in range(iterateMax):
        # c = FractalFunc(c, (.05+.5j)) # in case I want to create the Julia set
        z = FractalFunc(z,c)
        # if (np.abs(c) > 2):
        if (np.abs(z) > 2):
            last = i
            break
    return last

def QuickFractal(width=200, height=200, amin=-1.5, amax=1.5, bmin=-1.5, bmax=1.5,
            iterateMax=100, filename="blah.png"):
    (w, h, iMax, iterationValues, histogram) = Fractal(width, height, amin, amax, bmin, bmax, iterateMax)
    iFractal = DrawFractal(w, h, iMax, iterationValues, histogram)
    iFractal.show()
    iFractal.save(filename)

def ShowFractal(frac, filename="test.png"):
    (w, h, iMax, iterationValues, histogram) = frac
    iFractal = DrawFractal(w, h, iMax, iterationValues, histogram)
    iFractal.show()
    iFractal.save(filename)

def Fractal(width=200, height=200, amin=-1.5, amax=1.5, bmin=-1.5, bmax=1.5,
            iterateMax=100):
    aStep = (amax - amin) / (width)
    bStep = (bmax - bmin) / (height)
    """compute iteration values"""
    iterationValues = np.zeros((width, height))
    histogram = np.zeros(iterateMax)
    a = amin
    for x in range(width):
        b = bmin
        for y in range(height):
            c = np.complex(a,b)
            i = IterateFractal(c, iterateMax)
            iterationValues[x][y] = i
            if not(np.isnan(i)):
                histogram[i] = histogram[i] + 1
            b = b + bStep
        a = a + aStep
    return (width, height, iterateMax, iterationValues, histogram)

def DrawFractal(width, height, iterateMax, iterationValues, histogram):
    hue = np.zeros(iterateMax)
    hue[0] = histogram[0] / sum(histogram)
    image = Image.new("RGB", (width, height))
    for i in range(1, iterateMax):
        hue[i] = hue[i-1] + (histogram[i] / sum(histogram))
    """second pass to draw the values"""
    for x in range(width):
        for y in range(height):
            i_count = iterationValues[x,y]
            colorPixel = FractalColor(i_count, iterateMax, hue)
            image.putpixel((x,y), colorPixel)
    return image

def FractalColor(iterate, maxIt, hues):
    if np.isnan(iterate):
        return (0,0,0)
    else:
        grad_point_1 = np.array((0, 0, 255))
        grad_point_2 = np.array((255, 255, 255))
        grad_point_3 = np.array((0, 0, 255))
        hue_mod = (iterate % 100) / 100
        if (0 <= hue_mod < (.5)):
            delta = grad_point_2 - grad_point_1
            start = grad_point_1
        if ((.5) <= hue_mod < (1)):
            delta = grad_point_3 - grad_point_2
            start = grad_point_2
        scalar = ((hue_mod * 100) % (100 / 2))/30
        arr = np.floor(start + np.dot(scalar, delta))
        return tuple(arr.astype(int))

Example output:

The key thing to remember when working with numerical code is that the CPython interpreter is pretty slow (it trades speed for flexibility) and so you must avoid running in the interpreter whenever possible. Instead of iterating in slow Python bytecode using for x in ..., operate on whole arrays by calling the appropriate NumPy function or method, which dispatches to fast compiled code operating on fixed-size numbers.

So to speed up Fractal we must turn it inside out — instead of operating on one pixel at a time, we must operate on the whole array at once.

Let's start out by measuring the performance of the implementation in the post:

>>> from timeit import timeit
>>> timeit(Fractal, number=1)
1.4722420040052384

The constants \$c\$ are computed one at a time:

a = amin
for x in range(width):
    b = bmin
    for y in range(height):
        c = np.complex(a,b)
        # ...
        b = b + bStep
    a = a + aStep

Instead, compute a whole array of constants \$c\$ using numpy.linspace and numpy.meshgrid:

a, b = np.meshgrid(np.linspace(amin, amax, width),
                   np.linspace(bmin, bmax, height), sparse=True)
c = a + 1j * b

The IterateFractal function operates on the \$z\$ value for a single pixel at a time. Instead, we should operate on a whole array of \$z\$ values:

z = np.zeros_like(c)
iterations = np.zeros_like(c, dtype=int)
for i in range(1, iterateMax + 1):
    z = z ** 2 + c
    iterations[abs(z) <= 2] = i

Note that in this implementation, points that never escape from the set have iterations equal to iterateMax (rather than NaN as in the post). This requires a corresponding change to FractalColor:

def FractalColor(iterate, maxIt, hues):
    if iterate >= maxIt:
        return (0,0,0)
    else:
        # ...

Instead of computing histogram one pixel at a time, use numpy.bincount:

histogram = np.bincount(iterations.flatten())

This results in the revised code:

def Fractal2(width=200, height=200, amin=-1.5, amax=1.5, bmin=-1.5,
             bmax=1.5, iterateMax=100):
    a, b = np.meshgrid(np.linspace(amin, amax, width),
                       np.linspace(bmin, bmax, height), sparse=True)
    c = a + 1j * b
    z = np.zeros_like(c)
    iterations = np.zeros_like(c, dtype=int)
    for i in range(1, iterateMax + 1):
        z = z ** 2 + c
        iterations[abs(z) <= 2] = i
    histogram = np.bincount(iterations.flatten())
    return width, height, iterateMax, iterations.T, histogram

Note the iterations.T at the end there: the .T property is a shorthand for numpy.transpose. This is needed because NumPy prefers row-major ordering where a 2-dimensional array is indexed by row, column, but DrawFractal is using column-major ordering where an image is indexed by x, y.  See the Numpy documentation on "Multidimensional Array Indexing Order Issues". If you updated DrawFractal to use row-major indexing then you would avoid the need for this transpose.

This is about 40 times as fast as the original code:

>>> timeit(Fractal2, number=1)
0.03542686498258263

There are a couple of problems with the whole-array approach. First, it wastes work: once a \$z\$ value has escaped the set, we don't need to keep iterating it. Second, by continuing to iterate the \$z\$ value, we might find that it overflows the range of floating-point numbers, resulting in unwanted overflow warnings.

So what we can do is to keep track of the indexes of the pixels that have not yet escaped the set, and only operate on the corresponding values of \$z\$:

def Fractal3(width=200, height=200, amin=-1.5, amax=1.5, bmin=-1.5, bmax=1.5,
            iterateMax=100):
    a, b = np.meshgrid(np.linspace(amin, amax, width),
                       np.linspace(bmin, bmax, height), sparse=True)
    c = (a + 1j * b).flatten()
    z = np.zeros_like(c)
    ix = np.arange(len(c)) # Indexes of pixels that have not escaped.
    iterations = np.empty_like(ix)
    for i in range(iterateMax):
        zix = z[ix] = z[ix] ** 2 + c[ix]
        escaped = abs(zix) > 2
        iterations[ix[escaped]] = i
        ix = ix[~escaped]
    iterations[ix] = iterateMax
    histogram = np.bincount(iterations)
    iterations = iterations.reshape((height, width))
    return width, height, iterateMax, iterations.T, histogram

Note that when operating on a set of indexes like this, it's most convenient to work with a flattened array, so that we only need one array of indexes. (If we used a two-dimensional array, we'd need to maintain two arrays of indexes ix and iy.) So we call numpy.flatten at the start to flatten the array to a single dimension, and numpy.reshape at the end to restore it to two dimensions.

This is about 70 times as fast as the original code:

>>> timeit(Fractal3, number=1)
0.02115203905850649

Now that you've seen how to make Fractal operate on the whole array (rather than one pixel at a time), you should be able to do the same for DrawFractal. (Hint: instead of calling Image.putpixel for each pixel, call Image.putdata once.)


Create file path and filename in JSON and send it to Discord I have been working on a function which I call report. What it does is that whenever I call the report function. I can give it a payload of my dict with some data and as well as reason where I can have custom message or the exception errors of whatever can happened.
For now I have created something simple where I create names for file_path and filename. I check if there is a path for that name already and if not then we create. We create a JSON file with the report data to my local PC and then I send it to discord. Both the JSON file and a small text that describes that there has been and error and to check it out ASAP.
My question here is pretty simple to see if there is anything I can actually improve my code somehow. Make it less code or a better report, I take whatever possible!
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import json
import os
import time
from datetime import datetime
from typing import List

from discord_webhook import DiscordEmbed, DiscordWebhook

# payload example payload = {"store": "burger-king"}
# reason = Custom message or exception err

def report(payload=None, reason=None):

    webhook = DiscordWebhook(
        url="https://discord....."
    )

    embed = DiscordEmbed(title="An error has occurred", color=16711680)

    # -------------------------------------------------------------------------
    # Create file path and filename
    # -------------------------------------------------------------------------

    file_path = f'./error/{payload["store"] if payload else "Other"}'
    filename = f'{datetime.strftime(datetime.now(), "%Y-%m-%d_%H-%M-%S-%f")}.json'

    # Check if the path already exists
    if not os.path.exists(file_path):
        os.makedirs(file_path)

    # Write to a JSON file
    with open(f"{file_path}/{filename}", "w", encoding="utf-8") as f:
        f.write(json.dumps(
            {
                "payload": payload if payload else None,
                "reason": str(reason)
            },
            indent=4,
            ensure_ascii=False
        ))

    # -------------------------------------------------------------------------
    # Filename embed
    # -------------------------------------------------------------------------
    embed.add_embed_field(name="Filename", value=filename, inline=False)

    # -------------------------------------------------------------------------
    # Send files to discord
    # -------------------------------------------------------------------------
    with open(f"{file_path}/{filename}", "rb") as f:
        webhook.add_file(file=f.read(), filename=f"{filename}")

    # -------------------------------------------------------------------------
    # Footer timestamp
    # -------------------------------------------------------------------------
    embed.set_footer(text=f'AutoSnkr | {datetime.now().strftime("%Y-%m-%d [%H:%M:%S.%f")[:-3]}]')

    webhook.add_embed(embed)

    # -------------------------------------------------------------------------
    # Send to discord with exceptions
    # -------------------------------------------------------------------------
    while True:

        response = webhook.execute()

        # Workaround bug from discord_webhook pypi
        if isinstance(response, List):
            assert (len(response) == 1)
            response = response[0]

        # Successful requests
        if response.ok:
            return

        # Rate limit. Wait until the limitation is gone
        elif response.status_code == 429:
            sleep_time = int(response.headers["retry-after"]) / 1000
            time.sleep(sleep_time)

        else:
            print("Big error here! This text needs to be replaced later on")
            return

There's comments above report which should really be a docstring,
since they explain the function's workings.
The default parameters for report are a bit suspect:

The expression payload if payload else None is redundant, can just
be payload then.
str(reason) for the default value None for reason is odd,
maybe that also needs special casing and could be left out of the
JSON body?

Does the value from payload["store"] need escaping / is it safe?
E.g. if it's coming from the server you'd have to validate it before
using it as part of a filename to prevent attacks.
I feel it's a bit over-commented.  Consider "Create file path and
filename" - that's basically what I can discern from the block below,
same as "Check if the path already exists", that's basically the same
as the line if not os.path.exists(file_path).  Consider splitting
off smaller functions that have descriptive names instead of one huge
function, that way you wouldn't have to comment on blocks of code (and
would instead use the function names as descriptors).
with is used, good.
os.makedirs won't do anything if the path already exists, so the
check before it is redundant.
Consider making webhook and embed (global) constants, they
otherwise don't seem to add anything to the function.
After writing the JSON to the file, it's immediately being read back
for the webhook.add_file - avoid that unnecessary computation and
reuse the in-memory representation of the data.
Again, consider splitting the setup phase and the while True loop
into separate functions to help understanding and, potentially,
testability.
The only thing I'd have to complain about in the loop is the fetching
of the retry timeout value: Be conservative in what you expect.  The
server doesn't have to send that value and if it doesn't you'll get
exceptions.  Consider providing a default value and a maximum sleep
amount to not open yourself up to a malicious server (yes, that's a
stretch, but still).
Just noticed:  You're importing typing.List just to check
isinstance - AFAIK you can just use isinstance(response, list)
without the need to import the typing module.  Of course using
typing is great, you'd just have annotate your functions most likely
and use mypy or a similar type-checker ...


Fast canonical indexing of elements in array Given two arrays of elements:

aaabbccdefaa
zzzccddafgzz

I want to check whether these two arrays are equivalent up to a relabeling.
My strategy is to map them into a canonical form and then check whether they share the same canonical form:
# Convert aaabbccdefaa -> 000112234500
canonical <- function(input){
  output <- input
  labels <- unique(input)
  nlabels <- length(labels)
  for (i in 1:nlabels){
    output[grep(labels[i], input)] <- i
  }
  return(output)
}

# try it
input <- c("a","a","a","b","b","c","c","d","e","f","a","a")
canonical(input)

> [1] "1" "1" "1" "2" "2" "3" "3" "4" "5" "6" "1" "1"

Can this R function be faster?

First, why return a vector of characters when the output data is clearly about integers? Instead of initializing

output <- input

i.e., a vector of the same class as input (character), you should have used:

output <- integer(length(input))

to pre-allocate a vector of integers. Integers use less memory; you will also save time avoiding unnecessary conversions from integer to character.

Second, grep is for regular expression matching. When you do grep("a", x), you are checking if x contains an "a" which is not the same as asking if x is exactly "a". In your case, you want exact equality so having used == in output[input == labels[i]] <- i would have been more appropriate. Even better, there is the match function. It is vectorized so you can avoid the for loop and just do:

canonical2 <- function(input){
   labels <- unique(input)
   match(input, labels)
}

Last, you could look into factors. Your code is equivalent to doing:

canonical3 <- function(input) {
   labels <- unique(input)
   as.integer(factor(input, levels = labels))
}

Comparing speeds:

library(microbenchmark)
input <- sample(letters, 1e4, replace = TRUE)

identical(as.integer(canonical(input)), canonical2(input))
# [1] TRUE
identical(canonical2(input), canonical3(input))
# [1] TRUE

microbenchmark(canonical(input), canonical2(input), canonical3(input))

# Unit: microseconds
#               expr       min         lq     median         uq       max neval
 #  canonical(input) 47669.384 49870.0695 51615.3475 53604.0700 65261.986   100
#  canonical2(input)   492.921   529.9210   589.2805   635.7925   966.853   100
#  canonical3(input)   526.412   582.8405   638.5455   718.9310  3821.143   100


C++ Updated Stack Code The original question can be seen here: Stack implementation in C++ using linked list

Changes (with the help of Martin):

Added copy constructor and assignment operator overload
Changed return type of peek() to const T& rather than T (this prevents unnecessary copying of data)
Changed return type of pop() to void; it now only removes the top item rather than returning it on top. The user can call peek() and then call pop() to retrieve and then delete the item. This means we don't have to return T by value, and also maintains the "Strong Exception Guarantee".
Fixed a bug in pop() where the new head is deleted rather than the old one

#ifndef TEST_STACK_H
#define TEST_STACK_H

#include <stdexcept>

template <class T>
class stack {

    struct node {
        T data;
        node* previous;

        node(T data, node *previous) : data(data), previous(previous) {}
    };

    node* head = nullptr;

    int size = 0;
    int max = -1; // -1 so isFull() == false when default constructor used

public:
    stack() = default;

    stack(int max) {
        if (max <= 0) throw std::out_of_range("stack size must be > 0");
        this->max = max;
    }

    // copy constructor

    stack(stack const& rhs) :
        head(copyList(rhs.head)),
        size(rhs.size),
        max(rhs.size) {}

    // assignment operator

    stack& operator = (stack const& rhs)
    {
        stack tmp(rhs);
        swap(tmp);

        return *this;
    }

    ~stack() {
        node* n = head;

        while (n != nullptr) {
            node* previous = n->previous;
            delete n;

            n = previous;
        }
    }

    void push(const T &object) {
        if (isFull()) throw std::overflow_error("cannot push to a full stack");

        head = new node(object, head);
        ++size;
    }

    const void pop() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

        node* old = head;
        head = head->previous;

        --size;
        delete old;
    }

    T peek() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
        return head->data;
    }

    int getSize() {
        return size;
    }

    bool isFull() {
        return size == max;
    }

    bool isEmpty() {
        return head == nullptr;
    }

    void swap(stack& other) noexcept
    {
        using std::swap;
        swap(head, other.head);
        swap(size, other.size);
        swap(max,  other.max);
    }

private:
    node* copyList(node* l)
    {
        if (l == nullptr) {
            return nullptr;
        }
        return new node{l->data, copyList(l->previous)};
    }
};

#endif

#include <stdexcept>

And either <utility> or <algorithm>, for std::swap.

stack(int max) {

I very strongly recommend you make this constructor explicit. Right now it's a non-explicit (implicit) conversion, which means you're permitting your users to convert integers to stacks implicitly:

void foo(stack<int> s);
void bar() {
    foo(42);  // compiles and calls foo with stack<int>(42)
}

The general rule (at least for user codebases) is "make everything explicit unless you have some specific reason that it needs to be implicit." So you should make your node constructor explicit as well.

(I say "at least for user codebases" because the STL itself doesn't follow that principle — partly because the principle wasn't understood in 1998, and partly due to differences of opinion among the authors. "STL style" would be to make stack(int) explicit because it's a one-argument constructor, but leave all zero- and two-argument constructors implicit. I recommend against doing that.)

int max = -1; // -1 so isFull() == false when default constructor used

This comment doesn't help me understand. I would understand INT_MAX, but -1 just looks like it's breaking the class invariant enforced by the one-argument constructor:

if (max <= 0) throw std::out_of_range("stack size must be > 0");

Looking at these two lines in isolation, actually, I briefly wondered "wait, doesn't that always throw? You don't initialize max before that if, so it would have its default value, which is less than zero..." But then I realized that the name max here is overloaded: the max in the if statement is testing the function parameter, not the data member.

To eliminate confusion about name overloading, I strongly recommend that you sigil each of your data members with a trailing underscore: max_, size_, head_.
Then you don't have to write this-> when you access a member:

this->max = max;

can become just

max_ = max;

You don't need the disambiguating this->, because there's no confusion anymore about which max/max_ you mean.

stack(stack const& rhs) :
    head(copyList(rhs.head)),
    size(rhs.size),
    max(rhs.size) {}

Do you see the typo?

Write some unit tests for your code! In particular, now that you've spotted a bug, write a unit test that would have caught this bug and commit it as part of the bugfix. That's called a "regression test."

stack& operator = (stack const& rhs)
{
    stack tmp(rhs);
    swap(tmp);

    return *this;
}

FYI, the copy-and-swap idiom can be written more concisely if you want to:

stack& operator=(stack const& rhs)
{
    stack(rhs).swap(*this);
    return *this;
}

const void pop() {

The const here is useless; remove it. (I wonder if it was a mistake for something similar — void pop() const? constexpr void pop()? but neither of those makes sense either.)

T peek() {

OTOH, this method should be const:

T peek() const {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
    return std::as_const(head->data);
}

I threw in an as_const just to illustrate complete paranoia. We don't know what type T is, right? So when you construct the return value T, which constructor do you want to call — T(T&) or T(const T&)? Write a unit test for a type T where it makes a difference, and see what happens.

getSize(), isFull(), and isEmpty() should all be const methods as well.

void swap(stack& other) noexcept

Good! You also do the using std::swap; dance correctly — although, since you're not swapping anything but ints and pointers, the dance is unnecessary in this case, but hey it's good practice.

You did forget, though, that if you want the using std::swap; dance to work for anyone else who uses your stack class, you'll need to provide that free ADL function swap. So we add an inline friend:

friend void swap(stack& a, stack& b) noexcept {
    a.swap(b);
}

Now

using std::swap;
swap(redstack, bluestack);

will be as efficient as possible.

Consider adding move semantics to your class — stack(stack&&) noexcept, stack& operator=(stack&&) noexcept, void push(T&&) (or just void push(T) at that point). I assume you left them out on purpose for this simple example.

Your copyList is recursive. This could blow your stack if you're copying a very long list. You successfully eliminated the recursion from your destructor — why not eliminate it here too?

node* copyList(node* l)

Since this member function doesn't need the this pointer for anything, it should be marked static. And it wouldn't hurt to add const to the node you don't intend to modify, just for a tiny bit of self-documentation:

static node *copyList(const node *l)


Pearson Correlation in Haskell As an exercise to help me learn Haskell, I decided to write a small "program" to find the Pearson Correlation Coefficient for 2 lists of numbers.  I'm pretty unhappy with how it turned out, because I feel like the typing is a mess, and it is difficult to read.

I was hoping that someone with experience would help me to improve my code, and tell me how they would have approached the problem.

import Data.List

summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b
summation i n e = if (i < n)
                  then (e i + summation (i+1) n e)
                  else (e i)

mean :: (Real a, Fractional b) => [a] -> b
mean x = (1 / (genericLength x)) *
         (summation 1 (length x) (\i -> realToFrac (x !! (i-1))))

covariance :: (Real a, Fractional b) => [a] -> [a] -> b
covariance x y = (1 / (genericLength x)) *
                 (summation 1 (length x) (\i -> ((realToFrac (x !! (i-1)) - mean x) * (realToFrac (y !! (i-1)) - mean x))))

stddev :: (Real a, Floating b) => [a] -> b
stddev x = ((1 / (genericLength x)) *
             (summation 1 (length x) (\i -> (realToFrac (x !! (i-1)) - mean x) ** 2))) ** (1/2)

pearson :: (Real a, Floating b) => [a] -> [a] -> b
pearson x y = covariance x y / (stddev x * stddev y)

Each function on its own

Let us have a look at each of your functions first in solitude. What does summation do?

summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b
summation i n e = if (i < n)
                  then (e i + summation (i+1) n e)
                  else (e i)

Well, for all numbers from x in i to n, sum the e x. We can write this a lot more clear with a list comprehension:

summation :: (Enum n, Num a) => n -> n -> a
summation i n e = sum [e x | x <- [i..n]]

Note that this only holds if i is always lesser than n in the inital call.

Next, what does mean do?

mean :: (Real a, Fractional b) => [a] -> b
mean x = (1 / (genericLength x)) *
         (summation 1 (length x) (\i -> realToFrac (x !! (i-1))))

Uh, that looks complicated. First, let us rewrite it as proper fraction:

mean x = num / denom
  where
    num   = summation 1 (length x) (\i -> realToFrac (x !! (i-1)))
    denom = genericLength x

Much easier to read. So, what do you actually do in num? You calculate the sum of all numbers in x. However, this can be done with sum already. We end up with

mean :: Fractional a => [a] -> a
mean xs = sum xs / genericLength xs

Note that lists are usually named with a suffix s. One x, multiple xs.

We use the same approach on covariance. First, we rewrite it in simpler terms:

covariance x y = num / denom
  where
    num        = summation 1 (length x) elemwise
    denom      = genericLength x
    elemwise i = (realToFrac (x !! (i-1)) - mean x) * (realToFrac (y !! (i-1)) - mean x))

And now we immediately spot an error in elemwise. You wrote y !! (i-1) - mean x, but you meant y !! (i - 1) - mean y.

However, let us have a look at the mathematical definition again:

$$
cov(X,Y) = E\left[(X-E[X])*(Y-E[Y])\right]
$$

Allright. Let's write this exactly down as it stands there:

covariance x y = mean productXY
  where
   productXY = pairwiseProduct xSubMean ySubMean
   xSubMean  = subtractMean x
   ySubMean  = subtractMean y

This is obviously not ready yet. What are pairwiseProduct and subtractMean?

subtractMean :: Fractional a => [a] -> [a]
subtractMean xs = [x - mx | x <- xs]
  where
    mx = mean xs

pairwiseProduct :: Num a => [a] -> [a] -> [a]
pairwiseProduct xs ys = zipWith (*) xs ys

Now we're done. Note how the covariance almost looks like pseudo-code? It's clearly easy to read by a human. That's the most important point you should take from this review: make your code easy to read for yourself.

stddev xs is just sqrt (covariance xs xs), so you should probably use that:

-- sqrt needs Floating
stddev :: Floating a => [a] -> a
stddev xs = sqrt (covariance xs xs)

Everything at once

After we've finished our rewrite, it turns out you don't need summation at all. So what do we end up with?

mean :: Fractional a => [a] -> a
mean xs = sum xs / genericLength xs

covariance :: Fractional a => [a] -> [a] -> a
covariance xs ys = mean productXY
  where
   productXY = zipWith (*) [x - mx | x <- xs] [y - my | y <- ys]
   mx        = mean xs
   my        = mean ys

stddev :: Floating a => [a] -> a
stddev xs = sqrt (covariance xs xs)

pearson :: (Floating a) => [a] -> [a] -> a
pearson x y = covariance x y / (stddev x * stddev y)

Note that covariance got a lot easier to read due to bindings.

Please keep in mind that this implementation has some performance related issues. Especially the mean implementation is a poster child for a function that leaks memory, but for small lists you should be fine.

Working with lists

When you work with lists, avoid element-wise access. It's really slow. Instead, you want to transform the whole map into a single value (a fold, e.g. length or sum), or into another map (above with list comprehensions, e.g. [x - mx | x <- xs]).


Returning result and error status for number type conversions Looking for review of design strategy of using a struct to return the functional result and error status.  Your experience of how my design approach may succeeded or failed is especially welcomed.

In constructing a library of functions, I've tried various error handling approaches, none completely satisfactory and was about to embark on this 5th strategy. (1-4 below.) Identifying any pitfalls or referencing any existing like-designed specification is sought.

Return result as a struct bundled with the status.

Below is a small portion of a much larger conversion set of functions.  The style/correctness of the function bodies is primarily illustrative of how functions may construct the combined struct result.  In main(), one example use the returned structures value and status. The next just uses the value, showing a functional usage.

#include <errno.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  errno_t error;
  double retval;
} e_double_type;

typedef struct {
  errno_t error;
  unsigned retval;
} e_unsigned_type;

e_double_type string_to_double(const char *src) {
  char *endptr;
  errno = 0;
  e_double_type y = { 1, strtod(src, &endptr) };
  if (endptr == src) return y;
  if (errno && fabs(y.retval) > 1.0) return y;
  y.error = 0;
  return y;
}

e_unsigned_type longlong_to_unsigned(long long x) {
  e_unsigned_type y = { 1, 0 };
  if (x < 0) return y;
  if (x > UINT_MAX) {
    y.retval = UINT_MAX;
    return y;
  }
  y.retval = (unsigned) x;
  return y;
}

int main(void) {

  // Error status and value
  e_double_type y = string_to_double("123");
  printf("%d %le\n", y.error, y.retval);

  // Just value - status not of concern
  // e_unsigned_type variable not needed
  printf("%u\n", longlong_to_unsigned(123456789012345).retval +
     longlong_to_unsigned(12345).retval);

  return 0;
}

Typical other methods to receive a function result and error status include which I have tried.

Global errno:

errno = 0;
char *endptr;
long num = strtol(some_string, &endptr, 10);
if (errno) Handle_RangeError();

Return special value:

int ch = fgetc(stdin);
if (ch == EOF) Handle_Problem();

Pass address of error status and return result:

int status;
y = foo(x, &status);
if (status) Handle_fooFailure();

Pass address to store result and return error status:

FILE *stream;
errno_t status = fopen_s(&stream, filename, "r");
if (status) Handle_OpenFailure();

The above methods, except #2, fail to keep the result and status together.  #2 requires a wider return type that is often not available.  The program model of using a function, where the parameters are only the inputs, and the result is the output is very appealing.

I don't like the idea of using an all-in-one struct. You will have to do more maintenance: every time you create a function that returns different values, you have to create a new struct.

Further, I think the struct return value will confuse the user. Everyone is familiar with the basic types, so they will immediately know how to use a function just from it's signature. When you introduce non-opaque structs, the user also has to look up the documentation for that, on top of the documentation for the actual function.

Think about when a function has a multiple value result - you can't give meaningful names to the two members without creating a new struct for every function (even with the same types).

e_two_doubles_type ret = get_two_doubles();
// Was it ret.retval1 or ret.retval2 that I nedded?

My preferred way to signal status is to return a constant #defined in a header. For an example look at the API of SQLite. It's a library I've used in projects, and it has worked really well. I also use this pattern for my own code. The results of the functions are returned through pointer parameters. This strategy is simple and will feel intuitive to users since it's so common.

int sqlite3_open(
  const char *filename,   /* Database filename (UTF-8) */
  sqlite3 **ppDb          /* OUT: SQLite db handle */
);

The standard C library uses a "global variable" for error status. It is nowadays actually a macro, because globals simply aren't thread safe. If you want your API to be able to be used by multiple threads at the same time, global state is a no-no. There is no way to know which call generated the error code if you can't know the exact order of operations. I fear implementing your own errno as a thread-local macro will be more trouble than it's worth.

  Originally this was a static memory location, but macros are almost always used today to allow for multi-threading, such that each thread will see its own error number. (Wikipedia)

When re-reading your question I think you might have meant to use the actual errno global. This is feasible, but might surprise users. Normally, errno is only ever used by the standard library. I've seen one system implement their own version, but I don't see any advantages over returning the value directly.

The "return special value" approach can work in some cases. You need a value that is not a valid result, and must thus either artificially limit the domain of the function, or use a wider type than otherwise necessary. The obvious case is the NULL pointer, which is handy if there is only a single type of error, or if you don't need to know why the call failed.

"Pass address of error status" is similar to my proposed solution, it's just the other way around. The problem with this is that you can only return one value. There will only ever be one status, in contrast to results, so why not return the status instead?

You mention keeping status and result together. I don't agree with this goal, they are very different things and should be kept apart. The status is needed right after the call, but the result could live on for the rest of the program. Tightly coupling these will make continued use of the result awkward.

Consistency is key to making a great API. Make the user feel at home when using it, let their presumptions about your function's signatures be right. To achieve this, you need a consistent way to return status and results of functions. That's where "return status, reference results" shines, because it can be adapted to all situations - no matter how many results or of what types, the same basic principle is there.

When it comes to the status values themselves, you've pointed out two, and I've mentioned one approach above.

I don't like the idea of reusing standard errno values. Those values are specialised for system calls and most values probably won't be usable by your API. Here is a chart of values defined for several platforms. Note that different constants are available for different platforms. Imagine for instance that you want to use EMSGSIZE (Message too long). This would work fine for all platforms except for Microsoft's compiler (MSVC). Now you need to check for #ifdef _WIN32 and define it yourself. This is even more work than just coming up with your own suite of constants.

Extending the standard values is also bad. What if a platform you didn't think of has used this identifier already? Your library and this platform will be incompatible until you change it. Always try to avoid clashing with platforms, even if you don't think you want to support it today.

  Names beginning with a capital ‘E’ followed a digit or uppercase letter may be used for additional error code names. (GNU libc manual)

Further, errno values are not very readable. Their names are dense and hard to remember. I think EACCES is a great example, or rather a horrific one. They've intentionally misspelled "access" - that has thrown me off a couple of times.

Now we've ruled out that one, there are two left. You've decided to create your own constants, but should they be #defined enum-erated? I think both are good choices, but I'll go over the pros and cons of them below.

With macros, you have to specify each value by hand. This is both a strength and a weakness. It's dangerous because you can mistakenly #define two macros to the same value, without any compile time errors or warnings (I tried this with gcc -Wall). In effect, this bug can be hard to find.

#define LIB_OUT_OF_RANGE   86723
#define LIB_INVALID_STRING 86723

int status = string_to_double(str, &dbl);

if (status == LIB_OUT_OF_RANGE)
    fprintf(stderr, "Too large, try again\n");
else if (status == LIB_INVALID_STRING)
    fprintf(stderr, "Please input a number\n");

The second if-statement will never ever be executed, because LIB_OUT_OF_RANGE == LIB_INVALID_STRING. The compiler will probably even optimize the second if statement away.

The advantage is that you will always know what value a certain constant has, as opposed to enum constants. Try counting all prior constants to get the value in an enum with 50+ values.

Knowing the values is useful for debugging and logging: you can just print %d the values and check them against your header.

If you decide to go with enums, there are three different ways to do it. They are list below in order of transparency.

enum { ... };
int function();

enum lib_error { ... );
enum lib_error function();

typedef enum { ... } lib_error;
lib_error function();

I like to be upfront with what the user is getting. The enum/typedef is explicit with how values of them are to be interpreted, but not with the underlying type. I like to know what's an int and what's something else, but you might differ. I think any of these are fine.

In summary, use either macros or enums. Both are fine and each have their pros and cons.

PS. If you want to read up on a nifty way to pair integer constants with their string representation, check out this article on X Macros.