Archive

Archive for the ‘puzzles’ Category

Jotto (5-letter Mastermind) in the NAO robot

July 9, 2014 Leave a comment

I would like to show how to code the NAO robot to beat us at Jotto (5-letter Mastermind) with python in Choregraphe. I will employ a brute force technique that does not require any knowledge of the English language, the frequency of its letters, or smart combinations of vowels and consonants to try to minimize the number of attempts. It goes like this:

  1. Gather all 5-letter words with no repeated letters in a list.
  2. Choose a random word from that list—your guess—, and ask it to be scored ala Mastermind.
  3. Filter through the list all words that share the same score with your guess; discard the rest.
  4. Go back to step 2 and repeat until the target word is found.

Coding this strategy in python requires only four variables:

  • whole_dict: the list with all the words
  • step = [x for x in whole_dict]: A copy of whole_dict, which is going to be shortened on each step (hence the name). Note that stating step = whole_dict will change the contents of whole_dict when we change the contents of step — not a good idea.
  • guess = random.choice(step): A random choice from the list step.
  • score: A string containing the two digits we obtain after scoring the guess. The first digit indicates the number of correct letters in the same position as the target word; the second digit indicates the number of correct letters in the wrong position.
  • attempts: optional. The number of attempts at guessing words. For quality control purposes.

At this point, I urge the reader to stop reading the post and try to implement this strategy as a simple script. When done, come back to see how it can be coded in the NAO robot.

Read more…

Advertisements

Advanced Problem #18

March 4, 2014 Leave a comment

Another fun problem, as requested by Qinfeng Li in MA598R: Measure Theory

Let f \in L_2(\mathbb{R}) so that g(x)=xf(x) \in L_2(\mathbb{R}) too.

Show that f \in L_1(\mathbb{R}) and \lVert f \rVert_1^2 \leq 8 \lVert f \rVert_2 \lVert g \rVert_2.

I got this problem by picking some strictly positive value \lambda and breaking the integral \int_{\mathbb{R}} \lvert f \rvert\, d\mu as follows:

\begin{array}{rl} \displaystyle{\int_{\mathbb{R}} \lvert f \rvert\, d\mu} &= \displaystyle{\int_{\lvert x \rvert \leq \lambda} \lvert f \rvert\, d\mu + \int_{\lvert x \rvert \geq \lambda} \lvert f \rvert\, d\mu} \\ \\   &= \displaystyle{\int_{-\lambda}^{\lambda} \lvert f \rvert\, d\mu + \int_{\lvert x \rvert \geq \lambda} \tfrac{1}{\lvert x \rvert} \lvert g(x) \rvert\, d\mu} \\ \\   &= \displaystyle{\int_\mathbb{R} \lvert f \rvert \cdot \boldsymbol{1}_{\lvert x \rvert \leq \lambda}\, d\mu + \int_{\mathbb{R}} \lvert g \rvert \cdot  \big( \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda}\big) \, d\mu} \\ \\   &\leq \lVert f \rVert_2 \cdot \big\lVert \boldsymbol{1}_{\lvert x \rvert \leq \lambda} \big\rVert_2 + \lVert g \rVert_2 \cdot \big\lVert \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda} \big\rVert_2 \end{array}

Let us examine now the factors \big\lVert \boldsymbol{1}_{\lvert x \rvert \leq \lambda} \big\rVert_2 and \big\lVert \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda} \big\rVert_2 above:

\big\lVert \boldsymbol{1}_{\lvert x \rvert \leq \lambda} \big\rVert_2 = \sqrt{2\lambda}

\big\lVert \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda} \big\rVert_2 = \displaystyle{ \sqrt{ 2\int_\lambda^\infty \dfrac{dx}{x^2}} = \sqrt{ \dfrac{2}{\lambda}} }

We have thus proven that f \in L_1(\mathbb{R}) with \lVert f \rVert_1 \leq \sqrt{2\lambda} \lVert f \rVert_2 + \sqrt{\tfrac{2}{\lambda}} \lVert g \rVert_2. At this point, all you have to do is pick \lambda = \lVert g \rVert_2 / \lVert f \rVert_2 (provided the denominator is not zero) and you are done.

