Saturday, September 15, 2018

Solving (some) Logic Puzzles with Sets

As you may have noticed, since around this time last year, I have been playing around with generating puzzles based on those found in some of Raymond Smullyan's books. This has included Knights and Knaves, Portia's Caskets, The Case Files of Inspector Craig, Tigers and Treasure, and The Isle of Dreams. Some of the differences between puzzles are superficial: A "Portia's Casket" puzzle can be recast as a "Knights and Knaves" puzzle, for example. Even though there is some common deep structure to these various puzzles, I've found that sometimes the puzzle types call out for different approaches when writing solvers or generators.

The latest puzzle type that I have been enjoying is based on some puzzles found in Smullyan's What is the Name of This Book?. The "Lion and the Unicorn" puzzles are built around characters from Lewis Carroll's Through the Looking-Glass, and What Alice Found Thereand for this logic puzzle variation, I found that using sets to model the puzzle (rather than, say, propositions, truth tables, or graphs) seemed to make the most sense.

The Lion and the Unicorn, posing
at the East Block 

As described in the chapter 47 Alice and the Forest of Forgetfulness,
When Alice entered the Forest of Forgetfulness, she did not forget everything, only certain things. She often forgot her name, and the one thing she was most likely to forget was the day of the week. Now, the Lion and the Unicorn were frequent visitors to the forest. These two are strange creatures. The Lion lies on Mondays, Tuesdays, and Wednesdays, and tells the truth on the other days of the week. The Unicorn, on the other hand, lies on Thursdays, Fridays, and Saturdays, but tells the truth on other days of the week.
One day, Alice met the Lion and the Unicorn resting under a tree. They made the following statements: 
Lion: Yesterday was one of my lying days. 
Unicorn: Yesterday was one of my lying days too.
Alice must know: What day is today? 
If you think you have a solution to this - test it out on the interactive version of the puzzle.

If we model this using sets, our universe of discourse for this problem is the days of the week.


We consider the set L of days for which the lion is lying, and the set U of days for which the unicorn is lying.

The days that the animals are telling the truth are listed in the complements of each set.


These two sets have an empty intersection - the two characters never lie at the same time. The intersection of their truth-telling days is non empty, however: both tell the truth on the same day once a week.
The set Days is a set with structure, the days are an ordered set - the lion and the unicorn can talk about 'yesterday' and 'tomorrow.' For any set of days we can ask for its 'tomorrows' - the set of next days, or its set of 'yesterdays', the set of preceding days. When the lion says "I told lies yesterday" this can be translated as "today is a tomorrow for one of my lying days." The set of days covered by Lion's statement would be:

But do any of the days covered by Lion's statement coincide with a day that he is telling the truth? To believe his statement about what day it is, it must describe a day that he is actually speaking truthfully. If Lion is telling the truth, it must be a day in the intersection of the days in Lion's statement and the set of Lion's truthful days.

But, Lion could be lying. If Lion is lying, then today is in the intersection of the days not in Lion's statement, and Lion's lying days.
Since we don't know whether the lion is telling the truth or lying, we have to consider both possibilities, so the set of days that it could be, based only on Lion's statement is:


Going through a similar process, we can get another set of days based on the Unicorn's statements.


Days that fall in both the set from the Lion and the set from the Unicorn are possible solutions for today's day - if the intersection is empty, then there is no solution, if there are several days in the intersection, then the puzzle is ambiguous, if there is a single day in the intersection, that is today:


The notation might make this way of thinking seem difficult - here is the process stated a bit more plainly (see that it lines up with the formula above...):

1. Consider the Lion. Which days does the Lion's statement refer to?
2. Of these days, which coincide with Lion's truthful days?
3. Which of the days are not covered by the Lion's statement? Do any of these coincide with Lion's lying days?
4. Combine these two lists of days from the Lion.
5. Follow steps 1 through 4 for the Unicorn to produce a list of possible days from the Unicorn.
6. If there is one day that that is in both the Lion's list and the Unicorn's list, that is the solution.

We can come up with variations on this puzzle by varying the statements made by the Lion and the Unicorn. Instead of saying "I told lies yesterday," we could have them say things like "I will tell truths tomorrow" or "today is a week day", or even "today is Wednesday." Some of these will generate good puzzles (one element in the final set), others may not.

