When you run ./gradlew in your Term, it sometimes spawns a few java utilities, like the linter. On OS X, these java utilities greet you with an annoying Java icon that appears and never disappears in your Dock, plus you lose focus on your Term.

To hide this icon forever (for all java apps started from your shell), add this line to your ~/.bashrc or ~/.zshrc:

export JAVA_TOOL_OPTIONS="-Dapple.awt.UIElement=true"

Replace the word “Cat” by “Pony” in all the files of the current directory and subdirectories:

a=Cat; grep -lr $a . | xargs perl -pi -e s/$a/Pony/g

Just in case you’re stuck in an hotel with a $40/day wifi access. The usual solution is to spoof a MAC address (ie. use one from someone already connected). But how to list them?

On OS X, the easiest is to use the arp command:

$ arp -an | grep -v incomplete

If you want to make sure the device is currently connected, use nmap (replace 10.0.*.* by your subnet):

$ nmap -sP 10.0.*.*

And then, you just have to spoof one of the MAC address:

$ sudo ifconfig en0 ether CA:FE:CA:FE:CA:FE

I’ve been using the stock Android emulator these days. And the lack of copy/paste is annoying. There is a way to input text to any adb connect devices using adb shell input text, so I added a couple of functions to my .zshrc (works with bash too).

ai () { echo "$@" | sed "s/%/%%/g" | sed "s/ /\%\s/g" | xargs adb shell input text }
alias aip='pbpaste -Prefer txt | sed "s/%/%%/g" | sed "s/ /\%\s/g" | xargs adb shell input text'

Usage, to input text (including spaces) to your device:

$ ai test is cool

Usage, to paste the text in your clipboard to your device:

$ aip

Note: works on OS X, replace pbpaste -Prefer txt by the linux / windows equivalent.

• StayFocusd – to limit my time spend on Hacker News and Reddit to a maximum of 10 minutes / day.
• Pocket / Send to Kindle – to save articles to read them later (I’ll drop Pocket soon, I noticed I’m reading much more stuff on my Kindle).
• Disconnect – to stay out of sight from (some) analytics and other trackers.
• Pushbullet – to write SMS from my computer and share stuff between my Android devices and my computer.
• uBlock Origin – because some sites are cluttered with ads, good players whitelisted.
• HTTPS everywhere – use SSL when available.
• Stylish (to apply a Dark theme on my favorite sites: GitHub for example – reduce eye strain).
• Tampermonkey – with a bunch of home-made scripts hacks.

I’m using ack 100 times a day, it’s written in Perl and a bit slow when grepping a big directory. I recently switched to ag (aka the_silver_searcher). It’s much faster and ignores file patterns from your .gitignore. I see no reason to use ack anymore so:

$ brew install the_silver_searcher
$ brew remove ack
$ echo "alias ack=ag" >> ~/.zshrc # my muscle memory doesn't want to switch

Introduction

Here is an old article I wrote in January 2009. Since then, I received some emails and a lot of 404 errors, so I decided to repost it on this “new” blog. You can find the code here on github.

Genetic algorithm, another metaheuristic inspired by evolution of species. You can read the description of the algorithm on the genetic algorithm article on Wikipedia.

I applied the algorithm to a concrete problem: help lazy programmers and non-programmers to write file converters. I had to write file converters to unify all (more or less) formatted input files into one kind of CSV file. Each of these converters is made using the right combination of filtering / regexp matching / line splitting.

Description

So I wrote a program based on genetic algorithm where an individual is composed by 3 “genes”:

• a list of filters (remove consecutive spaces, replace tabs by spaces, …)
• a list of basics regexp to extract formatted basic blocks(int, float, date, line separator, …)
• a list of cleaning functions (remove empty cell, merge cells, …)

The fitness of an individual is calculated using a sample file to parse that goes through the genes (filters / regexp / cleaning functions). The result of this process is a CSV file that can be compared to the expected sample result (that I wrote manually). The comparison uses the SequenceMatcher of the difflib Python stantard module, it returns the fitness: a float. A fitness close to 1.0 means the results is close to the expected CSV format. When the fitness is exactly 1.0, that means the converter works perfectly for the sample.

