Increasing speed of BWT inverse I think understanding basic data compression and pattern finding / entropy reduction primitives is really important. Mostly the basic algorithms (before the many tweaks and optimizations are made) are really elegant and inspiring. What's even more impressive is how widespread they are, but perhaps also how little they are really understood except outside of people working in compression directly. So I want to understand.

I understand and have implemented the naive implementations of LZ77 (just find the maximal prefix that existed before the current factor) and LZ78 (just see if we can extend a factor that occurred before at least twice, or we make a new record and start a new factor). I also understand the naive version of Burrows-Wheeler Transform (maintain the invariant that the first column is sorted, and keep adding that column and resorting until the matrix is square).

I also understand why all these (parts of) compression algorithms work:

LZ77 asymptotically optimal since in the long term and with an infinite window all factors that exist are composed of prefixes earlier in the input which LZ77 can find.
LZ78 is also pretty good since if a factor occurs at least once before it can be compressed the second time, so long as it is not a suffix of another factor found earlier.
BWT, by grouping same letters on the left hand side (of the matrix), and finding patterns in the preceding letters in the right hand side, can exploit bigram repetitions, recursively.

The BWT code below works, but the inverse is not efficient. What are the optimizations, and how can I understand why they work?

BWT

def rot(v):
        return v[-1] + v[:-1]

def bwt_matrix(s):
        return sorted(reduce(lambda m,s : m + [rot(m[-1])],xrange(len(s)-1),[s]))

def last_column(m):
        return ''.join(zip(*m)[-1])

def bwt(s):
        bwtm = bwt_matrix(s)
        print 'BWT matrix : ', bwtm
        return bwtm.index(s), ''.join(last_column(bwtm))

def transpose(m):
        return [''.join(i) for i in zip(*m)]

def ibwt(s):
        return reduce(lambda m, s: transpose(sorted(transpose([s]+m))),[s]*len(s),[])

s = 'sixtysix'
index, bwts = bwt(s)
print 'BWT, index : ', bwts, index
print 'iBWT : ', ibwt(bwts)

BWT output

BWT matrix :
ixsixtys
ixtysixs
sixsixty
sixtysix
tysixsix
xsixtysi
xtysixsi
ysixsixt
BWT, index :  ssyxxiit 3
iBWT :
ixsixtys
ixtysixs
sixsixty
sixtysix
tysixsix
xsixtysi
xtysixsi
ysixsixt

Which is correct.

LZ77

def lz77(s):
        lens = len(s)
        factors = []
        i = 0
        while i < lens:
                max_match_len = 0
                current_word = i
                j = 0
                while j < lens-1:
                        if current_word >= lens or s[current_word] != s[j]:
                                j -= (current_word - i)
                                if current_word - i >= max_match_len:
                                        max_match_len = current_word - i
                                if current_word >= lens:
                                        break
                                current_word = i
                        else:
                                current_word += 1
                        j += 1
                if max_match_len > 1:
                        factors.append(s[i:i+max_match_len])
                        i += max_match_len
                else:
                        factors.append(s[i])
                        i += 1
        return ','.join(factors)

LZ78

def lz78(s):
        empty = ''
        factors = []
        word = empty
        for c in s:
                word += c
                if word not in factors:
                        factors.append(word)
                        word = empty
        if word is not empty:
                factors.append(word)
        return ','.join(factors)

Correct outputs against 7th Fibonacci word:

LZ77( abaababaabaab ): a,b,a,aba,baaba,ab
LZ78( abaababaabaab ): a,b,aa,ba,baa,baab

1. Introduction

The only actual question you asked is about how to make the inverse Burrows–Wheeler transform go faster. But as you'll see below, that's plenty for one question here on Code Review. If you have anything to ask about your LZ77 and LZ78 implementations, I suggest you start a new question.

2. A bug

First, the output of the function ibwt doesn't match the example output in the question:

>>> from pprint import pprint
>>> pprint(ibwt('ssyxxiit'))
['iisstxxy',
 'xxiiysts',
 'stxxsiyi',
 'iystixsx',
 'xsiyxtis',
 'tixssyxi',
 'yxtiissx',
 'ssyxxiit']

You should always prepare your question by copying and pasting input and output from source files and from an interactive session, rather than typing in what you think it should be. It's easy to introduce or cover up mistakes if you do the latter.

So it looks as if there is a missing transpose:

>>> pprint(transpose(ibwt('ssyxxiit')))
['ixsixtys',
 'ixtysixs',
 'sixsixty',
 'sixtysix',
 'tysixsix',
 'xsixtysi',
 'xtysixsi',
 'ysixsixt']

3. Avoiding transpositions

With that bug fixed, let's see how long the function takes on a medium-sized amount of data:

>>> import random, string
>>> from timeit import timeit
>>> s = ''.join(random.choice(string.printable) for _ in range(1024))
>>> t = bwt(s)
>>> timeit(lambda:ibwt(t[1]), number=1)
49.83987808227539

Not so good! What can we change? Well, an obvious idea is to cut out all those calls to transpose. The function ibwt transposes the matrix in order to sort it, and then transposes it back again each time round the loop. By keeping the matrix in transposed form throughout, it would be possible to avoid having to call transpose at all:

def ibwt2(s):
    """Return the inverse Burrows-Wheeler Transform matrix based on the
    string s.

    >>> ibwt2('SSYXXIIT')[3]
    'SIXTYSIX'

    """
    matrix = [''] * len(s)
    for _ in s:
        matrix = sorted(i + j for i, j in zip(s, matrix))
    return matrix

That simple change results in a big improvement:

>>> s = ''.join(random.choice(string.printable) for _ in range(1024))
>>> t = bwt(s)
>>> timeit(lambda:ibwt2(t[1]), number=1)
0.9414288997650146

4. Aside on programming style

Something that's perhaps worth mentioning at this point is that you seem quite keen on transforming code so as to use a functional style (for example in this question, where you wanted to express a loop using reduce). Transforming code into pure functional form is an excellent intellectual exercise, but you have to be aware of two problems that often arise:

Pure functional programs can easily end up doing a lot of allocation and copying. For example, it is often tempting to transform your data into a format suitable for passing in to a function (rather than transforming your function so that it operates on the data you have). Thus in ibwt it is convenient to call sorted on the data in row-major order, but convenient to append a new instance of the string s in column-major order. In order to express both of these operations in the most convenient way, the function has to transpose the matrix back and forth, and since it do so functionally, each transposition has to copy the whole matrix.
Pursuit of pure functional style often results in tacit or point-free programming where variable names are avoided and data is routed from one function to another using combinators. This can seem very elegant, but variable names have two roles in a program: they don't just move data around, they also act as mnemonics to remind programmers of what the data means. Point-free programs can end up being totally mysterious because you lose track of exactly what is being operated on.

Anyway, aside over. Can we make any more progress on the inverse Burrows–Wheeler transform?

5. An efficient implementation

If you look at what the inverse Burrows–Wheeler transform does, you'll see that it repeatedly permutes an array of strings (by sorting them). The permutation is exactly the same at each step (exercise: prove this!). For example, if we are given the string SSYXXIIT, then at each step we apply the permutation SSYXXIIT → IISSTXXY, which (taking note of where repeated letters go) is the permutation 01234567 → 56017342.

This observation allows us to reconstruct a row of the matrix without having to compute the whole matrix. In this example we want to reconstruct row number 3. Well, we know that the final matrix looks like this:

I.......
I.......
S.......
S*......
T.......
X.......
X.......
Y.......

so the first element of the row is S. What's the next letter of this row (marked with *)? Where did this come from? Well, we know that the last step of the transform must have looked like this:

S0......         I5......
S1......         I6......
Y2......    ->   S0......
X3......    ->   S1......
X4......    ->   T7......
I5......    ->   X3......
I6......         X4......
T7......         Y2......

So the * must have come from row 1 (which is the image of 3 under the permutation), and so it must be I (which is element number 1 of the sorted string IISSTXXY).

We can follow this approach all the way along the row. Here's an implementation in Python:

def ibwt3(k, s):
    """Return the kth row of the inverse Burrows-Wheeler Transform
    matrix based on the string s.

    >>> ibwt3(3, 'SSYXXIIT')
    'SIXTYSIX'

    """
    def row(k):
        permutation = sorted((t, i) for i, t in enumerate(s))
        for _ in s:
            t, k = permutation[k]
            yield t
    return ''.join(row(k))

Let's check that works:

>>> ibwt3(3, 'SSYXXIIT')
'SIXTYSIX'
>>> s = ''.join(random.choice(string.printable) for _ in range(1024))
>>> t = bwt(s)
>>> ibwt3(*t) == s
True

and is acceptably fast:

>>> timeit(lambda:ibwt3(*t), number=1)
0.0013821125030517578

(If you compare my ibwt3 to the sample Python implementation on Wikipedia you'll see that mine is not only much simpler, but also copes with arbitrary characters, not just bytes in the range 0–255. So either I've missed something important, or the Wikipedia article could be improved.)


Sums of some array elements I'm doing an archived MOOC at the moment which introduces Ruby programming.
There are some assingments, yet no solutions and since the MOOC is over no one will correct those (+ the forum is down)

I'm totally new to Ruby (background in Java) and asking for some hints on my solution to the following task (my solution under the task):

  Define a method sum which takes an array of integers as an argument and returns the sum of its elements. For an empty array it should return zero.

def sum(array)
  array[0] = array.pop + array[0];
  sum(array) until array.length == 1
  array.first
end

  Define a method max_2_sum which takes an array of integers as an argument and returns the sum of its two largest elements. For an empty array it should return zero. For an array with just one element, it should return that element.

def max_2_sum(a)
  case a.length
    when 0
      return 0
    when 1
      return a.first
    else
      return (a.sort!.pop)+(a.sort!.pop)
  end
end

I think this is pretty verbose, yet I do not know how to solve that better

  Define a method sum_to_n? which takes an array of integers and an additional integer, n, as arguments and returns true if any two distinct elements in the array of integers sum to n. An empty array or single element array should both return false.

def sum_to_n?(array, val)
  cartesian = array.product(array).select! { |c| c[0]+c[1] == val }
  not cartesian.empty?
end

I like this :)

Ruby can be an extremely concise language, where your programs are almost already written for you:

def sum(array)
    array.inject(0, :+)
end

Where the docs say:

  inject { |memo, obj| block } → obj

  Combines all elements of enum by applying a binary operation,
  specified by a block or a symbol that names a method or operator.

In fact reading the docs can go a long way in shortening your programs.

Reading the docs for Array tells us that sorting is built-in and last (the twin of first) are too, also, we just wrote a handy sum function.

def max_2_sum(array)
    sum(array.sort.last(2))
end

This is slower than needed, that is O log n instead of O n but it may be optimized iff it becomes a performance bottleneck (improbable).

Your last function is indeed nice, but the assignment was not necessary and you did not use the handy built-in any?

def sum_to_n?(array, val)
    array.product(array).any? {|couple| sum(couple) == val}
end


Keeping track of people's relationships using a people relation table I am trying to track relationships among people. I came up with my own solution, but I'm wondering if there might be another way or better way of doing this. To keep it simplified, I'll post just the bare bones.

