Developing an Algorithm to Draw Stars

Our goal is to create a new function star, so that star 12, blue draws a blue twelve-pointed star.

Introduction to Functions

Here is the most important concept in all of programming:

Programs define their own functions

A function is a miniature program. In CoffeeScript, a function is written with an arrow -> typed as two symbols next to each other (the minus and the greater-than) like this:

(input) -> something to do

Writing and Naming Functions

A function that advances the turtle by ten times a distance is

(x) -> fd 10 * x

Name a function like any variable, using =.

scoot = (x) -> fd 10 * x

After the definition, we can write scoot 7 or scoot 5 + 2. In other words, scoot can be used just like predefined functions like fd or rt.

Making a star Function

Functions can be long. This code defines a star function using indented lines after the ->:

star = (n, k) ->    # define a function star with two inputs and code to follow:
  pen k             # use the chosen color.
  for [1..n]        # repeat the following n times:
    fd 100          # move forward.
    rt 2 * 360 / n  # turn right using a magic star formula.

speed 10            # draw fast!
star 7, red         # use our newly-defined function!

Exercises

Enter the program above that defines the star function, and save it as "star1". Some tips:
- Since the function is longer than one line, its code is indented below the ->.
- Indenting is important: be sure to indent all the lines in the function neatly.
- The block of code inside the loop inside the function must be doubly-indented.
- Defining star = ... will not run it yet. To run it you must use it: star 7, red.
Test out the star function with different numbers, and note the outcomes below:

Test Outcome Test Outcome

star 5, red star 9, red

star 6, red star 10, red

star 7, red star 11, red

star 8, red star 12, red

Debugging the Algorithm

There is a problem with star whenever we ask for an even number of points:

star = (n, k) ->
  pen k
  for [1..n]
    fd 100
    rt 2 * 360 / n

speed 10
star 8, red

What causes the bug?

The problem is in the "magic" formula 2 * 360 / n. To understand, read on.

The Geometry of Stars

Drawing a star is similar to drawing a regular polygon. After the turtle has gone all the way around all n corners, it will come back to where it started, facing the same direction it started.

The difference between a star and a polygon is its winding number: In a polygon, all the turns total up to 360° because each of the n turns is (360/n)°. So the turtle winds once around the center: its "winding number" is 1. In a star, the turtle turns total to a larger multiple of 360, such as 2×360, which gives it a winding number of 2.

If we change the "magic formula" to 3 * 360 / n, we will get a star with winding number 3. That experiment is shown below.

star = (n, k) ->
  pen k
  for [1..n]
    fd 100
    rt 3 * 360 / n

speed 10
star 8, red

The problem is this: if the winding number evenly divides the number of corners, we retrace old corners exactly. For example, when using the winding number 2 with 8 points, 2 divides 8, and we retrace the same 4 corners twice. The winding number 3 works better.

An Algorithm With an Answer: Picking a Winding Number

How do we pick a winding number for an n-pointed star? We can write an algorithm for that!

To pick a winding number for a star with n points:
1. Check every number c from 2 to n as follows:
  1. If c not a divisor of n:
    1. Then c is our answer.

Translated from words into CoffeeScript:

winding = (n) ->        # define a function named winding.
  for c in [2..n]       # vary c from 2 to n, starting at 2.
    if (n % c) isnt 0   # if c is not a divisor of n then:
      return c          # c is the answer.

write winding 8         # run our function and write the answer.

Here are tools that we used to write this algorithm in CoffeeScript:

for c in [2..n] Control. Here c is a looping variable. When for is used with a looping variable, it repeats its block of code once for each value of in the range, or until a special command like return quits the loop.

if Control. if condition runs the indented code only when the condition is true.

% Arithmetic. The "modulo" arithmetic operator, written using the percent symbol x % y, calculates the remainder when x is divided by y. For example, 15 % 5 is 0 becuase 5 divides 15 exactly, but 15 % 4 is 3.

isnt Arithmetic. x isnt y tests if two values are unequal. For example, (n % c) isnt 0 tests if there is a nonzero remainder when n is divided by c.

return Control. When inside a function, return answer ends the calculation.

Exercises

Enter the program above that defines the winding function, and save it as "winding". Remember:
- Indenting is important: be sure to indent all the lines in the function neatly.
- Lines doubly-indented after the while will happen inside the loop.
- Since you want to return the answer outside the loop, return should not be doubly-indented. But since the return is part of the function, it should be singly-indented.
Test out the winding function with different numbers, and note the outcomes below:

Test Outcome Test Outcome

winding 5 winding 9

winding 6 winding 10

winding 7 winding 11

winding 8 winding 12

Using one Function inside Another

After we define winding, we can use it anywhere, including inside the star function. Here is how:

winding = (n) ->        # define the function winding
 for c in [2..n]
   if (n % c) isnt 0
     return c 

star = (n, k) ->        # define the function star
  pen k
  w = winding n         # use winding to pick w
  for [1..n]
    fd 100
    rt w * 360 / n      # use w as the winding number

star 12, purple         # draw a star!

The Importance of Testing

It is important to test algorithms! If you test this algorithm carefully, you will find that it still does not work for some values of n. For example, star 18, red draws a shape with only 9 stars.

It turns out that a better way to choose a winding number is to choose a number that has no common divisors with n (other than 1).

The following is Euclid's algorithm to calculate the greatest common divisor of two numbers:

gcd = (a, b) ->
  while b isnt 0    # repeat the indented lines while b isn't zero:
    if a > b        #  if a is greater than b, then do this:
      a = a - b     #   replace a with the difference (a - b)
    else            #  otherwise (if a is not greter than b):
      b = b - a     #   replace b with the difference (b - a)
  return a          # after the loop is done, the answer is a

If a and b have no common divisors, then gcd(a, b) is 1.

Exercises

Save the top program on this page as "star2" and test it. For what number larger than 18 does the algorithm draw the wrong number of corners? ______
Create a program called "star3" that modifies winding to use gcd instead of %:
1. Add the definition of gcd to your program before you use it.
2. Make your program find a value for c that satisfies the condition gcd(n, c) is 1.
3. Test the program carefully. How many corners are drawn by star 18, red? ______
The "pointiest" stars are produced when the winding number is closest to half of n. Create a program "star4" that produces pointy stars:
1. The primitive function floor rounds down, so floor(n/2) is half of n, rounded down.
2. Experiment with a reversed loop for [floor(n/2)..1].
3. For which positive integer n does star draw the least-pointy shape? ______
Make a version named "star5" that uses speed Infinity, pen path and fill gold.