Feeds:
Posts
Comments

I’ve got a new article up at The Code Project about how the internal keyword in C# can be used safely while preserving encapsulation. In a nutshell, it is about using internal interfaces instead of giving internal access directly to properties or fields, and how this can help maintain strict encapsulation while nevertheless granting special access to service layers. Give it a read and don’t forget to vote!

Advertisements

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.
Continue Reading »

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!

Continue Reading »

Keywords: Levenshtein, String Matching, Optimization

Introduction

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.

Continue Reading »

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?
Continue Reading »

Goodbye Bluetooth!

I’ve worked on many software projects over the years, and the trajectory that most software development efforts takes is something like this: You gather initial requirements from stakeholders and users, make an initial release, and gradually increase the feature set and improve upon existing features. Not so with Bluetooth. In the span of about six years, Bluetooth went from “awesome” to “almost useless” for me.
Continue Reading »

Keywords: Humor, Extreme Frustration

Within an Active Directory domain, NTFS has a very flexible and extensive system for authorization of user access to files. When coupled with a network share, there is one additional layer of security to pass. So in order to for a user to have permission to access an NTFS file through a network share, there are four conditions that must be met. The following assumes that the user has been authenticated within a domain.
Continue Reading »