Categories: Analysis, puzzles, Teaching

More on Lindenmayer Systems

September 24, 2013 2 comments

We briefly explored Lindenmayer systems (or L-systems) in an old post: Toying with Basic Fractals. We quickly reviewed this method for creation of an approximation to fractals, and displayed an example (the Koch snowflake) based on tikz libraries.

I would like to show a few more examples of beautiful curves generated with this technique, together with their generating axiom, rules and parameters. Feel free to click on each of the images below to download a larger version.

Note that any coding language with plotting capabilities should be able to tackle this project. I used once again tikz for \text{\LaTeX}, but this time with the tikzlibrary lindenmayersystems.

name  : Dragon Curve
axiom : X
order : 11
step  : 5pt
angle : 90
rules :
        X -> X+YF+
        Y -> -FX-Y
name  : Gosper Space-filling Curve
axiom : XF
order : 5
step  : 2pt
angle : 60
rules :
	XF -> XF+YF++YF-XF--XFXF-YF+
	YF -> -XF+YFYF++YF+XF--XF-YF
name  : Quadric Koch Island
axiom : F+F+F+F
order : 4
step  : 1pt
angle : 90
rules :
        F -> F+F-F-FF+F+F-F
name  : Sierpinski Arrowhead
axiom : F
order : 8
step  : 3.5pt
angle : 60
rules :
        G -> F+G+F
        F -> G-F-G
name  : ?
axiom : F+F+F+F
order : 4
step  : 2pt
angle : 90
rules :
        F -> FF+F+F+F+F+F-F
name  : ?
axiom : F+F+F+F
order : 4
step  : 3pt
angle : 90
rules :
        F -> FF+F+F+F+FF

Would you like to experiment a little with axioms, rules and parameters, and obtain some new pleasant curves with this method? If the mathematical properties of the fractal that they approximate are interesting enough, I bet you could attach your name to them. Like the astronomer that finds through her telescope a new object in the sky, or the zoologist that discover a new species of spider in the forest.

Sympy should suffice

June 6, 2013 Leave a comment

I have just received a copy of Instant SymPy Starter, by Ronan Lamy—a no-nonsense guide to the main properties of SymPy, the Python library for symbolic mathematics. This short monograph packs everything you should need, with neat examples included, in about 50 pages. Well-worth its money.

To celebrate, I would like to pose a few coding challenges on the use of this library, based on a fun geometric puzzle from cut-the-knot: Rhombus in Circles

Segments \overline{AB} and \overline{CD} are equal. Lines AB and CD intersect at M. Form four circumcircles: (E)=(ACM), (F)=(ADM), (G)=(BDM), (H)=(BCM). Prove that the circumcenters E, F, G, H form a rhombus, with \angle EFG = \angle AMC.

rhombusincircles

Note that if this construction works, it must do so independently of translations, rotations and dilations. We may then assume that M is the origin, that the segments have length one, A=(2,0), B=(1,0), and that for some parameters a>0, \theta \in (0, \pi), it is C=(a+1) (\cos \theta, \sin\theta), D=a (\cos\theta, \sin\theta). We let SymPy take care of the computation of circumcenters:

import sympy
from sympy import *

# Point definitions
M=Point(0,0)
A=Point(2,0)
B=Point(1,0)
a,theta=symbols('a,theta',real=True,positive=True)
C=Point((a+1)*cos(theta),(a+1)*sin(theta))
D=Point(a*cos(theta),a*sin(theta))

#Circumcenters
E=Triangle(A,C,M).circumcenter
F=Triangle(A,D,M).circumcenter
G=Triangle(B,D,M).circumcenter
H=Triangle(B,C,M).circumcenter

Finding that the alternate angles are equal in the quadrilateral EFGH is pretty straightforward:

In [11]: P=Polygon(E,F,G,H)

In [12]: P.angles[E]==P.angles[G]
Out[12]: True

In [13]: P.angles[F]==P.angles[H]
Out[13]: True

