Overview

In this post we cover a strategy for managing configurations for programs using a Singleton pattern to create a static Config class.

This allows the user to create an instance of the Config class, pointing it to a specific config file, which it loads into memory.

The Config class provides several static methods for accessing configuration options from the config file. Here's an example of its usage:

Config('/path/to/config.json')

if Config.get_foo() == "bar":
    do …

Confuse-A-Constructor

Today, we are going to confuse a constructor.

What is the constructor?

One of the first concepts encountered in object-oriented programming is that of the constructor, the method that …

Overview

This post is a summary of a useful Python programming pattern called the Registry pattern.

The Registry pattern is a way of keeping track of all subclasses of a given class.

More details about this pattern are available at https://github.com/faif/python-patterns.

What is the Registry Pattern …

About the Five-Letter Words

In Volume 4 Fascicle 0 of Donald Knuth's Art of Computer Programming, Knuth introduces a tool for exploring concepts in graph theory: the five-letter words. This is a collection …

About the Five-Letter Words

In Volume 4, Facsimile 0 of Donald Knuth's Art of Computer Programming, in which Knuth covers graph theory, he introduces a list of five-letter words as part of a data set useful in exploring graph theory and graph algorithms.

The list of words is part of the Stanford Graph Base, a set of data sets that are useful for studying graph theory and networks.

See Five Letter Words on the charlesreid1.com wiki for details.

Different by 1, Revisited

This post …

Table of Contents

• What's your favorite PEP?
• PEP 0
• PEP 8
• PEP 20
• PEP 3099
  • Addendum: 2 to 3 Changes
• PEP 202
• All the PEPs on Github

What's your favorite PEP?

PEPs, or Python Enhancement Proposals, are documents in which features, additions, or general ideas are proposed as additions to the core Python language.

As a Python user, we believe it's important to ask questions like this.

Picking a "favorite PEP" is not just about having a ready and clever answer to a question you might expect in a technical interview; the PEP documents really are important, and really do …

Table of Contents

• Starting example
• What needs to be changed
• Formatting the data
  • MediaWiki edits
  • Git commits
• Creating the color map
• How the calendar code works
• Final result

Starting example

Let's begin with a D3 example. Mike Bostock provided a Calendar View block illustrating how to draw a very interesting visualization of large amounts of data over time:

You might recognize this type of graph from Github, whose activity graph shows the same visualization.

The data shown in this example consists of several years of stock market data. It is a simple but very large data set, with each data …

Table of Contents

• Overview: Problem 172
• Background
  • Multiset Permutations
  • A Simple Problem (And Solution)
  • A Slightly More Complicated Problem
• Algorithm
  • Ignoring Numbers Starting with 0
• Code
  • Test Cases
  • Recursion
  • Pseudocode
  • Python Code
• Final Answer

Overview: Problem 172

How many 18-digit numbers \(n\) (without leading zeros) are there such that no digit occurs more than three times in \(n\)?

Link to Project Euler Problem 172

Background

Project Euler Problem 172 is your classic Project Euler problem: short, simple, and overwhelmingly complicated.

To nail this one, it's important to start simple - very simple. What I'll do is walk through the process of …

Generating Permutations

In today's post we're going to discuss the generation of permutations.

