How to Count Things¶

Sesame Street teaches us to easily count up to ten using our fingers. A computer doesn't have fingers, but it too can use brute force, enumerating things one by one, to easily count up to a billion or so.

So in that sense, a billion is a small number. For really big numbers, like 10¹⁰⁰, we need a better strategy: counting by calculating the number of things rather than enumerating them. This notebook describes some strategies for counting by calculating.

Problem 1: Counting Sub-cubes¶

We'll start with a really simple counting problem:

Given a cube with *n* sub-cubes on a side, how many total sub-cubes are there?

Here are two example cubes:

n = 3	n = 9

For the n = 3 cube, we could use the enumeration strategy, pointing to each sub-cube with our finger and counting 1, 2, 3, ... 27. That wouldn't work as well for the n = 9 cube, and it would be completely infeasible for an n = 1000 cube. How can we count with a computer?

First let's get some Python preliminaries out of the way: imports, and three utility functions:

• cat concatenates strings into one big string
• quantify (from the itertools module recipes) counts how many things a predicate is true for.
• totalcount totals up all the values in a Counter.

Here is an enumeration strategy and a calculation strategy for sub-cube counting:

The calculation strategy is much faster:

Problem 2: Counting Student Records (Late/Absent/Present)¶

A more difficult problem:

Students at a school must check in with the guidance counselor if they have two total absences, or three consecutive late days. Each student's attendance record consists of a string of 'A' for absent, 'L' for late, or 'P' for present. For example: "LAPLPA" requires a meeting (because there are two absences), and "LAPLPL" is OK (there are three late days, but they are not consecutive). How many attendance records of length n are OK?

The enumeration strategy says: define what it means for a record to be ok, define all the strings of length n, and count how many of them are ok:

This looks good, but for large values of n I will need an efficient calculation strategy. Here's how I think about it:

• I can't enumerate all the strings; there are too many of them.
• Instead, I want to divide and conquer: divide the problem up into simpler subproblems, solve the subproblems, and combine them. A good way to divide this problem is to solve the case for n by first solving the case for n-1.
• With the enumeration strategy, going from n-1 to n multiplies the amount of work by 3 (because you have to consider any of three letters tacked on to the end of every possible record).
• With the right divide and conquer strategy, we can get from n-1 to n with a constant amount of work. So the total complexity can be O(n) instead of O(3ⁿ).
• (This divide and conquer strategy is sometimes called dynamic programming, although some writers reserve the term dynamic programming for algorithms that explicitly store partial results in a table.)
• How do I get from n-1 to n? I will keep track of a summary of all the ok strings of length n-1, and use that to quickly (in constant time) compute a summary of the ok strings of length n.
• What is in the summary? A list of all ok strings is too much. A simple count of the number of ok strings is not enough. Instead, I need several different counts, for several different classes of strings. Each class is defined by the number of 'A' characters in the string, and the number of consecutive 'L' characters at the end of the string (because these are the two things that determine whether the string will be ok or not ok when I add a letter to the end). So the summary can be represented as a Counter of the form {(A, L): count, ...}.

For n = 0, the summary is {(0, 0): 1}, because there is one string of length zero, the empty string, which has no 'A' nor 'L' in it. From there we can proceed in a "bottom-up" fashion to compute the total number of ok strings for the next value of n, using the function next_summary, which says that we can add an 'A' to any string that doesn't already have one; we can add an L to any string that doesn't already end in 2 'L's; and we can add a 'P' to any string.

Here's an implementation of calculate_ok, and a demonstration that it gets the same results as enumerate_ok:

But we can go way beyond what we could do with enumerate_ok:

Alternative: Abstraction with iterate¶

This pattern of repeatedly calling next_summary n times will be common in this notebook; we can encapsulate it in a function called iterate (after the Haskell function of that name) allowing us to implement a version of calculate_ok in one line:

Alternative: Working Down¶

