Posts Tagged ‘math’

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

Second Order Cone Programming with CVXOPT

December 18, 2010

CVXOPT is a convex optimization package for Python that includes a Second Order Cone Programming (SOCP) solver.  The SOCP solver takes a set of matrices that describe the SOCP problem, but these matrices are different than the matrices usually used to express the SOCP problem.  This post walks through the simple algebra steps to find relationship between the two formulations of the SOCP problem.

(more…)

What is the best sequence to tighten the lug nuts on a wheel with N nuts?

November 10, 2010

Nuts are numbered [0,N) as you travel around the circle, and we’d like to output the list of nut indexes to tighten, in order. For N=4, we’d tighten [0,2,1,4], although there are many equivalent solutions due to the inherent symmetry. For N=5, we have [0,2,4,1,3].

This problem actually came up when I was trying to pick a deterministic “maximally distant sequence” of colors for a visualization that I was doing. There are answers good enough (or better) for my visualization problem, but I feel like the question is an interesting one. One thing that probably needs doing is defining the objective function (i.e., “maximally distant”) in a more formal way.

This post is intended to shame my future self into looking at it again, one day!

Solving equations with exponential and polynomial functions of x: the Product Log Function

October 18, 2009

I was trying to solve an equation of the form cx^p=q^x for x, but couldn’t figure out how to do the algebra needed to isolate x.  The actual problem was to find when an algorithm with O(n^2) runtime performance would have a shorter runtime than an algorithm that is O(2^n).

Text-based searches weren’t turning up anything, so I tried to see how Wolfram Alpha would solve it.  Turns out there is a neat tool called the Product Log function, aka the Lambert W function, that can be used to find a closed-form solution to this equation.  The Wikipedia article explains the solution method, but you basically need to reorganize the original equation into the form y = x e^x using algebraic and logarithmic operations and then x=W(y).  Note that the solution may not be unique; W(y) is a multivalued function.

Of course, for my original problem where I was actually trying to find the closest integer less than or equal to x, and given that q^x grows rather quickly, it is sufficient to use a spreadsheet to calculate the two sides of the original equation for all small values of x.

LaTeX test

August 29, 2009

WordPress supports \LaTeX.  Voila: $latex e^{j\pi}+1=0$ is e^{j\pi}+1=0.

Note that you must start your equations with “$latex” instead of just “$”. Also, here’s how to quote latex source code.