garethrees.org

Stack nomenclature
2018-03-12

What’s wrong with the names ‘top’ and ‘bottom’ for the two ends of a stack?

Big-O proofs
2018-03-11

Is there any benefit to be gained from learning to write big-O proofs in your analysis of algorithms class?

The stack of iterators pattern
2016-09-28

A design pattern for implementing depth-first search in Python using a stack of iterators instead of recursion.

Visual C/C++ incremental linker bug
2016-09-27

The Microsoft Visual C/C++ incremental linker sometimes fails to update the executable with the updated object code.

Exact cover III
2016-06-04

Using gadgets to translate combinatorial problems into exact cover instances, and how to avoid the gadgets using multiset covers.

Round trip
2015-12-15

How I combined a parser and a serializer to achieve an elaborate no-op.

Plan to throw one away
2015-12-14

How I had to write a JavaScript engine in two weeks.

Exact cover II
2015-11-17

Solving and setting Sudoku problems in Python using an exact cover solver.

Exact cover I
2015-11-09

Solving the exact cover problem in Python using ‘Algorithm X’.

A performance regression
2015-08-09

A debugging story.

Emacs/Perforce integration: a retrospective
2015-08-07

A look back at the first couple of years of maintaining the Emacs/Perforce integration.

The ping that wouldn’t die
2015-08-07

A debugging story.

Completion colours
2015-02-11

“At this point, if you are used to the way strings work in most programming languages, you ought to be asking yourself, how does this work?

Completion annotations
2015-02-09

“Interactive completion works poorly in the case of changelists and jobs, because all you get when you type TAB is a list of opaque identifiers that give you no help in choosing the item you want.”

Five whys
2015-02-07

“When confronted with a problem, have you ever stopped and asked why five times? It is difficult to do even though it sounds easy.”

The Bug
2015-01-18

“It is stressful to know that something is wrong in your code, but not to know what it is or how to find it, and to have it hanging over your head day after day as you fail to make progress towards solving it. This nightmare scenario is the driver behind Ellen Ullman’s 2003 novel The Bug.”

Software inspection and the Heartbleed bug
2014-05-08

Systematic use of software inspection could have fixed the Heartbleed bug without having to find it first.

Password purgatory
2014-04-15

I’m seeing what it’s like to try to follow “best practices” for password management, but I find myself wondering if these practices are really suitable for human beings?

Drawing square triangulations
2013-08-09

Drawing the triangulations of an oriented n×n square using only lines joining the 4n integer points around the edge of the square.

Shrinking SVG
2013-08-02

Generating smaller Scalable Vector Graphics (SVG) from Python.

Scalable vector triangulations
2013-06-15

Generating Scalable Vector Graphics (SVG) from Python.

Square triangulations
2013-06-14

Computing the number of ways to triangulate an oriented n×n square using only lines joining the 4n integer points around the edge of the square.

User options considered harmful
2013-06-13

The desire to add a user option often indicates that you have skimped on a important piece of usability work and are trying to put off doing it.

Software archaeology and technical debt
2013-06-12

It doesn’t take long to reach a ‘mature programming environment’ in which complexity is overwhelming and change is expensive and error-prone. We’re all programmer–archaeologists now.

The tabular method
2013-06-11

Dynamic programming is an important technique for writing combinatorial algorithms. But the name sucks!

Circular logic
2013-05-15

Truth tables, graph colourings and a surprising sequence in Project Euler problem 209.

Language-oriented programming
2013-05-09

“Languages are not just for describing algorithms to computers: they are for communication with other people.”

Emacs/Perforce integration: back from the dead
2013-05-01

I’ve forked the abandoned Emacs/Perforce integration, and started fixing it. In particular, it no longer hangs Emacs when it can’t connect to the Perforce server.

Bogus foreign keys in Django
2013-03-24

Handling bogus foreign keys in legacy databases in the Django web development framework.

The last lousy bug
2013-01-06

A debugging war story: “Bug 142 was especially mysterious because it happened after the program quit running…”

Method combinations in Python
2012-03-22

Using Python’s class introspection to implement a non-standard method combination.

Python has no precedence grammar
2011-07-17

A surprising fact about Python: it cannot be expressed by an operator precedence grammar.

Theo Jansen’s Strandbeest
2011-07-04

Theo Jansen is a Dutch artist who, for the last couple of decades, has been building increasingly elaborate kinetic sculptures that he calls strandbeesten (beach-animals).

Turning circles
2011-07-02

Using vector geometry to compute a turning circle. Plus a Javascript/canvas demo.

iOS location tracking
2011-04-21

The hidden location-tracking feature in iOS 4, with some maps to illustrate the accuracy of the recording.

Encapsulation is not always right
2010-12-09

In object-oriented programming, encapsulation is sometimes a bad idea, and motion planning and collision are areas where this is particularly likely to be the case.