A Jupyter notebook that generates 132 puzzles like this can be found here, and you can the puzzles out over here.

Thursday, September 6, 2018

generating celtic knot patterns

This post describes an algorithm for generating celtic knot patterns - ornamental knots, links, and braids that are laid out in a grid, like the one below:


If you would rather skip reading about how these are generated and start playing around with creating patterns like the one above, please try out the editor and random knot-pattern generator that I've posted on my github pages.

I have tried out various strategies for generating these patterns (for example,  using tiles), but the method described here is closest to how I like to draw them by hand, as described in the book by Aidan Meehan, Celtic Design: Knotwork - The Secret Method of the Scribes. The variation offered here is intended to suggest how to write a program to generate these patterns based on a simplified version of the techniques in Meehan's book.

A knot pattern is made up of strands that represent string or chord, and the gaps between the woven strands. The technique described below actually involves drawing the gaps, with the strands emerging out of the negative space between the gaps. Essentially, a grid of dots are drawn, and lines are selectively drawn between adjacent dots - these become the gaps between the strands. Additional rules are applied to connect the dots to create a woven effect, and the dots are replaced with polygons to  create a more stylised effect.

1) define primary grid points
A knot pattern is laid out on a square coordinate system using a set of "primary" points that are set at one unit distances in the horizontal and vertical directions. We'll say that (0,0) is the top left corner of the grid, and the positive x direction is towards the right and positive y direction is down.  The dimensions of the primary grid must be odd (there must be a total odd number of dots in both the x and y directions). Because we are starting with (0,0) in the top left, the top right point (x, 0) must have x even (4 in the example below), and the bottom left point (0,y) must have y even (6 in the example below).

the primary grid

(Note: In Meehan's account, things are layered a little differently so what we are calling the primary grid is referred to as the tertiary grid.)

2) identify secondary grid points
Some of the points on the grid are special - these form a secondary grid. The special secondary grid points are those where both x and y values are even, or both are odd.

the secondary grid

In step 4 below, the secondary grid points where both x and y are even will be referred to as even nodes, and those that have both x and y odd will be referred to as odd nodes. The requirement to have the primary grid have odd dimensions (step 1) was needed to ensure that the corners of the pattern are all secondary points.

3. draw a quadrilateral around the nodes
Each node will become a gap in the node pattern - the basic shape of a gap is quadrilateral whose vertices lie 1/4 unit above, below, and to the right and left of each node.

the basic node polygon

With all of the polygons drawn for the nodes, we get a grid of 'diamonds' like this:

node polygons drawn for
secondary grid points


4. extend lines from node polygon vertices
To create a woven affect, we extend lines from the vertices of each node polygon


Doing this for all nodes creates an image like the one below.

lines extended from node
polygon vertices

If you exchange the rules for odd and even nodes, you end up with a correct "opposite" weave: strands that were going under instead go over, and vice-versa.

5. place barriers, drop lines
In the above image, the simple woven pattern seems to extend off the sides. To create an edge boundary for the pattern, and to create more interesting twists and turns, we follow some rules for drawing boundaries.

boundary rule 1: A boundary can connect any two non-diagonally adjacent nodes (secondary points), as long as rule 2 is not violated. The midpoint of a boundary segment will be a primary point.

boundary rule 2: A primary point cannot have more than one boundary going through it.

The example below shows boundaries drawn along the edge of the image, as well as some internal boundaries.
legal boundary examples, showing
primary and secondary points
(node polygons are hidden)

Now that we have introduced boundaries, we refine how lines are drawn coming out of the nodes (adjusting step 4):

node-line rule: Only draw a line from a node vertex if there is no boundary across from the vertex.

Applying the node-line rule, and drawing the polygons (and dropping the primary grid points) we get an image like the one below, where the weaving respects the boundaries - the strands (in white) that emerge seem to bounce off the edges and twist to avoid internal boundaries.

node polygons, boundaries, and lines 

6. refine node polygons
We can apply some styling rules to make the pattern look smoother - these changes to our original node polygon (step 3) will be based on whether or not there are boundaries next to the node.

node-style rule: Truncate (chop off) the vertex of a node polygon that is next to a boundary.

Below is the same pattern above, but with the node polygons following the node-style rule. You can see the effects of the rule most clearly by looking at the nodes near the edge of the image, and particularly the corner nodes.

