Javascript PriorityQueue based on object property I wrote this class which is a priority queue based on a numeric property of any object. As far as I can tell, the following code is working as intended. Are there any stylistic tendencies that I am getting wrong, or any gotchas I should look out for?

//Constants

PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;

/**
* This is an improved Priority Queue data type implementation that can be used to sort any object type.
* It uses a technique called a binary heap.
*
* For more on binary heaps see: http://en.wikipedia.org/wiki/Binary_heap
*
* @param criteria The criteria by which to sort the objects. This should be a property of the objects you're sorting.
* @param heapType either PriorityQueue.MAX_HEAP or PriorityQueue.MIN_HEAP.
**/
function PriorityQueue(criteria,heapType) {
    this.length = 0; //The current length of heap.
    var queue = [];
    var isMax = false;

    //Constructor
    if (heapType==PriorityQueue.MAX_HEAP) {
        isMax = true;
    } else if (heapType==PriorityQueue.MIN_HEAP) {
        isMax = false;
    } else {
        throw heapType + " not supported.";
    }

    /**
    * Inserts the value into the heap and sorts it.
    *
    * @param value The object to insert into the heap.
    **/
    this.insert = function(value) {
        if (!value.hasOwnProperty(criteria)) {
            throw "Cannot insert " + value + " because it does not have a property by the name of " + criteria + ".";
        }
        queue.push(value);
        length++;
        bubbleUp(length-1);
    }

    /**
    * Peeks at the highest priority element.
    *
    * @return the highest priority element
    **/
    this.getHighestPriorityElement = function() {
        return queue[0];
    }

    /**
    * Removes and returns the highest priority element from the queue.
    *
    * @return the highest priority element
    **/
    this.shiftHighestPriorityElement = function() {
        if (length < 0) {
            throw ("There are no more elements in your priority queue.");
        }
        var oldRoot = queue[0];
        var newRoot = _queue.pop();
        length--;
        queue[0] = newRoot;
        swapUntilQueueIsCorrect(0);
        return oldRoot;
    }

    var bubbleUp = function(index) {
        if (index==0) {
            return;
        }
        var parent = getParentOf(index);
        if (evaluate(index,parent)) {
            swap(index,parent);
            bubbleUp(parent);
        } else {
            return;
        }
    }

    var swapUntilQueueIsCorrect = function(value) {
        left = getLeftOf(value);
        right = getRightOf(value);
        if (evaluate(left,value)) {
            swap(value,left);
            swapUntilQueueIsCorrect(left);
        } else if (evaluate(right,value)) {
            swap(value,right);
            swapUntilQueueIsCorrect(right);
        } else if (value==0) {
            return;
        } else {
            swapUntilQueueIsCorrect(0);
        }
    }

    var swap = function(self,target) {
        var placeHolder = queue[self];
        queue[self] = queue[target];
        queue[target] = placeHolder;
    }

    /*
    /*Helpers
    */
    var evaluate = function(self,target) {
        if (queue[target]==null||queue[self]==null) {
            return false;
        }
        if (isMax) {
            if (queue[self][criteria] > queue[target][criteria]) {
                return true;
            } else {
                return false;
            }
        } else {
            if (queue[self][criteria] < queue[target][criteria]) {
                return true;
            } else {
                return false;
            }
        }
    }

    var getParentOf = function(index) {
        return Math.floor(index/2)-1;
    }

    var getLeftOf = function(index) {
        return index*2 + 1;
    }

    var getRightOf = function(index) {
        return index*2 + 2;
    }
}

You're off to a great start. +1 for providing comments.

Here are some tips:

1) Define variables before modifying them.

So the constants MAX_HEAP and MIN_HEAP should be defined after PriorityQueue.

Old Code:

PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;

function PriorityQueue(criteria, heapType) {
    //...
}

New Code:

function PriorityQueue(criteria, heapType) {
    //...
}
PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;

Side note: In shiftHighestPriorityElement(), _queue isn't defined. I think it should be queue.

2) Use this to attach attributes to a Constructor.

More info

Example:
Old Code:

//..
function PriorityQueue(criteria, heapType) {
    this.length = 0;
    var queue = [];
    var isMax = false;
    //...

New Code:

//..
function PriorityQueue(criteria, heapType) {
    this.length = 0;
    this.queue = [];
    this.isMax = false;
//...

3) Split up functions longer than 8 - 12 lines of code into smaller functions.

Use the prototype on an object to attach functions to the constructor instead of including all the functionality within.

Old Code:

function PriorityQueue(criteria, heapType) {
    //...
    this.insert = function (value) {
        if (!value.hasOwnProperty(criteria)) {
            throw "Cannot insert " + value + " because it does not have a property by the name of " + criteria + ".";
        }
        queue.push(value);
        length++;
        bubbleUp(length - 1);
    }
    //...
    var swap = function (self, target) {
        var placeHolder = queue[self];
        queue[self] = queue[target];
        queue[target] = placeHolder;
    }
    //...
}

New Code:

function PriorityQueue(criteria, heapType) {
//...
}
PriorityQueue.prototype.insert = function (value) {
    if (!value.hasOwnProperty(this.criteria)) {
        throw "Cannot insert " + value + " because it does not have a property by the name of " + this.criteria + ".";
    }
    this.queue.push(value);
    this.length++;
    this.bubbleUp(this.length - 1);
}
PriorityQueue.prototype.swap = function (self, target) {
    var placeHolder = this.queue[self];
    this.queue[self] = this.queue[target];
    this.queue[target] = placeHolder;
}

4) Sometimes it's better to just return an boolean expression.

Old Code:

if (queue[self][criteria] < queue[target][criteria]) {
    return true;
} else {
    return false;
}

New Code:

return (queue[self][criteria] < queue[target][criteria]);

5) Make sure to create test units.

Try out qunit.js

6) Simplify if and else conditions.

Old Code:

var isMax = false;

//Constructor
if (heapType==PriorityQueue.MAX_HEAP) {
    isMax = true;
} else if (heapType==PriorityQueue.MIN_HEAP) {
    isMax = false;
} else {
    throw heapType + " not supported.";
}

New Code:

this.isMax = !!heapType;
if ( heapType !== 0 || heapType !== 1 ){
    throw heapType + " not supported.";
}

7) Use === instead of == when comparing for value and type of primitive values.

