Thursday, September 27, 2018

some knots and not knots

Here are some knot patterns made using the online tool mentioned a few posts back. For each knot, the 'grid pattern' used to create the knot in the editor is also shown. First up, the simple unknot.

not a knot

Solomon's Knot
Next to this, we have a nice motif that is not a knot at all: the Solomon Knot is the name given to this motif of interlocked chains.

solomon unknot

BTW, you can make pattern that looks like  a solomon knot using truchet tiles:

truchet solomon unknot

Trefoil Knot
The trefoil is the simplest actual knot we can draw, but there are several ways to draw visually different but essentially equivalent trefoils, the first is considered the 'foundational' celtic knot:

trefoil 1

Here's another rendition:

trefoil 2

And one that is less recognisable:

trefoil 3

The Josephine Knot
Another non-knot (but very decorative), the Josephine consists of two interlaced links, and seems to be a favourite among crafters (who use it in belts, bracelets and macrame):

josephine link

Figure Eight Knot
The Trefoil is the only mathematically distinct prime knot with 3 crossings in a minimal planar diagram, and the figure 8 is the only one with 4. This version illustrates its name nicely:

figure eight 1

And here it is, a little lopsided:

figure eight 2

The Three-Twist
One of only two prime knots with five crossings, the three-twist (or 5_2) looks a lot like the figure 8. You can see how removing one of the lines in the grid pattern of the figure 8 allows for the additional twist that forms this knot.

the three-twist

The eight-eighteen
I don't know of a common name for the 8_18, but it's a nice looking knot, so it should have one. Here are two presentations of it:

eight-eighteen 1

eight-eighteen 2

Experiment with these and others here.

Wednesday, September 26, 2018

polynomial division practice page

I've added a new polynomial division page that generates random questions and asks you to fill in the answer, one step at a time. The page is here, along with its partners - a polynomial division calculator and example generator.

The page presents you with a randomly generated question, like this:

An initial grid is set up, with the divisor written down in the first column on the left. Everything else is unknown.

This is a grid for polynomial multiplication, but we only have one polynomial - we don't know what to put along the top for the other multiplicand. If we think of the division question as N/D = Q (numerator divided by denominator gives the quotient), the corresponding multiplication problem is DxQ = N, we have D (the denominator or divisor) and we want to find the Q to put along the top so that the contents of the grid give us N (the numerator or dividend). 

We start with the term with the highest degree in N. The page provides this prompt:

In terms of the grid, you are being asked for the coefficient for the term that will go in the leftmost empty cell in the top row.

The correct entry is -2. This allows another column of the grid to be filled in:

Now we look at the next term in N, following this prompt:

It turns out that no degree 1 term is needed in the solution since we already have all we need in the grid. When doing these by hand, you can just move on to the constant term, but on this page you actually need to put a 0 in the degree 1 column.

Moving on to the next term in N, we get this prompt:

Since there are no degree 2 terms in the table, the coefficient required is 4.

... and it turns out that the linear term also works out, as there is no remainder in this case. 

Try out the polynomial division practice page here, and visit this page for links to other posts and resources on the topic.

Tuesday, September 25, 2018

what day is it, usually?

In the Forest of Forgetfulness, Alice is trying to find out what day it is, and the unreliable denizens of the forest are not helping much. The Lion lies on Monday, Tuesday, and Wednesday and the Unicorn Lies on Thursday, Friday, and Saturday. What's more, each of them only makes one statement, and from that Alice must make her deduction.

Illustration by John Tenniel (public domain)

You can try to solve some of these puzzles here, and read about how you might solve them here.

Inspired by the original puzzles in What is the Name of this Book? by Raymond Smullyan, the Lion and Unicorn will say things like: "I told truths yesterday," or "tomorrow is one of my lying days."

If we generate a bunch of puzzles where X says "Y tells lies|truths yesterday|today|tomorrow" we end up with each creature being able to make 12 statements (after fixing the grammar a bit for verb tense). Two of those statements "I will tell truths today" (which can be said on any day), and "I will tell lies today" (which can never be said), can be thrown out,  so we get 10 statements from each creature for a combined total of 100 possible puzzles. However, it turns out that only 43 of those combinations end up generating good puzzles (puzzles where the statements lead to a unique solution). What does the set of solutions look like? We know just from the number of solutions that the 7 days of the week are not equally represented. Here's what the frequencies look like:

The first of Lion's lying days (Monday) and the last of the Unicorn's (Saturday) only occur once in the solution set, the last of the Lion's lying days (Wednesday) and the first of the Unicorns (Thursday) show up 10 times each.  The most common day is the day where they are both honest, Sunday, with 21. In this forest, it is never Tuesday or Friday.

Why not Tuesday or Friday?
This suggests a meta-puzzle: Why can Tuesday or Friday never be one of the puzzle solutions? If we look at what these days permit the Lion and Unicorn to say, we can see why this happens. Let's take Tuesday - this is a lying day for the Lion, and it happens right in the middle of Lion's lying day sequence (on Tuesday, yesterday, today, and tomorrow are all lying days). So this means the Lion can make the following statements (all lies):

I told truths today
I will tell truths tomorrow
I told truths yesterday
Unicorn told lies today
Unicorn told lies yesterday
Unicorn will tell lies tomorrow

It is a truth-telling day for the Unicorn, who can say the following:

I told truths today
I will tell truths tomorrow
I told truths yesterday
Lion told lies today
Lion told lies yesterday
Lion will tell lies tomorrow

