This is Part 3 of an N-part series.
The Josephus Problem for a …
This is Part 2 of an N-part series.
In this blog post we'll walk through two examples of …
This is Part 1 of an N-part series.
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 …
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 …
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?
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.
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.
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 …
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 …
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 …
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 …
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 …