Simplistic Algorithms with Python

I have been working on the problems in Codility to get better at the algorithms and also to expand the way I solve problems in general. One common thing I notice with using Python as the language is that, sometimes the solutions are so simple I wonder if I learnt anything at all.

Take for example, this challenge called GenomicRangeQuery which aims to teach the application of Prefix sums in problem solving. Here is the solution which gets the perfect score of 100% for both accuracy and complexity.

def solution(S, P, Q):
    mins = []

    for i in range(0, len(P)):
        start = P[i]
        end = Q[i]+1
        sub = S[start:end]
        if 'A' in sub:
            mins.append(1)
        elif 'C' in sub:
            mins.append(2)
        elif 'G' in sub:
            mins.append(3)
        else:
            mins.append(4)
    return mins

The solution felt like cheating and also, I wasn’t sure of the complexity of in keyword magic of Python. I searched for a solution in a low level language to understand better. Here is it in Java. Reproducing for quick comparison.

public static int[] genome(String S, int[] P, int[] Q) {
   int len = S.length();
   int[][] arr = new int[len][4];
   int[] result = new int[P.length];

   for(int i = 0; i < len; i++){
     char c = S.charAt(i);
     if(c == 'A') arr[i][0] = 1;
     if(c == 'C') arr[i][1] = 1;
     if(c == 'G') arr[i][2] = 1;
     if(c == 'T') arr[i][3] = 1;
   }
   // compute prefixes
   for(int i = 1; i < len; i++){
     for(int j = 0; j < 4; j++){
       arr[i][j] += arr[i-1][j];
     }
   }

   for(int i = 0; i < P.length; i++){
     int x = P[i];
     int y = Q[i];

     for(int a = 0; a < 4; a++){
       int sub = 0;
       if(x-1 >= 0) sub = arr[x-1][a];
       if(arr[y][a] - sub > 0){
         result[i] = a+1;
         break;
       }
     }

   }
   return result;
 }

Needless to say, the solution is beautiful and as intended (teaches the application of prefix sums).

Pondering

The difference in the complexity of the two solutions showcases the power and simplicity of Python.

So what am I doing with Python? I am writing simpler code definitely. It is good. I am also worried that I might not be learning a number of techniques that will help in the long run.

Using React for parts of a Flask App

Background:

As a part of my work, I needed a console like viewer in a web application (like the one used in travis.ci). The frontend is simply Bootstrap 3 and some jQuery JavaScript. I have written a rudimentary one using Bootstrap’s Panel and List Groups and using the helper classes to style them. But the application has grown and it is time we got a really good log viewer.

Requirements:

  • The library should be easy to include in the project without requiring a complete overhaul of the frontend. (Things like Angular, Ember are out)
  • We might decouple the app into a REST API and frontend sometime in the future, so it needs to provide a upgrade path for the full frontend.
  • To me, a Python programmer, it should be easy to get started and start building, without enforcing specific new requirements.
    (e.g., Angular forces TypeScript, I am willing to learn, just not now, not for this one)

React with JSX syntax, the ability to just drop the the library and use it for only selective parts of the app seemed just right. After trying out the tic-tac-toe tutorial, I ventured to setup it for our project.

Setting up the development environment

JSX is not plain native Javascript. Even-though I could include the React and ReactDOM libraries using the script tags, I have to setup a node.js based environment to compile the JSX into JS.

Project file structure

The Flask app has a typical structure as show below

-- project/
    |-- flask_app/
    |   |-- static/
    |   |   |-- js/
    |   |   |-- css/
    |   |   |-- images/
    |   |-- tempaltes/
    |   |-- __init__.py
    |   |-- application.py
    |   |-- views.py
        ...
    |-- run.py
    |-- .gitgnore
    |-- README

Setting up React’s requirements

