Australian telephone tones

I made this set of telephone tones for an IP-PBX running asterisk. A lot of telephone-related audio files on the Internet seem to be recordings of actual beeps, so the quality is not great. Given that they are trivial to synthesise with Audacity, I made these:

To convert them to .ulaw format for asterisk (click here to download archive), I saved them as a .wav file and ran this bash script over the directory:

#!/bin/bash
for a in *.wav; do
    sox $a -r 8000 -t ul $a.ulaw
done

Making tones for other countries

Get a copy of the document "Various tones used in national networks (According to ITU-T Recommendation E.180) (03/1998)". It describes the tones used in most of the world. There is also a Cisco tones database, which has slightly different numbers.

Open up Audacity and use the Generate → Tones feature to make the first beep. Where there are multiple frequencies, make each frequency in different tracks, then merge them into a single track.

Use Generate → Silence to add the delay on the end, then continue from there

Afterward, you need to normalise the volume. Read the number from the volume Cisco tones database, then use Effect → Amplify, and set the new peak volume to the value shown — for the above tones this is -10 or -13dB.

HP Mini 210 review

I used a HP Mini 210 netbook for around 18 months. It costed just $329 AUD when I bought it, and had Windows XP and a 160GB hard drive.

I was originally interested in dual-booting Windows alongside Linux, but HP support proved to be very stubborn and would not provide recovery disks or the Windows licence key, so I ran it with only Linux instead.

Here are some features to note:

  • An SD card can be placed in the slot and stays out of the way.
  • The VGA port makes it suitable for doing presentations.
  • The battery life is not fantastic. Around 3 hours when new, and reduced to just 20 minutes or so by the first year.
  • Not particularly durable. The right-click stopped working on the mousepad after a while. I enabled mac-style gestures in Ubuntu to overcome this.
  • The ventilation is poor. It has no vents on the bottom at all, which is great for keeping the inside dry, but it has a very weak fan and does not handle heavy loads gracefully.

Some things you can do to improve it.

  • As soon as I found out how to open the case (video), I got an Intel SSD, which was quite expensive, but can be used in whatever netbook you have. It makes it quieter, faster, more power efficient, and removes the shock-sensitivity that plagues notebook hard-drives.
  • Consider getting a high-capacity battery. I replaced the dead standard size one with a cheap 3rd-party battery (link), but it could still do with more power.
  • The default install is filled with crapware. Either reinstall windows or run something else. GNU/Linux compatibility is great, and it also runs Windows 7 with no worries. It turns out your Windows XP key is inside the case, so open it up and use it.

It was a good laptop for the price, but not exceptionally fast, durable, or long in its battery life. This netbook should be purchased with the understanding that it will have a short life.

Alphanumeric phone numbers

Some popular phone numbers (eg. 1300-FOOBAR) are not numbers at all. If you are running a VOIP server then you may be interested in this snippet of PHP code to convert them into actual numbers, allowing users to dial by typing the more familiar form.

function normaliseTelephoneNumber($start) {
	/* Return an extension with numbers substituted in place of letters for dialling */
	$map = array(	"A" => "2", "B" => "2", "C" => "2",
			"D" => "3", "E" => "3", "F" => "3",
			"G" => "4", "H" => "4", "I" => "4",
			"J" => "5", "J" => "5", "L" => "5",
			"M" => "6", "N" => "6", "O" => "6",
			"P" => "7", "Q" => "7", "R" => "7", "S" => "7",
			"T" => "8", "U" => "8", "V" => "8",
			"W" => "9", "X" => "9", "Y" => "9", "Z" => "9",
			"+" => "+", "*" => "*", "#" => "#");
	$new = "";
	$hasnumber = false;
	$ext = strtoupper($start);
	for($i = 0; $i < strlen($ext); $i++) {
		$c = substr($ext, $i, 1);
		if(isset($map[$c])) {
			$new .= $map[$c];
			if($hasnumber == false) {
				/* No numbers before letters */
				return $start;
			}
		} else if(is_numeric($c)) {
			$new .= $c;
			$hasnumber = true;
		}
	}

	if($hasnumber == true) {
		return $new; /* Return numeric version as appropriate */
	} else {
		return $start; /* Leaves full words like "joe" or "bazza" unchanged */
	}
	return $new;
}

Note that this will only alter the number if it begins with numbers. This is to make sure that (at least in my case) the local network extensions don't get messed with:

echo normaliseTelephoneNumber("1300-FOOBAR")."n"; /* 1300366227 */
echo normaliseTelephoneNumber("mike")."n"; /* mike */

Introducing BigInteger

Most ordinary-scale programs don’t use very large numbers, but today I’ll show you how to use Java to do some more serious calculating, with the Fibonacci numbers as an example:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

The numbers in this sequence always get larger, so you don’t need to be a software engineer to see that int and long wont be big enough. Just to highlight the problem, here is a naive approach to listing the Fibonacci numbers:

class FibonacciLong {
	static long solutions = 0;

	public static void main(String[] args) {
		long num1 = 0;
		long num2 = 1;
		long tmp;
		solution(num1);
		solution(num2);
		while(true) {
			tmp = num1 + num2;
			solution(tmp);
			num1 = num2;
			num2 = tmp;
		}
	}

