The Pledge Maze-solving Algorithm

   John Pledge was a 12 year-old Exeter, England school student when he invented the maze-solving algorithm that bears his name.

   His algorithm collects local information by adding turns to the left as positive numbers and turns to the right as negative values to a variable called Total Turning.

   Total Turning is initially set to zero. The robot then moves forward until it strikes a barrier. It turns left, adding the angle measure of the turn to Total Turning and then executes the rest of the algorithm until Total Turning equals zero degrees (not 360º) that indicates the robot has navigated around the barrier. The algorithm resets Total Turning to zero, and the robot again moves forward until it strikes another barrier. And so on.

    A complete discussion of the Pledge algorithm can be found in the book Turtle Geometry, by Harold Abelson and Andrea A. diSessa published by the MIT Press in 1980.

    In the book, I was amazed to learn that if a robot following the Pledge algorithm can escape the interior of a capital letter G, then the robot can escape from any of the mazes commonly seen in books.

    Years ago (1986) I implemented the Pledge algorithm in Terrapin Logo. Searching Scratch for Pledge, I found a project ( http://scratch.mit.edu/projects/763827/) with all of the variable names written in a foreign language. I remixed the project by decoding the variable names into English. I discovered that my Logo algorithm and the remixed algorithm used the same technique of ‘holding the right hand on the wall of the maze’.

   I have shared, on the Scratch website, three Pledge Algorithm projects. The first is the Letter G-Maze Test project that tests the Scratch version of the Pledge algorithm.

   You can view and download this project by clicking on the following link.

http://scratch.mit.edu/projects/2814655/

   The second Scratch project, Pledge Algorithm Maze, pays homage to John Pledge by creating a maze made of the capital letters of his last name. The algorithm from the Letter G project was simply copied into this project. It was drawing the maze that took time.

   You can view and download this project by clicking on this link.

http://scratch.mit.edu/projects/2814737/

   The third project, The Pledge Algorithm - Large Maze project, adds a much more complicated maze than the first two projects. But again, exactly the same Pledge algorithm code was copied into this project. The little robot will now navigate through the maze from any point within the maze.

   You can also view and download this project by clicking on this link.

http://scratch.mit.edu/projects/2823071/

   I have written a written a document that describes, in detail, the Pledge Algorithm. You can obtain a copy of this document, free, by sending an email request to

grandadscience@gmail.com

Spirolaterals in Scratch

   Way back in the early 1980s, the first Apple II (Integer BASIC) program I ever saw programmed a pencil and graph paper exploration called Spirolaterals. I had a lot of success using Spirolaterals with middle school and secondary students. I used them to introduce the concept of mathematical conjecture.

   The simplest spirolateral is defined as follows:

   Start at some grid point on the Cartesian plane.

      move forward x steps, turn right 90,

      move forward 2x steps, turn right 90,

      move forward 3x steps, turn right 90.

      move forward 4x steps, turn right 90

      …

      move forward nx steps, turn right.

   The coefficient of the last x is called the order.

   This graphic shows the path of a 4x  or order 4 spirolateral.

   The order can be repeated and the number of repetitions is called the cycle. In the following graphic the order 3 spirolateral has been repeated 4 times, starting with the red, then the green, the blue, and finishing with the black order 3. 

 As is evident in the graphic, the order 3 cycle 4 spirolateral closes. It’s the relationship between order and cycle that can be explored and, by reviewing order-cycle data, a conjecture can be formed.

   The following graphic is a screen shot of the Scratch program that just computed the path followed by an order 9 cycle 4 spirolateral.

   This project can be viewed and downloaded by clicking on the following link.

http://scratch.mit.edu/projects/11260219/

    The second Spirolateral Scratch project mixes left and right turns. This greatly increases the number of patterns an order 5 spirolateral can compute. For example, there are 32 ways to order right and left turns for Order 5. In the graphic below, the right-right-left-right-right pattern for order 5 cycle 4 has been computed.

   This project is also a simple exercise for learning about how to store and retrieve data from a list.

   If enough data is collected by experiment, patterns in behavior do emerge. In other words, there is a relationship between order and cycle in this project that also leads to a conjecture.

   This project, Spirolateral Bot 2, can be viewed and downloaded by clicking on this link.

http://scratch.mit.edu/projects/11267799/

    Patterns really begin to get complicated (and even more interesting) when other turns, like 60 degree turns, and both left

and right turns are allowed.

   The project Spirolateral Bot 3 implements 60º right turns but can easily be modified to allow turns of any degree and both left and right turns. Doing so would make a nice exercise.

   In the graphic, an order 5 cycle 3 spirolateral has been computed.

   The project can also be viewed and downloaded by clicking on the link below.

http://scratch.mit.edu/projects/11265861/

    I do have pdf files for Spirolateral Bots 1 and 2 that go into more detail about programming spirolaterals in Scratch. To request a free copy, send an email to grandadscience@gmail.com

Five More Methods for Computing the Sierpinski Triangle

   In a previous post (see An Iconic Image of Deterministic Chaos, February 23, 2013), I shared a Scratch project that used mathematician Michael Barnsley’s Collage theorem to compute the Sierpinski triangle.
   I know five other methods for computing the same image;
(1) by playing the Chaos game, 
(2) by coloring the odd numbers in Pascal’s triangle, 
(3) using recursion and the initiator-generator method, 
(4) using the Lindenmayer L-system method, and 
(5) by using Wolfram’s linear cellular automaton, Rule 90.

   It’s the last method, Wolfram’s Rule 90, that is the subject of this post. Here is Rule 90.

   For any three-cell group, the state of the center cell, in the next generation, is determined by the black and white pattern of the three cells. Examine Rule 90 and you will find that the center cell transforms to a black cell in the next generation if the XOR operator (black = 1 or white = 0) of the left and right cells returns a 1 (black).

   You can view this project in action by clicking on this link. You do not need to have Scratch installed as the program will run in your browser.

http://scratch.mit.edu/projects/11024434/

   If you would like a detailed walk-through of Wolfram’s Rule 90, in a PDF file, email your request to:

mail to:grandadscience@gmail.com.