Counting Bejeweled Boards

June 30, 2013

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?

Read the rest of this entry »

Advertisements

Linear Addition from the Log Domain

February 24, 2013

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

\log(x+y)

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

\log(x+y) = \log(\exp(\log(x)) + \exp(\log(y)))

These conversions between log and linear domains are slow and problems arise when x 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.

Read the rest of this entry »

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

September 30, 2012

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.

Read the rest of this entry »

SSL Certificate Verification and Httplib2

February 6, 2012

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.
Read the rest of this entry »

Creating a Basic Webpage with html5-boilerplate

December 30, 2011

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.

Read the rest of this entry »

Naive Sort in Prolog

October 15, 2011

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.

Read the rest of this entry »

An Empirical Analysis of QuickSelect and QuickMedian

September 28, 2011

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).

Runtime of QuickMedian and SortMedian Trials, sorted by trial conditions to show regularities

Read the rest of this entry »

An Epoch Poem

September 21, 2011

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.

Read the rest of this entry »

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

July 12, 2011

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/{}

Read the rest of this entry »

Sphinx 4 Acoustic Model Adaptation

July 1, 2011

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.

Read the rest of this entry »