Alphanumeric phone numbers

Posted on

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

Posted on

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

Posted on

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

Posted on

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

Posted on

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

Posted on

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

Posted on

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.

On the price of watermelons

Posted on

Watermelons are huge, cheap, and contain a lot of water. The edible part is about 92% water. I wanted to find out whether water from watermelons is cheaper than bottled water at the supermarket.

I compared prices with other beverages, each is the cheapest in its category. Because prices change all the time, these numbers should be taken with a grain of salt:

Item Price per litre (AUD)
Home Brand Cordial (diluted 1:4 with free water) 0.23
Water 0.46
Cheap soft drink 0.63
Milk 0.89
Watermelon Juice 1.05
Tropical Juice 1.90
Lipton Iced Tea 2.57

So it’s settled. You wouldn’t save anything juicing watermelons unless you usually buy natural juice, which it turns out quite pricy!

This is how I got the price of a litre of watermelon water:

Water is 997.1kg/m3 (0.9971g/mL) at 25°C
1000mL * 0.9971g/mL = 997.1g water
997.1g / 91.45% = 1090g watermelon
1.090kg * 96c/kg = 1.05c/L for watermelon water.

This is not science: I ignored the watermelon rind, and the 6.2g / 100g of sugars which would be dissolved in the water. If anybody juices a watermelon in a lab then I will revise these numbers.

Samoan Language Section

Posted on

I’ve now uploaded my Samoan vocabulary (~1200 words), and unfinished introductory guide. The audio works in Firefox on Ubuntu, but I haven’t tested it in other browsers.

I have around a thousand words and a few hundred examples which I haven’t recorded yet, and the guide/phrases contain many unfinished sections. If you are a native speaker of Samoan, or are interested in helping, then let me know.

You can find the section at: https://mike42.me/sm

Update: I’ve made MP3 versions of the audio files, and they can now play in all major browsers.