React’s Adding React to an Existing Application lists three requirements – a package manager, a bundler and a compiler. I used npm for package manager, Webpack for bundler and Babel for the compiler. Here are the steps for the setup:

  • Create the package.json file using npm init inside project directory.
  • Create a new directory named ui insdie the project to hold the React JSX files
  • Install the packages react, react-dom using npm install --save
  • Install the packages webpack, babel-core, babel-loader, babel-preset-env, babel-preset-react using npm install --save-dev
  • Add the line "build": "webpack --config webpack.config.js" to the scripts block of package.json
  • Create file .babelrc with a single line {"presets": ["react", "env"]}
  • Create file webpack.config.js with the contents
const path = require('path');

module.exports = {
    entry: './ui/logger.js',  // logger.js is where I plan to write the JSX code
    output: {
        path: path.resolve(__dirname, 'flask_app/static/js/'),
        filename: "logger.js"
    },
    module: {
        rules: [
            { test: /\.js$/, exclude: /node_modules/, loader: "babel-loader" }
        ]
    }
}

Here is what I have done so far:

  • I have initiaed the project with package.json to manage things like requirements for the JS files, run npm commands, …etc. I guess this is like the setup.py of Python world.
  • Added the required packages
  • Configured Babel compiler to use the presets required for React to compile
  • Configured Webpack to read the ui/logger.js file and compile it using Babel and put it the Flask app’s static/js/ folder so that it can be used in the Jinja templates using url_for('static', filename='logger.js')
  • Configured NPM so that npm run build would run webpack to compile and put the file in static folder.

New Project structure

After adding everything, this is how the project looks

-- project/
    |-- flask_app/
    |   |-- static/
    |   |   |-- js/
        ...
    |-- run.py
    |-- .gitgnore
    |-- README
    |-- node_modules/
    |-- ui/
    |   |-- logger.js
    |-- .babelrc
    |-- webpack.config.js
    |-- package.json

With the above setup, I am good to go. All I need to do is add a script tag with src pointed to the logger.js. With everything setup,

  • I added a small JSX snippet to ui/logger.js
  • ran npm run build (the file compiled and was put in the static/js/ folder)
  • started the Flask development server python run.py
  • loaded the app in the browser.

Everything worked as expected.

..except it didn’t the second time

Now I changed the code in ui/logger.js > ran npm run build > reloaded the page in browser. Nothing changed. Now we have a problem. It’s the browser caching the output static/js/logger.js file.

Solving Caching issue

While Caching is good from a client’s point of view, it is a little tricky in a development environment. If we were building a full blown React app using the react-cli, we won’t have this issue as the react-scripts would watch the file changes and reload the browser for us. In the current setup using Flask’s development server, however, we need to take care of it ourselves. Webpack to the rescue.

Webpack optimizations

I followed Webpack’s Caching guide and applied everything suggested. Now the webpack.config.js looks like this:

const webpack = require('webpack');
const path = require('path');
const CleanWebpackPlugin = require('clean-webpack-plugin');


module.exports = {
    entry: {
        main: './ui/logger.js',
        vendor: [
            'react', 'react-dom'
        ]
    },
    output: {
        path: path.resolve(__dirname, 'flask_app/static/build'),
        filename: "[name].[chunkhash].js"
    },
    module: {
        rules: [
            { test: /\.js$/, exclude: /node_modules/, loader: "babel-loader" }
        ]
    },
    plugins: [
        new CleanWebpackPlugin(['flask_app/static/build']),
        new webpack.optimize.CommonsChunkPlugin({
            name: 'vendor'
        }),
        new webpack.optimize.CommonsChunkPlugin({
            name: 'runtime'
        }),
    ]
}

This is what the updated webpack config does:
– instead of saving the generated Javascript as a single file called logger.js it splits the output into three files named
* main.[chunkhash].js which contains the compiled ui/logger.js
* vendor.[chunkhash].js which contains the libraries listed in entry.vendor
* runtime.[chunkhash].js which contains the Webpack’s runtime logic to load the files generated

