A Programmer's Analysis of Boggle

In the era of modern tabletop games such as Apples to Apples, Dixit, Sushi Go, Hive, Zombie Dice, and Tokaido (all great games), the classics are often left behind. While many of these games deserve to be forgotten (Monopoly, Jenga, Risk, Life, and Snakes and Ladders; just to name a few), the venerable Boggle still reigns as one of the few great word games. Boggle has a lot to offer: it is a fast paced game that scales well to many players, everyone plays at the same time, winning requires skill (pattern recognition and a decent vocabulary) and strategy (trying to find words that other players aren't likely to spot) rather than luck, and it has a high replay value (every game is different). It is also easy to level the playing field for younger players, e.g. by counting their words even if found by other players or reducing the value of longer words.

Boggle is interesting from a programmer's perspective as well. While crafting an algorithm to efficiently find all of the words in a Boggle game is pretty straight forward, answering questions such as:

• What is the average number of words/points in a game and how does this differ between different  sets of dice?
• What percentage of total points do 3-letter words constitute? 4-letter words? Etc.
• How can we determine whether a given arrangement constitutes a valid board for a particular game?
• How many words in a given dictionary cannot be spelled using any possible arrangement of the provided dice?
• What is the highest scoring Boggle board?

are more challenging and require the use of non-trivial algorithms and data structures. A couple years ago, I wrote a program explore these questions (and others) called Word Game Solver (WGS for short) and documented the results which are presented below. While the details of the program itself will not be the focus here, I will provide the commands used when applicable so that others can reproduce/expand on the results presented and will also touch on the algorithms employed.  Comprehensive pdf documentation is provided with the program (available on GitHub) for those who are interested in the full scope of the functionality provided.

C11 - Generic Selections

C99 introduced type-generic macros defined in the new tgmath.h header. These are macros that expand to the appropriate function based on the type of the provided argument. For example, their are 6 different arc cosine functions: 3 for the different real floating point types and 3 for the different complex floating point types. If you #include <tgmath.h>, a macro with the name acos is exposed which will expand to a call to one of the 6 functions based on the argument type.

The type-generic mechanism employed to make this work was not exposed or made available to the programmer but was instead left up to implementation magic. C11 introduces the generic selection expression which provides a mechanism to make compile-time choices based on type allowing type-generic macros to be created using standard C constructs.

In this post I will introduce and explore some of the applications of the new generic selection.

C11 - Static Assertions

C11 provides the new _Static_assert declaration which allows the use of compile-time assertions. This post describes this new feature and the practical benefits.

Incremental Linting with FlexeLint

Tools like FlexeLint are great for finding and preventing bugs and the bad practices that are often associated with them and little argument can be made for not using a good static analysis tool from the inception of a new project.  Many times however, it is desired to start reaping the benefits of such a tool with an existing code base.  The initial scan of even a carefully configured FlexeLint installation can generate a daunting number of messages that simply are not practical to address before continuing development.  Because of this, such tools are often not used on established code bases.  Being able to establish a baseline snapshot of a code base and receive diagnostics only for new or changed code would make using FlexeLint significantly more manageable for such projects and allow previously existing issues to be addressed in a more practical timeline.  Such a method can also be used to easily track issues introduced between different versions.

This post discusses a method to run FlexeLint so as to receive messages only on code that differs from a specific baseline.  The examples use FlexeLint but the ideas are relatively simple and can be easily modified to work with other tools as well.

Suppressing messages for particular files in FlexeLint

A commonly asked question regarding Flexelint is how one can suppress some or all messages for a particular file.  Although there isn't an individual option to accompish this, like there is for suppressing messages for specific symbols, types, etc., there are several ways to achieve the same effect.

How Well Do You Know C?

Think you have mastered the ins and outs of the C language? Test your knowledge of the nuances of C by trying to determine what is printed by each of the following programs. All code is C99 and exhibits well-defined behavior. Answers and discussion follow.

FlexeLint: A Modern Static Analyzer for C and C++

Static analysis is a powerful technique for quickly finding programming defects in the earliest stages of development and is especially useful for statically typed languages like C and C++. In this post I will discuss FlexeLint, a mature static analysis tool for C and C++ from Gimpel Software. Plenty of examples are provided to demonstrate many of the features and types of issues the tool can detect. Although it is impossible to cover everything about a tool as featureful as FlexeLint in a single post, I will attempt to provide firm understanding of what the tool is capable of and how it can improve the quality of your code. If you are a serious C or C++ programmer, you will greatly benefit by using static analysis and FlexeLint is one of the best, and least expensive, tools out there today.

Cooperative Limiting of Concurrent Process Instances

It is a common desire to limit the number of instances of a specific program for one of several reasons including resource management, ensuring programs not meant to handle multiple concurrent instances are run only once, or managing license restrictions. In this post I will detail a method for managing the number of concurrent instances of a process or group of processes in a manner that does not require alteration of the programs being limited and avoids a number of issues with existing methods that usually do.