pattern using truncated
node polygons

It is possible to add further adjustments to how the nodes and lines are drawn to create smoother looking knot patterns. I have experimented a bit, but have not obtained great results. Here's an example of the same patter above that adjusts the node polygons and line thicknesses:

a slightly different style applied
to the knot pattern

I hope you enjoy playing around with this - either implementing the process described above yourself or playing around with my version: there is a simple editor available here, and one that allows for further adjustments of the size and dimensions here.


Wednesday, June 6, 2018

origami workshop again

A few years back, I posted some notes about an origami workshop that I had run with some middle school students. Last week I had the opportunity to run origami workshops with similar groups of students, using many of the same models I mentioned before (including the hopping frog).



One nice model that I used this time that is not mentioned in that other post is the multiform (aka windmill/pinwheel) -  a flexible hinged surface from which several simple models can be folded, including the windmill, the house, and the pajarita, and which can be extended to form the masu box and others.


Thursday, May 17, 2018

The Isle of Dreams

After a short break, we are returning to some logic puzzles inspired by those of Raymond Smullyan. Earlier we visited the island of knights and knaves, looked into Portia's caskets, explored the case files of Inspector Leslie Craig, and looked behind doors for tigers and treasure. In this post, we are visiting the Isle of Dreams. As Smullyan says in his book The Lady or The Tiger?:
I once dreamed that there was a certain island called the Isle of Dreams. The inhabitants of this island dream quite vividly; indeed, their thoughts while asleep are as vivid as while awake. Moreover, their dream life has the same continuity from night to night as their waking life has from day to day. As a result, some of the inhabitants sometimes have difficulty in knowing whether they are awake or asleep at a given time.  
Now, it so happens that each inhabitant is of one of two types: diurnal or nocturnal. A diurnal inhabitant is characterised by the fact that everything he believes while he is awake is true, and everything he believes while he is asleep is false. A nocturnal inhabitant is the opposite: everything a nocturnal person believes while asleep is true, and everything he believes while awake is false. 
On this island then, each islander has a type (diurnal or nocturnal), and a state (awake or asleep), and based on their type and state, you can assess the veracity of their thoughts (either true or false).

To play around with this, I decided to make some puzzles similar to ones found in The Lady or The Tiger?, but based on the thoughts of two islanders A and B. Each islander has two distinct thoughts: one about themselves (either about their state or their type), and one about the other (either their state or their type). Importantly, these thoughts occur to both A and B at exactly the same time. Here is an example:

  • Islander A has two distinct thoughts at the same moment: I am nocturnal. B is diurnal.
  • At the same moment, islander B has these distinct thoughts: I am awake. A is diurnal.
We want to know: what is the actual type and state of both A and B? Can we know everything about them, or is their something about them that we cannot tell? Or maybe these thoughts are impossible, and lead to contradictions.

To solve these kinds of puzzles, it helps to know the Four Laws of the Isle of Dreams:

  1. An islander while awake will believe they are diurnal.
  2. An islander while asleep will believe they are nocturnal.
  3. Diurnal inhabitants at all times believe they are awake.
  4. Nocturnal inhabitants at all times believe they are asleep.
Let's just establish the first law, and then you should try to convince yourself of the others. Consider the case of a diurnal awake islander: because they are diurnal and awake, they think true thoughts, so they will correctly think that they are diurnal. Second, consider the case of a nocturnal awake islander: because they are nocturnal and awake, they will think false thoughts, and will conclude that they are diurnal. So, no matter whether an islander is diurnal or nocturnal, when awake they will think they are diurnal (some correctly, some falsely). Using this along with rule 2, if an islander thinks they are diurnal, you should conclude that they are awake.

Now back to the puzzle:

  • Islander A has two distinct thoughts at the same moment: I am nocturnal. B is diurnal.
  • At the same moment, islander B has these distinct thoughts: I am awake. A is diurnal.
Applying the four laws of the Isle of Dreams to the first thoughts of the islanders in the puzzle above, we know that A must be asleep (law 2) , and that B must be diurnal (law 3). Now turning to A's second thought: because they are asleep and thinking something that is true (B is diurnal) A must be nocturnal. B's second thought is not true, so since they are diurnal they must be asleep. So, A is nocturnal and asleep, while B is diurnal and asleep. Sweet dreams, A and B.

