How to solve the water pouring puzzle programmatically.¶

Given two jugs of capcity of 3 and 5 liters, acquire exactly 4 liters in a jug. Assume an unlimited water supply, and that jugs can only be filled or emptied, i.e., no estimations.

First to model the data: a mapping of jug sizes to their current quantity. There are 3 primitive operations:

• filling a jug to capacity
• emptying a jug entirely
• pouring from a source jug to a destination jug, until either the source is emptied or the destination is full

That's sufficient to solve the puzzle through sheer brute force: scanning every possible combination breadth-first. Note the below implementations don't terminate unless a solution is found.

Now to relentlessly simplify the code. The first observation is that an empty source is useless, as is a full destination. So the fill and empty primitives are actually unneeded, and can be integrated into the pour method.

That reduced the search space considerably, but moreover has revealed another simplification: it's pointless to "undo" a pour. Whether the source was emptied or the destination was filled, whatever reversing the previous pour direction would accomplish could have been done in the first place.

If there were more than 2 jugs, then there could be complex workflows. But with only 2, the first choice in pour directions determines the rest. There are only 2 potential solutions to the puzzle.

And both of them are valid solutions. The solution to the puzzle is quite simply: keep pouring. It doesn't even matter which to start with.

But it can be further simplified. Now it's clear that the jug data structure is only providing modular arithmetic.

The puzzle is looking for integer solutions to $$ \ 3x + 5y = 4 $$ Which is known as a linear Diophantine equation, and must have a solution because $4$ is a multiple of $gcd(3, 5)$.

How to solve the coin balance puzzle programmatically.¶

Given a balance and a set of coins, which are all equal in weight except for one, determine which coin is of different weight in as few weighings as possible.

Twelve-coin problem

A more complex version has twelve coins, eleven or twelve of which are identical. If one is different, we don't know whether it is heavier or lighter than the others. This time the balance may be used three times to determine if there is a unique coin—and if there is, to isolate it and determine its weight relative to the others. (This puzzle and its solution first appeared in an article in 1945.[2]) The problem has a simpler variant with three coins in two weighings, and a more complex variant with 39 coins in four weighings.

First to model the data:

• An enum to represent different weights. Following the ternary comparison convention, such as Python 2's cmp, is convenient.
• An object to represent the balance. For testing, it will need to be configurable with the target coin and relative weight.
• An object to represent a coin and its state. A class is tempting, but the most useful data structure would keep the coins grouped by their known (or unknown) state anyway. So any hashable unique identifier is sufficient.

As is typical with induction puzzles, the constants chosen are just large enough to thwart an iterative approach. The 2 weighing variation would be trivial enough for most people to brute force the solution. Whereas 4 weighings would already be such a large decision tree, it would be tedious to even output. The easier approach is solve the puzzle recursively and more generally, for any number of coins and weighings.

So what can be done in a single weighing? Clearly all weighings must have an equal number of coins on each side, else nothing is learned. If it balances, then the different coin is in the unweighed group. If it doesn't balance, then the different coin is in the weighed group, but additionally it is known whether each coin would be heavy or light based on which side it was on. This is the crucial insight: there's a variant recursive puzzle embedded inside this puzzle.

The Towers of Hanoi is a classic puzzle often used in computer science curricula to teach recursion. This one would suitable as a subsequent more advanced problem.

So what can be done with known coins in a single weighing? If it balances, then as before the different coin is in the unweighed group. But if it doesn't balance, then which way can be used to further narrow the coins. Consider the heavier side; the different coin must be one of the heavy ones on that side, or one of the light ones on the other side. Therefore the coins can be split into 2 equal sized groups by putting equal numbers of heavy coins on each side, and equal numbers of light coins on each side. One obstacle is that if there aren't an even number, there will need to be filler coins just to balance. But that won't be a problem after the first weighing.

Now we can implement a solution to the sub-problem, and build the need for filler coins into the balance implementation. A generator is used so that the output of each weighing can be displayed.

Now with the sub-problem solved, there's just one thing missing for the main puzzle. In the known case, splitting into 3 equal sized groups is cleary optimal. But in the unknown case, we need to know how many coins to exclude from the weighing. This requires computing how many coins can be handled in the subsolution. Lucikly it's a trivial recurrence relation: n weighings can solve 3 times the number of n - 1 weighings. $$ \prod_{}^n 3 = 3^n $$