As a third alternative, instead of working up from 0 to n we can work down from n to 0 (although we may run up against Python's recursion limit):

A comparison:

There are over 10¹³⁴ ok strings of length 500, but it only takes a couple milliseconds to count them. Any of the three methods works equally well; use the approach you feel comfortable with.

Problem 3: Counting Strings with Alphabetic First Occurences¶

Here's another problem:

How many strings of length k can be formed such that the first occurrences of each character in the string forms a prefix of the alphabet?

Let's first make sure we understand the problem, because the statement is a bit abstract and tricky. Given a string we have to pick out the first occurrences of characters (letters). For example, for the string "abba", we read left-to-right, recording each time we see a letter for the first time; that gives us "ab" (the subsequent occurrences of 'a' and 'b' don't matter). Is that a prefix of the alphabet, "abcd..."? Yes it is.

Here are some test cases—pairs of strings along with their first occurrences—labelled with True for valid strings and False for invalid:

Now to implement the code that can run these tests. Since k could be arbitrarily large, I will by default assume an alphabet consisting of the non-negative integers, not the letters. Here are the key concepts:

I'll test this code on the examples I showed above by defining the function alpha_test:

Now I can count the number of valid strings by enumerating all possible strings in the alphabet and checking each one with is_alpha_firsts. The complexity of this algorithm is $O(k^{k+1})$, because there are $k^k$ strings, and to validate a string requires looking at all $k$ characters:

Now let's think about a calculation strategy that would be faster than the enumeration strategy. As with previous problems, I need a summary of the relevant information for strings of length k, to help me calculate the relevant information for length k+1. I know that if I have a valid string of length k with m distinct characters in it, then I can extend it by one character in m ways by repeating any of those m characters, or I can introduce a first occurrence of character number m+1 (but I can do that in just 1 way). I can't validly introduce any other character. So a good summary would be a Counter of {m:count}, and we get this:

That's a big number.

Alternative: Recursion¶

Another way to keep track of the number of valid strings of length k with m distinct characters is with a recursive counting function, which I will call C(k, m). There are three cases:

• C(0, 0) is 1, because the empty string is valid (and contains no distinct characters).
• C(k, m) is 0 when k is negative (because there is no such thing as a negative length string) or less than m (because a string can't contain more distinct characters than its length).
• Otherwise, there are m ways to add an existing letter to each of the strings of length k - 1, and there is one way to add a new letter.

Note that I used lru_cache, to avoid having to re-compute intermediate results.

Now I can define calculate_alpha_firsts2(k) as the sum of C(k, m) over all values of m:

Let's make sure the two calculations gives the same answers as the enumeration, at least for small values of $k$:

Problem 4: Counting Barcodes¶

Consider the barcode pictured below. A valid barcode consists of alternating black and white stripes, where each stripe is either 1, 2, or 3 units wide. The question is: for a box that is n units wide, how many different valid barcodes are there?

We'll represent a barcode as a string, such as 'BBWWWBBW'. Each of the n characters in the string can be either 'B' or 'W', but the string can't have 4 of the same character in a row. We'll start with the familiar enumerate-and-test strategy:

Here's a table of counts for small values of n:

We can see that the table starts out with the powers of two: 1, 2, 4, 8. That makes sense: each of the n positions in the barcode could be either black or white, so that's 2ⁿ barcodes. But barcodes with 4 or more of the same color in a row are invalid, so for n = 4, 'BBBB' and 'WWWW' are invalid, and we get 14 (not 16) valid barcodes. For n = 5 and up, the difference between 2ⁿ and the count of valid barcodes becomes larger.

Now for a fast calculation. As before, we need a representation that summarizes the valid barcodes of length n. The key thing we need to know is how many barcode units of the same color are at the end of the barcode: if it is 1 or 2, then we can add another instance of the same color to the end; no matter what it is we can always add the opposite color (and then the barcode will end in just one unit of the same color).

Verify that enumeration and calculation do the same thing for small values of n:

Demonstrate that we can compute big numbers:

Problem 5: Counting Rectangle Sets¶

This problem is covered in depth in another notebook, so here I present just the part that has to do with counting things:

Say you’re given the following challenge: create a set of five rectangles that have sides of length 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 units. You can combine sides in a variety of ways: for example, you could create a set of rectangles with dimensions 1 x 3, 2 x 4, 5 x 7, 6 x 8 and 9 x 10. How many different sets of five rectangles are possible?

This is a basic combinatorics problem. I will present three methods to calculate the number of sets. If all goes well they will give the same answer. The example set of rectangles given in the problem was

 {1 × 3, 2 × 4, 5 × 7, 6 × 8, 9 × 10}

and in general it would be

 {A × B, C × D, E × F, G × H, I × J}

The question is: how many distinct ways can we assign the integers 1 through 10 to the variables A through J?

Method 1: Count all permutations and divide by repetitions: There are 10 variables to be filled, so there are 10! = 3,628,800 permutations. But if we fill the first two variables with 1 × 3, that is the same rectangle as 3 × 1. So divide 10! by 2⁵ to account for the fact that each of 5 rectangles can appear 2 ways. Similarly, if we fill A and B with 1 × 3, that yields the same set as if we filled C and D with 1 × 3. So divide again by 5! (the number of permutations of 5 things) to account for this. That gives us:

(It is always a relief when this "count and divide" method comes out to a whole number.)

Method 2: Count without repetitions: in each rectangle of the example set the smaller component is listed first, and in each set, the rectangles with smaller first components are listed first. Without loss of generality, let's assume that all rectangle sets must be of this form, and count how many sets there are that respect this ordering. We'll work from left to right. How many choices are there for variable A? Only one! A must always be 1, because we agreed that the smallest number comes first. Then, given A, there are 9 remaining choices for B. For C, given A and B, there is again only one choice: C must be the smallest of the remaining 8 numbers. That leaves 7 choices for D, 5 for F, 3 for H and 1 for J. So:

(It is always a relief when two methods give the same answer.)

Method 3: Write a program to enumerate and check: We'll generate all permutations of sides, and then check which ones are valid rectangle sets: they must have the first element of each pair less than the second (i.e. A < B, C < D, ...) and the pairs must be sorted, which is equivalent to saying their first elements are sorted (i.e. A < C < E < G < I).

(It is a relief that once again we get the same answer.)

Problem 6: Counting Paths on a Grid¶

In a grid, how many paths are there from the upper left to the lower right corner, making only rightward or downward moves?

Here is an example 11 × 6 grid, with three of the possible paths:

 ----------+     |..........     --+........
 ..........|     |..........     ..+-+......
 ..........|     +--+.......     ....+-+....
 ..........|     ...|.......     ......+-+..
 ..........|     ...|.......     ........|..
 ..........|     ...+-------     ........+--

We can use the same three methods as the previous problem:

Method 1: Count all permutations and divide by repetitions: Any path must consist of 10 right and 5 down moves, but they can appear in any order. Arranging 15 things in any order gives 15! = 1,307,674,368,000 possible paths. But that counts all the moves as being distinct, when actually the 10 right moves are indistinguishable, as are the 5 down moves, so we need to divide by the number of ways that they can be arranged. That gives us:

Method 2: Count without repetitions: Another way to look at it is that there will be 15 total moves, so start with all 15 being "right" moves and then choose 5 of them to become "down" moves. So the answer is (15 choose 5), which happens to lead to the same formula we just used:

Method 3: Write a program to count the paths: The function calculate_paths(start, goal) counts the number of paths from the start location to the goal location, where a location is an (x, y) pair of integers. In general, the number of paths to the goal is the number of paths to the location just to the left of the goal, plus the number of paths to the location just above the goal. But there are two special cases: there is only one path (the empty path) when the start is equal to the goal, and there are zero paths when the goal is an illegal destination (one with a negative coordinate).

Even though calculate_paths is slower than the choose calculation, it can still handle reasonably large grids:

Why bother with the recursive function calculate_paths when the choose formula works so well? Good question. One reason is that the two different approaches validate each other by giving the same answer. Another reason is that we can modify calculate_paths to handle things that are hard to do with just the formula. For example, what if we have a grid with some obstacles in it? I'll define a Grid constructor, which adopts the convention that the input is a string of rows, where a '.' character within a row is a passable square, and all other (non-whitespace) characters are impassible barriers. Then calculate_grid_paths finds the number of paths on a grid from start to goal (by default, from upper left to lower right):

We can verify that we get the same answer on the 11 by 6 empty grid:

Here's a grid where there are only two paths around the walls:

If we put a hole in the wall, there should be many paths (but less than 3003 because most of the wall remains):

Here are a couple of bigger examples, courtesy of ascii-art-generator.org:

Can you verify that these last three answers are correct?

Problem 7: Counting Positions in Fischerandom Chess¶

In this variant of chess, the pieces are set up in a random but restricted fashion. The pawns are in their regular positions, and the major white pieces are placed randomly on the first rank, with two restrictions: the bishops must be placed on opposite-color squares, and the king must be placed between the rooks. The black pieces are set up to mirror the white pieces. How many starting positions are there?

We can answer by generating all distinct permutations of the eight pieces and quantifying (counting) the number of permutations that are legal:

[Note: initially I wrote pieces.rindex instead of cat(pieces).rindex, because I forgot that while tuples, lists and strings all have an index method, only strings have rindex. How annoying! In Ruby, both strings and arrays have index and rindex. In Java and Javascript, both strings and lists/arrays have both indexOf and lastIndexOf. What's wrong with Python?]

Problem 8: Counting Change¶

How many ways are there to select coins that add up to a specified amount of money? For example, to make 10 cents with an unlimited number of coins of denomination 10, 5, and 1 cents, there are four ways: {10, 5+5, 5+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1}.

For this problem there is no sense of advanccing from $k$ to $k$+1; instead we will need a recursive breakdown. Here are the cases:

• There is one way to add up to zero cents (with no coins).
• It is not possible to add up to a negative amount (because there are no negative coins).
• It is not possible to add up to a positive amount if you don't have any coin denominations to do it.
• In the general case, you should add up the number of ways you can make change by using one coin of the first denomination, plus the number of ways you can do it by skipping the first denomination. If you use one coin of a denomination you are free to use another one, but once you skip a denomination, you can't go back to it later. That way, assuming we are looking at the largest denominations first, we will count 10+1, but we will not also count 1+10, which is as it should be.

For example:

Problem 8b: Limited Change¶

The above assumed that you had a limitless supply of each denomination. What if you don't?

I'll define calculate_limited_change, where, instead of specifying denominations, you specify actual coins, repeating the ones you have more than one of. We use the same strategy, and if you skip a denomination, you can never use another coin of the same denomination.

Problem 8c: Optimal Denominations¶

The July 20, 2018 Riddler poses this problem (which has a Wikipedia article and a journal article):

I was recently traveling in Europe and struck by the number of coins the euro uses. They have 2 euro, 1 euro, 50 cent, 20 cent, 10 cent, 5 cent, 2 cent and 1 cent coins. This got me thinking: If Riddler Nation needed to make change (anywhere from 0.01 to 0.99) and was establishing its own denomination, what values of coins would be ideal to yield the smallest number of coins in any transaction? When picking values, let’s say we’re ditching the Europeans and limiting our denomination to four different coin denominations — replacing the current common American ones of penny, nickel, dime and quarter.

This is an optimization problem, not a counting problem, but it is related to the other coin/denomination problems here. Here's how I address the problem:

• The function totalcoins(denominations) will give the total number of coins (taken from those denominations) that are

required to make each amount of change from 1 to 99 cents (assuming optimal change choices).

• The function mincoins(amount, denominations) computes this optimal number of coins for a given amount, or returns infinity if the amount cannot be made.
• I know I'm going to need a 1 cent piece; otherwise I can't make 1 cent total.
• That leaves 3 coins that could be anywhere from 2 to 99 cents; let's try all combinations (even though it will take a minute or two).
• We'll report the candidate combination that has the minimum total number of coins.

Interesting! This is almost the US system of coins; we just need to trade in the dime for an 18 cent piece.