How many puzzles can we make like this, where we have two islanders, each thinking something about their state or type and something about the state or type of the other? Well, there are 4 possible thoughts an islander could have about themselves (I am awake/asleep/nocturnal/diurnal) and 4 possible thoughts about the other (They are awake/asleep/nocturnal/diurnal), giving us 16 pairs of thoughts. Since there are two islanders involved, this gives 256 puzzles (really only 128 truly different puzzles, as A and B are interchangeable).

You can try out all 256 of them, or as many as you like, here. They look something like this:



This collection of puzzles has some interesting features. There are 192 that are completely solvable: you can find the type and state of both A and B from the thoughts that they think (like the example above). There are 32 partially solvable puzzles, where the first thoughts of A and B (their thoughts about themselves) tell us something about their state and type, but their second thoughts (about the other islander) are inconclusive. Finally, there are 32 puzzles included in the set where the thoughts of A and B are contradictory, and therefore impossible. We can include these contradictory items in the set, as the question page gives you the chance to identify these nasty puzzles.



It turns out that the distribution of the partially solvable and impossible puzzles display an interesting pattern. Let's consider all 16 pairs of thoughts, and make a graph showing which combinations are (a) completely solvable, (b) partially solvable, or (c) impossible.

Here are the 16 pairs of thoughts an islander might have:

1: I am awake. The other is awake.
2: I am awake. The other is asleep.
3: I am awake. The other is diurnal.
4: I am awake. The other is nocturnal.
5: I am asleep. The other is awake.
6: I am asleep. The other is asleep.
7: I am asleep. The other is diurnal.
8: I am asleep. The other is nocturnal.
9: I am diurnal. The other is awake.
10: I am diurnal. The other is asleep.
11: I am diurnal. The other is diurnal.
12: I am diurnal. The other is nocturnal.
13: I am nocturnal. The other is awake.
14: I am nocturnal. The other is asleep.
15: I am nocturnal. The other is diurnal.
16: I am nocturnal. The other is nocturnal.

Let's create a graph where the horizontal axis represents A's thoughts and the vertical axis represents B's thoughts. A white square on the graph represents a completely solvable puzzle for that x/y combination of thoughts, a grey square on the graph represents a partially solvable puzzle, and a black square represents an unsolvable puzzle.

solvable, partially solvable, and unsolvable
Isle of Dreams puzzles

This is really neat: the partially solvable and unsolvable combinations form an interesting pattern dispersed through the whitespace of the completely solvable puzzles. There are 16 "problem squares" of 4 puzzles that have a distinct symmetric pattern, and these 16 problem squares are arranged in 4 sets of 4 puzzles that also have an interesting symmetry.

We'll zoom in on one of the "problem squares" to give a better picture of what the graph is displaying:


Let's look at one of the contradictory puzzles - the one in the bottom left of this "problem square."

A is thinking #1: I am awake. The other is awake.
B is thinking #5: I am asleep. The other is awake.

From their first thoughts, we know that A is diurnal and B is nocturnal. If A is awake, they they will think true thoughts and consequently B is awake. If B is awake, they must be thinking false thoughts, requiring A to be asleep - a contradiction. On the other hand, if A is asleep, they will be thinking false thoughts, so B will be asleep. B will then be thinking true thoughts, requiring A to be awake, again a contradiction.

But why to these partial/contradictory puzzles form the patterns that they do? Maybe we will return again to the Isle of Dreams someday to find an answer.

Try the puzzles out here: https://dmackinnon1.github.io/inspectorCraig/dreamers.html

Sunday, May 6, 2018

more bipartite art


Playing around with some of the images created by connecting two sets of dots. In this case, every dot from the second set is connected to every dot in the first set, and the two sets are arranged in concentric circles. In the picture above, the first set of dots has 12 equally spaced dots in a circle, and the second set has 48, but the second set is arranged on a circle whose radius is much, much larger than the first, so the lines from the second set to the first come in from a great distance.

If both sets have 3 dots, both sets are on concentric circles, and one of the sets is on a much larger circle, you might get something like this:



The second set is so far out, that it looks like the lines from a point the second set are parallel. If the first set has 3 points and the second far-out set has 6 points, you might get something like this:



Increasing size of the far-out set to 18 points:



Can you figure out the number of points in each set that would generate an image like this? You can test out your guesses here.