Archive for the ‘technical’ Category

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?

(more…)

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.

(more…)

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.

(more…)

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.
(more…)

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.

(more…)

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

(more…)

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

(more…)

Gnome “Show Desktop” applet that only minimizes all windows

June 28, 2011

The “show desktop” applet in Gnome is more like a toggle button that switches between minimizing all windows and restoring all windows. I’ve never found the restore all windows behavior useful, it requires an extra mouse click, and I’m always jolted by the temporary flash of restoring windows.

For those few souls who share this peeve there is a simple way to replace the applet with a version that always and only shows the desktop.  Reproducing ruizscar’s instructions here:

  1. Install "wmctrl" (i.e., sudo apt-get install wmctrl)
  2. Add a “Custom App Launcher” to the desktop panel bar with the command "wmctrl -k on"

If you want to completely reproduce the “show desktop” applet, you’ll need to also set the icon.  For the default Ubuntu/Gnome theme (as of 11.04), the icon is located at: "/usr/share/icons/Humanity/places/24/gnome-ccdesktop.svg".  Hopefully that’ll get you in the right neighborhood depending on the theme/panel size you run.

Negation in Prolog

April 10, 2011

The first Prolog example in Bruce Tate’s Seven Languages in Seven Weeks has a bug.  Tate defines the predicate \+ to be “logical negation”, but this is incorrect.  It’s like logical negation, but differs in ways that cause straightforward queries to fail.

(more…)

CRAPL — Community Research and Academic Programming License

April 7, 2011

The Community Research and Academic Programming License (CRAPL) is an open source license drafted by Matt Might and is directed at researchers who produce code that is a byproduct of research.  This license is tuned to the current academic environment and its emphasis on publishing moreso than licenses like GPL, LGPL, and BSD.

(more…)