Here is a sample file I wanted to convert:

08/12        Hello world 06/12
Paris 121231231         - 22,29
08/12   Something something ... 04/12
1111 1111 1111 1111         - 14,35
08/12   something else
        - 12,96
26/11   Vir AAAAA
AAAAAA 2008     264,51

into this csv file:

"08/12","Hello world 06/12","Paris 121231231","-22,29"
"08/12","Something something ... 04/12","1111 1111 1111 1111","-14,35"
"08/12","something else","","-12,96"
"26/11","Vir AAAAA","AAAAAA 2008","264,51"

The program prints for each generation the 5 bests individual (I’m using elitism, so the best individual is always kept from a generation to the next one). A sample run:

$ python ga.py tests/sample1.txt tests/sample1.expected result1.pickled
Generation: 0 (mutation rate=10)
0.53772
0.42507
0.30406
0.28598
0.26389
Generation: 1 (mutation rate=10)
0.53772
0.42507
0.32684
0.30406
0.26799

...

Generation: 271 (mutation rate=15)
1.0
0.96025
0.95107
0.91779
0.87886
"08/12","Hello world 06/12","Paris 121231231","-22,29"
"08/12","Something something ... 04/12","1111 1111 1111 1111","-14,35"
"08/12","something else","","-12,96"
"26/11","Vir AAAAA","AAAAAA 2008","264,51"

filters: str_remove_consecutive_spaces, str_remove_somespaces, str_strip, str_remove_consecutive_spaces
regex: ([0-9]{2}/[0-9]{2})(.+?)(
)(.+?)(-?[0-9]+[.,]+[0-9]+)
cleaners: clean_strip, _in, _in, _in

Conclusion

The good:

• It’s fun to watch your program evolve 😉
• You are lazy and don’t want to write _many_ of this kind of file converters. This was used in a real life problem, with more than 200 different input file formats.
• With a good interface and if the basic functions and genes size are well-defined, a non-programmer can create his own parser.

The bad:

• The resulted parsers are not optimal

The ugly:

• Of course it’s quite easy to write such genes by hand
• It may never converge to 1.0 and generated parsers of fitness != 1.0 are useless (this may not be the case for other kind of GA applications)
• You need many well-chosen primitives to cover a wide set of solutions

What next? Write a simple Web interface to help people generate their own converters. Add new construction blocks. Use the same idea to automatically plot any kind of formatted data.

To delete only issue/ and feature/ branches:

$ git branch --merged master | grep -E "issue/|feature/" | xargs git branch -d

In my code, I sometimes add some FIXME tag (just the FIXME string in a comment or in a debug print). And before staging them in git, I review my diff to check for them. And rarely I miss one FIXME line or debug print, stage it and then commit it. To avoid that, I just wrote a quick pre-commit hook that greps the regexp "[Ff][Ii][Xx][Mm][Ee]" in staged diff using the command git diff --cached -G "[Ff][Ii][Xx][Mm][Ee]".

Here is the full script:

#!/bin/sh
exec 1>&2
FORBIDDEN_RE="[Ff][Ii][Xx][Mm][Ee]"
if [ $(git diff --cached -G "$FORBIDDEN_RE"|wc -l) != 0 ]; then
    git --no-pager diff --cached -G "$FORBIDDEN_RE"
    echo
    echo "ERROR: You're trying to commit a line containing the $FORBIDDEN_RE re"
    exit 1
fi

Put that in the file .git/hooks/pre-commit and next time you’re trying to commit a file containing “FIXME”, it will abort and print you the involved diff.

Note that you can ignore the pre-commit hook with the following command:

$ git commit --no-verify

I now added my specific temporary folder to my system wide gitignore. Small impact for me, a huge impact for multi-project people I work with 😉

$ sudo git config --system core.excludesfile /etc/gitignore
$ sudo sh -c "(echo '*~'; echo ".DS_Store"; echo "tmp-max/") > /etc/gitignore"

