Regex Golf on regex.alf.nu - Part 1

If you haven't already, go here: http://regex.alf.nu/0

The first one needs you to match words with 'foo' in them, so the solution is straightforward.

foo

The second one has all words that end in 'k'. We use `k` followed by the end of line anchor `$`.

k$

Number 3, Ranges requires you to match all words that contain characters from a to f only.

^[a-f]+$

Backrefs is where it gets interesting. We need to match words that repeat a sequence of characters, like allochirally, heavyheaded or barbary.

(\w{3})\w*\1

Here we match any letter thrice in a group, followed by 0 or more letters followed by our first group. The 0 or more is important in cases like barbary where there is no letter between the group and its repetition.

I had to handle an edge case in Abba, but it looks alright otherwise. The level description is suggestive of a simpler solution but I couldn't figure that out.

^(?:[en](?!n)\w+|(?:(\w)(?!\1))+)$

Visual representation from Debuggex helps a lot in case of complicated regular expressions.

The edge case is for effusive and noisefully.

A man, a plan is similar to Backrefs, but you have to match the reverse of the first group. Again, I couldn't find the proper way, if there is one, but the solution is short and works as well.

^(\w)(\w)\w*?\2\1$

Two groups, one letter each, followed by 0 or more letters, followed by the second group and then the first group, eventually reversing the order.

I will get back to Prime in a later post perhaps.

Four is nice. There might be a possibility of nested groups here though, just to make it shorter.

(\w)\w\1\w\1\w\1

Stay tuned for part 2. If I am ever able to solve the rest.

Overriding forms in Django admin.

First up, find out where your python packages are stored. This will differ from your system packages if you are in a virtualenv.

echo `which python`

You will get a path like this

/some/path/bin/python

Navigate up a couple of directories and find the django package. Then browse to the following directory. Here you will find all the original templates for django admin.

/some/path/lib/python2.7/site-packages/django/contrib/admin/templates/admin/

My use case required overriding change forms for particular models of some applications.

This is the form that you get once an object of a particular model is saved and you need to change some values / fields in that model.

Copy the change_form.html from the directory and paste it in your projects templates folder. The path would depend on which model you are overriding. Suppose you have model Foo in application ABC.

Copy change_form.html to

templates/admin/ABC/foo/change_form.html

(creating directories where needed). This is your projects' templates folder.

Application name reserves the casing but the model name should be converted to lowercase.

Inside this template you can use {{ original }} along with {{ block.super}} to access the particular object of the model whose form you have overridden. A typical override would look like this, removing the unnecessary stuff.

{% extends "admin/change_form.html" %}
{% load i18n admin_urls %}

{% load static %}

{% block extrahead %}{{ block.super }}
	<link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css">
	<script src="//code.jquery.com/jquery-1.11.1.min.js"></script>
	<script src="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js"></script>
	<script src="{% static "js/custom.js" %}"></script>
{% endblock %}


{% block after_field_sets %}{{ block.super }}
    <!-- override template here -->
{% endblock %}

You can also override inlines. Suppose you are using ModelAdmin and need to override an inline.
You must add an additional attribute named template to the inline, and giving it the path of the form you have overridden.


We maintain the same directory path convention as found in the site-packages/django/.. directory. But this is not necessary, stacked.html can reside anywhere under templates. Copy it under your templates from the same directory that you copied change_form.html from.

class FooInline(admin.StackedInline):
	model = Foo
	fields = (('a'),('b'),('c'),)
	extra = 0
        template = 'admin/ABC/bar/edit_inline/stacked.html'

class BarAdmin(admin.ModelAdmin):
	list_display = ['b', 'a', 'r']
	inlines = [FooInline]

admin.site.register(Bar, BarAdmin)

admin.site.register(Foo)

Extra headers can be added under the extrahead block.

{% block extrahead %}
    <!-- extra css/js resources defined here -->
{% endblock %}

Custom JavaScript can be linked in the extrahead block or you can have it on the page at the end of the template. Note that if you intend on adding some forms, and have input or button with type="submit", it conflicts with the model's form (you should be able to stop event propagation by handling it, I suppose, this remains to be tried).

If you need to process any input separately, have a button tag with an event listener on it.

Making the Malhar app