Note: the chuckhash is a value that webpack substitutes when generating the files. This changes with the changes in entry files. So we have a different filename in the output with every build, thus avoiding the caching issue.

  • the CleanWebpackPlugin removes all the files in the output directory before generating new files so we don’t have outdated files like main.hash1.js, main.hash2.js.. etc.,
  • since static/js folder has other files like bootstrap, jquery ..etc., So the output.path is set to a new directory static/build, to prevent the Clean Webpack plugin from deleting them.

With the above config, we will have a different filename everytime we build using npm run build. Now the file cached by the web browser is not used as the new filename is different from the old one.

But how do we use the latest filenames in the “ tag in the Jinja templates?

There is a plugin to solve this issue called Flask-Webpack, but I felt it too be an overkill.

Flask Context Processor to get the hashed filename

Add the following context processor to the Flask app:

@app.context_processor
def hash_processor():
    def hashed_url(filepath):
        directory, filename = filepath.rsplit('/')
        name, extension = filename.rsplit(".")
        folder = os.path.join(app.root_path, 'static', directory)
        files = os.listdir(folder)
        for f in files:
            regex = name+"\.[a-z0-9]+\."+extension
            if re.match(regex, f):
                return os.path.join('/static', directory, f)
        return os.path.join('/static', filepath)
    return dict(hashed_url=hashed_url)

This provides a function called hashed_url which looks for the file and returns its hashed form. Now we can add the files using script tags as below:

<scrip.t src="{{ hashed_url('build/runtime.js')></script>
<scrip.t src="{{ hashed_url('build/vendor.js')></script>
<scrip.t src="{{ hashed_url('build/main.js')></script>

The hashed_url would match the filename passed to it with the the files in the directory and returns the hashed form. For e.g., hashed_url("build/main.js") returns /static/build/main.16f45d183a4c0f0b1b37.jss

Conclusion

The whole process of setting this up took multiple hours of research and testing. I could have used one of the available boilerplates to set this up, but I now have it in the form I want it and I understand what the different parts mean and do. It lets me use React for small components as required and grow as the project grows. It also creates no disruption in the workflow of other developers. Happy coding time ahead 🙂

Python mock – Handling namespaces

Unit testing a big python application comes with its own set of worries which includes mocking calls to parts of code which we will test somewhere else.

Let us say I have a **utils.py** (every project has one anyways)

# utils.py
def word_length(name):
    # here it is a trivial function
    # assume that this is a costly network/DB call
    return len(name)

 
And I have another module which uses word_length using the from module import function syntax.

# user.py
from project.utils import word_length

def calculate(name):
    length = word_length(name)
    return length

Now I want to unit test all the functions in **user.py** and since I am going to test just the user module and want to avoid costly calls made by my utils module I am going to mock out calls to `word_length` using Python mock library.

# test_user.py
from project.user import calculate

from mock import patch

@patch('project.utils.word_length')
def test_calculate(mock_length):
    mock_length.return_value = 10
    assert calculate('hello') == 5

One would expect this assertion to fail because we have mocked out the word_length to return 10. But this passes and our mock is not working. Why? Because **NAMESPACE**. Here we have patched the function in the namespace utils. But we have imported the function to the user.py namespace by using `from module import function`. So we need to patch the function in the user namespace where it is used and not in the utils where it is defined. So change the line


@patch('project.utils.word_length')

# to

@patch('project.user.word_length')

But what if we have used simply like

# user.py
import utils

def calculate(name):
    length = utils.word_length(name)
    return length

This time we can straight away use the @patch('project.utils.word_length') as we are importing the entire module and namespace remains as such.

Python Pitfalls

I was woken up today with the following question:
[python]
def foo(x=[]):
x.append(1)
return x

>>> foo()
>>> foo()
[/python]

What could be the output? The answer is

[1]
[1, 1]

I was stupefied for a minute before I started DuckDuckGo-ing Python default arguments, Python garbage collection, Python pitfalls..etc.,

These links helped me understand mutable objects’ memory management.
Deadly Bloody Serious – Default Argument Blunders
Udacity Wiki – Common Python Pitfalls
Digi Wiki – Python Garbage Collection

