Controller method to do fuzzy search for companies I would like some help to clean up this action, especially from @companies and downward. The comments should be enough to explain :)

def search
  @query = params[:query]
  unless @query.blank?
    @query.strip!
    #Get tags with fuzzy match
    tags = Tag.where("name LIKE ?", "%#{@query}%").pluck(:name)

    #Get vouchers with these tags
    @vouchers = Voucher.tagged_with(tags, :any => true)

    #Get companies with these tags, and add their vouchers to the list
    @companies = Company.tagged_with(tags, :any => true)
    @companies.each do |company|
      #Because can't merge with nil. Can this be re-written?
      if @vouchers.empty?
        @vouchers = company.vouchers
      else
        @vouchers.merge(company.vouchers)
      end
    end

    #Get every voucher's category. Can this be re-written?
    @categories = []
    @vouchers.each do |voucher|
      @categories << voucher.categories
    end
    #Because can't call .flatten on nil
    if @categories.any?
      #Need to flatten because the array will contain an arrays of categories [[],[],[]]
      @categories.flatten!.uniq # I don't really want .flatten.uniq in the view, or?
    end
  end
end

Unless I've misjudged what you're going for, this should work (it's not pretty though, I'm sure there's an even better way)

def search
  @query = params[:query].try(:strip) # strip here instead

  unless @query.blank?
    tags = Tag.where("name LIKE ?", "%#{@query}%").pluck(:name)
    @companies  = Company.tagged_with(tags, :any => true).includes(:vouchers) # eager load vouchers
    @vouchers   = [
      Voucher.tagged_with(tags, :any => true),
      companies.map(&:vouchers)
    ].flatten.uniq
    @categories = @vouchers.map(&:categories).uniq
  else
    # you need something here, by the way...
  end
end

If you don't need each of the collections in the search results, but only need the categories, you should probably add this to the Company model

has_many :categories, :through => :vouchers

then you can do

def search
  @query = params[:query].strip # strip here instead

  unless @query.blank?
    tags = Tag.where("name LIKE ?", "%#{@query}%").pluck(:name)
    vouchers  = Voucher.tagged_with(tags, :any => true).includes(:categories)
    companies = Company.tagged_with(tags, :any => true).includes(:categories)

    @categories = [vouchers, companies].flatten.map(&:categories).flatten.uniq
  end
end

However, I'd think about restructuring the database if possible, to avoid the mix of 1st and 2nd order associations.


implementing simple stream processor with sockets I'm trying to implement simple data streamer in Python with sockets. Consider one server and one or more clients. I just want to read data from server, process it and send it to the client. Here's how I do it now:

        outputsocket = socket.socket()
        outputsocket.bind((self.outputaddress, self.outputport))
        outputsocket.listen(2)
        inputsocket = socket.socket()
        rsocks, wsocks = [], []
        rsocks.append(outputsocket)
        rsocks.append(inputsocket)
        recv_data = []

        try:
            inputsocket.connect((self.inputaddress, self.inputport))
            while True:
                try:
                    reads, writes, errs = select.select(rsocks, [], [])
                except:
                    return
                for sock in reads:
                    if sock == outputsocket:
                        client, address = sock.accept()
                        wsocks.append(client)
                    elif sock == inputsocket:
                        data_from_socket = sock.recv(8192)

                if data_from_socket:
                    outdata = process_data(data_from_socket)
                    if wsocks:
                       reads, writes, errs = select.select([], wsocks, [], 0)
                       for sock in writes:
                           sock.send(outdata)
        except KeyboardInterrupt:
            inputsocket.close()
            outputsocket.close()
            # etc

Obviously, it's stripped down example, but I think you got the idea.
Does anyone have better ideas?

For the benefit of others (because this answer is two years late):

I had to implement a socket solution rapidly to accommodate testing a feature that required them. Ended up using socketserver to simplify the implementation, i.e., only about a dozen lines were needed.

Example below is pretty much straight out of the socket server docs:

""" creates, activates a socket server """
import socketserver

HOST, PORT = "localhost", 9999

class MyTCPHandler(socketserver.BaseRequestHandler):
    def handle(self):
        # self.request is the TCP socket connected to the client
        self.data = self.request.recv(1024).strip()
        print("{} wrote:".format(self.client_address[0]))
        print(self.data)
        # just send back the same data, but upper-cased
        self.request.sendall(self.data.upper())

print("Creating the server, binding to localhost on port", PORT)
server = socketserver.TCPServer((HOST, PORT), MyTCPHandler)

def activate_server():
    server.serve_forever()

def stop_server():
    print("Shutting the server on port", PORT)
    server.shutdown()

if __name__ == "__main__":
    activate_server()


Interleaving two strings The challenge:

From: URI Online Judge

  Implement a program Combiner that takes two Strings as parameters and combines them, alternating letters, starting with the first letter of the first String, followed by the first letter of the second String, then second letter of first String, etc. The remaining letters of the longer String are then appended to the end of the combination String and this combination String is returned.

  Input

  The input contains several test cases. The first line of input contain an integer N that indicates the number of test cases. Each test case is composed of a line containing two strings and each string contains between 1 and 50 characters, inclusive.

  Output

  Combine the two input strings, as shown in the example below and print the resulting string.

Code

static void Main(string[] args)
{
    int n = int.Parse(Console.ReadLine());

    while(n-- > 0)
    {
        args = Console.ReadLine().Split(' ');

        for (int j = 0; j < args[0].Length || j < args[1].Length; j++)
        {
            if (j < args[0].Length)
            {
                Console.Write(args[0][j]);
            }
            if (j < args[1].Length)
            {
                Console.Write(args[1][j]);
            }
        }

        Console.WriteLine();
    }
}

Question is

How can this code be faster?

Apparently, my code took 0.384 second to run with URI's test cases.

The faster sample that solved the problem using C# took 0.072 second, which is a significant difference.

An image with all the execution times from this problem in C# can be found here.

An if in a tight loop is usually a performance killer. At least worth trying is something along the lines of

    len = min(args[0].Length, args[1].Length);
    for (j = 0; j < len; ++j) {
        Console.Write(args[0][j]);
        Console.Write(args[1][j]);
    }
    WriteRemainingsOfLongerString();

As mentioned in the comments, it could also be more performant to build a string and Console.Write it at once.


Checking sensors in an environment I have the following diagram (did this only to ask here, it's obviously missing details):

From the diagram you can see I have to check if all sensors in an environment are respecting the established conditions, but I'm not comfortable with the way I'm implementing this...

class Environ:

    def __init__(self):
        self.load_conditions()
        self.load_modules()

    def load_modules(self):
        self.modules = []
        # Don't like this!
        m = Module(self.conditions)
        self.modules.append(m)

    def run_modules(self):
        for m in self.modules:
             m.process_sensors()

class Module:

    def __init__(self, conditions):
        self.conditions = conditions
        self.load_all_sensors()

    def load_all_sensors(self):
        self.sensors = []
        # Don't like this!
        s = Sensor(self.conditions)
        self.modules.append(m)

      def process_sensors(self):
         for s in sensors:
             if not s.is_sensor_respecting_conditions():
                 raise ...

e = Environ()
e.run_modules()

My question is: do I really have to replicate all these conditions? What can I do to make this code more clean?

The idea with objects is they maintain the data that they own. Try to avoid having the object hold onto other data just because it uses it. This makes later refactoring harder.
Below is a sketch of what the process chain might look like.

class Sensor(object):
    def process(self, conditions):
        if not self.is_respecting_conditions(conditions):
            raise Exception("Fill me in properly")

        self.apply(conditions)

class Module(object):
    def process(self):
        for s in self.sensors:
            try:
                s.process(self.conditions)
            except:  # Handle actual exception here
                pass  # whatever work is needed

class Environment(object):
    def process(self):
        for m in self.modules:
            m.process()

This assumes that the conditions are per module. If they are per Environment then you could would add the condition parameter to the process method of the Module object.


Trie - code review request for improvement Ok, code reviewers, I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

public class Trie {

    private static final int ASCII = 256;

    private TrieNode root;

    public Trie () {
        root = new TrieNode();
    }

    private static class TrieNode {
        TrieNode[] alphabets;
        char ch;
        String word;
        String meaning;

        public TrieNode() {
            this.alphabets = new TrieNode[ASCII];
        }

        public TrieNode (char ch) {
            this.alphabets = new TrieNode[ASCII];
            this.ch = ch;
        }
    }

    public void add (String word, String meaning) {
        TrieNode node = root;
        char[] ch = word.toCharArray();

        for (char c : ch) {
            if (node.alphabets[c] == null) {
                node.alphabets[c] = new TrieNode(c);
            }
            node = node.alphabets[c];
        }
        node.word = word;
        node.meaning = meaning;
    }

    public String getMeaning (String word) {
        TrieNode node = root;
        char[] ch = word.toCharArray();

        for (char c : ch) {
            node = node.alphabets[c];
            if (node == null) {
                return null;
            }
        }
        return node.meaning;
    }

    /**
     * Deletes all its children, but does not delete itself.
     */
    public void prune (String string) {
        TrieNode node = root;
        char[] ch = string.toCharArray();

        for (char c : ch) {
            node = node.alphabets[c];
            if (node == null) {
                return;
            }
        }
        node.alphabets = new TrieNode[ASCII];
        return;
    }

    public void print() {
        printWhole(root);
    }

    private void printWhole(TrieNode node) {
        if (node == null) {
            return;
        }
        if (node.word != null) {
            System.out.println("Word: " + node.word + " Meaning: " + node.meaning);
        }
        for (int i = 0; i < ASCII; i++) {
            printWhole(node.alphabets[i]);
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.add("mouse", "rat");
        trie.add("cop", "police");
        trie.add("cope", "endure");

        System.out.println("Expected rat, Actual: " + trie.getMeaning("mouse"));
        System.out.println("Expected police, Actual: " + trie.getMeaning("cop"));
        System.out.println("Expected endure, Actual: " + trie.getMeaning("cope"));
        System.out.println("Expected null, Actual: " + trie.getMeaning("co"));

        trie.print();

        trie.prune("cop");

        System.out.println("Expected police, Actual: " +trie.getMeaning("cop"));
        System.out.println("Expected null, Actual: " +trie.getMeaning("cope"));

        trie.print();
    }
}

The TrieNode[] alphabets can probably be changed to a Map<Character, TrieNode>.

This would have some important advantages:

First, you would not consume all characters domain space (256 in your sample code) unless you actually have nodes defined for all of them.
Second, if you use a HashMap or LinkedHashMap as implementation, the search algorithm is pretty fast, you won't have to iterate over the entire collection to find an element since the search is based on hashes.
Third, it will make it simpler to improve your code when you want to support other languages out there using more than just 256 characters.


Remove an event listener after firing once or any number of times Remove an event listener after firing once or any number of times

This is what I have:

/*jslint browser: true, vars: true, white: true, maxerr: 50, indent: 4 */
(function ()
{
    "use strict";

    function removeEventListenerAfterFiring(numberOfTimes, callback, useCapture)
    {
        var count = 0;
        return function listener(event)
        {
            count += 1;

            if (count >= numberOfTimes)
            {
                event.target.removeEventListener(event.type, listener, useCapture);
            }

            callback();
        };
    }

    function functionName()
    {
        // Code here.
    }

    window.addEventListener("DOMContentLoaded", removeEventListenerAfterFiring(1, functionName, false), false);
}());

Is there anything that could be improved, or is there a better way to do this?

Is it acceptable to specify useCapture twice? Is there a way to detect if useCapture has been specified so that I don't have to pass it to the removeEventListenerAfterFiring function?

Consider using event.currentTarget instead of event.target, since your handlers are probably bound to an ancestor element, not the current element.


Filtering out rude words This program will filter the input by replacing matching bad words with "Bleep!". I'd like the code to be more concise and C++ style where possible. One thing that bugs me is the was_bad flag I think is needed to skip printing a word that has matched one of my bad words - if there was some better way to skip the rest of the while loop upon encountering a bad word so I don't print Bleep! poop, for instance.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
    int i, was_bad = false;
    string input, bad[] = {"poop", "balls"};
    vector <string> badwords(bad, bad + sizeof(bad) / sizeof(string));

    while (cin >> input)
    {
        for (i = 0; i < badwords.size(); ++i)
            if (badwords[i] == input)
            {
                cout << "Bleep! ";
                was_bad = true;
                break;
            }

        if (!was_bad)
            cout << input << " ";

        was_bad = false;
    }

    return 0;
}

One thing that did strike me was to use a ternary operator:

while (cin >> input)
{
    for (i = 0; i < badwords.size(); ++i)
        if (badwords[i] == input)
        {
            is_bad = true;
            break;
        }

    cout << (is_bad ? "Bleep! " : input + " ");

    is_bad = false;
}

Instead of iterating over a vector I'd use std::find().
Even better, instead of std::vector I'd use std::set:

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main(int argc, const char * argv[])
{
    string bad[] = {"poop", "balls"};
    set<string> bad_words(bad, bad + sizeof(bad) / sizeof(string));

    string input;
    while(cin >> input)
    {
        if(bad_words.find(input)!=bad_words.end()){
            cout << "bleep! ";
        }
        else {
            cout << input << " ";
        }
    }
}


Beauty and the Strings in Haskell I decided to make a solution in Haskell to a problem that I found on another post here at CodeReview (link: The Beauty and the Strings)
I would like suggestions on how to improve letterFreqs.  I have tried searching for mutable arrays that could help with performance.  But is it worth it?  The array that is modified often is only 26 elements long.  Haskell is new to me, so I find syntax of libraries such as Data.Vector, Data.Array.MArray, and Data.IO.Array difficult to grasp easily.

{-# OPTIONS_GHC -F -pgmF htfpp #-}
module Main where
import Test.Framework
import Data.Char (isLower, isUpper, ord)
import Data.List (zipWith, sort)

letterFreqs :: String -> [Int]
letterFreqs str =
    freqs' str (replicate 26 0)
    where freqs' [] fs = fs
          freqs' (ch:tail) fs
            | isLower ch = let index = (ord ch - ord 'a')
                               (front, back) = splitAt index fs
                               newval = 1 + fs !! index
                           in freqs' tail (front ++ newval : drop 1 back)
            | isUpper ch = let index = (ord ch - ord 'A')
                               (front, back) = splitAt index fs
                               newval = 1 + fs !! index
                           in freqs' tail (front ++ newval : drop 1 back)
            | otherwise = freqs' tail fs

computeMaxBeauty :: String -> Int
computeMaxBeauty = sum . zipWith (*) [1..26] . sort . letterFreqs

test_ABbCcc = assertEqual 152 $ computeMaxBeauty "ABbCcc"

test_This_is_from_Facebook_Hacker_Cup_2013_ =
    assertEqual 551 $ computeMaxBeauty "This is from Facebook Hacker Cup 2013."

test_Ignore_punctuation__please___ =
    assertEqual 491 $ computeMaxBeauty "Ignore punctuation, please :)"

test_Sometimes_test_cases_are_hard_to_make_up_ =
    assertEqual 729 $ computeMaxBeauty "Sometimes, test cases are hard to make up."

test_CodeReview_is_love__CodeReview_is_life_ =
    assertEqual 724 $ computeMaxBeauty "CodeReview is love. CodeReview is life."

main :: IO ()
main = htfMain htf_thisModulesTests

If you're going to use a list in Haskell, the last thing you want to do is continually modify random elements within it. Luckily, there's a better way.

Start by listing out all of the different things your function is doing.

Drop characters that are not 'a'..'z' or 'A'..'Z'.
Regardless of case, determine a letter's position in the alphabet.
Tally a value that represents a specific letter in the alphabet.
Return a list of alphabet letter frequencies.

By identifying the smallest bits of functionality that still make sense to talk about, we can write or reuse functions that do only one thing, and then compose them using higher order functions into something that does everything we need in one go.

Since this problem is dependent on characters and lists, your first stop as a new Haskell user should be to the Haddock documentation for Data.Char and Data.List to learn about what pre-existing functions you might be able to use for your solutions.

Tackling the first bullet point, dropping some elements of a list conditionally on their values should jump out at you as a filter operation. If we look through the documentation for Data.Char you may realize that Char represents all Unicode characters—not just ASCII values—but we're only interested in the ASCII letters.

Knowing that Char is an instance of Enum (from the Data.Char documentation), we can use list range notation to get just the Char values we care about in a list. I.e., alphabet = ['a'..'z']. Instead of expanding our range to include the uppercase versions of letters, we'll next write a function to lowercase our string using toLower :: Char -> Char from Data.Char.

lower :: String -> String
lower = map toLower

And assuming we have a lowercase string, it's easy to filter to just the characters we're interested in.

alphas :: String -> Char
alphas = filter (`elem` alphabet)

Notice that we're building functions that can be easily composed to produce the functionality our final program requires. Going from an arbitrary string to just one containing valid letters all in lower case is easy, alphas . lower.

Going by the original statement of functionality, we next need to determine a letter's position in the alphabet so that we can then keep a tally of letter frequencies. In writing a functional version though we can be smarter. Instead of picking a letter and then finding the correct tally to increase, we rearrange the order of operations. First we group letters and then we count the number of elements in each group to produce a tally.

Perusing the documentation for Data.List we'll pull out sort and group. sort will rearrange our list of Char, then group will organize them into lists by equality. The last step is to run length encode the groups to produce a tally for each letter.

tally :: (Ord a) => [a] -> [(a, Int)]
tally = map runLength . group . sort
    where
        runLength :: [a] -> (a, Int)
        runLength       [] = error "runLength: Can't run length encode an empty list"
        runLength xs@(x:_) = (x, length xs)

That error case should be unnecessary, group shouldn't return any empty sub-lists, but we include it so that if our understanding is incorrect or future changes to the function ever break things we get a better error than a pattern-match failure (and the compiler stops complaining if we compile with -Wall).

Now one thing to note is that if a letter isn't present at all in a given string, tally won't return a pair for it. In your original computeMaxBeauty that's a problem since it relies on a list of length 26 being returned. Since we have alphabet which encodes letter value by position though we can write another version that is more flexible.

beauty :: (Char, Int) -> Int
beauty (a, n) = n * (fromMaybe 0 (elemIndex a alphabet) + 1)

Here we look up the index of a Char in alphabet, then use a utility function from Data.Maybe in the event that Char wasn't present. Because lists are 0-indexed we have to add 1.

And tying all of our simple single-purpose functions together,

computeMaxBeauty :: String -> Int
computeMaxBeauty = sum . map beauty . tally . alphas . lower

My working version, should be runnable.

import Data.Char (toLower)
import Data.List (group, sort)
import Data.Maybe (fromMaybe)

alphabet :: [Char]
alphabet = ['a'..'z']

lower :: String -> String
lower = map toLower

alphas :: String -> [Char]
alphas = filter (`elem` alphabet)

tally :: [Char] -> [(Char, Int)]
tally = map runLength . group . sort
    where
        runLength :: [a] -> (a, Int)
        runLength       [] = error "runLength: Can't run length encode an empty list"
        runLength xs@(x:_) = (x, length xs)

-- Matches original functionality, unnecessary with changed computeMaxBeauty as below
letterFreqs :: String -> [Int]
letterFreqs = map ((subtract 1) . snd) . tally . (alphabet ++) . alphas . lower

computeMaxBeauty :: String -> Int
computeMaxBeauty = sum . map beauty . tally . alphas . lower
    where
        beauty :: (Char, Int) -> Int
        beauty (a, n) = n * (fromMaybe 0 (elemIndex a alphabet) + 1)


Convert uppercase characters to lowercase and insert a space where each uppercase character used to be Prompt:

  You have been given a string s, which is supposed to be a sentence.
  However, someone forgot to put spaces between the different words, and
  for some reason, they capitalized the first letter of every word.
  Return the sentence after making the following amendments:

  Put a single space between the words. Convert the uppercase letters to
  lowercase.

Any suggestions on my code?

String amendTheSentence(String s) {
    StringBuilder modifiedString = new StringBuilder();
    char[] sToArray = s.toCharArray();
    if (Character.isUpperCase(sToArray[0])) {
        modifiedString.append(Character.toLowerCase(sToArray[0]));
    } else {
        modifiedString.append(sToArray[0]);
    }

    for (int i = 1; i < sToArray.length; i++) {
        char currentChar = sToArray[i];

        if (Character.isUpperCase(sToArray[i])) {
           currentChar = Character.toLowerCase(currentChar);
            modifiedString.append(" ");
        }
        modifiedString.append(currentChar);
    }
    return modifiedString.toString();
}

Thanks for sharing the code.

This is quite good for a first attempt (except the bug).

Things to consider:

Odd ball solution

This means that you do the same thing in different ways.

use of variable vs direct array access

when you handle the first letter you directly access it using array index access sToArray[0] whereas for all the other letters you first put the actual char into a local variable currentChar but you do not use it in the if statement. You should do the same at all places.
similar logic that could be the same

this is a bit trickier and may need some experience, but:
The difference between the handling of the first letter and all the other letters is that you don't put a space before it. Having in mind that there is an empty string ("") in Java putting that instead of the space is just a configuration, a different value to use and not a different behavior needing different instructions (or their order). Including point 1 your code could look like this:
(I intentionally kept your bug!)

String amendTheSentence(String s) {
    StringBuilder modifiedString = new StringBuilder();
    char[] sToArray = s.toCharArray();
    String separator = "";
    char currentChar = sToArray[0];

    if (Character.isUpperCase(currentChar)) {
        currentChar = Character.toLowerCase(currentChar);
        modifiedString.append(separator );
    }
    modifiedString.append(currentChar);

    for (int i = 1; i < sToArray.length; i++) {
        String separator = " ";
        char currentChar = sToArray[i];

        if (Character.isUpperCase(currentChar)) {
            currentChar = Character.toLowerCase(currentChar);
            modifiedString.append(separator);
        }
        modifiedString.append(currentChar);
    }
    return modifiedString.toString();
}

Now you have 4 lines which are repeated exactly the same before the loop and inside the loop. This 4 lines can be extracted to a parameterized method:

private void convertAndAppendTo(StringBuilder modifiedString, char currentChar,
                                String separator){
    if (Character.isUpperCase(currentChar)) {
        currentChar = Character.toLowerCase(currentChar);
        modifiedString.append(separator );
    }
    modifiedString.append(currentChar);
}

and your original method changes to this:

String amendTheSentence(String s) {
    StringBuilder modifiedString = new StringBuilder();
    char[] sToArray = s.toCharArray();
    convertAndAppendTo(modifiedString,  sToArray[0], "");

    for (int i = 1; i < sToArray.length; i++) {
        convertAndAppendTo(modifiedString,  sToArray[i], " ");
    }
    return modifiedString.toString();
}

Magic numbers

In your code the 0 is a magic number and should be declared as a constant with a meaningful name like this:

private static final int FIRST_LETTER_INDEX = 0;

String amendTheSentence(String s) {
    StringBuilder modifiedString = new StringBuilder();
    char[] sToArray = s.toCharArray();
    convertAndAppendTo(modifiedString,  sToArray[FIRST_LETTER_INDEX], "");
// ...

I for myself would also tread literal strings as magic numbers and convert them into constants:

private static final int FIRST_LETTER_INDEX = 0;
private static final String FIRST_SEPARATOR = "";
private static final String INTER_WORD_SEPARATOR = " ";

String amendTheSentence(String s) {
    StringBuilder modifiedString = new StringBuilder();
    char[] sToArray = s.toCharArray();
    convertAndAppendTo(modifiedString,  sToArray[FIRST_LETTER_INDEX], FIRST_SEPARATOR);
// ...

Naming

Finding good names is the hardest part in programming. So always take your time to think carefully of your identifier names.

Get your names from the problem domain, not from the technical solution.

You have a variable sToArray that stores the individual chars. The name tells something about the type of the variable but it should tell something about its purpose instead. So a better name might be individualLetters or just letters.


Pascal Triangle program in C I've created a program to calculate Pascal's triangle:

#include <stdio.h>
#include <stdlib.h>
void pascal(int limit)
{
    int *begin;
    begin=(int*)malloc(2*sizeof(int));
    *begin=1;
    *(begin+1)=1;
    int* p,q,s,t;
    int row=2,n=3,x;
    p=begin;
    q=begin+1;
    for(n=3;n<=limit+1;n++)
    {
        if(n==4)
        {
            free(begin);
        }
        x=1;
        printf("Row (%d) : ",row);
        for(int* i=p;i&lt;=q;i=i+1)
        {
            printf("%d ",*i);
        }
        putchar('\n');
        s=(int*)malloc(n*sizeof(int));
        t=s+n-1;
        *s=*p;
        *t=*q;
        for(int* g=p;g&lt;q;g=g+1)
        {
            *(s+x)=*g+*(g+1);
            x++;
        }
        p=s;
        q=t;
        row++;
    }
}

int main(void)
{
    int i;
    printf("Till which row would you like to calculate the Pascal Triangle?\n\n");
    printf("Type your answer:\t");
    scanf("%d",&i);
    putchar('\n');
    if(i<n)
        printf("Nope, you can't do that\n");
    else
    {
        printf("Row (1) : 1\n");
        pascal(i);
    }
}

My idea was to work with 2 arrays at the same time, but there is still a problem in my algorithm. How am I supposed to free the memory I allocated before? The first 8 bytes of begin are easy to free, but what should I do so I can free the memory I allocated through the pointers?

you don't free s which means you have a memory leak
*(begin+1) can be rewritten as begin[1], which is much clearer
1 char variable names are very hard to get into, use longer/descriptive names where needed

the entire function can be rewritten as

void pascal(int limit)
{

    int *row;
    row=(int*)malloc(2*sizeof(int));
    row[0]=1;
    row[1]=1;

    for(int n=3;n<=limit+1;n++){

    printRow(buffer,n);

    int* nextRow = (int*)malloc((1+n)*sizeof(int));
    nextRow[0]=row[0];
    nextRow[n]=row[n-1];

    for(int i=1;i<n;i++){
        nextRow[i]=row[i-1]+row[i];
    }
    free(row);
    row=nextRow;

    }
}

instead of the malloc->assign->free sequence I could have used realloc and then worked backwards:

row = (int*)realloc(row,(1+n)*sizeof(int));
row[n]=0;

for(int i=n;i>0;i--){
    row[i]+=row[i-1];
}

but this is less clear


MongoDB Perl Wrapper I'm trying to create a custom "mongodb perl wrapper".
I created the following perl module, which local on my machine runs.
My questions to the community are:

Would you create the module different?
Do you have improvements or adaptations to create the module better?

Code:

package MyMongo;

use strict;
use Exporter;
use vars qw($VERSION @ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
use MongoDB;

$VERSION     = 1.00;
@ISA         = qw(Exporter);
@EXPORT      = qw();
@EXPORT_OK   = qw();
%EXPORT_TAGS = ( DEFAULT => [qw()],
                 Both    => [qw()]);

sub new {
    my ($class, $args) = @_;
    my $self = {
        host     => $args->{host} || 'localhost',
        port     => $args->{port} || '27017',
        database => $args->{database} || '',
        connection => $class->_set_connection(),
    };
    return bless $self, $class;
}

sub _set_connection {
    my $self = shift;
    my $client = MongoDB->connect('mongodb://localhost');
    return $client;
}

sub get_database_names {
    # Lists all databases on the mongo server
    my $self = shift;
    return  $self->{connection}->database_names;
}

sub get_database {
    # Returns a MongoDB::Database instance for database with the given $name
    my ($self, $dbname) = @_;
    return $self->{connection}->get_database($dbname);
}

sub authenticate {
    my ($self, $args) = @_;
    $self = {
        dbname => $args->{dbname},
        user => $args->{user},
        password => $args->{password}
    };
    $self->{connection}->authenticate($self->{dbname}, $self->{user}, $self->{password});
}
1;

I'm the lead engineer for the MongoDB Perl driver with a couple of thoughts for you:

you're using 'authenticate', which is for a very old version of the driver which is not recommended for use.  In the v1.x series, you should provide username/password in the URI or in MongoClient parameters.
Most of the value of this module seems to be setting parameters and calling connect.  I would suggest doing that with a function, not a module and then just using the resulting MongoDB::MongoClient object directly.


Solution for sum of all fizzbuzz numbers in a given range The number fizz buzz is composed of two numbers that are fizz and buzz.

fizz represents the numbers that are divisible by 3 and buzz are the numbers that are divisible by 5.

combining both fizz buzz are the numbers that are divisible by both 3 and 5 both. So how can we get all the fizz buzz numbers sum in a given range?

If we analyze and try to find out the numbers that are divisible by both 3 and 5 we get series like this:

3*5*1, 3*5*2, 3*5*3, .....,3*5*n

analyzing this here is my C# code to find all fizz buzz numbers sum in a given range.

I am looping through the entire range and add all numbers whose remainder with 15 is 0.

int start_range = Convert.ToInt32(Console.ReadLine());
int end_range = Convert.ToInt32(Console.ReadLine());
int sum = 0;
for(int i= start_range; i<= end_range; i++)
{
    if(i%15==0)
    {
        sum = sum + i;
    }
}
Console.WriteLine(sum);
Console.ReadKey();

I don't have much to say for the code itself, it is concise, readable and does what you want it to do. That's a good start. My only critique is that you handle input and output in the same place, if you plan on reusing the code maybe consider making a method.

So since the code is on point, we can look at the algorithm you are using. The only time the sum will change is when the sequence passes a multiple of 15. So lets see if we can find which multiples of 15 are between our starting point (x) and our ending point (y).

If we start at x, the first multiple of 15 we will encounter will be

$$15 \lceil \frac{x}{15} \rceil$$

To give you some intuition as to why this is the case, my argument is as follows. When you divide a number by 15, you get a whole part (how many 15s you can make from x) and a remainder (how many are left over when you make as many 15s from x as you can). The next multiple of 15 after (or including) x will be the first number you get when counting upwards who's remainder is 0. In other words, the remainder is a progress bar of how close to 15 we are. By taking the ceiling of x / 15, we are setting the progress bar to full, so when we multiply by 15 we get the next multiple.

What is the last multiple before (or including) y? We can use similar logic to get

$$15 \lfloor \frac{y}{15} \rfloor$$

And now we can directly loop over multiples of 15, no need to do any mods.

int start = 15 * (int)Math.Ceiling((double)start_range / 15);
int end = 15 * (int)Math.Floor((double)end_range / 15);
int sum = 0;
for (int i = start; i <= end; i += 15) {
    sum += i;
}

We don't have to stop there. This is a straightforward enough sum so we can somewhat simplify it.

$$start + (start + 15) + (start + 30) + ... + end$$

We can write start and end as multiples of 15 (where a and b are just integers).

$$15a + (15a + 15) + (15a + 30) + ... + 15b$$

We will now factor out 15 term.

$$15(a + (a + 1) + (a + 2) + ... + b)$$

int a = (int)Math.Ceiling((double)start_range / 15);
int b = (int)Math.Floor((double)end_range / 15);
int sum = 0;
for (int i = a; i <= b; i++) {
    sum += i;
}
sum *= 15;

I think the sum is simple enough now that we can do it without a loop. I'm going to "cheat" a little and just introduce the identity we will use without much explanation. There are some nice visualizations and proofs online if you want to look them up yourself.

$$ a, b \in \mathbb{N}; \sum_{i=a}^{b}{i} = \sum_{i=0}^{b}{i} - \sum_{i=0}^{a-1}{i} $$

The sum of numbers from 0 to n is well known

$$ \sum_{i=0}^{n}{i} = \frac{n^2+n}{2} $$

So we can use this equation to derive

$$ \sum_{i=a}^{b}{i} = \frac{b^2+b}{2} - \frac{(a-1)^2 + a - 1}{2} $$

$$ = \frac{b^2+b}{2} - \frac{a^2 - 2a + 1 + a - 1}{2} = \frac{b^2+b}{2} - \frac{a^2 - a}{2} $$

$$ = \frac{b^2+b - a^2 + a}{2} $$

This is only a couple of lines of code now, and should run in constant time.

int a = (int)Math.Ceiling((double)start_range / 15);
int b = (int)Math.Floor((double)end_range / 15);
int sum = 15 * (b*b + b - a*a + a) / 2;

Final remarks, in many languages integer division will floor the result (once the numbers are both positive). This means we can avoid Math.Floor if we assume end_range >= 0 (which seems like a fair assumption).

We also have the constant 15 strewn around the code, let's make it a variable.

int num = 15;  // A magic number specific to our problem
int a = (int)Math.Ceiling((double)start_range / num);
int b = end_range / num;
int sum = num * (b*b + b - a*a + a) / 2;

We could also avoid the Math.Ceiling call but the code may lose it's readability. The code also doesn't account for bugs like overflow, and it could be reworked to delay those issues. Currently, I don't think either of these changes would be worth it.


Good interface for reverting effect of function In my job, we often write functions that do some calculation and write the result to a database. Sometimes mistakes are made and wrong stuff ends up being saved, therefore we also want to supply an interface to clean up after the function. This is an attempt of solving that problem.
from functools import wraps

def revert(func):
    if not hasattr(func,'_revert'):
        raise NotImplementedError(func.__name__ + " does not have a revert registered")

    @wraps(func._revert)
    def wrapper(*args,**kwargs):
        return func._revert(*args,**kwargs)
    return wrapper

def register_revert(revert):
    def revert_added(func):
        func._revert = revert

        @wraps(func)
        def wrapper(*args,**kwargs):
            return func(*args,**kwargs)
        return wrapper
    return revert_added

def _is_it_a_str(maybe_str):
    if not isinstance(maybe_str,str):
         raise ValueError("I need a string")

def _revert_stuff(a_str):
    _is_it_a_str(a_str)
    print('revert stuff with ' + a_str)

@register_revert(_revert_stuff)
def do_stuff(a_str):
    _is_it_a_str(a_str)
    print('doing stuff with ' + a_str)

do_stuff('something')
# Oops:
revert(do_stuff)('something')

The idea is to write your function doing your job - do_something in this case. And then when you are ready to take it to the next level, you write its revert, register it and you are done.
I like that

the solution does not require changing anything in the main functionality.
you can use the same identical interface for many functions
the syntax reads relatively intuitively

I think it is inconvenient that

I need to maintain two identical interfaces - the one on do_stuff and _revert_stuff needs to be identical (or at least _revert_stuff needs to work getting the one from do_stuff).
sometimes I want to type-check the arguments which I then also have to repeat (exemplified here with _is_it_a_str). I thought about moving that to another decorator, but I'm afraid it gets too confusing.

Edit: We use the newest stable version of Python
p.s. My first question tried my best. Critique welcome!

def revert(func):
    @wraps(func._revert)
    def wrapper(*args,**kwargs):
        return func._revert(*args,**kwargs)
    return wrapper

You are returning a wrapper, which takes arguments, calls a function, and returns results...
I'm pretty sure that is just a long way of writing:
def revert(func):
    return func._revert

This begs the question: why store the revert function as func._revert, when you could store it as func.revert?  Then instead of:
revert(do_stuff)('something')

you could write:
do_stuff.revert('something')

which is one character shorter.  Even better: autocomplete can tell you whether there is a .revert member for do_stuff, which is not possible using revert(...).


Card class for card games I'm attempting to improve my coding style by concentrating on simple and focused OOP client-server interfaces and error handling - atm in the context of designing a Blackjack game.  I'm starting with the Card class that represents an individual card.  I'm looking for any improvements on or flaws with my approach.

#include <sstream>
#include <stdexcept>
#include <string>

class Card
{
public:
    enum Ranks { Ace = 1, Ten = 10, Jack, Queen, King };
    enum Suits { Spades, Hearts, Diamonds, Clubs };

    Card( int rank, int suit ) throw(std::range_error)
    {
            if( rank < 1 || rank > 13 ) {
                    std::stringstream errMsg;
                    errMsg << "Card(): rank '" << rank << "' out of range";
                    throw std::range_error( errMsg.str() );
            } else if( suit < 0 || suit > 3 ) {
                    std::stringstream errMsg;
                    errMsg << "Card(): suit '" << suit << "' out of range";
                    throw std::range_error( errMsg.str() );
            }

            m_rank = rank;
            m_suit = suit;
    }

    int rank() const { return m_rank; }
    int suit() const { return m_suit; }
    std::string str( bool useStrings = false ) const
    {
            std::stringstream ret;
            if( useStrings )
                    ret << sRanks[m_rank] << " of " << sSuits[m_suit];
            else
                    ret << cRanks[m_rank] << cSuits[m_suit];
            return ret.str();
    }

private:
    static const char cRanks[14];
    static const char cSuits[4]
    static const std::string sRanks[14];
    static const std::string sSuits[4];

    int m_rank;
    int m_suit;
};

const std::string Card::sSuits[4] = {"Spades", "Hearts", "Diamonds", "Clubs"};
const std::string Card::sRanks[14] = { "\0", "Ace", "Two", "Three", "Four", "Five",
                    "Six", "Seven", "Eight", "Nine", "Ten", "Jack", "Queen", "King" };
const char Card::cSuits[4] = { 's', 'h', 'd', 'c' };
const char Card::cRanks[14] = { '\0', 'A', '2', '3', '4', '5', '6', '7',
                                '8', '9', 'T', 'J', 'Q', 'K' };

The client can create a card either using the Card enum constants or integers, like

Card card(Card::Ace, Card::Diamonds);
Card card2(0, 3); // throws an exception

I'm dubious on how useful the public enum constants are for client code.  Also, I'm very new to exception programming and I'm not sure if this is a good approach or whether the constructor should throw an exception.  Any improvements or suggestions?

If you are going to go to the trouble of creating Rank and Suit enum then use them.

Card( int rank, int suit ) throw(std::range_error)

I would have done

Card(Rank rank,Suit suit )

That way you can't accidentally go: Card(Card::Hearts,2) The compiler type checking will catch this at compiletime. Just use the enums all through your code. C++ is a strongly typed language use the compiler to catch your errors.

The exception specifications have been deprecated. They were mostly useless anyway (if you fail and throw an illegal exception it causes your application to terminate without unwinding the stack). So in general don't use them. For the one case where they are usfull (no throw specifications) they are good but I use them more as documentation to remind me that I should make sure the method does not throw.

But yes the constructor should throw an exception if it gets a value outside the expected range. There is no point in allowing an invalid object to propagate threw your code it will just cause problems with your invariants.

Prefer to use the initializer list rather than initializing variables in the constructor.

Card(Rank rank, Suit suit)
    : m_rank(rank)
    , m_suit(suit)

Again another place that it would have been nice to use the enum to make the code more eadable:

        if( rank < 1 || rank > 13 ) {

Try:

        if( rank < Ace || rank > King ) {

Hate getters/setter they spoil encapsulation. Do you really need to get the values of the card? Any operation that manipulates the card is usually a method on the card or a friendly class.

int rank() const { return m_rank; }
int suit() const { return m_suit; }

Don't try and write C++ like Java. We don;t need a string function. It is much more preferable (and flexable) to write an output (and probably input) stream operator.

std::string str() const
{
        return std::string( Ranks[m_rank] + Suits[m_suit] );
}

I would have done:

friend std::ostream& operator<<(std::ostream& stream, Card const& card)
{
    return stream << card.Ranks[card.m_rank] << card.Suits[card.m_suit];
}

Adding Cards to a deck. (Based on comment below)

#include <vector>

class Card
{
    public:
        enum Ranks { Ace = 1, Ten = 10, Jack, Queen, King };
        enum Suits { Spades, Hearts, Diamonds, Clubs };

        Card(Ranks rank, Suits suit){}
};

// Need to add the ++ operators for Ranks/Suits
Card::Ranks& operator++(Card::Ranks& r)
{
    return r = Card::Ranks(static_cast<int>(r)+1);
}
Card::Suits& operator++(Card::Suits& s)
{
    return s = Card::Suits(static_cast<int>(s)+1);
}

int main()
{
    std::vector<Card>   deck;

    // Does not look that verbose to me.
    for(Card::Ranks rank=Card::Ace;rank <= Card::King;++rank)
    {
        for(Card::Suits suit=Card::Spades;suit <= Card::Clubs;++suit)
        {
            deck.push_back(Card(rank, suit));
        }
    }

    // Compared to
    for(int rank=Card::Ace;rank <= Card::King;++rank)
    {
        for(int suit=Card::Spades;suit <= Card::Clubs;++suit)
        {
            deck.push_back(Card(rank, suit));
        }
    }
}


How do I refine my code in Sikuli? Seems very long and redundant I'm only just beginning in programming.

The goal of the program is to check to make sure images are properly rendered within a program(within a VM)

. Below is the code, and I am asking what I can do to clean it up.

I don't think you can tell much without the .png's, but I would appreciate it if anyone knows where/how I can optimize my code.

Thank you very much for any help,

var=(0) #Empty Variable
jpgl=0 #NUMBER PASSES
vm = App("C:\Program Files (x86)\VMware\VMware Workstation\\vmware.exe")
switchApp("vm")
reg=( )
reg.find( )
#------------------------------------
#BEGINNING SPECIAL CASES/NAVIGATION
if not exists( ):
    switchApp("vm")
    type(Key.BACKSPACE)
    onAppear( ,type(Key.BACKSPACE))
if exists( ):
    click( )
#if exists( ):#attempt to get rid of.
#   click( )
else:
    exists( )
    click( )
    exists( )
    click( )
    wait(1)
    if not exists ( ):#if the image hasn't already loaded, wait the maximum 5 seconds
        wait(5)
#END FOLDER NAVIGATION
#----------------------------------
#BEGIN IMAGE CHECK 1
    if not exists ( ):
        print("B-JPEG_L-20.jpg not displayed correctly")
    if exists( ):
        print("B-JPEG_L-20.jpg Unable to play")
        click( )
    else:
        jpgl=jpgl+1#if the image exists, it moves on by clicking "next"
        click( )
        wait(1)
        if not exists ( ):
            wait(5)
#DONE IMAGE CHECK 1
#----------------------------------
#BEGIN IMAGE CHECK 2
.....

#end code

One way to get started improving your script is to find repeated code, then create a function to hold it.

For example, if your code starting with #BEGIN IMAGE CHECK 1 is duplicated for subsequent image checks, it could become a function that takes a Sikuli image file name - define it somewhere near the top of your file (NOTE: This assumes the same image filename is used consistently across this entire chunk of code, which may not be true in your unedited code):

def check_image(image_filename):
        if not exists(image_filename):
                print("%s not displayed correctly" % image_filename)
        if exists(image_filename):
                print("%s Unable to play" % image_filename)
                click(image_filename)
        else:
                jpgl = jpgl + 1
                click(image_filename)
                wait(1)
                if not exists (image_filename):
                        wait(5)

Then below that you can call the function with:

check_image('foo.jpg')

Then you should have a starting point for incrementally refining your code. At some point creating a class to hold your test logic could be useful as well.

I recommend reading up on functions and classes in Python - solid knowledge in those areas really helps out with Sikuli development:

http://docs.python.org/tutorial/controlflow.html#defining-functions

http://docs.python.org/tutorial/classes.html#tut-classes


Optimize code to track player shot This code is for a simple 2D tile-based game. x1 and y1 are the mouse coordinates in the world. entity->x1 and entity->y1 is the point where the player is, the shot origin.

I would like to know how to keep the current output while simplifying the code and improving performance.

void shoot(Map *map, Entity *entity, int x1, int y1)
{
    float slope = (y1 - entity->y1) / (x1 - entity->x1);
    float y = entity->y1; //Weapon position
    Block *block;

    if(x1 > entity->x1){
        y += slope;
        for(float x = entity->x1 + 1; x < map->width && y < map->height && y > 0; ++x){

            //Get block at position x y. Check if found a hit
            if((block = map_block_at(map, x, y))->type != EMPTY){
                block_cause_damage(block, entity->hand_item->weapon.damage);
                return;
            }

            y += slope;
        }
    }

    else
    if(x1 < entity->x1){
        y -= slope;
        for(float x = entity->x1 - 1; x > 0 && y < map->height && y > 0; --x){

            //Get block at position x y. Check if found a hit
            if((block = map_block_at(map, x, y))->type != EMPTY){
                block_cause_damage(block, entity->hand_item->weapon.damage);
                return;
            }

            y -= slope;
        }
    }

    //When the player shoots up or down
    else {
        slope = (y1 > entity->y1) ? 1 : - 1;
        y += slope;
        while(y < map->height && y > 0){

            //Get block at position x y. Check if found a hit
            if((block = map_block_at(map, x1, y))->type != EMPTY){
                block_cause_damage(block, entity->hand_item->weapon.damage);
                return;
            }

            y += slope;
        }
    }
}

The code for Entity and Map:

typedef struct Entity {
    Renderable renderable;
    plist_id render_id;
    Point (*get_current_position)(struct Entity *, uint32_t);
    int health, attack_damage, running, jumping;
    float x0, y0, x1, y1;
    uint32_t t0, t1;
    enum {LEFT, RIGHT} side;
    Image **texture;
    Item *hand_item;
    Backpack backpack;
} Entity;

typedef struct {
    Renderable renderable;
    plist_id render_id;
    int width, height;
    Block *blocks;
    Camera *camera;
} Map;

It's a little difficult to do a good review because there are so many pieces missing, but I've guessed at a number of things and I believe I can help.

Specifically, it looks like your Map is a rectangular grid of Blocks and that all x and y coordinates are integers.  If so, then your shot routine is really doing the equivalent of drawing a line from the entity location to the passed x1,y1 coordinates and one very efficient way to do that is to use Bresenham's line-drawing algorithm.  Using a slight modification of that algorithm, since your shot routine seems to want to go until it either hits something or goes off the Map, we get a very efficient and very small routine:

void shoot(Map *map, Entity *entity, int x1, int y1)
{
    int sx = entity->x1 < x1 ? 1 : -1;
    int sy = entity->y1 < y1 ? 1 : -1;
    int dx = abs(x1 - entity->x1);
    int dy = abs(y1 - entity->y1);
    int err = (dx>dy ? dx : -dy)/2;
    int e2;

    x1 = entity->x1;
    y1 = entity->y1;
    Block *block;
    while (inbounds(map,x1,y1)) {
        e2 = err;
        if (e2 > -dx) {
            err -= dy;
            x1 += sx;
        }
        if (e2 < dy) {
            err += dx;
            y1 += sy;
        }
        if((block = map_block_at(map, x1, y1))->type != EMPTY){
            block_cause_damage(block, entity->hand_item->weapon.damage);
            return;
        }
    }
}

I've assumed that you have or can easily write an inbounds routine that returns true if the passed coordinates are within the Map.


William Fractal technical indicator implementation I'm really new to both Python, data analysis and Panda and for gathering a bit of familiarity with this components and trying to replicate a trading strategy I'm creating a function that give me the Wiliam Fractal technical indicator, which by nature is a lagging indicator to apply at the currently analysed row of the dataframe, rather than where it actually happen, but without look ahead bias to not have unrealistic backtesting results ( but also avoiding to go back and always looking for the signal 2 rows before when it actually occurs )
the indicator is defined with this constrains
source
\begin{aligned} \text{Bearish Fractal} =\ &\text{High} ( N ) > \text{High} ( N - 2 ) \text{ and} \\ &\text{High} ( N ) > \text{High} ( N - 1 ) \text{ and} \\ &\text{High} ( N ) > \text{High} ( N + 1 ) \text{ and} \\ &\text{High} ( N ) > \text{High} ( N + 2 ) \\ \end{aligned}
\begin{aligned} \text{Bullish Fractal} =\ &\text{Low} ( N ) < \text{Low} ( N - 2 ) \text{ and} \\ &\text{Low} ( N ) < \text{Low} ( N - 1 ) \text{ and} \\ &\text{Low} ( N ) < \text{Low} ( N + 1 ) \text{ and} \\ &\text{Low} ( N ) < \text{Low} ( N + 2 ) \\ \end{aligned}

which I implemented with the following code:
def wilFractal(dataframe):
        df = dataframe.copy()
        df['bear_fractal'] = (
                dataframe['high'].shift(4).lt(dataframe['high'].shift(2)) &
                dataframe['high'].shift(3).lt(dataframe['high'].shift(2)) &
                dataframe['high'].shift(1).lt(dataframe['high'].shift(2)) &
                dataframe['high'].lt(dataframe['high'].shift(2))
        )

        df['bull_fractal'] = (
                dataframe['low'].shift(4).gt(dataframe['low'].shift(2)) &
                dataframe['low'].shift(3).gt(dataframe['low'].shift(2)) &
                dataframe['low'].shift(1).gt(dataframe['low'].shift(2)) &
                dataframe['low'].gt(dataframe['high'].shift(2))
        )

        return df['bear_fractal'], df['bull_fractal']

any suggestions?
usage edit:
The code in this case is used to signal buy signal for a crypto trading bot in this manner:
def populate_buy_trend(self, dataframe, metadata)
    dataframe.loc[
        dataframe['bull_fractal'],
        'buy'] = 1

    return dataframe

Looks good, just a few ideas:

Since the function only returns two series, you can save some overhead by removing the copy() and just working with series.

np.logical_and.reduce() allows you to build the shifted series in a comprehension (and also seems slightly faster than chaining & & &, based on some rough testing).

Instead of testing shift(2) against 4,3,1,0, I find it more intuitive to test the unshifted series against -2,-1,1,2.

def wilFractal(df):
    periods = (-2, -1, 1, 2)

    bear_fractal = pd.Series(np.logical_and.reduce([
        df['high'] > df['high'].shift(period) for period in periods
    ]), index=df.index)

    bull_fractal = pd.Series(np.logical_and.reduce([
        df['low'] < df['low'].shift(period) for period in periods
    ]), index=df.index)

    return bear_fractal, bull_fractal

An alternative idea is to use Series.rolling() with a window size of 5 and check if the center value in each window is the max (bear) or min (bull):
def roll(df):
    bear_fractal = df['high'].rolling(5, center=True).apply(lambda x: x[2] == max(x), raw=True)
    bull_fractal = df['low'].rolling(5, center=True).apply(lambda x: x[2] == min(x), raw=True)
    return bear_fractal, bull_fractal

The rolling() code is more concise, but it turns out your shift() version scales better (memory permitting)!


1-dimensional and 2-dimensional Peak Finding Algorithm I have the following code for a peak finding algorithm in Python 3.4.3. A peak is an element that is not smaller than its neighbors.

def peak1d(array):
    '''This function recursively finds the peak in an array
       by dividing the array into 2 repeatedly and choosning
       sides.

       Complexity: O(log n)'''

    mid = len(array)//2

    if mid > 0 and array[mid] < array[mid-1]:
        return peak1d(array[:mid])

    elif mid < len(array)-1 and array[mid] < array[mid+1]:
        return peak1d(array[mid:])

    else:
        return array[mid]

def peak2d(array):
    '''This function finds the peak in a 2D array by the
       recursive method.

       Complexity: O(n log m)'''

    n = len(array)
    m = len(array[0])

    j = m//2

    row = [i[j] for i in array]

    i = row.index(max(row))

    print(i, j)

    if j > 0 and array[i][j] < array[i][j-1]:
        return peak2d([row[:j] for row in array])

    elif j < m - 1 and array[i][j] < array[i][j+1]:
        return peak2d([row[j:] for row in array])

    else:
        return array[i][j]

I think that I could utilize the first function in 2D peak finding but I don't know if it's upto the best practices. Also, can you suggest any methods to make my program faster and better.

Just another thought, I believe it doesn't matter if we transpose the array. The peak will remain the same. So should I transpose the array to reduce the complexity at times.

Just reviewing peak1d.

It's not clear from the docstring what kind of object array is. If it might be a list, then the complexity is actually \$O(n)\$, because slicing a list makes a copy.

The copy in array[:mid] or array[mid:] can be avoided by maintaining search bounds instead:

def peak1d(array):
    """Return a peak in array."""
    def peak(start, stop):
        mid = (start + stop) // 2
        if mid > 0 and array[mid] < array[mid-1]:
            return peak(start, mid)
        elif mid < len(array) - 1 and array[mid] < array[mid+1]:
            return peak(mid, stop)
        else:
            return array[mid]
    return peak(0, len(array))

Python doesn't do tail recursion elimination, so the function would be a bit faster if you eliminated the recursion:

def peak1d(array):
    """Return a peak in array."""
    start, stop = 0, len(array)
    while True:
        mid = (start + stop) // 2
        if mid > 0 and array[mid] < array[mid-1]:
            stop = mid
        elif mid < len(array) - 1 and array[mid] < array[mid+1]:
            start = mid
        else:
            return array[mid]


Counting ambiguous Morse Code encodings, with and without Java Streams Unique Morse Code Words

  International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

  For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

  Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cab" can be written as "-.-.-....-", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.

  Return the number of different transformations among all words we have.

  Example:

  Input: words = ["gin", "zen", "gig", "msg"]
  Output: 2
  Explanation:
  The transformation of each word is:

  "gin" → "--...-."
  "zen" → "--...-."
  "gig" → "--...--."
  "msg" → "--...--."

  There are 2 different transformations, "--...-." and "--...--.".

  Note:

  The length of words will be at most 100.
  Each words[i] will have length in range [1, 12].
  words[i] will only consist of lowercase letters.

My approach:

import java.util.*;

    class Solution {
        public int uniqueMorseRepresentations(String[] words) {

            HashMap<String,String> morseMap = new HashMap<>(26);
                       String [] morseWords = new String[] {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

        HashSet<String> uniqCode = new HashSet<>();
        String morse = "";
        int ind;

        for( int i = 0; i < words.length; i++ )
        {
            morse = "";
            for( int j = 0; j < words[i].length(); j++ )
            {
                ind = ((int)words[i].charAt(j)) - 97;
                morse += morseWords[ind];
            }
            uniqCode.add(morse);
        }

            return uniqCode.size();

        }
    }

A 2nd approach using Java Stream:

public int uniqueMorseRepresentations(String[] words) {
        Set<String> res = Arrays.stream(words).map(i -> getMC(i)).collect(Collectors.toSet());
        return res.size();
    }
    private String getMC(String str) {
        String[] mCode = {".-","-...","-.-.","-..",".","..-.","--.","....","..",
                          ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
                          "...","-","..-","...-",".--","-..-","-.--","--.."};
        return str.chars().mapToObj(ch -> mCode[(char)ch % 97]).reduce("", String::concat);
    }

With regards to the above code snippets, I have the following questions:

Which approach is better according to an interviewer?
What can be improved in the 1st approach?
Does the 2nd approach sacrifice readability for succintness?
Is there a better method, eg StringBuilder in place of string that can speed up the solution of the first approach?

Well, I do not want to be the one always hammering on using Streams, but your second solution was almost immediatly clear to me, whereas the first was not. It does help that with the second one you split it up into methods, a very good thing!

Nontheless, I still think you can improve the second solution:

First, I would save the morse code mapping in a field, as it is really a constant thing.
Second, collecting to a Set is not really necessary. A Stream has a count method, so you can use that. Of course, this will result in a wrong answer, because we only want to count the distinct number of morse code strings. How do we solve it? Call distinct first!
There is really no reason to shorten method names, nor variables. Use clear, useful names. Instead of getMC, use toMorseCode for example.
In this particular case, I think there is a slightly better way to calculate the index out of a character, namely subtracting with 'a', which also has an integer value of 97 but now I think it is perfectly clear what is happening, i.e. 'a' = 0, 'b' = 1, ....

Putting it all together, with a method reference here and a static import there:

import static java.util.Arrays.stream;
import static java.util.stream.Collectors.joining;

public final class Morse {

    private static final String[] CODE_TABLE = {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
            ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
            "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
    };

    public static long countUniqueMorseRepresentations(final String[] words) {
        return stream(words).map(Morse::toMorseCode).distinct().count();
    }

    private static String toMorseCode(final String string) {
        return string.chars().mapToObj(character -> CODE_TABLE[character - 'a']).collect(joining(""));
    }
}

A short comment about your first approach, using a StringBuilder would be a good thing, because concatenating Strings with + each time builds a new String object, whereas with a StringBuilder, you would only make a new String when you concatenated all parts.

In this very case though, pure performance wise, it might get optimized under the hood to use a StringBuilder anyway.


JavaScript function to get DOM elements by any attribute I needed to write a function today in JavaScript that would return all elements based on a given attribute.

e.g retrieve all elements that have an id attribute in them.

The function I wrote for this is as follows:

function getElements(attrib) {
    // get all dom elements
    var elements = document.getElementsByTagName("*");
    // initialize array to put matching elements into
    var foundelements = [];

    // loop through all elements in document
    for (var i = 0; i < elements.length; i++) {
        // check to see if element has any attributes
        if (elements[i].attributes.length > 0) {
            // loop through element's attributes  and add it to array if it matches attribute from argument
            for (var x = 0; x < elements[i].attributes.length; x++) {
                if (elements[i].attributes[x].name === attrib) {
                    foundelements.push(elements[i]);
                }
            }
        }
    }
    return foundelements;
}

Looking at this, I am sure it could be written a great deal better. Any feedback would be much appreciated!

querySelectorAll

First off, if you're only dealing with relatively modern browsers (basically anything above IE7), you can use querySelectorAll, which is the fastest and easiest method to go about this:

document.querySelectorAll('[' + attrib + ']');

Here's the fiddle: http://jsfiddle.net/rc6Pq/

Sizzle

If you're stuck having to support IE7 and below, then you might as well just include the Sizzle selector engine, since you're bound to be using some additional selectors in the future. Once you include the Sizzle script in your page, you could then just use it in a similar fashion to the native querySelectorAll:

Sizzle('[' + attrib + ']');

Here's the fiddle: http://jsfiddle.net/rc6Pq/1/

jQuery

If you're already using jQuery on the page, you don't have to use Sizzle separately, since jQuery has Sizzle incorporated within it. If that's the case, just use this:

$('[' + attrib + ']').get();

Here's the fiddle: http://jsfiddle.net/rc6Pq/2/


What improvements can I make to this table filtering jQuery Plugin? This plugin is meant to filter through a table based on column header text that matches options given to it.
check it out here: Filter Table Plugin

Plugin code below for reference:

//framework from http://jqueryboilerplate.com/
; (function ($, window, document, undefined) {

    var pluginName = "filterTable",
        defaults = {
        };
    function Plugin(element, options) {
        this.element = element;

        this.options = $.extend({}, defaults, options);

        this._defaults = defaults;
        this._name = pluginName;

        this.init();
    }

    Plugin.prototype = {

        init: function () {

            $el = $(this.element);
            $table = $('#' + $el.data('filtertable'));
            var filterColumnNames = ($el.attr('data-filtercolumns')).split(',');
            var filterColumns = new Array();
            var altRowCSS = $el.data('filteralternatingcss');

            //get the column index of the column we'll be filtering on
            $table.find('th').each(function (i) {
                for (j in filterColumnNames) {
                    if ($(this).text().trim() == filterColumnNames[j]) {
                        filterColumns.push(i + 1);
                    }
                }
            });

            $el.keyup(function () {
                var query = $(this).val();
                var numDisplayed = 0;
                //remove any no result warnings
                $table.find('#noResultsRow').remove();
                //hide all rows
                $table.find('tr').removeClass(altRowCSS).hide();
                //show the header row
                $table.find('tr:first').show();
                for (i in filterColumns) {
                    $table.find('tr td:nth-child(' + filterColumns[i] + ')').each(function () {
                        if ($(this).text().toLowerCase().indexOf(query.toLowerCase()) >= 0) {
                            $(this).parent().show();
                            numDisplayed++;
                        }
                    });
                }
                if (numDisplayed == 0) {
                    $tr = $('<tr>');
                    $tr.attr('id', 'noResultsRow');
                    $td = $('<td>').attr('colspan', $table.children('tbody').children('tr').children('td').length);
                    $td.html('No results for filter "' + query + '."');
                    $td.css({ textAlign: 'center' });
                    $tr.append($td);
                    $table.children('tbody').append($tr);
                }
                $table.find('tr:visible :odd').addClass(altRowCSS);
            });
            $el.keyup();
        },
    };

    $.fn[pluginName] = function (options) {
        return this.each(function () {
            if (!$.data(this, "plugin_" + pluginName)) {
                $.data(this, "plugin_" + pluginName, new Plugin(this, options));
            }
        });
    };

})(jQuery, window, document);

Any improvements I can make?

You have:

this._defaults = defaults;

This is redundant as the declaration :

var pluginName = "filterTable",
    defaults = {
    };

Can be accessed anywhere in your plugin.
Declare all variables that you use. This is a really good practice to have change lines like:

 $el = $(this.element);
 $table = $('#' + $el.data('filtertable'));

to:

var $el = $(this.element);
var $table = $('#' + $el.data('filtertable'));

JavaScript will let you use them without but you'll run into issues otherwise.
Variables need meaningful names so their lives don't seem meaningless and they despair.

  Invective! Verb your expletive nouns!

$table.find('th').each(function (i)
{
    for (j in filterColumnNames)
    {
        if ($(this).text().trim() == filterColumnNames[j])
        {
             filterColumns.push(i + 1);
        }
    }
 });

What is i? index? columnIndex?
What is j? currentColumnName?


Queue with std::vector How can I improve this code?

template<class T>
class Queue {
public:
    Queue(const std::initializer_list<T>& i) :elem{i} {}
    int size() const {
        return elem.size();
    }
    bool empty() const {
        return elem.empty();
    }
    void enqueue(T&&);
    void dequeue();
    T peek();
    T& operator[](std::size_t);
    typename std::vector <T>::iterator begin() {
        return elem.begin();
    }
    typename std::vector <T>::iterator end() {
        return elem.end();
    }

private:
    std::vector<T> elem;
};

template<class T>
void Queue<T>::enqueue(T&& t) {
    elem.push_back(t);
}

template<class T>
void Queue<T>::dequeue() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    elem.erase(elem.begin());
}

template<class T>
T Queue<T>::peek() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    return elem.front();
}

template<class T>
T& Queue<T>::operator[](std::size_t i) {
    if (empty() || i < 0 || i >= size()) {
        throw std::out_of_range("underflow");
    }
    return elem[i];
}

I assume that you are familiar with std::queue and std::deque and wrote this class as a reinventing-the-wheel exercise.

There are a few mainly aesthetic points that you could improve:

int size() is better if returning a std::size_t, which is the underlaying type returned by vector::size().
Keep parameter names in function prototypes, it helps self-documenting the code.
T peek() doesn't change any internal state, so it should be const too.
operator[] should be provided with two overloads, const and non-const:

T& operator[](std::size_t index);
const T& operator[](std::size_t index) const;

Otherwise you won't be able to access data in a const Queue<T>. The same thing applies to begin()/end(). You will have to provide both const and non-const versions. This is purely boilerplate code, but C++ doesn't offer a better solution.
This excessively long name: typename std::vector <T>::iterator should be replaced by a typedef or using alias:

using iterator = std::vector<T>::iterator;

// Then you simply use `iterator` now:
iterator begin() { ... }

Shouldn't you provide a constructor that takes no arguments? It is very likely that you will want to declare an empty queue at some point. A default constructor should also do:

Queue() = default;


Form validation library Background:

After reading this thought provoking book I decided to write a small library as an exercise.

goog.require('goog.structs.Map');

var MyModule = {};

MyModule.FormHelper = {
  /** @type {?Element} */
  form: null,
  /** @type {goog.structs.Map<string, string>} */
  errors: {},

  /** @param {!Element} element */
  init: function(formElement) {
    this.form = formElement;
  },

  /**
   * @param {!Element} element
   * @return {!Array<goog.structs.Map<string, Object>>}
   */
  getElementAttributes: function(element) {
    if (!element) return [];
    return [].slice.call(element.attributes).map(function(attr) {
      return {[attr.name]: attr.value};
    });
  },

  /**
   * @param {string} filterOn
   * @return {!Array<!Element>}
   */
  filterElements: function(filterOn) {
    return [].slice.call(this.form.elements).filter(function(element) {
      return element.hasAttribute(filterOn);
    });
  }
};

MyModule.Form = Object.create(MyModule.FormHelper);

MyModule.Form.validate = function() {
  /** @type {!Array<!Element>} */
  var elements = this.getRequiredElements();
  elements.reduce(function(map, element) {
    if (element.value == '') {
      map[element.name] = 'Required field cannot be empty';
    }
    return map;
  }, this.errors);
};

MyModule.Form.getRequiredElements = function() {
  return this.filterElements('required');
};

MyModule.createForm = function(name) {
  /** @type {!Element} */
  var formElement = document.forms[name];
  if (!formElement) {
    throw new Error('Form not found.');
  }
  var form = Object.create(MyModule.Form);
  form.init(formElement);
  return form;
};

var contactForm;
var callback = function(e) {
  e.preventDefault()
  contactForm.validate();
  console.log(contactForm.errors);
}

window.onload = function () {
  contactForm = MyModule.createForm('ContactForm');
  contactForm.form.addEventListener("submit", callback, false);  //Modern browsers
}

I am using Google closure for type checking and advance code optimizations.

I want to check if I am following a good object oriented design and practices?

Update 1

;(function(global, doc, lib) {
  var Form = {};

  Form.create = function(name) {
    var form = doc.forms[name];
    if (!form) {
      throw new Error('Form not found.');
    }
    this.formElement = form;
  };

  Form.elements = function() {
    return this.formElement.elements;
  };

  Form.filter = function(attr) {
    return [].slice.call(this.elements()).filter(function(element) {
      return element.hasAttribute(attr);
    });
  };

  Form.getAttributes = function(element) {
    if (!element) return [];
    return [].slice.call(element.attributes).map(function(attr) {
      return {[attr.name]: attr.value};
    });
  };

  Form.validate = function(formName) {
    var elements = this.filter('required');
    elements.reduce(function(error, element) {
      if (element.value == '') {
        error[element.name] = 'Required field cannot be empty';
      }
      return error;
    }, this.errors);
  };

  lib.validate = function(formName) {
    var form = Object.create(Form);
    form.create(formName);
    form.errors = [];
    form.validate();
    return form;
  };

})(window, document, window.lib || (window.lib = {}));

window.onload = function() {
  console.log(lib);
  console.log(lib.validate('foo').errors);
};

Global variables

I know this isn't part of the module and probably just throwaway code, but you should restructure the module usage to avoid making global variables contactForm and callback:

    window.onload = function () {
      var contactForm = MyModule.createForm('ContactForm');
      contactForm.form.addEventListener("submit", function onSubmit(e) {
        e.preventDefault()
        contactForm.validate();
        console.log(contactForm.errors);
      }, false);  //Modern browsers
    }

Organization of properties between prototypes

I'm not sure why you'd divide up methods and properties between FormHelper and Form, as they seem to perform very similar functionality. I'd combine them into a single Form object; that's the only prototype you need.

This may seem too simple, but your module solves a simple problem. A more complicated module that would benefit from delegation between multiple prototypes would be one that has multiple types of Element prototypes, with some validation functions shared between Elements and some specific to particular types.

form prototype property

I don't think you need/want the form: null property on the prototype object. Even though init is a method of the prototype, it's assigning form to the base object (also named form) that exists in the submit handler, and that's what you want - a shared form property would make multiple Forms impossible.

Also, a subjective point: I'd rename this property to formElement or just element, since there are too many forms and Forms running around this code.

I hope this helps! Kyle Simpson's YDKJS books made me think as well, and with ES6 classes growing more common every day, I often wonder how this explicitly prototype-based JavaScript style can coexist with the classes Simpson discredited.


Fastest computation of N likelihoods on normal distributions In the context of a Gibbs sampler, I profiled my code and my major bottleneck is the following:

I need to compute the likelihood of N points assuming they have been drawn from N normal distributions (with different means but same variance).

Here are two ways to compute it:

import numpy as np
from scipy.stats import multivariate_normal
from scipy.stats import norm

# Toy data
y = np.random.uniform(low=-1, high=1, size=100) # data points
loc = np.zeros(len(y)) # means

# Two alternatives
%timeit multivariate_normal.logpdf(y, mean=loc, cov=1)
%timeit sum(norm.logpdf(y, loc=loc, scale=1))

The first: use the recently implemented multivariate_normal of scipy. Build the equivalent N-dimensional gaussian and compute the (log)probability of a N-dimensional y.

1000 loops, best of 3: 1.33 ms per loop
The second: use the traditional norm function of scipy. Compute the individual (log)probability of every point y and then sum the results.

10000 loops, best of 3: 130 µs per loop

Since this is part of a Gibbs sampler, I need to repeat this computation around 10.000 times, and therefore I need it to be as fast as possible.

How can I improve it?

(either from python or calling Cython, R or whatever)

You should use a line profiler tool to examine what the slowest parts of the code are.  It sounds like you did that for your own code, but you could keep going and profile the source code that NumPy and SciPy use when calculating your quantity of interest.  The [Line profiler](https://pypi.python.org/pypi/line_profiler/) module is my favorite.

import numpy as np
from scipy.stats import multivariate_normal
from scipy.stats import norm
%lprun -f norm.logpdf norm.logpdf(x=np.random.random(1000000), \
                                  loc=np.random.random(1000000), \
                                  scale = np.random.random())

Timer unit: 1e-06 s

Total time: 0.14831 s
File: /opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/stats/_distn_infrastructure.py
Function: logpdf at line 1578

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  1578                                               def logpdf(self, x, *args, **kwds):
  1579                                                   """
  1580                                                   Log of the probability density function at x of the given RV.
  1581
  1582                                                   This uses a more numerically accurate calculation if available.
  1583
  1584                                                   Parameters
  1585                                                   ----------
  1586                                                   x : array_like
  1587                                                       quantiles
  1588                                                   arg1, arg2, arg3,... : array_like
  1589                                                       The shape parameter(s) for the distribution (see docstring of the
  1590                                                       instance object for more information)
  1591                                                   loc : array_like, optional
  1592                                                       location parameter (default=0)
  1593                                                   scale : array_like, optional
  1594                                                       scale parameter (default=1)
  1595
  1596                                                   Returns
  1597                                                   -------
  1598                                                   logpdf : array_like
  1599                                                       Log of the probability density function evaluated at x
  1600
  1601                                                   """
  1602         1           14     14.0      0.0          args, loc, scale = self._parse_args(*args, **kwds)
  1603         1           23     23.0      0.0          x, loc, scale = map(asarray, (x, loc, scale))
  1604         1            2      2.0      0.0          args = tuple(map(asarray, args))
  1605         1        13706  13706.0      9.2          x = asarray((x-loc)*1.0/scale)
  1606         1           33     33.0      0.0          cond0 = self._argcheck(*args) & (scale > 0)
  1607         1         5331   5331.0      3.6          cond1 = (scale > 0) & (x >= self.a) & (x <= self.b)
  1608         1         5625   5625.0      3.8          cond = cond0 & cond1
  1609         1           84     84.0      0.1          output = empty(shape(cond), 'd')
  1610         1         6029   6029.0      4.1          output.fill(NINF)
  1611         1        11459  11459.0      7.7          putmask(output, (1-cond0)+np.isnan(x), self.badvalue)
  1612         1         1093   1093.0      0.7          if any(cond):
  1613         1        58499  58499.0     39.4              goodargs = argsreduce(cond, *((x,)+args+(scale,)))
  1614         1            6      6.0      0.0              scale, goodargs = goodargs[-1], goodargs[:-1]
  1615         1        46401  46401.0     31.3              place(output, cond, self._logpdf(*goodargs) - log(scale))
  1616         1            4      4.0      0.0          if output.ndim == 0:
  1617                                                       return output[()]
  1618         1            1      1.0      0.0          return output

It looks like a not-insignificant amount of time is being spent checking and removing invalid arguments from the function input.  If you can be sure you will never need to use that feature, just write your own function to calculate the logpdf.

Plus, if you are going to be multiplying probabilities (i.e. adding log probabilities), you could use algebra to simplify and factor out common terms from the summand for the normal distribution's pdf.  That will lower the number of function calls to np.log etc.  I did this in a hurry, so I probably made a math mistake, but:

def my_logpdf_sum(x, loc, scale):
    root2 = np.sqrt(2)
    root2pi = np.sqrt(2*np.pi)
    prefactor = - x.size * np.log(scale * root2pi)
    summand = -np.square((x - loc)/(root2 * scale))
    return  prefactor + summand.sum()

# toy data
y = np.random.uniform(low=-1, high=1, size=1000) # data points
loc = np.zeros(y.shape)

# timing
%timeit multivariate_normal.logpdf(y, mean=loc, cov=1)
%timeit np.sum(norm.logpdf(y, loc=loc, scale=1))
%timeit my_logpdf_sum(y, loc, 1)
1 loops, best of 3: 156 ms per loop
10000 loops, best of 3: 125 µs per loop
The slowest run took 4.55 times longer than the fastest. This could mean that an intermediate result is being cached
100000 loops, best of 3: 16.3 µs per loop


Island perimeter code challenge in Java Problem:

  Source (with example): https://leetcode.com/problems/island-perimeter/

  You are given a map in form of a two-dimensional integer grid where 1
  represents land and 0 represents water.

  Grid cells are connected horizontally/vertically (not diagonally). The
  grid is completely surrounded by water, and there is exactly one
  island (i.e., one or more connected land cells).

  The island doesn't have "lakes" (water inside that isn't connected to
  the water around the island). One cell is a square with side length 1.
  The grid is rectangular, width and height don't exceed 100. Determine
  the perimeter of the island.

Below is my solution. I haven't coded in Java since college and I'm trying to pick it up again. How is my style and is there any new Java features I can apply to the method to make it more concise? Thank you in advance!

Code:

class Solution {
    private int m;
    private int n;

    public int islandPerimeter(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int perimeter = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    perimeter += getPerimeter(i, j, grid);
                }
            }
        }
        return perimeter;
    }

    private int getPerimeter(int i, int j, int[][] grid) {
        int perimeter = 0;
        if (i == 0 || grid[i-1][j] == 0) {
            perimeter++;
        }
        if (j == 0 || grid[i][j-1] == 0) {
            perimeter++;
        }
        if (i == m-1 || grid[i+1][j] == 0) {
            perimeter++;
        }
        if (j == n-1 || grid[i][j+1] == 0) {
            perimeter++;
        }
        return perimeter;
    }
}

Instead of looking for cool new features of Java i would strongly suggest that you concentrate on the basics of Java: Objects:

Think in Objects:

So far you have identified these Objects: Map, a Cell and an Island - so make some Objects of that type.

Map map = new Map(int[][] src);
Island island = map.extractIsland();
int diameter = island.getPerimater();

the Map needs some methods to properly extract the island

Cell cell = getCellAt(int x, int y);

and a method to gain relationship between each Cells on the map:

List<Cell> getNeighbours(Cell center);

and some elementary methods on the Cell class

boolean isWater();
boolean isLand();
int getAmountCoasts();

if you would have these elementary Objects you can simply create readable Code - see this example:

Cell center; //yes, here center.isLand() = true
List<Cell> neigbour = map.getNeighbours(center);
for (Cell neigbour: neigbours){
    if (neigbour.isWater()){
        center.addCoast();
    }
}

once you are here you can use features from java 8

List<Cell> landCells = cells.stream.filter(Cell::isLand).collect(CollectorsToList());
int perimeter = landCells.stream.mapToInt(Cell::.getAmountCoasts).sum();

Hint: you better let the Island class handle that, see first hints - Responsibility for coastLine is within the Island class!)

NOTE:

it's hard to think in objects whenever you try minimal code snippets as suggested from leet code. if minimal code is required, look maybe you are interested at CodeGolf...


What docblock definition on this function will satisfy PHPLint? /**
 * Implements hook_field_validate().
 *
 * @param string $entity_type
 * @param object $entity
 * @param array $field
 * @param array $instance
 * @param array $langcode
 * @param array $items
 * @param array $errors
 *
 * @return void
 */
function field_validate($entity_type, $entity, $field, $instance, $langcode, $items, &$errors) {
  foreach ($items as $delta => $item) {
    if (!empty($item['active'])) { /* ... */ }
  }
}

The code above works well enough, but I would like to apply some static analysis on it. Enter phplint, which doesn't like the $item['active'] check. It says:

  Warning: can't check usage of `[' applied to a value of type mixed.

The warning makes sense, if I don't declare more details about my array, PHPLint won't know if the []'s are applicable. My problem comes up when I read the array documentation for PHPLint. I don't understand how I'm supposed to change the doc-block to properly describe the array.

Array structure with example data:

0 => array('active' => 1)
1 => array('active' => 0)
2 => array('active' => 1)
3 => array('active' => 0)

Ok, did not noticed that, then:

@param int[int][string] $items

foreach($items as $k => $e){...}

here $k is int, $e is int[string].

In the general case, if

@param T[I1][I2][I3] $items

then

foreach($items as $k => $e){...}

yields $k of type I1 and $e of type T[I2][I3].


C++ Crypto:Part 3-pbkdf2 Looking around for modern Crypto libraries.
Could not find anything good.
I know I probably did this all wrong so work with me here. There will be four different reviews for four structures that build on each other:

Hashing
Hashed Key
Password Key
Salted Challenge Response

This review is for an implementation of pbkdf2 implementation. This is a way of using HMAC that allows you to make incrementally more expensive to create the hash on failures. The idea is that you can slow down attacks by making it harder to make lots of guesses.
The data structures and implementation presented in these questions are based on RFC2104 and this post on codeproject.
Usage Example
Digest<Pbkdf2<HMac<Sha1>>>    digest;
Pbkdf2<HMac<Sha1>>            pbkdf2;

pbkdf2.hash("The password", "A Salt", 2048, digest);

pbkdf2.h
#ifndef THORS_ANVIL_CRYPTO_PBKDF2_H
#define THORS_ANVIL_CRYPTO_PBKDF2_H

#include "hmac.h"
#include <string>

// RFC-2898 PKCS #5: Password-Based Cryptography Specification Version 2.0

namespace ThorsAnvil::Crypto
{

// Look in hmac.h for good examples of PRF
// ThorsAnvil::Crypto::HMac
template<typename PRF>
struct Pbkdf2
{
    static constexpr std::size_t digestSize = PRF::digestSize;
    using DigestStore    = typename PRF::DigestStore;

    void hash(std::string const& password, std::string const& salt, long iter, DigestStore& digest)
    {
#pragma vera-pushoff
        using namespace std::string_literals;
#pragma vera-pop
        PRF             prf;
        DigestStore     tmp;

        prf.hash(password, salt + "\x00\x00\x00\x01"s, tmp);
        std::copy(std::begin(tmp), std::end(tmp), std::begin(digest));

        for (int loop = 1; loop < iter; ++loop)
        {
            prf.hash(password, tmp.view(), tmp);
            for (std::size_t loop = 0; loop < digestSize; ++loop)
            {
                digest[loop] = digest[loop] ^ tmp[loop];
            }
        }
    }
};

}

#endif

void hash(std::string const& password, std::string const& salt, long iter, DigestStore& digest)
...
for (int loop = 1; loop < iter; ++loop)
        ...
        for (std::size_t loop = 0; loop < digestSize; ++loop)

"A long an int and a std::size_t all walked into a bar..." couldn't they all be std::size_t?
Also, overriding the loop variable is unnecessarily confusing.

    std::copy(std::begin(tmp), std::end(tmp), std::begin(digest));

I feel like this could just be digest = tmp; with an appropriate assignment operator.

salt + "\x00\x00\x00\x01"s

Could this be a named constant (or even a named function)? Or maybe add a comment to explain why this is here.

            digest[loop] = digest[loop] ^ tmp[loop];

Nitpick: could use ^=

Perhaps the output should be a return value, not written to a reference?

I don't know enough about cryptography / security to assess the algorithm / safety aspects of this.


Print all nodes from root to leaves I've made a function to print all paths from root to all leaves in a binary search tree. I already have an insert function, which I haven't included in the code here as I felt it was irrelevant to the question. However, assume that it works. The code provided does produce the correct results. However, is it optimal? Is there room for improvement? Also, am I correct in thinking that the time complexity of this function is \$O(n)\$?

public static void printPaths(Node node,ArrayList<Integer> path) {

    if(node == null) {

        return;
    }

    path.add(node.value);

    if(node.leftChild == null && node.rightChild == null) {

        System.out.println(path);
        return;

    } else {

        printPaths(node.leftChild,new ArrayList<Integer>(path));
        printPaths(node.rightChild,new ArrayList<Integer>(path));
    }
}

public static void main(String[] args) {

    BST tree = new BST();

    tree.insertNode(20);
    tree.insertNode(8);
    tree.insertNode(22);
    tree.insertNode(12);
    tree.insertNode(10);
    tree.insertNode(14);
    tree.insertNode(4);

    ArrayList<Integer> path = new ArrayList<Integer>();

    printPaths(tree.root, path);

However, is it optimal?

I don't see wasted operations or opportunities to simplify the main logic itself.

However, "optimal" is a bit tricky term. To begin with, optimal in terms of what? In terms of readability, I think this is fine. In terms of performance, it's not great. Cloning the list of nodes for every path is not efficient. If performance is important to you, then you need to rethink that part. I can think of at least these alternative algorithms:

Use a shared linked list passed down to all method calls, that grows and shrinks as you go deeper or come back higher in the tree. This will avoid the duplication of the entire path.
Use a shared array list passed down to all method calls, and also pass the current depth n. In each method call, overwrite the n-th element, and print the list contents up until the n-th element. This will avoid the duplication of the entire path. For an extra boost, if you know in advance the depth of the tree, initialize the array list with a size big enough to contain the entire path, so it doesn't need to be resized along the way. In fact, instead of an array list, you could use a plain array for best performance.

  Is there room for improvement?

Use interface types in method signatures and variable declarations. For example:

printPaths(Node node, List<Integer> path) { ... }
List<Integer> path = new ArrayList<Integer>();

You can omit the return statement here:

if(node.leftChild == null && node.rightChild == null) {

    System.out.println(path);
    return;

} else {

    printPaths(node.leftChild,new ArrayList<Integer>(path));
    printPaths(node.rightChild,new ArrayList<Integer>(path));
}

And you should add a space in front of the opening paren of the if, and after commas in argument lists, like this:

if (node.leftChild == null && node.rightChild == null) {
    System.out.println(path);
} else {
    printPaths(node.leftChild, new ArrayList<Integer>(path));
    printPaths(node.rightChild, new ArrayList<Integer>(path));
}

Another alternative is to keep the return but drop the else:

if (node.leftChild == null && node.rightChild == null) {
    System.out.println(path);
    return;
}
printPaths(node.leftChild, new ArrayList<Integer>(path));
printPaths(node.rightChild, new ArrayList<Integer>(path));

  Also, am I correct in thinking that the time complexity of this function is O(n)?

Yes. You visit all the n nodes exactly once.

Unfortunately, no, as @Florian explains very well in his answer.
You might want to consider accepting his answer instead.