To prove it a rhombus, the two sides that coincide on each angle must be equal. This presents us with the first challenge: Note for example that if we naively ask SymPy whether the triangle \triangle EFG is equilateral, we get a False statement:

In [14]: Triangle(E,F,G).is_equilateral()
Out[14]: False

In [15]: F.distance(E)
Out[15]: Abs((a/2 - cos(theta))/sin(theta) - (a - 2*cos(theta) + 1)/(2*sin(theta)))

In [16]: F.distance(G)
Out[16]: sqrt(((a/2 - cos(theta))/sin(theta) - (a - cos(theta))/(2*sin(theta)))**2 + 1/4)

Part of the reason is that we have not indicated anywhere that the parameter theta is to be strictly bounded above by \pi (we did indicate that it must be strictly positive). The other reason is that SymPy does not handle identities well, unless the expressions to be evaluated are perfectly simplified. For example, if we trust the routines of simplification of trigonometric expressions alone, we will not be able to resolve this problem with this technique:

In [17]: trigsimp(F.distance(E)-F.distance(G),deep=True)==0
Out[17]: False

Finding that \angle EFG = \angle AMC with SymPy is not that easy either. This is the second challenge.

How would the reader resolve this situation?


Instant SymPy Starter

Project Euler with Julia

January 4, 2013 Leave a comment

Disclaimer: Project Euler discourages the posting of solutions to their problems, to avoid spoilers. The three solutions I have presented in my blog are to the three first problems (the easiest and most popular), as a means to advertise and encourage my readers to “push the envelope” and go beyond brute-force solutions.

Just for fun, and as a means to learn Julia, I will be attempting problems from the Project Euler coding exclusively in that promising computer language.

The first problem is very simple:

Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multip les is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

One easy-to-code way is by dealing with arrays:

julia> sum( filter( x->((x%3==0) | (x%5==0)), [1:999] ) )
233168

A much better way is to obtain it via summation formulas: Note that the sum of all multiples of three between one and 999 is given by

3+6+\dotsb+999 = 3 (1+2+\dotsb+333) = 3 \frac{333\cdot 334}{2} = 166833.

Similarly, the sum of all multiples of five between one and 995 is given by

5+10+\dotsb+995 = 5 (1+2+\dotsb+199) = 5 \frac{199\cdot 200}{2} = 99500.

Finally, we need to subtract the sum of the multiples of both three and five, since they have been counted twice. This sum is

15+30+\dotsb+990 = 15 (1+2+\dotsb+66)= 15 \frac{66\cdot 67}{2}= 33165.

The final sum is then, 166833+99500-33165=233168.

Seked

December 16, 2012 Leave a comment

If a pyramid is 250 cubits high and the side of its base 360 cubits long, what is its seked?


Take half of 360; it makes 180. Multiply 250 so as to get 180; it makes 1/2 1/5 1/50 of a cubit. A cubit is 7 palms. Multiply 7 by 1/2 1/5 1/50:

\begin{array}{l|lll} 1&7&&\\ 1/2&3&1/2& \\ 1/5 &1&1/3&1/15\\ 1/50&&1/10&1/25 \end{array}

The seked is 5 \tfrac{1}{25} palms [that is, (3+1/2) + (1+1/3+1/15) + (1/10+1/25)].

A’h-mose. The Rhind Papyrus. 33 AD

The image above presents one of the problems included in the Rhind Papyrus, written by the scribe Ahmes (A’h-mose) circa 33 AD. This is a description of all the hieroglyphs, as translated by August Eisenlohr:

The question for the reader, after going carefully over the English translation is: What does seked mean?

Nezumi San

December 14, 2012 Leave a comment

On January first, a pair of mice appeared in a house and bore six male mice and six female mice. At the end of January there are fourteen mice: seven male and seven female.

On the first of February, each of the seven pairs bore six male and six female mice, so that at the end of February there are ninety-eight mice in forty-nine pairs. From then on, each pair of mice bore six more pairs every month.

  1. Find the number of mice at the end of December.
  2. Assume that the length of each mouse is 4 sun. If all the mice line up, each biting the tail of the one in front, find the total length of mice
Jinkō-ki, 1715
%d bloggers like this: