Archive for August, 2009

Farkle Odds

Farkle is an old dice game popular at parties and in bars. It’s a folk game, so the exact rules and scoring vary from place to place. I was introduced to the game on Facebook, where there is an online flash version. Basically, the game is played in rounds. During each round, you roll up to 6 dice. Certain die combinations are worth points. If you score some points during a roll, then you must take at least some scoring dice away and add those points to your point total for the round. Then you have the option of rolling again or standing pat. If at any time you roll and you don’t score, you “Farkle” and lose all of your points scored so far for the round. If you stand pat, then you can “bank” your points from the current round towards your total points for the game. In the flash version on Facebook, the following die combinations can score:

  • Any single 1 or 5
  • Three of a kind
  • Four of a kind
  • Five of a kind
  • Six of a kind
  • Three pairs
  • 1 through 6 straight run

On every successful roll, you should be taking at least one die away. If you happen to score all of your remaining dice during a roll, you can continue the round with all 6 dice again.

So I got to wondering, what are the probabilities of rolling various die combinations in Farkle? How often do you score, and how often do you Farkle? So I made the following tables.

Read Full Post »

Currency Parsing, Regular Expressions

ASP.Net 2.0 has some very powerful client-side web page validation features, including classes that emit javascript validation code to the user’s web browser.  The CompareValidator, allows one to test whether the value entered into a text box is convertible to a given data type.  All one has to do add the CompareValidator tag to your markup,  set the properties and ASP.Net does the rest.  But don’t expect it to handle a dollar sign: use a regular expression for that!


Read Full Post »

Pre-scoring Candidates for String Matching

Keywords: Levenshtein, String Matching, Optimization


In many service oriented businesses, the problem comes up to search your customers for names which are published on a government watchlist. The input names on either list may contain typographical errors, so a fault insensitive matching algorithm must be run on each name pair. A model algorithm to consider for this is the Levenshtein string matching algorithm. Levenshtein is a nice algorithm to consider because it is well behaved, easy to understand and work with, and it is unbiased in the sense that it is not parametric and tuned for “English” sounding names only. The Levenshtein algorithm is (somewhat whimsically) explained in another posting here with references.

The time to compare all possible combinations of names varies linearly with the length of each input list, quadratically if they are both growing.  Typical string matching algorithms that are insensitive to typographical errors run more slowly than linear time.  Levenshtein is itself quadratic in the length of the strings it is comparing, so it makes sense to attempt to find a fast, linear-time pre-scoring algorithm that enables fast rejection of as many comparisons as possible beforehand. Furthermore, and perhaps as importantly, it is desirable to find a pre-scoring strategy that is separable over two strings being matched so that the pre-score can be calculated “offline” and stored with each string for quick comparison later.


Read Full Post »

String Matching and Zaxxon

Keywords: Levenshtein, Wagner-Fischer, Zaxxon

It comes frequently in the service sector to check your customer names against some list provided by regulatory agencies, and the checking has to be tolerant against slightly mistyped names. So for example if “Hugo Chavez” is on the list, and “Huge Shavez” is in your list of customers, you might want to at least flag it as something to investigate further and see if it is a real match. One of the classic methods for evaluating near matches for words and names is the Levenshtein algorithm, or its closely related cousin Wagner-Fischer. But how does it work? And what does it have to do with Zaxxon?

Read Full Post »