Using the Autodesk FBX Python module on 64-bit Macs
2010-12-08

A bug report (mostly so that other people who encounter the problem can search for and find the workaround).

Indentation advice
2010-11-16

Supposing, just supposing, that you actually wanted to make your dots line up vertically in Emacs, how would you go about it?

History of level 24
2010-06-17

A finished game, with smooth gameplay and polished graphics, gives little evidence of the many twists and turns along the path of development. Here, in twenty-four screenshots of level 24, I show some of the trials, mistakes, and modest triumphs from the development of Floe.

Using html5lib to resolve relative URLs
2009-10-09

Python code for translating relative URLs in HTML source into absolute URLs suitable for syndication.

Emacs 23
2009-08-19

Emacs 23.1 was released on 2009-07-29. In this review, I describe some interesting and useful features of this release, and give some historical background to multilingual support in Emacs.

Colliding balls
2009-02-17

Several approaches to implementing a system of colliding balls, ranging from quick-and-rough to painstaking-and-slow.

Validating XHTML
2009-02-07

A program to allow you to run your XHTML document through the W3C validator and step through the errors and warnings conveniently in Emacs, and a brief discussion of why someone might want to do this.

Apple Mail crash: “bad external relocation length”
2009-02-02

A serious crash in the Apple Mail application, with some analysis and a possible remedy. “It’s a bit worrying that the entire world can make my mail application crash just by sending me some junk mail.

User interface asynchrony
2009-01-31

Implementing a match-making user interface for an ad-hoc wireless networked video game shows us that a user interface needs to be able to run asynchronously with respect to the implementation.

Fourteen years of e-mail
2008-08-11

Counting and graphing e-mails. With a digression on non-standards-conformant mail user agents and how to use Perl to parse their non-conformant Date headers.

How deep is your build pipeline?
2008-08-09

Discussion of video game build pipelines and the development difficulties that they entail.

Constant, qualified, and less attemptable
2008-08-06

The const type qualifier in the C programming language, and the consequent impossibility of implementing some common operations in a type-safe way.

Make my day
2008-06-24

The trouble with the build tool make is that because it uses file modification dates to determine whether a dependency has changed, it often rebuilds targets unnecessarily.

Multi-way mortgage calculator
2008-03-24

There are many thousands of mortgage calculators on the web that compute the monthly payments based on the capital sum, interest rate, and duration. But this one lets you compute any of these four values based on the other three.

Smallest possible transparent PNG
2007-11-15

A detailed look at the encoding of bitmap images in the PNG file format, leading up to the discovery of the smallest possible transparent PNG, only 67 bytes long.

Smart quotes in Emacs 22
2007-10-17

Smart quotes mode, a minor mode for Emacs 22 that makes it convenient to type ‘smart’ “quotes”.

Zendoku puzzle generation
2007-06-10

The technical challenges involved in implementing a sudoku puzzle generation algorithm on a handheld video game console, and how the developers at Zoonami solved them in the production of Zendoku for the Nintendo DS and Sony PSP.

The Python Challenge
2007-05-07

The Python Challenge is a website of puzzles compiled by Nadav Samet. The puzzles are a mixture of riddles, codes, and programming challenges, with the Python language being a recommended tool. Here are some of my notes and solutions.

Relational macros
2007-04-24

A C programming language technique for embedding relations (tables of data) into programs in a way which is easy to check, safe to update, and requires no tools other than the C preprocessor.

PSP loading times
2007-01-18

Why video games on the Sony PlayStation Portable take so long to load, and what game developers can do to reduce loading times.

Excel
2006-04-25

It’s common and convenient to represent relational databases in the form of spreadsheets, especially using Microsoft Excel. But it’s surpisingly hard to carry out relatively simple database operations on such spreadsheets. This article explains how to implement simple selects and joins as Excel formulae.

Type inference for Python
2002-02-26

A sketch of a type system for the typeless programming language Python. The system would allow a limited form of type inference that would detect some type errors at compile time.

The errors of Christminster
2001-12-15

A study of the errors found and fixed during the development, testing and release history of the adventure Christminster, together with a suggested categorization of defects in adventure games.

Statement coverage for Python
2001-12-04

A tool to support statement coverage testing for Python. It accumulates coverage data over many runs, generates coverage reports, and annotates Python source showing which statements have been covered.

Statement coverage for Python: design and analysis
2001-12-04

Lists the requirements for a statement coverage tool for Python, describes some issues in design and implementation, and compares coverage.py with other statement coverage implementations.

Can we ship yet? Using Perforce fixes to measure product quality
2001-09-01

How to use Perforce to efficiently measure the quality of a product in a software development environment where there are many branches, customers, and product versions. Presented at the Perforce User Conference 2001.