I took up the opportunity to build an app for a festival in my college. Having only three weeks to build and publish the whole thing, it seemed like a good time to try Cordova, after being frustrated by native (Java based) Android application development several times. I'd still go with native, as using a hybrid tool-kit is situational, as of today.

The app would be nothing complex, just displaying information about the festival itself, schedules and details of the departments involved in it. Mostly static content. Although there was a plan to include timed notifications for each of the festival events, I ended up giving up on it, discussed later in the post.

Choosing the hammer

First, and the most important task would be choosing a UI / page routing framework or library. First thought was Bootstrap or Foundation with AngularJS. Having worked with bootstrap before, and Angular routing, I could go about it quick. A friend recommended jQuery mobile. Ignorant me said 'meh'.

Ionic looked awesome, I started working on it. Things looked good, but then this happened ...

The app became slow and laggy after some time of scrolling and changing pages. This was on a desktop machine using Chrome. Phones don't have that kind of power so it would be worse on mobile.

I don't know what I was doing wrong, but this occurred when loading JSON data using the bundled Angular for doing all things MVC. There might be a very simple fix to this, but knowing very little about memory leaks or ever-increasing DOM nodes and listeners, nothing came to mind.

Tried out the nightly, reading on a GitHub issue that it had been fixed. The above was from using the beta version of Ionic.

No memory leak this time, but the number of nodes still won't go down.

After a bit of more research on how to fix this, I realised I was solving the wrong problem here. I had to build the app, and no matter how awesome Ionic looked and functioned, it wasn't working out for me. Time to move elsewhere. But this time I had no more time to spend on experimenting with frameworks.

jQuery mobile. It might not be as hip as Ionic but it had a stable version. A good theme builder, has been around much longer than most other frameworks with decent docs. Expecting the worse, I quickly rebuilt whatever I had on the Ionic test app but this time using jQuery mobile and it was much better. No more memory leaks or other issues. It was smooth, even on a mediocre Android. The decision was made. jQuery mobile it is. It's not as bad as it might seem at first.

Compatibility Issues

After testing stuff out with jQM (jQuery Mobile), I started working on building the app. Only to find another major issue. jQM and Angular don't work very well together. jQM has it's own routing system, which probably takes precedence over the one Angular has. So loading pages from external .html files seemed impossible. Again, there might be a way, something obvious that I might have missed, but I had limited knowledge and even lesser time. Here's what I came up with.

jQM fills the visible screen with a div of the specified id that has the data-role="page" attribute. I'm no fan of working on a single file for the entire app. But that's the way it had to be done. Angular offers a solution in terms of directives. I'm not sure if this is the way they are supposed to be used, but it worked for me. Without any visible side-effects or downsides. 

Create a placeholder div with a custom directive. And then load the specified template in that div. 

<!-- department listing for events -->
<div data-role="page" id="events_main" ng-controller="eventsMainController" events-main></div>

<!-- event listing for individual department -->
<div data-role="page" id="events_department" ng-controller="eventsController" events-department></div>

<!-- schedule -->
<div data-role="page" id="schedule_main" ng-controller="scheduleMainController" schedule-main></div>

This way I could have my pages in separate files, and load them on the main index.html when the app starts.

angular.module('malharApp', ['malhar.controllers'])

// events
.directive('eventsMain', function () {
 return {
  templateUrl: "pages/events/main.html",
  transclude: true
 };
})
.directive('eventsDepartment', function () {
 return {
  templateUrl: "pages/events/events.html",
  transclude: true
 };
})

// schedule
.directive('scheduleMain', function() {
 return {
  templateUrl: "pages/schedule/main.html",
  transclude: true
 };
})

Onwards

Another feature of the app was an image of a map that could be zoomed and panned into. Not having learnt enough from my previous non-productive time-spent encounter with Ionic, I tried out a couple of libraries that could be used to implement pan and zoom capabilities for the map, namely svgpan and Open Layers. I finally settled for jQuery Panzoom. Great library. Another lesson learnt here.

Given limited time, choose the simplest way to solve your problem.

I didn't have to work with the map vector (SVG) when a high-res PNG was good enough.

Why Angular for static content

