Proxy to hide singleton implementation I have a resource (e.g., current program configuration) that I want to handle in a single class instance, but want to hide the fact that there is, in effect, a singleton class by using a proxy class.

Reasons for not using a singleton directly include: don't want users of the class to have to change code if I move away from singleton implementation, and want to be able to have control over initialization and destruction order (which would be difficult with static classes, for example).

Additionally, this is a multithreaded application, so new instances of the Proxy class may be created at the same time (thus the mutex protecting creation of the Implementation).

The Proxy class is the proxy, and Impl class is the hidden singleton implementation. Note that I don't do anything special to Impl to make it a singleton. It is only a singleton because I track its existence in Proxy with a static member variable.

Proxy.h

#pragma once
#include <memory>
class Proxy {
 public:
   Proxy();
   void method1() //inline dispatch to hidden single class
   {
      data_->method1();
   }
 private:
   class Impl { //this class will be created once only
   public:
      void method1();
      Impl();
      ~Impl() = default;
   };
   std::shared_ptr<Impl> Make_Impl() const;
   const std::shared_ptr<Impl> data_{};
   inline static std::weak_ptr<Impl> impls_{}; //tracks whether Impl is created
};

Proxy.cpp

#include "Proxy.h"
#include <mutex>

Proxy::Proxy() : data_(Make_Impl()) {}

std::shared_ptr<Proxy::Impl> Proxy::Make_Impl() const
{ // note that impls_ may be accessed by another thread with non-const member function
  // (assignment) if it is running slightly ahead of this thread with an uninitialized impls_ so
  // need mutex before shared_ptr.lock call. if we use an atomic weak pointer (C++20) can call
  // shared_ptr.lock before mutex, check for success, and only run mutex (and try lock again) after
  // failure
   static std::mutex mtx;
   auto lock = std::lock_guard(mtx);
   std::shared_ptr<Impl> internal_data = impls_.lock(); //if implementation exists, assign to shared_ptr
   if (!internal_data) { //need to create implementation
      const auto new_impl(std::make_shared<Impl>());
      internal_data = new_impl;
      impls_ = new_impl;
   }
   return internal_data;
}

Proxy::Impl::Impl()
{
   // constructor for Impl here
}

void Proxy::Impl::method1()
{
   // the real method1 for the implementation
}

General comments welcome. Specific questions include:

is there a way to eliminate the pointer dereference that will occur with each call intended for the underlying implementation? (For example, When Proxy::method1 is called, that redirects to the underlying singleton class.)
Instead of using a static weak_ptr, is there a better way of tracking whether the Implementation exists?
Have others done anything like this? I'm concerned that I haven't seen this pattern (with smart pointers) documented anywhere. It makes me feel like I've gone "off the rails" with this code and have overlooked some problems with this approach.

Without locking, this works for me:

class proxy
{
public:
    proxy()
      : m_impl(make_impl()) {}

    void method()
    {
        m_impl.method();
    }
private:
    struct Impl
    {
        Impl() {}
        ~Impl() {}
        void method() {}
    };

    Impl& m_impl;
    Impl& make_impl()
    {
        static Impl impl;
        return impl;
    }
};

When locking, you need to synchronize access to the static impl in make_impl and you need to secure the call to m_impl.method().


JQuery/AJAX registration function reg(email, pass){
            $.ajax({
                url: "uman.php",
                type: "post",
                data:{email: email, password: pass},
                success: function(reply){
                if (reply == "success"){
                    $("#signinup").hide();
                    $("#donesucc").css("display","block");
                    console.log(reply);
                    }
                    if (reply == "duplicate"){
                        $("#signinup").hide();
                        $("#donedupe").css("display","block");
                    }
                }
            })
        }

Anything I should change? The PHP just echos the status of the query and Javascript takes that value and outputs the results through HTML.

What do you think about this?

var Request = {
    version: 1.0, //not needed but i like versioning things
    xproxy: function(type, url, data, callback, timeout, headers, contentType)
    {
        if (!timeout || timeout <= 0) { timeout = 15000; }
        $.ajax(
        {
            url: url,
            type: type,
            data: data,
            timeout: timeout,
            contentType: contentType,
            success:function(data)
            {
                if (callback != undefined) { callback(data); }
            },
            error:function(data)
            {
                if (callback != undefined) { callback(data); }
            },
            beforeSend: function(xhr)
            {
                //headers is a list with two items
                if(headers)
                {
                    xhr.setRequestHeader('secret-key', headers[0]);
                    xhr.setRequestHeader('api-key', headers[1]);
                }
            }
        });
    }
};

<script type="text/javascript">
var contentType = "applicaiton/json";
var url = "http://api.lastfm.com/get/data/";
var timeout = 1000*5; //five seconds
var requestType = "POST"; //GET, POST, DELETE, PUT

var header = [];
header.push("unique-guid");
header.push("23903820983");

var data = "{\"username\":\"james\"}"; //you should really deserialize this w/ a function
function callback(data)
{
   //do logic here
}
Request.xproxy(requestType, url, data, callback, timeout, header, contentType);
</script>


StringBuilder replacing specific characters I want to mask certain parts of an email address, and not to use regex at all.

Example:

  "testing@gmail.com" should become "t*****g@g***l.com"

Where the characters in the email (barring the first and last) become masked out, and no change to the domain.

        String email = "testing@gmail.com";
        StringBuilder sb = new StringBuilder(email);
        int mp = sb.lastIndexOf("@");
        int dp = sb.substring(mp).indexOf(".");
        for (int i = 1; i < sb.length(); i++) {
            if (i != mp && i != mp - 1 && i != mp + 1 && i != ((mp + dp) - 1) && i < (dp + mp)) {
                sb.setCharAt(i, '*');
            }
        }

I know this will fail if something unusual such as an @ in the domain, but that's fine.

It's mainly the if statement that seems awful to me, and wondering if I could shorten it to much simpler logic.

Online Demo

It's two consecutive ranges that you want to get replaced with *. So, I'd do two loops like:

    for (int i = 1; i < mp-1; i++) {
        sb.setCharAt(i, '*');
    }
    for (int i = mp+2; i < mp+dp-1; i++) {
        sb.setCharAt(i, '*');
    }

And add some sanity checks that the @ and . characters are present.


BTreeMap as a multimap in Rust I'm learning Rust so as an exercise I'm trying to write a datatype wrapping the builtin BTreeMap to allow it to store duplicates. Like the STL multimap type. The functions I have:

fn insert_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32, v: V)
{
    if map.contains_key(&k) {
        map.get_mut(&k).unwrap().push(v);
    } else {
        let mut vec: Vec<V> = Vec::new();
        vec.push(v);
        map.insert(k, vec);
    }
}

fn remove_dup_internal<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) -> usize {
    if map.contains_key(&k) {
        let ref mut vec = map.get_mut(&k).unwrap();
        vec.pop();
        return vec.len();
    }
    return 10;
}

fn remove_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) {
    if remove_dup_internal(map, k) == 0 {
        map.remove(&k);
    }
}

They work, but I would like to be able to parametrize the key too and not just the value. And the remove_dup / remove_dup_internal is because there  was a strange compiler error about borrowing I couldn't solve.

Idiomatic Rust style is to place braces on same line. When the function definition gets longer than one line then the brace lives on the next line all on its own.
Learn and love the entry API. Not only does the code end up clearer, it's faster too.
Don't use magic numbers. What is 10 supposed to mean? Why not 9 or 11 or 42? The very least you can do is to create a name for the magic value that indicates its purpose. However, there are usually better options in Rust. For example, if you need to indicate a potential absence of something, use Option.
It's very rare to use ref in a let pattern binding.
Avoid uses of unwrap, especially when they parallel existing code that ensures that the unwrap cannot fail. Usually there's a way to avoid duplicating the check.
Learn about transformative methods on Option and Result, map being the one used here.
Don't use an explicit return at the end of a function.

use std::collections::BTreeMap;

fn insert_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32, v: V) {
    map.entry(k).or_insert_with(Vec::new).push(v)
}

fn remove_dup_internal<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) -> Option<usize> {
    map.get_mut(&k).map(|vec| {
        vec.pop();
        vec.len()
    })
}

fn remove_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) {
    if remove_dup_internal(map, k) == Some(0) {
        map.remove(&k);
    }
}

Even better, the helper function isn't needed with the Entry API. We can also note that comparing the length against 0 is the same as the is_empty method:

use std::collections::btree_map::Entry;

fn remove_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) {
    if let Entry::Occupied(mut entry) = map.entry(k) {
        entry.get_mut().pop();
        if entry.get().is_empty() {
            entry.remove();
        }
    }
}

Now adding and removing a value each only require a single location computation and lookup.

Parameterizing the key can be done by:

Replacing i32 with K.
Adding K to the generic declaration list.
Following the compiler error message to restrict K to types that implement Ord.

use std::collections::{btree_map::Entry, BTreeMap};

fn insert_dup<K, V>(map: &mut BTreeMap<K, Vec<V>>, k: K, v: V)
where
    K: std::cmp::Ord,
{
    map.entry(k).or_insert_with(Vec::new).push(v)
}

fn remove_dup<K, V>(map: &mut BTreeMap<K, Vec<V>>, k: K)
where
    K: Ord,
{
    if let Entry::Occupied(mut entry) = map.entry(k) {
        entry.get_mut().pop();
        if entry.get().is_empty() {
            entry.remove();
        }
    }
}

  Any reason you are calling both entry.get and entry.get_mut in remove_dup?

This can be interpreted multiple ways:

"Why not call entry.get in both cases?" — because the chained pop needs a mutable receiver in order to do its work.
"Why not call entry.get_mut in both cases?" — this would compile, but the value doesn't need to be mutable for is_empty, and I find it better to opt-out of as much mutability as possible.
"Why not call entry.get_mut once and store it in variable?" — Now that non-lexical lifetimes are enabled, the straight-forward way works and you should do this. Before that, however,you would run into borrow checker issues because binding the result of get_mut to a variable will cause entry to be borrowed for the rest of the scope. This prevents using entry.remove:

if let Entry::Occupied(mut entry) = map.entry(k) {
    let vec = entry.get_mut();
    vec.pop();
    if vec.is_empty() {
        entry.remove();
    }
}

error[E0505]: cannot move out of `entry` because it is borrowed
  --> src/main.rs:17:13
   |
14 |         let vec = entry.get_mut();
   |                   ----- borrow of `entry` occurs here
...
17 |             entry.remove();
   |             ^^^^^ move out of `entry` occurs here

If get or get_mut were expensive, you could introduce a scope to constrain the borrow:

if let Entry::Occupied(mut entry) = map.entry(k) {
    let should_remove = {
        let vec = entry.get_mut();
        vec.pop();
        vec.is_empty()
    };
    if should_remove {
        entry.remove();
    }
}

However, I don't believe that get or get_mut are expensive.


Multiplication of any two matrices using lists and for in loop I've just started learning Python and after few lessons I grasped the idea of lists and loop and decided to create my first project.

Objective: Calculate multiplication of any two matrices from user's input.

The code is working as intended but as this is my first one, I would be happy for some hints as far what is written well and what is e.g. hard to read by someone, wrongly used method or unnecessary complication.

 I specifically wanted to stay within basic knowledge and not use for example NumPy for learning reason. There will be time for libraries in future.