On Tuesday, the Lion and the Unicorn can all make exactly the same statements... and also make exactly the same statements on Friday. Consequently, there is no way to distinguish between Tuesday and Friday given any pair of these statements, or tell who is lying and who is telling the truth. So none of the 36 puzzles formed by these sets of statements (the ones that could possibly be about Tuesday or Friday) are well formed puzzles (that have a unique solution).

Why is it that Sunday is so well represented in the set of puzzle solutions? Very close to half of our puzzles have Sunday as the solution (21/43). Here's an example of one of those puzzles, and here is another.

We can see how Sunday gets 21 days by listing the possible statements that can be made on that day, and seeing how the statements interact with each other. In round brackets after each statement we list all the days on which it is possible for the statement to be made (Sunday, plus some other days in some cases)

Lion's Sunday statements (all true)
I will tell lies tomorrow (Sunday, Wednesday) [5]
I told truths yesterday (Sunday, Tuesday, Wednesday, Friday) [3]

Unicorn told truths today (Sunday) [5]
Unicorn told lies yesterday (Sunday, Monday, Tuesday, Wednesday, Friday, Saturday) [3]
Unicorn will tell truths tomorrow (Sunday, Wednesday) [5]

Unicorn's Sunday statements (also all true)
I will tell truths tomorrow (Sunday, Monday, Thursday, Friday)
I told lies yesterday (Sunday, Thursday)

Lion told truths today (Sunday)
Lion told the truth yesterday (Sunday, Thursday)
Lion will tell lies tomorrow (Sunday, Monday, Tuesday, Thursday, Saturday)

Next to the Lion's statements, in square brackets we list the number of Unicorn statements that share no common days except Sunday. To Lion's statement "I will tell lies tomorrow," which can only be said on Sunday and Wednesday, all five of the Unicorn's statements can be paired to form a puzzle who's only solution is Sunday (none of the Unicorn's Sunday statements can also be made on a Wednesday). Counting up all the pairings from the list above we get 5 + 3 + 5 + 3 + 5 = 21.

Filling in some gaps

We'd like to have more puzzles, have every day represented, and not have so many Sundays. For a start, we can get some more puzzles by allowing each creature to say simply "today is Monday" or one of the other days of the week. Adding these statements increases our valid puzzle count by 67 to 110 puzzles (out of a possible 17^2 = 289 statement combinations).

Sunday more than doubles its frequency, now at 47 occurrences, and Tuesday and Friday make it in with 6 occurrences each. Monday and Saturday get 10 more occurrences, and Wednesday and Thursday get 26.

What else could we have the Lion and Unicorn say? We want them to be able to make a statement that provides a set of days as candidates for today. One example is to allow them to say "today is a weekday" or "today is the weekend." You can try out one of these puzzles here (The Lion says it is the weekend, the Unicorn says it is Friday).

Adding these two statements extend the number of statement combinations to 19^2=361, and extends the number of valid puzzles to 132. Because the 'weekend' and 'weekday' sets do not line up with the Lion and Unicorn lying days (Unicorn lies on one of the weekend days), the solution distribution is no longer symmetrical.

Monday shows up 12 times, Tuesday 6, Wednesday 38, Thursday 42, Friday 10, Saturday 13, and Sunday 54 times (down to about 41% of the puzzles).

Can we think of more statements for the Lion and the Unicorn? Sure. But with 132 puzzles to solve, let's stop here for now. Other interesting ways to change the number of solutions and their distribution is to change which days the are "truthful" for our forest friends - what if they are honest more often, and what if their lying days overlap? You can play with those questions by modifying the notebook here.

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.
$$ \begin{split} Days =& \{\textrm{Monday, Tuesday, Wednesday,} \\ & \textrm{Thursday, Friday, Saturday, Sunday} \} \end{split} $$ 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.
$$ \begin{split} L =& \{ \textrm{Monday, Tuesday, Wednesday}\} \\ U =& \{ \textrm{Thursday, Friday, Saturday}\} \end{split} $$
The days that the animals are telling the truth are listed in the complements of each set.
$$ \begin{split} \overline{L} =&\{ \textrm{Thursday, Friday, Saturday, Sunday}\} \\ \overline{U} =& \{ \textrm{Sunday, Monday, Tuesday, Wednesday}\} \end{split} $$ 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.
$$ \begin{split} L \cap U =& \emptyset \\ \overline{L} \cap \overline{U} =& \{ \textrm{Sunday} \} \end{split} $$ 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:
$$ S_L = t(L) = \{ \textrm{Tuesday, Wednesday, Thursday}\} $$ 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.
$$S_L \cap \overline{L} = \{ \textrm{Thursday}\}$$ 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.
$$\overline{S_L} \cap L = \{ \textrm{Monday} \}$$ 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: $$ \begin{split} D_L &= ( S_L \cap \overline{L} ) \cup ( \overline{S_L} \cap L ) \\ &= \{ \textrm{Monday, Thursday} \} \end{split} $$ Going through a similar process, we can get another set of days based on the Unicorn's statements.
$$ \begin{split} D_U &= ( S_U \cap \overline{U} ) \cup ( \overline{S_U} \cap U ) \\ &= \{ \textrm{Sunday, Thursday} \} \end{split} $$ 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:
$$ \begin{split} D &= D_L \cap D_U \\ &= [ (S_L \cap \overline{L} ) \cup ( \overline{S_L} \cap L)] \cap [ (S_U \cap \overline{U} ) \cup ( \overline{S_U} \cap U)] \\ &= \{ \textrm{Thursday} \} \end{split} $$ 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 this version.