This is Part 3 of an N-part series.

- The Josephus Problem: Part 1: The Problem
- The Josephus Problem: Part 2: Two Examples
- The Josephus Problem: Part 3: Solving the Double Step Case

## Solving the Double Step Case

The Josephus Problem for a …

This is Part 3 of an N-part series.

- The Josephus Problem: Part 1: The Problem
- The Josephus Problem: Part 2: Two Examples
- The Josephus Problem: Part 3: Solving the Double Step Case

Table of Contents

The Josephus Problem for a …

This is Part 2 of an N-part series.

- The Josephus Problem: Part 1: The Problem
- The Josephus Problem: Part 2: Two Examples
- The Josephus Problem: Part 3: Solving the Double Step Case

Table of Contents

In this blog post we'll walk through two examples of …

This is Part 1 of an N-part series.

- The Josephus Problem: Part 1: The Problem
- The Josephus Problem: Part 2: Two Examples
- The Josephus Problem: Part 3: Solving the Double Step Case

Table of Contents

The following problem, Cat and Mice, is Puzzle 88 in Boris Kordemsky's The Moscow Puzzles.

Purrer has decided to take a nap. He dreams …

Table of Contents

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 …

Table of Contents

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.

This post …

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 …

Posted in Computer Science

*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?*

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?*

*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?*

- About the Five Letter Words
- The Usefulness of Five Letter Words
- Warm-Up Exercises
- Get Words Function
- Euclidean Distance
- Mo Words, Mo Problems
- References

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.

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 …
```

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
- Solving the Reflection Problem
- Procedure
- References

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 …

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

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 …

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

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 …

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.

In the Checkers problem …

Table of Contents:

Recursion, particularly recursive backtracking, is far and away the most challenging topic I cover when I teach the CSE 143 (Java Programming II) course at South Seattle College. Teaching the concept of recursion, on its own, is challenging: the concept is a hard one to encounter in everyday life, making it unfamiliar, and that creates a lot of friction when students try to understand how to apply recursion.

The …

- Background
- The Z-Machine: Setup
- The Z-Machine: Instructions
- Simple Example: Loop
- Implementing an Addition Operator on the Z-Machine
- 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

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 …

- Background
- N Queens Revisited
- Perl Solution
- Python Solution
- Python vs. Perl: Walltime vs. Number of Queens
- Perl Profiling and Results
- Python Profiling
- Python Profiling Results
- Comparing Python to Perl
- Python vs. Perl: Walltime vs. Number of Solutions Tested
- The Winner: Perl for Small Problems, Python for Big Ones
- Sources

Revisiting the N queens problem, this time implementing the solution in Python.

Verb-oriented solution, functional, and based on Perl solution

More fair comparison - both are interpreted languages, not compiled languages

Compare Python and Perl, ease of implementation, speed, flexibility

As a recap from the …

- Background: Huh?
- N Queens Problem
- N Queens Solution
- Head to Head: Walltime vs. Number of Queens
- Perl Profiling
- Perl Profiling Results
- Java Profiling
- Java Profiling Results
- Head to Head: Walltime vs. Number of Solutions Tested
- Apples and Oranges
- Sources

In this post, we describe an implementation of the N Queens Problem, which is a puzzle related to optimization, combinatorics, and recursive backtracking. The puzzle asks: how many configurations are there for placing 8 queens on a chessboard such that no queen can attack any othr queen?

This problem was implemented in Perl …