	static void solution(long number) {
		solutions++;
		System.out.println(solutions + "t" + number);
	}
}

The output of this program overflows after the 93rd term. Java only uses signed integer types, so we end up with a negative number:

1	0
2	1
3	1
4	2
5	3
6	5
....
92	4660046610375530309
93	7540113804746346429
94	-6246583658587674878

To find larger values, we can use the BigInteger class, under java.math. They are constructed like this:

BigInteger num1 = new BigInteger("0");

They don’t really work like the primitive types. They are manipulated with methods like .add() and .subtract(), rather than the operators that we are accustomed to: + - * / %.

The below code has been written with BigInteger instead of long. It will return the nth term of the Fibonacci sequence, or enumerate solutions until the cows come home.

import java.math.BigInteger;

class FibonacciBigInteger {
	static long solutions = 0;
	static long find = 0;

	public static void main(String[] args) {
		if(args.length >= 1) {
			find = Long.parseLong(args[0]);
		}
		BigInteger num1 = new BigInteger("0");
		BigInteger num2 = new BigInteger("1");
		BigInteger tmp;
		solution(num1);
		solution(num2);

		while(true) {
			tmp = num1.add(num2);
			solution(tmp);
			num1 = num2;
			num2 = tmp;
		}
	}

	static void solution(BigInteger number) {
		solutions++;
		if(find == 0 || solutions == find) {
			System.out.println(number.toString());
			if(find != 0) { System.exit(0); }
		}
	}
}

The good news is that this program is now capable of working with numbers too large to say aloud. So today is a good day to start using Unix’s wc program to appreciate how big these numbers actually are:

mike~$ java FibonacciBigInteger 420000 | wc -m
87776

Subtract one character because there is an end-of-line in the output— and this means that the 420,000th Fibonacci number is 8775 digits long. We have discovered a new fact!

Note: There is still one variable in the program above that will overflow eventually, so you should also convert that to a BigInteger if you are hoping to calculate past about the nine quintillionth Fibonacci number (which you would be crazy to do with this method).

Palindromes

This is a highly miscellaneous Java snippet to find palindromes.

It will read stdin line-by-line and spit back the palindromes it finds.

import java.io.*;

class Palindrome {
	/* Return palindromes from a given list of words read from stdin */

	public static void main(String[] args) {
		boolean okay;
		String line;
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		do {
			try {
				/* Read a line, and spit it back again it if is a palindrome */
				line = input.readLine();
				if(isPalindrome(line)) {
					System.out.println(line);
				}
				okay = true;
			} catch (Exception e) {
				/* Exception will be raised after end-of-file */
				okay = false;
			}
		} while(okay);
	}

	static boolean isPalindrome(String test) {
		/* Return true if a string is palindromic, false otherwise */
		int len = test.length();
		if(len <= 1) {
			/* Disallow null / single-char palindromes */
			return false;
		}

		for(int i = 0; i < len; i++) {
			/* Compare first and last, second and second-last, etc) */
			if(test.charAt(i) != test.charAt(len - 1 - i)) {
				/* Found different letters, stopping. */
				return false;
			}
		}
		return true;
	}
}

On UNIX, you could feed it a dictionary to list all of the palindromes:

java Palindrome < /etc/dictionaries-common/words

On my computer that returns 57 palindromes made from ordinary words:

aha	bib	bob
boob	civic	dad
deed	deified	did
dud	eke	ere
eve	ewe	eye
gag	gig	hah
huh	kayak	kook
level	ma'am	madam
MGM	minim	mom
mum	non	noon
nun	oho	pap
peep	pep	pip
poop	pop	pup
radar	redder	refer
rotor	sagas	sees
seres	sexes	shahs
sis	solos	stats
tat	tenet	tit
toot	tot	wow	

There are certainly more if we allow 1-letter words or case-insensitive matching (allowing all sorts of proper nouns), but I really don't think they count.

Finding prime numbers

It’s not so hard to calculate small-ish primes. The below method is called a prime sieve, and can be done manually:

Take two, the smallest prime number.
We know that no multiples of two are prime (4, 6, 8, 10, 12 etc), so we can cross them off our list and just print two.
Then we go to 3. 3 is prime. But 6, 9, 12 and 15 can’t be, so we print 3 and cross those multiples off.
4 has been marked as not prime, so we skip it.
5 is prime, so we cross off 10, 15, 20.
so on and so forth

Computers are much better at this than humans though, so I wrote this algorithm up in java. You can find all primes up to n fairly quickly (for small values of n).

class Primes {
	public static void main(String[] args) {
		int searchMax = 16777216;
		if(args.length == 1) {
			/* Allow over-riding the maximum */
			searchMax = Integer.parseInt(args[0]);
		}
		boolean[] isprime = new boolean[searchMax];

		int i, tmp, count = 0;

		/* Initialise */
		isprime[0] = isprime[1] = false;
		for(i = 2; i < searchMax; i++) {
			isprime[i] = true;
		}

		/* Main loop */
		for(i = 2; i < searchMax; i++) {
			if(isprime[i]) {
				System.out.println(i);
				count++;
				tmp = i * 2;
				while(tmp < searchMax) {
					isprime[tmp] = false;
					tmp += i;
				}
			}
		}
		System.err.println("Found " + count + " primes between 1 and " + searchMax + " non-inclusive");
	}
}