The puzzle is solved. There's one last simplifcation that can be made, but requires a bit more math background. Ideally we wouldn't need to know the objective number of weighings; the algorithm would just solve any set of coins as efficiently as possible. To do that, the number of coins that can be solved has to be computed. As was done above, but this recurrence relation is more advanced: each weighing can solve 3 ^ n more coins. $$ \sum_{k=0}^{n-1} 3^k = (3^n - 1) / 2 $$

With that calculation inverted, the count can be removed from the interface

Notice the formula indicates it's possible to do 13 coins in 3 weighings, and it would be with a filler coin to balance out the 9 that need weighing.

How to solve the Hat puzzle programmatically.¶

Ten-Hat Variant

In this variant there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners will be lined up single file where each can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are killed on the spot. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 9 of the 10 prisoners will definitely survive, and 1 has a 50/50 chance of survival. What is the plan to achieve the goal?

This puzzle involves three concepts common to classic logic puzzles:

• Theory of mind
• Functional fixedness
• Induction

Theory of mind comes into play because each prisoner has differing knowledge, but assumes everyone else will think similarly. Functional fixedness occurs more subtly; each prisoner may state a color only to convey information. But because the information is encoded as a color, it tends to focus thinking on the colors themselves. So to combat that cognitive bias, first create a different enumeration to represent statements. Any binary enum can be mapped back to colors, so why not bool.

Which leaves induction: solve the puzzle for the base case (smallest size) first, and then methodically build on that solution. In the case of 1 prisoner, they have no information a priori, and therefore have a 50/50 chance of survival regardless of strategy. This variant of the puzzle already gives the optimal goal, so we know that everyone but the 1st can say their color and be saved, while the 1st can devote their answer to the common cause.

In the case of 2 prisoners, obviously the 1st can say the color of the 2nd. That approach does not scale; it is the path to functional fixedness. Instead, methodically enumerate all possible statements and colors to determine if there is an unambiguous solution.

The above table is a general solution with no assumptions other than the arbitrary ordering of enums. While it may appear absurdly pedantic, it represents a rule set which is key to building a recursive solution.

In the case of the 3rd prisoner, clearly they can not just repeat the above rule set, because the 3rd would receive no information. But there are only 2 choices, so the only option is to follow the opposite rule set, depending on the 3rd color.

The crucial step is to build off of the existing table.

The solution is valid if each prisoner is able to narrow the possibilities to a unique row based on the colors they hear and see.

The general solution is simply the above logic in recursive form, with a parametrized size.

The complicated puzzle is actually a trivial recurrence relation. $$ 2^n = 2^{n-1} * 2 $$ There are $2^n$ states of the prisoners, and each prisoner has $n-1$ bits of data. So an additional bit of data from the first is sufficient to solve the puzzle.

The puzzle is solved, but the output is of exponential size, certainly not the succinct solution which makes the puzzle famous. But instead of relying on a flash of insight, this approach produces not just a solution, but the solution. The only arbitrary decision made was the enumeration. Therefore it must be the case that the solution can be summarized.

First, it would be helpful to group the solution by the 1st statement. Any summary function would have to ensure that there is no collision in the grouped possibilities.

Now what summaries to attempt? Well there are few properties of sequences to work with: size and order. They are all the same size, so that won't help. That leaves ordering, which can be easily tested by sorting.

Success. Now that order does not matter, the appropriate data structure is a multiset (a.k.a. bag). Each prisoner can keep track of only how many of each color they hear and see.

Since there are only 2 colors which sum to a constant, keeping track of just one is sufficient.

There's one last pattern to the numbers, which can be used to achieve parity with the canonical solution.

Split an iterable into equal sized chunks.¶

A common task and interview question, with many variants. It's frequently asked and answered in a way that's suboptimal and only handles one specific case. The goal here is to present definitive, general, and efficient solutions.

The first variant is whether or not the chunks will overlap. Although this could be generalized into a step parameter, it's nearly always the case that step in (1, size).

The second variant is whether the tail of the data should be returned, if it's not of equal size. Clearly when step == 1 that's unlikely to be desirable. However, when step == size, that would seem to be the natural choice. And again when 1 < step < size, the desired behavior isn't clear at all.

The third variant is whether to slice sequences, or support any iterable. Obviously working for any iterable would be ideal, but it's also likely a user would expect slices given a sequence, particularly in the case of strings.