Old code:

} else if (value == 0) {

New Code:

} else if (value === 0) {

Or

} else if (!value) {

Final code:

function PriorityQueue(criteria, heapType) {
    this.criteria = criteria;
    this.length = 0;
    this.queue = [];
    this.isMax = !!heapType;
    if ( heapType !== 0 || heapType !== 1 ){
        throw heapType + " not supported.";
    }
}
PriorityQueue.prototype.insert = function (value) {
    if (!value.hasOwnProperty(this.criteria)) {
        throw "Cannot insert " + value + " because it does not have a property by the name of " + this.criteria + ".";
    }
    this.queue.push(value);
    this.length++;
    this.bubbleUp(this.length - 1);
};
PriorityQueue.prototype.getHighestPriorityElement = function () {
    return this.queue[0];
};
PriorityQueue.prototype.shiftHighestPriorityElement = function () {
    if (length < 0) {
        throw("There are no more elements in your priority queue.");
    }
    var oldRoot = this.queue[0];
    var newRoot = this.queue.pop();
    this.length--;
    this.queue[0] = newRoot;
    this.swapUntilQueueIsCorrect(0);
    return oldRoot;
};
PriorityQueue.prototype.bubbleUp = function (index) {
    if (index === 0) {
        return;
    }
    var parent = this.getParentOf(index);
    if (this.evaluate(index, parent)) {
        this.swap(index, parent);
        this.bubbleUp(parent);
    } else {
        return;
    }
};
PriorityQueue.prototype.swapUntilQueueIsCorrect = function (value) {
    var left = this.getLeftOf(value),
        right = this.getRightOf(value);

    if (this.evaluate(left, value)) {
        this.swap(value, left);
        this.swapUntilQueueIsCorrect(left);
    } else if (this.evaluate(right, value)) {
        this.swap(value, right);
        this.swapUntilQueueIsCorrect(right);
    } else if (value === 0) {
        return;
    } else {
        this.swapUntilQueueIsCorrect(0);
    }
};
PriorityQueue.prototype.swap = function (self, target) {
    var placeHolder = this.queue[self];
    this.queue[self] = this.queue[target];
    this.queue[target] = placeHolder;
};
PriorityQueue.prototype.evaluate = function (self, target) {
    if (this.queue[target] === null || this.queue[self] === null) {
        return false;
    }
    if (this.isMax) {
        return (this.queue[self][this.criteria] > this.queue[target][this.criteria]);
    } else {
        return (this.queue[self][this.criteria] < this.queue[target][this.criteria]);
    }
};
PriorityQueue.prototype.getParentOf = function (index) {
    return Math.floor(index / 2) - 1;
};
PriorityQueue.prototype.getLeftOf = function (index) {
    return index * 2 + 1;
};
PriorityQueue.prototype.getRightOf = function (index) {
    return index * 2 + 2;
};
PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;


Adder method of a binary calculator This is the adder method of my binary calculator. I did not cover for the case that someone passes a non binary number into the calculator yet.

I am pretty sure I have covered every other edge case for the calculator. I am trying to learn refactoring and how to look for simpler ways to do things. I know that I have a bunch of if's, but I don't know any other way I could have made the logic for this. Could someone mentor me through how they would refactor my code and why?

class BinaryCalculator:

    def bit_adder(self, number1, number2):
        num_a = self.num_to_list(number1)
        num_b = self.num_to_list(number2)
        maxx = max(len(num_a), len(num_b))
        minn = min(len(num_a), len(num_b))

        if minn == len(num_b):
            smaller = num_b
            num_b = [0] * (maxx - minn)
            for i in smaller:
                num_b.append(i)
        else:
            smaller = num_a
            num_a = [0] * (maxx - minn)
            for i in smaller:
                num_a.append(i)

        print " ",''.join(map(str, num_a))
        print "+",''.join(map(str, num_b))
        print '----------'
        carry_bit = 0
        answer = [0] * (maxx + 1)

        for bit in xrange(maxx - 1, -1, -1):
            sum_bit = 0
            if num_a[bit] == num_b[bit]:
                if num_a[bit] == 1:
                    if carry_bit == 0:
                        carry_bit += 1
                    else:
                        sum_bit = 1
                else:
                    if carry_bit == 1:
                        sum_bit = 1
                        carry_bit -= 1

            else:
                if carry_bit == 1:
                    sum_bit == 0
                else:
                    sum_bit = 1
            answer[bit + 1] = sum_bit

        if carry_bit == 1:
            answer[0] = 1

        print ''.join(map(str, answer))

    def num_to_list(self, num):
        num = str(num)
        list_to_return = []
        for bit in range(len(num)):
            list_to_return.append(int(num[bit]))
        return list_to_return

c = BinaryCalculator()

c.bit_adder(10011001, 1001)

There are some issues with your code concerning the code design.

Why do you use a class for your BinaryCalculator? You don't have multiple instances of the class, you do not even give the class a meaningful constructor. This task should not be solved with OOP, but just with regular functions.

You can easily drop the class and define the two functions as top level functions, e.g:

def num_to_list(num):
    ..... your code goes here ...

def bit_adder(a, b):
    ..... your bit adder goes here ....

if __name__ == '__main__':
    res = bit_adder(111101, 1011)
    print(res)

Second, you can reduce your code significantly with some utility functions, e.g for your num_to_list function:

def num_to_list(x):
    return [int(n) for n in reversed(str(x))]

Third, for your bit_adder the function zip_longest from the package itertools comes in handy. This just zips two lists like a regular zip, but fills up the shorter list with default values.

That's why I reversed the bit order in the num_to_list function earlier.

With this function you can reduce your bit_adder to a more compact version:

# zip the two revered bit lists with a default fillvalue of 0
z = itertools.zip_longest(a, b, fillvalue=0)
# add each bit, this results of a list that could look like [1, 0, 2, 1]
added = [n + k for n, k in z]

# we still have to get rid of the two's, so we iterate through the list
# and take care of the overflows, similarly to your approach
carry = 0
for n, v in enumerate(added):
    if v != 2 and carry == 0:
        continue
    elif v == 0 and carry == 1:
        added[n] = v + carry
        carry = 0
    else:
        added[n] = 0
        carry = 1

if carry == 1:
    added.append(carry)

The main advantage of this version, is that you don't have to care about the
smaller or bigger number.


High order functions on Array.prototype In order to better understand functional programming in Javascript, I thought I'd try to recreate (as well as extend) some of the higher order functions on the Array object. These methods don't intend to be identical but to have the basic functionality. Any tips/suggestions/feedback would be greatly appreciated!

// Array.prototype.map()
Array.prototype.newMap = function(fn) {
    var returnedArray = [];

    for (var i = 0; i < this.length; i++) {
        returnedArray[i] = fn(this[i]);
    }
    return returnedArray;
};

// newMap for multi-dimensional arrays
Array.prototype.newMapMulti = function(fn) {
    var mainArray = [];

    for (var i = 0; i < this.length; i ++) {
        var result = this[i].newMap(fn);
        mainArray.push(result);
    }
    return mainArray;
};

// Array.prototype.filter()
Array.prototype.newFilter = function(fn) {
    var returnedArray = [];

    for (var i = 0; i < this.length; i++) {
        var c = this[i];

        if (fn(c)) {
            returnedArray.push(c);
        }
    }
    return returnedArray;
};
// newFilter for multi-dimensional arrays
Array.prototype.newFilterMulti = function(fn) {
    var mainArray = [];

    for (var i = 0; i < this.length; i++) {
        var result = this[i].newFilter(fn);
        if (result.length === 0) { continue }
        mainArray.push(result);
    }
    return mainArray;
};

// Array.prototype.find()
Array.prototype.newFind = function(fn) {

    for (var i = 0; i < this.length; i++) {
        var c = this[i];

        if (fn(c)) {
            return c;
        }
    }
};

// Array.prototype.reduce()
Array.prototype.newReduce = function(fn) {
    var total = 0;

    for (var i = 0; i < this.length; i++) {
        total += fn(this[i]);
    }
    return total;

};

// newReduce for multi-dimensional arrays
Array.prototype.newReduceMulti = function(fn) {
    var total = 0;

    for (var i = 0; i < this.length; i++) {
        total += this[i].newReduce(fn);
    }
    return total;
};

// returns a reduce value. if fn1 returns a value < x, then apply fn2 and return that value
Array.prototype.newReduceIf = function(fn1, fn2, x) {
    var reduceResult = this.newReduce(fn1);

    if (reduceResult < x) {
        var secondResult = this.newReduce(fn2);
        return secondResult;
    }
    return reduceResult;
};

First, it's not recommended to extend native objects. That's because modifying the prototype applies to all instances. Now let's say the spec added a newMap method that acted differently from your implementation. Code that uses newMap according to spec (like third party code) will break because your code overrides the native implementation and operates in a totally different way.

That's one reason why libraries like lodash and underscore don't extend native objects, and just accept the array/object as an argument. They also provide "wrapping" mechanisms, accepting an array and wrapping it in a container object with its own prototype methods. That way, they safely add methods without modifying native objects while keeping it looking like they extend.

// In lodash, the _ function wraps the array in a "lodash object" which
// has methods like map etc.
var newValues = _([1,2,3]).map(v => v * 3).value(); // [3,6,9]

// In jQuery, the $ function wraps the element in a "jQuery object" which
// has its own DOM manipulation methods.
$(document.getElementById('myElement')).remove();

Now let's say you didn't extend it via native objects.

newFilterMulti isn't really a true multi-dimensional array filter. It only appears to go 2 levels deep (2D). Either you make it a true multi-dimensional filter (going as deep as it can) or rename it so it's more apparent that it only goes 2 levels deep.

newReduce doesn't act the same way native reduce works (and this is a good example of spec-breaking implementation). reduce doesn't add return values. It carries over the last result to the next call regardless of type. This means the callback accepts 2 values, the carry and the current value. Also, most reduce implementations accept an initial argument for the carry value. If omited, reduce starts at the second element in the array, with the first element as carry.

Again, newReduceMulti isn't a true multi-dimensional reduce, just 2D. Re-implement or rename accordingly.

Now one technique used by most libraries is to reuse the operations that have already been defined. In the case of jQuery, internally it makes heavy use of its $.each. So if they need anything looped through, instead of tediously writing for loops everywhere, they use their $.each. Also, I heard FP operations rely heavily on map.

So if you could make a solid forEach and map implementation, you can readily reuse them in your other methods instead of writing a for loop every time.


Calculating distance and time between waypoints for large files This is very similar to other code I've posted, however this is designed for very large CSV files, for example 35GB.

The files typically look like this:

9e77d54918dd25c3f9d2e5354ec86666,0,2015-10-01T14:14:15.000Z,45.0988,7.5811,,
9e77d54918dd25c3f9d2e5354ec86666,1,2015-10-01T14:17:15.000Z,45.0967,7.5793,,
9e77d54918dd25c3f9d2e5354ec86666,2,2015-10-01T14:20:15.000Z,45.1012,7.6144,,
9e77d54918dd25c3f9d2e5354ec86666,3,2015-10-01T14:23:15.000Z,45.0883,7.6479,,
9e77d54918dd25c3f9d2e5354ec86666,4,2015-10-01T14:26:15.000Z,45.0774,7.6444,,
9e77d5jhg35hg345hghge5354ec84751,0,2015-10-04T22:36:32.000Z,48.0723,7.6442,,
ect...

The code I've written works out the sum of the distance between each of the waypoints, as well as the time taken and total number of waypoints. Here it is in entirety:

import pandas as pd
import numpy as np

EarthRadius = 6371 #km

def distance(group): #calculate distances using Equirectangular approximation
    lat = np.radians(group.Lat)
    lon = np.radians(group.Lon)
    endLon = lon.shift(-1)
    endLat = lat.shift(-1)
    x = (endLon - lon) * np.cos(0.5 * (endLat + lat))
    y = endLat - lat
    D = EarthRadius * np.sqrt(x**2 + y**2)
    return D.sum()

def timedelt(group):  #calculate length of trip
    a = np.around((pd.to_datetime(group['Date']).max() - pd.to_datetime(group['Date']).min()).seconds/60, decimals=2)
    return a

def tripStatistics(trip):#Helper function to output distance and number of waypoints
    return pd.Series({"TripID":chunk.iloc[0,0],"Distance": distance(trip),"No. of Waypoints": len(trip),"Time Taken(Mins)": timedelt(trip)})

def iterateIDs(file): #create chunks based on tripID
    csv_reader = pd.read_csv(file, iterator=True, chunksize=1, header=None, usecols=[0, 2, 3, 4],names=['TripID', 'Date', 'Lat', 'Lon'])
    first_chunk = csv_reader.get_chunk()
    id = first_chunk.iloc[0,0]
    chunk = pd.DataFrame(first_chunk)
    for l in csv_reader:
        if id == l.iloc[0,0]:
            id = l.iloc[0,0]
            chunk = chunk.append(l)
            continue
        id = l.iloc[0,0]
        yield chunk
        chunk = pd.DataFrame(l)
    yield chunk

output = pd.DataFrame(columns=['TripID','Distance','No. of Waypoints','Time Taken(Mins)'])
chunkIterate = iterateIDs("TripRecordsReportWaypoints.csv")

for chunk in chunkIterate:
    temp = tripStatistics(chunk)
    output = output.append(temp, ignore_index=True)

output['Waypoint Frequency(Secs)'] = np.around(60*output['Time Taken(Mins)']/output['No. of Waypoints'], decimals=2)
output.reset_index().to_csv('TripDetails.csv', sep=',', index=False)

I'm wondering if there is anything in my code that might slow down processing speeds. I set it running on the previously mentioned 35GB file and it's been going for over 24 hours now. It's the first time I've used generators so I hope I've not made some simple error.

As a bit of a comparison, I had written a previous piece of code that is similar but without splitting the CSV file into chunks with the iterateIDs generator function. It processed a 200MB file in 100 seconds. A linear extrapolation of that would mean it would take only 3 hours to process a 35GB file.

This line looks like trouble:

        chunk = chunk.append(l)

The docs say it will "append rows of other to the end of this frame, returning a new object." If the new object were to be small, containing a reference to the old object, then you would win, but here I think we're looking at quadratic copying behavior. Consider using .concat() instead, with copy=False. Or perhaps you can preallocate. Verify that the columns of l always match those of the existing chunk.

I recommend adding periodic progress reports that mention throughput and chunk size, to see where performance falls off a cliff. Do a timing run with the call to output.append commented out. Verifying that expected group sizes are passed into distance() would be helpful, too.  And definitely use cProfile, as Graipher suggests.


Unit test for a function that transforms a PANDAS dataframe I am currently working on a project that uses many dataframe wrangling. The intention is to write test to check that the output functions are correct.

I have written a test for a dataframe function that transforms a dataframe of operations into another dataframe that contains the volumen of the operations for each of the containing days.

My question is:

Is this a good test for a function that receives a DataFrame and returns a DataFrame?

Should I do something different?

This is is my code:

import pandas as pd

class Operations:

    def disaggregate_ops_volume_date(self, df: DataFrame):
        """ Given a DataFrame with operations it generates an operation for each of the days it contains """

        if df.empty:
            return df

        ops = df.copy()

        ops['NDAYS'] = ops[['SEQ_PERIODSTART', 'SEQ_PERIODEND']].apply(
            lambda row: (row['SEQ_PERIODEND'] - row['SEQ_PERIODSTART']).days, axis=1)

        # Add a copy of each operation NDAYS times
        ops = ops.loc[np.repeat(ops.index, ops['NDAYS'])]

        # Correct the date based on the TradeId operation
        ops['SEQ_PERIODSTART'] += pd.to_timedelta(ops.groupby('TRADEID').cumcount(), unit='d')
        ops['SEQ_PERIODEND'] = ops['SEQ_PERIODSTART'] + pd.Timedelta(1, unit='d')

        ops = ops.reset_index(drop=True)

        return ops

This is the test I have developed:

from pandas.util.testing import assert_frame_equal
import unittest
import pandas as pd

class TestOperations(unittest.TestCase):

    def test_minimal(self):
        """To make sure at least a test is passed"""
        self.assertEqual('foo'.upper(), 'FOO')

    def test_disaggregate_ops_volume_date(self):
        input = pd.DataFrame(
            {'SEQ_PERIODSTART':
               ['2019-02-10', '2019-02-12', '2019-02-13'],
             'SEQ_PERIODEND':
               ['2019-02-11', '2019-02-14', '2019-02-18'],
             'ID': [0, 1, 2]})

        input['SEQ_PERIODSTART'] = pd.to_datetime(input['SEQ_PERIODSTART'])
        input['SEQ_PERIODEND'] = pd.to_datetime(input['SEQ_PERIODEND'])

        expected = pd.DataFrame(
            {'SEQ_PERIODSTART':
                 ['2019-02-10', '2019-02-12',                                                           '2019-02-13', '2019-02-13',                                              '2019-02-14', '2019-02-15',                                             '2019-02-16', '2019-02-17'],

              'SEQ_PERIODEND':
                  ['2019-02-11',  '2019-02-13',
                  '2019-02-14', '2019-02-14',                                               '2019-02-15', '2019-02-16',                                          '2019-02-17', '2019-02-18'],
               'ID': [0, 1, 2, 3, 4, 5, 6, 7],
               'NDAYS': [1, 2, 2, 5, 5, 5, 5, 5]
                               })
        expected['SEQ_PERIODSTART'] = pd.to_datetime(expected['SEQ_PERIODSTART'])
        expected['SEQ_PERIODEND'] = pd.to_datetime(expected['SEQ_PERIODEND'])

        myops = Operations()

        assert_frame_equal(expected, myops.disaggregate_ops_volume_date(input))

if __name__ == '__main__':
    unittest.main()

The test itself seems okay.

bug

You use "ID" as columns name in the test, but "TRADEID" in the method to test.

And the result is not what was expected. The TRADEIDs don't match

Classes

There is no use for the class Operations. If you want to group functions that belong together, you can do so in a module (file) and import that. The fact disaggregate_ops_volume_date has a self parameter that is unused is a giveaway here

Vectorize

there is no reason to calculate ops['NDAYS'] row per row via apply. (df["SEQ_PERIODEND"] - df["SEQ_PERIODSTART"]).dt.days works just as well.

Then you can use DataFrame.assign, and don't have to explicitly make a copy of df

ndays = (df["SEQ_PERIODEND"] - df["SEQ_PERIODSTART"]).dt.days
ops = df.assign(NDAYS = ndays)

Day

Since a days is used a lot in that method, it can be clearer to define that up front:

DAY = pd.Timedelta("1d")

ndays can then be defined as ndays = (df["SEQ_PERIODEND"] - df["SEQ_PERIODSTART"]) // DAY. Whether this is clearer than the .dt.days is a matter of taste.

correcting the date can then be expessed more clearly as:

ops["SEQ_PERIODSTART"] += ops.groupby("TRADEID").cumcount() * DAY
ops["SEQ_PERIODEND"] = ops["SEQ_PERIODSTART"] + DAY

input

input is a builtin. By using that name as a variable name, you shadow that builtin. In this case this is not a big problem, but in general you should avoid this

indentation style

You use a very inconsistent style of indenting the code, and what goes on a separate line. Better would be to remain consistent. For this, I use black.

This changes:

expected = pd.DataFrame(
    {'SEQ_PERIODSTART':
         ['2019-02-10', '2019-02-12',                                                           '2019-02-13', '2019-02-13',                                              '2019-02-14', '2019-02-15',                                             '2019-02-16', '2019-02-17'],

      'SEQ_PERIODEND':
          ['2019-02-11',  '2019-02-13',
          '2019-02-14', '2019-02-14',                                               '2019-02-15', '2019-02-16',                                          '2019-02-17', '2019-02-18'],
       'ID': [0, 1, 2, 3, 4, 5, 6, 7],
       'NDAYS': [1, 2, 2, 5, 5, 5, 5, 5]
                       })

to:

expected = pd.DataFrame(
    {
        "SEQ_PERIODSTART": [
            "2019-02-10",
            "2019-02-12",
            "2019-02-13",
            "2019-02-13",
            "2019-02-14",
            "2019-02-15",
            "2019-02-16",
            "2019-02-17",
        ],
        "SEQ_PERIODEND": [
            "2019-02-11",
            "2019-02-13",
            "2019-02-14",
            "2019-02-14",
            "2019-02-15",
            "2019-02-16",
            "2019-02-17",
            "2019-02-18",
        ],
        "ID": [0, 1, 2, 3, 4, 5, 6, 7],
        "NDAYS": [1, 2, 2, 5, 5, 5, 5, 5],
    }
)

Which I think, is a lot more clear

pd.to_datetime

You can invoke this immediately on a list, so defining the input DataFrame can become:

input_df = pd.DataFrame(
    {
        "SEQ_PERIODSTART": pd.to_datetime(
            ["2019-02-10", "2019-02-12", "2019-02-13"]
        ),
        "SEQ_PERIODEND": pd.to_datetime(
            ["2019-02-11", "2019-02-14", "2019-02-18"]
        ),
        "ID": [0, 1, 2],
    }
)

defining test DataFrames

Instead of invoking pd.DataFrame immediately, an alternative is working via a csv-like text input, and then use pd.read_csv and StringIO to convert it to a DataFrame.

expected_str = """
SEQ_PERIODSTART  SEQ_PERIODEND  TRADEID  NDAYS
2019-02-10       2019-02-11     0        1
2019-02-12       2019-02-13     1        2
2019-02-13       2019-02-14     2        2
2019-02-13       2019-02-14     3        5
2019-02-14       2019-02-15     4        5
2019-02-15       2019-02-16     5        5
2019-02-16       2019-02-17     6        5
2019-02-17       2019-02-18     7        5"""
expected = pd.read_csv(
    StringIO(expected_str),
    sep="\s+",
    parse_dates=["SEQ_PERIODSTART", "SEQ_PERIODEND"],
)

Whether this is more clear than using pd.DataFrame() is a matter of taste. The advantage of this method is that it is easy to add or remove a line, and see whether the data is aligned correctly.


Query String Serializer I have a ASP.NET Web Forms project, and I want to build calls to .aspx pages in a strongly-typed fashion. I ended up rolling my own serializer that takes simple structs and saves them to/loads them from the query string. What do you think? Is my approach sane? Is there an accepted alternative I don't know about? Any feedback on the code?

Here's what building a call to a particular page looks like:

var fooParams= new FooPage.Parameters
{
    NodeID = nodeId,
    FooString = "the foo string"
};
string url = MyHelper.BuildCall(FooPage.URL, fooParams);
//url: ~/dir/FooPage.aspx?NodeID=5&FooString=the%20foo%20string

FooPage:

public partial class FooPage : System.Web.UI.Page
{
    public const string URL = "~/Dir/FooPage.aspx";
    public struct Parameters
    {
        public long? NodeID;
        public string FooString;
        public int? OtherParam;
    }

    protected Parameters Params;

    protected void Page_Load(object sender, EventArgs e)
    {
        Params = MyHelper.DeserializeFromNameValueCollection<Parameters>(Request.Params);

        //...
        //use Params.NodeID, Params.FooString, etc..
    }
}

Serialize/Deserialize to/from NameValueCollection:

public static void SerializeToNameValueCollection<T>(NameValueCollection nameValueCollection, T @object) where T : struct
{
    Type type = typeof(T);

    var fields = type.GetFields();
    foreach (var field in fields)
    {
        string key = field.Name;
        var value = field.GetValue(@object);

        if (value != null)
            nameValueCollection.Add(key, value.ToString());
    }
}

public static T DeserializeFromNameValueCollection<T>(NameValueCollection nameValueCollection) where T : struct
{
    T result = new T();

    Type type = typeof(T);

    var fields = type.GetFields();

    foreach (var field in fields)
    {
        string key = field.Name;

        string stringValue = nameValueCollection[key];
        if (stringValue != null)
        {
            object value;

            var baseType = Nullable.GetUnderlyingType(field.FieldType);
            if (baseType != null)
            {
                value = Convert.ChangeType(stringValue, baseType);
            }
            else
            {
                value = Convert.ChangeType(stringValue, field.FieldType);
            }

            field.SetValueDirect(__makeref(result), value);
        }
    }

    return result;
}

Format NameValueCollection into query string:

public static string BuildCall<T>(string url, T queryStringParams) where T : struct
{
    var queryStringBuilder = HttpUtility.ParseQueryString("");

    UrlHelper.SerializeToNameValueCollection(queryStringBuilder, queryStringParams);

    string queryString = queryStringBuilder.ToString();

    return url + "?" + queryString;
}

One of my favorite patterns for handling URL parameters in WebForms is the WebNavigator - http://polymorphicpodcast.com/shows/webnavigator/

If you're going through these kinds of Strongly-typed interactions for passing parameters between pages, maybe it is time you check out ASP .NET MVC - your solution looks a lot like model-binding.


Decomposing a number as a sum of two products using tree recursion Below is the problem taken from page6 here.

  The TAs want to print handouts for their students. However, for some unfathomable reason, both the printers are broken; the first printer only prints multiples of n1, and the second printer only prints multiples of n2. Help the TAs figure out whether or not it is possible to print an exact number of handouts! First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

def has_sum(sum, n1, n2):
"""
>>> has_sum(1, 3, 5)
False
>>> has_sum(5, 3, 5) # 1(5) + 0(3) = 5
True
>>> has_sum(11, 3, 5) # 2(3) + 1(5) = 11
True
"""

Solution

I think there is no mathematical solution except bruteforce recursion.

def f(sum, n1, n2):
    """
    >>> f(1, 3, 5)
    False
    >>> f(5, 3, 5) # 1(5) + 0(3) = 5
    True
    >>> f(11, 3, 5) # 2(3) + 1(5) = 11
    True
    >>> f(189, 4, 9)
    True
    """
    memoiz = []
    value = []
    def has_sum(sum, n1, n2, x=0, y=0):
        if x == 0 and y == 0:
            value.append(n1)
            value.append(n2)   #execute once to reuse tup
        if (n1 + n2)  == sum:
            return True
        if (memoiz) and ((n1 + n2)  > sum): # inefficient base case, need to improve using math
            return False
        result1 = False
        result2 = False
        if (x+1, y) not in memoiz:
            memoiz.append((x+1, y)) #memoiz
            result1 = has_sum(sum, (x+1)*value[0], y*value[1], x+1, y)
        if (x, y+1) not in memoiz:
            memoiz.append((x, y+1)) #memoiz
            result2 = has_sum(sum, x*value[0], (y+1)*value[1], x, y+1)
        return result1 or result2
    return has_sum(sum, n1, n2)

Can we improve the base case that returns False?

First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

You haven't included an implementation without a helper function.
You implemented memoization, which was not part of the description.
In any case, memoization won't be possible without a helper function or annotations.

Code review

There are several problems with your implementation:

memoiz shouldn't be a list, but a set
The value variable is confusing: it merely stores the original values of n1 and n2, you could simply save those values before calling the helper function
sum is a poor name for a variable, because it shadows the built-in named "sum"
There should be spaces around operators to improve readability, for example instead of (x+1)*value[0] it should be (x + 1) * value[0]
Instead of multiplying value[0] and value[1], it would be better to accumulate a sum
If result1 is True, there's no need to evaluate result2

With the above tips, the solution can be simplified a bit and become more efficient:

memoiz = set()
def has_sum(sum, n1, n2, x=0, y=0):
    if n1 + n2 == sum:
        return True
    if n1 + n2 > sum:
        return False
    if (x+1, y) not in memoiz:
        memoiz.add((x+1, y))
        result1 = has_sum(sum, n1 + orig_n1, n2, x+1, y)
        if result1:
            return True
    if (x, y+1) not in memoiz:
        memoiz.add((x, y+1))
        return has_sum(sum, n1, n2 + orig_n2, x, y+1)
    return False
orig_n1, orig_n2 = n1, n2
return has_sum(sum, 0, 0)

An alternative solution

Consider this alternative algorithm:

If target is 0, then we can reach it by 0 times n1 and n2
If target is below 0, then we cannot reach it
If target can be reached by a sum of multiples of n1 and n2,
then target - n1 or target - n2 must be reachable too

Implementation using memoization:

memoize = { 0: True }
def helper(target):
    if target not in memoize:
        if target < 0:
            memoize[target] = False
        else:
            memoize[target] = helper(target - n1) or helper(target - n2)
    return memoize[target]
return helper(target)

Iterative solution

At first I overlooked your requirement of a recursive solution.
For the record, this was my original suggestion using iterative logic.

Unless I'm missing something,
you can solve this using a much simpler algorithm:

If a solution exists, then sum == n1 * A + n2 * B where A and B are integers
Loop from A = 0 to sum, by steps of n1
If sum - A is divisible by n2, then a solution exists
If the end of the loop is reached, then a solution doesn't exist

That is:

for A in range(0, sum + 1, n1):
    if (sum - A) % n2 == 0:
        return True
return False


Finding the largest repeating substring Here's my code that takes a large string, and searches for the longest reoccurring substring. It compares the first letter with every other until it finds a match, then saves it. Then it compares the first 2 letters with every other until it finds a match then saves it. Then 3, 4, etc... Then it comes back around and starts with the second letter and checks the first letter, then the first 2, then the first 3, etc.

I plan on using this on text files as large as a novel. The time complexity is horrendous. I think it's O(n# of characters in the text file). Is there any other way to approach this?

def largest_substring(string):

    length = 0
    x=0
    y=0

    for y in range(len(string)):
        for x in range(len(string)):
            substring = string[y:x]
            if len(list(re.finditer(re.escape(substring),string))) > 1  and len(substring) > length:
                match = substring
                length = len(substring)
    return match

I guess a prefix tree might help.

Build a parallel array of pointers (sorry for a C-speak) into an original text.
Sort it.
Scan it for a longest match in two consecutive entries.

Overall complexity is \$O(ns)\$

Where \$n\$ is the length of the text and \$s\$ is the length of the longest recurring substring.


Performing API calls from a mobile client, reauthorizing the session if necessary I'm working on mobile app which doing requests to a server's API. I want to develop module that doing following:

get authorization key already exists in previous session
connect to server api and read server StatusLine answer code
if answer code is 403 then try to re authorize
when authorization is passed process server answer body

I implement this with state-machine:

enum ConnectionState {
    checkAnswer, reAuth, processLinks, endProcess
}

And made process in while-loop:

        int authCount = 0;
        HttpResponse httpResponse = null;
        ConnectionState state = ConnectionState.checkAnswer;
        boolean processConnect = true;
        while (processConnect) {
            switch (state) {
                case checkAnswer:
                    httpResponse = client.execute(httpGet);
                    final int serverAnswer = httpResponse.getStatusLine().getStatusCode();
                    if (403 == serverAnswer) {
                        state = ConnectionState.reAuth;
                    } else {
                        state = ConnectionState.processLinks;
                    }
                    break;
                case reAuth:
                    if (++authCount > MAX_AUTH_ATTEMPTS) {
                        state = ConnectionState.endProcess;
                        break;
                    }
                    auth.invalidateAuth();
                    if (!auth.doAuth()) {
                        Utils.log("could not authorize api");
                    } else {
                        state = ConnectionState.checkAnswer;
                    }
                    break;
                case processLinks:
                    if (null == httpResponse)
                        throw new RuntimeException("HttpResponse is null");
                    processLinks(httpResponse, imgLinks);
                    state = ConnectionState.endProcess;
                    break;
                case endProcess:
                    processConnect = false;
                    break;
                default:
                    throw new RuntimeException("Finded impossible state: " + state.toString());
            }
        }

What do you think about such code organization for this task? How to write it more elegantly?

I agree with Ibalazscs that StatePattern makes sense - using a switch to drive changes in behavior is a code smell.

Given that this state machine has only one end state, you could ditch the processConnect boolean, and just check for end state...

ConnectionState state = ConnectionState.checkAnswer;
while(! ConnectionState.endProcess.equals(state) {
  ...
}

You also might want to consider whether ConnectionState should implement an interface to make it extensible.  See Item #34 "Emulate extensible enums with interfaces", Effective Java Second Edition, by Joshua Bloch


Count the number of occurrences of a word I was selected for the third round of MS internships for third years. We were surprisingly asked a very easy question: “Make a program that counts the number of times the WORD "a" or "A" occurs”. I  wrote the code below and was rejected from attending the final interview.

What is wrong with my code? Please tell me how to improve it. People who used Char[] instead of string and those who didn't check for first and last words to be "A" were all selected.  The condition for commas before and after 'a' was also ignored. What is the error?
Is str.at(i) not good enough...? I know even if we use str[i] it is interpreted as str.operator[](i), so I'm preventing the overhead conversion, right?

#include<iostream>
#include<ctype.h>
#include<string>

using namespace std;

int main()
{

    string str;

    getline(cin,str);

    int i;
    int count=0;
    int l=str.length();

    for(i=1;i<l-1;i++)
    {
        if(toupper(str.at(i))=='A')
            if(str.at(i-1)==' ' && str.at(i+1)==' ')
                    count++;
    }

    if(toupper(str.at(0))=='A' && str.at(1)==' ')
        count++;

    if(toupper(str.at(l-1))=='A' && str.at(l-2)==' ')
        count++;

    cout<<"Count is "<<count<<endl;
    return 0;

}

First of all, these interview questions are often a trick. It doesn't really matter if your code works for all cases (everybody makes mistakes). What does matter is how you write the code.

Even if they ask specifically for 'a' or 'A', you are not supposed to hardcode these values. They are a parameter. Understanding what is the input to your program is always the first task. If they ask you "Make a program that counts the number of times the letter 'a' occurs in 'Example'", the correct answer won't be return 1;. They also ask for words, you shouldn't assume that the program should search only for words withs 1 letter.

Second - words are not usually delimited only by a space. You should consider all whitespace and punctuation characters. Or just declare a function isWordDelimiter(char) and don't implement it.

Third - your code is not easily readable. An if inside another if in a for? Use functions. Example (pseudocode - I am not C++ programmer and I forgot STL):

while ((word = getNextWord(input)) != NULL) {
    if (word is in set of searched words) {  //replace this with STL set
        count++
    }
}

Summary:
Even on a very simple program, they can see how much experienced you are. Good developer won't just write something that works. He has to think how the problem will evolve in the future (different parameters), how the program will be maintained (write readable code). Good developers also write programs from top to bottom - first define the structure using high level functions, then write the implementation of the functions.


Python Making Bruteforce Password Crack Faster I made a simple password cracker using Python. But it's extremely slow. Here is my code:

import itertools
import string
import sys
import socket

def connection(ip, user, passw, port):
    s = socket.socket()
    s.connect((ip, int(port)))
    data = s.recv(1024)
    s.send(('USER ' + user + '\r\n').encode())
    data = s.recv(1024)
    s.send(('PASS ' + passw + '\r\n').encode())
    data = s.recv(1024)
    s.send(('quit\r\n').encode())
    s.close()
    return data
def crack(ip, user, port):
    chars = string.digits + string.ascii_letters
    for password_length in range(1, 9):
        for guess in itertools.product(chars, repeat = password_length):
            guess = ''.join(guess)
            p = connection(ip, user, guess, port)
            if '230'.encode() in p:
                print('Username : ' + user + '\nPassword : ' + guess)
                sys.exit(1)
if len(sys.argv) != 4:
    print('Usage: ./passcracker.py <IP> <Username> <Port>')
    sys.exit(1)
crack(sys.argv[1], sys.argv[2], sys.argv[3])

I want to make it faster. Also if there is any wrong part in code, please tell me.

As has been noted in the comments, you should try to figure out what part of the code is slow. Is it the connection to the server or does your program just have to try many passwords and that takes so long?

The former can be measured by decorating connection with a decorator that records the time it took to run the function:

import time
from functools import wraps

def timeit(func):
    func.mean_time = [0]
    func.k = [0]
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.perf_counter()
        ret = func(*args, **kwargs)
        t = time.perf_counter() - start

        # update average
        func.k[0] += 1
        func.mean_time[0] += (t - func.mean_time[0]) / func.k[0]

        print(f"{func.__name__} took {t} s (Average: {func.mean_time[0]} s)")
        return ret
    return wrapper

Which you can use like this in general:

@timeit
def f():
    time.sleep(0.1)

for _ in range(10):
    f()
# f took 0.1002191620063968 s (Average: 0.1002191620063968 s)
# f took 0.10021526199852815 s (Average: 0.10021721200246247 s)
# f took 0.10016683799767634 s (Average: 0.10020042066753376 s)
# f took 0.10014399800274987 s (Average: 0.10018631500133779 s)
# f took 0.10016678299871273 s (Average: 0.10018240860081278 s)
# f took 0.10017002299719024 s (Average: 0.10018034433354235 s)
# f took 0.10020436099875951 s (Average: 0.10018377528571623 s)
# f took 0.1001491690039984 s (Average: 0.1001794495005015 s)
# f took 0.10017034399788827 s (Average: 0.10017843777798892 s)
# f took 0.10020105999865336 s (Average: 0.10018070000005536 s)

And here specifically:

@timeit
def connect(ip, user, passw, port):
    ...

Note that this will slow down the overall execution time a bit (since stuff needs to be done in addition), but you do learn if the connect is the bottleneck (and you can always remove the timing again later).

To find out if it is just the number of permutations, I would add some debug prints. I would also factor out the generating of the passwords from trying them further:

def brute_force_n(chars, password_length):
    start = time.perf_counter()
    for i, guess in enumerate(itertools.product(chars, repeat=password_length)):
        yield ''.join(guess)
    print(f"Tried all {i + 1} permutations of length {password_length}.")
    print(f"It took {time.perf_counter() - start} s.")

def brute_force(max_length=8):
    chars = string.digits + string.ascii_letters
    for password_length in range(1, max_length + 1):
        yield from brute_force_n(chars, password_length)

def crack(ip, user, port):
    for guess in brute_force():
        p = connection(ip, user, guess, port)
        if '230'.encode() in p:
            print('Username : ' + user + '\nPassword : ' + guess)
            sys.exit(1)

When testing this you will quickly discover that there are many permutations to try and even when doing nothing with them, this takes quite some time:

for _ in brute_force(5):
    pass  # do nothing with it

# Tried all 62 permutations of length 1.
# It took 3.321799886180088e-05 s.
# Tried all 3844 permutations of length 2.
# It took 0.0009744890048750676 s.
# Tried all 238328 permutations of length 3.
# It took 0.06495958699815674 s.
# Tried all 14776336 permutations of length 4.
# It took 4.06446365499869 s.
# Tried all 916132832 permutations of length 5.
# It took 310.80436263100273 s.

I stopped at length 5, you want to go to length 8. As you can see in this plot, the time rises very quickly (note the logarithmic y-axis):

Extrapolating this to password_length = 8, it would take about 536 days just to generate all combinations of that length.

The real solution to this problem is that you need to use some more information/a more clever tactic. A common method is to try words in a dictionary (and then words in a dictionary with numbers at the end, with known common replacements, etc).

Passwords are still used today because it is very hard to guess a (random) password of sufficient length.


Read CSV with 3 columns and group some elements I have a csv with 3 columns (date, name, number) and it is about 20K rows long. I want to create a dictionary keyed by date whose value is a dictionary of name:number for that date. On top of that, I want add some elements together if the name contains a key word so they would be listed as keyword:sum of numbers, rather than their individual entries.

E.g. If the csv had four entries

 6/17/84, Blackcat, 10,
 6/17/84, Dog, 20,
 6/17/84, Tabbycat, 12,
 6/17/84, Lizard, 5

and the keyword is cat, the result should be

{6/17/84: {'Dog':20, 'Lizard':5, 'cat':22}}

Here's what I came up with. Is there a better way?

       import csv
        import operator
        import collections
        import time

            def dict_of_csv(file_name, group_labels_with):
                complete_dict = {}
                key_word = [x.lower() for x in group_labels_with]
                for i in file_name:
                    key = i[1].lower()
                    key_value = int(i[2])
                    row_date = time.strptime(i[0], "%m/%d/%y")
                    if row_date not in complete_dict:
                        complete_dict[row_date] = {}
                        for name in key_word:
                            complete_dict[row_date][name] = 0
                    if any(name in key for name in key_word):
                        for name in key_word:
                            if name in key:
                                key = name
                        complete_dict[row_date][key] += key_value
                    else:
                        complete_dict[row_date][key] = key_value
                return complete_dict

    weeks = open("../DataIn/Master List 14day.csv", "rU")
    real_labels = csv.reader(weeks)

print dict_of_csv(real_labels, ['keyword1', "keyword2", "keyword3"])

weeks.close()

The first argument to your function does not appear to be a string holding the name of a file, as its name lead me to initially assume. I would suggest you change to e.g. csv_reader (right?) to make it clear what we're getting.

i is another bad variable name, it's usually used for an integer index, and doesn't tell the reader anything useful. Also, the following is more meaningful than the current indices into i:

for date, key, val in csv_reader:

You can then apply whatever processing you need and it's still clear what's happening:

val = int(val)

I see what you're trying to do here:

if any(name in key for name in key_word):
    for name in key_word:
        if name in key:
            key = name

But won't save any time - you have to go through all name in key_word once for the any(...) is False case, and fully twice in the worst any(...) is True case. Just use:

for name in key_word:
    if name in key:
        key = name

collections.defaultdict would simplify much of that code for you, for example:

complete_dict = defaultdict(lambda: defaultdict(int))
...
for date, key, val in csv_reader:
    ...
    date = time.strptime(date, "%m/%d/%y")
    for name in key_word:
        ...
    complete_dict[date][key] += val # don't need any checks for keys

On a logical point, what should happen if a key contains more than one key_word, or if there are overlaps between key_words? At the moment the first match is used in cases where there are no further complications, but you could break to ensure this (and speed up the code).


Bisect Insertion Container for Calculating Running Median I'm looking for general feedback on this implementation. What issues might it  have? How could it be improved?

public class FindRunningMedian
{
    public void Run(string[] args)
    {
        var bound = 100000;
        var rando = new Random();
        var values = new[] { bound.ToString() }.Concat((from i in Enumerable.Range(0, bound)
                                                        select rando.Next(int.MaxValue / 2).ToString())).ToArray();

        RunBiSect(values);
    }

    public void RunBiSect(string[] args)
    {
        var count = Convert.ToInt32(args.First());
        var valus = args.Skip(1).Select(s => Convert.ToInt32(s)).ToArray();
        var sortd = new MedianList(count);

        foreach (var value in valus)
        {
            Console.WriteLine($"{sortd.InsertForMedian(value):F1} ");
        }
    }

    public class MedianList
    {
        private int _count;
        private float _iters;
        private int[] _values;

        public MedianList(int capacity)
        {
            _values = new int[capacity];
        }

        public int Count { get { return _count; } }

        public float Iterations { get { return _iters; } }

        public float IterationsPer { get { return _iters / Math.Max(1, _count); } }

        public int[] GetValues()
        {
            var copy = new int[_values.Length];
            _values.CopyTo(copy, 0);
            return copy;
        }

        public float InsertForMedian(int value)
        {
            Insert(value);
            var median = 0.0f;
            var middle = _count / 2;

            if (_count == 1) { median = _values[0]; }
            else if (_count % 2 == 0) { median = (_values[middle] + _values[middle - 1]) / 2.0f; }
            else { median = _values[middle]; }

            return median;
        }

        public void Insert(int value)
        {
            if (_count == 0) { _values[0] = value; }
            else
            {
                var index = FindDestinationIndex(value);
                Array.Copy(_values, index, _values, index + 1, _count - index);
                _values[index] = value;
            }
            _count++;
        }

        public int FindDestinationIndex(int value)
        {
            var max = _count - 1;
            int mid = 0, cmp = 0, min = 0;

            if (value.CompareTo(_values[0]) <= 0) { return 0; }
            else if (value.CompareTo(_values[_count - 1]) >= 0) { return _count; }

            while (max > (min + 1))
            {
                mid = Convert.ToInt32(Math.Min(Math.Ceiling((max - min) / 2.0f) + min, _count - 1));
                cmp = value.CompareTo(_values[mid]);

                if (cmp == 0) { return mid; }
                else if (cmp > 0) { min = Math.Max(mid, min + 1); }
                else if (cmp < 0) { max = Math.Min(mid, max - 1); }

                _iters++;
            }

            mid = value.CompareTo(_values[min]) > 0 && value.CompareTo(_values[max]) <= 0 ? max : min;

            cmp = value.CompareTo(_values[mid]);

            var index = cmp > 0 ? mid + 1 : mid;
            return index;
        }
    }
}

This

var values = new[] { bound.ToString() }.Concat(..).ToArray();
RunBiSect(values);

plus this

public void RunBiSect(string[] args)

plus this

var count = Convert.ToInt32(args.First());
var valus = args.Skip(1).Select(s => Convert.ToInt32(s)).ToArray();

is a super weird way of passing arguments from method to another. I'm not sure if you know it but methods can take more then one parameter ;-)

var valus = ..;
var sortd = ..;

Where is the e? Don't you like it? You should not use abbreviations unless they are well known like html or xml etc.

public class MedianList

Nested classes should not be public. Then this class is not a list and should be called like that. MedialCalculator sounds much better. Shouldn't the InsertForMedian API be named CalcMedian?

public float IterationsPer { get { return _iters / Math.Max(1, _count); } }

Here is something missing: IterationsPer what?


Avoiding Duplicate Boilerplate Code in WCF Service I'm responsible for maintaining a web service project in c#.  I have one service class with a bunch of methods that look a lot like this:

    [OperationContract]
    [WebInvoke(Method = "POST", UriTemplate = "v1/Login", ResponseFormat = WebMessageFormat.Json)]
    public string Login()
    {
        try
        {
            JObject incomingRequestJson = retrieveJson();
            JObject returningJson = new JObject();

            string accountId = incomingRequestJson.SelectToken("accountId", true).ToString();
            string username = incomingRequestJson.SelectToken("userName", true).ToString();
            string password = incomingRequestJson.SelectToken("password", true).ToString();

            LoginResult result = readerBLL.Login(accountId, username, password);
            returningJson.Add(new JProperty("userSessionId", result.userSessionId));
            returningJson.Add(new JProperty("friendlyUserName", result.friendlyUserName));

            return returningJson.ToString(Newtonsoft.Json.Formatting.None);
        }
        catch (Exception ex)
        {
            throw new WebFaultException<string>(ex.Message.ToString(), HttpStatusCode.OK);
        }
    }

Note that retrieveJson() grabs a JSON string from the HttpContext and runs JObject.Parse() on it.
Note also that the consumer of this service is a Flex app, so I do need the WebFaultException business with the "OK" response code (The networking component in Flex treats connection timeouts and all HTTP error codes exactly the same - no further data other than

I don't like the way I have the try-catch block repeated in every method, so I tried making the following method:

private object invokeBusinessLogic(Func<JObject, object> f)
    {
        try
        {
            return f(retrieveJson());
        }
        catch (Exception ex)
        {
            WebFaultException<string> wfe = new WebFaultException<string>(ex.Message.ToString(), HttpStatusCode.OK);
            throw wfe;
        }
    }

Then my service methods can look like this:

public object Login()
{
    LoginResult result = (LoginResult) invokeBusinessLogic(readerBLL.Login);
    returningJson.Add(new JProperty("userSessionId", result.userSessionId));
    returningJson.Add(new JProperty("friendlyUserName", result.friendlyUserName));

    return returningJson.ToString(Newtonsoft.Json.Formatting.None);
}

However, this has the problem that the use of JSON to carry the request data gets exposed to the business layer.  Is there a better way to avoid the duplicate try-catch blocks than this invokeBusinessLogic idea?

I'm not sure why your change all of a sudden would expose data to the business layer when it didn't before.

If you have a pattern of methods which look like this:

public string MyServiceCall()
{
    try
    {
        JObject incomingRequestJson = retrieveJson();
        JObject returningJson = new JObject();

        // do stuff

        return returningJson.ToString(Newtonsoft.Json.Formatting.None);
    }
    catch (Exception ex)
    {
        throw new WebFaultException<string>(ex.Message.ToString(), HttpStatusCode.OK);
    }
}

Then you can simply add a helper method to your service implementation:

private string ProcessServiceCall(Func<JObject, JObject> processor)
{
    try
    {
        JObject incomingRequestJson = retrieveJson();
        JObject returningJson = processor(incomingRequestJson);

        return returningJson.ToString(Newtonsoft.Json.Formatting.None);
    }
    catch (Exception ex)
    {
        throw new WebFaultException<string>(ex.Message.ToString(), HttpStatusCode.OK);
    }
}

and your service call then becomes:

public string MyServiceCall()
{
    ProcessServiceCall(incomingRequestJson => {

        string accountId = incomingRequestJson.SelectToken("accountId", true).ToString();
        string username = incomingRequestJson.SelectToken("userName", true).ToString();
        string password = incomingRequestJson.SelectToken("password", true).ToString();

        JObject result = new JObject();

        LoginResult result = readerBLL.Login(accountId, username, password);
        result.Add(new JProperty("userSessionId", result.userSessionId));
        result.Add(new JProperty("friendlyUserName", result.friendlyUserName));

        return result;
    }
}

This should be a simple refactoring on your service class and not expose any more json to the business logic than before.


MVC binding list of values to checkboxlist in an efficient way I have this code which generates and shows list of selectable items that user can post to controller in order to save into database.

Model looks like this:

public class DeliveryAddressSelectionModel()
{
public List<DeliveryAddress> DeliveryAddresses { get; set; }
public List<int> SelectedAddressIDs { get; set; }
}
public class DeliveryAddress()
{
public int ID { get; set; }
public string Location { get; set; }
}

Controller looks like

[HttpGet]
public ActionResult Edit()
{
    var model = new DeliveryAddressSelectionModel();
    model.DeliveryAddresses = AddressDetails.GetAvailable(); //Get from  EF
    model.SelectedAddressIDs = new List<int>(); //Populate this list with Address IDs for pre-selection
    return View(model);
}

[HttpPost]
public ActionResult Edit(DeliveryAddressSelectionModel model)
{
    //save the model.SelectedAddressIDs in DB
    return RedirectToAction("Index");
}

And finally view looks like this:

<form method="post">

        @foreach(var address in DeliveryAddresses)
        {

            <input id="address@(address.ID)" type="checkbox"
                name="SelectedAddressIDs"
                value="@address.ID"
                @(Model.SelectedAddressIDs.Contains(address.ID) ? "checked" : "")
                />
            @address.Location

        }

    <input type="submit" value="Save Address"/>
</form>

This code works, but as I am learning  MVC, and I would like to have suggestions. What areas in this code could have been done better, or what is best practice in regards with this kind of model population and posting? Could I use a @Html.CheckBoxFor() helper or this is ok?

In my opinion, your view is doing too much work. This is happening because your model is missing a property.

If you add an IsSelected property to your model, I think we can simplify the view a bit.

public class DeliveryAddress()
{
    public int ID { get; set; }
    public string Location { get; set; }
    public bool IsSelected { get; set; }
}

Now this single model contains all the information you need to bind to the view. You no longer even need the DeliveryAddressSelectionModel. The controller would look something like this (untested, I'm typing in the browser):

[HttpGet]
public ActionResult Edit()
{
    var selectedAddressIDs = new List<int>() { 1, 2, 4 };

    List<DeliveryAddress> model = AddressDetails.GetAvailable();

    foreach(var address in model.Where(a => selectedAddressIDs.Contains(a.ID)))
    {
        address.IsSelected = true;
    }

    return View(model);
}

Create a partial view for your DeliveryAddress.

@Model DeliveryAddress

@Html.CheckBoxFor(m => m.IsSelected)
@Html.LabelFor(m => m. Location)

Then, from your main view, render the partial view.

@Model System.Collections.Generic.List<DeliveryAddress>

<form method="post">

        @foreach(var address in Model)
        {

            @Html.RenderPartial("DeliveryAddress", address)

        }

    <input type="submit" value="Save Address"/>
</form>


Set Game State from String Before I used reflection to invoke a state based on the string, it looked like this:

public void setState (String state) {
    try {
        this.state = (State) Class.forName("state"+state).getConstructor().newInstance();
    } catch (Exception e) {
        System.out.println ("Tried to set state to " + state.toString() + ", but no such state exists.");
    }
}

It is supposed to say ...forName("state."+state). Notice the period in "state.".

However, it feels wrong to use reflection when I know all the State the project can be in.

They are:

Title
NewGame
LoadGame
Credits
HighScore
World

I'm rendering the most straightforward solution to be along these lines:

private  void setState (String state) {
    switch (state) {
        case "Title":
            this.state = new Title ();
            break;
        case "NewGame":
            this.state = new NewGame ();
            break;
        case "LoadGame":
            this.state = new LoadGame ();
            break;
        case "Credits":
            this.state = new Credits ();
            break;
        case "HighScore":
            this.state = new HighScore ();
            break;
        case "World":
            this.state = new World ();
            break;
        default:
            System.out.println ("Tried to set state to " + state.toString() + ", but no such state exists.");
    }
}

Is it possible to clean that up?

For example, could instance-mapping be a solution?

There is a very similar situation with the handle method. In the reflection case it looks like this:

public void handle (Event event) {
    try {
        this.getClass().getMethod(event.getMethod(), String.class).invoke(this, event.getArgument());
    } catch (Exception e) {
        state.handle (event);
    }
}

If the method can't be invoked in this class then it will be invoked in the state instead. Meaning, the exception can be caught for that reason.

However, it does not look as neat if I were to use mapping or a switch-case clause here:

public void handle (Event event) {
    switch (event.getMethod()) {
        case "setState":
            setState (event.getArgument());
            break;
        case "loadGame":
            loadGame (event.getArgument());
            break;
        case "logDebug":
            logDebug (event.getArgument());
            break;
        case "exitGame":
            exitGame (event.getArgument());
            break;
        default:
            state.handle(event);
            break;
    }
    logDebug ("Event handled: " + event.toString());
}

Can something similar be used in these two cases or is it fine to use reflection?

this.state = (State) Class.forName("state"+state).getConstructor().newInstance();

This looks for a class named "stateWhatever", which isn't what you're doing below. Let's assume it's an error which happened when you copied the code.

private  void setState (String state) {
    switch (state) {
        case "Title":
            this.state = new Title ();
            break;
        case ....................
        default:
            System.out.println ("Tried to set state to " + state.toString() + ", but no such state exists.");
    }
}

Yes, this is going to get pretty long. But don't you simply separate the setting of the state from its computation?

 private State getState() {
    switch (state) {
        case "Title":
            return new Title ();
        case ....

Here, you save one line, you could save another one if your conventions allow it and that's the optimum.

In case you can precreate your states, then simply

private static final Map<String, State> stateMap;
static {
     Map<String, State> map = new Map<>();
     map.put("Title", new Title()):
     ...
     stateMap = Collections.unmodifieableMap(map);
}

would do. The usage is obvious.

In case you can't precreate your states, then you could create a

private static final Map<String, Class<? extends State>> stateClassMap;

and use reflection for the instance creation.

You're having many implementation of state and each of them has a no-args constructor. This looks like an enum.

    System.out.println ("Tried to set state to " + state.toString() + ", but no such state exists.");

You know that's no proper error handling, right?


Console RPG - show cycle optimization I have this RPG game and this has elements such as the map, the monsters and the items. The monsters and the items are stored in Lists and every time I want to show the map around the player, I have to check if the element is within the bounds of the camera.

public void ShowCamera()
    {
        int size = cameraSize/2;
        int topY = player.GetY() - size, bottomY = player.GetY() + size, topX = player.GetX() - size, bottomX = player.GetX() + size;
        int setX = 0, setY = 0;

        //Print Map
        Console.SetCursorPosition(0,0);
        Console.ForegroundColor = ConsoleColor.DarkGreen;
        for (int i = topX; i < bottomX; i++)
        {
            for (int j = topY; j < bottomY; j++)
            {
                Console.ForegroundColor = ConsoleColor.DarkGreen;
                Console.SetCursorPosition(setY,setX);
                Console.Write(map[i, j]);
                if (monstros.Count > 0)
                {
                    Console.ForegroundColor = ConsoleColor.DarkRed;
                    foreach (var elem in monstros)
                    {
                        if (elem.ReX() == i && elem.ReY() == j)
                        {
                            Console.SetCursorPosition(setY, setX);
                            Console.Write(elem);
                        }
                    }
                }
                if (items.Count > 0)
                {
                    Console.ForegroundColor = ConsoleColor.DarkRed;
                    foreach (var elem in items)
                    {
                        if (elem.ReX() == i && elem.ReY() == j)
                        {
                            Console.SetCursorPosition(setY, setX);
                            Console.Write(elem);
                        }
                    }
                }
                setY++;
            }
            Console.Write("\n");
            setY = 0;
            setX++;
        }

So, this works but it is very unoptimized and flickers a lot. I was wondering if there's a way to improve this cycle in any way.

Performance

The main problem seems to be that you're checking each monster and item for each console position. If cameraSize is 80, that means you're checking each monster and item 80 x 80 = 6400 times.

Just draw the map first, and then loop through your monsters and items (once) and draw them if they're within view.

Other notes

You're using a lot of getter methods: GetX(), GetY(), ReX(), ReY(). In C# properties are normally used instead of getter/setter methods.

ReX and ReY are not very descriptive names. Obviously we're dealing with coordinates here, but what does that Re prefix mean?

Since you're dealing with 2D coordinates quite frequently, it could be useful to create a separate Position class for that, with X and Y properties and perhaps some overloaded operators (+, -) and utility methods (int DistanceTo(Position other), and so on).

Calling Console.Write(elem) invokes elem's ToString method. Personally I'd give those monster and item classes a public char Appearance { get; private set; } property, and turn that write call into Console.Write(elem.Appearance), to make it more obvious what's going on, and so I don't have to abuse a ToString method.

Monstro and Item class

These notes refer to the classes you posted in the chat:

new Random() gives you a pseudorandom number generator that's seeded based on the current time. Because each monster has its own Random instance, they will likely move in the exact same way if you create multiple monster instances at the same time (or close enough).

Your movement code can be simplified: if you use a offsetX and offsetY variable, which are set based on the chosen direction, then you don't need that switch-case statement anymore.

Making Item responsible for its own placement is quite inflexible. Just give its constructor an x and y parameter, and let the map-generating/loading code figure out where to place items.

Randomly picking spots until you find an empty one should work just fine if there's plenty of space, but large maps with few empty spots will cause a lot of retries. It'll even loop indefinitely if there is no empty spot available.

SetPickedUp can be simplified to pickedUp = argPickedUp. Or just use a property instead.

Map.CheckTile is not a very descriptive name. Map.IsTileEmpty is more obvious.

You don't need those StringBuilders in your ToString methods. Just return appearance.ToString() or GetType().Name directly.

More notes

Making Item and Monstro abstract implies that you've got several classes that inherit from them. I assume that each different item has a class of its own? That makes sense if different items actually have different behavior, but if they only have different stats, then a single Item class is sufficient. Since Item has an attack, defense, health and rarity field, it can already be used for a variety of different items: weapons (attack), armor (defense), health potions (health).

In larger games, such data is often stored in csv or Excel files, which makes it easy for game-designers to adjust items without the help of a programmer. In your case that's probably not worth the effort, but you can still create a 'table' of item data in code. For a one-man project that's just as easy to modify, and still saves you a ton of useless classes:

var itemBlueprints = Dictionary<string, Item> {
    { "Sword", new Item(5, 0, 0, 0.05, '|') },
    { "Shield", new Item(0, 2, 0, 0.08, 'o') },
    { "Potion", new Item(0, 0, 5, 0.12, '+') },
};

You'll want to add a Name property to the Item class so you can still determine an item's name (the type name no longer tells you what it is). That's more flexible than using a type name anyway.

The above code could be made a little more readable by using optional and named parameters:

new Item("Sword", attack: 5, rarity: 0.05, appearance: '|');
new Item("Shield", defense: 2, rarity: 0.08, appearance: 'o');


Finding subsets from specified array, avoiding duplicates I am printing subsets from an array whose sum has been specified, while avoiding duplicates.

I think there may be improvements, potentially on how using map is bad idea, or how can I avoid map to filter the duplicates.

Additionally, in my code I want to reverse the sort order of an int array using streams which is asked over here, are there any alternatives rather than sorting and reversing the array?

public class FindSubSetArray {

    private static final int TARGET_SUM = 24;
    private static Map<String,Integer> subSet = new HashMap<>();
    private static int count = 0;

    public static void main(String[] args) {
        int[] array= {2, 5, 1, 2, 4, 1, 6, 5, 2, 2};
        Arrays.sort(array);
        findSubset(array, 0, 0, "");
        subSet.keySet().stream().forEach(System.out::println);
    }

    public static void findSubset(int[] array, int index, int current, String subSetString) {

        if (current > TARGET_SUM || array.length < index) return;

        for (int i = index; i < array.length; i++) {
            int presentSum = current + array[i];
            if (presentSum == TARGET_SUM) {
     //         System.out.println(subSetString + " " + array[i]);
                subSet.put(subSetString + " " + array[i], count++);
            } else {
                findSubset(array, i + 1, presentSum, subSetString + " " + array[i]);
            }
        }
    }
}

To avoid the duplicates, you need to make the decision whether that element is already part of the subset. To do so, you need to do search in the already considered elements for the subset.

The challenge is performing this search optimally. Available options are to use a BST to store the subset elements which can be summed to the target sum. The searching operation will be efficient (log2H H -height of tree). This operation needs to be performed for every element, so it's better to use a BST.

Another alternative is to sort the given input, which is at the cost of \$\mathcal{O}(n \log n)\$. Then we can easily check the duplicates in the subset as they are appearing consecutively.

Let's compare the above approach:

BST has two costs:

Construction of BST for each subset and balancing it
Cearching (log2H)

Sorting approach needs: \$\mathcal{O}(n \log n)\$

The winning answer is to maintain the HashSet of the subset and contains can be performed in \$\mathcal{O}(1)\$ constant time.


Circular dependencies between immutable objects; the Freeze Pattern Generally, I structure small threadsafe immutable objects like this:

public class SmallObject {
    private final String state;
    public SmallObject(final String state) {
        this.state = state;
    }

    // ...
}

And then wire these up in Spring like this:

<bean name="SmallObjectForThisThing" class="my.package.SmallObject">
    <constructor-arg name="state" value="in practice this is usually a ref"/>
</bean>

However, this leads to complications with circular dependencies.  To keep the immutability when this happens, I use a "freeze" pattern, where the variables are set once.  This is what I want reviewed:

public class SmallObject {
    private String state = null;

    public void setState(String state) {
        if (this.state != null) {
            throw new IllegalStateException("state already set: '" + state + "'.");
        }
        this.state = state;
    }

    private void ensureInitialized() {
        if (this.state == null) {
            throw new IllegalStateException(
                "state must be set before this instance is used."
            );
        }
    }

    // ... For every additional method on the object, I call
    // ensureInitialized() first.
}

And then wire them up like this:

<bean name="SmallObjectForThisThing" class="my.package.SmallObject">
    <property name="state" value="in practice this is usually a ref"/>
</bean>

This class should instead use an AtomicReference to ensure the state is kept valid. Alternatively, you should incorporate thread-safe handling of the String.

Consider:

private final AtomicReference<String> stateref = new AtomicReference<String>();

public void setState(final String state) {
    // only one initializer will succeed (assuming state is not null)...
    if (!stateref.compareAndSet(null, state)) {
        throw new IllegalStateException("state already set: '" + state + "'.");
    }
}

private void ensureInitialized() {
    if (stateref.get() == null) {
        throw new IllegalStateException(
            "state must be set before this instance is used."
        );
    }
}

This pattern ensures usage is consistent, there can be only one initialization of the instance, and that any thread-unsafe practices are handled well.


Improved the output of the related posts in WordPress I made a simple code to improve the results for WordPress related posts area and it works fine , but because my experience in coding is low , my code is very long and i believe that there is a way to make simple and better

here is the code :-

$cat = get_the_category();
$cat0 = $cat[0];
$cat1 = $cat[1];
$cat2 = $cat[2];
$cat3 = $cat[3];
$cat4 = $cat[4];
$cat5 = $cat[5];
$cat6 = $cat[5];

    if ($cat0->cat_ID == 10 || $cat1->cat_ID == 10 || $cat2->cat_ID == 10 || $cat3->cat_ID == 10 || $cat4->cat_ID == 10 || $cat5->cat_ID == 10 || $cat6->cat_ID == 10){
        $post = get_the_ID();
        $args = array('cat'=>10, 'orderby' => 'date', 'showposts' => $related,'post__not_in' => array($post));
    } elseif ($cat0->cat_ID == 12 || $cat1->cat_ID == 12 || $cat2->cat_ID == 12 || $cat3->cat_ID == 12 || $cat4->cat_ID == 12 || $cat5->cat_ID == 12 || $cat6->cat_ID == 12){
        $post = get_the_ID();
        $args = array('cat'=>12, 'orderby' => 'date', 'showposts' => $related,'post__not_in' => array($post));
    } else {
        $cat = $cat[0];
        $cat = $cat->cat_ID;
        $post = get_the_ID();
        $args = array('cat'=>$cat, 'orderby' => 'date', 'showposts' => $related,'post__not_in' => array($post));
    }

$related = new WP_Query($args);

Also, i tried to use "foreach" function but it always fails in "else" part

Thanks

The major thing for me in this code is the repetition forms a large part of it.  You can also use some of the features of PHP to stop having to move data around and comparing individual items.

Using array_column() (this requires PHP 7+ as your input is an array of objects) to fetch all of the values of cat_ID, stops you having to extract the values from the objects and then compare each one individually.  You can then use in_array() to check for each value against all of them in one call rather than the list of || conditions.

Then the code setting $args is the same in each branch of your if, so I've reduced this to each branch sets $cat (as your last branch already does) and then this is used by the same code outside the if...

$cat = get_the_category();

$categories = array_column($cat, "cat_ID");
if ( in_array(10, $categories) ){
    $cat = 10;
} elseif (in_array(12, $categories)){
    $cat = 12;
} else {
    $cat = $cat[0]->cat_ID;
}
$post = get_the_ID();
$args = array('cat'=>$cat, 'orderby' => 'date',
    'showposts' => $related,'post__not_in' => array($post));


How can I use the State monad effectively in Haskell? I have written a simple fibonacci function in Haskell that uses the State monad to save solutions to overlapping sub-problems. Now despite the function working I am not really happy with the solution, especially with the last map lookup. How can I improve my solution? Thank you.
module Lib (
    fib
) where

import Control.Monad.State
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Maybe

type DP = Map Int Int

fib :: Int -> State DP Int
fib 0 = return 1
fib 1 = return 1
fib x = do
    solved <- get
    let m = Map.lookup x solved
    case m of
            Nothing -> do
                prev1 <- fib (x - 1)
                prev2 <- fib (x - 2)
                put $ Map.insert x (prev1 + prev2) solved
            Just value -> put $ Map.insert x value solved
    gets (fromMaybe 0 . Map.lookup x)

I won't be reviewing this code for efficiency, since I'm not quite so comfortable with analyzing some combination of State monad, immutable data structures, and laziness.
However, there are a few obvious changes you can make to your code.
Passing State Properly
This is what Franky was getting at with his comment, and it's a bit of a tricky bug. When you do
put $ Map.insert x (prev1 + prev2) solved

you use the solved that you get at the beginning of the function invocation. But your recursion goes from top-to-bottom, so if you're computing fib 10, solved is the empty map when you are getting the final answer. Essentially, your memo map keeps getting overwritten with maps that have less information. The fix is pretty easy.
prev1 <- fib (x - 1)
prev2 <- fib (x - 2)
solved' <- get
put $ Map.insert x (prev1 + prev2) solved'

Just get the updated state after the recursive invocations.
Naming
I think solved is ambiguous as to whether it refers to a single solution or the memo map. I would call it something like solutions, maybe sols or fibs if you feel like abbreviating. In light of the previous bug, you may wish to call the first one initialSolutions and later ones updatedSolutions or something like that (I just used solutions and solutions').
The name m is OK, but it doesn't really need to exist at all. You can just case on Map.lookup x solved directly instead of binding m and then casing on it.
The case Statement
It seems like you're trying to use the case statement to set up your memo map so that it always has a value for x. There are two things to address about this.
Indexing
If you, the programmer, are sure that x exists in the map (and in the case above you guarantee it), you could instead use the unsafe lookup Map.!. Given the option between returning an erroneous value silently (your fromMaybe 0) and crashing and burning in case of a bug, I would generally prefer the latter. So your last line would look something like gets (Map.! x).
The Last Lookup
However, doing the lookup itself is inelegant. It might make sense if there was a lot of convoluted stuff happening between, but proper indexing doesn't get checked by the type system and doing a lookup takes (not much, but some) extra time. Fortunately, you don't need to do it. Since I'm going to assume you're learning Haskell, consider how you'd approach a similar problem in an imperative language. What would you do to change this code:
if (x in solutions):
  solutions[x] = solutions[x]
else:
  prev1 = fib(x-1)
  prev2 = fib(x-2)
  solutions[x] = prev1 + prev2
return solutions[x]

There are many right answers, but one thing you can do is as follows (this particular code is nice because it avoids extra lookups):
if (x in solutions):
  return solutions[x]
else:
  prev1 = fib(x-1)
  prev2 = fib(x-2)
  solution = prev1 + prev2
  solutions[x] = solution
  return solution

Your case statement functions like the imperative if statement, except more powerful since you have guarantees on the types! So mirroring the imperative's revision, you can revise your code like so
case Map.lookup x solved of
        Just solution -> return solution
        Nothing -> do
            prev1 <- fib (x - 1)
            prev2 <- fib (x - 2)
            solutions' <- get
            let solution = prev1 + prev2
            put $ Map.insert x solutions' solved
            return solution

Now you don't need the last lookup. Notice how we also avoid the issue entirely of whether x is in solutions, because we explicitly handle the case where it is and isn't. This code doesn't have any unsafe lookups!
Addendum on Lookups
Now, even if you wanted to make your case statement only fill out the memo map instead of also returning the answers, I agree with you that you are doing unnecessary work.
Just value -> put $ Map.insert x value solved

The line above needlessly reinserts the value of x. The memo map already has x, and x is already set to value. If you wanted to otherwise keep your code the same, at least change this to
Just value -> return ()

put has type a -> State a (). It's a convention for monads to pass () as their return value if they perform an action that doesn't return anything (like how putStrLn has type String -> IO ()). You can simply return () to do nothing instead of actually modifying the memo map, which I assume you did to fix a type error.
Revised Function
Included are comments noting the revision
fib :: Int -> State DP Int
fib 0 = return 1
fib 1 = return 1
fib x = do
    -- Change to a more descriptive name
    solutions <- get
    -- Case directly on the value without intermediate variable
    case Map.lookup x solutions of
            Nothing -> do
                prev1 <- fib (x - 1)
                prev2 <- fib (x - 2)
                -- Get updated solutions
                solutions' <- get
                let solution = prev1 + prev2
                put $ Map.insert x solution solutions'
                -- Return solution directly
                return solution
            Just solution ->
                -- Return solution directly
                return solution
    -- Elide previous lookup


Piano, output all the keys and give a scale I've two snippets below, the first one output all the keys of a piano and the second one give me a scale when given a starting note. For those who don't know how a piano is structured here is an image of a piano.
Basically I want to put each notes, in an ordered array. As you can see the black notes have two names, one with b in it and one with #. Those two names are equivalent but I'm using the one with b.

So I have to create this array (like the image):

[ "A0", "Bb0", "B0", "C1", "Db1", "D1", "Eb1", "E1", "F1", "Gb1", "G1", "Ab1", "A1", "Bb1", "B1".............., "B7", "C8"]

Or check the console output from the jsfiddle below.

jsfiddle

const KEYS_NORMAL =  ["C", "Db", "D", "Eb", "E", "F", "Gb", "G", "Ab", "A", "Bb", "B"];

let keys = KEYS_NORMAL.slice(-3);
keys = keys.map( k => k + '0');

for(let octave = 1; octave < 8; octave++){
  for(let key of KEYS_NORMAL){
    keys.push(key + octave)
  }
}
keys.push('C8')
keys.forEach(k => console.log(k));
// I'm actually doing some work with those notes, So ultimately this is one more loop.

The second algorithm returns a scale given a note. For those who don't know a scale starts on any note and is given by the algorithm below:

Major: 2 - 2 - 1 - 2 - 2 - 2 - 1

Minor : 2 - 1 - 2 - 2 - 1 - 2 - 2

We can distinguish between major and minor because an m is appended to the name, eg: A is major whereas Am is minor.

Where 1 means go one note above, and 2 means go 2 notes above (the black keys are also notes).

Here is jsfiddle

Code :

 majorSemiTones = [2,2,1,2,2,2];
 minorSemiTones = [2,1,2,2,1,2];
 KEYS = ["A", "Bb", "B", "C", "Db", "D", "Eb", "E", "F", "Gb", "G", "Ab"];
 KEYS_NORMALIZED = ["C", "Db", "D", "Eb", "E", "F", "Gb", "G", "Ab", "A", "Bb", "B"];

 function getScale(scaleName){
        let tonic = scaleName.replace("m", "");
        let keys = [];
        let minor = false;
        let scaleIndex;
        let intervals = this.majorSemiTones;
        if(scaleName.indexOf("m") > -1){
            minor = true;
            intervals = this.minorSemiTones;
        }
        scaleIndex = KEYS.indexOf(tonic);// starts on the tonic
        for(let i = 0; i < 7; i++){
            keys.push(KEYS[scaleIndex]);
            if( scaleIndex + intervals[i] > KEYS.length - 1 ){
                scaleIndex = scaleIndex + intervals[i] - KEYS.length;
            }else{
                scaleIndex += intervals[i];
            }
        }
        return keys;
    }

What I hope to get from this review is ways to improve my code. The second snippet seems needlessly complex and unreadable while the first one seems inefficient and seems like it could benefit from some functional js.

Since you tagged this question with typescript, I would say you could benefit greatly from making your keyboard and scale representations into classes.

Since there are different keyboard layouts, I wonder if it makes sense to generalize the functionality on creating a keyboard based on standard keyboard configurations?

Your current logic to build keys seems basically hard-coded for standard 88 key keyboard. There is an odd mix of work that is happening before the main loop where keys are populated (setting the octave 0 keys) and after that main loop (setting the octave 8 key). I would strive to set all key values within the loop so this logic isn't disjointed like it currently is.

In both pieces of logic, you might consider "rotating" the array of 12 notes to get to an appropriate starting position for working with the array based on the values input.  This could make your array interaction logic much cleaner, by avoiding the need to look for boundary conditions on the array (i.e. when you need to go back to index 0);

You also have some fragility in your code around data input.  You really don't have anything here that validates or handles edge cases in input data (for example what if values like a, ABm, are passed to getScale()?).

Code like this:

if(scaleName.indexOf("m") > -1){

might be better to be made more specific like this:

if(scaleName.indexOf("m") === 1) {

as there is only one index value where m should ever be encountered.

Alternately, I would consider a regex like /^([A-G]b?)(m?)$/ to be able to validate the input string and capture the components of the string in one pass.

I don't understand the need for both KEYS and KEYS_NORMALIZED in the scale code.  This is just the same array rotated, and considering you will have to rotate or transform the array given the specific input scale, why have two arrays that hold the same values?

Some variable names seem confusing. For example:

In the "piano" code, your KEYS constant might better be called notes or keyNotes or similar since this array is not the representation of the physical "keys" on the keyboard.
In getScale(), keys array is not dealing with the key of the scale or keys on a keyboard, but rather the notes in the scale, so perhaps notes might be a better name.
In getScale() the major/minorSemiTones variables might better be named major/minroSemiToneIntervals.

Putting it all together might yield something like:

class Keyboard {
     static readonly standardKeyboardConfig = {
         49: {
             startKey: 'C',
             startOctave: 0,
             octaveBoundary: 'C'
         }
         61: {
             startKey: 'C',
             startOctave: 0,
             octaveBoundary: 'C'
         },
         76: {
             startKey: 'E',
             startOctave: 0,
             octaveBoundary: 'C'
         },
         88: {
             startKey: 'A',
             startOctave: 0,
             octaveBoundary: 'C'
         }
     }
     static readonly defaultKeyCount = 88;
     static readonly keyNotes = ["C", "Db", "D", "Eb", "E", "F",
         "Gb", "G", "Ab", "A", "Bb", "B"];
     readonly keys: string[];

     constructor(keyCount: number) {
         keyCount = keyCount || Keyboard.defaultKeyCount;
         if (keyCount in Keyboard.standardKeyboardConfig === false) {
             throw new RangeError('Invalid keyboard specified');
         }

         let config = Keyboard.standardKeyboardConfig[keyCount];
         let startKey = config.startKey;

         // first rotate the array of notes if needed
         let keyNotes = Keyboard.keyNotes;
         if(startKey !== keyNotes[0]) {
             let index = keyNotes.indexOf(startKey);
             keyNotes = keyNotes.slice(index, keyNotes.length)
                              .concat(keyNotes.slice(0, index));
         }

         // now build out keys with octave values
         let octave = config.startOctave;
         let octaveLength = keyNotes.length;
         let octaveBoundary = config.octaveBoundary;
         for (i = 0; i < keyCount; i++) {
             let noteIndex = i % octaveLength;
             let note = keyNotes[noteIndex];
             if (i > 0 && note === octaveBoundary) {
                 octave++;
             }
             this.keys.push(note + octave);
         }
     }
}

// usage for default keyboard (a piano)
let piano = new Keyboard();
let keys = piano.keys;

class Scale {
    static readonly majorSemiToneIntervals = [2,2,1,2,2,2];
    static readonly minorSemiToneIntervals = [2,1,2,2,1,2];
    static readonly regex = /^([A-G]b?)(m?)$/;
    static readonly allNotes = ["A", "Bb", "B", "C", "Db", "D", "Eb",
        "E", "F", "Gb", "G", "Ab"];
    readonly name: string;
    readonly tonic: string;
    readonly isMinor: boolean = false;
    readonly notes: string[];

    constructor (scaleName: string) {
        // validate scale name and capture components
        let match = Scale.regex.match(scaleName);
        if(match === null) {
            throw new RangeError('Invalid scale name.')
        };
        this.name = match[0];
        this.tonic = match[1];
        let intervals = Scale.majorSemiToneIntervals;
        if(match[2].length === 1) {
            this.isMinor = true;
            intervals = Scale.minorSemiToneIntervals;
        }

        // rotate the allNotes array
        let notes = Scale.allNotes;
        let index = notes.indexOf(this.tonic);
        if (index !== 0) {
            let notes = notes.slice(index, notes.length)
                             .concat(notes.slice(0, index));
        }

        // build notes for scale based on intervals;
        this.notes.push(notes[0]);
        noteIndex = 0;
        intervalIndex = 0;
        while (intervalIndex < intervals.length) {
            this.notes.push(notes[noteIndex]);
            noteIndex = noteIndex + intervals[intervalIndex];
            intervalIndex++;
        }
    }
}

// usage
let scale = new Scale('C');
let notesInScale = scale.notes;

Is this more code?  Yes.  But, this code is more reusable, less fragile, and does not pollute the global namespace as your current code examples do.  All logic is encapsulated within the classes.


Limit fgets input to up to a certain number of characters This question is an extension of this other question from Stackoverflow.
The objective is to limit the input of characters read by fgets to up to a certain number of characters. And in the following code, that I've come up with as a solution, we are working with a limit of 10 characters as an example:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char v[12];

    printf("Type a word with up to 10 chracters:\n");
    //Loop checks if fgets succeeded and if there is '\n' in the string:
    while (!fgets(v, 12, stdin) || strcspn(v, "\n") == 11){
        if(feof(stdin)) {
             printf("Error: End of file reached.\n");
             exit(EXIT_FAILURE);
        }
        printf("Error: The word is longer than 10 characters, try again.\n");
        for(int ch=getchar(); ch != '\n' && ch != EOF; ch=getchar());
        printf("Type a word with up to 10 chracters:\n");
    }
    v[strcspn(v, "\n")] = '\0';

    printf("%s\n", v);

    return 0;
}

It works as intended. However @chux-ReinstateMonica has pointed out that there may still be corner weaknesses and possible improvements to be made to this solution.
So, how can this code/solution be improved?

This would obviously be better as a function, so we can call with different parameters.
Instead of repeating the constant 12 in the fgets() call, we could simply use sizeof v.  Then it remains consistent if we change v.
Instead of strcspn() with only one character, I'd prefer strchr().  Conveniently, that returns a null pointer if not found, so we don't need to calculate the length to search.  And we shouldn't repeat the search to replace the newline with null character.
Error messages should go to stderr, not stdout.
We can skip the rest of line with a simple scanf("%*[^\n]") (note the * to suppress assignment).  That would replace the ch loop.