Of course, the limitation of this is that java isn’t terribly good at handling larger arrays, so I wouldn’t expect more than a few million primes from this code.

Update: The above code was tested for finding the first 7 million prime numbers.

Gettting lost with depth-first search

I was thinking about how to make mazes, and ended up making a maze generator.

It’s based on ‘depth-first search’, a recursive algorithm to make a spanning tree. Example output below:

Unfortunately for us, java doesn’t particularly like deep recursion, so this generator will fizzle out with an error on really big mazes. On the other hand, it can produce output as HTML:

You can download the maze generator here:

It’s a command line program. From the terminal, the usage is like this:

java -jar MazeGenerator.jar [width] [height] [formatting]

Width/height will change the size of your maze. You can set the format to ‘html’, or type in a character for the filled-in blocks to be. (The default is u2588 ‘Solid block’).

Solving the eight queens puzzle

In the eight queens puzzle, you need to place eight queens on a chessboard so that they aren’t attacking eachother. It has 92 solutions.

I implemented one method for solving the problem. It works for any nxn chessboard, but it’s not so fast with large boards.

You can invoke this with java -jar Queens.jar for an 8×8 board, or java -jar Queens.jar n for an nxn board with n queens.

It works by processing the board in vertical strips, first placing a queen in the top-right, and then attempting to place a queen in the second column at the first available space. Once it crosses the board like this, it has found a solution, but it goes through plenty of bad combinations first.

Update: online solution-viewer is now running to make that command-line output more useful.

Beautiful QR Codes

The verdict is in. QR codes are ugly. But they don’t have to be. Check out the modified code featured on this Wikipedia article. You don’t need to be a QR Code expert to do something like that.

The basic idea is that QR codes have error Correction. We can generate codes which store the data in multiple places, so that scanners will still read them if they are damaged.

Scripting the whole operation

Tedious image editing is not my cup of tea, so I made a PHP class to apply some templates to QR codes and add a centred logo for us.

Note: If you don’t have ImageMagick for PHP, read this page. On Ubuntu, apt-get install php5-imagick worked fine for me.

This is the basic formula:

QR Code + Template + Logo = Pretty PR Code

First we need the QR code. It is best generated with the phpqrcode library. Adding the logo wont work unless we use high error correction (H):

QRcode::png("http://bitrevision.com", "code.png", 'H', 8, 0);

After that, code.png looks like this:

Now the templates. Note that we used 8×8 pixels per block and 0 for the border above. The resulting code may line up with one of these templates, adding white lines over the image. Save these images to a ‘template’ folder:

Next, the logo. We have one of those:

Time for the code. This class will do most of the work. Just check the template folder contains an overlay that fits your code.

class QR_Pretty {
	public $template_base = "template/template-{SIZE}.png";
	public $qr = false;
	public $geometry = false;

	function prettify($file, $logo, $output = '') {
		/* Load image */
		$this -> qr = new Imagick();
		$this -> qr -> readImage($file);
		$this -> geometry = $this -> qr -> getImageGeometry();

		/* Perform modifications */
		$this -> add_template();
		$this -> add_logo($logo);

		/* Output image */
		if($output != '') {
			$this -> qr -> setImageFileName($output);
		}
		$this -> qr -> writeImage();
	}

	private function add_template() {
		/* This will overlay a template containing white lines,
			to make the QR codes look less code-ful */
		$size = $this -> geometry['width'];
		$template_filename = str_replace("{SIZE}", $size, $this -> template_base);
		$template = new Imagick();
		$template -> readImage($template_filename);
		$this -> qr -> compositeImage($template, imagick::COMPOSITE_OVER, 0, 0 );
	}

	private function add_logo($logo_file = false) {
		/* This places a logo in the middle of the QR code,
			64x64 would be advisable :) */
		if(!$logo_file) {
			/* No logo to add */
			return false;
		}
		$logo = new Imagick();
		$logo -> readImage($logo_file);
		$logo_size = $logo -> getImageGeometry();
		$x = ($this -> geometry['width'] - $logo_size['width']) / 2;
		$y = ($this -> geometry['height'] - $logo_size['height']) / 2;
		$this -> qr -> compositeImage($logo, imagick::COMPOSITE_OVER, $x, $y);
	}
}

To use the above class is quite simple. Once you have code.png, logo.png, and a folder full of templates, just do this:

$qr = new QR_Pretty();
$qr -> prettify("code.png", "bitrevis.png", "pretty.png");

That gives us pretty.png, which looks like this:

Thanks to that error correction, this picture still scans and takes us to http://bitrevision.com. Slightly larger logos can be used, but 64×64 looks good and scans reliably. Try embedding logos with transparency too!

This means no more excuses for ugly QR codes. Integrate this into your scripts right away.