Solving riddles

1 Introduction

Here is a funny riddle: An island has two types of inhabitants: knights and crooks. Knights always tell the truth, crooks always lie. Suppose an inhabitant A claims about himself and his brother B: "At least one of us is a crook." nOf which type are A and B?

Below we solve this riddle by hand, but, as becomes clear, this is a bit tedious. Can't we use the computer to solve problems like this? In fact, PyEDA is a package to solve such constraint satisfaction problems, in particular problems that can be formulated with Boolean algebra. Here we show how to use this package to attack such logical riddles.

2 Riddle: At least one of us is a crook

The above logical problem can be solved in a nice way with Boolean algebra. Let \(A=1\) if person A is a knight, and \(A=0\) if he is a crook, and similar for \(B\). With these variables, and writing \(A'\) for the complement of \(A\), the statement of person A can be written as

\begin{equation*} C = A B' + A' B + A' B'. \end{equation*}

Now, if A is a knight, he speaks the truth; and then, by consequence, claim \(C\) must be true. Thus, if \(A=1\), it must be that \(A C = 1\). On the other hand, if A is a crook, he lies, so that claim \(C\) is false (and \(C'\) is true.) Thus, if \(A'=1\) (i.e., person A is a crook), it must be that \(A' C' = 1\). Since also A is a knight or a crook, either \(AC=1\) or \(A'C'=1\), implying that

\begin{equation*} 1 = AC + A'C'. \end{equation*}

With this insight, the riddle can be formulated as: for which \(A\) and \(B\) is this equation true?

Let's solve it by hand for instructional purposes. With the above expression for \(C\) and noting that \(C' = A B'\), our problem can be rewritten as

\begin{equation*} 1 = AC + A'C' = A( A B' + A' B + A' B') + A'( A B'). \end{equation*}

Clearly, \(A A' = 0\) and \(A A = A\), so that this must reduce to 2\begin{equation*} A B' = 1, \end{equation*} from which follows that \(A=1\), i.e., A is a knight, and \(B'=1\), i.e., B is a crook.

Let's check this with PyEDA.

from pyeda.inter import exprvar

A, B = map(exprvar, 'AB')

The statement \(C\) can be written in PyEDA as:

C = A & ~B | ~A & B | ~A & ~B

and the statement we want to check is

S = A&C | ~A&~C

Let's solve it:

for x in S.satisfy_all():
   print(x)
{B: 0, A: 1}

We get the same result: \(A=1\), i.e., A is a knight, and \(B=0\), i.e., B is a crook.

3 Riddle: Exactly one of us is a crook

Now that we know how to tackle such riddles in an instant with PyEDA we can move on to the next riddle.

Suppose that, instead of the above, A said: "Precisely one of us is a crook." What can we say about A and B now?

The statement of A can now be modelled as \(C=A'B + AB'\).

C = ~A & B | A&~B

And we want again that the following is satisfied:

S = A&C | ~A&~C

for x in S.satisfy_all():
   print(x)
{B: 0, A: 0}
{B: 0, A: 1}

Apperently, the statement of A that only one of the two brothers is a crook allows two solutions. We can only conclude that B is a crook.

It is interesting to note that there's a boolean function in PyEDA to build claim C in another way. Note that according to C, precisely one of A and B is true. This behavior can be obtained with `OneHot`.

from pyeda.inter import OneHot

D = OneHot(A,B)
print(D)
And(Or(~A, ~B), Or(A, B))

4 Riddle: Knights of the same type

What if A has said that: "My brother and I are of the same type".

C = A & B | ~A&~B
S = A&C | ~A&~C

for x in S.satisfy_all():
   print(x)
{B: 1, A: 0}
{B: 1, A: 1}

So, now B is a knight, but A can be either of the two.

5 Riddle: Number of knights in a bus

Eleven inhabitants of the island are sitting in a bus. All of them know each other. When asked about the number of knights in the bus they answered: 3, 2, 5, 7, 5, 3, 4, 0, 3, 5, 5. How many knights are sitting in the bus?

To solve this with PyEDA, we can use the function 'NHot', provided to me by the author of PyEDA:

import itertools

from pyeda.inter import Expression, exprvars
from pyeda.boolalg import exprnode
from pyeda.boolalg.expr import _expr

def NHot(n, *xs, simplify=True):
    """
    Return an expression that means
    "exactly N input functions are true".
    """
    xs = {Expression.box(x).node for x in xs}
    terms = list()
    for hots in itertools.combinations(xs, n):
	args = hots + tuple(exprnode.not_(cold) for cold in (xs - set(hots)))
	terms.append(exprnode.and_(*args))
    y = exprnode.or_(*terms)
    if simplify:
	y = y.simplify()
    return _expr(y)

Let \(X\) be a vector of 11 Boolean variables such that \(X_{i}=1\) if inhabitant \(i\) is a knight.

X = exprvars('X', 11)

Answers = [3, 2, 5, 7, 5, 3, 4, 0, 3, 5, 5]

The problem can be solved by a straigtforward generalization of the solution of the above riddles.

S = 1 
for i, a in enumerate(Answers):
    S = S & (X[i]&NHot(Answers[i], *X) | ~X[i]&~NHot(Answers[i], *X))

for x in S.satisfy_all():
    for y in x:
	print(y, x[y])
X[10] 0
X[9] 0
X[8] 1
X[7] 0
X[6] 0
X[5] 1
X[4] 0
X[3] 0
X[2] 0
X[1] 0
X[0] 1

As \(X_{0}=1\) there must be three knights in the bus (and this checks with the other answers).

6 Riddle: Boxes with chips

P.J. Nahin describes a few interesting puzzles in his book "The Logician and the Engineer, How George Boole and Claude Shannon Created the Information Age". Here is puzzle 1.

On the table before you are three small boxes, labeled A, B , and C. Inside each box is a colored plastic chip. One chip is red, one is white, and one is blue. You do not know which chip is in which box. Then, you are told that of the next three statements, exactly one is true:

  1. box A contains the red chip;
  2. box B does not contain the red chip;
  3. box C does not contain the blue chip.

Determine the color of the chip in each box.

To solve this problem with Boolean logic, Nahin introduces, in Chapter 4, the variable \(Ar\): if \(Ar=1\), then box A contains the red chip, and \(Ar=0\) otherwise. Likewise variables are defined for the other boxes and chips.

Ar, Ab, Aw = map(exprvar, ('Ar', 'Ab', 'Aw'))
Br, Bb, Bw = map(exprvar, ('Br', 'Bb', 'Bw'))
Cr, Cb, Cw = map(exprvar, ('Cr', 'Cb', 'Cw'))

The given info above can be written as:

Info = OneHot(Ar, ~Br, ~Cb)

There are some, implicit, but obvious constraints to be satisfied. Each of the chips is in precisely one box:

r = OneHot(Ar, Br, Cr)  # the red chip is in precisely one box
b = OneHot(Ab, Bb, Cb)
w = OneHot(Aw, Bw, Cw)

A box contains precisely one chip.

A = OneHot(Ar, Ab, Aw)
B = OneHot(Br, Bb, Bw)
C = OneHot(Cr, Cb, Cw)

Finally, the given info and all the constraints have to be true simultaneously.

S = r & b & w & A & B & C & Info

Solve it:

for x in S.satisfy_all():
   print(x)
{Cw: 1, Cb: 0, Cr: 0, Bw: 0, Bb: 0, Br: 1, Aw: 0, Ab: 1, Ar: 0}

This was easy! Box A contains the blue chip, Box B the red chip, and Box C the white chip.

links in nikola and orgmode

I just started using nikola. Of course I want to refer from one page (or post) to another, but I could not find out how. After sending an issue, I got great and fast help. And now I know how to do it.

If things are not yet solved in the nikola plugin for orgmode, put this as the end of the init.el of the plugin:

(org-link-set-parameters
 "link"
 :export (lambda (path desc backend)
	   (cond
	    ((eq 'html backend)
	     (format "<a href=\"link:%s\">%s</a>"
		     path (or desc path)))))
)

And now you can refer to any page like so

link:/bio

or

[[link:/bio][My bio page]]

latex-pythontex-matplotlib-tikzplotlib

The problem

Sometimes I want to use a python script to produce a plot and include this plot in LaTeX. My usual approach was like this. First I wrote a python script that, after some computations, exported the plot to a pdf file (or some other format). Then I imported the pdf file within a figure environment in a LaTeX file. Thus, I had three files, of which two were kind of superfluous, i.e., the python script and the pdf file with the figure. And, after some time, I typically forgot which python script I used to make which pdf file, so I had to include comments in my LaTeX file to explain where to find what, and what did what.

And then there came a day that I did not like this anymore.

My solution

I want one file .tex file that contains all: obviously the story itself, but also the python and the figure, provided of course it takes not a lot of time to make the data for the figure. After some searching and testing, here is an MWE of how I am doing things now with pythontex, matplotlib, and tikzplotlib.

I use arara to compile the LaTeX file, but this just handy, not necessary for the rest to work.

One option.

If you want to run the code, but don't want to show it, use the pycode environment.

% arara: pdflatex: { shell: yes }
% arara: pythontex: {verbose: yes, rerun: modified }
% arara: pdflatex: { shell: yes }

\documentclass{article}
\usepackage{pythontex}
\usepackage{pgfplots}

\begin{document}
\maketitle

If you want to run the code, but don't want to show it, use the \verb+pycode+ environment.

\begin{figure}[h]
\centering
\begin{pycode}

from matplotlib.pylab import plt
import tikzplotlib

plt.plot([1, 2, 3], [1, 5, 2], label="x")

plt.legend()
print(tikzplotlib.get_tikz_code(axis_height="5cm", axis_width="6cm"))
\end{pycode}
\caption{It works.}
\end{figure}
\end{document}

The trick is to not write the output of tikzplotlib to a file, but have it printed as output of the pycode environment. Note that this is an MWE; for a good figure you'll need to tune it to your needs.

Another option

If you like to include the code to show how you made the graph, use the pyblock environment, and then \printpythontex within a figure environment.

% arara: pdflatex: { shell: yes }
% arara: pythontex: {verbose: yes, rerun: modified }
% arara: pdflatex: { shell: yes }

\begin{document}

If you like to include the code to show how you made the graph, use the \verb+pyblock+ environment, and then use \verb+\printpythontex+ within a figure environment.
Like this:

\begin{pyblock}

from matplotlib.pylab import plt
import tikzplotlib

plt.plot([1, 2, 3], [9, -1, 8], label="x")

plt.legend()
print(tikzplotlib.get_tikz_code(axis_height="5cm", axis_width="6cm"))
\end{pyblock}

\begin{figure}[h]
  \centering
  \printpythontex
\end{figure}

\end{document}

My first post

Table of Contents

Here is my first post

I want to write posts and a homepage in org mode. (I dislike markdown, and I detest typing math in rst.) After watching one of the blogs on Cest la Z I considered nikola as a good option to set things up. It turned out to be really easy; I just followed the steps as described Here. I had to install some python packages, but with pip this was a no brainer.

There was one caveat with including source code blocks in org files. After reading the error messages, I noticed that I had to install the emacs htlmize package. The init.el and myinit.org files on my emacs repo show how to set this up.

And now all works!