Separation of code and data. Given the amount of content, it would be a huge unmanageable mess to have everything in one file. There might be a performance improvement, but if you want someone to re-use the code for a future version of the app, or expect any sort of readability in your code, keeping data away from code helps. However, if there was a way to compile the resulting HTML generated after all Angular code loads, it would be worth trying. I'm not sure how much that would help in terms of performance.

Not every requirement can be satisfied

Having notifications for the events would be nice, but another caveat of using Angular and jQM together was discovered here. Two-way binding wouldn't work as expected. I had file read and write working (using a FileSystem API plugin) for storing the event notification preferences but the UI is where it was too much work. The app had to be released in a few days, and I knew that getting it to work would take me more time than I could give.

In the end, even if your attempts fail, you learn a lot. Stuff you wouldn't learn if you never tried. Stuff like Angular's $digest won't handle $scope variable changes outside of user interaction, the web FileSystem API's file writer will not reset file size when overwriting a file (this had me confused for several hours, before I realised), thinking twice before running git reset, using callback functions (see nodejs) when dealing with asynchronous code, etc.

You can download and try the app here: https://play.google.com/store/apps/details?id=org.malharfest.developer

Let me know what you think, or if you want a peek at the source.

Ugly code and Palindromes

When you try to figure out patterns yourself, and fail to find a solution for all cases, it looks something like this:

(Python code that generates palindromes, as opposed to checking whether each natural number is a palindrome or not)

import timeit
NUM = 100000

def get_palindromes(n):
  for i in range(1, n+1):
    if str(i)[::-1] == str(i):
      yield i

def get_palindromes_2(n, s=1):
  while s <= n:
    yield s
    if (s / (10 ** ( len(str(s)) / 2 ))) % 10 == 0 and (len(str(s)) % 2 == 1):
      s += 10 ** ( len(str(s))/2 )
    elif s == 9 or s == 99 or s == 999 or s == 9999 or s == 99999:
      s += 2
    elif ((s % 10 == 9 and (s / 10) % 10 == 9)) and s / 10 ** (len(str(s))-1) != 9:
      s += 2
    elif s / 10 == 0:
      s += 1
    elif s / 100 == 0:
      s += 11
    elif (s / (10 ** ( len(str(s)) / 2 ))) % 10 == 9 and (s / 10) % 10 == 9:
      s += 11
    elif (s / (10 ** ( len(str(s)) / 2 ))) % 10 == 9:
      if len(str(s)) % 2 == 1:
        s += 11 * (10 ** (len(str(s))/2 - 1))
      else:
        s += 11 * (10 ** ( len(str(s)) / 2 - len(str(s))/2 ))
    elif len(str(s)) % 2 == 1:
      s += 10 ** ( len(str(s))/2 )
    else:
      s += 11 * 10 ** ( len(str(s)) - len(str(s))/2 - 1 )


if __name__ == '__main__':
  print "Checking for all palindromes less than %s:" % (NUM,)
  print timeit.timeit('list(get_palindromes(NUM))',
    setup='from __main__ import get_palindromes, NUM',
    number=10)

  print "Generating all palindromes less than %s" % (NUM,)
  print timeit.timeit('list(get_palindromes_2(NUM))',
    setup='from __main__ import get_palindromes_2, NUM',
    number=10)
  
  print "Both return same results:"
  print list(get_palindromes(NUM)) == list(get_palindromes_2(NUM))

The results suggest the generating function is more than 20 times faster.

Checking for all palindromes less than 100000:
0.631178268752
Generating all palindromes less than 100000
0.0270419578788
Both return same results:
True
[Finished in 0.8s]

There might be a better palindrome generating algorithm here, haven't tested it though. Then again, it uses strings which are then converted to integers.

Don't do this in production or anywhere someone other than you reads the code you write.

More primes

Let's see how quickly we can calculate primes less than a million in other languages. Sieve of Eratosthenes is used again without any non-obvious language-specific optimizations.

For comparison, Python with the default interpreter takes 375ms.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;

public class Primes {
  public static ArrayList<Integer> gen_primes(int n) {
    boolean[] temp = new boolean[n];
    Arrays.fill(temp, true);
    temp[0] = temp[1] = false;

    ArrayList<Integer> primes = new ArrayList<Integer>();
    for(long i = 0 ; i < n ; i++) {
      if (temp[(int) i]) {
        primes.add((int) i);
        for(long j = i * i ; j < n ; j += i) {
          temp[(int) j] = false;
        }
      }
    }
    return primes;
  }