So this author feels it's best to split the problem in 2 distinct cases: a sliding window for overlapping sequences, and chunks for discrete sequences. In each case, supporting iterables and using advanced iterator algebra for a minimal and efficient solution.

Window¶

That's simple, and close to optimal. There is slight overhead in iterating an islice object, so a minor variant would be to force the step-wise iteration in advance.

Chunks¶

A lesser-known and under-utilized feature of iter is that in can take a callable (of no arguments) and a sentinel to create an iterator. A perfect use case of the "loop and a half" idiom.

This should also be optimal, for reasonable sizes.

Sequences with dispatch¶

Rather than explicitly check isinstance, this is a perfect use case for functools.singledispatch.

A Paul Graham classic, the accumulator function.¶

As an illustration of what I mean about the relative power of programming languages, consider the following problem. We want to write a function that generates accumulators-- a function that takes a number n, and returns a function that takes another number i and returns n incremented by i.

(That's incremented by, not plus. An accumulator has to accumulate.)

In Common Lisp this would be

(defun foo (n) (lambda (i) (incf n i)))

...

If you try to translate the Lisp/Perl/Smalltalk/Javascript code into Python you run into some limitations. Because Python doesn't fully support lexical variables, you have to create a data structure to hold the value of n. And although Python does have a function data type, there is no literal representation for one (unless the body is only a single expression) so you need to create a named function to return. This is what you end up with:

def foo(n): s = [n] def bar(i): s[0] += i return s[0] return bar

Python users might legitimately ask why they can't just write

def foo(n): return lambda i: return n += i

or even

def foo(n): lambda i: n += i

and my guess is that they probably will, one day. (But if they don't want to wait for Python to evolve the rest of the way into Lisp, they could always just...)

There are other solutions, using function attributes or instances with a __call__ method, but none are substantially more elegant. The challenge predates Python 3, which introduced the nonlocal keyword, making this the presumably preferred solution:

There was also yet another alternative as of Python 2.6: using a generator as a coroutine.

To satisfy the challenge, that would need to be wrapped with a decorator. The triple partial expression below may seem a little obtuse, but it's not as bad as it looks. Just unwind it one step at a time.

But what's the most Pythonic solution? This author would argue... don't. In my experience, I have never really needed global or nonlocal in production code. Typically it's because the objects in question are mutable, so it's not necessary to rebind a name in a different scope to a new object.

A typical tell of these kinds of code challenges are that they focus on the interface or implementation exclusively, never both in context. Python numbers are immutable, and have syntactic support for incrementing, so there's nothing more readable about acc(...) instead of n += ....

Futhermore, the accumulator object is intended to be used repeatedly, such as in a loop. In a language with such strong iteration support as Python, it's extremely likely that accumulation will occur in a iterative loop. Indeed, the real accumulator has since been added to the standard library.

Contrarian view on map and filter.¶

Although PEP 8 is silent on the topic, it's become recommended in many Python circles to eschew map and filter in favor of generator expressions or list comprehensions. For example, this Stack Overflow question received and accepted a typical response. Ironically, that question misquoted the google style guide, which this author happens to agree with.

Use list comprehensions and for loops instead of filter and map when the function argument would have been an inlined lambda anyway. [emphasis added]

The style guide also shows a non-lambda version as a positive example:

map(math.sqrt, data) # Ok. No inlined lambda expression.

First, a brief history of how the Python community arrived at this state.

Python 1¶

Prior to version 2.0, Python had neither list comprehensions nor nested scopes. Therefore simple map and filter operations had to use a for... append loop, or lambda. But the lacked of nested scopes was inherently crippling to the latter approach.

A NameError would have been raised on x, because it's not defined in the inner scope. One clever work-around was to shadow default arguments.

Unsurprisingly, that was widely viewed as an ugly hack. Many resigned themselves to for... append loops instead.

Python 2¶

Then Python added list comprehensions in 2.0, and that became the one obvious way to do it.

Python acquired nested scopes in the next version, 2.1, but the damage was done. Functional programming in Python in general, and lambda in particular, was widely frowned upon. Even though the lack of nested scopes affected all inner functions used in any context; it was never really about lambda per se.

Python 3¶

It's sometimes claimed to this day that map and filter only exist for backwards compatibility. But that belies the history of Python 3. map, filter, and reduce were all considered for removal. But only reduce was banished to the functools module. map and filter were not only retained, but updated to return iterators.

So it's already dubious to claim that using a built-in is unapproved. But the real point is that map and filter remain a higher level abstraction. Sure, with lambda there are the same number of logical components, and it's just a matter of syntactic sugar. But there is some abstraction value when the functions already have a name.

It's also commonly pointed out that generator expressions are superior because they can do a map and filter simultaneously, but crucially only if the filter comes first. Consider this task: normalizing an iterable of strings.

Note list is only being used for printing, and should be ignored for the sake of comparisons.

As for the alternative, surely calling strip twice to use a single expression is just plain cheating. So really the only option is:

Some would consider nested comprehensions already enough to separate with a temporary name. But that's inadvertently acknowledging how much more verbose it is.

Can it really be claimed that the latter is more readable than the former? It's just boilerplate, which never seems acknowledged in small examples. But if one only has to double the size of the context to show how verbose comprehensions are, doesn't that demonstrate the value of map and filter.

Epilogue¶

And now a shameless plug of the author's placeholder package for readers who appreciate function-style programming. It provides syntactic sugar for lambda.

But even speaking as the author, map isn't the best use case. Sort keys are a much better example, since there is no competing syntax.

Python 3.8's new assignment expressions provide yet another alternative.

The infamously simple FizzBuzz problem.¶

Reportedly a high percentage of programmer applicants can't solve this quickly.

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

A deep dive on this problem has been done in jest many times, e.g., deliberate over-engineering or code golf. But in all seriousness, let's consider what's the most Pythonic solution. A truncated version of the common solution:

Naturally interview questions tend to focus on output, e.g. print, but that's no reason to skip over basic abstractions or data structures. First, this could be written as a generator, to decouple the print operation and parametrize the numeric range. Alternatively, Python has such strong iterator support that it could also be just a function, ready to be mapped. So let's reframe the basic solution as:

Even at this size, it's already violating DRY, or the Rule of 3. Clearly the same logic is being repeated with different data.

However, that variation had to introduce the concept of the least common multiple. Even in such a trivial problem, there's a subtlety in how one interprets requirements. The final directive to output "FizzBuzz" can be seen as a mere clarification of the previous directives; certainly not a coincidence. Making this the more obvious solution:

Arguably that insight is more important, because its duplication grows exponentially, not linearly. There's a 2**N sized case statement to handle N cases, luckily N == 2. Adding just one more directive for the number 7 would make the basic solution unwieldy.

And of course both approaches can be combined.

So is that over-engineered? This author would argue that both deduplication and decoupling logic from data are worth observing. So maybe at this size the final version isn't necessary, but surely the basic version is not the most Pythonic.

How to solve the Cheryl's Birthday puzzle programmatically.¶

1. Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gave them a list of 10 possible dates:

    May 15     May 16     May 19
   June 17    June 18
   July 14    July 16
   August 14  August 15  August 17

2. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.
3. Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.
4. Bernard: At first I don't know when Cheryl's birthday is, but I know now.
5. Albert: Then I also know when Cheryl's birthday is.
6. So when is Cheryl's birthday?

As with the pytudes solution, the goal is to solve the puzzle in code. A different approach is taken here though, for simplicity and extensibility.

The first step is to model the data. A set of Date objects is suitable to represent the current possible dates. Since datetime.date objects require a year, a minimal collections.namedtuple is used instead.

As is typical of these kinds of puzzles, it assumes all participants have perfect Theory of Mind. That is, each participant making a statement is applying their private knowledge to what is publicly known, and assuming everyone else will do the same. With that in mind, the claims made fall into 3 categories:

• I know ...
• I don't know ...
• They don't know ...

The temporal variations "now" and "at first" can be modeled by the current set of dates. Any claim then can be implemented functionally in this form:

So what does it mean for Albert or Bernard to "know" the correct date? It would mean applying their knowledge of the month or day leaves only one possibility. The "I know ..." function therefore groups and filters for uniqueness.

To implement "I don't know ...", known could be parametrized with a different predicate (> 1), or simply use set.difference. "I don't know ..." is so trivial it's arguably not worth the abstraction.

The challenging part is what does it mean for Albert to claim Bernard doesn't know. All dates that would be knowable to Bernard must clearly be excluded, but Albert would have to exclude them based on his knowledge of the month. So "They don't know ..." is similar to unknown, but the exclusion is based on a different field.

This is sufficient to simply walk through the statements, one at a time.

Exactly one date is left, indicating success. Now the succinct in-lined version, with no superfluous statements.