Thanks all in advance and my code is below:

# This program multiplicates two matrices of any number of rows and columns.
# The matrix elements are filled by User
# The result is calculated and saved as list

print('MATRIX MULTIPLICATION\n')

# Ask user for dimensions of first matrix
r = int(input("Matrix1: Number of rows?: "))
c = int(input("Matrix1: Number of columns?: "))

# Print design of first Matrix for better understanding of elements' naming convention
print('''\nElements of matrix1:''')
element = ''                            # Later will be used to construct each row of the matrix
for vr in range(0, r):                  # vr - variable row
    for vc in range(0, c):              # vc - variable column
        element += 'M' + str(vr + 1) + str(vc + 1) + ' '
    print('|', element, '\b|')
    element = ''

# Create empty Matrix1 and fill it with user input element by element
Matrix1 = [[] for vr in range(0, r)]
for vr in range(0, r):
    Matrix1[vr] = [0 for vc in range(0, c)]

for vr in range(0, r):
    for vc in range(0, c):
        Matrix1[vr][vc] = int(input('M' + str(vr + 1) + str(vc + 1) + ': '))    # + 1 because vr and vc starts at 0 and we want elements be named from 1

# Ask the user for dimension of second matrix
v = int(input("Matrix2: Number of columns?: "))     # Only for columns since M2 rows = M1 columns by definition
print('''\nElements of matrix Matrix2:''')
element = ''
for vr in range(0, c):                  # vr in c because Matrix 2 must have the same number of rows as Matrix1 columns.
    for vc in range(0, v):
        element += 'M' + str(vr + 1) + str(vc + 1) + ' '
    print('|', element, '\b|')
    element = ''

# Create Empty Matrix2 and fill it with user input element by element
Matrix2 = [[] for vr in range(0, c)]
for vr in range(0, c):
    Matrix2[vr] = [0 for vc in range(0, v)]

for vr in range(0, c):
    for vc in range(0, v):
        Matrix2[vr][vc] = int(input('M' + str(vr + 1) + str(vc + 1) + ': '))

# Create empty Product Matrix for Result of multiplication of Matrix1 and Matrix2
Product = [[] for vr in range(0, r)]                # Number of rows defined by number of rows in Matrix1
for vr in range(0, r):
    Product[vr] = [0 for columns in range(v)]       # Number of columns defined by number of columns in Matrix2

# Calculate the Product of two tables
Products = 0            # dummy variable for calculating sum of product of each row and column
for vv in range(0, v):
    for vr in range(0, r):
        for vc in range(0, c):
            Products += Matrix1[vr][vc] * Matrix2[vc][vv]
        Product[vr][vv] = Products
        Products = 0        # clear the variable when looped for whole column of Matrix2

print('Matrix1: ', Matrix1)
print('Matrix2: ', Matrix2)
print('Result of Matrix Multiplication:', Product)

# Footnotes
print('\n\nCreated by: MK')
input('Press "Enter" to Exit')        # Easy way to Exit program If run from script

I have basically two comments:

Naming.
Use functions to follow the single responsibility principle.

Naming

Python has an official style-guide, PEP8. Some of its recommendations are:

Using lower_case for variables and functions, PascalCase for classes and ALL_CAPS for global constants.
To limit your line length to 80 (or at the most 120) characters

Your names which you use to iterate through the rows and columns are not clear at all. Why vc and vr (I guess the c and r stand for column and row, but what does the v stand for?)? Instead I would use rows and columns for the number of rows and columns and use i and j to iterate over them, because that is the convention used in mathematics when describing matrices.

Single responsibility principle

As for your actual code, you basically have four major responsibilities:

Asking the user for input
Creating a matrix
Calculating the matrix product
Printing a matrix scheme

I would make this into four functions:

def ask_user(message):
    while True:
        try:
            return int(input(message))
        except TypeError:
            pass

This function will ask the user the message until he inputs something that can be cast to an int.

def matrix_from_user():
    rows = ask_user("Number of rows?: ")
    columns = ask_user("Number of columns?: ")
    matrix = [[0] * columns for _ in range(rows)]
    for i in range(rows):
        for j in range(columns):
            matrix[i][j] = ask_user("M{}{}: ".format(i+1, j+1))
    return matrix

Here I used str.format to make the construction of the string easier.

def matrix_mul(matrix1, matrix2):
    rows, columns = len(matrix1), len(matrix2[0])
    matrix = [[0] * columns for _ in range(rows)]
    for i in range(rows):
        for j in range(columns):
            matrix[i][j] = sum(matrix1[i][k] * matrix2[k][j]
                               for k in range(len(matrix2)))
    return matrix

This is a straightforward implementation of the formula \$(AB)_{ij} = \sum_{k=1}^m A_{ik} B_{kj}\$ for two matrices \$A\$ and \$B\$. It uses the built-in sum function that takes an iterable to sum. This iterable is a generator comprehension here.

def matrix_print(matrix):
    print('\nElements of matrix:')
    rows, columns = len(matrix), len(matrix[0])
    for i in range(rows):
        row = ' '.join('M{}{}'.format(i + 1, j + 1) for j in range(columns))
        print('|', row, '|')

Here I used str.join to easily join an iterable of strings with a given delimiter (' ' here).

Your main program becomes then simply:

if __name__ == "__main__":
    matrix1 = matrix_from_user()
    matrix_print(matrix1)
    matrix2 = matrix_from_user()

    product = matrix_mul(matrix1, matrix2)

    print('Matrix1: ', matrix1)
    print('Matrix2: ', matrix2)
    print('Result of Matrix Multiplication:', product)

This code I put under an if __name__ == "__main__": guard which allows you to import this script from another script without this part of the code being run (so you get access to the functions).


Filter array with another array I want to output only the roles that contain the same group as the user.

// User can be part of many groups
const user = {
  groups: ["group2"]
};

// Roles can have many groups
// What you see here is the output or 2 different data source
// Thats why we have group duplication inside different role
const roles = [{
  name: "role1",
  groups: [{
    id: "group1"
  }]
}, {
  name: "role2",
  groups: [{
    id: "group1"
  }, {
    id: "group2"
  }]
}];

const result = roles.filter(role => role.groups.filter(group => user.groups.indexOf(group.id) > -1).length)
console.log(result);

Is there a better way by using reduce or something else?

This is little neater IMO.

// User can be part of many groups
const user = {
  groups: ["group2"]
};

// Roles can have many groups
// What you see here is the output or 2 different data source
// Thats why we have group duplication inside different role
const roles = [{
  name: "role1",
  groups: [{
    id: "group1"
  }]
}, {
  name: "role2",
  groups: [{
    id: "group1"
  }, {
    id: "group2"
  }]
}];

const result = roles.filter(role => role.groups.find(group => user.groups.includes(group.id)));
console.log(result);


Python - ternary operator or if statement? Which of these two alternatives is more readable?

token = map.get(token_str)
if not token:
   token = Course(token_str)
return token

or

token = map.get(token_str)
token if token else Course(token_str)

get() takes an optional second parameter, for a value to use if the key isn't present:

token = map.get(token_str, Course(token_str))

I think that one is clearly the best solution, unless you don't want to create and immediately throw away a Course object. In that case, I would use 'or':

token = map.get(token_str) or Course(token_str)

Both of these are only one line, that one line is quite readable, and there is no unnecessary repetition.

There is one third possible situation, in which you don't want to unnecessarily construct a Course instance, and you also can't rely on the values that are present to evaluate as True. Then 'or' wouldn't work correctly.

Then I would use an 'if' statement:

token = map.get(token_str)
if token is None:
    token = Course(token_str)

but that's personal preference. Something using 'in' is also fine:

token = map[token_str] if token_str in map else Course(token_str)

although of course that looks up token_str in map twice, so if you need to be really time efficient then don't do that.


Makefile for a C++ project using Boost, Eigen, and htslib I had a Makefile but it doesn't meet the "industry-standard expectation". That was feedback from my client. The old Makefile was rejected. Thus, I'm making a new one.

Here is the repository for my project.

My old Makefile:

# Boost C++ library
BOOST = /usr/local/include/boost_1_64_0

# Linear-algebra library
EIGEN = /usr/local/Cellar/eigen/3.2.8/include/eigen3

# HTSLIB library for BAM files
HTSLIB = /Users/tedwong/Sources/QA/htslib

# Where the header are
INCLUDE = src