  public static void main(String[] args) {
    Date d = new Date(); long c = d.getTime();
    ArrayList<Integer> p = gen_primes(1000000);
    System.out.println((new Date()).getTime() - c);
  }
}

Possibly the fastest, takes around 20ms!

Node / JS

(function() {
  function gen_primes(n) {
    var temp = [];
    for( var k = 0; k < n; k++ ) {
      temp.push(true);
    }
    temp[0] = temp[1] = false;
    var primes = [];
    for( var i = 0; i < n; i++) {
      if (temp[i]) {
        primes.push(i);
        for( var j = i * i; j < n ; j += i ) {
          temp[j] = false;
        }
      }
    }
  }
  var now = Date.now();
  gen_primes(1000000);
  console.log(Date.now() - now);
})();

Node does it in around 90ms, while in the browser it takes anywhere between 100-200ms.

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace primes_test
{
    class Program
    {
        public static ArrayList gen_primes(int n)
        {
            bool[] temp = new bool[n];
            for (int i = 0; i < n; i++)
            {
                temp[i] = true;
            }
            temp[0] = temp[1] = false;

            ArrayList primes = new ArrayList();
            for (long i = 0; i < n; i++)
            {
                if (temp[(int)i])
                {
                    primes.Add((int)i);
                    for (long j = i * i; j < n; j += i)
                    {
                        temp[(int)j] = false;
                    }
                }
            }
            return primes;
        }

        static void Main(string[] args)
        {
            DateTime begin = DateTime.UtcNow;
            ArrayList a = gen_primes(1000000);
            DateTime end = DateTime.UtcNow;
            Console.WriteLine((end - begin).TotalMilliseconds);
            Console.ReadKey();
        }
    }
}

Almost as fast as Java, 22ms.

Generating Primes

Using the Sieve of Eratosthenes, because I keep forgetting.

import timeit
NUM = 1000000

def generate_primes(n):
    nums = [i for i in xrange(n)]
    for i in xrange(2, n):
        if nums[i]:
            yield nums[i]
            for j in range(i*i, n, i):
                nums[j] = False

def gen_primes(n):
    primes = [True] * n
    primes[0] = primes[1] = False
    
    for (i, isprime) in enumerate(primes):
        if isprime:
            yield i
            for j in range(i*i, n, i):
                primes[j] = False

if __name__ == "__main__":
    # print timeit.timeit("list(gen_primes(NUM))", 
        # setup = "from __main__ import gen_primes, NUM", number=1)

    # print timeit.timeit("list(generate_primes(NUM))", 
    #   setup = "from __main__ import generate_primes, NUM", number=1)

gen_primes is from SO: 3939660

generate_primes is what I came up with. It is slower, and because Windows, I cannot find out why, yet. (Might be because xrange(n) is slower than enumerate(n) and / or [True] * n is faster than xrange(n))

The timeit print statements must be run one at a time, running both gives different results than if they are run individually.

Finding all primes less than a million takes ~0.4s on my machine (i5-661, 8 gigs of RAM)

Dota 2 Heroes in Blender

I picked Ogre Magi so that I could compare to Valve's render in the shader mask guide[pdf]. Haven't been able to use all the 8 different grayscale masks, but there's more work to be done here.

Colour and normal maps were the easy part but then came the specular intensity and specular exponent masks. Using general techniques would achieve results like these. Too much glossy there. After much experimenting, here's the starter node setup for the materials that I finally used. A node group was created and used for each object and just the image textures changed.

One thing I feel I got right is the self illumination mask setup. Magi's weapon in this render corresponds closely to the one in Valve's shader guide.

Stuff I couldn't manage:

Transparency on the cape. I couldn't find any clues in the shader guide as to which mask corresponds to transparency. It could be the Fresnel mask but I still have to figure it out.

Specular highlights are not as prominent when compared to the render in the shader guide, but this I feel looks a bit more realistic.

Rim highlights. Absolutely no idea how to get that in blender. Maybe with appropriate lighting specific specular maps. These highlights are more specific to the game and may not be necessary in a model render.

Detail map mask. This might be easy and could be tried with Razor.

If you have any suggestions, improvements that could make the render better, or you need the source blend, please let me know.