Counting Bejeweled Boards

I’ve recently become hooked on Bejeweled Blitz, an addictive match-three puzzle game. It’s got enough bright colors, explosive sounds, and variable reward mechanics to redline your dopamine levels.

Coders have an interesting coping mechanism to deal with these sorts of things: program a bot to automate the addiction. This is a bit better than grinding for points; it’s a nice programming exercise that is slightly subversive and without intellectual property issues that could worry one’s employer.

During the design phase of the bot, I’ve become stuck on a little mathematical question that has led me on a journey from coding to mathematics via some impressively knowledge-dense internet resources:

How many different Bejeweled boards are there?

Advertisement

Linear Addition from the Log Domain

Some speech recognizers and machine learning algorithms need to quickly calculate the quantity:

when given only and . The straightforward algorithm first uses the exponential function to convert the log values to the linear domain representation and , then performs the sum, and finally uses the log function to convert back to the log domain:

These conversions between log and linear domains are slow and problems arise when is too large or small for a machine’s floating point representation.

Luckily, there is a clever approximation method that allows quick, accurate calculation with a relatively small precomputed table.

How to Upload One File to Amazon Glacier, for Paranoid Developers

Amazon Glacier can be used as a data sanctuary-of-last-resort.  The API is simple and Amazon’s AWS offerings inspire Google-level confidence.  While gleeful to augment my collection of ad-hoc backup methods, I was also wary of trusting the github projects that were sprouting like dandelions.

But eventually my old Ubuntu distro wore out, and I decided to create my own Glacier “client” before upgrading.  Its mission: upload one file to Glacier.  No GUI, no command-line interface, not even a progress bar. Lo and behold, Amazon has a tutorial for exactly this.  If you are familiar with the Java/Eclipse (or .Net) ecosystem, then you too can roll your own archival tool with very little time investment and no third-party vendor lock-in.

SSL Certificate Verification and Httplib2

I’ve started experimenting with httplib2 to make REST calls to Parse.com. It looks decent enough, but it doesn’t include a root certificate that can validate the Parse SSL certificate. Below, I show examples of (1) the easy work-around and (2) the real solution.

Creating a Basic Webpage with html5-boilerplate

Here’s how I put together a basic personal homepage that is accessible, reads well on mobile devices, and follows current HTML5 and CSS3 best practices.

Naive Sort in Prolog

The simplest way to code a sort in Prolog is to describe what a sorted list looks like.  A sorted list is a permutation of some given list such that elements that appear earlier in the list are smaller than elements that appear later in the list.  In SWI Prolog:

srt(X,Y) :- permutation(X,Y), isSrt(Y).

isSrt([]).
isSrt([_]).
isSrt([H,I|J]) :- H=<I, isSrt([I|J]).

The beauty of this solution is that Prolog does all the dirty work of finding a sorted Y for our given X. The darker side is that Prolog’s satisfaction mechanism carries out a brute force search through all possible permutations of the given list. This is dangerous; compare the runtimes of our naive sort and the Prolog built-in sort (which is decidedly less naive):

% 5 seconds vs. something < 0.01 seconds
reverse([1,2,3,4,5,6,7,8,9,10],X), profile(srt(X,Y)).
reverse([1,2,3,4,5,6,7,8,9,10],X), profile(msort(X,Y)).

Not great, and notice how fast the worst case time of O(n!) grows:

% 55 seconds vs. something < 0.01 seconds
reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(srt(X,Y)).
reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(msort(X,Y)).

This is to be expected; if we want to be picky about how the job gets done, we can be more explicit in our description. So let’s ignore performance and and see how to write a declarative “permutation” predicate from scratch.

An Empirical Analysis of QuickSelect and QuickMedian

The QuickSelect algorithm is an efficient way to find the N-th largest element in a list. The QuickMedian algorithm uses QuickSelect to efficiently find the middle element(s) of the array.

This blog post sketches how QuickSelect and QuickMedian work in general and in my Java implementation. The bulk of the post discusses the plot of QuickMedian vs. SortMedian’s runtime shown below (click the image for more details).

An Epoch Poem

A folk explanation of genetic algorithms for my evolutionary computing class, to be recited with creative pronunciation:

---

A farmer was planting to reap,
Wished to profit the max on the cheap.
Trade-off soil, spacing, and blight,
Planting time, market value, and light,
But: too-complex his goals were to meet.

Bash one-liner using sox to batch convert the sampling frequency of audio files

A bash one-liner to batch convert the sampling rate of WAV files using the SoX tool.  The example will resample *.wav files in the current directory to 8000Hz and place the output in an existing subdirectory called 8000Hz.

The one-liner below is overkill for this task, but the extra arguments provide a starting point for modification for related tasks.  The use of find/xargs should help the one-liner deal with very large numbers of audio files and filenames that contain whitespace.

Code

---

find . -maxdepth 1 -name '*.wav' -type f -print0 | xargs -0 -t -r -I {} sox {} -r 8000 8000Hz/{}

---

Sphinx 4 Acoustic Model Adaptation

This is a writeup of the steps I took to perform acoustic model adaptation for an acoustic model to be used in Sphinx 4.  I followed the well-written CMU howto.  I performed all steps on a mostly-new Ubuntu 11.04 install and adapted the Communicator acoustic model for use in Sphinx 4.  Keep an eye out for paths that may be different on your system and any error messages that pop up when running these commands.

I also generated a new, full set of adaptation prompt data from the CMU ARCTIC prompts.