Often, in combinatorics problems, we are interested in how many different instances or configurations of a particular thing we can have (what we'll call "enumeration" or "counting"). However, that is different from wanting to actually see all of those configurations. Indeed, if we are counting something with an astronomical number of configurations, we don't want to try to list all of them.

However, as usual, Donald Knuth, who covers the topic of permutation generation in Volume 4A of his classic work, The Art of Computer Programming, uncovers …

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

Table of Contents

• Introduction
• A Simple Manual Exmaple
• Pseudocode
• Python Code
• Output and Timing

Introduction

The letter/word coverage problem, as presented by Donald Knuth in Volume 4, Facicle 0 of his masterpiece Art of …

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

Table of Contents

• Introduction
• Five-Letter Words with k Distinct Letters
  • Examining a Variation
• Lexicographic Ordering of Letters
  • Five-Letter Words with Lexicographically Ordered Letters
  • Five-Letter Words with Lexicographically Reversed Letters
• Finding Palindromes
  • Palindromes
  • Palindrome Pairs
  • Near …

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

Table of Contents

• About the Five Letter Words
• The Usefulness of Five Letter Words
• Warm-Up Exercises
• Get Words Function
• Euclidean Distance
  • Euclidean Distance Code
  • Examples
  • Different-by-N Code
• Mo Words, Mo Problems
• References

About the Five-Letter …

Table of Contents

• Overview: The Problem
• Polyominoes
  • Castle Rules for Polynominoes
• Don't Generate - Enumerate!

Overview: The Problem

In an earlier post, I mentioned my efforts on Project Euler problems and the wide variety of problems there that can offer some profound mathematical insights.

Given that the first post covered Project Euler problem 1, I thought it would be nice if the next problem cranked up the difficulty factor by an order of magnitude. Project Euler Problem 502 is a very hairy combinatorics problem that required me to learn about a wide variety of combinatorial enumeration techniques.

Let's start with the …

Table of Contents

• Overview: The Problem
• Why This Problem?
• Going Deeper: An Example

Overview: The Problem

Project Euler is a website that provides mathematically-oriented programming problems. There are many (over 500) and they are a rich source of profound mathematical insights.

I have been considering a writeup that goes deep into a particular problem, so why not do it with problem 1?

Problem 1 of Project Euler asks:

Find the sum of all the multiples of 3 or 5 below 1000.

It is a pretty simple task - one of the first things covered in a decent programming course is the …

The Lattice Paths Problem

I first came across the lattice paths problem in Project Euler problem 15. The question described a 2x2 square lattice, and illustrated the 6 ways of navigating from the top left corner to the bottom right corner by taking the minimum number of steps - 2 right …

Table of Contents

• Number Systems and Representations
• Continued Fraction Representations
• Convergents of Continued Fractions
• Example: Continued Fraction Coefficients of \(\sqrt{14}\)
• Example: Convergents of \(\sqrt{14}\)
• Approximating Square Roots

Continued Fractions

Let's start part 2 of our discussion of computing square roots by talking about continued fractions. When we first learn mathematics, we learn to count in the base 10 system: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We can construct representations of all of the integers using these 10 digits, by arranging them in a different order. So, for example, saying 125 is equivalent to saying …

Table of Contents

• Newton's Method for Finding Roots of Equations

• Newton's Method for Finding Square Roots

• Newton's Method for Finding Square Roots: Program

• Accuracy

• Speed

• Next Steps

• References

Newton's Method for Finding Roots of Equations

Suppose we have a function \(f(x)\) and we want to compute values of \(x\) for which \(f(x)=0\). These values of \(x\) are called the roots of \(f(x)\).

We can compute the roots using Newton's Method, which utilizes the derivative of the function to iteratively compute the roots of the function.

Newton's method begins with an initial guess. It evaluates the derivative …

Table of Contents

This is the third in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post deals with the code to solve the Hilbert Sort problem.

• Pseudocode

• Code

  • Utility Classes
  • Recursive Sort Function
  • Main Method

• References

Hilbert Sort: Pseudocode

From our prior post, here is the psudocode for our Hilbert Sort function:

define hilbert_sort( unsorted queue, square dimension ):
    create southwest queue
    create northwest queue
    create northeast queue
    create southeast queue
    for each point:
        if in southwest:
            create new point using X -> Y, Y -> X
            add to southwest queue
        if in …

Table of Contents

This is the second in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post solves the problem.

• Hilbert Sort Problem
• Space Is The Place
• The Reflections
  • Reflected Quadrants
  • Scaling
  • Reflection
• Solving the Reflection Problem
• Procedure
• References

Hilbert Sort Problem

In the prior post, we covered the Hilbert Sort problem, but we state it once more succinctly here before detailing a solution to the problem.

The Hilbert Sort problem asks the following: given a set of labeled \((x,y)\) points, how can we sort the points according to the order …

Table of Contents

This is the first in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post sets up the problem.

• Hilbert Sort: Motivation
• Hilbert, Peano, and Space-Filling Curves
• Constructing a Hilbert Curve
• Performing a Hilbert Sort
• Problem Statement
• References

Hilbert Sort: Motivation

In the next few series of posts, we will cover the Hilbert Sort problem, how it works, and how to implement it.
However, before we describe the problem further, let's start with some motivation for solving this problem.

Suppose we're dealing with a very large number of independent objects …

Table of Contents

• Problem Description
• Solution Approach
• Algorithm
• Pseudocode
• Using an Object-Oriented Approach
• Code
• References

Problem Description

Comedian John Cleese, in his memoir So Anyway..., described the social classes of his mother and father as "upper-uper-lower-middle class" and "middle-middle-middle-lower-middle class", respectively. Write a program that will sort individuals based on a labeling of their social standing by class.

The three main classes are upper, middle, and lower. Classes progress hierarchically from right to left. For example, lower-upper would come before lower-lower. There is also ordering within a class, so upper-upper is a higher class than middle-upper.

Once you have reached …

Table of Contents

• The Problem
  • Problem Description: Checkers
  • Input File
  • Output
• The Solution
  • Keep It Simple
  • Solution Analysis: Parity
  • Solution Analysis: Graphs and Euler Tours
  • Solution Algorithm
  • Solution Pseudocode
  • Solution Code
• References

The Problem

This is a programming challenge that was assigned to some of my CSE 143 students as a final project for their class.

The origin of this problem was the Association of Computing Machinery (ACM)'s International Collegiate Programming Competition (ICPC), in particular the Pacific Northwest Regional Competition, Division 1 challenges from 2015.

Link to Pacific NW ACM ICPC page.

Problem Description: Checkers

In the Checkers problem …

• The Traveling Schoolteacher Problem
• The Mathematical Model
• The Pseudocode
• The Java Code
  • TSTP Class Fields and Methods
  • Explore: Base Case
  • Explore: Recursive Case
• Example Graphs
• Results
  • Walltime vs Number of Nodes
• Conclusion
• References

The Traveling Schoolteacher Problem

The Traveling Schoolteacher Problem (TSTP) is a variation on the Traveling Salesperson Problem (TSP).

The Traveling Schoolteacher Problem supposes a schoolteacher that is traveling from school to school in order to give lessons at different schools. Being a poor schoolteacher, they are only able to afford an older car that gets bad mileage and has a small gas tank.

After visiting each school …

Table of Contents

• Background
• The Z-Machine: Setup
• The Z-Machine: Instructions
• Simple Example: Loop
• Implementing an Addition Operator on the Z-Machine
  • The Solution Approach (The Maths)
  • Solution 1: Positive Integers Only
  • Solution 2: Dealing with Zeros
• Implementing a Decrement Operator on the Z-Machine
• Implementing a Less Than Operator on the Z-Machine
• Who Cares? (Or, How To Build A Computer)
• Sources

Background

Recently I discovered the wonderful blog of John Graham-Cumming. One of hist posts, from 2013, details a question that he had to answer for the Oxford University Department of Computer Science's "interviews" (which, I believe, are a kind of final …

• Before We Begin: The Code
• Timing Scripts
• Before You Time: Developing Your Algorithm
• Beginning Your Timing Journey
• Statistical Timing, a.k.a., If You Give A Mouse A Cookie
• Hierarchical Timing Strategy
• Single Problem/Program/Binary
• Multiple Problem/Program/Binary
• Statistical Averaging
• Results
• Summary

Before We Begin: The Code

Note that all of the code discussed/shown in this post is available from the traveling salesperson problem repository on git.charlesreid1.com. The guava/ directory contains the guava solution to the traveling salesperson problem, along with the timing scripts discussed below, and several example output files.

Introduction

Timing a piece …

• Intro
• The Graphs We Are Solving
  • Visualizations of Graphs
• Guava TSP Solution
  • Timing the TSP Solution
• Improving the Guava TSP Solution
  • The Flaw
  • Fixing the Flaw
  • The Pessimist Algorithm
• Timing Results
• Future Work

Intro

In a prior blog post we introduced you to the traveling salesperson problem (TSP), which involves finding the shortest path through every city in a group of cities connected by a network of roads. Using Google Guava, we have implemented a solution to the TSP in Java.

Our philosophy toward timing, profiling, and optimization is that it is always best to work from data - and timing …

Table of Contents

• Background: Traveling Salesperson Problem (TSP)
• Graphs
  • Number of Edges
• Solution: Recursive Backtracking
• Solving the TSP with Java and Guava
  • Basics of Guava
  • Guava Graphs
  • Guava Mutable vs Immutable
  • Importing Guava
  • TSP Class
  • Node Class
  • Edge Class
• TSP Constructor and Building the Graph
  • Constructor
  • Build Graph Method
• Solving and Exploring with Recursive Backtracking
  • Solve Method
  • Explore (Backtrack) Method
• Next Steps: Timing and Profiling
• Sources

Background: Traveling Salesperson Problem (TSP)

The traveling salesperson problem, or TSP, is a classic programming problem and an important one in computer science, and applications in operations research and optimization.

The idea is that …