EXEC         = anaquin
SOURCES      = $(wildcard src/*.cpp src/tools/*.cpp src/analyzers/*.cpp src/RnaQuin/*.cpp src/VarQuin/*.cpp src/MetaQuin/*.cpp src/data/*.cpp src/parsers/*.cpp src/writers/*.cpp src/stats/*.cpp src/cufflinks/*.cpp)
OBJECTS      = $(SOURCES:.cpp=.o)
OBJECTS_TEST = $(SOURCES_TEST:.cpp=.o)
SOURCES_LIB  = $(wildcard src/htslib/cram/*.c)
OBJECTS_LIB  = $(SOURCES_LIB:.c=.o)

$(EXEC): $(OBJECTS) $(OBJECTS_TEST) $(OBJECTS_LIB)
    g++ $(OBJECTS) $(OBJECTS_TEST) $(OBJECTS_LIB) -DBACKWARD_HAS_BFD -g -lpthread -lz -lhts -L $(HTSLIB) -o $(EXEC)

%.o: %.c
    gcc -g -c -DBACKWARD_HAS_BFD -I src/htslib -I $(INCLUDE) -I $(EIGEN) -I ${BOOST} $< -o $@

%.o: %.cpp
    g++ -g -DK_HACK -DBACKWARD_HAS_BFD -c -std=c++11 -I src/htslib -I src/stats -I $(INCLUDE) -I $(EIGEN) -I ${BOOST} $< -o $@

clean:
    rm -f $(EXEC) $(OBJECTS) $(OBJECTS_TEST)

My new Makefile:

#
# Please modify only BOOST, EIGEN and HTSLIB. You should be able to leave all other options intact. C++ compiler with C++11 support is mandatory.
#

# Boost C++ library
BOOST = /usr/local/include/boost_1_64_0

# Linear-algebra library
EIGEN = /usr/local/Cellar/eigen/3.2.8/include/eigen3

# HTSLIB library for reading BAM files
HTSLIB = /Users/tedwong/Sources/QA/htslib

CC     = g++
CFLAGS = -g -O2
CPPFLAGS = -c -std=c++11
DFLAGS =
#DFLAGS = -DBACKWARD_HAS_BFD # https://github.com/bombela/backward-cpp
LIBS   = -lpthread -lz -lhts

# Where the header are (no need to modify this)
INCLUDE = src

EXEC         = anaquin
SOURCES      = $(wildcard src/*.cpp src/tools/*.cpp src/analyzers/*.cpp src/RnaQuin/*.cpp src/VarQuin/*.cpp src/MetaQuin/*.cpp src/data/*.cpp src/parsers/*.cpp src/writers/*.cpp src/stats/*.cpp src/cufflinks/*.cpp)
OBJECTS      = $(SOURCES:.cpp=.o)
OBJECTS_TEST = $(SOURCES_TEST:.cpp=.o)
SOURCES_LIB  = $(wildcard src/htslib/cram/*.c)
OBJECTS_LIB  = $(SOURCES_LIB:.c=.o)

$(EXEC): $(OBJECTS) $(OBJECTS_TEST) $(OBJECTS_LIB)
    $(CC) $(OBJECTS) $(OBJECTS_TEST) $(OBJECTS_LIB) $(CFLAGS) $(DFLAGS) $(LIBS) -L $(HTSLIB) -o $(EXEC)

%.o: %.c
    $(CC) $(CFLAGS) -c $(DFLAGS) -I $(INCLUDE) -I $(EIGEN) -I ${BOOST} $< -o $@

%.o: %.cpp
    $(CC) $(CFLAGS) $(DFLAGS) $(CPPFLAGS) -I $(HTSLIB) -I src/stats -I $(INCLUDE) -I $(EIGEN) -I ${BOOST} $< -o $@

clean:
    rm -f $(EXEC) $(OBJECTS) $(OBJECTS_TEST)

Couple of things you do that don't match standards.

CXX is usually the C++ compiler
CC  is usually the C   compiler.

CXXFLAGS  are the flags that are applied to the C++ compiler.
CPPFLAGS  are the flags that are applied for the pre-processor.
          This usually means passed to both C and C++ compiler.

CFLAGS    are the flags passed to the C compiler.

LDDFLAGS  are the flags passed to the linker.

Why are you building the tests into your main executable?
Should the test application be generated as a seprate application that includes the normal objects (apart from main) and the test objects.

Why do you have libs outside your lib variable?

$(LIBS) -L $(HTSLIB)

You should have a line earlier in your make file like:

# This adds more libs to the current set of libs.
LIBS    += -L $(HTSLIB)

I am confused why you are including -I ${BOOST} for the C compiler but not the C++ compiler. I did not think there was anything in the boost that could be used by C (I could be wrong but seems strange).

The default rule for C/C++/Linking are:

$(CC)  $(CPPFLAGS) $(CFLAGS) -c
$(CXX) $(CPPFLAGS) $(CXXFLAGS) -c
$(CC)  $(LDFLAGS) n.o $(LOADLIBES) $(LDLIBS)

Unless you need to change these I would not. This means adding values to the existing variables.

Something like this (untested):

# Addition Packages.
SRC_PACKAGES = BOOST EIGEN
LIB_PACKAGES = HTSLIB

# Boost C++ library
ROOT_BOOST▸ = /usr/local/include/boost_1_64_0

# Linear-algebra library
ROOT_EIGEN = /usr/local/Cellar/eigen/3.2.8/include/eigen3

# HTSLIB library for reading BAM files
ROOT_HTSLIB = /Users/tedwong/Sources/QA/htslib

#
# Turn on BFD by compiling with
# make -DHASBFD=1
DFLAGS_1▸   = -DBACKWARD_HAS_BFD # https://github.com/bombela/backward-cpp
DFLAGS▸ ▸   = $(DFLAGS_$(HASBFD))

EXTRA_INCLUDE_DIR▸  = $(foreach loop, $(SRC_PACKAGES) $(LIB_PACKAGES), -I$(ROOT_$(loop)))
EXTRA_LIB_DIR▸  ▸   = $(foreach loop, $(LIB_PACKAGES),                 -L$(ROOT_$(loop)))

# Compiler
CXX▸▸   ▸   = g++
CC▸ ▸   ▸   = $(CXX)
CPPFLAGS▸   += -g -O2 $(EXTRAFLAGS) $(DFLAGS) -Isrc -Isrc/stats
CFLAGS▸ ▸   +=
CXXFLAGS▸   += -std=c++11

# Linker
LDFLAGS▸▸   += $(EXTRA_LIB_DIR)
LDLIBS▸ ▸   += -lpthread -lz -lhts

# Application
SRC_DIR▸▸   = src src/tools src/analyzers src/RnaQuin src/VarQuin src/MetaQuin src/data src/parsers src/writers src/stats src/cufflinks

EXEC        = anaquin
SOURCES     = $(wildcard $(foreach loop, $(SRC_DIR), $(loop)/*.cpp))
OBJECTS     = $(patsubst $(SOURCE), %.cpp, %.o)

$(EXEC): $(OBJECTS)

.PHONEY: clean
clean:
    $(RM) $(EXEC) $(OBJECTS) $(OBJECTS_TEST)


php Laravel - given a certain argument, call different function I am building a simple calendar with recurring events.

CalendarEvent.php

id
start_date

CalendarRecurringPattern.php

parent_id
pattern_type // daily, weekly, monthly, yearly ...

Using pattern_type i build each following occurrence starting from start_date, using a recursive function and Carbon::class. What bugs me is the function getNextOccurrence(), I'd like to refactor the if/else block because it's not very clean. Here it is:

use \Carbon\Carbon;
....

public function getNextOccurrence(Carbon $startDate) {

    $pattern_type = $this->getPatternType() // daily, weekly...

    if ($pattern_type == 'daily') {
        $startDate->addDay();
    } else if ($pattern_type == 'weekly') {
        $startDate->addWeek();
    } else if ($pattern_type == 'monthly') {
        $startDate->addMonth();
    } else if ($pattern_type == 'yearly') {
        $startDate->addYear();
    }

}

Thanks!

I don't personally see a problem with the way its currently structured as there aren't that many options, but you could do it a couple of other ways;

Option 1

Array function name mapping (hacky name I just came up with), you could do the following;

$functionMap = [
    "daily" => "addDay",
    "weekly" => "addWeek",
    "monthly" => "addMonth",
    "yearly" => "addYear"
];

if(!isset($functionMap[$pattern_type])){
    throw new \Exception("Can't find patern type $pattern_type", 1);
}

$startDate->$functionMap[$pattern_type]();

This might be seen as a sin by the PHP community but it works none the less

Option 2

You could use a switch which probably isn't a sin by the community.

switch ($pattern_type) {
    case "daily":
        // Do the daily task
        break;
    case "weekly":
        // Do the weekly task
        break;
    case "monthly":
        // Do the monthly task
        break;
    case "yearly":
        // Do the yearly task
        break;
    default:
        throw new \Exception("Can't find pattern type $pattern_type", 1);
}

Conclusion

I would add some exception / error that can be picked up if a non matched  pattern_type is passed.

I would also convert the "magic strings" E.G "daily" to constants in case you need to re-use, change or update them in the future!

In terms of line count;

your way 10 lines of code
option 1  11 lines of code
option 2  15 lines of code

The switch & if statements may have some advantages when doing code analysis aswel where the expected required input values can be picked up.


Trimming blank space from images I am working on scanned documents (ID card, Driver licenses, ...). The problem I faced while I apply some preprocessing on them is that the documents occupy just a small area of the image, all the rest area is whether white/blank space or noised space. For that reason I wanted to develop a Python code that automatically trims the unwanted area and keeps only the zone where the document is located (without I predefine the resolution). That's possible with using findContours() from OpenCV. However, not all the documents (especially the old ones) have  clear contour and not all the blank space is white, so this will not work.
The idea that came to me is:

Read the image and convert it to gray-scale.

Apply the bitwise_not() function from OpenCV to separate the background from the foreground.

Apply adaptive mean threshold to remove as much possible of noise (and eventually to whiten the background).
At this level, I have the background almost white and the document is in black but containing some white gaps.

I applied erosion to fill the gaps.

Read each row of the image and if 20% of it contains black, then keep it, if it is white, delete it. And do the same with each column of the image.

Crop the image according to the min and max of the index of the black lines and columns.

Here is my code with some comments:
import cv2
import numpy as np

def crop(filename):
    #Read the image
    img = cv2.imread(filename)
    #Convert to grayscale
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    #Separate the background from the foreground
    bit = cv2.bitwise_not(gray)
    #Apply adaptive mean thresholding
    amtImage = cv2.adaptiveThreshold(bit, 255, cv2.ADAPTIVE_THRESH_MEAN_C, cv2.THRESH_BINARY, 35, 15)
    #Apply erosion to fill the gaps
    kernel = np.ones((15,15),np.uint8)
    erosion = cv2.erode(amtImage,kernel,iterations = 2)
    #Take the height and width of the image
    (height, width) = img.shape[0:2]
    #Ignore the limits/extremities of the document (sometimes are black, so they distract the algorithm)
    image = erosion[50:height - 50, 50: width - 50]
    (nheight, nwidth) = image.shape[0:2]
    #Create a list to save the indexes of lines containing more than 20% of black.
    index = []
    for x in range (0, nheight):
        line = []

        for y in range(0, nwidth):
            line2 = []
            if (image[x, y] < 150):
                line.append(image[x, y])
        if (len(line) / nwidth > 0.2):
            index.append(x)
    #Create a list to save the indexes of columns containing more than 15% of black.
    index2 = []
    for a in range(0, nwidth):
        line2 = []
        for b in range(0, nheight):
            if image[b, a] < 150:
                line2.append(image[b, a])
        if (len(line2) / nheight > 0.15):
            index2.append(a)

    #Crop the original image according to the max and min of black lines and columns.
    img = img[min(index):max(index) + min(250, (height - max(index))* 10 // 11) , max(0, min(index2)): max(index2) + min(250, (width - max(index2)) * 10 // 11)]
    #Save the image
    cv2.imwrite('res_' + filename, img)

Here is an example. I used an image from the internet to avoid any confidentiality problem. It is to notice here that the image quality is much better (the white space does not contain noise) than the examples I work on.
Input: 1920x1080

Output: 801x623

I tested this code with different documents, and it works well. The problem is that it takes a lot of time to process a single document (because of the loops and reading each pixel of the image twice: once with lines and the second with columns). I am sure that it is possible to do some modifications to optimize the code and reduce the processing time. But I am very beginner with Python and code optimization.
Maybe using numpy to process the matrix calculations or optimizing the loops would improve the code quality.

Split the code

This long method does a lot of things:

it reads the file
preprocesses it
searches for the bounding box of the area of interest
crops the result
writes the result to a file

Better would be to split this into more parts. This way, you don't need to comment as much, but let the function names speak for themselves.

Comments

If you do feel the need to comment, you can do that in the docstring. If you want to comment on the code, explain why you do it, not how.

#Ignore the limits/extremities of the document (sometimes are black, so they distract the algorithm)

is a useful comment.

# Apply adaptive mean thresholding

is not. It doesn't explain what problem this adaptive thresholding solves, and how you got to the parameters you use: 255, ADAPTIVE_THRESH_MEAN_C, 35 and 15

Indexing

negative indices start counting from the back of a sequence, so

(height, width) = img.shape[0:2]
image = erosion[50:height - 50, 50: width - 50]

can be replaced by erosion[50:-50, 50:-50]

There is also no need to put the parentheses around the height, width tuple.

Magic numbers

There are a lot of magic number in your code: 15 and 35 in the adaptive threshold, 15 in the kerneling, 50 in the cropping,...

Better would be to give them names, and define them in the function or use them as parameters to pass into the function.

Keyword arguments

amtImage = cv2.adaptiveThreshold(bit, 255, cv2.ADAPTIVE_THRESH_MEAN_C, cv2.THRESH_BINARY, 35, 15)

would be a lot clearer as:

blocksize = 35
constant = 15
max_value = 255 # 8 bits
amtImage = cv2.adaptiveThreshold(
    src=bit,
    maxValue=max_value ,
    adaptiveMethod=cv2.ADAPTIVE_THRESH_MEAN_C,
    thresholdType=cv2.THRESH_BINARY,
    blockSize=blocksize ,
    C=constant,
)

Vectorizing

opencv uses numpy arrays internally, so you can use all the vectorisation goodies, instead of iterating over each pixel twice in python land.

bw_threshold = 150
limits = 0.2, 0.15

mask = image < bw_threshold
edges = []
for axis in (0, 1):
    count = mask.sum(axis=axis)
    limit = limits[axis] * image.shape[axis]
    index = np.where(count > limit)
    _min, _max = index[0][0], index[0][-1]
    edges.append((_min, _max))

does the same, but vectorized and about 1000 times faster.

Final result

def preproces_image(
    image,
    *,
    kernel_size=15,
    crop_side=50,
    blocksize=35,
    constant=15,
    max_value=255,
):
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    bit = cv2.bitwise_not(gray)
    image_adapted = cv2.adaptiveThreshold(
        src=bit,
        maxValue=max_value,
        adaptiveMethod=cv2.ADAPTIVE_THRESH_MEAN_C,
        thresholdType=cv2.THRESH_BINARY,
        blockSize=blocksize,
        C=constant,
    )
    kernel = np.ones((kernel_size, kernel_size), np.uint8)
    erosion = cv2.erode(image_adapted, kernel, iterations=2)
    return erosion[crop_side:-crop_side, crop_side:-crop_side]

def find_edges(image_preprocessed, *, bw_threshold=150, limits=(0.2, 0.15)):
    mask = image_preprocessed < bw_threshold
    edges = []
    for axis in (1, 0):
        count = mask.sum(axis=axis)
        limit = limits[axis] * image_preprocessed.shape[axis]
        index_ = np.where(count >= limit)
        _min, _max = index_[0][0], index_[0][-1]
        edges.append((_min, _max))
    return edges

def adapt_edges(edges, *, height, width):
    (x_min, x_max), (y_min, y_max) = edges
    x_min2 = x_min
    x_max2 = x_max + min(250, (height - x_max) * 10 // 11)
    # could do with less magic numbers
    y_min2 = max(0, y_min)
    y_max2 = y_max + min(250, (width - y_max) * 10 // 11)
    return (x_min2, x_max2), (y_min2, y_max2)

if __name__ == "__main__":

    filename_in = "NHnV7.png"
    filename_out = "res_NHnV7.png"

    image = cv2.imread(str(filename_in))
    height, width = image.shape[0:2]
    image_preprocessed = preproces_image(image)
    edges = find_edges(image_preprocessed)
    (x_min, x_max), (y_min, y_max) = adapt_edges(
        edges, height=height, width=width
    )
    image_cropped = image[x_min:x_max, y_min:y_max]
    cv2.imwrite(str(filename_out), image_cropped)


Lookup class to get descriptions of values Following yesterday's advice on my Customer class, I have now created a new class which is for looking up descriptions from a MySQL database. I have a Lookup table which contains type, name, value, and descriptions.

Here's a basic example of type = customer and name = state

Customer States

New Customer
Pending Approval
Approved / Active
Deleted

In this example if I pass in the parameters "customer", "state", and 2, the method will return "Pending Approval".

pdo.inc.php

<?php

// Version 0.1
// Last updated 08 Jun 2016

define('DB_CONFIG_HOST', 'localhost');
define('DB_CONFIG_DB', 'dev');
define('DB_CONFIG_USER', 'dev');
define('DB_CONFIG_PW', 'dev');
$dsn = 'mysql:host=' . DB_CONFIG_HOST . ';dbname=' . DB_CONFIG_DB . ';';
define('DB_CONFIG_DSN', $dsn);

try
{
    $pdo = new PDO(DB_CONFIG_DSN, DB_CONFIG_USER, DB_CONFIG_PW);
}
catch (PDOException $ex)
{
    error_log('Connection failed: ' . $ex->getMessage());
    die();
}

?>

lookup.class.php

<?php

// Version 0.1
// Last updated 09 Jun 2016

class Lookup
{

    function __construct($pdo)
    {
        $this->pdo = $pdo;
    }

    function getLookup($lookup_type, $lookup_name, $lookup_value)
    {

        $valid_types = array("customer");
        $valid_names = array("state");

        if (!in_array($lookup_type, $valid_types))
        {
            throw new InvalidArgumentException('Lookup type is not a valid');
        }

        if (!in_array($lookup_name, $valid_names))
        {
            throw new InvalidArgumentException('Lookup name is not a valid');
        }

        if (empty($lookup_value) || !is_int($lookup_value) || $lookup_value < 0)
        {
            throw new InvalidArgumentException('Lookup value is not a valid integer');
        }

        $query = "SELECT lookup_description FROM Lookup WHERE lookup_type = :lookup_type AND lookup_name = :lookup_name AND lookup_value = :lookup_value LIMIT 1";
        try
        {
            $stmt = $this->pdo->prepare($query);
            $stmt->bindParam(':lookup_type', $lookup_type);
            $stmt->bindParam(':lookup_name', $lookup_name);
            $stmt->bindParam(':lookup_value', $lookup_value);
            $stmt->execute();
            if ($stmt->rowCount() === 0)
            {
                return false;
            }
            else
            {
                return $stmt->fetchColumn();
            }
        }
        catch (PDOException $ex)
        {
            error_log('Something went wrong in getLookup ' . $ex->getMessage());
            return null;
        }
    }

}

?>

test.php

<?php

// Version 0.1
// Last updated 09 Jun 2016

include_once('pdo.inc.php');
include_once('lookup.class.php');

try
{
    $l = new Lookup($pdo);
}
catch (Exception $ex)
{
    echo $ex->getMessage();
    die();
}

try
{
    echo $l->getLookup("customer", "state", 1); // Returns "New Customer"
    echo $l->getLookup("customer", "state", 2); // Returns "Pending Approval"
}
catch (Exception $ex)
{
    echo $ex->getMessage();
    error_log('Customer name lookup failed with: ' . $ex->getMessage());
}

?>

I'm not sure I like the idea of having fixed arrays for looking up valid parameter values. I was thinking of getting a distinct list from MySQL, but as to do that I might as well just pass the query without validation and let it return null. Any thoughts?

Getting a distinct list from MySQL would slow things down quite a bit, I wouldn't do that.

Perhaps you're overdoing it a bit? Yes, it is always good to filter user input, but I would do that at the point where this input arrives in your application, not in each class inside the application. You are already binding the parameters, which secures the database against injection. Anything apart from what's in your database will result in false, which might be better behaviour than throwing an exception.

So the protection is in the binding of the parameters, and not really in the validation.

Talking about validation. There might be a perfectly good reason to insert all that code. Regretably your validation is incomplete. If I give your method a $lookup_value of 10 it will just return false. That might be a real value, or a sign that the value doesn't exist. You would normally use null in these cases, which is what you do when the query fails.

So my suggestions are:

Filter user input, perhaps with static arrays, directly at the point
of entry. So at the point where you get user input out of $_POST,
$_GET, or anything else. Try to be as strict as possible. When a
value doesn't meet all the criteria, give feedback and allow the user
to enter a correct value. Never let an user freely enter values into
your application in the (false) assumption that the application will
deal with any abnormal values all by itself: It won't. You will
eventually make mistakes.
Keep the validation inside your application very simple and flexible,
this will make it easier to read, modify, and understand the code.
The validation is there to support you to debug your application, it
should not be relied upon as a security feature.
Always bind parameters, of course.

Something like this:

function getLookup($lookup_type,$lookup_name,$lookup_value)
{
  // checking type of arguments
  if (!(is_string($lookup_type) &&
        is_string($lookup_name) &&
        is_int($lookup_value))) {
    throw new InvalidArgumentException('Invalid arguments in Lookup->getLookup().');
  }
  // select a description of ???
  $query = 'SELECT lookup_description
            FROM Lookup
            WHERE lookup_type  = :lookup_type AND
                  lookup_name  = :lookup_name AND
                  lookup_value = :lookup_value
            LIMIT 1';
  try {
    $statement = $this->pdo->prepare($query);
    $statement->bindParam(':lookup_type', $lookup_type);
    $statement->bindParam(':lookup_name', $lookup_name);
    $statement->bindParam(':lookup_value',$lookup_value);
    $statement->execute();
    // return any results
    if ($statement->rowCount() > 0) return $statement->fetchColumn();
  }
  catch (PDOException $exception) {
    error_log('Database error in Lookup->getLookup(): '.$exception->getMessage());
  }
  // failure: no results or database error
  return null;
}

While I was writing this code I noticed that you're using strange names in your database: A Lookup table, containing columns like lookup_name. From these names I get no idea what the content of that table is. The names describe the functions in PHP and not their meaning. A database should be comprehensible on its own, without any code operating on it.

PS: Perhaps someone told you to validate the arguments of your method thouroughly. I cannot help that, this happens when many people can give advise.


Right usage of ViewModels in MVC I'm new to MVC and i'm having some difficulty on understanding the proper usage of ViewModels and Controllers.

I have this example where i will list several different informations in my HomeController as CTAs, Banners, News, Courses... and i came up with this ViewModel structure after some research :

public class CoursesViewModel
{
    private readonly Entities _db = new Entities();
    public List<Courses> Courses { get; private set; }

    public Courses ViewModel() { Initialize( "", "", 0 ); }

    public CursosViewModel( string where, string order, int take ) { Initialize( where, order, take ); }

    private void Initialize( string where, string order, int take )
    {
        IQueryable<Curso> query = _db.Curso;

        if( !string.IsNullOrEmpty( where ) )
            query = query.Where( @where );

        if( !string.IsNullOrEmpty( order ) )
            query = query.OrderBy( @order );

        if( take > 0 )
            query = query.Take( @take );

        Courses = query.ToList();
    }
}

public class BaseViewModel
{
    private readonly Entities _db = new Entities();

    public Page Page { get; private set; }
    public List<State> States { get; private set; }
    public List<HtmlBlock> Blocks { get; private set; }

    public Page GetPage( int pageId )
    {
        return Pagina = _db.Page.FirstOrDefault( x => x.ID == pageId ) ?? new Page();
    }

    public void SetBlocks( Page page )
    {
        Page = page;
    }

    public void SetBlocks( List<HtmlBlock> blocks )
    {
        Blocks = blocks.OrderBy( x => x.Ordem ).ToList();
    }

    public void SetStates( List<State> states )
    {
        States = states;
    }
}

And this is my Controller:

public class HomeController : Controller
{
    private readonly Entities _Db = new Entities();

    [MinifyHtml]
    public ActionResult Index()
    {
        var HtmlParser = new HtmlParser();
        var Redirect   = HelperMethods.GetRouteRedirect( HttpContext );
        var BaseVM     = new BaseViewModel();

        var page = BaseVM.GetPage( Redirect.pageId );

        if( page == null ) return new TransferResult( "/not-found" );

        //My ViewModel calls happen inside the HtmlParser.ParseBlocks,
        //there i will get the right ViewModel to each View and instantiate it
        BaseVM.SetBlocks( HtmlParser.ParseBlocks( page.html, ControllerContext ) );
        BaseVM.SetStates( ViewBag.states );

        return View( BaseVM );
    }
}

Is this the correct "usage" for the ViewModel and Controller ? Should i use my Entities (_db) inside a closure ( using ) ? Why ?

Another thing, i have some common information that exists on every page, how can i work with this on ViewModels without repeating the properties on each ViewModel. I created a BaseViewModel, should i extend it on every ViewModel  or should i implement it as a property ?

In your case CoursesViewModel includes the logic of retrieving entities from db. It should be moved to a service/a repository. ViewModel should include only properties to be shown in the view and some displaying logic in order not to put a lot of server code to the view.

public class HomeController : Controller
{
    // should CRUD products from db
    private readonly IProductService _productService;

    public HomeController(IProductService productService)
    {
        _productService = productService;
    }

    [HttpGet]
    public ActionResult Index()
    {
        var products = _productService.GetProducts(123);
        var model = new ProductViewModel(products);
        return View(model);
    }
}

public class ProductViewModel
{
    public ProductViewModel(IEnumerable<Product> products)
    {
        // init viewmodel here or use some mapper
        this.products = products;
    }

    // only those properties which are going to be displayed in your view

    public int ProductsCount { get; set; }
    public decimal Total { get; set; }
    public string VatCodeApplied { get; set; }

    // ...

    private IEnumerable<Product> products;
}

public interface IProductService
{
    IEnumerable<Product> GetProducts(int userAccountId);

    // ...
}

public class Product
{
    // ...
}


"Researcher Hatim is right or wrong" challenge I wrote a program to solve a problem, I am not so good in python so want help to find areas where this program can be improved or simplified and readable too:-

I got this problem in a code challenge

  Problem

  Professor Hatim is researching the sexual behavior of a rare
  species of lizard. He assumes that they feature two different genders
  and that they only interact with lizard of the opposite gender. Each
  lizard has a integer printed on their back.

  Given the details of lizard interactions, decide whether the
  experiment supports his assumption of two genders with no homosexual
  bugs, or if it contains some bug interactions that falsify it. Or
  simply, you have to print "Suspicious lizard found!" (without quotes),
  if an interaction of two lizards of same gender is found in the list
  of interactions, otherwise print "No suspicious lizard found!"
  (without quotes).

  Input format

  The first line contains an integer T, denoting the number of test    cases.
  The first line of each test case contains two integers N and M, where    N denotes the number of lizards and M denotes the number of
  interactions.
  Next M lines of each test case contains, two space separated    integers, say x and y , denoting the interaction between lizard no. x
  and lizard no. y.

  Note: Integers on the back of lizards are numbered from 1 to N.

  Output format

  For each test case ,print a line, saying either “No suspicious lizard    found!” if the experiment is consistent with his assumption about the lizard    sexual behavior, or “Suspicious lizard found!” if Professor Hatims’s    assumption is definitely wrong.

  Constraints

  1 ≤ T ≤ 5
  2 ≤ N ≤ 2000
  1 ≤ M ≤ 105

  Sample Input

2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

  Sample Output

Suspicious lizards found!
No suspicious lizards found!

  Time Limit: 1 sec(s) for each input file.
  Memory Limit: 256 MB Source
  Limit: 1024 KB
  Marking Scheme: Marks are awarded if any testcase passes.
  Allowed languages: PYTHON

CODE

from sys import argv

class Test:

    def __init__(self, file):
        self.file = file

    def run_test_case(self):
        n, m = self.file.readline().split()
        n = int(n)
        m = int(m)
        first_gender = []
        second_gender = []

        for i in range(m):
            x, y = 0, 0
            x, y = self.file.readline().split()
            if first_gender == [] and second_gender == []:
                first_gender[ len(first_gender) : ] = x
                second_gender[ len(second_gender) : ] = y
            elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
                print 'Suspicious lizard found!'
                return
            elif (x in first_gender and y not in  second_gender):
                second_gender[ len(second_gender) : ] = y
            elif (x in second_gender and y not in first_gender):
                first_gender[ len(first_gender) : ] = y
            elif (y in first_gender and x not in second_gender):
                second_gender[ len(second_gender) : ] = x
            elif (y in second_gender and x not in first_gender):
                first_gender[ len(first_gender) : ] = x
        print 'No suspicious lizard found!'

def start(filename):
    file = open(filename, 'r')
    num_test_cases = int(file.readline())
    for i in range(num_test_cases):
        test_instance = Test(file)
        test_instance.run_test_case()

if __name__ == '__main__':
    (script, filename) = argv
    start(filename)

You don't need a class

I highly recommend the Stop Writing Classes presentation. The typical situation it describes : a class with two methods, an init and a run is exactly what you've done.

Changing this already makes your code much simpler.

def run_test_case(file_):
    n, m = file_.readline().split()
    n = int(n)
    m = int(m)
    first_gender = []
    second_gender = []

    for i in range(m):
        x, y = 0, 0
        x, y = file_.readline().split()
        if first_gender == [] and second_gender == []:
            first_gender[ len(first_gender) : ] = x
            second_gender[ len(second_gender) : ] = y
        elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
            print 'Suspicious lizard found!'
            return
        elif (x in first_gender and y not in  second_gender):
            second_gender[ len(second_gender) : ] = y
        elif (x in second_gender and y not in first_gender):
            first_gender[ len(first_gender) : ] = y
        elif (y in first_gender and x not in second_gender):
            second_gender[ len(second_gender) : ] = x
        elif (y in second_gender and x not in first_gender):
            first_gender[ len(first_gender) : ] = x
    print 'No suspicious lizard found!'

def start(filename):
    file_ = open(filename, 'r')
    num_test_cases = int(file_.readline())
    for i in range(num_test_cases):
        run_test_case(file_)

Close your file

You open a file but never close it. You should but it's quite normal to forget it. A nice solution not to forget it is to use the with statement.

def start(filename):
    with open(filename, 'r') as file_:
        num_test_cases = int(file_.readline())
        for i in range(num_test_cases):
            run_test_case(file_)

Separation of concerns

Your run_test_case functions does way too much : file reading to get input, getting solution for the problem, printing out the answer. It would be much nicer to have this splitted into individual functions. Among other things, it would make your code easier to test. Code-challenge are very good candidates for unit tests because the algorithm involved is usually pretty tricky, the input and ouput are usually pretty clear, no side-effect is expected and you are provided some simple tests with the problem.

Rewriting this gives :

def find_suspicious_lizard(interactions):
    first_gender = []
    second_gender = []
    for x, y in interactions:
        if first_gender == [] and second_gender == []:
            first_gender[ len(first_gender) : ] = x
            second_gender[ len(second_gender) : ] = y
        elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
            return True
        elif (x in first_gender and y not in  second_gender):
            second_gender[ len(second_gender) : ] = y
        elif (x in second_gender and y not in first_gender):
            first_gender[ len(first_gender) : ] = y
        elif (y in first_gender and x not in second_gender):
            second_gender[ len(second_gender) : ] = x
        elif (y in second_gender and x not in first_gender):
            first_gender[ len(first_gender) : ] = x
    return False

def run_test_from_file(filename):
    with open(filename, 'r') as file_:
        num_test_cases = int(file_.readline())
        for i in range(num_test_cases):
            n, m = file_.readline().split()
            n = int(n)
            m = int(m)
            interactions = []
            for i in range(m):
                x, y = file_.readline().split()
                interactions.append((x, y))
            print('Suspicious lizard found!' if find_suspicious_lizard(interactions) else 'No suspicious lizard found!')

if __name__ == '__main__':
    (script, filename) = argv
    run_test_from_file(filename)
    assert find_suspicious_lizard([('1', '2'), ('2', '3'), ('1', '3')])
    assert not find_suspicious_lizard([('1', '2'), ('3', '4')])

With the test I've added, I can now tweak the algorithm and maybe see quickly if I break something.

Do things the easy way

second_gender[ len(second_gender) : ] = y seems like a complicated way to add an element to an array/list. If only there was an append method on Lists. Oh great, it is actually the first method documented.

def find_suspicious_lizard(interactions):
    first_gender = []
    second_gender = []
    for x, y in interactions:
        if first_gender == [] and second_gender == []:
            first_gender.append(x)
            second_gender.append(y)
        elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
            return True
        elif (x in first_gender and y not in  second_gender):
            second_gender.append(y)
        elif (x in second_gender and y not in first_gender):
            first_gender.append(y)
        elif (y in first_gender and x not in second_gender):
            second_gender.append(y)
        elif (y in second_gender and x not in first_gender):
            first_gender.append(x)
    return False

Performance

You call foo in bar many times with the same values. It could be worth storing the result:

        x_in_first = x in first_gender
        y_in_first = y in first_gender
        x_in_second = x in second_gender
        y_in_second = y in second_gender
        if x_in_first and y_in_first:
            return True
        elif x_in_second and y_in_second:
            return True
        elif x_in_first and not y_in_second:
            second_gender.append(y)
        elif x_in_second and not y_in_first:
            first_gender.append(y)
        elif y_in_first and not x_in_second:
            second_gender.append(y)
        elif y_in_second and not x_in_first:
            first_gender.append(x)

It also helped me to think about the logic you've written and helped me to find... a bug!!

Bug

Adding a simple test case (I knew it would be worth it) shows that there is something wrong in your code.

assert not find_suspicious_lizard([('1', '2'), ('3', '4'), ('3', '5'), ('4', '5')])  # should return true because of triplet 3-4-5.


Wrapper class for adding elements to HashSet I have many object of class Test. I want to be sure that among them, there are no two objects o1 and o2 where o1==o2. In order to achieve that, I want to add them all to a HashSet and check if hashSet.size() == numberOfInitialObjects .

In order to ensure that the potential future changes in equals method of the  Test class will not affect my implementation, I wrote a simple wrapper so that instead of adding Test objects to the HashSet, the wrapper objects will be used. The code as such:

private class HashSetWrapper {

        private final Test component;

        public HashSetWrapper(Test component) {
            this.component = component;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 89 * hash + Objects.hashCode(this.component);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final HashSetWrapper other = (HashSetWrapper) obj;
            return this.component == other.component;
        }
    }

Is my approach OK, or are there more suitable ways to achieve my goal?

Why build your own implementation when you can use the features available in the Java standard libraries?

IdentityHashMap gives you all the features you need, and a Java Stream/collector will allow you to extract the map easily from your collection....

Collection<Test> tests = .....
Map<Test,Test> uniques = tests.stream().collect(Collectors.toMap(
     t -> t,
     t -> t,
     (t,u) -> t,
     IdentityHashMap::new))

Now, if the size of the uniques is the same as the tests, you're good. The uniques Map is an IdentityHashMap where the key values are all identical instances (using ==). It supports a null key/value so that should be fine too.


Graph Adjacency List Spent some time implementing a graph as an adjacency list. Looking for suggestions on how to improve this implementation.

#include<vector>
#include<iostream>

class Graph{

public:
     //n is the number of vertices in graph
     Graph(int n)
     {
          N=n;
          E=0;
          //for(int i=0;i < n; ++i)
          for(;n > 0; n--)
          {
              std::vector<int> row;
              adjList.push_back(row);
          }
     }
     //# of vertices
     int Vertices()
     {
         return N;
     }
     //# of Edges
     int Edges()
     {
          return E;
     }
     void addEdge(int v, int w)
     {
          adjList[v].push_back(w);
          adjList[w].push_back(v);
          ++E;
     }

     void  adjVertices(int v)
     {
        std::cout<<"Adjacent vertices of"<< v <<std::endl;
        for(auto &x : adjList[v])
           std::cout<< x << std::endl;
     }

private:
    int N;
    int E;
    std::vector< std::vector<int> > adjList;
};

int main()
{
     Graph G(10);
     G.addEdge(3, 4);
     G.addEdge(0, 2);
     G.addEdge(0, 4);
     G.addEdge(0, 9);
     G.adjVertices(0);
     G.adjVertices(4);
}

First very important thing: Good/clear code without comments is better than bad code with comments. I say this because you are using comments to make up for vague variable and method names. For instance:

 //n is the number of vertices in graph
 Graph(int n)
 {
     ....

Then why not rename n to numberOfVerts?

Other instances:

 //# of vertices
 int Vertices() { ... }

 //# of Edges
 int Edges() { ... }

Would be more clear about their intent if named getNumOfVertices() or getVertexCount(). Conversely, getNumOfEdges() and getEdgeCount().

Still talking about naming, the members N and E are also very poor names. One is the number of vertices (N) and the other the number of edges (E). Single letter variable names should generally be avoided, as they are very ambiguous and unclear. One exception to this rule is in loop counters, which historically have been named with i, j, k, and so on, and thus have become a known idiom in programming.

You don't need to and should not use a loop to initialize the adjList vector.

 for(;n > 0; n--)
 {
     std::vector<int> row;
     adjList.push_back(row);
 }

That is a very inefficient way of initializing it. push_back() might grow the vector several times, incurring a few expensive memory re-allocations. Just construct the vector with its size, using the constructor initialization list:

 Graph(int numVerts)
     : numOfVerts(numVerts)
     , numOfEdges(0)
     , adjList(numVerts)
 { }

Also worth noting that C++11 allows you to replace the ( ) in the constructor call for the member variables with { }. This is the so called uniform initialization syntax.

Be const correct. Add const to methods that don't mutate member data. Get* methods are the common candidates:

int Edges() const { return E; }
            ^^^^^

Don't use endl unless you are meant to flush stdout. Otherwise, a "\n" should be used. Flushing at every print call can significantly bring performance down at no benefit.


CSS and HTML5 for this fixed header on scroll When I had to create a fixed header on scroll, I found a few examples on Stack Overflow but they were terrible in the sense that they relied on a fixed page height. Have a look at what I created which does not rely on a wrapper around the header and the content.

Default

On Scroll

Demo on CodePen.

HTML

Art in Finland

Archive

Events

Contact

CSS

header {
  height:360px;
  z-index:10;
}
.header-banner {
  background-color: #333;
  background-image: url('http://37.media.tumblr.com/8b4969985e84b2aa1ac8d3449475f1af/tumblr_n3iftvUesn1snvqtdo1_1280.jpg');
  background-position: center -300px;
  background-repeat: no-repeat;
  background-size: cover;
  width: 100%;
  height: 300px;
}

header .logo {
  background-color: transparent;
  background-image: url('http://www.futhead.com/static//img/14/clubs/1887.png');
  background-position: center top;
  background-repeat: no-repeat;
  position: absolute;
  top: 72px;
  height: 256px;
  width: 256px;
}
header h1 {
  position: absolute;
  top: 72px;
  left: 240px;
  color: #fff;
}

.fixed-header {
  position: fixed;
  top:0; left:0;
  width: 100%;
}

nav {
  width:100%;
  height:60px;
  background: #292f36;
  postion:fixed;
  z-index:10;
}

nav ul {
  list-style-type: none;
  margin: 0 auto;
  padding-left:0;
  text-align:right;
  width: 960px;
}
nav ul li {
  display: inline-block;
  line-height: 60px;
  margin-left: 10px;
}
nav ul li a {
  text-decoration: none;
  color: #a9abae;
}

/* demo */
.content{ width: 960px; max-width: 100%; margin:0 auto; padding-top: 60px; }
article { width: 720px; float: left; }
article p:first-of-type { margin-top: 0; }
aside { width: 120px; float: right; }
aside img { max-width: 100%; }
body {
  color: #292f36;
  font-family: helvetica;
  line-height: 1.6;
}

jQuery

$(window).scroll(function(){
    if ($(window).scrollTop() >= 300) {
       $('nav').addClass('fixed-header');
    }
    else {
       $('nav').removeClass('fixed-header');
    }
});

HTML

You might want to id that nav. It's because it might not be the only nav on the page, and the JS will pick it up and add .fixed-header to it. Something like:

<nav id="main-navigation">

CSS

On the CSS part, if only the nav gets a the .fixed-header class, you might want to consider declaring the CSS for .fixed-header like:

nav.fixed-header{...}

That way, it only applies to nav with that class. Scenario: You have another header that wants to be fixed at a certain position. It's logical to name it .fixed-header but it's not a nav. If you didn't do it this way, this style will also apply to the sidebar.

JS

It would be better if you cached the value of jQuery DOM pickups, rather than re-fetching them every time the scroll event fires. Additionally, as mentioned in the HTML section, it's better to identify that <nav>. This time, it's for performance.

When you do $('nav'), what jQuery does is pick up all <nav> in the page, and stores them in an array. When you call functions on it, jQuery loops through each one of them, and applies the function. You would want to avoid that looping, and so, you must limit what is being looped by being more specific with your query. Querying an id would be best since id should only happen once on the page.

var $window = $(window);
var nav = $('#main-navigation');
$window.scroll(function(){
    if ($window.scrollTop() >= 300) {
       nav.addClass('fixed-header');
    }
    else {
       nav.removeClass('fixed-header');
    }
});


Coin Flip Streak from Automate the Boring Stuff with Python I apologize beforehand if the question has been repeated so many times. This is a practice task from Automate the Boring Stuff with Python. In brief, the task entails writing a code that carries out an experiment of checking if there is a streak of 6 'heads' or 'tails' in 100 coin tosses, then replicates it 10,000 times and gives a percentage of the success rate.
When I wrote the code, I tried to be different by making the code applicable to any streaks in a number of predetermined experiments (in my case, the sample was 1 million coin tosses). I also tried to find the longest streak possible in that said experiment.
I also want to apologize beforehand that the comments were awfully verbose.
import random, copy, time

def torai(seq,pop): # seq is for #=streak, pop is for total sample/population/experiment
    # Creating a random chance of heads and tails
    tosses = []
    for i in range(pop):
        tosses.append(random.randint(1,2)) # 1 and 2 for head and tail, and vice versa

    # Defining initial values for the main loop
    streak = 0 # Iterated streak
    curlongstr = 0 # Current longest streak
    longeststr = 0 # Longest streak evaluated
    peak = [] # Record local streaks from 'tosses' list

    # The main loop
    for i in range(len(tosses)): # Looping based on list indexes
        if i == 0:  # Conditional for preventing tosses[0] == tosses[-1]
            continue

        elif tosses[i] == tosses[i-1]: # Conditional for checking if an i element has the same value as the previous element value, i-1
            streak += 1 # Adding tally mark if the line above is fulfilled
            if i == len(tosses)-1: # A nested conditional for adding the last tally mark from 'tosses' into the overall list of steaks 'peak', see lines 27-33
                peak.append(streak)

        elif tosses[i] != tosses[i-1]: # Conditional for checking if an i element value is different than the previous element value, i-1
            curlongstr = copy.copy(streak) # Creating a variable by returning a copy of streak before it resets to 0, see line 31
            if curlongstr > longeststr: # A nested conditional for comparing the current longest streak and the longest streak that has happened when looping the 'tosses' list
                longeststr = curlongstr
            streak = 0 # This is where streaks ended and then resets to 0, so before that, the value of the streak is copied first, see line 28
            if curlongstr > streak: # After streak is reset to 0, the value of current long streak is compared to 0, so that we create a list of streaks from 'tosses' list
                peak.append(curlongstr)

    truepeak = []
    for i in peak: # Example: a 2-streak is equal to either [1,1,1] or [2,2,2], a 4-streak is either [1,1,1,1,1] or [2,2,2,2,2]
        truepeak.append(i+1)

    apr = []
    # Loop for finding how many #-streaks happened
    for i in truepeak:
        if i == seq:
            apr.append(i)

    print('%s-streak count: ' %seq, len(apr)) # Total of #-streaks happened in 'tosses' list
    print('%s-streak prob (percent): ' %seq, (len(apr)/pop)*100) # Calculating probability if how many #-streak happened in given n times tosses
    print('longest streak: ',longeststr + 1) # Similar reason as line 36
    print('process time: ',time.process_time(), 'second\n')

    return (len(apr)/pop)*100

x = torai(2,1000000)
y = torai(6,1000000)
z = torai(10,1000000)
print(x, y, z)

I tried to increase the sample to 10 million coin tosses. However, the program will run 9-10 slower each time the function was called.
My request are can anyone check whether if the result (probability of n-streak) is right or not and are there any ways to make the code and process time shorter?

Bugs
torai(1, 10000)

This should print something around 50 %, since it's the individual count. But instead, it prints
1-streak count:  0
1-streak prob (percent):  0.0
longest streak:  19
process time:  0.046875 second

Avoid too many comments
There are too many comments in your code, which makes the code look unnecessarily convoluted. What I recommend is the usage of docstrings. IMO It isn't very important here, but its better than a million comments
def torai(seq,pop):
    tosses = []
    for i in range(pop):
        tosses.append(random.randint(1,2))
    streak = 0
    curlongstr = 0
    longeststr = 0
    peak = []
    for i in range(len(tosses)):
        if i == 0:
            continue
        elif tosses[i] == tosses[i-1]:
            streak += 1
            if i == len(tosses)-1:
                peak.append(streak)

        elif tosses[i] != tosses[i-1]:
            curlongstr = copy.copy(streak)
            if curlongstr > longeststr:
                longeststr = curlongstr
            streak = 0
            if curlongstr > streak:
                peak.append(curlongstr)

    truepeak = []
    for i in peak:
        truepeak.append(i+1)

    apr = []

    for i in truepeak:
        if i == seq:
            apr.append(i)

    print('%s-streak count: ' %seq, len(apr))
    print('%s-streak prob (percent): ' %seq, (len(apr)/pop)*100)
    print('longest streak: ',longeststr + 1)
    print('process time: ',time.process_time(), 'second\n')

    return (len(apr)/pop)*100

Simplify #1
    for i in range(len(tosses)):
        if i == 0:
            continue

It's clear to me that you want to skip the first element. In that case, you can specify the starting point for range()
    for i in range(1, len(tosses)):

Simplify #2
    for i in range(pop):
        tosses.append(random.randint(1,2))

Since this is going to be an immutable sequence, use a tuple, with a generator
tosses = tuple(random.randint(1, 2) for _ in range(pop)

Simplify #3
            if curlongstr > longeststr:
                longeststr = curlongstr

Your condition is simple. The new value is always the larger of the two
Just use the max() function
            longeststr = max(longeststr, curlongstr)

Simplify #4
truepeak = []
    for i in peak:
        truepeak.append(i+1)

You're creating an entirely new list, and fill it up with the exact same elements as peak except with a constant 1 added to them. Very inefficient. Either add the values with the +1 from the beginning or use the +1 where necessary.
    for i in peak:
        if i + 1 == seq:
            apr.append(i + 1)

But again, all you do with apr is get its length, so there's absolutely no point in maintaining so many lists when all you have to do is keep a counter. That also removes the need to maintain peak

Calculate tosses as you go
After removing all of the previous loops, there will still be 2 left. One for calculating the tosses and the other goes through them to calculate them. What I propose is, go through it only once, and keep track of two things. The current flip and the previous flip
def torai(seq, iterations ):
    total_streaks = 0

    previous_flip = random.randint(1, 2)
    for _ in range(1, iterations):
        current_flip = random.randint(1, 2)

        if current_flip == previous_flip:
            total_streaks += 1

        # other calculations

        current_flip = previous_flip

    print(f"Total streaks: {total_streaks}")


Re-inventing the wheel: Binary search in Scala I am trying to implement the code described in this post about how Reddit uses binary search to identify duplicate user names, in Scala. Just to clarify, this is mainly for me figuring out how these things work, i.e. reinventing the wheel. The way I understand it, the steps for binary search are:

You have a new user name you are comparing to an alphabetically sorted list of existing names
You compare that new name to the middle item in the list.
If there is no match, you check if the new name is higher or lower in the alphabet than the middle item, and focus on this side of the list, again checking the middle item.
You repeat until there is a match ("User name taken") or none ("User name available").

Below is what I have. It seems to work when I test it on the names in the list and random other names. It'd cool if someone had some feedback re:

Will this work correctly or is there some kind of bug?
Is there anything really un-Scalaesque in here? I'm just starting out...
Is the while loop the right way to go? Are there better options?
I think the comparer pattern matching function should be expanded to do more, i.e. cover different cases of non-matching, but I couldn't quite get there..
Any other comments are much appreciated!

-

//this is my test data
val lines = List("ally", "ben", "albert", "zong", "hermit", "??ennis", "123pat", "alfred", "zil", "zol", "zal")

def comparer(name_one:String, name_two:String): Boolean = name_one match
    //comparer takes two strings, returns true if identical
    {
    case `name_two` => true
    case _ => false
    }

def checker(new_name: String, old_names: List[String]) : Boolean =
    //checker takes a new user name, compares to List of names already in use
    //returns true if already present or false if not
    {
    val sortednames:List[String] = old_names.sorted
    println(new_name + "input list is length " + sortednames.length)

    //set vars, initialize
    var found: Boolean = false
    var startpoint: Int = 0
    var endpoint: Int = sortednames.length-1
    //while loop, breaks when something is found
    while (found == false && startpoint < endpoint)
    {
        println("start: "+startpoint+" end: "+endpoint)
        //set the midpoint were checking against
        var mid: Int = (startpoint + endpoint) / 2
        println("mid is " + mid)
        //run comparer to set found var initialized abpve
        found = comparer (new_name, sortednames(mid))
        println("new name " + new_name)
        println("ist window " + sortednames(mid))
        //check if new_name is higher or lower in alphabet than mid
        if (new_name > sortednames(mid)) {
            startpoint = mid +1
            println("set start to " + startpoint)
            }
        if (new_name < sortednames(mid)) {
            endpoint = mid
            println("set end to " + endpoint)
    }
    }
    found
    }

val x:Boolean =checker("ally", lines)

println("checker returns ")
println(x)

You're doing a number of things that are very un-Scalaesque, chief among them:

mutable variables - using var instead of val
while loop - recursion is usually preferred
basic comparison operators can be used on strings - >, <, ==, etc.

There are also efficiency issues to be considered:

indexing into a List is slow - Vector and Array collections are better
mixed binary search - many implementations abandon the binary search and go into a straight linear search when the field of candidates becomes small enough.

With a few of these things in mind, here's an alternative approach. (A full binary search, just for simplicity.)

def checker(name: String, names: Seq[String]) : Boolean = {
  // sort the input once, use Array for fast indexing
  val arr: Array[String] = names.sorted.toArray

  // tail-recursive binary search for name in names
  def search(start: Int = 0, end: Int = arr.length -1): Boolean = {
    val mid = start + (end-start)/2
    if (start > end)           false                // can't be found
    else if (arr(mid) == name) true                 // found
    else if (arr(mid) > name)  search(start, mid-1) // narrow the field
    else                       search(mid+1, end)
  }
  search()  // do it
}

Result:

val lines = List("ally", "ben", "albert", "zong", "hermit", "??ennis", "123pat", "alfred", "zil", "zol", "zal")
checker("zong", lines)  // res0: Boolean = true
checker("zing", lines)  // res1: Boolean = false


Python palindrome checker function For practice purposes I implemented a function that checks for palindromes:
def palindrom(name):
    name_reversed = ""

    for buchstabe in name[::-1]:
        name_reversed += buchstabe

    return name.lower() == name_reversed.lower()

print(palindrom("Tom"))
print(palindrom("Bob"))

How may I improve this code, especially the for-loop?

Localisation
It's fine to localise your user-facing strings (e.g. print('Die Buchstaben in diesem Wort bilden ein Palindrom'), but it is not advisable to write the code itself in a language other than English. For better or worse, English is the de-facto language of programming. Thus, buchstabe would be better as letter.
For-loop
The loop is not necessary:
    name_reversed = name[::-1]

name is a string, which is itself a sequence of one-character strings. Applying a slice, as is done here, reverses the sequence but does not change the type: the output of the expression is still a string.


Find kth smallest element in binary search tree I was faced with below interview question today and I came up with below solution but somehow interviewer was not happy. I am not sure why..

  Given a binary search tree, find the kth smallest element in it.

Is there any better or more efficient way to do this problem?

  /*****************************************************
   *
   * Kth Smallest Iterative
   *
   ******************************************************/

  public int kthSmallestIterative(TreeNode root, int k) {
    Stack<TreeNode> st = new Stack<>();

    while (root != null) {
      st.push(root);
      root = root.left;
    }

    while (k != 0) {
      TreeNode n = st.pop();
      k--;
      if (k == 0)
        return n.data;
      TreeNode right = n.right;
      while (right != null) {
        st.push(right);
        right = right.left;
      }
    }

    return -1;
  }

I mentioned time and space complexity as O(n). My iterative version takes extra space. Is there any way to do it without any extra space?

The "not happy interviewer" case is probably not connected to the efficiency of the algorithm, but to a few problems with the codes cleanliness:

You modify method parameters. While this is technically possible, it is generally frowned upon as it makes code hard to read and even harder to debug. Don't do this. Period.
Variable names don't match. root becomes a general pointer to a tree node (which is not root any more), right becomes left. This is a mumble jumble of hard to understand code, which is a nightmare to maintain.
The way you find the target element is not obvious at a glance. At least add a comment on what you do and why it solves the original problem.

From the interviewers perspective, you managed to solve a simple problem with a piece of code, which already is problematic to understand and maintain. Imagine what happens if you get a real complex task with 100 classes and 10000 lines of code involved...

Thus: work on maintainability and clarity first.


Appending objects to an array based on a field I am working with PHP5 (Laravel 5.1), and I couldn't optimize my function, which takes more 4 minutes turning, and fails in the end when I have a huge data (around 6500 rows, but working when i test with around 1000 rows only).
Basically, I try to get an array of objects (which contains users with their balances), and to append it to another array based on depositorId field (by creating a new array for the result).

protected function result(&$items, $statements, $params, $order)
{
    $statements = iterator_to_array($statements);
    $accountTypeId = $this->getAccountTypeId($params);
    $allAccountTypes = $this->getAllAccountTypes($params, $accountTypeId);
    $balancesPerAccount = $this->getAllBalancesPerAccount($allAccountTypes, $order);
    $items = json_decode(json_encode($items), true);
    $appendedResult = [];

    foreach ($statements as $statement) {
       if (!$obj = array_search($statement->depositorId(), array_column($items,'id'))) continue;

       $obj = $items[$obj];

        $obj['className'] = User::class;
        $obj['gamepoints'] = $statement->balance();

        foreach ($allAccountTypes as $accountType) {
            $balancePerDepositor = array_search($obj['id'],
                array_map(function($object) {
                    return $object->depositorId();
                },
                    $balancesPerAccount[$accountType]
                )
            );
            $obj["gamepoints_".$accountType] = isset($balancePerDepositor) ? $balancesPerAccount[$accountTypeId][$balancePerDepositor]->balance(): "";
        }

        array_push($appendedResult,(object)$obj);
    }
}

If $statement contains a huge amount of data

I'm assuming the 6500 records are in the $statement iterator, and that the $statement iterator somehow will fetch data from a database.

Just removing the iterator_to_array statement in the first line can increase the speed a lot. If it's coming from a database query, it will first load ALL queries into memory, which you will read afterwards in your foreach loop.

Since you don't actually use the array for anything other than doing a foreach, this might speed up the results, because the data will only be fetched per-line in the foreach loop, rather than first fetching everything, and then looping over it.

Watch out with your array_* methods

You're using the array* methods heavily. While this is nice and short, I think you're missing some complexity going on in using the methods.

You're looking up all values in the array of $items for every item in $statements, while looking up all id's in the array of items.

This is a worst-case complexity of [Amount of statements]*[Amount of items]*2

Which you could easily reduce to a single associative array lookup.

Since $items is not changing inside the loop, you can safely make a single version of $items:

Here you're trying to lookup if the id exists in a property of statement:

if (!$obj = array_search($statement->depositorId(), array_column($items,'id')))

Keep in mind that key lookups in PHP are a lot faster than in_array or array_search lookups (they're the same in this case).

Basically in_array is this:

function in_array($array, $item)
    foreach ($array as $arrayItem)
    {
         if ($arrayItem == $array)
         {
              return true;
         }
    }
    return false;
 }

You could optimize this by first creating an associative array of all keys (once, outside the foreach loop):

foreach ($items as $subItem)
{
    $idIndex[$subItem] = $subItem;
}

You can also cache this information if you're calling this method multiple times.

And then checking inside your foreach loop:

if (!isset($idIndex[$statement->depositorId()])) {
    continue;
}

The cost of a lookup in $idIndex will alway be 1, and worst-case scenario of the lookup cost you're doing now will be 2n the amount of items in $items (e.g. ), because you will iterate $items twice each row.

Watch out with your array_* calls, part 2

Exactly the same principle applies to this part:

And here you're trying to look up if an id exists in $balancesPerAccount[$accountType]

$balancePerDepositor = array_search($obj['id'],
    array_map(function($object) {
        return $object->depositorId();
    },
    $balancesPerAccount[$accountType]
)

Since this a simple lookup, I would really recommend building an index of all balancedPerAccount once, and then checking with isset() if it exists, rather than looping over each item in a doubly nested array.

I would recommend doing an exercise of writing all array_* methods by hand using foreach or for loops, then it will become obvious what these methods are doing.

Unsolicited advise: Style, comments, variable names, reusing variable names

This will not affect speed that much, but I generally recommend overwriting variables with a different kind of Object.
For example:

$items = json_decode(json_encode($items), true);

and

$obj = $items[$obj];

I would avoid this because

It's confusing to debug and test (obj used to be an int and now it's an object)
It becomes hard to read (what is actually the input and output of this method?)

PHP Doc
Also, depending on the objects, there's a lot of undocumented coding going on (documented by debugging). It's almost impossible to figure out what's happening without actually debugging the code. Make sure to use php annotations to describe what's inside the objects or arrays.

Variable naming

$items
$statement
$params
$order

Are all horribly generic in this case. If there are very clear comments on what they contain, this may not be a problem, but I would try using a bit more descriptive variable names.


Converting an integer into the written form For my homework assignment I have to create a class which converts an integer between 0 and 9999 into the written form. For example, 713 would be written as "seven hundred thirteen."

I wrote a few variations and I think I found the best approach. However, I was wondering if anyone had a moment to comment on my approach. Maybe point out subtle things I might not be taking advantage of.  Things like that.

I'll list just the important excerpts from the .cpp and .h files.

The following are all static members of the Numbers class:

const char* Numbers::lessThan20[] = {
  "zero",     "one",      "two",      "three",   "four",    "five",
  "six",      "seven",    "eight",    "nine",    "ten",     "eleven",
  "twelve",   "thirteen", "fourteen", "fifteen", "sixteen", "seventeen",
  "eighteen", "nineteen"
};
const char* Numbers::over19[] = {
  "",       "",      "twenty", "thirty", "fourty", "fifty", "sixty", "seventy",
  "eighty", "ninety"
};
const char* Numbers::hundred  = "hundred";
const char* Numbers::thousand = "thousand";

And this is my function to convert the number into a string:

std::string Numbers::print() const
{
  std::string text;
  int whole, remainder;

  remainder = this->number; // <- number is a member variable of the Numbers class

  whole = remainder / 1000;
  remainder %= 1000;

  if (whole > 0)
    text = text + lessThan20[whole] + " " + thousand + " ";

  whole = remainder / 100;
  remainder %= 100;

  if (whole > 0)
    text = text + lessThan20[whole] + " " + hundred + " ";

  if (remainder > 19)
  {
    whole = remainder / 10;
    remainder %= 10;
    text = text + over19[whole];
    if (remainder > 0)
      text = text + "-" + lessThan20[remainder];

  }
  else if (remainder > 0)
    text = text + lessThan20[remainder];

  return text;
}

Use STL Containers

Prefer using std::array (if your compiler supports it or) std::vector instead of raw arrays.  Also, I would recommend using std::string instead raw character pointers.

const std::array<std::string, 20> Numbers::lessThan20 = {
  "zero",     "one",      "two",      "three",   "four",    "five",
  "six",      "seven",    "eight",    "nine",    "ten",     "eleven",
  "twelve",   "thirteen", "fourteen", "fifteen", "sixteen", "seventeen",
  "eighteen", "nineteen"
};
const std::array<std::string, 10> Numbers::over19 = {
  "",       "",      "twenty", "thirty", "fourty", "fifty", "sixty", "seventy",
  "eighty", "ninety"
};
const std::string Numbers::hundred  = "hundred";
const std::string Numbers::thousand = "thousand";

Edge Cases

Currently there is no handling for edge cases.  If the number is 0 it will return an empty string instead of "zero".  Numbers greater than or equal to 20000 will cause an out of range access.  Therefore, numbers too large need to be properly handled.  These cases can checked at the beginning of the function.

A couple other minor points: I would remove the line int whole, remainder and declare the variables when they are initialized.  This will reduce the variables' scope and does not leave them initialized.  Also, prefer text += ... over text = text + ....  It's more clear that you are appending and less typing.  Lastly, I would recommend to always use curly braces even when there is only one statement.

Here is your function with my recommendations:

std::string Numbers::print() const
{
  int remainder = this->number; // <- number is a member variable of the Numbers class
  if(remainder == 0)
  {
    return lessThan20[0];
  }

  if(remainder >= 20000)
  {
    // handle this case
  }

  int whole = remainder / 1000;
  remainder %= 1000;

  std::string text;
  if (whole > 0)
  {
    text += lessThan20[whole] + " " + thousand + " ";
  }

  whole = remainder / 100;
  remainder %= 100;

  if (whole > 0)
  {
    text = text + lessThan20[whole] + " " + hundred + " ";
  }

  if (remainder > 19)
  {
    whole = remainder / 10;
    remainder %= 10;
    text = text + over19[whole];
    if (remainder > 0)
    {
      text = text + "-" + lessThan20[remainder];
    }
  }
  else if (remainder > 0)
  {
    text = text + lessThan20[remainder];
  }
  return text;
}


Generate combinations of a given sequence without recursion Given an array of unique numbers find the combinations
Doing a shallow copy in the code to avoid changes to the passed obj by reference
This has a run time of \$O(n \times \text{#ofcombinations})\$ - can this be done better -- iteratively and easy to understand

import copy
def gen_combinations(arr): #
    res = [[]]
    for ele in arr:
        temp_res = []
        for combination in res:
            temp_res.append(combination)
            new_combination = copy.copy(combination)
            new_combination.append(ele)
            temp_res.append(new_combination)
            res = copy.copy(temp_res)

    return res

First, a side note. What you call combination is usually called subset.
In a set of \$n\$ elements an average length of a subset is \$\dfrac{n}{2}\$. That is, generating a single subset takes \$O(n)\$ time. You cannot get a time complexity better than \$O(n2^n)\$.
The space complexity is a different matter. If you indeed need all the subset at the same time, then again the space complexity cannot be better than \$O(n2^n)\$. On the other hand, if you want one subset at a time, consider converting your function to a generator, which would yield subsets one at a time.
A more or less canonical way of generating subsets uses the 1:1 mapping of subsets and numbers. Each number a in the \$[0, 2^n)\$ range uniquely identifies subset of \$n\$ elements (and vice versa). Just pick the elements at the position where a has a bit set.
All that said, consider
def generate_subsets(arr):
    n = len(arr)
    for a in range(2 ** n):
        yield [arr[i] for i in range(n) if (a & (1 << i)) != 0]


Count words with given prefix using Trie I have been trying to solve this HackerRank problem:

We're going to make our own Contacts application! The application must perform two types of operations:

add name, where  is a string denoting a contact name. This must store  as a new contact in the application.

find partial, where  is a string denoting a partial name to search the application for. It must count the number of contacts starting with  and print the count on a new line.

Given  sequential add and find operations, perform each operation in order.

What I came up is this
class TrieNode():
    def __init__(self):
        self.children = {}
        self.word_count = 0

class Trie():
    def __init__(self):
        self.root = self.get_node()

    def get_node(self):
        return TrieNode()

    def add(self, key):
        crawl = self.root
        for char in key:
            if char not in crawl.children:
                crawl.children[char] = self.get_node()
            crawl = crawl.children[char]
            crawl.word_count += 1

    def get_prefix(self, key):
        crawl = self.root
        for char in key:
            if char not in crawl.children:
                return None
            crawl = crawl.children[char]
        return crawl

    def find(self, key):
        node = self.get_prefix(key)
        return node.word_count if node else 0

The code above is a modification of this from GeeksForGeeks. The modifications that I have done are keeping a word_count for every trie node. This denotes how many words start with the prefix ending in that node's letter. The other modification is using a hashmap to keep children rather than lists.
On HackerRank, 9/11 test cases pass, and the other 2 timeout. I can't figure out where I can optimize this further.
I know of a radix tree that is an optimized version of a normal trie, but that saves on space, rather than time, so I haven't explored that option.
Can anyone help me figure out where I can optimize for time in my code?
Thanks!

I think the important thing to notice here is that you don't actually need a Trie. The partial queries are not just substrings of the names, they are prefixes. It should therefore be faster to just built a dictionary which directly counts how often each prefix occurs.

Something as simple as this is sufficient (just tested it, it passes all testcases):

from collections import defaultdict

def contacts(queries):
    prefixes = defaultdict(int)
    for op, name in queries:
        if op == "add":
            # maybe not the best/nicest way to iterate over slices,
            # but probably the easiest
            for i in range(1, len(name) + 1):
                prefixes[name[:i]] += 1
        else:
            # gives 0 if name is not in prefixes, no need for `get`
            yield prefixes[name]

This is \$\mathcal{O}(len(name))\$ for each add and \$\mathcal{O}(1)\$ for each find. And since the length of all names is less than 22, the for loop will be very fast. It does not even seem to matter that slicing the string might create additional copies.

In contrast, your code is also \$\mathcal{O}(len(name))\$ for each add, but it is also \$\mathcal{O}(len(name))\$ for each find, as far as I can tell. You need to actually traverse the Trie to find the count. Apparently that, maybe together with the overhead of looking up class methods, is enough to reach the time limit for one of the larger testcases.

Stylistically your code looks very good. The only thing to improve there is adding some docstrings to your methods which explain how to use them.

If you were worried about Python 2 backward compatibility you should inherit from object, but nowadays that is probably less of a concern (especially with one-off code for a coding challenge).


The logic for re.match() , sys.exit(1) does not make sense, plus why can't i use return True if the re.match regex matches The whole idea behind this ,is the user enters :
1. hg commit -m "NO-TIK" and is able to submit the changeset
2. hg commit -m "NO-REVIEW" also does the same as # 1
3. hg commit -m "JIRA-123 blah blah" is also submitted as long as there is a valid issue "JIRA-123" otherwise the commit is reverted with the message "%s does not exist"%ticket
4. hg commit -m "plain english without ANY of the above, reverts the changes , so the above 3 rules MUST be observed.

#!/usr/bin/env python

import re, os, sys, jira, subprocess
from optparse import OptionParser
import warnings
from collections import namedtuple

def verify_commit_text(tags):
    for line in tags:
        if re.match(r'[^\NO-TIK]',line):
            sys.exit(1)
        elif re.match(r'[^\NO-REVIEW]', line):
            sys.exit(1)
        elif re.match(r'[a-zA-Z]+-\d+', line):
            # Validate the JIRA ID
            m = re.search("([a-zA-Z]+-\d+)",line)
            m_args = m.group(1)
            m_args = [m_args]
            if CheckForJiraIssueRecord(m_args):
                sys.exit(1)
            else:
                print >> sys.stderr, ("%s does not exist"%m_args)
        else:
            sys.exit(0)

def CheckForJiraIssueRecord(my_args):
    # turn off stdout
    #sys.stdout = open(os.devnull)
    #sys.stderr = open(os.devnull)
    com = jira.Commands()
    logger = jira.setupLogging()
    jira_env = {'home':os.environ['HOME']}
    command_name = "cat"
    server = "http://jira.server.com:8080/rpc/soap/jirasoapservice-v2?wsdl"
    options = namedtuple('Options', 'user password')('user','password')
    jira.soap = jira.Client(server)
    jira.start_login(options, jira_env, command_name, com, logger)
    issue = com.run(command_name, logger, jira_env, my_args)
    if issue:
        return True

if __name__ == '__main__':
    commit_text_verified = verify_commit_text(os.popen('hg tip --template "{desc}"'))
    if commit_text_verified:
        sys.exit(0)
    else:
        print >> sys.stderr, ('[obey the rules!]')
        sys.exit(1)

You seem confused about sys.exit is doing. It exits your program. You function verify_commit_text never exits. Your code after calling verify_commit_text is never executed. The program always hits a sys.exit in verify_commit_text and terminates. The first thing you need to do is eliminate all the sys.exit() except in the __main__ section. You should really only have sys.exit in there.