Travis CI config for Python + NodeJS

I currently work with the Gluu Federation – an open source company. My present job is to build a Web UI for the cluster management using the available API.

We use Python Flask for the Backend and AngularJS+Bootstrap for the Frontend. Pretty much a standard affair these days. Testing is crucial and we have the backend tests in Python Nose and the Frontend Unit tests using Karma and Jasmine running on NodeJS.

Now the question is how does one configure the Travis CI .yml file to perform tests in a both Python and Javascript. I initially set up using language: node_js and ran only the frontend tests. Then I went around searching and stumbled on travis-ci – issue#4090 – Support multiple languages. Thanks to the tip from @BanzaiMan I now have both frontend and backend tests running with a simple yml file.


language: python
python:
– 2.7
install:
– pip install -r requirements.txt
– nvm install 0.10
– npm install
before_script:
– export DISPLAY=:99.0
– sh -e /etc/init.d/xvfb start
script:
– nosetests –with-coverage –cover-package=gluuwebui
– npm test

view raw

.travis.yml

hosted with ❤ by GitHub

Zimbalaka – Zim file creator for Offline Wikipedia

OpenZim is a Wikimedia developed format for offline reading of Wikipedia. Read more here. But the project was sadly sidelined and the support from MediaWiki, the software that runs Wikipedia sites, was also removed.

I came to know about all this from Bala Jeyaraman of Vasippu. He is planning to introduce tablets in a classroom of 6th standard students, with exceptional comprehension levels compared to average Indian classrooms, and wanted a way to load select material into the tablets. The OpenZim files have an excellent reading app called Kiwix, which also offers complete Wiki sites as downloads. Tablets can’t afford to have a huge amount of data, like full Wikipedia. There is no way to create a zim file with select topics. One has to request the OpenZim team to do it for him/her.

Enter Zimbalaka

Zimbalaka is a project which tries to solve just that. It creates offline wikipedia content files in zim file format. A person can input a list of pages that need to be created as a zim, or at least a Wikipedia category. Then Zimbalaka downloads those pages, removes all the clutter like sidebar, toolbox, edit links …etc., and gives a cleaned version as a zim file for download. It can be opened in Kiwix.

The zim is created with a simple welcome page with all the pages as a list of links. The openzim format also has an inbuilt search index and Kiwix uses this really well. So you can create zims of 100 articles and still navigate to them easily either way.

Zimbalaka has multi-lingual and multi-site support. That is, you can create a zim file from pages of any language of the 280+ existing Wikipedias, and also from sites like Wikibooks, Wiktionary, Wikiversity and such. You can even input any custom URL like (http://sub.domain.com/), Zimblaka would add (/wiki/Page_title) to it and download the pages.

It is currently hosted by my good friend Srikanth (@logic) at http://srik.me/zimbalaka

Screenshots

Here is how the content looks in Kiwix for Android.

navigate

multi

Pain points

  • A small pain point is that Zimbalaka also strips the external references that occur at the end of the Wikipedia articles, as I didn’t find it useful in an offline setup.
  • You cannot add a custom Welcome page in the zim file. Not a very big priority. The current file does its work of listing all the pages
  • You cannot include pages from multiple sites as a single zim file. The workaround is to create multiple files or use a tool called zimwriterfs, which has to be compiled from source (this is used by zimbalaka behind the scenes).

Developers

This tool is written using Flask – A simple Python web framework for the backend, Bootstrap as the frontend and uses the zimwriterfs compiled binary as the workhorse. The zimming tasks are run by Celery, which has been automated by supervisord. All the coordination and message passing happen via Redis.

Do you want to peek in how it is all done? Here is the source code [https://github.com/tecoholic/Zimbalaka]. Feel free to fork, modify and host your own instance.

Update

The OpenZim team has appreciated the effort I had put in and offered to host the tool on their server at http://zimbalaka.openzim.org. They have also pointed me to the desired backend called ‘mwoffliner’ that they have developed to download and clean the HTML. I will be working on it in my free time.