Sorted Sets: ZSET

Redis ZSETs are a very good to store ordered data like leaderboards:

• You need to get the current score for an userid (every SQL or NOSQL
  can do that efficiently)
• You need to get the current rank for an userid
• You need to get a list of pairs userid/score sorted by score

Datastructure

In the Redis documentation, we can read complexity is O(lg(n)) to ZADD / ZRANK / ZREM and O(1) for ZSCORE. How are they implemented ? O(lg(n)) you said… hmmm smells like a tree or binary search. ZSCORE (a kind of search) in constant time… hmmm smells like a hashtable. So how is it implemented ? a mix of hashtable and tree ? No, but that’s close, it’s a mix of hashtable and Skip List. Skip list are an alternative to balanced binary tree.

You should read the original Skip List paper.

From the redis documentation:

ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure.

The elements are added to an hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this “view”).

So, how to perform a ZRANGEBYSCORE in linear time ?

1. search the min element. O(lg(n)) complexity (with n=|set|)
2. start from min and follow links to the next element until you reach max. O(m) complexity (with m elements returned)

Also, there is a modification from the original skip list implementation, level 1 list is doubly linked, so it gives you: ZREVRANGE, yeah !

I started to code some random problems from Project Euler. To have an extra hint of which kind of algorithm I’m looking for, I made the following table.

Read it like: “Assuming a computer can do 10 000 000 operations/sec, with a O(n^2) algorithm, you can solve a n ~ 3000 under a second”

Complexity      |   n for 1 second  |   n for 1 minute
------------------------------------------------------
O(1)            |   inf             |   inf
O(lg(n))        |   huge            |   2^(10^7)
O(sqrt(n))      |   10^14           |   36*10^16
O(n)            |   10 000 000      |   600 000 000
O(n*lg(n))      |   526 172         |   24 446 750
O(n*sqrt(n))    |   46 415          |   711 378
O(n^2)          |   3162            |   24 494
O(2^n)          |   23              |   29
O(n!)           |   10              |   12

Project Euler problems should be solved under 1 minute (even in Python, most problems I solved has been < 2 secs), so if the input N is ~10 000 000, you should look for a O(n*lg(n)) solution or better.

Also if you’re developping Python code, you should have a look at these Python Time Complexity Tables. I think other language libraries use the same underlying datastructures and algorithms.

$ echo "keys *" | redis-cli | grep user 
                | xargs -I % sh -c "echo hget % name | redis-cli"

I updated my bitcoin arbitrage project: https://github.com/maxme/bitcoin-arbitrage

More modular and now include trading bots if you want to automate buy and sell orders on some exchanges.

I released a quick hack to watch for bitcoin arbitrage opportunities. Code and documentation are on github: https://github.com/maxme/bitcoin-arbitrage

I made some bitcoins with it, pushing coins from mtgox to bitcoin central and back. If you are crazy enough to plug a API-trading tool, you should be one of the few bitcoin automated arbitrage trader.

Run a webserver at http://localhost:8000 serving current directory (and subdirectories)

$ python -m SimpleHTTPServer

Another tip to debug html5 apps for mobile on your desktop: install the Ripple Chrome Plugin

Very useful to debug webapps:

$ /Applications/Google Chrome.app/Contents/MacOS/Google Chrome --disable-web-security

I read this very interesting snippet in the Wikia Super Mario Bros’ page

“Interestingly, in the very first portion of World 1-1, the developers designed it so that the a newcomer almost always gets a Mushroom. In the first level, there are blocks that the player goes under. A menacing Goomba approaches the player, and instinctively the player jumps over it. By the time the player reaches the Goomba and jumps, they will hit a ? block above that would reveal a mushroom. The mushroom goes to the right, hits a pipe and comes towards the player. Since the mushroom resembles the Goomba, the player thinks to jump over it again. Doing this, however, will almost always lead the player to jump right into the Mushroom since after they jump they hit another block from above which causes them to come back to the ground and hit the mushroom. This was to teach players that Mushrooms were a positive thing in the game.”