Let's say I have created the tables: person, person_relation, and people_relation for a MYSQL database using the following code:

DROP TABLE IF EXISTS person;
DROP TABLE IF EXISTS person_relation;
DROP TABLE IF EXISTS people_relation;

CREATE TABLE `person` (
    `id`            int(10) NOT NULL auto_increment primary key,
    `name`          varchar(32) NOT NULL,
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE `people_relation` (
    `id`            int(2) NOT NULL auto_increment primary key,
    `relation`      varchar(32)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE `person_relation` (
    `id`            int(10) NOT NULL auto_increment primary key,
    `parent_id`     int(10) NOT NULL,
    `child_id`      int(10) NOT NULL,
    `relation_id`   int(10) NOT NULL,
    FOREIGN KEY (`parent_id`) REFERENCES person(`id`),
    FOREIGN KEY (`child_id`) REFERENCES person(`id`),
    FOREIGN KEY (`relation_id`) REFERENCES people_relations(`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

INSERT INTO `person` (`id`, `name`)
VALUES
(1, 'John Jr'), (2, 'Jane'), (3, 'Mark'), (4, 'John'), (5, 'Betty');

INSERT INTO `people_relation` (`id`, `relation`)
VALUES
(1, 'HUSBAND'), (2, 'WIFE'), (3, 'FATHER'), (4, 'MOTHER'), (5, 'SON'), (6, 'DAUGHTER'), (7, 'GRANDFATHER'),
(8, 'GRANDMOTHER'), (9, 'GRANDSON'), (10, 'GRANDDAUGHTER'), (11, 'GREAT GRANDFATHER'),
(12, 'GREAT GRANDMOTHER'), (13, 'GREAT GRANDSON'), (14, 'GREAT GRANDDAUGHTER'), (15, 'GODFATHER'),
(16, 'GODMOTHER'), (17, 'GODSON'), (18, 'GODDAUGHTER'), (19, 'BROTHER'), (20, 'SISTER'),
(21, 'MOTHER-IN-LAW'), (22, 'FATHER-IN-LAW'), (23, 'DAUGHTER-IN-LAW'), (24, 'SON-IN-LAW');

INSERT INTO `person_relation` (`id`, `parent_id`, `child_id`, `relation_id`)
VALUES
(1, 1, 2, 1), (2, 1, 3, 3), (3, 1, 4, 5), (4, 1, 5, 5), (5, 2, 1, 2), (6, 2, 3, 4), (7, 2, 4, 23),
(8, 2, 5, 23), (9, 3, 1, 5), (10, 3, 2, 5), (11, 3, 4, 9), (12, 3, 5, 9), (13, 4, 1, 3), (14, 4, 2, 22),
(15, 4, 3, 7), (16, 4, 5, 1), (17, 5, 1, 4), (18, 5, 2, 21), (19, 5, 3, 8), (20, 5, 4, 2);

So, in my example, I am capturing 5 people, all family related, where I make connections to each of them with a unique relation: spoken plainly, a John Jr. has listed: a wife, a son, a mother, and a father; and Jane has a husband, a son, a father-in-law, and a mother-in-law, etc.

The records with 5 people end up being 20 records in the person_relation table. If I add, let's say a new daughter for John Jr. and Jane. The table will then have presumably 30 records to account all the relations.

Does this sound about right? This problem seems like it could explode to be a very large table. Do you know maybe a better way to do this? Or do you think I am on the right track?

It seems fine for me for generic cases. Later you might need some denormalization or caching if it's too slow but it really depends on the usage. (If you have any special requirement you should share it, edit the question, please.)

Four things to consider:

varchar(32) for name could be too small.
Consider unique indexes for the person_relation(parent_id, child_id, relation_id) triplet and the people_relation.relation attribute. For example:

Currently, you can insert the same relation twice:

mysql> select * FROM person_relation;
Empty set (0.00 sec)

mysql> INSERT INTO `person_relation` (`parent_id`, `child_id`, `relation_id`)
    VALUES (1, 2, 1);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `person_relation` (`parent_id`, `child_id`, `relation_id`)
    VALUES (1, 2, 1);
Query OK, 1 row affected (0.00 sec)

mysql> select * FROM person_relation;
+----+-----------+----------+-------------+
| id | parent_id | child_id | relation_id |
+----+-----------+----------+-------------+
| 23 |         1 |        2 |           1 |
| 24 |         1 |        2 |           1 |
+----+-----------+----------+-------------+
2 rows in set (0.00 sec)

An unique index could prevent that:

CREATE UNIQUE INDEX person_relation_uniq_idx
    ON person_relation
    (parent_id, child_id, relation_id);

For example:

mysql> DELETE FROM person_relation;
Query OK, 2 rows affected (0.00 sec)

mysql>         CREATE UNIQUE INDEX person_relation_uniq_idx
    ->             ON person_relation
    ->             (parent_id, child_id, relation_id);
Query OK, 0 rows affected (0.31 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> INSERT INTO `person_relation` (`parent_id`, `child_id`, `relation_id`)
    VALUES (1, 2, 1);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `person_relation` (`parent_id`, `child_id`, `relation_id`)
    VALUES (1, 2, 1);
ERROR 1062 (23000): Duplicate entry '1-2-1' for key 'person_relation_uniq_idx'

mysql> SELECT * FROM person_relation;
+----+-----------+----------+-------------+
| id | parent_id | child_id | relation_id |
+----+-----------+----------+-------------+
| 25 |         1 |        2 |           1 |
+----+-----------+----------+-------------+
1 row in set (0.00 sec)

people_relation.relation might not be NULL.
people_relation and person_relation are easy to mix up, these names are too similar to each other. I'd rename people_relation to relation_type.


Logger which writes asynchronously to file from multiple threads I have written a simple logger, AsyncFile, which asynchronously writes data to a file. Since data is going to be written very often (E.g. 10 writes per 30 milliseconds from different threads, my system has a 30ms sync time), I would like to know if:

1. The design makes sense att all? Am I missing something obvious?
2. If the logger is fairly optimal, e.g. that no unneccessary copying takes place.

Basically, my idea is to write data to a shared buffer(m_queue), then copy that data to a tempBuffer from which I then write to a file.

The method write can be called from multiple threads.

I have tested this logger and it seems to work fine, but like all problems involving shared resources, it is hard to know if it is well-designed until you have tried it for a good amount of time.

AsyncFile.h:

#pragma once

#include <cstdint>
#include <cstddef>
#include <array>
#include <mutex>
#include <condition_variable>

class AsyncFile
{
public:

   AsyncFile();

   void write(std::array<char,40>& buffer);

   void done();

private:

    std::array<char, 160> m_queue;

    std::array<char, 160> tempBuffer;

    std::mutex queue_mutex;

    std::condition_variable cv;

    size_t counter = 0;

    bool readyToCopy = false;

    bool finished = false;

    void logger_thread();

}; // class AsyncFile

AsyncFile.cpp:

#include <thread>
#include <fstream>
#include <string.h>
#include <iostream>
#include <chrono>

void AsyncFile::logger_thread()
{
    FILE* file = fopen("test_file.bin", "wb");

    while(!finished) // Pass "finished" as a parameter by ref? Protect by a mutex?
    {
        std::unique_lock<std::mutex> lk(queue_mutex);
        cv.wait(lk, [&]{return readyToCopy;});

        std::copy(m_queue.begin(), m_queue.end(), tempBuffer.begin());

        readyToCopy = false;
        lk.unlock();

        // Now write to file from the temporary buffer:
        fwrite(&tempBuffer, sizeof(char), sizeof(tempBuffer), file);
    }
    fclose(file);
}

AsyncFile::AsyncFile()
{
      std::thread m_worker(&AsyncFile::logger_thread, this);
      m_worker.detach(); // let the worker thread live on its own.
}

void AsyncFile::done()
{
    finished = true;
}

void AsyncFile::write(std::array<char, 40>& buffer) // 40 should probably be a
                                                    // configurable parameter.
{
   std::lock_guard<std::mutex> guard(queue_mutex);
   std::copy(buffer.begin(), buffer.end(), m_queue.begin() + counter);
   if (counter == 120) // fill the queue, 40 char each time, until we have 160 chars in total. Then
                       // notify the writing thread we are ready.
   {
      counter = 0;
      readyToCopy = true;
      cv.notify_one();
   }
   else
   {
      counter += 40;
   }
}

To make a fast logger you need to

minimise the use of mutexes.
detach the logging from the writing.
minimise copying
pre-alloc the buffers

no allocs during logging.

make a ring buffer

fixed number of logging
decide what should happen if its full
slightly slower using a dequeue with minimises allocs

use atomic indexes to the (ring) buffer

if your system if fully loaded, you have to log often use the cv or wait until the logger thread gets scheduled by the OS.
use the cv.notice_one where the index is updated if the front is sufficient in front of the back end.

So a few of the things that are issues

The logger_thread blocks further logging while it writes.
The write blocks other threads logging

Running into a mutex that is taken causes a task switch, typically  taking from 1000ns to 22000ns on a x86, nearer the lower if its started again on the same hardware thread.


Find valid triples for a sorted list of integers (part 2) Have some ideas to improve code from this discussion (Find valid triples for a sorted list of integers) and post new code in a new post.

The new idea is to try to remember where low bound searched last time, and when doing the search, only search from the lower bound where last search is satisfied, since with j increase each time, the 3rd dimension of satisfied triple could only increase. More specifically, these two lines,

    #upperBoundIndex = findSum(numbers, j+1, numbers[i]+numbers[j]) # previous code
    upperBoundIndex = findSum(numbers, upperBoundIndex, numbers[i] + numbers[j])

I'm working on a problem in which I have an input array, sorted positive unique integers, and have to try to find all possible triples \$(x,y,z)\$ which satisfy \$x+y>z\$ and \$x<y<z\$. For example, \$(1,2,3)\$ is not a valid triple since \$1+2\$ is not \$> 3\$, and \$(3,4,5)\$ is a valid triple since \$3<4<5\$ and \$3+4>5\$.

This code leverages binary search, and I'm wondering if this can be improved in terms of time complexity. Please also help to point out any code issues/bugs or improvement areas.

BTW, I am not using enumeration feature of Python since I want to keep j greater than i, and leverage the feature in my logics.

from __future__ import division

def findSum(numbers, startIndex, value):
    """
    find index whose value is less than input parameter value (as upper bound)
    ,and the greatest possible value possible
    :param numbers: sorted value to search, may contains duplicates
    :param startIndex: where to search from, inclusive
    :param value: upper bound to search
    :return: the index whose value is less than upper bound value
    """
    low = startIndex
    high = len(numbers) - 1
    while low <= high:
        mid = (low + high) // 2
        if numbers[mid] == value:
            while mid >= low and numbers[mid] == value:
                mid -= 1
            return mid if mid >= low else -1
        elif numbers[mid] > value:
            high = mid - 1
        else:
            low = mid + 1
    # while
    return low-1 if (low-1) >= startIndex else -1

def findTriagles(numbers):
    """
    :param numbers: could contains duplicate number, assume numbers are sorted
    :return: unique triples
    """
    results = set()
    for i in range(0, len(numbers)-2):
        upperBoundIndex=min(i+2, len(numbers)-1)
        for j in range(i+1, len(numbers)-1):
            #upperBoundIndex = findSum(numbers, j+1, numbers[i]+numbers[j]) # previous code
            upperBoundIndex = findSum(numbers, upperBoundIndex, numbers[i] + numbers[j])
            if upperBoundIndex != -1:
                for k in range(j+1, upperBoundIndex+1):
                    results.add((numbers[i],numbers[j],numbers[k]))

    return results

if __name__ == "__main__":
    #print findTriagles([4,5,6,7]) # output, set([(4, 6, 7), (4, 5, 7), (4, 5, 6), (5, 6, 7)])
    print findTriagles([4, 4, 6, 7]) # output, set([(4, 4, 6), (4, 4, 7), (4, 6, 7)])

(I won't comment on the actual algorithm, just on the coding style.)

Overall, this feels pretty ok and standard Python style.

Some remarks:

remove commented-out code before going "live" (live here meaning, submitting to CR).
make sure your lines don't exceed 80 characters.
That will have the added convenience that there'll likely be no horizontal scrollbar for the code block here, making things overall easier to read.
I like the from __future__ import division, especially since the only division in the code is actually integer divison, and now is explicit with //.
Bonus: add from __future__ import print_function, add parentheses to yourprint` statement at the bottom and your code will be "generic" Python, not major version 2 or 3 specific.
(My preferred approach is to code Python 3, and then if necessary, refactor things to be Python 2 compatible. Start from the future, not from the past.)
the lower-first-CamelCase style is not Pythonic. CamelCase is used for classes, but functions and variable names are usually all lower case, with underscores as deemed necessary for readability.
(NB: you probably want to use the word "triangles", with an "n" in there, instead of "triagles". Or use e.g. find_triplets, since that's in your doc-string description.)
the quadruple nesting in findTriagles is about the limit of nesting (for-loop within an if-statement within a for-loop within a for-loop), but since the function is really short, it's probably ok. When there's a lot more code in any of these indented parts, consider moving a part to a separate function.
There is no general document doc-string (describing the purpose of the code), and the doc-string for findTriagles is missing its initial line/sentence: it jumps straight into the parameter description. findSum does this better.
findSum is an odd name: I don't see any sum calculation there. find_max_index or similar might be better.
for consistency: add space around the equal sign in upperBoundIndex=min(i+2, len(numbers)-1).


Shortening list of arguments to some kind of a variadic function If you look at ImportAndPreload method, it looks bad because:
MovingAverageConvergenceDivergence, StochasticRSI, RelativeStrengthIndex and ExponentialMovingAverage. They are all indicators, they all inherit from IndicatorBase. What would happen if I wanted to pass a few more indicators? There would be 10 indicators passed by arguments, which is annoying and it's against S.O.L.I.D. Is there a way to make that method like a variadic function in C++ and pass infinite amount of indicators. By the way, as you can see below, IndicatorBase is generic, which prevents params IndicatorBase<???>[] args.
For example: ImportAndPreload(symbol, interval, macd, stoch, rsi, ema, ...)
I'm also open for other ideas.
MovingAverageConvergenceDivergence macd = new MovingAverageConvergenceDivergence(12, 26, 100);
StochasticRSI stoch = new StochasticRSI(14, 9, 3, 3);
RelativeStrengthIndex rsi = new RelativeStrengthIndex(20);
ExponentialMovingAverage ema = new ExponentialMovingAverage(20);

ImportAndPreload(symbol, interval, macd, stoch, rsi, ema);

// Abstract base class for all indicators:
public abstract class IndicatorBase<TInput, TOutput>
    where TInput: struct
    where TOutput : struct
{
    public abstract TOutput ComputeNextValue(TInput input);
    public abstract void Reset();
}

private void ImportAndPreload(string symbol, KlineInterval interval, MovingAverageConvergenceDivergence macd, StochasticRSI stoch, RelativeStrengthIndex rsi, ExponentialMovingAverage ema)
{
    // Import candles
    List<BinanceKline> candles = Client.GetKlines(symbol, interval, limit: 1000).Data.SkipLast(1).ToList();

    for (int i = 0; i < 3; i++)
    {
        List<BinanceKline> moreCandles2 = Client.GetKlines(symbol, interval, startTime: null, endTime: candles.First().OpenTime, limit: 1000).Data.SkipLast(1).ToList();
        candles.InsertRange(0, moreCandles2);
    }

    // Workaround in case it gets more bigger time to import candles
    List<BinanceKline> moreCandles = Client.GetKlines(symbol, interval, limit: 2).Data.SkipLast(1).ToList();
    candles.AddRange(moreCandles.ExceptUsingJsonCompare(candles));

    // Preload indicators
    for (int i = 0; i < candles.Count; i++)
    {
        macd.ComputeNextValue(candles[i].Close);
        stoch.ComputeNextValue(candles[i].Close);
        rsi.ComputeNextValue(candles[i].Close);
        ema.ComputeNextValue(candles[i].Close);
    }
}
```

This will depend on whether or not all of the indicators you're interested in passing have the same generic type arguments. If they do then iSR5's solution is the simplest.
If not then you'll need a more complicated solution. On one hand I notice that you're not using any of the outputs of ComputeNextValue; you're only providing inputs to the indicators. Then one possible solution would be to define an interface with the void counterpart of ComputeNextValue which only takes an input and produces no output:
public abstract class IndicatorBase<TInput, TOutput> : IIndicatorBase<TInput>
    where TInput : struct
    where TOutput : struct
{
    public abstract TOutput ComputeNextValue(TInput input);
    public abstract void Reset();

    void IIndicatorBase<TInput>.ComputeNextValue(TInput input) =>
         ((IndicatorBase<TInput, TOutput>)this).ComputeNextValue(input);
}

public interface IIndicatorBase<TInput>
    where TInput: struct
{
    void ComputeNextValue(TInput input);
}

Then ImportAndPreload can become this: (I'm not sure what BinanceKline is, but the input type you're supplying to each indicator is the type of BinanceKline.Close, so that'd be the generic type argument for IIndicatorBase)
private void ImportAndPreload(string symbol, KlineInterval interval, params IIndicatorBase<TypeOfBinanceKlineDotClose>[] indicators)
{
    ...

    // Preload indicators
    for (int i = 0; i < candles.Count; i++)
    {
        foreach (var indicator in indicators)
        {
            indicator.ComputeNextValue(candles[i].Close);
        }
    }
}

...

ImportAndPreload(symbol, interval, macd, stoch, rsi, ema);

This will support any indicator whose input is the type of BinanceKline.Close.


Creating a ModelBinder to Sanitize user input in HTML format I have a custom model binder which takes user input in HTML format, sanitize the HTML input by removing any script or XSS threat and returns the sanitized HTML string:

public class AllowAndSanitizeHtmlBinder : IModelBinder
{

    private HtmlSanitizer _htmlSanitizer = HtmlSanitizerFactory.CreateInstance();

    public object BindModel(ControllerContext controllerContext, ModelBindingContext bindingContext)
    {
        var request = controllerContext.HttpContext.Request;
        var name = bindingContext.ModelName;

        // get the un-validated user input in HTML format
        var unsanitizedMessageHtmlString = request.Unvalidated[name];

        // removed script or any XSS threat from user input
        return _htmlSanitizer.Sanitize(unsanitizedMessageHtmlString);
    }
}

I am using HtmlSanitizer Nuget package to do this. I need to configure this object and tell it to add "nofollow" to all the links.

So I have created HtmlSanitizerFactory to do this configuration:

public static class HtmlSanitizerFactory
{
    public static HtmlSanitizer CreateInstance()
    {
        var sanitizer = new HtmlSanitizer();
        sanitizer.PostProcessNode += (s, e) =>  (e.Node as IHtmlAnchorElement)?.SetAttribute("rel", "nofollow noreferrer");
        return sanitizer;
    }
}

I am not entirely happy with this code. The reason is, in the future, a developer may forget that HtmlSanitizerFactory should be used for instantiating HtmlSanitizer... so he would create his new ModelBinder and initialize the object like:

HtmlSanitizer _htmlSanitizer = new HtmlSanitizer();

This would introduce a bug because links won't be converted to "nofollow"

I think DI would have worked much better here, but I don't know how to inject a class into a custom ModelBinder

Developer gone 'rogue'

  I am not entirely happy with this code. The reason is, in the future, a developer may forget that HtmlSanitizerFactory should be used for
  instantiating HtmlSanitizer... so he would create his new ModelBinder
  ..

For this to happen, a developer has to dive in your code and deliberately change

private HtmlSanitizer _htmlSanitizer = HtmlSanitizerFactory.CreateInstance();

to

 private HtmlSanitizer _htmlSanitizer = new HtmlSanitizer();

He would probably have a good reason to. And if not, other developers in the team should review and challenge that change. After all, it's best practice to perform code reviews, typically with pull requests.

Test-Driven Development

You have introduced a dependency on a third-party class in your code. Generally, when providing such API code, you would like to reduce the hard dependencies to a minimum. What you could do, is use its interface IHtmlSanitizer instead. This allows for white-bow testing such as

string unsanitizedMessageHtmlString = ".."; // some input
IHtmlSanitizer sanitizer = Mock<IHtmlSanitizer>(); // using some mock method ..
sanitizer.AssertWasCalled(m => m.Sanitize(unsanitizedMessageHtmlString));

You could go a step further and refactor out the third-party dependency entirely by providing your own interface. An adapter class mapping the third-party interface to yours can than be provided in a different library if you wish interop with that API. I am not suggesting this is a must. You should decide which dependencies you want to include in your own API.

Regression

  But it is likely that a year from now, we need to developer a new model binder to sanitize a different HTML input. It is at that point
  that the developer could forget to initialize the sanitizer using the
  factory.

In the comments you stated you are worried for new developers to use that class in a wrong way, possibly introducing bugs. These bugs should become apparent when providing unit tests. With white-box tests you can check whether PostProcessNode was registered to. And with black-box tests you could easily verify the content of the sanitized string.

It also wouldn't hurt to provide a team Wiki with guidelines, do's and dont's for new developers to get acquainted with the conventions and avoidable regressions.

Dependency Injection

Instead of calling the factory to get an instance of HtmlSanitizer, you should use Dependency Injection. One way to do so is to have the dependency injected through the constructor.

public AllowAndSanitizeHtmlBinder(IHtmlSanitizer htmlSanitizer)
{
    _htmlSanitizer = htmlSanitizer;
}

You would typically have an Ioc container where you register the dependencies. I don't know enough about the IModelBinder's lifetime scope, so you may also want to register these to the container.

container.RegisterSingleInstance<IHtmlSanitizer>(HtmlSanitizerFactory.CreateInstance());

Resource Management

I don't like the third-party class HtmlSanitizer. The events are never cleared and the class does not implement IDisposable. It's a memory leak waiting to occur. You need to find a way to dispose these instances yourself and make sure to unsubscribe from:

 sanitizer.PostProcessNode += (s, e) =>  (e.Node
     as IHtmlAnchorElement)?.SetAttribute("red", "nofollow noreferrer");


Adding events to multiple markers in a Google map I was looking over questions related to setting up markers on a Google map, and though the following works perfectly fine for me, it was different from the other (and accepted) answers. I just wanted to see if I'm doing something incorrect, or just a different way.

Mine:

this references the marker, and you can pull any data you have associated with it simply by calling it within the loop that creates all of the markers.

google.maps.event.addListener(marker, "click", function(){
     infowindow.setContent(this.position.toString());
     infowindow.open(this.map, this);
});

Accepted:

 google.maps.event.addListener(marker, 'click', (function(marker, i) {
     return function() {
     infowindow.setContent(locations[i][0]);
     infowindow.open(map, marker);
    }
 })(marker, i));

Your code is definitely simpler, though I would not use it myself. There is no good reason to have an anonymous function, and if you have multiple markers, then you will have multiple clones of the same function. I would create a named function and use that function with addListener.

(I am assuming that infowindow is available to this function)

function setPositionAsContent(){
  infoWindow.setContent(this.position.toString());
  infoWindow.open(this.map, this);
}

google.maps.event.addListener(marker, "click", setPositionAsContent);


Router and solid principle I would like to know if my Routing system respects the solid principle ?
The system is simple, Router class contains the routes and returns the correct route and Route class represents a route, contains a path and an action to call. Router takes the Request class as a parameter in its constructor to try to respect the solid principle.

https://en.wikipedia.org/wiki/SOLID
https://guillaume-richard.fr/principe-solid-simplifies-avec-des-exemples-en-php/
ETC...........

I would like to know what's good and what isn't.
class Router
{
    private $request;
    private $routes = [];

    public function __construct(Request $request)
    {
        $this->request = $request;
    }

    public function get(string $path, string $action)
    {
        return $this->addRoute($path, $action, 'GET');
    }

    private function addRoute(string $path, string $action, string $method)
    {
        $route = new Route($path, $action);
        $this->routes[$method][] = $route;
        return $route;
    }

    public function run()
    {
        if(!isset($this->routes[$this->request->getMETHOD()])) {
            throw new RouterException('REQUEST_METHOD does not exist');
        }
        foreach ($this->routes[$this->request->getMETHOD()] as $route) {
            if ($route->match($this->request->getUri())) {
                return $route->call();
            }
        }
        throw new RouterException("La page demandée est introuvable.");
    }
}

class Route
{
    private $path;
    private $action;
    private $matches;
    private $parameters = [];

    public function __construct(string $path, string $action)
    {
        $this->path = trim($path, '/');
        $this->action = $action;
    }

    public function where(string $param, string $regex)
    {
        $this->parameters[$param] = str_replace('(', '(?:', $regex);
        return $this;
    }

    public function match(string $requestUri)
    {
        $requestUri = trim($requestUri, '/');
        $path = preg_replace_callback('#:([\w]+)#', [$this, 'paramMatch'], $this->path);
        $regex = "#^$path$#";
        if (preg_match($regex, $requestUri, $matches)) {
            array_shift($matches);
            $this->matches = $matches;
            return true;
        } else {
            return false;
        }
    }

    private function paramMatch(array $match)
    {
        if (isset($this->parameters[$match[1]])) {
            return '(' . $this->parameters[$match[1]] . ')';
        }
        return '([^/]+)';
    }

    public function call()
    {
        $parameters = explode('@', $this->action);
        $controller = "Src\\Controller\\" . $parameters[0];
        $controller = new $controller();
        $method = $parameters[1];
        return call_user_func_array([$controller, $method], $this->matches);
    }
}

Router should not accept request object in constructor. You will need a new router for each request.
I know PHP spawns a new process for each request so it gets created for each request anyway. But in tests it may be different...
And anyway it doesn't make much sense to hide the request inside the router from the logical point of view.
Hiding a constructor dependency means that the dependency is an implementation detail. And sure you agree that request is not just an implementation detail of a router. It is the input for routing.
Also the route should not be aware of how to determine controller class and surely it doesn't want to know or, and thats even worse, force no constructor arguments for all controllers. There should be a controller factory that knows the details.
And you don't want to pass controller factory to every route. So maybe instead, route should just define path mapping and controller factory should take a route as an input. Router would then pass the matched route to the controller factory.
Another thing is that the addRoute method doesn't really belong on a router, it belong on a router builder. You register routes on the builder and finalize by calling it's createRouter method.
What's entirely missing in your code is an "application" class - that's the one where run method belongs, not the router, router should really have a method that accepts request object and returns response object. Application might have a request factory, the router and some kind of response emitter which takes the response object returned by router and send it's representation to the client.


Mapping a textual method name to a function My program (a daemon hosting a Minecraft server) exposes a D-Bus interface to allow interaction with the server from other processes. To that end, and to avoid a chain of repetitive conditionals in the invocation handler, I'm using a map of Glib::ustring keys (the method invoked) to std::bind-created function objects (code abbreviated slightly; see end of question for link to full source):

std::unordered_map<Glib::ustring, std::function<void(Minecraftd1*, const Glib::RefPtr<Gio::DBus::MethodInvocation>&)>> handlerMap;
std::once_flag handlerMapInitFlag;

Minecraftd::Minecraftd1() {
    // Only initialise the method name/handler method map once. Placeholders are used for the "this" and invocation arguments.
    std::call_once(handlerMapInitFlag, []{
        using namespace std::placeholders;
        handlerMap.emplace("SaveAll", std::bind(&Minecraftd1::handleSimpleCommand, _1, _2, "save-all"));
        // Omitted: two similar mappings
        handlerMap.emplace("Stop", std::bind(&Minecraftd1::handleSimpleCommand, _1, _2, "stop"));
    });
}

// Called by the Glib main loop when a D-Bus method call is received
void Minecraftd1::onMethodCall(const Glib::ustring &methodName, const Glib::RefPtr<Gio::DBus::MethodInvocation> &invocation) {
    auto handler = handlerMap.find(methodName);
    if(handler != handlerMap.end()) {
        handler->second(this, invocation);
    } else {
        invocation->return_error(Gio::DBus::Error{Gio::DBus::Error::UNKNOWN_METHOD, "Method does not exist."});
    }
}

void Minecraftd1::handleSimpleCommand(const Glib::RefPtr<Gio::DBus::MethodInvocation> &invocation, std::string command) const {
    // Write value of command to standard input (rebound to a pipe)
    invocation->return_value(Glib::VariantContainerBase{});
}

I realise that, for the current set of methods, I could just as well use a map of methodName to the command string to write to the file descriptor, but this way of doing it allows me to create more complex handlers for commands that require more than just a simple pass-through without having to change the execution flow of onMethodCall. Of course, if a handler method requires access to e.g. the parameters of the D-Bus invocation, I would need to modify the signature of all the handlers to accept it as an argument, with a corresponding additional placeholder in the std::bind call.

Is this a good way of going about runtime dispatch based on a string identifier, or am I barking up the wrong tree here? Is there any way that it could be improved further?

The full source code may be found on GitHub.

std::call_once is an interesting tool, but there are alternatives built into the language: namely, you can use the Immediately-Invoked Function Expression (IIFE) borrowed straight from JavaScript and made usable thanks to C++11 lambda functions.

Here is how you can use it to initialize handlerMap:

std::unordered_map<
    Glib::ustring,
    std::function<void(Minecraftd1*, const Glib::RefPtr<Gio::DBus::MethodInvocation>&)>
> handlerMap = []{
    using namespace std::placeholders;
    std::unordered_map<
        Glib::ustring,
        std::function<void(Minecraftd1*, const Glib::RefPtr<Gio::DBus::MethodInvocation>&)>
    > initMap;
    initMap.emplace("SaveAll", std::bind(&Minecraftd1::handleSimpleCommand, _1, _2, "save-all"));
    initMap.emplace("Stop", std::bind(&Minecraftd1::handleSimpleCommand, _1, _2, "stop"));
    return initMap;
}();

Agreed, it looks a bit messy with the big std::unordered_map type, but you could probably create a type alias to get rid of the syntactic mess. Even if you dont typedef the whole thing, I guess that exposing the type of std::function<void(Minecraftd1*, const Glib::RefPtr<Gio::DBus::MethodInvocation>&)> could be an interesting idea.

Alterntively, there is even better than IIFE: in your can, you can use initializer lists to achieve what you're trying to do:

std::unordered_map<
    Glib::ustring,
    std::function<void(Minecraftd1*, const Glib::RefPtr<Gio::DBus::MethodInvocation>&)>
> handlerMap = {
    { "SaveAll", std::bind(&Minecraftd1::handleSimpleCommand, std::placeholders::_1, std::placeholders::_2, "save-all") },
    { "Stop",    std::bind(&Minecraftd1::handleSimpleCommand, std::placeholders::_1, std::placeholders::_2, "stop") }
};

But it means that you have to explicitly write std::placeholders:: everywhere if you don't want using std::placeholders; to leak into the outer namespace. In other words, you have to choose which solutions seems to best convey your idea while not bearing too much syntactic noise.


Designing stack and queue from scratch in C As a beginner and curious guy I'm interested in implementing data structures and algorithms from scratch. Here's my implementation of Stack and Queue, the most fundamental data structures.

Are there are any mistakes/ memory leaks in the code that I have missed? How I can improve my implementation.

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

typedef struct NODE {
    int data;
    struct NODE *next_node;

    } NODE;

NODE *check_queue(NODE *head);
NODE *check_stack(NODE *head);
void push_node(NODE **head, int value);
void enqueue_node(NODE **head, int value, NODE **tail);
int  pop(NODE **s_head);
int  dequeue(NODE **q_head);
void print_stack(NODE *head);
void print_queue(NODE *head);
void free_memory(NODE **head);

int main(){

    NODE *Q_head = NULL;
    NODE *Q_tail = NULL;
    NODE *S_head = NULL;
    /*operations here*/

    return 0;
}

/*----- check functions for queue and stack if empty-----------*/

NODE *check_queue(NODE *head){
    return head;
}

NODE *check_stack(NODE *head){
    return head;
}

/*--------------------------------------------------------------*/

void push_node(NODE **head, int value){

    NODE *cache;
    cache = (NODE *) malloc(sizeof(NODE));
    cache->data = value;
    /*first commit / allocate a new head*/

    if ((*head) == NULL) {
        cache->next_node = NULL;
        (*head) = cache; /*assign the cache to head head*/
    }

    else {
        /*point to the previous head*/
        cache->next_node = (*head);
        (*head) = cache;
    }
}

void enqueue_node(NODE **head, int value, NODE **tail) {

    NODE *cache;
    cache = (NODE *) malloc(sizeof(NODE));
    cache->data = value;
    cache->next_node = NULL;

    if ((*head) == NULL && (*tail) == NULL) {
        (*head) = cache; /*assign the cache to head*/
        /*now assign tail the job as a cachet head and extends the queue*/
        (*tail) = (*head);
    }

    else {
        /*now tail is the representative of head and extened the queue*/
        (*tail)->next_node = cache;
        (*tail) = cache;
    }
}

int pop(NODE **s_head){

    if(check_stack((*s_head)) == NULL){
        printf("Stack is empty ! ! !\n");
        return -1;
    }

    else {
        /*put next head into a cache, free present head, take next head to present head*/
        NODE *cache ;
        cache = (*s_head)->next_node;
        int popped_value = (*s_head)->data;
        free((*s_head));
        (*s_head) = cache;
        return popped_value;
    }
}

int dequeue(NODE **q_head){

    if(check_queue((*q_head)) == NULL){
        printf("queue is empty ! ! !\n");
        return -1;
    }

    else {
        /*ditto of stack as we've got queue sequence*/

        NODE *cache ;
        cache = (*q_head)->next_node;
        int dequeued_value = (*q_head)->data;
        free((*q_head));
        (*q_head) = cache;
        return dequeued_value;
    }
}

void print_stack(NODE *head){

    while (head) {

        printf(" %d \n", head->data);
        printf(" |\n");
        head = head->next_node;
    }

    /*for further assurance*/
    if ( head == NULL){
        printf("NULL\n");
    }

    printf("\n");
}

void print_queue(NODE *q_head){

    while (q_head) {

        // printf(" %d  -> ", head->next_node);
        printf(" %d  -> ", q_head->data);
        q_head = q_head->next_node;
    }
    /*for further assurance*/
    if ( q_head == NULL){
            printf("NULL\n");
    }

    printf("\n");
}

void free_memory(NODE **head){
    NODE *cache_head;

    while ((*head)) {

        /*assign next head to the cache*/
        cache_head = (*head)->next_node;
        free((*head));
        (*head) = cache_head;
    }

    printf("memory release complete !!! \n");
}

casting and malloc

Unnecessary casting is generally frowned upon.  malloc returns a void*, so you don't need to cast it when you're assigned it.

cache = (NODE *) malloc(sizeof(NODE));

can just be

cache = malloc(sizeof(NODE));

Bug

You've got a bug in your dequeue function.  It doesn't update tail, which means that if you empty the queue, then start adding to it again you get errors.

enqueue_node(&Q_head, 1, &Q_tail);
printf("%d\n", dequeue(&Q_head));
enqueue_node(&Q_head, 1, &Q_tail);
printf("%d\n", dequeue(&Q_head));

Results in:

1
queue is empty ! ! !
-1

naming

It's a little odd that your push/enqueue methods have have a _node postfix, but your pop/dequeue methods don't.  I'd pick one and stick to it.

heads and tails

I'd rather see the head and tail of the queue wrapped up together in a queue structure.  This means that you only have to pass one parameter (the queue) into your enqueue/dequeue.  It also means that if you decide to change the way you implement the queue, your clients aren't impacted.

Are Queues Stacks?

As you've implemented it, it's possible to call stack functions on queue nodes and queue functions on stack nodes.  Is this really desirable?  If not, then making the change above to introduce a QUEUE structure that wraps a QNODE head and QNODE tail would mean that you would at least have some level of type safety and the compiler would warn you if you tried to call dequeue on your stack.


Node.JS Twitter Count Module I would like someone review this code and tell if it can be done better, or if the code is elegant and simple enough for the task at hand.

I used code climate and I got 4/4 and my test coverage is 96%, yet I would like a professional opinion about it.

'use strict';

var PromisePolyfill = require('promise');
var http = require('http');

var twitterCountURL = 'http://urls.api.twitter.com/1/urls/count.json?url=';

/**
 * Gets the numbers of tweets of a given url.
 * @param {string} validUrl - The url to query
 * @returns {Number} Number of tweets
*/
exports.getCount = function(validUrl) {
    return new PromisePolyfill(function(resolve, reject) {
        if (validUrl) {
            http.get(twitterCountURL + validUrl, function(res) {
                var body = '';
                res.on('data', function(chunk) {
                    body += chunk;
                });
                res.on('end', function() {
                    var twResponse = JSON.parse(body);
                    if (!twResponse.count) {
                        twResponse.count = 0;
                    }
                    // console.log(twResponse.count);
                    resolve(twResponse.count);
                });

            }).on('error', function(e) {
                reject(e.message);
            });

        }else {
            resolve(0);
        }
    });
};

And its respective test file:

'use strict';

var chai = require('chai');
var chaiAsPromised = require('chai-as-promised');
var sinon = require('sinon');
var http = require('http');
var PassThrough = require('stream').PassThrough;
var twitterCount = require('../../modules/twitterCount');

var response,
  responsePT;

chai.should();
chai.use(chaiAsPromised);

describe('twitterCount Module', function() {

    beforeEach(function(done) {
        response = new PassThrough();
        responsePT = new PassThrough();
        sinon.stub(http, 'get');
        done();
    });

    afterEach(function(done) {
        http.get.restore();
        done();
    });

    it('should return valid count when a valid url is passed', function(done) {
        var expected = {'count': 234453234, 'url': 'http:\/\/www.google.com\/'};

        response.write(JSON.stringify(expected));
        response.end();

        http.get.callsArgWith(1, response)
                .returns(responsePT);

        twitterCount.getCount('http://www.google.com').should.eventually.equal(234453234).notify(done);
    });

    it('should return 0 when a invalid url is passed', function(done) {
        var expected = {'count': 0, 'url': 'http:\/\/invalidurl.invalid\/'};

        response.write(JSON.stringify(expected));
        response.end();

        http.get.callsArgWith(1, response)
                .returns(responsePT);

        twitterCount.getCount('http://invalidurl.invalid').should.eventually.equal(0).notify(done);
    });

    it('should return 0 when an empty url is passed', function(done) {
        var expected = {'count': 0, 'url': ''};

        response.write(JSON.stringify(expected));
        response.end();

        http.get.callsArgWith(1, response)
                .returns(responsePT);

        twitterCount.getCount('').should.eventually.equal(0).notify(done);
    });
});

JSON.parse must always be wrapped in a try catch, because you cannot guarantee that the body will be in proper format.  This will crash your server on failure.

You should add a test case to confirm this, just by responding with an empty string.


case...when or Hash#fetch I have the following method, which can be written in the following two ways: which one would you prefer, and why?

# version with case...when
def choose(value)
  case value
  when value < LOWER_LIMIT
    'a'
  when value > UPPER_LIMIT
    'b'
  else
    'c'
end

# version with Hash#fetch
def choose(value)
  { (value < LOWER_LIMIT) => 'a',
    (value > UPPER_LIMIT) => 'b'
  }.fetch(true, 'c')
end

I personally find the first one more linear and readable.

I would have just gone for an if/else, this really isn't a good use case for a case statement and I've never seen anyone use a hash like that except for demonstration purposes:

def choose(value)
  if value < LOWER_LIMIT
    'a'
  elsif value <= UPPER_LIMIT
    'c'
  else
    'b'
 end
end

or possibly using a ternary

def choose(value)
  value < LOWER_LIMIT ? 'a' : value <= UPPER_LIMIT ? 'c' : 'b'
end

note that I find it easier to keep my conditions in ascending order.

If this is a common pattern I would consider extending ranges.

class Range
  def case(value, less, in, more)
    if value < first
      less
    elsif include?(value)
       in
    else
       more
    end
  end
end

(LOWER_LIMIT..UPPER_LIMIT).case(value, 'a', 'c', 'b')


Function to check whether two strings are similar at given % Since the previous question I posted here was not found as interesting as I expected, I decided to post a new one. I made a function solely for the purpose of having fun. That is, a function that checks if two strings are similar with a given %.

int case_insensitive_chrcmp (int ch1, int ch2)
{
    return ch1 == ch2 || ch1 + ' ' == ch2 || ch1 - ' ' == ch2;
}

int strpcmp (char* str1, char* str2, unsigned setting)
{
    int szStr1 = strlen(str1);
    int szStr2 = strlen(str2);
    int szMax  = max(szStr1, szStr2);
    int szMin  = 0;
    int chars  = 0;

    if(setting > 100)
        setting = 100;

    if(szStr1 == szMax)
        szMin = szStr2;
    else szMin = szStr1;

    chars = szMax * setting / 100;

    int cur = 0;
    for(int i = 0; i < szMin; i++)
    {
        if(case_insensitive_chrcmp(str1[i], str2[i]))
            cur++;
        else cur = 0;

        if(cur >= chars)
            return 1;
    }

    return 0;
}

(you may need to provide your own definition for min and max since I think they are not supported by all compilers)

Example usage:

char* str1 = "Hello";
char* str2 = "Hey";
int percentage = 50%101; // or just 50 or w/e
printf("%s %i%% %s - %s\n", str1, percentage, str2, strpcmp(str1, str2, percentage) ? "true" : "false");

Output:

  Hello 50% Hey - true

More info on what the function is supposed to do:

It calculates how many characters must match consecutively based on percentage in order to return true. The comparison between characters is also done in case insensitive manner.

More info on how the function is required to work:

Regarding safety, this function can do much more, check
against null pointers, re-entrancy guarding, MT-safety and that shouldn't really damage the performance level.
Speaking of performance, I am a performancecholic and the first thing I can see that is bothering me here is the two strlens - the size of the two strings can be obtained within a single loop. Otherwise there are redundant iterations.

Alright I have a hole in my schedule, so I will give it a review myself.

Let's start with the function case_insensitive_chrcmp

The name mixes two standards for function name, the well-descriptive, but long snake_case and the less descriptive but shorter standard abbreviation naming.
So it would be better if it is either:

case_insensitive_char_compare
chrcasecmp

Since the second function uses the second standard, I would choose chrcasecmp.

Many people do not like one-liners as they actually require more space (or even ironically more lines) than if they were not a function at all.
Also it is a little bit slower (needs to access the routine, push the arguments onto the stack, etc). A good C function should be at least two lines and not more than a person with the old 640x480 monitor can see.
It can be optimized and shortened further using the bitwise XOR operator:

return ch1 == ch2 || (ch1 ^ ' ') == ch2;

Since ' ' translates to 32, which is the sixth bit set and others unset.

And the strpcmp function

I already said that two strlens to find the length of two presumably identical strings is not very efficient as it needs to iterate over both the strings, increment and check against '\0 at every iteration while this could be done in a single loop. This is an optimized function to find lengths of two strings:

int str2len (char* str1, char* str2, size_t * szStr1, size_t * szStr2)
{
    /* Variables */
    char*   p1      = str1;
    char*   p2      = str2;
    size_t  len1    = 0;
    size_t  len2    = 0;

    /* Pre-checking */
    if(str1 == NULL || str2 == NULL || szStr1 == NULL || szStr2 == NULL)
        return(-1);

    /* Processing */
    while(str1[len1] || p2[len2])
    {
        if(str1[len1] != '\0')
            len1++;
        if(str2[len2] != '\0')
            len2++;
    }

    /* Assignment */
    *szStr1 = len1;
    *szStr2 = len2;

    return 0;
}

int cur = 0; is declaration after expression, which turns the code into C89-incompatible. Also the name cur is not very descriptive. While it may mean "current" it is not clear current of what it is. Better name nMatch.
chars = szMax * setting / 100;
Does not define what happens if the result from the division is not a whole number. In most cases the floating point number will be omitted which may or may not be the desired behavior. I should consider using round(), floor() or ceil() on a double
The function checks if a char from str1 with index x matches a char with index x in str2 which makes the code susceptible to this scenario:
"Hello World" and "World" will always return false.
The function should rather search whether a characters are CONTAINED consecutively into the second string instead.


Unit converter application I am working on an Android unit converter application, but I came to the point where I have to assign the formulas to the calculation method. At the moment I am using a switch-case statement, as it is more neat than an if-else, but still this proves to be very, very lengthy.

The way the application works is the user selects type of unit to convert, e.g. length. Then 2 spinners show up, one for the "From" unit and one for the "To" unit. On calculation the code picks up what is chosen in the spinners and determines the right formula to use.

Here is a code snippet for only one unit conversion:

switch (unitFrom) {
    case "Kilometers": switch (unitTo){
        case "Miles": initialValue = (initialValue / 1.6);
            break;
        case "Metres": initialValue *= 1000;
            break;
        case "Centimetres": initialValue *= 100000;
            break;
        case "Millimetres": initialValue *= 1000000;
            break;
        case "Feet": initialValue *= 3280.8399;
            break;
        case "Yards": initialValue *= 1093.6133;
            break;
        case "Inches": initialValue *= 39370.0787;
            break;
        case "Nautical Miles": initialValue *= 0.539956803;
            break;
        case "Fathoms": initialValue *= 546.806649;
            break;
        case "Light Years": initialValue *= (1.05702341*(10^-13));
            break;
    }
}

This will become so, so long after just few units being written down, so I was wondering if there's a better way of doing things. I am open to all sort of changes.

The problem with code like this is that it grows very quickly.

switch (unitFrom) {
    case "Kilometers": switch (unitTo){

Adding one unit means that you have to provide conversions to every other unit. But there's a pattern in your code:

    case "Metres": initialValue *= 1000;
        break;
    case "Centimetres": initialValue *= 100000;
        break;
    case "Millimetres": initialValue *= 1000000;
        break;
    case "Feet": initialValue *= 3280.8399;
        break;
    case "Yards": initialValue *= 1093.6133;
        break;
    case "Inches": initialValue *= 39370.0787;

Each unit is essentially just a factor. And the conversion is just the multiplication of the length value with that factor.

Take a look at the SI unit system, where such factors are actually part of the unit:

1 mm = =1 millimeter = 1 * milli * meter = 1 * 10^(-3) * meter

"milli" which would generally be considered part of the unit is actually just a number with a name: 10^(-3)

Notice that the opposite conversion means to divide by that factor.

To simplify the conversion, you can choose a common base unit.
Now you don't have to convert every unit to every other unit but only have to specify one conversion: to/from the base unit.

Here's an example class doing this:

import java.util.HashMap;
import java.util.Set;

public class Converter
{
    public static void main (String[] args)
    {
        Converter converter = new Converter();

        Set<String> units = converter.availableUnits();

        double value = 5.4;

        for (String unitFrom : units)
        {
            System.out.println(value + " " + unitFrom + " are:");

            for (String unitTo : units)
            {
                System.out.println("\t" + converter.convert(unitFrom, unitTo, value) + " " + unitTo);
            }

            System.out.println();
        }
    }

    private HashMap<String, Double> _units;

    public Converter()
    {
        _units = new HashMap<String, Double>();

        _units.put("Millimetres", 1.0);
        _units.put("Metres", 1000.0);
        _units.put("Inches", 25.4);
        _units.put("Feet", 304.8);
        _units.put("Yards", 914.4);
    }

    public double convert(String from, String to, double value)
    {
        return value * _units.get(from) / _units.get(to);
    }

    private Set<String> availableUnits()
    {
        return _units.keySet();
    }
}

The program does every conversion possible.

I kept the conversion from one unit to itself in as a quick test. If you don't want that, opt-out when unitFrom == unitTo.

5.4 Millimetres are:
    5.4 Millimetres
    0.017716535433070866 Feet
    0.21259842519685043 Inches
    0.0054 Metres
    0.005905511811023623 Yards

5.4 Feet are:
    1645.92 Millimetres
    5.4 Feet
    64.80000000000001 Inches
    1.64592 Metres
    1.8 Yards

5.4 Inches are:
    137.16 Millimetres
    0.44999999999999996 Feet
    5.4 Inches
    0.13716 Metres
    0.15 Yards

5.4 Metres are:
    5400.0 Millimetres
    17.716535433070867 Feet
    212.5984251968504 Inches
    5.4 Metres
    5.905511811023622 Yards

5.4 Yards are:
    4937.76 Millimetres
    16.2 Feet
    194.4 Inches
    4.93776 Metres
    5.4 Yards

Additional thoughts:

The name of each unit is only specified once. Retyping string literals is prone to error "Millimetres" != "Millimeters", which the compiler cannot catch.

You could go further and define a class Unit, which besides the name and factor can contain, an abbreviation, plural and singular forms, etc.


Find the next Fibonacci number This code calculates, from a list of integers, the next fibonacci number for each integer. It does this for the first 60 numbers in the sequence. Any pointers on improving computing time, code readability, etc. are what I'm looking for.

def getFib(limit):
    a = 1
    b = 1
    res = [a, b]

    for i in range(1, limit):
        temp = a
        a = b
        b = temp + b
        res.append(b)
    return res

def nextFibonacci(fib, n):

    for x in n:
        if x < 1 or x > fib[len(fib)-1]:
            print("Value is out of range.")
        else:
            temp = x

            for c in fib:
                if c > temp:
                    temp = c
                    break

                print(temp)

def main():
    listMe = [1, 9, 22]
    fib = getFib(60)

    nextFibonacci(fib, listMe)

if __name__ == "__main__":
    main()

Use a cache to save fibonacci numbers, will improve speed of the program. That way you won't have to compute the numbers again at each loop.

'''
Cached_fib
'''
def memoize(f):
    cache = {}
    return lambda *args: cache[args] if args in cache else cache.update({args: f(*args)}) or cache[args]

@memoize
def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

def find_closest_fib(l):
    for num in l:
        i = 1
        while 2*num>fib(i)+fib(i+1):
            i += 1
        print ('Nearest fib number = {} \n for num {}\n'.format(fib(i), num))

if __name__ == '__main__':
    l = (60, 234234231, 35342454, 27000000000000)
    start_time = timeit.default_timer()
    find_closest_fib(l)
    print('Elapsed time: ', timeit.default_timer() - start_time)

    start_time = timeit.default_timer()
    find_fib_op(l)
    print('Elapsed time: ', timeit.default_timer() - start_time)

Output new version

Nearest fib number = 55 for num 60
Nearest fib number = 267914296 for num 234234231
Nearest fib number = 39088169 for num 35342454
Nearest fib number = 27777890035288 for num 27000000000000

Timing of implementation

Cached fibonacci

  Elapsed time: 0.06364319414684597

OP fibonacci

  Elapsed time: 0.23451719927193976


Validating forms data Here is a class that I made to validate forms data.  I will really appreciate any criticism and hints.

  <?php

class formvalidator {

    public $filtered, $errors,$db,
    $fields_type = Array(), $error_msgs = Array();

    public function validate($form, $fields, $error_msgs) {

        $this->fields_type = $fields;
        $this->error_msgs = $error_msgs;

        foreach ($form as $field => $data) {

            if (isset($this->fields_type[$field])) {
                if (method_exists($this, $this->fields_type[$field])) {
                    $_POST[$field] = call_user_func_array(array($this, $this->fields_type[$field]), array($data));

                    if ($_POST[$field] === false) {
                        $this->errors[$field] = sprintf($this->error_msgs[$field], $data);
                     }
                }
            } else {//Else ? unset it Security ?
                unset($_POST[$field]);
            }
        }

        //Manual validation for password and password confirmation
        if($_POST['form'] == 'signup' or $_POST['form'] == 'login')
        if (!isset($_POST['password'])) {
            $this->errors[$field] = sprintf($this->error_msgs['password'], '');
        }
        if (isset($_POST['repassword']) and $_POST['password'] != $_POST['repassword']) {
            $this->errors[$field] = sprintf($this->error_msgs['repassword'], '');
        }
        //End of password confirmation and password check.

        //
        $_POST = $this->clean($_POST);

        if (is_null($this->errors)) {
            return true;
        } else {

            return false;
        }
    }

    public function value_calss($input) {
        if (isset($_POST[$input])) {
            if (isset($this->errors[$input])) {
                echo ' error ';
            } else {
                echo '" value = "' . $_POST[$input];
            }
        }
    }

    public function errors() {

        if (!is_null($this->errors)) {
            echo '

Please Fix these:

';
            foreach ($this->errors as $error)
                echo "
$error
";
            echo '

';
        }
    }

    public function setError($error) {
        $this->errors[] = $error;
    }

    //Validations

    public function IsEmail($email) {
        return filter_var($email, FILTER_VALIDATE_EMAIL);
    }

    public function IsAlphaNum($str) {
        if (ctype_alnum($str))
            return trim($str);
        else
            return false;
    }

    public function IsString($str) {
        if (preg_match("/^[A-Za-z0-9\s]+[^ ]$/", $str))
            return trim($str);
        else
            return false;
    }

//Explite will return false on empty values which will cause raise error flag.
    public function explite($input) {
        return trim($input);
    }

    public function text($input){
        return trim(htmlentities($input));
    }

    public function IsDate($is_date){
        if(strtotime($is_date))
            return date("Y-m-d",strtotime($is_date));
        else
            return false;
    }

    public function file($input)
    {
        return $input;
    }

    public function boolen($input)
    {
        if($input)
            return true;
        else false;
    }

    public function clean($input) {
        $clean = Array();
        foreach ($input as $field => $data) {
            $clean[$field] = mysql_real_escape_string($data);
        }
        return $clean;
    }

}

?>

Update: New Version on gist

One thing that I see right off the bat, is the clean() method.  Why are you escaping things arbitrarily?

public function clean($input) {
    $clean = Array();
    foreach ($input as $field => $data) {
        $clean[$field] = mysql_real_escape_string($data);
    }
    return $clean;
}

All you're doing is making it harder to trace code, and harder to prove if your code is secure or not.  Not to mention that's a major breach of the Single Responsibility Principle.

It's a huge side-effect and should be removed.

Always escape or quote as close as possible to where you're putting it.


Vowel/consonant counter in Golang To learn Go I decided to write a vowel/consonant counter. I really need tips/ideas on how I can improve my code.

package main

import (
    "os"
    "bufio"
    "fmt"
)

func isVowel(x string) bool {
    vowels := [5]string{"a", "e", "i", "o", "u",}
    vowelLookupTable := make(map[string]bool)
    for _, v := range vowels {
        vowelLookupTable[v] = true
    }

    return vowelLookupTable[x]
}

func isConsonant(x string) bool {
    consonants := [21]string{"b", "c", "d", "f", "g", "h", "j", "k", "l", "m", "n", "p", "q", "r", "s", "t", "v", "w", "x", "y", "z"}
    consonantLookupTable := make(map[string]bool)
    for _, v := range consonants {
        consonantLookupTable[v] = true
    }

    return consonantLookupTable[x]

}

func formatNumbers(vowelCount int, consonantCount int) {
    fmt.Print("Consonants: ")

    for i := 0; i < consonantCount; i++ {
        fmt.Print("=")
    }

    fmt.Printf(" %d\n", consonantCount)

    fmt.Print("Vowels:     ")

    for i := 0; i < vowelCount; i++ {
        fmt.Print("=")
    }

    fmt.Printf(" %d\n", vowelCount)
}

func countVowels(input string) int {
    vowelCount := 0

    for _, x:= range input {
        var s string
        s = fmt.Sprintf("%c", x)
        if isVowel(s) {
            vowelCount += 1
        }
    }

    return vowelCount
}

func countConsonants(input string) int {
    consonantCount := 0

    for _, x:= range input {
        var s string
        s = fmt.Sprintf("%c", x)
        if isConsonant(s) {
            consonantCount += 1
        }
    }

    return consonantCount
}

func takeInput() string {
    reader := bufio.NewReader(os.Stdin)
    fmt.Print("Enter text: ")
    text, _ := reader.ReadString('\n')

    return text
}

func main() {
    input := takeInput()

    vowelCount := countVowels(input)
    consonantCount := countConsonants(input)

    formatNumbers(vowelCount, consonantCount)
}

Handle errors. In Go, foo, _ := something() is a big code smell.
Iterating on a string gives you a rune; don't convert it to a one-char string just to compare it to another one-char string. Compare it to another rune instead ('a' instead of "a").
Your functions isVowel and isConsonant are re-building the vowel/consonant map from scratch every time they're called! This is very inefficient: initialize both maps as package variables, and inline these two functions completely. You have two options to do so, I like the second one better because it's slightly more readable.

Option 1:

var (
    vowels = map[rune]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
    }
    consonants = map[rune]bool{
        // …
    }
)

Option 2:

var (
    vowels = toSet('a', 'e', 'i', 'o', 'u')
    consonants = toSet(/* … */)
)
func toSet(chars ...rune) map[rune]bool {
    m := make(map[rune]bool, len(chars))
    for _, c := range chars {
        m[c] = true
    }
    return m
}

You then check if a rune r is a vowel by just calling vowels[r].
Your s = fmt.Sprintf("%c", x) statement looks a lot like printf debugging. Were you intending to keep it in your code?
countVowels and countConsonants can be inlined as well, and called on each char in the same loop like in Curtis' answer.
Replace foo += 1 by foo++.
I'd say you have needless blank lines in your code (I think each of your functions is simple enough not to have any), but that's a minor style thing.
Your code doesn't support non-ASCII encodings (and it probably should, UTF-8 is everywhere nowadays). It doesn't support uppercase letters, either =)


Programming Challenge from Kattis: Watchdog I've tried to solve the kattis-challenge called Watchdog. My code works just fine, but it was too slow on the last test. I'm wondering if anyone sees any big algorithmic performance issues.

A short description of the task: First line from .in states number of test-cases.
First line in each test-case gives length of a square and number of hatches respectively. For each hatch you'll have one line giving x and y-point of hatch respectively. The mission is to find a point (x,y) where the length from (x,y) to any hatch is not greater than the length from (x,y) to any point outside of the square. If no such point, print poodle. If several such point print point with lowest x, if several points with equal x, print point with lowest y. Hatches and these points cannot overlap.

I think one issue might be extensive usage of lists, but I'm also not sure how to avoid them. Initially I started reading one and one line from stdin using the data. That way things looked way more readable, but it was also slower. And it's the speed that I'm having issues with.

Example input:

3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3

Example output:

3 6
poodle
2 2
2 2

My code:

import sys
from math import sqrt
import itertools

def findmaxdist(x1, y1, list):
    '''Finds the distance from x1, y1 to the most
    distant point in the list.'''
    dist = 0
    for x2, y2 in list:
        newdist = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)
        if newdist>dist:
            dist=newdist
    return sqrt(dist)

fulltext = sys.stdin.readlines()
text = [w.rstrip('\n') for w in fulltext]

cases = int(text[0])
i = 0
j = 1
while i < cases:
    side, hatches = text[j].split()
    side = int(side)
    hatches = int(hatches)
    j += 1
    hatch_list = list()
    for k in range(hatches):
        x, y = text[j].split()
        hatch_list.append((int(x), int(y)))
        j += 1

    possibles = list()
    for x,y in itertools.product(range(side), range(side)):
        if (x, y) not in hatch_list:
            dist = findmaxdist(x, y, hatch_list)
            if x+dist<=side and x-dist>=0:
                if y+dist<=side and y-dist>=0:
                    possibles.append((x, y))

    if len(possibles)==0:
        print('poodle')
    elif len(possibles)==1:
        print(str(possibles[0][0])+' '+str(possibles[0][1]))
    elif len(possibles)>1:
        smallx = min(possibles, key = lambda t: t[0])[0]
        semifinal = list((tuple for tuple in possibles if tuple[0] == smallx))
        if len(semifinal)==1:
            x,y = semifinal[0]
            print(str(x)+' '+str(y))
        elif len(semifinal)>1:
            smally = min(semifinal, key = lambda t: t[1])[1]
            final = list((tuple for tuple in semifinal if tuple[1] == smally))
            if len(final)==1:
                x,y = final[0]
                print(str(x)+' '+str(y))
        else:
            print('Error: Wrong input-format?')
    i+=1

Your solution is right, but unfortunately the time limit enforces a certain optimization. The key of this is where it says:

  If several such point print point with lowest x, if several points with equal x, print point with lowest y

In your case, you just append all possible candidate and then you have a very complicated way to find the lowest. First of all, this complicated way could have been reduced to sorting and returning first element.

If we think a bit further on how does itertools.product work, it will first iterate over x and then over y. This means that the first candidate we find, is the one with lowest x and lowest y of those x. This means 2 things: you don´t even need that sort, the answer will always be the first candidate.

Now if the answer is always the first candidate, why are we keeping all candidates? And why are we still calculating other possible candidates when we already have the answer? Keeping this in mind, the solution to your time limit is simple adding a break after the possibles.append((x, y)) line. This will make us stop processing when we find the answer, and will save enough time for the time limit.

This means all the elif len(possibles)>1: part is unnecessary, making it shorter and cleaner. Another simple optimization is changing hatch_list to a set instead of a list so that the if (x, y) not in hatch_list: takes less than O(n). Its a small change that only requires changing list() to set() and append to add.

There might be more optimization to make but the one of the break is the key to the problem and the expected optimization to make to be able to not have time limit.


Simple CMD turn-based game made in C Ive been learning c for the past few weeks, I made a simple turn-based game to show off what I know. Is there anything I can do to improve the code or make the game run better?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <time.h>
#include <stdbool.h>

int main(){
    srand(time(NULL));
    bool play = true;

    while(play){
        int choose = -2;
        int P_h = 25;
        int E_h = 30;
        int SP_u = 3;
        puts("Do you wanna play this game. [Press 0 to exit or press any other number to play]");
        scanf("%d", &choose);

        if(choose == 0){
            play = false;
            puts("Goodbye");
            break;
        }
        else{
            puts("Okay");
            Sleep(300);

            while(E_h > 0){
                int P_at = (rand()%8);
                int E_at = (rand()%10);
                int SP = 100;
                int at_p = -5;

                if(P_h <= 0){
                    puts("You have died");
                    break;
                }
             if(E_h <= 0){
                puts("you win!");
                break;
             }

                printf("You have %d uses left of the super attack \n", SP_u);
                puts("Would you like to attack or do a super attack [Press 0 to do a super attack, Press 1 to attack]");
                scanf("%d", &at_p);

                if(at_p == 0){
                    if(SP_u <= 0){
                    puts("Sorry, you have 0 uses left, you cannot use this \n");
                }
                else{
                    E_h -= SP;
                    SP_u--;
                    printf("\nThe enemy took a damage of %d! It now has a health of %d!", SP, E_h);

                    P_h -= E_at;
                    printf("\nThe enemy attacks! Your health went down by %d it is now %d \n \n", E_at, P_h);
                }

            }
            else if(at_p == 1){
                 E_h -= P_at;
                printf("\nThe enemy took a damage of %d! It now has a health of %d!", P_at, E_h);

                P_h -= E_at;
                printf("\nThe enemy attacks! Your health went down by %d it is now %d \n \n", E_at, P_h);
            }
            else{
                puts("Thats not an option, idiot \n");
            }

        }

    }
    if(E_h <= 0){
            puts("You killed the enemy!");
            puts("Would you like to play again? [0 to exit, Press anything else to play again]");
            scanf("%d", &choose);

            if(choose == 0){
                play = false;
                break;
            }
            else{
                play = true;
            }
        }
        else if(P_h <= 0){
            puts("You died. Would you like to play again to try to defeat the enemy. [0 to exit, anything else to play again]");
            scanf("%d", &choose);

            if(choose == 0){
                play = false;
                break;
            }
            else{
                play = true;
            }
        }
    }

    return 0;
}

I feel like there is a better way to program the decisions because right now they are just nested if statements.
I think

Formatting & Conventions
Always run your code through an autoformatter. On Linux, I use clang-format, and on Win10 I use VSCode's autoformatting intellisense features. I'm not sure of your exact setup, but formatting is big.
Next, variable names. The variable choose is wonderfully descriptive. I know immediately what it's for. The variable P_h on the other hand is vague and undescriptive. Don't worry about how long your variable names are. The compiler won't care. Instead focus on making variable names that are descriptive, like Player_health so that anyone who reads your code immediately understands it.
Program Flow
Ignoring all the messy specifics, this is what I read your program's flow as:
while playing:
    setup variables.
    get player input
    if player doesn't want to play
        exit
    otherwise:
        main game loop
    if lose:
        ask to replay
    if win:
        ask to replay

I'm purposefully ignoring the main game loop for now. Right off the bat, I see one big problem: You do the same thing twice down at the bottom. That whole choose==0 thing can be moved outside the if statements because in either case, you'll encounter it. (In the case where E_h>0 && P_h>0, you won't have exited the main game loop, so we can ignore that.)
That would look like this:
if (E_h <= 0) {
    puts("You killed the enemy!\nWould you like to play again? [0 to exit, Press anything else to play again]");
}
else if (P_h <= 0) {
    puts("You died. Would you like to play again to try to defeat the enemy. [0 to exit, anything else to play again]");
}
scanf("%d", &choose);
if (choose == 0) {
    play = false;
    break;
}
else {
    play = true;
}

Even here, we can optimize further. Watching program flow, anytime we hit the scanf on this code, we can assert that play==true and so we can remove the whole section that sets it. Furthermore, since the very next thing we do is run while (play) we can cut out the break, since it'll exit the loop naturally. Finally, conditionals that only run a single statement don't need brackets. (That one's up to personal choice, and doesn't really affect your code. I like to knock them off of there.) Thus, we can take 25 lines of code down to
if (E_h <= 0)
    puts("You killed the enemy!\nWould you like to play again? [0 to exit, Press anything else to play again]");
else if (P_h <= 0)
    puts("You died. Would you like to play again to try to defeat the enemy. [0 to exit, anything else to play again]");
scanf("%d", &choose);
if (choose == 0)
    play = false;

just seven.

Next, let's look at the part of the code where you initially ask if the player wants to play. Logically, if the player runs your code, you can assume that they meant to. The whole initial choice section can be removed. (If you choose to leave it in there, think about what might happen if the player decides to replay the game. Right now, they have to say they want to (re)play the game twice!)
Main Game Loop
Ok, here's the meat of it. First thing you can do is move this little number to the end:
if (P_h <= 0) {
    puts("You have died");
    break;
}
if (E_h <= 0) {
    puts("you win!");
    break;
}

and remove the second break. That functions the same, but you don't have to calculate attack values for a round you're not going to use.
As for your actual 'attack' section, it looks like you can significantly reduce that as well. You've got two options here: Either use switch statements or modify the program flow. switch would look like:
switch at_p
{
    case 0:
        super_attack code;
    break;
    case 1:
        regular_attack code;
    break;
    default:
        idiot_code;
}

As for program flow: Notice that in both of the attacks, you have very similar/identical code.  If you code for the boundary conditions right, imagine what you could do with P_at = SP. You could significantly refactor your main loop.
I'd personally go for the switch statement simply because it's more amenable to future upgrades.
Other suggestions
Don't use stdbool.h. It's a lot easier to operate using int. Generally, false maps to 0 and true maps to anything that isn't false. (Plus, ints are normally 4 bytes big and bools are 1 byte big. You've got gigs of space to use.) I never use bools, and if I need to use them, I'll declare a union and make a utility variable that holds boolean flags.
Watch for program flow. A good maxim to work towards is having only one return location. Whether that's return, break, exit() or continue, minimizing the number of ways a program can escape a particular section of code makes it easier to debug. Oftentimes you can move things at the beginning of loops to the end, negate the conditional inside of an if statement, or otherwise simplify your code just by jimmying around with it a bit.
Keep track of variable's possible values throughout your code. If something has to be a certain value at a particular point in the code, then there's no point checking that value or setting it to what it already is. This can get a little more complicated with bigger code, but it's a powerful skill.
Suggestions for future features
Perhaps look at implementing some more options in the main game, such as

defending and armor
quitting from within the main game loop
breaking the attack/defend portions out into their own functions

Also take a look at

do-while loops
Switch statements
constants

All in all, your code is good, but there's a few modifications to program flow that can be made to cut down on operational complexity.


Working out how many hours worked after a certain time I am working on some custom rules in a time managment system and need to know how many hours in a shift have been before a certain time (19:00pm) and how many hours after. Shifts can start in the evening and finish in the morning so need to take that into account.

So far I have the below (this is just a snippet for one day) however it seems very clumsy and eloborate what I have written, can't help but feel I am missing a simpler solution, anyone have any ideas?

    DateTime cutOffTime = new DateTime(DateTime.Now.Year, DateTime.Now.Month, DateTime.Now.Day, 19, 00, 00);
    string cutOffTimeOfDay = GetTimeOfDayFromDateTime(cutOffTime);

    double baseMondayHours = 10.00;
    baseMondayHours = (baseMondayHours - 0.5);

    if (GetTimeOfDayOnlyFromDateTime(monday.ShiftStart.Value) == "AM" && GetTimeOfDayOnlyFromDateTime(monday.ShiftEnd.Value) == "PM"
        && monday.ShiftEnd.Value.TimeOfDay < cutOffTime.TimeOfDay)
    {
        postCutOffMondayHours = 0;
        baseMondayHours = monday.HoursWorked.Value;
    }
    else
    {
        string endTimeOfDay = GetTimeOfDayFromDateTime(monday.ShiftEnd.Value);
        double hoursAfterCutOff = GetDuration(cutOffTimeOfDay, endTimeOfDay);

        postCutOffMondayHours = hoursAfterCutOff;
        baseMondayHours = (baseMondayHours - hoursAfterCutOff);
    }

public static string GetTimeOfDayFromDateTime(DateTime d)
{
    return d.ToString("HH:mm") + " " + d.ToString("tt", CultureInfo.InvariantCulture);
}

public static string GetTimeOfDayOnlyFromDateTime(DateTime d)
{
    return d.ToString("tt", CultureInfo.InvariantCulture).ToUpper();
}

    public static double GetDuration(string startTime, string endTime)
    {
        DateTime start = DateTime.Parse(startTime);
        DateTime end = DateTime.Parse(endTime);
        if (start > end)
            end = end.AddDays(1);

        TimeSpan duration = end.Subtract(start);

        return duration.TotalHours;
    }

I agree with your summation that it is clumsy.  I see you like to stringly type objects, such as GetTimeOfDayFromDateTime.  It would be neater to just get the time of day as a TimeSpan.  Also, you may have several overloads accepting different input arguments, so you don't need to include the FromDateTime in the name.

public static TimeSpan GetTimeOfDay(DateTime d) => d - d.Date;

Or if you want to simply check AM versus PM, you could use the DateTime.Hour.  If the hour is < 12, it's AM.  Otherwise, it's PM.

Now GetDuration doesn't have to accept string inputs.  They can accept the TimeSpan (i.e. time of day) for start and end, or just better yet, just subtract the 2 DateTime objects.

This just looks clumsy:

double baseMondayHours = 10.00;
baseMondayHours = (baseMondayHours - 0.5);

Cleaner would be either:

double baseMondayHours = 10.0 - 0.5;

or directly

double baseMondayHours = 9.5;

Another tip to keep in mind: Subtracting dates can produce bad results if the Kind of each DateTime is different.  Doesn't seem to be the case here, but be forewarned.


A definition of for-each Exercise 2.23

  The procedure for-each
  is similar to map. It takes as
  arguments a procedure and a list of
  elements. However, rather than forming
  a list of the results, for-each just
  applies the procedure to each of the
  elements in turn, from left to right.
  The values returned by applying the
  procedure to the elements are not used
  at all -- for-each is used with
  procedures that perform an action,
  such as printing. For example,

(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88

  The value returned by the call to
  for-each (not illustrated above) can
  be something arbitrary, such as true.
  Give an implementation of for-each.

I wrote the following:

(define (for-each l f)
  (f (car l))
  (when (> (length l) 1) (for-each (cdr l) f)))

Is this a good answer?

No. Your function needs to handle the empty list too. If your implementation supports unless, use this:

(define (for-each f l)
  (unless (null? l)
    (f (car l))
    (for-each f (cdr l))))

Otherwise, the R5RS-compatible version would be:

(define (for-each f l)
  (cond ((not (null? l))
         (f (car l))
         (for-each f (cdr l)))))

Granted, the implicit begin behaviour of cond is not explained until Chapter 3. So if you want to avoid using that, here's a similar version that uses let to simulate begin:

(define (for-each f l)
  (cond ((not (null? l))
         (let ()
           (f (car l))
           (for-each f (cdr l))))))

Now, here, too, the let body is an implicit begin. If you want to work around that, too, then bind the result of the side-effect to a dummy variable:

(define (for-each f l)
  (cond ((not (null? l))
         (let ((unused (f (car l))))
           (for-each f (cdr l))))))


Encapsulating snprintf to avoid repetition of sizeof Correct usage of snprintf involves very long and repetitive lines:

if (snprintf(buff, sizeof(buff), format, ...) >= (int)sizeof(buff))
        goto err;

I first encapsulated this macro: #define SSIZEOF(x) ((ssize_t)sizeof(x)).  The result is I now have a slightly shorter line:

if (snprintf(buff, sizeof(buff), format, ...) >= SSIZEOF(buff))
        goto err;

But I'm not yet happy.  Writing sizeof twice is still very long and annoying, and more if the buffer has a relatively long name.

I decided to do a macro that behaves this way (with the same exact safety) (The b in the name stands for buffer):

if (sbprintf(buff, format, ...))
        goto err;

It needs to be a macro to avoid the array decaying to a pointer, so that I can still use sizeof(buff) inside the macro.

sbprintf.h:

/******************************************************************************
 ******* include guard ********************************************************
 ******************************************************************************/
#ifndef ALX_STDIO_SBPRINTF_H
#define ALX_STDIO_SBPRINTF_H

/******************************************************************************
 ******* headers **************************************************************
 ******************************************************************************/
#include <stdio.h>

#include "libalx/base/assert/assert.h"
#include "libalx/base/compiler/size.h"

/******************************************************************************
 ******* macros ***************************************************************
 ******************************************************************************/
/* int  sbprintf(char buff[restrict], const char *restrict format, ...); */
#define sbprintf(buff, format, ...)     (                               \
{                                                                       \
        alx_static_assert_array(buff);                                  \
                                                                        \
        snprintf(buff, sizeof(buff), format, ##__VA_ARGS__) >= SSIZEOF(buff) \
}                                                                       \
)

/******************************************************************************
 ******* include guard ********************************************************
 ******************************************************************************/
#endif      /* libalx/base/stdio/sbprintf.h */

Used macros (defined in other headers from my library (libalx)):

#include <assert.h>

#include <sys/types.h>

#define alx_same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))

#define alx_static_assert_array(a)      do                              \
{                                                                       \
        static_assert(!alx_same_type((a), &(a)[0]), "Not an array!");   \
} while (0)

#define SSIZEOF(x)      ((ssize_t)sizeof(x))

I use GCC8 and C17 (gcc -std=gnu17 -Wall -Wextra -Werror), but if there is any easy and not very ugly fix that helps portability, it is welcome.  The same about C++:  This is about C (I'll ask the same question about C++ after this one has been answered), but if there is any fix that would improve compatibility with C++, it is also welcome.

What do you think about sbprintf?  Feel free to comment the other macros, of course!

EDIT:

The actual name of the macro in my library is alx_sbprintf to avoid using a name that may end up being used by a future implementation.

Related links:

How to make a variadic macro (variable number of arguments)

Pedantically, if (snprintf(buff, sizeof(buff), format, ...) >= SSIZEOF(buff)) goto err; is an insufficient test.  Test for < 0 is also needed.

  The snprintf function returns the number of characters that would have been written
  had n been sufficiently large, not counting the terminating null character, or a negative value if an encoding error occurred....
  C111 §7.21.6.5 3

Note that ssize_t itself is not in standard C.

To cope with both issues, perform 2 sided test and drop using ssize_t.

int i = snprintf(buff, sizeof(buff), format, ...);
if (i < 0 || (unsigned) i >= sizeof(buff)) goto err;

... or if INT_MAX <= UINT_MAX/2 (a very common implementation), code can cheat with a one sided test as i<0 coverts to a large unsigned.  Again no need for ssize_t.

int i = snprintf(buff, sizeof(buff), format, ...);
if ((unsigned) i >= sizeof(buff)) goto err;